CN1268135C - Method, device and recording medium for encoding, and method, device and recording medium for decoding - Google Patents

Abstract

It has been very difficult to conduct real-time encoding and decoding, because the necessary quantity of arithmetical processing is very large when inputted image/voice data are encoded and when encoded image/voice data are decoded by a computer. The invention provides a 1st encoding method wherein signal form conversion, orthogonal conversion and variable length encoding are continuously carried out in units of predetermined small regions in a frame, and the frequency of memory access is reduced to thereby realize speed processing; a 2nd encoding method wherein the processing time is shortened by eliminating the orthogonal conversion calculation by using the coefficients subjected to the orthogonal conversion; and a 3rd encoding method wherein the number of registers which are used in the addition and substraction performed in the orthogonal conversion, etc. is reduced, and the frequency of memory access is decreased to realize high speed calculation. The invention also provides a decoding method wherein a table size is not large in variable length decoding, the maximum frequency of table access for one code word is two, and a plurality of code words are decoded by a single table access to realize high speed decoding.

Description

Encoding method, encoding device and recording medium, and decoding method, decoding device and recording medium

field of invention

The present invention relates to an encoding method, encoding device and recording medium for encoding input image data, and also relates to a decoding method, decoding device and recording medium for decoding encoded image data.

related technology

According to improvements in digital signal processing technology, devices capable of compressing, encoding, and recording digital image signals and decoding, decompressing, and reproducing digital image signals have been realized; and DVC (Digital Video Cassette) can be taken as an example. The format of DVC is described in the specification of "Customer Use Digital VCR Using 6.3mm Tape" edited by the HD Digital VCR Association.

In a digital image device including DVC, since input image data is large, the amount of data is reduced by compression and encoding, and the encoded image data is decoded to reproduce an original image by decoding, as is generally practiced.

Fig. 25 is a block diagram showing the structure of an encoding section in a conventional digital image device. In Fig. 25, reference numeral 2501 represents a first input terminal, reference numeral 2502 represents a first signal format conversion part, reference numeral 2503 represents a switch, reference numeral 2504 represents a second input terminal, reference numeral 2505 represents a second signal format conversion part, and reference numeral 2506 represents a repeating A shuffling section, reference numeral 2507 denotes an orthogonal transformation section, reference numeral 2508 denotes a variable-length coding section, and reference numeral 2509 denotes an encoded image output terminal.

An example of an image signal to be encoded for recording is a YUV422 component signal which includes a luminance (Y) signal, a first color difference (U) signal and a second color difference (V) signal at a ratio of 4:2:2. When this YUV422 component is input from the first input terminal 2501, it is converted into a YUV411 component signal (hereinafter referred to as a YUV format signal) by the first signal format conversion part 2502, which includes four Y signals, a U signal and a V The signal, as the amount of pixels per frame, is shown in Fig. 26.

On the other hand, an image signal other than a YUV format signal, for example, a digital RGB component signal (hereinafter referred to as an RGB format signal), which includes a red (R) signal, a green (G) signal, and a blue (G) signal, Sometimes it becomes an input signal. In this case, it is required that the RGB format signal input from the second input terminal 2504 be converted into a YUV format signal by the second signal conversion section 2505 . The RGB format signal has horizontal pixels at a ratio of 4:4:4 per frame, as shown in FIG. 27 . In the second signal format conversion section 2505, by using RGB pixel values for the respective coordinates, obtain

Y＝0.30R+0.59G+0.11B

U=0.70R-0.59G-0.11B

V=-0.30R-0.59G+0.89B;

In addition, the number of horizontal pixels of U and V signals will be reduced to 1/4 to obtain YUV format signals.

The YUV format signal obtained by the second signal format converting section is supplied to the rearranging section 2506 through the switch 2503, and is processed in the same way as shown in the figure.

The Y signal, U signal, and V signal of the YUV signal sent to the rearrangement section 2506 are divided into blocks including M horizontal pixels and N vertical pixels (generally, M=N=8). Four blocks of the Y signal, one block of the U signal, and one block of the V signal located in the same area of the display screen are defined as a macro block. By using this macroblock as a unit, a sync block serving as a coding unit is formed from 5 macroblocks located at separated positions in a frame, as shown in FIG. 28 .

The rearranged image signal is sent to the orthogonal transform section 2507, and undergoes orthogonal transform (generally, discrete cosine transform) in block units. The image signal subjected to orthogonal transformation is sent to variable length encoding section 2508, and encoded so that the code amount in the above-mentioned sync block is not more than a certain value. By performing the rearrangement described above, the amount of codes required for each sync block is averaged for the entire frame, and encoding can be performed efficiently; moreover, even if errors still exist during reproduction, they are scattered over the entire display screen, thereby The error becomes less significant. An encoded image signal is output from an output terminal 2509 for encoded image.

The variable-length encoding section performs variable-length encoding on a set of zeroruns, ie, the number of consecutive 0s, and values, ie, non-zero coefficients following the zeroruns, in the coefficient string subjected to the orthogonal transform. Fig. 29 is a variable length coding table for DVC.

In the variable length code for DVC, the code length is not less than 3 bits, and not more than 16 bits, and the code length is uniquely determined by its high-order 8 bits. In addition, it is also characterized in that, when the probability of occurrence is high, a codeword having a shorter code length is allocated. The end of a series of codewords is called EOB.

Next, referring to Figs. 29 and 30, the variable length encoding operation will be described.

Assume that, in FIG. 30, encoding of coefficient A (coefficient value 9) has been completed. The next part to be coded is 3 consecutive 0s, followed by the non-zero coefficient 2 (coefficient group B). At this point, the zero run is 3 and the value is 2. According to FIG. 29, the coefficient group B is encoded as "111001000".

After the coefficient group B, the coefficient C located after the coefficient group B is encoded. Since "0" does not exist between the coefficient group B and the coefficient C, the zero run is 0 at this time. Since the value is -6, the coefficient C is encoded as "101111" as shown in FIG. 29 .

Fig. 31 is a block diagram showing decoding for decoding a variable-length coded image signal to obtain an ordinary image signal. In FIG. 31, reference numeral 3101 denotes an encoded image input terminal, reference numeral 3102 denotes a variable length decoding section, reference numeral 3103 denotes an orthogonal inverse transform section, reference numeral 3104 denotes a deshuffling section, and 3105 denotes a first signal A format converting section, reference numeral 3106 denotes a first signal output terminal, reference numeral 3107 denotes a second signal format converting section, and reference numeral 3108 denotes a second signal output terminal.

The coded image signal (codeword string) input to the coded image input terminal 3101 is decoded by the variable length decoding section 3102 . In the case of decoding a codeword string based on the variable length table of FIG. 29, the following methods can be considered.

The first method is to scan the codeword string bit by bit until its code length (codeword) is determined, and according to the table, output the zero-run sum of the determined codeword. Through Figure 32, this method is described.

In FIG. 32, the 3-bit data at the head of the code word is regarded as a candidate, and it is judged whether to determine the code length (corresponding to the description indicated by code a in FIG. 32). If the code length is not determined, another code word having the next 1-bit data is regarded as a candidate, and it is judged whether to determine the code length (corresponding to the description represented by code b in FIG. 32 ). This operation is repeated until the code length is determined, thereby determining the codeword (corresponding to the description indicated by code c in FIG. 32).

Next, for the codeword that has been determined, this table is referred to, thereby obtaining its zero-run sum value (corresponding to the description represented by code d in Fig. 32).

As a result, one codeword has been decoded; therefore, the length of the codeword (7 bits in this example) is deleted from the header of the codeword string, and the header of the next codeword is taken out.

Repeat the above operations until EOB appears again. (variable length decoding method 1)

As a second method, a method of preparing a table for all codewords can be used. In the case of DVC, since the maximum code length is 16, encoding can be performed immediately by referring to a table in which 16-bit data is input, and the code length, zero-run, and value corresponding to each bit pattern are output, as shown in Fig. 33 Shown (variable length decoding method 2).

The data subjected to variable length decoding is decoded into a YUV format signal in units of blocks by the orthogonal inverse transform section 3103 . Thereafter, the operation opposite to the rearrangement is performed by the de-rearrangement section 3104, and the signal is converted into a YUV422 component signal, for example, the signal is converted into a YVU422 component signal by the de-rearrangement section 3104, and output from the first signal output terminal 3106 . On the other hand, when the RGB format is output, the RGB format signal is obtained from the YUV format by the second signal format converting section 3107 and output from the second signal output terminal 3108 .

The above-described processing can also be performed by using an arithmetic processing device, such as a computer. In other words, the above-mentioned encoding and decoding processes are performed by software, and the processing can be performed by using a computer in which the external memory 3401, including a cache memory, registers, and an arithmetic unit, is connected to the external memory 3401 through the data bus 3403 as shown in FIG. The CPU3402 and the hard disk 3404 are connected to each other. By implementing encoding and decoding processing by software, image data on a recording medium (such as a hard disk) connected to a computer can be encoded and recorded on the DVC; and the encoded image data recorded on the DVC can be directly extracted to the computer and undergoes a decoding process to be indicated on a monitor connected to the computer.

However, when the above-described encoding and decoding are performed by a computer, the following problems occur.

When encoding image data, or decoding encoded image data by using a computer, it is required to calculate a large amount of data in a very short time.

For example, when encoding or decoding an NTSC image signal, (1) during encoding, for 1 frame of image data containing 720 horizontal pixels and 480 vertical pixels, it is necessary to perform signal format conversion, Orthogonal transform and variable length encoding, and (2) during decoding, variable length decoding, orthogonal inverse transform, and signal format conversion need to be performed within 1/30 second for encoded 1-frame image data. Otherwise, encoding and decoding cannot be achieved in real time without frame dropout.

FIG. 35 shows data flow when an RGB format signal is input, and when encoding processing is performed by a computer in real time as in FIG. 25 . The input RGB format signal is mapped in the area of the external memory 3401 (corresponding to the dotted line shown by reference numeral 3551). The mapped RGB format signal is delivered to the CPU 3402 (3552), processed to convert the signal into a YUV format signal (3553), and written to another area of the external memory 3401 at a time (3554). Next, according to the address obtained by relying on the rearrangement mode, the image signal is read from the external memory 3401 in block units, transferred to the COU202 (3555) and subjected to orthogonal transformation and vertical length encoding (3556), thereby outputting the signal via the data bus 3403 Encoded image signal (3557).

When the decoding process shown in FIG. 31 is executed by using a computer, the encoded image signal (corresponding to the dotted line indicated by reference numeral 3651 in FIG. 36 ) transmitted through the data bus 3403 is taken out in the CPU 3402, subjected to variable length decoding and positive processing. Inverse transform (3652) and pass to external memory 3401 once to perform de-reordering (as shown in Figure 36). Next, the signal is transferred from the external memory 3401 to the CPU 3402 according to the address obtained by relying on the de-rearrangement mode, thereby undergoing signal format conversion (3654), being converted into an RGB format signal by the CPU 3402 (3655), and again being transferred to the external memory 3401 ( 3656). Image display and recording can be performed by mapping image signals stored in the external memory 3401 on a display device such as a VRAM.

Transferring data between the external memory 3401 and the CPU 3402 generally takes longer than transferring data between registers or between a cache memory inside the CPU and a register. In the conventional example, four data transfers are performed between the external memory 3401 and the CPU 3402, and depending on the architecture of the computer, this impairs real-time image processing.

Next, in the case of encoding and decoding using orthogonal transform, it is necessary to perform orthogonal transform on encoding and decoding. However, since the orthogonal transformation for general image signals is formed by complicated calculations including multiplication of irrational numbers, a long calculation time or a large-scale circuit is required.

Even conventional examples often employ butterfly calculations, in which the sum and difference of two inputs are calculated, to increase the speed of orthogonal transform calculations. In this butterfly calculation, for two inputs X0 and X1, an output value Y0 is calculated which is X0+X1 and an output value Y1 which is X0-X1. When executed on a computer, the calculations described below are processed.

(1) Set the input value X0 in register A.

(2) Set the input value X1 in register B.

(3) Set the output (X1) of register B in register C (creating a copy of X1).

(4) Add the output (X0) of the register A to the output (X1) of the register B, and set the result (calculate X0+X1) in the register B.

(5) Subtract the output (X1) of register C from the output (X0) of register A, and set the result (calculate X0-X1) in register A.

(6) The output of the output register B is taken as Y0.

(7) The output of the output register A is taken as Y1.

Although, the butterfly calculation is very simple as described above, it requires at least three registers to obtain two calculation outputs when the calculation is performed.

On the other hand, 8-dimensional orthogonal transforms are often used in image coding, and in this case, 4 sets of 2-input butterfly calculations need to be performed simultaneously. For this purpose, a total of 12 registers are required.

However, Intel's CPUs, which are most commonly used in personal computers, don't have that many registers; even the latest MMX-compatible CPUs have only 4 integer registers and 8 MMX registers. To compensate for the lack of registers, the data in some registers is kept on memory. Since the butterfly calculation described above is repeatedly performed for orthogonal transformation, register values are often saved on memory, thereby greatly delaying execution time.

As described above, saving on the memory during the butterfly calculation causes a serious problem of increasing the calculation time for encoding and decoding image signals and audio signals.

