Search

The survey propagation (SP) algorithm for solving k-SAT problems has been shown recently as an instance of the belief propagation (BP) algorithm. In this paper, we show that for general constraint-satisfaction problems, SP may not be reducible from BP. We also establish the conditions under which such a reduction is possible. Along our development, we present a unification of the existing SP algorithms in terms of a probabilistically interpretable iterative procedure -- weighted probabilistic token passing. [ABSTRACT FROM AUTHOR]

This paper considers the problem of transmitting linear functions of two correlated Gaussian sources over a two-user additive Gaussian noise multiple access channel. The goal is to recover this linear function within an average mean squared error distortion criterion. Each transmitter has access to only one of the two Gaussian sources and is limited by an average power constraint. In this paper, a lattice coding scheme and two lower bounds on the achievable distortion are presented. The lattice scheme achieves within a constant of a distortion lower bound if the signal-to-noise ratio is greater than a threshold. Furthermore, for the difference of correlated Gaussian sources, uncoded transmission is shown to be worse in performance to lattice coding methods for correlation coefficients above a threshold. [ABSTRACT FROM AUTHOR]

In this paper, Bayesian quickest change detection problems with sampling right constraints are considered. In particular, there is a sequence of random variables whose probability density function will change at an unknown time. The goal is to detect this change in a way such that a linear combination of the average detection delay and the false alarm probability is minimized. Two types of sampling right constrains are discussed. The first one is a limited sampling right constraint, in which the observer can take at most \(N\) observations from this random sequence. Under this setup, we show that the cost function can be written as a set of iterative functions, which can be solved by Markov optimal stopping theory. The optimal stopping rule is shown to be a threshold rule. An asymptotic upper bound of the average detection delay is developed as the false alarm probability goes to zero. This upper bound indicates that the performance of the limited sampling right problem is close to that of the classic Bayesian quickest detection for several scenarios of practical interest. The second constraint discussed in this paper is a stochastic sampling right constraint, in which sampling rights are consumed by taking observations and are replenished randomly. The observer cannot take observations if there are no sampling rights left. We characterize the optimal solution, which has a very complex structure. For practical applications, we propose a low complexity algorithm, in which the sampling rule is to take observations as long as the observer has sampling rights left and the detection scheme is a threshold rule. We show that this low complexity scheme is first order asymptotically optimal as the false alarm probability goes to zero. [ABSTRACT FROM AUTHOR]

This paper is concerned with the advantages of multi-user concurrent transmission in multiple-input multiple-output (MIMO) systems with rate constraints. We first study a maximum eigenmode beamforming (MEB) strategy for fading multiple access channels (MACs). This strategy allows each user to transmit only in its maximum eigenmode direction and applies a suboptimal matched-filter receiver with successive interference cancellation at the base station (BS). We derive a closed-form expression for the average minimum transmitted sum power required by MEB. Based on this, we show that: a) the MEB strategy is asymptotically optimal when the number of simultaneous users is sufficiently large; b) multi-user concurrent transmission has a power advantage, referred to as multi-user gain, over orthogonal transmission approaches such as time-division multiple-access; c) the number of antennas at the BS has a far stronger impact on the system performance than that at each user side. These properties are verified by simulation. Both numerical analyses and simulation results show that a major part of multi-user gain can be achieved in practical environments even with a quite small number of simultaneous users. We also study the MEB strategy for MIMO broadcast channels (BCs). The dirty paper coding (DPC) technique is necessary in this case. It is analytically shown that most observations made for MIMO MACs are extendable to MIMO BCs. [ABSTRACT FROM AUTHOR]

Multicast transmission, wherein the same packet must be delivered to multiple receivers, is an important aspect of sensor and tactical networks and has several distinctive traits as opposed to more commonly studied unicast networks. Specially, these include 1) identical packets must be delivered successfully to several nodes, 2) outage at any receiver requires the packet to be retransmitted at least to that receiver, and 3) the multicast rate is dominated by the receiver with the weakest link in order to minimize outage and retransmission. A first contribution of this paper is the development of a tractable multicast model and throughput metric that captures each of these key traits in a multicast wireless network. We utilize a Poisson cluster process (PCP) consisting of a distinct Poisson point process (PPP) for the transmitters and receivers, and then define the multicast transmission capacity (MTC) as the maximum achievable multicast rate per transmission attempt times the maximum intensity of multicast clusters under decoding delay and multicast outage constraints. A multicast cluster is a contiguous area over which a packet is multicasted, and to reduce outage it can be tessellated into v smaller regions of multicast. The second contribution of the paper is the analysis of several key aspects of this model, for which we develop the following main result. Assuming \tau/v transmission attempts are allowed for each tessellated region in a multicast cluster, we show that the MTC is \Theta\left(\rho k^x\log(k)v^y\right) where \rho, x and y are functions of \tau and v depending on the network size and intensity, and k is the average number of the intended receivers in a cluster. We derive \\rho, x, y\ for a number of regimes of interest, and also show that an appropriate number of retransmissions can significantly enhance the MTC. [ABSTRACT FROM AUTHOR]

