KR19990050486A - High-speed processing variable-length codec device - Google Patents

Abstract

Speed variable-length codec apparatus for codewording or decoding input data into a variable-length codeword on the basis of a Huffman code structure. The codec apparatus includes a boundary detection unit for detecting a boundary of variable length codewords according to a Huffman code structure. The boundary detection unit detects the length of the variable length codewords from the outside or the length of the variable length codewords of the storage codewords from the encoding memory. The variable length detection unit is operable to determine whether the stored codeword is in the stored codeword based on the selected codewords having m bits in the stored codeword and the node codeword of the terminal node of level n determined by the selected codeword in the Huffman code structure The length of the variable length codeword of the variable length codeword is detected. The codec apparatus includes an encoding packing unit for detecting a variable length codeword in a stored codeword in response to a length of a variable length codeword detected by the variable length detecting unit, and a decoding unit for decoding the detected variable length codeword into an address And a memory in which a code word is stored.

Description

High-speed processing variable-length codec device

The present invention relates to a fast processing variable length codec device capable of coding input data into a variable length codeword or decoding an input variable length codeword based on a Huffman code structure.

Generally, a variable length codec is a coding technique used for data compression without loss. Variable length coding converts all possible input data (or symbols) into variable length code words according to their probability of occurrence, thereby reducing the average code length. Variable-length coding assigns a codeword of a shorter length to data of a higher frequency and a longer-length codeword of data of a less frequent variable-length coding to a library of all possible source codewords, The average word length of the data coded by the code word is made shorter than the average word length of the data before coding, thereby realizing data compression as a result.

The most widely used variable length coding method is a Huffman coding method. The Huffman coding scheme implements a Prefix-free Variable Length Code by applying known data to the Huffman code tree according to the frequency of occurrence.

One example of a variable length coding device is disclosed in U.S. Patent No. 3,675,212 to Joseph. The variable length coding apparatus proposed by Joseph assigns variable length codewords to all possible symbols and stores each variable length codeword into memory in the memory as an address and stores the length of the variable length codeword in memory And when the symbol is input, the variable length code corresponding to the symbol and its length are read from the memory and coded.

The variable length decoding apparatus decodes data converted into a variable length codeword. In order to decode each variable length codeword into an original source symbol, a variable length codeword must first be derived from the received bit string. However, until the variable length codeword is decoded, the position of the start bit of the next codeword is unknown, and such decoding characteristics are invited to use multiple pipeline hardware in the production of the decoding device. Thus, typically, the variable length decoding apparatus is more complicated than the encoding apparatus.

There are many ways to decode a bitstream of a variable length codeword. One of the most commonly used is the tree-search algorithm. Variable length codes can be represented by a tree with code words in a leaf called a terminal node. Decoding starts from the root of the code tree and is guided by the received bitstream, leading to one of the two branches at each node. When reaching the leaf, the end of the code word is detected and is segmented from the remaining column. This type of decoder includes logic circuitry corresponding to the tree and control circuitry traversing the code tree. This method requires a bit-by-bit search through the code tree for each decoded symbol, so that the rate is slow for each symbol for which the bit-room-bit search through the tree is decoded, Long decode times are required for long codewords. In typical applications, input symbols are represented by a plurality of bits. The rate at which the received bits are shifted to the decoder is a multiple of the average rate of the decoded data. Thus, a decoder based on a tree-search must operate at a multiple of the output data rate.

However, the total sample rate combining luminance and signals for digital transmission of high-definition television requires about 100 MHz, and when a variable length coding is used, the maximum length codeword is typically 16 bits, so the bit- To detect the codeword at sample rate, the shift typically needs to be shifted at a rate of 1.6 gigabits per second. However, considering the recent IC manufacturing technology, it is difficult to implement such a high-speed decoder.

Meanwhile, various apparatuses have been proposed for decoding a stream of variable length code words. The structure of the variable length decoding apparatus proposed so far can be divided into sequential decoding and parallel decoding. First, sequential decoding is a method of decrypting bitstreams from the beginning in order, and can be divided into a constant speed input structure, a constant speed output structure, and a variable input / output structure. In the constant speed input structure, There is one slow problem. In addition, a variable length decoding apparatus of a constant rate output structure is a structure proposed by M. T Sun of Bell Core and packs the input bit string by a maximum code word length and stores it in a ROM table. In decoding, a codeword is found, Shifted to the barrel shifter by the length, and then the next code word is found (Bell Core, USA Patent No. 5173695). That is, since one codeword is decoded in one cycle, it is a constant output variable length decoding apparatus that is faster than the constant rate input structure.

It is an object of the present invention to provide a high-speed variable length codec device capable of coding input data into a variable length codeword or decoding an input variable length codeword without a memory storing a length of a variable length codeword.

