VARIABLE LENGTH CODING METHOD AND VARIABLE LENGTH DECODING METHOD

CODAGE/DECODAGE A LONGUEUR VARIABLE

English Abstract

According to the present invention, an image coding apparatus provides a run-length encoding unit RLE1 that subjects quantized coefficients which are obtained by quantizing frequency components of an image signal to a variable length coding process by using a run value Run that indicates the number of successive zero coefficients and a level value Lev that indicates a value of a non- zero coefficient following the zero coefficients. The run-length encoding unit RLE1 includes an reordering unit Lreodr for reordering level values Lev; a variable length coder LVLC for coding reordered level values ROLev by using a code table that is selected according to the value of a quantization parameter QP; a reordering unit Rreodr for reordering run values Run from high frequency component of the quantized coefficients to low frequency component; and a variable length coder RVLC for coding reordered run values RORun by using a code table that is selected according to the number of already-processed run values. Accordingly, a variable length coding process for quantized coefficients is carried out at a higher coding efficiency, with redundant information included in the coefficients being effectively reduced.

French Abstract

La présente invention concerne un codeur d'image dont le module de codage par longueur de plage (RLE1) prend des coefficients quantifiés issus de la quantification de composantes de fréquences d'un signal d'image et les soumet à un codage par longueur de plage. Il utilise à cet effet, d'une part une valeur de passage (Run) qui indique le nombre de coefficients nuls successifs, et d'autre part une valeur de niveau (Lev) qui indique une valeur d'un coefficient non nul suivant les coefficients nuls. Ce module de codage par longueur de plage (RLE1) comporte plusieurs modules. Un module de réagencement (Lreodr) remet en ordre les valeurs de niveaux (Lev). Un codeur par longueur de plage (LVLC) code les valeurs de niveaux remises en ordre (ROLev). Il utilise à cet effet une table de transcodage choisie en fonction de la valeur d'un paramètre de quantification (QP). Un module de réagencement (Rreodr) remet en ordre les valeurs de plages (Run) par valeurs décroissantes des coefficients quantifiés des composantes de fréquences. Enfin, un codeur par longueur de plage (RVLC) code les valeurs de plages remises en ordre (RORun). Il utilise à cet effet une table de transcodage choisie en fonction du nombre de valeurs de plages déjà traitées. L'invention permet ainsi de réaliser, avec une efficacité élevée, un codage par longueur de plage concernant des coefficients quantifiés, tout en réduisant les redondances d'informations des coefficients.

Claims

140
The embodiments of the invention in which an exclusive
property or privilege is claimed are defined as follows:
1. A method for decoding coded data of a block image,
the method comprising:
receiving the coded data including a coded run value
and a coded level value, wherein the coded run value is
obtained by coding a run value which indicates the number
of continuous quantized coefficients, each having a zero
value, and the coded level value is obtained by coding a
level value which indicates a value of a quantized
coefficient having a non-zero value;
decoding the coded run value to obtain a decoded run
value;
decoding the coded level value to obtain a decoded
level value; and
obtaining quantized coefficients of the block image
from the decoded level value and the decoded run value;
wherein the decoding of the coded run value is performed from
a high frequency component toward a low frequency component,
in accordance with information about a total number of
undecoded quantized coefficients which are not subjected to
the decoding process.
2. The method of Claim 1, wherein the undecoded
quantized coefficients are undecoded zero-value coefficients.
3. A decoding apparatus for decoding coded data of a
block image, said apparatus comprising:
a unit operable to receive the coded data including
a coded run value and a coded level value, wherein the
coded run value is obtained by coding a run value which
indicates the number of continuous quantized

141
coefficients, each having a zero value, and the coded
level value is obtained by coding a level value which
indicates a value of a quantized coefficient having a
non-zero value;
a unit operable to decode the coded run value to
obtain a decoded run value;
a unit operable to decode the coded level value to
obtain a decoded level value; and
a unit operable to obtain quantized coefficients of
the block image from the decoded level value and the
decoded run value;
wherein the decoding of the coded run value is performed from
a high frequency component toward a low frequency component,
in accordance with information about a total number of
undecoded quantized coefficients which are not subjected to a
decoding process.

Description

CA 02607755 2007-11-13
1
DESCRIPTION
VARIABLE LENGTH CODING METHOD AND VARIABLE LENGTH DECODING
METHOD
Technical Field
The present invention relates to a variable length
coding method and a variable length decoding method and,
more particularly, to a method for converting plural
coefficients which are obtained by quantizing frequency
components of image data (quantization coefficients) into
coded data according to a variable length coding process,
and a method for decoding the coded data according to a
variable length decoding process to reconstitute plural
coefficients.
Background Art
In recent years, we have greeted the age of multimedia
in which audio, video and other data are integrally handled,
and conventional information media (i.e., means for
transmitting information to persons), such as newspapers,
magazines, televisions, radios, and telephones have been
adopted as subjects of multimedia. Generally,
"multimedia" means to represent not only characters but
also diagrams, speeches and especially images
simultaneously in relation with each other. In order to
handle the conventional information media as the subjects
of multimedia, it is essential to transform the information
into digital format.

CA 02607755 2007-11-13
2
When the quantity of data processes by each
information medium described above is estimated as the
quantity of digital data, in the case of characters, the
data quantity for each character is 1-2 bytes. However,
in the case of speech, the data quantity is 64 kbits per
second (quality for telecommunication) and, in the case
of moving pictures, it is more than 100 Mbits per second
(quality for current television broadcasting).. So, as for
the information media described above, it is not practical
to handle such massive data as it is in the digital format.
For example, visual telephones have already been put to
practical use by ISDN (Integrated Services Digital
Network) having a transmission rate of 64kbps - 1.5Mbps,
but it is impossible to transmit an output image of a
television camera having a large quantity of data as it
is by the ISDN.
So, data compression technologies are demanded. For
example in the case of visual telephones, the moving
picture compression technologies standardized as H.261 and
H.263 by ITU-T (International Telecommunication Union-
Telecommunication Sector) are employed. Further,
according to the data compression technology based on
MPEG-1, it is possible to record image data, together with
audio data, in an ordinary music DC (compact disk).
Here, MPEG (Moving Picture Experts Group) is an
international standard associated with digital
compression for image signals of moving pictures. In
MPEG-1, an image signal of a moving picture is compressed
to 1.5 Mbps, i.e., data of a television signal is compressed

CA 02607755 2007-11-13
3
to about 1/100. Since the transmission rate to which
MPEG-1 is directed is mainly restricted to about 1.5 Mbps,
MPEG-2 is standardized to meet the demands for higher image
quality. In MPEG-2, an image signal of a moving picture
is compressed to 2-15 Mbps.
Under the existing circumstances, standardization of
MPEG-4 having a higher compression rate has been realized
by the working group for the standardization of MPEG-1 and
MPEG-2 (ISO/IEC JTC1/SC29/WG11). MPEG-4 not only enables
coding at a low bit rate with high efficiency but also
realizes introduction of a strong error resistant
technology that can reduce a subjective deterioration of
image quality even when a transmission line error occurs.
Further, ITU-T is developing standardization of H.26L as
an image coding method of the next generation, and the
latest coding method at this point of time is a method called
"Test Model 8" (TML8).
Fig. 30 is a block diagram illustrating a conventional
image coding apparatus.
This image coding apparatus 201a has a blocking unit
Blk for blocking an inputted image signal Vin into unit
areas (blocks) each comprising a predetermined number of
pixels and outputting an blocked image signal BlkS, and
a frequency transformation unit Trans for subjecting the
output BlkS to frequency transformation to output
frequency components TransS corresponding to respective
blocks. Here, the block is an area of a predetermined size
in a picture (image space) , which is a unit for a coding
process of an image signal, and it is composed of a

CA 02607755 2007-11-13
4
predetermined numberofpixels. Here, theimagesignalVin
corresponds to a moving image that is composed of plural
pictures.
The image coding apparatus 201a further includes a
quantization unit Q for quantizing the outputs (frequency
components) TransS from the frequency transformation unit
and outputting quantized components (quantization
coefficients) QS corresponding to respective blocks, and
a coding unit RLEOa for subjecting the outputs (quantized
components) Qs from the quantization unit to a variable
length coding process.
Next, its operation will be described.
When an image signal Vin is inputted to the image
coding apparatus 201a, the blocking unit Blk divides the
inputted image signal Vin into image signals corresponding
to block units, to generate an image signal (blocked image
signal) B1kS corresponding to each block. The frequency
transformation unit Trans transforms the blocked image
signal BlkS into frequency components TransS according to
DCT (Discrete Cosine Transformation) or Wavelet
transformation. The quantization unit Q quantizes the
frequency components TransS in a predetermined
quantization step on the basis of a quantization parameter
QP to output quantized components QS, as well as outputs
thequantizationparameterQP. Then, the coding unitRLEOa
subjects the quantized components QS to a variable length
coding process, and outputs a coded steam StrOa.
Fig. 31 is a block diagram for explaining the coding
unit RLEOa that constitutes the image coding apparatus

CA 02607755 2007-11-13
201a.
This coding unit RLEOa has a zigzag scanner Scan for
transforming the outputs (quantized components) QS of the
quantization unit Q in a two-dimensional array into
5 quantized component Coef in a one-dimensional array (i.e.,
predetermined order) , and a variable length coder VLC for
subjecting the quantized component's Coef outputted from
the zigzag scanner Scan to a variable length coding
process.
When the quantized components QS outputted from the
quantization unit Q are inputted to the coding unit RLEOa,
the zigzag scanner Scan transforms the quantized
components QS in a two-dimensional array from the
quantization unit Q into quantized components Coef in a
one-dimensional array (predetermined order), and outputs
the quantized components.
Fig. 43 is a diagram for specifically explaining the
process for transforming the quantized components QS by
the zigzag scanner Scan.
As shown in Fig. 43, the quantized components QS
outputted from the quantization unit Q have a two-
dimensional array, i.e., an array in which the quantized
components QS arranged in the form of matrix on a two-
dimensional frequency region Fr according to the height
of the horizontal frequency component and the height of
the vertical frequency component.
The zigzag scanner Scan carries out a process for
scanning the quantized components QS in the two-
dimensional array in a zigzag manner as shown by arrows

CA 02607755 2007-11-13
6
Y1 to Y7, to transform the components into quantized
components Coef in a one-dimensional array. That is, in
this scan process, a predetermined order along the scanning
course is set with respect to the plural quantized
components QS in the two-dimensional array.
Then, the variable length coder VLC assigns codes to
the quantized components Coef which are outputted from the
zigzag scanner Scan, with using a code table that shows
a correlation between numerical values indicating the
sizes of the quantized components and codes (code words),
to transform the quantized components into a coded stream
StrOa corresponding to each block.
Fig. 32 is a block diagram for explaining an image
decoding apparatus 202a corresponding to the image coding
apparatus 201a as shown in Fig. 30.
This image decoding apparatus 202a decodes the coded
stream StrOa which is outputted from the conventional image
coding apparatus 201a as shown in Fig. 30.
The image decoding apparatus 202a has a decoding unit
RLDOa for decoding the coded stream StrOa which is
outputted from the image coding apparatus 201a, and an
inverse quantization unit IQ for subjecting outputs
(decoded quantization components) DQS from the decoding
unit RLDOa to an inverse quantization process.
The image decoding apparatus 202a further includes
a inverse frequency transformation unit ITrans for
subjecting outputs (decoded frequency components) ITransS
from the inverse quantization unit IQ to an inverse
frequency transformation process, and a deblocking unit

CA 02607755 2007-11-13
7
Deb1k for generating a decoded image signal Vout
corresponding to each picture on the basis of outputs
(decoded blocked image signals) DB1kS from the inverse
frequency transformation unit ITrans.
Next, its operation will be described.
When the coded stream StrOa is inputted from the image
coding apparatus 201a to the image decoding apparatus 202a,
the decoding unit RLDOa decodes the coded stream StrOa and
outputs decoded quantized components DQS. The operation
of the decoding unit RLDOa is the inverse of the operation
of the coding unit RLEOa.
The inverse quantization unit IQ carries out the
inverse of the operation of the quantization unit Q, i.e.,
an operation of inversely quantizing the decoded quantized
components DQS with referring to the quantization
parameter QP, and outputs decoded frequency components
ITransS. The inverse frequency transformation unit
ITrans carries out the inverse of the operation of the
frequency transformation unit Trans, i.e., an operation
of subjecting the decoded frequency components ITransS to
inverse DCT or inverse wavelet transformation, to
reconstitute decoded image signals DB1kS corresponding to
respective blocks. Then, the deblocking unit DeBlk
integrates the decoded image signals DB1kS of the
respective blocks to output a decoded image signal Vout
corresponding to each picture (frame).
Fig. 33 is a block diagram for explaining the decoding
unit RLDOa that constitutes the image decoding apparatus
202a.

CA 02607755 2007-11-13
8
The decoding unit RLDOa has a variable length decoder
VLD for subjecting the coded stream StrOa to a variable
length decoding process to decode the quantized component
Coef corresponding to each code included in the coded
stream StrOa, and an inverse zigzag scanner IScan for
reconstituting quantized components DQS in a two-
dimensional array from the decoded quantized components
Coef in a one-dimensional array, which are outputted from
the variable length decoder VLD.
In this decoding unit RLDOa, the variable length
decoder VLD decodes the coded stream StrOa according to
the inverse operation to the variable length coder VLC,
and outputs quantized components Coef corresponding to
codes (codewords). Then, the inverse zigzag scanner IScan
carries out the inverse operation to the zigzag scanner
Scan, to reconstitute decoded quantized components DQS in
a two-dimensional array from the quantized components Coef
in a one-dimensional array, which are outputted from the
variable length decoder VLD, and outputs the decoded
quantized components DQS to the inverse quantization unit
IQ.
Japanese Published Patent Application No. Hei.6-
311534 discloses a method in which an image signal is
divided into a luminance signal and a color-difference
signal to subject the obtained signals to a variable length
coding process.
The plural quantized components corresponding to
respective blocks, to which the predetermined order has
been set, are data including a high redundancy, i.e., data

CA 02607755 2007-11-13
9
in which plural coefficients whose values are zero (zero
coefficients) continue after a coefficient whose value is
not zero (non-zero coefficient) . To encode such quantized
components, a method in which quantized components are
encoded with its redundant information being deleted, for
example, a run-length encoding method in which quantized
components are encoded by using a run value that indicates
the number of successive zero coefficients and a level
value that indicates a value of a non-zero coefficient
following the zero coefficients has been conventionally
employed.
Hereinafter, a conventional image coding apparatus
using the run-length encoding method will be described.
Fig. 34 is a block diagram illustrating a conventional
image coding apparatus that carries out the run-length
encoding.
This image coding apparatus 201b includes, in place
of the coding unit RLEOa of the image coding apparatus 201a
shown in Fig. 30, a run-length encoding unit RLEOb for
subjecting outputs (quantized components) QS from the
quantization unit Q to run-length encoding and outputting
a coded stream StrOb. Other components are the same as
those of the image coding apparatus 201a.
The operation of the image coding apparatus 201b is
different from that of the image coding apparatus 201a only
in the operation of the coding unit RLEOb.
Fig. 35 is a block diagram illustrating a specific
construction of the coding unit RLEOb in the image coding
apparatus 201b.

CA 02607755 2007-11-13
This run-length encoding unit RLEOb has, like the
coding unit RLEOa, a zigzag scanner Scan for transforming
outputs (quantized components) QS in a two-dimensional
array from the quantization unit Q into quantized
5 components Coef in a one-dimensional (i.e., a
predetermined order).
Then, this run-length encoding unit RLEOb further
includes a run calculator RunCal for calculating the number
of successive quantized components whose values are zero
10 (zero coefficients) Coef and outputting a run value Run
indicating the number of successive zero coefficients, and
a level calculator LevCal for calculating a value of a
quantized component whose value is not zero (non-zero
coefficient), following the zero coefficients, and
outputting a level value Lev indicating the value of the
non-zero coefficient.
The run-length encoding unit RLEOb further includes
a variable length coder LevVLC for subjecting the level
value Lev that is outputted from the level calculator
LevCal to a variable length coding process and outputting
a code string (level value code string) LStr, a variable
length coder RunVLC for subjecting the run value Run that
is outputted from the run calculator RunCal to a variable
length coding process and outputting a code string (run
value code string) RStr, and a multiplexer MUX for
multiplexing the level value code string LStr and the run
value code string RStr for each block and outputting a
multiplexed coded stream StrOb.
Next, its operation will be described.

CA 02607755 2007-11-13
11
The zigzag scanner Scan transforms the quantized
components QS in a two-dimensional array, which are
outputted from the quantization unit Q, into quantized
components Coef in a one-dimensional array (predetermined
order), and outputs the quantized components Coef. The
transformation process for the quantized components Qs by
the zigzag scanner Scan is carried out in the same manner
as that in the coding unit RLEOa of the image coding
apparatus 201a.
The run calculator RunCal calculates the number of
successive zero coefficients on the basis of the quantized
components Coef which are outputted from the zigzag scanner
Scan, and outputs a run value Run indicating the calculated
number. The level calculator LevCal calculates a value of
a non-zero coefficient that follows the successive zero
coefficients, on the basis of the quantized components Coef
outputted from the zigzag scanner Scan, and outputs a level
value Lev indicating this value.
Here, the run calculator RunCal generate a special
value EOB (End of Block) when detecting the highest
frequency component (the last non-zero coefficient) in the
target block to be processed, to inform that subsequent
higher frequency components have all zero value.
Further, the variable length coder RunVLC subjects
the run value Run which is outputted from the run calculator
RunCal to a variable length coding process for assigning
a code (code word) to the run value according to a code
table or arithmetic operation, and outputs a code string
RStr. The variable length coder LevVLC subjects the level

CA 02607755 2007-11-13
12
value Lev which is outputted from the level calculator
LevCal to a variable length coding process for assigning
a code (code word) to the level value according to a code
table or arithmetic operation, and outputs a code string
LStr.
The multiplexer MUX multiplexes the code string LStr
and the code string RStr for each block, and outputs a
multiplexed coded stream StrOb.
Here, the process for multiplexing the code string
LStr and the code string RStr is carried out for each block,
for example, in such manner that the code string RStr
corresponding to all run values for a target block is
followed by the code string LStr corresponding to all level
values for the target block, or the code string LStr
corresponding to all level values for a target block is
followed by the code string RStr corresponding to all run
values for the target block.
The image coding apparatus as described above for
encoding plural quantized coefficients in a predetermined
order, by using the run value Run indicating the number
of quantized components whose values are zero (zero
coefficients) Coef, and the level value Lev indicating a
value of a quantized component whose value is not zero
(non-zero coefficient) Coef, following the zero
coefficients, can encode the plural quantized coefficients
at a higher coding efficiency, while removing its redundant
information.
Fig. 36 is a block diagram for explaining an image
decoding apparatus 202b corresponding to the image coding

CA 02607755 2007-11-13
13
apparatus 201b as shown in Fig. 34.
This image decoding apparatus 202b decodes the coded
stream StrO that is outputted from the conventional image
coding apparatus 201b as shown in Fig. 34.
The image decoding apparatus 202b has, in place of
the decoding unit RLDOa of the image decoding apparatus
202a shown in Fig. 32, a run-length decoding unit RLDOb
for subjecting the coded stream StrOb that is outputted
from the image coding apparatus 201b to a run-length
decodingprocess. Other components are identical to those
of the image decoding apparatus 202a.
The operation of the image decoding apparatus 202b
is different from the image decoding apparatus 202a only
in the operation of the decoding unit RLDOb.
Fig. 37 is a block diagram illustrating a specific
construction of the run-length decoding unit RLDOb in the
image decoding apparatus 202b.
This run-length decoding unit RLDOb has a
demultiplexer DMUX for demultiplexing the multiplexed
coded stream StrOb that is outputted from the image coding
apparatus 201b to obtain the code string LStr corresponding
to the level values and the code string RStr corresponding
to the run values, a variable length decoder LevVLD for
subjecting the code string LStr to a variable length
decoding process to reconstitute the level values Lev, a
variable length decoder RunVLC for subjecting the code
string RStr to a variable length decoding process to
reconstitute the run values Run, and an inverse zigzag
scanner IScan for reconstituting decoded quantized

CA 02607755 2007-11-13
14
components DQS in a two-dimensional array from decoded
quantized components in a one-dimensional array, which are
represented by the level values Lev and the run values Run.
Next, its operation will be described.
In the image decoding apparatus 202b, the run-length
decoding unit RLDOb carries out the inverse operation to
the run-length encoding unit RLEOb. That is, the run-
length decoding unit RLDOb demultiplexes the multiplexed
coded stream StrOb to obtain the code string Lstr
corresponding to the level values and the code string RStr
corresponding to the run values.
Then, the variable length decoder LevVLD decodes the
code string LStr corresponding to the level values by the
inverse operation to the variable length coder LevVLC, and
outputs the level values Lev. The variable length decoder
RunVLD decodes the code string RStr corresponding to the
run values by the inverse operation to the variable length
coder RunVLC, and output the run values Run.
The inverse zigzag scanner IScan reconstitutes
decoded quantized components DQS in a two-dimensional
array from the quantized components in a one-dimensional
array, which are represented by the level values Lev and
the run values Run, by the inverse operation to the zigzag
scanner Scan, and outputs the decoded quantized components
to the inverse quantization unit IQ. However, this inverse
zigzag scanner IScan (see Fig. 37) is different from the
inverse zigzag scanner IScan as shown in Fig. 33 in that
the level value Lev and the run value Run are inputted
thereto. Thus, the inverse zigzag scanner IScan shown in

CA 02607755 2007-11-13
Fig. 37 has a function of converting a coefficient that
is represented by the level value Lev and the run value
Run into a quantized components Coef.
According to the image decoding apparatus that
5 carries out a decoding process for decoding plural
quantized coefficients in a predetermined order, by using
the run value Run indicating the n"umber of quantized
components whose values are zero (zero coefficients) Coef
and the level value Lev indicating a value of a quantized
10 component whose value is not zero (non-zero coefficient)
Coef, following the zero coefficients, coded data which
is obtained by coding plural quantized components
according to run-length encoding with removing its
redundant information at a higher coding efficiency is
15 decoded satisfactorily.
Hereinafter, another example of the conventional
image coding apparatus using the run-length encoding
method will be described.
Fig. 38 is a block diagram illustrating another
example of the image coding apparatus that employs the
conventional run-length encoding unit. Almost all of the
conventional image coding apparatuses which are compliant
with standards such as MPEG, or H.261 and H.263 (ITU), or
a draft H26L standard (TML8) that is now being planned have
a construction as shown in Fig. 38.
This image coding apparatus 201c performs coding of
quantized coefficients using the run value and the level
value, like the image coding apparatus 201b shown in Fig.
34, while this image coding apparatus 201c does not perform

CA 02607755 2007-11-13
16
a variable length coding process for the run value and the
level value separately like the image coding apparatus 201b,
but performs a variable length coding process for a pair
of the run value and the level value (run-level pair).
To be more specific, the image coding apparatus 201c
has, like the image coding apparatus 201b, a blocking unit
Blk to which an image signal Vin is "inputted, a frequency
transformation unit Trans for subjecting an output BlkS
from the blocking unit to frequency transformation, and
a quantization unit Q for quantizing outputs (frequency
components) TransS from the transformation unit. The
image coding apparatus 201c further includes a run-length
encoding unit RLEOc for subjecting outputs (quantized
components) QS from the quantization unit to a run-length
encoding process for transforming a run-level pair
comprising a run value and a level value into a variable
length code.
Next, its operation will be described.
The blocking unit Blk divides the image signal Vin
into image signals corresponding to block units to generate
pixel value components (blocked image signals) B1kS. The
frequency transformation unit Trans transforms the pixel
value'components BlkS into frequency components TransS
according to DCT (Discrete Cosine Transformation) or
Wavelet transformation. The quantization unit Q
quantizes the frequency components TransS on the basis of
a quantizationparameter QP to output quantized components
QS, as well as outputs the quantization parameter Q. The
run-length encoding unit RLEOc subjects the quantized

CA 02607755 2007-11-13
17
components QS to run-length encoding, and outputs a coded
stream StrOc.
Here, the block is an area of a predetermined size
in the picture (image space) , which is a unit in a coding
process for an image signal, and composed of a
predetermined number of pixels. The run-length encoding
is a process for transforming a pair -comprising a run value
that indicates the number of successive quantized
components whose values are zero (zero coefficients) and
a level value that indicates a value of a quantized
component whose value is not zero (non-zero coefficient),
following the zero coefficients, into a variable length
code, in other words, a process for assigning one variable
length code (code word) to a pair of a run value and a level
value (run-level pair).
Next, the run-length encoding unit RLEOc will be
specifically described.
Fig. 39 is a block di.agram illustrating a conventional
run-length encoding unit RLEOc.
This run-length encoding unit RLEOc has, like the
run-length encoding unit RLEOb as shown in Fig. 35, a zigzag
scanner Scan for transforming the outputs (quantized
components) QS in a two-dimensional array from the
quantization unit Q, into quantized components Coef in a
one-dimensional array (i. e., a predetermined order) ; a run
calculator RunCal for calculating the number of successive
quantized components whose values are zero (zero
coefficients) Coef and outputting a run value Run; and a
level calculator LevCal for calculating a value of a

CA 02607755 2007-11-13
18
quantized component whose value is not zero (non-zero
coefficient) Coef, following the zero coefficients, and
outputting a level value Lev.
The run-length encoding unit RLEOc further includes
a run-level encoder RunLevEnc for obtaining a code number
Code corresponding to a pair of the level value Lev and
the run value Run according to a code table or arithmetic
operation on the basis of the outputs from the run
calculator RunCal and the level calculator LevCal; and a
variable length coder VLC for assigning a code word to the
code number Code to generate a coded stream StrOc
corresponding to the image signal Vin.
Next, its operation will be described.
In the run-length encoding unit RLEOc, like in the
run-length encoding unit RLEOb, the zigzag scanner Scan
transforms quantized components QS in a two-dimensional
array, which are outputted from the quantization unit Q,
into quantized components Coef in a one-dimensional array
(predetermined order) , and outputs the obtained quantized
components.
Fig. 43 is a diagram for specifically explaining a
process for transforming the quantized components QS by
the zigzag scanner Scan.
The quantized components QS outputted from the
quantization unit Q have a two-dimensional array as shown
in Fig. 43, i.e., an array inwhich the quanti zed components
QS arranged in the form of matrix on a two-dimensional
frequency region Fr according to the size of the horizontal
frequency component and the size of the vertical frequency

CA 02607755 2007-11-13
19
component.
The zigzag scanner Scan carries out the process for
scanning the quantized components QS in the two-
dimensional array in a zigzag manner, as shown by arrows
Yl to Y7, to transform the quantized components QS into
quantized components Coef in a one-dimensional array.
That is, this scanning process sets -a predetermined order
along the scanning course, with respect to the plural
quantized components QS in the two-dimensional array.
The run calculator RunCal calculates the number of
successive zero coefficients on the basis of the quantized
components Coef outputted from the zigzag scanner Scan,
and outputs a run value Run indicating the calculated
number. The level calculator LevCal calculates a value of
a non-zero coefficient following the successive zero
coefficients, on the basis of the quantized components Coef
outputted from the zigzag scanner Scan, and outputs a level
value indicating the calculated value. Here, the run
calculator RunCal outputs a specific value EOB (End of
Block) when detecting the highest frequency component (the
last non-zero coefficient) in a target block to be
processed, to inform that subsequent higher frequency
components have all zero value.
Further, the run-level encoder RunLevEnc obtains a
code number Code corresponding to a pair of the level value
Lev and the run value Run on the basis of the outputs from
the run calculator RunCal and the level calculator LevCal,
according to a code table or arithmetic operation. The
variable length coder VLC encodes the code number Code that

CA 02607755 2007-11-13
is obtained by the converter RunLevEnc, i.e., assigns a
code word (bit string) to the code number to generate a
coded stream StrO.
Fig. 42 shows an example of a code table that is
5 employed by the run-length encoding unit RLEOc. The code
table (first coding table) T1 shown in Fig. 42 shows a code
table corresponding to DC components-of a color-difference
signal that is compliant with a draft H.26L standard (TML8)
that is now being planned.
10 This code table T is composed of a regularly generable
part including code numbers corresponding to pairs of level
values and run values which can be calculated according
to an arithmetic operation using level values and run
values (regularly build VLC), and an irregular part
15 including code numbers corresponding to pairs of level
values and run values which cannot be calculated by the
arithmetic operation (table look up VLC) . Further, a bit
string (not shown) is assigned to each code number Code
as a code word in a one-to-one relationship. A shorter code
20 word is assigned to a code number Code having a smaller
value.
Next, a conventional decoding apparatus
corresponding to the image coding apparatus 201c will be
described.
Fig. 40 is a block diagram illustrating an image
decoding apparatus 202c that employs a conventional
run-length decoding unit RLDO.
This image decoding apparatus 202c decodes the coded
stream StrOc that is outputted from the conventional image

CA 02607755 2007-11-13
21
coding apparatus 201c shown in Fig. 39.
The image decoding apparatus 202c decodes quantized
coefficients using the run value and the level value, as
the image decoding apparatus 202b in Fig. 36, while this
image decoding apparatus 202c does not carry out variable
length decoding of the run value and the level value
separately like the image decoding'apparatus 202b, but
carries out variable length decoding of a pair comprising
the run value and the level value (run-level pair).
To be more spec=ific, the image decoding apparatus 202c
has a run-length decoding unit RLDOc that subjects the
coded stream StrOc outputted from the image coding
apparatus 201c to a run-length decoding process using a
run-level pair comprising a run value and a level value.
The image decoding apparatus 202c further has, as the image
decoding apparatus 202b, an inverse quantization unit IQ
for subjecting outputs (decoded quantized components) DQS
from the run-length decoding unit RLDc to an inverse
quantization process; a inverse frequency transformation
unit ITrans for subjecting outputs (decoded frequency
components) ITransS from the inverse quantization unit IQ
to an inverse frequency transformation process; and a
deblocking unit DeBlkfor generating a decoded image signal
Vout corresponding to each picture on the basis of outputs
(decoded pixel value components) DB1kS from the inverse
frequency transformation unit ITrans.
Next, its operation will be described.
In the image decoding apparatus 202c, the run-length
decoding unit RLDOc carries out the inverse of the

CA 02607755 2007-11-13
22
operation of the run-length encoding unit RLEOc. To be
more specific, the run-length decoding unit RLDOc subjects
the coded stream StrOc to a run-length decoding process
to output decoded quantized components DQS. The inverse
quantization unit IQ carries out the inverse operation to
the quantization unit Q, i.e., an operation of inversely
quantizing the decoded quantized components DQS with
referring to a quantization parameter QP to output decoded
frequency components ITransS. The inverse frequency
transformation unit ITrans carries out the inverse
operation to the frequency transformation unitTrans,i.e.,
an operation of subjecting the decoded frequency
components ITransS to inverse DCT or inverse Wavelet
transformation, to reconstitute a decoded pixel value
signal (decoded blocked image signal) DB1kS corresponding
to each block. The deblocking unit DeBlk integrates the
image pixel value components for the respective blocks,
and outputs a decoded image signal Vout corresponding to
each picture (frame).
Next, the run-length decoding unit RLDOc will be
specifically described.
Fig. 41 is a block diagram for explaining a specific
construction of the run-length decoding unit RLDOc.
This run-length decoding unit RLDOc has a variable
length decoder VLD for subjecting the coded stream StrOc
to a variable length decoding process to obtain a code
number Code corresponding to each code (code word) included
in the coded stream StrOc; a run-level detector RunLevDec
for detecting a pair of a level value Lev and a run value

CA 02607755 2007-11-13
23
Run, corresponding to the code number Code; and an inverse
zigzag scanner IScan for reconstituting decoded quantized
components DQS in a two-dimensional array from decoded
quantized components in a one-dimensional array, which are
represented by the level values Lev and the run values Run,
on the basis of the pairs of the level values Lev and the
run values Run.
Next, its operation will be described.
In this run-length decoding unit RLDOc, the variable
length decoder VLD decodes the coded stream StrOc, and
outputs a code number Code corresponding to a code word
(bit string) according to the inverse operation to the
variable length coder VLC. The run-level detector
RunLevDec refers to a code table or performs an arithmetic
operation to output a pair of a level value Lev and a run
value Run, corresponding to the code number Code, according
to the inverse operation to the run-level encoder RunLevEnc.
The inverse zigzag scanner IScan reconstitutes decoded
quantized components DQS in a two-dimensional array from
quantized components in a one-dimensional array which are
represented by the pairs of the level values Lev and the
run values Run according to the inverse operation to the
zigzag scanner Scan, and outputs the decoded quantized
components DQS to the inverse quantization unit IQ.
Japanese Published Patent Application No. Hei.6-
237184 discloses a run-length encoding method in which
plural coefficients in a predetermined order are coded
using a run value Run that indicates the number of quantized
components whose values are zero (zero coefficients) Coef,

CA 02607755 2007-11-13
24
and a level value Lev that indicates a value of a quantized
component whose value is not zero (non-zero coefficient)
Coef, following the zero coefficients.
Japanese Patent No. 3144456 (corresponding to
Japanese Published Patent Application No. Hei.8-79088)
discloses a method by which a variable length coding table
(VLC table) is changed according to the value of a
differential motion vector value when the differential
motion vector value is coded using a variable length coding
table in a method for predictively coding digital video
data.
Further, an arithmetical coding is known as another
method by which the pixel values are variable-length coded,
in which variable length coding is performed according to
an arithmetic operation by using probability in which the
pixel value may take a predetermined value. According to
the arithmetical coding, a code is derived from the
probability, so that a probability table in which
probabilities corresponding to individual situations are
described corresponds to the VLC table. Here, "All about
MPEG-4" (first edition, first print, published September
30, 1998, written and edited by Miki Sukeichi, pp.69-73,
Kogyo Chosakai Publishing Co., Ltd.) describes a method
by which pixel values of pixels corresponding to a coding
target are subjected to arithmetic coding by changing a
probability table on the basis of a prediction method
(context) for a coding target pixel which are predicted
from pixel values of the surrounding pixels.
The above-mentioned coding unit RLEOa of the

CA 02607755 2007-11-13
conventional image coding apparatus 201a performs variable
length coding for plural quantized coefficients which are
obtained by quantizing frequency components of image data,
for each predetermined processing unit (block). This
5 coding unit employs a predetermined code table that
indicates correspondences between numerical value
information showing the size of each quantized coefficient
and a code (code word). In the variable length coding
process by the coding unit, redundant information included
10 in the quantized coefficient (data to be processed) cannot
be removed sufficiently and, thus, the compression rate
may be further improved.
Also in the run-length encoding unit that carries out
variable length coding of plural quantized coefficients
15 using a run value that indicates the number of quantized
components whose values are zero (zero coefficients) Coef,
and a level value that indicates a value of a quantized
component whose value is not zero (non-zero coefficient)
Coef, following the zero coefficients, like the coding
20 units RLEOb or RLEOc in the conventional image coding
apparatus 201b or 201c, redundant information included in
the quantized coefficients in the variable length coding
process is not sufficiently removed.
Further, the decoding unit RLDOa of the conventional
25 image decoding apparatus 202a or the run-length decoding
unit RLDOb or RLDOc of the conventional image decoding
apparatus 202b or 202c corresponds to a coding unit which
cannot sufficiently remove redundant information included
in the quantized coefficients in the variable length coding

CA 02607755 2007-11-13
26
process for the quantized coefficients.
Further, as for the method by which a variable length
coding table (VLC table) is changed according to the value
of a differential motion vector value when the differential
motion vector value is coded using a variable length coding
table in a method for predictively coding digital video
data, an effective change of the coding table in a variable
length coding process for data having such characteristics
that plural zero coefficients successively follow, like
the quantized coefficients which are obtained by
quantizing frequency components of an image signal has not
been known.
The present invention is made to solve the above-
mentioned problems, and this invention has for its object
to provide a variable length coding method and a variable
length decoding method, which can remove redundant
information included in target data (quantized
coefficients) for a variable length coding process, more
effectively according to characteristics of the quantized
coefficients and states of a coding process for the
quantized components, thereby further increasing a
compression rate of an image signal or the like.
Disclosure of the Invention
According to the present invention, there is provided
a variable length codingmethod for coding coefficient data
which is composed of plural coefficients including: a
coding step for subjecting the respective coefficients to
a coding process of transforming the coefficient data into

CA 02607755 2007-11-13
27
coded data which is composed of plural codes, by using
plural code tables indicating correspondences between the
values of the coefficients and codes, and this coding step
includes: a code table selection step for selecting the
code table in accordance with at least one of information
about an coded coefficient which has been coded, and a
parameter relating to encoding process of the
coefficients; and a code assignment step for assigning a
code to a uncoded coefficient which has not yet been coded,
using the selected code table. Therefore, redundant
information included in coefficient data which are to be
subjected to the variable length coding process is
effectively deleted by selection of a code table according
to characteristics of coefficients that constitute the
coefficient data or states of a coding process for the
coefficients, thereby greatly increasing a coding
efficiency of the variable length coding process for image
signals or the like.
According to the present invention, in the above-
mentioned variable length coding method, the coefficients
are obtained by quantizing frequency components of image
data in accordance with a quantization step corresponding
to the image data, and in the code table selection step,
the code table that is used in the code assignment step
is selected according to a value of the quantization step.
Therefore, a code table that is adapted to the value of
the quantization step and maximizes the coding efficiency
can be always employed.
According to the present invention, in the above-

CA 02607755 2007-11-13
28
mentioned variable length coding method, according to the
coding process for the coefficients, a run value that
indicates a number of successive zero coefficients whose
values are zero, and a level value that indicates a value
of a non-zero coefficient following the zero coefficients
are each transformed into a code, in the code table
selection step, at least one of a first selection process
for selecting a code table from plural code tables that
indicate correspondences between the run value and the code
according to the value of the quantization step, and a
second selection process for selecting a code table from
plural code tables that indicate correspondences between
the level value and the code according to the value of the
quantization step is carried out, and in the code
assignment step, a code is assigned to at least one of a
run value and a level value corresponding to an uncoded
coefficient which has not been coded yet, on the basis of
the selected code table. Therefore, the assignment of
codes to at least one of run values and level values can
be performed always by using a code table that is adapted
to the value of the quantization step and minimizes the
total number of bits corresponding to the assigned codes.
According to the present invention, in the above-
mentioned variable length coding method, according to the
coding process for the coefficients, a run-level pair
comprising a run value that indicates a number of
successive zero coefficients whose values are zero and a
level value that indicates a value of a non-zero
coefficient following the zero coefficients is transformed

CA 02607755 2007-11-13
29
into a code, in the code table selection step, a code table
is selected from plural code tables that indicate
correspondences between the run-level pair and the code
according to the value of the quantization step, and in
the code assignment step, a code is assigned to a run-
level pair corresponding to an uncoded coefficient which
has not yet been coded, on the basis of the selected code
table. Therefore, the assignment of codes to run-level
pairs can be performed always by using a code table that
is adapted to the value of the quantization step and
minimizes the total number of bits corresponding to the
assigned codes.
According to the present invention, in the above-
mentioned variable length coding method, in the code table
selection step, the code table that is used in the code
assignment step is selected in accordance with the
information about the already-processed coefficient which
has been coded. Therefore, the coding process for
quantized coefficients can be carried out always by using
a code table that is adapted to the number of uncoded
coefficients and maximizes the coding efficiency.
According to the present invention, in the above-
mentioned variable length coding method, according to the
coding process for the coefficients, a run value that
indicates a number of successive zero coefficients whose
values are zero, and a level value that indicates a value
of a non-zero coefficient following the zero coefficients
are transformed into a code respectively, in the code table
selection step, at least one of a first selection process

CA 02607755 2007-11-13
for selecting a code table from plural code tables that
indicate correspondences between the run value and the code
in accordance with information about a run value
corresponding to the coded, and a second selection process
5 for selecting a code table from plural code tables that
indicate correspondences between the level value and the
code in accordance with information about a level value
corresponding to the coded coefficients is carried out,
and in the code assignment step, a code is assigned to at
10 least one of a run value and a level value corresponding
to an uncoded coefficient, on the basis of the selected
code table. Therefore, the assignment of codes to at least
one of run values and level values can be performed always
by using a code table that is adapted to the number of
15 uncoded coefficients and maximizes the coding efficiency.
According to the present invention, in the above-
mentioned variable length coding method, in the code table
selection step, a code table is selected from plural code
tables that indicate correspondences between the runvalue
20 and the code according to a number of coded run values which
have been coded, and in the code assignment step, a code
is assigned to an uncoded run value which has not been coded
yet, on the basis of the selected code table. Therefore,
the assignment of codes to run values can be performed
25 always by using a code table that is adapted to the number
of not-yet-processed run values and maximizes the coding
efficiency.
According to the present invention, in the above-
mentioned variable length coding method, according to the

CA 02607755 2007-11-13
31
coding process for the coefficients, a run-level pair
comprising a run value that indicates a number of
successive zero coefficients whose values are zero, and
a level value that indicates a value of a non-zero
coefficient following the zero coefficients is transformed
into a code, in the code table selection step, a code table
is selected from plural code tables that indicate
correspondences between the run-level pair and the code
in accordance with information about a run-level pair
corresponding to a coded coefficient which has been coded,
and in the code assignment step, a code is assigned to a
run-level pair corresponding to an uncoded coefficient
which has not yet been coded, on the basis of the selected
code table. Therefore, the assignment of codes to run-
level pairs can be performed always by using a code table
that is adapted to the number of not-yet-processed
coefficients and maximizes the coding efficiency.
According to the present invention, in the above-
mentioned variable length coding method, the coefficients
are obtained by quantizing frequency components of image
data in accordance with a quantization step corresponding
to the image data, and in the coding step, the coding process
for the coefficients is carried out such that codes are
assigned to plural coefficients that constitute the
coefficient data from high frequency component of
corresponding image data to low frequency component.
Therefore, the total number of bits corresponding to codes
which are assigned to the coefficients can be further
reduced.

CA 02607755 2007-11-13
32
According to the present invention, in the above-
mentioned variable length coding method, according to the
coding process for the coefficients, a run-level pair
comprising a run value that indicates a number of
successive zero coefficients whose values are zero and a
level value that indicates a value of a non-zero
coefficient following the zero coefficients is transformed
into a code, for each block that is composed of a
predeterminednumber of coefficients, and in the code table
selection step, a code table is selected from plural code
tables that indicate correspondences between the run-level
pair and the code according to a sum of a number of
already-processed coefficients which have been subjected
to the coding process in a target block that is an object
of the coding process, and a number of uncoded non-zero
coefficients which have not yet been coded in the target
block, and in the code assignment step, a code is assigned
to a run-level pair corresponding to an uncoded coefficient
in the target block, on the basis of the selected code table .
Therefore, a code table that does not include pairs of run
values and level values which will never occur can be
employed, thereby increasing the variable length coding
efficiency.
According to the present invention, in the above-
mentioned variable length coding method, according to the
coding process for the coefficients, a run-level pair
comprising a run value that indicates a number of
successive zero coefficients whose values are zero and a
level value that indicates a non-zero coefficient

CA 02607755 2007-11-13
33
followingthe zero coefficients is transformedintoacode,
the coding step includes a code table processing step for
regularly changing the correspondences between the
run-level pair and the code in a first code table that
indicates correspondence between the run-level pair and
the corresponding code according to combinations of the
run value and the level value which compose the run-level
pair, on the basis of the first code table, thereby to form
a second code table having different correspondences
between the run-level pair and the code from the first code
table, and in the code table selection step, one of the
first and second code tables is selected in accordance with
at least one of the information about the already-processed
coefficient and the parameter relating to the generation
of the coefficients. Therefore, one of the first and
second code tables is adaptively selected as an optimum
code table that is to be used when codes are assigned to
pairs of run values and level values, whereby redundant
information included in the target data to be processed
can be effectively deleted. Accordingly, the compression
rate for image signals or the like can be further improved,
so that this variable length coding method is highly
useful.
According to the present invention, in the above-
mentioned variable length coding method, in the first and
second code tables, shorter codes are made correspond
adaptively to respective run-level pairs having smaller
level values that compose the run-level pairs, and in the
second code table, level values of run-level pairs to which

CA 02607755 2007-11-13
34
shorter codes are made correspond are small on average as
compared to the first code table. Therefore, this variable
length coding method is useful when the quantization
parameter for coefficients that constitute the target data
to be processed is large.
According to the present invention, in the above-
mentioned variable length coding method, in the first and
second code tables, shorter codes are made correspond
adaptively to respective run-level pairs having smaller
run values that compose the run-level pairs, and in the
second code table, run values of run-level pairs to which
shorter codes are made correspond are small on average as
compared to the first code table. Therefore, this variable
length coding method is useful when the quantization
parameter for the coefficients that constitute the target
data to be processed is small.
According to the present invention, in the above-
mentioned variable length coding method, according to the
coding process for the coefficients, the transformation
of run-level pairs into codes is carried out for each block
that is composed of apredetermined numberof coefficients,
and in the code table processing step, the second code table
is formed according to a number of already-processed
coefficients which have been subjected to the coding
process in a target block that is an object of the coding
process. Therefore, a code table that does not include
pairs comprising run values and level values which will
never occur can be employed as the second code table,
thereby further increasing the variable length coding

CA 02607755 2007-11-13
efficiency.
According to the present invention, in the above-
mentioned variable length coding method, in the code
assignmentstep, the assignment of codes to run-level pairs
5 is carried out from a run-level pair corresponding to a
coefficient having a highest frequency component of image
data, from high frequency component to low frequency
component. Therefore, the increase in the variable length
coding efficiency, obtained by using the code table that
10 does not include pairs comprising run values and level
values which will never occur as the second code table,
can be made larger.
According to the present invention, in the above-
mentioned variable length coding method, the second code
15 table is formed by changing only correspondences which can
be regularly operated, among the correspondences between
the run-level pair and the code included in the first code
table. Therefore, an arithmetic operation that is
required for the formation of the second code table can
20 be reduced.
According to the present invention, in the above-
mentioned variable length coding method, the coefficients
constituting the coefficient data are obtained by
quantizing frequency components of image data, in
25 accordance with a quantization step corresponding to the
image data, and the code table selection step is a code
table switching step for switching between the first code
table and the second code table according to a value of
the quantization step. Therefore, a code table that is

CA 02607755 2007-11-13
36
adapted to the quantization step can be employed as the
code table to be used in a variable length coding process
for the coefficients that constitute the target data to
be processed.
According to the present invention, in the above-
mentioned variable length coding method, the code table
selection step is a code table switching step for switching
between the first code table and the second code table in
accordance with a switch instruction signal, and in the
coding step, coding of the switch instruction signal is
carried out. Therefore, the code table to be used in the
variable length coding process for the coefficients can
be changed according to characteristics of the target data
or the like.
According to the present invention, in the above-
mentioned variable length coding method, according to the
coding process for the coefficients, the transformation
of run-level pairs into codes is carried out for each block
that is composed of apredetermined number of coefficients,
and in the code table processing step, the second code table
is formed on the basis of a sum of a number of
already-processed coefficients which have been subjected
to the coding process in a target block that is an object
of the coding process, and a number of uncoded non-zero
coefficients which have not been coded yet in the target
block. Therefore, a code table that does not include pairs
of run values and level values which will never occur can
be used as the second code table, thereby further
increasing the variable length coding efficiency.

CA 02607755 2007-11-13
37
According to the present invention, there is provided
a variable length coding apparatus that encodes
coefficient data that is composed of plural coefficients
including: a coding unit for subjecting the respective
coefficients to a coding process of transforming the
coefficient data into coded data which is composed of
plural codes, by using plural code tables indicating
correspondences between the values of the coefficients and
codes, and this coding unit includes: a code table
selection unit for selecting the code table in accordance
with at least one of information about a coded coefficient
which has been coded, and a parameter relating to encoding
process of the coefficients; and a code assignment unit
for assigning a code to an uncoded coefficient which has
not yet been coded, using the selected code table.
Therefore, redundant information included in coefficient
data which are to be subjected to the variable length coding
process is effectively deleted by selection of a code table
according to characteristics of coefficients that
constitute the coefficient data or states of the coding
process for the coefficients, thereby greatly increasing
the coding efficiency in the variable length coding process
for image signals or the like.
According to the present invention, in the above-
mentioned variable length coding apparatus, the
coefficients are obtained by quantizing frequency
components of image data in accordance with a quantization
step corresponding to the image data, and the code table
selection unit selects the code table that is to be used

CA 02607755 2007-11-13
38
by the code assignment unit, according to a value of the
quantization step. Therefore, a code table that is adapted
to the value of the quantization step and maximizes the
coding efficiency can be always used.
According to the present invention, in the above-
rnentioned variable length coding apparatus, the code table
selection unit selects the code table that is to be used
by the code assignment unit, in accordance with the
information about the coded coefficient. Therefore, the
coding process for quantized coefficients can be carried
out always by using a code table is adapted to the number
of not-yet-processed coefficients andmaximizes the coding
efficiency.
According to the present invention, in the above-
mentioned variable length coding apparatus, according to
the coding process for the coefficients, a run value that
indicates a number of successive zero coefficients whose
values are zero, and a level value that indicates a value
of a non-zero coefficient following the zero coefficients
are each transformed into a code, the code table selection
unit selects a code table from plural code tables that
indicate correspondences between the run value and the code,
according to a number of coded run values to which codes
have been assigned, and the code assignment unit assigns
a code to an uncoded run value which has not been coded
yet, on the basis of the selected code table. Therefore,
the assignment of codes to run values can be performed
always by using a code table that is adapted to the number
of not-yet-processed run values and maximizes the coding

CA 02607755 2007-11-13
39
efficiency.
According to the present invention, in the above-
mentioned variable length coding apparatus, the
coefficients are obtained by quantizing frequency
components of image data, in accordance with a quantization
step corresponding to the image data, and the coding unit
carries out the coding process for the coefficients such
that codes are assigned to the plural coefficients that
constitutes the coefficient data from high frequency
component to low frequency component. Therefore, the
total number of bits corresponding to codes that are
assigned to the coefficients can be further reduced.
According to the present invention, there is provided
a storage medium that contains a program for executing a
variable length coding process for coding coefficient data
that is composed of plural coefficients, by a computer,
and this program includes: a coding step for subjecting
the respective coefficients to a coding process of
transforming the coefficient data into coded data which
is composed of plural codes, by using plural code tables
indicating correspondences between the values of the
coefficients and codes, and further this coding step
includes: a code table selection step for selecting the
code table in accordance with at least one of information
about a coded coefficient which has been coded, and a
parameter relating to encoding process of the
coefficients; and a code assignment step for assigning a
code to an uncoded coefficient which has not yet been coded,
using the selected code table. Therefore, a variable

CA 02607755 2007-11-13
length coding process having a higher coding efficiency,
which can effectively delete redundant information
included in coefficient data as an object to be subjected
to the variable length coding process by selection of a
5 code table according to characteristics of coefficients
constituting the coefficient data or states of the coding
process for the coefficients, can be implemented by
software.
According to the present invention, there is provided
10 a variable length decoding method for decoding coded data
that is composed of plural codes, obtained by performing
variable length coding to coefficient data that is composed
of plural coefficients, including: a decoding step for
subjecting the respective codes to a decoding process of
15 decoding the coded data to reconstitute the coefficient
data which is composed of the plural coefficients, using
plural code tables indicating correspondences between the
values of the coefficients and the codes, and this decoding
step includes : a code table selection step for selecting
20 the code table in accordance with at least one of
information about a decoded coefficient which has been
decoded and a parameter relating to decoding process; and
a value detection step for detecting the value
corresponding to an undecoded code which has not yet been
25 decoded, by using the selected code table. Therefore, a
variable length decoding process corresponding to a
variable length coding process having a higher coding
efficiency, which can effectively delete redundant
information included in coefficient data by changing a code

CA 02607755 2007-11-13
41
table, to encode the coefficient data can be carried out.
According to the present invention, in the above-
mentioned variable length decoding process, the
coefficients are obtained by quantizing frequency
components of image data in accordance with a quantization
step corresponding to the image data, and in the code table
selection step, the code table that is used in the value
detection step is selected according to a value of the
quantization step. Therefore, a variable length decoding
process corresponding to a variable length coding process
that always employs a code table which is adapted to the
value of the quantization step and maximizes the coding
efficiency can be carried out.
According to the present invention, in the above-
mentioned variable length decoding process, in the
decoding process for the codes, a code is decoded to
reconstitute to a run value that indicates a number of
successive zero coefficients whose values are zero, and
a level value that indicates a value of a non-zero
coefficient following the zero coefficients, in the code
table selection step, at least one of a first selection
process for selecting a code table from plural code table
that indicate correspondences between the run value and
the code, according to the value of the quantization step,
and a second selection process for selecting a code table
from plural code tables that indicate correspondences
between the level value and the code according to the value
of the quantization step is carried out, and in the
numerical value detection step, at least one of a run value

CA 02607755 2007-11-13
42
and a level value corresponding to an undecoded which has
not yet been decoded is detected, on the basis of the
selected code table. Therefore, a variable length
decoding process corresponding to a variable length coding
process that performs the assignment of codes to at least
one of run values and level values always by using a code
table that is adapted to the value of-the quantization step
and minimizes the total number of bits corresponding to
the assigned codes can be carried out.
According to the present invention, in the above-
mentioned variable length decoding process, according to
the decoding process for codes, a code is decoded to
reconstitute a run-level pair comprising a run value that
indicates a number of successive zero coefficients whose
values are zero, and a level value that indicates a value
of a non-zero coefficient following the zero coefficients,
in the code table selection step, a code table is selected
from plural code tables that indicate correspondences
between the run-level pair and the code according to the
value of the quantization step, and in the numerical value
detection step, a run-level pair corresponding to an
undecoded code which has undecoded is detected on the basis
of the selected code table. Therefore, a variable length
decoding process corresponding to a variable length coding
process that performs the assignment of codes to run-level
pairs always by using a code table that is adapted to the
value of the quantization step and minimizes the total
number of bits corresponding to the assigned codes can be
carried out.

CA 02607755 2007-11-13
43
According to the present invention, in the above-
mentioned variable length decoding process, in the code
table selection step, the code table that is used in the
numerical value detection step is selected in accordance
with information about a decoded coefficient. Therefore,
a variable length decoding process corresponding to a
variable length coding process that encodes quantized
coefficients always by using a code table that is adapted
to the number of not-yet-processed coefficients and
maximizes the coding efficiency can be carried out.
According to the present invention, in the above-
mentioned variable length decoding method, according to
the decoding process for the codes, the code is decoded
to reconstitute a run value that indicates a number of
successive zero coefficients whose values are zero, and
a level value that indicates a value of a non-zero
coefficient followingthe zero coefficients, respectively,
in the code table selection step, at least one of a first
selection process for selecting a code table from plural
code tables that indicate correspondences between the run
value and the code in accordance with information about
an decoded run value, and a second selection process for
selecting a code table from plural code tables that
indicate correspondences between the level value and the
code in accordance with information about an decoded level
value is carried out, and in the value detection step, at
least one of a run value and a level value corresponding
to an undecoded code is detected on the basis of the selected
code table. Therefore, avariable length decodingprocess

CA 02607755 2007-11-13
44
corresponding to a variable length coding process that
performs the assignment of codes to at least one of run
values and level values always by using a code table that
is adaptedto the number of not-yet-processed coefficients
and maximizes the coding efficiency can be carried out.
According to the present invention, in the above-
mentioned variable length decoding method, in the code
table selection step, a code table is selected from plural
code tables that indicate correspondences between the run
value and the code according to a number of decoded run
values which have been already decoded, and in the value
detection step, a run value corresponding to an undecoded
code which has not yet been decoded is detected on the basis
of the selected code table. Therefore, a variable length
decoding process corresponding to a variable length coding
process that performs the assignment of codes to run values
always by using a code table that is adapted to the number
of not-yet-processed run values and maximizes the coding
efficiency can be carried out.
According to the present invention, in the above-
mentioned variable length decoding method, according to
the decoding process for codes, a code is decoded to
reconstitute a run-level pair comprising a run value that
indicates a number of successive zero coefficients whose
values are zero, and a level value that indicates a number
of non-zero coefficient following the zero coefficients,
in the code table selection step, a code table is selected
from plural code tables that indicate correspondences
between the run-level pair and the code in accordance with

CA 02607755 2007-11-13
information about a run-level pair that has been obtained
by the decoding process, and in the numerical value
detection step, a run-level pair corresponding to an
undecoded code which has not been decoded yet is detected
5 on the basis of the selected code table. Therefore, a
variable length decoding process corresponding to a
variable length coding process that performs the
assignment of codes to run-level pairs always by using a
code table that is adapted to the number of not-yet-
10 processed coefficients andmaximizes thecodingefficiency
can be carried out.
According to the present invention, in the above-
mentioned variable length decoding method, the
coefficients are obtained by quantizing frequency
15 components of image data in accordance with a quantization
step corresponding to the image data, and in the decoding
step, the decoding process for codes is carried out such
that values corresponding to the codes are obtained from
high frequency component to low frequency component.
20 Therefore, a variable length decoding process
corresponding to a variable length coding process that can
further reduce the total number of bits corresponding to
codes which are assigned to the coefficients can be carried
out.
25 According to the present invention, in the above-
mentioned variable length decoding method, according to
the decoding process for the codes, a code is decoded to
reconstitute a run-level pair comprising a run value that
indicates a number of successive zero coefficients whose

CA 02607755 2007-11-13
46
values are zero, and a level value that indicates a value
of a non-zero coefficient following the zero coefficients,
for each block that is composed of a predetermined
coefficients comprising the coefficient data, in the code
table selection step, a code table is selected from plural
code tables that indicate correspondences between the
run-level pair and the code accordirig to a sum of a number
of already-processed coefficients in a target block that
is an object of the decoding process, which have been
obtained by the decoding process for the target block, and
a number of undecoded non-zero coefficient in the target
block, which have not yet been obtained by the decoding
process for the target block, and in the numerical value
detection step, a run-level pair corresponding to an
undecoded coefficient in the target block is detected on
the basis of the selected code table. Therefore, a
variable length decoding process corresponding to a
variable length coding process that has a higherefficiency
can be implemented by using a code table which does not
include pairs comprising run values and level values which
will never occur.
According to the present invention, in the above-
mentioned variable length decoding method, according to
the decoding process for the codes, a code that constitutes
the coded data is decoded to reconstitute a run-level pair
comprising a run value that indicates a number of
successive zero coefficients whose values are zero, and
a level value that indicates a value of a non-zero
coefficient following the zero coefficients, the decoding

CA 02607755 2007-11-13
47
step includes a code table processing step for regularly
changing correspondences between the run-level pair and
the code in a first code table that indicates
correspondence between the run-level pair and the
correspondingcode according to combinations of arunvalue
and a level value which compose the run-level pair, on the
basis of the first code table, thereby to form a second
code table having different correspondences between the
run-level pair and the code from the first code table, and
in the code table selection step, one of the first and second
code tables is selected in accordance with at least one
of the information about the already-processed coefficient
and the parameter relating to the generation of the
coefficients. Therefore, one of the first and second code
tables is adaptively selected as an optimum code table that
is to be used when codes are transformed into pairs of run
values and level values. Accordingly, a variable length
decoding process corresponding to a variable length coding
process that effectively delete redundant information
included in target data to be processed is satisfactorily
carried out, so that this variable length decoding method
is highly useful.
According to the present invention, in the above-
mentioned variable length decoding method, in the first
and second code tables, shorter codes are made adaptively
correspond to respective run-level pairs having smaller
level values that compose the run-level pairs, and in the
second code table, level values of run-level pairs to which
shorter codes are made correspond are small on average as

CA 02607755 2007-11-13
48
compared to the first code table. Therefore, this variable
length decoding method is effective in cases where a
quantization parameter relating to coefficients that
constitute the target data to be processed is large.
According to the present invention, in the above-
mentioned variable length decoding method, in the first
and second code tables, shorter codes are made adaptively
correspond to respective run-level pairs having smaller
run values that compose the run-level pairs, and in the
second code table, run values of run-level pairs to which
shorter codes are made correspond are small on average as
compared to the first code table. Therefore, this variable
length decoding method is effective in cases where the
quantization parameter relating to coefficients that
constitute the target data to be processed is small.
According to the present invention, in the above-
mentioned variable length decoding method, according to
the decoding process for the codes, the reconstitution of
a run-level pair from a code is performed for each block
that is composed of a predetermined number of coefficients
which compose the coefficient data, and in the code table
processing step, the second code table is formed according
to a number of already-processed coefficients which have
been obtained by the decoding process in a target block
that is an object of the decoding process. Therefore, a
code table that does not include pairs of run values and
level values which will never occur can be employed as the
second code table, whereby a variable length decoding
process corresponding to a variable length coding process

CA 02607755 2007-11-13
49
that has a higher efficiency can be implemented.
According to the present invention, in the above-
mentioned variable length decoding method, in the
numerical value detection step, the detection of a
run-level pair corresponding to the code is performed from
a run-level pair having a highest frequency component of
image data, from high frequency component to low frequency
component. Therefore, a code table that does not include
pairs of run values and level values which will never occur
can be employed as the second code table, whereby a variable
length decoding process corresponding to a variable length
coding process that increases the compression rate more
effectively can be implemented.
According to the present invention, in the above-
mentioned variable length decoding method, the second code
table is formed by changing only correspondences which can
be regularly operated, among correspondences between the
run-level pair and the code included in the first code table.
Therefore, an arithmetic operation that is required for
formation of the second code table can be reduced.
According to the present invention, in the above-
mentioned variable length decoding method, the
coefficients constituting the coefficient data are
obtained by quantizing frequency components of image data,
in accordance with a quantization step corresponding to
the image data, and in the code table selection step,
switching between the first code table and the second code
table is performed according to a value of the quantization
step. Therefore, a code table that is suitable for the

CA 02607755 2007-11-13
quantization step can be employed as the code table which
is to be used in the variable length decoding process for
coefficients constituting the target data to be processed.
According to the present invention, in the above-
5 mentioned variable length decoding method, the code table
selection step includes a code table switching step for
switching between the first code table and the second code
table in accordance with a switch instruction signal, and
in the decoding step, decoding of the switch instruction
10 signal is carried out. Therefore, a code table to be
employed in the variable length decoding process can be
switched according to characteristics of target data to
be processed or the like.
According to the present invention, in the above-
15 mentioned variable length decoding method, according to
the decoding process for the codes, the reconstitution of
a run-level pair from a code is performed for each block
that is composed of a predetermined number of coefficients
which compose the coefficient data, and in the code table
20 processing step, the second code table is formed according
to a sum of a number of already-processed coefficients in
a target block that is an object of the decoding process,
which have been obtained by the decoding process for the
target block, and a number of undecoded non-zero
25 coefficients in the target block, which have not yet been
obtainedbythedecodingprocessfortheblock. Therefore,
a code table that does not include pairs of run values and
level values which will never occur is employed as the
second code table, whereby a variable length decoding

CA 02607755 2007-11-13
51
process corresponding to a variable length coding process
having a much higher efficiency can be implemented.
According to the present invention, there is provided
a variable length decoding apparatus that decodes coded
data that is composed of plural codes, obtained by
performing variable length coding to coefficient data that
is composed of plural coefficients, including: a decoding
unit for subjecting the respective codes to a decoding
process for decoding the coded data to reconstitute the
coefficient data that is composed of the plural
coefficients, using plural code tables indicating
correspondences between the values of the coefficients and
codes, and this decoding unit includes: a code table
selection unit for selecting a code table from plural code
tables in accordance with at least one of information about
a decoded coefficient which has been decoded and a
parameter relating to decoding process of the
coefficients; and a value detection unit for detecting the
value corresponding to an undecoded code which has not yet
been decoded, by using the selected code table. Therefore,
a variable length decoding process corresponding to a
variable length coding process having a higher coding
efficiency, which effectively deletes redundant
information in coefficient data by changing a code table,
to encode the coefficient data can be carried out.
According to the present invention, in the above-
mentioned variable length decoding apparatus, the
coefficients are obtained by quantizing frequency
components of image data in accordance with a quantization

CA 02607755 2007-11-13
52
step corresponding to the image data, and the code table
selection unit selects the code table that is used by the
numerical value detection unit, according to a value of
the quantization step. Therefore, a variable length
decoding process corresponding to a variable length coding
process that always employs a code table which is adapted
to the value of the quantization step and maximizes the
coding efficiency can be carried out.
According to the present invention, in the above-
mentioned variable length decoding apparatus, the code
table selection unit selects the code table that is used
by the numerical value detection unit, in accordance with
information about a decoded coefficient. Therefore, a
variable length decoding process corresponding to a
variable length coding process which encodes quantized
coefficients always by using a code table that is adapted
to the number of undecoded coefficients and maximizes a
coding efficiency can be carried out.
According to the present invention, in the above-
mentioned variable length decoding apparatus, according
to the decoding process for the codes, the code is decoded
to reconstitute a run value that indicates a number of
successive zero coefficients whose values are zero, and
a level value that indicates a value of a non-zero
coefficient following the zero coefficients, respectively,
the code table selection unit selects a code table from
plural code tables that indicate correspondences between
the run value and the code, according to a number of decoded
run values, and the value detection unit detects a run value

CA 02607755 2007-11-13
53
corresponding to a decoded code, on the basis of the
selected code table. Therefore, a variable length
decoding process correspondingto a variable length coding
process which performs the assignment of codes to run
values always by using a code table that is adapted to the
number of not-yet-processed run values and maximizes the
coding efficiency can be carried out.
According to the present invention, in the above-
mentioned variable length decoding apparatus, the
coefficients are obtained by quantizing frequency
components of image data in accordance with a quantization
step corresponding to the image data, and the decoding unit
carries out the decoding process for the codes such that
the value corresponding to the codes is obtained from high
frequency component to low frequency component.
Therefore, a variable length decoding process
corresponding to a variable length coding process that can
further reduce the total number of bits corresponding to
codes assigned to the coefficients can be carried out.
According to the present invention, there is provided
a storage medium that contains a program for executing a
variable length decoding process for decoding coded data
that is composed of plural codes, obtained by performing
variable length coding to coefficient data that is composed
of plural coefficients, by a computer, and this program
includes a decoding step for subjecting the respective
codes to a decoding process of decoding the coded data to
reconstitute the coefficient data which is composed of the
plural coefficients, using plural code tables indicating

CA 02607755 2007-11-13
54
correspondences between the value of the coefficients and
codes, and further this decoding step includes: a code
table selection step for selecting the code table in
accordance with at least one of information about a decoded
coefficient which has been decoded and a parameter relating
to decoding process of the coefficients; and a value
detection step for detecting the value corresponding to
an undecoded code which has not yet been decoded, by using
the selected code table. Therefore, a variable length
decoding process corresponding to a variable length coding
process having a higher coding efficiency, which can
effectively delete redundant information included in
coefficient data by changing a code table, to encode the
coefficient data can be implemented by software.
Brief Description of the Drawings
Fig. 1 is a block diagram for explaining an image
coding apparatus 101 according to a first embodiment of
the present invention.
Fig. 2 is a block diagram illustrating a run-length
encoding unit RLE1 that constitutes the image coding
apparatus 101 according to the first embodiment.
Figs. 3(a)-3(d) are diagrams for explaining zigzag
scanning by the run-length encoding unit RLE1, and Figs.
3(e) and 3(f) are diagrams for explaining reordering of
run values and level values.
Figs. 4 are diagrams for explaining processing in a
variable length coder LVLC of the run-length encoding unit
RLE1: Fig. 4(a) is a flowchart showing a variable length

CA 02607755 2007-11-13
coding process for a level value, and Fig. 4(b) is a code
table that is used in the variable length coding process
for the level value.
Figs . 5 are diagrams for explaining processing in a
5 variable length coder RVLC of the run-length encoding unit
RLEl: Fig. 5(a) is a flowchart showing a variable length
coding process for a run value, and Fig. 5(b) is a code
table that is used in the variable length coding process
for the run value.
10 Figs. 6 are diagrams showing the total number of bits
corresponding to codes which are assigned to level values
(a quantization parameter is relatively small) by the
variable length coder LevVLC in a case where a code table
L2 is employed (Fig. 6(a) ), and in a case where a code table
15 L1 is employed (Fig. 6(b)), respectively.
Figs. 7 are diagrams showing the total number of bits
corresponding to codes which are assigned to level values
(a quantization parameter is relatively large) by the
variable length coder LevVLC in a case where the code table
20 L2 is employed (Fig. 7(a) ), and in a case where the code
table L1 is employed (Fig. 7(b)), respectively.
Figs. 8 are diagrams showing the total number of bits
corresponding to codes which are assigned to run values
by the variable length coder RVLC in a case where a specific
25 code table is employed (Fig. 8(a)), a case where change
of a code table and reordering of run values are performed
(Fig. 8(b) ), and a case where only change of a code table
is performed (Fig. 8(c)), respectively.
Fig. 9 is a block diagram for explaining an image

CA 02607755 2007-11-13
56
decoding apparatus 102 according to a second embodiment
of the present invention.
Fig. 10 is a block diagram illustrating a run-length
decoding unit RLD1 that constitutes the image decoding
apparatus 102 according to the second embodiment.
Figs . 11 are diagrams for explaining a variable length
decoding process by a variable length decoder LVLD: Fig.
11(a) is a flowchart showing a variable length decoding
process for reconstituting a level value, and Fig. 11(b)
is a code table that is employed in the variable length
decoding process.
Figs . 12 are diagrams for explaining a variable length
decoding process by a variable length decoder RVLD: Fig.
12(a) is a flowchart showing a variable length decoding
process for reconstituting a run value, and Fig. 12 (b) is
a code table that is employed in the variable length
decoding process.
Fig. 13 is a block diagram for explaining an image
coding apparatus 103 according to a third embodiment of
the present invention.
Fig. 14 is a block diagram illustrating a run-length
encoding unit RLE2 that constitutes the image coding
apparatus 103 according to the third embodiment.
Figs. 15 are diagrams showing examples T2a (Fig.
15 (a) ) and T2b (Fig. 15 (b) ) of a code table (second code
table) that is formed by the run-length encoding unit RLE2
according to the third embodiment.
Figs . 16 are diagrams showing other examples T2c (Fig.
16 (a) ), T2d (Fig. 16 (b) ), T2e (Fig. 16 (c) ) of the code table

CA 02607755 2007-11-13
57
(second code table) that is formed by the run-length
encoding unit RLE2 according to the third embodiment.
Fig. 17 is a diagram showing an example of an order
in which quantized components are coded by the run-length
encoding unit RLE2 according to the third embodiment.
Fig. 18 is a block diagram for explaining an image
decoding apparatus 104 according to a fourth embodiment
of the present invention.
Fig. 19 is a block diagram illustrating a run-length
decoding unit RLD2 that constitutes the image decoding
apparatus 104 according to the fourth embodiment.
Fig. 20 is a block diagram for explaining an image
coding apparatus 105 according to a fifth embodiment of
the present invention.
Fig. 21 is a block diagram illustrating a run-length
encoding unit RLE3 that constitutes the image coding
apparatus 105 according to the fifth embodiment.
Fig. 22 is a block diagram for explaining an image
decoding apparatus 106 according to a sixth embodiment of
the present invention.
Fig. 23 is a block diagram illustrating a run-length
decoding unit RLD3 that constitutes the image decoding
apparatus 106 according to the sixth embodiment.
Figs. 24 are diagrams showing examples Ta (Fig. 24 (a)
Tb (Fig. 24 (b) ), and Tc (Fig. 24 (c) ) of a variable-length
code table that is employed by the run-length encoding unit
RLE3 according to the fifth embodiment and the run-length
decoding unit RLD3 according to the sixth embodiment.
Figs. 25 are diagrams for explaining a data storage

CA 02607755 2007-11-13
58
medium which contains a program for implementing a variable
length coding process ora variable length decodingprocess
according to any of the above embodiments by a computer
system (Fig. 25 (a) and 25 (b) ), and the computer system (Fig.
25(c)).
Fig. 26 is a diagram for explaining an application
of an image coding method and an image decoding method
according to any of embodiments, and this figure shows a
contents supply system that implements contents
distribution services.
Fig. 27 is a diagram for explaining a portable
telephone that employs an image coding method and an image
decoding method according to any of embodiments.
Fig. 28 is a block diagram illustrating the portable
telephone as shown in Fig. 27.
Fig. 29 is a diagram showing a digital broadcasting
system that employs an image coding apparatus or an image
decoding apparatus according to any of embodiments.
Fig. 30 is a block diagram illustrating a conventional
image coding apparatus 201a.
Fig. 31 is a block diagram for explaining a coding
unit RLEOa that constitutes the conventional image coding
apparatus 201a.
Fig. 32 is a block diagram for explaining a
conventional decoding apparatus 202a corresponding to the
conventional image coding apparatus 201a.
Fig. 33 is a block diagram for explaining a decoding
unit RLDOa that constitutes the conventional image
decoding apparatus 202a.

CA 02607755 2007-11-13
59
Fig. 34 is a block diagram illustrating an image
coding apparatus 201b that performs conventional run-
length encoding.
Fig. 35 is a block diagram for explaining a run-length
encoding unit RLEOb that constitutes the conventional
image coding apparatus 201b.
Fig. 36 is a block diagram for explaining a
conventional image decoding apparatus 202b corresponding
to the conventional image coding apparatus 201b.
Fig. 37 is a block diagram for explaining a run-length
decoding unit RLDOb that constitutes the conventional
image decoding apparatus 202b.
Fig. 38 is a block diagram for explaining another
image coding apparatus 201c that performs the conventional
run-length encoding.
Fig. 39 is a block diagram illustrating a run-length
encoding unit RLEOc that constitutes the conventional
image coding apparatus 201c.
Fig. 40 is a block diagram for explaining a
conventional image decoding apparatus 202c corresponding
to the conventional image coding apparatus 201c.
Fig. 41 is a block diagram for explaining a run-length
decoding unit RLDOc that constitutes the conventional
image decoding apparatus 202c.
Fig. 42 is a diagram showing an example of a code table
that is employed by the run-length encoding unit RLEOc that
constitutes the conventional image coding apparatus 201c.
Fig. 43 is a diagram showing an example of an order
in which quantized components are coded by the conventional

CA 02607755 2007-11-13
run-length encoding units RLEOa, RLEOb, or RLEOc.
Best Mode for Carrying out the Invention
Initially, fundamental principles of the present
5 invention will be described.
Generally, when the quantization step is rough,
quantized components have smaller absolute values. Then,
the run (the length of successively continuing zero
coefficients) gets longer, and accordingly the levelvalue
10 (the value of a non-zero coefficient) has a smaller
absolute value. On the contrary, when the quantization
step is fine, the quantized components have larger absolute
values. Therefore, the run gets shorter and accordingly
the level value has a larger absolute value.
15 Further, when variable length coding of many
quantized components has been already completed in an
object block to be processed and the number of quantized
components which are uncoded is small, a run value that
exceeds the number of uncoded quantized components never
20 occurs. Thus, when pairs of these run values and level
values are removed, the coding efficiency is increased.
From this point of view, the present invention changes
a code table indicating correspondences between numerical
value information that shows the size of a quantized
25 coefficient and a code, according to a state of a variable
length coding process or a variable length decoding process
for quantized coefficients and aparameter associated with
generation of quantized coefficients (quantization
parameter), thereby effectively removing redundant

CA 02607755 2007-11-13
61
information included in target data (quantized
coefficient) of the variable length coding process.
For example, the change of the code table is carried
out by selecting either a code table (first code table)
that is employed in the conventional variable length coding
or decoding process, or a second code table that is formed
on the basis of the first code table and optimized for the
data to be processed, on the basis of a processing state
of quantized coefficients. It is unnecessary to form the
second code table always on the basis of the first code
table, but any code table that is adapted for processing
target data may be selected as a code table.
Hereinafter, embodiments of the present invention
will be described with reference to Figs. 1 to 25.
[Embodiment 1]
Fig. 1 is a block diagram for explaining an image
coding apparatus according to a first embodiment of the
present invention.
This image coding apparatus 101 according to the first
embodiment has, in place of the run-length encoding unit
RLEOb in the conventional image coding apparatus 201b shown
in Fig. 34 which subjects an output (quantized components)
QS from the quantization unit Q to a variable length coding
process and outputs a coded stream StrOb, a run-length
encoding unit RLE1 for subjecting the output QS from the
quantization unit Q to a variable length coding process
on the basis of a quantization parameter QP and a VLC
selection signal VlcSel, and outputs a coded stream Strl.
Here, the quantization parameter QP is a parameter

CA 02607755 2007-11-13
62
that indicates a value of a quantization step, and the
quantization step is approximately proportional to the
quantization parameter QP. To be more specific, when the
quantization parameter QP is larger, quantized components
have smaller absolute values, then zero run of the
quantized components (the length of successively
continuing components whose values are zero) gets longer,
and a level value has a smaller absolute value.
Fig. 2 is a block diagram for explaining a specific
construction of the run-length encoding unit RLE1.
This run-length encoding unit RLE1 has, like the
conventional run-length encoding unit RLEOb shown in Fig.
35, a zigzag scanner Scan for transforming an output from
the quantization unit Q (quantized components) QS in a
two-dimensional array, into quantized coefficients Coef
in a one-dimensional array (i.e., a predetermined order);
a run calculator RunCal for calculating the number of
successive quantized components whose values are zero
(zero coefficients) Coef and outputting a run value Run
that indicates the number of successive zero coefficients;
and a level calculator LevCal for calculating a value of
a quantized component whose value is not zero (non-zero
coefficient) Coef, following the zero coefficients, and
outputting a level value Lev that indicates the value of
the non-zero coefficient.
Fig. 3(a) shows a two-dimensional array of quantized
components Q1 to Q16 corresponding to one block, and Fig.
3(b) shows a scanning course of the quantized components
Ql to Q16 in the zigzag scanner Scan by arrows Al to A15.

CA 02607755 2007-11-13
63
Here, a quantized component Q1 is obtained by quantizing
DC components of frequency components corresponding to an
image signal, and quantized components Q2 to Q16 are
obtained by quantizing AC components of the frequency
components corresponding to the image signal. Fig. 3(c)
shows a one-dimensional array (coding order) of the
quantized components Qi to Q16, which is obtained by the
zigzag scanning in the zigzag scanner Scan, and Fig. 3(d)
shows a one-dimensional array of concrete numerical values
which indicate the values of the quantized components Ql
to Q16.
The run-length encoding unit RLE1 further includes
an reordering unit Lreodr for reordering level values Lev
which are outputs from the level calculator LevCal; an
reordering unit Rreodr for reordering run values Run which
are outputs from the run calculator RunCal; and a number
calculator NumClc for calculating the number Cnum of
uncoded coefficients in a target block on the basis of the
outputs from the run calculator RunCal and outputting the
calculated number. Fig. 3(e) shows orders of run values
and level values which are obtained from the numerical
values of the quantized components having the arrangements
as shown in Figs. 3(c) and 3(d). Fig. 3(f) shows orders
of the run values and the level values after the reordering.
The run-length encoding unit RLE1 further includes
a variable length coder LVLC for subjecting an output ROLev
from the reordering unit Lreodr to a variable length coding
process on the basis of the quantization parameter QP and
a selection signal V1Se1, and outputting a code string

CA 02607755 2007-11-13
64
(level value code string) LStr; a variable length coder
RVLC for subjecting an output RORun from the reordering
unit Rreodr to a variable length coding process on the basis
of the number Cnum of the uncoded coefficients, and
outputting a code string (run value code string) RStr; and
a multiplexer MUX for multiplexing the code string LStr
and the code string RStr for each block and outputting a
multiplexed coded stream Stri.
Figs. 4 are diagrams for explaining the variable
length coding process by the variable length coder LVLC.
Fig. 4(a) is a flowchart explaining the variable length
coding process for a level value, and Fig. 4(b) is an
explanatory diagram showing code tables which are employed
in the variable length coding process for the level value.
Fig. 4(b) shows an arrangement Alev of level values
(Level) , an arrangement Cal of codes (code words) in a case
where the quantization parameter QP is smaller than a
threshold, and an arrangement Ca2 of codes (code words)
in a case where the quantization parameter QP is equal to
or larger than the threshold.
Here, a code table Ll is constituted by the
arrangement Alev of the level values (Level) and the
arrangement Cal of the codes (code words) in the case where
the quantization parameter QP is smaller than the threshold.
This code table L1 shows correspondence between the level
value (Level) and the code in the case where the
quantization parameter QP is smaller than the threshold.
A code table L2 is constituted by the arrangement Alev of
the level values (Level) and the arrangement Ca2 of the

CA 02607755 2007-11-13
codes (code words) in the case where the quantization
parameter QP is equal to or larger than the threshold. This
code table L2 shows correspondence between the level value
(Level) and the code in the case where the quantization
5 parameter QP is equal to or larger than the threshold.
Figs . 5 are diagram for explaining the variable length
coding process by the variable length coder RVLC. Fig.
5 (a) is a flowchart for explaining a variable length coding
process for a run value, and Fig. 5(b) is an explanatory
10 diagram showing code tables which are employed in the
variable length coding process for the run value.
Fig. 5(b) shows an arrangement Arun of run values
(Run) , an arrangement Cbl of codes (code words) in a case
where the number of uncoded zero coefficient is one, an
15 arrangement Cb2 of codes (code words) in a case where the
number of uncoded zero coefficients is two, an arrangement
Cb3 of codes (code words) in a case where the number of
uncoded zero coefficients is three, an arrangement Cb4 of
codes (code words) in a case where the number of uncoded
20 zero coefficients is four, an arrangement Cb5 of codes
(code words) in a case where the number of uncoded zero
coefficients is five, an arrangement Cb6 of codes (code
words) in a case where the number of uncoded zero
coefficients is six, an arrangement Cb7 of codes (code
25 words) in a case where the number of uncoded zero
coefficients is seven, and an arrangement Cb8 of codes
(code words) in a case where the number of uncoded zero
coefficients is eight or more.
Here, a code table R1 is constituted by the

CA 02607755 2007-11-13
66
arrangement Arun of the run values (Run) and the
arrangement Cbl of codes (code words) in the case where
the number of uncoded zero coefficients is one, and this
code table R1 shows correspondences between the run value
(Run) and the code in the case where the number of uncoded
zero coefficients is one. Similarly, code tables R2, R3,
R4, R5, R6, and R7 are constituted by the arrangement Arun
of the run values (Run), and the arrangements Cb2, Cb3,
Cb4, CbS, Cb6, and Cb7 of codes (code words) in the cases
where the numbers of uncoded zero coefficients are two,
three, four, five, six, and seven, respectively, and show
correspondence between the run value (Run) and the code
in the cases where the numbers of uncoded zero coefficients
are two, three, four, five, six, and seven, respectively.
Further, a code table R8 is constituted by the arrangement
Arun of the run values (Run), and the arrangement Cb8 of
codes (code words) in the case where the number of uncoded
zero coefficients is eight or more, and shows
correspondence between the run value (Run) and the code
in the case where the number of uncoded zero coefficients
is eight or more.
Next, its operation will be described.
In the image coding apparatus 101 according to the
first embodiment, the blocking unit Blk, the frequency
transformation unit Trans, and the quantization unit Q
operate in the same manners as those in the conventional
image coding apparatus 201a (see Fig. 30) or image coding
apparatus 201b (see Fig. 34).
More specifically, when an image signal Vin is

CA 02607755 2007-11-13
67
inputted to the image coding apparatus 101, the blocking
unit Bik divides the inputted image signal Vin in block
units, to generate image signals (pixel value components)
BlkS corresponding to respective blocks. The frequency
transformation unit Trans transforms the pixel value
components BlkS into frequency components TransS according
to DCT (Discrete Cosine Transformation) or Wavelet
transformation. The quantization unit Q quantizes the
frequency components TransS in a predetermined
quantization step on the basis of a quantization parameter
QP to output quantized components QS, as well as outputs
the quantization parameter QP. The run-length encoding
unit RLE1 subjects the quantized components QS to a
variable length coding process, and outputs a coded stream
Stri.
Hereinafter, the operation of the run-length
encoding unit RLE1 will be specifically described.
The zigzag scanner Scan carries out zigzag scanning
of the quantized components QS which are outputted from
the quantization unit Q (i.e., plural quantized
coefficients Q1 to Q16 in a two-dimensional array as shown
in Fig. 3(a)), to transform the quantized components QS
into quantized coefficients Coef. Here, the zigzag
scanning of the quantized components QS is carried out by
scanning the plural quantized components Qi to Q16 in a
two-dimensional array as shown in Fig. 3(a) along a course
indicated by the arrows Al to A15 in Fig. 3(b) , to transform
the array of the plural quantized coefficients Q1 to Q16
into a one-dimensional array (processing order) as shown

CA 02607755 2007-11-13
68
in Fig. 3(c). Here, Fig. 3(d) shows an arrangement of
concrete numerical values of the plural quantized
coefficients Q1 to Q16 which has been subjected to the
zigzag scanning (20, -10, 5, 0, 2, 0, 0, 0, 1, 0, 0, 0,
-1, 0, 0, 1).
The run calculator RunCal calculates the number of
successive zero coefficients on the basis of the quantized
components Coef which are outputted from the zigzagscanner
Scan, and outputs a run value Run indicating the calculated
number. Fig. 3(e) shows specific run values which are
successively outputted from the run calculator RunCal,
according to an order in which the run values are outputted:
(0, 0, 0, 1, 3, 3, 2). On the other hand, the level
calculator LevCal calculates a value of a non-zero
coefficient following the successive zero coefficients on
the basis of the quantized components Coef outputted from
the zigzag scanner Scan, and outputs a level value Lev
indicating the calculated value. Fig. 3(e) shows specific
level values which are successively outputted from the
level calculator LevCal, according to an order in which
the level values are outputted: (20, -10, 5, 2, 1, -1, 1) .
The reordering unit Rreodr reorders the run values
which have successively been outputted from the run
calculator RunCal in a reverse order to how the run values
have been outputted. Fig. 3(f) shows a changed order of
the specific run values which have been reordered by the
reordering unit Rreodr: (2, 3, 3, 1, 0, 0, 0) . The number
calculator NumClc calculates the number of uncoded
coefficients on the basis of the run values Run which are

CA 02607755 2007-11-13
69
outputted from the run calculator RunCal, and outputs the
calculated number of uncoded coefficients (hereinafter,
also referred to as uncoded coefficient number) Cnum. On
the other hand, the reordering unit Lreodr reorders the
level values which have successively been outputted from
the level calculator LevCal in a reverse order to how the
level values have been outputted. Fig. 3 (f) shows a change
order of the specific level values which have been
reordered by the reordering unit Lreodr: (1, -1, 1, 2, 5,
-10, 20).
The variable length coder RVLC subjects the run values
RORun which have been reordered as the output from the
reorderingunit Rreodr, to avariable length codingprocess
for assigning codes (code words) to the run values RORun
with using plural code tables indicating correspondences
between the run value and the code (code word) , on the basis
of the uncoded zero coefficient number Cum outputted from
the number calculator NumClc, and outputs a run value code
string RStr. On the other hand, the variable length coder
LVLC subjects the level values ROLev which have been
reordered as the output from the reordering unit Lreodr
to a variable length coding process for assigning codes
(code words) to the level values ROL, by using plural code
tables indicating correspondences between the level value
and the code (code word) on the basis the quantization
parameter QP from the quantization unit Q and a selection
signal VlcSel from the outside instructing selection of
variable length coding, and outputs a level value code
string LStr.

CA 02607755 2007-11-13
Then, the multiplexer MUX multiplexes the level value
code string Lstr and the run value code string Rstr, block
by block, and outputs a multiplexed coded stream Strl.
Here, the process for multiplexing the level value
5 code string LStr and the run value code string RStr is
carried out block by block, for example, in such manner
that the code string RStr corresponding to all run values
of a target block is followed by the code string LStr
corresponding to all level values of the target block, or
10 the code string LStr corresponding to all level values of
the target block is followed by the code string RStr
corresponding to all run values of the target block.
Hereinafter, the operation of the variable length
coder LVLC will be specifically described with reference
15 to Figs. 4.
The variable length coder LVLC obtains the
quantization parameter QP from the quantization unit Q
(step Sal), and determines whether the value of the
obtained quantization parameter QP is equal to or larger
20 than a threshold of the quantization parameter QP, which
is held in the variable length coder LVLC (step Sa2).
When a result of this determination indicates that
the value of the obtained quantization parameter QP is
smaller than the threshold of the quantization parameter
25 QP, the variable length coder LVLC selects the code table
L1 that is constituted by the arrangement Alev of level
values and the arrangement Cal of codes (code words) (see
Fig. 4(b) ) (step Sa3) , while when the value of the obtained
quantization parameter QP is equal to or larger than the

CA 02607755 2007-11-13
71
threshold of the quantization parameter QP, selecting the
code table L2 that is constituted by the arrangement Alev
of level values and the arrangement Ca2 of codes (code
words) (see Fig. 4(b)) (step Sa4).
Then, the variable length coder LVLC determines
whether there is any uncoded level value Lev in a target
block (step Sa5). When a uncoded level value Lev is
included in the target block, the variable length coder
LVLC carries out a process for coding the level value using
the selected code table, i.e., a process for assigning a
corresponding code to the level value (step Sa6), and
thereafter carries out the process of step Sa5. On the
other hand, when the result of the decision in step Sa5
indicates that there is no uncoded level value Lev in the
target block, the variable length coder LVLC finishes the
variable length coding process for the level values Lev.
Here, when the VLC selection signal VlcSel previously
designates a variable length coding process using a
specific code table, the variable length coder LVLC carries
out a variable length coding process for the level values
by using the specific code table, regardless of the value
of the quantization parameter QP.
Next, the operation of the variable length coder RVLC
will be specifically described with reference to Figs. 5.
The variable length coder RVLC determines whether
there is any uncoded non-zero coefficient in the target
block on the basis of the output (the number of uncoded
coefficients) Cnum from the number calculator NumClc (step
Sbl). When a result of the determination indicates that

CA 02607755 2007-11-13
72
there is a uncoded non-zero coefficient, the variable
length coder RVLC calculates the number of uncoded zero
coefficients in the target block on the basis of the output
Cnum from the number calculator NumClc (step Sb2).
Then, the variable length coder RVLC selects a code
table according to the calculated number of uncoded zero
coefficients (step Sb3) . To be more specific, the variable
length coder RVLC selects the code table R1 that is
constituted by the arrangement Arun of run values and the
arrangement Cbl of codes (code words) (see Fig. 5(b) ) when
the number of uncoded zero coefficients is one. Similarly,
the variable length coder RVLC selects the code table R2
when the number of uncoded zero coefficients is two, the
code table R3 when the number of the coefficients is three,
and the code table R4 when the number of the coefficients
is four. Further, the variable length coder RVLC selects
the code table R5 when the number of the uncoded zero
coefficients is five, the code table R6 when the number
of the coefficients is six, and the code table R7 when the
number of the coefficients is seven, respectively.
Further, when the number of uncoded zero coefficients is
eight or more, the variable length coder RVLC selects the
code table R8.
Next, the variable length coder RVLC carries out a
process for coding run values Run using the selected code
table, i.e., a process for assigning corresponding codes
to the run values (step Sb4), and then carries out the
determination process of step Sbl.
Here, when the result of the determination in step

CA 02607755 2007-11-13
73
Sbl indicates that there is no uncoded non-zero coefficient,
the variable length coder RVLC finishes the variable length
coding process for the run values.
Next, a specific example in which a code table is
selected on the basis of the quantization parameter in the
variable length coding of the level values as described
above, thereby to increase a coding efficiency will be
described.
Figs. 6 show the total number of bits corresponding
to codes which are assigned to level values when the
quantization parameter QP is relatively smaller, i.e.,
when outputs (level values) from the level calculator
LevCal which have been reordered and are outputted from
the reordering unit Lreodr are 1, -1, 1, 2, 5, -10, 20 as
shown in Fig. 3(f).
When the quantization parameter QP is determined to
be equal to or larger than a threshold and the code table
L2 is employed, codes (code words) are assigned to
respective level values as shown in Fig. 6(a) , and the total
number of bits corresponding to the assigned codes is 75
bits.
On the other hand, when the quantization parameter
QP is determined to be smaller than the threshold and the
code table Ll is employed, codes (code words) are assigned
to respective level values as shown in Fig. 6(b) , and the
total number of bits corresponding to the assigned codes
is 47 bits.
When the quantization parameter QP is relatively
smaller, the frequency of occurrence of quantized

CA 02607755 2007-11-13
74
components having larger values is higher. Thus, it is
effective to select the code table Ll in which shorter codes
are made correspond on average also to level values whose
absolute values are relatively larger as compared to the
code table L2 to increase the coding efficiency.
Figs. 7 show the total number of bits corresponding
to codes which are assigned to level values when the
quantization parameter QP is relatively larger, i.e., when
outputs (level values) from the level calculator LevCal
which have been reordered and are outputted from the
reordering unit Lreodr are 1, -1, 1, 1, 1, -2, 3, unlike
in the case shown in Fig. 3(f).
When it is determined that the quantization parameter
QP is equal to or larger than the threshold and the code
table L2 is employed, codes (code words) are assigned to
respective level values as shown in Fig. 7(a) , and the total
number of bits corresponding to the assigned codes is 15
bits.
On the other hand, when it is determined that the
quantization parameter QP is smaller than the threshold
and the code table Li is employed, codes (code words) are
assigned to the respective level values as shown in Fig.
7(b), and the total number of bits corresponding to the
assigned codes is 17 bits.
As described above, when the value of the quantization
parameter QP is relatively larger, the frequency of
occurrence of quantization coefficients having larger
values is lower. Thus, it is effective to select the code
table L2 in which shorter codes are made intensively

CA 02607755 2007-11-13
correspond to level values whose absolute values are
relatively smaller as compared to the code table Li, to
increase the coding efficiency.
Figs. 8 show the total number of bits corresponding
5 to codes which are assigned to run values outputted from
the run calculator RunCal when the run values are 0, 0,
0, 1, 3, 3, 2 as shown in Fig. 3(e).
When the reordering of run values as in the run-length
encoding unit RLE1 and the change of the code table is not
10 performed but the code table R8 shown in Fig. 5(b) is always
employed, codes (code words) are assigned to the respective
run values as shown in Fig. 8(a) , and the total number of
bits corresponding to the assigned code is 21 bits.
When the reordering of run values and the change of
15 the code table according to the number of uncoded zero
coefficients is performed as in the run-length encoding
unit RLE1, codes (code words) are assigned to the
respective run values as shown in Fig. 8 (b) , and the total
number of bits corresponding to the assigned codes is 13
20 bits. Here, every time a code is assigned to a run value,
the number of uncoded coefficients is reduced by a value
that is obtained by adding one to a run value that has been
coded immediately before. This is because a single or
successive zero coefficients are always followed by one
25 non-zero coefficient. In addition, the number of uncoded
zero coefficients obtained from plural reordered run
values corresponding to one block, which are outputted from
the reordering unit Rreodr, is 15. This is because a block
to be processed always has at least one non-zero

CA 02607755 2007-11-13
76
coefficient.
When the reordering of run values like in the
run-length encoding unit RLE1 is not performed but only
the change of the code table according to the number of
uncoded zero coefficients is performed, codes (code words)
are assigned to the respective run values as shown in Fig.
8(c), and the total number of bits corresponding to the
assigned codes is 20 bits.
As described above, the image coding apparatus 101
according to the first embodiment includes the run-length
encoding unit RLE1 that encodes quantized coefficients
which are obtained by quantizing frequency components of
an image signal, using a run value Run indicating the number
of successive quantized components whose values are zero
(zero coefficients) Coef and a level value Lev indicating
a value of a quantized component Coef whose value is not
zero (non-zero coefficient), following the zero
coefficients. Therefore, the quantized coefficients can
be coded at a higher coding efficiency, with its redundant
information being removed.
Further, the run-length encoding unit RLE1 according
to the first embodiment includes the variable length coder
LVLC that selects a code table according to the value of
the quantization parameter QP and carries out a variable
length coding of level values by using the selected code
table, thereby reducing the total number of bits
corresponding to codes which are assigned to the level
values. The run-length encoding unit RLE1 further
includes the reordering unit Rreodr that reorders plural

CA 02607755 2007-11-13
77
run values which are obtained from quantized coefficients
to which a predetermined processing order has been given,
from high frequency component to low frequency component;
and the variable length coder RVLC that selects a code table
according to the number of uncoded zero coefficients in
the target block, and carries out variable length coding
of the reordered run values using thfe selected code table.
Therefore, the total number of bits corresponding to codes
which are assigned to the run values is effectively reduced,
thereby increasing the coding efficiency.
In this first embodiment, the variable length coder
RVLC selects a code table according to the number of uncoded
zero coefficients in the target block (i.e., the output
Cnum from the number calculator NumClc) However, the
variable length coder RVLC may selects a code table on the
basis of not only the output Cnum from the number calculator
NumClc but also the VLC selection signal VlcSel. For
example, when a variable length coding process using a
specific code table is previously indicated by the VLC
selection signal VlcSel, the variable length coder RVLC
carries out a variable length coding process.for the run
value by using the specific code table, regardless of the
number of uncoded zero coefficients in the target block.
[Embodiment 2]
Fig. 9 is a block diagram for explaining an image
decoding apparatus according to a second embodiment of the
present invention.
This image decoding apparatus 102 according to the
second embodiment decodes, for example, the coded stream

CA 02607755 2007-11-13
78
Strl that is outputted from the image coding apparatus 101
of the first embodiment.
The image decoding apparatus 102 has, in place of the
run-length decoding unit RLDOb in the conventional image
decoding apparatus 202b shown in Fig. 36 which subjects
an inputted coded stream StrOb to a variable length
decoding process, a run-length decoding unit RLD1 that
subjects the inputted coded stream Strl to a variable
length decoding process on the basis of the quantization
parameter QP and a VLD selection signal V1dSel, to
reconstitute quantized coefficients. The construction
except for the run-length decoding unit RLD1 is the same
as that of the image decoding apparatus 202b as shown in
Fig. 36.
Fig. 10 is a block diagram for explaining a specific
construction of the run-length decoding unit RLD1.
The run-length decoding unit RLD1 has a demultiplexer
DMUX for demultiplexing the multiplexed coded stream Strl
that is outputted from the image coding apparatus 101 to
obtain a code string LStr corresponding to level values
and a code string RStr corresponding to run values, as the
conventional run-length decoding unit RLDOb as shown in
Fig. 37.
The run-length decoding unit RLD1 has a variable
length decoder LVLD for subjecting a level value code
string LStr which is obtained by demultiplexing the
multiplexed coded stream Strl to a variable length decoding
process on the basis of the quantization parameter QP and
the VLD selection signal VldSel, to reconstitute level

CA 02607755 2007-11-13
79
values ROLev; and a variable length decoder RVLD for
subjecting a run value code string RStr which is obtained
by demultiplexing the multiplexed coded stream Strl to a
variable length decoding process on the basis of the number
of undecoded coefficients to reconstitute run values
RORun.
The run-length decoding unit RLD1 further includes
an inverse reordering unit LIreodr that reorders the level
values ROLev outputted from the variable length decoder
LVLD in a reverse order to that of the reordering unit Lreodr
on the coding end to reconstitute the outputs Lev from the
level calculator on the coding end; an inverse reordering
unit RIreodr that reorders the run values RORun outputted
from the variable length decoder RVLD in a reverse order
to that of the reordering unit Rreodr on the coding end
to reconstitute the outputs Run from the run calculator
on the coding end; and a number calculator NumClc that
calculates the number Cnum of undecoded coefficients in
a target block on the basis of the outputs Run from the
inverse reordering unit RIreodr and outputs the obtained
number.
The run-length decoding unit RLD1 further includes
an inverse zigzag scanner IScan that reconstitutes decoded
quantized components DQS in a two-dimen'sional array from
decoded quantized components in a one-dimensional array,
which are represented by the level values Lev and the run
values Run.
Figs . 11 are diagrams for explaining a variable length
decoding process by the variable length decoderLVLD. Fig.

CA 02607755 2007-11-13
11(a) is a flowchart for explaining the variable length
decoding process for reconstituting level values, andFig.
11 (b) is an explanatory diagram showing a code table that
is employed in the variable length decodingprocess. Here,
5 code tables Ll and L2 which are employed in the variable
length decoding process for the level values are the same
as the code tables L1 and L2 which are employed in the coding
process for the level values in the run-length encoding
unit RLE1 according to the first embodiment.
10 Figs . 12 are diagrams for explaining a variable length
decoding process by the variable length decoderRVLD. Fig.
12(a) is a flowchart for explaining a variable length
decoding process for reconstituting run values. Fig.
12 (b) is an explanatory diagram showing code tables which
15 are employed in the variable length decoding process. Here,
code tables Rl to R8 which are employed in the variable
length decoding process for run values are the same as the
code tables R1 to RB, respectively, which are employed in
the coding process for run values in the run-length
20 encoding unit RLE1 according to the first embodiment.
Next, its operation will be described.
When a multiplexed coded stream Stri is for example
inputted to the image decoding apparatus 102 from the image
coding apparatus 101 according to the first embodiment,
25 the run-length decoding unit RLD1 subjects the coded stream
Str1 to a decoding process and outputs decoded quantized
components DQS. The operation of the run-length decoding
unit RLD1 is an inverse to that of the run-length encoding
unit RLE1.

CA 02607755 2007-11-13
81
To be more specific, in the run-length decoding unit
RLD1, the demultiplexer DMUX demultiplexes the inputted
multiplexed coded stream Strl to obtain a level value code
string LStr corresponding to level values and a run value
code string RStr corresponding to run values, and outputs
the level value code string and the run value code string
to the variable length decoder LVLD and the variable length
decoder RVLD, respectively.
The variable length decoder LVLD obtains level values
ROLev corresponding to respective codes (code words) for
the level value code string LStr obtained from the
demultiplexer DMUX, by using plural code tables which
indicate correspondences between the level value and the
code (code word), on the basis of the quantization
parameter QP from the quantization unit Q and a VLD
selection signal VldSel from the outside instructing
selection of variable length decoding, and outputs the
obtained level values to the inverse reordering unit
LIreodr. On the other hand, the variable length decoder
RVLD obtains run values ROLev corresponding to respective
codes (code words) for the run value code string RStr
obtained from the demultiplexer DMUX, by using plural code
tables which indicate correspondences between the run
value and the code (code words, on the basis of the number
Cnum of undecoded coefficients outputted from the number
calculator NumClc, and outputs the obtained run values to
the inverse reordering unit RIreodr.
The inverse reordering unit LIreodrsubject the level
values ROLev outputted from the variable length decoder

CA 02607755 2007-11-13
82
LVLD to an inverse arrangement process to the process by
the reordering unit Lreodr on the coding end, to
reconstitute the outputs Lev from the level calculator on
the coding end. On the other hand, the inverse reordering
unit Rlreodr subjects the run values RORun outputted from
the variable length decoder RVLD to an arrangement process
that is an inverse to the process of the reordering unit
Rreodr on the coding end, to reconstitute the outputs Run
from the run calculator on the coding end. Further, the
number calculator NumClc calculates the number Cnum of
undecoded coefficients in a target block on the basis of
the outputs Run from the inverse reordering unit RIreodr,
and outputs the obtained number Cnum to the variable length
decoder RVLD.
Then, the inverse zigzag scanner IScan carries out
an operation that is an inverse to that of the zigzag scanner
Scan to reconstitute decoded quantized components DQS in
a two-dimensional array from the quantized components in
a one-dimensional array, which are represented by the level
values Lev and the run values Run, and outputs the obtained
quantized components DQS to the inverse quantization unit
IQ.
Hereinafter, the operation of the variable length
decoder LVLD will be specifically described with reference
to Figs. 11.
The variable length decoder LVLD obtains the
quantization parameter QP from the quantization unit Q of
the image coding apparatus 101 (step Scl) , and determines
whether the obtained quantization parameter QP is equal

CA 02607755 2007-11-13
83
to or larger than a threshold of the quantization parameter
QP, which is held in the variable length decoder LVLD (step
Sc2) .
When the result of the determination indicates that
the obtained quantization parameter QP is smaller than the
threshold of the quantization parameter QP, the variable
length decoder LVLD selects the code table Ll (see Fig.
11 (b) ) that is constituted by the arrangement Alev of level
values and the arrangement Cal of codes (code words) (step
Sc3), and when the obtained quantization parameter QP is
equal to or larger than the threshold of the quantization
parameter QP, selects the code table L2 (see Fig. 11 (b) )
that is constituted by the arrangement Alev of level values
and the arrangement Ca2 of codes (code words) (see Fig.
11(b)) (step Sc4).
Thereafter, the variable length decoder LVLD
determined whether there is any undecoded level value Lev
in the target block (step Sc5). When undecoded level
values Lev are included in the target block, the variable
length decoder carries out a decoding process for
reconstituting level values Levby using the selected code
table, i.e., a process for obtaining level values
corresponding to codes (step Sc6), and then carries out
theabove -mentioned process of step Sc5. Ontheotherhand,
the result of the determination in step Sc5 indicates that
there is no undecoded level value Lev in the target bloc,
the variable length decoder finished the variable length
decoding process for reconstituting the level values Lev.
Here, when the LVD selection signal VldSelpreviously

CA 02607755 2007-11-13
84
designates a variable length decoding process using a
specific code table, the variable length decoder LVLD
carries out a variable length decoding process for
reconstituting level values by using the specific code
table, regardless of the value of the quantization
parameter QP.
Next, the operation of the variable length decoder
RVLD will be specifically described with referencetoFigs.
12.
The variable length decoder RVLD determines whether
there is any undecoded non-zero coefficients in a target
block on the basis of the output (the number of undecoded
coefficients) Cnum from the number calculator NumClc (step
Shc). When the result of the determination shows that
there are undecoded non-zero coefficients, the variable
length decoder calculates the number of undecoded zero
coefficients in the target block on the basis of the number
Cnum of the undecoded coefficients (step Sd2).
The variable length decoder RVLD selects a code table
according to the obtained number of undecoded zero
coefficients (step Sd3). To be more specific, when the
number of undecoded zero coefficients is one, the variable
length decoder selects the code table Ri that is
constituted by the arrangement Arun of run values and the
arrangement Cbl of codes (code words) (see Fig. 12(b)).
Similarly, the variable length decoder selects the code
table R2 when the number of undecoded zero coefficients
is two, the code table R3 when the number of undecoded zero
coefficients is three, and the code table R4 when the number

CA 02607755 2007-11-13
of undecoded zero coefficients it four. Further, the
variable length decoder selects the code table R5 when the
number of undecoded zero coefficients is five, the code
table R6 when the number of undecoded zero coefficients
5 is six, and the code table R7 when the number of undecoded
zero coefficients is seven, respectively. Further, when
the number of undecoded zero coefficients is eight or more,
the variable length decoder RVLD selects the code table
R8.
10 Next, the variable length decoder RVLD carries out
a decoding process for reconstituting run values Run by
using the selected code table, i.e., a process for
obtaining run values corresponding to respective codes
(step Sd4), and then carries out the above-mentioned
15 determination process of step Sdl.
Further, when the result of the determination in step
Sdl indicates that there is no undecoded non-zero
coefficient, the variable-length decode RVLD finishes the
variable length decoding process for reconstituting the
20 run values.
In this image decoding apparatus 102 according to the
second embodiment, the inverse quantization unit IQ, the
inverse frequency transformation unit ITrans, and the
deblocking unit DeBlk operate in the same manners as those
25 in the conventional image decoding apparatus 202a (see Fig.
32) and image decoding apparatus 202b (see Fig. 36).
To be more specific, the inverse quantization unit
IQ carries out an inverse operation of the quantization
unit Q, i.e., an operation of inversely quantizing the

CA 02607755 2007-11-13
86
decoded quantized components DQS with referring to the
quantization parameter QP, to output decoded frequency
components ITransS. The inverse frequency transformation
unit ITrans carries out an inverse operation of the
frequency transformation unit Trans, i.e., an operation
of transforming the decoded frequency components ITransS
corresponding to each block according to inverse DCT or
inverse Wavelet transformation, to reconstitute decoded
pixel value signals DB1kS corresponding to respective
blocks. Then, the deblocking unit DeBlk integrates the
decoded pixel value components DB1kS of respective blocks,
and outputs a decoded image signal Vout corresponding to
each picture (frame).
As described above, the image decoding apparatus 102
according to the second embodiment includes the run-length
decoding unit RLD1 that transforms a run code string RStr
and a level code string LStr which constitute coded data,
respectively, into a run value Run indicating the number
of successive zero coefficients Coef and a level value Lev
indicating a value of a non-zero coefficient following the
zero coefficients, to reconstitute quantized coefficients
on the basis of the run value and the level value.
Therefore, a decoding process corresponding to a variable
length coding process by which quantized coefficients can
be coded at a higher coding efficiency with its redundant
information being removed can be satisfactory carried out.
In addition, the run-length decoding unit RLD1
according to the second embodiment includes the variable
length decoder LVLD that selects a code table according

CA 02607755 2007-11-13
87
to the value of the quantization parameter QP and carries
out variable length decoding for reconstituting level
values by using the selected code table. Therefore, a
level value code string that is composed of a reduced total
number of bits corresponding to codes which are assigned
to level values can be satisfactorily decoded.
The run-length decoding unit RLD1 further includes
the variable length decoder RVLD that selects a code table
according to the number of undecoded zero coefficients in
a target block and decodes a code string corresponding to
reordered run values by using the selected code table, and
the inverse reordering unit Rlreodr that reorders the run
values which are obtained by the decoding process in a
reverse order to the reordering process for run values in
the run-length encoding unit RLD1. Therefore, the total
number of bits corresponding to codes which are assigned
to the run values can be effectively reduced, and the run
value code string comprising the run values can be
satisfactorily decoded.
In this second embodiment, the variable length
decoder RVLD selects a code table according to the number
of undecoded zero coefficients in the target block (i.e.,
the output Cnum from the number calculator NumClc), but
this variable length decoder RVLD may select the code table
on the basis of not only the output Cnum from the number
calculator NumClc but also the VLD selection signal VldSel.
For example, when a variable length decoding process using
a specific code table is previously indicated by the VLD
selection signal V1dSel, the variable length decoder RVLD

CA 02607755 2007-11-13
88
performs a variable length decoding process by using the
specific code table to reconstitute run values, regardless
of the number of undecoded zero coefficients in the target
block.
[Embodiment 3]
Fig. 13 is a block diagram for explaining an image
coding apparatus according to a third embodiment of the
present invention.
This image coding apparatus 103 according to the third
embodiment has, in place of the run-length encoding unit
RLEOc in the image coding apparatus 201c shown in Fig. 38
which subjects outputs (quantized components) QS from the
quantization unit Q to a variable length coding process
and outputs a coded stream StrOc, a run-length encoding
unit RLE2 that subjects the outputs QS from the
quantization unit Q to a variable length coding process
on the basis of a quantization parameter QP or a VLC
selection signal VlcSel and outputs a coded stream Str2.
Other components of the image coding apparatus 103 of the
third embodiment are the same as those in the conventional
image coding apparatus 201c.
To be more specific, the run-length encoding unit RLE2
has, like the conventional run-length encoding unit RLEOc,
the first code table T1 (see Fig. 42) that shows the
correspondence between the pair of a run value and a level
value (hereinafter, referred to as run-level pair) and a
corresponding code, according to combinations of the run
valuesandthelevelvalues. This run-length encoding unit
RLE2 regularly changes the correspondences between the

CA 02607755 2007-11-13
89
run-level pair and the code in the first code table, on
the basis of the first code table, to form a second code
table having different correspondences from the first code
table, and selects one of the first and second code tables
on the basis of the quantization parameter QP that is
outputted from the quantization unit Q or the VLC selection
signal VlcSel from outside, as well as assigns codes to
the run-level pairs associated with coefficients in the
target data to be processed, on the basis of the selected
code table.
Here, the quantization parameter QP is a parameter
that indicates the value of the quantization step, and the
quantization step is approximately proportional to the
quantization parameter QP. To be more specific, when the
quantization parameter QP is larger, the quantization
components have smaller absolute values, then zero run in
the quantized components (the length of successively
continuing components whose values are zero) gets longer,
and thus the level value has a smaller absolute value.
Therefore, in this case, a code table in which smaller codes
are assigned to run-level pairs comprising larger run
values and smaller level values is selected, thereby to
increase the coding efficiency. Conversely, when the
quantization parameter QP is smaller, the quantized
components have largerabsolutevalues. Therefore, a code
table in which smaller codes are assigned to run-level
pairs comprising smaller run values and larger level values
is selected, thereby increasing the coding efficiency.
Further, when the VLC selection signal V1cSel from

CA 02607755 2007-11-13
the outside of the image coding apparatus 103 is inputted,
the run-length encoding unit RLE2 selects a code table that
is employed in the coding process in accordance with the
selection signal V1cSe1. Thus, when an appropriate code
5 table is selected from outside according to image
characteristics (the value of motion of an image, the
complexity of the motion, the minuteness of a pattern, or
the like) , or when a stream that can be decoded by an image
decoding apparatus including only one code table is formed
10 on the side of the image coding apparatus 103, this image
coding apparatus 103 can be controlled by the VLC selection
signal VlcSel for always using a predetermined code table.
That is, it is also possible to carry out a variable length
coding process without changing a code table but using only
15 one code table.
Fig. 14 is a block diagram for explaining a specific
construction of the run-length encoding unit RLE2.
The run-length encoding unit RLE2 has, like the
conventional run-length encoding unit RLEOc (see Fig.39),
20 a zigzag scanner Scan for transforming outputs (quantized
components) QS in a two-dimensional array from the
quantization unit Q into quantized components Coef in a
one-dimensional array (i.e., predetermined order); a run
calculator RunCal for calculating the number of successive
25 quantized components whose values are zero (zero
coefficients) Coef and outputting a run value Run; and a
level calculator LevCal for calculating a value of a
quantized component whose value is not zero (non-zero
coefficient) Coef, following the zero coefficients, and

CA 02607755 2007-11-13
91
outputting a level value Lev.
In this third embodiment, the run-length encoding
unit RLE2 further has a run converter RunConv for carrying
out a conversion process of dividing the output (run value)
Run from the run calculator RunCal into a run value Runl
indicating an upper digit of the run value Run and a run
value Run2 indicating a lower digit of the run value Run,
on the basis of the quantization parameter QP or the VLC
selection signal VlcSel; and a level converter LevConv for
carrying out a conversion process of dividing the output
(level value) Lev from the level calculator LevCal into
a level value Levi indicating an upper digit of the level
value Lev and a level value Le2 indicating a lower digit
of the level value Lev on the basis of the quantization
parameter QP or the VLC selection signal V1cSel.
The run-length encoding unit RLE2 further includes
a run-level encoder RunLevEnc for obtaining a code number
Code corresponding to a pair of the run value Runl and the
level value Levl (hereinafter, referred to as a run-level
upper digit pair) according to a code table or arithmetic
operation; and an reordering unit ReOdr for carrying out
a process for reordering run-level upper digit pairs so
that run-level upper digit pairs for higher frequency
components, corresponding to an object block to be
processed, correspond to smaller code numbers on the basis
of correspondences between the run-level upper digit pair
and code number Code, in accordance with the quantization
parameter QP or the VLC selection signal VlcSel, and
outputting a code number ReOdrCode corresponding to a

CA 02607755 2007-11-13
92
reordered run-level upper digit pair.
The run-length encoding unit RLE2 further includes
a position calculator PosClc for calculating the number
of coded quantized components (coded coefficients) from
the run value Run and outputting the number Pos of the coded
coefficients; a code transformer CodeTrans for outputting
a code number ExtCode corresponding to a run-level pair,
indicated by a second code table, from the level value Lev2
and the run value Run2, on the basis of the correspondences
between the run-level upper digit pair and the code number
ReOdrCode; and a variable length coder VLC for assigning
a bit string (code word) to the code number ExtCode to
generate a code string Str2.
The zigzag scanner Scan, the run calculator RunCal,
the level calculator LevCal, and the variable length coder
VLC in the run-length encoding unit RLE2 are the same as
those in the conventional run-length encoding unit RLEOc
as shown in Fig. 39.
Next, functions and effects will be described.
The zigzag scanner Scan transforms the quantized
components QP in a two-dimensional array into quantized
components Coef in a one-dimensional array, i.e., to which
an order is set. The run calculator RunCal calculates the
number of successive zero components (quantized components
whose values are zero) Coef, and outputs a run value Run
indicating the obtained number. The level calculator
LevCal calculates a value of a non-zero component (a
quantized component whose value is not zero, following the
zero components) Coef, and outputs a level value Lev

CA 02607755 2007-11-13
93
indicating the value of the non-zero component.
The run converter RunConv carries out a conversion
process of dividing the run value Run into the run value
Runl indicating an upper digit of the run value Run and
the run value Run2 indicating a lower digit of the run value
Run. The level converter LevConv carries out a conversion
process of dividing the level value Lev into the level value
Lev1 indicating an upper digit of the level value Lev and
the level value Lev2 indicating a lower digit of the level
value Lev.
The run-level encoder RunLevEnc obtains a code number
Code corresponding to a pair of the level value Levl and
the run value Runi (run-level upper digit pair) according
to a code table (first code table) shown in Fig. 42 or
arithmetic operation. The reordering unit ReOdr carries
out a process of reordering the run-level upper digit pairs
in accordance with the quantization parameter QP or the
VLC selection signal VlcSel, and outputs a code number
ReOdrCode corresponding to a reordered run-level upper
digit pair. According to the process of reordering the
run-level upper digit pairs, the correspondences between
the run-level upper digit pair and the code number Code,
which are obtained by the run-level encoder RunLevEnc, are
converted into correspondences in which smaller code
numbers correspond to run-level upper digit pairs
corresponding to higher frequency components in the target
block to be processed.
The position calculator PosClc calculates the number
of coded components from the run value Run, and outputs

CA 02607755 2007-11-13
94
the number Pos of codedcoefficients. Thecodetransformer
CodeTrans outputs a code number ExtCode corresponding to
a run-level pair from the level value Lev2 and the run value
Run2, on the basis of the correspondences between the
run-level upper digit pair and the code number ReOdrCode.
At this time, the code transformer CodeTrans employs the
number Pos of coded coefficients which is outputted from
the position calculator PosClc, to obtain the number of
uncoded components.
Here, the code number ExtCode corresponding to the
run-level pair, which is outputted from the code
transformer CodeTrans, is obtained on the basis of the
second code table which have different correspondences
between the run-level pair and the code number from those
of the first code table. This second code table is formed
as follows: a code table thathas different correspondences
between a run-level pair and a code number from the first
code table is initially formed by the reordering process
by the reordering unit ReOdr, and then this code table
formed by the reordering unit ReOdr is modified by the
number transformer CodeTrans on the basis of the number
Pos of coded coefficients so as not to include
correspondences between run-level pair and code number,
corresponding to run values Run exceeding the number of
uncoded components.
The variable length coder VLC assigns a bit string
(code word) to the code number ExtCode to generate a coded
stream Str2.
Figs. 15 show examples of the second code table which

CA 02607755 2007-11-13
is formed by the run-length encoding unit RLE2 on the basis
of the first code table. Here, the first code table is the
same as the code table shown in Fig. 42, which is employed
in the conventional run-length encoding unit RLEOc. In the
5 first and second code tables, a bit string (code word) is
assigned to the code number in a one-to-one relationship,
while it is needless to say that shorter code words are
assigned to code numbers Code having smaller values.
Fig. 15(a) shows, as an example of the second code
10 table, a second code table T2a that is suitable for a case
where the quantization parameter QP is smaller.
This second code table T2a is formed as follows.
Initially, a value corresponding to 1/2 of the level
Lev is assigned as the level value Levl, and an absolute
15 value of (Levlx2-Lev) is assigned as the level value Lev2.
Here, when the level value Lev is an odd number, a
value that is obtained by dividing an even number having
an absolute value which is one larger than that of the level
value Lev, by 2 is employed as the level value Levi. To
20 be more specific, when the level value Lev is positive,
a value corresponding to 1/2 of (Lev+l) is assigned to the
level value Levi, while when the level value Lev is negative,
a value corresponding to 1/2 of (Lev-1) is assigned to the
level value Lev1.
25 Then, a code number Code corresponding to a pair of
the level value Lev1 and the run value Run is obtained from
the first code table (see Fig. 42) according to the
combinations of the level values Lev and the run value Run.
Further, the code number Code corresponding to a pair

CA 02607755 2007-11-13
96
of the level value Levl and the run value Run is converted
according to the next formula (1) when the Lev value is
positive, and according to the formula (2) when the Lev
value is negative. The second code table T2a shows
correspondences between the code number and the run-level
pair which are obtained by the above conversion.
2x (Code-Lev2) -1 . . . (1)
2x(Code-Lev2) . . . (2)
For example, when focusing attention on a run-level
pair (level=-2, run=1) in the code table (first code table)
in Fig. 42, a code number Code corresponding to this
run-level pair is converted from "10" indicated by the
first code table T1 in Fig. 42 into "12" indicated by the
second code table T2a in Fig. 15(a).
That is, since the run-level pair (Lev, Run) is (-2,
1) in this case, Levl and Lev2 are calculated as follows.
Levi = Lev =(1/2)= -1
Lev2 = ILevl =2-Levl = 1-1=2-(-2)1 = 0
Therefore, (Levi, Run) is (-1, 1) , and this run-level
pair corresponds to a code number (Code = 6) according to
the first code table (see Fig. 42).
Then, a code number corresponding to the run-level
pair (Lev, Run) = (-2, 1) is calculated by employing the
formula (2) :
2x(Code-Lev2) = 2x(6-0) = 12
The code table in Fig. 15 (a) is characterized in that
smaller code numbers (i.e., shorter code words) are
assigned to run-level pairs comprising smaller run values
and larger level values as compared to the code table (first

CA 02607755 2007-11-13
97
code table) shown in Fig. 42, and this is suitable for a
case where the quantization parameter QP is smaller.
Fig. 15(b) shows, as another example of the second
code table, a second code table T2b that is suitable for
a case where the quantization parameter QP is larger.
This second code table T2b is formed as follows.
Initially, a value corresponding to 1/2 of the run
value Run is assigned as the run value Run1, and an absolute
value of (Runlx2-Run) is assigned as the run value Run2.
Here, when the run value is an odd number, an integer part
of the value corresponding to 1/2 of (Run+1) is assigned
to the run value Runl.
Then, a code number Code corresponding to a pair of
the level value Lev and the run value Runi is obtained from
the first code table (see Fig. 42), according to
combinations of the level values Lev and the run values
Runl.
Further, the code number Code corresponding to a pair
of the level value Lev and the run value Runl is converted
on the basis of the next formula (3) when Lev value is
positive, and the formula (4) when Lev value is negative.
The second code table T2b shows correspondences between
the code number and the run-level pair which are obtained
as a result of the conversion.
2 x ( Code+Run2 ) -1 . . . ( 3 )
2 x ( Code+Run2 ) -2 . . . ( 4 )
For example, when focusing attention on a run-level
pair (level=-1, run=2) in the code table (first code table)
of Fig. 42, a code number Code corresponding to this

CA 02607755 2007-11-13
98
run-level pair is converted from "12" indicated by the
first code table Ti in Fig. 42 to "10" indicated by the
second code table T2b in Fig. 15(b).
To be more specific, since the run-level pair (Lev,
Run) in this case is (-1, 2) Runi and Run2 are calculated
as follows.
Run1 = Run =(1/2) = 1
Run2 = IRuni =2-Runi _ 11=2-21 = 0
Therefore, (Lev, Runi) is (-1, 1) , and this run-level
pair corresponds to a code number (code = 6) according to
the first code table (Fig. 42).
Then, a code number corresponding to the run-level
pair (Lev, Run) = (-1, 2) is calculated by using the formula
(4) :
2x(Code+Run2) = 2x(6-0)-2 = 10
The second code table T2b shown in Fig. 15(b) is
characterized in that smaller code numbers (i.e., shorter
code words) are assigned to run-level pairs comprising
larger run values and smaller level values as compared to
the code table (first code table) Ti shown in Fig. 42, and
this is suitable for a case where the quantizati.on
parameter QP is larger.
Figs. 16 show another examples of the second code
table that is formed on the basis of the first code table
by the run-length encoding unit RLE2. Here, the first code
table is the same as the code table Ti shown in Fig. 42,
which is employed in the conventional run-length encoding
unit RLEOc.
The number transformer CodeTrans calculates the

CA 02607755 2007-11-13
99
number of uncoded components (the number of coefficients
which has not yet been subjected to a coding process) in
a target block to be processed, on the basis of the number
Pos of coded-coefficients which is outputted from the
position calculator PosClc. Further, the second code
table which is formed from the first code table is made
include no code words corresponding to run-level pairs
including run values exceeding the number of uncoded
components. Thereby, coding at higher compression
efficiency is enabled.
Fig. 16 (a) shows a second code table T2c that is formed
when the number of uncoded components is three or more.
Fig. 16(b) shows a second code table T2d that is formed
when the number of uncoded components is two. Fig. 16(c)
shows a second code table T2e that is formed when the number
of uncoded components is one.
When correspondences between run-level pairs
including run values which will never be used and codes
are deleted from the code table as described above, a
shorter code is assigned to the run-level pair. For
example, according to the second code table T2e as shown
in Fig. 16 ( c), a run-level pair comprising a run value [ 01
and a level value [4] corresponds to a code number [7].
The run-level pair comprising the run value [0] and the
level value [4] corresponds to a code number [11] according
to the second code table T2d shown in Fig. 16(b), while
the run-level pair comprising the run value [0] and the
level value [4] corresponds to a code number having a
further larger value (not shown) according to the second

CA 02607755 2007-11-13
100
code table T2c shown in Fig. 16(a).
Fig. 17 shows an example of a coding order in the
run-length encoding unit RLE2 of the image coding apparatus
103 according to the third embodiment.
Generally, absolute values of level values
corresponding to lower frequency components are large and,
in the code table, code numbers Code having larger values
correspond to run-level pairs corresponding to the lower
frequency components. On the contrary, absolute values of
level values corresponding to higher frequency components
are small and, in the code table, code numbers having
smallervalues correspond to run-level pairs corresponding
to the higher frequency components.
As described with reference to Figs. 16, the increase
in the compression efficiency, which is obtained by
deleting code numbers (code words) corresponding to
run-level pairs that include run values exceeding the
number of uncoded components from the code table, gets
larger as the number of uncoded components is smaller, as
well as larger as the absolute value of the level value
is larger, because the ratio of decrease in the value of
the assigned code number is larger as compared to the case
where the code numbers are not yet deleted.
Thus, when quantized components having larger
absolute values of the level values and corresponding to
lower frequency components are coded later in the coding
of quantized components by the run-length encoding unit
RLE2, like in the image coding apparatus 103 according to
the third embodiment, the compression efficiency is

CA 02607755 2007-11-13
101
further increased.
To be more specific, the reordering unit ReOdr
reorders quantized components so as to be successively
arranged from a run-level pair of a quantized component
corresponding to a higher frequency component (the last
non-zero component) to a run-level pair of a quantized
component corresponding to a lower frequency component,
as shown by arrows Xl to X7 in Fig. 17, to add an EOB
indicating the last coded component in a target block after
a code word corresponding to a run-level pair of a quantized
component having the lowest frequency component, thereby
increasing the compression efficiency.
Further, in the third embodiment, the quantization
parameter QP and the VLC selection signal VlcSel are
supplied to the level converter LevConv, the run converter
RunConv, the reordering unit ReOdr, and the number
transformer CodeTrans. Therefore, a code table can be
changed according to the quantization parameter QP, or an
appropriate code table can be selected from outside
according to contents of an image (the value of a motion
of the image, the complicity of the motion, or the
minuteness of a pattern).
For example, when the code table that is employed in
the coding process is changed in accordance with the VLC
selection signal VlcSel from outside of the image coding
apparatus, the image decoding apparatus can create a stream
that is decodable by a decoding unit having only one code
table.
In this third embodiment, the image coding apparatus

CA 02607755 2007-11-13
102
103 that encodes quantized coefficients of an image signal
as a target data to be processed includes the run-length
encoding unit RLE2 that assigns variable-length codes to
the quantized coefficient using a code table, and this
run-length encoding unit RLE2 forms the second code table
that is optimized for the target data to be processed on
the basis of the first code table, and selects one of the
first and second code tables as a code table that is employed
for the assignment of variable length codes, on the basis
of the quantization parameter QP or the VLC selection
signal V1Se1. Therefore, redundant information included
in the target data can be removed effectively, thereby
further increasing the compression rate for image signals
or the like.
In this third embodiment, the run-length encoding
unit RLE2 includes various devices for increasing the
compression rate, i.e., the run converter RunConv, the
level converter LevConv, the reordering unit ReOdr, and
the number transformer CodeTrans, as shown in Fig. 14.
However, the run-length encoding unit RLE2 may include only
some of the devices for increasing the compression rate.
In this case, the run-length encoding unit RLE2 can be
easily mounted.
Further, in the third embodiment, the second code
table is obtained by modifying correspondences between the
run-level pairs and the code numbers in both parts
constituting the first code table: a part which can be
regularly generated by an arithmetic operation (regularly
build VLC) , and a part which cannot be regularly generated

CA 02607755 2007-11-13
103
(table look up VLC). However, when the first code table
has the part which can be regularly generated by an
arithmetic operation (regularly build VLC) and the part
which cannot be regularly generated (table loop up VLC),
the second code table may be formed by modifying only the
part as the part of the first code table, which can be
regularly generated by an arithmetic whose operation is
easily carried out. In this case, the mounting of the
run-length encoding unit RLE2 can be moreeasilyperformed.
According to this third embodiment, in the run-length
encoding unit that performs variable length coding of
quantized components by using run-level pairs, the
quantized components are successively subjected to
variable length coding from high frequency component to
low frequency component. However, it goes without saying
that in a run-length encoding unit that subj ects run values
and level values corresponding to quantized components in
the target block separately to the variable length coding
process like in the first embodiment, the run values and
the level values corresponding to the quantized components
in the target block may be subjected to variable length
coding, successively from high frequency component to low
frequency component.
[Embodiment 4]
Fig. 18 is a block diagram for explaining an image
decoding apparatus according to a fourth embodiment of the
present invention.
This image decoding apparatus 104 according to the
fourth embodiment has, in place of the run-length decoding

CA 02607755 2007-11-13
104
unit RLDOc in the conventional image decoding apparatus
202c as shown in Fig. 40 which subjects a coded stream StrOc
to a variable length decoding process and outputs decoded
quantized components DQS, a run-length decoding unit RLD2
that subjects a coded stream Str2 to a variable length
decoding process on the basis of the quantization parameter
QP or a variable length decoding selection signal (VLD
selection signal) VldSel and outputs decoded quantized
components DQS. Other components of the image decoding
apparatus 104 according to the fourth embodiment are the
same as those in the conventional image decoding apparatus
202c.
To be more specific, the run-length decoding unit RLD2
ha.s, like the conventional run-length decoding unit RLDOc,
a first code table Ti (see Fig. 42) which indicates the
correspondence between the pair of a run value and a level
value (hereinafter, referred to as run-level pairs) and
the corresponding code, according to combinations of the
run values and the level values. Then, the run-length
decoding unit RLD2 regularly changes the correspondences
between run-level pairs and codes in the first code table,
on the basis of the first code table, to form a second code
table having different correspondences from those of the
first code table, and selects one of the first and second
code tables in accordance with the quantization parameter
QP outputted from the quantization unit Q or the VLD
selection signal VldSel fromoutside, as well as transforms
code words (bit string) that constitute the coded stream
Str2 into pairs of run values and level values associated

CA 02607755 2007-11-13
105
with coefficients in the target data to be processed, on
the basis of the selected code table.
As described above, the quantization parameter QP is
a parameter indicating the value of the quantization step,
and the quantization step is approximately proportional
to the quantization parameter QP. To be more specific,
when the quantization parameter QP is larger, the quantized
components have smaller absolute values, then zero run of
the quantized components (the length of successively
continuing components whose values are zero) gets longer,
and thus level values have smaller absolute values. In
this case, accordingly, a code table in which smaller codes
are assigned to run-level pairs comprising larger run
values and smaller level values is selected, thereby to
further improve a coding efficiency. Conversely, when the
quantization parameter QP is smaller, the quantized
components have absolute values, and thus a code table in
which smaller codes are assigned to run-level pairs
comprising smaller run values and larger level values is
selected, thereby to increase the coding efficiency.
Fig. 19 is a block diagram illustrating a specific
construction of the run-length decoding unit RLD2.
The run-length decoding unit RLD2 has, as the
conventional run-length decoding unit RLDOc, a variable
length decoder VLD, and this decoder VLD decodes the coded
stream Str2 outputted from the image coding apparatus 103
according to the third embodiment and outputs a code number
ExtCode.
In this fourth embodiment, the run-length decoding

CA 02607755 2007-11-13
106
unit RLD2 has a number inverse transformer ICodeTrans for
carrying out a number inverse transformation process for
dividing the code number ExtCode into a code number PrmCode
corresponding to a run-level upper digit pair comprising
a level value Levl and a run value Runl, a level value Lev2,
and a run value Run2 on the basis of the quantization
parameter QP or the VLD selection signal V1dSel; and an
inverse reordering unit IReOdr for reordering plural code
numbers PrmCode corresponding to a target block to be
processed in order of increasing frequency of run-level
pair, and outputting the plural code numbers Code which
correspond to the target block and have a changed order.
The run-length decoding unit RLD2 further includes
a run-level detector RunLevDec for detecting a run-level
pair corresponding to a code number Code according to a
code table or arithmetic operation, and outputting a level
value Levi and a run value Runi constituting the run-level
pair; a run inverse converter IRunConv for reconstituting
a run value Run from the run value Runl indicating the upper
digit of the run value Run and the Run value Run2 indicating
the lower digit of the run value Run; and a level inverse
converter ILevConv for reconstituting a level value Lev
from the level value Levl indicating the upper digit of
the level value Lev and the level value Lev2 indicating
the lower digit of the level value Lev.
The run-length decoding unit RLD2 further include,
as the conventional run-length decoding unit RLDOc, an
inverse zigzag scanner IScan. This scanner IScan
transforms quantizedcomponentsinaone-dimensionalarray,

CA 02607755 2007-11-13
107
which are represented by the level values Lev and the run
values Run, into decoded quantized components DQS in a
two-dimensional array, and outputs the same.
Here, the variable length decoder VLD, the run-level
detector RunLevDec, and the inverse zigzag scanner IScan
in the run-length decoding unit RLD2 are the same as those
in the run-length decoding unit RLDOc shown in Fig. 41.
Next, functions and effects will be described.
In the run-length decoding unit RLD2, the variable
length decoder VLD carries out an inverse operation to that
of the variable length coder VLC. That is, the variable
length decoder VLD decodes the coded stream Str2 and
outputs a code number ExtCode corresponding to a code word
(bit string) that constitutes the stream. The number
inverse transformer ICodeTrans carries out an inverse
operation to that of the number transformer CodeTrans on
the basis of the quantization parameter QP or the VLD
selection signal V1dSel, to divide the code number ExtCode
into a code number PrmCode corresponding to a run-level
upper digit pair comprising the level value Levi and the
run value Runl, a level value Lev2, and -a run value Run2.
The inverse reordering unit IReOdr carries out an
inverse operation to that of the reordering unit ReOdr on
the basis of the quantization parameter QP or the VLD
selection signal V1dSel. Thereby, a process for
reordering plural code numbers PrmCode corresponding to
the target block to be processed in order of increasing
frequency of run-level pair is carried out, and plural code
numbers Code which have a changed order and correspond to

CA 02607755 2007-11-13
108
the block are outputted. The run-level detector RunLevDec
detects a run-level pair corresponding to a code number
Code according to a code table or arithmetic operation,
and outputs the level value Lev1 and the run value Runl
constituting the detected run-level pair.
The run inverse converter IRunConv carries out an
inverse operation to that of the run converter RunConv on
the basis of the quantization parameter QP or the VLD
selection signal VldSel, to reconstitute the run value Run
from the run value Run 1 indicating the upper digit of the
run value Run and the run value Run2 indicating the lower
digit of the run value Run. Further, the level inverse
converter ILevConv carries out an inverse operation to that
of the level converter LevConv on the basis of the
quantization parameter QP or the VLD selection signal
VldSel, to reconstitute the level value Lev from the level
value Levl indicating the upper digit of the level value
Lev and the level value Lev2 indicating the lower digit
of the level value Lev.
Here, in the number inverse transformer IcodeTrans,
the inverse reordering unit IReOdr, the run inverse
converter IRunConv and the level inverse converter
ILevConv, the selection of the first or second code table
is performed on the basis of the quantization parameter
QP or the VLD selection signal VldSel, and the operations
are carried out according to the selected code table.
The inverse zigzag scanner IScan carries out an
inverse operation to the operation of the zigzag scanner
Scan, to transform quantized components in a one-

CA 02607755 2007-11-13
109
dimensional array which are represented by the level values
Lev and the run values Run, into decoded quantized
components DQS in a two-dimensional array, on the basis
of the level values Lev and the run values Run.
Further, when the VLD selection signal VldSel is
inputted from outside, the run-length decoding unit RLD2
selects an appropriate code table corresponding to
contents of an image (the value of a motion of the image,
the complicity of the motion, the minuteness of a pattern)
which is indicated by the VLD selection signal V1dSel.
In this fourth embodiment, the quantization
parameter QP and the VLD selection signal V1dSel are
supplied to the number inverse transformer ICodeTrans, the
inverse reordering unit IReOdr, the run inverse converter
IRunConv, and the level inverse converter IlevConv,
respectively. Thus, a code table can be changed according
to the quantization parameter QP, or an appropriate code
table can be selected from outside of the image decoding
apparatus, according to characteristics of an image, i.e.,
the value of a motion of the image, the complexity of the
motion, the minuteness of a pattern or the like.
As described above, in this fourth embodiment, the
image decoding apparatus 104 that decodes coded data which
are obtained by variable-length-coding quantized
coefficients of an image signal includes the run-length
decoding unit RLD2 for transforming a variable length code
intoquantizedcomponentsusingacodetable. Further, the
run-length decoding unit RLD2 forms a second code table
that is optimized for the target data to be processed, on

CA 02607755 2007-11-13
110
the basis of the first code table, and selects one of the
first and second code tables as a code table that is employed
in the conversion of a variable length code into quantized
coefficients, in accordance with the quantization
parameterQPortheVLDselectionsignalVldSel. Therefore,
a decoding process corresponding to a variable length
coding process that can effectively remove redundant
information included in the target data to be processed
can be satisfactorily carried out.
In this fourth embodiment, as shown in Fig. 19, the
run-length decoding unit RLD2 has various devices for
increasing the compression rate, i.e., the number inverse
transformer ICodeTrans, the inverse reordering unit IReOdr,
the run inverse converter IRunConv, and the level inverse
converter ILevConv, while the run-length decoding unit
RLD2 may has only some of these devices for increasing the
compression rate. In this case, the run-length decoding
unit RLD2 can be mounted more easily.
Further, in the fourth embodiment, the second code
table is formed by changing the correspondences between
run-level pairs and code numbers in both parts which
constitute the first code table: the part that can be
regularly generated by an arithmetic operation (regularly
build VLC) and the part that cannot be regularly generated
(table look up VLC) . However, when the first code table
has the part that can be regularly generated by an
arithmetic operation (regularly build VLC) and the part
that cannot be regularly generated (table loop up VLC),
the second code table may be formed by changing only the

CA 02607755 2007-11-13
111
part as a part of the first code table, which can be
regularly generated by the arithmetic whose operation is
easily carried out. In this case, the mounting of the
run-length decoding unit RLD2 can be performed more easily.
According to this fourth embodiment, in the run-
length decoding unit that performs variable length
decoding of coded data corresponding to quantized
components by using run-level pairs, the variable length
decoding of the coded data corresponding to the quantized
components is performed successively from high frequency
component to low frequency component. However, it is
possible that, in a run-length decoding unit that subjects
coded data of run values and level values corresponding
to quantized components in a target block separately to
variable length decoding as in the second- embodiment, the
coded data of run values and level values corresponding
to the quantized components of the target block are
subjected to the variable length decoding, successively
from high frequency component to low frequency component.
[Embodiment 5]
Fig. 20 is a block diagram for explaining an image
coding apparatus according to a fifth embodiment of the
present invention.
This image coding apparatus 105 include, in place of
the run-length encoding unit RLE2 in the image coding
apparatus 103 according to the third embodiment as shown
in Fig. 13, a run-length encoding unit RLE3 that encodes
a run-level pair as well as encode the number of non-zero
components, like the run-length encoding unit RLE2. Other

CA 02607755 2007-11-13
112
components of the image coding apparatus 105 according to
the fifth embodiment are the same as those in the image
coding apparatus 103 according to the third embodiment.
Fig. 21 shows a specific construction of the run-
length encoding unit RLE3 in the image coding apparatus
105.
This run-length encoding unit RLE3 according to the
fifth embodiment has, in place of the position calculator
PosClc in the run-length encoding unit RLE2 according to
the third embodiment as shown in Fig.14, a non-zero
coefficient counter NZcount for counting the number NZnum
of non-zero coefficients on the basis of inputted quantized
components, and a position calculator PosClc2 for
calculating the number Pos2 of coded coefficients on the
basis of the counted number Nznum of non-zero coefficients
and a run value Run calculated by the run calculator RunCal.
The run-length encoding unit RLE3 according to the
fifth embodiment encodes an output (code number) ExtCode
from the number transformer CodeTrans as well as encodes
the number NZnum of non-zero components, unlike the
variable length coder VLC of the run-length encoding unit
RLE2 according to the third embodiment.
Other components of the run-length encoding unit RLE3
are the same as those of the run-length encoding unit RLE2
according to the third embodiment.
Next, functions and effects will be described.
Operations of the blocking unit Blk, the frequency
transformation unit Trans, and the quantization unit Q in
the image coding apparatus 105 according to the fifth

CA 02607755 2007-11-13
113
embodiment are the same as those in the image coding
apparatus 103 according to the third embodiment. Further,
operations of components other than the non-zero
coefficient counter NZcount, the position calculator
PosClc2, the number transformer CodeTrans, and the
variable length coder VLC2 in the run-length encoding unit
RLE3 according to the fifth embodiment, i. e., the scanner
Scan, the run calculator RunCal, the level calculator
LevCal, the run converter RunConv, the level converter
LevConv, the run-level encoder RunLevEnc, and the
reordering unit ReOdr are identical to those of the
run-length encoding unit RLE2 according to the third
embodiment. Thus, the operations of the non-zero
coefficient counter NZcount, the position calculator
PosClc2, the number transformer CodeTrans, and the
variable length coder VLC2 will be hereinafter mainly
described.
When quantized components QS outputted from the
quantization unit Q are inputted to the run-length encoding
unit RLE3, the non-zero coefficient counter NZcount in the
run-length encoding unit RLE3 counts the number of non-zero
components NZnum in the plural quantized components
corresponding to respective blocks on the basis of the
quantized components QS, and outputs the obtained number
NZnum of non-zero components to the position calculator
PosClc2 and the variable length coder VLC2.
The position calculator PosClc2 calculates a sum of
the number of coded zero components and the number of
non-zero components in a target block on the basis of the

CA 02607755 2007-11-13
114
number NZnum of non-zero components from the non-zero
coefficient counter NZcount and a run value Run from the
run calculator RunCal, and outputs the obtained value Pos2.
The number transformer CodeTrans outputs a code
number ExtCode corresponding to a run-level pair from a
level value Lev2 and a run value Run2, on the basis of
correspondences between the run-level upper digit pairs
and the code numbers ReOdrCode. At this time, the number
transformer CodeTrans employs the calculated value Pos2
that is outputted from the position calculator PosClc2 to
obtain the number of uncoded components in the target
block.
Here, the code number ExtCode corresponding to a
run-level pair, which is outputted from the number
transformer CodeTrans, is obtained on the basis of the
second code table having different correspondences between
run-level pairs and code numbers from the first code table.
This second table is formed as follows: a code table having
different correspondences between run-level pairs and code
numbers from the first code table is initially formed by
the reordering process in the reordering unit ReOdr, and
then the code table formed by the reordering unit ReOdr
is modified by the number transformer CodeTrans on the
basis of the calculated value Pos2 so that run-level pairs
having run values which are larger than the maximum run
value Run in the code table correspond to code numbers
ExtCode to which no codes are assigned.
The variable length coder VLC2 encodes the number
NZnum of non-zero components, as well as performs coding

CA 02607755 2007-11-13
115
for the code number ExtCode to assign a bit string (code
word) to the code number ExtCode to generate a coded stream
Str3.
Hereinafter, the operation of the variable length
coder VLC2 will be specifically described.
Unlike the variable length coder VLC according to the
third embodiment, the variable length coder VLC2 according
to the fifth embodiment not only encodes the code number
ExtCode corresponding to a run-level pair of a target block
but also encodes the number NZnum of non-zero components
in the target block before coding the code number ExtCode
of the block.
As described above, when the number NZnum of non-
zero coefficients is coded before coding the code number
ExtCode of a block, the number NZnum of non-zero components
of the target block can be initially decoded at the decoding,
and it can be checked that reconstitution of the last
run-level pair in the target block has been completed, at
a time when the run-level pairs corresponding to the number
NZnum of non-zero components have been reconstituted.
Consequently, a specific value EOB that is coded at the
end of the target block (a value that is transmitted after
the last non-zero component), which is required by the
variable length coder VLC according to the third embodiment,
is not required by the variable length coder VLC2.
Next, the operations of the position calculator
PosClc2 and the number transformer CodeTrans will be
specifically described.
Assuming that a target block includes NBlock

CA 02607755 2007-11-13
116
quantized components QS (including both of zero components
and non-zero components), the maximum run length (the
maximum number of successively continuing zero
coefficients) is (NBlock-NZnum) on the basis of the number
NZnum of non-zero coefficients in the target block.
Further, the maximum run value (the maximum number of
successively continuing zero coefficients) MaxRun(1) at
a time when the coding of the first run-level pair has been
completed is represented by the following formula (5),
using a run value FRun of the first run-level pair of the
target block.
MaxRun(l) = NBlock - NZnum - FRun ... (5)
Generally, the maximum run value MaxRun (i) at a time
when coding of an i-th run-level pair in a block has been
completed is represented by the following formula (6).
MaxRun(i) = NBlock - NZnum
- {the sum of lst-i-th run values} ...(6)
Therefore, the position calculator PosClc2 outputs
a calculated value Pos2 represented by the following
formula (7), thereby indicating to the number transformer
CodeTrans that the maximum run value MaxRun(i) is a value
represented by the formula (8).
Pos2 = NZnum + {the sum of lth-i-th run values (7)
MaxRun(i) = NBlock -Pos2 ...(8)
The number transformer CodeTrans forms the second
code table in which code numbers ExtCode to which no code
is assigned are made correspond to run-level pairs having
run values which are larger than the maximum run value
MaxRun. Thereby, redundancy in the coding process due to

CA 02607755 2007-11-13
117
the assignment of codes to run-level pairs which will never
occur is deleted, thereby increasing the compression rate.
When a variable-length code table that is composed
of a first part which can be generated by an arithmetic
operation (regularly build VLC) and a second part which
cannot be regularly generated by an arithmetic operation
(table look up VLC) is employed as the first and second
code tables when the variable length coding process for
the quantized components is carried out, the second code
table may be formed by changing both of the first and second
parts in the first code table according to the maximum run
value, or the second code table may be formed by changing
only the first part in the first code table, which can be
generated by an arithmetic whose operation is easily
performed according to the maximum run value.
Further, in place of changing the code table to one
in which no code is assigned to run-level pairs having run
values Run which are larger than the maximum run value
MaxRun(i) when the variable length code table is changed
according to the maximum run value MaxRun (i) at a time when
the coding of an i-th run-level pair has been completed,
a variable-length code table may be directly changed to
one in which no code is assigned to run-level pairs having
run values Run that are larger than the maximum run value
MaxRun ( i ) .
Figs. 24 are diagrams showing examples of the variable
length code tables. In a code table Ta (Fig. 24(a)),
shorter codes are assigned to smaller run values as
compared to a code table Tb (Fig. 24 (b) ) . In the code table

CA 02607755 2007-11-13
118
Tb (Fig. 24(b)), further shorter codes are assigned to
smaller run values as compared to a code table Tc (Fig.
24 (c) ) .
In addition, in the code table Tc (Fig. 24(c)),
shorter codes are assigned to level values having smaller
absolute values as compared to the code table Tb (Fig. 24 (b)
In the code table Tb, further shorter codes are assigned
to level values having smaller absolute values as compared
to the code table Ta (Fig. 24(a)),
Therefore, it is preferable to select the code table
Ta in Fig. 2 4( a) when the maximum run value MaxRun is smaller,
the code table Tc in Fig. 2 4( c) when the maximum run value
MaxRun is larger, and the code table Tb in Fig. 24 (b) when
the maximum run value MaxRun is an intermediate value.
According to the fifth embodiment, the image coding
apparatus 105 that encodes quantized coefficients which
are obtained by quantizing frequency components of an image
signal is provided with the run-length encoding unit RLE3
that assigns variable length codes to the quantized
components using a code table. Then, the run-length
encoding unit RLE3 selects a code table in which run-level
pairs which will never occur are deleted on the basis of
the sum of the number of processed coefficients (coded
coefficients) in a target block to be coded and the number
of uncoded non-zero coefficients in the target block, in
other words, the sum of the number of non-zero coefficients
in the target block and the number of already-processed
run values in the target block, thereby increasing the
variable length coding efficiency.

CA 02607755 2007-11-13
119
According to this fifth embodiment, in the run-length
encoding unit that performs variable length coding of
quantized components corresponding to each block by using
run-level pairs, the number NZnum of non-zero components
in a target block is coded. However, it is possible that
coding of the number NZnum of non-zero components of a
target block may be performed in a run-length encoding unit
that performs variable length coding of run values and
level values corresponding to quantized components of each
block separately, as in the first embodiment. In this case,
the maximum run value in the target block can be set at
a value that is obtained by subtracting the number NZnum
of non-zero components from the number of all components
in the target block.
[Embodiment 6]
Fig. 22 is a block diagram for explaining an image
decoding apparatus according to a sixth embodiment of the
present invention.
This image decoding apparatus 106 according to the
sixth embodiment has, in place of the run-length decoding
unit RLD2 in the image decoding apparatus 104 according
to the fourth embodiment as shown in Fig. 18, a run-length
decoding unit RLD3 that performs a decoding process for
coded data to reconstitute the number of run-level pairs
and the number of non-zero components in each block, as
in the run-length decoding unit RLD2. Other components of
the image decoding apparatus 106 according to the sixth
embodiment are the same as those in the image decoding
apparatus 104 according to the fourth embodiment.

CA 02607755 2007-11-13
120
Fig. 23 shows a specific construction of the run-
length decoding unit RLD3 in the image decoding apparatus
106.
This run-length decoding unit RLD3 of the sixth
embodiment includes, in place of the position calculator
PosClc in the run-length decoding unit RLD2 according to
the fourth embodiment as shown in Fig. 19, a position
calculator PosClc2 for calculating the sum Pos2 of the
number of decoded run values in a target block to be decoded
and the number NZnum of non-zero coefficients in the target
block.
Further, a variable length decoder VLD2 of the
run-length decoding unit RLD3 according to the sixth
embodiment is different from the variable length decoder
VLD in the run-length decoding unit RLD2 according to the
fourth embodiment in that a decoding process for
reconstituting a code number ExtCode and a decoding process
for reconstituting the coded number NZnum of non-zero
components are carried out.
Next, functions and effects will be described.
Operations of the inverse quantization unit IQ, the
inverse frequency transformation unit ITrans, and the
deblocking unit DeBlk in the image decoding apparatus 106
according to the sixth embodiment are the same as those
in the image decoding apparatus 104 of the fourth
embodiment. Further, operations of components of the
run-length decoding unit RLD3 according to the sixth
embodiment other than the variable length decoder VLD2,
the position calculator PosClc2 and the number inverse

CA 02607755 2007-11-13
121
transformer IcodeTrans, i.e., the inverse reordering unit
IReOdr, the run-level detector RunLevDec, the level
inverse converter ILevConv, the run inverse converter
IRunConv, and the inverse zigzag scanner IScan are
identical to those of the run-length decoding unit RLD2
according to the fourth embodiment. Therefore,
operations of the variable length decoder VLD2, the
position calculator PosClc2, and the number inverse
transformer ICodeTrans will be hereinafter mainly
described.
The variable length decoder VLD2 decodes the coded
stream Str3, and outputs a code number ExtCode
corresponding to a code word (bit string) that composes
the coded stream. The number inverse transformer
ICodeTrans carries out an inverse operation to that of the
number transformer CodeTranson the basis of at leasteither
the quantization parameter QP or the VLD selection signal
V1dSe1, and the sum Pos2 of the number of decoded
coefficients and the number of undecoded non-zero
coefficients, to divide the code number ExtCode into a code
number PrmCode corresponding to the run-level upper digit
pair comprising the level value Levl and the run value Runi,
a level value Lev2, and a run value Run2.
The inverse reordering unit IReOdr, the run-level
detector RunLevDec, the run inverse converter IRunConv,
the level inverse converter ILevConv, and the inverse
zigzag scanner IScan performs the same operations as those
in the fourth embodiment.
Here, the number inverse transformer ICodeTrans, the

CA 02607755 2007-11-13
122
inverse reordering unit IReOdr, the run inverse converter
IRunConv, and the level inverse converter ILevConv selects
one of the first and second code tables on the basis of
at least either the quantization parameter QP or the VLD
selection signal V1dSel, and the sum Pos2 of coefficients,
and perform the operations on the basis of the selected
code table.
Hereinafter, the operation of the variable length
decoder VLD2 will be specifically described.
The variable length decoder VLD2 according to the
sixth embodiment is different from the variable length
decoder VLD according to the fourth embodiment in that it
decodes not only the code number ExtCode corresponding to
a run-level pair but also the coded number NZnum of non-zero
components in the target block. When the number NZnum of
non-zero components is obtained by the decoding, at a time
when NZnum run-level pairs have been decoded, this NZnum-th
run-level pair is judged to be the last run-level pair.
Consequently, the variable length decoder VLD2 does not
require a value EOB that is required by the variable length
decoder VLD and is coded at the end of the target block.
For example, assuming that there are NBlock quantized
components QS in the target block, including zero
components and non-zero components, the maximum run value
(the maximum number of successively continuing zero
coefficients) is (NBlock-NZnum) on the basis of the number
NZnum of non-zero coefficients in the target block.
Further, the maximum run value (the maximum number of
successively continuing zero coefficients) MaxRun(1) at

CA 02607755 2007-11-13
123
a time when the decoding for reconstituting the first
run-level pair has been performed is (NBlock-NZnum-FRun)
as described in the fifth embodiment.
Generally, the maximum run value MaxRun ( i) at a time
when decoding for reconstituting an i-th run-level pair
in a block has been performed is obtained as follows:
MaxRun(i) = Nblock - Nznum
-{the sum of 1st-i-th run values}
Therefore, the position calculator PosClc2 outputs
the sum Pos2 of coefficients [=NZnum +{the sum of 1st-i-th
run values}], thereby indicating to the number transformer
CodeTrans that the maximum run value at a time when the
decoding for reconstituting an i-th run-level pair has been
performed is (NBlock-Pos2).
The number inverse transformer ICodeTrans employs a
code table in which no code is assigned to code numbers
corresponding to run-level pairs comprising run values
which are larger than the maximum run value Run, to obtain
a code number ExtCode corresponding to a code, thereby
decoding a code that is assigned to a code number according
to code assignment which avoids assignment of codes to
run-level pairs which will never occur.
Here, when a variable length code table that is
composed of the first part which can be generated by an
arithmetic operation (regularly build VLC) and the second
part that cannot be regularly generated (table loop up VLC)
is employed as the first and second code tables in the
variable length decoding process, the second code table
may be formed by changing both of the first and second parts

CA 02607755 2007-11-13
124
in the first code table according to the maximum run value,
while the second code table may be formed by changing only
the first part of the first code table which can be generated
by an arithmetic whose operation is easily carried out,
according to the maximum run value.
Further, when a variable length code table is changed
according to the maximum run value MaxRun at a time when
the decoding for reconstituting an i-th run-level pair has
been completed, the variable length code table can be
changed directly to the code table Ta in Fig. 24 (a), the
code table Tb in Fig. 24 (b) , or the code table Tc in Fig.
24 (c) , in place of changing the code table to one in which
no code is assigned to run-level pairs comprising run
values which are larger than the maximum run value MaxRun.
For example, it is preferable to select the code table
Ta in Fig. 2 4( a) when the maximum run value MaxRun is smaller,
the code table Tc in Fig. 24 (c) when the maximum run value
MaxRun is larger, and code table Tb in Fig. 24 (b) when the
maximum run value MaxRun is an intermediate value.
As described above, according to the sixth embodiment,
the image decoding apparatus 106 that reconstitutes
quantized coefficients which are obtained by quantizing
frequency components of an image signal by a decoding
process for coded data is provided with the run-length
decoding unit RLD3 for obtaining a quantized coefficient
corresponding to a variable length code by employing a code
table. Then, this run-length decoding unit RLD3 selects
a code table including no run-level pairs which will never
occur, on the basis of the sum of the number of processed

CA 02607755 2007-11-13
125
coefficients (decoded coefficients) in a target block and
the number of undecoded non-zero coefficients in the target
block. Therefore, a decoding process corresponding to a
variable length coding process that can more effectively
remove redundant information included in the quantized
coefficients to be processed can be satisfactorily carried
out.
According to this sixth embodiment, in the run-length
decoding unit that performs variable length decoding for
quantized components of each block by using run-level pairs,
the coded number NZnum of non-zero components in a target
block is decoded. However, it is possible that, for
example, in a run-length decoding unit that subjects run
values and level values corresponding to quantized
components of each block separately to the variable length
decoding process as in the second embodiment, the coded
number NZnum of non-zero components of the target block
is decoded. In this case, it can be judged that the
NZnum-th level value is the last level value in the target
block, at a time when NZnum level values have been decoded.
In any of the aforementioned embodiments, the code
table is changed according to the quantization parameter
QP, while the code table may be changed according to another
parameter. For example, another parameter may be newly
derived and expressly switched for each block.
In the above-mentioned embodiments, as a method for
subjecting coefficients such as quantized components to
a variable length coding (decoding) process, a method is
shown in which a VLC table is employed, and the VLC table

CA 02607755 2007-11-13
126
is changed on the basis of at least either information about
processed coefficients which have been subjected to the
coding (decoding) process, or a parameter relating to
generation of the coefficients. However, the method for
variable-length coding (decoding) coefficients such as
quantized components according to the present invention
is not restricted to one using the VLC table. For example,
the method for variable-length coding the quantized
components as described in any of the first, third, and
fifth embodiments may be a variable length coding method
in which the VLC table is not employed, and a code table
corresponding to the VLC table is changed on the basis of
at least either the information about the processed
coefficients, or the parameter relating to generation of
the coefficients. Further, the method for variable-
length decoding the coded data corresponding to the
quantized components according to any of the second, fourth,
and sixth embodiments may be a variable length decoding
method by which the VLC table is not employed, and a code
table corresponding to the VLC table is changed on the basis
of at least either the information about the processed
coefficients, or the parameter relating to generation of
the coefficients.
The image coding apparatus that carries out a variable
length coding process or the image decoding apparatus that
carries out a variable length decoding process according
to any of the aforementioned embodiments is implemented
by hardware, while these apparatuses may be implemented
by software. In this case, when a program for executing

CA 02607755 2007-11-13
127
the variable length coding or decoding process according
to any of the aforementioned embodiments is recorded in
a data storage medium such as a flexible disk, the image
coding apparatus or the image decoding apparatus according
to any of the aforementioned embodiments can be easily
implemented in an independent computer system.
Figs. 25 are diagrams for explaining a computer system
for executing the variable length coding process according
to the first, third or fifth embodiment, or the variable
length decoding process according to the second, fourth,
or sixth embodiment.
Fig. 25(a) shows a front view of a flexible disk FD
which is a medium that contains a program employed in the
computer system, a cross-sectional view thereof, and a
flexible disk body D. Fig. 25(b) shows an example of a
physical format of the flexible disk body D.
The flexible disk FD is composed of the flexible disk
body D and a case FC that contains the flexible disk body
D. On the surface of the disk body D, a plurality of tracks
Tr are formed concentrically from the outer circumference
of the disk toward the inner circumference. Each track is
divided into 16 sectors Se in the angular direction.
Therefore, in the flexible disk FD containing the
above-mentioned program, data of the program for executing
the variable length coding process or the variable length
decoding process are recorded in the assigned storage areas
(sectors) on the flexible disk body D.
Fig. 25(c) shows the structure for recording or
reproducing the program in/from the flexible disk FD. When

CA 02607755 2007-11-13
128
the program is recorded in the flexible disk FD, data of
the program are written in the flexible disk FD from the
computer system Cs through the flexible disk drive FDD.
When the above-mentioned image coding apparatus or image
decoding apparatus is constructed in the computer system
Cs by the program recorded in the flexible disk FD, the
program is read from the flexible disk FD by the flexible
disk drive FDD and then loaded to the computer system Cs.
Although in the above description a flexible disk is
employed as a storage medium that contains a program for
executing the variable length coding process or the
variable length decoding process, an optical disk may be
employed as the storage medium. Also in this case, the
variable length coding process or variable length decoding
process can be performed by software in like manner as the
case of using the flexible disk. The storage medium is not
restricted to these disks, and any medium may be employed
as long as it can contain the program, for example, a CD-ROM,
a memory card, or a ROM cassette. Also when such data
storage medium is employed, the variable length coding or
variable length decoding process can be performed by the
computer system in the same manner as the case of using
the flexible disk.
Applications of the image coding method or image
decoding method according to any of the aforementioned
embodiments and systems using the same will be described
hereinafter.
Fig. 26 is a block diagram illustrating an entire
construction of a contents provision system 1100 that

CA 02607755 2007-11-13
129
performs contents distribution services.
A communication service provision area is divided
into regions (cells) of desired size, and base stations
1107 to 1110 which are each fixed radio stations are
established in the respective cells.
In this contents provision system 1100, various
devices such as a computer 1111, a PDA (personal digital
assistant) 1112, a camera 1113, a portable telephone 1114,
and a portable telephone with a camera 1200 are connected,
for example, to the Internet 1101 through an Internet
service provider 1102, a telephone network 1104, and the
base stations 1107 to 1110.
However, the contents provision system 1100 is not
restricted to a system including all of the plural devices
shown in Fig. 26, but may be one including some of the plural
devices shown in Fig. 26. Further, the respective devices
may be connected directly to the telephone network 1104,
not through the base stations 1107 to 1110 as the fixed
radio stations.
The camera 1113 is a device that can take moving images
of an object, like a digital video camera. The portable
telephone may be a portable telephone set according to any
of PDC (Personal Digital Communications) system, CDMA
(Code Division Multiple Access) system, W-CDMA
(Wideband-Code Division Multiple Access) system, and GSM
(Global System for Mobile Communications) system, or PHS
(Personal Handyphone System).
A streaming server 1103 is connected to the camera
1113 through the base station 1109 and the telephone

CA 02607755 2007-11-13
130
network 1104. In this system, live distribution based on
coded data which are transmitted by a user using the camera
1113 can be performed. The coding process for the data of
taken images may be carried out by either the camera 1113
or the server that transmits the data. Moving image data
which are obtained by taking moving images of an object
by means of the camera 1116 may be transmitted to the
streaming server 1103 through the computer 1111. The
camera 1116 is a device that can take still images or moving
images of an object, such as a digital camera. In this case,
coding of the moving image data can be performed by either
the camera 1116 or the computer 1111. Further, the coding
process is carried out by an LSI 1117 included in the
computer 1111 or the camera 1116.
Image coding or decoding software may be stored in
a storage medium (a CD-ROM, a flexible disk, a hard disk,
or the like) which is a recording medium that contains data
readable by the computer 1111 or the like. The moving image
data may be transmitted through the portable telephone with
a camera 1200. The moving image data are data which have
been coded by an LSI included in the portable telephone
1200.
In this contents provision system 1100, contents
corresponding to images taken by the user by means of the
camera 1113 or the camera 1116 (for example, live video
of a music concert) are coded in the camera in the same
manner as any of the aforementioned embodiments, and
transmitted from the camera to the streaming server 1103.
The contents data are subjected to streaming distribution

CA 02607755 2007-11-13
131
from the streaming server 1103 to a requesting client.
The client may be any of the computer 1111, the PDA
1112, the camera 1113, the portable telephone 1114 and the
like, which can decode the coded data.
In this contents provision system 1100, the coded data
can be received and reproduced on the client side. When
the data are received, decoded, and reproduced in real time
on the client side, private broadcasting can be realized.
The coding or decoding in the respective devices that
constitute this system can be performed using the image
coding apparatus or the image decoding apparatus according
to any of the aforementioned embodiments.
A portable telephone will be now described as an
example of the image coding or decoding apparatus.
Fig. 27 is a diagram illustrating a portable telephone
1200 that employs the image coding method and the image
decoding method according to any of the aforementioned
embodiments.
This portable telephone 1200 includes an antenna 1201
for transmitting/receiving radio waves to/from the base
station 1110, a camera unit 1203 that can take video or
still images of an object, such as a CCD camera, and a
display unit 1202 such as a liquid crystal display for
displaying data of the video taken by the camera unit 1203
or video received through the antenna 1201.
The portable telephone 1200 further includes a main
body 1204 including plural control keys, a voice output
unit 1208 for outputting voices such as a speaker, a voice
input unit 1205 for inputting voices such as a microphone,

CA 02607755 2007-11-13
132
a storage medium 1207 for retaining coded data or decoded
data such as data of taken moving images or still images,
or data, moving image data or still image data of received
e-mails, and a slot unit 1206 which enables the storage
medium 1207 to be attached to the portable telephone 1200.
The storage medium 1207 has a flash memory element
as a type of EEPROM (Electrically Erasable and Programmable
Read Only Memory) that is an electrically programmable and
erasable non-volatile memory contained in a plastic case,
like a SD card.
The portable telephone 1200 will be described more
specifically with reference to Fig. 28.
The portable telephone 1200 has a main control unit
1241 that performs general control for the respective units
of the main body including the display unit 1202 and the
control key 1204.
The portable telephone 1200 further includes a power
supply circuit 1240, an operation input control unit 1234,
an image coding unit 1242, a camera interface unit 1233,
a LCD (Liquid Crystal Display) control unit 1232, an image
decoding unit 1239, a multiplexing/demultiplexing unit
1238, a recording/reproduction unit 1237, a
modulation/demodulation unit 1236, and an audio processing
unit 1235. The respective units of the portable telephone
1200 are connected to each other via a synchronization bus
1250.
The power supply circuit 1240 supplies power from a
battery pack to the respective units when a call end/power
supply key is turned ON under the control of a user, thereby

CA 02607755 2007-11-13
133
activating the digital portable telephone with a camera
1200 to be turned into an operable state.
In the portable telephone 1200, the respective units
operate under control of the main control unit 1241 that
is constituted by a CPU, a ROM, a RAM and the like. To be
more specific, in the portable telephone 1200, an audio
signal that is obtained by voice inputting into the voice
input unit 1205 in a voice communication mode is converted
into digital audio data by the audio processing unit 1235.
The digital audio data is subjected to a spectrum spread
process by the modulation/demodulation circuit 1236,
further subjected to a DA conversion process and a
frequency transformation process by the
transmission/receiving circuit 1231, and transmitted
through the antenna 1201.
In this portable telephone set 1200, a signal received
through the antenna 1201 in the voice communication mode
is amplified, and then subjected to a frequency
transformation process and an AD conversion process. The
received signal is further subjected to a spectrum inverse
spread process in the modulation/demodulation circuit 1236,
converted into an analog audio signal by the audio
processing unit 1235, and this analog audio signal is
outputted through the voice output unit 1208.
When the portable telephone 1200 transmits an
electronic mail in a data communication mode, text data
of the e-mail that is inputted by manipulation of the
control key 1204 on the main body is transmitted to the
main control unit 1241 via the operation input control unit

CA 02607755 2007-11-13
134
1234. The main control unit 1241 controls the respective
units so that the text data is subjected to the spectrum
spread processinthe modulation/demodulation circuit 1236,
then subjected to the DA conversion process and the
frequency transformation process in the
transmission/receiving circuit 1231, and then transmitted
to the base station 1110 through the antenna 1201.
When this portable telephone 1200 transmits image
data in the data communication mode, data of an image taken
by the camera unit 1203 is supplied to the image coding
unit 1242 via the camera interface unit 1233. When the
portable telephone 1200 does not transmit the image data,
the data of the image taken by the camera unit 1203 can
be displayed directly on the display unit 1202 via the
camera interface unit 1233 and the LCD control unit 1232.
The image coding unit 1242 includes the image coding
apparatus according to any of the aforementioned
embodiments. This image coding unit 1242 compressively
encodes the image data supplied from the camera unit 1203
by the image coding method according to any of the above
embodiments to convert the same into coded image data, and
outputs the obtained coded image data to the
multiplexing/demultiplexing unit 1238. At the same time,
the portable telephone 1200 transmits voices which are
inputted to the voice input unit 1205 while the image is
being taken by the camera unit 1203, as digital audio data,
to the multiplexing/demultiplexing unit 1238 through the
audio processing unit 1235.
The multiplexing/demultiplexing unit 1238

CA 02607755 2007-11-13
135
multiplexes the coded image data supplied from the image
coding unit 1242 and the audio data supplied from the audio
processing unit 1235 by a predetermined method. Resultant
multiplexed data is subjected to a spectrum spread process
in the modulation/demodulation circuit 1236, then further
subjected to the DA conversion process and the frequency
transformation process in the transmission/receiving
circuit 1231, and obtained data is transmitted through the
antenna 1201.
When the portable telephone 1200 receives data of a
moving image file that is linked to a home page or the like
in the data communication mode, a signal received from the
base station 1110 through the antenna 1201 is subjected
to a spectrum inverse spread process by the
modulation/demodulation circuit 1236, and resultant
multiplexed data is transmitted to the
multiplexing/demultiplexing unit 1238.
When the multiplexed data that is received via the
antenna 1201 is decoded, the multiplexing/demultiplexing
unit 1238 demultiplexes the multiplexed data to divide the
data into a coded bit stream corresponding to the image
data and a coded bit stream corresponding to the audio data,
and the coded image data is supplied to the image decoding
unit 1239 and the audio data is supplied to the audio
processing unit 1235, via the synchronization bus 1250.
The image decoding unit 1239 includes the image
decoding apparatus according to any of the aforementioned
embodiments. The image decoding unit 1239 decodes the
coded bit stream of the image data by the decoding method

CA 02607755 2007-11-13
136
corresponding to the coding method according to any of the
above-mentioned embodiments, to reproduce moving image
data, and supplies the reproduced data to the display unit
1202 through the LCD control unit 1232. Thereby, for
example, the moving image data included in the moving image
file that is linked to the home page is displayed. At the
same time, the audio processing unit 1235 converts the
audio data into an analog audio signal, and then supplies
the analog audio signal to the voice output unit 1208.
Thereby, for example, the audio data included in the moving
image file that is linked to the home page is reproduced.
Here, a system to which the image coding method and
the image decoding method according to any of the
aforementioned embodiments is applicable is not restricted
to the above-mentioned contents provision system.
Recently, digital broadcasting using satellites or
terrestrial waves is talked frequently, and the image
coding apparatus and the image decoding apparatus
according to the above embodiments is applicable also to
a digital broadcasting system as shown in Fig. 29.
More specifically, a coded bit stream corresponding
to video information is transmitted from a broadcast
station 1409 to a satellite 1410 such as a communication
satellite or a broadcast satellite, via radio
communication. When the broadcast satellite 1410
receives the coded bit stream corresponding to the video
information, the satellite 1410 outputs broadcasting waves,
and these waves are received by an antenna 1406 at home
including satellite broadcast receiving facility. For

CA 02607755 2007-11-13
137
example, an apparatus such as a television (receiver) 1401
or a set top box (STB) 1407 decodes the coded bit stream,
and reproduces the video information.
Further, the image decoding apparatus according to
any of the aforementioned embodiments can be mounted also
on a reproduction apparatus 1403 that can read and decode
the coded bit stream recorded on a storage medium 1402 such
as a CD or a DVD (recording medium).
In this case, a reproduced video signal is displayed
on a monitor 1404. The image decoding apparatus may be
mounted on the set top box 1407 that is connected to a cable
for cable television 1405 or an antenna for
satellite/terrestrial broadcast 1406, to reproduce an
output of the image decoding apparatus to be displayed on
a monitor 1408 of the television. In this case, the image
decoding apparatus may be incorporated not in the set top
box but in the television. A vehicle 1412 having an antenna
1411 can receive a signal from the satellite 1410 or the
base station 1107, and reproduce a moving image to display
the same on a display device of a car navigation system
1413 or the like which is mounted on the vehicle 1412.
Further, it is also possible that an image signal can
be coded by the image coding apparatus according to any
of the aforementioned embodiments and recorded in a
recording medium.
A specific example of a recording device is a recorder
1420 such as a DVD recorder that records image signals on
a DVD disk 1421, and a disk recorder that records image
signals on a hard disk. The image signals may be recorded

CA 02607755 2007-11-13
138
on a SD card 1422. Further, when the recorder 1420 includes
the image decoding apparatus according to any of the
aforementioned embodiments, the image signals which are
recorded on the DVD disk 1421 or the SD card 1422 can be
reproduced by the recorder 1420 and displayed on the
monitor 1408.
Here, the structure of the car navigation system 1413
may include, for example, the components of the portable
telephone shown in Fig. 28 other than the camera unit 1203,
the camera interface unit 1233 and the image coding unit
1242, and the same apply to the computer 1111, or the
television (receiver) 1401.
Further, as the terminal such as the portable
telephone 1114, one of three types of terminals: a
transmission-receiving type terminal having both of a
coder and a decoder, a transmission terminal having only
a coder, and a receiving terminal having only a decoder,
can be mounted.
As described above, the image coding method or the
image decoding method according to any of the
aforementioned embodiments is applicable to any of the
above-mentioned devices or systems, whereby the effects
as described in the above embodiments can be obtained.
Further, it goes without saying that the embodiments
and their applications of the present invention are not
restricted to those shown in this description.
Industrial Availability
The variable length coding method and the variable

CA 02607755 2007-11-13
139
length decoding method according to the present invention
effectively eliminates redundant information included in
coefficient data as a target of a variable length coding
process, by selecting a code table adaptively to
characteristics of coefficients that compose the
coefficient data or states of a coding process for the
coefficients, thereby greatly improving a coding
efficiency of a variable length coding process for image
signals or the like. These variable length coding method
and variable length decoding method are useful in data
processing of transmitting or storing moving image data.

Representative Drawing