Error detection/correction and fault detection/recovery – Pulse or data error handling – Data formatting to improve error detection correction...
Reexamination Certificate
2000-08-14
2003-11-18
Chung, Phung M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Data formatting to improve error detection correction...
C714S762000
Reexamination Certificate
active
06651194
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to a method and apparatus for interleaving an incoming stream of data blocks, more particularly a method and apparatus for interleaving an incoming stream of data blocks that are used for asymmetric digital subscriber line (ADSL) digital communication systems.
2. Description of the Related Art
In data communications systems, such as Asymmetric Digital Subscriber Lines (ADSL), noise transmission lines can cause data to be corrupted or lost. In order to correct errors and recover lost data, additional error-checking data is often transmitted along with the transmitted data (payload data). The combination of a group of payload data bytes and the error-checking data for the group payload data bytes is referred to as a codeword. The receiving end of the data transmission can determine if errors have occurred in a particular codeword based on the payload data and error-checking data received. If the amount of error or loss in a codeword is relatively small, the error-checking data can be used to recover the correct payload data. Bursts of noise on the transmission media may cause the severity of data corruption in a codeword to be such that recovery is not possible. In order to reduce the impact of these bursts of noise, data interleaving techniques can be employed. By interleaving data from different codewords before transmission and de-interleaving the received data at the receiver, the impact of a burst of noise is spread over a number of different codewords, thus reducing the loss in each codeword to a level where recovery of the payload data in each codeword is possible.
Generally, there are two types of interleaving techniques, namely block interleaving and convolutional interleaving, used in a data communication system. In ADSL G.992.1, the convolutional technique is used because of its lower memory requirement and end-to-end delay than those of block interleaving. In ADSL G.992.1, the pattern of interleaving is controlled by two parameters. The first is the number of bytes of data in each codeword, which is represented by the number (N). The second is the interleaving depth, which is represented by the number (D). Convolutional interleaving in ADSL requires that each of the N bytes B
0
, B
1
, . . . , B
N−1
in a codeword be delayed by an amount the varies linearly with the byte index. Byte B
i
(the byte of the codeword with index i) is delayed by (D−1)*i bytes.
Referring to
FIG. 1
, a table of an illustrative example (N=5, D=2) is shown, where B
j
i
denotes the i-th byte of the j-th codeword. The codeword B
j
at the first row of the table represents the original codeword before interleaving, and it is spread into an interval of two codewords after the interleaving operation. If a string of three errors, such as B
j−1
4
, B
j
2
, B
j+1
0
, occurs during data transmission, as shown at the second row of the table, the errors are spread out after de-interleaving, as shown at third row of the table.
According to the above delay rule, an amount of memory is necessary to store an incoming stream for interleaving. A codeword is stored in the memory in a specific order, and is transmitted in another order. The amount of memory required to perform the illustrated method could be up to N*D bytes in an ordinary interleaving design. In ADSL G.992.1, the maximum codeword size (N) is equal to 255, and the interleaving depth (D) can be up to 64. Thus, the amount of memory can be as large as 16K bytes. Moreover, the memory is required in both the transmitter and receiver to perform the interleaving and de-interleaving, respectively. In hardware implementation, these large memory blocks occupy relatively large die areas.
In U.S. Pat. No. 5,636,224, an amount of memory equal to about (N*D) /2 is required. In U.S. Pat. No. 5,764,649, an amount of memory equal to (N−1)*(D−1)/2 is required. However, complex operations are involved.
SUMMARY OF THE INVENTION
Therefore, the object of the present invention is to provide a method and apparatus for interleaving an incoming stream of data blocks that can reduce the amount of memory required to perform the interleaving of the incoming stream with minimum complexity.
According to one aspect of the present invention, a method is provided for interleaving an incoming stream of data blocks. The interleaving is accomplished at a predetermined interleaving depth (D) Each of the data blocks has a predetermined number (N) of block units indexed consecutively from 0 to (N−1), wherein a first one of the block units has no delay associated therewith, and subsequent ones of the block units in a designated one of the data blocks have a delay equal to (D−1) more than an immediately preceding one of the block units in the designated one of the data blocks. The method includes the steps of:
(a) configuring a data buffer to have a number of lines equal to (N−1), each of which is used to store a respective one of the 1
st
to (N−1)th block units, each of the lines having a size sufficient to accommodate a predetermined number of the block units, the predetermined number being a smallest integer equal to or larger than a quotient of the delay associated with the respective one of the 1
st
to (N−1)th block units divided by the number (N);
(b) outputting one of the block units of the incoming stream directly when the delay associated therewith is equal to zero;
(c) when the delay associated with said one of the block units of the incoming stream is not equal to zero, generating a reading index for reading one of the block units stored in the data buffer, outputting said one of the block units read from the data buffer, generating a writing index, and storing said one of the block units of the incoming stream in the respective one of the lines of the data buffer in accordance with the writing index; and
(d) repeating steps (b) and (c) for succeeding ones of the block units of the incoming stream.
According to another aspect of the present invention, a method is provided for interleaving an incoming stream of data blocks. The interleaving is accomplished at a predetermined interleaving depth (D) Each of the data blocks has a predetermined number (N) of block units indexed consecutively from 0 to (N−1), wherein a first one of the block units has no delay associated therewith, and subsequent ones of the block units in a designated one of the data blocks have a delay equal to (D−1) more than an immediately preceding one of the block units in the designated one of the data blocks. The method includes the steps of:
(a) providing a multiplexer that is connected to a data buffer and that receives the incoming stream;
(b) controlling the multiplexer to output one of the block units of the incoming stream when the delay associated therewith is equal to zero;
(c) when the delay associated with said one of the block units of the incoming stream is not equal to zero, generating a reading index for reading one of the data units stored in the data buffer, controlling the multiplexer to output said one of the block units read from the data buffer, generating a writing index, and storing said one of the block units of the incoming stream in the data buffer in accordance with the writing index; and
(d) repeating steps (b) and (c) for succeeding ones of the block units of the incoming stream.
According to still another aspect of the present invention, an apparatus is adapted for interleaving an incoming stream of data blocks. The interleaving is accomplished at a predetermined interleaving depth (d). Each of the data blocks has a predetermined number (N) of block units indexed consecutively from 0 to (N−1), wherein a first one of the block units has no delay associated therewith, and subsequent ones of the block units in a designated one of the data blocks have a delay equal to (D−1) more than an immediately preceding one of the block units in the designated one of the data blocks. The apparatus includes a data
Chen Wei-Gian
Huang Hsien-Chun
Tzou Ching-Kae
Britt Cynthia
Chung Phung M.
Ladas & Parry
Silicon Integrated Systems Corp.
LandOfFree
Method and apparatus for interleaving an incoming stream of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for interleaving an incoming stream of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for interleaving an incoming stream of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3118399