JPH08195680A - Arithmetic code decoding device - Google Patents

Abstract

(57) [Summary] [Purpose] To enable high-speed decoding of arithmetic codes. [Structure] Change the processing procedure to reduce the number of register updates. Increase the width of the stuffing bit of the code register to completely eliminate the loop associated with code input. The data is prefetched, two contexts depending on the undetermined preceding pixel are prepared and processed, and one is selected when the preceding pixel is confirmed, the processing is duplicated, and the preceding process is performed. The waiting time until the pixel is fixed is reduced.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an arithmetic coding / decoding device, and in particular, enables high-speed decoding suitable for use in decoding an arithmetically coded binary image. The present invention relates to a simple arithmetic code decoding device.

[0002]

2. Description of the Related Art When transmitting information using a transmission line or storing information in a database, it is desirable that the amount of information transmitted or stored is small. For example, since image information generally has an enormous amount of information, various methods are used for data compression when transmitting or storing the information.

Data compression includes lossy coding and lossless coding. Among the lossless coding,
The so-called entropy coding compresses the data from the information source output having a finite number of symbols by using the bias of the occurrence probability. That is, for symbols with a high appearance probability,
By allocating shorter codes, the average code length of generated codes is shortened, and information compression is achieved by purely statistical properties.

Among the entropy codings, the arithmetic coding can be said to be a practical reorganization of an ideal coding method for a memoryless information source known as Elias coding. In this arithmetic coding, a symbol sequence to be coded is mapped on a probability line which is divided according to the appearance probabilities of the inferior symbol and the dominant symbol, and the arithmetic code is created by encoding according to the position. ("Interface '91 .12 February" 15
See pages 4 to 157).

For example, in the conceptual diagram of the arithmetic code of FIG.
The symbol of "1" is regarded as the inferior symbol having the appearance probability of P, while the symbol of "0" has the appearance probability of (1-P).
Is considered to be the dominant symbol of. For example, "0, 1, 0,
When encoding a 0,1 "symbol sequence, first, the width (referred to as the augend value) A0 of the dominant symbol of (1-P) is obtained corresponding to the first symbol" 0 ". Corresponding to the second symbol "1", (1-P)
An augend value A01 of P is obtained. Corresponding to the third symbol "0", (1-P ) 2 P of augend value A010 is obtained. Corresponding to the fourth symbol "0", (1-P ) 3 P of augend value A0100 is obtained. (1-P) corresponding to the fifth symbol "1"
An augend value A01001 of ³ P ² is obtained. In response to the sixth symbol "1", augend value A010011 in ^{"(1-P) 3 P} 3" is obtained.

These augend values correspond to the range of codes on the probability line as shown in FIG.
What is indicated by the one-dot chain line C in FIG. 1 is the position of the code (referred to as a code) on the probability line. What is generally represented by a binary decimal value according to this code is the result of encoding the arithmetic code.

A coding process for performing such arithmetic coding,
Alternatively, in the decoding process for decoding the arithmetically encoded one, in general, on the probability number line and the augend register that stores the augend value indicating the range of the code on the probability number line as described above. Is a loop process in which the process using the code register that stores the code value indicating the position of the code is repeated.

Further, in the arithmetic code, since the code is regarded as a numerical value and the code is sequentially created by addition, carry may occur, which may affect the already-determined upper bits. A bit stuffing method is used in order to suppress the range of bit inversion due to this carry within a predetermined range.

As shown in FIG. 2, for example, a W-bit monitoring register P is prepared above the V-bit code register C, and the contents of the monitoring register P are all 1's.
Then, one bit "0" is inserted between the monitoring register P and the code register C. In this way, for example, when all of the monitoring registers P are "1", even if a carry occurs in the code register C, the inserted bit is only inverted and becomes "1", and the higher bits are higher than that. It is output without being affected.

Decoding of the arithmetic code is specifically performed as follows. (1) A number of decoded pixels including the immediately preceding pixel are arranged in an arbitrary form and are regarded as bitless to be an integer, and the current context CX is obtained. (2) Obtain the state ST from this context CX. (3) Probability (inferior division width LSZ) and the like are obtained from this state ST. (4) The augend is divided according to the probability, compared with the code value, and decoded. (5) Update the state ST corresponding to the context CX as necessary. (6) Repeat the above.

In the following, for an example having a register structure as shown in FIG.
O / IEC DIS 11544 (CCITT Re
c, T .; 82 (see 1993E) P41 to P46), a specific algorithm of the decoding process will be described. Here, for example, a High register that holds the upper 16 bits of the code register and a lower 1 of the code register
The Clow register that holds 6 bits can be considered as one 32-bit code register, and the code value C
By the normalization (renormalization) of, the bit of the new data from the 15th bit (left end of the figure) of the Clow register is shifted to the 0th bit (right end) of the Chigh register. However, the comparison for decoding is Chi
This is done using only the gh register. The Clow register is a register for handling carry, in which only the upper 8 bits in which “b” is written are used, and new data is stored in the “b” bit of the Clow register one byte at a time. The bit with "a" is a bit indicating the current augend value, and the bit with "x" is a bit indicating a code value. The 17th bit of the augend register A is conceptually present, but can be removed if 16-bit processing is required.

In the decoding process, as shown in the flow chart of FIG. 4, first, an initialization routine is called (step 100) to perform initialization.

The algorithm of this initialization routine is as shown in FIG. 5, for example. In this initialization routine, it is first determined whether it is the first stripe or forced reset of the image (step 200), and if it is the first stripe or forced reset of the image, all possible context CX. The value of the probability evaluation state ST (for example, 7 bits) corresponding to the value of (for example, 12 bits) and the value of the current dominant symbol MPS (for example, 1 bit) are set to "0" (step 202). On the other hand, if it is not the first stripe of the image or a forced reset, then ST and MPX values are set to the values of the end of the preceding stripe for all possible CX values (step 204).

After completion of step 202 or 204, first,
The value of the code register C is set to "0", and the code byte input (BYTE IN) routine (see FIG. 6) described later is called to perform the code input process. Then code register C
Value from the least significant bit LSB side to the most significant bit MSB
After shifting to the left by 8 bits, the code byte input routine is called again to perform the code input processing of the next byte. Further, the value of the code register C is shifted to the left by 8 bits, the code byte input routine is called again, and the code input process of the next byte is performed. As a result, 3 bytes are read into the code register C. Furthermore, set "0x10000" (hexadecimal number) in the augend register A,
Exit this initialization routine.

The algorithm of the sign byte input routine executed at step 206 of the initialization routine is as follows.
For example, as shown in FIG. In this code byte input routine, first, from the encoded bit stream data SCD (for example, 16 bits) until all data is read in byte units (step 300), SCD
1 byte at a time, and the buffer register BUFFER for temporarily holding the latest byte data is set to the same value (step 302). After reading all the data from the SCD, the buffer register BUF
FER is set to "0" (step 304). After step 302 or 304, the buffer register BUF
By shifting the FER to the left by 8 bits and adding it to the code register C, the read byte is inserted into the upper 8 bits of the lower bit Clow of the code register,
The counter CT is reset to 8 (step 30)
6).

Here, CT is a counter that holds the progress of the number of compression bits (the number of shifts per bit) in the lower bit Clow of the code register C. When CT becomes "0", a new byte is stored. Is inserted into Clow.

After exiting the initialization routine, the process returns to step 102 of FIG. 4 and the encoded bit stream data SCD is obtained.
Read out. Next, the context CX is read (step 104), and the state ST corresponding to the context CX is read.
Value ST [CX] of the inferiority division width LSZ prepared in advance and corresponding to the value of each state ST, for example, as shown in FIG. 7, and the inferiority array NLPS which gives the next probability evaluation state, respectively. , The value of the superior array NMPS, and the value of the exchange flag SWTCH for exchanging the superiority and the inferiority, the probability evaluation table (ISO / IEC 115
44: 1993 (E) Table 24; CCITT
Rec, T .; 82 (see P33 of 1993E),
The augend is divided by subtracting the value of the inferior division width LSZ read with the state ST [CX] as an index from the value of the augend register A at that time (step 106). Then, the divided augend value A
Is compared with the upper bit Chigh of the code register storing the code value (step 108). If the augend value A includes the code value C as shown by the solid line in FIG. Is less than "0x8000" (step 110). The MSB of Augend register A is "1", and step 1
If the determination result of 10 is negative, the dominant symbol MPS (1 bit value) at that time is put into the pixel Pix (step 112). On the other hand, MSB of Augend Register A
Is “0” and the determination result of step 110 is positive, the later-described MPS replacement routine (see FIG. 9) and the normalization routine (see FIG. 11) are called (step 11).
4).

