Data interleaver and method of interleaving data

Details Data interleaver and method of interleaving data Data interleaver and method of interleaving data

2003-04-14

2004-01-27

Chung, Phung M. (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C714S701000

Reexamination Certificate

active

06684361

ABSTRACT:

This invention relates to data interleavers and to methods of interleaving data symbols, and is particularly concerned with a so-called channel interleaver for interleaving data symbols in a communications system.
BACKGROUND
It is well known to perform interleaving of data in a communications system using forward error correction (FEC) in order, on deinterleaving, to distribute errors to facilitate their correction. Typically, such interleaving uses a block interleaver to interleave blocks of data. So-called turbo coding (parallel concatenated convolutional coding) uses an interleaver between inputs to two convolutional coders which produce respective parity bits from the input data before and after interleaving. With increasing attention being given to the use of turbo coding, particularly in wireless communications systems, attention has also been given to the form of the interleaver.
So-called 3rd generation CDMA (code division multiple access) wireless communications systems are also being developed which require a channel or inter-frame interleaver which operates to interleave or permute data in blocks corresponding to the radio frame duration, typically 10 ms. For example, a multi-stage block interleaver (MIL) has been proposed for channel (inter-frame) interleaving and for intra-frame interleaving.
However, in such systems the channel interleaver either precedes or follows a rate matching function which serves to match various data rates to the radio frame rate, and which typically involves puncturing (omission) of data symbols. It is necessary to avoid consecutive puncture of adjacent data symbols of coded blocks of data symbols, but the multi-stage interleaver suffers from a problem in this respect. A so-called potential punturing grid (PPG) concept has been proposed to correct this problem, but the choice of an appropriate PPG depends on variables such as the frame size, number of frames, puncturing rate, and puncturing position.
Accordingly, it would be desirable to provide an interleaver which maximizes the distances by which adjacent punctured data symbols are separated, for arbitrary puncturing rates and puncturing positions, without any PPG.
An object of this invention is to provide an improved data interleaver and method of interleaving data symbols.
SUMMARY OF THE INVENTION
According to one aspect, this invention provides a method of interleaving data symbols comprising permuting rows and columns of a matrix of N
r
rows and N
c
columns, in which data symbols to be interleaved are represented row by row, in accordance with:
Row Permutation
I
r
(k) = [&agr;
r
k + f
c
(l)]modN
r
Column Permutation
I
c
(l) = [&agr;
c
l + f
r
(k)]modN
c
where I
r
(k) represents a data symbol with a row index k, k is an integer from 1 to N
r
, &agr;
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 symbol with the column index l, &agr;
c
is an integer, f
r
(k) is zero or a function of the row index k, and modN
r
and modN
c
represent modulo-N
r
and modulo-N
c
arithmetic respectively, interleaved data symbols being derived from the matrix column by column.
Preferably f
c
(l)=ml where m is an integer; for example m is 1 or is approximately equal to N
r
/N
c
. If f
r
(k) is not zero, then preferably f
r
(k)=nk where n is an integer; for example n=1. Conveniently &agr;
r
is the largest prime number less than N
r
/2, and &agr;
c
is the largest prime number less than N
c
/2.
The actual number of data symbols to be interleaved need not be exactly equal to N
r
N
c
but can be a little less than this, in which case preferably the method further comprises 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.
The invention also provides a data symbol interleaver arranged for carrying out a method as recited above.
Another aspect of the invention provides a data interleaver comprising: a memory arranged to sequentially store up to N
c
N
r
data symbols to be interleaved at respective addresses, where N
c
and N
r
are integers greater than 1; a counter arranged to provide an index l from l to Nc, and a counter arranged to provide an index from l to Nr for each value of the index l; a circuit arranged to determine a first value [&agr;
c
l+nk]modN
c
and a second value [&agr;
r
k+ml]modN
r
, where &agr;
c
, &agr;
r
, and m are positive integers and n is a positive integer or zero, and modN
r
and modN
c
represent modulo-N
r
and modulo-N
c
arithmetic respectively; and an address combiner arranged to combine the first value as a more significant part and the second value as a less significant part of a read address for reading interleaved data symbols from the memory.
The data interleaver can further comprise an address decoder responsive to at least one read address produced by the address combiner at which a data symbol to be interleaved is not stored in the memory for inhibiting reading from the memory from such address. In this case conveniently the data interleaver further includes a first-in, first-out buffer arranged to buffer interleaved data symbols read from the memory.
The invention further provides a channel interleaver for a communications system including a data rate matching circuit which performs puncturing of data symbols, comprising a data interleaver as recited above.


REFERENCES:
patent: 6108252 (2000-08-01), Park
patent: 6334197 (2001-12-01), Eroz et al.
patent: 6442728 (2002-08-01), Cui et al.
patent: 6543013 (2003-04-01), Li et al.
patent: 6553516 (2003-04-01), Suda et al.

Affiliated with

Also associated with

Rating

Data interleaver and method of interleaving data does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Data interleaver and method of interleaving data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data interleaver and method of interleaving data will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3266984