Search

In this paper, we revisit the problem of finding the longest systematic-length k for a linear minimum storage regenerating (MSR) code with optimal repair of only systematic part, for a given per-node storage capacity l and an arbitrary number of parity nodes r. We study the problem by following a geometric analysis of linear subspaces and operators. First, a simple quadratic bound is given, which implies that k = r + 2 is the largest number of systematic nodes in the scalar scenario. Second, an r-based-log bound is derived, which is superior to the upper bound on log-base 2 in the prior work. Finally, an explicit upper bound depending on the value of r 2 /l is introduced, which further extends the corresponding result in the literature. [ABSTRACT FROM AUTHOR]

Quadratic residue codes are a well-known class of codes. In this paper, we consider the constructions of self-dual codes by higher power residues, especially fourth power residues. New infinite families of self-dual codes over GF(2), GF(3), GF(4), GF(8), and GF(9) are introduced. Some of them have better minimum weight than previously known codes. We also give general results related to the automorphism group of some of these codes. [ABSTRACT FROM PUBLISHER]

Shannon’s capacity and rate-distortion function, combined with the separation principle, provide tight bounds for the minimum possible distortion in joint source-channel coding. These bounds, however, are usually achievable only in the limit of a large block length. In their 1973 paper, Ziv and Zakai introduced a family of alternative capacity and rate-distortion functions, based on functionals satisfying the data-processing inequality, which potentially give tighter bounds for systems with a small block length. There is a considerable freedom as to how to choose those functionals, and the ways of finding the best possible functionals yielding the best bounds for a given source-channel combination are not specified. We examine recently conjectured high SNR asymptotic expressions for the Ziv–Zakai bounds, based on the Rényi-divergence functional. We derive nonasymptotic bounds on the Ziv–Zakai–Rényi rate-distortion function and capacity for a broad class of sources and additive noise channels, which hold for arbitrary SNR and prove the conjectured asymptotic expressions in the limit of a small distortion/high SNR. The results lead to new bounds on the best achievable distortion in finite dimensional joint source-channel coding. Examples are presented where the new bounds achieve significant improvement upon Shannon’s original bounds. [ABSTRACT FROM PUBLISHER]

This paper studies new bounds and code constructions that are applicable to the combinatorial granular channel model previously introduced by Sharov and Roth. We derive new bounds on the maximum cardinality of a grain-error-correcting code and propose constructions of codes that correct grain-errors. We demonstrate that a permutation of the classical group codes (e.g., Constantin–Rao codes) can correct a single grain-error. In many cases of interest, our results improve upon the currently best known bounds and constructions. Some of the approaches adopted in the context of grain-errors may have application to related channel models. [ABSTRACT FROM AUTHOR]

In this paper, we study the asymptotic performance of Abelian group codes for the channel coding problem for arbitrary discrete (finite alphabet) memoryless channels as well as the lossy source coding problem for arbitrary discrete (finite alphabet) memoryless sources. For the channel coding problem, we find the capacity characterized in a single-letter information-theoretic form. This simplifies to the symmetric capacity of the channel when the underlying group is a field. For the source coding problem, we derive the achievable rate-distortion function that is characterized in a single-letter information-theoretic form. When the underlying group is a field, it simplifies to the symmetric rate-distortion function. We give several illustrative examples. Due to the nonsymmetric nature of the sources and channels considered, our analysis uses a synergy of information-theoretic and group-theoretic tools. [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]

This paper studies fixed-rate randomized vector quantization under the constraint that the quantizer’s output has a given fixed probability distribution. A general representation of randomized quantizers that includes the common models in the literature is introduced via appropriate mixtures of joint probability measures on the product of the source and reproduction alphabets. Using this representation and results from optimal transport theory, the existence of an optimal (minimum distortion) randomized quantizer having a given output distribution is shown under various conditions. For sources with densities and the mean square distortion measure, it is shown that this optimum can be attained by randomizing quantizers having convex codecells. For stationary and memoryless source and output distributions, a rate-distortion theorem is proved, providing a single-letter expression for the optimum distortion in the limit of large blocklengths. [ABSTRACT FROM PUBLISHER]

Baranyai’s theorem is well known in the theory of hypergraphs. A corollary of this theorem says that one can partition the family of all \(u\) -subsets of an \(n\) -element set into \({n-1\choose u-1}\) subfamilies such that each subfamily forms a partition of the \(n\) -element set, where \(n\) is divisible by \(u\) . In this paper, we present a coding-theoretic application of Baranyai’s theorem. More precisely, we propose a combinatorial construction of locally decodable codes. Locally decodable codes are error-correcting codes that allow the recovery of any message symbol by looking at only a few symbols of the codeword. The number of looked codeword symbols is called query complexity. Such codes have attracted a lot of attention in recent years. The Walsh–Hadamard code is a well-known binary two-query locally decodable code of exponential length that can recover any message bit using 2 bits of the codeword. Our construction can give locally decodable codes over small finite fields for any constant query complexities. In particular, it gives a ternary two-query locally decodable code of length asymptotically shorter than the Walsh–Hadamard code. [ABSTRACT FROM PUBLISHER]

Write-once memory (WOM) is a storage medium with memory elements, called cells, which can take on \(q\) levels. Each cell is initially in level 0 and can only increase its level. A \(t\) -write WOM code is a coding scheme, which allows one to store \(t\) messages to the WOM such that on consecutive writes every cell’s level does not decrease. The sum-rate of the WOM code, which is the ratio between the total amount of information written in the \(t\) writes and number of memory cells, is bounded by \(\log (t+1)\) . Our main contribution in this paper is a construction of binary three-write WOM codes with sum-rate approaching 1.885 for sufficiently large number of cells, whereas the upper bound is 2. This improves upon a recent construction of sum-rate 1.809. A key ingredient in our construction is a recent capacity achieving construction of two-write WOM codes, which uses the so-called Wozencraft ensemble of linear codes. In our construction, we encode information in the first and second write in a way that leaves a large number (roughly half) of the cells nonprogrammed. This allows us to use the above two-write construction in order to invoke a third write to the memory. We also give specific constructions of nonbinary two-write WOM codes and multiple writes, which give better sum-rate than the currently best known ones. In the construction of these codes, we build upon previous nonbinary constructions and show how tools such symbols relabeling can help in achieving high sum-rates. [ABSTRACT FROM PUBLISHER]

The two-user compound Gaussian MIMO broadcast channel models the situation where each user has a finite set of possible realizations. The transmitter sends two messages, one for each user, such that each user must be able to decode its message regardless of the actual realization. This channel also models a broadcast channel (BC) with two groups of users and two messages, with one message intended for each group of users. Weingarten et al. established the capacity region for the degraded case where the realizations/users exhibit a degradedness order. The degradedness order is defined through an additional realization/user where the realizations/users from one set are degraded with respect to him and where he is degraded with respect to the realizations/users from the other set. To show that Gaussian inputs attain the capacity region, they proved a new extremal inequality and employed the use of the channel enhancement technique as well. In this paper, we extend the result to the \(N\) -user degraded compound Gaussian MIMO BC, where the \(N\) users exhibit a degradedness order similar to the two-user case. We first prove a generalization of the extremal inequality considered by Weingarten et al.; instead of considering the difference between the weighted sum of two sets of conditional differential entropies, we consider the summation of \(N-1\) sets of such differences, where the conditioning random variables of the \(N-1\) sets form a Markov chain. Our proof relies on the Gaussian perturbation approach, the necessary KKT conditions as well as a data processing inequality. Finally, we specialize the generalized extremal inequality to characterize the capacity region of the \(N\) -user degraded compound Gaussian MIMO BC. By making appropriate use of the necessary KKT conditions, we are able to do away with the use of the channel enhancement technique that was employed in the proof of the capacity region of the two-user case. [ABSTRACT FROM AUTHOR]

We study a two-transmitter two-receiver network where Receiver 1 can only hear the transmitted signal of Transmitter 1. Transmitter 1 has two messages, one of which is intended for Receiver 1 while both are intended for Receiver 2. Transmitter 2 has one message which is intended for Receiver 2. We call this channel model the Z channel with degraded message sets. For networks with the element of distributed encoding, it has been shown that when the multiple access link between the two encoders and the decoder satisfies the conditions proposed by Liu and Goldsmith, capacity results can be obtained for a variety of problems. In this paper, we generalize these conditions and show that for a larger class of multiple access links, the capacity region of the Z channel with degraded message sets can be characterized despite the presence of distributed encoding. [ABSTRACT FROM AUTHOR]

We study the transmission of correlated sources over discrete memoryless (DM) multiple-access-relay channels (MARCs), in which both the relay and the destination have access to side information arbitrarily correlated with the sources. As the optimal transmission scheme is an open problem, in this paper, we propose a new joint source-channel coding scheme based on a novel combination of the correlation preserving mapping (CPM) technique with Slepian–Wolf (SW) source coding, and obtain the corresponding sufficient conditions. The proposed coding scheme is based on the decode-and-forward strategy, and utilizes CPM for encoding information simultaneously to the relay and the destination, whereas the cooperation information from the relay is encoded via SW source coding. It is shown that there are cases in which the new scheme strictly outperforms the schemes available in the literature. This is the first instance of a source-channel code that uses CPM for encoding information to two different nodes (relay and destination). In addition to sufficient conditions, we present three different sets of single-letter necessary conditions for reliable transmission of correlated sources over DM MARCs. The newly derived conditions are shown to be at least as tight as the previously known necessary conditions. [ABSTRACT FROM AUTHOR]

Consider a binary-input memoryless output-symmetric channel \(W\) . Such a channel has a capacity, call it \(I(W)\) , and for any \(R0\) , then the required block-length \(N\) scales in terms of the rate \(R < I(W)\) as \(N \geq {\alpha }/{(I(W)-R)^{\underline {\mu }}}\) , where \(\alpha \) is a positive constant that depends on \(P_{\rm e}\) and \(I(W)\) . We show that \(\underline {\mu } = 3.579\) is a valid choice, and we conjecture that indeed the value of \(\underline {\mu }\) can be improved to \(\underline {\mu }=3.627\) , the parameter for the binary erasure channel. Also, we show that with the same requirement on the sum of Bhattacharyya parameters, the block-length scales in terms of the rate like \(N \leq {\beta }/{(I(W)-R)^{\overline {\mu }}}\) , where \(\beta \) is a constant that depends on \(P_{\rm e}\) and \(I(W)\) , and \(\overline {\mu }=6\) . [ABSTRACT FROM PUBLISHER]

The problem of simultaneously generating a secret key (SK) and private key (PK) pair among three terminals via public discussion is investigated. In this problem, each terminal observes a component of correlated sources. All three terminals are required to generate the common SK to be concealed from an eavesdropper that has access to the public discussion, while two designated terminals are required to generate an extra PK to be concealed from both the eavesdropper and the remaining terminal. An outer bound on the SK-PK capacity region was established by Ye and Narayan, and was shown to be achievable for a special case. In this paper, the SK-PK capacity region is established in general by developing schemes to achieve the outer bound for the remaining two cases. The main technique lies in the novel design of a random binning-joint decoding scheme that achieves the existing outer bound. [ABSTRACT FROM AUTHOR]

Distributed storage systems for large-scale applications typically use replication for reliability. Recently, erasure codes were used to reduce the large storage overhead, while increasing data reliability. A main limitation of off-the-shelf erasure codes is their high-repair cost during single node failure events. A major open problem in this area has been the design of codes that: 1) are repair efficient and 2) achieve arbitrarily high data rates. In this paper, we explore the repair metric of locality, which corresponds to the number of disk accesses required during a single node repair. Under this metric, we characterize an information theoretic tradeoff that binds together the locality, code distance, and storage capacity of each node. We show the existence of optimal locally repairable codes (LRCs) that achieve this tradeoff. The achievability proof uses a locality aware flow-graph gadget, which leads to a randomized code construction. Finally, we present an optimal and explicit LRC that achieves arbitrarily high data rates. Our locality optimal construction is based on simple combinations of Reed–Solomon blocks. [ABSTRACT FROM AUTHOR]

Consider a systematic linear code where some (local) parity symbols depend on few prescribed symbols, whereas other (heavy) parity symbols may depend on all data symbols. Such codes have been studied recently in the context of erasure coding for data storage, where the local parities facilitate fast recovery of any single symbol when it is erased, whereas the heavy parities provide tolerance to a large number of simultaneous erasures. A code as above is maximally recoverable, if it corrects all erasure patterns, which are information theoretically correctable given the prescribed dependence relations between data symbols and parity symbols. In this paper, we present explicit families of maximally recoverable codes with locality. We also initiate the general study of the tradeoff between maximal recoverability and alphabet size. [ABSTRACT FROM AUTHOR]

Multimedia fingerprinting is an effective technique to trace the sources of pirate copies of copyrighted multimedia contents. Separable codes were introduced to detect colluders taking part in the averaging attack, which is the most feasible approach to perform a collusion attack. In this paper, we provide some improved bounds for the size of separable codes. Using a combinatorial technique named grouping coordinates, we have greatly reduced the upper bound. On the other hand, we also provide some lower bounds for the size of separable codes by both probabilistic and deterministic construction methods. In particular, \( \overline {2}\) -separable codes with asymptotically optimal rate are obtained by the deletion method. [ABSTRACT FROM AUTHOR]

Let \(m\geq 3\) be an odd integer and \(p\) be an odd prime. In this paper, a number of classes of three-weight cyclic codes \(\mathcal {C}_{(1,e)}\) over \(\mathbb {F}_{p}\) , which have parity-check polynomial \(m_1(x)m_e(x)\) , are presented by examining general conditions on the parameters \(p\) , \(m\) , and \(e\) , where \(m_i(x)\) is the minimal polynomial of \(\pi ^{-i}\) over \(\mathbb {F}_{p}\) for a primitive element \(\pi \) of \(\mathbb {F}_{p^m}\) . Furthermore, for \(p\equiv 3 \pmod {4}\) and a positive integer \(e\) satisfying \((p^k+1)\cdot e\equiv 2 \pmod {p^m-1}\) for some positive integer \(k\) with \(\gcd (m,k)=1\) , the value distributions of the exponential sums \(T(a,b)=\sum \nolimits _{x\in \mathbb {F}_{p^m}}\omega ^{ \text {Tr}(ax+bx^e)}\) and \(S(a,b,c)=\sum \nolimits _{x\in \mathbb {F}_{p^m}}\omega ^{ \text {Tr}(ax+bx^e+cx^s)},\) where \(s=(p^m-1)/2\) , are determined. As an application, the value distribution of \(S(a,b,c)\) is utilized to derive the weight distribution of the cyclic codes \(\mathcal {C}_{(1,e,s)}\) with parity-check polynomial \(m_1(x)m_e(x)m_s(x)\) . In the case of \(p=3\) and even \(e\) satisfying the above condition, the dual of the cyclic code \(\mathcal {C}_{(1,e,s)}\) has optimal minimum distance. [ABSTRACT FROM PUBLISHER]

In this paper, the discrete memoryless arbitrarily varying broadcast channel (AVBC) with receiver side information is studied and its random code and deterministic code capacity regions are derived for the average error criterion. In addition, it is analyzed for deterministic list codes and it is shown that the corresponding list capacity region displays a behavior, which is similar to Ahlswede’s famous dichotomy result for the single-user arbitrarily varying channel: it either equals the random code capacity region or otherwise has an empty interior. This is characterized in terms of list sizes at the receivers and an appropriate concept of symmetrizability for the AVBC with receiver side information. The scenario studied here is motivated by the broadcast phase of bidirectional relaying, where a half-duplex relay node establishes a bidirectional communication between two other nodes using a decode-and-forward protocol. The relay decodes the messages both nodes have sent in the initial multiple access phase and broadcasts a re-encoded composition of them in the succeeding broadcast phase. Then, the broadcast phase corresponds to the AVBC with receiver side information, which differs from the classical broadcast channel, since both receivers can exploit their own messages from the previous phase as side information for decoding. [ABSTRACT FROM PUBLISHER]

This paper studies expurgated random-coding bounds and exponents for channel coding with a given (possibly suboptimal) decoding rule. Variations of Gallager’s analysis are presented, yielding several asymptotic and nonasymptotic bounds on the error probability for an arbitrary codeword distribution. A simple nonasymptotic bound is shown to attain an exponent of Csiszár and Körner under constant-composition coding. Using Lagrange duality, this exponent is expressed in several forms, one of which is shown to permit a direct derivation via cost-constrained coding that extends to infinite and continuous alphabets. The method of type class enumeration is studied, and it is shown that this approach can yield improved exponents and better tightness guarantees for some codeword distributions. A generalization of this approach is shown to provide a multiletter exponent that extends immediately to channels with memory. [ABSTRACT FROM PUBLISHER]

The centralized coded caching scheme is a technique proposed by Maddah-Ali and Niesen as a method to reduce the network burden in peak times in a wireless network system. Yan et al. reformulate the problem as designing a corresponding placement delivery array and propose two new schemes from this perspective. These schemes significantly reduce the rate compared with the uncoded caching schemes. However, to implement these schemes, each file should be cut into $F$ pieces, where $F$ grows exponentially with the number of users $K$. Such a constraint is obviously infeasible in the practical setting, especially when $K$ is large. Thus, it is desirable to design caching schemes with constant rate $R$ (independent of $K$ ) as well as smaller $F$. In this paper, we view the centralized coded caching problem in a hypergraph perspective and show that designing a feasible placement delivery array is equivalent to constructing a linear and (6,3)-free 3-uniform 3-partite hypergraph. Several new results and constructions arise from our novel point of view. First, by using the famous (6,3)-theorem in extremal graph theory, we show that constant rate placement delivery arrays with $F$ growing linearly with $K$ do not exist. Second, we present two infinite classes of placement delivery arrays to show that constant rate caching schemes with $F$ growing sub-exponentially with $K$ do exist. [ABSTRACT FROM AUTHOR]

We study a generalization of the setting of regenerating codes, motivated by applications to storage systems consisting of clusters of storage nodes. There are $n$ clusters in total, with $m$ nodes per cluster. A data file is coded and stored across the $mn$ nodes, with each node storing $\alpha $ symbols. For availability of data, we require that the file be retrievable by downloading the entire content from any subset of $k$ clusters. Nodes represent entities that can fail. We distinguish between intra-cluster and inter-cluster bandwidth (BW) costs during node repair. Node-repair in a cluster is accomplished by downloading $\beta $ symbols each from any set of $d$ other clusters, dubbed remote helper clusters, and also up to $\alpha $ symbols each from any set of $\ell $ surviving nodes, dubbed local helper nodes, in the host cluster. We first identify the optimal trade-off between storage-overhead and inter-cluster repair-bandwidth under functional repair, and also present optimal exact-repair code constructions for a class of parameters. The new trade-off is strictly better than what is achievable via space-sharing existing coding solutions, whenever $\ell > 0$. We then obtain sharp lower bounds on the necessary intra-cluster repair BW to achieve optimal trade-off. Under functional repair, random linear network codes (RLNCs) simultaneously optimize usage of both inter- and intra-cluster repair BW; simulation results based on RLNCs suggest optimality of the bounds on intra-cluster repair-bandwidth. Our bounds reveal the interesting fact that, while it is beneficial to increase the number of local helper nodes $\ell $ in order to improve the storage-vs-inter-cluster-repair-BW trade-off, increasing $\ell $ not only increases intra-cluster BW in the host-cluster, but also increases the intra-cluster BW in the remote helper clusters. We also analyze resilience of the clustered storage system against passive eavesdropping by providing file-size bounds and optimal code constructions. [ABSTRACT FROM AUTHOR]

We establish the rate region of an extended Gray–Wyner system (EGW) for 2-DMS $(X,Y)$ with two additional decoders having complementary causal side information. We show that the 5-D rate region of the EGW system is equivalent to the 3-D mutual information region consisting of the set of all triples of the form $(I(X;U),\,I(Y;U),\,I(X,Y;U))$ for some $p_{U|X,Y}$. This correspondence greatly simplifies the exploration of the the extreme points of the rate region. In addition to the operationally significant extreme points of the original Gray–Wyner rate region, which include Wyner’s common information, Gács-Körner common information, and the information bottleneck, the extreme points of the rate region for the EGW system also include the Körner graph entropy, the privacy funnel and excess functional information, as well as three new quantities of potential interest. We further show that projections of the mutual information region yield the rate regions for many settings involving a two discrete memoryless source (2-DMS), including lossless source coding with causal side information, distributed channel synthesis, and lossless source coding with a helper. To further motivate the mutual information region itself, we draw analogies between set operations and its extreme points. This allows us to find random variables that can be considered as intersection, difference, and symmetric difference of two random variables. Finally, we establish the rate regions for two related setups to the EGW system, namely, the noncausal EGW system and the lossy EGW system. [ABSTRACT FROM AUTHOR]

In this paper, we study the cycle distribution of random low-density parity-check (LDPC) codes, randomly constructed protograph-based LDPC codes, and random quasi-cyclic (QC) LDPC codes. We prove that for a random bipartite graph, with a given (irregular) degree distribution, the distributions of cycles of different length tend to independent Poisson distributions, as the size of the graph tends to infinity. We derive asymptotic upper and lower bounds on the expected values of the Poisson distributions that are independent of the size of the graph, and only depend on the degree distribution and the cycle length. For a random lift of a bi-regular protograph, we prove that the asymptotic cycle distributions are essentially the same as those of random bipartite graphs as long as the degree distributions are identical. For random QC-LDPC codes, however, we show that the cycle distribution can be quite different from the other two categories. In particular, depending on the protograph and the value of $c$ , the expected number of cycles of length $c$ , in this case, can be either $\Theta (N)$ or $\Theta (1)$ , where $N$ is the lifting degree (code length). We also provide numerical results that match our theoretical derivations. Our results provide a theoretical foundation for emperical results that were reported in the literature but were not well-justified. They can also be used for the analysis and design of LDPC codes and associated algorithms that are based on cycles. [ABSTRACT FROM AUTHOR]

The minimum description length two-part coding index of resolvability provides a finite-sample upper bound on the statistical risk of penalized likelihood estimators over countable models. However, the bound does not apply to unpenalized maximum likelihood estimation or procedures with exceedingly small penalties. In this paper, we point out a more general inequality that holds for arbitrary penalties. In addition, this approach makes it possible to derive exact risk bounds of order $1/n$ for iid parametric models, which improves on the order $(\log n)/n$ resolvability bounds. We conclude by discussing implications for adaptive estimation. [ABSTRACT FROM AUTHOR]

Distributed storage systems can store data with erasure coding to maintain data availability with low storage redundancy. One class of erasure coding is based on regenerating codes, which provably minimize the amount of data transferred for failure repair and realize the optimal tradeoff between the storage redundancy and the amount of traffic transferred for repair. Typical regenerating codes often require surviving storage nodes to encode their stored data for repair. In this paper, we study a framework called proxy-assisted regeneration, which offloads the repair process to a centralized proxy. We extend the previous applied work on proxy-assisted regeneration by providing theoretical validation. Specifically, we study a special class of regenerating codes called proxy-assisted minimum storage regenerating (PMSR) codes, which enable uncoded repair without the need of encoding in surviving nodes, while preserving the minimum storage redundancy and minimum amount of traffic transferred for repair. We formally prove the existence of PMSR codes for two configurations: 1) repairing single-node failures under double fault tolerance and 2) repairing double-node failures under triple fault tolerance. We also provide a semi-deterministic PMSR code construction for repairing single-node failures under double fault tolerance. [ABSTRACT FROM AUTHOR]

We consider a problem in which a source is encoded into $N$ packets, an unknown number of which are subject to adversarial errors en route to the decoder. We seek code designs for which the decoder is guaranteed to be able to reproduce the source subject to a certain distortion constraint when there are no packets errors, subject to a less stringent distortion constraint when there is one error, and so on. Focusing on the special case of the erasure distortion measure, we introduce a code design based on the polytope codes of Kosut et al.. The resulting designs are also applied to a separate problem in distributed storage. [ABSTRACT FROM PUBLISHER]

In this paper, we study the tradeoffs between the error probabilities of classical-quantum channels and the blocklength $n$ when the transmission rates approach the channel capacity at a rate lower than 1/\sqrt {n} , a research topic known as moderate deviation analysis. We show that the optimal error probability vanishes under this rate convergence. Our main technical contributions are a tight quantum sphere-packing bound, obtained via Chaganty and Sethuraman’s concentration inequality in strong large deviation theory, and asymptotic expansions of error-exponent functions. Moderate deviation analysis for quantum hypothesis testing is also established. The converse directly follows from our channel coding result, while the achievability relies on a martingale inequality. [ABSTRACT FROM AUTHOR]

Binary sequences with low odd correlation have important applications in communication systems to reduce interference. In this paper, using the interleaving technique, we present a generic connection between binary sequences with low odd correlation and quaternary sequences with low even correlation. As a result, some new binary sequences with optimal odd auto-correlation magnitude are obtained. Besides, two sets consisting of 2^n+1 binary sequences of period 2(2^n-1) with the maximum odd correlation magnitude 2^((n+1)/ 2)+2 are derived, which are the first two optimal classes of binary sequence sets achieving the Sarwate bound on the odd correlation magnitude in the literature. [ABSTRACT FROM PUBLISHER]

Large alphabet source coding is a basic and well-studied problem in data compression. It has many applications, such as compression of natural language text, speech, and images. The classic perception of most commonly used methods is that a source is best described over an alphabet, which is at least as large as the observed alphabet. In this paper, we challenge this approach and introduce a conceptual framework in which a large alphabet source is decomposed into “as statistically independent as possible” components. This decomposition allows us to apply entropy encoding to each component separately, while benefiting from their reduced alphabet size. We show that in many cases, such decomposition results in a sum of marginal entropies which is only slightly greater than the entropy of the source. Our suggested algorithm, based on a generalization of the binary independent component analysis, is applicable for a variety of large alphabet source coding setups. This includes the classical lossless compression, universal compression, and high-dimensional vector quantization. In each of these setups, our suggested approach outperforms most commonly used methods. Moreover, our proposed framework is significantly easier to implement in most of these cases. [ABSTRACT FROM PUBLISHER]

This paper studies the noncausal relay channel, also known as the relay channel with unlimited look ahead, introduced by by El Gamal, Hassanpour, and Mammen. Unlike the standard relay channel model, where the relay encodes its signal based on the previous received output symbols, the relay in the noncausal relay channel encodes its signal as a function of the entire received sequence. In the existing coding schemes, the relay uses this noncausal information solely to recover the transmitted message or part of it and then cooperates with the sender to communicate this message to the receiver. However, it is shown in this paper that by applying the Gelfand–Pinsker coding scheme, the relay can take further advantage of the noncausally available information and achieve rates strictly higher than those of the existing coding schemes. This paper also provides a new upper bound on the capacity of the noncausal relay channel that strictly improves upon the existing cutset bound. These new lower and upper bounds on the capacity coincide for the class of degraded noncausal relay channels and establish the capacity for this class. [ABSTRACT FROM AUTHOR]

Index coding is a source coding problem in which a broadcaster seeks to meet the different demands of several users, each of whom is assumed to have some prior information on the data held by the sender. A well-known application is satellite communications, as described in one of the earliest papers on the subject (Birk and Kol, 1998). It is readily seen that if the sender has knowledge of its clients’ requests and their side-information sets, then the number of packet transmissions required to satisfy all users’ demands can be greatly reduced if the data are encoded before sending. The collection of side-information indices as well as the indices of the requested data is described as an instance \mathcal I of the index coding with side-information (ICSI) problem. The encoding function is called the index code of $ \mathcal I$ , and the number of transmissions, resulting from the encoding is referred to as its length. The main ICSI problem is to determine the optimal length of an index code and instance $ \mathcal I$ . As this number is hard to compute, bounds approximating it are sought, as are algorithms to compute efficient index codes. These questions have been addressed by several authors (e.g., see Alon et al. 2008, Bar-Yossef et al. 2011, Blasiak et al. 2013), often taking a graph-theoretic approach. Two interesting generalizations of the problem that have appeared in the literature are the subject of this paper. The first of these is the case of index coding with coded side information (Dai et al. 2014), in which linear combinations of the source data are both requested by and held as users’ side-information. This generalization has applications, for example, to relay channels and necessitates algebraic rather than combinatorial methods. The second is the introduction of error-correction in the problem, in which the broadcast channel is subject to noise (Dau et al. 2013). In this paper, we characterize the optimal length of a scalar or vector linear index code with coded side information (ICCSI) over a finite field in terms of a generalized min-rank and give bounds on this number based on constructions of random codes for an arbitrary instance. We furthermore consider the length of an optimal $\delta $ -error correcting code for an instance of the ICCSI problem and obtain bounds analogous to those described in (Dau et al. 2013), both for the Hamming metric and for rank-metric errors. We describe decoding algorithms for both categories of errors. [ABSTRACT FROM AUTHOR]

For any bent function, it is very interesting to determine its dual function, because the dual function is also bent in certain cases. For k odd and \gcd (n, k)=1 , it is known that the Coulter–Matthews bent function f(x)=Tr\left(ax^\frac 3^k+12\right) is weakly regular bent over \mathbb F3^{n} , where a\in \mathbb F3^{n}^{*} , and Tr(\cdot ):\mathbb F3^{n}\rightarrow \mathbb F3 is the trace function. In this paper, we investigate the dual function of $f(x)$ , aiming to determine a universal formula. In particular, for two cases, we determine the formula explicitly: for the case of n=3t+1$ and k=2t+1$ with t\geq 2n=3t+2$ and k=2t+1$ with t\geq 2f(x)$ is regular bent. [ABSTRACT FROM PUBLISHER]

In this paper, we prove that Schubert union codes are Tanner codes constructed from the point–line incidence geometry inherited from the Grassmannian. Our proof is based on an iterative encoding algorithm for Tanner codes. This encoder determines the entries of a code word of a Tanner code from the entries in a given subset of its positions. As a result, we find sufficient conditions on the initial positions such that a code word is determined from the component codes only. This algorithm has linear complexity in the code length. We also use this encoder to determine the minimum distance of Schubert union codes in terms of the minimum distance of the Schubert varieties contained therein. [ABSTRACT FROM PUBLISHER]

The rate regions of multilevel diversity coding systems (MDCSs), a sub-class of the broader family of multi-source multi-sink networks with special structure, are investigated in a systematic way. We enumerate all non-isomorphic MDCS instances with at most three sources and four encoders. Then, the exact rate region of every one of these more than 7000 instances is proven via computations showing that the Shannon outer bound matches with a custom constructed linear code-based inner bound. Results gained from these computations are summarized in key statistics involving aspects, such as the sufficiency of scalar binary codes, the necessary size of vector binary codes, and so on. Also, it is shown how to construct the codes for an achievability proof. Based on this large repository of rate regions, a series of results about general MDCS cases of arbitrary size that they inspired is introduced and proved. In particular, a series of embedding operations that preserve the property of sufficiency of scalar or vector codes is presented. The utility of these operations is demonstrated by boiling the thousands of MDCS instances for which scalar binary (superposition) codes are insufficient down to 12 (26) forbidden the smallest embedded MDCS instances. [ABSTRACT FROM PUBLISHER]

Motivated by recent interest in physical-layer secret-key generation over wireless fading channels, we study the non-coherent secret-key generation capacity of a block-fading wireless channel with channel reciprocity and bi-directional (two-way) communication. We assume a non-coherent main channel, i.e., the realization of channel gains on the main channel is not known to any terminal. The eavesdropper is assumed to have both perfect Channel State Information of its own channel and orthogonal observations from the forward and backward channels. As our main result, we establish new upper and lower bounds on the secret-key generation capacity with public discussion, which are structurally similar. The upper bound can be expressed as a sum of three terms—one of the terms arises due to channel reciprocity, while the other two terms correspond to communication on the forward and backward channels, respectively. In the limit of long coherence period, the contribution from channel reciprocity vanishes to zero, whereas the other terms prevail. The lower bound is based on a separation based scheme. In each coherence block, we use the first symbol for training while the remainder of the coherence block is devoted to source emulation, i.e., to generate correlated sources between the terminals. The lower bound expression also consists of three terms and admits an interpretation similar to the upper bound expression. For Rayleigh fading channels, in the high signal-to-noise ratio (SNR) regime, the gap between the upper and lower bounds is shown to vanish inversely with the coherence period. Numerical results indicate significant performance gains over training-only schemes even for moderate values of SNR and small coherence periods. [ABSTRACT FROM PUBLISHER]

We introduce multidimensional analogues of quasi-cyclic (QC) codes and study their algebraic structure. We demonstrate a concatenated structure for multidimensional QC codes and use this to prove that this class of codes is asymptotically good. We also relate the new family of codes to convolutional codes. It is known that the minimum distance of QC codes provides a natural lower bound on the free distance of convolutional codes. We show that the same relation also holds between certain rank one 2-D convolutional codes and the related multidimensional QC codes. We provide examples, which show that our bound is sharp in some cases. We also present some optimal 2-D QC codes. Along the way, we provide a condition on the encoders of rank one convolutional codes, which are equivalent to noncatastrophicity for 1-D convolutional codes. In the n\textD case ( $n>1$ ), our condition is sufficient for the noncatastrophicity of the encoder. [ABSTRACT FROM PUBLISHER]

We approach index coding as a special case of rate–distortion with multiple receivers, each with some side information about the source. Specifically, using techniques developed for the rate–distortion problem, we provide two upper bounds and one lower bound on the optimal index coding rate. The upper bounds involve specific choices of the auxiliary random variables in the best existing scheme for the rate–distortion problem. The lower bound is based on a new lower bound for the general rate–distortion problem. The bounds are shown to coincide for a number of (groupcast) index coding instances, including all instances for which the number of decoders does not exceed three. [ABSTRACT FROM PUBLISHER]

Planar functions over finite fields give rise to finite projective planes. They were also used in the constructions of DES-like iterated ciphers, error-correcting codes, and codebooks. They were originally defined only in finite fields with odd characteristic, but recently Zhou introduced pesudo-planar functions in even characteristic, which yields similar applications. All known pesudo-planar functions are quadratic, and hence, they give presemifields. In this paper, a new approach to constructing quadratic pseudo-planar functions is given. Then, five explicit families of pseudo-planar functions are constructed, one of which is a binomial, two of which are trinomials, and the other two are quadrinomials. All known pesudo-planar functions are revisited, some of which are generalized. These functions not only lead to projective planes, relative difference sets, and presemifields, but also give optimal codebooks meeting the Levenstein bound, complete sets of mutually unbiased bases and compressed sensing matrices with low coherence. [ABSTRACT FROM PUBLISHER]

This paper establishes that the strong converse holds for some classes of discrete memoryless multimessage multicast networks (DM-MMNs) whose corresponding cut-set bounds are tight, i.e., coincide with the corresponding sets of achievable rate tuples. Our strong converse result implies that for any DM-MMN of these classes, the average error probabilities of any sequence of codes operated at a rate tuple belonging to the exterior of the cut-set bound must tend to one (and are not simply bounded away from zero) as the block length grows. Examples in the classes of DM-MMNs include wireless erasure networks, DM-MMNs consisting of independent discrete memoryless channels (DMCs) as well as single-destination DM-MMNs consisting of independent DMCs with destination feedback. Our elementary proof technique leverages properties of the Rényi divergence. [ABSTRACT FROM PUBLISHER]

We leverage proof techniques from discrete Fourier analysis and an existing result in coding theory to derive new bounds for the problem of non-interactive simulation of binary random variables. Previous bounds in the literature were derived by applying data processing inequalities concerning maximal correlation or hypercontractivity. We show that our bounds are sharp in some regimes. Indeed, for a specific instance of the problem parameters, our main result resolves an open problem posed by E. Mossel in 2017. As by-products of our analyses, various new properties of the average distance and distance enumerator of binary block codes are established. [ABSTRACT FROM AUTHOR]

Polar codes are constructed for arbitrary channels by imposing an arbitrary quasi-group structure on the input alphabet. Just as with usual polar codes, the block error probability under successive cancellation decoding is o(2^-N^1/2-\epsilon ) , where $N$ is the block length. Encoding and decoding for these codes can be implemented with a complexity of $O(N\log N)$ . It is shown that the same technique can be used to construct polar codes for arbitrary multiple access channels by using an appropriate Abelian group structure. Although the symmetric sum capacity is achieved by this coding scheme, some points in the symmetric capacity region may not be achieved. In the case where the channel is a combination of linear channels, we provide a necessary and sufficient condition characterizing the channels whose symmetric capacity region is preserved by the polarization process. We also provide a sufficient condition for having a maximal loss in the dominant face. [ABSTRACT FROM AUTHOR]

The binary symmetric stochastic block model deals with a random graph of $n$ vertices partitioned into two equal-sized clusters, such that each pair of vertices is independently connected with probability $p$ within clusters and $q$ across clusters. In the asymptotic regime of $p=a \log n/n$ and $q=b \log n/n$ for fixed $a,b$ , and $n \to \infty $ , we show that the semidefinite programming relaxation of the maximum likelihood estimator achieves the optimal threshold for exactly recovering the partition from the graph with probability tending to one, resolving a conjecture of Abbe et al. Furthermore, we show that the semidefinite programming relaxation also achieves the optimal recovery threshold in the planted dense subgraph model containing a single cluster of size proportional to $n$ . [ABSTRACT FROM AUTHOR]

The quantum relative entropy between two states satisfies a monotonicity property meaning that applying the same quantum channel to both states can never increase their relative entropy. It is known that this inequality is only tight when there is a recovery map that exactly reverses the effects of the quantum channel on both states. In this paper, we strengthen this inequality by showing that the difference of relative entropies is bounded below by the measured relative entropy between the first state and a recovered state from its processed version. The recovery map is a convex combination of rotated Petz recovery maps and perfectly reverses the quantum channel on the second state. As a special case, we reproduce recent lower bounds on the conditional mutual information, such as the one proved by Fawzi and Renner. Our proof only relies on the elementary properties of pinching maps and the operator logarithm. [ABSTRACT FROM AUTHOR]

Linear network coding transmits data through networks by letting the intermediate nodes combine the messages they receive and forward the combinations toward their destinations. The solvability problem asks whether the demands of all the destinations can be simultaneously satisfied by using linear network coding. The guessing number approach converts this problem into determining the number of fixed points of coding functions f:A^n\to A^n over a finite alphabet $A$ (usually referred to as Boolean networks if A = \{0,1\} ) with a given interaction graph that describes which local functions depend on which variables. In this paper, we generalize the so-called reduction of coding functions in order to eliminate variables. We then determine the maximum number of fixed points of a fully reduced coding function, whose interaction graph has a loop on every vertex. Since the reduction preserves the number of fixed points, we then apply these ideas and results to obtain four main results on the linear network coding solvability problem. First, we prove that non-decreasing coding functions cannot solve any more instances than routing already does. Second, we show that the triangle-free undirected graphs are linearly solvable if and only if they are solvable by routing. This is the first classification result for the linear network coding solvability problem. Third, we exhibit a new class of non-linearly solvable graphs. Fourth, we determine large classes of strictly linearly solvable graphs. [ABSTRACT FROM AUTHOR]

We consider the situation in which a transmitter attempts to communicate reliably over a discrete memoryless channel, while simultaneously ensuring covertness (low probability of detection) with respect to a warden, who observes the signals through another discrete memoryless channel. We develop a coding scheme based on the principle of channel resolvability, which generalizes and extends prior work in several directions. First, it shows that irrespective of the quality of the channels, it is possible to communicate on the order of \sqrt n reliable and covert bits over n channel uses if the transmitter and the receiver share on the order of \sqrt {n}\log n key bits. Second, it proves that if the receiver’s channel is better than the warden’s channel in a sense that we make precise, it is possible to communicate on the order of \sqrt n reliable and covert bits over n$ channel uses without a secret key. This generalizes earlier results established for binary symmetric channels. We also identify the fundamental limits of covert and secret communications in terms of the optimal asymptotic scaling of the message size and key size, and we extend the analysis to Gaussian channels. The main technical problem that we address is how to develop concentration inequalities for low-weight sequences. The crux of our approach is to define suitably modified typical sets that are amenable to concentration inequalities. [ABSTRACT FROM AUTHOR]

We show that the jumps correlation matrix of a multivariate Hawkes process is related to the Hawkes kernel matrix through a system of Wiener–Hopf integral equations. A Wiener–Hopf argument allows one to prove that this system (in which the kernel matrix is the unknown) possesses a unique causal solution and consequently that the first- and second-order properties fully characterize a Hawkes process. The numerical inversion of this system of integral equations allows us to propose a fast and efficient method, which main principles were initially sketched by Bacry and Muzy, to perform a non-parametric estimation of the Hawkes kernel matrix. In this paper, we perform a systematic study of this non-parametric estimation procedure in the general framework of marked Hawkes processes. We precisely describe this procedure step by step. We discuss the estimation error and explain how the values for the main parameters should be chosen. Various numerical examples are given in order to illustrate the broad possibilities of this estimation procedure ranging from monovariate (power-law or non-positive kernels) up to three-variate (circular dependence) processes. A comparison with other non-parametric estimation procedures is made. Applications to high-frequency trading events in financial markets and to earthquakes occurrence dynamics are finally considered. [ABSTRACT FROM AUTHOR]

Frequency-hopping sequences (FHSs) with favorable partial Hamming correlation properties are desirable in many synchronization and multiple-access systems. An FHS set is said to be strictly optimal if it has optimal partial Hamming correlation for any correlation window. In this paper, we derive upper bounds on the family sizes of FHS sets with respect to partial Hamming correlation from some classical bounds on error-correcting codes. We then present strictly optimal FHS sets having optimal family sizes with respect to one of the new bounds. In particular, our construction gives new parameters not covered in the literature. [ABSTRACT FROM AUTHOR]

A table of contents for the issue is presented.