JP2000299641A - Encoding device, decoding device, encoding / decoding device, encoding method, and decoding method - Google Patents

Abstract

(57) [Summary] [Problem] To reduce the total code length and the code sweeping time by determining the code by controlling the carry and replacing it with a predetermined pattern. A data memory for storing information source data,
A learning memory that stores learning data relating to encoding target data specified based on auxiliary parameters, a probability estimation table that outputs encoding parameters specified based on the learning data, and In an encoding device including an encoder that performs arithmetic encoding and outputs a code, a synchronization detector that measures and notifies a predetermined interval at each input processing of information source data or at each output of a code, and an effective area at a predetermined interval. The carry boundary value within
A carry boundary detector that indicates a truncation area in the effective area based on the detection result is provided, and the encoder is configured to divide one of the partial areas obtained by equally dividing the effective area indicated by the carry detector into upper and lower parts. Update the valid area by truncating.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to arithmetic coding and decoding of images or data, and more particularly to a coding device, a decoding device, a coding / decoding device, a coding method and a decoding method. It is.

[0002]

2. Description of the Related Art FIG. 39 is an explanatory diagram showing the concept of arithmetic coding. In FIG. 39, encoding is performed in such a manner that the entire effective area on the number line is divided into two partial areas for the superior symbol MPS and the inferior symbol LPS, and the partial area corresponding to the appearing symbol is updated to a new effective area. Done. However, as the area width becomes smaller, the number of significant digits of the lower bound value and the upper bound value increases as shown by a binary decimal number (fixed point), and the register precision for the operation becomes necessary.

Here, it is noted that even when the number of significant digits increases, the upper digits hardly change, and as shown in FIG.
The decimal part is always kept at the accuracy of area division (three digits in the figure), and normalization is performed to sweep out the upper digits to the integer part. FIG.
At 0, the effective area width A is set to 4 or more corresponding to 1/2 and 8 or less (8 is only the initial value) by expanding the effective area width A to a power of 2 by the normalization processing, and the lower bound value (sign) C
Then, the effective area can be represented by C or more and less than C + A.

A first conventional example An encoder (Decoder) and a decoder (Decoder) for arithmetic coding according to a first conventional example are based on ITU-T International Standard Recommendation T.30. 82
Can be realized by a table and a flowchart describing processing. Hereinafter, this arithmetic coding is referred to as QM
-Coder, its encoder is referred to as an encoder 1A, and its decoder is referred to as a decoder 16A. FIGS. 41 and 42 show schematic configurations of the encoder and the decoder.

In FIG. 41, there are two inputs to a coding section 1A, a first input is a context CX (Context) 2, and a second input is a pixel PIX (Pixel) 3 to be coded.
It is. The output is Code 4A. FIG.
, There are two inputs to the decoding unit 16A, the first input is the context CX2, and the second input is the code 4A. The output is the decoded pixel PIX3.

The data memory 5 stores an image (Image) 6 and, among neighboring pixels which have already been encoded / decoded, which can be commonly referred to with respect to a pixel to be encoded or decoded. Position the model template (Model Templa
A context (10 bits, total number: 1024) CX2 that is a reference pattern of 10 pixels specified by te) is generated. Also, at the time of encoding, the encoding target pixel is output at the same time, and at the time of decoding, the decoded pixel to be decoded is accumulated.

[0007] The QM-coder has a context CX
2 and 3 shown in FIG.
Select one of the standard model templates for the line,
The encoder informs the decoder using the specified header information.

[0008] In the QM-coder, the prediction coincidence probability of the pixel value is estimated for each context with respect to the pixel to be encoded / decoded, and the encoding / decoding is performed while learning according to the fluctuation.
Proceed with decryption. The learning is performed by rewriting a learning memory composed of two variable tables each having a context as an index. One is a 1-bit MPS table 7 that stores a pixel value MPS (More Probable Symbol: dominant symbol) having a high probability of appearing as a predicted value (a pixel value having a low predicted matching probability is LPS [Less
Probable Symbol]. The other is a 7-bit ST table 8 for storing state numbers (0 to 112) in which the degree of the predicted matching probability of the predicted value is classified into a total of 113 states. Default value is MPS
Table 7 and ST table 8 are all 0.

[0009] In addition to the variable table, a probability estimation table (Probab) composed of four constant tables that refer to state numbers (states) as indexes during encoding / decoding.
ility Estimation Table). LSZ table 9 representing LPS area width by 16 bits, MPS transition destination is 7
NMPS table 10 represented by bits, LPS transition destination is 7
An NLPS table 11 represented by bits, and a SWTCH table 12 represented by 1 bit for prediction value inversion determination. The set values are shown in FIG. 44 (the alphabetic variable / constant table name shown here is an array name used in a flowchart for describing processing to be described later).

The LSZ table 9 has an arithmetic encoder 13A /
It is referred to by the arithmetic unit in the arithmetic decoder 17A and is not directly related to learning of adaptive prediction. The arithmetic operation is performed using the LSZ value inside the arithmetic encoder 13A / arithmetic decoder 17A, and the normalization processing (Renormaliz
ation). When this normalization processing is performed, learning is instructed at the same time.

At the time of encoding, the pixel symbol converter 15
Is the coincidence of the pixel PIX3 with the MPS value output from the MPS table 7 using the context CX2 as an index /
The discrepancy is determined, and the binary symbol 14 is converted to the arithmetic coder 13
A, learning memory (MPS table 7, ST table 8)
And learning is performed according to the learning instruction.

At the time of decoding, the symbol pixel converter 1
8 is a binary symbol 14 decoded by the arithmetic decoder 17A.
From the MPS value output from the MPS table 7 using the context CX2 as an index and the pixel PI to be decoded
Judgment is made as to whether X3 matches or not, and if they match, the MPS value is decoded, and if they do not match, the LPS value (= 1−MPS) is decoded as the pixel PIX3 value. The decoded binary symbol 14 is output to a learning memory (MPS table 7, ST table 8), and learning is performed according to a learning instruction.

When learning is instructed, the NMPS table value 10 is written to the ST table 8 if the binary symbol 14 to be encoded / decoded is the superior symbol, and the NLPS table value 11 is written to the ST table 8 if the binary symbol 14 is the inferior symbol. Is realized. In the learning using the inferior symbol, if the predicted matching probability is １ ／, the MPS table value is inverted (operation “1-MPS”) and written into the MPS table.
Whether the match probability is 1/2 is determined using the SWTCH value as a flag.

The arithmetic encoder 13A performs an encoding operation on the input of the LSZ value 9 and the binary symbol 14 by a C register 30A indicating a code (area lower limit value) and an A register 31 indicating an area width. At 50, the code output timing is measured in byte units, the BUFFER 51 and the SC counter perform an undetermined code output standby with a possibility of carry-up and a determined code output, and output a code 4A.

The arithmetic decoder 17A measures the code input timing in byte units by the CT counter 50 from the input of the LSZ value 9 and the code 4A, and indicates the displacement from the lower limit of the area to the code 4A via the BUFFER 51. The decoding operation is advanced by the C register 30B and the A register 31 indicating the area width, and the binary symbol 14 is output.

Detailed processing operations within and between the constituent blocks shown in FIGS. 41 and 42 will be described with reference to FIGS.

Before describing the flow describing the encoding process and the flow describing the decoding process, the encoding register (C register) 30A and the decoding register (C register) 3
FIG. 45 shows the bit arrangement of 0B and the area width register (A register) 31.

In the encoding register (C) 30A, b
A decimal point is set between it15 and bit16, and "x" (1
6 bits) is an operation unit Cx32 for LSZ9,
If there is a carry, it propagates to a higher level. "s" (3 bits) is a spacer bit section Cs33, "b" (8 bits) is a byte output section Cb34, and "c" (1 bit) is a carry determination section Cc35. In the course of the encoding, the C register value is updated so as to be the lower limit of the area corresponding to the symbol encoded as code 4.

In the decoding register (C) 30B, the lower word CLOW 36 and the upper word CHIGH 38 are 32
Bit register that can be realized as a register of bits
A decimal point is set at the upper part of 31 and "b" (8 bits) is the upper byte Cb3 of the byte input part (CLOW register 36).
7, "x" (16 bits) is the operation unit Cx for LSZ9
(CHIGH register 38) 39. In the decoding process, the C register value is updated so as to be an offset value from the lower bound value of the area corresponding to the decoded symbol to the code 4 which is the coordinates in the area.

The area width register (A) 31 is common to the encoding / decoding, and corresponds to the decimal point of the encoding / decoding registers 30A and 30B, so that "a" (16
Bit) is arranged as a decimal part, and the integer part (bit 16) is "1" only in the initial state value. The area width (also called area size) is A-LSZ (lower area width) or LSZ
(Upper region width) is updated so that bit15 indicating a weight of 1/2 except for the initial value (integer part = "1") is normalized to be "1", and is maintained at 1/2 or more. Whatever LSZ 9 is selected as the upper region width, the lower region is ensured. In the normalization processing, the A register 31 and the C register 30A or 30B are simultaneously enlarged by the shift processing.

In the QM-coder, the upper region LSZ9, which has a fixed size with respect to the state, is normally assigned to the inferior symbol, but is assigned to the superior symbol when the lower region is smaller than the upper region.
PS exchange ". When encoding / decoding the inferior symbol and encoding / decoding the superior symbol by applying the conditional MPS / LPS exchange, the normalization process is always performed.

Based on the bit arrangement of the register, a flow for explaining the encoding process and a flow for explaining the decoding process will be described. The term "layer" in the flow describing the process
Means "(resolution) layer" in the case of hierarchical coding, and "stripes" means "strips" obtained by dividing an image in units of N lines (only the last stripe is N lines or less, or N = 1). . Here, the number of layers = 1 and the stripe = line (N = 1) will be described, but this does not prevent extension to encoding / decoding of a plurality of layers.

In order to explain the flow for explaining the encoding / decoding processing, the variables described in FIGS.
In addition to tables and registers, the following auxiliary variables CT50, B
UFFER51, SC52, and TEMP53 are used.
CT50 is the C register 30A, 30
This is an auxiliary variable for counting the number of shifts of the B and A registers 31 and, when the value becomes 0, performing the next code byte input / output. BUFFER 51 is an auxiliary variable that stores the code byte value output from the C register 30A during encoding and the code byte value input to the C register 30B during decoding. SC52 is an auxiliary variable used only for encoding and counting the number of consecutive bytes when the code byte value output from the C register 30A is 0xFF.

In this specification, a numerical value starting with "0x" represents a hexadecimal number. The TEMP 53 is used only for encoding, detects a carry to the BUFFER 51, and after carry processing, the lower 8 bits are replaced with a new BU.
This is an auxiliary variable for setting the FFER value 51. BUFF set from C register 30A through TEMP53
The ER51 does not become 0xFF without performing the carry process, and at that time, the lower 0xFF of the BUFFER51, that is, the BUFFER51 and SC52 0xFFs may be changed if the carry goes higher than the C register 30A. Code 4 even if output from C register 30A
Has not been determined.

