JPH04343576A - High-efficiency encoding method and high-efficiency code decoding method - Google Patents

Abstract

PURPOSE:To drastically improve transmission error resistance without reducing coding efficiency by transmitting the upper bit information of a predictive error and the lower bit information of input data. CONSTITUTION:The category number Ji of the upper bit information of a predictive error and the residual data Ei of the lower bit information of input data are coded and transmitted. Namely a coding circuit 110 finds out the number Mi of bits in residual data Ei included in a prescribed table based upon the category number Ji and outputs the lower Mi bits of the data Ei by a bit serial format. The output is coded data CEi. Since the data Ei can be expressed by the Mi bits, only the lower Mi bits of the data Ei are outputted. A multiplexing circuit 111 outputs coded data Ci obtained by connecting the data CEi to the back of coded data CJi from a terminal 108 by the bit serial form.

Description

[Detailed description of the invention]

0001

[Field of Industrial Application] The present invention relates to a high-efficiency encoding method and a high-efficiency code decoding method for reducing the amount of information such as data obtained by sampling and quantizing analog signals such as video and audio. .

0002

2. Description of the Related Art There are various methods for high-efficiency encoding, and there are also methods that combine these methods. Currently, high-efficiency encoding methods for images and audio are being standardized, and standardization of still image encoding methods is being promoted by JPEG, a subordinate organization of the International Organization for Standardization (ISO).

[0003] As a conventional high-efficiency encoding method, the DCT method, which is a JPEG high-efficiency encoding method, will be explained as an example (Reference: Journal of the Television Society Vol. 44, No. 2).
(1990) pp158-159).

The input signal is a sampled and quantized image signal, ie, digital image data. Image data, which is a raster scan pixel arrangement, is formed into a rectangular area of 8 pixels each in the horizontal and vertical directions of the screen (this is called a block).
Divide into blocks and convert the data into blocks. This is called blocking. An 8th-order two-dimensional discrete cosine transform (hereinafter referred to as DCT) is performed for each block, and the obtained DCT coefficients are quantized by a predetermined quantization step Q determined for each coefficient (that is, divided by Q and rounded). ). The AC coefficients of the quantized DCT coefficients are subjected to two-dimensional Huffman encoding, and the DC coefficients of the quantized DCT coefficients are predictively encoded.

[0005] The predictive encoding method of the DC coefficient will be explained. The input data is the DC coefficient of the quantized DCT coefficient, which is converted into data Di (i=0, 1, 2
,3,. ．． ．． ．． , i is the data number, which is equal to the block number). Predictive coding involves finding a predicted value Pi using coded input data, finding a prediction error Si that is the difference between the input data Di and the predicted value Pi, and encoding the prediction error Si. The prediction method is previous value prediction, in which the previous input data is used as the predicted value.

[0006] A method of encoding the prediction error Si will be explained. The prediction errors Si are classified into predetermined categories according to their magnitudes, and the number of the corresponding category is obtained, which is then Huffman encoded. The category number corresponds to the upper bit information of the prediction error. As for the prediction error, the lower bits are cut out by the number L of bits determined by the category number, and are outputted following the Huffman encoded category number. That is, the prediction error is divided into upper bit information and lower bit information and encoded respectively. Note that if the lower L bits of the prediction error are cut out as they are, overlapping codes will occur for positive and negative values, so if the prediction error is negative, 1 is subtracted in advance, and then the lower L bits are cut out.

Huffman encoding is a reversible encoding method that reduces the amount of codes on average by assigning codes with short word lengths to data with a high probability of occurrence and codes with long word lengths to data with low probability of occurrence. It is. Since the correlation between adjacent input data is high and there is a high probability that the prediction error will be around 0, highly efficient coding can be achieved by assigning a short code to the category number that represents the small range of the absolute value of the prediction error. realizable.

[0008]

[Problem to be Solved by the Invention] However, predictive coding obtains a decoded value by integrating the prediction errors, so when an error occurs in the encoded output, the influence of the error is accumulated and error propagation occurs. It was something that I had.

[0009]

[Means for Solving the Problems] A first high-efficiency encoding method of the present invention uses a sampled and quantized signal as input data, obtains a predicted value of the input data, and combines the input data and the predicted value. , a step of classifying the prediction error according to its size and outputting a category number representing the applicable category, and a predetermined upper limit value defining the range of the applicable category. and a predetermined lower limit value, the input data is divided using a predetermined value as a divisor to obtain a remainder; and the step of encoding and outputting the category number and the remainder. This is a characteristic feature.

[0010] A second high-efficiency encoding method of the present invention is
Data, which is a sampled and quantized signal, is used as an encoding input,
A step of forming a block by collecting a predetermined number of the input data, and performing a predetermined conversion on the data of the block.
a step of determining C coefficients and AC coefficients and quantizing each; a step of encoding the quantized DC coefficient data D to output DC encoded data; and encoding the quantized AC coefficient. and outputting AC encoded data, and the step of outputting the DC encoded data obtains a prediction error that is the difference between the data D and its predicted value, and categorizes the prediction error according to its size. The data D is divided by a divisor determined by the corresponding category to obtain a remainder, and the category number and the remainder are encoded to obtain DC encoded data. be.

[0011] Furthermore, the first high-efficiency code decoding method of the present invention obtains a prediction error that is the difference between data D to be encoded and its predicted value, and classifies the prediction error into categories according to its size. A category number is obtained, the data to be encoded is divided by a divisor determined by the corresponding category to obtain a remainder, and the category number and the remainder are encoded to obtain encoded data. A high-efficiency code decoding method using encoded data as input data, the method comprising the steps of decoding the encoded data to obtain the category number and the remainder, and obtaining a predicted value from output data that has already been decoded. a step of generating an offset of an integral multiple of the divisor using at least one of the upper limit value or the lower limit value of the prediction error range of the category indicated by the category number, a divisor determined from the category number, and the predicted value; and a step of adding the offset and the remainder to obtain new output data,
When a control signal is input from the outside, the step of obtaining a predicted value is to obtain a predicted value by performing a prediction method different from that used in encoding using the control signal, and the step of generating an offset is a step of obtaining a predicted value using the control signal. This method is characterized in that an offset is generated so that the output data obtained by decoding has a high correlation with the predicted value.

A second method of decoding a high-efficiency code according to the present invention includes the steps of using data as a sampled and quantized signal as an encoding input, and configuring a block by grouping a predetermined number of the input data; a step of performing a predetermined transformation on the data to obtain a DC component and an AC component and quantizing each; a step of encoding the quantized DC component data D to output DC encoded data; and outputting AC encoded data by encoding the encoded AC component, and the step of outputting the DC encoded data obtains a prediction error that is the difference between the data D and its predicted value, and the Classifying the prediction errors into categories according to their size to obtain a category number, dividing the data D by a divisor determined by the corresponding category to obtain a remainder;
A high-efficiency code decoding method using as input data encoded data of a high-efficiency encoding method characterized in that the category number and the remainder are encoded to obtain DC encoded data, the AC encoded data Decoded and quantized AC
a step of decoding the DC encoded data to obtain a quantized DC component; a step of dequantizing the quantized AC component to obtain an AC component; comprising a step of performing inverse transformation on a DC component to obtain decoded data in a block, and a deblocking step of decomposing the block to obtain and output decoded data in the same order as the encoded input data,
The step of obtaining the quantized DC component includes the step of obtaining the quantized DC component.
decoding encoded data to obtain the category number and the remainder; obtaining a predicted value from already decoded quantized data; and an upper or lower limit of a range of prediction errors for the category indicated by the category number. generating an offset that is an integral multiple of the divisor using at least one of the values, a divisor found from the category number, and the predicted value; and adding the offset and the remainder to generate new quantized data D. and when a control signal is input from the outside, the step of obtaining the predicted value performs a prediction method different from that at the time of encoding using the control signal, and the step of generating the offset includes The offset is generated so that the decoded data of the block being decoded is adjacent to the block being decoded and has the highest correlation with the decoded data of the block in which no error has occurred.

[0013]

[Operation] The first high-efficiency encoding method of the present invention has the above-described configuration and transmits the lower bit information of the input data, so error propagation does not necessarily occur, and transmission error resistance is improved compared to the conventional predictive encoding method. This is something that can be improved further.

The second high-efficiency encoding method of the present invention has the above-described configuration, so that when a transmission error occurs, the correlation of the AC component is also used to decode the DC component, so that even if a transmission error with a large error occurs, In some cases, it can be decoded accurately, and error resistance can be greatly improved.

Furthermore, the first high-efficiency code decoding method of the present invention has the above-described configuration, so that even if a transmission error with a large error occurs, a predicted value is obtained using decoded data without a transmission error, and a predicted value with a small error is obtained. If this is obtained, accurate decoding is possible.

Further, the second high-efficiency code decoding method of the present invention has the above-described configuration, so that even if a transmission error with a large error occurs in the DC component of a block, the correlation between decoded data including AC components of adjacent blocks is maintained. It is possible to obtain a highly accurate predicted value of the DC component using the method, and it is possible to perform decoding with small errors.

[0017]

[Embodiment] First, the encoding method of the present invention will be explained below.

1. A predicted value Pi of the input data Di is obtained, and this is subtracted from the input data Di to obtain a prediction error Si. Note that Di represents the i-th input data, and in the following, symbols to which the subscript i is attached represent data corresponding to Di.

2. The prediction error S using a predetermined classification table
Classify i according to its size. A category number Ji representing the range to which the prediction error Si belongs is determined. Therefore, if the upper and lower limits of the prediction error range indicated by the category number Ji are SXi and SNi, respectively, the following equation

[0020]

[Math 1]

##EQU1## holds true. Furthermore, in one-to-one correspondence with the category number Ji, the following formula

[0022]

[Math 2]

Predetermined divisor data OUi that satisfies the following is determined. 3. The input data Di is divided by the divisor data OUi to obtain a remainder Ei. That is, the following equation

[0024]

[Math 3]

##EQU1## holds true. However, Ni is a quotient. 4. The category number Ji and the remainder data Ei are encoded.

A specific example of the prediction error classification table is shown in Table 1.

[0027]

[Table 1]

(Table 1) includes not only the category number Ji and the corresponding prediction error range (SNi to SXi), but also
The word lengths Mi of the divisor data OUi and the remainder data Ei are shown in correspondence.

As explained above, the encoding method of the present invention encodes and transmits the category number, which is the upper bit information of the prediction error, and the residual data, which is the lower bit information of the input data. It is.

Next, this decoding method will be explained. In the encoding method of the present invention, the category number Ji and the remainder data Ei
is encoded and transmitted. In order to obtain data Di, divisor data OUi, remainder data Ei, and quotient data Ni are required as shown in equation (3). Category number J
Since there is a one-to-one correspondence between i and the divisor data OUi,
A category number-divisor data conversion table is prepared in advance, and by using this table, divisor data Ei can be obtained from the transmitted category number Ji. Since the remainder data Ei is being transmitted, if the quotient data Ni is determined, the data Di can be obtained.

A method for obtaining the necessary quotient data Ni will now be explained. By substituting the equation (3) into the equation (1) and eliminating the prediction error Si, we get the following equation

[0032]

[Math 4]

##EQU1## is obtained. Furthermore, the formula (Math. 4) is added to the formula (Math. 3
) and eliminate Di, we get the following equation

[0034]

[Math 5]

[0035] is obtained. The predicted value Pi is obtained from the decoded data Di, and SXi and SNi are the category number Ji.
Since there is a one-to-one correspondence, a conversion table is created in advance and can be found from the category number Ji by using this table. Furthermore, the quotient data Ni is an integer, and the difference (SXi - SNi)/OUi between the leftmost term and the rightmost term in Equation (Equation 5) is less than 1 according to Equation (Equation 2), so Equation (Equation 5) The quotient data Ni that satisfies can be uniquely determined. Therefore, the following formula is obtained by taking out the left-hand side of formula (Math. 5)

[0036]

[Math 6]

Either find the minimum integer Ni that satisfies the following equation, or use the following equation by taking the right-hand side of equation (5).

