# US 12,113,554 B2 · Low complexity optimal parallel Huffman encoder and decoder

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 12,113,554 B2
- Document ID: US12113554B2
- Status: Granted
- Kind: B2
- Application number: 17/939,643
- Filed: 2022-09-07
- Published: 2024-01-18
- Granted: 2024-10-08
- Earliest claimed: 2022-07-12
- Assignees: Samsung Display Co., Ltd.
- Applicants: Samsung Display Co., Ltd.
- Inventors: Gregory William Cook
- Web page: https://patentgrep.com/patent/US12113554B2

## CPC

- H03M 7/4093: {Variable length to variable length coding}
- H03M 7/3079: {Context modeling}
- H03M 7/40: Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
- H03M 7/405: {Tree adaptation}
- H03M 7/4062: {Coding table adaptation}
- H03M 7/42: using table look-up for the coding or decoding process, e.g. using read-only memory {(H03M7/4006 takes precedence)}
- H03M 7/6017: {Methods or arrangements to increase the throughput}
- H03M 7/6023: {Parallelization}
- G06F 2212/401: Compressed data
- 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)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A memory device includes a memory; and at least one processor configured to: obtain a symbol stream including a plurality of symbols; determine a Huffman tree corresponding to the symbol stream, wherein each symbol of the plurality of symbols is assigned a corresponding prefix code from among a plurality of prefix codes based on the Huffman tree; generate a prefix length table based on the Huffman tree, wherein the prefix length table indicates a length of the corresponding prefix code for each symbol; generate a logarithm frequency table based on the prefix length table, wherein the logarithm frequency table indicates a logarithm of a frequency count for each symbol, generate a cumulative frequency table which indicates a cumulative frequency count corresponding to each symbol; generate a compressed bitstream by iteratively applying an encoding function to the plurality of symbols based on the logarithm frequency table and the cumulative frequency table; and store the compressed bitstream in the memory.

## Claims

### Claim 1

A memory device, comprising:
a memory; and
at least one processor configured to:
obtain a symbol stream comprising a plurality of symbols,
determine a Huffman tree corresponding to the symbol stream, wherein each symbol of the plurality of symbols is assigned a corresponding prefix code from among a plurality of prefix codes based on the Huffman tree,
generate a prefix length table based on the Huffman tree, wherein the prefix length table indicates a length of the corresponding prefix code for each symbol,
generate a logarithm frequency table based on the prefix length table, wherein the logarithm frequency table indicates a logarithm of a frequency count for each symbol,
generate a cumulative frequency table which indicates a cumulative frequency count corresponding to each symbol,
generate a compressed bitstream by iteratively applying an encoding function to the plurality of symbols based on the logarithm frequency table and the cumulative frequency table, and
store the compressed bitstream in the memory.

### Claim 2 (depends on 1)

The memory device of claim 1, wherein, to generate the logarithm frequency table, the at least one processor is further configured to subtract the length of the corresponding prefix code for each symbol from a maximum length of the plurality of prefix codes.

### Claim 3 (depends on 1)

The memory device of claim 1, wherein, to generate the cumulative frequency table, the at least one processor is further configured to:
obtain the frequency count of each symbol by left shifting an integer value of 1 based on the logarithm of the frequency count for each symbol, and
obtain the cumulative frequency count for each symbol by adding the frequency count of each symbol to a sum of frequency counts of previous symbols of the plurality of symbols.

### Claim 4 (depends on 3)

The memory device of claim 3, wherein, to apply the encoding function to each symbol, the at least one processor is further configured to:
obtain a current state value,
obtain a shifted state value by right shifting the current state value based on the logarithm of the frequency count for each symbol,
obtain a first value by left shifting the shifted state value based on a maximum length of the plurality of prefix codes,
obtain the frequency count for each symbol by left shifting an integer value of 1 based on the logarithm of the frequency count,
obtain a second value by performing a bitwise AND operation on the current state value and the frequency count for each symbol minus 1, and
obtain an updated state value by adding the first value, the second value, and the cumulative frequency count corresponding to each symbol.

### Claim 5 (depends on 4)

