JPH0685684A - Binary arithmetic encoder - Google Patents

Abstract

PURPOSE:To reduce the number of times of a detecting operation for arrangement of '1' by providing a function to judge the presence/absence of possibility in which a constant number of arrangement of '1' appear in a register in a process to encode a constant number of bits. CONSTITUTION:Output from the register 2 in which an output bit is accumulated to a buffet 6 is controlled by a controller 5. The bit pattern of the register 2 in the case that the possibility where the constant number of arrangement of '1' appear in the register 2 in the process to encode the constant number of bits in the following operation exists, is held in a table 7. Thereby, it is possible to dispense with the detecting operation of the arrangement of '1' while the constant number of bits are encoded in the following operation depending on a result comparing the bit patterns in the table 7 in accordance with the register 2 by the controller 5.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a binary arithmetic encoder for encoding a binary arithmetic code which is a distortion-free data compression technique.

[0002]

2. Description of the Related Art The binary arithmetic encoder proposed by Langdon is shown in FIG. 3 (IBM, Journal of Research and Development, 28 (2), 135-.
149, 1984). In FIG. 3, reference numeral 11 denotes a prediction bit ('0' or '1') for predicting whether the next input bit is '0' or '1' and a probability (2 ^-k form) that the prediction bit does not appear. A table that stores a set of values (K),
12 is a register that stores output bits, 13 is a register that represents the main part of the appearance probability value of the input sequence up to the encoding point,
Reference numeral 14 is a processor that controls the central operation of encoding for performing subtraction and shift in the register 12 and addition and shift in the register 3, and 15 is a controller for controlling the output from the register 12 to the buffer 16. is there.

In order to encode the next input bit, it is determined from the past input bit string which set in the table 11 is to be used. Based on the result of comparing the expected bit and the actual input bit, the processor 14 adds "1" to the lower digit of the register 12 according to K or shifts it by K, and outputs K to the register 13. Decrease the digit from "1" by "1" or reset. Register 13
When the highest-order bit of the register 13 becomes "0" as a result of subtraction, the register 13 is shifted by 1 bit so that the highest-order bit becomes "1". At this time, the register 12 is also shifted by 1 bit. To do. If necessary, the expected bit or probability value (K) in the subsequent table 1 is rewritten. The above flow is shown in a flow chart in FIG.

The controller 15 moves from the register 12 to the buffer 1
Although the output to 6 is controlled, if output is performed in byte units, for example, it is necessary to prevent the output byte from being affected by carry due to addition to the register 12. Then, when '1' continues in the register 12 endlessly, the output to the buffer 16 cannot be made forever, and the length of the register 12 must be infinite.
The delay in the coding time becomes great. To avoid this, check the register 12 for each byte delimiter from the beginning to see if all the bits in each byte are '1', and if so, after the 1 byte sequence of '1''
By inserting a few bits of 0 ', carry propagation can be stopped there, and a byte of all'1's was output from register 2 to buffer 6.

[0005]

In order to increase the speed by encoding binary arithmetic encoding with bit serial up to now by parallel encoding several bits, the output in the case of parallel has been output from before. It is hoped that it will be an exact match and compatible with the case of the known bit serial.
At that time, the problem is that when the sequence of '1' appears in the register 13 in FIG. 3, which is described at the end of the section "Conventional method", "0" is inserted. In other words, if you are encoding in parallel, you should insert "0" if you originally encoded in bit serial depending on the number of the bit, but since it is left in parallel, it does not occur in the case of bit serial. Carrying may occur, resulting in different output results. However, if the arrangement of '1's is detected for each input bit, the encoding speed cannot be increased even if parallelization is carried out.

[0006]

The binary arithmetic encoder of the present invention is a binary arithmetic encoder which is a distortion-free data compression device and is output as a result of encoding which is a part of the encoder. A function for controlling the output from the register by judging from the current state of the register whether or not there is a possibility that a sequence of 1s of a constant length may appear in a register that stores bits in a certain number of bits. It is characterized by being provided.

[0007]

By pre-determining whether a sequence of '1's may appear while encoding a fixed number of input bits, the output bit is encoded each time 1 bit is encoded only when there is a possibility. It is possible to observe whether the sequence of '1' appears in the register to be stored, and if not, skip the sequence of 1's during that time. Thus, if the process of detecting the sequence of '1's in the register is reduced,
Higher coding speed can be expected. Particularly, when the parallel processing is performed, the output data can be matched with the case where the output data is processed by bit serial while maintaining high speed.

[0008]

DESCRIPTION OF THE PREFERRED EMBODIMENTS FIG. 1 is an example for realizing such an invention, and shows a case of encoding in 4-bit parallel.
The table 7 holds the pattern of the bit string of the register 3 when there is a possibility that all of the 1 byte in the byte unit from the beginning of the register 3 may become "1" in the process of encoding the next 4 bits. Then, by matching with the bit string in the register 3, it is determined whether or not to detect the arrangement of '1's in the process of encoding the next 4 bits. It is assumed that the output from the register 2 to the buffer 6 is performed in byte unit when 20 bits or more are stored in the register 2 so that there is no carry carry effect.

For example, consider the following situation. If the input bit and the expected bit are equal, 1 is added to any digit from the least significant digit to the upper 4 digits of register 3, and 1 is subtracted from register 2 accordingly, while If the expected bits are not equal, the register 3 is shifted according to the probability value, and the register 2 is reset so that the highest digit is 1 and the remaining digits are 0.
Register 2 may be 5 bits. As shown in FIG. 4, a pattern corresponding to the number n of bits currently in the register 2 is registered in the table 7.

The register 2 and the pattern of FIG. 4 are collated each time 4-bit encoding is completed. The bit pattern of register 2 is compared with the part other than ** in FIG. 4, but if the bit pattern of register 2 is smaller than the pattern of FIG.
It can be coded at once in 4-bit parallel. If it is larger than the pattern of FIG. 4, this time is essentially the same as the case of encoding by bit serial, and every time when encoding each bit in 4 bits, the sequence of '1' is detected, When a sequence of 1's for 1 byte appears, output from register 2 to buffer 6 and at the beginning of register 2 '
Insert 0 '. The process of this output control is shown in the flowchart of FIG.

[0011]

In the embodiment, when it is considered that "0" and "1" appear at random in the register 2 of FIG. 1 (in many cases, this can often be the case), the sequence of 1s is detected. You have to do it once every 10 times. In other words, with the conventional method, it was necessary to check 1 sequence of 1s in the register 12 40 times when encoding in 4-bit parallel 10 times, but in the method proposed this time, it is 14 times to check the register 2. Only about 30% of the conventional number of times is required.

[Brief description of drawings]

FIG. 1 is a block diagram showing the configuration of an embodiment of a binary arithmetic encoder of the present invention.

FIG. 2 is a flowchart showing an algorithm of binary arithmetic code.

FIG. 3 is a block diagram showing a configuration of an embodiment of a conventional binary arithmetic encoder.

FIG. 4 is a content of a table holding a bit pattern to be matched with the output bit register 2

5 is a flowchart showing a process of output control at the time of 4-bit parallel encoding using the table of FIG.

[Explanation of symbols]

1, 11 Table holding a pair of prediction bit and probability value (K) 2, 12 Register for storing output bit 3, 13 Register representing the main part of the probability value of the previous part of the input sequence 4, 14 Register 3, 13, a processor 2,15 which controls the operations to the registers 2 and 12 and the tables 1 and 11 A controller 7 which controls the output from the registers 2 and 12 to the buffers 6 and 16 A bit pattern for matching with the bit string of the register 2 Holding table 8 serial-parallel converter

Claims (1)

[Claims] 1. A binary arithmetic encoder which is a distortionless data compression apparatus, wherein a register, which is a part of the encoder, stores a bit output as a result of encoding, and encodes a fixed number of bits. A binary arithmetic encoder having a function of controlling the output from the register by judging from the current state of the register whether or not there is a possibility that a sequence of 1's of a certain length will appear in the register.