JPH0936749A - Encoding / decoding apparatus and encoding method used therefor - Google Patents

Abstract

(57) [Abstract] [Purpose] In a coding / decoding apparatus, a method capable of performing coding / decoding by a simple algorithm without impairing the good compression efficiency of a non-block code,
A complicated device is not required, and encoding / decoding with a high operation speed can be performed. [Configuration] When encoding, the occurrence probability of a symbol of an input signal is predicted, the symbol is divided into a dominant symbol and a recessive symbol, and the occurrence prediction probability of the recessive symbol is
Expressed by 1 / (2 ** R, R is a positive integer) to the R-th power of 2, when a recessive symbol is input, the code register is shifted by R bits to the upper position. When the dominant symbol is input, the lower R of the code register is
Increments each 0 to give one recessive symbol and 0
Encoding is performed on the code register with one or more dominant symbols as a set.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a coding / decoding device and a coding method used for the same, and is a device capable of efficiently compressing enormous data such as image information and audio information. Therefore, the present invention relates to an encoding / decoding device capable of performing the compression algorithm easily and at high speed, and an encoding method used for the same.

[0002]

2. Description of the Related Art Conventionally, MH (Modified Huffman, Mo
An encoding method called dified Huffman) or MR (Modified Read) is widely used as an image encoding method for facsimiles and the like.
In these methods, a code word (Huffman Code) corresponding to a symbol to be encoded is determined in advance, and the actually generated symbol is replaced with the corresponding code word. This is one of the methods classified into “Block Code”. For example, ITU-T Recommendation T.4 defines the details of the MH system, and many devices based on this system have been developed in addition to facsimiles.

On the other hand, there is a method classified into "non-block code", and code words are generated while sequentially predicting the occurrence probability of symbols. Regarding this method, there are the following documents and explanations.

Published by McGRAW-HILL (1963), N. Abramso
n, "INFORMATION THEORY AND CODING", pages 61 to 62, the Elias code (Elias Co
The method called de) is described.

A technique entitled "Outline of Color Still Image Coding Standardization Method (JPEG) (Part 2: Arithmetic Code)" on pages 113 to 120 of Journal of Image Electronics Engineers of Japan, Volume 20, Issue 2 (1991). The explanation is described.

In both cases, basically, the division of the [0,1) section (including 0 and not 1) is repeated corresponding to the ratio of the occurrence probabilities of the symbols to be encoded, and the final The numerical value indicating the point on the [0,1) section divided into is used as a code word.

[0007]

The block code widely used as described above has a feature that the device configuration is easy, but it is said that the block code is inferior to the non-block code in terms of coding efficiency. .

On the other hand, the non-block code is superior in coding efficiency to the block code, but has the following problems.

(1) High calculation accuracy is required Since the occurrence probabilities of a plurality of symbols are multiplied, high calculation accuracy below the decimal point may be required in some cases. Therefore, the number of bits required for the register and the memory becomes large, and the operation time becomes long.

(2) Complicated signal processing procedure in which many condition judgments are made The method developed to solve the above-mentioned problem of calculation accuracy is the method referred to as an example of the prior art. They are,
The calculation required for the generated codeword itself is limited to simple addition by setting a new conversion value.

However, although the calculation itself is simplified, many condition judgments are made and the number of variables is increased to introduce the converted value, so that the signal processing procedure becomes more complicated.

(3) Non-uniform Decoding / Generation Rate It is pointed out that the non-uniformity of the decoding / generation rate, which is called latency (latency of decoded output).

The present invention has been made to solve the above-mentioned problems, and an object thereof is to compress a data into a code, and in a coding / decoding device for decoding the same, a non-block code. It is a method that can perform encoding and decoding with a simple algorithm without compromising the good compression efficiency of, and does not require a complicated device.
An object of the present invention is to provide an encoding / decoding device that performs encoding / decoding with high calculation speed.

[0014]

In order to achieve the above object, the first configuration of the invention relating to the coding / decoding apparatus of the present invention is to perform coding of an input signal and decoding which is the reverse process. In the encoding / decoding device for performing, it has a means for predicting the probability of occurrence of symbols, a means for determining the symbols of the input signal, a code register, and a shift control means, and when performing the encoding, the occurrence probability is By predicting the occurrence probability of the symbol of the input signal by the predicting means, by the means for discriminating the symbol of the input signal, of the predicted occurrence probability of the symbol obtained by the means for predicting the occurrence probability, the larger one of The symbol with the predicted occurrence probability is determined as the dominant symbol, and the symbol with the smaller predicted occurrence probability is determined as the recessive symbol, and the occurrence probability of the recessive symbol is divided by 2 R 1/2 ** R, R is a positive integer), and when the recessive symbol is input, the shift control means shifts the R bit to the upper bit of the one recessive symbol. And moreover,
It is configured such that R zeros are inserted in the lower order.

In order to achieve the above object, the second structure of the invention relating to the coding / decoding apparatus of the present invention is a coding / decoding for performing coding which is a process of coding an input signal and vice versa. The encoding device has means for predicting the occurrence probability of symbols, means for discriminating the symbols of the input signal, a code register, and a counter, and when encoding, the means for predicting the occurrence probability inputs The symbol having the larger predicted occurrence probability among the predicted occurrence probabilities of the symbols obtained by the means for predicting the occurrence probability by the means for predicting the occurrence probability of the signal symbol and determining the symbol of the input signal Is the dominant symbol and the symbol with the smaller predicted occurrence probability is the recessive symbol, and the occurrence prediction probability of the recessive symbol is divided by 2 R
Expressed by 1 (1/2 ** R, R is a positive integer), when the dominant symbol is input, the counter counts the number of consecutive occurrences of the dominant symbol, and only the counted number The code register is incremented.

Another structure relating to the encoding / decoding device of the present invention, which is derived from the first structure and the second structure, has the functions of the encoding / decoding device of the first structure and the second structure. In the encoding / decoding device that has, when performing encoding,
When the recessive symbol is input, the first code word composed of R 0s generated on the code register as described above and when the dominant symbol is input,
As described above, the second codeword generated by incrementing the code register is generated, and the first codeword and the second codeword are combined to generate a code. It was done like this.

