# US 11,909,423 B2 · Compression circuit, storage system, and compression method > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,909,423 B2 - Document ID: US11909423B2 - Status: Granted - Kind: B2 - Application number: 17/693,606 - Filed: 2022-03-14 - Published: 2023-03-16 - Granted: 2024-02-20 - Earliest claimed: 2021-09-16 - Assignees: Kioxia Corporation - Applicants: Kioxia Corporation - Inventors: Sho Kodama; Keiri Nakanishi; Daisuke Yashima - Web page: https://patentgrep.com/patent/US11909423B2 ## CPC - H03M 7/3084: {using adaptive string matching, e.g. the Lempel-Ziv method} - H03M 7/3088: {employing the use of a dictionary, e.g. LZ78} - G06F 3/0608: {Saving storage space on storage systems} - G06F 3/0659: {Command handling arrangements, e.g. command buffers, queues, command scheduling} - G06F 3/0679: {Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]} - H03M 7/40: Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code - H03M 7/6023: {Parallelization} - H03M 7/4037: {Prefix coding} - 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 According to one embodiment, a compression circuit generates substrings from input data for (3+M) cycles, the input data being N bytes per cycle, a byte length of each substring being greater than or equal to (N×(1+M)+1); obtains a set of matches, each of the matches including at least one past input data which input past and corresponds to at least a part of each of the substrings; selects a subset of matches from the set of matches including the input data of one cycle; and outputs the subset of matches. M is zero or a natural number. N is a positive integer which is two or more. ## Claims ### Claim 1 A compression circuit, comprising: a processor configured to generate substrings from input data for (3+M) cycles, the input data being N bytes per cycle, a byte length of each substring being greater than or equal to (N×(1+M)+1); obtain a set of matches, each of the matches including at least one past input data which input past and corresponds to at least a part of each of the substrings; select a subset of matches from the set of matches including the input data of one cycle; and output the subset of matches, wherein M is zero or a natural number, and N is a positive integer which is two or more. ### Claim 2 (depends on 1) The compression circuit of claim 1, further comprising a buffer memory configured to store the input data for (3+M) cycles, and wherein the processor is configured to generate the substrings, each of the substring being at least (N×(1+M)+1) bytes of the input data stored in the buffer memory at different storing positions. ### Claim 3 (depends on 1) The compression circuit of claim 1, further comprising a ring buffer configured to store the input data, and wherein the processor is configured to search the input data stored in the ring buffer in parallel for the matches. ### Claim 4 (depends on 1) The compression circuit of claim 1, wherein the processor is configured to skip outputting of the subset of matches for (1+k) cycles from a next cycle if a last match selected most recently in a current cycle corresponds to a match for the (1+k) cycles from the next cycle, and k is equal to or less than M and is a positive integer which is zero or more. ### Claim 5 (depends on 1) The compression circuit of claim 1, wherein the processor is configured to merge sets of matches obtained for Y cycles and to output a merged set of matches once per the Y cycles, and the processor is configured to select a subset of matches corresponding to the input data of at least (N×Y) bytes from the merged set of matches, and Y is a positive integer. ### Claim 6 (depends on 1) The compression circuit of claim 1, wherein the processor is configured to generate the substrings, a byte length of each substring being N×(M+2). ### Claim 7 (depends on 1) A storage system comprising: a nonvolatile memory; and a controller configured to control data write to the nonvolatile memory and data read from the nonvolatile memory, wherein the controller comprises: the compression circuit of claim 1; and an encoder configured to encode the subset of matches, and write and encoded subset of matches to the nonvolatile memory. ### Claim 8 A compression method, comprising: generating substrings from input data for (3+M) cycles, the input data being N bytes per cycle, a byte length of each substring being greater than or equal to (N×(1+M)+1); obtaining a set of matches, each of the matches including at least one past input data which input past and corresponds to at least a part of each of the substrings; selecting a subset of matches from the set of matches including the input data of one cycle; and outputting the subset of matches, wherein M is zero or a natural number, and N is a positive integer which is two or more. ### Claim 9 (depends on 8) The compression method of claim 8, further comprising: writing the input data for (3+M) cycles to a buffer memory; and generating the substrings, each of the substring being at least (N×(1+M)+1) bytes of the input data stored in the buffer memory at different storing positions. ### Claim 10 (depends on 8) The compression method of claim 8, further comprising: writing the input data to a ring buffer; and searching the input data stored in the ring buffer in parallel for the matches. ### Claim 11 (depends on 8) The compression method of claim 8, further comprising: skipping outputting of the subset of matches for (1+k) cycles from a next cycle if a last match selected most recently in a current cycle corresponds to a match for the (1+k) cycles from the next cycle, wherein k is equal to or less than M and is a positive integer which is zero or more. ### Claim 12 (depends on 8) The compression method of claim 8, further comprising: merging sets of matches obtained for Y cycles; outputting a merged set of matches once per the Y cycles; and selecting a subset of matches corresponding to the input data of at least (N×Y) bytes from the merged set of matches, wherein Y is a positive integer. ### Claim 13 (depends on 8) The compression method of claim 8, wherein a byte length of each substring being N×(M+2).