Browse Prior Art Database

Embedding Prefix Codes Into Arithmetic Codes

IP.com Disclosure Number: IPCOM000042239D
Original Publication Date: 1984-May-01
Included in the Prior Art Database: 2005-Feb-03
Document File: 2 page(s) / 15K

Publishing Venue

IBM

Related People

Langdon, GG: AUTHOR

Abstract

This invention relates to embedding prefix codes into an arithmetic code string where prefix codes represent rare events. This saves encoding cycles. Suppose there exists a plurality of events to which it is desired to assign prefix code words. Now, such a "multi-bit" event in one step can be encoded. Some ability to adapt dynamically is lost, but there is a gain in speed at both the encoder and decoder because it just takes one step for each of these prefix code words. Parenthetically, one of the advantages of prefix codes includes the ability to decode an event by a simple decoder on the leading bits of the code string. The invention is described in terms of combining a binary arithmetic code with a prefix code. This combination is a FIFO (first-in, first-out) code.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 46% of the total text.

Page 1 of 2

Embedding Prefix Codes Into Arithmetic Codes

This invention relates to embedding prefix codes into an arithmetic code string where prefix codes represent rare events. This saves encoding cycles. Suppose there exists a plurality of events to which it is desired to assign prefix code words. Now, such a "multi-bit" event in one step can be encoded. Some ability to adapt dynamically is lost, but there is a gain in speed at both the encoder and decoder because it just takes one step for each of these prefix code words. Parenthetically, one of the advantages of prefix codes includes the ability to decode an event by a simple decoder on the leading bits of the code string. The invention is described in terms of combining a binary arithmetic code with a prefix code. This combination is a FIFO (first-in, first-out) code. Let the coder have 6- bit registers C and A, initialized for the encoding process to #0.00000 and
1.00000, respectively. For this explanation, use of "#" is made as a delimiter, indicating that the following bit is the first bit of the code string. With 6-bit registers, this binary arithmetic code accepts skew numbers K (as coding parameters) of 1, 2, ..., 5. Register C is the register in which the code string is developed. The invention is independent of means and alternatives for handling the code string once it has left the C register. As the code is formed, register C is shifted left, into a "Buffer Carry-over Unit". To decode the code string, the C register is initialized with the code string's first 6 bits. If the code string is "#uvwxyz....", then the C register is initialized as follows: #u.vwxyz. As the C register is subtracted from, and shifted left during the decoding process, the C register vacated positions on the right are filled with the next-in-line bits of the code string (7th, 8th, etc., in turn). Next, there is set out an example of the encoding and decoding process, where the events are binary arithmetic code (BAC) events, and one of the events is a 4-bit code word "1010". The BAC encoder normally performs as follows. For the More Probable Symbol (MPS), add 2*-K to the C register and subtract 2*-K from the A register. If the leading bit of the A register goes to "0", normalize by shifting the A and C registers each left one bit. For the Less Probable Symbol (LPS), shift the C register left K bits, and set the A register to 1.00000. The BAC decoding algorithm is as follows. The model provides the decoder with the value K. Subtract 2*-K from the C register and the A register. If the result in the C register is negative, the Event was LPS, and shift the original C left K bits (they will all be 0) and set A to 1.00000. If subtracting 2*-K from C leaves a positive result, keep that as the new result and decode the MPS. If the leading bit of the A register became 0, then normalize by shifting A and C registers left one bit. To supplement the above rules for embedding prefix code words, perform the following s...