Table device, variable length coding apparatus, variable length decoding apparatus, and variable length coding and decoding apparatus

• US 8,291,150 B2
• Filed: 05/09/2007
• Issued: 10/16/2012
• Est. Priority Date: 01/19/2007
• Status: Active Grant

• Current Assignee: Mitsubishi Electric Corporation
• Original Assignee: Mitsubishi Electric Corporation
• Inventors: El, Tomomi, Minegishi, Noriyuki
• Primary Examiner(s): Ly, Cheyne
• Application Number:
  US12/515,841
• Publication Number:
  US 20100057810A1
• Time in Patent Office: 1,987 Days
• Field of Search: 341/50, 341/51, 341/67, 707/797, 707/914, 711/1, 711/6, 711/202
• US Class Current: 711/6
• 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 configured to hold a conversion table including data conversion values indicating a branch code and a result of variable length coding or a result of variable length decoding, where the data conversion values are constructed in a form of a search tree, and where the branch code indicates information on a child node connected with a branch node in the search tree;

a plurality of cells to which nodes of the search tree indicated by the conversion table in the configuration memory are assigned by mapping, to each of which a specific comparison object value is assigned, and each of which is configured to compare said comparison object value with input data when receiving a comparison instruction signal, and output a matching signal when said comparison object value matches said input data;

a cell number output unit configured to output a cell number indicating a cell which is included in said plurality of cells and which outputs the matching signal;

a node specifying unit configured to specify a node corresponding to the cell number outputted from said cell number output unit from among nodes assigned to the plurality of cells; and

a cell control unit configured to acquire a data conversion value assigned to the node specified by said node specifying unit from the conversion table in said configuration memory, output the acquired data conversion value to outside said table device when said data conversion value is data showing a result of variable length coding or a result of variable length decoding, and, when said data conversion value is a branch code of the search tree, output another comparison instruction signal to a cell to which a child node indicated by said branch code is assigned.

2. The table device according to claim 1, wherein

the plurality of cells are grouped into cell groups according to a comparison object value having a same number of bits, and

the cell control unit outputs a same comparison instruction signal to each of cells belonging to a same cell group.

3. The table device according to claim 1, wherein

the cell control unit outputs a table number showing a conversion table to be used, and

the node specifying unit implements said specification of the node by using nodes of the search tree indicated by the conversion table shown by the table number outputted from said cell control unit.

4. A variable length coding apparatus comprising:

a coefficient data storing unit configured to store coefficient data to be variable length coded;

a conversion table output unit configured to output a conversion table including data conversion values indicating a branch code and a result of variable length coding, where the data conversion values are constructed in a form of a search tree, and where the branch code indicates information on a child node connected with a branch node in the search tree;

a configuration memory configured to hold the conversion table outputted from said conversion table output unit;

a plurality of cells to which nodes of the search tree indicated by the conversion table in the configuration memory are assigned by mapping, to each of which a specific comparison object value is assigned, and each of which is configured to compare said comparison object value with the coefficient data stored in said coefficient data storing unit when receiving a comparison instruction signal, and output a matching signal when said comparison object value matches said coefficient data;

a cell number output unit configured to output a cell number showing a cell which is included in said plurality of cells and which outputs the matching signal;

a node specifying unit configured to specify a node corresponding to the cell number outputted from said cell number output unit from among nodes assigned to the plurality of cells;

a cell control unit configured to acquire a data conversion value assigned to the node specified by said node specifying unit from the conversion table in said configuration memory, output the acquired data conversion value when said data conversion value is a bit stream, and, when said data conversion value is a branch code of said search tree, output another comparison instruction signal to a cell to which a child node indicated by said branch code is assigned; and

a packing unit configured to pack the bit stream outputted from said cell control unit in data in units of bits.

5. A variable length decoding apparatus comprising:

a bit stream storing unit configured to store a bit stream to be variable length decoded;

a bit stream output unit configured to read the bit stream from said bit stream storing unit in units of bits, and output a bit stream having a fixed length by using the read bit stream;

a conversion table output unit configured to output a conversion table including data conversion values indicating a branch code and a result of variable length decoding, where the data conversion values are constructed in a form of a search tree, and where the branch code indicates information on a child node connected with a branch node in the search tree;

a configuration memory configured to hold the conversion table outputted from said conversion table output unit;

a plurality of cells to which nodes of the search tree indicated by the conversion table in the configuration memory are assigned by mapping, to each of which a specific comparison object value is assigned, and each of which is configured to compare said comparison object value with the bit stream outputted from said bit stream output unit when receiving a comparison instruction signal, and output a matching signal when said comparison object value matches said bit stream;

