JPH07106981A - Variable length code decoding circuit - Google Patents

Abstract

(57) [Abstract] [Purpose] To reduce the size of the data expansion conversion table to reduce the memory capacity and cost. A variable-length code decoding circuit for decoding a variable-length code having a length of 1 to 2 ⁿ bits, wherein a table holding the smallest code of each length of the variable-length code in the order of the code length and 2
^{It has m} −1 (where m = 1, 2, ...) Comparators,
Reading 2 ^m -1 elements at a time from the table,
Each of the comparators performs a magnitude comparison with the variable length code input and repeats the comparison operation n / m times to satisfy the condition that i-th table element ≦ variable length code input <i + 1th table element. The feature is that the length of the leading code of the variable-length code input is obtained by finding the table element.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a variable length code decoding circuit which converts variable length coded and compressed data into an original code. In recent years, the amount of data handled in fields such as data processing, image processing or information communication tends to increase more and more, and effective data compression / expansion is performed in terms of improving transfer efficiency and efficient use of storage devices. Technology is required.

[0002]

2. Description of the Related Art If there are imbalances in the occurrence probabilities of M information source symbols (hereinafter referred to as "original codes") {A} (A = 0, 1, ..., M-1), a length n It is possible to map the original code sequence into a short sequence of n '<n, that is, to compress the sequence, and the following data compression techniques utilizing this principle are known.

In the data compression conversion table of FIG.
Codes 1 to 256 are 256 (the number is an example) original code, and are arranged in the order of code 1, code 2, ..., Code 256 according to the appearance frequency (occurrence probability). The code 1 has the highest appearance frequency, and the code 256 has the lowest frequency. The variable length code (binary number) assigned to each code is a conversion sequence for each original code, and the number of bits of each is Has become. That is, the number of bits of the variable-length code sequentially increases from the higher appearance frequency of the original code to the lower appearance frequency.

Now, when the original code string is composed of [code 30, code 1, code 7], the sequence after conversion is [abc].
Is represented by [1111111101011 ₂ ], b
Becomes [0 ₂ ] and c becomes [1111010 ₂ ], and finally the sequence [11111110] having a length of 20 bits is obtained.
1011011111010 ₂ ] (hexadecimal representation is FEB
7A ₁₆ ).

Therefore, since the actual original code sequence is composed of a much larger number of codes, for example, code 1 in the original code sequence is used.
The greater the ratio of, the shorter the sequence length after conversion and the more efficient data compression becomes possible. FIG. 8 is a configuration diagram of a main part of a system including a data compression unit and a decompression unit for data processing, image processing, information communication and the like. Reference numeral 71 is a data compression unit, and 72 is a data decompression unit, which are connected to a host CPU (Central Processing Unit) 74 and a mass storage device (for example, a hard disk) 75 via a data bus 73 and are not shown. The communication control unit and various input / output control units are connected.

The data compression section 71 includes a variable length coding circuit 7
Variable length coding circuit 7 including 1a and pack circuit 71b
1a internally has the above-mentioned data compression conversion table (see FIG. 7), converts the original code into a variable-length code, and converts the length information of the variable-length code after conversion (the number of bits of the variable-length code; Code length information ") is output. Pack circuit 71
b is a sequence for generating a concatenation of all variable-length codes (hereinafter referred to as “variable-length code sequence”), and this sequence is written in the storage device 75, or a communication control unit or various input / output controls. It may be transferred to the outside of the system via the department.

The data decompression unit 72 converts the variable length code sequence into 16
Bit unit (or bit unit specified by code length information)
An unpack circuit 72a and an unpack circuit 7
And a variable length code decoding circuit 72b for converting the output of 2a into the original code and reproducing the code length information for designating the number of division bits. Here, as shown in FIG. 9, the variable-length code decoding circuit 72b is a 16-bit address memory, which receives the variable-length code as an address input and outputs an 8-bit original code and 4-bit code length information. Is.

FIG. 10 shows a variable length code decoding circuit 72b.
Is a data decompression conversion table stored inside
The table capacity is hexadecimal [0000₁₆] To [FF
BB ₁₆] Up to about 64 kW (kiloword)
Is the amount. The binary representation of the lowest address in the table is [0
000000000000000000 ₂], The highest address
The binary representation of [11111111110111011₂]
And x in the bit is 0 or 1
There is. For example, [0xxxxxxxxxxxxxxxxxxx₂]
Is [0000000000000000₂] To [0
111111111111111₂] Up to
It is meant to include.

Now, the variable length code string to be converted is shown in the above example of data compression [111111101011011].
11010 ₂ ], first, m bits (m is the number of address bits in the conversion table) are fetched from the beginning of this variable length code string. Here, because it is m = 16, captures the 1111111010110111 _2]. Then, the conversion table of FIG. 10 is referred to by the captured data, and “code 30” and “code length information 11” (however, the value of the code length information is represented by 4 bits) from the address [111111101011xxxx ₂ ] matching the captured data. Is subtracted from the actual code length by 1; that is, the actual code length is 12 ₁₀ ).

