JPH06311045A - Encoder and decoder - Google Patents

Abstract

PURPOSE:To provide an encoder/decoder whose processing speed is improved when prediction encoding or its decoding is applied to an information source symbol. CONSTITUTION:The encoder/decoder is provided with barrel shifters 5i, 5k shifting a new valid area width and a border of an area by a predetermined bit number in response to an LPS or an MPS. A selector 5c selects the new valid area width and provides an output of the result to the 1st barrel shifter 5i. On the other hand, a selector 5j selects a border of the new area and provides an output of it to the 2nd barrel shifter 5k. A bit location detector 5h monitors the new valid area outputted from the selector 5c to detect a bit number for normalizing processing. The 1st barrel shifter 5i, the 2nd barrel shifter 5k and a code register 5f execute shift processing and code processing by one clock based on the bit number obtained by the bit location detector 5h.

Description

Detailed Description of the Invention

[0001]

The present invention relates to an encoding / decoding device,
In particular, it relates to a coding / decoding device for image information and the like.

[0002]

2. Description of the Related Art In coding a Markov information source, a target symbol to be coded is predicted from a reference symbol which has already been coded for an output symbol sequence of the information source, and the prediction error signal is used as a reference symbol pattern. Thus, each prediction error signal is classified into several groups according to the predictive predictive value, and coding is performed using a code suitable for each. Here, the creation of this prediction error signal
Predictive conversion, classification into groups is called integration, and group identifiers are called orders. Further, the prediction error signal to be encoded will be called a prediction error symbol.

As this predictive conversion and order selection method,
A technique for performing adaptive processing is disclosed in Japanese Patent Application Laid-Open No. 2-305225 in order to cope with local changes in the statistical properties of information sources. Regarding the coding method of the prediction error symbol, the subtraction type arithmetic coding method is described in IBM Research and Development Information 198.
November 32, Vol. 32, No. 6 (IBM Journal
of Research and Developmen
t, Vol. 32, No. 6, Nov, 1988), "Appearance of the basic principle of a Q-coder compatible binary arithmetic encoder".
(An overview of the basic
princple of the Q-Coder
adaptive-binary arith-me
tic coder) and Japanese Patent Publication No. 2-58811. These are a kind of number line display coding method that maps a symbol sequence between 0.0 and 1.0 on the number line and encodes the coordinates as a code word. Is divided and added and subtracted only.

The process of the conventional predictive conversion, integration and encoding will be described with reference to the drawings. FIG. 14 is a block diagram of an encoding device according to a conventional technique, and FIG. 15 is an internal configuration diagram of an arithmetic encoder therein. For simplicity, the information source is a binary image signal and the reference symbol is 12 in FIG.
The number of pixels and integration is 16.

In FIG. 14, reference numeral 1 is a reference symbol generator which selectively outputs a reference symbol from a sequence of information source symbols 101, and 2 is a reference symbol pattern 102 which is an output thereof, and outputs the order 103 and predicted value 104 of the target symbol. The order / predicted value memory 3, 3 is a predictive converter that creates a prediction error symbol 105 based on the predicted value 112 selected and stored in the order / predicted value register 8 described later, and 4 is the order
An area width table for outputting the area width 106 of the arithmetic code based on the degree 111 selected and stored in the prediction value register 8,
Reference numeral 5 is an arithmetic encoder, 6 is an order / prediction value control circuit that controls reading and updating of the order / prediction value memory, and 7 is a reference symbol pattern for the immediately preceding encoding target symbol from the reference symbol pattern 102 and an encoding target symbol. A detector 8 for detecting whether or not the reference symbol patterns match each other. Reference numeral 8 denotes the order 103 and the predicted value output 104 from the order / predicted value memory 2 or the order / predicted value control circuit 6
Is an order / prediction value register for temporarily storing the update signal 108 from. Here, since the number of reference symbols is set to 12, 2 ¹² kinds of order / predicted value tables (contents of the order / predicted value memory) are required as shown in FIG. Regarding the order value, the integration is made into 16 groups, and therefore this is identified. Here, the higher the predictive predictive ratio, the higher the order.

FIG. 15 is a block diagram showing the internal structure of the arithmetic encoder 5. In the figure, 5a is an A register for storing the effective area Ai on the number line, 5b is a subtracter for calculating the MPS area width 114, and 5c is the LPS area width and M.
A selector 5d for selecting the PS region width and inputting it to the A register 5a is a C register for storing the lower bound coordinates 116,
Reference numeral 5e is an adder for calculating the C register value 117 in the case of LPS, and 5f is a temporary storage of the carry output 118 which is an overflow (shift out) signal of the C register, and carries out carry processing when updating the C register 5d. A code register 5g for creating such a code sequence is a timing control circuit for controlling the operation of the arithmetic encoder 5.

Next, the operation will be described with reference to FIG.
The symbol 101 (image signal) generated from the information source is stored in the reference symbol generator 1 and its sequence is stored.
The signal of 12 pixels shown in 6 is selected and output as the reference symbol pattern 102. Based on this, the order / predicted value memory 2 outputs the predicted value 104 and the order 103 of the target symbol from the table contents shown in FIG.
3 information is the area width 106 in the area width table 4 shown in FIG.
Is converted and output as. On the other hand, the generated symbol 101 is subjected to exclusive OR with the prediction value 112 in the prediction converter 3 to create the prediction error symbol 105. Since this prediction error symbol is a binary image signal to be encoded, it is 0 (MPS: More Probable Sy) in the case of prediction matching.
mbol), 1 in case of disagreement (LPS: Less P
It is a robbable symbol).

In the arithmetic encoder 5, the prediction error symbol 105 is mapped on a number line based on the region width 106 signal, and coding is executed. That is, the i-th symbol in the prediction error symbol sequence is a _i , and the LP at the i-th time point is
If the mapping range (allocation area) of S is S, and the MPS area is located below the effective area, the mapping range (effective area) Ai of the symbol sequence at the i-th time point and its lower bound coordinate Ci.
When the symbol _ai is MPS, Ai = Ai-1−SCi = Ci-1 When the symbol _ai is LPS, Ai = SCi = Ci-1 + (Ai-1−S).

When the effective area Ai becomes 1/2 or less, it is multiplied by a power of 2 in order to improve the calculation accuracy. At this time, the overflow of coordinate Ci (the part above the decimal point)
Minutes are output as a code bit sequence. Hereinafter, this exponentiation process is called normalization. Ai update value = Ai * 2 ^m (1/2 <
Ai update value ≤ 1) Ci update value = Ci * 2 ^m

In the arithmetic code, it is known that high efficiency coding extremely close to the information source entropy can be performed by setting S to the appearance probability (= prediction error probability) of LPS. Therefore, arithmetic coding can be performed by the above processing by selecting an S value suitable for the predictive predictive value corresponding to the order. FIG. 18 is an example of a correspondence table between the degree and the area width S. The values in the table are the values in the above formula multiplied by 2 ¹⁶ . In this example, the area calculation on the number line is performed with 16-bit precision, and each of the A register and the C register has a decimal number of 16 bits or less.

Next, the adaptive processing of prediction and integration will be described. The adaptive processing method includes a method of counting and controlling the number of consecutive MPSs and LPSs from the output symbol sequence, and a symbol when the normalization occurs is MPS or L.
There is a method of controlling by PS. Here, the latter method will be described as an example. The order / predicted value control circuit 6 determines whether the output symbol of the predictive converter 3 is MPS or LPS during normalization.

In the case of LPS, the order / predicted value memory 2 subtracts 1 from the order value corresponding to the reference symbol pattern at that time. For example, when the degree of the target symbol X to be encoded with respect to the reference symbol patterns A to L is 4 and the predicted value is 1 as shown in FIG. 17A, the degree is 3 as shown in FIG. 17B. To This is because the prediction in the reference symbol state is wrong, so by lowering the order showing the accuracy of the prediction, the information source that is the current encoding target,
This is an operation of adapting the order / predicted value. When the order reaches the lowest order and the order cannot be reduced any more, the predicted value is inverted. By this operation, the predicted value with extremely bad hit rate is rewritten.

In the case of MPS In the order / predicted value memory 2, the order value corresponding to the reference symbol pattern at that time is incremented by one. For example, when the degree of the encoding target symbol X with respect to the reference symbol patterns A to L is 4 as shown in FIG. 17A, the degree is set to 5 as shown in FIG. 17C. This is because the prediction in the reference symbol state is correct, so by increasing the order indicating the accuracy of the prediction, the order / predicted value is adapted to the information source currently being encoded. It is an action. If the degree has already reached the highest degree, no addition is performed. When the prediction is extremely accurate by this operation, the S value is reduced by increasing the order, and the code amount output from the arithmetic encoder 5 can be suppressed.

By the above-described operation of the adaptive processing, the order / predicted value control circuit 6 rewrites the order / predicted value table in accordance with the property of the information source, and arithmetic coding with high coding efficiency can be realized.

Here, the processing operation for each symbol of this encoding apparatus will be described in detail with reference to FIG. In FIG. 19, C
1, C2, C3, ... Show one cycle of the system clock. Further, in the figure, # 1, # 2, # 3, ... Show target symbols to be encoded. However, in FIG.
# 1, # 2, and # 3 in the above do not mean the target symbol itself, but indicate that various patterns and outputs described on the left side of the drawing correspond to the target symbol. For example, in the target symbol pattern 102 #
.., # 2, # 3, ... indicate the output of the reference symbol pattern corresponding to the target symbol # 1, and similarly # 2 indicates the output of the reference symbol pattern corresponding to the target symbol # 2. ing.

As shown in FIG. 19, the system clock C
1, the information source symbol 101 is input, and the reference symbol generator 102 outputs the reference symbol pattern 102. At the same time, at the system clock C1, the order / predicted value memory 2 outputs the order 103 and the predicted value 104. Further, at the system clock C2, the order signal 1 of the target symbol to be coded is output from the order / predicted value register 8.
11 and the prediction value signal 112 are output, and the order / prediction value memory 2 outputs the order 1 for the next symbol to be encoded.
03 and the predicted value 104 are read using one cycle of the system clock. Further, at the system clock C3,
The arithmetic encoder 5 outputs for the symbol encoding and outputs the code from the A register and the C register in parallel with the degree signal 111 and the prediction value signal of the next encoding target symbol. 112 is the order / prediction value register 8
From the order / prediction value memory 2, the order 103 and the prediction value 104 for the next symbol to be encoded are read out. In this way, the encoding device is configured to perform processing in a pipeline manner.

Next, there will be described cases where normalization and order / prediction value updating is not performed when the target symbol is coded, and cases where it is present. (1) When normalization and order / prediction values are not updated For example, as in the case of # 1, # 3, # 4, and # 6 in FIG. Move to the area and coordinate calculation of. (2) Normalization and update of order / prediction value For example, as in the case of # 2 and # 5 in FIG. 19, after the calculation of the area and coordinates is performed in one clock, the following update / normalization is performed. To convert.

The contents of the order / predicted value memory 2 are updated from the reference pattern 109 (the reference symbol pattern 102 delayed by one symbol) for the symbol output from the detector 7 and the order / predicted value control circuit 6. Based on the update signal 108. At this time, if the reference symbol pattern 102 (signal for the next encoding target symbol) and the reference pattern 109 for the encoding target symbol match, the contents of the order / prediction value register are also updated. These content updates are processed in one cycle of the system clock.

The normalization is performed in parallel with this updating operation by left shifting at one system clock cycle per bit. A specific example of the case where the normalization and the order / predicted value are updated will be described. At the system clock C3, the area / coordinate calculation is performed on the encoding target symbol # 2. When the effective area becomes 1/2 or less as a result of the calculation, normalization processing is performed. Similarly, the adaptive processing described above is performed. That is, in order to perform the normalization processing, the A register and the C register are shifted by 1 bit at the system clock C4, and the code is output. In addition, regarding the adaptive processing, as shown in FIGS. 17B and 17C, the order corresponding to the reference symbol pattern referred to by the encoding target symbol # 2 is changed. Alternatively, the predicted value is changed. The updated order and prediction value referenced by the encoding target symbol # 2 in the order / prediction value memory 2 is shown as # 2 ′ in FIG.

After the completion of both these operations, the process proceeds to the area / coordinate calculation of the next symbol to be coded. At the system clock C5, the next encoding target symbol is calculated, but the next encoding target symbol # 3 is calculated.
The order and prediction value used for
When the reference symbol patterns of 2 and the encoding target symbol # 3 do not match, the order and prediction value obtained from the reference symbol pattern of the encoding target symbol # 3 are used. On the other hand, when the reference symbol patterns of the encoding target symbol # 2 and the encoding target symbol # 3 match, the order and the prediction value (the order
Predicted value memory output # 2 ') is used.

Further, in the case of the symbol # 5 to be coded, as a result of the operation of the system clock C7, 2-bit shift is performed for the normalization process. Therefore, in the system clocks C8 and C9, the 2-bit shift is normalized. Processing is performed. Also, regarding the order and the prediction value of the encoding target symbol # 6 to be encoded next, if the reference symbol patterns of the encoding target symbol # 5 and the encoding target symbol # 6 do not match, the system clock C7 remains unchanged. The order and the prediction value obtained in step S10 are used in the system clock C10. However, when the reference symbol patterns of the encoding target symbol # 5 and the encoding target symbol # 6 match, the encoding target symbol # 5 By adaptive processing,
Since the content of the predicted value memory 2 is being updated, the updated order and predicted value (indicated by # 5 'of the order / predicted value memory output in the figure) are used in the system clock C10. The normalization process is performed as described above, and one cycle of the additional system clock is used every time a 1-bit code is output. The number of this additional system clock is equal to the number of sign bits.

As is clear from the above description, the coding processing time T of this coding apparatus is such that when the total number of symbols is Na and the number of code bits is Nc, the system clock is 10 MH.
In the case of Z, T = 100 + 100 * Na + 100 * Nc (nse
c). The first item 100 in the above equation represents the time of the system clock C1 in FIG. Also, the second item 1
Since 00 × Na takes 100 nsec per symbol, it indicates the time for processing all symbols. Also, the third
The item 100 × Nc indicates the additional time required for the normalization process in FIG. 19, that is, the process of outputting the sign bit. For example, in FIG. 19, since the shift processing of the system clocks C4, C8, and C9 is performed three times, three code bits are output, and in this example, 100 × 3.
= 300 nsec. Therefore, assuming that the compression rate is 30 for an A4 size original document with a standard resolution of 8 pixels / mm horizontal and 7.7 lines / mm vertical, Na = 1728 * 2376 Nc = 1728 * 2376 * (1/30), The encoding processing time T is about 0.4 seconds.

[0023]

As described above, in the conventional apparatus, the reference symbol pattern is created for all symbols, the order / predicted value table is searched, and the number line area is calculated. Therefore, the order / prediction value table is updated and normalized, which causes a problem that the encoding / decoding process is delayed due to the nature of the image signal. In particular, for an organized dither image or a pseudo-halftone image binarized by the error diffusion method, an A4 size document has 8 horizontal pixels /
In the case of encoding at a resolution of mm, vertical 7.7 lines / mm, the processing time is about 0.7 to 1 second, which is about twice as long as the processing time of a normal character image.

The present invention has been made to solve the above problems, and an object of the present invention is to obtain an encoding / decoding device capable of significantly increasing the processing speed.

[0025]

An encoding apparatus according to the first aspect of the present invention estimates a symbol appearance probability from an output symbol sequence of an information source, performs effective area division according to the estimated probability of occurrence, and obtains this symbol sequence. A first register for storing the effective area on the number line, a first calculating means for calculating the area width of the MPS, and a second value for storing the boundary value of the effective area on the number line during arithmetic coding. Register, a second calculating means for calculating a boundary value between the area corresponding to the LPS and the area of the MPS, and a first selecting means for selecting a new effective area width depending on whether the generated symbol is MPS or LPS. Second selection means for selecting a new boundary value of the effective area, bit position detection means for receiving the output of the first selection means and detecting the position of the highest "1" or "0", and this detection means. 1st according to output A first barrel shifter that shifts the output of the selecting means to output the first register input value, and also outputs the second register input value and the overflowed data from the second register by receiving the output of the second selecting means. The second barrel shifter is configured to include a second barrel shifter and a code generation unit that receives the overflowed data output from the second register from the second barrel shifter and generates a code output.

The encoding apparatus according to the second invention is F
It is provided with a code generation means having an IFO memory.

The decoding apparatus according to the third aspect of the present invention estimates a symbol appearance probability from an output symbol sequence of an information source, performs effective area division according to the estimated probability, and arithmetically codes this symbol sequence to obtain code bits. A first register for storing the effective area on the number line when decoding the sequence;
First calculation means for calculating a region width of a symbol (dominant symbol: MPS) that is assumed to occur frequently, a second register for storing a boundary value of an effective region on a number line, and a second register Areas of symbols (recessive symbols: LPS) and MPSs that are assumed to have a low frequency of occurrence from the output
The boundary value with the area is subtracted and the symbol is MPS or LP.
The second calculation means for determining whether S and the symbol are MP
First selection of new effective area width depending on S or LPS
Selection means, second selection means for selecting a new boundary value of the effective area, and bit position detection for receiving the output of the first selection means and detecting the position of the highest "1" or "0". Means, a first barrel shifter for shifting the output of the first selecting means according to the output of the detecting means and outputting the shifted value as a first register input value, a second selecting means output, and a code reading means output described later. A second barrel shifter that receives and outputs a second register input value and an input code data sequence are received, and a code sequence having a required number of bits is output to the second barrel shifter as a lower bit signal of the second register. It is provided with a code reading means.

The decoding device according to the fourth invention is F
It is provided with a code reading means having an IFO memory.

The coding apparatus according to the fifth aspect of the present invention predicts the symbol to be coded from the states of a plurality of reference symbols at predetermined positions of the output symbol sequence of the information source, and outputs the prediction error signal. A two-port memory capable of simultaneous reading and writing, which stores the predicted value of the target symbol to be encoded in each state of the reference symbols and the order which is the identifier of the group classified by the predictive matching rate when encoding, An order / prediction value control circuit for checking whether or not the encoding target symbols are predictively matched and rewriting the prediction value and the order in the reference symbol state according to the result,
Prediction value and order signal of the encoding target symbol read from the memory, or an order / prediction value register that stores the prediction value and order after the rewriting process for the immediately preceding encoding target symbol, and the encoding target A detector that detects whether or not the reference symbol state for the symbol matches the reference symbol state for the immediately preceding symbol, and the predicted value output from the order / predicted value register.
An arithmetic encoder for encoding a prediction error signal based on order information is provided.

The decoding device according to the fifth aspect of the present invention predicts the symbol to be decoded from the states of a plurality of reference symbols at predetermined positions of the output symbol sequence of the information source and outputs the prediction error signal. When decoding the coded code bit sequence, simultaneous write readable that stores the predicted value of the decoding target symbol from the state of the reference symbol and the order that is the identifier of the group classified by the predicted matching rate The port memory, an order / prediction value control circuit for checking whether or not the above decoding target symbol matches prediction and rewriting the predicted value and the order in the reference symbol state according to the result, and the preceding decoding target symbol A selector for selectively outputting a set of predicted values and orders of memory outputs for a plurality of states according to the reproduced signal value of And the order, or a register that stores the updated predicted value and order for the immediately preceding decoding target symbol, and whether the reference symbol state for the decoding target symbol and the reference symbol state for the immediately preceding symbol match or not. It is provided with a detector for detecting and an arithmetic decoder for decoding the code bit sequence based on the selected prediction value / order information.

[0031]

The encoding apparatus according to the first aspect of the present invention improves the encoding speed by accelerating the normalization operation using the first and second barrel shifters.

In the encoding device according to the second aspect of the present invention, the encoding speed is reduced by using the FIFO as the code generation means to buffer the code output to reduce the interruption of the encoding operation related to the code output. To improve.

The decoding apparatus according to the third aspect of the invention improves the decoding speed by speeding up the normalization operation using the first and second barrel shifters.

In the decoding device according to the fourth aspect of the present invention, the decoding speed is improved by using the FIFO as the code reading means to buffer the code input and reduce the interruption of the decoding operation related to the code input. To improve.

In the encoding device according to the fifth aspect of the present invention, the memory for storing the order / predicted value has a two-port structure, and the read / write operation is simultaneously performed to improve the encoding speed.

In the decoding device according to the sixth aspect of the present invention, the memory for storing the order / predicted value has a two-port structure, and the read / write operation is simultaneously performed to improve the decoding speed.

[0037]

EXAMPLES Example 1. Hereinafter, the present invention will be described based on illustrated embodiments. The encoding device block configuration of the present embodiment is
14 is the same as the conventional device shown in FIG.
The order / predicted value memory 2 has a high speed, the writing operation is possible in the first half cycle of the system clock, and the reading operation is possible in the second half cycle, and the internal configuration of the arithmetic encoder 5 is different. That is the point.

FIG. 1 is a block diagram showing the internal structure of the arithmetic encoder 5 of this embodiment. The difference from the arithmetic encoder of the conventional encoder of FIG. 15 is that the LPS area width and MPS are different.
A bit position detector 5h that receives the output of the area width selector 5c and detects the position of the highest 1 and a selector 5c corresponding to the number of bits corresponding to the normalized bit number signal 120 that is the output.
The left side of the output of the first register shifter 5i which inputs 121 to the A register 5a, and the output 116 of the C register 5d.
And the selector 5j for switching the C register value 117 in the case of LPS, and the output 122 of the selector 5j is left-shifted by the number of bits corresponding to the normalized bit number signal 120 to output the overflow amount 124 to the code register 5f. The addition of the second barrel shifter 5k for inputting the lower bit 123 to the C register 5d, and the sign register 5
Instead of the conventional 1-bit carry output as the input of f,
Overflow signal 12 from the second barrel shifter 5k
4 and the normalized bit number signal 120 from the bit position detector 5h.

FIG. 2 is a diagram showing the internal structure of the code register 5f. 5f1 is a barrel shifter for shifting the overflow signal by a predetermined number of bits, and 5f2 receives the normalized bit number signal 120 and shift-adds the overflow signal. Digit control circuit for controlling the number of bits 126, 5f3 is an adder for adding / adding an overflow signal to the lower order of the preceding bit sequence, 5f4 is a byte pack register for packing the overflow signal sequence into bytes, 5f5
Is carry 130 from the byte pack register 5f4
The overflow detector 5f6 for detecting "0x" in hexadecimal from the output 129 of the byte pack register 5f4.
ff pattern detector / counter for detecting / counting ff ”, 5
f7 is an output 129 from the byte pack register 5f4
Is temporarily stored and the overflow detector 5f5
Buffer register that adds 1 to the stored data when there is an overflow from the ff data generator that outputs "0xff" in hexadecimal, 5f9
Also outputs "0x00", 00 data generator, 5
f10 is a buffer register 5f7 and an ff data generator 5
This is a selector for selecting the data from the f8,00 data generator 5f9 and creating a code data sequence.

Next, the operation of this embodiment will be described with reference to FIG. 3 is different from the conventional one in that since the order / prediction value memory 2 is high-speed, reading from the order / prediction value memory is possible in the latter half of the system clock. For example, when the encoding target symbol # 1 is read from the order / prediction value memory 2, the latter half of the system clock C1 is used. Similarly, when reading the encoding target symbol # 2, the latter half of the system clock C2 is used for reading. If, as a result of the calculation, normalization processing and order / prediction value change processing occur, the order / prediction value memory can be updated using the first half of the system clock. For example, if the normalization process of 1-bit shift occurs as a result of the arithmetic processing of the encoding target symbol # 2 at the system clock C3 and the order / prediction value is updated, the first half of the system clock C4 is changed. It is possible to update the order / predicted value memory 2 using the update processing. Similarly, in the system clock C6, when normalization processing of 2-bit shift and update processing of order / predicted value occur as a result of the arithmetic processing of the encoding target symbol # 5, the system clock C7
It is possible to update the order / predicted value memory 2 in the first half of the above. Now, assuming that the order signal 111 and the predicted value signal 112 of the target symbol to be coded are output from the order / predicted value register 8, the order In the predicted value memory 2, the order and predicted value for the next symbol to be encoded are read using the latter half cycle of the system clock. (1) When normalization and order / prediction values are not updated For example, as in the case of # 1, # 3, # 4, and # 6 in FIG.
After the calculation of the above area and coordinates, the operation moves to the area / coordinate calculation of the next encoding target symbol. (2) Normalization and update of order / prediction value For example, as in the case of # 2 and # 5 of FIG. 3, after the processing up to the calculation of the area and coordinates and normalization is performed in one clock, The processing of the symbol moves.

Since the barrel shifter can perform the shift processing of a plurality of bits in one clock, even in the case of the normalization processing of performing the shift processing of a plurality of bits, the normalization processing can be completed in one clock. The operation of this normalization processing will be described later. The contents of the order / predicted value memory 2 are updated by the order / predicted value control circuit 6 and the detector 7 in the cycle of the first half of the system clock of the cycle in which the area of the next symbol and the coordinates are calculated.

Next, a specific operation will be described with reference to FIG. In the system clock C3, when it is determined that the normalization process and the order / prediction value update process (adaptive process) are performed as a result of the calculation process of the encoding target symbol # 2, the first half of the system clock C4. Is used to update the order / predicted value memory. In order to determine the order and the predicted value of the encoding target symbol # 3 in the system clock C4, it may be possible that the reference symbol patterns of the encoding target symbol # 2 and the encoding target symbol # 3 match or not. When the reference symbol patterns of the encoding target symbol # 2 and the encoding target symbol # 3 do not match, the order of the encoding target symbol # 3 read from the order / prediction value memory 2 at the time of the system clock C3 and The predicted value is output as the order and predicted value of the encoding target symbol # 3 at the system clock C4. On the other hand, when the reference symbol patterns of the encoding target symbol # 2 and the encoding target symbol # 3 match, the normalization process and the order / prediction value update process occur after the arithmetic process of the encoding target symbol # 2. Therefore, the updated order and predicted value must be used. The update process of the order and the predicted value is performed in the first half of the system clock C4. Therefore, as the order and predicted value from the order / predicted value register 8, the order and predicted value updated in the first half of the system clock C4 are used as the order and predicted value of the encoding target symbol. Encoding the order / prediction value register 8 in the first half of the system clock C4 by updating the order / prediction value register 8 in parallel with the update to the order / prediction value memory 2 in the first half of the system clock C4. The order and the predicted value of the target symbol # 2 can be updated at the same time. System clock C4
In the above, by using the updated order and prediction value of the order / prediction value register 8 as the order and prediction value of the encoding target symbol # 3, the newly updated order and prediction value can be correctly used.

In the encoding target symbol # 5,
Even when the 2-bit normalization process and the order / predicted value change process occur, the normalization process and the order / predicted value update process similar to those of the encoding target symbol # 2 described above are performed. Further, when determining the order and prediction value for the encoding target symbol # 6, the encoding target symbol # 6 is determined as described above.
When the reference symbol patterns of 2 and # 3 match or do not match, the updated new order and prediction value are used when they match, and when they do not match, the order read for the encoding target symbol # 6. And the predicted value is used as is.

As described above, in this embodiment, since the order / prediction value memory 2 is faster than the conventional one, writing and reading can be performed using the first half and the second half of the system clock. What can be done is a big feature. Further, it is a great feature that even if there is a process of a plurality of bits by using a barrel shifter in the shift process at the time of normalization, it can be performed in one clock. As described above, in the conventional apparatus, the system clock is required to perform the shift processing, whereas in this embodiment, even if the number of shift bits is plural, it is possible to finish in one clock and normalize. There is no need to delay other pipelined processing for processing. Further, since the normalization process and the update process of the order / predicted value are performed in a later stage of the arithmetic encoder of the device configured in a pipeline, it is determined whether the order and the predicted value are updated, and the update is performed. The order / predicted value memory 2 can be accessed at high speed in order to reflect the new order and predicted value on the encoding target symbol to be encoded next.

Next, the operation of the arithmetic encoder 5 will be described with reference to FIG. The arithmetic encoder 5 inputs the area width 106 and the prediction error symbol 105 and outputs a code 107. The prediction error symbol 105 is one of LPS (1) / MPS (0), and in the case of LPS, the selector 5c selects S1 and SS.
Connect 3. And the selector 5j selects S6 and S4. On the other hand, when the prediction error symbol 105 is MPS, the selector 5c connects S2 and S3. The selector 5j connects S5 and S6. When the selector 5c connects S1 and S3, the area width 106 is input and output to the first barrel shifter 5i. On the other hand, when S2 and S3 are connected, the remaining MPS area width 114 obtained by subtracting the area width 106 from the area width in the A register 5a is used as the first barrel shifter 5
Output to i.

The bit position detector 5h monitors the output 115 from the selector and detects the most significant bit position of the output 115. For example, when the bit "1" is detected in the second digit, 1 is output as the normalized bit number signal. When bit 1 is detected in the third digit, 2 is output as the normalized bit number signal. When the normalized bit number signal represents 1, it indicates that the shift number is 1, and when the normalized bit number signal is 2, it indicates that the shift number is 2. The normalized bit number signal 120 is input to the first barrel shifter 5i and the second barrel shifter 5k, and shifts the signals output from the selectors 5c and 5j. In this way, the normalization process is completed in one clock. When S4 and S6 are connected in the selector 5j, the MPS area width 114 is added to the value in the C register 5d to calculate a new LPSC register value, and this is added to the second value.
Output to the barrel shifter 5k. On the other hand, the selector 5j is S5.
When S6 and S6 are connected, the C register output 116 output from the C register 5d is selected and output to the second barrel shifter 5k.

Next, the operation of the code register 5f will be described with reference to FIG. The code register 5f inputs the overflow signal 124 from the second barrel shifter 5k and outputs a code 107. When outputting the code 107 from the overflow signal 124, the normalization bit signal 120 is input and the coding stop signal 125 is output to adjust the coding timing. As previously mentioned,
When 2 bits of the overflow signal 124 are input, the normalized bit number signal 120 inputs 2 as the number of bits to be shifted. The digit control circuit 5f2 shifts the barrel shifter 5f1 based on the value of the normalized bit number signal 120 and takes in the overflow signal 124. If the barrel shifter 5f1 cannot shift by the number of bits based on the normalized bit number signal 120, the digit control circuit 5f2 outputs the encoding stop signal 125. The encoding stop signal 125 is input to the timing control circuit 5g shown in FIG. The timing control circuit 5g uses the encoding stop signal 1
When 25 is input, the encoding operation of the arithmetic encoder 5 is temporarily stopped. The digit control circuit that has output the encoding stop signal 125 performs the remaining shift operation of the barrel shifter 5f1 while the arithmetic encoder 5 is stopping the next operation, so that the next overflow signal 124 in the code register 5f is changed.
The operation of the code register 5f is continued until it becomes possible to input.

The operation of the code register 5f during normalization is as follows. (A) Overflow signal 124 from C register 5d
Is added to the position immediately below the immediately preceding overflow signal that has already been processed. However, when the overflow signal is larger than the normalized bit number (only 1 bit at maximum), the most significant bit is added to the least significant bit of the immediately preceding overflow signal. (B) When the overflow signal cannot be added to the byte pack register at once, output from the byte pack register in (c) below and perform the same addition operation until the least significant bits are stored in the byte pack register. repeat. (C) When data is stored up to the byte boundary in the byte pack register 5f4, the ff pattern detection / counter 5f
The following processing is performed according to 6. (C-1) When the data of the byte pack register 5f4 exceeds "0xff" (detected by the overflow detector), 1 is added to the already stored contents of the buffer register 5f7, and it is passed through the selector 5f10. To output the code, then "0
"0x00" is code-outputted by the 00 data generator 5f9 by the number corresponding to the count value of "xff." After that, the lower 8 bits of the byte pack register 5f4 are read and output to the buffer register 5f7. (c-2) Byte pack When the data in the data register 5f4 is “0xff”, the count value of “0xff” is incremented by 1. (c-3) When the data in the byte pack register 5f4 is less than “0xff” The contents of the already stored buffer register 5f7 Is output as a code through the selector 5f10, and then “0xff” is output as a code by the ff data generator 5f8 by the number of the count value of “0xff.” After that, the byte pack register 5f4 is read and is stored in the buffer register 5f7. By these processes, so-called pure output
The code generation process is performed.

As is clear from the above description, the coding processing time T of this coding apparatus is such that when the total number of symbols is Na and the number of code bits is Nc, the system clock is 10 MH.
In the case of Z, T = 100 + 100 * Na + α (nse
c). Here, α represents the overflow signal 124 of a plurality of bits sent from the C register 5d,
At time f, the next overflow signal is generated while the data is packed into 8 bits and output, and therefore the time for waiting for the calculation of the area of the next coded symbol is reached. This occurs when the overflow signal 124 exceeds 8 bits. Therefore, as an A4 size document with a standard resolution of horizontal 8 pixels / mm and vertical 7.7 lines / mm, the compression rate is 30.
Assuming that, the encoding processing time T is about 0.4 seconds, and it is about 0.4 seconds even when the compression rate is 1.5 for an extremely complicated image such as an error diffusion image. Here, α is set to α = 100 * Nc * (1/16).

On the other hand, in the conventional apparatus shown in FIG. 14, it takes about 0.7 seconds when the compression rate is 1.5.

Example 2. Next, FIG. 4 shows a block configuration of an arithmetic encoder of an encoder which is another embodiment of the present invention. The difference between this embodiment and the embodiment of FIG. 1 is that a FIFO for storing the overflow signal 124 and the normalized bit number signal 120 is added to the first stage of the code register 5f.

According to the arithmetic coding, the coding is performed in accordance with the property of the information source, so that the compression rate exceeds 1 except for the transitional part, and the processing of the code register 5f is ( Since it can process 8 bits in 1 clock, there is no need to stop the area calculation by the FIFO of about 16 stages (that is, α = 0) and the ultra-high speed and constant speed required for digital copiers etc. An encoder can be realized.

Example 3. Next, FIG. 5 shows a block configuration of an encoding apparatus which is another embodiment of the present invention. In the figure, the difference from the block diagram in the above embodiment is that the order
The predicted value memory 2 has a two-port configuration, and the reference symbol pattern 102 and the update reference symbol pattern signal 109 are monitored in place of the detector 7, and the update signal 1
When both patterns match when 08 occurs, the 2-port control unit 9 and the access prohibition circuit 10 for stopping the access of the order / predicted value memory for the next symbol are added.

FIG. 6 shows an example of the encoding operation in this embodiment.
Here, the arithmetic encoder used is that shown in FIG. The same processing as described above can be performed by the 2-port memory at half the access speed.

Next, this specific example will be described with reference to FIG. At the system clock C3, the normalization process and the order / prediction value update process (adaptive process) are performed as a result of the calculation process of the encoding target symbol # 2. System clock C
In 4, the order and the prediction value used for the encoding target symbol # 2 for updating the order and the prediction value are to be updated.
The write operation to the order / predicted value memory 2 is performed in parallel with the reading for the encoding target symbol # 4 of the order / predicted value memory at the system clock C4.
However, if the reference symbol patterns of the encoding target symbol # 2 and the encoding target symbol # 4 are the same, the order
Since writing and reading conflict with the prediction value memory 2, there is a need to prohibit access to either the order / prediction value memory 2 even if it is a two-port memory. When the reference symbol patterns of the encoding target symbol # 2 and the encoding target symbol # 4 are the same, the 2-port control unit 9 instructs the access prohibition circuit 10 to prohibit access. The access prohibition circuit 10 prohibits the reading of the order / predicted value memory for the encoding target symbol # 4. Even if the reading of the order / predicted value memory for the coding target symbol # 4 is prohibited, the order / predicted value memory 2 and the order are calculated because the order and predicted value are updated by the coding target symbol # 2. Encoding target symbol # 2 of the prediction value register 8 (that is, encoding target symbol #
The reference symbol pattern of 4) can be used as an updated new value.

When the reference symbol patterns of the encoding target symbol # 2 and the encoding target symbol # 4 do not match at the system clock C4, the writing process to the order / prediction value memory and the reading process are performed at different addresses. Therefore, reading and writing are performed in parallel at the same time.
Encoding target symbol # in the system clock C5
As the order and predicted value of 4, the order and predicted value set in the order / predicted value register 8 at the system clock C4 are used. That is, when the encoding target symbol # 2 and the encoding target symbol # 4 do not match, the order and prediction value read from the order / prediction value memory 2 are used as the order and prediction value of the encoding target symbol # 4. Used. On the other hand, when the reference symbol patterns of the encoding target symbol # 2 and the encoding target symbol # 4 match, the access is prohibited by the access prohibition circuit 10, so the order and prediction value memory is not read, and the order is not read. The new order and prediction value updated by the prediction value control circuit 6 are used as the order and prediction value of the encoding target symbol # 4.

Also, when the normalization process and the update process to the order / predicted value occur in the encoding target symbol # 5, the encoding target symbol # 7 is processed by the above-mentioned process.
The order and predicted value of is determined.

Example 4. Next, FIG. 7 shows a block configuration of a decoding apparatus which is another embodiment of the present invention. In the figure, 11 is a region width signal 106 from the code bit sequence 107.
An arithmetic decoder that reproduces the prediction error symbol 105 based on
Reference numeral 12 is a prediction inverse converter that reproduces the information source symbol 101 by performing an exclusive OR operation of the prediction error symbol 105 and the prediction value 112. Further, 2 is a reference symbol pattern of 11 pixels excluding A among the reference pixels of FIG. 16, and the order and prediction value signals (103a, 104a and 103b, 104, respectively) for two kinds of states in which A is 1 and 0 are input.
It is a degree / predicted value memory that outputs 2 kinds of
Is a register which receives this output and also stores two kinds of orders and predicted values. Further, 13 is a selector for selecting one of two kinds of orders and prediction values according to the information source symbol 101 immediately before reproduced by the prediction inverse converter 12, and updating from the order / prediction value control circuit 6. A signal 108 is received and the reference pixel A in FIG. 16 has a degree / predicted value memory 2 of either 1 or 0 in accordance with the reproduced information source symbol.
The first selection update signal 108a and the second selection update signal 1 for updating the contents of the
It has a function of creating 08b.

FIG. 8 is a block diagram showing the internal structure of the arithmetic decoder 11. 11a is an effective area Ai on the number line.
Is stored in the A register, 11b is a subtractor for calculating the MPS area width 114, 11c is the LPS area width 106 and MPS.
A selector for selecting the region width 114, 11d is a bit position detector for receiving the selector output 115 and detecting the position of the highest one, and 11e is a selector 11c output 115 for the number of bits corresponding to the output 120. The first barrel shifter that shifts to the left, 11f is a C register that stores the lower bound coordinates, 1
1g is a subtracter that calculates the C register value 117 in the case of LPS, 11h is the C register value 117 and C in the case of LPS
A selector for selecting the register output 116, 11i is a code register 11j to be described later below the switch output 122.
The second barrel shifter for adding the low-order bit input 140 from, 11j is the code data 1 sent in byte units
A code register for inputting 07 to the C register 11f via the second barrel shifter 11i by a predetermined bit, 1
1k is a timing control circuit for controlling the movement of the arithmetic decoder 11.

FIG. 9 is a block diagram showing the internal structure of the code register 11j. 11j1 to 11j3 are buffer registers for temporarily storing code data, and 11j4 is a lower bit 1 input from the code register output to the C register.
A barrel shifter for producing 40, 11j5 is a digit control circuit for controlling the number of bits 126 to be shifted by this barrel shifter.

Next, the operation of this embodiment will be described. In the decoding of the arithmetic code, if the relative coordinates that are the contents of the C register are Ci and the area width of the LPS at the time of the i-th prediction error symbol a _i is S, then Ci-1 <(Ai-1 − S ) Then a _i is MPS Ai = Ai-1 − S Ci = Ci-1 Ci-1 ≧ (Ai-1 − S), then a _i is LPS Ai = S Ci = Ci-1 − (Ai-1 − S).

Here, when the effective area Ai becomes 1/2 or less, the normalization processing is 2 to increase the calculation accuracy.
To the power of. At this time, the code data of n bits is input to the lowest order of Ci from the code register 11j. Ai update value = Ai * 2 ^m (1/2 <A
i update value ≤ 1) Ci update value = Ci * 2 ^m

FIG. 10 is a timing chart showing an operation example of this embodiment. First, at each system clock, for the decoding target symbol, based on the reference symbol pattern of 11 pixels excluding A among the reference pixels of FIG. 16, A of 1 and 0 for two states 103a, 103b, and The predicted values 104a and 104b are read from the memory 2 and stored in the register 8. System clock 1
Do at the time of the cycle. After that, one of these two kinds of orders and predicted values is selected according to the value of A which is the information source symbol reproduced immediately before, and the reproduction and order of the information source symbol are selected.
Update the predicted value.

The reproduction of the prediction error symbol a _i , the calculation of the effective area Ai and the relative coordinates Ci, and the update of the order / predicted value are performed by the following operations. (1) First, the timing control circuit 1 inside the arithmetic decoder 11
At 1 k, the symbol a _i (MPS or LPS) is determined by comparing Ci-1 and (Ai -1-S) as described above according to the polarity of the LPSC register value signal 117. (2) When normalization and order / prediction value update is not performed As in the case of decoding target symbols # 1, # 3, # 4, and # 6 in FIG. 10, Ai and Ci are calculated and the A register 11a is calculated.
And the C register 11f. The series of processes (1) and (2) is performed in one cycle of the system clock. (3) When normalization and order / prediction value updating is performed As shown in FIG. 10, decoding target symbols # 2, # 5, #
When the effective area Ai is less than 1/2 as a result of the calculation of Ai and Ci as in the case of 7, the bit position detector 11d
The normalization process corresponding to the number of bits indicated by is performed.
Here, the bit shift / normalization operations by the barrel shifters 11e and 11i are performed within the same clock cycle as the processing of (1), and the processing of the next symbol is started. Also in this embodiment, it is assumed that the order / predicted value memory 2 is one capable of high-speed processing as compared with the conventional one.

The order / predicted value memory is updated by changing the order / order as shown by the system clocks C3, C6, and C8 in FIG.
The prediction value control circuit 6 and the detector 7 perform the first half cycle of the system clock. As described above, this decoding apparatus is characterized in that the normalization process can be performed within one system clock by using the barrel shifter. Further, since the normalizing operation can be executed within one clock cycle by using the barrel shifter, a big feature is that the order / prediction value memory is updated at high speed. In this example, writing to the order / predicted value memory 2 is performed in the first half of the system clock, and reading from the order / predicted value memory 2 is performed in the latter half of the system clock.

At the time of updating the order / predicted value, an update signal is output from the order / predicted value control circuit 6, and the reference pixel A is set to 1 to 0 based on the value of the information source symbol reproduced immediately before by the selector 13. Corresponding selection update signal (108a, 108b)
Is generated and the contents of the order / predicted value memory 2 are updated. Also, at this time, the order / predicted value memory 2 read immediately before
Reference pattern 102 is the update reference symbol pattern 1
If it matches with 09, the contents of the order / predicted value register 8 are also updated at the same time.

The operation of the code register 11j during normalization is as follows.
It is as follows. (A) The unprocessed code bit sequence already shown at the position from the uppermost position of the barrel shifter 11j4 is read by the number of normalized bits, and the data is set in the lower part of the C register 11f via the barrel shifter 11i. (B) As a result of this reading, the third buffer register 11
When there is no unprocessed code bit in j3, new code data is input and stored in the first buffer register 11j1, and the first and second buffer registers 11j2,
The contents of 11j3 are transferred to the second and third buffer registers 11j3 and 11j4, respectively. (C) Second and third buffer registers 11j2, 11j
If there is no unprocessed code bit for all three, another one byte of code data will be similarly input.

Therefore, the decoding processing time T is the same as that at the time of encoding. T = 100 + 100 * Na + α (nse
Therefore, even in the present embodiment, a great improvement can be realized in comparison with the decoding device according to the conventional technique.

Example 5. Further, FIG. 11 shows a block configuration of a code register 11j of an arithmetic decoder which is another embodiment. In this embodiment, the difference from the embodiment of FIG. 9 is that a word converter 11j6 that collectively forms code data input in byte units every 2 bytes into a word configuration, and a FIFO memory 11j7 that temporarily stores this are added. That is, the first and second buffer registers are deleted and the third buffer register 11j3 has a word configuration.

With this configuration, since the next 16-bit data can be prepared at the time when the code bit (maximum 16 bits) required for normalization is read from the buffer register 11j3, the decoding at ultra-high speed and constant speed is possible. Can be realized.

Example 6. Next, FIG. 12 shows a block configuration of a decoding apparatus which is another embodiment of the present invention. In the figure, the difference from the embodiment of FIG. 7 is that the order / prediction value memory 2 has a two-port configuration, and instead of the detector 7, the reference symbol pattern 102 and the same signal 109 for updating are monitored, If the reference symbol patterns 102 match (except A in FIG. 16) when the update signal 108 occurs,
Two-port control unit 1 for canceling access of a symbol pattern for updating, which corresponds to the reference symbol pattern 102 that is being accessed in parallel but coincides with the symbol pattern for updating
4. The access prohibition circuit 15 is added.

FIG. 13 shows an example of the decoding operation in this embodiment. The arithmetic decoder used here is that shown in FIG. The same processing as described above can be performed by the 2-port memory having the access time of 100 nsec.

In the above embodiment, the LPS and MPS calculation methods for arithmetic coding are a single method regardless of the effective area width. However, as disclosed in Japanese Patent Laid-Open No. 3-247123, the LPS of MPS is used.
When the magnitude relationship of the effective range of is reversed, MPS and LP
LPS when the SS allocation is reversed or when the MPS area width is less than 1/2, as in Japanese Patent Laid-Open No. 2-202267.
The same effect can be obtained by a method of allocating a part of the area to the MPS. The same applies to a method in which the MPS region is positioned higher on the number line.

[0074]

As described above, according to the present invention, the LPS can be used for arithmetic coding or decoding of the information source symbol.
Alternatively, by providing a new effective area width corresponding to the MPS and a boundary shifter for the area boundary value by a predetermined number of bits, or a FIFO memory, or a memory for storing the order / predictable value capable of simultaneous writing / reading,
It is possible to realize an encoding device or a decoding device that can significantly improve the encoding or decoding speed.

[Brief description of drawings]

FIG. 1 is a block diagram of an arithmetic encoder of an encoding device according to an embodiment of the present invention.

2 is a block configuration diagram showing an internal configuration of a code register in the embodiment of FIG. 1. FIG.

FIG. 3 is a timing chart showing an operation example according to the present embodiment.

FIG. 4 is a block diagram of a code register of an arithmetic encoder of an encoder according to another embodiment of the present invention.

FIG. 5 is a block configuration diagram of an encoding device according to another embodiment of the present invention.

6 is a timing diagram showing an operation example according to the embodiment of FIG.

FIG. 7 is a block configuration diagram of a decoding device showing another embodiment of the present invention.

8 is a block configuration diagram showing an internal configuration of an arithmetic decoder in the embodiment of FIG. 7. FIG.

9 is a block diagram showing an internal configuration of a code register of the arithmetic decoder shown in FIG.

10 is a timing diagram showing an operation example according to the embodiment of FIG.

FIG. 11 is a block configuration diagram of a code register of an arithmetic decoder showing another embodiment of the present invention.

FIG. 12 is a block diagram of an arithmetic decoder showing another embodiment of the present invention.

13 is a timing diagram illustrating an operation example according to the embodiment of FIG.

FIG. 14 is a block configuration diagram of an encoding device according to a conventional technique.

15 is a block diagram showing an internal configuration of an arithmetic encoder in the encoding device shown in FIG.

FIG. 16 is a diagram showing positions of reference symbols used for encoding.

FIG. 17 is a diagram showing the contents of an order / predicted value table.

FIG. 18 is a diagram showing the contents of an area width table.

19 is a timing diagram showing an operation example in the encoding device in FIG.

[Explanation of symbols]

 Second order / predicted value memory 5 Arithmetic encoder 6 Order / predicted value control circuit 7 Detector 8 Order / predicted value register 11 Arithmetic decoder 13 Selector 5a First register 5b First computing means 5d Second register 5e Second calculating means 5c First selecting means 5j Second selecting means 5h Bit position detecting means 5i First barrel shifter 5k Second barrel shifter 5f Code generating means 5f11 FIFO 11a First register 11b First calculating means 11f Second register 11g Second arithmetic means 11c First selecting means 11h Second selecting means 11d Bit position detecting means 11e First barrel shifter 11i Second barrel shifter 11j Code reading means 11j4 FIFO

Claims (6)

[Claims] 1. A coding apparatus for estimating the symbol appearance probability from an output symbol sequence of an information source, performing effective region division according to the estimation on the number line, and arithmetically coding this symbol sequence, , A first register for storing the effective area width of, a first calculating means for calculating the area width of a symbol (dominant symbol: MPS) which is assumed to occur frequently, and a boundary value of the effective area on the number line A second register for storing, a second calculation means for calculating a boundary value between a region corresponding to a symbol (recessive symbol: LPS) which is assumed to occur infrequently and an MPS region, and whether the generated symbol is MPS First selecting means for selecting a new effective area width depending on whether it is LPS; second selecting means for selecting a boundary value for a new effective area depending on whether the generated symbol is MPS or LPS; Bit position detecting means for receiving the new effective area width from the selecting means and detecting the position of the highest "1" or "0", and the first selecting means according to the output from the bit position detecting means. A first barrel shifter that shifts the new effective area width of the first effective area and outputs it to the first register, and shifts the boundary value of the new effective area from the second selecting means in accordance with the output from the bit position detecting means. And a second barrel shifter for outputting overflowed data to the second register and a code generation means for receiving a overflowed data output from the second barrel shifter and generating a code output. Encoding device. 2. The encoding device according to claim 1, wherein the code generation means includes a FIFO memory. 3. Decoding for estimating a symbol appearance probability from an output symbol sequence of an information source, performing effective area division according to it on a number line, and decoding a code bit sequence obtained by arithmetically coding this symbol sequence. In the device, a first register for storing the effective area width on the number line, a first calculating means for calculating the area width of a symbol (dominant symbol: MPS) that is assumed to occur frequently, and a number line on the number line Of the second register for storing the boundary value of the effective area of the second register, and the boundary value between the area of the symbol (recessive symbol: LPS) assumed to have a low frequency of occurrence from the second register output and the MPS area, and Second computing means for determining whether the symbol is MPS or LPS; first selecting means for selecting a new effective area width depending on whether the symbol is MPS or LPS; A second selecting means for selecting a boundary value of a new effective area depending on whether MPS or LPS and a new effective area width from the first selecting means are used to set the position of the highest "1" or "0". The bit position detecting means for detecting, the code data sequence as an input, the code reading means for outputting the code data sequence of the required number of bits according to the output from the bit position detecting means, and the output from the bit position detecting means. A first barrel shifter that shifts the new effective area width from the first selecting means to the first register and outputs it to the first register, and a new barrel from the second selecting means according to the output from the bit position detecting means. A decoding device comprising a second barrel shifter for shifting the boundary value of the effective area and the output from the code reading means and outputting the shifted value to the second register. 4. The decoding device according to claim 3, wherein the code reading means comprises a FIFO memory. 5. A coding device for predicting a coding target symbol from the states of a plurality of reference symbols at predetermined positions of an output symbol sequence of an information source and coding a prediction error signal thereof, the reference symbol comprising: In each state, the prediction value of the encoding target symbol and the order which is the identifier of the group classified by the predictive matching rate are stored in the two-port memory capable of simultaneous read / write operation, and the encoding target symbol is predictively matched. And a prediction value control circuit that rewrites the prediction value and the order in the reference symbol state according to the result, and the prediction value and the order of the encoding target symbol read from the 2-port memory, Or a degree / prediction value register for storing the prediction value and the degree after the rewriting process for the immediately preceding symbol to be encoded, and Prediction error signal based on the detector that detects whether the reference symbol state for the phantom symbol matches the reference symbol state for the immediately preceding symbol, and the predicted value / order output from the above-mentioned order / predicted value register. When the prediction value or order for the immediately preceding symbol is updated, the prediction value and order for the immediately preceding symbol is rewritten and the prediction value and order for the symbol to be coded are read. After the rewriting process, the prediction value and the order used for encoding depend on whether the reference symbol state for the encoding target symbol and the reference symbol state for the immediately previous encoding target symbol match. It is characterized by selecting and using the predicted value and order of, or the order and predicted value stored in the 2-port memory. Encoding apparatus for. 6. A code bit sequence in which a prediction error signal is encoded is decoded by predicting a decoding target symbol from the states of a plurality of reference symbols at predetermined positions of an output symbol sequence of an information source. The decoding device stores the predicted value of the decoding target symbol and the order, which is the identifier of the group classified by the predictive matching rate, from the state of the reference symbol, and corresponds to a plurality of symbols that may be decoded. Simultaneous write readable 2-port memory that outputs a plurality of orders and predicted values as a set, and whether or not the decoding target symbols are predictively matched, and the predicted values in the reference symbol state and The order / predicted value control circuit that rewrites the order and the reproduced signal value of the preceding decoding target symbol
A selector for selectively outputting one set of prediction values and orders out of a plurality of sets of prediction values and orders output from the port memory, and a prediction value and order from the two-port memory, or for the immediately preceding decoding target symbol. A register that stores the updated predicted value and order, a detector that detects whether the reference symbol state for the decoding target symbol matches the reference symbol state for the immediately preceding symbol, and the selected predicted value Equipped with an arithmetic decoder that decodes the code bit sequence based on the order, and when there is an update of the predicted value or order for the immediately preceding symbol, the predicted value / order rewriting process for the immediately preceding symbol and the decoding target symbol The prediction value or order reading process is performed in parallel, and the decoding target symbol is used as the prediction value and order used for decoding. Depending on whether or not the reference symbol state for the current symbol and the reference symbol state for the immediately previous symbol match, the predicted value and order after rewriting of the immediately previous decoding target symbol, or
A decoding device characterized by selecting and using a prediction value and an order stored in a 2-port memory.