JPH04213221A - Information source symbol appearance probability estimating device - Google Patents

Abstract

PURPOSE:To attain effective utilization of the device by providing a storage area storing 2-dimension symbols and a storage area storing an information symbol. CONSTITUTION:A past information source symbol is stored in an information source symbol storage means 13, and a part of two-dimension series representing a current information symbol from which an estimated appearance probability is calculated is stored in a two-dimension series storage means 12, and the state depending on the means 12, 13 is calculated by a state calculation means 14. Each estimated appearance probability of 2-dimension elements corresponding to the calculated state from a count storage means 15 is calculated by an estimated appearance probability calculation means 16 by using an arithmetic ratio at an estimated appearance probability calculation means 16. Thus, it is not required to clarify the relation between an information source symbol of 3-dimension or over and a code word, and the appearance probability of elements representing the information source symbol of the information source is sequentially estimated based on the arrangement of real past information source symbols. Thus, the storage device is effectively utilized by implementing the efficient coding in this way.

Description

[Detailed description of the invention]

0001

[Industrial Application Field] The present invention relates to an information source symbol occurrence probability estimating device, particularly in the field of digital data processing, which estimates the occurrence probability of an information source symbol at any time by utilizing data properties. The present invention relates to an information source symbol occurrence probability estimation device capable of estimating occurrence probability of an information source symbol.

0002

[Prior Art] Generally, when encoding an information source so that the encoded sequence is as short as possible, redundancy, which is the ratio of the code length to the overall code length, is set in consideration of coding efficiency. Estimate the probability of occurrence of the source symbol to reduce it. In encoding, there is a method of expressing a data string generated from an information source using a code word length based on an estimated probability of occurrence. The encoding side calculates the probability of occurrence by counting the number of times the information source symbol appears. At this time, when encoding a ternary or more information source symbol, it is necessary to uniquely associate the code word that is the encoded expression with the information source.

FIG. 4 shows a configuration diagram of an example of a conventional information source symbol occurrence probability estimation device. In the figure, a binary sequence holding unit 41 holds a partial sequence of binary symbols representing information source symbols from an information source. The state calculation unit 42 calculates a unique state from the state of the symbol sequence in the binary sequence holding unit 41. A count holding section 43 is prepared for each state (in this example, a count holding section for two states), and the state calculation section 42 calculates the number of appearances of the information source symbol from the state calculation result. This count holding section 43 has a first
There are two holding sections, a count holding section 44 and a second count holding section 45. The first count holding unit 44 holds the number of occurrences of the binary symbol in the state calculated by the state calculation unit 42. The second count holding unit 45 holds the number of times the other binary symbol occurs in the state calculated by the state calculation unit 42. The estimated occurrence probability calculation unit 46 is the first count holding unit 4
4 and the contents of the second count holding unit 45, the estimated probability of occurrence is calculated.

[0004] The conventional information source symbol occurrence probability estimating device has two methods.
There are two types. First, in the case of encoding a ternary or more information source symbol, the first information source symbol occurrence probability estimating device calculates in advance the relationship between the information source symbol output from the information source and a code word that is a sequence of code symbols. , the number of occurrences of the information source symbol is counted by the count holding unit 43 prepared for each state, and the occurrence probability is calculated by the estimated occurrence probability calculation unit 46. presume.

On the other hand, when encoding a ternary or more information source symbol, a second information source symbol occurrence probability estimation device replaces the information source symbol from the information source with a binary symbol (0 and 1). It is stored in the binary sequence holding unit 41, and the original information source is regarded as an information source consisting of binary information source symbols, and the sequence that is the sequence of past binary information source symbols is regarded as one state. The count is counted by a count holding unit 43 prepared for each time, and the estimated probability of occurrence calculation unit 46 estimates the probability of occurrence.

[0006]