Furthermore, when the above-mentioned variable length decoding method 1 and variable length decoding method 2 are programmed for variable length decoding and executed using a computer, the following problems occur.

In the case of the variable length decoding method 1, it is necessary to use a branch instruction to judge whether a codeword can be determined at each scan. However, when Intel's Pentium, which is the CPU that dominates today's computers, is used, every time a branch instruction is executed, processing information for high-speed processing obtained before the branch information is cleared. Therefore, it is necessary to obtain the above-mentioned processing information to perform subsequent calculations, and during this period, the processing is interrupted. In the case of variable-length decoding of DVC, when scanning is performed in units of bits, a branch instruction must be executed a maximum of 11 times, and an average of 3 times for one codeword.

In other words, in the case of variable length decoding method 2, the required size of the table requires the storage of three parameters for each input bit pattern, namely code length, zero run and value. When it is assumed that each of these three parameters has 1 bit, the size of the table becomes 3*216=192 kilobits. However, since the size of the cache memory provided in the CPU is about 16 kilobits in the case of the latest Pentium, all the tables described in the variable-length decoding method 2 cannot be stored in the above-mentioned cache memory. in buffer memory. For this reason, there is a high possibility that the contents of the table to be referred to are not stored in the super cache memory. If the table content is not contained in the cache, it must be transferred from external memory to the cache, greatly increasing processing time.

Even in both cases, problems arise due to certain difficulties in conventional encoding and decoding using a computer in real time.

Summary of the invention

In view of the conventional problems, the present invention aims to provide a high-speed encoding method, encoding apparatus, and encoding program for performing encoding by dividing input image data having a predetermined signal format into block units and performing orthogonal transformation in the above-mentioned block units. Coding: The present invention also provides a high-speed decoding method, decoding device and decoding program, which are used to obtain image data by performing orthogonal inverse transformation and signal format transformation on coded data.

In order to achieve the above object, claim 1 of the present invention is an encoding method for encoding input image data in a predetermined signal format by dividing said image data into block units and performing orthogonal transformation in said block units, include:

a macroblock forming step for forming a macroblock from said plurality of blocks,

a signal format conversion step for converting said image data in said predetermined signal format into image data in another signal format,

an orthogonal transformation step for orthogonally transforming said image data subjected to said signal format conversion, and

an encoding step for encoding the output of said orthogonal transform step, wherein

The signal format converting step, the orthogonal transforming step, and the encoding step are successively performed in units of macroblocks.

Claim 4 of the present invention is the encoding method according to claim 1, wherein the input image data includes red, green, and blue signals, and the image data obtained after the signal format conversion includes luminance, A color-difference signal and a second color-difference signal.

Claim 7 of the present invention is the encoding method as claimed in claim 1, wherein said input image data includes brightness, first color difference and second color difference signals, and the image obtained after said signal format conversion The data includes luminance, first color difference and second color difference signals, which have a different structure than before said conversion.

Claim 10 of the present invention is an encoding method for encoding input image data in a predetermined signal format by dividing said image data into block units and performing orthogonal transformation in said block units, comprising:

a pixel value detection step for detecting input pixel values in said block and judging whether all pixel values in said block are equal or approximately equal or not equal, and

Orthogonal transformation step, wherein, in the block, it is judged by the pixel value detection step whether all the pixel values are equal or approximately equal, in the block, a DC coefficient component value is generated from the value of one pixel and all The AC coefficient component values are set to zero and ordinary orthogonal transform calculations are performed in other blocks.

Claim 13 of the present invention is an encoding method for encoding input image data in a predetermined signal format by dividing said image data into block units and performing orthogonal transformation in said block units,

Assuming that the horizontal direction or the vertical direction is referred to as a first direction, and the other direction is referred to as a second direction, and assuming that the two-dimensional block has m×n pixels, along the first direction has m pixels and along the second direction has n pixels,

The methods include:

a first orthogonal transform step for orthogonally transforming said input pixel values in said two-dimensional block in m pixel units along said first direction,

a pixel value detecting step for detecting the coefficient component values obtained in the first orthogonal transform step in n coefficient units along the second direction, and

The second orthogonal transform step, wherein, among the coefficients detected in the pixel value detecting step, a DC coefficient component value is generated from a value of one of the n coefficients, and all AC coefficient component values are set to is zero, and ordinary orthogonal transform calculations are performed in other coefficients of the n coefficients, wherein the coefficients include the n coefficients along the second direction and having the same or approximately the same coefficient values.

Claim 16 of the present invention is an encoding method for encoding input image data in a predetermined signal format by dividing said image data into block units and performing orthogonal transformation in said block units,

Assuming that the horizontal direction or the vertical direction is referred to as a first direction, and the other direction is referred to as a second direction, and assuming that the two-dimensional block has m×n pixels, along the first direction has m pixels and along the second direction has n pixels,

The methods include:

a first orthogonal transform step for orthogonally transforming said input pixel values in said two-dimensional block in m pixel units along said first direction,

a pixel value detecting step for detecting the coefficient component values obtained in the first orthogonal transform step in n coefficient units along the second direction, and

The second orthogonal transform step, wherein, among the coefficients detected in the pixel value detecting step, the DC coefficient component values and all the AC coefficient component values for the n coefficients are set to zero, and in the Ordinary orthogonal transform calculations are performed on other coefficients of the n coefficients, wherein said coefficients include said n coefficients along said second direction and having coefficient values, all of which are zero or approximately zero.

Claim 22 of the present invention is an encoding method for encoding input image data in a predetermined signal format by dividing said image data into block units and performing orthogonal transformation in said block units,

When an output value Y0, i.e., X0+X1 and an output value Y1, i.e., X0−X1 are generated from two input values X0 and X1 by at least an orthogonal transformation calculation,

The methods include:

First, an addition step for adding the X0 to the X1 to produce a new X1,

Second, a doubling step for doubling the X0 to produce a new X0, and

Third, a subtraction step for subtracting said new X1 from said new X0 to produce an updated X0, wherein

The new X1 is used as output value Y0, and the updated X0 is used as output value Y1.

Claim 25 of the present invention is an encoding method for encoding input image data in a predetermined signal format by dividing said image data into block units and performing orthogonal transformation in said block units,

When an output value Y0, i.e., X0+X1 and an output value Y1, i.e., X0−X1 are generated from two input values X0 and X1 by at least an orthogonal transformation calculation,

The methods include:

First, a subtraction step for subtracting said X1 from said X0 to produce a new X0,

Second, a doubling step for doubling the X1 to produce a new X1, and

Third, an addition step of adding said new X0 to said new X1 to generate a new X1, wherein

The new X1 is used as output value Y0, and the updated X0 is used as output value Y1.

Claim 28 of the present invention is an encoding method for encoding input image data in a predetermined signal format by dividing said image data into block units and performing orthogonal transformation in said block units,

When an output value Y0, i.e., X0+X1 and an output value Y1, i.e., X0−X1 are generated from two input values X0 and X1 by at least an orthogonal transformation calculation,

The methods include:

First, a first addition step for adding said X0 to said X1 to produce a new X1,

Next, a second addition step for adding said X0 to said X0 to produce a new X0, and

Third, a subtraction step for subtracting said new X1 from said new X0 to produce an updated X0, wherein

The new X1 is used as output value Y0, and the updated X0 is used as output value Y1.

Claim 31 of the present invention is an encoding method for encoding input image data in a predetermined signal format by dividing said image data into block units and performing orthogonal transformation in said block units,

When an output value Y0, i.e., X0+X1 and an output value Y1, i.e., X0−X1 are generated from two input values X0 and X1 by at least an orthogonal transformation calculation,

The methods include:

First, a subtraction step for subtracting said X1 from said X0 to produce a new X0,

Next, a first addition step for adding the X1 to the X1 to produce a new X0, and

Third, a second addition step for adding said new X0 to said new X1 to generate new X1, wherein

The new X1 is used as output value Y0, and the updated X0 is used as output value Y1.

Claim 34 of the present invention is an encoding method for encoding input image data in a predetermined signal format by dividing said image data into block units and performing orthogonal transformation in said block units,

When an output value Y0, i.e., X0+X1 and an output value Y1, i.e., X0-X1 are generated from two input values X0 and X1 by at least an orthogonal transformation calculation,

The methods include:

First, a first addition step for adding said X0 to said X1 to produce a new X1,

Next, a shifting step for shifting said X0 used as a binary number one bit to the MSB side to generate a new X0, and

Third, a subtraction step for subtracting said new X1 from said new X0 to produce an updated X0, wherein

The new X1 is used as output value Y0, and the updated X0 is used as output value Y1.

Claim 37 of the present invention is an encoding method for encoding input image data in a predetermined signal format by dividing said image data into block units and performing orthogonal transformation in said block units,

When an output value Y0, i.e., X0+X1 and an output value Y1, i.e., X0−X1 are generated from two input values X0 and X1 by at least an orthogonal transformation calculation,

The methods include:

First, a subtraction step for subtracting said X1 from said X0 to produce a new X0,

second, a shift step for shifting said X1 used as a binary number one bit towards the MSB to produce a new X1, and

Third, a second addition step for adding said new X0 to said new X1 to generate new X1, wherein

The new X1 is used as output value Y0, and the updated X0 is used as output value Y1.

Claim 40 of the present invention is a decoding method for performing variable length decoding, orthogonal inverse transformation, and signal format conversion on coded data to obtain image data,

When the maximum codeword length for each codeword of the encoded data is n (n: natural number),

The variable length decoding step includes:

(1) A first table referring step for referring to a first table by using j-bit data of the code word as input, for outputting a code length from the first table when the code length s is j or less related information and decoded data, and for outputting code length related information and second table access information when the code length s is j+1 or more, and

(2) The second table reference step, for calculating the second table address according to the second table access information and the s-bit data of the code word, for referring to the second table according to the second table address, and for outputting decoded data.

Claim 43 of the present invention is a decoding method for performing variable-length decoding, orthogonal inverse transformation, and signal format conversion on coded data to obtain image data,

When the encoded data is a variable-length encoded codeword string, and the maximum codeword length of each codeword is n (n: a natural number),

The variable length decoding step includes:

(1) a codeword string obtaining step, used to obtain j-bit data from the header of the codeword string,

(2) A first table referring step for referring to a first table by using said obtained j-bit data as input, for outputting a code length correlation from said first table when the code length s is j or less information and decoded data, and for outputting code length related information and second table access information from said first table when the code length s is j+1 or more, and

(3) The second table reference step is used to obtain s-bit data from the header of the codeword string, calculate the second table address according to the second table access information and the s-bit data, and calculate the second table address according to the first two table addresses refer to the second table, and are used to output decoded data, and

(4) A displacement step for obtaining a code s from the code length related information, for deleting the s-bit code from the head of the code word string, and for repeating this operation until an end code occurs.

Claim 46 of the present invention is a decoding method for performing variable-length decoding, orthogonal inverse transformation, and signal format conversion on coded data to obtain image data,

When the encoded data is a variable-length encoded codeword string, and the maximum codeword length of each codeword is n (n: a natural number),

The variable length decoding step includes:

(1) a codeword string obtaining step, used to obtain j-bit data from the header of the codeword string,

(2) Expanding the first table referencing step, wherein the first table is referred to by using the obtained j-bit data as input, and when the sum of the code lengths of k or less consecutive codewords is j or less, from the first A table outputs the code length-related information of the k consecutive code words and the decoded data of each code word in the k or less consecutive code words, and when the code length s is j+1 or more, from the The first table outputs code length related information and the second table access information, and

(3) The second table reference step is used to obtain s-bit data from the header of the codeword string, calculate the second table address according to the second table access information and the s-bit data, and calculate the second table address according to the first A second table address refers to the second table, and is used to output decoded data.

Claim 49 of the present invention is a decoding method for performing variable-length decoding, orthogonal inverse transformation, and signal format conversion on coded data to obtain image data,

When the coded data is a variable-length encoded codeword, and the maximum codeword length of each codeword is n (n: a natural number),

The variable length decoding step includes:

(1) a codeword string obtaining step, used to obtain j-bit data from the header of the codeword string,

(2) A first table referring step, wherein the first table is referred to by using said obtained j-bit data as input, when the sum of the code lengths of m or less consecutive codewords is j or less, and when the unique When determining the sum of the code lengths of the m consecutive codewords and the codewords next to the m consecutive codewords, outputting information about the m consecutive codewords and the m consecutive codewords from the first table information on the total code length of , decoded data for each of said m or fewer consecutive codewords and second table access information on said codeword following said m consecutive codewords, and

(3) A second table referring step of accessing a second table by using the second table access information as an input, and outputting decoded data on said codewords following said m consecutive codewords.

Claim 73 of the present invention is a decoding method for performing orthogonal inverse transformation and signal format conversion on coded data to obtain image data,

When an output value Y0, i.e., X0+X1, and an output value Y1, i.e., X0-X1 are produced from two input values X0 and X1, calculated by at least an orthogonal inverse transformation,

The methods include:

First, an addition step for adding said X0 to said X1 to produce a new X1,

Second, a doubling step for doubling the X0 to produce a new X0, and

Third, an addition step for subtracting said new X1 from said new X0 to produce an updated X0, wherein

