JP3230933B2 - Data decompression device, data decompression method, decoding device, decoding method, encoding device, and entropy decoder - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

FIELD OF THE INVENTION The present invention relates to the field of data compression / decompression devices, and more particularly to a method and apparatus for parallel encoding and decoding of data in a compression / decompression device.

[0002]

BACKGROUND OF THE INVENTION Data compression is a very useful tool for storing and transmitting large amounts of data. For example, by using compression to reduce the number of bits required for image reproduction, the time required for image transmission, such as facsimile transmission of a document, is dramatically reduced.

Conventionally, there are a variety of data compression techniques. Compression techniques are broadly classified into lossy coding and lossless coding. Lossy coding does not guarantee complete reproduction of the original image because the coding loses information. The goal of lossy coding is to make changes to the original image unimportant,
Or, to the extent that it is not noticed. In lossless compression, all information is preserved and the data is compressed so that it can be completely restored.

[0004] For lossless compression, input symbols are converted to output codewords. If compression is successful, the codeword is represented with fewer bits than the input symbol. Lossless coding methods include dictionary coding methods (eg Lenpel-Ziv), run-length coding, counting
(enumerative) coding, and entropy coding. See H. Meyr, H. G. Roskolsky, and T. S. H. for details on run-length coding.
uang, "Optimum Run Length Codes", IEEE T
ransactions on Communications, Vol. COM-2
2, No. 6, June 1974, pp. 826-835],
[G. G. FIG. Langdon, Jr., "An Adaptive Run-Len
gth Coding Algorithm ", IBM Technical Disclosure
sure Bulletin, Vol.26, No.7B, December 1
983, pp.3783-3785] (The coding method using the R2 (k) code having a dynamically changing k value is as follows.
Langdon), "SW Golomb," Run-Length
Encoding, "IEEE Trans., IT-12, (July
1966), pp. 399]. For more information on run-length codes and their use in connection with facsimile transmission, see "M. Takagi and T.S. Tsuda, "
A Highly Efficient Run-Length Coding Scheme
For Facsimile Transaction "Electronics and C
ommunications in Japan, Vol. 58-A, No. 2, 1
9752 pp. 30-38]. 1982
U.S. Pat. No. 4,325,085, issued on Apr. 13, 2014,
hod and Apparatus for Adaptive Facsimile Compr
ession Usinga Two Dimensional Maximum Likelyh
See also ood Predictor (RP Gooch).

[0005] Entropy coding uses some lossless (and thus fully reproducible) coding technique to attempt to compress data to near the entropy limit using known or estimated symbol probabilities. . Entropy codes include Huffman codes, arithmetic codes, and binary entropy codes.
Code included. Huffman coding uses a fixed length-variable length code that generates an integer number of bits for each symbol. However, Huffman coding cannot encode symbols with less than one bit, so the probability is 5
Single symbols greater than 0% cannot be encoded efficiently.
Arithmetic code is based on theoretical coding techniques that require infinite precision floating point numbers. However,
Since an arithmetic coder can only be realized by finite precision arithmetic, the coding efficiency is lower than the theoretical maximum efficiency. Practical arithmetic coders, such as the IBM Q coder, use additional techniques to speed up software or reduce hardware at the expense of compression efficiency. Q coder is a binary arithmetic coder,
Multiplication is replaced by addition, the probability values are limited to discrete values, and the probability estimates are updated on bit output.

[0006] A binary entropy coder is a lossless (ie, fully reproducible) coder that has the highest probability symbol (MPS) and the lowest probability symbol (L
Binary (yes /
no) Only decisions can be handled. Examples of binary entropy coders include the IBM Q coder and the coder called the B coder. This B coder uses a binary entropy algorithm that utilizes a finite state machine for compression.
Coda. For more information on the B coder, see pending US patent application Ser. No. 07 / 931,156 (1992).
Received on August 17, 2008, "Method and Apparatus For
Entropy Coding ”).

FIG. 1 shows a block diagram of a conventional compression / decompression system using a binary entropy coder.
For coding, the data is context (contex
t) Input to the model (CM) 101. CM 101 converts the input data into a set or sequence of binary decisions and provides a context bin for each decision. Both the series of binary decisions and their associated context bins are C
The signal is output from M101 to the probability estimation module (PEM). PEM 102 receives each context bin and generates a probability estimate for each binary decision. Practical probability estimates are usually represented by a class called the P class. Each P-class is used for a range of probabilities. PEM102 also
It is also determined whether the binary decision (result) is in the high probability state (ie, whether the decision corresponds to an MPS). The bitstream generator (BG) module 103 receives as inputs a probability estimate (ie, a P-class) and a determination of whether the probability of a binary decision is high. Then, the BG module 103 outputs compressed data representing the original input data, that is, zero or one or more bits.

In the case of decoding, the CM 104 gives the context bin to the PEM, and the PEM gives a probability class (P class) to the BG module 106 based on the context bin. The BG module 106 is connected to receive the probability class. In response to this probability class, BG module 106 returns a bit indicating whether the binary decision (ie, event) is in its highest probability state. The PEM 105 receives this bit, updates the probability estimate based on the bit, and returns the result to the CM 104. CM 104 receives the returned bits, uses it to generate the original data, and updates the context bin for the next binary decision.

[0009] Context models are typically application-specific. Since any kind of data can be broken down into bits, a binary entropy coder can be used with any data by using a suitable context model. One example of a context model is
Given by the JBIG standard (ISO / IEClnter
national Standard, "Codded Representation of Pi
cture and AudioInformation-Progressive Bi-leve
l Image Compresion Standard ”).

"The model template defines the surroundings of the pixels to be coded. The values of these surrounding pixels and the spatial phase of the differential layer define one context." One example is given by the JPEG standard (Digital Compression and Coding of Continuous).
-tone Still Images. ISO / IEC internationa
l Standard).

[0011] Since the context model is application specific, a general purpose coder is built with only the probability estimation module and the bitstream generator in mind. Certain probability estimation modules and bitstream modules can be substituted. Another probability estimation module relies exceptionally only on one particular bitstream generator. For example, IBM's Q coder combines a probability estimation module and a bitstream generator. The B coder is just a bitstream generator. Thus, the B coder can be used with any probability estimation module.

[0012] Like IBM's Q coder and B coder,
The problem with decoders that use binary entropy codes is that they are slow even if implemented in hardware. Their operation requires a single large slow feedback loop. To rewrite the decoding process, the context model generates context using past decoded data. The probability estimation module uses the context to generate a probability class. The bitstream generator is
Using this probability class and compressed data, the next bit is
It is determined whether the result is likely or unlikely (likely or unlikely result). The probability estimation module uses this "probable / impossible result" to generate a result bit (and updates the probability estimate for the context). This result bit is used by the context model to update the history of the past data. All of these steps are required for 1-bit decoding.
The decoding of the next bit must wait because the context model cannot provide the next context until the result bit history is updated. Therefore, conventionally, parallel decoding of a single code data stream has not been performed. In order to increase the decoding speed of the compressed data, it is desired to decode the data in parallel.

[0013]

Accordingly, it is a primary object of the present invention to achieve high speed decoding, and the details of this and many other objects will be apparent from the description in connection with the following embodiments. Would.

[0014]

SUMMARY OF THE INVENTION The present invention introduces parallelism in decoding coded data. According to one aspect of the present invention, the decoding apparatus has a configuration for processing a plurality of context bins in parallel, and the coded data stream is rearranged into a plurality of data streams corresponding to the context bins and operates independently. To a combination of multiple sets of bitstream generators and probability estimation modules. According to another aspect of the present invention, the decoding apparatus is configured such that the coded data streams are processed in parallel according to the probability classes by a plurality of bitstream generators associated with different probability classes.

[0015] The above and other means of the present invention for solving the problems will be described in detail in the description relating to the embodiments.

[0016]

Since the coded data stream is decoded by the parallel processing, the decoding speed can be drastically increased as compared with the prior art.

The above operation and other operations of the present invention will be described in detail in the description related to the embodiment.

[0018]

DETAILED DESCRIPTION OF THE INVENTION The present invention provides a method and apparatus for encoding and decoding data in parallel. The present invention provides an apparatus for compressing a multi-bit data stream. The device has an input channel for receiving a data stream. The apparatus also includes a decoder for decoding each bit of the data stream, wherein at least two of the codewords in the data stream are decoded simultaneously, so that the data stream is decoded in parallel.

The present invention, in one aspect, processes context bins in parallel, and in another aspect, processes probability classes in parallel.

In the present invention, the encoded data is provided to a number of bitstream generators.
In one aspect, multiple channels are used. In another embodiment, a single non-interleaved
Channels are used. In another aspect, a single interleaved channel is used.

The present invention provides a parallel decoding /
A method of using an R coder associated with an encoding device is provided. The R coder according to the invention comprises at least one Rn
Use the R2 (k) code with the (k) code. Where n
Is a natural number. The R coder of the present invention, in one aspect, uses R2 (k) and R3 (k) codes.

Now, a method and apparatus for parallel encoding / decoding of data will be described. In the following description, various specific examples, such as a specific number of bits, the number of coders, the probability, and the type of data, will be presented in order to enhance the understanding of the preferred embodiment of the present invention. It will be apparent to one skilled in the art that the present invention may be embodied without these specific examples. In other instances, well known circuits have been shown in block diagram form in order to avoid unnecessarily obscuring the present invention.

<Overview of Parallel Decoding> The present invention provides:
An apparatus for decoding encoded data in parallel and losslessly. The invention is based on the realization that in most entropy compression devices the feedback loop between the context model and the decoder is a bottleneck. We decompose this feedback loop by dedicating multiple coders to one context bin. As a result, the speed of the device is determined solely by the smaller, faster feedback loop in the context model and the input speed of the codeword to the device. The present invention contemplates multiple coder and context models by considering that the context model substantially reorganizes the coded data stream into several different data streams, one for each context bin. And decoupling between them. By obtaining the coded data in context bin order instead of the original data stream order, multiple coders decode any or all of the coded data without waiting for feedback from the context model (These streams are generated in context bins, but may be generated for each probability class).

Here, the parallel decoding of the present invention will be described in comparison with the prior art. FIG. 2 shows a conventional decoder in which an input buffer 201 is connected to receive coded data and a feedback signal from a decoder 202. Input buffer 201 sends coded data to decoder 202 in response to requests made by the decoder through a feedback signal. Decoder 20
2 decodes the coded data according to its context and probability estimates, and
To the model 203, this context model 20
3 outputs decoded data. Once the decoder 202 sends the decoded data to the context model, the context model 203 can update the context and send the necessary information to the decoder 202 to start decoding the next bit to the decoder 202 via a feedback signal. . Then, the decoder 202 requests coded data from the input buffer 201 using the feedback signal. Thus, two feedback loops operate sequentially to decode the coded data stream.

FIG. 3 shows the decoder of the present invention without the conventional slow feedback loop. As in FIG. 2, input buffer 204 receives the coded data (ie, the codeword) and the feedback signal from decoder 205, and supplies the coded data to decoder 205 of the present invention in context bin order.
Decodes the coded data. The decoder 250
It comprises a plurality of decoders 205A, 205B, 205C,..., One for each context bin.
A plurality of decoders 205A and 205 in the decoder 205
, B, 205C,... Are supplied from the input buffer 204 with the coded data of the corresponding context bin. Each decoder 205A, 205B, 205
C,... Send out the decoded data of the context bin. The context model does not need to associate coded data with a particular context bin. The decoder data is supplied to the decode data memory 207 (207A, 207B, 207) by the decoder 205.
C, ...).

