JPH03220870A - How to automatically create a variable-length code decoding table - Google Patents

Abstract

PURPOSE:To automatically generate a decoding table for efficiently decoding a variable length code to one memory by generating the decoding table as to other intermediate and its succeeding nodes from an address succeeding to a termination address to be stored when the decoding table is recursively generated by using the intermediate node as a new root node as to the intermediate node connecting to a root node of a code tree appearing after the intermediate node whose coded table is generated. CONSTITUTION:A decoding consecutive instruction of 'fetch 2-bit and jump to address 1' is written to a head address 'address' = 0 on a decoded table. Then a bit number resulting from subtracting a minimum code bit number = 2-bit from each code bit number respectively is used as a new code bit number and a 'weight' of each termination node is newly calculated in response to the code bit number. Then let 'stp' = 0 be set and the sum of 'weight' of each termination node is calculated in the order of the value of 'point' and the 'point' when the sum reaches '1' at first is used as 'enp'. When the above processing operation is repeated recursively till the intermediate node is lost, the decoded table is finally generated.

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention relates to a method for automatically creating a decoding table for variable length codes that can be expressed as a code tree in one memory.

[Conventional technology]

Zehafman code is a typical example of a variable length code that can be expressed as a code tree. This Huffman code is a variable length code that assigns short codes to events that occur frequently and long codes to events that occur less frequently, so that the overall average code length is the shortest code. As an example of an image data encoding method using this Huffman code, for example,
There is an international standardization proposal for natural still image coding adopted by ISO/JTC1/SC2/WG8. The baseline system in this international standardization proposal employs an encoding method using ADCT (adaptive discrete cosine transform) and Huffman codes.

The Huffman code decoding method in the baseline system of the above international standardization proposal is as follows.

That is, all events are sorted in advance according to the number of code bits, and codes are assigned to all events in order from the smallest number of bits. Each memory address of the decoding table corresponds to each event, and each address stores the value of each event, encoded data, and number of encoded bits. Therefore, first, in the portion representing the encoded data of the memory address corresponding to the first event, only the least significant bit is set to "1" and the other bits are set to 0. Below, the encoded data of the event immediately before the event of interest is “
1”, and if the number of encoded bits increases from the previous event, bit-shift the encoded data to the left (higher) by the increased number of bits, and This is encoded data.

If the above decoding process is considered as a code tree in which the technique on the left of each node corresponds to the code "0" and the technique on the right corresponds to the code "l", the result is as follows. First, we match the first event to the node representing the encoded data with the minimum number of bits, and as we proceed through the code tree to the right, we match each event to the node at the same depth as the number of coded bits. I'll let you do it. When the right end of the code tree is reached, the next step is to move to the left end, and the same operation is repeated.

A specific example of this process is shown in FIGS. 5 and 6. In Figure 5, ", poIol is the serial number used for sorting,""hu"
fftab, value" is the value of the event (for convenience, each value is expressed as alpha abet A to J), "hufftab
, 5ize is the number of code bits, “hufftab, cod
e" indicates encoded data (binary number). Figure 6 is a code tree of Figure 5. In Figure 6, each terminal node has the following characters:
°'paint' = 0 to 9 and "hufftab" corresponding to the terminal node.

value"=A to J, and the other nodes (root and intermediate nodes) are respectively written with serial numbers 0 to 8 according to the order in which the code tree is constructed.

The decoding procedure when using the code tree shown in FIG. 6 is as follows. First, start from the root (node = O) and interpret the input code string bit by bit, and if it is "0", proceed to the left child, and if "1'", proceed to the right child. Repeat this process, and when you reach the terminal node, the value written there is taken as the value of the event to be decoded.

Conventionally, one method of efficiently representing a code tree as shown in Figure 6 in a table is the method proposed by Eibo et al.
“Algorithm Design and Analysis” p.

47, ^, v, by Eiho et al., translated by Nozaki et al., Science Publishing.

1986). According to this, the code tree shown in FIG. 6 is expressed by a decoding table as shown in FIG. 7.

The numbers written on the roots and intermediate nodes in Figure 6 correspond to the two "addresses" in Figure 7, and each "address"
There are two values available for "1eftson" and "rightson'."Leftson" has two values: "1eftson" and "rightson'.
The address of the node (corresponding to the decoding continuation command) is contained, and if the contact point of interest is the terminal node, the value of the corresponding event (corresponding to the decoding end command) is stored. Whether it exists or not is determined using a flag bit. The same applies to "rightson".

