Search

Minimal linear codes have significant applications in secret sharing schemes and secure two-party computation. When they are defined over finite fields, those codes have been intensively studied, especially in recent years, but they have been firstly partially characterized by Ashikhmin and Barg since 1998. Next, they were completely characterized in 2018 by Ding, Heng, and Zhou in terms of the minimum and maximum nonzero weights in the corresponding codes. Since then, many construction methods for minimal linear codes over finite fields throughout algebraic and geometric approaches have been proposed in the literature. In particular, the algebraic approach gives rise to minimal codes from (cryptographic) functions. Linear codes over finite fields have been expanded into the collection of acceptable alphabets for codes and study codes over finite commutative rings. A natural way to extend the known results available in the literature is to consider minimal linear codes over commutative rings with unity. In extending coding theory to codes over rings, several essential principles must be considered. Particularly extending the minimality property from finite fields to rings and creating such codes is not simple. Such an extension offers more flexibility in the construction of minimal codes. The present article investigates one-dimensional minimal linear codes over the rings $\mathbb {Z}_{p^{n}}$ (where $p$ is a prime) and $\mathbb {Z}_{p^{m}q^{n}}$ (where $p < q$ are distinct primes and $m\leq n$). Our ultimate objective is to characterize such codes’ minimality and design minimal linear codes over the considered rings. Given our objective, we first introduced the notion of minimal codes over (commutative) rings and succeeded in deriving simple characterization of one-dimensional minimal linear codes over the underlying rings mentioned above. Our new algebraic approach allows designing new minimal linear codes. Almost minimal codes over rings are also presented. To the best of our knowledge, the present paper offers a wide variety of minimal codes over (commutative) rings for the first time. Novel perspectives and developments in this direction are expected in the future. [ABSTRACT FROM AUTHOR]

Regenerating code is a class of distributed storage codes that can optimally trade the bandwidth required to repair a failed node with the amount of data stored per node. There are two optimal points in the regeneration tradeoff curve: the minimum storage regeneration code and the minimum bandwidth regeneration code. However, in hostile networks where the storage nodes may be compromised, the storage capacity of the network can be significantly affected. In this paper, we propose two optimal regenerating code constructions through rate-matching to combat this kind of adversarial attacks in hostile networks. We first develop a two-layer rate-matched regenerating code construction. By matching the parameters of the full rate code and the partial rate code, we can optimize the overall storage efficiency while maintaining the corrupted node detection probability. Through comprehensive analysis, we show that the two-layer rate-matched regenerating code can achieve 70% higher storage efficiency than the universally resilient regenerating code. We then propose an optimal $m$ -layer regenerating code construction. While the principle remains the same as the two-layer code, it is designed to optimize the total number of detectable corrupted nodes of $m$ layers from which the errors can be corrected under the constraint of any given code efficiency. Compared with the universally resilient regenerating code with the same rate, our $m$ -layer code can detect 50% more corrupted nodes. [ABSTRACT FROM PUBLISHER]

In this paper, we explore the three-node multi-terminal lossy source coding problem, which seems to offer a formidable mathematical complexity. We derive an inner bound to the general rate-distortion region of this problem, which is a natural extension of the seminal work by Kaspi on the interactive two-terminal source coding problem. It is shown that this (rather involved) inner bound contains several rate-distortion regions of some relevant source coding settings. In this way, besides the non-trivial extension of the interactive two terminal problem, our results can be seen as a generalization and hence unification of several previous works in the field. By specializing the inner bound to particular cases, we obtain some novel rate-distortion regions for several multi-terminal lossy source coding problems. [ABSTRACT FROM PUBLISHER]

Given n items with at most d of which being positive, instead of testing these items individually, the theory of combinatorial group testing aims to identify all positive items using as few tests as possible. This paper is devoted to a fundamental and thirty-year-old problem in the nonadaptive group testing theory. A binary matrix is called d -disjunct if the Boolean sum of arbitrary d columns does not contain another column not in this collection. Let T(d) denote the minimal t , such that there exists a t\times n\,\,d -disjunct matrix with n>t and was conjectured that T(d)\ge (d+1)^{2} . In this paper, we narrow the gap by proving T(d)/d^{2}\ge (15+\sqrt {33})/24$ , a quantity in [6/7,7/8]. [ABSTRACT FROM PUBLISHER]

One central theme in quantum error-correction is to construct quantum codes that have a relatively large minimum distance. In this paper, we first present a construction of classical linear codes based on certain classes of polynomials. Through these classical linear codes, we are able to obtain some new quantum codes. It turns out that some of the quantum codes exhibited here have better parameters than the ones available in the literature. [ABSTRACT FROM PUBLISHER]

In this paper, we investigate an instance of the Heegard–Berger problem with two sources and arbitrarily correlated side information sequences at two decoders, in which the reconstruction sets at the decoders are degraded. Specifically, two sources are to be encoded in a manner that one of the two is reproduced losslessly by both the decoders, and the other is reproduced within some prescribed distortion level at one of the two decoders. We establish a single-letter characterization of the rate-distortion function for this model. In particular, we show that the optimal coding scheme for this setting is one in which the common description to be recovered by both the decoders should allow to involve all or part of the source that is to be reproduced at only one decoder. Furthermore, we also generalize our result to the setting in which the source component that is to be recovered by both users is reconstructed in a lossy fashion, under the requirement that all terminals (i.e., the encoder and both the decoders) can share an exact copy of the compressed version of this source component, i.e., a common encoder–decoder reconstruction constraint. For this model as well, we establish a single-letter characterization of the associated rate-distortion function. [ABSTRACT FROM PUBLISHER]

