Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-09-23
2004-02-03
Lamarre, Guy J. (Department: 2784)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C711S217000
Reexamination Certificate
active
06687870
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to the transmission or storage of digital data, and specifically to the dispersion of redundancy in digital data for transmission or storage.
2. Description of Related Art and General Background
Digital techniques are becoming increasingly widespread in applications for the transmission or storage of information. One advantage of using digital rather than analog techniques in such applications is that once information has been generated in or transformed into digital form, it is possible to preserve it in an endless variety of different media, or to transmit it over virtually any kind of channel, as a perfect copy of the digital source. In contrast, it is essentially impossible to transmit or transfer analog information without degrading it to some extent. Some of the areas where digital techniques may be applied are voice, data, and video communications and image, data, and document storage, processing, and archiving.
Unfortunately, because storage media and transmission channels are not perfect, they tend to alter the digital information passing through them, eventually introducing errors. In a storage medium, for example, errors may arise because of defects which prevent some or all of the digital information from being properly stored, retained, or retrieved. In a transmission channel, errors may arise because of, e.g., interference from another signal or variations in channel quality due to a fading process.
In some cases, errors will have only a localized effect. For example, an error introduced into a digital representation of a picture (e.g. by a piece of dust on a CD-R blank or by a momentary deep fade in a transmission channel) may affect only one pixel or a few adjacent pixels, leaving the rest of the representation uncorrupted. In other cases, however, the introduction of a single error may be catastrophic, rendering the entire body of information unusable.
Theoretically, it is impossible to determine from the information alone what portion of it is erroneous, or even to know that an error has occurred. Therefore, digital transmission or storage operations typically introduce a redundant factor so that some degree of confidence in the accuracy of the information may be obtained upon receipt or retrieval. Common implementations of redundancy factors include parity bits and cyclic redundancy check (CRC) checksums, which are usually calculated upon blocks (also called ‘frames’) of adjacent symbols. Memory systems that incorporate parity, for example, commonly add one check bit to every eight-bit byte, while a CRC checksum is commonly appended to the block of data that it characterizes. Note that the incorporation of such factors constitutes system overhead, as it requires additional processing and also reduces the effective transmission or storage capacity of the system.
Frequently, it is not enough simply to detect errors, and some provision must be made to correct them as well. In many digital wireless communications, for example, a certain error rate is expected to be encountered. If it were necessary to retransmit all of the corrupted frames, the data throughput could be reduced so severely that the system would have little practical value. In storage applications, if data stored on an imperfect medium has been corrupted, it is possible that repeated readings would yield only the same corrupted information, and in this case the data and any other information depending on it might be irretrievably lost if the errors could not be corrected.
Therefore, enough redundancy should be provided in such applications so that data corrupted by errors at the expected rate may not only be detected but may also be corrected. Devices such as convolutional, Reed-Solomon, concatenated, or turbo codes are commonly used to provide such redundancy and are referred to in this context as forward error correction (FEC) codes. Typically, data frames are individually processed using one or more of these codes, and the resulting redundancy checksums are appended to the frames they represent.
When errors occur, they tend to corrupt a number of adjacent symbols. A defect in a storage medium will affect a number of consecutive storage locations, for example, while a deep fade in a transmission channel will distort any sequence of bits transmitted within its duration. In digital signal transmission, errors with this characteristic are called burst errors.
A high degree of redundancy may be needed to recover the information lost to a burst error, as the error may decimate a large portion of the affected data frame. During those portions of the signal where no errors occur, however, the considerable complexity and overhead incurred by incorporating a high degree of redundancy are wasted. This inefficiency arises in part because when the redundant information remains local to the data it represents, the signal continues to be susceptible to long burst errors.
One way to disperse the information redundancy and thereby increase code efficiency is through interleaving, or rearranging the sequential order of the symbols in some predetermined fashion. By spreading the redundancy across a larger set of data, interleaving makes it possible for less powerful codes to overcome the effects of a burst error. To express this concept in a different way, interleaving introduces diversity in time or space by making adjacent symbols independent in a time-variable or space-variable process (such as a fading transmission channel or storage onto an imperfect medium).
While it is desirable to obtain as much diversity in the interleaver output as possible, note that the degree of diversity provided by an interleaver is directly related to three costs: (1) the time by which the data transfer is delayed, (2) the complexity of the addressing scheme, and (3) the size of the storage space or ‘scratchpad’ needed to hold the symbols so that their sequence may be rearranged. The time delay factor may not be important in storage applications, although it becomes more of a concern in time-sensitive areas such as telephony and other communications applications. The complexity factor shrinks in importance as advances in processing speed continue to outstrip advances in memory access times. As data rates and frame lengths increase, however, the space cost is becoming more of an obstacle.
In terms of circuit area, RAM storage can be very expensive in a small device where space is limited. Moreover, it is often desirable to build an entire processing circuit including the interleaver on a single chip, in which case fabrication techniques may require that static RAM be used. Because static RAM uses more space than other RAM implementations, up to 50% or more of the available chip area may ultimately be consumed by the scratchpad.
SUMMARY OF THE INVENTION
The novel method and apparatus for interleaving as described herein performs an interleaving function on a block of data symbols, in that the block of symbols is inputted in one order and outputted in a different order. A principal advantage of the novel method and apparatus is that the interleaving function is performed using a scratchpad that is smaller than the block of symbols.
REFERENCES:
patent: 4583190 (1986-04-01), Salb
patent: 4736307 (1988-04-01), Salb
patent: 5410546 (1995-04-01), Boyer et al.
patent: 5659781 (1997-08-01), Larson
patent: 6304581 (2001-10-01), Chen et al.
patent: 6304991 (2001-10-01), Rowitch et al.
patent: 2002/0012397 (2002-01-01), De With et al.
Postula et al. (Automated synthesis of interleaved memory systems for custom computing machines; IEEE, On page(s): 115-122 vol. 1, Aug. 25-27, 1998).*
Al-Mouhamed et al. (A heuristic storage for minimizing access time of arbitrary data patterns; IEEE, On page(s): 441-447, Apr. 1997).*
Al-Mouhamed et al. (A compiler address transformation for conflict-free access of memories and networks ; IEEE, On page(s): 530-537, Oct. 23-26, 1996).*
Thapar (Interleaved dual tag directory scheme for cache coherence; IEEE, On page(s): 546-553, Jan. 4-
Butler Brian
John Deepu
Mohseni Jafar
Zhang Haitao
Brown Charles D.
Lamarre Guy J.
Qualcomm Incorporated
Seo Howard H.
Wadsworth Philip R.
LandOfFree
Method and apparatus for interleaving for information... 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 for information..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for interleaving for information... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3300086