To decode using the decoding table shown in Fig. 7, always start from “address” = O, and while looking at the manual code string bit by bit, if
If the value of “ftson” is “1”, “rightson”
” while referring to the value.

Further, as another decoding method, there is a ``Run-length code decoding method'' in Japanese Patent Publication No. 63-38153. This decoding method relates to decoding run-length codes such as modified Huffman codes, and using this method, decoding can be performed as follows.

First, try rewriting the code tree in Figure 6 as shown in Figure 8. The procedure for creating FIG. 8 is as follows. Focusing on the root (node 0) in FIG. 6, it can be seen that there is no node with a depth less than 2 based on this root. Therefore, the intermediate node at depth l (node 1°2) is deleted, and the intermediate node at depth 2 (nodes 3 and 4) and the terminal nodes (nodes A and B) are directly connected to silver (node 0). Hereinafter, by repeating the same operation using nodes 3 and 4 as reference points, FIG. 8 is obtained.

The major difference between Fig. 8 and Fig. 6 is that in Fig. 6, all nodes except the terminal node each have two children.
In contrast to what is called a binary tree, the number of children differs depending on the node in FIG. 8.

The procedure for decoding using FIG. 8 is as follows. root(
Start from node 0), take in 2 bits from the input code string, if “oo” go to node 4, if “11” go to node 3, if “01” or S is “10°” then go to node 3. "A" or "B" is obtained as the value. If you proceed to node 4, take in another 2 bits,
When the process advances to node 3, 1 more bits are taken in, and decoding is continued in the same manner until reaching the terminal node.

In order to express the code tree in FIG. 8 as a table, it is important to note that, first, it is necessary to specify how many hints are to be interpreted together. When in Figure 6, it is always 1
This is because the number of interpretation hits changes depending on the node in Figure 8, although we were interpreting each node one by one. Second, the number of branches varies depending on the number of bits to be interpreted (two for one bit, four for two bits). In Figure 6,
There are always two branches (' left tson' and 'rig
htson") L/, so the table could be expressed easily, but in the case of Figure 8, it is not so easy.

FIG. 9 shows a decoding table for FIG. 8 created with these points in mind. However, the decoding table shown in Fig. 9 is
What was previously represented in one memory is divided into multiple memories and re-expressed.

The contents of the decoding table in FIG. 9 are as follows. In other words, prepare 5 memories O to 4 as decoding tables, write "Import 2 bits" (decoding continuation instruction) to the first address "address=0" of memory 0, and write the bits to be interpreted following this address. 22 = corresponding to the number
Four address spaces are reserved. These four address spaces “address = 1 to 4 contain 2 bits of the input code string.
The instructions for each case are “00”, “01”
, "10", and "11" (in order from left to right in the code tree of FIG. 8). This “address
The specific contents of the instructions stored in s”=1 to 4 are as follows:
If the next node to move to is an intermediate node, for example, “addr
This is a decoding continuation instruction that says "jump to memory 2" as shown in "ess" = 1, and in response, the first address of memory 2 at the jump destination "'address" = O contains the bit that should be interpreted at that node again. A decoding continuation command "capture 2 bits" corresponding to the number is stored.The same process is repeated thereafter.

On the other hand, if the next node to be moved to is the terminal node, a decoding end command such as "event is A" is stored, such as "address"=2 in memory O, and decoding ends there.

Note that the above three types of instructions are distinguished from each other by flag bits.

[Problems to be Solved by the Invention] Conventionally, decoding was performed using a decoding chifur as described above. However, in the case of a decoding table as shown in Fig. 7, the compressed image data string is checked against the encoding table one bit at a time starting from the first address of the decoding table, and it matches the human code string. The disadvantage is that the encoded data must be found, and decoding takes time.

On the other hand, the decoding table shown in Figure 9 is a fixed table devised to express run-length codes in which encoded data is determined in advance, such as modified Huffman codes. This method cannot be directly applied to codes in which encoded data changes adaptively depending on the data. In addition, the special public
No. 153 does not propose any table creation method for automatically creating the decoding table shown in FIG. 9, but merely discloses a run-length code decoding method.

Therefore, the present applicant previously filed an application for a table creation method for automatically creating a decoding table as shown in FIG. This method calculates the range of the sorted events included in each child or descendant of the root of the code tree using the weight for the child of the terminal node corresponding to each event calculated from the code bit number data. , determines whether each child is a terminal node or an intermediate node from the weight, and if the child is a terminal node, writes a decoding end instruction to the decoding table, and if the child is an intermediate node, decodes a decoding continue instruction. By writing to the table, making the child a new root, and repeating the above operation recursively, the ninth
A decoding table for variable length codes as shown in the figure is automatically created. Furthermore, in the method,
Directly connect all terminal nodes corresponding to the event with the minimum code bit number data and intermediate nodes with the same depth as the terminal node to the root, and consider each of these nodes as new children. This makes it possible to automatically create a decoding table more efficiently.

However, in these methods proposed by the applicant,
Since the memory address cannot be set in the decoding continuation command, it must be configured to jump to a different memory each time the decoding continuation command is issued, and it has the disadvantage that multiple memories are required to create a decoding table. Ta.

The present invention has been made under the above circumstances, and its purpose is to improve the above-described method of the applicant, use two values, the value of the input event and the number of sign bits, and use only one. An object of the present invention is to provide a method for automatically creating a decoding table for variable length codes, which can automatically create a decoding table as shown in FIG. 9 using two memories.

[Means to solve the problem]

In order to achieve the above-mentioned object distantly, the present invention is capable of expressing events sorted in descending order of number of code bits and nodes and code number data corresponding to the events as input event data in a code tree. A decoding table for variable-length codes, which has a plurality of instructions selected according to the result of a bit string extracted from the beginning of variable-length coded data that is continuously transmitted. The range of the sorted events included in each child of the root of the tree or its descendants is determined using the weight for the child of the terminal node corresponding to each event calculated from the code number data, and the weight is calculated. Determine whether each child is a terminal node or an intermediate node from In addition, a method for automatically creating a variable-length code decoding table by repeating the above operation recursively with the child as a new root.B.In this case, if the child is an intermediate node, After recursively creating a decoding table for the child and its descendants as a root, the end address of the decoding table for the child and descendants is stored, and after the child for which the encoding table was created, When recursively creating a decoding table for another child connected to the root of the code tree that appears, using that child as a new root, the creation of the decoding table for the other child and its descendants is performed using the stored terminal address. It is designed to continue from the next address.

Furthermore, in the above method, all terminal nodes corresponding to the event having the minimum code bit number data with respect to the root of interest and intermediate nodes having the same depth as the terminal node are directly connected to the root, and these nodes are Each child is considered to be a new child, and the end address of the decoding table corresponding to these multiple children is calculated from the minimum number of code bits and stored, and the child that is the first intermediate node that appears among the children is When recursively creating a decoding table for the child and its descendants using the decoding table as a new root, the creation of the decoding table is continued from the address next to the end address of the stored decoding table. .

[For production]

If the child is an intermediate node, after creating a decoding table for the child and its descendants, store the end address of the decoding table, and store the decoding table for the next other child and its descendants. Continuously create from the address following the terminal address. Therefore, a decoding table that can efficiently decode variable length codes is automatically created in one memory.

Furthermore, all terminal nodes corresponding to the event with the minimum code bit number data and intermediate nodes having the same depth as the terminal node are directly connected to the root, and each of these nodes is created as a new child. A decoding table is created using the code tree considered as Therefore, a decoding table that allows more efficient decoding is automatically created in one memory.

〔Example〕

Embodiments of the present invention will be described below with reference to the drawings.

FIG. 2 is a code tree having exactly the same structure as FIG. 6 described above. In the case of the present invention, in this code tree, each end node A-J is given the "number of code bits"("huf" in FIG.
ftab, 5ize" value) and the "weight" of that node. For example, at the terminal node A, of the two numbers written below the node, the left number 2 indicates the number of sign bits. , the value (1/4) in parentheses on the right represents the weight.This weight is defined as 1/2'', where n is the number of code hits at the terminal node. The “weight” here is the weight for the root of each terminal contact, and the “′weight” of all terminal nodes
The total sum is l.

The present invention automatically creates a decoding table using the code tree shown in FIG. An example of the processing will be described using the method according to claim (2) as an example.In the case of the method according to claim (1), the code tree shown in FIG. Similar processing can be performed using the code tree of .

Now, when carrying out the method according to claim (2), the code tree shown in FIG. 2 is first transformed as shown in FIG. 3. That is, in FIG. 2, since the minimum number of sign bits of input event data is 2 bits, the terminal node A corresponds to an event with the number of sign bits=2.

B and intermediate nodes 3 and 4 at the same depth are all directly connected to the root (node 0). The new code tree obtained in this way is shown in FIG.

As can be seen from Figure 3, the values of "paint" (numbers in the lower half of nodes A-J) of each terminal node corresponding to each event included in one child or its descendants are continuous according to the depth. Therefore, to express the range of events included in one child or its descendants, the corresponding “p
It can be seen that it is sufficient to indicate the minimum and maximum values of ``aint''.Thus, from now on, the minimum value will be referred to as ``stp'' and the maximum value as ``enp''.The three embodiments will be based on this FIG. The decoding table shown in FIG. 1, which is equivalent to the decoding table shown in FIG. 9, is automatically created in one memory as follows.

That is, first, a decoding continuation command "fetch 2 bits and jump to address l" is written to the first address "" address = 0 of the decoding table shown in FIG.

22 bits here corresponds to the value of the minimum number of code bits mentioned above.

By the way, since the minimum number of code bits is 2, the number of children can be calculated as 22=4. Therefore, it can be seen that four addresses are required to describe the portion of the encoding table corresponding to these four children. Up to this point, the decoding table in Figure 1 still has 'address =
Since instructions are only written to 0, the end address of the encoding table for describing these four children is O+
4=4, that is, "address=4." Therefore, this terminal address "address=5" is set as enad=4 and stored.

Next, the new number of code bits is obtained by subtracting the minimum number of code bits = 2 bits from each code bit number in FIG.
"Weight" is also newly calculated.

This is shown in FIG. From FIG. 4, it can be seen that, for example, the sum of the "weights" of the descendant events (E, F, G, H, I, J) of node 4 is l. The other three nodes (A, B,
The same applies to 3).

Then, in Fig. 4, set "stp" = 0, and then calculate the sum of "weights" of each terminal node in the order of the "paint" value, and when the sum becomes 1 for the first time, " p
aint” is “enp”. In the case of Fig. 4, the node A
Since the “weight” of is 1, “enp = “stp” =
0, and it can be seen that there is only one event included in this first child (node A) and its descendants. Therefore, it can be seen that this child (node A) is the terminal node, so the ""address" in the decoding table in Figure 1
A decoding end command "°event is A" is written in =2 and the process proceeds to the next step.

Next, the same process as above is performed by setting ° “stp” = 0 + 1 = 1, but here again the next node B is “weight °
'=1, and "enp"="stp"=1.

Therefore, it can be seen that the second child (node B) is also a terminal node, so like the first child, "
Write the decoding end command “Event is B” to address = 3 and proceed to the next step.

Next, the same process is performed with "stp" = 1 + 1 = 2, but here "enp = 3, so the third child (node 3) is an intermediate node that has descendants, and the events included in the descendants It can be seen that the number of is 2. Also, “stp”
Since the number of sign bits of =2 (node C) is l, node 3
It can be seen that the minimum code length when is regarded as a new root is 1 bit.

Furthermore, as mentioned above, the terminal address "enad"=4
Since I remember that, “addr” in the decryption table
It can be seen that the address after ess = 5 is a free address.

Therefore, write the decoding continuation command "fetch l bit and jump to address 5" to "address = 4" in the decoding table.
1 point 3) is regarded as a new root, and the above operation is repeated recursively. As a result, the “event at address=5” is C.
” and “event is D” at address=5. Then, the end address of the decoding table for this node 3 part “address =
6 is stored as “enad”=6.

Next, set "stp" = 3 + 1 = 4 and add the fourth child (
Similar processing is performed for node 4). At this time, “st”
Since the number of code bits for p"=4 and "stp"=4 (node E) is 2, the minimum code length when node 4 is regarded as a new root is 2 bits. Therefore, the fourth child (
It can be seen that node 4)- is an intermediate node with descendants.

