ENG SC500 A1 Spring 2006
(Statistical Theory of Communication)
Project presentations:
Presentation time: 10 mins (hard limit) for
solo projects and 15 mins (hard limit) for 2 person
group projects.
Speakers, titles,
and abstracts
Karin Griffis
Context Based Image Compression with the Burrows Wheeler Transform
Abstract
Lossless compression techniques remove data redundancy where different
methods exploit different models to capture the redundancy. Common
model scales are single symbol repetition based (RLC), symbol pattern
repetition based (LZW) and symbol context based (BWT or PPM). The
Burrows Wheeler Transform (BWT), also called block sorting, is a
technique traditionally used to make text files better suited for
compression by arranging the file so that characters with similar
contexts are grouped together in the output. In this work a 2D image
compression scheme which exploits 2D contexts via the Burrows Wheeler
Transformation is presented. Two different block based methods are
developed where one method utilizes the DCT to extract horizontal,
vertical and diagonal correlations and the other is dictionary based
where each block is mapped to an alphabet symbol which will be the
basis for the context, thus allowing for 2D patterns to be used for
the basis of the context.
[Talk viewgraphs]
Danny Morris
Information Theory and Perceptual Audio Coding
Abstract
When compressing an audio signal it is important to retain the quality
of the source with out a large perceptual distortion. Strict lossless
coding can not provide high rates of compression due to the lack of
statistical redundancies in an audio signal. In order to achieve these
high rates it is possible to apply lossy coding that is perceptually
lossless. By using a psychoacoustic model of the human ear it is
possible to create a global masking threshold for just-noticeable
distortion. When separating an audio signal into critical frequency
bands, each band is allocated a certain number of bits. As long as the
distortion created by allocating such bits is below the global masking
threshold the compressed signal will be perceptually indistinguishable
from the source. When minimizing the mutual information between the
source and the compressed signal with the constraint that the
distortion cannot be larger than the global masking threshold for
each band, a lower bound (perceptual entropy) on the number of bits
per sample needed to compress a perceptually indistinguishable audio
signal can be found.
[Talk viewgraphs]
Ye Wang
Distributed Source Coding and Recent Advancements in Practical Code Constructions
Abstract
The landmark papers by Slepian and Wolf and by Wyner and Ziv
established the theoretical performance limits of source coding with
side information for the cases of perfect reconstruction and
reconstruction with a distortion constraint. However, not until
recently have practical constructions have been devised. This project
explores the theoretical background of the Slepian-Wolf and Wyner-Ziv
theory and examines practical code constructions proposed by
S.S.Pradhan and K.Ramchandran. In this framework, a linear channel
code is used to perform a hashing operation and achieve distributed
compression. Specifically, they propose code constructions within the
class of Low-Density Parity-Check (LPDC) codes and Trellis codes. This
project focuses on LDPC-based code constructions and practical
iterative decoding methods based on the belief propagation algorithm.
[Talk viewgraphs]
Birant Orten
Entropic Spanning Graphs and their Applications in Data Clustering
Abstract
Let X_n = {x1, x2, ..., xn} be a collection of i.i.d. random vectorsin d-dimensional Euclidean space distributed according to a
probability density function f. A minimum spanning tree (MST) is an
acyclic graph spanning all these n samples specified by edge lengths
and adjacency relations between edges. It has been shown by Beardwood,
Halton and Hammersley that the normalized graph length of MST
converges to the Renyi entropy of the source, f. These graphs for
which the normalized length converges to the entropy can be called as
entropic spanning graphs. In this study, this idea will be illustrated
by some simulations over well-known distributions. An immediate
extension of this idea is to estimate the Renyi information divergence
given a reference distribution and some random samples from an unknown
distribution. It will be shown that, with an appropriate non-linear
transformation on the random data points, it is possible to estimate
the information divergence using entropic spanning graph
methods. Finally, an application of these methods in data clustering
will be investigated.
[Talk viewgraphs]
Karen Jenkins
Sensor Management using Information Measures
Abstract
In this project we present a sensor management system based on an
algorithm that is motivated by information theory. The sensors are
tasked in such a way that the observation they make results in the
maximum amount of information gain. The sensor management scheme is
based on maximizing an information theoretic quantity, such as the
expected Renyi Information Divergence, at each observation. The Renyi
Information Divergence is a generalization of the Kullback-Leibler
Distance and provides a way to measure the dissimilarity between two
densities. The sensor modes are selected based on maximizing the
expected Renyi Information Divergence between the current joint
probability density and the joint probability density after a
measurement has been made. We evaluate the expected information gain
for each of the possible measurement decisions, and select the
measurement that maximizes the expected information gain for each
sample. We show that this optimization of information flow is
analogous to designing a communication system to maximize channel
capacity. The mode selection problem becomes a channel estimation
problem with feedback. We attempt to find an analytic solution to this
problem when the number of modes in which the sensor may operate is
finite.
[Talk viewgraphs]
Bum-Jun Lim
A Mathematical Basis for Power Reduction in Digital VLSI Systems
Abstract
This project is an overview of "A Mathematical Basis for Power Reduction
in Digital VLSI Systems," by Naresh R. Shanbhag, 1997. Techniques for reliable
power reduction are valuable since low-power digital circuits typically have
diminished reliability but lower packaging costs. N.Shanbhag develops
reliable power reduction techniques by viewing digital architectures as
communication systems with associated channel bandwidth and capacity.
He derives performance bounds based on the values of channel capacity and
the signal to noise ratio for arbitrary digital circuits.
The proposed minimum power dissipation technique is tested on a simple
CMOS digital circuit through simulation using a commercial CAD tool.
CMOS digital circuits contain networks of pull up(PMOS) and pull
down(NMOS) devices. Ideal CMOS digital circuits will have zero power
dissipation. However, practical transistors are nonideal switches and
real-world circuits will always have nonzero power dissipation.
Simulations are run with different values of the supply voltage, which
is related to the high or low representation of bits (input and
output). The input voltage is directly correlated with power dissipation.
Shanghag's analytical results are derived under simplified modeling
assumptions for tractability. To better approximate practical scenarios,
wire connects between different nodes are modeled as simple transmission
lines with a resistor shunted by a capacitor connected to the ground;
parasitic capacitance effects seen at the gate of transistors are also
accounted for in the simulation.
[Talk viewgraphs]
Manqi Zhao and Yuqing Ke
The Information-theoretic Capacity of Single-Server Queues
Abstract
The Shannon capacity of the continuous-time single-server queue is
analyzed. This channel has memory and the information is conveyed on
the inter-departure times of the packets when they are passing through
the channel. The capacity of this channel is lowest, equal to 1/e nats
per average service time, when the service time distribution is
exponential. For general service time distribution, greater capacity
can be achieved. A related and practical model of the single-server
queue channel is the memoryless telephone signaling channel and the
capacity of this channel is derived. Furthermore, if the information
of the packets is combined with the inter-departure times, the
capacity of this information-bearing queue is derived. Finally, the
discrete-time analog of this model is analyzed and compared with the
continuous-time single-server queue channel.
[Talk viewgraphs]
Nan Ma and Wei Kang
Duality of Source Coding and Channel Coding
Abstract
We explore an information-theoretic functional duality between source
coding and channel coding. We begin with a summary of the mathematical
characterization of the functional duality between conventional
(point-to-point) source and channel coding. The concept of optimality
for a source-channel communication system is also discussed. While
duality exists between the source coding problem and the channel
coding problem, the combination of them works optimally for joint
source-channel coding with the associated cost-distortion
tradeoff. The problem of single-letter codes is further discussed. We
show that in order to achieve duality or optimality, the cost function
or the distortion measure satisfies exactly the same form.
In the specific example of the BSC and the AWGN channel, we can see
that the source coding and the channel coding which achieve optimality
are exact duals. Because of the duality, we observe somewhat
surprisingly that the functions of source coding and the channel
coding may be ``canceled'' while maintaining optimality. We further
discuss a mutual information game with an associated cost function and
distortion measure. We also present extensions of the concept of
functional duality to source and channel coding problems with side
information. We provide some insights into the formulation of these
side-information coding problems and also discuss the concept of
uniqueness.
[Talk viewgraphs]
Ivana Stojanovic
Capacity of Fading Broadcast Channels: overview and recent results
Abstract
In this project we study capacity and capacity-achieving techniques
for the multiuser downlink fading channel for both single antenna
multi-antenna (MIMO) systems. When the base station (BS) and each
mobile station (MS) has a single antenna, the broadcast channel (BC)
has a special property: the received signals at different mobiles can
be ordered as a series of successive physical degradations of the
cleanest received signal. The capacity region for this ``physically
degraded'' broadcast channel is known. The combination of
superposition encoding at the transmitter and successive interference
cancellation (SIC) at the receivers is known to be a
capacity-achieving strategy. The MIMO situation is more challenging
because the broadcast channel for this case is not physically
degraded. The SIC strategy is no longer guaranteed to lead to reliable
decoding at the receivers. An achievable region based on successive
dirty paper encoding (DPC) was first proposed and later shown to equal
the capacity region in the MIMO BC case. This region was explicitly
quantified by exploiting uplink-downlink (MAC-BC) duality and looking
for MIMO-MAC boundary point transmission strategies equivalent to MIMO
BC dirty-paper capacity region. In the second part of this paper, we
look into sum-capacity of fading broadcast channel. In the single
antenna case, the sum capacity is maximized by transmitting to a user
with the best channel. But, in MIMO case, sum-capacity is achieved by
simultaneously transmitting to multiple users using dirty-paper
coding. Finally, as an example of practical interest we compare the
capacity of DPC versus that of TDMA for MIMO broadcast channel. It
was shown that DPC gain over the maximum single user capacity(TDMA) is
at most min(M,K), where M is number of transmit antennas, K is the
number of receivers.
[Talk viewgraphs]
Rohit Kumar
Relay Networks for Mobile Communication
Abstract
Relay networks is a key idea from information theory proposed by van
der Meulen in the late seventies, wherein a relay node is placed
between transmitter and receiver with the sole purpose of enhancing
the communication. After the initial work by Cover and Gamal, there
had not been any significant contribution to the area until the
emergence of sensor networks. Sensor networks has again spurred a
great interest among the researchers to come up with the best possible
transmission/cooperative schemes to achieve maximum rate with
arbitrarily small probability of error under the constraints of
limited power and computational capabilities.
In wireless systems, multiple antennas are placed as input and/or
output to enhance the rate and quality of communication. This is known
as diversity. In the first part of the talk, I will briefly go over
basic ideas of relay and antenna diversity. These are well studied
topics in the literature, and I have nothing new to talk to about
them. Hence I will not spend much time on them, though sufficient
enough to familiarize the audience with the basic idea.
The concept of multi antenna is not feasible for the mobile users due
to small size of the device. In order to exploit the advantages of the
mobile system, a new technique called user cooperative diversity is
proposed which achieves the spatial gain by cooperation among the
users. The single antenna mobile users cooperate with other mobile
user and provide each other with virtual antenna to allow them achieve
transmit diversity. In the second part of the talk, I will discuss the
model of cooperative communication proposed by Sendonaris et al., and
other results proved so far in this area.
[Talk viewgraphs]
Thomas Butler
Cramer-Rao bounds in Image Formation: an Information-Theoretic Perspective
Abstract
The well-known Cramer-Rao inequality is often used to measure the
performance of an unbiased estimator. The goal of image formation is
to reconstruct an underlying image from a collection of data. In this
project, we attempt to cast the image formation problem as a general
communication problem. Within this framework, we also explore the
link between the Cramer-Rao bound and mutual information as defined by
Shannon.
[Talk viewgraphs]