Software Synthesis of Variable-length Code Decoder using a Mixture of Programmed Logic and Table Lookups

Gene Cheung, Steven McCanne and Christos Papadimitriou

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-99-1040
February 1999

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1999/CSD-99-1040.pdf

Implementation of variable-length code (VLC) decoders can involve a tradeoff between decoding time and memory usage. In this paper, we proposed a novel scheme for optimizing this tradeoff using a machine model abstracted from general purpose processors with hierarchical memories. We formulate the VLC decode problem as an optimization problem where the objective is to minimize the average decoding time. After showing that the problem is NP-complete, we present a Lagrangian algorithm that finds an approximate solution with bounded error. In the resulting framework, an implementation is automatically synthesized by a code generator. To demonstrate the efficacy of our approach, we conducted experiments of decoding codebooks for pruned tree-structured vector quantizer and H.263 motion vector that show a performance gain of our proposed algorithm over single table lookup implementation and logic implementation.

BibTeX citation:

@techreport{Cheung:CSD-99-1040,
    Author = {Cheung, Gene and McCanne, Steven and Papadimitriou, Christos},
    Title = {Software Synthesis of Variable-length Code Decoder using a Mixture of Programmed Logic and Table Lookups},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1999},
    Month = {Feb},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1999/5366.html},
    Number = {UCB/CSD-99-1040},
    Abstract = {Implementation of variable-length code (VLC) decoders can involve a tradeoff between decoding time and memory usage. In this paper, we proposed a novel scheme for optimizing this tradeoff using a machine model abstracted from general purpose processors with hierarchical memories. We formulate the VLC decode problem as an optimization problem where the objective is to minimize the average decoding time. After showing that the problem is NP-complete, we present a Lagrangian algorithm that finds an approximate solution with bounded error. In the resulting framework, an implementation is automatically synthesized by a code generator. To demonstrate the efficacy of our approach, we conducted experiments of decoding codebooks for pruned tree-structured vector quantizer and H.263 motion vector that show a performance gain of our proposed algorithm over single table lookup implementation and logic implementation.}
}

EndNote citation:

%0 Report
%A Cheung, Gene
%A McCanne, Steven
%A Papadimitriou, Christos
%T Software Synthesis of Variable-length Code Decoder using a Mixture of Programmed Logic and Table Lookups
%I EECS Department, University of California, Berkeley
%D 1999
%@ UCB/CSD-99-1040
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1999/5366.html
%F Cheung:CSD-99-1040