Browse Prior Art Database

FAST BINARY SEARCH ALGORITHM FOR TRELLIS-CODED QUANTIZATION

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

Publishing Venue

Motorola

Related People

Glen P. Abousleman: AUTHOR

Abstract

A new codebook search algorithm was devel- Recall that for encoding a memoryless source at oped for trellis-coded quantization that enables R bits/per sample, trellis-coded quantization (TCQ) either fixed-rate codebooks or entropy-constrained [l] uses a codebook of size 2R+1 that is partitioned codebooks to be searched proportional to lograN, into four subsets, each containing 2R-1 codewords. where N is the number of codewords. These subsets are labeled Da, D,, D,, and D,, and are used as labels for the branches of a suitably cho- This is in contrast to traditional trellis-coded sen trellis. quantization, where the search is proportional to N.

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 35% of the total text.

Page 1 of 6

Technical M-OLA @ Developments

FAST BINARY SEARCH ALGORITHM FOR

TRELLIS-CODED QUANTIZATION

by Glen I? Abousleman

  A new codebook search algorithm was devel- Recall that for encoding a memoryless source at oped for trellis-coded quantization that enables R bits/per sample, trellis-coded quantization (TCQ) either fixed-rate codebooks or entropy-constrained [l] uses a codebook of size 2R+1 that is partitioned codebooks to be searched proportional to lograN, into four subsets, each containing 2R-1 codewords. where N is the number of codewords. These subsets are labeled Da, D,, D,, and D,, and are used as labels for the branches of a suitably cho-

  This is in contrast to traditional trellis-coded sen trellis. quantization, where the search is proportional to N.

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

w DI "2 0, , m DI m 03

I -

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

. . .

0 Mmmla, 1°C. *MO 144 January 2a!m

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

Page 2 of 6

0 M MO-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 DO or Ds.

   If a codeword from Dz 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 xt, x2,.... the best
(minimum mean-squared-error) allowable sequence of codewords is determined as follows. For the iti stage in the trellis (corresponding to xi), the best codeword in the J* subset (j = 0, 1, 2, 3), say cj, is chosen, and the associated cost pi = (xi - cj )2 is cal- culated. Each branch in the ;* 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 tixed- rate TCQ is superior to that of optimized fixed-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 LX [31.

  Note that at each step in the encoding, the code- word must be chosen from either A, = Do u 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:

fWW = ~.r~~P(clAi)P(4i)logzScl~. (1)

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