 
Last updated on September 25, 2017. This conference program is tentative and subject to change
Technical Program for Thursday September 28, 2006

ThIA 
Library 
Cooperative Wireless Communication and Sensing 
Invited Session 
Chair: Franceschetti, Massimo  Univ. of California at San Diego 
Organizer: Franceschetti, Massimo  Univ. of California at San Diego 
Organizer: Kumar, PR  Univ. of Illinois Urbana 

08:3009:00, Paper ThIA.110  
Shot Noise Models for the Dual Problems of Cooperative Coverage and Outage in Random Networks (I) 
Venkataraman, Jagadish  Univ. of Notre Dame 
Haenggi, Martin  Univ. of Notre Dame 
Collins, Oliver  Univ. of Notre Dame 
Keywords: Sensor Networks in Communications
Abstract: The performance analysis of ad hoc networks requires the characterization of the network's selfinterference. However, thus far, the exact distribution of the interference has been analytically tractable only for a path loss exponent of 4. Further, conventional power law decay models for signal propagation have a singularity at the origin that causes all the moments of the network selfinterference to diverge, resulting in no useful insight into the statistics of the interference. In this paper, we employ a 2D shot noise process with a stochastic power law impulse response function together with a bounded path loss to model the interference in large wireless networks, where the nodes are distributed according to a Poisson point process. We further show that this interference problem and the problem of coverage in cooperative sensor networks are duals of each other  they can be solved using the same shot noisebased approach.


09:0009:30, Paper ThIA.120  
Congestion Control and Routing Schemes for Wireless Sensor Networks (I) 
Zawodniok, Maciej  Univ. of MissouriRolla 
Sarangapani, Jagannathan  Univ. of MissouriRolla 
Keywords: Sensor Networks in Communications, Wireless Communications, Pricing and Congestion Control
Abstract: Available congestion control schemes, for example transport control protocol (TCP), when applied to wireless networks, result in a large number of packet drops, unfair scenarios and low throughputs with a significant amount of wasted energy due to retransmissions. To fully utilize the hop by hop feedback information, a novel, decentralized, predictive congestion control method consisting of a) an adaptive flow and backoff interval selection scheme, b) adaptive scheduling, and c) energy aware routing, is proposed for wireless sensor networks in concert with distributed power control (DPC). Moreover, the embedded channel estimator algorithm in DPC predicts the channel quality in the subsequent time interval. Additionally, due to the recursive application of the proposed congestion control at each node and through piggyback acknowledgments, the onset of congestion is propagated backward towards the source nodes so that they too reduce their transmission rates. The optional adaptive scheduling scheme at each node updates the packet weights to guarantee the weighted fairness during congestion. Finally, congestionaware routing scheme is also added that addresses hardware constraints of the sensor nodes and overcomes local congestion by identifying a path, which is both energy efficient and minimal delay, around the congested nodes to the destination. Closedloop stability of the proposed congestion control is demonstrated by using the Lyapunovbased approach.


09:3010:00, Paper ThIA.130  
Achieving 2/3 Throughput Approximation with Sequential Maximal Scheduling under Primary Interference Constraints (I) 
Sarkar, Saswati  Univ. of Pennsylvania 
Kar, Koushik  Rensselaer Pol. Inst 


10:3011:00, Paper ThIA.150  
On Universal Distributed Estimation of Noisy Fields with OneBit Sensors (I) 
Wang, Ye  Boston Univ 
Ma, Nan  Boston Univ 
Zhao, Manqi  Boston Univ 
Ishwar, Prakash  Boston Univ 
Saligrama, Venkatesh  Boston Univ 
Keywords: Sensor Networks, Detection and Estimation, Source Coding and Compression
Abstract: This paper formulates and studies a general distributed field reconstruction problem using a dense network of noisy one–bit randomized scalar quantizers in the presence of additive observation noise of unknown distribution. A constructive quantization, coding, and field reconstruction scheme is developed and an upper–bound to the associated mean squared error (MSE) at any point and any snapshot is derived in terms of the local spatio–temporal smoothness properties of the underlying field. It is shown that when the noise, sensor placement pattern, and the sensor schedule satisfy certain minimal technical requirements, it is possible to drive the MSE to zero with increasing sensor density at points of field continuity while ensuring that the per–sensor bitrate and sensing–related network overhead rate simultaneously go to zero. The proposed scheme achieves the order–optimal MSE versus sensor density scaling behavior for the class of spatially constant spatio–temporal fields.


11:0011:30, Paper ThIA.160  
Collaborative Content Distribution for Vehicular Ad Hoc Networks (I) 
Johnson, Mark  UC Berkeley 
De Nardis, Luca  UC Berkeley 
Ramchandran, Kannan  UC Berkeley 
Keywords: Network Coding in Communication, Sensor Networks in Communications, Wireless Communications
Abstract: The proliferation of lowcost wireless connectivity, combined with the growth of distributed peertopeer cooperative systems, is changing the way in which nextgeneration vehicular networks will evolve. In this paper, we address the problem of lowlatency content distribution to a dense vehicular highway network from roadside infostations. Due to the highly dynamic nature of the underlying vehicular network topology, we depart from architectures requiring centralized coordination, reliable MAC scheduling, or global network state knowledge, and instead adopt a distributed and minimally coordinated paradigm. We establish the viability of our approach with both analysis and extensive simulations. The key ingredient in our approach is the use of multihop randomized network coding to efficiently distribute the content in the vehicular network. Specifically, we show that in the limit of a highly dense network, our decentralized approach can attain a multicast throughput that is up to a factor of 1/e of the throughput which could be achieved by perfectly scheduling all packets in the network. Further, the gains in throughput achieved by using randomized network coding instead of classical storeandforward multihop routing strategies can be significant. This in turn translates into a significant decrease in the number of roadside infostations required to meet desired throughput and latency constraints for specific streaming applications.


11:3012:00, Paper ThIA.170  
Maxwell Meets Shannon: SpaceTime Duality in Multiple Antenna Channels (I) 
Franceschetti, Massimo  Univ. of California at San Diego 
Chakraborty, Kaushik  Univ. of California, San Diego 


ThIB 
Porch 
Network Coding 
Invited Session 
Chair: Lun, Desmond S.  Massachusetts Inst. of Tech 
Organizer: Meyn, Sean  Univ. of Florida 
Organizer: Médard, Muriel  MIT 
Organizer: Kötter, Ralf  Tech. Univ. München 

08:3009:00, Paper ThIB.110  
Network Coding Techniques for Topology Inference (I) 
Fragouli, Christina  EPFL 
Markopoulou, Athina  Univ. of California, Irvine 
Diggavi, Suhas  EPFL 
Keywords:
Abstract: The network coding paradigm is based on the idea that independent information flows can be linearly combined throughout the network to give benefits in terms of throughput, complexity etc. In this paper, we explore the application of the network coding paradigm to topology inference. Our goal is to infer the topology of a network by sending probes between multiple sources and receivers at the edge of the network, while intermediate nodes locally combine incoming probes before forwarding them. In previous tomography work, the correlation between the observed packet loss patterns has been used to infer the underlying topology. In contrast, our main idea behind using network coding is to introduce correlations among probe packets in a topology dependent manner and also develop algorithms that take advantage of these correlations to infer the network topology from endhost observations. Preliminary simulations illustrate the performance benefits of this approach. In particular, in the absence of packet loss, we can deterministically infer the topology, with very few probes; in the presence of packet loss, we can rapidly infer topology, even at very small loss rates (which was not the case in previous tomography techniques).


09:0009:30, Paper ThIB.120  
On Constructive Network Coding for Multiple Unicasts (I) 
Ho, Tracey  California Inst. of Tech 
Chang, YuHan  Univ. of Southern California 
Han, Keesook  AFOSR/IFGB 
Keywords:
Abstract: We consider the problem of network coding across multiple unicasts. We give, for wired and wireless networks, offline and online back pressure algorithms for finding optimal network codes within the class of network codes restricted to XOR coding between pairs of flows.


09:3010:00, Paper ThIB.130  
Network Coding Capacity with a Limited Number of Coding Nodes (I) 
Cannons, Jillian  Univ. of California, San Diego 
Zeger, Ken  UC San Diego 
Keywords:
Abstract: We study network coding capacity under a constraint on the total number of network nodes that can perform coding. That is, only a certain number of network nodes can produce coded outputs, whereas the remaining nodes are limited to performing routing. We prove that every nonnegative, monotonically nondecreasing, eventually constant, rationalvalued function on the nonnegative integers is equal to the capacity as a function of the number of allowable coding nodes of some directed acyclic network.


10:3011:00, Paper ThIB.150  
Conservative Network Coding (I) 
Harvey, Nicholas  MIT 
Jain, Kamal  Microsoft Res 
Lau, Lap Chi  Univ. of Toronto 
Nair, Chandra  Microsoft Res 
Wu, Yunnan  Microsoft Corp 
Keywords:
Abstract: Motivated by practical networking scenarios, we introduce a notion of restricted communication called "conservative networking". Consider a network of lossless links and a number of independent sources. Each node needs to recover a certain subset of the sources. However, each node is "conservative" in that all information it receives can only be a function of the sources it will ultimately recover. For acyclic networks, we show that conservative networking admits a clean characterization: (i) the rates achievable by integer routing, factional routing, and network coding are equal, and (ii) this rate is determined by a simple cut bound. However, this clean characterization does not extend to cyclic networks. We present cyclic examples showing that (i) fractional routing can be strictly better than integer routing, and (ii) network coding can be strictly better than fractional routing. This work underscores the difficulties generally encountered in cyclic networks.


11:0011:30, Paper ThIB.160  
Fiber Memory (I) 
Li, ShuoYen  The Chinese Univ. of Hong Kong 
Tan, Xuesong  The Chinese Univ. of Hong Kong 
Keywords:
Abstract: When a fiber is used as a delay line, data retrieval abides with the FIFO order and the storage time is fixed by the length of the fiber. To enhance the access flexibility, the fiber needs logical elasticity in harnessing the fluid data. Fiber memory combines fibers and switches in serving purposes such as random access, timeslot interchanging, queueing, multiplexing, demultiplexing, and flexible delay. The present paper proposes systematic algorithms for the recursive construction of fiber memory by emulating the most fundamental patterns of multistage switching networks. The mathematical underpinning is mainly the algebraic theory on 2stage switching networks, over which the switching control is distributed and suitable for highspeed optical applications.


ThIC 
Butternut 
Multiuser Secrecy 
Regular Session 
Chair: Moulin, Pierre  Univ. of Illinois 

08:3009:00, Paper ThIC.110  
Achievable Rates for the General Gaussian Multiple Access WireTap Channel with Collective Secrecy 
Tekin, Ender  The Pennsylvania State Univ 
Yener, Aylin  The Pennsylvania State Univ 
Keywords: Information Theory, Information Hiding and Watermarking, Wireless Communications
Abstract: We consider the General Gaussian Multiple Access WireTap Channel (GGMACWT). In this scenario, multiple users communicate with an intended receiver in the presence of an intelligent and informed eavesdropper who is as capable as the intended receiver, but has different channel parameters. We aim to provide perfect secrecy for the transmitters in this multiaccess environment. Using Gaussian codebooks, an achievable secrecy region is determined and the power allocation that maximizes the achievable sumrate is found. Numerical results showing the new rate region are presented. It is shown that the multipleaccess nature of the channel may be utilized to allow users with zero singleuser secrecy capacity to be able to transmit in perfect secrecy. In addition, a new collaborative scheme is shown that may increase the achievable sumrate. In this scheme, a user who would not transmit to maximize the sum rate can help another user who (i) has positive secrecy capacity to increase its rate, or (ii) has zero secrecy capacity to achieve a positive secrecy capacity.


09:0009:30, Paper ThIC.120  
Secure Communication Over Fading Channels 
Liang, Yingbin  Princeton Univ 
Poor, H. Vincent  Princeton Univ 
Keywords: Wireless Communications, Information Theory
Abstract: The fading wiretap channel is investigated, where the sourcetodestination channel and the sourcetowiretapper channel are corrupted by multiplicative fading gain coefficients in addition to additive Gaussian noise terms. The channel state information is assumed to be known at both the transmitter and the receiver. The parallel wiretap channel with independent subchannels is first studied, which serves as an informationtheoretic model for the fading wiretap channel. Each subchannel is assumed to be a general broadcast channel and is not necessarily degraded. The secrecy capacity of the parallel wiretap channel is established, which is the maximum rate at which the destination node can decode the source information with small probability of error and the wiretapper does not obtain any information. This result is then specialized to give the secrecy capacity of the fading wiretap channel, which is achieved with the source node dynamically changing the power allocation according to the channel state realization. An optimal source power allocation is obtained to achieve the secrecy capacity. This power allocation is different from the waterfilling allocation that achieves the capacity of fading channels without the secrecy constraint.


09:3010:00, Paper ThIC.130  
Relay Secrecy in Wireless Networks with Eavesdropper 
Venkitasubramaniam, Parvathinathan  Cornell Univ 
He, Ting  Cornell Univ 
Tong, Lang  Cornell Univ 
Keywords: Reliable and Trustworthy Networks, Intrusion/Anomaly Detection and Diagnosis, Information Hiding and Watermarking
Abstract: Anonymous monitoring of transmissions in a wireless network by eavesdroppers can provide critical information about the data flows in the network. It is, therefore, necessary to design network protocols that maintain secrecy of routes from eavesdroppers. In this work, we present a mathematical formulation of route secrecy when eavesdroppers observe transmission epochs of nodes. We propose scheduling techniques to provide complete secrecy of routes, and characterize achievable rate regions for a multiplex relay under transmitter directed spread spectrum signaling. Further, we extend the results to the case when an additional constraint on packet loss is imposed.


10:3011:00, Paper ThIC.150  
Secure Broadcasting with Multiuser Diversity 
Khisti, Ashish  MIT 
Wornell, Gregory  MIT 
Tchamkerten, Aslan  MIT 
Keywords: Information Theory, Wireless Communications
Abstract: We consider the problem of broadcasting information to one or more receivers in the presence of potential eavesdropper(s). We impose an asymptotic secrecy constraint as in the wiretap channel and investigate the ergodic capacity when the transmitter has instantaneous knowledge of the channel gains of the intended receivers but only statistical knowledge of the channel gains of potential eavesdroppers. Upper and lower bounds on the sum capacity with independent messages are derived, which coincide as the number of intended receiver grows. We note that while the secrecy constraint preserves the gains from multiuser diversity, the power gain is lost. Our achievable scheme can be easily combined with the scheduling algorithms designed for conventional systems (without a secrecy constraint) to incorporate the fairness issues in multiuser diversity. Finally we provide a simple scheme for multicasting a common message to all the receivers with a secrecy constraint. We motivate our setup and assumptions by discussing applications to sensor networks and payTV systems.


11:0011:30, Paper ThIC.160  
Secrecy Capacity of Independent Parallel Channels 
Li, Zang  Rutgers Univ 
Yates, Roy  Rutgers Univ 
Trappe, Wade  Rutgers Univ 
Keywords: Information Theory, Wireless Communications
Abstract: Security has been one of the most prominent problems surrounding wireless and mobile communications, in large part due to the broadcast nature of the wireless medium where eavesdropping can be easily accomplished. On the other hand, the wireless propagation environment also causes users to have varying channel qualities. From an information theoretic view, secret communication in presence of eavesdropper is still possible by exploiting these variations. In this paper, we extend the prior results on secrecy capacity to a system consisting of multiple independent parallel channels. We show that the secrecy capacity of the system is simply the summation of the secrecy capacities of the individual channels. We further derive the optimal power allocation strategy for a system with parallel AWGN channels subject to a total power constraint. The results can be extended to random fading channels with additive Gaussian noise. Secrecy capacity under various channel conditions and the benefit of the optimal power allocation strategy are evaluated numerically for an OFDM system as an example.


11:3011:45, Paper ThIC.171  
An Opportunistic PhysicalLayer Approach to Secure Wireless Communications 
Bloch, Matthieu  GtCnrs Umi 2958 
Barros, Joăo  FCUP  Univ. of Porto 
Rodrigues, Miguel  Univ. of Cambridge 
McLaughlin, Steven W.  Georgia Inst. of Tech 
Keywords: Information Theory, Wireless Communications, Iterative Coding Techniques
Abstract: Recent theoretical and practical work has shown that physical layer security techniques have the potential to significantly strengthen the security of wireless networks. We propose a practical security scheme by which two terminals (say Alice and Bob) are able to exploit the randomness of wireless fading channels to exchange data in an informationtheoretically secure way. To ensure that a potential eavesdropper (say Eve) is unable to decode any useful information, Alice sends useful symbols to Bob only when the instantaneous secrecy capacity is strictly positive. In the remaining time, a specially designed class of LDPC codes is used for reconciliation, thus allowing the extraction of a secret key, which can be distilled using privacy amplification. We believe this opportunistic approach can be used effectively as a physical layer complement to existing cryptographic protocols


11:4512:00, Paper ThIC.172  
Spectrum Management for InterferenceLimited Multiuser Communication Systems 
Hayashi, Shunsuke  Kyoto Univ 
Luo, ZhiQuan  Univ. of Minnesota 
Keywords: Wireless Communications, Information Theory
Abstract: Consider a multiuser communication system in a frequency selective environment whereby users share a common spectrum and can interfere with each other. Assuming Gaussian signaling and no interference cancellation, we study optimal spectrum sharing strategies for the maximization of sumrate under separate power constraints for individual users. Since the sumrate function is nonconcave in terms of the users' power allocations, there can be multiple local maxima for the sumrate maximization problem in general. In this paper, we show that, if the normalized crosstalk coefficients are larger than a given threshold (roughly equal to 1/2), then the optimal spectrum sharing strategy is frequency division multiple access (FDMA). In case of arbitrary positive crosstalk coefficients, if each user's power budget exceeds a given threshold, then FDMA is again sumrate optimal, at least in a local sense. In addition, we show that the problem of finding the optimal FDMA spectrum allocation is NPhard, implying that the general problem of maximizing sumrate is also NPhard, even in the case of two users. We also propose several simple distributed spectrum allocation algorithms that can approximately maximize sumrates. Numerical results indicate that these algorithms are efficient and can achieve substantially larger sumrates than the existing Iterative Waterfilling solutions, either in an interferencerich environment or when the users' power budgets are sufficiently high.


ThID 
Pine 
Source Coding 
Invited Session 
Chair: Shamir, Gil  Univ. of Utah 
Organizer: Shamir, Gil  Univ. of Utah 
Organizer: Singer, Andrew  Univ. of Illinois at Urbana Champaign 

08:3009:00, Paper ThID.110  
Sampling Distortion Measures (I) 
Niesen, Urs  MIT 
Shah, Devavrat  MIT 
Wornell, Gregory  MIT 
Keywords: Source Coding and Compression
Abstract: This paper is motivated by the following problem. Consider an image we want to compress. The appropriate distortion measure with respect to which we compress the image is specified by the human visual system. This distortion measure can only be experimentally determined and our knowledge about it will hence be only partial. This leads us to consider the general problem of lossy source coding with partial knowledge about the distortion measure. More precisely, the distortion measure is only known at a number of sampling points. We describe several measures for the loss we incur through the lack of full knowledge of the true distortion measure, each with a different operational meaning. We give an asymptotically tight characterization of this loss in terms of three key parameters: The number of sampling points, the dimensionality of the source, and the smoothness assumptions on the distortion measure.


09:0009:30, Paper ThID.120  
Improving the Redundancy of SlepianWolf Coding by Feedback (I) 
He, Dake  IBM T. J. Watson Res. Center 
LastrasMontano, Luis  IBM T. J. Watson Res. Center 
Yang, Enhui  Univ. of Waterloo 
Keywords: Source Coding and Compression, Information Theory, Image and Video Compression
Abstract: For any memoryless sourceside information pair (X, Y) with finite alphabet, it is well known that the smallest compression rate in bits per letter achievable in SlepianWolf coding, i.e., coding X with Y being available only to the decoder, is the conditional entropy H(XY). Though this rate is the same as the best rate achievable in traditional lossless source coding of X with Y being available to both the encoder and the decoder, it has been found recently that the redundancy {cal R}_n(epsilon_n) of SlepianWolf coding, which is defined as the minimum of the difference between the compression rate of any SlepianWolf code resulting from coding X_1^n with decoding error epsilon_n, and H(XY), is significantly worse than that of traditional source coding. In this paper, we investigate whether feedback from the decoder to the encoder can improve the compression efficiency of SlepianWolf coding. It turns out that the answer is affirmative. More specifically, it is shown that feedback reduces the redundancy of SlepianWolf coding significantly.


09:3010:00, Paper ThID.130  
Using a Universal Coding Technique for Sources with Large Alphabets to Estimate Differential Entropy (I) 
Willems, Frans M.J.  Eindhoven Univ. of Tech 
Keywords: Universal Algorithms and Machine Learning
Abstract: The objective of this paper is to find an estimator for differential entropy. We restrict ourselves to densities that have a bounded support set, that are bounded, and continuous almost everywhere. The techniques on which the proposed estimator is based are very similar to those that play a role in the contexttree weighting method [1995], the difference is that instead of a context tree we use a decomposition tree here. Another difference is that the weighting method includes uncoded coding probabilities. An interesting property of our decompositiontree weighting estimator is its small computational complexity. We show that our estimator converges to differential entropy with probability one.


10:3011:00, Paper ThID.150  
Minimax Risk for Gaussian Sequence Models (I) 
Liang, Feng  Duke Univ. 

11:0011:30, Paper ThID.160  
Results on Compression and Probability Estimation (I) 
Orlitsky, Alon  UCSD 

ThIE 
Lower Level 
Network Algorithms and Analysis 
Invited Session 
Chair: Hajek, Bruce  Univ. of Illinois at UrbanaChampaign 
Organizer: Hajek, Bruce  Univ. of Illinois at UrbanaChampaign 
Organizer: Srikant, R  Univ. of Illinois at UrbanaChampaign 

08:3009:00, Paper ThIE.110  
Cost Shares and Approximation Algorithms for Network Design Problems (I) 
Fleischer, Lisa  Dartmouth 
Keywords:
Abstract:


09:0009:30, Paper ThIE.120  
Bloom Filters Via DLeft Hashing and Dynamic Bit Reassignment : Extended Abstract (I) 
Bonomi, Flavio  Cisco Systems 
Mitzenmacher, Michael  Harvard Univ 
Panigrahy, Rina  Stanford Univ 
Singh, Sushil  Cisco Systems 
Varghese, George  Univ. of California San Diego 
Keywords:
Abstract: In recent work, the authors introduced a data structure with the same functionality as a counting Bloom filter (CBF) based on fingerprints and the dleft hashing technique. This paper describes dynamic bit reassignment, an approach that allows the size of the fingerprint to flexibly change with the load in each hash bucket, thereby reducing the probability of a false positive. This technique allows us to not only improve our dleft counting Bloom filter, but also to construct a data structure with the same functionality as a Bloom filter, including the ability to handle insertions online, that yields fewer false positives for sufficiently large filters. Our results show that our dleft Bloom filter data structure begins achieving smaller false positive rates than the standard construction at 16 bits per element. We explain the technique, describe why it is amenable to hardware implementation, and provide experimental results.


09:3010:00, Paper ThIE.130  
MultiObjective Network Protocols (I) 
Goel, Ashish  Stanford Univ. 

10:3011:00, Paper ThIE.150  
Control Plane Resilience: The Method of Strong Detection (I) 
Rajendran, Raj Kumar  Columbia Univ 
Misra, Vishal  Columbia Univ 
Rubenstein, Dan  Columbia Univ 
Keywords:
Abstract:


11:0011:30, Paper ThIE.160  
Congestion Control in Networks with No Congestion Drops (I) 
Lu, Yi  Stanford Univ 
Pan, Rong  Cisco Systems 
Prabhakar, Balaji  Stanford Univ 
Bergamasco, Davide  Cisco Systems 
Alaria, Valentina  Cisco Systems 
Baldini, Andrea  Cisco Systems 
Keywords:
Abstract: Congestion is intrinsic to the operation of networks and is usually handled by a combination of algorithms at the link and network/transport layers. Link level algorithms alleviate ``transient congestion" caused by the temporary oversubscription of a link due to a burst of packets arriving at a switch or router buffer. Network or transport level algorithms alleviate ``sustained congestion" which occurs when the longterm arrival rate at a link exceeds its capacity. Algorithms at the two levels interact to provide a scalable, stable and fair bandwidth allocation to the flows passing through the network. Link level algorithms are typically very simple: drop or mark packets with increasing probability as buffer congestion increases; moreover, if a packet arrives at a full buffer, drop it. These dropped or marked packets are used by the transport algorithms to adjust the transmission rate of sources. In this paper we are concerned with networks in which packets cannot be dropped when there is congestion. In such networks a backpressure mechanism ``pauses'' the link or links feeding a congested buffer, thus preventing further packets from arriving at the buffer. The links are later unpaused when the buffer becomes uncongested. This paper is a theoretical study of the stability and fairness properties of network level congestion control when pause mechanisms operate at the link level to prevent packet drops. Our focus is on the Backward Congestion Notification (BCN) algorithm w


11:3012:00, Paper ThIE.170  
Stochastic Stability under Fair Bandwidth Allocation: General File Size Distribution (I) 
Chiang, Mung  Princeton Univ 
Shah, Devavrat  MIT 
Tang, Ao (Kevin)  California Inst. of Tech 
Keywords:
Abstract: We prove the stochastic stability of resource allocation under Network Utility Maximization (NUM) under general arrival process and file size distribution with bounded support, for alphafair utilities with alpha sufficiently small and possibly different for different sources' utility functions. In addition, our results imply that the system operating under alphafair utility is 1/(1+alpha)approximate stable for any alpha in (0,infty) for any file size distribution with bounded support. Our results are in contrast to the recent stability result of Bramson (2005) for maxmin fair (i.e., alpha = infty) under general arrival process and file size distribution, and that of Massoulie (2006) for proportional fair (i.e., alpha = 1) under Poisson arrival process and phasetype distributions. To obtain our results, we develop an appropriate Lyapunov function for the fluid model established by Gromoll and Williams (2006).


ThIF 
Brick 
Theory of Graphical Models 
Regular Session 
Chair: Yeh, Edmund  Yale Univ 

08:3009:00, Paper ThIF.110  
Criteria for Rapid Mixing of Gibbs Samplers and Uniqueness of Gibbs Measures 
Winkler, Stephan Norbert  Yale Univ 
Tatikonda, Sekhar  Yale Univ 
Keywords: Iterative Coding Techniques
Abstract: We survey conditions for rapid mixing of certain Markov chains, called Gibbs samplers, and uniqueness of certain probability measures with prescribed finite dimensional conditional distributions, called Gibbs measures. By Tatikonda and Jordan's sufficiency result, these criteria translate into conditions for convergence of the SumProduct algorithm. The basic idea is to show that the transition kernels (in the Gibbs sampler case) or the prescribed conditional distributions (in the Gibbs measure case) act as contractions on spaces of functions or measures, provided they are weakly influenced by neighboring sites. The contributions of this paper are as follows: We compare various notions of influence, unifying notation and terminology currently scattered across a large body of literature. We survey, generalize and extend existing proof techniques which fall in three broad categories: analytic arguments, coupling arguments, and arguments using path coupling. In particular, we extend all arguments from single sites to finite blocks and from total variation to Wasserstein distance; we introduce new matrix methods; we answer an open question by Weitz; and we provide evidence to support the superiority of path coupling, addressing a question raised by Sokal regarding the dual relationship of analytic and coupling techniques.


09:0009:30, Paper ThIF.120  
A Rigorous Proof of the Cavity Method for Counting Matchings 
Bayati, Mohsen  Stanford Univ 
Nair, Chandra  Microsoft Res 
Keywords: Iterative Coding Techniques, Universal Algorithms and Machine Learning, Coding Techniques and Applications
Abstract: In this paper we rigorously prove the validity of the cavity equations for the problem of counting the number of matchings in graphs. Cavity method is an important heuristic developed by statistical physicists that has lead to the development of faster distributed algorithms for problems in coding theory and other optimization problems. The validity of the approach has been supported mostly by numerical simulations. In this paper we prove the validity of cavity method for the problem of counting matchings using rigorous techniques. We hope that these rigorous approaches will finally help us unravel the validity of the cavity method in general.


09:3010:00, Paper ThIF.130  
Belief Propagation Is Asymptotically Equivalent to MAP Estimation for Sparse Linear Systems 
Wang, ChihChun  Purdue Univ 
Guo, Dongning  Northwestern Univ 
Keywords: Information Theory, Iterative Coding Techniques, Multiuser Detection and Estimation
Abstract: This paper addresses the relationship between belief propagation (BP) and the optimal maximum a posteriori (MAP) detection for large linear systems with Gaussian noise. Assuming an input vector of independent symbols with arbitrary distribution, it is proved that BP is asymptotically equivalent to MAP as long as the linear system is ``sparse'' and ``semiregular'' in some sense where the probability of seeing short cycles in the factor graph which describes the system vanishes, and that the aspect ratio of the linear system is below a certain threshold. Moreover, the problem of estimating each input symbol through the sparse linear system is shown to be asymptotically equivalent to that of estimating the same symbol through a scalar Gaussian channel with some degradation in the signaltonoise ratio (SNR), known as the efficiency of the system. The efficiency has been previously shown to satisfy a fixedpoint equation by Guo and Verdu using nonrigorous statistical physics techniques in the context of codedivision multiple access (CDMA) with no requirement of sparsity. This paper establishes a rigorous proof of the result in the special case of sparse systems, and henceforth fully characterizes the performance of such systems.


10:3011:00, Paper ThIF.150  
Clustering and Mixing in Constraint Satisfaction Problems 
Tatikonda, Sekhar  Yale Univ 
Keywords: Iterative Coding Techniques, Statistical Signal Processing, Coding Theory
Abstract: The belief propagation algorithm and its variants have recently been shown to work quite well on hard constraint satisfaction problems. Survey propagation is one such algorithm that has been developed for solving the kSAT problem. This algorithm is based on two hypotheses deriving from the replica symmetry breaking theory developed for the statistical mechanics of spin glasses. The first is that the solutions of constraint satisfaction problems near threshold organize into disjoint clusters. The second is that within each cluster there is spatial mixing. In this paper we give, to the best of the author's knowledge, the first rigorous proof that both these hypotheses hold for a large class of constraint satisfaction problems including the kSAT problem. We show that the existence of multiple clusters corresponds to the nonuniqueness of the corresponding Gibbs measure.


11:0011:30, Paper ThIF.160  
Detection of Markov Random Fields on TwoDimensional Intersymbol Interference Channels 
Zhu, Ying  Washington State Univ 
Cheng, Taikun  Washington State Univ 
Sivakumar, Krishnamoorthy  Washington State Univ 
Belzer, Benjamin  Washington State Univ 
Keywords: Detection and Estimation, Iterative Coding Techniques, Data Storage
Abstract: We present a novel iterative algorithm for detection of binary Markov random fields (MRFs) corrupted by twodimensional (2D) intersymbol interference (ISI) and additive white Gaussian noise (AWGN). We assume a firstorder binary MRF as a simple model for correlated images. We assume a 2D digital storage channel, where the MRF is interleaved before being written and then read by a 2D transducer; such channels occur in recently proposed optical disk storage systems. The detection algorithm is a concatenation of two softinput/softoutput (SISO) detectors: an iterative rowcolumn softdecision feedback (IRCSDF) ISI detector, and a MRF detector. The MRF detector is a SISO version of the stochastic relaxation algorithm by Geman and Geman in IEEE Trans. Pattern Anal. and Mach. Intell., Nov. 1984. On the 2 x 2 averagingmask ISI channel, at a bit error rate (BER) of 10 ^{5}, the concatenated algorithm achieves SNR savings of between 0.5 and 2.0 dB over the IRCSDF detector alone; the savings increase as the MRFs become more correlated, or as the SNR decreases. The algorithm is also fairly robust to mismatches between the assumed and actual MRF parameters.


11:3011:45, Paper ThIF.171  
Improving Convergence of Belief Propagation Decoding 
Stepanov, Mikhail  Univ. of Arizona 
Chertkov, Michael  Los Alamos National Lab 
Keywords: Iterative Coding Techniques, Coding Theory, Information Theory
Abstract: The decoding of LowDensity ParityCheck codes by the Belief Propagation (BP) algorithm is revisited. To check the iterative algorithm for its convergence to a codeword (termination), we run Monte Carlo simulations and find the probability distribution function of the termination time, n_it. Tested on the [155, 64, 20] code, this termination curve shows a maximum and an extended algebraic tail at the highest values of n_it. Aiming to reduce the tail of the termination curve we consider a family of iterative algorithms modifying the standard BP by means of a simple relaxation. The relaxation parameter controls the convergence of the modified BP algorithm to a minimum of the Bethe free energy. The improvement is experimentally demonstrated for AdditiveWhiteGaussianNoise channel in some range of the signaltonoise ratios. We also discuss the tradeoff between the relaxation parameter of the improved iterative scheme and the number of iterations.


11:4512:00, Paper ThIF.172  
Accelerated Gossip Algorithms for Distributed Computation 
Cao, Ming  Yale Univ 
Spielman, Daniel  Yale Univ 
Yeh, Edmund  Yale Univ 
Keywords: Sensor Networks in Communications, Sensor Networks
Abstract: We introduce a technique for accelerating the gossip algorithm of Boyd et. al. (INFOCOM 2005) for distributed averaging in a network. By employing memory in the form of a small shiftregister in the computation at each node, we can speed up the algorithm's convergence by a factor of 10. Our accelerated algorithm is inspired by the bservation that the original gossip algorithm is analogous to the ower method in Numerical Analysis, which can be accelerated by a shiftregister based recurrence.


ThIG 
Visitor Center 
Sensor Networking 
Regular Session 
Chair: Do, Minh  Univ. of Illinois 

08:3009:00, Paper ThIG.110  
Data Fusion Trees for Detection: Does Architecture Matter? 
Tay, WeePeng  MIT 
Tsitsiklis, John  MIT 
Win, Moe  MIT 
Keywords: Detection and Estimation, Sensor Networks
Abstract: We consider the problem of decentralized detection in a network consisting of a large number of sensors arranged as a tree of bounded height. We characterize the optimal error exponent under a NeymanPearson formulation. We show that the Type II error probability decays exponentially with the number of sensors, and surprisingly, the optimal error exponent is often the same as that corresponding to a star configuration. We provide sufficient, as well as necessary, conditions for this to happen.


09:0009:30, Paper ThIG.120  
Optimal Sensor Querying in Kalman Filtering 
Wu, Wei  Univ. of Texas at Austin 
Arapostathis, Ari  Univ. of Texas at Austin 
Keywords: Stochastic Systems and Control, Networked Control Systems, Sensor Networks
Abstract: In this paper, we examine a class of discretetime stochastic linear control problems for which the observations available to the controller are not fixed, but there is a number of options to choose from, and each choice has a cost associated with it. The observation costs are added to the running cost of the optimization criterion and the resulting optimal control problem is investigated. This problem is motivated by the wide deployment of networked control systems and data fusion. Since only part of the observation information is available at each time step, the controller has to balance the system performance with the penalty of the requested information (query). We study the optimal control of stochastic linear quadratic Gaussian (LQG) problem, where we show that a partial separation principle still holds. We focus primarily on the ergodic control problem and analyze the stability and the existence of the optimal control in detail.


09:3010:00, Paper ThIG.130  
Randomization for Robust Communication in Networks, or Brother, Can You Spare a Bit? 
Sarwate, Anand D.  Univ. of California, Berkeley 
Gastpar, Michael  Univ. of California, Berkeley 
Keywords: Sensor Networks in Communications, Information Theory, Wireless Communications
Abstract: Communication strategies for large distributed networks such as sensor networks or wireless adhoc networks should be robust to unknown environmental conditions. Arbitrarily varying channels (AVCs) are one way of modeling unknown interference. A recent result of the authors showed that for a Gaussian arbitrarily varying channel a small secret key shared by the transmitter and receiver could enable them to use a randomized code that is robust to the AVC interference. The question of how to acquire this small secret key is discussed for both sensor networks and adhoc wireless networks. For sensor networks some examples are given in which a sparse underlying signal can be reconstructed from correlated observations at the transmitter and receiver. For adhoc networks a cellular model for distributing the randomization is proposed and the benefits of feedback are analyzed. All of these operations can be viewed as a onetime operation  once each link has its own secret key, it can be updated at no cost to the data rate.


10:3011:00, Paper ThIG.150  
Capacity of Cooperative Fusion in the Presence of Byzantine Sensors 
Kosut, Oliver  Cornell Univ 
Tong, Lang  Cornell Univ 
Keywords: Information Theory, Sensor Networks in Communications, Wireless Communications
Abstract: The problem of cooperative fusion in the presence of both Byzantine sensors and misinformed sensors is considered. An information theoretic formulation is used to characterize the Shannon capacity of sensor fusion. It is shown that when there are fewer Byzantine sensors than honest sensors, the effect of Byzantine attack can be entirely mitigated, and the fusion capacity is identical to that when all sensors are honest. However, when at least as many sensors are Byzantine as are honest, the Byzantine sensors can completely defeat the sensor fusion so that no information can be transmitted reliably. A capacity achieving transmitthenverify strategy is proposed for the case that fewer sensors are Byzantine than honest, and its error probability and coding rate is analyzed by using a Markov decision process modeling of the transmission protocol.


11:0011:30, Paper ThIG.160  
Sensor Deployment Optimization for Network Intrusion Detection 
Yoo, TaeSic  Idaho National Lab 
Garcia, Humberto E.  Idaho National Lab 
Keywords: Intrusion/Anomaly Detection and Diagnosis, Sensor Networks, Sensor Networks in Communications
Abstract: This paper introduces a methodology for the costeffective detection of the activities of intruders within a bounded network geometry modelled with a graph. The developed methodology can be used to optimize the configuration of heterogenous sensory agents, including stationary and mobile sensors, for minimizing the expected intruder detection time and sensor deployment cost, while meeting the specified intruder detection probability requirement. Applicability of this methodology is illustrated with an example optimizing the deployment of sensor configurations to protect an illustrative complex network.


11:3011:45, Paper ThIG.171  
Location Sensing with Robust Minimax ThinPlate Splines 
Mohammad, Muqsith  Univ. of Houston 
Zheng, Rong  Univ. of Houston 
Barton, Ricard  Univ. of Houston 
Keywords: Wireless Communications, Detection and Estimation, Statistical Signal Processing
Abstract: In this paper, we propose RMTS, a localization algorithm based on the concept of robust minimax thinplate spline for indoor location sensing. Shortterm average of received signal strength (RSS) measurements from a transmitter node are modeled as a function f : R^dxR^d> R subject to certain convexity constraints. Localizing a target essentially translates into finding the inverse given measured RSS values at unknown locations. Unlike existing mapping approaches, RMTS does not require extensive site survey in RSS map construction. Empirical results demonstrate that RMTS outperforms existing methods and has comparable or better performance than a genieaided Bayesian Inference method.


ThIIA 
Library 
System Theory for Sensor Networks 
Invited Session 
Chair: Veeravalli, Venugopal  Univ. of Illinois at UrbanaChampaign 
Organizer: Veeravalli, Venu  Univ. of Illinois 

13:3014:00, Paper ThIIA.210  
Cooperative Localization Bounds for Wireless Sensor Networks (I) 
Shi, Qicai  Motorola 
Patwari, Neal  Univ. of Utah 
Kyperountas, Spyros  Motorola 
Correal, Neiyer  Motorola 
Keywords: Sensor Networks, Detection and Estimation, Statistical Signal Processing
Abstract: Wireless sensor network technology is experiencing significant growth. Integration of location capability into the wireless sensor network enables automatic localization of sensors anywhere in the area of deployment, significantly enhancing the network’s value. The combined abilities to sense, locate and communicate serve to open an exciting world of possibilities for the development of novel applications and new services. In earlier approaches to localization, location estimates were assumed to be uncoupled and were performed independently. In wireless sensor networks nodes communicate with their peers, thus augmenting the amount of information available for location estimation. Cooperative location uses peertopeer range estimates derived from packet exchanges among neighboring sensors in the estimation of the node locations. In this paper we present fundamental results on the performance of cooperative location in wireless sensor networks including network estimation bounds and validating simulation data for several example systems.


