JPS6376525A - Method for probability fitting in arithmetic encoding system - Google Patents

Abstract

(57) [Abstract] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

DETAILED DESCRIPTION OF THE INVENTION A. Field of Industrial Application The present invention relates to a technique for encoding and compressing input data using an arithmetic encoding method and restoring original data through decoding based on the arithmetic encoding method.

B. Prior Art and its Problems In order to obtain a desired data transfer rate or to store data in limited memory space, it is necessary to compress data to reduce the number of bits. Compressed data is later decompressed. This step is called de-compressing the data.

One of the application fields of data compression/decompression technology is optical imaging. In this field, it is necessary to handle large amounts of information such as the darkness and shadow of a single pixel, and to transfer this information at high speed.

It must be memorized for future use.

Arithmetic coding is one technique for accomplishing data compression/decompression. In arithmetic coding, the decision
As n) are encoded one after another, intervals along the number line that are smaller and encompassed by previously defined intervals are defined. Regarding arithmetic coding methods, several papers have been written by the inventor of the present invention. G, G,
“An Introd” by Langdon, Jr.
Production to Arithmetic Codi
ng”, IBM Journal of Re5ear
ch and Development, vol.

28, n, 2. March 1984, pP, 135-149
,Andori,R,Helman,G,G,La
ngdon, Jr., J. J. R15sanen
Author “Arithmetic Compression”
ode Control Parameters
Approximation”, involume
23, Mail, April 1981, pP, 5112-
5114 is an example. The prior art will be explained with reference to these.

As stated in the above paper, according to the arithmetic coding method, each decision has multiple possible exclusive outcomes (o
utcome, or event). Each result or event is symbolized and represented in the form of data. For example, in an optical imaging environment, each decision corresponds to whether a given pixel is black or not. The result of the judgment is represented by a Y (i.e., TES) symbol if the pixel is black, and N (i.e., No) if the pixel is not black.
represented by a symbol. Therefore, a plurality of judgments can be represented by one symbol string, for example, YNYYN, . . . .

According to the conventional encoding technique, a current interval along a probability line is defined.The first current interval is from O to 1. The current interval is divided into segments. At this time,
Each segment has one possibility for subsequent decisions.
corresponds to one result.

If there are only two possible outcomes for each decision, then
The current interval is divided into two segments.

The length of each segment is based on its associated probability. Each probability may be fixed or may be adapted with input of one judgment data.

Compression efficiency is improved by associating larger segments with more frequently occurring symbols. The former of the above documents (“An Introduction
o Arithmetic Encoding' describes an example of 4-symbol arithmetic encoding.

There, each decision has an "a"'' event rate of 50%).

II l, 11 event (probability 25%), II c11 event (probability 12.5%), or “d” event (probability 12.5%).
5%). Representing these four events in binary numbers requires two bits for each event, each representing 00. OX, 10.11. For three events, such as aab, which is extremely likely, the honest data without encoding would be 0 00 01, requiring 6 bits.

However, as can be seen on page 137 of the above article, according to the arithmetic coding method, the sequence aab is represented by the number 001. Instead of 6 bits, information can be expressed in 3 bits. Bits are thus saved when related events occur in succession with relatively high probability.

However, if a large number of low-probability events, ie, relatively short line segments, occur, the conservation effect decreases. When using the above probability, the event sequence dd is.

While it is represented as 1111 in the form of unencoded data, it is represented as 111111 according to the arithmetic encoding method. If large segments effectively correspond to frequently occurring events, then the conservation effect achieved when more probable symbols occur outweighs the disadvantage of requiring extra bits for less probable symbols. I have some left over. Therefore, it is important to ensure that the associated probabilities (and their corresponding segment lengths) reasonably track the actual probabilities of individual events.

Conventionally, various techniques have been proposed for estimating event probabilities while collecting a large amount of history of judgment data. References describing such techniques include G.
“Method for Coding counts” by N, Jr. and J, J. R15sanen et al.
to Coding Parameters” (IBM
Technical Disclosure Bull
etin Vol. 22 No. 7, December 1979, No. 288
0 to 2882 pages). According to this literature,
A counter is used to detect changes in the probability of a monitored symbol from its occurrence and to modify the least probable symbol (LPS) probability q accordingly. especially,
q is changed to equal the count of one symbol divided by the total number of symbols counted during one symbol string. That is, if k is the count of one symbol and n is the count of both symbols, then the probability of a symbol changes based on k/n.

Other references by Langdon and R15sanen et al. “Compression of Black Wh
ite Images With Arithmetic
Coely “(IEEE Transactions
onCommunications, COM-2
9, No. 6, June 1981) describes the adaptation of probability in arithmetic coding. In discussing adaptation to non-stationary statistics, this document
Section 5 begins as follows: The current estimate of the probability that symbol S (i) is 0 given r consecutive 0s in state 2 consisting of 1s is p = c Q / c. Assume. However, co
is c(Ol z, s (0), -----, 5(
t)), and C is the count value defined as C(Z, 5
This is a count value defined as (0), . . . , 5(t). Here, the symbol s (i) is taken. If s
If (i) is 0, check whether p' (r+1)≧0.2. If so, consider that this am is consistent with the estimate for p, update cO and C by 1, and make a new estimate. ...However, ρ'
If (r+1)<0.2, then this observation will probably result in modified statistics, so we should try to change the estimate to a larger value of p. This is done by halving counts co and C before updating them by one. If the received symbol 5(i) is 1, then perform the same reliability test using probability p (r). ...Actually, in order to facilitate implementation, upper and lower limits are set for the LPS count, and
Let each skew value Q(s) indicate whether the count should be halved. 'This document describes that the probability of LPS is approximated by the closest value of 2-Q(S). Here, Q(S) is an integer and is called a "skew number."

Regarding the special probability adaptation method, see Japanese Patent Application Laid-Open No. 1986-196.
Publication No. 014 and patent application filed by the applicant in 1982-28
It is described in the specification of No. 6891.

A general and novel probability estimator adaptation method is presented.

Patent application filed at the same time as this application by the applicant (Title of invention: Probability adaptation method in an arithmetic coding system)
In this specification, references are made to the extent necessary to provide a detailed explanation of the present invention.

In the above patent application, the possible probability value Qe of a certain event is
For example, it is specified in the form of a table. According to the invention related to the above-mentioned application, the prescribed addend value A decreases each time a determination is made. The amount by which the addend value decreases depends on the event. That is, the result of each decision is L P S (less probab
input of M P S (le symbol) or M P S (mo
In a binary application resulting in an input of a re probable symbol), when LPS is input, the addend value decreases to the current Qe value, while when MPS is input, the addend value A (A-
Qe). When the updated value of A becomes less than the predefined minimum value AMIN (which is greater than the maximum value of Qe), the updated value is renormalized again until A becomes at least AMIN. (preferably doubled). The basic concept of the invention according to the above application is to renormalize Q every time A is renormalized. If renormalization occurs following an LPS event, then (LP
The Qe value (representing the estimated probability of an S event) increases. If renormalization follows an MPS event, the Qe value will decrease. By linking the change in Qe and the renormalization of the addend value, the need for counters is eliminated and the time required to change Qe is easily reduced, thus reducing the probability of realism over the entire range of Qe values compared to the prior art. Close tracking of values is possible. Furthermore, it is recognized in the above application that the update procedure may become trapped at certain "bad" J values; for example, at certain "bad" J values, the , which leads to a cumbersome sequence like the one below.

(1) After an LPS event, A is set equal to (bad) Qe.

(2) Until A becomes at least AMIN, (1)
The updated A is doubled (and further doubled if necessary). Then, a higher Qe value than before is selected.

(3) Since A updated in (2) is equal to or close to AMIN, even if only one MPS event occurs,
A falls to a value less than AMIN. As a result, renormalization is required and the Qe value is reduced resulting in a (bad) Qe value.

(4) If the actual LPS probability is much larger than the estimated value Qe, the LPS event is likely to occur again, resulting in Q
e returns to a higher value than the current one.

(5) MPS occurs once again, causing renormalization;
The Qe value returns to a bad Qe value. Same below.

According to the teachings of the above application, "trapping"
The problem is handled by not allowing "bad" values.

However, the drawback of this solution is that "trapping"
A particular number that is "bad" from the perspective of efficiency is actually a good number from the perspective of overall efficiency.

In addition to adapting probabilities based on an updated history of decisions, other issues are relevant to implementations of arithmetic coding.

Examples include "carry propagation" and "borrow propagation." The problem of "carry propagation" should be noted in the case of an arithmetic coding encoder that updates the code stream C with successive decision inputs according to the conventions below.

(1) If the symbol being encoded is an LPS, then C
The value of remains unchanged, and the new current interval is A (new) = Q
It becomes e.

(2) If the symbol being encoded is MPS, C
is updated to become C+Qe, and the new current interval is A (
neIl) = A (previous) -Q e
, that is, the previous interval minus Qe.

Interval A becomes smaller and smaller, and the smaller interval is added to C, thereby increasing the precision of C (ie, the length of the code stream). As long as the judgment data to be encoded is input, the accuracy may be extended without limit.
Although C (and precision) can be of indefinite length,
Since there is a finite amount of memory to store code stream information, carries can be a problem.

In particular, if the code stream value is hundreds of consecutive ones, but only the most recent bits of C are accommodated in the shift register,
A problem arises when C is added to C. It is impossible for a carry to propagate through hundreds of 1 bits. This is because only the latest bits can be accessed. One preferred solution to carry propagation is called bit stuffing and is also outlined in the literature. In the conventional method of bit stuffing,
It has been suggested to insert at least one carry receive bit after a predetermined number of 1 bits.

In a patent application (title of the invention: Data Compression System) filed concurrently with this application by the applicant, an "optimal" software encoder is described.

According to it, each time a decision is encoded, the value of the code point remains the same or decreases. Therefore, if the code stream Cs contains a string of zero bits and a subtraction is required, the borrow will propagate beyond the length of the shift register that only contains the most recent part of the code stream. there's a possibility that. Such "borrow propagation" is described in the above patent application by converting all Hex'OO' bytes in the encoding code stream into
It is processed by converting it to 'F F' and a carry bit. Borrow propagation thus becomes a carry propagation situation. It is a desired objective to generate carries and borrows without sacrificing encoding efficiency and without requiring large numbers of extra bits.

Another aspect of arithmetic coding methods is the desire to insert control words into the code stream6, i.e., to allow an external control device to interrupt the code stream and insert control words. desired. At the decoder end, another control device should be able to detect the control word and remove it from the received data string. Regarding insertion of control words, (a) prepare a large number of possible control words, and
(b) It is desirable to identify the presence of control words without substantially reducing encoding efficiency. In the above patent application,
A 32-bit register is provided to accommodate a portion of the code stream on the way to the buffer. The lower 12 bits (0 to 11) are the decimal part of the code stream that is aligned with the current value of A. Bit 12 corresponds to the spacer bit.
2o is the next 8 bits (1
(byte) code stream data.

Bit 21 is the carry receiver bit.

Of the two bits preceding bit 21, bit 22
is used to identify whether a control word has been inserted. Bits 31-24 are flag bits, bit O
As data is input from , it shifts to the left. (After eight shifts, the flag bit is in the bit position that indicates that one byte of data is ready to be sent to the buffer.) With a single spacer bit, in some situations two may be required to be inserted.

Means for Solving the C6 Problem The encoder and decoder for arithmetic coding according to the present invention provide probability adaptation methods as described in the above-mentioned patent volume vA (Title of invention: Probability adaptation method in an arithmetic coding system). Take up adaptation. In particular, probability adaptation is facilitated there by selecting possible Qe values that enhance the performance of the encoder and decoder.

In this regard, it should be mentioned that the present invention relates to a binary arithmetic coder in which a probability estimator is incorporated into the arithmetic encoding process. That is, in the present invention, the value of the summand corresponds to the current interval along the number line, and the value of Qe is updated in response to renormalization of A, the value of the current interval. The addend value (that is, the value of the current interval) A is the minimum value A
In order to determine when Qe should be updated when it falls below MIN, the first bit representing the value of AMIN is set, and the following bits are not set. For example, AM I N is Hex
'l OOO', that is 1 00000000 0
Represented by 000 (binary number). In this way,
When the first bit changes to O, renormalization and Qe update are indicated. In this way, the renormalization test becomes a single bit test. Therefore, the present invention requires a simple test to determine when to change Qe in addition to when renormalization is required. US Pat. No. 4,467,317 suggests testing one bit for summand renormalization. However, integrating single-bit tests for probability adaptation and renormalization provides significant benefits over the prior art.

In other words, to implement the above single-bit test, select the value of AMIN, then change it by a scale factor, and then change the most significant digit of AMIN (
The bits in the same 9 digits as A are 1 and the bits in other digits are 0.

Other numerical values are also scaled according to this scaling. In the preferred embodiment, A is between 0.75 and 1.5; In short, the range of A may be appropriate as long as AMIN can be expressed so that a single-bit test can be realized.

Moreover, the present invention further enhances the probability adaptation method disclosed in the above-mentioned patent application in several aspects. First, a table containing Qe values has the following characteristics.

1. Each Qe child table entry has a 6-bit coding parameter, 1 bit of which is the MPS
Show your sense of style. The Q index consisting of the remaining 5 bits identifies the corresponding Qe value.

2. For each entry, the length of the Qe value is preferably 1
It is 2 bits. Only 5 bits of any Qe value are set. The least significant bit of each Qe value is always set (this facilitates hardware implementation). The selection of bits to set for the various Qe values is determined in part by the consideration of limiting the number of gates that must be passed to obtain a Qe value from a Q index to a small number.

The use of 6-bit coding parameters is important in that it complies with existing macros and predefined cells. Furthermore, if the number of bits used as coding parameters is less than 6, the table will be very coarse, leading to poor results for stationary statistics. Using more than 7 bits as a coding parameter requires an additional increase in chip area and increases the cost.By appropriately choosing the sQe value, the number of required Qe entries can be reduced to a relatively small number ( For example, 30) can be maintained, and an improvement in encoding efficiency and a considerable simplification of implementation can be achieved.

Furthermore, in order to avoid the problem of "trapping" of Qe values, the present invention proposes the following. As stated in the above-mentioned patent application (Title of invention: Probability adaptation method in an arithmetic coding system), AMIN/2
Certain [bad] J values in the form are prohibited.

However, in the present invention, it is allowed to include "bad j values" in the table that contribute to performance except for capturing "trapping". To avoid “bad JQe”
In response to an LPS renormalization under a value of 0, the Qe value is increased to a predetermined table value such that more than one MPS renormalization is required to return to the stray Qe value. The invention is
If you do not do this, it will cause "trapping"Q
The purpose is to preserve the e value.

Furthermore, to facilitate software implementation of encoders and decoders according to the present invention, negative Q
The e expression indicates that the sense of MPS is 1, and the positive Qe expression indicates that MPS=O. In particular, using this method there is no need to mask the sign bit, saving processing cycles.

Yet another object of the invention is to improve the allocation of bits in a shift register that accommodates a code stream on its way to a buffer memory. In this regard, two or more spacer bits are set to separate the fractional part of the code stream and the r bytes to be sent out. Including more than one spacer bit eliminates the possibility of a Hex'FF' sequence being followed by another Hex'FF' sequence.

Furthermore, by increasing the number of spacer bits, 1
By simply filling a bit, the bit can serve to receive or receive a carry or create an escape code for a control word.

According to one embodiment of the invention, the X register containing the code stream data initially allocates bits as follows.

X = 0OOO000f 00000000 ss,
When the xxxxxxx xxxxxxx001 byte is ready to be sent to the buffer, the X register is configured as follows.

X=f←0OO0000c bbbbbbbb ss,
xxxxxxx xxxxxxxool not one (11
The use of two spacer bits (denoted as "ss") eliminates the possibility that more than one filler bit may be required.

Therefore, by using two spacer bits, there is no need to transmit extra bits and the efficiency of encoding is improved. Furthermore, the present invention provides an efficient system in which control words can be inserted into the code stream by an external control device before encoding and transmission, and can be withdrawn from the transmitted stream before decoding. A perfect escape is realized.

Furthermore, the present invention proposes that the first two bits of the code stream are OO, so that the objective of facilitating decoding is achieved.

Finally, the invention addresses the above object in an arithmetic coding system in which the encoding and/or decoding can be performed interchangeably by hardware or software according to different conventions.

Here, I will once again explain the concept of spacer bits.

To prevent carry propagation, one bit of O is usually inserted between bytes.

On the other hand, in the present application, regardless of the possibility of carry propagation, the bits of the code stream are determined to either (a) remain at their current value in response to a binary event, or (b) a trailing byte part holding the bytes to be sent to the storage means; (c) a trailing byte part holding the bytes to be sent to the storage means; At least one spacer bit is allocated between parts (a) and (b).

and means for shifting code stream data through the shift register in response to encoding a decision event, and means for transmitting data one byte (n bits) at a time to storage means.

This configuration facilitates byte-by-byte processing.

In particular, when two bits 00 are assigned as spacer bits, the two bits are normally only changed to 01 even if a carry occurs. Therefore, by causing a code other than 00 and 01, that is, 11 or 10, to appear as an escape code in the spacer bits, it is possible to instruct the decoder of the arithmetic code system to temporarily stop decoding. On the decoder side, for example, after sending out the currently held intermediate data to an appropriate storage means, it waits for a new instruction. This instruction may be, for example, error correction. Preserving such escape codes is extremely important when multitasking is performed in an arithmetic coding system.

D. Embodiment FIG. 1 shows an overall apparatus 100 for compressing and decompressing data, including an arithmetic encoder 102 and a corresponding arithmetic decoder 104.

When compressing data, the device 100 first compresses long-term data (DA
TAIN) is received. Kugata data is based on binary judgment (b
It can be expressed as a sequence (YN) of initial decision). Here, each outcome, or event, has a probability. The apparatus 100 then characterizes the string by turning it into an encoded bit string. By encoding the decision string with built-in probability information, the compressed bit string can be transferred more quickly than the original data, and the compressed data requires less storage space.

a large portion of the data must be transferred at high speed by some transfer device or medium (e.g., element 105);
Or compress data in applications where most of the data must be stored in limited memory (or where most of the data is stored and then transferred at a low modulation rate). It is very important to use One environment where such compression is particularly important is
One example is the field of video data processing, and more specifically, teleconferencing. In teleconferencing, information such as pictures must be transmitted quickly from one location to another.

After the encoding data is transferred to the desired destination, the data is decompressed. That is, the decoder 1.4 restores the original data or some representation related to it. In fact, the decoder 104 decodes the encoded code
Examining the stream one byte at a time, the encoder 10
Cancel the procedure performed in step 2.

In Fig. 1, input data DATAIN is first input to model 1.
Processed by 06.

Conventionally, various types of models have been discussed.

The model generates a context state S and a binary decision B ITIN for encoding by Q coder 102 .

Based on the past BITIN decisions for a particular context S, the Q-coder has already generated an estimated probability that the BITIN decision is 1 or 0, and this estimate is used to encode the BITIN. For example, in a facsimile, each piece of input data corresponds to whether a given pixel is black or non-black. An estimate of whether a given pixel can be expected to be black or white is generally obtained from neighboring pixel values, which are already the encoding method. Q-coders and Q-decoders make an estimate of the probability that a given pixel is black or non-black based on previous pixel values for the same neighboring pixel values as successive data are processed. , the relative probability values of more probable states (referred to as MPS or non-Qe events) and less probable states (referred to as LPS or Qe events) may change or even be swapped. be.

That is, if MPS is black, then the non-black fact (inst
ance), the probability of the astigmatic state becomes higher, that is, it may become dominant. In that case, the MPS changes from a thermal state to an astigmatic state.

The Q coder 102 uses an arithmetic coding method to code model 1.
Convert the status S and B ITIN information from 06 to compressed data. Arithmetic coding uses estimated probabilities that have already been generated by the Q-coder and stored in an appropriate form following previous BITIN decisions for state S.

2 and 3 respectively show an overview of encoding, FIG. 2 shows an encoder most suitable for hardware, and FIG. 3 shows an encoder most suitable for software.

In FIG. 2, the code point is
Initially, it is located at the lower limit of the given interval.

The Q segment associated with the occurrence of an LPS event is also at the bottom of the interval. P segments related to MPS events are at the top of the interval. C(n) corresponds to the code stream value at time n. A(n) corresponds to the value of the current interval at time n.

For each decision, the optimal hardware encoder (shown in FIG. 2) follows a first order convention.

In other words, if the judgment event (shown as YN in the figure) is an MPS event, (a) C(n)←C(n-1) 〇(b) A'(n)←[A(n-1) Q ].

If the event is an LPS event.

(a) C(n)←C(n-1) (b) A(n)←Q Whether it is an MPS event or an LPS event, the hardware performs a processing cycle to respecify the value A of the interval (i.e. range). spend time on. Furthermore, for MPS, the code point is the value Q
is moved in increments, i.e. Since the hardware can process updates of A and C in parallel, such hardware only needs to spend one processing cycle for any decision. On the other hand, if the hardware LPS were configured to move the code point for each event, it would take two processing cycles to determine C←C+(A-Q) each time the code point must be moved. It becomes necessary. Considering that limiting the number of processing cycles is critical in hardware operation, and that moving the code point in case of an LPS event results in a lot of cycle time, it is It turns out to be optimal to shift the code points in case of MPS events.

The encoding process of FIG. 3 represents a preferred "software" scheme, with the same ordering of P and Q segments. However, in response to an LPS event, the code point moves downward (ie, toward smaller numbers).

In this scheme the code stream is represented by C. C(n)+A(n) is equal to C(n).

If some part of the final interval is subtracted from Ci, then C(n) or '6(n) can be decoded by a single decoder to recover the same set of input decision events. That is, the decoder (m I D +
7) Which state is M for 7 coder 104)?
Given a first input indicating whether it corresponds to a PS event and a second input indicating the current Q-value for the code stream being decoded, the decoder
n) or "6 (n) minus some portion of the final interval can be processed to produce a YN output sequence corresponding to the YNN deer sequence to coder 102. 110, and the original data or a replica thereof is produced as output DATAOUT.

In the scheme shown in FIG. 3, the number of cycles required for software processing is kept low because the code points are moved during an LPS event.

In Figure 4, there are four encoders 200.202.2°4.20
6 is shown. The encoders 200, 204 each MPS
Encoding is performed according to optimal hardware rules that move code points for each event. Of these, the former is implemented in P/Q symbol order, and the latter is implemented in Q/P (reverse) symbols. Encoders 202, 206 encode according to optimal software rules in which code points are moved for each LPS event. Among these, the former is P/
The latter is implemented in Q symbol order, and the latter in Q/P (reverse) symbols. encoder 20
The code streams produced by 0,202 can be the same (or at least compatible). It is designated as C. Also, according to the invention, the code streams produced by encoders 204, 206 can be the same (or at least compatible). It is represented as 2. 2 and C can be derived from one by the formula C'=A(o)-Z. The calculation of this equation is explained with the value of A(0) in inverter 208 set to 1. Code stream C takes into account optimizations in the hardware case (e.g. no inconvenience (u
nawkward)) is directly decoded by the decoder 210. Also, Code Stream Z
is a decoder 21 considering optimization in the case of software.
It is directly decoded by 2. 4 encoders 200~
Whatever code stream 2o6 generates,
It can be seen that either decoder 210 or 212 can be used for decoding. Some of the code streams are processed by inverter 208 on the way to the decoder.

It is worth mentioning here that two other decoders can also be implemented, namely a Q/P hardware decoder and a P/Q software decoder; various embodiments of these are described in the above patent application (invention It is also explained in the name: Data Compression System).

■ Encoding and decoding of continuous events with finite precision To make the description in this section easier to understand, the following definitions are provided. In most cases, variable names have the same meaning.

1 C = pointer (code point) to the code stream, i.e. the current interval Cd = decoder code stream with base 1ine Qe(i) = L for the i-th encoded symbol
PS event estimated probability Pe(i) ==+: MPS event estimated probability A(i) for the i-th encoded symbol = summand for the i-th symbol (that is, 1 interval) Si = i-th symbol n(i) = cumulative count of renormalizations up to the encoding of symbol Si R(i) = renormalization factor for the i-th symbol δ(C) = delta function of Kronets force − and Equivalence (1 when the condition is true; 0 when it is false) ε; Minimum possible change to the current Q value Under the above definition, the following relationship applies.

Pa(i)=A(i)−(A(i)XQe(i))R(
i) = 1/2”) i = R(i)2-12 (for 12-bit precision) 11A,
P/Q Hardware Encoder and Decoder If the symbol ordering is P/Q, the optimal hardware encoder points to the bottom of the current interval.

