DE19900150B4 - Apparatus and method for encoding information with a finite state machine - Google Patents

Abstract

Method for coding input bits, comprising the following steps:
an interval is generated based on a Finisher (FSM) state, the interval including a pair of subintervals having endpoints, each endpoint represented by a binary value;
a subinterval from a subinterval pair is selected based on whether the input bit is in its most likely state;
zero or more bits are output corresponding to those bits which, when the binary values of the endpoints of the selected subinterval of the pair are compared with the binary values of the endpoints of the other subinterval of the pair, match in their value and their bit significance and those with the most significant bit begin and go to the first mismatched bit in an order decreasing in bit significance, but not including the first mismatched bit.

Description

The The present invention relates to the field of data coding and of data decoding; In particular, the present invention relates Data coding and data decoding with an encoder with a finite or finite state machine or with a "finite state machine" encoder.

The Data compression is a very useful Tool for saving and transferring greater Amounts of data. For example, the time to transfer an image is required, such as a fax transmission of a document, drastically reduced when using compression is used to reduce the number of bits needed to rebuild of the image are required.

at Some compression systems use an input file or record translated into a sequence of decisions, under the proviso a decision model. Each decision has an associated one Probability and, based on this probability, An output code is generated and attached to the compressed file. Around To realize this coding system, compression systems have three Parts: a decision model, a probability estimation method and a bitstream generator. The decision model receives the An initial data and translated the data into a set of decisions made by the compression system uses to encode the data. The decision model becomes typical referred to as a context model. The probability estimation method represents a method to obtain the probability estimate for the probability to develop each decision. The bitstream generator carries this final Bitstream encode to generate the output code that contains the represents a compressed data set or the compressed file. A Compression can be effective in the decision model and / or the Bit generator take place.

One binary Encoder represents a type of coding system that uses data as a sequence of binary decisions coded.

encoder with finite automata are binary Entropy encoders that are well known in the art. An encoder with a finite state machine (hereinafter called "FSM encoder") is a lossless binary multicontext entropy coder. Finite automata are used both for biter production (production of bitstreams resulting bits with known or assumed probabilities) as well as the probability estimate (estimation of probabilities based on past data from the same context). While of coding, the FSM encoder takes a number of bits with associated ones Contexts and generates a coded bitstream representing those bits and with as little data as possible. During decoding takes the FSM encoder the encoded bitstream and the sequence of contexts and generates the original sequence of bits. An example of this is in U.S. Patent No. 5,272,478 A, entitled "Method and Apparatus for Entropy Encoding ", and that was issued on 21 December 1993. It will as well See U.S. Patent No. 5,475,388 A, entitled "Method and Apparatus for Using Finite State Machines to Perform Channel Modulation and Error Correction and Entropy Coding ", published on December 12, 1995 has been.

Binary entropy coders can is used as the lossless coding section of image compression systems become. they allow the best possible Compression by allowing symbols with a probability greater than 50%, and by changing contexts (changing Probability estimates) is allowed, independently for each data bits to be compressed. Other binary entropy coders are the IBM Q Encoder, the IBM / Mitsubishi QM Encoder, and the ABS Encoder in U.S. Patent No. 5,381,145 A entitled "Method and Apparatus for Parallel Encoding and Decoding of Data "and published on 10 January 1995 and U.S. Patent No. 5,583,500 A are described in U.S. Patent No. 5,583,500 the title is "Method and Apparatus for Parallel Encoding and Decoding of Data "and published on 10 January 1996 has been.

Of the FSM encoder is relatively fast and easy in terms of software to realize. The FSM encoder is currently being used in image compression systems which are based on reversible wavelets and that of the applicant the present invention for standardization or for a standard has proposed.

An FSM encoder hardware is described. In one embodiment, the present invention provides a method of encoding that includes generating an interval based on a finite state machine (FSM) state (hereinafter "finite state machine") abbreviated by "FSM"). The interval includes a pair of subintervals having endpoints. The method also includes selecting a pair of subinterval pairs based on whether the input bit is in a most probable state, and further including outputting 0 or more bits corresponding to bits that match between endpoints of said one subinterval, which occur from the most significant bits to the first disagreeing bits between the endpoints of said one subinterval, but not up to and including the first disagreeing bit.

The The present invention will become more apparent when taken in conjunction with the accompanying drawings described. In this case, various embodiments are disclosed. Various Features of different embodiments can be combined with each other.

1A Figure 10 is a block diagram of one embodiment of a compression / decompression system.

1B shows an alternative embodiment of a system based on a FSM encoder.

2 Fig. 12 is a block diagram of one embodiment of a FSM encoder / decoder having a combined FSM encoding / decoding table having a separate probability estimate and bitmap lookup tables (a look-up table is hereinafter abbreviated to "LUT").

3 FIG. 12 is a block diagram of one embodiment of a single LUT FSM encoder / decoder that performs both likelihood estimation and bit generation.

4 Fig. 10 is a block diagram of one embodiment of the FSM encoder of the present invention.

5 is a block diagram of one embodiment of the pem_code unit ("pem" stands for "probability estimation machine").

6 FIG. 12 is a block diagram of one embodiment of the pem_expand unit ("expand" stands for "widening").

7 is a block diagram of one embodiment of the bit_generate unit ("generate" means "generate").

8th Figure 4 is a block diagram of one embodiment of the bit generation logic.

9 Figure 4 is a block diagram of one embodiment of the state expansion logic.

10 shows an exemplary alignment of wavelet coefficients.

11 Figure 10 is a block diagram of one embodiment of flushing logic for scavenging in one cycle.

12 Figure 12 shows a block diagram of a flush logic for "flushing" in a cycle with the codeword determined by the current interval.

13 Figure 10 is a block diagram of one embodiment of the codeword generation unit (cw_gen unit) of the bit generation logic of the encoder of the present invention.

14 Fig. 12 is a block diagram of one embodiment of the packing unit of the entropy encoder of the present invention.

14A Figure 12 is a block diagram of an alternative embodiment of the packing logic.

15 Figure 10 is a block diagram of one embodiment of the unpack unit.

16 is a control flowchart for coding.

17 is a control flowchart for decoding.

One Part of the disclosure of this patent document contains material that is under copyright protection. The copyright owner has no objection to facsimile reproduction of the patent document or the patent publication as disclosed in file or record of the Patent and Trademark Office are, keep but otherwise all copyright.

It An apparatus and method for FSM coding is described. In the following description, numerous details, e.g. Signal names, numbers of bits, etc. set forth. It is, however, for one Professional obvious that the present invention practiced without this specific detail can be. In other cases well-known structures and devices are shown in block diagram form, rather than in detail, a concealment of the present invention to avoid.

Certain Parts of the detailed descriptions given below be through algorithms and symbolic representations of operations expressed with data bits within a computer memory. These algorithmic descriptions and representations represent the means used by professionals in the field of data processing to convey the essence of their work to other professionals effectively. An algorithm is here and in general as a self-consistent Sequence of steps taken the one to a desired one Result leads. The steps are those that are physical manipulations of physical quantities make necessary. Usually but not necessarily these quantities take the form of electric or magnetic signals that are capable of, stored, transmitted, combined, compared or otherwise manipulated. It has yourself, mainly for reasons a common use, these signals have proved expedient as bits, values, elements, symbols, signs or characters, terms, To designate numbers or the like.

you However, keep in mind that all these or similar expressions be related to appropriate physical quantities and they are merely expedient designations represent that are applied to these quantities. So far it is not particularly emphasized elsewhere, as can be seen from the The following discussion becomes obvious are in the discussion terms used in the present invention, e.g. "Processing" or "calculating" or "determining" or "displaying" or "displaying" or the like, to understand that they on the effect and the processing of a computer system or a similar one electronic computing device can relate manipulating and transforming data that is considered to be physical (electronic) quantities represented within the registers and memory of the computer system and that are transformed into other data that are similar Way as physical quantities within the stores or registers or other information store of the computer system or the transmission or display devices.

As will be discussed below, the present invention relates on an apparatus to perform the operations in it. This Apparatus can for the required purpose can be built up specifically or he can include a general-purpose computer, selectively by a computer program is enabled or reconfigured in the computer is. Such a computer program can be read in a computer Memory are stored, such. on any record or Floppy disk, such as optical disks, magnetic disks, CD-ROMs, magneto-optical disks, read only memories (ROMs), memory with random access (RAMs), EPROMs, EEPROMs, magnetic or optical Cards or any type of medium used to store electronic Commands is suitable, the medium in particular with a computer system bus connected is. The algorithms presented herein relate not inherent on any particular computer or other device. Various general purpose devices can use Programs in accordance with the herein given Gauges or it may prove useful to build a more specialized apparatus that required Performs method steps. The required structure for A variety of these machines will become apparent from the following description result. additionally the present invention is not with reference to any certain programming language described. You will realize that a variety of programming languages can be used to teach the lessons of To realize the invention as described herein.

Overview of the present invention

The The present invention provides a FSM encoder and a coding system. based on FSM. They are for improved performance designed. Certain implementations are more suitable for a hardware implementation or a software realization or a combination of both.

Of the The FSM encoder of the present invention may be the entropy encoder which is used in a system that uses compression reversible wavelets used.

1A FIG. 12 is a block diagram of one embodiment of the compression / decompression system of the present invention. FIG. If you take reference 1A , so are image data 105 in the transformation facility 101 input or received for reversible wavelets. The transformation device 101 is with the context model 102 connected. The context model 102 is the same with the FSM encoder 103 connected to the header processing unit or header processing unit as well 104 connected is. The header processing unit 104 generates or receives coded data and signaling 108 , In one embodiment, the encoded data and the signaling include 108 a tagged code stream. Thus, in addition to communicating with the context model 102 the coded data of the FSM encoder 103 in a designated code stream generated / used by a header processing unit.

The basic operation of the system based on a FSM encoder and in the 1A is shown is as follows. During encoding, the input data (the image data 105 ) into a series of coefficients, each of which is several bits long, by the reversible forward wavelet transform of the transform means 101 converted. The bits of the coefficients of the transformation 101 be in context bins through the context model 102 divided. A probability estimate is stored for each context bin and by a probability estimator (PEM) within the FSM encoder 103 generated. In one embodiment, the estimate is a state that is similar to the value of a counter. In one embodiment, a bit of the state indicates whether the context bin is more likely to experience "0" or "1". This is called the more probable symbol or MPS. The other bits indicate the skew (PSTATE) of the MPS (as opposed to the Least Probable Symbol (LPS)), from near 50% to near 100%. In other words, the other bits indicate how likely it is that the MPS (as compared to the LPS) occurs.

FSM update rules which will be described below, specify what happens at a given condition and the occurrence of a 0 or a 1 do is more likely to use the PSTATE and the bit as context bin occurs, update. In one embodiment, the specify Only control 10 bits per context to follow the MPS and PSTATE or to keep up with it. In general, the rules that the PSTATE increases to some extent when an MPS occurs, and decreases to some extent when an LPS (least likely Symbol) occurs. In one embodiment becomes the skew in 16 probability classes (PCLASS). Each PCLASS will work for a range of probabilities used.

An FSM encoder 103 includes a finite state machine that encodes bits for each PCLASS. In order to code bits with probabilities greater than 50%, sometimes no bits are output and the information is temporarily stored in the state of this finite state machine. This entropy encoder state indicates which bit patterns can be output in the future so that bits that have not been output yet are correctly understood by the decoder.

In an alternative embodiment, such as those described in U.S. Pat 1B 3, a system based on an FSM encoder is shown for handling binary images. The binary image may include pixels that are divided into one of 1024 contexts that are based on binary values of adjacent pixels that have already been encoded. This is similar to the JBIG standard. 1B also includes two examples of contexts based on neighboring pixels.

Although the system is described in conjunction with a system based on reversible wavelets and a binary image compression system, the present invention is also applicable to other systems, such as non-wavelet-based systems. Next, though the 1A and 1B other data types and information may be used, such as sounds, text, computer-executable files and / or programs, and computer data files.

FSM encoder, the on based on a lookup table (LUT)

The present invention provides a software FSM encoder in which most of the FSM encoder is implemented as a lookup table or as multiple lookup tables (LUTs). The FSM encoder of the present invention may include, for example, LUTs with address inputs for the bit to be encoded (MPS or not), use the entropy encoder state and / or either the PCLASS or the PSTATE. In one embodiment, the PCLASS is a class that contains a current probability estimate for a binary decision and that is used for a range of probabilities. In one embodiment, the PSTATE is a probability estimate for a binary decision. The PCLASS and the PSTATE may correspond to probabilities for decisions other than binary decisions. In one embodiment, the address input for the bit to be encoded comprises 1 bit, for the entropy encoder state 6 bits, for the PCLASS 4 bits and for the PSTATE 9 bits. Using this address scheme, the total address size is 11 or 16 bits, which requires 2K or 64K LUT entries. Certain software implementations of the decoder portion of the FSM encoder use the encoded data as an input to the LUT (replacing the bit to be encoded). The encoded data can be 8 bits long. This increases the size of the LUT input address from 18 to 23 bits, which requires 256K or 8M LUT entries.

at an embodiment The present invention provides a single table of approximately the size of the coding table, described above for both coding and decoding used. In other words, separate tables for decoding and the coding is not needed. By Eliminate the big one Decoder LUT becomes a considerable Savings achieved.

2 FIG. 12 illustrates a block diagram of an FSM encoder / decoder having a combined FSM encode / decode table that uses separate and probabilistic estimate and bit generation LUTs, respectively. If you take reference 2 so is a context store 201 with a probability estimation table 202 , a multiplexer (MUX) 203 , a probability estimation logic 205 and a bit logic 204 connected. A probability estimation table 202 is as well with a mux 203 and a probability estimation logic 205 as well as with an entropy coding table 206 connected. The probability estimation logic 205 is on with a mux 203 , a bit logic 204 and a mux 209 connected. The entropy coding table 206 is with an entropy coding state 207 , a bit logic 204 and muxs 208 to 210 connected. The muxs 208 to 210 are with a bit logic 204 connected. The MUX 210 is also with an entropy coding state 207 connected.

