JPH04219027A - Decoding method for modified huffman code - Google Patents

Abstract

PURPOSE:To decrease the storage capacity and to prevent the processing speed of decoding from being deteriorated by devising the processing of the circuit for the decoding method. CONSTITUTION:A high-order address of a white or black level of an MH decoding table is set to a register H. Then the initial value (00)16 of a low-order address is set to a register L. When an MH code S is inputted by one bit in this state, it is added to a least significant bit of the register L. Then a data stored in registers H, L is used as an address signal to read a data in the MH decoding table from a storage circuit and inputted to an accumulator A, in which 'Pole/Final' of the input data is discriminated. In the case of the 'Final' as a result of the discrimination, the content of the data of the MH decoding table stored in the storage circuit is outputted as a run length. In the case of the 'Pole' and the data set to (00)16, an EOL is detected. With the data not set to (00)16, the data in the accumulator A is moved to the register L and an MH code S inputted newly to a processor is added to the least significant bit of the register L, and the processing above is repeated.

Description

[Detailed description of the invention]

0001

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method for decoding modified Huffman codes.

0002

2. Description of the Related Art Modified Huffman codes (hereinafter referred to as MH codes) are variable length codes in which the number of bits differs for each code. For this reason, when MH codes are transmitted continuously, the code length cannot be predicted on the receiving side, so a method is used in which an MH decoding table is stored in a storage circuit and the MH decoding table is decoded.

[0003] Several methods of creating an MH decoding table have been proposed in the past, depending on the decoding processing speed and the capacity of the storage circuit. For example, there is a method of modifying the address of a storage circuit with an input MH code. In this case, a run length corresponding to the MH code is written in the data in the storage circuit, and if a corresponding run length does not exist, meaningless content is written. However, according to the method shown in the above example, for example, in the case of facsimile communication, the maximum code length of the MH code is 13 bits, so 213
A storage circuit with a storage capacity of bytes (approximately 8 Kbytes) is required.

[0004] Several methods have therefore been proposed to reduce the storage capacity by focusing on the characteristics of MH codes. for example,
In the case of facsimile communication, the 9th bit and above of the MH code are all "0" codes, so only the lower 8 bits of the input code are used to modify the lower byte of the address in the memory circuit, and the upper byte of the address is Create a decoding table so that it can be distinguished by code length. According to this method, the MH decoding table can be created using a storage circuit having a storage capacity of about 3 Kbytes.

However, as is well known, the MH code in facsimile communication has a terminating code for each of white and black.
) are 64 (run length 0, 1, 2, ..., 63), and the makeup code (
There are 40 Make Up Codes (run lengths 64, 128, 192, . . . , 2560), and there are only 208 in total. Therefore, in the conventional MH code decoding system, there is still considerable waste in the storage circuit that stores the MH decoding table.

[0006]

[Problems to be Solved by the Invention] The present invention has been made in view of the drawbacks of the conventional MH code decoding method described above.
It is an object of the present invention to provide a MH code decoding method that uses a storage circuit with a small storage capacity and does not reduce the decoding processing speed.

[0007]

[Means for Solving the Problems] The MH code decoding method of the present invention is such that in a system that transmits information using MH codes, input MH codes are processed in a branched manner when decoding on the receiving side. It is provided with a storage circuit that stores a decoding table for inverse conversion, and decodes by sequentially referring to the decoding table stored in the storage circuit according to the input MH code. To explain in more detail, each address of the memory circuit has MH
Address data indicating two branch points located lower than one branch point in a tree structure indicating the code generation process is stored, and if there is no lower branch point, the corresponding run length is stored. (corresponds to the decoding table above)
. Also, one of the two branch points is indicated using the input MH code and the above address data (not needed for the next two branch points after the top branch point of the tree structure). A read address signal forming means is provided for forming a read address signal.

[0008]

[Operation] Every time one bit of the MH code S is input, the processor 1 refers to the MH decoding table stored in the storage circuit 2 and executes decoding. First, the run-length code always repeats white and black, and the upper address of white or black in the MH decoding table is set in register H, and then the initial value (00) 16 of the lower address is set in register L. When 1 bit of MH code S is input in this state, it is added to D0 of register L, and then the data of the MH decoding table is read using the data of registers H and L as address signals to determine whether or not it is the final branch.

[0009]

DESCRIPTION OF THE PREFERRED EMBODIMENTS The present invention will be explained in more detail below with reference to the accompanying drawings.

FIG. 1 is a diagram showing the MH code generation process in a tree structure. That is, in generating the MH code, a method is used in which two run lengths with the lowest probability of appearance among all run lengths are integrated. The integration formally creates a new probability element, and its probability is given as the sum of the two integrated probability elements. One integration apparently reduces the number of run lengths by one, and the run length groups are newly rearranged in order of appearance probability. Integration of run lengths is performed repeatedly, and the operation ends when all run lengths are finally integrated into one stochastic element. The n run lengths are integrated into one stochastic element by (n-1) integrations.

FIG. 1 shows the above MH code generation process, where Pn (n=1, 2, . . . , 6) represents each run length, and the number in parentheses represents the probability of occurrence. Each code word is shown in the boxed area. For example, the two run lengths with the lowest probability among the run lengths P1 to P6 are P4 and P6, and these two run lengths are first integrated to form the run length G1. And the probability of appearance of run length G1 is run length P4
, P6, which is 0.17. Subsequently, similar processing is performed on run lengths P1, P2, P3, P
5 and G1, and are finally integrated into one run length G5.

The MH code decoding method of the present invention focuses on the MH code generation method described above, and upon decoding, a tree structure as shown in FIG. It converts the code into each run length. To explain in more detail, for example, if the first MH code input is 1, the run length G5 is changed from the run length G5 to the run length G5.
Branches into 3. If the next input MH code is 0, the process branches to run length P5, and the decoding of one code ends. The decoding table is composed of address data indicating each branch point in this tree structure.

FIG. 2 is a block diagram of a decoding circuit showing an embodiment of the present invention applied to facsimile communication.

A memory circuit 2 is connected to the processor (CPU) 1 via an address bus and a data bus. In addition to the MH decoding table, a program for carrying out decoding processing is written in this storage circuit 2. In this embodiment, the processor 1 and the memory circuit 2 are configured in units of 8 bits.

Each time one bit of the MH code S is input, the processor 1 refers to the MH decoding table stored in the storage circuit 2 and executes decoding. In the storage circuit 2, the decoding table corresponding to the white run length and the decoding table corresponding to the black run length are assigned to different addresses.

FIG. 3 shows the data structure of the MH decoding table stored in the storage circuit 2. Here, for example, set the D0 bit to "P
ole/Final” bit, “Pole” when D0 is “0”, and “Final” when D0 is “1”.
It is defined as Next, the meanings of the above "Pole" and "Final" will be explained.

(a) "Pole" means that the MH code S input to the processor 1 is not yet completed. Further, when D7 to D0 shown in FIG. 3 are all "0", it means that eight "0" codes have been input consecutively as MH codes. After that, 8 bits D7 to D0 like this
Data where all are "0" is displayed as (00)16. Therefore, the subsequent processing is EOL (END OF LI
NE) Enter detection mode.

If the data is "Pole" and the data is not (00)16 read from the MH decoding table of the storage circuit 2, the data D7 to D1 shown in FIG. Used for address signals. These address bits A7 to A1 are address signals indicating the next two branch points after the branch point. Then, the newly inputted MH code S (a code of "0" or "1") is used as an address signal for address bit A0 of the MH decoding table. Then, based on these address signals A7 to A0, a read address signal indicating one of the next two branch points is formed, and data is newly read from the MH decoding table.

(b) "Final" means that the input MH code S has been completed. In this case, for example, FIG.
The data D7 bit shown in is allocated to distinguish between the terminating code and the make-up code of the MH code. The remaining 6 bits D6 to D1 represent 64 terminating codes and 40 makeup codes. In other words, bits D6 to D1 represent the run length of the terminating code or make-up code, and in the case of a terminating code, they each represent 25 to 20 bits.
means bit, 211 in case of make-up code
~26 bits.

As explained above, the address signals of the MH decoding table stored in the storage circuit 2 are sequentially modified by the MH code input to the processor 1, and the input MH code S
Branching is repeated according to the data of "Pole" until it reaches "Final".

FIG. 4 is a flowchart outlining the operation of the embodiment shown in FIG.

First, the first run length input after EOL detection is always white, and since the run length is always a repetition of white and black, the upper address of white or black in the MH decoding table is stored in register H. Set to . Next, the initial value (00) 16 of the lower address is set in register L. When one bit of MH code S is input in this state, it is added to the least significant bit of register L. Next, register H,
The storage circuit 2 uses the data stored in L as an address signal.
The data of the MH decoding table is read from the MH decoding table and inputted to the accumulator A. Then, “Pole/F” of the input data
inal” is executed.

[0023] As a result of the "Pole/Final" determination,
In the case of "Final", the contents of D6 to D1 are output as a run length. If the result of the determination of "Pole/Final" is "Pole" and the data is (00)16, the process moves to EOL detection processing. If it is "Pole" and the data is not (00)16, the data in accumulator A is moved to register L, and the MH code S newly input to processor 1 is added to the least significant bit of register L. Then, in exactly the same way as in the above case, reference to the MH decoding table and "Pole/Final" determination of the data are repeatedly executed.

In the above explanation, the processor 1 and the memory circuit 2 are configured in units of 8 bits per word, but the present invention is not limited to this, and can be implemented in exactly the same way even if the unit is 9 bits or more. be able to.

[0025]

Effects of the Invention According to the MH code decoding method of the present invention, to explain the case of facsimile communication as an example, MH
There are 104 codes for each of white and black, and 103 data for each of white and black are written to the next address corresponding to the branch point of the tree structure (104-1=10
3) It becomes necessary. Then, data (
There is one address that stores 00)16. Therefore, according to the MH code decoding method of the present invention, the MH decoding table can be realized in 416 bytes, which has the effect of greatly reducing the required storage capacity compared to the conventional MH code decoding method. has.

Furthermore, the decoding processing time according to the MH code decoding method of the present invention is proportional to the number of input codes, and is almost the same as the decoding processing time according to the conventional method, which also has an excellent effect. are doing.

[Brief explanation of the drawing]

FIG. 1 is an explanatory diagram of a tree structure showing the process of generating an MH code;

[
FIG. 2 is a block diagram showing an embodiment of the present invention;

FIG. 3 is an explanatory diagram showing the data structure in the memory circuit in the embodiment shown in FIG. 2;

FIG. 4 is a flowchart outlining the operation of the embodiment shown in FIG. 2;

[Explanation of symbols]

1... Processor (CPU), 2...Memory circuit, A...Accumulator, H, L...Register, S...Input MH code string.

Claims (1)

[Claims] Claim 1: A decoding table for inversely converting an input modified Huffman code into a branch formula, and two branches located below one branch point in a tree structure showing the modified Huffman code generation process. Address data indicating a point is stored in each address, and if there is no lower branch point at one branch point, the run length and terminating code corresponding to the input series of modified Huffman code strings are stored. A memory circuit that stores data indicating whether the code is a make-up code at the address, and a decoding process that sequentially refers to a decoding table stored in the memory circuit according to the input modified Huffman code and performs decoding. In the modified Huffman code decoding method, the decoding processing means includes registers H, L and an accumulator, and stores a white or black upper address of the modified Huffman decoding table in the storage circuit in the register. H, and setting the initial value of the white or black lower address of the modified Huffman decoding table to the register L, and when one bit of the modified Huffman signal is input to the decoding processing means. , adding this to the least significant bit of the register L, reading the data of the modified Huffman decoding table from the storage circuit using the data stored in the registers H and L as address signals, and transmitting the read data to the accumulator. The step of inputting to A and the Pole/Fon of the input data (D0) input to the accumulator
The step of determining al, and the result of the above determination, Pol
At the time of e, a step of outputting a part of the input data (D6 to D1) as a run length, and when it is a pole and the data is not the initial value of the lower address, the data in the accumulator A is transferred to the register L. a step of adding the modified Huffman code signal S newly input to the decoding processing means to the least significant bit of the register L; referring to the modified Huffman decoding table and reading the data Pole/from the storage circuit; Fi
A method for decoding a modified Huffman code, comprising the steps of repeating determination of nal.