JP3533339B2 - Decoding device, decoding method, and program recording medium - Google Patents

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a decoding device and a decoding method for decoding a variable length code such as a Huffman code, and a program recording medium having a decoding program recorded therein.

[0002]

2. Description of the Related Art There are roughly three methods for decoding variable length codes such as Huffman codes. First
The method of is, every 1 bit from the first bit of the variable length code,
This is a method of determining a target variable length code by a binary tree. The second method is to make a table of variable-length codes together with the number of bits and compare these tables sequentially. The third method is a method of converting the variable length code itself into a table having a size corresponding to the maximum bit length and searching this table.

In the first method, since the comparison is made bit by bit, it takes a long processing time to decode one variable length code. In the worst case, the second method
It cannot be decrypted without comparing all the tables, which requires a long processing time. In addition, the third method has an advantage that processing can be performed by one table search and the processing time can be extremely short. However, when the maximum bit length of the variable length code is large, a large capacity memory is required.

In order to solve the above-mentioned drawbacks, therefore, the first method and the third method are combined to search the variable-length code at high speed when decoding the variable-length coded data. In order to carry out with a table having a small capacity, a "decoding method of Huffman code" as disclosed in Japanese Patent Application Laid-Open No. 7-107303 has been proposed.

In the "decoding method of Huffman code", the Huffman code is composed of a first group having a code length of 8 bits, a second group having a code length of 9 bits to 12 bits, and a third group having a bit length of 13 bits or more. Divide into Then, for each group, the Huffman code is used as an address, and the data indicating the code length and the effective coefficient is written in association with the address.
Create the tables up to the table in advance. And
At the time of decoding, the target Huffman code is decoded by referring to the first to third tables to determine the code length and the effective coefficient of the Huffman-coded data.

Similarly, in order to speed up the decoding of a variable length code and to cope with an increase in the capacity of the search table, a "decoding device" disclosed in Japanese Patent Laid-Open No. 9-246989. And its method "have been proposed.

In this "decoding device and method",
An analysis length which is less than or equal to the maximum bit length of the variable length code is selected from the analysis length register, and the decoding RAM is accessed based on the address generated by the bit string for the above analysis length extracted by the bit extraction unit. This process is repeated until all the bits of the variable length code are completed, and finally the decoded value is obtained. Further, when accessing the decoding RAM at the final stage, the fetch bit length controller limits the analysis length to the minimum based on the decoding end signal.

Further, when decoding a variable-length code, in order to reduce the overall capacity of a plurality of conversion tables to reduce the memory capacity, the "code" disclosed in Japanese Patent Laid-Open No. 9-298470. A "decoding device" has been proposed.

In this "code decoding device", a common conversion table in which common parts in which the same conversion result is set for the same code among a plurality of conversion tables is put together and the common part is excluded. An individual conversion table for each decryption item is provided. Then, when the code decoding unit cannot decode the code by referring to the common conversion table, the code decoding unit performs decoding by referring to the individual conversion table for each decoding item. In this way, by eliminating the waste of storing the same data in multiple conversion tables in duplicate,
The overall capacity of multiple conversion tables is reduced.

[0010]

However, the "decoding method of Huffman code" disclosed in Japanese Patent Laid-Open No. 7-107303 has the following problems. That is, when referring to the first to third three tables, it is determined whether the Huffman code is 8 bits or less and is determined by referring to the first table, and the Huffman code is 9 bits to 12 bits. Therefore, it is necessary to judge whether or not it is determined by referring to the second table. Therefore, when performing the decoding process, the processing time must be estimated in consideration of the worst case even though the processing amount is reduced on average, and the processing time can be accurately estimated. difficult.

Further, the "decoding device and method thereof" disclosed in Japanese Patent Laid-Open No. 9-246989 has the following problems. That is, as in the case of the “decoding method of Huffman code” disclosed in Japanese Patent Laid-Open No. 7-107303, the decoded bit in the read variable code is provided with the end detecting means (comparator). It is necessary to compare the length and the code length of the Huffman code to detect the end of decoding and generate the decode end signal.

The "code decoding device" disclosed in Japanese Patent Laid-Open No. 9-298470 has the following problems. That is, since it is necessary to determine whether or not the input variable length code is on the common table, the processing amount increases. Furthermore, it is rare that some processing is not added to the conversion table, and there are few parts that are put together in the common conversion table. Therefore, reduction in memory capacity cannot be expected so much.

As described above, in any case, it is necessary to make a judgment in the decoding process, and the decoding process algorithm has a branch instruction associated with the judgment. By the way, LSI
With the progress of processing technology of (large-scale integrated circuit) and CPU (central processing unit), many instructions can be executed in one clock, and as the clock speed of the CPU is increased, Pipelining is progressing.
Therefore, the penalty of the pipeline reloading due to the branch instruction accompanying the above determination becomes large, and the algorithm having no branch condition can be executed faster.

Therefore, if an attempt is made to apply a decoding processing algorithm having no branching condition to each of the conventional decoding devices or decoding methods described above, the memory capacity of the above-mentioned table, decode RAM and conversion table becomes large. Will end up. Therefore, there is a problem that the original purpose of reducing the search table capacity cannot be achieved.

Therefore, an object of the present invention is to provide a decoding device and a decoding method capable of decoding a variable length code at high speed by applying a decoding processing algorithm without a branch condition while reducing the search table capacity. , Providing a program recording medium.

[0016]

In order to achieve the above object, the decoding device of the invention according to claim 1 uses a variable length code .
A bit string having a maximum bit length that is a fixed bit length in the input is input, and a dividing unit that divides the input bit string into two or more bit strings for each predetermined number of bits and a table corresponding to each bit string that is divided by the dividing unit are stored. Table storing means, and referring to the table with each bit string divided by the dividing means as an index,
A lookup means for obtaining a parameter for calculating the code length or the decoded value, and a computing means for computing the code length or the decoded value based on the parameter obtained by the lookup means. .

According to the above configuration, when the bit string for each predetermined number of bits obtained by dividing the input bit string by the dividing unit is input to the lookup unit, the lookup unit creates a table using the input bit sequence as an index. A parameter for obtaining the code length or the decoded value is obtained by referring to the code length. When this parameter is input to the calculating means, the calculating means calculates the code length or the decoded value of the variable length code based on the input parameter.

As described above, the processing results from the preceding processing means are input without the processing means of the dividing means, the lookup means, and the computing means determining whether or not the processing of the other processing means has ended. Then, the processing is executed by itself, the processing result is output to the processing means in the subsequent stage, and the processing is sequentially executed. Therefore, the algorithm having no branch condition is applied, and the decoding process is executed at high speed.

The invention according to claim 2 is the decoding apparatus of the invention according to claim 1, wherein the table contains a code length calculation parameter for calculating a code length or a decoded value calculation parameter for calculating a decoded value. The registered arithmetic means is characterized in that the arithmetic means calculates the code length or the decoded value based on the code length calculation parameter or the decoded value calculation parameter output from the lookup means.

According to the above construction, the code length or the decoded value of the variable length code can be easily obtained by the calculation by the calculating means based on the code length calculation parameter or the decoded value calculation parameter registered in the table.

Further, the decoding device of the invention according to claim 3 receives the bit string of the maximum bit length which is a fixed bit length in the variable length code as an input, and divides the input bit string into two or more bit strings for every predetermined number of bits. The dividing means, the code number calculation parameter is registered, the first table storing means stores the first table corresponding to each bit string divided by the dividing means, and each of the divided by the dividing means. Referring to the first table a bit string as an index, calculating a first look-up means for obtaining a code number calculation parameter, the code number based on the code number calculation parameters obtained in the first look-up means second table and calculating means, and the code number and the code length or the decoded value of said variable length code is registered in association to the A second table storage means which is paid to the code number obtained by the calculating means by referring to the second table as an index, with a second look-up means for obtaining the code length or the decoded value Is characterized by.

According to the above construction, the bit string for each predetermined number of bits, which is formed by dividing the input bit string by the dividing means,
Is input to the first look-up means, by the first Le <br/> Kkuappu means, code number calculation parameter bit sequence input is being referred to the first table as an index is obtained. Then, the calculation means calculates the code number based on the code number calculation parameter. Then, the second lookup means refers to the second table using the code number as an index to obtain the code length or the decoded value of the variable length code.

As described above, the processing means of the dividing means, the first look-up means, the computing means and the second look-up means do not need to determine whether the processing of the other processing means is completed. When the processing result from the processing means in the previous stage is input, the processing itself is executed, the processing result is output to the processing means in the subsequent stage, and the sequential processing is executed. Therefore, the algorithm having no branch condition is applied, and the decoding process is executed at high speed.

The invention according to claim 4 is, in the decoding device of the invention according to claim 1 or claim 3, aggregates a plurality of tables corresponding to each bit string divided by the dividing means into one table. It is characterized by having done.

According to the above configuration, the table storing means or the one stored in the first table storing means by the lookup means in the invention according to claim 1 or the first lookup means in the invention according to claim 3 Only one table is referenced to obtain each of the above parameters. In this way, the parameters for calculating the code length, the decoded value, and the code number are obtained by using the table having a small capacity.

Further, the fixed bi in the invention according to claim 5
The decoding method of the bit length is a step of dividing a bit string having a maximum bit length of a variable-length code into two or more bit strings each having a predetermined number of bits, and using each of the divided bit strings as an index. A step of obtaining the code length calculation parameter or the decoded value calculation parameter by referring to the table in which the code length calculation parameter or the decoded value calculation parameter is registered; and the code length or the decoded value based on each of the obtained parameters. Is characterized by including a step of calculating

According to the above configuration, as in the case of the first aspect of the invention, the step of dividing the input bit string into bit strings each having a predetermined number of bits, the divided bit string as an index and referring to the table to set the parameters. The processing result from the preceding step is input without determining the end of other steps in each step of obtaining and calculating the code length or the decoded value based on each of the obtained parameters. And is executed sequentially.
Therefore, the algorithm having no branch condition is applied, and the decoding process is executed at high speed.

Further, in the decoding method of the invention according to claim 6, a bit string having a maximum bit length which is a fixed bit length in a variable length code is input, and the input bit string is divided into two or more bit strings for every predetermined number of bits. A step of obtaining the code number calculation parameter by referring to a first table in which the code number calculation parameter is registered using the divided bit strings as indexes, and based on the obtained code number calculation parameter The step of calculating the code number and the second table in which the code number and the code length or the decoded value are registered in association with each other by using the calculated code number as an index It is characterized by having a step of obtaining a value.

According to the above structure, as in the case of the invention according to claim 3, the step of dividing the input bit string into bit strings each having a predetermined number of bits, and referring to the first table with the divided bit string as an index . A step of obtaining a parameter, a step of calculating a code number based on the obtained parameter, and a step of obtaining the code length or the decoded value by referring to a second table using the calculated code number as an index . Each step is sequentially executed when the processing result from the preceding step is input without determining the end of other steps.
Therefore, the algorithm having no branch condition is applied, and the decoding process is executed at high speed.

According to a seventh aspect of the present invention, there is provided a program recording medium in which a computer is provided with a fixed code in a variable length code .
A bit string having the maximum bit length, which is the bit length, as an input, and dividing means for dividing the input bit string into two or more bit strings for each predetermined number of bits, and a code length calculation parameter or decoded value using each of the divided bit strings as an index. Look-up means for obtaining the above code length calculation parameter or decoded value calculation parameter by referring to a table in which calculation parameters are registered, and function as calculation means for calculating the code length or decoded value based on each of the obtained parameters It is characterized in that the decryption processing program is recorded.

