Figure 1: Proposed LVA-CED system for magnetic recording
The exponential-server timing channel (ESTC) is one in which the sender chooses times at which identical jobs are submitted to a single-server queue with an exponential service time distribution, while the receiver observes their departure times. Our interest in this channel is due to its canonical nature and the central role it plays in the study of covert timing channels, in which the sender sends messages containing irrelevant or misleading information, and actually communicates with the receiver using the timing of the messages, unknown to a casual observer.
Previous work has established the Shannon capacity of the channel [1], and the random-coding and sphere-packing bounds on its reliability function [2]. The bounds prove that the reliability function is at least as large as the reliability function of the well-known Poisson channel [3,4], and that the two reliability functions coincide at rates close to their common capacity. We have proved that at sufficiently low rates, the reliability function of the ESTC lies strictly above the Poisson channel's, answering in the negative the open question of whether the two reliability functions coincide at all rates [2]. Our results reveal a distance metric between codewords for the ESTC that parallels Hamming distance for the binary symmetric channel and Euclidean distance for the Gaussian channel. We are currently attempting to determine the zero-rate error exponent of the ESTC exactly.
When the sampling rate at the output of a channel carrying coded information varies, the performance of the decoder can be significantly degraded. For example, for simple linear codes, even as the SNR goes to infinity, one cannot successfully decode the input sequence because two or more distinct input sequences can potentially give rise to the same output sequence.
To address this issue, we adopt the following model. An input sequence is first encoded by a linear block code. The output is then passed through a set of linear transformations, which model the uncertainty of the sampling rate. The transformations include, for the simplest case, a family of identity matrices with one column repeated, or more generally, a symbolic dynamics (d,k) pattern.
Our goal is to identify which conditions impose on the linear block code, and in which properties of the family of the transformations no two input sequences result in the non-zero overlapping set of outputs. We also want to determine the most efficient precoding technique which will eliminate the identification problem while keeping the rate of the code as high as possible.
It was shown recently in [1] that the well known belief propagation algorithms for posterior probability evaluation can be viewed as algorithms that aim to minimize certain approximations to the variational free energy in a statistical physics context. Specifically, the fixed points of belief propagation algorithms are shown to coincide with the stationary points of Bethe's approximate free energy subject to certain consistency constraints. Bethe's approximation is known to be a special case of a more general class of approximations called Kikuchi free energy approximations. A more general class of belief propagation algorithms was thus introduced which corresponds to algorithms that aim to minimize a general Kikuchi approximate free energy.
In this reseach we develop and extend this general method of approximation. Specifically, given an arbitrary collection of regions, i.e., proper subsets of a set of state variables, and a collection of functions of the configuration of state variables over these regions, we define a general constrained minimization problem corresponding to the general Kikuchi approximation whose stationary points approximate marginals over these regions of the product function, and we specify a general class of local message-passing algorithms along the edges of a graphical representation of the collection of Kikuchi regions, which attempt to solve that problem (see [2]). We have also developed a suitable minimal graphical representation of the collection of regions (see [3]). Iterative message-passing algorithms on the graph we construct involve fewest message updates at each iteration. We have proven that exactness of Kikuchi approximation of marginals depends directly on this graph being cycle-free, and we have conditions for convexity of the Kikuchi function based on the properties of the minimal graph of regions.
In this project, we investigate the effect of using multilevel signaling with coded modulation techniques for fiber-optical communication systems with optical amplifiers. Such systems are usually dominated by the beat noise of amplified spontaneous emission. After square-root transforming the received signal, we apply the coded modulation schemes such as trellis-coded modulation and multi-level coding, which lead to significant power gain. Further improvements are made by jointly optimizing the coded modulation and the signal constellation.
In this project, we study the theory of lattice code shaping and nonequiprobable signaling for optical systems. Previous work has established results for coherent detection systems [1] and direct-detection systems without amplifiers [2].
Our work focuses on the theory of shaping and nonequiprobable signaling for amplified direct-detection systems. In such systems, the intensity-modulated signals are corrupted by the signal-spontaneous emission beat noise, which is proportional to the signal intensity.
In this project, we propose and analyze the list Viterbi algorithm (LVA) with an arithmetic coding-based continuous error detection (CED) scheme for transmission on inter-symbol interference (ISI) channels. We have shown that the system localizes error occurrences to the end of the transmission and that the proportion of bits where errors are likely to occur asymptotically approaches zero as the inverse of the number of transmitted bits. We analytically derived an upper bound on the bit error rate (BER) of the LVA-CED system as a function of the redundancy added by the CED code, the number of bits transmitted, and the BER when the standard maximum likelihood detector is used on the same channel. We analytically derived the number of paths required by the LVA for a target error rate. To show the benefits of these theoretical results in a practical setting, we have applied the system to high-order partial-response magnetic recording channels. Simulations show that this system results in a 2 dB improvement over maximum transition run (MTR) encoded EEPR4 partial response decoding with maximum likelihood sequence detection (EEPRML) at a BER of 2 x 10-6 in additive white Gaussian noise, and confirm the theoretical predictions.
Figure 1: Proposed LVA-CED system for magnetic recording
Recent advancements in wireless communications and electronics have led to the development of sensor networks. Applications for sensor networks can be found in many different areas, including military, office, and home. In sensor networks, unlike in ad hoc networks, the most critical factors are not bandwidth efficiency, packet throughput, or latency, but power efficiency and scalibility. These different emphases make the design choices over the protocol stack in sensor networks very different from in ad hoc networks.
In this project, we build a power model including both the physical layer and datalink layer, with various wireless channel models assumed. We consider power consumption in actual circuit components as well as from a communication prospective (SNR/BER). Taking circuit complexity into account when considering power consumption, we found that the traditional way of designing communication systems (modulation/demodulation, MAC protocol, error control coding, etc.) does not necessarily lead to the optimum result. In this project, we intend to analyze the tradeoffs between low power and acceptable QoS in a sensor network, integrate across both the physical and datalink layer, and find the optimum operating point.
My research introduces a framework where models for components in the data link layer are brought together with models for the network layer and the channel. This framework includes all the factors that influence the design of the data link layer and enables us to study the design of any component in the data link layer in the context of other components and layers. As a case study, we have built models for commonly used MAC/Link designs. We applied Banach’s fixed point theorem to solve the closed loop problem we encountered. We verified our models with network simulations using OMNET++. We also studied the impact of some important parameters.
As a part of the PicoRadio project to build a ubiquitous ad-hoc wireless sensor node network, the physical layer has to provide a reliable point-to-point radio link under very tight power constraints. The analog transceiver building blocks make up a large percentage of the overall power budget. In order to minimize the amount of energy needed to convey one bit of information, new strategies have to be employed which take into account the power consumption not only in a communication theoretic sense in the form of energy transmitted over the channel, but also the energy needed to meet performance requirements of the analog and digital building blocks in the receiver chain. Following this approach, the PicoRadio RF group is implementing a transceiver utilizing the least number of analog components possible together with promising new technologies like RF-MEMS [1]. To evaluate the performance, my research focuses on modeling the radio link, including these blocks. I developed a behavioral simulation framework for a point-to-point link and further abstracted the design into an analytical model. From this model, we can derive performance specifications for the blocks under development and can use them in the design process.
The downlink problem in a wireless system with multiple transmit antennas and multiple users can be modeled by a multiple input multiple output Gaussian broadcast channel. The capacity region of this channel is still an open problem. Caire and Shamai [1] applied a technique known as "dirty-paper coding," due to Costa [2], to find an achievable region. It was later shown [3] that the maximum sum rate of this region is also the maximum possible sum rate. It is widely believed that this achievable region is in fact optimal. We attempt to show that this conjecture is true at high SNRs. We hope that solving this problem would give insights into the general problem.
Sampling theory has been a topic of extensive research over the past decade, which has led to a reexamination of some of the foundations of Shannon's theory, and development of more general formulations with immediate relevance to signal processing and communications. Recently, it has been shown that it is possible to develop sampling schemes for a large class of non-bandlimited signals, namely certain signals of finite innovation rate [1,2]. A common feature of these signals is that they allow for a parametric representation with a finite number of degrees of freedom, and can be perfectly reconstructed from a finite set of samples. We consider one possible application of our sampling results to be the problem of timing synchronization and channel estimation in wideband communication systems, such as ultra-wideband and CDMA systems.
Synchronization in wideband communication systems is a crucial task that imposes serious restrictions on system performance. Vast literature has appeared recently, addressing both algorithmic and implementation issues of various synchronization techniques, with a clear trend toward eliminating the necessity for analog components as much as possible and performing all processing digitally. Even though many high-performance schemes have already been proposed, their application in real time systems is often not feasible due to their high computational complexity. Furthermore, almost all of them use the Nyquist sampling rate, which requires very fast and expensive A/D converters and therefore high power consumption. This problem becomes critical in ultra-wideband systems, where in digital-oriented solutions A/D converters must operate in the gigahertz range.
We propose a low-complexity timing synchronization method that uses low-rate uniform sampling and well-developed algorithmic solutions. Specifically, we extend some of our sampling results [2] to the problem of multipath delay estimation in wideband channels and develop an algorithm for estimating unknown propagation delays from a low-dimensional subspace of a received signal [1]. Our approach leads to reduced computational requirements and lower power consumption compared to existing techniques, thus allowing for a practical hardware implementation and all the benefits of a digital design.
We propose a constructive framework for distributed lossless source coding of two binary sources that have arbitrary correlation structures (Figure 1), i.e., not just symmetric correlation structures of the form of Y = X + N where X and N are independent. Our proposed framework accommodates the important special case of the absence of any correlation between the two sources, wherein it becomes an entropy coding scheme for a single source (Figure 2). This framework is obtained by combining Low-density parity check (LDPC) codes with the distributed source coding using syndromes (DISCUS) framework of [1]. This combined algorithm is powerful enough to reach the Slepian-Wolf bound for two memoryless binary sources and the entropy rate for a single memoryless binary source.
Figure 1: Block diagram of symmetric DISCUS. Two sources are compressed independently and reconstructed at the receiver.
Figure 2: Symmetric DISCUS construction used for lossless coding, or in the special case of zero correlation between sources.
We propose a novel approach to reducing energy consumption in sensor networks using a distributed adaptive signal processing framework and efficient algorithms. While the topic of energy-aware routing to alleviate energy consumption in sensor networks has received attention recently, in this project, we propose an orthogonal approach to previous methods. Specifically, we propose a distributed way of continuously exploiting existing correlations in sensor data based on adaptive signal processing and distributed source coding principles. Our approach enables sensor nodes to blindly compress their readings with respect to one another without the need for explicit and energy-expensive inter-sensor communication to effect this compression. Furthermore, the distributed algorithm used by each sensor node is low in complexity and easy to implement, while an adaptive filtering framework is used to continuously learn the relevant correlation structures in the sensor data. Our simulations show the power of our proposed algorithms, revealing their potential to effect significant energy savings (from 15%-40%) for typical sensor data corresponding to a multitude of sensor modalities.
Figure 1: Distributed source coding setup: node with reading X must compress the reading to close to H(X|Y) without knowing Y
Figure 2: Many sensor nodes reporting to a data-gathering node are clustered according to the correlations of their readings.
There has been a lot of interest recently in applying channel coding with side information (CCSI) concepts to data hiding. Part of the interest stems from the fact that information theoretic bounds can be derived for such systems. In this project, we model the audio data embedding problem as a parallel CCSI problem. This is done by dividing the audio spectrum into frequency bins and then treating each bin as a separate CCSI channel. A perceptual mask is derived from the audio signal to determine the amount of power to use in each channel. It acts as a "water-filling" formula by determining the amount of distortion that can be introduced into each frequency bin without introducing audible distortion. As a result, our data embedding scheme will be imperceptible to the human ear. We will show in this project how a variable-rate trellis construction can be used in conjunction with a perceptual mask to embed data. We will also show how the perceptual mask can be seamlessly conveyed from encoder to decoder. An exciting application for our audio data embedding solution is to embed data within the audio signal that will enable surround sound at the receiver. The resulting surround sound system will be better than existing surround sound systems that are based on manipulating two stereo channels to derive the other surround channels.
Many current applications such as data hiding and watermarking can be posed as the problem of channel coding with side information. There has been considerable interest in designing codes to try and attain the theoretical capacity of the problem. In order to achieve capacity, a powerful channel codebook that partitions into a powerful source codebook should be chosen. The data to be embedded will index the source codebook partition. The constructions that exist in the literature, however, are typically based on powerful channel codebooks and weak source codebooks and hence remain at a considerable gap to capacity. In this project, we present two methods of construction that are based on a powerful channel codebook (i.e., turbo codes) and powerful source codebook partitions (i.e., trellis coded quantization) to try and bridge the gap to capacity.
1Visiting Professor, University of Michigan
We study the problem of rate-constrained robust estimation of noisy sensor measurements in an unreliable sensor network. Noisy measurements of physical process X (e.g., temperature) made by individual sensors need to be communicated to a central observer over unreliable channels. Limited power resources of the sensors place a strong limit on the resolution with which the noisy sensor readings can be transmitted. Both the sensors and the communication links can break down. However, the central observer is guaranteed to reliably receive readings from a minimum of k out of n sensors. The goal of the central observer is to estimate the observed physical process from the received transmissions where a specified distortion metric provides an objective measure of estimation quality. In this work, we derive an information-theoretic achievable rate-distortion region for this problem when the sensor measurement noise statistics are symmetric with respect to the sensors.
In the special case of a Gaussian sensor network, i.e., when the source is i.i.d. Gaussian, the sensor noise processes are additive i.i.d. Gaussian, and the distortion metric is mean squared error, we have the following remarkable result. When any k out of n unreliable sensor transmissions are received, the central decoder's estimation quality can be as good as the best reconstruction quality that can be achieved by deploying only k reliable sensors and the central decoding unit is able to receive transmissions from all k sensors. Furthermore, when more than k out of the n sensor transmissions are received, the estimation quality strictly improves.
Figure 1: An unreliable sensor network. A noisy version of source X is
observed at each of the n sensors. The noisy observations
Y1,...,Yn are encoded and the encoded
indices I1,...,In are transmitted. The
network delivers some m >= k indices. The decoder
obtains the best possible reconstruction of X from the received
indices.
Figure 2: Random code construction. n independent random codebooks of
block length l are constructed, each containing
2lR' codewords. Each codebook is randomly
partitioned into 2lR bins each with approximately
2l(R'-R) codewords.
Figure 3: Structure of sensor encoders that can achieve rate-distortion
performance. The encoder of each sensor consists of a rate R'
quantizer, for block length l, followed by a rate R
random binning function.
Figure 4: Structure of the central observer decoder that can achieve
rate-distortion performance. The central observer first decodes the
received indices to intermediate representations of length l,
and then forms the best estimate of the source. Here, m >= k.
1Postdoctoral Researcher
2Postdoctoral Researcher
3Professor, University of Michigan, Ann Arbor
MIMO channels with perfect channel state information (CSI) at the receiver and Rayleigh flat faded channel gains i.i.d. across antenna pairs have a capacity that grows as min(nt, nr) log SNR for large SNR, where nt and nr are the number of transmit and receive antennas, and SNR is the signal to noise ratio [1,2]. The parameter min(nt, nr) can be interpreted as the number of degrees of freedom (d.o.f.) of the channel: the dimension of the space over which communication can take place.
In high mobility applications the perfect CSI assumption may not be reasonable. If one relaxes this assumption the channel uncertainty at high SNR may have a significant impact on performance. This leads to the question: what is the high SNR capacity of time-varying fading channels without the prior assumption of CSI? Recent results indicate that the first order term in the high SNR capacity expansion is log log SNR regardless of nt and nr [3,4]. This implies that at sufficiently large SNR the benefit of having multiple transmit and receive antennas appears only as a second order effect, and hence the increase in the number of d.o.f. has minimal impact.
The above result is obtained by keeping the channel variation process fixed while taking the SNR to infinity, so its regime of validity corresponds to the case of a noise level much smaller than the channel variation between samples. However, typical wireless channels are underspread, which means that this variation is small. In this work we consider the capacity of underspread MIMO fading channels without CSI when the SNR goes to infinity while the channel variation between samples goes to zero simultaneously. We define three regimes of operation based on the relationship between the SNR and the channel variation. We show that in the first two regimes the capacity is proportional to the degrees of freedom in the channel and argue that most practical systems operate in these two regimes. This suggests that in underspread fading channels, multiple antennas provide significant gains and the concept of degrees of freedom is a useful measure of that performance gain, even without the assumption of perfect CSI.
GASNet [1] is a network-independent and language-independent high-performance communication interface intended for use in implementing the runtime system for global address space languages, such as Unified Parallel C (UPC) [2] or Titanium [3]. GASNet stands for "Global-Address Space Networking."
Goals of this research include:
Figure 1 shows the organization of the GASNet communication layer and its relation to the parallel language system.
The GASNet interface is divided into two distinct layers:
GASNet Core API
GASNet Extended API
GASNet has already been implemented on Myrinet/GM, Quadrics/elan, IBM/LAPI, and MPI (a fully portable implementation), and implementations are on the way for Infiniband, Gigabit Ethernet and other high-performance networks. This research effort includes carefully evaluating the performance characteristics for the target high-performance networks and interfaces [4], and developing strategies for best utilizing the network capabilities to implement low-latency, low-overhead, one-sided small put/gets and zero-copy high-bandwidth bulk transfers [5].
Figures 2 and 3 demonstrate the small-put/get "round-trip" latency and large-put/get bandwidth achieved by the Myrinet and Quadrics implementations of GASNet in various configurations and on several machines. The leftmost bar for each machine shows the performance of the fully portable GASNet-MPI implementation on that system (MPI-based core API, reference implementation of extended API). The middle bar for the Quadrics machines shows the performance of using the reference extended API with a natively-implemented GASNet-Quadrics core API. The rightmost bar for each machine shows the performance of a fully-native implementation of the GASNet core and extended API on the underlying network. We find this performance to be very competitive with the best performance achievable on these networks, therefore justifying the claim that GASNet is indeed a very lightweight, high-performance interface.
Figures 4 and 5 show the small-put/get "round-trip" latency for the fully-native GASNet-Quadrics and GASNet-Myrinet implementations over varying message sizes.
This work is done in conjunction with the Berkeley UPC compiler group, a joint effort between Lawrence Berkeley National Laboratory and UC Berkeley. GASNet is already being used as a communication system for the Berkeley UPC compiler and the UC Berkeley Titanium compiler, and several other global address space language research efforts are considering adopting GASNet.
Figure 1: High-level system organization for a GAS language using GASNet
Figure 2: Small put/get "round-trip" latency performance of GASNet-Myrinet and GASNet-Quadrics in several configurations and machines
Figure 3: Large put/get bandwidth performance of GASNet-Myrinet and GASNet-Quadrics in several configurations and machines
Figure 4: Put/get "round-trip" latency performance of GASNet-Quadrics over varying message size
Figure 5: Put/get "round-trip" latency performance of GASNet-Myrinet over varying message size