Of the Operation during of coding is as follows. Details, such as the values of the LUTs are and how the probability logic works will be detailed described below. Bit widths are examples only group; in a software implementation these would typically open multiple of 8 bits or the word size of the computer on which the Software is running, be rounded up.

First, a context 211 used the context memory 201 to address. In response to the context 211 gives a context memory 201 a PSTATE (pstate 234 ) and an MPS (mps 215 ) out. The number of address bits (and memory locations) is application dependent. In one embodiment, 540 storage locations are used and the context memory 201 gives 9 bits for pstate 234 and 1 bit for mps 215 out. The 10-bit binary templates in 1B make 1024 memory locations necessary.

In response to the input of pstate 234 generates the probability estimation table 202 representing an LUT in one embodiment, a number of outputs. The probability estimation table 202 gives a probability estimate (pclass 219 ) out. The probability estimation table 202 Also issues the next Probability Estimate State, PSTATE, if an MPS occurred and an update of the PSTATE is required. The probability estimation table 202 also outputs the next PSTATE and whether the MPS should be toggled (from 0 to 1 or from 1 to 0) as shown by the toggle indication 218 is displayed if an LPS occurred and an update to the PSTATE is required. In one embodiment, the toggle indication includes 218 a 1-bit signal. The next probability estimation states that are output when an MPS occurred are referred to herein as pstate_mps 216 and, if an LPS occurred, as a pstate_lps 217 designated.

The pstate_mps 216 and the pstate_lps 217 along with the pstate 234 provide inputs to the MUX 203 dar. The probability estimation logic 215 gives a selection display (eg a signal or signals) 220 from among the probability estimation states leading to the MUX 203 are entered as the next probability estimate state, which is next_pstate 213 referred to as. In one embodiment, if the pstate 234 less or equal 214 is, the selection display 220 either a pstate_mps 216 if the input bit is an MPS or a pstate_lps 217 if the input bit is an LPS; if the pstate 234 greater than 214 and the bits are output, then the selection display selects 220 a pstate_mps 216 if the input bit is an MPS or a pstate_lps 217 off if the input bit is an LPS. On the other hand, if the pstate 234 greater than 214 is and not bits are output (coding) or consumed (decoding), then the selection display selects 220 a pstate 234 as next_pstate 213 out.

An entropy coding table 206 is connected to a pclass 219 and a FSM_state 236 from the entropy coding state memory 207 to recieve. In one embodiment, the entropy encoding state comprises 207 a register, another temporary buffer, a queue or storage mechanism. The entropy coding table 206 works as a bit-generating LUT. Initially, the entropy coding state is 0 , The entropy coding table 206 gives cw (codeword) _mps 227 and cw_lps 228 as code words (eg, bit patterns, tokens, symbols, etc.) as the coded data stream. cw_mps 227 and cw_lps 228 are the code words respectively outputted in response to an MPS and an LPS being input to the decoder. In one embodiment, cw_mps 227 and cw_lps 228 8-bit codewords.

Likewise, in response to their inputs, the entropy coding table returns 206 an indication of the number of bits in the output. In particular, the entropy coding table gives 206 size_mps 230 and size_lps 231 indicating the size of the codewords, that is, the number of bits respectively in cw_mps 227 and cw_lps 228 that contain the current bit pattern. In one embodiment, each size_mps 230 and size_lps 231 4 bits. The outputs of the entropy coder table 206 also include state_mps 233 indicating the next entropy encoder state if MPS is output and state_lps 234 indicating the next entropy encoder state if LPS is output. In one embodiment, both state_mps 233 as well as state_lps 234 6 bits.

The bit logic 204 compares the bit to be coded bit_in 222 with mps 215 and generates a probable display (eg a signal or signals) 223 if they are the same. On the other hand, if they are not the same, the probability indicator becomes 223 not claimed or activated.

If the probability display 223 true (that is, activated) becomes cw_mps 227 , size_mps 230 and state_mps 223 of muxs 208 to 210 respectively as output bitstream (output coded data 229 ), the size of the output (size 232 ) and the next FSM state 235 (which is loaded into the entropy coding state register). If the probability indicator is not true, cw_lps 228 , size_lps 231 and state_lps 234 of muxs 208 to 210 respectively issued.

The probability estimation logic 205 determined next_mps 212 and controls whether the next PSTATE (next_pstate 213 ) the current pstate 234 or one of the updated values (pstate_mps 216 or pstate_lps 217 ). In one embodiment, the probability estimation logic determines 205 next_mps 212 and should be toggled if an LPS occurs and if the PSTATE is 4 or less or equal 262 is. The controller to next_pstate 213 Selecting includes logic to display a selection 220 to generate an input of the MUX 203 select.

Next_mps 212 and next_pstate 213 will be in the place of the context memory 201 written addressed with an address based on the context 211 based. In one embodiment, the address is context 211 , where the data to be written is next_mps 212 and next-pstate 213 is.

Consequently leads up this way the LUT based encoder / decoder with the separate probability estimate and FSM bit generation encoding.

The encoder / decoder 200 on LUT basis decoded in a similar way. To begin decoding, the context memory becomes 201 through the context 211 addressed. In response to the context 211 wins the context memory 201 pstate 234 and MPS 215 again. Again, the number of address bits (and memory locations) depends on the application. In one embodiment, the context memory is 201 9 bits for pstate 234 and 1 bit for MPS 215 out.

In response to pstate 234 gives the probability estimation table 202 a probability estimate (pclass 219 ) out. In one embodiment, pclass 219 4 bits. The probability estimation table 202 Also issues the next PSTATE if an MPS occurs and a PSTATE update is required. In such a case, the next PSTATE comprises pstate_mps 216 , In one embodiment, a PSTATE update is required when the pstate 234 equal 214 or less or if the pstate 234 greater than 214 is, and bits are consumed. In one embodiment, pstate_mps 216 9 bits. The probability estimation table 202 also issues the next PSTATE and an indication that the MPS should be switched (from 0 to 1 or from 1 to 0) if an LPS occurs and the PSTATE update is required. In this case, the next PSTATE is pstate_lps 217 at shown and the indication whether the MPS should be switched, is indicated by the switching display (eg a signal or signals) 218 displayed. In one embodiment, pstate_lps 217 9 bits and the shift indicator 218 1 bit.

The entropy coding table 206 is connected to pclass 219 and the FSM state 236 (from the entropy coding state register 207 ) to recieve. In response to these inputs, the entropy coding table (bit generation LUT) 206 the current number of bits in cw_mps 227 and cw_lps 228 which contain the current bit pattern (eg codeword, token, symbol, etc.) along with size_mps 230 and size_lps 231 that is the size of the codewords cw_mps 227 and cw_lps 228 represent respectively. Cw mps 227 and cw_lps 228 are not used when decoded and do not need to be generated in an environment where only decodes are made. In one embodiment, these size indications are 4 bits at a time, while the code words are 8 bits long. The entropy coding table 206 also gives a state-mps 233 and a state-lps 234 as the next entropy states. It should be noted that the term "state" in this application stands for "state". In one embodiment, the next entropy encoder states comprise 6 bits. It is noteworthy that initially the entropy coding state is 0.

During this decoding process, the entropy coding table returns 206 also a splitting value 226 indicating a separation between the MPS and LPS bit patterns in the code stream. In one embodiment, the split value comprises 226 8 data bits. The entropy coding table 206 Also outputs an fps indication or a value 225 indicating whether bit patterns on the "00000000" side of the split value 226 show an MPS or not. In one embodiment, the fps value includes 225 a 1-bit value. The use of a splitting value 226 and an fps value 225 will be described in more detail below.

The bit logic 204 is connected to an fps value 225 and a split value 226 as well as mps 215 and encoded incoming data 221 to recieve. In response to these inputs, the bit logic compares 204 8 bits of bitstream (coded incoming data 221 or "coded_data_in") with the splitting value 226 and generates a probable display (eg a signal or signals) 223 by using the truth table shown in Table 1 below.

Table 1

Generation of a probable display when decoding

If the probability display 223 true is state_mps 223 of the MUX 210 as the next FSM state 235 output to the entropy coding state register 207 is loaded. If so, the probability display 223 true is size_mps 230 from the mux 209 to specify the number of bits of coded data used in decoding that are no longer needed. This allows the control of a shift register (not shown to avoid obfuscation of the invention) that causes a shift in the input coded data or coded_data_in 221 perform. Otherwise, the probability indicator 223 is not true, will size_lps 231 from the mux 209 (unused) and state_lps 234 from the mux 210 output. It is noteworthy that the output coded data or coded_data_out 229 not be used during decoding (that is, "do not worry about it").

Also, during decoding, the probability estimation logic determines 205 the next MPS value and returns it as next_mps 212 out. In one embodiment, next_mps 212 a 1-bit value. In one embodiment, the MPS value is toggled if an LPS occurs and if the PSTATE is equal to or less than 4 or equal 262 is. The probability estimation logic 205 also controls whether the next PSTATE is the current PSTATE, as by pstate 234 or one of the updated PSTATE values indicated by pstate_mps 216 or pstate_lps 217 are displayed. The probability estimation logic 205 controls this selection by using the selection display (eg a signal or signals) 220 to the mux 203 whose output is the next_pstate 213 is.

Both the next_mps 212 as well as the next_pstate 213 become the place of the context memory 201 written by the context 211 is addressed.

It is noteworthy that the context memory 201 the same input, whether encoded or decoded. It is equally noteworthy that the enable logic to enable the decode mode or the encoder mode is not shown, but would be apparent to one of ordinary skill in the art.

It is noteworthy that the encoder / decoder of the 2 similar to other encoders described herein, showing two separate data inputs, one for encoded data and another for uncoded data. In one embodiment, the encoder may receive these two types of data on the same input or port and use well known logic and / or one or more encode / decode control signals to notify the associated parts of the encoder or select logic which data type is currently from the encoder is received. Such an input structure may be incorporated in any embodiment described herein.

3 shows a FSM coder / decoder with a single LUT that performs both a likelihood estimation and a bit generation. Using a single LUT, in a software implementation, uses fewer operations (instructions) at the cost of a larger LUT.

During encoding, the operation is as follows. First, the context 211 used the context memory 201 to address. In response to the context 211 gives the context memory 201 pstate 234 and mps 215 out. The number of address bits (and memory locations) is application dependent. In one embodiment, 540 storage locations are used and the context memory 201 gives 9 bits for pstate 234 and 1 bit for mps 215 out.

In response to the input of pstate 234 gives a combined probability estimate and a FSM bit generation table 301 the next Probability Estimate State (PSTATE) if an MPS occurs, and an update of the PSTATE is required. In one embodiment, a PSTATE update is required if pstate 234 equal or less than 214 is or if pstate 234 greater than 214 and both bits are output (in the case of encoding or consumed in the case of decoding). In one embodiment, pstate_mps 216 9 bits. The combined table 202 also outputs the next PSTATE and whether the MPS should be toggled (from 0 to 1 or from 1 to 0) as shown by the toggle indication 218 is displayed if an LPS occurs and an update of the PSTATE is required. In one embodiment, the toggle indication includes 218 a 1-bit signal. The next probability estimation state includes a pstate_mps when an MPS occurs 216 or, if an LPS occurs, a pstate_lps 217 , The pstate_mps 216 and the pstate_lps 217 together with pstate 234 make entries to the MUX 203 dar. The probability estimation logic 205 gives a selection display (eg a signal or signals) 220 from among the probability estimation states on the inputs of the MUX 203 as the next probability estimation state next_pstate 213 selects.

The combined table 301 is connected to the FSM state 236 from the entropy coding state memory 207 to recieve. In one embodiment, the entropy encoding state comprises 207 a register, temporary buffer, queue, or other storage mechanism. The combined table 301 works as a literacy LTU. Initially, the entropy coding state is 0 and the. Entropiekodiertabelle 206 gives cw_mps 227 and cw_lps 228 as codewords (bit patterns) as the coded data stream. In one embodiment, cw_mps 227 and cw_lps 228 8-bit codewords. The combined table 301 also outputs an indication of the number of bits in the output. In particular, there is the combined table 301 size_mps 230 indicating the size of the codewords, that is, the number of bits in cw_mps 227 , and gives size_lps 231 indicating the size of the codewords, that is, the number of bits in cw_lps 228 , each containing the current bit pattern. In one embodiment, both size_mps 230 as well as size_lps 231 4 bits. The outputs of the combined table 301 also include state_mps 233 as well as state_lps 234 indicating the next entropy encoder states if an MPS or an LPS is output, respectively. In one embodiment, each includes state_mps 233 and state_lps 234 6 bits.

The bit logic 204 compares the bit to be coded, bit_in 222 , with mps 215 and activates the probability display 223 (Probably display 223 is true), if they are the same. On the other hand, if they are not equal, the probability indicator 223 not activated (Probable display 223 is not true).

If the probability display 223 true (that is, activated) will become respectively cw_mps 227 , size_mps 230 and state_mps 233 from the MUXs 208 to 210 to the bitstream and next_FSM_state 235 or next FSM state 235 (which in the entropy coding state register 207 loaded). Otherwise, cw_lps 228 , size_lps and state_lps 234 from the MUXs 208 to 210 respectively issued.

The probability estimation logic 205 determined next_mps 212 and controls whether the next PSTATE (next_pstate 213 ) the current pstate is as through pstate 234 is displayed, or one of the updated pstate_mps values 216 or pstate_lps 217 is. This control partially occurs by a selection display 220 for MUX 203 is generated as described above.

Next_mps 212 and next-pstate 213 become also the place of the context memory 201 written by the context 211 is addressed. That is, the address includes context 211 and the data to be written includes next_mps 212 and next_pstate 213 ,

The decoding mode of the 3 is similar. First, the context 211 used the context memory 201 to address. In response to the context 211 gives the context memory 201 pstate 234 and mps 215 out. The number of address bits (and memory locations) is application dependent. In one embodiment 540 Memory locations used. The context memory 201 gives 9 bits for pstate 234 and 1 bit for mps 215 out.

