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

WIA 
Library 
Coding Theory I 
Invited Session 
Chair: Milenkovic, Olgica  Univ. of Colorado at Boulder 
Organizer: Koetter, Ralf  Univ. of Illinois 
Organizer: Ashikhmin, Alexei  Bell Lab. Tech 

08:3009:00, Paper WIA.110  
An Improved SpherePacking Bound Targeting Short to Moderate Block Codes and Applications (I) 
Wiechman, Gil  Tech 
Sason, Igal  Tech.  Israel Inst. of Tech 
Keywords:
Abstract: This paper derives an improved spherepacking (ISP) bound targeting codes of short to moderate block lengths. We first review the 1967 spherepacking (SP67) bound for discrete memoryless channels, and a recent improvement by Valembois and Fossorier. These concepts are used for the derivation of a new lower bound on the decoding error probability (referred to as the ISP bound) which is uniformly tighter than the SP67 bound and its recent improved version. Under a mild condition, the ISP bound is applicable to general memoryless channels, and some of its applications are exemplified. Its tightness is studied by comparing it with bounds on the ML decoding error probability. It is exemplified that the ISP bound suggests an interesting alternative to the 1959 spherepacking (SP59) bound of Shannon for the Gaussian channel, especially for digital modulations of high spectral efficiency.


09:0009:30, Paper WIA.120  
Analysis of DoublyGeneralized LDPC Codes with Random Component Codes for the Binary Erasure Channel (I) 
Paolini, Enrico  Univ. of Bologna, Italy 
Fossorier, Marc  Univ. of Hawaii 
Chiani, Marco  Univ. of Bologna, Italy 
Keywords:
Abstract: A method for the asymptotic analysis of doublygeneralized lowdensity paritycheck (DGLDPC) codes on the binary erasure channel (BEC) is described. The proposed method is based on extrinsic information transfer (EXIT) charts. It permits to overcome the impossibility to evaluate the EXIT function for the check or variable component codes, in situations where the information functions or split information functions for the component code are unknown. According to the proposed method, DGLDPC codes where the check and variable component codes are random codes from an expurgated ensemble, are considered. A technique is then developed which permits to obtain the EXIT chart for the overall DGLDPC code, by evaluating the expected EXIT function for each check and variable component code. This technique is then combined with differential evolution (DE) algorithm in order to generate some optimal DGLDPC degree distributions. Numerical results on long, random codes, are presented which reveal how DGLDPC codes can outperform standard LDPC codes in terms of both waterfall performance and error floor.


09:3010:00, Paper WIA.130  
A FactorGraph Approach to Universal Decoding (I) 
Vontobel, Pascal  HewlettPackard Lab 
Keywords:
Abstract: We consider data communication over a discrete memoryless channel where neither the sender nor the receiver knows the channel law. The setup is universal in the sense that no training sequence is allowed, i.e. no position of the channel code is allowed to be fixed to a certain symbol. We discuss a variety of approaches for solving this problem efficiently. It turns out that it is worthwhile to design decoders which try to minimize the symbol error probability. This is in contrast to the usual approach where the block error probability is minimized. As a side result, we present a very simple derivation of the socalled onesweep algorithm by Johansson and Zigangirov. In the context of universal channel decoding, this algorithm has certain structural advantages over the BCJR algorithm.


10:3011:00, Paper WIA.150  
Loop Calculus Helps to Improve Belief Propagation and Linear Programming Decodings of LowDensityParityCheck Codes (I) 
Chertkov, Michael  Los Alamos National Lab 
Chernyak, Vladimir Y.  Wayne State Univ 
Keywords:
Abstract: We illustrate the utility of the recently developed loop calculus for improving the Belief Propagation (BP) algorithm. If the algorithm that minimizes the Bethe free energy fails we modify the free energy by accounting for a critical loop in a graphical representation of the code. The loglikelihood specific critical loop is found by means of the loop calculus. The general method is tested using an example of the Linear Programming (LP) decoding, that can be viewed as a special limit of the BP decoding. Considering the (155,64,20) code that performs over AdditiveWhiteGaussian channel we show that the loop calculus improves the LP decoding and corrects all previously found dangerous configurations of loglikelihoods related to pseudocodewords with low effective distance, thus reducing the code's errorfloor.


11:0011:30, Paper WIA.160  
Generating Good Finite Length LDPC Codes Based on Lifted Graphs (I) 
Sharon, Eran  TelAviv Univ. Israel 
Litsyn, Simon  Tel Aviv Univ 
Keywords:
Abstract: A method for generating good finite length LowDensity ParityCheck (LDPC) codes based on lifted graphs is described. The codes are constructed using a progressive edge growth technique by taking into account the influence that every introduced edge has on the error floor and waterfall threshold of the code. The generated code can be tailored according to prescribed specification, achieving the desirable error floor versus waterfall threshold tradeoff. For the constructed codes, an analytical upper bound on the expected block error probability of the code over the Binary Erasure Channel (BEC) in the error floor region and an asymptotic Density Evolution (DE) waterfall threshold are obtained.


11:3012:00, Paper WIA.170  
On the Fading Paper Achievable Region of the Fading MIMO Broadcast Channel (I) 
Bennatan, Amir  Tel Aviv Univ 
Burshtein, David  Tel Aviv Univ 
Keywords:
Abstract: We consider transmission over the ergodic fading multiantenna broadcast (MIMOBC) channel with partial channel state information at the transmitter and full information at the receiver. Over the equivalent nonfading channel, capacity has recently been shown to be achievable using transmission schemes that were designed for the “dirty paper” channel. We focus on a similar ``fading paper'' model. The evaluation of the fading paper capacity is difficult to obtain. We confine ourselves to the linearassignment capacity, which we define, and use convex analysis methods to prove that its maximizing distribution is Gaussian. We compare our fadingpaper transmission to an application of dirty paper coding that ignores the partial state information and assumes the channel is fixed at the average fade. We show that a gain is easily achieved by appropriately exploiting the information. We also consider a cooperative upper bound on the sumrate capacity as suggested by Sato. We present a numeric example that indicates that our scheme is capable of realizing much of this upper bound.


WIB 
Porch 
Wireless Networks and Large Deviations 
Invited Session 
Chair: Hanly, Stephen Vaughan  Univ. of Melbourne 
Organizer: Hajek, Bruce  Univ. of Illinois at UrbanaChampaign 
Organizer: Srikant, R  Univ. of Illinois at UrbanaChampaign 

08:3009:00, Paper WIB.110  
Some Blocking Bounds for Autonomous Channel Selection in Dynamic Spectrum Access (I) 
Alanyali, Murat  Boston Univ 
Keywords:
Abstract: We consider a circuitswitched network model in which a channel can be utilized at a node if it is idle in all neighbors of the node. The model arises in cellular telephony and various channel assignment strategies have been studied. Motivated by cognitive radio technologies we revisit autonomous channel selection with local information. It is assumed that call chooses an eligible channel uniformly at random from such channels at the time of arrival, and it is blocked if no eligible channel exists. Upper and lower bounds for the blocking probabilities are determined via an auxiliary network process whose equilibrium distribution admits a convenient product form in tree topologies. By way of another approximate characterization, it is argued that random channel selection incurs vanishing loss of optimality as the number of channels and the traffic load increase in proportion.


09:0009:30, Paper WIB.120  
Order Optimal Delay for Opportunistic Scheduling in MultiUser Wireless Uplinks and Downlinks (I) 
Neely, Michael  Univ. of Southern California 
Keywords:
Abstract: We consider a onehop wireless network with independent time varying channels and N users, such as a multiuser uplink or downlink. We first show that general classes of scheduling algorithms that do not consider queue backlog necessarily incur average delay that grows at least linearly with N. We then construct a dynamic queuelength aware algorithm that stabilizes the system and achieves an average delay that is independent of N. This is the first analytical demonstration that O(1) delay is achievable in such a multiuser wireless setting. The delay bounds are achieved via a technique of queue grouping together with basic Lyapunov stability and statistical multiplexing concepts.


09:3010:00, Paper WIB.130  
On Characterizing the Delay Performance of Wireless Scheduling Algorithms (I) 
Lin, Xiaojun  Purdue Univ 
Keywords:
Abstract: In this paper we study the problem of characterizing the delay performance of wireless scheduling algorithms. In wireless networks operated under these wireless scheduling algorithms, there often exists a tight coupling between the servicerate process, the system backlog process, the arrival process and the channel variations. Although one can use samplepath largedeviation techniques to form an estimate of the delayviolation probability under a given offered load, the formulation leads to a multidimensional calculus of variations problem that is often very difficult to solve. In this paper, we present a new technique for addressing this complexity issue. Using ideas from the Lyapunov function approach in control theory, this technique maps the complex multidimensional calculus of variations problem to a onedimensional calculus of variations problem, and the latter is often much easier to solve. We believe that this technique can potentially be used to study the delayperformance of a large class of wireless scheduling algorithms.


10:3011:00, Paper WIB.150  
Approximation Schemes for Information Acquisition and Exploitation in Multichannel Wireless Networks (I) 
Guha, Sudipto  Univ. of Pennsylvania 
Munagala, Kamesh  Duke Univ 
Sarkar, Saswati  Univ. of Pennsylvania 
Keywords:
Abstract: Nodes in future wireless networks are likely to have access to multiple channels. A node can learn the instantaneous state of a channel only by probing it which in turn consumes both additional energy and time. A node therefore needs to not only optimally select the channel based on available information but also optimally determine the amount of information it should acquire about the instantaneous states of its available channels. The successful exploitation of the available channels is therefore contingent upon designing simple mechanisms for jointly optimizing both information acquisition and exploitation. We provide a joint channel probing and selection scheme that can approximate a utility function that captures both the cost and value of information. The approximation can be made arbitrarily close to the optimal while increasing the computation time of the solution. Specifically, given any positive epsilon, the proposed scheme can be tuned to attain a utility which is at most epsilon less than that of the optimal, and requires a computation time which is polynomial in the number of channels and the degree of this polynomial increases with decrease in epsilon.


11:0011:30, Paper WIB.160  
Large Deviations with Large Coding Buffers (I) 
Bhadra, Sandeep  The Univ. of Texas at Austin 
Shakkottai, Sanjay  The Univ. of Texas at Austin 
Keywords:
Abstract: We consider coding at the source instead of buffering at the pointofingress in a network. We provide a sufficient condition under which the packet loss probability decreases exponentially in a function that is linear in the size of the input buffer, where the function is required to meet a predetermined negative slope. We express the loss effective bandwidth for coding and compare it against that for queueing.


11:3012:00, Paper WIB.170  
Large Deviations of Queues under QoS Scheduling Algorithms (I) 
Stolyar, Alexander  Bell Lab. Lucent Tech 
Keywords:
Abstract: We consider a model where multiple queues are served by a server whose capacity varies randomly and asynchronously with respect to different queues. The problem is to optimally control large deviations of the queues in the following sense: find a scheduling rule maximizing min_i lim_n (1/n) log Pr{a_i Q_i > n}, (1) where Q_i is the length of ith queue in a stationary regime, and a_i>0 are parameters. Thus, we seek to maximize the minimum of the exponential decay rates of the tails of distributions of weighted queue lengths a_i Q_i. We give a characterization of the upper bound on (1) under any scheduling rule, and of the lower bound on (1) under the *exponential* (EXP) rule. For the case of two queues, we prove that the two bounds match, thus proving optimality of EXP rule in this case. The EXP rule is *not* asymptotically invariant with respect to scaling of the queues, which complicates its analysis in large deviations regime. To overcome this, we introduce and prove a refined sample path large deviations principle, or refined Mogulsky theorem, which is of independent interest.


WIC 
Butternut 
Wireless Adhoc 
Regular Session 
Chair: Elia, Petros  Univ. of Southern California 

08:3009:00, Paper WIC.110  
Random Matrix Analysis of Large Relay Networks 
Morgenshtern, Veniamin  ETH Zurich 
Boelcskei, Helmut  ETH Zurich 
Keywords:
Abstract: We analyze fading interference relay networks where M singleantenna sourcedestination terminal pairs communicate concurrently and in the same frequency band through a set of K singleantenna relays using halfduplex twohop relaying. The relays do not have channel state information, perform amplifyandforward (AF) relaying, and the destination terminals can cooperate and perform joint decoding. Our main results are as follows:  We compute the per sourcedestination terminal pair capacity for M,Ktoinfty, with~K/Mtobeta fixed, using tools from random matrix theory.  We show that for betatoinfty, the AF relay network is turned into a pointtopoint multipleinput multipleoutput link and thus extend the result found previously for the finite M, Ktoinfty case in~cite{bolcskei06} to the~M,K,rightarrow,infty case.


09:0009:30, Paper WIC.120  
A Coding Strategy for Wireless Networks with No Channel Information 
Oggier, Frederique  California Inst. of Tech 
Hassibi, Babak  California Inst. of Tech 
Keywords: Wireless Communications, MIMO Systems, Sensor Networks in Communications
Abstract: In this paper, we present a coding strategy for wireless networks, where we assume no channel knowledge. More precisely, the relays operate without knowing the channel that affected their received signal, and the receiver decodes knowing none of the channel paths. The coding scheme is inspired by noncoherent differential spacetime coding, and is shown to yield a diversity linear in the number of relays. It is furthermore available for any number of relay nodes.


09:3010:00, Paper WIC.130  
Explicit, Unified DMG Optimal Construction for the Dynamic DecodeAndForward Cooperative Wireless Network 
Elia, Petros  Univ. of Southern California 
Kumar, P. Vijay  Indian Inst. of Science 
Keywords: Coding Theory, Information Theory, MIMO Systems
Abstract: This work presents the first explicit implementation of the dynamic decodeandforward cooperative diversity protocol, that achieves the optimal diversitymultiplexing gain (DMG) tradeoff for any network size, all delays, all numbers of transmit and receive antennas at the relays, and all families of fading statistics.


10:3011:00, Paper WIC.150  
Throughput and Transmission Capacity of Ad Hoc Networks with Channel State Information 
Weber, Steven  Drexel Univ 
Andrews, Jeffrey  The Univ. of Texas at Austin 
Jindal, Nihar  Univ. of Minnesota 
Keywords: Wireless Communications, Performance Analysis, Information Theory
Abstract: This paper develops a general framework for deriving the spatial throughput and transmission capacity of spatially Poisson distributed ad hoc networks for (i) random (e.g., fading) channels, and (ii) random transmission distances. In both of these scenarios the randomness of the channels and ranges invariably lowers both throughput and transmission capacity assuming that users randomly elect to transmit with some probability (i.e., Aloha). Assuming each node knows the channel state information (CSI, e.g., the channel gain and/or channel distance) to just its intended receiver, we propose a simple distributed thresholdbased scheduling rule and derive the threshold that optimizes throughput. The gains are surprisingly large: a factor of three increase in throughput over Aloha is typical even with no further coordination between the nodes in the network.


11:0011:30, Paper WIC.160  
ThroughputOptimal Configuration of Wireless Networks 
Karnik, Aditya  Univ. of Waterloo 
Iyer, Aravind  Purdue Univ 
Rosenberg, Catherine  Univ. of Waterloo 
Keywords: Wireless Communications, Performance Analysis
Abstract: In this paper, we address the following two questions: (i) given a set of nodes with arbitrary locations, and a set of data flows, what is the maxmin achievable throughput? and (ii) how should the network be configured to achieve the optimum? We consider these questions from a networking standpoint, and pose them as an optimization problem to determine jointly optimal flow routes, link activation schedules and physical layer parameters. We obtain some interesting insights into the interplay of the achievable throughput, routing and transmit power and modulation schemes. Determining the achievable throughput is computationally hard in general, however, using a smart technique we obtain numerical results for different scenarios of interest. We believe that our optimization based framework can also be used as a tool, for planning and capacity provisioning of wireless networks.


11:3012:00, Paper WIC.170  
On Broadcast Stability Region in Random Access through Network Coding 
Sagduyu, Yalin Evren  Univ. of Maryland 
Ephremides, Anthony  Univ. of Maryland 
Keywords: Network Coding in Communication, Queuing Theory and Analysis, Wireless Communications
Abstract: We specify the stable throughput region for broadcast systems with one or two source nodes transmitting packets to two receivers over independent channels with probabilistic reception. We show that the plain retransmission policy is suboptimal and the stable operation is optimized by coded retransmissions with finite packet delay and low complexity. We introduce a dynamic network coding policy based on the instantaneous queue content and prove the equivalence of the queueing stability region and maximum throughput region for random access of two sources randomly transmitting packets to two receivers over multipacket reception channels. We also discuss the relationship between the maximum achievable and stable throughput regions (for saturated and possibly emptying packet queues) and the general capacity region. Finally, we explore the maximum stable throughput region for unicast traffic of packets addressed to either one of the two receivers and combine the results with broadcast communication.


12:0012:15, Paper WIC.181  
RateDistortion Bounds on LocationBased Routing Protocol Overheads in Mobile Ad Hoc Networks 
Bisnik, Nabhendra  RPI 
Abouzeid, Alhussein  RPI 
Keywords: Information Theory, Performance Analysis
Abstract: We present an information theoretic analysis of the minimum routing overhead incurred for reliable routing of packets using locationbased routing. We formulate the minimum routing overhead problem as a ratedistortion problem and derive a lower bound on the minimum routing overhead incurred. We also characterize the deficit in transport capacity caused by the routing overheads. It is observed that for high mobility and packet arrival rates, the routing overheads may consume the entire capacity of a network.


12:1512:30, Paper WIC.182  
Reliability Bounds for DelayConstrained MultiHop Networks 
Oyman, Ozgur  Intel Corp 
Keywords: Information Theory, Wireless Communications, Sensor Networks in Communications
Abstract: We consider a linear multihop network composed of multistate discretetime memoryless channels over each hop, with orthogonal timesharing across hops under a halfduplex relaying protocol. We analyze the probability of error and associated reliability function cite{Gallager68} over the multihop network; with emphasis on random coding and sphere packing bounds, under the assumption of pointtopoint coding over each hop. In particular, we define the system reliability function for the multihop network and derive lower and upper bounds on this function to specify the reliabilityoptimal operating conditions of the network under an endtoend constraint on the total number of channel uses. Moreover, we apply the reliability analysis to bound the expected endtoend latency of multihop communication under the support of an automatic repeat request (ARQ) protocol. Considering an additive white Gaussian noise (AWGN) channel model over each hop, we evaluate and compare these bounds to draw insights on the role of multihopping toward enhancing the endtoend ratereliabilitydelay tradeoff.


WID 
Pine 
Communications, Control, and Optimization 
Regular Session 
Chair: Mehta, Prashant G.  Univ. of Illinois 

08:3009:00, Paper WID.110  
On Stabilizing the Double Integrator with Switched Gain Feedback and Binary Sensing 
Tarraf, Danielle C.  MIT 
Megretski, Alexandre  MIT 
Dahleh, Munther  MIT 
Keywords: Hybrid Systems, Nonlinear Control, Reliable and Robust Control
Abstract: This paper considers the simple benchmark problem of stabilizing a double integrator by switching between two static gain feedbacks, assuming that the only information available to the switching controller is the sign of the position measurement. A systematic, semiautomated, constructive controller design procedure is presented. The sampled plant is first approximated by a finite state machine, and a bound on the quality of approximation is established. A control law is then designed to robustly stabilize the nominal finite state machine model in the presence of admissible uncertainty. The resulting controller thus consists of a finite state machine observer and a corresponding full state feedback control law.


09:0009:30, Paper WID.120  
Receding Horizon Networked Control 
Gupta, Vijay  California Inst. of Tech 
Sinopoli, Bruno  Stanford Univ. & UC Berkeley 
Adlakha, Sachin  Stanford Univ 
Goldsmith, Andrea  Stanford Univ 
Murray, Richard  California Inst. of Tech 
Keywords: Networked Control Systems, Stochastic Systems and Control, Decentralized and Distributed Control
Abstract: This paper deals with the design of control systems over lossy networks. A network is assumed to exist between the sensor and the controller and between the latter and the actuator. Packets are dropped according to a Bernoulli independent process, with gamma and mu being the probabilities of losing an observation packet and a control packet respectively, at time any instant t. A receding horizon control scheme is proposed for the Linear Quadratic Control (LQG) problem. At each instant N future control inputs are sent in addition to the current one. Under this scheme the separation of estimation and control is shown and stability conditions, dependent on loss probabilities, are provided. Simulations show how the overall performance, in terms of lower cost, increases with the length of the horizon.


09:3010:00, Paper WID.130  
On the Stability of Hybrid Systems with Random Switching 
Zhu, Chao  Wayne State Univ 
Yin, George  Wayne State Univ 
Song, Qingshuo  Univ. of Southern California 
Keywords: Hybrid Systems, Nonlinear Control, Stochastic Systems and Control
Abstract: This work is concerned with stability of hybrid systems. The hybrid systems that we are interested in are randomswitching systems of differential equations. This work presents the formulation of regimeswitching systems, recalls the notion of stability, and provides sufficient conditions in terms of Liapunov function. Then the main results including easily verifiable conditions for stability and instability of systems arising in approximation are established. Using a logarithm transformation, necessary and sufficient conditions are derived for systems that are linear in the continuous state component. Several examples are given for demonstrations. It should be noted that somewhat different behavior than the wellknown HartmanGrodman theorem is observed.


10:3011:00, Paper WID.150  
Duality in Stability Theory: Lyapunov Function and Lyapunov Measure 
Vaidya, Umesh  Iowa State Univ 
Keywords: Nonlinear Control, Stochastic Systems and Control
Abstract: In this paper, we introduce Lyapunov measure to verify weak (a.e.) notions of stability for an invariant set of a nonlinear dynamical system. Using certain linear operators from Ergodic theory, we derive Lyapunov results to deduce a.e. stability. In order to highlight the linearity of our approach, we also provide explicit formulas for obtaining Lyapunov function and Lyapunov measure in terms of the resolvent of the two linear operators.


11:0011:30, Paper WID.160  
A Game Theoretic Model for Network Upgrade Decisions 
Musacchio, John  Univ. of California, Santa Cruz 
Walrand, Jean  Univ. of California, Berkeley 
Wu, Shuang  Univ. of California, Santa Cruz 
Keywords: Pricing and Congestion Control, Dynamic Games and Decision Theory
Abstract: We develop a game theoretic model for studying when interconnected Internet Service Providers (ISP)s will decide to upgrade their networks. We are in particular interested in network upgrades to better accommodate realtime applications like voice over IP, but our game model is applicable to other types of upgrade. Achieving the full benefit from network upgrades requires that enough ISPs upgrade so that the users' traffic encounters only upgraded ISPs as it traverses the Internet. This situation gives rise to two important effects. One effect is that providers are reluctant to be first to invest in an upgrade when the full benefit of the upgrade cannot be achieved until their peers do the same. The second effect is that when a provider upgrades, the quality of the Internet as a whole increases, increasing demand, and thereby increasing revenue for all ISPs  including those who have not invested in the upgrade. This ``freerider'' effect gives providers a temptation to not upgrade and instead enjoy the benefits of their peers upgrading. Our game model takes into account both effects, and finds sufficient conditions for it to be a Nash equilibrium the ISPs involved in the game to decide to upgrade. There are a large number of other equilibria for this game, so we also find stronger conditions under which the Nash equilibrium in which all providers upgrade is the unique Nash equilibrium. Another important feature of network upgrade costs is that they are declining as technol


11:3012:00, Paper WID.170  
LMS versus Wiener Filter for a Decision Feedback Equalizer 
Kavitha, Veeraruna  Indian Inst. of Science 
Sharma, Vinod  Indian Inst. of Science 
Keywords: Statistical Signal Processing, Detection and Estimation
Abstract: In this paper we study an LMSDFE. We use the ODE framework to show that the LMSDFE attractors are close to the true DFE Wiener filter (designed considering the decision errors) at high SNR. Therefore, via LMS one can obtain a computationally efficient way to obtain the true DFE Wiener filter under high SNR. We also provide examples to show that the DFE filter so obtained can significantly outperform the usual DFE Wiener filter (designed assuming perfect decisions) at all practical SNRs. In fact, the performance improvement is very significant even at high SNRs (up to 50%), where the popular Wiener filter designed with perfect decisions, is believed to be closer to the optimal one.


WIE 
Lower Level 
Learning 
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 WIE.110  
How to Filter an "Individual Sequence with Feedback" (I) 
Weissman, Tsachy  Stanford 
Keywords: Dynamic Games and Decision Theory, Universal Algorithms and Machine Learning, Detection and Estimation
Abstract: We consider causally estimating (filtering) the components of a noisecorrupted sequence relative to a reference class of filters. The noiseless sequence to be filtered is an ``individual sequence with feedback'', meaning it may evolve arbitrarily (in a way undisclosed to the filter), based on past emph{noisy} sequence components. We show that this setting is more challenging than that of an individual noiseless sequence in the sense that emph{any} deterministic filter, even one guaranteed to do well on every noiseless individual sequence, fails under some individual sequence with feedback. On the other hand, we constructively establish the existence of a emph{randomized} filter which successfully competes with an arbitrary given finite reference class of filters, under emph{every} individual sequence with feedback. Thus, unlike in the semistochastic setting, randomization is crucial if the individual sequence has access to feedback. Our noise model allows for channels whose noisy output depends on the l past channel outputs (in addition to the noiseless channel input symbol). Memoryless channels are obtained as a special case of our model by taking l=0. In this case, our scheme coincides with one that was recently shown to compete with an arbitrary reference class when the underlying noiseless sequence is an individual sequence. Hence, our results show that the latter scheme is universal also for individual sequences with feedback.


09:0009:30, Paper WIE.120  
Sharp Thresholds for Sparsity Recovery in the HighDimensional and Noisy Setting (I) 
Wainwright, Martin  UC Berkeley 
Keywords: Universal Algorithms and Machine Learning, Information Theory, Sensor Networks
Abstract: The problem of consistently estimating the sparsity pattern of a vector beta^* in real^p based on observations contaminated by noise arises in various contexts, including subset selection in regression, structure estimation in graphical models, sparse approximation, and signal denoising. We analyze the behavior of ell_1constrained quadratic programming (QP), also referred to as the Lasso, for recovering the sparsity pattern. Our main result is to establish a sharp relation between the problem dimension p, the number s of nonzero elements in beta^*, and the number of observations n that are required for reliable recovery.


09:3010:00, Paper WIE.130  
Upper and Lower Error Bounds for Active Learning (I) 
Castro, Rui  Univ. of Wisconsin, Madison 
Nowak, Robert  Univ. of Wisconsin, Madison 
Keywords: Universal Algorithms and Machine Learning, Detection and Estimation, Statistical Signal Processing
Abstract: This paper analyzes the potential advantages and theoretical challenges of "active learning" algorithms. Active learning involves sequential, adaptive sampling procedures that use information gleaned from previous samples in order to focus the sampling and accelerate the learning process relative to ``passive learning'' algorithms, which are based on nonadaptive (usually random) samples. There are a number of empirical and theoretical results suggesting that in certain situations active learning can be significantly more effective than passive learning. However, the fact that active learning algorithms are feedback systems makes their theoretical analysis very challenging. It is known that active learning can provably improve on passive learning if the error or noise rate of the sampling process is bounded. However, if the noise rate is unbounded, perhaps the situation most common in practice, then no previously existing theory demonstrates whether or not active learning offers an advantage. To study this issue, we investigate the basic problem of learning a threshold function from noisy observations. We present an algorithm that provably improves on passive learning, even when the noise is unbounded. Moreover, we derive a minimax lower bound for this learning problem, demonstrating that our proposed active learning algorithm converges at the nearoptimal rate.


WIF 
Brick 
MIMO 
Regular Session 
Chair: Madhow, Upamanyu  Univ. of California, Santa Barbara 

08:3009:00, Paper WIF.110  
Millimeter Wave MIMO: Wireless Links at Optical Speeds (I) 
Torkildson, Eric  Univ. of California, Santa Barbara 
Ananthasubramaniam, Bharath  Univ. of California, Santa Barbara 
Madhow, Upamanyu  Univ. of California, Santa Barbara 
Rodwell, Mark  Univ. of California, Santa Barbara 
Keywords: MIMO Systems, Wireless Communications
Abstract: We propose a new architecture for bridging the existing gap in speeds between wireless and optical links. The Millimeter Wave MIMO system employs “millimeter (mm) wave” spectrum in the Eband (7095 GHz), which has been made available by the Federal Communications Commission on a semiunlicensed basis for outdoor pointtopoint communication. The small wavelengths enable highly directive beams providing link budgets sufficient to communicate even in poor weather conditions over ranges of the order of kilometers, while requiring radio frequency (RF) frontends that can be realized in lowcost silicon processes. Furthermore, because of the small wavelengths, spatial multiplexing gains can be obtained even in Line of Sight (LOS) environments with only a moderate separation of transmitters. The proposed mmwave MultipleInput MultipleOutput system exploits these characteristics to provide LOS links of speeds of up to 40 Gbps (e.g., by supporting eight 5 Gbps links in parallel between two nodes). This paper provides an initial exposition of the key concepts, provides some rough calculations of attainable performance, and hints at the issues that must be addressed before this concept can become a reality.


09:0009:30, Paper WIF.120  
Impact of Spatial Correlation on Statistical Precoding in MIMO Channels with Linear Receivers 
Raghavan, Vasanthan  Univ. OF WISCONSIN 
Sayeed, Akbar  Univ. of WisconsinMadison 
Keywords: MIMO Systems, Wireless Communications, Information Theory
Abstract: Multiple antennas at the transmitter and the receiver can be used to achieve diversity or multiplexing gain or a combination of the two gains. Most works to date study schemes that achieve either of the two extremes in this diversitymultiplexing tradeoff. In this work, we assume communication with a fixed number (M) of independent datastreams and a linear receiver architecture. Motivated by a limited feedback paradigm, we focus on precoding with a semiunitary matrix. We first provide evidence that the optimal semiunitary precoder consists of the M dominant right singular vectors of the channel. Then, we study the average relative enhancement in error probability and relative loss in mutual information with statistical precoding and show that these quantities vanish in the receive antenna asymptotics. For a given transmit and receive antenna dimension, N_t and N_r, we also show that these quantities are minimized if the eigenvalues of the transmit covariance matrix can be partitioned into two components: a dominant component of M eigenvalues that is wellconditioned and a subdominant component of N_t  M eigenvalues that is illconditioned away from the dominant component.


09:3010:00, Paper WIF.130  
ScalingLaw Optimal Training and Scheduling in the SIMO Uplink 
Murugesan, Sugumar  Ohio State Univ 
UysalBiyikoglu, Elif  Ohio State Univ 
Schniter, Philip  Ohio State Univ 
Keywords: MIMO Systems, Information Theory, Wireless Communications
Abstract: In fading MIMO channels, there is a tradeoff between the time (or energy) spent gathering CSI and the remaining time in which to transmit data before the channel loses coherence. The tradeoff is more pronounced in multiuser systems as the number of users hence the number of channel vectors to be estimated increases, and is inherently coupled with multiuser scheduling. We consider a multiple access block fading channel with coherence time T, n independent users, each with one transmit antenna and the same average power constraint, and a base station with M receive antennas and no a priori CSI. We construct a trainingbased communication scheme and jointly optimize the training and user selection: we find the optimal number of users to be trained and the optimal number to be scheduled for transmission out of those trained, in order to maximize sum rate. The optimal duration of training, in symbol times, is shown to be equal to the number of users trained. We also show the necessary and sufficient condition for training sequences to satisfy. This optimized trainingbased scheme achieves the same scaling law with increasing SNR as the noncoherent capacity of a single user nxM MIMO channel. We show this is also the scaling law of the sum capacity of the associated noncoherent SIMO uplink, hence our scheme is scalinglaw optimal. Finally, the asymptotic behavior of sum rate under increasing n, M or T is explored.


10:3011:00, Paper WIF.150  
STORM : Optimal Constellations for Noncoherent MIMO Communications at Low SNR under PAPR Constraints 
Srinivasan, Shivratna  Univ. of Colorado, Boulder 
Varanasi, Mahesh  Univ. of Colorado, Boulder 
Keywords: MIMO Systems
Abstract: Reliable communication over the discrete input and continuous output noncoherent MIMO Rayleigh fading channel is considered when the SNR per degree of freedom is low. The input constellations are required to satisfy peak and average power constraints. When the peaktoaverage power is constrained and in the low SNR regime, the mutual information upto second order in SNR is maximized jointly over the input signal matrices and their respective probabilities. Even though the problem considered is a finite dimensional nonconvex optimization, it admits an elegant solution in closed form. The constellation obtained is referred to as Space Time Orthogonal Rank one Modulation (STORM), and it provides several new insights into noncoherent MIMO comunications in the low SNR regime. In contrast to most existing schemes for the noncoherent MIMO channel at low SNR, STORM is a practical constellation due to its discrete structure with a finite number of points and because it requires a moderate PAPR in general. Moreover, STORM is nearoptimal with respect to the maximum mutual information with unconstrained cardinality, even with a moderate peaktoaverage power ratio (PAPR). Numerical results show that STORM is also close to optimal from the important viewpoint of spectral efficiency.


11:0011:30, Paper WIF.160  
Mismatched and Optimum Receivers for the Correlated Rician Fading MIMO Channel 
Taricco, Giorgio  Pol. Di Torino 
Coluccia, Giulio  Pol. Di Torino 
Keywords: MIMO Systems, Coding Theory, Wireless Communications
Abstract: Two receiver structures for the separatelycorrelated Rician fading MIMO channel, based on pilotaided channel estimation, are considered. A mismatched receiver, based on maximumlikelihood estimation of the channel matrix, and using this estimate in the decision metric as if it were exact. An optimum receiver, processing jointly the pilot symbols and the received pilot and data samples by maximum likelihood estimation. An iterative implementation of the optimum receiver is provided, which is suitable to trellis spacetime decoding. Numerical results are given for a 2 x 2 correlated Rician MIMO channel with a simple trellis spacetime code. Channel parameter estimation, affecting the optimum receiver and not the mismatched one and implemented by a simple algorithm, is shown not to degrade the error performance. Finally, the complexity increase of the optimum receiver is investigated.


11:3012:00, Paper WIF.170  
User Selection for MIMO Broadcast Channel with Sequential WaterFilling 
Wang, Jianqi  Purdue Univ 
Love, David J.  Purdue Univ 
Zoltowski, Michael D.  Purdue Univ 
Keywords: Multiuser Detection and Estimation, MIMO Systems, Wireless Communications
Abstract: In this paper, we propose a new suboptimal user selection method for MIMO broadcast channel based on the sequential waterfilling (SWF) algorithm. This algorithm is designed to maximize the sum rate of the zeroforcing beamforming (ZFBF) strategy. The reduction of complexity is achieved in a number of ways. First, an iterative procedure to calculate the PenroseMoore inverse of the channel matrix, based on LQ decomposition, is introduced. This procedure converts the matrix inversion operation to one vectormatrix multiplication. Secondly, the sequential nature of the user selection problem rules out the tryandtest phase for the waterfilling approach. Finally, it is shown that the search space of this algorithm can be further pruned. Simulation demonstrates that this algorithm achieves a sum rate that is lose to the maximal sum rate achievable by ZFBF, with a complexity that is comparable to the best algorithms known so far.


12:0012:30, Paper WIF.180  
Systematic Expansion of SpaceTime Block Multiple TCM Codes for Two Transmit Antennas 
Lee, Heechoon  Univ. of California Los Angeles 
Fitz, Michael P.  Univ. of California Los Angeles 
Keywords: MIMO Systems, Coding Techniques and Applications, Wireless Communications
Abstract: This paper proposes improved spacetime block multiple TCM (STBMTCM) codes via a systematic expansion of spacetime block code (STBC) for two transmit antennas. Starting from orthogonal STBC, the STBC set is expanded as superorthogonal STBC, and further expanded up to spatial multiplexing. Exploiting the expanded set of STBCs as the number of states increase, improved full diversity STBMTCM codes can be designed by increasing the coding gain and Euclidean distance of pairwise error.


WIG 
Visitor Center 
Broadcast 
Regular Session 
Chair: Poon, Ada  Univ. of Illinois at UrbanaChampaign 

08:3009:00, Paper WIG.110  
Scheduling of MultiAntenna Broadcast Systems with Heterogeneous Users 
Jagannathan, Krishna Prasanna  MIT 
Borst, Sem  Bell Labs, Lucent Tech 
Whiting, Philip  Bell Labs, Lucent Tech 
Modiano, Eytan  MIT 
Keywords: MIMO Systems, Wireless Communications
Abstract: We consider a two transmit antenna broadcast system with heterogeneous users, and tackle the problem of maximizing a weighted sum rate. We establish a novel upper bound for the weighted sum capacity, which we then use to show that the maximum expected weighted sum rate can be asymptotically achieved by transmitting to a suitably selected subset of at most 2C users, where C denotes the number of distinct user classes. Numerical experiments indicate that the asymptotic results are remarkably accurate and that the proposed schemes operate close to absolute performance bounds, even for a moderate number of users.


09:0009:30, Paper WIG.120  
Broadcasting a Message Over Erasure Channels with Cooperating Receivers 
Khalili, Ramin  CNRSSupelecParis XI 
Lasaulce, Samson  CNRSSupelecParis XI 
Duhamel, Pierre  CNRSSupelecParis XI 
Keywords: Network Coding, Information Theory, Wireless Communications
Abstract: In this paper we consider the orthogonal cooperative broadcast channel with a common message. The downlink and cooperation channels are modelled by erasure channels and assumed to be orthogonal. We derive an achievable rate for this channel by using a combination of decodeandforward and estimateandforward and considering both symmetric and asymmetric cooperation. These schemes are based on a twostep cooperation. It is shown under which conditions the proposed achievable rate coincides with the considered upper bound that is in fact the interpretation of the traditional cutset bound in the context of broadcast cooperative erasure channels. Moreover we propose a timesharingbased iterative coding scheme with more than two cooperation steps.


09:3010:00, Paper WIG.130  
Discrete Memoryless Interference and Broadcast Channels with Confidential Messages 
Liu, Ruoheng  Rutgers Univ 
Maric, Ivana  Stanford Univ 
Spasojevic, Predrag  Rutgers Univ 
Yates, Roy  Rutgers Univ 
Keywords: Information Theory, Wireless Communications
Abstract: Discrete memoryless interference and broadcast channels in which independent confidential messages are sent to two receivers are considered. Confidential messages are transmitted to each receiver with perfect secrecy, as measured by the equivocation at the other receiver. In this paper, we derive inner and outer bounds for the achievable rate regions for these two communication systems.


10:3011:00, Paper WIG.150  
Transmitter Design with Interference PreSubtraction for Uncertain Broadcast Channels 
Botros Shenouda, Michael  McMaster Univ 
Davidson, Timothy N  McMaster Univ 
Keywords: MIMO Systems, Multiuser Detection and Estimation
Abstract: We consider the design of TomlinsonHarashima (TH) precoders for broadcast channels in the presence of channel uncertainty. For systems in which uplinkdownlink reciprocity is used to obtain a channel estimate at the transmitter, we present a robust design based on a statistical model for the channel uncertainty. We provide a convex formulation of the design problem subject to two types of power constraints: a set of constraints on the power transmitted from each antenna and a total power constraint. For the case of the total power constraint, we obtain a closedform solution for the robust TH precoder that has essentially the same computational cost as the corresponding designs that assume perfect channel knowledge. For systems in which the receivers feed back quantized channel state information to the transmitter, we present a robust design based on a bounded model for the channel uncertainty. We provide a convex formulation for the TH precoder that maximizes the performance under the worstcase channel uncertainty subject to both types of power constraints. An interesting feature of the proposed robust TH precoders is that they do not necessarily use all the allowable power. Simulation studies verify our analytical results and show that the robust TH precoders can significantly reduce the high sensitivity of broadcast transmissions to errors in the channel state information.


11:0011:30, Paper WIG.160  
On the DiversityMultiplexing Region of Broadcast Channels with Partial Channel State Information 
Stojanovic, Ivana  Boston Univ 
Sharif, Masoud  Boston Univ 
Ishwar, Prakash  Boston Univ 
Keywords: Wireless Communications, Information Theory
Abstract: In this paper, we study the reliability (error probability) and rate tradeoffs among the receivers in singleantenna block Rayleighfading Gaussian broadcast channels. The rate and reliability tradeoffs are quantified through the notions of average multiplexing and diversity gains in the high signal to noise ratio (SNR) regime. Diversity and multiplexing gains that can be simultaneously achieved and the associated tradeoffs are wellunderstood in multiantenna (MIMO) pointtopoint systems. However, broadcast channels are different from pointtopoint links in two important aspects (i) the availability of additional degrees of freedom in terms of flexible diversity tradeoffs among different users for the same set of multiplexing rates, and (ii) the opportunity to exploit the inherent multiuser diversity of the channel to improve the reliability. We study the diversitymultiplexing {it region} defined as the set of 2K tuples of diversity and average multiplexing gains corresponding to all K receivers that are simultaneously achievable. We show that the diversitymultiplexing region can be significantly enlarged compared to the case where the transmitter has no channel state information (CSI) by exploiting only partial CSI in the form of the ordering of channel fading gains of users at the transmitter. This is done by proposing a timedivision opportunistic scheduling scheme that can adjust to and support the average rate requirements of all receivers while exploiting


11:3011:45, Paper WIG.171  
Achievable Rates for the Fading MIMO Broadcast Channel with Imperfect Channel Estimation 
Piantanida, Pablo  CNRS/LSSSupelec 
Duhamel, Pierre  Lab. Des Signaux Et Systčmes (L2S)Supélec 
Keywords: Wireless Communications, Information Theory
Abstract: In most practical scenarios of multiuser wireless communications, only an estimate of the channel parameters that differs from the true channel is available. In this paper, we examine the effects of imperfect channel estimation at both transmitter and all receivers on the capacity region of the multiuser Fading MIMO Broadcast Channel. We derive an achievable rate region with the assumption of Gaussian inputs and Dirtypaper coding (DPC) scheme. Our results, for uncorrelated Rayleigh fading, provide intuitive insights on the impact of the channel estimate and the channel characteristics (e.g. SNR, fading distribution, training sequence length) on the achievable rates. These are useful for a system designer to assess the amount of training data to achieve a target pair of rates using a DPC scheme with imperfect channel estimation. We provide numerical results for a twousers MIMO Broadcast Channel with maximumlikehood (ML) and minimum mean square error (MMSE) channel estimation. Results illustrate an interesting practical tradeoff between the benefit of an elevated number of transmit antennas and the amount of training, and its impact to the performance of the DPC scheme.


11:4512:00, Paper WIG.172  
Capacity of Fading Broadcast Channels with LimitedRate Feedback 
Agarwal, Rajiv  Stanford Univ 
Cioffi, John  Stanford Univ 
Keywords: Wireless Communications, Information Theory
Abstract: In this paper, we study a fading broadcast channel (BC) with perfect channel state information at the receiver (CSIR) and only a quantized version of it at the transmitter due to limitedrate links for channel feedback at each user. We find an achievable region for the fading BC under this condition using superposition coding and show that it is sumrate optimal. We also derive a closedform expression for finding channel partitioning, which turns out to be the same in form as that for waterfilling of power over time in fading channels. Using the derived closed form expression with temporal waterfilling of power at the transmitter in an iterative manner, we show numerically that a single iteration is adequate to achieve most of the capacity. Thus the complexity of finding the optimal (global maximum) or close to optimal (local maximum) channel partitioning is greatly reduced as compared to using a searchbased kmean clustering algorithm like Lloyd's algorithm that requires multiple iterations.


12:0012:15, Paper WIG.181  
Precoding for Broadcasting with Linear Network Codes (I) 
Zou, Qiyue  Univ. of California, Los Angeles 
Nosratinia, Aria  Univ. of Texas at Dallas 
Sayed, Ali H.  Univ. of California, Los Angeles 
Keywords: Network Coding in Communication, Network Coding, Coding Techniques and Applications
Abstract: A technique based on linear precoding is introduced for broadcasting on linear networks. The precoding allows the different message components of a broadcast message to be separated and decoded at the desired sink nodes, thus providing a systematic design methodology for broadcasting over a given network with a given linear network code. To achieve a good throughput, however, the network code itself must also be chosen judiciously. Motivated by several recent results on random network codes, we propose a combination of precoding and random linear network codes. This approach does not require a centralized coordination for network code design. One of the advantages of this approach is that by simply changing the precoding matrix (together with associated decoding strategies), different broadcast objectives can be achieved without tampering with the network code, therefore one can manage the network operation by controlling the origin and destination nodes of the network and without manipulating the network interior. Together, random network codes and linear precodings provide a simple yet powerful methodology for broadcast over linear networks.


WIIA 
Library 
Topics in Communication Theory 
Invited Session 
Chair: Viswanath, Pramod  Univ. of Illinois 
Organizer: Viswanath, Pramod  Univ. of Illinois 

13:3014:00, Paper WIIA.210  
How Does the Information Capacity of Ad Hoc Networks Scale? (I) 
Ozgur, Ayfer  EPFL, Lausanne 
Leveque, Olivier  Ec. Pol. Federale De Lausanne 
Tse, David  UC Berkeley 
Keywords:
Abstract: n source and destination pairs randomly located in an area want to communicate with each other. Signals transmitted from one user to another at distance r apart is subject to a power attenuation of r^{alpha} as well as a random phase. We identify exactly the scaling laws of the information theoretic capacity of the network. In the case of dense networks, where the area is fixed and the density of nodes increasing, we show that the total capacity of the network scales {em linearly} with n. In the case of extended networks, where the density of nodes is fixed and the area increasing linear with n, we show that the total capacity scales as n^{2alpha/2} for alpha <3 and sqrt{n} for alpha ge 3. Thus, much better scaling than multihop can be achieved in dense networks and in extended networks with low attenuation. The performance gain is achieved by intelligent node cooperation and distributed MIMO communication. The key ingredient is a {em hierarchical} and {em digital} architecture for nodal exchange of information for realizing the cooperation.


14:0014:30, Paper WIIA.220  
On the Reliability of Gaussian Channels with Noisy Feedback (I) 
Kim, YoungHan  UCSD 
Lapidoth, Amos  ETH Zurich 
Weissman, Tsachy  Stanford 
Keywords:
Abstract: We derive bounds on the reliability of the additive white Gaussian noise channel Y = X + Z with output fed back to the transmitter over independent additive white Gaussian noise channel tilde{Y} = Y + tilde{Z}. These bounds appear to be new even for transmission at zero rate. As a corollary, it is shown that linear feedback coding schemes of finitedimensional constellation, such as the celebrated SchalkwijkKailath coding scheme, not only fail to achieve the capacity, but in fact cannot achieve any positive rate. Our approach is applicable to the derivation of upper bounds on the error exponents in various other scenarios involving channels with feedback.


14:3015:00, Paper WIIA.230  
Fractional Power Reuse in Cellular Networks (I) 
Wu, Xinzhou  Qualcomm Flarion Tech 
Das, Arnab  Qualcomm Flarion Tech 
Li, Junyi  Qualcomm Flarion Tech 
Laroia, Rajiv  Qualcomm Flarion Tech 
Keywords:
Abstract: In this paper, we discuss the potential benefit of introducing a fractional power reuse scheme to multicell cellular networks, by assigning different power levels to different carriers in each cell. In the twocell scenario, we show that in the case that the power levels keep constant over time, fractional power reuse schemes lead to a much bigger capacity region as compared to the traditional frequency reuse schemes. This can be further improved by introducing timevariation of the power level assignments, at the cost of higher system complexity. We extend the twocell analysis to a multicell network and propose a novel intercell interference mitigation scheme which we refer to as a breathingcell scheme. Simulation results show that a substantial gain can be obtained by using such a scheme in a loaded cellular network.


15:3016:00, Paper WIIA.250  
IProjection and the Geometry of Error Exponents (I) 
Borade, Shashi  MIT 
Zheng, Lizhong  MIT 
Keywords:
Abstract: We present a geometric approach, using Iprojection, for analyzing error exponents in various information theory problemse.g., hypothesistesting, source coding, and channel coding. By illuminating on the hidden geometrical structure, it also clarifies the distribution of the log likelihood for correct and incorrect codewords. Calculating the error exponent for very noisy channels becomes essentially trivial now. We also prove tightness of Gallager's formula for error exponent of the expurgated ensemble.


16:0016:30, Paper WIIA.260  
Cooperative Encoding with Asymmetric State Information at the Transmitters (I) 
SomekhBaruch, Anelia  Princeton Univ 
Shamai (Shitz), Shlomo  Tech 
Verdu, Sergio  Princeton Univ 
Keywords:
Abstract: We generalize the Gel'fandPinsker model with the setup of a memoryless multipleaccess channel where there is a single message source fed to both encoders. Only one of the encoders knows the state of the channel (noncausally), which is also unknown to the receiver. We find an explicit characterization of the capacity of this singleuser channel. An explicit characterization of the capacity is also provided for the same channel with causal channel state information. Further, we apply the general formula to the Gaussian case with noncausal channel state information, in which capacity is achievable by a generalized writingondirtypaper scheme.


WIIB 
Porch 
Communication, Feedback, and Rate Distortion 
Invited Session 
Chair: Hadjicostis, Christoforos  Univ. of Illinois 
Organizer: Hadjicostis, Christoforos  Univ. of Cyprus 

13:3014:00, Paper WIIB.210  
FiniteRate RealTime Navigation 
Sarma, Sridevi  MIT 
Dahleh, Munther  MIT 
Keywords: Networked Control Systems, Control Applications, Reliable and Robust Control
Abstract: In this paper, we consider a set up in which the plant and controller are local to each other, but are together driven by a remote reference signal that is transmitted through a finiterate noiseless channel. When control must be done over a communication channel, there is a fundamental tradeoff between allowing enough time for reconstruction of signals over the channel and achieving performance in finitetime. Most work in the area of control under communication constraints have addressed infinitehorizon control objectives (eg. stability, disturbance rejection). In this paper, we study a finitehorizon navigation problem. Our task is to navigate the state of the remote system from a nonzero initial condition, which lies in a bounded set, to as close to the origin as possible in finitetime. We compute lower and upper bounds on the worstcase performance as a function of the channel rate, time horizon, and system parameters. We achieve the lower bound with a noncausal coding scheme and show that imposing causality on the coding scheme degrades performance. We illustrate how the bounds behave under various scenarios and show tradeoffs between time and performance accuracy.


14:0014:30, Paper WIIB.220  
The Directed Data Processing Inequality and Its Applications (I) 
Tatikonda, Sekhar  Yale Univ. 

14:3015:00, Paper WIIB.230  
On the Fixed Point Problem in the Abstract Rate Distortion Theory (I) 
Rezaei, Farzad  Univ. of Ottawa 
Charalambous, Charalambos  Univ. of Cyprus 
Ahmed, NasirUddin  Univ. of Ottawa 


15:3016:00, Paper WIIB.250  
Coding for Additive White Noise Channels with Feedback Corrupted by Quantization or Bounded Noise (I) 
Martins, Nuno  Univ. of Maryland 
Weissman, Tsachy  Stanford 
Keywords: Coding Techniques and Applications, Coding Theory, Information Theory
Abstract: We present simple coding strategies, which are variants of the SchalkwijkKailath scheme, for communicating reliably over additive white noise channels in the presence of corrupted feedback. More specifically, we consider a framework comprising an additive white forward channel and a backward link which is used for feedback. We consider two types of corruption mechanisms in the backward link. The first is quantization noise, i.e., the encoder receives the quantized values of the past outputs of the forward channel. The quantization is uniform, memoryless and time invariant (that is, symbolbysymbol scalar quantization), with bounded quantization error. The second corruption mechanism is an arbitrarily distributed additive bounded noise in the backward link. Here we allow symbolbysymbol encoding at the input to the backward channel. We propose simple explicit schemes that guarantee positive information rate, in bits per channel use, with positive error exponent. If the forward channel is additive white Gaussian then our schemes achieve capacity, in the limit of diminishing amplitude of the noise components at the backward link, while guaranteeing that the probability of error converges to zero as a doubly exponential function of the block length.


16:0016:30, Paper WIIB.260  
Gaussian Channels with Feedback: Confluence of the Fundamental Limitations on Communication, Estimation, and Control (I) 
Liu, Jialing  Iowa State Univ. 
Elia, Nicola  Iowa State Univ. 

16:3017:00, Paper WIIB.270  
Beating the Burnashev Bound in Delay with Noisy Feedback (I) 
Draper, Stark  Univ. of Wisconsin at Madison, Mitsubishi Electric Res 
Sahai, Anant  Univ. of California at Berkeley 
Keywords: Information Theory, Coding Techniques and Applications, Queuing Theory and Analysis
Abstract: We show how to use a noisy feedback link to yield highreliability streaming data communications. We demonstrate a strategy that can maintain the best known reliability function (error exponent) in delay, even when the feedback link is noisy. Only the capacity of the feedback channel need be sufficiently large for this result to hold. More detailed characterization of the feedback link, e.g., its error exponent, is not required. We discuss the architectural implications of our result, which are different from those drawn from blockcoding paradigms.


WIIC 
Butternut 
Iterative LDPC 
Regular Session 
Chair: Lun, Desmond S.  Massachusetts Inst. of Tech 

13:3014:00, Paper WIIC.210  
Exact EXIT Functions for Convolutional Codes Over the Binary Erasure Channel 
Shi, Jun  Intel Corp 
ten Brink, Stephan  Wionics Res.  Realtek Group 
Keywords: Coding Theory, Iterative Coding Techniques, Coding Techniques and Applications
Abstract: Extrinsic information transfer (EXIT) curves characterize the iterative decoding process by a single variable, thus facilitating the understanding and design of capacity achieving codes. The EXIT curves are often obtained empirically through Monte Carlo simulation. On the Binary Erasure Channel (BEC), they can be analytically derived for certain codes. In this case, they are called EXIT functions. We present an algorithm to compute these functions for convolutional codes over the BEC. With the closedform expressions, concatenation of multiple accumulators is studied and shown to be an efficient method to shape the EXIT curves. In addition, higher order accumulators are used to trade off convergence threshold versus error floor behavior.


14:0014:30, Paper WIIC.220  
Raptor Codes for Hybrid ARQ 
Soljanin, Emina  Bell Labs 
Varnica, Nedeljko  Marvell Semiconductor, Inc 
Whiting, Philip  Bell Labs 
Keywords: Coding Techniques and Applications, Coding Theory, Iterative Coding Techniques
Abstract: An incremental redundancy hybrid ARQ scheme (IRHARQ) scheme based on recently introduced Raptor codes is proposed and analysed. A number of important issues such as rate and power control, and error rate performance after each transmission on time varying binary input syummetric channels are addressed by analysing the performance of Raptor codes on parallel channels. A set of rules for incrementing redundancy and setting the signal power at each transmission in order to maximize the throughput are derived. The theoretical results obtained for random code ensembles are tested on several practical code examples by simulation. Both theoretical and simulation results show that Raptor codes are suitable for HARQ schemes.


14:3015:00, Paper WIIC.230  
InformationReduced Carrier Synchronization of BPSK and QPSK Using Soft Decision Feedback 
Simon, Marvin  Jet Propulsion Lab 
Valles, Esteban Luis  Univ. of California, Los Angeles 
Jones, Christopher  Jet Propulsion Lab 
Wesel, Richard  Univ. of California, Los Angeles 
Villasenor, John  Univ. of California, Los Angeles 
Keywords: Iterative Coding Techniques, Wireless Communications, Coding Techniques and Applications
Abstract: This paper addresses the carrierphase estimation problem under low SNR conditions as are typical of turbo and LDPCcoded applications. In [1],[2] closedloop carrier synchronization schemes for errorcorrection coded BPSK and QPSK modulation were proposed that were based on feeding back hard data decisions at the input of the loop, the purpose being to remove the modulation prior to attempting to track the carrier phase as opposed to the more conventional decisionfeedback schemes that incorporate such feedback inside the loop. In this paper, we consider an alternative approach wherein the soft information from the iterative decoder of turbo or LDPC codes is instead used as the feedback.


15:3015:45, Paper WIIC.251  
LDPC Codes Over Ergodic and NonErgodic Relay Channels 
Hu, Jun  Arizona State Univ 
Duman, Tolga  Arizona State Univ 
Keywords: Coding Techniques and Applications, Iterative Coding Techniques, Wireless Communications
Abstract: In this work, we exploit the capacity approaching capability of low density parity check (LDPC) codes over wireless relay channels. We consider the classical fullduplex relay channel model under both ergodic and nonergodic scenarios, and propose two practical relaying schemes. By comparing with the theoretical information rate bounds, we show that the LDPC coded relay systems can approach the ergodic/outage information rates (i.e., constrained channel capacities) very closely. Specifically, we show that they can even outperform the existing turbo coded relay systems under appropriate code design. In addition, based on the measure of average mutual information, we analyze the convergence behavior of the proposed schemes which also demonstrates their great potential to perform near capacity over both ergodic and nonergodic wireless relay channels.


15:4516:00, Paper WIIC.252  
On the Performance of Distributed LT Codes 
Puducheri, Srinath  Univ. of Notre Dame 
Kliewer, Joerg  Univ. of Notre Dame 
Fuja, Thomas E.  Univ. of Notre Dame 
Keywords: Coding Techniques and Applications, Network Coding in Communication, Coding Theory
Abstract: In this paper we extend our previous results on distributed LT codes and focus on the frame erasure rate performance of the corresponding block codes with fixed code rate. Specifically, we address Modified LT (MLT) codes which resemble LT codes in both structure and performance. First, an MLT code onstruction scheme for four sources communicating with a single sink via a common relay is presented. Then, for the fixed code rate case and erasure channels at both sourcerelay and relaysink links, simulation results are given for the frame erasure rate versus the corresponding erasure probabilities. We observe that MLT codes significantly outperform a scheme where an LT block code for every source is separately transmitted over the relaysink erasure channel. This is due to an increased codeword length for the MLT codebased schemes.


16:0016:15, Paper WIIC.261  
LDPC Coding for VariableRank MIMO Channels 
Bagley, Zachary  Univ. of Utah 
Schlegel, Christian  Univ. of Alberta 

16:1516:30, Paper WIIC.262  
Coded Random CDMA with Partitioned Spreading 
Truhachev, Dmitri  Univ. of Alberta 
Schlegel, Christian  Univ. of Alberta 
Krzymien, Lukasz  Univ. of Alberta 
Keywords: Multiuser Detection and Estimation
Abstract: A Code Division Multiple Access (CDMA) system is considered, where a number of concurrent users, distinguished by random spreading waveforms, access the common additive white Gaussian noise (AWGN) channel. All users employ a regular lowdensity paritycheck (LDPC) error control code (ECC). Additionally, a method, called Partitioned Spreading (PS) is used. Each user's spreading waveform is divided into M partitions which are interleaved and spread in time. Asymptotic performance of the proposed system is studied for two different decoding schedules. In the first schedule, called twostage schedule, iterative multiple access (MA) detection and LDPC decoding are executed separately. The second schedule, named full decoding, allows to exchange information between MA and LDPC sides. Supportable system loads are derived as functions of the users' signaltonoise ratio (SNR). It is shown that significantly higher system loads can be achieved compared to the traditional LDPC coded random CDMA.


16:3016:45, Paper WIIC.271  
Improved OptimumDegree Randomized LDPC Codes of Moderate Length by Welding 
Doenmez, Andac  Univ. of ErlangenNuremberg 
Hehn, Thorsten  Univ. of ErlangenNuremberg 
Laendner, Stefan  Univ. of Colorado at Boulder 
Huber, Johannes B.  Univ. of ErlangenNuremberg 
Keywords: Coding Techniques and Applications, Iterative Coding Techniques, Coding Theory
Abstract: We introduce a new method for constructing randomized lowdensity paritycheck (LDPC) codes of moderate length, denoted Welding. The progressive edge growth (PEG) algorithm, a powerful method for constructing short and medium length codes, designs LDPC codes from optimumdegree distributions. The Welding algorithm uses these constructed codes as basis codes to create a longer code by switching edges in the code's Tanner graph randomly so that the capability of PEG is combined with the advantages of random graph codes. The Welding algorithm yields about 0.2 {mathrm{dB}} performance improvement for the AWGN channel over the other long codeword design mechanisms Lifting and PEG.


16:4517:00, Paper WIIC.272  
Methods for Efficient Network Coding 
Maymounkov, Petar  MIT 
Harvey, Nicholas  MIT 
Lun, Desmond S.  Massachusetts Inst. of Tech 
Keywords: Network Coding, Coding Techniques and Applications, Coding Theory
Abstract: Random linear network coding is a capacityachieving communication scheme for single sessions over lossy wireline or wireless packet networks. Thus, from the point of view of efficiently utilizing transmissions, random linear network coding is an attractive strategy. However, it is not presently attractive from the point of view of efficiently utilizing computational resources. A natural code design question arises: can we design a network code that preserves the communication efficiency of a random linear code and achieves better computational efficiency? In this paper, we give an affirmative answer to this question. The code that we present as our answer achieves significantly better computational efficiency and is based primarily on techniques that are now quite standard in the literature on erasure codes. We define and use the language of "adversarial schedules" to compare the performance of our coding scheme against other schemes with respect to a broad class of network environments in a concise manner.


WIID 
Pine 
Coding Theory II 
Invited Session 
Chair: Ashikhmin, Alexei  Bell Lab. Tech 
Organizer: Ashikhmin, Alexei  Bell Lab. Tech 
Organizer: Koetter, Ralf  Univ. of Illinois 

13:3014:00, Paper WIID.210  
Explicit Constructions for Compressed Sensing Problems (I) 
Indyk, Piotr  MIT 

14:0014:30, Paper WIID.220  
Enumerating RNA Motifs: A CodingTheoretic Approach (I) 
Milenkovic, Olgica  Univ. of Colorado at Boulder 
Keywords:
Abstract: We consider the problem of enumerating RNA and DNA secondary structures that obey a set of structural constraints arising due to the biochemical properties of the sugarphosphate backbone of the strands. The enumeration problem is cast into a framework involving contextfree attribute grammars, where the grammars are used to obtain a closedform expression for the qgenerating functions of the constrained objects via the DelestF´edou method. This approach can be viewed as an extension of the paradigm of constrained coding, which was so far used to operate on regular, rather than contextfree languages.


14:3015:00, Paper WIID.230  
Performance Analysis of Algebraic SoftDecision Decoding of ReedSolomon Codes (I) 
Duggan, Andrew  Univ. of Maryland, Coll. Park 
Barg, Alexander  Univ. of Maryland, Coll. Park 
Keywords:
Abstract: We investigate the decoding region for Algebraic Soft Decision Decoding (ASD) of ReedSolomon codes in a discrete, memoryless, additivenoise channel. An expression is derived for the error correction radius within which the softdecision decoder produces a list that contains the transmitted codeword. The error radius for ASD is shown to be larger than that of GuruswamiSudan (GS) harddecision decoding for a subset of lowrate codes. These results are also extended to multivariable interpolation in the sense of Parvaresh and Vardy. We also use the technique developed for the analysis of the error radius to derive and analyze the error exponent of the ASD algorithm.


15:3016:00, Paper WIID.250  
Quantum Convolutional Codes: Encoders and Structural Properties (I) 
Grassl, Markus  Univ. Karlsruhe (TH) 
Rötteler, Martin  NEC Lab. America, Inc 
Keywords:
Abstract: Quantum convolutional codes can be used to protect streams of quantum bits against errors when sending them along a quantum channel. We review the underlying error model, conditions for quantum convolutional codes, and present a product code construction that yields families of quantum convolutional codes. Concerning the structure of encoding circuits for general quantum convolutional codes, we review the notion of catastrophic errors and show that each quantum convolutional code has encoders which are noncatastrophic, i.e., which have good error propagation properties. We present an algorithm to compute a quantum circuit which can be used to perform noncatastrophic encoding and inverse encoding in constant depth and give several examples for illustration.


16:0016:30, Paper WIID.260  
Quantum Error Correcting Subsystem Codes and FaultTolerant Quantum Computing (I) 
Bacon, Dave  Univ. of Washington 
Casaccino, Andrea  Univ. of Siena 
Keywords:
Abstract: The essential insight of quantum error correction was that quantum information can be protected by suitably encoding this quantum information across multiple independently erred quantum systems. Recently it was realized that, since the most general method for encoding quantum information is to encode it into a subsystem, there exists a novel form of quantum error correction beyond the traditional quantum error correcting subspace codes. These new quantum error correcting subsystem codes differ from subspace codes in that their quantum correcting routines can be considerably simpler than related subspace codes. Here we present a class of quantum error correcting subsystem codes constructed from two classical linear codes. These codes are the subsystem versions of the quantum error correcting subspace codes which are generalizations of Shor's original quantum error correcting subspace codes. For every Shortype code, the codes we present give a considerable savings in the number of stabilizer measurements needed in their error recovery routines.


16:3017:00, Paper WIID.270  
Subsystem Codes (I) 
Aly, Salah A  Texas A&M Univ 
Klappenecker, Andreas  Texas A&M Univ 
Sarvepalli, Pradeep Kiran  Texas A&M Univ 
Keywords:
Abstract: We investigate various aspects of operator quantum errorcorrecting codes or, as we prefer to call them, subsystem codes. We give various methods to derive subsystem codes from classical codes. We give a proof for the existence of subsystem codes using a counting argument similar to the quantum GilbertVarshamov bound. We derive linear programming bounds and other upper bounds. We answer a question by Poulin whether or not there exist [[n,n2d+2,r>0,d]] subsystem codes. Finally, we compare stabilizer and subsystem codes with respect to the required number of syndrome qudits.


WIIE 
Lower Level 
Information Theory 
Regular Session 
Chair: Coleman, Todd  Univ. of Illinois at UrbanaChampaign 

13:3014:00, Paper WIIE.210  
Computation Complexity and Information Theoretic Depth of Decision Trees 
Sohangir, Sina  Stanford Univ 
Linscott, Ivan  Stanford Univ 
Keywords: Information Theory, Source Coding and Compression
Abstract: Measuring the intrinsic hardness or complexity of a computation problem has been of interest for many years. Many intuitive relationships suggest that information theory is an effective tool to measure this intrinsic complexity. In this paper we pose and answer an information theoretic question about computation which has not been considered before. The question is, for a given computation problem and some given input distribution, what is the least information that an intelligent computation box needs to observe from the input to be able to find the output. We show that this quantity is an information theoretic generalization to the average depth of decision trees and therefore it can be utilized to measure the intrinsic complexity of computation for any input distribution.


14:0014:30, Paper WIIE.220  
Bounds on Distortion BitCost Function for First Order SigmaDelta AnalogToDigital Converter with Input Noise 
Kakavand, Hossein  Stanford Univ 
El Gamal, Abbas  Stanford Univ 


14:3015:00, Paper WIIE.230  
Error Exponents for Joint SourceChannel Coding with DelayConstraints 
Chang, Cheng  UC Berkeley 
Sahai, Anant  UC Berkeley 
Keywords: Information Theory
Abstract: Traditionally, joint sourcechannel coding is viewed in the block coding context — all the source symbols are known in advance by the encoder. Here, we consider source symbols to be revealed to the encoder in real time and require that they be reconstructed at the decoder within a certain fixed endtoend delay. We derive upper and lower bounds on the reliability function with delay for cases with and without channel feedback. For erasure channels with feedback, the upperbound is shown to be achievable and the resulting scheme shows that from a delay perspective, nearly separate source and channel coding is optimal.


15:3016:00, Paper WIIE.250  
Lossy Source Coding for a Cascade Communication System with SideInformations 
Vasudevan, Dinkar  EPFL 
Tian, Chao  EPFL 
Diggavi, Suhas  EPFL 
Keywords: Information Theory
Abstract: We investigate source coding in a cascade communication system consisting of an encoder, a relay and an end terminal, where both the relay and the end terminal wish to reconstruct source X with certain fidelities. Additionally, sideinformations Z and Y are available at the relay and the end terminal, respectively. The sideinformation Z at the relay is a physically degraded version of sideinformation Y at the end terminal. Inner and outer bounds for the rate distortion region are provided in this work for general discrete memoryless sources. The rate distortion region is characterized when the source and sideinformations are jointly Gaussian and physically degraded. The doubly symmetric binary source is also investigated and the inner and outer bounds are shown to coincide in certain distortion regimes. A complete equivalence of the ratedistortion region is established between the problem being considered and the sideinformation scalable source coding problem, when there is no sideinformation at the relay. As a byproduct, the same equivalence can be established between the wellknown successive refinement problem and Yamamoto's cascade communication system, without relying on their ratedistortion characterization.


16:0016:30, Paper WIIE.260  
Coding into a Source: A Direct Inverse RateDistortion Theorem 
Agarwal, Mukul  MIT 
Sahai, Anant  UC Berkeley 
Mitter, Sanjoy  MIT 
Keywords: Information Hiding and Watermarking, Source Coding and Compression, Coding Theory
Abstract: Shannon proved that if we can transmit bits reliably at rates larger than the rate distortion function R(D), then we can transmit this source to within a distortion D. We answer the converse question ``If we can transmit a source to within a distortion D, can we transmit bits reliably at rates less than the rate distortion function?'' in the affirmative. This can be viewed as a direct converse of the rate distortion theorem.


WIIF 
Brick 
Queueing Theory 
Regular Session 
Chair: Meyn, Sean  Univ. of Illinois 

13:3014:00, Paper WIIF.210  
Scheduling with Soft Deadlines for Input Queued Switches 
Dua, Aditya  Stanford Univ 
Bambos, Nicholas  Stanford Univ 
Keywords: Stochastic Systems and Control, Performance Analysis, Control Applications
Abstract: We study the problem of deadline aware scheduling for input queued (IQ) switches. While most research on IQ switch scheduling has focused on optimizing performance for nonrealtime traffic, packet deadlines are a key consideration in the context of realtime applications. In this paper, we introduce the notion of ``soft deadlines'' and study the scheduling problem within a dynamic programming (DP) framework. We demonstrate that by partitioning the set of switch configurations into ``orthogonal'' and ``complete'' subsets, the IQ switch scheduling problem is transformed into one of scheduling parallel queues on a single server. We establish key structural properties of the optimal policy for the latter problem. We show that operating the switch using a single configuration subset is good enough to support any uniform admissible load. Further, we show that a scheduling policy which combines subset based operation with a randomized subset selection rule can support any admissible load. The randomized policy requires a Birkhoffvon Neumann decomposition of the load vector. To eliminate this dependence, we propose a heuristic subset selection policy based on periodic maximum weight matching (pMWM). We demonstrate the efficacy of the proposed policies via simulations. The proposed policies have a computational complexity of only {cal O}(N^2) per timeslot, and outperform MWM under many scenarios.


14:0014:30, Paper WIIF.220  
A New MinCut Problem with Application to Electric Power Network Partitioning 
Sen, Arunabha  Arizona State Univ 
Ghosh, Pavel  Arizona State Univ 
Vittal, Vijay  Arizona State Univ 
Yang, Bo  Arizona State Univ 
Keywords: Control Applications
Abstract: The problem of partitioning a graph into two or more subgraphs that satisfies certain conditions is encountered in many different domains. Accordingly, graph partitioning problem has been studied extensively in the last fifty years. The most celebrated result among this class of problems is the max flow = min cut theorem due to Ford and Fulkerson. Utilizing the modifications suggested by Edmonds and Karp, it is well known that the minimum capacity cut in the directed graph with edge weights can be computed in polynomial time. If the partition divides the node set V into subsets V_1 and V_2, where V_1 contains the source node s and V_2 contains the destination node t, the capacity of a cut is defined as the sum of the edge weights going from V_1 to V_2. In this paper, we consider a graph partition problem which is encountered in electric power distribution networks. In this environment, the capacity of a cut is defined as the absolute value of the difference of the edge weights going from V_1 to V_2 and V_2 to V_1. Surprisingly, with slight change of the definition of the capacity of a cut, the computational complexity of the problem changes significantly. In this paper we show that with the new definition of the capacity of a cut, the minimum cut computation problem becomes NPcomplete. We provide an optimal solution to the problem using mathematical programming techniques. In addition, we also provide a heuristic solution and compare the performan


14:3015:00, Paper WIIF.230  
Linear Stability Analysis of FAST TCP Using a New Accurate Link Model 
Tang, Ao (Kevin)  California Inst. of Tech 
Jacobsson, Krister  KTH 
Andrew, Lachlan  California Inst. of Tech 
Low, Steven  California Inst. of Tech 
Keywords: Pricing and Congestion Control
Abstract: A link model which captures the queue dynamics when congestion windows of TCP sources change was recently proposed. By considering both the selfclocking and the link integrator effects, the model is a generalization of the known extreme cases and is more accurate in general. In this paper, we apply this model to the stability analysis of FAST TCP. It is shown that FAST TCP flows over a single link are always linearly stable regardless of delay distribution. This result resolves the notable discrepancy between empirical observations and previous theoretical predictions. The analysis highlights the critical role of selfclocking in TCP stability and the scalability of FAST TCP with respect to delay. The proof technique is new and much less conservative than existing ones.


15:3016:00, Paper WIIF.250  
Cooperation and Resource Sharing in Data Networks: A Queueing Perspective 
Javidi, Tara  Univ. of California, San Diego 
Keywords: Queuing Theory and Analysis, Dynamic Games and Decision Theory, Performance Analysis
Abstract: From multidescription/multipath routing for multimedia applications to content distribution in P2P networks to community networking, many forms of resource sharing have been proposed to improve the network performance. From the perspective of any one user, when ignoring the interaction among users, all such schemes reduce to various forms of providing parallelism and, hence, increased throughput. In this paper, we argue that focusing on parallelism is by no means sufficient as it ignores the existence of many users with potentially similar strategies. In this paper, we illustrate the issue of resource sharing in the above context via a multiqueue multiserver problem. Although, our proposed model is not realistic in that it ignores the overhead inefficiencies, it does capture the tradeoff between parallelism and reassembly/synchronization delay to a larger extent. We use this model to provide analytical results in a special case of homogeneous users and servers. Furthermore, we prove the robustness of a certain locally optimal strategy to noncooperation in a Nash equilibrium/strategy context.


16:0016:30, Paper WIIF.260  
A MultiClass DiscreteTime ProcessorSharing Queueing Model for Scheduled Message Communication Over Multiaccess Channels with Joint MaximumLikelihood Decoding 
Kompalli Chakravartula, Kalyanarama Sesha Sayee  Indian Inst. of Science 
Mukherji, Utpal  Indian Inst. of Science 
Keywords: Queuing Theory and Analysis, Information Theory, Wireless Communications
Abstract: We develop a multiclass discretetime processorsharing queueing model for scheduled message communication over a discrete memoryless multiple access channel with joint maximumlikelihood decoding. The framework we consider here models both the random message arrivals and the subsequent reliable communication by suitably combining techniques from queueing theory and information theory. Requests for message transmissions are assumed to arrive according to i.i.d. arrival processes. Then, (i) we derive an outer bound to the stability region of message arrival rate vectors achievable by the class of stationary scheduling policies, (ii) we show for any message arrival rate vector that satisfies the outer bound, that there exists a stationary ``stateindependent'' policy that results in a stable system for the corresponding message arrival processes, and (iii) the stability region of information arrival rate vectors is the informationtheoretic capacity region of a multiaccess channel.


16:3016:45, Paper WIIF.271  
Stable Throughput of Cognitive Radios with Relaying Capability 
Simeone, Osvaldo  NJIT 
Yeheskel, BarNess  NJIT 
Spagnolini, Umberto  Pol. Di Milano 
Keywords: Wireless Communications, Information Theory, Queuing Theory and Analysis
Abstract: A cognitive interference channel consists of two singleuser links, one licensed to use the spectral resource (primary) and one unlicensed (secondary or cognitive). According to the cognitive radio principle, the activity of the secondary link should not interfere with the performance of the primary link. The cognitive transmitter then accesses the channel only when sensed idle. In this paper, the advantages of having the cognitive transmitter acting as a "transparent relay" for the packets of the primary are investigated in terms of stable throughput (packets/slot). The analysis accounts for random packet arrivals, sensing errors due to fading at the secondary link, and power allocation at the secondary transmitter based on longterm measurements.


16:4517:00, Paper WIIF.272  
On BestCase Throughput of Cellular Data Networks with Cooperating Base Stations 
Acampora, Anthony  Univ. of California, San Diego 
Bhardwaj, Sumit  Univ. of California, San Diego 
Tamari, Ron  Qualcomm Inc 
Keywords: MIMO Systems, Wireless Communications
Abstract: In this paper, we consider a cellular radio system in which base stations cooperate over noisefree, infinite capacity wireline links. Attention is confined to the forward direction. A simple Poisson packet arrival process is assumed, and the ratio of traffic intended for each user is specified in advance. The channel between each base station and each mobile is randomly drawn but otherwise static. For this system, we combine physical level multiuser communication theory (in particular, Dirty Paper Coding) with a coupled queueing model to evaluate achievable delay and throughput. The service rates of the user queues are coupled by virtue of the system's multiuser capacity surface. An exact expression is found for the maximum achievable throughput for this system. A service discipline dependent on the empty/nonempty status of each queue is proposed and a fixedpoint approximation is derived and applied to compute the average delay. Simulations confirm that the fixedpoint approximation is an excellent approximation to the average delay.