However, when encoding ternary or more information source symbols, the first information source symbol occurrence probability estimating device is designed to estimating the occurrence probability of another symbol for a sequence of information source symbols and information source symbols. It is necessary to clearly indicate the relationship between code words, which are sequences of codes to which sequences are assigned, and a corresponding amount of expression is required. On the other hand, when encoding information source symbols with three or more elements, the second information source symbol occurrence probability estimating device considers the information source symbols to be binary, so it has a state based on the past arrangement of the actual information source symbols. I can't do that. Furthermore, there is a problem in that the probability of occurrence of an information source symbol cannot be estimated.

Next, explanation will be given using a specific example. For example, an information source symbol consisting of 256-element information source symbols can be uniquely expressed by a symbol string of eight binary symbols of equal length. As an example, if the output "AABBAC" of the information source is expressed using binary symbols 0 and 1, it becomes as follows. At this time, “A” is “01000001”, “B”
” to “01000010”, “C” to “0100001”
1”. Also, “X” is expressed as “1000001”.
0, "Y" is expressed as "10000100", when estimating the probability of occurrence of the next symbol based on the past series stored in the storage area consisting of binary symbols in the conventional technology, the past series When the part “AB” is stored as
The probability of occurrence of the next symbol 0 is “01000” in the count holding unit 43.
In the state of “00101000010”, the binary symbol “0”
” is the next element and the number of times the binary symbol “1” is the next element.

"1000001010000100" is stored in the binary sequence holding unit 41 of the storage area consisting of binary symbols, and since the final binary symbol is "0", the probability of occurrence of the next symbol "1" is will be estimated. At this time, the past series stored is series “AB”.
The information source symbol “
This affects the count holding unit 43 for estimating the probability of occurrence of an element occurring subsequent to "XY", and the probability that B occurs next to "AB" can no longer be determined.

[0009] The present invention has been made in view of the above points.
Information source symbol in compression encoding that estimates the probability of occurrence of each information source symbol based on the past history of a data string composed of finite element information source symbols, and encodes the current information source symbol. Information source symbol occurrence probability estimation that eliminates the need to specify the relationship between ternary or higher information source symbols and code words, and enables estimation using a count holding unit prepared for each state based on a sequence of information source symbols. The purpose is to provide equipment.

0010

[Means for Solving the Problems] FIG. 1 shows a diagram of the basic configuration of the present invention. In the information source symbol occurrence probability estimating device 11 that estimates the occurrence probability of each information source symbol in a data string composed of finite element information source symbols based on past history,
A binary sequence storage means 12 that holds a partial sequence of binary symbols representing the information source symbol from the information source 10, an information source symbol storage means 13 that holds the information source symbol, and a binary sequence storage means 12.
and a state calculation means 14 that calculates a unique state from the state of the information source symbol storage means 13, a set of two count storage means 15 that holds the number of occurrences of the information source symbol for each state, and a count storage means 15. The estimated occurrence probability calculation means 16 calculates the estimated probability of occurrence from the calculations, and stores past information source symbols in the information source symbol storage means 13, The part for which the probability has been calculated is stored in the binary sequence storage means 12, the state determined by the binary sequence storage means 12 and the information source symbol storage means 13 is calculated by the state calculation means, and the count storage means corresponds to the calculated state. 15, the estimated probability of occurrence of each of the two-dimensional elements is calculated by an arithmetic ratio.

[0011]

[Operation] The present invention has counting storage means for each state indicated by a storage area consisting of one binary symbol (0 and 1) and a storage area consisting of one set of information source symbols, A counting storage means for storing the number of times one of the binary symbols has occurred for each state based on the arrangement of source symbols; and a counting storage means for storing the number of times the other binary symbol has occurred in the state calculated by the state calculation means. It has two counting storage means. This eliminates the need to clearly state the relationship between ternary or more information source symbols and code words, and calculates the probability of occurrence of elements representing the source symbols of an information source based on the actual arrangement of past information source symbols. presume.