[0038]

[Math 7]

It is sufficient to find the maximum integer Ni that satisfies the following. That is, the quotient data Ni can be obtained using any of the equations (5), (6), and (7). formula(
The method using Equation 7) is the simplest because it only requires truncating the decimal part of the division result on the right side.

The quotient data Ni obtained from the above is expressed by the formula (Equation 3
), the data Di can be found, that is, decoded. The decoding method is summarized as follows. 1. The encoded data is decoded to obtain the category number Ji.
and the surplus data Ei is obtained. 2. A predicted value Pi is obtained from data Dk (k is an integer smaller than i) that has already been decoded. 3. From the category number Ji, the divisor data OUi, the upper limit value SXi of the prediction error range, or the lower limit value S of the prediction error range
Find Ni. 4. The quotient data Ni is obtained using the formula (Math. 7), the formula (Math. 6), or the formula (Math. 5). 5. Data Di is obtained using equation (3).

Since the remainder data Ei is less than the divisor data OUi, its code length Mi is (log2 OUi) bits. In order to minimize this, that is, to improve encoding efficiency, the minimum value that satisfies the equation (Equation 2) may be set as the divisor data OUi. Also, the divisor data OUi is 2
By raising the value to a power, the remainder calculation and division can be realized with an extremely simple circuit, and since the code length Mi is an integer value, the remainder data Ei can be efficiently encoded in binary. That is, the following equation

[0042]

[Math. 8]

The divisor data, the upper limit value, and the lower limit value of the prediction error may be set so as to satisfy the following. The prediction error classification table (Table 1) is created to satisfy the equation (Equation 8) when the word length of the input data Di is 8 bits.

(FIG. 1) shows an encoding device (FIG. 1(a)) and a decoding device (FIG. 1(b)) in a first embodiment using the first high-efficiency encoding method and decoding method of the present invention. )) is a block configuration diagram. The input data is a sampled and quantized analog video signal obtained by raster scanning an image.

In FIG. 1(a), 101 is an input terminal for data Di to be encoded, 102 is a prediction circuit for obtaining a predicted value Pi, and 103 is a prediction circuit for obtaining the predicted value P from the input data Di.
104 is a classification circuit that receives the prediction error Si and outputs the category number Ji; 105 is a conversion circuit that obtains the divisor data OUi from the category number Ji; 106 is the data Di 107 is the category number Ji and a first encoding circuit that encodes the remainder data Ei to obtain encoded data Ci. 108 is the encoding circuit. Data Ci output terminal, 10
9 encodes the category number Ji to generate encoded data C.
110 is a third encoding circuit that encodes the residual data Ei to obtain encoded data CEi; 111 connects the encoded data CJi and the encoded data CEi; This is a multiplexing circuit that obtains encoded data Ci.

In (FIG. 1(b)), 112 is an input terminal for the encoded data Ci, and 113 is the input terminal for the encoded data Ci.
114 is a conversion circuit that obtains the upper limit value SXi of the prediction error range of the category with number Ji and divisor data OUi, and 115 outputs quotient data Ni. A quotient data calculation circuit; 116 is a synthesis circuit for reproducing data Di from the divisor data OUi, the quotient data Ni and the remainder data Ei; 117 is an output terminal for the data Di; 118 is the already decoded data Dk(k is an integer smaller than i), a prediction circuit outputs a predicted value Pi of data Di, 1
Reference numeral 19 denotes a buffer memory for temporarily storing coded data Ci from the terminal 112, and 120 obtains coded data CJi multiplexed at the beginning of the coded data Ci from the buffer memory 119 and decodes it to obtain a category number Ji. 121 is a third decoding circuit that obtains encoded data CEi multiplexed with the remaining portion of encoded data Ci from the buffer memory 119 and decodes it to obtain residual data Ei; 122 is an adder circuit; , 123 is a subtraction circuit that subtracts the surplus data Ei from the output from the addition circuit 122;
24 converts the output from the subtraction circuit 123 into the divisor data OU.
Divide by i and use only the integer part of the result as quotient data Ni
125 is the divisor data OU.
126 is a multiplication circuit that multiplies i and the quotient data Ni to obtain an offset Fi, and 126 is an addition circuit that adds the remainder data Ei and the offset Fi to obtain new decoded data Di.

The operation of the encoding device and decoding device of this embodiment configured as described above will be explained below.

In the encoding device, input data Di from a terminal 101 is input to a prediction circuit 102, a subtraction circuit 103, and a remainder calculation circuit 106. The prediction circuit 102 performs previous value prediction and consists of only one register that holds the previous data Di-1, and the predicted value Pi=Di-1.
Outputs 1.

A subtraction circuit 103 subtracts the predicted value Pi from the data Di and outputs a prediction error Si. The classification circuit 104 receives the prediction error Si as input, classifies it according to its size according to Table 1, and outputs a category number Ji indicating the corresponding classification item. The conversion circuit 105 can be configured with a ROM (read only memory), and converts the divisor data OUi or the data M from the category number Ji according to (Table 1).
Output i. The remainder calculation circuit 106 divides the data Di by the divisor data OUi and outputs the remainder Ei. In Table 1, the divisor data OUi is 2 raised to the Mi power, so the remainder calculation circuit 106 uses the lower M of the data Di.
This can be realized with a simple gate circuit that extracts only i bits. In this case, the conversion circuit 105 may output the data Mi instead of the divisor data OUi.

The encoding circuit 109 uses the category number Ji
Huffman encoding (a type of entropy encoding) is performed and output in bit serial format. This output is encoded data CJi. Since the probability of occurrence of a prediction error whose category number is Ji is almost the same as the probability of occurrence of a prediction error whose category number is -Ji, in this example, the same Huffman code is assigned to these two categories, and which category The encoded data CJi is obtained by adding a 1-bit flag G indicating the Huffman code. When the category number is 0, the flag G is unnecessary. When the flag G=0, the category number is positive, and G=1
When , the category number is assumed to be negative.

