Communications Research Colloquium and Informal Seminar

School of Electrical and Computer Engineering -- Cornell University

Spring 2003 -- Meetings: Wednesdays, 11am-12:00pm, 310 Rhodes (coffee and cookies available before)
If you would like to give a talk, please get in touch with Sergio Servetto.

Wed 1/29 Yao-Win Hong Bayesian Detector and Adaptive Receivers for TH-SSMA Ultra-Wide Bandwidth Impulse Radio.
Wed 2/05 Toby Berger Neural Interspike Interval Analysis via a PDE.
Wed 2/12 empty slot .
Wed 2/19 Stark Draper Sensor Networks: Side-Information Aware Coding Strategies.
Wed 2/26 Frederique Oggier Two Problems in Coding Theory.
Wed 3/05 Sergio Servetto Rescheduled for 3/26.
Tue 3/11 Vinay Vaishampayan Curves in Communications and Signal Processing. (ECE Colloquium)
Wed 3/19 Spring break. No seminar
Wed 3/26 Sergio Servetto Distributed Signal Processing Algorithms for the Sensor Broadcast Problem.
Wed 4/02 An-swol Hu Detection of Waveforms Generated by a Distributed Transmission Array.
Wed 4/09 Christina Peraki On the Maximum Stable Throughput Problem in Random Networks with Directional Antennas.
Tue 4/15 Alon Orlitsky Better Turing: Asymptotically Optimal Probability Estimation. (ECE Colloquium)
Wed 4/16 Zhiyu Yang Exploiting Protocol Information for Transmission over Unknown Fading Channels.
Wed 4/23 Raff D'Andrea Design of Robust Networked Control Systems.


Speaker:
Yao-win Hong.

Title:
Bayesian Detector and Adaptive Receivers for TH-SSMA Ultra-Wide Bandwidth Impulse Radio.

Abstract:
In this paper, we derive and analyze a Bayesian detector for a multiple access Ultra-Wideband (UWB) system, which only requires the knowledge of the signature code of the user of interest. The receiver structure is equivalent to a single user matched filter (MF) receiver followed by an adaptive threshold. Since the multiple access interference (MAI) is not Gaussian, this detector outperforms the conventional MF detector at the expense of the additional complexity necessary for calculating the adaptive threshold. In the two-user case, we show that as the AWGN tends to zero, the probability of error of the Bayesian detector goes to zero for any finite-length time-hopping codes. This is in contrast to the MF receiver which requires infinitely long codes to achieve the same result. Finally, we propose a linear MMSE adaptive receiver to mitigate MAI with low complexity.

Joint work with Anna Scaglione.


Speaker:
Toby Berger.

Title:
Neural Interspike Interval Analysis via a PDE.

Abstract:
We explore the statistics of the durations of the intervals between efferent spikes produced by a typical neuron in primate neocortex. Such a neuron receives between 200,000 and 2,000,000 afferent spikes per second from a total of circa 10,000 other neurons whose axons connect to synapses on its dendritic tree. Under mild restrictions we show that the overall afferent spike arrival instants are well modeled as a Poisson process. The neuron's post-synaptic potential (PSP) is a linear combination of these afferent stimuli, most of which are excitatory but some of which are inhibitory.

Each time the PSP exceeds a threshold, the neuron produces an efferent spike that propagates along its axon to some 10,000 recipient neurons. Immediately after each spike emission, the neuron's PSP is reset to zero. There follows a brief refractory period during which the neuron is virtually incapable of producing another spike even if its PSP builds up above the threshold.

We assume that the PSP decays exponentially after each afferent contribution until the next contribution arrives. This, in conjunction with the times of occurrence of said contributions constituting a Poisson process, makes the process of efferent spike times a renewal process. That is, in this model successive efferent pulses are separated by interspike intervals (ISI's), or gaps, whose random durations, G_1, G_2, ... are i.i.d.r.v. We seek the probability distribution common to these gap durations, call it F_G(g) = P[G < g], where Grepresents a generic G_i.

The key step toward finding an analytical expression for F_G(g) is to derive and then solve a partial differential equation (PDE) for q_{R|X}(r|x), the probability density function of the residual time R to first passage through the threshold conditional on the PSP's current value X. With the R|X subscript repressed, this PDE reads

{\[\frac{\partial q(r|x)}{\partial r} + (\alpha x - \lambda \bar A)\frac{\partial q(r|x)}{\partial x} = ({{2 \alpha x - \lambda \bar A}\over \lambda}) \frac {{\partial}^2 q(r|x)}{\partial r \partial x},\]}} ,

where \alpha is the PSP decay constant, \lambda is the afferent Poisson arrival rate, and \bar A is the mean algebraic value of a contribution to the PSP.

We show how to solve this PDE with the refractory period explicitly taken into account, and we describe how F_G(g) follows therefrom. The mean and standard deviation of G are evaluated both computationally and via simulation as functions of the model parameters \alpha, \lambda and \bar A. The neuroscientific significance of the findings is then discussed.


