# ITA Workshop : source and channel coding

There were some talks on dynamic spectrum access as well as waterfilling and other resource allocation problems.

• Twice-universal types and simulation of individual sequences (Alvaro Martín, Universidad de la República, Neri Merhav, Technion, Gadiel Seroussi, Universidad de la República, and Marcelo J. Weinberger, HP Labs)

A universal source code partitions the set of all length-n sequences so that under an iid model class into types, so that two sequences that have the same type have the same probability. If we look at order-k Markov sources, we can ask for a universal code that is universal for all n and k. This leads to twice-universal source codes. Given a Markov-order esimator that takes a sequence and estimates an order k, we can intersect the set of sequences with the same order with the type class of order k. Given some conditions on the quality of the order estimator, this partition has some nice properties, including simulation of individual sequences with similar empirical statistics.

• Universal noiseless compression for noisy data (Gil I. Shamir, University of Utah, Tjalling J. Tjalkens, Frans M. J. Willems, Eindhoven University of Technology)

We’d like to be able to compress noisy data, since sometimes we only have access to noisy data. What they propose is a new probability estimator that can take into account upper and lower bounds on the probability to be estimated. So if I know the true probability lies in [a,b] I can use that knowledge in the estimator. When a = 0, b = 1 this reduces to the Krichevsky-Trofimov (KT) estimator. Intuitively, noise reduces the richness of the model class, and hence reduces the redundancy. Some properties of the esimator and corresponding compression results were given.

• On universal coding of unordered data (Lav R. Varshney and Vivek K Goyal, MIT)

Suppose you want to compress data but don’t care about the order of the data (think database records for concreteness) — then using a source code for vectors is silly, since you want a source code for multisets. In this work they address universal coding for multisets , and show that universal lossless coding is impossible, but a low universal rate is achievable across the model class (iid sources I believe, but it might be more general).

• Sum-Capacity of a Degraded Gaussian Multiaccess Relay Channel (Lalitha Sankar, WINLAB, Rutgers, Gerhard Kramer, Bell Labs, and Narayan B. Mandayam, WINLAB, Rutgers)

For a physically degraded multiple-access relay channel (MARC), the decode-forward inner bound and old outer bounds do not match in general. But by making new outer bounds that exploit the causality of the relay, an optimized decode-forward scheme meets the outer bound.

• Secrecy generation for channel models (Imre Csiszar, Renyi Institute, Budapest, and Prakash Narayan, Univ. of Maryland, College Park, USA)

I am not as familiar with the 2004 paper on which this work builds (but I’m reading it now). The model is that an encoder transmits a vector into a DMC with many outputs. Other terminals each view one output and then can engage in public discussion that is overheard by an eavesdropper. The terminals must come up with a secret key that is secret from the eavesdropper. The results are related to a multerminal source problem that was discussed earlier.