Patent ID: 6842490

Claim:
A method for decoding transmitted data that has been generated by encoding a sequence of information data with a convolutional encoder that generates convolutional codes based on an input sequence of information data, the encoder characterized by a constraint length K and a data rate k/n, wherein K, k and n are integers the method employing a decoder memory, the method comprising the steps of: (a) storing a first encoder state corresponding to a first time step; (b) beginning at the first time step, performing a first traceback through a plurality of time steps, thereby determining a first input bit corresponding to an encoder state transition from the last time step of the first traceback to the second to last time step of the first traceback; (c) storing in the decoder memory a first possible input data bit corresponding to a transition from an encoder state at a third time step within the first traceback, to an encoder state at a fourth time step within the first traceback, where neither the third nor fourth time steps are the last time step; (d) performing a second traceback beginning at a second time step and encompassing the first time step, thereby determining a second encoder state at the first time step; (e) comparing the first encoder state with the second encoder state; and (f) if the first encoder state is equal to the second encoder state, designating the first possible input data bit as a decoded data bit corresponding to the transition from the encoder state at the third lime step to the encoder state at the fourth time step.