Next, 16 bits [0111101000000000 ₂ ] (the lower 8 bits are additional bits for digit alignment) are taken in, excluding the leading 12 bits (the number of bits indicated by the code length information) of the variable length code string. Then, the conversion table of FIG. 10 is referred to again by this fetched data, and the address [0xxx
“Code 1” and “code length information 0” (actual code length is 1 ₁₀ ) are read out from within xxxxxxxxxxxxxx ₂ ].

Finally, 16 bits [1111010000000000000 ₂ ] (lower 9 bits of the remaining variable length code string excluding the first 1 bit (the number of bits indicated by the code length information))
Bits are additional bits for digit alignment). And
The conversion table of FIG. 10 is referred to again by the captured data, and the address [111
“Code 7” and “code length information 6” (actual code length is 7 ₁₀ ) are read out from within 1010xxxxxxxxxx ₂ ].

By the above operation, the variable length code string [11
1111101011011111010 ₂ ] can be reproduced into the original code string [code 30, code 1, code 7] to decompress the data.

[0013]

However, in such a conventional variable length code decoding circuit, in hexadecimal representation, about 64 bits from [0000 ₁₆ ] to [FFBB ₁₆ ] are used.
Since the data decompression conversion table of KW is required, there is a problem that the memory capacity increases and the cost increases. [Purpose] Therefore, an object of the present invention is to reduce the scale of the data expansion conversion table to reduce the memory capacity and to reduce the cost.

[0014]

In order to achieve the above object, the present invention provides a variable length code decoding circuit for decoding a variable length code having a length of 1 to 2 ⁿ bits, wherein each length of the variable length code is Has a table that holds the smallest code in the order of code length and 2 ^m −1 (where m = 1, 2, ...) Comparator, and 2 ^m −1 The element is read out, the magnitude comparison with the variable-length code input is performed in each of the comparators, and the comparison operation is repeated n / m times to satisfy the condition that the i-th table element ≦ the variable-length code input <i + 1-th table element. The feature is that the length of the leading code of the variable-length code input is obtained by finding the i-th table element that satisfies the condition.

Alternatively, there is provided a variable length code decoding circuit for decoding a variable length code having a length of 1 to 16 bits, in which a table holding the smallest code of each length of the variable length code in the order of the code length and 3, Of the i-th table element by reading out three elements at a time from the table, performing a magnitude comparison with the variable-length code input in each of the comparators, and repeating the comparison operation twice. <Variable-length code input <i + 1th table element The condition is that the length of the code at the beginning of the variable-length code input is found by finding the i-th table element.

Alternatively, a variable length code decoding circuit for decoding a variable length code, which is an FC table holding the original code, a VC table holding the smallest code of each length of the variable length code in the order of the code length, VL table holding code length corresponding to VC table, FC corresponding to VC table
It includes a BP table that holds the address of the table, three comparators, a shifter, an adder, and a subtracter. At the first stage, three elements are read from the VC table at the same time, and
The number of comparators compares the variable length code input with that of the variable length code input to determine which of the four groups of the VC table the variable length code input belongs to.
The three elements of the group determined at the stage are read out, and the magnitude comparison with the variable length code input is performed by the three comparators to determine which element of the VC table the variable length code input corresponds to. In the step, the elements of the VC table, the elements of the VL table and the elements of the BP table corresponding to the variable length code input are read, the difference between the value of the variable length code input and the read value of the VC table is obtained by the subtractor, and , V in the shifter
A shift is performed according to the read value of the L table, the read value of the BP table is added to the shift result by the adder to obtain the address of the FC table, and the FC of the address is calculated.
It is characterized in that the original code is obtained by reading the elements of the table and the start position of the next variable length code is determined from the read value of the VL table.