On the other hand, if the result of the determination at step 108 is negative and the code value C does not exist in the range of the augend value A as shown by the broken line in FIG. 8, the latter LPS (inferior symbol) is replaced. The routine (see FIG. 10) and the normalization routine are called (step 116).

That is, since it is necessary to align the digit positions of the augend register and the code register performed at the time of the next decoding, the code register C also moves to the left by the same number of bits as the number of bits shifted from the augend register A. Shift and perform normalization (renormalization).

The processes of steps 104 to 116 are
The process is repeated until all pixels are completed (step 118).

The specific algorithm of the MPS replacement routine called in step 114 of the decoding process is as follows:
This is as shown in FIG. That is, the augend value A is compared with the inferior division width LSZ, and if the determination result is negative, the value of the superior symbol MPS is put into the pixel Pix, and the value of the superior array NMPS corresponding to MPS and giving the next probability evaluation state. (For example, 7 bits) is put in the state ST, and the state ST is updated (step 402). On the other hand, when the result of the determination in step 400 is positive, the superior symbol MPS is inverted and the inferior symbol LPS (= 1-MPS) is set to the pixel Pi.
It is put into x (step 404) and it is judged whether the exchange flag SWTCH is 1 (step 406). If the determination result of step 406 is positive, the superior symbol M
Invert PS (step 408), corresponding to LPS,
The value of the inferior array NLPS that gives the next probability evaluation state (for example, 7 bits) is put into the state ST, and the state ST is updated (step 410).

The specific algorithm of the LPS replacement routine called in step 116 of the decoding process is as shown in FIG. That is, the augend value A and the inferior division width LSZ are compared (step 500), and when the determination result is positive, a new code register is obtained by subtracting the augend value A from the code register upper bit value Chigh at that time. The code value is changed as the high-order bit value Chigh, the inferior division width LSZ is set to the augend value A (step 502), and the dominant symbol MPS at that time is put in the pixel Pix and the value of the dominant array NMPS is put in the state ST. The state ST is updated (step 504).

On the other hand, if the determination result of step 500 is negative, the same processing as step 502 (step 5
06), the value (1-MPS) obtained by inverting the dominant symbol MPS is put in the pixel Pix (step 50).
8) It is determined whether the replacement flag SWTCH is "1" (step 510). If the determination result of step 510 is positive, the superior symbol MPS is inverted (step 512) and the value of the inferior array NLPS is set to the state S.
The state ST is updated by entering T (step 514).

Steps 114 and 11 of the decoding process
The specific algorithm of the normalization routine called in 6 is as shown in FIG. That is, it is determined whether or not the counter CT for holding the progress of the number of compression bits (the number of shifts per bit) in the lower bit Clow of the code register C is "0" (step 600), and the counter CT If the value is "0", the sign byte input routine (FIG. 6) is called to insert a new byte into the lower bit Clow (step 602). Next, the values of the registers A and C are shifted to the left one bit at a time, the value of the counter CT is decremented by 1 (step 604), and the augend value A becomes "0x080".
00 ”, that is, M of the augend register A
The value of the augend register A and the value of the code register C are shifted bit by bit until SB becomes "1" (step 606). Even if the determination result in step 606 is negative, if the value of the counter CT is not 0 (step 608), the code byte input routine is called again (step 610).

[0025]

However, conventionally,
Since the intermediate value BUFFER and the like are also stored in the register, the number of times the register is updated is large and the processing speed decreases.
Further, as shown in FIG. 11, the normalization routine has a loop for returning to the step 600 from step 606 and accompanying the code input, and the augend value A and the code value C are shifted by 1 bit, so that the processing speed is also changed. Is reduced. Furthermore,
Since the context CX depends on the value of the pixel Pix decoded immediately before, there is a problem that the decoding of the next pixel cannot be started unless the decoding of the immediately preceding pixel is completed.