The encoding circuit 110 uses the category number Ji
The number Mi of bits of the surplus data Ei shown in (Table 1) is determined by (Table 1), and the lower Mi bits of the surplus data Ei are output in bit serial format. This output is encoded data CEi
It is. The reason why only the lower Mi bits of the remainder data Ei are output is that the remainder data Ei can be expressed by Mi bits. The multiplexing circuit 111 connects the coded data CEi after the coded data CJi and outputs coded data Ci obtained from a terminal 118 in a bit serial format. The above operations realize encoding of the data Di.

In the decoding device, encoded data Ci from terminal 112 is temporarily stored in buffer memory 119.

First, the decoding circuit 120 starts with the buffer memory 1
While determining the code length from 19, the encoded data CJi
is read and decoded, and the code word length L1 and category number Ji of the read code are output. Buffer memory 119
receives the code word length L1 and outputs the coded data CJ.
The first position of the encoded data CEi following i is determined and set in the internal read pointer.

Subsequently, the decoding circuit 121 decodes the decoding circuit 120
The word length Mi of the residual data Ei shown in (Table 1) is determined from the category number Ji from the buffer memory 119, the coded data CEi of Mi bits is read from the buffer memory 119, data 0 is added to the upper part, and the word length Mi is determined in the bit parallel format. The residual data Ei that is data is reproduced.

The buffer memory 119 receives the word length Mi from the decoding circuit 121 and converts it into the encoded data CEi.
The head position of the next encoded data CJi following is determined, and the read pointer is updated in preparation for decoding the next data.

The conversion circuit 114 can be constructed of, for example, a ROM, and outputs the upper limit value SXi of the prediction error range and the divisor data OUi shown in Table 1 from the category number Ji.

The quotient data calculation circuit 115 calculates the residual data Ei, the SXi and the predicted value P from the prediction circuit 118.
The calculation shown on the right side of the equation (Equation 7) is performed using i, and the quotient data Ni, which is the integer part, is output.

The synthesis circuit 116 inputs the quotient data Ni, the divisor data OUi, and the remainder data Ei, performs the calculation shown in equation (3), reproduces the data Di, and outputs it from the terminal 117.

The prediction circuit 118 has the same configuration as the prediction circuit 102 in the encoding device, receives the data Di as input, and outputs the predicted value Pi. The above operations realize decoding of the data Di.

Next, the operation and effects of the present invention will be explained using specific data examples. Assume that the input data Di to be encoded from now on in the encoding device is 46, and the previous input data Di-1, which has already been encoded, is 35. The prediction circuit 102 outputs a predicted value Pi=Di-1=35. In the subtraction circuit 103, the prediction error Si=46-35
=11 is obtained. In the classification circuit 104, the category number J according to (Table 1) is determined from the prediction error Si=11.
i=4 is obtained.

In the conversion circuit 105, the category number Ji is converted to divisor data O which is a power of 2 according to (Table 1).
Output Ui or its exponent part data Mi=3. The remainder calculation circuit 106 converts the data Di into divisor data OUi=2M
Output the remainder data Ei=6 after dividing by i=8. Since the divisor data OUi is a power of 2, there is no need to perform normal division, and the remainder data Ei can be obtained by simply extracting only the lower Mi=3 bits of the data Di.

[0062] In the encoding circuit 109, the category number Ji is Huffman encoded. Ji=4 or Ji=
The Huffman code representing -4 is a 3-bit binary number “10”
1" (in the following, binary codes are shown enclosed in ""), the encoded code CJi for category number Ji = 4 will be "1010" and will be output in bit serial format. The 1-bit data "0" is a flag G indicating the positive/negative of the category number, indicating that the category number is positive.

In the encoding circuit 110, the lower Mi=3 bits of the residual data Ei=6 are outputted in a bit serial format to become encoded data CEi "110". In the multiplexing circuit 111, the encoded data CJi''1
The encoded data CEi "110" is added after "010", resulting in encoded data Ci="1010110", which is output from the terminal 118 in bit serial format starting from the left end (most significant bit).

In the decoding device, the encoded data from the terminal 112 is temporarily stored in a buffer memory 119 in a bit serial format. It is assumed that decoding has now been completed up to data Di-1 = 35, and data Di is now decoded from encoded data Ci.

The decoding circuit 120 reads encoded data Ci in bit serial format from the memory address indicated by the pointer in the buffer memory 119. The decoding circuit 120 can detect that the code length LJ of the encoded data CJi is 4 bits when reading up to "101" from the first bit of the encoded data Ci, and if Ji is not 0, the added 1 bit is detected. Read the flag G of. i.e. 4
All bits of encoded data CJi="1010" are read. Since the flag G=0 indicates that the category number Ji is positive, the decoding circuit 120 uses the category number Ji
=4 is output.

Next, the decoding circuit 121 receives the decoded category number Ji=4 and decodes M according to (Table 1).
Encoded data CEi="110" is obtained by reading data for i=3 bits from the buffer memory 119, and by converting this into parallel format and adding 0 to the upper bits, remainder data Ei=6 is obtained. ,Output. Note that the pointer in the buffer memory 119 is updated to indicate the first memory address of the next encoded data Ci+1.

According to (Table 1), the conversion circuit 114 converts the upper limit value SXi of the prediction error range in the category of category number Ji=4 to 15 and the divisor data OU which is a power of 2.
Outputs the exponent part Mi of i.

The quotient data calculation circuit 115 is the prediction circuit 11
The predicted value Pi=Di−1=35 from 8 and the upper limit S
After adding Xi=15, the remainder data Ei=6 is subtracted and further divided by divisor data OUi=2Mi=8 to obtain quotient data Ni=5 and output.

The synthesis circuit 116 multiplies the quotient data Ni=5 by the divisor data OUi=2Mi=8 to obtain an offset Fi.
By adding the remainder data Ei=6 to this, decoded data Di=46 is obtained and outputted from the terminal 117. This completes the decoding of the data Di.