The memory device of claim 4, wherein, to apply the encoding function to each symbol, the at least one processor is further configured to:
determine whether a difference between a most significant set bit of an initial state value corresponding to the symbol stream and the logarithm of the frequency count corresponding to each symbol is greater than or equal to a minimum bit length of a codeword corresponding to the symbol stream, and
based on determining that the difference is greater than or equal to the minimum bit length of the codeword:
determine a third value by subtracting the logarithm of the frequency count for each symbol from the most significant set bit,
obtain a shifted third value by right shifting the third value based on a logarithm of the minimum bit length of the codeword,
determine a number of bits to be transferred out of the initial state value by left shifting the shifted third value based on the logarithm of the minimum bit length of the codeword,
output the determined number of bits to the compressed bitstream, and
obtain the current state value by right shifting the initial state value based on the determined number of bits.

### Claim 6 (depends on 5)

The memory device of claim 5, wherein the at least one processor comprises a plurality of processors configured to perform the encoding function in parallel for the plurality of symbols,
wherein, to perform the encoding function, each processor of the plurality of processors is assigned a corresponding initial state value,
wherein after each processor determines the number of bits to be transferred from the corresponding initial state value, each processor is assigned a corresponding memory location to output the determined number of bits, and
wherein after the determined number of bits are output to the compressed bitstream, each processor is further configured to determine a corresponding current state value.

### Claim 7

A memory device, comprising:
a memory; and
at least one processor configured to:
obtain a compressed bitstream from the memory, wherein the compressed bitstream corresponds to a symbol stream comprising a plurality of symbols,
obtain a logarithm frequency table from the compressed bitstream, wherein the logarithm frequency table indicates a logarithm of a frequency count for each symbol of the plurality of symbols,
generate a cumulative frequency table based on the logarithm frequency table, wherein the cumulative frequency table indicates a cumulative frequency count corresponding to each symbol,
generate an inverse symbol table based on the logarithm frequency table and the cumulative frequency table, and
generate the symbol stream by iteratively applying a decoding function to the plurality of symbols based on the cumulative frequency table and the inverse symbol table.

### Claim 8 (depends on 7)

The memory device of claim 7, wherein, to generate the cumulative frequency table, the at least one processor is further configured to:
obtain the frequency count of each symbol by left shifting an integer value of 1 based on the logarithm of the frequency count for each symbol, and
obtain the cumulative frequency count for each symbol by adding the frequency count of each symbol to a sum of frequency counts of previous symbols of the plurality of symbols.

### Claim 9 (depends on 7)

The memory device of claim 7, wherein to generate the inverse symbol table, the at least one processor is further configured to determine, for each symbol, an inverse symbol value by performing a bitwise AND operation on a current state value and a maximum length of a plurality of prefix codes corresponding to the compressed bitstream minus 1,
wherein the inverse symbol value is greater than or equal to the cumulative frequency count of each symbol, and
wherein the inverse symbol value is less than a cumulative frequency count of a next symbol.

### Claim 10 (depends on 9)

The memory device of claim 9, wherein, to apply the decoding function to each symbol, the at least one processor is further configured to:
obtain each symbol based on the inverse symbol value corresponding to each symbol from the inverse symbol table,
obtain a shifted state value by right shifting the current state value based on the maximum length of the plurality of prefix codes,
obtain a first value by left shifting the shifted state value based on the logarithm of the frequency count for each symbol,
obtain a total frequency count by left shifting an integer value of 1 based on the maximum length of the plurality of prefix codes,
obtain a second value by performing a bitwise AND operation on the current state value and the maximum length of the plurality of prefix codes minus 1, and
obtain an updated state value by subtracting the cumulative frequency count corresponding to each symbol from a sum of the second value and the inverse symbol value.

### Claim 11 (depends on 10)

The memory device of claim 10, wherein, to apply the decoding function to each symbol, the at least one processor is further configured to:
determine a difference between the maximum length of the plurality of prefix codes and a most significant set bit of an initial state value corresponding to the compressed bitstream is greater than 0, and
based on determining that the difference is greater than 0:
obtain a third value by left shifting an integer value of 1 based on a logarithm of a minimum bit length of a codeword corresponding to the symbol stream,
obtain a fourth value by adding the difference to the third value minus 1,
obtain a shifted fourth value by right shifting the fourth value based on the logarithm of the minimum bit length of the codeword,
determine a number of bits to be transferred into the initial state value by left shifting the shifted fourth value based on the logarithm of the minimum bit length of the codeword,
obtain additional bits from the compressed bitstream based on the determined number of bits; and
obtain a shifted state value by left shifting the initial state value based on the determined number of bits, and
obtain the current state value by adding the shifted state value and the additional bits.