In response to the input of pstate 234 gives the combined table 301 the next probability estimate state PSTATE if an MPS occurs and an update of the PSTATE is required. Combined table 301 also outputs the next PSTATE and whether the MPS should be toggled (from 0 to 1 or 1 to 0), as by the toggle indication 218 is displayed if an LPS occurred and an update of the PSTATE is required. In one embodiment, the toggle indication includes 218 a 1-bit signal. The next probability estimation states include, if an MPS occurred, a pstate_mps 216 and when an LPS occurs, a pstate_lps 217 , Pstate_mps 216 and pstate_lps 217 be together with pstate 234 to the mux 203 entered. The probability estimation logic 205 gives a selection display 220 from among the probability estimation states at the inputs of MUX 203 as the next probability estimation state next_pstate 213 selects.

The FSM state 236 (from the entropy coding state register 207 ) is also an input to the combined table (LUT) 301 , In one embodiment, the entropy encoding state comprises 207 a register, temporary buffer, queue, or other storage mechanism. The combined table 301 works as a bit-generating LUT. Initially, the entropy coding state is 0. The combined table 301 gives cw_mps 227 and cw_lps 228 as codewords (bit patterns, tokens, symbols, etc.) as the coded data stream, depending on whether a probable display 223 is activated. In one embodiment, cw_mps 227 and cw_lps 228 8-bit codewords. In one embodiment that only decodes, cw_mps 227 and cw_lps 228 not required. The entropy coding table 206 also outputs an indication of the number of bits in the output. In particular, the entropy coding table gives 206 size_mps 230 and size_lps 231 which is the size of the codewords, that is, the number of bits in cw_mps 227 and cw_lps 228 containing the current bit patterns. In one embodiment, both size_mps 230 as well as size_lps 231 4 bits. The outputs of the combined table 301 also include state_mps 233 and state_lps 234 indicating the next entropy coder states if an MPS or an LPS is respectively output. In one embodiment, state_mps 233 and state_lps 234 6 bits.

The bit logic 204 of the 3 works in the same way as above in conjunction with 2 including the performance of decoding using a split value 226 and a fps ad 225 ,

If the probability display 223 true is state_mps 223 from MUX 210 as the next FSM state 235 output to the entropy coding state register 207 is loaded. Likewise, if the probability display 223 true is size_mps 230 from MUX 209 to specify the number of bits of coded data used in decoding and no longer needed the. This allows control of a shift register (not shown to avoid obfuscation of the invention) used in coded_data_in 221 makes a shift. Otherwise, if the probability display 223 is not true, respectively size_lps 231 and state_lps 234 of muxs 209 and 210 output. It is noteworthy that coded_data_out 229 is not used during decoding (that is, "you do not have to worry about it").

The probability estimation logic 205 determined next_mps 212 and controls if the next PSTATE next_pstate 213 the current PSTATE pstate 234 or one of the updated pstate_mps values 216 or pstate_lps 217 is. This control partially occurs by a selection display 220 for MUX 203 is generated as described above.

Next_mps 212 and next_pstate 213 become the place of the context memory 201 written by the context 211 is addressed. That is, the address includes context 211 and the data to be written includes next_mps 212 and next_pstate 213 , The LUTs, labeled "disconnected" or "separate," require a "pure probability estimate" LUT. The LUTs, referred to as "combined", do not require a "pure probability estimate" LUT.

The Table 2 summarizes the sizes of different LUTs together. This table shows the significant ones Savings when using a single encoding / decoding table with splitting points for encoding via the use of the decode-only tables containing the Use code stream as an input. If one refers to table 2, LUTs labeled "separate" require a "pure probability estimate" LUT, while LUTs, which are called "combined", do not need a "pure probability estimation" LUT.

Table 2 LUT sizes

Logic-based FSM encoder

at an embodiment the FSM encoder is implemented as hardware. The following description sets at least one such embodiment represents.

One some of the description will be given in an exemplary manner the behavior inspired Verilog hardware description language ("HDL" stands for "hardware description language").

Of the FSM encoder of the present invention reduces hardware costs. In one embodiment becomes the size of the entropy coder (bitmap) lookup table significantly reduced and in some embodiments, their size becomes substantially reduced to a minimum, with the redundant entries not be used. The logic generates all the information needed from the non-redundant LUT entries. The Codeword bit pattern and the lengths have to not generated by the LUT; they are generated by logic.

4 Fig. 10 is a block diagram of one embodiment of the FSM encoder of the present invention. The pem_expand unit 401 is with the pem_code unit 402 and the bit_generate_unit 403 connected. The pem_code unit 402 is the same with the bit_generate unit 403 connected. The packing unit 404 and the unpacking unit 405 are also with the bit_generate unit or bit generation unit 403 connected.

The pem_code unit 402 contains the context memory and performs several context probability estimates. The pem_expand unit 401 converts a PSTATE, such as a pstate 234 into the transformation that describes that PSTATE. The bit_generate unit 403 performs the conversion between uncoded bits and encoded bits in response to a PCLASS, such as pclass 219 by. The packing unit 404 combines codewords of variable length in bytes, when coded, during the unpacking unit 405 performs a variable length shift of the bytes of the coded data stream during decoding.

The inputs to the FSM encoder 400 are as follows.

bit_in 222 Input to the pem_code unit 402 which indicates the bit to be coded during encoding. data_in 221 Entry to the unpacking unit 405 indicating the coded data stream (bit stream during decoding). In one embodiment, the data is entered as one byte at a time, although other sizes may be used for the data entries. context 211 The context bin (context store address) associated with the pem_code unit 407 , is entered. clock 410 System clock input to the pem_code unit 402 , Packing unit 404 , bit_generate unit 403 and unpacking unit 405 , In one embodiment, the clock input 410 serve as an enable signal for the FSM encoder. release 414 Control indicator (eg a signal or signals) connected to the pem_code unit 402 , the bit_generate unit 403 , the packing unit 404 and the unpacking unit 405 to enable the encoding or decoding of a bit in the current clock cycle. Encode 415 control display (e.g., a signal) to encode or decode select. flush 413 Control display (eg a signal or signals) to "Flushen" or spaces at the end of the coding. The flush signal 413 causes a bit_generate unit 403 is vacated. "Flushing" refers to the operation that occurs at the end of the coding, where any information that is not yet available

reset 411 is outputted from the code stream. If the bit_generate unit 403 which has completed spaces becomes a bg_done_flush_signal 416 the packing unit 404 actively fed. In response to the bg_done_flush_signal 416 and the flush signal 413 The pack unit admits itself 404 itself. When the flushing is completed, the packing unit activates 404 the done_flush_signal 424 , Asynchronous initialization display (eg a signal or signals) for all memory elements (eg flip-flops) in the pem_code unit 402 , Packing unit 404 , bit_generate unit 403 and unpacking unit 405 , In response to that resetting 411 is disabled, the internal memories are cleared, including the context memories in the pem_code unit 402 ,

The Issues of the FSM encoder are as follows.

data_out 229 coded Data (bitstream) during of coding. In one embodiment the data is output byte by byte, although other sizes are for data output can be used. data_out_ready 423 Control indicator (eg a signal or signals) to indicate that data_out 229 is valid in the current clock cycle. "data_out_ready" stands for "data done". BIT_Out 224 decoded Bit. "bit_out" stands for "bit off". reset_done 421 Control indicator (eg, a signal) to indicate that a reset has been completed. In one embodiment, reset_done shows 421 indicates that all internal memories have been cleared due to deactivation of Reset.

done_flush 424 Control display (eg, a signal) to indicate that a flush has been completed after the flush signal 413 has been activated.

The pem_expand unit 401 creates a pclass 219 in response to the pstate 234 that from the pem_code unit 402 in response to the context 211 (which corresponds to it) is issued. The pem_expand unit 401 also generates an indication of the next PSTATE if an MPS is generated, called mps_pstate 216 and an indication of the next PSTATE if an MPS is generated, as by lps_pstate 217 is displayed (if the MPS is not switched). Both mps_pstate 216 as well as lps_pstate 217 represent PSTATEs that are used when a PSTATE update is required. The pem_expand unit 401 also generates a toggle indication 218 to indicate that the MPS should be toggled (from 0 to 1 or from 1 to 0).

The pem_expand unit 401 Also indicates whether updating the PSTATE is necessary, with an update display 412 is used. In one embodiment, if the update indicator (eg, a signal or signals) 412 is updated, the PSTATE updated, regardless of the MPS value. On the other hand, if an update message occurs 412 is not activated (that is, not true), updating only if a codeword is issued or used if the size of the codeword is greater than 0, or if the size of the output is less than zero. The size of the output is indicated by the size of the output code word, which in turn depends on the size of the display 418 from the biter generation logic 403 is shown.

In response to the pclass 219 leads the bit_generate unit 403 a bit generation and indicates whether the bit_in to be coded 222 the same as the MPS (eg MPS 520 ). This comparison occurs in the pem_code unit 402 on, the more detailed in 5 is described (eg comparator 512 ). If so, the probable indicator becomes 223 activated. In this case, the probable indicator shows 223 an encoding is likely and it will be in the pem_code unit 402 entered. In response to the probable message 223 sets the pem_code unit 402 BIT_Out 224 on the MPS, in case the probability display 223 true, otherwise on its complement, in the case where the probability indicator 223 is not true.

Based on the input signals, the pem_code unit generates 402 the next pstate, pstate 234 , and returns a decoded bit as bit_out 224 off when decoding. During decoding, however, bit_out becomes 224 ignored and the encode_likely ad ("Coding Probable Display") 422 is activated and by the bit_generate unit 403 receive. During decoding, the coding display becomes 415 not activated and the unpacking unit 405 unpacks the data bytes into variable length codewords, which are code stream 419 to the bit_generate unit 403 be issued. The unpacking unit 405 also gives a data_in_next signal 420 indicating that the current input of data_in 221 has been consumed and is requesting the next data bit.

In response to the code stream 419 and the pclass 219 bit_generate unit 403 generates a codeword 417 and a size indicator 418 , In response to the code words 417 and the size indicator 418 combines the packing unit 404 the variable length codewords in bytes.

In one embodiment, a bit_out_signal 424 can be used to update the context model to make coding and decoding equal. The packing unit 404 is not used when decoding.

each these units will be described in more detail below.

An exemplary Verilog HDL description of 4 as follows. Here and in the following "clock" stands for "clock";"reset" for "reset";"bit_in" for "bit on";"context" for "context";"data_in" for "data in";"encode" for "encode";"enable" for "enable";"flush" for "clearing";"reset_done" for "reset performed";"bit_out" for "bit off";"data_out" for "data out";"data_out_ready" for "data done";"data_innext" for "data next";"done_flush" for "finish cleaning";"codeword" for "codeword";"codestream" for "code stream";"size" for "size";"encode_likely" for "likely to encode";"likely" for "likely";"switch" for "toggle";"update" for "update";"in" for "on" and "out" for "off" respectively. The English terms have been retained in the following hardware description language in accordance with the usual use of English terms in a description language in the art.
// Copyright or Copyright 1997 RICOH
// FSM entropy coder (with probability estimation and context memory)

Multiple Context probability estimate

A block diagram of one embodiment of a pem_code unit 402 that contains the context memory and performs a multi-context probability estimation is in 5 shown.

If you take reference 5 so is the memory release logic 502 connected to an update screen 412 , a size indicator 418 and a release indicator 414 to recieve. In response to these inputs, the memory enable logic generates 502 an output connected to an input of an OR or OR gate 505 connected is. The reset indicator 411 is with the inputs of the reset counter 503 and the reset-done logic ("reset_done" logic) 504 , The output of the reset counter 503 is also with another input to the reset-performed logic 504 as well as with an input of the MUX 507 connected. The output of the reset performed logic 504 is a selection signal that comes with the MUXs 507 to 509 is connected and with a negating input of the OR gate logic 505 connected is. The output of the reset performed logic 504 is also performed as a reset-done display 521 output. The output of the OR gate 505 is with the write-enable input of the context memory 501 connected.

The muxs 507 - 509 are two input multiplexers. The other entrance of the MUX 507 is with the context 211 connected. The MUX 508 is connected to an initial pstate and the output of the mux 506 to recieve. In one embodiment, the initial is pstate 262 , Other initial pstates can be used. A selection of the initial pstates allows for faster adaptation. For further information on a more rapid adaptation, reference is made to U.S. Patent Application Serial No. 08 / 768,237, entitled "Method and Apparatus for Encoding and Decoding Data" filed December 17, 1996 and assigned to the assignee of the present invention and incorporated herein by reference.

The inputs of the MUX 506 are connected to mps_pstate 216 and lps_pstate 217 to receive, one of which in response to a probable indication 223 is selected, which is to the selection input MUX 506 connected. The inputs of MUX 509 are at the initialization value (eg 0 in one embodiment) and the output of the MPS update logic 510 connected. The inputs to the MPS update logic 510 are connected to a probable ad 223 , a switchover indicator 218 and an MPS 520 to receive that from the context store 501 is issued. The outputs of each mux 507 to 509 are to the inputs of a context memory 501 connected.

MPS 520 that from the context store 501 is output to an input of the comparator 511 and an input of the comparator 512 connected. The other input of the comparator 511 includes a probable message 223 while the other input to the comparator 512 a bit_in 222 includes. Although not shown to avoid obscuring the invention, the clock signal 510 is connected to all registers and counters.

The reset indicator 411 clears the reset_counter or reset counter 503 to 0. After the reset is deactivated, the reset_counter or reset counter is generated 503 Addresses for each context location in the context memory 501 and an initial PSTATE and an initial MPS are written to each context location. The initial values are written by MUXs 507 to 509 in conjunction with the reset_done_signal or reset-performed signal 421 that by the reset-performed logic 504 is spent. The reset_done_signal 421 acts as a selection signal for the MUXs 507 to 509 where context memory addresses from the reset counter 503 with the mux 507 , an initial pstate with mux 508 and an initial MPS with MUX 509 to be selected. In one embodiment, the initially PSTATE value 262 and the initial MPS value of 0 in memory locations in the context memory 501 written. After all memory locations have been initialized, the reset performed logic activates 504 the reset_done_display 421 ,

While coding is in a context memory 501 if its write enable (WE) input is activated. The WE input of the context memory 501 is activated when the output of the OR gate logic 509 is on high. The output of the OR gate logic 509 is high when the output of the reset-performed logic 504 is low, indicating that the reset has not been completed, or if the output of the memory enable logic 502 is on high.