It is conjectured that the covariance matrices minimizing the outage probability under a power constraint for multiple-input multiple-output channels with Gaussian fading are diagonal with either zeros or constant values on the diagonal. In the multiple-input single-output (MISO) setting, this is equivalent to conjecture that the Gaussian quadratic forms having largest tail probability correspond to such diagonal matrices. This paper provides a proof of the conjecture in this MISO setting. [ABSTRACT FROM PUBLISHER]

This paper studies the structure of downlink sum-rate maximizing selective decentralized feedback policies for opportunistic beamforming under finite feedback constraints on the average number of mobile users feeding back. First, it is shown that any sum-rate maximizing selective decentralized feedback policy must be a threshold feedback policy. This result holds for all fading channel models with continuous distribution functions. Second, the resulting optimum threshold selection problem is analyzed in detail. This is a nonconvex optimization problem over finite-dimensional Euclidean spaces. By utilizing the theory of majorization, an underlying Schur-concave structure in the sum-rate function is identified, and the sufficient conditions for the optimality of homogenous threshold feedback policies are obtained. Applications of these results are illustrated for well-known fading channel models such as Rayleigh, Nakagami, and Rician fading channels. Rather surprisingly, it is shown that using the same threshold value at all mobile users is not always a rate-wise optimal feedback strategy, even for a network in which mobile users experience statistically the same channel conditions. For the Rayleigh fading channel model, on the other hand, homogenous threshold feedback policies are proven to be rate-wise optimal if multiple orthonormal data carrying beams are used to communicate with multiple mobile users simultaneously. [ABSTRACT FROM PUBLISHER]

This paper considers the two-cell two-hop multiple-input-multiple-output (MIMO) interference channel, where two source groups consisting of multiple users with a single antenna wish to communicate with two multiantenna destinations by sharing two multiantenna relays. For such a channel, an inner bound on the degrees of freedom is derived for different channel knowledge assumptions and relay operations. Assuming global channel knowledge at the relays and full-duplex relay operation, it is shown that two cascaded interfering links can be decomposed into two independent parallel relay channels while sharing the spectrum. The key to showing this result is a novel amplify-and-forward interference-free relay transmission method, which performs interference-shaping during reception and interference neutralization during transmission. Assuming that the relays have global channel knowledge only for the first hop, a spectrally efficient relaying protocol is proposed that overcomes the loss due to half-duplex relaying constraint. The proposed protocol improves performance compared to a trivial time-division-multiple access method for the two-cell two-hop MIMO interference channel. [ABSTRACT FROM PUBLISHER]

Owing to the special structure of the Gaussian multiple-input multiple-output (MIMO) broadcast channel (BC), the associated capacity region computation and beamforming optimization problems are typically non-convex, and thus cannot be solved directly. One feasible approach is to consider the respective dual multiple-access channel (MAC) problems, which are easier to deal with due to their convexity properties. The conventional BC-MAC duality has been established via BC-MAC signal transformation, and is applicable only for the case in which the MIMO BC is subject to a single transmit sum-power constraint. An alternative approach is based on minimax duality, which can be applied to the case of the sum-power constraint or per-antenna power constraint. In this paper, the conventional BC-MAC duality is extended to the general linear transmit covariance constraint (LTCC) case, which includes sum-power and per-antenna power constraints as special cases. The obtained general BC-MAC duality is applied to solve the capacity region computation for the MIMO BC and beamforming optimization for the multiple-input single-output (MISO) BC, respectively, with multiple LTCCs. The relationship between this new general BC-MAC duality and the minimax duality is also discussed, and it is shown that the general BC-MAC duality leads to simpler problem formulations. Moreover, the general BC-MAC duality is extended to deal with the case of nonlinear transmit covariance constraints in the MIMO BC. [ABSTRACT FROM AUTHOR]

The capacity region of the N-sender Gaussian multiple access channel with feedback is not known in general. This paper studies the class of linear-feedback codes that includes (nonlinear) nonfeedback codes at one extreme and the linear-feedback codes by Schalkwijk and Kailath, Ozarow, and Kramer at the other extreme. The linear-feedback sum-capacity CL(N,P) under symmetric power constraints P is characterized, the maximum sum-rate achieved by linear-feedback codes when each sender has the equal block power constraint P. In particular, it is shown that Kramer's code achieves this linear-feedback sum-capacity. The proof involves the dependence balance condition introduced by Hekstra and Willems and extended by Kramer and Gastpar, and the analysis of the resulting nonconvex optimization problem via a Lagrange dual formulation. Finally, an observation is presented based on the properties of the conditional maximal correlation—an extension of the Hirschfeld-Gebelein-Rényi maximal correlation—which reinforces the conjecture that Kramer's code achieves not only the linear-feedback sum-capacity, but also the sum-capacity itself (the maximum sum-rate achieved by arbitrary feedback codes). [ABSTRACT FROM PUBLISHER]

