Variable length encoding method and variable length decoding method

Variable length coding method and variable length decoding method

Technical field

The present invention relates to a variable-length encoding method and a variable-length decoding method for performing frequency conversion on image data of a moving image in units of blocks having a predetermined size, and encoding the obtained coefficient values in each block.

Background technique

The moving image coding process generally uses the spatial and temporal redundancy of the moving image to compress the amount of information. Among them, a method that uses redundancy in the space direction generally uses conversion to a frequency region, and a method that uses redundancy in the time direction uses an inter-image predictive coding process.

In order to improve the coding efficiency of the conventional MPEG-4 moving picture coding method (for example, refer to Non-Patent Document 1), the moving picture coding method in the current standardization work performs frequency conversion in units of blocks of 4×4 pixels. Perform quantization to generate coefficient values. Then, scan from the DC component to the high-frequency component, and create the number of coefficients R (Run, also referred to as'R' below) with a continuous value of '0' and the subsequent coefficient value L (Level, also referred to below as' The combination of L') forms a combination column of (R, L). After converting the (R, L) into a code number using a predetermined code table, a variable length coding (VLC: Variable Length Coding) table is used to convert the code number into a VLC code to perform coding. In the code table at this time, the higher the frequency of occurrence, the smaller the assigned code number. For example, the combination of small R and L has a high frequency of occurrence, so a small code number is assigned. In addition, there is also a VLC table (ISO/IEC 14496-2: "Information technology--Coding of audio-visual objects--Part 2: Visual" 7.4.1, pp. 119-120, 1999.12).

However, in the above-mentioned conventional method, if the continuous number R and the coefficient value L of coefficients having a coefficient value of "0" become larger, the coding length becomes longer, resulting in a decrease in coding efficiency. Generally, since the coefficient value L of the low-frequency component value has a large value, the coding efficiency when encoding the low-frequency sufficient value is significantly reduced.

That is, according to the frequency of occurrence, a unique variable-length code is assigned to a pair of R and L of a VLC table. As a result, in order to obtain a coefficient value L with a large value, it is often converted into a variable-length code with a very long code length. Variable length encoding. In addition, even when R and L are coded separately (one-dimensional coding of L), when one variable-length coding table is used, the same problems as when R and L are used for coding will occur.

Summary of the invention

In view of the above-mentioned problems, an object of the present invention is to provide a variable length coding method and a variable length decoding method that can improve coding efficiency when coding the coefficient value L.

In order to achieve the above-mentioned object, the variable-length coding method according to the present invention performs frequency conversion on the image data of a moving image in units of blocks having a predetermined size, and encodes the coefficient values in each block obtained, and is characterized in that it includes : The coefficient value scanning step is to scan the coefficient values in the block in a prescribed order; and the coding step is to switch multiple tables used in encoding, and the coefficient values scanned through the coefficient value scanning step are in a prescribed order. Encode to make it a variable length encoding.

In this way, variable-length coding with a coding length adapted to the coefficient value can be adapted to each table, so coding efficiency can be improved. That is, when the coefficient value is small, use a certain table for encoding to make the coding length shorter than the variable-length coding of other tables. When the coefficient value is large, use another table for coding, so that the coding length is shorter than that of other tables. Variable-length coding switches the table according to the coefficient value, so that the coding length can be drastically shortened.

Among them, the switching direction of each table can also be characterized as a single direction. In this way, the coefficient value is used to prevent frequent table switching and reduce the number of table switching. Therefore, coding efficiency can be improved. For example, because the working space of the memory is limited, it is generally only the table that is used subsequently in the working space. In this case, every time the table is switched, it takes time to read the next table from the ROM and expand it into the work space. Therefore, it takes a lot of time to encode the subsequent coefficient values. Therefore, by using one direction to limit the number of table switching times, the effect of shortening the time for encoding subsequent coefficient values as a whole can be exerted.

In addition, in the encoding step, a structure characterized by switching the multiple tables within a block and encoding may also be adopted, or a coefficient other than the one-dimensionalized '0' may be adopted. The value is the structure of the feature.

In addition, a preferred feature is that the coding is non-arithmetic coding. In this way, once the table to be used for encoding is determined, encoding can be performed only by referring to the table, making it a variable-length encoding.

The preferred structure of each table is to make the rate of change of the coding length of the relative coefficient value different, so that the coding length of the minimum value of the coefficient value becomes longer in the order of the number assigned to each table, and the maximum value of the coefficient value is increased. The code length does not become longer in the order of the sequence number. Another preferred structure of the respective tables is that the increase rate of the code length relative to the increased part of the coefficient value decreases in the order of the number assigned to the respective tables. In this way, it is possible to allocate a range in which the coding length becomes shorter for each table, so that the coding efficiency can be reliably improved.

In addition, in the encoding step, it is preferable to switch the tables according to a limit value relative to the absolute value of the coefficient value set in advance. In this way, the switching time of the table can be simply judged, and the coding efficiency can be improved.

The coefficient value scanning step preferably scans the coefficient values in order from high-frequency components to low-frequency components. In this way, the absolute value of the coefficient has a tendency to gradually increase from around '1', so it is easy to determine the table used to encode the initial coefficient value in the block, or the structure of each table can be simply determined, or the limit value can be easily determined .

In the encoding step, when the absolute value of the coefficient of the coding target exceeds the limit value, it is preferable to switch from the table for encoding the coefficient of the coding target to a table with a sequence number greater than the sequence number assigned to the table, and to encode subsequent coefficient values. In this way, when encoding subsequent coefficient values, the encoding length can be shortened, so that the encoding efficiency can be improved.

The variable-length decoding method according to the present invention performs frequency conversion on the image data of a moving image in units of blocks having a predetermined size, encodes the coefficient values in each block obtained, and then performs the generated variable-length encoding The decoding is characterized by comprising: a decoding step of switching multiple tables used in decoding, and decoding the variable-length codes in the respective blocks into coefficient values in a prescribed order; and a decoding step based on the coefficients generated in the decoding step Value, a coefficient generation step for generating coefficient values in the block. In this way, the code that has been highly compressed and coded can be decoded correctly.

Wherein, the switching direction of each table is one direction as a feature.

In the decoding step, switching the multiple tables within a block and performing encoding may be a feature, and the coefficient value may be a coefficient value other than one-dimensionalized '0' as a feature.

It can also be characterized as whether the decoding is non-arithmetic decoding.

The tables may also be characterized by the following structure, which makes the rate of change of the coding length of the relative coefficient value different, so that the coding length of the minimum value of the coefficient value becomes longer in the order of the number assigned to each table, and the coefficient value The encoding length of the maximum value does not become longer in the order of the sequence number.

Each of the tables may also feature the increase rate of the code length relative to the increase of the coefficient value as the order of the number assigned to the tables becomes smaller.

The decoding step may also be characterized by switching the tables based on a limit value relative to the absolute value of the coefficient value set in advance.

In the coefficient generation step, the coefficient values may be scanned sequentially from high-frequency components to low-frequency components as features.

The encoding step may also be characterized by the following method: when the absolute value of the decoded coefficient exceeds the limit value, the table used when decoding the variable-length code of the decoding target is switched to a sequence number greater than the sequence number assigned to the table The following variable-length code is decoded into coefficient values.

The present invention can not only realize the variable-length encoding method and variable-length decoding method, but also realize the variable-length encoding device and the variable-length encoding device and the variable-length encoding device using the steps contained in the variable-length encoding method and the variable-length decoding method as the technical method The variable-length decoding device implements a moving image encoding method and a decoding method using the steps included in the variable-length encoding method and the variable-length decoding method, and implements a program that causes a computer to execute these steps. Of course, the program can be distributed through recording media such as CD-ROM and transmission media such as the Internet.

Description of the drawings

FIG. 1 is a block diagram showing the functional configuration of an encoding device using the variable-length encoding method and the moving image encoding method according to Embodiment 1 of the present invention.

Fig. 2 is a block diagram showing the detailed functional structure of the variable length coding unit shown in Fig. 1.

FIG. 3 is a schematic diagram illustrating the process of executing the RL column generating unit shown in FIG. 2.

4 is a schematic diagram illustrating the RL column generated by the RL column generating unit and the arrangement replacement process of the execution arrangement replacement unit shown in FIG. 2.

Fig. 5 is a diagram showing an example of a code table held by the table storage unit shown in Fig. 2.

Fig. 6 is a diagram showing an example of a variable-length coding table held by the table storage unit shown in Fig. 2.

FIG. 7 is a schematic diagram illustrating another example of the RL column generated by the RL column generating unit and the arrangement replacement process of the arrangement replacement unit shown in FIG. 2.

8 is a block diagram showing the functional configuration of a decoding device using the variable-length decoding method and the moving image decoding method according to Embodiment 2 of the present invention.

Fig. 9 is a block diagram showing a detailed functional structure of the variable length decoding unit shown in Fig. 8.

FIG. 10 is a schematic diagram illustrating the RL column generated by the code conversion unit and the arrangement replacement process performed by the arrangement replacement unit shown in FIG. 2.

Fig. 11 is a schematic diagram illustrating the processing performed by the coefficient generating unit shown in Fig. 9.

12 is a schematic diagram illustrating another example of the RL column generated by the code conversion unit and the arrangement replacement process performed by the arrangement replacement unit.

Fig. 13 is a block diagram showing the configuration of an encoding apparatus according to the third embodiment of the present invention.

Fig. 14 is a block diagram showing the internal configuration of a variable length decoding unit according to the third embodiment.

Fig. 15 is a schematic diagram showing a coefficient block output from the quantization unit of the third embodiment.

Fig. 16 is a schematic diagram showing the RL column output from the RL column generating unit of the third embodiment.

FIG. 17 is a transition diagram showing a switching method of the probability table in the third embodiment.

FIG. 18 is a schematic diagram showing the content of the probability table of the third embodiment.

FIG. 19 is a block diagram showing the configuration of an image decoding device according to the fourth embodiment of the present invention.

Fig. 20 is a block diagram showing the internal configuration of a variable length decoding unit according to the fourth embodiment.

Fig. 21 is a schematic diagram showing an example of a binary table.

22 is a block diagram showing the functional configuration of an encoding device using the variable-length encoding method and the moving picture encoding method according to Embodiment 5 of the present invention.

Fig. 23 is a block diagram showing a detailed functional structure of the variable length coding unit shown in Fig. 22.

24 is a schematic diagram illustrating an example of the L column and the R column generated by the R column·L column generating unit shown in FIG. 23.

FIG. 25 is a schematic diagram showing an example of the structure of each variable-length coding table held in the storage unit shown in FIG. 23. FIG.

FIG. 26 is a schematic diagram showing an example of the structure of a limit value table held by the storage unit shown in FIG. 23.

Fig. 27 is a flowchart showing a variable-length code allocation process performed by the code allocation unit shown in Fig. 23;

Fig. 28 is a diagram showing the relationship between a variable-length coding table used in encoding and a limit value.

Fig. 29 is a schematic diagram showing the state of encoding processing of a code allocation unit.

30 is a block diagram showing the functional configuration of a decoding device using the variable-length coding method and the moving picture decoding method according to Embodiment 6 of the present invention.

Fig. 31 is a block diagram showing a detailed functional structure of the variable length decoding unit shown in Fig. 30.

FIG. 32 is an explanatory diagram of a computer system using a floppy disk storing a program for executing the moving image encoding method of Embodiments 1, 3, and 5 or the moving image decoding method of Embodiments 2, 4, and 6 and using a computer system.

Fig. 33 is a block diagram showing the overall configuration of a content supply system for realizing content distribution services.

FIG. 34 is a schematic diagram showing a mobile phone using the moving picture prediction method, moving picture coding device, and moving picture decoding device according to the present invention.

Fig. 35 is a schematic diagram showing the structure of a mobile phone according to the present invention.

Fig. 36 is a block diagram showing the overall configuration of the digital broadcasting system according to the present invention.

detailed description

Hereinafter, embodiments according to the present invention will be described with reference to the drawings.

(Embodiment 1) FIG. 1 is a block diagram showing the functional configuration of an encoding device using the moving picture encoding method of the present invention. In this first embodiment, the functional configuration when the video encoding method of the present invention is used to perform intra-encoding processing on an input image is illustrated.