Another structure of the invention relating to the coding / decoding apparatus of the present invention is that the probability of occurrence of a symbol is determined in a coding / decoding apparatus that performs coding which is the reverse process of coding an input signal. Predicting means, means for discriminating the symbols of the input signal, code register, shift control means,
A counter and predicting the occurrence probability of the symbol of the input signal by means of predicting the occurrence probability when performing encoding, and predicting the occurrence probability by means of determining the symbol of the input signal Among the predicted occurrence probabilities of the symbols obtained by the means, the symbol having the larger predicted occurrence probability is determined as the dominant symbol, and the symbol having the smaller predicted occurrence probability is determined as the recessive symbol,
The probability of occurrence of a recessive symbol is calculated by dividing the R power of 2 by 1 (1/2 **
R and R are represented by positive integers, and when the recessive symbol is input, the shift control means causes the shift register to move the code register to the upper R for one recessive symbol.
When the number of consecutive occurrences of the dominant symbol is counted by the counter when the dominant symbol is input by bit-shifting and by inserting R zeros in the lower order, the counter is counted by the counted number. Incrementing the lower R 0s of the code register and thus encoding the input signal as a set of one recessive symbol and zero or more dominant symbols on the code register. It was done.

More specifically, in the above coding / decoding apparatus, the number of consecutive occurrences of the input dominant symbol is N
, And the probability of occurrence of recessive symbols is represented by 1 of 2 R (1/2 ** R, R is a positive integer), (2 ** R-1 )> N, the R 0s on the code register generated as the codeword of the recessive symbol are incremented by N, and if (2 ** R-1) ≦ N, the recessive symbol R 0s on the code register generated as code words
With all 1s to generate a code word meaning a = N- (2 ** R-1), combine these, and combine the code word of the recessive symbol and the code word of the dominant symbol. It is meant to be a word.

More specifically, in the above coding / decoding apparatus, the code word that means a = N- (2 ** R-1) is composed of a continuous block consisting of each R, and the last Except for blocks, all bits are made up of 1.

Further, regarding the device configuration in detail, in the above-mentioned coding / decoding device, the code register has a processor and a memory, and the code register is a register in the processor. The procedure of encoding on this register is executed by the processor according to the program stored in the memory.

Another configuration according to the encoding / decoding apparatus of the present invention is, in the encoding / decoding apparatus, a set of one recessive symbol and zero or more dominant symbols as described above. As a table, a code word generated in the lower order on the code register is created in advance, and one recessive symbol, zero or more dominant symbols, and the code word corresponding to the one recessive symbol are set as one item. With this table, one input recessive symbol and zero or more dominant symbols are set as a set, and corresponding code words are searched and encoded.

Further, another configuration to which the coding / decoding apparatus of the present invention is applied is a case where the input signal is composed of symbols which can take a plurality of states in the above coding / decoding apparatus. Based on the predicted occurrence probability predicted by the occurrence probability means, divide the possible states of those symbols into two groups, the dominant group and the inferior group, when the state of the recessive group is input,
When the recessive symbol described above is input, and when the state of the dominant group is input, the process is performed as when the dominant symbol described above is input, and as described above. The first code word and the second code word are combined into a set of code words, and a code word that identifies the state of the symbol in the group to which the symbol belongs is a block code. A combination of a set of code words created by using the first code word and the second code word, and a code word specifying the state of the symbol in the group to which the symbol belongs. Is a code word in a state that this input signal can take.

Another configuration of the apparatus is a case where the input signal has a plurality of signal characteristics in the encoding / decoding apparatus, and a plurality of occurrence probability predicting means corresponding to the respective signal characteristics are provided. It was prepared.

Next, in order to achieve the above-mentioned object, the structure of the invention relating to the encoding method of the present invention is the encoding method for performing the encoding of the input signal and the decoding which is the reverse process. Has a means for predicting the probability of occurrence of a symbol, a means for determining the symbol of an input signal, a code register, a shift control means, and a counter, and the prediction of the symbol obtained by the means for predicting the probability of occurrence. Among the occurrence probabilities, the symbol having the larger predicted occurrence probability is the dominant symbol, the symbol having the smaller predicted occurrence probability is the recessive symbol, and the predicted occurrence probability of the symbol obtained by the means for predicting the occurrence probability of the symbol. Where the larger symbol is the dominant symbol and the smaller symbol is the recessive symbol, the probability of occurrence of the recessive symbol is the R power of 2 Of 1 (1/2 ** R, R is a positive integer)
And (1) a procedure of predicting the occurrence probability of a symbol of an input signal by the means for predicting the occurrence probability,
(2) a step of discriminating the input signal into a dominant symbol and a recessive symbol by means for discriminating the symbol of the input signal, (3) a step of inputting the recessive symbol,
(4) For the one recessive symbol, the shift control means shifts the code register to the upper bit by R bits, and further, generates a first code word in which R number of 0's are inserted. (5) The procedure of inputting the dominant symbol, (6) The number of consecutive occurrences of the dominant symbol is counted by the counter, and only the counted number,
A step of incrementing the code register to generate a second code word; and (7) a step of synthesizing the first code word and the second code word, wherein (1) to (7) ) Is repeated in this order, and the input signal is generated as a set of one recessive symbol and zero or more dominant symbols as a set of code words.

In order to achieve the above object, another structure of the invention relating to the coding method of the present invention is a coding method for carrying out coding of an input signal and decoding which is the reverse process. The device has means for predicting the probability of occurrence of symbols, means for discriminating the symbols of the input signal, a code register, shift control means, and a counter, and the means for predicting the probability of occurrence of the symbols Of the predicted occurrence probabilities, the symbol having the larger predicted occurrence probability is the dominant symbol and the symbol having the smaller predicted occurrence probability is the recessive symbol, and the predicted occurrence probability of the symbol obtained by the means for predicting the occurrence probability of the symbol When the larger symbol is the dominant symbol and the smaller symbol is the recessive symbol, the occurrence probability of the recessive symbol is set to 2. 1 to the Rth power (1/2 ** R, R is a positive integer)
And (1) a procedure of predicting the occurrence probability of a symbol of an input signal by the means for predicting the occurrence probability,
(2) a step of discriminating the input signal into a dominant symbol and a recessive symbol by means for discriminating the symbol of the input signal, (3) a step of inputting the recessive symbol,
(4) ′ With respect to the one recessive symbol, the shift control means shifts the code register to the upper bit by R bits, and further inserts R zeros in the lower bit,
(5) A step of inputting the dominant symbol, (6) ′ A step of counting the number of consecutive occurrences of the dominant symbol by the counter, and incrementing the lower R pieces of the code register by the counted number. And repeating the steps (1) to (3), (4) ′, (5), and (6) ′ in this order, and inputting the input signal to one recessive symbol and zero or more dominant symbols. And as a set,
The encoding is performed on the code register.

More specifically, in the above encoding method,
The number of consecutive occurrences of the dominant symbol at the time of encoding is N, and the occurrence probability of recessive symbols is R of 2.
When expressed as a power of 1 (1/2 ** R, R is a positive integer), if (2 ** R-1)> N, it is generated as a codeword of a recessive symbol. Incrementing R 0s of the code register by N, and if (2 ** R-1) ≦ N, the lower R 0s of the code register generated as the code word of the recessive symbol are incremented. When all are 1, and a code word that means a = N- (2 ** R-1) is generated and the procedure for combining these is (O), (6), ( Follow the procedure in 7) to this procedure (O).
, Or (6) ′ described above is replaced by this procedure (O).

More specifically, the code word meaning a = N- (2 ** R-1) is composed of a continuous block consisting of R units, and all bits except for the last block. 1
It is made up of.

In order to achieve the above object, another aspect of the invention relating to the encoding method of the present invention is that the code word of the recessive symbol and the dominant symbol generated as described above in the encoding method. A codeword that is a combination of the codewords of
It is prepared in advance and is provided with a table in which one recessive symbol, zero or more dominant symbols, and corresponding codewords combined therewith are set as one item. When the procedure for searching the corresponding codeword is set as (T) with a set of recessive symbols and 0 or more dominant symbols, in the above-mentioned procedures (1) to (3) and (5), Repeat steps (1) to (3), (5), and (T) in this order,
It is designed to be encoded.

Another configuration to which the coding method of the present invention is applied is a case where the input signal is composed of symbols capable of assuming a plurality of states in the above coding method, and the prediction occurrence probability means is used. Based on the predicted occurrence probability of prediction, the possible states of those symbols are divided into two groups, a dominant group and an inferior group, and the symbol is a code word that identifies the state of the symbol in the group to which the block code is assigned. (B) is a procedure in which one recessive group and zero or more dominant groups are combined as a set, and a code word encoded on the code register and a symbol in the group to which the symbol belongs (C) the procedure for combining with the codeword that specifies the state of
Then, in the procedure of (1) to (6) described above, the dominant symbol is read as the dominant group and the recessive symbol is read as the recessive group, and the codeword of the recessive group and the codeword of the dominant group are read. Is performed to generate a code word, and then (B) and (C) are performed in this order, and a series of these processes are repeated to perform encoding.

[0030]

According to the present invention, when encoding, in the case of a recessive symbol, the code register is shifted by a predetermined number of bits, and in the case of a dominant symbol, the code register is incremented by the number of consecutive symbols. . In the case of decoding, the reverse operation is performed.

Therefore, a special device is not required for the encoding / decoding, and the encoding / decoding can be executed at high speed by only the basic arithmetic operation of the register. Moreover, since it is a non-block code that uses the prediction occurrence probability, it is a method with a higher data compression efficiency than a coding method based on a block code (for example, Huffman code). Moreover, the data of the information source can be losslessly encoded.

Further, unlike the conventional arithmetic code, latency does not occur at the time of decoding.

[0033]

Embodiments of the present invention will now be described with reference to FIGS.
8 will be described. [Basic Principle of the Present Invention] First, the basic principle of the encoding method in the encoding / decoding device according to the present invention will be described with reference to FIG. FIG. 1 is a basic principle diagram of an encoding method in an encoding / decoding device according to the present invention.

First, the occurrence probability of a symbol to be encoded is predicted (S101). This may be obtained by inputting a signal, or may be obtained by other statistical means.

Next, it is determined whether the input symbol is a dominant symbol or a recessive symbol (S10).
2).

If the symbol is a recessive symbol, the code register is shifted by a predetermined number of bits (S103). When the symbol is the dominant symbol, the number of consecutive occurrences is counted (S10
4) The code registers are incremented by that number (S105).

One set of the processing of the recessive symbol and the processing of the dominant symbol is a unit of coding. When the recessive symbol is next to the recessive symbol, the number of consecutive occurrences of the dominant symbol may be considered to be zero. Then, the code is output at an appropriate timing.

Hereinafter, this will be described in detail.

(I) Prediction of Occurrence Probability In general, in the coding method based on arithmetic code, the occurrence probability is predicted before coding, and the content of the code to be coded is determined accordingly. Also in the present invention, the occurrence probability of a sequence of one or more symbols is predicted by the same idea.

