Search

As an optimal combinatorial object, zero-difference balanced (ZDB) functions introduced by Ding in 2008, are a generalization of the well-known perfect nonlinear functions. ZDB functions have received much attention in recent years due to its important applications in coding theory and sequence design. One objective of this paper is to present a construction of ZDB functions based on a kind of generalized cyclotomy. It generates ZDB functions over cyclic group with new parameters which can not be produced by earlier constructions. Another objective of this paper is to employ these ZDB functions to obtain at the same time: 1) optimal constant-composition codes; 2) perfect difference systems of sets; and 3) optimal frequency-hopping sequences, all with new parameters. [ABSTRACT FROM PUBLISHER]

Volume estimates of metric balls in manifolds find diverse applications in information and coding theory. In this paper, new results for the volume of a metric ball in unitary group are derived via tools from random matrix theory. The first result is an integral representation of the exact volume, which involves a Toeplitz determinant of Bessel functions. A simple but accurate limiting volume formula is then obtained by invoking Szegő’s strong limit theorem for large Toeplitz matrices. The derived asymptotic volume formula enables analytical evaluation of some coding-theoretic bounds of unitary codes. In particular, the Gilbert–Varshamov lower bound and the Hamming upper bound on the cardinality as well as the resulting bounds on code rate and minimum distance are derived. Moreover, bounds on the scaling law of code rate are found. Finally, a closed-form bound on the diversity sum relevant to unitary space-time codes is obtained, which was only computed numerically in the literature. [ABSTRACT FROM AUTHOR]

This paper is about deriving lower bounds on the error exponents for the two-user interference channel under the random coding regime for several ensembles. Specifically, we first analyze the standard random coding ensemble, where the codebooks are comprised of independently and identically distributed (i.i.d.) codewords. For this ensemble, we focus on optimum decoding, which is in contrast to other, suboptimal decoding rules that have been used in the literature (e.g., joint typicality decoding, treating interference as noise, and so on). The fact that the interfering signal is a codeword, rather than an i.i.d. noise process, complicates the application of conventional techniques of performance analysis of the optimum decoder. In addition, unfortunately, these conventional techniques result in loose bounds. Using analytical tools rooted in statistical physics, as well as advanced union bounds, we derive single-letter formulas for the random coding error exponents. We compare our results with the best known lower bound on the error exponent, and show that our exponents can be strictly better. Then, in the second part of this paper, we consider more complicated coding ensembles and find a lower bound on the error exponent associated with the celebrated Han–Kobayashi random coding ensemble, which is based on superposition coding. [ABSTRACT FROM AUTHOR]

This paper investigates the compress-and-forward scheme for an uplink cloud radio access network (C-RAN) model, where multi-antenna base stations (BSs) are connected to a cloud-computing-based central processor (CP) via capacity-limited fronthaul links. The BSs compress the received signals with Wyner-Ziv coding and send the representation bits to the CP; the CP performs the decoding of all the users’ messages. Under this setup, this paper makes progress toward the optimal structure of the fronthaul compression and CP decoding strategies for the compress-and-forward scheme in the C-RAN. On the CP decoding strategy design, this paper shows that under a sum fronthaul capacity constraint, a generalized successive decoding strategy of the quantization and user message codewords that allows arbitrary interleaved order at the CP achieves the same rate region as the optimal joint decoding. Furthermore, it is shown that a practical strategy of successively decoding the quantization codewords first, then the user messages, achieves the same maximum sum rate as joint decoding under individual fronthaul constraints. On the joint optimization of user transmission and BS quantization strategies, this paper shows that if the input distributions are assumed to be Gaussian, then under joint decoding, the optimal quantization scheme for maximizing the achievable rate region is Gaussian. Moreover, Gaussian input and Gaussian quantization with joint decoding achieve to within a constant gap of the capacity region of the Gaussian multiple-input multiple-output (MIMO) uplink C-RAN model. Finally, this paper addresses the computational aspect of optimizing uplink MIMO C-RAN by showing that under fixed Gaussian input, the sum rate maximization problem over the Gaussian quantization noise covariance matrices can be formulated as convex optimization problems, thereby facilitating its efficient solution. [ABSTRACT FROM PUBLISHER]

The state-dependent point-to-point Gaussian channel with a helper is first studied, in which a transmitter communicates with a receiver via a state-corrupted channel. The state is not known to the transmitter nor to the receiver, but known to a helper noncausally, which then wishes to assist the receiver to cancel the state. Differently from the previous work that characterized the capacity only in the infinite state power regime, this paper explores the general case with arbitrary state power. A lower bound on the capacity is derived based on an achievable scheme that integrates direct state subtraction and single-bin dirty paper coding. By analyzing this lower bound and further comparing it with the existing upper bounds, the capacity of the channel is characterized for a wide range of channel parameters. Such an idea of characterizing the capacity is further extended to study the two-user state-dependent multiple access channel with a helper. By comparing the derived inner and outer bounds, the channel parameters are partitioned into appropriate cases, and for each case, either segments on the capacity region boundary or the full capacity region are characterized. [ABSTRACT FROM PUBLISHER]

A classical method of constructing a linear code over \mathrm GF(q) with a $t$ -design is to use the incidence matrix of the $t$ -design as a generator matrix over \mathrm GF(q) of the code. This approach has been extensively investigated in the literature. In this paper, a different method of constructing linear codes using specific classes of 2-designs is studied, and linear codes with a few weights are obtained from almost difference sets, difference sets, and a type of 2-designs associated to semibent functions. Two families of the codes obtained in this paper are optimal. The linear codes presented in this paper have applications in secret sharing and authentication schemes, in addition to their applications in consumer electronics, communication and data storage systems. A coding-theory approach to the characterization of highly nonlinear Boolean functions is presented. [ABSTRACT FROM AUTHOR]

For an odd prime \(p\) and two positive integers \(m\) , \(k\) such that \(m/\gcd (k,m)\geq 3\) is odd, let \(d\) be a positive integer satisfying \(d(p^{k}+1)\equiv 2\,({\rm mod}\,p^{m}-1)\) . In this paper, the cross-correlation between a \(p\) -ary \(m\) -sequence and its \(d\) -decimated sequences is investigated, and the cross correlation distribution is completely determined. The relationship between the decimations \(d\) considered in this paper and some known ones is also studied. This paper generalizes some previous results, and also gives new decimations, which lead to low cross correlation. [ABSTRACT FROM PUBLISHER]

These instructions give guidelines for preparing papers for this publication. Presents information for authors publishing in this journal. [ABSTRACT FROM AUTHOR]

These instructions give guidelines for preparing papers for this publication. Presents information for authors publishing in this journal. [ABSTRACT FROM AUTHOR]

These instructions give guidelines for preparing papers for this publication. Presents information for authors publishing in this journal. [ABSTRACT FROM AUTHOR]

The article talks about the Institute of Electricals and Electronics Engineers (IEEE) transactions on Information theory information for authors. Topics include the thory publishing theoretical and experimental papers concerned with the transmission, processing, and utilization of information; preparation of Manuscripts; and supplementary material along with the graphical abstract for the same.

These instructions give guidelines for preparing papers for this publication. Presents information for authors publishing in this journal. [ABSTRACT FROM AUTHOR]

The article offers information on preparation of manuscripts, graphical abstract, and open access related to the periodical.

In prior work, we have shown how the basic concepts and terms of quantum mechanics relate to factorizations and marginals of complex-valued quantum mass functions, which are generalizations of joint probability mass functions. In this paper, using quantum mass functions, we discuss the realization of measurements in terms of unitary interactions and marginalizations. It follows that classical measurement results strictly belong to local models, i.e., marginals of more detailed models. Classical variables that are created by marginalization do not exist in the unmarginalized model, and different marginalizations may yield incompatible classical variables. These observations are illustrated by the Frauchiger–Renner paradox, which is analyzed (and resolved) in terms of quantum mass functions. Throughout, the paper uses factor graphs to represent quantum systems/models with multiple measurements at different points in time. [ABSTRACT FROM AUTHOR]

We consider the problem of massive matrix multiplication, which underlies many data analytic applications, in a large-scale distributed system comprising a group of worker nodes. We target the stragglers’ delay performance bottleneck, which is due to the unpredictable latency in waiting for slowest nodes (or stragglers) to finish their tasks. We propose a novel coding strategy, named entangled polynomial code, for designing the intermediate computations at the worker nodes in order to minimize the recovery threshold (i.e., the number of workers that we need to wait for in order to compute the final output). We demonstrate the optimality of entangled polynomial code in several cases, and show that it provides orderwise improvement over the conventional schemes for straggler mitigation. Furthermore, we characterize the optimal recovery threshold among all linear coding strategies within a factor of 2 using bilinear complexity, by developing an improved version of the entangled polynomial code. In particular, while evaluating bilinear complexity is a well-known challenging problem, we show that optimal recovery threshold for linear coding strategies can be approximated within a factor of 2 of this fundamental quantity. On the other hand, the improved version of the entangled polynomial code enables further and orderwise reduction in the recovery threshold, compared to its basic version. Finally, we show that the techniques developed in this paper can also be extended to several other problems such as coded convolution and fault-tolerant computing, leading to tight characterizations. [ABSTRACT FROM AUTHOR]

Randomness extraction against side information is the art of distilling from a given source a key which is almost uniform conditioned on the side information. This paper provides randomness extraction against quantum side information whose extractable key length is given by a quantum generalization of the collision entropy, which is smoothed and conditioned differently from how this is done in existing schemes. Based on the fact that the collision entropy is not subadditive, its optimization with respect to additional side information is introduced, and is shown to be asymptotically optimal. The lower bound derived there for general states is expressed as the difference between two unconditional entropies and its evaluation reduces to an eigenvalue problem of two states, which are the entire state and the marginal state of side information. [ABSTRACT FROM AUTHOR]

In the classical model for (information theoretically secure) Private Information Retrieval (PIR) due to Chor, Goldreich, Kushilevitz and Sudan, a user wishes to retrieve one bit of a database that is stored on a set of ${n}$ servers, in such a way that no individual server gains information about which bit the user is interested in. The aim is to design schemes that minimise the total communication between the user and the servers. More recently, there have been moves to consider more realistic models where the total storage of the set of servers, or the per server storage, should be minimised (possibly using techniques from distributed storage), and where the database is divided into ${R}$ -bit records with ${R}>1$ , and the user wishes to retrieve one record rather than one bit. When ${R}$ is large, downloads from the servers to the user dominate the communication complexity and so the aim is to minimise the total number of downloaded bits. Work of Shah, Rashmi and Ramchandran shows that at least ${R}+1$ bits must be downloaded from servers in the worst case, and provides PIR schemes meeting this bound. Sun and Jafar have considered the download cost of a scheme, defined as the ratio of the message length ${R}$ and the total number of bits downloaded. They determine the best asymptotic download cost of a PIR scheme (as ${R}\rightarrow \infty $) when a database of ${k}$ messages is stored by ${n}$ servers. This paper provides various bounds on the download complexity of a PIR scheme, generalising those of Shah et al. to the case when the number ${n}$ of servers is bounded, and providing links with classical techniques due to Chor et al. The paper also provides a range of constructions for PIR schemes that are either simpler or perform better than previously known schemes. These constructions include explicit schemes that achieve the best asymptotic download complexity of Sun and Jafar with significantly lower upload complexity, and general techniques for constructing a scheme with good worst case download complexity from a scheme with good download complexity on average. [ABSTRACT FROM AUTHOR]

The article offers information related to supplementary material, preparation of manuscripts, and open access for the authors of the periodical.

Content delivery networks store information distributed across multiple servers, so as to balance the load and avoid unrecoverable losses in case of node or disk failures. Coded caching has been shown to be a useful technique which can reduce peak traffic rates by pre-fetching popular content at the end users and encoding transmissions so that different users can extract different information from the same packet. On one hand, distributed storage limits the capability of combining content from different servers into a single message, causing performance losses in coded caching schemes. But, on the other hand, the inherent redundancy existing in distributed storage systems can be used to improve the performance of those schemes through parallelism. This paper designs coded caching and delivery schemes tailored towards systems where the library is distributed across multiple servers, possibly with some redundancy in the form of maximum distance separable (MDS) erasure codes. Different schemes are proposed based on the capacity of the users’ caches, as well as the number of parity servers. The main focus is on scenarios with one (RAID-4) or two (RAID-6) parity servers, but the paper also includes simple extensions for cases with more than two or no parity servers at all. The proposed schemes are shown to reduce the worst case latency, or equivalently the peak transmission rate from any server, below that of state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]

This paper studies the low-SNR regime performance of a scalar complex $K$ -user interference channel with the Gaussian noise. The finite bandwidth case is considered, where the low-SNR regime is approached by letting the input power go to zero, while the bandwidth is small and fixed. We show that for all $\delta >0$ , there exists a set of channel coefficients with non-zero measure (probability), in which the wideband slope per user satisfies $ \mathcal {S}_{0}< {\scriptstyle {}^{\scriptstyle 2}}\hspace{-0.224em}/\hspace{-0.112em}{\scriptstyle K}+\delta $. This is quite contrary to the large bandwidth case, where a slope of 1 per user is achievable with probability 1. We also develop an interference alignment scheme for the finite bandwidth case that shows some gain in wideband slope. [ABSTRACT FROM AUTHOR]

An additive white Gaussian noise energy-harvesting channel with an infinite-sized battery is considered. The energy arrival process is modeled as a sequence of independent and identically distributed random variables. The channel capacity $\frac {1}{2}\log (1+P)$ is achievable by the so-called best-effort and save-and-transmit schemes where $P$ denotes the battery recharge rate. This paper analyzes the save-and-transmit scheme whose transmit power is strictly less than $P$ and the best-effort scheme as a special case of save-and-transmit without a saving phase. In the finite blocklength regime, we obtain new non-asymptotic achievable rates for these schemes that approach the capacity with gaps vanishing at rates proportional to $1/\sqrt {n}$ and $({(\log n)/n})^{1/2}$ respectively where $n$ denotes the blocklength. The proof technique involves analyzing the escape probability of a Markov process. When $P$ is sufficiently large, we show that allowing the transmit power to back off from $P$ can improve the performance for save-and-transmit. The results are extended to a block energy arrival model where the length of each energy block $L$ grows sublinearly in $n$. We show that the save-and-transmit and best-effort schemes achieve coding rates that approach the capacity with gaps vanishing at rates proportional to $\sqrt {L/n}$ and $({\max \{\log n, L\}/n})^{1/2}$ , respectively. [ABSTRACT FROM AUTHOR]

We investigate a probabilistic model for routeing in a multihop ad hoc communication network, where each user sends a message to the base station. Messages travel in hops via other users, used as relays. Their trajectories are chosen at random according to a Gibbs distribution, which favors trajectories with low interference, measured in terms of signal-to-interference ratio. This model was introduced in our earlier paper, where we expressed, in the limit of a high density of users, the typical distribution of the family of trajectories in terms of a law of large numbers. In this paper, we derive its qualitative properties. We analytically identify the emerging typical scenarios in three extreme regimes. We analyze the typical number of hops and the typical length of a hop and the deviation of the trajectory from the straight line, regime 1 in the limit of a large communication area and large distances and regime 2 in the limit of a strong interference weight. In both the regimes, the typical trajectory approaches a straight line quickly, in regime 1 with equal hop lengths. Interestingly, in regime 2, the typical length of a hop diverges logarithmically in the distance of the transmitter to the base station. We further analyze (regime 3) local and global repulsive effects of a densely populated subarea on the trajectories. [ABSTRACT FROM AUTHOR]

Locally repairable codes have been investigated extensively in recent years due to practical applications in distributed storage as well as theoretical interest. However, not much work on asymptotical behavior of locally repairable codes has been done until now. In particular, there is little result on constructive lower bound of asymptotical behavior of locally repairable codes. In this paper, we extend the construction given by Barg et al. via automorphism groups of function field towers. The main advantage of our construction is to allow more flexibility of locality. Furthermore, we show that the Gilbert–Varshamov type bound on locally repairable codes can be improved for all sufficiently large alphabet size $q$. [ABSTRACT FROM AUTHOR]

In this paper, we focus on the downlink ergodic sum rate of a single-cell large-scale multiuser MIMO system in which the base station employs $N$ antennas to communicate with $K$ single-antenna user equipments (UEs). A regularized zero-forcing (RZF) scheme is used for precoding under the assumption that each UE uses a specific power and each link forms a spatially correlated MIMO Rician fading channel. The analysis is conducted assuming that $N$ and $K$ grow large with a given ratio and perfect channel state information is available at the base station. New results from random matrix theory and large system analysis are used to compute an asymptotic expression of the signal-to-interference-plus-noise ratio as a function of system parameters, spatial correlation matrix, and Rician factor. Numerical results are used to validate the accuracy of asymptotic approximations in the finite system regime and to evaluate the performance under different operating conditions. It turns out that the asymptotic expressions provide accurate approximations even for relatively small values of $N$ and $K$. [ABSTRACT FROM AUTHOR]

We revisit and take a closer look at a (not so well known) result of a 2017 paper, showing that the differential uniformity of any vectorial function is bounded from below by an expression depending on the size of its image set. We make explicit the resulting tight lower bound on the image set size of differentially $\delta $ -uniform functions (which is the only currently known non-trivial lower bound on the image set size of such functions). We also significantly improve an upper bound on the nonlinearity of vectorial functions obtained in the same reference and involving their image set size. We study when the resulting bound is sharper than the covering radius bound. We obtain as a by-product a lower bound on the Hamming distance between differentially $\delta $ -uniform functions and affine functions, which we improve significantly with a second bound. This leads us to study what can be the maximum Hamming distance between vectorial functions and affine functions. We provide an upper bound which is slightly sharper than a bound by Liu, Mesnager and Chen when $m < n$ , and a second upper bound, which is much stronger in the case (happening in practice) where $m$ is near $n$ ; we study the tightness of this latter bound; this leads to an interesting question on APN functions, which we address (negatively). We finally derive an upper bound on the nonlinearity of vectorial functions by means of their Hamming distance to affine functions and make more precise the bound on the differential uniformity which was the starting point of the paper. [ABSTRACT FROM AUTHOR]

Consider a massive random access scenario in which a small set of $k$ active users out of a large number of $n$ potential users need to be scheduled in $b\ge k$ slots. What is the minimum common feedback to the users needed to ensure that scheduling is collision-free? Instead of a naive scheme of listing the indices of the $k$ active users in the order in which they should transmit, at a cost of $k\log (n)$ bits, this paper shows that for the case of $b=k$ , the rate of the minimum fixed-length common feedback code scales only as $k \log (e)$ bits, plus an additive term that scales in $n$ as $\Theta (\log \log (n))$ for fixed $k$. If a variable-length code can be used, assuming uniform activity among the users, the minimum average common feedback rate still requires $k \log (e)$ bits, but the dependence on $n$ can be reduced to $O(1)$. When $b>k$ , the number of feedback bits needed for collision-free scheduling can be significantly further reduced. Moreover, a similar scaling on the minimum feedback rate is derived for the case of scheduling $m$ users per slot, when $k \le mb$. The problem of constructing a minimum collision-free feedback scheduling code is connected to that of constructing a perfect hashing family, which allows practical feedback scheduling codes to be constructed from perfect hashing algorithms. [ABSTRACT FROM AUTHOR]

Uplink-downlink duality refers to the fact that under a sum-power constraint, the capacity regions of a Gaussian multiple-access channel and a Gaussian broadcast channel with Hermitian transposed channel matrices are identical. This paper generalizes this result to a cooperative cellular network, in which remote access-points are deployed as relays in serving the users under the coordination of a central processor (CP). In this model, the users and the relays are connected over noisy wireless links, while the relays and the CP are connected over noiseless but rate-limited fronthaul links. Based on a Lagrangian technique, this paper establishes a duality relationship between such a multiple-access relay channel and broadcast relay channel, under the assumption that the relays use compression-based strategies. Specifically, we show that under the same total transmit power constraint and individual fronthaul rate constraints, the achievable rate regions of the Gaussian multiple-access and broadcast relay channels are identical, when either independent compression or Wyner-Ziv and multivariate compression strategies are used. The key observations are that if the beamforming vectors at the relays are fixed, the sum-power minimization problems under the achievable rate and fronthaul constraints in both the uplink and the downlink can be transformed into either a linear programming or a semidefinite programming problem depending on the compression technique, and that the uplink and downlink problems are Lagrangian duals of each other. Moreover, the dual variables corresponding to the downlink rate constraints become the uplink powers; the dual variables corresponding to the downlink fronthaul constraints become the uplink quantization noises. This duality relationship enables an efficient algorithm for optimizing the downlink transmission and relaying strategies based on the uplink. [ABSTRACT FROM AUTHOR]

The zero-error capacity of a channel is defined as the maximum rate at which it is possible to transmit information with zero probability of error. In this paper, we settle all previously unsolved cases for the zero-error capacity of binary channels with one memory. [ABSTRACT FROM AUTHOR]

It is well known that the mutual information between two random variables can be expressed as the difference of two relative entropies that depend on an auxiliary distribution, a relation sometimes referred to as the golden formula. This paper is concerned with a finite-blocklength extension of this relation. This extension consists of two elements: 1) a finite-blocklength channel-coding converse bound by Polyanskiy and Verdú, which involves the ratio of two Neyman–Pearson $\beta $ functions (beta–beta converse bound); and 2) a novel beta–beta channel-coding achievability bound, expressed again as the ratio of two Neyman–Pearson $\beta $ functions. To demonstrate the usefulness of this finite-blocklength extension of the golden formula, the beta–beta achievability and converse bounds are used to obtain a finite-blocklength extension of Verdú’s wideband-slope approximation. The proof parallels the derivation of the latter, with the beta–beta bounds used in place of the golden formula. The beta–beta (achievability) bound is also shown to be useful in cases where the capacity-achieving output distribution is not a product distribution due to, e.g., a cost constraint or structural constraints on the codebook, such as orthogonality or constant composition. As an example, the bound is used to characterize the channel dispersion of the additive exponential-noise channel and to obtain a finite-blocklength achievability bound (the tightest to date) for multiple-input multiple-output Rayleigh-fading channels with perfect channel state information at the receiver. [ABSTRACT FROM AUTHOR]

We consider the problem of recovering a high-dimensional structured signal from independent Gaussian linear measurements each of which is quantized to $b$ bits. The focus is on a specific method of signal recovery that extends a procedure originally proposed by Plan and Vershynin for one-bit quantization to a multi-bit setting. At the heart of this paper is a characterization of the optimal trade-off between the number of measurements m$ and the bit depth per measurement b$ given a total budget of B = m \cdot b -error in estimating the signal. It turns out that the choice b = 1$ is optimal for estimating the unit vector (direction) corresponding to the signal for any level of additive Gaussian noise before quantization as well as for a specific model of adversarial noise, whereas in a noiseless setting the choice b = 2$ is optimal for estimating the direction and the norm (scale) of the signal. Moreover, Lloyd–Max quantization is shown to be an optimal quantization scheme with respect to -estimation error. Our analysis is corroborated by the numerical experiments showing nearly perfect agreement with our theoretical predictions. This paper is complemented by an empirical comparison to alternative methods of signal recovery. The results of that comparison point to a regime change depending on the noise level: in a low-noise setting, the approach under study falls short of more sophisticated competitors while being competitive in moderate- and high-noise settings. [ABSTRACT FROM PUBLISHER]

Data compression is a well-studied (and well-solved) problem in the setup of long coding blocks. But important emerging applications need to compress data to memory words of small fixed widths. This new setup is the subject of this paper. In the problem we consider, we have two sources with known discrete distributions, and we wish to find codes that maximize the success probability that the two source outputs are represented in $L$ bits or less. A good practical use for this problem is a table with two-field entries that is stored in a memory of a fixed width $L$ . Such tables of very large sizes are common in network switches/routers and in data-intensive machine-learning applications. After defining the problem formally, we solve it optimally with an efficient code-design algorithm. We also solve the problem in the more constrained case where a single code is used in both fields (to save space for storing code dictionaries). For both code-design problems we find decompositions that yield efficient dynamic-programming algorithms. With the help of an empirical study we show the success probabilities of the optimal codes for different distributions and memory widths. In particular, this paper demonstrates the superiority of the new codes over existing compression algorithms. [ABSTRACT FROM AUTHOR]

This paper investigates the problem of coordinating several agents through their actions, focusing on an asymmetric observation structure with two agents. Specifically, one agent knows the past, present, and future realizations of a state that affects a common payoff function, while the other agent either knows the past realizations of nothing about the state. In both cases, the second agent is assumed to have strictly causal observations of the first agent’s actions, which enables the two agents to coordinate. These scenarios are applied to distributed power control; the key idea is that a transmitter may embed information about the wireless channel state into its transmit power levels so that an observation of these levels, e.g., the signal-to-interference-plus-noise ratio, allows the other transmitter to coordinate its power levels. The main contributions of this paper are twofold. First, we provide a characterization of the set of feasible average payoffs when the agents repeatedly take long sequences of actions and the realizations of the system state are i.i.d.. Second, we exploit these results in the context of distributed power control and introduce the concept of coded power-control. We carry out an extensive numerical analysis of the benefits of coded power control over alternative power-control policies, and highlight a simple yet non-trivial example of a power control code. [ABSTRACT FROM PUBLISHER]

Lattices possess elegant mathematical properties which have been previously used in the literature to show that structured codes can be efficient in a variety of communication scenarios, including coding for the additive white Gaussian noise channel, dirty-paper channel, Wyner–Ziv coding, coding for relay networks, and so forth. We consider the family of single-transmitter multiple-receiver Gaussian channels, where the source transmits a set of common messages to all the receivers (multicast scenario), and each receiver has coded side information, i.e., prior information in the form of linear combinations of the messages. This channel model is motivated by applications to multi-terminal networks, where the nodes may have access to coded versions of the messages from previous signal hops or through orthogonal channels. The capacity of this channel is known and follows from the work of Tuncel (2006), which is based on random coding arguments. In this paper, following the approach of Erez and Zamir, we design lattice codes for this family of channels when the source messages are symbols from a finite field \mathbb Fp of prime size. Our coding scheme utilizes Construction A lattices designed over the same prime field \mathbb Fp , and uses algebraic binning at the decoders to expurgate the channel code and obtain good lattice subcodes, for every possible set of linear combinations available as side information. The achievable rate of our coding scheme is a function of the size $p$ of underlying prime field, and approaches the capacity as $p$ tends to infinity. [ABSTRACT FROM PUBLISHER]

This paper focuses on the modeling and analysis of the temporal performance variation experienced by a mobile user in a wireless network and its impact on system-level design. We consider a simple stochastic geometry model: the infrastructure nodes are Poisson distributed while the user’s motion is the simplest possible, i.e., constant velocity on a straight line. We first characterize variations in the signal-to-noise ratio (SNR) process and associated downlink Shannon rate, resulting from variations in the infrastructure geometry seen by the mobile. Specifically, by making a connection between stochastic geometry and queuing theory, the level crossings of the SNR process are shown to form an alternating renewal process whose distribution is completely characterized. For large/small SNR levels, and associated rare events, we further derive simple distributional (exponential) models. We then characterize the second major contributor to such variations, namely, changes in the number of other users sharing the infrastructure. Combining these two phenomena, we study what are the dominant factors (infrastructure geometry or sharing number) when a mobile experiences a very high/low shared rate. These results are then used to evaluate and optimize the system-level quality of experience of the mobile users sharing such a wireless infrastructure, including mobile devices streaming video which proactively buffer content to prevent rebuffering and mobiles which are downloading large files. Finally, we use simulation to assess the fidelity of this model and its robustness to factors which are presently not taken into account. [ABSTRACT FROM PUBLISHER]

Repair operations in erasure-coded distributed storage systems involve a lot of data movement. This can potentially expose data to malicious acts of passive eavesdroppers or active adversaries, putting security of the system at risk. This paper presents coding schemes and repair algorithms that ensure security of the data in the presence of passive eavesdroppers and active adversaries while maintaining high availability, reliability, and resource efficiency in the system. The proposed codes are optimal in that they meet previously proposed lower bounds on storage and network-bandwidth requirements for a wide range of system parameters. The results thus establish the secure storage capacity of such systems. The proposed codes are based on an optimal class of codes called product-matrix codes. The constructions presented for security from active adversaries provide an additional appealing feature of “on-demand security,” where the desired level of security can be chosen separately for each instance of repair, and the proposed algorithms remain optimal simultaneously for all possible security levels. This paper also provides necessary and sufficient conditions governing the transformation of any (non-secure) code into one providing on-demand security. [ABSTRACT FROM PUBLISHER]

This paper considers the problem of estimating a high-dimensional vector of parameters \theta \in \mathbb R^n from a noisy observation. The noise vector is independent identically distributed Gaussian with known variance. For a squared-error loss function, the James–Stein (JS) estimator is known to dominate the simple maximum-likelihood (ML) estimator when the dimension n exceeds two. The JS-estimator shrinks the observed vector toward the origin, and the risk reduction over the ML-estimator is greatest for {\theta } that lie close to the origin. JS-estimators can be generalized to shrink the data toward any target subspace. Such estimators also dominate the ML-estimator, but the risk reduction is significant only when {\theta } lies close to the subspace. This leads to the question: in the absence of prior information about \theta , how do we design estimators that give significant risk reduction over the ML-estimator for a wide range of \theta ? In this paper, we propose shrinkage estimators that attempt to infer the structure of \theta from the observed data in order to construct a good attracting subspace. In particular, the components of the observed vector are separated into clusters, and the elements in each cluster shrunk toward a common attractor. The number of clusters and the attractor for each cluster are determined from the observed vector. We provide concentration results for the squared-error loss and convergence results for the risk of the proposed estimators. The results show that the estimators give significant risk reduction over the ML-estimator for a wide range of \theta , particularly for large $n$ . Simulation results are provided to support the theoretical claims. [ABSTRACT FROM AUTHOR]

This paper focuses on the problem of separately modulating and jointly estimating two independent continuous-valued parameters sent over a Gaussian multiple-access channel (MAC) under the mean square error (MSE) criterion without bandwidth constraints. To this end, we first improve an existing lower bound on the MSE that is obtained using the parameter modulation-estimation techniques for the single-user additive white Gaussian noise (AWGN) channel. As for the main contribution of this paper, this improved modulation-estimation analysis is generalized to the model of the two-user Gaussian MAC. We present outer bounds to the achievable region in the plane of the MSE’s of the two user parameters, which provides a trade-off between the MSE’s, where we used zero-rate lower bounds on the error probability of Gaussian channels by Shannon and Polyanskiy et al. Numerical results showed that, the multi-user adaptation of the zero-rate lower bound by Polyanskiy et al. provides a tighter overall lower bound on the MSE pairs than the classical Shannon bound. In addition, we introduced upper bounds on the MSE exponents, namely, the exponential decay rates of these MSE’s in the asymptotic regime of long blocks that could make use of any bound on the error exponent of a single-user AWGN channel. The obtained results are numerically evaluated for three different bounds on the reliability function of the Gaussian channel. It is shown that the adaptation of the reliability function by Ashikhmin et al. to the MAC provides a significantly tighter characterization than Shannon’s sphere-packing bound and the divergence bound. [ABSTRACT FROM AUTHOR]

The Riemannian geometry of covariance matrices has been essential to several successful applications, in computer vision, biomedical signal and image processing, and radar data processing. For these applications, an important ongoing challenge is to develop Riemannian-geometric tools which are adapted to structured covariance matrices. This paper proposes to meet this challenge by introducing a new class of probability distributions, Gaussian distributions of structured covariance matrices. These are Riemannian analogs of Gaussian distributions, which only sample from covariance matrices having a preassigned structure, such as complex, Toeplitz, or block-Toeplitz. The usefulness of these distributions stems from three features: 1) they are completely tractable, analytically, or numerically, when dealing with large covariance matrices; 2) they provide a statistical foundation to the concept of structured Riemannian barycentre (i.e., Fréchet or geometric mean); and 3) they lead to efficient statistical learning algorithms, which realise, among others, density estimation and classification of structured covariance matrices. This paper starts from the observation that several spaces of structured covariance matrices, considered from a geometric point of view, are Riemannian symmetric spaces. Accordingly, it develops an original theory of Gaussian distributions on Riemannian symmetric spaces, of their statistical inference, and of their relationship to the concept of Riemannian barycentre. Then, it uses this original theory to give a detailed description of Gaussian distributions of three kinds of structured covariance matrices, complex, Toeplitz, and block-Toeplitz. Finally, it describes algorithms for density estimation and classification of structured covariance matrices, based on Gaussian distribution mixture models. [ABSTRACT FROM AUTHOR]

In this paper, we examine an input-constrained erasure channel and we characterize the asymptotics of its capacity when the erasure rate is low. More specifically, for a general memoryless erasure channel with its input supported on an irreducible finite-type constraint, we derive partial asymptotics of its capacity, using some series expansion type formula of its mutual information rate; and for a binary erasure channel with its first-order Markovian input supported on the $(1, \infty )$ -RLL constraint based on the concavity of its mutual information rate with respect to some parameterization of the input, we numerically evaluate its first-order Markov capacity and further derive its full asymptotics. The asymptotics obtained in this paper, when compared with the recently derived feedback capacity for a binary erasure channel with the same input constraint, enable us to draw the conclusion that feedback may increase the capacity of an input-constrained channel, even if the channel is memoryless. [ABSTRACT FROM PUBLISHER]

This paper considers the problem of lossy source coding with a specific distortion measure: logarithmic loss. The focus of this paper is on the single-shot approach, which exposes crisply the connection between lossless source coding with list decoding and lossy source coding with log-loss. Fixed-length and variable-length bounds are presented. Fixed-length bounds include the single-shot fundamental limit for average as well as excess distortion. Variable-length bounds include the single-shot fundamental limit for average as well as excess length. Two multi-terminal problems are addressed: coding with side information (Wyner–Ziv) and multiple descriptions coding. In both the cases, the application of the Shannon–McMillan theorem to the single-shot bounds yields the rate-distortion function and the rate distortion-region for stationary ergodic sources. [ABSTRACT FROM PUBLISHER]

Complexity of sequences plays an important role in pseudorandom sequences and cryptography. In this paper, we present a construction of sequences with high nonlinear complexity from function fields. The main idea is to make use of function fields with many rational places as well as an automorphism of large order. We illustrate our construction through rational function fields and cyclotomic function fields in which there exist some automorphisms of large order. It turns out that we are able to: 1) slightly increase the length of the inversive sequence without losing nonlinear complexity and 2) obtain sequences with much larger nonlinear complexity than random sequences. [ABSTRACT FROM AUTHOR]

Consider a continuous signal that cannot be observed directly. Instead, one has access to multiple corrupted versions of the signal. The available corrupted signals are correlated because they carry information about the common remote signal. The goal is to reconstruct the original signal from the data collected from its corrupted versions. Known as the indirect or remote reconstruction problem, it has been mainly studied in the literature from an information theoretic perspective. A variant of this problem for a class of Gaussian signals, known as the “Gaussian CEO problem,” has received particular attention; for example, it has been shown that the problem of recovering the remote signal is equivalent with the problem of recovering the set of corrupted signals (separation principle). The information theoretic formulation of the remote reconstruction problem assumes that the corrupted signals are uniformly sampled and the focus is on optimal compression of the samples. On the other hand, in this paper, we revisit this problem from a sampling perspective. More specifically, assuming restrictions on the sampling rate from each corrupted signal, we look at the problem of finding the best sampling locations for each signal to minimize the total reconstruction distortion of the remote signal. In finding the sampling locations, one can take advantage of the correlation among the corrupted signals. The statistical model of the original signal and its corrupted versions adopted in this paper are similar to the one considered for the Gaussian CEO problem; i.e., we restrict to a class of Gaussian signals. Our main contribution is a fundamental lower bound on the reconstruction distortion for any arbitrary nonuniform sampling strategy. This lower bound is valid for any sampling rate. Furthermore, it is tight and matches the optimal reconstruction distortion in low and high sampling rates. Moreover, it is shown that in the low sampling rate region, it is optimal to use a certain nonuniform sampling scheme on all the signals. On the other hand, in the high sampling rate region, it is optimal to uniformly sample all the signals. We also consider the problem of finding the optimal sampling locations to recover the set of corrupted signals, rather than the remote signal. Unlike the information theoretic formulation of the problem in which these two problems were equivalent, we show that they are not equivalent in our setting. Finally, another contribution of this paper is a new reverse majorization inequality that might be of independent interest. [ABSTRACT FROM PUBLISHER]

Boolean functions with high algebraic immunity are important cryptographic primitives in some stream ciphers. In this paper, two methodologies for constructing minimal binary codes from sets, Boolean functions and vectorial Boolean functions with high algebraic immunity, are proposed. More precisely, a general construction of new minimal codes using minimal codes contained in Reed-Muller codes and sets without nonzero low degree annihilators is presented. The other construction allows us to yield minimal codes from certain subcodes of Reed-Muller codes and vectorial Boolean functions with high algebraic immunity. Via these general constructions, infinite families of minimal binary linear codes of dimension $m$ and length less than or equal to $m(m+1)/2$ are obtained. Besides, a lower bound on the minimum distance of the proposed minimal linear codes is established. Conjectures and open problems are also presented. The results of this paper show that Boolean functions with high algebraic immunity have nice applications in several fields additionally to symmetric cryptography, such as coding theory and secret sharing schemes. [ABSTRACT FROM AUTHOR]

The nondispersive per-sample channel model for the optical fiber channel is considered. Under certain smoothness assumptions, the problem of finding the minimum amount of noise energy that can render two different input points indistinguishable is formulated. This minimum noise energy is then taken as a measure of distance between the points in the input alphabet. Using the machinery of optimal control theory, necessary conditions that describe the minimum-energy noise trajectories are stated as a system of nonlinear differential equations. It is shown how to find the distance between two input points by solving this system of differential equations. The problem of designing signal constellations with the largest minimum distance subject to a peak power constraint is formulated as a clique-finding problem. As an example, a 16-point constellation is designed and compared with conventional quadrature amplitude modulation. A computationally efficient approximation for the proposed distance measure is provided. It is shown how to use this approximation to design large constellations with large minimum distances. Based on the control-theoretic viewpoint of this paper, a new decoding scheme for such nonlinear channels is proposed. [ABSTRACT FROM AUTHOR]

Two general constructions of linear codes with functions over finite fields have been extensively studied in the literature. The first one is given by C(ƒ) = {Tr(aƒ(x) + bx)x∈Fqm*: a, b ∈ Fqm}, where q is a prime power, Fqm* = Fqm \ {0}, Tr is the trace function from Fqm to Fq, and ƒ(x) is a function from Fqm to Fqm with ƒ(0) = 0. Almost bent functions, quadratic functions and some monomials on F2m were used in the first construction, and many families of binary linear codes with few weights were obtained in the literature. This paper studies some punctured codes of these binary codes. Several families of binary linear codes with few weights and new parameters are obtained in this paper. Several families of distance-optimal binary linear codes with new parameters are also produced in this paper. [ABSTRACT FROM AUTHOR]

This paper studies a memoryless state-dependent multiple access channel (MAC) where two transmitters wish to convey a message to a receiver under the assumption of causal and imperfect channel state information at transmitters (CSIT) and imperfect channel state information at receiver (CSIR). In order to emphasize the limitation of transmitter cooperation between physically distributed nodes, we focus on the so-called distributed CSIT assumption, i.e., where each transmitter has its individual channel knowledge, while the message can be assumed to be partially or entirely shared a priori between transmitters by exploiting some on-board memory. Under this setup, the first part of the paper characterizes the common message capacity of the channel at hand for arbitrary CSIT and CSIR structure. The optimal scheme builds on Shannon strategies, i.e., optimal codes are constructed by letting the channel inputs be a function of current CSIT only. For a special case when CSIT is a deterministic function of CSIR, the considered scheme also achieves the capacity region of a common message and two private messages. The second part addresses an important instance of the previous general result in a context of a cooperative multi-antenna Gaussian channel under i.i.d. fading operating in frequency-division duplex mode, such that CSIT is acquired via an explicit feedback of perfect CSIR. The capacity of the channel at hand is achieved by distributed linear precoding applied to Gaussian codes. Surprisingly, we demonstrate that it is suboptimal to send a number of data streams bounded by the number of transmit antennas as typically considered in a centralized CSIT setup. Finally, numerical examples are provided to evaluate the sum capacity of the binary MAC with binary states as well as the Gaussian MAC with i.i.d. fading. [ABSTRACT FROM AUTHOR]

The puncturing and shortening techniques are two important approaches to constructing new linear codes from old ones. In the past 70 years, a lot of progress on the puncturing technique has been made, and many works on punctured linear codes have been done. Many families of linear codes with interesting parameters have been obtained with the puncturing technique. However, little research on the shortening technique has been done and there are only a handful references on shortened linear codes. The first objective of this paper is to prove some general theory for shortened linear codes. The second objective is to study some shortened codes of the Hamming codes, Simplex codes, some Reed-Muller codes, and ovoid codes. Eleven families of optimal shortened codes over finite fields are presented in this paper. As a byproduct, five infinite families of 2-designs are also constructed from some of the shortened codes presented in this paper. [ABSTRACT FROM AUTHOR]

Orthogonal/vector approximate message-passing (AMP) is a powerful message-passing (MP) algorithm for signal reconstruction in compressed sensing. This paper proves the convergence of Bayes-optimal orthogonal/vector AMP in the large system limit. The proof strategy is based on a novel long-memory (LM) MP approach: A first step is a construction of LM-MP that is guaranteed to converge systematically. A second step is a large-system analysis of LM-MP via an existing framework of state evolution. A third step is to prove the convergence of state evolution recursions for Bayes-optimal LM-MP via a new statistical interpretation of existing LM damping. The last is an exact reduction of the state evolution recursions for Bayes-optimal LM-MP to those for Bayes-optimal orthogonal/vector AMP. The convergence of the state evolution recursions for Bayes-optimal LM-MP implies that for Bayes-optimal orthogonal/vector AMP. Numerical simulations are presented to show the verification of state evolution results for damped orthogonal/vector AMP and a negative aspect of LM-MP in finite-sized systems. [ABSTRACT FROM AUTHOR]

Approximate message passing (AMP) is a low-cost iterative parameter-estimation technique for certain high-dimensional linear systems with non-Gaussian distributions. AMP only applies to independent identically distributed (IID) transform matrices, but may become unreliable (e.g., perform poorly or even diverge) for other matrix ensembles, especially for ill-conditioned ones. To solve this issue, orthogonal/vector AMP (OAMP/VAMP) was proposed for general right-unitarily-invariant matrices. However, the Bayes-optimal OAMP/VAMP (BO-OAMP/VAMP) requires a high-complexity linear minimum mean square error (MMSE) estimator. This prevents OAMP/VAMP from being used in large-scale systems. To address the drawbacks of AMP and BO-OAMP/VAMP, this paper offers a memory AMP (MAMP) framework based on the orthogonality principle, which ensures that estimation errors in MAMP are asymptotically IID Gaussian. To realize the required orthogonality for MAMP, we provide an orthogonalization procedure for the local memory estimators. In addition, we propose a Bayes-optimal MAMP (BO-MAMP), in which a long-memory matched filter is used for interference suppression. The complexity of BO-MAMP is comparable to AMP. To asymptotically characterize the performance of BO-MAMP, a state evolution is derived. The relaxation parameters and damping vector in BO-MAMP are optimized based on state evolution. Most crucially, the state evolution of the optimized BO-MAMP converges to the same fixed point as that of the high-complexity BO-OAMP/VAMP for all right-unitarily-invariant matrices, and achieves the Bayes optimal MSE predicted by the replica method if its state evolution has a unique fixed point. Finally, simulations are provided to verify the theoretical results’ validity and accuracy. [ABSTRACT FROM AUTHOR]

In its most elementary form, compressed sensing studies the design of decoding algorithms to recover a sufficiently sparse vector or code from a lower dimensional linear measurement vector. Typically it is assumed that the decoder has access to the encoder matrix, which in the combinatorial case is sparse and binary. In this paper we consider the problem of designing a decoder to recover a set of sparse codes from their linear measurements alone, that is without access to encoder matrix. To this end we study the matrix factorisation task of recovering both the encoder and sparse coding matrices from the associated linear measurement matrix. The contribution of this paper is a computationally efficient decoding algorithm, Decoder-Expander Based Factorisation, with strong performance guarantees. Under mild assumptions on the sparse coding matrix and by deploying a novel random encoder matrix, we prove that Decoder-Expander Based Factorisation recovers both the encoder and sparse coding matrix at the optimal measurement rate with high probability and from a near optimal number of measurement vectors. In addition, our experiments demonstrate the efficacy and computational efficiency of our algorithm in practice. Beyond compressed sensing, our results may be of interest for researchers working in areas as diverse as linear sketching, coding theory, matrix compression and dictionary learning. [ABSTRACT FROM AUTHOR]