Nonadaptive group testing involves grouping arbitrary subsets of n items into different pools. Each pool is then tested and defective items are identified. A fundamental question involves minimizing the number of pools required to identify at most d defective items. Motivated by applications in network tomography, sensor networks and infection propagation, a variation of group testing problems on graphs is formulated. Unlike conventional group testing problems, each group here must conform to the constraints imposed by a graph. For instance, items can be associated with vertices and each pool is any set of nodes that must be path connected. In this paper, a test is associated with a random walk. In this context, conventional group testing corresponds to the special case of a complete graph on n vertices. For interesting classes of graphs a rather surprising result is obtained, namely, that the number of tests required to identify d defective items is substantially similar to what is required in conventional group testing problems, where no such constraints on pooling is imposed. Specifically, if T(n) corresponds to the mixing time of the graph G, it is shown that with m=O(d^2T^2(n)\log(n/d)) nonadaptive tests, one can identify the defective items. Consequently, for the Erdős-Rényi random graph G(n,p), as well as expander graphs with constant spectral gap, it follows that m=O(d^2\log^3n) nonadaptive tests are sufficient to identify d defective items. Next, a specific scenario is considered that arises in network tomography, for which it is shown that m=O(d^3\log^3n) nonadaptive tests are sufficient to identify d defective items. Noisy counterparts of the graph constrained group testing problem are considered, for which parallel results are developed. We also briefly discuss extensions to compressive sensing on graphs. [ABSTRACT FROM PUBLISHER]

In this paper, a lower bound on the capacity of wireless ad hoc erasure networks is derived in closed form in the case where n nodes are uniformly and independently distributed in the unit area square. It holds almost surely and is asymptotically tight. Nodes are assumed to have fixed transmit power; hence, two nodes should be within a specified distance rn to overcome noise. With interference determining outages, each transmitter-receiver pair is modeled as an erasure channel with a broadcast constraint, i.e., each node can transmit only one signal across all its outgoing links. A lower bound of \Theta (n rn) for the network capacity is derived when erasures across distinct links are independent, with constant erasure probabilities. When erasures are correlated, the lower bound \Theta \left ( 1\over rn\right ) is proved. If the broadcast constraint is relaxed, the gain is a function of rn and the link erasure probabilities, and is at most a constant if the erasure probabilities grow sufficiently large with n. Finally, the case where the erasure probabilities are random variables, for example due to randomness in geometry or channels, is analyzed. In this setting, it is shown somewhat surprisingly that variability in erasure probabilities increases network capacity. [ABSTRACT FROM AUTHOR]

The problem of finding a minimum decomposition of a permutation in terms of transpositions with predetermined non-uniform and non-negative costs is addressed. Alternatively, computing the transposition distance between two permutations, where transpositions are endowed with arbitrary non-negative costs, is studied. For such cost functions, polynomial-time, constant-approximation decomposition algorithms are described. For metric-path costs, exact polynomial-time decomposition algorithms are presented. The algorithms in this paper represent a combination of Viterbi-type algorithms and graph-search techniques for minimizing the cost of individual transpositions, and dynamic programing algorithms for finding minimum cost decompositions of cycles. The presented algorithms have a myriad of applications in information theory, bioinformatics, and algebra. [ABSTRACT FROM PUBLISHER]

A practical constraint that comes in the way of spectrum estimation of a continuous time stationary stochastic process is the minimum separation between successively observed samples of the process. When the underlying process is not band-limited, sampling at any uniform rate leads to aliasing, while certain stochastic sampling schemes, including Poisson process sampling, are rendered infeasible by the constraint of minimum separation. It is shown in this paper that, subject to this constraint, no point process sampling scheme is alias-free for the class of all spectra. It turns out that point process sampling under this constraint can be alias-free for band-limited spectra. However, the usual construction of a consistent spectrum estimator does not work in such a case. Simulations indicate that a commonly used estimator, which is consistent in the absence of this constraint, performs poorly when the constraint is present. These results should help practitioners in rationalizing their expectations from point process sampling as far as spectrum estimation is concerned, and motivate researchers to look for appropriate estimators of bandlimited spectra. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of recovering sparse or compressible signals from uniformly quantized measurements. We present a new class of convex optimization programs, or decoders, coined Basis Pursuit DeQuantizer of moment p (BPDQ_p), that model the quantization distortion more faithfully than the commonly used Basis Pursuit DeNoise (BPDN) program. Our decoders proceed by minimizing the sparsity of the signal to be reconstructed subject to a data-fidelity constraint expressed in the \ell_p-norm of the residual error for 2\leqslant p\leqslant \infty. [ABSTRACT FROM AUTHOR]