If in the context memory 501 is written and not in reset, becomes a context model address of the context 211 via MUX 507 , the next probability estimation state via MUX 508 and the MPS via MUX 509 provided. The entrance of the MUX 508 is the output of the MUX 506 which is either a mps_pstate 216 or a lps_pstate 217 one of which is based on a probable indication 223 is selected. The MPS value from the MPS update logic 510 is the complement of the MPS value if the toggle indication 218 is activated and if an LPS occurs.

For the data stored in the context store 501 written, it is the PSTATE, by the probability display 223 and the MPS that is changed when the Likelihood indicator is selected 223 0 is and the shift indicator 218 1 is. In one embodiment, if the probability indication 223 true is, mux 506 mps_pstate 216 out; otherwise he gives lps_pstate 217 out. The output of the MPS update logic 510 includes MPS 520 , which according to the XOR or. according to the XOR function with the result of ANDing the shift indication 218 with the negation of the probability indicator 223 is linked.

The outputs of the context memory 501 are pstate 234 and MPS 520 , For encoding, the bit to be coded (bit_in 222 ) using the comparator 512 with MPS 520 compared to the encode_likely ad 422 to create. In one embodiment, the encode_likely ad becomes 422 generated by MPS 520 according to the XNOR function with the bit_in 222 is linked, where MPS 520 by a bit of the entry in the context model 501 is shown. It is noteworthy that the logic (not shown) for feeding back an encode_likely signal 422 to the probable message 223 is used. This will be described in more detail below. For decoding the probable display 223 using the comparator 511 with MPS 520 compared to the decoded bit (bit_out 224 ) to create. In one embodiment, bit_out becomes 224 through an XNOR link of the MPS 520 with the probability indicator 223 generated. The XNOR function is a synchronization of the MPS 520 with the probability indicator 223 equivalent to.

In 5 a single memory is used and the memory outputs the information for a single context. Parallel memories can be used to increase the speed. Often, the previously decoded bit affects the context for the next bit. This feedback to the context model, referred to herein as the bit-to-context delay, may limit the speed. One way to increase the speed is to have multiple memory outputs that correspond to the context bins used for both values of the previous bit. Memory access can be done in parallel (in a pipelined manner) to generate the previous bit. The correct context bin of the two can be multiplexed if the previous bit is known. Multiplexing is typically much faster than memory access. It can either be a single memory with multiple outputs or multiple memories can be used.

Pipelining memory accesses require that used information not be used when the same memory location is used twice in sequence (or used within a certain minimum number of consecutive clock cycles). If ever a Memory location is read for the first time, it should not be read again until the updated value is written back to memory. Instead of reading the memory for subsequent reads, the value that is already out of memory and undergoing processing should be used.

An exemplary Verilog HDL description that the 5 is as follows, the explanations given above on the Verilog description apply.
// Copyright or Copyright 1997 RICOH
// This is the multicontext part of the entropy coder.
// it contains the context store that stores pstates
// and manages using this store.

Probability state expansion

6 Figure 4 is a block diagram of one embodiment of the pem_expand unit 401 that the pstate 234 converted into the information that describes the PSTATE represented by its output.

If you take reference 6 so includes the probability state expansion unit 401 a pclass unit 601 , a mps_pstate 602 , a lps_pstate 603 , a switching unit 604 and an updating unit 605 , each of which is connected to a pstate 234 to receive and generate its corresponding output.

The pclass unit 601 generates pclass 219 in response to pstate 234 , In one embodiment, the probability estimate is a 4-bit value. In one embodiment, pstate suffices 234 from 0 to 268 and converts to a pclass that ranges from 0 to 15. An example of a code intended to perform this function is given below.

The MPS_pstate unit 602 generates a mps_pstate 216 (in response to pstate 234 ), which is the next PSTATE if an MPS occurs and the PSTATE is updated. In one embodiment, mps_pstate 216 9 bits. In one embodiment, the mps_state 216 who pstate 234 increased by an integer from 0 to 5 or decreased by 11 based on the value of the pstate 234 ,

The LPS_pstate unit 603 generates an lps_pstate 217 (in response to the pstate 234 ), which is the next PSTATE if an LPS occurs and the PSTATE is updated. In one embodiment, lps_pstate 217 9 bits. In one embodiment, lps_state 216 the pstate 234 increased by an integer 1, 3, or 5, or decreased by an integer ranging from -1 to -246, based on the value of the pstate 234 ,

The switching unit 604 activates the switching display 218 if the MPS is to be switched. In one embodiment, the toggle indication becomes 218 activated, if pstate 234 less than or equal to 4 or equal 262 is; otherwise the switchover indicator will be displayed 218 disabled. The switching indicator 218 indicates that the MPS stored in a context memory, such as the context memory 501 , should be changed if a bit occurs that is not likely. In one embodiment, the display includes 218 a signal.

In one embodiment, the update unit activates 605 the update display 412 . if the pstate is less than or equal to 214 is. It is noteworthy that the states are less than or equal to each other 214 are used for low offset (near 50%) states where a good probability estimate requires updating for each bit. States greater than 214 are used for high offset states where a good probability estimation using a small number of states does not require updating for each MPS. In other embodiments, a condition other than 214 its choice is based on the offset and whether the probability estimate is such that it requires an update for each bit. This can be a data-specific selection. The update display 412 indicates that an update of the context memory should be performed even if no coded data has been generated. In one embodiment, the update indicator includes 412 a signal. The probability estimate can be updated every bit. In an alternative embodiment, the probability estimate is updated each time bits are output (or consumed).

An exemplary Verilog HDL, the 6 corresponds, is given below. One embodiment of the probability estimation rules of the present invention will be described by this Verilog.
// Copyright or Copyright 1997 RICOH
// PEM - Probability Estimate
// given pstate, certain pclass and possible next pstates

bit generation

7 Figure 13 is a block diagram of one embodiment of the bit_generate unit 403, and performs the conversion between uncoded bits and coded bits. The bulk of the operation is through the biter generation logic 701 carried out.

If you take reference 7 that is the logic of generation 701 connected to a likely_in_display 709 , pclass 219 , a coding display (eg a signal or signals) 415 and a code stream 419 along with issues from the registers 702 to 704 Receive the fsm_state, a start value and a stop value, respectively. Each register 702 to 704 is with the clock 410 connected.

The fsm_state register 702 is the internal state of the FSM state machine. In one embodiment, the fsm_state register includes 702 a 6-bit register and is set to a predetermined state when reset is activated. In one embodiment, the predetermined state is 0. The fsm_state input 702 is updated with clock cycles when enable 415 is activated.

The start register 703 contains the smallest validity value that can be output to the code stream. In one embodiment, the start register includes 703 an 8-bit register. The start register 703 is set to a predetermined value when reset is activated and updated with clock cycles when the enable indication 415 is activated. In one embodiment, the predetermined value is 0.

The stop register 704 contains the largest valid value that can be output to the code stream. In one embodiment, the stop register comprises 704 an 8-bit register. The stop register 704 is set to a predetermined value when reset is activated and updated with clock cycles when the enable indication 415 is activated. In one embodiment, the stop register becomes 704 set to 11111111 ₂ when resetting.

In response to these inputs, the biter generation logic generates 701 a likely_out ad 223 , a sz ad 710 , a cw ad 711 , a next_stop value 712 , a next_start value 713 and a next_state 714 ,

The sz ad 710 is with an input of the mux 705 connected. The other entrance to MUX 705 is with the flush_sz indicator (eg a signal or signals) 715 connected. Similarly, MUX receives 706 cw 711 on an input and flush_cw 716 from the flush logic 707 on the other entrance.

In one embodiment, the bit_generate unit generates 403 Code words to clear at the end of coding. The flush signal 413 is connected to an input for both MUX 705 as well as 706 select. If the bit generator is not cleared and thus the flush signal 413 does not activate, enter the MUXs 705 to 706 a sz ad 710 as the size indicator 418 and cw 711 as the codeword 417 out. On the other hand, when the bit generator is cleared and the flush signal 413 is activated, the predefined codewords generated by flush_cw 716 be presented by MUX 706 as a codeword 417 with a size indicator output by the flush_sz indicator 715 is displayed as the size ("size") 418 is issued. It is noteworthy that the biter generation logic 701 and the flush logic 707 will be described in more detail below.

8th Figure 10 is a block diagram of one embodiment of bit generation logic 701 , If you take reference 8th so includes the biter generation logic 701 a state expansion unit 801 , a comparator 802 , a probable logic 803 , a multiplexer 804 and a codeword generation unit 805 , The state expansion logic 801 is connected to the fsm_state from the register 702 and pclass 219 to recieve. In response to these inputs, the state expansion unit generates 801 the first probable icon (fps) 821, split8 value 822 or split-8 value 822 together with the next states, in the case when an MPS or an LPS occurs, respectively as next_state mps 810 and next_state_lps 811 be designated. An embodiment of the state expansion logic 801 is in more detail in conjunction with 9 described.

The comparator 802 is connected to split8 value 822 and the code stream 419 and, in response, generates a top_split signal 823 , In one embodiment, if the code stream 419 greater than split8 value 822 is the top_split signal 823 activated (eg 1); on the other hand, if the code stream 419 smaller than split8 value 822 , the top_split signal 823 not activated (eg 0).

The probability logic 803 is connected to a likely_in indicator (eg a signal or signals) 709 and a coding display 415 , a top_split signal 223 and an fps ad 821 to recieve. In response to these input signals, the probable logic operates 803 in a way that the bit logic in the 2 and 3 is similar and generates a likely_out indication 720 , This is essentially equivalent to the probability indicator 223 , If the ad 415 Is 1, the output is the likely_out indicator 720 the likely_in ad 709 ; if the coding display 415 0, then the output includes the likely_out indication 720 the XOR of the fps signal 821 and the top_split signal 823 , The likely_out ad 720 is with the selection input of the MUX 804 as well as with the input of the codeword generation unit 805 connected.

The mux 804 is connected to next_state_mps 810 and next_state_lps 811 to recieve. In one embodiment, next_state 714 , next_state_mps 810 if the likely_out ad 720 is activated; otherwise it will be next_state_lps 811 as next_state 714 output.

The codeword generation unit 805 is connected to a fps signal 821 , a split8 value 822 , the starting value of the register 703 and the stop value from the register 704 to recieve. In response to these inputs, the codeword generation unit generates 805 a sz ad 710 , a cw (codeword) 711 , a next_start value 712 and a next_stop value 713 , The codeword generation block will be described in more detail in connection with 13 described.

It is noteworthy that the state expansion unit 801 and codeword generation (cw_gen) 805 Outputs generated, the entropy coding table in 2 using logic to reduce hardware costs.

Zustandsausdehnologik

9 FIG. 10 is a block diagram of one embodiment of a state expansion logic 801 , The state expansion logic 801 uses multi-level lookup tables to reduce hardware costs by eliminating redundant LUT entries.

If you take reference 9 so is pclass 219 with the input of the mask generation unit 901 connected. The output of the mask generation unit 901 is with an input of an AND gate 903 connected. The fsm_state from the registry 702 is with an input of the forward unit 902 and an input of the next_state_mps unit 905 , next_state_lps unit 906 , fps unit 907 and split unit or split unit 908 connected. The output of the forward unit 902 is at the other input of an AND gate 903 connected. The output of the AND gate 903 is with the bits_on unit or bits-a-unit 904 connected. The output of the bits_on unit or bits-in unit 904 is with the other Input of the next_state_mps unit 905 , the next_state_lps unit 906 , the fps unit 907 and the allocation unit 908 connected.

In response to these inputs, the next_state_mps unit ("next state, most likely symbol" unit) generates 905 the next_state_mps 810 , the next_state_lps unit ("next state, least likely symbol" unit) 906 generates the next_state_lps 811 and the fps unit 907 generates the fps signal 821 , Likewise, in response to these inputs, the split unit generates 908 the split8 value 822 , The split unit or split unit comprises the split5 unit 909 which is connected to the inputs of the distribution unit 908 to receive and generates a split5 signal 911 in response. The split5 signal 911 is connected to the input of the split5_to_split8 unit ("split-5" to "split-8" unit) 910 that the split8 value 822 generated.

The first stage of the LUT is through the forward unit 902 carried out. In one embodiment, the forward unit comprises 902 an entry for each FSM (Entropy Encoder) state and outputs the entry in response to the fsm state of the register 702 Will be received. In one embodiment, the advance unit ("Advance" unit) comprises 902 61 entries that are (from left to right) as follows:

In one embodiment, each entry represents a 15-bit hexadecimal value. Each bit position corresponds to a PCLASS 1 to 15 (there is no bit corresponding to the 0 probability class). One bit indicates if a PCLASS is encoded as well as or unlike the previous PCLASS (that is, if the LUT information is the same or decides on successive PCLASSs). For example, state 0 ("state 0") has the entry 7ECD ₁₆ or 111111011001101 ₂ . From the right (LSB) there are two zeros in sections 2, 5, 6 and 9. This means that PCLASS 2 is the same as PCLASS 1. Similarly, PCLASSs 4, 5 and 6 are the same and PCLASSs 8 and 9 are the same. A state is the same for each PCLASS (advance = 0000 ₁₆ ); others have a small number of different PCLASSs. If many PCLASSs ("P-classes") have the same LUT information, the logic may be used to implement the next_state_mps unit 905 , next_state_lps unit 906 , fps unit 907 and the split5 unit 909 be reduced.

The mask generation unit 901 creates a mask in response to pclass 219 , In one embodiment, the mask is 000000000000000 ₂ for PCLASS 0, 000000000000001 ₂ for PCLASS 1, 000000000000011 ₂ for PCLASS 2, etc. The mask is represented by the AND gate logic 903 according to the AND function with the output of the forward unit 902 connected.

The bits-a-unit 904 sums up the number of 1-bits used by the AND gate logic 903 be issued to a sel value 912 to create. The sel value 912 is used as an index for the second-stage LUTs.

The next_state_mps unit 905 , the next_state_lps unit 906 and the fps unit 907 complete the lookup of the corresponding values.

