Coded data generation or conversion – Digital code to digital code converters – To or from interleaved format
Reexamination Certificate
2000-08-24
2003-12-30
Dildine, R. Stephen (Department: 2133)
Coded data generation or conversion
Digital code to digital code converters
To or from interleaved format
C714S701000
Reexamination Certificate
active
06670898
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the field of data communications and in particular to a method and system for interleaving and de-interleaving data in a data communications system.
BACKGROUND OF THE INVENTION
Digital data communication systems are commonly used to transmit and receive data transmitted between remote transmitting and receiving locations. A central facet of any data communications system is the reliability and integrity of the data communicated. Ideally, the data, received at the receiving location should be identical to the data transmitted from the transmitting location. Practically however, a noisy transmission medium can cause the data which is being received to be corrupted or lost with respect to the originally transmitted data.
Early data communications systems utilized simple error detection and correction schemes to compensate for noise on a communications medium. A widely utilized method of error detection included the use of a parity bit in each block of transmitted data to indicate whether the particular block contained an odd or even number of high bits, i.e., bits equal to one. By determining whether the total number of high bits was even or odd and comparing the result to the value of the parity bit, a data receiver determined if the transmitted data blocks contained errors. This relatively simple scheme has numerous disadvantages such as its ability to detect only one inaccurate bit in a data block. Moreover, parity bit error detection cannot be used to correct a bit in error. Upon receiving a bit in error, a data receiver using parity bit error detection is limited to requesting retransmission of the data block in error from a data transmitter.
Other early methods and systems for error detection and correction included the use of a voting consensus circuit. Using a voting consensus circuit, a data transmitter transmitted a single data block multiple times to a data receiver. A data receiver included a voting circuit that would compare the multiple received versions of the same data block transmitted by the data transmitter and determine which, if any, of the transmitted data blocks was the correct, i.e., non-corrupted, data block. While a voting circuit reduced the number of retransmission requests issued by a transmitter as compared to a system utilizing parity bits, a voting consensus circuit system suffered from speed and throughput constraints due to repeated transmission of the same data.
The above-mentioned error correction and detection schemes are examples of binary block codes. More particularly, an (n,k,d) binary block code includes a series of 2
k
binary codewords of block length n and minimum distance d, i.e., coding distance. Using binary block codes, a datastream to be transmitted is partitioned into binary blocks of length k which are then mapped into binary codewords of length n and then modulated and transmitted through a communication medium. As is known in the art, these schemes are limited to correcting up to (d−1)/2 bit errors within each codeword.
The limitations of the above-described systems become evident when considering the nature of noisy transmission media. Frequently, noise in a communications medium occurs in non-frequent bursts. Thus, where blocks of data are transmitted in sequence, a burst of noise may corrupt a block of data beyond the capabilities of the above-mentioned schemes to correct the errors, i.e., a burst of noise may corrupt more than (d−1)/2 bits of data in a codeword, thus rendering error correction schemes, such as those described above, ineffective.
Interleaver/de-interleaver systems have been developed to address and compensate for the effects of noise bursts over transmission media. An interleaver accepts a datastream to be transmitted and interleaves or co-mingles the data from several codewords in a predetermined manner such that the co-mingled data can be re-organized and the datastream reconstructed by a de-interleaver at the receiving end. In other words, instead of transmitting a succession of complete codewords, the interleaver transmits a portion (also referred to as a symbol), e.g., a byte, of a first codeword then transmits a portion of a second codeword and so on. By processing a datastream through an interleaver before it is modulated and transmitted through a communications media or channel, the effects of non-periodic noise bursts are minimized because noise encountered in the transmission medium is distributed among several codewords of the reconstructed or de-interleaved datastream.
An interleaver/de-interleaver system requires two known values, the total number of symbols (N) in each codeword of the non-interleaved datastream and the depth (D) of the interleaver. The size of a symbol is measured in bits and is preferably equal to one byte, i.e., eight bits. The depth of the interleave (D) represents the total number of non-interleaved codewords that are represented in any one interleaved codeword.
Viewing a simple interleaver/de-interleaver system logically, the symbols of the datastream to be transmitted are written to an (N,D) two dimensional memory of the interleaver in columns and are read out from the two dimensional memory of the interleaver in rows. The write and read operations are performed in groups of symbols rather than being alternated between each symbol. This type of interleaving is known in the art as block interleaving and introduces a latency in transmission of one (N*D) block at the interleaver. Furthermore, block interleaving requires two blocks of memory (2*N*D) at the interleaver and two blocks of memory (2*N*D) at the de-interleaver.
Thus, it can be seen from the above description of block interleaving that an interleaver/de-interleaver system requires memory storage units to store symbols at both the transmitting (interleaving) end and the receiving (de-interleaving) end of the transmission medium. Because the codewords in an interleaved datastream are not arranged in the same sequential time order as the non-interleaved datastream, an interleaver requires a sufficient amount of memory to store the input symbols of the non-interleaved codewords which are not immediately transmitted in the interleaved datastream. Similarly, a de-interleaver requires a sufficient amount of memory to store the input symbols of the interleaved codewords which are not immediately placed into the non-interleaved datastream. Memory requirements are, therefore, an important factor to be considered in designing interleaver/de-interleaver systems.
One type of prior art interleaver/de-interleaver system and method which reduces the amount of necessary memory over that required in block interleaving is a convolutional interleaver/de-interleaver system and method disclosed by John L. Ramsey in “Realization of Optimum Interleaver”,
I.E.E.E. Transactions on Information Theory
, Vol. IT-16, No. 3, May 1970, which is hereby incorporated herein by reference in its entirety. In convolutional interleaving and de-interleaving, the write and read operations of the interleaver and de-interleaver are alternated on a symbol basis rather than being carried out in groups of symbols as in block interleaving.
Each of the convolutional interleaving techniques described by Ramsey utilizes a tapped shift register and a commutator to accomplish the convolutional interleaving described therein. More particularly, four techniques for convolutional interleaving are described by Ramsey. As discussed therein, the convolutional techniques known in the art at that time, although achieving minimum possible end to end latency, were wasteful of storage insofar as, during the interleaving process, many of the symbols stored in later shift register stages were already read into the output sequence of the convolutional interleaver. Ramsey described a technique of reducing the required storage capacity of a convolutional interleaver without changing the functionality of the convolutional interleaver. Furthermore, the convolutional interleaver disclosed by Ramsey reduce
Darby & Darby
Dildine R. Stephen
Tioga Technologies Ltd.
LandOfFree
Efficient method and apparatus for interleaving and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient method and apparatus for interleaving and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient method and apparatus for interleaving and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3158967