Info. Theory Society
• Info. Theory
• Network Coding
• Biology & Info.
• Quantum Info.
Thanks to all team leaders and students for their enthusiastic
participation. The research round table, held for the first time at ISIT
2006, was a smashing success, judging by the size and participation. Here
are the summaries of the discussions:
MIMO Broadcast Capacity and Space-Time
Leader: Hanan Weingarten (Technion University)
Jinsong Wu (Queen's University)
T. M. Cover, "Comments on Broadcast
This is a short and very nice tutorial on the broadcast
channel but does not contain what is known the MIMO
G. Caire and S. Shamai (Shitz), "On the
Achievable Throughput of a Multiantenna Gaussian Broadcast
This is the paper which launched the interest in MIMO
broadcast channels and introduces Costa coding in the
context of the broadcast channel.
S. Vishwanath, N. Jindal and A.
Goldsmith, "Duality, Achievable Rates, and Sum-Rate Capacity
of Gaussian MIMO Broadcast Channels"
This is a key paper on uplink-downlink duality and
establishes the sum-capacity.
H. Weingarten, Y. Steinberg and S. Shamai
(Shitz), "The Capacity Region of the Gaussian Multiple Input
Multiple Output Broadcast Channel", IEEE Transaction on
Information Theory, Sept 2006
This paper contains the converse for the capacity region of
this channel and introduces the idea of channel enhancement.
Jinsong Wu: Quite a few people are interested in MIMO Broadcast
(BC) channels. They exchanges their feelings on this topic. People also
talked about their research interests and discussed specific questions,
mainly on MIMO Broadcast, Scheduling.
Hanan Weingarten: The following only reflects part of discussion
at our table: We discussed the differences between the proofs of MIMO
broadcast channel capacity region given by myself and that given
recently by Mehdi Mohseni. In addition we discussed briefly the problem
of the capacity region of the MIMO BC with common information.
List of participants (Name, University, Research Interest):
Rui Zhang - Stanford - Dynamic resource allocations in MIMO-MAC, MIMO-BC,
Recent results, Power region
Taesang Yoo - Stanford - MIMO-BC, Scheduling, Beamforming, Quantized
feedback, Multiuser diversity
Cong Shen - UCLA - STC,Cross-layer resource allocation in MAC, feedback
in 802.11n MIMO-OFDM
Mehdi Mohseni - Stanford - Gaussian MIMO BC, Resource allocation over
fading MAC & BC
Jinsong Wu - Queen’s - STC, MIMO, MIMO-OFDM
Weingarten Hanan - Technion - IIT - MIMO BC
Tie Liu - UIUC - Entropy power inequalities
Camilla Hollanti - University of Turku, Finland
Kibeom Seong - Stanford - Cross layer resource allocation, BC & MAC
Mohammad A. Maddah-Ali - Waterloo - MIMO broadcast, Resource allocation,
Capacity with Feedback
Leader: Haim Permuter (Stanford University)
J Schalkwijk, T Kailath, "A coding scheme
for additive noise channels with feedback I: No bandwidth
L Ozarow, "The capacity of the white
Gaussian multiple access channel with feedback"
J. Massey, "Causality, Feedback and
T. Cover, S. Pombra, "Gaussian Feedback
M.V. Burnashev "Data transmission over a
discrete channel with feedback, random transmission time"
The round table discussion on feedback capacity had three main parts. In
the first part each one introduced himself to the group. In the second
one we did a review on feedback capacity and in the last part we have
talked about research problems related to feedback capacity.
During the review on the feedback capacity several results among many
that exists in the literature where mentioned. Here are only four of
Feedback does not increase capacity of Discrete Memoryless Channel (DMC):
This result was shown in 1956 by Shannon in . In the paper Shanon
distinguished between zero error capacity in which the error is
identically zero to regular capacity where the error goes to zero as the
block length of the code goes to infinity. Shannon showed that even
though the feedback can increases the zero-error capacity it does not
increase the regular capacity.
Schalkwijk and Kailath presented in 1966 a communication scheme  for
memoryless Gaussian channel with feedback that shows that even though
the capacity is not increased probability of error does significantly
decrease compared to the nonfeedback setting the. More specifically, the
probability of the decoding error decays doubly exponentially in the
duration of communication, compared to the exponential decay for the
Feedback capacity Gaussian channel with memory:
In 1989 Cover and Pombra  characterized the feedback capacity of
channel with memory. By using the asymptotic equipartition theorem for
non stationary Gaussian process they characterized the capacity of
time-varying additive Gaussian noise. In addition, with the aid of
certain matrix inequality they showed that feedback capacity can not
increase by more then half a bit then the capacity without feedback and
also can not increase more then twice the capacity without feedback. In
this ISIT Young-Han Kim, who also participated in the round-table
discussion, showed that this result can be used to find an explicit
expression for the capacity of a channel with Auto-Regressive moving
Average Gaussian noise of first order.
In 1990 Massey  coined a new term called Directed information. Massey
showed in  that directed information is always less or equal to the
mutual information and in the case of no feedback they are equal. He
also showed that directed information is an upper bound for the feedback
capacity and conjectured that it is the right term for characterizing
feedback capacity of channel with feedback. In this ISIT, Permuter,
Weissman and Goldsmith proved that it is the right term for
characterizing the capacity of channels with any time invariant
We would like to mention that there are many more important results
related to feedback such as those that are related to multi-user
settings like Broadcast, MAC relay and MIMO. Many of them were discussed
during the third part of the discussion where many interesting research
problem were suggested. In particular Brooke Shrader suggested the
compound channel with feedback. Later on, we found out that the case,
where each channel in the compound channel is memoryless, was considered
by Wolfowitz in his book but the case that each channel in the compound
channel has memory was not yet considered.
some references related to feedback capacity that were mentioned in the
 C. E. Shannon, "The Zero Error Capacity of a Noisy Channel." IEEE
Trans. on Information Theory, Vol 2, pp. S8-S19, September 1956.
 J. P. M. Schalkwijk and T. Kailath, “A coding scheme for additive
noise channels with feedback–I: No bandwidth constraint,” IEEE Trans.
Inform. Theory, vol. IT-12,pp. 172–182, April 1966.
 T. Cover and S. Pombra, "Gaussian Feedback Capacity." IEEE Trans. on
Information Theory, Vol. IT-35, No. 1, January 1989, pp. 37-43.
 J. L. Massey, Causality, feedback and directed information,
Proceedings of the International Symposium on Information Theory and its
Applications, Honolulu, HI, Nov. 27-30, 1990.
Cooperation and Relaying
Leader: Chris Ng (Stanford University)
T. Cover and A. El Gamal, "Capacity
Theorems for the Relay Channel"
We took turns to introduce ourselves and what we're working on. Most
people are already working in the field of cooperative communications. A
few were just starting in the topic.
We then discussed different cooperative protocols such as
decode-and-forward and compress-and-forward. Different performance
metrics were also discussed: ergodic capacity, outage capacity,
diversity order etc. And we talked about the impact of different channel
state information and power assumptions. Then the table broke out to
smaller discussion groups with two to three people discussing the topics
of their interests.
Leader: Niranjan Ratnakar (UIUC)
S.P Borade, "Network information flow:
limits and achievability"
R. Dougherty, C. Freiling, and K. Zeger "Unachievability
of Network Coding Capacity"
The focus of this round table was on the interaction between information
theory and network coding. The minutes of the meeting are as follows:
* The main idea of network coding was introduced. We are interested in
communicating data across a network with multiple nodes (which represent
sources, relays, and destinations). In the paradigm of network coding,
data is encoded by all nodes in the network, as opposed to the
traditional approach of encoding only at the source.
* Multicast (one source generates data that is demanded by multiple
destinations) has been extensively studied by the network coding
* Multiple unicast (a unicast involves one source and one destination
and by multiple unicast, we assume that there are parallel independent
unicast sessions) is more difficult to analyze than multicast. Some of
the results we discussed were the insufficiency of linear network coding
and the recent result by Koetter (unpublished) where he considers a
network of discrete memoryless channels (DMCs) and shows that an optimal
mode of operating these networks is to perform channel coding on each
DMC and then to perform network coding on this network of error free
* The above point suggests that the problem of computing capacity
regions of networks of DMCs is the same as computing capacity regions of
networks of error free links (which is a combinatoric problem). Was this
a reason why comoputing the capacity regions of DMCs was an open problem
for a long time?
* One of the questions raised during the discussion was whether capacity
is the right measure to evaluate performance of networks? Note that
capacity has been a successful measure for the point to
Secrecy System Capacity
Leader: Yingbin Liang (Princeton University)
A. D. Wyner, "The Wire-Tap Channel"
I. Csiszar and J. Korner "Broadcast
Channels with Confidential Messages"
We first went over the Wyner's framework of information-theoretic security
for the wire-tap channel, where a sender wishes to transmit confidential
information to a legitimate receiver and to keep a wire-tapper as ignorant
of this information as possible. A generalization of Wyner's wire-tap
channel is the broadcast channel with confidential messages, and was studied
by Csiszar and Korner. This model was also discussed.
The secrecy level of confidential information at the wire-tapper is measured
by the equivocation rate, i.e., the entropy rate of confidential messages
conditioned on channel outputs at the wire-tapper. This concept was
introduced. The secrecy capacity was also discussed, which is the maximum
rate that can be achieved with perfect secrecy, i.e., the wire-tapper is
fully ignorant of the confidential message.
The important results on the secrecy capacity were summarized. These results
include the secrecy capacity of the wire-tap channel and its Gaussian
example, the broadcast channel with confidential messages, and the relay
channel with confidential messages. The intuition behind the results were
The concept of common randomness was introduced. The secret key capacity
that arises in this setting was discussed.
The security issues in fading wireless channels were finally discussed. One
interesting problem in this setting is whether fading can help in achieving
communication security. We also discussed what are important factors that
affect secure communication in wireless channels.