JPH07249995A - Data encoder - Google Patents

Abstract

(57) [Abstract] [Purpose] To increase the processing speed of encoding and decoding by collectively processing input data of multiple bits. [Arrangement] The probability of occurrence of a symbol sequence in N-bit input data is calculated for a specified Markov model,
An area corresponding to the input data is collectively assigned to the input symbol string. Further, in updating the probability estimation value, the probability estimation values of all the inferior symbols are updated in the normalization of the dominant symbol sequence, and the probability estimation values of only the encoded inferior symbols are updated in the normalization of the inferior symbol sequence.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to the structure of a data encoding device in, for example, an image communication device or an image storage device.

[0002]

2. Description of the Related Art Conventionally, MH and MMR coding have been proposed as entropy coding for images, and have been put to practical use in facsimiles and the like. In addition, an arithmetic encoder that can realize high compression efficiency has been devised as an image encoding method for binary images and color images (IBM Journal of Research and
Development Vol.32, No.6, Nov.1988), which is adopted in the binary image coding standard (JBIG).

The arithmetic encoder defines a Markov model for the data to be encoded, estimates the occurrence probability of the encoded data from the state of the Markov model, and calculates the number according to the magnitude of the estimated occurrence probability. A straight line is divided to generate a code word. The symbol with a high probability of occurrence is the dominant symbol (More Probable Simbol: MPS), and the symbol with a low probability of occurrence is the lesser symbol (Less Probable Simbol: MPS).
(l: LPS), predict the next generated symbol from the state of the Markov model for the already encoded symbol,
If the prediction is correct, the probability of MPS occurrence is given as the region width of the number line, and if the prediction is incorrect, the probability of occurrence of the LPS is given as the region width of the number line. It is an encoding device that outputs existing positions as code words.

A specific example of encoding will be described below.
However, here, encoding of binary symbol 1 bit is assumed.

First, a number line from 0.0 to 1.0 is defined, the width (augent) of the currently allocated area is A, and the lowest end of the allocated area is C. C = 0.0 and A = as initial values before encoding
Encoding is started as 1.0. MP the area of the number line
Assuming that the occurrence probability of S is p and the occurrence probability of LPS is q, the sum of the occurrence probability of the dominant symbol and the occurrence probability of the inferior symbol is 1, so p + q = 1. When the symbol s is MPS, Ai = p * Ai-1 = (1-q) * Ai-1 Ci = Ci-1 In the case of LPS, Ai = q.Ai-1 Ci = Ci-1 + (1-q) .Ai-1. At this time, multiplication is required for the calculation of q · Ai−1, but in order to avoid this multiplication, q · Ai−1 has a fixed value Q according to the occurrence probability as a table, and the fixed value Q is obtained from the table. A subtraction type arithmetic code has been devised which simplifies the operation by selecting it.

Therefore, Ai and Ci are the symbols s
Is MPS, Ai = Ai-1-Q Ci = Ci-1 When the symbol s is LPS, Ai = Q Ci = Ci-1 + (Ai-1-Q).

Further, JP-A-63-76525 and JP-A-2-285774 have been devised for the fixed value Q of the probability estimation table.

The arithmetic encoder repeats the above-mentioned operation until the symbol s is completed, and outputs the operation result C as a code word. C is the lower end point of the augento A, and the position of C is uniquely obtained, so that it is established as a code word. However, when the above calculation is repeated, Ai becomes small and the calculation accuracy becomes insufficient. Therefore, A is 1/2
The accuracy of the operation is guaranteed by performing an operation (normalization) that doubles A so that A becomes ½ or more when the value is less than 1. At this time, double A and at the same time double C. The definition of encoding is also preserved.

An arithmetic coder which is a high-efficiency compression coding is applied to a color image (gradation image), a multi-color image (limited color image).
In the conventional case, as shown in FIG.
Data (MCP) represented by bits is subjected to binary sequence conversion, and then encoded by the above-mentioned binary arithmetic encoder which encodes the binary symbol s.

In FIG. 5, reference numeral 11 is a delay device for storing image data MCP represented by N bits per pixel.
Reference numeral 2 is a context generation circuit that defines a Markov model from already encoded data, and outputs a context CX from the state of the Markov model, and 14 is a binary data from the input data MCP expressing a gradation image or a limited color image. B
It is a binary sequence converter for converting to D. As the binary sequence converter, a parallel / serial converter that can be configured by a shift register may be used, or a specific binary codeword may be assigned to a multi-color image as disclosed in JP-A-2-285774. Reference numeral 13 is a binary arithmetic encoder that inputs the context output from the context generation circuit 12 and the binary data BD from the binary sequence converter 14 and outputs the code word CODE.

As described above, an arithmetic coder is used as a highly efficient entropy coder for color images and multicolor images. The arithmetic code defines a Markov model in which pixels around the pixel to be coded are used as reference pixels and generates a context, so that the correlation between adjacent pixels of the image can be used, and thus a high compression rate is realized.

[0012]

However, in the above-mentioned conventional technique, since the addition and subtraction processing of the arithmetic encoder is performed for each bit, the following arithmetic encoding processing is executed in encoding until the codeword CODE is determined. Can not. Similarly, in the decryption, the next CODE until the decryption of the data is completed.
Cannot start arithmetic decoding process of. Therefore, it is difficult to realize high-speed processing with the conventional arithmetic encoder / decoder configuration.

A pipeline processing may be introduced into the arithmetic operation to speed up the arithmetic coding / decoding processing. However, in the conventional arithmetic encoder, 1-bit data is encoded and decoded. In order to update the probability estimation table of the arithmetic encoder, the update of the probability estimation table is detected,
When the update is performed, it is necessary to interrupt the process and use the result after updating the probability estimation table to re-execute the calculation, which is an obstacle to realizing the pipeline process.

Therefore, it is an object of the present invention to provide a data coding apparatus capable of realizing high speed processing while maintaining high coding efficiency of entropy coding.

[0015]

In order to solve the above-mentioned problems, a data coding apparatus according to the present invention is a data coding apparatus for processing data such as an image in a plurality of bits at a time. , A context (CX) that specifies the Markov model from the input data stored in the delay device and indicates the state before the data to be encoded
And a multi-valued arithmetic encoder that outputs a code word from the input data and the context.

In the decoding, a delay unit for storing the decoded data from the multi-value arithmetic decoder, and a state before the input of the data to be coded by defining the Markov model from the decoded data stored in the delay unit. And a multivalued arithmetic decoder that inputs the codeword and the context and decodes the original data.

Further, a probability estimation table for storing the probability of occurrence of a symbol in a probability estimation table, a transition destination table for storing state transitions for generating a probability estimation value of a symbol according to input data, and input data. In the above-mentioned multi-valued arithmetic coder comprising a probability updating device that outputs the index of the probability estimation table according to the history of the past dominant symbol sequence and the normalization condition of the arithmetic code, the probability of occurrence of N-bit input data is divided into cases, A plurality of index memories that store indexes indicating the occurrence probabilities in each case, a predominant symbol string memory that stores the symbol string with the highest probability estimation value that appears in the input data, and N-bit data and symbol string occurrences. It is characterized by comprising a multi-symbol arithmetic code arithmetic unit for inputting a probability and outputting a code word.

Further, N-bit data (2 to the Nth power-
1) Estimated probability of occurrence of one inferior symbol sequence, dominant symbol sequence with the highest probability of occurrence, and data to be encoded, calculate the position of the number line according to the probability of occurrence, and output the codeword. It is characterized by having the above-mentioned multi-symbol arithmetic code arithmetic unit.

Further, in the above-mentioned multi-value arithmetic encoder and multi-value arithmetic decoder, when the length of the number line assigned to the symbol according to the occurrence probability of the input symbol is less than 1/2 and the normalization processing is performed. In addition, a probability updating device configured by means for updating probability estimation values of all inferior symbols during normalization by the dominant symbol sequence and means for updating probability estimation values for inferior symbol sequences generated during normalization by the inferior symbol sequence. It is characterized by having.

[0020]

The input data in the data encoding apparatus of the present invention described below is limited to a multi-color image expressing a color code of one pixel by N bits, and a preferable embodiment is shown. Further, the present invention can be applied to a gradation image expressing one pixel with N bits and data expressing a character in byte units. In the present embodiment, the bit number of one pixel is described as representing two bits and a color code of four colors.

FIG. 3 shows the configuration of an embodiment of a data encoding device to which the present invention is applied. Reference numeral 1 is a delay device for storing the input pixel MCP 101 of the multi-color image, which can be realized by a line buffer or the like. Reference numeral 2 is a context generation circuit that inputs the already encoded pixel data stored by the delay device 1 and outputs the context CX103 of the Markov model. In the context generation circuit 2, the input pixel MCP
A Markov model is defined by pixels having a strong correlation with respect to and a context is generated according to the state of the DP 102 input from the delay device. Reference numeral 3 denotes a multi-value arithmetic encoder which inputs a symbol string expressing the input pixel MCP and the context 103, estimates the occurrence probability of a symbol string of a plurality of bits, and arithmetically encodes it. CO output from the multi-value arithmetic encoder 3
The DE 104 is stored in the memory in the case of the image storage device, and is sent to the transmission line in the case of the image communication device.

Next, the decoding process will be described. Reference numeral 6 is a multi-value arithmetic decoder, which receives the CODE 104 output from the transmission line or the image memory and the CX'105 output from the context generation circuit 4 and inputs the decoded data MCP'107.
Is a multilevel arithmetic decoder that outputs Similarly to the multi-value arithmetic encoder 3, 6 is a multi-value that estimates the probability that an N-bit symbol string will occur depending on the state of the context and simultaneously outputs a plurality of bits that output N-bit decoded data to CODE. It is an arithmetic decoder. Since the arithmetic encoder / decoder is lossless encoding, the input data 101 and the decoded data 107 are the same. A delay device 5 stores the decoded data 107 and is composed of a line buffer or the like. Reference numeral 4 denotes a decoding side context generation circuit, which outputs the context CX ′ 105 indicating the state of the Markov model in accordance with the output DP from the delay device as in the encoding side. Coding of the same pixel
Upon decoding, CX on the encoding side and CX ′ on the decoder side show the same state, and the encoder and the decoder basically perform the same operation.

FIG. 4 shows an embodiment of the context generating circuit. When the input pixel 101 is a 2-bit multi-color image and the pixel data n bits before the pixel 101 to be encoded is required as a reference pixel of the Markov model, a 2 × n-bit delay unit 1 is required. . When defining a Markov model in which the number of reference pixels is m, data for m pixels is extracted from the delay device, the model is defined by the model generation circuit 21 that can be configured by a multiplexer, and the context 104 indicating the state of the Markov model is output. To do. It is also possible to adaptively change the model by the model select signal Msel as to which model is to be defined. Further, the model generation circuit 21 may be configured to input 2m-bit reference pixel data from a delay device, degenerate the Markov model, and output a k-bit (k <2m) context. Degenerating the model eliminates the redundancy of the Markov model and expresses the features of the input data with a smaller number of bits.
By degenerating the Markov model, it is possible to reduce the memory for storing the probability estimation value.

The outline of the present invention will be described with reference to FIG. The number line of the arithmetic code is changed from 0.0 to 1.0, 1.0 is given to the width of the orient A as an initial value, and the code word (CODE)
Let C = 0.0 be the lower end of the orient A. In addition, in the subtraction type arithmetic code, the order of the orient assignment of each symbol string MCP is 00, 01, 1 in order.
Assign an augento as a 0, 11 symbol string. A00, A01, A10, and A11 each represent an augent assigned to each symbol string, and C0
0, C01, C10, and C11 indicate the CODE positions when the respective symbol strings are generated. At the start of encoding, when an orient for a symbol sequence is given as shown in the figure, 00 is the dominant symbol sequence, and the other 01, 10, 11 are inferior symbol sequences, and the longest orient is given to the dominant symbol sequence. To be MCP =
When 00 is encoded, the augenent is A = A00 and the codeword C = C00. In encoding, A1
0 becomes the dominant symbol string, and the other symbols become the inferior symbol string. When encoding MCP = 10, the orient is A = A10 and the codeword C = C10.
Similarly, in encoding, A01 becomes the dominant symbol string,
Since the dominant symbol 01 is coded, the orient is A = A01 and the codeword is C01. In the encoding of 0, 00 is the dominant symbol sequence, but 11 inferior symbol sequences are encoded, and the orient is A = A11 and codeword C = C11. In this way, encoding is continued through similar processing steps for the superior symbol and the inferior symbol. As shown in the figure, when encoding is repeated, the width of the orient gradually becomes smaller, and it becomes impossible to guarantee sufficient calculation accuracy. Therefore, even in the multi-valued arithmetic encoder of the present invention that simultaneously processes a plurality of symbol sequences, when the orient A is less than 1/2 as in the conventional binary arithmetic encoder that performs bit-by-bit encoding, Normalization processing that doubles the augen is performed to ensure the arithmetic accuracy of the arithmetic code.

FIG. 1 is a diagram showing the configuration of a multilevel arithmetic encoder for collectively encoding a plurality of symbols according to the present invention. The Markov model context 103 is the address of the plurality of index memories 31, 32, 33 and the dominant symbol string memory 34. Probability estimation table 3 in the index memory
The state (index) of 6 is stored. That is, the probability estimation table stores a probability estimation value indicating the probability of occurrence of a symbol string, and when the index of the table is given, the estimated value of the probability of occurrence of the symbol string is output. Therefore, the probability of occurrence of the symbol string can be output by reading the data from the address of the index memory according to the state of the context. In the present invention, since a plurality of symbols (N bits) are collectively processed, (2 N power-
1) It is necessary to prepare one index memory and calculate the occurrence probability of each index memory. The occurrence probabilities stored in the index memory are all the probabilities of occurrence of the inferior symbol sequence, and the probabilities of occurrence of the dominant symbols are obtained by A- (Q0 + Q1 + Q2). The dominant symbol string memory 34 stores the dominant symbol string MSS for the context. Index memory 31, 32, 33 and dominant symbol string memory 34
Requires a memory capacity for the number of context states.

In FIG. 1, one probability estimation table 36 is accessed from a plurality of index memories. Access to the probability estimation table from each index memory is arbitrated by the multiplexer 45, and the probability estimation value is read out in a time division manner and stored in the Q registers 38, 40, 42. On the other hand, by preparing the probability estimation table 36 in the same number as the index memory, the multiplexers 45, Q
The registers 38, 40, 42 can be deleted, and the processing speed can be improved. However, if the hardware scale of the probability estimation table is large,
As shown in (1), the hardware scale can be reduced by the configuration in which one probability estimation table is accessed in a time division manner.

Reference numeral 44 is the probability estimation values Q0 (111), Q1 (112) and Q2 (113) output from the Q register, the dominant symbol sequence MSSi124 and the input pixel data M.
Input CP101, perform coding processing, and CODE104
Is a multi-symbol arithmetic code arithmetic unit for outputting.

In the embodiment shown in FIG. 1, the update of the probability is performed when the normalization of the augent of the arithmetic code occurs. It is also possible to set the probability update condition by counting the number of times the symbols occur consecutively. The update of the probability estimation value includes the update of the probability estimation value associated with the dominant symbol and the update of the probability estimation value associated with the inferior symbol. The transition destination table 37 storing the indexes of the transition destinations for both updates is created, and the transition destinations can be determined by table lookup. The probability updating device 35 controls the index of the probability estimation table according to the normalization condition.

The control of updating the probability estimate by learning will be described in detail below. ST registers 39, 41, 4
3 stores the index of the probability estimation table that transits at the next probability update of the inferior symbol sequence. The ST register stores both the update index associated with the dominant symbol sequence and the update index associated with the inferior symbol sequence.
In the probability updating device 35, the ST indexes 114, 115,
116 and the current dominant symbol sequence 124 are updated according to the update condition. The input pixel 101 and the normalization condition REN117 output from the multi-symbol arithmetic code arithmetic unit 44
And the new dominant symbol sequence MSSo (120) and index ST0 (12) by the orient Ap for the input pixel and the orient Amssi for the dominant symbol sequence.
1), ST1 (122), ST2 (123) are obtained, and the memory is updated.

Further, the index of the transition destination is also (2 to the Nth power −1), as the probability estimation value is prepared by the number of symbol sequences.
It is necessary to prepare each one, and the transition destination address corresponding to the symbol string is stored in the ST registers 39, 41, 43. The embodiment of FIG. 1 employs a configuration in which the reading of the index from the transition destination table is loaded into the ST registers 39, 41, 43 in a time division manner for the symbol string selected by the multiplexer. On the other hand, the probability estimation table 36
It is also possible to adopt a configuration in which a plurality of transition destination tables are prepared as in the case of access to.

FIG. 6 is a diagram showing the configuration of a multi-symbol arithmetic code arithmetic unit according to the present invention. Probability estimated values 111, 112, 1 of the inferior symbol sequence output from the probability estimation table
13 is input to adders (subtractors) 51, 52, 53,
Output 1 of A register 58 showing the current width of the orient
Amssi (A-Q0-Q1-Q2) is obtained by subtraction with 33.
Amssi is input to the probability updating device 35 and used as a probability updating condition. The switch 54 is the dominant symbol array MS
Si124 as a selector Q1, Q2, Q3, Amssi
Is the width A00 (136) of the orient of each symbol string,
A01 (137), A10 (138), A11 (13
Switch to 9). The input pixel 101 is used as a selector by the multiplexer 55, and the augent (136-13
The encoded orient is selected from 9). Authentic Amcp (11
8) is input to the shift amount control device 56, the barrel shifter 57, and the probability updating device 35. Normalization is performed by controlling the barrel shifter 57 by the shift amount control device 56, and the normalized ogent 134 is stored in the A register 58.

In addition, the symbol string augento A00,
A01, A10 and the output 140 of the C register 64 are added by the adders 59, 60, 61, and the lower end points C00 (140) and C01 (14) of the orient division shown in FIG.
1), C10 (142) and C11 (143) are calculated.
The lower end point of the obtained orient is set to the multiplexer 62.
Select by. In other words, selecting the augent by the input pixel 101 means obtaining the codeword.
The output 144 of the multiplexer 62 is the shift amount control device 5
Controlled by 6, the barrel shifter 63 performs normalization. The bit that has caused an overflow from the C register 64 due to the normalization becomes the output CODE 104 of the code word and is sent to the transmission line.

In the arithmetic code, it is necessary to consider the carry propagation problem associated with normalization, but in the present invention, as a solution of the carry propagation problem, a method by bit stuffing, a counter for counting consecutive '1' bits, is used. There is a buffer method, etc., and which method is to be used is not specified.

The operation of the multilevel arithmetic encoder of the present invention will be described with reference to the flowchart of FIG. Prior to encoding
The A register and the C register are initialized to A = 1.0 and C = 0.0, and the index memory and the dominant symbol string memory are initialized. Since the occurrence probability of the symbol string in the initial state cannot be predicted, in the case of an N-bit symbol string, the probability estimation value p
= 1 / (2 to the Nth power) is set to the initial value of the inferior symbol sequence. At this time, in the initial state, the probability estimation values of the dominant symbol sequence and the inferior symbol sequence are defined to be equal, but the probability estimation value p of the inferior symbol sequence is set to be slightly smaller than 1 / (N to the power of 2). It is also possible to do so. In the embodiment, since N = 2 bits, p = 1/4 is initialized. In addition, the symbol string 0 is stored in the dominant symbol string memory.
0 is set as the initial value of the dominant symbol sequence. If the encoding and decoding are unified, any symbol sequence may be set as the initial value of the dominant symbol sequence. Alternatively, the image to be encoded may be pre-scanned once to obtain the statistical value of the occurrence probability in advance and load it as an initial value.

After the initialization is completed, the reference data is input. In the case of an image, the peripheral pixels of the coded pixel become the reference data. The context is determined by the specified Markov model. The index of the probability estimation table 36 is obtained from the index memory using the context 103 as an address, and the probability estimation table is accessed to read the symbol sequence occurrence probabilities of the probability estimation values Q0, Q1, Q2. Probability estimated values Q0, Q1 and Q2 are input to a multi-symbol arithmetic code arithmetic unit, and addition / subtraction processing is performed to generate an augent A0.
0, A01, A10, A11 are assigned. The symbol string 101 is input, the multi-symbol arithmetic code processing 306 is performed, and the code word CODE is output. After CODE output, a new probability estimated value is determined by the symbol string occurrence probability update process. If the symbol to be coded is judged to have ended by the judgment of 309, the processing is ended, and if not ended, the processing of the reference data input 302 is continued.

FIG. 8 is a flow chart showing the agent allocation processing 304. The orient assignment process is a probability estimation value Q obtained from the probability estimation table 36.
This is a process of inputting 0, Q1, Q2 and the current o-register of the A register 58, and assigning the o-gent by the switch 54 using the dominant symbol sequence as a selector.

FIG. 9 is a flowchart showing the multi-symbol arithmetic code processing 306. The plural-symbol arithmetic coding process is a process of determining an augent by the input pixel MCP from the augent assigned according to the probability of occurrence of a symbol string as shown in FIG. When MCP = 00, assign an augen to A00 and maintain C.
When MCP = 01, the augent is assigned to A01 and A00 is added to C. When MCP = 10, the augent is assigned to A10, and C00 is added with A00 and A01. When MCP = 11, A11 is assigned to the augent, and A00, A01, and A10 are added to C. When the augent A is less than 0.5, the A register and the C register are normalized, and the process ends.

FIG. 10 is a flowchart showing the processing of the probability updating devices 35 and 205. Probability update process is 331
The judgment is made when A <0.5. That is,
The probability estimate is also updated when normalization is needed. The presence / absence of normalization is input from REN signals 117 and 157. 33
2 is a process of determining whether or not the input pixel that has caused normalization matches the dominant symbol string. When they match, the probability update process is performed on the dominant symbol sequence, and the index ST is updated so that the probability estimated values Q of all the inferior symbols become small. On the other hand, when the determination at 332 is Y, the probability update process is performed for the inferior symbol sequence, and the probability estimation value Qmc of the input pixel sequence MCP that causes the normalization is generated.
The index ST is updated so that p becomes large. Three
Reference numeral 34 is a process for determining the magnitudes of the orient Amcp of the encoded inferior symbol sequence MCP and the orient Amssi of the superior symbol sequence. If Amcp is larger than the orient Amssi of the dominant symbol string, the MCP is updated as a new dominant symbol string, and the probability estimate Q of the symbol string MCP is updated as the probability estimate of the previous dominant symbol string. That is, the replacement of the dominant symbol sequence and the substitution of the probability estimation value that was the inferior symbol before the replacement with the replacement, into the probability estimation value that becomes the inferior symbol after the replacement. This process can be realized by exchanging ST of the index memory.

FIG. 11 is a diagram showing the structure of a multilevel arithmetic decoder for collectively decoding a plurality of symbols according to the present invention. The Markov model context 105 includes a plurality of index memories 201, 202, 203 and a dominant symbol string memory 2
The address is 04. The state (index) of the probability estimation table 206 is stored in the index memory. Similar to the encoder shown in FIG. 1, the index memory stores an index indicating a probability estimation value, and
When 5 is input, the probability estimation table is read 206 and the probability estimation value of each symbol string is written in the Q registers 208, 210 and 212. The index of the transition destination of the transition destination table 207 for updating the probability estimated value is also written in the ST registers 209, 211, and 213 in the same manner.

Reference numeral 205 denotes transition destination indexes 154, 155, 156 which are the outputs of the ST register, the dominant symbol sequence 164, the normalization condition REN output from the multi-symbol arithmetic decoding arithmetic unit, the decoded pixel augen Amcp ',
Ogent Amssi of dominant symbol sequence, decoded pixel MC
P'is input, and according to the probability update condition shown in FIG. 10, the dominant symbol sequence MSSo, the states ST0, ST of the index.
This is a probability updating device that outputs 1, ST2.

Reference numeral 214 denotes a multi-symbol arithmetic decoding operation device, which will be described in more detail with reference to FIG. The probability estimation values Q0, Q1, Q2 of the inferior symbol sequence and the orient A are input to the adders 221, 222, 223 to obtain the orient Amssi of the current superior symbol sequence, and the superior symbol sequence MSSi164 is used as a select signal. Two
According to 24, the orients A00, A01,
Define A10 and A11. The allocation of the orient is executed by the orient allocation processing shown in the flowchart of FIG. With respect to the code word C, the output of the C register indicating the current code word and the augents A00 and A0
Subtractors 229, 230, 231
And the subtraction results 181, 182, 183 are input to the data detector 235. 18 in the data detector 235
The positive and negative signs of 1, 182 and 183 are detected, and the decoded pixel M
Determine CP'107. Using the decoded pixel 107 as a selector, the multiplexer 232 obtains the updated value of the C register, and the multiplexer 225 obtains the updated value of the A register. At this time, the shift amount control device 226 examines the normalization condition of the orient A, and when the normalization is necessary, the barrel shifters 227 and 233 are controlled to shift the bits so that the A and C registers have the ogent and the ogent. Stores the position (codeword). Also, the CODE 104 is loaded into the C register according to the shift amount.

The operation of the multilevel arithmetic decoder of the present invention will be described with reference to the flowchart of FIG. Prior to decryption, the A and C registers are A = 1.0 and C = 0.0.
To initialize the index memory and the dominant symbol string memory. Since the initial state of the probability of occurrence of a symbol string needs to be the same for encoding and decoding, the probability estimation value p = 1 / The initial value of the inferior symbol sequence is set to (2 to the Nth power). Further, the symbol string 00 is set in the dominant symbol string memory as an initial value of the dominant symbol string.

After the initialization, the reference data is input and the context is obtained by the prescribed Markov model. In the case of an image, the peripheral pixels of the coded pixel become the reference data. The index of the probability estimation table 206 is obtained from the index memory using the context 105 as an address,
Further, the probability estimation table is accessed to access the probability estimation value Q.
The symbol string occurrence probabilities of 0, Q1 and Q2 are read. Probability estimated values Q0, Q1 and Q2 are input to a multi-symbol arithmetic code arithmetic unit, and addition / subtraction processing is performed to generate an augent A0.
0, A01, A10, A11 are assigned. COD
E104 is input, the multi-symbol arithmetic decoding process 346 is performed, and the decoded pixel 107 is output. After the decoding process for one pixel is completed, a new probability estimated value is determined by the symbol string occurrence probability update process 348. If the symbol to be decoded ends in the determination of 349, the process ends, and if not, the process of the reference data input 342 continues.

FIG. 14 shows a multi-symbol arithmetic decoding process 346.
It is a flowchart showing. The multi-symbol arithmetic decoding process is a process of comparing an assigned gent according to the occurrence probability with an input CODE to determine which CODE the CODE belongs to. When C <A00, MCP ′ = 00, and the augenent is assigned to A00, and C is maintained. A00 ≦ C <A00 + A01
Then, MCP '= 01, and the augent is A01.
And subtract A00 from C. A00 + A01
When ≦ C <A00 + A01 + A10, MCP ′ = 10
Then, assign the augen to A10, and from C to A0
0 and A01 are subtracted. When C ≧ A00 + A01 + A10, MCP ′ = 11, A11 is assigned to the augen, and A00, A01, and A10 are subtracted from C.
When Ogent A is below 0.5, A register and C
Registers are normalized and the process ends.

As described above, it has been shown that arithmetic coding and arithmetic decoding processing that handles a plurality of bits collectively can be realized. In the present invention, the number of bits to be collectively processed is N
However, the processing speed can be expected to improve by increasing the number of bits N of the symbol for expanding the information source. On the other hand, increasing N leads to an increase in hardware scale, so it is preferable that the number of bits N is 2 to 16, and more preferably N is 2 to 8.

The multivalued arithmetic encoder and decoder of the present invention are an image communication device for transmitting multicolor images,
Alternatively, it can be applied as a highly efficient data encoding device for an image storage device that stores multi-color images. As the image storage device, for example, the storage capacity of the RAM or ROM can be apparently increased by providing the data encoding device of the present invention at the input / output interface of the storage medium such as RAM or ROM. Further, by providing the input / output interface of the storage medium such as a CD-ROM with the data encoding device of the present invention, it is possible to reduce the access to the CD-ROM, so that the data transfer can be speeded up.

[0047]

As described above, according to the present invention, the processing speed of encoding and decoding can be increased by collectively processing a plurality of bits. Further, it is possible to expect an improvement in compression rate by predicting while learning the occurrence probability of the symbol string represented by a plurality of bits.

[Brief description of drawings]

FIG. 1 is a diagram showing a configuration example of a multilevel arithmetic encoder to which the present invention has been applied.

FIG. 2 is a diagram for explaining encoding and decoding processing by the multilevel arithmetic encoder and the multilevel arithmetic decoder according to the present embodiment.

FIG. 3 is a block diagram showing a configuration example of a data encoding device of the present invention.

FIG. 4 is a diagram showing a configuration example of a Markov model generator.

FIG. 5 is a block diagram showing the configuration of a conventional data encoding device.

FIG. 6 is a block diagram showing a configuration of a multi-symbol arithmetic code arithmetic unit according to the present embodiment.

FIG. 7 is a flowchart showing the processing content of arithmetic coding.

FIG. 8 is a flowchart showing an augent allocation process.

9 is a flowchart showing the multi-symbol arithmetic coding process of FIG.

FIG. 10 is a flowchart showing the processing contents of the probability updating device.

FIG. 11 is a diagram showing a configuration example of a multilevel arithmetic decoder to which the present invention has been applied.

FIG. 12 is a block diagram showing the configuration of a multi-symbol arithmetic decoding operation device according to the present embodiment.

FIG. 13 is a flowchart showing the processing contents of arithmetic decoding.

14 is a flowchart showing the multi-symbol arithmetic decoding process of FIG.

[Explanation of symbols]

 1, 5 Delay device 2, 4 Context generation circuit 3 Multi-value arithmetic encoder 4 Multi-value arithmetic decoder 13 Binary arithmetic encoder (arithmetic encoder) 31, 32, 33 Index memory 34 Dominant symbol sequence memory 35 Probability updating device 36 Probability estimation table 37 Transition destination table 38, 40, 42 Q register 39, 41, 43 ST register 44 Multi-symbol arithmetic code arithmetic unit 201, 202, 203 Index memory 204 Dominant symbol sequence memory 205 Probability updating unit 214 Multi-symbol arithmetic decoding Arithmetic unit 101 Multi-color input pixel (MCP) 103, 105 Context 104 Code word (CODE) 107 Decoded pixel 111, 112, 113 Probability estimated value Q 114, 115, 116 Transition destination state signal 117 Normalization condition signal (REN) 118 Augen (Amcp) 119 Orgent (Amssi) 120, 124 Dominant symbol sequence 121, 122, 123 Transition destination state signal

─────────────────────────────────────────────────── ─── Continuation of the front page (51) Int.Cl. ⁶ Identification code Internal reference number FI Technical indication H04N 1/41 C 1/411 7/24 11/04 Z 9185-5C

Claims (7)

[Claims] 1. A data encoding apparatus for collectively processing a plurality of bits of data such as an image and the like, and a delay unit for storing the input data, and a Markov model defined from the input data stored in the delay unit, which is to be encoded. A data encoding device comprising a context generation circuit for generating a context (CX) indicating a state before data input, and a multi-value arithmetic encoder for outputting a code word from the input data and the context. 2. A data encoding apparatus for collectively processing a plurality of bits of data such as an image, a delay unit for storing decoded data from a multi-value arithmetic decoder, and a Markov model from the decoded data stored in the delay unit. A context generation circuit for generating a context indicating a state before input of data to be defined and encoded, and a multi-code decoder for inputting a code word and a context generated by the data encoding device according to claim 1 to decode original data. A data encoding device comprising a value arithmetic decoder. 3. A probability estimation table that stores the probability of occurrence of a symbol in a probability estimation table, a transition destination table that stores state transitions for generating a probability estimation value of a symbol according to input data, and input data. In the above-mentioned multi-valued arithmetic coder comprising a probability updating device that outputs the index of the probability estimation table according to the history of the past dominant symbol sequence and the normalization condition of the arithmetic code, the probability of occurrence of N-bit input data is divided into cases, Multiple index memories that store indexes that indicate the occurrence probabilities in each case, predominant symbol string memories that store the symbol strings that have the highest probability estimates in the input data, and N-bit data and symbol string occurrences. 2. The data according to claim 1, comprising a multi-symbol arithmetic code arithmetic unit for inputting a probability and outputting a code word. Encoder. 4. A probability estimation table storing a probability of occurrence of a symbol in a probability estimation table, a transition destination table storing state transitions for generating a probability estimation value of a symbol according to decoded data, and decoded data. In the above-mentioned multi-level arithmetic decoder which is a probability updating device that outputs the index of the probability estimation table according to the history of the past dominant symbol sequence and the normalization condition of the arithmetic code, the probability of occurrence of N-bit input data is divided into cases, The index memory that stores the index that indicates the probability of occurrence in each case, the dominant symbol string memory that stores the symbol string with the highest probability estimate in the input data, and the occurrence probability of the codeword and symbol string 3. A multi-symbol arithmetic decoding arithmetic unit for inputting and decoding original data.
The described data encoding device. 5. A probability estimation value of occurrence of (2 N-1) inferior symbol sequences of N-bit data, a dominant symbol sequence having the highest probability of occurrence, and data to be encoded and generated. 2. The data encoding device according to claim 1, further comprising the multi-symbol arithmetic code arithmetic device for arithmetically operating a position of a number line according to probability and outputting a code word. 6. The data encoding according to claim 1, wherein a probability estimation value of occurrence of (2 N-1) inferior symbol strings of N-bit data, a dominant symbol string having the highest probability of occurrence, and 3. The data encoding device according to claim 2, further comprising the multi-symbol arithmetic decoding operation device which inputs the code word generated by the device, operates the position of the number line according to the occurrence probability, and decodes the data. 7. The multilevel arithmetic encoder and the multilevel arithmetic decoder, when the length of a number line assigned to a symbol according to the occurrence probability of an input symbol is less than 1/2 and a normalization process is performed. In addition, a probability updating device configured by means for updating probability estimation values of all inferior symbols during normalization by the dominant symbol sequence and means for updating probability estimation values for inferior symbol sequences generated during normalization by the inferior symbol sequence. 3. The data encoding device according to claim 1, further comprising: