US 6,636,168 B2Granted

Variable length coding method and variable length coding apparatus

AssigneeMatsushita Electric Industrial Co., Ltd.

InventorsMasahiro Ohashi, Tsuyoshi Nakamura

Life of this patent

Estimating the term…

Loading patent…

Abstract

A variable length coding (VLC) method and a variable length coding apparatus for producing variable length coding having a reduced number of arithmetic cycles. The method includes carrying out (a) performing a VLC process and assigning a code to a combination of (Last, Run, Level), (b) subtracting LMAX as the maximum Level corresponding to (Last, Run) from Level to calculate amended Level and thereafter assigning a code to a combination of (Last, Run, amended Level), (c) subtracting a value that is obtained by adding 1 and RMAX as the maximum Run corresponding to (Last, Level) from Run to calculate amended Run and thereafter assigning a code to a combination of (Last, amended Run, Level), and (d) of performing faxed length coding (FLC) assignment in parallel with each other, and includes (e) selecting the code according to predetermined priorities.

Claims9

Dependent claims

A variable length coding (VLC) method by which Run as the number of preceding zero coefficients, Level as a value of a non-zero coefficient, and Last indicating whether the non-zero coefficient is the last one from discrete cosine transform coefficients which are rearranged in an one-dimensional array are taken as a combination of (Last, Run, Level), a VLC process of assigning a unique code to the combination is carried out, and when the VLC assignment cannot be performed, three escape modes are applied, thereby performing coding, comprising:

process (a) performing the code assignment for the combination of (Last, Run, Level);
process (b), as a first escape mode, subtracting LMAX as a maximum Level corresponding to (Last, Run) from Level, and performing code assignment for a combination including an obtained amended Level of (Last, Run, amended Level);
process(c), as a second escape mode, subtracting a value that is obtained by adding RMAX as a maximum Run corresponding to (Last, Level) and 1 from Run, and performing code assignment for a combination including an obtained amended Run of (Last, amended Run, Level);
and
process(d), as a third escape mode, assigning a fixed length code (FLC), wherein processes (a) to (d) are carried out in parallel with each other, and
process(e) selecting the codes assigned in said processes(a) to (d) in the prioritized order:
(a), (b), (c), (d), and outputting the selected codes.

4 more elements

A variable length coding (VLC) apparatus comprising an RMAX table for receiving a Level absolute value signal as an absolute value of a Level signal and a Last signal;

an LMAX table for receiving a Run signal and the Last signal;
a first VLC table for receiving the Level absolute value signal, a signal indicating the sign of the Level signal, the Run signal, and the Last signal;
a first subtraction circuit for subtracting a sum of an output signal of the RMAX table and 1, from the Run signal;
a second register for holding an output signal of the first subtraction circuit;
a second VLC table for receiving an output signal of the second register, the Level absolute value signal, the signal indicating the sign of the Level signal, and the Last signal;
a second subtraction circuit for subtracting an output signal of the LMAX table from the Level absolute value signal;
a third register for holding an output signal of the second subtraction circuit;
a third VLC table for receiving an output signal of the third register, the signal indicating the sign of the Level signal, the Run signal, and the Last signal;
a first register for holding an output signal of the first VLC table;
a fourth register for holding an output signal of the second VLC table;
a fifth register for holding an output signal of the third VLC table;
an RMAX VLC generation circuit for receiving an output signal of the fourth register;
an LMAX VLC generation circuit for receiving an output signal of the fifth register;
a fixed length code (FLC) generation circuit for receiving the Level signal, the Run signal, and the Last signal;
a control circuit for receiving an output signal of the first register, the output signal of the fourth register, and the output signal of the fifth register;
and a selection circuit for receiving the output signal of the first register, an output signal of the RMAX VLC generation circuit, an output signal of the LMAX VLC generation circuit, and an output signal of the FLC generation circuit, wherein
the control circuit judges whether the output signal of the first register, the output signal of the fourth register, and the output signal of the fifth register are correct VLCs, and outputs a selection signal for indicating the judgement result to the selection circuit, and
the selection circuit selects one output signal from the output signal of the first register, the output signal of the RMAX VLC generation circuit, the output signal of the LMAX VLC generation circuit, and the output signal of the FLC generation circuit, in accordance with the selection signal, and outputs the selected signal as a code.

15 more elements

A variable length coding (VLC) apparatus comprising an RMAX table for receiving a Level absolute value signal as an absolute value of a Level signal and a Last signal;

an LMAX table for receiving a Run signal and the Last signal;
a first subtraction circuit for subtracting a sum of an output signal of the RMAX table and 1, from the Run signal;
a second subtraction circuit for subtracting an output signal of the LMAX table from the Level absolute value signal;
a second register for holding an output signal of the first subtraction circuit;
a third register for holding an output signal of the second subtraction circuit;
a first selection circuit for selecting one of an output signal of the third register and the Level absolute value signal;
a second selection circuit for selecting one of an output signal of the second register and the Run signal;
a VLC table for receiving an output signal of the first selection circuit, an output signal of the second selection circuit, a signal indicating the sign of the Level signal, and the Last signal;
a first register for holding an output signal of the VLC table, a fixed length code (FLC) generation circuit for receiving the Level signal, the Run signal, and the Last signal;
a control circuit for receiving an output signal of the first register;
a VLC generation circuit for receiving the output signal of the first register, and an output signal of the control circuit;
and a third selection circuit for receiving an output signal of the VLC generation circuit and an output signal of the FLC generation circuit, wherein
in a first cycle, the first selection circuit receives a first selection signal outputted from the control circuit, selects the Level absolute value signal, and outputs the Level absolute value signal to the VLC table, the second selection circuit receives a second selection signal outputted from the control circuit, selects the Run signal, and outputs the Run signal to the VLC table, then the VLC table implements VLC, outputs an output signal to the first register, and in a second cycle, the control circuit judges whether the output signal of the first register is correct as a normal VLC, and when the output signal of the first register is judged to be correct as a normal VLC, outputs a third selection signal indicating the judgement result to the VLC generation circuit and the third selection circuit, the VLC generation circuit outputs the output signal of the first register as a normal VLC code, and the third selection circuit selects the output signal of the VLC generation circuit in accordance with the third selection signal and outputs the selected signal,
in the first cycle, the LMAX table receives the Last signal and the Run signal, generates an LMAX data signal, and outputs the LMAX data signal to the second subtraction circuit, the second subtraction circuit receives the LMAX data signal and the Level absolute value signal, subtracts the LMAX data signal from the Level absolute value signal, and outputs an obtained result to the third register, and in the second cycle, the first selection circuit receives the first selection signal outputted from the control circuit, selects the output signal of the third register, and outputs the selected signal to the VLC table, the second selection circuit receives the second selection signal outputted from the control circuit, selects the Run signal, and outputs the selected Run signal to the VLC table, then the VLC table implements VLC, outputs an output signal to the first register, and in the third cycle, when the judgement of the normal VLC performed in the second cycle shows that the output signal is not correct, the control circuit judges whether the output signal of the first register is correct as LMAX VLC, and when the output signal of the first register is judged to be correct as LMAX VLC, outputs the third selection signal indicating the judgement result to the VLC generation circuit and the third selection circuit, the VLC generation circuit outputs the output signal of the first register as an LMAX VLC code, and the third selection circuit selects the output signal of the VLC generation circuit in accordance with the third selection signal and outputs the selected signal, and
in the first cycle, the RMAX table receives the Last signal and the Level absolute value signal, generates an RMAX data signal, and outputs the PMAX data signal to the first subtraction circuit, the first subtraction circuit receives the RMAX data signal and the Run signal, subtracts a value that is obtained by adding the RMAX data signal and 1, from the Run signal, and outputs an obtained result to the second register, and in the third cycle, the first selection circuit receives the first selection signal outputted from the control circuit, selects the Level absolute value signal, and outputs the selected signal to the VLC table, the second selection circuit receives the second selection signal outputted from the control circuit, selects the output signal of the second register, and outputs the selected signal to the VLC table, then the VLC table implements VLC, outputs an output signal to the first register, and in a fourth cycle, when the judgement of the LMAX VLC performed in the third cycle shows that the output signal is not correct, the control circuit judges whether the output signal of the first register is correct as RMAX VLC, and when the output signal of the first register is judged to be correct as RMAX VLC, outputs the third selection signal to the VLC generation circuit and the third selection circuit, the VLC generation circuit outputs the output signal of the first register as an RMAX VLC code, and the third selection circuit selects the output signal of the VLC generation circuit in accordance with the third selection signal and outputs the selected signal, and
when it is judged that none of the output signals of the first register, inputted to the control circuit, is correct as VLC, in a fifth cycle, the third selection circuit selects the output signal of the FLC generation circuit and outputs the selected signal.

13 more elements

A variable length coding (VLC) apparatus comprising an RMAX table for receiving a Level absolute value signal as an absolute value of a Level signal and a Last signal;

an LMAX table for receiving a Run signal and the Last signal;
a first subtraction circuit for subtracting a sum of an output signal of the RMAX table and 1, from the Run signal;
a second subtraction circuit for subtracting an output signal of the LMAX table from the Level absolute value signal;
a second register for holding an output signal of the first subtraction circuit;
a third register for holding an output signal of the second subtraction circuit;
a first selection circuit for selecting one of an output signal of the third register and the Level absolute value signal;
a second selection circuit for selecting one of an output signal of the second register and the Run signal;
a VLC table for receiving an output signal of the first selection circuit, and output signal of the second selection circuit, a signal indicating the sign of the Level signal, and the Last signal;
a first register for holding an output signal of the VLC table;
a fixed length code (FLC) generation circuit for receiving the Level signal, the Run signal, and the Last signal;
a control circuit for receiving an output signal of the first register;
a VLC generation circuit for receiving the output signal of the first register and an output signal of the control circuit;
and a third selection circuit for receiving an output signal of the VLC generation circuit and an output signal of the FLC generation circuit, wherein
in a first cycle, the first selection circuit receives a first selection signal outputted from the control circuit, selects the Level absolute value signal, and outputs the selected signal to the VLC table, the second selection circuit receives a second selection signal outputted from the control circuit, selects the Run signal, and outputs the Run signal to the VLC table, then the VLC table implements VLC and outputs an output signal to the first register, and in a second cycle, the control circuit judges whether the output signal of the first register is correct as a normal VLC, and when the output signal of the first register is judged to be correct as a normal VLC, outputs a third selection signal indicating the judgement result to the VLC generation circuit and the third selection circuit, the VLC generation circuit outputs the output signal of the first register as a normal VLC code, and the third selection circuit selects the output signal of the VLC generation signal in accordance with the third selection signal and outputs the selected signal, and
in the first cycle, the LMAX table receives the Last signal and the Run signal, generates an LMAX data signal, and outputs the generated signal to the second subtraction circuit, the second subtraction circuit receives the LMAX data signal and the Level absolute value signal, subtracts the LMAX data signal from the Level absolute value signal, and outputs an obtained result to the third register, and in the second cycle, the first selection circuit receives the first selection signal outputted from the control circuit, selects the output signal of the third register, and outputs the selected signal to the VLC table, the second selection circuit receives the second selection signal outputted from the control circuit, selects the Run signal, and outputs the Run signal to the VLC table, then the VLC table implements VLC and outputs an output signal to the first register, and in the third cycle, when the judgement of the normal VLC performed in the second cycle shows that the output signal is not correct, the control circuit judges whether the output signal of the first register is correct as LMAX VLC, and when the output signal of the first register is judged to be correct as LMAX VLC, outputs the third selection signal indicating the judgement result to the VLC generation circuit and the third selection circuit, the VLC generation circuit outputs the output signal of the first register as an LMAX VLC code, and the third selection circuit selects the output signal of the VLC generation circuit in accordance with the third selection signal and outputs the selected signal, and
in the first cycle, the RMAX table receives the Last signal and the Level absolute value signal, generates an RMAX data signal, and outputs the generated signal to the first subtraction circuit, the first subtraction circuit receives the RMAX data signal and the Run signal, subtracts a value that is obtained by adding the RMAX data signal and 1, from the Run signal, and outputs an obtained result to the second register, and in the third cycle, the first selection circuit receives the first selection signal outputted from the control circuit, selects the Level absolute value signal, and outputs the selected signal to the VLC table, the second selection circuit receives the second selection signal outputted from the control circuit, selects an output signal of the second register, and outputs the selected signal to the VLC table, then the VLC table implements VLC and outputs an output signal to the first register, and in a fourth cycle, when the judgement of the LMAX VLC performed in the third cycle shows that the output signal is not correct, the control circuit judges whether the output signal of the first register is correct as PMAX VLC, and when the output signal of the first register is judged to be correct as RMAX VLC, outputs the third selection signal to the VLC generation circuit and the third selection circuit, the VLC generation circuit outputs the output signal of the first register as an RMAX VLC code, and the third selection circuit selects an output signal of the VLC generation circuit in accordance with the third selection signal and outputs the selected signal, and
when it is judged that none of the output signals of the first register, inputted to the control circuit, is correct as VLC, in the fourth cycle, the third selection circuit selects the output signal of the FLC generation circuit and outputs the selected signal.

14 more elements

A variable length coding (VLC) apparatus comprising a first selection circuit for receiving a Level absolute value signal as an absolute value of a Level signal, a Last signal, and fixed values, selecting one of the Level absolute value signal and the fixed value to output a first output signal, and selecting one of the Last signal and the fixed value to output a second output signal;

an RMAX table for receiving the first output signal and the second output signal;
a second selection circuit for receiving a Run signal, the Last signal and fixed values, selecting one of the Run signal and the fixed value to output a third output signal, and selecting one of the Last signal and the fixed value to output a fourth selection signal;
an LMAX table for receiving the third output signal and the fourth output signal;
a first subtraction circuit for subtracting a sum of an output signal of the RMAX table and 1, from the Run signal;
a second subtraction circuit for subtracting an output signal of the LMAX table from the Level absolute value signal;
a second register for holding an output signal of the first subtraction circuit;
a third register for holding an output signal of the second subtraction circuit;
a third selection circuit for selecting one of an output signal of the third register and the Level absolute value signal;
a fourth selection circuit for selecting one of an output signal of the second register and the Run signal;
a VLC table for receiving an output signal of the third selection circuit, an output signal of the fourth selection circuit, a signal indicating the sign of the Level signal, and the Last signal;
a first register for holding an output signal of the VLC table;
a fixed length code (FLC) generation circuit for receiving the Level signal, the Run signal, and the Last signal;
a control circuit for receiving an output signal of the first register;
a VLC generation circuit for receiving the output signal of the first register and an output signal of the control circuit;
and a fifth selection circuit for receiving an output signal of the VLC generation circuit and an output signal of the FLC generation circuit, wherein
in a first cycle, the first selection circuit receives a first selection signal outputted from the control circuit and selects the fixed value, the second selection circuit receives a second selection signal outputted from the control circuit and selects the Run signal and the Last signal, the third selection circuit receives a third selection signal outputted from the control circuit, selects the Level absolute value signal, and outputs the selected signal to the VLC table, the fourth selection circuit receives a fourth selection signal outputted from the control circuit, selects the Run signal, and outputs the Run signal to the VLC table, and then the VLC table implements VLC and outputs an output signal to the first register, and in a second cycle, the control circuit judges whether the output signal of the first register is correct as a normal VLC, and when the output signal of the first register is judged to be correct as a normal VLC, outputs a fifth selection signal indicating the judgement result to the VLC generation circuit and the fifth selection circuit, the VLC generation circuit outputs the output signal of the first register as a normal VLC code, and the fifth selection circuit selects the output signal of the VLC generation circuit in accordance with the fifth selection signal and outputs the selected signal, and
in the first cycle, the LMAX table receives the Last signal and the Run signal, generates an LMAX data signal, and outputs the generated signal to the second subtraction circuit, the second subtraction circuit receives the LMAX data signal and the Level absolute value signal, subtracts the LMAX data signal from the Level absolute value signal, and outputs an obtained result to the third register, and in the second cycle, the third selection circuit receives the third selection signal outputted from the control circuit, selects the output signal of the third register, and outputs the selected signal to the VLC table, the fourth selection circuit receives the fourth selection signal outputted from the control circuit, selects the Run signal, and outputs the Run signal to the VLC table, then the VLC table implements VLC and outputs an output signal to the first register, and in a third cycle, when the judgement of the normal VLC performed in the second cycle shows that the output signal is not correct, the control circuit judges whether the output signal of the first register is correct as LMAX VLC, and when the output signal of the first register is judged to be correct as LMAX VLC, outputs the fifth selection signal indicating the judgement result to the VLC generation circuit and the fifth selection circuit, the VLC generation circuit outputs the output signal of the first register as an LMAX VLC code, and the fifth selection circuit selects an output signal of the VLC generation circuit in accordance with the fifth selection signal and outputs the selected signal, and
in the second cycle, the RMAX table receives the Last signal and the Level absolute value signal, generates an RMAX data signal, and outputs the generated signal to the first subtraction circuit, and the first subtraction circuit receives the RMAX data signal and the Run signal, subtracts a value that is obtained by adding the RMAX data signal and 1, from the Run signal, and outputs an obtained result to the second register, and in the third cycle, the third selection circuit receives the third selection signal outputted from the control circuit, selects the Level absolute value signal, and outputs the selected signal to the VLC table, the fourth selection circuit receives the fourth selection signal outputted from the control circuit, selects the output signal of the second register, and outputs the selected signal to the VLC table, then the VLC table implements VLC and outputs an output signal to the first register, and in a fourth cycle, when the judgement of LMAX VLC performed in the third cycle shows that the output signal is not correct, the control circuit judges whether the output signal of the first register is correct as RMAX VLC, and when the output signal of the first register is judged to be correct as RMAX VLC, outputs the fifth selection signal indicating the judgement result to the VLC generation circuit and the third selection circuit, the VLC generation circuit outputs the output signal of the first register as an RMAX VLC code, and the fifth selection circuit selects an output signal of the VLC generation circuit in accordance with the fifth selection signal and outputs the selected signal, and
when it is judged that none of the output signals of the first register, inputted to the control circuit, is correct as VLC, in the fourth cycle, the fifth selection circuit selects the output signal of the FLC generation circuit and outputs the selected signal.

16 more elements

Dependencies are inferred from the claim text.

Facts

Application: 10/031,711Filed 21 Feb 2002
Priority: JP 2000-15119323 May 2000
Published: US 2003/0006917 A19 Jan 2003
Granted: 21 Oct 2003
Term ends: Not estimatedThe source records don’t support an estimate.

Classification5 codes

H03M 7/4006
Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code: conversion to or from arithmetic code
H04N 19/60
Methods or arrangements for coding, decoding, compressing or decompressing digital video signals: using transform coding
H04N 19/61
Using transform coding: in combination with predictive coding
H03M
Coding