By the way, since the divisor data OUi is a power of 2, the division circuit 124 does not need to perform normal division, and the quotient data Ni is obtained by removing the lower Mi=3 bits of the data Di, and the multiplication The circuit 125 does not need to perform normal multiplication, and adds Mi to the lower part of the quotient data Ni.
By simply adding 0 bits, the offset Fi, which is the multiplication result, can be obtained. Furthermore, in the adder 126, since the remainder data Ei which is one input has 0 except for the lower Mi bits, and the offset Fi which is the other input has its lower Mi bits 0, there is no need to perform normal addition.
It is only necessary to replace the lower Mi bits of the offset Fi with the lower Mi bits of the remainder data Ei. Therefore divider 1
24. The multiplier 125 and the adder 126 are realized by a very simple circuit, that is, a circuit that replaces the lower Mi bits of the output of the adder 123 with the lower Mi bits of the remainder data Ei and outputs this as decoded data Di. can.

Next, let us consider the case where the previous data Di-1 = 36 was decoded to 31, a value with a relatively small error, due to a transmission error. Predicted value Pi=Di-1
Therefore, conventional predictive coding always causes error propagation. However, when decoding is actually performed using the high-efficiency encoding method of the present invention, a correct result of Di=46 is obtained. In other words, no error propagation occurs. This is the formula (
The quotient data Ni is obtained using Equation 7) or Equation (Equation 5) or Equation (Equation 6), but the predicted value Pi used in these equations is
This is because correct quotient data Ni can be obtained even if there is an error within a certain range from the predicted value at the time of encoding. According to the formula (Equation 7), it can be seen that when Di=46, if the predicted value Pi is between 31 and 38, correct quotient data Ni=5 can be obtained.

As described above, according to this embodiment, error propagation does not necessarily occur, so transmission error resistance can be greatly improved. Further, by setting the divisor data to a power of 2, the encoding device of the present invention can be realized with a circuit scale as small as that of a conventional predictive encoding device.

In the embodiments described above, the residual data is coded by cutting out the lower Mi bits thereof as a simple binary code, but error resistance can be further improved by converting the residual data to a Gray code and then coding. This is because the Gray code can reduce the error due to a 1-bit error to 1 level. Exceptionally, the upper limit value of residual data becomes the lower limit value,
Or vice versa, but in this case, it can be corrected by adding 1 or -1 to the quotient data Ni.

If the decoded value used for prediction has a fairly large error due to a transmission error, the same prediction method used during encoding will only yield a predicted value Pi with a large error, and a correct decoded value will no longer be obtained. However, if a predicted value Pi' with a small error is obtained by a prediction method using another decoded value that is not affected by transmission errors, that is, a prediction method different from that used during encoding, correct decoding is possible. This is because the encoding method of the present invention encodes and transmits the upper bit information of the prediction error (category number Ji) and the lower bit information of the data to be encoded (remainder data Ei). This is because correct decoded data Di can be obtained by finding the quotient data Ni, which is one unknown quantity. In particular, when the divisor data OUi is large, the range in which the quotient data Ni exists becomes narrow, making it easy to determine it.

A second embodiment of the decoding apparatus using the decoding method using the predicted value Pi', that is, the first high-efficiency code decoding method of the present invention, will be described. First, this decoding method will be explained. Note that the encoded data is the encoded data Ci output from the encoding apparatus of the first embodiment.

The input data in the first embodiment is an image signal, and at the time of encoding, previous value prediction is performed in the horizontal direction of the image to obtain a predicted value Pi. The image signal is transmitted in two-dimensional direction (
In the case of a video, there is a correlation in the three-dimensional direction including the time axis direction), for example, data Di is correlated with the decoded data Di-H of the previous line (where H represents the number of pixels in one line). When the correlation is strong, that is, the vertical correlation is strong, the predicted value Pi' (=Di-
H ) can be obtained. Therefore, when the predicted value Pi' with a small error is obtained, the data Di and the predicted value P
The quotient data Ni is determined so that the error with i' is small,
That is, the following equation

[0077]

[Math. 9]

Find Ni that satisfies
By substituting , correct data Di can be reproduced with high probability.

Therefore, a circuit is provided which detects that a large error has occurred in the decoded data due to a transmission error, and detects that the vertical correlation of the data Di is strong, and generates a control signal. In normal times when no control signal is generated, decoding is performed using the predicted value Pi according to the same prediction method as in encoding, as in the decoding device of the first embodiment, and when the control signal is generated, the prediction value Pi is used in the same way as in the decoding device of the first embodiment. By performing the decoding method using the predicted value Pi' based on a different prediction method, a decoding device that is more resistant to transmission errors can be realized.

A decoding apparatus according to a second embodiment using the high-efficiency code decoding method of the present invention will be described next. This decoding device replaces the prediction circuit 118 and quotient data calculation circuit 115 in the decoding device (FIG. 1) with the prediction circuit shown in (FIG. 2) and the quotient data calculation circuit shown in (FIG. 3), respectively. The overall configuration diagram of the decoding device is omitted.

In (FIG. 2), 201 is a delay circuit consisting of one register that holds the previous decoded data and causes one stage of data delay; 202 is the register 20;
A delay circuit 203 takes the output of the delay circuit 201 as an input and causes a data delay of (H-1) stages, and a delay circuit 203 outputs the output of the delay circuit 201 as a predicted value Pi when the control signal is not generated, and only when the control signal is generated. This is a switch that outputs the output of the delay circuit 202 as a predicted value Pi'.

[0082] In normal times when the control signal is not input, the switch 203 selects the horizontal predicted value Pi=D, which is the same as that at the time of encoding.
i-1 and performs the same operation as the prediction circuit 118 in FIG. 1. When the control signal is generated, prediction different from that during encoding, that is, previous value prediction in the vertical direction, is performed to output a predicted value Pi'=Di-H.

In (FIG. 3), 301 indicates the upper limit value SXi of the prediction error range and the predicted value P from the prediction circuit shown in (FIG. 2).
302 is a switch that selects the output of the adder circuit 301 when the control signal is not generated, and selects and outputs the predicted value Pi' when the control signal is generated; 303 is the switch that selects and outputs the predicted value Pi'; A subtraction circuit that subtracts the remainder data Ei from the output of the switch 303; 304 a division circuit that divides the output of the subtraction circuit 303 by divisor data OUi; and 305 a division circuit that divides the output of the division circuit 303 when the control signal is not generated. This is a rounding circuit that performs truncation processing and rounds off processing when the control signal is generated.

