Data block convolutional coding device and method, and corresponding decoding method and device

• US 6,119,264 A
• Filed: 04/19/1998
• Issued: 09/12/2000
• Est. Priority Date: 04/03/1996
• Status: Expired due to Term

• Current Assignee: Orange S.A., Telediffusion De France SA
• Original Assignee: France Telecom Telediffusion de France SA
• Inventors: Berrou, Claude, Jezequel, Michel
• Primary Examiner(s): Decady, Albert
• Assistant Examiner(s): Chase, Shelly A
• Application Number:
  US09/155,819
• Time in Patent Office: 877 Days
• Field of Search: 714/786, 714/790, 714/794, 714/795
• US Class Current: 714/786
• CPC Class Codes: E05B 15/0205 Striking-plates, keepers, staples means for reducing friction E05B17/007; electric strikers E05B47/0046; staples for padlocks E05B67/383; strikers for espagnolettes E05C9/1808
• CPC Class Codes: H03M 13/23 using convolutional codes, e.g. unit memory codes
• CPC Class Codes: H03M 13/2707 Simple row-column interleaver, i.e. pure block interleaving
• CPC Class Codes: H03M 13/2771 Internal interleaver for turbo codes H03M13/2714 and H03M13/2725 take precedence
• CPC Class Codes: H03M 13/2957 Turbo codes and decoding
• CPC Class Codes: H03M 13/296 Particular turbo code structure
• CPC Class Codes: H03M 13/2984 using less component decoders than component codes, e.g. multiplexed decoders and scheduling thereof
• CPC Class Codes: H03M 13/299 Turbo codes with short blocks
• CPC Class Codes: H03M 13/2993 Implementing the return to a predetermined state, i.e. trellis termination
• CPC Class Codes: H03M 13/2996 Tail biting
• CPC Class Codes: H03M 13/39 Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes
• CPC Class Codes: H04L 1/0043 Realisations of complexity reduction techniques, e.g. use of look-up tables
• 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/0059 Convolutional codes
• CPC Class Codes: H04L 1/0066 Parallel concatenated codes
• CPC Class Codes: H04L 1/0068 by puncturing

Abstract

Disclosed are a method and a device for the convolutive encoding of blocks each formed by a predetermined number N of source data elements, wherein each of said source data elements is introduced twice into one and the same convolutive encoder implementing a generating polynomial with a period L in an order such that the two instances of introduction of one and same source data element d_i are separated by the introduction of (p_i.L)-1 other source data elements, p_i being a non-zero integer. Also disclosed are a corresponding decoding method and device that can be applied, in particular, to the transmission of short messages, for example in radiotelephony, for satellite communications or gain computer telecommunications (Internet for example). FIG. 2.

Claims

1. A method for the convolutive encoding of blocks each formed by a predetermined number N of source data elements,

wherein each of said source data elements is introduced twice into one and the same convolutive encoder implementing a generating polynomial with a period L in an order such that the two instances of introduction of one and same source data element d_i are separated by the introduction of (p_i.L)-1 other source data elements, p_i being a non-zero integer.

2. A method according to claim 1, wherein said source data elements are introduced into said decoder for a first time (these are called original data elements) in their natural order and then a second time (they are then called duplicated data elements) in an order such that the two instances of introduction of one and the same source data element d_i are separated by the introduction of (p_i.L)-1 other source data elements, p_i being a non-zero integer.

3. A method of encoding according to claim 2, wherein the order of introduction of said duplicated data elements is obtained by:

recording the source data elements row by row in a memory with a size N=n₁ *n_c, n₁ being the number of rows which is a multiple of L and n_c being the number of columns which is a prime number with L; and

reading said duplicated data elements column by column in travelling, on a given column at the instant k₂, through the successive rows until there is found a data element that has been used for a first time (original data element) at the instant k₁ such that k₁ -k₂ is a multiple of L.

4. A method of encoding according to claim 1, wherein this encoding is a systematic encoding, said source data elements being systematically transmitted in conjunction with the data elements delivered by said encoder.

5. A method according to claim 1, implementing a punching of the data delivered by said encoder.

6. A method according to claim 1, wherein the number N of source data elements forming a block is a multiple of the period L of the generating polynomial of said encoder.

7. A method according to claim 1 wherein, since the number N of source data elements forming a block is not a multiple of the period L of the generating polynomial of said encoder, each of said blocks is supplemented by a number N'"'"'-N of fixed values, N'"'"' being the multiple of L that is immediately greater than N.

8. A device for the convolutive encoding of blocks each formed by a predetermined number N of source data elements,

comprising means for the introducing of each of said source data elements twice into one and the same convolutive encoder implementing a generating polynomial with a period L in an order such that the two instances of introduction of one and same source data element d_i are separated by the introduction of (p_i.L)-1 other source data elements, p_i being a non-zero integer.

9. A method for the decoding of an encoded block formed by encoded data, corresponding to a source block formed by a predetermined number N of source data elements,

wherein said block has undergone an encoding such that each of said source data elements is introduced twice into one and the same convolutive encoder implementing a generating polynomial with a period L in an order such that the two instances of introduction of one and same source data element d_i are separated by the introduction of (p_i.L)-1 other source data elements, p_i being a non-zero integer,

and wherein the method comprises a maximum likelihood decoding step taking account, firstly, of the received encoded data elements and, secondly, of the fact that the initial state and the final state of the encoder are known.

10. A decoding method according to claim 9 wherein, said encoding being a systematic encoding, the decoding method implements an iterative procedure comprising:

the duplication of the original symbols received and the association, with each of them, of one or other of the redundant data elements received so as to form 2.N pairs of information elements to be decoded;

a first iteration comprising the following steps;

the initialization of the decoding so as to take account of the initial state of the encoder;

the determining, for each pair of information elements, of an estimation s_k of this pair and of an extrinsic information element z_k representing the confidence associated with said estimation, as a function of the encoded data elements and the redundancy data elements received, and in taking account of the fact that the initial state and the final state of the encoder are known;

at least one intermediate iteration, repeating the determination step, in replacing the source data elements received by a weighted combination of the source data elements received and of the dual extrinsic information;

a last iteration delivering a definitive estimation of the data elements received corresponding to the summing of the estimation obtained from one of the redundancy symbols with the extrinsic information obtained from the other redundancy symbol, for each source symbol.

11. A method according to claim 10, wherein a logarithmic law is applied to the absolute value on the estimations produced during said steps of determination.

12. A method according to claim 10, wherein said iterations are implemented by:

reusing a single decoder several times, at a rate greater than that of the transmitted data element;

cascading several decoding modules, each corresponding to an iteration.

13. A decoder of an encoded block formed by encoded data elements corresponding to a source block formed by a predetermined number N of source data elements,

wherein said source block has undergone an encoding such that each of said source data elements is introduced twice into one and the same convolutive encoder implementing a generating polynomial with a period L in an order such that the two instances of introduction of one and same source data element d_i are separated by the introduction of (p_i.L)-1 other source data elements, p_i being a non-zero integer,

and wherein said decoder comprises maximum likelihood decoding means taking account, firstly, of the encoded data elements received and, secondly, of the fact that the initial state and the final state of the encoder are known.