According to the above configuration, similar to the case of the invention according to claim 5, a process of dividing the input bit string into bit strings of a predetermined number of bits, and referring to the table with the divided bit string as an index, a parameter is set. Processing to get,
Then, the respective processes of the process of calculating the code length or the decoded value based on the obtained respective parameters are sequentially executed without determining whether other processes are completed. Therefore, the algorithm having no branch condition is applied, and the decoding process is executed at high speed.

A program recording medium according to an eighth aspect of the present invention allows a computer to execute a fixed view in a variable length code .
Inputting a bit string having the maximum bit length, which is the bit length, and dividing means for dividing the input bit string into two or more bit strings for each predetermined number of bits, and a code number calculation parameter is registered using each of the divided bit strings as an index. First
Referring to the tables, indexes and first look-up means for obtaining the code number calculation parameters, and calculation means for calculating the code number based on the obtained code number calculation parameter, the calculated code number As a reference, a decoding processing program which functions as a second lookup means for obtaining the code length or the decoded value by referring to a second table in which the code number and the code length or the decoded value are associated with each other and registered. Is recorded.

According to the above configuration, similar to the case of the invention according to claim 6, a process of dividing the input bit string into bit strings of a predetermined number of bits, and referring to the first table with the divided bit string as an index . To obtain a parameter, to calculate a code number based on the obtained parameter, and to obtain a code length or a decoded value by referring to a second table using the code number as an index . , Are sequentially executed without determining whether other processing is completed. Therefore, the algorithm having no branch condition is applied, and the decoding process is executed at high speed.

[0034]

BEST MODE FOR CARRYING OUT THE INVENTION The present invention will be described in detail below with reference to the embodiments shown in the drawings. <First Embodiment> FIG. 1 is a block diagram of a decoding apparatus according to the present embodiment. The decoding device according to the present embodiment is a variable-length code decoding device, and a judgment means for judging whether or not the decoding for the input variable-length code is completed is provided as compared with the conventional decoding device. There is not, but the arithmetic unit 8 is added instead. The details will be described below.

A bit string having the maximum code length in the variable length code is input to the divider 1 from the system in which the present decoding device is installed. Here, a variable length code as shown in Table 1 is considered as an example.

[Table 1] The “code number” in Table 1 above is a number assigned to each variable length code so as to correspond one-to-one, and may be any number. In the case of the variable-length codes shown in Table 1, the maximum code length is 6 bits, so a 6-bit bit string is input to the divider 1.

Then, the divider 1 divides the input 6-bit bit string into three bits of upper 2 bits, middle 2 bits, and lower 2 bits. Then, the upper 2 bits are output to the first lookup unit 3, the middle 2 bits are output to the second lookup unit 5, and the lower 2 bits are output to the third lookup unit 7. The number of bits output to each lookup unit may be an arbitrary number of bits of 1 bit or more. The number of lookup units is the maximum code length of the variable length code input and the number of bits output to each of the lookup units. Therefore, it may be set appropriately.

The first lookup unit 3 looks up the first table stored in the first table storage unit 2 by using the input bit string of the upper 2 bits as an address,
The address (table address) to the second table registered in the table address column of the table, the code length calculation parameter registered in the code length calculation parameter column, and the decoded value registered in the decoded value calculation parameter column Read the calculated parameters. Table 2 shows an example of the first table.

[Table 2] Then, the table address is output to the second lookup unit 5, and the code length calculation parameter and the decoded value calculation parameter are output to the calculator 8.

The second lookup unit 5 uses the table address for the second table input from the first lookup unit 3 and the middle 2-bit bit string input from the divider 1 as an index to generate a second index. The address of the table is obtained, and the second table stored in the second table storage unit 4 is drawn. Then, the table address to the third table registered in the table address column in the second table, the code length calculation parameter registered in the code length calculation parameter column, and the decoding registered in the decoded value calculation parameter column Read the value calculation parameters. Table 3 shows an example of the second table.

[Table 3] Then, the table address is output to the third lookup unit 7, and the code length calculation parameter and the decoded value calculation parameter are output to the calculator 8.

The third look-up unit 7 uses the table address for the third table input from the second look-up unit 5 and the bit string of the lower 2 bits input from the divider 1 as an index for the third table. Is obtained, and the third table stored in the third table storage unit 6 is pulled. Then, the code length calculation parameter registered in the code length calculation parameter column in the third table and the decoded value calculation parameter registered in the decoded value calculation parameter column are read. Table 4 shows an example of the third table.

[Table 4] Then, the code length calculation parameter and the decoded value calculation parameter are output to the calculator 8.

The arithmetic unit 8 calculates the code length of the variable length code based on the code length calculation parameter and the decoded value calculation parameter input from the first, second and third look-up units 3, 5, and 7. And the decoded value are calculated, and the calculation result is output.

Here, in the present embodiment, the first lookup unit 3, the second lookup unit 5, the third lookup unit 7 and the first table corresponding to each lookup unit
For convenience of explanation, the three tables of the third table have a configuration of upper, middle, and lower three stages, but as described above, if the configuration has two or more stages, the number of stages is not particularly limited. Absent.

FIG. 2 shows a schematic procedure of the decoding process executed by the divider 1, the first lookup unit 3, the second lookup unit 5, the third lookup unit 7 and the calculator 8 in FIG. It is a flowchart. Hereinafter, the decoding processing procedure according to the present embodiment will be described with reference to FIG.

First, in step S1, the bit string of the maximum code length (6 bits in the case of the variable length code shown in Table 1) input by the divider 1 is the upper 2 bits and the middle 2 bits.
It is divided into 3 bits, the lower 2 bits. Then, the upper 2 bits are sent to the first lookup unit 3, and the middle 2
The bits are sent to the second lookup unit 5, and the lower 2 bits are sent to the third lookup unit 7. The dotted line indicates the flow of the divided bit string data.