As shown in the figure, the encoding device 100a is composed of a block transformation unit 110, a frequency transformation unit 120, a quantization unit 130, and a variable length encoding unit 140. Each part constituting the encoding device 100a is realized by a CPU, a ROM that stores programs and data executed by the CPU in advance, a work area that provides a work area when the programs are executed, or a memory that temporarily stores input images and the like.

The block conversion unit 110 divides the input image into blocks having a size of 4 pixels horizontally and 4 pixels vertically, and outputs the blocks to the frequency conversion unit 120 for each pixel block.

The frequency conversion unit 120 performs frequency conversion on the input pixel block to convert it into a frequency coefficient. The frequency transform unit 120 outputs the transformed frequency coefficient to the quantization unit 130.

The quantization unit 130 performs quantization processing on the input frequency coefficient. The quantization process mentioned here means a process of dividing a predetermined quantization value by a frequency coefficient value. The quantization value generally differs from block to block and from frequency region. The quantized frequency coefficient is input to variable length coding section 140.

The variable-length encoding unit 140 performs variable-length encoding on the frequency coefficient values of a block of a predetermined size (4 pixels horizontally and 4 pixels vertically).

FIG. 2 is a block diagram showing a detailed functional structure of the variable-length encoding unit 140.

As shown in FIG. 2, the variable-length encoding unit 140 is composed of an RL column generation unit 141, an arrangement replacement unit 142, a code allocation unit 143, and a table storage unit 144.

The quantized frequency coefficient output from the quantization unit 130 is input to the RL column generation unit 141.

The RL column generation unit 141 first performs one-dimensional processing on the quantized frequency coefficient values using a predetermined scanning method. Then, the RL column generation unit 141 generates a combination of the number R of consecutive coefficient values of "0" and the coefficient value L other than the subsequent "0" (hereinafter referred to as the RL value) for the coefficient values after the one-dimensional processing. Column (hereinafter referred to as RL column). An example will be explained using Figure 3 and Figure 4.

FIG. 3(a) shows a schematic diagram of the quantized frequency coefficients in one block output from the quantization unit 130. Among them, the upper left coefficient represents the DC component, and the frequency component in the horizontal direction increases toward the right, and the frequency component in the vertical direction decreases toward the bottom. Fig. 3(b) shows a schematic diagram of a scanning method when one-dimensional processing is performed on the quantized frequency coefficient value. The RL column generation unit 141 performs one-dimensional processing by scanning from the low-frequency region to the high-frequency region.

The RL column is generated for the coefficient values that have been one-dimensionally processed by the RL column generating unit 141, and the result is shown in FIG. 4(a). Among them, in FIG. 4(a), EOB (End of Block) is an identifier indicating that all the coefficient values in the block from then on are '0'. Generally, the higher the high-frequency component, the easier it is for the coefficient value to be '0', so by scanning from the low-frequency area to the high-frequency area, the amount of information in the RL column can be reduced. The generated RL column is input to the arrangement replacement unit 142.

The arrangement replacement unit 142 rearranges the input RL column in the reverse direction. However, EOB is excluded from the arrangement replacement object. The state after the arrangement is replaced is shown in Figure 4(b). The RL column after the replacement of this arrangement is input to the code allocating unit 143.

The table storage unit 144 holds in advance a table (code table, refer to FIG. 5) corresponding to the RL value and the code number assigned to the RL value; and various tables (variable length codes) corresponding to the code number and the variable length code. Coding table, Figure 6).

The code allocation unit 143 uses the table held by the table storage unit 144 to allocate variable-length codes to each group of the RL column.

Specifically, the code allocating unit 143 first allocates a code number to the RL value. At this time, a predetermined code table (refer to FIG. 5) held in the table storage unit 144 is used to perform conversion into a code number.

Figure 5 shows an example of the code table.

The code table is generally assigned a smaller code number as the frequency of the RL value is higher, but generally, the smaller the R and L values are, the higher the frequency band is, so it is constructed using this property. When using this code table, for example, the code number of the first RL value (0, -1) is "2". The code numbers of the 2nd to 5th RL values (1, 1), (0, -2), (0, 3), (0, 4) are '3', '8', '13', ' 15'.

Then, the code allocating unit 143 converts the code number into a variable length code. When converting to this variable length code, a plurality of variable length coding tables (refer to FIG. 6) held in the table storage unit 144 are used to perform conversion to variable length coding.

Fig. 6 shows an example of a variable length coding table.

In the first embodiment, the variable-length coding table maintains two structures.

The first variable length coding table 1 and the second variable length coding table 2 form a structure in which the variable length coding length increases with the increase of the code number. On the other hand, compared with the variable length coding table 2, it can be The variable length code table 1 has a structure in which the variable length code length becomes shorter when the code number is small. Compared with the variable length code table 1, the variable length code table 2 has a structure in which the variable length code length becomes shorter when the code number is large. That is, the variable-length code table 1 is formed by assigning short codes with small code numbers, and the variable-length code table 2 is a structure in which short codes are assigned with large code numbers.

Relative to the first RL value, variable length coding table 1 is used. In this case, the code number of the first RL value is "2", so the variable length code at this time is "011". The variable-length coding conversion is performed sequentially, and when the absolute value of L exceeds the limit value, the variable-length coding table 2 is used after the subsequent RL value. Among them, if the limit value of the absolute value of the relative L is set to '2', the fourth RL value (0, 3) exceeds the limit value. Therefore, the first to fourth RL values are converted using the variable-length coding table 1, and the fifth and subsequent RL values are converted using the variable-length coding table 2.

Among them, at the seventh RL value (1, 2), the absolute value of L again falls below the limit value, and the switch to the variable length coding table 1 is not performed, and the variable length coding table 2 is used for conversion. That is, the switching direction of the table is one direction. One direction mentioned here refers to not reusing the table once it has been used up. In this way, the coefficient value can be used to prevent frequent table switching and reduce the number of table switching. When performing one-dimensional processing from high-frequency components to low-frequency components, the absolute value of L generally tends to increase. Therefore, when the absolute value of L once exceeds the limit value, even if the absolute value of L is below the limit value again, the coefficient below the limit value is mostly limited to the coefficient. Therefore, even if the absolute value of L is lower than the limit value again, the original variable-length coding table is not used again, so the coding efficiency can be improved. For example, because the working space of the memory is limited, generally only the tables to be used subsequently are placed in the working space. In this case, every time the table is switched, the subsequent table needs to be read from the ROM and expanded into the work space, which takes time. Therefore, it takes time to encode the subsequent coefficient values. For this reason, by creating one direction to limit the number of table switching times, it is possible to achieve the effect of shortening the time until the encoding of subsequent coefficient values as a whole.

In addition, the coefficient values of the coefficient value sequence are scanned in the order from the low-frequency component to the high-frequency component via the RL column generating unit 141, and the code allocation unit 143 performs coding sequentially from the back of the coefficient value column to make variable-length coding. Since the absolute value of the coefficient has a tendency to gradually increase from around '1', it is easy to determine the table used to encode the first coefficient value in the block, the structure of each table can be easily determined, or the limit value can be easily determined.

As described above, the variable-length coding method of the first embodiment scans the frequency coefficient values in the block from the low-frequency region to the high-frequency region, and performs one-dimensional processing. For the one-dimensionally processed coefficient values, a column of RL values, which is a combination of the number R of consecutive coefficient values of '0' and subsequent coefficient values L other than '0', is generated. Then, the RL value is converted into a variable length code in the reverse order of the scanning order. That is, it is also possible to directly convert the RL value into a variable length code. When converting to variable-length coding, multiple variable-length coding tables are prepared. First, the first variable-length coding table is used for conversion, and when the absolute value of L exceeds the limit value, the second variable-length coding table is used for conversion for subsequent RL values. In this case, compared with the second variable-length coding table, the first variable-length coding table has a structure in which the variable-length coding length becomes shorter when the code number is small, and the second variable-length coding table is compared with the first variable-length coding table. The length code table forms a structure in which the variable length code length becomes shorter when the code number is large.

Generally, the higher the low frequency component, the greater the absolute value of L. Therefore, the absolute value of L gradually changes when the RL value is converted to variable-length encoding in the reverse order of scanning from the low-frequency area to the high-frequency area to generate the RL value. Big.

Therefore, after the absolute value of L exceeds the limit value, when the code number is large, that is, when the absolute value of L is large, a variable-length code table with a shorter variable-length code length is used, so that the total code amount can be reduced. That is, by encoding L using multiple variable-length encoding tables that are different from R, the total amount of encoding of L can also be reduced.

In the first embodiment, the case where an image is coded by intra-coding is described. However, when a moving image input is inter-coded using motion compensation or the like, the same effect can be obtained by the method of this embodiment.

In addition, in the first embodiment, the case where the input image is divided into blocks of 4 pixels horizontally and 4 pixels vertically has been described, but the size of the blocks may be other sizes.

In the first embodiment, the scanning method within the block was described using FIG. 3(b), but other scanning order may be used as long as it is scanning from the low-frequency region to the high-frequency region.

In the first embodiment, as an example of the code table, the description was made using FIG. 5, but other code tables may also be used.

In the first embodiment, as an example of the variable-length coding table, the description is made using FIG. 6, but other tables may be used.

In addition, the case when two variable-length coding tables are used is explained, but it is also possible to use three or more variable-length coding tables, use multiple limit values, and switch the variable each time each limit value is exceeded. Length coding table.

In this embodiment, the case where the variable-length coding table is switched when the absolute value of L exceeds the limit value is described, but the same effect can be obtained if the variable-length coding table is switched when the code number exceeds the limit value.

In this embodiment, the case where the EOB is added to the end of the RL column has been described, but the number of RL values may be added to the first of the RL column. In this case, the number of RL values to be coded and the RL column corresponding to FIG. 4 are as shown in FIG. 7(a) and FIG. 7(b). In addition, for the code table shown in FIG. 5, it is not necessary to assign a code number to EOB.

(Embodiment 2) FIG. 8 is a block diagram showing the functional configuration of a decoding device using the variable-length decoding method according to an embodiment of the present invention. Here, the code string generated by the variable-length coding method of the present invention described in the first embodiment is input.

As shown in FIG. 8, the decoding device 500a is composed of a variable length decoding unit 510, an inverse quantization unit 520, an inverse frequency transform unit 530, and a frame memory 540. The various parts constituting the decoding device 500a are the same as those of the encoding device 100a, and are realized by a CPU, a ROM that stores programs and data executed by the CPU in advance, a working space for executing programs, or a memory that temporarily stores input images and the like.

The encoded string is input to variable length decoding unit 510. The variable-length decoding unit 510 decodes the coded string that has been variable-length-coded. As described above, the encoding sequence is obtained by dividing the image data in units of blocks with a predetermined size, and performing one-dimensional processing on the frequency coefficient values of the blocks in a predetermined scanning order, and the continuous number R of coefficients whose continuous coefficient value is 0 It is generated by encoding a column of a combination (RL value) with the subsequent coefficient value L.

FIG. 9 is a block diagram showing a detailed functional structure of the variable-length decoding unit 510.

As shown in FIG. 9, the variable-length decoding unit 510 is composed of a code conversion unit 511, a table storage unit 512, an arrangement replacement unit 513, and a coefficient generation unit 514.

The structure of the table storage unit 512 is the same as that of the table storage unit 144, and various tables (variable-length coding table, FIG. 6) corresponding to the code number and the variable-length code are stored in advance; and the RL value and the RL value are assigned to it. Table corresponding to the code number (code table, refer to Figure 5).

The code conversion unit 511 uses the table (a plurality of variable length coding tables) held by the table storage unit 512 to first convert the input code sequence from variable length coding to code number. The conversion to the code number is performed using a plurality of variable-length coding tables. The variable-length coding table is held in the table storage unit 512, and the conversion to the code number is performed by referring to the table storage unit 512.

An example of the variable length coding table is explained using FIG. 6. There are two types of variable-length coding tables. The variable-length coding table 1 is formed by assigning short codes with small code numbers, and the variable-length coding table VLC is a structure in which short codes are assigned with large code numbers. Among them, the leading code of the input code string is '01100100000100100011100010011'. Use Variable Length Coding Table 1 for the first variable length code. When referring to the variable length coding table 1 of FIG. 6, the variable length coding "011" is consistent with the input coding sequence, and the code number at this time is "2".

Then, the code conversion unit 511 converts the obtained code number into an RL value. In this case, use a predetermined code table for conversion. The code table is held in the table storage unit 512, and the conversion to the RL value is performed by referring to the table storage unit 512. Figure 5 shows an example of the code table. The code number at this time is '2', so the RL value is (0, -1).

Similarly, the conversion from variable length code to code number is performed sequentially, using variable length code table 1, to convert variable length code "00100" to code number "3", and variable length code "0001001" to code number "8", the variable-length code "0001110" is converted to a code number "13", and the respective code numbers are converted to RL values (1, 1), (0, -2), (0, 3).

Among them, the code conversion unit 511 uses the variable length coding table 2 in the subsequent variable length coding conversion when the absolute value of L in the obtained RL exceeds the limit value. Among them, if the limit value of the absolute value of the relative L is set to '2', the fourth RL value (0, 3) exceeds the limit value. Therefore, the variable length coding table 2 is used to transform the RL value from then on. Therefore, the subsequent variable length code "0010011" is converted to code number 15, and converted to RL value (0, 4).

Even in the RL values obtained in the subsequent decoding process, when the absolute value of L is lower than the limit value again, the switch to the variable length coding table 1 is not performed, and the variable length coding table 2 is used for conversion. As described above, when the RL value of one block is generated (when EOB is detected), it is input to the arrangement replacement unit 513. Among them, the RL column shown in FIG. 10(a) is generated.

The arrangement replacement unit 513 rearranges the input RL column in the reverse direction. However, EOB is excluded from the arrangement replacement object. The state after the arrangement is replaced is shown in Figure 10(b). The RL column after such permutation and replacement is input to the coefficient generation unit 514.

The coefficient generating unit 514 converts the input RL column into coefficient values, and performs two-dimensional processing according to a predetermined scanning method to form a coefficient block. When performing the conversion to the coefficient value, the coefficient value '0' is generated only for the value denoted by R according to the predetermined scanning order, and then the coefficient value of the value denoted by L is generated, and by repeating this process, it is performed from the RL column Conversion to coefficient value. Among them, if the Z-scan is performed from the low-frequency area to the high-frequency area, the RL column of Fig. 10(b) is transformed into the coefficient block shown in Fig. 11. The generated coefficient block is input to the inverse quantization unit 520.

The inverse quantization unit 520 performs inverse quantization processing on the input coefficient block. The inverse quantization process referred to here means a process equivalent to multiplying the coefficient value by a predetermined quantization value. Among them, the quantization value is generally different from block to block and from frequency region, and can be obtained from the code sequence, or a specified value can be used. The inversely quantized coefficient block is input to the frequency conversion unit 530.

The frequency transform unit 530 performs inverse frequency transform on the inversely quantized coefficient block, and transforms it into a pixel block. The transformed pixel block is input to the frame memory 540.

The decoded pixel blocks are sequentially accumulated in the frame memory 540, and when the pixel blocks of one screen are accumulated, they are output as an output image.

As described above, the variable-length decoding method of the present invention first uses the first variable-length coding table to decode the input coded sequence, and generates a combination of the number R of consecutive coefficient values of 0 and the subsequent coefficient value L other than 0. That is, the value of the RL column. When the absolute value of L exceeds the limit value, the second variable-length encoding table is used to decode the subsequent variable-length encoding. After replacing the RL values in reverse order, the RL values are transformed into coefficient values according to the specified scanning order in the block.

According to the above operations, by using the variable-length decoding method of the present invention, it is possible to correctly decode the coded string encoded by the variable-length encoding method of the present invention.

In this second embodiment, the case of decoding a coded sequence generated by intra-coding is described. However, when using motion compensation or the like to decode a coded sequence generated by inter-coding a moving image input, this The method of the embodiment can also obtain the same effect.

In addition, in the second embodiment, the case where the input image is divided into blocks of 4 horizontal pixels and 4 vertical pixels to be coded has been described, but the block size may be other sizes.

In the second embodiment, the scanning method within the block is described using FIG. 11, but as long as the scanning method is the same as the scanning method used in encoding, another scanning order may be used.

In the second embodiment, as an example of the code table, FIG. 5 was used for description, but as long as it is the same as the code table used in encoding, another code table may be used.

In the second embodiment, as an example of a variable-length coding table, the description is given using FIG. 6, but as long as it is the same as the variable-length coding table used in encoding, another table may be used. In addition, the case when two variable-length coding tables are used is explained, but it is also possible to use three or more variable-length coding tables, use multiple limit values, and switch the variable each time each limit value is exceeded. Length coding table. However, the structure and limit value of the variable-length coding table at this time must be the same as the structure and limit value of the variable-length coding table used during encoding.

In the second embodiment, the case where the variable-length coding table is switched when the absolute value of L exceeds the limit value is described, but the same effect can be obtained if the variable-length coding table is switched when the code number exceeds the limit value.

In the second embodiment, the case of decoding a coded sequence that encodes the EOB added to the last of the RL column is described, but it is also possible to decode the coded sequence that encodes the number of RL values added to the first RL column. . In this case, the number of RL values obtained by decoding and the RL column corresponding to FIG. 10 are shown in FIG. 12(a) and FIG. 12(b). In addition, for the code table shown in FIG. 5, it is not necessary to assign a code number to EOB.

The variable-length encoding method of the present invention described above scans the frequency coefficient values in a block from the low-frequency region to the high-frequency region and performs one-dimensional processing. For the coefficient values after the one-dimensional processing, a column of RL values is generated, which is a combination of the number R of consecutive coefficient values of 0 and the coefficient value L other than 0 after it. The RL value is converted into a variable length code in the reverse order of the scanning order. When converting to variable-length coding, a plurality of variable-length coding tables are prepared. First, the first variable-length coding table is used for conversion, and when the absolute value of L or the code number exceeds the limit value, the second variable-length coding table is used for conversion for subsequent RL values. In this case, compared with the second variable-length coding table, the first variable-length coding table has a structure in which the variable-length coding length becomes shorter when the code number is small, and the second variable-length coding table is compared with the first variable-length coding table. The length code table forms a structure in which the variable length code length becomes shorter when the code number is large.

Generally, the higher the low-frequency component, the larger the absolute value of L and the code number. Therefore, when the RL value is converted into a variable-length code by scanning from the low-frequency area to the high-frequency area and generating the RL value, the absolute value of L is The value gradually becomes larger. Therefore, after the absolute value of L exceeds the limit value, when the code number is large, a variable-length code table with a shorter variable-length code length is used, so that the total code amount can be reduced.

The variable-length decoding method of the present invention first uses the first variable-length coding table to decode the input coded sequence, and generates the combination of the number R of consecutive coefficient values of 0 and the following coefficient value L other than 0, that is, the RL value. Column. When the absolute value of L or the code number exceeds the limit value, the second variable-length encoding table is used to decode the subsequent variable-length encoding. Then, after replacing the RL values in reverse order, the RL values are transformed into coefficient values according to the specified scanning order in the block.

According to the above operations, by using the variable-length decoding method of the present invention, it is possible to correctly decode the coded string encoded by the variable-length encoding method of the present invention.

(Embodiment 3) Hereinafter, an encoding device according to a third embodiment of the present invention will be described with reference to the drawings.

Fig. 13 is a block diagram showing the configuration of an encoding apparatus 100b according to the third embodiment of the present invention.

The encoding device 100b is used to improve the encoding efficiency of the input image (image data) and perform intra-image encoding processing, and is composed of a block transformation unit 101, a frequency transformation unit 102, a quantization unit 103, and a variable length encoding unit 150.

The block transforming unit 101 divides the input image into pixel blocks having a size of 4 horizontal × 4 vertical pixels, and outputs it to the frequency transforming unit 102.

The frequency conversion unit 102 performs frequency conversion on each of the divided pixel blocks to generate frequency coefficients. The frequency conversion unit 102 outputs the generated frequency coefficient to the quantization unit 103.

The quantization unit 103 performs quantization processing on the frequency coefficient output from the frequency conversion unit 102. The quantization process mentioned here means a process of dividing a predetermined quantization value by a frequency coefficient. The quantization value generally varies from pixel block to frequency region. The quantization unit 103 inputs the quantized frequency coefficient to the variable length encoding unit 150.

The variable-length encoding unit 150 performs variable-length encoding on the frequency coefficient quantized by the quantization unit 103.

FIG. 14 is a block diagram showing the internal structure of variable-length encoding unit 150.

As shown in FIG. 14, the variable-length encoding unit 150 is composed of an RL column generation unit 201, an arrangement replacement unit 202, a binary unit 203, a table storage unit 204, and an arithmetic encoding unit 205.