Code stream C is expressed by the following equation.

C=ΣR(i)A(i)Qe(i)δ(Si
=M) In other words, the value C is determined by considering each successive decision event (or symbol). If the subject symbol corresponds to an LPS event, then
The Qe value at the time of the subject symbol is multiplied by the renormalization factor.

The renormalization factor is related to the fact that the interval size is kept within a predetermined range ζ, for example between 0.75 and 1.5. That is, the interval size is expressed as an addend (denoted as A), and its value is adjusted so that it remains within a predetermined range. The value of the i-th summand, that is, A(i) is 0
．． When it becomes less than 75, the multipliers are multiplied by 2 (or A(i) is modified in some other way) as many times as necessary to return within the predetermined range.

By keeping the value of A at or near 1, the multiplication factor AXQ can be approximated as A, simplifying the calculations for A and C.

Renormalization may occur each time a symbol is encoded.

Indeed, each time the interval size is set to AXQe times Qe (which, by definition, is less than or equal to AXPa and therefore less than or equal to 0.75), the value of A(i) is (together) and renormalized, e.g., back into the range as above.

In response to an MPS event, the size of the current interval A(i) is estimated as [A(i-1)-Qe]. This value may or may not be less than 0.75. In this way, in the case of an MPS event, there are cases where renormalization is necessary and cases where renormalization is not necessary. The number of renormalizations of the current interval is accumulated, and the C value can also change in the same way as the interval value (for example, by doubling the same number of times) by R(i), that is, R(i) as described above. Guaranteed.

Therefore, the C value when the symbol Si is encoded is for the P/Q hardware encoder and for the MPS
It is incremented upon an event, and the increment is determined by the renormalization factor and the Qe value for all preceding symbols.

The P/Q hardware decoder solves the above process according to the following equation.

Cd=C−ΣR(i)A(i)Qe(i)δ(Si=
M) where Cd is the code stream value after the effects of certain events have been removed.

P/Q hardware decoder.

If Cd<A(i)Qe(i), decode LPS.

nB, P/Q software, 1 and recovery device P/Q
The software encoder points to the top of each current interval, and the software code stream C is determined by the following equation.

Te=A(0)−ΣR(i)A(i)P e(i)δ(S
i=L), the value evaluation starts from A(0), and A(0
) to subtract the sum term in the above equation. The addend of the sum term is A
, 4 current P value, and renormalization factor for the preceding LPS event.

Subtracting the final interval value A(f) from the result C yields C as derived in the P/Q hardware code stream.

The P/Q software decoder follows the equation:

However, the comparisons required to decode LPS symbols are cumbersome. Namely.

Cd<A(0) A(i)+A(i)XQe(i) Or, subtract A(0) from both sides of the above relational expression and get Cd-A
(0)<-A(i)+A(i)XQe(i).

If C' d = Cd - A (0), then C' d < C-
A(i)X(1-Qe(i))].

Both C16 and [A(i)X(1-Qe(i))] are negative, but their absolute values range from 0 to IA(i)l. Therefore, the operations for the decoder are fixed precision operations. The processing of the software decoder can be summarized as shown in Table 8 below.

Table 8 T4-AXQe A+-A-T If C'd<A (LPS decoded) Cd4-C'd-A 4-T renormalize A and C'dlse (MPS decoded) renormalize A and C'd if
needed+ndif The above calculation is conveniently simplified by setting the value of A(i) to approximately 1.

