초록 ▼

The traceback operation for a Viterbi algorithm can be minimized by producing optimal path values for each state in the trellis, and updating the optimal path values at each state for each symbol. The optimal path value can be used to quickly determine the output values for the system without requir

The traceback operation for a Viterbi algorithm can be minimized by producing optimal path values for each state in the trellis, and updating the optimal path values at each state for each symbol. The optimal path value can be used to quickly determine the output values for the system without requiring a traceback which would typically require a memory read for each transmitted symbol.

대표청구항 ▼

1. A method of implementing a Viterbi algorithm comprising:calculating branch metrics for branches of a Viterbi trellis; combining the branch metrics with old path metrics to produce candidate path metrics; selecting a new path metric associated with a selected trellis path for each state in the Vit

1. A method of implementing a Viterbi algorithm comprising:calculating branch metrics for branches of a Viterbi trellis; combining the branch metrics with old path metrics to produce candidate path metrics; selecting a new path metric associated with a selected trellis path for each state in the Viterbi trellis from the candidate path metrics; and composing an optimal path value for each state in the Viterbi trellis, the optimal path value indicating multiple transitions of the selected trellis path. 2. The method of claim 1 wherein the optimal path value comprises optimal path value fragments.3. The method of claim 2 wherein the optimal path value fragments are stored in memory blocks.4. The method of claim 1 further comprising using the optimal path value to determine an output value.5. The method of claim 1 wherein the optimal path value for a lowest state of the Viterbi trellis at an end of a memory block indicates transmitted symbols.6. The method of claim 1 further including using traceback pointer to select between two prior optimal path values.7. The method of claim 6 further including selecting an optimal path value from the optimal path value for a state that transitions into a current state.8. The method of claim 1 wherein the Viterbi algorithm is implemented by a reconfigurable chip.9. The method of claim 1 wherein selecting the new path metric and composing the optimal path value operate in parallel.10. An apparatus to implement a Viterbi algorithm comprising:a path metric storage to store a path metric associated with a selected trellis path for each state in a Viterbi trellis; a path update unit to update each path metric; an optimal path value storage to store an optimal path value for each state in the Viterbi trellis, the optimal path value indicating multiple transitions of the selected trellis path; and a an optimal path value update unit to update each optimal path value. 11. The apparatus of claim 10 further comprising an output unit to determine an output value for the Viterbi algorithm.12. The apparatus of claim 11 wherein the output value is the optimal path value for the state with a lowest path metric.13. The apparatus of claim 10 wherein the path update unit and the optimal path value update unit operate in parallel.14. The apparatus of claim 10 wherein the Viterbi algorithm is computed using reconfigurable logic.15. The apparatus of claim 14 wherein the optimal path value update unit uses resources not used by the path update unit.16. The apparatus of claim 10 wherein the optimal path value storage includes multiple memory blocks.17. The apparatus of claim 16 wherein the optimal path value comprises optimal path fragments stored in the multiple memory blocks.18. The apparatus of claim 17 wherein the optimal path value update unit operates on the optimal path value fragments to update the optimal path value.19. The apparatus of claim 17 wherein, during the readback operation, the optimal fragment from one memory block is used to determine a pointer to an optimal path fragment in another memory block.