Method for detecting information bits processed by concatenated block codes

• US 5,563,897 A
• Filed: 11/18/1994
• Issued: 10/08/1996
• Est. Priority Date: 11/19/1993
• Status: Expired due to Term

• Current Assignee: Orange S.A.
• Original Assignee: Orange S.A.
• Inventors: Pyndiah, Ramesh, Glavieux, Alain, Berrou, Claude
• Primary Examiner(s): Envall, Jr., Roy N.
• Assistant Examiner(s): KUNDUPOGLU, YONCHA LYNN
• Application Number:
  US08/345,370
• Time in Patent Office: 690 Days
• Field of Search: 371/37.4
• US Class Current: 714/755
• CPC Class Codes: H03M 13/2963 Turbo-block codes, i.e. turbo codes based on block codes, e.g. turbo decoding of product codes
• CPC Class Codes: H03M 13/453 wherein the candidate code words are obtained by an algebraic decoder, e.g. Chase decoding
• CPC Class Codes: H04L 1/005 Iterative decoding, including iteration between signal detection and decoding operation
• CPC Class Codes: H04L 1/0052 Realisations of complexity reduction techniques, e.g. pipelining or use of look-up tables
• CPC Class Codes: H04L 1/0057 Block codes H04L1/0061, H04L1/0064 take precedence
• CPC Class Codes: H04L 1/0064 Concatenated codes
• CPC Class Codes: H04L 1/0071 Use of interleaving interleaving per se H03M13/27

Abstract

The transmitted bits are coded according to the product of at least two systematic block codes. An iterative decoding is applied in order to determine, at each code word search step, a data matrix and a decision matrix which are used for the following step. The new decision matrix is determined at each step by decoding the rows or the columns of the input matrix, and the new data matrix is determined by taking account of correction terms which increase the reliability of the decoding at each iteration. The method is especially suited for use with high-efficiency block codes.

Claims

1. Method for detecting information bits in a coded digital signal, within a receiver, the coding of the said digital signal having been performed within a transmitter by applying, to information bits to be transmitted, a block code corresponding to the product of at least two elementary systematic block codes, the method comprising an iterative decoding phase including a number m of decoding cycles, each decoding cycle successively including code word search steps for each elementary block code used in the product code,

wherein, at each code word search step, a data matrix and a decision matrix with binary components are received which, before the first search step of the iterative decoding phase consist respectively of an input matrix consisting of samples of the received signal and of a matrix, the components of which are those of the input matrix put into binary form, and a new decision matrix and a new data matrix are produced for the following search step,

wherein decoded information bits are extracted from the decision matrix produced during the last code word search step,

and wherein each code word search step includes a division of the data matrix received into data vectors each corresponding to a code word of the elementary code and a corresponding division of the decision matrix received into decision vectors, and the following substeps for respectively processing at least some of the data vector/decision vector pairs:

determining a number p of indices for which the components of the data vector are the least reliable;

constructing a number q of binary words to be decoded from the said p indices and from the decision vector;

obtaining q'"'"' code words on the basis of algebraic decodings of the decision vector of the q binary words to be decoded;

selecting, among the q'"'"' code words obtained, the one having the smallest euclidean distance from the data vector;

calculating a correction vector, each component W_j of the correction vector being calculated respectively by determining a possible concurrent word having a j-th component different from that of the selected code word, and by applying the formula;

##EQU14## when a concurrent word has been determined, M^d and M^c respectively designating the euclidean distances, with respect to the data vector, of the selected code word and of the concurrent word, and C_j^d and R'"'"'_j respectively designating the j-th components of the selected code word and of the date vector;

updating said decision vector by obtaining a new decision vector taken to be equal to the said selected code word; and

updating said data vector, a new data vector being calculated by adding the correction vector multiplied by a first confidence coefficient to a corresponding input vector extracted from the input matrix.

2. Method according to claim 1, wherein, in the substep of calculating a correction vector, the determination of a possible concurrent word relative to the j-th component of the selected code word comprises the determination, among the q'"'"' code words obtained, of those having their j-th component different from that of the selected code word and the selection as concurrent word of that one of the code words thus determined having the smallest euclidean distance with the data vector, no concurrent word being determined when the q'"'"' code words obtained all have their j-th component equal to that of the selected code word.

3. Method according to claim 1, wherein, in the substep of calculating a correction vector, the determination of a possible concurrent word relative to the j-th component of the selected code word comprises a comparison between the j-th component of the decision vector and that of the selected code word, the decision vector being taken as concurrent word when its j-th component is different from that of the selected code word, and no concurrent word being determined in the opposite case.

