US 5,311,177 AGranted

Code transmitting apparatus with limited carry propagation

AssigneeMitsubishi Denki Kabushiki Kaisha

InventorsTomohiro Kimura, Fumitaka Ono, Masayuki Yoshida, Shigenori Kino

Life of this patent

Estimating the term…

Loading patent…

Abstract

Although data is transmitted with efficiency by an arithmetic encoding system, the number of carry control signals increases in proportion to the number of consecutive bits "1" s or bytes X`FF` s in a conventional system. In the present invention, an arithmetic encoder 302 `detects the possibility of a carry generated during arithmetic coding operation being propagated beyond at least a predetermined number of consecutive bytes X`FF` s in a supplied arithmetic code 315. When the propagation of the carry is impossible, a carry control signal is inserted into the first 2 bits of the byte other than X`FF` which occurs immediately after the consecutive bytes X`FF` s so as to transmit the presence or absence of a carry. An arithmetic decoder 303 detects the continuation of at least a predetermined number of bytes X`FF` s in the arithmetic code 315, and arithmetically decodes an output value YN316 on the basis of the predicted value MPS317 of the occurrence probability of the output value YN316 to be encoded and the region width Qe of the complementary predicted value LPS. Since the number of total bits of the inserted carry control signals is reduced by this "one-time 2-bits insertion system", the total number of transmitted code bits is also reduced.

A code transmitting apparatus comprising:

a) an arithmetic encoding means for dividing an effective region width A on a probability number line into the region width A(0) of a more probable symbol (MPS) and the region width A(1) of a less probable symbol (LPS) in accordance with an occurrence probability ratio whenever a symbol of a symbol stream which is supplied from an information source is encoded, for updating a current lower boundary value CR of said effective region width A to a value obtained by adding A(1) thereto and said A to said A(0) when said symbol is a more probable symbol (MPS), while maintaining said CR as is and updating said A to said A(1) when said symbol is a less probable symbol (LPS), and for repeating the dividing and updating processes until the final bit of said symbol stream to serially supply an encoded signal and a carry signal;
b) an arithmetic decoding means for dividing A into A(0) and A(1) in the same process as by said arithmetic encoding means whenever the encoded symbol stream is decoded into the corresponding symbol, for decoding a code into a more probable symbol (MPS), and for updating a predetermined first plurality of digits DR at the left of the decoding bit of said code to the value with said A(1) subtracted therefrom and said A to said A(0) when said DR is not smaller than said A(1), while decoding said code into a less probable symbol (LPS), maintaining said DR at the current value and also updating said A to said A(1) when said Dr is smaller than said A(1), and repeating the dividing and updating processes until the final bit of said encoded symbol stream to serially generate a decoded symbol stream and to control the propagation of a carry by a control bit detection signal;
c) a carry transmission control means of one-time 2-bits insertion system for monitoring said encoded signal and said carry signal supplied from said arithmetic encoding means, for inserting two carry propagation absorbing control bits including of a first bit "0" which indicates the end of the continuation of code bits 1's and a second bit "1" or "0" which indicates the presence or absence of a carry from the adjacent digit immediately after the end of the continuation of at least a predetermined number of code bits 1's, and for supplying a code bit stream obtained by the insertion to a transmission path;
and
d) a carry reception control means for a one-time 2-bits insertion system for monitoring said code bit stream supplied from said transmission path, for detecting said carry propagation absorbing control bits "00" or "01" immediately after the end of the continuation of at least a predetermined number of code bits 1's, and for supplying a decoded signal and said control bit detection signal in accordance with said carry propagation absorbing control bits.

2 more elements

Abstract

Claims18