JPS6139770B2 - - Google Patents

Description

[Detailed description of the invention]

The present invention relates to a method for encoding a multivalued information source. When the number of types of information symbols output from a multilevel information source and the appearance probability of each symbol are known, symbols with a high probability of appearance are assigned codes with the simplest form possible to comprehensively transmit information. It is necessary to improve efficiency, and such an encoding method is required, for example, when document and image information is encoded and transmitted. A highly efficient code assignment method represented by Huffman encoding is known as a conventional encoding method, but this method requires an extremely complicated encoding device. Moreover, it has the disadvantage that there is no guarantee regarding encoding efficiency. The object of the present invention is to eliminate the above-mentioned drawbacks of conventional encoding methods and to provide an encoding method that is highly efficient, practical, and can be implemented by a simple device. Therefore, in this invention, a binary series is created from the output of a multivalued information source, and
DESCRIPTION OF THE PREFERRED EMBODIMENTS Embodiments of the present invention will be described below with reference to the drawings, which perform highly efficient encoding using knowledge regarding encoding of original sequences. FIG. 1 is an explanatory diagram for explaining the method of the present invention, and FIG. _1a shows an example of a symbol sequence to be encoded. This is an example in which the appearance probability of each symbol is p _1a1 = _0.1 ; p _1a2 = 0.2; p _1a3 = 0.7 (1 ₎ . In this invention, in the first step, a sequence whose appearance probability is 1/2 or less is selected from among the sequences shown in Figure 1a. In other words, select symbols in which the number of elements in the series shown in Figure 1a is less than or equal to 1/2 of the total number of elements (10 in the example shown). Symbols that correspond to this include a ₁ and a ₂ , but let us assume that a ₁ is selected. In this case a ₂ may be chosen, provided that the order of selection is known by both the sender and the receiver. That is, as long as a common rule (for example, alphabetical order, order of low signal level, etc.) is used, a common symbol is selected for both transmission and reception, making decoding possible. Therefore, when a ₁ is selected, "1" is associated with a ₁ and "0" is associated with other symbols, that is, a ₂ and a ₃ , thereby creating a sequence T ₁ . What is shown in FIG. 1b is series _T1 . Next, p _2a2 = p _1a2 /1-p _1a1 ; p _2a3 = p _1a3 /
1-p _1a1 ...(2) to create p _2a2 and p _2a3 respectively, and p _2a2 and p _2a3
Choose 1/2 or less of them. In the above numerical example, p _2a2 = 2/9, p _2a3 = 7/9, and p _2a2 is less than 1/2. In other words, symbols having a number less than 1/2 of the total number of “0” codes in sequence T ₁
a means to choose ₂ . When a ₂ is selected, a series T ₂ is created by associating "1" with a ₂ and "0" with another symbol, that is, a ₃ . What is shown in FIG. 1c is series _T2 . Here, as shown in FIG. 1, symbols converted to "1" in series T ₁ are ignored in series T ₂ and subsequent series. This is indicated by a "-" symbol in FIG. 1c; in reality, there is no "-" symbol, and the signal "001000001" shifted to the left becomes the sequence _T2 . Knowing that a ₁ was selected in FIG. 1b and a ₂ was selected in FIG. 1c, the information in FIG. 1a can be represented by FIGS. 1b and 1c. Here, when reproducing Figure 1 a from Figures 1 b and c, it is known that by sequentially reproducing from series T ₁ , for example, the ignored symbol indicated by "-" is missing in series T ₂ . It can be reproduced. In other words, since sequence T ₁ is encoded and transmitted before sequence T ₂ , sequence T ₁ is decoded before sequence T ₂ on the receiving side, and “0” is written on sequence T ₁ .
This is because it can be seen that the signal of sequence T ₂ is sent only for the part shown in FIG. The amount of information in Figure 1 a is H ₀ and the amount of information in Figure 1 b is
H ₁ , and if the amount of information in Figure 1 c is H ₂ , then H ₀ =-{0.7log ₂ 0.7+0.2log ₂ 0.2 +0.1log ₂ 0.1}×10 = 11.5678...(3) H ₁ =-{0.1log ₂ 0.1+0.9log ₂ 0.9}×10 =4.6900 …(4) H ₂ =-{0.2/0.9log ₂ (0.2/0.9) +0.7/0.9log ₂ (0.7 /0.9)}×9 = 6.8778 ...(5) and H ₀ = H ₁ + H ₂ ...(6) Therefore, the coding efficiency in Figure 1a is equal to the coding efficiency in Figures 1b and c. It will then be given to you.
Figure 1 shows the simplest case where r=3, but no matter what value r is, the above steps are repeated to obtain the binary sequences T ₁ , T ₂ ,
...It is clear that T _o can be made.
If the i-th symbol of the r-value information source is a _i and its appearance probability is p _i , the amount of information per symbol of the original sequence G ₀ is

[Formula], and the amount of information G _i per symbol of the i-th binary sequence T _i is as follows. Here, H _i =−xlog ₂ x−(1−x)log ₂ (1−
x),

[Formula]. The total amount of information G _s of (r-1) binary sequences is

[Formula] becomes G ₀ = G _s . Therefore, this means that the information source of the r value has been converted into a binary sequence with the same amount of information. In the above example of r = 3, a ₁ is selected as the first converted symbol, a ₂ is selected as the second, and the criterion is that the probability of appearance in the series of Figure 1 a is 1. /2
The following are applicable. This selection is made in order to improve the efficiency of binary encoding, which will be described later. If only the above-mentioned conversion to a binary sequence having an equal amount of information is required, it is only necessary to decide in advance the order in which symbols are selected. Furthermore, the binary sequences obtained as shown in FIGS. 1b and 1c are collectively encoded into sequences T ₁ and T ₂ and transmitted sequentially. At this time, the symbol "-" in FIG. 1c is omitted, and the sequence is encoded as consisting only of "0" and "1". For example, the number of pixels of the image to be transmitted is determined in advance, so the break between sequence T ₁ and sequence T ₂ , which are sequentially encoded and transmitted, occurs when the receiving side decodes sequence T ₁ and reaches a predetermined number of pixels. The break with the next series T ₂ can be determined. Also, series
The break between T ₂ and subsequent sequences can be determined by counting the number of “0” signals in sequence T ₁ when decoding sequence T ₁ .
Since the number of pixels in series T ₂ is known, it is possible to determine the break with subsequent series. Subsequent breaks in the series will be determined in the same manner. Now, the first
The series T ₁ and series T ₂ in the figure can be encoded using the code format shown in FIG. 2, for example. The encoding format shown in Figure 2 is publicly known, such as in ``Coding Compression of Binary Information Sources'' in the Journal of the Institute of Electronics and Communication Engineers (Trans・IECE'77/12 Vol. 60-A, No. 12). , M consecutive binary symbols "0...0" are converted into codewords "0" with code length 1, binary symbols "1" are converted into codewords "10...0" with code length m+1, Binary symbol “0” with i consecutive “0”s
01” is a code word “1x…x” with code length m+1; This means converting the code word "11...1" into the code word "11...1".If you use this code format and select the order M that satisfies the condition of equation (7) shown below, the signal appearance form is arbitrary, and 2. A coding efficiency of at least about 90% is guaranteed for the amount of information determined by the probability of appearance of value symbols.M/M+1≦(1-C)<2M/2M+1...(7) However, M=2 ^m , C is the probability of appearance of “1” symbol. For example, in the example in Figure 1, for sequence T ₁ , C
= 1/10, M = 8, and for series T ₂ , C =
Since it is 2/9, M=2. Therefore, for series T ₁ , M=8, m=3
The table shown in FIG. 2 is used for encoding. FIG. 4 shows an example of coding for M=8 and m=3 in FIG. 2, and FIG. 5 shows an example in which the code words of FIG. 4 are given to sequence _T1 . FIG. 3 is a block diagram showing an example of a circuit that automatically executes the method of the present invention, in which 108 is an input terminal for symbols from a multilevel information source, and 100 is a terminal 1.
A storage device for storing information input from 08, 1
02 is a second symbol counter that counts the total number r of symbols input from the terminal 108. 1
Some gates are provided between 08 and 100 and between 108 and 102, but such gates are well known in the art and are therefore omitted from FIG. Other parts omitted in FIG. 3 will be explained in the main text if necessary. Reference numeral 101 is a first symbol counter that counts the number of arbitrarily selected symbols, and a circuit for automatically performing this selection is not shown in the drawings. 103 is a shift register into which the contents of the first symbol counter 101 are input. 104 is a comparison circuit, 105 is a binary memory, 106 is an order determining circuit, 107 is an encoder, and 109 is a code output terminal. Assuming that the selection of symbol types is performed cyclically in a predetermined order, the operation of FIG. 3 will be explained with respect to the example shown in FIG. 1.
The information shown in Figure 1a is input to 0, and at the same time the information shown in Figure 1a is input to
The symbol counter 102 counts the number of symbols, and in the example of FIG. 1, the number 10 is set. It shows the numerical value 1 counted by the first counter 101 where symbol _a1 was selected first. This is input to the shift register 103, shifted by 1 bit to become 2, and compared with the output of the second symbol counter 102 in the comparator circuit 104. 2<10, therefore, a ₁ of the storage device 100 is set as "1" and a ₂ and a ₃ are set as 0 and input into the binary memory 105. The contents of the binary memory 105 are as shown in FIG. 1b. Any conventionally known circuit may be used as the circuit for obtaining the output code from the contents of the binary memory 105, so a detailed explanation will be omitted.
The value of M in Equation (7) is determined by counting how many times the contents of the symbol counter 102 must be shifted to exceed the contents of the second symbol counter 102 while shifting the shift register 103. For example, if a ₁ is 6 in Figure 1 a
In the first comparison,
12 > 10, in this case choose the next a ₂ . When the encoding of _T1 is completed, the first symbol counter 1 is converted from the contents of the second symbol counter 102.
01 and the second symbol counter 1
After setting the contents of 02 to 10-1=9, _a2 is counted and input to the first symbol counter 101. The content of the first symbol counter 101 becomes 2, which is shifted by the shift register 103 to become 4, but 4<9, so a2 of the storage device 100 is "1" and _a3 is " ₀ ". ” as binary memory 1
05, the contents of the binary memory 105 will be as shown in FIG. 1c. As is clear from the above explanation, according to the method of the present invention, encoding can be performed using a simple circuit, and in particular, it is possible to use a code that can guarantee encoding efficiency of 90% or more. There is.

[Brief explanation of the drawing]

FIG. 1 is an explanatory diagram for explaining the method of this invention, FIG. 2 is a diagram showing an example of an encoding format, FIG. 3 is a block diagram showing an example of a circuit for implementing the method of this invention, and FIG. The figure is M=8, m=3 in Fig. 2.
Figure 5 shows an example of encoding the sequence
5 is a diagram showing an example in which the code word of FIG. 4 is given to T _{1. FIG} . In the figure, 100 is a storage device, 101 is a first
102 is a second symbol counter, 103 is a shift register, and 104 is a comparison circuit.

Claims (1)

[Claims] 1. In an encoding method for determining a code to be assigned to information for which the number of types of symbols and the appearance probability of each symbol are known, (a) each symbol of the above information source is Select one type of symbol whose number is less than or equal to 1/2 of the total number of elements from the set of symbols included in each probability of appearance, and associate "1" with that symbol and assign "1" to the other symbols. (b) A step of creating a series T ₁ in which "0" is associated with each other in the series T ₁ ; Steps of selecting a type of symbol and creating a series T ₂ in which "1" corresponds to that symbol and "0" corresponds to other symbols, and (c) repeating the step (b) above, Select one type of symbol whose number is less than or equal to 1/2 of the total number of elements from the set of symbols that correspond to “0” in the sequence T _o-1 obtained in the step, and Create a series T _o that corresponds to “1” and other symbols to “0”,
a step of repeating until n becomes the value obtained by subtracting 1 from the number of types of symbols r, and (d) each sequence obtained in this way.
T ₁ , T ₂ ,...T _r-1 for each series,
1. An encoding method comprising the step of calculating the probability of occurrence of "1" included in the binary sequence and performing code conversion to remove redundancy of the binary sequence.