In data communications systems such as Asymmetric Digital Subscriber Lines (ADSL), noisy 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 of 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.
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 depth of interleaving to be performed, which is represented by the number D. Convolutional interleaving in ADSL requires that each of the N bytes B.sub.0, B.sub.1, . . . , B.sub.N-1 in a codeword be delayed by an amount that varies linearly with the byte index. Byte B.sub.i (the byte of the codeword with index i) is delayed by (D-1)*i bytes, where D is the interleave depth.
In order to interleave a data stream, memory is required to store the data from multiple codewords before transmission. If a particular byte is to be delayed by 20 bytes, the particular byte must be stored in memory for the next 20 transmissions before its turn to be transmitted arises. In one prior art technique described in the ADSL standard, data is stored in memory in interleaved form and transmitted when completed interleaved codewords become available. The amount of memory required to perform the interleave function is equal to N*D bytes. It can be seen that as the number of bytes in a codeword and/or the depth of interleaving increases, the amount of memory required to store the interleaved data increases dramatically. Note that an equivalent amount of memory is required in the de-interleaver of the receiver, as data for different codewords will have to be stored until each de-interleaved codeword is complete.
The American National Standards Institute (ANSI) T1E1.4 (ADSL) committee has determined the parameters in an ADSL system regarding the size of each codeword (N) and the depth of interleaving (D). In a particular ADSL example, the size of each codeword (N) may be equal to 255 bytes, and the depth of interleaving (D) equal to 64.
Certain parameters of an ADSL system may be varied by the user, and it is desirable for ADSL transceivers to support these different parameters without adding system cost. One such parameter is the number of frames in a codeword, designated by the variable S. The S value is user selectable and is dependent on the number of payload bytes in a frame and the maximum size of a codeword. As a result of forward error correction, a group of redundancy bytes are added to the S frames of payload data to form a codeword having a length of N bytes, which equals the number of redundancy bytes (R) plus the aggregate number of basic data bytes (K) for the S frames of data. The number of redundancy bytes is chosen to provide a desirable amount of error correction at the receiver. The movement of data bytes during interleaving and de-interleaving occurs in a different order as S varies, adding substantial complexity to the interleaving/de-interleaving task.
What is needed, then, is a method for interleaving and de-interleaving data which may be altered for changes in system parameters without adding significant circuit area. The present invention provides such a method and circuitry which uses this method, and its features and advantages will be more clearly understood from the following detailed description taken in conjunction with the accompanying drawings.