TABLE DEVICE, VARIABLE LENGTH CODING APPARATUS, VARIABLE LENGTH DECODING APPARATUS, AND VARIABLE LENGTH CODING AND DECODING APPARATUS

• US 20100057810A1
• Filed: 05/09/2007
• Published: 03/04/2010
• Est. Priority Date: 01/19/2007
• Status: Active Grant

• Current Assignee: Mitsubishi Electric Corporation
• Original Assignee: Mitsubishi Electric Corporation
• Inventors: EI, Tomomi, Minegishi, Noriyuki
• Granted Patent: US 8,291,150 B2
• Time in Patent Office: Days
• US Class Current: 707/754
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code

Abstract

A table device includes a match cell number output unit 25 for outputting a match cell number showing a cell PE which outputs a matching signal, and an address decoder 26 for specifying a node from among nodes in a search tree which construct a conversion table, the node corresponding to the match cell number. The table device acquires a data conversion value assigned to the above-mentioned node from a configuration memory 21, and, when the data conversion value is data showing a coded result or the like, outputs the data conversion value to outside the table device, whereas when the data conversion value is a branch code of the search tree, updates the cell PE to which a comparison instruction signal is furnished.

Claims

1. A table device comprising:

a configuration memory for holding a conversion table for variable length coding and variable length decoding which is constructed in a form of a search tree;

a plurality of cells to each of which a specific comparison object value is assigned, and each of which, when receiving a comparison instruction signal, compares said comparison object value with input data and outputs a matching signal when said comparison object value matches said input data;

a cell number output means for outputting a cell number indicating a cell which is included in said plurality of cells and which outputs the matching signal;

a node specifying means for specifying a node corresponding to the cell number outputted from said cell number output means from among nodes of the search tree which construct said conversion table; and

a cell control means for acquiring a data conversion value assigned to the node specified by said node specifying means from said configuration memory, and for outputting said data conversion value to outside said table device when said data conversion value is data showing a coded result or a decoded result, and for updating a cell to which said cell control means furnishes the comparison instruction signal when said data conversion value is a branch code of said search tree.

2. The table device according to claim 1, characterized in that in a case in which cells to each of which a comparison object value having a same number of bits is assigned are grouped into a same cell group, the cell control means outputs the comparison instruction signal to a cell group corresponding to a subtree of the search tree which constructs the conversion table.

3. The table device according to claim 1, characterized in that in a case in which a plurality of conversion tables are held by the configuration memory, the cell control means outputs a table number showing a conversion table to be used, the node specifying means specifies a node corresponding to the cell number outputted from said cell number output means from among nodes of the search tree which construct the conversion table shown by the table number outputted from said cell control means.

4. A variable length coding apparatus comprising:

a coefficient data storing means for storing coefficient data to be variable length coded;

a conversion table output means for outputting a conversion table for variable length coding which is constructed in a form of a search tree;

a configuration memory for holding the conversion table outputted from said conversion table output means;

a plurality of cells to each of which a specific comparison object value is assigned, and each of which, when receiving a comparison instruction signal, compares said comparison object value with the coefficient data stored in said coefficient data storing means, and outputs a matching signal when said comparison object value matches said coefficient data;

a cell number output means for outputting a cell number showing a cell which is included in said plurality of cells and which outputs the matching signal;

a node specifying means for specifying a node corresponding to the cell number outputted from said cell number output means from among nodes of the search tree which construct said conversion table;

a cell control means for acquiring a data conversion value assigned to the node specified by said node specifying means from said configuration memory, and for, when said data conversion value is a bit stream, outputting said bit stream, whereas when said data conversion value is a branch code of said search tree, updating a cell to which said cell control means furnishes the comparison instruction signal; and

a packing means for packing the bit stream outputted from said cell control means in data in units of bits.

5. A variable length decoding apparatus comprising:

a bit stream storing means for storing a bit stream to be variable length decoded;