Also, the stored terminal address is “enad”=6
It is.

Therefore, we write a decoding m-continuation instruction that says ``Fetch 2 he notes to address = 1 and jump to address 7'' in the decoding table.Then, we consider the fourth child (node 4) we are looking at as a new root. , the same processing operations as described above are repeated recursively.

The above processing operations are repeated recursively until there are no intermediate nodes, and finally a decoding table as shown in FIG. 1 is created.

In the above embodiment, the minimum number of code bits is 2, but this is just an example. Also, in connection with this, the above-mentioned "2 bits are taken in" in memory.

Needless to say, the number of bits taken in by the decoding instruction also changes.

〔Effect of the invention〕

According to the method described in claim (1), when the child is an intermediate node, after recursively creating a decoding table for the child and its descendants by using the child as a new root,
The end address of the decoding table for the child and descendant part is memorized, and for other children connected to the root of the code tree that appear after the child that created the encoding table, recursively use that child as a new root. When creating a decoding table for the other child and its descendants, the creation of the decoding table for the other child and its descendants continues from the address next to the stored end address. A decoding table can be automatically created in one memory.

In addition, when using the method described in claim [2], all terminal nodes corresponding to the event having the minimum code bit number data and intermediate nodes having the same depth as the terminal node are all root nodes. These nodes are each considered as a new child, and the end address of the decoding table corresponding to these multiple children is calculated from the minimum number of code bits and stored, and the first node among the children is When recursively creating a decoding table for the child and its descendants using a child that is an intermediate node appearing in as a new root, the decoding table is created from the address next to the end address of the stored decoding table. Let's continue! Therefore, it is possible to automatically create a decoded chifur that can be decoded more efficiently in one memory.