14:0014:30, Paper ThIIA.220  
Distributed Beamforming Using 1 Bit Feedback: From Concept to Realization (I) 
Mudumbai, Raghuraman  UC Santa Barbara 
Wild, Ben  UC Berkeley 
Madhow, Upamanyu  Univ. of California, Santa Barbara 
Ramchandran, Kannan  UC Berkeley 
Keywords: Wireless Communications, Sensor Networks, Sensor Networks in Communications
Abstract: We present theoretical and experimental results for a distributed beamforming system based on a simple 1bit feedback algorithm. The algorithm is based on an iterative procedure, that synchronizes multiple transmitters to cooperatively send a common message signal coherently to a receiver, using only a single bit of feedback in each timeslot. Under this algorithm, the transmitters make independent, random phase adjustments that increase the SNR at the receiver. We describe the design of an experimental prototype to implement the beamforming algorithm, and present measurement data that shows the SNR gains from beamforming. We also analyze the convergence behaviour of the algorithm mathematically using a statistical approach. We show that the mathematical model accurately predicts the behaviour of the algorithm for static and timevarying channels, and use the analysis to demonstrate the scalability of the algorithm.


14:3015:00, Paper ThIIA.230  
Ramanujan Topologies for Decision Making in Sensor Networks (I) 
Kar, Soummya  Carnegie Mellon Univ 
Moura, Jose' M. F.  Carnegie Mellon Univ 
Keywords: Sensor Networks, Sensor Networks in Communications, Detection and Estimation
Abstract: We consider the design of the topology of the communication graph {cal G}=(V,E) supporting distributed decision in sensor networks with N=V sensors. The number~M of links connecting the sensors, i.e., the number of edges E=M in the graph~cal G, is fixed. We assume a simple binary decision test where the data may be spatially correlated. The global detector performs a threshold test on a weighted fusion of the local likelihood ratios, which can be computed in a distributed fashion using a consensus algorithm. The graph topology plays a central role in the convergence speed of the distributed detector. Exhaustive search over the class of possible communication networks is unrealistic. Our solution is constructive. We first reduce this topology design to a spectral graph optimization problem; specifically, to designing the topology that maximizes the ratio gamma of the algebraic connectivity to the largest eigenvalue of the graph Laplacian. Borrowing results from spectral graph theory, we show that for the class of nonbipartite Ramanujan graphs gammageq gamma_{mbox{scriptsize min}}, where lim_{Nrightarrowinfty}gamma_Nleq gamma_{mbox{scriptsize min}} for any other regular graph. The paper discusses different available explicit constructions of Ramanujan graphs and their impact on the convergence speed of distributed consensus. In particular, it shows that these graphs perform much better even for finite values of~N than highly structured reg


15:3016:00, Paper ThIIA.250  
Sensing for Communication: The Case of Cognitive Radio (I) 
Sahai, Anant  UC Berkeley 
Tandra, Rahul  UC Berkeley 
Hoven, Niels Kang  UC Berkeley 
Mishra, Sridhar Mubaraq  UC Berkeley 


16:0016:30, Paper ThIIA.260  
SourceChannel Communication Protocols and Tradeoffs in Active Wireless Sensing (I) 
Sayeed, Akbar  Univ. of WisconsinMadison 
Sivanadyan, Thiagarajan  Univ. of Wisconsin  Madison 
Keywords: Sensor Networks, Wireless Communications, Detection and Estimation
Abstract: Active Wireless Sensing (AWS) is motivated by emerging advances in wireless technology and offers an alternative and complementary approach to innetwork processing for rapid and energyefficient information retrieval in wireless sensor networks. The basic architecture in AWS consists of: i) a wireless information retriever (WIR), equipped with an antenna array, that interrogates a select ensemble of wireless sensors with spacetime waveforms, ii) the sensors acting as active scatterers  modulating the acquired waveforms with their (possibly encoded) measured data  to generate a multipath response to the WIR's interrogation signal, and iii) the WIR retrieving the sensor data by exploiting the spacetime characteristics of the resulting multipath sensing channel. An important feature of AWS is its flexibility in tailoring the spacetime interrogation waveforms, sensor encoding strategies, and associated processing of the received multipath signal at the WIR for energyefficient information retrieval. A key mechanism for energy efficiency is distributed sourcechannel matching: generating a coherent response from subensembles of sensors with highly correlated data, based on the spatial smoothness or correlation in the signal field or on the spatial scale of local cooperation in the network. In this paper, we will discuss a family of sourcechannel matching protocols in AWS and associated tradeoffs involving rate, reliability and energy consumption of information retrieval.


16:3017:00, Paper ThIIA.270  
Optimal Power Allocation for Distributed Detection in Wireless Sensor Networks (I) 
Zhang, Xin  Princeton Univ 
Poor, H. Vincent  Princeton Univ 
Chiang, Mung  Princeton Univ 
Keywords: Sensor Networks, Detection and Estimation
Abstract: In distributed detection systems with wireless sensor networks, communication between sensors and a fusion center is not perfect due to interference and limited communication power of the sensors to combat noise. The problem of optimizing detection performance with imperfect communication between the sensors and the fusion center over wireless channels brings a new challenge to distributed detection. In this paper, a distributed detection system infrastructure is provided, and a multiaccess channel model is included to account for imperfect communication between the sensors and the fusion center. The Jdivergence between the distributions of the detection statistic under different hypotheses is used as a performance criterion in order to provide a tractable analysis. Optimizing the performance (in terms of the Jdivergence) under a total communication power constraint on the sensors is studied, and the corresponding optimal power allocation scheme is provided. It is interesting to see that, for the case with orthogonal channels, the power allocation can be solved by a weighted waterfilling algorithm. Numerical results are used to illustrate the solution.


ThIIB 
Porch 
Joint SourceChannel Coding and Iterative Source Coding 
Invited Session 
Chair: Shamir, Gil  Univ. of Utah 
Organizer: Shamir, Gil  Univ. of Utah 
Organizer: Singer, Andrew  Univ. of Illinois 

13:3014:00, Paper ThIIB.210  
On the Shannon Cipher System with a CapacityLimited Key Distribution Channel (I) 
Merhav, Neri  Tech.  Israel Inst. of Tech 
Keywords: Information Theory
Abstract: We consider the Shannon cipher system in a setting where the secret key is delivered to the legitimate receiver via a channel with limited capacity. For this setting, we characterize the achievable region in the space of three figures of merit: the security (measured in terms of the equivocation), the compressibility of the cryptogram, and the distortion associated with the reconstruction of the plaintext source. Although lossy reconstruction of the plaintext does not rule out the option that the (noisy) decryption key would differ, to a certain extent, from the encryption key, we show, nevertheless, that the best strategy is to strive for perfect match between the two keys, by applying reliable channel coding to the key bits, and to control the distortion solely via ratedistortion coding of the plaintext source before the encryption. In this sense, our result has a flavor similar to that of the classical sourcechannel separation theorem. Some variations and extensions of this model are discussed as well.


14:0014:30, Paper ThIIB.220  
Joint SourceChannel Coding for the Arbitrarily Varying WynerZiv Source and Gel'fandPinsker Channel (I) 
Winshtok, Amir  Tech.  IIT 
Steinberg, Yossef  Tech.  IIT 
Keywords:
Abstract: In this work we characterize the ratedistortion function of a WynerZiv source, depending on an arbitrarily varying state, known noncausally at the encoder. We then consider the problem of joint sourcechannel coding of this source transmitted over an arbitrarily varying Gel'fandPinsker channel, where we assume that one jammer controls both, the source state sequence and the channel state sequence. Utilizing our result, and a previous result by Ahlswede on the capacity of the arbitrarily varying Gel'fandPinsker channel, we show that a separation principle for this setup holds. A by product of this result is that the best strategy for the jammer, is to choose the source state and the channel state sequences in such a manner, that the WynerZiv source and the Gel'fandPinsker channel look like independent of each other. This implies that a separation holds also with respect to the operation of the jammer, as the jammer employing the best strategy (from his point of view) can be split into two non cooperating jammers, one of which controls only the source state sequence, and the other controls only the channel state sequence.


14:3015:00, Paper ThIIB.230  
Fountain Codes for the SlepianWolf Problem (I) 
Shokrollahi, Amin  EPFL 
Ndzana Ndzana, Bertrand  EPFL 


15:3016:00, Paper ThIIB.250  
Analysis of Belief Propagation for NonSystematic LDPC Codes with Redundant Data (I) 
Alloum, Amira  Ec. Nationale Superieure des Telecommunications (ENST) 
Boutros, Joseph Jean  Ec. Nationale Superieure des Telecommunications (ENST) 
Shamir, Gil  Univ. of Utah 

16:0016:30, Paper ThIIB.260  
Design Considerations for IterativelyDecoded SourceChannel Coding Schemes (I) 
Thobaben, Ragnar  Univ. of Kiel 
Kliewer, Joerg  Univ. of Notre Dame 
Keywords: Iterative Coding Techniques, Coding Techniques and Applications, Source Coding and Compression
Abstract: We address outer variablelength encoding of a firstorder Markov source in a serially concatenated coding scheme with an inner recursive convolutional code. Decoding is carried out iteratively between the constituent decoders for variablelength and convolutional code. While variablelength codes are commonly known to be sensitive to transmission errors, we show that they can lead to significant performance improvements compared to fixedlength source encoding with optimized mappings. Specifically, we propose a simple variablelength code construction with a free distance of two and good compression properties at the same time. Numerical results show that the performance gain of the proposed approach also holds for precoded ISI channels where iterative joint source channel equalization and decoding is employed at the receiver.


ThIIC 
Butternut 
Multiuser Information Theory 
Regular Session 
Chair: Coleman, Todd  Univ. of Illinois at UrbanaChampaign 

13:3014:00, Paper ThIIC.210  
RateSplitting and Its Applications for a General Wireless Channel 
Gopalan, RaviKiran  Univ. of Notre Dame 
Ranganathan, Shyam  Univ. of Notre Dame 
Padmanabhan, Krishnan  Univ. of Notre Dame 
Collins, Oliver  Univ. of Notre Dame 
Keywords: MIMO Systems, Information Theory, Wireless Communications
Abstract: In a general multitransmitter, multireceiver system employing successive decoding, individual user capacities can be equalized without any loss in the sum capacity of the system. This paper considers an N transmitter, K receiver wireless network with successive decoding at the receiver and an arbitrary channel between the transmitters and receivers. The ratesplitting algorithm presented in the paper splits each user (transmitted signal) into two virtual users and then equalizes the user capacities by choosing the power of the virtual users and the order of decoding. One practical application is a successive decoding receiver scheme for a Rayleigh flatfading MIMO channel. The achievable rate of this scheme, plotted in this paper, serves as a constructive lower bound on the MIMO channel capacity. The paper also derives an upper bound, and demonstrates that these two bounds tightly define the true MIMO capacity of the network, so that the successive decoding scheme nearly achieves capacity.


14:0014:30, Paper ThIIC.220  
Secrecy Capacity Region of Binary and Gaussian Multiple Access Channels 
Liang, Yingbin  Princeton Univ 
Poor, H. Vincent  Princeton Univ 
Keywords: Information Theory
Abstract: A generalized multiple access channel (GMAC) with one confidential message set is studied, where two users (users 1 and 2) attempt to transmit common information to a destination, and user 1 also has confidential information intended for the destination. Moreover, user 1 wishes to keep its confidential information as secret as possible from user 2. A deterministic GMAC is first studied, and the capacityequivocation region and the secrecy capacity region are obtained. Two main classes of the GMAC are then studied: the binary GMAC and the Gaussian GMAC. For both channels, the capacityequivocation region and the secrecy capacity region are established.


14:3015:00, Paper ThIIC.230  
Asymptotic Transport Capacity of Wireless Erasure Networks 
Smith, Brian  Univ. of Texas at Austin 
Vishwanath, Sriram  Univ. of Texas at Austin 
Keywords: Information Theory, Performance Analysis, Wireless Communications
Abstract: We investigate the transport capacity, or the distanceweighted sum of rates, of wireless erasure networks. These memoryless networks are characterized by independent erasure channels between the nodes, and a wireless broadcast requirement that each node must send the same signal on all of its outgoing channels. Our innovation to the model involves introducing a dependence between the probability of an erasure event over a channel and the physical, geometric distance between the two nodes connected by that channel. We show, under a minimum node separation constraint and for three different models for erasure probability as a function of distance, that transport capacity is upperbounded by a constant multiplied by n, the total number of nodes. Thus, transport capacity can grow no faster than linearly in the number of nodes.


15:3016:00, Paper ThIIC.250  
Asymptotic Analysis of Downlink OFDMA Capacity 
Chen, Jieying  Northwestern Univ 
Berry, Randall  Northwestern Univ 
Honig, Michael  Northwestern Univ 
Keywords: Wireless Communications, Information Theory
Abstract: We consider asymptotic performance of a downlink OFDMA system as the number of users and subchannels increase. Specifically, we study the asymptotic growth in the weighted sum capacity, where each user is assigned a weight to reflect its quality of service. We begin by considering a limited feedback scheme, where each user is preassigned a threshold and feeds back one bit per subchannel to indicate whether the channel gain is above the threshold or not. If more than one user requests the same subchannel, the base station picks the user with the largest weight to transmit. In earlier work we analyzed such a scheme when each user has i.i.d. Rayleigh fading on each subchannel. Here we consider a larger class of distributions that includes most common fading models. We characterize the asymptotic behavior of the optimal thresholds and the growth of the weighted sum capacity. We then compare the asymptotic capacity achieved by this one bit feedback scheme with the capacity when full CSI is available at the transmitter. We derive upper and lower bounds on the capacity with full CSI. The difference between these bounds asymptotically converges to a constant and the lower bound converges to the capacity of the onebit feedback scheme.


16:0016:30, Paper ThIIC.260  
On an Improvement Over R'enyi's Equivocation Bound 
Santhi, Nandakishore  Univ. of California San DIego 
Vardy, Alexander  Univ. of California San Diego 
Keywords: Detection and Estimation, Information Theory, Coding Theory
Abstract: We consider the problem of estimating the probability of error in multihypothesis testing when MAP criterion is used. This probability, which is also known as the Bayes risk is an important measure in many communication and information theory problems. In general, the exact Bayes risk can be difficult to obtain. Many upper and lower bounds are known in literature. One such upper bound is the equivocation bound due to R'enyi which is of great philosophical interest because it connects the Bayes risk to conditional entropy. Here we give a simple derivation for an improved equivocation bound. We then give some typical examples of problems where these bounds can be of use. We first consider a binary hypothesis testing problem for which the exact Bayes risk is difficult to derive. In such problems bounds are of interest. Furthermore using the bounds on Bayes risk derived in the paper and a random coding argument, we prove a lower bound on equivocation valid for most random codes over memoryless channels.


16:3016:45, Paper ThIIC.271  
An Outer Bound for a Multiuser TwoWay Channel 
Dash, Debashis  Rice Univ 
Sabharwal, Ashutosh  Rice Univ 
Keywords: Information Theory, Network Coding in Communication, Wireless Communications
Abstract: Most networks are twoway in nature, i.e., senders are also receivers. However, little is known about twoway networks except for the simplest twoway channel between two nodes, first proposed and studied by Shannon in 1961. In this paper, we continue our study of a threenode multiuser twoway channel first proposed in a previous paper cite{dash06}. Our main result is an outer bound on the capacity region of the threenode network where each node operates in halfduplex mode. The key challenge in deriving the outer bound stems from the infinite Markov chain structure induced by the implicit feedback in encoding at each node. We show that the outer bound reduces to wellknown results in multiple access and broadcast channels in several special cases.


16:4517:00, Paper ThIIC.272  
Bounds on the Capacity of the Soft Handover Channel 
Rajan, Dinesh  Southern Methodist Univ 
Muharemovic, Tarik  Texas Inst 
Keywords: Information Theory, Wireless Communications
Abstract: In this paper, we introduce the model for a Gaussian soft handover channel and investigate an achievable region for its capacity. The achievable region is given by the convex hull of the union of certain multiple access and interference channels. Some properties of the achievable region are studied .


17:0017:15, Paper ThIIC.281  
Achievable Sum Rate Bounds of ZeroForcing Based Linear MultiUser MIMO Systems 
Chae, ChanByoung  The Univ. of Texas at Austin 
Heath, Robert  The Univ. of Texas at Austin 
Mazzarese, David  Samsung Electronics 
Keywords: MIMO Systems, Wireless Communications
Abstract: In this paper, jointly optimized linear transmit beamforming and receive processing for the downlink of a multiuser multiple input multiple output (MIMO) system is investigated. In this system the base station, equipped with multiple antennas, transmits to several users, who are also equipped with multiple antennas. To solve the dimensionality constraint that conventional block diagonalization (BD) has, we use an iterative based coordinated beamforming (CBF) method and also consider block diagonalization with receive antenna selection (BDRAS) for performance comparison. We show the upper and lower bounds on ergodic sum rate of CBF and BDRAS. Analysis and simulation results show that the proposed beamforming always outperforms conventional BDRAS, and achieves a sum rate close to the MIMO broadcast channel (BC) sum capacity.


ThIID 
Pine 
Challenges in Speech Communication Over Digital Channels 
Invited Session 
Chair: HasegawaJohnson, Mark  Univ. of Illinois 
Organizer: HasegawaJohnson, Mark  Univ. of Illinois 
Organizer: McLaughlin, Mike  Motorola 
Organizer: Jasiuk, Mark  Motorola 

13:3014:00, Paper ThIID.210  
The ITUT Embedded Variable Bit Rate Speech Coder  Requirements and Standardization (I) 
Gibbs, Jonathan Alastair  Motorola UK Ltd 
Keywords: Speech Processing, Source Coding and Compression, Network Coding in Communication
Abstract: In Spring 2007, Study Group 16 of the ITUT will select a baseline algorithm for the development of an embedded speech codec operating from 8kb/s to in excess of 48 kb/s. This codec, due to be completed in 2008, will provide quality telephone band and wideband speech at the core data rate of 8kb/s and, through the gradual addition of enhancement layers, a stereo audio capability at the highest bit rates. A key feature of this codec is that, in addition to providing high quality, it is also designed to provide high resilience to packet loss. This paper describes in detail the requirements for the codec and also describes the standardization process, which is new to the area of speech coding in the ITUT.


14:0014:30, Paper ThIID.220  
A Framework for CodedDomain Acoustic Echo Control (I) 
Sukkar, Rafid  Tellabs, Inc 
Younce, Rick  Tellabs, Inc 
Zhang, Peng  Tellabs, Inc 
Keywords: Speech Processing
Abstract: In new generation networks like 3G wireless and VoIP, a great deal of emphasis is put on transcoderfree operation (TrFO), where speech remains coded throughout the core network. Any networkbased speech processing function must, therefore, operate on the coded parameters directly if the value of TrFO is to be realized. One of these functions is acoustic echo control. Given that an intermediate step of decoding/reencoding is not an option, we present, in this paper, a framework and a method for performing acoustic echo control directly in the codeddomain. We consider acoustic echo control as dynamic amplitude scaling of the speech signal. We derive expressions for modifying the relevant coded parameters such that the resulting decoded speech would correspond to the desired scaled signal. Experimentally, we use the AMR 12.2 kbps coder, and show that the proposed method results in a signal whose level, as well as speech quality, closely matches the desired scaled signal.


14:3015:00, Paper ThIID.230  
Distributed Acquisition and Processing Systems for Speech and Audio (I) 
Anderson, David  Georgia Inst. of Tech 
Ravindran, Sourabh  Georgia Inst. of Tech 
Keywords: Sensor Networks, Speech Processing, VLSI Signal Processing
Abstract: In surveillance, audio signal acquisition over large spaces, and related applications it may be useful or necessary to use networks of acoustic sensors. In many cases the sensor network has or would benefit from constraints on power, form factor, and bandwidth. In this paper, we discuss some characteristics of audio sensor networks in which processing is done in a distributed manner, at the sensor. We also discuss some applications and processing paradigms for such systems.