FIG. 46 is a flowchart for explaining the ENCODER process showing the entire flow of the encoding process.
International Standard Recommendation T. 82, TP (Typical Prediction) and DP (Dete
The processing related to (rministic Prediction) is omitted because there is no direct relation. First, in S101, INITEN
The C processing is called, and the encoding processing is initialized. S10
In step 2, a pair of the pixel PIX3 and the context CX2 is read one by one, and in step S103, encoding is performed by ENCODE processing. In S104, S102 and S103 are repeated until the end of the stripe (here, line), and in S105, the encoding of the stripe is repeated from S102 to S104 until the end of the image. S10
In step 6, the FLUSH process is called to perform post-processing of the encoding process.

FIG. 47 shows an encoding target pixel value 3 and a prediction value 7
To switch the process to be called from the match / mismatch
It is a flowchart explaining a DE process. In S111, it is determined whether the pixel value 3 matches the prediction value 7 or not. If the pixel value 3 matches and the prediction value 7 does not match, the superior symbol is encoded. In S113, the CODEMPS process is called to code the superior symbol, and in S112, the CODELPS process is called to encode the inferior symbol.

FIG. 48 shows an encoding target pixel value 3 and a prediction value 7
Is a flowchart for explaining a CODELPS process called when non-coincidence is detected, that is, when encoding the inferior symbol. First, in S121, the value of the A register 31 is temporarily updated to the lower region width. If the determination in S122 is Yes, a conditional MPS / LPS exchange is applied, the A register 31 is left as it is to encode the lower region, and the C register 30A is not updated. If the determination in S122 is No, the upper region is encoded, and in S123, the C register 30A which is the lower limit of the region, and in S124, the A register 31 which is the region width is updated. Constant S in the determination of S125
If the WTCH value 12 is 1, the predicted value (MPS
Table) is inverted and updated. In LPS coding, S
At 127, a state transition is performed by referring to the NLPS table 11, and at S128, a RENORME process is called to perform a normalization process.

FIG. 49 shows an encoding target pixel value 3 and a prediction value 7
Is a flowchart for explaining a CODEMPS process called when encoding is performed, that is, when encoding a dominant symbol. First, in S131, the A register 3 is temporarily stored.
The 1 value is updated to the lower region width. N in S132
If it is o, the CODEMPS process is terminated as it is. S1
If the determination of No. 32 is Yes, the state transition by referring to the NMPS table 10 is always performed in S136, and the RE is changed in S137.
The normalization process is performed by calling the NORME process. S13
Before S6 and S137, if the determination in S133 is Yes, the A register 31 is left as it is to encode the lower region, and the C register 30A is not updated. If the determination in S133 is No, a conditional MPS / LPS exchange is applied, the upper region is encoded, and the C register 30
A, the A register 31 is updated in S135.

FIG. 50 shows a RENORM for performing a normalization process.
It is a flowchart explaining E processing. In S141, the A register 31 is shifted, and in S142, the C register 30A is shifted upward by one bit to perform an operation equivalent to double multiplication. In S143, 1 is subtracted from the variable CT50, and S
At 144, it is determined whether or not the value of the variable CT50 is 0.
If yes, the BYTEOUT processing is called in S145, and the 1-byte code 4 is output from the C register 30A. S1
In the determination at 46, the end of the normalization process is determined.
If the value of the register 31 is less than 0x8000, S141 to S
145 is repeated, and the process ends when 0x8000 or more is reached.

FIG. 51 is a flow chart for explaining BYTEOUT processing for outputting the code 4 one byte at a time from the C register 30A. The output byte is the byte output part Cb34 of the encoding register C30A. The carry determination unit Cc35 for determining carry is also processed at the same time. In S151, the Cb register 34 and the Cc register 3
5, a total of 9 bits are set in the variable TEMP53. S15
2 when there is a carry (TEMP ≧ 0x100; Cc
= 1), if there is no carry, the byte output is processed separately in S159 if 0xFF or less than 0xFF. If the determination in S152 is Yes, C
The value of the variable BUFFER 51 already output from the register 30A plus the carry 1 in S153, and the sum of the 52 byte values 0 of the variable value SC (the accumulated 0xFF has become 0x00 due to carry propagation) in S154. SC + 1
The byte determines the carry as the propagated code value.

At S155, the variable SC52 is set to 0, and at S15
In step 6, the lower 8 bits of the variable TEMP are set in the variable BUFFER51. In step S157, the Cc register 35 and the Cb register 34 processed as the variable TEMP53 are cleared,
In step S158, the variable C for processing 8 bits until the next output is output.
8. Set 8 to T50. If the determination in S159 is Yes, the code 4 cannot be determined, and 1 is added to the variable value SC52 to accumulate 0xFF. If the determination in S159 is No,
The code 4 already output from the C register 30A is assigned to S15.
3, the value of BUFFER 51 is determined, and in step S154, the sum SC + 1 bytes of the 52 variable values SCx byte value 0xFF is determined as the code value. At S163, the variable SC52 is set to 0, and at S16
In step 4, a variable BUF53 is set to a variable TEMP53 (8 bits as it is because there is no carry).

FIG. 52 is a flow chart for explaining the ST table 8, the MPS table 7, and the INITENC process for setting initial values of each variable at the start of encoding.
When the concept of layer and stripe is not introduced, the “first stripe of this layer” in S171 means “at the time of starting image coding”. For an image composed of a plurality of stripes, the variable table is initialized for each stripe. Processing can be continued without performing. In S171, it is determined whether the pixel is the first stripe of this layer or the table is forcibly reset.

If the determination in S171 is Yes, S172
Variable table S for all contexts CX2
T8 and MPS7 are initialized. S173 describes SC52,
S174 initializes the A register 31 value, S175 initializes the C register 30A, and S176 initializes the variable CT50. The initial value 11 of the variable CT50 is the sum of the number of bits of the Cb register 34 and the number of bits of the Cs register 33. When 11 bits are processed, the first code output is performed. S171
Is negative, the variable table is not initialized in S177, and the table value at the end of the stripe immediately before the same layer is reset.

FIG. 53 is a flow chart for explaining a FLUSH process for performing post-processing including a process of sweeping out the value remaining in the encoding register 30A at the end of encoding. S1
At 81, the CLEARBITS process is called to minimize the number of significant digits of the code remaining in the C register 30A. S182
Calls FINALWRITES processing and calls the variable BUF
The undetermined code 4 of the FER 51, SC52 and C register 30A is determined and finally output. In S183, the first byte of code 4 is the variable BUFFER 51 in the C register 3.
Since it is output (as an integer part) prior to the output of the 0A value, it is removed. In step S184, the code 4 is a decimal coordinate in the final effective area.
x00 is removed.

FIG. 54 is a flowchart for explaining a CLEARBITS process for performing a process for minimizing the number of significant digits of the code 4 at the end of encoding. As a result, the code 4 is a value in which 0x00 continues at the end as much as possible.
In step S191, a value obtained by clearing the lower two bytes (Cx register 32) of the upper bound value of the final effective area is set as the variable TEMP53. In S192, the magnitude of the cleared value of the lower 2 bytes of the upper bound value is compared with the value of the C register 30A. If the determination in S192 is Yes, in S193, the value that has been cleared is returned to the variable value TEMP53 and the C register 3
The value is assumed to be 0A. If the determination in S192 is No, the variable value T
Let EMP53 be the value of C register 30A.

FIG. 55 shows a FINAL in which the code determined at the end of encoding is written up to the value remaining in the C register 30A.
It is a flowchart explaining a WRITES process. S
At 201, the C register is shifted by the number of bits indicated by the variable value CT50 to enable code output and carry determination. At S202, the presence or absence of a carry is determined. S202
If the determination is Yes, there is a carry, and if No, there is no carry. Similar to the flow for explaining the BYTEOUT process, the code values with carry in S203 and S204, S2
At 07 and S208, the code 4 of the SC + 1 byte already output from the C register having a code value with no carry is determined.
The code output is completed by outputting the Cb register value (1 byte) in S205 and the lower 1 byte in S206.

FIG. 56 is a flowchart showing the overall flow of the decoding process.
It is a flowchart explaining an ECODER process. International Standard Recommendation T. The processes related to TP and DP in the flowchart describing the present process of 82 have no relation to the present invention and the conventional example (the first conventional example and the second conventional example), and thus the description thereof will be omitted. First, in step S211, the INITDEC process is called, and the decoding process is initialized. In S212, the context CX2 is read out one by one, and in S213, D
The pixel PIX3 is decoded by the ECODE processing. S
In step 214, steps S112 and S113 are repeated until the end of the stripe (here, the line).
Then, the decoding of the stripe is repeated from S212 to S214 until the image ends.

FIG. 57 shows a DEC for decoding a pixel to be decoded.
It is a flowchart explaining an ODE process. First, S
At 221, the value of the A register 31 is temporarily updated to the lower area width. If the determination in S222 is Yes, the lower area is decoded. If the determination in S223 is Yes, MPS_EXCHANGE processing is called in S224, and S225
And calls the RENORMD process to perform the normalization process.
If the determination in S223 is No, the dominant symbol is decoded without performing the normalization process, and the prediction value 7 is set to the pixel value 3. If the determination in S222 is No, the upper area is decoded. In step S227, the LPS_EXCHANGE process is called, and in S228, the RENORMD process is called to perform normalization. MPS_EXCHANGE processing, LPS
In the path that calls the _EXCHANGE process, even if the regions to be decoded are determined, it is impossible to determine whether the symbol to be decoded is the superior symbol or the inferior symbol without comparing the sizes of the regions. A pixel value 3 to be decoded is determined in the flowchart describing the called process.

FIG. 58 shows LPS_E for decoding the upper region.
It is a flowchart explaining an XCHANGE process.
If the determination in S231 is Yes, the dominant symbol is decoded. The C register 30B is updated in S232, and the A register 31 is updated in S233. In S234, the prediction value 7 is set to the pixel value 3 as it is. In S235, a state transition is performed by referring to the NMPS table 10. If the determination in S231 is No, the inferior symbol is decoded. C register 3 in S236
0B is updated to the A register 31 in S237. S23
In 8, the non-prediction value “1−prediction value” is set to the pixel value 3. S2
If the determination at Step 39 is Yes, the predicted value (MPS
Table) 7 is inverted and updated. NLPS in S241
State transition is performed by referring to Table 11.

FIG. 59 shows an MPS_E for decoding the lower region.
It is a flowchart explaining an XCHANGE process.
If the determination in S251 is Yes, the inferior symbol is decoded. In S252, the non-prediction value is set to the pixel value 3. S253
Is YES, the predicted value (MPS table) 7 is inverted and updated in S254. In S255, a state transition is performed by referring to the NLPS table 11. If the determination in S251 is No, the superior symbol is decoded. In S256, the prediction value 7 is set to the pixel value 3 as it is. NM in S257
State transition is performed by referring to the PS table 10.

FIG. 60 shows a RENORM for performing a normalization process.
It is a flowchart explaining a D process. In S261, it is determined whether or not the variable CT50 is 0. If the determination is Yes, S2 is performed.
At 62, BYTEIN processing is called and C register 30B
1 byte code 4 is input. In S263, the A register 31 is shifted, and in S264, the C register 30B is shifted one bit higher to perform an operation equivalent to double multiplication. In S265, 1 is subtracted from the variable CT50. S266
Is to determine the end of the normalization process, and if the A register 31 is less than 0x8000, the process proceeds from S261 to S26.
Repeat step 5. In S267, it is determined whether or not the value of the variable CT50 is 0. If the determination is Yes, BYTEIN processing is called in S268, and a one-byte code is input to the C register 30B.

FIG. 61 shows a case where the code 4 is set to 1 in the C register 30B.
It is a flowchart explaining BYTEIN process which reads byte by byte. SCD (Stripe Coded Data) is a code 4 for the stripe. Determination is Yes in S271
In the case of, because there is no code 4 to be read, the variable BUFFER5
1 is set to 0. In step S273, the variable BUFFER51 is set to CL.
The value is read into the OW register 36 (Cb 37), and 8 is set in the variable CT50 to process 8 bits until the next input in S274.
Set. When the determination is No, 1 byte code 4
Is read into the variable BUFFER 51.

FIG. 62 shows an ST table 8 at the start of decoding.
MPS table 7 and IN for setting initial values of each variable
It is a flowchart explaining ITDEC processing. S281, S282, S29 for setting the initial value of the table
0 is the same as S171, S172, and S177 in the flowchart for describing the INITENC process of the encoding process. The initial value of the C register 30B is set by reading 3 bytes of the code 4 into the Cx register 39 and the Cb register 37. In step S283, the C register 30B is cleared. In step S284, the BYTEIN process is called, and the code 4 is read into the Cb register 37 by one byte. S285
Shifts the C register 30B by 8 bits, calls BYTEIN processing in S286, and sets the code 4 to the Cb register 3
Read one byte into 7 In S287, the C register 30B is shifted by 8 bits, and in S288, the BYTEIN process is called to read the code 4 into the Cb register 37 by 1 byte. Thus, the code 4 of 3 bytes in total is stored in the Cx register 39.
And Cb register 37. S28
In step 9, the initial value of the A register 31 is set.

Next, a second conventional example will be described. An encoder / decoder for arithmetic coding according to the second conventional example is disclosed in Japanese Patent No. 275.
This is realized by a table described in No. 5091 and a flowchart describing processing. Here, in arithmetic coding that outputs a code in byte units, when the output byte value becomes 0xFF, if a carry occurs later, the code value cannot be determined because it may propagate to higher places already output. Therefore, if the output byte value is 0
It is considered that if there is a possibility of carry in the effective area at the time of xFF, the presence or absence of carry is forcibly determined.

FIG. 63 is a conceptual diagram for forcibly determining the presence or absence of a carry. In the figure, the lower bound value C is a code register (C register) value 30A, and the upper bound value U60 is a value obtained by adding the effective area width A (A register value) 31 to the lower bound value C30A. When the most significant bits of the lower bound value and the upper bound value do not match, it is determined that there is a carry, and at that time, a carry boundary value T61 exists in the effective area.

Accordingly, if the effective area is called a carry area and an area without carry is called a non-carry area in two partial areas divided by a carry boundary, the carry area is The region width R162 is (U-
T), the non-carry region width R063 is represented by (TC). In order to determine the presence or absence of a carry, the effective area only has to completely match or be included in the carry area or the non-carry area. And correct the other as a new valid area. In the truncation of the region, the loss of the code length can be reduced by truncating the smaller region. Therefore, in the drawing, the smaller R063 partial region is truncated. By truncating the partial area, it is necessary to determine again the necessity of the normalization processing for the corrected effective area. Such a carry control method of arithmetic coding is called an adaptive region truncation method.

FIGS. 64 and 6 show schematic configurations of the encoding unit 1B and the decoding unit 16B of the arithmetic coding to which the adaptive region truncation method is applied.
It is shown in FIG. In FIG. 64, the encoding unit 1B associated with the replacement of the arithmetic encoder 13B and the code 4B is configured corresponding to FIG. 41 of the first conventional example. In FIG. 65, the arithmetic decoder 17B and the decoding unit 16B accompanying the replacement of the code 4B are different from FIG. 42 of the first conventional example. The data flow between the blocks in which these have been replaced, and the learning method are the same as in the conventional embodiment shown in FIGS.

The arithmetic encoder 13B performs an encoding operation in the C register 30A and the A register 31 from the input of the LSZ value 9 and the binary symbol 14, and measures the code output timing in byte units by the CT counter 50, and calculates the code. In synchronization with the output, the U register 60, T
Judgment is made from the register 61, the R1 register 62, and the R0 register 63. If there is a carry boundary, the adaptive region truncation method is applied to correct the C register 30A and the A register 31 to forcibly determine whether or not a carry is present. The code is output by carrying the carry up to and the code is determined, and the code 4B is output.

The arithmetic decoder 17B measures the code input timing in byte units by the CT counter 50 from the input of the LSZ value 9 and the code 4B, and arithmetically checks whether there is a carry boundary in the area at the time of code input. D register 64 and U register 6 reproducing the code register 30A of the encoder 13B
0, the T register 61, the R1 register 62, and the R0 register 63, and if there is a carry boundary, the adaptive region truncation method is applied to the C register 30A, the D register 64, and the A register.
By modifying the register 31, via the BUFFER 51,
C register 30B, A register 31, D register 64
And the decoding operation proceeds, and the binary symbol 14 is output.

The detailed processing operations within and between the constituent blocks shown in FIGS. 64 and 65 are described in the first section.
FIG. 46 is a flowchart for explaining the processing of the conventional example of FIG.
49, 53, 54, 56, 57, 59
And FIG. 67 to FIG.
Will be described.

FIG. 66 shows a code register of the adaptive area truncation method. The Cs register 33 is omitted in comparison with the code register shown in FIG. 45 according to the first conventional example. This is to synchronize the byte output of the encoder with the byte input of the decoder, and the application of the adaptive region truncation process is also applied in synchronization with the byte input / output. here,
In encoding (encoder), the code register value is updated to the lower bound of the effective area, and in decoding (decoder), the code register value is updated to the displacement (offset) from the lower bound of the effective area to the code value. Therefore, at the time of decoding, the carry boundary cannot be accurately determined unless the code register value of the encoder is reproduced. Therefore, in decoding, it is assumed that the value is held by the D register 64 having the same configuration as the code register of the encoder.

A description will now be given of a flowchart for explaining a modified or added process in the second conventional example. The adaptive region truncation method will be described by adding only necessary modifications to the flowchart for explaining the encoding / decoding process of the QM-coder described in the first conventional example. 46 to 49, 53, and 54 relating to the encoder and FIGS. 56, 57 and 59 relating to the decoder are the same as the flow for explaining the processing of the first conventional example. The upper bound value U60, carry boundary value T61, non-carry area width R063, carry area width R162, and D register 64 used in the above description are additionally introduced as variables.

FIG. 67 shows a RENORM for performing a normalization process.
It is a flowchart explaining E processing. For the first conventional example (FIG. 50), a ROUNDDOWN process for calling the adaptive region truncation process is determined.
147 is added, and the call of the BYTEOUT process (S145 in FIG. 50) is performed from the ROUNDDOWN process.

FIG. 68 is a flow chart for explaining the ROUNDDOWN processing for applying the adaptive area truncation processing. In S301, it is determined whether or not the output byte value is 0xFF. If No, the process ends. A carry boundary value T61 (constant) is set in S302, and a non-carry region width R063 is set in S303. In step S304, the non-carry region width R063 is compared with the region width (A register value).
0 value 63 is not smaller than A register value 31 or R
If the 0 value 63 is not larger than 0 (No), the process is terminated as it is because the carry boundary T61 is not within the effective area.
If the R0 value 63 is smaller than the A value 31 or the R0 value 63 is larger than 0 (Yes), the upper bound value U6 is determined in S305.
0 is set, and a carry region width R162 is set in S306. If the R0 value 63 is smaller than the R1 value 62 in S307 (Yes), the carry-over area is set as an effective area.
At 308, the lower bound value is changed to the carry boundary value. At S309, the R1 value is set to the area width (A register value). If the value is larger (No), S30 is set to make the non-carry area an effective area.
In step 9, the R0 value 63 is set in the area width (A register value) 31. Finally, the BYTEOUT processing is called in S311.

Each change in FIGS. 69 (flow describing the BYTEOUT processing), FIG. 70 (flow describing the INITENC processing), and FIG. 71 (flow describing the FINAL WRITES processing) shown in FIGS. 51, 52 and 55 will be described. Then, first, by deleting the Cs register section 33 of the code register, S151 ′ and S157 ′ of FIG. 69 (flow describing the BYTEOUT processing) and FIG. 70
S17 in (flow describing INITENC process)
6 ′, the settings of the masks and shift numbers in S202 ′, S205 ′, and S206 ′ of FIG. 71 (flow describing the FINAL WRITES processing) are changed.

Also, in FIG. 68 (flow describing the ROUNDDOWN processing), the output byte value is 0xFF
Since the presence or absence of carry propagation at the time of has already been solved, the variable BUFFER can be sequentially output, and the determination S159 in FIG. 69 (flow describing the BYTEOUT processing) becomes unnecessary, and The variable SC itself and the related FIG. 69 (BYTEOUT
S154, S155, S16 of the flow for explaining the processing)
0, S162, S163, S173 in FIG. 70 (flow describing the INITENC process), and FIG. 71 (FINALW)
S204, S20 of the flow describing the RITS process)
8 is also unnecessary.

