Patent ID: 6563441
Filing Date: 2003-05-13
Classification: H03M

Abstract:
A medium readable by a device and conveying a first program of instructions executable by the device to perform a method for generating a second program of instructions to be used to decode encoded information having variable-length codes, wherein the method comprises:obtaining data that defines connections between a root node and a plurality of other nodes such that each of the other nodes is a child node that connects to one respective parent node, each parent node connects to at most two child nodes, and the connections between a parent node and its respective child nodes are associated with either of two binary values, wherein a node that does not connect to any child node is a leaf node, and obtaining data that defines a respective value for each leaf node; generating a binary tree data structure representing the root node and the other nodes with branches having binary values and connecting the nodes according to the data that defines connections, wherein each respective node has a depth equal to the number of branches that are encountered during a traverse of the binary tree from the root node to the respective node, and wherein each respective leaf node is associated with a value and a variable-length code derived from a sequence of bits equal to the binary values of the branches that are encountered during a traverse of the binary tree from the root node to the respective leaf node; and traversing the binary tree data structure to generate a first portion of the second program of instructions that includes a lookup table data structure to decode variable-length codes derived from a sequence of bits having a length less than or equal to N, where N is an integer greater than zero, and to generate a second portion of the second program on instructions that includes a static logic structure corresponding to branches in the binary tree data structure to decode variable-length codes derived from a sequence of bits having a length greater than N, wherein the lookup table data structure has a plurality of first entries and a plurality of second entries for a total number of entries less than or equal to 2N, each entry identified by a lookup key derived from a sequence of bits of length N, and wherein each first entry is identified by a lookup key that either is prefixed by or is equal to a respective variable-length code having a length M less than or equal to N, and contains information that identifies the length M and the value associated with the leaf node that is associated with the respective variable-length code, and each second entry is identified by a lookup key that is a prefix of one or more variable-length codes having lengths greater than N, and contains an indication that it does not identify a value associated with any leaf node.