The context model 206 sends a feedback signal to the decode data memory 207 (207A, 207B, 207C,...) While operating independently, and in response to this signal,
(207A, 207B, 207C,...) Are connected to receive already decoded data. Therefore, there are two independent feedback loops. One is between the decoder 205 and the input buffer 204, and the other is between the context model 206 and the decode data memory 207. Since the large feedback loop has been eliminated, the decoder 205
A plurality of decoders 205A, 205B, 205
C,... Can receive their associated codewords from input buffer 204 and immediately decode them.

The context model provides a memory portion of the coding device, based on which the set of data (eg, images) is divided into various categories (eg, context bins). In the present invention, context bins are considered as independent data sets. In one embodiment, each context bin has its own probability estimation model. Thus, each context bin can use a different probability estimation model and / or bitstream generator. In another embodiment, the probability estimation model is shared and each context bin has a unique state (stat
e) can have.

In the present invention, a context model divides data (eg, an image) into several data streams. In other words, the context model reorganizes a collection of data or images into multiple data streams, one for each context bin. In one embodiment, each coder is dedicated to a particular context bin.

By dedicating a coder to a particular context bin, the feedback loop between the context model and the coder can be eliminated. Note that the feedback loop is eliminated because the previous bit is in the same bin as the next bit, and therefore in the same context, so each coder indicates the context of the previous bit before decoding the next bit. Because it is not necessary to receive it. In other words, no context feedback must be completed before the next bit can be decoded.

The present invention allows each context bin to send an individual coded data stream in parallel,
The bits of all context bins are received in parallel by the bitstream generator. Each of the bitstream generators returns a bit indicating whether the binary decision is in its probable state, and the probability estimation module uses this bit to return the decoded bit (ie, the binary decision). The context model reproduces the original data by selecting the decoded bits from the bitstream generator in an appropriate order and outputting a stream of decoded data. That is, the context model simply selects the decoding result from a different codestream in a manner similar to a multiplexer. Thus, by obtaining the coded data in a context bin (or class) order rather than a special order (eg, raster scan order), the coder can partially wait without waiting for feedback from the context model. Alternatively, encoded data corresponding to all context bins can be decoded. Note that since the probability estimation model is not removed by the present invention, a feedback loop of the probability estimation value remains.

The parallel decoding apparatus of the present invention has various implementation methods. In one embodiment, the coded data streams corresponding to multiple context bins can be interleaved into a single stream that is ordered for the needs of various coder. In the currently preferred embodiment of the invention, the coded data is ordered such that each coder is constantly supplied with data, even if it is sent serially to the decoder.

The coded data can be decoded quickly and in parallel using a small simple coder that can be duplicated cheaply on an integrated circuit. In one embodiment, a field programmable gate array is used.
A coder is implemented in hardware using a gate array (FPGA) chip or a standard cell application specific integrated circuit (ASIC) chip. The combination of parallelization and a simple bitstream generator allows the decoding of coded data to be performed at a higher speed than conventional decoders, while maintaining the compression efficiency of conventional decoding devices.

The binary entropy code uses a plurality of context bins and probability estimation states (classes). The method and apparatus of the present invention allows for parallel processing of context bins or probability classes by parallelization. When processing the context bins in parallel, one probability estimation module is associated with each bitstream generator. The probability estimation module indicates to the associated bitstream generator which code to use to generate a data stream from the input codeword. An example of such a device is shown in FIG. 4, in which coded data is input to channel control 221. Channel control 221 receives the encoded data,
Multiple bitstream generators (BG222,
BG223, BG224,...). Each of these bitstream generators receives the coded data and provides the result of whether the codeword is in a high probability state to the associated probability estimation module by its probability estimation module (PEM). Connected to provide according to the given probability class. PEM225, 226, 227, ... are BG22
, 223, 224,... Respectively.
Each bitstream generator can operate independently of each other because it always decodes coded data with the same context bin. The context model 228 is connected to each of the probability estimating modules and selects the probability estimating module to obtain decoded data in an order determined by the application. In this way, decoded data is generated by performing parallel processing of the context bin.

On the other hand, when processing probability classes in parallel, a context model and a probability estimation model are combined. In this case, each bitstream generator is assigned to a particular probability class and receives the resulting information. An example of an apparatus for processing probability classes in parallel is shown in FIG. In FIG. 5, coded data is input to a channel control 231, and a plurality of bitstream generators (BG232, BG233, BG23) connected to receive the coded data are received.
4, ...). Each of the bitstream generators is connected to a PEM 235.
The PEM 235 is also connected to the CM 236. In this configuration, each of the bitstream generators decodes the coded data and the result of the decoding is selected by PEM 235 (rather than by CM 236). Each of the bitstream generators receives coded data from a source associated with a certain probability class (ie, here it is possible to receive coded data from any context bin). PEM 235 uses the probability class to select a bitstream generator. The probability class is
In contrast, indicated by the context bin provided by CM 236. Thus, decoded data is generated by parallel processing of the probability classes.

The parallel processing of context and probability classes eliminates the need to serialize the codestream as in conventional decoders.

It should be noted that the present invention can be applied to all kinds of data including image data.

<Code Type and Bitstream Generator for Parallel Decoding> In the present invention, an existing coder such as a Q coder or a B coder can be used as a bitstream generation element having a parallel configuration. However, other codes and coders may be used. The coder and its code employed in the present invention are simple.

In the present invention, a bit stream generator of not a complicated code but a simple code such as an arithmetic code used in a Q coder or a multi-state code used in a B coder. Use to bring effect. The advantage of simple code is that the hardware is much faster and faster than complex code.
It is simpler and requires less silicon.
Another advantage is that decoding efficiency can be improved. Code using a finite amount of state information cannot completely satisfy Shannon's entropy limit for every probability. Code that allows a single bitstream generator to handle multiple probabilities or contexts must be limited to reduce coding efficiency. Eliminating the necessary restrictions for this multiple context or probability class would allow us to use code that nearly satisfies Shannon's entropy limit.

Two codes that can be used in the parallel decoding method of the present invention are an R code and an A code.

<R Code> The code (and coder) employed in the presently preferred embodiment of the present invention is called an R code. The R code is an adaptive code that includes a Golomb run-length code (ie, an R2 (k) code).
In the presently preferred embodiment, the parameters of the R code are determined so that many different probabilities can be handled by one decoder design. further,
The R code of the present invention can be decoded by simple and high-speed hardware.

In the present invention, an R code is used for encoding or decoding by an R coder. In the currently preferred embodiment, R
The coder is a combination of a bitstream generator and a probability estimation module. For example, referring to FIG. 1, the R coder is a combination of a probability estimation module 102 and a bitstream generator 103, and
It could consist of a combination of a probability estimation module 105 and a bitstream generator 106.

A codeword represents a run of the highest probability symbol (MPS). MPS represents the result of a binary decision with a probability greater than 50%. On the other hand, the lowest probability symbol (LPS) represents the result of a binary decision with a probability of less than 50%. When the two results have the same probability, it does not matter whether the result is specified in the MPS or the LPS, but the same specification is made in both the encoder and the decoder. For a certain parameter called MAXRUN,
Table 1 shows the resulting bit sequence in the compressed file.

[0043]

[Table 1]

When encoding, M in one run
The number of PSs is counted by a simple counter.
If this count value is equal to the MUXRUN count value, a codeword of zero is sent out in the codestream and the counter is reset. Upon encountering the LPS, a unique description of the number of MPS symbols before the LSP, followed by one and a group of bits N, is sent out in the codestream. (Note that there are various ways of assigning the N-bit group for describing the run length.) The counter is reset again. The required number of bits of N is MAXRUN
Depends on the value of Also, the one's complement of a codeword can be used.

When decoding, when the first bit of the code stream is 0, the value of MUXRUN is put into the MPS counter, and the LPS indication is cleared. Then, the zero bit is discarded. If the first bit is 1, subsequent bits are examined to extract bits N, the appropriate count value (N) is placed in the MPS counter, and the LSP indication is set. Then, the bit group of the code stream including the 1N codeword is discarded.

The R code is generated according to the rules shown in Table 1. The definition of a specific R code Rx (k) is MAXRUN
Note that it is determined by For example, MUXRUN for Rx (k) = x * 2k ^-1 . Thus, MUXRUN for R2 (k) = 2 * 2 ^k-1 MUXRUN for R3 (k) = 2 * 2 ^{k-1 and} so on.

It should be noted that the R code is an extension of the Golomb code. Golomb code is R2 (・)
Only use code. The R code of the present invention can use both the R2 (k) code and the R3 (k) code, and can use other Rn (k) codes if necessary.
(k) Code can also be used. In some embodiments, R2
The (k) code and the R3 (k) code are used. Note that Rn is
exists for n = 2 and n = any odd number (eg,
R2, R3, R5, R7, R9, R11, R13, R1
5). In one embodiment, for an R2 (k) code, the run count r is decoded to N and the run count r is k
Are described in bits, so 1N is represented by k + 1 bits. In one embodiment, in the case of the R3 (k) code, the bit group N includes one bit for indicating whether n <2 ^(k-1) or n ≧ 2 ^(k-1). K-1 bits or k, which can be included and indicate the run count value
Bits, so that the variable N has a total k
Bit or k + 1 bits. In another embodiment, the one's complement of N is used for the codeword. In this case, M
PS tends to generate a code stream with many zeros, and LPS tends to generate a code stream with many ones.

Tables 2, 3, 4 and 5 show the efficient R codes used for the presently preferred embodiment of the present invention. Note that other run length codes can be used in the present invention. Examples of other available run length codes for R2 (k) are shown in Table 6.

[0049]

[Table 2]

[0050]

[Table 3]

[0051]

[Table 4]

[0052]

[Table 5]

[0053]

[Table 6]

<R Code Probability Estimation Model> In the presently preferred embodiment of the present invention, the R2 (0) code is not coded. That is, the input 0 becomes 0 and the input 1 becomes
Are each encoded to 1 (and vice versa), which is optimal for a 50% probability. In the currently preferred embodiment, the R3 (0) code is not used. In the currently preferred embodiment, the R2 (1) code has a probability of 0.70.
7 (ie, 70.7%), and R3 (1) is optimal when the probability is 0.794 (79.4%). R
The 2 (2) code is optimal for a probability of 0.841 (84.1%). Table 7 below shows the nearly optimal Golomb code, where the probability skew is defined by the following equation: Probability skew = -log ₂ (LPS)

[0055]

[Table 7]

It should be noted that although the k value at which the optimal probability is high does not vary as much as at the low k value, the probability range indicated by the probability skew covers the probability space almost uniformly, and this code is Almost optimal.

R2 (k) for a given k is called Golomb's run-length code. However, a certain k
Is only approximately optimal for a certain probability. When coding with optimal probability, R
Note that the code uses the 0 codeword and the 1N codeword at the same frequency. In other words, the R coder of the present invention outputs one code at half the time and outputs the other code at another half of the time. By examining the number of 0 codewords and 1N codewords, it is possible to determine whether an optimal code is used. That is, when the number of outputs of the IN code word is too large, the run length is too long,
On the other hand, when the number of outputs of the 0 code word is too large, the run length is too short.

The probability estimation model used by Langdon examines the first bit of each codeword to determine if the source probability is higher or lower than the current estimate. K is increased or decreased based on the determination result. For example, when a codeword indicating MPS appears, the probability estimate is too low. Thus, according to Langdon, k is incremented by one for each 0 codeword. MUXRUN MPS
The probability estimate is too high when a codeword indicating less than followed by LPS appears. Thus, according to Langdon, k is decremented by one for each 1N codeword.

The present invention enables a more complex probability estimation than the method of simply increasing or decreasing k by one for each codeword. The invention includes the state of the probability estimation module, which determines the code to use. The same code may be used in many situations. Code is assigned to states using a state table or state machine.

