Probability Estimation Table Apparatus

The present invention generally relates to a probability estimation table apparatus, and more particularly to an apparatus for reading a probability estimation table for use in an arithmetic coder as well as an apparatus for generating the probability estimation table stored in a memory of the probability estimation table reading apparatus.

The ISO/IEC International Standard of Coded Representation of Picture and Audio Information (Early Draft, WG9-S1R2, Dec. 14, 1990, the standard number being still not assigned) defines a method for compression encoding a bi-level image, and recommends a standard probability estimation table adaptive to the arithmetic coding data compression. The standardization of this technology is under way, and some prototypes of arithmetic coders for carrying out the arithmetic coding data compression have been proposed. However, there is still not a useful mechanism for outputting a next index, required for compression encoding an image, by using the standard probability estimation table.

FIGS. 1A and 1B show the standard probability estimation table recommended by the above mentioned international standard. The probability estimation table is called the Qe table. For each possible value of the index CX there is stored a 1-bit value MPS (CX) and a seven-bit value ST (CX), which together completely express the adaptive probability estimate associated with that particular index. An index CX is used to identify the index of the state of the coder for coding a current pixel.

In the standard Qe table in FIGS. 1A and 1B, four arrays are indexed by the index (CX). The MPS is the estimated most likely color for a pixel PIX in a symbol sequence. The Qe Value is a 15-bit value of the LPS interval size, which can be interpreted to be a probability based on a prescribed equation.

The arrays N/I-LPS (Next Index-LPS) and N/I-MPS (Next Index-MPS) are 7-bit values of next indexes giving, respectively, the next Qe state for an observation of the LPS and the MPS. The movement given by the N/I-MPS only occurs if in addition to observing the MPS, a renormalization also occurs. When the movement given by the N/I-LPS occurs, there will also be an inversion of MPS (CX) if the SWITCH (CX) value is 1. The array SWITCH is a 1-bit value of the MPS/LPS switch. A Qe table reading apparatus requires a memory (for example, a ROM) for storing the above mentioned standard Qe table. Since the 1-bit data of the switch and the 15-bit data of the Qe-Value are fixed and cannot be changed, a memory space of at least 112 14-bit words is required for storing the LPS data and the MPS data of the standard Qe table. However, memory chips currently available to the manufacturers at a low cost are multi-purpose 8-bit ROMs. There is a problem in that it is necessary to use a 16-bit memory chip for storing the standard Qe table with space of at least 112 14-bit words, thus increasing the manufacturing cost.

Accordingly, it is a general object of the present invention to provide an improved probability estimation table apparatus in which the above described problems are eliminated.

Another and more specific object of the present invention is to provide a probability estimation table reading apparatus in which a Qe table of the smallest possible size is stored and by means of which a next index can be generated effectively. The above mentioned object of the present invention is achieved by a probability estimation table reading apparatus which includes a memory part for storing a probability estimation table, the probability estimation table defining, with respect to each of a plurality of possible address values, a switch data value, a probability estimate data value, an LPS data value indicative of a next address value when a more probable symbol occurs in a sequence of symbols, and an MPS data value indicative of a next address when a less probable symbol occurs in the sequence of symbols, where each LPS data value has been replaced by the difference between a current address value and the next address value indicated by a standard LPS data value corresponding to the current address value, and where each MPS data value has been replaced by the difference between the current address and the next address value indicated by a standard MPS data value corresponding to the current address value, and a control part coupled to the memory part for reading out each LPS data value and MPS data value for each current address value of the stored probability estimation table, so that next address values required by the arithmetic coder to perform arithmetic coding data compression, can be generated. According to the present invention, it is possible to reduce the number of bits required for binary representation of the LPS/MPS data in the table into a total of 8 bits, and therefore a memory space for storing the table can be remarkably reduced.

