Low complexity optimal parallel Huffman encoder and decoder

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.

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.

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.