Next, in step S2, the first look-up unit 3 draws the first table using the input upper 2 bit string as an address, and the table address to the second table, the code length calculation parameter, and the decoded value. The calculated parameters and are read. Then, the table address is sent to the second lookup unit 5, and the code length calculation parameter and the decoded value calculation parameter are sent to the calculator 8.

Next, in step S3, the second look-up section 5 obtains the address of the second table by using the input middle 2-bit string and the table address from the first look-up section 3 as an index. The second table is looked up and the table address, code length calculation parameter and decoded value calculation parameter to the third table are read. Then, the table address is sent to the third lookup unit 7, and the code length calculation parameter and the decoded value calculation parameter are sent to the calculator 8.

Next, in step S4, the third look-up unit 7 obtains an address to the third table by using the input lower 2 bit string and the table address from the second look-up unit 5 as an index, The third table is looked up and the code length calculation parameter and the decoded value calculation parameter are read. Then, the code length calculation parameter and the decoded value calculation parameter are sent to the calculator 8. The broken line shows the flow of the code length calculation parameter and the decoded value calculation parameter.

Next, in step S5, based on the code length calculation parameter and the decoded value calculation parameter output from each of the lookup units 3, 5, and 7 by the arithmetic unit 8,
The code length of the variable-length code and the decoded value are calculated, and the calculation result is output. After that, the decoding process ends.

As described above, in the decoding process according to the present embodiment, the division unit 1, the first lookup unit 3, the second unit
Each processing unit of the look-up unit 5, the third look-up unit 7 and the arithmetic unit 8 is adapted to sequentially execute each process. Therefore, it is not necessary to make a determination in the decoding process. Therefore, it is not necessary to describe a branch instruction associated with the determination in the decoding processing algorithm, and the decoding processing can be executed faster than the above-described conventional decoding device and decoding method.

The variable length code bit string "00010" will be described below.
The operation of the decoding apparatus having the above configuration will be described more specifically by taking the case where "1" is input to the divider 1. The divider 1 converts the input bit string “000101” into 3 of the upper 2 bits “00”, the middle 2 bits “01” and the lower 2 bits “01”.
Divide into two. Then, the top 2 is added to the first lookup unit 3.
The bit “00” is output, the middle 2 bits “01” are output to the second lookup unit 5, and the lower 2 bits “01” are output to the third lookup unit 7.

Then, the first lookup unit 3
Draws the first table with the input upper 2 bits “00” as an address, and the code length calculation parameter “2”, the decoded value calculation parameter “0”, and the table address “2-
a ”is obtained. Then, the table address “2-a” is sent to the second lookup unit 5. On the other hand, the code length calculation parameter “2” and the decoded value calculation parameter “0” are sent to the calculator 8.

Next, the second lookup unit 5 receives the middle 2 bits "01" input from the divider 1 and the table address "2-a" input from the first lookup unit 3. The address of the second table is obtained as an index, and the second table is drawn with that address. Then, the code length calculation parameter “0”, the decoded value calculation parameter “0”, and the table address “3-a” to the third table are obtained. Then, the table address “3-a” is sent to the third lookup unit 7, while the code length calculation parameter “0” and the decoded value calculation parameter “0” are sent to the calculator 8.

Next, the third lookup unit 7 indexes the lower 2 bits "01" input from the divider 1 and the table address "3-a" input from the second lookup unit 5. Then, the address of the third table is obtained, and the third table is drawn with the address. Then, the code length calculation parameter “0” and the decoded value calculation parameter “0” are obtained. Then, the code length calculation parameter “0” and the decoded value calculation parameter “0” are sent to the calculator 8.

Then, the arithmetic unit 8 operates as the first,
The code length calculation parameters “2”, “0”, “0” output from the second and third lookups 3, 5, 7 are added to obtain the code length “2” of the input variable length code. Similarly, the decoded value calculation parameters “0”, “0”, and “0” output from the first, second, and third lookups 3, 5, and 7 are added to obtain the decoded value “0”. Then, the code length "2" and the decoded value "0" thus obtained are output.

As described above, in the present embodiment, a variable length code having a maximum code length of 6 bits is divided into 2 bits, and the upper 2 bits are used as an index for "code length calculation parameter" and "decoded value calculation parameter". Also, a first table for searching "table address to next table" is created and stored in the first table storage unit 2. Similarly, medium 2
A second table is created to search for “code length calculation parameter”, “decoded value calculation parameter”, and “table address to next table” using bits and “table address” of the first table as an index. Stored in the table storage unit 4. In addition, a third table for searching the “code length calculation parameter” and the “decoded value calculation parameter” using the lower 2 bits and the “table address” of the second table as an index is created and stored in the third table storage unit 6. Store.

However, as the element values of both parameters of each table, the code length and the decoded value of the code are given to the address corresponding to the variable length code whose decoded value is determined by subtracting the table, and the other addresses. Is given "0". That is, specifically, in the variable-length codes exemplified in Table 1,
The code corresponding to the code “00” in the case of the first table, the code “010” to “1101” in the case of the second table, and the code “11100” to “111111” in the case of the third table is assigned to the code of the code. It gives the length and the decoded value.

Then, the divider 1 divides the input bit string of the maximum code length (6 bits) by 2 bits, outputs the upper 2 bits to the first lookup unit 3, and outputs the middle 2 bits second It outputs to the lookup unit 5, and outputs the lower 2 bits to the third lookup unit 7. Each lookup section 3,
Reference numerals 5 and 7 sequentially search the corresponding table using the input 2-bit bit string and the "table address" from the lookup unit of the previous stage as an index, and calculate the "code length calculation parameter" and the "decoded value calculation parameter". , And "table address". Then, the “code length calculation parameter” and the “decoded value calculation parameter” are output to the calculator 8. The calculator 8 is
Since each table has the above-described configuration, by adding each of the “code length calculation parameter” and the “decoded value calculation parameter” input from each lookup unit 3, 5, 7, The "code length" and the "decoded value" can be obtained.