a cell number output unit configured to output a cell number showing a cell which is included in said plurality of cells and which outputs the matching signal;

a node specifying unit configured to specify a node corresponding to the cell number outputted from said cell number output unit from among nodes assigned to the plurality of cells; and

a cell control unit configured to acquire a data conversion value assigned to the node specified by said node specifying unit from the conversion table in said configuration memory, output the acquired data conversion value when said data conversion value is coefficient data, and, when said data conversion value is a branch code of said search tree, output another comparison instruction signal to a cell to which a child node indicated by said branch code is assigned.

6. A variable length coding and decoding apparatus comprising:

a coefficient data storing unit configured to store coefficient data to be variable length coded;

a bit stream storing unit configured to store a bit stream to be variable length decoded;

a bit stream output unit configured to read the bit stream from said bit stream storing unit in units of bits, and output a bit stream having a fixed length by using the read bit stream;

a conversion table output unit configured to output a conversion table including data conversion values indicating a branch code and a result of variable length coding or a result of variable length decoding, where the data conversion values are constructed in a form of a search tree, and where the branch code indicates information on a child node connected with a branch node in the search tree;

a configuration memory configured to hold the conversion table outputted from said conversion table output unit;

a plurality of cells to which nodes of the search tree indicated by the conversion table in the configuration memory are assigned by mapping, to each of which a specific comparison object value is assigned, and each of which is configured to compare said comparison object value with said coefficient data or said bit stream unit when receiving a comparison instruction signal, and output a matching signal when said comparison object value matches said coefficient data or said bit stream;

a cell number output unit configured to output a cell number showing a cell which is included in said plurality of cells and which outputs the matching signal;

a node specifying unit configured to specify a node corresponding to the cell number outputted from said cell number output unit from among nodes assigned to the plurality of cells;

a cell control unit configured to acquire a data conversion value assigned to the node specified by said node specifying unit from the conversion table in said configuration memory, output the acquired data conversion value when said data conversion value is a bit stream or coefficient data, and, when said data conversion value is a branch code of said search tree, output another comparison instruction signal to a cell to which a child node indicated by said branch code is assigned; and

a packing unit configured to pack the bit stream outputted from said cell control unit 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 has a comparator and a plurality of registers, where the comparator is for comparing said comparison object value with input data when receiving a comparison instruction signal, where the plurality of registers are for holding a conversion table including at least one data conversion value corresponding to said comparison object value, where each of the cells outputs a data conversion value held by one of the registers which corresponds to a register selection signal when a result of the comparison by said comparator shows that the comparison object value matches the input data, and, when the result of the comparison by said comparator shows that the comparison object value does not match the input data, each of the cells outputs a zero value as said data conversion value, where the data conversion values are constructed in a form of a search tree, and indicate a branch code and a result of variable length coding or a result of variable length decoding, where the branch code indicates information on a child node connected with a branch node in the search tree, and where nodes of the search tree are assigned to the plurality of cells by mapping;

an OR circuit configured to implement an OR operation on the data conversion values outputted from said plurality of cells; and

a cell control unit configured to output the data conversion values through the OR operation by the OR circuit to outside said table device when the data conversion values are a coded result or a decoded result, when said data conversion values are a branch code, output another comparison instruction signal to a cell to which a child node indicated by said branch code is assigned, and update the register selection signal according to the branch code, wherein

the plurality of cells are grouped into cell groups according to a comparison object value having a same number of bits, and

the cell control unit outputs a same comparison instruction signal to each of cells belonging to a same cell group.

8. The table device according to claim 7, wherein the cell control unit generates the register selection signal by using 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, outputs the generated 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, wherein each of the plurality of cells has an address decoder for writing a conversion table in the plurality of registers.

10. A variable length coding apparatus comprising:

a coefficient data storing unit configured to store coefficient data to be variable length coded;

a conversion table output unit configured to output a conversion table including data conversion values indicating a branch code and a result of variable length coding, where the data conversion values are constructed in a form of a search tree, and where the branch code indicates information on a child node connected with a branch node in the search tree;

a plurality of cells to which nodes of the search tree indicated by the conversion table are assigned by mapping, to each of which a specific comparison object value is assigned, each of which has a comparator and a plurality of registers, where the comparator is for comparing said comparison object value with input data when receiving a comparison instruction signal, where the plurality of registers are for holding said conversion table including data conversion value[s] corresponding to said comparison object value, where each of the cells outputs a data conversion value held by one of the registers which corresponds to a register selection signal when a result of the comparison by said comparator shows that the comparison object value matches the input data, and, when the result of the comparison by said comparator shows that the comparison object value does not match the input data, each of the cells outputs a zero value as said data conversion value, where the data conversion values indicate a branch code and a result of variable length coding, where the branch code indicates information on a child node connected with a branch node in the search tree;