a bit stream output means for reading the bit stream from said bit stream storing means in units of bits so as to output a bit stream having a fixed length;

a conversion table output means for outputting a conversion table for variable length decoding which is constructed in a form of a search tree;

a configuration memory for holding the conversion table outputted from said conversion table output means;

a plurality of cells to each of which a specific comparison object value is assigned, and each of which, when receiving a comparison instruction signal, compares said comparison object value with the bit stream outputted from said bit stream output means, and outputs a matching signal when said comparison object value matches said bit stream;

a cell number output means for outputting a cell number showing a cell which is included in said plurality of cells and which outputs the matching signal;

a node specifying means for specifying a node corresponding to the cell number outputted from said cell number output means from among nodes of the search tree which construct said conversion table; and

a cell control means for acquiring a data conversion value assigned to the node specified by said node specifying means from said configuration memory, and for, when said data conversion value is coefficient data, outputting said coefficient data, whereas when said data conversion value is a branch code of said search tree, updating a cell to which said cell control means furnishes the comparison instruction signal.

6. A variable length coding and decoding apparatus comprising:

a coefficient data storing means for storing coefficient data to be variable length coded;

a bit stream storing means for storing a bit stream to be variable length decoded;

a bit stream output means for reading the bit stream from said bit stream storing means in units of bits so as to output a bit stream having a fixed length;

a conversion table output means for outputting a conversion table for variable length coding or variable length decoding which is constructed in a form of a search tree;

a configuration memory for holding the conversion table outputted from said conversion table output means;

a plurality of cells to each of which a specific comparison object value is assigned, and each of which, when receiving a comparison instruction signal, compares said comparison object value with said coefficient data or said bit stream, and outputs a matching signal when said comparison object value matches said coefficient data or said bit stream;

a cell number output means for outputting a cell number showing a cell which is included in said plurality of cells and which outputs the matching signal;

a node specifying means for specifying a node corresponding to the cell number outputted from said cell number output means from among nodes of the search tree which construct said conversion table;

a cell control means for acquiring a data conversion value assigned to the node specified by said node specifying means from said configuration memory, and for, when said data conversion value is a bit stream or coefficient data, outputting said data conversion value, whereas when said data conversion value is a branch code of said search tree, updating a cell to which said cell control means furnishes the comparison instruction signal; and

a packing means for packing the bit stream outputted from said cell control means, which is a data conversion value, in data in units of bits.

7. A table device comprising:

a plurality of cells to each of which a specific comparison object value is assigned, each of which includes a comparator for, when receiving a comparison instruction signal, comparing said comparison object value with input data, and a plurality of registers for holding a conversion table including a data conversion value corresponding to said comparison object value, and each of which, when a result of the comparison by said comparator shows that the comparison object value matches the input data, outputs a data conversion value held by one of the registers which corresponds to a register selection signal, whereas when the result of the comparison by said comparator shows that the comparison object value does not match the input data, outputs a zero value as said data conversion value;

an OR circuit for implementing an OR operation on the data conversion values outputted from said plurality of cells; and

a cell control means for, when the data conversion values on which the OR operation is implemented by said OR circuit are data showing a coded result or a decoded result, outputting said data conversion values to outside said table device, whereas, when said data conversion values are a branch code, updating a cell to which said cell control means furnishes said comparison instruction signal according to the branch code and also updating the register selection signal according to the branch code.

8. The table device according to claim 7, characterized in that the cell control means generates the register selection signal from a register selection value included in either an initial code which is set up at a time of starting variable length coding or variable length decoding or the branch code and outputs the register selection signal to the plurality of cells, and also outputs the comparison instruction signal to cells which are included in said plurality of cells and which correspond to a cell group specification code included in the initial code or the branch code.

9. The table device according to claim 7, characterized in that each of the plurality of cells includes an address decoder for writing a conversion table in the plurality of registers.

10. A variable length coding apparatus comprising:

a coefficient data storing means for storing coefficient data to be variable length coded;

a conversion table output means for outputting a conversion table for variable length coding which is constructed in a form of a search tree;

a plurality of cells to each of which a specific comparison object value is assigned, each of which includes a comparator for, when receiving a comparison instruction signal, comparing said comparison object value with input data, and a plurality of registers for holding said conversion table including a data conversion value corresponding to said comparison object value, and each of which, when a result of the comparison by said comparator shows that the comparison object value matches the input data, outputs a data conversion value held by one of the registers which corresponds to a register selection signal, whereas when the result of the comparison by said comparator shows that the comparison object value does not match the input data, outputs a zero value as said data conversion value;

an OR circuit for implementing an OR operation on the data conversion values outputted from said plurality of cells;

a cell control means for, when the data conversion values on which the OR operation is implemented by said OR circuit are a bit stream, outputting said bit stream, whereas, when said data conversion values are a branch code, updating a cell to which said cell control means furnishes said comparison instruction signal according to the branch code and also updating the register selection signal according to the branch code; and

a packing means for packing the bit stream outputted from said cell control means in data in units of bits.

11. A variable length decoding apparatus comprising:

a bit stream storing means for storing a bit stream to be variable length decoded;

a bit stream output means for reading the bit stream from said bit stream storing means in units of bits so as to output a bit stream having a fixed length;

a conversion table output means for outputting a conversion table for variable length decoding which is constructed in a form of a search tree;

a plurality of cells to each of which a specific comparison object value is assigned, each of which includes a comparator for, when receiving a comparison instruction signal, comparing said comparison object value with the bit stream outputted from said bit stream output means, and a plurality of registers for holding said conversion table including a data conversion value corresponding to said comparison object value, and each of which, when a result of the comparison by said comparator shows that the comparison object value matches the bit stream, outputs a data conversion value held by one of the registers which corresponds to a register selection signal, whereas when the result of the comparison by said comparator shows that the comparison object value does not match the bit stream, outputs a zero value as said data conversion value;

an OR circuit for implementing an OR operation on the data conversion values outputted from said plurality of cells; and

a cell control means for, when the data conversion values on which the OR operation is implemented by said OR circuit are coefficient data, outputting said coefficient data, whereas, when said data conversion values are a branch code, updating a cell to which said cell control means furnishes said comparison instruction signal according to the branch code and also updating the register selection signal according to the branch code.

12. A variable length coding and decoding apparatus comprising:

a coefficient data storing means for storing coefficient data to be variable length coded;

a bit stream storing means for storing a bit stream to be variable length decoded;

a bit stream output means for reading the bit stream from said bit stream storing means in units of bits so as to outputting a bit stream having a fixed length;

a conversion table output means for outputting a conversion table for variable length coding or variable length decoding which is constructed in a form of a search tree;

a plurality of cells to each of which a specific comparison object value is assigned, each of which includes a comparator for, when receiving a comparison instruction signal, comparing said comparison object value with said coefficient data or said bit stream, and a plurality of registers for holding said conversion table including a data conversion value corresponding to said comparison object value, and each of which, when a result of the comparison by said comparator shows that the comparison object value matches the coefficient data or the bit stream, outputs a data conversion value held by one of the registers which corresponds to a register selection signal, whereas when the result of the comparison by said comparator shows that the comparison object value does not match the coefficient data or the bit stream, outputs a zero value as said data conversion value;

an OR circuit for implementing an OR operation on the data conversion values outputted from said plurality of cells;

a cell control means for, when the data conversion values on which the OR operation is implemented by said OR circuit are coefficient data or a bit stream, outputting said data conversion values, whereas, when said data conversion values are a branch code, updating a cell to which said cell control means furnishes said comparison instruction signal according to the branch code and also updating the register selection signal according to the branch code; and

a packing means for packing the bit stream outputted from said cell control means, which is a data conversion value, in data in units of bits.