FIG. 72 shows LPS_E for decoding the upper region.
It is a flowchart explaining an XCHANGE process.
S24 for reproducing the code register of the encoder as the D register 64 with respect to the first conventional example (FIG. 58).
2. S243 has been added.

FIG. 73 shows REN for performing normalization processing.
It is a flowchart explaining an ORMD process. Compared to the first conventional example (FIG. 60), S269 for reproducing the code register of the encoder as a D register, ROUNDDOWN for determining the application of adaptive region truncation processing.
S270 for calling the D processing is added, and the calling for the BYTEOUT processing (S262 in FIG. 60) is set to ROUNDDOWND.
It is performed from processing. Also, S261 and S267 of FIG.
The flow shape for explaining the processing is different because the redundancy of the judgment has been removed, but the processing content is the same.

FIG. 74 is a flow chart for explaining a ROUNDDOWN process for applying the adaptive region truncation process. The code register variable name C30A has been changed to D64 for the ROUNDDOWN processing in FIG.
Steps S321 to S331 correspond to steps S301 to S311. The code register 30B of the decoder is additionally provided with S332 for performing the adaptive region truncation processing corresponding to the code register 30A (register D64) of the encoder. Finally, the BYTEIN process is called in S331 instead of the BYTEOUT process (S311) in FIG.

FIG. 75 (flow for explaining BYTEIN processing), FIG. 76 (flow for explaining INITDEC processing)
61 and FIG. 62, S276 of FIG. 75 and S290 of FIG. 76, which are initialization processing for reproducing the code register 30A of the encoder as the D register 64, are added.

[0061]

However, the above-mentioned prior art has the following problems. In the encoder according to the first conventional example, when the code value cannot be determined without solving for the presence or absence of a carry, the code length to wait in the counter is stored. There was a problem that there is. Further, the code may not be swept out to the end unless the code value is determined. In particular, when the data length is unknown, it is difficult to estimate the code delay time. Furthermore, when the code value is determined, the longer the code length waiting for output is, the longer the sweeping time is, and there is a problem that the encoding process must be stopped completely or temporarily.

On the other hand, in the encoder according to the second conventional example, there is a problem that it is necessary to determine the execution of the carry control based on the value of the code register and to calculate the carry boundary exactly. Further, in the decoder according to the second conventional example, there is a problem that it is impossible to accurately determine whether carry control is performed unless the code register of the encoder is reproduced.

The present invention has been made to solve the above-described problems relating to the prior art, and eliminates the overflow of a counter for storing a code length that waits until a code is determined, thereby preventing the counter from overflowing. The carry is controlled by forcibly determining the code so that the delay time of the code is finite and can be estimated.When the code value is determined, the total code length and the code are replaced by a predetermined pattern. The purpose of the present invention is to shorten the time required for sweeping out.

Another object of the present invention is to perform carry control without strictly calculating a carry boundary, and to carry carry without reproducing a code register of an encoder by a decoder.

[0065]

According to the present invention, there is provided an encoding apparatus comprising: a data memory for storing information source data and outputting encoding target data and auxiliary parameters (context) thereof; A learning memory that accumulates and outputs learning data relating to the encoding target data specified in the above, a probability estimation table that outputs an encoding parameter specified based on the learning data, the encoding target data and the encoding A coder that performs arithmetic coding based on parameters and outputs a code, and a synchronization detector that measures the input processing of information source data in a predetermined unit or outputs the code at a predetermined interval and notifies the synchronization detector Detecting a carry boundary value in the effective area at the predetermined interval, and instructing a truncation area in the effective area based on the detection result. And an up boundary detector, wherein the encoder updates the effective area by truncating one of partial areas obtained by equally dividing the effective area indicated by the carry detector into upper and lower parts. Is what you do.

When the carry boundary is detected by the carry boundary detector, the encoder includes a partial area obtained by equally dividing the effective area designated by the carry boundary detector into upper and lower parts. The method is characterized in that one of the valid areas is updated by truncating one of them.

Further, the carry boundary detector instructs to cut off a partial area including the detected carry boundary.

The above-mentioned predetermined interval is characterized in that a predetermined unit of data to be coded is coded.

Further, the predetermined interval is set based on the maximum value of the code length to wait until the code value is determined.

Further, the encoder is characterized in that a maximum value of a code length to wait until a code value is determined is set based on the predetermined interval.

The above-mentioned predetermined interval is characterized in that a predetermined unit of code output is generated.

The predetermined interval is characterized in that a predetermined unit of code output is generated and the code output value becomes a predetermined value.

The carry boundary detector indicates one of the partial areas obtained by equally dividing the effective area into upper and lower parts even if no carry boundary is detected in the effective area. It is characterized by the following.

The encoder is characterized in that it has a run-length marker converter which replaces the determined code with a run-length marker which can specify the value and length when the same value continues.

Further, the run-length marker converter includes:
If the code output is shorter than the run length marker that is converted without being replaced, the conversion is not performed.

The maximum value of the continuous length extracted from the run-length marker is set by the encoder to the run-length marker converter based on the result of the inverse transform of the run-length marker at the time of decoding. It is assumed that.

