Interleaving with golden section increments

Details Interleaving with golden section increments Interleaving with golden section increments

1999-05-27

2002-01-15

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

06339834

ABSTRACT:

FIELD OF THE INVENTION
This invention relates to interleaving and is particularly concerned with interleaving systems and methods suited for Turbo and Turbo-like forward-error-correcting codes, by using golden section increments.
BACKGROUND OF THE INVENTION
Interleaving is a key component of many digital communications systems involving forward error correction (FEC) coding. This is especially true for channels characterized by fading, multipath, and impulse noise, for example. A second example is the class of magnetic recording channels where bursts of errors are caused by defects in the recording media. Interleaving, or permuting, of the transmitted elements, provides time diversity for the FEC scheme being employed. An element is used herein to refer to any symbol, sample, digit, or a binary digit (bit). Interleaving spreads out the corrupted portions of the signal and makes it easier for the FEC scheme to correct the associated errors. Conventionally, the interleaving strategy is only weakly linked to the FEC scheme being employed. An exception is the case of concatenated FEC schemes using concatenated Viterbi and Reed-Solomon decoders. The interleaver is placed between the two FEC encoders to help spread out error bursts and the depth of interleaving is directly linked to the error correction capability of the inner (Viterbi) decoder. More recently, however, interleavers have become a more integral part of the coding and decoding strategy itself. Such is the case for Turbo and Turbo-like codes, where the interleaver forms an integral part of the coding scheme. The problem of finding optimal interleavers for such schemes is really a code design problem, and is an on-going area of research.
Claude Berrou obtained U.S. Pat. No. 4,446,747 entitled: “Error-correction coding method with at least two systematic convolutional codings in parallel, corresponding iterative decoding method, decoding module and decoder”. This patent describes essentially the same Turbo-code presented by Berrou et al. in their paper “Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codes”, published in the Proceedings of ICC'93, Geneva, Switzerland, pp. 1064-1070, May, 1993. The Turbo code presented, is a rate ½ binary code that provided performance within 0.5 dB of the BPSK capacity limit at a BER of 10
−5
, when using an interleaver block size of 65,536. This result is also only 0.7 dB from the more general Shannon capacity limit. The encoder consists of two rate ½ recursive systematic convolutional (RSC) encoders operating in parallel with the information binary digits (bits) interleaved between the two encoders as shown in FIG.
1
. Without puncturing, and with rate ½ constituent codes, the overall code rate is ⅓. This is because the systematic information bits only need to be sent once. Other code rates can be achieved as required by puncturing the parity bits c
1
k
and c
2
k
. In this configuration, the job of the interleaver is to spread error bursts that occur in one code throughout the other code so that there is a higher probability of correcting unreliable information.
More recently Berrou, and Glavieux provided more discussion of the coding and decoding of Turbo codes in their paper “Near Optimum Error Correcting Coding and Decoding: Turbo-Codes”, published in the IEEE Trans. on Conm., Vol. 44, No. 10, October 1996.
FIG. 2
illustrates one approach to Turbo decoding, based on maximum a posteriori (MAP) decoding algorithm derived by Bahl et al their paper “Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate”, published in IEEE Trans. on Inform. Theory, Vol. IT-20, pp. 284-287, March 1974. The MAP decoder is implemented in the log domain, so the log-MAP algorithm is used. The Turbo decoder uses an iterative process where the de-interleaved output vector of the second log-MAP decoder L
2
, is fed back to the input of the first log-MAP decoder after the first iteration. The storage vector to the second log-MAP decoder must be interleaved using the same interleaver used in the Turbo encoder. Likewise, the output from the second log-MAP decoder must be de-interleaved before being fed back to the input of the first log-MAP decoder. Decisions can be made either at the output of the first log-MAP decoder or the de-interleaved output of the second log-MAP decoder. It is the convention that one Turbo decoding iteration be defined as two log-MAP decoding operations as shown in FIG.
2
.
Interleaving is a key component of any Turbo encoder and decoder, as already shown in
FIGS. 1 and 2
. Although some form of random or pseudo-random interleaving is usually recommended for Turbo-codes, it has been found that simple structured interleavers can also offer excellent performance, especially for short data blocks on the order of a few hundred bits. Examples of structured prior art interleavers include relative prime interleavers, convolutional interleavers, helical interleaver and L×M matrix (or block) interleavers using L rows and M columns. L×M matrix interleavers are usually implemented by writing into the rows and reading out of the columns, or vice versa. The rows and/or columns are sometimes read in and/or out in a permuted order. This permuted order is often implemented using a relative prime number. That is, the row or column index can be generated using modulo arithmetic where the index increment and row or column lengths are relative prime numbers. With L or M equal to 1, this type of interleaver simply becomes a one-dimensional relative prime interleaver.
In U.S. Pat. No. 5,056,105, Darmon et al refer to relative prime interleavers which seem to offer some advantages over conventional L×M matrix interleavers. In a relative prime interleaver, the n'th digit (element) of the interleaved vector is read out of the original vector using the index s+np, modulo N, where s is an integer starting index and p is an integer index increment. The starting index s is usually set to 0 but can be any index. The increment p must be relative prime to the block size N to ensure that each element is read out once and only once.
One problem with prior art interleavers is that they are usually designed to provide a specific interleaving depth. This is fine if each burst of errors never exceeds the interleaver depth, but it is wasteful if the interleaver is over-designed (too long) and error bursts are much shorter than the interleaver depth. For example, a simple 10×10 matrix interleaver has an interleaving depth of 10 elements. If a burst of 10 errors occurs, the de-interleaver will optimally spread these 10 errors throughout the block of 100 elements. If the error burst is 11 elements long, however, then two errors will again be adjacent. If the error burst is only 2-elements long then these 2 errors will only be spaced 10 elements apart after de-interleaving, but they could have been spaced much farther apart if it was known that only two errors were present. For example, a 2×50 matrix interleaver would have spaced these two errors 50 elements apart. Of course this interleaver is not good for longer bursts of errors. In practice, most channels usually generate error events of random length, and the average length can be time varying, as well as unknown. This makes it very difficult to design optimum interleaving strategies using the above-mentioned prior art methods.
It is also desirable for an interleaving strategy for Turbo-codes to spread “error bursts” from one component decoder throughout the data block for the other component decoder. One measure of how good a particular burst of elements has been spread by an interleaver is the minimum difference between the interleaved indexes of the original burst of elements considered. The problem is that error bursts can start anywhere and are random in length. The best interleaver for one burst length is not necessarily the best interleaver for another burst length. What is sought is an interleaving strategy that is good for any error burst length.
SUMMARY OF THE

Affiliated with

Also associated with

Rating

Interleaving with golden section increments does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Interleaving with golden section increments, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interleaving with golden section increments will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2826545