Data encoder and data encoding method

Patent metadata

Field	Value
Publication number	US-10498358-B2
Application number	US-201816181774-A
Country	US
Kind code	B2
Filing date	Nov 6, 2018
Priority date	Feb 5, 2018
Publication date	Dec 3, 2019
Grant date	Dec 3, 2019

Abstract

A data encoder including a preprocessor configured to divide a data stream into a plurality of sub data blocks; a plurality of meta data generators each configured to generate meta data from one of the plurality of sub data blocks; and a plurality of data compressors each configured to compress one of the plurality of sub data blocks according to the meta data.

First claim

What is claimed is:

1. A data encoder comprising:
a preprocessor configured to divide a data stream into a plurality of sub data blocks;
a plurality of meta data generators each configured to generate meta data from one of the plurality of sub data blocks; and
a plurality of data compressors each configured to compress one of the plurality of sub data blocks according to the meta data.

2. The data encoder of claim 1 , wherein the preprocessor divides the data stream into the plurality of sub data blocks according to entropy of each of the plurality of sub data blocks.

3. The data encoder of claim 2 , wherein the data stream includes a memory command and the preprocessor redefines don't care bits of the memory command into a high level or a low level, arranges bits of the memory command and divides the memory command into a plurality of groups.

4. The data encoder of claim 2 , wherein the data stream includes a plurality of memory commands each comprised in a row of a matrix and the preprocessor performs a transpose operation on the matrix and divides the matrix by the row into a plurality of groups.

5. The data encoder of claim 4 , wherein the preprocessor further performs a delta coding after performing the transpose operation.

6. The data encoder of claim 1 , wherein each of the meta data generators generates a frequency table storing kinds of symbols included in a sub data block and frequencies of the symbols and generates meta data corresponding to the sub data block.

7. The data encoder of claim 6 , wherein the meta data includes the kinds of the symbols and a frequency table storing the symbols sorted by frequencies of the symbols.

8. The data encoder of claim 6 , wherein each of the plurality of data compressors comprises:
a tree generating circuit configured to generate a tree structure including nodes corresponding to the symbols stored in the frequency table;
a codeword determining circuit configured to determine codewords corresponding to the symbols; and
a codeword output circuit configured to compress the sub data block according to the codewords.

9. The data encoder of claim 8 , wherein the tree generating circuit extracts two symbols with least frequency and inserts a combined symbol made from the two symbols and having a frequency corresponding to sum of frequencies of the two symbols in the frequency table.

10. The data encoder of claim 9 , wherein the codeword determining circuit designate one of the two symbols as a left node and the other of the two symbols as a right node and updates a codeword of a symbol included in the left node or the right node.

11. The data encoder of claim 10 , wherein the codeword determining circuit adds a high level bit to update a codeword of a symbol include in the left node and adds a low level bit to update a codeword of a symbol included in the right node.

12. The data encoder of claim 9 , wherein the tree generating circuit generates a bitmap indicating whether the two symbols are extracted and the codeword determining circuit identifies the two symbols with reference to the bitmap.

13. The data encoder of claim 8 , wherein the codeword output circuit includes a plurality of pipeline stages.

14. The data encoder of claim 1 , further comprising:
a compressed data output circuit configured to output a compressed data stream with an output from the plurality of meta data generators and an output from the plurality of data compressors,
wherein the compressed data output circuit includes a compressed data stream generating circuit generating a compressed data stream including a series of a plurality of meta data corresponding to the plurality of sub data blocks and a series of compressed data corresponding to the plurality of sub data blocks.

15. The data encoder of claim 14 , wherein the compressed data output circuit further comprises a packing circuit for packing the compressed data stream by a predetermined number of bits.

16. The data encoder of claim 1 , further comprising a compressed data synthesizer configured to combine a plurality of outputs from the plurality of data compressors.

17. The data encoder of claim 1 , further comprising a meta data synthesizer configured to combine a plurality of outputs from the plurality of meta data generators.

18. The data encoder of claim 17 , further comprising a plurality of meta data processors each configured to combine meta data output from corresponding one of the plurality of meta data generators.

19. A data encoding method comprising:
generating a frequency table comprising symbols and frequencies associated with the symbols;
extracting two symbols having the least frequency from the frequency table;
updating the frequency table with a combined symbol made from the two symbols and sums of frequencies of the two symbols;
storing information on the combined symbol in a bitmap;
designating one of the two symbols as a left node and the other of the two symbols as a right node; and
updating a codeword of a symbol included in the left node and updating a codeword of a symbol included in the right node with reference to the bitmap.

20. The data encoding method of claim 19 , wherein the updating a codeword of a symbol in the left node includes adding a high level bit and the updating a codeword of a symbol in the right node includes adding a low level bit.

Assignees

• Sk Hynix Inc
• Seoul Nat Univ R&Db Foundation

Inventors

• Choi Jiwoong
• Kim Boyeal
• Kim Hyun
• Lee Hyuk Jae
• Lee Junseo
• Kwak Changmin
• Song Youngdoo

Classifications

• H03M7/607 Primary

  Selection between different types of compressors · CPC title

• H03M7/6088

  according to the data type · CPC title

• G06F3/0661

  Format or protocol conversion arrangements · CPC title

• H03M7/42 Primary

  using table look-up for the coding or decoding process, e.g. using read-only memory {(H03M7/4006 takes precedence)} · CPC title

• G06F3/0673

  Single storage device · CPC title