loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Eighth IEEE Symposium on Computers and Communications
Fair Noiseless Broadcast Source Coding
Kemer-Antalya, Turkey
June 30-July 03
ISBN: 0-7695-1961-X
Serdar Boztas, RMIT University
We present a noiseless source coding problem in a broadcast environment and supply a simple solution to this problem. A transmitter wishes to transmit a binary random vector X_1^n = (X1, X2, ..., Xn) to n receivers, where receiver k is only interested in the component Xk. A source encoding is a binary sequence f = (f1, f2, ...) which is chosen by the transmitter.
The expected time at which the kth receiver determines Xk (with probability one) is denoted l(f, k). This means that the initial segment (f1, f2, ..., fl(f, k)) of the encoding allows unique decoding of Xk. We define the performance measure
L(n) = \mathop {\min }\limits_f \mathop {\max }\limits_k l\left( {f,k} \right),
where the minimization is over all possible encodings, and wish to approach it by practical schemes.
For the case of independent but not necessarily identically distributed Bernoulli sources, we demonstrate (randomized) encoding schemes f for which
\mathop {\lim }\limits_{n \to \infty } \frac{{\max _k l\left( {f,k} \right)}} {{\left( {n + 1} \right)/2}} = 1
where \frac{{n + 1}} {2} is the arithmetic mean of the values \left( {l\left( {f,k} \right)} \right)_{k = 1}^n obtained by the naive scheme fk = Xk. In the naive scheme, the worst case receiver learns its value only after n bits have been received, so this is a substantial improvement. In conclusion, we constructively establish that the inequality L(n) \le \frac{{n + 3}} {2} holds for stationary, ergodic and bitwise independent sources. We also generalize our results to the case where each receiver is interested in a block of data, as opposed to only one bit. The determination of lower bounds on L(n) is still open.
Citation:
Serdar Boztas, "Fair Noiseless Broadcast Source Coding," iscc, pp.1292, Eighth IEEE Symposium on Computers and Communications, 2003
Usage of this product signifies your acceptance of the Terms of Use.