When the control signal is not generated, the predicted value of the input is Pi, which is the same as during encoding, the output of the addition circuit 301 is input to the addition circuit 303 via the switch 302, and the rounding circuit 305 performs truncation processing. Therefore, the same processing as the quotient data calculation circuit 115 in FIG. 1 is performed. When the control signal is generated, the input predicted value is the predicted value Pi' which is predicted in the vertical direction.
02, the predicted value Pi' is input to the rounding circuit 305.
is rounded off, so the error between the decoded output data Di and the predicted value Pi' becomes the smallest, that is, the equation (
Quotient data Ni satisfying Equation 9) is output.

Using the obtained quotient data Ni, the synthesis circuit 116 (FIG. 1) performs the calculation of the equation (1) to obtain decoded data Di, and outputs the decoded data Di. As described above, according to the present embodiment, only when decoded data with a large error occurs due to a transmission error and a predicted value Pi' with a small error can be obtained by a prediction method different from that used during encoding, the first embodiment is applied. Since the decoded data is obtained by a decoding method different from that of the decoding device, that is, by determining and decoding the quotient data Ni such that the correlation with the predicted value Pi' is high, the data can be correctly decoded with a higher probability. , the error tolerance can be significantly improved compared to the conventional method.

Furthermore, the data Dr between the data Dm that caused a transmission error and the data Di decoded by the control signal
(However, m<r<i) can be correctly decoded by using data Di and decoding in the direction in which r decreases, that is, in the reverse direction. If this decoding method is used in combination, the error propagation area can be made smaller. It is possible to do so.

Decoding in the reverse direction, that is, decoding data Di from data Di+1, is possible by the following method. That is, the following equation

[0088]

[Math. 10]

The quotient data Ni is obtained so as to satisfy the following equation (
The quotient data Ni obtained from Equation 3), the divisor data OUi obtained from the category number Ji, and the transmitted remainder data Ei
By substituting , data Di can be found.

(FIG. 4) shows an encoding apparatus (FIG. 4) in a third embodiment using the second high-efficiency encoding method of the present invention and the second high-efficiency code decoding method that is the inverse transformation thereof. a)
) is a block configuration diagram of the decoding device (FIG. 4(b)). As in the first and second embodiments, the input data V is obtained by sampling and quantizing an analog video signal obtained by raster scanning an image.

In FIG. 4(a), 401 is an input terminal for the data V to be encoded, and 402 is a rectangular area in which the input data is rearranged and divided into 8 pixels in the horizontal direction and 8 pixels in the vertical direction. Data DDi for each block (
h) (where h is an integer from 0 to 63), a blocking circuit 403 performs 8-order DCT on the data DDi(h) in the horizontal and vertical directions, respectively, and
A DC that outputs DCT coefficients consisting of one DC coefficient DCi (subscript i represents block number i) and 63 AC coefficients ACi(k) (k is an integer from 1 to 63).
T circuit 404 is a quantization circuit that quantizes the DC coefficient DCi with a predetermined quantization step size Qd (that is, divides by Qd and rounds) to obtain data Di; 405 is a quantization circuit (see FIG.
), an encoding circuit 406 encodes the data Di to obtain encoded data Ci, and 406 quantizes the AC coefficient ACi(k) with a predetermined quantization step size to generate data Bi(k). 407 is an encoding circuit that performs two-dimensional Huffman encoding on the data Bi(k) from the quantization circuit 406 and outputs encoded data Ai; 408 is an encoding circuit that outputs the encoded data Ai and the encoded data Ci;
A multiplexing circuit 409 outputs the coded data CCi multiplexed with the coded data CCi, and 409 is a terminal that outputs the coded data CCi.

In (FIG. 4(b)), 410 is an input terminal for the coded data CCi, and 411 is the input terminal for the coded data CCi.
412 is a decoding circuit for decoding the encoded data Ci to obtain data Di; 413 is a decoding circuit for decoding the encoded data Ai to obtain data Di; A decoding circuit 414 obtains Bi(k), a dequantization circuit 414 performs dequantization by multiplying the data Di by the quantization step size Qd to obtain decoded data DCi' of DC coefficients, and 415 a decoding circuit 41
416 is an inverse DCT circuit that performs inverse transformation of the DCT circuit 403; 417 is a delay circuit for timing adjustment, and 418 is a block-by-block image data D by adding the inverse DCT output that has passed through the delay circuit and the decoded data DCi'.
an addition circuit for obtaining Di'(h); 419 is a deblocking circuit for rearranging the image data DDi' in units of blocks to obtain image data in the same data arrangement as before encoding;
420 is decoded image data V from the reverse block circuit
' is the output terminal of '.

The operation of the encoding device and decoding device of this embodiment configured as described above will be explained below.

In the encoding device, image data V from a terminal 401 is input to a blocking circuit 402 . The blocking circuit 402 rearranges the image data and outputs data DDi(h) for each block. DCT
The circuit 403 performs 8-order two-dimensional DCT on the data DDi(h) for each block, and calculates one DC coefficient DCi.
ACi(k) consisting of 63 AC coefficients is output. The quantization circuit 404 quantizes the DC coefficient DCi with a predetermined quantization step size Qd (that is, divides it by Qd and rounds it) and outputs quantized data Di. Encoding circuit 40
5 encodes the data DCi in the same way as the encoding device shown in FIG. 1 and outputs encoded data Ci. The difference from the encoding device shown in FIG. 1 is that the input is not the quantized value of the image data, but the DC coefficient (
The point is that it is quantized data (equal to the average value). The same symbol Di as in FIG. 1 is used to clarify the correspondence. The quantization circuit 406 converts the AC coefficient ACi(k) into a predetermined quantization step size Qai(k) determined for each coefficient.
quantize with k). The encoding circuit 407 is the quantization circuit 40
6 is subjected to two-dimensional Huffman encoding and outputs encoded data Ai. A multiplexing circuit 408 multiplexes the encoded data Ci and the encoded data Ai and outputs encoded data CCi from a terminal 409.