Further, a decoding device according to the present invention includes a data memory for outputting auxiliary parameters (context) for data to be decoded, storing the decoded data to be decoded, and outputting it as information source data; A learning memory that accumulates and outputs learning data on the data to be decoded specified based on the auxiliary parameter; a probability estimation table that outputs a decoding parameter specified based on the learning data; A decoder that performs arithmetic decoding and outputs the data to be decoded, and a synchronization detector that measures and notifies output processing or code input of information source data in a predetermined unit as a predetermined interval, and The carry boundary value in the effective area is detected at the above-mentioned predetermined interval, and the cutoff in the effective area is performed based on the detection result. A carry boundary detector for indicating a discard region, wherein the decoder updates the valid region by truncating one of the partial regions, which does not include the code value, of the partial region obtained by equally dividing the valid region into upper and lower parts It is characterized by the following.

Further, when the carry boundary is detected by the carry boundary detector, the decoder cuts off one of the partial areas obtained by equally dividing the effective area into upper and lower parts that does not include the code value. It is characterized in that the effective area is updated.

Further, the carry boundary detector instructs to cut off a partial area including the detected carry boundary.

Further, the predetermined interval is characterized in that a predetermined unit of data to be decoded is decoded.

The predetermined interval is characterized in that a predetermined unit of code input occurs.

Further, the predetermined interval is characterized in that a code input of a predetermined unit occurs and a code output value reproduced at the same time as decoding becomes a predetermined value.

Further, the above-mentioned decoder is characterized in that it has a run-length marker inverse transformer that, when a run-length marker is detected, inversely transforms it to the original code value of the replaced length.

The encoding / decoding device according to the present invention, as an encoding device, accumulates information source data and encodes data to be encoded and its auxiliary parameters (context).
, A learning memory for accumulating and outputting learning data on the data to be encoded specified based on the auxiliary parameter, and a probability estimation for outputting an encoding parameter specified based on the learning data. A table, an encoder that performs arithmetic encoding based on the encoding target data and the encoding parameter and outputs a code, and measures input processing of information source data in a predetermined unit or output of the code as a predetermined interval. A synchronous detector for notifying and detecting a carry boundary value in the effective area at the predetermined interval,
A carry boundary detector for indicating a truncated area in the effective area based on the detection result, wherein the encoder is configured to equally divide the effective area indicated by the carry detector into upper and lower parts One of the areas is truncated to update the effective area, and the decoding device outputs auxiliary parameters (context) for the data to be decoded, accumulates the decoded data to be decoded, and outputs it as information source data. A data memory, a learning memory for accumulating and outputting learning data relating to the data to be decoded specified based on the auxiliary parameter, a probability estimation table for outputting decoding parameters specified based on the learning data, A decoder that performs arithmetic decoding based on parameters and codes and outputs the decoding target data; and a predetermined unit of information source data. A synchronization detector that measures and outputs the output of the power processing or the code as a predetermined interval, and detects a carry boundary value in the effective area at the predetermined interval, and truncates the effective area based on the detection result. A carry boundary detector for indicating a region, wherein the decoder updates the valid region by truncating one of the partial regions that does not include the code value of the partial region obtained by equally dividing the valid region into upper and lower parts. It is a feature.

When the carry boundary is detected by the carry boundary detector, the encoder includes a partial area obtained by equally dividing the effective area designated by the carry boundary detector into upper and lower parts. When the carry boundary is detected by the carry boundary detector, the code value of a partial region obtained by equally dividing the effective region into upper and lower parts is detected when the carry boundary is detected by the carry boundary detector. , And the effective area is updated by cutting off one of the effective areas.

Further, the encoding method according to the present invention
(A) a data accumulation step of accumulating information source data and outputting encoding target data and its auxiliary parameters (context); and (b) learning on the encoding target data specified based on the auxiliary parameters. A learning step of accumulating and outputting data; (c) a probability estimating step of outputting an encoding parameter specified based on the learning data; and (d) an arithmetic operation based on the encoding target data and the encoding parameter. An encoding step of encoding and outputting a code; (e) a synchronization detection step of inputting information source data in a predetermined unit or measuring and outputting a code output at a predetermined interval; A carry boundary detecting step for detecting a carry boundary value in the effective area at intervals of and instructing a truncation area in the effective area based on the detection result. , Those having an encoding correction step of updating the effective region by truncating one of (g) the carry boundary detected partial areas obtained by equally dividing the effective area indicated in the upper and lower by step.

In addition, the encoding correction step includes, when a carry boundary is detected in the carry boundary detection step, a portion obtained by equally dividing the effective area designated in the carry boundary detection step into upper and lower parts. The present invention is characterized in that one of the areas is truncated to update the effective area.

Further, the encoding step and the encoding correcting step include a conversion step in which, when the same value continues to the determined code, the code is replaced with a run-length marker whose value and length can be specified. Things.

The conversion step is characterized in that conversion is not performed when the code output is shorter than the run-length marker to be output as it is without replacement.

Further, the maximum value of the continuous length extracted from the run-length marker is set in the encoding step in the conversion step based on the result of the inverse transformation of the run-length marker during decoding. Things.

Further, the decoding method according to the present invention
(A) a data accumulating step of outputting auxiliary parameters (context) for the data to be decoded, accumulating the decoded data to be decoded, and outputting the data as information source data; and (b) a data designation step based on the auxiliary parameters. A learning step of accumulating and outputting learning data relating to the decoding target data, (c) a probability estimating step of outputting a decoding parameter designated based on the learning data, and (d).
A decoding step of performing arithmetic decoding based on the decoding parameter and the code and outputting the decoding target data; and (e) measuring a predetermined unit of output processing of information source data or inputting a code as a predetermined interval and notifying. A synchronization detection step
(F) a carry boundary detecting step of detecting a carry boundary value in the effective area at the predetermined interval and indicating a truncation area in the effective area based on the detection result;
(G) a decoding correction step of updating the effective area by cutting off one of partial areas obtained by equally dividing the effective area specified by the carry boundary detection step into upper and lower parts.

In addition, the decoding correction step includes, when a carry boundary is detected in the carry boundary detection step, a portion obtained by equally dividing the effective area designated in the carry boundary detection step into upper and lower parts. The present invention is characterized in that one of the areas is truncated to update the effective area.

Further, the decoding step includes a run-length marker inverse transforming step of, when a run-length marker is detected, performing inverse transform to an original code value having a replaced length.

[0094]

DESCRIPTION OF THE PREFERRED EMBODIMENTS Embodiment 1 In the first embodiment, as in the above-described second conventional example, a method is employed in which the partial area of the effective area is truncated and the presence or absence of a carry is determined for the output code. It is equally divided into regions, and a partial region including a carry boundary is discarded.

Since the area width always takes the same value between the encoder and the decoder, according to the equal division operation, the carry boundary value does not have to be strictly introduced into the encoding / decoding as in the second conventional example. It is only necessary to know which of the upper and lower partial areas is included.

For example, as shown in FIG. 1, when the maximum effective area is 16, the effective area is kept at 8 or more by the normalization processing. At this time, if 1.0000 is the carry boundary, the upper half area is truncated if the boundary is higher, and the lower 1/2 area is truncated if the boundary is lower. However, when the effective area width is an odd number, an error due to loss of digit due to lack of effective representation accuracy occurs. In the figure, since the effective area width = 9,
If it is simply set to １ ／, it becomes 4 (integer), and if it is set as the lower region width, the upper region width becomes 5. Therefore, if the upper region is truncated, the width of the lower region is doubled to 8; if the lower region is truncated, the width of the upper region is doubled to 10
And it is not strictly equally divided.

Here, 1/1/3 of the area width (A register) 31
After calculating 2, it is certain that it will be at least doubled in the normalization process. Therefore, there is a method of correcting a bit that is lost by a 1/2 operation of the A register later. Another method is to keep the area width (= 9),
First, only the lower bound (C register) 30A is doubled, and when the lower region is discarded, a desired error-free coordinate can be obtained by adding the region width 31 = 9. In any case, according to the 1/2 area truncation method, a code length of 1 bit is always generated for one application.

In the first embodiment, a coder for arithmetic coding of the half area truncation method is a coder 1C and a decoder thereof is a decoder 16C, and the schematic configuration of the coder and the decoder is shown in FIG. As shown in FIG. In FIG. 2, the arithmetic encoder 13C, the code 4
The encoding unit 1C accompanying the replacement of C is the same as that of FIG.
It is configured corresponding to. In FIG. 3, the arithmetic decoder 17C,
The decoding unit 16C accompanying the replacement of the code 4C is different from FIG. 65 of the second conventional example. The data flow between the blocks in which these are replaced and the learning method are the same as those in the conventional example shown in FIGS.
Same as 5.

The arithmetic encoder 13C performs an encoding operation in the C register 30A and the A register 31 from the input of the LSZ value 9 and the binary symbol 14, and measures the code output timing in byte units by the CT counter 50, and calculates the code. T register 61, R
Judge from 0 register 63, and if there is a carry boundary, 1 /
By applying the two-region truncation method, the C register 30A and the A register 31 are corrected to forcibly determine the presence or absence of a carry, carry-carrying is performed up to a maximum of BUFFER 51, a fixed code is output, and a code 4C is output. .

The arithmetic decoder 17C measures the code input timing in byte units by the CT counter 50 from the input of the LSZ value 9 and the code 4C, and arithmetically checks whether there is a carry boundary in the area at the time of code input. D register 64 and T register 6 reproducing the code register 30A of the encoder 13C
1. Judgment is made from the R0 register 63, and if there is a carry boundary, a half area truncation method is applied to the C register 30A,
Modify D register 64 and A register 31
Via the ER 51, the C register 30B and the A register 3
1. The decoding operation is advanced by the D register 64, and the binary symbol 14 is output.

Detailed processing operations in and between the constituent blocks shown in FIGS. 2 and 3 are flow charts for explaining the processing of the first conventional example described above. FIGS.
9, FIG. 53, FIG. 54, FIG. 56, FIG. 57, and FIG. 59, and FIG. 67, FIG. 69 to FIG. 74, FIG. 4 to 7, or FIGS. 4, 6, and 8 to 11, which are given as flows describing the equivalent processes.

In the first embodiment, a description will be given of FIG. 68 (flow describing the ROUNDDOWN processing) in which the carry-out or non-carry-out area is cut off in the second conventional example, and FIG. 74 (ROUNDDOWN processing). 4 and 6 shown below, and FIG. 5 (flow describing HALVINGE processing) and FIG. 7 (flow describing HALVINGD processing) called therefrom.
Is a method for realizing the half area truncation method by adding.

FIG. 4 is a flowchart for explaining the ROUNDDOWN processing for determining the application of the 1/2 area truncation processing. In the figure, S301 to S304 and S3
01 and S311 to be processed based on the determination results in S304 (both are No) are the same as those in FIG. According to the determination result (Yes) in S304, the HALVING process for performing the half area truncation process is called in S312.

FIG. 5 shows an HA for performing a half area truncation process.
It is a flowchart explaining a LVINGE process. S
At 341, the double of the non-carry area width R 0 is A register value 3
If it is smaller than 1 (judgment Yes), the lower half area includes a carry boundary, and if it is not smaller (decision No), the information 1/2 area includes a carry area and includes the carry boundary. The / 2 region is truncated. Lower 1
If the / 2 area is to be truncated, after updating the C register value (effective area lower limit value) 30A by １ ／ of the A register value (effective area width) 31 in S342, BYTE is executed in S343.
Call OUT processing. Although the A register value 31 should be actually reduced to １ ／ due to the region truncation, the A register value 31 is not updated because it is immediately doubled by the normalization processing. S344 and S345 corresponding to normalization processing are performed on the C register 30A and the CT counter value 50. At S346, it is determined whether or not the A register value 31 is an odd number. If the A register value 31 is an odd number, the value lost by 1/2 of the A register value 31 is corrected at S347. When the upper half area is truncated, the C register value 30A is not updated, and the BYTEOUT processing is called in S348. S349 and S350 corresponding to the normalization processing are performed on the C register 30A and the CT counter value 50.

FIG. 6 is a flowchart for explaining the ROUNDDOWN processing for determining the application of the half area truncation processing. In the figure, S321 to S324 and S3
21 and S332 performed based on the determination results of S324 (both are No) are the same as those in FIG. Based on the determination result (Yes) in S324, the HALVINGD process for performing the half area truncation process is called in S333.