0012

Embodiment FIG. 2 shows a system configuration of an embodiment of the present invention, and shows an example in which an information source symbol occurrence probability estimating device is used as an occurrence probability estimating device of an arithmetic coding device. In the figure, the same components as in FIG. 1 are given the same reference numerals. The system of this embodiment includes an information source 10 such as a storage medium or a transmission medium, an arithmetic coding device 21, an information source symbol occurrence probability estimation device 11, and a storage medium or transmission medium 16.

An information source 10, such as a storage medium or a transmission medium, generates a data string of source symbols. The information source symbols output from the information source 10 are input to the arithmetic encoding device 21 as a string of binary symbols. As a result, the information source symbol is determined by the information source symbol occurrence probability estimation device 11 for one binary symbol.
is encoded according to the estimated probability of occurrence of the binary symbol obtained from The information source symbol occurrence probability estimating device 11 receives a binary symbol delayed by one clock from the arithmetic coding device 21, and
The status of the source symbol occurrence probability estimation device 11 is communicated.

FIG. 3 shows the configuration of an embodiment of the present invention. In the figure, the same components as in FIGS. 1 and 4 are given the same reference numerals. The information source symbol occurrence probability estimation device 11 of this embodiment includes a binary sequence holding section 41, an information source symbol holding section 30, a state calculation section 42,
It is composed of a count holding section 31, a first count holding section 32, a second count holding section 33, and an estimated occurrence probability calculation section 46. The binary series holding unit 41 stores information source symbols and partial series of binary symbols from the information source 10 such as a storage medium. The state calculation unit 42 calculates a unique state from the state of the symbol sequence in the binary sequence holding unit 41. The information source symbol holding unit 30 stores a total of 48 bits (6 bytes) of past information source symbols from the binary sequence holding unit 41, with each symbol being 8 bits. The count holding unit 31 stores the number of occurrences of the information source symbol, and among them,
The count holding unit 32 stores the number of times one of the binary symbols has occurred, and the count holding unit 33 stores the number of times the other binary symbol has occurred based on the state calculated by the state calculation unit 42. The estimated occurrence probability calculation section 46 calculates the ratio of the counts of the count holding sections 32 and 33 using a method that does not result in a zero device.

Next, the operation up to the calculation of the estimated probability of occurrence will be explained. First, the current information source symbol is supplied from the information source 10 to the binary sequence holding unit 41, and further, the current information source symbol is supplied to the binary sequence holding unit 41.
The information is supplied to the information source symbol holding unit 30 and the state calculation unit 41 from the source symbol storage unit 30 and the state calculation unit 41. Next, when the binary symbol series represented by the binary sequence holding unit 41 becomes the current information source symbol, the information source symbol holding unit 30 shifts the held information source symbol by one byte and holds the information source symbol. The information source symbol of the binary sequence holding section 41 is stored in the section 30, and the binary sequence holding section 41 is left empty. Further, the empty binary sequence holding unit 41 holds the current information source symbol from the information source 11.

At this time, the count holding unit 31 holds the actual number of occurrences of the information source symbol. First count holding unit 3
2 is a count holding unit that holds the number of times one of the binary symbols occurs in the state calculated by the state calculation unit 42. The second count holding unit 33 is a count holding unit that holds the number of times the other one of the binary symbols occurs in the state calculated by the state calculation unit 42. As a result, the estimated occurrence probability calculation unit 46 calculates the estimated probability of occurrence by calculating the arithmetic ratio from the first count holding unit 32 and the second count holding unit 33, and supplies the calculated probability to the storage medium 16.

Next, explanation will be given using a specific example. For example, an information source symbol consisting of 256-element information source symbols can be uniquely expressed by a symbol string of eight binary symbols of equal length. As an example, if the output "AABBAC" of the information source is expressed using binary symbols 0 and 1, it becomes as follows. At this time, “A” is “01000001”, “B”
” to “01000010”, “C” to “0100001”
It is expressed as 1”.

