Interleavers for turbo code

Details Interleavers for turbo code Interleavers for turbo code

1998-11-19

2002-02-12

Decady, Albert (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Data formatting to improve error detection correction...

Reexamination Certificate

active

06347385

ABSTRACT:

FIELD OF THE INVENTION
This invention relates to the field of electronic communications systems and, more particularly, to interleavers for performing code modulation.
BACKGROUND OF THE INVENTION
Techniques for encoding communication channels, known as coded modulation, have been found to improve the bit error rate (BER) of electronic communication systems such as modem and wireless communication systems. Turbo coded modulation has proven to be a practical, power-efficient, and bandwidth-efficient modulation method for “random-error” channels characterized by additive white Gaussian noise (AWGN) or fading. These random-error channels can be found, for example, in the code division multiple access (CDMA) environment.
The key innovation of turbo codes is an interleaver which permutes the original received or transmitted data frame before input to a second encoder. Permuting is accomplished by a processor performing a randomizing algorithm, the construction of which is well known. Combining the permuted data frames with the original data frames has shown to achieve low bit-error rates in AWGN and fading channels. The interleaving process increases the diversity in the data in such a way that if the modulated symbol is distorted in transmission the error may be recoverable with the use of error correcting algorithms in the decoder.
A conventional interleaver collects, or frames, the signal points to be transmitted into a matrix, where the matrix is sequentially filled up a row at a time. After a predefined number of signal points have been framed, the interleaver is emptied by sequentially reading out the columns of the matrix for transmission. As a result, signal points in the same row of the matrix that were near each other in the original signal point flow are separated by a number of signal points equal to the number of rows in the matrix. Ideally, the number of columns and rows would be picked such that interdependent signal points, after transmission, would be separated by more than the expected length of an error burst for the channel. However, this may not be practicable. As the number of rows is increased, so is the signal delay due to the framing of the signal points. As a result, there is a system constraint on the size of the interleaver in order to keep the signal delay within acceptable limits. On the other hand, constraining the size of the interleaver limits the separation of the time-diverse interdependent signal points and thus limits the improvement in error performance achieved by the interleaver.
There are two conventional interleaving methods; uniform interleaving (i.e. a regular interleaving pattern); and non-uniform interleaving (i.e. a pseudo-irregular interleaving pattern). In the case of uniform interleaving, finite code words (FC) of higher weight can be constructed from FCs of lower weight. Therefore a certain “repetitive pattern” of low-weight FC output sequences can occur in the output stream of a uniform-interleaving turbo coder. However, uniform interleaving does not sufficiently de-correlate the output of the two encoders, hence the minimum distance of the resulting turbo code does not increase as one might expect.
On the other hand, non-uniform interleaving achieves better “maximum scattering” of data and “maximum disorder” of the output sequence, which means that the redundancy introduced by the two convolutional codes is more equally spread in the output sequence of the turbo encoder. The minimum distance is increased to much higher values than for uniform interleaving. A persistent problem for non-uniform interleaving is how to achieve sufficient “non-uniformity”, since the interleaving algorithms can only be based on pseudo-irregular patterns. Besides this, the effort for implementing the scheme should be reasonable for practical applications. Furthermore, conventional interleavers require a significant amount of memory in the encoder. Conventional interleaving matrices also require delay compensations, which limit their use for applications with real-time requirements.
Accordingly there exists a need for systems and methods of interleaving codes that improve non-uniformity.
There also exists a need for systems and methods of interleaving codes that require minimal delay compensations.
It is thus an object of the present invention to provide systems and methods of interleaving codes that improve non-uniformity.
It is also an object of the present invention to provide systems and methods of interleaving codes that require minimal delay compensations.
SUMMARY OF THE INVENTION
In accordance with the teachings of the present invention, these and other objects may be accomplished by the present invention, which interleaves a data frame, where the data frame has a predetermined size and is made up of portions. An embodiment of the invention includes a memory configured to receive and store the data frame. Once received, the data frame is indexed by a plurality of rows having a predetermined row size and a plurality of columns having a predetermined column size. The product of the predetermined row size and the predetermined column size equals the predetermined size of the data frame.
A processor is coupled to the memory and used for separating the data frame into a plurality of portions. The processor also is used for generating a permuted sequence of the plurality of portions which are indexed by the plurality of rows in accordance with i
1
(n
1
)=&agr;
1
{circumflex over ( )}(n
1
)mod(P
1
), where P
1
is a prime number greater than the predetermined row size, where n
1
is an integer in the range of 1 through and including P
1
−1, and where &agr;
1
is a root of P
1
. This algorithm enables i
1
(n
1
) to be a unique number between 1 and the predetermined row size.
The processor is also configured to generate a permuted sequence of the plurality of portions indexed by the plurality of columns in accordance with i
2
(n
2
)=&agr;
2
{circumflex over ( )}(n
2
)mod(P
2
), where P
2
is a prime number greater than the predetermined column size, where n
2
is an integer in the range of 1 through and including P
2
−1, and where &agr;
2
is a root of P
2
. This algorithm enables i
2
(n
2
) to be a unique number between 1 and the predetermined column size. The result is interleaved portions of the dataframe.


REFERENCES:
patent: 4394642 (1983-07-01), Currie et al.
patent: 4742517 (1988-05-01), Takagi et al.
patent: 5136588 (1992-08-01), Ishijima
patent: 5483541 (1996-01-01), Linsky
patent: 5764649 (1998-06-01), Tong
patent: 6035427 (2000-03-01), Kweon
patent: 6151690 (2000-11-01), Peeters
patent: 0 235 477 (1987-09-01), None
patent: 0 511 141 (1992-10-01), None
patent: 0 627 821 (1994-12-01), None
patent: WO 97/05702 (1997-02-01), None
patent: WO 98/16930 (1998-04-01), None

Affiliated with

Also associated with

Rating

Interleavers for turbo code does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Interleavers for turbo code, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interleavers for turbo code will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2978752