The new X1 is used as output value Y0, and the updated X0 is used as output value Y1.

Claim 76 of the present invention is a decoding method for performing orthogonal inverse transformation and signal format conversion on coded data to obtain image data,

When an output value Y0, that is, X0+X1, and an output value Y1, that is, X0-X1 are produced from two input values X0 and X1 by orthogonal inverse transformation calculation, etc.,

The methods include:

First, a subtraction step for subtracting said X1 from said X0 to produce a new X0,

Second, a doubling step for doubling said X1 to produce new X1, and

Third, an addition step for adding said new X0 to said new X1 to generate new X1, wherein

The new X1 is used as output value Y0, and the updated X0 is used as output value Y1.

Claim 79 of the present invention is a decoding method for performing orthogonal inverse transformation and signal format conversion on coded data to obtain image data,

When an output value Y0, i.e., X0+X1, and an output value Y1, i.e., X0-X1 are produced from two input values X0 and X1, calculated by at least an orthogonal inverse transformation,

The methods include:

First, a first addition step for adding said X0 to said X1 to produce a new X1,

Next, a second addition step for adding said X0 to said X0 to produce a new X0, and

Third, a subtraction step for subtracting said new X1 from said new X0 to produce an updated X0, wherein

The new X1 is used as the output value Y0, and the updated X0 is used as the output value Y1.

Claim 82 of the present invention is a decoding method for performing orthogonal inverse transformation and signal format conversion on coded data to obtain image data,

When an output value Y0, i.e., X0+X1, and an output value Y1, i.e., X0-X1 are produced from two input values X0 and X1, calculated by at least an orthogonal inverse transformation,

The methods include:

First, a subtraction step for subtracting said X1 from said X0 to produce a new X0,

Next, a first addition step for adding the X1 to the X1 to produce a new X0, and

Third, a second addition step for adding said new X0 to said new X1 to generate new X1, wherein

The new X1 is used as the output value Y0, and the updated X0 is used as the output value Y1.

Claim 85 of the present invention is a decoding method for performing orthogonal inverse transformation and signal format conversion on coded data to obtain image data,

When an output value Y0, i.e., X0+X1, and an output value Y1, i.e., X0-X1 are produced from two input values X0 and X1, calculated by at least an orthogonal inverse transformation,

The methods include:

First, a first addition step for adding said X0 to said X1 to produce a new X1,

Second, a shift step for shifting said X0 used as a binary number one bit to the MSB side to generate a new X0, and

Third, a subtraction step for subtracting said new X1 from said new X0 to produce an updated X0, wherein

The new X1 is used as the output value Y0, and the updated X0 is used as the output value Y1.

Claim 88 of the present invention is a decoding method for performing orthogonal inverse transformation and signal format conversion on coded data to obtain image data,

When an output value Y0, i.e., X0+X1, and an output value Y1, i.e., X0-X1 are produced from two input values X0 and X1, calculated by at least an orthogonal inverse transformation,

It is characterized in that the method comprises:

First, a subtraction step for subtracting said X1 from said X0 to produce a new X0,

Next, a shifting step for shifting said X1 used as a binary number one bit towards the MSB to produce a new X1, and

Third, a second addition step for adding said new X0 to said new X1 to generate new X1, wherein

The new X1 is used as the output value Y0, and the updated X0 is used as the output value Y1.

Claim 91 of the present invention is a decoding method for performing orthogonal inverse transformation and signal format conversion on coded data in block units to obtain image data, characterized in that it includes:

Existence range detection step, wherein, when decoding said encoded information to orthogonal coefficient components, only non-zero orthogonal coefficient components are detected, and by storing the positions of said orthogonal coefficient components in blocks, in block units detecting the existence range of the orthogonal coefficient components, and

an orthogonal inverse transform step in which, when the coefficient components other than the DC component are all set to 0 by the existence range detection step, the pixel value of the block is replaced with the DC component or a multiple of the DC component , and when there are coefficient components other than the DC component, ordinary orthogonal inverse transform is performed.

Claim 94 of the present invention is a decoding method for performing orthogonal inverse transformation and signal format conversion on coded data in block units to obtain image data,

When input pixels are divided into horizontal and vertical two-dimensional block units and converted into orthogonal coefficient components by orthogonal transformation, and information obtained by encoding the orthogonal coefficient components is decoded by using orthogonal inverse transformation or the like,

Assume that the horizontal or vertical direction is referred to as a first direction, and the other direction is referred to as a second direction, and that the two-dimensional block has m×n coefficient components including m coefficient components along the first direction and n coefficient components along the second direction,

It is characterized in that the method comprises:

an existence range detection step of detecting an existence range of non-zero orthogonal coefficient components along the first direction for the m coefficient component units when the encoded information is decoded into orthogonal coefficient components, and

an orthogonal inverse transform selection step, wherein a plurality of orthogonal orthogonal transform steps for converting the orthogonal coefficient components into pixel components are provided, and the range is selected depending on the range detected by the existence range detection step Orthogonal inverse transform step.

Claim 97 of the present invention is a decoding method for performing orthogonal inverse transformation and signal format conversion on coded data in block units to obtain image data,

When the input pixels are divided into horizontal and vertical two-dimensional block units and converted into orthogonal coefficient components by orthogonal transformation, and the information obtained by encoding the orthogonal coefficient components is decoded by using orthogonal inverse transformation or the like; it is assumed that the horizontal Or the vertical direction is called the first direction, and the other directions are called the second direction, and the two-dimensional block has m×n coefficient components, which includes m coefficient components along the first direction and along n coefficient components in the second direction,

providing one or more orthogonal inverse transform steps along said first direction and said second direction to convert orthogonal coefficient components into pixel components,

The methods include:

A first direction existence range detection step, for when decoding the encoded information into orthogonal coefficient components, for the m coefficient component unit, detect the existence range of non-zero orthogonal coefficient components along the first direction,

a first direction orthogonal inverse transform selection step for selecting said first direction orthogonal inverse transform step depending on said range detected by said first direction presence range detection step,

The second direction existence range detection step is used to detect the existence range of non-zero orthogonal coefficient components along the second direction for n coefficient component units after the orthogonal inverse transformation in the first direction, and

A second direction orthogonal inverse transform selection step for selecting said second direction orthogonal inverse transform step depending on said range detected by said second direction presence range detection step.

Claim 103 of the present invention is the decoding method according to claim 97, characterized in that, when performing the existence range detection, in the case of rearranging the orthogonal coefficient components by zigzag scanning during encoding, the The existence range along the first direction stored in each orthogonal transform unit is set at the position of the last non-zero orthogonal coefficient component.

Claim 109 of the present invention is a decoding method for performing orthogonal inverse transformation and signal format conversion on coded data to obtain image data, comprising:

a decoding step for decoding the encoded data in a predetermined signal format,

an orthogonal inverse transform step for performing an orthogonal inverse transform on the decoded data, and

a signal format converting step of converting said image data in said predetermined signal format subjected to said orthogonal inverse transform into image data in another signal format, wherein

For data within a predetermined range, the decoding step, the orthogonal inverse transform step and the signal format conversion step are continuously performed.

Claim 112 of the present invention is the decoding method as claimed in claim 109, characterized in that said image data in said predetermined signal format includes luminance, first color difference, and second color difference signals, and in the signal format conversion The subsequent data includes red, green and blue signals.

Claim 115 of the present invention is the decoding method according to claim 109, characterized in that said image data in said predetermined signal format includes luminance, first color difference and second color difference signals, and after signal format conversion The image data of includes luminance, first color-difference and second color-difference signals, which have a different structure than before conversion.

Figure overview

FIG. 1 is a block diagram showing a first embodiment of the present invention;

Fig. 2 is a schematic diagram showing data flow when utilizing a computer to realize the first embodiment of the present invention;

Figure 3 is a block diagram illustrating a second embodiment of the present invention;

Figure 4 is a block diagram illustrating a third embodiment of the present invention;

Fig. 5 is a block diagram showing a fourth embodiment of the present invention;

FIG. 6 is a flowchart illustrating a fifth embodiment of the present invention;

FIG. 7 is a flowchart illustrating a sixth embodiment of the present invention;

FIG. 8 is a flowchart showing a seventh embodiment of the present invention;

FIG. 9 is a flowchart showing an eighth embodiment of the present invention;

FIG. 10 is a flowchart showing a ninth embodiment of the present invention;

Fig. 11 is a flowchart showing a tenth embodiment of the present invention;

Fig. 12 is a flowchart showing an eleventh embodiment of the present invention;

FIG. 13 is a diagram showing a first table according to an eleventh embodiment of the present invention;

FIG. 14 is a diagram showing a method of obtaining a second table using an eleventh embodiment of the present invention;

Fig. 15 is a flowchart showing a twelfth embodiment of the present invention;

Fig. 16 is a flowchart showing a thirteenth embodiment of the present invention;

FIG. 17 is a diagram of a first table according to a thirteenth embodiment of the present invention;

Fig. 18 is a flowchart showing a fourteenth embodiment of the present invention;

FIG. 19 is a diagram simply showing a first table according to a fourteenth embodiment of the present invention;

Fig. 20 is a block diagram showing a fifteenth embodiment of the present invention;

Fig. 21 is a block diagram showing a sixteenth embodiment of the present invention;

Fig. 22 is a block diagram showing a seventeenth embodiment of the present invention;

Fig. 23 is a block diagram showing an eighteenth embodiment of the present invention;

Fig. 24 is a schematic diagram showing the flow of data when the eighteenth embodiment of the present invention is realized by a computer;

Fig. 25 is a block diagram showing conventional image data encoding;

Fig. 26 is a block diagram showing the structure of a YUV format signal;

Fig. 27 is a block diagram showing the structure of an RGB format signal;

Figure 28 is a block diagram illustrating rearrangement;

29 is a diagram for a variable length code of DVC;

FIG. 30 is a diagram illustrating variable length coding for DVC;

Fig. 31 is a block diagram showing conventional image signal decoding;

FIG. 32 is a diagram illustrating a conventional variable length encoding method 1;

FIG. 33 is a diagram illustrating a conventional variable length encoding method 2;

FIG. 34 is a diagram simply showing the structure of a computer;

Fig. 35 is a schematic diagram showing the flow of data when utilizing a computer to implement conventional encoding;

Fig. 36 is a schematic diagram showing the flow of data when utilizing a computer to realize conventional decoding;

FIG. 37( a) is a diagram showing the physical format of a floppy disk;

Fig. 37 (b) is a diagram showing a casing accommodating a floppy disk; and

Fig. 37(c) is a diagram for recording and reproducing a program to a floppy disk.

BEST MODE FOR CARRYING OUT THE INVENTION

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

An embodiment of the present invention, a first embodiment, is described with reference to FIGS. 1 and 2 .

FIG. 1 is a block diagram showing the structure of an encoding device according to a first embodiment. In FIG. 1, reference numeral 101 denotes an input terminal, reference numeral 102 denotes a rearrangement section for reproducing arrangement, reference numeral 103 denotes a signal format conversion section, reference numeral 104 denotes an orthogonal transformation section, reference numeral 105 denotes a variable-length coding section, and reference numeral 106 represents an output terminal. Assume that the image signal input from the input terminal 101 is an RGB format signal.

The RGB format signal input from the input terminal 101 is rearranged by the rearrangement section 102 . The rearranged RGB format signal is sent to the signal format conversion section 103, and converted into a YUV format signal. The YUV format signal is orthogonally transformed by the orthogonal transformation section 104, and an orthogonal transformation coefficient is obtained. The orthogonal transform coefficients are Huffman encoded by the variable length encoding section 105 . At this time, the above-mentioned orthogonal transform coefficients are appropriately quantized so that the number of codes in all sync blocks does not exceed a certain value. The encoded image signal is output from the output terminal 106 .

FIG. 2 is a diagram showing the flow of data when the processing of the present embodiment is executed with a computer. In FIG. 2, reference numeral 201 denotes an external memory, reference numeral 202 denotes a CPU, and reference numeral 203 denotes a data bus.

As in the case of the conventional example, the input RGB format signal is mapped in the area of the external memory 201 (corresponding to the dotted line indicated by reference numeral 251 in FIG. 2). For the RGB format signal mapped in the external memory 201, the pixel data stored in the address according to the rearrangement pattern is transferred to the CPU 202 (reference numeral 252). At the CPU 202, orthogonal transform and variable-length encoding are sequentially performed. A series of these calculations can be performed in sync blocks, that is, in 30 block units, and when it is assumed that the amount of information for one pixel is 1 byte, 30*8*8=1920 bytes are required, and these bytes can be Stored in the CPU's internal cache memory. The data transfer time between the registers used for calculation and the cache memory is much shorter than the time between the registers and the external memory 201 . Therefore, signal format conversion and orthogonal transformation can be continuously performed without using an external memory. The encoded image signal (reference numeral 254) is output through the data bus 203.

As described above, compared with the conventional example shown in FIG. 35, in the first embodiment, after the signal format conversion, the operation of once writing data back to the memory to perform rearrangement again and reloading from the memory again can be omitted. Operations that read data to perform orthogonal transformation and variable length encoding. As a result, data transfer between the CPU and external memory is not required, thereby greatly reducing processing time.

In this embodiment, the RGB format is used as the input image signal; however, even when the input signal is a YUV422 component signal and the YUV422 component signal is converted into a YUV411 component signal by the signal conversion section, the same effect can be obtained.

A recording medium such as a magnetic recording medium or an optical recording medium may be produced in which a program for executing the functions of all or part of the devices using a computer according to the present embodiment is recorded, and the same operations as above can be performed with such a medium.

The above-described embodiments mainly correspond to claims 1, 2 and 3 of the present invention.

Referring to Fig. 3, an embodiment of the present invention, a second embodiment, is described. Fig. 3 is a block diagram showing the structure of an encoding device according to a second embodiment. As shown in Fig. 3, the above reference numeral 301 is the pixel value input part, the reference numeral 302 represents the pixel block generation part, the reference numeral 303 represents the pixel value detection part, the reference numeral 304 represents the orthogonal transformation part, the reference numeral 305 represents the AC component zero setting part and Reference numeral 306 denotes an output section.

Next, when the operation of the second embodiment is described below, the operation of the embodiment of the encoding method according to the present invention will also be described simultaneously.

In this embodiment, the video data input from the pixel value input section 301 in units of pixels is first divided by the block generation section 302 into two-dimensional blocks including horizontal 8 pixels and vertical 8 pixels. Next, the pixel value detection section 303 performs detection to judge whether or not all pixel values in each block are approximately equal. As a result, in the case where the pixel values in the block are almost equal, the AC component zero setting section 305 sets a given pixel value in the block or its multiple as the DC coefficient component, and sets all other AC coefficient component values as is 0, and is output by the output section 306. On the contrary, in the case where the pixel values in the block are not approximately equal, the orthogonal transform section 304 performs ordinary two-dimensional orthogonal transform, and the output is performed by the output section 306 .

When the pixel values in a block are approximately equal, the orthogonal transform calculation is omitted in the second embodiment described above, so that the amount of calculation required for the orthogonal transform can be greatly reduced. Furthermore, at the AC component zero setting section 305, calculation results obtained from a plurality of pixel values in a block may be used as DC coefficient component values. In addition, generally, a discrete cosine transform (DCT) is employed as the orthogonal transform.

A recording medium, such as a magnetic recording medium or an optical recording medium, is recorded in which a program for executing the functions of all or part of the devices using a computer according to the present embodiment can be produced, and the same operations as described above can be performed with such a medium.

The above-described embodiments mainly correspond to claims 10 to 12 of the present invention.

Referring to Fig. 4, a third embodiment of the invention, the third embodiment, will be described.

Fig. 4 is a block diagram showing the structure of an encoding device according to a third embodiment. Reference numeral 401 denotes a first orthogonal transform section, numeral 402 denotes an image value detection section, numeral 403 denotes a second orthogonal transform section, and numeral 404 denotes an AC component zero setting section.

The operations of the pixel value input section 301 and the block generation section 302 shown in FIG. 4 are the same as those described with reference to FIG. 3 .

First, the pixel values in the block are subjected to orthogonal transformation in the horizontal direction by the first orthogonal transformation section 401 . Next, the pixel value detecting section 402 detects the pixel value (coefficient component), undergoes orthogonal transformation along the horizontal direction, the vertical direction and detects whether all the coefficient component values along the vertical direction are approximately equal in the orthogonal transformation unit.

In the case where the coefficient component values along the vertical direction in the orthogonal transform unit are approximately equal, the AC component zero setting section 404 sets a given coefficient component value along the vertical direction in the above-mentioned orthogonal transform unit or its multiple is set as the DC coefficient component, and all other AC coefficient component values are set to 0, and then the output is performed by the output section 306 . On the contrary, in the case where the above-mentioned coefficient component values along the vertical direction are not approximately equal in the orthogonal transform unit, the second orthogonal transform section 403 performs ordinary orthogonal transform, and the output is performed by the output section 306 .

In this embodiment, a selection is made to determine whether or not to perform orthogonal transformation calculation for the orthogonal transformation performed at the time of the second two-dimensional orthogonal transformation along the horizontal or vertical direction. Since information is generally concentrated on certain parts of the coefficient components by the first orthogonal transform, transform units having only DC components appear in large numbers at the time of the second orthogonal transform. Therefore, the number of times of actually performing orthogonal transform calculations can be greatly reduced.

A recording medium such as a magnetic recording medium or an optical recording medium may be produced in which a program for executing the functions of all or part of the devices with a computer according to the present embodiment is recorded, and the same operations as above can be performed with this medium.

The above-described embodiments mainly correspond to claims 13 to 15 of the present invention.

Next, referring to FIG. 5, an embodiment of the fourth invention, the fourth embodiment, will be described.

Fig. 5 is a block diagram showing the structure of an encoding device according to a fourth embodiment. In FIG. 5, reference numeral 501 denotes a pixel value detecting section, and reference numeral 502 denotes a DC/AC component zero setting section.

As shown in FIG. 5, the operations of the pixel value input section 301, the block generation section 302, and the first orthogonal transform section 401 are the same as those shown in FIG.

The pixel value detection section 501 detects pixel values (coefficient components), undergoes vertical transformation along the horizontal direction, the vertical direction and detects whether all coefficient component values along the vertical direction are approximately zero in an orthogonal transformation unit.

In the case where the coefficient component value along the vertical direction in the orthogonal transform unit is approximately zero, the DC/AC component zero setting section 502 sets the above-mentioned DC coefficient component value along the vertical direction in the orthogonal transform unit to zero, and the output is performed by the output section 306. In contrast, in the case where the above coefficient component values along the vertical direction are not approximately zero in the orthogonal transform unit, the second orthogonal transform section 403 performs ordinary orthogonal transform, and the output section 306 performs output.

Also, in this embodiment, a selection is made to determine whether or not to perform orthogonal transformation calculation for the orthogonal transformation performed at the time of the second two-dimensional orthogonal transformation along the horizontal or vertical direction. Typically during the second orthogonal transform, orthogonal transform units in which all coefficient components are zero occur in large numbers. Therefore, the number of times of actually performing orthogonal transform calculations can be greatly reduced.

A recording medium, such as a magnetic recording medium or an optical recording medium, is recorded in which functions for executing all or part of the means with a computer according to the present embodiment can be produced, and the same operations as above can be performed with this medium.

The above-described embodiments mainly correspond to claims 16 to 18 of the present invention.

In the second, third and fourth embodiments, when applied to a calculation device capable of simultaneously calculating K pixels or K orthogonal coefficients, the efficiency can be further improved by changing, so that in K pixel units , perform the detection and the like in the above-described embodiments.

Furthermore, the present invention can be applied to any given image signal, and any given method other than those of the embodiment can also be applied with respect to the number of dimensions and the type of orthogonal transformation. Furthermore, the sequence of horizontal and vertical calculations for two-dimensional orthogonal transforms can be changed.

In addition, the structures of the embodiments described in the block diagrams and their processing sequences can also be realized by various methods.

Referring to Fig. 6, a fifth embodiment of the invention, the fifth embodiment, will be described.

Fig. 6 is a flowchart showing addition/subtraction according to the fifth embodiment. The symbol 601 shown in Figure 6 represents the first input step, the symbol 602 represents the second input step, the symbol 603 represents the first computing step, the symbol 604 represents the second computing step, the symbol 605 represents the third computing step, and the symbol 606 represents the first computing step. An output step and reference numeral 607 denotes a second output step.

Next, the operation of the present embodiment is described.

First, in the first input step 601, the input value X0 is set in the register A, and in the second input step 602, the input value X1 is set in the register B. In a first calculation step 603, the output of register A (input value X0) is added to the output of register B (input X1) and the result (new X1) is set in register B. In a second calculation step 604, the output of register A (input value X0) is doubled (double) and the result (new X0) is set in register A. In a third calculation step 605, the output of register B (new X1) is subtracted from the output of register A (new X0) and the result (updated X0) is set in register A. Finally, in a first output step 606, the output of register B is output as output value Y0, and in a second output step 607, the output of register A is output as output value Y1.

As mentioned above, in this embodiment, only two registers, registers A and B, are used to realize the butterfly calculation. For this reason, with only eight registers, the four sets of butterfly calculations required for 8-dimensional orthogonal transformations can be realized. In this case, by utilizing the latest MMX-compatible registers, an orthogonal transformation can be realized without saving on the memory. Furthermore, since the above-mentioned addition and subtraction calculations are repeated for the orthogonal transformation, the output in the embodiment of the present invention can become an input for the next addition and subtraction calculation.

A recording medium such as a magnetic recording medium or an optical recording medium may be produced in which a program for executing the functions of all or part of the devices using a computer according to the present embodiment is recorded, and the same operations as above can be performed with such a medium.

The above-described embodiments mainly correspond to claims 22 to 24 and 73 to 75 of the present invention.

Referring to Fig. 7, an embodiment of the sixth invention, the sixth embodiment, will be described. Fig. 7 is a flowchart showing addition/subtraction according to the sixth embodiment. Although the structure shown in FIG. 7 is substantially the same as that shown in FIG. 6, reference numeral 703 in the figure denotes a first calculation step, reference numeral 704 denotes a second calculation step, and reference numeral 705 denotes a third calculation step.

In this embodiment, first, in the first input step 601, the input value X0 is set in the register A, and in the second input step 602, the input value X1 is set in the register B. In a first calculation step 703, the output of register B (input value X1) is subtracted from the output of register A (input value X0) and the result (new X0) is set in register A. In a second computation step 704, the output of register B (input value X1) is doubled and the result (new X1) is set in register B. In a third calculation step 705, the output of register A (new X0) is added to the output of register B (new X1), and the result (updated X1) is set in register B. Finally, in a first output step 606, the output of register B is output as output value Y0, and in a second output step 607, the output of register A is output as output value Y1.

As in the case of the fifth embodiment, in this embodiment, butterfly calculation can be realized with only two registers.

A recording medium such as a magnetic recording medium or an optical recording medium may be produced in which a program for executing the functions of all or part of the devices using a computer according to the present embodiment is recorded, and the same operations as above can be performed with such a medium.

The above-described embodiments mainly correspond to claims 25 to 27 and 76 to 78 of the present invention.

Referring to Fig. 8, an embodiment of the seventh invention, the seventh embodiment, will be described. Fig. 8 is a flow chart outputting addition/subtraction according to the seventh embodiment. In this embodiment, the second calculation step 604 in the fifth embodiment is changed to a second calculation step 804 . First, in the first input step 601, the input value X0 is set in the register A, and in the second input step 602, the input value X1 is set in the register B. In a first calculation step 603, the output of register A is added to the output of register B (X1), and the result (new X1) is set in register B. In the second calculation step 704, the output of register A (input value X0) is added to the output of register A (input value X0), and the result (new X0) is set in register A. In the third calculation step 605, The output of register B (new X1) is subtracted from the output of register A (new X0), and the result (updated X0) is set in register A. Finally, in a first output step 606, the output of register B is output As output value Y0, and in a second output step 607, the output of register A is output as output value Y1.

As described above, in this embodiment, the double calculation of the fifth embodiment is realized by additional calculation. Since addition calculation is a basic function of a computer and can be done at high speed, butterfly calculation can be done at high speed. Furthermore, in cases where the CPU is capable of executing two instructions simultaneously, it is highly possible to execute the addition instruction concurrently with another instruction, which can further improve computational efficiency.

A recording medium such as a magnetic recording medium or an optical recording medium may be produced in which a program for executing the functions of all or part of the devices using a computer according to the present embodiment is recorded, and the same operations as above can be performed with such a medium.

The above-described embodiments mainly correspond to claims 28 to 30 and 79 to 81 of the present invention.

Referring to Fig. 9, an eighth embodiment, an embodiment of the eighth invention, will be described.

Fig. 9 is a flowchart showing addition/subtraction according to the eighth embodiment. In this embodiment, the second calculation step 704 in the sixth embodiment is changed to a second calculation step 904 . First, in the first input step 601, the input value X0 is set in the register A, and in the second input step 602, the input value X1 is set in the register B. In a first calculation step 703, the output of register B (input value X1) is subtracted from the output of register A (input value X0) and the result (new X0) is set in register A. In a second calculation step 904, the output of register B (input value X1) is added to the output of register B (input value X1) and the result (new X1) is set in register B. In a third calculation step 705, the output of register A (new X0) is added to the output of register B (new X1), and the result (updated X1) is set in register B. Finally, in a first output step 606, the output of register B is output as output value Y0, and in a second output step 607, the output of register A is output as output value Y1.

In this embodiment, the doubling calculation of the fifth embodiment is also completed by high-speed addition calculation.

A recording medium such as a magnetic recording medium or an optical recording medium may be produced in which a program for executing the functions of all or part of the devices using a computer according to the present embodiment is recorded, and the same operations as above can be performed with such a medium.

The above-described embodiments mainly correspond to claims 31 to 33 and 82 to 84 of the present invention.

Referring to Fig. 10, an embodiment of the ninth invention, the ninth embodiment, will be described.

