High throughput polar ecc decoding via compressed successive cancellation algorithm

A storage device, comprising:

• a memory configured to store a plurality of values, wherein each value of the plurality of values is within a range, and wherein the range is not a power of 2;
• a buffer;
• and
• at least one processor configured to:
• select a codeword length, wherein the codeword length is selected based on the range;
• determine a plurality of combinations of bit chunk lengths, wherein a number of the plurality of combinations is based on a number of power-of-2 components of the range;
• assign a plurality of prefixes to the plurality of combinations, wherein for each combination, a sum of the bit chunk lengths included in the each combination and a length of a corresponding prefix assigned to the each combination is less than the codeword length;
• store the assigned plurality of prefixes in a table;
• group the plurality of values into a codeword having the codeword length;
• obtain a plurality of bit chunks, wherein each bit chunk of the plurality of bit chunks represents a corresponding value of the plurality of values, and wherein a length of the each bit chunk is selected from among the bit chunk lengths;
• select a prefix corresponding to the plurality of bit chunks based on the table;
• obtain a compressed codeword including the prefix and the plurality of bit chunks;
• and
• store the compressed codeword in the buffer.

A method of controlling a storage system, the method being executed by at least one processor and comprising:

• obtaining, from a storage, a plurality of encoded values, wherein each value of the plurality of encoded values has a predetermined value length and is within a predetermined range, and wherein the predetermined range is not a power of 2;
• grouping the plurality of encoded values into a codeword;
• obtaining a plurality of bit chunks, wherein each bit chunk of the plurality of bit chunks represents a corresponding encoded value of the plurality of encoded values, and wherein a length of the each bit chunk is selected from among one or more predetermined bit chunk lengths which are determined based on the predetermined range;
• selecting a variable-length prefix from among a plurality of variable-length prefixes, wherein the variable-length prefix indicates bit chunk lengths of the plurality of bit chunks;
• obtaining a compressed codeword including the variable-length prefix and the plurality of bit chunks;
• and
• decoding the plurality of encoded values based on the compressed codeword.

A method of controlling a storage device, the method comprising:

• obtaining, from a memory, a plurality of values, wherein each value of the plurality of values is within a range, and wherein the range is not a power of 2;
• selecting a codeword length, wherein the codeword length is selected based on the range;
• determining a plurality of combinations of bit chunk lengths, wherein a number of the plurality of combinations is based on a number of power-of-2 components of the range;
• assigning a plurality of prefixes to the plurality of combinations, wherein for each combination, a sum of the bit chunk lengths included in the each combination and a length of a corresponding prefix assigned to the each combination is less than the codeword length;
• and storing the assigned plurality of prefixes in a table;
• grouping the plurality of values into a codeword having the codeword length;
• obtaining a plurality of bit chunks, wherein each bit chunk of the plurality of bit chunks represents a corresponding value of the plurality of values, and wherein a length of the each bit chunk is selected from among the bit chunk lengths;
• selecting a prefix corresponding to the plurality of bit chunks based on the table;
• obtaining a compressed codeword including the prefix and the plurality of bit chunks;
• and
• storing the compressed codeword in a buffer.