Variable-length decoding apparatus and method

Details Variable-length decoding apparatus and method Variable-length decoding apparatus and method

2002-02-07

2003-08-05

JeanPierre, Peguy (Department: 2819)

Coded data generation or conversion

Digital code to digital code converters

To or from variable length codes

C341S065000

Reexamination Certificate

active

06603413

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to a decoding apparatus and method for encoded data of still images and moving images.
BACKGROUND OF THE INVENTION
Conventionally, a scheme using an entropy coding technique using a variable-length code is well known as one compression coding technique of still images and moving images. This technique is also adopted in JPEG (Joint Photographic Expert Group) as an international standard. In recent years, especially, many hardware implementation means using a Huffman code table as a variable-length code have been proposed. Such prior art will be explained below.
A conventional decoding apparatus comprises a shift means which comprises a circuit capable of shifting input encoded data for respective bits, a decoder for obtaining the code length and frequency of generation of a head code output from the shift means by comparing the encoded data output from the shift means and a pre-stored minimum or maximum code word of each code length, a symbol memory for storing decoded data (symbol data) in the order of frequency of generation, an additional bit processor for executing an additional bit process, and a shift amount select means for controlling a shift amount of the shift means.
The shift amount select means selects, as the shift amount of the shift means, the code length obtained by the decoder in an odd cycle, and an additional bit length output from the symbol memory in an even cycle. In this example, the throughput of the decoding process is always 0.5 symbols/cycle. In addition, the following technique for improving the throughput of the decoding process is known.
In this technique, a decoding apparatus comprises two different decoders, and a first decoder executes the same process in the aforementioned decoder. On the other hand, a second decoder pre-stores code words with high frequencies of generation and symbol data corresponding to these code words, and outputs symbol data in one cycle for a code word with a high frequency of generation.
For other code words, the first decoder generates an address of the symbol memory, and outputs symbol data output from the symbol memory in the next cycle as decoded data. According to this example, a throughput of a maximum of 1 symbol/cycle can be obtained.
In order to realize a high-speed decoding process, a specific decoding means must be implemented as hardware and the circuit must be operated at high frequency. However, the conventional apparatus suffers the following problems.
Conventionally, since an additional bit processing means is unknown in the decoding process, it is difficult to attain hardware implementation. Especially, when a process is done at the throughput of a maximum of 1 symbol/cycle, since the additional bit processor must at least cope with this processing rate, a hardware implementation means of the additional bit processor is very important upon realizing a high-speed circuit.
When two different blocks (second decoder and symbol memory) output decoded data depending on input encoded data, since their latencies (execution times) are different, the input timings of symbol data to a selector deviate from each other. Hence, control that considers this timing deviation is required, resulting in complicated control.
It is hard to implement a pipeline process. Even if code lengths corresponding to the code words stored in the second decoder are stored in advance and a code length corresponding to a selected code word is shifted out from the shift means in one cycle to solve the aforementioned problem, since the output from the decoding apparatus is one cycle, an arithmetic operation for the decoding process, e.g., an additional bit arithmetic operation must be done in one cycle, and it is difficult to realize a pipeline structure in synchronous circuit design.
In order to achieve efficient, high-speed processes, the processing unit must be shifted for each encoded data. However, conventionally, the shift amount control of the input means to the decoding apparatus is unknown.
FIG. 11
shows the arrangement of a variable-length decoding apparatus as prior art
1
. This decoding apparatus comprises a shift-out means (to be referred to as “shift” hereinafter)
1201
that comprises a circuit capable of shifting input encoded data for respective bits, a decoder
1203
for obtaining the code length and frequency of generation of a head code output from the shift
1201
by comparing the encoded data output from the shift
1201
and a minimum or maximum code word of each code length, which is stored in advance, a symbol memory
1205
for storing decoded data (symbol data RRRR/SSSS) in the order of frequency of generation, an additional bit processor
1202
for executing an additional bit process, and a shift amount select means
1204
for controlling the shift amount of the shift
1201
.
The shift amount select means
1204
selects, as the shift amount of the shift
1201
, the code length obtained by the decoder
1203
in an odd cycle, and an additional bit length output from the symbol memory
1205
in an even cycle.
FIG. 12
shows the arrangement of prior art
2
which can improve the throughput of the decoding process in addition to the decoding apparatus of prior art
1
. In this prior art, a high-speed symbol decoder
1352
executes a high-speed decoding process of a plurality of selected symbols, and a symbol decoder
1353
decodes other symbols. As an example of a select means of symbols to be decoded by the high-speed symbol decoder
1352
, a plurality of symbols in descending order of frequency of generation, or symbols with zero runlength may be selected.
A characteristic feature of prior art
2
lies in that priority is given to the decoding process of the high-speed symbol decoder
1352
. If input encoded data hits a code word corresponding to a symbol registered in the high-speed symbol decoder
1352
, the decoding result of the high-speed symbol decoder
1352
is preferentially selected as an output.
FIG. 13
shows prior art
3
as a technique for further improving the throughput of prior art
2
. A variable-length decoding apparatus according to prior art
3
comprises a 1-code word decoder
1403
for decoding a head code word, and a 2-successive code word decoder
1402
capable of decoding a successive sequence of two ode words from the head with high frequency of generation, and is characterized in that priority is given to the 2-successive code word decoder
1402
. If a hit has occurred in the 2-successive code word decoder
1402
, since two code words can be decoded at one time, the throughput can be further improved.
As the encoded data sizes of still images and moving images increase, the required processing performance for an encoding processing apparatus becomes considerably high. Especially, since the variable-length decoding apparatus must decode a variable-length code, it is very difficult to improve the throughput. For this reason, various solutions have been proposed so far, but the following problems remain unsolved.
The throughput varies depending on the hit ratio of the high-speed symbol decoder
1352
. Even if all data hit, the performance of a maximum of only one symbol per decoding sequence is obtained. This throughput is insufficient in consideration of the performance required for a variable-length decoding apparatus in the future. When the symbol decoder
1353
can decode in one cycle, an effect obtained upon adopting a parallel arrangement with the high-speed symbol decoder
1532
is lost. Such problem occurs when a table that stores symbol data as a decoding result comprises an asynchronous RAM or hardwired. The recent advance of semiconductor techniques allows to operate at higher clock frequency even if the circuit arrangement remains the same, and a conventional circuit which processes in two cycles can now process in one cycle.
As in prior art
2
, the throughput varies depending on the hit ratio of the 2-successive code word decoder
1402
, and the performance of a maximum of two code words per decoding sequence can be obtained

Affiliated with

Also associated with

Rating

Variable-length decoding apparatus and method does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Variable-length decoding apparatus and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Variable-length decoding apparatus and method will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3111003