Volume of metric balls relates to rate-distortion theory and packing bounds on codes. In this paper, the volume of balls in complex Grassmann manifolds is evaluated for an arbitrary radius. The ball is defined as a set of hyperplanes of a fixed dimension with reference to a center of possibly different dimensions, and a generalized chordal distance for unequal dimensional subspaces is used. First, the volume is reduced to a 1-D integral representation. The overall problem boils down to evaluating a determinant of a matrix of the same size as the subspace dimensionality. Interpreting this determinant as a characteristic function of the Jacobi ensemble, an asymptotic analysis is carried out. The obtained asymptotic volume is moreover refined using moment-matching techniques to provide a tighter approximation in finite-size regimes. Finally, the pertinence of the derived results is shown by rate-distortion analysis of source coding on Grassmann manifolds. [ABSTRACT FROM PUBLISHER]

Reed-Muller codes are error-correcting codes used in many areas related to coding theory, such as electrical engineering and computer science. The binary $r^{th}$ -order Reed-Muller code $RM(r,n)$ can be viewed as the set of all $n$ -variable Boolean functions of algebraic degree at most $r$. Despite the intense work on these codes, many problems are known to be hard (notably, determining their covering radius) and remain open to this day. Fourteen years ago, Carlet and Mesnager improved in [IEEE Transactions on Information Theory, “Improving the Upper Bounds on the Covering Radii of Binary Reed-Muller Codes”, 53(1), 2007] the upper bound on the covering radius of the Reed-Muller code of order 2, and they deduced improved upper bounds on the covering radii of the Reed-Muller codes of higher orders. Until 2021, these upper bounds remained the best ones in the literature. The Reed-Muller code $RM(n-3,n)$ , which corresponds to the dual of the Reed-Muller code $RM(2,n)$ , has attracted much attention. One of the main reasons is that it is precisely the code that has been considered to get the upper bounds derived by Carlet and Mesnager. Those upper bounds have been obtained thanks to the characterization of the codewords of the Reed-Muller code, whose Hamming weights are strictly less than 2.5 times the minimum distance $2^{n-r}$ due to Kasami, Tokura, and Azumi. Despite their impressive work in the seventieth, a more refined study and profound description of those codewords of ${RM}({n-3},{n})$ whose Hamming weight equals 16, and especially 18, seem necessary, as it could help us significantly in improving the covering radius of Reed-Muller codes. In this paper, we push further the known results on the Reed-Muller codes by focusing on the Reed-Muller code ${RM}({n-3},{n})$. We provide a classification of the codewords of weights 16 and 18 of the Reed-Muller code $RM(n-3,n)$. Our algebraic descriptions allow us to count the number of such codewords and to enumerate all of them explicitly. [ABSTRACT FROM AUTHOR]

The de Bruijn graph, its sequences, and their various generalizations, have found many applications in information theory, including many new ones in the last decade. In this paper, motivated by a coding problem for emerging memory technologies, a set of sequences which generalize the window property of de Bruijn sequences, on its shorter subsequences, are defined. These sequences can be also defined and viewed as constrained sequences. Hence, they will be called locally-constrained de Bruijn sequences and a set of such sequences will be called a locally-constrained de Bruijn code. Several properties and alternative definitions for such codes are examined and they are analyzed as generalized sequences in the de Bruijn graph (and its generalization) and as constrained sequences. Various enumeration techniques are used to compute the total number of sequences for any given set of parameters. A construction method of such codes from the theory of shift-register sequences is proposed. Finally, we show how these locally-constrained de Bruijn sequences and codes can be applied in constructions of codes for correcting synchronization errors in the $\ell $ -symbol read channel and in the racetrack memory channel. For this purpose, these codes are superior in their size to previously known codes. [ABSTRACT FROM AUTHOR]

Ovoids in ${\mathrm {PG}}(3, {\mathrm {GF}}(q))$ have been an interesting topic in coding theory, combinatorics, and finite geometry for a long time. So far only two families of ovoids are known. The first is the elliptic quadrics and the second is the Tits ovoids. It is known that an ovoid in ${\mathrm {PG}}(3, {\mathrm {GF}}(q))$ corresponds to a $[q^{2}+1, 4, q^{2}-q]$ code over ${\mathrm {GF}}(q)$ , which is called an ovoid code. The objectives of this paper are to develop the general theories of subfield codes and to study the subfield codes of the two families of ovoid codes. The dimensions, minimum weights, and the weight distributions of the subfield codes of the elliptic quadric codes and Tits ovoid codes are settled. The parameters of the duals of these subfield codes are also studied. Some of the codes presented in this paper are optimal, and some are distance-optimal. The parameters of the subfield codes are new. [ABSTRACT FROM AUTHOR]