Fig. 10 is a flowchart showing addition/subtraction according to the ninth embodiment. In this embodiment, the second calculation step 604 in the fifth embodiment is changed to the second calculation step 1004 . First, in the first input step 601, the input value X0 is set in the register A, and in the second input step 602, the input value X1 is set in the register B. In a first calculation step 603, the output of register A (input value X0) is added to the output of register B (input X1) and the result (new X1) is set in register B. In the second calculation step 1004, the output of register A (input value X0) is shifted to the MSB side, and the result (new X0) is set in register A. In a third calculation step 605, the output of register B (new X1) is subtracted from the output of register A (new X0) and the result (updated X0) is set in register A. Finally, in a first output step 606, the output of register B is output as output value Y0, and in a second output step 607, the output of register A is output as output value Y1.

As described above, in this embodiment, the doubling calculation of the fifth embodiment is performed by simple shift calculation. Since the shift calculation is a basic function of a computer and can be realized at high speed, the butterfly calculation is completed at high speed.

A recording medium such as a magnetic recording medium or an optical recording medium may be produced in which a program for executing the functions of all or part of the devices using a computer according to the present embodiment is recorded, and the same operations as above can be performed with such a medium.

The above-described embodiments mainly correspond to claims 34 to 36 and 85 to 87 of the present invention.

Referring to Fig. 11, an embodiment of the tenth invention, the tenth embodiment, will be described.

Fig. 11 is a flowchart showing addition/subtraction according to the tenth embodiment. In this embodiment, the second calculation step 704 in the sixth embodiment is changed to the second calculation step 1104 . First, in the first input step 601, the input value X0 is set in the register A, and in the second input step 602, the input value X1 is set in the register B. In a first calculation step 703, the output of register B (input value X1) is subtracted from the output of register A (input X0) and the result (new X0) is set in register A. In a second calculation step 1104, the output of register B (input value X1) is shifted one bit to the MSB and the result (new X1) is set in register B. In a third calculation step 705, the output of register A (new X0) is added to the output of register B (new X1), and the result (updated X1) is set in register B. Finally, in a first output step 606, the output of register B is output as output value Y0, and in a second output step 607, the output of register A is output as output value Y1.

In this embodiment, the doubling calculation of the fifth embodiment is also performed by high-speed shift calculation.

As described above, in the fifth to tenth embodiments of the present invention, by using only two registers, the butterfly calculation, that is, the basic calculation for the orthogonal transformation can be performed, and the calculation result can be stored in the memory. rise to a minimum, which can greatly reduce the calculation time.

The method of using doubling calculations (including addition calculations and shift calculations) according to the present invention can be implemented by other methods than the above-mentioned embodiments; in addition to only software implementation, it can also be implemented by hardware. Furthermore, in actual orthogonal transform calculation, besides the basic technique of the present invention, various calculations corresponding to the orthogonal transform to be performed can be added.

Not only the orthogonal transform method described in the fifth to tenth embodiments can be applied to the orthogonal transform for encoding, but also the exact same method can be applied to the orthogonal inverse transform for decoding.

A recording medium such as a magnetic recording medium or an optical recording medium may be produced in which a program for executing the functions of all or part of the devices using a computer according to the present embodiment is recorded, and the same operations as above can be performed with such a medium.

The above-described embodiments mainly correspond to claims 37 to 39 and 88 to 90 of the present invention.

An eleventh embodiment, an embodiment of the eleventh invention, will be described with reference to Figs. 12 to 14 .

According to the present invention, the variable length code in the following embodiments is a code in which the maximum value (as shown in FIG. 29 ) of the code length of one code word is 16, and is uniquely determined by 8 bits from the head of the code word code length s.

FIG. 12 is a flowchart showing a variable length decoding method according to the present embodiment.

When a code word is input, access to the first table is performed using 8-bit data from the header as first table access data. In the first table, the code length s of input 8-bit data is uniquely determined. When s ≤ 8, output the run-sum value of zero as the code length and the data to be decoded. When the codeword is EOB, for example, it is set to 127 with zero run, thereby identifying it as EOB.

For example, when the codeword is "01111100110011", 8 bits from the header of the codeword, ie, "01111100", are obtained. When entering this into the first table, s=5, zero runs = 1 and a value of -1 is obtained. At the same time, the code word is "01111", thereby completing the decoding of the code word.

In addition, when s≥9, a mask pattern and offset value for obtaining access to the second table, and a code length s are output. Masking patterns and bias values are unique with respect to value s.

FIG. 13 is a diagram showing operations before and after referring to the first table in detail. With reference to the structure of the first table, when the input value is in the range of "00000000" to "11011111", the code length is not greater than 8 bits; therefore, the code length, zero run and value (output 1) are shown from the first table.

In other words, when the input value is in the range of "11100000" to "11111101", the code length s is determined; however, since s≥9, decoded data cannot be output using only the input value. At this time, the mask pattern and offset value for gaining access to the second table are output (output 2).

When the input value is "11111110", the low-order 6 bits of the 13-bit code directly become the zero-run value, and the value is 0 (output 3). On the other hand, when the input value is "11111111", the value can be obtained from the lower 9 bits of the 16-bit code by simple calculation, and the run of zero is 0 (output 4).

Fig. 14 is a diagram showing the relationship between the output of the first table, the codeword to be obtained, and the second table. A method of obtaining decoded data when s≥9 is described below.

The second table is constituted so that addresses (initial value: 0) and output values of codewords having code lengths of 9 to 13 (except output 3) are arranged in an increasing sequence of codewords.

The newly obtained s-bit codeword is subjected to masking mode, ie, output of the first table, and AND calculation. The value t obtained by masking at this moment (dotted line portion in the figure) is a uniquely determined value within codewords having the same code length. Next, a=f+t is calculated using the uniquely determined offset f according to the code length in the first table. When a is input into the second table, the output of the codeword corresponding to it can be uniquely obtained, that is, the zero-run sum value.

When, for example, the codeword "1111011110" is decoded, the following happens.

First, 8-bit data from the header, ie, "11110111", is obtained. The code length of the pattern "11110111 is 10; and the corresponding mask pattern and offset value are "11111" and 32, respectively.

Since the code length is 10, the code word is found to be "1111011110". Therefore, the mask value t is the AND of the mask patterns "11111" and "11110", ie, 30.

The input address to the second table becomes f+t=30+32=62. The output at this point is a zero run of 0 and a value of 22, thus decoding the codeword "1111011110".

In the variable-length codes in this embodiment, the probability of occurrence of a code having a code length of 8 or less is about 90%. Therefore, the probability of decoding by one table reference operation is about 90%; even in other cases, decoding can be done by two reference operations. Furthermore, since both output 1 and output 2 require 3 bits, the size of the first table becomes 3×28=768 bits. On the other hand, the size of the second table is 2*128=256 bits, because the input address is in the range of 0 to 128, and the parameters, ie, zero run and value, require 2 bits. The sum of the sizes of the two tables is 1 kilobyte, and this can be adequately stored in the cache memory. Furthermore, in the case of output 3 and output 4, the zero run and value can be obtained by simple calculations, if the code length is known.

As described above, in the eleventh embodiment, when decoding a variable-length code, first obtain 8-bit data from the codeword header, and refer to the table; if the code length is 9 bits or more, then refer to the table again, thereby Decoded data can be obtained. The processing required at this time is one table access (maximum two times) with a probability of about 90%, maximum execution of two branch instructions (generally one time), and simple calculation.

Therefore, according to the present embodiment, compared with the variable-length decoding method 1 described in explaining the conventional technique, the number of branch instruction executions can be greatly reduced. In addition, compared with the variable length decoding method 2, the size of the referenced table is sufficiently small, and the probability of storing the table to be accessed in the cache memory is high, so that the time for transferring table data from the external memory can be greatly reduced. As a result, decoding calculations can be performed at a higher rate than the variable length decoding methods 1 and 2.

A recording medium such as a magnetic recording medium or an optical recording medium may be produced in which a program for executing the functions of all or part of the devices using a computer according to the present embodiment is recorded, and the same operations as above can be performed with such a medium.

The above-described embodiments mainly correspond to claims 40 to 42 of the present invention.

Referring to Fig. 15, an embodiment of the twelfth invention, a twelfth embodiment, will be described.

Fig. 15 is a flowchart showing a variable length decoding method according to the twelfth embodiment. This embodiment employs a computer having the structure shown in Fig. 34, and the size of the register is 32 bits.

First, the 32-bit data from the head of the code word string stored in the external memory 3401 is loaded in register A, while the code word string is in MSB (Most Significant Bit), and 32 is set as the remaining code length L. Next, the contents of register A are copied to register B, and register B undergoes a 24-bit right logical shift. Through this operation, 8-bit data is obtained from the codeword string.

The first table can be accessed by using 8-bit data as (the offset of) the table reference address, and a predetermined decoding operation according to the first embodiment is performed to obtain the code length s and decoded data. After decoding, a left logical shift of s bits is performed at register A, setting the value obtained by subtracting s from L as new L. With this operation, the codeword is decoded immediately before erasure.

This operation is repeated, and if L is less than 16, successive codewords are obtained from the external memory 340 and combined with the string of codewords held in register A to form a new string of codewords. Repeat this operation until EOB occurs.

In the present embodiment, the size of the register is 32 bits; however, this can be realized by using the MMX register (64 bits) disclosed by Intel Corporation. In this case, first load the 64-bit code word into the register; when the remaining code length is less than 32, only 32-bit data should be obtained from the external memory, and the other parts are the same as those of the 32-bit register. By utilizing the MMX registers, the number of memory accesses per codeword group can be approximately halved, allowing variable-length decoding to be performed at higher speeds.

A recording medium, such as a magnetic recording medium or an optical recording medium, is recorded in which a program for executing the functions of all or part of the devices using a computer according to the present embodiment can be produced, and the same operations as described above can be performed with such a medium.

The above-described embodiments mainly correspond to claims 43 to 45 of the present invention.

Referring to Figs. 16 and 17, an embodiment of the thirteenth invention, a thirteenth embodiment, will be described.

FIG. 16 is a flowchart showing a variable length decoding method according to the present embodiment, and FIG. 17 is a diagram showing a first table according to the present embodiment.

The difference between this embodiment and the twelfth embodiment lies in the following points: the input 8-bit pattern includes two codewords, wherein two consecutive codewords (hereinafter referred to as codeword I and codeword II in this order) In the case where the sum of the code lengths of the two code words is 8 or less, and the zero-run length of the two code words is 0, instead of the code length, set the value of multiplying the sum of the code lengths of the two code words by -1, instead of With zero run, the value of codeword I (value I) is set and instead of code length II, the value of codeword II (value II) is set as output. For example, when the 8-bit pattern is "00110010", this includes codeword I "001", which is (code length, zero run, value) = (3, 0, -1), and codeword II "10010", which is is (5, 0, 4). At this time, -8 is set in the area of the code length corresponding to the input "00110010" in the first table, -1 is set in the zero-run area, and 4 is set in the value area.

When 8-bit data is obtained from the code word string in the flowchart shown in FIG. 16, and when its value is "00110010", the code length s=-8 is output. At this time, set -s as the code length and set it to 8. In addition, when reading the value output from the zero-run area as value I, and reading the value output from the previous value as value II, the zero-runs of the two codewords become 0, so that the comparison can be done by 1 table reference Decoding of two codewords.

Other operations are similar to those of the twelfth embodiment.

As described above, according to the present embodiment, when codewords having a short code length continue, two codewords can be decoded at a time by one table reference, so that decoding can be performed at a higher speed.

In the explanation of the present embodiment, it is assumed that the value I and the value II are stored in the zero-run area and the value area of the first table, respectively; however, they may be inversely stored. In addition, it is assumed that the code length is multiplied by -1 to identify the codeword string in the case of decoding two codewords at a time; however, other methods can be used if identification is possible. Furthermore, if a 4-byte area is reserved for an input bit pattern, then for example data allocation for code length, zero run of code word I, value of code word I and value of code word II is performed; In the case where the zero-run of bits and codeword II is 0 (the zero-run of codeword I is not required to be 0), extension can be performed.

A recording medium, such as a magnetic recording medium or an optical recording medium, is recorded in which a program for executing the functions of all or part of the devices using a computer according to the present embodiment can be produced, and the same operations as described above can be performed with such a medium.

The above-described embodiments mainly correspond to claims 46 to 48 of the present invention.

Referring to Figs. 18 and 19, an embodiment of the fourteenth invention, a fourteenth embodiment, will be described.

FIG. 18 is a flowchart outputting the variable length decoding method according to the present embodiment, and FIG. 19 is a diagram showing the first table according to the present embodiment.

The difference between this embodiment and the thirteenth embodiment lies in the following points: for two consecutive codewords (hereinafter referred to as codeword I and codeword II in this order), when the code length of codeword I is 7 or more Small, the sum of the code lengths of code word I and code II is 9 or more, and the code length of code word II is determined to be "8-code length of code word I" bits, the first table shows the same as -1 Multiplied code length, run of zeros and value of codeword I and a second table access offset for decoded codeword II.

For example, when it is assumed that the obtained 8-bit data is "00111000" (for example, as shown in FIG. 19 ), "001" becomes codeword I (code length 3), and the zero-run sum value of codeword I is output, that is, -1 and 0. Furthermore, since it is determined that the code length of the code word starting with the remaining "11000" is 7, output is obtained by multiplying the sum of the code length 3 of the code word I and the code length 7 of the code word II, that is, 10 by -1 "-10", as the code length, and furthermore, an offset for accessing the second table for codeword II is output.