8. Encoder Registers and Decoder Registers FIG. 5 shows an X memory register 300 suitable for storing code stream information. register 300
contains 32 bits, which are allocated as follows. That is, eight bits 31-24 are flag bits. The 31st bit represents the ``sign j bit.'' Bit 24 also serves to receive and take any ``carry'' that occurs in the process of preparing to send out the next byte. In the case of normal 8 shifts each, (b
Bits 23-16 (identified as bbbbbbbb) represent the byte to be sent to the buffer memory. If the preceding byte is 'F F', only seven shifts are required and bits 24-17 are sent out. Bit positions 14.15 are assigned spacer bits to provide a delay between the bit position for the byte to be sent and the bit position of the data that is further computed with the summand. Bits 13-2 represent the most recent portion of code stream data.

It is this part that is subject to addition (or subtraction) using the numerical value of the register that contains the value of the current interval (addend). Bits 13-2 are the "fractional part" of the code stream
Bits 24-14 correspond to the "integer part" of the code stream.

Register 300 is called the X register and contains the latest encoding portion of code stream O8.

In some cases, the bits in the X register were encoded before the bits in the X register were encoded. These early encoded bits pass through the fractional part of the X register into the integer part and from there to the buffer memory. The buffer memory stores the preceding bytes in this way, but the number of bytes is limited.

If desired, the bytes leaving the buffer memory may be transferred to storage or to another location where decoding is being performed.

As indicated above, data is organized as bytes and sent out as bytes.

This is accomplished by flag bits. By initializing the eight flag bits to 00000001, the one bits are shifted as successive b bits are shifted into the integer portion of register 30o. When the leftmost flag bit becomes 1, the contents of the X register are determined to be "negative." The next time a shift occurs, the integer in the X register 300 is entered into the buffer memory.

Preferably, the buffer memory (not shown) is a memory that stores, for example, 256 bytes.

Buffer pointer BP identifies the most recently entered byte into the buffer memory.

In addition to the X register, A for storing the current interval value
There is a register. As mentioned above, the current interval is maintained within a predetermined range, for example between 0.75 and 1.5. The A register has a 12-bit "fraction" part (appended with two 0 bits) that is aligned with the fraction part (appended with two 0 bits) of the X register.
(with two O bits) and also includes an integer part.

Aligning the fractional parts of the A and X registers facilitates various calculations performed when updating the code stream. Each time the interval is renormalized back into the given range.

Reiterating that the code stream is renormalized in the same way to preserve its relative values, if the interval size is set between 0.75 and 1.5, the renormalization Recall that it simply means a shift some to the left (ie, multiplying by 2 means adding together).

After the code byte is set (and there is no carry), the contents of the X register 300 are ANDed with the appropriate hexadecimal number and the bits of the code byte are removed. Also, the X register (written in hexadecimal) is 100
Bit 24 (of the flag bits) is definitely set to 1 since it is set to calculate the (7) XOR with 0000.

FIG. 6 shows a 32-bit decoder register 400 used in the P/Q hardware implementation.
It is shown. The bit allocation is as follows. first,
There are two leading 0 bits, followed by 12 "fractional" bits, followed by two mm bit positions and eight new data bit positions, and the lowest eight bits are flags.
Corresponds to bit. Register 400 is a full word;
It can be divided in various ways, such as half words or bytes. The 12 fractional bits are stored in the decoder's A register. Aligned with the fractional bits of the summand.

After a new data byte has been shifted into XC (bits 31-16), the new data is input into the high order bits of XNEW (bits 15-0) and, if no carry has occurred, is set to 1.

That is, the following formula is true.

XNEW=SLL B 8 XFLAG=1 When the low byte XFLAG becomes 0, a new compressed data byte is sought.

■D, Carry and Borrow As can be seen from the above explanation of the encoder and decoder,
Where a difference occurs in the code stream is where a carry or borrow occurs for a given P,Q deal.

It should be noted here that carries and borrows are prepared by appropriately inserting one or more bits (but smaller than one byte) at byte boundaries.

As a result, any carry or borrow results will not propagate beyond the previously sent byte. Therefore, there is no need for the buffer pointer to go back to past bytes. The pointer may advance to each subsequent byte as it is input into the buffer memory.

The problem with carry propagation is when the value of the code stream is incremented and updated, and there is already one or more consecutive bytes of consecutive 1's in the encoding. In this case, the addition results in carry propagation. To avoid this situation, the present invention packs bits into bytes to take the carry that may occur.
, of which B is buffer n+1n
-1 in memory and the buffer pointer is byte Bn-1
Suppose we are identifying . And suppose that byte B is in the integer part of the X register and byte n B is in the fraction part of the same register.

If the value of n+1 byte B is 'FF' (in hexadecimal), bits are filled in the n+1 position at the beginning (most significant bit) of the subsequent byte B. B , B is so n
n+1 are respectively 11111111 ('FF'), then the present invention inserts n+1 bits at the beginning of B, and as a result, the new encoding method data example becomes 111111.
11.01111111.1...

In this way, if necessary, the receiver is 0 to receive a carry.
bits are inserted. When a decoder detects a byte with all bits being 1, it recognizes that the following low order bits are insert bits and takes action to generate the appropriate code stream.

The borrow problem occurs when decrementing a code stream containing bytes where all bits are O bits. For example, three consecutive bytes Bn-1, Bn
, Bn+, where all bits in the central byte are O.

At this time, 1 is from B byte to preborrow (pre
-borrow), and all eight bits of the B byte are converted to 1 bits. The bit to be filled is inserted as the new first bit n+1 of byte B. This new leading bit is
It serves as a carry bit. Therefore, the data stream transferred from the encoder is:

B -1,11111111,1 (first 7 bits of Bn+) The bit n+1 dropped from the B byte segment is picked up in the subsequent byte segment of the data. A borrow is effectively turned into a carry by a filled (set) bit. In any case,
When the decoder detects a padded bit as described above, it treats the padded bit as a carry. P/Q software code stream compatible with P/Q hardware code stream including bit stuffing
Since the goal is to generate a stream, the code stream must also be generated according to two constraints. First, the hexadecimal 'F F' must be filled with bits.

Otherwise, a byte pattern unsuitable for a hardware decoder would be generated. Then, 'fM
(present) The code stream must be constructed so that borrows can be retrieved whenever bytes need to be retrieved (obviously).

(Here, the current byte is the byte that was transferred from the code register to the code buffer in the previous code byte cycle.) Since one unit is borrowed, there is no need to borrow a digit. The only possible byte value is zero.

Generally, the need to borrow from the current byte is detected by setting a high order "preborrow" bit at the start of a new byte in the code register. For convenience, the pre-borrow bit is bit position 1f.
If set at lP and a subsequent byte becomes writeable, it becomes a sign bit. For example, assume that the contents of the 32-bit code (X) register are as follows.

X register: ooooooooo, poooooooo, XXXXXXX
XX, XXXXXXXXXA register: 000aaaaa+aaaaaaaa When the new byte is completed, the contents will be:

X register: poooooooo, nnnnnnnnn, XXXXXXXX
X+XXXXXXXXA register: 000aaaaa, aaaaaaaa If the code register is positive (p=o), a pre-borrow was used and a borrow from the current byte is required. Therefore, a borrow is taken from the current byte before the new byte nnnnnnnnn is transferred from the code register to the buffer register. With preborrow, the value in the code register is always greater than the A register,
Future borrows will be allowed to be taken from the contents of the code register. Code register is negative (P=1
), there is no need to borrow digits from the current byte, and the unused pre-borrow P is removed.

The contents of the code (X) register are compared to the contents of the A register. If the code register is smaller, two things have been detected. first.

The next byte sent out (nnnnnnnnn) will be zero; second, there may be a need to borrow from the current byte. Therefore, borrows are taken from the current byte and propagated through the zero byte in the register. As a result, the byte that was zero is converted to 'FF'. After sending this 'FF' to the code buffer and shifting the contents of the code register, two preborrows are set.

One is set in the position that will be the sign bit.

The other is set to the bit position that will be the "carry" bit position for subsequent bytes. Therefore, if the contents of the code register are smaller than the A register, then the X register: ooooooooo, poooooooo, 00Px,
xxxx, xxxxxxxxxA register: 000aaaaa, aaaaaaaa.

When the subsequent byte is completed, the X register: poooooooo, Pnnnnnnnn% XXXXX
XXX, XXXXXXXXXA register: 000aaaaa, aaaaaaaa.

The hex digit 'F F' in the buffer triggers bit stuffing, so the pre-borrow bit is written to the stuff bit (carry receiver) location. Therefore, an unused preborrow is equivalent to a carry in the hardware code stream.

If the contents of the code register are greater than or equal to the contents of the A register, then the current contents of the code register are large enough to satisfy any borrow request.

The current part-time job is checked.

If it is 'FF', bit stuffing is caused. In this case, no pre-borrow was requested, so the inserted carry bit is always clear.

The above sequence satisfies all requirements: it prevents borrow propagation and produces a code stream that is compatible with the hardware. Even if all zero bytes were simply converted to 'F F', a hardware decoder would still be able to decode the resulting code stream. However, by knowing ahead of time whether a borrow will be required when the byte to be sent is zero, the resulting code stream is identical to the hardware code stream. In fact, by looking ahead in this way, the presence of 'FF' in the hardware code stream is detected.

The above article by Langdon, R15sannen discusses arithmetic coding in detail and is also cited here.

Arithmetic encoding is a powerful method for compressively encoding data symbols, due to two attributes:

(1) The ability to approach the entropy limit in terms of coding efficiency.

(2) The ability to dynamically change the probability of the symbol being encoded.

As shown above, multiple decisions are encoded to represent points on a number line. The point is associated with a certain interval on the number line that uniquely expresses a particular judgment sequence. Such an encoding method is accomplished by first defining a current interval bounded by two points on a number line. To the first order, the current interval is divided into segments. Here, each segment corresponds to one of the possible events that may occur as a result of the decision. Possible events must be exclusive. That is, no segments overlap. In a multi-symbol environment, any decision can result in one of m (≧2) events. The length of each segment is determined by the relative probability of the corresponding decision event.

That is, the larger the probability of one judgment event, the larger the corresponding segment will be. This is important.

This is because the number of bits representing large segments can be reduced. Therefore, events that should be encoded frequently are expressed using as few bits as possible.

In binary arithmetic coding where m=2, an LPS event is defined as YE for a given YES/No (Y/N) decision.
Corresponds to either S or No symbol. and,
Another event will correspond to the MPS event. Usually, a segment corresponding to LPS is called a Q segment, and a segment corresponding to 1 MPS is called a P segment. The length of the Q segment corresponds to the estimated probability Qe for an LPS event, and the length of the P segment corresponds to the probability (1-
Qe).

By keeping A in the range 0.75 to 1.5, the value A can be approximated as approximately 1.0. Then, the calculation for determining C and A for the above optimal hardware scheme can be simplified as follows.

That is, if MPS is encoded, C4-C+ Q e A4-A-Qe and when LPS is encoded, A <-Q e becomes.

If Ag becomes 0.75 after encoding a certain event,
A and C are renormalized. By renormalizing not only A but also C, the ratio of the code point value to the interval value remains unchanged.

When decoding encoding method data generated according to the P/Q scheme, the following operations are performed.

If C≧Qe, the MPS is decoded and the following calculation is performed.

C4-C-Q e A4-A-Qe If the above conditions do not hold, the LPS is decoded and A4-Qe becomes.

The simplified encoder (and decoder) described above is ideal for hardware implementation. This is because range subtraction (addition) and code stream addition (subtraction) can be performed in parallel. However, even if a software implementation adopts the same conventions for code stream definition and modification as the hardware implementation, it is less efficient. This is because the most frequently taken path (pat
This is because h) requires two arithmetic operations.

Therefore, a highly efficient encoder implementation in software is based on the code stream C
This is achieved by directing the current interval to the upper end of the interval instead of the lower end. The encoding process for software is as follows.

If it is an MPS event, A4-A-Qe So, if it is an LPS event, C4-C-(A-Qe) A←Qe becomes.

Optimal hardware scheme or optimal software scheme
In both schemes, when A<0.75, A
and C are renormalized and Qe is updated.

When considering the above arrangement, note that in any implementation, when A<0°75, A and C are renormalized and Qe is updated accordingly.

We now explain how Qe is updated according to the invention.

, (b) Update the probability estimator 1, update Qe every time the summand is renormalized. Figure 7 shows the probability estimate Qe when consecutive events are encoded and renormalized. It is a figure explaining the update of. In FIG. 7, the ordinate represents the value of the summand A, and the abscissa represents the allowable value of Qe contained in the Qe child table (described below). If the allowed value of Qe starts at 0.42208, then the encoded LPS event results in a summand value of 0°42208. Results of encoding LPS events.

Since the value of the summand is less than 0.75, LPS (causes) renormalization (“LPS renovm”)
) is carried out. As a result, the Qe value increases to 0.46896 and the value of A is renormalized to 0°8441
It becomes 6. In the current example, by multiplying by 2,
Note that a renormalization of A and C is performed; this operation not only has the advantage of being simple, since it can be performed simply by shifting registers, but also because it keeps a count of the number of renormalizations performed. A subsequent MPS event, which also has the advantage of simplicity, results in a value of A of 0.37520, according to the following simple formula:

A 4- A -Q e i.e. A = (0,84416-0,46896
) = 0.3752OA is smaller than 0.75, so
MPS (caused) renormalization (“MPS r
enorm”) is generated.

Qe takes the smaller value 0.42208 and A takes the smaller value 0.7
5040. (There is no need to further renormalize A, since A is no longer less than 0.75.6) The next time an MPS event occurs, A becomes 0.
It decreases to 0,32833 which is less than 75. A smaller value of 0.32833 is selected as Qe. Even if A is doubled, it is still 0.65666, which is still less than 0.75.

If A is further doubled, it becomes 1.31332.

If an MPS event subsequently occurs, the summand is 0.98499.
, which is greater than 0.75, so no renormalization occurs. If more MPS events occur, A is 0.65
666, MPS renormalization can be performed.

A smaller value, that is, 0.30489, is selected as Qe, and the summand A is multiplied by 2 to become 1.
It becomes 3133. If two subsequent MPS events occur, the MP
S renormalization is required.

2. Qe Child Table According to the invention, Qe values as shown in FIG. 7 are stored in the form of a table. In the left column of Table 1, the allowed values of Qe are shown in hexadecimal form. Each Qe value in the table is preferably a 12-bit value and is defined to occupy two bytes.

Divide the Qe value by 5461 (1555 in hexadecimal),
Converted to N-decimal decimal representation. A 5-bit index is sufficient to uniquely identify the Qe value. Moving to an adjacent entry in the table requires a two-byte shift.

The second column of Table 1 lists each listed probability value as L
When shifting following PS renormalization.

1' Indicates how many bytes should be shifted.

It can be seen that the LPS renormalization results in an increase in the probability value by one, two, or three index positions in the table, as the case may be.

An examination of Table 1 shows that the entries therein correspond to the Qe values explained in FIG.

In other words, the decimal number 0.46896 is 16 in Table 1.
Corresponds to base number 0a81. The three entries listed after that, namely 0aO1, 0901, and 07
01 is 0°42208.0.328 in Figure 7, respectively.
33. and 0.30489. If MPS is 1, a negative number of Qe is used.

An alternative table to Table 1 is shown in Table 2. Table 2 shows the qiO values with respect to the allowed values of Qe. This is related to LPS renormalization. By multiplying the Qe values in Table 1 by 4, the qo values are obtained. Furthermore, if MPS is 1, the qo value is negated. qi in Table 2.

The term is called qilps(i 0 ). This is due to the subsequent Qe value (qO) ゛ (for both cases when Mps is 0, i.e. when Qe is positive, and when MPS is 1, i.e. when Qe is negative) and hence LPS renormalization has occurred. Indicates that the index has information related to index (10) that is sometimes applicable.

In Table 2, both the subsequent Qe value and its associated 10 value are found in the preceding index. However, in Table 1, the subsequent index is first determined and then the subsequent Qe value is determined based on it. Therefore, the table index (lookup) procedure for Table 2 is simpler.

Table 3 is similar to Table 2, except that it is intended for the case of MPS renormalization. In particular, in the case of M P S renormalization, according to Table 3, for each Qe value in the table, the subsequent probability value qO and the subsequent index 10 are indicated. In Table 2, the selected numerical values become larger, whereas in Table 3, the selected numerical values become smaller.

It should also be noted that the Qe values included in the table are limited to the range from 0 to 0.5. At 0°5,
A binary event representing LPS becomes MPS, and vice versa. Therefore, the event corresponding to Qe changes. For example, if a white pixel event represents an LPS event, then Qe
The value represents an estimate of the probability of a white pixel event. However, when the Qe value reaches and exceeds 0.5, black pixel events now become LPS events identified by Qe.

The Qe child table can be viewed symmetrically with respect to the conversion point where the definitions of LPS and MPS change.

The choice of acceptable value for Qe depends on several factors. First, a certain value is recognized as a "bad" J value. In particular, a "trapping" of the Qe value
ping)J is not allowed.

Value AMIN/2, AMIN/4, ..., AMIN/
Probability values that are or are close to 2n (where n is some positive integer) are considered "bad" values. For such values, cycles such as the first order can trap the estimation process.

(1) LPS renormalization.

(2) Transition to the first Qe value.

(3) MPS renormalization after only one probable MPS event (note that A was already equal to or close to AMIN), corresponding to Qe Move the value to a second (worse) value (less than the current value).

(4) One more LPS occurs and LPS renormalization occurs.

(5) Return to the first Qe value.

Therefore, the value of Qe is determined by MP following LPS renormalization.
It is preferable to choose a predetermined value δ greater than AMIN/2° so that the probability of performing S renormalization is not too high. One way to achieve this goal is to make the MPS renormalization after one LPS renormalization occur by making all Qe values that are smaller after the renormalization far away from '1000' in hexadecimal. Normalization occurs only after multiple consecutive MPS events. This condition is relaxed when the Qe value is close to 0.5. When Qe is extremely small, the renormalization method Q
The interval between e and AMIN is the probability of MPS renormalization and LPS
must be large enough such that the probabilities of are of the same order of magnitude.