The decoding device can be realized with a block configuration that performs inverse transformation of the encoding circuit shown in FIG. 4(a), but it is possible to perform correct decoding with a higher probability even when a transmission error occurs that causes a decoded value with a large error. In order to do this, the block configuration shown in FIG. 4(b) is adopted.

[0096] In the decoding device, encoded data CCi from terminal 410 is input to separation circuit 411. A separation circuit 411 separates the coded data CCi into coded data Ci and coded data Ai. The decoding circuit 413 decodes the encoded data Ai that has been subjected to two-dimensional Huffman encoding to obtain quantized AC coefficients Bi(k). The inverse quantization circuit 415 performs inverse quantization by multiplying the data Bi(k) by a predetermined quantization step Qai(k) determined for each coefficient to obtain an AC coefficient ACi'(k). The inverse DCT circuit 416 performs inverse DCT with the DC coefficient input as a provisional value 0 and the AC coefficient input as the ACi'(k) to obtain provisional decoded data (AC component data) DTi of the block.

The decoding circuit 412 is basically the same as the decoding device of the second embodiment, and the decoding circuit 412 is basically the same as the decoding device of the second embodiment.
i is decoded and data Di, which is a quantized DC coefficient, is output. The difference from the decoding circuit of the second embodiment is that the configuration of the prediction circuit is not as shown in (Fig. 2), but as shown in (Fig. 5).
The point is that it is shown in the figure below. During normal decoding without transmission errors, this prediction circuit is used as the prediction circuit 11 in (FIG. 1).
8 and (Fig. 2), that is, the same predicted value Pi = Di-1 (This is the DC coefficient of the i-th block that has already been decoded, and this block (i- 1) is located to the left of block i in the image), but if a large error is detected and a control signal is input from the outside, a prediction different from that used during encoding is performed and the prediction is Output the value Pi'.

The predicted value Pi' is obtained from the data of the block (i-H) immediately above and adjacent to the block i currently being decoded. As in the second embodiment, the predicted value P
i'=Di-H' (where H is the number of blocks in the horizontal direction of the image), but in this embodiment, in order to improve the accuracy of the predicted value, decoded image data DDi-H
The predicted value Pi' is calculated from '. This quantized D
A method for determining the predicted value Pi' for the C coefficient Di will be explained.

Eight pixel data DDi'(q) of block i adjacent to the boundary with block (i-H) (however, q=q
1, q2, . ．． ．． , q8) have a short distance from the block (i-H), the predicted values pi(q) for these can be obtained with higher accuracy than the pixel data DDi-H' in the block (i-H). The pixel data DDi'(q) is expressed as the sum of the DC component DCi'=Di·Qd of the block and the AC component DTi(q), and the pixel data DD
If the difference or error between i'(q) and the predicted value pi(q) is d, then the following equation

[0100]

[Math. 11]

[0101] holds true. By making the error d small and setting it to 0, an approximate value of the quantized DC component Di, that is, a predicted value Pi' is obtained, and the following equation is obtained.

[0102]

[Math. 12]

[0103] holds true. In this embodiment, in order to simplify the circuit configuration, pre-prediction in the vertical direction is performed to obtain the predicted value pi(q). 8 of block i
pixel data DDi'(q) (where q=q1, q2,
．． ．． ．． , q8) respectively adjacent blocks (i-H)
If the decoded data of 8 pixels within is expressed as DDi-H'(q), these are equal to the predicted value pi(q) in pre-prediction. Also, the predicted value Pi' can be obtained by simply calculating the formula (Equation 12) for one q, but in order to further improve the accuracy, the average value of (pi (q) - DTi (q)) for eight q's is calculated. , divided by the quantization step size Qd is set as the predicted value Pi'. The configuration and operation of the prediction circuit that obtains this predicted value Pi' will be explained using (FIG. 5).

In FIG. 5, 501 is a delay circuit which inputs data Di and outputs the previous data Di-1 as a predicted value Pi. 502 is a delay circuit which inputs the decoded data DDi' and calculates the predicted value pi(q)=D
Output Di-H'(q). A subtraction circuit 503 calculates the difference between the predicted value pi(q) and the data DTi(q). An averaging circuit 504 outputs the average value of the differences for the eight q, and a quantization circuit 505 divides this by the quantization step size Qd (that is, performs quantization) and outputs the predicted value Pi'. do. 506 is a switch which outputs the predicted value Pi in normal times when the control signal is not input;
However, when the control signal is input, the predicted value Pi' is output.

[0105] As a result, the decoding circuit 412 outputs decoded data Di with less error even when a transmission error occurs. Note that in order to obtain the predicted value Pi', it is necessary to decode the AC coefficients and perform inverse DCT before decoding the DC coefficients, so the decoding circuit 4
12 has a delay circuit for timing adjustment inside. The inverse quantization circuit 414 multiplies the data Di by the quantization step size Qd and outputs DC coefficient data DCi'. The adder circuit 418 adds the data DTi that has passed through the delay circuit 417 for timing adjustment and the data DCi', and outputs decoded image data DDi' for each block. The reverse block circuit 419 receives the image data DDi.
'(h) is rearranged to return the data to the pre-encoded order, and the decoded image data V' is output from the terminal 420.

As described above, according to this embodiment, even if decoded data Di with a large error occurs due to a transmission error, correct decoded values of image data can be obtained with a high probability by using the correlation of pixel data between blocks. , the error tolerance can be significantly improved compared to the conventional method.

Although reversible encoding was performed in the above embodiment, an irreversible encoding method is also possible, for example, where the prediction error is large, by rounding and transmitting the lower bits of the residual data Ei. In this case, in order to match the predicted values in the encoding device and the decoding device, it is necessary to provide a local decoding device within the encoding device and create a predicted value from the decoded data. Of course, even in reversible encoding as in this embodiment, a configuration in which the local decoding device is provided is possible.

Furthermore, the present invention is not limited to these embodiments, and various prediction methods can be applied, and arithmetic coding etc. can also be applied as an entropy encoding method. In addition to DCT, various conversion methods and various encoding methods such as mean value separation vector quantization can be applied.

