Rate matching and channel interleaving for a communications system

• US 6,744,744 B1
• Filed: 04/07/2000
• Issued: 06/01/2004
• Est. Priority Date: 04/13/1999
• Status: Expired due to Term

• Current Assignee: Ericsson AB (Telefonaktiebolaget LM Ericsson)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Gosne, Stephane, Tong, Wen, Leretaille, Catherine
• Primary Examiner(s): Vu, Huy D.
• Assistant Examiner(s): RYMAN, DANIEL J
• Application Number:
  US09/544,981
• Time in Patent Office: 1,516 Days
• Field of Search: 370/477, 375/265, 714/786, 714/790, 714/792
• US Class Current: 370/320
• CPC Class Codes: H03M 13/00 Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes error detection or error correction for analogue/digital, digital/analogue or code conversion H03M1/00 – H03M11/00; specially adapted for digital computers G06F11/08; for information storage based on relative movement between record carrier and transducer G11B, e.g. G11B20/18; for static stores G11C
• CPC Class Codes: H03M 13/271 Row-column interleaver with permutations, e.g. block interleaving with inter-row, inter-column, intra-row or intra-column permutations
• CPC Class Codes: H03M 13/2739 Permutation polynomial interleaver, e.g. quadratic permutation polynomial [QPP] interleaver and quadratic congruence interleaver
• CPC Class Codes: H03M 13/275 Interleaver wherein the permutation pattern is obtained using a congruential operation of the type y=ax+b modulo c
• CPC Class Codes: H03M 13/276 Interleaving address generation
• CPC Class Codes: H03M 13/2764 Circuits therefore
• CPC Class Codes: H03M 13/2792 Interleaver wherein interleaving is performed jointly with another technique such as puncturing, multiplexing or routing
• CPC Class Codes: H03M 13/2957 Turbo codes and decoding
• CPC Class Codes: H03M 13/635 Error control coding in combination with rate matching
• CPC Class Codes: H04L 1/0041 Arrangements at the transmitter end
• 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/0068 by puncturing
• CPC Class Codes: H04L 1/0071 Use of interleaving interleaving per se H03M13/27

Abstract

Matching a rate of data bits, in a matrix of data bits interleaved by a predetermined interleaving process, to a desired rate by deletion of redundant data bits or repetition of data bits derived from the matrix. It includes steps of determining in a non-interleaved matrix of the data bits a pattern of bits to be deleted or repeated to provide the desired data rate, decoding an address of each bit in said pattern in a manner inverse to the interleaving process to product a respective address of the bit in the matrix of interleaved data bits, and deleting or repeating the respective bit in the interleaved data bits in dependence upon the respective address. The address decoding is performed in the same manner as a coding of addresses for producing the interleaved data bits from the non-interleaved matrix of the data bits.

Claims

1. A method of matching a rate of data bits, in a matrix of data bits interleaved by a predetermined interleaving process, to a desired rate by deletion of redundant data bits or repetition of data bits derived from the matrix, including the steps of:

determining in a non-interleaved matrix of said data bits a pattern of bits to be deleted or repeated to provide said desired data rate;

interleaving an address of each bit in said pattern to produce a respective address of the bit in the matrix of interleaved data bits; and

deleting or repeating the respective bit in the interleaved data bits in dependence upon the respective address.

2. A method as claimed in claim 1 wherein the address decoding is performed in the same manner as a coding of addresses for producing the interleaved data bits from the non-interleaved matrix of said data bits.

3. A method as claimed in claim 1 wherein the pattern of bits to be deleted or repeated is dependent upon the number of bits to be deleted or repeated and a column index of the matrix.

4. A method as claimed in claim 1 wherein the interleaving process comprises permuting rows and columns of a matrix of N_r rows and N_c columns, in which data bits to be interleaved are represented row by row, in accordance with:

5. A method as claimed in claim 4 wherein

f_c(l)=ml+[N_r+1]mod2, where m is an integer.

6. A method as claimed in claim 5 wherein m is approximately equal to N_r/N_c.

7. A method as claimed in claim 4 wherein

f_r(k)+2k+[Nc+1]mod2.

8. A method as claimed in claim 4 wherein α

_r is the largest prime number less than N_r/log₂(log₂(N_r)).

9. Rate matching apparatus arranged for carrying out a method as claimed in claim 1.

10. A method of interleaving data bits comprising permuting rows and columns of a matrix of N_r rows and N_c columns, in which data bits to be interleaved are represented row by row, in accordance with:

11. A method as claimed in claim 10 wherein m is approximately equal to N_r/N_c.

12. A method as claimed in claim 10 wherein α

_r is the largest prime number less than N_r/log₂(log₂(N_r)).

13. A data interleaver arranged for carrying out the method of claim 10.