In the present invention, by having the binary sequence holding unit 41 and the information source symbol holding unit 30, the information source symbol holding unit 30 stores “01000001” of “A” and
“01000010” of “B” is stored in the binary series holding unit 41.
is stored, and the probability of occurrence of the next symbol "0" is estimated. At this time, the probability of occurrence of the next symbol "0" is estimated by the state calculation unit 4 based on the past information source symbol and the binary symbol "1".
In the state calculated in step 2, the count holding units 32 and 33 hold the respective number of occurrences, and the estimated occurrence probability calculation unit 46
By calculating the arithmetic ratio of the count holding units 32 and 33, the estimated probability of occurrence is obtained.

Next, the information source symbol holding unit 30 stores the “0100” of the information source symbol “B” represented by the binary sequence holding unit 41.
0010” is stored, and “0” is stored in the binary sequence holding unit 41.
is stored, and the probability of occurrence of the next symbol "1" is estimated by the state calculation unit 42 using the past information source symbol and the binary symbol "0".
In the state calculated by , the count holding units 32 and 33 hold the number of occurrences, and the estimated occurrence probability calculating unit 46 calculates the arithmetic ratio of the count holding units 32 and 33 to obtain the estimated probability of occurrence.

As a result, a count holding section 31 is prepared for each state indicated by a storage area that holds binary symbols and a storage area that consists of a set of one information source symbol, and two
The count holding unit 31 based on the state using storage areas divided into three parts eliminates the need to clearly state the relationship between three or more information source symbols and code words, and calculates the probability of occurrence of the element representing the information source symbol based on the actual past value. It can be estimated based on the arrangement of information source symbols.

[0021]

Effects of the Invention As described above, according to the present invention, states are calculated by providing a storage area that holds binary symbols and a storage area that holds information source symbols, and counts are maintained in each state. Since the information source symbol occurrence probability estimating device is equipped with an information source symbol occurrence probability estimation device, the occurrence probability of an element representing an information source symbol to be encoded can be estimated at any time based on the actual past arrangement of information source symbols. By performing efficient encoding using such a method, effective use of the storage device can be realized, which is extremely useful in practice.

[Brief explanation of the drawing]

FIG. 1 is a diagram showing the principle configuration of the present invention.

FIG. 2 is a system configuration diagram of an embodiment of the present invention.

FIG. 3 is a configuration diagram of an embodiment of the present invention.

FIG. 4 is a configuration diagram of an example of a conventional information source symbol occurrence probability estimation device.

[Explanation of symbols]

10 Information source 11 Information source symbol occurrence probability estimation device 12 Binary series storage means 13 Information source symbol storage means 14 Status calculation means 15 Count storage means 16 Estimated occurrence probability calculation means 30 Information source symbol holding section 41 Binary series holding unit 42 Status calculation unit 31 Count holding part 46 Estimated occurrence probability calculation unit

Claims (1)

[Claims] Claim 1. An information source symbol occurrence probability estimating device for estimating the occurrence probability of each information source symbol from an information source based on past history of a data string composed of finite element information source symbols. binary sequence storage means for holding a subsequence of binary symbols representing information source symbols from a source; information source symbol storage means for holding information source symbols from said binary sequence storage means; and said binary sequence storage. a state calculation means for calculating a unique state from the state of the information source symbol storage means; a set of two count storage means for retaining the number of occurrences of the information source symbol for each state; the estimated occurrence probability calculating means calculates the estimated probability of occurrence from the count of The calculated portion is stored in the binary series storage means, the state determined by the information source storage means and the binary series storage means is calculated by the state calculation means, and the state corresponding to the calculated state is stored in the count storage means. An information source symbol occurrence probability estimating device characterized in that the estimated probability of occurrence of each of two-dimensional elements is calculated by an arithmetic ratio.