VLSI efficient Huffman encoding apparatus and method
US9882583B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Apr 15, 2016 |
| Grant date | Jan 30, 2018 |
| Priority date | — |
| Expiry date | Apr 15, 2036 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH03M7/6058
- WIPO fieldBasic communication processes
- WIPO sectorElectrical engineering
Abstract
A compression algorithm based on Huffman coding is disclosed that is adapted to be readily implemented using VLSI design. A data file may be processed to replace duplicate data with a copy commands including an offset and length, such as according to the LV algorithm. A Huffman code may then be generated for parts of the file. The Huffman code may be generated according to a novel method that generates Huffman code lengths for literals in a data file without first sorting the literal statistics. The Huffman code lengths may be constrained to be no longer than a maximum length and the Huffman code may be modified to provide an acceptable overflow probability and be in canonical order. Literals, offsets, and lengths may be separately encoded. The different values for these data sets may be assigned to a limited number of bins for purpose of generating usage statistics used for generating Huffman codes.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.