According to an aspect of the present invention, there is provided a variable length codec comprising: a) a buffer for storing an encoded bit stream input from a source; b) storing a decoded bit string from the outside, outputting the stored decoded codeword as a maximum length of the variable length codeword, and decoding the decoded codeword in the decoded bit string according to the length of the variable length codeword included in the decoded bit string A decoding packing unit 130 for outputting bits from the next bit; c) storing variable length codewords defined for each possible symbol for each possible symbol on the basis of the Huffman code structure, and for storing the symbol (X) in the buffer (110) A coding memory 150 for outputting a stored code word M (X) including a variable length code word VLW (X) corresponding to the variable length code word X; d) a decoding memory for storing the decoded codeword as the address of the location of the terminal node in the Huffman code tree; e) selection means 160 for selectively outputting the stored codeword M (X) from the memory 150 and the encoding bit stream ECS _i from the decoding packing unit 130 in response to a control signal from the outside ); f) at the level, and each level in a Huffman code tree of a bit string (CW) selection code word (BW _m) and said selection code word (BW _m) are generated by selecting the m bits in the input from the selection means A variable length detector (200) for detecting a length of the variable length codeword included in the bit string (CW) based on the number of terminal nodes; g) detecting a position of a variable length codeword included in the bit string (CW) in the Huffman tree in response to the length of the variable length codeword detected by the variable length detector (200), and detecting the detected position An address generator 600 for providing the decoded data to the decoding memory; And h) detecting a variable length codeword (W ₂ ) in the bit string (CW) in response to a length (LEG) of a variable length codeword detected by the length detector (220) And an encoding / coding unit 310 for outputting a word W ₂ , where m is 1, 2, 3 .... K, and K is a maximum length of a variable length codeword.

According to the present invention, by detecting the length of the variable length codeword according to the Huffman code structure from the stored codeword generated from the memory, the length of the variable length codeword is not stored in the memory, The length of the variable length codeword to be coded or inputted can be detected to decode the variable length codeword into the fixed length codeword.

1 is a block diagram illustrating a variable-length codec apparatus according to an embodiment of the present invention.

Fig. 2 is a configuration diagram showing an example of the boundary detection unit shown in Fig. 1. Fig.

3 is a configuration diagram showing an example of the operation unit shown in FIG.

4 is a configuration diagram showing an example of the length detector shown in Fig.

Fig. 5 is a circuit diagram showing an example of the coding packing unit shown in Fig. 1. Fig.

6 is a diagram for explaining a Huffman code structure.

Description of the Related Art

110, 130: buffer 150:

160: Switch 210:

220 Length Detection Unit 310: Coding Packing Unit

610: Multiplex 620: Register portion

412, 422, 424, 432: Latches 630, 420:

421, 650: adder 510: code selector

520: level detector 530:

540: boundary value generator

1 is a block diagram illustrating a high-speed processing variable-length codec apparatus according to an embodiment of the present invention.

1, the variable length codec apparatus includes a buffer 110, a decoding packing unit 130, a coding memory 150, a switch 160, a variable length detecting unit 200, an encoding packing unit 310, Unit 600, and a decryption memory 660.

The buffer 110 stores an encoded bit stream (hereinafter referred to as a symbol) input from the outside in serial or parallel and outputs the symbol X to the encoding memory 150 (not shown) in response to a control signal .

The encoding memory 150 stores the stored codewords M (X). The encoding memory 150 stores the stored codewords as the maximum length of variable length codewords according to the symbols or the addresses corresponding to the symbols. Therefore, when a certain symbol is input to the encoding memory 150, the encoding memory 150 generates a stored code word M (X) corresponding to the symbol. Since the code length of the stored codeword is the maximum length of the variable length codeword, the stored codeword is composed of a variable length codeword and stuffing bits.

For example, when the maximum length of the variable length codeword is K bits and a symbol [X] is input to the encoding memory 150, the encoding memory 150 generates a storage codeword M (X) And provides the stored code word M (X) to the first input terminal S1 of the switch 160 and the encoding packing unit 310, respectively.

The decryption packing unit 130 stores a decoded bit string VLW input from the outside and outputs the stored decoded code word VLW as a maximum length of a variable length codeword, To the second input terminal (S2) of the switch (160) according to the length of the code word, from the bit subsequent to the bits decoded in the decoded bit string.

The switch 160 selects one bit string from the bit string input through the first and second input terminals S1 and S2 and provides the selected bit string CW to the variable length detector 200. [

8, the variable length detecting unit 200 detects the length LEG (X) of the variable length codeword included in the bit string CW from the switch 160 based on the canonical Huffman code tree, ).

The variable length detecting unit 200 sequentially selects 1 bit to K bits in the bit string CW to detect the length LEG (X) of the variable length codeword included in the bit string CW, Words (BW _m ). The selected code words (BW _m ) then detect the levels defined by the Huffman code tree and the number of terminal nodes at each detected level. The length LEG (X) of the variable length codeword included in the bit string CW is detected based on the selected codeword BW _m , the levels, and the number of terminal nodes at each detected level do.

The decoding memory 660 stores the decoded codeword according to the address corresponding to the position of the terminal node in the Huffman code tree.

The address generator 600 detects the position of the variable length codeword included in the bit string CW in the Huffman tree in response to the length of the variable length codeword detected by the variable length detector 200 , Generates the address in response to the detected location, and provides the generated address to the decryption memory 660.

1, the variable length detector 200 includes a boundary detector 210 and a length detector 220 to detect the length LEG (X) of the variable length codeword.

The boundary detector 210 sequentially selects 1 bit to K bits of the bit string CW from the switch 160 in the storage codeword M (X) to generate K selected codewords BW (X) ₁ , BW (X) _2, to generate a _{BW (X) 3, ...,} BW (X) K. Also, the boundary detecting unit 210 detects the number of terminal nodes at the level in the Huffman code structure corresponding to each of the selected code words BW (X) _{m = 1, 2, ..., K.}

Then, the boundary detector 210 compares each of the selected code words BW (X) _{m = 1, 2, ..., K} with the number of terminal nodes at each level, and as a result, CW) the variable-length code words VLW (X) and the stuffing bits detecting a boundary between, and to generate a boundary value MSB (X) _m as the edge detection result, the resulting boundary value MSB (X) included in _m To the length detector 220.

