Soft-decision decoding of convolutionally encoded codeword
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
H03D-001/00
H04L-027/06
출원번호
US-0791608
(2001-02-26)
우선권정보
GB-0004765(2000-03-01)
발명자
/ 주소
Jin,Gary Q.
출원인 / 주소
1021 Technologies KK
인용정보
피인용 횟수 :
10인용 특허 :
12
초록▼
A method and apparatus for decoding convolutional codes used in error-correcting circuitry for digital data communication. To increase the speed and precision of the decoding process, the branch and/or state metrics are normalized during the soft decision calculations, whereby the dynamic range of t
A method and apparatus for decoding convolutional codes used in error-correcting circuitry for digital data communication. To increase the speed and precision of the decoding process, the branch and/or state metrics are normalized during the soft decision calculations, whereby the dynamic range of the decoder is better utilized. Another aspect of the invention relates to decreasing the time and memory required to calculate the log-likelihood ratio by sending some of the soft decision values directly to a calculator without first storing them in memory.
대표청구항▼
What is claimed is: 1. A method of decoding a received convolutionally encoded data stream having multiple states s, the data stream having been encoded by an encoder, comprising the steps of: deriving normalized values γ'j(Rk, sj',s)(j=0, 1) of branch metrics γj(Rk, sj',s)(j=0, 1), which
What is claimed is: 1. A method of decoding a received convolutionally encoded data stream having multiple states s, the data stream having been encoded by an encoder, comprising the steps of: deriving normalized values γ'j(Rk, sj',s)(j=0, 1) of branch metrics γj(Rk, sj',s)(j=0, 1), which are defined as γ j(Rk,sj',s)=log(Pr( dk=j,Sk=s,Rk|Sk-1=sj')) and recursively determining values of forward state metrics αk(s) and reverse state metric βk(s) defined as from the normalized values γ'j(Rk, sj',s)(j=0, 1) and previous values αk-1(s') of forward state metrics αk(s) and future values βk+ 1(s') of reverse state metrics βk(s), where Pr represents probability, R1k represents received bits from time index 1 to k, Sk represents the state of the encoder at time index k, Rk represents received bits at time index k, and dk represents transmitted data at time k. 2. A method as claimed in claim 1, wherein the step of recursively determining the values of the state metrics αk (s) and βk(s) uses as said previous values of α k(s) the values αk-1(s0'), αk-1(s1') at time k-1, and as said future values of β k(s) the values βk+1(s0'), βk+1 (s1') at time k+1. 3. A method as claimed in claim 1, wherein the step of recursively determining the values of the state metrics αk (s) and βk(s) includes the step of adding said normalized values γ'j(Rk,sj',s)(j=0, 1) to said previous and future values αk-1(s0'), α k-1(s1') and βk+1(s0'), βk+ 1(s1'). 4. A method as claimed in claim 1, further comprising the step of normalized the values of γj(Rk,sj ',s)(j=0, 1) to zero in each iteration. 5. A method as claimed in claim 1, further comprising the step of normalizing current values of the forward state metrics by adding a maximum value (Smax) of the previous values (αk-1(s) at time k-1. 6. A decoder for a convolutionally encoded data stream having multiple states s, the data stream having been encoded by an encoder, comprising: a normalization unit for normalizing the branch metric quantities γ j(Rk,sj',s)=log(Pr( dk=j,Sk=s,Rk|Sk-1=sj')) to provide normalized quantities γ'j(R k,sj',s)(j=0, 1) adders for adding normalized quantities γ'j (Rk,sj',s)(j=0, 1) to forward state metrics α k-1(s0'), αk-1(s1'), and reverse state metrics βk+1(s0'), βk+1(s 1'), where a multiplexer and log unit for multiplexing the outputs of the adders to produce corrected cumulative metrics αk'(s), and βk'(s), and a second normalization unit for normalizing the corrected cumulative metrics αk'(s) and βk'(s) to produce desired outputs αk(s) and βk(s) where Pr represents probability, R1k represents received bits from time index 1 to k and Sk represents the state of the encoder at time index k, from previous values of αk(s) and future values of βk(s), and from quantities γ'j(Rk,sj',s)(j=0, 1) where γ'j(Rk,sj',s)(j=0, 1) is a normalized value of γj(Rk,sj',s)(j=0, 1), Rk represents received bits at time index k, and dk represents transmitted data at time k. 7. A decoder as claimed in claim 6, wherein said second normalization unit performs a computation Smax on each of previous value αk-1(s), and future value βk+1 (s), and a further adder is provided to add Smax to value α k'(s) and value βk'(s). 8. A decoder as claimed in claim 6, wherein said first normalization unit comprises a comparator receiving inputs γ 0, γ1 having an output connected to select inputs of multiplexers, a first pair of said multiplexers receiving said respective inputs γ0, γ1, a subtractor for subtracting outputs of said first pair of multiplexers, an output of said subtractor being presented to first inputs of a second pair of said multiplexers, second inputs of said second pair of multiplexers receiving a zero input. 9. A method for decoding a convolutionally encoded codeword having multiple states s using a turbo decoder with x bit representation and a dynamic range of 2x-1-1 to-(2x-1-1), comprising the steps of: a) defining a trellis representation of possible states and transition branches of the convolutional codeword having a block length N, N being the number of received samples in the codeword; b) initializing each starting state metric α-1 (s) of the trellis for a forward iteration through the trellis; c) calculating branch metrics γk0(s0', s) and γk1(s1',s); d) determining a branch metric normalizing factor; e) normalizing the branch metrics by subtracting the branch metric normalizing factor from both of the branch metrics to obtain γk1'(s1',s) and γk0'(s0', s); f) summing αk-1(s1') with γ k1'(s1',s), and αk-1(s0') with γk0'(s0',s) to obtain a cumulated maximum likelihood metric for each branch; g) selecting the cumulated maximum likelihood metric with the greater value to obtain αk(s); h) repeating steps c) to g) for each state of the forward iteration through the entire trellis; i) defining a second trellis representation of possible states and transition branches of the convolutional codeword having the same states and block length as the first trellis; j) initializing each starting state metric βN-1 (s) of the trellis for a reverse iteration through the trellis; k) calculating the branch metrics γk0(s 0',s) and γk1(s1',s); l) determining a branch metric normalization term; m) normalizing both of the branch metrics determined in step k) by subtracting the branch metric normalization term from both of the branch metrics determined in step k) to obtain γk1'(s 1',s) and γk0'(s0',s); n) summing βk+1(s1') with γ k1'(s1',s), and βk+1(s0') with γk0'(s0',s) to obtain a cumulated maximum likelihood metric for each branch; o) selecting the cumulated maximum likelihood metric with the greater value as βk(s); p) repeating steps k to o for each state of the reverse iteration through the entire trellis; q) calculating soft decision values P1 and P0 for each state; and r) calculating a log likelihood ratio at each state to obtain a hard decision thereof. 10. The method according to claim 9, wherein step d) includes selecting the branch metric with the greater value to be the branch metric normalizing factor. 11. The method according to claim 9, wherein step l includes selecting the branch metric with the greater value to be the branch metric normalizing term. 12. The method according to claim 9, further comprising: determining a maximum value of αk(s); and normalizing the values of αk(s) by subtracting the maximum value of αk(s) from each value α k(s). 13. The method according to claim 9, further comprising: determining a maximum value of αk-1(s); and normalizing the values of αk(s) by subtracting the maximum value of αk-1(s) from each value α k(s). 14. The method according to claim 9, further comprising: normalizing αk(s) by subtracting a forward state normalizing factor, based on the values of αk-1(s), to reposition the values of αk(s) proximate the center of said dynamic range. 15. The method according to claim 14, wherein, when any one of the values of αk-1(s) is greater than zero, the normalizing factor is between 1 and 8. 16. The method according to claim 14, wherein, when all of the values of αk-1(s) are less than zero and any one of the values of αk-1(s) is greater than-2x-2, the normalizing factor is about-2x-3. 17. The method according to claim 14, wherein, when all of the values of αk-1(s) are less than-2x-2, the normalizing factor is a bit OR value for each αk-1(s). 18. The method according to claim 9, further comprising: determining a maximum value of βk(s); and normalizing the values of βk(s) by subtracting the maximum value of βk(s) from each value βk(s). 19. The method according to claim 9, further comprising: determining a maximum value of βk+1(s); and normalizing the values of βk(s) by subtracting the maximum value of βk+1(s) from each βk(s). 20. The method according to claim 9, further comprising: normalizing βk(s) by subtracting a reverse normalizing factor, based on the values of βk+1(s), to reposition the values of βk(s) proximate the center of said dynamic range. 21. The method according to claim 20, wherein when any one of the values of βk+1(s) is greater than zero the reverse normalizing factor is between 1 and 8. 22. The method according to claim 20, wherein when all of the values of βk+1(s) are less than zero and any one of the βk+1(s) values is greater than-2x-2 the normalizing factor is about-2x-3. 23. The method according to claim 20, wherein when all of the values of βk+1(s) are less than-2x-2 the normalizing factor is a bit OR value for each βk+1(s). 24. A turbo decoder system with x bit representation for decoding a convolutionally encoded codeword comprising: receiving means for receiving a sequence of transmitted signals; trellis means with block length N defining possible states and transition branches of the convolutionally encoded codeword; decoding means for decoding said sequence of signals during a forward iteration and a reverse iteration through said trellis means, said decoding means including: branch metric calculating means for calculating branch metrics γk0(s0',s) and γk1(s 1',s); for use during said forward iteration and during said reverse iteration; branch metric normalizing means for normalizing the branch metrics to obtain normalized branch metrics γk1'(s 1',s) and γk0'(s0',s) during said forward iteration and during said reverse iteration; summing means for adding state metrics αk-1 (s1') with normalized branch metrics γk1'(s 1',s), and state metrics αk-1(s0') with normalized branch metrics γk0'(s0',s) during said forward iteration to obtain cumulated metrics for each branch and for adding state metrics βk+1(s1') with normalized branch metrics γk1(s1',s) and state metrics β k+1(s0') with normalized branch metrics γ k0(s0',s) during said reverse iteration to obtain cumulate metrics for each branch; and selecting means for choosing, during the forward iteration, the cumulated metric with the greater value to obtain α k(s) and, during said reverse iteration, the cumulated metric with the greater value to obtain βk(s); soft decision calculating means for determining the soft decision values Pk0 and Pk1; and log likelihood ratio (LLR) calculating means for determining from the soft decision values the log likelihood ratio for each state to obtain a hard decision therefor. 25. The system according to claim 24, wherein, during the forward iteration, said branch metric normalizing means determines which branch metric γk0'(s0',s) or γk1 '(s1',s) has the greater value, and subtracts the branch metric with the greater value from both branch metrics. 26. The system according to claim 24, further comprising state metric normalizing means for normalizing the values of state metrics αk(s) during the forward iteration, by subtracting a forward state metric normalizing factor from each state metric value αk(s). 27. The system according to claim 26, wherein the state metric normalizing means uses a forward state metric normalizing factor that is a maximum value of αk(s). 28. The system according to claim 26, wherein the state metric normalizing means uses a forward state metric normalizing factor that is a maximum value of αk-1(s). 29. The system according to claim 26, wherein the state metric normalizing means uses a forward state metric normalizing factor that is between 1 and 8, when any one of the values of αk-1 (s) is greater than 0. 30. The system according to claim 26, wherein the state metric normalizing means uses a state metric normalizing factor that is about-2x-3, when all of the state metric values αk-1(s) are less than 0 and any one of the state metric values α k-1(s) is greater than-2x-2. 31. The system according to claim 26, wherein the state metric normalizing means uses a state metric normalizing factor that is a bit OR value for each state metric value αk-1(s), when all of the state metric values αk-1(s) are less than-2x-2. 32. The system according to claim 24, wherein, during the reverse iteration, the reverse state metric normalizing means normalizes the values of βk(s) by subtracting a reverse state metric normalizing factor. 33. The system according to claim 32, wherein the state metric normalizing means uses a reverse state metric normalizing factor that is a maximum value of βk(s). 34. The system according to claim 32, wherein the state metric normalizing means uses a reverse state metric normalizing factor that is a maximum value of βk+1(s). 35. The system according to claim 32, wherein the state metric normalizing means uses a reverse state metric normalizing factor that is between 1 and 8, when any one of the values of βk+1 (s) is greater than 0. 36. The system according to claim 32, wherein the state metric normalizing means uses a state metric normalizing factor that is about-2x-3, when all of the values of βk+1(s) are less than 0 and any one of the values of βk+1(s) is greater than-2x-2. 37. The system according to claim 32, wherein the state metric normalizing means uses a state metric normalizing factor that is a bit OR value for each value of βk+1(s) when all of the values of βk+1(s) are less than-2x-2. 38. The system according to claim 24, wherein the decoding means comprises a single decoder for performing both said forward and reverse iterations.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (12)
Ulmer Elisha J.,ILX ; Stein Jeremy M.,ILX, Efficient trellis state metric normalization.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.