JPH0453328B2 - - Google Patents

Description

[Detailed Description of the Invention] <Industrial Application Field> The present invention is designed to extract data from compressed data by removing redundancy in order to save transmission time and storage capacity when transmitting or storing digital data. The present invention relates to a data compression/decoding device for restoring data.

<Prior Art> As a method of compressing redundant data and a method of restoring the original redundant data from the compressed data, a method using arithmetic codes is well known and used in the past. For details on the arithmetic code data compression encoding device (device that compresses data, hereinafter also simply referred to as encoding device) and data compression decoding device (device that restores data, hereinafter also simply referred to as 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.
Volume 20, No. 3, pages 198-203 of Vol.
A doctoral dissertation by Richard Clark Pasco published in 1976 at Source Coding Algorithms for First Data Compression (Source
coding algorithms (fast data compression)”
is described in detail. To briefly describe the data compression method among these methods, information digit strings X ₁ , X _{2 .} . . , X _N are converted into code digit strings W ₁ , W ₂ .
W _L is changed, for example, as follows to remove the redundancy of the information digit string.

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, the following steps _A1 ) to _A5 ) are executed. Note that in the following, XY represents substituting the value of Y for X. Also, all operations are b
It shall be done in hexadecimal format.

Let the value of A ₁ i be 1.

_A2 Input the i-th information digit Xi.

A ₃ Probability of appearance q _i of the i-th information digit Xi
(x _i ) and cumulative appearance probability C _i (X _i )=Σ ^y < ^xi q _i (y).

A ₄ FF+C _i (X _i )・T Tq _i (X _i )・T, and T is truncated at a predetermined significant number of K digits.

If A ₅ i<N, increase the value of i by 1 and move to A ₂ .

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 express the selected real number as digits O・W ₁ W ₂ ……W _L The sign digit string
Define as W ₁ , W ₂ , ..., W _L. Note that the following notation will be used below for convenience of explanation.

T=A・b ^- 〓 A=Ct ₁ t ₂ ......t _l(A) F=(F1+F2)・b ^- 〓 {F1=f ₁ , ₁ f ₁ , ₂ ... f ₁ , _l(F1) F2 =O・f ₂ , ₁ ...f ₂ , (2)...f ₂ , _l(F2) where l(A), l(F ₁ ), and l(F ₂ ) are respectively A,
Expression of F1 and F2 Represents the number of digits. Furthermore, in the initial state (that is, when the encoding device is initialized with F and O and T as 1), t ₁ ≠ 0
shall be set. Then the steps mentioned above
A4) is expressed as follows.

A4.1 If F2+C _i (X _i )A・1, execute F1F1+1.

A4.2 Let F2frac(F2+C _i (X _i )・A). Here, frac(X) is a function that gives a value below the decimal point of X.

A4.3 Let Aq _i (X _i )・A.

A4.4 If t ₁ = 0, F1b・F1+f ₂ , ₁ F2frac(b・F2) Ab・A ττ+1.

A4.5 If t ₁ = 0, move on to A4.4), otherwise move on to the next one.

A4.6 Truncate t _k+1 , t _k+2 , etc. below the K+1 decimal point of A.

It is shown in the above-mentioned literature that if the above procedures A1) to A5) are followed, the length L of the code word is generally smaller than the length N of the information digit string, and data can be compressed. On the other hand, to briefly describe the method for restoring data, the coded digit sequence W ₁ , W ₂ , ...,
For example, W _L is converted as follows, and the original information digit strings X ₁ , X ₂ , . . . , X _N are restored.

First, OW ₁ W _{2 .} . . W _L is substituted for W, and 1 is substituted for S. Next, execute steps B1) to B5) below. Note that in the following, XY represents substituting the value of Y 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.

B3 _Xi is output as a restored information digit, B4 WW-C _i (X _i )·S Sq _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, end.

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

S=B・b ^- 〓 B=OS ₁ S ₂ ...S _l(B) W=(W1+W2)・b ^- 〓 {W1=W ₁ , 1W ₁ , ₂ ...W ₁ l (W ₁ ) W2= OW ₂ , ₁ W ₂ , ₂ ...W ₂ , _(W2) where l(B), l(W1), l(W2) are B, respectively.
Expression of W1 and W2 Represents the number of digits. Further, in the initial state (that is, when the decoding device is initialized with W as OW ₁ W ₂ . . . W _L and S as 1), it is assumed that S ₁ ≠O. Then, the above step B2) becomes as follows.

Let X _i be the largest digit among Y that satisfies B2 Ci(Y)(W1+W2)/B.

Further, step B4) is expressed as follows.

B4.1 If W2−C _i (X _i )・B<O, execute W1W1−1 W2 (1.0+W2)−C _i (X _i )・B. Otherwise, execute W2W2−C _i (X _i )·B.

B4.2 Let Bq _i (X _i )・B.

B4.3 If S ₁ = O, then W1b・W1+W2, ₁ W2frac(b・W2) Bb・B δδ+1.

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

Otherwise, move on.

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

If you follow the steps B1) to B5) above, the code digit string will be
The above-mentioned document shows that the original information digit sequence X ₁ , X ₂ , _. . . , X _N can be restored without error from W 1 , W _{2 ,} .

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 set up 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, and the length L of the code digit string is set to a value determined depending on the redundancy of the information digit string, but conversely, L is set to a predetermined constant value. It is also possible to take a predetermined constant value and take a value for N that depends 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 move to A2). If τ=L−J, end.

B5' If δ<L-J, increase the value of i by 1 and move to B2). If δ=L−J, end.

Here, J is the number of significant digits of q _i (·) and C _i (·).
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 that the code digits can be sequentially output in the above steps A1) to A5). That is, according to the above-mentioned document, once a carry occurs in the operation F1F1+1 in step A4.1), the finish will not be propagated again to digits higher than the range in which the carry propagated (for example, if b=2 and 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 performing data compression and data restoration as described above are described in, for example, U.S. Patent No. 4122440 of International Business Machines Corporation of the United States. This can be realized with a circuit that includes a digit operation circuit such as addition and multiplication.

Of course, even if code digits can be output sequentially, for example, when F1 = 0111111, the procedure
When F1F1+1 is executed in A1), the carry propagates to the most significant digit, so the code digits cannot be sequentially output. In other words, since the length of carry propagation is not constant, the encoding delay becomes large when 1s appear continuously 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 F1F1 of step B4.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 F1b・F1+f ₂ , ₁ F2frac (b・F2) ττ+1 A C Move to 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 is equivalent to shifting the contents of the register in which the representation digits of F1 and F2 are stored upwards until M b-1 numbers are no longer consecutive.

On the other hand, as a decoding method for this encoding method, a method was used in which the following procedure was added between the above-mentioned procedures B.3) and B.4).

B i Execute FF+C _i (X _i )・S.

In other words, if F2+C _i (X _i )・B1, then F1F1+1, F2frac(F2+C _i (X _i )・B)
Otherwise, F2frac(F2+C _i (X _i )・B
Execute.

B B The lower M digits of F1 are all b-1
If so, move on to the next step, otherwise move on to B/H).

Execute B C F1b・F1+f ₂ , ₁ F2frac(b・F2) W1b・W1+W ₂ , ₁ W2frac(b・W ₂ ) ττ+1, δδ+1.

Move to B. ni B. ro).

B. Ho Move on to the next one.

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 coding delays.

<Problem 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., the representation digit of F was shifted one digit toward the higher order digit). Therefore, for each carry propagation control operation, an average of about b/(b-1) digits of redundant digits is added to the code digit. It was done. This is because the probability that j consecutive b's occur in the upper digits of register F2 is (b-1)/b ^j+1 , and if there are j consecutive b's in the upper digits of F2, then 1
Since j+1 shifts are executed for carry propagation control, the average number of shifts associated with one carry propagation control is approximately _∞ Σ ^j=0 (j+1)・(b−
1)/b ^j+1 = b/(b-1) times. In particular, when b = 2, the conventional carry propagation control method yields an average of b/(b-1) per operation.
=2 bits also had the disadvantage that the length of the code bit string increased.

An object of the present invention is to eliminate the above-mentioned drawbacks of conventional data compression encoding devices and data compression decoding devices, and to provide a new carry propagation control method in which the length of the coded digit string increases little due to carry propagation control. An object of the present invention is to provide a data compression/decoding device that is compatible with a data compression/encoding device incorporating the above.

