JP2833743B2 - MH code decoder - Google Patents

Description

Description: TECHNICAL FIELD The present invention relates to an MH (Modified Huffman) code decoder. [Prior art] The MH (Modified Huffman) code is mainly used for compressing one-dimensional data of a document image of a black and white pixel of a facsimile. The CCITT general meeting was held in November 1980 (Showa 55). Recommended as T.4. This MH code is a code in a separate table after [Effect of the Invention] in this specification, and this code will be specifically described with reference to the different table. First, the FAX reads black and white pixels in one dimension from the edge of the document. If the first 4 pixels are white, the next 133 pixels are black, and the next 1588 pixels are white, the corresponding MH code is Will be described. In the separate table, the portion where four pixels correspond to white is first searched for a portion in which the “run length”, which is the length of a continuous white pixel or black pixel, is 4, and then represents a white pixel on the right side of this portion. Look for the code of the "white run" part and obtain 1011 as the code. Next, in the same table, when a portion where 133 pixels correspond to black is searched, there are run lengths of 128 and 192, but no run length. In this case, since the number of pixels 133 is 133 = 128 + 5,
It is necessary to divide into 128 pixels and 5 pixels. Therefore, looking at the portion where the run length is 128, the code of the “black run” portion representing the black pixel on the right side of this portion is searched, and the code 000011001000 is obtained. Next, the remaining five pixels (= 133-128) are coded black. In the separate table, for the portion where 5 pixels correspond to black, first, a portion having a run length of 5 is searched, and then the code of the black run portion on the right side of this portion is searched to obtain 0011... Next, similarly in the separate table, the part where 1588 pixels correspond to white first has a run length between 1536 and 1600, so look at the part with the smaller run length of 1536, and then on the right side of this part The code of a certain white run is searched, and 010011001... Is obtained as the code. By the way, this part is 15 if not MH encoded.
Although it becomes large data of 36 bits, it becomes only 9-bit data (010011001) when encoded. Next, since 1588 pixels are white, 1536 pixels can be encoded, and the remaining 52 pixels (= 1588-1536) are encoded in white. In the separate table, for the portion where 52 pixels correspond to white, first, a portion with a run length of 52 is searched, and then the code of the white run portion on the right side of this portion is searched, and as a code, 01010101... By arranging these five MH codes sequentially, the following MH code string is created. 1011000011001000001101001100101010101... The MH code also has EOL indicating the end of the pixel read in the one-dimensional direction. Now, the MH-encoded data is decoded into the original black and white pixels, and the MH encoding shown in the attached table will be further described. There is a rule that the beginning of the MH code string is a white run (in the case of a black pixel at the beginning, the run length of the white run is 0).
(MH code is used), it is found from the first bit to which run length applies, and it can be seen that 1011 having a run length of 4 corresponds, and that four white pixels are arranged. Next, by removing the decoded 1011 from the MH code string, the following code string 000011001000001101001100101010101... Can be obtained. As can be seen, the MH code is divided into a "terminating codeword" and a "makeup codeword" as shown in a separate table. The 1011 MH code used for decoding is included in the "terminating codeword" indicating that the pixel of that color ends with this code, and the next pixel is black, It can be seen that it is sufficient to check whether or not the condition applies to the run length. When the collation is performed, it can be seen that 000011001000 having a run length of 128 corresponds, and that 128 black pixels are arranged. Also, this MH code is included in the "make-up code word" (indicating that one "terminating code word" of the same color follows next) as shown in the separate table, so the next pixel remains black, It can be seen that the run length of the code of the black run should be checked. Therefore, the decoded 00001100
By removing 1000 from the MH code sequence, the following code sequence 001101001100101010101 is obtained. Again, when it is checked which of the black run codes corresponds to which run length, it can be seen that 0011, which has a run length of 5, corresponds, and that the black pixels are lined up with 133 of 128 + 5. The MH code of 0011 is included in the “terminating codeword”, and it can be seen from this that the next pixel is white and the run length of the white run code should be checked. The correspondence between the arrangement of black and white pixels and the MH code string has been described above. In the following description, "terminating codeword" is abbreviated as T code, and "makeup codeword" is abbreviated as M code. The MH code decoder decodes the MH code and outputs the run length. The code length of the MH code is from 2 to 13. Therefore, it is sufficient to decode consecutive 13 bits at a time. Conventionally, in this type of MH code decoder, a continuous 13-bit code has been input as it is. FIG. 3 shows an example of a conventional MH code decoder. In the figure, a shift register 301 is a register for sequentially inputting a code string of an MH code to a decoding logic circuit 302. In the figure, the most significant bit is MSB and the least significant bit is LSB. The shift register 301 is 16 bits, and is latched by a latch signal 311 described later.
Latch the MH code 8 bits at a time. The held data is shifted one bit at a time in the LSB direction by a shift pulse 312 described later. The decoding logic circuit 302 is realized by using a read only memory (hereinafter, referred to as ROM). The decoding logic circuit 302 inputs the MH code 13 bits at a time from the shift register 301, inputs the run length to the run length integrator 303, 304
And outputs the code length to the code length integrator 310. The run length integrator 303 is a color inversion circuit 304
The run length is integrated until the color inversion signal 305 comes from. The color inversion circuit 304 receives a signal indicating the distinction between the T code and the M code from the decoding logic circuit 302, and outputs a color inversion signal 305 and a decoding logic selection signal 306 when detecting that the signal is a T code. The color inversion signal 305 is connected to the run length integrator 303 as described above. Further, the decoding logic selection signal 306 is output to the decoding logic circuit 302. The code length integrator 310 receives the code length from the decoding logic circuit 302 and generates the same number of shift pulses 312 as the code length. Further, the code length is integrated and a latch signal 311 is output every 8 bits. The operation of decoding the MH code in FIG. First,
The start signal (not shown) in the shift register 301 causes MH
Enter the sign 16 bits. It is assumed that the start is a white run.
The lower 13 bits of the input 16 bits are the decoding logic circuit
At 302, the run length, T code / M code, and code length are output. If the code is an M code, the color inversion signal 305
Becomes inactive, and the run length is also integrated in the next decoding. The decoding logic selection signal 306 is also inactive, and the next decoding is also a white run. If it is a T code, the color inversion signal 305 becomes active and the run length is newly added from the next decoding. Also, the decoding logic selection signal 306 becomes active, and the next decoding becomes a black run. Code length integrator 310
Generates the same number of shift pulses 312 as the code length, and the contents of the shift register 301 are shifted by the code length. Also,
When the latch signal 311 becomes active, the shift register 3
An 8-bit MH code is input to 01. The output of the run length integrator 303 when the code becomes the T code is the decoded data. In this example, since the run length is 2560 at the maximum from Table 1, the run length output to the run length integrator 303 is 12 bits, and the code length output to the code length integrator 310 is 4 bits. Therefore,
If the T code is represented by one bit, the output from the decoding logic circuit 302 is a total of 17 bits. At this time, if the decoding logic circuit 302 is configured by a ROM, the total number of bits is 2 ¹⁴
× 17 = 272K bits. [Problems to be Solved by the Invention] As described above, in the conventional MH code decoder, when the decoding logic circuit is configured by ROM, the total number of bits is 2 ¹⁴ ×
17 = 272 Kbits, and there is a problem that the amount of hardware is too large. Therefore, the object of the present invention is to use a small amount of hardware.
It is to realize an MH code decoder. [Means for Solving the Problems] The MH code decoder according to the present application performs MH decoding when decoding a white run.
Only 9 bits are read continuously from the beginning of the undecoded part of the code string of the code, and the MH code having a run length of 0 to 1728 of a white run having an MH code of 9 bits or less is decoded, and 11 bits are decoded. It has a decoding logic circuit consisting of one memory of 9-bit input, which outputs a detection signal without decoding the MH code having a run length of 1792 or more of the white run. Example Next, an example of the present invention will be described with reference to the drawings. First Embodiment FIG. 1 is a block diagram showing a first embodiment of the present invention. In the figure, a shift register 101 is a register that supplies a code sequence of an MH code to a decoding logic circuit 121, a decoding logic circuit 122, and a decoding logic circuit 123. MS is the upper side in the figure.
B, the lower side is LSB. The shift register 101 is 16 bits and latches the MH code 8 bits at a time by a latch signal 111 described later. The data inside is shifted one bit at a time in the LSB direction by a shift pulse 112 described later. In this embodiment, the decoding logic circuit 121 is a decoding logic circuit for a white run, the decoding logic circuit 122 is a decoding logic circuit for a black run and a black and white common run, and the decoding logic circuit 123 is a decoding circuit for a part of black runs. It is a chemical logic circuit. Each of the decoding logic circuit 121, the decoding logic circuit 122, and the decoding logic circuit 123 inputs the MH code from the shift register 101 by 9 bits and sets the run length, the T code / M code, and the code length. Output to the multiplexer 130. Also, the decoding logic circuit 122
Outputs a continuous zero detection signal. Multiplexer 130
Selects one of the pieces of information output from the three decoding logic circuits according to a decoding logic selection signal 132 described later, and sends the run length to the run length integrator 103 and the color inversion circuit 1
The T code / M code is output to 04, the code length is output to the code length integrator 110, and the continuous zero detection signal is output to the decoding logic selection circuit 131. The decoding logic selection circuit 131 outputs a decoding logic selection signal 132 to the multiplexer 130. The run length integrator 103 integrates the run length until the color inversion signal 105 from the color inversion circuit 104 comes. The color inversion circuit 104 includes the multiplexer 1
A signal representing the distinction between the T code and the M code is input from 30. When the signal is detected as a T code, a color inversion signal 105 and a decoding logic selection signal 132 are output. The code length integrator 110 receives the code length from the multiplexer 130 and generates the same number of shift pulses 112 as the code length. Further, the code length is integrated and a latch signal 111 is output every 8 bits. Next, the operation will be described. FIG. 4 shows an outline flow of the processing. A start signal not shown in the shift register 101 causes M
Input 16-bit H code. For the sake of simplicity, it is assumed that the beginning is a white run. The lower 9 bits of the input 16 bits are supplied to the decoding logic circuit 121, the decoding logic circuit 122, and the decoding logic circuit 123. Since the beginning is a white run, the output from the decoding logic circuit 121 is selected by the multiplexer 130. Here, from the relationship shown in the attached table, if the least significant consecutive 8 bits of the input 9 bits are "0000 00
If it is not 01 ", the decoding logic circuit 121 outputs the run length, the T code / M code, and the code length. If the code is M code, the color inversion signal 105 becomes inactive and the run length becomes It is also integrated in the next decoding, and the decoding logic selection signal
132 is also inactive and the next decryption will be a white run.
In the case of the T code, the color inversion signal 105 becomes active, and the run length is newly integrated from the next decoding. Also, the decoding logic selection signal 132 becomes active, and the next decoding becomes a black run. The code length integrator 110 generates the same number of shift pulses 112 as the code length, and the contents of the shift register 101 are shifted by the code length. When the latch signal 111 becomes active, the next 8-bit MH code is input to the shift register 101. The output of the run length integrator 103 when the code becomes the T code is the decoded data. If the least significant consecutive 8 bits of the input 9 bits are "0000 000
If "1", the decoding logic circuit 121 determines that the run length, T code /
Outputs a continuous zero detection signal in addition to the M code and code length. At this time, the run length is "0", the T code / M code is M code, and the code length is "4". The color inversion signal 105 becomes inactive, and the run length is integrated in the next decoding.
Further, the decoding logic selection circuit 131 receives the continuous zero detection signal and the color inversion signal 105 and outputs a decoding logic selection signal 132, and the next decoding is a white run, but a decoding logic circuit to be selected. To the decoding logic circuit 122. The code length integrator 110 generates the same number of shift pulses 112 as the code length, that is, four shift pulses. The contents of the shift register 101 are shifted by a predetermined bit of 4 bits. Next, the lower 9 bits from the shift register 101 are again decoded logic circuits 121, 122, and 123.
Enter. By the above operation, this time the decoding logic circuit 12
The output from 2 is selected by multiplexer 130. The following operation is the same as that described above. Next, consider the case of a black run. Shift register
9 bits of the MH code input from 101 are used as the decoding logic circuit 12
1. The decoding logic circuit 122 and the decoding logic circuit 123 are entered.
In the case of a black run, the least significant four consecutive bits out of the input 9 bits are "0000" in order from the LSB, according to the relationship shown in the attached table.
If not, the output from the decoding logic circuit 123 is selected by the multiplexer 130. The decoding logic circuit 123 outputs the run length, the T code / M code, and the code length. In this case, since the code is a T code, the color inversion signal 105 becomes active, and the run length is newly integrated from the next decoding. Also, the decoding logic selection signal 106 becomes active, and the next decoding is a white run. The code length integrator 110 generates the same number of shift pulses 112 as the code length, and the contents of the shift register 101 are shifted by the code length. When the latch signal 111 becomes active, the next 8-bit MH code is input to the shift register 101. The output of the run length integrator 103 is the decoded data. If the lowest 4 consecutive bits among the input 9 bits are “0000”, the decoding logic circuit 122 is selected. The decoding logic 122 includes a run length,
A detection signal of continuous zero is output in addition to the T code / M code and the code length. The run length at this time is “0”, T code / M
The code is M code and the code length is "4". The color inversion signal 105 becomes inactive, and the run length is integrated in the next decoding. Further, the decoding logic selection circuit 131 receives the continuous zero detection signal and the color inversion signal 105, outputs a decoding logic selection signal 106, and selects the decoding logic circuit to be selected because the next decoding is also a black run. It is instructed to switch to the decoding logic circuit 122 again. The code length integrator 110 generates the same number of shift pulses 112 as the code length, that is, four shift pulses. The contents of the shift register 101 are shifted by 4 bits. Next, the lower 9 bits from the shift register 101 enter the decoding logic circuit 121, the decoding logic circuit 122, and the decoding logic circuit 123 again. By the above operation, the output from the decoding logic circuit 122 is selected by the multiplexer 130 again this time. The following operations are the same as those described above. According to this embodiment, the input to the decoding logic may be 9 bits. Further, since the decoding logic circuit 123 only handles the case of a short black run, the decoding logic circuit 123 can be configured by a simple logic circuit. If the remaining two decoding logic circuits are to be constituted by ROM, the total number of bits is 2 ⁹ × 17 × 2 = 17K bits. Even if the logic circuit of the decoding logic circuit 123 and the hardware of the multiplexer 130 and the decoding logic selection circuit 131 are added, the hardware amount of the ROM of 2 ¹⁴ × 17 = 272 Kbits is far less. . Second Embodiment FIG. 2 is a block diagram showing a second embodiment of the present invention. In the figure, the input registers 241 and 242
Inputs an MH code in accordance with a latch signal 243 and a latch signal 244 described later. The barrel shifter 201 is a register that inputs a code string of the MH code to the decoding logic circuit 221, the decoding logic circuit 222, and the decoding logic circuit 223. The barrel shifter 201 has 16 bits, and the MH is controlled by a latch signal 211 described later.
A code string of codes is input from the input register 241 and the input register 242. In the figure, the upper part is the MSB and the lower part is the LSB. The data in the middle is shifted in the LSB direction by the number of bits indicated by the shift number 213 by a shift pulse 212 described later. In this embodiment, the decoding logic circuit 221 is a decoding logic circuit for a white run, the decoding logic circuit 222 is a decoding logic circuit for a black run and a black and white common run, and the decoding logic circuit 223 is a decoding for a part of black runs. It is a chemical logic circuit. Each of the decoding logic circuit 221, the decoding logic circuit 222, and the decoding logic circuit 223 inputs the MH code from the barrel shifter 201 by 9 bits, and sets the run length, the T code / M code, and the code length to a multiplexer. Output to 230. The decoding logic circuit 221 and the decoding logic circuit 222 output a continuous zero detection signal. The multiplexer 230 selects one of the pieces of information output from the three decoding logic circuits according to a decoding logic selection signal 232 described later, and sends the run length to the run length integrator 203 and the run length to the color inversion circuit 204. For the T code / M code, the code length is output to the code length integrator 210 and the continuous zero detection signal is output to the decoding logic selection circuit 231. Decoding logic selection circuit 23
1 outputs the decoding logic selection signal 232 to the multiplexer 230. The run length integrator 203 integrates the run length until a color inversion signal 205 from the color inversion circuit 204 is received. Color inversion circuit 204
Receives a signal representing the distinction between the T code and the M code from the multiplexer 230, and outputs a color inversion signal 205 and a decoding logic selection signal 206 when detecting a T code. The code length integrator 210 receives the code length from the multiplexer 230 and generates a shift pulse 212 and a shift number 213. Further, the code length is integrated and a latch signal 211 is output every 8 bits. In this embodiment, the operation of the code length integrator 210 is different from that of the first embodiment. The code length integrator 210 is connected to the multiplexer 2
When a code length is input from 30, a shift pulse 212 is generated. At this time, the shift number 213 is simultaneously output, and this value is given by the remainder of 8 of the integrated value of the code length. Further, it outputs the latch signal 211 to the barrel shifter 201 and outputs it to either the input register 241 or the input register 242. At this time, the latch signal 243 and the latch signal 244 are generated from the latch signal 211. In this embodiment, since the shift of the MH code is performed in one clock using the barrel shifter, there is an advantage that the processing is faster than in the first embodiment. [Effects of the Invention] As described above, according to the present invention, there is an effect that the amount of hardware of the MH code decoder can be reduced.

BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 is a block diagram showing a first embodiment of the present invention, FIG. 2 is a block diagram showing a second embodiment of the present invention, and FIG. FIG. 4 is a flow chart showing an outline flow of processing of the first embodiment. 101 shift register, 103 run length integrator, 104 color inversion circuit, 105 color inversion signal, 110 code length integrator, 111
Latch signal, 112: shift pulse, 121, 122, 123: decoding logic circuit, 130: multiplexer, 131: decoding logic selection circuit, 132: decoding logic selection signal, 201: barrel shift,
203: run length integrator, 204: color inversion circuit, 205: color inversion signal, 210: code length integrator, 211: latch signal, 212: shift pulse, 213: shift number, 221, 222, 223: decoding logic circuit, 230 ... Multiplexer, 231 ... Decoding logic selection circuit,
232: decoding logic selection signal, 241, 242: input register, 24
3,244 ... Latch signal.

Claims (1)

(57) [Claims] When decoding a white run, the undecoded part of the code sequence of the MH code is read only 9 bits continuously from the beginning, and the run length of the white run having the MH code of 9 bits or less is from 0 to 1728. A decoding logic circuit consisting of one memory of 9-bit input for decoding a MH code and outputting a detection signal without decoding an MH code having a white run of 11 bits or more and a run length of 1792 or more. Characteristic MH code decoder.