Viterbi decoding device and method for decoding a signal produced by a convolutional encoder
View Patent ↗A Viterbi decoding device to decode a signal produced by a convolutional encoder is described. The device may include: an analog-to-digital conversion unit to extract a soft symbol S=(S 0 , S 1 ) from the signal, the soft symbol including a first sample value S 0 and a second sample value S 1 ; and a digital processing unit to compute, for each of the N states, a branch metric value of BM — 0 _K in dependence on the soft symbol S, K being an index identifying the respective state. The digital processing unit may store the soft symbol S as a complex number S=S 0 +J*S 1 in a complex number format; and compute a complex branch metric value BM — 0 _(K, K′)=BM — 0 _K+J*BM — 0 _K′ in a complex number format on the basis of the soft symbol S, with K different from K′.
1. A Viterbi decoding device for decoding a signal produced by a convolutional encoder, said encoder having N different states, each of said N states having two predecessor states, each branch from each of said two predecessor states having a static code word CW=(B 0 , B 1 ) having a first bit B 0 and a second bit B 1 , said first bit B 0 having either a value −1 or +1 and said second bit B 1 having either the value −1 or +1, said signal having a sequence of code words, said device comprising:
an analog-to-digital conversion unit arranged to extract a soft symbol S=(S 0 , S 1 ) from said signal, said soft symbol comprising a first sample value S 0 and a second sample value S 1 ; and
a digital processing unit connected to said analog-to-digital conversion unit and arranged to compute, for each of said N states, a branch metric value BM_ 0 _K in dependence on said soft symbol S, K being an index identifying a respective state;
said digital processing unit arranged to:
store said soft symbol S as a complex number S=S 0 +J*S 1 in a complex number format; and
compute a complex branch metric value BM_ 0 _(K, K′)=BM_ 0 _K+J*BM_ 0 _K′ in the complex number format on the basis of said soft symbol S, with K different from K′.
2. The device of claim 1 , each of said branch metric values BM_ 0 _K indicating a distance D(CW, S) between said soft symbol S and the codeword CW associated with the transition from one of said two predecessor states to the state with index K.
3. The device of claim 2 , said distance D(CW, S) being a Euclidean distance.
4. The device of claim 2 , said distance being defined as
D ( CW, S )= D ( B 0, B 1, S 0, S 1)=( S 0− B 0)**2+( S 1− B 1)**2.
5. The device of claim 1 , wherein
BM_ 0 _K=S 0 +S 1 if CW_K=(−1, −1);
BM_ 0 _K=S 0 −S 1 if CW_K=(−1, 1);
BM_ 0 _K=−S 0 +S 1 if CW_K=(1, −1);
BM_ 0 _K=−S 0 −S 1 if CW_K=(1, 1)
for any K identifying one of said N states, CW_K being the code word CW associated with the transition from one of said two predecessor states to the state with index K.
6. The device of claim 1 , said digital processing unit arranged to compute said complex branch metric value BM_ 0 _(K, K′)=BM_ 0 _K+J*BM_ 0 _K′ by either:
multiplying S and (1−J); or
multiplying conj(S) and (−1+J); or
multiplying conj(S) and (1−J); or
multiplying S and (−1+J).
7. The device of claim 1 , said digital processing unit arranged to perform one or more complex algebra operations to compute the real part BM_ 0 _K and the imaginary part BM_ 0 _K′ of said complex branch metric value BM_ 0 _(K, K′) simultaneously.
8. The device of claim 1 , comprising storing said branch metric values BM_ 0 _K as a vector (BM_ 0 _ 0 , BM_ 0 _ 1 , . . . , BM_ 0 _{N−1}), each pair (BM_ 0 _{2*K}, BM_ 0 _{2*K+1}) among the components of said vector being associated with one of the following pairs of code words: (CW 0 , CW 2 ), (CW 2 , CW 0 ), (CW 1 , CW 3 ), and (CW 3 ,CW 1 ), wherein CW 0 , CW 1 , CW 2 , and CW 3 denote the two-bit code words (−1, −1), (−1, 1), (1, −1), and (1, 1), respectively.
9. The device of claim 1 , said digital processing unit being programmable.
10. The device of claim 1 , said digital processing unit being a digital signal processor.
11. A Viterbi decoding method for decoding a signal produced by a convolutional encoder, said encoder having N different states, each of said N states having two predecessor states, each branch from each of said two predecessor states having a static codeword CW=(B 0 , B 1 ) a first bit B 0 and a second bit B 1 , said first bit B 0 having either a value −1 or +1 and said second bit B 1 having either the value −1 or +1 , said signal having a sequence of code words said method comprising:
extracting a soft symbol S=(S 0 , S 1 ) from said signal, said soft symbol comprising a first sample value S 0 and a second sample value S 1 ;
for each of said N states, computing a branch metric value BM_ 0 _K in dependence on said soft symbol S, K being an index identifying a respective one of said N states;
said computation of said branch metric values comprising:
storing said soft symbol S as a complex number S=S 0 +J*S 1 using a complex number format, J being the imaginary unit; and
computing a complex branch metric value BM_ 0 _(K, K′)=BM_ 0 _K+J*BM_ 0 _K′ in the complex number format in dependence on said complex number S, with K different from K′.
12. The method of claim 11 , further comprising:
updating a path metric value PM_K in dependence on said branch metric value BM_ 0 _K.
13. The method of claim 11 , each of said branch metric values BM_ 0 _K indicating a distance D(CW, S) between said soft symbol S and the codeword CW associated with the transition from one of said two predecessor states to the state with index K.
14. The method of claim 13 , said distance D(CW, S) being a Euclidean distance.
15. The method of claim 13 , said distance being defined as
D ( CW, S )= D ( B 0, B 1, S 0, S 1)=( S 0− B 0)**2+( S 1− B 1)**2.
16. The method of claim 11 , wherein
BM_ 0 _K=S 0 +S 1 if CW_K=(−1, −1);
BM_ 0 _K=S 0 −S 1 if CW_K=(−1, 1);
BM_ 0 _K=−S 0 +S 1 if CW_K=(1, −1);
BM_ 0 _K=−S 0 −S 1 if CW_K=(1, 1)
for any K identifying one of said N states, CW_K being the code word CW associated with the transition from one of said two predecessor states to the state with index K.
17. The method of claim 11 , further comprising:
computing said complex branch metric value BM_ 0 _(K, K′)=BM_ 0 _K+J*BM_ 0 _K′ by either:
multiplying S and (1−J); or
multiplying conj(S) and (−1+J); or
multiplying conj(S) and (1−J); or
multiplying S and (−1+J).
18. The method of claim 11 , further comprising:
performing or more complex algebra operations to compute the real part BM_ 0 _K and the imaginary part BM_ 0 _K′ of said complex branch metric value BM_ 0 _(K, K′) simultaneously.
19. The method of claim 11 , comprising storing said branch metric values BM_ 0 _K as a vector (BM_ 0 _ 0 , BM_ 0 _ 1 , . . . , BM_ 0 _{N−1}), each pair (BM_ 0 _{2*K}, BM_ 0 _{2*K+1}) among the components of said vector being associated with one of the following pairs of code words: (CW 0 , CW 2 ), (CW 2 , CW 0 ), (CW 1 , CW 3 ), and (CW 3 ,CW 1 ), wherein CW 0 , CW 1 , CW 2 , and CW 3 denote the two-bit code words (−1, −1), (−1, 1), (1, −1), and (1, 1), respectively.
20. A Viterbi decoding device comprising:
an analog-to-digital conversion unit to extract a soft symbol S=(S 0 , S 1 ) from a signal produced by a convolutional encoder; and
a digital processing unit to communicate with the analog-to-digital conversion unit, the digital processing unit to:
compute, for each of N different states of the signal, a branch metric value (BM_ 0 _K) in dependence on the soft symbol S, K being an index identifying a respective state;
store said soft symbol S as a complex number S=S 0 +J*S 1 in a complex number format; and
compute a complex branch metric value BM_ 0 _(K, K′)=BM_ 0 _K+J*BM_ 0 _K′ in the complex number format on the basis of said soft symbol S, with K different from K′.