Iterative concatenated convolutional Reed-Solomon decoding method

• US 20060248430A1
• Filed: 04/28/2005
• Published: 11/02/2006
• Est. Priority Date: 04/28/2005
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Sandbridge Technologies Incorporated (Qualcomm, Inc.)
• Inventors: Iancu, Daniel, Ye, Hua, Glossner, John
• Granted Patent: US 7,370,258 B2
• Time in Patent Office: Days
• US Class Current: 714/755
• CPC Class Codes: H03M 13/153 using the Berlekamp-Massey algorithm
• CPC Class Codes: H03M 13/154 Error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial
• CPC Class Codes: H03M 13/156 Encoding or decoding using time-frequency transformations, e.g. fast Fourier transformation
• CPC Class Codes: H03M 13/1585 Determination of error values
• CPC Class Codes: H03M 13/2936 comprising an outer Reed-Solomon code and an inner convolutional code
• CPC Class Codes: H03M 13/2948 Iterative decoding H03M13/2957 takes precedence
• CPC Class Codes: H03M 13/4146 soft-output Viterbi decoding according to Battail and Hagenauer in which the soft-output is determined using path metric differences along the maximum-likelihood path, i.e. "SOVA" decoding

Abstract

A method and apparatus for decoding a coded data stream of bits using an inner decoder, deinterleaver and an outer decoder. The outer decoder first decodes by error correction decoding for r errors per word. The decoding is terminated and a decoded word is outputted if the syndromes of the corrected word of the first decoding are all zeros. If the syndromes of the corrected word of the first decoding are not all zeros, a second decoding is performed by error decoding and erasure for the number of errors reduced by one and the number of erasures increased to two. The decoding is terminated and a decoded word is outputted if the syndromes of the corrected word of the second decoding are all zeros. If the syndromes of the corrected word of the second decoding are not all zeros, the second decoding by correcting and erasure decoding is repeated for the number of errors reduced by one and the number of erasures increased by two for each iteration of the second decoding.

Claims

1. A method of decoding an encoded data stream of bits comprising:

inner decoding the bits to produce hard decision of coded bit information and a soft decision of reliability bit information for each bit;

deinterleaving the coded and reliability bit information; and

outer decoding the deinterleaved coded and reliability bit information by

a) first decoding by error correction decoding for r errors per word;

b) terminating the decoding and outputting a decoded word if the syndromes of a corrected word of the first decoding are all zeros,

c) second decoding by error correcting and erasure decoding for the number of error decreased by one and two erasures if the syndromes of the corrected word of the first decoding are not all zeros,

d) terminating the decoding and outputting a decoded word if the syndromes of a corrected word of the second decoding are all zeros, and

e) repeating the second decoding by error correcting and erasure decoding for the number of errors decreased by one and the number of erasures increased by two for each iteration of the second decoding if the syndromes of the corrected word of the previous second decoding are not all zeros.

2. The method according to claim 1, wherein the outer decoding is Reed-Solomon decoding.

3. The method according to claim 1, wherein the inner decoding is concatenated convolutional decoding.

4. The method according to claim 1, wherein the inner decoding is Soft Output Viterbi Algorithm decoding.

5. The method according to claim 1, wherein the second decoding is terminated without an output if the syndromes are not all zeros for the corrected word of the second decoding by error correcting and erasure decoding for zero number of errors and 2r number of erasures.

6. The method according to claim 1, including:

prior to the second decoding, deriving an error locator polynomial and comparing the degree of the error locator polynomial to the decreased numbers of errors;

if the degree of the error locator polynomial is greater than the decreased numbers of errors, decreasing the number of errors by one, increase the number of erasures by two and repeating the deriving and comparing step; and

if the degree of the error locator polynomial is equal or less than the decreased numbers of errors, perform the second decoding.

7. The method according to claim 6, wherein if the degree of the error locator polynomial is equal or less than the decreased numbers of errors, terminating the decoding and outputting a decoded word if the syndromes of a corrected word of the second decoding are all zeros and terminating without an output if the syndromes are not all zeros for the corrected word of the second decoding.

8. The method according to claim 1, wherein the decoding is performed on packets of data.

9. The method according to claim 1, wherein the method is performed in software in a communication device.

10. A communication device including a decoder performing the method of claim 1.

11. A method of decoding an encoded data stream of bits comprising:

inner decoding the bits to produce hard decision of coded bit information and a soft decision of reliability bit information for each bit;

deinterleaving the coded and reliability bit information; and

outer decoding the deinterleaved coded and reliability bit information by

a) first decoding by error correction decoding for r errors per word,

b) terminating the decoding and outputting a decoded word if the syndromes of a corrected word of the first decoding are all zeros,

c) reducing the number of errors r by one and increasing the number of erasures by two if the syndromes of the corrected word of the first decoding are not all zeros,

d) deriving an error locator polynomial and comparing the degree of the error locator polynomial to the decreased numbers of errors if the syndromes of a corrected word of the first decoding are not all zeros,

e) if the degree of the error locator polynomial is greater than the decreased numbers of errors, decreasing the number of errors by one, increase the number of erasures by two and repeating the deriving and comparing step, and

f) if the degree of the error locator polynomial is equal to or less than the decreased numbers of errors, perform a second decoding by error correcting and erasure decoding.

12. The method according to claim 11, wherein if the degree of the error locator polynomial is equal or less than the decreased numbers of errors, 1) terminate the decoding and outputting a decoded word if the syndromes of a corrected word of the second decoding are all zeros and 2) terminate without an output if the syndromes are not all zeros for the corrected word of the second decoding.

13. The method according to claim 11, wherein the outer decoding is Reed-Solomon decoding.

14. The method according to claim 11, wherein the inner decoding is concatenated convolutional decoding.

15. The method according to claim 11, wherein the inner decoding is Soft Output Viterbi Algorithm decoding.

16. The method according to claim 11, wherein the decoding is performed on packets of data.

17. The method according to claim 11, wherein the method is performed in software in a communication device.

18. A communication device including a decoder performing the method of claim 11.