Alternatively, as shown in the principle configuration diagram in FIGS. 1 and 2, among the variable length codes corresponding to the M original codes and the one-to-one correspondence, all other variable length codes have the same code length. A first table 1 in which variable length codes that do not exist and variable length codes having the minimum value in the same code length group are arranged in ascending order, and the arranged variable length codes are stored in group units; Of the second table 2 which stores the code length information corresponding to each element of the first table 1 by assigning predetermined identification information to each element of the first table 1 and the beginning of the input variable length code string or designated. The cutout unit 3 that cuts out a length corresponding to the maximum code length from the code length +1 is compared with the output of the cutout unit 3 and the variable length code of the minimum value in the group stored in the first table 1, and the output of the cutout unit 3 is compared. A variable-length code or a value whose value matches the output First comparison means 4 for specifying the group of the first table 1 including the variable length code having a smaller value than the output of the means 3 and the difference between them is small, and all of the groups specified by the first comparison means 4. Of the variable length code of No. 1, the second selection unit 6 of selecting all code length information in the group specified by the first comparison unit 4, and the first comparison unit 4 The third selection means 7 for selecting all the identification information in the group is compared with the output of the cutout means 3 and the output of the first selection means 4, and the output of the cutout means 3 is a variable-length code or a cutout whose value matches. From the output of the first selecting means 5, the second comparing means 8 for specifying the variable length code having a smaller value than the output of the means 3 and the difference between them is the smallest, and the variable length code specified by the second comparing means 8 are outputted. Specified by the fourth selecting means 9 for selecting and the second comparing means 8. Fifth selecting means 10 for selecting one piece of code length information corresponding to the variable length code from the output of the second selecting means 6 and one piece of identification information corresponding to the variable length code specified by the second comparing means 8. Third selection means 7
The sixth selecting means 11 for selecting among the outputs of the above, the difference calculating means 12 for calculating the difference between the output of the cutting means 3 and the output of the fourth selecting means 9, and the bit length of the output of the difference calculating means 12 are the fifth. Bit length adjusting means 13 for adjusting according to the output of the selecting means 10, the output of the bit length adjusting means 13 and the sixth selecting means 1.
The sum calculation means 14 for calculating the sum with the output of 1 and the third table 15 for storing all the source codes are provided, and the source codes of the third table 15 have the same variable length codeword length. Objects are stored in the memory area of consecutive addresses in ascending order of the value of the variable length code, and the predetermined information is determined in the third table 15 so as to indicate the first address of the memory area corresponding to each code length. The addresses of the three tables 15 are determined by the sum calculation means 14.

[0018]

According to this structure, first, the group in the first table 1 is specified from the comparison result of the first comparing means 4, and then one variable length code is determined from the comparison result of the second comparing means 8. Identified and by this one variable length code, code length information and identification information associated with it,
Finally, one original code in the third table 15 is specified.

Here, the variable-length code stored in the first table 1 is a variable-length code whose code length does not match with all other variable-length codes and a variable-length code having the smallest value in the same code-length group. The number of stored codes is certainly smaller than the maximum number (M) of original codes. Therefore, 64 kW (M = 2
(In the case of 56), compared with the conventional example that required a large capacity,
The table capacity can be reduced significantly.

[0020]

Embodiments of the present invention will be described below with reference to the drawings. 3 to 6 are diagrams showing an embodiment of the variable length code decoding circuit according to the present invention. In FIG. 3, 20 is V
C memory, 21 is VL memory, 22 is BP memory, 23
25 to 25 are comparators, 26 is an address determination circuit, and 27 is RA
Register, 28 is RB register, 29 is RC register,
30 is an RD register, 31 is a subtractor, 32 is a shifter, 3
3 is an adder, 34 is an FC memory, 35 is a host CPU
A data bus connected to (not shown), and 36 is an address bus also connected to the host CPU. The numbers 16, 8, or 4 shown in the figure represent the number of bits of input / output data.

First, the four memories will be described.
A VC (Variable Length Code) memory 20 is a 4-port (ports A to D) memory having a capacity of 16 W (word), and has a first table described later stored therein.
A VL (Variable Length) memory 21 is a 2-port (port A, B) memory having a capacity of 16 W, and a part of a second table (code length information part) described later is stored therein. BP (Base Pointer) memory 22 has 16
It is a 2-port (port A, B) memory having a capacity of W, and stores the remaining portion (identification information portion) of a second table described later inside. The FC (Fixed Code) memory 34 has 2 ports (port A,
B) A memory, which stores a third table described later.

The structure of the first, second and third tables will now be described with reference to FIG. In FIG. 4, a large number of variable length codes are stored in the first table.
However, the stored variable length codes are M (here, M = 2).
56) Not all variable length codes defined for each original code, but some variable length codes selected according to a predetermined condition.

That is, the variable-length code in the first table is a variable-length code whose code length does not match with all the other variable-length codes among all the variable-length codes defined for each of the M original codes. Also, it is only the variable length code having the minimum value in the same code length group, which allows the capacity of the first table to be within 16 W. By the way, if the number of original codes is 256 (see FIG. 7), it is actually 256W.
However, by performing the above selection,
In the variable length code example shown here, 1 from address 0 to 13
It can be done with 4W. In the first table of FIG. 4, a dummy variable length code (all 1) is stored in the remaining 2W (addresses 14 and 15).

The variable length code in the first table is a value
Sort in ascending order from smallest to largest
It is stored, for example, at address 0 [000000
0000000000₂], But at address 1 [100
0000000000 ₂], ..., address 1
3 includes [11111111011011110₂] Is stored
Has been done.

