Convolutional interleaver employing an efficient memory scheme

Details Convolutional interleaver employing an efficient memory scheme Convolutional interleaver employing an efficient memory scheme

2001-08-14

2004-08-31

Lamarre, Guy J. (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C714S762000, C714S702000

Reexamination Certificate

active

06785862

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates, generally, to digital communications and, more particularly, to the use of convolutional interleavers for forward error correction (FEC) in digital systems. More particularly, an efficient memory scheme for convolutional interleaving is disclosed.
2. Background Art
In digital communication systems, for example, in the context of digital subscriber line technology (xDSL, ADSL, VDSL etc.), it is desirable to provide reliable and robust error correction capability. One popular method of providing error correction involves the use of Reed-Solomon (R-S) code in conjunction with a convolutional interleaver. The purpose of the is combination of R-S code and interleaving is to spread bursts of errors such that adjacent bytes in the transmitted data stream do not originate from the same codeword; thus, it reduces the number of errors in any one codeword to what can be corrected by the R-S decoder (usually half of the number of redundant check bytes added in the code). The data bytes are then reordered at the receiver by a de-interleaver.
Two important parameters which characterize an interleaver are the number of bytes per interleaving block length, N, and the interleaver depth, D, which is defined as the minimum separation at the output of the interleaver of any two input bytes in the same codeword. N can be chosen to be the same length as, or a fractional length of, the R-S codeword. In this application, we will assume N is the same as the R-S codeword length. It will be appreciated, however, that the present invention is not so limited.
There are two main interleaving methods: block interleaving and convolutional interleaving. Both types of interleaving change the order of the transmitted bytes of an outgoing stream, but do so in a deterministic fashion so that the stream can be restored upon receipt. Block interleaving fills in a fixed-size block by rows and then sends the data out by columns. N×D total bytes must be stored in each of two transmit memories of a block interleaver and a total 4×N×D bytes memory area is required for an end-to-end systems (2N×D for the transmitter and 2N×D for the receiver). Compared to convolutional interleavers, block interleavers are not very efficient in terms of memory use and end-to-end delay. In general, convolutional interleavers reduce the delay and memory by a factor of 2 to 4 for the similar burst error distribution.
For a convolutional interleaver, each of the N bytes B
i
k
in a R-S codeword (say k-th codeword as shown in
FIG. 4
) is delayed by an amount that varies linearly with the byte index i, where precisely, byte B
i
k
(with index i) is delayed by i×(D−1) bytes. With the above defined rule, and the chosen interleaving depths, the output bytes from the interleaver always occupy distinct time slots when N and D are co-primed as shown in
FIG. 4
with N=15, D=4. When they are not co-primed, dummy bytes are typically added at the beginning of the codeword at the input to the interleaver, and then (N−1) and D are co-primed. The resultant codeword is then convolutionally interleaved, and the dummy byte is removed from the output of the interleaver as in
FIG. 5
, where N=14, D=4.
The interleaver scheme adopted in ANSI T1.413, and ITU G.992.1/G.992.2 (ADSL) is based on a system originally proposed in Aslanis, J. T., Tong, P. T. and Zogakis, T. N., “An ADSL proposal for selectable forward error correction with convolutional interleaving”, Aug. 20, 1992, TIE1.4: ADSL; and Tong, P. T., Zoagkis, T. N. and Cioffi, J. M., “Revised FEC and interleaving recommendations for DMT ADSL”, TIE1.4/93-117, May 1993.
A special type of triangular convolutional interleaver, adopted in the latest ANSI T1E1 VDSL draft, requires that the interleaver depth be D=N×M+1, where M is an integer. The implementation requires a memory of (N−1)×(D−1) bytes, but the constraint on D is very inconvenient for xDSL, when a typical xDSL system uses D<N. A conventional method of implementing the convolutional interleaver, arranged in a one-dimensional array, is to use a circular buffer of circumference N×D. For input byte B
i
k
, the i-th byte in the k-th R-S codeword is as follows:
write address=(
k×N+i×D
)mod
N×D
, for
i
=0, 1
, . . . , N
−1
,k=
0,1
, . . . , D
−1
read address=(
k×N+i)mod N×D
, for
i
=0,1
, . . . , N−
1
, k
=0,1
, . . . , D−
1.
Alternatively, one can also use a N×D matrix with n as column index and m as row index as shown in
FIGS. 4-5
as follows,
 write address: (
n,m
)=((
i×D
) mod
N
, (
k+i×D
) mod mod
D
),
read address: (
n,m
)=(
i, k
mod
D
), ∀
i
=0,1
, . . . , N
−1
, k
=0,1
, . . . ,D
−1.
It can be shown that the memory requirement of the conventional implementation of the convolutional interleaver is N×D bytes. Thus, the convolutional interleaver needs no more than half the memory of a block interleaver but twice that of triangular interleaver. As the codeword length and interleaver depth increase for such interleaver systems, the memory requirements become quite significant. As memory requires a significant amount of chip area, it is often necessary to implement such interleavers using multiple integrated circuits, which increases cost, size, and interconnect complexity.
Even in the event the interleaver and memory are included on a single chip, such chips tend to be large. Due to defect density in semiconductor manufacturing, the process yield (i.e., the number of good chips per wafer) is significantly reduced.
Referring now to
FIGS. 4 and 5
, it should be noted that at any time epoch k almost half of bytes in the memory need not be stored because they have already been transmitted. The memory locations vacated are available for storing new incoming bytes. U. S. Pat. No. 5,764,649 (“Tong”) discloses a fairly complicated addressing scheme—involving reading one byte from an address, writing to the same address, and then calculating the next address. The Tong method can reduce the memory requirement to almost ND/2, which is the theoretical limit. However, the Tong method is unsatisfactory in a number of respects. For example, in order to reduce the memory requirement, the computational-complexity of the algorithm is high and difficult to implement. In particular, this scheme uses at least 3N programmable registers to address the interleaver memory. Thus, there is an intense need for convolutional interleaver designs, which incorporate a more efficient interleaver memory arrangement. More particularly, there is a need for improved convolutional interleaving methods which save memory while significantly reduce programming complexity.
SUMMARY OF THE INVENTION
In accordance with one aspect of the present invention, a convolutional interleaver includes an interleaver memory partitioned into a plurality of circular buffers, wherein each of said circular buffers has a write pointer and a read pointer associated therewith, and wherein the interleaver is configured to selectively read symbols from an input vector and store the input symbols in the interleaver memory in accordance with said write pointers, and to selectively read symbols from said interleaver memory to form an output vector in accordance with said read pointers.
In a further aspect of the present invention, symbols are written to the interleaver prior to reading. In accordance with another aspect, the position of the write pointer corresponds to the position of the read pointer within the circular buffer, and symbols are read from said interleaver memory prior to writing. In this way, the size of the interleaver memory can be significantly reduced. More importantly, the present invention approaches the theoretical memory limit with much lower complexity.


REFERENCES:
patent: 5636224 (1997-06-01), Vo

Affiliated with

Also associated with

Rating

Convolutional interleaver employing an efficient memory scheme does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Convolutional interleaver employing an efficient memory scheme, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Convolutional interleaver employing an efficient memory scheme will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3361323