JP2537551B2 - Variable length code decoding circuit - Google Patents

Description

The present invention relates to a variable length decoding circuit for decoding a variable length code string represented by a code having a different length for each information source symbol.

<Prior Art> Generally, in an image encoding / transmission apparatus in which input information is extremely large, information is compression-encoded to improve processing efficiency and transmission efficiency. For example, in the Huffman coding method, attention is paid to the fact that the occurrence probabilities of the respective information source symbols are different for each symbol, and a code having a code length approximately equal to the reciprocal of the information amount (native word probability) of each information source symbol. A table is created, symbols input from the information source are replaced with code words based on the code table, and a code string in which the redundancy of the information source is suppressed by compressing the code length is obtained.

The Huffman coding circuit is configured to read a code word and a code length from a code table stored in a ROM using an information source symbol as an address. On the other hand, the decoding circuit sends the codeword from the 0th node of the root to the 1st and 2nd nodes.
No. 3, No. 3, ... Radial branching by “0”, “1” toward the branch ends. Represented by a binary code tree as shown in FIG. 3, an attempt is made to decode this binary code tree “0”. The sequential logic circuit can be configured to obtain a storage address A, B, ... In an information source symbol table of an information source symbol which is a decoding result at a branch end by searching from a root according to a code string composed of "," 1 ".

Conventionally, as a variable length code decoding circuit of this type, for example, there is a decoding sequencer circuit 11 shown in FIG. The decoding sequencer circuit 11 uses an information source symbol table 2 in which information source symbols, which are decoding results, are stored in respective storage addresses, and one bit of a variable-length code string Di to be input, as a sequential address signal, and outputs "0". , A decoding table ROM 14 having a state transition table 13 forming a binary code tree (see FIG. 3) whose branch direction is determined by "1", and a node number of the above-mentioned binary code tree which is currently in progress. , The state register 5 which outputs this node number to the state transition table 13 as an address signal for obtaining the node to be transferred next, and the storage address of the branch end when the binary code tree reaches the branch end.
Symbol register 6 for latching and outputting the information source symbol D ₀ which is the decoding result output from the information source symbol table 2 shown in the left column of FIG. 2 based on A, B, ... (See FIG. 3)
Timing signal St from the timing control circuit 10
It is designed to operate in response to this.

Then, for example, when the variable length code sequence Di of “0110 ...” Shown in FIG.
From the table 13 pointing to the root (node 0) of the binary code tree in the figure, the first bit of the input code string is "0".
Therefore, the second node is the next node and the status register 5
Is output to and latched. Then, in the table above,
Since the latched node number 2 and the next bit "1" are input, the binary code tree advances by one node and the third node is read and latched. Further, the binary code tree reaches the branch end C by the latched node number 3 and the next input bit “1”, and based on this storage address C, the information source symbol table 2 (see the left column in FIG. 2) is read. The decoding result “0010” is read as the information source symbol D ₀ , latched in the symbol register 6 and output, and
A decoding end signal Sf indicating that the decoding is completed is output. At this time, the state register 5 is reset to the node number 0, and the state transition table 13 again points to the root of the binary code tree. The input code sequence is sequentially decoded by repeating such processing for each bit input in bit serial.

<Problems to be Solved by the Invention> Among the code words forming the actual variable-length code string, those having a long code length have a variable length part in the first few bits, and the remaining bits occupying most of them are predetermined bits. Often consists of a fixed number of parts.

However, since the conventional decoding sequencer circuit 11 is configured to process the input variable length code string bit by bit serially, when decoding a code word with a long code length, 1 for many fixed length parts
Since it is processed bit by bit, there is a disadvantage that decoding takes a long time. In addition, a large difference occurs in the decoding time with the short code word, the output of the decoding result varies temporally, and the processing load in the next stage increases, and the decoding sequencer circuit 11
There is a drawback in that not only the decoding efficiency of itself decreases, but also the processing efficiency of an image coding and transmitting apparatus using the same decreases.

Therefore, an object of the present invention is to reduce the difference in decoding time between long and short code words by providing a decoding circuit with a function of decoding several bits in parallel in addition to a function of serially decoding each bit. It is to provide a variable length code decoding circuit capable of improving the decoding high rate and the processing efficiency of a data processing device using this decoding circuit.

<Means for Solving the Problem> In order to achieve the above object, the variable-length code decoding circuit of the present invention uses an input variable-length code sequence in which each information source symbol is coded with a code of a different length, In the one which sequentially decodes and outputs the original information source symbol, the information source symbol table storing the above information source symbols in the respective storage addresses, and the node number on the route side to be inputted and 1 bit of the inputted code are designated. The node number on the branch end side to be moved next is stored in the address to be transferred, and the branch end is the storage address in the information source symbol table of the information source symbol that is the decoding result. A state transition table forming a binary code tree allocated for an input code in which fixed length data of a predetermined bit is added to variable length data, and a node currently in progress of the binary code tree A state register that stores the number and outputs this node number to the state transition table as the root side node number, and when the node number stored in the state register does not reach the specific node number, bit serially The variable-length code string input is serially output to the state transition table, and when the node number reaches the specific node number, the variable-length code string input bit serially is parallel-converted by the predetermined bits. Then, a shift register for outputting to the above state transition table is provided.

<Operation> At the address specified by the node number currently in progress input from the status register and 1 bit of the input code string,
The binary code tree that stores the node number on the side of the branch end to be moved next and the branch end is the storage address in the information source symbol table of the information source symbol that is the decoding result is variable below that specific node number. It is allocated for an input code word in which fixed length data (predetermined bit) is added to long data, and is configured by a state transition table. Now
It is assumed that the codeword including the variable length data and the fixed length data is input to the state transition table. Then, the state transition table pointing to the root (node 0) of the binary code tree has the next node number on the branch end side from the address designated by the first 1 bit “0” or “1” of the code word. Is read and output to the status register for latching. Next, the state transition table stores the next 1-bit “0” or “1” of the code word and the next node number on the branch end side from the address specified by the next node number latched in the state register. Read and output this to the status register for latching. When such an operation is repeated for the variable length data of the input code word, the binary code tree reaches the above specific node number, and this node number is latched in the status register. Then, the shift register, which has been outputting the input codeword as it is in bit-serial fashion, batch-parallel-converts the fixed-length data of a predetermined bit, which is input thereafter, and outputs it to the state transition table. The address data input in parallel is 10 with the above specified node number.
It is converted by a binary decoder or the like, the branch end of the binary code tree is immediately specified, the information source symbol as the decoding result is read from the information source symbol table according to the storage address of the branch end, and it is immediately output. Then, the state register is reset to the 0th node indicating the root of the binary code tree, and the state transition table shifts to the decoding process of the subsequent code word. When the codeword is composed of only variable length data, the binary code tree is traced bit by bit toward the branch end.

<Examples> Hereinafter, the present invention will be described in detail with reference to illustrated examples.

FIG. 1 is a block diagram showing an embodiment of a variable length code decoding circuit of the present invention. This decoding circuit 1 uses the state transition table 13 of the circuit described in FIG. 5 as a new state transition table 3 forming a binary code tree as shown in FIG. The shift register 7 capable of converting Di into parallel by 3 bits, and the shift signal receiving the control signal Sc output from the state transition table 3 when the binary code tree reaches a specific node number (node 5 in this case) A shift register control circuit 8 for switching the register 7 to a parallel conversion operation, and the shift register 7
From the bit serial or 3-bit parallel data and the current node number input from the state register 5 are decoded, and the storage location of the node number of the binary code tree to be transferred next is stored in the state transition table 3. An address converter 9 for outputting an address signal to be expressed is added, and the same blocks as those in FIG. 5 are denoted by the same reference numerals and the description thereof will be omitted.

As shown in FIG. 3, the binary code tree formed by the state transition table 3 has variable length data “00” of 2 bits in the fifth node and below and fixed length data “00” of 3 bits following the variable length data “00”.
Branch ends F to M, which are allocated for an input codeword (see FIG. 2) consisting of 0 "to 111" and having a code length of 5 bits, are variable length data and a fixed length. It is the storage address of the information source symbol table 2 which stores the information source symbol D ₀ which is the decoding result corresponding to each input code Di made of data. In addition, the other branch ends A of the binary code tree
E is the storage address of the decoding result D ₀ for the input codeword Di from only the variable length data.

 The operation of the decoding circuit 1 having the above configuration will be described next.

Now, it is assumed that the variable length code string Di "0001010 ..." As shown in FIG. 4 (b) is input to the shift register 7. The binary code tree (see FIG. 3) of the state transition table 3 points to the 0th node of the first root, and the control signal Sc
Is not output, the shift register 7 outputs the input code string as it is to the address converter 9 in bit serial. With the address signal output from the address converter 9 by the first bit "0" of the input code string Di, the second node is read from the state transition table 3 according to the binary code tree and latched in the state register 5, By the address signal similarly output by the latched node number 2 and the next input bit "0", the fifth node on the branch end side is further read and similarly latched. At this time,
Since the binary code tree has reached the specific node number, node 5, the state transition table 3 outputs the control signal Sc, and the shift register control circuit 8 receiving this outputs the shift register 7
To parallel conversion operation. Then, the shift register 7 batch-parallel-converts the 3-bit fixed-length data “010” that is subsequently input and outputs it to the address converter 9. The address converter 9 uses the parallel data “010” and the node number 5 latched in the state register 5 to directly specify the corresponding branch end F without passing through the 6th and 8th nodes. 3 and the information source symbol D ₀ “0111” as a decoding result is read from the information source symbol table 2 based on the storage address F read from the table 3. Thus, the decoding table ROM4, together with the decoding end signal Sf, is the information source symbol D ₀ “01” which is the decoding result of the input codeword Di “00010”.
11 "is output to the symbol register 6, which is latched and output to the outside.
Is reset to the 0th node indicating the root of the binary code tree, the state transition table 3 stops the output of the control signal Sc, and shifts to the decoding process of the subsequent input code string “10 ...”.

When the input code word Di consists of only variable length data, the binary code tree of FIG. 3 is traced bit by bit toward any one of the branches A to E to perform decoding. Become.

As described above, according to the above-described embodiment, when decoding the code word Di composed of variable-length data and fixed-length data included in the actual variable-length code sequence, , The parallel conversion by the shift register 7 and the direct designation of the branch end address of the binary code tree in the state transition table 3 by the address converter 9 immediately obtains the corresponding information source symbol D ₀ as the decoding result, and the decoding time To significantly reduce the decoding time difference between the long and short code words included in the variable-length code string, thereby significantly improving the decoding efficiency of the decoding circuit and the processing efficiency of the data processing device using the decoding circuit. You can

Needless to say, the present invention is not limited to the illustrated embodiment.

<Effects of the Invention> As is apparent from the above description, the variable-length code decoding circuit of the present invention generates a binary code tree in which an input codeword composed of variable-length data and fixed-length data is assigned a specific node number or less. It is composed of a state transition table, and when the decoding of the variable length data bit by bit reaches this specific node number of the binary code tree, the shift register is used to batch-parallel convert the fixed length data and The data and the node number stored in the state register directly specify the address of the branch end of the binary code tree of the state transition table, and the information that is the decoding result immediately from the information source symbol table based on the storage address stored at this address. Since the source symbol is read and output, a comparatively long code consisting of variable-length data and fixed-length data included in many actual variable-length code strings is used. It is possible to significantly reduce the decoding time of the code word, reduce the difference in the decoding time between the long and short code words, and significantly improve the decoding efficiency of the decoding circuit and the processing efficiency of the data processing device using these.

[Brief description of drawings]

FIG. 1 is a block diagram showing an embodiment of a variable length code decoding circuit of the present invention, FIG. 2 is a diagram showing a code table of the above embodiment, and FIG. 3 is a diagram showing a binary code tree of the above embodiment. FIG. 4 is a diagram showing an example of an input variable length code sequence, and FIG. 5 is a diagram showing a conventional variable length code decoding circuit. 1 ... Decoding circuit, 2 ... Information source symbol table, 3 ... State transition table, 4 ... Decoding table ROM, 5 ... Status register, 7 ... Shift register, 9 ... Address converter, Di ... Input Code string, D ₀ …… Source symbol, Sc …… Control signal.

Claims (1)

(57) [Claims] 1. A variable length code decoding circuit for sequentially decoding an input variable length code sequence in which each information source symbol is coded with a code having a different length, and outputting an original information source symbol, An information source symbol table that stores symbols in each storage address, and the input node number on the root side and the input code 1
The address specified by the bit stores the node number on the branch end side to be moved next, and the branch end is the storage address in the information source symbol table of the information source symbol that is the decoding result, and the specific node number The following stores a state transition table that constitutes a binary code tree allocated for an input code in which fixed-length data of a predetermined bit is added to variable-length data, and a node number of the binary code tree currently in progress. Along with this, a state register that outputs this node number to the state transition table as a node number on the root side, and a variable that is input in bit serial when the node number stored in the state register does not reach the specific node number The long code string is serially output to the state transition table, while when the node number reaches the specific node number, Variable length code decoding circuit of the variable-length code sequence to parallel conversion by the predetermined bits comprising the shift register output to the state transition table which is input to Toshiriaru.