The length detector 220 detects the length LEG (X) of the variable length codeword included in the bit string CW based on the boundary value MSB (X) _m from the boundary detector 210, (310).

2 is a circuit configuration diagram showing an example of the boundary detection unit 210 shown in FIG.

2, the boundary detector 210 preferably includes a code selector 510, a level detector 520, a calculator 530, and a boundary value MSB (X) _m to detect the boundary value MSB And a generating unit 540.

The code selector 510 generates the selected code words BW (X) _m by sequentially selecting from 1 to K bits in the stored code word M (X) from the encoding memory 150, And provides the codewords BW (X) _{m = 1, 2, ..., K} to the level detector 520 and the arithmetic unit 530, respectively.

When a predetermined selection code word BW (X) _m is input from the code selection unit 510, the level detection unit 520 receives the selected code word BW (X) _m from the code selection unit 510 And detects the level m in the Huffman tree of the selected code word BW (X) _m in response. Then, the number of terminal nodes at each level from the route to the detected level m is detected, a weight corresponding to each level is given to the number of terminal nodes, and the number of terminal nodes to which the weight is given is added , And level code words NW (X) _m .

That is, the sum of the weighted numbers for the level m defined by the selected code word BW (X) _m has the form as shown in the following Equation (1).

Here, j is rebael, and L _j in the Huffman code tree is the number of terminal nodes at level j.

The level detector 520 generates the level code word NW (X) _m by converting the sum WS (X) _m into a binary number and provides the level code word NW (X) _m to the arithmetic unit 530 do.

The operation unit 530 receives the level code words NW (X) from the level detection unit 520 at the selected code words BW (X) _{m = 1, 2, .., K} from the code selection unit 510 X) _{m = 1,2, .., K} is subtracted, and the result of the subtraction of position values LD (X) _{m = 1,2, .., K} the address generation unit 600 and the threshold generating part (540). The subtraction results LD (X) _{m = 1,2, .., K} are composed of bits of variable length codewords for each of the selected codewords BW (X) _{m = 1,} Whether or not it is.

3 is a circuit configuration diagram showing an example of the operation unit shown in Fig.

3, the operation unit 530 subtracts the level code word NW (X) _m from the level detection unit 520 in the selected code word BW (X) _m from the code selection unit 510 First to Kth subtractors 531 to 537, respectively.

The first through the K subtractors (531 to 537) are each of the selected code words BW (X) ₁ to the selected code words BW (X), the level codes in _K word NW (X) ₁ to level codeword NW (X ) _K and provides LD (X) ₁ to LD (X) _K as a result of the first to Kth subtraction to the boundary value generator 540.

The boundary value generator 540 generates the most significant bits MSB (X) _{m = 1, 2, ...} from the first through K th subtraction results LD (X) ₁ through LD (X) _K from the calculator 530 _{. ,} detects and _K, the detected MSB (X) _{m = 1,2, .., K} the threshold MSB (X) _{m = 1,2, ..,} provided to the length detection unit 220 as the _K . The boundary value MSB (X) _{m = 1, 2, .., K} represents the boundary between the stuffing bits of the stored codeword M (X) and the variable length codeword VLW (X).

1, the length detector 220 detects the boundary value MSB (X) _{m = 1} indicating the boundary between the stuffing bits of the stored codeword M (X) and the variable length codeword VLW (X) _{, 2, ..., K} to generate the length value LEG (X).

FIG. 4 is a circuit diagram showing an example of the length detector shown in FIG. 1. FIG.

Referring to FIG. 4, the length detector 220 includes K XOR gates.

The XOR gate 1 is "0" value and MSB (X) _1, and the n XOR gate is the exclusive-OR of MSB (X) _n-1 and MSB (X) _n. Where n is an integer from 2 to K.

The logic values generated by the K XOR gates are the length values of the variable length codeword VLW (X) of the stored codeword M (X), and the logic values generated by the coding encoding packing unit 310, Respectively.

Referring again to FIG. 1, the encoding and decoding unit 310 encodes the variable length code M (X) _i in the storage codeword M (X) _i in response to the length LEG (X) of the variable length codeword from the variable length detector 200, Detects the word VLW (X), and outputs the detected variable length codeword VLW (X) to the outside.