FIG. 7 shows an HA for performing a half area truncation process.
It is a flowchart explaining an LVINGD process. In the ROUNDDOWN processing of FIG. 5, the code register variable name C30A has been changed to D64, S361 to S370 correspond to S341 to S350, and the code register C30B of the decoder is replaced with the code register 30A of the encoder.
S371, S372, S373, and S374 for performing a half area truncation process corresponding to (register D64) are added. Finally, the BYTEIN process is called in S331 instead of the BYTEOUT process (S311) in FIG.

Here, the flow for explaining the HALVINGD process in FIG. 5, the flow for explaining the HALVINGD process in FIG. 7, the flow for explaining the called BYTEOUT process (FIG. 69), and the flow for explaining the BYTEIN process (FIG. 74) 8 (HALVINGE) shown below.
The processing can be replaced by a flow for explaining the processing, FIG. 9 (a flow for explaining the BYTEIN7 processing), FIG. 10 (a flow for explaining the HALVINGD processing), and FIG. 11 (a flow for explaining the BYTEIN7 processing). BYTEOU
The flow for explaining the T7 process and the flow for explaining the BYTEIN7 process are as follows. The C register 30B is doubled first without reducing the A register value (area width) 31 to １ ／, thereby preventing the loss of digits. The input / output position is shifted by one bit to a higher position than the normal position in the flow explaining the BYTEOUT process and the flowchart explaining the BYTEIN process. In particular, in the encoder, an extra bit of precision must be guaranteed in the higher order.

FIG. 8 shows an HA for performing a half area truncation process.
It is a flowchart explaining a LVINGE process. S
In steps 381 and S382, the C register 30A and the non-carry area width R063 are doubled, and processing equivalent to normalization is performed first. If the non-carry region width R063 is smaller than the A register value 31 in S307 (determination Yes), the lower half
If the area includes a carry boundary and is not small (judgment N
o), the upper half area includes the carry area. When the lower half area is truncated (determination Yes),
In S384, the C register value (effective area lower limit value) 30A is changed to A.
Only the register value (effective area width) 31 is updated. Before the output of the sign byte, the double enlargement (normalization process) which is performed immediately after the BYTEOUT process is originally performed.
In 5, the BYTEOUT processing is performed instead of the BYTEOUT processing.
7 processing is called.

FIG. 9 is a flowchart for explaining the detailed processing of the BYTEOUT processing. This BYTEOUT
70 shows a change of FIG. 69 (flow describing the BYTEOUT processing) of the 7 processing. The correction in S151 "and S157" is based on the fact that the code output position has been moved one bit higher. The correction in S158 'is based on the fact that the processing (S382) corresponding to the normalization has already been performed in FIG.

FIG. 10 is a diagram showing an example of H for performing a half area truncation process.
It is a flowchart explaining an ALVINGD process.
The code register variable name C30A has been changed to D64 in the ROUNDDOWN processing of FIG.
1 to S395 correspond to S381 to S385, and the code register 30 of the encoder is stored in the code register C30B of the decoder.
S3 for performing processing corresponding to A (register D64)
96 and S397. Finally, FIG.
The BYTEIN7 process is called in S395 instead of the YTEOUT7 process (S385).

FIG. 11 is a flowchart for explaining the detailed processing of the BYTEIN7 processing. This BYTEIN
FIG. 74 of 7 processing (flow explaining BYTEIN processing)
Indicates a change to Modification of S273 'and S276'
This is due to the fact that the code input position has moved up by one bit. The correction in S274 ′ is based on the fact that the processing (S392, S396) corresponding to normalization has already been performed in FIG.

According to the above-described first embodiment, it is only necessary to determine whether the carry boundary exists in the upper half or the lower half area. Therefore, the carry area width R162
Does not need to be calculated.

Embodiment 2 In the QM-coder shown in the above-mentioned first conventional example, a code that has been output but has not been determined is made to wait in the variable BUFFER 51 and the SC counter 52. However, depending on the specifications of the encoder, during encoding, Overflow of the SC counter 52 may occur, and as a result, a code byte (0xFF or 0x00) is lost for each overflow in the maximum number of counts,
An accurate code cannot be output.

In general, the final image size is not always known in advance, but if processing is performed in units of stripes (or lines) divided by a finite size, the worst code amount can be estimated. It is known that the worst case in arithmetic coding is a bit more than one bit. Therefore, the specification of the SC counter 52 that should be almost prepared for the divided stripe (or line) configuration size (the number of bytes) is as follows. Can be determined and its double sign byte 0xF
It is enough to be able to count the runs of F. In the second embodiment, each time a stripe is completed, the code bytes waiting to be output are forcibly determined and swept out, so that the maximum determination delay can be estimated to be about the stripe encoding processing time. Become. It is assumed that a half area truncation method is applied as a method for determining the code byte.

In the adaptive area truncation method shown in the second conventional example described above, it is possible to sequentially perform output if only one code byte is put on standby. In order to suppress the code length loss, the position of the carry boundary in the effective area must be strictly calculated. Therefore, the decoder cannot perform accurate decoding unless the code register 30A of the encoder is reproduced. . Further, if the execution of the adaptive area truncation processing is not synchronized with the byte input / output timing of the encoder and the decoder by deleting the Cs register 33, it is necessary to prepare another dedicated synchronization means. The decoding load increases. For example, in order to synchronize the encoder and the decoder without deleting the Cs register 33, the encoder is provided with a counter of the number of normalized shifts as the dedicated synchronization means, and synchronizes every 8 bits (when a multiple of 8). What is necessary is just to consider it as timing or to reproduce the CT counter 50 for decoding.

In the second embodiment, the restriction on the synchronization due to the presence or absence of the Cs register 33 can be eliminated by performing the half area truncation processing at the end timing of the stripe. Further, even when there is no carry boundary in the effective area without depending on the code byte value output from the C register 30A, the half area truncation processing is always performed,
In the decoder, the code (C) is used without reproducing the code register 30A of the encoder and without strictly calculating the carry boundary.
Register value) upper or lower 1 not indicated by 30B
Accurate decoding can be performed by truncating the / 2 region.

Here, the encoder determines the half area to be truncated as described above and updates the effective area, which can be regarded as dummy symbol encoding. Also, the decoder updates the effective area to the half area indicated by the code, which can be regarded as decoding a dummy symbol,
The symbol may be ignored regardless of whether the effective area is updated to upper or lower.

In the half area truncation method according to the second embodiment, even if no code bit is generated in the stripe encoding process, a one-bit code is generated by the half area truncation. For this reason, a 1-byte code can be output in the worst 8 stripes while suppressing overflow of the SC counter 52, and the required time can be estimated as the maximum delay until the code is determined.

The encoder for arithmetic coding of the half-area truncation method is referred to as an encoder 1C, and the decoder thereof is referred to as a decoder 16C. FIGS. 12 and 13 show schematic configurations of the encoder and the decoder.
In FIG. 12, an encoding unit 1D associated with the replacement of the arithmetic encoder 13D and the code 4D is configured corresponding to FIG. 39 of the first conventional example. In FIG. 13, an arithmetic decoder 17D and a decoding unit 16D accompanying the replacement of the code 4D are different from FIG. 40 of the first conventional example. The data flow between the blocks in which these are replaced, and the learning method are the same as those in FIGS. 39 and 40 of the first conventional example.

The arithmetic encoder 13D performs the encoding operation in the C register 30A and the A register 31 from the input of the LSZ value 9 and the binary symbol 14, and measures the code output timing in byte units by the CT counter 50. In the same manner as in the conventional example 1, the BUFFER 51 and the SC counter perform an undetermined code output standby with a possibility of carry propagation and a determined code output, and output a code 4D. Then, in synchronization with the detection of the end of the line (or the end of the stripe), the presence / absence of a carry boundary in the area is determined by the T register 65 and the CW register 6.
6 and apply a 1/2 area truncation method of truncating the selected upper or lower 1/2 truncated area,
The register 30A and the A register 31 are modified to forcibly determine the presence or absence of a carry, carry-carrying is performed up to a maximum of BUFFER 51, the determined code is output, and a code 4D is output.

The arithmetic decoder 17D measures the code input timing in byte units by the CT counter 50 from the input of the LSZ value 9 and the code 4D, and performs the decoding operation by the C register 30B and the A register 31 via the BUFFER 51. And outputs a binary symbol 14. Then, C is synchronized with the detection of the line end (or the stripe end).
A half area truncation method of truncating a half truncated area on the side not pointed to by the register 30B is applied, and the C register 30B and the A register 31 are modified.

Detailed processing operations in and between the constituent blocks shown in FIGS. 12 and 13 are described in the first section.
47 is a flowchart for explaining the processing of the conventional example of FIG.
55 to FIG. 57 and FIG. 57 to FIG. 62, and flowcharts 14 to 19 for explaining the processing described later. Embodiment 2
FIG. 14 and FIG. 18 show a case where the half area truncation method is applied at the end of a stripe.

An example of the half area truncation method according to the second embodiment is the QM-Co method described in the first conventional example.
A description will be given by adding only necessary modifications to the flowchart for explaining the der encoding / decoding process. 45 for the encoding / decoding / region width register, FIGS. 47 to 55 for the encoder, and FIGS. 57 to 62 for the decoder,
This is the same as the flow describing the processing of the first conventional example. For the sake of explanation, the variables additionally introduced in the first conventional example are a half area boundary value T65 of the effective area, a variable CT
The carry boundary value CW66 defined by the value 50.

FIG. 14 is a flowchart for explaining the ENCODER process showing the entire flow of the encoding process.
A call (S107) of the HALVING process for performing the half area truncation process is added between the stripe end determination (S104) and the image end determination (S105) in FIG.

FIG. 15 is a diagram showing H for performing a half area truncation process.
It is a flowchart explaining an ALVINGE process.
Steps S501 and S502 correspond to normalization processing for the C register 30A and the CT counter 50, and the A register 31 is kept as it is. S503 and S504 are 1/1 of the effective area.
A carry boundary value CW66 defined by a two-region boundary value T65 and a CT counter value 50 is set. In S505, 1 /
A comparison is made between the two-region boundary value T65 and the carry boundary value CW66. If the determination result is Yes, the carry boundary is the upper 1 /
Since there are two or more areas, a code byte in standby without carry propagation is output, and a CODELOWER process in which the lower half area is an effective area is called (S506). If the determination result is No, since the carry boundary exists in the lower half area or less, the code byte in the standby state after the carry propagation is output, and the upper half area is set as the effective area.
The PPER process is called (S507). Finally, S50
If the variable CT50 is 0 in step 8, the buffer in step S509 is BUFFER.
51, and the Cb register value 34 is BUed in S510.
FFER 51 is set, and the Cc register unit 35 is set in S511.
And Cb register section 34 are cleared and CT is performed in S512.
8 is set in the counter 50. Here, already S506
Alternatively, in S507, the presence or absence of a carry is determined, and if there is a carry, a propagation process is also performed (the Cc register unit 35 = 0 after the propagation), and the waiting code byte is completed (after the variable SC value 52 is released). = 0), and S509
From S512, S161 and S164 (TEMP =
Cb register value), S157 and S158. S
In 510, there is no problem even if BUFFER 51 becomes byte 0xFF.

FIG. 16 shows a CODE in which the upper half area is truncated and the output standby code is cleared without carry.
It is a flowchart explaining a LOWER process. S5
If the variable SC value 52 is positive in S21, BUFF in S522
Write out ER51. Further, the variable SC value 5 in S523
If 2 is greater than 1, sign byte 0xFF in S524
Is written (SC-1) times. In S525, 0xFF which is the last standby code byte is set in BUFFER 51,
At 526, the variable SC value 52 is set to 0.

FIG. 17 shows a CODE in which the lower half area is truncated and the output standby code with carry is swept out.
It is a flowchart explaining an UPPER process. S5
At 31, the carry is propagated to the BUFFER 51, and the carry is carried out from the C register 30 A (carry boundary value CW66).
Clear If the variable SC value 52 is positive in S533,
In S534, BUFFER 51 is written out. Further, S5
If the variable SC value 52 is greater than 1 at 35, the code byte 0x00 is written out (SC-1) times at S536. S53
7. BUFFE 0x00 which is the last wait code byte
R51 is set, and the variable SC value 52 is set to 0 in S537.

