Process for transmitting information bits with error correction coding and decoder for the implementation of this process

• US 6,122,763 A
• Filed: 08/28/1997
• Issued: 09/19/2000
• Est. Priority Date: 08/28/1996
• Status: Expired due to Term

• Current Assignee: Orange S.A.
• Original Assignee: Orange S.A.
• Inventors: Pyndiah, Ramesh, Adde, Patrick
• Primary Examiner(s): Grant, William
• Assistant Examiner(s): Marc, McDieunel, Marc, McDieunel
• Application Number:
  US08/919,969
• Time in Patent Office: 1,118 Days
• Field of Search: 395/86, 371/42, 371/37.07, 371/40.11, 371/37.4, 371/40.3, 371/39.1, 371/43.5, 371/40.12, 375/340
• US Class Current: 714/755
• CPC Class Codes: H03M 13/251 with block coding
• CPC Class Codes: H03M 13/2909 Product codes
• 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: H03M 13/6362 by puncturing
• CPC Class Codes: H03M 13/6502 Reduction of hardware complexity or efficient processing

Abstract

The bits transmitted are coded according to the product of at least two systematic block codes. Iterative decoding is applied in order to determine, at each code word search step, a data matrix ({R}) and a decision matrix ({D}) used for the following step. The new decision matrix is determined at each step by decoding the lines or columns of the input matrix, and the new data matrix is determined taking into account the correction terms which increase the reliability of the decoding on each iteration. The coding and decoding circuits (17) are rendered programmable by a shortening technique allowing selection of the number k-X of non-redundant information bits per block to be coded. Known values are assigned to the other bits, the positions of which are uniformly distributed according to each dimension of the matrices.

Claims

1. Process for transmitting information bits, wherein a transmitter executes the following steps:

forming a first binary matrix from the information bits to be transmitted;

converting the first binary matrix into a second binary matrix by applying a systematic block code corresponding to a product of elementary systematic block codes; and

transmitting bits extracted from the second binary matrix towards a channel, and a receiver executes the following steps;

forming an input matrix from a signal received according to said channel, the input matrix having the same size as the second binary matrix, and being comprised of digital samples having signs which represent respective initial estimations of the bits in the second binary matrix and absolute values which respectively measure confidences associated with said initial estimations; and

iteratively decoding the input matrix, wherein the iterative decoding of the input matrix includes a number m of decoding cycles, each decoding cycle successively comprising 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 having binary components are received which, before the first search step of the iterative decoding are respectively constituted by the input matrix and by a matrix having binary components which respectively correspond to the signs of the input matrix samples, and a new decision matrix and a new data matrix are produced for the following search step, whereby the new decision matrix has binary components which represent new respective estimations of the bits of the second binary matrix and the new data matrix has samples having absolute values which respectively measure confidences associated with said new estimations, wherein decoded information bits are extracted from the decision matrix produced during the last code word search step, 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 soft decision elementary decodings to respectively process at least certain data vector/decision vector pairs, wherein the first binary matrix comprises, in addition to the information bits, a set of bits having values a priori known to the receiver, the bits of said set being distributed in a substantially uniform manner according to each dimension of the first binary matrix, whereby, after systematic coding, the bits of said set are located in determined positions of said second binary matrix, wherein the bits of said set are not transmitted towards the channel, and wherein the receiver places in the input matrix, in positions corresponding to said determined positions of the second binary matrix, samples having signs which correspond respectively to the a priori known values of the bits of said set and absolute values which are representative of a maximum confidence.

2. Process according to claim 1, wherein the soft decision elementary decoding for the processing of a data vector/decision vector pair comprises the following steps:

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

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

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

selecting, from the q'"'"' code words obtained, that having the shortest euclidean distance with the data vector;

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

##EQU9## 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;

obtaining the new decision vector taken as equal to said selected code word; and

calculating the new data vector by adding the correction vector multiplied by a first confidence coefficient to the corresponding input vector extracted from the input matrix.

3. Process according to claim 2, wherein, in the step of calculating a correction vector, the determination of an optional concurrent word with respect to the j-th component of the selected code word includes a comparison between the j-th component of the selected code word and the j-th component of a candidate code word which, among the q'"'"' code words obtained except for the selected code word, has the shortest euclidean distance with the data vector, said candidate code word being taken as a concurrent word when its j-th component is different from the j-th component of the selected code word, and no concurrent word being determined if not.

4. Process according to claim 2, wherein the calculation of each component W_j of the correction vector in the absence of determination of a concurrent word with respect to said component W_j is carried out according to the formula:

##EQU10## where β

_i designates a second confidence coefficient.

5. Process according to claim 2, wherein the calculation of each component W_j of the correction vector in the absence of determination of a concurrent word with respect to said component W_j is carried out according to the formula:

##EQU11## where β

_i designates a confidence coefficient.

6. Redundancy coder, comprising:

means to form a first binary matrix from information bits to be transmitted;

elementary coding means controlled to convert the first binary matrix into a second binary matrix by application of a systematic block code corresponding to a product of elementary systematic block codes;

means to transmit bits extracted from the second binary matrix towards a channel; and

programming means to determine, from a number X supplied to program the number of information bits to be included in each first matrix, X positions uniformly distributed according to each dimension of the first matrix, wherein the means of forming the first matrix are designed to place bits of known values in said X positions, whereby said bits of known values are located after systematic coding in determined positions of the second binary matrix, and wherein said means to transmit do not include said bits of known values located at determined positions after systematic coding in the bits transmitted towards the channel.

7. Error correction decoder, comprising:

means for forming an input matrix from a signal received according to a transmission channel, the input matrix being composed of digital samples the signs of which represent respective initial estimations of bits of a binary matrix formed by a redundancy coder applying a systematic block code corresponding to a product of elementary systematic block codes and the absolute values of which respectively measure confidences associated with said initial estimations; and

iterative decoding means controlled to decode the input matrix according to successive decoding cycles, each decoding cycle successively comprising steps for searching code words o each elementary block code used in the product code, wherein, at each code word search step, the decoding means receive a data matrix and a decision matrix having binary components which, before the first search step of the iterative decoding, are respectively constituted by the input matrix and a matrix having binary components which correspond to the signs of samples of the input matrix, and produce a new decision matrix and a new data matrix for the following search step, whereby the new decision matrix has binary components which represent new respective estimations of the bits of the second binary matrix and the new data matrix has samples having absolute values which respectively measure confidences associated with said new estimations, wherein decoded information bits are extracted from the decision matrix produced during the last step of the code word search, 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 elementary soft decision decodings respectively process at least certain data vector/decision vector pairs, the error correction decoder further comprising programming means to determine, from a number X supplied to program the number of decoded information bits to be extracted from the decision matrix, X positions uniformly distributed according to each dimension of a non-redundant sub-matrix of said binary matrix, and wherein the means for forming the input matrix are designed to place, in positions corresponding to said X positions, digital samples of determined signs having absolute values representative of a maximum confidence.