Now, the symbol to be encoded is Xi (i =
0,1), the superior symbol is X0, and the inferior symbol is X1.
And Here, the dominant symbol is a symbol having a high probability of appearing, and the recessive symbol is a symbol having a low probability of appearing. The predicted value of the occurrence probability of the dominant symbol is P0, and the predicted value of the occurrence probability of the inferior symbol is P1. In addition, the predicted value of the occurrence probability for a sequence of one or more symbols is "predicted occurrence probability", or
We simply call it the "probability of occurrence".

In the coding method according to the present invention, the occurrence probability of the next symbol to be coded is predicted by referring to the symbol which has already been coded. For this purpose, it is possible to use the result of statistically analyzing the occurrence of symbols in advance for the same coding target.

On the contrary, in the decoding method according to the present invention, the occurrence probability is predicted by referring to the already-decoded symbols in the same procedure as the coding device.

Although a specific prediction method and device configuration example for this purpose will be described later, the present invention does not depend on such a prediction method of occurrence probability value or a device configuration for prediction, and a signal source. A specific occurrence probability predicting means may be configured based on the characteristic of. For example, it is possible to provide a unit for performing pre-scanning of the symbol to be encoded and detecting its characteristic prior to the encoding process. If the detection result is added to the beginning of the code word, the same detection result can be used in the decoding process. Further, it is possible to provide a means for learning the characteristics of the signal source while executing the signal processing.

The relationship between the prediction occurrence probability and the coding efficiency will be added. Since the predicted occurrence probability is a predicted value of a symbol that will occur in the future, a reliable value cannot be obtained. Therefore, calculating the occurrence probability with high resolution does not always help improve the coding efficiency. Within the range of possible probability values (0 ≦ P1 ≦ 0.5, 0.5 ≦ P
The prediction value may be set so as to cover 0 ≦ 1.0).

In view of the above facts, the present invention is characterized in that the occurrence probability is roughly predicted to handle the arithmetic processing of that portion efficiently.

(II) Principle of Code Generation (II-1) Determination of Occurrence Probability Next, the principle of determining the occurrence probability of code generation according to the present invention will be described with reference to FIG. This will be explained in comparison with the principle. FIG. 2 is a schematic diagram showing the principle of determining the probability of occurrence of a conventional arithmetic code and the principle of determining the probability of occurrence of code generation according to the present invention.

As shown in FIG. 2A, according to the principle of the conventional arithmetic code (Elias code), the points on the [0,1) section are divided and the coordinates for encoding are obtained. The coordinates thus divided will be referred to as “probability coordinates”.

The width of this probability coordinate is a value that can be evaluated as the occurrence probability, and this is C. Here, since the initial value of the probability coordinate is [0,1), the initial value of C is 1.

At this time, when the input encoding target is the dominant symbol X0, the following (Equation 1) is used, and when it is the inferior symbol X1, the following (Equation 2) is used.

[0050]

[Equation 1] When Xi = X0: C ← C · P0 (Equation 1) When Xi = X1: C ← C · P1 (Equation 2) where P0 is the predicted occurrence probability of the dominant symbol X0. P1
Is the predicted occurrence probability of the dominant symbol X1. By sequentially calculating the above equation while inputting the encoding target, the point on the number line represented by the numerical value after the decimal point is obtained as shown in FIG. To use as. Then, the encoding by the occurrence probability of the arithmetic code can realize a compression rate that approaches the entropy which is the theoretical limit. On the other hand, however, this encoding method has a problem in that it requires a high calculation accuracy for the numbers below the decimal point.

Next, in contrast to this, the determination of the occurrence probability based on the code generation principle according to the present invention will be described. The feature of the present invention, which is different in principle from the conventional example, is shown in FIG.
As shown in (b), the interval on the number line divided by the occurrence probability is always normalized to "1".

In the method of obtaining the probability coordinates based on the arithmetic code of the conventional example, the probability coordinates are gradually narrowed on the code coordinates as shown in FIG. 2A, and are divided by the occurrence probability. The width of the section is very small after the decimal point.

In order to prevent the section thus divided from becoming smaller, the present invention multiplies the reciprocal of the width of the occurrence probability determined for each symbol. Specifically, when the initial value of the probability coordinate is [0,1) and the input encoding target is the dominant symbol X0, the following (Equation 3)
Then, in the case of the inferior symbol X1, calculation is performed by the following (formula 4).

[0054]

[Formula 2] When Xi = X0: C ← C / P0 (Equation 3) When Xi = X1: C ← C / P1 (Equation 4) The meaning of “normalization” here is selected The ratio of the predicted normal probability of the symbol to the width of the probability coordinate is given as 1.

In other words, if the selected symbol is Pi (i = 0,1) and the width of the j-th probability coordinate is C _j , the following proportional expression is to be established.

[0056]

[Equation 3] Pi: C _j = 1: C _{j + 1} (Equation 5) In this way, the width of the probability coordinate whose initial value was 1 expands in proportion to the reciprocal of the predicted occurrence probability. I will go.

(II-2) Specific Encoding Method Next, a specific encoding method based on the principle of determining the occurrence probability of the present invention will be described with reference to FIGS. 3 to 5. FIG. 3 is a schematic diagram showing an example of the encoding method according to the present invention. FIG. 4 is a schematic diagram showing the contents of the code register and the code buffer in time series. FIG. 5 is a schematic diagram showing an example of encoding of a dominant symbol.

In the present invention, the encoding is performed according to the determination of the occurrence probability of the code generation. Specifically,
Let us also consider the calculation procedure in the register.

Here, a register that can store a code for encoding is referred to as a code register, and the value of C is assumed to be in this range.

First, the predicted occurrence probability P0 of the dominant symbol is
It is assumed that the value is 1 or less, but extremely close to 1.
Then, in the above (formula 3), the following approximation is performed.

[0061]

(Equation 4) That is, when calculating C, the probability of occurrence of the dominant symbol is kept constant to simplify the calculation. In this way, the division by the occurrence probability P0 can be replaced by adding (incrementing) 1 to the current value C of the code register.

On the other hand, the predicted occurrence probability P1 of the inferior symbol is
Set the value that can be expressed as 1 / (2 ** R). Here, R is a positive integer of 1 or more, and is a value set based on the inferior symbol P1. Further, 2 ** R represents 2 to the power of R. At this time,

[0063]

(Equation 5) With this configuration, when the value C of the code register is represented by the binary system, the operation performed by the above (formula 7) can be realized by shifting the value C by R bits. In other words, the current code register value C
It is only necessary to add R "0" s to the lower order of.

For example, this concrete calculation example (R = 1 to 4) is shown in decimal notation as follows.

[0065]

[Equation 6] R = 1 P1 = 0.5 C = C ・ 2 R = 2 P1 = 0.25 C = C ・ 4 R = 3 P1 = 0.125 C = C ・ 8 R = 4 P1 = 0.0625 C = C ・ 16 where , R codewords represented by “0” will be referred to as “basic code of inferior symbol of length R”. That is,
The basic code of the inferior symbol of length R is a bit string added to the lower order of the code register when the predicted occurrence probability P1 of the inferior symbol is 1 / (2 ** R).

Now, the coding procedure of the present invention will be described below with reference to FIGS. 3 to 5 based on a specific signal sequence.

First, the principle of this procedure is to repeat the following (inferior code procedure) and (excellent code procedure). In addition,
We promise that a recessive symbol will be added to the beginning of the input signal.

"(Inferior code procedure) First, it is assumed that a recessive symbol is input. At this time, R zeros are inserted in the lower bits of the code register. That is, the basic code of length R is inserted into the code register. ] "(Excellent sign procedure) Next, the number of superior symbols is counted. Here, when the recessive symbol comes next to the recessive symbol, it is considered that the number of dominant symbols is zero. Then, the code register is incremented by this number.

However, the number of consecutive dominant symbols becomes large, and it may not be possible to represent only the basic code of length R in the code register.

Therefore, here, when the number of consecutive dominant symbols cannot be represented only by the R "0" portions of the basic code, a block code is newly connected to the end and the new block code is added to this new block code. The number of consecutive occurrences of the remaining dominant symbols needs to be encoded.

That is, when the basic code of the recessive symbol of the length R is incremented and all the bits become "1", the block code is added. For example, this fixed block of M bit length is added. The sign. The value of this block code is M bits long, and the number of consecutive occurrences of the remaining dominant symbols is expressed in binary.

In this way, the number of consecutive occurrences of the dominant symbol may not be represented by the M bit length. In this case, in the case where all the M-bit length block codes are replaced with "1", the procedure of adding a further N-bit length block code to the terminal end may be repeated without limitation. it can. That is, when all the bits of the block code to be added are “1”, the block code may be added after that.

Here, the bit length (M, N in the above example) of the block code to be added may be fixedly set, or may be variable based on the predicted occurrence probability of the preceding symbol, or It may be a variable-length Huffman code representing the number of consecutive occurrences of the remaining dominant symbols.

The above block code is added only when the basic code of the inferior symbol cannot be incremented to represent the number of consecutive occurrences of the superior symbol that follows, and the overflow caused by the increment is generated. It can be interpreted as a process for preventing.

A more detailed description based on this idea is as follows.

The basic code of length R in the lower bit of the code register is incremented and all bits are set to 1
When, the block code is added after that. This block code can be uniquely decodable. As the block code to be added, it is simple as an algorithm to use an R-bit code, so in the following description, an R-bit block code will be added.

If the number of consecutive dominant symbols is too large to be represented by one block code, a block code is added after this. in this way,
The block code is added repeatedly until the number of consecutive dominant symbols can be expressed.

In this way, the number of consecutive superior symbols is set to R
The algorithm expressed by the block code of bits is expressed as follows by mathematical expressions.

Let N be the number of consecutive dominant symbols.

When the following (Equation 8) is established, the code register is simply incremented N times.

[0081]

[Equation 7] N <2 ** R-1 (Equation 8) When (Equation 8) does not hold, the maximum positive integer m that satisfies the following (Equation 9) is taken.

[0082]

[Equation 8] N ≧ 2 ** mR-1 (Equation 9) Then, all the 0s of the R inserted in (1) are set to 1, and
Further, when m ≥ 2, the sign register stores (m-1) R
The bit set to 1 is added to the lower order of the code register.

Further, the basic code of the recessive symbol of length R is incremented by N- (2 ** mR-1) and added to the lower bits of the code register. That is, the code register is shifted by R bits and is incremented N-(2 ** mR-1) times. When N = (2 ** mR-1), the basic code of the recessive symbol of length R is simply added to the code register. Here, it is assumed that the recessive symbol is “1” and the dominant symbol is “0”. Now, in FIG. 3, the input signal “1” of (a) is a recessive symbol, and the value of R at this time is 3
Therefore, the corresponding codeword is “000” ((b)). At this time, as shown in FIG. 4A, the code register is shifted by 3 bits by the (inferior code procedure).

Next, the dominant symbol "0" continues four times ((c)). The code word corresponding to this is "100".
((D)), which is combined with the basic code of the preceding recessive symbol of length 3. Actually, the code register may be incremented four times as shown in FIG. 4B by the (excellent code procedure).

In the next recessive symbol (e), R is assumed to be 4, so the corresponding code word is "0000" ((g)). Here, since the recessive symbol (e) immediately follows the recessive symbol (e), the state of the code register shifts from FIG. 4C to FIG. 4D.

Next, the dominant symbol continues eight times ((ri)). Since the value of R immediately before is 3, the corresponding codeword is "111001" ((nu)).

This is to increment the value of the code register by 7 in accordance with the (excellent sign procedure) (FIG. 4 (e)).
After that, the code register is shifted by 3 bits (see FIG.
(F)) Finally, this value is incremented by 1 (FIG. 4 (g)).

As described in the section (superior code procedure), the concrete replacement of the dominant symbol with the code is shown in FIG.
It becomes as shown in.

Further, in the above description, the lower bits of the code register are incremented directly. However, counting is performed at another place, and then the basic code of the recessive symbol of length R on the code register and the bitwise It is also possible to take a procedure of combining such as taking an OR.

(III) Principle of Decoding Next, the principle of decoding the code generated as described above will be described.

In the above encoding process, the code word of the recessive symbol and the code word of the dominant symbol are combined and generated as one code word, starting from the code word of the recessive symbol. Now, the synthesized codeword is referred to as a synthesized codeword.

In the decoding process, the composite code word must be separated into the code word of the recessive symbol and the code word of the dominant symbol. Therefore, it is assumed that the beginning of the composite codeword can be identified now. At that time, the following codewords are recognized in the following cases. Then, these may be repeated until the decoding is completed. Also,
The value of R is obtained from the predicted occurrence probability of the inferior symbol.

(Decoding Case 1) If all R of the composite codewords are represented by "0", it means that the codewords are composed of only the codewords of the inferior symbol. When decoding, only the recessive symbols need to be decoded.

(Decoding Case 2) When "0" and "1" are mixed in the combined R codewords, the codeword of the inferior symbol and the codeword of the dominant symbol are mixed. is there. In that case, the dominant symbol is decoded by one recessive symbol and by the number of times when the R-bit codeword is interpreted in binary.

(Decoding Case 3) The R composite code words are
If all are represented by "1", the next code word is R
Examine the bits.

If all the code words are "1", the next R code words are checked. In this way, it is repeated for each block of R units and repeated until a block including "0" appears.

Here, it is assumed that all R-unit blocks of "1" appear m times, and when the immediately following R-unit block is converted into a binary number, it is b. In this case, one recessive symbol and a superior symbol (2 ** m
R-1) + b are decoded.

(IV) Features of the Present Invention In the present invention, when the recessive symbol appears as described above, the code register is shifted by the number of bits calculated from the predicted occurrence probability, and when the dominant symbol appears,
Increment the sign register. Based on such a principle, highly efficient encoding / decoding processing can be realized with a simple processing procedure. It is needless to say that similar effects can be obtained by performing the encoding / decoding process by replacing "0" and "1" assumed as the recessive and dominant symbols used in the description of the present invention. .

[Encoding / Decoding Procedure] (I) Encoding Procedure Next, the procedure of the encoding process based on the above principle will be described in order of FIG. FIG. 6 is a flowchart showing the procedure of the encoding process according to the present invention. Also in this description, it is assumed that the level of the input signal is a binary level of “0” and “1”.

(1) Initialization A code register for performing the calculation is prepared. Before inputting a signal, this code register needs to be initialized in order to clarify the start position of the code word (S601).

As a concrete example of this initialization, for example, an initial value "1" is set in the code register C. Alternatively, a virtual inferior symbol may be set and, for example, one “0” may be placed at the beginning of the codeword. Further, if the promise is decided by both of the devices that perform the encoding / decoding processing, the head code may be set without being limited to the above example, or no code may be added.

(2) Estimation of Probability Value Data to be a signal is statistically examined or the prediction occurrence probability of the encoding target is estimated by some predetermined algorithm (S602). For example, a typical method is to predict the occurrence probability of the next signal according to the already input signal value. It is assumed that the respective occurrence probabilities are estimated to be P0 for the dominant symbol X0 and P1 for the inferior symbol X1.

(3) Signal Input Next, a signal is input (S603). The occurrence probability of the signal is predicted by the above-mentioned procedure (2) of estimating the predicted occurrence probability.

(4) Creation of code Here, a signal value ("0", which has a high predicted occurrence probability P0,
It is assumed that either "1") is the dominant symbol X0, and the signal level having a low predicted occurrence probability P1 (value opposite to the dominant symbol X0) is the inferior symbol X1. Also, the current value of the sign register is
When C is set, the following judgment is made (S604).

[0105]

[Formula 9] Xi = X0: C ← C + 1 (Equation 10) That is, 1 is added to the current code (S6082).

[0106]

When Xi = X1: C ← C · 2 ** R (Equation 11) That is, the value of the code register is shifted to the left by R bits (S6081).

Here, as described in the principle of code generation, R is a value determined by the predicted occurrence probability P1 of the inferior symbol.

According to this procedure, in the case where the dominant symbol is successively generated following the inferior symbol, the R "0" s constituting the basic code of the preceding inferior symbol placed in the lower bit of the code register are generated. The "part"("the basic code of the recessive symbol of length R") is replaced with the binary number representing the succession of the dominant symbol by incrementing the code register by the number of successive dominant symbols.

When the basic code of the recessive symbol of length R placed in the lower bit of the code register is incremented to all "1", as described in (excellent code procedure). A block code is added (S608)
3).

(5) Code Output At the time when the coding of the predetermined symbol is completed, the code of the predetermined number of bits is created in the code register C, or the bits created in the code register overflow and can be accommodated. When a condition such as disappearance occurs, the content of the code register is output to, for example, the code buffer, the memory, or the like (S609).

After the code is output, the initial value of the register may need to be reset.

(6) Termination Judgment When the target encoding process is completed (S610), the contents of the register C at that time are output, and the termination process is completed.

To continue the coding process, the process for the next symbol is repeated.

(II) Decoding Procedure Next, the decoding procedure of the code performed according to the above principle will be described in the order of FIG. FIG. 7 is a flowchart showing a decoding procedure according to the present invention. Even in this decoding process, the original signal is "0" or "1".
Assume it is a value.

(1) Detection of the start position of a code word The code word is input to the register C.

Here, the head position of the code word is detected and determined based on the promise determined by both the devices that perform the encoding / decoding processing (S701).

(2) Prediction of Occurrence Probability The prediction occurrence probability of the encoding target is estimated by the same method as the estimation procedure of the prediction occurrence probability performed at the time of encoding (S702). Each predicted occurrence probability is P0 for the superior symbol X0 and the inferior symbol X1 as in the case of encoding.
Is P1.

(3) Input of Code Word Next, the code word is input (S703). And (2)
The occurrence probability corresponding to each codeword is predicted according to the procedure of estimating the predicted occurrence probability of.

(4) Codeword Detection and Recessive Symbol Reproduction Processing First, the length R of the recessive symbol when the codeword is separated into the dominant symbol and the recessive symbol based on the estimated value of the occurrence probability. Ask (S704).

It is detected whether or not there is a code word of the dominant symbol in the code words of length R (S704). That is, this is to check whether or not the symbol "1" appears in the codeword of length R.

Next, one recessive symbol is reproduced for the R code words (S704).

(5) Detecting Dominant Symbol and Reproducing Process of Dominant Symbol If at least one symbol "1" is included in the code of the length R (S705), this code word follows the recessive symbol. , The dominance symbol continues to occur. At this time, the process proceeds to S706.

In all cases, when the symbol is "0", the dominant symbol does not appear, so the dominant symbol is not reproduced.

When it is determined that the dominant symbol is continuously generated, the number of consecutive dominant symbols is detected (S7).
06), it is necessary to reproduce as many dominant symbols as that number (S706).

At this time, if all of the code words of length R are the symbols "1", it is necessary to consider the following block code. When the block code is followed by the block code, the number of consecutive dominant symbols must be obtained in the same manner.

When the signal is reproduced, the signal level having the high predicted occurrence probability P0 (either "0" or "1") is the dominant symbol X0, and the signal level having the low predicted occurrence probability P1 (the dominant symbol X0 (The opposite value) is the inferior symbol
Since it is associated with X1, the distinction between the superior symbol and the inferior symbol obtained by decoding may be associated with the predicted occurrence probability.

(6) Termination judgment If the decoding of all codewords is completed, the processing is terminated (S70).
7) Otherwise, the decoding of the next codeword is repeated.

(III) About Code Output As timings to output a codeword, the time when the generated codeword reaches a certain length, the time when the number of encoded symbols reaches a certain amount, and the symbol to be encoded Can be used when

The code word to be output may be a bit sequence as it is, or may be divided because it is incorporated in some frame structure. For example, if the information field in the frame has a size of 58 bytes, the generated codeword is divided into the number of bytes and output.

When storing and transmitting code data, C
It is desirable to use a means for eliminating data errors such as RC (Cyclic Redundancy Check). The present invention does not limit the means for eliminating the data error and can be combined with various means.

Header information including some information can be added prior to the bit string of the code word. For example, information that explicitly indicates that the code has been generated according to the present invention, the number of symbols to be encoded (that is, the number of symbols to be decoded), and the like can be set as the header information.

Furthermore, it is also possible to insert a synchronization signal containing some information for each fixed number of coded symbols or fixed codeword bits. For example, a specific bit pattern can be set as a so-called escape code, and some control signal can be inserted subsequently to the code. As the escape code, for example, a code word corresponding to an inferior symbol having a very low occurrence probability, which is not used in the actual encoding process, may be used.

[Configuration of Encoding / Decoding Device] (I) Configuration of Encoding Device Next, the configuration of the encoding device according to the present invention will be described with reference to FIGS. 8 and 10. FIG. 8 is a block diagram showing the configuration of the encoding device according to the present invention. FIG. 10 is a diagram schematically showing a code register and a code buffer of the encoding device according to the present invention.

The occurrence probability prediction device 101 predicts the occurrence probability of the symbol to be coded. That is, the memory device 1
At 00, symbols that have already undergone encoding processing are temporarily accumulated. The output from that is used to predict the occurrence probability of the next symbol to be encoded, and which of the symbols is , Set whether to become the dominant symbol or the inferior symbol.

Then, the dominant symbol and the inferior symbol based on this judgment are compared with the actually generated symbol which is the symbol to be encoded, by using the comparator 102. Prediction probability output from the occurrence probability prediction device 101 and the comparator 10
2 and the bit shift control device 103 for generating a code word corresponding to the inferior symbol and the measuring device 104 for counting the number of occurrences of the dominant symbol. Then, the code words generated by each are combined using the code register 105. Further, the code buffer 106 is prepared in order to temporarily store the output codeword.

Here, the conventional method requires a plurality of registers for handling numerical values below the decimal point,
As shown in FIG. 10, the sign register 105 of the present invention may be a binary register capable of expressing a positive integer value including "0".

The code register 105 can have various configurations as follows.

(1) Single register (2) Multiple registers are connected and configured (3) Single register and general-purpose memory are combined Here, the bit configuration of the code register 105 is From the viewpoint of simplification and improvement of processing speed, it is desirable to provide the maximum codeword length of the inferior symbol as the minimum length.

In order to use the general-purpose memory for accumulating the code word, the general-purpose memory is combined with a pointer for indicating the final position of the accumulated code or a counter for measuring the number of bits of the accumulated code. It can be used without depending on the bit configuration of.

(II) Configuration of Decoding Device Next, the configuration of the decoding device according to the present invention will be described with reference to FIG. FIG. 9 is a block diagram of the configuration of the decoding device according to the present invention.

First, the input codeword is transferred from the code buffer 206, which temporarily stores the codeword, to the code register 205. The occurrence probability prediction device 201 predicts the occurrence probability of the next symbol to be decoded using the output of the memory device 200 that temporarily stores the symbols that have already undergone the decoding process. Set whether the symbol will be the dominant symbol or the inferior symbol.

In accordance with the code of the code register 205 and the result of the predicted occurrence probability of the symbol output from the occurrence probability prediction device 201, the inferior symbol is used by the inferior symbol reproduction device 203 and the superior symbol by the superior symbol reproduction device 204. The reproduction is executed and the symbol is restored using the signal synthesis output device 202.

(III) Improvement of Processing Speed From the viewpoint of signal processing speed, it is desirable to encode or decode one symbol in one machine cycle. To this end, the operations of the code generation device and the code analysis device may be configured to process symbols in synchronization with the machine cycle.

By incorporating a coding / decoding device capable of coding or decoding one symbol in one machine cycle, image signal processing characterized by high-speed signal processing is incorporated. The device can be realized.

[Speeding Up of Encoding / Decoding Process Using Code Table] Next, it will be described with reference to FIGS. 11 and 12 that the speed of the encoding / decoding process according to the present invention can be increased by using the code table. FIG. 11 is a schematic diagram of a code table. FIG. 12 is a block diagram of an encoding device and a decoding device using a code table.

In the encoding process according to the present invention, the code word is generated for each input symbol by the encoding process procedure. In the decoding process, the input code is decoded to generate a signal. However, the code word (in the case of decoding, the signal for the input code) corresponding to the combination of symbols that occur consecutively is
It may be created in advance.

For example, when one inferior symbol and one or a plurality of superior symbols are consecutive, as shown in FIG. 11, the code words corresponding to the combination of the symbols may be predetermined and collected in a table. it can. The parameters for creating the code table are the probability of occurrence of the inferior symbol and the number of consecutive succeeding dominant symbols.

Hereinafter, this will be referred to as a "code table". According to this code table, the coding / decoding processing described so far can be performed only by searching the table, so that it can be expected that the processing speed is improved.

An example of the configuration of the encoding process and the decoding process using such a code table is as shown in FIG.

This apparatus has basically the same configuration as that shown in FIGS. 8 and 9, but instead of the code registers 105 and 205 for performing the calculation, the code table 110 as shown in FIG. 11 is used. And 210.

As described above, the advantage of using the code table is that the code register for calculating the code word can be eliminated, the code generation procedure and the decoding procedure for each symbol can be simplified, and the speed of the encoding / decoding processing can be increased. There is a point that can be realized.

In particular, in the decoding process, one inferior symbol and a plurality (0 or more) of superior symbols can be decoded by performing a table search for a codeword corresponding to the codeword length of one inferior symbol. That is, it can be said that, in terms of the signal processing speed in symbol units, in general, the decoding process can be executed at a higher speed than the encoding process in comparison.

The concept of encoding / decoding by the code table is based on the fact that the non-block code generation process of the present invention can be represented by a finite state transition. In other words, although it is different in principle, it is shown that the encoding process can be realized by connecting the codewords created in advance, like the block code.

The coding process using the block code is as follows.
Although a process of collectively converting a plurality of target symbols into a code word can be adopted, what can be referred to in predicting the occurrence probability is a symbol that has been processed before the target symbol corresponding to the code word.

