Search

Distributed Arithmetic Coding (DAC) is a practical realization of Slepian-Wolf coding that partitions source space into cosets. Coset Cardinality Spectrum (CCS) is an important property of DAC that was defined in our previous work. In this paper, we give two applications of CCS. First, we find that DAC bitstream is not compact. The rate loss of DAC bitstream is caused by two factors: unequal coset partitioning and bit indivisibility. It is proved that as code length goes to infinity, the expected value of bit-indivisibility rate loss will tend to 0.5 for any irrational Rate Change Step (RCS), where the RCS refers to the rate change when one source bit is flipped. With the help of CCS, the bit-indivisibility rate loss can be compensated to some extend. Especially, for any irrational RCS, as code length goes to infinity, the expected value of the remaining bit-indivisibility rate loss after compensation will tend to about 0.47. The second application of CCS is DAC decoder design. We derive the formula of path metric and find that in the original paper on DAC, the intuitive formula of path metric is not correct. The backward-replacing algorithm is proposed to make full use of memory. Experimental results confirm the correctness of theoretical analyses. [ABSTRACT FROM AUTHOR]

Motivated by the established notion of storage codes, we consider sets of infinite sequences over a finite alphabet such that every $k$ -tuple of consecutive entries is uniquely recoverable from its $l$ -neighborhood in the sequence. We address the problem of finding the maximum growth rate of the set, which we term capacity, as well as constructions of explicit families that approach the optimal rate. The techniques that we employ rely on the connection of this problem with constrained systems. In the second part of the paper we consider a modification of the problem wherein the entries in the sequence are viewed as random variables over a finite alphabet that follow some joint distribution, and the recovery condition requires that the Shannon entropy of the $k$ -tuple conditioned on its $l$ -neighborhood be bounded above by some $\epsilon >0$. We study properties of measures on infinite sequences that maximize the metric entropy under the recoverability condition. Drawing on tools from ergodic theory, we prove some properties of entropy-maximizing measures. We also suggest a procedure of constructing an $\epsilon $ -recoverable measure from a corresponding deterministic system. [ABSTRACT FROM AUTHOR]

This paper studies the downlink of a cloud radio access network (C-RAN) in which a centralized processor (CP) communicates with mobile users through base stations (BSs) that are connected to the CP via finite-capacity fronthaul links. Information theoretically, the downlink of a C-RAN is modeled as a two-hop broadcast-relay network. Among the various transmission and relaying strategies for such model, this paper focuses on the compression strategy, in which the CP centrally encodes the signals to be broadcast jointly by the BSs, then compresses and sends these signals to the BSs through the fronthaul links. We characterize an achievable rate region for a generalized compression strategy with Marton’s multicoding for broadcasting and multivariate compression for fronthaul transmission. We then compare this rate region with the distributed decode-forward (DDF) scheme, which achieves the capacity of the general relay networks to within a constant gap, and show that the difference lies in that DDF performs Marton’s multicoding and multivariate compression jointly as opposed to successively as in the compression strategy. A main result of this paper is that under the assumption that the fronthaul links are subject to a sum capacity constraint, this difference is immaterial; so, for the Gaussian network, the compression strategy based on successive encoding can already achieve the capacity region of the C-RAN to within a constant gap, where the gap is independent of the channel parameters and the power constraints at the BSs. As a further result, for C-RAN under individual fronthaul constraints, this paper also establishes that the compression strategy can achieve to within a constant gap to the sum capacity. [ABSTRACT FROM AUTHOR]

This paper considers secret-key generation between several agents and a base station that observe independent and identically distributed realizations of correlated random variables. Each agent wishes to generate the longest possible individual key with the base station by means of public communication. All keys must be jointly kept secret from all external entities. In this many-to-one secret-key generation setting, it can be shown that the agents can take advantage of a collective protocol to increase the sum rate of their generated keys. However, when each agent is only interested in maximizing its own secret-key rate, agents may be unwilling to participate in a collective protocol. Furthermore, when such a collective protocol is employed, how to fairly allocate individual key rates arises as a valid issue. This paper studies the tension between cooperation and self-interest with a game-theoretic treatment. This paper establishes that cooperation is in the best interest of all individualistic agents and that there exist individual secret-key rate allocations that incentivize the agents to follow the protocol. In addition, an explicit coding scheme that achieves such allocations is proposed. [ABSTRACT FROM AUTHOR]

In this paper, we study an information-theoretic secret sharing problem, where a dealer distributes shares of a secret among a set of participants under the following constraints: (i) authorized sets of users can recover the secret by pooling their shares, and (ii) non-authorized sets of colluding users cannot learn any information about the secret. We assume that the dealer and participants observe the realizations of correlated Gaussian random variables and that the dealer can communicate with participants through a one-way, authenticated, rate-limited, and public channel. Unlike traditional secret sharing protocols, in our setting, no perfectly secure channel is needed between the dealer and the participants. Our main result is a closed-form characterization of the fundamental trade-off between secret rate and public communication rate. [ABSTRACT FROM AUTHOR]

A coding scheme for transmission of a bit maps a given bit to a sequence of channel inputs (called the codeword associated with the transmitted bit). In this paper, we study the problem of designing the best code for a discrete Poisson channel with memory (under peak-power and total-power constraints). The outputs of a discrete Poisson channel with memory are Poisson distributed random variables with a mean comprising of a fixed additive noise and a linear combination of past input symbols. Assuming a maximum-likelihood (ML) decoder, we search for a codebook that has the smallest possible error probability. This problem is challenging because error probability of a code does not have a closed-form analytical expression. For the case of having only a total-power constraint, the optimal code structure is obtained, provided that the blocklength is greater than the memory length of the channel. For the case of having only a peak-power constraint, the optimal code is derived for arbitrary memory and blocklength in the high-power regime. For the case of having both the peak-power and total-power constraints, the optimal code is derived for memoryless Poisson channels when both the total-power and the peak-power bounds are large. [ABSTRACT FROM AUTHOR]

In this paper, we propose CodedSketch, as a distributed straggler-resistant scheme to compute an approximation of the multiplication of two massive matrices. The objective is to reduce the recovery threshold, defined as the total number of worker nodes that the master node needs to wait for to be able to recover the final result. To exploit the fact that only an approximated result is required, in reducing the recovery threshold, some sorts of pre-compression are required. However, compression inherently involves some randomness that would lose the structure of the matrices. On the other hand, considering the structure of the matrices is crucial to reduce the recovery threshold. In CodedSketch, we use count–sketch, as a hash-based compression scheme, on the rows of the first and columns of the second matrix, and a structured polynomial code on the columns of the first and rows of the second matrix. This arrangement allows us to exploit the gain of both in reducing the recovery threshold. To increase the accuracy of computation, multiple independent count–sketches are needed. This independency allows us to theoretically characterize the accuracy of the result and establish the recovery threshold achieved by the proposed scheme. To guarantee the independency of resulting count–sketches in the output, while keeping its cost on the recovery threshold minimum, we use another layer of structured codes. The proposed scheme provides an upper-bound on the recovery threshold as a function of the required accuracy of computation and the probability that the required accuracy can be violated. In addition, it provides an upper-bound on the recovery threshold for the case that the result of the multiplication is sparse, and the exact result is required. [ABSTRACT FROM AUTHOR]

In this paper, a new model for arbitrarily varying classical-quantum channels is proposed. In this model, a jammer has side information. The communication scenario in which a jammer can select only classical inputs as a jamming sequence is considered in the first part of the paper. This situation corresponds to the standard model of arbitrarily varying classical-quantum channels. Two scenarios are considered. In the first scenario, the jammer knows the channel input, while in the second scenario the jammer knows both the channel input and the message. The transmitter and receiver share a secret random key with a vanishing key rate. The capacity for both average and maximum error criteria for both scenarios is determined in this paper. A strong converse is also proved. It is shown that all these corresponding capacities are equal, which means that additionally revealing the message to the jammer does not change the capacity. The communication scenario with a fully quantum jammer is considered in the second part of the paper. A single letter characterization for the capacity with secret random key as assistance for both average and maximum error criteria is derived in the paper. [ABSTRACT FROM AUTHOR]

The two-user multiple-input multiple-output Gaussian broadcast channel with common, private, and confidential messages is considered. The transmitter sends a common message to both users, a confidential message to the User 1 and a private (non-confidential) message to the User 2. The secrecy-capacity region is characterized by showing that certain inner and outer bounds coincide and that the boundary points are achieved by Gaussian inputs, which enables the development of a tight converse. The proof relies on the factorization of upper concave envelopes and a variant of dirty-paper coding (DPC). It is shown that the entire region is exhausted by using DPC to cancel out the signal of the non-confidential message at Receiver 1, thus making DPC against the signal of the confidential message unnecessary. A numerical example illustrates the secrecy-capacity results. [ABSTRACT FROM AUTHOR]

This paper investigates the asymptotic expansion for the maximum rate of fixed-length codes over a parallel Gaussian channel with feedback under the following setting: a peak power constraint is imposed on every transmitted codeword, and the average error probabilities of decoding the transmitted message are non-vanishing as the blocklength increases. The main contribution of this paper is a self-contained proof of an upper bound on the first- and second-order asymptotics of the parallel Gaussian channel with feedback. The proof techniques involve developing an information spectrum bound followed by using Curtiss’ theorem to show that a sum of dependent random variables associated with the information spectrum bound converges in distribution to a sum of independent random variables, thus facilitating the use of the usual central limit theorem. Combined with existing achievability results, our result implies that the presence of feedback does not improve the first- and second-order asymptotics. [ABSTRACT FROM PUBLISHER]

In the distributed function computation problem, dichotomy theorems, initiated by Han-Kobayashi, seek to classify functions by whether the rate regions for function computation improve on the Slepian-Wolf regions or not. In this paper, we develop a general approach to derive converse bounds on the distributed function computation problem. By using this approach, we recover the sufficiency part, i.e. the conditions such that the Slepian-Wolf regions become optimal, of the known dichotomy theorems in the two-terminal distributed computing. Furthermore, we derive an improved sufficient condition on the dichotomy theorem in the multiterminal distributed computing for the class of i.i.d. sources with the positivity condition. Finally, we derive the matching sufficient and necessary condition on the dichotomy theorem in the multiterminal distributed computing for the class of smooth sources. [ABSTRACT FROM AUTHOR]

It is well known that superposition coding, namely separately encoding the independent sources, is optimal for symmetric multilevel diversity coding (SMDC) (Yeung-Zhang 1999) for any $L\geq 2$ , where $L$ is the number of levels of the coding system. However, the characterization of the coding rate region therein involves uncountably many linear inequalities and the constant term (i.e., the lower bound) in each inequality is given in terms of the solution of a linear optimization problem. Thus this implicit characterization of the coding rate region does not enable the determination of the achievability of a given rate tuple. In principle, the achievability of a given rate tuple can be determined by direct computation, but the complexity is prohibitive even for $L=5$. In this paper, for any fixed $L$ , we obtain in closed form a finite set of linear inequalities for characterizing the coding rate region. We further show by the symmetry of the problem that only a much smaller subset of this finite set of inequalities needs to be verified in determining the achievability of a given rate tuple. Yet, the cardinality of this smaller set grows at least exponentially fast with $L$. We also present a subset entropy inequality, which together with our explicit characterization of the coding rate region, is sufficient for proving the optimality of superposition coding. [ABSTRACT FROM AUTHOR]

In this paper, we study the arbitrarily varying broadcast channel (AVBC) when the state information is available at the transmitter in a causal manner. We establish the inner and outer bounds on both the random code capacity region and the deterministic code capacity region with degraded message sets. The capacity region is then determined for a class of channels satisfying a condition on the mutual information between the strategy variables and the channel outputs. As an example, we consider the arbitrarily varying binary symmetric broadcast channel. We show the cases where the condition holds and, hence, the capacity region is determined and other cases where there is a gap between the bounds. This gap shows that the minimax theorem does not hold for rate regions. [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]

The Gauss–Markov source produces $U_{i} = aU_{i-1} + Z_{i}$ for $i\geq 1$ , where $U_{0} = 0$ , $|a|< 1$ and $Z_{i}\sim \mathcal {N}(0, \sigma ^{2})$ are i.i.d. Gaussian random variables. We consider lossy compression of a block of $n$ samples of the Gauss–Markov source under squared error distortion. We obtain the Gaussian approximation for the Gauss–Markov source with excess-distortion criterion for any distortion $d>0$ , and we show that the dispersion has a reverse waterfilling representation. This is the first finite blocklength result for lossy compression of sources with memory. We prove that the finite blocklength rate-distortion function $R(n,d,\epsilon)$ approaches the rate-distortion function $\mathbb {R}(d)$ as $R(n,d,\epsilon) = \mathbb {R}(d) + \sqrt {\frac {V(d)}{n}}Q^{-1}(\epsilon) + o\left ({\frac {1}{\sqrt {n}}}\right)$ , where $V(d)$ is the dispersion, $\epsilon \in (0,1)$ is the excess-distortion probability, and $Q^{-1}$ is the inverse $Q$ -function. We give a reverse waterfilling integral representation for the dispersion $V(d)$ , which parallels that of the rate-distortion functions for Gaussian processes. Remarkably, for all $0 < d\leq \frac {\sigma ^{2}}{(1+|a|)^{2}}$ , $R(n,d,\epsilon)$ of the Gauss–Markov source coincides with that of $Z_{i}$ , the i.i.d. Gaussian noise driving the process, up to the second-order term. Among novel technical tools developed in this paper is a sharp approximation of the eigenvalues of the covariance matrix of $n$ samples of the Gauss–Markov source, and a construction of a typical set using the maximum likelihood estimate of the parameter $a$ based on $n$ observations. [ABSTRACT FROM AUTHOR]

This paper establishes the exact exponents for the soft-covering phenomenon of a memoryless channel under the total variation metric when random (i.i.d. and constant-composition) channel codes are used. The exponents, established herein, are strict improvements in both directions on bounds found in the literature. This complements the recent literature establishing the exact exponents under the relative entropy metric; however, the proof techniques have significant differences, and thus, neither result trivially implies the other. The found exponents imply new and improved bounds for various problems that use soft-covering as their achievability argument, including new lower bounds for the resolvability exponent and the secrecy exponent in the wiretap channel. [ABSTRACT FROM AUTHOR]

Classical multiuser information theory studies the fundamental limits of models with a fixed (often small) number of users as the coding blocklength goes to infinity. This paper proposes a new paradigm, referred to as many-user information theory, where the number of users is allowed to grow with the blocklength. This paradigm is motivated by emerging systems with a massive number of users in an area, such as the Internet of Things. The focus of this paper is the many-access channel model, which consists of a single receiver and many transmitters, whose number increases unboundedly with the blocklength. Moreover, an unknown subset of transmitters may transmit in a given block and need to be identified as well as decoded by the receiver. A new notion of capacity is introduced and characterized for the Gaussian many-access channel with random user activities. The capacity can be achieved by first detecting the set of active users and then decoding their messages. The minimum cost of identifying the active users is also quantified. [ABSTRACT FROM AUTHOR]

An open problem in polarization theory is to determine the binary operations that always lead to polarization (in the general multilevel sense) when they are used in Arıkan style constructions. This paper, which is presented in two parts, solves this problem by providing a necessary and sufficient condition for a binary operation to be polarizing. This (first) part of this paper introduces the mathematical framework that we will use in the second part to characterize the polarizing operations. We define uniformity preserving, irreducible, ergodic, and strongly ergodic operations, and we study their properties. The concepts of a stable partition and the residue of a stable partition are introduced. We show that an ergodic operation is strongly ergodic if and only if all its stable partitions are their own residues. We also study the products of binary operations and the structure of their stable partitions. We show that the product of a sequence of binary operations is strongly ergodic if and only if all the operations in the sequence are strongly ergodic. In the second part of this paper, we provide a foundation of polarization theory based on the ergodic theory of binary operations that we develop in this part. [ABSTRACT FROM PUBLISHER]

In this paper, we consider a binary erasure channel (BEC) with an unknown erasure probability of ${\delta }$ at a transmitter. In addition, we consider that ${\delta }$ has a constant value in each transmission block and the transmitter knows the probability distribution of ${\delta }$. For this problem with the infinite block length, based on the distribution of the random variable ${\delta }$ , a multi-layer encoding strategy at the transmitter and a successive decoding strategy at the receiver are proposed. In our proposed scheme, based on the value of ${\delta }$ , the receiver can decode a part of transmitted data from different transmission layers. In order to have a comparison with other erasure correction codes, we generalize the result of the infinite block length to the finite block-length transmission. We show that considering the average transmission rate, our scheme has a better performance than the other erasure correction codes such as the Raptor and the MDS codes. We also analyze both the decoding complexity and bit error rate versus the erasure probability of the channel. Besides, by using a numerical comparison, we try to show that our proposed strategy outperforms other transmission strategies. [ABSTRACT FROM AUTHOR]

An important problem in secret sharing schemes is minimizing the share size. For ($k$ , $n$)-threshold schemes and ($k$ , $L$ , $n$)-ramp schemes, constructions that minimize the share size are known. This paper presents optimal constructions for a more general class of access structures in which subsets with the same cardinality have the same amount of information about the secret. We refer to schemes with such uniform access structures as uniform secret sharing. We first derive a tight lower bound for share entropy and then present an optimal construction. Our lower bound exceeds that previously reported. The optimal construction encodes the secret value using one or more ramp schemes. [ABSTRACT FROM AUTHOR]

Compressed sensing is now established as an effective method for dimension reduction when the underlying signals are sparse or compressible with respect to some suitable basis or frame. One important, yet under-addressed problem regarding the compressive acquisition of analog signals is how to perform quantization. This is directly related to the important issues of how “compressed” compressed sensing is (in terms of the total number of bits one ends up using after acquiring the signal) and ultimately whether compressed sensing can be used to obtain compressed representations of suitable signals. In this paper, we propose a concrete and practicable method for performing “analog-to-information conversion”. Following a compressive signal acquisition stage, the proposed method consists of a quantization stage, based on $ \Sigma \Delta $ (sigma-delta) quantization, and a subsequent encoding (compression) stage that fits within the framework of compressed sensing seamlessly. We prove that, using this method, we can convert analog compressive samples to compressed digital bitstreams and decode using tractable algorithms based on convex optimization. We prove that the proposed analog-to-information converter (AIC) provides a nearly optimal encoding of sparse and compressible signals. Finally, we present numerical experiments illustrating the effectiveness of the proposed AIC. [ABSTRACT FROM AUTHOR]

This paper investigates the downlink of a cloud radio access network (C-RAN) in which a central processor communicates with two mobile users through two base stations (BSs). The BSs act as relay nodes and cooperate with each other through error-free rate-limited links. We develop and analyze two coding schemes for this scenario. The first coding scheme modifies the Liu–Kang scheme (to make it amenable to a rigorous analysis) and extends it to introduce common codewords and to apply for downlink C-RAN with BS-to-BS cooperation. This first coding scheme enables arbitrary correlation among the auxiliary codewords that are recovered by the BSs. We show that this scheme improves over previous schemes for various instances of Gaussian C-RAN channels. In particular, in many scenarios, the scheme can better exploit the possibility of BS-to-BS cooperation than other schemes. The second coding scheme extends the distributed decode and forward (DDF) scheme by means of Gray–Wyner compression and by exploiting the cooperation links between BSs. In addition and as a separate extension, we provide an improved capacity approximation for the DDF strategy for the capacity of a general $N$ -BS $L$ -user C-RAN model in the memoryless Gaussian case. [ABSTRACT FROM AUTHOR]

We consider the problem of information embedding where the encoder modifies a white Gaussian host signal in a power-constrained manner to encode a message, and the decoder recovers both the embedded message and the modified host signal. This partially extends the recent work of Sumszyk and Steinberg to the continuous-alphabet Gaussian setting. Through a control-theoretic lens, we observe that the problem is a minimalist example of what is called the triple role of control actions. We show that a dirty-paper-coding strategy achieves the optimal rate for perfect recovery of the modified host and the message for any message rate. For imperfect recovery of the modified host, by deriving bounds on the minimum mean-square error (MMSE) in recovering the modified host signal, we show that Dirty-Paper Coding-based strategies are guaranteed to attain within a uniform constant factor of 16 of the optimal weighted sum of power required in host signal modification and the MMSE in the modified host signal reconstruction for all weights and all message rates. When specialized to the zero-rate case, our results provide the tightest known lower bounds on the asymptotic costs for the vector version of a famous open problem in decentralized control: the Witsenhausen counterexample. Numerically, this tighter bound helps us characterize the asymptotically optimal costs for the vector Witsenhausen problem to within a factor of 1.3 for all problem parameters, improving on the earlier best known bound of 2. [ABSTRACT FROM AUTHOR]

This paper presents polar coding schemes for the two-user discrete memoryless broadcast channel (DM-BC) which achieve Marton’s region with both common and private messages. This is the best achievable rate region known to date, and it is tight for all classes of two-user DM-BCs whose capacity regions are known. To accomplish this task, we first construct polar codes for both the superposition as well as binning strategy. By combining these two schemes, we obtain Marton’s region with private messages only. Finally, we show how to handle the case of common information. The proposed coding schemes possess the usual advantages of polar codes, i.e., they have low encoding and decoding complexity and a superpolynomial decay rate of the error probability. We follow the lead of Goela, Abbe, and Gastpar, who recently introduced polar codes emulating the superposition and binning schemes. To align the polar indices, for both schemes, their solution involves some degradedness constraints that are assumed to hold between the auxiliary random variables and channel outputs. To remove these constraints, we consider the transmission of $k$ blocks and employ a chaining construction that guarantees the proper alignment of the polarized indices. The techniques described in this paper are quite general, and they can be adopted to many other multiterminal scenarios whenever there polar indices need to be aligned. [ABSTRACT FROM AUTHOR]

In this paper, we use entropy functions to characterize the set of rate-capacity tuples achievable with either zero decoding error, or vanishing decoding error, for general network coding problems for acyclic networks. We show that when sources are colocated, the outer bound is tight and the sets of zero-error achievable and vanishing-error achievable rate-capacity tuples are the same. Then, we extend this paper to networks subject to linear encoding constraints, routing constraints (where some or all nodes can only perform routing), and secrecy constraints. Finally, we show that even for apparently simple networks, design of optimal codes may be difficult. In particular, we prove that for the incremental multicast problem and for the single-source secure network coding problem, characterization of the achievable set can be very hard and linear network codes may not be optimal. [ABSTRACT FROM AUTHOR]

In this paper, we consider different aspects of the problem of compressing for function computation across a network, which we call network functional compression. In network functional compression, computation of a function (or, some functions) of sources located at certain nodes in a network is desired at receiver(s). The rate region of this problem has been considered in the literature under certain restrictive assumptions, particularly in terms of the network topology, the functions, and the characteristics of the sources. In this paper, we present results that significantly relax these assumptions. For a one-stage tree network, we characterize a rate region by introducing a necessary and sufficient condition for any achievable coloring-based coding scheme called coloring connectivity condition. We also propose a modularized coding scheme based on graph colorings to perform arbitrarily closely to rate lower bounds. For a general tree network, we provide a rate lower bound based on graph entropies and show that, this bound is tight in the case of having independent sources. In particular, we show that, in a general tree network case with independent sources, to achieve the rate lower bound, intermediate nodes should perform computations. However, for a family of functions and random variables, which we call chain-rule proper sets, it is sufficient to have no computations at intermediate nodes to perform arbitrarily closely to the rate lower bound. In addition, we consider practical issues of coloring-based coding schemes and propose an efficient algorithm to compute a minimum entropy coloring of a characteristic graph under some conditions on source distributions and/or the desired function. Finally, extensions of these results for cases of having feedback and lossy function computations are discussed. [ABSTRACT FROM AUTHOR]

Rivest and Shamir introduced a write-once memory (WOM), a model of storage devices whose storage elements have restrictions on state transitions, and they presented some coding methods to reuse a WOM. An interesting question about a WOM is how efficiently we can reuse it with the best coding method, and as an answer to the question, Fu and Han Vinck determined the capacity of Fiat and Shamir’s generalized WOMs. In this paper, we extend their results, introducing write-constrained memories (WCMs) that consider state transition costs, and determining the capacity of WCMs under a certain type of cost constraints. [ABSTRACT FROM AUTHOR]

This paper investigates the achievable rates of an additive white Gaussian noise energy-harvesting (EH) channel with an infinite battery. The EH process is characterized by a sequence of blocks of harvested energy, which is known causally at the source. The harvested energy remains constant within a block while the harvested energy across different blocks is characterized by a sequence of independent and identically distributed random variables. The blocks have length $L$ , which can be interpreted as the coherence time of the energy-arrival process. If L$ is a constant or grows sublinearly in the blocklength n$ , we fully characterize the first-order term in the asymptotic expansion of the maximum transmission rate subject to a fixed tolerable error probability \varepsilon $ . The first-order term is known as the \varepsilon for any $\varepsilon $ less than 1/2. The lower bound is obtained through analyzing the save-and-transmit strategy. If $L$ grows linearly in $n$ , we obtain lower and upper bounds on the $\varepsilon $ -capacity, which coincide whenever the cumulative distribution function of the EH random variable is continuous and strictly increasing. In order to achieve the lower bound, we have proposed a novel adaptive save-and-transmit strategy, which chooses different save-and-transmit codes across different blocks according to the energy variation across the blocks. [ABSTRACT FROM PUBLISHER]

In this paper, we propose an open-loop unequal-error-protection querying policy based on superposition coding for the noisy 20 questions problem. In this problem, a player wishes to successively refine an estimate of the value of a continuous random variable by posing binary queries and receiving noisy responses. When the queries are designed non-adaptively as a single block and the noisy responses are modeled as the output of a binary symmetric channel, the 20 questions problem can be mapped to an equivalent problem of channel coding with unequal error protection (UEP). A new non-adaptive querying strategy based on UEP superposition coding is introduced, whose estimation error decreases with an exponential rate of convergence that is significantly better than that of the UEP repetition coding introduced by Variani et al. (2015). With the proposed querying strategy, the rate of exponential decrease in the number of queries matches the rate of a closed-loop adaptive scheme, where queries are sequentially designed with the benefit of feedback. Furthermore, the achievable error exponent is significantly better than that of random block codes employing equal error protection. [ABSTRACT FROM AUTHOR]

The problem of characterizing the fundamental tradeoff between storage and repair bandwidth of exact-repair regenerating codes against a passive eavesdropper is studied. The eavesdropper is assumed to be capable of observing the data stored in a fixed number of nodes and the data involved in the repair of these nodes. In this paper, the tradeoff for regenerating codes with small parameters is characterized, and then, the results are extended to some general settings. [ABSTRACT FROM PUBLISHER]

Noisy channels are a powerful resource for cryptography as they can be used to obtain information-theoretic secure key agreement, commitment, and oblivious transfer protocols, among others. Oblivious transfer (OT) is a fundamental primitive, since it is complete for secure multi-party computation, and the OT capacity characterizes how efficiently a channel can be used for obtaining string oblivious transfer. Ahlswede and Csiszár (ISIT’07) presented upper and lower bounds on the OT capacity of generalized erasure channels (GECs) against passive adversaries. In the case of GEC with erasure probability at least 1/2, the upper and lower bounds match and, therefore, the OT capacity was determined. It was later proved by Pinto et al. [IEEE Trans. Inf. Theory 57(8)] that the OT capacity is identical for passive and malicious adversaries. In the case of GEC with erasure probability smaller than 1/2, the known lower bound against passive adversaries that was established by Ahlswede and Csiszár does not match their upper bound and it was unknown whether this OT rate could be achieved against malicious adversaries as well. In this paper, we show that there is a protocol against malicious adversaries achieving the same OT rate that was obtained against passive adversaries. We obtain our results by a new combination of interactive hashing and typicality tests that are suitable for dealing with the case of low erasure probability ( p^* <1/2 ). [ABSTRACT FROM PUBLISHER]

This paper studies the performance of sparse regression codes for lossy compression with the squared-error distortion criterion. In a sparse regression code, code words are linear combinations of subsets of columns of a design matrix. It is shown that with minimum-distance encoding, sparse regression codes achieve the Shannon rate-distortion function for i.i.d. Gaussian sources R^ (D) as well as the optimal excess-distortion exponent. This completes a previous result which showed that R^ (D) and the optimal exponent were achievable for distortions below a certain threshold. The proof of the rate-distortion result is based on the second moment method, a popular technique to show that a non-negative random variable $X$ is strictly positive with high probability. In our context, $X$ is the number of code words within target distortion $D$ of the source sequence. We first identify the reason behind the failure of the standard second moment method for certain distortions, and illustrate the different failure modes via a stylized example. We then use a refinement of the second moment method to show that R^ (D) is achievable for all distortion values. Finally, the refinement technique is applied to Suen’s correlation inequality to prove the achievability of the optimal Gaussian excess-distortion exponent. [ABSTRACT FROM AUTHOR]

This paper revisits the Gaussian degraded relay channel, where the link that carries information from the source to the destination is a physically degraded version of the link that carries information from the source to the relay. The source and the relay are subject to expected power constraints. The $\varepsilon $ -capacity of the channel is characterized and it is strictly larger than the capacity for any $\varepsilon >0$ , which implies that the channel does not possess the strong converse property. The proof of the achievability part is based on several key ideas: block Markov coding, which is used in the classical decode-forward strategy, power control for Gaussian channels under expected power constraints, and a careful scaling between the block size and the total number of block uses. The converse part is proved by first establishing two non-asymptotic lower bounds on the error probability, which are derived from the type-II errors of some binary hypothesis tests. Subsequently, each lower bound is simplified by conditioning on an event related to the power of some linear combination of the codewords transmitted by the source and the relay. Lower and upper bounds on the second-order term of the optimal coding rate are also obtained. [ABSTRACT FROM PUBLISHER]

It was previously shown by Hashimoto that Forney’s optimal erasure decoder can be significantly simplified, in the sense that a simplified decoder achieves the same random coding bounds, for the ensemble of independent and identically distributed codewords. In this paper, the analysis of simplified decoders is refined and generalized in several aspects. First, tighter random coding bounds for simplified decoders are derived, which equal the exact exponential behavior of the fixed composition ensemble average. Second, the exponential bounds are valid both in the erasure mode and in the list mode. Third, the analysis pertains to a rather general class of simplified decoders, including the case of mismatch in the threshold function of the decoder. Fourth, expurgated exponents, which are larger than the random coding exponents at low rates, are shown to be achievable using a significantly simpler decoder than Forney’s optimal decoder. It is shown numerically that, from the aspect of exact random coding exponents, a decoder in the spirit of Hashimoto’s is as good as Forney’s in the erasure mode, as well as in the list mode. [ABSTRACT FROM PUBLISHER]

This paper introduces a convenient strategy for coding and predicting sequences of independent, identically distributed random variables generated from a large alphabet of size $m$ . In particular, the size of the sample is allowed to be variable. The employment of a Poisson model and tilting method simplifies the implementation and analysis through independence. The resulting strategy is optimal within the class of distributions satisfying a moment condition, and it is close to optimal for the class of all i.i.d distributions on strings of a given length. The method also can be used to code and predict strings with a condition on the tail of the ordered counts, and it can be applied to distributions in an envelope class. Moreover, we show that our model permits exact computation of the minimax optimal code, for all alphabet sizes, when conditioning on the size of the sample. [ABSTRACT FROM PUBLISHER]

Group-testing refers to the problem of identifying (with high probability) a (small) subset of D defectives from a (large) set of N items via a “small” number of “pooled” tests (i.e., tests that have a positive outcome if at least one of the items being tested in the pool is defective, else have a negative outcome). For ease of presentation in this paper, we focus on the regime when D = \mathcal O(N^1- \delta ) for some \delta > 0 . The tests may be noiseless or noisy, and the testing procedure may be adaptive (the pool defining a test may depend on the outcome of a previous test), or non-adaptive (each test is performed independent of the outcome of other tests). A rich body of the literature demonstrates that \Theta (D\log (N)) tests are information-theoretically necessary and sufficient for the group-testing problem, and provides algorithms that achieve this performance. However, it is only recently that reconstruction algorithms with computational complexities that are sub-linear in N have started being investigated. In the scenario with adaptive tests with noisy outcomes, we present the first scheme that is simultaneously order-optimal (up to small constant factors) in both the number of tests and the decoding complexity ( \mathcal O\left (D\log (N)\right ) in both the performance metrics). The total number of stages of our adaptive algorithm is “small” ( \mathcal O\left (\log (D)\right ) ). Similarly, in the scenario with non-adaptive tests with noisy outcomes, we present the first scheme that is simultaneously near-optimal in both the number of tests and the decoding complexity (via an algorithm that requires \mathcal O\left (D\log (D)\log (N)\right ) tests and has a decoding complexity of \mathcal O(D(\log N+\log ^2D)) . Finally, we present an adaptive algorithm that only requires two stages, and for which both the number of tests and the decoding complexity scale as \mathcal O(D(\log N+\log ^2D)) . For all three settings, the probability of error of our algorithms scales as \mathcal O\left (1/(poly(D)\right ) . For each of the statements mentioned earlier about the order of the number of measurements, decoding complexity, and probability of error, we provide explicitly computed “small” universal factors in our theorem statements. [ABSTRACT FROM PUBLISHER]

An information theoretical analysis of nonadaptive group testing schemes based on sparse pooling graphs is presented. A pooling graph is a bipartite graph for which the adjacency matrix is a pooling matrix. The binary status of the objects to be tested are modeled by independent identically distributed. Bernoulli random variables with probability $p$ . An $(l, r, n)$ -regular pooling graph is a bipartite graph in which the left nodes have degree $l$ , the right nodes have degree $r$ , and $n$ is the number of left nodes. The main contribution of this paper is a direct coding theorem that gives the conditions for the existence of an estimator that can achieve an arbitrarily small probability of error. An estimator is a function that uses observations to infer the state of an object. The direct coding theorem is proved by averaging the upper bound on the probability of the estimation error of the typical set estimator over an $(l, r, n)$ -regular pooling graph ensemble. Numerical results indicate sharp threshold behaviors in the asymptotic regime. These results can provide a concrete benchmark for nonadaptive group testing of existing and emerging detection algorithms over a noiseless system. [ABSTRACT FROM PUBLISHER]

An open problem in polarization theory is to determine the binary operations that always lead to polarization (in the general multilevel sense) when they are used in Arıkan style constructions. This paper, which is presented in two parts, solves this problem by providing a necessary and sufficient condition for a binary operation to be polarizing. This (second) part provides a foundation of polarization theory based on the ergodic theory of binary operations which we developed in the first part. We show that a binary operation is polarizing if and only if it is uniformity preserving and its right-inverse is strongly ergodic. The rate of polarization of single user channels is studied. It is shown that the exponent of any polarizing operation cannot exceed \frac 12 , which is the exponent of quasi-group operations. We also study the polarization of multiple access channels (MAC). In particular, we show that a sequence of binary operations is MAC-polarizing if and only if each binary operation in the sequence is polarizing. It is shown that the exponent of any MAC-polarizing sequence cannot exceed \frac 12 , which is the exponent of sequences of quasi-group operations. [ABSTRACT FROM AUTHOR]

The best known inner bound for the two-user discrete memoryless interference channel is the Han–Kobayashi rate region. The coding schemes that achieve this region are based on rate-splitting and superposition coding. In this paper, we develop a multicoding scheme to achieve the same rate region. A key advantage of the multicoding nature of the proposed coding scheme is that it can be naturally extended to more general settings, such as when encoders have state information or can overhear each other. In particular, we extend our coding scheme to characterize the capacity region of the state-dependent deterministic Z-interference channel when noncausal state information is available at the interfering transmitter. We specialize our results to the case of the linear deterministic model with ON/OFF interference, which models a wireless system where a cognitive transmitter is noncausally aware of the times it interferes with a primary transmission. For this special case, we provide an explicit expression for the capacity region and discuss some interesting properties of the optimal strategy. We also extend our multicoding scheme to find the capacity region of the deterministic Z-interference channel when the signal of the interfering transmitter can be overheard at the other transmitter (also known as unidirectional partial cribbing). [ABSTRACT FROM PUBLISHER]

In this paper, we investigate problems of communication over physically degraded, state-dependent broadcast channels (BCs) with cooperating decoders. Two different setups are considered, and their capacity regions are characterized. First, we study a setting in which one decoder can use a finite capacity link to send the other decoder information regarding the messages or the channel states. In this scenario, we analyze two cases: one, where noncausal state information, is available to the encoder and the strong decoder, and the other, where state information, is available only to the encoder in a causal manner. Second, we examine a setting in which the cooperation between the decoders is limited to taking place before the outputs of the channel are given. In this case, one decoder, which is informed of the state sequence noncausally, can cooperate only to send the other decoder rate-limited information about the state sequence. The proofs of the capacity regions introduce a new idea of coding for channels with cooperation between different users, where we exploit the link between the decoders for multiple binnings. Finally, we discuss the optimality of using rate-splitting techniques when coding for cooperative BCs. In particular, we show that rate splitting is not necessarily optimal when coding for cooperative BCs by solving an example in which our method of coding outperforms rate splitting. [ABSTRACT FROM AUTHOR]

We propose two coding schemes for the two-receiver discrete memoryless broadcast channel (BC) with rate-limited feedback from one or both receivers. They improve over the no feedback capacity region for a large class of channels, including the class of strictly essentially less-noisy BCs that we introduce in this paper. Examples of strictly essentially less-noisy BCs are the binary symmetric BC or the binary erasure BC with unequal crossover or erasure probabilities at the two receivers. When the feedback rates are sufficiently large, our schemes recover all previously known capacity results for discrete memoryless BCs with feedback. In both our schemes, we let the receivers feedback quantization messages about their receive signals. In the first scheme, the transmitter simply relays the quantization information obtained from Receiver 1 to Receiver 2, and vice versa. This provides each receiver with a second observation of the input signal and can thus improve its decoding performance unless the BC is physically degraded. Moreover, each receiver uses its knowledge of the quantization message describing its own outputs so as to attain the same performance as if this message had not been transmitted at all. In our second scheme, the transmitter first reconstructs and processes the quantized output signals, and then sends the outcome as a common update information to both receivers. A special case of our second scheme also applies to memoryless BCs without feedback but with strictly causal state-information at the transmitter and causal state-information at the receivers. It recovers all previous achievable regions also for this setup with state-information. [ABSTRACT FROM AUTHOR]

This paper shows that the capacity region of the continuous-time Poisson broadcast channel is achieved via superposition coding for most channel parameter values. Interestingly, the channel in some subset of these parameter values does not belong to any of the existing classes of broadcast channels for which superposition coding is optimal (e.g., degraded, less noisy, and more capable). In particular, we introduce the notion of effectively less noisy broadcast channel and show that it implies less noisy but is not in general implied by more capable. For the rest of the channel parameter values, we show that there is a gap between Marton’s inner bound and the UV outer bound. [ABSTRACT FROM AUTHOR]

We consider the transmission of a memoryless bivariate Gaussian source over a two-user additive Gaussian multiple-access channel with unidirectional conferencing encoders. Here, prior to each transmission block, Encoder 1, which observes the first source component, is allowed to communicate with Encoder 2, which observes the second source component, via a unidirectional noise-free bit-pipe of given capacity. The main results of this paper are sufficient conditions and a necessary condition for the achievability of a distortion pair expressed as a function of the channel \sf SNR and of the source correlation. The main sufficient condition is obtained by an extension of the vector-quantizer scheme suggested by Lapidoth–Tinguely, for the case without conferencing, to the case with unidirectional conference. In the high- \sf SNR regime, and when the capacity of the conference channel is unlimited, these necessary and sufficient conditions are shown to agree. We evaluate the precise high- \sf SNR asymptotics for a subset of distortion pairs when the capacity of the conference channel is unlimited in which case we show that a separation-based scheme attains these optimal distortion pairs. However, with symmetric average-power constraints and fixed conferencing capacity, at high- \sf SNR , the latter separation-based scheme is shown to be suboptimal. [ABSTRACT FROM AUTHOR]

In this paper, the multiple access channel (MAC) with combined cooperation and partial cribbing is studied, and its capacity region is characterized. Cooperation means that each of the two encoders sends a message to the other via a rate-limited link prior to transmission, while partial cribbing means that each of the two encoders obtains a deterministic function of the other encoder’s output with or without delay. Prior work in this field dealt separately with cooperation and partial cribbing, but by combining these two methods, we can achieve significantly higher rates. Surprisingly, the capacity region of the MAC with combined cooperation and partial cribbing can be expressed using only one auxiliary random variable (RV) similar to the capacity regions of the MAC with cooperation and with partially cribbing encoders. The reason is that in an optimal coding scheme, the encoders use both cooperation and partial cribbing to generate a common message between the encoders. Furthermore, the Gaussian MAC with combined one-sided cooperation and quantized cribbing is studied. For this model, an achievability scheme is given. This scheme shows how many cooperation or quantization bits are required to practically achieve the capacity region of the Gaussian MAC with full message cooperation or perfect cribbing. To ratify the main results, two additional models are studied. In both models, only one auxiliary RV is needed. The first is a rate distortion dual setting for the MAC with degraded message set and combined cooperation and cribbing. The second is a state-dependent MAC with cooperation, where the state is known at a partially cribbing encoder and at the decoder. However, there are cases where more than one auxiliary RV is needed, e.g., when the cooperation and the cribbing are not used for the same purposes. The MAC with an action-dependent state is presented, where the action is based on the cooperation but not on the cribbing. Therefore, in this case, more than one auxiliary RV is needed. As a result, when the common information shared by the two encoders is used unevenly by the users in the channel, more than one auxiliary RV is needed to express the capacity region. [ABSTRACT FROM AUTHOR]

In this paper, we study the capacity of the diamond channel. We focus on the special case where the channel between the source node and the two relay nodes are two separate links with finite capacities and the link from the two relay nodes to the destination node is a Gaussian multiple access channel. We call this model the Gaussian multiple access diamond channel. We first propose an upper bound on the capacity. This upper bound is a single-letterization of an $n$ -letter upper bound proposed by Traskov and Kramer, and is tighter than the cut-set bound. As for the lower bound, we propose an achievability scheme based on sending correlated codes through the multiple access channel with superposition structure. We then specialize this achievable rate to the Gaussian multiple access diamond channel. Noting the similarity between the upper and lower bounds, we provide sufficient and necessary conditions that a Gaussian multiple access diamond channel has to satisfy such that the proposed upper and lower bounds meet. Thus, for a Gaussian multiple access diamond channel that satisfies these conditions, we have found its capacity. [ABSTRACT FROM PUBLISHER]

We consider the problem of channel state amplification in a Gaussian channel with additive Gaussian channel states, where the encoder observes noncausally a noisy version of these states. A complete characterization is provided for the minimum reconstruction distortion under a transmitter power constraint, and it is shown that a simple analog scheme with power control is optimal. More precisely, if the power available to the encoder is below certain threshold, the analog scheme using full power is optimal, however, when the power available to the encoder is above that threshold, analog transmission using only a fixed amount of the available power is optimal. Furthermore, the problem of simultaneous message transmission and Gaussian state amplification with noisy observations is studied, for which an inner bound and two nontrivial outer bounds to the optimal tradeoff between the transmission rate and the state reconstruction distortion are provided. The coding scheme underlying the inner bound combines analog signaling and Gelfand-Pinsker coding, where the latter deviates from the operating point of Costa’s dirty paper coding. The first outer bound is obtained by extending the channel decomposition technique, while the second outer bound requires a strategic analysis of the covariance matrix of the relevant random variables. [ABSTRACT FROM AUTHOR]

This paper studies a Shannon-theoretic version of the generalized distribution preserving quantization problem where a stationary and memoryless source is encoded subject to a distortion constraint and the additional requirement that the reproduction also be stationary and memoryless with a given distribution. The encoder and decoder are stochastic and assumed to have access to independent common randomness. Recent work has characterized the minimum achievable coding rate at a given distortion level when unlimited common randomness is available. Here, we consider the general case where the available common randomness may be rate limited. Our main result completely characterizes the set of achievable coding and common randomness rate pairs at any distortion level, thereby providing the optimal tradeoff between these two rate quantities. We also consider two variations of this problem where we investigate the effect of relaxing the strict output distribution constraint and the role of private randomness used by the decoder on the rate region. Our results have strong connections with Cuff’s recent work on distributed channel synthesis. In particular, our achievability proof combines a coupling argument with the approach developed by Cuff, where instead of explicitly constructing the encoder–decoder pair, a joint distribution is constructed from which a desired encoder–decoder pair is established. We show, however, that for our problem, the separated solution of first finding an optimal channel and then synthesizing this channel results in a suboptimal rate region. [ABSTRACT FROM AUTHOR]

This paper studies the fundamental limits of the minimum average length of lossless and lossy variable-length compression, allowing a nonzero error probability \epsilon , for lossless compression. We give nonasymptotic bounds on the minimum average length in terms of Erokhin’s rate-distortion function and we use those bounds to obtain a Gaussian approximation on the speed of approach to the limit, which is quite accurate for all but small blocklengths: (1 - \epsilon ) k H(\mathsf S) - {({({k V(\mathsf S)}/{2 \pi })})}^{1/2} \mathop {\rm exp}[- ({( Q^{-1}\left ({\epsilon }\right ))^{2}}/{2})] , where Q^{-1}\left ({\cdot }\right )$ is the functional inverse of the standard Gaussian complementary cumulative distribution function, and $V(\mathsf S)$ is the source dispersion. A nonzero error probability thus not only reduces the asymptotically achievable rate by a factor of $1 - \epsilon $ , but this asymptotic limit is approached from below, i.e., larger source dispersions and shorter blocklengths are beneficial. Variable-length lossy compression under an excess distortion constraint is shown to exhibit similar properties. [ABSTRACT FROM PUBLISHER]

This paper shows that the Maddah-Ali–Tse (MAT) scheme, which achieves the symmetric capacity of two example broadcast channels with strictly causal state information at the transmitter, is a simple special case of the Shayevitz–Wigger (SW) scheme for the broadcast channel with generalized feedback, which involves block Markov coding, Gray–Wyner compression, superposition coding, and Marton coding. Focusing on the class of symmetric broadcast channels with state, we derive an expression for the maximum achievable symmetric rate using the SW scheme. We show that the MAT results for the two-receiver case can be recovered by evaluating this expression for the special case in which superposition coding and Marton coding are not used. We then introduce a new broadcast channel example that shares many features of the MAT examples. We show that another special case of our maximum symmetric rate expression in which superposition coding is also used attains a higher symmetric rate than the MAT scheme. The symmetric capacity of this new example is not known, however. [ABSTRACT FROM PUBLISHER]

In a network, a node is said to incur a delay if its encoding of each transmitted symbol involves only its received symbols obtained before the time slot in which the transmitted symbol is sent (hence the transmitted symbol sent in a time slot cannot depend on the received symbol obtained in the same time slot). A node is said to incur no delay if its received symbol obtained in a time slot is available for encoding its transmitted symbol sent in the same time slot. Under the classical model, every node in a discrete memoryless network (DMN) incurs a unit delay, and the capacity region of the DMN satisfies the well-known cut-set outer bound. In this paper, we propose a generalized model for the DMN where some nodes may incur no delay. Under our generalized model, we obtain a new cut-set outer bound, which is proved to be tight for some two-node DMN and is shown to subsume an existing cut-set bound for the causal relay network. In addition, we establish under the generalized model another cut-set outer bound on the positive-delay region—the set of achievable rate tuples under the constraint that every node incurs a delay. We use the cut-set bound on the positive-delay region to show that for some two-node DMN under the generalized model, the positive-delay region is strictly smaller than the capacity region. [ABSTRACT FROM PUBLISHER]