Error detection/correction and fault detection/recovery – Pulse or data error handling – Data formatting to improve error detection correction...
Reexamination Certificate
2002-10-30
2004-09-07
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Data formatting to improve error detection correction...
Reexamination Certificate
active
06789218
ABSTRACT:
FIELD OF THE INVENTION
The present invention is related to the field of digital communications. More particularly, the present invention is a method and apparatus for, inter alia, conducting digital communications using a generatable pseudo random interleaver.
DESCRIPTION OF RELATED TECHNOLOGY
Turbo coding is a recently developed forward error correction coding and decoding technique that provides previously unavailable error correction performance. A general description of a parallel turbo code can be found in U.S. Pat. No. 5,446,747 entitled “Error-correction Coding Method With at Least Two Systematic Convolution Codings in Parallel, Corresponding Iterative Decoding Method, Decoding Module and Decoder,” filed Apr. 16, 1992 assigned to France Telecom and incorporated herein by reference. The enhanced level of error correction provided by turbo codes facilitates the transmission of data over noisy channels, thereby improving the data transmission capability of all sorts of communications systems.
Some characteristics of turbo codes combine to make the associated decoders more difficult to implement in an integrated circuit. These characteristics include large frame sizes, the use of repeated decoding steps that incorporate extrinsic information, and the use of a pseudo random interleaver for generating interleaved versions of the transmitted information and extrinsic information used during encoding and decoding. Additionally, many turbo-coding schemes require a sufficiently high degree of randomness in the pseudo random interleaver that the data sequence must be stored in memory rather than calculated on the fly.
This combination of characteristics causes turbo codes to require, in general, greater processing resources than other forward error correction coding techniques. For example, the use of repeated decoding steps increases the decoding time. The (typically) large frame size combined with the use of extrinsic information during decoding increases the amount of memory required to implement a decoder.
Additionally, the use of a pseudo random interleaver complicates the ability to decode a frame in parallel because extrinsic and sample information can not be accessed in an orderly fashion. Memory requirements are further increased by the use of memory based interleavers, which are preferred when turbo codes having the best performance are required. The use of memory based interleavers can also reduce the speed of the decoder since the interleaver typically has to be accessed twice during a decoding subiteration. This limits the possible decoding speed to half the memory access rate, which is often much slower than the rate of other available circuits.
In the paper, S. Crozier, “
New High-Spread High-Distance Interleavers for Turbo Codes
”, 20-th biennial Symposium on Communications (Kingston, Canada, May 2000), pp. 3-7, various high spread pseudo random interleavers are described, including a high-spread random interleaver as well as a “dithered-diagonal” interleaver. These interleavers provide excellent “spreading” properties while also maintaining sufficient randomness to provide good performance when incorporated into a turbo decoder.
One interleaver described in the paper is a high spread random interleaver. The high spread interleaver is generated by randomly generating real numbers, applying a spread test, and then rejecting those numbers that do not pass the spread test. Finally, a sorting step is performed. The resulting interleaver provides excellent performance when used in a turbo code, but cannot be generated in real time on an integrated circuit due in part to the sorting step. Because these interleavers cannot be generated in real time, they typically must be stored in memory consuming large amounts of chip area.
The paper also describes a dithered-diagonal interleaver including a number of variations. In the most general variation, interleaver generation requires dithering a set of diagonal lines and then enclosing a block K of these dithered values. The resulting values are sorted to determine integer read and write indexes.
While the dithered-diagonal interleavers also provide good spreading and randomness properties, in their most general form, dithered-diagonal interleavers can not be generated on the fly. Thus, the dithered diagonal interleaver also requires substantial circuit area for real time implementation on an integrated circuit.
The above referenced paper does describe one generatable variation of the dithered diagonal interleaver. (referred to herein as the “generatable dithered diagonal” (GDD) interleaver). However, in order to make the interleaver generatable, the GDD interleaver places some restrictions on the size of the interleaver and the dithering that can be performed.
These restrictions significantly reduce the performance and usefulness of this interleaver in a turbo code because the restrictions significantly reduce the randomness property of the interleaver. The performance reduction worsens as the size the interleaver increases.
Thus, while the paper sets forth many very useful interleavers, it does not supply a highly flexible, readily generatable interleaver that has performance in a turbo code comparable to the state of the art non-generatable interleavers.
SUMMARY OF THE INVENTION
The present invention is directed to providing a decoding circuit that minimizes the negative effect the above described characteristics have on performance and cost, thereby increasing the number of applications for which turbo codes may be used in a practical and economic manner. Additionally, the present invention is directed to a turbo decoder architecture that provides broadband using a practical amount of circuitry and memory.
In another aspect of the invention, a method and apparatus for generating and performing digital communications using a randomized generatable interleaver is described. In accordance with one embodiment of the invention, a pseudo random interleaver of size n*m with excellent randomness and spread properties may be generated form set a set of seed values.
In one exemplary embodiment, the interleaver of size N=n*m is defined by, dividing the N possible address in the interleaver (0−N−1) into n subsets. The subsets are preferably generatable from a single value within the subset either using an algorithm or a memory based lookup table. To select the set of n seeds one value from each subset is selected.
The interleaver is preferably employed in a communication system incorporating the use of turbo codes or other concatenated coding systems incorporated the use of pseudo-random interleavers such as serial concatenated codes or hybrids.
REFERENCES:
patent: 5056105 (1991-10-01), Darmon et al.
patent: 5136588 (1992-08-01), Ishijima
patent: 5377340 (1994-12-01), Seroussi et al.
patent: 5530837 (1996-06-01), Williams et al.
patent: 5535220 (1996-07-01), Kanno et al.
patent: 5652861 (1997-07-01), Mayo et al.
patent: 5924111 (1999-07-01), Huang et al.
patent: 6035434 (2000-03-01), Sazzad et al.
patent: 6323788 (2001-11-01), Kim et al.
patent: 6339834 (2002-01-01), Crozier et al.
patent: 6381728 (2002-04-01), Kang
patent: 6434203 (2002-08-01), Halter
patent: 6590951 (2003-07-01), Kim et al.
patent: 6591381 (2003-07-01), Kim et al.
patent: 6598202 (2003-07-01), Kim et al.
patent: 6603412 (2003-08-01), Gatherer et al.
Edmonston Brian S.
Gray Paul K.
Baker Stephen M.
Gazdzinski & Associates
Icoding Technology, Inc.
LandOfFree
High spread highly randomized generatable interleavers does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with High spread highly randomized generatable interleavers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High spread highly randomized generatable interleavers will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3209209