Still another object of the present invention is to provide a probability estimation table generating apparatus for generating a probability estimation table which has the smallest possible size and is stored in a memory part of the Qe table reading apparatus to effectively output a next index to an arithmetic coder for carrying out the arithmetic coding data compression. The above mentioned object of the present invention is achieved by a probability estimation table generating apparatus which includes a difference generating part for generating difference values, with respect to each of a plurality of addresses ranging from 0 through 112 in decimal, on a probability estimation table which defines a switch data value, a probability estimate data value, a standard LPS data value indicative of a next address value when a more probable symbol occurs in a sequence of symbols, and a standard MPS data value indicative of a next address value when a less probable symbol occurs in the sequence of symbols, an LPS difference data value represented by a difference value between a current address value and a next address value when the next address value is indicated by the standard LPS data corresponding to the current address, an MPS difference data value represented by a difference value between the current address value and a next address value when the next address value is indicated by the standard MPS data value corresponding to the current address, and an MPS sign data value indicative of whether the MPS difference data value corresponding to the current address is positive, negative or equal to zero, an MPS data generating part coupled to the difference generating part, for generating an MPS data value having either six binary digits or two binary digits based on the MPS difference data value supplied by the difference generating part for each of the plurality of addresses, where the number of the binary digits is determined in response to the MPS sign data value supplied by the difference generating part for each of the plurality of addresses and where the MPS data generating part replaces the standard MPS data value by the MPS data value for each of the plurality of addresses of the stored table, and an LPS data generating part, coupled to the difference generating part, for generating an LPS data value having either six binary digits or two binary digits based on the LPS difference data value supplied by the difference generating part for each of the plurality of addresses, where the number of the binary digits is determined in response to the MPS sign data value supplied by the difference generating part for each of the plurality of addresses and where the LPS data generating part replaces the standard LPS data value by the LPS data value for each of the plurality of addresses of the stored table. According to the present invention, it is possible to reduce the number of bits required for binary representation of the LPS/MPS data in the Qe table, and therefore a memory space needed for storing the Qe table can be reduced remarkably.

Other objects and further features of the present invention will become more apparent from the following detailed description when read in conjunction with the accompanying drawings.

FIGS. 1A and 1B are the standard Qe table recommended by the international standard;

FIG. 2 is an LPS/MPS data table in which a difference between the current index and the next index is substituted for each next index of the LPS/MPS data of the table of FIGS. 1A and 1B;

FIGS. 3A and 3B are charts showing a Qe table which is developed from the table of FIG. 2 according to the present invention;

FIGS. 4A and 4B are block diagrams showing a memory part and a control part in the Qe table reading apparatus of the present invention;

FIG. 5 is a circuit diagram showing the control part of the Qe table reading apparatus to which the present invention is applied; and

FIG. 6 is a block diagram showing a Qe table generating apparatus for generating the probability estimation table shown in FIGS. 3A and 3B, to which the present invention is applied.

First, a description will be given of a process of making a useful probability estimation table according to the present invention, by referring to FIGS. 2, 3A and 3B. In the standard Qe table shown in FIGS. 1A and 1B, data in the array N/I-LPS denotes a next index in decimal when the less probable symbol LPS occurs in a sequences of symbols, and data in the array N/I-MPS denotes a next index in decimal when the more probable symbol MPS occurs in the symbol sequence. The LPS data in the standard Qe table ranges from "1" to "112" in decimal, and the MPS data therein ranges from "1" to "111" in decimal. Therefore, at least 7 bits are required for representing each of the LPS data and the MPS data, so that 14 bits in total are required for representing both the LPS data and the MPS data for each index. In the Qe table reading apparatus of the invention, the memory space required for storing the data of the next indexes is reduced remarkably, as described in the following.

FIG. 2 shows an LPS/MPS data table defining, with respect to each value of the index, LPS data indicative of a next index for the LPS occurrence and MPS data indicative of a next index for the MPS occurrence. In this LPS/MPS data table, the LPS data and the MPS data shown in FIGS. 1A and 1B are replaced by differences between a current index and a next index indicated by a corresponding LPS data or a corresponding MPS data, for each possible value ("0" through "112") of the index. In this LPS/MPS data table, for example, the LPS data "14" for the index "1" shown in FIG. 1A is replaced by a difference "+13" between the current index "1" and the next index "14" indicated by the LPS data corresponding to the current index. Also, the MPS data "2" for the index "1" shown in FIG. 1A is replaced by a difference "+1" between the current index "1" and the next index "2" indicated by the MPS data corresponding to the current index "1". Similarly, the LPS data "16" for the index "2" is replaced by a difference "+14" between the current index "2" and the next index "16" indicated by the LPS data corresponding to the current index, and the MPS data "3" for the index "2" is replaced by a difference "+1" between the the current index "2" and the next index "3" indicated by the MPS data corresponding to the current index. In this manner, the differences between the current index and the next index for both the LPS data and the MPS data are calculated with respect to each possible value of the index, and the LPS data and the MPS data are, respectively, replaced by the corresponding differences thus calculated, except those for the index "0". In other words, the LPS data and the MPS data with respect to the index "0" in the LPS/MPS data table shown in FIG. 2 are the same as corresponding data shown in FIG. 1A.