<Configuration of the Invention> The data compression/decoding device of the present invention includes a first register and a second register that store a b-ary value (b≧2), and outputs a probability parameter registered in advance according to an input digit. a probability parameter generator 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; An alarm circuit is provided which generates a carry alarm signal when all of the upper fixed length digits of the first register become b-1, and each time information is input, the output of the adder and the multiplier are The outputs of are held in the first register and the second register, respectively, and when the most significant digit of the second register becomes 0, the first register and the second register are held as the upper digits until the most significant digit of the second register becomes 0. On the other hand, if a carry alarm signal is generated, the contents of the second register are all set to b-1, and the first register is shifted toward the upper digit until the alarm signal is no longer generated. , in a data compression/decoding device corresponding to a data compression/encoding device that outputs the digit string shifted and overflowing from the first register as a code digit string corresponding to the input information digit string. a third register for holding code digits; a copy of the data compression encoding device; a generating circuit for generating digits from 0 to b-1 and supplying them to the probability parameter generator; a divider for dividing the contents by the contents of the second register; a comparator for comparing the output of the divider with the output of the probability parameter generator; and a subtraction circuit for subtracting the output of the multiplier from the third register. The output of the generator circuit is varied, and when the outputs of the comparator match, the output of the adder, the multiplier, and the subtraction circuit are transferred to the first register and the second register, respectively. and a third register, and the second
When the most significant digit of the register becomes 0, the first, second, and third registers are shifted toward the upper digit until it is no longer 0, and the sign digit is shifted to the most significant digit of the third register. On the other hand, if the carry alarm signal is generated, the contents of the second register are all set to b-1, and the first and second registers are held until the carry alarm signal is no longer generated. The third register is shifted toward the upper digit, and the code digit is held at the lowest digit of the third register, and the output of the generator circuit is outputted as an information digit corresponding to the input code digit. Features.

<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 section reduction rate 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).

A.a) Let t ₁ , t ₂ , ..., t _k be b-1.

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

B.a) Let S ₁ , S ₂ , ..., S _k be b-1.

That is, in the present invention, the width of the section is expanded after performing steps A and B) and B and C). However, procedures A.B) and A.z) and procedure B.C) and B.
Since the operations performed in step z) are mutually independent operations, steps A.a) and B.a) are executed by A.
B), B and C) may occur 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 to which code digits are added can be kept small. Also, step A.
Even if a) and B/a) are executed, the interval after execution is clearly included in the interval before carry propagation control, so the original information digit can be restored from the code digit string without error. . In addition, in steps A.a) and B.a), T after the procedure is executed,
If the value of S becomes larger than the values of T and S before execution, t ₁ , t ₂ , ..., t _k S ₁ , S ₂ ..., S _k should be set to a value other than b-1. However, from the point of view of ease of instrumentation, all digits should be equally <b−
It is preferable to set it to 1.

FIG. 2 is a basic configuration diagram of an encoding device that executes procedure A.a). In the figure, information digits X _i inputted from an input terminal 101 are sequentially inputted to a probability parameter generator 102, and the probability parameter generator 102 generates probability parameters C _i according to the value of X _i .
(X _i ) and q _i (X _i ) are output to lines 104 and 103, respectively. The adder and multiplier update the values of F1, F2, and A according to the aforementioned encoding procedure A.4), and store them in registers 108, 106, and 105. In addition, to line 107, F2 + C _i (X _i )・A
When it is 1, 1 is output; otherwise, 0 is output. Among the values of F1, digits higher than the lower M digits are sequentially outputted from the output terminal 109. On the other hand, the lower M digits of F1 are also supplied to the alarm circuit 110, and when a carry propagation longer than the M digits is about to occur, that is, when all the 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, and shifts the contents of the registers 108 and 106 toward higher digits until the carry alarm signal is no longer generated. line 107
This prevents 1 from being output. That is, execute steps A.a) to A.d) and A.a).

FIG. 1 is a basic configuration diagram of the present invention. In the figure, an F1 register 207, an F2 register 208, an alarm circuit 209, and a probability parameter generator 204 are the same as those included in the corresponding encoding device. The sign digit W _i inputted from the input terminal 201 is inputted in order to the register 202 in which the representation digits of W1 and W2 are stored, and the sign digit W i is inputted to the X _i generator 2.
03 is C _i (y) by varying the output supplied to the stochastic parameter generator 204.
Find the maximum digit X _i among y that satisfies (W1+W2)/B, 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 change the values of W and B according to the above-described decoding procedure B.4) and store them in the registers 202 and 206, respectively. Also
The contents of the F1 register 207 and F2 register 208 are changed according to the above-mentioned decoding procedure B/a). X _i
The output of the generator 203 is also supplied to the output terminal 205, and when the value of X _i is determined, the output terminal 20
It is output from 5. On the other hand, F1 register 207
The contents of are also supplied to the alarm circuit 209, and when a carry propagation longer than M digits is about to occur, the alarm circuit sends a carry alarm signal to the section correction circuit 2.
Send to 10. When the section correction circuit 210 receives the carry alarm signal, it changes all the contents of the B register 206 to b.
-1, and registers 202, 206, 207, 208 until the carry alarm signal is no longer generated.
In other words, steps B.a) to B.e) and B.a) are executed.

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

In FIGS. 3 and 4, lines without blocks having the same functions as those in FIGS. 1 and 2, respectively, are labeled with the same numbers. In this example b=2. That is, calculations in the encoding device and the decoding device are performed in binary notation, and numerical values are displayed in binary notation.

