Abstracts of talks, Fall 2006

Information and Coding Theory Seminar

Abstracts of talks

Fall 2006

9/20 Prakash Narayan (UMD), Slepian-Wolf Data Compression and Linear Channel Codes

ABSTRACT:
It has long been known that Slepian-Wolf data compression, i.e., compression of a source sequence when the decoder is aided by additional access to correlated side-information, can be performed at the optimal rate using a linear encoder [Csiszar, 1982]. For the special case in which the source sequence and the decoder's side-information are connected by a virtual additive noise channel, Wyner [1978] had shown earlier how the source sequence could be compressed at the optimal (Slepian-Wolf) rate using a suitable linear code for this virtual channel. In a recent paper in the Proceedings of the 2006 IEEE International Symposium on Information Theory, Da-ke He and En-Hui Yang have examined the duality between Slepian-Wolf data compression and linear channel codes for the general situation in which the source sequence and the decoder's side-information are arbitrarily correlated.

This body of work, culminating in the recent He-Yang result, will be discussed.

Reference: He-Yang

9/27 Alexander Barg (UMD), Two topics in error-correcting codes: Locally testable codes and the Gilbert-Varshamov bound

ABSTRACT:
1) Locally testable codes: given a linear binary code C of length n, we would like to provide an algorithm that will tell whether a given vector y in {0,1}^n is in C or is (epsilon n) away from C. An algorithm is called a tester if it gives a correct answer with probability close to 1 by looking at a constant number of randomly chosen bits of y. The notion of locally testable codes (for Hadamard codes, or Reed-Muller codes of the first order) first arose in (relation to) the proof of the celebrated PCP theorem Following N. Alon et al. (IEEE IT, Nov. '05), we will prove that Reed-Muller codes of any order are locally testable. Related results and an open problem will be mentioned.

2) The Gilbert-Varshamov bound: Jiang and Vardy ('04) have shown that it is possible to construct binary linear codes that are better than the GV bound by a factor \Omega(n). Gaborit and Zemor have recently shown the same for double circulant codes. We will prove their result and mention an application of these works to sphere packing.

Reference: Gaborit-Zemor

10/4 Nuno Martins (UMD), Coding for Additive White Noise Channels with Feedback Corrupted by Uniform Quantization or Bounded Noise

ABSTRACT:
We present simple coding strategies, which are variants of the Schalkwijk-Kailath scheme, for communicating reliably over additive white noise channels in the presence of corrupted feedback. More specifically, we consider a framework comprising an additive white forward channel and a backward link which is used for feedback. We consider two types of corruption mechanisms in the backward link. The first is quantization noise, i.e., the encoder receives the quantized values of the past outputs of the forward channel. The quantization is uniform, memoryless and time invariant (that is, symbol-by-symbol scalar quantization), with bounded quantization error. The second corruption mechanism is an arbitrarily distributed additive bounded noise in the backward link. Here we allow symbol-by-symbol encoding at the input to the backward channel. We propose simple explicit schemes that guarantee positive information rate, in bits per channel use, with positive error exponent. If the forward channel is additive white Gaussian then our schemes achieve capacity, in the limit of diminishing amplitude of the noise components at the backward link, while guaranteeing that the probability of error converges to zero as a doubly exponential function of the block length. Furthermore, if the forward channel is additive white Gaussian and the backward link consists of an additive bounded noise channel, with signal-to-noise ratio (SNR) constrained symbol-by-symbol encoding, then our schemes are also capacity-achieving in the limit of high SNR.

Joint work with Tsachy Weissman.

Reference: Martins-Weissman (submitted to IEEE Trans. on IT, abridged version published in Allerton '06)

10/11 Vijay Gupta (UMD), Data Transmission over Networks for Estimation and Control

ABSTRACT:
We will consider the problem of estimation of a linear dynamic process across an arbitrary network of communication links that drop packets stochastically. We will identify the optimal information processing strategy at each node that allows the estimator to calculate the best possible estimate in the minimum mean squared error sense. For the case when the drop probabilities are memoryless and independent across links, we will analyze the stability and performance for our algorithm.

Reference: Gupta et al., Dana et al.

10/25 N. Prasanth Anthapadmanabhan (UMD), Capacity of binary fingerprinting with two pirates

ABSTRACT:
Digital fingerprinting is a technique to prevent the piracy of copyrighted content. It is accomplished by assigning to each licensed user a unique mark, called a "fingerprint", which is hidden within the content. A coalition of users, termed "pirates", may compare their copies to identify some fingerprint positions and create a pirated copy with a modified fingerprint. The objective is to assign fingerprints in a way that enables the distributor to identify at least one of the members of the coalition to have created the pirated copy as long as the coalition size does not exceed a certain threshold t, which is a parameter of the problem. A single-letter expression (involving mutual information terms) is obtained as an upper bound on the capacity (maximal rate) of fingerprinting codes secure against coalitions of size two by modeling fingerprinting as a communication problem and using an information-theoretic approach. For the special case of fingerprinting with two pirates over the binary alphabet, we obtain a random coding lower bound which matches with the previous upper bound and establishes the exact value of capacity for this case as 0.25.

(Joint work with A. Barg, I. Dumer and P. Narayan)

11/1 Sirin Nitinawarat (UMD), A Graph-based Framework for Transmission of Correlated Sources over Multiple Access Channels

ABSTRACT:
The problem of finding a necessary and sufficient condition for reliable transmission of correlated sources over a multiple access channel has remained open since its formulation in the early '70. It had been realized shortly after that a naive way to communicate in this setting: firstly perform lossless source encoding; and secondly encode each codebooks separately by the MAC channel code, can be strictly suboptimal. In this article, the authors are working towards giving a new sufficient condition to this problem. The authors persist on using the above separation, namely first coding for the source and then coding for the MAC channel. A novel idea is to introduce a new discrete object between this separation which they call semi regular bipartite graph. Motivation will be discussed as to why this object arises as a natural candidate to this problem. The results are then presented. Lastly, we comment on the prospect of realizing the final goal: establishing a new sufficient condition for the problem.

Reference:
"A graph-based framework for transmission of correlated sources over multiple access channels", S. S. Pradhan, S. Choi and K. Ramchandran, Submitted to IEEE Transactions on Information Theory, January, 2006.

11/8 Armand Makowski (UMD), Geometric random graphs on the unit interval (Part I)

ABSTRACT:
We consider the simplest of geometric random graphs, namely the one generated by independent nodes which are uniformly distributed on the unit interval. We study its connectivity properties, namely the corresponding zero-one laws and underlying phase transitions. The presentation will be self-contained!

Slides from the talk

11/14 Rudolf Ahlswede (Universität Bielefeld), Identification Entropy (joint with HyNet Colloquium)

ABSTRACT: click here

Suggested advance reading: identropy1, identropy2, identification

12/4 Armand Makowski (UMD), Geometric random graphs on the unit interval (Part II)

Slides from the talk

12/6 Nan Liu (UMD), Dense Gaussian Sensor Networks: Minimum Achievable Distortion and the Order Optimality of Separation

ABSTRACT:
We investigate the optimal performance of dense sensor networks by studying the joint source-channel coding problem. The overall goal of the sensor network is to take measurements from an underlying random process, code and transmit those measurement samples to a collector node in a cooperative multiple access channel with potential feedback, and reconstruct the entire random process at the collector node. We provide lower and upper bounds for the minimum achievable expected distortion when the underlying random process is Gaussian. When the Gaussian random process satisfies some general conditions, we evaluate the lower and upper bounds explicitly, and show that they are of the same order for a wide range of power constraints. Thus, for these random processes, under these power constraints, we express the minimum achievable expected distortion as a function of the power constraint. Further, we show that the achievability scheme that achieves the lower bound on the distortion is a separation-based scheme that is composed of multi-terminal rate-distortion coding and amplify-and-forward channel coding. Therefore, we conclude that separation is order-optimal for the dense Gaussian sensor network scenario under consideration, when the underlying random process satisfies some general conditions.

Joint work with S. Ulukus, submitted to IEEE Trans. on IT. (Liu-Ulukus)

12/13 Brooke Shrader (UMD), Fountain Codes and Fountain Capacity

ABSTRACT:
We will discuss the use of fountain codes for distribution of data over the erasure channel. We will examine two different types of fountain codes (LT codes and Raptor codes) with an emphasis on the encoding/decoding complexity. We will then discuss a new formulation of capacity for fountain coding.

Reference: Shokrollahi, Shamai et al