It should be noted from FIG. 2 that the LPS data in the LPS/MPS data table shown in FIG. 2 ranges from "-2" to "+30" in decimal, and the MPS data therein ranges from "-31" to "+1" in decimal. Therefore, if a sign bit is included, only 6 bits are required for representing each of the LPS data and the MPS data, and the number of bits required for binary representation of the LPS data and the MPS data for each index is reduced to a total of 12 bits.

It should also be noted from FIG. 2 that the LPS data and the MPS data do not concurrently have the maximum value "+30" nor the minimum value "-31". When the MPS data in the table shown in FIG. 2 is positive or equal to zero, the value of the MPS data is limited to "+1" or "0" in decimal. In this case, therefore, the least number of bits required for the binary representation is 6 bits for the LPS data and 2 bits for the MPS data if a sign bit of the MPS data is included. Hence, it is possible to reduce the total number of bits required for the binary representation of the LPS data and the MPS data to 8 bits, if the LPS data is expressed in 6 binary digits and the MPS data is expressed in 2 binary digits in which a sign bit is included.

When the MPS data in the LPS/MPS data table shown in FIG. 2 is negative, the value of the LPS data is limited to "-2", "-1", "0", "+1" and "+2" in decimal. Thus, the least number of bits required for the binary representation is 6 bits for the MPS data and 3 bits for the LPS data if a sign bit of the LPS data is included. In this case, also, it is possible to reduce the total number of bits required for the binary representation of the LPS data and the MPS data into 8 bits if the following measure is taken. That is, when the MPS data is negative and the LPS data is not equal to zero, "1" is subtracted from the original LPS data, and the corresponding part of the stored LPS/MPS data table is replaced by the reduced LPS data. Only when the MPS data is negative and the LPS data is equal to zero, the LPS data remains unchanged, and the corresponding part of the LPS/MPS data table is set to zero. Thus, the LPS data in the LPS/MPS data table can be expressed in two binary digits which are limited to "11", "10", "00" and "01". However, there is a problem in that it is impossible to detect whether the value of the LPS data, obtained from the Qe table, is equal to "1" or "0" in decimal. In order to solve this problem, after the LPS data is read out from the Qe table, the LPS data can be restored to the original state if "1" is added to the LPS data only when the MPS data is negative and the LPS data is not equal to zero. As obvious from FIG. 2, the case for the index "112" is the only case in which the MPS data is negative and the LPS data is equal to zero. Thus, when it is detected that the next index is equal to "113" in decimal, the next index is always changed into "112".

Accordingly, when the MPS data is negative, it is possible to reduce the total number of bits required for the binary representation of the LPS data and the MPS data to 8 bits, if the MPS data is expressed in 6 binary digits and the LPS data is expressed in 2 binary digits which can be described as one from among "11", "10", "00" and "01". If the above described measure is taken, the LPS data and the MPS data can always be represented by a total of 8 binary digits, regardless of whether the MPS data is positive or not. Thus, it is possible to reduce the total number of bits required for the binary representation of the LPS data and the MPS data to 8 bits.

FIGS. 3A and 3B show a probability estimation table in which the number of bits required for representing the LPS data and the MPS data is reduced in the manner described above. The standard probability estimation table shown in FIGS. 1A and 1B requires 30 bits for representing the data of the table for each word, and requires 14 bits for representing the LPS data and the MPS data of the table. However, the probability estimation table shown in FIGS. 3A and 3B requires only 8 bits for representing the LPS data and the MPS data for each word. Thus, the memory space needed for storing the Qe table of the present invention is reduced remarkably, and it is unnecessary to use a 16-bit memory chip for installing a probability estimation table in the Qe table reading apparatus. In the Qe table shown in FIGS. 3A and 3B, each 24-bit data string is indexed by an address value (or the index), and the top bit of each data string denotes a switch bit, the 1st through 8th bits denoting a reduced next index value of the LPS data and the MPS data, which is determined in the manner described above, and the 9th through 23th bits denoting a value of the probability estimate with respect to each of a plurality of address values.