Furthermore, the variable length codes in the first table are divided into a plurality of groups (here, four groups G0 to G3), and the head (minimum address) of each group is:
The variable length code having the minimum value is located within the group. The second table stores code length information and predetermined identification information associated with each variable length code in the first table by address matching. The code length information is information indicating the number of bits (1 to 16 bits) of the corresponding variable length code, but 1 is subtracted from the actual number of bits in order to express 1 to 16 bits by 4-bit data. Has a value. For example, the variable length code [1
The code length corresponding to 1111101111000002 ₂ ] is [11 ₁₀ ] but this actually means [12 ₁₀ ].

The identification information is the address reference information of the third table described below. For example, 16 indicates the address 16 of the third table. In the third table, 256 original codes are arranged in order of appearance frequency with addresses 0 to 255. Code 1 has the highest appearance frequency and code 25
6 has the lowest appearance frequency. However, arranging in order of appearance frequency is not an essential requirement of the present invention. If the addresses registered in the second table correspond to the addresses in the third table, the order does not have to be the frequency of appearance.

In the third table, reference numerals 1, 2, 3,
4, 14, 15, 16, 32, 33, or 34, the code length of the corresponding variable-length code does not match all other variable-length codes, code 5-8, code 9-13, or code 35-2.
56 is the code length of the corresponding variable length code is the same in each group. FIG. 5 is a block diagram of the address determination circuit 26. The address determination circuit 26 includes three inverter gates 37 to 39 and two composite gates 40 and 4.
1 is a gate circuit 42 that forms a logic according to the truth table of Table 2 below, The RE register 43 and the RF register 44 that hold the 2-bit outputs g0 and g1 of the gate circuit 42, and the addresses I, J, and K (where I is i ₀ to i ₃ , J is j ₀ to j ₃ , and K is k
₃ selectors 45 for generating _{0 to} k ₃ (4 bits each)
~ 47. The upper and middle selectors 45 and 46 are of a type that selects two inputs (A, B), and the lower selector 47 is a type that selects three inputs (A, B, C). 1 (first stage)
The input A is selected by this operation, the input B is selected in the phase 2 (second step), and the input C is selected in the lower selector 47 in the phase 3 (third step).

A fixed value [0100 ₂ ] (4 ₁₀ ) is given to the input A of the upper selector 45, and the middle selector 4
A fixed value [1000 ₂ ] (8 ₁₀ ) is given to the input A of 6 and a fixed value [1100 is given to the input A of the lower selector 47.
₂ ] (12 ₁₀ ) is given. In addition, [(RE) 01 ₂ ] is input to the input B of the upper selector 45 (where RE is R
The value of the E register 43) is input, and the selector 46 in the middle stage is input.
[(RE) 10 ₂ ] is input to the input B of the above, and [(RE) 11 ₂ ] is input to the input B of the lower selector 47. Further, [(RE) (RF) ₂ ] (where RF is the RF register 44
Output) is given.

Therefore, from the address determination circuit 26, i ₃ = 0 i ₂ = 1 i ₁ = 0 i ₀ = 0 in phase 1 described later, that is, the head address (4 ₁₀ ) of the group G1 of the first table. Is output as the address I, and j ₃ = 1 j ₂ = 0 j ₁ = 0 j ₀ = 0 That is, the head address (8 ₁₀ ) of the group G2 in the first table is output as the address J, and k ₃ = 1 k ₂ = 1 k ₁ = 0 k ₀ = 0 That is, the head address (12 ₁₀ ) of the group G3 in the first table is output as the address K.

In phase 2 to be described later, i ₃ = (g1) i ₂ = (g0) i ₁ = 0 i ₀ = 1 That is, the head of one group designated by the outputs g1 and g0 of the gate circuit 42. The address +1 is output as the address I, and j ₃ = (g1) j ₂ = (g0) j ₁ = 1 j ₀ = 0 That is, the start address +2 of one group designated by the outputs g1 and g0 of the gate circuit 42. Is output as the address J, and k ₃ = (g1) k ₂ = (g0) k ₁ = 1 k ₀ = 1 That is, the start address +3 of one group designated by the outputs g1 and g0 of the gate circuit 42 is the address. It is output as K.

Further, in phase 3 described later, k ₃ = (g 1; value in phase 2) k ₂ = (g 0; value in phase 2) k ₁ = (g ₁ ; value in phase 3) k ₀ = (G0; value of phase 3) That is, the address of one variable-length code in the group specified in phase 2 is output as the address K.

Next, the operation will be described. FIG. 6 is a flow chart for explaining the circuit operation of the present embodiment, and this operation is divided into phase 1, phase 2 and phase 3. The arrow (←) in the flow chart means that the result of the expression on the right side is assigned to the variable (or register) on the left side.
Further, the equal sign (=) means that the result of the expression on the right side is output with the signal name on the left side, and VC [I, J or K] is the first specified by the address I, J or K. Means an element in a table.

Operation of Phase 1 In this phase, first, at step 50, the head addresses 4 of the groups G1, G2 and G3 of the first table are
8 and 12 are generated as addresses I, J and K. This operation is performed by the address determination circuit 26 as described above. Next, in steps 51 to 53, the input 16-bit variable length code string (“input” in the figure) and VC [K],
Comparing the VC [J] and VC [I], according to the combination of the comparison result (cp2, cp1, cp0), at step 54-57, the RE register 43, 0 _10, 1 _10,
Substitute 2 ₁₀ or 3 ₁₀ .

If input ≧ VC [K], [11 ₂ ] (3 ₁₀ ) is substituted into the RE register 43 (group G3 selection), and if VC [K]> input ≧ VC [J], then RE [10 ₂ ] (2 ₁₀ ) is assigned to the register 43 (group G2 selection), and if VC [J]> input ≧ VC [I],
[01 ₂ ] (1 ₁₀ ) is assigned to the RE register 43 (group G1 selection), and if VC [I]> input, [00 ₂ ] (0 ₁₀ ) is assigned to the RE register 43 (group G0). Choice).

