CN108886367A - Method, apparatus and system for compression and decompression data - Google Patents
Method, apparatus and system for compression and decompression data Download PDFInfo
- Publication number
- CN108886367A CN108886367A CN201780015236.4A CN201780015236A CN108886367A CN 108886367 A CN108886367 A CN 108886367A CN 201780015236 A CN201780015236 A CN 201780015236A CN 108886367 A CN108886367 A CN 108886367A
- Authority
- CN
- China
- Prior art keywords
- data
- mask
- value
- data value
- data block
- 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
Links
- 230000006837 decompression Effects 0.000 title claims abstract description 161
- 238000007906 compression Methods 0.000 title claims abstract description 86
- 230000006835 compression Effects 0.000 title claims abstract description 86
- 238000000034 method Methods 0.000 title claims abstract description 56
- 230000015654 memory Effects 0.000 claims abstract description 55
- 238000004891 communication Methods 0.000 claims abstract description 32
- 238000013144 data compression Methods 0.000 claims description 130
- 238000003860 storage Methods 0.000 claims description 65
- 230000007246 mechanism Effects 0.000 claims description 29
- 239000000872 buffer Substances 0.000 claims description 17
- 238000004590 computer program Methods 0.000 claims description 10
- 238000003825 pressing Methods 0.000 claims description 10
- 238000004458 analytical method Methods 0.000 claims description 9
- 238000009825 accumulation Methods 0.000 claims description 8
- 239000000284 extract Substances 0.000 claims description 5
- 235000013399 edible fruits Nutrition 0.000 claims description 4
- 230000008878 coupling Effects 0.000 claims description 2
- 238000010168 coupling process Methods 0.000 claims description 2
- 238000005859 coupling reaction Methods 0.000 claims description 2
- GOLXNESZZPUPJE-UHFFFAOYSA-N spiromesifen Chemical compound CC1=CC(C)=CC(C)=C1C(C(O1)=O)=C(OC(=O)CC(C)(C)C)C11CCCC1 GOLXNESZZPUPJE-UHFFFAOYSA-N 0.000 claims description 2
- 238000007689 inspection Methods 0.000 claims 1
- 239000000203 mixture Substances 0.000 claims 1
- 230000005540 biological transmission Effects 0.000 abstract description 12
- 238000001514 detection method Methods 0.000 description 23
- 238000010586 diagram Methods 0.000 description 20
- 238000012545 processing Methods 0.000 description 20
- 230000001419 dependent effect Effects 0.000 description 7
- 238000002156 mixing Methods 0.000 description 7
- 238000013461 design Methods 0.000 description 6
- 230000006870 function Effects 0.000 description 4
- 238000012546 transfer Methods 0.000 description 4
- 230000008901 benefit Effects 0.000 description 3
- 238000006073 displacement reaction Methods 0.000 description 3
- 238000005516 engineering process Methods 0.000 description 3
- 238000000605 extraction Methods 0.000 description 3
- 230000008569 process Effects 0.000 description 3
- 238000006467 substitution reaction Methods 0.000 description 3
- 230000009471 action Effects 0.000 description 1
- 238000000151 deposition Methods 0.000 description 1
- 238000009826 distribution Methods 0.000 description 1
- 230000002708 enhancing effect Effects 0.000 description 1
- 230000006872 improvement Effects 0.000 description 1
- 238000003780 insertion Methods 0.000 description 1
- 230000037431 insertion Effects 0.000 description 1
- 230000014759 maintenance of location Effects 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
- 238000004321 preservation Methods 0.000 description 1
- 230000003362 replicative effect Effects 0.000 description 1
- 239000007787 solid Substances 0.000 description 1
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F12/00—Accessing, addressing or allocating within memory systems or architectures
- G06F12/02—Addressing or allocation; Relocation
- G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
- G06F12/0802—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
-
- 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/46—Conversion to or from run-length codes, i.e. by representing the number of consecutive digits, or groups of digits, of the same kind by a code word and a digit indicative of that kind
- H03M7/48—Conversion to or from run-length codes, i.e. by representing the number of consecutive digits, or groups of digits, of the same kind by a code word and a digit indicative of that kind alternating with other codes during the code conversion process, e.g. run-length coding being performed only as long as sufficientlylong runs of digits of the same kind are present
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F12/00—Accessing, addressing or allocating within memory systems or architectures
- G06F12/02—Addressing or allocation; Relocation
- G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
- G06F12/0802—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
- G06F12/0806—Multiuser, multiprocessor or multiprocessing cache systems
- G06F12/0811—Multiuser, multiprocessor or multiprocessing cache systems with multilevel cache hierarchies
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR 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/0602—Interfaces specially adapted for storage systems specifically adapted to achieve a particular effect
- G06F3/0608—Saving storage space on storage systems
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR 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/0628—Interfaces specially adapted for storage systems making use of a particular technique
- G06F3/0638—Organizing or formatting or addressing of data
- G06F3/064—Management of blocks
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR 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/0628—Interfaces specially adapted for storage systems making use of a particular technique
- G06F3/0655—Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices
- G06F3/0659—Command handling arrangements, e.g. command buffers, queues, command scheduling
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR 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
-
- 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
-
- 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
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
- H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
- H04N19/10—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding
- H04N19/102—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding characterised by the element, parameter or selection affected or controlled by the adaptive coding
- H04N19/13—Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
- H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
- H04N19/90—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using coding techniques not provided for in groups H04N19/10-H04N19/85, e.g. fractals
- H04N19/91—Entropy coding, e.g. variable length coding [VLC] or arithmetic coding
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F2212/00—Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
- G06F2212/40—Specific encoding of data in memory or cache
- G06F2212/401—Compressed data
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR 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/0628—Interfaces specially adapted for storage systems making use of a particular technique
- G06F3/0655—Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices
- G06F3/0656—Data buffering arrangements
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)
- Multimedia (AREA)
- Signal Processing (AREA)
- Compression, Expansion, Code Conversion, And Decoders (AREA)
Abstract
Method, apparatus and system extend compressor and decompressor to code and decode for data in cache/memories/data transmission sub-system to computer system or in communication network.Example variable-length compressor and decompressor be extended with new feature with：It is more densely packed compressed when occurring in the specific position of particular value within the data block；Improve compression and decompression delay when there is the particular value frequently occurred in data block；Also postponed by recording the length of the value of the variable length code of compressed data block to improve decompression.The compressor and decompressor are extended to support the compression and decompression for the common compression situation being used in combination with variable-length compression, to improve compressibility in cache/memories/data transmission sub-system of computer system or in communication network.
Description
Technical field
Present disclosure generally relates to the fields of data compression and decompression, for example, computer system caching/deposit
Data compression and decompression in reservoir subsystem and/or in data transmission sub-system or in data communication system.
Background technique
Data compression is for reducing the more mature technology of one kind of size of data.It is applied to be stored in department of computer science
Data in the memory sub-system of system are to increase storage capacity.When data pass between the different sub-systems in computer system
When defeated, or usually when carrying out the transmission between two points in the data communication system for including communication network, data
Compression is also used.
Data compression needs two basic operations：1) compression (also referred to as encoding), compression is to make unpressed data
For input, and by will be uncompressed with corresponding code word (be also referred to as encode in the literature, character code or code) replacement data value
Data be converted to compressed data；And 2) decompression (also referred to as decode), decompression be using compressed data as
It inputs and unpressed by being converted to the compressed data with corresponding data value replacement code word.Data compression can be with
It is lossless formula or damages formula, this depends on whether that the raw value before actual data value and compression after decompression is complete
Exactly the same (lossless formula), or depend on whether that the data value after decompression is different from raw value and original value can not obtain
(damaging formula).It can implement compression and decompression with the combination of software or hardware or software and hardware, it is corresponding to realize
Method, apparatus and system.
Fig. 1 depicts the example of computer system 100.Computer system 100 includes using communication device such as Internet
Network is connected to one or several processing lists of storage hierarchy (memory hierarchy, memory hierarchy) 110
First P1 ... Pn.Each processing unit includes processor (or core), and each processing unit can be CPU (central processing
Unit), GPU (graphics processing unit) or be usually execute calculate block.On the other hand, storage hierarchy 110 is constituted
The storage subsystem of computer system 100, and including can be with one or several ranks (level, level, grade) L1-L3
Carry out the buffer memory 120 and memory 130 (also known as primary memory) of tissue.Memory 130 may be also connected to secondary
Grade storage device (for example, hard disk drive, solid state drive or flash memory).Memory 130 can be organized into several ranks, example
Such as, fast, primary memory (for example, DDR) and flash memory.Buffer memory 120 in instant example includes three ranks, wherein L1
It is dedicated cache with L2, because each processing unit P1-Pn is connected to specified L1/L2 caching, and L3 is in all processing
It is shared between unit P1-Pn.In the processing unit with different number and normally with processing unit and memory subsystem
In the case where various combination between system, alternative example, which may be implemented to have, does not have cache level more, less or even
Different cache hierarchies other and with or without dedicated or shared specified caching, realize various storage levels
Not, everything is all easy to accomplish by technical staff.
It can be in different ways by data compression applications in computer system.Fig. 2 depicts computer system such as Fig. 1
System 100 example 200, wherein data are compressed in the memory such as main memory of this computer system.
This means that by corresponding squeeze operation as described above, data are through compressing before being stored in memory, and data exist
It is decompressed when leaving memory.
In the alternate example 300 of computer system shown in Fig. 3, the L3 that data compression can be applied to caching system is slow
It deposits.It similar to previous example, needs to be compressed before data are stored in caching, and needs to leave caching in data
(for example, go thereto data be it is unpressed other caching rank (L2) or memory 330) before unzip it.It is substituting
In example, data can be stored in a compressed format in any rank of cache hierarchy.
Only it can also be compressed when being transmitted between data different sub-systems in computer systems.?
In the alternate example 400 of computer system shown in Fig. 4, when using corresponding communication device L3 caching with memory 430 it
Between transmit data when, data are compressed.Similar to previous example, need to have compression reconciliation in the end of communication device
Compression before transmitting the data to compress data, and is to solve data when receiving data at the other end
Compression.
In the alternate example 500 of computer system, data compression can be applied to the group of subsystem as depicted in figures 5
In conjunction.In this example, when data are stored in memory 530 and when data are in memory 530 and caching level knot
When transmitting between structure 520, data are compressed.In this way, when data are moved to memory 530 from cache hierarchy 520,
It can only need to compress it before L3 caching transfer in data.Alternatively, leaving memory 530 goes to caching level knot
The compressed data of structure 520 can only need to connect memory 530 with cache hierarchy 520 being received
It is decompressed when the other end of communication device.About the combination that will compress the different sub-systems being applied in computer system, appoint
What example is all feasible, and can be realized by those skilled in the art.
It can also carry out data transmission between two arbitrary points in communication network.Fig. 6 is depicted including between two o'clock
Communication network 605 data communication system 600 example, wherein data are transmitted by transmitter 610 and are connect by receiver 620
It receives.In such an example, these points can be the source node and purpose of two intermediate nodes or communication link in network
The combination of ground node or these situations.Data compression can be applied to data as example system 700 as depicted in figure 7
Communication system.Applied compression is needed before data are launched on communication network 705 by transmitter 710, and in data quilt
Receiver 720 is needed after receiving using decompression.
Realize that data compression there are a variety of different algorithms.Family in data compression algorithm is statistics compression algorithm, the system
Meter compression algorithm is data dependence and can provide compression efficiency close to entropy, because the statistics compression algorithm is based on number
Variable-length (also referred to as variable-width) code is distributed according to the statistical property of value：Short code word is used for the data value frequently occurred
It is encoded, and longer code word encodes the data value less frequently occurred.Huffman coding is known statistics
Compression algorithm.
Known modification for accelerating the huffman coding of decompression is canonical Huffman coding.Based on this, code word has
Serial No. attribute, it means that the code word of equal length is continuous integer.
The example of the compression and decompression mechanism based on canonical Huffman is proposed in the prior art.This compression reconciliation
Compression mechanism can be used in example above-mentioned to realize the compression and decompression based on Huffman.
Fig. 9, which is shown, implements the huffman coding such as compressor 900 from the prior art of canonical Huffman coding
Example.By unpressed piece as input, described unpressed piece is burst of data value and is included in entire sheet the compressor
Be typically expressed as in disclosure v1, v2 ..., one or more data values of vn.Unit 910 --- it is single that it can be storage
Member or the extractor for extracting data value from unpressed piece --- data value is provided to variable length coding unit 920.
Variable length coding unit 920 includes code table (CT) 922 and code word (CW) selector 928.CT 922 is to may be embodied as searching
The table of table (LUT) or Computer Cache memory (with any arbitrary correlation), and include one or more entries；Often
A entry includes the value 923 that code word can be used to compress, CW 925 and code word size (cL) 927.Due to counting compression algorithm
Used various code word sets are variable-lengths, so when saving it in width (code of each entry with fixed size
Word 925) CT 922 in when, it is necessary to zero to these code word sets carry out mend fill out.Code word size 927 keeps variable length code
Physical length (for example, as unit of position).CW selector 928 is identified actual CW using cL and gives up zero for mending and filling out.
Then the value of coding is linked to the rest part of compressed value, be formed together compressed piece.It depicts and abides by Figure 27
According to the exemplary process diagram of the compression method of previously described compression step.
The example of decompressor 1000 in the prior art is shown in Figure 10.Canonical Huffman decompression can be divided into two
A step：Codeword detection and value retrieval (retrieve is obtained, restores, fetched).Each of these steps are all by following
One of unit is implemented：(1) codeword detection unit (CDU) 1020 and (2) value retrieval unit (VRU) 1030.CDU's 1020
Purpose is to find effective code word in compressed sequence (that is, sequence of the code word of compressed data value).CDU 1020
Including one group of comparator 1022 and priority encoder 1024.Each comparator 1022a, 1022b, 1022c will be each potential
Bit sequence (bit-sequence, bit sequence) is compared with known code word, and the known code word is specific length in this example
(when code generates) the canonical Huffman code word (FCW) of degree distributed for the first time.In substitution is implemented, last distribution also can be used
Canonical Huffman code word, but in this case, the definite comparison done will be different.Above-mentioned bit sequence to be compared can
To be stored in storage unit 1010 (such as being embodied as FIFO or trigger) and determine the quantity and position sequence of comparator
The largest amount of the maximum width of most wide person in column, bit sequence to be compared depends on the effective Hough determined when code generates
The maximum length (mCL) of graceful code word.However, depending on the selected implementation of this decompressor (for example, with software or with hard
Part), the maximum length can be restricted to particular value in design, compiling, configuration or runing time.By the defeated of comparator 1022
It is inserted into the priority encoder such as structure 1024 out, the length which exports the matched code word (is being schemed
It is known as " matched length " in 10).Based on this, extracted from the bit sequence for being stored in storage unit 1010 detected effective
Code word (matched code word)；By bit sequence displacement and position as many defined by " matched length ", and by vacant portion
Load is divided to allow CDU 1020 to determine next effective code word at the subsequent bit of compressed sequence.
On the other hand, value retrieval unit (VRU) 1030 includes that offset table 1034, subtractor unit 1036 and decompression are searched
Table (DeLUT) 1038.Being determined using " matched length " from previous step must be from the also determination in previous step
The deviant (being stored in offset table 1034) of (1036) is subtracted in the arithmetic value of the matched code word, to obtain DeLUT 1038
Address, wherein the raw value corresponding to the code word detected, which can be obtained and is attached to from DeLUT, is stored in decompression
Remaining decompressed value in contracting block 1040.Repeat decompressor operation, until be stored in a compressed format inputted through pressing
All values in the sequence (in Figure 10 be known as compressed piece) of contracting be restored to unpressed data value v1, v2 ..., vn.
Figure 28 depicts the exemplary process diagram of the decompression method in accordance with previously described decompression step.
Compressor and decompressor noted earlier can use variable-length canonical Huffman coding quickly and efficiently
Compress blocks of data and decompress using variable-length canonical Huffman coding compression data block.However, in the decompression phase
Between the codeword detection stage be inherently orderly so that decompression it is very slow；Although teaching in prior art how by its parallelization,
But implementation is complicated and is added to many area overheads or needs a large amount of computing resource.When pressure will be counted
When contracting is applied to the computer system or communication network of previous examples, this is a kind of challenge.In addition, although aforementioned have statistics pressure
The compressor of compression algorithm can effectively compress most frequent value, but decompressor is all worked with same speed but regardless of through pressing
The data of contracting are frequent or infrequently.In addition, when in the normal place for the stream that the frequent value appears in value, pressure
Contracting device is less effective.The present inventors have realized that there are improved skies in the technical field of data compression and decompression
Between.
Summary of the invention
It is an object of the invention to improvement is provided in the technical field of data compression and decompression.
Present disclosure, which generally discloses to work as to compress, to be applied in such as data communication system and/or computer system
Cache subsystem and/or memory sub-system and/or when data transmission sub-system, be used for compressed data value block and decompression
The method, apparatus and system of compressed data value block.There are various modes come use in said subsystem based on entropy can
Become length coding effectively compressed data, and a kind of such mode is by using huffman coding.Existing compressor
It is used for huffman coding compressed data value block, while existing decompressor can be used for decompressing using Huffman
Encode the block of the data of compression.However, the decompression of the sequence of variable length code is inherently orderly and at this
Determine that the data value of huffman coding is very slow in compressed piece of sample, because the value of huffman coding is variable-length code (VLC)
Word；Therefore, their boundary is unknown.In addition, the speed of existing decompressor be it is identical, with compressed piece whether
It is unrelated including frequent or infrequently compressed value, and when most frequent value appears in standard setting/position in block
When middle, existing compressor is also less effective.Disclosed method, apparatus and system utilize below in this disclosure
New feature enhances existing compressor and decompressor using variable length code：When particular value occurs within the data block
When in specific position, more densely packed compress；When the particular value frequently occurred occurs within the data block, improve compression and decompression
Delay；Also improve decompression delay by recording the length of the value of the variable length code of compressed data block.In addition, being mentioned
Method, apparatus and system out are even further by respectively and being directed to the department of computer science for the compressor and decompressor
Other aggressive compressors and decompressor of common compression situation in system and communication system combine to make its enhancing.
The first aspect of the invention is a kind of data compression device, for that will include the unpressed number of n data value
According to the compressed data block of block boil down to, which includes：
Compressor, the compressor are configured to the corresponding variable-length code (VLC) of data value boil down to of unpressed data block
Word；
Detector, the detector are configured to detect at least one particular data value depositing in unpressed data block
?；And
Compressed data block generator, the compressed data block generator coupled with compressor and detector and by
It is configured to by being combined to generate compressed data block by following：
Data value mask, the data value mask include n mask position, wherein each mask position instruction is uncompressed
Data block in corresponding data value whether with as the detector detect described at least one particular data value
Any one particular data value is equal；And
For in unpressed data block with the unequal data value of at least one particular data value, by compressing
Device carries out compressing resulting corresponding variable length codeword,
Wherein, compressed data block includes data value mask and m variable length codeword, wherein m≤n, and its
In, it does not include in unpressed data block and at least one described particular data value in compressed data block
The variable length codeword of the equal data value of any one particular data value.
In some embodiments, detector is configured to detect a particular data value in unpressed data block
In the presence of, wherein each mask position in n mask position of data value mask includes single position.In other embodiment party
In formula, detector is configured to detect presence of multiple and different particular data values in unpressed data block, wherein data
Each mask position in n mask position of value mask includes can be to any one certain number in multiple particular data values
According to the bit combination for the fixed size that value is encoded.
In some embodiments, it is somebody's turn to do or each particular data value is the data value frequently occurred, if replacing ground
Using variable length code, then the data value frequently occurred can use the smallest position and be encoded.Advantageously, such spy
Determining data value is 0 (zero).Alternatively, it is somebody's turn to do or each particular data value can require quickly to solve very much when present
The data value of compression.
With reference to Figure 16 and Figure 18 to the preferred embodiment of data compression device according to the first aspect of the invention
In addition feature is described, and in addition, is defined in the appended dependent claims 7-11 submitted together with this.This
The second aspect of invention is a kind of corresponding data compression method, for that will include the unpressed of scheduled n data value
The compressed data block of data block boil down to, the data compression method include：
By the corresponding variable length codeword of data value boil down to of unpressed data block；
Detect presence of at least one particular data value in unpressed data block；And
By being combined to generate compressed data block by following：
Data value mask, the data value mask include n mask position, wherein each mask position instruction is uncompressed
Data block in corresponding data value it is whether equal with any one particular data value at least one described particular data value；
And
For in unpressed data block with any one particular data value at least one described particular data value
All unequal data value, corresponding variable length codeword,
Wherein, compressed data block includes data value mask and m variable length codeword, wherein m≤n, and its
In, it does not include in unpressed data block and at least one described particular data value in compressed data block
The variable length codeword of the equal data value of any one particular data value.
Data compression method according to the second aspect of the invention may include according to the first aspect of the invention
Data compression device includes any or all of functional character of embodiments thereof.
The third aspect of the invention is data decompression device, for being through decompressing by compressed data block decompression
The data block of contracting, the decompressed data block include the n data value at corresponding data value positions, data decompression
Equipment includes：
Decompressor is configured to for the variable length codeword decompression of compressed data block being condensed to corresponding decompressed
Data value；And
Decompressed data block generator, is configured to：
The data value mask comprising n mask position is read from compressed data block, wherein each mask position instruction
Whether corresponding data value in unpressed data block is before the data compression for generating compressed data block at least one
Any one particular data value in a particular data value is equal；And
Based on data value mask, the decompressed data value by self solving compressor in the future and the phase by data value mask
At least one the described particular data value for the mask position instruction answered combines, to generate decompressed data block,
Wherein, the order of the data value of decompressed data block generated and the data value are before data compression
The order occurred in unpressed data block is identical.
In some embodiments, each mask position in n mask position of data value mask include instruction or
The single position an of particular data value is not indicated.In other implementations, every in n mask position of data value mask
A mask position all includes the bit combination that can decode the fixed size of any one particular data value in multiple particular data values.
Advantageously, such particular data value is 0 (zero).
With reference to Figure 17 and Figure 19 to the preferred embodiment of data compression device according to the third aspect of the present invention
In addition feature is described, and in addition, is limited in the appended dependent claims 17 submitted together with this.
The fourth aspect of the invention is a kind of corresponding uncompressing data, for decompressing compressed data block
It is condensed to decompressed data block, the decompressed data block includes the n data value at corresponding data value positions,
Uncompressing data includes：
The variable length codeword decompression of compressed data block is condensed to corresponding decompressed data value；
The data value mask comprising n mask position is read from compressed data block, wherein each mask position instruction
Whether corresponding data value in unpressed data block is before the data compression for generating compressed data block at least one
Any one particular data value in a particular data value is equal；And
Based on data value mask, by the way that decompressed data value is referred to by the corresponding mask position of data value mask
At least one the described particular data value shown is combined, to generate decompressed data block,
Wherein, the order of the data value of decompressed data block generated and the data value are before data compression
The order occurred in unpressed data block is identical.
Uncompressing data according to the fourth aspect of the present invention may include according to the third aspect of the present invention
Data decompression device include embodiments thereof any or all of functional character.
The fifth aspect of the invention is a kind of data compression device, for that will include the unpressed number of n data value
According to the compressed data block of block boil down to, which includes：
Compressor is configured to the corresponding variable length codeword of data value boil down to of unpressed data block；
Detector is configured to detect presence of at least one particular data value in unpressed data block；And
Compressed data block generator, couples with compressor and detector, and is configured to generate comprising n masked bits
The data value mask set, wherein corresponding data value in each unpressed data block of mask position instruction whether with by institute
Any one particular data value stated at least one described particular data value that detector detects is equal,
Wherein, compressed data block generator includes mask code generator, which is configured to：
Data value mask generated is analyzed, including determining and if any one mask mode in a variety of mask modes
Matching；And
Mask coding is generated to represent the result of analysis；
Wherein, compressed data block generator be further configured to by will at least it is following be combined to generate it is compressed
Data block：
Mask coding generated；And
For special with any of at least one particular data value in unpressed data block
Determine all unequal data value of data value, is carried out compressing resulting corresponding variable length by compressor
Code word is spent,
Wherein, compressed data block includes mask coding generated and m variable length codeword, wherein m≤n, and
And wherein, do not include in compressed data block in unpressed data block with described at least one particular data value
In the equal data value of any one particular data value variable length codeword, and
Wherein, compressed data block further includes data value mask, unless as mask code generator carry out described in point
Analysis the result is that data value mask generated indicates the predetermined repeat pattern of the particular data value in unpressed data block.
With reference to Figure 18 to the other spy of the preferred embodiment of data compression device according to the fifth aspect of the present invention
Sign is described, and in addition, is limited in the appended dependent claims 21-24 submitted together with this.
The sixth aspect of the invention is a kind of data compression method, for that will include not pressing for scheduled n data value
The compressed data block of data block boil down to of contracting, data compression method include：
By the corresponding variable length codeword of data value boil down to of unpressed data block；
Detect presence of at least one particular data value in unpressed data block；
Generate the data value mask comprising n mask position, wherein in each unpressed data block of mask position instruction
Corresponding data value it is whether equal with any one particular data value at least one described particular data value；
Data value mask generated is analyzed, including determining and if any mask mode in a variety of mask modes
Matching；
Mask coding is generated to represent the result of analysis；And
By that at least following will be combined to generate compressed data block：
Mask coding generated；And
For in unpressed data block with any one particular data value at least one described particular data value
All unequal data value is carried out compressing resulting corresponding variable length codeword by compressor,
Wherein, compressed data block includes mask coding generated and m variable length codeword, wherein and 0≤m≤
N, and wherein, in compressed data block do not include in unpressed data block at least one described certain number
According to the variable length codeword of the equal data value of any one particular data value in value, and
Wherein, compressed data block further includes data value mask, unless analytical procedure the result is that data generated
Value mask indicates the predetermined repeat pattern of the particular data value in unpressed data block.
Data compression method according to the sixth aspect of the invention may include according to the fifth aspect of the present invention
Data compression device includes any or all of functional character of embodiments thereof.
The seventh aspect of the invention is a kind of data decompression device, for being warp by compressed data block decompression
The data block of decompression, the decompressed data block include the n data value at corresponding data value positions, data solution
Compression device includes：
Decompressor is configured to for the variable length codeword decompression of compressed data block being condensed to corresponding decompressed
Data value；And
Decompressed data block generator, is configured to：
Mask coding is read from compressed data block, mask coding represents any one mask in a variety of mask modes
Mode；
When the mask mode represented by read mask coding does not indicate in the data pressure for generating compressed data block
When the predetermined repeat pattern of any particular data value before contracting in unpressed data block at least one particular data value,
The data value mask comprising n mask position is read from compressed data block, wherein each mask position instruction is unpressed
Whether the corresponding data value in data block is special with any of at least one particular data value before data compression
It is equal to determine data value；And
Based on mask coding and the data value mask under usable condition, by being combined to both following described in generation
Decompressed data block, one of both described is the decompressed data value from the decompressor, described two
Person the other of be by by mask coding represent predetermined repeat pattern instruction or by under usable condition
At least one described particular data value of the corresponding mask position instruction of data value mask,
Wherein, the order of the data value of decompressed data block generated and the data value are before data compression
The order occurred in unpressed data block is identical.
With reference to Figure 19 to the other spy of the preferred embodiment of data compression device according to the seventh aspect of the present invention
Sign is described, and in addition, is limited in the appended dependent claims 27-30 submitted together with this.
The eighth aspect of the invention is a kind of corresponding uncompressing data, for decompressing compressed data block
It is condensed to decompressed data block, the decompressed data block includes the n data value at corresponding data value positions,
Uncompressing data includes：
The variable length codeword decompression of compressed data block is condensed to corresponding decompressed data value；
Mask coding is read from compressed data block, mask coding represents any one mask in a variety of mask modes
Mode；
When the mask mode represented by read mask coding does not indicate in the data pressure for generating compressed data block
When the predetermined repeat pattern of any particular data value before contracting in unpressed data block at least one particular data value,
The data value mask comprising n mask position is read from compressed data block, wherein each mask position instruction is unpressed
Whether the corresponding data value in data block is special with any of at least one particular data value before data compression
It is equal to determine data value；And
Based on mask coding and the data value mask under usable condition, by being combined to generate through solving by both following
The data block of compression, one of both described is decompressed data value, and the other of both described is by by covering
The predetermined repeat pattern instruction that code coding represents or by the data value mask under usable condition corresponding masked bits
At least one described particular data value of instruction is set,
Wherein, the order of the data value of decompressed data block generated and the data value are before data compression
The order occurred in unpressed data block is identical.
Uncompressing data according to the eighth aspect of the present invention may include according to the seventh aspect of the present invention
Data compression device include embodiments thereof any or all of functional character.
The ninth aspect of the invention is a kind of data compression device, for that will include the unpressed number of n data value
According to the compressed data block of block boil down to, data compression device includes：
Compressor is configured to the corresponding variable length codeword of data value boil down to of unpressed data block, and
Export the variable length codeword and its corresponding code length；
Compressed data block generator is coupled with compressor and is posted including the length mask with n storage location
Storage, each storage location is for a data value in n data value of unpressed data block, length mask register quilt
It is disposed for storing the length mask of n position,
Wherein, compressed data block generator is configured to store in the corresponding position of length mask and be mentioned by compressor
The corresponding code length of the variable length codeword of confession, and
Wherein, compressed data block generator is configured to by being combined to generate compressed data by following
Block：
The length mask being stored in length mask register；And
By the compressed data value for the variable length codeword form that compressor provides.
In an advantageous embodiment, data compression device further includes detector, the detector coupled with compressor and
Be configured to detect in unpressed data block cannot be by the data value of the compressor compresses, wherein compressed data
Module generator is configured to：There to be spy when the data value that detector has been detected by unpressed data block cannot be compressed
The code length being very worth is stored in the corresponding position in length mask, and by the unpressed data value storage in compressed number
According in block.Advantageously, the particular value of code length is 0.
With reference to Figure 23 to the other spy of the preferred embodiment of data compression device according to the ninth aspect of the present invention
Sign is described, and in addition, is limited in the appended dependent claims 33-39 submitted together with this.
The tengh aspect of the invention is a kind of corresponding data compression method, for that will include not pressing for n data value
The compressed data block of data block boil down to of contracting, the data compression method include：
By the corresponding variable length codeword of data value boil down to of unpressed data block, and export the variable-length
Code word and its corresponding code length；
The length mask of n position is stored in the length mask register with n storage location, each storage position
A data value in the n data value for unpressed data block is set,
The corresponding code length of variable length codeword is stored in the corresponding position of length mask, and
By being combined to generate compressed data block by following：
The length mask being stored in length mask register；And
The compressed data value of variable length codeword form.
Data compression method according to the tenth aspect of the present invention may include according to the ninth aspect of the present invention
Data compression device includes any or all of functional character of embodiments thereof.
Of the invention the tenth is a kind of data decompression device on one side, for being by compressed data block decompression
Decompressed data block, the decompressed data block include the n data value at corresponding data value positions, data
Decompression apparatus includes：
Decompressor is configured to for the variable length codeword decompression of compressed data block being condensed to corresponding decompressed
Data value；
Extractor mechanism, the extractor mechanism are used for：The length mask of n position, root are read from compressed data block
The corresponding code length that the variable length codeword in compressed data block is determined according to length mask, based on identified corresponding
Code length extracts corresponding variable length codeword from compressed data block, and by extracted corresponding variable length codeword
It is supplied to decompressor；And
Decompressed data block generator is configured to be generated according to the decompressed data value from decompressor
Decompressed data block,
Wherein, the order of the data value of decompressed data block generated and the data value are before data compression
The order occurred in unpressed data block is identical.
In an advantageous embodiment, decompressed data block generator is configured to：
For one or more positions in length mask, the one or more corresponding data values of detection instruction are with uncompressed
Form include one or more of compressed data block have particular value code length；And
Based on detected one or more have particular value code length, by self solve in the future compressor through decompressing
The data value of contracting data value corresponding with the one or more of the uncompressed form from compressed data block is combined next life
At decompressed data block.Advantageously, the particular value of code length is 0.
12nd aspect of the invention is a kind of uncompressing data, for being by compressed data block decompression
Decompressed data block, the decompressed data block include the n data value at corresponding data value positions, the number
Include according to decompression method：
The length mask of n position is read from compressed data block；
The corresponding code length of the variable length codeword in compressed data block is determined according to length mask；
Corresponding variable length codeword is extracted from compressed data block based on identified corresponding code length；
Extracted variable length codeword decompression is condensed to corresponding decompressed data value；And
Decompressed data block is generated according to decompressed data value,
Wherein, the order of the data value of decompressed data block generated and the data value are before data compression
The order occurred in unpressed data block is identical.
Uncompressing data according to the twelfth aspect of the present invention may include 11st according to the present invention
The data decompression device of aspect includes any or all of functional character of embodiments thereof.
Another aspect of the present invention is a kind of system, the system comprises one or more memories, according to above-mentioned
On one side, the data compression device of the 5th aspect or the 9th aspect and according to above-mentioned third aspect, the 7th side
The data decompression device of face or the tenth one aspect.
An additional aspect of the present invention is a kind of computer program product, and the computer program product includes that code refers to
It enables, the code command causes when load by processing equipment and being executed according to above-mentioned the second aspect, in terms of the 6th or the
The execution of the method for ten aspects.
An additional aspect of the present invention is a kind of computer program product, and the computer program product includes that code refers to
It enables, the code command causes when load by processing equipment and being executed according to above-mentioned 4th aspect, in terms of the 8th or the
The execution of the method for 12 aspects.
According to disclosure, accompanying independent claim and attached drawing in detailed below, disclosed embodiment its
His aspect, target, feature and advantage will become apparent from.Generally, unless separately there is specific definition herein, otherwise institute in the claims
All terms used should be explained according to their ordinary meanings in technical field.
Unless otherwise specific statement, otherwise to " one (a)/mono- (an)/be somebody's turn to do (the) [element, equipment, component, device, step
It is rapid etc.] " with reference to should all be read as with being opened to element, equipment, component, device, step etc. at least one
The reference of example.Unless explicitly stated otherwise, otherwise any method disclosed herein the step of need not be with disclosed exact time
Sequence executes.
Detailed description of the invention
The embodiment of example and present invention aspect in background technique is described with reference to the following drawings：
Fig. 1 instantiates the block diagram that the computer system of core is handled including n, and there are three ranks with tool for each processing core
Cache hierarchy is connected with main memory.
Fig. 2 instantiates the block diagram of Fig. 1, wherein main memory saves the data of compressed form.
Fig. 3 instantiates the block diagram of Fig. 1, wherein L3 caching saves the data of compressed form.Others caching rank
It can store the data of compressed form.
Fig. 4 instantiates the block diagram of Fig. 1, and wherein data are compressed in communication dress, such as when in memory and caching level
When being transmitted between structure.
Fig. 5 instantiates the block diagram of Fig. 1, wherein compression can be applied to main memory and memory is connected to caching level
The link of structure.In general, compression can be applied to similar cache hierarchy, transmitting device (for example, memory is connected to
The link of cache subsystem) and main memory part any combination.
Fig. 6 instantiates the block diagram of the data transfer links of two points in connection communication network.These points can be network
In two intermediate nodes or source node in communication link and destination node either these situations combination.
Fig. 7 instantiates the block diagram of the data transfer links of Fig. 6, wherein and the data transmitted are compressed forms, so
They may need to be compressed and be decompressed in the receiver in the transmitter.
Fig. 8 instantiates unpressed data value block on the left side, and instantiates to use on the right and utilized huffman coding
The same block of the compressed form of the variable length code of generation.Unpressed piece of all data values are by corresponding Huffman
Code word replaces.
Fig. 9 instantiates the compressor for being used for that (or coding) block as illustrated in Figure 8 is compressed using huffman coding.
Figure 10 instantiates the decompressor that be used to decode the block of (or decompression) operating specification huffman coding compression.
Figure 11 instantiates unpressed data value block (i.e. unpressed data block) on the left side, and instantiates benefit on the right
With the same block (i.e. compressed data block) for the compressed form for using huffman coding variable length code generated.
All data values of unpressed data block are replaced by the corresponding Huffman code word in compressed data block.
Figure 12 instantiates unpressed data block on the left side, and is instantiated in a manner of alternative cover including position on the right
The same block of the compressed form of code and variable length code (i.e. by the encoded bit sequence of variable length code), which covers
Code indicates which data value is zero and nonzero value, which includes the mixing of compressed non-zero data value.
Figure 13 instantiates unpressed data value block on the left side, and instantiates to use on the right and utilized huffman coding
The same block of the compressed form of the variable length code of generation.All data values of unpressed data block are compressed
Corresponding Huffman code word in data block replaces.
Figure 14 instantiates unpressed data block on the left side, and is instantiated in a manner of alternative including mask on the right
The same block of the compressed form of coding and variable length code (i.e. by the encoded bit sequence of variable length code), this is covered
Whether code coding instruction bitmask is included in described compressed piece or indicates whether are data values of zero and non-zero data value
Occur in a particular order or whether in accordance with specific mode, which includes compressed non-zero data value
Mixing.
Figure 15 instantiates unpressed data block on the left side, and is instantiated in a manner of alternative including mask on the right
Coding, bitmask and variable length code (i.e. by the encoded bit sequence of variable length code) compressed form it is same
Block, whether mask coding instruction bitmask followed by, which indicates which value is zero and nonzero value, this can be changed
Length coding includes the mixing of compressed non-zero data value.
Figure 16 instantiates the compressor based on Fig. 9 but is modified and be extended to the unpressed data block that can compress Figure 12
Data compression device.
Figure 17, which instantiates the decompressor based on Figure 10 but modified and be extended to, can decompress the compressed of Figure 12
The data decompression device of data block.
Figure 18, which instantiates the compression device based on Figure 16 but modified and be extended to, can compress not pressing for Figure 14 and Figure 15
The data compression device of the data block of contracting.
Figure 19, which instantiates the decompression apparatus based on Figure 17 but modified and be extended to, can decompress Figure 14's and Figure 15
The data decompression device of compressed data block.
Figure 20 instantiates unpressed data value block (i.e. unpressed data block) on the left side, and instantiates benefit on the right
With the same block (i.e. compressed data block) of the compressed form for the variable length code for using huffman coding to generate.
Figure 21 instantiates unpressed data block on the left side, and is instantiated in a manner of alternative cover including position on the right
The same block of the compressed form of code and variable length code (i.e. by the encoded bit sequence of variable length code), which covers
Code keeps the length of the variable length code of compressed data value, which includes compressed data value and not
The mixing of the data value of compression.
Figure 22 instantiates unpressed data block on the left side, and is instantiated in a manner of alternative cover including position on the right
The same block of the compressed form of code and variable length code (i.e. by the encoded bit sequence of variable length code), which covers
Code keeps the length of the variable length code of compressed value, which includes compressed data value and uncompressed
Data value mixing, but wherein, unpressed data value with the order that occurs in original unpressed data block
Opposite order is stored in the end of compressed data block.
Figure 23 instantiates the compressor based on Fig. 9 but is modified and be extended to the unpressed data block that can compress Figure 21
Data compression device.
Figure 24, which instantiates the decompressor based on Figure 10 but modified and be extended to, can decompress the compressed of Figure 21
The data decompression device of data block.
Figure 25, which instantiates the decompressor based on Figure 10 but modified and extended to, can decompress the compressed of Figure 22
The data decompression device of data block.
Figure 26, which instantiates the decompression apparatus based on Figure 24 but modified and be extended to, can concurrently decompress 2 through pressing
The decompression apparatus of the data of contracting.
Figure 27 instantiates the compression side for compressing unpressed data block using variable length code (for example, Huffman)
The example flow diagram of method.
Figure 28, which is instantiated, is used the compressed of variable length code (for example, canonical Huffman) compression for decompressing
The example flow diagram of the decompression method of data block.
Figure 29 instantiates foundation on the compression method of Figure 27 and in accordance with the step similar to the compression device of Figure 18
Make it possible to compress the example flow diagram of the new method of the unpressed data block of Figure 14 and Figure 15.
Figure 30 instantiates foundation to be made on the method for Figure 28 and in accordance with the step similar to the decompression apparatus of Figure 19
Obtain the example flow diagram that can decompress the new method of compressed data block of Figure 14 and Figure 15.
Figure 31 instantiates foundation on the compression method of Figure 27 and in accordance with the step similar to the compression device of Figure 23
(skipping step required for determining unpressed value and mixing compressed value and unpressed value) makes it possible to compress
The example flow diagram of the new method of the unpressed data block of Figure 21.
Figure 32 instantiates foundation on the decompression method of Figure 28 and in accordance with similar with the decompression apparatus of Figure 24
Step (skipping step required for determining unpressed value and mixing compressed value and unpressed value) makes it possible to
Decompress the example flow diagram of the new method of the compressed data block of Figure 21.
Specific embodiment
Present disclosure is disclosed for working as the caching subsystem that will be compressed applied in communication network and/or computer system
When system and/or memory sub-system and/or data transmission sub-system, one or more data value blocks and decompression one are compressed
Or the method, apparatus and system of multiple compressed data value blocks.Disclosed method, apparatus and system extend and optimize baseline
Compression method, equipment and system and decompression method, equipment and system, so as to can be with better compressibility and higher pressure
Contracting/decompression speed is applied to data compression situation common in applied system above-mentioned.
Data block includes one or more data values and can be arbitrary size.In the department of computer science made as depicted in FIG. 1
In the embodiment of system, data value block can alternatively be referred to as 1) cache lines, caching group or caching sector, when data block quilt
When being stored in the cache hierarchy in such computer system；2) cache lines, storage page or memory sectors, work as number
It is saved in the memory in such computer system or in the communication device in such computer system according to block
When transmission.On the other hand, in the embodiment of the transmitting link road in the communication network that such as Fig. 6 is drawn, data block can also be with
Refer to packet (packet, data packet, packet), microplate (flit), payload, data head (header, stem, header) etc..
Variable-length compression based on entropy, such as huffman compression can be shown what such as Fig. 2, Fig. 3, Fig. 4, Fig. 5 were drawn
It is answered in cache/memories/data transmission sub-system of example computer system or the situation for the example communication link made as depicted in fig. 7
For data value block shown in the left side such as Fig. 8.Described piece include 8 data values, however as previously mentioned, its can be it is arbitrarily large
It is small.It is right using the example embodiment of huffman compression device such as Fig. 9 of one group of example specification Huffman code word and the prior art
All data values in described piece are compressed (or coding) and form compressed piece, as the right of Fig. 8 is drawn.In addition,
The compressed data value block of example variable-length for being plotted in the right of Fig. 8 can be decompressed by the canonical Huffman of the prior art
The example embodiment of contracting device such as Figure 10 decompresses.
When data compression applications are in cache/memories subsystem or transfer network sub system or point-to-point communication network
When, common scene is that particular data value 0 fairly frequently occurs in data block, but there is no by the certain number for data block
It is fully filled with according to value 0.Assuming that data value 0 encodes (best circumstance) with 1 bit word, such unpressed data block and use can
Becoming the conventional of the compressed respective data blocks of length coding (for example, huffman coding) progress indicates to be plotted in Figure 11.According to
The alternative expression of embodiments of the present invention, the unpressed data block of Figure 11 is presented in Figure 12, wherein compressed number
It include the mask with X bit width according to block, wherein quantity (this of X and the data value for including in block before variable length code
In to be 8) equally big.Referred to as the mask of Z value mask (Z-Value Mask) frequently goes out to described present in compressed piece
Existing particular data value such as data value 0 is encoded, thus when such data values of zero is present in unpressed data block
Omit the example Huffman code word in variable length code.In this way, the embodiment (in total 12 of compressed data block ratio Figure 21
Position) 2 big (in total 14), however, compressed piece of decompression can become faster using such coding.
The block diagram for being capable of forming the sample data compression device 1600 of the compressed data block of Figure 12 is plotted in figure
In 16.The sample data compression device includes the detection of the compressor of 1620 form of variable length coding unit, comparator form
Device 1630 and compressed data block generator 1640-1670, these compressed data block generators include for storing
The Z value mask register 1640 of Z value mask is used to store from the received variable length of variable length coding unit (compressor) 1620
Spend the storage unit 1650 and connector 1670 of code word 1625.As in the compressor embodiment of Fig. 9, data pressure
For contracting equipment 1600 by unpressed data block 1610 as inputting, which is data value stream and including one
Or multiple data value v1, v2 ..., vn, and the unpressed data block can obtain or from having from storage unit 1605
The extractor for coming from the data value of unpressed data block obtains.However, the data value of unpressed data block 1610 not only by
Be supplied to variable length coding unit 1620, be also supplied to compare the value whether be zero (i.e. particular data value) comparator
(detector) 1630.If the value non-zero, coding is carried out to it using unit 1620 and the encoded value will be placed
In the variable length code 1635 of accumulation, and the result (" 0 " indicates to mismatch) of comparator 1630 will be stored in Z value mask
In corresponding position in 1640 (first value in first position corresponding blocks in Z value mask, etc.).If the value is
Zero, then the result (" 1 " indicates matching) of comparator 1630 will disable storage unit 1650, so that from variable length code 1635
It is middle to omit the encoded value.In addition, " 1 " is written in the corresponding position in Z value mask 1640 to indicate zero.When entire block
When being compressed (this can by those skilled in the art using counter and with the maximum number that includes value in unpressed piece
Amount is made comparisons and is realized), Z value mask is read from Z value mask register 1640 and is connected Z value mask using connector 1670
Before variable length code 1635, compressed piece 1690 is formed.Storage unit 1650 can by those skilled in the art with
Different modes are realized, for example, using one group of three state buffer.
Therefore, in the data compression device 1600 in Figure 16, aforesaid detector includes comparator 1630, has and is matched
It is set to the first input for receiving the data value v1-vn at the corresponding data value positions in unpressed data block 1610
1631a, the second input for being configured to receive particular data value 1632 and are configured to export particular data value 1631b
Comparison result between 1632 and the data value v1-vn at the corresponding data value positions in unpressed data block 1610
Output 1633.
In addition, in data compression device 1600 in Figure 16, aforementioned compressed data block generator 1640-1670 packet
The mask register 1640 with a n storage locations is included, each storage location is used for n mask of data value mask
A mask position in position.The output 1633 of comparator 1630 is coupled to mask register 1640, so that using specific
Data value 1632 is compared between the data value v1-vn at the corresponding data value positions in unpressed data block 1610
Result be updated mask register 1640 at the corresponding storage location in its n storage location.
In addition, in data compression device 1600 in Figure 16, aforementioned compressed data block generator 1640-1670 packet
Storage unit 1650 is included, which has the first input 1651a, and the first input is configured to from the reception pair of compressor 1620
The variable length codeword 1625 of data value v1-vn of the Ying Yu at the corresponding data value positions in unpressed data block 1610
And it stores it in storage unit 1650.Storage unit 1650 also has the variable length codeword for being configured to be stored
1625 are output to the output 1653 in the variable length code 1655 of accumulation, and are configured to receive dependent on comparator 1630
Output 1633 control signal second input 1631b.Storage unit 1650 is configured to：When the comparison knot of comparator 1630
Fruit indicates particular data value 1632 and the data value v1-vn at the corresponding data value positions in unpressed data block 1610
Between matching when, forbid stored variable length codeword 1625 to be output in variable length code 1655.
In addition, in data compression device 1600 in Figure 16, aforementioned compressed data block generator 1640-1670 packet
Connector 1670 is included, which is configured to：When unpressed data block 1610 all n data value v1-vn all
When processed, by will be from the data value mask Z value mask of mask register 1640 and the variable length code 1655 of accumulation
Connection is to generate compressed data block 1690.
In the disclosed embodiment according to the data compression device 1600 of Figure 16, in compressed data block 1690
In, data value mask Z value mask is placed in front of the variable length code 1655 of accumulation.In other embodiments, through compressing
Data block 1690 in, data value mask Z value mask can alternatively be attached at the end of the variable length code 1655 of accumulation.
The above disclosure of Figure 16 can alternatively be considered as including the unpressed of one or more data values
The equipment (that is, data compression device) that compressed piece of data block boil down to；Wherein, the compressed data block is covered including position
Code and variable-length bit sequence, the variable-length bit sequence further include carry out encoding using variable length code resulting one or
Multiple compressed data values, wherein the quantity of compressed data value is less than or equal to the quantity of unpressed data value；Its
In, the equipment includes：Compressor, for compressing the data value using the variable-length character code for corresponding to data value；First
Mechanism, detection will not be used for specific using the one or more of the compressor compresses of variable-length character code compressed data value
Data value；Second mechanism carrys out the bitmask of particular value described in update instruction using the detection information of the first mechanism.
The block diagram that described compressed piece of the sample data decompression apparatus 1700 of Figure 12 can be decompressed is plotted in figure
In 17.Data decompression device 1700 is constructed based on the decompressor 1000 of Figure 10 and including saving compressed data block
(size of storage unit 1710 is at least unpressed value length and maximum code word to the storage unit 1705 of 1710 a part
The maximum in length), codeword detection unit 1720 (similar to the codeword detection unit 1020 of decompressor 1000 of Figure 10),
It is worth retrieval unit 1730 (similar to the value retrieval unit 1030 of decompressor 1000 of Figure 10) and forms compressed data
Added logic (extra logic extends logic) 1740-1780 of module generator.Codeword detection unit 1720 and value retrieval are single
Therefore member 1730 forms decompressor.
Decompressed data block generator includes obtaining for storing from the attachment part of compressed data block 1710
Z value mask register 1750, variable-length (VL) value position generator 1740, variable-length (VL) value position assigner
1760 and selector 1780.Z value mask is used in two ways：1) selector 1780 is generated using each Z value masked bits
Control signal so that alternatively selecting to write on zero if data value has been encoded into zero (i.e. particular data value)
In decompressed block 1790；2) all Z value masked bits are used by VL value position generator 1740.VL value position generator is raw
At the mask index (being indicated by the zero-bit in Z value mask) for all nonzero values.For example, in the embodiment of Figure 12, it is non-
Zero is marked in Z value mask index 5 and 6.VL value position assigner 1760 is determined using this information will be by decompressing
Decoded each (non-zero) value (v5 and v6 of the embodiment of Figure 12) of device is placed on where.
Therefore, a part of the compressed data value included by the compressed data block be data value 0 (or it is another most
Frequent data value) when, the data decompression device 1700 of Figure 17 accelerates the decompression to compressed data block, because should
Data decompression device is only needed to the non-zero data value decompression that variable length code encodes it is utilized.
If basis is above to understand, in the data decompression device 1700 of Figure 17, aforementioned decompressed data
Module generator 1740-1780 includes value position generator 1740, is worth position assigner 1760 and multiple selectors 1780, each
Selector is for a data value positions in n data value positions of decompressed data block 1790.It is worth position generator
1740 are configured to controlling value position assigner 1760 and multiple selectors 1780, so that working as the phase of data value mask Z value mask
It is from corresponding selector reception particular data value 1782 and this is specific when the mask position instruction particular data value 1782 answered
Data value includes being located at corresponding data value positions in decompressed data block 1790, and make when data value mask
When the corresponding mask position of Z value mask does not indicate particular data value 1782, corresponding warp is received from decompressor 1720-1730
The data value of decompression and by the decompressed data value include be located in decompressed data block 1790 it is corresponding
At data value positions.
The disclosure of figure 17 above can alternatively be considered as compressed data block decompression being one or more
The equipment (that is, data decompression device) of a data value；Wherein, the compressed data block includes bitmask and variable-length
Bit sequence, further comprise carry out encoding using variable length code the compressed data value of resulting one or more and with
One or more particular values of bitmask coding；Wherein, the equipment includes：Decompressor, for decompressing variable length word
Code corresponds to the data value of the variable-length character code to rebuild；First mechanism, read bitmask with determine during compression
Whether occur particular value in unpressed piece and generates the value position in unpressed piece；And second mechanism, using coming from
The instruction of first mechanism creates the particular data value again, so that the order of the value in decompressed data block and compression
The order of value in preceding original data block is identical.
In alternative embodiment, technical staff can be by another very frequent particular data value as data value 0
It encodes like that.In yet an alternative embodiment, it can use the mask encoded using fixed size to more frequent data value
It is encoded.For example, 3 most frequent data values can be encoded into 00,01,10, leaves 11 and utilize variable-length to represent
Encode frequent (or less frequently) data value of encoded to it non-.Multiple particular data values can be real by substitution
The mode of applying detects, wherein the comparator 1630 or 1830 of data compression device 1600 and 1800 is contained multiple spies respectively
The small-sized dictionary of definite value is replaced.Alternate embodiments can be realized by those skilled in the art.
Figure 13 shows unpressed data block (on the left side Figure 13) and the corresponding warp using variable length huffman code
The expression of the block (on the right of Figure 13) of compression.Unpressed piece of Figure 13 is common situation, and wherein particular data value 0 appears in
In the even number index position of block (assuming that the index of first value is 0, the index of second value is 1, etc.).Such case is in block
Data value be that may occur when being declared as the lowerinteger value of big integer.Similarly, particular data value 0 can consistently occur
In the odd number index position of block.Embodiment according to the present invention, what Figure 14 showed compression unpressed piece of Figure 13 can
Alternative, wherein there is using 2 (10) to every two data value scene (wherein, first data value of block of one 0 values
It is 0) to be encoded, and compress remaining non-zero data value as previously described.In this way, with the warp of Figure 13
When the expression (in total 18) of the block of compression is made comparisons, compression is modified 2 (in total 16).In order to such difference
Compression scene and unpressed piece of embodiment of Figure 12 encoded, it is desirable that set before mask (if any)
Set mask coding.For example, being encoded using 2 bitmasks, we can be encoded following mode scenarios：00 → without mask with
With (there is no zero in data block)；There is a value 0 in 01 → every two data value, and with the beginning of value 0, (zero is not in data block
In odd positions)；There is a value 0 in 10 → every two data value, and with 0 beginning of value, (zero is in even number position to data block
In)；11 → value 0 occurs one or many and is unable to use pattern and is similarly described.Therefore, this 2 codings can will more
More positions is added to compressed data block or can cause preferably to compress (01 and 10 mode), but in short, it can be with
Accelerate to decompress by adding a small amount of source.
The block diagram for being capable of forming described compressed piece of the sample data compression device 1800 of Figure 14 and Figure 15 is plotted in
In Figure 18.Just as the compression device of Figure 16, it includes the compressor of 1820 form of variable length coding unit, for storing Z value
Z value mask register 1840, other logics 1830 and 1850, compressed data block generator 1870 and the mask of mask are compiled
Code generator 1860.It is executed in a manner of identical with the data compression device 1600 of Figure 16 to data values of zero (even if they are presented
Out in accordance with the mode in such as Figure 14) and non-zero data value compression, until block compress complete.So far, Z value mask register
Z value mask is supplied to mask code generator 1860 by 1840.In this example embodiment, the generator 1860 includes
Boolean logic, Boolean logic attempt identify whether the AD HOC (Z- even number and Z- odd number) about zero occurs, or any
Whether zero (any-Z) has already appeared.Mask encoder 1867 generates corresponding mask coding 1868 using these signals.
Note that then this data block is compressed to if all data values (e.g., 8 values, i.e. n=8) in data block are all zeros
" 1111111111 ", wherein first 2 are that mask encodes and remaining 8 are Z value masks.If it is this situation, then logic
Z- odd number and Z- even number are switched to " 0 " by 1864-1866, and otherwise their logic-baseds 1861 and 1862 keep set/reset.If
There is no zero to be included in data block, then Z- even number, Z- odd number and any-Z will be " 0 ", generate " 00 " in this way and cover
Code coding 1868.In addition, connector 1870 checks mask coding 1868：If it is " 00 ", " 01 " or " 10 ", in variable length
Attachment mask coding 1868 before degree coding 1835, before mask 1868 is otherwise placed in Z value mask, Z value mask is placed in again can
Become before length coding 1835.In addition to mask code generator 1860 and its sub-component, and to the additional defeated of connector 1870
Enter and its as described above except additional function, the component 18nn of the data compression device 1800 in Figure 18 can be with Figure 16
In data compression device 1600 corresponding component 16nn it is identical, shared in their appended drawing reference it is same most latter two
Digital nn.
As according to it is above it will be appreciated that, in the data compression device 1800 in Figure 18, aforementioned mask code generator
1860 may be configured to：When data value mask Z value mask generated instruction certain number in unpressed data block 1810
When being located at the predetermined repeat pattern at a data value positions according to value (such as data values of zero), generating has the first mask coding
The mask coding 1868 of value, wherein only including mask coding 1868 without wrapping in compressed data block 1890 generated
Include data value mask Z value mask.
Mask code generator 1860 also may be configured to：When data value mask Z value mask generated is indicated not
Particular data value (such as data values of zero) is located at the predetermined repetition mould at a data value positions in the data block 1810 of compression
When formula (however deviating a position relative to the predetermined repeat pattern of the first mask encoded radio), generating has the second mask coding
The mask coding 1868 of value, wherein only including mask coding 1868 in compressed data block 1890 generated without including
Data value mask Z value mask.
Mask code generator 1860 can be configured to：When data value mask generated is indicated in unpressed number
According at least one data value positions in block, there are when particular data value, generate that there is the mask of third mask encoded radio to encode
1868, wherein mask coding 1868 and data value mask Z value mask are included in compressed data block 1890 generated
In.Alternatively, mask code generator 1860 may be configured to：When data value mask Z value mask generated instruction exists
Particular data value (such as data values of zero) is located at the predetermined repeat pattern at each data value positions in unpressed data block 1810
When, the mask coding 1868 with third mask encoded radio is generated, wherein in compressed data block 1890 generated only
Including mask coding 1868 without including data value mask Z value mask.
Mask code generator 1860 can be configured to：When data value mask Z value mask generated is indicated not
When particular data value being all not present in all data value positions in the data block 1810 of compression, generating has the 4th mask coding
The mask coding 1868 of value, wherein only including mask coding 1868 in compressed data block 1890 generated without including
Data value mask Z value mask, alternatively, mask code generator 1860 may be configured to：When data value generated is covered
When code Z value mask does not indicate any one of the predetermined repeat pattern of the first, second or third mask encoded radio, generation has
The mask coding 1868 of 4th mask encoded radio, wherein mask coding 1868 and data value mask Z value mask are included in institute
In the compressed data block 1890 generated.
Advantageously, in compressed data block 1890, mask coding 1868 can be placed in m variable length codeword it
Before, wherein in compressed data block 1890, it can be after mask encodes 1868 and before m variable length codeword
It provides data value mask Z value mask (if present).However, in compressed data block 1890, mask coding 1868
Other opposite order between m variable length codeword and data value mask Z value mask (if present)
It is possible.
The disclosure of figure 18 above can alternatively be considered as including the unpressed of one or more data values
The equipment (that is, data compression device) that compressed piece of data block boil down to；Wherein, the compressed data block includes mask
Coding, bitmask and variable-length bit sequence, which further comprises being compiled using variable length code
The resulting compressed data value of one or more of code, wherein the quantity of compressed data value is less than or equal to unpressed
The quantity of data value；Wherein, the equipment includes：Compressor, for being compressed using the variable-length character code for corresponding to data value
The data value；First mechanism, detection will not be used for the compressor compresses using variable-length character code compressed data value
One or more particular data values；Second mechanism carrys out particular value described in update instruction using the detection information of the first mechanism
Bitmask；Third mechanism searches the AD HOC about the particular data value and generates the mask coding；And the 4th
Mechanism uses mask coding, bitmask and variable length code using the information from the second mechanism and third mechanism to generate
Compressed piece.
The frame of the sample data decompression apparatus 1900 of the compressed data block of Figure 14 and Figure 15 can be decompressed
Figure is plotted in Figure 19.Data decompression device 1900 is constructed based on the decompressor 1000 of Figure 10, the data decompression with Figure 17
Contracting equipment 1700 is similar.Just as data decompression device 1700, data decompression device 1900 includes saving compressed data
(size of storage unit 1910 is at least unpressed value length and maximum code to the storage unit 1905 of a part of block 1910
The maximum in word length), codeword detection unit 1920, value retrieval unit 1930, to be included in further include mask coding and decoding
Added logic 1940-1960 and 1980 in the decompressed data block generator 1940-1980 of device 1970.Codeword detection list
Therefore member 1720 and value retrieval unit 1730 form decompressor.
Decoder 1970 includes comparator 1974 and selector 1978, and generates selector based on mask coding 1915
1980 control signal.Unlike data decompression device 1700, data decompression device 1900 starts from checking the front two of block
(i.e. mask coding 1915).If it is " 11 ", then next 8 of compressed piece are extracted from storage unit 1905 and incited somebody to action
It copies to Z value mask 1950.The content of mask be used for VL value position generator 1940 (such as in the equipment of Figure 17) and
It is used to be fed to the selector 1978 of decoding unit 1970.Distributor 1960 and selector 1980 work as follows：
If mask coding 1915 is " 00 " (Z value mask is not present), exported from the unit 1930 of decompressor
Decoded value 1935 is fed to it and controls the selector 1980 that signal ctrl0 ', ctrl1 ' etc. are configured to " 0 ".This occurs
Point be useZ-mask (using Z mask), isEven (for even number) because in this case, in decoding unit 1970 and
IsOdd (for odd number) is configured to " 0 ".As a result, selector 1978 will select the first input (isEven or isOdd), it is
“0”。
If mask coding 1915 is " 01 " (Z- odd number, Z value mask are not present), then from the unit of decompressor 1930
The decoded value 1935 of output is fed to the selector 1980 in even number position (v1, v3, v5 etc.), and the choosing in odd positions
Select device 1980 (there is control signal ctrl1 ', ctrl3 ' etc.) selective value 0 (i.e. particular data value 1982).This means that
Ctrl0 ', ctrl2 ' etc. are configured to " 0 " and ctrl1 ', ctrl3 ' etc. and are configured to " 1 ".It is because at this that this point, which occurs,
In one situation, in decoding unit 1970, useZ-mask is " 0 ", and isEven is " 0 " and isOdd is " 1 ".As a result, selection
Device 1978 will select the first input (isEven or isOdd), cause " 0 " for ctrl0 ', ctrl2 ' etc. and " 1 " is used for
Ctrl1 ', ctrl3 ' etc..
If mask coding 1915 is " 10 " (Z- even number, Z value mask are not present), then from the unit of decompressor 1930
The decoded value 1935 of output is fed to the selector 1980 in odd positions (v2, v4, v6 etc.), and the choosing in even number position
Select device 1980 (there is control signal ctrl0 ', ctrl2 ' etc.) selective value 0 (i.e. particular data value 1982).This means that
Ctrl0 ', ctrl2 ' etc. are configured to " 1 " and ctrl1 ', ctrl3 ' etc. and are configured to " 0 ".It is because at this that this point, which occurs,
In one situation, in decoding unit 1970, useZ-mask is " 0 ", and isEven is " 1 " and isOdd is " 0 ".As a result, selection
Device 1978 will select the first input (isEven or isOdd), cause " 1 " for ctrl0 ', ctrl2 ' etc. and " 0 " is used for
Ctrl1 ', ctrl3 ' etc..
If mask coding 1915 is " 11 " (presence of Z value mask), the warp exported from the unit 1930 of decompressor
Decoded value 1935 is fed to the selector 1980 in the position determined by unit 1940, such as in decompression apparatus 1700 that
Sample, wherein control signal ctrl0 ', ctrl1 ' of selector 1980 etc. are equal with control signal ctrl0, ctrl1 etc..This occurs
Any is because in this case, in decoding unit 1970, useZ-mask is " 1 ", and isEven is " 0 " and isOdd is
"0".As a result, all selectors 1978 will select the second input (ctrl0, ctrl1 etc.), it is the output of Z value mask.
As according to it is above it will be appreciated that, in the data decompression device 1900 in Figure 19, aforementioned decompressed number
It may be configured to according to module generator 1940：When the mask of reading coding 1915 has the first mask encoded radio, pass through in the future
Self solve the decompressed data value 1935 of compressor 1920-1930 in following predetermined repeat patterns it is described at least one
Particular data value 1982 (such as data values of zero) is combined to generate decompressed data block 1990, and the predetermined repeat pattern is
Particular data value in decompressed data block 1990 at a data value positions.
In addition, decompressed data block generator 1940 may be configured to：When the mask coding 1915 of reading has
When the second mask encoded radio, by self solve in the future the decompressed data value 1935 of compressor 1920-1930 in following
At least one described particular data value 1982 (such as data values of zero) of predetermined repeat pattern combines to generate decompressed data
Block 1990, the predetermined repeat pattern of the second mask encoded radio are particular data value in decompressed data block (1990)
At a data value positions, however relative to the predetermined repeat pattern of the first mask encoded radio deviate a position.
In addition, decompressed data block generator 1940-1980 may be configured to：When the mask of reading encodes 1915
When with third mask encoded radio, decompressed data block 1990 is generated, it is every in the decompressed data block 1990
It all include at least one described particular data value 1982 (such as data values of zero) at a data value positions.
In addition, decompressed data block generator 1940-1980 may be configured to：When the mask of reading encodes 1915
When with the 4th mask encoded radio, by self solve in the future the decompressed data value 1935 of compressor 1920-1930 with such as by
At least one described particular data value 1982 (such as data values of zero) indicated by the corresponding mask position of data value mask Z value mask
It is combined to generate decompressed data block 1990.
The alternative embodiment of this new decompressor embodiment can be realized by those skilled in the art.Such as
Another value that fruit ratio 0 more frequently occurs is used substitution value 0, then alternative embodiment can also be by art technology
Personnel realize.
The disclosure of figure 19 above can alternatively be considered as compressed data block decompression being one or more
The equipment (that is, data decompression device) of a data value；Wherein, the compressed data block includes mask coding, bitmask
With variable-length bit sequence, further comprise carry out encoding resulting one or more using variable length code it is compressed
Data value and the one or more particular values encoded with bitmask；Wherein, the equipment includes：Decompressor, for decompressing
Variable length code corresponds to the data value of the variable-length character code to rebuild；Decode the first mechanism of mask coding；Second
Mechanism, reads whether bitmask particular value occurs during compression with determination in unpressed piece and generate unpressed piece
In value position；Third mechanism is made using the instruction from the first mechanism and the second mechanism to create the particular data value again
The order for obtaining the value in decompressed data block is identical as the order of value in the original data block before compression.
What the aforementioned embodiments (1000,1700 and 1900) of data compression device had is common that, needs in structure
At finding the unknown code word of length in the variable-length bit sequence of compressed data block and therefrom extract it.This is by code word
What detection unit 1020,1720 and 1920 was completed.Codeword detection is inherently orderly process, because decoded bit sequence arranges (its structure
At compressed data block) in a compressed data value need to decompress it is all first in (decoding) described sequence
The compressed data value occurred.Exemplary decompression device solves the problems, such as this by following：Construct the layer of codeword detection unit
Secondary structure, the hierarchical structure of the codeword detection unit are aligned in incoming compressed bit sequence or part thereof of different position
In position so that the result of the codeword detection unit based on first rank selected in many predicted code words after code
Word.Since multiple-group analysis device and priority encoder increase area cost and power consumption, such embodiment is added
Vast resources.
On the other hand, if each variable length codeword be it is known in advance, fully codeword detection can be avoided to walk
Suddenly.It is plotted in Figure 20 using the expression that variable length huffman code compress resulting data block.It is according to the present invention
The alternative expression of embodiment is plotted in Figure 21, wherein before the sequence (variable length code) of variable length codeword
Store the mask (L- mask) of the length value of variable length codeword.Each length value has consolidating for the largest amount depending on code word
Determine size.As being previously previously mentioned in the background technology part of this document, this can be in design, compilation, configuration or operation
In define specific length.Length 0 also indicates that data value is uncompressed.In compressed piece of Figure 21 of example embodiment,
First compressed data value in variable-length bit sequence has length 1 (corresponding code word is " 0 "), variable-length position sequence
Second compressed data value in column has length 2 (corresponding code word is " 11 "), and so on.In this way, may be used
The value of multiple compressed data values is retrieved parallelization by simplifying decompressor, but will be to increase compressed data
The size of block is cost, it is thus possible to reduce compression efficiency.
The block diagram for being capable of forming the sample data compression device 2300 of the compressed data block of Figure 21 is plotted in Figure 23.
Data compression device 2300 includes the compressor of 2320 form of variable length coding unit, for storing L- mask, (" L " represents code
Length) register 2350 and form the logic 2340,2360,2370 of compressed data block generator.Different from Fig. 9
Equipment, unit 2320 not only exports encoded data value 1625 and also exports cL (code length), and cL is recorded in L- mask.
It is wrapped in (depending on embodiment) in design, compilation, configuration or operation based on the decision of the quantity of block size and its data value
Include the quantity of the entry in L- mask.For example, if the data block of uncompressed form includes 8 data values (that is, n=8),
L- mask register 2350 includes 8 entries.Entry width determines by maximum codeword length, can be such as the institute in previous paragraph
It is defined as description, therefore it is log2 (max_cw_length).For in compressed each value, (not in Figure 23
Show, but counter may be implemented to monitor which value and compressed in those skilled in the art), cL is stored in the deposit of L- mask
In the corresponding position of device 2350.When all values of data block are all compressed, using connector unit 2370 by L- mask
It is attached at before variable length code 2355, forms compressed piece 2390.Therefore, in disclosed embodiment through compressing
Data block 2390 in, length mask L- mask is placed in front of variable length codeword 2325；However, in other embodiments
In, opposite order is also possible.
In addition, if variable length coding unit 2320 cannot compress all possible data values, then comparator is needed
2330 and selector 2340 and 2360, allow the variable length coding unit to determine whether data value will keep uncompressed
And its size is recorded as 0 in L- mask.It therefore, can be in all compressed alternate embodiments of all numerical value
This logic is omitted, therefore cL is connected to L- mask register 2350.
Therefore, the data compression device 2300 in Figure 23 further includes the detector of 2330 form of comparator, the detector coupling
It closes compressor 2320 and is configured to detect the number that cannot be compressed by compressor 2320 in unpressed data block 2310
According to value.Compressed data block generator 2340-2370 is configured to：It is not pressed when detector (comparator) 2330 has been detected by
When the data value of the data block 2310 of contracting cannot be compressed, the code length cL with particular value is stored in length mask L- mask
In corresponding position, and by this unpressed data value storage in compressed data block 2390.Disclosed
In embodiment, the particular value of code length is 0.
In addition, detector 2330 is configured to unpressed data block in the data compression device 2300 of Figure 23
Cannot be detected as by the data value that compressor 2320 compresses in 2310 is one of following or a variety of：
The data value being not present in the code table 2322 of compressor 2320,
It is present in code table but lacks in the code table of compressor the data value of code word 2325,
It is present in code table, there is code word 2325 in the code table but be indicated as invalid number in the code table of compressor
According to value.
In addition, compressed data block generator 2340-2370 is configured in the data compression device 2300 of Figure 23
At：By including the variable length provided by compressor 2320 by the order of the data value v1-vn of unpressed data block 2310
The unpressed data value spending the compressed data value of 2325 form of code word and being detected by detector 2330, to generate through pressing
The data block 2390 of contracting.
In the alternate embodiments of data compression device 2300, in the case where some data values keep unpressed situation,
It can choose the code word of unpressed data value and compressed data value is not admixed together.Alternatively, all not press
The data value of contracting is saved in different buffers, is placed on end in reverse order and to be concatenated device 2370 attached
It is connected to the end of compressed data block 2390.Although compressed data value and unpressed number in compressed data block
It is disturbed compared with unpressed data block according to the order of value, but original order is maintained in L- mask.It is unpressed
The example embodiment that data value is stored in such compressed data block of its end is illustrated in Figure 22.It is unpressed
Data value " 500 " appears in the 6th position of unpressed data block.By the way that 0 code length is placed on the 6th of L- mask
The end of compressed data block is placed in position and by unpressed data value " 500 " to record to it.It is described
The example embodiment of alternative data compression device can be realized by those skilled in the art.
Correspondingly, in the alternate embodiments of data compression device 2300, compressed data block generator 2340-
2370 are configured to：By include first by the data value v1-vn in unpressed data block 2310 order, by compressor
The compressed data value of 2320 2325 forms of variable length codeword provided, then includes being detected not by detector 2330
The data value of compression, to generate compressed data block 2390, or vice versa.Advantageously, the unpressed number is compared
According to order of the value in unpressed data block 2310, unpressed data value is stored in warp generated in reverse order
In the data block 2390 of compression.Because the order of all corresponding code length cL in length mask L- mask is in accordance with unpressed
The order of all data value v1-vn of data block 2310, so will still during the decompression of compressed data block 2390
Allow to rebuild all data values by original order of unpressed data block 2310.
The disclosure of figure 23 above can alternatively be considered as including the unpressed of one or more data values
The equipment (that is, data compression device) that compressed piece of data block boil down to；Wherein, the compressed data block is covered including position
Code and variable-length bit sequence, variable-length bit sequence further comprises carrying out encoding resulting one using variable length code
Or multiple compressed data values；Wherein, the equipment includes：Compressor, for utilizing the variable-length for corresponding to data value
Coding compresses the compressor of the data value；Mechanism, encoded with institute's bit mask record using variable length code obtained by
Compressed one or more encoding of a data value length.
The block diagram that the sample data decompression apparatus 2400 of the compressed data block of Figure 21 can be decompressed is drawn
In Figure 24.Data decompression device 2400 includes the compressed data block 2410 of preservation for being referred to as compression buffer 2405
(size of the storage unit 2405 is at least in uncompressed value length and maximum code word size the storage unit of a part
The maximum), code word extractor 2420, L- mask storage location 2430, value the (decompressor 1000 with Figure 10 of retrieval unit 2440
Value retrieval unit 1030 it is similar) and form the added logic 2450- of decompressed data block generator 2450-2470
2470.L- mask storage location 2430 save the top N of compressed data block 2410 and with data compression device 2300
L- mask is completely compatible.For example, N is 4*8=32 for the data block and 15 maximum codeword lengths of 8 data values
Position, while L- mask storage location 2430 includes 8 entries.Decompressed data block generator 2450-2470 includes checking
In the ratio that the compressed data value being decompressed is actually compressed or unpressed (therefore not needing to decompress)
It is selected between decoded data value 2445 and unpressed data value compared with device 2450, the result based on comparator 2450
Selector 2460 and keep be formed by the decompressed of the decompressed data block 2490 with data value v1 ... vn
Data block storage device 2470.
Block decompression is divided into execution step.At each execution step beginning, the L- of the length of certain code word is indicated
Mask entry be used to abandon by decompressed code word in the execution step, therefore the code word should not next execute step
The part of the bit sequence in compression buffer 2405 is stored in rapid.The discarding amount is referred to as " shift amount " in Figure 14.Such as
The length of the specific L- mask entry of fruit is 0, then shift amount is that the size of unpressed value (is similarly dependent on embodiment setting
It is determined in when meter, compilation, configuration or operation), for example, 32.In same execution step, CW (code word) extractor 2420 will
The compressed sequence being stored in compression buffer 2405 and the code word size conduct provided by L- mask storage location 2430
It inputs and goes out code word from compressed sequential extraction procedures.In this embodiment, code word extractor 2420 includes from buffer
Width subtracts the subtracter of code word size value and moves to right the input to unit 2420 by the displacement of subtracter amount calculated
Device.If the most left half of buffer includes the beginning of compressed sequence, shift unit is moved to right.Then, the code word being extracted
It is fed into the value retrieval unit 2440 that associated unpressed data value is determined using code word.L- mask storage location 2430
Code word size is also used for the appropriate offset between the offset 2444 in locator value retrieval unit 2440.
For example, the variable length code for the compressed data block 01111110101110 ... being such as plotted in Figure 21 includes
Code word 0,11,111101 etc., such as the L- mask " 1,2,6,1,4 ... " in the beginning of data block compressed as described in being saved in
Indicated.Therefore, in order to obtain and the associated data value of code word 0, it would be desirable to discarding bit sequence first
1111110101110 ... (this is executed by CW extractor 2420).In same step, we are also required to from compression buffer 2405
Code word 0 is abandoned, is obtained and associated second data value of the second code word 11 so as to be executed in step second.
By the way that the sample data decompression apparatus 2400 of Figure 24 is made comparisons with the decompression apparatus 1000 of Figure 10, Qian Zheke
With faster in the latter, because including (decompression apparatus 1020) codeword detection unit of comparator, priority encoder and displacement
1020 logical depth is than the logic including algorithm and (data decompression device 2400) CW extractor 2420 of shifting function
Depth is big.
As according to above it is evident that decompressed data block is raw in data decompression device 2400 in Figure 24
The 2450-2470 that grows up to be a useful person is configured to：
For one or more positions in length mask L- mask, the one or more corresponding data values of detection instruction
It include the code length that there is particular value in one or more of compressed data block 2410 in the form of unpressed；And
There is the code length of particular value based on detected one or more, by self solving compressor 2440 in the future
Decompressed data value data value corresponding with the one or more of the uncompressed form from compressed data block 2410
It is combined, to generate decompressed data block 2490.Again, the particular value of code length advantageously can be 0.
As explained above for data compression device 2300, in compressor side, unpressed data value do not need with
Compressed data value in variable length code 2355 mixes.The data block compressed so can be decompressed
The alternate embodiments of the data decompression device 2400 of contracting are illustrated in Figure 25.It is different from data decompression device 2400, number
It further include unpressed value extraction unit 2580 according to decompression apparatus 2500.Difference between equipment 2400 and 2500 exists
In the former will extract unpressed value from compression buffer 2405, and the latter is from comprising in the reverse order (that is, in the reverse order
The first unpressed data value, the second unpressed data value ..., last unpressed data value, variable length code)
The storage unit 2584 of compressed data block 2510 extract unpressed value.When L- mask entry contains length 0, will protect
It holds the counter-increments of the quantity of unpressed data value and is read accordingly using selector 2588 from storage unit 2584
Unpressed data value.In this data decompression device 2500, when L- mask entry is 0, compression buffer 2505
" shift amount " content is 0, is different from the equipment 2400 that " shift amount " is equal to the width of unpressed data value.Compression is slow as a result,
Rushing device 2505 can have narrower width (that is, be equal to maximum codeword length), or even by disclosed data decompression device
Logical depth more minimize.
Compared with decompression apparatus 1000, aforementioned data decompression apparatus 2400 and 2500 has improved performance, however,
Compressed data block is still sequentially decompressed.The data decompressions of 2 values can be decompressed in same execution step
The alternate embodiments of equipment 2400 are illustrated in Figure 26, wherein data decompression device 2600 is from same compressed data
Two streams of block concurrently decompress (for each execution step).This is completed by almost replicating 2400 unit, in addition to：
1) value retrieval unit 2640 is one (offset 2644 and DeLUT 2648 is mapped to 2 port stores)；And 2) L- mask
It is divided into two panels, 2630a and 2630b：2630a includes the first the half of L- mask, and 2630b include its second half.These lists
Member is now represented by " a " and " b ", for example, CW extractor 2620a and CW extractor 2620b, while data decompression device
2600 substantially include two decompressors：One decompressor includes all " a " units, another decompressor includes institute
" b " unit having.There is also additional unit, adders 2690.In an alternative embodiment, ground duplication value retrieval can be replaced
Unit.
In data decompression device 2600, decompression work is as follows：The half of L- mask is placed on storage unit
In 2630a and the other half is placed in 2630b.Then, add up L- mask the first half length value (2690) to calculate
In the beginning location by the second part in the resulting compressed data block of device " b " decompression is decompressed (from through compressing
Data block variable length code the beginning takeoff of position skipped).Two decompressors respectively will be decompressed
Value sub-block be maintained in the 2670a and 2670b being concatenated when all compressed data values are all decompressed.
In the alternate embodiments that 2 values are decompressed in same execution step, if replacing ground in same execution
2 values being decompressed in step are continuously that then L- mask can be maintained one and not need adder 2690.At this
In the example embodiment of sample, additional shift unit is needed to abandon and will be extracted by CW extractor " a " before CW extractor " b "
Code word.
When with hardware realization, increased additional areas/logic due to the parallelization in the data decompression device
Be compared with the additional logic required for for parallelization decompression apparatus 1000 it is lesser, because of codeword detection unit 1020
With the design more complicated than corresponding code word extractor 2620.
In the alternate embodiments that multiple compressed data values are concurrently decompressed, need by those skilled in the art
Member modifies decompressor design accordingly.
The disclosure of figure 24 above to Figure 26 can alternatively be considered as compressed data block decompression being one
The equipment (that is, data decompression device) of a or multiple data values；Wherein, the compressed data block includes bitmask and can
Elongated degree bit sequence further comprises carrying out encoding the resulting compressed data of one or more using variable length code
Value and the one or more code length values encoded with bitmask；Wherein, the equipment includes：Decompressor, for decompressing
Variable length code corresponds to the data value of the variable length code to rebuild；First mechanism, reading bitmask can with determination
The length of character code in elongated degree bit sequence；And second mechanism, using the instruction from the first mechanism with from variable-length position
Sequential extraction procedures character code and supply decompressor；And form the third mechanism of decompressed block.
It, can be by those skilled in the art in the aforementioned embodiments of data compression device and/or data decompression device
The delay cell of member's insertion such as trigger, so that the compression of the data value of a block and/or one compressed piece of value
Decompression can turn to multiple stages with pipeline to reduce the clock cycle and increase processing (compression or/and decompression) handling capacity.
In addition, by those skilled in the art and according to introduction commonly known per se, by the data value for compressing multiple pieces simultaneously
Or/and multiple compressed piece of the data values of decompression, can by open data compression device in this disclosure and/or
The alternate embodiments parallelization of data decompression device.In such circumstances, it needs by those skilled in the art to decompression
The design of contracting device is modified accordingly.
Corresponding data compression device 1600,1800,2300 in Figure 16, Figure 18 and Figure 23 can be for example with hardware reality
It is existing, for example, being embodied as the digital circuit in integrated circuit, special equipment (such as Memory Controller), programmable processing equipment
(such as central processing unit (CPU) or digital signal processor (DSP), field programmable gate array (FPGA), etc..Description
The function of corresponding data compression method in this disclosure can for example by being suitably configured corresponding data pressure
Contracting equipment 1600,1800,2300 executes, or as the corresponding computer program product including following code commands, described
Code command causes the execution of correlation method when being loaded and being executed by general purpose processing device such as CPU or DSP.
Corresponding data decompression device 1700 in Figure 17, Figure 19, Figure 24, Figure 25 and Figure 26,1900,2400,2500,
2600 can be for example with hardware realization, for example, being embodied as the digital circuit in integrated circuit, special equipment (such as memory control
Device processed), programmable processing equipment (such as central processing unit (CPU) or digital signal processor (DSP), field programmable gate
Array (FPGA), etc..The function of the corresponding uncompressing data of description in this disclosure can be for example by being fitted
The corresponding data decompression device 1700,1900,2400,2500,2600 of locality configuration executes, or as including following generations
The corresponding computer program product of code instruction, the code command is by general purpose processing device such as CPU or DSP (such as Fig. 1
Cause the execution of correlation method when loading and execute to any processing unit P1 ... Pn of Fig. 5).
Example embodiment disclosed herein proposes the method for following data block compression and decompressions, equipment and is
System, so that more compactly storage or transmission information, the data block compression and decompression are：Computer system caching/deposit
In reservoir subsystem or for the cache/memories subsystem data block compression and decompression, in the number of computer system
According in transmission subsystem or for the data transmission sub-system data block compression and decompression or in a communication network
Or the data block compression and decompression for the communication network.
Figure 33 instantiates general-purpose system 3300 according to the present invention.The system includes one or more memories 3310, number
According to compression device 3320 (such as, for example, any data compression device 1600,1800,2300) and data decompression device
3330 (such as, for example, any data decompression device 1700,1900,2400,2500,2600).Advantageously, system 3300
It is computer system (any computer system 100-500 of such as Fig. 1 to Fig. 5), and one or more of memories
It 3310 is one or more buffer memories (any buffer memory L1-L3 of such as Fig. 1 to Fig. 5), one or more random
Access memory (any memory 130-530 of such as Fig. 1 to Fig. 5) or one or more additional storages.Advantageously, it is
System 3300 is data communication system (communication network 600,700 of such as Fig. 6 to Fig. 7), wherein one or more of memories
3310 can be in data communication system transmitting node and the associated data buffer of receiving node (such as Fig. 6 is to Fig. 7's
Transmitter 610,710 and receiver 620,720).
Although they are not limited to disclosed reality using example embodiment to being described for the use of of the invention
Mode is applied, and covers the alternative embodiment that can be realized by those skilled in the art.
Claims (49)
1. a kind of data compression device (1600；1800), being used for will be including the unpressed data block of n data value (v1-vn)
(1610；1810) the compressed data block (1690 of boil down to；1890), the data compression device includes：
Compressor (1620；1820), the compressor is configured to the data value boil down to pair of the unpressed data block
The variable length codeword (1625 answered；1825)；
Detector (1630；1830), the detector is configured to detect at least one particular data value (1632；1832) institute
State unpressed data block (1610；1810) presence in；And
Compressed data block generator (1640-1670；1840-1870), the compressed data block generator with it is described
Compressor and the detector are coupled and configured to by being combined to generate the compressed data block by following
(1690；1890)：
Data value mask (Z value mask), the data value mask include n mask position, wherein each mask position instruction
The unpressed data block (1610；1810) corresponding data value in whether with by the detector (1630；1830) it examines
At least one the described particular data value (1632 measured；1832) any one particular data value in is equal；And
For the unpressed data block (1610；1810) in at least one described particular data value (1632；
1832) unequal data value is carried out compressing resulting corresponding variable length codeword by the compressor,
Wherein, the compressed data block (1690；It 1890) include the data value mask (Z value mask) and m variable length
Spend code word, wherein m≤n, and wherein, in the compressed data block (1690；It 1890) does not include not pressed for described in
The data block (1610 of contracting；1810) in at least one described particular data value (1632；1832) any one certain number in
According to the variable length codeword for being worth equal data value.
2. data compression device according to claim 1, wherein the detector (1630；1830 are configured to detect one
A particular data value (1632；1832) in the unpressed data block (1610；1810) presence in, and wherein, it is described
Each mask position in n mask position of data value mask (Z value mask) includes single position.
3. data compression device according to claim 1, wherein the detector (1630；1830) it is configured to detect
Multiple and different particular data values (1632；1832) in the unpressed data block (1610；1810) presence in, and its
In, each mask position in n mask position of the data value mask (Z value mask) includes can be to multiple certain numbers
According to value (1632；1832) bit combination for the fixed size that any one particular data value in is encoded.
4. according to data compression device described in any one preceding claims, wherein at least one described particular data value
(1632；1832) particular data value or each particular data value in are the data values frequently occurred, if ground is replaced to use
Variable length code, the data value frequently occurred may be utilized least position and be encoded.
5. data compression device according to any one of claim 1-3, wherein at least one described particular data value
(1632；1832) particular data value or each particular data value in are the data for requiring quickly to decompress very much when present
Value.
6. according to data compression device described in any one preceding claims, wherein at least one described particular data value
(1632；1832) particular data value or a particular data value in are 0.
7. according to data compression device described in any one preceding claims when being subordinated to claim 2, wherein the inspection
Survey device (1630；It 1830) include comparator (1630；1830), the comparator has：
First input (1631a, 1831a), first input are configured to receive in the unpressed data block (1610；
1810) data value (v1-vn) at the corresponding data value positions in；
Second input (1631b, 1831b), second input are configured to receive the particular data value (1632；1832)；
And
Output (1633；1833), the output is configured to export the particular data value (1632；1832) it is not pressed with described
The data block (1610 of contracting；1810) knot of the comparison between the data value (v1-vn) at the corresponding data value positions in
Fruit.
8. data compression device according to claim 7,
Wherein, the compressed data block generator (1640-1670；It 1840-1870) include that there are a n storage locations
Mask register (1640；1840), each storage location is a for the n of the data value mask (Z value mask)
A mask position in mask position, and
Wherein, the comparator (1630；1830) output (1633；1833) it is coupled to the mask register (1640；
1840), so that utilizing the particular data value (1632；1832) and in the unpressed data block (1610；1810) in
The comparison result between the data value (v1-vn) at corresponding data value positions makes the mask register
(1640；1840) it is updated at the corresponding storage location in its n storage location.
9. data compression device according to claim 7 or 8, wherein the compressed data block generator (1640-
1670；It 1840-1870) include storage unit (1650；1850), the storage unit has：
First input of the first input (1651a, 1851a), the storage unit is configured to from the compressor (1620；
1820) it receives and in the unpressed data block (1610；1810) data value at corresponding data value positions in
(v1-vn) corresponding variable length codeword (1625；1825) it is single and by the received variable length codeword of institute to be stored in the storage
Member (1650；1850) in；
Output (1653；1853), the variable length codeword (1625 that the output of the storage unit is configured to be stored；
1825) it is output to the variable length code (1655 of accumulation；1855) in；And
Second input (1631b, 1831b), the second input of the storage unit, which is configured to receive, depends on the comparator
(1630；1830) output (1633；1833) control signal,
Wherein, the storage unit (1650；1850) it is configured to：When by the comparator (1630；1830) what is carried out is described
Result of the comparison indicate that the particular data value (1632；1832) and in the unpressed data block (1610；1810) in
When matching between the data value (v1-vn) at corresponding data value positions, forbid stored variable length codeword
(1625；1825) it is output to the variable length code (1655；1855) in.
10. according to data compression device described in claim 8 and 9, wherein the compressed data block generator (1640-
1670；It 1840-1870) include connector (1670；1870), the connector is configured to：When the unpressed data block
(1610；1810) when all n data values (v1-vn) are processed, by the way that the mask register will be come from
(1640；1840) variable length code (1655 of the data value mask (Z value mask) and the accumulation；1855) connection comes
Generate the compressed data block (1690；1890).
11. data compression device according to claim 10, wherein in the compressed data block (1690；1890)
In, the data value mask (Z value mask) is placed in the variable length code (1655 of the accumulation；1855) before.
12. a kind of data compression method, for that will include the unpressed data block of scheduled n data value (v1-vn)
(1610；1810) the compressed data block (1690 of boil down to；1890), the data compression method includes：
By the corresponding variable length codeword (1625 of the data value boil down to of the unpressed data block；1825)；
Detect at least one particular data value (1632；1832) in the unpressed data block (1610；1810) presence in；
And
By being combined to generate the compressed data block (1690 by following；1890)：
Data value mask (Z value mask), the data value mask include n mask position, wherein each mask position instruction
The unpressed data block (1610；1810) corresponding data value in whether at least one described particular data value
(1632；1832) any one particular data value in is equal；And
For the unpressed data block (1610；1810) in at least one described particular data value (1632；
1832) all unequal data value of any one particular data value in, corresponding variable length codeword,
Wherein, the compressed data block (1690；It 1890) include the data value mask (Z value mask) and m variable length
Spend code word, wherein m≤n, and wherein, in the compressed data block (1690；It 1890) does not include not pressed for described in
The data block (1610 of contracting；1810) in at least one described particular data value (1632；1832) any one certain number in
According to the variable length codeword for being worth equal data value.
13. a kind of data decompression device (1700；1900) it, is used for compressed data block (1710；1910) decompression is condensed to
Decompressed data block (1790；1990), the decompressed data block includes n at corresponding data value positions
Data value (v1-vn), the data decompression device include：
Decompressor (1720-1730；1920-1930), the decompressor is configured to the compressed data block
Variable length codeword (1625；1825) decompression is condensed to corresponding decompressed data value (1735；1935)；And
Decompressed data block generator (1740-1780；1940-1980), the decompressed data block generator quilt
It is configured to：
From the compressed data block (1710；1910) the data value mask (Z value mask) comprising n mask position is read,
Wherein, the unpressed data block (1610 of each mask position instruction；1810) the corresponding data value in is described through pressing in generation
The data block (1690/1710 of contracting；1890/1910) before data compression whether at least one particular data value (1632；
1832) any one particular data value in is equal；And
It is worth mask (Z value mask) based on the data, by the way that the decompressor (1720-1730 will be come from；1920-1930)
Decompressed data value and the corresponding mask position instruction by the data value mask (Z value mask) it is described at least one
Particular data value (1782；1982) it is combined, to generate the decompressed data block (1790；1990),
Wherein, decompressed data block (1790 generated；1990) order of data value is with the data value described
In the unpressed data block (1610 before data compression；1810) order occurred in is identical.
14. data decompression device according to claim 13, wherein n of the data value mask (Z value mask) cover
Each mask position in code position includes to indicate or do not indicate a particular data value (1782；1982) single position.
15. data decompression device according to claim 13, wherein n of the data value mask (Z value mask) cover
Each mask position in code position includes that can decode multiple particular data values (1782；1982) any one certain number in
According to the bit combination of the fixed size of value.
16. data decompression device described in any one of 3-15 according to claim 1, wherein at least one described certain number
According to value (1782；1982) particular data value or a particular data value in are 0.
17. data decompression described in any one of 4 or the claim 16 when being subordinated to claim 14 according to claim 1
Equipment, wherein the decompressed data block generator (1740-1780；1940-1980) include：
It is worth position generator (1740；1940)；
It is worth position assigner (1760；1960)；And
Multiple selectors (1780；1980), each selector is used for the decompressed data block (1790；1990) n
A data value positions in data value positions,
Wherein, described value position generator (1740；1940) it is configured to control described value position assigner (1760；1960) and
The multiple selector (1780；1980), so that working as the corresponding mask position instruction institute of the data value mask (Z value mask)
State particular data value (1782；1982) when, the particular data value (1782 is received from corresponding selector；1982) and make described
Particular data value includes in the decompressed data block (1790；1990) it is located at corresponding data value positions in, and
So that the corresponding mask position when the data value mask (Z value mask) does not indicate the particular data value (1782；1982)
When, from the decompressor (1720-1730；It 1920-1930) receives corresponding decompressed data value and makes described through solving
The data value of compression includes in the decompressed data block (1790；1990) it is located at corresponding data value positions in.
18. a kind of uncompressing data is used for compressed data block (1710；1910) decompression is condensed to decompressed number
According to block (1790；1990), the decompressed data block includes the n data value (v1- at corresponding data value positions
Vn), the uncompressing data includes：
By the variable length codeword (1625 of the compressed data block；1825) decompression is condensed to corresponding decompressed data
Value (1735；1935)；
From the compressed data block (1710；1910) the data value mask (Z value mask) comprising n mask position is read,
Wherein, the unpressed data block (1610 of each mask position instruction；1810) the corresponding data value in is described through pressing in generation
The data block (1690/1710 of contracting；1890/1910) before data compression whether at least one particular data value (1632；
1832) any one particular data value in is equal；And
It is worth mask (Z value mask) based on the data, by by decompressed data value and by data value mask (the Z value
Mask) corresponding mask position instruction at least one described particular data value (1782；1982) it is combined, it is described to generate
Decompressed data block (1790；1990),
Wherein, decompressed data block (1790 generated；1990) order of data value is with the data value described
In the unpressed data block (1610 before data compression；1810) order occurred in is identical.
19. a kind of data compression device (1800), for that will include the unpressed data block of n data value (v1-vn)
(1810) the compressed data block of boil down to (1890), the data compression device include：
Compressor (1820), the compressor be configured to by the data value boil down to of the unpressed data block is corresponding can
Variable length code word (1825)；
Detector (1830), the detector are configured to detect at least one particular data value (1832) described unpressed
Presence in data block (1810)；And
Compressed data block generator (1840-1870), the compressed data block generator and the compressor and institute
Detector coupling is stated, and is configured to generate the data value mask (Z value mask) comprising n mask position, wherein is each covered
Code position indicates whether the corresponding data value in the unpressed data block (1810) is examined with by the detector (1830)
Any one particular data value at least one described particular data value (1832) measured is equal,
Wherein, the compressed data block generator (1840-1870) includes mask code generator (1860), the mask
Code generator is configured to：
Analyze data value mask generated (Z value mask), including the determination data value mask whether with a variety of mask modes
In any mask pattern match；And
Mask coding (1868) is generated to represent the result of the analysis；
Wherein, the compressed data block generator (1840-1870) is further configured to by that at least following will be combined to
Generate the compressed data block (1890)：
Mask generated encodes (1868)；And
For in the unpressed data block (1810) with any at least one described particular data value (1832)
The all unequal data value of a particular data value is carried out compressing resulting corresponding variable length codeword by the compressor,
Wherein, the compressed data block (1890) includes that mask generated encodes (1868) and m variable length codeword,
Wherein, m≤n, and wherein, it does not include for the unpressed data block in the compressed data block (1890)
(1810) data value equal with any one particular data value at least one described particular data value (1832) in can
Variable length code word, and
Wherein, the compressed data block (1890) further includes the data value mask (Z value mask), unless by the mask
The analysis that code generator (1860) carries out the result is that not pressed described in data value mask (Z value mask) generated instruction
The predetermined repeat pattern of particular data value in the data block (1810) of contracting.
20. data compression device according to claim 19, wherein the mask code generator (1860) is configured
At：When data value mask generated (Z value mask) instruction particular data value position in the unpressed data block (1810)
When predetermined repeat pattern at a data value positions, generating, there is the mask of the first mask encoded radio to encode
(1868), and wherein, in compressed data block (1890) generated only include the mask coding (1868) without
Including the data value mask (Z value mask).
21. data compression device according to claim 20, wherein the mask code generator (1860) is configured
At：When data value mask generated (Z value mask) instruction particular data value position in the unpressed data block (1810)
In at a data value positions however relative to one position of the predetermined repeat pattern of the first mask encoded radio offset
Predetermined repeat pattern when, generating, there is the mask of the second mask encoded radio to encode (1868), and wherein, generated
Compressed data block (1890) in only include the mask coding (1868) without include the data value mask (Z value is covered
Code).
22. data compression device according to claim 21, wherein the mask code generator (1860) is configured
At：When data value mask generated (Z value mask) instruction is at least one of described unpressed data block (1810) number
According in value position, there are when particular data value, generate the mask coding (1868) with third mask encoded radio, and its
In, it include mask coding (1868) and the data value mask (Z in compressed data block (1890) generated
It is worth mask).
23. data compression device according to claim 22, wherein the mask code generator (1860) is configured
At：When data value mask generated (Z value mask) indicates all data values in the unpressed data block (1810)
When particular data value being all not present in position, generating, there is the mask of the 4th mask encoded radio to encode (1868), and its
In, it only include mask coding (1868) without including the data value in compressed data block (1890) generated
Mask (Z value mask).
24. data compression device described in any one of 9-23 according to claim 1, wherein in the compressed data block
(1890) in, the mask coding (1868) is placed in front of the m variable length codeword, and wherein, described through compressing
Data block (1890) in, if there is the data value mask (Z value mask), then the data value mask is arranged in the mask
(1868) are encoded later and before the m variable length codeword.
25. a kind of data compression method, for that will include unpressed data block (1810) compression of n data value (v1-vn)
For compressed data block (1890), the data compression method includes：
By the corresponding variable length codeword of data value boil down to (1825) of the unpressed data block；
Detect presence of at least one particular data value (1832) in the unpressed data block (1810)；
Generate the data value mask (Z value mask) comprising n mask position, wherein uncompressed described in each mask position instruction
Data block (1810) in corresponding data value it is whether special with any of at least one particular data value (1832)
It is equal to determine data value；
Analyze data value mask generated (Z value mask), including the determination data value mask whether with a variety of mask modes
In any mask pattern match；
Mask coding (1868) is generated to represent the result of the analysis；And
By that at least following will be combined to generate the compressed data block (1890)：
Mask generated encodes (1868)；And
For in the unpressed data block (1810) with any at least one described particular data value (1832)
The all unequal data value of a particular data value is carried out compressing resulting corresponding variable length codeword by the compressor,
Wherein, the compressed data block (1890) includes that mask generated encodes (1868) and m variable length codeword,
Wherein, 0≤m≤n, and wherein, it does not include for the unpressed data in the compressed data block (1890)
The data value equal with any one particular data value at least one described particular data value (1832) in block (1810)
Variable length codeword, and
Wherein, the compressed data block (1890) further includes the data value mask (Z value mask), unless the analysis step
It is rapid the result is that data value mask (Z value mask) generated indicates the specific data in the unpressed data block (1810)
The predetermined repeat pattern of value.
26. a kind of data decompression device (1900), decompressed for compressed data block (1910) decompression to be condensed to
Data block (1990), the decompressed data block include the n data value (v1-vn) at corresponding data value positions,
The data decompression device includes：
Decompressor (1920-1930), the decompressor are configured to the variable-length code (VLC) of the compressed data block
Word (1825) decompression is condensed to corresponding decompressed data value (1935)；And
Decompressed data block generator (1940-1980), the decompressed data block generator are configured to：
Mask coding (1915) is read from the compressed data block (1910), the mask coding (1915) represents a variety of cover
Any mask mode in pattern；
When the mask mode represented by read mask coding (1915) does not indicate generating the compressed data
Any particular data value before the data compression of block (1890/1910) at least one particular data value is described unpressed
When predetermined repeat pattern in data block (1810), reading from the compressed data block (1910) includes n mask position
Data value mask (Z value mask), wherein it is corresponding in unpressed data block (1810) described in each mask position instruction
Whether data value is equal to any one particular data value at least one described particular data value (1832) before data compression；
And
Based on mask coding (1915) and the data value mask (Z value mask) under usable condition, by will be following
The two is combined to generate the decompressed data block (1990), and one of both described is from the decompressor
The decompressed data value of (1920-1930), the other of both described is by encoding (1915) generation by the mask
The predetermined repeat pattern instruction of table or pass through the corresponding of the data value mask (Z value mask) under usable condition
Mask position instruction at least one described particular data value (1982),
Wherein, the order of the data value of decompressed data block (1990) generated and the data value are in the data pressure
The order occurred in the unpressed data block (1810) before contracting is identical.
27. data decompression device according to claim 26, wherein the decompressed data block generator
(1940-1980) is configured to pass through following manner when read mask, which encodes (1915), has the first mask encoded radio
To generate the decompressed data block (1990)：The mode will come from the warp of the decompressor (1920-1930)
The data value of decompression is combined at least one described particular data value (1982) in following predetermined repeat patterns, described
Predetermined repeat pattern be particular data value in the unpressed data block (1990) at a data value positions.
28. data decompression device according to claim 27, wherein the decompressed data block generator
(1940-1980) is configured to pass through following manner when read mask, which encodes (1915), has the second mask encoded radio
To generate the decompressed data block (1990)：The mode will come from the warp of the decompressor (1920-1930)
The data value of decompression is combined at least one described particular data value (1982) in following predetermined repeat patterns, described
The predetermined repeat pattern of second mask encoded radio be particular data value in the decompressed data block (1990) every
At one data value positions, however a position is deviated relative to the predetermined repeat pattern of the first mask encoded radio.
29. data decompression device according to claim 28, wherein the decompressed data block generator
(1940-1980) is configured to：When read mask coding (1915) has third mask encoded radio, by the way that institute will be come from
State the decompressed data value of decompressor (1920-1930) and corresponding the covering by the data value mask (Z value mask)
At least one described particular data value (1982) of code position instruction is combined, to generate the decompressed data block
(1990)。
30. data decompression device according to claim 29, wherein the decompressed data block generator
(1940-1980) is configured to：When read mask coding (1915) has the 4th mask encoded radio, generate comprising coming from
The decompressed data block (1990) of all decompressed data values of the decompressor (1920-1930).
31. a kind of uncompressing data, for compressed data block (1910) decompression to be condensed to decompressed data block
(1990), the decompressed data block includes the n data value (v1-vn) at corresponding data value positions, the number
Include according to decompression method：
Variable length codeword (1825) decompression of the compressed data block is condensed to corresponding decompressed data value
(1935)；
Mask coding (1915) is read from the compressed data block (1910), the mask coding (1915) represents a variety of cover
Any mask mode in pattern；
When the mask mode represented by read mask coding (1915) does not indicate generating the compressed data
Any particular data value before the data compression of block (1890/1910) at least one particular data value is in unpressed data
When predetermined repeat pattern in block (1810), read from the compressed data block (1910) include n mask position number
According to value mask (Z value mask), wherein the corresponding data in unpressed data block (1810) described in each mask position instruction
It is worth any one particular data value whether being equal at least one described particular data value (1832) before data compression；And
Based on mask coding (1915) and the data value mask (Z value mask) under usable condition, by will be following
The two is combined to generate the decompressed data block (1990), and one of both described is decompressed data
Value, it is the other of both described be it is by the predetermined repeat pattern instruction that is represented by mask coding (1915) or
Person by the corresponding mask position instruction of the data value mask (Z value mask) under usable condition it is described at least one
Particular data value (1982),
Wherein, the order of the data value of decompressed data block (1990) generated and the data value are in the data pressure
The order occurred in the unpressed data block (1810) before contracting is identical.
32. a kind of data compression device (2300), for that will include the unpressed data block of n data value (v1-vn)
(2310) the compressed data block of boil down to (2390), the data compression device include：
Compressor (2320), the compressor be configured to by the data value boil down to of the unpressed data block is corresponding can
Variable length code word (2325), and export the variable length codeword (2325) and its corresponding code length (cL)；
Compressed data block generator (2340-2370), the compressed data block generator are coupled with the compressor
And including the length mask register (2350) with n storage location, each storage location is for described uncompressed
Data block (2310) n data value (v1-vn) in a data value, the length mask register (2350) is configured
For storing the length mask (L- mask) of n position,
Wherein, the compressed data block generator (2340-2370) is configured in the length mask (L- mask)
The corresponding code length (cL) for the variable length codeword (2325) that corresponding position storage is provided by the compressor (2320), and
Wherein, the compressed data block generator (2340-2370) is configured to by being combined to generate institute by following
State compressed data block (2390)：
The length mask (L- mask) being stored in the length mask register (2350)；And
By the compressed data value of variable length codeword (2325) form that the compressor (2320) provide.
33. data compression device according to claim 32, wherein in the compressed data block (2390), institute
Length mask (L- mask) is stated to be placed in front of the variable length codeword (2325).
34. the data compression device according to claim 32 or 33 further includes detector (2330), the detector and institute
State compressor (2320) be coupled and configured to detect in the unpressed data block (2310) cannot be by the compression
The data value of device (2320) compression,
Wherein, the compressed data block generator (2340-2370) is configured to：When the detector (2330) has been examined
It measures the data value of the unpressed data block (2310) and stores the code length (cL) with particular value when cannot be compressed
Corresponding position in the length mask (L- mask), and by the unpressed data value storage in the compressed number
According in block (2390).
35. data compression device according to claim 34, wherein the particular value of the code length is 0.
36. the data compression device according to claim 34 or 35, wherein the detector (2330) is configured to institute
State cannot be detected as by the data value that the compressor (2320) are compressed in following one in unpressed data block (2310)
Kind is a variety of：
The data value being not present in the code table (2322) of the compressor (2320),
It is present in the code table but lacks in the code table of the compressor data value of code word (2325),
It is present in the code table, there are code word (2325) in the code table but referred in the code table of the compressor
It is shown as invalid data value.
37. the data compression device according to any one of claim 34-36, wherein the compressed data block is raw
Grow up to be a useful person (2340-2370) be configured to：By including by the data value (v1- in the unpressed data block (2310)
Vn order) by the compressor (2320) provide variable length codeword (2325) form compressed data value and by
The unpressed data value that the detector (2330) detects, to generate the compressed data block (2390).
38. the data compression device according to any one of claim 34-36, wherein the compressed data block is raw
Grow up to be a useful person (2340-2370) be configured to generate the compressed data block (2390) by following manner：The mode is
By include first by the data value (v1-vn) in the unpressed data block (2310) order, by the pressure
The compressed data value of variable length codeword (2325) form that contracting device (2320) provides, then includes by the detector
(2330) the unpressed data value detected, or vice versa, wherein all phases in the length mask (L- mask)
The order for the code length (cL) answered in accordance with all data values (v1-vn) of the unpressed data block (2310) order, by
This permission rebuilds pressing for unpressed data block (2310) during the decompression of the compressed data block (2390)
All data values of original order.
39. the data compression device according to claim 38, wherein the unpressed data value with its it is described not
Order in the data block (2310) of compression is stored in compressed data block (2390) generated compared to opposite order.
40. a kind of data compression method, for that will include unpressed data block (2310) compression of n data value (v1-vn)
For compressed data block (2390), the data compression method includes：
By the corresponding variable length codeword of data value boil down to (2325) of the unpressed data block, and can described in output
Variable length code word (2325) and its corresponding code length (cL)；
The length mask (L- mask) of n position is stored in the length mask register (2350) with n storage location,
Each storage location is used for a data value in the n data value (v1-vn) of the unpressed data block (2310),
The corresponding code length (cL) of variable length codeword (2325) is stored in the corresponding positions in the length mask (L- mask)
Place is set, and
By being combined to generate the compressed data block (2390) by following：
The length mask (L- mask) being stored in the length mask register (2350)；And
The compressed data value of variable length codeword (2325) form.
41. a kind of data decompression device (2400；2500；2600) it, is used for compressed data block (2410；2510；
2610) decompression is condensed to decompressed data block (2490；2590；2690), the decompressed data block is included in accordingly
Data value positions at n data value (v1-vn), the data decompression device includes：
Decompressor (2440；2540；2640), the decompressor is configured to the variable length of the compressed data block
Degree code word decompression is condensed to corresponding decompressed data value (2445；2545；2645)；
Extractor mechanism (2420-2435；2520-2535；2620-2635), the extractor mechanism is used for：From described through compressing
Data block (2410；2510；2610) the length mask (L- mask) of n position is read, (L- is covered according to the length mask
Code) determine the compressed data block (2410；2510；2610) the corresponding code length of the variable length codeword in, is based on
Identified corresponding code length is from the compressed data block (2410；2510；2610) corresponding variable-length code (VLC) is extracted
Word, and extracted corresponding variable length codeword is supplied to the decompressor (2440；2540；2640)；And
Decompressed data block generator (2450-2470；2550-2570；2650-2670), the decompressed data
Module generator is configured to according to from the decompressor (2440；2540；2640) the decompressed data value is raw
At the decompressed data block (2490；2590；2690),
Wherein, decompressed data block (2490 generated；2590；2690) order of data value and the data value exist
The order occurred in the unpressed data block (2310) before data compression is identical.
42. data decompression device according to claim 41, wherein the decompressed data block generator
(2450-2470；2550-2570；2650-2670) it is configured to：
For one or more positions in the length mask (L- mask), one or more code lengths with particular value are detected
Degree, the one or more corresponding data values of particular value instruction are included in the compressed data block in the form of unpressed
(2410；2510,2584；2610) in；And
Based on detected one or more code lengths with the particular value, by the way that the decompressor will be come from
(2440；2540；2640) decompressed data value with come from the compressed data block (2410；2510；2610)
One or more of corresponding data values of uncompressed form are combined to generate the decompressed data block (2490；
2590；2690).
43. data decompression device according to claim 42, wherein the particular value of code length is 0.
44. a kind of uncompressing data is used for compressed data block (2410；2510；2610) decompression is condensed to through decompressing
The data block (2490 of contracting；2590；2690), the decompressed data block includes n at corresponding data value positions
Data value (v1-vn), the uncompressing data include：
From the compressed data block (2410；2510；2610) the length mask (L- mask) of n position is read；
The compressed data block (2410 is determined according to the length mask (L- mask)；2510；2610) variable length in
Spend the corresponding code length of code word；
Based on identified corresponding code length from the compressed data block (2410；2510；2610) it extracts and accordingly may be used
Variable length code word；
Extracted variable length codeword decompression is condensed to corresponding decompressed data value (2445；2545；2645)；And
The decompressed data block (2490 is generated according to the decompressed data value；2590；2690),
Wherein, decompressed data block (2490 generated；2590；2690) order of data value and the data value exist
The order occurred in the unpressed data block (2310) before data compression is identical.
45. a kind of system (3300), the system comprises one or more memories (3310), according to claim 1-11,19-
Data compression device (3320 described in any one of 24 or 32-39；1600；1800) and according to claim 1 3-17,26-
Data decompression device (3330 described in any one of 30 or 41-43；1700,1900).
46. system (3300) according to claim 45, wherein the system is computer system (100；200；300；
400；500), and wherein, one or more of memories (3310) carry out the group of freely following compositions：
Buffer memory (L1-L3),
Random access memory (130；230；330；430；530), and
Additional storage.
47. system (1900) according to claim 45, wherein the system is data communication system (600；700), and
And wherein, one or more of memories (3310) are data buffers.
48. a kind of computer program product, the computer program product includes code command, and the code command is by handling
Equipment loads and causes the execution of method described in 2,25 or 40 according to claim 1 when executing.
49. a kind of computer program product, the computer program product includes code command, and the code command is by handling
Equipment loads and causes the execution of method described in 8,31 or 44 according to claim 1 when executing.
Applications Claiming Priority (5)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| SE1650119-9 | 2016-01-29 | ||
| SE1650119 | 2016-01-29 | ||
| SE1650767-5 | 2016-06-01 | ||
| SE1650767A SE540178C2 (en) | 2016-01-29 | 2016-06-01 | Methods, devices and systems for compressing and decompressing data |
| PCT/SE2017/050078 WO2017131579A1 (en) | 2016-01-29 | 2017-01-30 | Methods, devices and systems for compressing and decompressing data |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN108886367A true CN108886367A (en) | 2018-11-23 |
| CN108886367B CN108886367B (en) | 2022-01-11 |
Family
ID=59398468
Family Applications (2)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201780015262.7A Active CN108702160B (en) | 2016-01-29 | 2017-01-27 | Method, apparatus and system for compressing and decompressing data |
| CN201780015236.4A Active CN108886367B (en) | 2016-01-29 | 2017-01-30 | Method, apparatus and system for compressing and decompressing data |
Family Applications Before (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201780015262.7A Active CN108702160B (en) | 2016-01-29 | 2017-01-27 | Method, apparatus and system for compressing and decompressing data |
Country Status (2)
| Country | Link |
|---|---|
| CN (2) | CN108702160B (en) |
| WO (2) | WO2017131578A1 (en) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN111814009A (en) * | 2020-06-28 | 2020-10-23 | 四川长虹电器股份有限公司 | BF improved algorithm based on search engine retrieval information pattern matching |
| CN114637459A (en) * | 2020-12-16 | 2022-06-17 | 株式会社日立制作所 | device for processing received data |
Families Citing this family (9)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2016186563A1 (en) | 2015-05-21 | 2016-11-24 | Zeropoint Technologies Ab | Methods, devices and systems for hybrid data compression and decompression |
| SE540178C2 (en) | 2016-01-29 | 2018-04-24 | Zeropoint Tech Ab | Methods, devices and systems for compressing and decompressing data |
| WO2020130929A1 (en) * | 2018-12-21 | 2020-06-25 | Zeropoint Technologies Ab | Methods, devices and systems for efficient compression and decompression for higher throughput |
| US11489541B2 (en) * | 2019-05-21 | 2022-11-01 | Nvidia Corporation | Compression techniques for data structures suitable for artificial neural networks |
| RU2729509C1 (en) * | 2019-12-23 | 2020-08-07 | федеральное государственное автономное образовательное учреждение высшего образования "Национальный исследовательский ядерный университет МИФИ" (НИЯУ МИФИ) | Device for unpacking data |
| US10911267B1 (en) * | 2020-04-10 | 2021-02-02 | Apple Inc. | Data-enable mask compression on a communication bus |
| US11362672B2 (en) * | 2020-05-08 | 2022-06-14 | Qualcomm Incorporated | Inline decompression |
| SE544557C2 (en) * | 2020-12-01 | 2022-07-12 | Zeropoint Tech Ab | Systems, methods and devices for exploiting value similarity in computer memories |
| CN118337217A (en) * | 2023-01-12 | 2024-07-12 | 华为技术有限公司 | Method for compressing data, method for decompressing data, device, system and medium |
Citations (11)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20020066007A1 (en) * | 1992-06-30 | 2002-05-30 | Wise Adrian P. | Multistandard video decoder and decompression system for processing encoded bit streams including pipeline processing and methods relating thereto |
| US20030090709A1 (en) * | 2001-11-07 | 2003-05-15 | International Business Machines Corporation | System and method for efficient compression of raster image data |
| US20030090398A1 (en) * | 2001-11-07 | 2003-05-15 | International Business Machines Corporation | System and method for efficient data compression |
| US20040178933A1 (en) * | 2003-03-11 | 2004-09-16 | Canon Kabushiki Kaisha | Encoding method and encoding apparatus, and computer program and computer readable stroage medium |
| CN1599258A (en) * | 2004-06-25 | 2005-03-23 | 浙江大学 | Coding mode suitable for different refrared control signal |
| CN1606038A (en) * | 2003-10-29 | 2005-04-13 | 威盛电子股份有限公司 | A device for compressing data in a bit pattern or bit stream |
| US20080317299A1 (en) * | 2007-06-21 | 2008-12-25 | Canon Kabushiki Kaisha | Image processing apparatus and control method thereof |
| US20130170556A1 (en) * | 2011-12-29 | 2013-07-04 | Microsoft Corporation | Variable length coding and decoding using counters |
| CN103563255A (en) * | 2011-04-11 | 2014-02-05 | 马维尔国际贸易有限公司 | Method for compression and real-time decompression of executable code |
| US9031852B2 (en) * | 2012-08-01 | 2015-05-12 | Nintendo Co., Ltd. | Data compression apparatus, computer-readable storage medium having stored therein data compression program, data compression system, data compression method, data decompression apparatus, data compression/decompression apparatus, and data structure of compressed data |
| CN105264779A (en) * | 2013-01-22 | 2016-01-20 | 阿尔特拉公司 | Data compression and decompression using simd instructions |
Family Cites Families (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN1157653C (en) * | 1994-04-22 | 2004-07-14 | 索尼公司 | Device and method for transmitting data, and device and method for recording data |
| US6272453B1 (en) * | 1998-01-05 | 2001-08-07 | Trw Inc. | Concurrent legacy and native code execution techniques |
| US6492991B1 (en) * | 1998-08-28 | 2002-12-10 | Ati International Srl | Method and apparatus for controlling compressed Z information in a video graphics system |
| JP4479530B2 (en) * | 2004-12-28 | 2010-06-09 | カシオ電子工業株式会社 | Data compression apparatus and data restoration apparatus |
| JP4801778B2 (en) * | 2007-10-18 | 2011-10-26 | 富士通株式会社 | Video compression / encoding device, video restoration device, video compression program, and video restoration program |
| JP5051087B2 (en) * | 2008-09-30 | 2012-10-17 | ヤマハ株式会社 | Lossless compression coding apparatus and lossless decoding apparatus |
| US8665124B2 (en) * | 2011-10-01 | 2014-03-04 | Intel Corporation | Compression format for high bandwidth dictionary compression |
| US8497788B1 (en) * | 2012-04-25 | 2013-07-30 | Pure Storage Inc. | Efficient techniques for aligned fixed-length compression |
-
2017
- 2017-01-27 WO PCT/SE2017/050074 patent/WO2017131578A1/en active Application Filing
- 2017-01-27 CN CN201780015262.7A patent/CN108702160B/en active Active
- 2017-01-30 CN CN201780015236.4A patent/CN108886367B/en active Active
- 2017-01-30 WO PCT/SE2017/050078 patent/WO2017131579A1/en active Application Filing
Patent Citations (11)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20020066007A1 (en) * | 1992-06-30 | 2002-05-30 | Wise Adrian P. | Multistandard video decoder and decompression system for processing encoded bit streams including pipeline processing and methods relating thereto |
| US20030090709A1 (en) * | 2001-11-07 | 2003-05-15 | International Business Machines Corporation | System and method for efficient compression of raster image data |
| US20030090398A1 (en) * | 2001-11-07 | 2003-05-15 | International Business Machines Corporation | System and method for efficient data compression |
| US20040178933A1 (en) * | 2003-03-11 | 2004-09-16 | Canon Kabushiki Kaisha | Encoding method and encoding apparatus, and computer program and computer readable stroage medium |
| CN1606038A (en) * | 2003-10-29 | 2005-04-13 | 威盛电子股份有限公司 | A device for compressing data in a bit pattern or bit stream |
| CN1599258A (en) * | 2004-06-25 | 2005-03-23 | 浙江大学 | Coding mode suitable for different refrared control signal |
| US20080317299A1 (en) * | 2007-06-21 | 2008-12-25 | Canon Kabushiki Kaisha | Image processing apparatus and control method thereof |
| CN103563255A (en) * | 2011-04-11 | 2014-02-05 | 马维尔国际贸易有限公司 | Method for compression and real-time decompression of executable code |
| US20130170556A1 (en) * | 2011-12-29 | 2013-07-04 | Microsoft Corporation | Variable length coding and decoding using counters |
| US9031852B2 (en) * | 2012-08-01 | 2015-05-12 | Nintendo Co., Ltd. | Data compression apparatus, computer-readable storage medium having stored therein data compression program, data compression system, data compression method, data decompression apparatus, data compression/decompression apparatus, and data structure of compressed data |
| CN105264779A (en) * | 2013-01-22 | 2016-01-20 | 阿尔特拉公司 | Data compression and decompression using simd instructions |
Non-Patent Citations (1)
| Title |
|---|
| 高海春等: "数字化语音存储与回放系统", 《华东船舶工业学院学报》 * |
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN111814009A (en) * | 2020-06-28 | 2020-10-23 | 四川长虹电器股份有限公司 | BF improved algorithm based on search engine retrieval information pattern matching |
| CN111814009B (en) * | 2020-06-28 | 2022-03-01 | 四川长虹电器股份有限公司 | Mode matching method based on search engine retrieval information |
| CN114637459A (en) * | 2020-12-16 | 2022-06-17 | 株式会社日立制作所 | device for processing received data |
| CN114637459B (en) * | 2020-12-16 | 2025-04-18 | 日立万达拉株式会社 | Device for processing received data |
Also Published As
| Publication number | Publication date |
|---|---|
| WO2017131579A1 (en) | 2017-08-03 |
| WO2017131578A1 (en) | 2017-08-03 |
| CN108886367B (en) | 2022-01-11 |
| CN108702160B (en) | 2022-05-17 |
| CN108702160A (en) | 2018-10-23 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN108886367A (en) | Method, apparatus and system for compression and decompression data | |
| US10268380B2 (en) | Methods, devices and systems for semantic-value data compression and decompression | |
| CA1223965A (en) | High speed data compression and decompression apparatus and method | |
| US10831655B2 (en) | Methods, devices and systems for compressing and decompressing data | |
| US7538696B2 (en) | System and method for Huffman decoding within a compression engine | |
| US9479194B2 (en) | Data compression apparatus and data decompression apparatus | |
| US20090060047A1 (en) | Data compression using an arbitrary-sized dictionary | |
| CN107925418A (en) | Method, apparatus and system for hybrid data compression and decompression | |
| CN109075798B (en) | Variable size symbol entropy-based data compression | |
| CN112968706B (en) | Data compression method, FPGA chip and FPGA online upgrading method | |
| CN103095305A (en) | System and method for hardware LZ77 compression implementation | |
| US6748520B1 (en) | System and method for compressing and decompressing a binary code image | |
| WO2020114283A1 (en) | Data processing method and device | |
| KR20200121760A (en) | Conditional transcoding for encoded data | |
| Anand et al. | Compression and decompression of files without loss of quality | |
| US7612692B2 (en) | Bidirectional context model for adaptive compression | |
| CN116318171B (en) | LZ4 decompression hardware acceleration realization/compression method, device, medium and chip | |
| CN111342844B (en) | LZW coding and improved run-length coding-based radar data lossless compression and decompression method | |
| JPH03209923A (en) | Data compressing system | |
| El Qawasmeh et al. | Development and investigation of a new compression technique using Boolean minimizations | |
| CN119966416A (en) | Huffman-based coding method and device, and quick decoding method and circuit | |
| Chang et al. | The block lossless data compression algorithm | |
| CN112200301A (en) | Convolution calculation device and method | |
| Twelves et al. | JPEG2000 Arithmetic Encoding on the StarCore SC140 | |
| Munasa et al. | Single Dictionary based Cache Compression and Decompression Algorithm |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |