Error detection/correction and fault detection/recovery – Pulse or data error handling – Error/fault detection technique
Reexamination Certificate
1999-07-12
2002-07-09
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Error/fault detection technique
C714S748000
Reexamination Certificate
active
06418549
ABSTRACT:
BACKGROUND AND FIELD OF THE INVENTION
This invention relates to data transmission using continuous error detection based on arithmetic coding.
Arithmetic coding, as used in this invention, differs considerably from other compression techniques such as prefix (Huffman) block codes. Arithmetic coding is also distinct from error control coding, which can be used to detect and rectify errors in computer operations. Arithmetic coding, generally, is a data compression technique, which sequentially encodes data or a data string by creating a code string which represents a fractional value on the number line between 0 and 1. The coding algorithm performs encoding/decoding by operations upon one data symbol per iteration. The algorithm deals with successively smaller intervals, and the code string lies in each of the nested intervals. The code-string length corresponding to the data string is equivalent to the number of bits necessary to represent the magnitude of the interval in which the code-string falls. The data string of information is recovered by using magnitude comparisons on the code-string to recreate how the encoder must have successively partitioned and retained each nested subinterval.
The use of block cyclic redundancy check (CRC) is known as a popular and powerful error detection technique in modem digital communications.
However, though efficient, CRCs can detect errors only after an entire block of data has been received and processed. This invention provides a new class of “continuous” error detection techniques, and shows its applicability in a variety of popular communication applications, including (a) data transmission based on Automatic Repeat Request (ARQ), and (b) (Serially) Concatenated Coding systems deploying an inner error-correction code and an outer error-detection code. The inventive approach is based on a popular source (entropy) coding technique, namely the arithmetic coder. The basic concept of continuous error detection based on arithmetic coding was first suggested by Boyd, et al. in a paper entitled “Integrating Error Detection into Arithmetic Coding” by C. Boyd, J. Cleary, S. Irvine, I. Rinsma-Melchert, and I. Witten, in
IEEE Transactions on Communications,
vol. 45, no. 1, Jan. 1997, albeit with little system performance analysis or exposition of its utility in communication systems. This invention presents a more rigorous analysis of this paradigm, quantifying the underlying tradeoffs involved in the process, but also establishes the impressive gains in system performance that are attainable through sophisticated integration of this novel paradigm into popular, powerful transmission applications such as those listed above.
There are several US patents which generally and severally relate to data coding, ARQ, and CRC in data transmission applications.
U.S. Pat. No. 5,530,708 to Miya teaches an error detection in data wherein the data is attached with error detection codes and then subjected to convolutional coding. The input data in Miya is subsequently subjected to an error correction Viterbi decoding operation, whereby at the time of detecting an error in the error detection code, an error detection block which has an error present therein is also detected.
U.S. Pat. No. 4,149,142 to Kageyama et al. teaches a selective automatic Request repeat (ARQ) system for controlling errors occurring in transmission of data on telephone data communication channels. Therein, an error controlling signal is devoid of a check bit for detection or correction of errors, thus obviating time loss which would occur if an error control signal was repeatedly issued between the transmission and receiving sides. The Kageyama system is useful in static image transmission.
In U.S. Pat. No. 5,715,257 to Matsuki et al., a selective repeat ARQ system with limited buffer memory is obtained by modifying a part of a user data area in a data frame. A comparison is made between a modified and an unmodified version of the user data area from the same frame number, and said part of the user data is preferably the last word area in a user data area in a frame structure.
U.S. Pat. No. 4,276,646 to Haggard et al. teaches method an apparatus for detecting errors in a data set of sequential binary digits. Initially, alternating ones of the binary digits are separated into data subsets to generate a CRC for each data subset. The code subsets are merged into a codeset. Depending on the form of the CRC generator, the code subset CRC value will indicate the presence of an error and the error location.
U.S. Pat. No. 4,718,066 to Rogard is directed to data transmission between a satellite and land mobile terminals. The system encodes data in sets of blocks including redundant symbols and redundant blocks, and provides automatic retransmission of lost data blocks, and in parallel, correction of detected errors within received blocks.
IEEE publication, “Integrating Error Detection into Arithmetic Coding” by C. Boyd, J. G. Cleary, S. A. Irvine, I. Rinsma-Melchert, and I. H. Witten in
IEEE Transactions on Communication,
vol. 45, no. 1, Jan. 1997, teaches integrating error detection into arithmetic coding. In the publication, there is a discussion of why arithmetic coding can be used for error control. The publication states that with arithmetic coding, (a) the amount of redundancy included in the encoded message can be controlled as a single tunable parameter of the coding processing, and (b) error checking can take place continuously as each input bit is processed so that errors are located quickly. As per the IEEE publication, redundancy is introduced by adjusting the coding space so that some parts are never used by the encoder. During decoding, if the number defined by the received encoded string ever enters the forbidden region, a communication error must have occurred. To adjust the coding space, at regular points in the encoding procedure, the current coding interval is reduced by a certain proportion, which is called the “reduction factor”. Upon decoding, the same reduction process is performed. The number defined by the received string is checked after each reduction to see if it lies within the received interval. If not, an error has occurred. Redundancy is controlled by varying the “reduction factor”. Another method of adding redundancy is to use an extra model with only two symbols, encoding one of them periodically, and signaling an error if the other is ever decoded. The publication also discusses choosing the reduction factor, guaranteeing detection of single bit errors, and the use of end of file markers.
SUMMARY OF THE INVENTION
An object of this invention generally, is to provide continuous error checking in the transmission of data from a transmitter to a receiver, wherein, there is no need to wait for error checking until a complete block of data is transmitted.
In one aspect, the invention resides in a method of data-transmission from a transmitter to a receiver using an arithmetic coder without using cyclic redundancy check codes, comprising adding a forbidden symbol, which occupies &egr;-th portion of a coding space to a data stream of said data to increase redundancy, said forbidden symbol not being meant to be coded, controlling said coding space as necessary to control the redundancy, tracking if said forbidden symbol is decoded at the receiver and using a presence of such forbidden symbol decoding for error detection in said data transmission, conveying a position of an error to the transmitter, and requesting a retransmission of n bits where n is related to a confidence level whereby continuous error detection in said data transmission is performed with automatic repeat request.
In another aspect, the invention provides a method of transmitting data with continuous error detection in a received data bitstream, using a serially concatenated coding scheme with an inner convolutional coder and outer error detection coder by employing Viterbi Algorithms (VA), comprising changing the VA to produce an ordered list of N most likely transmitted codewords for a list N VA,
Chou Jim
Kozintsev Igor
Ramchandran Kannan
Chase Shelly A
De'cady Albert
Hamilton Brook Smith & Reynolds P.C.
Merunetworks, Inc.
LandOfFree
Data transmission using arithmetic coding based continuous... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data transmission using arithmetic coding based continuous..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data transmission using arithmetic coding based continuous... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2879629