Mutually uncorrelated (MU) codes are a class of codes in which no proper prefix of one codeword is a suffix of another codeword. These codes were originally studied for synchronization purposes and recently, Yazdi et al. showed their applicability to enable random access in DNA storage. In this paper,we follow the research of Yazdi et al. and study MU codes along with their extensions to correct errors and balanced codes. We first review a well-known construction of MU codes and study the asymptotic behavior of its cardinality. This task is accomplished by studying a special class of run-length limited codes that impose the longest run of zeros to be at most some function of the codewords length. We also present an efficient algorithm for this class of constrained codes and show how to use this analysis for MU codes. Next, we extend the results on the run-length limited codes in order to study $(d_{h},d_{m})$ -MU codes that impose a minimum Hamming distance of $d_{h}$ between different codewords and $d_{m}$ between prefixes and suffixes. In particular, we show an efficient construction of these codes with nearly optimal redundancy. We also provide similar results for the edit distance and balanced MU codes. Last, we draw connections to the problems of comma-free and prefix synchronized codes. [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]

In recent years, self-dual MDS codes have attracted a lot of attention due to theoretical interest and practical importance. Similar to self-dual MDS codes, self-dual near MDS (NMDS for short) codes have nice structures as well. From both theoretical and practical points of view, it is natural to study self-dual NMDS codes. Although there has been lots of work on NMDS codes in literature, little is known for self-dual NMDS codes. It seems more challenging to construct self-dual NMDS codes than self-dual MDS codes. The only work on construction of self-dual NMDS codes shows existence of $q$ -ary self-dual NMDS codes of length $q-1$ for odd prime power $q$ or length up to 16 for some small primes $q$ with $q\le 197$. In this paper, we make use of properties of elliptic curves to construct self-dual NMDS codes. It turns out that, as long as $2|q$ and $n$ is even with $4\le n\le q+\lfloor 2\sqrt {q}\rfloor -2$ , one can construct a self-dual NMDS code of length $n$ over $ {\mathbb {F}}_{q}$. Furthermore, for odd prime power $q$ , there exists a self-dual NMDS code of length $n$ over $ {\mathbb {F}}_{q}$ if $q\ge 4^{n+3}\times (n+3)^{2}$. [ABSTRACT FROM AUTHOR]

Cages, defined as regular graphs with minimum number of nodes for a given girth, are well-studied in graph theory. Trapping sets are graphical structures responsible for error floor of low-density parity-check (LDPC) codes, and are well investigated in coding theory. In this paper, we make connections between cages and trapping sets. In particular, starting from a cage (or a modified cage), we construct a trapping set in multiple steps. Based on the connection between cages and trapping sets, we then use the available results in graph theory on cages and derive tight upper bounds on the size of the smallest trapping sets for variable-regular LDPC codes with a given variable degree and girth. The derived upper bounds in many cases meet the best known lower bounds and thus provide the actual size of the smallest trapping sets. Considering that non-zero codewords are a special case of trapping sets, we also derive tight upper bounds on the minimum weight of such codewords, i.e., the minimum distance, of variable-regular LDPC codes as a function of variable degree and girth. [ABSTRACT FROM AUTHOR]

We consider data transmission over a network where each edge is an erasure channel and the inner nodes transmit the random linear combinations of their incoming information. We distinguish two channel models in this setting: the row and the column erasure channel model. For both models, we investigate spread codes and determine their symbol erasure correction capability and the probability of decoding success. We also compare the performance of spread codes to other known codes suitable for those models. Furthermore, we explain how to decode these codes in the two channel models and compare the decoding complexities. The results show that depending on the application and the to-be-optimized aspect, any combination of codes and channel models can be the best choice. [ABSTRACT FROM AUTHOR]

Existing polar coding schemes for the two-user interference channel follow the original idea of Han and Kobayashi, in which component messages are encoded independently and then mapped by some deterministic functions (i.e., homogeneous superposition coding). In this paper, we propose a new polar coding scheme for the interference channel based on the heterogeneous superposition coding approach of Chong, Motani, and Garg. We prove that fully joint decoding (the receivers simultaneously decode both senders’ common messages and the intended sender’s private message) in the Han–Kobayashi strategy can be simplified to two types of partial-joint decoding, which are friendly to polar coding with practical decoding algorithms. The proposed coding scheme requires less auxiliary random variables and no deterministic functions and can be efficiently constructed. Furthermore, we extend this result to interference networks and show that partial-joint decoding is a general method for designing heterogeneous superposition polar coding schemes in interference networks. [ABSTRACT FROM AUTHOR]

Private information retrieval (PIR) protocols allow a user to retrieve entries of a database without revealing the index of the desired item. Information-theoretical privacy can be achieved by the use of several servers and specific retrieval algorithms. Most known PIR protocols focus on decreasing the number of bits exchanged between the client and the server(s) during the retrieval process. On another side, Fazeli et al. introduced so-called PIR codes in order to reduce the storage overhead on the servers. However, few works address the issue of the computation complexity of the servers. In this paper, we show that a specific encoding of the database yields PIR protocols with reasonable communication complexity, low storage overhead, and optimal computational complexity for the servers. This encoding is based on incidence matrices of transversal designs, from which a natural and efficient recovering algorithm is derived. We also present several instances for our construction, which make use of finite geometries and orthogonal arrays. We finally give a generalization of our main construction in order to resist collusions of servers. [ABSTRACT FROM AUTHOR]