an OR circuit configured to implement an OR operation on the data conversion values outputted from said plurality of cells;

a cell control unit configured to output the data conversion values through the OR operation by the OR circuit to outside said table device when the data conversion values are a bit stream, when said data conversion values are a branch code, output another comparison instruction signal to a cell to which a child node indicated by said branch code is assigned, and update the register selection signal according to the branch code; and

a packing unit configured to pack the bit stream outputted from said cell control unit in data in units of bits, wherein

the plurality of cells are grouped into cell groups according to a comparison object value having a same number of bits, and

the cell control unit outputs a same comparison instruction signal to each of cells belonging to a same cell group.

11. A variable length decoding apparatus comprising:

a bit stream storing unit configured to store a bit stream to be variable length decoded;

a bit stream output unit configured to read the bit stream from said bit stream storing unit in units of bits, and output a bit stream having a fixed length by using the read bit stream;

a conversion table output unit configured to output a conversion table including data conversion values indicating a branch code and a result of variable length decoding, where the data conversion values are constructed in a form of a search tree, and where the branch code indicates information on a child node connected with a branch node in the search tree;

a plurality of cells to which nodes of the search tree indicated by the conversion table in the configuration memory are assigned by mapping, to each of which a specific comparison object value is assigned, each of which has a comparator and a plurality of registers, where the comparator is for comparing said comparison object value with the bit stream outputted from said bit stream output unit when receiving a comparison instruction signal, where the plurality of registers are for holding said conversion table including a data conversion value corresponding to said comparison object value, where each of the cells outputs a data conversion value held by one of the registers which corresponds to a register selection signal when a result of the comparison by said comparator shows that the comparison object value matches the bit stream, and, when the result of the comparison by said comparator shows that the comparison object value does not match the bit stream, each of the cells outputs a zero value as said data conversion value, where the data conversion values indicate a branch code and a result of variable length decoding, where the branch code indicates information on a child node connected with a branch node in the search tree;

an OR circuit configured to implement an OR operation on the data conversion values outputted from said plurality of cells; and

a cell control unit configured to output the data conversion values through the OR operation by the OR circuit to outside said table device when the data conversion values are coefficient data, when said data conversion values are a branch code, output another comparison instruction signal to a cell to which a child node indicated by said branch code is assigned and update the register selection signal according to the branch code, wherein

the plurality of cells are grouped into cell groups according to a comparison object value having a same number of bits, and

the cell control unit outputs a same comparison instruction signal to each of cells belonging to a same cell group.

12. A variable length coding and decoding apparatus comprising:

a coefficient data storing unit configured to store coefficient data to be variable length coded;

a bit stream storing unit configured to store a bit stream to be variable length decoded;

a bit stream output unit configured to read the bit stream from said bit stream storing unit in units of bits, and output a bit stream having a fixed length by using the read bit stream;

a conversion table output unit configured to output 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 which nodes of the search tree indicated by the conversion table are assigned by mapping, to each of which a specific comparison object value is assigned, each of which includes a comparator and a plurality of registers, where the comparator is for comparing said comparison object value with said coefficient data or said bit stream when receiving a comparison instruction signal, where the plurality of registers for holding said conversion table including at least one data conversion value corresponding to said comparison object value, where each of cells outputs a data conversion value held by one of the registers which corresponds to a register selection signal when a result of the comparison by said comparator shows that the comparison object value matches the coefficient data or the bit stream, and, 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, each of the cells outputs a zero value as said data conversion value, where the data conversion values indicate a branch code and a result of variable length coding or a result of variable length decoding, where the branch code indicates information on a child node connected with a branch node in the search tree;

an OR circuit configured to implement an OR operation on the data conversion values outputted from said plurality of cells;

a cell control unit configured to output the data conversion values through the OR operation by the OR circuit to outside said table device when the data conversion values are coefficient data or a bit stream, when said data conversion values are a branch code, output another comparison instruction signal to a cell to which a child node indicated by said branch code is assigned, and update the register selection signal according to the branch code; and

a packing unit configured to pack the bit stream outputted from said cell control unit in data in units of bits, wherein

the plurality of cells are grouped into cell groups according to a comparison object value having a same number of bits, and

the cell control unit outputs a same comparison instruction signal to each of cells belonging to a same cell group.