As described above, in this embodiment, the input bit string of the variable length code is divided into the upper bit string, the middle bit string, and the lower bit string, and the table for each bit string is sequentially searched from the upper bit string. By doing so, the decoding is performed, so that the decoding can be performed at high speed with a small capacity table. At that time, the divider 1, the first lookup unit 3, the second lookup unit 5, and the third lookup unit
The processing units of the lookup unit 7 and the arithmetic unit 8 do not need to determine the processing end of the other processing units from each other, and a decoding processing algorithm without a branch condition can be applied. Therefore, according to the present embodiment, the decoding process can be executed at a higher speed.

<Second Embodiment> FIG. 3 is a block diagram of a decoding apparatus according to the present embodiment. The present embodiment is intended to further reduce the capacity of each of the first, second and third tables in the first embodiment.

The divider 11 has the same configuration as the divider 1 in the first embodiment and operates in the same manner. The first lookup unit 13 looks up the first table stored in the first table storage unit 12 using the input high-order 2-bit bit string as an address, and acquires the table address registered in the table address column in the first table. Then, the code number parameter registered in the code number parameter column is read.
Table 5 shows an example of the first table.

[Table 5] Then, the table address is output to the second lookup unit 15, and the code number parameter is output to the calculator 18.

The second look-up unit 15 and the third look-up unit 17 are the same as in the case of the first embodiment.
Addresses of the second and third tables are obtained using the table address input from the lookup unit of the previous stage and the bit string of middle and lower 2 bits input from the divider 11 as an index, and the second and third table storage units are obtained. The second and third tables stored in 14 and 16 are drawn. Then, the table address and the code number parameter are read from each table. Second in Table 6
An example of the table and Table 7 show an example of the third table.

[Table 6]

[Table 7] Then, the table address is output to the lookup unit in the next stage, and the code number parameter is output to the calculator 18.

The computing unit 18 computes the code number of the variable length code based on the code number parameters input from the first, second and third lookup units 13, 15, 17 and
The calculation result is output to the fourth lookup unit 19.

Finally, the fourth lookup unit 19 is
Using the input code number as an address, the fourth table stored in the fourth table storage unit 20 is looked up, and the code length registered in the code length column and the decoded value column in the fourth table are registered. Read the decrypted value. Table 8 shows an example of the fourth table.

[Table 8]

FIG. 4 shows the divider 11, the first look-up unit 13, the second look-up unit 15, the third look-up unit 17, the calculator 18 and the fourth look-up unit 1 in FIG.
9 is a flowchart showing a schematic procedure of a decryption process executed by 9. Step S11 in the present embodiment
The steps S15 to S15 are basically the same as the steps S1 to S5 in FIG. 2 of the first embodiment. However, the parameters that the respective lookup units 13, 15, 17 obtain from the respective tables and output to the calculator 18 are code number parameters. Therefore, it is the code number of the variable length code that the calculator 18 calculates in step S15. Then, the code number from the calculator 18 is the fourth lookup unit 1
When it is output to 9, the process proceeds to step S16.

In step S16, the fourth lookup unit 19 looks up the fourth table using the input code number as an address to obtain the code length and the decoded value. Then, the obtained code length and decoded value are output. After that, the decoding process ends.

As described above, also in the case of this embodiment, the division unit 11, the first lookup unit 13, and the second lookup unit 1 are also included.
5, each processing unit of the third lookup unit 17, the arithmetic unit 18, and the fourth lookup unit 19 sequentially executes respective processes, so that it is not necessary to describe a branch instruction associated with the determination in the decoding algorithm. . Therefore, the decoding process can be executed faster than the above-described conventional decoding device and decoding method.

Hereinafter, as in the case of the first embodiment, the operation of the decoding apparatus having the above-described configuration will be described more concretely by taking the case where the bit string “000101” of the variable length code is input to the divider 11. Explained. The divider 11 divides the input bit string “000101” into three bits of upper 2 bits, middle 2 bits, and lower 2 bits. Then, the upper 2 bits “00” are output to the first lookup unit 13, the middle 2 bits “01” are output to the second lookup unit 15, and the lower 2 bits “01” are output to the third lookup unit 17. Is output.

Then, the first look-up unit 13
Takes the first table with the input upper 2 bits "00" as an address, and the code number parameter "0" and the table address "2-a" to the second table are obtained. Then, the table address “2-a” is sent to the second lookup unit 15, while the code number parameter “0” is sent to the calculator 18.

Next, the second look-up unit 15 receives the middle two bits "01" input from the divider 11 and the first two bits.
Table address “2-a” input from the lookup unit 13
The address of the second table is obtained by using and as an index, and the second table is drawn by the address. Then, the code number parameter "0" and the table address "3-
a ”is obtained. Then, the table address “3-a” is sent to the third lookup unit 17, while the code number parameter “0” is sent to the arithmetic unit 18.

Next, the third look-up unit 17 compares the lower 2 bits "01" input from the divider 11 with the second lower bit "01".
Table address “3-a” input from the lookup unit 15
The address of the third table is obtained by using and as an index, and the third table is drawn by the address. Then, the code number parameter “0” is obtained. Then, the code number parameter “0” is sent to the calculator 18.

Then, the arithmetic unit 18 adds the code number parameters “0”, “0” and “0” output from the first, second and third lookups 13, 15 and 17 and inputs them. The code number "0" of the variable length code is obtained. Then, the obtained code number “0” is output to the fourth lookup unit 19.

Finally, the fourth lookup unit 19
The fourth table is looked up with the code number "0" input from the arithmetic unit 18 as an address, and the code length "2" and the decoded value "0" are obtained. Then, the obtained code length "2" and the decoded value "0" are output.