That is, this selection operation is performed by inputting 1
6-bit variable length code string and group G of the first table
0 to G3 minimum variable length code ([0000000000
0000000 _2] [111100000000000
0 ₂ ], [11111111111000000 ₂ ] and [1111111011011100 ₂ ]), and the value is smaller than the variable-length code having the same value or the input 16-bit variable-length code string and its difference is the smallest. It is nothing but specifying the group of the first table containing the variable length code.

Incidentally, 3 in steps 51 to 53 above.
One comparison operation is performed by the comparators 23 to 25 at the same time. The comparator 23 outputs a signal cp2 which becomes 1 when the condition of input ≧ VC [K] is satisfied, and the comparator 24
Outputs a signal cp1 which becomes 1 when the condition of input ≧ VC [J] is satisfied, and further, a signal which becomes 1 when the condition of input ≧ VC [I] is satisfied from the comparator 25. cp0 is output.

For example, the input 16-bit variable length code string is [111111101] as in the conventional example at the beginning.
0110111 ₂ ], there is no variable length code of the minimum value in the group that completely matches this input sequence, but the minimum value in the group that satisfies the condition that the value is smaller than this input sequence and the difference between them is the minimum. The value variable length code is [1111110111000] of group G2.
000 ₂ ] is applicable.

Therefore, in the case of this example, (cp2, cp
1, cp0) = (0,1,1), and from Table 2 above, (g
1, g0) = (1,0), the RE register 43
Is set to [10 ₂ ] (that is, 2 ₁₀ ) indicating the identified group G2. Operation of Phase 2 In this phase, it is determined at which position within the group specified in Phase 1 the input variable length code string is located. That is, VC [K] that satisfies the condition of VC [n] ≦ input <VC [n + 1] is determined.

First, in step 58, the address is compared for comparison.
Determine I, J and K as follows. I = RE × 4 + 1 J = RE × 4 + 2 K = RE × 4 + 3 However, RE is the value of the RE register 43 at the time of phase 1.
And RE × 4 is of the group identified in Phase 1
It is the start address itself. For example, in Phase 1
If loop G2 was specified, RE is 2_TenAnd
RE × 4 is 8 _TenTherefore, after all, the address I is 9
_TenBecomes Similarly, the address J is 10_Ten, Address K is
11_TenThen, the address in the group G2 of the first table
Three variable length codes VC [9], Vc
[10] and VC [11] will be referenced. This
These variable length codes are compared with the input in steps 59-61.
And the combination of the comparison results (cp2, cp1, cp0)
Depending on the situation, in steps 62 to 65, the RF register 44
To 0_Ten1_TenTwo_TenOr 3_TenIs substituted.

If input ≧ VC [K], [11 ₂ ] (3 ₁₀ ) is assigned to the RF register 44 (first + 3rd in the specific group is selected), and VC [K]> input ≧ VC
If [J], [10 ₂ ] is set in the RF register 44.
If (2 ₁₀ ) is substituted (first + second in the specific group is selected) and VC [J]> input ≧ VC [I], then RF
[01 ₂ ] (1 ₁₀ ) is assigned to the register 44 (first + first in the specific group is selected), and if VC [I]> input, [00 ₂ ] (0 ₁₀ ) is assigned to the RF register 44. (The first + 0th in the specific group is selected).