Next, a description will be given of the Qe table reading apparatus of the present invention, with reference to FIGS. 4A, 4B and 5. In FIG. 4A, a control part 2 of the Qe table reading apparatus outputs a next address value to an arithmetic coder 3 based on readout data of the above Qe table stored in a memory part 1 provided in the apparatus. FIG. 4B shows the construction of the control part 2 of the Qe table reading apparatus of the present invention. In FIG. 4B, a sign bit checking part 10, coupled to the memory part 1, detects whether or not a readout data obtained from the stored Qe table is positive by checking a leftmost sign bit of each word corresponding to the readout data. This readout data is from the 1st through 9th bits of each 24-bit word included in the stored Qe table in the memory part 1. A data reading part 20, coupled to the memory part 1 and the sign bit checking part 10, generates input data based on the readout data obtained from the Qe table, and based on a sign data supplied by the sign bit checking part 10. The input data is determined by the data reading part 20, in response to a switch bit of the readout data and the sign data, as being either the LPS data or the MPS data in the stored Qe table. An address generating part 30, coupled to the data reading part 20, generates a next address required for arithmetic coding data compression, by adding the input data generated by the data reading part 20 to a current address, corresponding to the above readout data, supplied by an external control unit. An address checking part 40, coupled to the address generating part 30, detects whether or not the next address generated by the address generating part 30 equals 113 in decimal. If the value of the generated next address is equal to 113 in decimal, the address checking part 40 converts the next address to 112.

FIG. 5 shows the construction of the control part of the Qe table reading apparatus of the present invention. In FIG. 5, a current address value indicating a location of the stored Qe table is supplied from the memory part 1 via lines QER0 through QER6. A readout data of the 8-bit LPS/MPS data obtained from the Qe table is supplied via lines QEOUT1 through QEOUT8. A switch signal SW for causing the MPS/LPS switching is supplied via a line SW. The control part 2 outputs a next address value to the arithmetic coder 3 via lines INDEX1 through INDEX6.

The data reading part 20 has circuit elements 21 through 25 generating input data based on the readout data supplied via lines QEOUT1 through QEOUT8, a sign bit of the MPS data, and a switch signal supplied via line SW. If it is detected from the sign bit and the switch signal that the MPS data is positive and the MPS/LPS switching does not occur, the circuit elements 21 through 25 output 5-bit data value via line QEOUT7. If it is detected that the MPS data is positive and the switching occurs, the circuit elements 21 through 25 output 5-bit data value via lines QEOUT1 through QEOUT6. If it is detected that the MPS data is not positive and the switching does not occur, the circuit elements 21 through 25 output 5-bit data value via lines QEOUT3 through QEOUT7. If it is detected that the MPS data is not positive and the switching occurs, the circuit elements 21 through 25 output 5-bit data via line QEOUT1.

A sign bit checking part 11 uses a QEOUT2 data value as a sign bit of the LPS data if the MPS data is positive. If the MPS data is not positive, it uses a QEOUT6 data value as the sign bit of the LPS data. The address generating part of the circuit system includes circuit elements 31 through 36 and circuit elements 39a through 39d. The circuit element 31 is a switching circuit in which addition/subtraction exchange occurs, selectively, in response to the switch signal and the sign bits of the LPS/MPS data. An addition state of the circuit element 31 occurs when the addition of the input data generated by the elements 21 through 25 is necessary. The state of the circuit element 31 is inverted when subtraction of the input data is necessary. The circuit elements 39a through 39d generate a next address value by adding the input data value generated by the elements 21 through 25 to the current address value supplied via lines QER0 through QER6. The circuit elements 37 and 38 add "1" to the input data generated by the elements 21 through 25 when the MPS data is negative and the switching of the MPS does not occur, or when the LPS data is positive and the switching occurs. The address checking part includes circuit elements 41 and 42 which change the generated next address into "112" in decimal if it is detected that the next address equals "113" in decimal. The switching of the MPS occurs if the switch data in the table equals 1. If the switch data in the table equals zero, the switching of the MPS does not occur.