15:3016:00, Paper ThIID.250  
Evaluation of Speech Quality in Communication Systems (I) 
Sharpley, Alan  Dynastat, Inc. 

ThIIE 
Lower Level 
Coding Theory III 
Invited Session 
Chair: Vontobel, Pascal  HewlettPackard Lab 
Organizer: Ashikhmin, Alexei  Bell Lab. Tech 
Organizer: Koetter, Ralf  Univ. of Illinois 

13:3014:00, Paper ThIIE.210  
Probabilistic Analysis of Linear Programming Decoding (I) 
Daskalakis, Constantinos  Univ. of California, Berkeley 
Dimakis, Alexandros  UC Berkeley 
Karp, Richard  Univ. of California, Berkeley 
Wainwright, Martin  UC Berkeley 
Keywords:
Abstract: We initiate the probabilistic analysis of linear programming (LP) decoding of lowdensity paritycheck (LDPC) codes. Specifically, we show that for a random LDPC code ensemble, the linear programming decoder of Feldman et al. succeeds in correcting a constant fraction of errors with high probability. The fraction of correctable errors guaranteed by our analysis surpasses all prior nonasymptotic results for LDPC codes, and in particular exceeds the best previous finitelength result on LP decoding by a factor greater than ten. This improvement stems in part from our analysis of probabilistic bitflipping channels, as opposed to adversarial channels. At the core of our analysis is a novel combinatorial characterization of LP decoding success, based on the notion of a generalized matching. An interesting byproduct of our analysis is to establish the existence of ``almost expansion'' in random bipartite graphs, in which one requires only that almost every (as opposed to every) set of a certain size expands, with expansion coefficients much larger than the classical case.


14:0014:30, Paper ThIIE.220  
A General Computation Rule for Lossy Summaries/Messages with Examples from Equalization (I) 
Hu, Junli  ETH Zurich 
Dauwels, Justin  RIKEN Brain Science Inst 
Kschischang, Frank R.  Univ. of Toronto 
Loeliger, HansAndrea  ETH Zurich 
Keywords:
Abstract: Elaborating on prior work by Minka, we formulate a general computation rule for lossy messages. An important special case (with many applications in communications) is the conversion of "softbit" messages to Gaussian messages. By this method, the performance of a MMSE equalizer is improved, both for uncoded and coded transmission.


14:3015:00, Paper ThIIE.230  
A Scaling Law for Gallager A (I) 
Ezri, Jeremie  EPFL (Lausanne) 
Montanari, Andrea  Stanford Univ 
Urbanke, Rudiger  EPFL (Lausanne) 
Keywords:
Abstract: We consider LDPC codes, transmission over the binary symmetric channel (BSC), and decoding using Gallager's algorithm A. For those ensembles whose threshold is determined by the behavior of the algorithm at the beginning of the decoding process we derive a scaling law. This scaling law has the same form as the scaling law which established for the the case of transmission over the binary erasure channel. We show how the scaling parameters can be computed and point out some interesting open challenges.


15:3016:00, Paper ThIIE.250  
The Asymptotic Error Floor of LDPC Ensembles under BP Decoding (I) 
Montanari, Andrea  Stanford Univ 
Keywords:
Abstract: We consider communication over binary memoryless symmetric channels using random elements from irregular low density parity check code (LDPC) ensembles, and belief propagation (BP) decoding. Under the assumption that the corresponding Tanner graph includes a nonvanishing fraction of degree 2 variable nodes, we determine the large blocklength behavior of the bit error rate for noise levels below threshold. More precisely, we show that the BP bit error rate is, asymptotically, K/n, where n is the blocklength and K an explicit constant. Surprisingly, this is the same behavior found for maximum likelihood (ML)decoding, implying that the BP and ML error floor are asymptotically equal.


16:0016:30, Paper ThIIE.260  
Computational Hardness and Explicit Constructions of Error Correcting Codes (I) 
Cheraghchi, Mahdi  EPFL 
Shokrollahi, Amin  EPFL 
Widgerson, Avi  Inst. for Advanced Studies 
Keywords:
Abstract: We outline a procedure for using pseudorandom generators to construct binary codes with good properties, assuming the existence of sufficiently hard functions.


16:3017:00, Paper ThIIE.270  
Achieving List Decoding Capacity Using Folded ReedSolomon Codes (I) 
Guruswami, Venkatesan  Univ. of Washington 
Rudra, Atri  Univ. of Washington 
Keywords:
Abstract: We present errorcorrecting codes that achieve the informationtheoretically best possible tradeoff between the rate and errorcorrection radius. Specifically, for every 0 < R < 1 and eps > 0, we present an explicit construction of errorcorrecting codes of rate R that can be list decoded in polynomial time up to a fraction (1Reps) of errors. At least theoretically, this meets one of the central challenges in algorithmic coding theory. Our codes are simple to describe: they are {em folded ReedSolomon codes}, which are in fact {em exactly} ReedSolomon codes, but viewed as a code over a larger alphabet by careful bundling of codeword symbols. Given the ubiquity of RS codes, this is an appealing feature of our result, and in fact our methods directly yield better decoding algorithms for RS codes when errors occur in phased bursts. These results were first reported in (Guruswami and Rudra, STOC 2006). The description in this paper, though, is different and the codes are based on a different, more flexible, version of folding. The algebraic argument underlying the decoding algorithm is also simpler, and leads to a slightly better bound on decoding complexity and worstcase list size.


ThIIF 
Brick 
Resource Allocation Networks 
Regular Session 
Chair: Meyn, Sean  Univ. of Illinois 

13:3014:00, Paper ThIIF.210  
Resource Allocation and Quality of Service Evaluation for Wireless Communication Systems Using Fluid Models 
Liu, Lingjia  Texas A&M Univ 
Parag, Parimal  Texas A&M Univ 
Tang, Jia  Texas A&M Univ 
Chen, WeiYu  Texas A&M Univ 
Chamberland, JeanFrancois  Texas A&M Univ 
Keywords: Wireless Communications, Queuing Theory and Analysis, Performance Analysis
Abstract: Wireless systems offer a unique mixture of connectivity, flexibility, and freedom. It is therefore not surprising that wireless technology is being embraced with increasing vigor. For realtime applications, user satisfaction is closely linked to quantities such as queue length, packet loss probability, and delay. System performance is therefore related to, not only Shannon capacity, but also Quality of Service (QoS) requirements. This work studies the problem of resource allocation in the context of stringent QoS constraints. The joint impact of spectral bandwidth, power, and coderate is considered. Analytical expressions for the probability of buffer overflow, its associated exponential decay rate, and the effective capacity are obtained. Fundamental performance limits for Markov wireless channel models are identified. It is found that, even with an unlimited power and spectral bandwidth budget, only a finite arrival rate can be supported for a QoS constraint defined in terms of exponential decay rate.


14:0014:30, Paper ThIIF.220  
CrossLayer Congestion and Contention Control for Wireless Ad Hoc Networks 
Yu, Yingqun  Univ. of Minnesota 
Giannakis, Georgios  Univ. of Minnesota 
Keywords: Pricing and Congestion Control, Performance Analysis
Abstract: We consider joint congestion and contention control for multihop wireless ad hoc networks, where the goal is to find optimal endtoend source rates at the transport layer and perlink persistence probabilities at the medium access control (MAC) layer to maximize the aggregate source utility. The primal formulation of this problem is nonconvex and nonseparable. Under certain conditions, by applying appropriate transformations and introducing new variables, we obtain a decoupled and dualdecomposable convex formulation. For general nonlogarithmic concave utilities, we develop a novel dualbased distributed algorithm using the subgradient method. For logarithmic utilities, we introduce two modified algorithms: a heuristic one with linearly regularized log rate adjustments and a penaltybased one by adding a quadratic term to the linear objective. For both logarithmic and nonlogarithmic utilities, our solutions enjoy the benefits of crosslayer optimization while maintaining the simplicity and modularity of the traditional layered architecture.


14:3015:00, Paper ThIIF.230  
Implementation in Nash Equilibria of a Rate Allocation Problem in Networks 
Stoenescu, Tudor  California Inst. of Tech 
Ledyard, John  California Inst. of Tech 
Keywords: Pricing and Congestion Control, Networked Control Systems, Decentralized and Distributed Control
Abstract: We present a novel pricing mechanism which achieves a solution to a rate allocation problem in unicast service provisioning. This mechanism is different from the ones which appear in the existing literature since it accounts for the strategic behavior of individual users and achieves efficient allocations. The main features of this mechanism are: (i) it implements the rate allocation problem in Nash equilibria; (ii) it is budget balanced; and (iii) it is incentive compatible. We also provide some insight on how one may generalize this mechanism.


15:3016:00, Paper ThIIF.250  
The Estimation Error of Adaptive Deterministic Packet Marking 
Andrew, Lachlan  Caltech 
Hanly, Stephen Vaughan  Univ. of Melbourne 
Keywords: Pricing and Congestion Control, Stochastic Systems and Control, Performance Analysis
Abstract: This paper is concerned with problem of signalling congestion link price information to a receiver using single bit marks. An efficient method was presented in (Andrew et al. 07) which exploits side information in the IPid field of the IP header to allow the maximum price on a flow's path to be estimated. In this paper we provide analysis to support the claim that the scheme can track a changing price. We consider a random walk model for the price, and provide a weak convergence result showing that the squared error (normalized by the drift) is asymptotically exponentially distributed, as the drift tends to zero.


16:0016:30, Paper ThIIF.260  
Limits on Reverse Link Capacity of Large Wireless Networks with Fading 
Gopalan, RaviKiran  Univ. of Notre Dame 
Collins, Oliver  Univ. of Notre Dame 
Keywords: MIMO Systems, Information Theory, Wireless Communications
Abstract: This paper evaluates lower and upper bounds on the capacity of large cellular networks, and proves that the introduction even of very slow fading causes the peruser capacity to decay toward zero as the number of users increases. The capacity calculated in this paper is an upper bound on the capacity of all existing and foreseeable cellular networks, so the decaying peruser capacity is a fundamental constraint on the emergence of truly ubiquitous cellular networks. This paper considers a cellular network of N transmitters (users) and K receivers (base station), where the transmitters and receivers are uniformly distributed over a grid in a 3D, 2D, or 1D universe. The transmitters transmit with a power P_0 and the receivers receive the transmitted signals with a power inversely proportional to the second, third or the fourth power of their distance from the transmitter and are allowed complete cooperation. The channel between the transmitters and the receivers is Rayleigh flatfading, and neither the transmitters nor the receivers have any knowledge of the fading realizations. This paper also demonstrates the existence of simple schemes that approach the true capacity of the channel to within a multiplicative constant.


16:3017:00, Paper ThIIF.270  
Optimal Rate Allocation in a Wireless AdHoc Network 
Ehsan, Navid  Univ. of California, San Diego 
Cruz, Rene  Univ. of California, San Diego 
Keywords: Wireless Communications, Stochastic Systems and Control, Performance Analysis
Abstract: In this paper we study the effect of variable rate transmission on the performance of wireless adhoc networks. Specifically we consider two cases: a fixed rate system and a variable rate system. In the fixed rate system, all users can transmit with a fixed rate which is decided in advance. We study the problem of finding an optimal transmission rate for this system. In the second case the rate is variable and can be changed depending on the intended receiver. The smaller the transmission rate, the farther the intended receiver can be located. This however increases the probability of colliding with other users' transmissions. We model this tradeoff in both systems. When all the parameters of the two are optimally chosen, we compare their performance. We also study the effect of having a finite set of rates and study the performance as the set of available rates increases.


17:0017:15, Paper ThIIF.281  
Loss Rates in Large Loss Systems with Subexponential Demands 
Radovanovic, Ana  IBM T.J. Watson Res. Center 
Lu, Yingdong  IBM T.J. Watson Res. Center 
Keywords: Performance Analysis, Queuing Theory and Analysis, Stochastic Systems and Control
Abstract: The analysis of stochastic loss networks has long been of interest in telephone engineering, and is becoming important in the areas of service and information systems, workforce management and inventory control. In more traditional settings, where requests for fixed amount of resources arrive as Poisson process and require them for some almost surely finite time, it is well known that the request loss rate can be explicitly computed using a generalization of the well known Erlang formula. However, computing loss rates for these systems becomes intractable, since the state space increases exponentially fast. Using compound point processes to capture stochastic variability in the request process, we introduce a new class of models in this framework that allows us to compute simple asymptotic expressions for loss rates in a quite general setting. Assuming that requests arrive according to a renewal process, requiring resources for some random time with finite mean, we compute an explicit asymptotic formula for the request loss rate as resource capacity grows large. In addition, we extend our model to incorporate requests for different resource types, as well as advance reservations. Although asymptotic, our experiments show excellent match between derived formulas and simulation results even for relatively small resource capacities and relatively large values of loss rates.


ThIIG 
Visitor Center 
Algebraic and Combinatorial Coding Theory 
Regular Session 
Chair: Duursma, Iwan  Univ. of Illinois 

13:3014:00, Paper ThIIG.210  
Identifying Codes and the Set Cover Problem 
Laifenfeld, Moshe  Boston Univ 
Trachtenberg, Ari  Boston Univ 
BergerWolf, Tanya  Univ. of Illinois 
Keywords: Coding Theory, Coding Techniques and Applications, Sensor Networks in Communications
Abstract: We consider the problem of finding a minimum identifying code in a graph, i.e., a designated set of vertices whose neighborhoods uniquely overlap at any vertex on the graph. This identifying code problem was initially introduced in 1998 and has been since fundamentally connected to a wide range of applications, including fault diagnosis, location detection, environmental monitoring, and connections to information theory, superimposed codes, and tilings. Though this problem is NPcomplete, its known reduction is from 3SAT and does not readily yield an approximation algorithm. In this paper we show that the identifying code problem is computationally equivalent to the set cover problem and present a Theta(log n)approximation algorithm based on the greedy approach for set cover; we further show that, subject to reasoanble assumptions, no polynomialtime approximation algorithm can do better. Finally, we show that a generalization of the identifying codes problem, for which no complexity results were known thusfar, is NPhard.


14:0014:30, Paper ThIIG.220  
The Tradeoff between Cyclic Topology and Complexity in Graphical Models of Linear Codes 
Halford, Thomas R  Univ. of Southern California 
Chugg, Keith M  Univ. of Southern California 
Keywords: Iterative Coding Techniques, Coding Theory
Abstract: It is now wellknown that together with a suitable message passing schedule, a graphical model for a code implies a softin softout (SISO) decoding algorithm which is optimal for cyclefree models and suboptimal, yet often substantially less complex, for cyclic models. The CutSet Bound (CSB) indicates that the introduction of cycles to graphical models can lead to dramatic reductions in complexity and in the case of tailbiting trellises (i.e. singlecycle models), the CSB can be used to establish the squareroot bound, thus quantifying this potential reduction precisely. The aim of this work is to provide such a precise characterization of the tradeoff between cyclic topology and complexity (i.e. maximum hidden variable size and local constraint complexity) in graphical models with more than one cycle. To this end, a new bound is introduced  the treeinducing cutset bound  which can be viewed as a generalization of the squareroot bound to graphical models with arbitrary cyclic topologies.


14:3015:00, Paper ThIIG.230  
Algebraic SoftDecision Decoding of ReedSolomon Codes Using BitLevel Soft Information 
Jiang, Jing  Texas A&M Univ 
Narayanan, Krishna  Texas A&M Univ 
Keywords: Coding Techniques and Applications, Coding Theory, Data Storage
Abstract: The performance of algebraic softdecision decoding (ASD) of ReedSolomon (RS) codes using bitlevel soft information is investigated. Based on the performance analysis of ASD over the binary erasure channel (BEC) and the binary symmetric channels (BSC), we study the multiplicity assignment strategies (MAS) and the corresponding performance analysis of ASD for medium to high rate RS codes over a mixed bitlevel error and erasure channel. The bitlevel decoding region of the proposed MAS is shown to be significantly larger than that of conventional BerlekampMassey (BM) decoding. As an important application, a bitlevel generalized minimum distance (BGMD) decoding algorithm is proposed. The proposed BGMD compares favorably with many other RS softdecision decoding algorithms on various channels. Moreover, owing to the simplicity of BGMD, its performance can be tightly bounded using ordered statistics.


15:3016:00, Paper ThIIG.250  
The Stopping Redundancy Hierarchy of Cyclic Codes 
Hehn, Thorsten  Univ. of ErlangenNuremberg 
Laendner, Stefan  Univ. of Colorado at Boulder 
Milenkovic, Olgica  Univ. of Colorado at Boulder 
Huber, Johannes B.  Univ. of ErlangenNuremberg 
Keywords: Iterative Coding Techniques, Coding Theory, Information Theory
Abstract: We extend the framework for studying the stopping redundancy of a linear block code by introducing and analyzing the stopping redundancy hierarchy. The stopping redundancy hierarchy of a code represents a measure of the tradeoff between performance and complexity of iteratively decoding a code used over the binary erasure channel. It is defined as an ordered list of positive integers in which the ith entry, termed the ith stopping redundancy, corresponds to the minimum number of rows in any paritycheck matrix of the code that has stopping distance at least i. In particular, we derive lower and upper bounds for the ith stopping redundancy of a code by using probabilistic methods and Bonferronitype inequalities. Furthermore, we specialize the findings for cyclic codes, and show that paritycheck matrices in cyclic form have some desirable redundancy properties. We also propose to investigate the influence of the generator codeword of the cyclic paritycheck matrix on its stopping distance properties.


16:0016:30, Paper ThIIG.260  
A Multiple Lattice Reduction Based Detector for Space Time Block Codes Based on Cyclotomic Extensions 
Gopalan, Aditya  Indian Inst. of Tech. Madras 
Bhashyam, Srikrishna  Indian Inst. of Tech. Madras 
Keywords: MIMO Systems, Wireless Communications, Detection and Estimation
Abstract: Full diversity highrate Space Time Block Codes (STBCs) based on cyclotomic field extensions can be decoded by LenstraLenstraLovasz (LLL) lattice reductionaided linear equalization followed by appropriate zero forcing. LLL lattice reductionaided linear equalization enables lower complexity decoding compared to sphere decoding, while resulting in a performance loss. In this paper, we propose a new suboptimal detection algorithm which exploits the algebraic structure of this class of STBCs and applies LLL lattice reductionbased detection multiple times on the received spacetime symbol to arrive at an estimate of the transmitted codeword matrix. The decoding complexity is still significantly lower than sphere decoding complexity. Using simulations, the proposed scheme is shown to perform better than the conventional LLL reductionbased scheme in terms of bit error rate. We also point out that the computational effort for the multiple lattice reductionbased scheme can be significantly reduced for codes over certain numbers of transmit antennas.


16:3017:00, Paper ThIIG.270  
Efficient Computation of the Binary Vector That Maximizes a Rank3 Quadratic Form 
Karystinos, George  Tech. Univ. of Crete 
Liavas, Athanasios  Tech. Univ. of Crete 
Keywords: Coding Techniques and Applications, MIMO Systems, Multiuser Detection and Estimation
Abstract: The maximization of a positive (semi)definite quadratic form with a binary vector is NPhard and achieved through exhaustive search when the form has full rank. However, if the form is rankdefficient, then exponentialcomplexity exhaustive search may not be necessary. In this work, we consider a rank3 positive semidefinite quadratic form and develop a method that maximizes the form with respect to a binary vector with polynomial complexity. Our method utilizes auxiliary spherical coordinates and partitions the threedimensional space into a polynomialsize set of regions, where each region corresponds to a distinct binary vector. The binary vector that maximizes the rank3 quadratic form is shown to belong to the polynomialsize set of vectors. Therefore, the proposed method efficiently reduces the size of the feasible set from exponential to polynomial. Interestingly enough, following similar principles of auxiliary spherical coordinates our method can be extended to even higherrank quadratic forms where a hyperspace is divided into a finite set of regions and each region corresponds to a distinct binary vector.

 