The RL column generation unit 201 performs one-dimensional processing on the quantized frequency coefficients (hereinafter, abbreviated as "coefficients) output from the quantization unit 103 using a predetermined scanning method. Then, the RL column generating unit 201 generates a column of the combination of the number R of consecutive coefficient values of "0" and the coefficient value L other than the subsequent "0" (hereinafter referred to as the RL value) for the coefficients after the one-dimensional processing. (Hereinafter referred to as RL column). An example will be explained using Fig. 15 and Fig. 16.

FIG. 15(a) shows a coefficient block composed of a plurality of quantized coefficients output from the quantization unit 103. Among them, the upper left frequency coefficient in the coefficient block represents the DC component, and the frequency component in the horizontal direction increases toward the right, and the frequency component in the vertical direction decreases toward the right.

Fig. 15(b) is a schematic diagram for explaining a scanning method when one-dimensional processing is performed on a plurality of coefficients in a coefficient block. The RL column generation unit 201 scans the coefficient block from the low-frequency area to the high-frequency area as shown by the arrow in FIG. 15(b) to perform one-dimensional processing of the coefficients.

FIG. 16(a) shows the RL column output from the RL column generating unit 201.

In Fig. 16(a), the first number indicates the number of coefficients. Generally, the higher the frequency region, the easier it is for the coefficient value to be '0'. Therefore, by scanning from the low frequency region to the high frequency region, the amount of information in the RL column (the amount of information in the number R) can be reduced. The generated RL column is input to the arrangement replacement unit 202.

The arrangement replacement unit 202 rearranges the input RL columns in the reverse direction. However, the number of coefficients is excluded from the arrangement replacement object.

FIG. 16(b) shows the RL row after the arrangement replacement unit 202 is arranged. Through this arrangement replacement, although the amount of information is reduced as described above, the result is that the coefficient block is scanned from the high-frequency area to the low-frequency area, and one-dimensional processing of the coefficients is performed. The RL column after the replacement of this arrangement is input to the binary unit 203.

The binary unit 203 performs binary data on the number of coefficients and each RL value, that is, transforms them into binary data composed of '0' and '1'. Here, the number R and the coefficient value L are respectively binary.

FIG. 16(c) shows only the coefficient value L of the RL column after the arrangement replacement by the arrangement replacement unit 202. For these coefficient values L, their absolute values and positive and negative codes are processed separately. The binary unit 203 uses, for example, a predetermined binary table shown in FIG. 21 to binary the absolute value of the number R and the coefficient value L. Then, the binary unit 203 outputs to the arithmetic coding unit 205 the binary data after the binary data has been applied to them.

The arithmetic coding unit 205 performs binary arithmetic coding on the number R value represented as binary data and the absolute value of the coefficient value L, and simultaneously codes the positive and negative codes of the coefficient value L. Here, the arithmetic coding of the absolute value of the coefficient value L will be described. When the arithmetic coding unit 205 performs arithmetic coding on the absolute value of the coefficient value L represented as binary data, it switches the use of a plurality of probability tables. These multiple probability tables are stored in the table storage unit 204.

Fig. 17 is a transition diagram showing a switching method of the probability table.

As shown in FIG. 17, the arithmetic coding unit 205 uses four probability tables, and performs arithmetic coding on the absolute value of the first coefficient value L using the probability table 1. Regarding the absolute value of the subsequent coefficient value L, the arithmetic coding unit 205 switches the probability table to be used according to the table number and absolute value of the probability table used when encoding the absolute value of the preceding coefficient value L. Among them, the 4 probability tables are probability table 1, probability table 2, probability table 3, probability table 4. The table number of probability table 1 is '1', the table number of probability table 2 is '2', and the table of probability table 3 The sequence number is '3', and the table sequence number of the probability table 4 is '4'.

Specifically, the absolute value of the preceding coefficient value L is coded using probability table 1, and its absolute value is '1', or the absolute value of the immediately preceding coefficient value L is coded using probability table 2, and its When the absolute value is '1', use probability table 2. When the absolute value of the preceding coefficient value L is coded using probability table 1, and its absolute value is '2', or the absolute value of the preceding coefficient value L is coded using probability table 2, and its absolute value is '2 ', or the absolute value of the preceding coefficient value L is coded using probability table 3, and when its absolute value is '2 or less', probability table 3 is used. When the absolute value of the preceding coefficient value L is "3 or more", or when the absolute value of the preceding coefficient value L is encoded using the probability table 4, the probability table 4 is used.

The switching of this kind of probability table is one direction from the probability table with a small table number to the probability table with a large table number. Even if the absolute value of the previous coefficient value L is below the specified limit value, the switch in the opposite direction is not performed. This point is different from the previous embodiment.

FIG. 18 is a schematic diagram of the content of the probability table showing the content of the four probability tables 1 to 4 described above.

The probability tables 1 to 4 are shown in Fig. 18, and are composed of the probability of producing a '0' and the probability of producing a '1'.

For example, the probability table 1 is composed of the probability of producing a '0' '0.1' and the probability of producing a '1' is composed of '0.9', and the probability table 2 is composed of the probability of producing a '0' of '0.2' and the probability of producing a '1' of '0.8' constitute.

That is, if the absolute value of the coefficient value L is '2', and the '2' is binarized to be '01', when the arithmetic coding unit 205 uses the probability table 1 to arithmetic coding it, it uses the '0' corresponding to the aforementioned '01' The probability of '0.1' and the probability of '1' corresponding to the above-mentioned '01' are '0.9', and this '01' is arithmetic coded.

Among them, the total of the probability of producing a '0' and the probability of producing a '1' is 1.0, so there is no need to maintain the probability of both, and only one probability can be maintained.

Hereinafter, an example of switching the probability table when the absolute value (binary value) of the coefficient value L shown in FIG. 16(c) is encoded will be described.

The arithmetic coding unit 205 uses the probability table 1 for the absolute value of the first coefficient value L(-2). The absolute value of the coefficient value L here is 2, so the arithmetic coding unit 205 transfers the probability table used from the probability table 1 to the probability table 3. In this way, the arithmetic coding unit 205 uses the probability table 3 to perform arithmetic coding on the absolute value of the second coefficient value L(3). The absolute value of the coefficient value L here is 3, so the arithmetic coding unit 205 transfers the probability table used from the probability table 3 to the probability table 4. In this way, the arithmetic coding unit 205 uses the probability table 4 to perform arithmetic coding on the absolute value of the third coefficient value (6). The probability table used here is transferred to the probability table 4, so the arithmetic coding unit 205 performs arithmetic coding using the probability table 4 for all the absolute values of the subsequent coefficient values L. For example, when the absolute value of the fifth coefficient value L is "2, unlike the previous example, when the arithmetic coding unit 205 arithmetic coding the absolute value of the coefficient value L after the sixth, the probability table is used instead of the probability table. Table 4.

In addition, each probability table is updated at any time according to whether the input is "0" or "1", so it is updated to a probability table suitable for the input.

As described above, the variable-length encoding method of the variable-length encoding unit 150 of the image encoding device 100b according to the present invention scans the coefficient block from the low-frequency region to the high-frequency region and performs one-dimensional processing. For the one-dimensionally processed coefficient values, a combination of the number R of consecutive coefficient values of 0 and the following coefficient value L other than 0, that is, a column of RL values (RL column) is generated. The RL value is converted into a variable length code in the reverse order of the scanning order. When converting to variable-length coding, the number R, the absolute value of the coefficient value L, and the positive and negative codes of the coefficient value L are respectively converted. When performing these transformations, binary is first performed, and then arithmetic coding is performed. When performing arithmetic coding on the absolute value of the coefficient value L, a plurality of probability tables are switched. When switching the probability table, according to the table number of the current probability table and the absolute value of the coefficient value L, the probability table for encoding the absolute value of the following coefficient value L is determined. The transition of the probability table is only performed in one direction. When the absolute value of the coefficient value L exceeds the prescribed value once, the subsequent arithmetic coding is all performed using the same probability table.

Generally, the absolute value of the coefficient value L becomes larger as it goes to the low frequency region. Therefore, when scanning from the high frequency region to the low frequency region in order, the absolute value of the coefficient value L becomes larger in order in most cases. Therefore, when the absolute value of the coefficient value L exceeds the specified value once, even if the absolute value of the following coefficient value L is less than the specified value, the possibility that the absolute value of the coefficient value L becomes smaller is very high, and the same probability is used The table is arithmetic-coded, so that the update of the probability table is easily adapted to the input, so the probability of occurrence of the symbols ('0' or '1' in binary data) of each probability table is likely to be offset (ie, '0' Or the probability of occurrence of either "1" becomes a value close to 1.0). Arithmetic coding has the feature that the more the probability value in the probability table shifts, the higher the coding efficiency. Therefore, by using the variable length coding method of the present invention, an improvement in coding efficiency can be achieved.

As mentioned above, the image coding apparatus according to the present invention has been described using this embodiment, but the present invention is not limited to this.

For example, in this embodiment, the case where an image is encoded using intra-image encoding is described, but the same effect can be obtained when inter-image encoding is performed on a moving image input using motion compensation or the like.

In addition, in this embodiment, the case where the input image is divided into pixel blocks of horizontal 4×vertical 4 pixels has been described, but the size of the pixel block may be other sizes.

In the present embodiment, the scanning method in the coefficient block is described using FIG. 15(b), but other scanning order may be used as long as it is scanning from the low-frequency region to the high-frequency region.

In this embodiment, the following case is described. The RL column generating unit 201 uses a predetermined scanning method to perform one-dimensional processing on the quantized frequency coefficients, and then generates a continuous coefficient value of '0 on the one-dimensional processed coefficient values. A column of combinations of the number R of 'and the coefficient value L other than the subsequent '0' (the RL column), but the column of the number R and the column of the coefficient value L may be generated separately. For example, when generating a column of coefficient values L, if scanning is performed from a high-frequency region to a low-frequency region and generating by selecting a coefficient other than the coefficient value of 0, the arrangement replacement unit 202 may be omitted.

In this embodiment, it is explained that four probability tables are used and the probability table is transferred based on the transition diagram shown in FIG. 17, but the number of probability tables and the limit of the absolute value of the relative coefficient value L at the time of transition in FIG. The value can also be other values.

In this embodiment, as an example of a binary table, the description is made using FIG. 21, but other tables may be used.

In addition, in this embodiment, the case where the arithmetic coding unit performs binary arithmetic coding has been described, but it is also possible to perform multi-value arithmetic coding. In this case, the binary unit 203 can be omitted.

(Embodiment 4) Hereinafter, an image decoding device according to a fourth embodiment of the present invention will be described with reference to the drawings.

Fig. 19 is a block diagram showing the configuration of a decoding apparatus 500b according to the fourth embodiment of the present invention.

The decoding device 500b is used to perform intra-image decoding processing on a coded sequence of image data subjected to intra-image coding processing, and is composed of a variable-length decoding unit 601, an inverse quantization unit 602, an inverse frequency transform unit 603, and a frame memory 604 . Here, the input coded sequence is generated by, for example, the variable-length coding method of the coding apparatus 100b of the third embodiment, and the variable-length decoding unit 601 first obtains the coded sequence.

The variable-length decoding unit 601 acquires a coded sequence, and performs variable-length decoding on the coded sequence, thereby creating a coefficient block composed of a plurality of coefficients as shown in FIG. 15(a).

The inverse quantization unit 602 obtains the above-mentioned coefficient block from the variable length decoding unit 601, and performs an inverse quantization process on the coefficient block. The inverse quantization process referred to here means multiplying each coefficient of the coefficient block by a predetermined quantization value. The quantized value here is generally different for each coefficient block and frequency region, and can be obtained from the coded column. The inverse quantization unit 602 outputs the inversely quantized coefficient block to the inverse frequency transform unit 603.

The inverse frequency transform unit 603 performs inverse frequency transform on the inversely quantized coefficient block, and transforms the coefficient block into a pixel block. The inverse frequency transform unit 603 outputs the transformed pixel block to the frame memory 604.

The decoded pixel blocks are sequentially accumulated in the frame memory 604. When the pixel blocks of one screen are accumulated, these pixel blocks are output as output images.

The variable length decoding unit 601 will be described in detail below.

FIG. 20 is a block diagram showing the internal structure of the variable-length decoding unit 601.

As shown in FIG. 20, the variable-length decoding unit 601 is composed of an arithmetic decoding unit 701, a multi-valued unit 702, a table storage unit 703, an arrangement replacement unit 704, and a coefficient generation unit 705.

The table storage unit 703 holds, for example, four probability tables 1 to 4 shown in FIG. 18.

The arithmetic decoding unit 701 obtains a coded sequence, and first performs arithmetic decoding on the coded sequence. Next, the binary arithmetic decoding of the absolute value (binary value) of the coded coefficient value L included in the coded sequence will be described.

When the arithmetic decoding unit 701 performs arithmetic decoding on the absolute value of the encoded coefficient value L, it obtains the decoded and multi-valued absolute value of the previous coefficient value L from the multi-valued unit 702, according to the absolute value of the coefficient value L , Switch and use the probability tables 1 to 4 held in the table storage unit 703 as shown in FIG. 17, perform binary arithmetic decoding on the absolute value of each coefficient value L after encoding, and output binary data corresponding to them.

The multi-valued unit 702 multi-values the binary data output from the arithmetic decoding unit 701 as the absolute value of the coefficient value L using, for example, the binary table shown in FIG. 21. The multi-valued unit 702 outputs the absolute value of the coefficient value L to the arithmetic decoding unit 701 and the arrangement replacement unit 704.

Next, specific operations of the arithmetic decoding unit 701 and the multi-valued unit 702 will be described.

First, the arithmetic decoding unit 701 uses the probability table 1 to perform arithmetic decoding on the absolute value of the coded leading coefficient value L. The arithmetic decoding unit 701 outputs the binary data obtained by the arithmetic decoding to the multivalued unit 702. The multivalued unit 702 performs conversion from the binary data to the absolute value of the coefficient value L using the binary table, and outputs the absolute value to the arithmetic decoding unit 701 and the arrangement replacement unit 704.

Then, the arithmetic decoding unit 701 uses the absolute value of the coefficient value L that has been coded after that to use the table number and the number of the probability table used when performing binary arithmetic decoding on the absolute value of the coefficient value L that has been coded before. The absolute value of the previous coefficient value L obtained by the quantization unit 702 switches the probability table used. As shown in FIG. 17, the absolute value of the previously encoded coefficient value L is when arithmetic decoding is performed using the probability table 1, and the absolute value of the previous coefficient value L obtained from the multi-valued unit 702 is '1', or When the absolute value of the previously encoded coefficient value L is arithmetically decoded using the probability table 2, and the absolute value of the previous coefficient value L obtained from the multi-valued unit 702 is '1', the probability table 2 is used. The absolute value of the previously encoded coefficient value L is when arithmetic decoding is performed using the probability table 1, and the absolute value of the previous coefficient value L obtained from the multi-valued unit 702 is '2', or the previously encoded coefficient The absolute value of the value L is when arithmetic decoding is performed using the probability table 2, and the absolute value of the previous coefficient value L obtained from the multi-valued unit 702 is '2', or the absolute value of the previously encoded coefficient value L is When arithmetic decoding is performed using the probability table 3, and the absolute value of the previous coefficient value L obtained from the multi-valued unit 702 is "2 or less, the probability table 3 is used. When the absolute value of the previous coefficient value L obtained from the multivalued unit 702 is "3 or more, or when the absolute value of the previously encoded coefficient value L is arithmetic decoding using the probability table 4, the probability table 4 is used. This kind of switching of probability tables 1 to 4 is one direction from the probability table with a small table number to the probability table with a large table number, even if the absolute value of the previous coefficient value L obtained from the multi-value unit 702 reaches the specified limit value or less When, the switch in the opposite direction is not performed. This point is different from the previous embodiment.

Hereinafter, an example of switching the probability table when decoding to the absolute value of the coefficient value L shown in FIG. 16(c) is described.

The arithmetic decoding unit 701 performs arithmetic decoding on the absolute value of the coefficient value L(-2) that has been coded first using the probability table 1 to make it into binary data "01. The arithmetic decoding unit 701 obtains the binary data "01" after the binary data "01" is multivalued from the multivalue unit 702, and therefore transfers the probability table used from the probability table 1 to the probability table 3. In this way, the arithmetic decoding unit 701 uses the probability table 3 to arithmetically decode the absolute value of the second encoded coefficient value L(3) into binary data "001. The arithmetic decoding unit 701 obtains the "3 after the binary data "001 is multi-valued from the multi-value unit 702, so the used probability table is transferred from the probability table 3 to the probability table 4. In this way, the arithmetic decoding unit 701 uses the probability table 4 to arithmetically decode the absolute value of the third encoded coefficient value L(6) into binary data "000001. The probability table used here is transferred to the probability table 4, so the arithmetic decoding unit 701 performs arithmetic decoding on all the absolute values of the coefficient values L to be encoded later using the probability table 4. For example, the absolute value of the fifth encoded coefficient value L is decoded and multi-valued, and the result is '2'. However, unlike the previous example, the arithmetic decoding unit 701 performs the calculation of the sixth and subsequent encoded coefficients. When the absolute value of the value L is arithmetically decoded, the probability table 4 is used instead of the transition probability table.

Through the above operations, the absolute value of the coefficient value L of one coefficient block, the number R and the positive and negative codes of the coefficient value L are generated, and these are input to the arrangement replacement unit 704 as the RL column.

The arrangement replacement unit 704 rearranges the input RL column in the reverse direction. However, the number of coefficients is excluded from the arrangement replacement object. The state after the arrangement is replaced is shown in Figure 16(a). The arrangement replacement unit 704 inputs the RL column after such arrangement replacement to the coefficient generation unit 705.

The coefficient generation unit 705 transforms the input RL column into a coefficient block. At this time, the coefficient generation unit 705 generates a coefficient for only the value "0" represented by the number R according to the predetermined scanning order, and then generates a coefficient value for the value represented by the coefficient value L, and repeats this process to perform the Transformation of RL column to coefficient block. Among them, the coefficient generating unit 705, as shown in FIG. 15(b), performs a Z-scan from the low-frequency area to the high-frequency area, and transforms the RL column shown in FIG. 16(a) into the coefficient block shown in FIG. 15(a) . The coefficient generation unit 705 inputs the coefficient block thus generated to the inverse quantization unit 602.

As described above, the variable-length decoding method of the variable-length decoding unit 601 of the decoding device 500b according to the present invention switches between a plurality of probability tables when performing arithmetic decoding of the absolute value of the coefficient value L in the input code sequence. When switching between multiple probability tables, the table number of the current probability table and the absolute value of the coefficient value L obtained by decoding are used to determine the probability table used when decoding the absolute value of the subsequent coefficient value L. The transition of the probability table at this time is only performed in one direction, and when the absolute value of the coefficient value L obtained by decoding exceeds the predetermined value once, the same probability table is used for arithmetic decoding from then on.

In this way, by using the variable-length decoding method of the present invention, it is possible to correctly decode the coded string encoded by the variable-length encoding method of the present invention.

As mentioned above, the image decoding device according to the present invention has been described using this embodiment, but the present invention is not limited to this.

For example, in this embodiment, the case where the generated coded sequence is decoded by intra-image coding is described. However, when using motion compensation or the like to decode the coded sequence generated by inter-image coding of moving image input, it may be Get the same effect.

In addition, in the present embodiment, the case where the image data is divided into 4 horizontal pixel blocks of 4 vertical pixels and coded sequence is described, but the size of the pixel block may be another size.

In this embodiment, it is explained that four probability tables are used and the probability table is transferred based on the transition diagram shown in FIG. 17, but the number of probability tables and the limit of the absolute value of the relative coefficient value L at the time of transition in FIG. The value can also be other values.

In this embodiment, the scanning method in the coefficient block is described using FIG. 15(b), but as long as the scanning method is the same as the scanning method used in encoding, another scanning order may be used.

In this embodiment, as an example of binary, the description is made using FIG. 21, but as long as it is the same as the binary table used in encoding, another table may be used.

In addition, in this embodiment, the case where the arithmetic decoding unit 701 performs binary arithmetic decoding has been described, but it is also possible to perform multi-value arithmetic decoding. In this case, the multi-valued unit 702 can be omitted.

Hereinafter, other embodiments according to the present invention will be described with reference to the drawings.

(Embodiment 5) FIG. 22 is a block diagram showing the functional configuration of an encoding device to which the variable-length encoding method of the present invention and the moving picture encoding method using the method are applied. In the fifth embodiment, the same as the encoding devices 100a and 100b of the first and third embodiments, the functional configuration when the moving image encoding method of the present invention is used to perform intra-encoding processing on an input image is illustrated. The various parts constituting the encoding device 100c are realized by a CPU, a ROM that stores programs and data executed by the CPU in advance, a memory that provides a working space when the programs are executed, or a memory that temporarily stores input images and the like.

As shown in FIG. 22, the encoding device 100c according to the fifth embodiment is composed of a block transformation unit 110, a frequency transformation unit 120, a quantization unit 130, and a variable length encoding unit 160.

Among them, the coding device 100a according to the above-mentioned Embodiment 1 is configured to use multiple variable-length coding tables (VLC tables) to code R and L pairs, and the coding device 100b according to the above-mentioned Embodiment 3 is configured to use multiple probabilities. Tables perform arithmetic coding on R and L respectively. The coding device 100c according to the fifth embodiment is configured to use multiple variable-length coding tables different from R to code L, which is different from the coding devices 100a and 100b. Therefore, the encoding device 100c uses the variable-length encoding unit 160 instead of the variable-length encoding units 140, 150 of the encoding devices 100a, 100b. The other configuration is the same as that of the encoding apparatuses 100a and 100b, so the description thereof is omitted, and the variable-length encoding section 160 will be described in detail.

The variable-length coding unit 160 generates an L column and an R column respectively based on the frequency coefficients quantized by the quantization unit 130, and generates a coded sequence such as absolute value |L| of the coefficient using a one-dimensional VLC switching method.

FIG. 23 is a block diagram showing a detailed functional structure of the variable-length encoding unit 160.

As shown in FIG. 23, the variable-length encoding unit 160 is composed of an R column·L column generating unit 161, a code allocating unit 163, and a table storage unit 164.

The R column·L column generating unit 161 zigzags the quantized frequency coefficients (hereinafter, referred to as "coefficients) from the lower frequency to the higher frequency, and generates L and R columns, respectively.

Specifically, when the block coefficients shown in FIG. 3(a) are input, the R column·L column generating unit 161 performs Z-scanning as shown in FIG. 3(b). As shown in Fig. 24(a), the R column·L column generating unit 161 first obtains, for the L column, the number m of L other than the coefficient value of "0, the column of the absolute value of the coefficient |L|, and the The coding column of the coefficient. This is because R depends on L, and L does not depend on R and can be obtained independently. Then, the R column·L column generating unit 161 generates the R column (R column) as shown in FIG. 24(b).

The table storage unit 164 holds a plurality of (for example, eight) variable-length coding tables 1641a to 1641g for variable-length coding of the absolute value of each coefficient |L| of the L column, and the absolute value of the relative coefficient. The limit value of the value |L| is maintained for the limit value table 1642 and the like for appropriately switching the variable length coding tables 1641a to 1641g according to the absolute value of the coefficient |L|.

Fig. 25 shows an example of the structure of the variable-length coding tables 1641a to 1641g. The variable-length encoding tables 1641a to 1641g are actually constructed by associating the absolute values of coefficients |L| with their binary codes, but in this figure, one table is used for illustration.

The higher the frequency of the absolute value of the coefficient |L|, the smaller the code number is assigned, but generally the smaller the value of the absolute value of the coefficient |L|, the higher the frequency of occurrence. This is because the maximum value of the absolute value of the coefficient |L| is scattered in the image and in the screen, and the same value appears less frequently, while the minimum value of the absolute value of the coefficient |L|, that is, the high frequency component is basically There is a strong tendency to concentrate on '1' and '2', so the frequency of occurrence of the same value increases. On the other hand, if only the absolute value of the coefficient |L| and the binary code correspond to a variable-length coding table, the larger the absolute value of the coefficient |L|, the longer the code length becomes. For this reason, variable-length coding tables 1641a to 1641g adapted to the absolute value of the coefficient |L| are prepared in advance so that even if the absolute value of the coefficient |L| becomes larger, the code length will not be too long.

The variable length coding tables 1641a to 1641g are structured such that the rate of change of the coding length of the relative coefficient value is different, so that the coding length of the minimum value of the coefficient value is increased in the order of the number k assigned to each of the tables. , The coding length of the maximum value of the coefficient value becomes shorter in the order of sequence number k.

Specifically, in each table, the variable length coding table 1641a is the table with the longest coding length when the absolute value of the coefficient |L| is small, the coding length is the shortest, and when the absolute value of the coefficient |L| is large, the coding length is the longest. That is, in each of the variable-length coding tables 1641a to 1641g, the variable-length coding table 1641a is a table in which the rate of change of the coding length with respect to the absolute value of the coefficient |L| is the largest, and it is suitable for the case where the absolute value of the coefficient |L| is small. (For example, "1" to "3").

In each table, the variable length coding table 1641g is the table with the shortest coding length when the absolute value of the coefficient |L| is small, the coding length is the longest, and the absolute value of the coefficient |L| is large, the coding length is the shortest. That is, among the variable-length coding tables 1641a to 1641g, the variable-length coding table 1641g is the table with the smallest absolute value |L| of the coefficient of change rate of the coding length, and is suitable for the absolute value of the coefficient |L| large ( For example, in the case of '193'~).

The variable-length coding tables 1641b to 1641f in the middle are in the order of 1641b to 1641f. When the absolute value of the coefficient |L| is small, the coding length gradually becomes longer, and when the absolute value of the coefficient |L| is large, the coding length gradually changes. Short table. That is, the variable length coding tables 1641b to 1641f are tables where the rate of change of the coding length becomes smaller with respect to the absolute value of the coefficient |L| in the order of 1641b to 1641f. They are respectively applicable to the following situations, namely, variable length coding Table 1641b is used when the absolute value of the coefficient |L| is from '4' to '6', and the variable-length coding table 1641c is used when the absolute value of the coefficient |L| is from '7' to '12', for example. use,.......

In this way, variable-length coding whose coding length is adapted to the coefficient value can be adapted to each table, so coding efficiency can be improved. That is, when the coefficient value is small, use a certain table for encoding to make the coding length shorter than the variable length coding of other tables. When the coefficient value is large, use another table for coding to make the coding length shorter than that of other tables. Variable-length coding switches the table according to the coefficient value, so that the coding length can be drastically shortened. In addition, it is possible to allocate a range in which the coding length is shortened to each table, so that the coding efficiency can be improved. The coding is a non-arithmetic coding, that is, the VLC method, so there is no need for complicated processing like arithmetic coding. When the table used for coding is determined, the table can be simply referred to and the variable-length coding can be easily coded.

FIG. 26 is a diagram showing a configuration example of the limit value table 1642.

The limit value table 1642 is preset based on the characteristics of the variable length coding tables 1641a to 1641g, and holds a plurality of limit values used when switching the variable length coding tables 1641a to 1641f. For example, the threshold value for switching between the variable length coding tables 1641a and 1641b is set to '4', and the threshold value for switching (transition) to the variable length coding tables 1641b and 1641c is set to '7',... ..., the limit value of the switching with respect to the variable-length encoding tables 1641f and 1641g is '193'. In this way, the switching time of the table can be simply judged, and the table can be switched to the best table suitable for the absolute value of the coefficient |L|.

The code allocating unit 163 uses the variable-length coding tables 1641a to 1641g and the limit value table 1642 held by the table storage unit 164 to determine the absolute value |L| of the coefficient output from the R column·L column generating unit 161 different from that of the R column. Variable-length coding, assigning a binary code. That is, the code allocating unit 163 performs one-dimensional encoding on the absolute value |L| of the coefficient.

Next, the encoding operation of the encoding device 100c will be described. The operations of the block transform unit 110 to the quantization unit 130 are the same as the operations of the encoding apparatuses 100a and 100b described above, so the description of the operations is omitted, and the variable-length encoding operation of the variable-length encoding unit 160 will be described in detail.

The frequency coefficients quantized by the quantization unit 130 are input to the R column·L column generation unit 161 of the variable length coding unit 160.

The R column·L column generating unit 161 first, as shown in FIG. 3(b), performs a unity of the frequency coefficient values by scanning the quantized frequency coefficient values in the Z-shaped scanning block from the DC component area to the high frequency component area. Dimension processing. Then, the R column·L column generating unit 161 generates a column of coefficient values L other than "0 (hereinafter referred to as "L column) and a column of the number R of continuous coefficient values of "0 (hereinafter, Called'R column'). An example of the generated L and R columns is shown in Fig. 24. The L column is divided into the number m of coefficients, the absolute value of the coefficient |L|, and the sign of the coefficient. In addition, for the sign of the coefficient, for example, positive corresponds to "0 and negative corresponds to "1.

Generally, the higher the high-frequency component, the easier it is for the coefficient value to become '0', so by scanning from the low-frequency region to the high-frequency region, the coefficient value in the L column is close to '1'.

The code allocating unit 163 encodes each L value of the L column generated by the R column·L column generating unit 161 in the reverse order of the Z-scan, that is, from the higher frequency. That is, the code allocating section 163 uses the variable-length coding tables 1641a to 1641g sequentially from the back of the L column to sequentially obtain the Huffman coding (variable-length coding) of the absolute value |L| of the corresponding coefficient.

The reason for adopting the reverse order of the zigzag scan is that it is easy to determine the first table to be used when coding coefficient values other than "0 in the high-frequency region, and it is easy to create variable-length coding tables 1641a~ 1641g, and easy to determine the limit value.

The code allocating unit 163 uses various tables held in the table storage unit 164 to allocate a variable-length code to each R of the L and R columns of the L column. The code assigning unit 163 also assigns variable-length codes to the number m of coefficients. The process of assigning variable-length codes to the absolute value |L| of the coefficients will be described below.

FIG. 27 shows a flowchart of the variable-length code allocation process performed by the code allocation unit 163.

When the code allocating unit 163 starts the coding of the coefficient values in the block (the absolute value of the coefficient |L|), it sets the number m of coefficient values output from the R column·L column generating unit 161 (S101). Then, the code allocating unit 163 sets '0' to the table number k as the initial value of the variable-length coding table to be referred to (S102). After that, the code allocating unit 163 refers to the limit value table 1642 and sets the limit value=4 (S103).

When the number of coefficients m, the reference target of the variable-length coding table (in this case, the variable-length coding table 1641a), and the setting of the limit value are completed, the code allocation unit 163 reads out from the R column·L column generation unit The absolute value of the coefficient |L| output by 161 (S104) uses the variable length coding table of the set sequence number to encode the absolute value of the coefficient |L| read out to make it a variable length code (S105) . Once the encoding is completed, the code allocating unit 163 stores the binary code obtained by encoding in a buffer (for example, a FIFO buffer) not shown (S106), and subtracts '1' from the number m of coefficients (S107), It is judged whether the decremented number m is '0', that is, it is judged whether all the coefficients included in the L column have been coded (S108).

If the number m of coefficients is not '0' (No in S108), it is judged whether the absolute value |L| of the immediately preceding coefficient exceeds the limit value (S109). If it does not exceed (No in S109), the code allocating unit 163 reads out the absolute value of the subsequent coefficient |L| (S104), and executes steps S105 to S108 and so on. That is, the absolute value |L| of the subsequent coefficient is coded using the same variable-length coding table as before.

When the absolute value |L| of the immediately preceding coefficient exceeds the limit value (No in S109), the code allocating unit 163 increments the table number k by "1" (S110). In this way, when the subsequent encoding of the absolute value of the coefficient |L| is performed, the variable-length encoding table (for example, If the previous variable length coding table is 1641a with k=0, then 1641b with k=1).

Once the increment of the table number k ends, the code allocation unit 163 refers to the limit value table 1642 and updates to the subsequent limit value (for example, if the previous limit value is '4', then it is updated to '7') (S111). In this way, only when the absolute value of the coefficient |L| exceeds the new limit value, it is possible to shift to the subsequent variable-length coding that is suitable for the coding of the absolute value of the long-coded coefficient |L| with a smaller rate of change in the coding length. table.

Specifically, the absolute value of the immediately preceding coefficient |L| exceeds the limit value '4' between the variable-length coding table 1641a whose table number is '0' and the variable-length coding table 1641b whose table number is '1' As shown in Fig. 28, as the reference target when encoding the subsequent absolute value of the coefficient |L|, the reference target is switched from the variable-length coding table 1641a to the variable-length coding table 1641b, and the limit value is set to '7'.

Even when the absolute value of the immediately preceding coefficient |L| exceeds the limit value of '7' to '193' between the variable length coding tables 1641b to 1641g whose table number is '1' to '6', the sum exceeds the limit value The same is true for the case of '4'. As the reference target when encoding the subsequent absolute value of coefficients |L|, the order is switched from the variable-length coding table 1641b whose table number is '1' to the variable-length coding table whose table number is '2'. Length coding table 1641c,..., variable length coding table 1641g. The switching state at this time is shown in Figure 28.

Among them, the switching direction of the table is one direction and does not return. In this way, the coefficient value is used to prevent frequent table switching and reduce the number of table switching. Therefore, coding efficiency can be improved. For example, the working space of the memory is limited, so generally only the subsequently used tables are placed in the working space. In this case, every time the table is switched, it takes time to read the subsequent table from the ROM and expand it to the workspace, so it takes time to encode the coefficient value following the limit. For this reason, by forming one direction and limiting the number of table switching times, the overall effect of shortening the coding time of coefficient values following the limit can be achieved.

Once the increment of the table number and the update of the limit value are completed, the code allocating unit 163 reads the absolute value of the subsequent coefficient |L| from the back (S104), and executes steps S105 to S108 and so on. That is, coding is performed using a variable-length coding table in which the absolute value |L| suitable for the coefficient is larger than the previous one.

By repeating this process (S104 to S111), until the number m of coefficients is "0", when the number m of coefficients is "0", the coding of the absolute value of the coefficient |L| in the block is ended. .

Specifically, the column of the absolute value of the coefficient |L| in the block is '1', '1', '2', '3', '4', '12', '2', '3 from the back ","31","22","5","9","38", the code allocation unit 163 as shown in Figure 29, first use the variable length coding table 1641a to separate "1", "1" ', '2', '3', '4', and '12' are sequentially encoded as binary codes '1', '1', '010', '011', '00100', and '0001100'. Since the absolute value of the coefficient |L|='12' was coded to exceed the limit value of '4', the code allocating unit 163 switches the table used for coding to a variable-length coding table with table number k=1. 1641b.

Then, the code allocating unit 163 uses the switched variable-length coding table 1641b to sequentially encode the absolute values of the subsequent coefficients |L|='2', '3', and '31' into binary codes '11', ' 0100', '0000100000'. Since the absolute value of the coefficient |L|='31' was coded to exceed the limit value of '7', the code allocating unit 163 switches the table used for coding to a variable-length coding table with table number k=2. 1641c.

The code allocating unit 163 uses the switched variable-length coding table 1641c to encode the absolute value of the subsequent coefficient |L|='22' into the binary code '0011001'. Since the absolute value of the coefficient |L|='22' was coded to exceed the limit value of '13', the code allocating unit 163 switches the table used for coding to a variable-length coding table with table number k=3. 1641d.

Then, the code allocating unit 163 uses the switched variable-length coding table 1641d to sequentially encode the absolute values of the subsequent coefficients |L|='5', '9', and '38' into binary codes '1100', ' 010000', '00101101'. In this way, the 2-value code '1101001100100000110011010000001000000011001110001000000101101' is stored in the buffer.

The number m of the coefficients of the coded L column, the sign of the coefficients, and the R value binary code of the R column are also stored in the buffer, and the coded coefficients of the L column are stored in the buffer. The number m, the binary code of the absolute value of the coefficient |L|, the sign of the coefficient, and the binary code of the R value in the R column are sent to the decoding device via recording media such as CDs and transmission media such as the Internet and satellite broadcasting.

Among them, it is assumed that only the variable length coding table 1641a is used for the absolute values of the coefficients of the above L column |L|'1','1','2','3','4','12','2' , '3', '31', '22', '5', '9', and '38' when encoding, its binary code is '1', '1', '010', '011', ' 00100', '0001100', '010', '011', '000011111', '000010110', '00101', '001001', and '00000100110' are 64-bit encoding lengths.

In contrast, the coding method of the fifth embodiment can form a 61-bit code even when the absolute value of the coefficient in the block |L| has a low maximum value and the absolute value of the coefficient |L| does not rise slowly. Length can improve coding efficiency. When the absolute value of the coefficient |L| is, for example, '22', '38', if only the variable-length coding table 1641a is used, 9 bits of '000010110' and 11 bits of '00000100110' are required, but this method uses' 0011001' 7 bits and '00101101' 8 bits can be solved. Therefore, when the maximum absolute value of the coefficient |L| in a normal block is high, and the absolute value of the coefficient |L| rises gradually, the coding efficiency can be improved drastically.

In addition, in the fifth embodiment above, when the absolute value |L| of the immediately preceding coefficient exceeds the limit value (S109 is determined as Yes), the table number is increased by 1 (S110), and the variable-length coding table of the following number is used for encoding. (Refer to FIG. 28), but it is also possible to skip and switch to a variable-length coding table adapted to the absolute value of the coefficient |L| based on the absolute value |L| of the preceding coefficient that exceeds the limit value. That is, when the absolute value |L| of the preceding coefficient encoded with reference to the table of index k=1 is '20', the absolute value of the following coefficient |L| is highly likely to be greater than '20', so perform the following When coding the absolute value of the coefficient |L|, you can also refer to the table of k=3 for coding. In this case, it is only necessary to set the limit value to a limit value (for example, 25) that matches the variable-length coding table.

The above describes the case when 8 variable length coding tables are used, but 2 to 7 variable length coding tables can also be used, or more than 8 and multiple limit values are used, and each limit value is exceeded each time Switch the variable length coding table.

In addition, in the fifth embodiment, the coefficient values are divided into absolute values and positive and negative codes to be coded, and the absolute value of the coefficient values is constructed in a form without positive and negative codes (absolute values). Each variable-length coding table is also used. The coefficient value can be coded in the format with positive and negative codes. In this case, the format with positive and negative codes can be used to form a binary code. In this case, for example, a 1-bit positive/negative code may be added to the variable-length coded LSB bits.

In addition, in the fifth embodiment, the case where an image is encoded by intra-coding is described. However, when inter-coding a moving image input using motion compensation or the like, the same effect can be obtained by using the method of this embodiment. .

In the fifth embodiment, the case where the input image is divided into blocks of 4 pixels horizontally and 4 pixels vertically is described, but the size of the blocks may be other sizes.

In the fifth embodiment, the scanning method within the block is described using FIG. 3(b), but other scanning order may be used as long as it is scanning from the low-frequency region to the high-frequency region.

In the fifth embodiment, as an example of the variable-length coding table, the description is made using FIG. 25, but other tables may be used.

In the fifth embodiment, the case where the number of L values is added to the beginning of the L column has been described, but EOB may be added to the end of the L column.

(This Embodiment 6) FIG. 30 is a block diagram showing the functional configuration of a decoding device to which a variable-length decoding method according to an embodiment of the present invention is used and a moving picture decoding method that uses this method is applied. Here, a case where a code string generated by the variable-length coding method of the present invention described in the fifth embodiment is input will be described.

As shown in FIG. 30, the decoding device 500c is composed of a variable length decoding unit 560, an inverse quantization unit 520, an inverse frequency transform unit 530, and a frame memory 540. The various parts constituting the decoding device 500c are the same as those of the encoding device 100c, and are implemented by a CPU, a ROM that stores programs and data executed by the CPU in advance, a memory that provides a working space when the programs are executed, or a memory that temporarily stores input code sequences and the like. The inverse quantization unit 520, the inverse frequency transform unit 530, and the frame memory 540 are the same as the above-mentioned decoding devices 500a and 500b, so their description is omitted, and the structure of the variable-length decoding unit 560 will be described in detail.

The variable length decoding unit 560 is composed of a code conversion unit 561, a table storage unit 562, and a coefficient generation unit 564.

The table storage unit 562 holds in advance a plurality of (8) variable-length coding (decoding) tables 5621a to 5621g, a limit value table 5622, and the like corresponding to the variable-length coding and the absolute value of the coefficient |L|. The variable length coding tables 5621a to 5621g have the same structure as the variable length coding tables 1641a to 1641g shown in FIG. 25, respectively, and the limit value table 5622 is the same as the limit value table 1642 shown in FIG. 26.

The code conversion unit 561 uses the tables held by the table storage unit 562 (variable-length coding tables 5621a to 5621g, and limit value table 5622) to perform variable-length coding on the input coded sequence from the variable-length coding to the number m and the number of coefficients in the L column. Conversion of the absolute value of the coefficient |L| and the R value of the R column. The conversion to the absolute value of the coefficient |L| is performed using variable-length coding tables 5621a to 5621g.

The coefficient generation unit 564 converts the input L column and R column into coefficient values, and performs two-dimensional processing according to a predetermined scanning method. When performing the conversion of the coefficient value, the coefficient value "0 of the value represented by R is generated according to the predetermined scanning order, and then the coefficient value of the value represented by L is generated. By repeating this process, it is performed from the L column and the R column. Conversion of column-wise coefficient values. Among them, if a zigzag scan is performed from the low-frequency area to the high-frequency area, it is converted into the coefficient block shown in FIG. 11 described above. The generated coefficient block is input to the inverse quantization unit 520.

Next, the decoding operation of each part of variable-length encoding section 560 will be described.

The following describes the encoding of the binary code input code string input to the code conversion unit 561 in the order of '1', '1', '010', '01 1', '00100', '0001100', '11', When it is "0100"0000100000", "0011001", "1100", "010000", and "00101101".

When the code conversion unit 561 starts decoding of variable-length coding, it decodes the number m of coefficients output from the encoding device 100c, and sets the number m of coefficients after decoding. Then, the code conversion unit 561 sets the table number k to "0" as the initial value of the variable-length coding table to be referred to. After that, the code allocating unit 163 refers to the limit value table 5622, and sets the limit value=4 (S103). When the number of coefficients m, the reference target of the variable-length coding table (in this case, the variable-length coding table 5621a), and the setting of the limit value are completed, the code conversion unit 561 starts from the front in the output order from the coding device 100c (that is, High frequency side) Read the absolute value of the coefficient |L|, use the variable-length coding table of the set sequence number to perform variable-length decoding on the read-out variable-length code to make the absolute value of the coefficient |L| . Once the decoding is completed, the code conversion unit 561 stores the absolute value of the coefficient |L| obtained by the decoding in a buffer (for example, a FILO buffer) not shown, and subtracts the number m of coefficients by '1', and judges to subtract Whether the measured number m is '0', that is, whether all the coefficients included in the L column are decoded.

If the number m of coefficients is not '0', it is judged whether the absolute value |L| of the previous coefficient after variable length decoding exceeds the limit value. If it is not exceeded, the code conversion unit 561 reads the subsequent variable-length code from the front, and uses the same variable-length code table as the previous to perform decoding, so that it becomes the absolute value of the coefficient |L|.

When the absolute value |L| of the immediately preceding coefficient after variable-length decoding exceeds the limit value, the code conversion unit 561 increments the table number k by "1". In this way, when the subsequent encoding of the absolute value of the coefficient |L| is performed, the variable-length encoding table suitable for encoding the absolute value of the long-encoded coefficient |L| with a smaller rate of change of the encoding length is referred to (for example, if The previous variable-length coding table is 5621a, please refer to 5621b). Once the increment of the table number k ends, the code conversion unit 561 refers to the limit value table 5622 and updates it to the subsequent limit value (for example, if the previous limit value is '4', then it is updated to '7'). In this way, only when the absolute value of the coefficient |L| exceeds the new limit value, it is possible to shift to a subsequent variable-length coding table suitable for the decoding of variable-length coding of long-coded coefficients with a smaller rate of change of the coding length.

Specifically, for the first variable-length code, refer to the variable-length code table 5621a with k=0. When referring to the variable-length code table 5621a, the variable-length code "1" corresponds to the input code sequence, and the absolute value of the coefficient |L| at this time becomes "1". Similarly, using the variable length coding table 5621a, if the conversion from the variable length coding to the absolute value of the coefficient |L| is sequentially performed, the variable length coding "1" is converted to the absolute value of the coefficient |L|='1 ', the variable length code '010' is transformed into the absolute value of the coefficient |L|='3', the variable length code '00100' is transformed into the absolute value of the coefficient |L|='4', the variable length code '0001100' is transformed into the absolute value of the coefficient |L|='12'.

Among them, when the absolute value of the relative coefficient |L| has a limit value of '4', the absolute value of the sixth coefficient |L| = '12', which exceeds the limit value. Therefore, when the code conversion unit 561 performs conversion to the absolute value |L| of the subsequent variable-length-coded coefficients, it uses the subsequent variable-length coding table 5621b of k=1, sets the limit value to 7, and converts it to The absolute value of the coefficient |L|. Therefore, the following seventh variable-length code '11' is transformed into the absolute value of the coefficient |L|='2'.

The following eighth variable-length code '0100' is transformed into the absolute value of the coefficient |L|='3', and the ninth variable-length code '000010000' is transformed into the absolute value of the coefficient |L|='31 '. Among them, when the absolute value of the relative coefficient |L| has a limit value of '7', the absolute value of the ninth coefficient |L| = '31', which exceeds the limit value. Therefore, when the code conversion unit 561 performs conversion to the absolute value |L| of the subsequent variable-length-coded coefficients, it uses the subsequent variable-length coding table 5621b of k=2, sets the limit value to 13, and converts it to The absolute value of the coefficient |L|. Even if the absolute value of the coefficient obtained when decoding the absolute value |L| of the seventh coefficient |L| reaches the limit value 7 or less again, the switch to the variable length coding table 5621a is not performed, and the variable length is used. The encoding table 5621b is converted.

The above process is repeated, and when the absolute value |L| of one block (m) coefficients is generated, they are arranged and replaced in the reverse order of first-in, first-out through the FILO buffer. Even the signs of the coefficients are arranged and replaced by the FILO buffer in the reverse order of first-in-last-out. However, the number is excluded from the arrangement replacement object. At this time, the same column as the sequence (that is, the sequence from low frequency to high frequency) as the L column shown in FIG. 24(a) is generated. The absolute value |L| of each coefficient of the L column after such permutation replacement is input to the coefficient generation unit 564. The code conversion unit 561 also decodes the R of the R column using the same processing as the absolute value of the coefficient |L|, and outputs the R column shown in FIG. 24(a) to the coefficient generating unit 564.

The coefficient generation unit 564 converts into coefficient values based on the input L column and R column. At this time, according to the predetermined scanning method, the coefficient value "0" of the value represented by R is generated, and then the positive and negative code is added to generate the coefficient value of the value represented by L. By repeating this process, it is performed from the L column and the R column to the Conversion of coefficient values. Among them, as shown in FIG. 11, when the Z-scan is performed from the low-frequency region to the high-frequency region, the L column shown in FIG. 24(a) and the R column shown in FIG. 24 are converted into coefficient blocks. The generated coefficient block is input to the inverse quantization unit 520.

As described above, in the variable-length decoding method according to the sixth embodiment of the present invention, in the decoding step, a plurality of variable-length coding (decoding) tables used in decoding are switched in one direction, and the switched variable-length coding is used at the same time. The table decodes the variable-length code of the arithmetic code sequence into coefficient values other than '0' related to the frequency region in a predetermined order. Then, in the coefficient value conversion step, the generated coefficient value is converted into the coefficient value in the block. Wherein, the structure of each table is to make the rate of change of the coding length of the relative coefficient value different, so that the coding length of the minimum coefficient value is increased in the order of the number assigned to each table, and the coding length of the maximum coefficient value is The sequence number sequence becomes shorter. The limit value is set according to the adaptation characteristics of each table in which the coding length of the corresponding coefficient value is shorter than that of other tables. The variable-length codes of the coded sequence are arranged in order from high-frequency components to low-frequency components, the decoding step is decoded into coefficient values in the sequence of the coded sequence, and the decoded codes are sequentially output from the rear end of the coded sequence. Coefficient values, thereby generating a coefficient value sequence of coefficient values, and the coefficient generation step scans the coefficient values in the order of arrangement of the coefficient value sequence.

In the encoding step, when the absolute value of the decoded coefficient exceeds the limit value, the table used when decoding the variable-length encoding of the decoding target is switched to a table with a sequence number greater than the sequence number assigned to the table, and the subsequent variable The length code is decoded into coefficient values.

Through the above operations, by using the variable-length decoding method of the present invention, it is possible to correctly decode the coded string encoded by the variable-length encoding method of the present invention.

In the above-mentioned sixth embodiment, combined with the fifth embodiment, when the absolute value of the previous coefficient |L| after the same decoding exceeds the limit value, the table number k is increased by 1, and the variable-length coding table limit of the latter number is used for decoding , But as long as the method of switching the table used in encoding is the same, it can also be skipped and switched to a variable-length encoding table adapted to the absolute value of its coefficient |L|. In this case, it is only necessary to set the limit value to a limit value that matches the variable length code table.

In the sixth embodiment, as an example of a variable-length coding table, the description is given using FIG. 25, but as long as it is the same table used for coding, another table may be used. In addition, the case when 8 variable length coding tables are used is explained, but 2 to 6 variable length coding tables can also be used, or more than 8 can be used, and multiple limit values are used, and each limit value is exceeded each time. Switch the variable-length encoding table at time. However, the structure and limit value of the variable-length coding table at this time must be the same as those used during coding.

In addition, in the sixth embodiment, the coefficient values are divided into absolute values and positive and negative codes to be coded, and the absolute value of the coefficient values are constructed in a form without positive and negative codes (absolute values). Each variable-length coding table is also used. The coefficient value can be coded in the format with positive and negative codes. In this case, the format with positive and negative codes can be used to form a binary code. In this case, for example, a 1-bit positive/negative code may be added to the variable-length coded LSB bits.

In addition, in the sixth embodiment, when the L value exceeds the limit value, the variable-length coding table is switched, but when the absolute value of the coefficient |L| is larger in the order (that is, the order from the high frequency side) is decoded , Use a variable-length coding table with a large sequence number, and when the absolute value of the decoded coefficient |L| is less than the limit value, it can also be switched to a variable-length coding table with a small sequence number.

In this sixth embodiment, the case of decoding a coded sequence generated by intra-coding is described. However, when using motion compensation or the like to decode a coded sequence generated by inter-coding a moving image input, use this embodiment The same effect can also be obtained by way of method.

In the sixth embodiment, the case where the input image is divided into blocks of 4 horizontal pixels and 4 vertical pixels to be coded has been described, but the block size may be another size.

In the sixth embodiment, the scanning method within the block is described using FIG. 11, but as long as the scanning method is the same as the scanning method used in encoding, another scanning order may be used.

(Embodiment 7) In the following, the variable-length encoding method, variable-length decoding method, variable-length encoding device, variable-length decoding device, moving image encoding method, moving image decoding method, and other methods of implementing the present invention will be described. Examples of moving image encoding devices and moving image decoding devices.

The program for realizing the encoding device or the decoding device described in each of the above-mentioned embodiments is recorded in a storage medium such as a floppy disk, so that the processing described in each of the above-mentioned embodiments can be easily implemented by an independent computer system.

FIG. 32 is a schematic diagram illustrating the implementation of a computer system using a floppy disk storing a program, where the program is used to execute the moving image coding method of the above-mentioned Embodiments 1, 3, and 5 or the dynamics of the Embodiments 2, 4, and 6 Image decoding method processing.

FIG. 32(b) shows the appearance, cross-sectional structure, and the floppy disk when viewed from the front of the floppy disk, and FIG. 32(a) shows an example of the physical format of the floppy disk as the main body of the recording medium. The floppy disk FD is built in a floppy disk cartridge F. A plurality of concentric tracks Tr are formed on the surface of the floppy disk from the outer circumference to the inner circumference, and each track is divided into 16 sectors Se in the angular direction. Therefore, in the floppy disk storing the above-mentioned program, the moving image encoding device as the above-mentioned program is recorded in the allocated area of the above-mentioned floppy disk.

FIG. 32(c) shows the structure of recording and reproducing for executing the above-mentioned program on the floppy disk FD. When the program is recorded on the floppy disk FD, a video encoding device or a video decoding device as the program is written from the computer system Cs via the floppy disk. When constructing the above-mentioned moving image encoding device in a computer system using a program in a floppy disk, the program is read from the floppy disk using a floppy disk drive and transferred to the computer system.

In the above description, the case where a floppy disk is used as a recording medium is described, but an optical disk can also be used in the same way. In addition, the recording medium is not limited to this, as long as the program can be recorded, an IC card, a ROM memory, etc. can be implemented.

Hereinafter, application examples of the moving picture prediction method, moving picture coding device, and moving picture decoding device shown in the above-mentioned embodiments and a system using them will be described.

FIG. 33 is a block diagram showing the overall configuration of the content supply system ex100 for realizing the content distribution service. The communication service provision section is divided into desired sizes, and base stations ex107 to ex110, which are fixed wireless stations, are installed in each cell.

The content supply system ex100 uses, for example, a computer ex111, a PDA (Personal Digital Assistant) ex112, a camera ex113, a mobile phone ex114, and a mobile phone ex115 with a camera through an Internet service provider ex102, a telephone network ex104, and base stations ex107 to ex110. Wait for each machine to connect to the Internet ex101.

However, the content supply system ex100 is not limited to the combination shown in FIG. 33, and can be connected in any combination. In addition, each device may be directly connected to the telephone network ex104, not through the base stations ex107 to ex110 which are fixed wireless stations.

The camera ex113 is a device that can perform dynamic shooting such as a digital video camera. The mobile phone can be any type of mobile phone, for example, PDC (Personal Digital Communications) method, CDMA (Code Division Multiple Access) method, W-CDMA (Wideban-Code Division Multiple Access) method, or GSM (Global System for Mobile Communications) ) Method, PHS (Personal Handyphone system), etc.

