Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-03-04
2002-08-27
Chung, Phung M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S755000, C714S790000
Reexamination Certificate
active
06442728
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to communication 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. Since the capacity of a CDMA environment is dependent upon the operating signal to noise ratio, improved performance translates into higher capacity.
An aspect of turbo coders which makes them so effective is an interleaver which permutes the original received or transmitted data frame before it is input to a second encoder. The permuting is accomplished by randomizing portions of the signal based upon one or more randomizing algorithms. Combining the permuted data frames with the original data frames has been shown to achieve low BERs in AWGN and fading channels. The interleaving process increases the diversity in the data such 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 an array, where the array is sequentially filled up row by row. After a predefined number of signal points have been framed, the interleaver is emptied by sequentially reading out the columns of the array for transmission. As a result, signal points in the same row of the array 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 array. 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.
Non-uniform interleaving achieves “maximum scattering” of data and “maximum disorder” of the output sequence. Thus the redundancy introduced by the two convolutional encoders 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 practically implement the interleaving while achieving sufficient “non-uniformity,” and minimizing delay compensations which limit the use for applications with real-time requirements.
Finding an effective interleaver is a current topic in the third generation CDMA standard activities. It has been determined and generally agreed that, as the frame size approaches infinity, the most effective interleaver is the random interleaver. However, for finite frame sizes, the decision as to the most effective interleaver is still open for discussion.
Accordingly there exists a need for systems and methods of interleaving codes that improve non-uniformity for finite frame sizes.
There also exists a need for such systems and methods of interleaving codes which are relatively simple to implement.
It is thus an object of the present invention to provide systems and methods of interleaving codes that improve non-uniformity for finite frame sizes.
It is also an object of the present invention to provide systems and methods of interleaving codes which are relatively simple to implement.
These and other objects of the invention will become apparent to those skilled in the art from the following description thereof.
SUMMARY OF THE INVENTION
The foregoing objects, and others, 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 an interleaver for interleaving these data frames. The interleaver includes an input memory configured to store a received data frame as an array organized into rows and columns, a processor connected to the input memory and configured to permute the received data frame in accordance with the equation D(j,k)=D (j, (&agr;
j
k+&bgr;
j
)modP), and a working memory in electrical communication with the processor and configured to store a permuted version of the data frame. The elements of the equation are as follows: D is the data frame, j and k are indexes to the rows and columns, respectively, in the data frame, &agr; and &bgr; are sets of constants selected according to the current row, and P and each &agr;
j
are relative prime numbers. (“Relative prime numbers” connotes a set of numbers that have no common divisor other than 1. Members of a set of relative prime numbers, considered by themselves, need not be prime numbers.)
Another embodiment of the invention includes a method of storing a data frame and indexing it by an N
1
×N
2
index array I, where the product of N
1
and N
2
is at least equal to N. The elements of the index array indicate positions of the elements of the data frame. The data frame elements may be stored in any convenient manner and need not be organized as an array. The method further includes permuting the index array according to I(j,k)=I(j,(&agr;
j
k+&bgr;
j
)modP), wherein I is the index array, and as above j and k are indexes to the rows and columns, respectively, in the index array, &agr; and &bgr; are sets of constants selected according to the current row, and P and each &agr;
j
are relative prime numbers. The data frame, as indexed by the permuted index array I, is effectively permuted.
Still another embodiment of the invention includes an interleaver which includes a storage device for storing a data frame and for storing an N
1
×N
2
index array I, where the product of N
1
and N
2
is at least equal to N. The elements of the index array indicate positions of the elements of the data frame. The data frame elements may be stored in any convenient manner and need not be organized as an array. The interleaver further includes a permuting device for permuting the index array according to I(j,k)=I(j,(&agr;
j
k+&bgr;
j
)modP), wherein I is the index array, and as above j and k are indexes to the rows and columns, respectively, in the index array, &agr; and &bgr; are sets of constants selected according to the current row, and P and each &agr;
j
are relative prime numbers. The data frame, as indexed by the permuted index array I, is effectively permuted.
The invention will next be described in connection with certain illustrated embodiments and practices. However, it will be clear to those skilled in the art that various modifications, additions and subtractions can be made without departing from the spirit or scope of the claims.
REFERENCES:
patent: 4394642 (1983-07-01), Currie
patent: 5742612 (1998-04-01), Gourge
“Computer Dictionary” Microsoft Press, Second Edition, 1994, pp. 218-219.*
Interleaver design for turbo codes with reduced memory requirement, ETSI SMG2 UMTS L1 Expert Group, Tdoc SMG2 UMTS L1 510-98, Nov. 1998.
Description of the GF Interleaver for Turbo Codes, ETSI SMG2 UMTS L1 Expert Group, Tdoc SMG2 UMTS-L1 765/98, Jan. 1999.
Algebraic interleavers for turbo codes: Precisions on complexity and interleaver generation, ETSI SMG2 UMTS L1 Expert Group, Tdoc SMG2 UMTS-L1 721-98, Dec. 1998.
A Proposal for Turbo Code Interleaving, mschaff1@email.mot.com, Motorola, Inc. 1998.
Turbo Interleaver Performance Evaluation, brownta@cig.mot.com, Motorola, Inc., 1998.
A new Low-Complexity TurboCode Interleaver Employing Linear Congruential Sequences (Revised), fling@qualcomm.com, Qualcomm, Inc., 1998.
New Interleaver Proposals from Lucent Technologies.
Cui Jian
Li Bin
Tong Weng
Wang Rui R.
Chung Phung M.
Cobrin & Gittes
Nortel Networks Limited
LandOfFree
Methods and apparatus 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 Methods and apparatus for turbo code, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for turbo code will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2879132