Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2001-08-06
2004-08-31
Dildine, R. Stephen (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S759000, C714S774000
Reexamination Certificate
active
06785859
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention relates to electronic devices, and, more particularly, to encoders and decoders for turbo codes and methods of coding.
Digital communication systems typically employ a channel coding for the symbols transmitted across a communication channel; the channel coding introduces redundancies to provide for correction of errors introduced by the communication channel. In 1993 Berrou et al introduced “turbo coding” as a type of channel coding with error correction performance close to the theoretical limit. Turbo code are parallel concatenations of recursive systematic (punctured) convolutional coders with random interleaving between the recursive encoders as illustrated schematically in
FIG. 2
a
for the case of two recursive encoders.
FIG. 2
b
shows a corresponding decoder with serial architecture; parallel decoders also exist. Turbo codes apparently achieve their performance with relatively simple component codes and large information blocks with random interleavers. A signal-to-noise ratio of only 0.7 dB could yield a bit error rate (BER) of 10
−5
and could be useful for noisy communication channels. Essentially, the interleaver should be capable of spreading low-weight input sequences so that the resulting codeword has high weight. The interleaver reorders the symbols in a block of K symbols (typically in the range of 100-100,000). Mathematically, the interleaver generates a permutation that maps the set {0, 1, 2, 3, . . . , K−1} onto itself so that the mapping is one-to-one.
In conventional communication systems that require interleaving, the common practice is to apply a block interleaver. A block interleaver can be easily implemented by writing the data into a matrix of dimensions K
1
×K
2
(K=K
1
K
2
) row by row and then reading the data out column by column.
The actual permutation used in a turbo coding scheme has a crucial effect on the performance of the coding scheme in terms of probability of bit error at a given signal-to-noise ratio. It has been found that a good interleaver for a turbo coding scheme resembles a random permutation. The simple method of using a block interleaver has been proven to be unsatisfactory for turbo coding.
The design of a good interleaver for a turbo coding scheme turned out to be an extremely difficult challenge and has become a topic of an extensive research effort. While no method for designing an “optimal” interleaver has yet been found, most of the published procedures for designing a good interleaver are based on the following principles:
a. Given the size of the data block and other parameters of the turbo coding scheme, design an interleaver by either applying a deterministic procedure or by generating numerous random permutations and picking out the “best” permutation. The choice of the best permutation is made by applying some quality criterion.
b. Store the found interleaver in the transmitter (encoder) and in the receiver (decoder). The interleaver is usually stored as the sequence of the permuted indices. Thus, the required storage memory increases linearly with the block size K.
The foregoing approach for “off-line” construction of an interleaver enables one to generate an interleaver matched to a specific coding scheme by applying one of the suggested procedures. However, this approach implies that memory storage is allocated in both the transmitter and the receiver for storing the computed permutation.
The foregoing approach for “off-line” construction of an interleaver has two shortcomings:
a. Dedicated storage memory is required. This might be a serious problem if the coding scheme operates with a large block.
b. The approach is not applicable for a coding system which is designed to use blocks of variable size. If the number of legitimate block sizes is large, it would be impractical to design and store “off-line” designed interleavers for all allowable block sizes.
Dolinar et al, Weight Distribution of Turbo Codes Using Random and Nonrandom Permutations, JPL TDA Progress Report 42-122 (August 1995) analyzes various interleavers with regard to how effectively data sequences that produce low encoded weight at the output of one encoder are matched with permutations of the same data sequence that yield higher encoded weights at the outputs of the other encoder(s). One of the permutations considered (in detail for the case N=32) was the circular shift &pgr;(j)=a*j+r (mod N) where r<N is an offset and a <N is a step size that is relatively prime to N. Similarly, Takeshita et al, On Deterministic Linear Interleavers for Turbo Codes, 35th Allerton Conference on Communication, Control and Computing (September 1997). Divsalar et al, U.S. Pat. No. 6,023,783 illustrates various Turbo code encoder architectures which incorporate interleavers.
SUMMARY OF THE INVENTION
The present invention provides a permutation generator for constructing interleavers for turbo coding schemes with varying block sizes.
This has advantages including real-time permutation generation with minimal memory requirements.
REFERENCES:
patent: 6430722 (2002-08-01), Eroz et al.
Ran, Moshe and Shahaf Wayer; Improving ECC scheme of proposals 802.16.1pc-00/14 and 802.16.1pc-00/13; Mar. 6, 2000; IEEE Broadband Wireless Access Working Group <http://ieee802.org/16>; pp. 1-15.*
Hess, Jason R.; Implementation of a Turbo Decoder on a Configurable Computing Platform; Sep. 17, 1999; Virginia Polytechnic Institute and State University (scholar.lib.vt.edu); pp. i-x and 1-74.*
Barbulescu, Sorin A. et al.; Turbo Codes 2000; Jan. 8-12, 2001; ITU—Telecommunication Standardization Sector, Study Group 15, pp. 1-20.
Brady W. James
Dildine R. Stephen
Hoel Carlton H.
Telecky, Jr. Fredrick J.
Texas Instruments Incorporated
LandOfFree
Interleaver for variable block size does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Interleaver for variable block size, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interleaver for variable block size will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3278615