### Claim 12 (depends on 11)

The memory device of claim 11, wherein the at least one processor comprises a plurality of processors configured to perform the decoding function in parallel for the plurality of symbols,
wherein, to perform the decoding function, each processor of the plurality of processors is assigned a corresponding initial state value,
wherein after each processor determines the number of bits to be transferred into the corresponding initial state value, each processor is assigned a corresponding memory location from which to obtain the additional bits, and
wherein after the additional bits are obtained from the compressed bitstream, each processor is further configured to determine a corresponding current state value.

### Claim 13

A method of compressing a symbol stream for storage in a memory device, the method being performed by at least one processor and comprising:
obtaining the symbol stream comprising a plurality of symbols;
determining a Huffman tree corresponding to the symbol stream, wherein each symbol of the plurality of symbols is assigned a corresponding prefix code from among a plurality of prefix codes based on the Huffman tree;
generating a prefix length table based on the Huffman tree, wherein the prefix length table indicates a length of the corresponding prefix code for each symbol;
generating a logarithm frequency table based on the prefix length table, wherein the logarithm frequency table indicates a logarithm of a frequency count for each symbol;
generating a cumulative frequency table which indicates a cumulative frequency count corresponding to each symbol;
generating a compressed bitstream by iteratively applying an encoding function to the plurality of symbols based on the prefix length table and the cumulative frequency table; and
storing the compressed bitstream in the memory device.

### Claim 14 (depends on 13)

The method of claim 13, wherein the generating of the logarithm frequency table comprises subtracting the length of the corresponding prefix code for each symbol from a maximum length of the plurality of prefix codes.

### Claim 15 (depends on 13)

The method of claim 13, wherein the generating of the cumulative frequency table comprises:
obtaining the frequency count of each symbol by left shifting an integer value of 1 based on the logarithm of the frequency count for each symbol; and
obtaining the cumulative frequency count for each symbol by adding the frequency count of each symbol to a sum of frequency counts of previous symbols of the plurality of symbols.

### Claim 16 (depends on 15)

The method of claim 15, wherein the applying of the encoding function to each symbol comprises:
obtaining a current state value;
obtaining a shifted state value by right shifting the current state value based on the logarithm of the frequency count for each symbol;
obtaining a first value by left shifting the shifted state value based on the maximum length of the plurality of prefix codes;
obtaining the frequency count for each symbol by left shifting an integer value of 1 based on the logarithm of the frequency count;
obtaining a second value by performing a bitwise AND operation on the current state value and the frequency count for each symbol minus 1; and
obtaining an updated state by adding the first value, the second value, and the cumulative frequency count corresponding to each symbol.

### Claim 17 (depends on 16)

The method of claim 16, wherein the applying of the encoding function to each symbol further comprises:
determining whether a difference between a most significant set bit of an initial state value corresponding to the symbol stream and the logarithm of the frequency count corresponding to each symbol is greater than or equal to a minimum bit length of a codeword corresponding to the symbol stream; and
based on determining that the difference is greater than or equal to the minimum bit length of the codeword:
determining a third value by subtracting the logarithm of the frequency count for each symbol from the most significant set bit;
obtaining a shifted third value by right shifting the third value based on a logarithm of the minimum bit length of the codeword;
determining a number bits to be transferred out of the initial state value by left shifting the shifted third value based on the logarithm of the minimum bit length of the codeword;
outputting the determined number of bits to the compressed bitstream; and
obtaining the current state value by right shifting the initial state value based on the determined number of bits.

### Claim 18 (depends on 17)