On the other hand, in the encoding processing of the present invention, since the code word is basically created for each target symbol,
Up to the last symbol can be referred to for the prediction of the occurrence probability.

[Embodiment by Program and Processor] The basic procedure of the encoding / decoding processing described so far can be easily realized by a program procedure using a general processor.

The processor mentioned here is a so-called general-purpose processor, and structurally consists of several general-purpose registers,
It has an address register and the like and is used by being connected to a general-purpose memory, interpreting and executing a program stored in the general-purpose memory, and inputting / outputting data stored in the memory.

As the code register described above, a general-purpose register incorporated in this processor can be used. A general-purpose memory that can be accessed by the processor can be used as the memory that stores the code. Bit length can also be increased by connecting multiple general-purpose registers built into the processor.

Even in this case, in order to speed up the signal processing, as described above, code words corresponding to a combination of a plurality of symbols are arranged in advance in the memory as a table as a code table. Of course, you can do it. At this time, the code table on the memory can be searched easily by converting the search data into a memory address.

Further, as a matter of course, even when the present invention is executed by a program procedure by a general-purpose processor, it does not depend on the type of processor that executes signal processing, the type of programming language, or the like.

[Multilevel Encoding Processing] Next, referring to FIG.
It will be described with reference to FIG. 14 and FIG. 14 that the encoding / decoding processing procedure according to the present invention can also be applied to the case where the input symbol has a multi-value level. That is, the procedure described so far is for the case where the signal level that the input target symbol can take is a binary value, but here, the multilevel signal is encoded by being used in combination with other processing. Explain what you can do. FIG. 13 is a diagram schematically illustrating two methods for performing multilevel coding. FIG.
FIG. 3 is a block diagram of an encoding device according to a mixed code system.

(I) Code Mixed Method First, an encoding / decoding method according to an example of the code mixed method will be described.

Since this method is a method in which the arithmetic code and the block code explained so far are combined, it is called "code mixed method".

In the case of encoding by this method, FIG.
As shown in (a), first, the possible states (2 or more) of the target symbol are divided into two groups, the dominant and the inferior, based on the predicted occurrence probability. Then, next, the distinction of the state of the symbol in each group is represented by a block code.

That is, according to this method, the code word corresponding to one symbol is divided into a code word based on an arithmetic code for distinguishing between superiority and inferiority and a block code for distinguishing symbols in each group. There are two types of combinations of code words based on each other.

When an arithmetic code and a block code are combined, for example, when the code register has an arithmetic code,
It suffices to shift it by the required amount to the left and add it to the code word in the shifted area of the block code. Alternatively,
When a plurality of block codes are added without bit shift of the code register, they are connected in order. In this way, it is possible to create a codeword in which the codeword based on the arithmetic code and the block code are mixed.

On the contrary, on the decoding side, two types of code words corresponding to one symbol, that is, a code word based on an arithmetic code and a subsequent block code are analyzed.

Here, as an example of the above grouping method, it is possible to assign only one state to the dominant group and assign all the remaining states to the inferior group. For example, in the case of FIG. 13A, only s1 is a dominant group and s2 to sK are recessive groups.

In this case, since it is not necessary for the dominant group to distinguish the symbol states, it is possible to create the block code only in the inferior group and to create the code word in which the code word based on the arithmetic code and the block code are mixed. .

FIG. 14 shows the structure of the coding apparatus based on this code mixing method.

That is, a buffer memory for storing a code word based on the arithmetic code and a code memory based on the block code is separately prepared. Then, position information indicating the bit position connecting both codewords is stored, and when the codewords of both are output from these memories, the combination process of both codewords is performed using this position information. By doing so, one code string can be output.

In addition, a table of combinations of code words based on arithmetic codes and code words based on block codes is created in advance, and this table is used as a code table for encoding / decoding. It is also possible to convert to a code word at a high speed by searching this code table based on.

(II) Tree expansion method In this tree expansion method, as shown in FIG. 13B, the states (2 or more) that the target symbol can take are expanded into two branch trees, and each branch node ●. When dividing, the symbols "0" and "1" are made to correspond. By doing so, the multi-valued state can be mapped to the binary symbol. Then, while obtaining the predicted occurrence probability at each branch point, the process is repeated until reaching the branch, and encoding is performed based on the arithmetic code described so far, whereby a code word corresponding to one symbol can be created. Note that the number of branches from the root of the two-branch tree to the branches may be uniform or non-uniform in all symbol states.

[Specific Application Example of Encoding / Decoding Method of the Present Invention] Finally, the encoding / decoding method of the present invention is specifically applied to any system with reference to FIGS. 15 to 18. Explain what is done. FIG. 15 is a schematic diagram showing how to calculate the predicted occurrence probability when the image data of a still image is encoded. FIG. 16 is a schematic diagram for explaining the relationship between image subsampling and predicted occurrence probabilities, and the order of encoding when there are multiple planes. FIG.
[Fig. 3] is a schematic diagram for explaining one of a waveform signal coding process and a line drawing information coding process. FIG. 18 is a schematic diagram showing the basic configuration of the encoding processing device and the basic configuration of the multimedia encoding processing device in comparison.

(I) Still Image Not limited to a still image, image data is generally represented as a set of pixels.

An example of a method of predicting the occurrence probability at this time will be described.

For example, the signal value of the pixel of interest can be predicted by using the signal value of the pixel adjacent to the pixel of interest to be coded and for which the encoding process has already been completed as the reference pixel. The present invention does not depend on the prediction method and device configuration, but will be described as a powerful method of predicting the occurrence probability of image data with reference to FIG.

As shown in FIG. 15A, the reference pixel is set to Y.
It is assumed that A, YB, and YC are set, the target pixel is set to Y, and binary levels of 0 and 1 are taken.

Since the signal level of the target pixel Y is related to the signal level of the adjacent reference pixel, Y
The appearance frequencies of the signal levels of A, YB, YC and Y are summarized in statistics for general images. Thus, FIG.
As shown in (b), three reference pixels can take 8
The occurrence probability of the signal level (0 or 1) of the pixel of interest in each state can be set. Using this result, the occurrence probability of the pixel of interest can be predicted using the reference pixel in the actual encoding process of the image data.

Naturally, the encoding / decoding method of the present invention does not limit the set number of reference pixels and the set place in this example, and the set number of reference pixels
The setting location can be changed adaptively.

Further, in the encoding processing of a grayscale image having a multi-valued level per pixel, the encoding / decoding procedure of the present invention can be applied by converting the signal into a binary level signal. . For example, the encoding / decoding method of the present invention is applied to a multilevel signal represented by a binary code, a gray code, or the like, which is scanned for each bit plane to become a binary level signal for each pixel. As a result, efficient encoding processing can be realized. here,
FIG. 16B is a diagram showing an example of the sequence when encoding the bit plane.

Further, as shown in FIG. 16A, sub-sampling can be performed by interlaced scanning of pixels for each bit plane. Since the reference pixels can be set around the target pixel, the occurrence probability of the signal of the target pixel can be obtained with high accuracy, and the compression rate can be improved. The data that is sub-sampled and coded is decoded from different places, so it is suitable for hierarchical decoding and reproduction that makes a picture appear gradually, and it is possible to efficiently search for images. . So, for example, in medical images,
The present invention can be effectively used in the case of high definition, high gradation, easy retrieval of a wide variety of images, and data storage without deterioration.

The encoding / decoding procedure of a color image will be described.