That is, this selection operation is performed by inputting 1
A 6-bit variable length code string and a variable length code in a specific group (for example, [11111 when the specific group is G2].
1011000000 ₂ ], [1111110111
100000 ₂ ] [11111111011010000
₂ ] and [1111111011011000 ₂ ]), and a variable length code having a matching value, or a variable length code having a smaller value than the input 16-bit variable length code string and the difference between them is the smallest. It is nothing but specifying.

For example, the input 16-bit variable length code string is [111111101011] as in the case of phase 1.
[0111 ₂ ], there is no variable length code in the group G2 that completely matches this input sequence, but within the group G2 that satisfies the condition that the value is smaller than this input sequence and the difference between them is the smallest. As a variable length code,
Address 9 [11111111111100000 ₂ ]
Is applicable.

Therefore, in the case of this example, (cp2, cp
1, cp0) = (0,0,1), and from Table 2 above, (g
1, g0) = (0,1), the RF register 44
At the position within the group of the variable length code at address 9 (start +
[01 ₂ ] (that is, 1 ₁₀ ) indicating the first) is set. Operation of Phase 3 In this phase, the original code is obtained using the results of Phases 1 and 2 above.

First, in step 66, the address of the variable length code specified in phase 2 is generated. The generation formula is K = RE × 4 + RF. However, RE × 4 is the start address of the group specified in phase 1, and RF is the position within the group of the variable length code specified in phase 2. For example, Phase 1
In the case where the group G2 is specified in step 1 and the first + 1th variable length code in the group G2 is specified in phase 2, RE × 4 is 8 ₁₀ and RF is 1 ₁₀ .
The address K becomes 9 ₁₀ .

Then, in step 67, VC is read from the first table and the second table according to the address K.
Read [K], VL [K] and BP [K], and
[K] is set in the RB register 28 and VL [K] is set to R
The C register 29 is set, BP [K] is set in the RD register 30, and the input sequence is set to the RA register 2
Set to 7.

Next, at step 68, the address of the third table is generated. The generation formula is (RA-RB) × 2 ^RC-15 + RD where RA: value of RA register 27 (input sequence) RB: value of RB register 28 (specified variable length code) RC: value of RC register 29 (Code length information) RD: The value (identification information) of the RD register 30, and this generation formula calculates the difference between the input sequence (RA) and the specified variable length code (RB), and the bit of the difference. The length is adjusted according to the code length information (RC), and the sum of the difference after the bit length adjustment and the identification information (RD) is obtained.