4. Method according to claim 1, wherein the obtaining of the q'"'"' code words comprises, for each code word resulting from the algebraic decoding of the decision vector or of one of the q binary words to be decoded, the identification of the components of the associated input vector having a sign opposite to that of the corresponding component of the said code word, the said code word being adopted among the q'"'"' code words only if the absolute values of the said components of opposite sign of the input vector are all less than a preestablished threshold.

5. Method according to claim 4, wherein the threshold increases in step with the code word search steps.

6. Method according to claim 1, wherein the first confidence coefficient increases in step with the code word search steps.

7. Method according to claim 1, wherein the calculation of each component W_j of the correction vector in the absence of determination of a concurrent word relative to said component is performed according to the formula:

space="preserve" listing-type="equation">W.sub.j =β

.sub.i C.sub.j.sup.d

where β

_i designates a second confidence coefficient.

8. Method according to claim 1, wherein the calculation of each component W_j of the correction vector in the absence of determination of a concurrent word relative to said component is performed according to the formula:

space="preserve" listing-type="equation">W.sub.j =(β

.sub.i -C.sub.j.sup.d R'"'"'.sub.j)C.sub.j.sup.d

where β

_i designates a second confidence coefficient.

9. Method according to claim 7, wherein the second confidence coefficient increases in step with the code word search steps.

10. Method according to claim 1, wherein each of the q binary words to be decoded is constructed in such a way that all components thereof other than those corresponding to the p indices for which the components of the data vector are least reliable are equal respectively to the corresponding components of the decision vector.

11. Method according to claim 10, wherein each of the q binary words to be decoded is constructed in such a way as to have one or two components different from the corresponding components of the decision vector.

12. Method according to claim 11, wherein q=p(p+1)/2.

13. Method according to claim 1, wherein the elementary block codes used in the product code are identical.

14. Method for transmitting information bits, comprising:

a coding phase in which a block code, corresponding to the product of at least two elementary systematic block codes, is applied to the information bits to be transmitted;

a phase of modulation and of transmission of a signal obtained from the coded information bits;

a phase of reception of the transmitted signal after propagation and of demodulation; and

an iterative decoding phase including a number m of decoding cycles, each decoding cycle successively including code word search steps for each elementary block code used in the product code,

wherein, at each code word search step, a data matrix and a decision matrix with binary components are received which, before the first search step of the iterative decoding phase consist respectively of an input matrix consisting of samples of the received signal and of a matrix, the components of which are those of the input matrix put into binary form, and a new decision matrix and new data matrix are produced for the following search step,

wherein decoded information bits are extracted from the decision matrix produced during the last code work search step,

and wherein each code word search step includes a division of the data matrix received into data vectors each corresponding to a code word of the elementary code and a corresponding division of the decision matrix received into decision vectors, and the following substeps for respectively processing at least some of the data vector/decision vector pairs;

determining a number p of indices for which the components of the data vector are the least reliable;

constructing a number q of binary words to be decoded from the said p indices and from the decision vector;

obtaining q'"'"' code words on the basis of algebraic decodings of the decision vector and of the q binary words to be decoded;

selecting, among the q'"'"' code words obtained, the one having the smallest euclidean distance from the data vector;

calculating a correction vector, each component W_j of the correction vector being calculated respectively by determining a possible concurrent word having a j-th component different from that of the selected code word, and by applying the formula;

##EQU15## when a concurrent word has been determined, M^d and M^c respectively designating the euclidean distances, with respect to the data vector, of the selected code word and of the concurrent word, and C_j^d and R'"'"'_j respectively designating the j-th components of the selected code word and of the data vector;

updating said decision vector by obtaining a new decision vector taken to be equal to the said selected code word; and

updating said decision vector, a new data vector being calculated by adding the correction vector multiplied by a first confidence coefficient to a corresponding input vector extracted from the input matrix.

15. Method according to claim 14, wherein, in the substep of calculating a correction vector, the determination of a possible concurrent word relative to the j-th component of the selected code word comprises the determination, among the q'"'"' code words obtained, of those having their j-th component different from that of the selected code word and the selection as concurrent word of that one of the code words thus determined having the smallest euclidean distance with the data vector, no concurrent word being determined when the q'"'"' code words obtained all have their j-th component equal to that of the selected code word.

16. Method according to claim 14, wherein that, in the substep of calculating a correction vector, the determination of a possible concurrent word relative to the j-th component of the selected code word comprises a comparison between the j-th component of the decision vector and that of the selected code word, the decision vector being taken as concurrent word when its j-th component is different from that of the selected code word, and no concurrent word being determined in the opposite case.

17. Method according to claim 14, wherein the obtaining of the q'"'"' code words comprises, for each code word resulting from the algebraic decoding of the decision vector or of one of the q binary words to be decoded, the identification of the components of the associated input vector having a sign opposite to that of the corresponding component of the said code word, the said code word being adopted among the q'"'"' code words only if the absolute values of the said components of opposite sign of the input vector are all less than a preestablished threshold.

18. Method according to claim 17, wherein the threshold increases in step with the code word search steps.

19. Method according to claim 14, wherein the first confidence coefficient increases in step with the code word search steps.

20. Method according to claim 14, wherein the calculation of each component W_j of the correction vector in the absence of determination of a concurrent word relative to said component is performed according to the formula:

space="preserve" listing-type="equation">W.sub.j =β

.sub.i C.sub.j.sup.d

where β

_i designates a second confidence coefficient.

21. Method according to claim 20, wherein the second confidence coefficient increases in step with the code word search steps.

22. Method according to claim 14, wherein each of the q binary words to be decoded is constructed in such a way that all components thereof other than those corresponding to the p indices for which the components of the data vector are least reliable are equal respectively to the corresponding components of the decision vector.

23. Method for retrieving information bits stored in coded from in a memory, the coding of the said bits having been performed by applying a block code corresponding to the product of at least two elementary systematic block bodes, the said method comprising a phase of reading in the memory and a phase of iterative decoding, including a number m of decoding cycles, each decoding cycle successively including code word search steps for each elementary block code used in the product code,

wherein, at each code word search step, a data matrix and a decision matrix with binary components are received which, before the first search step of the iterative decoding phase consist respectively of an input matrix consisting of samples of the received signal and of a matrix the components of which are those of the input matrix put into binary form, and a new decision matrix and a new data matrix are produced for the following search step,

wherein decoded information bits are extracted from the decision matrix produced during the last code word search step,

and wherein each code word search step includes a division of the data matrix received into data vectors each corresponding to a code word of the elementary code and a corresponding division of the decision matrix received into decision vectors, and the following substeps for respectively processing at least some of the data vector/decision vector pair:

determining a number p of indices for which the components of the data vector are the least reliable;

constructing a number q of binary words to be decoded from the said p indices and from the decision vector;

obtaining q'"'"' code words on the basis of algebraic decodings of the decision vector and of the q binary words to be decoded;

selecting, among the q'"'"' code words obtained, the one having the smallest euclidean distance from the data vector;

calculating a correction vector, each component W_j of the correction vector being calculated respectively by determining a possible concurrent word having a j-th component different from that of the selected code word, and by applying the formula;

##EQU16## when a concurrent word has been determined, M^d and M^c respectively designating the euclidean distances with respect to the data vector, of the selected code word and of the concurrent word, and C_j^d and R'"'"'_j respectively designating the j-th components of the selected code word and of the data vector;

updating said decision vector by obtaining a new decision vector taken to be equal to the said selected code word; and

updating said data vector, a new data vector being calculated by adding the correction vector multiplied by a first confidence coefficient to a corresponding input vector extracted from the input matrix.

24. Method according to claim 23, wherein, in the substep of calculating a correction vector, the determination of a possible concurrent word relative to the j-th component of the selected code word comprises the determination, among the q'"'"' code words obtained, of those having their j-th component different from that of the selected code word and the selection as concurrent word of that one of the code words thus determined having the smallest euclidean distance with the data vector, no concurrent word being determined when the q'"'"' code words obtained all have their j-th component equal to that of the selected code word.

25. Method according to claim 23, wherein, in the substep of calculating a correction vector, the determination of a possible concurrent word relative to the j-th component of the selected code word comprises a comparison between the j-th component of the decision vector and that of the selected code word, the decision vector being taken as concurrent word when its j-th component is different from that of the selected code word, and no concurrent word being determined in the opposite case.

26. Method according to claim 23, wherein the obtaining of the q'"'"' code words comprises, for each code word resulting from the algebraic decoding of the decision vector or of one of the q binary words to be decoded, the identification of the components of the associated input vector having a sign opposite to that of the corresponding component of the said code word, the said code word being adopted among the q'"'"' code words only if the absolute values of the said components of opposite sign of the input vector are all less than a preestablished threshold.

27. Method according to claim 26, wherein the threshold increases in step with the code word search steps.

28. Method according to claim 23, wherein the first confidence coefficient increases in step with the code word search steps.

29. Method according to claim 23, wherein the calculation of each component W_j of the correction vector in the absence of determination of a concurrent word relative to said component is performed according to the formula:

space="preserve" listing-type="equation">W.sub.j =β

.sub.i C.sub.j.sup.d

where β

_i designates a second confidence coefficient.

30. Method according to claim 29, wherein the second confidence coefficient increases in step with the code word search steps.

31. Method according to claim 23, wherein each of the q binary words to be decoded is constructed in such a way that all components thereof other than those corresponding to the p indices for which the components of the data vector are least reliable are equal respectively to the corresponding components of the decision vector.