As described above, in this embodiment, the variable length code having the maximum code length of 6 bits is divided into 2 bits. Then, the first table for searching the “code number parameter” and the “table address to the next table” using the upper 2 bits as an index, and the “table address” of the middle 2 bits and the first table as the index A second table for searching "code number parameter" and "table address to next table", and a third table for searching "code number parameter" using lower 2 bits and "table address" of the second table as indexes. Create a table.
Furthermore, a fourth table for searching for “code length” and “decoded value” is created using the code number as an address and stored in the fourth table storage unit 20.

However, as the element value of the code number parameter in the above-mentioned first to third tables, the code number of the code is given to the address corresponding to the variable length code whose decoding value is determined by subtracting the table, and other than that. "0" is given to the address of. That is, specifically, in the variable length code illustrated in Table 1, specifically, in the case of the first table, the code is “0”.
0 ", and in the case of the second table, reference numerals" 010 "to" 110 "
1 ", and in the case of the third table, reference numerals" 11100 "to" 111 "
The code number of the code is given to the address corresponding to "111".

As a result, the arithmetic unit 18 can obtain the "code number" by adding the "code number parameter" input from each of the look-up units 13, 15 and 17. Then, the fourth lookup unit 19 searches the fourth table using the code number as an address to obtain the "code length" and the "decoded value".

Therefore, the processing units of the divider 11, the first lookup unit 13, the second lookup unit 15, the third lookup unit 17, the computing unit 18, and the fourth lookup unit 19 are different from each other. It is not necessary to determine the processing end of the processing unit, and a decoding processing algorithm without a branch condition can be applied. That is, according to the present embodiment, the decoding process can be executed at high speed. Further, the parameters registered in the first to third tables are only code number parameters. Therefore, the capacities of the first to third tables can be reduced as compared with the first embodiment.

<Third Embodiment> FIG. 5 is a block diagram of a decoding apparatus according to the present embodiment. The present embodiment is intended to further reduce the capacity of each of the first, second and third tables in the second embodiment.

Looking at the relationship between the code number parameters in the second table and the third table in the decoding apparatus of the second embodiment shown in FIG. 3, "2-a" in the second table and "" in the third table The code number parameter of “3-a” is the same, and if the element of the table address is ignored, it is possible to share “2-a” of the second table and “3-a” of the third table.

Further, the first table shown in Table 5 above is
When changed to the first table shown in Table 9,

[Table 9] "2-a", "2-b", "2--" in the second table shown in Table 6 above
c ”and“ 2-d ”are“ 1-b ”and“ 1 ”in the first table shown in Table 9.
It can be rewritten as "-c", "1-d", "1-e". Then, in the third table shown in Table 7, "3-b" and "3-
"c" can be shared with "1-d" and "1-e" of the first table shown in Table 9. Thus, the code number above,
By appropriately setting the code number parameter and the calculation method, it is possible to share and use a part of the first table shown in Table 5, the second table shown in Table 6, and the third table shown in Table 7. Therefore, it is possible to reduce the capacity of each of the first to third tables in the second embodiment.

Therefore, in this embodiment, the first to third tables in the second embodiment are shown in Table 9 as the first table.
The data is collected into one table and stored in the first table storage unit 22. In addition, the fourth table (Table 8) in the second embodiment
The same table as the reference table) is stored in the second table storage unit 30 as the second table. The divider 21,
First lookup unit 23, second lookup unit 25, third
The look-up unit 27, the calculator 28, and the fourth look-up unit 29 are the divider 11, the first look-up unit 13, the second look-up unit 15, the third look-up unit 17, and the calculator 18 in the second embodiment. And fourth lookup unit 19
It has the same configuration as and operates in the same manner.

Hereinafter, as in the case of the first and second embodiments, the bit string "000101" of the variable length code is divided by the divider 21.
The operation of the decoding apparatus having the above configuration will be described by taking the case of inputting into the as an example. The divider 21 inputs the input bit string “000
101 "is divided into three, that is, upper 2 bits, middle 2 bits, and lower 2 bits. Then, the upper 2 bits “00” are output to the first lookup unit 23, and the second lookup unit 25
The middle 2 bits "01" are output to the third lookup unit 2
The lower 2 bits “01” are output to 7.

Then, the first look-up unit 23 is
Subtracts "1-a" in the first table using the input upper 2 bits "00" as an address, and the code number parameter "0"
And the table address "1-b" to the same table are obtained. Then, the table address “1-b” is transmitted to the second lookup unit 25, while the code number parameter “0” is the arithmetic unit 28.
Sent to.

Next, the second look-up unit 25 compares the middle two bits “01” input from the divider 21 with the first two bits.
Table address “1-b” input from the lookup unit 23
An address is obtained by using and as an index, and the first table (“1-b”) is drawn at the address. Then, the code number parameter "0" and the table address "1-b" to the same table are obtained. Then, the table address “1-b” is sent to the third lookup unit 27, while the code number parameter “0”.
Is sent to the calculator 28.

Next, the third look-up unit 27 compares the lower 2 bits “01” input from the divider 21 with the second lower bit “01”.
Table address “1-b” input from the lookup unit 25
The address is obtained by using and as an index, and the first table (“1-b”) is drawn again at the address. Then, the code number parameter “0” is obtained. Then, the code number parameter “0” is sent to the arithmetic unit 28.

Then, the arithmetic unit 28 adds the code number parameters "0", "0", "0" output from the first, second, and third lookups 23, 25, 27, and inputs them. The code number "0" of the variable length code is obtained. Then, the obtained code number “0” is output to the fourth lookup unit 29.

Finally, the fourth lookup unit 29 described above
The second table is looked up with the code number "0" input from the arithmetic unit 28 as an address, and the code length "2" and the decoded value "0" are obtained. Then, the obtained code length "2" and the decoded value "0" are output.

The divider 1 in each of the above embodiments,
11, 21, first lookup unit 3, 13, 23, second lookup unit 5, 15, 25, third lookup unit 7, 1.
7, 27, the arithmetic units 8, 18, 28 and the fourth lookup units 19, 29 are dedicated LSI (Large Scale Integrated Circuit) or CP.
U (central processing unit) or a combination thereof, and part or all of the processing by the above means can be realized not only by hardware but also by software or a combination thereof.

Here, the decryption processing program as the software is recorded in the program recording medium.
The program recording medium in each of the above embodiments is
It is a program medium composed of a ROM (Read Only Memory). Alternatively, it may be a program medium loaded in an external auxiliary storage device and read. In any case, the program reading means for reading the decryption processing program from the program medium is
It may have a configuration in which the program medium is directly accessed and read out, or a RAM (random access
Program storage area (not shown) provided in the memory)
It may be configured to be downloaded to, and to access and read out the program storage area. The download program for downloading from the program medium to the program storage area of the RAM is
It is assumed that it is stored in advance in the system in which the present decoding device is installed.

Here, the program medium is configured to be separable from the main body side, and is a tape system such as a magnetic tape or a cassette tape, a magnetic disk such as a floppy disk or a hard disk, or a CD (compact disk) -RO.
M, MO (magneto-optical) disc, MD (mini disc), DVD
Disc systems of optical discs such as (digital video discs), card systems such as IC (integrated circuit) cards and optical cards, mask ROM, EPROM (UV erasable ROM), EEP
It is a medium that holds a program fixedly, including semiconductor memory systems such as ROM (electrically erasable ROM) and flash ROM.

Further, when the system in which the decoding device in each of the above-mentioned embodiments is installed has a configuration connectable to a communication network including the Internet, the program medium is downloaded from the communication network or the like. Even if it is a medium that fluidly carries the program, it does not matter. The download program for downloading from the communication network in that case is stored in advance in the system. Alternatively, it is assumed that the program is installed from another recording medium.

It should be noted that what is recorded on the recording medium is not limited to the program, and data can be recorded.

As described above, according to each of the above-described embodiments, by providing the arithmetic units 8, 18, and 28, each lookup unit corresponds to the case where the parameter is sent from the preceding-stage lookup unit. It suffices to search the table and send the search result to the arithmetic units 8, 18 and 28, and it is not necessary to determine the end of processing of other processing units. Therefore, an algorithm without a branch instruction can be applied, and the code of the variable length code can be decoded at high speed with a memory having a small capacity as compared with the conventional decoding method.

[0092]

As is clear from the above, the decoding device of the invention according to claim 1 divides the input bit string into two or more bit strings by a predetermined number of bits by the dividing means, and divides each of the divided bit strings. The lookup means refers to the table as an index to obtain a parameter, and the computing means computes the code length or the decoded value based on the obtained parameter, so that the table corresponds to each bit string divided by the dividing means. By using such a table, it is possible to reduce the table capacity. Furthermore, since the dividing means, the lookup means, and the computing means perform sequential processing based on the processing result from the processing means at the preceding stage, an algorithm without a branch condition can be applied.

In recent years, as the clock speed of the CPU has been improved, the pipeline at the time of instruction execution has advanced, and the penalty of reloading the pipeline due to a branch instruction has increased, so that an algorithm without a branch condition can be executed faster. It has become to. Therefore, according to the present invention, the decoding process can be executed at high speed by applying the algorithm having no branch condition.

Further, a code length calculation parameter for calculating a code length or a decoded value calculation parameter for calculating a decoded value is registered in the table in the decoding device according to the second aspect of the present invention, and the arithmetic means is configured to operate as described above. Since the code length or the decoded value is calculated based on the code length calculation parameter or the decoded value calculation parameter output from the lookup means, the code length or the decoded value of the input variable length code can be easily obtained.

Further, in the decoding apparatus of the invention according to claim 3, the input bit string is divided by the dividing means into two or more bit strings for each predetermined number of bits, and each divided bit string is used as an index for the first lookup. By means
The code number calculation parameter is obtained by referring to the first table, the code number is calculated by the calculating means based on the obtained parameter, and the second lookup means makes the second code by using the obtained code number as an index . Since the code length or the decoded value is obtained by referring to the table of
By making the first table a table corresponding to each bit string divided by the dividing means, it is possible to reduce the table capacity. Further, since the dividing means, the first lookup means, the computing means and the second lookup means perform sequential processing based on the processing result from the processing means of the previous stage, an algorithm without a branch condition is used. By applying it, the decoding process can be executed at high speed.

Since the decoding device of the invention according to claim 4 aggregates a plurality of tables corresponding to each bit string divided by the dividing means into one table,
It is possible to further reduce the table capacity.

Further, the decoding method of the invention according to claim 5 is the step of dividing the input bit string into two or more bit strings for each predetermined number of bits, and coding with reference to the table using each of the divided bit strings as an index. Obtaining a length calculation parameter or a decoded value calculation parameter,
Since the method includes the step of calculating the code length or the decoded value based on each of the obtained parameters, the step of dividing the input bit string, the parameter is referred to by referring to the table as in the case of the invention according to claim 1. The step of obtaining and the step of calculating the code length or the decoded value can be sequentially processed based on the processing result from the previous step. Therefore, by applying an algorithm without a branch condition, it is possible to suppress the increase in the storage capacity of the table and execute the decoding process at high speed.

The decoding method of the invention according to claim 6 divides the input bit string into two or more bit strings for each predetermined number of bits, and refers to the first table using each of the divided bit strings as an index. To obtain the code number calculation parameter, to calculate the code number based on the obtained parameter, and to refer to the second table using the calculated code number as an index to obtain the code length or the decoded value. As in the case of the invention according to claim 3, a step of dividing the input bit string, a step of obtaining a parameter by referring to the first table, a step of calculating the code number, and the step of calculating the code length or decoded value with reference to the second table, the processing result from the preceding step It is possible to perform sequential processing on the basis of. Therefore, by applying an algorithm without a branch condition, it is possible to suppress the increase in the storage capacity of the table and execute the decoding process at high speed.