In practice, the difference calculation is performed by the subtracter (difference calculation means) 31 of FIG. 3, the bit length adjustment is also performed by the shifter (bit length adjustment means) 32 of FIG. 3 adder (sum operation means) 33. For example,
The input sequence (RA) is the same as in Phases 1 and 2 [1111
111010110111 _2] (hexadecimal FEB7 ₁₆₎
Then, the specified variable length code (RB) is [1111
110111100000 _2] (hexadecimal FDE0 ₁₆₎
Since the code length information (RC) in this case is 11 ₁₀ and the identification information (RD) is 16 ₁₀ , (RA-RB) × 2
^{The RC-15} term is D7 ₁₆ × 2 ^-4 = D ₁₆ .

Therefore, since D ₁₆ is 13 ₁₀ in decimal, K = 13 ₁₀ + RD = 13 ₁₀ +16 ₁₀ = 29 ₁₀ and the address 29 of the third table, that is, the code 3
0 is read. The operations of the above phases 1 to 3 are repeated until all the bits of the variable length code string are exhausted. However, in the second and subsequent operations, y is calculated from the beginning of the variable length code string.
Bit (y is the value of RC register 29 of the previous round + 1)
Only the remaining 16 bits discarded are treated as a new input sequence. If the remaining variable length code is less than 16 bits, dummy bit (0) is added after the input sequence.

For example, if the original variable length code string is [1111]
1110101101111010 ₂], Then
The value (code length information) of the RC register 29 is 11 times._TenAnd
11_Ten+1, that is, discard 12 bits from the beginning
Left over [01111010 ₂16 bits of
This is the second new input sequence. Here, 16 bits
8 dummy bits (0) are added to the back.
In addition, [01111010000000000000₂]
It

According to this input sequence, first, the phase 1
(Cp2, cp1, cp0) = (0,0,0) is obtained with (2) and (g1, g0) = (0,0) from the previous table 2,
The specific group becomes G0 and [00
₂ ] is set, and in the next phase 2, (cp2, cp
1, cp0) = (0,0,0) is obtained, and from Table 2 above, (g1, g0) = (0,0), so that the specific variable length code is the first + 0th (address 0) of the group G0. Then, [00 ₂ ] is set in the RF register 44. Then, in the last phase 3, VC [0] of the first table,
VL [0] and BP [0] of the second table are referred to,
RA register 27, RB register 28, RC register 2
9 and the RD register 30 are set to the following values.

RA = [0111101000000000 ₂ ] (16
7A00 ₁₆ ) RB = [0000000000000000 ₂ ] (16
0000 ₁₆ ) RC = 0 ₁₀ RD = 0 ₁₀ Therefore, the reference address K of the third table in the second operation is K = (RA-RB) × 2 ^RC-15 + RD = 7A00 ₁₆ × 2 ^-15 +0 = 0, and eventually the code 1 is extracted from the third table.

In the third operation, the RC register 2 of the previous operation is used.
Since the value of 9 (code length information) is 0 ₁₀ , 0 ₁₀ +1, that is, the remaining 1 bit from the beginning [1111010
16 bits of ₂ ] are used as a new input sequence for the third time. Here, since it is less than 16 bits, 9 dummy bits (0) are added at the end of [111101000
0000000 _2] and.

According to this input sequence, first, the phase 1
(Cp2, cp1, cp0) = (0, 0, 1) is obtained from (2) and (g1, g0) = (0, 1) from the previous table 2,
The specific group becomes G1 and [01
₂ ] is set, and in the next phase 2, (cp2, cp
1, cp0) = (0,0,0) is obtained, and from Table 2 above, (g1, g0) = (0,0). Therefore, the specific variable-length code is the first + 0th (address 4) of the group G1. Then, [00 ₂ ] is set in the RF register 44. Then, in the final phase 3, VC [4] in the first table,
VL [4] and BP [4] of the second table are referred to,
RA register 27, RB register 28, RC register 2
9 and the RD register 30 are set to the following values.

RA = [1111010000000000000 ₂ ] (16
F400 _{16 in} radix RB = [1111000000000000000 ₂ ] (16
Proceeds in _{F000 16) RC = 6 10 RD} = 4 10 Therefore, the reference address K of the third table in the third operation, K = (RA-RB) × 2 RC-15 + RD = 0400 16 × 2 -9 +4 = 6, and eventually the code 7 is extracted from the third table.

As described above, according to the present embodiment, the input sequence [11111110101101101111010] given as an example is used.
To (FEB7A ₁₆ in hexadecimal representation) _2], by repeating 3 times of operations, the original code sequence [code 30, code 1, correctly reproduced code 7], obtained similar data decompression function and the conventional example In addition to the above, a unique effect that the table capacity can be significantly reduced can be obtained.

That is, as shown in FIG. 4, only 13 types of variable length codes need to be stored in the first table, and the same type of code length information and identification information can be stored in the second table. Good. This indicates that the VC memory 20, the VL memory 21, and the BP memory 23 used as the first and second tables have a capacity of 16 W, which is sufficient. FC used as the third memory
The memory 34 needs a capacity for all kinds of original codes, but the capacity is 256 W at most.
16 + 16 + 16 + 25 even if the capacity of one memory is combined
Since 6 = 304 W, the capacity can be much reduced compared to the conventional 64 kW.

In this embodiment, the comparators 23 to 25,
Address determination circuit 26, registers 27 to 30, subtractor 3
1, an additional circuit such as the shifter 32 and the adder 33 is required. However, even if the cost increase due to these additional circuits is taken into consideration, the cost reduction effect of the memory is remarkably large, so that the cost reduction of the entire device is obviously reduced. Can be planned.

[0058]

According to the present invention, since it is configured as described above, the scale of the data expansion conversion table can be reduced, the memory capacity can be reduced, and the cost can be reduced.

[Brief description of drawings]

FIG. 1 is a principle configuration diagram (1/2) of the present invention.

FIG. 2 is a principle configuration diagram (2/2) of the present invention.

FIG. 3 is an overall configuration diagram of an embodiment.

FIG. 4 is a conceptual diagram of a first table, a second table and a third table according to an embodiment.

FIG. 5 is a configuration diagram of an address determination circuit according to an embodiment.

FIG. 6 is a flowchart showing the operation of one embodiment.

FIG. 7 is a conceptual diagram of a data compression conversion table using a variable length code.

FIG. 8 is a configuration diagram of a main part of a system including a data compression unit and a decompression unit, such as data processing, image processing, or information communication.

FIG. 9 is a conceptual diagram of a conventional variable length code decoding circuit.

FIG. 10 is a conventional data expansion conversion table diagram.

[Explanation of symbols]

 1: First table 2: Second table 3: Cutting means 4: First comparing means 5: First selecting means 6: Second selecting means 7: Third selecting means 8: Second comparing means 9: Fourth selecting means 10: Fifth selecting means 11: Sixth selecting means 12: Difference calculating means 13: Bit length adjusting means 14: Sum calculating means 15: Third table

Claims (4)

[Claims] 1. A variable-length code decoding circuit for decoding a variable-length code having a length of 1 to 2 ⁿ bits, a table for holding the smallest code of each length of the variable-length code in the order of the code length, and 2 ^m. -1 (however, m = 1, 2, ...) Comparators are provided, and 2 ^m −1 elements are read from the table at one time,
Each of the comparators performs a magnitude comparison with the variable length code input and repeats the comparison operation n / m times to obtain the i th table element ≦ the variable length code input <i + 1 th table element. A variable-length code decoding circuit characterized in that the length of the code at the beginning of a variable-length code input is obtained by finding a table element. 2. A variable-length code decoding circuit for decoding a variable-length code having a length of 1 to 16 bits, wherein a table holding the smallest code of each length of the variable-length code in the order of the code length and 3, Of the i-th table element by reading out three elements at a time from the table, performing a magnitude comparison with the variable-length code input in each comparator, and repeating the comparison operation twice. <Variable-length code input <i + 1th table element The variable-length code is characterized in that the length of the leading code of the variable-length code input is found by finding the i-th table element that satisfies the condition. Decoding circuit. 3. A variable length code decoding circuit for decoding a variable length code, comprising an FC table holding an original code, a VC table holding the smallest code of each length of the variable length code in order of code length, A VL table holding the code length corresponding to the VC table, a BP table holding the address of the FC table corresponding to the VC table, three comparators,
It includes a shifter, an adder, and a subtracter. In the first stage, three elements are read from the VC table at the same time, and three comparators perform a magnitude comparison with the variable length code input. It is determined which of the four groups belongs to, and in the second stage, the three elements of the group determined in the first stage in the VC table are read out and the three comparators compare the size with the variable length code input. The comparison is performed to determine which element of the VC table the variable length code input corresponds to. In the third stage, the VC table element, the VL table element and the BP table element corresponding to the variable length code input are determined. Read, the difference between the input value of the variable length code and the read value of the VC table is obtained by the subtracter, and further, the shifter performs a shift according to the read value of the VL table, and the shift result is read by the BP table. F was value by adding in the adder
The address of the C table is obtained, and the original code is obtained by reading the element of the FC table at that address.
A variable length code decoding circuit, characterized in that the start position of the next variable length code is determined from the read value of the L table. 4. A variable-length code whose code length does not match with all other variable-length codes among the variable-length codes corresponding to M original codes in a one-to-one correspondence, and the smallest in the same code-length group. A first table (1) in which variable-length codes having values are arranged in ascending order and the arranged variable-length codes are stored in group units, and code length information corresponding to each element of the first table (1) is shown. At the same time, a second table (2) in which predetermined identification information is assigned to each element of the first table (1) and stored, and from the beginning of the input variable length code string or from a specified code length +1 to a maximum code length The cutting-out means (3) for cutting out the length corresponding to the above, the output of the cutting-out means (3) and the variable length code of the minimum value in the group stored in the first table (1) are compared, and the cutting-out means (3) Variable length code or cut-out means (3 First comparing means (4) for specifying a group of the first table (1) including a variable length code having a smaller value than the output of the above and a difference therebetween is the group specified by the first comparing means (4). First selecting means (5) for selecting all variable length codes in the group, and second selecting means (6) for selecting all code length information in the group specified by the first comparing means (4), The output of the cutting means (3) and the output of the first selecting means (4) are compared with the third selecting means (7) for selecting all the identification information in the group specified by the first comparing means (4). And a second comparing means (8) for specifying a variable length code whose value matches the output of the cutting means (3) or a variable length code having a smaller value than the output of the cutting means (3) and a minimum difference. , Is the variable length code specified by the second comparing means (8) being output by the first selecting means (5)? Fourth selecting means for selecting from (9)
A fifth selecting means (10) for selecting one code length information corresponding to the variable length code specified by the second comparing means (8) from the output of the second selecting means (6); Sixth selection means (11) for selecting one piece of identification information corresponding to the variable length code specified by the means (8) from the output of the third selection means (7), the output of the cutout means (3) and the Difference calculating means (12) for calculating the difference from the output of the fourth selecting means (9), and bit length for adjusting the bit length of the output of the difference calculating means (12) according to the output of the fifth selecting means (10). Adjustment means (1
3), the output of the bit length adjusting means (13) and the sixth selecting means (1
1) is provided with a sum calculation means (14) for calculating the sum with the output, and a third table (15) for storing all the original codes, and the original code of the third table (15) is a corresponding variable Those having the same length of the long code word are stored in the memory area of consecutive addresses in ascending order of the value of the variable length code, and the predetermined information is stored in the memory area corresponding to each code length in the third table (15). A variable length code decoding circuit characterized in that it is determined so as to indicate the first address, and the address of the third table (15) is determined by the sum operation means (14).