In one embodiment, the next_state_mps unit includes 905 an LUT with the following entries (shown in hexadecimal), each row corresponding to an FSM state (beginning with a FSM state 0). It is noteworthy that the second column follows below the first column.

For each of the 61 states, there are eight entries for up to eight possible values of a sel value 912 , If less than 8 values of the sel value 912 for a given state (because many PCLASSs use the same information), "do not care" values are indicated by "xx". More than 8 values of the sel value occur for state 0, the first 8 entries for the next state of the MPS are shown in the table above and the remaining ones are 6 ₁₆ , 10 ₁₆ , 1B ₁₆ and 38 ₁₆ , respectively ,

at an embodiment Next_state_lps unit 906 includes a LUT with the following entries (shown in hexadecimal), where each row corresponds to an FSM state. Again, the second column follows the first one.

For each of the 61 states there are 8 entries for up to 8 possible values of the sel value 912 , If less than 8 values of the sel value 912 for a given state, "do not care" values are indicated by "xx". More than 8 values of the sel value 912 occur for state 0, the first 8 entries for the next state on MPS are shown in the table above, and the remaining ones are all 0.

In one embodiment, the fps unit contains 907 an LUT with the following entries, with the second column following the first column and the third column following the second column. Again, each row corresponds to a different FSM state.

For each of the 61 states there are 8 entries for up to 8 possible values of the sel value 912 , If fewer than 8 values of the sel value 912 occur for a particular state, "do not care" values are indicated by "x". More than 8 values of the sel value 912 occur for state 0. The first 8 entries for the next state on MPS are shown in the table above and the remaining ones are all 1.

The split5 unit 909 performs a lookup that generates a 5-bit split index, then through the split5_to_split8 logic 910 is expanded or expanded to the correct 8-bit split value, the split8 value 822 to create. The split5 unit 909 contains an LUT with the following 5-bit entries (shown in hexadecimal), with the second column following the first column.

For each of the 61 states there are 8 entries up to 8 possible values of the sel value 912. If less than 8 values of the sel value 912 for a given state, "do not care" values are indicated by "xx". More than 8 values of the sel value 912 occur for state 0, the first 8 entries for the next state on MPS are shown in the table above and the remaining ones are respectively 1C ₁₆ , 1D ₁₆ , 1E ₁₆ and 1F ₁₆ .

The 5-bit indexes are divided into 8-bit split values by the split5_to_split8 unit 910 converted. The split5_to_split8 unit 910 uses the following LUT (with entries shown in hexadecimal). For example, for state 0 and sel 0, the first split point index is 05 ₁₆ , which corresponds to a value of 80 ₁₆ . The 05 ₁₆ value appears at the top left of the split.hex value above. The 80 ₁₆ value is derived from the 05 ₁₆ position in the split58.hex list below (the sixth position from the start of the list where "xx" is the 00 ₁₆ position).
// split58.hex
// 5-bit split-point indices to preserve 8-bit values
xx 40 60 64 70 80 84 88 8c 90 98 9c aO a8 ac b0 b8 bc be c0 c8 cc d0 d8 dc e0 e8 f0 f8 fc fe ff

The next_state_mps unit 905 , the next_state_lps unit 906 , the fps unit 907 and the split5 unit 909 can be realized, assuming that both the fsm_state and register 702 as well as the sel-value 912 are valid at the beginning of the operation. In this case, each unit generates a single output. Alternatively, the speed can be increased if a two-step process is used for each unit. First, the fsm_state is used to output all possible values of the sel value 912 to determine. Second, the sel value 912 used to multiplex the correct possible output to the output. Because fsm_state before the sel value 912 will be valid, this can allow a higher speed.

The following example shows the operation of one embodiment of the FSM encoder. Table 3 sums up the lower results. Initially, the encoder starts in the pstate 262 for each context with the PCLASS equal to 0, the MPS equal to 1, and the FSM state equal to 0. A context of 6 and an input bit of 0 are received as inputs to the FSM encoder. (Contexts and bits in this example are arbitrarily taken up.) The PCLASS 0 implies that the sel value 912 is equal to 0. With the sel value 912 equal to 0 and a FSM state equal to 0, a 5-bit split index value is obtained. It is noteworthy that this value is obtained from the above split.hex table, where each row corresponds to a FSM state (beginning with the first line corresponding to FSM state 0). Using the split58.hex table, the 5-bit split point index is converted to a split value of 80 hex. Therefore, the interval running from 0-7F is split at 80 hex so that an interval of 0-7F is set and the other interval is 80-FF. The fps signal indicates which of the 0-7F or 80-FF intervals is related to the occurrence of an MPS. To determine which side is associated with or associated with the MPS, the fps signal is calculated. In this case, the fps signal is 0. This is determined by looking at first.hex and examining the first row corresponding to a FSM state equal to 0, which is a selection of the first row of the Table and sel 912 equal to 0, which is the first bit position of the first bit in that row. In this case, because the fps signal is 0, the MPS is assigned to the upper interval of 80-FF. Since the input bit is in a probable state (that is, the input bit is the same as MPS), the interval of 80-FF is calculated. When the most significant bits of the upper limit bits FF and the lower limit 80 of the interval are compared, the first bit is 1 in both cases. Therefore, a 1-bit is output.

Because the pstate is bigger or the same 214 and there is an output, the PSTATE is updated. The update is based on the current contents of the table and is based on the state 263 updated. As far as the FSM state is concerned, it remains in FSM state 0 because 00 _{16 is} in the first position (sel value 912 = 0) of the first row (FSM state = 0) of the next m.hex table.

When next the interval is changed and a new interval is created by moving the remaining ones Generates bits that have not been output from the interval. For example, all bits that are the lower interval end point which are not output as a result of the output of the codewords were shifted to the left and zero bits are in the least significant Bits shifted. Since the first zero bit has been issued and seven zero bits remain, all seven are least significant Bits are shifted one bit to the left and 0 goes to the LSB added In similar Manner include the upper end of the interval 7F all remaining bits 1111111, which are shifted to the left by one bit and / or another Bit is added to the least significant bit of the interval. This leads to a new interval of 00-FF (the state 0 means that the interval 00-FF).

The next context is 6 and the next bit entered is 0, while the PSTATE 263 is. A PSTATE of 263 corresponds to a PCLASS of 2. In response to the pclass 219 2 is gives the mask generation 901 a mask value equal to 000000000000011. In response to a FSM state equal to 0 indicates the forward unit 902 the entry corresponding to the FSM state 0 which is 7ECD ₁₆ or 111111011001101 ₂ . The results of ANDing the output of the mask generation 901 and the forward unit 902 are 000000000000001. In response to this value, the bit_on unit or bit-in unit generates 904 a sel value 912 equals 1. Thus, with the FSM state equal to 0 and the sel value 912 equal to 1 get a split index of 0C from split.hex. This corresponds to an 8-bit split value of A0. Therefore, the two intervals of 00-9F and A0-FF run.

With a FSM state of 0 and a sel value 912 equal to 1, the second position of the first row of first.hex indicates that the fps signal 821 is equal to 1. So that the fps signal 821 is equal to 1, the interval associated with the more probable case is the interval of 00-BF. This interval is chosen for calculation because the input bit is the same as the MPS (that is, it is in its more probable state). Because the most significant bit of the beginning of this interval (00) does not match the most significant bit of the end of the interval (A0), there are no bits that are output and the system transitions to a new FSM state, as by next.m .hex is displayed (state 3, as in the second position (sel value 912 = 1) of row 0 (FSM state = 0) is displayed) while the PSTATE remains the same. It is noteworthy that, because no bits are output, no pushing of bits into the Intervallendpunkte is performed.

The next Inputs are a context bit of 6 and an input bit 0. Based on the entries an allocation value of 60 hex occurs. This split value will be on the previously selected Interval from 00 to BF applied. Therefore, the 00-9F interval becomes divided between 00-5F and 60-9F. The fps signal indicates that the first Section of the first interval from 0-5F the probable interval is. Because an MPS was obtained as the input bit, this becomes calculated first interval from 0-5F. In this case, the first bit is right the endpoints of the interval 0 and 5F and is therefore output. After the bit is output, the remaining bits of the interval values become moved to the left and a 0 is added to the lower interval (where a 00 end point is generated) and a 1 becomes the upper interval added (where a BF endpoint is generated) so that the new interval becomes 0-BF.

This processing of input data continues as shown in the table below. However, an interesting example occurs when the context is 6 and the input bit is a 1. In this case, the interval from 0-C7 runs with a split value of C0 (from split58.hex). Based on the fps signal, the probable interval, or the probable interval, runs from C0 to C7. In this case, the most significant 5 bits of both the beginning and end points of this interval match and would be output (11000 ₂ ). After the output of the five bits, the remaining bits of both the start and stop intervals are shifted left, with the zeroes filling the lower order bits of the lower end of the interval and the ones filling the lower order bit positions of the upper interval. This results in a new interval of 0-FF.

Table 3 Sample Data (cw = codeword; "size" = size)

So far the output bits are 100000011000, so can the first byte 81 in hexadecimal.

Although the embodiments of the encoder using the fps and split values are described, the encoder can be implemented in software using similar displays. However, while in hardware an XOR operation with the fps signal is relatively easy to implement, in some computer architectures there is a difficulty in the case of software because the determination of whether one number is greater than or equal to another is Specifying a status bit, not just a bit that is easy to access. The operation of XORing or comparing a bit with a status bit is performed only by performing branching operations that branch to different locations based on whether the status bit is a 1 or a 0, and then goes on a register is accessed at each location loaded with either 1 or 0 representing the status bit display. An example of a pseudo-code of such software is given below:
compare code stream, split8
branch greater than or equal to label 1
load 0 in register
branching label 2
Label 1: load 1 in register
Label 2: compare registers, FPS
branch greater than or equal to LPS
mps

This represents a very cumbersome Implementation.

In the case of software, to overcome these difficulties, two split values may be generated for the cases where fps is 0 and fps is 1. Since the fps signal equal to 1 occurs frequently or with a high percentage of time, only one comparison can be made to obtain a result that has been XORed (rather than the two needed in hardware implementation become). However, if the one comparison does not provide the necessary results, then two additional comparisons are needed, which is more than the two needed in hardware, with a final comparison made between the input and the MPS to determine if they match (probably). An example of a pseudo code for this software is given below, using two split values, one of which is for the fps indicator to be 1 (split8_fps1) and one for the fps indicator to be 0 ( split8_fps0).
compare code stream, split8_fps1
branch less than MPS; most likely case
compare split8_fps1,0
do not branch LPS right away
compare code stream, split8_fps0
branch greater than or equal to MPS
LPS

clear

There are several possible implementations of the flush logic or purging logic 707 , 11 Figure 4 is a block diagram of one embodiment of the flush logic 707 to evacuate in a cycle with the value 0111 ₂ . Alternatively, a longer value, such as 10,000,000 ₂ , may be used. If you take reference 11 so is the delay 1101 connected to the flush signal or clearing signal 413 to receive and the done_ or "cleared rooms" display 416 issue. In one embodiment, clearing takes one cycle. Again, in this case, the flush_sz ad will appear 715 set to 4 and flush_cw 716 is set to 4 bits 0111. Again, the start and stop values are from the start register 703 and the stop register 704 not used.

Bei einer alternativen Ausführungsform kann das Räumen durch Kodieren von 8 Bits in PCLASS 0 durchgeführt werden. Dies erfordert keine Logik in dem FSM-Kodierer. Die Kontextmodell-/Wahrscheinlichkeitsschätz-/Systemsteuerung führt das Räumen durch.To clear out with the minimum number of bits, the codeword used for spaces can be determined by the start and stop values, as in 12 is shown. If you take reference 12 so is the generate_codeword_for_flush unit ("generate code word to rooms" unit) 1201 connected to the starting value from the register 703 and the stop value from the register 704 to recieve. In response to these output signals, the unit gives 1201 a flush_sz ad 715 and a flush_cw 716 out. Likewise, the delay unit 1202 connected to a flush signal 413 to receive and a done_flush ad 416 issue. The generate_codeword for flush unit 201 works as follows:

In an alternative embodiment, clearing may be performed by encoding 8 bits into PCLASS 0. This does not require logic in the FSM encoder. The context model / probability estimation / system control performs the broaching.

Biterzeugungs-Verilog

The following is an exemplary Verilog HDL description for the 8th . 9 and 11 shown.

Determination of the number the one-bit

The bits-a-unit 904 in 9 determines the number of 1-bits with a tree of adders. An exemplary Verilog HDL description is the following:

Codeword generation

13 is a block diagram of one embodiment of the codeword generation unit (cw_gen) 805 the bit generation logic 701 , As previously discussed, the code word engine generates 805 a codeword and performs this function within a logic rather than within a LUT, which can save hardware.

If you take reference 13 so includes the code word unit 805 MUX 1301 that is connected to the seed from the seed register 703 and receive the split8 value 822. The mux 1302 is connected to the output of the subtractor 1309 on its first input and the stop value from the stop value register 704 to receive the second input. The outputs of the MUXs 1301 and 1302 are via a select signal output from the comparator 1303 selected, which is connected to a probable indicator 720 and a fps signal 821 and if the two are equal, the output signal on the selection signal is asserted, thereby reducing the start value provided by the MUX 1301 and the split8 value 822 minus 1, from the mux 1302 is to be output is selected. If not enabled, the split8 value becomes 822 from the mux 1301 output and the stop value is from the MUX 1302 output.

The output signal of MUX 1301 is applied to an input of the XOR gate 1304 to the codeword slider 1306 and the start slider 1307 connected. The output of the MUX 1302 is at the other input of the XOR 1304 and to an entrance of the stopper 1308 connected. The output of the XOR gate 1304 is at the input of the priority encoder 1305 connected. The output of the priority encoder 1305 is a sz indicator (eg a signal or signals) 710 that from the codeword generation unit 805 is issued. The sz ad 710 is also at the other input of each codeword slider 1306 , Start slider 1307 and stop slider 1308 connected. The outputs of the codeword slider 1306 , Start slider 1307 and stop slider 1308 are the cw (codeword) 711 , of the next_start value 712 and the next_start 713 ,

