CaltechAUTHORS
  A Caltech Library Service

Low complexity code design for lossless and near-lossless side information source codes

Zhao, Qian and Effros, Michelle (2003) Low complexity code design for lossless and near-lossless side information source codes. In: Data Compression Conference (DCC '03), Snowbird, UT, 25-27 March 2003. IEEE , Los Alamitos, CA, pp. 3-12. ISBN 0-7695-1896-6 http://resolver.caltech.edu/CaltechAUTHORS:ZHAdcc03

[img]
Preview
PDF
See Usage Policy.

1197Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:ZHAdcc03

Abstract

The instantaneous side of information source code (SISC) design is considered. In the SISC configuration, the encoder describes source X to the decoder; the decoder uses this description and side information Y, to reconstruct X. Prior work on lossless and near-lossless SISC design demonstrates that globally optimal design is NP-hard. A family of polynomial complexity code design algorithms is introduced that approximates the optimal solution for lossless and near-lossless SISCs. The algorithm may be used to design both Huffman and arithmetic SISCs for an arbitrary probability mass function p(x,y). Experimental results comparing the resulting performances to each other and to the theoretical limit are included.


Item Type:Book Section
Additional Information:© Copyright 2003 IEEE. Reprinted with permission. This material is based on work supported by NSF Award No. CCR-9909026 and CCR-0220039 and by Caltech's Lee Center for Advanced Networking.
Subject Keywords:Huffman codes, arithmetic codes, computational complexity, source coding, source code design, source coding theory, network information theory
Record Number:CaltechAUTHORS:ZHAdcc03
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:ZHAdcc03
Alternative URL:http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26854&arnumber=1193991
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:7388
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:08 Feb 2007
Last Modified:26 Dec 2012 09:31

Repository Staff Only: item control page