An error-erasure channel is a simple noise model that introduces both errors and erasures. While the two types of errors can be corrected simultaneously with error-correcting codes, it is also known that any linear code allows for first correcting errors and then erasures in two-step decoding. In particular, a carefully designed parity-check matrix not only allows for separating erasures from errors but also makes it possible to efficiently correct erasures. The separating redundancy of a linear code is the number of parity-check equations in a smallest parity-check matrix that has the required property for this error-erasure separation. In a sense, it is a parameter of a linear code that represents the minimum overhead for efficiently separating erasures from errors. While several bounds on separating redundancy are known, there still remains a wide gap between upper and lower bounds except for a few limited cases. In this paper, using probabilistic combinatorics and design theory, we improve both upper and lower bounds on separating redundancy. We also show a relation between parity-check matrices for error-erasure separation and special matrices, called X-codes, for data compaction circuits in VLSI testing. This leads to an exponentially improved bound on the size of an optimal X-code. [ABSTRACT FROM AUTHOR]

We investigate the maximum coding rate for a given average blocklength and error probability over a $K$ -user discrete memoryless broadcast channel for the scenario where a common message is transmitted using variable-length stop-feedback codes. For the point-to-point case, Polyanskiyet al.(2011) demonstrated that variable-length coding combined with stop-feedback significantly increases the speed of convergence of the maximum coding rate to capacity. This speed-up manifests itself in the absence of a square-root penalty in the asymptotic expansion of the maximum coding rate for large blocklengths, i.e.,zero dispersion. In this paper, we present nonasymptotic achievability and converse bounds on the maximum coding rate of the common-message $K$ -user discrete memoryless broadcast channel, which strengthen and generalize the ones reported in Trillingsgaardet al.(2015) for the two-user case. An asymptotic analysis of these bounds reveals that zero dispersion cannot be achieved for certain common-message broadcast channels (e.g., the binary symmetric broadcast channel). Furthermore, we identify conditions under which our converse and achievability bounds are tight up to the second order. Through numerical evaluations, we illustrate that our second-order expansions approximate accurately the maximum coding rate and that the speed of convergence to capacity is indeed slower than for the point-to-point case. [ABSTRACT FROM AUTHOR]

The polarization process of polar codes over a prime $q$ -ary alphabet is studied. Recently, it has been shown that the blocklength of polar codes with prime alphabet size scales polynomially with respect to the inverse of the gap between code rate and channel capacity. However, except for the binary case, the degree of the polynomial in the bound is extremely large. In this paper, a different approach to computing the degree of this polynomial for any prime alphabet size is shown. This approach yields a lower degree polynomial for various values of the alphabet size that were examined. It is also shown that even lower degree polynomial can be computed with an additional numerical effort. [ABSTRACT FROM AUTHOR]

The ordering of communication channels was first introduced by Shannon. In this paper, we aim to find characterizations of two orderings: input-degradedness and the Shannon ordering. A channel $W$ is said to be input-degraded from another channel $W'$ if $W$ can be simulated from $W'$ by randomization at the input. We provide a necessary and sufficient condition for a channel to be input-degraded from another one. We show that any decoder that is good for $W$ is also good for $W'$. We provide two characterizations for input-degradedness, one of which is similar to the Blackwell-Sherman-Stein theorem. We show that $W'$ contains $W$ (in the Shannon ordering sense) if and only if $W$ is the skew-composition of $W'$ with a convex-product $n$ channel. This fact is used to derive a characterization of the Shannon ordering that is similar to the Blackwell-Sherman-Stein theorem. [ABSTRACT FROM AUTHOR]

The main problem of constant-dimension subspace coding is to determine the maximal possible size ${\mathbf{A}}_{q}(n,d,k)$ of a set of $k$ -dimensional subspaces in ${\mathbf{F}}_{q}^{n}$ such that the subspace distance satisfies $d(U,V) \geq d$ for any two different subspaces $U$ and $V$ in this set. In this paper, we give a direct construction of constant-dimension subspace codes from two parallel versions of maximum rank-distance codes. The problem about the sizes of our constructed constant-dimension subspace codes is transformed into finding a suitable sufficient condition to restrict number of the roots of $L_{1}(L_{2}(x))-x$ where $L_{1}$ and $L_{2}$ are $q$ -polynomials over the extension field ${\mathbf{F}}_{q^{n}}$. New lower bounds for ${\mathbf{A}}_{q}(4k,2k,2k)$ , ${\mathbf{A}}_{q}(4k+2,2k,2k+1)$ , and ${\mathbf{A}}_{q}(4k+2,2(k-1),2k+1)$ are presented. Many new constant-dimension subspace codes better than previously best known codes with small parameters are constructed. [ABSTRACT FROM AUTHOR]

Discrete polymatroids are the multi-set analogue of matroids. In this paper, we explore the connections among linear network coding, linear index coding, and representable discrete polymatroids. We consider the vector linear solutions of networks over a field \mathbb Fq , with possibly different message and edge vector dimensions, which are referred to as linear fractional solutions. It is well known that a scalar linear solution over \mathbb Fq exists for a network if and only if the network is matroidal with respect to a matroid representable over \mathbb Fq . We define a discrete polymatroidal network and show that a linear fractional solution over a field \mathbb Fq exists for a network if and only if the network is discrete polymatroidal with respect to a discrete polymatroid representable over \mathbb Fq . An algorithm to construct the networks starting from certain class of discrete polymatroids is provided. Every representation over \mathbb Fq for the discrete polymatroid, results in a linear fractional solution over \mathbb Fq for the constructed network. Next, we consider the index coding problem, which involves a sender, which generates a set of messages X=\x1,x2,\dotso xk\ , and a set of receivers \mathcal R , which demand messages. A receiver R \in \mathcal R is specified by the tuple $(x,H)$ , where x \in X$ is the message demanded by R$ and is the side information possessed by $R$ . We first show that a linear solution to an index coding problem exists if and only if there exists a representable discrete polymatroid, satisfying certain conditions, which are determined by the index coding problem considered. Rouayheb et al. showed that the problem of finding a multi-linear representation for a matroid can be reduced to finding a perfect linear index coding solution for an index coding problem obtained from that matroid. The multi-linear representation of a matroid can be viewed as a special case of representation of an appropriate discrete polymatroid. We generalize the result of Rouayheb et al., by showing that the problem of finding a representation for a discrete polymatroid can be reduced to finding a perfect linear index coding solution for an index coding problem obtained from that discrete polymatroid. [ABSTRACT FROM PUBLISHER]

Consider an energy-harvesting receiver that uses the same received signal both for decoding information and for harvesting energy, which is employed to power its circuitry. In the scenario where the receiver has limited battery size, a signal with bursty energy content may cause power outage at the receiver, since the battery will drain during intervals with low signal energy. In this paper, we analyze subblock energy-constrained codes (SECCs), which ensure that sufficient energy is carried within every subblock duration. We consider discrete memoryless channels and characterize the SECC capacity and the SECC error exponent, and provide useful bounds for these values. We also study constant subblock-composition codes (CSCCs), which are a subclass of SECCs where all the subblocks in every codeword have the same fixed composition, and this subblock composition is chosen to maximize the rate of information transfer while meeting the energy requirement. Compared with constant composition codes (CCCs), we show that CSCCs incur a rate loss and that the error exponent for CSCCs is also related to the error exponent for CCCs by the same rate loss term. We exploit the symmetry in CSCCs to obtain a necessary and sufficient condition on the subblock length for avoiding power outage at the receiver. Furthermore, for CSCC sequences, we present a tight lower bound on the average energy per symbol within a sliding time window. We provide numerical examples highlighting the tradeoff between the delivery of sufficient energy to the receiver and achieving high information transfer rates. It is observed that the ability to use energy in real-time imposes less of penalty compared with the ability to use information in real-time. [ABSTRACT FROM PUBLISHER]

Linear programming (LP) decoding for low-density parity-check codes was introduced by Feldman et al. and has been shown to have theoretical guarantees in several regimes. Furthermore, it has been reported in the literature—via simulation and via instanton analysis—that LP decoding displays better error rate performance at high signal-to-noise ratios (SNR) than does belief propagation (BP) decoding. However, at low SNRs, LP decoding is observed to have worse performance than BP. In this paper, we seek to improve LP decoding at low SNRs while maintaining LP decoding’s high SNR performance. Our main contribution is a new class of decoders obtained by applying the alternating direction method of multipliers (ADMM) algorithm to a set of non-convex optimization problems. These non-convex problems are constructed by adding a penalty term to the objective of LP decoding. The goal of the penalty is to make pseudocodewords, which are non-integer vertices of the LP relaxation, more costly. We name this class of decoders—ADMM penalized decoders. For low and moderate SNRs, we simulate ADMM penalized decoding with \ell 1 and \ell 2 penalties. We find that these decoders can outperform both BP and LP decoding. For high SNRs, where it is difficult to obtain data via simulation, we use an instanton analysis and find that, asymptotically, ADMM penalized decoding performs better than BP but not as well as LP. Unfortunately, since ADMM penalized decoding is not a convex program, we have not been successful in developing theoretical guarantees. However, the non-convex program can be approximated using a sequence of linear programs; an approach that yields a reweighted LP decoder. We show that a two-round reweighted LP decoder has an improved theoretical recovery threshold when compared with LP decoding. In addition, we find via simulation that reweighted LP decoding significantly attains lower error rates than LP decoding at low SNRs. [ABSTRACT FROM AUTHOR]

A locally recoverable code (LRC code) is a code over a finite alphabet, such that every symbol in the encoding is a function of a small number of other symbols that form a recovering set. In this paper, we derive new finite-length and asymptotic bounds on the parameters of LRC codes. For LRC codes with a single recovering set for every coordinate, we derive an asymptotic Gilbert–Varshamov type bound for LRC codes and find the maximum attainable relative distance of asymptotically good LRC codes. Similar results are established for LRC codes with two disjoint recovering sets for every coordinate. For the case of multiple recovering sets (the availability problem), we derive a lower bound on the parameters using expander graph arguments. Finally, we also derive finite-length upper bounds on the rate and the distance of LRC codes with multiple recovering sets. [ABSTRACT FROM AUTHOR]

This paper investigates various subtleties of applying linear physical-layer network coding (PNC) with $q$ -level pulse amplitude modulation ( $q$ -PAM) in two-way relay channels. A critical issue is how the PNC system performs when the received powers from the two users at the relay are imbalanced. In particular, how would the PNC system perform under slight power imbalance that is inevitable in practice, even when power control is applied? To answer these questions, this paper presents a comprehensive analysis of $q$ -PAM PNC. Our contributions are as follows. First, we give a systematic way to obtain the analytical relationship between the minimum distance of the signal constellation induced by the superimposed signals of the two users (a key performance determining factor) and the channel-gain ratio of the two users, for all $q$ . In particular, we show how the minimum distance changes in a piecewise linear fashion as the channel-gain ratio varies. Second, we show that the performance of $q$ -PAM PNC is highly sensitive to imbalanced received powers from the two users at the relay, even when the power imbalance is slight (e.g., the residual power imbalance in a power-controlled system). This sensitivity problem is exacerbated as $q$ increases, calling into question the robustness of high-order modulated PNC. Third, we propose an asynchronized PNC system in which the symbol arrival times of the two users at the relay are deliberately made to be asynchronous. We show that such asynchronized PNC, when operated with a belief propagation decoder, can remove the sensitivity problem, allowing a robust high-order modulated PNC system to be built. [ABSTRACT FROM AUTHOR]

This paper presents an outage analysis for a two-user parallel Gaussian interference channel consisting of two sub-channels. Each sub-channel is modeled as a two-user Gaussian interference channel with quasi-static and flat fading. Both users employ single-layer Gaussian code-books and maintain a statistical correlation \rho between the signals transmitted over the underlying sub-channels. When joint decoding (JD) is performed at the receivers, setting \rho =0 minimizes the outage probability, regardless of the value of the signal-to-noise ratio (SNR). It is shown, however, that if the receivers treat interference as noise (TIN) or cancel interference (CI), the value of optimum \rho approaches 1 as SNR goes to infinity. Motivated by these observations, we let \rho =0 under JD and \rho =1 , it is shown that the outage probability scales like \mathrm snr^-(1-r) under both TIN and CI, while it vanishes at least as fast as \mathrm snr^-\min \2-r,4(1-r)\\log \mathrm snr under JD. This paper is concluded by extending some of the results to a two-user parallel Gaussian interference channel with an arbitrary number of sub-channels. [ABSTRACT FROM AUTHOR]

This paper presents exact capacity characterizations for the case, when a principal, Alice, wants to securely send a message to another principal, Bob, over three network configurations: the parallel edges network, the V-network, and the triangle network. We assume that: 1) a passive eavesdropper, Eve, overhears any one edge in the network; 2) each edge corresponds to an independent broadcast packet erasure channel with arbitrary erasure probabilities; and 3) all legitimate nodes can publicly but causally acknowledge whether they received each packet or not. We develop optimal achievability schemes that are expressed as linear programs (LPs) and share a two-phase structure, where at the first phase, we create secret keys, and at the second phase, we use them to encrypt the transmitted message. Our outer bounds are also expressed through LP formulations. We prove that our schemes are optimal by showing that the optimal solution of the outer bound LP and the optimal solution of the achievability scheme LP coincide. [ABSTRACT FROM AUTHOR]

In this paper, we provide a solution to the open problem of computing the Fourier transform of a binary function defined over n -bit vectors taking m -bit vector values. In particular, we introduce the two-modular Fourier transform (TMFT) of a binary function f:G\rightarrow \mathcal R , where G = (\mathbb F2^{n},+) is the group of n bit vectors with bitwise modulo two addition +, and {\mathcal{ R}} is a finite commutative ring of characteristic 2. Using the specific group structure of G and a sequence of nested subgroups of G , we define the fast TMFT and its inverse. Since the image {\mathcal{ R}} of the binary functions is a ring, we can define the convolution between two functions f:G\rightarrow {\mathcal{ R}}$ . We then provide the TMFT properties, including the convolution theorem, which can be used to efficiently compute convolutions. Finally, we derive the complexity of the fast TMFT and the inverse fast TMFT. [ABSTRACT FROM AUTHOR]

This paper studies an untrusted relay channel, in which the destination sends artificial noise simultaneously with the source sending a message to the relay, in order to protect the source’s confidential message. The traditional amplify-and-forward (AF) scheme shows poor performance in this situation because of the interference power dilemma. Providing better security by using stronger artificial noise will consume more power of the relay, impairing the confidential message’s transmission. To solve this problem, this paper proposes a modulo-and-forward (MF) operation at the relay with nested lattice encoding at the source. For the proposed MF scheme with full channel state information at the transmitter (CSIT), theoretical analysis shows that the MF scheme approaches the secrecy capacity within 1/2 bit for all channel realizations, and, hence, achieves full generalized security degrees of freedom (G-SDoF). In contrast, the AF scheme can only achieve a small fraction of the G-SDoF. For the MF scheme without CSIT, the total outage event, defined as either connection outage or secrecy outage, is introduced. Based on this total outage definition, analysis shows that the proposed MF scheme achieves the full generalized secure diversity gain (G-SDG) of order one. On the other hand, the AF scheme can achieve a G-SDG of only 1/2 at most. [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]

We consider a communication system in which status updates arrive at a source node, and should be transmitted through a network to the intended destination node. The status updates are samples of a random process under observation, transmitted as packets, which also contain the time stamp to identify when the sample was generated. The age of the information available to the destination node is the time elapsed, since the last received update was generated. In this paper, we model the source-destination link using the queuing theory, and we assume that the time it takes to successfully transmit a packet to the destination is an exponentially distributed service time. We analyze the age of information in the case that the source node has the capability to manage the arriving samples, possibly discarding packets in order to avoid wasting network resources with the transmission of stale information. In addition to characterizing the average age, we propose a new metric, called peak age, which provides information about the maximum value of the age, achieved immediately before receiving an update. [ABSTRACT FROM AUTHOR]

Gabidulin codes can be seen as the rank-metric equivalent of Reed–Solomon codes. It was recently proved, using subspace polynomials, that Gabidulin codes cannot be list decoded beyond the so-called Johnson radius. In another result, cyclic subspace codes were constructed by inspecting the connection between subspaces and their subspace polynomials. In this paper, these subspace codes are used to prove two bounds on the list size in decoding certain Gabidulin codes. The first bound is an existential one, showing that exponentially sized lists exist for codes with specific parameters. The second bound presents exponentially sized lists explicitly for a different set of parameters. Both bounds rule out the possibility of efficiently list decoding several families of Gabidulin codes for any radius beyond half the minimum distance. Such a result was known so far only for non-linear rank-metric codes, and not for Gabidulin codes. Using a standard operation called lifting, identical results also follow for an important class of constant dimension subspace codes. [ABSTRACT FROM AUTHOR]

This paper considers the problem of linear Boolean classification, where the goal is to determine in which set, among two given sets of Boolean vectors, an unknown vector belongs to by making linear queries. Finding the least number of queries is equivalent to determining the minimal rank of a matrix over $GF(2)$ , whose kernel does not intersect a given set $S$ . In the case where $S$ is a Hamming ball, this reduces to finding linear codes of largest dimension. For a general set $S$ , this is an instance of the critical problem posed by Crapo and Rota in 1970, open in general. This paper focuses on the case where $S$ is an annulus. As opposed to balls, it is shown that an optimal kernel is composed not only of dense but also of sparse vectors, and the optimal mixture is identified in various cases. These findings corroborate a proposed conjecture that for an annulus of inner and outer radius $nq$ and $np$ respectively, the optimal relative rank is given by the normalized entropy $(1-q)H(p/(1-q))$ , an extension of the Gilbert–Varshamov bound. [ABSTRACT FROM AUTHOR]

This paper considers the signal-to-noise ratio (SNR)-evolution, meaning the behavior as a function of the SNR, of the minimum mean-square error (MMSE) function of code sequences in several multi-user settings in the additive white Gaussian noise regime. The settings investigated in this context include the Gaussian wiretap channel, the Gaussian broadcast channel (BC), and the Gaussian BC with confidential messages (BCC). This paper shows that the specific properties of the SNR-evolution of the MMSE and conditional MMSE functions are necessary and sufficient conditions for capacity or equivocation achieving code sequences. In some cases, the complete SNR-evolution of a family of code sequences can be determined, providing significant insight into the disturbance (in terms of MMSE) such codes have on unintended receivers at other SNRs. Moreover, the effects of an additional MMSE constraint on the capacity region and on the SNR-evolution of code sequences are considered in the BC and BCC settings. Such an analysis emphasizes the tradeoff between rates and limited disturbance on unintended receivers. [ABSTRACT FROM AUTHOR]

An involution is a permutation, such that its inverse is itself (i.e., cycle length ≤ 2). Due to this property, involutions have been used in many applications, including cryptography and coding theory. In this paper, we provide a systematic study of involutions that are defined over a finite field of characteristic 2. We characterize the involution property of several classes of polynomials and propose several constructions. Furthermore, we study the number of fixed points of involutions, which is a pertinent question related to permutations with short cycle. In this paper, we mostly have used combinatorial techniques. [ABSTRACT FROM AUTHOR]

Polar coding is a method for communication over noisy classical channels, which is provably capacity achieving and has an efficient encoding and decoding. Recently, this method has been generalized to the realm of quantum information processing, for tasks such as classical communication, private classical communication, and quantum communication. In this paper, we apply the polar coding method to network classical-quantum information theory, by making use of recent advances for related classical tasks. In particular, we consider problems such as the compound multiple access channel and the quantum interference channel. The main result of our work is that it is possible to achieve the best known inner bounds on the achievable rate regions for these tasks, without requiring a so-called quantum simultaneous decoder. Thus, this paper paves the way for developing network classical-quantum information theory further without requiring a quantum simultaneous decoder. [ABSTRACT FROM AUTHOR]

Burst errors are a type of distortion in many data communications and data storage channels. In this paper, we consider the list decodability of codes for single burst error case and phased-burst error case independently. Firstly, we analyze the list decodability of random codes, and we show that the burst list decoding radius and the rate of random codes achieve the Singleton bound and the Gilbert-Varshamov bound for single case and phased case, respectively. Second, we illustrate that cyclic codes and algebraic geometry codes are good burst list-decodable codes for single case and phased case, respectively. [ABSTRACT FROM AUTHOR]

This paper is devoted to studying two main problems: 1) computing the apparent distance of an Abelian code and 2) giving a notion of Bose, Ray-Chaudhuri, Hocquenghem (BCH) multivariate code. To do this, we first strengthen the notion of an apparent distance by introducing the notion of a strong apparent distance; then, we present an algorithm to compute the strong apparent distance of an Abelian code, based on some manipulations of hypermatrices associated with its generating idempotent. Our method uses less computations than those given by Camion and Sabin; furthermore, in the bivariate case, the order of computation complexity is reduced from exponential to linear. Then, we use our techniques to develop a notion of a BCH code in the multivariate case, and we extend most of the classical results on cyclic BCH codes. Finally, we apply our method to the design of Abelian codes with maximum dimension with respect to a fixed apparent distance and a fixed length. [ABSTRACT FROM AUTHOR]

An upper bound on the error probability of specific lattices, based on their distance spectrum, is constructed. The derivation is accomplished using a simple alternative to the Minkowski–Hlawka mean-value theorem of the geometry of numbers. In many ways, the new bound greatly resembles the Shulman–Feder bound for linear codes. Based on the new bound, error-exponent and channel-dispersion expressions are derived for specific lattice sequences (of increasing dimension) over the AWGN channel. Measuring a sequence’s gap to capacity, using the new asymptotics, is demonstrated. Additional finite dimension results, encountered along the way, are presented. [ABSTRACT FROM PUBLISHER]

In 1973, Gallager proved that the random-coding bound is exponentially tight for the random code ensemble at all rates, even below expurgation. This result explained that the random-coding exponent does not achieve the expurgation exponent due to the properties of the random ensemble, irrespective of the utilized bounding technique. It has been conjectured that this same behavior holds true for a random ensemble of linear codes. This conjecture is proved in this paper. In addition, it is shown that this property extends to Poltyrev’s random-coding exponent for a random ensemble of lattices. [ABSTRACT FROM PUBLISHER]

A tight converse bound to the channel coding rate in the finite block-length regime and under additive white Gaussian noise conditions was recently proposed by Polyanskiy-Poor–Verdú (PPV). The bound is a generalization of a number of other classical results, and it was also claimed to be equivalent to Shannon’s 1959 cone packing bound. In this paper, we investigate methods for a reliable numerical evaluation of the bound, which is troublesome even for not too large values of the block-length $n$ , by compactly expressing the Polyanskiy, Poor, and Verdú (PPV) converse bound in terms of non-central chi-squared distributions, and by evaluating those through an integral expression and a corresponding series expansion which exploit a method proposed by Temme. As a result, a robust evaluation method and new insights on the bound’s asymptotics, as well as new approximate expressions, are obtained. [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]

In this paper we study stopping sets of AG codes over a family of curves, denoted by Xƒ,g, that includes several important curves with applications in coding theory. We present results concerning stopping sets of one-point and m-point codes over Xƒ,g , generalizing some results for Hermitian codes presented by Anderson and Matthews. [ABSTRACT FROM AUTHOR]

This paper considers the problem of optimal zero-delay jamming over an additive noise channel. Building on a sequence of recent results on conditions for linearity of optimal estimation, and of optimal mappings in source-channel coding, the saddle-point solution to the jamming problem is derived for general sources and channels, without recourse to Gaussianity assumptions. The linearity conditions are shown to play a pivotal role in jamming, in the sense that the optimal jamming strategy is to effectively force both the transmitter and the receiver to default to linear mappings, i.e., the jammer ensures, whenever possible, that the transmitter and the receiver cannot benefit from non-linear strategies. This result is shown to subsume the known result for Gaussian source and channel. The conditions and general settings where such unbeatable strategy can indeed be achieved by the jammer are analyzed. Moreover, a numerical procedure is provided to approximate the optimal jamming strategy in the remaining (source-channel) cases where the jammer cannot impose linearity on the transmitter and the receiver. Next, the analysis is extended to vector sources and channels. This extension involves a new aspect of optimization: the allocation of available transmit and jamming power over source and channel components. Similar to the scalar setting, the saddle-point solution is derived using the linearity conditions in vector spaces. The optimal power allocation strategies for the jammer and the transmitter have an intuitive interpretation as the jammer allocates power according to water-filling over the channel eigenvalues, while the transmitter performs water-pouring (reverse water-filling) over the source eigenvalues. [ABSTRACT FROM PUBLISHER]

The current flash memory technology focuses on the cost minimization of its static storage capacity. However, the resulting approach supports a relatively small number of program-erase cycles. This technology is effective for consumer devices (e.g., smartphones and cameras) where the number of program-erase cycles is small. However, it is not economical for enterprise storage systems that require a large number of lifetime writes. The proposed approach in this paper for alleviating this problem consists of the efficient integration of two key ideas: 1) improving reliability and endurance by representing the information using relative values via the rank modulation scheme and 2) increasing the overall (lifetime) capacity of the flash device via rewriting codes, namely, performing multiple writes per cell before erasure. This paper presents a new coding scheme that combines rank-modulation with rewriting. The key benefits of the new scheme include: 1) the ability to store close to 2 bit per cell on each write with minimal impact on the lifetime of the memory and 2) efficient encoding and decoding algorithms that make use of capacity-achieving write-once-memory codes that were proposed recently. [ABSTRACT FROM PUBLISHER]

In the case of ordinary identification coding, a code is devised to identify a single object among $N$ objects. But, in this paper, we consider a coding problem to identify K$ objects at once among N$ objects in the both cases that K$ objects are ranked or not ranked. By combining Moulin–Koetter scheme with the \varepsilon $ -almost strongly universal class of hash functions used in Kurosawa–Yoshida scheme, an efficient and explicit coding scheme is proposed for K$ -multiple-object identification ( KK$-MOID}} , which is the maximum achievable coding rate in the K -MOID coding, is equal to the ordinary channel capacity, and the proposed scheme can attain C_{\text {K$-MOID}}$ . [ABSTRACT FROM PUBLISHER]

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]

An explicit characterization of the capacity region of the general network coding problem is one of the best known open problems in information theory. A simple set of bounds that is often used in the literature to show that certain rate tuples are infeasible are based on the graph-theoretic notion of cut. The standard cut-set bounds, however, are known to be loose in general when there are multiple messages to be communicated in the network. This paper focuses on broadcast networks, for which the standard cut-set bounds are closely related to union as a specific set operation to combine different simple cuts of the network. A new set of explicit network coding bounds, which combine different simple cuts of the network via a variety of set operations (not just the union), are established via their connections to extremal inequalities for submodular functions. The tightness of these bounds are demonstrated via applications to combination networks. [ABSTRACT FROM AUTHOR]