17:0017:30, Paper WIIF.280  
Modulated Branching Processes and Origins of Power Laws 
Jelenkovic, Predrag R.  Columbia Univ 
Tan, Jian  Columbia Univ 
Keywords: Performance Analysis, Reliable and Trustworthy Networks
Abstract: Power law distributions have been repeatedly observed in a wide variety of socioeconomic, biological and technological areas, including: distributions of wealth, speciesarea relationships, populations of cities, values of companies, sizes of living organisms and, more recently, distributions of documents and visitors on the Web, etc. In the vast majority of these observations, e.g., city populations and sizes of living organisms, the objects of interest evolve due to the replication of their many independent components, e.g., birthsdeaths of individuals and replications of cells. Furthermore, the rates of replication of the many components are often controlled by exogenous parameters causing periods of expansion and contraction, e.g., baby booms and busts, economic booms and recessions, etc. In addition, the sizes of these objects often either have reflective lower boundaries, e.g., cities do not fall bellow a certain size, low income individuals are subsidized by the government, companies are protected by bankruptcy laws, etc; or have porous/absorbing lower boundaries, e.g., cities may degenerate, bankruptcy protection may fail and a company can be liquidated. Hence, it is natural to propose reflected modulated branching processes as generic models for many of the preceding observations of power laws. Indeed, our main results show that these apparently new mathematical objects result in power law distributions under quite general ``polynomial G"artnerEllis'' conditions.


WIIG 
Visitor Center 
Fading Channels 
Regular Session 
Chair: Poon, Ada  Univ. of Illinois at UrbanaChampaign 

13:3014:00, Paper WIIG.210  
FiniteSNR DiversityMultiplexing Tradeoffs for Half Duplex Protocols in Fading Relay Channels 
Stauffer, Erik  Stanford Univ 
Oyman, Ozgur  Intel Corp 
Narasimhan, Ravi  Univ. of California, Santa Cruz 
Paulraj, Arogyaswami  Stanford Univ 
Keywords: Performance Analysis, Wireless Communications, Sensor Networks in Communications
Abstract: We analyze the diversitymultiplexing tradeoff in a fading relay channel at finite signaltonoise ratios (SNRs). In this framework, the rate adaptation policy is such that the target system data rate is a multiple of the capacity of an additive white Gaussian noise (AWGN) channel. The proportionality constant determines how aggressively the system scales the data rate and can be interpreted as a finiteSNR multiplexing gain. The diversity gain is given by the negative slope of the outage probability with respect to the SNR. The finiteSNR diversitymultiplexing tradeoff is characterized for three practical decode and forward halfduplex cooperative protocols with different amounts of broadcasting and simultaneous reception. For each configuration, system performance is computed as a function of SNR under a systemwide power constraint on the source and relay transmissions. Our analysis yields the following findings; (i) improved multiplexing performance can be achieved at any SNR by allowing the source to transmit constantly, (ii) both broadcasting and simultaneous reception are desirable in halfduplex relay cooperation for superior diversitymultiplexing performance, and (iii) the diversitymultiplexing tradeoff at finiteSNR is impacted by the power partitioning between the source and the relay terminals. Finally, we verify our analytical results by numerical simulations.


14:0014:30, Paper WIIG.220  
On Successive Refinement of Diversity for Fading ISI Channels 
Dusad, Sanket  EPFL 
Diggavi, Suhas  EPFL 
Keywords: Coding Techniques and Applications, Information Theory, Wireless Communications
Abstract: Rate and diversity impose a fundamental tradeoff in communications. This tradeoff was investigated for Intersymbol Interference (ISI) channels in [4]. A different point of view was explored in [1] where highrate codes were designed so that they have a highdiversity code embedded within them. Such diversity embedded codes were investigated for flat fading channels and in this paper we explore its application to ISI channels. In particular, we investigate the rate tuples achievable for diversity embedded codes for scalar ISI channels through particular coding strategies. The main result of this paper is that the diversity multiplexing tradeoff for fading ISI channels is indeed successively refinable. This implies that for fading single input single output (SISO) ISI channels one can embed a high diversity code within a high rate code without any performance loss (asymptotically). This is related to a deterministic structural observation about the asymptotic behavior of frequency response of channel with respect to fading strength of time domain taps.


14:3015:00, Paper WIIG.230  
On Optimal Outage in Fading Relay Channels at Low SNR 
Atia, George  Boston Univ 
Sharif, Masoud  Boston Univ 
Saligrama, Venkatesh  Boston Univ 
Keywords: Wireless Communications, Information Theory
Abstract: This paper deals with outage capacity of relay networks in the low signal to noise ratio (SNR) regime. The general topic of relay networks has generated significant interest in the context of cooperative communications for cognitive radio applications. Our paper is motivated by the need to account for new challenging constraints that naturally arise in these applications. First, channel models are generally unknown and this calls for strategies that are robust to lack of this knowledge. Second, it is desirable to minimize the power utilized in any cooperative architecture so that the interference outside a footprint is minimized. With regards to robustness to channel models we consider the Bursty Amplify and Forward (BAF) scheme, that has recently been shown to be optimal for Rayleigh channels, and show that this scheme achieves the optimal outage capacity for a wide range of channel models. We prove that, for all channel fading distributions with a valid Taylor expansion in the neighborhood of zero and with zero mass at zero, BAF is optimal. We then consider Nrelay networks and present a scheme that opportunistically uses only one relay and achieves an outage within a constant fraction of that of a scheme that uses all the N relays. The proposed scheme spends much less average power, independent of N, thus holding out potential for significant gains while minimizing interference to possibly other users.


15:3016:00, Paper WIIG.250  
Minimum Probability of Error in Sparse Wideband Channels 
Hariharan, Gautham  Univ. of WisconsinMadison 
Sayeed, Akbar  Univ. of WisconsinMadison 
Keywords: Wireless Communications, Information Theory, MIMO Systems
Abstract: This paper studies the impact of channel coherence and the role of channel state information (CSI) on the probability of error in wideband multipath fading channels. Inspired by recent ultra wideband channel measurement campaigns, we propose a sparse channel model for time and frequency selective fading in which the number of resolvable channel paths grow sublinearly with signal space dimensions. As a result, the degrees of freedom (DoF) in the channel scale sublinearly. With perfect CSI, the DoF reflect the amount of channel diversity whereas with no CSI, the DoF represent the level of channel uncertainty. Based on this model, we investigate the reliability of wideband communication using error exponents. With perfect CSI at the receiver, it is seen that sparse channels are less reliable to communicate over than rich channels in which the paths scale linearly with signaling dimensions. When there is no receiver CSI, we analyze trainingbased communication schemes aimed at learning the sparse channel and our results reveal a fundamental tradeoff between channel learnability and diversity that affects error performance. We present numerical examples with realistic parameter sets and discuss the conditions under which the two effects can be balanced to obtain the best probability of error in any practical system.


16:0016:15, Paper WIIG.261  
Tracking Performance of an LMSLinear Equalizer for Fading Channels 
Kavitha, Veeraruna  Indian Inst. of Science 
Sharma, Vinod  Indian Inst. of Science 
Keywords: Wireless Communications, Statistical Signal Processing
Abstract: We consider a time varying wireless fading channel, equalized by an LMS linear equalizer. We study how well this equalizer tracks the optimal Wiener equalizer. We model the channel by an Autoregressive (AR) process. Then the LMS equalizer and the AR process are jointly approximated by the solution of a system of ODEs (ordinary differential equations). Using these ODEs, the error between the LMS equalizer and the instantaneous Wiener filter is shown to decay exponentially/polynomially to zero unless the channel is marginally stable in which case the convergence may not hold. Using the same ODEs, we also show that the corresponding Mean Square Error (MSE) converges towards minimum MSE (MMSE) at the same rate for a stable channel. We further show that the difference between the MSE and the MMSE does not explode with time even when the channel is unstable. Finally we obtain an optimum step size for the linear equalizer in terms of the AR parameters, whenever the error decay is exponential.


16:1516:30, Paper WIIG.262  
On the Spectral Efficiency of Noncoherent Doubly Selective Channels 
Kannu, Arun  The Ohio State Univ 
Schniter, Philip  The Ohio State Univ 
Keywords: Information Theory, Wireless Communications, Detection and Estimation
Abstract: This paper considers block transmissions over singleantenna doubly selective channels that obey a complexexponential basis expansion model. We consider the noncoherent case, when the channel fading coefficients are not known at both transmitter and receiver. We characterize the spectral efficiency of the channel when the inputs are chosen from continuous distributions. Then, we study several pilot aided transmissions (PAT) over the doubly selective channels. We establish that all the PAT schemes designed to minimize the channel estimation error variance are spectrally inefficient. We also design novel spectrally efficient PAT schemes.


16:3016:45, Paper WIIG.271  
On the Impact of Finite Receiver Resolution in Fading Channels 
Middleton, Gareth  Rice Univ 
Sabharwal, Ashutosh  Rice Univ 
Keywords: Wireless Communications, MIMO Systems, Statistical Signal Processing
Abstract: In this paper, we will consider the impact of finite resolution in a receiver analogdigital converter on the performance of square, linearly modulated systems over fading channels. We show that in fading channels, the probability of error in a quantized system cannot be reduced to zero due to the introduction of quantization noise, even for arbitrarily large SNR. The error floor occurs due to a nonzero number of outage events events caused by channel fading below a threshold which does not decrease with SNR and is completely determined by quantization noise. We characterize this quantization noise and discuss the relation between number of receive antennas L, modulation order M, and bits of quantization b.


16:4517:00, Paper WIIG.272  
Untangling the SVD's of Random Matrix Sample Paths 
Browne, David W.  Univ. of California at Los Angeles 
Browne, Michael W.  Ohio State Univ 
Fitz, Michael P.  Northrop Grumman 
Keywords: MIMO Systems, Statistical Signal Processing, Wireless Communications
Abstract: Singular Value Decomposition (SVD) is a powerful tool for multivariate analysis. However, independent computation of the SVD for each sample taken from a bandlimited matrix random process will result in singular value sample paths whose tangled evolution is not consistent with the structure of the underlying random process. The solution to this problem is developed as follows: (i) a SVD with relaxed identification conditions is proposed, (ii) an approach is formulated for computing the SVD's of two adjacent matrices in the sample path with the objective of maximizing the correlation between corresponding singular vectors of the two matrices, and (iii) an efficient algorithm is given for untangling the singular value sample paths. The algorithm gives a unique solution conditioned on the seed matrix's SVD. Its effectiveness is demonstrated on bandlimited Gaussian randommatrix sample paths. Results are shown to be consistent with those predicted by randommatrix theory. A primary application of the algorithm is in multipleantenna radio systems. The benefit promised by using SVD untangling in these systems is that the fading rate of the channel's SVD factors is greatly reduced so that the performance of channel estimation, channel feedback and channel prediction can be increased.

 