Method and apparatus for storing survivor paths in a Viterbi detector using systematic pointer exchange
View Patent ↗Methods and apparatus are provided for storing survivor paths in a Viterbi detector. The invention maintains at least one register and at least one pointer for each state. Each register stores a bit sequence associated with a Viterbi state and each pointer points to one of the registers. One or more predefined rules based on a trellis structure are employed to exchange one or more of the pointers. A survivor path memory is also disclosed for a Viterbi detector. The survivor path memory comprises a plurality of columns, each associated with a different time step, and an input processor. Each column comprises a flip flop for storing one bit or portion of a bit sequence associated with a Viterbi state; and a multiplexer for each state controlled by a case signal indicating a time step, the multiplexer selecting a state from a previous time step, wherein an output of the multiplexer of a given state is connected to at least one data input of a flip flop of the given state. The input processor generates a control signal that exchanges one or more pointers based on a trellis structure, wherein each of the pointers points to one of the flip flops.
1. A method for storing survivor paths in a Viterbi detector, comprising:
maintaining at least one register and at least one pointer for each state, wherein each of said registers stores a bit sequence associated with a Viterbi state and each of said pointers points to one of said registers; and
employing one or more predefined rules based on a trellis structure to exchange one or more of said pointers.
2. The method of claim 1 , further comprising transforming said trellis to one or more butterfly trellises.
3. The method of claim 1 , further comprising collapsing said trellis to combine a plurality of steps into a single step.
4. The method of claim 1 , wherein one or more of said states maintain values and wherein said associated pointers are maintained by said one or more predefined rules.
5. The method of claim 1 , wherein one or more of said states maintain values for each cycle and wherein said associated pointers are maintained by said one or more predefined rules unless a change is required.
6. The method of claim 1 , wherein said one or more predefined rules exchange said one or more pointers based on a current cycle.
7. A system for storing survivor paths in a Viterbi detector, comprising:
a memory; and
at least one processor, coupled to the memory, operative to:
maintain at least one register and at least one pointer for each state, wherein each of said registers stores a bit sequence associated with a Viterbi state and each of said pointers points to one of said registers; and
employ one or more predefined rules based on a trellis structure to exchange one or more of said pointers.
8. The system of claim 7 , wherein said trellis structure comprises one or more butterfly trellises.
9. The system of claim 7 , wherein said trellis structure has been collapsed to combine a plurality of steps into a single step.
10. The system of claim 7 , wherein one or more of said states maintain values and wherein said associated pointers are maintained by said one or more predefined rules.
11. The system of claim 7 , wherein one or more of said states maintain values for each cycle and wherein said associated pointers are maintained by said one or more predefined rules unless a change is required.
12. The system of claim 7 , wherein said one or more predefined rules exchange said one or more pointers based on a current cycle.