Search

A bound on the capacity of the causal dirty-paper channel with arbitrary interference and general independent identically distributed additive noise is derived. In particular, it is shown that for the case of Gaussian noise, the capacity is upper bounded by \log_2\left(1+SNR/e\right) bits per real dimension. This bound is useful for SNR\leq e(e-2). [ABSTRACT FROM AUTHOR]

This paper presents a joint typicality framework for encoding and decoding nested linear codes in multi-user networks. This framework provides a new perspective on compute–forward within the context of discrete memoryless networks. In particular, it establishes an achievable rate region for computing a linear combination over a discrete memoryless multiple-access channel (MAC). When specialized to the Gaussian MAC, this rate region recovers and improves upon the lattice-based compute–forward rate region of Nazer and Gastpar, thus providing a unified approach for discrete memoryless and Gaussian networks. Furthermore, our framework provides some valuable insights on establishing the optimal decoding rate region for compute–forward by considering joint decoders, progressing beyond most previous works that consider successive cancellation decoding. Specifically, this paper establishes an achievable rate region for simultaneously decoding two linear combinations of nested linear codewords from $K$ senders. [ABSTRACT FROM AUTHOR]

This paper introduces the simultaneous partial-inverse problem (SPI) for polynomials and develops its application to decoding interleaved Reed–Solomon codes beyond half the minimum distance. While closely related both to standard key equations and to well-known Padé approximation problems, the SPI problem stands out in several respects. First, the SPI problem has a unique solution (up to a scale factor), which satisfies a natural degree bound. Second, the SPI problem can be transformed (monomialized) into an equivalent SPI problem where all moduli are monomials. Third, the SPI problem can be solved by an efficient algorithm of the Berlekamp–Massey type. Fourth, decoding interleaved Reed–Solomon codes (or subfield-evaluation codes) beyond half the minimum distance can be analyzed in terms of a partial-inverse condition for the error pattern: if that condition is satisfied, then the (true) error locator polynomial is the unique solution of a standard key equation and can be computed in many different ways, including the well-known multi-sequence Berlekamp–Massey algorithm and the SPI algorithm of this paper. Two of the best performance bounds from the literature (the Schmidt–Sidorenko–Bossert bound and the Roth–Vontobel bound) are generalized to hold for the partial-inverse condition and thus to apply to several different decoding algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we consider a three-terminal state-dependent relay channel (RC) with the channel state noncausally available at only the relay. Such a model may be useful for designing cooperative wireless networks with some terminals equipped with cognition capabilities, i.e., the relay in our setup. In the discrete memoryless (DM) case, we establish lower and upper bounds on channel capacity. The lower bound is obtained by a coding scheme at the relay that uses a combination of codeword splitting, Gel'fand-Pinsker binning, and decode-and-forward (DF) relaying. The upper bound improves upon that obtained by assuming that the channel state is available at the source, the relay, and the destination. For the Gaussian case, we also derive lower and upper bounds on the capacity. The lower bound is obtained by a coding scheme at the relay that uses a combination of codeword splitting, generalized dirty paper coding (DPC), and DF relaying; the upper bound is also better than that obtained by assuming that the channel state is available at the source, the relay, and the destination. In the case of degraded Gaussian channels, the lower bound meets with the upper bound for some special cases, and, so, the capacity is obtained for these cases. Furthermore, in the Gaussian case, we also extend the results to the case in which the relay operates in a half-duplex mode. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the notion of plausible deniability in an information theoretic framework. We consider a scenario where an entity that eavesdrops through a broadcast channel summons one of the parties in a communication protocol to reveal their message (or signal vector). It is desirable that the summoned party has enough freedom to produce a fake output that is likely plausible given the eavesdropper’s observation. We examine three variants of this problem—message deniability, transmitter deniability, and receiver deniability. In the first setting, the message sender is summoned to produce the sent message. Similarly, in the second and third settings, the transmitter and the receiver are required to produce the transmitted codeword and the received vector, respectively. For each of these settings, we examine the maximum communication rate that allows a given minimum rate of plausible fake outputs. First, for the message deniability problem, we fully characterize the capacity region for general broadcast channels. Next, for the transmitter deniability problem, we give an achievable region for general broadcast channels by fully characterizing the set of rate pairs’ achievable using deterministic coding schemes. Finally, for the receiver deniability problem, we give an achievable rate region for physically degraded broadcast channels. [ABSTRACT FROM AUTHOR]

The paper proposes Monte Carlo algorithms for the computation of the information rate of 2-D source/channel models. The focus of the paper is on binary-input channels with constraints on the allowed input configurations. The problem of numerically computing the information rate, and even the noiseless capacity, of such channels has so far remained largely unsolved. Both problems can be reduced to computing a Monte Carlo estimate of a partition function. The proposed algorithms use tree-based Gibbs sampling and multilayer (multitemperature) importance sampling. The viability of the proposed algorithms is demonstrated by simulation results. [ABSTRACT FROM AUTHOR]

Network navigation, encompassing both spatial and temporal cooperation to locate mobile agents, is a key enabler for numerous emerging location-based applications. In such cooperative networks, the positional information obtained by each agent is a complex compound due to the interaction among its neighbors. Thisinformation couplingmay result in poor performance: algorithms that discard information coupling are often inaccurate, and algorithms that keep track of all the neighbors’ interactions are often inefficient. In this paper, we develop a principled framework to characterize the information coupling present in network navigation. Specifically, we derive the equivalent Fisher information matrix for individual agents as the sum of effective information from each neighbor and the coupled information induced by the neighbors’ interaction. We further characterize how coupled information decays with the network distance in representative case studies. The results of this paper can offer guidelines for the development of distributed techniques that adequately account for information coupling, and hence enable accurate and efficient network navigation. [ABSTRACT FROM AUTHOR]

In this paper, the large family of generalized Kasami sequences has been studied. In particular, the cross-correlation distribution among these sequences has been explicitly calculated. Meanwhile, the weight distributions of two classes of cyclic codes could also be determined. This paper generalizes the results from several previous papers. [ABSTRACT FROM AUTHOR]

This paper studies the throughput-delay performance tradeoff in large-scale wireless ad hoc networks. It has been shown that the per source–destination pair throughput can be improved from \Theta (1/\sqrt n\log n) to \Theta (1) if nodes are allowed to move and a two-hop relay scheme is employed. The price paid for such a throughput improvement is large delay. Indeed, the delay scaling of the two-hop relay scheme is \Theta (n\log n) under the random walk mobility model. In this paper, coding techniques are used to improve the throughput-delay tradeoff for mobile wireless networks. For the random walk mobility model, the delay is reduced from \Theta (n\log n) to \Theta (n) by employing a maximum distance separable Reed–Solomon coding scheme. This coding approach maintains the diversity gained by mobility while decreasing the delay. [ABSTRACT FROM PUBLISHER]

In this paper, we consider a downlink communication system in which a base station (BS) equipped with M antennas and power constraint P communicates with N users each equipped with K receive antennas. It is assumed that the users have perfect channel state information (CSI) of their own channels, while the BS only knows the partial CSI provided by the receivers via a feedback channel. We study the fundamental limits on the amount of feedback required at the BS to achieve the sum-rate capacity of the system (when BS has perfect CSI for all users) in the asymptotic case of N \to \infty , considering various signal to noise ratio (SNR) regimes. The main results of this paper can be expressed as follows. 1) In the fixed-SNR regime (where the SNR does not scale with N) and low-SNR regime (where the SNR is much smaller than 1\over \ln (N)), to achieve the (1 - \varepsilon)-portion of the sum-rate capacity, the total amount of feedback should scale at least with \ln (\varepsilon ^-1). In the fixed-SNR regime, to reduce the gap between the achievable sum rate and the sum-rate capacity of the system (which is defined as the sum-rate gap) to zero, the amount of feedback should scale at least logarithmically with the sum-rate capacity, which is achievable by using the random beam-forming (RBF) scheme proposed by Sharif and Hassibi. In the low-SNR regime, we propose an opportunistic beam-forming (OBF) scheme, which is shown to be asymptotically feedback optimal. 2) In the high-SNR regime (where the SNR grows to infinity as N \to \infty ), the total amount of feedback depends on the number of receive antennas. In particular, to reduce the sum-rate gap to zero in the case of K < M, the amount of feedback in the SNR regime of \ln (P)\over \ln (N) > 1\over M-1, should scale at least logarithmically with the SNR. In the case of K \geq M, the amount of feedback does not need to scale with the SNR. Moreover, we show that RBF is asymptotically feedback optimal in the high-SNR regime. [ABSTRACT FROM AUTHOR]

Consider transmitting a set of information sources through a communication network that consists of a number of nodes. Between certain pair of nodes, there exist communication channels on which information can be transmitted. At a node, one or more information sources may be generated, and each of them is multicast to a set of destination nodes on the network. In this paper we study the problem of under what conditions a set of mutually independent information sources can be faithfully transmitted through a communication network; for which the connectivity among the nodes and the multicast requirements of the source information are arbitrary except that the connectivity does not form directed cycles. We obtain inner and outer bounds on the zero-error admissible coding rate region in term of the regions γ*[subN] and &γsline;*[subN], which are fundamental regions in the entropy space defined by Yeung. The results in this paper can be regarded as zero-error network coding theorems for acyclic communication networks. [ABSTRACT FROM AUTHOR]

Representing signals using coarsely quantized coefficients of redundant expansions is an interesting source coding paradigm, the most important practical case of which is oversampled analog-to-digital (A/D) conversion. Signal reconstruction from quantized redundant expansions and the accuracy of such representations are problems which are not well understood and we study them in this paper for uniform scalar quantization in finite-dimensional spaces. To give a more global perspective, we first present an analysis of the resilience of redundant expansions to degradation by additive noise in general, and then focus on the effects of uniform scalar quantization. The accuracy of signal representations obtained by applying uniform scalar quantization to coefficients of redundant expansions, measured as the mean-squared Euclidean norm of the reconstruction error, has been previously shown to be lower-bounded by an 1/r² expression. In this paper, we establish some general conditions under which the 1/r² accuracy can actually be attained, and under those conditions prove a 1/r² upper error bound. For a particular kind of structured expansions, which includes many popular frame classes, we propose reconstruction algorithms which attain the 1/r²2 accuracy at low numerical complexity. These structured expansions, moreover, facilitate efficient encoding of quantized coefficients in a manner which requires only a logarithmic bit-rate increase in redundancy, resulting in an exponential error decay in the bit rate. Results presented in this paper are immediately applicable to oversampled A/D conversion of periodic bandlimited signals. [ABSTRACT FROM AUTHOR]

A Write Once Memory (WOM) is a storage medium with binary memory elements, called cells, that can change from the zero state to the one state only once. Examples of WOMs include punch cards and optical disks. WOM-codes, introduced by Rivest and Shamir, permit the reuse of a WOM by taking into account the location of cells that have already been changed to the one state. The objective in designing WOM-codes is to use the fewest number of cells to store a specified number of information bits in each of several reuses of the memory. An [n,k,t] WOM-code \cal C is a coding scheme for storing k information bits in n cells t times. At each write, the state of each cell can be changed, provided that the cell is changed from the zero state to the one state. The rate of \cal C, defined by \cal R(\cal C)=kt/n, indicates the total amount of information that is possible to store in a cell in t writes. Two WOM-code constructions correcting a single cell-error were presented by Zémor and Cohen. In this paper, we present another construction of a single-error-correcting WOM-code with a better rate. Our construction can be adapted also for single-error-detection, double-error-correction, and triple-error-correction. For the last case, we use triple-error-correcting BCH-like codes, which were presented by Kasami and more recently described again by Bracken and Helleseth. Finally, we show two constructions that can be combined for the correction of an arbitrary number of errors. [ABSTRACT FROM AUTHOR]

In 2006, Helleseth and Kholosha conjectured and partially proved the existence of a class of ternary weakly regular monomial bent functions and also the expression for the dual bent function up to the sign value. The bentness was finally proved later in 2009 using a complicated technique that employs Stickelberger's theorem. Extensively using the previously found results and approaches, in this paper, a surprisingly short proof for the conjectured expression of the dual is given but without resolving the sign ambiguity. Furthermore, we resolve the sign by finding the trace representation of the dual function. [ABSTRACT FROM AUTHOR]

Scalar quantization is the most practical and straightforward approach to signal quantization. However, it has been shown that scalar quantization of oversampled or compressively sensed signals can be inefficient in terms of the rate-distortion tradeoff, especially as the oversampling rate or the sparsity of the signal increases. In this paper, we modify the scalar quantizer to have discontinuous quantization regions. We demonstrate that with this modification it is possible to achieve exponential decay of the quantization error as a function of the oversampling rate instead of the quadratic decay exhibited by current approaches. Our approach is universal in the sense that prior knowledge of the signal model is not necessary in the quantizer design, only in the reconstruction. Thus, we demonstrate that it is possible to reduce the quantization error by incorporating side information on the acquired signal, such as sparse signal models or signal similarity with known signals. In doing so, we establish a relationship between quantization performance and the Kolmogorov entropy of the signal model. [ABSTRACT FROM AUTHOR]

In this contribution, an algorithm for evaluating the capacity-achieving input covariance matrices for frequency selective Rayleigh MIMO channels is proposed. In contrast with the flat fading Rayleigh case, no closed-form expressions for the eigenvectors of the optimum input covariance matrix are available. Classically, both the eigenvectors and eigenvalues are computed numerically and the corresponding optimization algorithms remain computationally very demanding. In this paper, it is proposed to optimize (w.r.t. the input covariance matrix) a large system approximation of the average mutual information derived by Moustakas and Simon. The validity of this asymptotic approximation is clarified thanks to Gaussian large random matrices methods. It is shown that the approximation is a strictly concave function of the input covariance matrix and that the average mutual information evaluated at the argmax of the approximation is equal to the capacity of the channel up to a \cal O\left(1\over t\right) term, where t is the number of transmit antennas. An algorithm based on an iterative waterfilling scheme is proposed to maximize the average mutual information approximation, and its convergence studied. Numerical simulation results show that, even for a moderate number of transmit and receive antennas, the new approach provides the same results as direct maximization approaches of the average mutual information. [ABSTRACT FROM AUTHOR]

The paper investigates the mean-squared error (MSE) distortion of a variance-mismatched fixed-rate scalar quantizer that is optimal or asymptotically optimal in the minimum MSE sense for a Laplacian density with standard deviation \sigmaq but is applied to another with standard deviation \sigmap. A Nitadori-like formula is discovered for an optimal quantizer when \rho (\triangleq\sigmap/\sigmaq)=1/2. Also it is shown that the distortion expressions derived rigorously for asymptotically optimal quantile quantizers essentially confirm the heuristically obtained previous result that the distortion decreases as 1/ N^3/\rho for the heavy mismatch of \rho>3/ 2, as \ln N/ N^2 for the critical mismatch of \rho=3/2, and as 1/N^2 for the mild mismatch of \rho<3/2, where N is the number of quantization points. These asymptotic behaviors agree surprisingly well with Bennett's integral even in the critical and heavy mismatched cases. Thus, in the case of nonuniform quantizers, the long-conjectured convergence of the MSE distortion to zero at a rate other than 1/N^2 is confirmed rigorously. In addition, optimal uniform quantizers are found to be heavily mismatched when \rho>1 and the resulting distortion decreases as (\ln N/N^2)^1/\rho. [ABSTRACT FROM AUTHOR]

Multimedia fingerprinting is an effective technique to trace the sources of pirate copies of copyrighted multimedia information. AND anti-collusion codes can be used to construct fingerprints resistant to collusion attacks on multimedia contents. In this paper, we first investigate AND anti-collusion codes and related detection algorithms from a combinatorial viewpoint, and then introduce a new concept of logical anti-collusion code to improve the traceability of multimedia fingerprinting. It reveals that frameproof codes have traceability for multimedia contents. Relationships among anti-collusion codes and other structures related to fingerprinting are discussed, and constructions for both AND anti-collusion codes and logical anti-collusion codes are provided. [ABSTRACT FROM AUTHOR]

This paper is devoted to the design of precoders maximizing the ergodic mutual information (EMI) of bi-correlated flat fading MIMO systems equipped with MMSE receivers. The channel state information and the second-order statistics of the channel are assumed available at the receiver side and at the transmitter side respectively. As the direct maximization of the EMI needs the use of nonattractive algorithms, it is proposed to optimize an approximation of the EMI, introduced recently, obtained when the number of transmit and receive antennas t and r converge to \infty at the same rate. It is established that the relative error between the actual EMI and its approximation is a O( 1\over t^2) term. It is shown that the left singular eigenvectors of the optimum precoder coincide with the eigenvectors of the transmit covariance matrix, and its singular values are solution of a certain maximization problem. Numerical experiments show that the mutual information provided by this precoder is close from what is obtained by maximizing the true EMI, but that the algorithm maximizing the approximation is much less computationally intensive. [ABSTRACT FROM AUTHOR]

In this paper, a new construction of optimum sets of zero correlation zone (ZCZ) sequences, derived from generalized chirp-like (GCL) sequences, is presented. A special case with reduced alphabet size is also described. In a set of GCL-ZCZ sequences, the length of the zero correlation zone D has the maximum possible value D = T - 1 for a given sequence length N = tm and for a given number of sequences in the set M = m. Many values of N can be decomposed into multiple products of two positive integers, thus allowing for flexible tradeoff between the length of the ZCZ and the number of sequences in the set. As the set of GCL-ZCZ sequences is obtained by modulating a common "carrier" sequence with a set of orthogonal modulating sequences, there is a possibility for efficient implementation of the corresponding bank of matched filters. [ABSTRACT FROM AUTHOR]

This paper considers an entropy-power inequality (EPI) of Costa and presents a natural vector generalization with a real positive semidefinite matrix parameter. The new inequality is proved using a perturbation approach via a fundamental relationship between the derivative of mutual information and the minimum mean-square error (MMSE) estimate in linear vector Gaussian channels. As an application, a new extremal entropy inequality is derived from the generalized Costa EPI and then used to establish the secrecy capacity regions of the degraded vector Gaussian broadcast channel with layered confidential messages. [ABSTRACT FROM AUTHOR]

In this paper, for some linear block codes, two kinds of optimum distance profiles (ODPs) are introduced to consider how to construct and then exclude (or include) the basis codewords one by one while keeping a distance profile as large as possible in a dictionary order (or in an inverse dictionary order, respectively). The aim is to improve fault-tolerant capability by selecting subcodes in communications and storage systems. One application is to serve a suitable code for the realization of the transport format combination indicators (TFCIs) of code-division multiple-access (CDMA) systems. Another application is in the field of address retrieval on optical media. [ABSTRACT FROM AUTHOR]

This paper starts a systematic study of capacity-achieving (c.a.) sequences of low-density parity-check codes for the erasure channel. We introduce a class A of analytic functions and develop a procedure to obtain degree distributions for the codes. We show various properties of this class which will help us to construct new distributions from old ones. We then study certain types of capacity-achieving sequences and introduce new measures for their optimality. For instance, it turns out that the right-regular sequence is c.a. in a much stronger sense than, e.g., the Tornado sequence. This also explains why numerical optimization techniques tend to favor graphs with only one degree of check nodes. [ABSTRACT FROM AUTHOR]

The average conditional entropy of the key given the message and its corresponding cryptogram, H(K∣M, C), which is refer as a key appearance equivocation, was proposed as a theoretical measure of the strength of the cipher system under a known plaintext attack by Dunham in 1980. In the same work (among other things), lower and upper bounds for H(SM∣MLCL) are found and its asymptotic behavior as a function of cryptogram length L is described for simple substitution ciphers, i.e., when the key space SM is the symmetric group acting on a discrete alphabet M. In the present paper we consider the same problem when the key space is an arbitrary subgroup K ◁ SM and generalize Dunham's result. [ABSTRACT FROM AUTHOR]

We consider the problem of securing a multicast network against a wiretapper that can eavesdrop on the packets on a limited number of network edges of its choice. We assume that the network employs network coding to simultaneously deliver the packets available at the source to all the destinations. We show that this problem can be looked at as a network generalization of the wiretap channel of type II introduced in a seminal paper by Ozarow and Wyner. In particular, we show that the transmitted information can be secured by using the Ozarow–Wyner approach of coset coding at the source on top of the existing network code. This way, we quickly and transparently recover some of the results available in the literature on secure network coding for wiretap networks. Moreover, we use this framework to derive new bounds on the code alphabet size that are independent of the network size, and provide algorithms for explicit construction of secure network codes. We also analyze the amount of information that can be leaked to the wiretapper as a function of the number of wiretapped edges. [ABSTRACT FROM AUTHOR]

This paper studies communication outages in multiple-input multiple-output (MIMO) block-fading channels with imperfect channel state information at the receiver (CSIR). Using mismatched decoding error exponents, we prove the achievability of the generalized outage probability, the probability that the generalized mutual information (GMI) is less than the data rate, and show that this probability is the fundamental limit for independent and identically distributed (i.i.d.) codebooks. Then, using nearest neighbor decoding, we study the generalized outage probability in the high signal-to-noise ratio (SNR) regime for random codes with Gaussian and discrete signal constellations. In particular, we study the SNR exponent, which is defined as the high-SNR slope of the error probability curve on a logarithmic-logarithmic scale. We show that the maximum achievable SNR exponent of the imperfect CSIR case is given by the SNR exponent of the perfect CSIR case times the minimum of one and the channel estimation error diversity. Random codes with Gaussian constellations achieve the optimal SNR exponent with finite block length as long as the block length is larger than a threshold. On the other hand, random codes with discrete constellations achieve the optimal SNR exponent with block length growing with the logarithm of the SNR. The results hold for many fading distributions, including Rayleigh, Rician, Nakagami-m, Nakagami-q and Weibull as well as for optical wireless scintillation distributions such as lognormal-Rice and gamma-gamma. [ABSTRACT FROM AUTHOR]

Due to the large size of wireless networks, it is often impractical for nodes to track changes in the complete network state. As a result, nodes have to make distributed decisions about their transmission and reception parameters based on their local view of the network. In this paper, we characterize the impact of distributed decisions on the global network performance in terms of achievable sum rates. We first formalize the concept of local view by proposing a protocol abstraction using the concept of local message passing. In the proposed protocol, nodes forward information about the network state to other neighboring nodes, thereby allowing network-state information to trickle to all the nodes. The protocol proceeds in rounds, where all transmitters send a message followed by a message by all receivers. The number of rounds then provides a natural metric to quantify the extent of local information at each node. We next study two network connectivities, Z-channel, and a three-user double Z-channel. In each case, we characterize achievable sum rate with partial message passing leading to two main results. First, in many cases, nodes can make distributed decisions with only local information about the network and can still achieve the same sum capacity as can be attained with global information irrespective of the actual channel gains. We label such schemes as universally optimal. Second, for the case of three-user double Z-channel, we show that universal optimality is not achievable if the per node information is below a threshold. In fact, distributed decisions can lead to unbounded losses compared to full information case for some channel gains. [ABSTRACT FROM AUTHOR]

In this paper, we consider completely regular codes, obtained from perfect (Hamming) codes by lifting the ground field. More exactly, for a given Hamming code C of length n=(q^m-1)/(q-1) over \BBF_q with a parity check matrix H_m, we define a new linear code C(m,r) of length n over \BBFq^r, r \geq 2, with this parity check matrix H_m. The resulting code C(m,r) is completely regular with covering radius \rho = \min\r,m\. We compute the intersection numbers of such codes and we prove that Hamming codes are the only codes that, after lifting the ground field, result in completely regular codes. Finally, we also prove that extended perfect (Hamming) codes, for the case when extension increases their minimum distance, are the only codes that, after lifting the ground field, result in uniformly packed (in the wide sense) codes. [ABSTRACT FROM AUTHOR]

The complete complementary code (CCC) that was proposed by Suehiro and Hatori is a sequence family, that is a set of sequence sets, with ideal correlation sums. Numerous studies in the literature show its applications to direct-spread code-division multiple access (DS-CDMA) systems for interchannel interference (ICI)-free communication with improved spectral efficiency. In this paper, we propose a systematic framework for the construction of CCCs based on N-shift cross-orthogonal sequence families (N\-CO\-SFs). We show theoretical bounds on the size of N\-CO\-SFs and CCCs and give a set of four algorithms for their generation and extension. The algorithms are optimal in the sense that the size of the resultant sequence families achieves theoretical bounds and, with the algorithms, we can construct an optimal CCC consisting of sequences whose lengths are not only almost arbitrary but even variable between sequence sets. We also discuss the family size, alphabet size, and length of constructible CCCs based on the proposed algorithms. [ABSTRACT FROM AUTHOR]

The problem of broadcasting a parallel Gaussian source over an additive white Gaussian noise broadcast channel under the mean-squared error distortion criterion is studied. A hybrid digital-analog coding strategy which combines source coding with side information, channel coding with side information, layered source coding, and superposition broadcast channel coding is presented. When specialized to the open problem of broadcasting a white Gaussian source over an additive white Gaussian noise broadcast channel with bandwidth mismatch, which has been the subject of several previous investigations, this coding scheme strictly improves on the state of the art. [ABSTRACT FROM AUTHOR]

The problem of finding the rate-distortion function of an arbitrarily varying source (AVS) composed of a finite number of memoryless subsources is revisited. Berger's 1971 paper “The Source Coding Game” solves this problem when the adversary is allowed only strictly causal access to the subsource realizations. The case when the adversary has access to the subsource realizations non-causally is considered. This new rate-distortion function is determined to be the maximum of the rate-distortion function over a set of independent and identically distributed (IID) random variables that can be simulated by the adversary. The results are extended to allow for partial or noisy observations of subsource realizations. The model is further explored by attempting to find the rate-distortion function when the ‘adversary’ is actually helpful. Finally, a bound is developed on the uniform continuity of the IID rate-distortion function for finite-alphabet sources. The bound is used to give a sufficient number of distributions that need to be sampled to compute the rate-distortion function of an AVS to within a desired accuracy. The bound is also used to give a rate of convergence for the estimate of the rate-distortion function for an unknown IID source. [ABSTRACT FROM AUTHOR]

A relatively new model of error correction is the limited magnitude error model. That is, it is assumed that the absolute difference between the sent and received symbols is bounded above by a certain value l. In this paper, we propose systematic codes for asymmetric limited magnitude channels that are able to correct a single error. We also show how this construction can be slightly modified to design codes that can correct a single symmetric error of limited magnitude. The designed codes achieve higher code rates than single error correcting codes previously given in the literature. [ABSTRACT FROM AUTHOR]

This paper shows that Corollary 1 of “On Multiple Linear Approximations” is incorrect. In particular, the value given for the gain by Corollary 1 is likely to be a significant overestimate of this quantity. Thus, any data requirements for linear cryptanalysis with multiple linear approximations based on this value for the gain are highly questionable. [ABSTRACT FROM AUTHOR]

In this paper, we study the question of the representation of random variables by means of frames or Riesz basis generated by stationary sequences. This concerns the representation of continuous time wide sense stationary random processes by means of discrete samples. [ABSTRACT FROM AUTHOR]

Consider the scenario where we are given an ideal functionality of oblivious transfer (OT), and we wish to construct a larger OT by invoking the above functionality as a black box. How many invocations of an ideal OT functionality are necessary? In tackling this problem, some lower bounds were derived using entropy previously. In this paper, we manage to achieve tighter lower bounds by employing a combinatorial approach. This new approach yields lower bounds which are two times larger than the existing bounds. [ABSTRACT FROM AUTHOR]

In this paper, a novel approach is proposed for estimating traffic matrices. Our method, called PamTram for PArtial Measurement of TRAffic Matrices, couples lightweight origin-destination (OD) flow measurements along with a computationally lightweight algorithm for producing OD estimates. The first key aspect of our method is to actively select a small number of informative OD flows to measure in each estimation interval. To avoid the heavy computation of optimal selection, we use intuition from game theory to develop randomized selection rules, with the goals of reducing errors and adapting to traffic changes. We show that it is sufficient to measure only one flow per measurement period to drastically reduce errors⪢thus rendering our method lightweight in terms of measurement overhead. The second key aspect is an explanation and proof that an Iterative Proportional Fitting algorithm approximates traffic matrix estimates when the goal is a minimum mean-squared error; this makes our method lightweight in terms of computation overhead. A one-step error bound is provided for PamTram that bounds the average error for the worst scenario. We validate our method using data from Sprint's European Tier-1 IP backbone network and demonstrate its consistent improvement over previous methods. [ABSTRACT FROM AUTHOR]

The paper develops a systematic framework for designing a stochastic location detection system with associated performance guarantees using a wireless sensor network. To detect the location of a mobile sensor, the system relies on RF-characteristics of the signal transmitted by the mobile sensor, as it is received by stationary sensors (clusterheads). Location detection is posed as a hypothesis testing problem over a discretized space. Large deviations results enable the characterization of the probability of error leading to a placement problem that maximizes an information-theoretic distance (Chernoff distance) among all pairs of probability distributions of observations conditional on the sensor locations. The placement problem is shown to be NP-hard and is formulated as a linear integer programming problem; yet, large instances can be solved efficiently by leveraging special-purpose algorithms from the theory of discrete facility location. The resultant optimal placement is shown to provide asymptotic guarantees on the probability of error in location detection under quite general conditions by minimizing an upper bound of the error-exponent. Numerical results show that the proposed framework is computationally feasible and the resultant clusterhead placement performs near-optimal even with a small number of observation samples in a simulation environment. [ABSTRACT FROM AUTHOR]

LT-codes are a new class of codes introduced by Luby for the purpose of scalable and fault-tolerant distribution of data over computer networks. In this paper, we introduce Raptor codes, an extension of LT-codes with linear time encoding and decoding. We will exhibit a class of universal Raptor codes: for a given integer k and any real ϵ > 0, Raptor codes in this class produce a potentially infinite stream of symbols such that any subset of symbols of size k(1 + ϵ) is sufficient to recover the original k symbols with high probability. Each output symbol is generated using O(log(1/ϵ)) operations, and the original symbols are recovered from the collected ones with O(k log(1/ϵ)) operations. We will also introduce novel techniques for the analysis of the error probability of the decoder for finite length Raptor codes. Moreover, we will introduce and analyze systematic versions of Raptor codes, i.e., versions in which the first output elements of the coding system coincide with the original k elements. [ABSTRACT FROM AUTHOR]

Gupta and Kumar (2000) introduced a random model to study throughput scaling in a wireless network with static nodes, and showed that the throughput per source-destination pair is Θ (1/√n log n). Grossglauser and Tse (2001) showed that when nodes are mobile it is possible to have a constant throughput scaling per source-destination pair. In most applications, delay is also a key metric of network performance. It is expected that high throughput is achieved at the cost of high delay and that one can be improved at the cost of the other. The focus of this paper is on studying this tradeoff for wireless networks in a general framework. Optimal throughput-delay scaling laws for static and mobile wireless networks are established. For static networks, it is shown that the optimal throughput-delay tradeoff is given by D(n) = Θ (nT(n) ), where T(n) and D(n) are the throughput and delay scaling, respectively. For mobile networks, a simple proof of the throughput scaling of Θ (1) for the Grossglauser-Tse scheme is given and the associated delay scaling is shown to be Θ(n log n). The optimal throughput--delay tradeoff for mobile networks is also established. To capture physical movement in the real world, a random-walk (RW) model for node mobility is assumed. It is shown that for throughput of O (1/√n log n), which can also be achieved in static networks, the throughput-delay tradeoff is the same as in static networks, i.e., D (n) = Θ(nT(n)). Surprisingly, for almost any throughput of a higher order, the delay is shown to be Θ (n log n), which is the delay for throughput of Θ (1). Our result, thus, suggests that the use of mobility to increase throughput, even slightly, in real-world networks would necessitate an abrupt and very large increase in delay. [ABSTRACT FROM AUTHOR]

In recent years there Ires been renewed interest in deriving tight bounds on the error performance of specific codes and ensembles, based on their distance spectrum. In this paper, we discuss many reported upper bounds on the maximum-likelihood (ML) decoding error probability and demonstrate the underlying connections that exist between them. In addressing the Gallager bounds and their variations, we focus on the Duman and Salehi variation, which originates from the standard Gallager bound. A large class of efficient recent bounds (or their Chernoff versions) is demonstrated to be a special case of the generalized second version of the Damon and Salehi bounds. Implications and applications of these observations are pointed out, including the fully interleaved fading channel, resorting to either matched or mismatched decoding. The proposed approach can be generalized to geometrically uniform nonbinary codes, finite-state channels, bit interleaved coded modulation systems, and it can be also used for the derivation of upper bounds on the conditional decoding error probability. [ABSTRACT FROM AUTHOR]

Two sets of 0–1 vectors of fixed length form a uniquely decodeable code pair if their Cartesian product is of the same size as their sumset, where the addition is pointwise over integers. For the size of the sumset of such a pair, van Tilborg has given an upper bound in the general case. Urbanke and Li, and later Ordentlich and Shayevitz, have given better bounds in the unbalanced case, that is, when either of the two sets is sufficiently large. Improvements to the latter bounds are presented. [ABSTRACT FROM AUTHOR]

In the paper above [1], published in the March 2017 issue of the IEEE Transactions on Information Theory, the following changes are noted. •

In the Abstract, page 1349, left column, line 3, “using square-integrable and bandlimited signals” should be replaced by “using square-integrable, bandlimited signals.” [ABSTRACT FROM AUTHOR]

An encoder, subject to a rate constraint, wishes to describe a Gaussian source under squared-error distortion. The decoder, besides receiving the encoder's description, also observes side information consisting of uncompressed source symbol subject to slow fading and noise. The decoder knows the fading realization but the encoder knows only its distribution. The rate-distortion function that simultaneously satisfies the distortion constraints for all fading states was derived by Heegard and Berger. A layered encoding strategy is considered in which each codeword layer targets a given fading state. When the side-information channel has two discrete fading states, the expected distortion is minimized by optimally allocating the encoding rate between the two codeword layers. For multiple fading states, the minimum expected distortion is formulated as the solution of a convex optimization problem with linearly many variables and constraints. Through a limiting process on the primal and dual solutions, it is shown that single-layer rate allocation is optimal when the fading probability density function is continuous and quasiconcave (e.g., Rayleigh, Rician, Nakagami, and log-normal). In particular, under Rayleigh fading, the optimal single codeword layer targets the least favorable state as if the side information was absent. [ABSTRACT FROM AUTHOR]

We study the half-duplex multiple-relay channel (HD-MRC) where every node can either transmit or listen but cannot do both at the same time. We obtain a capacity upper bound based on a max-flow min-cut argument and achievable transmission rates based on the decode-forward (DF) coding strategy, for both the discrete memoryless HD-MRC and the phase-fading HD-MRC. We discover that both the upper bound and the achievable rates are functions of the transmit/listen state (a description of which nodes transmit and which receive). More precisely, they are functions of the time fraction of the different states, which we term a schedule. We formulate the optimal scheduling problem to find an optimal schedule that maximizes the DF rate. The optimal scheduling problem turns out to be a maximin optimization, for which we propose an algorithmic solution. We demonstrate our approach on a four-node multiple-relay channel, obtaining closed-form solutions in certain scenarios. Furthermore, we show that for the received signal-to-noise ratio degraded phase-fading HD-MRC, the optimal scheduling problem can be simplified to a max optimization. [ABSTRACT FROM AUTHOR]

We consider the problem of bounding the information rate of intersymbol interference channels via simulation-based algorithms. The adopted approach, which is based on a general class of reduced-complexity receivers that includes several previously studied receivers as special cases, leads to provable upper and lower bounds on the information rate of interest. As a by-product of the information-theoretic investigations, novel insights on the design of efficient reduced-complexity receivers are also provided, since the proposed lower bounds are known to be achievable by practical receivers. In many scenarios, our novel approach significantly outperforms the existing ones, for all practical values of the signal-to-noise ratio. [ABSTRACT FROM AUTHOR]

Let X be a nonnegative random variable and let the conditional distribution of a random variable Y, given X, be Poisson (\gamma\cdot X), for a parameter \gamma\geq 0. We identify a natural loss function such that: 1) the derivative of the mutual information between X and Y with respect to \gamma is equal to the minimum mean loss in estimating X based on Y, regardless of the distribution of X; 2) when X\sim P is estimated based on Y by a mismatched estimator that would have minimized the expected loss had X\sim Q, the integral over all values of \gamma of the excess mean loss is equal to the relative entropy between P and Q. For a continuous time setting where X is a nonnegative stochastic process and the conditional law of Y, given X, is that of a non-homogeneous Poisson process with intensity function \gamma\cdot X, under the same loss function: 1) the minimum mean loss in causal filtering when \gamma=\gamma0 is equal to the expected value of the minimum mean loss in noncausal filtering (smoothing) achieved with a channel whose parameter \gamma is uniformly distributed between 0 and \gamma0. Bridging the two quantities is the mutual information between X and Y; 2) this relationship between the mean losses in causal and noncausal filtering holds also in the case where the filters employed are mismatched, i.e., optimized assuming a law on X which is not the true one. Bridging the two quantities in this case is the sum of the mutual information and the relative entropy between the true and the mismatched distribution of Y. Thus, relative entropy quantifies the excess estimation loss due to mismatch in this setting. These results are parallel to those recently found for the Gaussian channel: the I-MMSE relationship of Guo , the relative entropy and mismatched estimation relationship of Verdú, and the relationship between causal and noncasual mismatched estimation of Weissman. [ABSTRACT FROM AUTHOR]

In addition to exploring its various regularity properties, we show that the minimum mean-square error (MMSE) is a concave functional of the input–output joint distribution. In the case of additive Gaussian noise, the MMSE is shown to be weakly continuous in the input distribution and Lipschitz continuous with respect to the quadratic Wasserstein distance for peak-limited inputs. Regularity properties of mutual information are also obtained. Several applications to information theory and the central limit theorem are discussed. [ABSTRACT FROM AUTHOR]

We investigate the capacity of a multiple access channel with cooperating encoders where partial state information is known to each encoder and full state information is known to the decoder. The cooperation between the encoders has a two-fold purpose: to generate empirical state coordination between the encoders, and to share information about the private messages that each encoder has. For two-way cooperation, this two-fold purpose is achieved by double-binning, where the first layer of binning is used to generate the state coordination similarly to the two-way source coding, and the second layer of binning is used to transmit information about the private messages. The complete result provides the framework and perspective for addressing a complex level of cooperation that mixes states and messages in an optimal way. [ABSTRACT FROM AUTHOR]

We consider linear time-varying channels with additive white Gaussian noise. For a large class of such channels we derive rigorous estimates of the eigenvalues of the correlation matrix of the effective channel in terms of the sampled time-varying transfer function and, thus, provide a theoretical justification for a relationship that has been frequently observed in the literature. We then use this eigenvalue estimate to derive an estimate of the mutual information of the channel. Our approach is constructive and is based on a careful balance of the tradeoff between approximate operator diagonalization, signal dimension loss, and accuracy of eigenvalue estimates. [ABSTRACT FROM AUTHOR]

Different types of convolution operations involving large Vandermonde matrices are considered. The convolutions parallel those of large Gaussian matrices and additive and multiplicative free convolution, and include additive and multiplicative convolution of Vandermonde matrices and deterministic diagonal matrices, and cases where two independent Vandermonde matrices are involved. It is also shown that the convergence of any combination of Vandermonde matrices is almost sure. The convolutions are divided into two types: those which depend on the phase distribution of the Vandermonde matrices, and those which depend only on the spectra of the matrices. A general criterion is presented to find which type applies for any given convolution. A simulation is presented, verifying the results. Implementations of the presented convolutions are provided and discussed. The implementation is based on the technique of Fourier-Motzkin elimination, and is quite general as it can be applied to virtually any combination of Vandermonde matrices. Connections with related matrices, such as Toeplitz and Hankel matrices, are also discussed. [ABSTRACT FROM AUTHOR]