In addition to the above measures to avoid renormalized Qe values from being AMIN or values below it, the present invention provides
The jump in index position in response to renormalization is MP
It tells us that "bad" JQe values can be included if they are relatively larger than the drop in index position in response to S renormalization. For example, the minimum value of Qe in Table 1 is a "bad" value.

However, when LPS renormalization occurs, the index for the Qe value is shifted by two entries (4 bytes). Therefore, to return to the minimum value of Qe above, M
PS renormalization must occur twice in a row. Therefore, the estimator will not be trapped even though M P S renormalization is very likely to occur immediately after LPS renormalization.

A second point to consider when choosing table values relates to encoding inefficiencies. In this regard, it is desirable to minimize coding inefficiencies over the range of acceptable values for Qe. The graph in FIG. 8 shows the relationship between encoding inefficiency and the magnitude of log and Q. Q
The e values are the values contained in Table 1. The circles represent experimental results, and the solid lines represent the results of theoretical calculations for one specific example of encoding in the case of single-sentence doors (see Section 2).

Coding inefficiencies are determined by the entropy, the bit rate/symbol for a particular state (i.e. a particular entry in the Qe child table), and the occupancy (
Occupation) probability-based, where the entropy H is.

m P r(x) defined by H=-(ΣPr(i)1ogPr(i)) represents the probability of the first decision event, and the sum is found over all decision events for a given decision. shall be. Given the granularity of the table and the arithmetic approximation used during encoding, the most uniform curve is desirable;
It is not necessary that this is the case.

According to the invention, the density of index positions is
is enhanced in the high entropy Qe value part of the table compared to the set of powers of . In the power of 2 set, the range from 1/4 to 1/2 has a Q of 0.1
e value, 1/8 to 1/4 to 0.01, 1/16 to 1/
8 corresponds to 0.001, respectively. The same applies to the subsequent index positions. There are relatively many entries near the 1/4 to 1/2 range compared to, for example, the skew coder described above. At low entropy Qe values, the density is relatively linear.

Third, one must consider the responsiveness of the system, ie, how long it takes to get from a misplaced value to a proper Qe value.

To facilitate this objective, larger increments and decrements are chosen between adjacent Qe values. However, this is the case if such large derivatives do not adversely affect the steady-state results. A stationary result is generated according to a fixed probability, for example based on data provided by a pseudo-random number generator.

Non-stationary results are based on real-world data whose probabilities can vary over time.

Table 1 was determined in consideration of the above matters, and
Simplicity, minimal storage required for each context (eg, 1 bit for sensing the MPS symbol and 5 bits for indexing the Qe value, for a total of 6 bits).

), the validity of the efficiency of the coding for fixed (i.e. stationary) statistics, and different data compression models (
for example.

It is a compromise between performance on multiple context data obtained from facsimile compression models and continuous tone image compression models.

The above discussion describes a compromise between coding efficiency and rapid estimation of changing probabilities.

A gating circuit is shown in FIG.

It has multiple input lines and multiple output lines. By setting the input line to a predetermined pattern of O and 1 signals, the corresponding q index is input to the gating circuit. For each q index, the dating circuit provides a signal pattern on the output line representing the corresponding Qe value. According to the invention, the Qe value is selected such that the number of gates and gating required to output the Qe value in response to the q index input can be limited to a small number. The Qe value is such that (a) the least significant bit (LSB) of the Qe value is always set (to 1), and (b)
) For any given Qe value, only 5 of the 12 bits of the Qe value are selected to be set.

Thus, the above objectives are achieved while simplifying the hardware.

3. Single context adaptation and context adaptation A context table is shown in FIG.

In particular, three contexts are listed: C01C1 and C2. Each context corresponds to a different setting, and decisions are made in each.

For example, different contexts represent different regions within a frame of optical data, where some regions are predominantly black and other regions are predominantly white. Another area may be that each type of event is represented in equilibrium, so that for each context, the MPS identifier, i.e., a black (i.e. YES) decision is an MPS, or a white There is an indicator as to whether the decision (that is, No) is MPS. This is expressed as a binary number in the MPS column in the table of FIG.

In the context of co and C2, the O event represents an MPS event, while in the context of C1, the 1 event represents an MPS event.

The next column of the table is the Qe index table, which displays the currently pointed Qe entry for each context. In the C0 context, the 0th entry is indicated. Similarly, in C1 and C2 contexts, 1
The 2nd and 29th entries are indicated. In the last column, the individual Qe values are 0.5.0.10.0 respectively.
．． 001. MPS identifier and Q
The e index is preferably expressed in 6 bits, and in this example the Qe index is preferably expressed in 5 bits. However, the number of bits can be changed.

According to one embodiment of the invention, a single addend value is stored and used independently of the context considered.6 When a decision is entered in each context and renormalization is performed for each context, a common The summand of is processed.

As an example, a string of 0 and 1 bits is shown, each associated with a corresponding context. string 01100
represent the bits in the Go-C1-GO-Co-C2 context, respectively. From the table in FIG. 10, the bit strings are MPS (for CO), M
PS, (for Co) LPS, (for Go) MP
Express S, and MPS (for C2). For purposes of this example, assume that the initial value of A is 1.0 before the first bit is encoded. Under the above P/Q encoding scheme, in response to bit string 01100, the following operations occur.

i, for the 1st bit.

A4-A-Qe(Go)=1.0-0.5=0.5. Since A becomes less than 0.75, A is renormalized to 1°0 and the value of Qe(Go) is reduced to 0.486 ■, the second bit represents the MPS in C1 context and Therefore, the summand A decreases according to the following formula.

A+-A-Qe(C:1)=1.0-0.1=0.90
Neither renormalization nor updating of Qe takes place.

=, the third bit represents the LPS of the context CO, causing LPS renormalization. The value of the summand is 0.90
to Q e (G O), that is, 0.48.

The value of A must be renormalized (doubled) to 0.96, and the Qe value for the C0 context is incremented. In this example, it is assumed that the Qe(Co) value increases by moving back one entry toward the 0th entry. As discussed below, the present invention also contemplates raising the Qe value to a single value that is one or more factories apart. Another method according to the invention allows the Qe value to be increased to a selected one of several possible subsequent Qe values depending on how far the Qe value appears from the real probability. Gender is also taken into consideration. The latter method is described as a multi-rate example in the manifest of the above-mentioned patent application (title: Probability Adaptation Method in Arithmetic Coding Systems).

■The fourth bit is the MPS in the C0 context. A
is changed to (0,96-0,5)=0.46, and MPS
Renormalization is required. The value of A is doubled to 0.92 and Qe(Co) is reduced to 0°48.

v, the fifth bit corresponds to the MPS in one context C2. The value of summand A is (0,92-Qe(C2))=0.
92-0.0OL=0.919. This is 0.75
After 65 bits, the table has the following entries: That is, for context CO, MPS=O1Qe(
Co) index is 1 and the value of Qe(Co) is 0
．． For the 48° context C1, all data remain unchanged. For context C2, the current summand A for the zero-order encoded decision event remains unchanged in all data.
is 0.919 regardless of the context of the decision.

Compared to single-context examples, multi-context examples allow multiple decision contexts to be processed together.

4. Single rate adaptation According to the single rate estimator, for a certain Qe,
For LPS renormalization, only one value larger than the current value to be selected as the next probability is specified, and for MPS renormalization, only one value smaller than the current value is specified. One example of a single rate estimator is described in Section 5 as a finite state machine.

5. Qe Child Table Finite State Machine Representation FIG. 12 shows the implementation of a single-rate, single-context estimator with a finite-precision estimator. The value k represents a state in which the definitions of the MPS event and the LxPS event are swapped. In FIG. 12, each state has one outgoing path corresponding to MPS renormalization and one outgoing path corresponding to LPS renormalization. If k, then U
Even if the update is performed by ff1a due to PS renormalization, the state returns to the same state.

Each state may be thought of as one table entry representing a particular Qe value; each entry
tied with two possible entries.

Preferably, the MPS renormalization results in a transition to the next state that is closer to aX by k. It should be noted that during LPS renormalization, the state position may change by one, two, or more through the transition to the possible next single state.

In the flowcharts from 1 to Akiichi of the V,Q coder system flowchart, the above "hardware" and "
Specific examples of "software" are described in accordance with flowcharts. In the example of an encoder and a decoder, to indicate the difference between the two, -H or -8 is added.

FIG. 13 is a flowchart (contrast with FIG. 1) illustrating a cog and decoder according to the arithmetic coding compression/decompression system of the present invention. In FIG. 1, BITIN is the encoded binary event and BITOUT is the decoded binary event.

In the flowchart of FIG. 13, binary judgment is called YN in both the encoder and decoder. Generally speaking, INITENC in FIGS. 14 and 15 is a hardware scheme.

Initialize each compression system of the software and scheme. The model process is represented by the statement "Acquisition of rS, YN." INIT
STATE (Figure 16).

For all contexts S, the initial value of the q index and the Qe value are set. The ENCODE block (Figure 17) uses one context state S and the YN value to
A stream is generated. The decision as to when all symbols have been encoded is provided by external means. For example, a grayscale TV has 512
There is a fixed format, such as pixels/line x 480 lines. If no agreement is reached, the encoder sends the information to the decoder, either by external means or as part of the compressed data.

Once all symbols have been encoded, the block FLUS
The last byte is output by the function of H (FIGS. 33 and 34). Therefore, the decoder is provided with enough data to ensure that all symbols are completely decoded. The block "Send" represents storage or transmission. In this diagram, it appears as if the complete compressed data is generated before transmission or storage.6 However, any byte can be transmitted immediately after the subsequent byte is generated. To initialize the decoder, INITD
The EC block (Figures 39 and 40) is called once.

At the decoder, the model provides the value of the context state S. DEC
The ODE block (Figure 41) recovers the YN decision.

The determination as to when decoding is complete is provided externally or as part of the compressed data stream.

(a) Detailed Description of Encoder Operation The following definitions apply to the flowchart and its description.

■ Q○(S) is defined in programs and flowcharts as a fixed decimal point with 16 bits. It can be a positive number or it can be a negative number.

lo(S) is QIMPS for updating Qe probability value
Table or QILPS table index. This is stored in the form of 2 pies, t immediately after QO(S). The 4 bytes from the QIMPS table or QILPS table become the next QO, IO pair.

A is a 16-bit integer, but it is divided into 12 fractional bits, followed by two zeros, and two leading integer bits.
It can be thought of as a binary number with a base point.

X is a 32-bit number having a structure as shown in FIG. 5 for the encoder and FIG. 6 for the decoder.

XC is the upper 16 bits containing the most significant bit of X at the decoder.

XNEW is the lower 16 bits containing the least significant bit of X at the decoder.

XFLAG is the lower 8 bits containing the least significant bit of X at the decoder.

LE'N is the buffer length for the code stream. This is (optionally but conveniently) set to 256 bytes. LEN can also be set to 1.

BPST indicates the beginning of the compressed data buffer.

BE points to the first byte beyond the compressed data buffer.

BP is a pointer indicating the current byte of compressed data.

B is the compressed data byte pointed to by BP.

AMIN determines when renormalization is required. A.M.
I'N is (equivalent to 0,75) Hex '400
Set to 0'. However, only for the software decoder, it is set to minus He x'4000'. This is also equivalent to 0°75.