The capacity of 1-D constraints is given by the entropy of a corresponding stationary maxentropic Markov chain. Namely, the entropy is maximized over a set of probability distributions, which is defined by some linear equalities and inequalities. In this paper, certain aspects of this characterization are extended to 2-D constraints. The result is a method for calculating an upper bound on the capacity of 2-D constraints. The key steps are as follows: The maxentropic stationary probability distribution on square configurations is considered; set of linear equalities and inequalities is derived from this stationarity; the result is then a convex program, which can be easily solved numerically. Our method improves upon previous upper bounds for the capacity of the 2-D “no isolated bits” constraint, as well as certain 2-D RLL constraints. [ABSTRACT FROM AUTHOR]

The two user multiple-input single-output (MISO) broadcast channel with confidential messages (BCCM) is studied, in which the nature of channel state information at the transmitter (CSIT) from each user can be of the form Ii , i=1,2 where I_{1}, I_{2}\in \{\mathsf {P}, \mathsf {D}, \mathsf {N}\} , and the forms \mathsf {P} , \mathsf D , and \mathsf N correspond to perfect and instantaneous, completely delayed, and no CSIT, respectively. Thus, the overall CSIT can alternate between nine possible states corresponding to all possible values of I1I2 , with each state occurring for \lambda I1I2 fraction of the total duration. We assume that perfect and instantaneous CSI is available at the all receivers. The main contribution of this paper is to establish the secure degrees of freedom (s.d.o.f.) region of the MISO BCCM with alternating CSIT with the symmetry assumption, where \lambda I1 I2=\lambda I2I1 . The main technical contributions include developing 1) novel achievable schemes for MISO BCCM with alternating CSIT with security constraints, which also highlight the synergistic benefits of inter-state coding for secrecy; 2) new converse proofs via local statistical equivalence and channel enhancement; and 3) showing the interplay between various aspects of channel knowledge and their impact on s.d.o.f. [ABSTRACT FROM AUTHOR]

A point-to-point multiple-relay communication system with half-duplex constraints is considered. The relays operate under the amplify-and-forward paradigm and implement a linear dispersion distributed space-time code with randomized dispersion matrices of independent and identically distributed entries. The large-signal-to-noise-ratio behavior of the asymptotically large deterministic system is studied for both the optimum (maximum likelihood) receiver and the linear minimum mean squared error (LMMSE) receiver. The diversity order of the system is shown to have a strong dependence on the aspect ratio of the linear dispersion matrices. More specifically, when the linear dispersion matrices are sufficiently tall, both receivers achieve the maximum diversity order, i.e., the total number of relays plus one. Conversely, when the linear dispersion matrices are fat (in the sense that relays linearly compress the information received from the source), the optimum receiver is shown to achieve an asymptotic diversity order of two, whereas the LMMSE receiver is totally unable to exploit the available spatial diversity. [ABSTRACT FROM PUBLISHER]

The quantum chromatic number of a graph G is sandwiched between its chromatic number and its clique number, which are well-known NP-hard quantities. We restrict our attention to the rank-1 quantum chromatic number \chi q^{(1)}(G), which upper bounds the quantum chromatic number, but is defined under stronger constraints. We study its relation with the chromatic number \chi (G) and the minimum dimension of orthogonal representations \xi (G). It is known that \xi (G) \leq \chi q^{(1)}(G) \leq \chi (G). We answer three open questions about these relations: we give a necessary and sufficient condition to have \xi (G) = \chi q^{(1)}(G), we exhibit a class of graphs such that \xi (G) < \chi q^{(1)}(G), and we give a necessary and sufficient condition to have \chi q^{(1)}(G) < \chi (G). Our main tools are Kochen–Specker sets, collections of vectors with a traditionally important role in the study of contextuality of physical theories and, more recently, in the quantification of quantum zero-error capacities. Finally, as a corollary of our results and a result by Avis on the quantum chromatic number, we give a family of Kochen–Specker sets of growing dimension. [ABSTRACT FROM AUTHOR]

List-decoding for arbitrarily varying channels (AVCs) under state constraints is investigated. It is shown that rates within \epsilon of the randomized coding capacity of AVCs with input-dependent state can be achieved under maximal error with list-decoding using lists of size O(1/\epsilon). Under the average error criterion, an achievable rate and converse bound are given for lists of size L. These bounds are based on two different notions of symmetrizability and do not coincide in general. An example is given which shows that for list size L, the capacity may be positive but strictly smaller than the randomized coding capacity, in contrast to the situation without constraints. [ABSTRACT FROM AUTHOR]