The currently valid interval between the start and stop values is divided into the value specified by split8 value 822. The comparator 1303 performs a comparison between a probable ad 720 and an fps 821 to determine whether either the start or stop value is replaced by the split value indicated by the split8 value 822 at a new interval (new start and stop value). to create. In one embodiment, if the stop value is replaced, it is replaced with the stop value minus 1. The new start and stop values are given by the XOR 1304 according to the exclusive-OR operation to locate bits that match. The number of match bits is started by the priority encoder starting with the MSB 1305 determined and as the size of the codeword (sz display 710 ). The size of the codeword controls the sliders 1306 to 1308 , The match bits of the new start and stop values are given by a cw-slider 1306 as cw 711 output. The bits that do not match are given by the start slider 1307 and the stop slider 1308 as next_start 712 and next_stop 713 respectively issued. The start slider 1307 fills the LSB (s) of the lower and the interval with zeroes. The stop slider 1308 fills the LSB (s) of the upper endpoint of the interval with ones. In some embodiments, this requires the move and the ORn (see Verilog).

It is noteworthy that in alternative embodiments, two or all three of these slides can be combined. Equally noteworthy is that the cw-slider 1306 used the new stop value as an input instead of the new start value.

An exemplary veriolog-HDL description of 13 is given below:
// Copyright or Copyright 1997 RICOH
// Create a codeword

table 4 sums up the valid ones Start and stop pairs representing the 61 FSM states. These start and stop pairs and no others will be through the operation of Hardware generated.

Table 4 Valid start and stop pairs (hexadecimal)

Bit-packing

14 Fig. 10 is a block diagram of one embodiment of the packing unit 404 of the entropy coder 400 , The packing unit 404 combines codewords of variable length in bytes when coded. The clock and enable signals are not shown to avoid obscuring the invention.

If you take reference 14 that's the code word 417 with an input of the OR gate 1402 connected to the output of the sliding device 1401 linked according to the OR link. The results of the OR operation are in the buffer register 1403 saved. The buffer register (bbuf) 1403 Holds the bits until they are put together in bytes and output. In one embodiment, the buffer register is 1403 a 16-bit buffer. When the input data is received, the data that is currently in the buffer register 1403 are moved, moved by the slider 1401 is used to make room for the new data and the new data is added. To clear at the end of decoding, any data that is currently in the buffer register 1403 are moved to complete a byte. The data coming from the buffer register 1403 are output with the input slider 1405 connected. The slider 1405 sets up the data content buffer register 1403 according to the value of the counting register 1406 off to the data output data_out 229 to create. For example, assuming that there are 9 bits in the buffer register 1403 in positions 8..0, the count in the count register 1406 9 and bits 8..1 are for output, the shifter 1405 directs these 8 bits to bits 7..0 of data_out 229 out. Bit 0 of the buffer register 1403 remains until the next byte can be output.

Alternatively, a single slider could be used instead of two slides. The only slider would be the data at the input of the buffer register 1403 align. The buffer register 1403 would be realized as two 8-bit registers which can shift by 8 when each byte has been issued. An example of such a realization is in 14A shown.

The buffer register 1403 saves data in response to the output of the release logic 1408 which is connected to the size indicator 418 to receive and an advertisement 414 to enable. The release logic 1408 enables its release output if size (size) greater than 0 is enabled in the share. The release output for the release logic 1408 is with the input of the register used 1409 connected to indicate that bits have been sent.

The output of the buffer register 1403 becomes the slider 1401 returned to be combined with the moved data.

The counting register (bcnt) 1406 stays with the bits in the buffer register 1403 ongoing, waiting to be issued. The counting register 1406 is incremented / incremented by the size of the input data minus a certain amount based on whether the data_in_ready signal 1428 is activated. If enabled, the counter will be in the count register 1406 increased by the size of the input data minus 8; otherwise the counter is increased by the size of the input data (minus 0). The counting logic 1404 (which is connected to the size indicator or size indicator 418 , a feedback of the data_out_ready_signal or data_out_fertig_Signals 423 , a feedback from the counting register 1406 and the output signal of the purging logic 1410 to receive) is for activating the data_in ready_signal 1428 responsible. In one embodiment, the count register comprises 1406 a 4-bit counter.

The finished logic 1407 monitors when the output of a count register 1406 8 or more and activates the data_out_ready signal 423 , When this occurs, the counting logic lowers 1404 the count in the count register 1406 at 8.

The clearing logic 1410 is used to clear or dump any data that is still buffered at the end of the encoding. In one embodiment, the clean-up logic removes 1410 the counting logic 1404 and the slider 1401 in response to the stink signal 413 and bg_done_flush signal 416 , The flush logic 1410 is also connected to the output of the used register (bused) 1409 and the output of the count register 1406 to recieve. The used register 1409 is set to 1 if any data is entered. In one embodiment, the register used is 1409 a 1-bit register. It is used to indicate when no data has been entered, so that space is not necessary. The flush logic 1410 performs the scavenging operation if a flush signal 413 is activated, the value in the count register 1406 is greater than 0 and the value in the register used 1409 is greater than 0. If the used or used register 1409 indicates that no data has been entered, shows the flush logic 1410 that the room is completed. To clean up, if data_out_ready 423 is not activated, then the contents of the buffer register 1403 moved to the MSB (s) by the slider 1401 is used and the contents of the count register 1406 is set equal to 0 if the data_out_ready signal 423 is enabled or set equal to 8 if the data_out_ready signal 423 is not activated. Spaces are well known in the art.

After the room is completed, the flush logic activates 1419 the done_flush signal 424 , In other words, if the flush signal 415 is activated and either the count in the count register 1406 0 or the value of the used or used register 1409 0, then the done_flush signal 424 activated.

If the FSM encoder is reset, the buffer register will be 1403 , the counting register 1406 and the used register 1409 initialized. In one embodiment, they are initialized to zero.

An exemplary Verilog HDL description for the 14 follows.

Bit unpacking

15 Fig. 10 is a block diagram of one embodiment of an unpacking unit 405 which performs a variable-length shift of the bytes of the coded data stream into variable-length codewords during decoding. The beat 405 , the reset signal 411 and the enable signal 414 are not shown to avoid obscuring the present invention.

If you take reference 15 so that's the data_in codeword 221 to the input of the buffer register 1501 and the slider 1504 connected. The buffer register (ubuf) 1501 holds a previous number of bits of encoded data. In one embodiment, the buffer register is 1501 an 8-bit register holding the previous 8 bits of encoded data.

The output of the buffer register 1501 is at the entrance of the slider 1502 connected, the data in an input of the OR gate 1503 in response to the output of the count register 1506 shifts. The other input of the OR gate 1503 is at the exit of the slider 1504 connected, the data_in 221 in response to the count 1509 that from the count register 1506 is issued, shifts. The output of the OR gate 1503 is the data_out 1520 which is the code stream 419 is.

The counting register 1506 gives the count 1509 in response to an input of the count logic 1505 out. The counting logic 1505 generates its output in response to the count 1509 from the output of the count register 1506 is returned, the size indicator 418 and the output of the comparator 1507 , The other input of the comparator 1507 is with the count 1509 connected. The output of the comparator 1507 , the wnext signal 1510 is at the input of the next register or the next register 1508 connected. The output of the next register 1508 is the next_byte signal 420 ,

The counting register (ucnt) 1506 Holds the number of bits in the buffer register 1501 that have not been consumed by the decoder. The counting register 1506 is about the counting logic 1505 is decremented by the size of the codeword consumed by the decoder, such as the size indicator 418 is shown. If the value in the count register 1506 is less than or equal to the size of the currently requested code word, data_in 221 in the buffer register 1501 loaded, the counting register 1506 is incremented by 8 and a wnext signal 1510 is activated.

The correctly aligned code stream data_out 1520 is generated by the number of bits equal to the count 1509 (count register 1506 ) from the buffer register 1501 and the number of bits equals 8 minus the on number of bits equal to the count 1509 from data_in 221 is taken.

The comparator 1507 is a "less than or equal" comparator that determines whether the count is 1509 less than or equal to the size indicator or size indicator 1418 is. If it is, the wnext signal will be generated 1510 activated. In response to the fact that the wnext signal 1590 is activated, generates the next register ("next") 1508 the next_byte control display 420 indicating that the next byte of the encoded data stream is at data_in 221 should be presented. In one embodiment, the register is 1508 a 1-bit signal. In other words, when the first of the two bytes are consumed, the next_byte display shows 420 that the next byte of data_in 221 should be issued.

If the FSM encoder is reset, the buffer register will be 1501 , the counting register 1506 and the next register 1508 all initialized. In one embodiment, these registers are initialized to zero. It is noteworthy that the registers 1501 . 1506 and 1508 can be realized as other types of storage devices.

The following is an exemplary Verilog HDL description for 15 given.
// Copyright or Copyright 1997 RICOH
// unpack the 8-bit code stream bytes into variable length codewords
// data_in must be output directly to data_out, so it's elsewhere
// must be registered

FSM encoder control

16 is a control flowchart for coding. 17 is the corresponding flowchart for decoding. Control is performed by processing logic, which may be hardware logic, software logic, or a combination of both. In one embodiment, the processing logic includes a computer system having one or more processors executing instructions.

If you take reference 16 Thus, the control flowchart for coding begins by processing a logic that performs a reset or a reset (processing block 1601 ). After performing the reset, the processing logic tests to see if the bit and context for coding are done (processing block 1602 ). If the bit and the context are not ready for encoding, processing proceeds to the processing block 1603 where the processing logic does not enable a release indication (eg, signals) and the processing loops back to the beginning of the processing block 1602 , If the bit and the context are done, processing proceeds to the processing block 1604 where the processing logic activates the enable indicator to encode the bit.

After activating the release indicator, the processing logic tests whether the data output is complete (processing block 1605 ). If the data output is done, the processing logic handles the output data at the processing block 1606 and the processing proceeds to the processing block 1607 continued. Such handling may involve the provision of memory, a channel, a display, processing, or whatever else the data uses. If the processing logic determines that the data is not ready to be output, processing proceeds to the processing block 1607 where the processing logic determines if more data is to be encoded. If more data is to be encoded, processing branches to the processing block 1602 back; otherwise, the processing proceeds to the processing block 1608 continued.

At the processing block 1608 The processing logic activates the flush display or the clearing display (eg signal or signals). Thereafter, the processing logic tests whether data is ready for output (processing block 1609). If the data is ready for output, processing proceeds to the processing block 1610 where the processing logic handles the output data and processing proceeds to the processing block 1611 continued. If the data is not ready for output, processing proceeds to the processing block 1611 just like that. At the processing block 1611 Tests the processing logic to determine if a room is complete. If flushing is not complete, the processing logic branches to the processing block 1608 back. If the space has been completed, the control flow for coding ends., Reference is made 17 Thus, the control flow for decoding begins at the processing block 1701 where the processing logic resets the FSM encoder. After resetting the FSM encoder, the processing logic tests whether the context is complete and the encoder is ready for decoding (processing block 1702 ). A synchronization system is always ready while an asynchronous system requests bits of decoded data and / or the system waits for encoded data. If the context is not ready or the encoder is not ready for decoding, processing proceeds to the processing block 1703 where the processing logic does not enable the enable indicator and processing branches to the beginning of the processing block 1702 back. On the other hand, if the context is ready and the decoder is ready for decoding, processing proceeds to the processing block 1704 where processing logic activates the enable indicator to begin decoding the bit. After activating the enable display, the processing logic handles the output bit (processing block 1705 ). This handling may be to provide the decoded data, whatever its use, such as

memory, channel, display, processing, etc. After handling the output bit, the processing logic tests whether more encoded data is needed (processing block 1706 ). If more coded data is needed, the processing logic gives more coded data to the decoder (processing block 1707 ) and the processing proceeds to the processing block 1708 continued. On the other hand, if more coded data is not needed, processing goes directly to the processing block 1708 above. At the processing block 1708 tests the processing logic to see if there is more data to decode. If there is more data for decoding, the processing logic branches to the processing block 1702 back. If there is no data to be encoded, the control flow for decoding ends.

The Verilog shows the operations in detail and includes one as well certain initialization for the Simulation is specific.

parallelization and pipelining

The The present invention can be used with parallelization and pipelined or pipelined become. Both types of processing increase the maximum clock speed and allow coding more than 1 bit per clock cycle. However, this is pipelining and parallelism by the amount of logic involved Feedback loops difficult. The context memory and the fsm_state or fsm state along with the start and stop registers must be for each bit before the next context to be updated. Many context models are required for decoding as well as receiving the previously decoded bit before the next context, thereby generating another feedback loop becomes. These feedback loops require that certain Operations are sequential, which complicates the parallelism becomes.

at an embodiment The hardware design given above processes one bit per clock cycle. Other compression applications require many bits for each Pixels in a picture are encoded; thus many clock cycles needed. The current number of clock cycles per component of each pixel depends on the depth of the picture and the picture content. It is desirable either more than one bit per clock cycle to process and / or to have a clock rate that is much faster than the pixel clock is.

• • Kodiere ein Bit in irgendeiner PCLASS und ein Bit nur in PCLASS 0.
• • Kodiere zwei Bits, beide in PCLASS 0.
• • Kodiere vier Bits, alle in PCLASS 0.
• • Kodiere zwei Bits in irgendeiner PCLASS, aber nur wenn im FSM-Zustand 0 begonnen wird.

The present invention provides FSM encoders that have true parallelism. For example, two bits (with associated contexts) can be encoded in one cycle. In such a case, the context model creates two contexts in parallel. The bitstream, context memory and fsm_state or fsm state and the start and stop registers are updated as if the two bits were being coded sequentially. The bit generation logic can be modified to handle two PCLASSs. This would require a significant increase in hardware complexity. For example, the codeword generator would have to handle two split values, causing both a start and a stop, and would have to generate up to 16-bit codewords. Simultaneously handling two bits or more could be simplified if only special cases are handled. The normal mode of a "one bit at a time" operation would be used if the special case was not applicable. Here are some examples:

• • Encode a bit in any PCLASS and a bit only in PCLASS 0.
• • Encode two bits, both in PCLASS 0.
• • Encode four bits, all in PCLASS 0.
• • Encode two bits in any PCLASS, but only when starting in FSM state 0.

