Error detection/correction and fault detection/recovery – Pulse or data error handling – Data formatting to improve error detection correction...
Reexamination Certificate
1999-08-16
2001-12-25
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Data formatting to improve error detection correction...
C714S755000
Reexamination Certificate
active
06334197
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to error correction in coding schemes for digital communication systems, and more particularly to design optimization for Interleavers of any size within a specified wide range used in such error correction. Even more particularly, the present invention relates to optimization of Turbo Interleavers such that smaller optimal Interleavers can be built from larger optimal Interleavers.
Interleaving is a process of reordering a sequence of symbols or bits in a predetermined manner. “Interleaver size” is equal to the size of the sequence. The apparatus performing the interleaving is referred to herein as an Interleaver.
Turbo Interleavers are interleavers used in the construction of turbo codes. In a turbo code built as a parallel concatenation of two constituent recursive convolutional codes, a Turbo Interleaver serves to re-order an input data sequence in a pseudo-random fashion prior to an encoding by a second of the constituent codes. As a result, separate encodings produced by the two constituent encoders are largely uncorrelated, which property allows them to be combined by a turbo encoder to produce a composite encoding with excellent error protection capability.
S-random Interleavers are one of the most widespread forms of turbo Interleavers.
The principle behind S-random Interleavers is to avoid mapping neighbor positions of an original input sequence to another neighbor position of the interleaved sequence within a window of size S. The design goal in S-random Interleavers is to maximize S while preserving the above principle. However, S-random Interleavers have to be re-designed every time the Interleaver size is changed and there is typically no requirement of any resemblance between the Interleavers with similar sizes.
Thus, it is desirable to have a general Interleaver design for Interleavers of any size within a set of sizes, wherein the design methodology is concise and efficient such that the same Interleaver design is near-optimal for all Interleavers within the set of sizes. It is also advantageous to have a design for building a near-optimal Interleaver that can easily be reduced to smaller-sized near-optimal Interleavers without performance degradation.
Therefore, the present invention advantageously addresses the above and other needs.
SUMMARY OF THE INVENTION
The present invention advantageously addresses the needs above as well as other needs by providing a method and apparatus for a turbo Interleaver which employs Interleavers of variable length employing one or more permutations.
In one embodiment, the invention is characterized as a method of interleaving blocks of indexed data of varying length. The method includes the steps of: providing a set of basic Interleavers comprising a family of one or more permutations of the indexed data and having a variable length; selecting one of the basic Interleavers based upon a desired Interleaver length L; and adapting the selected basic Interleaver to produce an Interleaver having the desired Interleaver length L.
In another variation, a method of interleaving blocks of indexed data of variable length includes the steps of: providing a family of basic Interleavers comprising “two-dimensional permutations” including computing the “two-dimensional permutations”, further comprising: writing the indexed data into an Interleaver matrix having one or more rows in each of two dimensions; permuting the indexed data in one or more rows in at least one of the two dimensions to produce “constituent permutations”, possibly being different from one row to another row, wherein the constituent permutations are pseudo-random permutations described by a limited number of parameters, wherein an amount of storage required for storing the limited number of parameters is less than that for storing a vector representation of the constituent permutations; reading out the data from the Interleaver matrix; selecting one of the basic Interleavers for use in encoding based upon a desired Interleaver length L; adapting the selected basic Interleaver to produce an Interleaver having the desired Interleaver length L; wherein the selecting includes: identifying a group of the basic Interleavers having a length greater than or equal to the desired Interleaver length L; and selecting one of the basic Interleavers having a length smallest among the identified group of the basic Interleavers; wherein the adapting includes: deleting indexed data having indices higher than required for a permutation of length L; providing an Interleaver device for interleaving blocks of indexed data, the Interleaver device further comprising a memory device for storing descriptions of the basic Interleavers; and storing the descriptions in the memory device.
In another embodiment, a system for interleaving and turbo encoding blocks of indexed data, of varying length, comprises: a parallel concatenation of two or more constituent encoders for recursive convolutional codes of recursion period p; and an Interleaver device coupled to the parallel concatenation for performing the steps of: accessing stored descriptions of basic Interleavers, the basic Interleavers comprising a family of one or more permutations of the indexed data and having a variable length; identifying a group of the basic Interleavers having a length greater than or equal to a desired Interleaver length L; selecting one of the basic Interleavers having a length which is smallest among the group of the basic interleaves; and adapting the selected one of the basic Interleavers to produce an Interleaver having the desired Interleaver length L.
REFERENCES:
patent: 5742612 (1998-04-01), Gourgue et al.
patent: 5996104 (1999-11-01), Herzberg
patent: 6289486 (2001-09-01), Lee et al.
patent: 0300139 A2 (1989-01-01), None
patent: 0952673 A1 (1999-10-01), None
patent: WO 96/37050 (1996-11-01), None
C. Berrou et al., Near Shannon Limit Error—Correcting Coding and Decoding: Turbo Codes, May 23, 1993.
S. V. Maric, Class of Algebraically Constructed Permutations for Use in Pseudorandom Interleavers, Aug. 18, 1994.
Eroz Mustafa
Hammons, Jr. A. Roger
Sun Feng-Wen
Baker Stephen M.
Hughes Electronics Corporation
Sales Michael W.
Whelan John T.
LandOfFree
Turbo code interleaver with near optimal performance does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Turbo code interleaver with near optimal performance, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Turbo code interleaver with near optimal performance will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2591916