5, the encoding and packing unit 310 preferably includes an input unit 410, an accumulator 420, and an output unit 430. [

Referring to FIG. 5, the input unit 410 includes a first barrel shifter 411 and a first latch 412. The input unit 410 includes a first barrel shifter 411 and a first latch 412.

The first barrel shifter 411 of the input unit 410 receives the stored codeword M from the encoding memory 150 in response to the length value LEG (X) of the variable length codeword from the variable length detector 200 The first window bit string B ₁ is read by sliding the bit string of the first window bit string X and the first latch bit string from the first latch 412 to read out the K bit first window bit string B _1, To the first latch (412).

The first latch 412 is the first storing the window bit stream B _1, the first window bit string first latch bit string W ₁ of the first barrel shifter 411, to have the same bit value, and B ₁ And the output unit 430, respectively. Therefore, as described above, the bit streams of the first latch bit stream W ₁ and the storage codeword M (X) are input to the first barrel shifter in parallel.

5, the accumulator 420 includes an adder 421, a second latch 422, a subtracter 423, and a third latch 424. The adder 421 of the accumulator 420 receives the length value LEG (X) from the variable length detector 200 and the latch value L ₁ from the second latch 422 in the K-module (module-K) And provides the added value to the second latch 422. The adder 421 generates a carry signal C when the added value is K or more. The carry signal C is for informing the outside that the fourth latch 432 of the output unit 430 to be described later is filled with the bits of the variable code word M (X) _i .

The second latch 422 stores the addition value from the adder 421 and provides the stored addition signal to the subtracter 423 and the adder 421 as the latched value L ₁ , respectively. The subtractor 423 by subtracting the latched value L ₁ from the second latch 422 in the K = 6 ₁₀ variable-length The maximum length of the codeword to generate a subtraction value S _0.

The third latch 424 stores the subtracted value S ₀ and provides the stored subtracted signal S ₀ to the output unit 430 as a control signal L ₂ of the output unit 430.

The output unit 430 includes a second barrel shifter 431 and a fourth latch 432. The second barrel shifter 431 is responsive to the control signal L ₂ to output a bit string of the stored code word M (X) from the encoding memory 150 and a bit string of the stored code word M (X) from the first latch 412 of the input unit 410 The second window bit string B ₂ is generated by sliding the 2K bit string composed of the first latch bit string W ₁ of the first window bit string W ₁ and the generated second window bit string B ₂ to the fourth latch 432 do.

The fourth latch 432 stores the second window bit string B ₂ from the second barrel shifter 431 in the input order and stores the stored second window bit string B ₂ as the variable length code word W ₂ And outputs it to the outside.

1, the address generator 600 includes a multiplexer 610, the register unit 610, the fifth latch 630, a sixth latch 640, and an adder 650 .

The multiplexer 610 outputs one position value from the boundary detection unit 210 to the sixth latch 640 in response to the length of the variable length codeword from the length detector 220.

The register unit 610 stores the total number of terminal nodes before the corresponding level with respect to the codeword to be decoded in the Huffman code tree structure, And provides the stored total number of terminal nodes to the fifth latch 630.

The fifth latch 630 latches the total number of terminal nodes from the register portion 620 and provides the number of latched total terminal nodes to the adder 650.

The sixth latch 640 latches the position value from the multiplexer 610 and provides the latched position value to the adder 650.

The adder 650 adds the number of the total terminal nodes from the fifth and sixth latches 630 and 640 and the position value and outputs the added value to the decryption memory 660 as the address. The memory 660 sequentially stores the decoded codeword from the root of the Huffman tree according to the node position of the encoded codeword and outputs the decoded codeword Si in response to the addition value from the adder 650 .

Hereinafter, a variable length codec according to the present invention will be described in detail with reference to the accompanying drawings.

B, c, d, e, f, g, h] are generated from the data source through the buffer 110, 13, 12, 11, 5, 2, 1, and 1, the variable length codeword is allocated to the eight symbols according to the frequency of occurrence, as shown in FIG. The code values of the variable length codewords allocated to the eight symbols according to the Canonical Huffman code tree are shown in Table 1 below.

As shown in Table 1, the variable length codeword VLW (X) of 1 bit is allocated to the symbol [a] having the highest frequency based on the canonical Huffman tree structure, and the symbol [g, h] A variable length code word of 6 bits is allocated.

Symbol (X) The variable length codeword VLW (X) a 0 b 1 0 0 c 1 0 1 d 1 1 0 e 1 1 1 0 f 1 1 1 1 0 g 1 1 1 1 1 0 h 1 1 1 1 1 1

As shown in Table 2 below, the variable length codeword VLW (X) is stored in the coding memory 150 with each of the symbols X as an address. The variable length codeword VLW (X) is filled in the order from the most significant digit (MSB) to the least significant digit (NSB) of the memory cells of each unit of the encoding memory 150, and the variable length codeword VLW Stuffing bits (or do not care) are filled in the remaining space.

Accordingly, when the symbol X is input, the encoding memory 150 generates a stored code word M (X) having the input symbol X as an address.

Symbol (X) The stored data (MSB (X); MSB? LSB) a 0 X X X X X b 1 0 0 X X X c 1 0 1 X X X d 1 1 0 X X X e 1 1 1 0 X X f 1 1 1 1 0 X g 1 1 1 1 1 0 h 1 1 1 1 1 1

The coding memory 150 generates a bit string of [101XXX] stored as an address of the symbol X (c) from the buffer 110 as the stored code word M (c), as shown in Table 2 , The 6 bits of the storage codeword M (c) are supplied to the boundary detector 210 and the encoding packing unit 310 of the variable length detector 200 in parallel through the first input terminal S1 of the switch 160 Respectively.

The stored code word M (c) input to the variable length detector 200 is input to the code selector 510 of the boundary detector 210. When the stored code word M (c) is input to the code selection unit 510, the code selection unit 510 selects one or more bits from the stored code word M (c) select the 6-bit code words in order to select BW (c) _{m = 1,2,3 ...} and generating the _K, in which the selected code words generated BW (c) _{m1,2,3 ...} to the respective _K Level detector 520 and the arithmetic unit 530 of the boundary detection unit 210, respectively.

m BW (c) _m One BW (c) ₁ = 1 2 BW (c) ₂ = 10 3 BW (c) ₃ = 101 4 BW (c) ₄ = _{10 &lt}; RTI ID = 0.0 > 5 BW (c) ₅ = 10111 6 BW (c) ₆ = 101111

When the selected code word BW (c) _m is input from the code selection unit 510 to the level detection unit 520, the level detection unit 520 detects the selected code word BW (c) _m based on the Huffman code tree shown in FIG. Detects the number of terminal nodes from level 1 to _m of BW (C) _m , and generates a level code word NW (c) _m weighted according to each level as described above.