In the encoding device shown in FIG. 4, the information bits X _i inputted from the input terminal
02 (which can be configured, for example, by a read-on memory or an adaptive predictor), and the probability parameter generator 102 generates probability parameters C _i (X _{i )} , q _i (X _i ) respectively on line 103
Output to. The adder and multiplier update the values of F1, F2, and A according to the above-mentioned encoding procedure A.4),
It is stored in registers 108, 106, and 105. In addition, to line 107, F2 + C _i (X _i )・A1
1 when , and 0 otherwise.
The bits higher than the predetermined lower M bits of the value of F1 are sequentially outputted from the output terminal 109. On the other hand, the lower bit of F1 is the alarm circuit 11
0 is also supplied, and when a carry propagation longer than M bits is about to occur, that is, when all M bits become 1, a carry alarm signal is sent to section shortening circuit 111.
send to 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,
While register 105 sets all contents to 1, register 10 remains unchanged until the carry alarm signal is no longer generated.
The contents of 8,106 are shifted toward the high order bits to prevent a 1 from being output on line 107. That is, steps A.a) to A.d), A.a)
Execute.

In the decoding device shown in Fig. 3, 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
2, and the X _i generator 203 first converts the output supplied to the probability parameter generator 204 into 1
and C _i supplied to line 211
Examine the comparison results between (1) and (W1+W2)/B, and if C _i (1) (W1+W2)/B, then X _i =1, otherwise X _i =0, and X _i is the final output. shall be. 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 B.
4), the values of W and B are changed and stored in registers 202 and 206, respectively. Also, the contents of the F1 register 207 and F2 register 208 are changed according to the above-mentioned decoding procedure B/a). The output of the generator 203 of X _i is also supplied to the output terminal 205, and when the value of X _i is determined, it is sequentially supplied to the output terminal 205.
It is output from. 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, while
Register 2 until the carry alarm signal is no longer generated.
The contents of 02, 206, 207, and 208 are shifted toward the higher bits. In other words, step B/i)~
Execute B. ho) and B. a).

<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 conventional data compression encoding/decoding devices.

Moreover, since the data compression encoding/decoding apparatus shown in the embodiment can be constructed with a simple circuit, it can also be used in high-speed data transmission systems.

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

[Brief explanation of drawings]

FIG. 1 is a basic configuration diagram of the present invention, FIG. 2 is a diagram showing a basic configuration diagram of an encoding device used with the present invention, FIG. 3 is a diagram showing an embodiment of the present invention, and FIG.
The figure is a diagram showing an example of the configuration of a decoding device used together with the encoding device of FIG. 3. In the figure, 102, 204... stochastic parameter generator, 106, 108, 105, 202, 2
06,207,208...Register, 110,2
09...Alarm circuit, 111...Section shortening circuit, 2
03...X _i generator, 210... section correction circuit,
112, 213...Selector.

Claims (1)

[Claims] 1. A first register and a second register that store a b-ary value (b≧2), a probability parameter generator that outputs a pre-registered probability parameter according to an input digit, and the contents of the second register. a multiplier for multiplying by the output of the probability parameter generator; an adder for adding the output of the multiplier and the contents of the first register; an alarm circuit that generates a carry alarm signal when the value becomes 1, and sends the output of the adder and the output of the multiplier to the first register and the second register, respectively, each time information is input. and when the most significant digit of the second register becomes 0, the first and second registers are shifted toward the upper digit until it is no longer 0, while a carry alarm signal is generated. If so, all the contents of the second register are set to b-1, the first register is shifted toward the upper digits until the alarm signal is no longer generated, and the digits that have been shifted and overflowed from the first register are In a data compression decoding device corresponding to a data compression encoding device that outputs a string as a coded digit string corresponding to an inputted information digit string, a third register that holds the inputted coded digit, and a third register that holds the inputted coded digit string; a generator for generating digits from 0 to b-1 and supplying them to the probability parameter generator; and a divider for dividing the contents of a third register by the contents of a second register; A comparator that compares the output of the divider and the output of the probability parameter generator, and a subtraction circuit that subtracts the output of the multiplier from the third register, and changes the output of the generator circuit and compares the output of the probability parameter generator. When the outputs of The most significant digit of the register is 0
If the digit becomes zero, shift the first, second, and third registers in the direction of higher digits until it is no longer 0, and hold the sign digit at the lowest digit of the third register; If the carry alarm signal occurs, the contents of the second register are all b-1.
and shifts the first and third registers toward the upper digits and holds the sign digit at the lowest digit of the third register until the carry alarm signal is no longer generated; A data compression/decoding device characterized in that the output of the code digit is output as an information digit corresponding to an input code digit.