[go: up one dir, main page]

KR20120109753A - 저장 장치에서의 데이터 압축 방법 - Google Patents

저장 장치에서의 데이터 압축 방법 Download PDF

Info

Publication number
KR20120109753A
KR20120109753A KR1020110027176A KR20110027176A KR20120109753A KR 20120109753 A KR20120109753 A KR 20120109753A KR 1020110027176 A KR1020110027176 A KR 1020110027176A KR 20110027176 A KR20110027176 A KR 20110027176A KR 20120109753 A KR20120109753 A KR 20120109753A
Authority
KR
South Korea
Prior art keywords
data
codeword
symbol
length
chunk data
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
KR1020110027176A
Other languages
English (en)
Other versions
KR101725223B1 (ko
Inventor
서만근
공준진
손홍락
조경래
송제혁
이광구
Original Assignee
삼성전자주식회사
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 삼성전자주식회사 filed Critical 삼성전자주식회사
Priority to KR1020110027176A priority Critical patent/KR101725223B1/ko
Priority to US13/364,787 priority patent/US8593307B2/en
Publication of KR20120109753A publication Critical patent/KR20120109753A/ko
Application granted granted Critical
Publication of KR101725223B1 publication Critical patent/KR101725223B1/ko
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
    • H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • H03M7/40—Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0668—Interfaces specially adapted for storage systems adopting a particular infrastructure
    • G06F3/0671—In-line storage system
    • G06F3/0673—Single storage device
    • G06F3/0679—Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F5/00—Methods or arrangements for data conversion without changing the order or content of the data handled
    • G—PHYSICS
    • G11—INFORMATION STORAGE
    • G11C—STATIC STORES
    • G11C29/00—Checking stores for correct operation ; Subsequent repair; Testing stores during standby or offline operation
    • G11C29/04—Detection or location of defective memory elements, e.g. cell constructio details, timing of test signals
    • G11C29/08—Functional testing, e.g. testing during refresh, power-on self testing [POST] or distributed testing
    • G11C29/12—Built-in arrangements for testing, e.g. built-in self testing [BIST] or interconnection details
    • G11C29/38—Response verification devices
    • G11C29/40—Response verification devices using compression techniques

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Human Computer Interaction (AREA)
  • Compression, Expansion, Code Conversion, And Decoders (AREA)

Abstract

저장 장치에서의 데이터 압축 방법이 개시된다. 본 발명의 실시예에 따른 저장 장치에서의 데이터 압축 방법은, 청크(chunk) 데이터의 심볼의 발생 빈도수와 부호어 길이와의 관계를 나타내는 제1 테이블을 이용하여 상기 심볼에 대한 부호어 길이를 결정하고, 상기 부호어 길이를 갖고 상기 심볼에 대응되는 부호어를 결정하는 단계; 및 상기 심볼을 상기 부호어로 변환하여 상기 청크 데이터에 대한 압축 데이터를 생성하는 단계를 구비한다.

Description

저장 장치에서의 데이터 압축 방법{Data compressing method of storage device}
본 발명은 저장 장치에서의 데이터 압축 방법에 관한 것으로 특히, 데이터 압축에 소요되는 연산량의 증가 및 동작 지연을 줄일 수 있는 저장 장치에서의 데이터 압축 방법에 관한 것이다.
저장 장치에 데이터를 저장하기 전에 데이터를 압축함으로써 저장 공간을 효율적으로 사용할 수 있으며, 데이터의 프로그램 및 독출의 횟수를 줄일 수 있어 저장 장치의 수명을 연장할 수 있다. 이때, 짧은 시간에 많은 양의 데이터를 압축하면서도 압축 처리에 의한 지연 시간을 최소화할 수 있는 저장 장치가 요구되고 있다.
본 발명이 해결하고자 하는 기술적 과제는, 짧은 시간에 많은 양의 데이터를 압축하면서도 압축 처리에 의한 지연 시간을 최소화할 수 있는 저장 장치에서의 데이터 압축 방법을 제공하는 것에 있다.
상기 기술적 과제를 달성하기 위한 본 발명의 실시예에 따른 저장 장치에서의 데이터 압축 방법은, 청크(chunk) 데이터의 심볼의 발생 빈도수와 부호어 길이와의 관계를 나타내는 제1 테이블을 이용하여 상기 심볼에 대한 부호어 길이를 결정하고, 상기 부호어 길이를 갖고 상기 심볼에 대응되는 부호어를 결정하는 단계; 및 상기 심볼을 상기 부호어로 변환하여 상기 청크 데이터에 대한 압축 데이터를 생성하는 단계를 구비한다.
바람직하게는, 상기 청크 데이터를 압축하는 단계는, 상기 청크 데이터의 상기 심볼의 발생 빈도수를 카운트 하는 단계; 상기 제1 테이블 상에 상기 심볼의 발생 빈도수에 대응되는 부호어 길이를 검색하여 결정하는 단계; 및 상기 부호어 길이에 대응되는 부호어를 결정하여, 상기 심볼을 상기 부호어로 변환하는 단계를 구비한다.
바람직하게는, 상기 제1 테이블을 형성하는 단계가 더 구비될 수 있다. 이때, 상기 제1 테이블을 형성하는 단계는, 테스트 데이터를 수신하는 단계; 및 상기 테스트 데이터의 각 심볼의 발생 빈도의 확률을 산출하는 단계; 상기 테스트 데이터의 각 심볼의 발생 빈도의 확률을 정렬하여 허프만 트리를 생성하는 단계; 및 상기 테스트 데이터에 대한 상기 허프만 트리에 근거하여, 상기 테스트 데이터의 각 심볼과 상기 각 심볼에 대응되는 부호어 길이를 매치하는 단계를 구비할 수 있다.
바람직하게는, 상기 테스트 데이터는, 상기 청크 데이터와 압축률, 디코딩 방식 및 크기 중 적어도 하나가 동일할 수 있다.
바람직하게는, 상기 제1 테이블은, 상기 각 심볼과 상기 부호어의 길이와의 제1 관계에 대한 제1 서브 테이블 및 상기 각 심볼과 상기 부호어의 길이와의 제2 관계에 대한 제2 서브 테이블을 포함할 수 있다. 이때, 상기 청크 데이터를 압축하는 단계는, 상기 제1 서브 테이블 및 상기 제2 서브 테이블 중 하나를 선택하는 단계; 및 상기 제1 서브 테이블 및 상기 제2 서브 테이블 중 선택된 서브 테이블을 이용하여 상기 부호어의 길이를 결정하는 단계를 구비할 수 있다. 이때, 상기 서브 테이블을 선택하는 단계는, 상기 청크 데이터를 압축하고자 하는 압축률에 따라 상기 서브 테이블을 선택할 수 있다.
바람직하게는, 상기 저장 장치는, 솔리드 스테이트 드라이브(Solid State Drive)일 수 있다.
상기 기술적 과제를 해결하기 위한 본 발명의 다른 실시예에 따른 저장 장치에서의 데이터 압축 방법은 청크 데이터를 제1 유형의 제1 청크 데이터 및 제2 유형의 제2 청크 데이터 중 하나로 분류하는 단계; 상기 제1 청크 데이터의 각 심볼의 발생 빈도수와 부호어의 길이와의 관계를 나타내는 제1 테이블을 이용하여 상기 제1 청크 데이터의 각 심볼에 대응되는 부호어 길이를 결정하고, 상기 제1 청크 데이터의 각 심볼을 대응되는 부호어의 길이를 갖는 부호어로 변환하여 상기 제1 청크 데이터를 압축하는 단계; 및 상기 제2 청크 데이터에 포함되는 각 심볼의 발생 빈도수와 부호어의 길이와의 관계를 나타내는 제2 테이블을 이용하여 상기 제2 청크 데이터의 각 심볼에 대응되는 부호어 길이를 결정하고, 상기 제2 청크 데이터의 각 심볼을 대응되는 부호어의 길이를 갖는 부호어로 변환하여 상기 제2 청크 데이터를 압축하는 단계를 구비한다.
본 발명에 따른 저장 장치에서의 데이터 압축 방법에 의하면, 압축 효율을 유지하면서도 허프만 트리의 형성에 소요되는 연산량 증가 및 지연을 줄일 수 있는 장점이 있다. 이에 따라, 본 발명에 따른 저장 장치에서의 데이터 압축 방법에 의하면, 장치의 수명이 연장될 수 있는 장점이 있다.
본 발명의 상세한 설명에서 인용되는 도면을 보다 충분히 이해하기 위하여 각 도면의 간단한 설명이 제공된다.
도 1은 본 발명의 실시예에 따른 저장 장치에서의 데이터 압축 방법을 나타내는 순서도이다.
도 2는 도 1의 데이터 압축 방법으로 동작하는 데이터 압축기를 나타내는 블록도이다.
도 3은 본 발명의 실시예에 따른 솔리드 스테이트 드라이브를 좀 더 자세히 나타내는 도면이다.
도 4는 도 2의 데이터 압축기가 구비되는 위치에 대한 실시예들을 나타내는 도면이다.
도 5는 도 2의 데이터 압축기를 포함하는 네트워크 시스템을 나타내는 도면이다.
도 6은 각 청크 데이터의 심볼의 발생 빈도수와 부호어의 길이와의 관계를 나타내는 그래프이다.
도 7 및 도 8은 허프만 트리를 형성하여 심볼의 발생 빈도 확률에 따른 부호어 길이를 할당하는 방법을 나타내는 도면이다.
도 9는 본 발명의 실시예에 따른 제1 테이블의 예를 나타내는 도면이다.
도 10 및 도 11은 각각, 본 발명의 실시예에 따른 제1 테이블을 형성하는 방법 및 이를 위한 데이터 압축기의 구조를 나타내는 도면이다.
도 12는 본 발명의 다른 실시예에 따른 솔리드 스테이트 드라이브(Solid State Drive)에서의 데이터 압축 방법을 나타내는 순서도이다.
도 13은 도 12의 데이터 압축 방법으로 동작하는 데이터 압축기를 나타내는 블록도이다.
도 14는 본 발명의 실시예에 따른 제2 테이블의 예를 나타내는 도면이다.
도 15는 본 발명의 또 다른 실시예에 따른 솔리드 스테이트 드라이브(Solid State Drive)에서의 데이터 압축 방법을 나타내는 순서도이다.
도 16은 도 15의 데이터 압축 방법으로 동작하는 데이터 압축기를 나타내는 블록도이다.
도 17은 본 발명의 실시예에 따른 청크 데이터의 구조를 나타내는 도면이다.
도 18은 본 발명의 실시예에 따른 컴퓨팅 시스템을 나타내는 도면이다.
본 발명과 본 발명의 동작상의 이점 및 본 발명의 실시에 의하여 달성되는 목적을 충분히 이해하기 위해서는 본 발명의 바람직한 실시 예를 예시하는 첨부 도면 및 도면에 기재된 내용을 참조하여야 한다.
이하 첨부한 도면을 참조하여 본 발명의 바람직한 실시 예를 설명함으로써, 본 발명을 상세히 설명한다. 각 도면에 제시된 동일한 참조부호는 동일한 부재를 나타낸다.
도 1은 본 발명의 실시예에 따른 저장 장치에서의 데이터 압축 방법을 나타내는 순서도이고, 도 2는 도 1의 데이터 압축 방법으로 동작하는 데이터 압축기를 나타내는 블록도이다.
도 1 및 도 2를 참고하면, 본 발명의 실시예에 따른 데이터 압축 방법(100)은 청크(chunk) 데이터(CDTA)를 수신하는 단계(S120), 청크 데이터(CDTA)에 포함되는 각 심볼(SYM)의 발생 빈도수(NUM)와 부호어 길이(LEN)와의 관계를 나타내는 제1 테이블(TBAL1)을 이용하여 부호어(CWRD)를 결정하는 단계(S140), 및 청크 데이터(CDTA)의 각 심볼(SYM)을 변환하여 압축 데이터(COMD)를 생성하는 단계(S160)를 구비한다.
도 1의 압축 방법(100)으로 동작하는 도 2의 데이터 압축기(DCT)는 부호어(CWRD)를 생성하는 부호어 생성부(CGT) 및 부호어(CWRD)를 이용하여 청크 데이터(CDTA)의 각 심볼(SYM)을 변환하여 압축 데이터(COMD)를 생성하는 심볼 변환부(SCU)를 구비할 수 있다. 부호어 생성부(CGT)는 데이터 수신부(DREV), 카운터(CNT), 부호어 길이 결정부(CLD) 및 부호어 결정부(CWD)를 구비한다. 데이터 압축기(DCT)의 구조 및 동작에 대한 더 자세한 설명은 후술된다.
도 1의 압축 방법(100)은 다양한 저장 장치에서 사용될 수 있다. 특히, 도 1의 압축 방법(100)은 저장 장치 중 솔리드 스테이트 드라이브(Solid State drive)에서 사용될 수 있다. 따라서, 도 2의 데이터 압축기(DCT)도 솔리드 스테이트 드라이브에 포함될 수 있다. 이하에서는 설명의 편의를 위해, 도 1의 압축 방법(100)이 솔리드 스테이트 드라이브에서 사용되는 예에 한하여 설명한다. 다만, 이에 한정되는 것은 아니고, 다른 저장 장치에서도 도 1의 압축 방법(100)이 사용될 수 있다. 이하에서 설명되는 다른 실시예에 따른 압축 방법도 마찬가지임을 명확히 해 둔다.
본 발명의 실시예에 따른 청크 데이터(CDTA)는 솔리드 스테이트 드라이브(SSD)에 포함되는 플래시 메모리에 프로그램하고자 하는 데이터(프로그램 데이터(PDTA))를 압축하는 단위일 수 있다. 예를 들어, 본 발명의 실시예에 따른 솔리드 스테이트 드라이브(SSD)가 4KB 단위로 매핑(mapping)되는 경우, 청크 데이터(CDTA)는 4KB로 설정될 수 있다.
프로그램 데이터(PDTA)를 프로그램 하기에 앞서 해당 데이터를 압축하면, 저장 공간이 효율적으로 사용될 수 있고, 데이터의 기입 및 독출의 횟수가 줄어들어 저장 장치의 수명이 연장될 수 있다. 그런데, 솔리드 스테이트 드라이브(SSD)와 같은 저장 장치는 높은 입출력(I/O) 처리율을 요구한다. 따라서, 본 발명의 실시예에 따른 솔리드 스테이트 드라이브(SSD)에서의 데이터 압출 방법(100) 및 데이터 압축기(DCT)는 짧은 시간 안에 많은 양의 데이터를 압축하여야 하며, 압축에 의한 지연 시간을 최소화하여야 한다.
짧은 시간 내에 많은 양의 데이터를 압축하기 위해, 본 발명의 실시예에 따른 데이터 압축 방법(100) 및 데이터 압축기(DCT)는 엔트로피 부호화(entropy coding) 방식으로 압축을 수행할 수 있다. 본 발명의 실시예에 따른 데이터 압축 방법(100) 및 데이터 압축기(DCT)는 특히, 엔트로피 부호화 방식 중, 청크 데이터(CDTA)에 포함되는 심볼(SYM)들 중 발생 빈도수(NUM)가 많은 심볼(SYM)에 짧은 부호어(codeword, CWRD)를 할당하고, 발생 빈도수(NUM)가 적은 심볼에는 상대적으로 긴 길이의 부호어(CWRD)를 할당하는 허프만 코딩(Huffman coding) 방식으로 청크 데이터(CDTA)에 대한 압축을 수행할 수 있다.
본 발명의 실시예에 따른 솔리드 스테이트 드라이브(SSD)를 좀 더 자세히 나타내는 도 3을 참조하면, 본 발명의 실시예에 따른 솔리드 스테이트 드라이브(SSD)는 SSD 컨트롤러(SCTL) 및 플래시 메모리(MEM)를 포함할 수 있다. SSD 컨트롤러(SCTL)는 버스(BUS)로 연결되는 프로세서(PROS), 램(RAM), 캐쉬 버퍼(CBUF) 및 메모리 컨트롤러(Ctrl)를 구비할 수 있다. 프로세서(PROS)는 호스트(미도시)의 요청(명령, 어드레스, 데이터)에 응답하여 메모리 컨트롤러(Ctrl)가 플래시 메모리(MEM)와 데이터를 송수신하도록 제어한다. 본 발명의 실시예에 따른 솔리드 스테이트 드라이브(SSD)의 프로세서(PROS) 및 메모리 컨트롤러(Ctrl)는 하나의 ARM 프로세서로 구현될 수도 있다. 프로세서(PROS)의 동작에 필요한 데이터는 램(RAM)에 로딩될 수 있다.
호스트 인터페이스(HOST I/F)는 호스트의 요청을 수신하여 프로세서(PROS)로 전송하거나, 플래시 메모리(MEM)로부터 전송된 데이터를 호스트로 전송한다. 호스트 인터페이스(HOST I/F)는 USB(Universal Serial Bus), MMC(Man Machine Communication), PCI-E(Peripheral Component Interconnect-Express), SATA(Serial Advanced Technology Attachment), PATA(Parallel Advanced Technology Attachment), SCSI(Small Computer System Interface), ESDI(Enhanced Small Device Interface), 그리고 IDE(Intelligent Drive Electronics) 등과 같은 다양한 인터페이스 프로토콜로, 호스트와 인터페이스 할 수 있다. 플래시 메모리(MEM)로 전송하고자 하거나, 플래시 메모리(MEM)로부터 전송된 데이터는 캐쉬 버퍼(CBUF)에 임시로 저장될 수 있다. 캐쉬 버퍼(CBUF)는 SRAM 등일 수 있다.
이때, 도 2의 데이터 압축기(DCT)는 도 4의 (a)와 같이 SSD 컨트롤러(SCTL)에 구비되거나, 도 4의 (b)와 같이 플래시 메모리(MEM)에 구비될 수 있다. 특히, 도 2의 데이터 압축기(DCT)는 SSD 컨트롤러(SCTL) 또는 플래시 메모리(MEM)에 포함되는 압축 엔진(미도시)에 구비될 수 있다. 도 2의 데이터 압축기(DCT)를 포함하는 솔리드 스테이트 드라이브(SSD)는 도 5와 같이 네트워크 시스템(NSYS)에 연결되는 서버 시스템(SSYS)에 포함될 수 있다.
도 5를 참조하면, 본 발명의 실시예에 따른 네트워크 시스템(NSYS)은 네트워크를 통해 연결되는 서버 시스템(SSYS) 및 다수의 단말기들(TEM1~TEMn)을 포함할 수 있다. 본 발명의 실시예에 따른 서버 시스템(SSYS)은 네트워크에 연결되는 다수의 단말기들(TEM1~TEMn)로부터 수신되는 요청을 처리하는 서버(SERVER) 및 단말들(TEM1~TEMn)로부터 수신되는 요청에 대응되는 데이터를 저장하는 솔리드 스테이트 드라이브(SSD)를 구비할 수 있다. 이때, 도 5의 솔리드 스테이트 드라이브(SSD)는 도 3의 솔리드 스테이트 드라이브(SSD)일 수 있다. 즉, 도 5의 솔리드 스테이트 드라이브(SSD)는 도 3의 SSD 컨트롤러(SCTL) 및 플래시 메모리(MEM)를 포함할 수 있다.
단말기들(TEM1~TEMn)로부터 서버 시스템(SSYS)으로 전송되어 서버 시스템(SSYS)에 저장되는 데이터(예를 들어, 프로그램 데이터(PDTA))는, 전술한 바와 같이, 플래시 메모리(MEM)에 저장되기에 앞서 청크 데이터(CDTA)의 단위로 압축이 수행될 수 있고, 특히 허프만 코딩 방식으로 압축이 수행될 수 있다. 그런데, 도 5의 서버 시스템(SSYS)은 네트워크로 연결되는 복수의 단말기들(TEM1~TEMn)과 유사한 유형의 데이터를 송수신할 수 있다.
예를 들어, 본 발명의 실시예에 따른 솔리드 스테이트 드라이브(SSD)에 저장하고자 복수의 단말기들(TEM1~TEMn)로부터 전송되는 데이터들은 서로 동일한 압축률(예를 들어 50% 전후)을 가질 수 있다. 구체적으로, 제1 단말기(TEM1)로부터 전송되는 제1 데이터(DTA1), 제2 단말기(TEM2)로부터 전송되는 제2 데이터(DTA2) 및 제3 단말기(TEM3)로부터 전송되는 제3 데이터(DTA3)는 모두 멀티미디어 데이터로, 서로 동일한 비율로 압축될 수 있다. 다른 단말기의 데이터(예를 들어, 제n 단말기(TEMn)의 제n 데이터(DTAn))도 마찬가지일 수 있다. 데이터 압축의 특성 상, 서로 다른 데이터가 완전히 동일한 압축률로 압축되기 어려울 수 있다. 따라서, 본 발명의 실시예에 따른 데이터가 동일한 압축률로 압축되었다 함은, 각 데이터에 대한 압축률의 차이가 일정한 범위 이내인 경우를 포함함을 알려둔다.
유사한 데이터 특성을 갖는 데이터(DTA1~DTAn)를, 서버를 통해 솔리드 스테이트 드라이브(SSD)로 저장하기에 앞서 압축하기 위해, 각 데이터(DTA1~DTAn)의 청크 데이터(CDTA1~CDTAn) 단위로 허프만 코딩하면, 각 청크 데이터(CDTA1~CDTAn)의 심볼(SYM)의 발생 빈도수(NUM)와 부호어 길이(LEN) 관계가 청크 데이터(CDTA1~CDTAn)마다 유사한 경향을 보일 수 있다. 예를 들어, 청크 데이터(CDTA)들의 각 심볼(SYM)의 발생 빈도수(NUM)와 부호어 길이(LEN)와의 관계는 도 6에 도시되는 바와 같이, 청크 데이터(CDTA)들 마다, 심볼(SYM)의 발생 빈도수(NUM)가 a이면 부호어 길이(LEN)는 a'이고, 발생 빈도수(NUM)가 b이면 부호어 길이(LEN)는 b'로 같을 수 있다.
즉, 제1 단말기(TEM1)로부터 전송되는 제1 데이터(DTA1)의 제1 청크 데이터(CDTA1), 제2 단말기(TEM2)로부터 전송되는 제2 데이터(DTA2)의 제2 청크 데이터(CDTA2) 및 제3 단말기(TEM3)로부터 전송되는 제3 데이터(DTA3)의 제3 청크 데이터(CDTA3)는 모두, 발생 빈도수(NUM)가 a인 심볼(SYM)에 대한 부호어 길이(LEN)가 a'로 같게 할당되고, 발생 빈도수(NUM)가 b인 심볼(SYM)에 대한 부호어 길이(LEN)가 b'로 같게 할당될 수 있다. 다른 단말기의 청크 데이터(예를 들어, 제n 단말기(TEMn)의 제n 청크 데이터(CDTAn))도 마찬가지일 수 있다.
본 발명의 실시예에 따른 데이터 압축 방법(100) 및 데이터 압축기(DCT)에 의하면, 청크 데이터(CDTA)들의 각 심볼(SYM)의 발생 빈도수(NUM)와 부호어 길이(LEN)와의 관계를 규정하는 제1 테이블(TBAL1)을 형성함으로써, 다음과 같은 허프만 트리를 형성하는 과정이 생략될 수 있다. 도 2, 도 7 및 도 8을 참조하여 허프만 트리의 형성 예를 설명한다.
도 2, 도 7 및 도 8을 참조하면, 청크 데이터(CDTA)에 포함되는 심볼(SYM)이 A, B, C, D 및 E이다. 상기 예에서, 각 심볼(SYM)의 발생 빈도수(NUM)를 확률로 환산하면, A는 0.25, B는 0.15, C는 0.45, D는 0.1, 그리고 E는 0.05의 확률로 발생된다. 각 심볼(SYM)을 발생 빈도수(NUM), 즉 발생 빈도 확률이 낮은 순서대로 정렬하면, 도 7의 ①에 도시된 것과 같이, E, D, B, A 및 C 순서로 정렬될 수 있다. 다음으로, 발생 빈도 확률이 낮은 두 개의 심볼들 E와 D의 확률을 합하여 확률 0.15의 N1을 생성한다. 그리고 다시, 심볼 B, A, C와 N1을 확률이 낮은 순서대로 정렬하면 도 7의 ②와 같을 수 있다. 마찬가지로, B, A, C와 N1 중 발생 빈도 확률이 낮은 B와 N1의 확률을 합하여 확률 0.3의 N2를 생성한다. 상기와 같이, 확률의 크기로 심볼들을 정렬하고, 확률이 낮은 두 개의 심볼들을 합하는 과정을, 그 확률의 합이 1이 될 때까지 반복한다. 따라서, A, C 및 N2를 정렬하면 도 7의 ③과 같고, 이 중 확률이 낮은 A 및 N2의 확률을 합하여 확률 0.55의 N3를 생성한다. 도 7의 ④에서, N3의 확률 0.55와 C의 확률 0.45를 합하면, 도 7의 ⑤와 같이, 그 합이 1인 N4가 생성된다.
이렇게, 허프만 부호어를 생성하기 위한 정렬 과정이 종료되면, 도 8과 같은 허프만 트리가 형성된다. 허프만 트리에 근거하여, 심볼의 발생 빈도수에 따른 부호어의 길이가 결정된다. 도 8의 예에서, 심볼 D 및 E에 대한 부호어의 길이는 각각 4bit로 결정되고, 심볼 B에 대한 부호어의 길이는 3bit로 결정되며, 심볼 A에 대한 부호어의 길이는 2bit로 결정된다. 그리고, 심볼 C에 대한 부호어의 길이는 1bit로 결정된다.
그런데, 도 7의 반복적인 정렬 과정의 수행은 연산량의 증가 및 장치의 동작 지연을 유발시킨다. 본 발명의 실시예에 따른 데이터 압축 방법(100) 및 데이터 압축기(DCT)에 의하면, 청크 데이터(CDTA)의 각 심볼의 발생 빈도수(NUM)와 부호어 길이(LEN)와의 관계를 나타내는 제1 테이블(TBAL1)을 이용함으로써, 압축 효율을 유지하면서도 허프만 트리의 형성에 소요되는 연산량 증가 및 지연을 줄일 수 있다. 이에 대하여 자세히 설명한다.
다시 도 1 및 도 2를 참조하면, 본 발명의 실시예에 따른 데이터 수신부(DREV)는 청크 데이터(CDTA)를 수신한다(S120). 전술한 바와 같이, 청크 데이터(CDTA)는 프로그램 데이터(PDTA)를 압축의 단위로 분할한 데이터일 수 있다. 도 2 및 이하에서 설명되는 도면에서 데이터 수신부(DREV)가 청크 데이터(CDTA)를 수신하는 것으로 도시하고 있으나, 이에 한정되는 것은 아니다. 데이터 수신부(DREV)는 프로그램 데이터(PDTA)를 수신하여 이를 청크 데이터(CDTA)로 분할할 수도 있다.
카운터(CNT)는 청크 데이터(CDTA)를 이루는 각 심볼(SYM)의 발생 빈도수(NUM)를 카운트한다(S142). 예를 들어, 카운터(CNT)는 청크 데이터(CDTA)에 심볼 "0000000011111111"이 3번 발생하고, 심볼 "0101010101010101"이 90번 발생한 것을 카운트할 수 있다. 카운터(CNT)는 카운트한 발생 빈도수(NUM)를 부호어 길이 결정부(CLD)로 전송한다. 부호어 길이 결정부(CLD)는 테이블 저장부(TST)에 저장되어 있는 제1 테이블(TBAL1)을 참조하여, 심볼(SYM)의 발생 빈도수(NUM)에 대응되는 부호어 길이(LEN)를 결정한다(S144).
테이블 저장부(TST)는 부호어 길이 결정부(CLD)로부터 전송되는 요청(REQ)에 응답하여, 대응되는 부호어 길이(LEN)를 출력할 수 있다. 부호어 길이 결정부(CLD)로부터 전송되는 요청(REQ)에는 해당 심볼의 발생 빈도수에 대한 값이 포함될 수 있다. 본 발명의 실시예에 따른 제1 테이블(TBAL1)은 도 9에 도시되는 바와 같을 수 있다. 예를 들어, 본 발명의 실시예에 따른 제1 테이블(TBAL1)은 발생 빈도수(NUM)가 1인 경우 부호어 길이(LEN)는 12이고, 발생 빈도수(NUM)가 2인 경우 부호어 길이(LEN)는 11이며, 발생 빈도수(NUM)가 3~4인 경우 부호어 길이(LEN)는 10으로 맵핑되도록 설정될 수 있다.
제1 테이블(TBAL1)은 호스트나 컨트롤러에 의해 제공되어 테이블 저장부(TST)에 저장될 수 있다. 또는 제1 테이블(TBAL1)은 본 발명의 실시예에 따른 데이터 압축기(DCT)에 의해 생성될 수 있다. 본 발명의 실시예에 따른 데이터 압축기(DCT)에 의해 제1 테이블(TBAL1)의 생성되는 방법에 대한 더 자세한 사항은 후술된다.
다시 도 1 및 도 2를 참조하면, 본 발명의 실시예에 따른 부호어 길이 결정부(CLD)는 도 9와 같은 제1 테이블(TBAL1)을 참조하여, 상기 예와 같이 3번 발생한 심볼 "0000000011111111"의 부호어 길이(LEN)를 10으로 결정하고, 90번 발생된 심볼 "0101010101010101"에 대한 부호어 길이(LEN)를 5으로 결정한다.
부호어 길이 결정부(CLD)는 각 심볼(SYM)에 대해 결정된 부호어 길이(LEN)를 부호어 결정부(CWD)에 전달한다. 부호어 결정부(CWD)는 해당 길이(LEN)를 갖는 부호어(CWRD)를 결정한다(S146). 예를 들어, 부호어 결정부(CWD)는 심볼 "0000000011111111"를 길이 10의 부호어 "0001100011"로 결정하고, 심볼 "0101010101010101"를 길이 5의 부호어 "11110"으로 결정할 수 있다. 이때, 부호어 결정부(CWD)는 동일한 길이를 갖는 다수의 부호어 중 임의의 부호어를 결정할 수 있다. 예를 들어, 상기 예에서 심볼 "0101010101010101"를 길이 5의 부호어 "11110"가 아닌, 길이 5의 부호어 "01010"으로 결정할 수 있다.
본 발명의 실시예에 따른 부호어 결정부(CWD)는 대응되는 길이의 부호어(CWRD)를 랜덤하게 결정할 수 있다. 또는 본 발명의 실시예에 따른 부호어 결정부(CWD)는 외부로부터 전송되는 제어 신호(미도시)에 응답하여 대응되는 길이의 부호어(CWRD)를 결정할 수도 있다.
심볼 변환부(SCU)는 각 심볼(SYM)을 대응되는 부호어(CWRD)로 변환한다(S160). 상기 예에서, 심볼 변환부(SCU)는 청크 데이터(CDTA)에서 "0000000011111111"를 부호어 "0001100011"로 변환하고, "0101010101010101"를 부호어 "11110"로 변환한다. 따라서, 심볼 변환부(SCU)는 각 청크 데이터(CDTA)에 대하여 압축된 데이터인 압축 데이터(COMD)를 생성한다. 압축 데이터(COMD)는 플래시 메모리(MEM)에 저장될 수 있다.
심볼 변환부(SCU)가 청크 데이터(CDTA)의 각 심볼(SYM)을 대응되는 부호어(CWRD)로 변환하기 위해, 심볼 변환부(SCU)는 청크 데이터(CDTA)를 데이터 수신부(DREV)를 통해 수신하거나, 데이터 수신부(DREV)를 거치지 아니하고 청크 데이터(CDTA)를 바로 수신하는 등, 다양한 실시예들이 존재할 수 있다. 따라서, 도 2에서 심볼 변환부(SCU)로 청크 데이터(CDTA)가 입력되는 것을 특정하여 도시하지 아니한다.
이하에서는, 본 발명의 실시예에 따른 제1 테이블(TBAL1)의 생성 방법에 대하여 알아본다. 도 10 및 도 11을 참조하면, 본 발명의 실시예에 따른 데이터 압축기(DCT)는 제1 테이블(TBAL1)을 생성하기 위해, 먼저, 데이터 수신부(DREV)가 테스트 데이터(TDTA)를 수신한다(S1010). 테스트 데이터(TDTA)는 프로그램 데이터(PDTA)의 일부로, 청크 데이터(CDTA)와 동일한 유형의 데이터일 수 있다. 즉, 청크 데이터(CDTA)와 같은 크기이거나, 청크 데이터(CDTA)와 디코딩 방식이 동일할 수 있다. 나아가 테스트 데이터(TDTA)는 청크 데이터(CDTA)일 수도 있다. 다시 말해, 본 발명의 실시예에 따른 제1 테이블(TBAL1)의 생성 방법(1000)은 청크 데이터(CDTA)들 중 초기(데이터 압축기(DCT)의 인에이블 시, 또는 제1 테이블 생성이나 업데이트를 위한 동작 시)에 수신되는 청크 데이터(CDTA)를 이용하거나, 임의의 청크 데이터(CDTA)를 랜덤하게 샘플링하여 제1 테이블(TBAL1)을 생성할 수 있다.
이러한 테스트 데이터(TDTA)에 포함되는 각 심볼(SYM)과 그 발생 빈도수(NUM)의 관계를 나타내는 제1 테이블(TBAL1)은 본 발명의 실시예에 따른 데이터 압축기(DCT)에 더 구비되는 테이블 생성부(TGT)에 의해 생성될 수 있다. 이때, 각 심볼(SYM)과 그 발생 빈도수(NUM)의 관계는 도 7 및 도 8에서 설명된 허프만 트리를 형성하여 설정될 수 있다.
즉, 테이블 생성부(TGT)는 테스트 데이터(TDTA)의 심볼(SYM)의 발생 빈도의 확률을 산출하고(S1020), 테스트 데이터(TDTA)의 각 심볼(SYM)의 발생 빈도의 확률을 정렬하여(S1030) 허프만 트리를 생성(S1040)할 수 있다. 다음으로, 테이블 생성부(TGT)는 테스트 데이터(TDTA)에 대한 허프만 트리에 근거하여, 테스트 데이터(TDTA)의 각 심볼(SYM)과 상기 부호어 길이(LEN)를 매치(match)시킴으로써, 제1 테이블(TBAL1)을 생성할 수 있다(S1050).
이상에서는 하나의 테이블을 이용하여 부호어의 길이를 결정하는 예를 도시하였다. 다만, 이에 한정되는 것은 아니다. 본 발명의 실시예에 따른 데이터 압축 방법 및 데이터 압축기는 다수의 테이블들 중 하나를 선택하고, 선택된 테이블을 이용하여 부호어의 길이를 결정할 수도 있다. 이에 대하여 설명한다.
도 12는 본 발명의 실시예에 다른 따른 솔리드 스테이트 드라이브(Solid State Drive)에서의 데이터 압축 방법을 나타내는 순서도이고, 도 13은 도 12의 데이터 압축 방법으로 동작하는 데이터 압축기를 나타내는 블록도이다.
도 12 및 도 13을 참조하면, 본 발명의 다른 실시예에 따른 데이터 압축 방법(1200) 및 데이터 압축기(DCT)는 각각, 도 1 및 도 2의 데이터 압축 방법(100) 및 데이터 압축기(DCT)와 유사한 구성으로 동작한다. 즉, 도 12의 데이터 압축 방법(1200) 및 도 13의 데이터 압축기(DCT)에 의하면, 데이터 수신부(DREV)를 통해 청크 데이터(CDTA)가 수신되고(S1220), 카운터(CNT)에 의해 청크 데이터(CDTA)의 각 심볼(SYM)의 발생 빈도수(NUM)가 카운트되며(S1242), 부호어 길이 결정부(CLD)에 의해 테이블을 이용하여 각 심볼(SYM)의 발생 빈도수(NUM)에 대응되는 부호어 길이(LEN)가 결정된다(S1244). 또한, 도 12의 데이터 압축 방법(1200) 및 도 13의 데이터 압축기(DCT)에 의하면, 부호어 결정부(CWD)에 의해 각 심볼(SYM)의 부호어 길이(LEN)에 대응되는 부호어(CWRD)가 결정되고(S1246), 심볼 변환부(SCU)에 의해 각 심볼(SYM)이 대응되는 부호어(CWRD)로 변환되어 압축 데이터(COMD)가 생성된다(S1260). 마찬가지로, 제1 테이블(TBAL1)은 테이블 저장부(TST)에 저장된다.
다만, 도 12의 데이터 압축 방법(1200) 및 도 13의 데이터 압축기(DCT)에 의하면, 부호어 생성부(CGT)에 의한 부호어(CWRD)를 생성(S1240)함에 있어, 도 1 및 도 2와 같이 하나의 테이블(TABL1)을 이용하는 것이 아니라, 다수의 서브 테이블(STABL1, STABL2) 중 하나를 선택하고 선택된 서브 테이블을 이용하여 부호어 길이(LEN)를 결정한다. 따라서, 도 13의 테이블 저장부(TST)는 다수의 서브 테이블(예를 들어, 제1 서브 테이블(STABL1) 및 제2 서브 테이블(STABL2))을 저장할 수 있다. 각 서브 테이블(STAB1, STABL2)은 전술된 제1 테이블(TBAL1)의 생성 방법에 의해 생성될 수 있다.
청크 데이터(CDTA)를 압축하고자 하는 압축률에 따라 제1 서브 테이블(STABL1) 및 제2 서브 테이블(STABL2) 중 하나가 선택될 수 있다. 예를 들어, 제1 서브 테이블(STABL1)이 도 9의 제1 테이블(TBAL1)과 같고, 제2 서브 테이블(STABL2)이 도 14의 제2 테이블(TBAL2)과 같은 경우, 청크 데이터(CDTA)의 압축률을 더 높게 하기 위해서는, 각 심볼(SYM)의 발생 빈도수(NUM)에 대한 부호어 길이(LEN2)가 제1 서브 테이블(STABL1)에서의 부호어 길이(LEN1)보다 짧은 제2 서브 테이블(STABL2)이 선택될 수 있다.
도 14의 제2 테이블(TBAL2)을 이용하는 경우, 전술된 예에서, 부호어 길이 결정부(CLD)는 3번 발생한 심볼 "0000000011111111"의 부호어 길이(LEN2)를 8로 결정하고, 90번 발생된 심볼 "0101010101010101"에 대한 부호어 길이(LEN2)를 3으로 결정할 것이다.
서브 테이블의 선택(S1243)은 데이터 수신부(DREV)로부터 전송되는 선택 신호(XSST)에 응답하여 수행될 수 있다. 선택 신호(XSST)는 청크 데이터(CDTA)를 압축시키고자 하는 압축율과 서브 테이블의 관계에 대한 정보를 포함할 수 있다. 도 13은 선택 신호(XSST)가 데이터 수신부(DREV)로부터 전송되는 것으로 도시하고 있으나, 이에 한정되는 것은 아니다. 선택 신호(XSST)는 부호어 길이 결정부(CLD)의 테이블 저장부(TST)에 대한 요청(REQ)에 포함되어, 테이블 저장부(TST)에 전송될 수도 있다. 또는, 선택 신호(XSST)는 외부의 호스트(미도시) 또는 컨트롤러(미도시) 등으로부터 전송될 수도 있다.
도 12 및 도 13에서는 청크 데이터를 압축하고자 하는 압축율에 따라 테이블을 선택하는 예를 도시하였다. 다만, 이에 한정되는 것은 아니다.
본 발명의 다른 실시예에 따른 솔리드 스테이트 드라이브에서의 데이터 압축 방법(1500)을 나타내는 도 15 및 도 15의 데이터 압축 방법으로 데이터를 압축하는 데이터 압축기(DCT)를 나타내는 도 16을 참조하면, 데이터 수신부(DREV)로 수신되는 청크 데이터(CDTA)를 제1 유형의 제1 청크 데이터(CDTA1) 및 제2 유형의 제2 청크 데이터(CDTA2) 중 하나로 분류(S1520)하여, 제1 유형의 제1 청크 데이터(CDTA1)인 경우(S1540의 "예") 제1 청크 데이터(CDTA1)에 포함되는 각 심볼(SYM)의 발생 빈도수(NUM)와 부호어 길이(LEN)와의 관계를 나타내는 제1 테이블(TBAL1)을 이용하여 제1 청크 데이터(CDTA1)를 압축한다(S1560). 반면, 제2 유형의 제2 청크 데이터(CDTA2)인 경우(S1540의 "아니오"), 제2 청크 데이터(CDTA2)에 포함되는 각 심볼(SYM)의 발생 빈도수(NUM)와 부호어 길이(LEN)와의 관계를 나타내는 제2 테이블(TBAL2)을 이용하여, 제2 청크 데이터(CDTA2)를 압축할 수 있다(S1580).
도 16의 테이블 저장부(TST)는 제1 테이블(TBAL1) 및 제2 테이블(TBAL2)을 저장할 수 있다. 테이블 저장부(TST)는 부호어 길이 결정부(CLD)의 요청(REQ)이 수신되는 때에, 청크 데이터(CDTA)의 데이터 특성을 나타내는 특성 신호(XFACT)에 응답하여 해당 심볼의 발생 빈도수에 대응되는 제1 테이블(TBAL1)의 제1 부호어 길이(LEN1) 및 제2 테이블(TBAL2)의 제2 부호어 길이(LEN1) 중 하나를 부호어 길이 결정부(CLD)로 전송할 수 있다. 도 16은 특성 신호(XFACT)가 데이터 수신부(DREV)로부터 전송되는 것으로 도시하고 있으나, 이에 한정되는 것은 아니다. 후술되는 바와 같이, 청크 데이터(CDTA)의 헤더(HD)에서 검출되는 정보로부터 생성되는 특성 신호(XFACT)는 부호어 길이 결정부(CLD)의 테이블 저장부(TST)에 대한 요청(REQ)에 포함되어, 테이블 저장부(TST)에 전송될 수도 있다.
즉, 도 15 및 도 16의 실시예에 의하면, 청크 데이터(CDTA)의 데이터 특성에 따라 테이블(부호어의 길이)을 달리 선택할 수 있다. 이때, 청크 데이터(CDTA)의 데이터 특성은, 청크 데이터(CDTA)를 구성하는 도 17의 헤더(HD)에 포함되는 정보로부터 검출될 수 있다. 청크 데이터(CDTA)의 헤더(HD)는 플래시 메모리(MEM)에 저장하고자 하는 데이터(DDTA)의 디코딩 방식, 또는 디코딩된 데이터(DDTA)의 크기 등에 대한 정보를 포함할 수 있다. 솔리드 스테이트 드라이브(SSD)에서 사용되는 압축의 단위가 다양할 수 있는데, 이러한 경우에 청크 데이터(CDTA)의 크기(또는 디코딩된 데이터(DDTA))가 달라질 수 있다. 헤더(HD)에 포함된 정보는 청크 데이터(CDTA)의 데이터 특성으로 인식될 수 있다.
전술한 바와 같이, 도 15 및 도 16의 실시예에서, 청크 데이터(CDTA)의 데이터 특성을 나타내는 특성 신호(XFACT)에 응답하여 테이블이 선택될 수 있는데, 예를 들어, 제1 청크 데이터(CDTA1)의 디코딩된 데이터(DDTA)가 제2 청크 데이터(CDTA2)의 디코딩된 데이터(DDTA)보다 큰 경우, 각 심볼의 발생 빈도수에 대응되는 부호어 길이가 더 긴 제1 테이블(TBAL1)이 선택될 수 있을 것이다.
도 18은 본 발명의 실시예에 따른 컴퓨팅 시스템 장치를 나타내는 블럭도이다.
본 발명의 실시예에 따른 컴퓨팅 시스템 장치(CSYS)는 버스(BUS)에 전기적으로 연결된 프로세서(CPU), 사용자 인터페이스(UI) 및 솔리드 스테이트 드라이브(SSD)를 구비한다. 솔리드 스테이트 드라이브(SSD)는 SSD 컨트롤러(SCTRL) 및 플래시 메모리(MEM)를 포함한다. 플래시 메모리 (MEM)에는 프로세서(CPU)에 의해서 처리된 또는 처리될 N-비트 데이터(N은 1 또는 그 보다 큰 정수)가, SSD 컨트롤러(SCTRL)를 통해, 저장될 것이다. 도 18의 솔리드 스테이트 드라이브(SSD)는 도 2의 솔리드 스테이트 드라이브(SSD)일 수 있다.
본 발명의 실시예에 따른 컴퓨팅 시스템 장치(CSYS)는 파워 공급 장치(PS)를 더 구비할 수 있다. 또한, 본 발명의 실시예에 따른 컴퓨팅 시스템 장치(CSYS)는 시스템 메모리(예를 들어, RAM)을 더 구비할 수 있다.
본 발명의 실시예에 따른 컴퓨팅 시스템 장치(CSYS)가 모바일 장치인 경우, 컴퓨팅 시스템의 동작 전압을 공급하기 위한 배터리 및 베이스밴드 칩셋(baseband chipset)과 같은 모뎀이 추가적으로 제공될 수 있다. 또한, 본 발명의 실시예에 따른 컴퓨팅 시스템 장치(CSYS)에는 응용 칩셋(application chipset), 카메라 이미지 프로세서(Camera Image Processor: CIS), 모바일 디램, 등이 더 제공될 수 있음은 이 분야의 통상적인 지식을 습득한 자들에게 자명한 사항인 바, 더 자세한 설명은 생략한다.
이상에서와 같이 도면과 명세서에서 최적 실시예가 개시되었다. 여기서 특정한 용어들이었으나, 이는 단지 본 발명을 설명하기 위한 목적에서 사용된 것이지 의미 한정이나 특허청구범위에 기재된 본 발명의 범위를 제한하기 위하여 사용된 것은 아니다. 그러므로 본 기술분야의 통상의 지식을 가진 자라면 이로부터 다양한 변형 및 균등한 타 실시예가 가능하다는 점을 이해할 것이다. 따라서, 본 발명의 진정한 기술적 보호범위는 첨부된 특허청구범위의 기술적 사상에 의해 정해져야 할 것이다.

Claims (10)

  1. 저장 장치에서의 데이터 압축 방법에 있어서,
    청크(chunk) 데이터의 심볼의 발생 빈도수와 부호어 길이와의 관계를 나타내는 제1 테이블을 이용하여 상기 심볼에 대한 부호어 길이를 결정하고, 상기 부호어 길이를 갖고 상기 심볼에 대응되는 부호어를 결정하는 단계; 및
    상기 심볼을 상기 부호어로 변환하여 상기 청크 데이터에 대한 압축 데이터를 생성하는 단계를 구비하는 것을 특징으로 하는 데이터 압축 방법.
  2. 제1 항에 있어서, 상기 청크 데이터를 압축하는 단계는,
    상기 청크 데이터의 상기 심볼의 발생 빈도수를 카운트 하는 단계;
    상기 제1 테이블 상에 상기 심볼의 발생 빈도수에 대응되는 부호어 길이를 검색하여 결정하는 단계; 및
    상기 부호어 길이에 대응되는 부호어를 결정하여, 상기 심볼을 상기 부호어로 변환하는 단계를 구비하는 것을 특징으로 하는 데이터 압축 방법.
  3. 제1 항에 있어서,
    상기 제1 테이블을 형성하는 단계를 더 구비하는 것을 특징으로 하는 데이터 압축 방법.
  4. 제3 항에 있어서, 상기 제1 테이블을 형성하는 단계는,
    테스트 데이터를 수신하는 단계; 및
    상기 테스트 데이터의 각 심볼의 발생 빈도의 확률을 산출하는 단계;
    상기 테스트 데이터의 각 심볼의 발생 빈도의 확률을 정렬하여 허프만 트리를 생성하는 단계; 및
    상기 테스트 데이터에 대한 상기 허프만 트리에 근거하여, 상기 테스트 데이터의 각 심볼과 상기 각 심볼에 대응되는 부호어 길이를 매치하는 단계를 구비하는 것을 특징으로 하는 데이터 압축 방법.
  5. 제3 항에 있어서, 상기 테스트 데이터는,
    상기 청크 데이터와 압축률, 디코딩 방식 및 크기 중 적어도 하나가 동일한 것을 특징으로 하는 데이터 압축 방법.
  6. 제1 항에 있어서, 상기 제1 테이블은,
    상기 각 심볼과 상기 부호어의 길이와의 제1 관계에 대한 제1 서브 테이블 및 상기 각 심볼과 상기 부호어의 길이와의 제2 관계에 대한 제2 서브 테이블을 포함하는 것을 특징으로 하는 데이터 압축 방법.
  7. 제6 항에 있어서, 상기 청크 데이터를 압축하는 단계는,
    상기 제1 서브 테이블 및 상기 제2 서브 테이블 중 하나를 선택하는 단계; 및
    상기 제1 서브 테이블 및 상기 제2 서브 테이블 중 선택된 서브 테이블을 이용하여 상기 부호어의 길이를 결정하는 단계를 구비하는 것을 특징으로 하는 데이터 압축 방법.
  8. 제7 항에 있어서, 상기 서브 테이블을 선택하는 단계는,
    상기 청크 데이터를 압축하고자 하는 압축률에 따라 상기 서브 테이블을 선택하는 것을 특징으로 하는 데이터 압축 방법.
  9. 제1 항에 있어서, 상기 저장 장치는,
    솔리드 스테이트 드라이브(Solid State Drive)인 것을 특징으로 하는 데이터 압축 방법.
  10. 저장 장치에서의 데이터 압축 방법에 있어서,
    청크 데이터를 제1 유형의 제1 청크 데이터 및 제2 유형의 제2 청크 데이터 중 하나로 분류하는 단계;
    상기 제1 청크 데이터의 각 심볼의 발생 빈도수와 부호어의 길이와의 관계를 나타내는 제1 테이블을 이용하여 상기 제1 청크 데이터의 각 심볼에 대응되는 부호어 길이를 결정하고, 상기 제1 청크 데이터의 각 심볼을 대응되는 부호어의 길이를 갖는 부호어로 변환하여 상기 제1 청크 데이터를 압축하는 단계; 및
    상기 제2 청크 데이터에 포함되는 각 심볼의 발생 빈도수와 부호어의 길이와의 관계를 나타내는 제2 테이블을 이용하여 상기 제2 청크 데이터의 각 심볼에 대응되는 부호어 길이를 결정하고, 상기 제2 청크 데이터의 각 심볼을 대응되는 부호어의 길이를 갖는 부호어로 변환하여 상기 제2 청크 데이터를 압축하는 단계를 구비하는 것을 특징으로 하는 데이터 압축 방법.
KR1020110027176A 2011-03-25 2011-03-25 저장 장치에서의 데이터 압축 방법 Active KR101725223B1 (ko)

Priority Applications (2)

Application Number Priority Date Filing Date Title
KR1020110027176A KR101725223B1 (ko) 2011-03-25 2011-03-25 저장 장치에서의 데이터 압축 방법
US13/364,787 US8593307B2 (en) 2011-03-25 2012-02-02 Methods of compressing data in storage device

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
KR1020110027176A KR101725223B1 (ko) 2011-03-25 2011-03-25 저장 장치에서의 데이터 압축 방법

Publications (2)

Publication Number Publication Date
KR20120109753A true KR20120109753A (ko) 2012-10-09
KR101725223B1 KR101725223B1 (ko) 2017-04-11

Family

ID=46876896

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1020110027176A Active KR101725223B1 (ko) 2011-03-25 2011-03-25 저장 장치에서의 데이터 압축 방법

Country Status (2)

Country Link
US (1) US8593307B2 (ko)
KR (1) KR101725223B1 (ko)

Cited By (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR101531661B1 (ko) * 2013-11-19 2015-06-26 서울대학교산학협력단 비휘발성 메모리 장치, 이를 위한 메모리 제어기 및 동작 방법
KR20160021004A (ko) * 2014-08-15 2016-02-24 김정훈 이진 데이터의 압축 및 복원 방법과 장치
KR20160021416A (ko) * 2014-08-17 2016-02-25 김정훈 이진 데이터의 압축 및 복원 방법과 장치
KR20170019556A (ko) * 2015-08-11 2017-02-22 삼성전자주식회사 스토리지 장치로부터 데이터를 검색하는 방법
KR20180067956A (ko) * 2016-12-13 2018-06-21 에스케이텔레콤 주식회사 데이터 압축 장치 및 방법
US10810016B2 (en) 2015-08-11 2020-10-20 Samsung Electronics Co., Ltd. Operating methods of computing devices comprising storage devices including nonvolatile memory devices, buffer memories and controllers

Families Citing this family (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8847798B2 (en) * 2012-12-17 2014-09-30 Maxeler Technologies, Ltd. Systems and methods for data compression and parallel, pipelined decompression
US9430326B2 (en) * 2014-07-22 2016-08-30 HGST Netherlands B.V. Multiple ECC codeword sizes in an SSD
US10152389B2 (en) 2015-06-19 2018-12-11 Western Digital Technologies, Inc. Apparatus and method for inline compression and deduplication
US9552384B2 (en) 2015-06-19 2017-01-24 HGST Netherlands B.V. Apparatus and method for single pass entropy detection on data transfer
US11232075B2 (en) * 2018-10-25 2022-01-25 EMC IP Holding Company LLC Selection of hash key sizes for data deduplication
US10509676B1 (en) * 2018-10-29 2019-12-17 EMC IP Holding Company LLC Techniques for optimizing entropy computations
CN113572479B (zh) * 2021-09-22 2021-12-21 苏州浪潮智能科技有限公司 一种有限状态熵编码表的生成方法及系统
CN118838292B (zh) * 2024-09-20 2024-12-03 武汉优力克自动化系统工程股份有限公司 一种汽车生产线数据管理方法及系统

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6636167B1 (en) * 2000-10-31 2003-10-21 Intel Corporation Method of generating Huffman code length information
US6646577B2 (en) * 2000-10-31 2003-11-11 Intel Corporation Method of performing Huffman decoding
US7071853B2 (en) * 2000-09-28 2006-07-04 Roke Manor Research Limited Method of compressing data packets
US7375660B1 (en) * 2006-11-24 2008-05-20 Primax Electronics Ltd. Huffman decoding method

Family Cites Families (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4646061A (en) * 1985-03-13 1987-02-24 Racal Data Communications Inc. Data communication with modified Huffman coding
US4899149A (en) * 1986-02-28 1990-02-06 Gary Kahan Method of and apparatus for decoding Huffman or variable-length coees
KR0139162B1 (ko) 1994-11-30 1998-05-15 김광호 부호어재배정을 이용한 가변장부호화장치 및 복호화장치
JP3659196B2 (ja) 2001-06-18 2005-06-15 ヤマハ株式会社 ハフマン符号の復号方法および装置
US7436329B2 (en) 2003-04-17 2008-10-14 Droplet Technology, Inc. Multiple technique entropy coding system and method

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7071853B2 (en) * 2000-09-28 2006-07-04 Roke Manor Research Limited Method of compressing data packets
US6636167B1 (en) * 2000-10-31 2003-10-21 Intel Corporation Method of generating Huffman code length information
US6646577B2 (en) * 2000-10-31 2003-11-11 Intel Corporation Method of performing Huffman decoding
US7375660B1 (en) * 2006-11-24 2008-05-20 Primax Electronics Ltd. Huffman decoding method

Cited By (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR101531661B1 (ko) * 2013-11-19 2015-06-26 서울대학교산학협력단 비휘발성 메모리 장치, 이를 위한 메모리 제어기 및 동작 방법
KR20160021004A (ko) * 2014-08-15 2016-02-24 김정훈 이진 데이터의 압축 및 복원 방법과 장치
KR20160021416A (ko) * 2014-08-17 2016-02-25 김정훈 이진 데이터의 압축 및 복원 방법과 장치
KR20170019556A (ko) * 2015-08-11 2017-02-22 삼성전자주식회사 스토리지 장치로부터 데이터를 검색하는 방법
US10621171B2 (en) 2015-08-11 2020-04-14 Samsung Electronics Co., Ltd. Method for searching for data in storage device
US10810016B2 (en) 2015-08-11 2020-10-20 Samsung Electronics Co., Ltd. Operating methods of computing devices comprising storage devices including nonvolatile memory devices, buffer memories and controllers
KR20180067956A (ko) * 2016-12-13 2018-06-21 에스케이텔레콤 주식회사 데이터 압축 장치 및 방법

Also Published As

Publication number Publication date
US8593307B2 (en) 2013-11-26
US20120242517A1 (en) 2012-09-27
KR101725223B1 (ko) 2017-04-11

Similar Documents

Publication Publication Date Title
KR101725223B1 (ko) 저장 장치에서의 데이터 압축 방법
US8949687B2 (en) Memory device and memory system
US10187081B1 (en) Dictionary preload for data compression
US10680645B2 (en) System and method for data storage, transfer, synchronization, and security using codeword probability estimation
US12321596B2 (en) System and method for codebook-based data encoding
US20140040214A1 (en) Entropy Coding and Decoding Using Polar Codes
JP2021527376A (ja) データ圧縮
US12373101B2 (en) System and method for data compaction with codebook statistical estimates
US12061794B2 (en) System and method for multiple pass data compaction utilizing delta encoding
US12307089B2 (en) System and method for compaction of floating-point numbers within a dataset
US12224776B2 (en) System and method for data storage, transfer, synchronization, and security using automated model monitoring and training
KR20150092585A (ko) 이진 영상에 기반한 유전체 데이터 압축 방법 및 장치
JP2016052046A (ja) 圧縮装置、伸長装置およびストレージ装置
US12081241B2 (en) Code table generation device, memory system, and code table generation method
JP7562451B2 (ja) 圧縮装置および制御方法
JP6301459B2 (ja) 周波数エンベロープベクトル量子化方法及び装置
US12443343B2 (en) Data compaction utilizing delta encoding
US11855772B2 (en) High throughput polar ECC decoding via compressed successive cancellation algorithm
US20230315288A1 (en) System and method for data compaction and security using multiple encoding algorithms with pre-coding and complexity estimation

Legal Events

Date Code Title Description
PA0109 Patent application

Patent event code: PA01091R01D

Comment text: Patent Application

Patent event date: 20110325

PG1501 Laying open of application
A201 Request for examination
PA0201 Request for examination

Patent event code: PA02012R01D

Patent event date: 20160224

Comment text: Request for Examination of Application

Patent event code: PA02011R01I

Patent event date: 20110325

Comment text: Patent Application

E902 Notification of reason for refusal
PE0902 Notice of grounds for rejection

Comment text: Notification of reason for refusal

Patent event date: 20160630

Patent event code: PE09021S01D

E701 Decision to grant or registration of patent right
PE0701 Decision of registration

Patent event code: PE07011S01D

Comment text: Decision to Grant Registration

Patent event date: 20170117

GRNT Written decision to grant
PR0701 Registration of establishment

Comment text: Registration of Establishment

Patent event date: 20170404

Patent event code: PR07011E01D

PR1002 Payment of registration fee

Payment date: 20170405

End annual number: 3

Start annual number: 1

PG1601 Publication of registration
PR1001 Payment of annual fee

Payment date: 20200330

Start annual number: 4

End annual number: 4

PR1001 Payment of annual fee

Payment date: 20210329

Start annual number: 5

End annual number: 5

PR1001 Payment of annual fee

Payment date: 20220323

Start annual number: 6

End annual number: 6

PR1001 Payment of annual fee

Payment date: 20230327

Start annual number: 7

End annual number: 7

PR1001 Payment of annual fee

Payment date: 20240325

Start annual number: 8

End annual number: 8

PR1001 Payment of annual fee

Payment date: 20250325

Start annual number: 9

End annual number: 9