초록 ▼

Methods and apparatus are provided for efficiently implementing a traceback decoding of Viterbi codes. A Viterbi decoder circuit having at least two data selection blocks and at least two trace registers is described. The number of registers corresponds to the number of states in a Viterbi trellis d

Methods and apparatus are provided for efficiently implementing a traceback decoding of Viterbi codes. A Viterbi decoder circuit having at least two data selection blocks and at least two trace registers is described. The number of registers corresponds to the number of states in a Viterbi trellis diagram applicable to encoded data. The trace registers are used to represent the current state best metric and are each configured to send their output to the inputs of the predecessor states representing the possible branches to the current state. The best metric for the predecessor state is determined using a survivor vector stored in memory. Traceback occurs by sequentially reading survivor vectors from memory, using the vectors to control the data selection blocks, and using the trace registers to sequentially identify predecessor states in the traceback.

대표청구항 ▼

What is claimed is: 1. A Viterbi decoder comprising: at least two data selection blocks, each of the at least two data selection blocks having at least two inputs, an output, and control circuitry; at least two trace registers each having an input and an output, wherein the output of each of the at

What is claimed is: 1. A Viterbi decoder comprising: at least two data selection blocks, each of the at least two data selection blocks having at least two inputs, an output, and control circuitry; 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 the 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 circuitry for transmitting survivor vector values from a forward movement through a Viterbi trellis to the control circuitry for each of the at least two data selection blocks to select a signal corresponding to one of the inputs of the data selection block to appear at the output in order to select a predecessor best metric state in a traceback. 2. The Viterbi decoder described in claim 1, 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 a plurality of current states and one of its predecessor states in a traceback of the Viterbi trellis. 3. The Viterbi decoder described in claim 1, wherein the survivor vector values are determined by add-compare select circuitry from received encoded data in the forward movement through the Viterbi trellis. 4. The Viterbi decoder described in claim 1, wherein the number of trace registers corresponds to a constraint length L of an encoder used to encode data into one of 2^(L-1) states, wherein L is an integer. 5. The Viterbi decoder described in claim 1, wherein the number of trace registers is equal to the number of data selection blocks. 6. The Viterbi decoder described in claim 2, wherein a current state having the best metric is represented by an active value in the trace register corresponding to that state. 7. The Viterbi decoder described in claim 1, wherein the data selection blocks comprise multiplexers. 8. The Viterbi decoder described in claim 1, wherein the trace registers are configured to operate sequentially to store values received at their inputs upon detection of a predetermined electrical clock signal or signal change, each sequential value corresponding to a predecessor state for a current state, as traced in a Viterbi trellis diagram. 9. The Viterbi decoder described in claim 1, wherein a predetermined portion of the survivor vector identifies a predecessor state for a current state, said portion comprising at least one bit. 10. The Viterbi decoder described in claim 1, further configured to identify the predecessor best metric state to a current best metric state by using the predetermined portion of the survivor vector corresponding to the current best metric state to control the control circuitry for each of the at least two data selection blocks to select a signal corresponding to one of the inputs of the data selection block to appear at the output. 11. The Viterbi decoder described in claim 1, wherein the trace registers comprise a flip flop. 12. The Viterbi decoder described in claim 1, further comprising a memory for storage of survivor vector values, the memory having at least two ports. 13. The Viterbi decoder described in claim 12, wherein the memory is set up as a circular buffer. 14. The Viterbi decoder described in claim 13, further configured so that the sequence of survivor vectors read from memory corresponds to the survivor states determined in the forward movement through the Viterbi trellis. 15. The Viterbi decoder described in claim 1, further configured to generate a decoded bit by performing a logical "OR" operation on the bits output from the trace registers corresponding to the lower half of the Viterbi trellis. 16. The Viterbi decoder described in claim 1, further configured to generate at least two decoded bits during each traceback cycle. 17. The Viterbi decoder described in claim 1, wherein a traceback length used to generate a second of the at least two decoded bits during each traceback cycle is one larger than the traceback length used to generate the first of the at least two decoded bits, and each succeeding bit decoded during said traceback cycle uses a traceback length one larger than used for the preceding decoded bit. 18. The Viterbi decoder described in claim 1, wherein the number of bits decoded per traceback cycle corresponds to the next integer value rounded up from the result of the traceback length selected divided by a constraint length of an encoder used to encode data to more efficiently match the decoding rate with the survivor vector generation rate. 19. The Viterbi decoder described in claim 16, further comprising a serial shift register to reverse the order of the decoded bits generated during each traceback cycle. 20. The Viterbi decoder described in claim 1, wherein the decoder is configured within a programmable logic device. 21. 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. 22. The Viterbi decoder described in claim 21, wherein the traceback circuit comprises: at least two data selection blocks, each of the at least two data selection blocks having at least two inputs, an output, and control circuitry; at least two trace registers 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 the 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 circuitry for transmitting survivor vector values corresponding to a forward movement through a Viterbi trellis and read from the at least two memories to the control circuitry for each of the at least two data selection blocks to select a signal corresponding to one of the inputs to appear at the output. 23. The Viterbi decoder described in claim 21, further comprising an add-compare-select circuit to generate and transmit survivor vectors to the at least two memory blocks. 24. The Viterbi decoder described in claim 21, wherein the survivor vectors are written continuously to the at least two memory blocks. 25. The Viterbi decoder described in claim 21, further comprising an output memory having at least two ports for storing decoded bits generated in a reversed order. 26. The Viterbi decoder described in claim 21, further configured to: commence a first traceback cycle when at least about 2*v survivor vectors have been written into one of the at least two memories and to generate a decoded bit after at least about v survivor vectors have been read after commencement of the first traceback cycle, where v is an integer value of the traceback length; commence a second traceback operation cycle substantially concurrently with the commencement of generation of decoded bits in the first traceback cycle; and generate decoded bits from the second traceback operation after at least about v survivor vectors have been read from the time of commencement of the second traceback cycle. 27. The Viterbi decoder described in claim 26, wherein the second traceback cycle commences traceback on survivor vectors written about v clock cycles later than the survivor vectors used for the first traceback cycle. 28. The Viterbi decoder described in claim 26, wherein at least about v decoded bits are generated during each of the first traceback cycle and the second traceback cycle. 29. The Viterbi decoder described in claim 26, wherein groups of at least v bits are decoded and written to the output memory alternately from the first traceback cycle and the second traceback cycle. 30. The Viterbi decoder described in claim 21, further comprising a read counter having the number of states corresponding to 2 times the traceback length and wherein the decoder is further configured to read decoded bits from the output memory by counting down using the read counter. 31. The Viterbi decoder described in claim 21, wherein the decoder is configured within a programmable logic device. 32. 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. 33. The method for traceback decoding described in claim 32, further comprising designating a current state, selecting a predecessor state, and determining a new current state until the traceback has been completed. 34. 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. 35. 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. 36. 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.