# US 6,732,316 B1 · Data interleaver and method of interleaving data

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 6,732,316 B1
- Document ID: US6732316B1
- Status: Granted
- Kind: B1
- Application number: 09/531,470
- Filed: 2000-03-20
- Granted: 2004-05-04
- Earliest claimed: 1999-03-19
- Assignees: Nortel Networks Limited
- Inventors: Wen Tong; Catherine Leretaille
- Web page: https://patentgrep.com/patent/US6732316B1

## CPC

- H04L 1/0068: {by puncturing}
- H03M 13/271: {Row-column interleaver with permutations, e.g. block interleaving with inter-row, inter-column, intra-row or intra-column permutations}
- H03M 13/2764: {Circuits therefore}
- H04L 1/0041: {Arrangements at the transmitter end}
- H04L 1/0071: {Use of interleaving (interleaving per se H03M13/27)}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)

## Abstract

Interleaving of data symbols comprises permuting rows and columns of a matrix of Nr rows and Nc columns, in which data symbols to be interleaved are represented row by row, in accordance with: Row Permutation Ir (k) = [αrk + fc (l)] modNr Column Permutation Ic (l) = [αcl + fr (k)] modNc where Ir(k) represents a data symbol with a row index k, k is an integer from 1 to Nrαr is an integer, fc(l) is a non-zero function of a column index l, l is an integer from 1 to Nc, Ic(l) represents a data symbol with the column index l, αc is an integer, fr(k) is zero or a function of the row index k, and modnr and modnc represent modulo-Nr and modulo-Nc arithmetic respectively, interleaved data symbols being derived from the matrix column by column. A data interleaver comprises a memory for sequentially storing data symbols to be interleaved and a relatively simple circuit for determining read addresses for the interleaved data symbols. The data interleaver is particularly suited for channel interleaving in a 3rd generation CDMA wireless communications system.

## Claims

### Claim 1

A method of interleaving data symbols comprising the steps of:
storing data symbols to be interleaved in a memory having storage locations representing rows and columns of a matrix of Nr rows and Nc columns, the data symbols to be interleaved being represented row by row in said matrix;
reading the stored data symbols from the storage locations of the memory in an interleaved manner as interleaved data symbols by deriving the interleaved data symbols column by column of a permutation of the matrix so that the interleaved data symbols are arranged in accordance with:
Row Permutation Ir (k) = [αrk + fc (l)] modNr Column Permutation Ic (l) = [αcl + fr (k)] modNc
where lr(k) represents a data symbol with a row index k, k is an integer from 1 to Nr, αr is an integer, fc(l) is a non-zero function of a column index I, I is an integer from 1 to Nc, Ic(I) represents a data symbol with the column index I, αc is an integer, fr(k) is zero or a function of the row index k, and modNr and modNc represent modulo-Nr and module Nc arithmetic respectively.

### Claim 2 (depends on 1)

A method as claimed in claim 1 wherein fc(l)=ml where m is an integer.

### Claim 3 (depends on 2)

A method as claimed in claim 2 wherein fr(k)=nk where n is an integer.

### Claim 4 (depends on 3)

A method as claimed in claim 3 wherein n=1.

### Claim 5 (depends on 2)

A method as claimed in claim 2 wherein m=1.

### Claim 6 (depends on 2)

A method as claimed in claim 2 wherein m is approximately equal to NrNc.

### Claim 7 (depends on 1)

A method as claimed in claim 1 wherein fr(k) is zero.

### Claim 8 (depends on 1)

A method as claimed in claim 1 wherein αr is the largest prime number less than Nr/2.

### Claim 9 (depends on 1)

A method as claimed in claim 1 wherein αc is the largest prime number less than Nc/2.

### Claim 10 (depends on 1)

A method as claimed in claim 1 wherein a number of data symbols to be interleaved is less than NrNc, the method further comprising the step of determining one or more matrix positions in which data symbols to be interleaved are not represented, interleaved data symbols not being derived from such determined matrix positions.

### Claim 11 (depends on 1)

A data symbol interleaver arranged for carrying out a method as claimed in claim 1.

### Claim 12 (depends on 1)

A method of claim 1, further comprising puncturing the data symbols to be interleaved, separating adjacent ones of the punctured data symbols in accordance with the interleaving.

### Claim 13

An apparatus of interleaving data symbols, comprising:
a means for permuting rows and columns of a matrix of Nr rows and Nc columns, in which data symbols to be interleaved are presented row by row, in accordance with: row ⁢ ⁢ permutation ⁢ : ⁢ ⁢ I r ⁢ ⁢ ( k ) = [ α r ⁢ ⁢ k + f c ⁢ ⁢ ( l ) ] ⁢ ⁢ mod ⁢ ⁢ N r column ⁢ ⁢ permutation ⁢ : ⁢ ⁢ I c ⁢ ⁢ ( l ) = [ α c ⁢ ⁢ l + f r ⁢ ⁢ ( k ) ] ⁢ ⁢ mod ⁢ ⁢ N c
where lr(k) represents a data symbol with a row index k, k is an integer from 1 to Nr, αr is an integer, fc(l) is a non-zero function of a column index 1, I is an integer from 1 to Nc, lc(l) represents a data symbol with the column index 1, αc is an integer, fr(k) is a zero or a function of the row index k, and modNr and modNc represent modulo-Nr and modulo-Nc arithmetic respectively, interleaved data symbols being derived from the matrix column by column.

### Claim 14 (depends on 13)

The apparatus of claim 13, wherein fc(i)=ml, where m is an integer.

### Claim 15 (depends on 14)

The apparatus of claim 14, wherein m=1.

### Claim 16 (depends on 14)

The apparatus of claim 14, wherein m is approximately equal to Nr/Nc.

### Claim 17 (depends on 13)

The apparatus of claim 13, wherein fr(k) is zero.

### Claim 18 (depends on 13)

The apparatus of claim 13, wherein fr(k)=nk, where n is an integer.

### Claim 19 (depends on 18)

The apparatus of claim 18, wherein n=1.

### Claim 20 (depends on 13)

The apparatus of claim 13, wherein αr is the largest prime number less than Nc/2.

### Claim 21 (depends on 13)

The apparatus of claim 13, wherein αc is the largest prime number less than Nc/2.

### Claim 22 (depends on 13)

The apparatus of claim 13, wherein a number of data symbols to be interleaved is less than NrNc.

### Claim 23 (depends on 13)

The apparatus of claim 13 further comprising:
a means for determining one or more matrix positions in which data symbols to be interleaved are not represented, interleaved data symbols not being derived from such determined matrix positions.

### Claim 24 (depends on 13)

A method for symbol interleaving arranged to be carried by an apparatus of claim 13.

### Claim 25

An apparatus for interleaving data symbols comprising:
a memory arranged to store data symbols to be interleaved, the memory having storage locations representing rows and columns of a matrix of Nr rows and Nc columns, the data symbols to be interleaved being represented row by row in said matrix;
an address circuit for reading the stored data symbols in an interleaved manner as interleaved data symbols from the storage locations of the memory so that the interleaved data symbols are derived column by column from a permutation of the matrix in accordance with:
Row Permutation Ir (k) = [αrk + fc (l)] modNr Column Permutation Ic (l) = [αcl + fr (k)] modNc
where lr(k) represents a data symbol with a row index k, k is an integer from 1 to Nr, αr is an integer, fc(l) is a non-zero function of a column index 1, I is an integer from 1 to Nc, lc(l) represents a data symbol with the column index 1, αc; is an integer, fr(k) is zero or a function of the row index k, and modNr and modNc represent modulo-Nr and modulo-Nc arithmetic respectively.

### Claim 26 (depends on 25)

The apparatus of claim 25, wherein fc(l)=ml, where m is an integer.

### Claim 27 (depends on 26)

The apparatus of claim 26, wherein m=1.

### Claim 28 (depends on 26)

The apparatus of claim 26, wherein m is approximately equal to Nr/Nc.

### Claim 29 (depends on 25)

The apparatus of claim 25, wherein fr(k) is zero.

### Claim 30 (depends on 25)

The apparatus of claim 25, wherein fr(k)=nk, where n is an integer.

### Claim 31 (depends on 30)

The apparatus of claim 30, wherein n=1.

### Claim 32 (depends on 25)

The apparatus of claim 25, wherein αr is the largest prime number less than Nc/2.

### Claim 33 (depends on 25)

The apparatus of claim 25, wherein αc is the largest prime number less than Nc/2.

### Claim 34 (depends on 25)

The apparatus of claim 25, wherein a number of data symbols to be interleaved is less than NcNc.

### Claim 35 (depends on 34)

The apparatus of claim 34 further comprising:
a generator for determining of one or more matrix positions in which data symbols to be interleaved are not represented, interleaved data symbols not being derived from such determined matrix positions.

### Claim 36 (depends on 25)

A method for symbol interleaving arranged to be carried by an apparatus of claim 25.

### Claim 37 (depends on 25)

The apparatus of claim 25, wherein the memory includes storage of adjacent data symbols that are punctured, the interleaver being configured to separate the adjacent data symbols that are punctured by a distance in accordance with the interleave.