The streamline server ex103 is connected from the camera ex113 through the base station ex109 and the telephone network ex104, and the camera ex113 can be used to efficiently transmit and so on based on the encoded data sent by the user. The encoding process of the captured data may be performed by the camera ex113, or may be performed by a server or the like that performs data transmission processing. In addition, the motion data captured by the camera 116 may be sent to the streaming server ex103 via the computer ex111. The camera ex116 is a device such as a digital camera that can capture still images and moving images. In this case, the encoding of the moving image data may be performed using the camera ex116 or the computer ex111. The encoding process is performed by the LSI ex117 included in the computer ex111 and the camera ex116. In addition, the software for image encoding and decoding may be installed in any storage medium (CD-ROM, floppy disk, hard disk, etc.) that can be read by the computer ex111 or the like. Alternatively, the mobile phone ex115 with a camera may be used to transmit the moving image data. The moving image data at this time is the data encoded by the mobile phone ex115 through the LSI.

The content supply system ex100 performs the same encoding processing as the above-mentioned embodiment on the content captured by the user using the camera ex113, the camera ex116, etc. (for example, the image of the live music is captured, etc.), and sends it to the mobile server ex103. On the other hand, the mobile The server ex103 sends the above-mentioned content data to the requesting client. As the client, there are a computer ex111, a PDA ex112, a camera ex113, a mobile phone ex114, etc. that can decode the above-mentioned encoded data. In this way, the content supply system ex100 is a system that can receive and replay encoded data on the client, and realize personal playback by receiving, decoding, and replaying it in real time on the client.

The encoding and decoding performed by each device constituting the system may use the image encoding device or image decoding device described in each of the above-mentioned embodiments.

An example of this will be explained using a mobile phone.

FIG. 34 shows a schematic diagram of a mobile phone ex115 using the moving picture prediction method, moving picture coding device, and moving picture decoding device described in the above embodiment. The mobile phone ex115 has: an antenna ex201 that receives and transmits radio waves to and from the base station ex110; an imaging unit ex203 that can capture images and still images of a CCD camera, etc.; and is used to represent the images captured by the imaging unit ex203 and the images received by the antenna ex201 A display unit ex202 such as a liquid crystal display and other decoded data; a main unit composed of a group of operation keys ex204; a sound output unit ex208 such as a speaker for outputting sound; a sound input unit ex205 such as a microphone for inputting sound; A recording medium ex207 that stores captured moving image or still image data, etc., encoded data or decoded data; and a slot unit ex206 in which the recording medium ex207 can be installed in the mobile phone ex115. A flash storage element is stored in the recording medium ex207, which is a type of EEPROM (Electrically Erasable and Programmable Read Only Memory) that can be electrically rewritten and erased in a plastic box such as an SD card.

Next, the mobile phone ex115 will be described with reference to FIG. 35. In the mobile phone ex115, the main control unit ex311, which uniformly controls the various parts of the main unit having the display unit ex202 and the operation unit ex204, is connected to the power supply circuit unit ex310, the operation input control unit ex304, and the image encoding unit ex312 through the synchronization bus ex313. , Camera interface unit ex303, LCD (Liquid Crystal Display) control unit ex302, image decoding unit ex309, demultiplexing unit ex308, recording and playback unit ex307, modem circuit unit ex306, and sound processing unit ex305.

The power supply circuit unit ex310 supplies power from the battery pack to each part when the call is ended and the power key is turned on by the user's operation to activate the digital mobile phone ex115 with the camera in an operational state.

According to the control of the main control unit ex311 formed by the CPU, ROM, RAM, etc., the mobile phone ex115 uses the sound processing unit ex305 to convert the sound signal collected by the sound input unit ex205 into digital sound data during the voice call mode. The modulation and demodulation circuit unit ex306 performs spectrum diffusion processing on it, digital-to-analog conversion processing and frequency conversion processing are performed by the transmitting and receiving circuit unit ex301, and then transmission is performed via the antenna ex201. In addition, the mobile phone ex115 amplifies the signal received through the antenna ex201 in the voice call mode, performs frequency conversion processing and analog-to-digital conversion processing, uses the modem circuit unit ex306 to perform inverse spectrum diffusion processing on it, and uses the voice processing unit ex305 After being converted into an analog audio signal, it is output through the audio output unit ex208.

In addition, when sending an email in the data communication mode, the text data of the email input by operating the operation key ex204 of the main unit is sent to the main control unit ex311 via the operation input control unit ex304. The main control unit ex311 performs spectrum diffusion processing on the text data through the modem circuit unit ex306, performs digital-to-analog conversion processing and frequency conversion processing through the receiving and transmitting circuit unit ex301, and transmits it to the base station ex110 through the antenna ex201.

When transmitting image data in the data communication mode, the image data captured by the imaging unit ex203 is supplied to the image encoding unit ex312 through the imaging interface unit ex203. When the image data is not sent, the image data captured by the imaging unit ex203 can be directly displayed on the display unit ex202 through the imaging interface unit ex203 and the LCD control unit ex302.

The image encoding unit ex312 has the image encoding device described in the present invention. The image data supplied from the imaging unit ex203 is compressed and encoded using the encoding method used by the image encoding device shown in the above-mentioned embodiment, and converted into encoded image data. It is sent to the demultiplexing unit ex308. At the same time, the mobile phone ex115 transmits the sound collected by the sound input unit ex205 when the camera unit ex203 is used for shooting, as digital audio data through the sound processing unit ex305, and sends it to the demultiplexing unit ex308.

The demultiplexing unit ex308 multiplexes the encoded image data supplied from the image encoding unit ex312 and the audio data supplied from the sound processing unit ex305 in a predetermined manner, and uses the modem circuit unit ex306 to multiplex the resulting multiplexed data The spectrum diffusion process is performed, the digital-analog conversion process and the frequency conversion process are performed by the receiving and transmitting circuit unit ex301, and then the antenna ex201 is used for transmission.

When receiving data linked to a moving image file such as a homepage in the data communication mode, the modem circuit unit ex306 is used to perform spectrum diffusion processing on the received signal received from the base station ex110 via the antenna ex201, and the resulting multiplexed data is transmitted To the demultiplexing unit ex308.

When decoding the multiplexed data received through the antenna ex201, the demultiplexing unit ex308 separates the multiplexed data into an encoded bit stream of image data and an encoded bit stream of audio data. The bus ex313 supplies the encoded image data to the image decoding unit ex309, and at the same time supplies the audio data to the sound processing unit ex305.

The image decoding unit ex309 has the image decoding device described in the present invention, and decodes the coded bit stream of the image data by the decoding method corresponding to the coding method shown in the above-mentioned embodiment to generate playback moving image data, and the LCD control unit ex302 This is supplied to the display unit ex202, so that, for example, the moving image data contained in the moving image file linked to the homepage can be displayed. At the same time, the sound processing unit ex305 converts the audio data into an analog sound signal and supplies it to the sound output unit ex208, so that, for example, the sound data contained in the moving image file linked to the homepage can be reproduced.

However, it is not limited to the above system examples. Recently, digital broadcasting using satellites and surface waves has become a topic. As shown in FIG. 36, the digital broadcasting system can also be equipped with at least one of the image encoding device or image decoding device of the above-mentioned embodiment. . Specifically, the broadcasting station ex409 communicates the coded bit stream of the video information by radio waves or transfers it to the broadcasting satellite ex410. The broadcasting satellite ex410 that has received the information sends the broadcasting radio waves, and the home antenna ex406 with satellite broadcasting receiving equipment receives the radio waves. The encoded bit stream is decoded and reproduced by a television (receiver) ex401 or set-top box (STB) ex407. put. In addition, the playback device ex403 that reads and decodes the encoded bit stream recorded on the storage medium ex402 such as CD and DVD as a recording medium can also be equipped with the image decoding device shown in the above-mentioned embodiment. In this case, the reproduced video signal is displayed on the monitor ex404. It is also conceivable to install an image decoding device in the set-top box ex407 connected to the cable ex405 for cable TV or the antenna ex406 for satellite/surface wave broadcasting, and to reproduce it on the monitor ex408 of the TV. At this time, the set-top box may not be installed, and the image decoding device may be installed in the television. In addition, the vehicle ex412 with the antenna ex411 receives signals from the satellite ex410 or the base station ex107, etc., and can reproduce moving images on a display device such as the car navigation system ex413 of the vehicle ex412.

In addition, the image encoding device described in the above-mentioned embodiment may be used to encode an image signal and record it on a recording medium. As specific examples, there are recording devices ex420 such as a DVD recording device that records image signals on a DVD disk ex421 and a disk recording device that records on a hard disk. It can also be recorded on the SD card ex422. If the recording device ex420 has the image decoding device shown in the above embodiments, the image signals recorded on the DVD disc ex421 and SD card ex422 can be reproduced and displayed on the monitor ex408.

The structure of the car navigation system ex413 can be considered. For example, in the structure shown in FIG. 36, the structure except the camera unit ex203, the camera interface unit ex303, and the image encoding unit ex312 can also be considered. The computer ex111 and the television (receiver) ex401 can also be considered. Wait.

For terminals such as the mobile phone ex411, in addition to a receiving and transmitting terminal having both an encoder and a decoder, three embodiments of a transmitting terminal with only an encoder and a receiving terminal with only a decoder can also be considered.

In this way, the variable-length coding method shown in the above-mentioned embodiment is used. Variable length decoding method. The variable-length encoding device, variable-length decoding device, moving image encoding method, moving image decoding method, moving image encoding device, and image decoding device using these methods can be applied to any of the above-mentioned machines and systems, thereby obtaining The effects described in the above-mentioned embodiment.

Regarding all the embodiments of the present invention, the present invention is not limited to the above-mentioned embodiments, and various deformations or modifications are possible as long as they do not depart from the scope of the present invention.

In addition, the variable-length encoding device and variable-length decoding device of the above-mentioned Embodiments 1 to 6 scan the coefficient values in order from the low-frequency component to the high-frequency component. However, as a modified example of the present invention, it may be The structure of the coefficient value is scanned sequentially from the component to the low-frequency component. In this case, processing such as replacement of coefficient values can be omitted.

Industrial Applicability The variable-length encoding method and the variable-length decoding method related to the present invention are applicable to computer devices such as mobile phones, portable information terminals, television playback devices, television receivers, or set-top boxes, for moving images in a block unit of a predetermined size. The coefficient values in each block after the frequency conversion of the image data are coded or decoded.