Browse Prior Art Database

"Speed-up Mode" for Q-coder Software Implementation

IP.com Disclosure Number: IPCOM000099333D
Original Publication Date: 1990-Jan-01
Included in the Prior Art Database: 2005-Mar-14
Document File: 4 page(s) / 151K

Publishing Venue

IBM

Related People

Anderson, KL: AUTHOR [+2]

Abstract

A technique is described whereby Q-Coder (*) software is provided with "Speed-Up" encoding and decoding sequences so as to reduce processing cycles for a software implementation, such as is used in binary image compression.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 38% of the total text.

"Speed-up Mode" for Q-coder Software Implementation

       A technique is described whereby Q-Coder (*) software is
provided with "Speed-Up" encoding and decoding sequences so as to
reduce processing cycles for a software implementation, such as is
used in binary image compression.

      Q-Coder software normally requires one complete cycle per
symbol encoded/decoded.  In some applications, long sequences of more
probable symbols are encoded/decoded using the same context.  The
concept described herein provides a more efficient way to encode and
decode the long sequences so as to attain an overall increase in
processing speed.

      In general, the Q-Coder compresses a sequence of binary
decisions, given a "context" (defined by the model) for each
decision.  For each context, the Q-Coder stores a flag indicating
what the more probable decision for that context is, along with an
estimate of the probability of the less probable decision.  These
values are adapted dynamically during the coding process.

      The "Speed-Up" description concentrates on the "serial"
software version, although the "parallel" or hardware version has
similar properties and would also benefit from the speed-up mode.

      The Q-Coder works with an interval A, a probability Q0 that the
less probable symbol will occur, and a "Code Stream" whose low-order
bits are kept in a variable X.  The operations required to code a
more probable symbol (MPS) decision are:

                            (Image Omitted)

    A=A-QO
    if A<AMIN
    renormalize
    end To code a less probable decision, the procedure is:
    A=A-QO
    X=X-A
    A=QO
    renormalize
    The renormalization scales X and A up until A is greater than or
equal to the constant AMIN, and may adjust QO and the flag indicating
what the more probable decision for the current context is.  The
corresponding decoder determines the next symbol coded using the
following procedure:
    A=A+QO
    if X>=A
    (MPS decoded)
    if A>-AMIN
    renormalize
    end
    else
    (LPS decoded)
    X=X-A
    A=-QO
    renormalize
    end
    In some applications, long sequences of more probable symbols are
common.  The concept described herein concentrates on methods for
encoding and decoding such sequences in an efficient manner, as
follows:

      The Q-Coder incorporates the adaptation of the less probable
symbol (LPS) probability QO into the coding process.  Therefore, it
is known that for a particular context, QO is unchanged as long as A
is greater than or equal to AMIN.

      Assuming that it is known that a long sequence of more probable
symbols is to be coded for a particular context, then this may be
performed by reducing the interval A for each decision coded,
comparing A with the lower limit AMIN after each reduction, and
renormalizing whenever A becomes smaller than AMIN.  However,...