World Library  
Flag as Inappropriate
Email this Article

Slepian–Wolf coding

Article Id: WHEBN0030474423
Reproduction Date:

Title: Slepian–Wolf coding  
Author: World Heritage Encyclopedia
Language: English
Subject: Distributed source coding, Video codec
Collection:
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Slepian–Wolf coding

In information theory and communication, the Slepian–Wolf coding, also known as the Slepian–Wolf bound, is a fundamental result in distributed source coding discovered by David Slepian and Jack Wolf in 1973. It is a method of theoretically coding two lossless compressed correlated sources.[1]

Distributed coding is the coding of two, in this case, or more dependent sources with separate encoders and a joint decoder. Given two statistically dependent i.i.d. finite-alphabet random sequences X and Y, the Slepian–Wolf theorem includes theoretical bound for the lossless coding rate for distributed coding of the two sources as shown below:[1]

R_X\geq H(X|Y), \,
R_Y\geq H(Y|X), \,
R_X+R_Y\geq H(X,Y). \,

If both the encoder and the decoder of the two sources are independent, the lowest rate it can achieve for lossless compression is H(X) and H(Y) for X and Y respectively, where H(X) and H(Y) are the entropies of X and Y. However, with joint decoding, if vanishing error probability for long sequences is accepted, the Slepian–Wolf theorem shows that much better compression rate can be achieved. As long as the total rate of X and Y is larger than their joint entropy H(X,Y) and none of the sources is encoded with a rate larger than its entropy, distributed coding can achieve arbitrarily small error probability for long sequences.[1]

A special case of distributed coding is compression with decoder side information, where source Y is available at the decoder side but not accessible at the encoder side. This can be treated as the condition that R_Y=H(Y) has already been used to encode Y, while we intend to use H(X|Y) to encode X. In other words, two isolated sources can compress data as efficiently as if they were communicating with each other. The whole system is operating in an asymmetric way (compression rate for the two sources are asymmetric).[1]

This bound has been extended to the case of more than two correlated sources by Thomas M. Cover in 1975,[2] and similar results were obtained in 1976 by Aaron D. Wyner and Jacob Ziv with regard to lossy coding of joint Gaussian sources.[3]

See also

References

  1. ^ a b c d Slepian & Wolf 1973, pp. 471–480.
  2. ^ Cover 1975, pp. 226–228.
  3. ^ Wyner & Ziv 1976, pp. 1–10.

Sources

External links

  • Wyner-Ziv Coding of Video algorithm for video compression that performs close to the Slepian–Wolf bound (with links to source code).


This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.