# US 9,882,583 B2 · VLSI efficient Huffman encoding apparatus and method > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 9,882,583 B2 - Document ID: US9882583B2 - Status: Granted - Kind: B2 - Application number: 15/130,054 - Filed: 2016-04-15 - Published: 2016-08-11 - Granted: 2018-01-30 - Earliest claimed: 2014-06-09 - Assignees: Tidal Systems, Inc. - Applicants: Tidal Systems, Inc. - Inventors: Yingquan Wu; Alexander Hubris - Web page: https://patentgrep.com/patent/US9882583B2 ## CPC - H03M 7/40: Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code - H03M 7/3084: {using adaptive string matching, e.g. the Lempel-Ziv method} - H03M 7/4037: {Prefix coding} - H03M 7/4056: {Coding table selection} - H03M 7/4062: {Coding table adaptation} - H03M 7/6047: {Power optimization with respect to the encoder, decoder, storage or transmission} - H03M 7/6058: {Saving memory space in the encoder or decoder} - H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C) ## 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. ## Claims ### Claim 1 An electronic device comprising: a statistic generating module configured to process a data file and flag each literal as part of one of a plurality of literal groups of one or more non-duplicative literals and one of a plurality of copy groups of one or more literals; and wherein: the one or more literals of each literal group not being preceded in the data file by an identical group of one or more literals; the one or more literals of each copy group being preceded in the data file by an identical group of one or more literals; each copy group having both a length indicating a number of literals in the copy group and an offset to the identical group of one or more literals preceding the each copy group in the data file; and each literal group having a length indicating a number of literals in the literal group; and a Huffman coding module configured to: code a first portion of the plurality of literal groups to obtain Huffman coded literal groups, the portion of the plurality of literal groups being included in a first portion of the data file; include the Huffman coded literal groups in an output file; and include a second portion of the plurality of literal groups in a second portion of the data file in the output file without Huffman coding the second portion of the plurality of literal groups, the second portion occurring after the first portion in the data file. ### Claim 2 (depends on 1) The electronic device of claim 1, wherein the Huffman coding module is further configured to: divide the data file into the first portion and the second portion by evaluating an average number of literal groups with respect to copy groups in the first and second portions. ### Claim 3 (depends on 1) The electronic device of claim 1, wherein: the Huffman coding module is further configured to: code offsets of a plurality of copy groups to obtain Huffman coded offsets; include the Huffman coded offsets in the output file. ### Claim 4 (depends on 3) The electronic device of claim 3, further comprising a length module is configured to: separate from the Huffman coding of the offsets of the plurality of copy groups, Huffman code the lengths of the plurality of copy groups to obtain Huffman coded lengths; and include the Huffman coded lengths in the output file. ### Claim 5 (depends on 3) The electronic device of claim 3, further comprising a length module is configured to: limit a Huffman code length for the Huffman coding of the offsets and the lengths of a plurality of copy literals to N bits. ### Claim 6 (depends on 5) The electronic device of claim 5, wherein N is 8. ### Claim 7 (depends on 5) The electronic device of claim 5, wherein the length module is further configured to: for each data set of the lengths and offsets: generate a first canonical Huffman code of data words in the each data set, the first canonical Huffman coding including a code length for each data word, the code lengths being arranged in order; set all code lengths greater than N to be equal to N to obtain a second canonical Huffman code; and determine a benchmark code that is a largest code length lower than N that when incremented by one causes an overflow probability of the second canonical Huffman coding to be greater than or equal to one. ### Claim 8 (depends on 7) The electronic device of claim 7, wherein: the length module is further configured to increment an adjusted code by one to generate a third canonical Huffman code, the adjusted code having a length less than the benchmark code; and the Huffman coding module further configured to code the data file according to the third canonical Huffman coding. ### Claim 9 (depends on 5) The electronic device of claim 5, wherein the length module is further configured to: Huffman code the offsets and the lengths using a very large scale integrated (VLSI) circuit programmed to perform Huffman coding of Huffman codes of N or less. ### Claim 10 (depends on 5) The electronic device of claim 5, wherein the length module is further configured to: map lengths from 1 to M to one of 2*N bins, M being greater than 2*N.