The present invention has been made to solve the above-mentioned conventional problems, and an object of the present invention is to provide an arithmetic code decoding device capable of increasing the processing speed and decoding at a high speed.

[0027]

According to the present invention, a symbol sequence to be coded is mapped on a probability number straight line divided according to the appearance probabilities of the inferior symbol and the dominant symbol,
An arithmetic code created by encoding in accordance with the position, an augend register that stores an augend value indicating a range of the code on the probability line, and a position of the code on the probability line. In an arithmetic code decoding device for decoding using a code register that stores a code value, means for generating a current context from preceding data, and determining a state and a current dominant symbol using the context as an index Means for reading the value of the probability evaluation table stored in the read-only memory using the state as an index, and dividing the augend according to the probability read from the probability evaluation table for normalization. The shift amount and means for calculating the value of the code value that may be updated, and whether the code value is superior or inferior as a result of the division. Included in, determine which area is large, divide the processing, a means for generating data, and perform a shift using the previously calculated shift amount according to the distributed result, The object is achieved by providing means for updating the augend register and code register and, if necessary, means for updating the state stored in the random access memory and the current dominant symbol. .

The code register further comprises means for adding the actually shifted amount to the size of the gap of the code register, and means for performing bit stuffing by inserting the following code into the gap of the code register. In addition to the upper bit of the bit length corresponding to the code value and the effective bit length corresponding to the shift amount, an extended lower bit of a bit length capable of accommodating the maximum amount of the gap is included, and the lower bit is It also achieves the above object by being used as a stuffing bit.

In a similar arithmetic code decoding device,
Means for generating a plurality of contexts depending on undetermined data among preceding data, and means for generating a candidate of a state and a current dominant symbol corresponding to each of the plurality of contexts as an index By providing a means for determining a state to be actually used and a current dominant symbol from among the candidates when the preceding data is determined,
Similarly, the above-mentioned object is achieved.

[0030]

According to the present invention, the processing speed is increased by changing the processing procedure and reducing the number of register updates.

In addition to this, the width of the code register is expanded to completely eliminate the loop associated with the code input, thereby increasing the processing speed.

In addition, 2 depending on the previous undetermined data
This is to speed up the processing speed by preparing two contexts, duplicating the processing by prefetching, and selecting one when the preceding data is determined.

[0033]

Embodiments of the present invention will now be described in detail with reference to the drawings.

The decoding process in this embodiment is executed according to the procedure shown in FIGS. 12 to 14 correspond to step 102 and subsequent steps of the conventional example shown in FIG. 4. First, in steps 700 to 704 of FIG. 12, a random access memory (RAM) is referenced with context CX as an index. Thus, the state ST and the dominant symbol MPS are generated. Specifically, since the context CX depends on the decoded value of the immediately preceding pixel, the immediately preceding pixel is “0”.
Considering the case of "1" and the case of "1", two RAMs are used,
The context CX in each case is set to CX0 and CX1 (for example, 12 bits) (step 700). Then, using the contexts CX0 and CX1, the corresponding state ST
0 and ST1 (for example, 7 bits) are generated and used as ST candidates. In addition, the poor array NLPS used in the previous decoding
And the dominant array NMPS (eg 7 bits) is also in state ST
(Step 702). Further, similarly to the state ST, the corresponding dominant symbols MPS0 and MPS1 (for example, 1 bit) are generated from the contexts CX0 and CX1 and are set as candidates for the dominant symbol MPS. In addition, the dominant symbol MPS used for the immediately preceding decoding and its inversion are M
It is a candidate for PS (step 704). The above steps 700 to 704 are the procedure for reading from the RAM.

Next, in step 706, the state ST and the dominant symbol MPS to be actually used are determined (selected) from the immediately preceding pixel value and the like by "discrimination" described later.

Next, the routine proceeds to step 708, where the read-only memory (RO
By referring to the probability evaluation table previously stored in M) as shown in FIG. 7, the inferior division width LSZ,
The inferior array NLPS, the superior array NMPS, and the replacement flag SWTCH are determined (reading of ROM).

Next, in step 710 of FIG. 13, the inferior division width LSZ is stored in the register p (for example, 15 bits), and the inferior division width LSZ is calculated from the augend value A at that time.
The augend is divided by putting a value obtained by subtracting into the register q (for example, 16 bits). Next, in step 712, p is set to "0" in order to normalize the register p.
x8000 "or more shift amount ps (for example, 4
Bit) and q to “0x to normalize register q
The stuffing bit is updated to 30 bits in the code register C (for example, 46 bits) by obtaining the shift amount qs (for example, 4 bits) for making 8000 ″ or more and subtracting q from the code value C. Calculate possible values C '(eg 46 bits) (division etc.).

Next, in steps 714 to 718, four values are selected depending on whether the code value Chigh is included in the inferior region p or the superior region q, and which of the inferior region p and the superior region q is larger. It is allotted to the processing of.

At this point, for example, FIGS.
A selection signal used when decoding the next pixel is generated by using the relationship shown in FIG. In FIGS. 13 and 14, X is a don't care state that may be either “0” or “1”.

When the determination results of steps 714 and 716 are both positive, that is, as shown by the solid line in FIG.
If Chigh (= C) is included in the dominant region q and the dominant region q is smaller than the inferior region p, step 72
0, and the inferior symbol LPS at that time is set to the pixel Pix.
And Next, at step 722, the register q is collectively shifted to the left by the previously calculated shift amount qs to obtain the augend value A, and the code value C (= Chig
h) are collectively shifted by the shift amount qs to the left to obtain a new code value C (shift and update of register).

Next, in step 724, if the replacement flag SWTCH is set, the dominant symbol MPS is inverted in step 726, and the inferior array NLPS is set to the state ST (update of RAM) in step 728.

On the other hand, if the determination result of step 714 is positive,
When the determination result of step 716 is negative, that is, in FIG.
As indicated by the solid line in 8, when the code value C is included in the dominant region q and the dominant region q is not smaller than the inferior region p,
Proceed to step 730, and the dominant symbol MPS at that time
The value of is put into the pixel Pix. Next, in step 732, similar to step 722, the shift amount qs is combined and updated, and the augend register and the code register are updated (shift and register update).

Next, in step 734, if the shift amount qs for normalizing q is not "0", the dominant array NMPS is put in the state ST in step 736 (RAM update).

If the determination result of step 714 is negative and the determination result of step 718 is positive, that is,
As shown by the broken line in FIG. 17, when the code value C is not included in the dominant region q and the dominant region q is smaller than the inferior region p, the process proceeds to step 740, and similarly to step 730, the dominant symbol MPS at that time is selected. A value is put in the pixel Pix, and in step 742, the register p is collectively shifted by the pre-calculated shift amount ps to the left and is set as a new augend value A, and the code value candidate C obtained in step 712 is obtained. ′ ′ Is shifted to the left by a shift amount qs, and the new code value C is used to update the register (shift and update of register).

Next, in step 744, the value of the dominant array NMPS at that time is put in the state ST (update of RAM).

If the determination results of steps 714 and 718 are negative, that is, as shown by the broken line in FIG. 18, the code value C is not included in the dominant region q, and the dominant region q is the inferior region. If it is not smaller than p, the process proceeds to step 750, the inferior symbol LPS at that time is put into the pixel Pix, and in step 752, the registers p are collectively shifted by the shift amount ps to the left and set as a new augend value A, and the code value The candidate C ′ of (1) is collectively shifted by the shift amount qs and shifted to the left as a new code value C, and the register is updated (shift and update of register).

Next, in step 754, if the replacement flag SWTCH is "1", the dominant symbol MPS is inverted in step 756, and the value of the inferior array NLPS at that time is entered in the state ST in step 758 ( RAM
Update).

Then, steps 760 to 768 of FIG.
Then, the code is input and normalized in byte units (code byte input: BYTE IN). Specifically, in step 760, of the shift amounts ps and qs, the amount actually used for the shift is set to S (for example, 4 bits), and step 76
At 2, the counter CS (for example, 5 bits) holding the size of the gap created in the code register by the shift is incremented by S. This counter CS corresponds to the conventional counter CT.