Other operations are the same as those of the 13th embodiment.

As described above, according to the present embodiment, two codewords are decoded from one codeword obtained by two table references to the first table and the second table, so that decoding can be performed at a higher speed.

In the eleventh and fourteenth embodiments, the code length of each codeword is output as the first table; however, other values may be used if the code length can be uniquely determined instead of the code length itself.

A recording medium, such as a magnetic recording medium or an optical recording medium, is recorded in which a program for executing the functions of all or part of the devices using a computer according to the present embodiment can be produced, and the same operations as described above can be performed with such a medium.

The above-described embodiments mainly correspond to claims 49 to 51 of the present invention.

Referring to Fig. 20, an embodiment of the fifteenth invention, the fifteenth embodiment, will be described.

FIG. 20 is a block diagram showing the structure of a decoding device according to the present embodiment. In FIG. 20, reference numeral 2001 denotes an encoded data input section, reference numeral 2002 denotes a codeword decoding section, reference numeral 2003 denotes a presence access detection section, reference numeral 2004 denotes an orthogonal transform section, reference numeral 2005 denotes a DC element replacement section, and reference numeral 2006 denotes an output section. .

This embodiment is for orthogonal inverse transform used when decoding coded data using orthogonal transform. First, encoded data input from encoded data input section 2001 as shown in FIG. 20 is converted from codewords into orthogonal coefficient component values by codeword decoding section 2002. At this time, all the orthogonal coefficient component values of the block before decoding are initialized to zero; when decoding, the orthogonal coefficient component value is not 0, the orthogonal coefficient component value is rewritten in the two-dimensional block in the corresponding position. At this time, with respect to rewriting the two-dimensional position, the presence position of the orthogonal coefficient component value stored in the block by the presence access detection section 2003 is present. Also, the existence position is updated only when high-frequency components are generated in the horizontal or vertical direction in the same block.

In the case where the existence position of the above-mentioned stored orthogonal coefficient component value indicates that there is an AC component after obtaining the orthogonal coefficient component value for one block, the DC coefficient component or its multiple value is set to all by the DC component replacing section 2005 The pixel value, and output from the output section 2006 performs all output. On the contrary, when the existence access of the orthogonal coefficient component value is limited to the DC coefficient component, ordinary orthogonal transform is performed by the orthogonal transform section 2004 and output is performed from the output section 2006 .

By utilizing this embodiment, the existence position of the DC coefficient component is detected only when a non-zero orthogonal coefficient component is generated when codeword decoding; Calculations.

A recording medium, such as a magnetic recording medium or an optical recording medium, is recorded in which a program for executing the functions of all or part of the devices using a computer according to the present embodiment can be produced, and the same operations as described above can be performed with such a medium.

The above-described embodiments mainly correspond to claims 91 to 93 of the present invention.

An embodiment of the sixteenth invention, the sixteenth embodiment, will be described with reference to FIG. 21 .

Fig. 21 is a block diagram showing the structure of a decoding device according to the present embodiment. Reference numeral 2101 denotes an existing range detection section, reference numeral 2102 an orthogonal transform selection position, reference numeral 2103 a first orthogonal transform section, and reference numeral 2104 a second orthogonal transform section.

The operations of the encoded data input section 2001 and the codeword decoding section 2002 described above in FIG. 21 are the same as those shown in FIG. 20 . At the existence range detection section 2101, according to the result of the codeword detection section 2002, the existence positions of the non-zero orthogonal coefficient components are stored in the orthogonal transform unit along the vertical direction.

Next, at the orthogonal transform selection section 2102, the operation of the first orthogonal transform section 2103 is controlled based on the maximum position of the non-zero orthogonal transform coefficient component along the vertical direction in the orthogonal transform unit. At this time, at the first orthogonal transform section 2103, switching is made between two kinds of orthogonal transform, i.e., ordinary orthogonal transform and simplified orthogonal transform in which the DC coefficient component or its multiple is used as all transform values . With this method, the actual orthogonal transform calculation is performed only on the orthogonal transform unit in which the DC orthogonal component exists. Furthermore, the orthogonal coefficient components that are orthogonally transformed in the vertical direction are subjected to orthogonal transformation in the horizontal direction by the second orthogonal transformation section 2104 and output to the output section 2106 .

This embodiment can determine whether to perform actual orthogonal transformation in a horizontal or vertical orthogonal transformation unit of a two-dimensional block; therefore, it is possible to reduce the amount of calculation when performing orthogonal transformation for given image information.

A recording medium, such as a magnetic recording medium or an optical recording medium, is recorded in which a program for executing the functions of all or part of the devices using a computer according to the present embodiment can be produced, and the same operations as described above can be performed with such a medium.

The above-described embodiments mainly correspond to claims 94 to 96 of the present invention.

Referring to Fig. 22, an embodiment of the seventeenth invention, a seventeenth embodiment, will be described.

FIG. 22 is a block diagram showing the structure of a decoding device according to the present embodiment. Reference numeral 2201 denotes a first direction existence range detection part, reference numeral 2202 a first direction orthogonal transformation selection part, reference numeral 2203 a first orthogonal transformation part, reference numeral 2204 a second direction existence range detection part, and reference numeral 2205 a second direction An orthogonal transform selection section and reference numeral 2206 represent a second orthogonal transform section.

The operations of the encoded data input section 2001 and the codeword decoding section 2002 shown in FIG. 22 are the same as those of FIG. 20 . At the first existence range detection section 2201, as in the case of the existence range detection section 2101 shown in FIG. 21, along the vertical direction, the existence positions of the non-zero orthogonal coefficient components are stored in the orthogonal transform unit. Next, at the first orthogonal transform selection section 602, the operation of the first orthogonal transform section 2203 is controlled according to the maximum position of the non-zero orthogonal transform coefficient component along the vertical direction in the orthogonal transform unit. At this time, at the first orthogonal transform section 2203, switching is made between two kinds of orthogonal transform, that is, ordinary orthogonal transform and simplified orthogonal transform in which the DC component or its multiple is used as all transform values .

Next, the second direction existence range detection section 2204 receives the output from the first orthogonal transform section, and stores the existence range of non-zero orthogonal coefficient components in the orthogonal transform unit along the horizontal direction. In the second orthogonal transform selection section 2205, the operation of the second orthogonal transform section 2206 is controlled according to the maximum position of the non-zero orthogonal transform coefficient component along the horizontal direction in the orthogonal transform unit. At this time, in the second orthogonal transform section 206, between two kinds of orthogonal transform, that is, ordinary orthogonal transform and simplified orthogonal transform in which DC coefficient components or multiples thereof are used as all transform values switch. In this way, the pixel values obtained by the orthogonal transformation along the first and second directions are output from the output section 2006 .

In this embodiment, in addition to the fifteenth embodiment, the calculation amount of the orthogonal transformation from the second direction can be reduced, so that a greater effect can be obtained.

In the 16th and 17th embodiments, in the first or second orthogonal transform section, two orthogonal transform methods are switched; however, other orthogonal transform methods can be selected depending on the number of used orthogonal coefficient components .

Also, in the case of employing ordinary orthogonal transform coding, rearrangement called zigzag scanning is performed on orthogonal coefficient components of a two-dimensional block to perform two-dimensional coding in order from low-frequency components to high-frequency components. In this case, a non-zero orthogonal coefficient component existence range in each orthogonal transform unit may be represented by a position of a non-zero orthogonal coefficient component generated last in each orthogonal transform unit. Therefore, the presence range can be detected more easily.

A recording medium, such as a magnetic recording medium or an optical recording medium, is recorded in which a program for executing the functions of all or part of the devices using a computer according to the present embodiment can be produced, and the same operations as described above can be performed with such a medium.

The above-described embodiments mainly correspond to claims 97 to 99 of the present invention.

Referring to Figs. 23 and 24, an eighteenth embodiment, an embodiment of the eighteenth invention, will be described.

Fig. 23 is a block diagram showing the structure of a decoding device according to the present embodiment. In Fig. 23, the reference numeral 2301 represents the input terminal, the reference numeral 2302 represents the variable length decoding part, the reference numeral 2303 represents the orthogonal inverse transformation part, the reference numeral 2304 represents the signal format conversion part, to convert the YUV format signal into an RGB format signal, and the reference numeral 2305 Denotes a de-rearrangement section and reference numeral 2306 denotes an output terminal.

The variable length coded YUV format image signal input from the input terminal 2301 is decoded by the variable length decoding section 2302 . The decoded signal is converted into an ordinary YUV format signal by the orthogonal inverse transform section 2303 and immediately converted into an RGB format signal for each coordinate by the signal format conversion section 2304 . The RGB format signal obtained from the signal format conversion section is de-rearranged by the de-rearrangement section 2305 and output from the output terminal 2306 .

FIG. 24 is a diagram of a flow of data when the above-described image signal processing is performed with a computer.

The coded YUV format signal input from the data bus 203 is taken into the CPU 202 (2451), and it is successively subjected to decoding, inverse orthogonal transformation, and signal format conversion (2452). The image signal subjected to the signal format conversion is written in the external memory 201 at the address generated according to the rearrangement pattern. At this time, the reproduced image is appropriately stored in the external memory 201; therefore, by mapping the image signal in the external memory 202 through a display device such as VRAM or text, it is possible to display the image signal, store it, etc. (2454 ).

As described above, when this embodiment is compared with the conventional example shown in FIG. 36 , after the orthogonal inverse transform, the functions for writing data to the memory to perform de-rearrangement and for reading data from the memory can be omitted. The operation of signal format conversion is thereby performed; therefore, the overall processing time can be shortened. As a result, data transfer between the CPU and external memory becomes unnecessary, and processing time can be greatly reduced.

In this embodiment, an RGB format signal is used as an image signal to be output; however, the signal format converted by the signal format conversion section is not limited to the RGB format signal, and the same effect can be obtained regardless of the format.

A recording medium, such as a magnetic recording medium or an optical recording medium, is recorded in which a program for executing the functions of all or part of the devices using a computer according to the present embodiment can be produced, and the same operations as described above can be performed with such a medium.

The above-described embodiments mainly correspond to claims 109 to 111 of the present invention.

All of the above-described embodiments can be implemented using software, or performed through a recording medium or a transmission medium. Furthermore, an encoding method, apparatus, and program can be constituted in which the above-mentioned various techniques are combined and include orthogonal transform.

Furthermore, by implementing the present invention using a program and recording the program on a recording medium such as a floppy disk and by transferring the program, the present invention can be easily carried out with another independent computer system. 37(a) to 37(c) show the cases obtained using a floppy disk.

Fig. 37(a) shows an example of the physical format of a floppy disk used as the main body of the recording medium. From the outer circumference to the inner circumference, tracks are generated concentrically, and each track area is divided into 16 sectors along the circumferential direction. Programs are recorded according to the area assigned in this way.

Fig. 37(b) shows a case for accommodating a floppy disk. Front and side views of the floppy disk and the floppy disk are shown from the left. By housing the floppy disk in the casing in this way, it is possible to contain the disk from dust and external shocks, so that it can be safely transferred.

Fig. 37(c) is a diagram for recording a program to a floppy disk and reproducing the program from it. By connecting a floppy disk drive to the computer system (as shown), programs can be recorded to and reproduced from a disk. Insert the disk into the floppy through the notch, and remove the disk from the floppy. During reproduction, the disk drive reads the programs from the disk and transfers them to the computer system.

Industrial applicability

As described above, according to the present invention, in encoding processing, for example, the number of times of storing register values in memory at the time of orthogonal transform calculation can be greatly reduced; therefore, calculation time can be greatly shortened. In addition, by switching the orthogonal transformation method according to the existence position of the non-zero orthogonal coefficient component, the calculation amount for the orthogonal transformation can be greatly reduced. In addition, during the decoding process, it is possible to omit the operation of writing data to the memory to perform de-rearrangement after the inverse orthogonal transform and reading data from the memory to perform signal format conversion; therefore, the overall processing time can be reduced . As a result, data transfer between the CPU and external memory becomes unnecessary, and processing time can be greatly reduced.

Claims (56)

1. An encoding method carried out by a calculation device with a processor and a memory, is characterized in that, comprising: a macroblock forming step for dividing input image data of a predetermined signal format into macroblocks composed of a plurality of pixels, and a macroblock unit encoding step for encoding pixels included in the macroblock generated in the macroblock forming step, Wherein, the macroblock unit encoding step includes: an orthogonal transform step for dividing the macroblock into a plurality of blocks and performing the orthogonal transform in units of the block, and an encoding step for encoding the output of said orthogonal transform step, wherein The processor, after reading a macroblock from the memory, does not read the same macroblock from the memory during the successive execution of the orthogonal transform step and the encoding step on the macroblock. 2. An encoding device, characterized in that, comprising: memory for storing macroblocks, macroblock forming means for dividing input image data of a predetermined signal format into macroblocks composed of a plurality of pixels, and macroblock unit encoding means for encoding pixels included in the macroblock generated by the macroblock forming means, Wherein, the macroblock unit encoding device includes: Orthogonal transformation means for dividing the macroblock into a plurality of blocks and performing the orthogonal transformation in units of the block, and encoding means for encoding the output of said orthogonal transform means, wherein After the macroblock-unit encoding means reads out the macroblock from the memory, it does not read the macroblock from the Read the same macroblock from memory. 3. The encoding method according to claim 1, wherein said input image data comprises brightness, a first color difference signal and a second color difference signal, and the image data obtained after said signal format conversion comprises brightness, a second color difference signal A color-difference signal and a second color-difference signal having a different structure than before said conversion. 4. The encoding device according to claim 2, wherein said input image data comprises brightness, first color difference and second color difference signals, and the image data obtained after said signal format conversion comprises brightness, The first color-difference and second color-difference signals have a different structure than before said conversion. 5. An encoding method for encoding input image data in a predetermined signal format by dividing said image data into block units and performing orthogonal transformation in said block units, When an output value Y0, i.e., X0+X1 and an output value Y1, i.e., X0−X1 are generated from two input values X0 and X1 by at least an orthogonal transformation calculation, It is characterized in that the method comprises: First, an addition step for adding the X0 to the X1 to produce a new X1, Second, a doubling step for doubling the X0 to produce a new X0, and Third, a subtraction step for subtracting said new X1 from said new X0 to produce an updated X0, wherein The new X1 is used as output value Y0, and the updated X0 is used as output value Y1. 6. An encoding device for encoding input image data in a predetermined signal format by dividing said image data into block units and performing orthogonal transformation in said block units, When an output value Y0, i.e., X0+X1 and an output value Y1, i.e., X0−X1 are generated from two input values X0 and X1 by at least an orthogonal transformation calculation, It is characterized in that the device includes: First, adding means for adding said X0 to said X1 to produce a new X1, Second, a doubling means for doubling the X0 to produce a new X0, and Third, subtraction means for subtracting said new X1 from said new X0 to produce an updated X0, wherein The new X1 is used as output value Y0, and the updated X0 is used as output value Y1. 7. An encoding method for encoding input image data in a predetermined signal format by dividing said image data into block units and performing orthogonal transformation in said block units, When an output value Y0, i.e., X0+X1 and an output value Y1, i.e., X0−X1 are generated from two input values X0 and X1 by at least an orthogonal transformation calculation, It is characterized in that the method comprises: First, a subtraction step for subtracting said X1 from said X0 to produce a new X0, Second, a doubling step for doubling the X1 to produce a new X1, and Third, an addition step of adding said new X0 to said new X1 to produce an updated X1, wherein The updated X1 is used as the output value Y0 and the new X0 is used as the output value Y1. 8. An encoding device for encoding input image data in a predetermined signal format by dividing said image data into block units and performing orthogonal transformation in said block units, When an output value Y0, i.e., X0+X1 and an output value Y1, i.e., X0−X1 are generated from two input values X0 and X1 by at least an orthogonal transformation calculation, It is characterized in that the device includes: Firstly, subtraction means for subtracting said X1 from said X0 to generate new X0, Second, a doubling means for doubling said X1 to produce new X1, and Third, means for adding said new X0 to said new X1 to produce an updated X1, where The updated X1 is used as the output value Y0 and the new X0 is used as the output value Y1. 9. An encoding method for encoding input image data in a predetermined signal format by dividing said image data into block units and performing orthogonal transformation in said block units, When an output value Y0, i.e., X0+X1 and an output value Y1, i.e., X0−X1 are generated from two input values X0 and X1 by at least an orthogonal transformation calculation, It is characterized in that the method comprises: First, a first addition step for adding said X0 to said X1 to produce a new X1, Next, a second addition step for adding said X0 to said X0 to produce a new X0, and Third, a subtraction step for subtracting said new X1 from said new X0 to produce an updated X0, wherein The new X1 is used as output value Y0, and the updated X0 is used as output value Y1. 10. An encoding device for encoding input image data in a predetermined signal format by dividing said image data into block units and performing orthogonal transformation in said block units, When an output value Y0, i.e., X0+X1 and an output value Y1, i.e., X0−X1 are generated from two input values X0 and X1 by at least an orthogonal transformation calculation, It is characterized in that the device includes: First, a first adding means for adding said X0 to said X1 to generate a new X1, Secondly, a second adding means for adding said X0 to said X0 to generate new X0, and Third, subtraction means for subtracting said new X1 from said new X0 to produce an updated X0, wherein The new X1 is used as output value Y0, and the updated X0 is used as output value Y1. 11. An encoding method for encoding input image data in a predetermined signal format by dividing said image data into block units and performing orthogonal transformation in said block units, When an output value Y0, i.e., X0+X1 and an output value Y1, i.e., X0−X1 are generated from two input values X0 and X1 by at least an orthogonal transformation calculation, It is characterized in that the method comprises: First, a subtraction step for subtracting said X1 from said X0 to produce a new X0, Next, a first addition step for adding said X1 to said X1 to produce a new X1, and Third, a second addition step for adding said new X0 to said new X1 to produce an updated X1, wherein The updated X1 is used as the output value Y0 and the new X0 is used as the output value Y1. 12. An encoding device for encoding input image data in a predetermined signal format by dividing said image data into block units and performing orthogonal transformation in said block units, When an output value Y0, i.e., X0+X1 and an output value Y1, i.e., X0−X1 are generated from two input values X0 and X1 by at least an orthogonal transformation calculation, It is characterized in that the device includes: Firstly, subtraction means for subtracting said X1 from said X0 to generate new X0, Next, first adding means for adding said X1 to said X1 to produce new X1, and Third, a second adding means for adding said new X0 to said new X1 to produce an updated X1, wherein The updated X1 is used as the output value Y0 and the new X0 is used as the output value Y1. 13. An encoding method for encoding input image data in a predetermined signal format by dividing said image data into block units and performing orthogonal transformation in said block units, When an output value Y0, i.e., X0+X1 and an output value Y1, i.e., X0−X1 are generated from two input values X0 and X1 by at least an orthogonal transformation calculation, It is characterized in that the method comprises: First, a first addition step for adding said X0 to said X1 to produce a new X1, Next, a shifting step for shifting said X0 used as a binary number one bit sideways to a high-order bit to generate a new X0, and Third, a subtraction step for subtracting said new X1 from said new X0 to produce an updated X0, wherein The new X1 is used as output value Y0, and the updated X0 is used as output value Y1. 14. An encoding device for encoding input image data in a predetermined signal format by dividing said image data into block units and performing orthogonal transformation in said block units, When an output value Y0, i.e., X0+X1 and an output value Y1, i.e., X0−X1 are generated from two input values X0 and X1 by at least an orthogonal transformation calculation, It is characterized in that the device includes: Firstly, a first adding means for adding said X0 to said X1 to generate a new X1, Next, shifting means for shifting said X0 used as a binary number to the high-order bit by one bit to generate a new X0, and Third, subtraction means for subtracting said new X1 from said new X0 to produce an updated X0, wherein The new X1 is used as output value Y0, and the updated X0 is used as output value Y1. 15. An encoding method for encoding input image data in a predetermined signal format by dividing said image data into block units and performing orthogonal transformation in said block units, When an output value Y0, i.e., X0+X1 and an output value Y1, i.e., X0−X1 are generated from two input values X0 and X1 by at least an orthogonal transformation calculation, It is characterized in that the method comprises: First, a subtraction step for subtracting said X1 from said X0 to produce a new X0, second, a shift step for shifting said X1 used as a binary number one bit to the high-order bit sideways to produce a new X1, and Third, a second addition step for adding said new X0 to said new X1 to produce an updated X1, wherein The updated X1 is used as the output value Y0 and the new X0 is used as the output value Y1. 16. An encoding device for encoding input image data in a predetermined signal format by dividing said image data into block units and performing orthogonal transformation in said block units, When an output value Y0, i.e., X0+X1 and an output value Y1, i.e., X0−X1 are generated from two input values X0 and X1 by at least an orthogonal transformation calculation, It is characterized in that the device includes: Firstly, subtraction means for subtracting said X1 from said X0 to generate new X0, second, shifting means for shifting said X1 used as a binary number one bit sideways to a high-order bit to generate a new X1, and Third, a second adding means for adding said new X0 to said new X1 to produce an updated X1, wherein The updated X1 is used as the output value Y0 and the new X0 is used as the output value Y1. 17. A decoding method for performing variable length decoding, orthogonal inverse transformation and signal format conversion on coded data to obtain image data, When the maximum codeword length for each codeword of the encoded data is n, wherein n is a natural number, It is characterized in that the variable length decoding step comprises: (1) A first table referring step for referring to a first table by using j-bit data of the code word as input, for outputting a code length from the first table when the code length s is j or less related information and decoded data, and for outputting code length related information and second table access information when the code length s is j+1 or more, and (2) The second table reference step, for calculating the second table address according to the second table access information and the s-bit data of the code word, for referring to the second table according to the second table address, and for outputting decoded data. 18. A decoding device comprising variable length decoding means for variable length decoding encoded data and means for performing orthogonal inverse transform and signal format conversion using a result of said decoding to obtain image data, When the maximum codeword length for each codeword of the encoded data is n, wherein n is a natural number, It is characterized in that the variable length decoding device includes: (1) First table referring means for referring to a first table by using j-bit data of said codeword as input, for outputting a code length from said first table when code length s is j or less related information and decoded data, and for outputting code length related information and second table access information when the code length s is j+1 or more, and (2) a second table reference device, for calculating a second table address according to the second table access information and the s-bit data of the codeword, for referring to the second table according to the second table address, and for outputting decoded data. 19. A decoding method for performing variable length decoding, orthogonal inverse transformation and signal format conversion on coded data to obtain image data, When the coded data is a variable-length encoded codeword string, the maximum codeword length of each codeword is n, wherein n is a natural number, It is characterized in that the variable length decoding step comprises: (1) a codeword string obtaining step, used to obtain j-bit data from the header of the codeword string, (2) A first table referring step for referring to a first table by using said obtained j-bit data as input, for outputting a code length correlation from said first table when the code length s is j or less information and decoded data, and for outputting code length related information and second table access information from said first table when the code length s is j+1 or more, and (3) The second table reference step is used to obtain s-bit data from the header of the codeword string, calculate the second table address according to the second table access information and the s-bit data, and calculate the second table address according to the first two table addresses refer to the second table, and are used to output decoded data, and (4) A displacement step for obtaining a code s from the code length related information, for deleting the s-bit code from the head of the code word string, and for repeating this operation until an end code occurs. 20. A decoding device comprising variable length decoding means for variable length decoding encoded data and means for performing orthogonal inverse transform and signal format conversion using a result of said decoding to obtain image data, When the coded data is a variable-length encoded codeword string, the maximum codeword length of each codeword is n, wherein n is a natural number, It is characterized in that the variable length decoding device includes: (1) a codeword string obtaining device, used to obtain j-bit data from the header of the codeword string, (2) First table referring means for referring to a first table by using said obtained j-bit data as input, for outputting a code length correlation from said first table when the code length s is j or less information and decoded data, and for outputting code length related information and second table access information from said first table when the code length s is j+1 or more, and (3) The second table reference device is used to obtain s-bit data from the header of the code word string, calculate the second table address according to the second table access information and the s-bit data, and calculate the second table address according to the first two table addresses refer to the second table, and are used to output decoded data, and (4) Shifting means for obtaining a code s from said code length related information, for deleting said s-bit code from the head of said code word string, and for repeating this operation until an end code occurs. 21. A decoding method for performing variable length decoding, orthogonal inverse transformation and signal format conversion on coded data to obtain image data, When the coded data is a variable-length encoded codeword string, the maximum codeword length of each codeword is n, wherein n is a natural number, It is characterized in that the variable length decoding step comprises: (1) a codeword string obtaining step, used to obtain j-bit data from the header of the codeword string, (2) Expanding the first table referencing step, wherein the first table is referred to by using the obtained j-bit data as input, and when the sum of the code lengths of k or less consecutive codewords is j or less, from The first table outputs the code length related information of the k consecutive code words and the decoded data of each code word in the k or less consecutive code words, and when the code length s is j+1 or more , outputting code length related information and second table access information from said first table, and (3) The second table reference step is used to obtain the s-bit data from the header of the codeword string, calculate the second table address from the second table access information and the s-bit data, and calculate the second table address according to the first A second table address refers to the second table, and is used to output decoded data. 22. A decoding device comprising variable length decoding means for variable length decoding encoded data and means for performing orthogonal inverse transform and signal format conversion using a result of said decoding to obtain image data, When the coded data is a variable-length encoded codeword string, the maximum codeword length of each codeword is n, wherein n is a natural number, It is characterized in that the variable length decoding device includes: (1) codeword string obtaining means for obtaining j-bit data from the header of said codeword string, and extending the first table referring means, wherein the first table is referred to by using the obtained j-bit data as input, and When the sum of the code lengths of k or fewer consecutive codewords is j or less, output the code length-related information of the k consecutive codewords and the k or fewer consecutive codewords from the first table and when the code length s is j+1 or more, output code length related information and second table access information from said first table, and (2) The second table reference device is used to obtain s-bit data from the header of the codeword string, calculate the second table address from the second table access information and the s-bit data, and calculate the address of the second table according to the first A second table address refers to the second table, and is used to output decoded data. 23. A decoding method for performing variable length decoding, orthogonal inverse transformation and signal format conversion on coded data to obtain image data, When the coded data is a variable-length encoded codeword string, the maximum codeword length of each codeword is n, wherein n is a natural number, It is characterized in that the variable length decoding step comprises: (1) a codeword string obtaining step, used to obtain j-bit data from the header of the codeword string, (2) A first table referring step, wherein the first table is referred to by using said obtained j-bit data as input, when the sum of the code lengths of m or less consecutive codewords is j or less, and when the unique When determining the sum of the code lengths of the m consecutive codewords and the codewords next to the m consecutive codewords, outputting information about the m consecutive codewords and the m consecutive codewords from the first table information on the total code length of , decoded data for each of said m or fewer consecutive codewords and second table access information on said codeword following said m consecutive codewords, and (3) A second table referring step of accessing a second table by using the second table access information as an input, and outputting decoded data on said codeword following said m consecutive codewords. 24. A decoding device comprising variable length decoding means for variable length decoding encoded data and means for performing orthogonal inverse transform and signal format conversion using a result of said decoding to obtain image data, When the coded data is a variable-length encoded codeword string, the maximum codeword length of each codeword is n, wherein n is a natural number, It is characterized in that the variable length decoding device includes: (1) a codeword string obtaining device, used to obtain j-bit data from the header of the codeword string, (2) First table referring means, wherein the first table is referred to by using said obtained j-bit data as input, when the sum of the code lengths of m or less consecutive codewords is j or less, and when the unique When determining the sum of the code lengths of the m consecutive codewords and the codewords next to the m consecutive codewords, outputting information about the m consecutive codewords and the m consecutive codewords from the first table information on the total code length of , decoded data for each of said m or fewer consecutive codewords and second table access information on said codeword following said m consecutive codewords, and (3) Second table referring means for accessing a second table by using said second table access information as an input, and outputting decoded data on said codeword following said m consecutive codewords. 25. The decoding method according to any one of claims 17, 19, 21 or 23, wherein said j is a natural number satisfying j<n, and by inputting at least j bits into said first Table to uniquely determine the relevant information of the code length. 26. The decoding device according to any one of claims 18, 20, 22 or 24, wherein said j is a natural number satisfying j<n, and by inputting at least j bits into said first Table to uniquely determine the relevant information of the code length. 27. The decoding method according to any one of claims 17, 19, 21 or 23, wherein, relative to the variable-length code undergoing said variable-length decoding, when the probability of occurrence of data is higher The assigned code length is shorter. 28. The decoding device according to any one of claims 18, 20, 22 or 24, wherein, relative to the variable-length code undergoing said variable-length decoding, when the probability of occurrence of data is higher The assigned code length is shorter. 29. The decoding method according to any one of claims 17, 19 or 21, wherein when the second table accesses information, the masking mode and offset of the codeword corresponding to it are output value. 30. The decoding device according to any one of claims 18, 20 or 22, wherein, as the second table access information, the masking mode and offset value of the codeword corresponding to it are output . 31. The decoding method according to claim 23, wherein a table access address offset value is output as the second table access information. 32. The decoding device according to claim 24, wherein a table access address offset value is output as the second table access information. 33. The decoding method according to claim 17 or 19, wherein said n=16 and said j=8. 34. The decoding device according to claim 18 or 20, wherein said n=16 and said j=8. 35. The decoding method according to claim 21, wherein said n=16, said j=8 and said k=2. 36. The decoding apparatus according to claim 22, wherein said n=16, said j=8 and said k=2. 37. The decoding method according to claim 23, wherein said n=16, said j=8 and said m=1. 38. The decoding apparatus according to claim 24, wherein said n=16, said j=8, and said m=1. 39. A decoding method for performing orthogonal inverse transformation and signal format conversion on coded data to obtain image data, When an output value Y0, i.e., X0+X1, and an output value Y1, i.e., X0-X1 are produced from two input values X0 and X1, calculated by at least an orthogonal inverse transformation, It is characterized in that the method comprises: First, an addition step for adding said X0 to said X1 to produce a new X1, Second, a doubling step for doubling the X0 to produce a new X0, and Third, an addition step for subtracting said new X1 from said new X0 to produce an updated X0, wherein The new X1 is used as output value Y0, and the updated X0 is used as output value Y1. 40. A decoding device for performing orthogonal inverse transformation and signal format conversion on coded data to obtain image data, When an output value Y0, i.e., X0+X1, and an output value Y1, i.e., X0-X1 are produced from two input values X0 and X1, calculated by at least an orthogonal inverse transformation, It is characterized in that the device includes: First, adding means for adding said X0 to said X1 to produce a new X1, Second, a doubling means for doubling said X0 to produce a new X0, and Third, subtraction means for subtracting said new X1 from said new X0 to produce an updated X0, wherein The new X1 is used as output value Y0, and the updated X0 is used as output value Y1. 41. A decoding method for performing orthogonal inverse transformation and signal format conversion on coded data to obtain image data, When an output value Y0, i.e., X0+X1, and an output value Y1, i.e., X0-X1 are produced from two input values X0 and X1, calculated by at least an orthogonal inverse transformation, It is characterized in that the method comprises: First, a subtraction step for subtracting said X1 from said X0 to produce a new X0, Second, a doubling step for doubling said X1 to produce new X1, and Third, an addition step for adding said new X0 to said new X1 to produce an updated X1, wherein The updated X1 is used as output value Y0 and the new X0 is used as output value Y1. 42. A decoding device for performing orthogonal inverse transformation and signal format conversion on coded data to obtain image data, When an output value Y0, i.e., X0+X1, and an output value Y1, i.e., X0-X1 are produced from two input values X0 and X1, calculated by at least an orthogonal inverse transformation, It is characterized in that the device includes: Firstly, subtraction means for subtracting said X1 from said X0 to generate new X0, Second, a doubling means for doubling said X1 to produce a new X1, and Third, adding means for adding said new X0 to said new X1 to produce an updated X1, wherein The updated X1 is used as output value Y0 and the new X0 is used as output value Y1. 43. A decoding method for performing orthogonal inverse transformation and signal format conversion on coded data to obtain image data, When an output value Y0, i.e., X0+X1, and an output value Y1, i.e., X0-X1 are produced from two input values X0 and X1, calculated by at least an orthogonal inverse transformation, It is characterized in that the method comprises: First, a first addition step for adding said X0 to said X1 to produce a new X1, Next, a second addition step for adding said X0 to said X0 to produce a new X0, and Third, a subtraction step for subtracting said new X1 from said new X0 to produce an updated X0, wherein The new X1 is used as the output value Y0, and the updated X0 is used as the output value Y1. 44. A decoding device for performing orthogonal inverse transformation and signal format conversion on coded data to obtain image data, When an output value Y0, i.e., X0+X1, and an output value Y1, i.e., X0-X1 are produced from two input values X0 and X1, calculated by at least an inverse orthogonal transformation, It is characterized in that the device includes: First, a first adding means for adding said X0 to said X1 to generate a new X1, Secondly, a second adding means for adding said X0 to said X0 to generate new X0, and Third, subtraction means for subtracting said new X1 from said new X0 to produce an updated X0, wherein The new X1 is used as the output value Y0, and the updated X0 is used as the output value Y1. 45. A decoding method for performing orthogonal inverse transformation and signal format conversion on coded data to obtain image data, When an output value Y0, i.e., X0+X1, and an output value Y1, i.e., X0-X1 are produced from two input values X0 and X1, calculated by at least an orthogonal inverse transformation, It is characterized in that the method comprises: First, a subtraction step for subtracting said X1 from said X0 to produce a new X0, Next, a first addition step for adding said X1 to said X1 to produce a new X1, and Third, a second addition step for adding said new X0 to said new X1 to produce an updated X1, wherein The updated X1 is used as output value Y0, and the new X0 is used as output value Y1. 46. A decoding device for performing orthogonal inverse transformation and signal format conversion on coded data to obtain image data, When an output value Y0, i.e., X0+X1, and an output value Y1, i.e., X0-X1 are produced from two input values X0 and X1, calculated by at least an orthogonal inverse transformation, It is characterized in that the device includes: Firstly, subtraction means for subtracting said X1 from said X0 to generate new X0, Next, first adding means for adding said X1 to said X1 to produce new X1, and Third, a second adding means for adding said new X0 to said new X1 to produce an updated X1, wherein The updated X1 is used as output value Y0, and the new X0 is used as output value Y1. 47. A decoding method for performing orthogonal inverse transformation and signal format conversion on coded data to obtain image data, When an output value Y0, i.e., X0+X1, and an output value Y1, i.e., X0-X1 are produced from two input values X0 and X1, calculated by at least an orthogonal inverse transformation, It is characterized in that the method comprises: First, a first addition step for adding said X0 to said X1 to produce a new X1, Second, a shifting step for shifting said X0 used as a binary number one bit sideways to a high-order bit to generate a new X0, and Third, a subtraction step for subtracting said new X1 from said new X0 to produce an updated X0, wherein The new X1 is used as the output value Y0, and the updated X0 is used as the output value Y1. 48. A decoding device for performing orthogonal inverse transformation and signal format conversion on coded data to obtain image data, When an output value Y0, i.e., X0+X1, and an output value Y1, i.e., X0-X1 are produced from two input values X0 and X1, calculated by at least an orthogonal inverse transformation, It is characterized in that the device includes: First, a first adding means for adding said X0 to said X1 to generate a new X1, secondly, shifting means for shifting said X0 used as a binary number one bit sideways to a high-order bit to generate a new X0, and Third, subtraction means for subtracting said new X1 from said new X0 to produce an updated X0, wherein The new X1 is used as the output value Y0, and the updated X0 is used as the output value Y1. 49. A decoding method for performing orthogonal inverse transformation and signal format conversion on coded data to obtain image data, When an output value Y0, i.e., X0+X1, and an output value Y1, i.e., X0-X1 are produced from two input values X0 and X1, calculated by at least an orthogonal inverse transformation, It is characterized in that the method comprises: First, a subtraction step for subtracting said X1 from said X0 to produce a new X0, Second, a shifting step for shifting said X1 used as a binary number one bit sideways to a high-value bit to generate a new X1, and Third, a second addition step for adding said new X0 to said new X1 to produce an updated X1, wherein The updated X1 is used as output value Y0, and the new X0 is used as output value Y1. 50. A decoding device for performing orthogonal inverse transformation and signal format conversion on coded data to obtain image data, When an output value Y0, i.e., X0+X1, and an output value Y1, i.e., X0-X1 are produced from two input values X0 and X1, calculated by at least an orthogonal inverse transformation, It is characterized in that the device includes: Firstly, subtraction means for subtracting said X1 from said X0 to generate new X0, Next, shifting means for shifting said X1 used as a binary number one bit sideways to a high-order bit to generate a new X1, and Third, a second adding means for adding said new X0 to said new X1 to produce an updated X1, wherein The updated X1 is used as output value Y0, and the new X0 is used as output value Y1. 51. A decoding method carried out by an arithmetic device having a processor and a memory, characterized in that it comprises: a macroblock forming step for dividing the coded data of a predetermined format into predetermined macroblock units, and a macroblock unit decoding step of decoding data contained in the macroblock generated in the macroblock forming step into pixels, Wherein, the macroblock unit decoding step includes: a decoding step, for decoding the macroblock into data obtained by orthogonal transformation in units of multiple blocks included in the macroblock, The orthogonal inverse transform step is used for orthogonally inverse transforming the decoded orthogonally transformed data decoded in the decoding step into pixels, wherein The processor, after reading a macroblock from the memory, does not read the same macroblock from the memory during the continuous execution of the decoding step and the orthogonal inverse transform step on the macroblock. 52. An encoding device, characterized in that it comprises: memory for storing macroblocks, macroblock forming means for dividing the encoded data of a predetermined format into predetermined macroblock units, and macroblock unit decoding means for decoding data included in the macroblock generated by the macroblock forming means into pixels, Wherein, the macroblock unit decoding device includes: a decoding device, configured to decode the macroblock into data obtained by orthogonal transformation in units of multiple blocks included in the macroblock, an orthogonal inverse transform step, for orthogonally inverse transforming the orthogonally transformed data decoded by the decoding device into pixels, wherein After the macroblock unit decoding means reads out the macroblock from the memory, while the decoding and the orthogonal inverse transform operations in the decoding means and the orthogonal inverse transform means are continuously performed on the macroblock, no The same macroblock is read from the memory. 53. The decoding method according to claim 51, wherein the image data in the predetermined signal format includes brightness, first color difference and second color difference signals, and the data after signal format conversion includes red , green and blue signals. 54. The decoding apparatus according to claim 52, wherein said image data in said predetermined signal format includes luminance, first color difference, and second color difference signals, and the data after signal format conversion includes red , green and blue signals. 55. The decoding method according to claim 51, wherein the image data in the predetermined signal format includes brightness, first color difference and second color difference signals, and the image data after signal format conversion includes brightness , a first color-difference signal and a second color-difference signal, which have a different structure than before the conversion. 56. The decoding apparatus according to claim 52, wherein the image data in the predetermined signal format includes brightness, first color difference and second color difference signals, and the image data after signal format conversion includes brightness , a first color-difference signal and a second color-difference signal, which have a different structure than before the conversion.

Images