Coded data generation or conversion – Digital code to digital code converters – To or from variable length codes
Reexamination Certificate
1998-04-17
2001-04-03
Wamsley, Patrick (Department: 2731)
Coded data generation or conversion
Digital code to digital code converters
To or from variable length codes
C341S081000
Reexamination Certificate
active
06211801
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to communication systems, and particularly to communication arrangements and methods benefiting from variable length coding.
BACKGROUND OF THE INVENTION
The widespread use of digital processing technology has found its way into a variety of equipment and, in some form, into most industries. In many applications, digital processing technology involves the communication of information in coded form. The information to be sent is first translated to a set of code words and then the information is sent as a sequence of code words over a communications channel for decoding at another terminal.
For effective use of the communications channel, selection of the correct coding scheme can be particularly important. Some coding schemes can be implemented using a relatively small amount of data information and, in many instances, permit effective data compression. For communication environments that are susceptible to various types of interference, however, many seemingly efficient data coding schemes become intolerable. For instance, in a data coding scheme involving synchronization of data bits between the transmitting and receiving terminals, interference such as noise can result in loss of synchronization and require retransmission of the data. The retransmission frustrates the object of being an efficient data coding scheme.
There have been many attempts to develop an efficient data coding scheme that permits some degree of interference without requiring retransmission. Many of these efforts concern variable length coding. Variable length coding, as the name suggests, involves assigning code words of different lengths to the symbols to be transmitted. This type of coding is founded on the observation that space can be saved if the short code words are assigned to the most commonly used symbols. An early example of this coding type is the Morse code, where more frequently-used English letters are assigned a short representation (e.g., e=“·”) and less frequently-used letters are assigned a longer representation (e.g., p=“·- -·”).
Another example of variable length coding is the Huffman algorithm. The Huffman algorithm takes into account the probability of each symbol and then assigns variable length codes to them in a manner that minimizes the average code word length. The Huffman code words are all variable length strings of ones and zeros, with the underlying rule that no code word for one symbol is a prefix for the code word of another symbol. Accordingly, variable length coding schemes are designed so that the symbols can be uniquely decoded symbol by symbol, by parsing the concatenation of prefix code words in the forward direction.
The International Telecommunications Union (ITU) recently adopted a reverse variable length coding (RLVC) scheme for use in the H.263+ video compression standard. Reverse variable length coding refers to variable length codes that can be uniquely decoded in two directions. An advantage of decoding from both ends of the transmission sequence is the ability to increase tolerance for errors. A bit error in the middle of the sequence, for example, might prevent decoding beyond the point of the error. Using a RVLC scheme, however, the sequence can be decoded from one end up to the point of the error and then from the other end up to the point of the error. By decoding in this manner, RVLCs increase the tolerance of transmission interference, thereby decreasing the need for retransmission and extensive error-correcting algorithms.
The potential applications for reverse and conventional variable length coding schemes are diverse and, for many applications, it is important to maintain a relatively high degree of tolerance for transmission interference and to minimize the size (e.g., bit length) of the codes for efficiency. Tolerance for transmission interference is typically increased by adding verification or error-correcting data to the transmission sequence. A decoder at the receiving end then uses this added data for integrity verification or for error correction. Unfortunately, these two objectives are inconsistent. By adding the verification or error-correcting data to increase tolerance for transmission errors, the effective size of the codes transmitted is increased rather than minimized.
SUMMARY OF THE INVENTION
The present invention is directed to methods and arrangements of variable length coding for use in data communication applications.
One particular embodiment of the present invention is directed to an arrangement for coding and decoding data representing symbols as uniquely decodable code words having a maximum code word length. The arrangement provides for variable length coding in a Huffman decoder, such as the one referred to above. This arrangement is advantageous in that it permits highly efficient communication for relatively long blocks of data. The arrangement also provides for reverse variable length coding, in which the encoded symbols can be decoded in two directions.
Another particular embodiment of the present invention is a method of communicating data representing symbols as uniquely decodable code words having a maximum code word length. The method involves using a resultant bitstream over a communications channel to communicate the symbols, with the resultant bitstream provided by EXORing a first bitstream and a second bitstream. The first bitstream represents the sequence of symbols by a sequence of prefix code words and the second bitstream represents the same sequence of symbols by a sequence of suffix code words, delayed at least by the maximum code word length.
Other aspects of the present invention concern arrangements for implementing methods of communicating data in manners consistent with the above characterization.
The above summary of the invention is not intended to describe each disclosed embodiment of the present invention. An overview of other example aspects and implementations will be recognizable from the figures and of the detailed description that follows.
REFERENCES:
patent: 5654704 (1997-08-01), Tayama
patent: 5852469 (1998-12-01), Nagai et al.
patent: 5883589 (1999-03-01), Takishima et al.
Cheung, “Quantization Error in Ternary Delta Modulation Schemes,” IEEE, 1990.*
Panchanathan et al, “A Systolic Array Architecture for Image Coding Using Adaptice Vector Quantization,” IEEE, 1991.
Crawford PLLC
Netergy Networks
Wamsley Patrick
LandOfFree
Data communication arrangement having variable length coding... 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 communication arrangement having variable length coding..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data communication arrangement having variable length coding... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2499268