Effective capacity, which provides the maximum constant arrival rate that a given service process can support while satisfying statistical queueing constraints, is analyzed in a multiuser scenario. In particular, the effective capacity region of fading multiple-access channels in the presence of quality of service (QoS) constraints is studied. Perfect channel side information is assumed to be available at both the transmitters and the receiver. It is initially assumed that the transmitters send the information at a fixed power level and, hence, do not employ power control policies. Under this assumption, the performance achieved by superposition coding with successive decoding techniques is investigated. It is shown that varying the decoding order with respect to the channel states can significantly increase the achievable throughput region. In the two-user case, the optimal decoding strategy is determined for the scenario in which the users have the same QoS constraints. The performance of orthogonal transmission strategies is also analyzed. It is shown that for certain QoS constraints, time-division multiple access can achieve better performance than superposition coding if fixed successive decoding order is used at the receiver side. In the subsequent analysis, power control policies are incorporated into the transmission strategies. The optimal power allocation policies for any fixed decoding order over all channel states are identified. For a given variable decoding-order strategy, the conditions that the optimal power control policies must satisfy are determined, and an algorithm that can be used to compute these optimal policies is provided. [ABSTRACT FROM AUTHOR]

The secrecy throughput of mobile ad hoc networks (MANETs) with malicious nodes is investigated. The MANET consists of n legitimate mobile nodes and m malicious nodes. Transmissions between legitimate nodes are subject to a delay constraint D. A model under passive attack is first studied, in which the malicious nodes are assumed to be eavesdroppers that only listen to transmission without actively injecting signals. An information-theoretic approach for security is applied to achieve secure communication among legitimate nodes in MANETs with transmissions being kept perfectly secure from eavesdroppers. A critical threshold on the number of malicious nodes (m) is identified such that when m=o(\sqrt nD), i.e., \lim n\rightarrow \infty m/\sqrt {nD}=0, the optimal secrecy throughput equals that of MANETs without malicious nodes, i.e., the impact of the presence of malicious nodes on the network throughput is negligible; and when m=\Omega \left (\sqrt nDpoly(n)\right ), i.e., \lim n\rightarrow \infty m/\left (\sqrt {nD}poly(n)\right ) \geq c for a positive constant c, the optimal secrecy throughput is limited by the number of malicious nodes. A model under active attack is further studied, in which the malicious nodes actively attack the network by transmitting modified packets to the destination nodes. It is shown that to guarantee the same throughput as the model under passive attack, the model under active attack needs to satisfy more stringent condition on the number of malicious nodes. [ABSTRACT FROM AUTHOR]

The minimum expected length for fixed-to-variable length encoding of an n-block memoryless source with entropy H grows as n H + O(1), where the term O(1) lies between 0 and 1. However, this well-known performance is obtained under the implicit constraint that the code assigned to the whole n-block is a prefix code. Dropping the prefix constraint, which is rarely necessary at the block level, we show that the minimum expected length for a finite-alphabet memoryless source with known distribution grows as $ n H - 1 \over 2 \log n +O(1) $unless the source is equiprobable. We also refine this result up to o(1) for those memoryless sources whose log probabilities do not reside on a lattice. [ABSTRACT FROM AUTHOR]

We study ensembles of codes on graphs (generalized low-density parity-check, or LDPC codes) constructed from random graphs and fixed local constrained codes, and their extension to codes on hypergraphs. It is known that the average minimum distance of codes in these ensembles grows linearly with the code length. We show that these codes can correct a linearly growing number of errors under simple iterative decoding algorithms. In particular, we show that this property extends to codes constructed by parallel concatenation of Hamming codes and other codes with small minimum distance. Previously known results that proved this property for graph codes relied on graph expansion and required the choice of local codes with large distance relative to their length. [ABSTRACT FROM AUTHOR]

We investigate two-party cryptographic protocols that are secure under assumptions motivated by physics, namely special relativity and quantum mechanics. In particular, we discuss the security of bit commitment in the so-called split models, i.e., models in which at least one of the parties is not allowed to communicate during certain phases of the protocol. We find the minimal splits that are necessary to evade the Mayers-Lo-Chau no-go argument and present protocols that achieve security in these split models. Furthermore, we introduce the notion of local versus global command, a subtle issue that arises when the split committer is required to delegate noncommunicating agents to open the commitment. We argue that classical protocols are insecure under global command in the split model we consider. On the other hand, we provide a rigorous security proof in the global command model for Kent's quantum protocol refid="ref1"/. The proof employs two fundamental principles of modern physics, the no-signaling property of relativity and the uncertainty principle of quantum mechanics. [ABSTRACT FROM AUTHOR]

In networks with large latency, feedback about received packets may lag considerably the transmission of the original packets, limiting the feedback's usefulness. Moreover, time duplex constraints may entail that receiving feedback may be costly. In this work, we consider tailoring feedback and coding jointly in such settings to reduce the expected delay for successful in order reception of packets. We find that, in certain applications, judicious choices provide results that are close to those that would be obtained with a full-duplex system. We study two cases of data transmission: one-to-all broadcast and all-to-all broadcast. We also analyze important practical considerations weighing the trade off between performance and complexity in applications that rely on random linear network coding. Finally, we study the problem of transmission of information under the large latency and time duplexing constraints in the presence of random packet arrivals. In particular, we analyze the problem of using a batch by batch approach and an online network coding approach with Poisson arrivals. We present numerical results to illustrate the performance under a variety of scenarios and show the benefits of the proposed schemes as compared to typical ARQ and scheduling schemes. [ABSTRACT FROM AUTHOR]

