An apparatus and a method for decoding bits of a received signal in a communication system are provided. The method includes determining path metrics of respective states in a trellis corresponding to the received signal, selecting a start state in the trellis for a traceback in a last window of the trellis, repeating the traceback at least twice within the last window, and when the repeating of the traceback is completed, determining the decoded bits of the received signal using a survived path of a last traceback.