Then, the procedure proceeds to step 764, and when the size CS of this gap becomes 16 or more, step 766.
Then, in the code value C, the next encoded data SCD (for example, 1
(6 bits) are added together by shifting (CS-16) to the left, and a counter C corresponding to the input is added.
A new CS obtained by subtracting S by “16” is read in as a new encoded data SCD in step 768, and the process proceeds to the next data.

As shown in FIG. 19, the code register C in this embodiment has only the upper 16 bits Chigh for storing a code value as in the conventional case and only 16 bits in the conventional example as shown in FIG. The stuffing bit is expanded to 30 bits, and the total of Clow is 46 bits. 15 stuffing bits like this
By setting bits × 2 = 30 bits, the processing can be simplified together with the above processing procedure.

That is, if the code register shifts in the order of, for example, the actual shift amounts S = 5, S = 6, and S = 7 according to the normalization, the effective bits of V shown in FIG. "0" enters the gap. Now, as an initial value, if the gap counter CS = 0, that is, if there is no gap,
First, it shifts 5 bits, so the gap becomes 5 bits,
Next, 6 bits are shifted, so the gap becomes 5 + 6 = 11 bits, and further 7 bits are shifted, so the gap becomes 11
+ 7 = 18 bits. Since the gap becomes 16 bits or more by this third shift, the next code data SCD is put in the gap and bit stuffing is performed.

The reason why Clow is set to 30 bits is as follows. That is, if the bit length of Clow is W and the gap is CS, the effective bit length L in Clow is L.
Is represented by L = W-CS.

On the other hand, since the maximum shift amount S is 15, the effective bit length L must be 15 or more. Also, the gap C
Since S is 15 at the maximum, in order to satisfy the condition that L is 15 or more, W (= L + CS) is 3 as shown in FIG.
Must be 0 or greater. FIG. 20 shows a state in which CS = 15, that is, the gap is maximum and the effective bit is minimum.

FIG. 21 shows a time chart of the processing in this embodiment. When the pixel n is decoded, the RAM is read out first (corresponding to steps 700 to 704 in FIG. 12). At this point, since the decoding of the immediately preceding pixel n-1 has not been completed, the context CX cannot be uniquely determined. So R
Two AMs are used so that both the case where the pixel n-1 is 0 and the case where the pixel n-1 is 1 can be dealt with.

At the time when the reading of the RAM of the pixel n is completed, the immediately preceding pixel n-1 is determined (step 71 in FIG. 13).
(Corresponding to 4 to 718) is finished, and the pixel n-1 is determined to be 0 or 1. Then, according to the value of the pixel n-1,
Select an appropriate state from the RAM read results (Fig. 12
Corresponding to step 706). According to this selection result, the ROM is read (corresponding to step 708 in FIG. 12). It takes 2 clocks to read this ROM, and the probability (recessive division width LSZ) and the like can be obtained. The pixel n is divided (corresponding to steps 710 to 712 in FIG. 13) based on the obtained probability and register value. Discrimination (including pixel generation) is performed based on the division result (step 71 in FIG. 13).
4 to 720, 730, 740, 750).

Next, a shift process (corresponding to steps 722, 732, 742, and 752 in FIG. 13) is performed to update the register, and RAM is updated (steps 724 to 728 and 734 to 736 in FIG. 13) if necessary. , 744, 7
54 to 758) to update the register.

Further, if necessary, a code byte input (BY
TE IN: Corresponding to steps 760 to 768 in FIG. 14)
I do.

In this embodiment, since the lower bit (stuffing bit) of the code register is expanded to 30 bits, it is possible to rapidly perform processing in units of 16 bits. On the other hand, conventionally, it took time in units of 8 bits.

In this embodiment, as shown in FIG.
Since the RAM is read out before the immediately preceding pixel n-1 is determined and a pixel is generated, the processing speed can be increased. On the other hand, conventionally, when the code byte input (writing to the code register C) of the immediately preceding pixel is completed, the RAM reading of the next pixel is started for the first time. Therefore, in the example of FIG. , It took extra time.

FIG. 22 shows the construction of an embodiment of the apparatus using the present invention.

This embodiment has an arithmetic processing unit 10 for performing subtraction, comparison, shift, register processing, etc., and two RAMs, and corresponds to the case where the preceding pixel value is "0" or "1". As possible, the state generator 60 that generates the two states ST0 and ST1 and the dominant symbols MPS0 and MPS1 and the multiplexer 70 that selects the correct state ST and the dominant symbol MPS according to the selection signal generated according to the preceding pixel. And a probability estimation unit 80 that generates a probability and the like using a ROM that stores a probability evaluation table.

The arithmetic processing unit 10 is specifically shown in FIG.
As shown in 3, the augend value A and the inferior division width LSZ
Latches 12 and 14 for temporarily holding the
By subtracting LSZ from A input via 2 and 14, division processing corresponding to step 710 in FIG. 13 is performed, and a subtraction circuit 16 that outputs p and q, and p output from the subtraction circuit 16 are performed. Latches 18 and 20 that temporarily hold the values of q and q, respectively, and a shift amount calculation circuit 22 that calculates shift amounts ps and qs according to the values of p and q output from the latches 18 and 20, respectively. A subtraction circuit 2 for calculating a code value candidate C ′ by subtracting the value of q from the code value C stored in the upper 16 bits of the code register.
4 and the values of p and q held in the code value C and the latches 18 and 20, and steps 714 to 71 of FIG.
The discrimination circuit 26 for performing discrimination processing corresponding to 8 to generate a pixel, a selection signal, etc., and the outputs of the shift amount calculation circuit 22, the latches 18, 20, and the subtraction circuit 24 according to the discrimination result of the discrimination circuit 26, respectively. Multiplexer 2 to select
8, 30, 32 and the multiplexers 28, 30, 3
2. Latches 34, 36, 38, 40 for temporarily holding the output of the discriminating circuit 26, and the shift amount ps input from the latch 34 with respect to the value of p or q input from the latch 36. A shift circuit 42 for shifting by qs and a shift circuit 4 for shifting qs with respect to the code value C or its candidate C'input from the latch 38.
4 and the shift amount input from the latch 34, the code register control circuit 4 for performing the processing of the clearance counter CS of FIG.
6, latches 48 and 50 for latching the outputs of the shift circuits 42 and 44, an augend register 52 whose contents are updated by the output of the latch 48, and an output of the code register control circuit 46. The contents are updated by the output of the memory 54, if necessary, by the memory 54 for inputting the encoded data SCD and storing it in the first-in first-out (FIFO) memory and the control signal from the code register control circuit 46. And a code register 56 to be used.

As the shift amount calculation circuit 22, for example, a priority encoder can be effectively used. That is, the shift amount is "how many bits left (MSB direction)
Shifting to will result in more than "0x8000"? Means. Further, "0x8000" or more means that the MSB is "1". Therefore, the calculation of the shift amount results in the problem of "what bit, when counted from the MSB, has" 1 "?". This problem can be solved by a priority encoder having a logic as shown in FIG. For example, if the 15th bit of the input is "1",
"0" is output regardless of other inputs. Further, for example, if the fifteenth bit to the thirteenth bit are "0" and the twelfth bit is "1", "3" is similarly output, and the shift amount can be obtained in both cases.

In the present embodiment, since the processing procedure in which the number of register updates is small, the code register in which the stuffing bit is extended, and the processing by the pre-reading of undetermined pixels are duplicated, the processing speed is extremely high. can do. Note that it is also possible to use these processes independently without combining them.

[0065]

As described above, according to the present invention,
The processing speed can be increased and decoding can be performed at high speed, and the speed can be increased several times to several tens of times faster than the conventional one.

[Brief description of drawings]

FIG. 1 is a diagram showing an example of a probability line in arithmetic code.

FIG. 2 is a diagram explaining the principle of bit stuffing.

FIG. 3 is a diagram showing an example of a configuration of a conventional decoding register.

FIG. 4 is a flowchart showing a basic procedure of a conventional decoding process.

FIG. 5 is a flowchart showing an example of an initialization routine.

FIG. 6 is a flow chart showing an example of a code byte input routine.

FIG. 7 is a diagram showing an example of a probability evaluation table.

FIG. 8 is a diagram showing an example of the relationship between the augend and the code value.

FIG. 9 is a flowchart showing an example of a dominant symbol (MPS) replacement routine.

FIG. 10 is a flow chart showing an example of an inferior symbol (LPS) replacement routine.

FIG. 11 is a flow chart showing an example of a normalization (renormalization) routine.

FIG. 12 is a flowchart showing a part of a processing procedure of an embodiment of the arithmetic decoding processing device according to the present invention.

13 is a flowchart showing a part of the processing procedure following FIG.

14 is a flowchart showing the rest of the processing procedure following FIG.

FIG. 15 is a diagram showing an example of selection criteria of a state ST in the processing procedure.

FIG. 16 is a diagram similarly showing an example of selection criteria of the dominant symbol MPS.

FIG. 17 is a diagram showing an example of the relationship between divided augends and code values.

FIG. 18 is a diagram similarly showing another example of the relationship between the divided augend and the code value.

FIG. 19 is a diagram showing a configuration of a code register used in the embodiment and an example of its shift state.

FIG. 20 is a line diagram showing an example of the state of the code register when the gap is maximum and the effective bit is minimum.

FIG. 21 is a time chart showing an example of the temporal relationship of the processing procedure for each pixel in the embodiment.

FIG. 22 is a block diagram showing the overall configuration of the embodiment.

FIG. 23 is a block diagram showing a specific configuration example of the arithmetic processing unit according to the embodiment.

FIG. 24 is a diagram showing a logic of a priority encoder used as a shift amount calculation circuit of the arithmetic processing unit.

[Explanation of symbols]

 A ... Augend value C ... Code value SCD ... Encoded bit stream data CX ... Context ST ... State Pix ... Pixel LSZ ... Inferior division width MPS ... Dominant symbol LPS ... Inferior symbol p, q ... Register ps, qs ... Shift amount 10 ... Arithmetic processing unit 16, 24 ... Subtraction circuit 22 ... Shift amount calculation circuit 26 ... Discrimination circuit 28, 30, 32 ... Multiplexer 42 ... Shift circuit 46 ... Code register control circuit 52 ... Augend register 54 ... Memory 56 ... Code register 60 ... State generation unit 70 ... Multiplexer 80 ... Probability estimation unit

Claims (3)

[Claims] 1. An arithmetic code created by mapping a symbol sequence to be coded on a probability number line obtained by dividing according to the appearance probabilities of the inferior symbol and the dominant symbol, and encoding according to the position of the symbol sequence. An arithmetic code for decoding by using an augend register that stores an augend value indicating a range of codes on a number line and a code register that also stores a code value indicating a position of a code on a probability number line In the decoding device, means for generating a current context from preceding data, means for determining a state and a current dominant symbol using the context as an index, and storing the state in the read-only memory as an index Means for reading out the value of the read probability evaluation table, and dividing the augend according to the probability read from the probability evaluation table Shift amount for normalization, and
A means to calculate the value of code value that may be updated, and as a result of the division, determine which area of the code value is superior or inferior and which area is larger, divide the processing, and generate the data. And a means for updating the augend register and the code register by performing a shift using the previously calculated shift amount according to the distributed result, and a random access memory if necessary. And a means for updating the state and the current dominant symbol stored in the arithmetic code decoding apparatus. 2. The method according to claim 1, further comprising means for adding the actually shifted amount to the size of the clearance of the code register, and means for performing the bit stuffing by inserting the following code into the clearance of the code register. Wherein the code register has an upper bit of a bit length corresponding to a code value and an effective bit length corresponding to a shift amount, and an extended lower bit of a bit length capable of accommodating the maximum amount of the gap. And an arithmetic code decoding device, wherein the lower bit is used as a stuffing bit. 3. An arithmetic code created by mapping a symbol sequence to be coded on a probability number line obtained by dividing according to the appearance probabilities of the inferior symbol and the dominant symbol, and encoding according to the position of the symbol. An arithmetic code for decoding by using an augend register that stores an augend value indicating a range of codes on a number line and a code register that also stores a code value indicating a position of a code on a probability number line In the decoding device, means for generating a plurality of contexts depending on undetermined data among preceding data, and a state and a current dominant symbol candidate corresponding to each of the plurality of contexts as an index And the means for generating the preceding data, the state to be actually used and the current dominant symbol are determined from the candidates at the stage where the preceding data is determined. Arithmetic coding decoding apparatus comprising: the means.