The Hardware costs of true parallelism or contextual models, which do not allow a parallel context generation, can one make true parallelism unattractive.

A Alternative to true parallelism is different FSM encoders to have the different sections of the encoded bitstream independently to process.

• • Für Video können unterschiedliche Frames bzw. Vollbilder parallel kodiert werden.
• • Das Bild kann in Platten bzw. Unterteilungen ("tiles ") aufgeteilt werden und unterschiedliche Platten bzw. Unterteilungen können parallel kodiert werden.
• • Falls das Bild mehrere Komponenten aufweist (wie z.B. RGB, CMYK oder YUV), können unterschiedliche Komponenten parallel kodiert werden.
• • Es kann Orte innerhalb einer Unterteilung/Komponente geben, so der FSM-Kodierer zurückgesetzt wird, die hierin als Eintrittspunkte bezeichnet werden. Segmente kodierter Daten, die bei unterschiedlichen Eintrittspunkten starten, können parallel kodiert werden. Hinsichtlich Wavelet-Koeffizienten kann es vorteilhaft sein, eine übliche Ausrichtung zu verwenden, wie sie in 10 gezeigt ist. Koeffizienten werden in vier Gruppen gleicher Größe unterteilt (da die DS₁-, SD₁- und DD₁-Frequenzbänder jeweils ein Viertel der Gesamtzahl der Koeffizienten sind). (Eine gleiche Größe bedeutet eine gleiche Anzahl von Koeffizienten, wohingegen die Anzahl der Gesamtbits oder der gesamten binären Entscheidungen in jeder Gruppe unterschiedlich sein können). Niveaus anders als 1 können in einer normalisierten oder pyramidalen Art und Weise ausgerichtet werden. Falls nur ein paralleles Kodieren gewünscht ist, können Kontexte parallel erzeugt werden. Zum parallelen Dekodieren benötigt das Kontextmodell nicht Daten, die noch nicht dekodiert sind. Zur Ausrichtung gemäß 10 kann das Kodieren der Niveau-1-Koeffizienten ohne Konditionierung der Eltern bzw. der Mütter ("parents") notwendig sein.

A particularly attractive option is to pipeline a single physical FSM encoder so that it operates like several independent FSM virtual encoders. Once the pipelining capabilities are exhausted, then the FSM encoders (or non-pipelined portions of FSM encoders) can be replicated for parallel processing. There are many ways to divide the bitstream into sections for parallel coding:

• • For video, different frames or frames can be encoded in parallel.
• • The image can be divided into tiles, and different tiles or partitions can be encoded in parallel.
• • If the image has multiple components (such as RGB, CMYK or YUV), different components can be encoded in parallel.
• • There may be places within a subdivision / component to reset the FSM encoder, referred to herein as entry points. Segments of coded data starting at different entry points can be coded in parallel. With regard to wavelet coefficients, it may be advantageous to use a common orientation, as in 10 is shown. Coefficients are divided into four groups of equal size (since the DS ₁ , SD ₁ , and DD ₁ frequency bands are each one quarter of the total number of coefficients). (An equal size means an equal number of coefficients, whereas the number of total bits or the total binary decisions in each group may be different). Levels other than 1 can be aligned in a normalized or pyramidal manner. If only parallel coding is desired, contexts can be generated in parallel. For parallel decoding, the context model does not need data that has not yet been decoded. For alignment according to 10 coding the level 1 coefficients without parental conditioning may be necessary.

Around To achieve a high degree of parallelism, various of the above can be used Ways to share the data used in the same implementation become. Unfortunately all of these ways limit flexibility in some ways to one to achieve high speed. A single picture with a single one Plate or subdivision ("tile"), a single component and no entry points (apart from the start of the coded Data for the subdivision or the plate) can not be coded in parallel become.

• • zwischen dem Kontextmodell und dem FSM-Kodierer,
• • nach dem Kontextspeicher,
• • nach der Wahrscheinlichkeitszustands-Ausdehnung,
• • nach der Erzeugung des sel-Wertes,
• • nach der Zustandsausdehnung.

There are several places where the FSM encoder can be broken down into pipeline stages, such as the following:

• Between the context model and the FSM encoder,
• • after the context memory,
• • after the probability state expansion,
• After the generation of the sel value,
• • after state expansion.

Around a valid one Wavelet code stream when using multiple independent FSM encoders will be rearranged the coded data. The issue of Each encoder becomes independent buffered when encoding. After the coding is completed, the buffers are output to the code stream at the correct locations. For decoding, each encoder uses a different one Section of the code stream too.

In In the foregoing description, the "variable length shifting of bytes" means of bytes ") that the bits moved within the bytes who the. This is sometimes called "barrel shifting" or "bin shifting".

at In the description above and in the claims, the term "most significant bits" includes the most significant bits, starting with the highest value Bit. For one byte (8 bits) with bits 7, 6, 5, 4, 3, 2, 1, 0 is e.g. the most significant Bit the bit 7. The two most significant ones Bits are bits 6 and 7. The three most significant bits are the Bits 5, 6, and 7, the four most significant Bits are bits 4, 5, 6, and 7, and the five most significant bits are Bits 3, 4, 5, 6 and 7 etc.

• Falls A[7] ! = B[7], dann stimmen keine Bits überein.
• Falls dies nicht gilt und falls A[6] ! = B[6], dann stimmt ein Bit, nämlich das Bit 7 überein.
• Falls dies nicht gilt und falls A[5] ! = B[5], dann stimmen zwei Bits überein, nämilich das Bit 6 und das Bit 7.
• Falls dies nicht gilt und falls A[4] ! = B[4], dann stimmen drei Bits überein, nämlich das Bit 5, 6 und 7, usw.

The endpoint of an interval, as claimed in claim 1 for example, may be a bit string, such as a binary information unit. As an example of a binary information unit you can use eg a byte. For example, consider two bytes A and B as endpoints of a subinterval, and let A [7] be the 7th bit of A. If "! =" Means that the bits do not match, and one bit can only have the value 1 or 0, then when comparing the starting point and the end point of a subinterval (in particular according to claim 1), the following applies:

• If A [7]! = B [7], then no bits match.
• If not, and if A [6]! = B [6], then one bit, namely bit 7, is the same.
• If this is not true and if A [5]! = B [5], then two bits match, namely bit 6 and bit 7.
• If this is not true and if A [4]! = B [4], then three bits match, namely bits 5, 6 and 7, etc.

Thus, a comparison is made of the bits of the endpoints A and B in the order of their significance, starting with the most significant bit, where a match is detected only up to the first mismatched bit (see also the Verilog in connection with US Pat 13 ).

takes one e.g. that A is equal to "10101010" and B is equal to "10111011", where the order is "most significant bit ... least significant Bit "is, then agree the three most significant ones Bits (7, 6, 5) match. The first mismatched Bit is the 4th bit. The matching ones Bits are "101", both with A [7..5] as well as agree with B [7..5], since they are the same. The three matching Bits "101" are used during the Coding output. The mismatched Bits of A are "01010" and the mismatches Bits of B are "11011". The mismatched In particular, bits are used to create new endpoints (being among the highest Bits are moved): "01010" becomes "01010 ..." becomes "01010000"; and "11011" becomes "11011 ..." and becomes "11011111".

The invention can be summarized in particular as follows:
An FSM coding hardware is described. In one embodiment, the present invention provides a method of encoding that allows the generation of an interval based on a Finisher (FSM) approach stand included. The interval includes a pair of subintervals that have endpoints. The method also includes selecting one of the pairs of subintervals based. whether the input bit is in a most probable state, and outputting zero or more bits, corresponding to bits that match between endpoints of the one subinterval, from the most probable bits to, and not including, the first mismatching bits between the two Endpoints of a subinterval occur.

Herewith becomes the content of the German applications 198 44 752.3-31 and 198 19 405.6-31 and 196 26 600.9-31 by reference in the present Registration included.

Claims (81)

Method for coding input bits, the the following steps include: one Interval is generated on a Finisher (FSM) state based, wherein the interval comprises a pair of subintervals, the Have endpoints, each endpoint represented by a binary value becomes; a subinterval of a subinterval pair becomes based on selected whether the input bit is in its most likely state is; zero or more bits are output that those Bits correspond to when the binary values of the endpoints of the selected subinterval of the couple with the binary values compared to the endpoints of the other subinterval of the pair will match in terms of their value and bit significance and those with the highest Start bit and get to the first mismatched one Bit in a descending order of bits significance but do not include the first non-matching bit. The method of claim 1, wherein the step the generation of the interval includes the selection of a value to split the interval into the pair of subintervals is. The method of claim 1, wherein the first Subinterval of the pair of subintervals most likely Symbol is assigned and the second subinterval of the pair of Subintervals associated with a least probable symbol is. Apparatus for coding input bits, the following comprising: a Device to set an interval based on the state of a finisher (FSM), where the interval is a pair of subintervals comprises having endpoints, each endpoint represented by a binary value becomes; means for selecting a pair of subintervals based on whether the input bit is in the most probable state is or not; a device for outputting zero or more bits corresponding to those bits which, when the binary values of the Endpoints of the selected Subinterval of the pair with the binary values of the endpoints of the other subinterval of the couple, in terms of their value and theirs Match bit significance and those with the highest Begin bit and to the first mismatched bit in one respect the bitsignificance descend, but they do not the first mismatched Include bit. Apparatus according to claim 4, wherein the device for generating an interval means for selecting one Value includes by splitting the interval into the pair of subintervals is. Apparatus according to claim 4, wherein the first of the Pair of subintervals a most probable symbol is assigned and a second of the pair of subintervals one lowest possible symbol is assigned. Apparatus for coding, comprising: a first logic unit for generating an interval based on a state of a finisher (FSM), the interval having a pair of sub-intervals having endpoints, each endpoint represented by a binary value; a second logic unit for selecting a subinterval of the pair of subintervals based on whether the input bit is in a most probable state and outputting zero or more bits corresponding to those bits when the binary values of the endpoints of the selected one Sub-interval of the pair are compared with the binary values of the endpoints of the other subinterval of the pair, with respect to their value and their bit significance match and those with the most significant bit begin and go to the first mismatched bit in an order decreasing in bit significance, but not including the first mismatched bit. Apparatus according to claim 7, wherein the first logic unit select a value, by splitting the interval into the pair of subintervals is. Apparatus according to claim 7, wherein the first sub-interval of the pair of subintervals the most probable symbol is assigned and a second interval of the pair of subintervals assigned to the lowest probable symbol. The apparatus of claim 9, further comprising an indicator comprises which is connected to the second logic unit to indicate which pair of subintervals is the most probable symbol assigned. Apparatus according to claim 10, wherein the display includes a signal. Method for coding a number of bits with an FSM encoder, the method comprising the steps of: one Interval is for each of the number of bits specifies the two subintervals and wherein each of the two sub-intervals comprises a pair of endpoints has, each endpoint represented by a binary value; for each the said bits becomes a subinterval of the two subintervals selected an interval, based on which of the two sub-intervals the most likely Symbol is assigned and whether that bit is the same symbol is like the most likely Symbol; and zero or more bits are output for each interval, which correspond to those bits which, when the binary values of the endpoints of the selected subinterval of the couple with the binary values compared to the endpoints of the other subinterval of the pair will match in terms of their value and bit significance and those with the highest Begin bit and to the first mismatched bit in one respect the bitsignificance descend, but they do not the first mismatched Include bit. The method of claim 12, wherein one of signal generated, which of the two subintervals the most probable Symbol is assigned. The method of claim 12, further comprising the following Steps includes: the relevant bit or the one bit is the display of the most probable Symbols compared; and a probable ad is activated if the bit in question matches the display of the most probable symbol. The method of claim 12, further comprising the following Steps includes: one first split value is obtained from a first table; one second split value is obtained from a second table by the first split value is used. The method of claim 15, wherein the split value is obtained based on the FSM state and a first value. The method of claim 16, further comprising the following Steps includes: a Mask is generated based on a probability class; one second value is obtained from a table, based on on the FSM state; the mask and the second value is ANDed, to produce a result; and the first value is generated based on the result. The method of claim 17, wherein the step of generating the counting of ones in the result includes for a count or a count value to generate, with the count or the count includes the first value. The method of claim 12, further comprising the step of shifting disagreeing bits to the left to the most probable bit locations, and filling any little significant bits with either a 0 bit if the endpoint in the subinterval is a lower bound, or a 1- Bit, if the end point in the subinterval is an upper limit. Device comprising: a context model; one Final Automate (FSM) encoder connected to the context model is to encode bits received from the context model, wherein the FSM encoder encodes bits by specifying an interval will, for each of the number of bits having two subintervals and where each of the two subintervals has a pair of endpoints, where each endpoint by a binary value is shown, wherein a subinterval of the pair of subintervals selected based on it whether the input bit is in a most probable state and outputs zero or more bits representing those bits match that when the binary values the endpoints of the selected Subinterval of the pair with the binary values of the endpoints of the other Sub-interval of the pair are compared, in terms of their value and their bit significance and those with the highest Start bit and get to the first mismatched bit in one run in descending order of bits significance, but that's not the first mismatched one Include bit. Apparatus according to claim 20, further comprising a reversible Wavelet transform comprises which is connected to the context model. The apparatus of claim 20, further comprising header processing or a header processing associated with the FSM encoder connected to output coded data and signaling. The apparatus of claim 20, wherein the FSM encoder a combined FSM coding / decoding table with separate probability estimation and Bitmap Lookup Tables (LUTs). The apparatus of claim 20, wherein the FSM encoder includes a single LUT, around both a probability estimate and a bit generation perform. The apparatus of claim 20, wherein the FSM encoder comprises a first logic unit, to select a value by splitting the interval into the pair of subintervals is. Apparatus according to claim 20, wherein a first Subinterval of the pair of subintervals the most probable Symbol is assigned and a second subinterval of the pair subintervals are assigned to the least probable symbol is. The apparatus of claim 26, wherein the FSM encoder further comprises an advertisement, to indicate which subinterval of the pair of subintervals the most probable Symbol is assigned. Apparatus according to claim 27, wherein the display includes a signal. The apparatus of claim 20, wherein the FSM encoder comprising: a first unit to perform a multiple context probability estimation; a Conversion unit to a probability estimation state to convert into information describing the condition wherein the conversion unit is uncoded bits in response to a Probably display generated; a bit generation unit, which includes a look-up table (LUT) to switch between uncoded Convert bits and encoded bits, where the bit-generation LUT is zero or more codewords in response to each probability estimate from the conversion unit and where the bit generation LUT is the probable indication generated in response to the encoded data stream from the unpacking unit; a Packing unit connected to code words from the bitmap lookup table to receive code words variable length to combine in bytes when encoded to output with to generate coded data. Apparatus according to claim 29, wherein the bit-generating LUT in the FSM encoder non-redundant entries contains. The apparatus of claim 29, wherein the FSM encoder further comprises an unpacking unit for variable-length so-called "variable-length displacement of bytes" of the coded data stream into codewords Length to be carried out, wherein the "variable length displacement of bytes", the bits are shifted within the bytes. The device of claim 29, further comprising comprising: a Probability class unit, around a probability class in response to the probability state; a MPS likelihood state unit for the next likelihood estimation state event generate if an MPS occurs and update the probabilistic state is required; an LPS probability state unit, around the next Probability estimation state in the case generate when an LPS occurs and the probability state to be updated; a switching unit to the switching indicator to generate if the MPS is to be switched; and an updating unit, to generate an update indication when the probability state less than or equal to the predefined value. The apparatus of claim 32, wherein the MPS probability state unit the next probability estimation state generated by a current probability estimation state is incremented or decremented by an integer, and indeed within a range of values based on the value of the current one Probability state based. Apparatus according to claim 32, wherein the switching indicator includes a signal. Apparatus according to claim 32, wherein the switching indicator is activated if the probability state is less than or equal to or equal to a first predetermined value second predetermined value. The apparatus of claim 32, wherein the update indicator includes a signal. Apparatus according to claim 29, wherein the bit generation unit the biter generation logic involves to perform a conversion between uncoded bits and coded bits. Apparatus according to claim 37, wherein said bit generation logic a first output signal to provide the codeword, and a second output signal to the Size of the codeword display. Apparatus according to claim 37, wherein said bit generation logic the next Start and stop value generated to set the interval. Apparatus according to claim 39, further comprising the starting and stop registers, which are connected to the start and stop values by the bit generation logic is generated to receive, the startup and stop registers as well to the entrances the Biterzeugungslogik are connected. Apparatus according to claim 29, wherein the bit generation unit codewords generated to clear at the end of the coding. Apparatus according to claim 29, wherein the generating unit continue a clearing logic comprises to generate a codeword to a predefined codeword in response to spend that one evacuation indicator is signaled to clear the Biterzeugungseinheit. The device of claim 42, wherein the clearance indication a clearing signal includes. The apparatus of claim 42, further comprising a MUX comprises which is connected to receive a codeword that coded Represents data, and a predefined codeword to evict. In which the MUX is still connected to receive the eviction notice, around the entrances to select as the output of the bit generation unit. The apparatus of claim 29, further comprising: a state expansion unit responsive to a probability estimate and the finisher state (FSM) state for generating a first split value and the next probability estimate states for occurrences of an MPS and an LPS when a probability estimation state Updating is required; a comparator for comparing the first split value with the incoming code stream, the comparator outputting a second split value; a probabilistic logic connected to the comparator and the state expansion unit to generate a probable indication; a MUX connected to receive the next probability estimation variable and the probable indication, the MUX outputting one of the next probability estimation states based on the probable indication; a codeword generating unit for generating codewords in response to the first split value, the probable display, and an interval display. Apparatus according to claim 45, wherein the interval display a start value, indicating a beginning of the interval, and a stop value, the indicating an end of the interval. Apparatus according to claim 45, wherein the expansion unit comprising: a first unit to assign a mask value in response to a probability estimate produce; a second unit to get a value in response to to generate the FSM state; a gate logic connected is to logically ANDing the outputs of the first unit and the second unit; a third unit, which is connected to an output signal of the To receive gate logic and a selection signal that appeals to it, to create; an MPS unit according to a next state or a next-state MPS unit, respectively, in response to the selection signal and the FSM state the next probability estimation state for the Create case when an MPS occurs and an update is required is; an LPS unit according to a next State in response to the select signal and the FSM state the next Probability estimation for the case to generate when an LPS occurs and an update is required is; a fourth unit to respond in response to the selection signal and the FSM state an ad about it to generate which subinterval is associated with an occurrence of an MPS is; and a fifth Unit to the second split value in response to the selection signal and to generate the FSM state. Device designed as FSM encoder, which includes: a first unit to perform a multiple context probability estimation; a Conversion unit to a probability estimation state to convert into information describing the condition wherein the conversion unit is uncoded bits in response to a Probably display generated; a bit generation unit, which includes a look-up table (LUT) to switch between uncoded Convert bits and encoded bits, where the bit-generation LUT is zero or more codewords in response to each probability estimate from the conversion unit and where the bit generation LUT is the probable indication generated in response to the encoded data stream from the unpacking unit; a Packing unit connected to code words from the bitmap lookup table to receive code words variable length to combine in bytes and to link in byte form, if is encoded to produce an output with encoded data. Apparatus according to claim 48, wherein the bit-generation LUT no redundant entries contains. The apparatus of claim 48, further comprising an unpacking unit comprises to a so-called "variable length shift Bytes "of the coded Data stream in codewords variable length perform at the "variable length shift Bytes "the bits within the bytes. The apparatus of claim 48, further comprising: a probability class unit for generating a probability class in response to the probability state; an MPS likelihood state unit for generating the next likelihood estimation event if an MPS occurs and updating the likelihood state is required; an LPS likelihood state unit for generating the next likelihood estimation state in the case where an LPS occurs and the likelihood state is to be updated; a switching unit to generate a switching indication if the MPS is to be switched; and an updating unit to generate an update indication when the probability was less than or equal to the first predefined value. The apparatus of claim 51, wherein the MPS probability state unit the next probability estimation state generated by a current probability estimation state increased by an integer in a range of values or is lowered, based on the value of the current probabilistic state. Apparatus according to claim 51, wherein the switching indicator includes a signal. Apparatus according to claim 51, wherein the switching indicator is activated if the probability state is less or equal to a first predetermined value or a second one predetermined value. The apparatus of claim 51, wherein the update pointer includes a signal. Apparatus according to claim 48, wherein the bit generation unit the biter generation logic involves to perform a conversion between uncoded bits and coded bits. The apparatus of claim 56, wherein the bit generation logic a first output signal to to provide the codeword and a second output signal to the Size of the codeword display. The apparatus of claim 56, wherein the bit generation logic the next Start and stop values generated to set the interval. Apparatus according to claim 58, further comprising the starting and stop registers, which is connected to receive the start and stop values, generated by the biter generation logic, where the startup and stop registers to the inputs the Biterzeugungslogik are connected. Apparatus according to claim 48, wherein the bit generation unit codewords generated to clear at the end of the coding. Apparatus according to claim 48, wherein the generating unit continue a clearing logic comprises to generate a codeword to a predefined codeword in response to spend that one Räumanzeige is signaled to clear the Biterzeugungseinheit. Apparatus according to claim 61, wherein the clearance display a cleanroom signal includes. The device of claim 61, further comprising a MUX comprises that is connected to a codeword that represents encoded data and to receive a predefined codeword for clearing, wherein the MUX is still connected to receive the clearance indication to between the input signals as the output of the bit generation unit select. The device of claim 48, further comprising comprising: a State expansion unit operating in response to a probability estimate and the finisher (FSM) state responds to a first split value and the next Probability estimation states for occurrence of an MPS and an LPS when a probability estimation update is required; a comparator to the first split value compare with the incoming code stream, the comparator outputs a second split value; a probable logic, which are connected to the comparator and the state expansion unit is to produce a probable indication; a mux that is connected to the next Probability Estimates and to receive the probable indication, where the MUX is one of the next Probability estimation states based on the probable display outputs; a codeword generation unit to convert codewords into Response to the first split value, the probable indicator and generate an interval display. Apparatus according to claim 64, wherein the interval display a start value and a stop value, a start and an end for indicates the interval respectively. Apparatus according to claim 64, wherein the expansion unit comprising: a first unit to assign a mask value in response to a probability estimate produce; a second unit to get a value in response to to generate the FSM state; a gate logic connected is to logically ANDieren the outputs of the first unit and the second unit; a third unit connected to an output of the gate logic and to receive a selection signal that responds to it produce; an MPS unit according to a next state, in response to the selection signal and the FSM state the next probability estimation state for the Case when an MPS occurs and an update is required; an LPS unit according to a next state, in response to the selection signal and the FSM state the next probability estimation state for the Case when an LPS occurs and an update is required; a fourth unit to answer in the Selection signal and the FSM state to generate a display which subinterval with an occurrence connected to an MPS; and a fifth unit to the second Split value in response to the select signal and the FSM state to create. An encoder for processing information, wherein the encoder comprises a Probability estimation table about probability estimates to generate in response to contexts; an entropy coding table, which is connected to the probability estimation table at least one ad in response to the probability estimate and a set of outputs that are the most likely Symbol (MPS) that occurs and a set of output signals that associated with the least probable symbol (LPS), which occurs, with each set of output signals Codeword, a size indicator of the codeword and another Entropy coding state includes; a Logic connected to the entropy coding table and the is connected to receive encoded data and uncoded data, which are input to the encoder, where the logic is a bitstream in Response to at least one signal and the coded data during the Decoding issues and an ad during encoding in response on each of the uncoded data outputs to be used as output signals of the Encoder to output either the set of output signals, the communicating with the MPS, or the set of output signals, which communicates with the LPS. An encoder according to claim 67, wherein the probability estimation table a first next probability estimation state for use as next Probability estimation state outputs when an MPS occurred and an update of the probability estimate perform and the probability estimation table is a second next probability estimation state for use as next Probability estimation state outputs when an LPS occurred and an update of the Probability Estimate perform is. The encoder of claim 67, further comprising a context memory comprises which is connected to probability estimation states of the probability estimation table and logic in response to contexts. An encoder according to claim 69, wherein the context memory an indication of the most likely Symbols to the logic in response to each of the contexts outputs. Method for coding data by means of an FSM encoder, which includes the following steps: a probability estimate is retrieved from a Probability Estimate Lookup Table (LUT) in response creates a context; a codeword, a size indicator of the codeword and a next one FSM state display as well as an MPS and LPS are responded by an entropy-coding LUT the probability estimate and output a final state machine state; the codeword, the size indicator of the codeword and the next FSM status indicator associated with either the MPS or the LPS are based on whether the probable ad is activated is or is deactivated, respectively selected; and the selected codeword and the size indicator are issued. The method of claim 71, further comprising the steps of: a first indication of a next probability estimation state is output if the MPS occurred and a probability estimation update is required; and a second indication of a next probability estimation state and an indication that the MPS should be toggled if the LPS occurred and a probability estimation update is required is issued. The method of claim 72, wherein the first and the second ad next Probability estimation states of the probability estimation table be issued. The method of claim 72, further comprising the step the selection between the first display of the next probability estimation state, the second ad of the next Probability estimation state and the current probability estimation state based thereon, whether the input bit is an MPS or an LPS, and based on the current probability estimation state, includes. The method of claim 74, wherein the step the selection further comprises the following steps: the first ad the next Probability estimation state will be chosen, if an MPS occurred and the current probability estimate state is less than or equal to a predetermined state; the second display of the next Probability estimation state will be chosen, if an LPS occurred and the current probability estimate state is less than or equal to the predefined state; the first display of the next Probability estimation state will be chosen, if an MPS occurred and the current probability estimate state greater than the predefined state is and one or more bits are output become; the second indication of the next probability estimate will be chosen, if an LPS occurred, the current probability estimate state greater than the predefined state is and one or more bits are output become; and the current probability estimation state will be chosen, if the current probability estimate state is greater than the predefined state is and no bits are output. The method of claim 71, wherein the step the generation of the probability estimate the following steps comprising: one Context memory is addressed with a context; a current one Probability estimation state and an indication of a most likely Symbols for the Context is procured or procured again; the current Probability estimation state is converted into a probability estimate; and the probability estimate is output. The method of claim 76, wherein the probability estimate is a Probability class includes. The method of claim 71, further comprising the step the generation of a probable display, based on a comparison between a bit to be coded with the MPS. The method of claim 71, further comprising the following Steps includes: of the next MPS value is determined; and the next probability estimate value will be chosen. A method of encoding symbols, comprising the steps of: context memory being addressed with a context; a probability estimation state and an indication of a most probable symbol for the context is retrieved; the probability estimation state is converted into a probability estimate; the probability estimate is issued; the next probability estimate state is output if a most probable symbol (MPS) occurred and an update of the probability estimate state is required; the next probability estimation state and an indication that the MPS should be switched if a least likely symbol occurred and a probability estimation update is required is output; a codeword, a code word size indicator, and an indication of the next FSM state for both an MPS and a least probable symbol (LPS) is obtained from an entropy coding table in Ant word on the probability estimate and a state of the final machine output; a probable indication is generated based on a comparison between a bit to be coded with the MPS; the code word, the code word size indicator, and the next FSM state indication associated with either the MPS or the LPS is selected based on whether or not the probable indication is respectively enabled or disabled; the next MPS value is determined; the next probability estimation value is selected. Encoder for encoding and decoding information, the encoder comprising: a combined probability estimate and a finisher-biter generation table, at least one signal in response to a probability estimation state and a set of output signals, the most probable symbol (MPS) that occurs, and a set of output signals, which are associated with the least probable symbol (LPS), that occurs, generating, each set of output signals a codeword, a size indicator of the codeword and a state of next entropy coding; a Bit logic connected to the combined table and connected is to receive encoded data and uncoded data in the encoder is input, the bit logic being a bitstream in response to the at least one signal and the encoded data while of decoding and an indication during encoding in response on each bit of the uncoded data outputs to output the encoder either the set of output signals that with the MPS, or the set of output signals that to connect to the LPS.