JPS5915229B2 - encoding device - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to an encoding device that encodes output symbols of an information source in which the probabilities of appearance of binary symbols are close to each other.

Conventionally, the code shown in Figure 1 has been known as a practical code that effectively encodes information sources with probabilities of occurrence of binary symbols that are close to each other. Considering the time of the information source, the most frequently occurring symbols (゛o
There was a problem in that compression could not be performed if the probability of appearance of a ``symbol'' was less than about 0.62.

The present invention has been made in view of this point, and when the probability of occurrence of a symbol with a high frequency of occurrence (dominant symbol) is P, select n that satisfies pn+''>(1-p)n, and select n from the information source. Divide the output symbols into patterns consisting only of (n+1)-bit dominant symbols, patterns consisting only of n-bit inferior symbols, and patterns containing both dominant and recessive symbols, A pattern consisting only of the above n-bit recessive symbols is defined as (n
+1) By converting a pattern consisting of both symbols into a bit codeword, no matter how close the probability of appearance of the dominant symbol is to 0.5, as long as the symbol appearance process follows a memoryless process. The present invention provides an encoding device that can always perform encoding compression.

FIG. 2 shows an example of a code format when n=2 in the present invention, and FIG. 3 shows the correspondence between a binary symbol sequence, a reporting symbol sequence, and a coded sequence.

Now, if the symbol ``o'' is the dominant symbol, the third
The binary output symbol sequence in figure a is
If ``, then ``1'' will appear next, or b total 3
If the first symbol is ゝ 1 '', it is divided according to whether ゝ o '' appears next or if ゝ bi appears two times in total. Then, the reporting symbol string in Figure 3b is obtained. obtained,
When the code shown in FIG. 2 is assigned to this, the code sequence shown in FIG. 3c is obtained.

In the code word example in Figure 2, only the ゞo'' symbol, (n+1)
For each pattern, the code word is a sequence of n 1'' symbols, and only for the n symbols (T
Since the sequence of O'' symbols (n+1) is used as a code word, and the original symbol sequence \ is used as the code word for other patterns, the construction of the encoder is extremely easy.

Furthermore, since decoding is possible on the receiving side using exactly the same algorithm as on the transmitting side, the decoder may be the same as the encoder. If the target information source outputs symbols according to a memoryless process, select n that satisfies ゞthe probability of appearance of the o'' symbol as P(〉↓), and the probability of appearance of the ゞ1'' symbol as 1-P. Encoding compression is always possible.

That is, by using this code, it is possible to extremely efficiently code and transmit information sources in which the probabilities of appearance of binary symbols are close to each other. FIG. 4 shows the encoding efficiency of a memoryless information source, and the shaded area shows the case where encoding and compression cannot be performed.

Incidentally, FIG. 5 is an example of a block diagram of the encoding part of the present invention, and the symbol sequence to be encoded is guided to the code converter 100.

101 is the first symbol memory, the first symbol is ゞo''
The maximum count is output to the symbol counter 102 depending on the input power ~ 1'', and the symbol to be encoded is sent to the code converter 1.
At the same time as being led to 00, it is also led to the symbol counter 102 and the exclusive OR circuit 103.

The exclusive OR circuit 103 performs an exclusive OR of the first symbol and the currently read symbol, and if a symbol different from the first symbol appears, it is determined that this is a break in the series, that is, the occurrence of a notification symbol. Further, the symbol counter 102 counts the occurrence of the same symbol as the first symbol, and when the maximum count is reached, it is determined that it is a break in the series, that is, the occurrence of a reporting symbol. In this way, the first symbol memory 101. The symbol counter 102 and the exclusive OR circuit 103 constitute a dividing means that divides the output symbols from the information source into predetermined patterns. When the code converter 100 (code converter) is a notification symbol based on the judgment output of the exclusive OR circuit 103,
When the original binary symbol is output as a \ code and the notification symbol is determined by the judgment output of the symbol counter 102, when it consists of ゞo'' symbols, when it consists of n ゞ 1'' symbols and ゞ 1'' symbols, is (n+1)
The decoder is converted into ゞo'' symbols and outputted as a code.The decoder may be the same as the encoder, as already mentioned.

The present embodiment described above specifically proposes a practical and highly efficient method for setting notification symbols and a method for creating code words.

As described above, according to the present invention, when the probability of occurrence of a dominant symbol is P, n is selected that satisfies P1+1>(1-P)0, and the output symbol from the information source is changed to the (n+1)-bit dominant symbol. A pattern consisting only of n-bit dominant symbols, a pattern consisting only of n-bit recessive symbols, and a pattern including both dominant and recessive symbols. Since a pattern consisting only of bit-inferior symbols is converted into an (n+1)-bit code word, and a pattern consisting of both symbols is converted into a code word of the same bit, a proximate information source for the appearance probability of a binary symbol is used. Highly efficient encoding can be realized.

[Brief explanation of the drawing]

FIG. 1 is a configuration diagram showing a conventionally known code format.
FIG. 2 is a block diagram showing an example of a code with n=2 as an embodiment according to the present invention, and FIG. Second
FIG. 4 is an explanatory diagram showing the encoding efficiency when the code according to the present invention is applied to a memoryless information source, and FIG. 5 is a block diagram of the encoding device according to the present invention. .

Claims (1)

[Claims] 1. A code that gives a code word to an output symbol from an information source in which the probability of occurrence P of a frequently occurring dominant symbol is close to the occurrence probability (1-P) of a less frequently occurring symbol. In the conversion device, the above output symbols are outputted at the time when an inferior symbol appears when the first symbol is a dominant symbol, or when dominant symbols are consecutively (n+1) (n is P^n^
+＾1>(1-P)＾Positive integer that satisfies n) Separate when symbols appear, and when the first symbol is an inferior symbol, when a dominant symbol appears or when n inferior symbols appear consecutively. When the separated pattern consists of only dominant symbols, there is a
When a bit codeword is given and it consists only of inferior symbols, (
(n+1) bit code word, and code converting means for giving a bit code word having the same length as the pattern when it consists of both symbols. 2. The code conversion means gives a code word in which n bits of consecutive less-favorable symbols are provided when the divided pattern consists only of dominant symbols, and a code word in which n bits of consecutive dominant symbols are given when the pattern consists only of inferior symbols. 2. The encoding device according to claim 1, wherein a code word is given, and when the symbol is composed of both symbols, the original signal is given as it is as a code word.