Data compression circuit, memory system and method for controlling the data compression circuit

A data compression circuit configured to compress first data which is input data, the data compression circuit comprising:

• a buffer including a plurality of registers each storing a 1-byte data unit, one or more first registers in which data units included in the first data are sequentially stored for each cycle being included in the plurality of registers;
• a plurality of comparators, each of the plurality of comparators corresponding to a distance between the one or more first registers and a register that stores a data unit of an earlier storage order than the data unit stored in the first register, each of the plurality of comparators comparing a data unit stored in the one or more first registers and a data unit in the earlier storage order;
• a plurality of match length calculation circuits, each of the plurality of match length calculation circuits corresponding to one or more comparators among the plurality of comparators, each of the plurality of match length calculation circuits calculating a match length based on a result received from the corresponding one or more comparators;
• a plurality of intermediate match candidate selection circuits, each of the plurality of intermediate match candidate selection circuits corresponding to two or more match length calculation circuits among the plurality of match length calculation circuits, each of the plurality of intermediate match candidate selection circuits selecting a match length from two or more match lengths received from the two or more corresponding match length calculation circuits;
• and
• a plurality of intermediate match candidate generation circuits, each of the plurality of intermediate match candidate generation circuits corresponding to an intermediate match candidate selection circuit among the plurality of intermediate match candidate selection circuits, each of the plurality of intermediate match candidate generation circuits generating an intermediate match candidate based on the match length selected by the corresponding intermediate match candidate selection circuit, wherein
• each of the intermediate match candidate generation circuits is configured to calculate a match length with a bit width larger than a bit width of the match length calculation circuits, and
• each of the plurality of intermediate match candidate generation circuits is configured to:
• generate an intermediate match candidate by incrementing, based on a match length received from the corresponding intermediate match candidate selection circuit, a match length corresponding to an intermediate match candidate generated in a previous cycle when a distance corresponding to the received match length matches a distance corresponding to the intermediate match candidate generated in the previous cycle and the received match length is greater than a threshold value;
• and
• generate the received match length as a new intermediate match candidate when the distance corresponding to the received match length does not match the distance corresponding to the intermediate match candidate generated in the previous cycle, or when the received match length is equal to or less than the threshold value.