CN100546200C - Be used for method, decoder, system and equipment from the bitstream decoding codewords of variable length - Google Patents
Be used for method, decoder, system and equipment from the bitstream decoding codewords of variable length Download PDFInfo
- Publication number
- CN100546200C CN100546200C CNB038142732A CN03814273A CN100546200C CN 100546200 C CN100546200 C CN 100546200C CN B038142732 A CNB038142732 A CN B038142732A CN 03814273 A CN03814273 A CN 03814273A CN 100546200 C CN100546200 C CN 100546200C
- Authority
- CN
- China
- Prior art keywords
- code word
- decoded
- bit stream
- length
- field
- 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.)
- Expired - Fee Related
Links
- 238000000034 method Methods 0.000 title claims abstract description 60
- 238000000605 extraction Methods 0.000 claims description 6
- 238000010295 mobile communication Methods 0.000 claims 1
- 239000000872 buffer Substances 0.000 description 39
- 230000006835 compression Effects 0.000 description 3
- 238000007906 compression Methods 0.000 description 3
- 238000009434 installation Methods 0.000 description 3
- 238000001514 detection method Methods 0.000 description 2
- 238000009825 accumulation Methods 0.000 description 1
- 230000005540 biological transmission Effects 0.000 description 1
- 230000015572 biosynthetic process Effects 0.000 description 1
- 230000003139 buffering effect Effects 0.000 description 1
- 230000001419 dependent effect Effects 0.000 description 1
- 238000010586 diagram Methods 0.000 description 1
- 230000006870 function Effects 0.000 description 1
- 230000008676 import Effects 0.000 description 1
- 239000011159 matrix material Substances 0.000 description 1
Images
Classifications
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
- H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
- H03M7/40—Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
- H03M7/42—Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code using table look-up for the coding or decoding process, e.g. using read-only memory
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Compression, Expansion, Code Conversion, And Decoders (AREA)
- Compression Or Coding Systems Of Tv Signals (AREA)
- Reduction Or Emphasis Of Bandwidth Of Signals (AREA)
Abstract
The present invention relates to a kind of being used for, in this bit stream, be code word definition minimum length and maximum length from the method for bitstream decoding codewords of variable length.In the method, portions ground is handled decoded bit stream, searching code word in each part of bit stream, and the code word of decoding discovery.In the method, by this way from the partly overlapping at least field of the bit stream extracting section of just handling, that is: the starting point of at least two fields is possible starting points of code word in the described bit stream part.In at least one field, the ending of searching code word, and according to the definite data relevant with code word of code word terminal point.Use the data relevant to find in the field generation with decoded code word with at least one code word, and the code word found of decoding.The invention still further relates to decoder, wherein use the system and the equipment of this method, and the storage device of the program of this method is used in storage.
Description
Technical field
The present invention relates to a kind of method of the codewords of variable length of from bit stream, decoding, be code word definition minimum length and maximum length in this bit stream, in the method, portions ground is handled decoded bit stream, in each part of bit stream, carry out the code word search, and the code word of decoding discovery.The invention still further relates to a kind of being used for from the decoder of bit stream decoding codewords of variable length, in this bit stream, be code word definition minimum length and maximum length, described decoder is furnished with and is used for the section processes of the length-specific device with decoded bit stream, be used for device at each part searching code word of bit stream, and the device of the code word found of being used to decode.The invention still further relates to a kind of system of transmitting the information of binary form, this system comprises an encoder and a decoder, and described decoder comprises the device that is used for from the bitstream decoding codewords of variable length, in this bit stream, be code word definition minimum length and maximum length, described decoder is furnished with and is used for the device of fixed length section processes with decoded this bit stream, be used for device at each part searching code word of bit stream, and the device of the code word found of being used to decode.And, the present invention relates to a kind of comprising from the equipment of the decoder of bitstream decoding codewords of variable length, in this bit stream, be code word definition minimum length and maximum length, described decoder is furnished with and is used for the device of fixed length section processes with decoded bit stream, be used for device at each part searching code word of bit stream, and the device of the code word found of being used to decode.At last, the present invention relates to be used for stored program memory device, described program comprises step that can be carried out by machine, the codewords of variable length of decoding from bit stream, in this bit stream, be code word definition minimum length and maximum length, described program is furnished with the computer instruction of length-specific section processes with decoded bit stream, at the computer instruction of each part searching code word of bit stream, and the computer instruction of the code word found of decoding.
Background technology
In by data network images and video data, need compressing image data, this is because by obtainable transmission rate, is very large with the data volume that is transmitted.Known compression algorithm comprises lossless compression and diminishes algorithm.Discrete cosine transform (DCT) is in conjunction with quantizing, being used for removing from view data the algorithm that diminishes of redundant information.For primary image unit (for example, 8 * 8 pixels) calculates the DCT factor, and the matrix notation of image block to form by these factors.Behind DCT, by zigzag (Zig-Zag) scanning these factors are arranged in suitable order and are used for harmless Huffman encoding.Huffman encoding only is an example of Variable Length Code (VLC), and Variable Length Code (VLC) reduces statistical redundancy at DCT with after quantizing.The principle of Variable Length Code is to represent the frequent symbol that takes place and represent infrequently symbol with long code word with short code word.In order to begin coding, arrange each symbol to come the process source data by the probability that takes place according to symbol.The symbol of probability minimum recursively is combined in the symbol, wherein forms a tree structure (example as shown in Figure 1a) so that to represent each branch be the code word of each allocation of symbols it self by defining one.From the code tree of Fig. 1 a as can be seen, the symbol of probability of happening minimum has the longest code word.Table 1b represents the probability of happening P (X) of each symbol, code word (code) and entropy H (x).Said method causes the shortest code word for mean value, and above-mentioned compression is in close proximity to the entropy of original source; Therefore, being coded in is effective generally.Thereby Variable Length Code is the element an of necessity in many standards that relate to image processing.
Point out that as the definition of Variable Length Code the code word of Variable Length Code changes on length.If can not directly detect the starting point and the terminal point of code word from bit stream, between code word, can produce the recurrence dependence, this can make decoding more difficult.This dependence will make must find code word from bit stream in that variable-length decoding (VLD) is preceding, that is to say the position that must determine code word.Therefore, in decode procedure, determine that code length and position, code word and corresponding symbol are necessary.
Bit stream processing according to following mode can characterize the VLD realization.In the serial process on the throne, one one processing bit stream continuously.Therefore, the whole bit stream that enters is to handle with constant input rate.Because code word has variable-length, whole decodings of code word also spend the variable time, and this will cause variable output speed.
In the parallel processing on the throne, enter a plurality of positions of bit stream with constant input rate or variable input rate parallel processing.When input rate kept constant, it is variable that output speed remains, and this is because the variable-length of code word causes.For obtaining constant output speed, need to handle changeably to enter bit stream.In other words, for guaranteeing constant output speed, input must comprise a plurality of positions corresponding to required output speed and the longest codeword length product.
To be similar to the mode of the feature of handling according to bit stream, the concurrency of decoder also can be described with a plurality of code words that will be decoded simultaneously (or from exporting the symbol that obtains).When once a code word being carried out decoding, decoding can be characterized into symbol string.Therefore, when decoded result is when once obtaining a plurality of symbol, the decoding is-symbol is parallel.
Decoding can be by realizing based on the algorithm of tree, and this algorithm is the realization with the Huffman tree inverted configuration: will encode enter bit stream and binary tree compares, from root, and carry out up to having determined whole code word from each leaf unit always.In the decoding of tree-model, have only with the short code word to obtain effectively decoding.Yet, need also should obtain corresponding output speed to long code word to the high request of real-time processing.And because the Bits Serial form of tree-model so tree-model is not suitable for several symbols of decoding simultaneously, that is, is not suitable for the parallel processing of symbol, this is because of the dependence between the code word when handling single bit stream.
In order to improve disposal ability, improve concurrency by the parallel processing multidigit, this is to realize by collect enough data volumes (maximum code word length) in input buffer, begins to detect and decode code word from buffer.In the symbol serial decode, find a symbol for guaranteeing each circulation, the data volume of the corresponding maximum code length of accumulation in input buffer.The problem here is that a plurality of positions are left on the end of buffer, and they can not be utilized in current circulation.Symbol parallel decoding (or many symbol decodings) relates to the problem and the challenge of design aspect: device or system will become very complicated very soon.
Hsieh﹠amp; Al is at C.T.Hsieh and S.P.Kim " A concurrent memory-efficient VLCdecoder for MPEG applications " IEEE Trans Consumer Electron., 42 volumes the 3rd phase 439-446 page or leaf is given in while parallel decoding short code word (parallel decoding algorithm) in the same circulation in 1996 8 months.Decoder uses the probability distribution of Variable Length Code, and according to this probability distribution, the bit sequence that enters bit stream has big probability to comprise the code word shorter than long code word.For example, under the poorest situation, one 16 enter data sequence and can comprise 82 code words, 8 decode cycle of decoding needs of next symbol of these code words.The target of disclosed decoding algorithm is by detecting 2 or manyly quicken decode procedure than the short code word simultaneously in publication; In other words, use this method to come the combination of detected codeword.For example, in decoding two-stage code word, the first order of tree-model is corresponding to decoded first generation code word, and the second level is corresponding to decoded second generation code word.Therefore, target is two code words of decoding simultaneously.The length of first generation code word may change between 2 to k positions.If the length of first generation code word is 2, may be 2 to k by the length of the second generation code word of parallel decoding so
2The position.On the other hand, if the length of first generation code word is 3, the length of the second generation code word that may be decoded simultaneously is 2 to k so
3Position or the like.Because the first order comprises all codes, so k equals the maximum length of code book, the length of corresponding the longest code word.In the second level, (possibility) code preferably short according to the base attribute of VLC.Therefore, k
iValue at scope 0≤k
iIn≤the k.
Basic process in the two-stage decoding process starts from the root of tree-model.Contrast every grade and go up all possible code word, haply the bit sequence of each branch in the while testing tree.If on the second level of tree, find more than one suitable branch, will select so from the continuous always path of root, just, bit stream is not have interruption continuously.If next stage does not have branch to provide continuous path from root, then decode procedure can finish in the first order.This means the second level code word of to decode.Use is controlled the next data of inlet flow from the codeword length of every grade of acquisition, and wherein decode procedure will begin once more.Also coding/decoding method that can be identical to more multistage use.Code word detection piece according to maximum possible bit pattern (MLBP) returns 3 factors to finish decode cycle: determines group echo remaining in the group, shifts the length that bit stream begins to next code word, and the group code that is used for memory.Retrieve this symbol according to remaining and group from random access memory.
Summary of the invention
The objective of the invention is by in the first step of decode procedure, removing the dependence between code word, and make may be concurrently and channelization ground decode, in the first step of decode procedure, locate this code word.In the method according to the invention, from input buffer, extract the bit field of fixed length, to find all possible code word.Roughly detect all possible code word by cascade structure simultaneously from buffer.In other words, from the bit stream that enters buffer, from each possible buffer positions detected codeword lengths.Yet this will cause also detecting invalid code word from input buffer.In the method according to the invention, the mode of the selection by using first detector (first code word length) control, second output is selected effective codeword length according to codeword length the preceding.Successively, select third generation code word size or the like according to codeword length sum the preceding.In selecting the actual code word, use multiplexer to select effective codeword length from several codeword length (all possible codeword locations acquisition from buffer of these length).For example, can use elementary logic circuit (with/or door and inverter) realize above-mentioned multiplexer.In the method according to the invention, multiplexer links by this way, and they provide the direct output of the length of all complete code words in the buffer as them.About part and and the data of institute's detected codeword lengths sum also can obtain to use after a while.A preferred embodiment of the present invention is characterised in that the structure of implementing cascade, and it makes by MultiplexedAdd (the multiplexing addition of MA) equipment, and critical path is shorter to become longer.In the method for the invention, all complete code words that occur in can detection buffer; Therefore, can executed in parallel to the actual search of symbol, to quicken decoding under the dependent situation without limits.
In view of the above, according to a kind of method provided by the present invention from the bitstream decoding codewords of variable length, in this bit stream, be code word definition minimum length and maximum length, portions ground is handled decoded bit stream in the method, each part of bit stream is carried out the search of code word, and the code word of decoding discovery, in the method
From the partly overlapping at least field of the size that processed bit stream extracting section is not more than the code word maximum length, make that the starting point of at least two fields is possible starting points of code word in the described bit stream part by this way,
From at least one field searching code word ending terminal point,
Determine the data relevant according to the code word terminal point with code word, and
Use the data relevant to determine in the field generation with decoded code word with at least one code word, and
The code word that decoding is found.
The present invention also provides a kind of decoder that has the code word of variable-length from bitstream decoding, in this bit stream, be code word definition minimum length and maximum length, described decoder is furnished with: be used for the section processes of each fixed length the hair of decoded bit stream being managed device, be used for searcher at each part searching code word of bit stream, and, described decoder is configured to be used to the code word of decoding and finding, wherein:
Decoder also comprises extraction element, is used for being not more than from the bit stream extracting section of just handling the partly overlapping at least field of the size of code word maximum length, thereby the starting point of at least two fields is possible starting points of code word in the described bit stream part;
Wherein searcher is configured in searching code word terminal point at least one field; With
Wherein decoder comprises the first definite device that is used for determining according to the code word terminal point data relevant with the code word of finding in this field; And
Be used for the basis data relevant, determine in this field device is determined in second of the generation of decoded code word with at least one code word.
The invention still further relates to a kind of system of transmitting the information of binary form, comprise an encoder and a decoder, described decoder is configured to be used for from the bitstream decoding codewords of variable length, in this bit stream, be code word definition minimum length and maximum length, described decoder is furnished with: be used for the section processes of each fixed length processing unit with decoded bit stream, be used for searcher at each part searching code word of bit stream, and described decoder is configured to be used to the code word of decoding and finding, wherein:
Decoder also comprises extraction element, is used for being not more than from the bit stream extracting section of just handling the partly overlapping at least field of the size of code word maximum length, thereby the starting point of at least two fields is possible starting points of code word in the described bit stream part;
Wherein searcher is configured in searching code word terminal point at least one field; With
Decoder comprises the first definite device that is used for determining according to the code word terminal point data relevant with the code word of finding in this field; And
Be used for the basis data relevant and determine the second definite device of this field the generation of decoded code word with at least one code word.
The present invention also provides a kind of and comprises from the equipment of the decoder of bitstream decoding codewords of variable length, in this bit stream, be code word definition minimum length and maximum length, described decoder is furnished with: be used for the section processes of each fixed length processing unit with decoded bit stream, and be used for searcher at each part searching code word of bit stream, and decoder is configured to be used to the code word of decoding and being found, wherein
Decoder also comprises extraction element, is used for being not more than from the bit stream extracting section of just handling the partly overlapping at least field of the size of code word maximum length, thereby the starting point of at least two fields is possible starting points of code word in the described bit stream part;
Wherein searcher is configured in searching code word terminal point at least one field; And
Decoder comprises the first definite device that is used for determining according to terminal point the data relevant with the code word of finding in this field; And
Be used for the basis data relevant and determine the second definite device of this field the generation of decoded code word with at least one code word.
For making it more accurate, principal characteristic features of the method according to the invention is, in the method, from isolating partly overlapping at least field the processed part bit stream by this way, make that the starting point of at least two fields is possible starting points of code word in the described bit stream part, from at least one field searching code word ending, and according to the definite data relevant of the terminal point of this code word with code word, and use the data relevant to determine in this field generation, and the code word found of decoding with decoded code word with at least one code word.Principal character according to decoder of the present invention is that described decoder also comprises: from the device of the partly overlapping at least field of bit stream extracting section just handled, make that the starting point of at least two fields is possible starting points of code word in the described bit stream part; The device of searching code word ending at least one field; With the device (CD) of determining the data relevant according to this ending with the code word found in this field; And according to the data relevant with at least one code word, determine in the field with the device of the generation of decoded code word (MUX1, MUX, M, MA).Principal character according to system of the present invention is, decoder also comprises: be used for by this way from the device of the partly overlapping at least field of just handling of bit stream extracting section, make that the starting point of at least two fields is possible starting points of code word in the described bit stream part; Be used for device at least one field searching code word ending; With the device that is used for determining the data relevant with the code word of finding in this field according to terminal point; And be used for the basis data relevant and determine the device of this field the generation of decoded code word with at least one code word.Principal character according to equipment of the present invention is, decoder also comprises: be used for by this way from the device of the partly overlapping at least field of just handling of bit stream extracting section, make that the starting point of at least two fields is possible starting points of code word in the described bit stream part; Be used for device at least one field searching code word ending; With the device that is used for determining the data relevant with the code word of finding in this field according to terminal point; And be used for the basis data relevant and determine the device of this field the generation of decoded code word with at least one code word.At last, principal character according to storage device of the present invention is, program comprises: by this way from the computer instruction of the partly overlapping field of bit stream extracting section just handled, make that the starting point of at least two fields is possible starting points of code word in the described bit stream part; The computer instruction of searching code word ending at least one field; With determine that according to terminal point the data computing machine relevant with the code word of finding instructs in this field; And determine in this field computer instruction with the generation of decoded code word according to the data relevant with at least one code word.
The present invention has improved the prior art of decoding code word by the mode of parallel-by-bit, symbol parallel, and this mode also is suitable for the decoding of parallel long code word.Therefore, the present invention can use long input buffer (buffer of any length).And this method is divided into the stage with decoding so that make this enforcement pipelining.The possible code word of all location findings of the input buffer that may be positioned in code word.Valid code word detects by index, and above-mentioned index is to obtain by the length sum of calculating in preceding suitable code word.Because the data about restriction (starting point and terminal point) find relatively with finding code word, so be independent of decode this code word and to improve concurrency be possible of other code words.Being in proportion of output stage of the method according to this invention and input buffer.
Description of drawings
Below, with more detailed description the present invention with reference to the accompanying drawings, wherein
Fig. 1 a represents the tree structure by Huffman encoding formation,
Fig. 1 b represents the probability of Huffman code word and corresponding symbol and generation with the form of form,
Fig. 2 represents to find the principle of VLC code word according to preferred embodiment from bit stream,
Fig. 3 finds the system of VLC code word according to the preferred embodiment of invention from bit stream with the graphical presentation simplified,
Fig. 4 a represents the MultiplexedAdd device in the chart,
Fig. 4 b represents the internal structure of MultiplexedAdd, and
Fig. 5 from bit stream finds the system of VLC code word according to another preferred embodiment of invention by using MultiplexedAdd with the graphical presentation of simplifying.
Embodiment
Let us at first is defined in the buffer once can occur for how many codewords of variable length.For this reason, the code length of code table is by group S
L={ l
1..., l
nDefinition, wherein l
1And l
nMinimum length and the maximum length of representing code word respectively.Therefore, in a N digit buffer, the maximum length of code word is
N 〉=l
nLet us points out to have the codewords of variable length of symbol Wi, i=0 wherein, and 1 ..., (K
Max-1) and have a symbol L
iCode word W
iLength.Simultaneously, let us index of definition j
1, 0≤j
i≤ (N-1), be illustrated in code word W in the code word buffer of N position
iFirst.
Generally speaking, can suppose first code word W
0Always be positioned at the beginning of buffer, wherein W
0Starting point be j
0=0.Second code word W
1Be sitting at after first code word, wherein define the index j of the starting point of second code word
1Be the length of first code word, just, j
1=L
0This means code word W
iStarting point be length sum in preceding code word, just,
Codeword length is not to be in advance known in the buffer.For avoiding the dependence of recurrence, also need be in buffer optional position parallel search code word.Generally speaking, all possible positions of any code word can be by p={l
1, l+1, l+2 ..., N-l
1Definition, this means N-2 (l in the N digit buffer
1-1) individual position.Because the maximum length l of code word
nBe known, will be not more than maximum length l
nThe field of size is separated from all possible positions of p definition, by using for example pattern matching, code table attribute, searches for possible codeword length such as guiding character, maximum possible bit pattern (MLBP) or number attribute in each above-mentioned field.Yet, have only all positions of definition code word can obtain to finish decoding, promptly find symbol, could find symbol.Reason for this reason is with last l
nDetected codeword is to be relatively easy in the field that-1 index begins; Only need from the bit field search K position code word that begins with starting point N-K, wherein K＜l
n
In said process, detect the redundant code word, this is because if isolate bit field from the centre of effective longer code word, then may find shorter code word in this code word.Reason for this reason, each search procedure is only returned the length of institute's detected codeword.The index of valid code word can be defined by length on recursiveness ground in the buffer; The starting point of first code word length definition second generation code word; The starting point of the length definition third generation code word of first and second code words, or the like.
Fig. 2 represents the method by according to a preferred embodiment of the present invention, finds the example of code word in 16 digit buffers.Let us is supposed wherein length by group S={2,3,4,5,6,7, and the maximum length of code word is K in 8} definition and 16 input buffers
Max=8 code table.According to said method, from buffer, distinguish 14 field F0-F13, in each field, attempt finding possible code word.What determine is that the first field F0 comprises the first suitable code word W0.Find second generation code word W1 for one in field F1-F7.In the corresponding way, can in one of field F3-F13, find possible third generation code word W 2.Can in field F5-F13, find possible other code words W3-W7.Bit field length in field F8-F13 is shorter than the length in other fields, and this is because be contained in the code word of buffer end than maximum length l
nLack.
In order to finish decode procedure, retrieve the symbol of corresponding code word from code table.Because can find the starting point and the terminal point of code word, so eliminated the dependence between the code word by said method.In other words, can isolate code word, and can carry out search independently from inlet flow.
Generally, the pattern of description can followingly be represented:
Determine the maximum quantity K of code word in the code word buffer of N position
Max,
(N-2 (the l that separates necessary size from buffer
1-1)) individual field F0-F (N-2 (l
1-1)-1) to determine codeword length.The starting point of each field be buffer positions 0, l
1, l
1+ 1, l
1+ 2 ..., N-l
1,
Begin to locate to find possible code word in each field.Return the length of the code word of finding,
In the length of first field discovery first generation code word, find other effective code words by index at buffer, this index obtains by the length sum of calculating at preceding appropriate codes word,
According to the symbol of code table discovery corresponding to suitable code word.
Because input rank and output rank are variable in said method, so will need buffering in input and output.Fig. 3 represents to realize the decoder of said process, has considered all code words that detect simultaneously in the input buffer in the design of decoder.In order to realize this purpose, use N-2 (l
1-1) individual code word detector C D.First generation code word detector C D1 (left side is one among Fig. 3) uses the field that begins from the input buffer beginning with detected codeword.Second generation code word detector C D2 uses the some l from input buffer
1The field of beginning is with detected codeword.In order according to this figure, the N-l on the left side
n-l
1+ 2 code word detectors use the field (maximum length code word) that begins from the input buffer difference, and other l
n-l
1Individual code word detector only need detect the code word shorter than maximum length.All code word detector C D1-CD (N-2 (l
1-1)) detected codeword and return the length of the code word of finding simultaneously haply.Select suitable codeword length Li for the code word from all discoveries, use multiplexer MUX, it forms a cascade structure.Each multiplexer MUX has the input from each code word detector C D, and the position of detector is by group p definition.The bit field of code word detector C D is at the position of input buffer il
1-il
nIn.Because first code length L
0Always obtain, go to select the second appropriate codes length L so it will control the first multiplexer MUX1 from first generation code word detector C D1
1This also can be used to change the information about decoding schema.In other words, if code length is 0, then or stop decoding or have been found that mistake.By controlling other multiplexers in preceding code length sum.By this way, the calculating of code length sum produces a critical path, and this path is illustrated by the broken lines in Fig. 3.
Code word can be separated from input buffer and independent decoding according to length data.And, when removing the dependence of code word, can walk abreast and decode.
In the system of another preferred embodiment according to the present invention, use MultiplexedAdd MA, its schematic diagram is shown in Fig. 4 a, and cut-away view is shown in Fig. 4 b.Can use this scheme to reduce the critical path that in determining code word, produces.Shown in Fig. 4 a, MultiplexedAdd MA calculates two input sums and also carries out multiplexingly haply simultaneously, and Fig. 4 b represents the internal structure of 3 MultiplexedAdd.An X position MultiplexedAdd comprises X full adder FA and the multiplexing tree structure of X rank, and this structure receives full adder sum and imports as it, as select signal and alternative objects (probability, P).Exemplary system as shown in the figure is two 3 bit digital A and B, they with selection (the corresponding codeword length L that from probability P select of S control from the output O of probability P 0-P7
i), in the method according to the invention, these probability representatives are from the position p of input buffer
iThe all possible codeword length of those code words of beginning.Therefore, realize that the formula of exporting can be defined as follows:
O＝P
0s
2s
1s
0+P
1s
2s
1s
0+P
2s
2s
1s
0+P
3s
2s
1s
0+
P
4s
2s
1s
0+P
5s
2s
1s
0+P
6s
2s
1s
0+P
7s
2s
1s
0，
This formula can further be simplified to following form:
O＝(P
0s
1s
0+P
1s
1s
0+P
2s
1s
0+P
3s
1s
0)s
2+(P
4s
1s
0+P
5s
1s
0+P
6s
1s
0+P
7s
1s
0)s
2
＝[(P
0s
0+P
1s
0)s
1+(P
2s
0+P
3s
0)s
1]s
2+[(P
4s
0+P
5s
0)s
1+(P
6s
0+P
7s
0)s
1]s
2
By MultiplexedAdd MA, calculate the current code length L
iWith at preceding code length sum ∑
K=0 I-1L
kAnd select code length L of future generation
I+1Be possible.By using MultiplexedAdd MA, the delay between two code lengths is reduced to the delay of log (N) full adder and 2-1 multiplexer by the delay of log (N) position adder and multiplexer group.With corresponding form, by use 3-4 with or door and 2-2 with or and inverter, and logic level is reduced to log (N)+1 grade by 2log (N) grade.Fig. 5 represents according to second preferred embodiment of the present invention, finds the system of code word by MultiplexedAdd MA.
Variable Length Code decoder according to the present invention can be used as the part realization of electronic installation, for example, as independent logical circuit, by the application-specific integrated circuit (ASIC) in digital signal processor (ASIC), or the functional unit in the processor.Typically, above-mentioned electronic installation also comprises other functions, for example shows the device of decoded information and the processor of control electronic installation to the user.
It is apparent that the present invention and not only be confined to the foregoing description, but correct within the scope of the appended claims.
Claims (13)
1. method from the bitstream decoding codewords of variable length, in this bit stream, be code word definition minimum length and maximum length, portions ground is handled decoded bit stream in the method, each part of bit stream is carried out the search of code word, and the code word of decoding discovery, it is characterized in that, in the method
From the partly overlapping at least field of the size that processed bit stream extracting section is not more than the code word maximum length, make that the starting point of at least two fields is possible starting points of code word in the described bit stream part,
From at least one field searching code word terminal point,
Determine the data relevant according to the code word terminal point with code word, and
Use the data relevant to determine in the field generation with decoded code word with at least one code word, and
The code word that decoding is found.
2. the method for claim 1 is characterised in that with the data that decoded code word is relevant to comprise length with decoded code word, and wherein search is carried out decoded code word as follows:
In first field, search for decoded first generation code word,
In the bit stream just handled part, be in corresponding the field that will be decoded in its starting point at the point of preceding codeword length sum, search for decoded code word of future generation,
Carry out above-mentioned steps in the bit stream part of just handling, to find that all are with decoded code word.
3. method as claimed in claim 2 is characterised in that in the method, in order to find the starting point with decoded code word of future generation, calculates the decoded codeword length sum in preceding discovery is also selected this starting point basically simultaneously.
4. method as claimed in claim 3, be characterised in that and partly finding the step of code word from the bit stream of just handling, the summation position and the probability of all possible codeword length of the code word that reception begins from the possible position of code word are so that determine selection corresponding to the output of codeword length.
5. as any described method of claim 1 to 4, be characterised in that at least first, the code word of second and the 3rd discovery is decoded.
6. decoder that has the code word of variable-length from bitstream decoding, in this bit stream, be code word definition minimum length and maximum length, described decoder is furnished with: be used for the section processes of each fixed length processing unit with decoded bit stream, be used for searcher at each part searching code word of bit stream, and, described decoder is configured to be used to the code word of decoding and finding, is characterised in that:
Decoder also comprises extraction element, is used for being not more than from the bit stream extracting section of just handling the partly overlapping at least field of the size of code word maximum length, thereby the starting point of at least two fields is possible starting points of code word in the described bit stream part;
Wherein searcher is configured in searching code word terminal point at least one field; With
Wherein decoder comprises the first definite device that is used for determining according to the code word terminal point data relevant with the code word of finding in this field; And
Be used for the basis data relevant, determine in this field device is determined in second of the generation of decoded code word with at least one code word.
7. decoder as claimed in claim 6 is characterised in that with the data that decoded code word is relevant to comprise length with decoded code word, and,
Searcher is configured in the search of first field with decoded first generation code word, and
Be used for searching for this field with decoded code word of future generation, wherein said searcher further is arranged in order to being formed on the length data of the code word of finding in the field,
Wherein decoder comprises that being used in starting point is that choice device with decoded code word is partly selected from the bit stream of just handling in decoded position in preceding codeword length sum.
8. system of transmitting the information of binary form, comprise an encoder and a decoder, described decoder is configured to be used for from the bitstream decoding codewords of variable length, in this bit stream, be code word definition minimum length and maximum length, described decoder is furnished with: be used for the section processes of each fixed length processing unit with decoded bit stream, be used for searcher at each part searching code word of bit stream, and described decoder is configured to be used to the code word of decoding and finding, is characterised in that:
Decoder also comprises extraction element, is used for being not more than from the bit stream extracting section of just handling the partly overlapping at least field of the size of code word maximum length, thereby the starting point of at least two fields is possible starting points of code word in the described bit stream part;
Wherein searcher is configured in searching code word terminal point at least one field; With
Decoder comprises the first definite device that is used for determining according to the code word terminal point data relevant with the code word of finding in this field; And
Be used for the basis data relevant and determine the second definite device of this field the generation of decoded code word with at least one code word.
9. system as claimed in claim 8 is characterised in that with the data that decoded code word is relevant to comprise length with decoded code word, and,
Searcher is configured in the search of first field with decoded first generation code word, and
Be used in the search of this field decoded next code word, wherein said searcher further is arranged in order to being formed on the length data of the code word of finding in this field,
Wherein decoder comprises choice device, and being used in starting point is that the position of decoded length sum in preceding code word is partly selected decoded code word from the bit stream of just handling.
10. one kind comprises from the equipment of the decoder of bitstream decoding codewords of variable length, in this bit stream, be code word definition minimum length and maximum length, described decoder is furnished with: be used for the section processes of each fixed length processing unit with decoded bit stream, and be used for searcher at each part searching code word of bit stream, and decoder is configured to be used to the code word of decoding and being found, be characterised in that
Decoder also comprises extraction element, is used for being not more than from the bit stream extracting section of just handling the partly overlapping at least field of the size of code word maximum length, thereby the starting point of at least two fields is possible starting points of code word in the described bit stream part;
Wherein searcher is configured in searching code word terminal point at least one field; And
Decoder comprises the first definite device that is used for determining according to terminal point the data relevant with the code word of finding in this field; And
Be used for the basis data relevant and determine the second definite device of this field the generation of decoded code word with at least one code word.
11. equipment as claimed in claim 10 is characterised in that with the data that decoded code word is relevant to comprise length with decoded code word, and,
Searcher is configured in first field and searches for decoded first generation code word, and
Be used in the search of this field decoded code word of future generation, wherein said searcher further is arranged in order to being formed on the length data of the code word of finding in this field,
Wherein decoder comprises that being used in starting point is that choice device with decoded code word is partly selected from the bit stream of just handling in the position of decoded length sum in preceding code word.
12., be characterised in that this decoder comprises the summing unit with decoded codeword length summation, to find that the starting point of decoded code word is also selected this starting point basically simultaneously as claim 10 or 11 described equipment.
13., be characterised in that this equipment is configured to be used to carry out mobile communication as claim 10 or 11 described equipment.
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| FI20021221 | 2002-06-20 | ||
| FI20021221A FI116813B (en) | 2002-06-20 | 2002-06-20 | A method and system for decoding variable length coding, and a code word locator |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN1663128A CN1663128A (en) | 2005-08-31 |
| CN100546200C true CN100546200C (en) | 2009-09-30 |
Family
ID=8564212
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CNB038142732A Expired - Fee Related CN100546200C (en) | 2002-06-20 | 2003-06-16 | Be used for method, decoder, system and equipment from the bitstream decoding codewords of variable length |
Country Status (9)
| Country | Link |
|---|---|
| US (1) | US6980138B2 (en) |
| EP (1) | EP1514356B1 (en) |
| KR (1) | KR20050010918A (en) |
| CN (1) | CN100546200C (en) |
| AT (1) | ATE363769T1 (en) |
| AU (1) | AU2003240915A1 (en) |
| DE (1) | DE60314139T2 (en) |
| FI (1) | FI116813B (en) |
| WO (1) | WO2004001978A1 (en) |
Families Citing this family (9)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN100440979C (en) * | 2005-12-15 | 2008-12-03 | 清华大学 | Self-adaptive two-dimensional variable length decoding method and device based on context |
| CN100466743C (en) * | 2006-08-07 | 2009-03-04 | 清华大学 | Method for programmable entropy decoding based on shared storage and countra-quantization |
| JP4841496B2 (en) * | 2007-04-26 | 2011-12-21 | パナソニック株式会社 | Variable length code decoding apparatus |
| JP4763853B2 (en) * | 2008-03-31 | 2011-08-31 | パナソニック株式会社 | Variable length code decoding apparatus and method |
| US8660261B2 (en) * | 2009-06-04 | 2014-02-25 | Mediatek Singapore Pte. Ltd. | System and apparatus for integrated video/image encoding/decoding and encryption/decryption |
| WO2012099433A2 (en) * | 2011-01-20 | 2012-07-26 | 한국전자통신연구원 | Entropy coding method using an index mapping table, and image-encoding/decoding apparatus and method using said entropy coding method |
| KR20120084639A (en) | 2011-01-20 | 2012-07-30 | 한국전자통신연구원 | Adaptive sorting table for entropy coding |
| US9819359B1 (en) | 2016-12-11 | 2017-11-14 | Microsoft Technology Licensing, Llc | Multi-symbol, multi-format, parallel symbol decoder for hardware decompression engines |
| US11211945B1 (en) * | 2020-10-29 | 2021-12-28 | Microsoft Technology Licensing, Llc | Parallelized decoding of variable-length prefix codes |
Family Cites Families (14)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5280349A (en) * | 1992-02-13 | 1994-01-18 | Industrial Technology Research Institute | HDTV decoder |
| US5245338A (en) * | 1992-06-04 | 1993-09-14 | Bell Communications Research, Inc. | High-speed variable-length decoder |
| KR940010433B1 (en) * | 1992-06-09 | 1994-10-22 | 대우전자 주식회사 | Apparatus for decoding variable length code |
| US5821885A (en) * | 1994-07-29 | 1998-10-13 | Discovision Associates | Video decompression |
| US5488366A (en) * | 1993-10-12 | 1996-01-30 | Industrial Technology Research Institute | Segmented variable length decoding apparatus for sequentially decoding single code-word within a fixed number of decoding cycles |
| KR0124191B1 (en) | 1994-01-18 | 1998-10-01 | 배순훈 | Vld |
| JP2746109B2 (en) * | 1994-03-09 | 1998-04-28 | 日本電気株式会社 | Huffman code decoding circuit |
| US5491480A (en) * | 1994-05-25 | 1996-02-13 | Industrial Technology Research Institute | Variable length decoder using serial and parallel processing |
| KR0141298B1 (en) * | 1994-11-17 | 1998-06-15 | 배순훈 | Variable length decoding apparatus |
| US5835035A (en) * | 1995-12-28 | 1998-11-10 | Philips Electronics North America Corporation | High performance variable length decoder with two-word bit stream segmentation and related method |
| KR100214593B1 (en) * | 1996-03-15 | 1999-08-02 | 구자홍 | Run-length code word detecting method and apparatus using cascade structure |
| EP1162847B1 (en) * | 2000-04-28 | 2003-07-02 | Matsushita Electric Industrial Co., Ltd. | Variable length decoder |
| US6542095B1 (en) * | 2001-12-14 | 2003-04-01 | Taiwan University | Universal variable length code (UVLC) encoder |
| US6573846B1 (en) * | 2001-12-31 | 2003-06-03 | Apple Computer, Inc. | Method and apparatus for variable length decoding and encoding of video streams |
-
2002
- 2002-06-20 FI FI20021221A patent/FI116813B/en not_active IP Right Cessation
-
2003
- 2003-06-16 WO PCT/FI2003/000480 patent/WO2004001978A1/en active IP Right Grant
- 2003-06-16 KR KR10-2004-7020323A patent/KR20050010918A/en not_active Application Discontinuation
- 2003-06-16 DE DE60314139T patent/DE60314139T2/en not_active Expired - Lifetime
- 2003-06-16 AU AU2003240915A patent/AU2003240915A1/en not_active Abandoned
- 2003-06-16 CN CNB038142732A patent/CN100546200C/en not_active Expired - Fee Related
- 2003-06-16 AT AT03730281T patent/ATE363769T1/en not_active IP Right Cessation
- 2003-06-16 EP EP03730281A patent/EP1514356B1/en not_active Expired - Lifetime
- 2003-06-18 US US10/465,033 patent/US6980138B2/en not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| CN1663128A (en) | 2005-08-31 |
| US6980138B2 (en) | 2005-12-27 |
| FI116813B (en) | 2006-02-28 |
| AU2003240915A1 (en) | 2004-01-06 |
| US20040070525A1 (en) | 2004-04-15 |
| WO2004001978A1 (en) | 2003-12-31 |
| FI20021221A0 (en) | 2002-06-20 |
| FI20021221A (en) | 2003-12-21 |
| KR20050010918A (en) | 2005-01-28 |
| EP1514356B1 (en) | 2007-05-30 |
| DE60314139T2 (en) | 2008-01-24 |
| ATE363769T1 (en) | 2007-06-15 |
| DE60314139D1 (en) | 2007-07-12 |
| EP1514356A1 (en) | 2005-03-16 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| EP0951753B1 (en) | Computer sorting system for data compression | |
| US7378992B2 (en) | Content independent data compression method and system | |
| US6982661B2 (en) | Method of performing huffman decoding | |
| CN102098508B (en) | The coding of multimedia signature and decoding | |
| CN109716658B (en) | Method and system for deleting repeated data based on similarity | |
| JP4805364B2 (en) | Improved digital signal encoding / decoding with permutation codes, especially in vector quantization. | |
| KR20040041651A (en) | Huffman coding | |
| JP2003218703A (en) | Data coder and data decoder | |
| US5857036A (en) | System and method for the fractal encoding of datastreams | |
| US7652596B1 (en) | Variable-length compression technique for encoding or decoding a sequence of integers | |
| CN100546200C (en) | Be used for method, decoder, system and equipment from the bitstream decoding codewords of variable length | |
| US7609000B1 (en) | Variable-length compression technique for encoding or decoding a sequence of integers | |
| CN1426629A (en) | Method and apparatus for optimized lossless compression using plurality of coders | |
| US6130631A (en) | Method and apparatus utilizing a simplified content-addressable memory for JPEG decoding | |
| US6778107B2 (en) | Method and apparatus for huffman decoding technique | |
| KR20030016859A (en) | The decoding method of Huffman code | |
| Yokoo | Data compression using a sort-based context similarity measure | |
| Doshi et al. | Achieving Better Compression Applying Index-based Byte-Pair Transformation before Arithmetic Coding | |
| KR100451256B1 (en) | MPEG-4 Reversible Variable Length Code Decoding Method and Circuit | |
| Park et al. | High speed search and an area efficient Huffman decoder | |
| GB2360916A (en) | Compression encoder which transmits difference between new data word and recent data word where this falls within a threshold | |
| GB2360917A (en) | Run length compression encoding of runs of similar data words | |
| Jiang et al. | Lossless compression of images by a search order based entropy coding | |
| KR20050037307A (en) | Huffman decoding method based on n-tree searching and apparatus thereof | |
| GB2402584A (en) | Method of performing Huffman decoding |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| C14 | Grant of patent or utility model | ||
| GR01 | Patent grant | ||
| ASS | Succession or assignment of patent right |
Owner name: SISVEL INTERNATIONAL S.A. Free format text: FORMER OWNER: NOKIA CORPORATION Effective date: 20121011 |
|
| C41 | Transfer of patent application or patent right or utility model | ||
| C56 | Change in the name or address of the patentee |
Owner name: NOKIA CORPORATION Free format text: FORMER NAME: NOKIA LTD. |
|
| CP01 | Change in the name or title of a patent holder |
Address after: Espoo, Finland Patentee after: NOKIA Corp. Address before: Espoo, Finland Patentee before: NOKIA Corp. |
|
| TR01 | Transfer of patent right |
Effective date of registration: 20121011 Address after: Luxemburg Luxemburg Patentee after: Sisvel International S.A. Address before: Espoo, Finland Patentee before: NOKIA Corp. |
|
| CF01 | Termination of patent right due to non-payment of annual fee |
Granted publication date: 20090930 Termination date: 20200616 |
|
| CF01 | Termination of patent right due to non-payment of annual fee |