[0109]

[Effects of the Invention] The present invention provides a high-efficiency encoding method characterized by transmitting upper bit information of a prediction error and lower bit information of input data, and a decoding method that performs inverse transformation thereof, thereby reducing the encoding efficiency. It is possible to significantly improve transmission error tolerance without causing any problems, and its practical effects are significant.

[Brief explanation of drawings]

FIG. 1 is a block configuration diagram of an encoding device and a decoding device in a first embodiment using a first high-efficiency encoding method and its decoding method of the present invention.

FIG. 2 is a block configuration diagram of a prediction circuit in a decoding device of a second embodiment using the first high-efficiency code decoding method of the present invention.

FIG. 3 is a block configuration diagram of a quotient data calculation circuit in a decoding device of a second embodiment using the first high-efficiency code decoding method of the present invention.

FIG. 4: Blocks of an encoding device and a decoding device in a third embodiment using the second high-efficiency encoding method of the present invention and the second high-efficiency code decoding method of the present invention, which is an inverse transformation thereof; FIG.

FIG. 5 is a block configuration diagram of a prediction circuit in a decoding device according to a third embodiment of the present invention.

[Explanation of symbols]

101 Input terminal 102 of data Di to be encoded
Prediction circuit 103 Subtraction circuit 104 Classification circuit 105 Conversion circuit 106 Remainder calculation circuit 107 Encoding circuit 108 Output terminal 112 of encoded data Ci Input terminal 113 of encoded data Ci Decoding circuit 114 Conversion circuit 115 Quotient data calculation circuit 116 Synthesis circuit 117 Output terminal 118 for decoded data Di
prediction circuit

Claims (7)

[Claims] 1. A step of taking a sampled and quantized signal as input data, obtaining a predicted value of the input data, and determining a prediction error that is a difference between the input data and the predicted value; a step of classifying according to the size and outputting a category number representing the applicable category; A highly efficient encoding method comprising: dividing input data to obtain a remainder; and encoding and outputting the category number and the remainder. [Claim 2] The divisor is a value obtained by adding 1 to the difference between the upper limit value and the lower limit value, and the upper limit value and lower limit value of each category are set so that the divisor is a power of 2. The high efficiency encoding method according to claim 1. 3. The step of encoding and outputting the category number and the remainder comprises the steps of entropy encoding the category number and converting the remainder into a variable length code according to the size of the divisor. The high-efficiency encoding method according to claim 1, characterized in that: 4. The highly efficient encoding method according to claim 1, wherein the step of encoding and outputting the category number and the remainder comprises the step of converting the remainder into a Gray code. 5. Obtain a prediction error that is the difference between the data D to be encoded and its predicted value, classify the prediction error into categories according to the size, obtain a category number, and use a divisor determined by the corresponding category to calculate the prediction error. Decoding a high-efficiency code using as input data the encoded data obtained by a high-efficiency encoding method in which data to be encoded is divided to obtain a remainder, and the category number and the remainder are encoded to obtain encoded data. The method comprises: decoding the encoded data to obtain the category number and the remainder; obtaining a predicted value from output data that has already been decoded; and calculating a prediction error for the category indicated by the category number. generating an offset of an integral multiple of the divisor using at least one of the upper limit value or the lower limit value of the range, the divisor found from the category number, and the predicted value; and adding the offset and the remainder to create a new offset. When a control signal is input from the outside, the step of obtaining a predicted value performs a prediction method different from the one used during encoding using the control signal to obtain the predicted value, and offsets the predicted value. A high efficiency code decoding method, wherein the step of generating generates an offset so that the output data obtained by decoding using the control signal has a high correlation with the predicted value. 6. A step of using data as a sampled and quantized signal as an encoding input, forming a block by collecting a predetermined number of the input data, and performing a predetermined transformation on the data of the block to obtain DC and AC components. and quantizing each of them; encoding the quantized DC component data D to output DC encoded data; and encoding the quantized AC component to output AC encoded data. and outputting the DC encoded data, the step of outputting the DC encoded data obtains a prediction error which is the difference between the data D and its predicted value, and classifies the prediction error into categories according to the size thereof. A number is obtained, the data D is divided by a divisor determined by the applicable category to obtain a remainder, and the category number and the remainder are encoded and DC
A highly efficient encoding method characterized by obtaining encoded data. 7. A step of using data as a sampled and quantized signal as an encoding input, configuring a block by collecting a predetermined number of the input data, and performing a predetermined transformation on the data of the block to obtain DC and AC components. and quantizing each of them; encoding the quantized DC component data D to output DC encoded data; and encoding the quantized AC component to output AC encoded data. and outputting the DC encoded data, the step of outputting the DC encoded data obtains a prediction error which is the difference between the data D and its predicted value, and classifies the prediction error into categories according to the size thereof. A number is obtained, the data D is divided by a divisor determined by the applicable category to obtain a remainder, and the category number and the remainder are encoded and DC
A high-efficiency code decoding method that uses encoded data as input data of a high-efficiency encoding method characterized by obtaining encoded data, the method comprising decoding the AC encoded data to obtain a quantized AC component. decoding the DC encoded data to obtain a quantized DC component; dequantizing the quantized AC component to obtain an AC component; performing inverse transformation on the block to obtain decoded data in the block;
a deblocking step of decomposing the block to obtain and output decoded data in the same order as the encoded input data, and obtaining the quantized DC component,
decoding the DC encoded data to obtain the category number and the remainder; obtaining a predicted value from already decoded quantized data; and an upper limit value of the prediction error range of the category indicated by the category number. or at least one of the lower limit value and a divisor determined from the category number,
and the predicted value to generate an offset that is an integer multiple of the divisor, and the step of adding the offset and the remainder to obtain new quantized data D. In this case, the step of obtaining the predicted value uses the control signal to perform a prediction method different from that used during encoding, and the step of generating the offset includes the step of obtaining the predicted value using the control signal so that the decoded data of the block being decoded is the block being decoded. A method for decoding a high-efficiency code, the method comprising: generating an offset so as to have the highest correlation with decoded data of a block adjacent to the block in which no error has occurred.