FIG. 18 is a diagram showing the overall flow of the decoding process.
It is a flowchart explaining an ECODER process. A call (S216) of the HALVINGD process for performing a half area truncation process is added between the stripe end determination (S214) and the image end determination (S215) in FIG.

FIG. 19 shows H for performing half area truncation processing.
It is a flowchart explaining an ALVINGD process.
S541 and S542 correspond to normalization processing for the C register 30B and the CT counter 50, and the A register 31
Keep as it is. At S545, the CHIGH register value is 38.
Is compared with the A register value 31. If the determination result is Yes, the lower half area has been truncated and S546
Subtracts the A register value 31 from the CHIGH register value 38. If the determination result is No, it means that the lower half area has been truncated. Finally, if the variable CT50 is 0 in S547, the BYTEIN process is called.

However, the carry boundary value CW66 is １ ／.
When the area is equal to the area boundary T65, either the upper half or the lower half may be used. In 82, STUFF immediately after the code byte 0xFF
Since the transmission (control of the marker code) is performed by inserting the byte (0x00), the final code length may be shorter when the carry is propagated.

Here, it is assumed that the specification of the SC counter 52 to be prepared can be determined for the stripe (or line) configuration size (the number of bytes) that divides the image. However, when the specification of the SC counter 52 cannot be changed, What is necessary is just to set the stripe (or line) configuration size that cannot overflow.

Embodiment 3 Although the maximum delay in the second embodiment is eight stripes, when no code bit is generated, the presence or absence of a carry remains resolved. Therefore, if the half area truncation processing is not performed, the code is determined. However, it is also possible to suppress the overflow of the SC counter 52 while preventing the generation of an extra code bit in the code due to the half area truncation processing. In the third embodiment, as an example, E described in the second embodiment is used.
Flow for explaining NCODER processing (FIG. 14), DEC
It is assumed that the flow (FIG. 18) for explaining the ODER process is replaced with FIGS.

FIG. 20 is a flowchart for explaining the ENCODER process showing the entire flow of the encoding process.
In FIG. 14, normalization processing is performed during the stripe encoding processing between the stripe end determination (S104) and the HALVING processing call (S107) for performing 1/2 area truncation processing (whether a code bit is generated). ) Is added (S108), and only when it is performed,
Performs region truncation processing.

FIG. 21 is a flowchart showing the overall flow of the decoding process.
It is a flowchart explaining an ECODER process. The stripe end determination (S214) in FIG.
During the calling of the HALVINGD process for performing the two-region truncation process (S216), a determination (S217) as to whether or not the normalization process was performed (the sign bit was read) during the stripe decoding process was added. Only when this is done, the half area truncation processing is performed.

Here, if the configuration specification of the code register C30A is the same as that of the first embodiment, the byte input / output of the encoder / decoder can be synchronized. Of code byte input / output during line processing for the execution of half area truncation processing due to (eg, detection of the execution presence / absence flag or increase in the number of code bits)
It is also possible to carry out. In this case, even if a normalization process of less than several bits up to the byte input / output occurs, the half area truncation process is not performed, and an extra sign bit associated with it can be reduced.

Embodiment 4 In the second embodiment, when the image is divided into stripes and encoded / decoded, the initialization / post-processing of the encoder / decoder is performed only once. In the fourth embodiment, 領域 area truncation processing is performed for each line processing, and initialization processing and post-processing of an encoder / decoder are performed for each stripe processing. Here, in the post-processing of the encoder (flow for explaining the FLUSH processing), a processing of determining and sweeping out an undetermined code is performed. / 2 area truncation processing is performed. In the fourth embodiment, as an example, the flow for explaining the ENCODER process (FIG. 14) and the flow for explaining the DECODER process (FIG. 18) described in the second embodiment are replaced with FIGS. .

FIG. 22 is a flowchart for explaining the ENCODER process showing the entire flow of the encoding process.
By adding a line end determination (S109) to FIG. 14, the stripe end determination (S104)
By reconstructing the end judgment of the image (S105), the half area truncation processing (S107) is executed for each line, the initialization processing (S101), and the post-processing (S106) are executed for each stripe. .

FIG. 23 is a diagram showing the overall flow of the decoding process.
It is a flowchart explaining an ECODER process. By adding the line end determination (S218) to FIG. 18, the stripe end determination (S214) and the image end determination (S215) are reconstructed, so that the half area truncation processing ( S216), and the initialization process (S211) is performed for each stripe.

As described above, by performing the 領域 region truncation processing for each line, the code definite delay becomes a maximum of 8 lines as in the second embodiment, and the initialization processing and post-processing are performed. The code will be completed for each stripe.

Embodiment 5 FIG. In the third embodiment, when an image is divided into stripes and encoded / decoded, the initialization / post-processing of the encoder / decoder is performed only once. In the fifth embodiment, １ ／ area truncation processing is performed for each line processing, and initialization processing and post-processing of an encoder / decoder are performed for each stripe processing. In the fifth embodiment, as an example, the flow for explaining the ENCODER process (FIG. 20) and the flow for explaining the DECODER process (FIG. 21) described in the second embodiment are replaced with FIGS. I do.

FIG. 24 is a flowchart for explaining the ENCODER process showing the entire flow of the encoding process.
By adding a line end determination (S109) to FIG. 20, stripe end determination (S104),
By reconstructing the end judgment of the image (S105), the half area truncation processing (S107) is executed for each line, the initialization processing (S101), and the post-processing (S106) are executed for each stripe. .

FIG. 25 is a diagram showing the entire flow of the decoding process.
It is a flowchart explaining an ECODER process. By adding the line end determination (S218) to FIG. 21, the stripe end determination (S214) and the image end determination (S215) are reconstructed, so that the half area truncation processing ( S216), and the initialization process (S211) is performed for each stripe.

As described above, by performing the 領域 area truncation processing for each line, the code definite delay is larger than that in the fourth embodiment, as in the third embodiment.
An extra code bit is not generated in the code while suppressing the overflow of the SC counter 52. Further, by performing the initialization processing and the post-processing in the same manner as in the fourth embodiment, the code is completed for each stripe.

Embodiment 2 to Embodiment 5
Performs the synchronization of the half area truncation processing in the encoder and the decoder in units of stripes and lines.
For example, it may be any other unit that can be synchronized, such as a block or a sub-block. Further, the data does not necessarily have to be an image.

Embodiment 6 FIG. In the sixth embodiment, for example, when a code is output in byte units, when the same byte value is continuous in the code, the continuation of the byte value is replaced with another byte group indicating the byte value and its length. A method for reducing the total code length and the output time by the above will be described. Hereinafter, it is assumed that a byte group to be replaced here is called a run length marker, and can be extended to an arbitrary length by a predetermined instruction method to express a numerical value.

As shown in FIG. 26, for example, a sequence of four bytes 0xFF is used.
And byte MK indicating that four 0xFFs follow
In this example, 8 bytes are replaced with 2 bytes in addition to the STUFF bytes inserted to secure the ESC code. In (2), byte MK is 0xFF
And the length is specified in bytes RL
This is an example of replacing with 3 bytes. Also, in the case where 0x00 continues, the byte MK indicating that 0x00 continues is replaced with a byte RL if necessary. Here, it is assumed that the byte MK is assigned a value that can identify the byte value to be replaced and its length.

As shown in FIG. 27, a run-length marker in which seven bytes 0xFF are replaced is, for example, two run-length markers indicating four and three replacements, or two and three run-length markers. Two run-length markers indicating two replacements are equivalent, and a combination in which the total of other run lengths is equal can be said to be equivalent.

If the run length marker is represented by an ESC code (0xFF) followed by a byte MK as shown in FIG. 28, for example, the byte MK is composed of (8-N) bits of the identification part of the replacement target byte and N It consists of a bit run length part. In this case, the replacement target byte is 2 (8
-N) A power type can be specified, and the run length of the replacement target byte up to 2 N can be indicated.

However, according to International Standard Recommendation T. In 82, since other marker segments are defined, not all values that can be specified in the identification unit can be used. In addition, since marker segments may be separately used in other international standard recommendations, when the run-length markers are used here, it is necessary not to overlap with all the marker segments.

The run-length marker is, for example, as shown in FIG.
As shown in FIG. 9, if an ESC code (0xFF), a byte MK following the ESC code, and a run length portion RL of a predetermined S byte are used, all 8 bits of the byte MK become an identification portion of a replacement target byte. In this case, 255 types of bytes to be replaced (excluding MK = STUFF) can be designated, and the run length of the bytes to be replaced can be shown up to 2 (8 × S).

Further, as shown in FIG. 30, for example, the run length marker is an ESC code (0xFF) followed by a byte MK and a run length portion RL of S bytes.
, The byte MK is composed of an (8-N) -bit replacement target byte identification unit and an N-bit run length instruction unit. In this case, the replacement target byte is 2 (8-
N) The type of the power can be specified, and the byte length of the run-length portion up to 2 N bytes can be indicated. And 2
To the (8 × S) power can be indicated.

FIGS. 28 to 30 show examples of the run length marker. When the byte to be replaced cannot be indicated by the byte MK, the start of the run length marker is determined by the ESC and the byte MK, and the fixed length or the byte MK is used. There is also a method of directly specifying the replacement target byte by placing it before or after the run length part in the run length part of the specified length. According to this method, if only the run-length marker is recognized by the byte MK with respect to the other marker segments, all of the replacement target bytes can be used regardless of the value.

For a repetition of a plurality of bytes, for example, there is a method in which the byte MK indicates the byte length of the pattern to be replaced, and the pattern is directly specified together with the run length of the pattern (the number of repetitions).

An example is shown in FIG. 31 (a), which is composed of a marker MK including an ESC code (0xFF) and an identification section, a replacement target pattern section PT composed of a plurality of bytes, and a run length section RL. . Here, the marker MK
Is the field length (value P) of the pattern portion PT to be replaced,
If the field length (value R) of the run-length part RL is specified, the P-byte replacement target pattern PT is repeated RL times represented by R bytes.

As a specific example, when the 2-byte patterns 0x01 and 0x23 repeated three times are replaced with run-length markers, a marker having a field length P of the pattern portion to be replaced is 2 and a field length R of the run-length portion is 1 Using MK, it is shown as in FIG.

In the marker MK, the two field length parts other than the run-length marker identification part may be independent of the byte including the identification part. Also, the field length part and the run length part R of the pattern part PT to be replaced
The field length portion of L, the pattern portion to be replaced PT, and the run-length portion RL are not limited to the above example and can be freely arranged as long as the recognition is identical between the encoder and the decoder.

Since the run length of the replacement target byte indicated by the run length marker is never 0, whether 0 represents the maximum value or whether the actual (run length-1) is always embedded in the run length portion It is necessary to arrange.

Here, 0xFF or 0
x00 consecutive SC byte output (BYTEOUT
S154, S162 of the flowchart for explaining the processing,
Regarding S204 and S208 in the flowchart describing the FINALWRITES process, S524 in the flowchart describing the CODELOWER process, and S536 in the flowchart describing the CODEUPPER process,
For example, as shown in FIG. 32, the process for replacing with a run-length marker can be easily executed in the flowchart describing the RUNLENMARK process. Here, it is assumed that the encoder and the decoder determine in advance which type of the run-length marker shown in FIGS. 28 to 30 is to be used. The maximum value that can be indicated in the run length part of the run length marker to be used is a constant MA
RKLEN80. For example, in FIG.
If it is 4, the constant MARKLEN80 will be 16.

In FIG. 32, RL81 is a counter variable for replacing SC 52 bytes. S60
At 1, the variable SC value 52 is set to the variable RL81. S
If the variable RL value 81 is larger than the constant MARKLEN80 in 602, a run length (RL) marker indicating the replacement target byte for the length MARKLEN80 is written in S603, and the variable RL81 is converted from the variable RL81 to the constant MARKL in S604.
Reduce EN80. In step S602, the variable RL value 81 is a constant M
If it does not become larger than ARKLEN80, finally S60
In 5, a run length (RL) marker indicating the replacement target byte having the remaining length of the variable RL value 81 is written, and the variable RL value 81 is set to 0 in S 606.

According to the flowchart for explaining this processing, when the run-length markers are divided and output continuously, the run-length markers are output from those having the maximum length, and finally those having a length less than the maximum value are output. As shown in FIG. 27, the output order does not have to be used. Also, the replacement target byte does not necessarily need to be 0x00 or 0xFF, and any continuous code byte may be replaced by monitoring the code output.

If the number of bits in the run length part of the run length marker is equal to or greater than the number of bits in the SC counter 52,
It is possible to specify the run length instruction with only one run length marker.

The replacement target byte is not necessarily a byte, but may be a multibyte unit such as a word or a double word, or may be a single byte or a plurality of bytes by appropriately selecting a run length marker to be replaced. Can be targeted.

Embodiment 7 FIG. According to the sixth embodiment, all the replacement target bytes whose run length is the variable SC value 52 are replaced by the run length marker. In Embodiment 7, in FIG. 33, it is assumed that the replacement target byte can be output as it is without replacing a part of the run length with the run length marker. Here, the number of bytes constituting the run length marker is set to a constant MARK.
LENMIN82. For example, in FIG. 28, the constant MARKLENMIN is 2.

FIG. 34 is a flow chart for explaining a RUNLENMARK process for replacing a run-length marker. In FIG. 34, from S601 to S604
In S606, the same processing as in FIG. 32 is performed.
In step S607, the variable RL value 81 is set to the constant MARKLEN.
If the value is equal to or more than MIN82, a run length (RL) marker indicating the replacement target byte whose length is the variable RL value 81 is written in S605. Just write out.

As described above, if the run length of the replacement target byte is smaller than the number of bytes constituting the run length marker, the replacement target byte is output as it is by the length of the run without replacing the run length marker with the run length marker. Can be shortened. If the lengths are the same regardless of the output,
It may or may not be replaced.

However, the replacement target byte is byte 0xFF
In the case of, since the STUFF byte is inserted when not replaced and the code length is doubled, the length determination should be considered so as to be shorter.

Embodiment 8 FIG. In the sixth embodiment or the seventh embodiment, when the run-length marker is used, as shown in FIG. 35, information for notifying the use can be included in the output code.

When used at all times, it is not necessary to notify the use of the run-length marker. For example, the format of the run-length marker, the type of the byte to be replaced, and the length of the run-length part shown in FIGS. For some or all of them, the operation mode can be unified by notifying the decoder of the additional information in advance from the encoder.

Further, the encoder confirms the processing capability implemented in the decoder prior to encoding (negotiation),
The applied mode information may be notified from the result. As the capability of the decoder, for example, there is a limit value such as the number of digits of a counter of a run-length unit for performing an inverse transform of a run-length marker.

Further, in this case, the decoder can regard code data not containing the run-length marker use notification as a code generated by a conventional encoder.
If the decoder is a conventional decoder, the encoder does not need to insert the run-length marker use notification into the code and does not need to use the run-length marker.

Embodiment 9 FIG. In order to use the run-length marker shown in the sixth embodiment or the seventh embodiment in a conventional encoder and a conventional decoder, the run-length marker is used between a conventional encoder and a line (communication path) or a line (communication path). Communication can be made possible by inserting an adapter between the communication channel) and the conventional decoder.

First, as shown in FIG. 36, the adapter (run-length marker converter) on the encoder side distinguishes the code from the data, and monitors the code byte. Is changed to SC again.
The processing is replaced with a run-length marker according to the flowchart describing the processing of FIG. The adapter (run-length marker inverse transformer) on the decoder side also discriminates the code from the data in the same manner, and when the run-length marker is detected while monitoring the code byte, the specified replacement target byte is detected. Output continuously for a long time.

As shown in FIG. 37, when there is no run-length marker inverse transformer on the decoder side, the encoder passes the code as it is without substantially using the run-length marker transformer. As shown in (1), when there is no run-length marker converter on the encoder side, the decoder uses the run-length marker inverse transformer and practically does not use the run-length marker. Compatibility with can be maintained.

Here, the adapter (run-length transformer / inverter) connected to the conventional encoder / decoder may have an appearance independent of the encoder / decoder.
It may be an integral configuration.

As described above, the encoding and decoding processes are as follows.
A facsimile device, a scanner device, a printer device, a computer, a database device, which stores data inside a computer or a device, and exchanges data with the outside by wireless or wired communication or a storage medium via a public line or a dedicated line, Image display devices, image storage devices,
The present invention can be applied to hardware such as a data storage device, an image transmission device, and a data transmission device. Further, a function equivalent to each of the above-described devices can be realized by software and a part of hardware on a general-purpose computer, and the appearance of the devices may be integrated or may be independent of a plurality of devices. Furthermore, the inside of the dedicated hardware is not limited to a mounting form using an LSI (semiconductor chip) or middleware equipped with these processing functions. Communication is not limited to electrical or optical wireless or wired, public or private lines, or communication formats such as LAN, WAN, Internet, and intranet. The recording format on the storage medium is not limited to a magnetic, electrical, optical, digital or analog recording format, and the recording medium is limited to whether it is fixed to the device or separated. Not something. Further, a recording format using ink or the like may be used regardless of whether or not the visual permission is given.

In the present invention, the block diagram and the flow chart have been described as being applied to image coding. However, it goes without saying that the present invention can also be used for general data coding.

[0177]

As described above, according to the present invention, it is possible to eliminate the overflow of the counter for storing the code length which waits until the code is determined, and to forcibly determine the code at appropriate intervals. Thus, the carry can be controlled to make the code definite delay time finite and estimated. In addition, when the code value is determined, the total code length and code sweeping time can be reduced by replacing the code value with a predetermined pattern.

In addition, the carry control can be performed without strictly calculating the carry boundary, and the carry control can be performed without reproducing the code register of the encoder by the decoder. Can be

[Brief description of the drawings]

FIG. 1 is an explanatory diagram of an upper / lower half area truncation method according to the concept of the present invention.

FIG. 2 is a block diagram illustrating a configuration of an encoding unit according to Embodiment 1 of the present invention.

FIG. 3 is a block diagram showing a configuration of a decoding unit according to Embodiment 1 of the present invention.

FIG. 4 is a diagram showing a ROUNDD according to the first embodiment of the present invention;
It is a flowchart explaining an OWNE process.

FIG. 5 shows HALVIN according to Embodiment 1 of the present invention.
It is a flowchart explaining a GE process.

FIG. 6 shows a ROUNDD according to the first embodiment of the present invention.
It is a flowchart explaining an OWND process.

FIG. 7 shows HALVIN according to Embodiment 1 of the present invention.
It is a flowchart explaining a GD process.

FIG. 8 shows HALVIN according to the first embodiment of the present invention.
It is a flowchart explaining a GE process.

FIG. 9 shows a BYTEOU according to the first embodiment of the present invention.
It is a flowchart explaining a T7 process.

FIG. 10 shows a HALVI according to the first embodiment of the present invention.
It is a flowchart explaining an NGD process.

FIG. 11 shows a BYTEI according to the first embodiment of the present invention.
It is a flowchart explaining an N7 process.

FIG. 12 is a block diagram showing a configuration of an encoding unit according to Embodiment 2 of the present invention.

FIG. 13 is a block diagram showing a configuration of a decoding unit according to Embodiment 2 of the present invention.

FIG. 14 is an ENCODE according to Embodiment 2 of the present invention;
It is a flowchart explaining an ER process.

FIG. 15 shows a HALVI according to the second embodiment of the present invention.
It is a flowchart explaining an NGE process.

FIG. 16 is a CODEL according to a second embodiment of the present invention.
It is a flowchart explaining an OWER process.

FIG. 17 is a CODEU according to Embodiment 2 of the present invention;
It is a flowchart explaining a PPER process.

FIG. 18 shows a DECOD according to the second embodiment of the present invention.
It is a flowchart explaining an ER process.

FIG. 19 shows a HALVI according to the second embodiment of the present invention.
It is a flowchart explaining an NGD process.

FIG. 20 shows ENCODE according to Embodiment 3 of the present invention;
It is a flowchart explaining an ER process.

FIG. 21 is a DECOD according to the third embodiment of the present invention.
It is a flowchart explaining an ER process.

FIG. 22 is an ENCODE according to Embodiment 4 of the present invention.
It is a flowchart explaining an ER process.

FIG. 23 shows a DECOD according to a fourth embodiment of the present invention.
It is a flowchart explaining an ER process.

FIG. 24 is an ENCODE according to Embodiment 5 of the present invention.
It is a flowchart explaining an ER process.

FIG. 25 shows a DECOD according to the fifth embodiment of the present invention.
It is a flowchart explaining an ER process.

FIG. 26 is an explanatory diagram of a run-length marker according to Embodiment 6 of the present invention.

FIG. 27 is an explanatory diagram of a run length marker divided output according to the sixth embodiment of the present invention.

FIG. 28 is a configuration diagram showing an example of a run-length marker according to Embodiment 6 of the present invention.

FIG. 29 is a configuration diagram showing an example of a run-length marker according to Embodiment 6 of the present invention.

FIG. 30 is a configuration diagram showing an example of a run-length marker according to Embodiment 6 of the present invention.

FIG. 31 shows a byte MK according to Embodiment 6 of the present invention.
FIG. 4 is a diagram illustrating a byte length of a pattern to be replaced, and a method of directly specifying a pattern together with a run length of the pattern.

FIG. 32 shows a RUNLE according to Embodiment 6 of the present invention.
It is a flowchart explaining an NMARK process.

FIG. 33 is an explanatory diagram relating to a comparison of run-length marker code lengths according to Embodiment 7 of the present invention.

FIG. 34: RUNLE according to Embodiment 7 of the present invention;
It is a flowchart explaining an NMARK process.

FIG. 35 is an explanatory diagram of information for notifying the application of the run-length marker according to the eighth embodiment of the present invention.

FIG. 36 is a block diagram showing an example of a configuration for performing mutual communication between an encoder and a decoder using a run-length marker according to Embodiment 9 of the present invention.

FIG. 37 is a block diagram showing an example of a configuration for performing mutual communication between an encoder and a decoder using a run-length marker according to Embodiment 9 of the present invention.

FIG. 38 is a block diagram showing an example of a configuration for performing mutual communication between an encoder and a decoder using a run-length marker according to Embodiment 9 of the present invention.

FIG. 39 is an explanatory diagram showing the concept of conventional arithmetic coding.

FIG. 40 is an explanatory diagram of a conventional normalization process for always keeping the decimal part at the accuracy of area division and sweeping out the upper digits to the integer part.

FIG. 41 is a block diagram showing a configuration of an encoder according to a first conventional example.

FIG. 42 is a block diagram illustrating a configuration of a decoder according to a first conventional example.

FIG. 43 is an explanatory diagram of a standard model template.

FIG. 44 is an explanatory diagram of a probability estimation table.

FIG. 45 is a configuration diagram of an encoding / decoding / region width register.

FIG. 46 is a flowchart illustrating an ENCODER process according to a first conventional example.

FIG. 47 is a flowchart illustrating an ENCODE process according to the first conventional example.

FIG. 48 is a flowchart illustrating a CODELPS process according to a first conventional example.

FIG. 49 is a flowchart illustrating CODEMPS processing according to a first conventional example.

FIG. 50 is a flowchart illustrating a RENOME process according to a first conventional example.

FIG. 51 is a flowchart illustrating BYTEOUT processing according to a first conventional example.

FIG. 52 is a flowchart illustrating an INITENC process according to a first conventional example.

FIG. 53 is a flowchart illustrating a FLUSH process according to a first conventional example.

FIG. 54 is a flowchart illustrating a CLEARBITS process according to a first conventional example.

FIG. 55: FINAL WRITE according to the first conventional example
It is a flowchart explaining S processing.

FIG. 56 is a flowchart illustrating a DECODER process according to a first conventional example.

FIG. 57 is a flowchart illustrating a DECODE process according to a first conventional example.

FIG. 58: LPS_EXCHAN according to the first conventional example
It is a flowchart explaining a GE process.

FIG. 59: MPS_EXCHAN according to the first conventional example
It is a flowchart explaining a GE process.

FIG. 60 is a flowchart illustrating a RENORMD process according to a first conventional example.

FIG. 61 is a flowchart illustrating a BYTEIN process according to a first conventional example.

FIG. 62 is a flowchart illustrating an INITDEC process according to a first conventional example.

FIG. 63 is an explanatory diagram of a carry / non-carry area truncation process according to the second conventional example.

FIG. 64 is a block diagram illustrating a configuration of an encoder according to a second conventional example.

FIG. 65 is a block diagram showing a configuration of a decoder according to a second conventional example.

FIG. 66 is a configuration diagram of an encoding / region width register according to a second conventional example.

FIG. 67 is a flowchart illustrating a RENOME process according to a second conventional example.

FIG. 68: ROUNDDOWN according to a second conventional example.
It is a flowchart explaining a process.

FIG. 69 is a flowchart illustrating BYTEOUT processing according to a second conventional example.

FIG. 70 is a flowchart illustrating an INITENC process according to a second conventional example.

FIG. 71: FINAL WRITE according to a second conventional example
It is a flowchart explaining S processing.

FIG. 72 shows LPS_EXCHAN according to a second conventional example.
It is a flowchart explaining a GE process.

FIG. 73 is a flowchart illustrating a RENORMD process according to a second conventional example.

FIG. 74: ROUNDDOWN according to a second conventional example
It is a flowchart explaining a process.

FIG. 75 is a flowchart illustrating a BYTEIN process according to a second conventional example.

FIG. 76 is a flowchart illustrating INITDEC processing according to a second conventional example.

[Explanation of symbols]

1A encoding unit, 1B decoding unit, 2 context CX,
3 pixel PIX, 4 codes, 5 data memory, 6 images, 7 predicted value table MPS, 8 state table ST, 9 LPS area width table LSZ, 10 MPS
State transition destination table NMPS, 11 LPS State transition destination table NLPS, 12 Predicted value inversion determination table SW
TCH, 13A arithmetic encoder, 13B arithmetic decoder, 1
4 symbols, 15A Pixel symbol converter, 15B
Symbol pixel converter, 16 predicted value update processor, 17
State update processor, 18 state table STAT
E, 19 Non-predicted value table LPS, 30A Encoding register (lower bound) C, 30B Decoding register C, 31
Area width register A, 32 Cx register, 33 Cs register, 34 Cb register, 35 Cc register, 3
6 CLOW register, 37 Cb register, 38 C
HIGH register, 39 Cx register, 50 CT counter, 51 code buffer BUFFER, 52 SC
Counter, 53 Output determination buffer TEMP, 60 Upper bound value U, 61 Carry boundary T, 62 Carry region width R1, 63 Non-carry region width R0, 64 Code register D (of decoder), 65 1/2 region Boundary value T, 66
Carry boundary value CW, maximum value of run length part 80 M
ARKLEN, 81 Run length counter RL, 82
Run length marker length MARKLENMIN.

 ────────────────────────────────────────────────── ─── Continuing on the front page (72) Inventor Fumitaka Ono 2-3-2 Marunouchi, Chiyoda-ku, Tokyo F-term within Mitsubishi Electric Corporation (reference) 5C059 KK15 ME05 ME11 UA02 UA05 UA34 UA38 5C078 BA21 CA31 DA00 DA01 DA02 DA06 DA11 5J064 AA02 BA08 BA10 BB09 BB12 BC01 BC02 BC04 BC14 BC17 BC28 9A001 BB03 EE04 HH05 HH27 JJ71 KK54

Claims (29)

[Claims] 1. A data memory for storing information source data and outputting encoding target data and its auxiliary parameters (context), and learning data on the encoding target data specified based on the auxiliary parameters. A learning memory that accumulates and outputs, a probability estimation table that outputs an encoding parameter specified based on the learning data, and outputs a code by performing arithmetic encoding based on the encoding target data and the encoding parameter. A synchronization detector that measures and notifies the input processing of the information source data in a predetermined unit or the output of the code as a predetermined interval, and carries in the effective area at the predetermined interval. And a carry boundary detector that detects a boundary value and indicates a truncation region in the effective region based on the detection result. An encoding apparatus characterized in that the effective area is updated by cutting off one of partial areas obtained by equally dividing the effective area indicated by the carry detector into upper and lower parts. 2. The encoder according to claim 1, wherein when the carry boundary is detected by the carry boundary detector, the valid area indicated by the carry boundary detector is divided into upper and lower equal regions. 2. The encoding apparatus according to claim 1, wherein one of the effective areas is updated by truncating one of them. 3. The encoding apparatus according to claim 1, wherein the carry boundary detector instructs to cut off a partial region including the detected carry boundary. 4. The encoding device according to claim 1, wherein the predetermined interval is when a predetermined unit of data to be encoded is encoded. 5. The encoding apparatus according to claim 4, wherein the predetermined interval is set based on a maximum value of a code length for waiting until a code value is determined. 6. The encoding apparatus according to claim 4, wherein the encoder sets a maximum value of a code length to wait until a code value is determined based on the predetermined interval. 7. The encoding apparatus according to claim 1, wherein the predetermined interval is when a predetermined unit of code output is generated. 8. The encoding apparatus according to claim 1, wherein the predetermined interval is a time when a code output of a predetermined unit is generated and the code output value becomes a predetermined value. 9. The carry boundary detector indicates one of partial areas obtained by equally dividing the effective area into upper and lower parts even if no carry boundary is detected in the effective area. The encoding device according to claim 1, wherein: 10. The encoder according to claim 1, wherein the encoder has a run-length marker converter that replaces the determined code with a run-length marker capable of specifying a value and a length when the same value continues. 3. The encoding device according to 2. 11. The code according to claim 10, wherein the run-length marker converter does not perform the conversion when the code output is shorter than the run-length marker to be converted without being replaced. Device. 12. The encoder according to claim 1, wherein the maximum value of the continuous length extracted from the run-length marker is set by the encoder to the run-length marker converter based on a result of inverse transform of the run-length marker at the time of decoding. The encoding device according to claim 10, wherein: 13. A data memory for outputting auxiliary parameters (context) for data to be decoded, storing the decoded data to be decoded, and outputting the data as information source data, and the data memory specified based on the auxiliary parameters. A learning memory that accumulates and outputs learning data relating to decoding target data, a probability estimation table that outputs a decoding parameter specified based on the learning data, and an arithmetic decoding based on the decoding parameter and code, and the decoding target data A synchronization detector for measuring and notifying the output processing of a predetermined unit of information source data or the input of a code as a predetermined interval, And a carry boundary indicating a truncated area in the effective area based on the detection result. And a detector, the decoder decoding apparatus characterized by truncated one that does not include the code value of the partial regions obtained by equally dividing the effective area to the upper and lower updating the effective region. 14. The decoder, when a carry boundary is detected by the carry boundary detector, cuts off one of the partial areas, which does not include the code value, of the effective area into upper and lower equal parts. 14. The decoding device according to claim 13, wherein the valid area is updated. 15. The decoding apparatus according to claim 13, wherein the carry boundary detector instructs to cut off a partial region including the detected carry boundary. 16. The decoding apparatus according to claim 13, wherein the predetermined interval is when a predetermined unit of data to be decoded is decoded. 17. The decoding apparatus according to claim 13, wherein the predetermined interval is when a predetermined unit of code input occurs. 18. The decoding according to claim 13, wherein the predetermined interval is when a code input of a predetermined unit occurs and a code output value reproduced at the same time as decoding becomes a predetermined value. Device. 19. The apparatus according to claim 13, wherein said decoder has a run-length marker inverse transformer for inversely transforming to an original code value having a replaced length when a run-length marker is detected. A decoding device as described. 20. An encoding apparatus, comprising: a data memory for storing information source data and outputting encoding target data and auxiliary parameters (context) thereof; and an encoding target specified based on the auxiliary parameters. A learning memory that accumulates and outputs learning data relating to data, a probability estimation table that outputs an encoding parameter specified based on the learning data, and an arithmetic encoding based on the encoding target data and the encoding parameter. An encoder that outputs a performed code, a synchronization detector that measures and notifies the input processing of the information source data in a predetermined unit or the output of the code as a predetermined interval, and a carry boundary in the effective area at the predetermined interval. A carry boundary detector for detecting a value, and indicating a truncated area in the effective area based on the detection result. One of the partial areas obtained by equally dividing the effective area into upper and lower parts indicated by the beam detector is updated to update the effective area. In addition, as a decoding device, auxiliary parameters (context) for the decoding target data are set. A data memory for accumulating and outputting the decoded data to be decoded and outputting it as information source data, a learning memory for accumulating and outputting learning data relating to the data to be decoded specified based on the auxiliary parameter; A probability estimation table that outputs a decoding parameter specified based on data, a decoder that performs arithmetic decoding based on the decoding parameter and code and outputs the data to be decoded, and an output process of information source data in a predetermined unit Or a synchronization detector that measures and notifies the input of the code as a predetermined interval, and a digit in the effective area at the predetermined interval. And a carry boundary detector for indicating a truncated area in the effective area based on the detection result. The decoder includes: a partial area obtained by equally dividing the effective area into upper and lower parts. An encoding / decoding device characterized in that the effective area is updated by discarding one not including the code value. 21. The encoder, when a carry boundary is detected by the carry boundary detector, a partial area obtained by equally dividing the effective area designated by the carry boundary detector into upper and lower parts. When the carry boundary is detected by the carry boundary detector, the code value of a partial region obtained by equally dividing the effective region into upper and lower parts is detected when the carry boundary is detected by the carry boundary detector. 21. The encoding / decoding apparatus according to claim 20, wherein the valid area is updated by truncating one of the effective areas. 22. (a) a data storage step of storing information source data to output data to be encoded and its auxiliary parameters (context); and (b) the code specified based on the auxiliary parameters. A learning step of accumulating and outputting learning data relating to the data to be encoded; (c) a probability estimating step of outputting an encoding parameter specified based on the learning data; An encoding step of performing arithmetic coding based on the parameter and outputting a code, and (e) a synchronization detecting step of inputting information source data in a predetermined unit or measuring and outputting a code output as a predetermined interval and notifying; (F) detecting a carry boundary value in the effective area at the predetermined interval;
(G) one of partial areas obtained by equally dividing the effective area specified by the carry boundary detection step into upper and lower parts, and (g) a carry boundary detection step for designating a truncated area in the effective area based on the detection result And a coding correction step of updating the effective area by truncating the data. 23. The encoding correction step, wherein when the carry boundary is detected in the carry boundary detection step, the effective area designated in the carry boundary detection step is equally divided into upper and lower parts. 3. The method according to claim 2, wherein the valid area is updated by truncating one of the areas.
3. The encoding method according to 2. 24. The encoding step and the encoding correction step, further comprising a conversion step of, when the same value continues to the determined code, replacing the same with a run-length marker capable of specifying the value and length. Claim 2
24. The encoding method according to 2 or 23. 25. The encoding method according to claim 24, wherein the conversion step does not perform the conversion when the code output is shorter than the run-length marker to be output without being replaced. 26. The decoding method according to claim 26, wherein the maximum value of the continuous length extracted from the run-length marker is set to the conversion step in the encoding step based on the result of the inverse transformation of the run-length marker during decoding. An encoding method according to claim 24. 27. A data storage step of: (a) outputting auxiliary parameters (context) for data to be decoded, storing the decoded data to be decoded, and outputting the data as information source data; (C) a probability estimating step of outputting decoding parameters specified based on the learning data, and (d) a probability estimating step of outputting decoding parameters specified based on the learning data. (E) output processing of information source data in a predetermined unit or synchronization detection for measuring and notifying input of a code at a predetermined interval, and outputting the decoding target data. And (f) detecting a carry boundary value in the effective area at the predetermined interval and cutting off the effective area based on the detection result. (G) decoding for updating the valid area by cutting off one of partial areas obtained by equally dividing the valid area specified by the carry boundary detecting step into upper and lower parts; A decoding correction step. 28. The decoding correction step, wherein when a carry boundary is detected in the carry boundary detection step, the effective area designated in the carry boundary detection step is equally divided into upper and lower parts. 3. The method according to claim 2, wherein the valid area is updated by truncating one of the areas.
8. The decoding method according to 7. 29. The decoding method according to claim 27, wherein the decoding step includes a run-length marker inverse transforming step of, when a run-length marker is detected, performing inverse transform to an original code value having a replaced length. 3. The decoding method according to item 1.