Variable-length code determining device and variable-length code decoding method

• US 7,924,179 B2
• Filed: 03/15/2007
• Issued: 04/12/2011
• Est. Priority Date: 03/23/2006
• Status: Expired due to Fees

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Kumura, Takahiro
• Primary Examiner(s): Lauture; Joseph
• Application Number:
  US12/225,422
• Publication Number:
  US 20100225508A1
• Time in Patent Office: 1,489 Days
• Field of Search: 341/67, 341/65, 341/51, 375/240.25, 375/240.23, 375/240.01, 382/233, 382/244, 382/245, 382/246, 382/247, 712/213, 712/224, 712/226, 712/204, 707/101
• US Class Current: 341/67
• CPC Class Codes: G06F 9/30007 to perform operations on data operands
• CPC Class Codes: G06F 9/30018 Bit or string instructions
• CPC Class Codes: G06F 9/30021 Compare instructions, e.g. Greater-Than, Equal-To, MINMAX
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
• CPC Class Codes: H04N 19/423 characterised by memory arrangements H04N19/433 takes precedence
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding

Abstract

To provide a decoding device that compactly stores prefix related information therein compatible to variable-length codes used in various systems. The decoding device includes a register file in which a prefix common portion and a word length of the prefix common portion, prefix individual portions and word lengths of the prefix individual portions, word lengths of suffixes, and an input bit sequence are stored, a bit matching unit that determines a prefix included in the input bit sequence from prefixes generated from the prefix common portion and the prefix individual portions, a codeword computation unit that computes the word length of a codeword included in the input bit sequence using the respective word lengths of the prefix common portion, a prefix individual portion, and a suffix corresponding to the determined prefix, and an index computation unit that computes an index in a symbol table using the respective word lengths of the corresponding suffix and the codeword.

Claims

1. A variable-length code decoding device that decodes variable-length encoded codeword using prefix included in the codeword, comprising:

a unit that stores a prefix common portion common to a plurality of prefixes used for decoding, a prefix individual portion except the prefix common portion in each prefix, and an input bit sequence including an unknown codeword of variable-length code; and

a prefix identification unit that determines which prefix among a plurality of prefixes is included or not in the input bit sequence stored in said storage unit, said plurality of prefixes being generated from each prefix common portion and a plurality of prefix individual portions corresponding to the prefix common portion concerned, said prefix common portion and said prefix individual portions being stored in said storage unit.

2. A variable-length code decoding device that decodes variable-length encoded codeword using a prefix included in the codeword, comprising:

a storage unit that stores a prefix common portion common to a plurality of prefixes used for decoding and a word length of the prefix common portion, a prefix individual portion except the prefix common portion in each prefix and a word length of the prefix individual portion, a word length of a suffix except the prefix in each of a plurality of codewords, and an input bit sequence including an unknown codeword of variable-length code;

a prefix identification unit that determines which prefix among the prefixes generated from the prefix common portion and the plurality of prefix individual portions is included or not in the input bit sequence;

a word length computation unit that computes word length of the unknown codeword included in the input bit sequence, using the word length of the prefix common portion, the word length of the prefix individual portion, and the word length of the suffix, specified based on a result of the determination;

an index computation unit that computes index of a decoding table, using the word length of the suffix and the word length of the unknown codeword, specified based on the result of the determination; and

a control unit that controls said prefix identification unit, said word length computation unit, and said index computation unit, according to an instruction for generating the word length of the unknown codeword included in the input bit sequence and the index for said decoding table.

3. A program control processor implementing said decoding device according to claim 2, wherein

said storage unit comprises a register file;

and

said control unit comprises an instruction decoder that controls said prefix identification unit, said word length computation unit, and said index computation unit according to an instruction of a decoding program and stores in said register file the computed word length of the unknown codeword and the index of said decoding table.

4. A variable-length code decoding device that decodes variable-length encoded codeword using a decoded value table, comprising:

storage means for storing a plurality of codewords used for decoding and word lengths of the codewords, and an input bit sequence including an unknown codeword of variable-length code;

identification means for determining which codeword

among the codewords is included or not in the input bit sequence, using the codewords and the word lengths of the codewords;

word length computation means for computing word length of the unknown codeword included in the input bit sequence, based on a result of the determination;

index computation means for computing index for referring to said decoded value table, based on the result of the determination; and

control means for controlling said identification means, said word length computation means, and said index computation means such that the word length of the unknown codeword included in the input bit sequence and the index are generated.

5. A program control processor that implements said decoding device according to claim 4, wherein

said storage means comprises a register file;

and

said control means comprises an instruction decoder that controls said identification means, said word length computation means, and said index computation means according to an instruction of a decoding program, and stores the computed word length of the unknown codeword and the computed index in said register file.

6. A variable-length code decoding method of decoding variable-length encoded codeword using a prefix included in the codeword, comprising:

storing a prefix common portion common to a plurality of prefixes used for decoding;

storing a prefix individual portion except the prefix common portion in each prefix;

storing an input bit sequence including an unknown codeword of variable-length code;

generating prefixes from each prefix common portion and a plurality of prefix individual portions corresponding to the prefix common portion concerned, said prefix common portion and said prefix individual portions being stored; and

determining which prefix among said prefixes is included or not in the input bit sequence.

7. A variable-length code decoding program that causes a computer comprising a decoding device that decodes variable-length encoded codeword using a prefix included in the codeword to:

storing a prefix common portion common to a plurality of prefixes used for decoding;

storing a prefix individual portion except the prefix common portion in each prefix;

storing an input bit sequence including an unknown codeword of variable-length code;

generating a plurality of prefixes generated from each prefix common portion and a plurality of prefix individual portions corresponding to the prefix common portion concerned, said prefix common portion(s) and said prefix individual portions being stored; and

determining which prefix among said plurality of prefixes is included or not in the input bit sequence.