[Brief explanation of drawings]

FIG. 1 is a diagram showing an example of a decoding code tree created by the method of the present invention, FIG. 2 is a diagram showing an example of a code tree for creating a decoding table by the method of the present invention, and FIG. Figure 4 shows the code tree rewritten by directly connecting the nodes with the minimum code bit depth to the roots. Figure 4 shows the code tree re-weighted in Figure 3. Figure 5 shows a natural still image. A diagram showing an example of a decoding table in the international standardization proposal for encoding. Figure 6 is a diagram showing a code tree for the decoding table in Figure 5. Figure 7 is an example of a decoding table according to Eiho's method. Figure 8 is a diagram showing a code tree rewritten by directly connecting the node with the minimum code bit depth to the root in Figure 6S. Figure 9 is a diagram showing decoding using the code tree in Figure 8. FIG. 3 is a diagram showing an example of a conversion table. Patent Source Co., Ltd. Riko No. 1 Fig. 1 r e++ Saefu Kakuban 3 Tree σ1'' Fig. Fig. 3 Dark 13 (-i) 3 (-fl 3 Dark) Hana 3 Bacteria 1:3.
\・′? ″f2t<1 chou (Shinire Tsubaki Vinegar No. ♂ Non・No.
η 51°JFigure 5Figure 5I! 1st tree e4 hiteb 1st 5th ^? t%q book 1st figure half 6 ffi IZ R<1'7 Z d ・(' ツト3yn%J,UJ+5JJtlemma 1Jlr:. 2nd figure of cat issue (C1) mebeniwa ○ 8th cause ζ now end^ne Nirig boots: Shino 5
1st diagram

Claims (2)

[Claims] (1) A variable-length code decoding table that can express events sorted in descending order of code bit number and code bit number data corresponding to the event as input event data as a code tree, and that is continuous. It has a plurality of instructions selected according to the result of a bit string extracted from the beginning of variable-length encoded data that is transmitted by a predetermined number of bits, and includes the sorted instructions included in each child or descendant of the root of the code tree. The range of events is calculated using the weight for the child of the terminal node corresponding to each event calculated from the code bit number data, and from the weight it is determined whether each child is a terminal node or an intermediate node. In the case of a node, a decoding end instruction is written to the decoding table, and if the child is an intermediate node, a decoding continue instruction is written to the decoding table, and the above operation is repeated recursively with the child as a new root. In a method for automatically creating a decoding table for a long code, if the child is an intermediate node, the decoding table for the child and its descendants is recursively created using the child as a new root, and then the decoding table for the child and its descendants is recursively created. The end address of the decoding table for the child and descendant parts is memorized, and for other children connected to the root of the code tree that appear after the child that created the encoding table, recursively use that child as a new root. A method for automatically creating a decoding table for a variable length code, characterized in that when creating the decoding table, the creation of the decoding table for the other child and its descendants is continued from the address next to the stored end address. . (2) In the method described in claim (1), all the terminal nodes corresponding to the event having the minimum code bit number data and the intermediate nodes having the same depth as the terminal node are set as roots based on the root of interest. These nodes are directly connected, each of these nodes is considered as a new child, and the end address of the decoding table corresponding to these multiple children is calculated from the minimum number of code bits and stored, and the first node among the children is When recursively creating a decoding table for the child and its descendants using the child, which is an intermediate node, as a new root, the decoding table is created from the address next to the end address of the stored decoding table. A method for automatically creating a decoding table for a variable length code, characterized in that: