JPS5836073A - Pair run encoding system - Google Patents

Abstract

PURPOSE:To improve coding efficiency and to perform linear coding by selecting a pair of runs on adjacent black and white lines of a binary signal in combination, and coding the sum length of the pair of black and white runs and the length of either black or white run in each pair. CONSTITUTION:A facsimile signal from an input terminal 1 is stored in a memory 10 temporarily, and then applied to gate circuits 21-24 together with a signal delayed by one bit through a delay circuit 31. By the outputs of the circuits 21 and 22, a counter 41 counts white runs, and by the outputs of the circuits 23 and 24, a counter 42 counts black runs. The outputs of those counters 41 and 42 are added together by an adder 50 to find the run length of pairs of black and white runs. The value of this adder 50 is coded by a coder 61, whose output is applied to a signal synthesizing circuit 70; and a coder 62 references the counted value of the counter 42 to code the output of the adder 50, thereby applying the result to the circuit 70. Further, a block 2 processes white run at a large blank part on the right-hand side, and the result is applied to the circuit 70 through a coder 63, thus improving coding efficiency.

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a one-dimensional encoding system for a two-electronic signal train such as a facsimile signal.

Conventionally, the Consultative Committee for International Telegraph and Telephone (CCIT)
Modified Huffman standardized by T) 1-F7 (Modified Huffman:
There is a MH) method. In this method, run lengths in the range from O to 63 pixels (the length of pixel rows with the same polarity) are encoded using only the terminating code shown in Table 1, and runs of 64 pixels or more (pixel rows with the same polarity) are encoded using the terminating code shown in Table 1. ) is first encoded with a make-up code (Table 2) representing a run length equal to or less than that run length, and then the difference between the actual run and the run length represented by the make-up code is encoded as a terminating code. It is encoded by

In this way, in the conventional MH system, as is clear from Table 11 and Table 2, the code word (code) is fixedly determined for the entire range of run lengths for each of the white run and black run. As long as a coding system is used, there is a limit to the improvement in coding efficiency.

