TY - GEN
T1 - Variable-rate universal Slepian-Wolf coding with feedback
AU - Sarvotham, Shriram
AU - Baron, Dror
AU - Baraniuk, Richard G.
PY - 2005
Y1 - 2005
N2 - Traditional Slepian-Wolf coding assumes known statistics and relies on asymptotically long sequences. However, in practice the statistics are unknown, and the input sequences are of finite length. In this finite regime, we must allow a non-zero probability of codeword error e and also pay a penalty by adding redundant bits in the encoding process. In this paper, we develop a universal scheme for Slepian-Wolf coding that allows encoding at variable rates close to the Slepian-Wolf limit. We illustrate our scheme in a setup where we encode a uniform Bernoulli source sequence and the second sequence, which is correlated to the first via a binary symmetric correlation channel, is available as side information at the decoder. This specific setup is easily extended to more general settings. For length n source sequences and a fixed ε, we show that the redundancy of our scheme is O(√n -1(ε)) bits over the Slepian-Wolf limit. The prior art for Slepian-Wolf coding with known statistics shows that the redundancy is (√/n -1(ε)). Therefore, we infer that for Slepian-Wolf coding, the penalty needed to accommodate universality is (√/n -1(ε)).
AB - Traditional Slepian-Wolf coding assumes known statistics and relies on asymptotically long sequences. However, in practice the statistics are unknown, and the input sequences are of finite length. In this finite regime, we must allow a non-zero probability of codeword error e and also pay a penalty by adding redundant bits in the encoding process. In this paper, we develop a universal scheme for Slepian-Wolf coding that allows encoding at variable rates close to the Slepian-Wolf limit. We illustrate our scheme in a setup where we encode a uniform Bernoulli source sequence and the second sequence, which is correlated to the first via a binary symmetric correlation channel, is available as side information at the decoder. This specific setup is easily extended to more general settings. For length n source sequences and a fixed ε, we show that the redundancy of our scheme is O(√n -1(ε)) bits over the Slepian-Wolf limit. The prior art for Slepian-Wolf coding with known statistics shows that the redundancy is (√/n -1(ε)). Therefore, we infer that for Slepian-Wolf coding, the penalty needed to accommodate universality is (√/n -1(ε)).
UR - http://www.scopus.com/inward/record.url?scp=33847617537&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33847617537&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:33847617537
SN - 1424401313
SN - 9781424401314
T3 - Conference Record - Asilomar Conference on Signals, Systems and Computers
SP - 8
EP - 12
BT - Conference Record of The Thirty-Ninth Asilomar Conference on Signals, Systems and Computers
T2 - 39th Asilomar Conference on Signals, Systems and Computers
Y2 - 28 October 2005 through 1 November 2005
ER -