The method of claim 17, wherein the at least one processor comprises a plurality of processors,
wherein the encoding function is applied in parallel by the plurality of processors for the plurality of symbols,
wherein, to perform the encoding function, each processor of the plurality of processors is assigned a corresponding initial state value,
wherein after each processor determines the number of bits to be transferred from the corresponding initial state value, each processor is assigned a corresponding memory location to output the determined number of bits, and
wherein after the determined number of bits are output to the compressed bitstream, the method further comprises determining a corresponding current state value for each processor.

### Claim 19

A method of generating a symbol stream based on a compressed bitstream, the method being performed by at least one processor and comprising:
obtaining the compressed bitstream from a memory, wherein the compressed bitstream corresponds to a plurality of symbols included in the symbol stream;
obtaining a logarithm frequency table from the compressed bitstream, wherein the logarithm frequency table indicates a logarithm of a frequency count for each symbol of the plurality of symbols;
generating a cumulative frequency table based on the logarithm frequency table, wherein the cumulative frequency table indicates a cumulative frequency count corresponding to each symbol;
generating an inverse symbol table based on the logarithm frequency table and the cumulative frequency table; and
generating the symbol stream by iteratively applying a decoding function to the plurality of symbols based on the cumulative frequency table and the inverse symbol table.

### Claim 20 (depends on 19)

The method of claim 19, wherein the generating of the cumulative frequency table comprises:
obtaining the frequency count of each symbol by left shifting an integer value of 1 based on the logarithm of the frequency count for each symbol; and
obtaining the cumulative frequency count for each symbol by adding the frequency count of each symbol to a sum of frequency counts of previous symbols of the plurality of symbols.

### Claim 21 (depends on 19)

The method of claim 19, wherein the generating of the inverse symbol table further comprises determining, for each symbol, an inverse symbol value by performing a bitwise AND operation on a current state value and a maximum length of a plurality of prefix codes corresponding to the compressed bitstream minus 1,
wherein the inverse symbol value is greater than or equal to the cumulative frequency count of each symbol, and
wherein the inverse symbol value is less than a cumulative frequency count of a next symbol.

### Claim 22 (depends on 21)

The method of claim 21, wherein the applying of the decoding function to each symbol comprises:
obtaining each symbol based on the inverse symbol value corresponding to each symbol from the inverse symbol table;
obtaining a shifted state value by right shifting the current state value based on the maximum length of the plurality of prefix codes;
obtaining a first value by left shifting the shifted state value based on the logarithm of the frequency count for each symbol;
obtaining a total frequency count by left shifting an integer value of 1 based on the maximum length of the plurality of prefix codes;
obtaining a second value by performing a bitwise AND operation on the current state value and the maximum length of the plurality of prefix codes minus 1; and
obtaining an updated state value by subtracting the cumulative frequency count corresponding to each symbol from a sum of the second value and the inverse symbol value.

### Claim 23 (depends on 22)

The method of claim 22, wherein the applying of the decoding function to each symbol further comprises:
determining whether a difference between the maximum length of the plurality of prefix codes and a most significant set bit of an initial state value corresponding to the compressed bitstream is greater than 0;
based on determining that the difference is greater than 0:
obtaining a third value by left shifting an integer value of 1 based on a logarithm of a minimum bit length of a codeword corresponding to the symbol stream;
obtaining a fourth value by adding the difference to the third value minus 1;
obtaining a shifted fourth value by right shifting the third value based on the logarithm of the minimum bit length of the codeword,
determining a number of bits to be transferred into the initial state value by left shifting the shifted fourth value based on the logarithm of the minimum bit length of the codeword;
obtaining additional bits from the compressed bitstream based on the determined number of bits;
obtaining a shifted state value by left shifting the initial state value based on the determined number of bits; and
obtaining the current state value by adding the shifted state value and the additional bits.

### Claim 24 (depends on 23)

The method of claim 23, wherein the at least one processor includes a plurality of processors,
wherein the decoding function is applied in parallel by the plurality of processors for the plurality of symbols,
wherein, to perform the decoding function, each processor of the plurality of processors is assigned a corresponding initial state value,
wherein after each processor determines the number of bits to be transferred into the corresponding initial state value, each processor is assigned a corresponding memory location from which to obtain the additional bits, and
wherein after the additional bits are obtained from the compressed bitstream, the method further comprises determining a corresponding current state value for each processor.