Efficient method for traceback decoding of trellis (Viterbi) codes

A Viterbi decoder for performing a continuous traceback comprising:

• a traceback circuit;
• and
• at least two memory blocks, each having at least two ports and each having a word depth of at least about 4 times the traceback length of the decoder, and wherein each word of memory stores a survivor vector for a time period in the traceback, and wherein the decoder is configured to
• write survivor vectors into the at least two memories simultaneously but offset by a distance in memory locations from the memory location in an adjacent memory block equal to about the traceback length, and
• read, in a traceback mode, the survivor vectors in groups alternately selected from each of the at least two memory blocks.

A method for traceback decoding comprising:

• designating a current state as the state having the best metric by using at least two trace registers each having an input and an output, wherein the output of each of the at least two trace registers is connected to an input of one of at least two data selection blocks and the input of each of the at least two trace registers is connected to an output of a corresponding data selection block and wherein the connection from the output of one of the at least two trace registers to an input of one of the at least two data selection blocks corresponds to the connection between one of the current states and one of its predecessor states in a traceback of the Viterbi trellis;
• selecting a predecessor state to the current state by using a survivor vector corresponding to the predecessor state, wherein the survivor bits corresponding to the predecessor states determine which of the potential predecessor states was the surviving state, and by controlling the inputs to at least one of the at least two data selection blocks;
• and
• determining a new current state using an active value transmitted from the output of one of the at least two data selection blocks to the input of one of the at least two trace registers.

A method for performing continuous traceback decoding comprising:

• writing surviving vectors continuously into each of at least a first and a second memory having at least two ports, each having a word depth of at least 2 times the traceback length v;
• performing a traceback from the first memory for a number of time periods corresponding to the traceback length v without generating decoded bits from that traceback;
• continuing the traceback from the first memory and decoding v bits sequentially from a traceback cycle of said first memory, the traceback length for the v bits varying from v to 2*v, wherein v is an integer;
• performing a traceback from the second memory for v cycles without generating decoded bits from that traceback simultaneously while decoding v bits from the first memory, wherein the traceback commences on survivor vectors written v cycles later than the survivor vectors used for the traceback operation performed on the first memory;
• and
• continuing the traceback from the second memory and decoding v bits sequentially from a traceback cycle of said second memory, the traceback length generating each of the v bits varying from about v to 2*v.

A computer program product comprising:

• a machine readable medium having stored thereon program instructions for a method of performing traceback decoding, the method comprising:
• designating a current state as the state having the best metric by using at least two trace registers each having an input and an output, wherein the output of each of the at least two trace registers is connected to an input of one of at least two data selection blocks and the input of each of the at least two trace registers is connected to an output of a corresponding data selection block and wherein the connection from the output of one of the at least two trace registers to an input of one of the at least two data selection blocks corresponds to the connection between one of the current states and one of its predecessor states in a traceback of the Viterbi trellis;
• selecting a predecessor state to the current state by using a survivor vector corresponding to the predecessor state, wherein the survivor bits corresponding to the predecessor states determine which of the potential predecessor states was the surviving state, and by controlling the inputs to at least one of the at least two data selection blocks;
• and
• determining a new current state using an active value transmitted from the output of one of the at least two data selection blocks to the input of one of the at least two trace registers.

A computer program product comprising:

• writing surviving vectors continuously into each of at least a first and a second memory having at least two ports, each having a word depth of at least 2 times the traceback length v, wherein v is an integer;
• performing a traceback from the first memory for a number of time periods corresponding to the traceback length v without generating decoded bits from that traceback;
• continuing the traceback from the first memory and decoding v bits sequentially from a traceback cycle of said first memory, the traceback length for the v bits varying from v to 2*v;
• performing a traceback from the second memory for v cycles without generating decoded bits from that traceback simultaneously while decoding v bits from the first memory, wherein the traceback commences on survivor vectors written v cycles later than the survivor vectors used for the traceback operation performed on the first memory;
• and
• continuing the traceback from the second memory and decoding v bits sequentially from a traceback cycle of said second memory, the traceback length generating each of the v bits varying from about v to 2*v.