ITU-T Recommendation T.81 is given as a recommendation for defining encoding / decoding of such a color image. In this Recommendation, DCT (Discrete Cosine Transform, Discret
It is stipulated that the Huffman code be used for the encoding process of the frequency component after performing the e Cosign Transform.
Applying an arithmetic code instead of the Huffman code is defined as an optional function. Instead of the arithmetic code, the encoding process according to the present invention can be applied.

Even in the encoding process of a color image represented by a plurality of color signals per pixel, the same efficient encoding process is realized by applying the above-mentioned grayscale image encoding process method for each color. can do. At this time, the occurrence probability of the signal of each color can be obtained by utilizing the color signal of the adjacent pixel and the peculiarity of signal generation in the color space having each color as the coordinate axis.

(II) Moving picture In a moving picture, not only pixels in the same frame but also signal prediction utilizing the correlation in the time axis direction of the picture is possible.
For example, in a moving picture coding method called MPEG (Moving Picture Experts Group), signal processing such as motion prediction is performed between a plurality of temporally consecutive frames, and DCT (discrete cosine transform) is performed in each frame. Then, the result is converted into a code word.

The coding / decoding processing of the present invention can be applied to the case where the occurrence probability of the symbol to be coded can be predicted in advance without depending on such signal processing.

As pointed out in the description of the prior art, one of the problems of the encoding / decoding processing device based on arithmetic codes is the non-uniformity of the decoding generation rate called latency (latency of decoded output). is there. This problem is emphasized especially when real-time processing is required such as coding and decoding of moving images.

As described above, according to the present invention, the number of branches of signal processing based on judgment is smaller than that of the conventional method, and latency of decoded output is theoretically impossible. Therefore, the present invention is particularly useful in a system requiring real-time processing. This is a useful technique.

(III) Waveform signal of voice, etc. A voice signal is a one-dimensional signal change in the time axis direction,
That is, it is a waveform signal. As a similar signal, for example,
There are electric signal waveforms such as voltage, vibration waveforms such as earthquakes, and electrocardiogram waveforms.

For such waveform signals as shown in FIG.
As shown in (a), it is possible to calculate the difference value of the sampled signal levels, predict the occurrence probability of the difference value by referring to the past signal levels, and perform the multi-value level encoding process.

(IV) Line Image of Map etc. [0192] An efficient encoding method of a line figure constituting a map image etc. will be described. In general, a line figure can be expressed as a series of vectors. As an example of the encoding process in this case, a line is decomposed into a vector as shown in FIG. 14B, the angular range that the vector can take is sequentially divided and represented by a binary tree, and the occurrence probability of each divided range is represented. By predicting, the present invention can be easily utilized.

Further, the vector is represented by a combination of two pieces of information of the angle and the length. Here, the angle information is converted into a code word by using the arithmetic code as described above, the length information is converted into a code word by using the block code, and both are converted in the same manner as the above-mentioned multilevel coding method. It is also possible to mix them in one code string.

(V) Signal processing device for executing only decoding process For example, only decoding process is performed because the coded data downloaded from the network or the coded data stored in the CD-ROM or the semiconductor memory is decoded and used. It is possible to configure a signal processing device including.

Since the encoding process is not required, the part that performs the signal process can be configured only by the device that performs only the decoding process of the present invention.

(VI) Replacing the conventional coding / decoding device based on arithmetic codes with the coding / decoding device of the present invention. ITU Recommendations T.81 and T.8 standardized as an international standard.
In the coding / decoding device based on 2, the part that executes the coding / decoding process based on the arithmetic code can be replaced with the coding / decoding device of the present invention. It is also one of the features of the encoding / decoding processing according to the present invention that the encoding / decoding device can be easily replaced.

(VII) Encoding and Decoding of Multimedia Recently, there has been an increasing interest in multimedia in which various media are handled in an integrated manner.

Also according to the encoding / decoding method of the present invention, signals from a plurality of types of signal sources such as binary images, multi-valued images, color images, audio signals, line images, etc. obtained from various media can be easily converted. It can be used as a multimedia encoding / decoding device that efficiently performs encoding / decoding with the device configuration.

That is, as shown in FIG. 18 (a), the encoding process is conceptually divided into modeling, occurrence probability prediction, and code generation. A plurality of units are prepared as shown in FIG. 18B, the prediction of the occurrence probability is connected in parallel based on the characteristics of each signal of a plurality of types of multimedia, and the means for code generation is common. It can be realized by operating the.

Here, with respect to multi-valued images, color images, audio signals, line images, etc., as described above, means for predicting the occurrence probability for performing subsampling, bit plane expansion, tree expansion, etc. are prepared. can do.

Here, the device for modeling in FIG. 18B is a device for combining a reference symbol and a symbol of interest from a symbol to be coded to obtain a correlation between signal characteristics of both, and Configure according to the types of multiple signal sources. Here, in order to prepare the reference symbols, a memory for temporarily storing the already signal-processed symbols is required, but for this purpose, one memory device can be commonly used. .

A code for distinguishing the type of signal source can be added to the generated code word. It is also possible to add a code for distinguishing the type of coding.

Further, the codes of a plurality of types of signal sources can be multiplexed based on a certain rule, but the coding / decoding method of the present invention does not depend on the multiplexing means.

In this way, it is expected that the present invention can be effectively used in a display device, a storage device, a transmission device, and the like, which are a combination of a plurality of signal sources called so-called multimedia.

[0205]

According to the present invention, in a coding / decoding device for compressing data into a code and decoding the data, the compression efficiency of the non-block code is not impaired, and the coding is simple. It is a method that can perform encoding and decoding by various algorithms, and does not require a complicated device,
It is possible to provide an encoding / decoding device that performs encoding / decoding with a high calculation speed.

[Brief description of drawings]

FIG. 1 is a basic principle diagram of an encoding method in an encoding / decoding device according to the present invention.

FIG. 2 is a schematic diagram showing a principle of determining a probability of occurrence of a conventional arithmetic code and a principle of determining a probability of occurrence of code generation according to the present invention.

FIG. 3 is a schematic diagram showing an example of an encoding method according to the present invention.

FIG. 4 is a schematic diagram showing the contents of a code register and a code buffer in time series.

FIG. 5 is a schematic diagram showing an example of encoding of a dominant symbol.

FIG. 6 is a flowchart showing a procedure of an encoding process according to the present invention.

FIG. 7 is a flowchart showing a decoding procedure according to the present invention.

FIG. 8 is a block diagram showing a configuration of an encoding device according to the present invention.

FIG. 9 is a block diagram of a configuration of a decoding device according to the present invention.

FIG. 10 is a diagram schematically showing a code register and a code buffer of the encoding device according to the present invention.

FIG. 11 is a schematic diagram of a code table.

FIG. 12 is a block diagram of an encoding device and a decoding device using a code table.

[Fig. 13] Fig. 13 is a diagram schematically illustrating two methods for performing multilevel coding.

[Fig. 14] Fig. 14 is a block diagram of an encoding device according to a mixed code system.

FIG. 15 is a diagram showing a case where image data of a still image is encoded,
It is a schematic diagram which shows how to calculate a prediction occurrence probability.

[Fig. 16] Fig. 16 is a schematic diagram for explaining a relationship between image subsampling and a predicted occurrence probability, and an encoding order when a plurality of planes are included.

FIG. 17 is a schematic diagram for explaining the encoding process of the waveform signal and the encoding process of the line drawing information.

FIG. 18 is a schematic diagram showing the basic configuration of the encoding processing device and the basic configuration of the multimedia encoding processing device in comparison.

Claims (16)

[Claims] 1. A coding / decoding device for performing coding of an input signal and decoding which is a reverse process of the input signal, means for predicting a probability of occurrence of a symbol, means for discriminating a symbol of an input signal, and a code register. And a shift control means, and when performing the encoding, by the means for predicting the occurrence probability of the input signal, the means for predicting the occurrence probability of the symbol of the input signal, the means for determining the symbol of the input signal, Among the predicted occurrence probabilities of the symbols obtained by the means for predicting the probability, the symbol with the larger predicted occurrence probability is determined to be the dominant symbol, and the symbol with the smaller predicted occurrence probability is determined to be the recessive symbol. Occurrence prediction probability, which is the R-th power of 2 (1/2 **
R and R are represented by positive integers, and when the recessive symbol is input, the shift control means sets the code register to a higher order for one recessive symbol.
An encoding / decoding device characterized by shifting R bits and inserting R zeros in the lower order. 2. A coding / decoding device for performing coding of an input signal and decoding which is a reverse process thereof, means for predicting a symbol occurrence probability, means for discriminating a symbol of an input signal, and a code register. And a counter, and at the time of encoding, predicting the occurrence probability of the symbol of the input signal by the means for predicting the occurrence probability, and determining the occurrence probability by the means for determining the symbol of the input signal. Among the predicted occurrence probabilities of the symbols obtained by the predicting means, the symbol with the larger predicted occurrence probability is determined as the dominant symbol, and the symbol with the smaller predicted occurrence probability is determined as the recessive symbol, and the occurrence prediction of the recessive symbol is predicted. Probability is the R-th power of 2 (1/2 **
R and R are represented by positive integers, and when the dominant symbol is input, the counter counts the number of consecutive occurrences of the dominant symbol and increments the code register by the counted number. An encoding / decoding device characterized by: 3. The coding / decoding device having the functions of the coding / decoding device according to claim 1, wherein, when performing the coding, when the recessive symbol is input, When the first codeword consisting of R 0s generated on the code register and the dominant symbol are input, the code register is incremented as described in claim 2. An encoding / decoding device, which generates a generated second codeword and combines the first codeword and the second codeword to generate a code. 4. A coding / decoding device for performing coding of an input signal and decoding which is the reverse process, means for predicting a probability of occurrence of a symbol, means for discriminating a symbol of an input signal, and a code register. A shift control means, a counter, and when performing encoding, by means for predicting the occurrence probability of the input signal, by means for predicting the occurrence probability of the symbol of the input signal, and by means for determining the symbol of the input signal Among the predicted occurrence probabilities of the symbols obtained by the means for predicting the occurrence probability, a symbol having a larger predicted occurrence probability is determined as a dominant symbol, and a symbol having a smaller predicted occurrence probability is determined as a recessive symbol, The probability of occurrence of a recessive symbol is calculated by dividing the R power of 2 by 1 (1/2 **
R and R are represented by positive integers, and when the recessive symbol is input, the shift control means sets the code register to a higher order for one recessive symbol.
When the R number is shifted by R bits and the R zeros are inserted in the lower order and the dominant symbol is input, the counter counts the number of consecutive occurrences of the dominant symbol, and only the counted number is generated. The lower part of the sign register
Encoding R number of 0s and encoding the input signal on the code register in this way, with one recessive symbol and zero or more dominant symbols as a set. Decoding device. 5. The number of consecutive occurrences of the input dominant symbol is N, and the occurrence prediction probability of a recessive symbol is 1 (1
/ 2 ** R, R is a positive integer), and if (2 ** R-1)> N, it is generated as a codeword of a recessive symbol on the code register. Increment R 0s by N, and if (2 ** R-1) ≤ N, set all 0s on the code register generated as codewords of recessive symbols to 1, A code word that means a = N- (2 ** R-1) is generated, these are combined, and a code word is generated by combining the code word of the recessive symbol and the code word of the dominant symbol. The encoding / decoding device according to any one of claims 3 and 4. 6. The code word meaning a = N- (2 ** R-1) is composed of a continuous block consisting of the R number, and all bits are from 1 except for the last block. The encoding / decoding device according to claim 5, wherein 7. A processor having a processor and a memory, wherein the code register is a register in the processor, and a procedure for coding the dominant symbol or the recessive symbol on the register is stored in the memory. The encoding / decoding device according to any one of claims 1 to 6, wherein the processor executes the program in accordance with a stored program. 8. The code word generated in the lower order on the code register is preliminarily created with one recessive symbol and zero or more dominant symbols as a set as set forth in claim 3 or claim 4. It should be noted that a table having the one recessive symbol, zero or more dominant symbols, and the corresponding codeword as one item is provided, and an input signal is treated as one recessive symbol by this table. An encoding / decoding device, characterized in that a set of zero or more dominant symbols is searched for corresponding codewords and encoded. 9. A case where an input signal is composed of symbols that can take a plurality of states, and states that the symbols can take are determined by a dominant group based on the predicted occurrence probability predicted by the prediction occurrence probability means. It divides into two groups of a recessive group, When the state of the recessive group is input,
The processing is performed as when the recessive symbol described in the above is input, and when the state of the dominant group is input,
The processing is performed as when the above-described dominant symbol is input, and the first code word and the second code word are combined as described in claim 3 to form a set of code words, and , A symbol is created by using a block code to specify a state of a symbol in the group to which the symbol belongs, and a set of code words in which the first code word and the second code word are combined. 9. The combination of a code word with a code word that specifies the status of a symbol in the group to which the symbol belongs belongs to a code word that can take the input signal. Any encoding / decoding device. 10. The method according to claim 1, wherein when the input signal has a plurality of signal characteristics, a plurality of occurrence probability predicting means corresponding to the respective signal characteristics are provided. The encoding / decoding device. 11. An encoding method for performing encoding of an input signal and decoding which is a reverse process thereof, wherein an encoding device predicts a probability of occurrence of a symbol, and a device that determines a symbol of an input signal. , A code register, a shift control means, and a counter, among the predicted occurrence probabilities of the symbols obtained by the means for predicting the occurrence probability, the symbol having the larger predicted occurrence probability is the dominant symbol and the smaller one. When the symbol having the predicted occurrence probability of is a recessive symbol and the predicted occurrence probability of the symbol obtained by the means for predicting the occurrence probability of the symbol is the larger symbol as the dominant symbol and the smaller symbol as the recessive symbol. Then, the probability of occurrence of recessive symbols is calculated by dividing the R power of 2 by 1 (1/2 **
R and R are represented by positive integers, and (1) by the means for predicting the occurrence probability, the procedure for predicting the occurrence probability of the symbol of the input signal, (2) by the means for determining the symbol of the input signal. , A procedure for discriminating the input signal into a dominant symbol and a recessive symbol, (3) a procedure for inputting the recessive symbol, (4) for one recessive symbol,
By the shift control means, the code register
R bit-shifted, and further, generating a first codeword in which R 0s are inserted in the lower order, (5) inputting the dominant symbol, (6) continuation of the dominant symbol by the counter A procedure of counting the number of occurrences and incrementing the code register to generate a second code word by the counted number, (7) combining the first code word and the second code word The above procedure (1) to (7) is repeated in this order to generate a code word by using one recessive symbol and zero or more dominant symbols as a set as an input signal. An encoding method characterized by going. 12. An encoding method for performing encoding of an input signal and decoding, which is the reverse process, wherein an encoding device predicts a probability of occurrence of a symbol, and means for determining a symbol of an input signal. , A code register, a shift control means, and a counter, among the predicted occurrence probabilities of the symbols obtained by the means for predicting the occurrence probability, the symbol having the larger predicted occurrence probability is the dominant symbol and the smaller one. When the symbol having the predicted occurrence probability of is a recessive symbol and the predicted occurrence probability of the symbol obtained by the means for predicting the occurrence probability of the symbol is the larger symbol as the dominant symbol and the smaller symbol as the recessive symbol. Then, the probability of occurrence of recessive symbols is calculated by dividing the R power of 2 by 1 (1/2 **
R and R are represented by positive integers, and (1) by the means for predicting the occurrence probability, the procedure for predicting the occurrence probability of the symbol of the input signal, (2) by the means for determining the symbol of the input signal. , A step of discriminating the input signal into a dominant symbol and a recessive symbol, (3) a step of inputting the recessive symbol, (4) 'with respect to the one recessive symbol, the shift control means sets the code register to a higher order. R bits are shifted to, and R number of 0s are inserted in the lower order, (5) The above-mentioned dominant symbol is input,
(6) ′ The counter has a procedure of counting the number of consecutive occurrences of the dominant symbol and incrementing the lower R number of the code register by the counted number. ), (4) ', (5), (6)'
The coding method is characterized in that the above procedure is repeated in this order, and the input signal is coded on the code register as a set of one recessive symbol and zero or more dominant symbols. 13. The number of consecutive occurrences of a dominant symbol at the time of encoding is N, and the probability of occurrence of a recessive symbol is 1 (1
/ 2 ** R, R is a positive integer)
If -1)> N, increment the R 0s of the code register generated as codewords of the recessive symbol by N, and if (2 ** R-1) ≤N, A procedure for generating a code word meaning a = N- (2 ** R-1) by setting all the lower R 0s of the code register generated as the code word of 1 to 1, and combining these. Is defined as (O), the procedure of (6) and (7) described in claim 11 is replaced with this procedure (O), or (6) ′ of claim 12 is defined as this procedure (O). 11. The method according to claim 11 and claim 1, wherein
2. The encoding method according to any one of 2 above. 14. The code word meaning a = N- (2 ** R-1) is composed of consecutive blocks of R each, and all bits are 1 to 1 except for the last block. The encoding method according to claim 13, wherein 15. A code word, which is a combination of a code word of a recessive symbol and a code word of a dominant symbol, generated in accordance with claim 11, is created in advance, and the code word of the one recessive symbol is generated. , A table in which 0 or more dominant symbols and the corresponding codewords corresponding thereto are set as one item is used, and by this table, an input signal is classified into one recessive symbol and 0 or more dominant symbols. 12. When the procedure for searching the corresponding codewords as a set is (T), in the procedures (1) to (3) and (5) according to claim 11, (1) to (3), (5) ) And (T) are repeated in this order to perform encoding. 16. A case where an input signal is composed of symbols that can take a plurality of states, and states that the symbols can take are determined by a dominant group based on the predicted occurrence probability predicted by the prediction occurrence probability means. (B) a procedure of creating a codeword that identifies a state of a symbol in the group to which the symbol belongs by dividing it into two groups of inferior groups (B), one recessive group and zero or more superior groups A group and a code word encoded on the code register as a set,
12. The procedure of (1) to (6) according to claim 11, wherein when the procedure of combining the symbol with a codeword that specifies the state of the symbol in the group to which the symbol belongs is (C). Is read as the dominant group and the recessive symbol is read as the recessive group, and a process of generating a code word in which the code word of the recessive group and the code word of the dominant group are combined is performed, and then (B) and (C). Is performed in this order, and a series of these processes is repeated to perform encoding.