For example, when m = 3, the selected code word BW (C) ₃ = [101] is generated from the code selection unit 510 as shown in Table 3. At this time, Weights are given to each level, and the number of weighted terminal nodes is added to generate a sum as shown in Equation (2).

Where j is the level in the Huffman code tree and L _j is the number of terminal nodes at level j.

Then, the level detector 520 converts the sum WS (c) ₃ into a binary number to generate a level code word NW (c) ₃ = [0001000]. The level code word NW (c) _m for all selected code words BW (c) _m (m = 1,2, ..., 6) is shown in Table 4 below.

m NC (c) _m One 0 = 000000 2 2 = 000010 3 8 = 001000 4 14 = 001110 5 30 = 011110 6 62 = 111110

The level codeword NW (c) _m and selecting code words BW (c) _m have the above-level code word NW (c) _m and select code input on the operating section 530, if each input to the arithmetic unit 530 The words BW (c) _m are sequentially input to the first to sixth subtractors 531 to 536 of the operation unit 530, as shown in FIG.

The first to sixth subtractors 531 to 536 perform the function LD (c) _m as shown in the following Equation (3).

LD (c) _m = BW (c) _m -NW (c) _m

Therefore, the operation unit 530 generates the first to sixth subtraction results LD (c) _{m = 1, 2, ..., 6} as shown in Table 5 below.

m LD (c) _m MSB? LSB One One 2 0 3 One 4 111101 5 111001 6 110001

The first subtraction results LD (c) ₁ to the sixth subtraction result LD (c) ₆ outputted from the first to sixth subtractors 531 to 536 of the operation unit 530 with respect to the input symbol [c] And is provided to the boundary value generator 540.

The first to sixth subtractors 531 to 536 generate the first to sixth subtraction results LD (c) ₁ to LD (c) ₆ as shown in the following Equation (4).

= 0 ₁₀

= 1 ₁₀

= -3 ₁₀

= -7 ₁₀

= -17 ₁₀

Where b _i is the i-th bit value of the selected code word BW (c) _m , and L _j is the number of terminal nodes at level j.

The boundary value generator 540 detects the most significant bits MSB in the first subtraction result LD (c) ₁ to the sixth subtraction result LD (c) ₆ and outputs the bit values of the most significant bits MSB To the length detector 220 as a variable length codeword VLW (c) of the stored codeword M (c) and a boundary value MSB (c) indicating the boundary between the stapling codes.

4, each bit of the boundary value MSB (C) _{m = 1, 2, ..., 6} = [000111] input to the length detector 220 is divided into the first through (C) indicating the length VLG (c) of the variable length codeword VLW (c) of the symbol [c], as a result of which the length detector 220 outputs a length value LEG To generate a bit string [000100].

When the length value LEG (c) is input to the encoding and decoding unit 310, the encoding and decoding unit 310 encodes the variable length codeword M (C) in the storage codeword M (C) in response to the length value LEG Only the VLW (C) is detected, and the detected variable length code word VLW (C) is output to the outside.

Hereinafter, the operation of the coding and packing unit 310 will be described in more detail with reference to FIG.

The storage codeword M (X) is not input from the encoding memory 150 to the encoding packing unit 310 at time t = 1 and thus the first barrel shifter 411 of the encoding packing unit 310, A first window bit string B ₁ [xxxxxx] composed of do not care in response to the length LEG (x) of the variable length codeword [0 ₁₀ ] from the code length detector 220, To the first latch (412). A] for the symbol [a] generated from the encoding memory 150 when a stored codeword M (a) for the symbol [a] is generated from the encoding memory 150 at time t = 2, M (a) is input to the first barrel shifter 411 of the input unit 410 of the encoding packing unit 310 and the second barrel shifter 431 of the output unit 430, The length LEG (b) of the variable length codeword for the symbol [a] is input to the shifter 411 and the adder 421 of the accumulator 420 from the variable length detector 220, respectively.