The present invention was made in view of the above-mentioned prior art, and aims to provide a pair-run encoding method which is a one-dimensional encoding method with high encoding efficiency. The run is called a "pair run"),
The two run lengths 2 1 Terminating code table 2 Make-up code (&1 fbl for standard paper width 3 for extended paper width This method is characterized by encoding the run length of one run.

The present invention will be explained in detail below using the drawings.

First, the present invention will be explained in detail using FIG.

In the figure, (a) shows a pixel column, where squares represent pixels and the shaded areas represent black pixels.

fbl indicates an encoding example. In the figure, the run length of the first pair of white run and black run is 5, so it is encoded as 'J100' using the MH white run code in Table 1. Next, the black run included in this pair run is Table 3
Encode using the code shown below. In this example, although the length of the black run is 2, it is encoded as "'io". The second pair run that appears is 1 white and 1 black, so the run length 2 of this pair run is ``011'' using the MH code in Table 1.
In this case, since the run length of the pair run is 2, it is uniquely defined as 1 white and 1 black, so the black run included in the pair run is not encoded.

5- 4- White 1 as in the conventional method. If each black 1 run is encoded using the MH code in Table 1, it will be "000111"'.

The code becomes "010" and requires 9 bits, but according to the present invention, only 4 bits are required, which is a factor in improving the encoding efficiency. The run length of the third pair run is 9,
Of these, black's run length is 3, so 'JO100'
The run length of the fourth pair of runs is 7, and the run length of black is 6, so it is encoded as "'1111"1.IIQQ11"'. Similarly, the run length of the fifth pair run is 1
3 and black's run length is 3, so "00001"
1″l, 11 IQ I+.

Next, the effectiveness of the present invention will be described. In the present invention, when the run length of the white run is W1 and the run length of the black run is B, and the code word length is represented by [ ], the MH shown in Tables 1 and 2 is used.
In the method, the codeword length of the run length W of the white run [
W] and the codeword length CB of the run length B of the black run) The codeword length CW of the run length (W 1 B) of the diamond and pair runs
By focusing on the relationship [W] + (BE> (W0B) between The information of the run length B of the black run included in the pair run length (W1B) is added to the minimum code word length while referring to the length (W1B) of the black run in this case. The codeword length of run length B is [
B], and (W) + CB) > [W
10B) 11B1m is created to improve the encoding efficiency. Therefore, the code word Nagamasa Bto indicating the run length B of the black run is important. Table 3 shows an example of the code word no for the run length of this black run. Table 3 shows the codes for pair run run lengths 2 to J1, and 12 or more is an example of using the M) (method code). Using the codes in Table 3, encoding is performed based on the principle described above. Table 4 shows a comparison of the code word length (required number of bits) with the conventional MH method.
] +[It shows that there is a relationship of B3.

According to the results of Nomura/Yon using CCITT's facsimile test document, most of the run lengths in Bear Run Table 3 and Table 4 occur between 2 and 11, and even when using 3, the encoding efficiency is large. can be expected to improve.

Furthermore, in 3, it is assumed that the probability of occurrence of black runs is higher from the shortest run length, but in actual image signals, the probability of occurrence is biased, so if this is taken into account, efficiency can be further increased. .

For example, if we focus on the run length 4 of the pair run, the possible run lengths of the black run among the run lengths 4 of the pair run are 1, 2, and 3. In Table 3, the smallest sign is given to black run 1, but black run 1.2.
Efficiency can be improved by assigning the smallest code to the run with the highest probability of occurrence among the three. The same thing can be said about the run lengths of other pair runs in Table 3.

In addition, in the present invention, for all run lengths in the range shown in Table 11 and Table 2, CW)+[B]>(W+B)+(
[:B3 relationship cannot be maintained. Also in Table 4, when the run length of the pair run is 8 or more, the effect becomes weaker. In this case, it is conceivable to apply the codes shown in Tables 11 and 2, or to adaptively use the conventional MI (method).

The present invention will be explained in detail below.

FIG. 2 shows an embodiment of an encoding circuit using this method. 1 is an input terminal, 2 is an output terminal, 10 is a memory having a capacity to store information for one line, 21 to 26 are AND gate circuits (some of which include a negative circuit on the input side), and 31 to 32 are delay circuits. , 41 to 44 are counters, 50 is an adder, 61 to 44 are counters, 50 is an adder, and 61 to 44 are counters;
63 is a Korg, and 70 is a signal synthesis circuit (OR circuit).

The facsimile signal is input from input terminal 1 and memory 1
It is temporarily stored at 0. The fufunmiri signal accumulated in the memo IJIO is directly applied to the gate circuits 21-24. Furthermore, the facsimile signal delayed by one bit in the delay circuit 31 is also applied to the gate circuits 21-24. The gate circuit 21 outputs an output pulse when both of the two input powers are 0 (white), and the number of pulses is counted by the counter 41. The gate circuit 22 outputs an output pulse when the signal changes from white to black, thereby stopping the color/color 41 counting. The count value of the counter 41 corresponds to the run length of the white run. On the other hand, when the gate circuit 24 is 1 (black), it outputs an output pulse.
The number of pulses is counted by a counter 42. The gate circuit 23 outputs an output pulse when the signal changes from black to white, causing the counter 42 to stop counting from this point K. The count value of the counter 42 corresponds to the length of the black run. The contents of counters 41 and 42 are added in adder 50. This value corresponds to the run length of the pair run.

The value of the adder 50 is encoded by the KOG 61, applied to the signal synthesis circuit (OR circuit), and transmitted to the output terminal 2.

Further, the count value of the counter 42 is calculated by the adder 50 in the Korg 62.
is encoded by referring to the value of . The counters 41 and 42 are reset when this encoding is completed. korg 6
The output of 2 is transmitted to input terminal 2 via a signal synthesis circuit.

In the above explanation, the run length of the pair run is Korg 61.
Although encoding was performed without referring to other values, encoding can be performed by referring to the number of unencoded pixels in one line. In the MH coding system shown in Table 1, codes are conveniently assigned to 64 types of run lengths, but for example, the run lengths of all pair runs that appear when the number of remaining pixels is 16 or less can be expressed with a 4-bit code length. .

Similarly, if the number of remaining pixels is 8 or less, the code length is 3 bits,
When the number of remaining pixels is 4 or less, encoding can be performed with a code length of 2 bits, and the encoding efficiency can be further improved. This can be achieved by calculating the number of remaining pixels with the counter 44 shown as block 1 in FIG. 2, and by having the Cog 61 refer to this value.

In addition, a normal document has a large margin on the right side, resulting in a relatively long white run. Encoding efficiency can be improved by first encoding this and then performing pair run/length from the beginning, but this can be achieved by adding block 2 as shown in FIG. That is, the contents of the memory 10 are first read from the rear side and are counted directly and via a delay circuit in addition to the games (25, 26), white runs by the counter 43, and encoded by the cog 63. After that,
13- Execute Alain's run length encoding as described above.

FIG. 3 shows an embodiment of a decoding circuit for a code string encoded by the method of the present invention. 101 is an input terminal, 102 is an output terminal, 111 to 113 are memories, 121 to 123 are gates, 131 to 133 are decoders, 140 is a subtracter, 15
0 is a counter.

The encoded facsimile signal for one line is stored in the memory 111 via the input terminal 101.

Initially, the gate 121 is open and the memory 111 to 1
The signal for the pair run is sent to the decoder 13 via the gate 121.
1. When the decoding of the pair run is completed by the decoder 131, the gate 121 is closed and the gate 1
22 opens. As a result, one run-length signal is read out from the memory 111 to the decoder 132 via the gate 122. The decoder 132 refers to the value of the decoder 131 and decodes the one run length. When decoding by decoder 132 is completed, gate 122 is closed and gate 121 is opened. A subtracter 140 subtracts the value of decoder 1132 from the value of decoder 131 to calculate the number of pixels corresponding to the white run length. First, the number of pixels in the white run "0"' of the subtracter 140 is added to the line memo 1J112, and then the number of pixels in the black run "1" of the decoder 132 is added to restore the original pixel string. The above decoding operation is repeated by opening and closing the gates 121 and 122, and the white run and black run are sequentially restored.

As described in the embodiment of the encoding circuit, when the run length of a pair run is encoded by referring to the number of unencoded pixels in one line, the value of the counter 150 in the decoder 131 hublock 1 Refer to and decrypt. Here, the counter 150 is a counter that initially stores the number of pixels of l line, and subtracts the value each time the run length of each pair run is decoded by the decoder 131.

Further, if the run at the right end of each line is first encoded, and then the run-length encoding of the first pair run is performed, the run is decoded by adding block 2 in FIG. 3. That is, first, only the gate 123 is opened, and the signal corresponding to the rightmost run is read out from the memory 111 via the gate 123 and decoded by the decoder 133. This value is stored in the memory 113 and added to the line memory 112 at the end of the line (2). When the decoding by the decoder 133 is completed, the gate 123 is closed and the gate 123 is closed.
121 opens. The decoding of each pair run described above is then executed.

In the above explanation, the codes shown in Tables 11 and 2 are used as codes that indicate the run length of pair runs, and Table 3 is used as codes that indicate the run length of black runs, but the method of the present invention is limited to these codes. Of course, other codes can be applied instead.

In addition, the present invention is applied to pixels (referred to as basic pixels) from which fan/millimeter signals are extracted every N pixels (referred to as basic pixels) in the "One-dimensional coding method for Facun-millimeter signals" filed on August 19, 1981, and the basic pixel Pixels located in between (referred to as supplementary pixels) can also be encoded by referring to neighboring pixels that have already been encoded.

The encoding effect of the present invention has already been described, but the present invention also has the effect of keeping the influence of transmission errors within a local range and preventing them from spreading to other areas. For example, in FIG. 1, even if the signal 110' indicating a black run is received as +111 due to a transmission error, the length of the black run is only recognized to be 3 (the length of the white run is 2), and the length of the black run is 2.

There is no effect on Black Run.

[Brief explanation of the drawing]

FIG. 1 is a time chart for explaining the principle of encoding according to the present invention, FIG. 2 is a block diagram showing an embodiment of the present invention,
FIG. 3 is a diagram showing an example of a circuit for decoding a code string encoded according to the present invention. Patent applicant International Telegraph and Telephone Corporation Representative Inuzuka 1 person from outside the university 17-

Claims (1)

[Claims] In a one-dimensional encoding method for two electric signals such as facsimile signals, each pair of runs is selected so that the combination of adjacent white runs and black runs of the two electric signals sequentially form a pair, and A pair-run encoding method characterized by encoding the length of the sum of a run and a black run and, if necessary, the length of either a white run or a black run constituting each pair.