In the present invention, the probability estimation value changes state for each codeword output. Therefore, in the present invention,
The probability estimation module increases or decreases the probability estimate depending on whether the codeword starts with 0 or 1. For example, when the "0" codeword is output, the estimated value of the MPS probability increases. On the other hand, when the "1" codeword is output, the estimated value of the MPS probability decreases.

The conventional Langdon coder uses an R2 (k) code and only increases or decreases k for each codeword. In contrast, the present invention uses the R2 (k) and R3 (k) codes in combination with a state table or state machine to adjust the adjustment speed to the application. That is, if there is a small amount of fixed data, the adjustment must be quick for optimal coding,
If there is a large amount of fixed data, the adjustment time may be increased so that coding can be selected to improve the compression ratio for the rest of the data. When the number of occurrences of the state change is variable, the adjustment speed is also affected by the characteristics of each application. Due to the nature of the R code, R
Code estimation is simple and requires little hardware, albeit very powerful.

By incorporating the R3 (k) code,
A wider probability space can be covered with higher resolution. FIG. 6 shows an example of the probability estimation state table according to the present invention.
Is shown in Please refer to FIG. The probability estimation state table comprises a state counter and codes associated with each state in the table. Note that this table includes both positive and negative states. This table contains, as shown, the state of 0,
It has 37 positive states and 37 negative states. A negative state means an MPS state different from its positive state. In one embodiment, a negative state when MPS is 1 and an MPS
The positive state can be used respectively, or vice versa. Note that the table shown in FIG. 6 is merely an example, and that the number of states may be increased or decreased, and a table with a different state assignment may be used.

Initially, the coder is in state 0,
Is the R2 (0) code (ie no code) for the case where the probability estimate is 0.50. After processing each codeword, the state counter is incremented or decremented according to the first bit of the codeword. In the currently preferred embodiment, a codeword of 0 increases the value of the state counter, and a codeword that starts with 1 decreases the value of the state counter. Thus, all codewords change state with the state counter. Stated another way, the probability estimation module changes state. However, successive states can be associated with the same code. In this case, probability estimation is performed without changing the code for each codeword. In other words, the state changes every cycle,
At certain time intervals, they are mapped to the same probability. For example, state 5 to state -5 all use the R2 (0) code, but state 6 to state 11 and state -6 to state -11 use the R2 (0) code.
(1) Use the code. By using the state table of the present invention, nonlinear probability estimation is possible with the same coder.

It should be noted that for low probabilities, more states with the same R code are involved. The reason for this is that using a wrong code with a low probability results in a large loss of efficiency. The nature of the run-length code table is that the state switches after each codeword.
In a state table designed so that the code changes at each state change, at a low probability of state switching, the code goes between code very close to the entropy efficiency limit and code far from the entropy efficiency limit. Come and go. Thus, disadvantages (disadvantages in terms of the number of bits of coded data) result in state transitions. It is this disadvantage that conventional probability estimation modules, such as the Langdon probability estimation module, do not perform well.

For high-probability run-length codes, the penalty for code errors is not significant.
Therefore, in the present invention, the state is added to the low probability, and 2
By reducing the change that spans between the two correct states, coding efficiency is reduced. FIG. 7 shows a graph of such coding efficiency (code length normalized with respect to entropy) versus MPS probability. FIG. 7 illustrates how some of the R codes of the present invention cover a probability space. As an example, it can be seen from FIG. 7 that for an MPS probability of about 0.55, the efficiency of the R2 (0) code is 1.01 times the entropy limit (ie, 1% worse than the entropy limit). In contrast, R2 (1)
The efficiency of the code is 1.09 times the entropy limit (9% worse than the entropy limit). This example shows that using the wrong code for such a low probability reduces coding efficiency by 8%.

In some embodiments, the coder may have an initial probability estimation state. In other words, the coder may be started from a predetermined state in the states, for example state 18. In one embodiment, by using a state table for the first few symbols,
Several states that allow for quick adjustment are used, and for the remaining symbols, another state table for slow adjustment is used to allow for fine adjustment of the probability estimates. In this way, the coder can use the more optimal code more quickly in the coding process. In another embodiment, an initial probability estimate can be specified for each context in the codestream. In some embodiments, the increment and decrement are not fixed numbers (eg, one).
The probability estimation state is incremented by a variable number corresponding to the amount of data already encountered or the amount of change (stability) of the data.

When the state table is symmetric as in the table illustrated in FIG. 6, it is sufficient to store only half of the state table (including the 0 state). In some embodiments, to take advantage of this symmetry, state numbers are stored in signed one's complement form. In this way, this table can be used by determining the state by taking the absolute value of the one's complement and checking the sign to determine whether the MPS is 1 or 0. This allows the table to be indexed using the absolute value of the state and the simple calculation of the absolute value of the one's complement reduces the hardware required for incrementing or decrementing the state. Can be. In another embodiment, the state table is replaced with a hardwired or programmable state machine to increase hardware efficiency.

<Example of Hardware Configuration> FIG. 8 is a block diagram of a decoding apparatus using an R code. In FIG. 8, an R code decoder 501 is connected to coded input data and outputs a run length and an indication of whether LPS has appeared (for example, 1N code). run·
The counter 502 is connected to receive the run length and the LPS instruction from the R code decoder 501, and outputs the reproduced original data. Run counter 50
2 also outputs a signal requesting the next count value (the R code decoder 501 is connected to receive this signal).

Since the R code is used, the decoder 501
Examines the codeword received as coded data input to determine the run length of the current codeword. The R code decoder 501 also determines whether there is an LSP at the end of the run. Run length (ie, run count value) and L
According to the determination result of the PS, the run counter 502 outputs MPS by the same number as the run count value, and outputs LSP when the decoder 501 instructs. LP
When "no" is output to the run counter 502 as the determination result of S, the run counter 502 outputs only the MPS (in the Q coder, an operation is required to output bits, Note that in the present invention only a counter is sufficient).

The run counter 502 actually outputs a group of bits. It should be noted that the run counter 502 partially acts as the decode data memory 207 of FIG. In one embodiment, the run counter 50
2 outputs the required number of MPS bits, followed by LSB bits if necessary. Run counter 50
2 is a signal (ne
xt count request) to request the next codeword.
Thus, the run counter 502 is simple and fast. The R code decoder 501 includes a run counter 50
Upon receiving the signal from 2, a one-bit shift is performed for the next codeword. The R code decoder 501 also updates the state of the probability estimation module.

FIG. 9 is a block diagram showing another embodiment of the R coder according to the present invention. In FIG. 9, the R coder 600 includes a shift block 601, a decode block 602,
It comprises a run counter 603 and a PEM 604. Shift block 601 is connected to a coded data input stream of codewords. Shift block 60
1 is also connected to receive a feedback signal from the PEM 604 indicating the length of the current codeword (ie, the amount to shift). Shift block 601 outputs a signal (code data properly aligned) which is connected to the input of decode block 602. Decode block 602 is also connected to receive a feedback signal from PEM 604 to indicate the current code. PEM 604 is also connected to the signal from decode block 602. Decode block 602 includes the current run length and the LPS at the end of the run.
Determine if there is. Decode block 602 outputs two signals, a run length (RL) and an LSP indication, both signals being connected to the input of counter 603. Counter 603 is also connected to the signal output to PEM 604. The counter 603 generates reproduction data. The counter 603 is a run count counter (run count).
counter) and whether to transmit LPS. The counter 603 also sends out the decoded data,
In addition, it indicates when to process the next codeword. PEM6
04 is connected so as to receive from the counter 603 an instruction (next count value request) at the time of processing the next codeword.

The PEM 604 includes a shift block 601
, The shift amount for processing the next data, the current code for the decode block, the next state for updating the internal state, and the MPS. The current code form is a bit mask that causes decode block 602 to decode only the bits of the current codeword. Each of these functions is directed to the essential blocks (ie, shift block 601, decode block 602, and counter 603) by separate feedback lines.

When the operation of the R coder 600 starts, the code sets the R coder 600 from the bit position to be processed first.
Given to. Shift block 601 receives the coded data and provides it to decode block 602. In one embodiment, shift block 601 comprises a barrel shifter. In one embodiment, shift block 601 provides coded data to decode block 602 in parallel.

[0074] Decode block 602 determines the type of codeword based on the first bit. In one embodiment, determining the codeword type is by checking for an LSP at the end of the run. In another embodiment, the codeword type determination includes checking whether the second bit is 1 or 2. Checking this second bit is 1N
Is important when the number of N bits of the second bit is known by the second bit (for example, in R3 (1), the number of bits following 1 is one or two bits).

In one embodiment, decode block 60
No. 2 determines whether the run length is MUXRUN or whether the run length is encoded in N bits after 1 (for example, 1N). PEM6
04 sends the current code to the current code signal line to indicate the number of bits in the 1N codeword. The number of bits is indicated because the longer the code, the more bits are required.

The result of the code word type determination is instructed to PEM 604 by a code word type signal. PEM604 is
The codeword length is determined using the current code and the codeword type.
This codeword length is connected to shift block 601.
Shift block 601 uses the codeword length to adjust data for the next codeword.

The PEM 604 updates the state of the probability estimation module using the type of the code word. The updated state of the probability estimation module is used by the decode block 602 to determine a new current code to be used later. The counter 603 generates decoded data in the same manner as the run counter of FIG.

Since the length of a code is variable, if the length of a certain code is 3, the next code word is located at a position separated by 4 bits. Thus, the shift block 601 shifts 4 bits backward in the codestream,
The data is sent to the decoding block 602 from that position. In one embodiment, the signal to signal that decode block 602 has finished for the current codeword is a PE signal.
By inputting to the shift block 601 from M604, the shift block 601 shifts. After outputting the decode data, the run counter 603 requests the R code decoder 500 for the next count value. Thereafter, the entire decoding, probability estimation module and shifting process is repeated.

When compression is enabled, most codewords are decoded into multiple bits. If the device has a plurality of R code decoders, the shifter module, the decoding module and the feedback
A module can be shared by several counter modules. Examples of such a device will be described later.

Therefore, the present invention can perform decoding at almost the highest compression ratio by using the R2 (k) code and the R3 (k) code together with the state table / machine PEM. Further, the present invention provides a state table P
By using EM, a simple probability estimation module can be realized with low hardware cost and high-speed hardware.

<Example of Hardware Configuration of R Decoder Using FPGA> FIG. 10 shows the configuration of a simple R coder. This R coder is available from Concurrent Logic (Sunnyval
e, California) of the brand CLi6005
Designed using PGA. The probability estimation model associated with the R coder of FIG. 10 is shown below.

[0082]

[Table 8]

In this example, only the R2 code is supported, and the R2 (7) code is the longest run length code.

Referring to FIG. Shift register 701
Are connected to receive coded data from memory by an 8-bit bus. The shift register 701 outputs the coded data one bit at a time, and this bit is connected to the control 703 and the shift register 702.
The shift register 702 is connected to the multiplexer 704. Loading of the up / down shift register 708 is performed by inputting a logic one. The shift register 708 is an up / down shift register 7
09, and a logic 0 is input to the shift register 709. The output of shift register 709 is connected as input to encoder 710 and multiplexer 704. The output of the multiplexer 704 is connected to one input of a comparator 706. The other input of the comparator 706 is connected to the output of the counter 705. The counter 705 is connected to the counter 711. The counter 711 is connected to one input of the comparator 712. The other input of the comparator 712 is connected to the output of the encoder 710. The output of the comparator 712 is the control 703
The output of the comparator 706 is the same. The output of the control 703 is data connected to the input of the shift register 707. The shift register 707 receives data serially and outputs the data in parallel. The control 703 is connected to other blocks and controls them.

The circuit of FIG. 10 operates in a manner similar to that described with reference to FIG. In the case of this embodiment, the shift register 70
1, 702 corresponds to the shift block in FIG. Combination of up / down shift registers 708 and 709 and encoder 710, counter 711 and comparator 7
12 provides a probability estimation module of the R coder in FIG. The decoding block of the R coder is a multiplexer 7
04, the run counter is implemented using a counter 705 and a comparator 706.

FIGS. 11 to 13 show examples of the circuit configuration of FIG. FIG. 11 is a circuit diagram of the control logic of the R decoder of FIG. FIG. 12 is a circuit diagram of the probability estimation module. FIG. 13 is a circuit diagram of the shifter, decoder and counter of the R decoder of FIG. The operation of each circuit shown in the circuit diagram is well known in the related art. 11 to 13, the same elements as those of the specific block in FIG. 10 are clearly indicated by reference numbers enclosed in parentheses. All other blocks without reference numbers in parentheses are control circuits whose operation is well known in the art.

<A Code> The A code of the present invention is a variable length to variable length code optimized for a certain probability. In other words, the A code of the present invention is not adaptive. The A code of the present invention can be used in an apparatus that performs parallel decoding of different probability classes. An example of A code is A1
Code. The A1 code is shown below. 00 → 001 → 10 1 → 11 The A1 code of the present invention has an MPS of about 0.71 (71%).
Efficient for probability.

Another example of the A code is the A2 code. The A2 code of the present invention is shown below. 0000 → 00001 → 10000010 → 10010011 → 11111010 → 101011 → 11101100 → 110101 → 1111011 → 11100 A codes can be cascaded to accommodate various probabilities. For A codes, one variable length code is used as a building block, which can be cascaded in series with the variable length code to generate a code for another probability. In practice, passing a code of one probability through another coder produces a code stream of another probability. For example, when the output of the above A1 code is input to another A1 decoder,
One cascaded A1 code is obtained. Similarly, the output of the A2 decoder can be input to the A1 decoder.

It is also possible to use an A1 coder to obtain a multistage cascaded code. In one embodiment,
The device processes multiple probability classes in parallel, but each probability can be input to a separate part of the A-coder chain. That is, each of the A-coders is
Probability classes corresponding to the output of the coder and the data for a context bin are received, and when both are input, another probability code is generated.

The A code of the present invention is a code that can be easily realized by hardware. By cascading a plurality of A-coders, the amount of hardware required to implement the device is reduced.

The A code of the present invention can be decoded at a high speed by using a small amount of wiring logic or a small look-up table. The A-code allows the use of an external probability estimation module, so that any PEM can be used in the entropy coding device.

<Parallel Decoding Device> Non-Interleaved Parallel Decoding Device The present invention uses non-interleaved or multi-channel coder in parallel to increase the coding speed of a binary entropy coder. As mentioned above, binary entropy coders, such as the IBM Q and B coders, require a single large feedback loop between the decoder and the context model. By using appropriate coded data transmission methods and multiple decoders, the context model feedback loop is isolated. By separating the context model feedback loop, the context model can be turned into a choice of decoding results.

In the present invention, parallelization can be adopted by separating the functions of the context model and the coder. In the currently preferred embodiment, the probability estimation module is combined with a context model (for a B coder) or a bitstream generator (for a Q coder). Each bitstream generator is assigned to one subset of the code data. Each subset may be associated with a context bin or a probability class, which is up to the design. In other words, in one embodiment,
Each of a group of bitstream generators
In another embodiment, each of the bitstream generators receives coded input data corresponding to one probability class, wherein the coded input data corresponds to one context or class of context bins. If the number of contexts and bins is larger than the number of coders, a plurality of context bin classes may be associated with one bitstream generator.

By pipelining the context model and the bitstream generator, the speed of the decoder is increased and the speed is increased only by the time required to complete the slower operation, rather than the total time of the two operations. Limited. Because the bitstream generator operates independently of the context model, multiple bitstream generators can be used in parallel to increase speed.

The present invention can be implemented utilizing pipeline techniques. In the present invention, the bit stream
The generator part can also be a pipeline. FIG. 9 is referred to again. Input data may be input to the R code decoder while data is being sent from the decode block 602 to the run counter 603. Similarly,
A pipeline technique may be employed between the R code decoder and the run counter 603. The pipeline technique may also be used for the decoding block 602 and the PEM 604 inside the R code decoder.

Therefore, the present invention can operate at the same speed as that of the context model (when the decoding result is selected, the time required to perform a simple multiplexer operation is added to the time of the context model). Equipment.

In the present invention, the coded data is provided to a number of bitstream generators. In some embodiments, multiple channels are used. In another embodiment, a single non-interleaved channel is used.
In another embodiment, a single interleaved channel is used.

Multi-Channel Coder The present invention provides a multi-channel coder that performs parallel decoding of compressed input data. In one embodiment, in a multi-channel coder, each bitstream generator is assigned to a context bin or a group of context bins. To implement this multi-channel coder, independent channels are provided for each context bin. Thus, each context bin has one independent channel that is input to a dedicated bitstream generator and probability estimation module for decoding the bits of a particular context bin. Another embodiment is a probability class (P class)
Each has one independent channel. FIG. 14 is a block diagram of an embodiment of a multi-channel coder for a parallel probability class according to the present invention.

In FIG. 14, original data is input to an encoder 1101. In one embodiment, encoder 1101 receives the data and encodes it into an encoded data file. The decoding of the data is performed by the decoder 1111. Decoder 1111
Are the bitstream generators 1102 to 110
5 and an integrated PEM / CM 1106. When decoding data, each probability class (P class)
Are received by a group of bitstream generators over separate channels. Coded data corresponding to P class 1 is sent by channel 1107. Channel 1107 is connected to one input of bitstream generator 1102. P
The coded data for class 2 is sent by channel 1108. Channel 1108 is connected to one input of bitstream generator 1103. Coded data corresponding to P class 3 is sent by channel 1109. Channel 1109 is connected to one input of bitstream generator 1104. P class 4
The corresponding coded data is sent on channel 1110. Channel 1110 is connected to one input of bitstream generator 1105. Although only four channels and bitstream generators are shown in FIG. 14, the actual number depends on the specific application and may be increased or decreased from four.

The probability estimation module (PEM) / context model (CM) 1106 includes a bit stream
Each of the generators 1102-1105 is connected to receive an output and produces a decoded data output. It should be noted that the encoder 1105 is only shown to describe the entire data path of the compression / decompression device. The decoder 1111 can operate when data to be decoded is encoded and stored in advance, for example, when a graphic image is stored in a memory in a video display device.

When the decoder 1111 decodes the compressed data, the PEM / CM 1106 selects the data output of the bit stream generators 1102 to 1105. When the PEM / CM 1106 selects one of the bitstream generators as the decode bit, the data is ready in time. Therefore, PEM / CM1
106 only selects the result that has already been decoded.
While the PEM / CM 1106 is selecting one of the bitstream generators, the other unselected bitstream generators are decoding data received on their dedicated channel. Thus, when the PEM / CM 1106 selects the next result, the data is ready (in the proper order).

This proper order is freely designed and is known on the PEM / CM 1106 side. PEM /
The CM 1106 selects data from the bin in this proper order. For example, if the data is image data,
The PEM / CM 1106 accesses the respective output data of the bit stream generator in the order of images (that is, the order of raster scan). That is, the meaning of the order of use of the PEM / CM 1106 is given by the raster scan.

Since the independent channels 1107 to 1110 constantly supply new data to the bit stream generators 1102 to 1105, the bit stream
Generators 1102-1105 never play (always have data to decode).

FIG. 15 shows a block diagram of one embodiment of a multi-channel decoder according to the present invention that processes context bins in parallel. In FIG. 15, data is input to an encoder 1215 and encoded. The encoder 1215 is connected to each of the channels 1201 to 1204. Each of the channels 1201 to 1204 transmits the coded data corresponding to the context bins 1 to 4, respectively.
5 to 1208, respectively. The outputs of the bitstream generators 1205-1208 are output to probability estimation modules (PEMs) 1209-1212.
Are connected to the inputs. PEM1209-1
The decoded data output from each of the 212 is connected to a context model 1213,
Model 1213 orders the output of all PEMs 1209-1212. FIG. 15 is merely a data flow diagram. Other signals required for operation have not been shown in order not to obscure the present invention. These signals and their function will be apparent to those skilled in the art.

The operation of the decoder 1214 is as follows.
9 to 1212, the decoder 1 shown in FIG.
Similar to 111. In the decoder 1214, P
Each of the EMs 1209-1212 is dedicated to a separate bitstream generator. For example, PEM
1209 is a bitstream generator 1205
Only works in connection with. In this case, the probability estimation module sends the decoded data bits to the context model 1213 in response to the data request signal from the context model 1203. context·
The model 1213 operates at any time. While the context model 1213 is requesting data for one context, the data is processed in parallel because data for other context bins is being decoded. Therefore,
Parallelization is available in multi-channel configurations where all bins have dedicated channels, bitstream generators and probability estimation modules.

Multi-channel decoding of data in parallel
Coders are expensive due to the large bandwidth required. This bandwidth is wasted if only one bin is used.

Non-Interleaved Channel Coder The present invention provides an apparatus for using a single channel to supply coded data corresponding to each context bin (or class) to a plurality of bitstream generators. To achieve this single channel configuration, non-interleaved channels are used. Thus, if a non-interleaved channel coder is used in the present invention, only one channel can be used to make the bitstream generator independent of the context bin (or class).

FIG. 16 shows an embodiment of a non-interleaved channel coder according to the invention for processing probability classes in parallel. Referring to FIG.
0 receives and encodes the original data. The decoder 1301 receives the coded data and reproduces the original data. The decoder 1301 has a memory
It consists of a memory control 1303, bitstream generators 1304-1307, and a probability estimation module (PEM) / context model (CM) 1308. The memory control 1303 is connected to receive the coded data stream and output data of each probability class (P class). Bitstream generators 1304-1307 are connected to receive coded data for individual probability classes from a single port of memory. The output of each of the bitstream generators 1304 to 1307 is connected to the PEM / CM 1308.

Bit stream generator 1304
1307 and the PEM / CM 1308 operate similarly to the bitstream generator and the PEM / CM of FIG. However, the decoder 1301 has various P
Receive coded data from a single channel that combines the code streams of the classes.

In the presently preferred embodiment, the coded data transmitted by a single channel is a list of pointers to the data of each P class (or pointers to the data of each context bin when processing the context bins in parallel). ), Followed by the data for each bin. All coded data is received and stored in memory memory control 1303. In the currently preferred embodiment, the coded data is stored sequentially. The memory control unit uses a pointer to store appropriate P-class data into a corresponding bit stream.
Supply to generator.

The PEM / CM 1308 requests decoded data from one of the bit stream generators 1304 to 1307. The bit stream generators 1304 to 1307 are respectively PEM / CM 1308
When it does not have the next codeword to be requested, the memory control 1303 requests a codeword. If both of these operations occur at the same rate, only one request for memory 1303 can occur at a time. However, when the PEM / CM 1303 operates at a higher speed, a plurality of requests may be issued to the memory 1303 within one memory access time. An arbitration scheme may be used to determine which bitstream generators are entitled to use the memory. In this apparatus, the PEM / CM 1308 does not instruct the memory / memory control 1303 to perform the operation-the bitstream generator requests memory access when necessary.

FIG. 17 shows a non-interleaved single channel decoder 1 for processing context bins in parallel.
FIG. 411 shows a block diagram of one embodiment of 411. The apparatus shown in FIG. 17 includes an encoder 1412 that receives data and sends coded data, and a decoder 1411 that receives coded data from a channel. Decoder 1411
Are the memory / memory control 1401, the bitstream generators 1402-1405, the probability estimation modules 1406-1409, the context model 1
410. Bitstream generators 1402-1402, probability estimation module 140
The connection and operation of 6-1409 and the context model 1410 are similar to the bitstream generator, probability estimation module and context model described in connection with FIG. Memory / Memory control 1
401 is connected and operates with bitstream generators 1402-1405 and coded input data, similar to the memory control described in connection with FIG. Again, each context bin has its own channel, bitstream generator and probability estimation module.

FIG. 18 shows an example of a concatinated code stream including data of all bins. The concatenated code stream for a single channel includes a header and coded data of each context bin. The header is used for each context in the codestream.
Consists of a pointer to the beginning of the coded data for the bin. For example, the coded data 1501 in the code stream corresponds to a pointer to the coded data of the context bin 1. The coded data 1502 in this code stream corresponds to a pointer to the data of the context bin 2. Data 1503 in this code stream corresponds to a pointer to the coded data of context bin 3. In the currently preferred embodiment, the coded data for each context bin is stored in the codestream in turn. For example, in FIG. 18, the coded data 1504 of context bin 1 follows the pointer portion of the codestream. After that, the data 150 of the context bin 2
5 followed by the coded data of context bin 3, and so on. Note that the coded data amount of each of the coded data sections (1504 to 1506) may be different.

Returning to FIG. When the decoder 1301 has fetched all of the compressed data from the single channel into the memory 1303, the start position of each data can be identified and the data can be sent to the bitstream generator when required.

In the present invention, the encoder must generate a data stream in the format required by the decoder 1308. One way to accomplish this is to use a computer to encode the data for each context bin and store the data for each context bin in a separate file. Completing the encoding of the encoded data in separate context bins determines the length of each file. This length information is converted into an appropriate format for the pointer and input to the channel. Next, each file of the encoded data is sequentially input to the channel.

Since a non-interleaved channel coder uses multiple bitstream generators, it is advantageous to use code that allows for a bitstream generator with low hardware cost.
In one embodiment, a non-interleaved channel coder is implemented using an R coder as shown in FIG. It should be noted that the non-interleaved channel of the present invention can be implemented using many other codes.

When the context model 1308 is in the memory 1
Assuming that it is slower than the accessible speed of 303, decoder 1301 operates in a pipeline and can decode data in parallel. A bit stream
While the generator is capturing the coded data, the context model 1308 decodes the run lengths of the other coded data, determines the LPS, and makes a further selection of the decoded data;
All this is done simultaneously. In one embodiment, one bit is output every memory cycle.

FIG. 19 shows a block diagram of one embodiment of a non-interleaved single channel parallel decoding architecture using the R coder of the present invention. In FIG. 19, an encoder 1609 is connected to receive and encode data. The coded data is received by the decoder 1600 from the channel. Decoder 1
Reference numeral 600 denotes a memory 1601, a decoder 1602, an address generator 1603, and counters 1604 to 160.
7, a context model 1608. The memory 1601 receives coded data from the channel, an address from the address generator 1603,
Each is connected to receive. Memory 160
1 stores the coded data and decodes it
Output to Decoder 1602 receives coded data from memory 1601. The decoder 1602 outputs a count value to a designated one of the counters 1604 to 1607. The counters 1604 to 1607 are the decoder 160
2 and receive count data in context
Connected to output to model 1608. The context model 1608 includes counters 1604-16
07, and outputs decoded data. Note that although only four counters are shown, the actual number of counters may be more or less depending on the number of context bins.

The only part that requires parallel operation of decoder 1600 is the counter part. Decoder 160
0 (ie, shifter, R code decoder,
The probability estimation module) can be shared by all the counters, and can access a single memory 1601.

The memory 1601 is connected to the decoder 1602 and supplies data to the decoder 1602. Memory 1
The number of connection lines between 601 and decoder 1602 is equal to or greater than the number of bits of the largest codeword. In other words, the memory width is greater than or equal to the maximum number of bits of the run-length codeword. Note that if the decoder 1602 operates at a speed similar to the memory bandwidth and probability estimation module, multiple bitstream generators are not required. Even so, multiple counters (eg, counter 1604) may be provided to provide data to context model 1608.
To 1607) are used.

Each of counters 1604 to 1607 outputs decoded data. In the present invention, the counter 1
Since 604 to 1607 do not stop, decoded data is always supplied to the context model 1608. As long as the memory address generated by address generator 1603 is known, the entire decoder 1600 can be pipelined. context·
If a counter is selected by the model 1608, its count value may be obsolete. The context model 1608 can select one counter three times in a row and cause the counter to select the decoder 1602 three times in a row. In the presently preferred embodiment, the request from context model 1608 is only once per cycle, the decoding operation is performed only once per cycle, and the memory access occurs only once per cycle. . Thus, if the coder of the present invention has a reserve of count values in the FIFO (i.e., each counter has at least two count values), the context model 1608 will never be paused. .

To ensure that the context model 1608 is non-pause, the present invention first decodes some run-length, eg, three run-lengths, for each counter in the decoder. . By doing so, the memory address generator 1603
Can start capturing data for the pipeline. Upon completion of this operation, by the time the context model 1608 has begun a counter selection operation since some run count values have been obtained. By the time the above initial count value is used up, other count values have been decoded. In this way, the context
Model 1608 never sleeps.

Since the context model request is made once per cycle, the final context access can access the memory 1601 and the decoder 1602. Utilizing one or two latches as small FIFOs (first-in / first-out) for buffering the input of the counter eliminates speed limitations because memory access and decoding can be pipelined.

The use of parallelism in a non-interleaved channel decoder reduces the overhead of the pipeline stage of the bitstream generator and removes the speed limit of the overall device. In comparison, devices that do not utilize a parallel counter require one memory word for each bin to store the current count value. Due to memory speed limitations, the time to read-modify-write the count value is
This will have a negative effect on the overall speed of the device.

The overall speed of the device is limited by the context model and / or the memory access time for storing coded data. To make full use of parallelism and increase device speed, at least context
The model, and possibly the entire decoder, must also be operated in parallel. However, the parallelization of the bitstream generator described here makes it possible to realize a coder faster than the current state of the art.

Interleave Parallel Decoding Device The present invention also provides an interleave decoding device for decoding compressed data in parallel. The data is segmented into independent streams by context bin, context class or probability class and then coded as described above. These streams can be distributed to the decoder in parallel by probability class (as in the multi-channel coder described above), or they can be distributed as fully concatenated files (non-interleaved channel As with the coder). However, it should be noted that a parallel decoder needs the data of these streams in a continuous, inevitable order. The order in which the decoder needs the coded data is not simple, but not random. As with the other methods, the coded data can be interleaved into a single stream by arranging the codewords in this order at the encoder rather than at the decoder.

When this interleaving ordering is performed on a variable-length codeword, the code stream must be input to a single shifter that shifts out the correct number of bits to the decoder. This will probably require a slow feedback loop. To avoid that, the codeword of each coded data stream (eg, for each context) is packed into fixed length words. Thus, each decoder receives the entire fixed length word of a single coded data stream. The decoding is performed in parallel because the variable length codeword is shifted out at each decoder.

The interleaved parallel architecture is shown in FIG.
0 is shown. In FIG. 20, the interleaved parallel architecture includes an encoder 1713 that receives data and generates coded data, a FIFO 170
1. Decoder 1711 and context model 171
Consists of zero. The input of the FIFO 1701 is connected to the encoded input data. The output of the FIFO 1701 is connected to bit stream generators 1702 to 1705 of the decoder 1711. The bitstream generators 1702-1705 are connected to probability estimation modules (PEMs) 1706-1709, respectively. Each of the PEMs 1706 to 1709 is
It is connected to a context model 1710 that sends out decoded output data. A request signal 1712 is output from the context model 1710 to the decoder 1711. A request signal 1713 is also output from the decoder 1711, and the signal is connected to the FIFO 1701 to request the next encoded data.

The coded data is buffered in the FIFO 1701. In the present invention, the FIFO 170
The size of 1 may be arbitrary. In the currently preferred embodiment, F
IFO 1701 is smaller than the entire coded file. F
The output of IFO 1701 is sent to a decoder consisting of a bitstream generator and a probability estimation machine. F
The IFO 1701 is requested to send data by a request signal 1713. However, FIFO 1701
Does not know in advance which bitstream generator has requested the data-only the data is provided to the requesting bitstream generator. The context model 1710 is a PEM 17
Via 06 to 1709, it requests decoded data from the bit stream generators 1702 to 1705 in a known order. As a result, the bitstream data 1702-1705 requires coded data in the necessary order.

If the CM 1710 operates at a higher speed than the data supply speed of the FIFO 1701, the FIFO 1
701 must be able to accommodate multiple (ie, parallel) requests to provide data to the bitstream generator. To handle parallel requests, F
IFO 1701 is required to accept multiple requests and is required to manage the request source to ensure that the requested data is sent to the correct bitstream generator.

In the currently preferred embodiment, the context
Model 1710 operates faster than FIFO 1701. When the FIFO empties, the entire encoder and context model stop until the next data arrives.

FIG. 21 is a block diagram of an interleaved parallel architecture for processing probability classes in parallel.
In FIG. 21, this interleaved parallel architecture is an encoder 1 that receives and encodes data.
808, a FIFO 1801, and a decoder 1800. The decoder 1800 includes a bitstream generator 1802-1805 and a probability estimation module (PE
M) / context module 1806.
The input of the FIFO 1801 is connected to the encoded input data. The output of the FIFO 1801 is
800 bitstream generators 1802-1
805. The bit stream generators 1802-1805 are connected to a PEM / CM 1806 that sends out decoded output data. A request signal 1807 is output from the decoder 1800, which is used to request the next encoded data.
Connected to IFO 1801. Note that the actual number of bitstream generators will increase or decrease.

The coded data is buffered in the FIFO 1801 and supplied to the bit stream generators 1802 to 1805 in response to the request signal 1807 as in the case of the FIFO 1701 in FIG. Bitstream generators 1802-18
05 decodes the encoded data. PEM /
The CM 1806 requests decoded data from the bitstream generators 1802-1805 in a known order according to the probability class, so that the bitstream generators 1802-1805 request data in the necessary order. The PEM / CM 1806 operates in the same manner as the PEM / CM in FIG.

To take advantage of the speed of operation of the context model, a series of registers can be used to provide data to the bitstream generator, as opposed to a FIFO. One embodiment of such a scheme is shown in FIG. FIG. 22 shows an encoder 1912 that receives and encodes data. The coded data is sent to the channel distribution unit (channel delive
ry) Received in 1911. FIFO 1901 is connected to receive coded data input. FIFO1
901 is controlled by control logic (not shown). FIFO 1901 supplies coded data to registers 1902 to 1905 connected in series. The coded data output from the FIFO 1901 is connected to one input of a register 1902. Register 19
02 is output to both the register 1903 and the bitstream generator 1909. Register 1903
Are connected to receive the coded data output from the register 1902 and output it to the register 1904 and the bitstream generator 1908. Register 1904 is connected to receive coded data from register 1903 and output it to register 1905 and bitstream generator 1907. Register 1905 outputs the coded data to bitstream generator 1906. Bitstream generators 1906-190
Reference numeral 9 is connected to a probability estimation module (PEM) / context model (CM) 1910 that outputs decoded data. Bitstream generator 19
06 to 1909 are registers 1905 to 19, respectively.
02 is also connected. That is, the register 1902
1905 supply encoded data to the bitstream generator in response to a request signal therefrom. In addition, bit stream
The generators 1906 to 1909 and the PEM / CM operate in the same way as some components in FIG.

The FIFO 1901 includes registers 1902 to
The encoded data via 1905
Supply to generators 1906 to 1909. But,
Since the registers 1902 to 1905 are connected in series, data is sequentially supplied from the register 1902 to the register 1905. When the coded data in one register is used, the coded data output from the lower register gives the next coded data.
If the context model can request decoded data faster than the FIFO can supply the data,
Multiple bitstream generators may request data during the same memory cycle. The register system shown in FIG. 22 can simultaneously respond to a plurality of requests for coded data. For example, register 19
When the data in register 04 and register 1905 are used, the coded data in registers 1903 and 1902 are shifted upward (when requested), and then the code to be decoded by bitstream generators 1906 and 1907. Data. Also,
New data is transferred from FIFO1901 to register 190.
3,1902.

It should be noted that under such a configuration, there is a necessary order in which the coded data is shifted into the register associated with the correct bitstream generator. Thus, by arranging the coded data in the order in which it is used, all of the registers 1902-1905 contain the coded data after each request for the next data. With this type of configuration, N accesses can be generated simultaneously every N cycles. For example, two bitstream generators can be accessed simultaneously every two cycles, and four bitstream generators can be accessed simultaneously every four cycles.

An additional control for such interleaving devices is to determine which bitstream generator has requested the next coded data and to register 1902 after each memory (ie FIFO) cycle.
This is a control for judging the shift amount and judging the position where the shift is stopped so that each of the data Nos. To 1905 contains data. Note that each of the registers 1902 to 1905 can be a FIFO, but in this case, an additional control circuit will be required.

<Encoding for Interleaving Apparatus> The main difference between an encoder and a decoder is that the encoder must wait for transmission of a code until the end of the run while counting data of one run. . The decoder needs a codeword at the beginning of the run, after which decoding and sending out the valid bits are possible. Such a discrepancy between the requirements of the decoder and the capabilities of the encoder does not matter if there is only one context bin. If there are multiple context bins, the data stream is split into multiple context bin data streams. The data encoding speed differs for each stream. When this is combined into a single stream, the offset must be corrected somewhat with an encoder. For example, if the context bin is one encoder encounters the first bit of a very long run, the final generated codeword for this run is the code that the decoder next needs. But,
Before the run of the context bin ends, a number of other codewords may be generated by the coder of the other context bin. These other codewords must be stored until after the first context bin run and the coder sends out the codeword.

A problem arises in that the amount of memory required to store a codeword generated by another coder is not known. Therefore, the device is limited by the memory. When implemented with non-real-time software, computer memory is typically large and therefore less of a problem. In FIG. 23, this memory storage is shown as a buffer combined with bit packing. Note that this can be achieved using only one buffer or using another memory configuration.

As described above, the variable length codeword of each context bin is packed into a fixed word size. Otherwise, the decoder would have to have a feedback loop to check the codeword length, which does not fit the purpose of a parallel architecture. Another problem is creating a state machine to determine the correct order. Determining the order in which data should be decoded is complex and there are various methods. One way to determine this order is to have a copy of the decoder (a "snooper" decoder) in the encoder. This "snooper" decoder decodes data immediately after encoding. Thus, the codeword request leaving this "snooper" decoder is exactly the same as for the actual decoder at the other end of the channel.

In the present invention, the encoder encodes all data and the context bins are bit packed. The decoder then requests the codewords in some order, which order is used to correctly generate the coded data stream.

FIG. 16 does not show details of the encoder block. The encoder encodes each bin by arranging the original data into context bins and ordering the outputs in the proper order. One embodiment of the encoder of the present invention is shown in FIG. Currently, encoding is performed in software in a non-real-time, serial stream, memory-centric manner, but the same block configuration can be described by a hardware configuration.

Referring to FIG. The encoder 2000 includes a context model 2001, encoding / probability estimation modules 2002 to 2005, and a bit pack (bit pa).
ck) Buffers 2006 to 2009 and ordered block 2
010. Context model 2001
Receives a data input stream and
Binary data encoding / probability estimation module 2
002 to 2005 are connected. Each of the encoding / probability estimation modules 2002-2005 is connected to receive and encode a separate context data stream. The outputs of the encoding / probability estimation modules 2002-2005 are:
The bit pack buffers are connected to bit pack buffers 2006 to 2009, respectively, where encoded data is stored. The outputs of the bit pack buffers 2006-2009 are connected to a sequence block 2010, which outputs an ordered compressed codestream.

FIG. 24 shows a block diagram of the snooper decoder of the present invention which realizes the sequential block shown in FIG. In FIG. 24, a snooper decoder 210
0 is shown connected to the bit pack buffers 2101-2103. Although only three bit pack buffers are shown, more or less bit pack buffers may be used. Bit pack buffers 2101 to 2103 output the encoded data to the snooper decoder.

In the currently preferred embodiment, the snooper decoder includes a decoder data request arbitrator 21.
04, decoders 2105 to 2107, and a context model 2108. Although only three decoders are shown, any number of decoders can be used. Outputs of the bit pack buffers 2101 to 2103 are connected to a decoder data request arbitration unit 2104. The decoders 2105 to 2107 are connected to request the arbitration unit 2104 for data. The requested data is also output from the arbitration unit 2104 as an ordered compressed code stream. Decoders 2105-21
07 is connected to a context model 2108, which is a decoder 2105-2.
The data to be requested is instructed to 107. The context model 2108 outputs decoded data,
It is not used.

The context model 2108 requests data from the decoders 2105 to 2107, and the data is fetched from the bit pack buffer. The arbitration unit 2104 arbitrates the duplicate request, and
When data is sent to one of .about.2107, the data is output as ordered compressed data. Note that the snooper / decoder 2100 includes decoders 2105 to 210
When two or more of the data are lost at the same time (output in parallel from the context model), an arbitration unit 2104 is provided to determine which decoder should receive the data first. The context model also reintegrates the context stream into the original data stream and determines the order.

In the case of a duplex system, such as a facsimile machine, little or no additional hardware is required for the function of the snooper decoder since the decoder is an integral part of the system.

FIG. 25 shows another embodiment of the encoder of the present invention.
Is shown in In FIG. 25, an encoder 2200
Is a context model (CM) / probability estimation module (PEM) 2201, a bit pack buffer 2202
2205, and an order generator 2206. CM
/ PEM 2201 is connected to receive a data input stream and output data according to a probability class (P class) to bit pack buffers 2202 to 2205, which store the encoded data. Bit pack buffers 2202 to 220
5 stores the encoded data and outputs the data to the order generator 2206 in response to a subsequent request. An order generator 2206 is connected to receive the data from the bit pack buffers 2202-2206 and output an ordered compressed codestream.

<Application of Apparatus> One of the effects obtained by all compression apparatuses is a reduction in the storage capacity required for collecting data. The parallel device of the present invention can be used in any application where a lossless binary coding device is currently utilized. Such applications include facsimile compression, database compression, bitmap graphic image compression, and conversion coefficient compression in image compression standards such as JPEG and MPEG. The present invention can be realized by a small amount of efficient hardware or can be realized by software at a considerably high speed, and the present invention is effective even in applications that do not require high speed.

The true effects of the present invention are:
In particular, a very high-speed operation is possible in the case of decoding. Therefore, the present invention can fully utilize wide-area high-speed channels such as high-speed computer networks, satellite broadcast channels, and terrestrial broadcast channels. FIG. 26 illustrates such a system.
Broadcast data or high-speed computer network data is provided to a decoding device 2301, which decodes the data in parallel and sends out output data. Current hardware entropy coders (eg, Q coders) reduce the throughput of these systems. All of these systems are very costly designs to get high bandwidth. It is unproductive to keep the throughput reduced by the decoder. The parallel device of the present invention
Although it is possible to cope with these high bandwidths, it is not only that, but the data can be transmitted in a compressed form, so that the effective bandwidth is increased.

The parallel device of the present invention can be used for ISDN, CD-R
It can also be used to get higher effective bandwidth from medium speed channels like OM, SCSI. Such a bandwidth matching system is shown in FIG. C
Data from a D-ROM, Ethernet, small computer standard interface (SCSI), or similar source is connected to a decoding device 2401, which receives, decodes, and outputs the data. These channels are faster than some current coder. These channels are often used for services of data sources that require higher bandwidth than their own. For example, a real-time video system or a computer-based multimedia system. The device of the present invention can play a role in bandwidth matching.

The apparatus of the present invention is most suitable for the entropy coder of a real-time video system such as the latest high definition television (HDTV) or the MPEG video standard. Such a system is shown in FIG. FIG.
At 8, the real-time video system has a decoding device 2501 connected to the compressed image data. Decoding device 2501 decodes the data and outputs it to lossy decoder 2502. The lossy decoder 2502 is a part of conversion, color conversion and sub-sampling of, for example, an HDTV or MPEG decoder. Monitor 2503 is a television or video monitor.

[0153]

As is apparent from the above detailed description,
According to the present invention, extremely high-speed decoding is enabled by parallel processing. A method and apparatus for performing high-speed decoding by parallel processing of a plurality of context bins can be realized. A method and apparatus for performing high-speed decoding by parallel processing of a plurality of probability classes can be realized. High-speed decoding can be performed by parallel processing using a simple decoder that can be duplicated at low cost in an integrated circuit. A large low-speed feedback loop, which has been one of the bottlenecks in increasing the speed of the conventional decoding device, can be eliminated. Using a simple code, decoding efficiency can be improved, and hardware of the decoding device can be simplified and speeded up. The hardware cost of the probability estimation module can be reduced.
A high-speed decoding device using a pipeline technique can be realized. A method and apparatus for performing high-speed encoding by parallel processing can be realized. An encoding device suitable for the purpose of parallel decoding that generates a coded stream in which variable-length codewords are packed into a fixed word size can be realized. By providing the snooper decoder, it is possible to realize an encoding device suitable for the purpose of parallel decoding, which rapidly generates an encoded data stream in which code words of context bins are arranged in the order required on the decoder side. An encoding device suitable for use in a duplex system such as a facsimile can be realized. A decoding device optimal for use in a high-speed computer network or the like can be realized. Many effects can be obtained, such as realizing a decoding device optimal for the entropy coder section of the real-time video system.

[Brief description of the drawings]

FIG. 1 is a block diagram showing a conventional binary entropy encoder and decoder.

FIG. 2 is a block diagram of a conventional decoder.

FIG. 3 is a block diagram of a decoder according to the present invention.

FIG. 4 is a block diagram of the decoder of the present invention for processing context bins in parallel.

FIG. 5 is a block diagram of a decoder of the present invention that processes probability classes in parallel.

FIG. 6 is a diagram illustrating an example of a probability estimation table and a bit stream generator for an R coder according to the present invention.

FIG. 7 is a graph of coding efficiency versus MPS probability.

FIG. 8 is a block diagram of an R coder decompression device of the present invention.

FIG. 9 is a block diagram of an example of an R coder according to the present invention.

FIG. 10 is a block diagram of one R coder in the present invention.

FIG. 11 is a circuit diagram illustrating an example of a circuit configuration of control logic of an R coder according to the present invention.

FIG. 12 is a circuit diagram showing an example of a circuit configuration of a PEM for an R coder.

FIG. 13 is a circuit diagram showing an example of a circuit configuration of a shifter, a decoder, and a counter of the R coder.

FIG. 14 is a block diagram illustrating a non-interleaved, multi-channel parallel architecture.

FIG. 15 is a block diagram illustrating a non-interleaved, multi-channel parallel decoding architecture.

FIG. 16 is a block diagram illustrating a non-interleaved single channel parallel architecture.

FIG. 17 is a block diagram illustrating a non-interleaved single channel parallel decoding architecture.

FIG. 18 is a diagram showing an example of a concatenated code stream used in the present invention.

FIG. 19 is a block diagram illustrating a non-interleaved single channel parallel decoding architecture using an R coder.

FIG. 20 is a block diagram illustrating an example of an interleave / parallel decoding apparatus for processing a context bin according to the present invention;

FIG. 21 is a block diagram illustrating an example of an interleaved parallel decoding device that processes probability classes according to the present invention.

FIG. 22 is a block diagram of an interleaved parallel decoding device that supports a plurality of requests simultaneously.

FIG. 23 is a block diagram illustrating an example of a parallel decoding device according to the present invention.

FIG. 24 is a block diagram of an example of a snooper decoder according to the present invention.

FIG. 25 is a block diagram of an example of the parallel encoding architecture of the present invention.

FIG. 26 is a block diagram of a high bandwidth system using the present invention.

FIG. 27 is a block diagram of a bandwidth matching system using the present invention.

FIG. 28 is a block diagram of a real-time video device using the present invention.

[Explanation of symbols]

101, 104 Context model (CM) 102, 105 Probability estimation module (PEM) 103, 106 Bitstream generator (B
G) 201 input buffer 202 decoder 203 context model 204 input buffer 205 decoder 207 decode data memory 206 context model 221 channel control 222 to 224 bitstream generator (B
G) 225-227 Probability estimation module (PEM) 228 Context model (CM) 231 Channel control 232-234 Bit stream generator (B
G) 235 Probability estimation module (PEM) 236 Context model (CM) 501 R code decoder 502 Run counter 600 R code decoder 601 Shift block 602 Decode block 603 Run counter 604 Probability estimation module (PEM) 1101 Encoder 1102 １1105 Bitstream generator (BG) 1106 Probability estimation module (PEM) / context model (CM) 1107-1110 channels 1111 Decoders 1201-1204 channels 1205-1208 Bitstream generator (BG) 1209-1212 Probability estimation module ( PEM) 1213 Context Model (CM) 1214 Decoder 1215 Encoder 1300 Encoder 13 01 Decoder 1303 Memory / Memory Control 1304-1307 Bitstream Generator (BG) 1308 Probability Estimation Module (PEM) / Context Model (CM) 1401 Memory / Memory Control 1402-1405 Bitstream Generator (BG) 1406-1409 Probability Estimation Module (PEM) 1410 Context Model (CM) 1411 Decoder 1412 Encoder 1501-1503 Pointer 1504-1506 Context Bin Data 1600 Decoder 1601 Memory 1602 Decoder / Probability Estimation Module (PEM) 1603 Address Generator 1604-1607 Counter 1608 Context・ Model (CM) 1609 Encoder 1701 FI O 1702-1705 Bitstream Generator (BG) 1706-1709 Probability Estimation Module () 1710 Context Model (CM) 1711 Decoder 1713 Encoder 1800 Decoder 1801 FIFO 1802-1805 Bitstream Generator (BG) 1806 Probability Estimation Module / Context Model 1808 Encoder 1900 Decoder 1901 FIFO 1902-1905 Registers 1906-1909 Bitstream Generator (BG) 1910 Probability Estimation Module / Context Model 1911 Channel Distribution Unit 1912 Encoder 2000 Encoder 2001 Context Model 2002-2005 Encode PEM 2006- 2009 Bit Pack Buffer 2010 Order block 2100 Snooper decoder 2101 to 2103 Bit pack buffer 2104 Decoder data request arbitration unit 2105 to 2107 Decoder 2108 Context model 2200 Encoder 2201 Context model / probability estimation module 2202 to 2205 Bit pack buffer 2206 Order generator 2301 , 2401, 2501 Decoding device 2502 HDTV / MPEG lossy decoder 2503 Television / video monitor

──────────────────────────────────────────────────の Continued on the front page (51) Int.Cl. ⁷ Identification code FI H04N 7/30 H04N 7/133 Z (72) Inventor Martin Pi Beaurick United States 94025 Menlo Park Sand Hill Road 2882 Ricoh Corporation (56) References JP-A-61-84125 (JP, A) JP-A-63-299520 (JP, A) JP-A-6-104767 (JP, A) (58) Fields investigated (Int. ⁷ , DB name) H03M 7/40 G06F 5/00 H04N 1/41

Claims (72)

(57) [Claims] 1. A device for decompressing the data stream comprising a plurality of codewords, channel means for receiving a plurality of codewords of the data stream, and decode each codeword of said data stream And decoding means connected to the channel means for processing the context bins in parallel.
Data decompression device characterized by including means for performing
Place. 2. A data stream comprising a plurality of codewords.
Apparatus for decompressing a plurality of codewords of the data stream.
Channel means and each codeword of the data stream
A decoder connected to the channel means for coding
Comprising a loading means, because the decoding means for parallel processing the probability class
A data decompression device comprising: 3. The data decompression device according to claim 1,
The channel means comprises at least two data streams.
Data decompression device characterized by providing the game in parallel
Place. 4. A data decompression device according to claim 1,
And that the channel means comprises a plurality of channels.
Characteristic data decompression device. 5. A data decompression device according to claim 3, wherein
The channel means is a single non-interleaved channel
A data decompression device characterized by comprising: 6. A data decompression device according to claim 3, wherein
Whether the channel means is a single interleaved channel
A data decompression device characterized by comprising: 7. A data stream comprising a plurality of codewords.
Device for decompressing a data stream, comprising a plurality of codewords for receiving a plurality of codewords of the data stream.
Yaneru means, connected to said channel means, low in the data stream
Decoding at least two codewords simultaneously,
Decode Funding for outputting bits of data in parallel
Means for storing the decoded data, the decoding
Data storage means connected to the data storage means, and decodes the data from the data storage means.
Select the data record to be output in its original order.
A data decompression device comprising modeling means connected to storage means . 8. A data decompression device according to claim 7, wherein
Therefore, the decoding means comprises a plurality of decoders.
And a data decompression device. 9. A data decompression device according to claim 8, wherein
And each of the plurality of decoders has at least one
Decoding the data corresponding to the context bin
Allows codewords to run in parallel according to the context bin
A data decompression device characterized by being processed. 10. A data decompression device according to claim 9, wherein
And at least one of the plurality of decoders has a class
Decode data corresponding to the context bin
A data decompression device characterized by the above-mentioned. 11. A data decompression device according to claim 8, wherein
And each of the plurality of decoders has at least one
By decoding the data corresponding to the probability class
Codewords are decoded in parallel according to the probability class
A data decompression device characterized by the above-mentioned. 12. A data stream comprising a plurality of codewords.
Apparatus for decompressing a data stream for receiving a plurality of codewords of the data stream
Wherein said data stream is divided into a plurality of parallel data streams.
Channel control means, including means for providing as stream, codewords of each of the plurality of parallel data streams.
Code and generate decoded data that is decoded in parallel
One of the plurality of parallel data streams to
Multiple bitstream generators connected to each other
Data from the bit stream generator.
Select the data and output it in some inevitable order
Connected to the plurality of bitstream generators.
Data decompression apparatus, characterized by comprising the modeling means. 13. Each of said modeling means and said compound means.
Connected to one of a number of bitstream generators
For the plurality of bitstream generators
Add multiple probability estimators to provide probability estimates
Wherein each of the plurality of bitstream generators comprises
Associated with at least one context bin
This allows codewords in different context bins to be
According to the probability estimates received from multiple probability estimators
Decoding in parallel, and the modeling means
Selecting each of the rate estimating means in the necessary order and
Decoded data from the bitstream generator
13. The data according to claim 12, wherein the data is output.
Data extension device. 14. The modeling means and the plurality of bits
Connected to each of the stream generators
Probability estimation for multiple bitstream generators
Further comprising probability estimating means for providing a constant value, wherein each of the plurality of bitstream generators
By being associated with at least one probability class
Code words of different probability classes
Decoded in parallel according to the received probability estimates,
The modeling means is adapted to determine the necessary order with respect to the probability estimating means.
Providing the context with the plurality of bitstreams.
By selecting the data from the generator,
The rate estimating means includes a plurality of bit stream generators.
Selecting decoded data from the
The data decompression device according to claim 12, wherein 15. A data decompression device according to claim 12,
Memory means for storing the data stream , wherein the channel control means comprises:
Data corresponding to at least one context bin
Stream into the plurality of bitstream generators
The plurality of memory means and the plurality of
Connected to a bitstream generator
Data comprising at least one channel.
Data extension device. 16. A data decompression device according to claim 12, wherein
There are, the channel control means, memory means for storing said data stream, and
Data stream corresponding to at least one probability class
Each of the bitstream generators
The memory means and the plurality of bits providing for the
At least one connected to the stream generator
Data decompression device, comprising:
Place. 17. The data decompression device according to claim 12, wherein
And wherein the channel control means comprises : memory means for receiving the data stream, each of the plurality of bit stream generators comprising:
Connected to one another and the connected bitstream
Multiple channels that carry data to the Nerator, and
The data in the data stream from the memory means is
Means for sending to a number of channels
Data decompression device. 18. The data decompression device according to claim 12, wherein
And a code stream to which the data stream is connected.
And the channel control means comprises the connected code.
The appropriate part of the stream is
Means for sending to an appropriate one in the generator,
A data decompression device characterized by the above-mentioned. 19. A data decompression device according to claim 18, wherein
And the concatenated code stream is
Bin data and the data of each context bin
Consisting of multiple pointers to indicate the position of data
A data decompression device characterized by the above-mentioned. 20. The data decompression device according to claim 18, wherein
And the concatenated codestreams of each probability class
Data for each probability class
Of multiple pointers to indicate the position of the
Data decompression device. 21. A data decompression device according to claim 12,
And wherein the channel control means
To send the word to the appropriate bitstream generator.
A data decompression device, characterized in that the data decompression device includes means for executing the data decompression. 22. A data decompression device according to claim 12,
Wherein the channel control means includes a FIFO.
Data decompression device. 23. The data decompression device according to claim 12, wherein
There are, the channel control unit, receives the data stream, the data stream
Means for outputting in a predetermined order
And serially connected to data output from the memory means.
A plurality of register means, each of which comprises a plurality of bit
Connected to one of the
The stream to the relevant one of the stream generators.
Providing at least one codeword of the data stream,
Bit stream generator with at least two words
Making multiple data requests when used by data
Data can be shifted between the plurality of register means.
After each access, data is stored in all the register means.
The data stream is ordered so that it is
A data decompression device. 24. The data decompression device according to claim 23,
And the memory means comprises a FIFO.
Data decompression device. 25. The data decompression device according to claim 23,
And each of the register means comprises a FIFO.
And a data decompression device. 26. The plurality of bitstream generators.
At least two of the data are stored in the memory
Arbitrate access to the memory means when requesting
The multiple bitstream generators to
Characterized by further comprising connected arbitration means.
The data decompression device according to claim 12. 27. The data decompression device according to claim 12, wherein
And the plurality of bitstream generators are Rx
(k) Use code (where x and k are integers)
A data decompression device characterized by the above-mentioned. 28. A data decompression apparatus according to claim 12,
And the plurality of bitstream generators are R2
(k) code and Rn (k) code (where n is an integer)
A data decompression device characterized in that: 29. The data decompression device according to claim 28,
And n = 3, and the plurality of bit stream
Nerator uses R2 (k) and R3 (k) codes
A data decompression device characterized by the above-mentioned. 30. A data decompression device according to claim 12, wherein
And the plurality of bitstream generators are variable.
Data decompression characterized by using long-variable length codes
Long equipment. 31. A data decompression device according to claim 12,
And the plurality of bitstream generators
Decode probability classes in parallel using coded code
A data decompression device characterized in that the data is decompressed. 32. The data decompression device according to claim 12, wherein
And at least one of the codes is in the probability class
For one, the input data is decoded as shown below.
A data decompression device comprising a code to be executed. (Input Data) (decoding result) 0000 → 0 0001 → 1000 0010 → 1001 0011 → 11111 010 → 101 011 → 11101 100 → 110 101 → 11110 11 → 11100 33. The data decompression device according to claim 12,
And that of the plurality of bitstream generators
Each of which uses a binary arithmetic coder.
Data extension device. 34. A data stream comprising a plurality of codewords.
Providing a plurality of data streams from the data stream.
Steps, using a plurality of bit stream generator, said plurality
Decoding results according to the data in the number of data streams
In which the decoding result is reduced.
Both are generated at the same time, so the decoding result
Is a step that is generated in parallel, selects the decoding result, and decompresses the decompressed data in the necessary data order
Providing a plurality of data streams, comprising the steps of:
Multiple data for a particular context bin
Data decompression characterized by supplying data streams
Method. 35. A data stream comprising a plurality of codewords.
Providing a plurality of data streams from the data stream.
Steps, using a plurality of bit stream generator, said plurality
Decoding results according to the data in the number of data streams
In which the decoding result is reduced.
Both are generated at the same time, so the decoding result
Is a step that is generated in parallel, selects the decoding result, and decompresses the decompressed data in the necessary data order
Providing a plurality of data streams, comprising the steps of:
Multiple data lists for a particular probability class
A data decompression method characterized by generating a stream. 36. A data expansion method according to claim 34,35.
In the method, the step of selecting the decoding result
Including outputting the loaded data in parallel.
And a data decompression method. 37. A data stream comprising a plurality of codewords.
Providing a plurality of data streams , the method comprising :
Each channel has a specific context
Providing data corresponding to the bins, using a plurality of bitstream generators;
Decoding in response to the data in
And generating a result, the plurality of bit Tosutori
Each of the game generators
Provide the decoding result for the quist bin and
At least two of the number bitstream generators
Generating decoded results simultaneously, wherein the plurality of bitstream generators
Code for decoding each data stream.
Specifying a plurality of probability estimating means, and selecting the plurality of probability estimating means.
With an associated bitstream generator
Receives the generated decoding result and generates decompressed data
Data decompression method characterized by comprising that step. 38. A data stream comprising a plurality of codewords.
Providing a plurality of data streams , the method comprising :
Each of the channels corresponds to a particular probability class.
Providing corresponding data, using a plurality of bitstream generators,
Decoding results according to the data in the number of data streams
Generating the plurality of bit streams
Each of the generators has a fixed probability class.
A decoding result for the plurality of bits.
At least two of the stream generators
Generating a code result, wherein for the plurality of bitstream generators,
Code for decoding each data stream.
Specifying a plurality of probability estimating means, and selecting the plurality of probability estimating means.
Deco generated by the associated bitstream
Receiving data results and generating decompressed data . 39. A coded stream comprising a plurality of bits.
An apparatus for decoding a data stream, comprising: a key for receiving a plurality of bits of the data stream.
Yaneru means is connected to said channel means, at least the decoding
Will generate two streams of
Sea urchin, Dekode Ingu hand to decode the bits of said plurality of
Stage, data bits decoded by the decoding means
Connected to receive the decoding hand
To select the decoded data bits from the stage
More than one decoded data bit
A decoding device, comprising: modeling means for selecting from a trim . 40. A decoding device according to claim 39.
At each stream of said at least two streams
System corresponds to at least one context bin
A decoding device. 41. The decoding device according to claim 39.
At each stream of said at least two streams
That at least one probability class corresponds to
Characteristic decoding device. 42. Coded data comprising a plurality of bits
An apparatus for decoding a stream, comprising: a memo for receiving and storing the encoded data stream;
And the memory means.
Decoding method that receives and decodes decoded data
Stage, receives the decoded data from the decoding means
To generate the decoding result.
Therefore, at least two of them can be used simultaneously.
A plurality of counters each having a code result, and decoding results generated by the plurality of counters.
Connected to receive and select the plurality of counter means
And obtain the decoding result for generating decompressed data
A decoding unit for performing the decoding. 43. A decoding device according to claim 42.
Wherein the decoding means receives the coded data.
While simultaneously decoding the decoded data
Output to the counter means, in a pipeline system
A decoding device that operates. 44. Coded data consisting of a plurality of bits
An apparatus for decode the stream, note receiving and storing the coded data stream
Storage means, and coded data connected to the memory means.
Data that is received and decoded.
Judgment and the lowest probability symbol at the end of the run
Decoding means, the run length and the lowest probability from the decoding means.
Connected to receive the symbol determination result,
Generating at least two results.
Multiple cows, one with simultaneous available decode results
Counter means, and decode results generated by the plurality of counter means.
Connected to receive and select the plurality of counter means
And obtain the decoding result for generating decompressed data
A decoding unit for performing the decoding. 45. A data stream comprising a plurality of bits
An apparatus for encoding a beam, memory means for storing said data stream, coupled to said memory means, a plurality of the data streams
Providing a data stream of
Each of the data streams has a specific context
From the data of the data stream corresponding to the
Means for providing the plurality of data streams, connected to the means for providing the plurality of data streams,
Encoding the data in parallel, wherein
Is connected to one of the plurality of data streams.
A plurality of encoding means, encoded from the plurality of encoding means
Storage means connected to receive data, access to the storage means, access to the storage means,
Encoding means for generating an attached coded stream . 46. An encoding apparatus according to claim 45.
The ordering means requires the coded data.
Decoder means for determining the order of the compressed data.
An encoding device characterized by being recognized. 47. An encoding device according to claim 46.
The decoder means is connected to the storage means , and decodes data from the storage means.
Decoders to be loaded and for the plurality of decoders
Equipped with modeling means for providing context bins
And the plurality of decoders are provided by the modeling means.
Decoding data in a given order.
Encoding device. 48. Each of the plurality of decoders has an appropriate
The plurality of pins so as to receive the data of the context pin.
Further arbitration means for arbitrating data requests from the decoder
48. The encoding according to claim 47, comprising:
Device. 49. An encoding apparatus according to claim 45.
Wherein the storage means comprises a plurality of bit pack buffers.
An encoding device comprising: 50. An encoding apparatus according to claim 45.
Wherein the ordering means comprises an
Convert coded data into a single data sequence
Encoding means comprising means for performing
Place. 51. A data stream comprising a plurality of bits
An apparatus for encoding a beam, memory means for storing said data stream, coupled to said memory means, a plurality of the data streams
Providing a data stream of
Each of the data streams has a certain probability class
Including the data of the data stream corresponding to
Means for providing a data stream, connected to the means for providing the plurality of data streams;
Encoding the data in parallel, wherein
Is connected to one of the plurality of data streams.
That were encoded from a plurality of encoding means, said plurality of encoding means de
Storage means connected to receive data, the storage means being connected to the storage means, and
An ordering method that produces an attached coded stream
An encoding device comprising: a stage . 52. An encoding apparatus according to claim 51.
The ordering means requires the coded data.
Decoder means for determining the order of the compressed data.
An encoding device characterized by being recognized. 53. An encoding apparatus according to claim 52.
The decoder means is connected to the storage means , and decodes data from the storage means.
Decoders to be loaded and for the plurality of decoders
Equipped with modeling means for providing context bins
And wherein the plurality of decoders are provided by the modeling means.
Characterized by decoding data in a specified order.
Coding equipment. 54. An encoding apparatus according to claim 51.
Wherein the ordering means comprises an encoder from the storage means.
The loaded data into a single data sequence
Encoding means, comprising: 55. A data stream comprising a plurality of codewords.
An entropy decoder for decoding the data stream , wherein the bit stream generator receives the data stream.
Stage, and connected to the bitstream generating means,
Probability estimation for providing an estimate to the bitstream generation means
Setting means, wherein the bit stream generating means includes one for a plurality of values n.
Provided by the probability estimating means.
Each codeword in the data stream according to the estimated probability value
Generating decode results for
Tropy decoder. 56. The entropy deco according to claim 55.
In the decoder, the bit stream generating means is an R2 (k)
Code and Rn (k) code (where n is an integer)
And an entropy decoder. 57. An entropy deco according to claim 56.
N = 3, the bit stream generation
That the means uses R2 (k) and R3 (k) codes.
Characteristic entropy decoder. 58. An entropy deco according to claim 55.
The probability estimator includes a state machine
An entropy decoder. 59. The entropy deco according to claim 58.
The state machine has the same Rn (k) code.
An entry comprising at least two states
Ropy decoder. 60. An entropy deco according to claim 58.
At least one state change uses
Rn (k) code is not changed.
Entropy decoder. 61. The entropy deco according to claim 55.
, The probability estimating means switches between a positive state and a negative state.
Entropy characterized by including a state machine having
decoder. 62. The entropy deco according to claim 61.
The state machine determines that only its positive state or negative
It consists of a symmetric state table that stores only states.
Characteristic entropy decoder. 63. A data stream comprising a plurality of codewords.
An entropy decoder for decoding the data stream , wherein the bit stream generator receives the data stream.
Stage and the bit stream generating means,
To provide a probability estimate to the stream generator
A status table, the status table including a plurality of states, and
Each is associated with a single code and the multiple states
At least two states have the same code.
The bit stream generating means is the probability estimating means
Each symbol in the data stream according to their probability estimates.
The decoding result for the word is expressed as an Rn (k) code (where n and
k is an integer)
P-decoder. 64. A compressed data stream comprising a plurality of bits.
An apparatus for decoding the data stream , wherein the apparatus decodes the data stream;
Run length and lowest probability symbol depending on the bit
Decoder generating an indication of whether (LPS) has occurred
Means, connected to the decoder means, the LPS and the run length
Means for outputting data decoded according to the
And the decoder means includes a state table having a plurality of states.
Each of the states is associated with one code
And at least two states are the same code
Being related, the at least two states
Decoder means use the same code during transition between
A decoding device characterized by the above-mentioned. 65. A decoding device according to claim 64.
The code is an R2 (k) code and an Rn (k) code
(Where n is an integer)
Device. 66. A decoding apparatus according to claim 65.
, N = 3, and the code is an R2 (k) code and
Decoding characterized by consisting of R3 (k) code
apparatus. 67. A decoding apparatus according to claim 64.
Wherein the decoder means is connected to receive the data stream as a codeword.
Run-length decoding to determine the type of codeword
Means and run-length decoding means
Probabilistic estimating means connected to the run length decoding means.
Code for the run-length decode
Running means according to each codeword and the code.
And an indication of whether an LPS has occurred.
Decoding device to be featured. 68. Receiving said data stream,
The coded data that is properly aligned is stored in the run-length / deco
Further comprising shift means for outputting to the loading means.
68. The decoding of claim 67, wherein
apparatus. 69. A decoding device according to claim 68.
Wherein the shift means is provided from the probability estimation means.
It is, in response to a signal indicating the length of the previous codeword, coded
Providing data to the run-length decoding means.
A decoding device. 70. A decoding apparatus according to claim 64.
Wherein the counter means is provided to the decoding means.
On the other hand, includes means to indicate when the next codeword should be processed.
A decoding device characterized by the following: 71. A data stream comprising a plurality of codewords
Apparatus for decompressing a data stream, the method for providing a plurality of codewords of the data stream.
And the data means connected to the channel means and the channel means.
Decoding method for decoding each codeword in the stream
A decoding step, wherein the decoding means uses a code according to the probability class.
Decoding of the data stream using
And the plurality of decoders are cascaded, and
Each of the plurality of decoders is input by the preceding decoder
With the input of data corresponding to a certain probability class.
That is, each of the plurality of decoders has a certainty of the data input.
Output a code stream with a probability different from the
Data at one input in a chain of cascaded decoders
And propagate the data to the rest of the chain
Causes the data stream to be decoded
A data decompression device for obtaining data. 72. The data decompression device according to claim 71,
And at least one of the codes is of the probability class
For one, the input data is decoded as shown below
Data decompression device characterized by a code
Place. (Input data) (decoding result) 0000 → 00001 → 1000 0010 → 1001 0011 → 11111 010 → 101 011 → 11101 100 → 110 101 → 11110 11 → 11100