JPH0548971B2 - - Google Patents

Description

[Detailed Description of the Invention] <Industrial Application Field> The present invention compresses digital data by removing redundancy included in the data when transmitting or storing the data.
The present invention relates to a data compression encoding device that saves transmission time or storage capacity.

<Prior Art> A method using arithmetic codes is a well-known and commonly used method for compressing redundant data and restoring original redundant data from compressed data. For details on the arithmetic code data compression encoding device (device that compresses data; hereinafter also simply referred to as the encoding device) and data compression/decoding device (device that restores data; hereinafter also simply referred to as the decoding device), , for example, International Business Machines Corporation in the United States.
The journal IBM Journal of Research and Development was published in 1976 by IBM Corporation.
Development) Vol. 20, No. 3, pages 198-203, and Vol. 28, No. 2 of the same magazine, published in 1984, pages 135-149.
Page and Stanford University in the United States.
The doctoral dissertation by Richard Clark Pasco, published in 1976 at the University of California, Source Coding Algorithms and First Data Compression (Source
coding algorithms for fast data
compression)”.

Of these methods, _the method for compressing data can be briefly described as _follows :
. . , x _N are converted into code digit strings W ₁ , W _{2 .}

First, let F be the value at the smaller end (ie, 0) of a predetermined interval on a number line (between 0 and less than 1), and T be the width of that interval (ie, 1). Next, execute steps A1) to A5) below. Note that in the following, x⇒y indicates that the value of y is substituted for x. Also, all operations are b
It shall be done in hexadecimal format.

Let the value of A1 i be 1.

A2 Input the i-th information digit x _i .

A3 Probability of appearance q _i of the i-th information digit x _i
(x _i ) and cumulative
Find the probability of appearance C _i (x _i ) = y<xi qi (y).

A4 F⇒F+C _i (x _i )・T T ⇒ q _i (x _i )・T, and T is truncated at a predetermined K significant digits.

A5 If i<N, increase the value of i by 1 and move to A2).

If i=N, end.

Finally, from among the real numbers included in the interval determined by the final values of F and T, choose a real number that has the smallest number of digits when expressed numerically, and use the representation digit of the selected implementation as 0.W ₁ W ₂ ...W _L Sign digit string W ₁ ,
Defined as W ₂ …, W _L. Note that the following notation will be used below for convenience of explanation.

T=A・b ^- 〓 A=0.t ₁ t ₂ ...t _l (A) F=(F1+F2)・b ^- 〓 F1=f _1,1 , f _1,2 ...f _1,l (F ₁ ) F2=0.f _2,1 , f _2,2 …f _2,l (F ₂ ) Here, l(A), l(F1), l(F2) are the representation digit numbers of A, F1, F2, respectively. represent. In addition, in the initial state (that is, when the encoding device is initialized with F set to 0 and T set to 1), t ₁
It is assumed that it is set as ≠0. Then, the above-mentioned step A4) can be expressed as follows.

A4.1 If F2+C _i (x _i )・A1, execute F1⇒F1+1.

A4.2 F2⇒f _rac (F2+C _i (x _i )・A).

Here, f _rac (x) is a function that gives a value below the decimal point of x.

A4.3 Let A⇒q _i (x _i )・A.

A4.4 If t ₁ = 0, F1⇒b・F1+f _2,1 F2⇒f _rac (b・F2) A⇒b・A τ⇒τ+1.

A4.5 If t ₁ = 0, move to A4.4).

Otherwise, move on.

A4.6 K+1 decimal place of A t _K+1 , t _K+2 ,...
will be discontinued.

If you follow the steps A1) to A5) above, the length of the code word is L.
It is shown in the above-mentioned literature that the length N of the information digit string is generally smaller than the length N of the information digit string so that data can be compressed.

On the other hand, to briefly describe the method for restoring data, the code digit sequence W ₁ , W ₂ , ..., W _L is converted as follows, for example, and the original information digit sequence x ₁ , x ₂ , ..., x _N is restored.

First, assign 0.W ₁ , W ₂ ,...W _L to W, and set 1 to S.
Substitute. Next, execute steps B1) to B5) below. Note that in the following, x⇒y indicates that the value of y is substituted for x. It is also assumed that all operations are performed in the b-adic system.

Let the value of B1 i be 1.

B2 C _i (y) Let x _i be the largest digit among y that satisfies W/S.

Output B3 x _i as a restored information digit.

B4 W⇒W−C _i (x _i )・S S ⇒ q _i (x _i )・S, and S is truncated at a predetermined significant number K digits.

B5 If i<N, increase the value of i by 1 and move to B2).

If I=N, it ends.

Note that the following notation will be used below for convenience of explanation.

S=B・b ^- 〓 B=0.S ₁ S ₂ ...S _l(B) W=(W1+W2)・b ^- 〓 W1=W _1,1 , W _1,2 ...W _1,l(W1) W2 =0.W _2,1 , W _2,2 . . . W _2,l(W2) where l(B), l(W1), and l(W2) represent the representation digit numbers of B, W1, and W2, respectively. In addition, the initial state (i.e., W is 0.W ₁ , W ₂ ...W _L , S
When initializing the decoding device with 1)
In this case, it is assumed that S ₁ ≠0.

Then, the above-mentioned step B2) can be expressed as follows.

Let x _i be the largest digit among y that satisfies A2 C _i (y)⇒(W1+W2)/B.

Further, step B4) is expressed as follows.

B4.1 If W2-C _i (x _i )・B<0, execute W1⇒W1-1 W2⇒(1.0+W2)-C _i (x _i )・B. Otherwise, execute W2⇒W2−C _i (x _i )・B.

B4.2 Let B⇒q _i (x _i )・B.

B4.3 If S ₁ = 0, then W1⇒b・W1+W _2,1 W2⇒f _rac (b・W2) B⇒b・B δ⇒δ+1.

B4.4 If S ₁ = 0, move to B4.3).

Otherwise, move on.

B4.5 K+1 decimal place of B S _K+1 , S _K+2 ,
...is discontinued.

The above-mentioned document shows that the original information digit strings x ₁ , x ₂ , ..., x _N can be reconstructed without error from the code digit strings W ₁ , W ₂ , ..., W _L by following the above steps B1) to B5). has been done.

In addition, the above steps A1) to A5) and B1) to B5)
The above-mentioned literature shows that the above-mentioned method has properties that are convenient for deviceization, such as those described below. The first point is that it can be designed flexibly depending on the purpose of use. That is, in the above procedure, the length N of the information digit string is set to a predetermined constant value,
On the other hand, the length L of the code digit string was set to a value determined depending on the redundancy of the information digit string, but conversely, the length L
It is also possible to take a predetermined constant value and N to take a value determined depending on the redundancy of the information digit string. To do this, steps A5) and B5) may be modified as follows.

If A5′ τ<L−J, increase the value of i by 1 and use A2)
Move to. If τ=L-J, end.

If B5′ δ<L−J, increase the value of i by 1 B2)
Move to. If δ=L−J, end.

Here, J is the number of significant digits of q _i (o) and C _i (o).
However, in both cases, the only difference is the criteria for terminating encoding/decoding, and the configuration of the devices is the same. Therefore, in the following explanation, for convenience, the length N of the information digit string is assumed to be a constant value, while the length L of the code digit string is assumed to be a constant value. Let be a value determined depending on the redundancy of the information digit string. The second point is that if the length N of the information digit string is made sufficiently large, the compression efficiency will improve and almost reach the theoretical limit. Finally, the third point is
The point is that the code digits can be sequentially output in the above steps A1) to A5). That is, according to the above literature, once a carry occurs in the operation F1⇒F1+1 in step A4.1), the carry will not propagate again to a higher-order digit than the range in which the carry propagated (for example, b=2). (When F1 = 10101111, the carry never propagates to the upper 3 bits of F1 101), so the high-order code digits in which the carry does not propagate are sequentially output before the encoding of all information digits is completed. I can go. For example, when b=2 and F1=10101111, F1
Since the carry never propagates to the upper 3 bits 101 of , the upper 3 bits 101 can be output as a code digit.

Now, a data compression encoding device and a data compression decoding device for compressing data and restoring data as described above are described in, for example, U.S. Patent No. 4122440 of International Business Machines Corporation in the United States. It can be realized with a circuit that includes arithmetic operation circuits such as addition and multiplication.

Of course, even though it is possible to output the code digits sequentially, for example, when F1 = 0111111, when F1⇒F1+1 is executed in step A1), the carry propagates to the most significant digit, so the code digits cannot be output sequentially. Can not. In other words, since the length of carry propagation is not constant, the encoding delay becomes large if 1's appear consecutively in the code digit.