As described above, it is possible to reduce the number of bits required for binary representation of the LPS/MPS data in the table to a total of 8 bits, and therefore memory space needed for storing the probability estimation table can be reduced remarkably. Also, it is possible to effectively output a next address value by means of the stored probability estimation table.

Next, a description will be given of a Qe table generating apparatus for generating the Qe table stored in the memory part of the above described Qe table reading apparatus, with reference to FIG. 6 This Qe table generating apparatus according to the present invention generally has a difference making part 50, an MPS data making part 60 coupled to the part 50, and an LPS data making part 70 coupled to the part 50. The LPS data making part 70 has an LPS data compression part 80 coupled to the LPS data making part 70.

With respect to a particular current index of the standard Qe table shown in FIGS. 1A and 1B, a 7-bit data of the standard MPS data, a 7-bit data of the standard LPS data, and data of that particular current index are supplied to the difference making part 50. The supplying of these data to the difference making part 50 is made for each possible values "0" through "112" of the index of the standard Qe table. An MPS difference data indicative of a difference between the current index and a next index indicated by the standard MPS data, and an LPS difference data indicative of a difference between the current index and a next index indicated by the standard LPS data are generated by the difference making part 50 with respect to each value of the index of the standard Qe table. In the LPS/MPS data table shown in FIG. 2, the standard LPS data and the standard MPS data are replaced by such an LPS difference data and such a MPS difference data generated by the part 50, respectively.

For example, when a current index "1" is supplied to the difference making part 50, the standard LPS data for that current index indicating "14" in decimal as the next index, and the standard MPS data for that current index indicating "2" in decimal as the next index are given to the difference making part 50. An LPS difference data indicating a difference "+13" between the current index "1" and the next index "14" indicated by the standard LPS data, and an MPS difference data indicating a difference "+1" between the current index "1" and the next index "2" indicated by the standard MPS data are generated by the difference making part 50. Similarly, when a current index "2" is supplied to the difference making part 50, the standard LPS data for the current index "2" indicating the next index "16" in decimal and the standard MPS data for the current index "2" indicating the next index "3" in decimal are given to the difference making part 50. An LPS difference data indicating a difference "+14" between the current index "2" and the next index "16" indicated by the standard LPS data, and an MPS difference data indicating a difference "+1" between the current index "2" and the next index "1" indicated by the standard MPS data are generated by the difference making part 50. In this manner, the differences between the current index and the next index for both the LPS data and the MPS data are calculated by the difference making part 50 with respect to each possible value ("0" through "112") of the index, and the standard LPS data and the standard MPS data in the standard Qe table are, respectively, replaced by the corresponding differences as in the LPS/MPS data table shown in FIG. 2, except those for the index "0". Exceptionally, the LPS data and the MPS data with respect to the index " 0" are the same as those corresponding standard LPS/MPS data shown in FIG. 1A.

In the above described difference making part 50 in FIG. 6, the particular current index, the standard MPS data and the standard LPS data for that particular current index are supplied thereto. However, a modification of this difference making part may be made. In such a modified difference making part, the standard MPS data and the standard LPS data for each possible value "0" through "112" of the index are, in advance, stored, and each standard MPS/LPS data is read out in response to a current index supplied to the difference making part, and the above described differences are generated for each value of the index.

As in the LPS/MPS data table shown in FIG. 2, the LPS difference data ranges from "-2" to "+30" in decimal, and the MPS difference data ranges from "-31" to "+1" in decimal. Therefore, if a sign bit is included for binary representation of the LPS/MPS difference data, only 6 bits are required for representing each of the LPS difference data and the MPS difference data, and the total number of bits required for each index is reduced into 12 bits.

