Error detection/correction and fault detection/recovery – Pulse or data error handling – Data formatting to improve error detection correction...
Reexamination Certificate
2001-09-28
2004-08-03
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
06772377
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field of the Invention
The present invention relates generally to the field of communications and, more particularly, to interleaving data frames in a digital subscriber line system.
2. Description of the Related Art
Digital communication systems that are subject to bursty errors often use the technique known as “interleaving” in cooperation with error correction, such as Reed-Solomon (R-S) encoding and decoding techniques where a data stream is transformed into a sequence of error protected packets of data, to improve system reliability. Generally, there are two types of interleaving approaches; a block interleaver and a convolutional interleaver. The block interleaver interleaves the data stream in block units, comprising of rows and columns and randomizes the data stream by varying the input/output sequence. That is, the input data stream is horizontally scanned to be stored in a memory and the data stored in the memory is vertically scanned to be outputted. In a deinterleaver, the inverse permutation is accomplished by vertically scanning the data stream into a memory and then the stored data is horizontally scanned out of the deinterleaver.
In the convolutional interleaver, the input data is temporarily stored in the memory for a predetermined delay, and the same memory is used for reading and writing, which happen alternately. This group of interleavers results in an easier synchronization scheme, reduces the end-to-end latency and requires a smaller memory configuration while achieving the same performance.
For asymmetric digital subscriber line (ADSL) communication systems, convolutional interleaving and de-interleaving techniques on either end of the transmission path are used to interleave the data stream so that the effects of burst errors become distributed when the packet data is de-interleaved in a receiver or modem, and do not overwhelm the error correcting and detecting codes.
A convolutional interleaving approach used in many ADSL systems is that detailed in the G.992.1 International Telecommunication Union standard for “Asymmetrical Digital Subscriber Line (ADSL) Transceivers” which provides for interleaving data frames based on Reed-Solomon coding and convolutional interleaving (similar standards may be provided by the American National Standards Institute). The Reed-Solomon codewords are convolutionally interleaved to a depth (D) that varies and that is defined by the rule that each of the N bytes B
0
, B
1
, . . . B
N−1
in a Reed-Solomon codeword is delayed an amount that varies linearly with the byte index. More precisely, byte B
i
(with index i) is delayed by (D−1) x i bytes, where D is the interleaving depth. Further, D varies but is always a power of 2.
With a rate of 4,000 data frames per second and a maximum R-S codeword of 255 bytes per data frame, the ADSL downstream line rate is limited to approximately 8 Mbit/s per latency path. This transmission rate limitation is avoided by putting more than one codeword in an interleaved data frame. That is, the line rate limit can be increased to about 16 Mbit/s for the interleaved path by mapping two R-S codewords into one forward error correction (FEC) data frame. When the number of data bytes in a data frame cannot be packed into one R-S codeword or when it is preferable to have two codewords to increase the error-correction capability, the data bytes are split into two consecutive R-S codewords. When this number of data bytes in the data frame is even, the first and second codeword have the same length, otherwise the first codeword is one byte longer than the second.
Further, for the G.992.1 International Telecommunication Union standard, the convolutional interleaving requires all codewords to have the same odd length. To achieve the odd codeword length, insertion of a dummy (not transmitted) data byte is required for codewords with an even length. The dummy data byte addition to the first and/or second codeword at the input of the interleaving operation is shown in Table 7-9 of section 7.6.4 of the aforementioned standard (shown as Table 1 in the present application).
TABLE 1
R-S1
R-S2
Dummy Byte Insertion Action
odd
odd
no action
even
even
Add one dummy byte at the beginning of both codewords
odd
even
Add one dummy byte at the beginning of the second
codeword
even
odd
Add one dummy byte at the beginning of the first codeword
and two dummy bytes at the beginning of the second
codeword (the de-interleaver shall insert one dummy
byte into the de-interleaver matrix on the first byte and the
(D + 1)th byte of the corresponding codeword to make the
addressing work properly)
In the G.992.1 International Telecommunication Union standard, D is always a power of 2, such that N and D can be made co-prime by adding dummy bytes according to Section 7.63 and 7.6.4. However, it is implicitly assumed in the standard that N is always larger than D. If that is not the case, which is certainly possible in some applications, the convolutional interleaving will not be done correctly using the existing rules under the following conditions: (1) There are two codewords in a DMT symbol; and (2) the length of the first codeword is even; and (3) the length of the second codeword is odd.
In view of the foregoing, an improved interleaving scheme which enables convolutional interleaving in applications which include an interleave depth larger than the codeword size.
SUMMARY OF THE INVENTION
The present invention achieves technical advantages as an apparatus and method of interleaving data frames in a digital subscriber line system in which the data frames are divided into first and second codewords such that the first codeword comprises an even number of data bytes and the second codeword comprises an odd number of data bytes. The codewords are written to a first matrix in predetermined manner with an interleaver depth (D) greater than the number of data bytes in the codewords, including the dummy bytes inserted (N), and read from the first matrix in a predetermined manner in which the data bytes of the codewords are delayed by a number of bytes. The codeword data bytes (defined by: B
0
, B
1
, . . . , B
N−1
) are delayed by an amount that varies linearly with a byte index, where byte Bi (with index i) is delayed by (D−1) x i bytes. Further, de-interleaving the interleaved data frames can be implemented by a reverse interleaving writing and reading in a second matrix.
REFERENCES:
patent: 5737337 (1998-04-01), Voith et al.
patent: 5898698 (1999-04-01), Bross
patent: 5907560 (1999-05-01), Spruyt
patent: 5983388 (1999-11-01), Friedman et al.
patent: 6151690 (2000-11-01), Peeters
patent: 6536001 (2003-03-01), Cai et al.
patent: 6546509 (2003-04-01), Starr
patent: 6625219 (2003-09-01), Stopler
patent: 6651194 (2003-11-01), Huang et al.
patent: 6654410 (2003-11-01), Tzannes
patent: 6667991 (2003-12-01), Tzannes
patent: 6670898 (2003-12-01), Lifshitz
patent: 6697975 (2004-02-01), Cameron
Baker Stephen M.
Moore J. Dennis
LandOfFree
Convolutional interleaving with interleave depth larger than... 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 interleaving with interleave depth larger than..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Convolutional interleaving with interleave depth larger than... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3333957