INITENC (FIGS. 14 and 15) initializes the encoder. The version to be implemented is either the hardware version (-H) shown in Figure 2 or the third version.
Two versions of INITEC are implemented according to the software version (-8) shown in the figure. After the table is set up, INITSTATE (Figure 16) initializes the context storage. Common to the two versions, LEN
is initialized to 256 bytes, and BE is the compressed data.
It is positioned at the end of the buffer, and BP
1 of ST (i.e. the actual start of the buffer to send)
It is positioned in front of the part-time job. The pointer is updated before a single byte is written. Therefore, an offset of 1 is required.

Byte B (addressed by BP) is '80
′ is initialized. This means B=O or B='F as the first byte in the compressed data stream.
This is to prevent the trigger from being triggered in the special case of F''. Range A is set to '4000', and AM
IN is also initialized to the same value.

It is in the initialization of X that the differences between versions appear. In all versions, to signal when the 8 compressed bits are ready,
The 8th m s b is set to 1. In the software version, a borrow bit is inserted immediately after the X flag bit, and the lower bit is ORed with A. This borrow bit blocks borrow propagation to the flag bit.

ENCODE (Figure 17) shows the two paths taken depending on YN being 1 or O.

(1,0DEYNI (Figs. 18 and 19) is YN
=1 is encoded. If QO(S)<O, then MPS=1
, and the MPS symbol must be encoded.

A is decreased by adding a QO that is negative.

The hardware version increases X by subtracting a negative QO. A is AMI in MPS path
If it is less than N.

QO can be reduced by UPDATEMPS (Figure 22). In the RE N ORM block (Figure 24), both A and X are renormalized.

If QO is positive (zero is not allowed), MPS=0
, and the LPS symbols must be encoded. For the software version, the MPS range must be calculated and/or reduced by the new A. In both cases, A is set to QO(S) and the update of the probability for the LPS case is UPD
This is carried out in the A position LPS (Fig. 23). Since QO is always less than AMIN, renormalization is required.

C0DEYNO (Figures 20 and 21) shows the same operation as Figures 18 and 19 for paths where YN=O, in this case QO is positive for MPS paths and positive for LPS paths. QO is negative.

UPDATEMPS (FIG. 22) updates the probability on the MPS path. A new Qe and index (4 bytes total) are found in the place of the old IO(S) in the Q I MP S table. Table 3 is an example of a QIMPS table.

The UPDA-based LPS (Figure 23) uses new Qe and indices (total 4
byte) is the old lo(S) in the QILPS table
can be found at the location. Table 2 is an example of a QILPS table.

RENORME (Figure 24) normalizes the A and X values one bit at a time. After A is shifted first, a test is made for X to see if the most significant bit is set. If set, the next shift of X removes that flag bit and
A byte is output by BYTEOUT (see Figures 25 and 26). If not set, or just shifted by one bit. This process continues as long as A is less than AMIN.

According to BYTEOUT (Figures 25 and 26), the decoder expects a bit to be inserted at the beginning of the following byte immediately after each "FF" byte. The first bit will be the carry bit.

In Figure 25, the hardware version first looks at the last byte B, and if B is 'FF', it immediately follows 5.
Only 6 bits are output in HIP7-H (FIG. 27). Any carry will appear in the first significant bit of the new byte. If B is less than 'FF', then test X for carry. If there is no carry, the 8-bit output is set to 5HIP8-H (
(Fig. 29). If there is a carry, it is necessary to increment by 1 for the last byte B, and a test is made to see if the result is 'FF'. If the result is 'FF'.

The carry in X of the additive method must already be cleared in B before outputting the following 7 bits. Results'
If not FF', 8 bits may be output to a new byte.

BYTEOUT-5, the software version
(Figure 26) tests whether or not X is positive @X
If is positive, a borrow bit was used and 8
B must be decremented by 1 before outputting the bit; if no borrow bit was used, A
The borrow bit is cleared from X before it is compared with MATA.

If X is less than A, a borrow may be needed in the future, but will not be available if the new byte is output as a zero.

(A is at most '7FFC' and X has only zero among its eight output bits.) SHIP8FF
-5 (Figure 31) performs a pre-borrow, converting the new byte to FF'' and saving the borrowed bits to X.B
If is 'FF', then instead of 8 bits being sent by 5HIP8-8 (Figure 30), 5HIP7-8 (
28), only 7 bits are sent.

5HIP7-H (Figure 27) increments the output byte pointer in NEXTBYTE (Figure 32) and holds the new B bits 24-17 from X. The first bit contains any carries.

Only the next 17 bits are left in X before the flag is inserted at the 7th largest bit. As a result, the next byte is output when the 7 new bits are ready.

Because one bit remains in X,
5HIP7-3 (Figure 26) is the same as 5HIP7-H except that the borrow bit is set to immediately follow the flag bit.

5HIP8 (see Figures 29 and 30), both versions are similar. After incrementing the pointer to the subsequent output byte B, the 8 bits in bits 23-16 of X are retained in B.

All bits in X except the least significant 13 bits are cleared, and a flag is inserted at the 8th bit from the most significant. The software version also inserts a borrow bit after the flag.

In the software encoder version, it must be ensured that it is possible to perform a decrement on B if necessary. 5HIP8FF-8 (Figure 31) is executed when the subsequent byte to be written is zero and it may become necessary to take a borrow. Therefore, B is decreased by 1 and the subsequent byte is
It is converted to ex'FF' and borrowed immediately.

The borrow taken from these two bytes is inserted into X. There, if the borrow is not needed, it is output as a carry in a subsequent byte.

” NEXTBYTE (Figure 32) moves BP to address the next byte in the compressed data buffer. After being incremented, if BP becomes greater than or equal to the end of the buffer, then the buffer must be transferred and B
P must also be reset to return to the beginning of the buffer. It is envisaged that BPST and BE will be changed appropriately if necessary.

2 still in X after the last symbol is encoded
Two compressed bits need to be flushed out. In FLUSH-H (Figure 33), CT is initialized to 22 and is decremented for each shift in X until the flag is in the most significant bit. Another shift positions the output bits on byte boundaries. Then, FINALBYTES
-H (Figure 35) allows output of these last bytes.

FLUSH-3 (Figure 34) moves X to the bottom of the interval. This positions it precisely to the value produced by the hardware version. After byte alignment of bits, if the borrow is used, FINALBY
In TES-8 (Figure 36) the last byte must be decremented before it is output.

FINALBYTES-H (Figure 35) has all bits flushed out, so FLUSH7 (Figure 37) and FLUSH8 perform the same type of operation as BYTEOUT-H (Figure 25) in a loop. (
The block in Figure 38) involves decrementing CT by 7 or 8 bits as appropriate. When it is complete, the BP is
is incremented so that the last contents of the buffer can be sent out.

Version FINALBYT for software encoders
The ES-8 (Figure 36) only needs to send out 7 or 8 bits depending on whether the preceding byte is 'FF' or not. Pre-borrow processing has already been done by FLUSH-8
It is being held in

Since X has been moved to the bottom of the interval, the test with A at BYTEOUT-8 is irrelevant.

In FLUSH7 (Figure 37), in both hardware and software versions,
By pointing to the new byte, storing bits 24-17, saving only the lower 17 bits of X, and decrementing CT by 7, 6 bits are output.

In FLUSH8 (Figure 38), in both hardware and software versions,
By pointing to the new byte, storing bits 23-16, saving only the lower 16 bits of X, and decrementing CT by 8, 8 bits are output.

INITDEC (Figures 39 and 40) initializes the decoder. The decoder is the best suited for the hardware (H)
Two versions of INITDEC have been implemented, depending on which one (S) is most appropriate for the software.

After the table is set up, all states are initialized as in the encoder. The initialization of X is from a buffer of compressed data. However, note that the size of A is initialized to match the encoder. Both versions begin by acquiring a new buffer of compressed data. This is BPST
This assumes initialization of LEN. BE is initialized to point to the end of the compressed buffer, and BP points to the beginning of the buffer. "The difference between the versions is X, A
, and appears in the initialization of AMIN. For hardware version, range A is “4000”
, AMIN is initialized to 64000', respectively. In software versions, these numbers will be negative. , TNITDEC-H, the first two bytes are placed in bits 31-16. For initialization convenience, the first two bits of the compressed data stream are specified as O's. This simplifies byte alignment of the code byte and the byte of the X register during initialization. When the first byte is shifted to positions 31-24 and the pointer BP is incremented at GETBYTE (Figure 49), the second byte is shifted to bits 23-16.
It is guaranteed that the 6 first bytes added to 'FF' will not become 'FF', so there is no need to test them. The decoding process only cares about the bits in XC, the high order two bytes of X (bits 31-16). Using BYTEIN, the third byte is placed in bits 15-8. (
However, this is the case when the second byte is not 'FF'. If the second byte was FF', the third byte is added to bits 16-7. )BYTE
IN sets a flag indicating when a new byte is needed. Software version INI
TDEC-8 (Figure 40) is 'C000' in XC.
Start by subtracting A from O.

The first two bytes are added to this starting point. BYTEI
N is used to add the third byte and set flags.

DECODE (Figure 41) shows the two paths taken depending on whether the MPS is 1 or O.

DECODEMPSI (Figures 42 and 43) is M
Two implementations of decoding when PS=1 are shown. In the hardware version, the QO that is negative
(S) is added to XC.

If the result is greater than or equal to 0, the MPS pass continues. YN is set to 1 and A is decreased by adding QO(S) which is negative. If renormalization of A is required on the MPS path because A is less than AMIN, then t
The magnitude of QO(S) is also reduced in JPDATEMPs. In the LPS path, YN is set to 0, XC is recovered by subtracting the negative QO(S), and A is set to the negative of QO(S). LP
Renormalization is always required in the S path, and the magnitude of QO(S) is increased in the UPDA and LPS.

In the software version of Figure 43, before comparing XC to A, the magnitude of A is reduced by subtracting QO(S) which is negative. A has a negative MPS range; if XC is greater than or equal to A, LPS is decoded. Otherwise, the MPS is decoded. If the LPS is decoded, the software version increases xC by subtracting the negative MPS range A. In the MPS path, both A and A M I N are negative, so A is A M
If it is greater than IN, the absolute value of A) is AMIN.
(absolute value), indicating that renormalization is required.

DECODEMPSO (Figures 44 and 45) is an MP
The same operation as in FIGS. 42 and 43 is shown for the path S=O. In this case, QO is positive.

RENORMD (Figures 46 and 47) is the A value and
Normalizes the value one bit at a time. After both A and X are shifted, XFLAG, the least significant byte of X, is tested for any bits being set. If there is no such bit, move on to acquiring a new byte. This process continues as long as A is less than AMIN (for hardware) and as long as A is greater than AMIN (for software).

During the process of moving a new byte to X as shown in BYTEIN (Figure 48), GETBYTE (4th
Before moving on to the next byte (Figure 9), a test is made on the last byte B to see if it was on 'FF'FF. The first bit of any byte following 'FF' was inserted during encoding and must be properly considered during decoding. If there was 'FF',
XNEW (the two least significant bytes of X) is set to the value 2.

0 to shift the flag bit by 1 in XFLAG The next byte, usually located in the second least significant byte, is sent out towards the extra bits and
6 If the last byte B added to is not 'FF', the least significant bit of XNEW is set and
The new byte B is added to the high order byte of the new byte.

GETBYTE (Figure 49) moves BP to address the next byte in the compressed data buffer. If the BP after being incremented is at least the end of the buffer, a new buffer must be acquired and the BP must be reset to the beginning of the buffer. It is assumed that BPST and BE are modified appropriately if necessary.

The procedure for the software-based encoder described above is implemented on a conventional mainframe computer, such as the IBM 3370. Alternatively, it can be implemented in a personal computer, such as IBM PC-XT, PC-AT.

The procedure can be implemented using a high-level language such as PASCAL.

■Example explanation of hardware As shown in FIG. 50, the Q coder 500 has two
Each time a value event BITIN is encoded, an N-bit state S is provided by the encoder-side state generator model (see FIG. 1). The output of Q-coder 500 is bytes of compressed data. These are the Q decoders (see Figure 54)
transmitted or stored before being entered into the Q
The decoder determines the logical value of the binary event BITOUT based on the N-bit input state S from the decoder-side state generator model. This decoded BITOUT value is fed back to a decoder side state generator (not shown).

The Q-coder/Q-decoder system operates one major cycle for one of the binary events to be encoded, and the timing is determined by an edge-triggered flip-flop and a single phase clock system. It is determined. The time between clock edges is long enough,
Thus worst case propagation delay and setup time requirements are met.

Here we explain what happens during each major cycle. FIG. 50 is a block diagram of Q coder 500. For each new cycle, the Qcoder 500 is supplied with the binary event value BITIN and the state S specifying the storage location of the information about the probability as its main inputs. At the end of the cycle, the output control from the carry over (C10VER) output buffer (OUTPUT C0NTR0L
) is 1 of the code string (CODESTRING)
Specifies whether the number of bytes prepared in 6 bits is 0.1.2.

One input to the statistics unit 502 is the N-bit state j
ll S te&ru. Coreha, MPS value (MPSVAL
) and the Q index for the current binary decision BITIN, a conditional technique is used to address the context store. The Q index is a series of integers that index the set of probability estimates for the LPS. In a specific example, the Q index ranges from 0 to 629.

Statistics unit 502 outputs the MPS value and Q index early in the cycle. It is therefore possible to input these parameters to both the encoder unit 504 and the adaptation unit 506. Late in the cycle,
If the input A bus <O> (the most significant bit of the A bus) was not 0 for some period of the cycle, the statistics unit 502 inserts the new MPS value and the new Q index into the location specified by the state S. Remember. The operation of the statistics unit 502 is as follows.

The same is true for both encoder and decoder.

Adaptation unit 506 is also the same for both encoder and decoder. The operation of this unit is shown in Table 4. The same functionality can be achieved using discrete logic.

The binary event BITIN is input to encoder unit 504 along with the MPS value and Q index. One of the outputs from encoder unit 504 is binary (Boolean)
The signal A bus 0>, that is, the most significant bit of the A bus. This tells the statistics unit 502 when to change the Q index or MPS value. Adaptation unit 506 receives “M” from encoder unit 504.
Ps o p ”Receives and accepts boolean signals. This is
Displays whether the current judgment is MPS operation or not. The output of adaptation unit 506 becomes new values for the two inputs from statistics unit 502. , statistics unit 502
stores a new value only if A bus 0> is zero.

Cl0VER output buffer 508 is connected to encoder unit 5
04 and adaptation unit 506, or can operate in a pipelined manner. As a unit of the pipeline, in cycle "n" the system runs through cycles at, 1 . In each cycle, the flip
A flop stores the output of the encoder.

There are two types of major cycles.

That is, MPS operation and LPS operation, respectively.
P S OP equals 1 and MPS OP equals 0 are displayed. If the BITIN value and MPS value are the same, MPS
operation, if different, it will be LPS operation. BI in Figure 51
An exclusive OR gate according to the TIN and MPS values determines the type of operation for the major cycle.

During one cycle, encoder unit 504 outputs Cl
For the 0VER output buffer 508, the binary carry
out value Cl0UT, the 13-bit unnormalized code stream C-UNNORM, and the code
It outputs a 4-bit control signal SHI FTAMT indicating how much the stream should be shifted. buffer 50
8 outputs a control signal indicating the number of 1 or 2 bytes and whether the number of bytes sent out is Oll or 2.

Statistics unit 502 and adaptation unit 506 provide Q
Identical for both coder and Q-decoder.

FIG. 51 is a detailed block diagram of encoder unit 504. Arithmetic coding methods of the type discussed here form codes by additions and shifts.

The number (quantity) to be added is the summand. The input Q index is related to the summand. The Q value (QVALUE) has a one-to-one correspondence with the numerical value of the Q index. Here, Q
The value is the summand in the arithmetic encoding process in the hardware Q-coder implementation. The encoder unit only determines the Q value and not the Q index; in this example, the Q value is a 5-bit number, and the Q value is 12 significant bits plus a leading zero. Therefore, it is more economical to store the Q index. Also, the Q index is easier for the adaptation unit 506 to manipulate.

For both encoder and decoder, let the Q index be
It is Q logic 510 that converts it to a value.

The conversion can be performed using Table 5 or using combinational circuits using truth tables that appear in current textbooks. Note that the most significant bit of the Q value is always O and the least significant bit is always 1.

The Q coder uses two registers, an A register 528 and a C register 534. The C register is functionally equivalent to the X register used in software flowcharts. FIG. 52 is a detailed explanatory diagram of the A logic that modifies the contents of the A register 528. Depending on the input MPSOP, the A multiplexer (A-MUX) 522
Select the Q value corresponding to the S operation (0) or the Q value corresponding to the MPS operation (1) subtracted from the A register 528. Priority encoder 524 counts the number of leading zeros on the A bus and generates the shifts ffisHIFTAMT necessary to restore a 1 to the most significant bit of the A bus.

This shift is performed in A register 526. The least significant bits are filled with 0 as necessary. Table 6 shows the value of SHIFTAMT as a function of the A bus, where the dashes indicate ``don't care''. After the value of has stabilized, its contents are fed to the person subtractor 529.

Shifting from the code stream, specifically through C register 534, is done through A register 528.
It is controlled as follows.

When A register 528 needs to be shifted to the left by a given number of bit positions, C register 534 is also shifted by the same number of bits. At the beginning of each major cycle, the A register must be normalized. That is, the value in the A register must be greater than or equal to the lower limit value.

As mentioned above, if this condition is not met, A is renormalized (by shifting to the left). (A is initialized to the lower limit LB.) A shift of the A register 528 occurs in a major cycle in which an operation on the A register 528 results in the value of the A register being less than the lower limit. The fact that the value is below the lower limit is detected based on the fact that the most significant bit of the A bus, that is, the A bus 0> becomes 0.

In MPS operation, the Q value is subtracted from the A register 528;
If necessary, the difference after renormalization is returned to the A register 528. For LPS operations, the normalized Q value is placed in A register 528. In Fig. 52, the Q value is set to A register 5.
The subtraction from 28 is performed in the human subtractor unit. Its output passes through a 2-to-1 data selector called the A multiplexer. In LPSOP, the Q value passes through data selector A-MUX 522. A-MUX5
The output of 22 is called the A bus. According to the result of subtraction,
The resulting value of the A bus may be less than LB. In this example, the value of LB is chosen such that if A bus 0> is 0, at least one renormalization shift must occur.

In fact, the number of renormalization shifts that the A bus must undergo is the number of leading zeros in the result (of the subtraction) on the A bus. Renormalization of the A bus is performed in the A shifter 526 unit. A shifter 526 is a barrel left shifter with zero fill functionality. The number of bit positions shifted out of the A bus depends on the number of leading zeros on the A bus. SHIFT which is the control signal of A shifter
AMT (shift amount) is a 4-bit number between 0 and 12. When the A bus does not require renormalization.

SHI FTAMT is 0 and the A bus passes straight through. Control signal SHIFTAM supplied to the shifter
T is determined by priority encoder 524. The encoder 524 encodes the number of leading O's on the A bus. During MPSOP, A multiplexer 522 outputs the difference obtained by subtracting the Q value from the A register to the A bus. LPS
At the time of OP, the data selector A-MUX 522 outputs the Q value. The SHIFTAMT value also controls the C register 534 portion of the encoder and is also the control signal for the Cl0VER output buffer 508 unit.

In MPSOP, the C register 534 and the Q value are stored in the C adder 5.
36 to yield the MPS result for the C bus. In LPSOP, C multiplexer (C-MUX
) 534 provides the value of C register 532 to the C path.

Cl0UT is also supplied to the C/○VER output buffer 508 unit. Adding the Q value to C register 534 (as in this example) may occur in parallel with subtracting the Q value from A register 528. C bus is the same SHI as A bus
It must be shifted by FTAMT (shift amount). For this reason, the output SHIFTAMT of unit priority encoder 524 is also supplied to C shifter 8. M.P.
In SOP cycle, 2 to 1 data, selector C-MU
X passes the C bus to the C shifter. The C sister is paired with the A shifter and is a barrel sister with a C1 left shift. The output of the C shifter is sent back to the C register 534.

The (unshifted) output of the C-MUX is the C-UN
It is called NORM and is C,1 like SHI FTAMT.
It is sent to the 0VER output buffer 508 unit. S
By HIFTAMT, the Cl0VER output buffer 508 unit knows how many leading bits of C-UNNORM to take.

In LPSOP, there is no addition to C register 534, only a shift. In the LPS○P cycle, the C-MUX control signal selects the C register 534 itself and sends it to the C shifter. Therefore, the value of the C register is SHI
After being shifted left by FTAMT bits, the process returns to C register 534.

As mentioned above, SHIFTAMT and C-UNNORM
(C-MUX (7) output) is also input to the Cl0VER output buffer 508 unit. Here, Cl
0UT must be O. This is because nothing is added to C.

The purpose of the adaptation unit 506 is to adapt the input O and 1
is to adjust the encoding parameters used in a particular context based on the relative probabilities of .

In the code described, A register 528 and C register 5
The length of 34 is 13 bits, and the bit position is O.
It is expressed as ll, . . . , 12. here.

5 positions 0 and 1 where position 0 is the highest and position @12 is the lowest
Conveniently, there is a radix point in between. Then, if bit A〈0〉 is 1, then A
The value of the register is between 1.0 and 2.0 drops. The value of LB is 1.0. The Q values are all less than 1°0, but some of them are close to 0.5. Therefore, the range of Q values has 12 significant bits. Bit position C<O>
is not added directly. This is because the corresponding bit position of the Q value is known to be 0. Therefore, C0〉 can be changed because MPSo
This is when a carry is brought in during the P cycle.

Due to the nature of arithmetic encoding, after any major cycle the value of the code string is stored in the current A register 52.
It is impossible for the current C register 534 value to contain more than 8 values plus the code string. Therefore, once carry-out from C<O> occurs,
A block of encoder C logic 530 is shown in FIG. 53 where no other carry comes to that bit position in the code string. Input M to C multiplexer 532
PSPOP selects the contents of C register 534 for LPS operation (0), while selecting the contents of C register 534 for LPS operation (1).
), the sum of the contents of the C register 534 and the Q value by the adder 536 is selected. 1 from C-MUX532
The 3-bit output is the C/UNN (before renormalization)
It is output as an ORM signal. The same data on the C bus is input to the C shifter 538 so that the S
It can be shifted by HIFTMATO. Zeros are inserted into the least significant bits during the shifting process if necessary.

The Q-decoder of FIG. 54 includes a statistics unit 602, an adaptation unit 604, a decoder unit 606, and a C/I that accounts for carries in the code stream.
N buffers 608 are included. Elements 602.604 are Q
It is identical to similarly named units in coder 500. FIG. 55 shows details of the decoder unit 606. The decoder unit 606 includes the CD logic 60.
8, Q logic 610, and A logic 612.

In FIG. 56, the decoder CD logic is shown.

The difference between the least significant bit of the Q value (which is always 1) minus the carry-in C/IN is 1 if C/IN is 0, and 0 if C/IN is 1. Therefore, the Q value minus C/IN can be obtained by replacing the least significant bit of the Q value with the inverted value of C/IN. In the CD subtracter 620, from the Q value minus C/IN to the CD register 624
If the result of subtracting the contents of is positive, the MPS has been decoded, and the result is sent to the CD shifter 622 via the CD bus. The MSPOP signal is 1. Otherwise, LPS has occurred and the sum of the contents of CD register 624 and the C/IN output of adder 626 is
0 at CD multiplexer (CD-MUX) 628
is selected by the MPSOP. The BITOUT value is obtained by exclusive ORing the MSPOP signal and the MPS value. Shift amount SHIFT
The AMT is stored in the CD register 624 before it can be stored.
Determine how much the Dbus value must be shifted. During shifting, the least significant bits are filled by the most significant bits of the instring (IN5TRINO).

In fact, CD register 624 contains the current code associated with the bottom (lower end) of the current interval. The upper 12 bits of the 13-pitch Q value (most significant bit is zero) are sent to CD subtractor 620. The least significant bit of the Q value is replaced by the bit derived from C/IN. The least significant bit of the Q value is always 1, so when C/IN is O (i.e. no carry), the value is inverted and becomes the least significant bit of the Q value for the CD subtractor 620; The C/IN adder is directly fed to the C/IN adder.

Thus, the carry is added to the code stream and removed from the Q value in parallel, and the Q value is then subtracted from the code value. The borrow from CD subtractor 620 is the decoded MPS/LPS decision, MPSOP. Next, the exclusive O of MPSOP and MPS value
By taking R, the value of BITOVT is obtained.

FIG. 56 also shows the data bus for CD register 624.

Although the CD bus <0> bit is not pulled directly, it must be present. This is because the value of 11' may be shifted to CD bus <0> by the shift operation. SHIFTA obtained from A logic circuit
MT becomes a control input for a CD shifter 622 that performs a left shift. The lower "fill" bit for the shifter is C/
Bus IN5 output from IN human power buffer unit
Derived from TRING.

The decoder unit 606 (FIG. 55) includes lN5TRIN
Up to 12 bits from G plus the carry C/IN signal are used to decompress the data. MPS
The value and Q-index value are also required as inputs for decoding the output bit BITOUT. As with the encoder, the decoder unit 606 provides the A-pass 0> signal to the statistics unit.

Escape from the arithmetic code stream In many coding environments, it is desirable to provide an escape from the code stream that is detectable independently of the arithmetic decoder. In the following, we discuss escapes based on assigning spacer bit positions to code stream register X of the encoder. In fact, the inclusion of the spacer bits causes a delay in the time that the xXx... bits are shifted into the subsequent byte of the X register identified by bit position bbb....

By including a spacer bit, He x'FF
Certain bit patterns after the ' are malformed, suggesting an escape from the code stream and the insertion of a control word. (Typically, the control word is withdrawn by the controller prior to decoding6) In addition, the use of spacer bits allows for more than one carry beyond the byte in the trailing byte portion of the code stream register. The possibility of being brought to fruition disappears.

The bit pattern of the X register, which holds the partially completed subsequent byte of the code stream, is bit aligned with (the summand) register A, which holds the value of the current interval. For a 12-bit integer representation of probabilities, one example of encoder register bit allocation may be as follows.

X=OOOO00000cbbbbbbbbss, x
xxx xxxxxxxxx A=00000000000
00000000a, aaaa aaaaaaaa where 10' represents the zero bit and C is the carry receiver bit. 'b' indicates the bit at the position where the subsequent byte is generated.

’s’ is the spacer necessary to limit carry propagation.
Indicates a bit. or represents a binary decimal number still being expanded in the X register. One of the tap bits in the A register is an integer bit and the others are fractional bits. If the preceding code byte is Hex'FF', the bit positioning is shifted by one bit. Therefore, the carry bit occupies the fill bit position of the subsequent byte. In this special case, X=0000000000cbbbbbb bbss, x
xxx XXXXXXXXX. Note that in this special case, only seven 'b' bits are defined.

Following the removal of fully expanded code bytes, rules for bit positioning and renormalization dictate the upper bounds of the values in the two registers. That is, X=OO000000000000000011,11
1111111111A=0000000000000
0000001.111111111110.

Note that even if a future event is encoded, the value in the , so the upper limit of the code register is X=SLL(0000000000000000010
1,11111111101)N. Here, N
is the renormalized shift count. The SLL performs a "left shift logic" operation ('5hift logical
'operation). When the byte is completed, N is 8 if the preceding byte is not 'FF'.
and 7 if the preceding byte is FF'. Therefore, after 'FF', the upper limit of the X register is as follows.

X=OO000000001011111111,11
1010000000X=OO00000000cbb
bbb bbss, xxxx xxxxxxxxxx Therefore, if you include two spacer bits, Hax
The maximum value of data bytes following 'FF' is Hex'B
By the way, if only one spacer bit is allowed, the maximum value of the byte after the 'FF' byte is '9F'. Thus, by providing two or more spacer bits, the ill-formed code following the 'FF' byte is
Provides an escape from the stream.

(As shown in the flowchart and Tables 2 and 3,
) A two-bit shift in the alignment of the A and X registers shifts the byte to be removed from the code register to a byte boundary in the X register. This shift does not change the escape code structure.

■Test sequences for small data sets Generate test files by applying binary sequences to
This was done using a random number generator with a probability of 0.1875. The actual number of zeros in the file is 4, as expected.
It was 8. The Q value was initially set to '0AC1'.

This is represented as '2b04' when shifted by two places. A positive Qe indicates an MPS value of O.

In the encoder test shown in Table 7 below, the event counter ec is first shown. This is followed by the Qe value and YN symbol at the end of the cycle. The total number of renormalizations in "bits"
It is shown in the column. The "code bytes" are shown exactly as they are output. Two bytes may be listed in this column, indicating both the new byte and the previous byte that has changed.

The test data is displayed in hexadecimal as follows.

For this file, the encoded bit count is 208, including the overhead for flushing the final data. . The actual compressed data stream for either encoder, expressed in hexadecimal, looks like this:

23CAO8826F7E20151C267BAOA
B606CD63AA 26E7 IC197A80A
O7CO Table 1 Qe I (dQ) - hex f6fc hex ffec hex 0Odc hex 0Odc hex OOe4 hex fffc hex 0Obc hex 0Occ hex 0Odc hex 0Oec S8-M l"'lir'-, OO- to h4 good ψt Nono O-NI”Nζii+JNNl'J NIN
−11111〇〇 〇 〇 〇 〇 〇 〇 〇 〇 〇 〇 〇 〇 〇 〇 〇 〇 〇
〇 〇 〇 〇 〇ΦToω＋T% O−−M rl”l
Good r---N 5 ψ and ω's 〇-bad---tN F
J NIN NNIN N-ff
”η−r ψtωΦQ−NMj ψtωΦ1～h4
0 of ψ and ω -1%l NNIN I
N NIN NN (to N -2C30
29 Table 6 Priority encoder operation 256 eefc 1 00006010ooo
ooooo.

190 004e Oa 07 c.

RoN Ll
y mouth■ ωCo small to 5 good to ω's 0 to 5 Φψtodo ψ low 1”l I”11”l M-years old $5-7
$55? LALA u)LALALINIALl'%
%LA'+O.

−−−−0−0−−0=−〇〇〇−−−−−−0−r
”-ao's 0- ~ hhi ψ to's 0- h4 ψ and ω's 0+r+r+r is good, good and good ψψψψψψψψ
ψψto A mouth r++1 − NNNff”l M l’l”l Ma 5 L+
'% LA LA Ll'% LA%J) (n (j
'l口0000−−5tjl■ ρψΦψψψψψψψψψψψψψψψψψψψψTototototototototototo-”−−=−= −==−−−−MO−−−
------0 low 256 eafc + 0O
O09ffO9ffOO0040190004e E0 Effects of the Invention According to the present invention, even if it is a numerical value that is likely to cause trapping, it can be selected as a candidate for the estimated probability value Qe, so the analysis of the Qe value can be made more uniform, and therefore the encoding An excellent effect can be obtained in that it becomes possible to further improve efficiency.

[Brief explanation of the drawing]

FIG. 1 is a block diagram of a general arithmetic coding system including a Q-coder and a Q-decoder according to the present invention. FIG. 2 is an explanatory diagram of a probability number line in which one section is divided into two segments according to suitable encoding and recovery amounts by hardware. FIG. 3 is an explanatory diagram of a probability number line in which one section is divided into two segments according to suitable encoding and recovery amount by software. FIG. 4 shows a plurality of different encoders, and
FIG. 3 is a block diagram for explaining that any of them can be used in conjunction with any of a plurality of mutually different decoders. Figure 5 shows the 32-bit code register (X register) used when compressing and encoding a data stream.
FIG. 2 is an explanatory diagram of bit allocation in FIG. FIG. 6 is an illustration of bit allocation in a 32-bit register used in decoding a compressed data stream. FIG. 7 is an explanatory diagram showing the integration of updating the probability Qe and renormalizing the summand. FIG. 8 is a graph showing inefficiency during encoding. FIG. 9 is an explanatory diagram of a dating circuit used to derive an output Qe value from an input q index. FIG. 10 is a table showing a plurality of contexts, each having an estimated probability. FIG. 11 is an illustration of how a string of bits is interpreted based on context. FIG. 12 is an illustration of a finite state machine representation of a single rate coding system. Figures 13 to 49 show the Q coder and Q coder, respectively.
3 is a flowchart showing the operation of a decoder. FIG. 50 is a general block diagram illustrating the major components of a hardware Q-coder according to the present invention. 51 to 53 are detailed explanatory diagrams of the elements of the Q coder. FIG. 54 is a general block diagram showing the main components of a hardware Q-decoder according to the present invention. 55 and 56 are detailed illustrations of the elements of the Q decoder. Applicant: International Business Machines Corporation Representative Patent Attorney: Takashi Tonmiya - (1 other person) FIG, 1 FIG, 2 8-Tou 1 Lower (-H) Kasato Kasukei / Degohiko FIG,
3 C=C+A Software (-5) Code/decoding possession MPS MPS LPS MPS MPSFI
G, 11 FIG 1,6 FIG, 17 FIG
°20 p FIG, 21 FIG, 22 FIG, 23 FIG, 24 FIG, 31 FIG, 37 FIG, 39 FIG, 40 FIG, 41 FIG, 49

Claims (1)

[Claims] (1) When encoding a series of binary decision events, each time a new decision event is input, a new interval is created that is included in the previously identified interval on the number line. A code that identifies one included point and encodes a series of input judgment events with a numerical value corresponding to the identified point.
In the stream arithmetic coding system, a plurality of candidates for the estimated value Qe of the probability of occurrence of the first event among the judgment events are selected in advance, and in the step of identifying the new interval, the plurality of candidates are selected in advance. Using one of the candidates as the current value of Qe, the numerical value A associated with the length of the interval is used to determine whether the newly input judgment event is the first event or the second event. update to a value related to the current value of Qe, although it differs depending on If the renormalization occurs due to the input of the first event, update the current value of Qe to a larger value among the multiple candidates. , if the renormalization occurs due to the input of the second event, the current value of Qe is updated to a smaller value among the multiple candidates, and the current value of Qe is updated. If renormalization occurs due to the input of the above first event when is AMIN/2^n (n is a positive integer) or a value close to this, the new Qe
As the current value of Qe, select a sufficiently large value so that it will not return to the current value of Qe even if renormalization occurs due to the second event immediately after updating the current value of Qe. A probability adaptation method in an arithmetic coding system characterized by: