Rate Matching And Channel Interleaving For A Communications System

Abstract

A method, an apparatus, and a computer program product for matching a rate of data bits to a desired rate by deletion of redundant data bits or repetition of data bits are disclosed. In a non-interleaved matrix of the data bits, a pattern of bits to be deleted or repeated to provide the desired data rate is determined. An address of each bit in the pattern in a manner inverse to the interleaving process is decoded to produce a respective address of the bit in the matrix. The respective bit in the interleaved data bits is deleted or repeated depending 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.

1 - 17 . (canceled) 
     
     
         18 . A computer-implemented method for matching a rate of data bits, comprising
 receiving a data stream containing systematic coded data bits, first parity coded data bits, and second parity coded data bits;   interleaving each of the systematic coded data bits, the first parity coded data bits, and the second coded data bits separately from each other, without determining a pattern of data bits to be deleted prior to interleaving;   providing, based on the interleaving, the interleaved systematic coded data bits, the interleaved first parity coded data bits, and the interleaved coded data bits for matching of the rate of data bits; and   performing matching of the rate of data bits by
 deleting at least one interleaved parity data bit, wherein the at least one interleaved parity data bit includes an interleaved first parity coded data bit and an interleaved second parity coded data bit, without deleting systematic coded data bits; and 
 repeating at least on interleaved data bit, wherein the at least one interleaved data bit includes the at least one interleaved systematic data bit and the at least one interleaved parity data bit; 
   wherein at least one of the receiving, the interleaving, the providing, and the performing is performed by at least one processor.   
     
     
         19 . The method according to  claim 18 , wherein the repeating further comprises
 repeating at least one interleaved parity data bit with a greater repetition factor than any repetition factor of at least one interleaved systematic data bit.   
     
     
         20 . The method according to  claim 18 , further comprising
 shuffling a plurality of data bits by inserting data bits of a first data stream into a second data stream to result in a shuffled data stream, wherein the first data stream and the second data stream include at least one of a stream of the systematic coded data bits, a stream of the first parity coded data bits, and a stream of the second coded data bits.   
     
     
         21 . The method according to  claim 20 , further comprising
 adding data bits of a third data stream into the shuffled data stream to produce a new shuffled data stream, wherein the third data stream includes at least one of a stream of the systematic coded data bits, a stream of the first parity coded data bits, and a stream of the second coded data bits; and,   recursively performing the adding function for each data stream in excess of three data streams.   
     
     
         22 . The method according to  claim 18 , wherein the receiving further comprises
 receiving the data stream, wherein the data bits are produced by a parallel concatenated convolutional coder.   
     
     
         23 . The method according to  claim 18 , wherein interleaving further comprises
 generating an address for each interleaved data bit, wherein the interleaving of the generated addresses for the interleaved data bits is performed before the deleting and the repeating;   wherein the deleting or the repeating of the interleaved data bits is performed based on the generated address for each interleaved data bit.   
     
     
         24 . The method according to  claim 18 , wherein the interleaving further 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:
     I   r ( k )=[α r   k+f   c ( l )] mod  N   r ,  Row Permutation
 
     I   c ( l )=[α c   l+f   r ( k )] mod  N   c   Column Permutation
 
   
       wherein
 I r (k) represents a data bit with a row index k, 
 k is an integer from 1 to N r , α r  is an integer, 
 f c (l) is a non-zero function of a column index l, 
 l is an integer from 1 to N x , 
 I c (l) represents a data bit with the column index l, 
 α c  is an integer, 
 f r (k) is zero or a function of the row index k, and 
 mod N r  and mod N c  represent modulo-N r  and modulo-N c  arithmetic respectively, interleaved data bits being derived from the matrix column by column. 
 
     
     
         25 . The method according to  claim 24 , wherein f c (l)=ml+[N r +1] mod 2, where m is an integer. 
     
     
         26 . The method according to  claim 25 , wherein m is approximately equal to N r /N c . 
     
     
         27 . The method according to  claim 24 , wherein f r (k)=2k+[N c +1] mod 2. 
     
     
         28 . The method according to  claim 24 , wherein α r  is the largest prime number less than N r /log 2 (log 2 (N r )). 
     
     
         29 . A system comprising:
 at least one programmable processor; and   a machine-readable medium storing instructions that, when executed by the at least one programmable processor, cause the at least one programmable processor to perform operations comprising:
 receiving a data stream containing systematic coded data bits, first parity coded data bits, and second parity coded data bits; 
 interleaving each of the systematic coded data bits, the first parity coded data bits, and the second coded data bits separately from each other, without determining a pattern of data bits to be deleted prior to interleaving; 
 providing, based on the interleaving, the interleaved systematic coded data bits, the interleaved first parity coded data bits, and the interleaved coded data bits for matching of the rate of data bits; and 
 performing matching of the rate of data bits by
 deleting at least one interleaved parity data bit, wherein the at least one interleaved parity data bit includes an interleaved first parity coded data bit and an interleaved second parity coded data bit, without deleting systematic coded data bits; and 
 repeating at least on interleaved data bit, wherein the at least one interleaved data bit includes the at least one interleaved systematic data bit and the at least one interleaved parity data bit. 
 
   
     
     
         30 . The system according to  claim 29 , wherein the repeating further comprises
 repeating at least one interleaved parity data bit with a greater repetition factor than any repetition factor of at least one interleaved systematic data bit.   
     
     
         31 . The system according to  claim 29 , wherein the operations further comprise
 shuffling a plurality of data bits by inserting data bits of a first data stream into a second data stream to result in a shuffled data stream, wherein the first data stream and the second data stream include at least one of a stream of the systematic coded data bits, a stream of the first parity coded data bits, and a stream of the second coded data bits.   
     
     
         32 . The system according to  claim 31 , further comprising
 adding data bits of a third data stream into the shuffled data stream to produce a new shuffled data stream, wherein the third data stream includes at least one of a stream of the systematic coded data bits, a stream of the first parity coded data bits, and a stream of the second coded data bits; and,   recursively performing the adding function for each data stream in excess of three data streams.   
     
     
         33 . The system according to  claim 29 , wherein the receiving further comprises
 receiving the data stream, wherein the data bits are produced by a parallel concatenated convolutional coder.   
     
     
         34 . The system according to  claim 29 , wherein interleaving further comprises
 generating an address for each interleaved data bit, wherein the interleaving of the generated addresses for the interleaved data bits is performed before the deleting and the repeating;   wherein the deleting or the repeating of the interleaved data bits is performed based on the generated address for each interleaved data bit.   
     
     
         35 . The system according to  claim 29 , wherein the interleaving further 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:
     I   r ( k )=[α r   k+f   c ( l )] mod  N   r ,  Row Permutation
 
     I   c ( l )=[α c   l+f   r ( k )] mod  N   c   Column Permutation
 
   
       wherein
 I r (k) represents a data bit with a row index k, 
 k is an integer from 1 to N r , α r  is an integer, 
 f c (l) is a non-zero function of a column index l, 
 l is an integer from 1 to N c , 
 I c (l) represents a data bit with the column index l, 
 α c  is an integer, 
 f r (k) is zero or a function of the row index k, and 
 mod N r  and mod N c  represent modulo-N r  and modulo-N c  arithmetic respectively, interleaved data bits being derived from the matrix column by column. 
 
     
     
         36 . The system according to  claim 35 , wherein f c (l)=ml+[N r +1] mod 2, where m is an integer. 
     
     
         37 . The system according to  claim 36 , wherein m is approximately equal to N r /N c . 
     
     
         38 . The system according to  claim 35 , wherein f r (k)=2k+[N c +1] mod 2. 
     
     
         39 . The system according to  claim 35 , wherein α r  is the largest prime number less than N r /log 2 (log 2 (N r )). 
     
     
         40 . A computer program product comprising a machine-readable medium storing instructions that, when executed by at least one programmable processor, cause the at least one programmable processor to perform operations comprising:
 receiving a data stream containing systematic coded data bits, first parity coded data bits, and second parity coded data bits;   interleaving each of the systematic coded data bits, the first parity coded data bits, and the second coded data bits separately from each other, without determining a pattern of data bits to be deleted prior to interleaving;   providing, based on the interleaving, the interleaved systematic coded data bits, the interleaved first parity coded data bits, and the interleaved coded data bits for matching of the rate of data bits; and   performing matching of the rate of data bits by
 deleting at least one interleaved parity data bit, wherein the at least one interleaved parity data bit includes an interleaved first parity coded data bit and an interleaved second parity coded data bit, without deleting systematic coded data bits; and 
 repeating at least on interleaved data bit, wherein the at least one interleaved data bit includes the at least one interleaved systematic data bit and the at least one interleaved parity data bit. 
   
     
     
         41 . The computer program product according to  claim 40 , wherein the repeating further comprises
 repeating at least one interleaved parity data bit with a greater repetition factor than any repetition factor of at least one interleaved systematic data bit.   
     
     
         42 . The computer program product according to  claim 40 , wherein the operations further comprise
 shuffling a plurality of data bits by inserting data bits of a first data stream into a second data stream to result in a shuffled data stream, wherein the first data stream and the second data stream include at least one of a stream of the systematic coded data bits, a stream of the first parity coded data bits, and a stream of the second coded data bits.   
     
     
         43 . The computer program product according to  claim 42 , wherein the operations further comprise
 adding data bits of a third data stream into the shuffled data stream to produce a new shuffled data stream, wherein the third data stream includes at least one of a stream of the systematic coded data bits, a stream of the first parity coded data bits, and a stream of the second coded data bits; and,   recursively performing the adding function for each data stream in excess of three data streams.   
     
     
         44 . The computer program product according to  claim 40 , wherein the receiving further comprises
 receiving the data stream, wherein the data bits are produced by a parallel concatenated convolutional coder.   
     
     
         45 . The computer program product according to  claim 40 , wherein interleaving further comprises
 generating an address for each interleaved data bit, wherein the interleaving of the generated addresses for the interleaved data bits is performed before the deleting and the repeating;   wherein the deleting or the repeating of the interleaved data bits is performed based on the generated address for each interleaved data bit.   
     
     
         46 . The computer program product according to  claim 40 , wherein the interleaving further 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:
     I   r ( k )=[α r   k+f   c ( l )] mod  N   r ,  Row Permutation
 
     I   c ( l )=[α c   l+f   r ( k )] mod  N   c   Column Permutation
 
   
       wherein
 I r (k) represents a data bit with a row index k, 
 k is an integer from 1 to N r , α r  is an integer, 
 f c (l) is a non-zero function of a column index l, 
 l is an integer from 1 to N c , 
 I c (l) represents a data bit with the column index l, 
 α c  is an integer, 
 f r (k) is zero or a function of the row index k, and 
 mod N r  and mod N c  represent modulo-N r  and modulo-N c  arithmetic respectively, interleaved data bits being derived from the matrix column by column. 
 
     
     
         47 . The computer program product according to  claim 46 , wherein f c (l)=ml+[N r +1] mod 2, where m is an integer. 
     
     
         48 . The computer program product according to  claim 47 , wherein m is approximately equal to N r /N c . 
     
     
         49 . The computer program product according to  claim 46 , wherein f r (k)=2k+[N c +1] mod 2. 
     
     
         50 . The computer program product according to  claim 46 , wherein α r  is the largest prime number less than N r /log 2 (log 2 (N r )).