According to a seventh aspect of the present invention, there is provided a program recording medium in which a computer divides an input bit string into two or more bit strings for each predetermined number of bits, and a table using each of the divided bit strings as an index. The lookup means for obtaining a parameter by reference and the decoding processing program for functioning as a computing means for computing a code length or a decoded value based on each of the obtained parameters are recorded. In the same manner as in the above case, an algorithm without a branch condition is applied to each process of dividing the input bit string, obtaining the parameter by referring to the table, and calculating the code length or the decoded value. The decryption process can be executed at high speed.

The program recording medium of the invention according to claim 8 is characterized in that the computer divides the input bit string into two or more bit strings for each predetermined number of bits, and a first division using each of the divided bit strings as an index . First lookup means for obtaining a parameter by referring to the table, computing means for computing a code number based on the obtained parameter, and second computing means for computing the code number as an index . Since the decoding processing program for functioning as the second lookup means for obtaining the code length or the decoded value is recorded by referring to the table of (1), the input bit string is divided as in the case of the invention according to claim 6. processing,
A process for obtaining a parameter by referring to the first table,
An algorithm without a branch condition can be applied to each of the process of calculating the code number and the process of obtaining the code length or the decoded value by referring to the second table, and the decoding process can be executed at high speed.

[Brief description of drawings]

FIG. 1 is a block diagram of a decoding device according to the present invention.

FIG. 2 is a flowchart of a decoding process executed by the divider, the first to third look-up units and the arithmetic unit in FIG.

FIG. 3 is a block diagram of a decoding device different from that of FIG.

FIG. 4 is a flowchart of a decoding process executed by the divider, the first to third look-up units, the calculator and the fourth look-up unit in FIG.

FIG. 5 is a block diagram of a decoding device different from FIGS. 1 and 3.

[Explanation of symbols]

1,11,21 ... Divider, 2, 12, 22, ... First table storage unit, 3,13,23 ... 1st lookup section, 4, 14, 30 ... Second table storage unit, 5,15,25 ... 2nd lookup section, 6, 16 ... Third table storage, 7,17,27 ... 3rd lookup section, 8, 18, 28 ... Operation unit, 19,29 ... Fourth lookup section, 20 ... Fourth table storage unit.

Claims (8)

(57) [Claims] 1. A dividing means for dividing a bit string of a maximum bit length, which is a fixed bit length in a variable-length code, into two or more bit strings for each predetermined number of bits, and the dividing means. A table storing means for storing a table corresponding to each bit string to be divided, and a look for obtaining a parameter for calculating a code length or a decoded value by referring to the table with each bit string divided by the dividing means as an index A decoding apparatus comprising: an up means and an operation means for operating the code length or the decoded value based on the parameter obtained by the lookup means. 2. The decoding device according to claim 1, wherein a code length calculation parameter for code length calculation or a decoded value calculation parameter for decoded value calculation is registered in the table, and the calculation means is A decoding device for calculating the code length or the decoded value based on the code length calculation parameter or the decoded value calculation parameter output from the lookup means. 3. A dividing means for dividing an input bit string into two or more bit strings for each predetermined number of bits by inputting a bit string having a maximum bit length which is a fixed bit length in a variable length code, and a code number calculation parameter. index with but is registered, a first table storing means for a first Te <br/> Buru is stored corresponding to each bit sequence is divided by the dividing means, each bit string divided by said dividing means the first refers to the table, the code number and the first look-up means for obtaining a calculation parameter, the code number calculation obtained in the first look-up means as
A second table in which a calculating means for calculating the code number based on the output parameter and the code number of the variable length code and the code length or the decoded value are registered in association with each other are stored.
A second table storing means and a second lookup means for obtaining the code length or the decoded value by referring to the second table using the code number obtained by the calculating means as an index. Decryption device. 4. The decoding device according to claim 1, wherein a plurality of tables corresponding to each bit string divided by the dividing means are aggregated into one table. . 5. A step of dividing an input bit string into two or more bit strings for each predetermined number of bits, using a bit string of a maximum bit length that is a fixed bit length in a variable-length code as an input, and each of the divided bits. The step of obtaining the code length calculation parameter or the decoded value calculation parameter by referring to the table in which the code length calculation parameter or the decoded value calculation parameter is registered using the bit string as an index, and the code based on each of the obtained parameters A decoding method comprising a step of calculating a length or a decoded value. 6. A step of dividing an input bit string into two or more bit strings for each predetermined number of bits by using a bit string of a maximum bit length which is a fixed bit length in a variable length code as an input, and each of the divided parts. A step of obtaining the code number calculation parameter by referring to the first table in which the code number calculation parameter is registered using the bit string as an index, and a step of calculating the code number based on the obtained code number calculation parameter And a step of obtaining the code length or the decoded value by referring to a second table in which the calculated code number is used as an index and the code number is associated with the code length or the decoded value. Decoding method characterized by the above. 7. A dividing means for dividing the input bit string into two or more bit strings for every predetermined number of bits by inputting a bit string having a maximum bit length which is a fixed bit length in a variable length code, to the computer. A lookup means for obtaining the code length calculation parameter or the decoded value calculation parameter by referring to a table in which the code length calculation parameter or the decoded value calculation parameter is registered using the bit string as an index, and based on each of the obtained parameters. A computer-readable program recording medium having recorded thereon a decoding processing program which functions as a calculating means for calculating a code length or a decoded value. 8. A dividing means, which divides an input bit string into two or more bit strings for each predetermined number of bits, by inputting a bit string having a maximum bit length which is a fixed bit length in a variable length code, to a computer. A first lookup means for obtaining the code number calculation parameter by referring to a first table in which the code number calculation parameter is registered using the bit string as an index, and a code based on the code number calculation parameter obtained above. The calculation means for calculating the number and the second table in which the code number and the code length or the decoded value are registered in association with each other by using the calculated code number as an index are referred to, and the code length or the decoding is obtained. programming the decoding program to function as a second look-up means for obtaining a value is equal to or recorded Non-recording medium.