Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

ENHANCED ARITHMETIC ENCODING SYSTEM FOR USE WITH WAVELET IMAGE CODING

IP.com Disclosure Number: IPCOM000009716D
Original Publication Date: 2000-Jan-01
Included in the Prior Art Database: 2002-Sep-12
Document File: 5 page(s) / 280K

Publishing Venue

Motorola

Related People

Glen P. Abousleman: AUTHOR

Abstract

A new arithmetic encoding system uses two Recall that for encoding a memoryless source at modeling procedures in four configurations to pro- R bits/per sample, trellis-coded quantization (TCQ) vide outstanding lossless compression of ECTCQ [l] uses a codebook of size 2R+' that is partitioned quantization indices. into four subsets, each containing 2R-' codewords.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 22% of the total text.

Page 1 of 5

Technical MOTOROLA @ Developments

ENHANCED ARITHMETIC ENCODING SYSTEM FOR USE WITH WAVELET IMAGE CODING

by Glen P. Abousleman

  A new arithmetic encoding system uses two Recall that for encoding a memoryless source at modeling procedures in four configurations to pro- R bits/per sample, trellis-coded quantization (TCQ) vide outstanding lossless compression of ECTCQ [l] uses a codebook of size 2R+' that is partitioned quantization indices. into four subsets, each containing 2R-' codewords.

                                These subsets are labeled DO, D,, D,, and D,, and The choice of a particular scheme is a function are used a labels for the branches of a suitably cho- of both sequence length and bit rate. sen trellis.

An example is shown in Figure 1 for R = 2.

M 0, 02 D3 , m 0, 02 03

I -

Fig. 1 A 4-state trellis with subset labeling and codebook.

. . .

0 *omla. 1°C. zml 154 January 2ooo

[This page contains 15 pictures or other non-text objects]

Page 2 of 5

0 M M-LA Technical Developments

  Sequences of codewords that can be produced by the TCQ system are those that result from "walks" along the trellis from left to right. For example, if beginning in the top left state of the trel- lis in Figure 1, the first codeword must be chosen from either Da or Dz.

   If a codeword from Ds is chosen, then we walk along the lower branch (shown with a heavy line) to the second state from the bottom, at which we must choose a codeword from either Di or Ds.

  Given an input data sequence xi, x2,..., the best (minimum mean-squared-error) allowable sequence of codewords is determined as follows. For the ifi stage in the trellis (corresponding to xi). the best codeword in the J* subset fj = 0, 1,2, 3), say cj, is chosen, and the associated cost pi = (xi - cj )* is cal- culated. Each branch in the ,'h stage of the trellis that is labeled with subset Dj is assigned cost pj. The Viterbi algorithm is then used to find the path through the trellis with the lowest overall cost.

  Although the performance of optimized fixed- rate TCQ is superior to that of optimized fvted-rate scalar quantization (Lloyd-Max quantization), there is still much performance to be gained by entropy coding the output of a specially designed TCQ sys- tem PI, t31.

  Note that at each step in the encoding, the code- word must be chosen from either A, = Da v D, or A, = D, u D,. Each of these "supersets" contains 2R codewords and hence, given an initial trellis state, the sequence of selected codewords can be transmitted using one R-bit label for each sample.

  These codeword labels can then be noiselessly compressed using one variable length code for each superset. The encoding rate achievable by this process is the conditional entropy of the codebook C, given the superset:

WW = I;,~.I~~A~P(cI~~)P(A~~o~P(cIA~). (1)

  For a codebook of size 2R+' (as discussed above), this noiseless compression causes the encoding rate to fall below R bits/sample. Thus, the size of the codebook should be increased.

  An obvious method of adjusting th...