Survivor memory management in a Viterbi decoder
An apparatus for survivor path decoding in a Viterbi decoder with a constraint length of K. The apparatus of the invention includes a best survivor unit, a a register-exchange network, and a trace-back unit. The best survivor unit receives path metrics of 2 K−2 local winner states from which a best state is selected every L iterations. Meanwhile, the register-exchange network generates decision vectors of survivor paths leading to 2 K−1 states at instant i according to decision bits of all states from instant i−L to instant i. Every L iterations the register-exchange network outputs L-bit decision vectors for all states at instant i. Then the trace-back unit stores the decision vectors and finds a global survivor path sequence by following the decision vectors back from the best state at instant i−L. In this manner, L decoded bits can be output from the trace-back unit every L iterations.
1. A survivor path decoding apparatus for a Viterbi decoder with a constraint length of K, comprising:
a best survivor unit for receiving path metrics of 2 K−2 local winner states from which a best state is selected every L iterations_said local winner states are chosen from 2 K−2 pairs of odd and even states, respectively; and
a survivor memory comprising:
a register-exchange network for receiving decision bits of 2 K−1 states and generating decision vectors of survivor paths leading to said 2 K−1 states at instant i according to said decision bits of said 2 K−1 states from instant i−L to instant i, wherein said 2 K−1 states are divided into said 2 K−2 pairs of odd and even states, said decision vectors of said 2 K−1 states are output every L iterations, and each of said decision vectors has a length of L bits; and
a trace-back unit for storing said decision vectors of said 2 K−1 states and finding a global survivor path sequence by following said decision vectors back from the best state at instant i−L, such that L decoded bits are output every L iterations.
2. The apparatus as recited in claim 1 wherein said best survivor unit comprises γ 2-to-1 comparators for choosing the best state among said 2 K−2 local winner states by comparing said path metrics of said 2 K−2 local winner states in L−1 iterations.
3. The apparatus as recited in claim 2 wherein the number of said 2-to-1 comparators, γ, is given by:
γ
=
⌈
2
K
-
2
-
1
L
-
1
⌉
where ┌·┐ denotes a ceiling function.
4. The apparatus as recited in claim 1 wherein said number of L is equal to a divisible factor of a data payload length for a conformant 802.11g system.
5. The apparatus as recited in claim 4 wherein said number of L is equal to 8 for said conformant 802.11g system.
6. The apparatus as recited in claim 1 wherein said survivor memory features a decoding window length of Γ=L(L−2)+K −1.
7. A rate 1/n Viterbi decoder with a constraint length of K comprising:
a branch metric generator for computing a plurality of branch metrics, each of which is a distance between a corresponding branch label and a currently received data symbol including n decision metrics;
an add-compare-select module, responsive to said branch metrics, for generating decision bits of 2 K−1 states along with path metrics of 2 K−2 local winner states, wherein said 2 K−2 local winner states are selected from 2 K−2 pairs of odd and even states, respectively, and said 2 K−1 states are divided into said 2 K−2 pairs of odd and even states;
a best survivor unit for receiving said path metrics of said 2 K−2 local winner states from said add-compare-select module and selecting a best state from among said 2 K−2 local winner states every L iterations; and
a survivor memory comprising:
a register-exchange network for receiving said decision bits of said 2 K−1 states from said add-compare-select module and generating decision vectors of survivor paths leading to said 2 K−1 states at instant i according to said decision bits of said 2 K−1 states from instant i−L to instant i, wherein said decision vectors of said 2 K−1 states are output every L iterations and each of said decision vectors has a length of L bits; and
a trace-back unit for storing said decision vectors of said 2 K−1 states and finding a global survivor path sequence by following said decision vectors back from the best state at instant i−L, such that L decoded bits are output every L iterations.
8. The Viterbi decoder as recited in claim 7 wherein said best survivor unit comprises γ 2-to-1 comparators for choosing the best state among said 2 K−2 local winner states by comparing said path metrics of said 2 K−2 local winner states in L−1 iterations.
9. The Viterbi decoder as recited in claim 8 wherein the number of said 2-to-1 comparators, γ, is given by:
γ
=
⌈
2
K
-
2
-
1
L
-
1
⌉
where ┌·┐ denotes a ceiling function.
10. The Viterbi decoder as recited in claim 7 wherein said number of L is equal to a divisible factor of a data payload length for a conformant 802.11g system.
11. The Viterbi decoder as recited in claim 10 wherein said number of L is equal to 8 for said conformant 802.11g system.
12. The Viterbi decoder as recited in claim 7 wherein said survivor memory features a decoding window length of Γ=L(L−2)+K−1.
13. The Viterbi decoder as recited in claim 7 wherein said decision metrics are hard-decision data if quantized to one-bit precision.
14. The Viterbi decoder as recited in claim 7 wherein said decision metrics are soft-decision data if quantized with more than one bit of precision.