# US 12,119,843 B2 · 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,119,843 B2 - Document ID: US12119843B2 - Status: Granted - Kind: B2 - Application number: 18/178,437 - Filed: 2023-03-03 - Published: 2023-12-21 - Granted: 2024-10-15 - Earliest claimed: 2022-06-17 - Assignees: Kioxia Corporation - Applicants: Kioxia Corporation - Inventors: Takashi Takemoto - Web page: https://patentgrep.com/patent/US12119843B2 ## CPC - H03M 7/30: Compression (speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N); Expansion; Suppression of unnecessary data, e.g. redundancy reduction - H03M 7/40: Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code - G06F 3/0608: {Saving storage space on storage systems} - G06F 3/064: {Management of blocks} - G06F 3/0679: {Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]} - H03M 7/3079: {Context modeling} - 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 An entropy code encoder includes a register and first, second, third, and fourth arithmetic circuits. The first arithmetic circuit is configured to output, based on an input symbol, a first value corresponding to an appearance frequency of the input symbol and a second value corresponding to a cumulative distribution of the first value. The second arithmetic circuit is configured to output a third value corresponding to division of a value of bits in the register by the first value. The third arithmetic circuit is configured to output a fourth value obtained by adding the second value to a bit-shifted value of the third value, to update a value in the register. The fourth arithmetic circuit is configured to compare the value of upper bits in the register and the first value and output a value of lower bits in the register as a compressed data stream. ## Claims ### Claim 1 An entropy code encoder comprising: a register; a first arithmetic circuit configured to output, based on an input symbol to be compressed, a first value corresponding to an appearance frequency of the input symbol and a second value corresponding to a cumulative distribution of the first value; a second arithmetic circuit configured to output a third value corresponding to division of a value of bits stored in the register by the first value; a third arithmetic circuit configured to output a fourth value obtained by adding the second value to a bit-shifted value of the third value to the register, to update a value of bits stored in the register to the fourth value; and a fourth arithmetic circuit configured to compare a value of upper bits stored in the register and the first value and output a value of lower bits stored in the register as a compressed data stream in accordance with a comparison result. ### Claim 2 (depends on 1) The entropy code encoder according to claim 1, wherein the first arithmetic circuit includes a first table storing cumulative distribution values corresponding to various values of input symbols, and obtains the second value corresponding to the input symbol by referring to the first table. ### Claim 3 (depends on 2) The entropy code encoder according to claim 2, wherein the first arithmetic circuit further includes a second table storing appearance frequency values corresponding to various values of input symbols, and obtains the first value corresponding to the input symbol by referring to the second table. ### Claim 4 (depends on 3) The entropy code encoder according to claim 3, wherein the first arithmetic circuit further includes a third table storing reciprocals of appearance frequency values corresponding to various values of input symbols, and is configured to output a reciprocal of the first value corresponding to the input symbol by referring to the third table, and the second arithmetic circuit includes a multiplier circuit configured to multiply the reciprocal of the first value and the value of the bits stored in the register, to obtain the third value. ### Claim 5 (depends on 2) The entropy code encoder according to claim 2, wherein the first arithmetic circuit includes a subtractor circuit configured to calculate a difference of the second value and a second value corresponding to the input symbol plus or minus 1 and calculate the first value based on the difference. ### Claim 6 (depends on 1) The entropy code encoder according to claim 1, wherein the second arithmetic circuit includes a first divider circuit configured to divide the value of the bits stored in the register by the first value, to obtain the third value. ### Claim 7 (depends on 6) The entropy code encoder according to claim 6, wherein the second arithmetic circuit further includes a second divider circuit configured to divide the value of the bits stored in the register that have been bit-shifted by the first value, and the third arithmetic circuit is configured to output a value obtained through addition of the second value and the value of the bits stored in the register divided by the first value, as the fourth value when the value of the bits stored in the register is less than the first value, and output a value obtained through addition of the second value and the value of the bits stored in the register that have been bit-shifted divided by the first value, as the fourth value when the value of the bits stored in the register is greater than the first value. ### Claim 8 (depends on 1) The entropy code encoder according to claim 1, wherein the second arithmetic circuit includes a reciprocal calculation circuit configured to calculate a reciprocal of the first value and a multiplier circuit configured to multiply the reciprocal of the first value calculated by the reciprocal calculation circuit and the value of the bits stored in the register, to obtain the third value. ### Claim 9 (depends on 1) The entropy code encoder according to claim 1, wherein the fourth arithmetic circuit outputs the value of the lower bits stored in the register as the compressed data stream when the value of the upper bits stored in the register is greater than the first value, and does not output the value of the lower bits stored in the register when the value of the upper bits stored in the register is less than the first value. ### Claim 10 (depends on 1) The entropy code encoder according to claim 1, wherein the compressed data stream is compressed in accordance with a range variant asymmetric numeral system (rANS). ### Claim 11 (depends on 1) A memory system comprising: a non-volatile semiconductor memory; and a memory controller including the entropy code encoder according to claim 1, the memory controller configured to compress data to be written into the non-volatile semiconductor memory using the entropy code encoder. ### Claim 12 An entropy code decoder comprising: a register; a plurality of comparator circuits configured to compare cumulative distribution values corresponding to various values of data symbols with lower bits of a value stored in the register, respectively; a binary encoder circuit configured to output an output symbol as a decompressed data stream based on output values of the comparator circuits; and an arithmetic circuit configured to: obtain a first value corresponding to an appearance frequency of the output symbol and a second value corresponding to a cumulative distribution of the first value; calculate a third value through multiplication of the first value with a bit-shifted value of the value stored in the register and subtraction of the second value therefrom; and output a fourth value including at least a part of bits of the third value to update the value in the register to the fourth value. ### Claim 13 (depends on 12) The entropy code decoder according to claim 12, wherein the fourth value is the third value, when a number of bits of the third value is greater than a predetermined number, and the fourth value is a combination of a bit-shifted value of the third value, which is shifted by the predetermined number, and the predetermined number of bits of an input data stream, when the number of bits of the third value is less than the predetermined number. ### Claim 14 (depends on 12) The entropy code decoder according to claim 12, further comprising: a first table storing cumulative distribution values corresponding to various values of data symbols, wherein the arithmetic circuit obtains the second value corresponding to the output symbol by referring to the first table. ### Claim 15 (depends on 14) The entropy code decoder according to claim 14, further comprising: a second table storing appearance frequency values corresponding to various values of data symbols, and obtains the first value corresponding to the output symbol by referring to the second table. ### Claim 16 (depends on 13) The entropy code decoder according to claim 13, wherein the first arithmetic circuit includes a subtractor circuit configured to calculate a difference of the second value and a second value corresponding to the output symbol plus or minus 1 and calculate the first value based on the difference. ### Claim 17 (depends on 12) The entropy code decoder according to claim 12, wherein the decompressed data stream is decompressed in accordance with a range variant asymmetric numeral system (rANS). ### Claim 18 (depends on 12) A memory system comprising: a non-volatile semiconductor memory; and a memory controller including the entropy code decoder according to claim 12, the memory controller configured to decompress data read from the non-volatile semiconductor memory using the entropy code decoder. ### Claim 19 A compression and decompression circuit comprising: an entropy code encoder comprising: a first register; a first arithmetic circuit configured to output, based on an input symbol, a first value corresponding to an appearance frequency of the input symbol and a second value corresponding to a cumulative distribution of the first value; a second arithmetic circuit configured to output a third value corresponding to division of a value of bits stored in the first register by the first value; a third arithmetic circuit configured to output a fourth value obtained by adding the second value to a bit-shifted value of the third value to the register, to update a value of bits stored in the first register to the fourth value; and a fourth arithmetic circuit configured to compare a value of upper bits stored in the first register and the first value and output lower bits of the value stored in the first register as a compressed data stream in accordance with a comparison result; and an entropy code decoder a second register; a plurality of comparator circuits configured to compare cumulative distribution values corresponding to various values of data symbols with a value of lower bits stored in the second register, respectively; a binary encoder circuit configured to output an output symbol as a decompressed data stream based on output values of the comparator circuits; and an arithmetic circuit configured to: obtain a fifth value corresponding to an appearance frequency of the output symbol and a sixth value corresponding to a cumulative distribution of the first value; calculate a seventh value through multiplication of the fifth value with a bit-shifted value of the value stored in the second register and subtraction of the sixth value therefrom; and output an eighth value including at least a part of bits of the seventh value to update the value in the second register to the eighth value. ### Claim 20 (depends on 19) A memory system comprising: a non-volatile semiconductor memory; and a memory controller including the compression and decompression circuit according to claim 19, the memory controller configured to compress data to be written into the non-volatile semiconductor memory using the entropy code encoder and decompress data read from the non-volatile semiconductor memory using the entropy code decoder. ### Claim 21 An entropy code decoder comprising: a register; a plurality of comparator circuits configured to compare cumulative distribution values corresponding to various even values of data symbols with a value of lower bits stored in the register, respectively; a binary encoder circuit configured to output an output symbol as at least a part of a decompressed data stream based on output values of the comparator circuits; and an arithmetic circuit configured to: obtain a first value corresponding to an appearance frequency of the output symbol and a second value corresponding to an appearance frequency of the output symbol plus 1; calculate a third value through multiplication of the first value with a bit-shifted value of the value stored in the register and subtraction of a value corresponding to a cumulative distribution of the output symbol and a fourth value through multiplication of the second value with a bit-shifted value of the value stored in the register and subtraction of a value corresponding to a cumulative distribution of the output symbol plus 1; select one of the third value and the fourth value; and output a fifth value including at least a part of bits of the selected one of the third and fourth values to update the value in the register to the fifth value.