Speaker:
Stark Draper.

Title:
Sensor Networks: Side-Information-Aware Coding Strategies.

Abstract:
We develop strategies for signal quantization, data fusion, and estimation under communication constraints in tree-structured sensor networks. Factoring sensor trees into elemental serial (pipeline) and parallel (hub-and-spoke) networks, we develop side-information-aware coding strategies for these networks based on a suitable generalization of Wyner-Ziv source coding with decoder side information. Combining these strategies gives an efficient coding approach to arbitrary sensor trees. Under a sum-rate constraint, the parallel network is closely related to the "CEO" problem. We connect our work to those earlier results. Finally, we apply our results to develop channel coding strategies for certain classes of relay channels.


Speaker:
Frederique Oggier.

Title:
Two Problems in Coding Theory.

Abstract:
The goal of this talk is to briefly present two different topics of coding theory.

Topic 1: A Semidefinite Programming Approach for Network Coding. The first topic can be related to the vector quantization problem. We have a real point that we want to transmit, under rate constraint, over a communication network. We assume that due to length limitation of the input packets, our encoding will be split into smaller packets. Furthermore, we assume that the network will lose packets, and that hard delay constraints disable retransmission. We address the question of designing codes for this problem.

Topic 2: Algebraic Codes for the Rayleigh Fading Channel. The second topic is inspired by work of Boutros et al. They consider communication over the Rayleigh fading channel. Instead of using error-correcting codes, they introduced modulation schemes with intrinsic diversity, based on lattice constellations. Using algebraic methods, we build several families of these lattice constellations. Furthermore, we give explicit formulas to evaluate their performance over the Rayleigh fading Channel.

The first topic is joint work with Sergio Servetto. The second is joint work with Emanuele Viterbo (Politecnico di Torino)


Speaker:
Vinay Vaishampayan.

Title:
Curves in Communications and Signal Processing.

Abstract:
This talk is about bandwidth expansion maps, i.e., functions which map $R$ to $R^N$, $N>1$. Such maps (curves) are studied in communication theory because they underlie nonlinear modulation systems such as frequency modulation. We address the following problem: on the sphere $S^{N-1}$ in $R^N$, construct a curve of maximal length subject to a constraint on the minimum distance between its folds (which we define). A performance analysis is presented, optimal constructions are given and a decoding algorithm is developed. Interesting connections to shift dynamical systems, the cubic lattice (especially its projection into one lower dimension), and Nyquist rate A/D conversion are also highlighted. Finally, I will also review from the literature, some interesting applications of curves in statistics and signal processing.

Collaboration with: Sueli I. R. Costa and N. J. A. Sloane.

Bio: Vinay A. Vaishampayan received the B.Tech degree from the Indian Institute of Technology, Delhi, India, in 1981, the M.S. and Ph.D. degrees from the University of Maryland, College Park, Maryland, in 1986 and 1989, respectively. He works on research problems in the areas of communications, signal processing, statistics and information theory and has a strong interest in geometric aspects of such problems. He works at AT\&T Labs-Research, Shannon Laboratory, Florham Park, NJ, where he heads the Communication Sciences Research Department. Previous experience includes academia, teaching Electrical Engineering at Texas A\&M University, and the oil industry, for Schlumberger Technical Services.


Speaker:
Sergio Servetto.

Title:
Distributed Signal Processing Algorithms for the Sensor Broadcast Problem.

Abstract:
We consider the design of efficient algorithms for the sensor broadcast problem. In this problem, sensors are deployed on a field, and they collect (correlated) samples of a stochastic process that unfolds over the field---the goal then is for each sensor to broadcast a rate constrained encoding of its sample to every other sensor, so that all nodes are able to form an estimate of the entire field, to within a prescribed distortion value. In previous work, we established the existence of solutions to the sensor broadcast problem. In this talk, we present distributed algorithms for computing linear signal expansions that form the core of a sensor broadcast protocol. Fundamental to our claim of practicality is the use of compactly supported wavelets: compact support for the basis functions translates into localized communication patterns---to decorrelate, sensors only need access to samples from a few nearby sensors, irrespective of network size.

Note: this will be a re-run of my talk presented two weeks ago at CISS.


Speaker:
An-swol Hu.

Title:
Detection of Waveforms Generated by a Distributed Transmission Array.

Abstract:
We consider the problem of communication over the reachback channel: this is a channel that arises in the context of wireless sensor networks, where multiple cheap and unreliable nodes pick up correlated samples of some spatial stochastic process, and then they need to communicate their observations back to a remote receiver. We address the problem of designing suitable transmitters for reachback. We assume that all the nodes agree on a common bit of information to send, and that all the sensor nodes cooperate to generate an aggregate signal that can be reliably detected at a far location (even though, in general, the individual signals generated by each node cannot). An important challenge that we face is due to the fact that, with a large number of cheap and unreliable transmitters, it seems unlikely that these transmitters will be able to achieve high precision to synchronize their transmissions in the cooperative transmission step. We present two transmission schemes. The first reachback transmitter uses wideband pulses and we show how the problem of detecting signals generated with unreliable clocks is equivalent to detecting signals that undergo multipath fading, and use this equivalence to derive optimal detection structures for the signals generated by this distributed transmission array. In the second transmitter, each node transmits a square wave. We show that with an infinite number of nodes, the aggregate signal corrupted by jitter noise becomes deterministic. With the consideration of jitter noise, we present an algorithm for optimally placing transition times in the square wave.

This is a dry run for a talk that will be presented at ISIT 2003. Joint work with Sergio Servetto.


Speaker:
Christina Peraki.

Title:
On the Maximum Stable Throughput Problem in Random Networks with Directional Antennas.

Abstract:
We consider the problem of determining rates of growth for the maximum stable throughput achievable in dense wireless networks. We formulate this problem as one of finding maximum flows on random unit-disk graphs. Equipped with the max-flow/min-cut theorem as our basic analysis tool, we obtain rates of growth under three models of communication: (a) omnidirectional transmissions; (b) "simple" directional transmissions, in which sending nodes generate a single beam aimed at a particular receiver; and (c) "complex" directional transmissions, in which sending nodes generate multiple beams aimed at multiple receivers. Our main finding is that an increase of \Theta(\log^2(n)) in maximum stable throughput is all that can be achieved by allowing arbitrarily complex signal processing (in the form of generation of directed beams) at the transmitters and receivers. We conclude therefore that neither directional antennas, nor the ability to communicate simultaneously with multiple nodes, can be expected in practice to effectively circumvent the constriction on capacity in dense networks that results from the geometric layout of nodes in space.

This is a dry run for a talk that will be presented at MobiHoc 2003. Joint work with Sergio Servetto.


Speaker:
Alon Orlitsky.

Title:
Better Turing: Asymptotically Optimal Probability Estimation.

Abstract:
During World War Two, I.J. Good and A.M. Turing considered the problem of estimating a probability distribution from a sample of data. They derived a surprising and unintuitive formula that has since been used in a variety of applications and studied by a number of researchers.

Borrowing an information-theoretic and machine-learning framework, we define the attenuation of an estimator as the ratio between the probability assigned to each symbol in a sequence by any distribution, and the corresponding probability assigned by the estimator. We show that the Good Turing estimator performs well in the sense that its attenuation is at most 2, however it is suboptimal in the sense that for some sequences its attenuation is at least 1.39. We then derive an estimator whose attenuation approaches 1, namely, as the length of any sequence increases, the ratio between the probability assigned to each symbol by any distribution, and that assigned by the estimator is at most one.

To better understand the behavior of the estimator, we study the probability it assigns to several simple sequences. We show that for some sequences this probability agrees with our intuition, while for others it is quite unintuitive.

Joint work with N. Prasad Santhanam and Junan Zhang.

Biography: Alon Orlitsky received B.Sc. degrees in Mathematics and Electrical Engineering from Ben Gurion University in 1980 and 1981, and M.Sc. and Ph.D. degrees in electrical engineering from Stanford University in 1982 and 1986.

From 1986 to 1996, Dr. Orlitsky was with the Communications Analysis Research Department of Bell Laboratories. From 1996 to 1997 he was a quantitative analyst at D.E. Shaw and Company, an investment firm in New York City. In 1997 he joined the University of California in San Diego where he is currently a professor of Electrical and Computer Engineering and of Computer Science and Engineering.

Dr. Orlitsky's research concerns information theory, learning, and speech recognition. He is a recipient of the 1981 ITT International Fellowship and of the 1992 IEEE W.R.G. Baker Paper Award.


Speaker:
Zhiyu Yang.

Title:
Exploiting Protocol Information for Transmission over Unknown Fading Channels.

Abstract:
We consider the transmission of two independent sources with different priorities over unknown fading channels. One source (protocol information) has a low information rate and a delay constraint. The other source has a high information rate and no delay constraints. We study a receiver structure in which the protocol information is first decoded incoherently and then fed back to facilitate coherent decoding for the high-rate information.

We derive lower bounds on the achievable rate for the high-rate source by this decision directed structure. These bounds are given as functions of the low-rate message error probability \gamma, which characterizes the impact of \gamma on the performance of the system. It is shown that, in terms of the achievable rate for the high-rate information, the decision directed scheme achieves the performance of the known-training scheme as \gamma goes to zero.

Joint work with Lang Tong.


Speaker:
Raff D'Andrea.

Title:
Design of Robust Networked Control Systems.

Abstract:
In this talk I will describe new tools, based on semi-definite programming, for designing robust networked control systems. The computational complexity of these tools is dictated by the underlying interconnection topology, and thus great computational savings can be achieved when considering interconnection graphs with regular or sparse structures. The resulting control systems have desirable implementation properties: the computation is distributed, and the control system's communication network has the same structure as that of the system to be controlled.