Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-05-19
2003-04-29
Ton, David (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S755000
Reexamination Certificate
active
06557137
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to compression/restoration of data using arithmetic coding, and more particularly, to a bit-error resistant arithmetic coding/decoding apparatus and method therefor.
2. Description of the Related Art
Arithmetic coding is a type of data compression/restoration technique. By using arithmetic coding, a compression efficiency close to the theoretical entropy can be obtained practically. The arithmetic coding technique is described in ‘Arithmetic Coding for Data Compression’ on pages 520-540 of “Communication of the ACM” volume 30, Number 6, published June, 1987.
By using the arithmetic coding technique, digital data is compressed into a plurality of code words. Therefore, original data can be expressed using a lesser amount of data. However, if a bit error occurs in a code word, the code word is decoded into wrong data. In addition, because all code words generated by using the arithmetic coding technique are linked to each other, bit errors occurring in a code word are propagated to the following code words.
In general, erroneous restoration of digital data could cause a serious problem. When a voice or audio signal is transmitted and errors occur in transmission, a very harsh sound can be inserted, or a digital image signal can be restored into a seriously distorted image. In order to cope with the possible occurrence of such bit errors in data transmission, a channel that transmits compressed data needs to perform additional processes, including additional encoding for detecting the occurrence of bit errors, and error correction coding for correcting bit errors, or retransmission of data having bit errors.
If data to be transmitted is formed into a plurality of independent segments in order to solve the above problems, instead of being formed into one segment in which all code words are connected, at least the propagation of bit errors among segments can be prevented. Here, the greater the number of segments, the more resistant the transmission of data is to bit-errors. However, when the existing arithmetic coding method is applied to each segment, the length of compressed data of a segment is variable, and an accurate boundary cannot be attained for each segment.
In order to solve this problem, each of the compressed code words in a segment can be formed into a different packet, for each of the segments. However, if the number of segments increases, the number of code words in a segment decreases, and the number of packets for transmitting code words increases, which increases overhead in transmitting compressed data and lowers transmission efficiency.
SUMMARY OF THE INVENTION
To solve the above problems, it is an objective of the present invention to provide an arithmetic coding/decoding apparatus and an arithmetic coding/decoding method which incorporates a compression function and resistance to bit-errors by generating a plurality of codes having a plurality of predetermined lengths in each of a plurality of segments without increasing complexity compared to the existing arithmetic encoding method.
To accomplish the above object of the present invention, there is provided a bit-error resistant arithmetic encoding apparatus for generating an encoded bit stream by compressing a plurality of input binary symbols, the arithmetic encoding apparatus having a symbol distribution unit for dividing the plurality of input binary symbols into a plurality of segments and determining the length of a code stream corresponding to each divided segment; a first encoding unit for arithmetically encoding each of the symbols of a divided segment until the encoded length of the code stream is a predetermined length, for each divided segment; a symbol accumulation unit for accumulating binary symbols that are not encoded by the first encoding unit; a second encoding unit for generating a code stream by arithmetically encoding binary symbols stored in the symbol accumulation unit until the encoded length of a code stream is a predetermined length, for each divided segment in which the encoded length of the code stream is less than the predetermined length among the segments arithmetically encoded by the first encoding unit; and a code multiplexing unit for generating the encoded bit stream by multiplexing the plurality of code streams.
It is preferable that the first encoding unit further comprises a plurality of first encoders, which operate independently to each other, each of the first encoders performs arithmetic encoding until the estimated length of a cumulative code stream of the corresponding segment becomes equal to the length of a code stream corresponding to the segment, or until binary symbols allotted to the segment are all encoded, and the second encoding unit further comprises a plurality of second encoders, which sequentially operate and respectively correspond to the plurality of segments, and each of the second encoders receives the estimated length of a cumulative code stream of the corresponding segment from the corresponding first encoders, and performs arithmetic encoding until the estimated length of a cumulative code stream becomes equal to the length of a code stream of the corresponding segment.
To accomplish another object of the present invention, there is also provided a bit-error resistant arithmetic decoding apparatus for generating a data stream of binary symbols by decoding arithmetically encoded code streams, the arithmetic decoding apparatus having a code distribution unit for determining the length of a code stream corresponding to a plurality of segments, and dividing input code streams into a plurality of segments; a first decoding unit for arithmetically decoding the divided code stream until the decoded length of the code stream is a predetermined length, for each segment; a code accumulation unit for accumulating codes which are not decoded in the first decoding unit; a second decoding unit for generating a data stream by arithmetically decoding code streams stored in the code accumulation unit until the decoded length of a code stream is a predetermined length, for each divided segement in which the decoded length of the code stream is less than the predetermined length among the segments arithmetically decoded by the first decoding unit; and a symbol multiplexing unit for generating the data stream by multiplexing the plurality of binary symbols.
It is preferable that the first decoding unit further comprises a plurality of first decoders operating independently to each other, each of the first decoders performing arithmetic decoding until the estimated length of a cumulative code stream of the corresponding segment becomes equal to the length of a code stream corresponding to the segment, or until codes allotted to the segment are all decoded, and the second decoding unit further comprises a plurality of second decoders sequentially operating and respectively corresponding to the plurality of segments, and each of the second decoders receives the estimated length of a cumulative code stream of the corresponding segment from the corresponding first decoders, and performs arithmetic decoding until the estimated length of a cumulative code stream becomes equal to the length of a code stream of the corresponding segment.
To accomplish still another object of the present invention, there is also provided a bit-error resistant arithmetic encoding method for generating a code stream by compressing input binary symbols, the arithmetic encoding method having the steps of (a) dividing input binary symbols into a plurality of segments and determining the length of a code stream corresponding to each divided segment; (b) arithmetically encoding as many divided binary symbols as the amount of the length, in bits , of a code stream corresponding to each segment, for each segment; (c) accumulating binary symbols which are not encoded in the step (b); (d) generating a plurality of code streams, by arithmetically encoding as many binary symbols accumulated in the step (c) as the length,
Kim Yeon-bae
Park Sung-hee
Seo Yang-seock
Burns Doane , Swecker, Mathis LLP
Ton David
LandOfFree
Bit-error resistant arithmetic coding/decoding apparatus 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 Bit-error resistant arithmetic coding/decoding apparatus and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bit-error resistant arithmetic coding/decoding apparatus and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3020414