A binary erasure version of n-channel multiple descriptions (MD) with symmetric descriptions (i.e., the rates of the n descriptions are equal and the distortion constraint depends only on the number of messages received) is considered. No excess rate for every k out of n descriptions, i.e., any k messages have sum rate R(Dk)=1-Dk, where R(\cdot) is Shannon's rate-distortion function for erasure distortion and Dk is the distortion constraint to be met, is investigated. The goal is to characterize the achievable distortions D1,D2,\ldots,Dn. Reconstruction fidelity is measured using two criteria: a worst-case criterion which computes distortion by maximizing the per-letter distortion over all source sequences, and an average-case criterion which computes distortion by averaging the per-letter distortion over all source sequences. Achievability schemes are presented, based on systematic maximum distance separable codes for worst-case distortion and random binning for average-case distortion, and optimality results are proved for the corresponding distortion regions. The erasure MD setup is then used to propose a layered coding framework for multiple descriptions, which is then applied to vector Gaussian MD and shown to be optimal for symmetric scalar Gaussian MD with two levels of receivers and no excess rate at the central receiver. [ABSTRACT FROM AUTHOR]

We determine the rate region of the Gaussian one-helper source-coding problem in which the helper observes a scalar, the main encoder observes a vector, and the distortion constraint is a positive semidefinite upper bound on the error covariance matrix of the main source. The rate region is achieved by a Gaussian achievable scheme. We introduce a novel outer bounding technique to establish the converse. Our approach is to create a reduced dimensional problem by projecting the main source and the distortion constraint in certain directions determined by the optimal Gaussian scheme. We also provide an outer bound to the rate region of the more general problem in which there are distortion constraints on both sources. This outer bound is partially tight in general and completely tight in some nontrivial cases. [ABSTRACT FROM PUBLISHER]

Consider a relay cascade, i.e., a network where a source node, a sink node and a certain number of intermediate source/relay nodes are arranged on a line and where adjacent node pairs are connected by error-free (q+1)-ary pipes. Suppose the source and a subset of the relays wish to communicate independent information to the sink under the condition that each relay in the cascade is half-duplex constrained. A coding scheme is developed which transfers information by an information-dependent allocation of the transmission and reception slots of the relays. The coding scheme requires synchronization on the symbol level through a shared clock. The coding strategy achieves capacity for a single source. Numerical values for the capacity of cascades of various lengths are provided, and the capacities are significantly higher than the rates which are achievable with a predetermined time-sharing approach. If the cascade includes a source and a certain number of relays with their own information, the strategy achieves the cut-set bound when the rates of the relay sources fall below certain thresholds. For cascades composed of an infinite number of half-duplex constrained relays and a single source, we derive an explicit capacity expression. Remarkably, the capacity in bits/use for q=1 is equal to the logarithm of the golden ratio, and the capacity for q=2 is 1 bit/use. [ABSTRACT FROM PUBLISHER]

The diversity-multiplexing tradeoff of the dynamic decode-and-forward protocol is characterized for the half-duplex three-terminal (m,k,n)-relay channel where the source, relay and the destination terminals have m, k and n antennas, respectively. The tradeoff curve is obtained as a solution to a simple, two-variable, convex optimization problem which is explicitly solved in closed-form for certain special classes of relay channels, namely, the (1,k,1) relay channel, the (n,1,n) relay channel and the (2,k,2) relay channel. Moreover, the tradeoff curves for a certain class of relay channels, such as the (m,k,n>k) channels, are found to be identical to those for the decode-and-forward protocol for the full duplex channel while for other classes of channels they are marginally lower at high multiplexing gains. Our results also show that for some classes of relay channels and at low multiplexing gains the diversity orders of the dynamic decode-and-forward protocol are greater than those of the static compress-and-forward protocol which in turn is known to be tradeoff optimal over all static half duplex protocols. In general, the dynamic decode-and-forward protocol has a performance that is comparable to that of the static compress-and-forward protocol which, unlike the dynamic decode-and-forward protocol, requires global channel state information at the relay node. Its performance is also close to that of the decode-and-forward protocol over the full-duplex relay channel thereby indicating that the half-duplex constraint can be compensated for by the dynamic operation of the relay wherein the relay switches from the receive to the transmit mode based on the source-relay channel quality. [ABSTRACT FROM AUTHOR]

We consider optimal scalar quantization with rth power distortion and constrained Rényi entropy of order \alpha . For sources with absolutely continuous distributions the high rate asymptotics of the quantizer distortion has long been known for \alpha =0 (fixed-rate quantization) and \alpha =1 (entropy-constrained quantization). These results have recently been extended to quantization with Rényi entropy constraint of order \alpha \geq r+1. Here we consider the more challenging case \alpha \in [-\infty ,0)\cup (0,1) and for a large class of absolutely continuous source distributions we determine the sharp asymptotics of the optimal quantization distortion. The achievability proof is based on finding (asymptotically) optimal quantizers via the companding approach, and is thus constructive. [ABSTRACT FROM AUTHOR]

The fundamental principle underlying compressed sensing is that a signal, which is sparse under some basis representation, can be recovered from a small number of linear measurements. However, prior knowledge of the sparsity basis is essential for the recovery process. This work introduces the concept of blind compressed sensing, which avoids the need to know the sparsity basis in both the sampling and the recovery process. We suggest three possible constraints on the sparsity basis that can be added to the problem in order to guarantee a unique solution. For each constraint, we prove conditions for uniqueness, and suggest a simple method to retrieve the solution. We demonstrate through simulations that our methods can achieve results similar to those of standard compressed sensing, which rely on prior knowledge of the sparsity basis, as long as the signals are sparse enough. This offers a general sampling and reconstruction system that fits all sparse signals, regardless of the sparsity basis, under the conditions and constraints presented in this work. [ABSTRACT FROM AUTHOR]

The performance of multiple-input multiple-output (MIMO) wireless systems is investigated in the presence of statistical queueing constraints. Queuing constraints are imposed as limitations on buffer violation probabilities. The performance under such constraints is captured through the effective capacity formulation. A detailed analysis of the effective capacity is carried out in the low-power, wideband, and high signal-to-noise ratio (SNR) regimes. In the low-power analysis, expressions for the first and second derivatives of the effective capacity with respect to SNR at SNR = 0 are obtained under various assumptions on the degree of channel state information at the transmitter. Transmission strategies that are optimal in the sense of achieving the first and second derivatives are identified. It is shown that while the first derivative does not get affected by the presence of queueing constraints, the second derivative gets smaller as the constraints become more stringent. Through the energy efficiency analysis, this is shown to imply that the minimum bit energy requirements do not change with more strict limitations but the wideband slope diminishes. Similar results are obtained in the wideband regime if rich multipath fading is being experienced. On the other hand, sparse multipath fading with bounded number of degrees of freedom is shown to increase the minimum bit energy requirements in the presence of queueing constraints. Following the low-SNR study, the impact of buffer limitations on the high-SNR performance is quantified by analyzing the high-SNR slope and the power offset in Rayleigh fading channels. Finally, numerical results are provided to illustrate the theoretical findings, and to demonstrate the interactions between the queueing constraints and spatial dimensions over a wide range of SNR values. [ABSTRACT FROM AUTHOR]

Line and star networks with both node and edge constraints are studied in the network coding framework. For line networks, the capacity region of the general multiple multicast problem is established. The coding theorem is based on a binary linear coding scheme, while the converse requires new upper bounds that improve on standard cut-based bounds. For star networks, the multiple unicast problem is examined. Capacity upper bounds are derived and a simple linear coding scheme is proposed which is based on the combinatorial optimization problem of cycle packing in directed graphs. The optimality of this scheme is established for a broad class of demands. The connection of node-constrained network coding in star networks, and index coding with side information is discussed and used to partially characterize the optimal linear code for general rates. [ABSTRACT FROM AUTHOR]

We examine the well-known problem of determining the capacity of multidimensional run-length-limited constrained systems. By recasting the problem, which is essentially a combinatorial counting problem, into a probabilistic setting, we are able to derive new lower and upper bounds on the capacity of (0,k)-RLL systems. These bounds are better than all previously-known analytical bounds for k\geqslant 2, and are tight asymptotically. Thus, we settle the open question: what is the rate at which the capacity of (0,k)-RLL systems converges to 1 as k\rightarrow\infty? We also provide the first nontrivial upper bound on the capacity of general (d,k)-RLL systems. [ABSTRACT FROM AUTHOR]

We study source coding in the presence of side information, when the system can take actions that affect the availability, quality, or nature of the side information. We begin by extending the Wyner-Ziv problem of source coding with decoder side information to the case where the decoder is allowed to choose actions affecting the side information. We then consider the setting where actions are taken by the encoder, based on its observation of the source. Actions may have costs that are commensurate with the quality of the side information they yield, and an overall per-symbol cost constraint may be imposed. We characterize the achievable tradeoffs between rate, distortion, and cost in some of these problem settings. Among our findings is the fact that even in the absence of a cost constraint, greedily choosing the action associated with the “best” side information is, in general, suboptimal. A few examples are worked out. [ABSTRACT FROM AUTHOR]

Constant-weight and constant-charge binary sequences with constrained run length of zeros are introduced. The weight and charge distribution for these sequences are found. Next, recurrent and direct formulas for calculating the number of these sequences are obtained. By considering these numbers of constant-weight and constant-charge run-length limited (RLL) sequences as coefficients of convergent power series, generating functions are derived. The fact that generating function for enumerating constant-charge RLL sequences does not have a closed form is proved. Subsequently, implementation of encoding and decoding procedures using Cover's enumerative scheme is shown. Based on the obtained results, some examples, such as enumeration of running-digital sum (RDS) constrained RLL sequences or peak-shifts control capability are also provided. [ABSTRACT FROM AUTHOR]

Necessary conditions for asymptotically optimal sliding-block or stationary codes for source coding and rate-constrained simulation of memoryless sources are presented and used to motivate a design technique for trellis-encoded source coding and rate-constrained simulation. The code structure has intuitive similarities to classic random coding arguments as well as to “fake process” methods and alphabet-constrained methods. Experimental evidence shows that the approach provides comparable or superior performance in comparison with previously published methods on common examples, sometimes by significant margins. [ABSTRACT FROM AUTHOR]

The sum-rate capacity of the parallel Gaussian interference channel is shown to be achieved by independent transmission across subchannels and treating interference as noise if the channel coefficients and power constraints satisfy a certain condition. The condition requires the interference to be weak, a situation commonly encountered, e.g., in digital subscriber line transmission. The optimal power allocation is characterized by using the concavity of the sum-rate capacity as a function of the power constraints. [ABSTRACT FROM AUTHOR]

The Sudoku puzzle is a discrete constraint satisfaction problem, as is the error correction decoding problem. We propose here an algorithm for solution to the Sinkhorn puzzle based on Sinkhorn balancing. Sinkhorn balancing is an algorithm for projecting a matrix onto the space of doubly stochastic matrices. The Sinkhorn balancing solver is capable of solving all but the most difficult puzzles. A proof of convergence is presented, with some information theoretic connections. A random generalization of the Sudoku puzzle is presented, for which the Sinkhorn-based solver is also very effective. [ABSTRACT FROM AUTHOR]

We study coding schemes which encode unconstrained sequences into run-length-limited (d, k) -constrained sequences. We present a general framework for the corstruction of such (d, k)-codes from variable-length source codes. This framework is an extension of the previously suggested bit stuffing, bit flipping, and symbol sliding algorithms. We show that it gives rise to new code constructions which achieve improved performance over the three aforementioned algorithms. Therefore, we are interested in finding optimal codes under this framework, optimal in the sense of maximal achievable asymptotic rates. However, this appears to he a difficult problem. In an attempt to solve it, we are led to consider the encoding of unconstrained sequences of independent but biased (as opposed to equiprobable) bits. Here, our main result is that one can use the Tunstall source coding algorithm to generate optimal codes for a partial class of (d, k) constraints. [ABSTRACT FROM AUTHOR]

We consider a number of constrained coding techniques that can be used to mitigate a nonlinear effect in the optical fiber channel that causes the formation of spurious pulses, called "ghost pulses?' Specifically, if b1 b2 …bn, is a sequence of bits sent across an optical channel, such that bk = = bm = 1 for some k, l, m (not necessarily all distinct) but bk+l-m = 0, then the ghost-pulse effect causes bk+l-m to change to 1, thereby creating an error. Such errors do not occur if the sequence of bits satisfies the following constraint: for all integers k, l, m such that bk = bl = bm = 1, we have bk+l-m = 1. We call this the binary ghost-pulse (BGP) constraint. We will show, however, that the BGP constraint has zero capacity, implying that sequences satisfying this constraint cannot carry much information. Consequently, we consider a more sophisticated coding scheme, which uses ternary sequences satisfying a certain ternary ghost-pulse (TGP) constraint. We further relax these constraints by ignoring interactions between symbols that are more than a certain distance t apart in the transmitted sequence. Analysis of the resulting BGP(t) and TGP(t) constraints shows that these have nonzero capacities, and furthermore, the TGP(t)-constrained codes can achieve rates that are significantly higher than those for the corresponding BGP(t) codes. We also discuss the design of encoders and decoders for coding into the BGP, BGP(t), and TGP(t) constraints. [ABSTRACT FROM AUTHOR]

In digital storage systems where the input to the noisy channel is required to satisfy a modulation constraint, the con strained code and error-control code (ECC) are typically designed and decoded independently. The achievable rate for this situation is evaluated as the rate of average intersection of the constraint and the ECC. The gap from the capacity of the noisy constrained channel is called the constraint gain, which represents the potential improvement in combining the design and decoding of the con- strained code and the ECC. The constraint gain is computed for various constraints over the binary-input additive white Gaussian noise (AWGN) channel (BIAWGNC) as well as over intersymbol interference (ISI) channels. Finally, it is shown that an infinite cascade of reverse concatenation with independent decoding of constraint and ECC has a capacity equal to the rate of average intera section. [ABSTRACT FROM AUTHOR]