Coded data generation or conversion – Digital code to digital code converters – To or from variable length codes
Reexamination Certificate
2002-05-10
2003-05-13
Wamsley, Patrick (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from variable length codes
C341S106000
Reexamination Certificate
active
06563441
ABSTRACT:
TECHNICAL FIELD
The present invention relates to the automatic generation of a program that may be used to decode encoded information that contains variable-length codes.
BACKGROUND ART
Data compression techniques are used in a wide range of applications to reduce the capacity requirements of text, audio, video, and other forms of source data. Some data compression techniques use so called entropy coding like Huffman coding or Shannon-Fano coding to reduce capacity requirements by encoding segments or symbols of source data into variable-length codes. Shorter codes are associated with symbols of source data that occur more frequently. Longer codes are associated with symbols that occur less frequently.
Any process or apparatus that is expected to successfully decode the variable-length codes requires information that establishes an association between each symbol of source data and the corresponding variable-length code. This association for many compression techniques can often be represented by a binary tree structure with a root node and two or more other nodes that are connected by branches in such a way that each of the other nodes is a child node that connects to only one parent node, each parent node connects to at most two child nodes, and the branches that connect a parent node and its child nodes are assigned one of two binary values, zero or one. Each node in the tree has a depth, which is the number of branches that must be crossed or “traversed” to travel from the root node to that particular node. The root node has a depth equal to zero. A node that is an immediate child of the root node has a depth equal to one.
A node that does not connect to any child node is a leaf node that represents a symbol of source data. The variable-length code associated with the symbol for a particular leaf node corresponds to a sequence of bits equal to the binary values of the branches that are encountered along a path from the root node to the particular leaf node. The bit length of a variable-length code is equal to the depth of the leaf node with which it is associated.
The association between a particular set of symbols of source data and a set of corresponding variable-length codes is referred to herein as a “coding scheme.” Different applications will generally use different coding schemes because the frequency of occurrence of source data symbols generally varies from one application to another. The amount of compression that can be achieved by entropy coding techniques depends on correctly associating shorter length codes with more frequently occurring symbols.
Decoding apparatuses are often implemented by digital processors that execute one or more programs of instructions. If the association between a symbol of source data and the corresponding variable-length codes can be represented by a binary tree, then decoding may be performed by a general purpose decoding program that is capable of adapting its decoding process to different coding schemes. The decoding process is controlled by a data structure that represents a particular binary tree including the symbols associated with each leaf node. This general purpose program receives encoded information as a serial stream of input bits, crosses or “traverses” one branch of the binary tree data structure for each received bit until reaching a leaf node, generates the symbol associated with that leaf node as the decoded output, and continues the decoding process by crossing or “traversing” branches in the binary tree starting at the root node for the next input bit. The general purpose decoding program is not very efficient because of the processing that is required to traverse branches in the binary tree.
A program that is specific to a particular coding scheme is more efficient. Unfortunately, a programmer is required to write a different program for each coding scheme. The programming process is time consuming and error prone.
DISCLOSURE OF INVENTION
It is an object of the present invention to provide for the automatic generation of program logic that can be used to decode variable-length codes from essentially any coding scheme that can be represented by a binary tree.
According to one aspect of the present invention, an apparatus with processing circuitry performs a process that generates a program of instructions to be used to decode encoded information having variable-length codes. The process obtains data that describes the association between source symbols and variable-length codes for a particular coding scheme, generates a binary tree that represents these associations in the coding scheme, processes the binary tree to generate a lookup table to decode variable-length codes having a length less than or equal to a threshold length, and processes the binary tree and the lookup table to generate a program having logic to decode variable-length codes having a length longer than the threshold length. In another aspect, the process is expressed as a program of instructions conveyed by a medium that is readable by a device.
The various features of the present invention and its preferred embodiments may be better understood by referring to the following discussion and the accompanying drawings in which like reference numerals refer to like elements in the several figures. The contents of the following discussion and the drawings are set forth as examples only and should not be understood to represent limitations upon the scope of the present invention.
REFERENCES:
patent: 4535320 (1985-08-01), Weaver
patent: 4853696 (1989-08-01), Mukherjee
patent: 5202986 (1993-04-01), Nickel
patent: 5436626 (1995-07-01), Fujiwara et al.
patent: 5694127 (1997-12-01), Tayama
patent: 5821887 (1998-10-01), Zhu
patent: 5870039 (1999-02-01), Imanishi et al.
patent: 5915041 (1999-06-01), Thielens
patent: 6188797 (2001-02-01), Moledina et al.
patent: 6219457 (2001-04-01), Potu
patent: 6307489 (2001-10-01), Freking et al.
patent: 6313766 (2001-11-01), Langendorf et al.
Gabrik Michael T.
Seiko Epson Corporation
Wamsley Patrick
LandOfFree
Automatic generation of program logic to decode... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Automatic generation of program logic to decode..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Automatic generation of program logic to decode... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3092969