Data storage device and method performing background operation with selected data compression

• US 8,706,953 B2
• Filed: 04/28/2011
• Issued: 04/22/2014
• Est. Priority Date: 05/10/2010
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Cho, Kyoung Lae, Kim, Kwang Ho, Kong, Jun Jin, Kim, Jaehong, Son, Hong Rak
• Primary Examiner(s): Blair, April Y
• Assistant Examiner(s): Kolb, Michael C
• Application Number:
  US13/096,036
• Publication Number:
  US 20110276777A1
• Time in Patent Office: 1,090 Days
• Field of Search: None
• US Class Current: 711/103
• CPC Class Codes: 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

Abstract

A method of storing data in a storage medium of a data storage device comprises storing input data in the storage medium, and reading the input data from the storage medium and compressing the read data during a background operation of the data storage device.

Claims

1. A method of storing data in a storage medium of a data storage device, comprising:

storing input data in the storage medium; and

reading the input data from the storage medium and compressing the read input data during a background operation of the data storage device;

wherein the background operation comprises a merge operation, and compressing data stored in the storage medium comprises;

determining whether a free block can be generated by merging “

M”

selected memory blocks to be merged using a first merge scheme;

performing the merge operation according to the first merge scheme if a free block can be generated by merging the “

M”

selected memory blocks using the first merge scheme; and

performing the merge operation according to a second merge scheme different from the first merge scheme if a free block cannot be generated by merging the “

M”

selected memory blocks using the first merge scheme;

wherein the first merge scheme comprises reading valid data from “

M”

used memory blocks in the storage medium as the read input data, compressing the read valid data to generate compressed data, and storing the compressed data in free memory blocks of the storage medium; and

wherein the second merge scheme comprises reading valid data from “

N”

used memory blocks in the storage medium as the read input data, where N is greater than M, and storing the read valid data in free memory blocks of the storage medium.

2. The method of claim 1, further comprising:

determining whether the input data is compressed data and generating a compression indicator indicating whether the input data is compressed data; and

storing the compression indicator in a header or footer of the input data or a spare area of a memory block in which the input data is stored.

3. The method of claim 2, wherein the determination of whether the input data is compressed data is made by identifying a compression rate of the input data.

4. The method of claim 2, wherein the determination of whether the input data is compressed data is made according to a size of the input data.

5. The method of claim 1, further comprising:

receiving information indicating whether the input data is compressed data; and

storing the received information in a compression mapping table, a header or footer of the input data, or a spare area of a memory block in which the input data is to be stored.

6. The method of claim 1, wherein compressing the read data comprises:

reading valid data from a source block of the storage medium as the read input data;

compressing the read valid data to generate compressed data; and

storing the compressed data in a target block of the storage medium.

7. The method of claim 6, wherein the source block is erased after the merge operation is completed.

8. The method of claim 1, further comprising erasing the “

N”

or “

M”

used memory blocks after the merge operation is completed.

9. A data storage device, comprising:

a storage medium comprising memory blocks;

a memory translation layer configured to select “

M”

memory blocks of the storage medium in which input data is to be stored; and

a compression block configured to compress data stored in the “

M”

selected memory blocks during a background operation of the data storage device;

wherein the background operation comprises a merge operation, and data compression is accomplished by determining whether a free block can be generated by merging the “

M”

selected memory blocks using a first merge scheme, performing the merge operation according to the first merge scheme if a free block can be generated by merging the “

M”

selected memory blocks using the first merge scheme, and performing the merge operation according to a second merge scheme different from the first merge scheme if no free block can be generated by merging the “

M”

selected memory blocks using the first merge scheme;

wherein the first merge scheme comprises reading valid data from “

M”

used memory blocks in the storage medium as the read input data, compressing the read valid data to generate compressed data, and storing the compressed data in free memory blocks of the storage medium; and

wherein the second merge scheme comprises reading valid data from “

N”

used memory blocks in the storage medium as the read input data, where N is greater than M and storing the read valid data in free memory blocks of the storage medium.

10. The data storage device of claim 9, wherein data compression is accomplished by reading valid data from a source block among the memory blocks as the read input data, compressing the read valid data to generate compressed data, and storing the compressed data in a target block among the memory blocks.

11. A method of operating a data storage device, comprising:

storing input data in a log block;

updating a log block mapping table to reflect the storage of the input data in the log block;

during a background operation of the data storage device, reading the input data from the log block, compressing the read input data to produce compressed data, and storing the compressed data in a data block; and

updating a data block mapping table to reflect storage of the compressed data in the data block;

wherein the background operation comprises a merge operation, and data compression is accomplished by determining whether a free block can be generated by merging the log block with at least one other memory block using a first merge scheme, performing the merge operation according to the first merge scheme if a free block can be generated by the merging using the first merge scheme, and performing the merge operation according to a second merge scheme different from the first merge scheme if no free block can be generated by the merging using the first merge scheme;

wherein the first merge scheme comprises reading valid data from “

M”

used memory blocks in the storage medium as the read input data, compressing the read valid data to generate compressed data, and storing the compressed data in free memory blocks of the storage medium; and

wherein the second merge scheme comprises reading valid data from “

N”

used memory blocks in the storage medium as the read input data, where N is greater than M and storing the read valid data in free memory blocks of the storage medium.

12. The method of claim 11, wherein the data block mapping table further comprises a compression mapping table indicating whether stored data is compressed.