For this reason, in order to apply arithmetic codes to applications that require small coding delays, it is necessary to control carry propagation. Sometimes, by dividing the width of the interval by b, the operation F1⇒F1 in step A4.1) above
A method has been used to prevent +1 from being executed and to control the length of carry propagation to a certain length or less. Specifically, as an encoding method, the above-mentioned step A4)
and A5) with the following steps added.

A.B All lower M digits of F1 are b-1
If so, then move on to A. D).

A. B F1⇒b・F1+f _2,1 F2⇒f _rac (b・F2) τ⇒τ+1 A.H A.B).

A. D Move on to the next one.

Here, M is a predetermined value, and if you want the carry propagation length to be less than 10 digits, M =
Set it to 10. This operation converts the contents of the registers containing the representation digits of F1 and F2 into M b
This is equivalent to shifting the -1s toward higher levels until they are no longer consecutive. On the other hand, as a decoding method for this encoding method, the above-mentioned steps B.3) and B.4)
In between, the following procedures were used:

B. Execute F⇒F+C _i (x _i )・S.

In other words, if F2+C _i (x _i )・B1, F1⇒F1+1, F2⇒f _rac (F2+C _i (x _i )・B
otherwise, execute F2⇒f _rac (F2+C _i (x _i )・B).

B. All lower M digits of F1 are b-1
If so, move on to the next step, otherwise move on to B. ho).

B. Execute F1⇒b・F1+f _2,1 F2⇒f _rac (b・F2) W1⇒b・W1+W _2,1 W2⇒f _rac (b・W2) τ⇒τ+1, δ⇒δ+1.

B. ni B. ro).

B. E Move on to the next step.

Here, F1 and F2 are equal to those used by the corresponding encoder, and the initial values are also the same as those of the encoder. By incorporating carry propagation control as described above, arithmetic codes have been applied to data compression even in applications that require small encoding delays.

<Problems to be solved by the invention> However, in the conventional carry propagation control method, when b-1 appears a certain number or more consecutively, the width of the interval is reduced to 1/b. (i.e., move the representation digits of F toward higher digits by 1)
(digits shifted), an average of about b/(b-1) digits of redundant digits were added to the code digits per carry propagation control operation. This is because the probability that j consecutive bs appear in the upper digits of register F2 is (b-1)/b ^j+1
, and if there are j consecutive b's above F2,
Since j+1 shifts are executed for one carry propagation control, the average number of shifts associated with one carry propagation control is approximately 〓 〓 j=0(j+1)・(b-1)/b This is because ^j+1 = b/(b-1) times. In particular, when b = 2, the conventional carry propagation control method has the disadvantage that the length of the code bit string increases by an average of b/(b-1) = 2 bits per operation. Ta.

The purpose of the present invention is to eliminate the above-mentioned drawbacks of conventional data compression encoding devices and data compression decoding devices, and to incorporate a new carry propagation control method in which the increase in length of code digit string due to carry propagation control is small. An object of the present invention is to provide a data compression encoding device.

<Structure of the Invention> The present invention sequentially changes predetermined intervals on a numerical line using a predetermined method according to information digits that are sequentially input, and changes the finally obtained interval. In a data compression encoding device that outputs the b-adic representation of the real numbers included as a coded digit string for an input information digit string, a predetermined value is determined by monitoring the contents of a register that stores the value at one end of the interval. The alarm circuit that generates a carry alarm signal according to the rule, and the contents of the register that stores the width of the section if a carry alarm signal is generated, are all set to b-1, and the value at one end of the section is set to b-1. and a section shortening circuit that limits the propagation length of a carry to a certain length or less by shifting the contents of a register storing a carry alarm signal toward higher-order digits until a carry alarm signal is no longer generated. It is characterized by

<Function> According to the above-mentioned literature, the length of the code digit string is longer if the width of the finally obtained section is smaller, and vice versa. Therefore, the smaller the reduction rate of the section due to carry propagation control, the smaller the increase in redundant digits due to carry propagation control.
Here, the reduction rate is a value obtained by dividing the width of the section before the change by the width of the section after the change. However, according to the above-mentioned document, in order to be able to restore the original information digit string from the code digit string without error, it is necessary that the section after the change is included in the section before the change.

In the present invention, the following procedure is added between steps A.b) and A.c).

Let Aa t ₁ , t ₂ , ..., t _K be b-1.

Additionally, the following procedure is added between steps B.c) and B.d).

Let Ba S ₁ , S ₂ , ..., _SK be b-1.

That is, in the present invention, steps A.b) and B.c)
After execution, the width of the section is expanded. Of course, the operations performed in steps A.B) and AZ) and B.C) and Bz) are mutually independent operations, so performing steps Aa) and Ba) is A.B) and B.C). It does not matter if it is before or at the same time. In this way, the reduction rate is smaller than in the conventional case where the width of the section is simply divided by b, so the number of redundant digits added to the code digits can be kept small. Furthermore, even if steps Aa) and Ba) are executed, the interval after execution is clearly included in the interval before carry propagation control, so it is not possible to restore the original information digit from the code digit string without error. can. In addition, in steps Aa) and Ba), if the values of T and S after execution of the procedure are larger than the values of T and S before execution, then t ₁ , t ₂ , ..., t _K , S ₁ , S ₂ ,
..., S _K may be set to a value other than b-1, but it is preferable to set all digits equally to b-1 in terms of ease of device implementation.

FIG. 1 is a basic configuration diagram of the present invention. In the figure, the information digit input from the input terminal 101
x _i is sequentially input to the probability parameter generator 102, and the probability parameter generator 102 outputs probability parameters C _i (x _i ) and q _i (x _i ) to lines 104 and 103, respectively, according to the value of x _i . do. The adder and multiplier are F1, F2,
Update the value of A and transfer it to registers 108, 10
6,105. In addition, to line 107
1 is output when F2+C _i (x _i )·A1, and 0 is output otherwise. Among the values of F1, digits higher than the lower M digits are sequentially outputted from the output terminal 109. On the other hand, F1's lower M
The digits are also supplied to the alarm circuit 110, and when a carry propagation longer than M digits is about to occur, that is, when all M digits become b-1, a carry alarm signal is sent to the section shortening circuit 111.
When the section shortening circuit receives the carry alarm signal, it sets all the contents of the A register 105 to b-1, while
Register 1 until the carry alarm signal is no longer generated.
The contents of 08,106 are shifted toward the higher order digits to prevent a 1 from being output on line 107. That is, execute steps A.a) to A.d) and Aa).

FIG. 2 is a basic configuration diagram of a decoding device for the encoding device of FIG. 1. In the figure, F1 register 207, F2 register 208, alarm circuit 209,
The probability parameter generator 204 is the same as that included in the corresponding encoding device. The code digit W _i input from the input terminal 201 is
The representation digits of W1 and W2 are sequentially input into a register 202 in which they are stored, and the x _i generator 203 changes the output supplied to the stochastic parameter generator 204 to generate C _i (y)(W1+
The largest digit among y that satisfies W2)/B
Find x _i and use it as the final output. Note that when the output of the x _i generator 203 is y, the comparison result between C _i (y) and (W1+W2)/B is supplied to the line 211. When the output of the x _i generator 203 is determined, the adder and multiplier perform the decoding procedure described above.
Change the values of W and B according to B.4) and store them in registers 202 and 206, respectively. Also, the contents of the F1 register 207 and F2 register 208 are changed according to the decoding procedure B.a) described above. x _i generator 2
The output of 03 is also supplied to the output terminal 205, and when the value of x _i is determined, it is outputted from the output terminal 205 in order. On the other hand, the contents of the F1 register 207 are also supplied to an alarm circuit 209, and the alarm circuit sends a carry alarm signal to the interval correction circuit 210 when a carry propagation longer than M digits is about to occur. When the section correction circuit 210 receives the carry alarm signal, it changes all the contents of the B register 206 to b-1.
At the same time, the contents of registers 202, 206, 207, and 208 are shifted toward higher digits until the carry alarm signal is no longer generated, that is, steps B.a) to B.e) and Ba) are executed.

<Embodiment> As an embodiment, a data compression encoding device configured according to the present invention is shown in FIG. 3, and a corresponding data compression encoding device is shown in FIG. 4.

Blocks or lines in FIGS. 3 and 4 having the same functions as those in FIGS. 1 and 2, respectively, are designated by the same numbers. In this example b=2. In other words, operations in the encoding device and decoding device are performed in binary notation, and numerical values are
It shall be displayed in decimal notation.

In the encoding device shown in FIG.
The input information bits x _i are sequentially input to a probability parameter generator 102 (which can be configured, for example, by a read-only memory or an adaptive predictor), and the probability parameter generator 102 generates a probability according to the value of x _i . Parameters C _i (x _i ) and q _i (x _i ) are output to lines 104 and 103, respectively. The adder and multiplier are F1, F2,
Update the value of A and transfer it to registers 108, 10
6,105. In addition, to line 107
1 is output when F2+C _i (x _i )·A1, and 0 is output otherwise. Of the value of F1, the bits higher than the predetermined lower M bits are sequentially outputted from the output terminal 109. On the other hand, the lower M bits of F1 are also supplied to the alarm circuit 110,
When a carry propagation longer than a bit is about to occur, that is, when all M bits become 1, a carry alarm signal is sent to the section shortening circuit 111. Since the alarm circuit generates a carry alarm signal when all the lower M bits of F1 become 1, the alarm circuit can be constructed by ANDing these M bits. When the section shortening circuit 111 receives the carry alarm signal, it sets all the contents of the A register 105 to 1, and shifts the contents of the registers 108 and 106 toward the higher bits until the carry alarm signal is no longer generated. 107
This prevents 1 from being output. i.e. procedure
Execute A.b) to A.d), Aa).

In the decoding device shown in Fig. 4, F1 register 2
07, F2 register 208, alarm circuit 209, and probability parameter generator 204 are the same as those included in the corresponding encoding device. The sign bit W _i input from the input terminal 201 is W1,
Register 20 where the representation bits of W2 are stored
The x _i generator 203 first converts the output supplied to the stochastic parameter generator 204 into 1
and C _i supplied to line 211
Examine the comparison results between (1) and (W1+W2)/B,
If C _i (1)(W1+W2)/B, x _i =1 otherwise x _i =0, and x _i is the final output.
Note that the output of the x _i generator 203 is on the line 211.
When , the comparison result between C _i (y) and (W1+W2)/B is supplied. When the output of the x _i generator 203 is determined, the adder and multiplier perform the decoding procedure described above.
Change the values of W and B according to B.4) and store them in registers 202 and 206, respectively. Also, the contents of the F1 register 207 and F2 register 208 are changed according to the decoding procedure B.a) described above. x _i generator 2
The output of 03 is also supplied to the output terminal 205, and when the value of x _i is determined, it is output from the output terminal 205 in order. On the other hand, the contents of the F1 register 207 are also supplied to the alarm circuit 209, and when a carry propagation longer than M bits is about to occur, that is, when all M bits become 1, the alarm circuit sends a carry alarm signal to the interval correction circuit 210. send to When the section correction circuit 210 receives the carry alarm signal, it sets all the contents of the B register 206 to 1, and keeps the contents of the register 206 until the carry alarm signal is no longer generated.
Shift the contents of 2, 206, 207, and 208 toward the higher bits. That is, steps B.a) to B.
Execute e) and b).

<Effects of the Invention> As described above, according to the present invention, it is possible to easily configure a data compression encoding/decoding device with higher compression efficiency than, for example, conventional data compression encoding/decoding devices.

Moreover, output compression encoding as shown in the example,
Since the decoding device can be configured with a simple circuit, it can also be used in high-speed data transmission systems.

It is clear that these will be effective in improving efficiency and performance in the future development of high-speed digital communication networks and the spread of large-capacity storage devices.

[Brief explanation of drawings]

FIG. 1 is a basic configuration diagram of the present invention, FIG. 2 is a diagram showing the basic configuration of a decoding device used with the present invention, FIG. 3 is a diagram showing an embodiment of the present invention, and FIG. FIG. 2 is a diagram showing an example of the configuration of a decoding device used together with the encoding device shown in the figure. In the figure, 102, 204... stochastic parameter generator, 1
06,108,105,202,206,20
7,208...Register, 110,209...Alarm circuit, 111...Section shortening circuit, 203...x _i
Generator, 210... section correction circuit, 112, 21
3...Selector.

Claims (1)

[Claims] 1. A first register and a second register that store b-ary values (b≧2), and a probability parameter generator that outputs pre-registered probability parameters according to input information digits. a multiplier for multiplying the contents of the second register by the output of the probability parameter generator; and an adder for adding the output of the multiplier and the contents of the first register and supplying the result to the first register. Each time an information digit is input, the output of the adder and the output of the multiplier are respectively
and the second register, and if the most significant digit of the second register becomes 0, it becomes 0.
Shifts the first and second registers in the upper digit direction until the digits disappear, and outputs the digit string shifted and overflowing from the first register as a code digit string corresponding to the input information digit string. The data compression encoding device for arithmetic codes includes at least an alarm circuit that generates a carry alarm signal when all upper fixed length digits of the first register become b-1, and when the carry alarm signal is If an alarm signal occurs, the contents of the second register are all set to b-1, and the first register is shifted toward higher digits until the alarm signal is no longer generated.