The first barrel shifter 411 receives the storage codeword M (a) for the symbol [a] from the encoding memory 150 and the length LEG (a) of the variable length codeword from the variable length detector 220, If the input, input from the first latch bit string [xxxxxx] and the coding memory 150 to the variable length of the length of the code words in response to the LEG (a) [1 _10] output from the first latch (412) storing the code word bits of M (a) in _{[a 1 xxxxx] [1 10} ] bit sliding is to select the first window bit string (B ₁₎ [xxxxxa _1], wherein the selected [xxxxxa _1] bit sequence the 1 window bit string B ₁ to the first latch 412.

The second adder 421 of the accumulator 420 receives the length LEG (a) of the variable length codeword from the code length detector 220 and the length of the second latch 422 from the second latch 422, And outputs the added signal to the second latch 422. The second latch 422 outputs the added signal to the second latch 422. [ Since the second latch value L ₁ is [0 ₁₀ ] and the variable length codeword length LEG (a) = 1 ₁₀ , the adder 421 adds [1 ₁₀ ], And outputs an addition signal having the value of [ ₁₀ ] to the second latch 422. [

Subtractor 423 of the accumulator 420 by subtracting the [0 _10] showing an added signal from the second latch 422 from the reference signal having a predetermined value _[610] the value of _[610] generating a subtracted signal (S ₀₎ and having, a subtracted signal (S ₀₎ in the _[610] the value is generated and provided to the third latch (424). The third latch 424, the third latch signal [6 _10] store the subtracted signal (S ₀₎ of the value, and subtracting the signal of the _[510] value (S ₀₎ from the subtracter 423 ( L ₂ ) to the second barrel shifter 431. Then, the second barrel shifter 431 slides the first latch bit string [xxxxxx] and the stored code word M (a) by 6 bits in response to the third latch signal L ₂ , And outputs the column [a ₁ xxxxx] to the fourth latch 432.

When the stored code word M (b) _i for the symbol [b] is generated from the encoding memory 150 at time t = 3, the storage code for the symbol 'b' generated from the encoding memory 150 As described above, the word M (b) is input to the first barrel shifter 411 of the input unit 410 and the second barrel shifter 431 of the output unit 430 of the encoding / coding packing unit 310 The length LEG (b) of the variable length codeword for the symbol 'b' from the variable length detector 220 is added to the adder 421 of the first barrel shifter 411 and the accumulator 420, The value '3 ₁₀ ' is input.

When the first code word M (b) _i for the symbol 'b' and the length LEG (b) of the variable length codeword are input, the first barrel shifter 411 outputs the variable length codeword length LEG (b) b) a first latch bit string 'xxxxxa ₁ ' output from the first latch 412 in response to '3 ₁₀ ' and a bit string 'xxxxxa ₁ ' of the stored code word M (b) _i input from the encoding memory 150 ' xxa ₁ b ₁ b ₂ b ₃ 'is selected as the first window bit string (B ₁ ) by sliding' 3 ₁₀ 'bits in b ₁ b ₂ b ₃ xxx', and the selected 'xxa ₁ b ₁ b ₂ b ₃ 'bit string to the first latch 412 as the first window bit string (B ₁ ).

The adder 421 of the accumulator 420 receives the length LEG (b) of the variable length codeword from the code length detector 400 and the second latch value L ₁ (b) from the second latch 422, ) ' ₁₀ ' to generate an addition signal A _D having an added value '4 ₁₀ ', and outputs the generated addition signal to the second latch 422.

Further, the value of _'510' the subtractor 423 is to the reference value _'610' as the reference signal subtraction to _'110' as the sum signal from the second latch 422 of the accumulator 420, to generate a subtracted signal (S ₀₎ having, a subtracted signal (S ₀₎ of the _"510" value is generated and provided to the third latch (424). The third latch 424 stores the subtracted signal (S ₀₎ of the _"510" value from the subtractor 423, and the _'510' subtracted signal (S _0), the third latch signal value L ₂ to the second barrel shifter 431. Then, the second barrel shifter 431 latches the first latch bit string 'xxxxxa ₁ ' and the stored code word M (b) = 'b ₁ b ₂ b ₃ xxx' in response to the third latch signal L ₂ ' as the _"510" bit by sliding, a ₁ b ₁ b ₂ b ₃ xx 'of the second window, the bit string (w ₂₎ and outputs to the fourth latch 432.

C] generated from the encoding memory 150 when the stored codeword M (c) _i for the symbol [c] is generated from the encoding memory 150 at time t = 4, The word M (c) is input to the first barrel shifter 411 of the input unit 410 and the second barrel shifter 431 of the output unit 430, as in the symbols [a] and [b] At the same time, the adder 421 of the first barrel shifter 411 and the accumulator 420 receives the length LEG (k) of the variable length codeword for the symbol [c] from the variable length detector 200, b) = 3).

When the first code word M (c) for the symbol [c] and the length LEG (b) of the variable length codeword are input, the first barrel shifter 411 determines the length LEG (c ) in response to the _[310] of the first latch 412, first latch bit string [xxa ₁ b ₁ b ₂ b _3] and stores the code word M (c inputted from the encoding memory 150) output from the bit string _{[c 1 c 2 c 3 xxx} ] in 3 bits sliding by a first window bit string (b ₁₎ as a _{[b 1 b 2 b 3 c} 1 c 2 c 3] selected, and the selected bit string to the _i [b ₁ b ₂ b ₃ c ₁ c ₂ c ₃ ] to the first latch 412 as the first window bit string (B ₁ ).

The second adder 421 of the accumulator 420 receives the length LEG (c) of the variable length codeword from the code length detector 400 and the second latch value by adding the L ₁₎ [3 _10] there is thereby generate a sum signal having a sum value _[710], the adder 421 generates a carry signal (c) whenever the the addition value is more than _[610] And generates the addition signal by subtracting [6 ₁₀ ] from the addition value [7 ₁₀ ]. Therefore, the adder 421 outputs the value of [ _{10 2} ] to the second latch 422 as the addition signal, while outputting the carry signal C to the outside.

Further, the subtractor 423 of the accumulator 420 is the value of _[510] by subtracting [1 _10] as the sum signal from the second latch 422 from the reference value _[610] as the reference signal to generate a subtracted signal (S ₀₎ having, a subtracted signal (S ₀₎ in the _[510] the value is generated and provided to the third latch (424). The third latch 424 is _[510] store the subtracted signal (S ₀₎ in value, and the _[510] The third latch signal to the subtraction signal (S ₀₎ of the value L from the subtractor 423 ₂ to the second barrel shifter 431. Then, in response to the third latch signal L ₂ , the second barrel shifter 431 latches the first latch bit string [xxa ₁ b ₁ b ₂ b ₃ ] and the stored code word M (b) = [c ₁ c ₂ c ₃ xxx] by two bits to output the bit string [a ₁ b ₁ b ₂ b ₃ c ₁ c ₂ ] to the fourth latch 432 as the second window bit string w ₂ .

Therefore, the generation of the carry signal C occurs when the fourth latch 432 of the output unit 430 is filled with only the bits of the variable length codewords VLW (X) (W ₂ ) of the fourth latch 432 in response to the read code word, it is possible to detect only the variable length codeword in the stored codeword.

In this manner, the encoding and encoding unit 310 repeats the above-described operation every time the lengths of the storage codeword and the variable length codeword for the symbols are input, and detects only the variable length codeword in the storage codeword And outputs it to the outside.

Thus, according to the above configuration, the length of the variable length codeword for the input symbol is detected whenever a symbol to be encoded from the outside is inputted, and the storage code It is possible to detect and output only the variable length codeword in the word.

Next, the decoding operation of the codec apparatus will be described.

First, when [101100001110 ....] of a decoding bit string corresponding to the symbols [cbaa e ....] is input as in the buffer 110, the switch 160 transmits the decoded data to the decryption packing unit 130 (ECS _i ) of the maximum length K of the variable length codeword in the decoded code bit string from the decoding packing unit 130 to the second input terminal S2 of the boundary detection unit 210).

Then, as in the encoding operation, the boundary detector 210 detects the boundary of the variable length codeword included in the bit stream CW to be decoded inputted through the switch 160, and outputs the detected variable length codeword And generates a boundary value indicating the boundary of the word. The boundary detection unit 210 detects the first position values LD (c) ₁ to LD (c) ₆ output from the first to sixth subtractors 531 to 536 of the arithmetic unit 530 And applies it to the multiplexer 610 for use as the address of the decoded code word.

The length detector 220 detects the length LEG (X) of the variable length codeword included in the bit string CW from the boundary value MSB _m from the boundary detector 210 as described above, Length codeword LEG (X) to the multiplexer 610 and the plurality of registers 620 of the decryption packing unit 130 and the address generator 600, respectively.

That is, when the bit string [101100] is input from the decoding packing unit 130 to the boundary detection unit 210, the boundary detection unit 210 detects the boundary of the variable length codeword from the bit string [101100] The position values LD _{k = 1, 2, ..., 6} from the first to sixth subtractors 531 to 536 are calculated in parallel as described above.

That is, the position values LD _{k = 1, 2, ... 6} are as shown in Table 6 below.

LD _m LD _m sign value Decimal number Binary number (MSB → LSB) One One 0 0 0 0 0 1 amount 2 0 0 0 0 0 0 0 amount 3 One 0 0 0 0 0 1 amount 4 - 3 1 1 1 1 0 1 Well 5 - 8 1 1 1 0 0 0 Well 6 -18 1 0 1 1 1 0 Well

At this time, the boundary detection unit 210 outputs the calculated position values (LD ₁ , LD _2, LD ₃ , LD ₄ , LD _{5, and} LD ₆ ) to the multiplexer 610 for use as an address of a decoded codeword. The boundary detector 210 also calculates the position values LD ₁ , LD _2, LD ₃ , LD ₄ , LD _5, LD ₆ to determine the sound amount of the calculated position values LD ₁ , LD _2, LD _3, (MSB _m = 000111) of the LDs ₃ , ₄ , _{5, and 6} to the code length detector 220 as the boundary value MSB _m . Then, the length detector 220 exclusively ORs the boundary value [MSB _m = 000111] to generate a length LEG (X) = [00100] of the variable length codeword.

The multiplexer 610 receives the position values LD (X) from the boundary detector 210 in response to the length LEG (X) = [00100] of the variable length codeword detected by the variable length detector 200, ) and outputs a position value of LD (X) ₂ = a [1] to the sixth latch 640 of the _m.

At the same time, only the register storing the number [1] of terminal nodes up to level 2 among the plurality of registers 620 is enabled, and the number of terminals [1] .

Then, the adder 650 adds the number of terminal nodes [1] from the plurality of registers 620 to the position value LD (X) ₂ = 1 from the multiplex 610 and outputs the decoded code word address [ 2] and outputs the generated address [2] to the decoding memory 660 to generate a decoded code word Si corresponding to the variable length codeword [101] from the decoding memory 660 .

In addition, the decoding and packing unit 130 may store the variable length codeword in the range of the maximum length of the variable length codeword from the next bit excluding the decoded input bit string [101] in response to the length LEG (X) = [001000] And then the bit string of the next bit string [100001110. . . . .] Can be decoded.

As described above, according to the present invention, the variable length coded codewords are sequentially stored in the look-up table memory in the node order according to the level on the canonical tree structure, and the node order of the codewords Huffman code tree is used as the address of the decoded codeword, which is searched and decoded by the operation. Therefore, even if the Huffman code tree changes according to the central system, variable length decoding is performed at high speed by simply storing the variable in the memory and latch without changing the hardware. Therefore, regardless of the length of the encoded code word, one encoded codeword is processed in one clock based on the parallel operation, so that the decoding process is performed at a higher speed than the conventional variable length decoding apparatus or method that performs decoding processing on a bit basis.

As described above, according to the present invention, the length of the variable length codeword is detected based on the Huffman code structure and the variable length codeword, and the input data is coded into the variable length codeword using the length of the detected variable length codeword And a variable length coding method and apparatus therefor.

While the present invention has been particularly shown and described with reference to exemplary embodiments thereof, it is to be understood that the invention is not limited to the disclosed exemplary embodiments, but variations and modifications may be made without departing from the scope of common knowledge of those skilled in the art.

Claims (11)

a) a buffer 110 for storing an encoded bit stream input from a source; b) storing a decoded bit string from the outside, outputting the stored decoded codeword as a maximum length of the variable length codeword, and decoding the decoded codeword in the decoded bit string according to the length of the variable length codeword included in the decoded bit string A decoding packing unit 130 for outputting bits from the next bit; c) storing variable length codewords defined for each possible symbol for each possible symbol on the basis of the Huffman code structure, and for storing the symbol (X) in the buffer (110) A coding memory 150 for outputting a stored code word M (X) including a variable length code word VLW (X) corresponding to the variable length code word X; d) a decoding memory for storing the decoded codeword as the address of the location of the terminal node in the Huffman code tree; e) selection means 160 for selectively outputting the stored codeword M (X) from the memory 150 and the encoding bit stream ECS _i from the decoding packing unit 130 in response to a control signal from the outside ); f) selecting code words BW _m generated by selecting m bits in the bit string (CW) input from the selecting means and a level in the Huffman code tree of the selected code words BW _m and the number of terminal nodes at each level A variable length detector (200) for detecting the length of the variable length codeword included in the bit string (CW); g) detecting a position of a variable length codeword included in the bit string (CW) in the Huffman tree in response to the length of the variable length codeword detected by the variable length detector (200), and detecting the detected position An address generator 600 for providing the decoded data to the decoding memory; And h) detecting a variable length codeword (W ₂ ) in the bit string (CW) in response to a length (LEG) of a variable length codeword detected by the length detector (220) (W ₂₎ is composed of the encoded encoding packing unit 310 for outputting, Here, m is 1, 2, 3 .... K, and K is a maximum length of a variable length codeword. 2. The apparatus as claimed in claim 1, wherein the variable length detector (200) comprises a variable length detector (200) for detecting the selection code word (BW _m ), the selection code word (BW _m) generating a position value LD (X) _m in each of the levels of the word BW _m and, on the basis of the position value LD (X) _m the boundary between the variable length codewords, and the stuffing bits included in the bit stream (CW) A boundary detection unit (210) for generating a boundary value (MSB _m ) to be displayed; And And a length detector 220 for detecting a length LEG (X) of a variable length codeword included in the bit string CW based on a boundary value MSB _m from the boundary detector 210 , Here, the position value LD (X) _m is: LD (X) _m = BW (X) _m -NW (X) _m Lt; B _i is the i-th bit value of the selected codeword generated by selecting m bits, and L _j is the number of total terminal nodes at the jth level of the Huffman code tree. 3. The apparatus of claim 2, wherein the boundary detection unit (210) comprises: a code selection unit (510) for selecting m bits from the bit string (CW) input from the selection unit to generate the selection code words BW _m ; Detects the level in the Huffman code tree for each of the selected code words BW _m from the code selection unit 510 and outputs the level code word NW (n) corresponding to the detected level and the number of terminal nodes in the detected level (X) _m ; The choice selection unit wherein the selection from 510, codewords BW _m, and the selected code words of BW _m position value by calculating the level of the code word NW (X) _m from the level detector 520 corresponding to the respective An operation unit 530 for generating LD (X) _m ; And And a boundary value generator 540 for detecting the most significant bits of the position value LD (X) _m to generate the boundary value MSB (X) _m . The method of claim 3, wherein the operating section 530, a plurality of subtractors for the operation in parallel of the level code word NW (X) corresponding to each of the said selected code word in BW _m, and the selected code words BW _{m m} ( 531 to 537). ≪ / RTI > 3. The method of claim 2, wherein the length detector (220) mutually exclusive-ORs the bits of the boundary value MSB (X) _m generated from the boundary value generator (540) Speed variable-length codec device. 3. The apparatus of claim 2, wherein the address generator generates the address LD (X) from the boundary detector (210) in response to a length LEG (X) of the variable length codeword detected by the variable length detector select X) a position value of the _m LD (X) _m, and by adding the number of terminal nodes to the level m the previous corresponding to the selected position value LD (X) _m contained in said bit sequence (CW) Length codeword in the Huffman tree of the variable-length codeword. 7. The apparatus as claimed in claim 6, wherein the address generator (600) comprises: a position detector (210) for detecting a position LD (X) from the boundary detector (210) in response to a length LEG (X) of a variable length codeword detected by the variable length detector X) multiplexed (610) for selecting _m of the LD position value (X) of the _m; Stores the number of terminal nodes to each level of the Huffman code tree, and responds to the length LEG (X) of the variable length codeword detected by the variable length detector 200, A plurality of registers (620) And And an adder 650 for adding the number of terminal nodes from one of the plurality of registers 620 to the position value LD (X) _m from the multiplex 610 to generate the address. Speed processing variable length codec device. 2. The apparatus of claim 1, wherein the decode coding and encoding unit (310) comprises: an input unit (110) for detecting bits in a predetermined bit string in response to a length of the variable length code word to generate a first window bit string; An output unit 430 for detecting bits of the stored code word and the bits of the variable length codeword in the first window bit string in response to a control signal and outputting the detected bits; And And an accumulator (420) for accumulating the number of bits output from the output for generating the control signal. The apparatus of claim 8, wherein the input unit comprises: a first latch (412) for outputting the first window bit string to the output unit and the first barrel shifter; And And the first barrel shifter (411) for generating the first window bit string by slicing in the bit string in response to the length of the variable length codeword. 9. The apparatus of claim 8, wherein the output (430) is responsive to the control signal to detect bits of the variable length codeword to generate a first window bit string and a second Barrel shifter 431; And And a second latch (432) for storing bits of a variable length codeword from the second barrel shifter. 9. The apparatus of claim 8, wherein the accumulator comprises: a third latch (422) for storing an addition value input from the adder; An adder (421) for adding the addition value from the third latch and the length value of the variable length codeword to the module-K and generating a carry signal when the added value is K or more; And And a subtractor (423) for subtracting the stored value from the third latch from the K to generate the control signal.