In FIG. 6, an output of the difference making part 50 is coupled to the MPS data making part 60 for sending a 6-bit MPS difference data to the MPS data making part 60, an output of the difference making part 50 is coupled to the LPS data making part 70 for sending a 6-bit LPS data difference data to the LPS data making part 70, and a sign-bit output of the difference making part 50 is coupled to the LPS data making part 70 for sending to the part 70 a sign-bit data indicative of whether the value of the MPS difference data is positive, equal to zero, or negative.

As shown in the LPS/MPS data table shown in FIG. 2, the LPS difference data and the MPS difference data do not concurrently have the maximum value "+30" nor the minimum value "-31". When the supplied MPS difference data is positive or equal to zero, the value of the MPS difference data is limited to "+1" or "0" in decimal if the LPS difference data has the maximum value "+30" or the minimum value "-2". That is, when the MPS data making part 60 detects in response to a sign bit of the supplied MPS difference data that the value of the MPS difference data is positive or equal to zero, a 2-bit MPS data indicating the MPS difference data is generated by the MPS data making part 60. On the other hand, when the supplied MPS difference data is negative, the value of the LPS data is limited to "-2", "-1", "0", "+1" and "+2" in decimal if the MPS difference data has the minimum value "-31". That is, when it is detected in response to a sign bit of the MPS difference data that the value of the MPS difference data is negative, a 6-bit MPS data indicating the MPS difference data is generated by the MPS data making part 60.

In response to the supplied sign-bit data of the MPS difference data, the LPS data making part 70 detects whether the value of the MPS difference data is positive, negative, or equal to zero. When it is detected that the value of the MPS difference data is positive or equal to zero, a 6-bit LPS data indicating the LPS difference data is generated by the LPS data making part 70. On the other hand, when it is detected that the value of the MPS difference data is negative, the value of the LPS data is limited to "-2", "-1", "0", "+1" and "+2" in decimal if the MPS difference data has the minimum value "-31", and a 3-bit LPS data indicating the LPS difference data is generated by the LPS data making part 70.

The 6-bit or 2-bit MPS data is output by the MPS data making part 60 as the MPS data in the Qe table (FIG. 3) to be stored, regardless of whether the value of the MPS difference data is positive, negative, or equal to zero. The 6-bit LPS data is output by the LPS data making part 70 as the LPS data of the Qe table (FIG. 3) to be stored, when the value of the MPS difference data is positive or equal to zero. However, when the value of the MPS difference data is negative, the 3-bit LPS data is output by the LPS data making part 70 to the LPS data compression part 80.

In the LPS data compression part 80, the 3-bit LPS data supplied is converted into 2-bit LPS data by taking the above described measure when the MPS difference data is negative. That is, when the LPS data is not equal to zero and the MPS difference data is negative, "1" in decimal is subtracted by the LPS data compression part 80 from the absolute value of the supplied 3-bit LPA data, and the thus converted LPS data (=the absolute value of the LPS difference data minus "1") is output by the LPS data compression part 80 as the 2-bit LPS data of the Qe table (FIG. 3) to be stored. Therefore, when the 2-bit LPS data is read out by the Qe table reading apparatus from the stored Qe table, "1" is always added to the LPS data. When the LPS data is equal to zero, the unchanged LPS data (=the LPS difference data equal to zero) is output by the LPS data compression part 80 as the 2-bit LPS data of the Qe table (FIG. 3) to be stored. Hence, the 2-bit LPS data output by the LPS data compression part 80 as the LPS data of the stored Qe table (FIG. 3) is limited to "11", "10", "00", or "01" in binary representation. Accordingly, it is possible to always reduce the total number of bits required for binary representation of the LPS data and the MPS data in the Qe table (FIG. 3) to be stored into 8 bits.

Only when the MPS difference data is negative and the LPS difference data is equal to zero, the unchanged LPS data (=the LPS difference data equal to zero) is output by the LPS data compression part 80 as the 2-bit LPS data of the Qe table (FIG. 3) to be stored. As being obvious from the LPS/MPS data table of FIG. 2, the LPS data and the MPS data for the index "112" is the only case in which the MPS data is negative and the LPS data is equal to zero. Thus, only when it is detected by the Qe reading apparatus that the next index indicated by the readout data is equal to "113", the next index is changed into "112".

Further, the present invention is not limited to the above described embodiment, and variations and modifications may be made without departing from the scope of the present invention.