Communications: electrical – Audible indication – Percussion-type sound producer
Patent
1981-03-30
1984-08-21
Miller, C. D.
Communications: electrical
Audible indication
Percussion-type sound producer
235310, H03K 1300
Patent
active
044673175
DESCRIPTION:
BRIEF SUMMARY
DESCRIPTION
1. Technical Field
This invention relates to arithmetic compression coding of conditional binary sources, the coding being controlled by a parameter whose values correspond to predetermined source probability intervals.
2. Background Art
The prior art of FIFO arithmetic string encoding is detailed in the copending U.S. patent application Ser. No. 098,285, filed on Nov. 28, 1979. Further, methods for carry-over control in FIFO arithmetic code strings are set out in copending U.S. patent application Ser. No. 048,319, filed on June 14, 1979, and the IBM Technical Disclosure Bulletin, Vol. 23, pages 310-312, published in June 1980.
Rissanen and Langdon, "Arithmetic Coding", IBM Journal of Research and Development, Vol. 23, No. 2, March 1979, discloses that in arithmetic coding, the current code string is generated recursively by adding augends to the previous code string which result from the encoding of the previous binary source symbol. Decoding involves examining the most significant part of the code string and determining from its magnitude the largest augend not exceeding the numerical value of said code string. The augend is, in turn, subtracted out. The decoded symbol is that source alphabet symbol which corresponds to the subtracted-out augend.
Rissanen and Langdon, "Universal Modeling and Coding", IEEE, Trans. Information Theory, Vol. IT-27, No. 1, January 1981, partition the data compression problem in a modeling part and a coding part. The present invention deals only with the coding aspect of compression. The Rissanen and Langdon reference also depicts the code string generated by a FIFO arithmetic code as being a number in the interval (0,1), that is, a semi-open interval on the number line which includes 0, but does not include 1. The code is constrained in order to treat rational numbers along this interval. The source string is encoded recursively, one source symbol b at a time. Operatively, arithmetic coding successively subdivides this interval. A subinterval corresponding to a so-far encoded source string s=b(1), b(2) . . . b(i) is defined by its lower bound, C(s), in the interval, and a number T(s) defining the size of the interval. Significantly, the subinterval size is represented to a fixed precision in that the number of significant digits in the binary representation of T(s) is no more than a predetermined q bits in length. The subinterval thus defined may be represented by [C(s), C(s)+T(s)]. The interval includes the lower-bound C(s) and spans the range up to, but not including, the number C(s)+T(s).
According to the prior art U.S. patent application Ser. No. 098,285, in order to encode the next symbol, the interval length T(s) should be subdivided into as many parts as there are source symbol values. In the binary case, each source symbol takes only one of two symbol values. This requires that the interval be partitioned into two parts with two corresponding size values T. The values T are calculated according to an integer-valued control parameter k. Thus, the two sizes T resulting from the partitioning or subdivision operation are assigned to the more probable symbol (MPS) and the less probable symbol (LPS), respectively. For the subdivision operation disclosed in the prior art, specifically:
The new subinterval would be encoded as: ##EQU1##
In FIG. 2b, size 1 is called the augend because size 1 is added to C(s) to form the new lower bound.
A stream of ones and zeros to be encoded can also be represented as a run of MPS's terminated by an LPS. The action of the encoder requires modification of the code string value C(s) and the current subinterval magnitude T(s). Let s.b denote the so-far encoded string following the recursive encoding of symbol b. The prior art states that:
For each MPS
Upon the occurrence of each LPS in a binary symbol string, the worst-case cycle time requires an encoder to perform four operations. These comprise the steps of (1) decreasing by shift and subtract an internal variable T(s) as a function of the control parameter k in order to form T(s.
REFERENCES:
patent: 4286256 (1981-08-01), Langdon
Rissanen, "IEEE Transactions on Information Theory", vol. IT-27, No. 1, Jan. 1981, pp. 12-23.
Rissanen, "IBM Journal of Research & Development", vol. 23, No. 2, Mar. 1979, pp. 149-162.
Langdon, "IBM Technical Disclosure Bulletin", vol. 23, No. 1, Jun. 1980, pp. 310-312.
Langdon, Jr. Glen G.
Rissanen Jorma J.
Brodie R. Bruce
International Business Machines - Corporation
Miller C. D.
LandOfFree
High-speed arithmetic compression coding using concurrent value does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with High-speed arithmetic compression coding using concurrent value , we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High-speed arithmetic compression coding using concurrent value will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1938154