Search

We consider the problem of communicating over a channel that randomly “tears” the message block into small pieces of different sizes and shuffles them. For the binary torn-paper channel with block length $n$ and pieces of length ${\mathrm{ Geometric}}(p_{n})$ , we characterize the capacity as $C = e^{-\alpha }$ , where $\alpha = \lim _{n\to \infty } p_{n} \log n$. Our results show that the case of ${\mathrm{ Geometric}}(p_{n})$ -length fragments and the case of deterministic length- $(1/p_{n})$ fragments are qualitatively different and, surprisingly, the capacity of the former is larger. Intuitively, this is due to the fact that, in the random fragments case, large fragments are sometimes observed, which boosts the capacity. [ABSTRACT FROM AUTHOR]

We introduce a fundamental lemma called the Poisson matching lemma, and apply it to prove one-shot achievability results for various settings, namely channels with state information at the encoder, lossy source coding with side information at the decoder, joint source-channel coding, broadcast channels, distributed lossy source coding, multiple access channels and channel resolvability. Our one-shot bounds improve upon the best known one-shot bounds in most of the aforementioned settings (except multiple access channels and channel resolvability, where we recover bounds comparable to the best known bounds), with shorter proofs in some settings even when compared to the conventional asymptotic approach using typicality. The Poisson matching lemma replaces both the packing and covering lemmas, greatly simplifying the error analysis. This paper extends the work of Li and El Gamal on Poisson functional representation, which mainly considered variable-length source coding settings, whereas this paper studies fixed-length settings, and is not limited to source coding, showing that the Poisson functional representation is a viable alternative to typicality for most problems in network information theory. [ABSTRACT FROM AUTHOR]

A functional $k$ -batch code of dimension $s$ consists of $n$ servers storing linear combinations of $s$ linearly independent information bits. Any multiset request of size $k$ of linear combinations (or requests) of the information bits can be recovered by $k$ disjoint subsets of the servers. The goal under this paradigm is to find the minimum number of servers for given values of $s$ and $k$. A recent conjecture states that for any $k=2^{s-1}$ requests the optimal solution requires $2^{s}-1$ servers. This conjecture is verified for $s \leqslant 5$ but previous work could only show that codes with $n=2^{s}-1$ servers can support a solution for $k=2^{s-2} + 2^{s-4} + \left \lfloor{ \frac { 2^{s/2}}{\sqrt {24}} }\right \rfloor $ requests. This paper reduces this gap and shows the existence of codes for $k=\lfloor \frac {5}{6}2^{s-1} \rfloor - s$ requests with the same number of servers. Another construction in the paper provides a code with $n=2^{s+1}-2$ servers and $k=2^{s}$ requests, which is an optimal result. These constructions are mainly based on extended Simplex codes and equivalently provide constructions for parallel Random I/O (RIO) codes. [ABSTRACT FROM AUTHOR]

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

Quantum readout provides a general framework for formulating statistical discrimination of quantum channels. Several paths have been taken for such this problem. However, there is much to be done in the avenue of optimizing channel discrimination using classical codes. At least two open questions can be pointed out: how to construct low complexity encoding schemes that are interesting for channel discrimination and, more importantly, how to develop capacity-achieving protocols. This paper aims at presenting a solution to these questions using polar codes. Firstly, we characterize the information rate and reliability parameter of the channels under polar encoding. We also show that the error probability of the scheme proposed decays exponentially with the square root of the code length. Secondly, an analysis of the optimal quantum states to be used as probes is given. [ABSTRACT FROM AUTHOR]

In general coding theory, we often assume that error is observed in transferring or storing encoded symbols, while the process of encoding itself is error-free. Motivated by recent applications of coding theory, in this paper, we consider the case where the process of encoding is distributed and prone to error. We introduce the problem of distributed encoding, comprised of a set of $K \in \mathbb {N}$ isolated source nodes and $N \in \mathbb {N}$ encoding nodes. Each source node has one symbol from a finite field, which is sent to each of the encoding nodes. Each encoding node stores an encoded symbol from the same field, as a function of the received symbols. However, some of the source nodes are controlled by the adversary and may send different symbols to different encoding nodes. Depending on the number of the adversarial nodes, denoted by $\beta \in \mathbb {N}$ , and the cardinality of the set of symbols that each one generates, denoted by $v \in \mathbb {N}$ , the process of decoding from the encoded symbols could be impossible. Assume that a decoder connects to an arbitrary subset of $t \in \mathbb {N}$ encoding nodes and wants to decode the symbols of the honest nodes correctly, without necessarily identifying the sets of honest and adversarial nodes. An important characteristic of a distributed encoding system is $t^{*} \in \mathbb {N}$ , the minimum of such $t$ , which is a function of $K$ , $N$ , $\beta $ , and $v$. In this paper, we study the distributed linear encoding system, i.e. one in which the encoding nodes use linear coding. We show that $t^{*}_{\textrm {Linear}}=K+2\beta (v-1)$ , if $N\ge K+2\beta (v-1)$ , and $t^{*}_{\textrm {Linear}}=N$ , if $N\le K+2\beta (v-1)$. In order to achieve $t^{*}_{\textrm {Linear}}$ , we use random linear coding and show that in any feasible solution that the decoder finds, the messages of the honest nodes are decoded correctly. In order to prove the converse of the fundamental limit, we show that when the adversary behaves in a particular way, it can always confuse the decoder between two feasible solutions that differ in the message of at least one honest node. [ABSTRACT FROM AUTHOR]

The Bose-Chaudhuri-Hocquenghem (BCH) codes are a well-studied subclass of cyclic codes that have found numerous applications in error correction and notably in quantum information processing. They are widely used in data storage and communication systems. A subclass of attractive BCH codes is the narrow-sense BCH codes over the Galois field ${\mathrm {GF}}(q)$ with length $q+1$ , which are closely related to the action of the projective general linear group of degree two on the projective line. Despite its interest, not much is known about this class of BCH codes. This paper aims to study some of the codes within this class and specifically narrow-sense antiprimitive BCH codes (these codes are also linear complementary duals (LCD) codes that have interesting practical recent applications in cryptography, among other benefits). We shall use tools and combine arguments from algebraic coding theory, combinatorial designs, and group theory (group actions, representation theory of finite groups, etc.) to investigate narrow-sense antiprimitive BCH Codes and extend results from the recent literature. Notably, the dimension, the minimum distance of some $q$ -ary BCH codes with length $q+1$ , and their duals are determined in this paper. The dual codes of the narrow-sense antiprimitive BCH codes derived in this paper include almost MDS codes. Furthermore, the classification of ${\mathrm {PGL}}(2, p^{m})$ -invariant codes over ${\mathrm {GF}}(p^{h})$ is completed. As an application of this result, the $p$ -ranks of all incidence structures invariant under the projective general linear group ${\mathrm {PGL}}(2, p^{m})$ are determined. Furthermore, infinite families of narrow-sense BCH codes admitting a 3-transitive automorphism group are obtained. Via these BCH codes, a coding-theory approach to constructing the Witt spherical geometry designs is presented. The BCH codes proposed in this paper are good candidates for permutation decoding, as they have a relatively large group of automorphisms. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of guessing a sequence subject to a distortion constraint. Specifically, we assume the following game between Alice and Bob: Alice has a sequence ${x}$ of length $n$. Bob wishes to guess ${x}$ , yet he is satisfied with finding any sequence $\hat {x}$ which is within a given distortion $D$ from $x$. Thus, he successively submits queries to Alice, until receiving an affirmative answer, stating that his guess was within the required distortion. Finding guessing strategies which minimize the number of guesses (the guesswork), and analyzing its properties (e.g., its $\rho $ –th moment) has several applications in information security, source and channel coding. Guessing subject to a distortion constraint is especially useful when considering contemporary biometrically–secured systems, where the “password” which protects the data is not a single, fixed vector but rather a ball of feature vectors centered at some ${x}$ , and any feature vector within the ball results in acceptance. We formally define the guessing problem under distortion in four different setups: memoryless sources, guessing through a noisy channel, sources with memory and individual sequences. We suggest a randomized guessing strategy which is asymptotically optimal for all setups and is five–fold universal, as it is independent of the source statistics, the channel, the moment to be optimized, the distortion measure and the distortion level. [ABSTRACT FROM AUTHOR]

We study the list decodability of different ensembles of codes over the real alphabet under the assumption of an omniscient adversary. It is a well-known result that when the source and the adversary have power constraints $P $ and $N $ respectively, the list decoding capacity is equal to $\frac {1}{2}\log \frac {P}{N}$. Random spherical codes achieve constant list sizes, and the goal of the present paper is to obtain a better understanding of the smallest achievable list size as a function of the gap to capacity. We show a reduction from arbitrary codes to spherical codes, and derive a lower bound on the list size of typical random spherical codes. We also give an upper bound on the list size achievable using nested Construction-A lattices and infinite Construction-A lattices. We then define and study a class of infinite constellations that generalize Construction-A lattices and prove upper and lower bounds for the same. Other goodness properties such as packing goodness and AWGN goodness of infinite constellations are proved along the way. Finally, we consider random lattices sampled from the Haar distribution and show that if a certain conjecture that originates in analytic number theory is true, then the list size grows as a polynomial function of the gap-to-capacity. [ABSTRACT FROM AUTHOR]

For fixed integers $n$ and $b\geq k$ , let $A(b,k,n)$ the largest size of a subset of $\{1,2,\ldots,b\}^{n}$ such that, for any $k$ distinct elements in the set, there is a coordinate where they all differ. Bounding $A(b,k,n)$ is a problem of relevant interest in information theory and computer science, relating to the zero-error capacity with list decoding and to the study of $(b, k)$ -hash families of functions. It is known that, for fixed $b$ and $k$ , $A(b,k,n)$ grows exponentially in $n$. In this paper, we determine new exponential upper bounds for different values of $b$ and $k$. A first bound on $A(b,k,n)$ for general $b$ and $k$ was derived by Fredman and Komlós in the ’80s and improved for certain $b\neq k$ by Körner and Marton and by Arikan. Only very recently better bounds were derived for general $b$ and $k$ by Guruswami and Riazanov, while stronger results for small values of $b=k$ were obtained by Arikan, by Dalai, Guruswami and Radhakrishnan, and by Costa and Dalai. In this paper, we strengthen the bounds for some specific values of $b$ and $k$. Our contribution is a new computational method for obtaining upper bounds on the values of a quadratic form defined over discrete probability distributions in arbitrary dimensions, which emerged as a central ingredient in recent works. The proposed method reduces an infinite-dimensional problem to a finite one, which we manage to further simplify by means of a series of optimality conditions. [ABSTRACT FROM AUTHOR]

Erasure codes are essential for providing efficient resilience against node failures in distributed storage. Typically, an $[n, k]$ erasure code encodes $k$ symbols into $n$ symbols which are then stored in different nodes. Recent work by Kadekodi et al. shows that the failure rates of storage nodes vary significantly over time, and that changing the rate of the code (via a change in $n$ and $k$) in response to such variations provides substantial storage space savings. However, the resource overhead of re-encoding the already encoded data is prohibitively high. We present a new theoretical framework formalizing code conversion—the process of converting data encoded with an $[n^{ I}, k^{ I}]$ code into data encoded with an $[{n^{ F}}, {k^{ F}}]$ code while maintaining desired decodability properties. We then introduce convertible codes, a new class of codes that allow for code conversions in a resource-efficient manner. This paper begins the study on convertible codes by focusing on linear MDS codes and the access cost of conversion. We derive a lower bound on the access cost of conversion and present an explicit optimal construction matching this bound for an important subclass of conversions. Additionally, we propose constructions with low field-size requirement for a broad subset of parameters. Our results show that it is possible to achieve code conversions with significantly less resources than the default approach of re-encoding for a wide range of parameters. [ABSTRACT FROM AUTHOR]

We study spatially coupled LDPC codes that allow access to sub-blocks much smaller than the full code block. Sub-block access is realized by a semi-global decoder that decodes a chosen target sub-block by only accessing the target, plus a prescribed number of helper sub-blocks adjacent in the code chain. This paper develops a theoretical methodology for analyzing the semi-global decoding performance of spatially coupled LDPC codes constructed from protographs. The main result shows that semi-global decoding thresholds can be derived from certain thresholds we define for the single-sub-block graph. These characterizing thresholds are also used for deriving lower bounds on the decoder’s performance over channels with variability across sub-blocks, which are motivated by applications in data storage. [ABSTRACT FROM AUTHOR]

We consider the concatenation of a convolutional code (CC) with an optimized cyclic redundancy check (CRC) code as a promising paradigm for good short blocklength codes. The resulting CRC-aided convolutional code naturally permits the use of serial list Viterbi decoding (SLVD) to achieve maximum-likelihood decoding. The convolutional encoder of interest is of rate- $1/\omega $ and the convolutional code is either zero-terminated (ZT) or tail-biting (TB). The resulting CRC-aided convolutional code is called a CRC-ZTCC or a CRC-TBCC. To design a good CRC-aided convolutional code, we propose the distance-spectrum optimal (DSO) CRC polynomial. A DSO CRC search algorithm for the TBCC is provided. Our analysis reveals that the complexity of SLVD is governed by the expected list rank which converges to 1 at high SNR. This allows a good performance to be achieved with a small increase in complexity. In this paper, we focus on transmitting 64 information bits with a rate-1/2 convolutional encoder. For a target error probability $10^{-4}$ , simulations show that the best CRC-ZTCC approaches the random-coding union (RCU) bound within 0.4 dB. Several CRC-TBCCs outperform the RCU bound at moderate SNR values. [ABSTRACT FROM AUTHOR]

Previous algorithms for decoding AG codes up to the designed distance all assumed existence of an extra rational place on the base algebraic curve. The place is used to solve the decoding problem by linear algebra over the base field of the curve. The rationality of the place is essential, and therefore AG codes supported by all rational places on the curve are excluded from the domain of applicability of the decoding algorithms. This paper presents a decoding algorithm for those AG codes using an extra place of higher degree. Hence finally all AG codes, as Goppa defined 40 years ago, are equipped with a fast decoding algorithm. [ABSTRACT FROM AUTHOR]

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

This paper derives the optimal test channel distribution and the complete characterization of the classical Gorbunov and Pinsker (1973), Gorbunov and Pinsker (1974) nonanticipatory epsilon entropy of multivariate Gaussian Markov sources with square-error fidelity, which remained an open problem since 1974. The paper also formulates a state dependent nonanticipatory epsilon entropy, in which past reproductions are available to the decoder and not to the encoder, the test channel is specified with respect to an auxiliary (state) random process, and the reproduction process is a causal function of past reproduction and the auxiliary random process. This variation is analogous to the Wyner and Ziv (1976) and Wyner (1978) rate distortion function (RDF), of memoryless sources. It is shown that the operational rate of zero-delay codes, with past reproductions available to the decoder but not to the encoder is bounded below by the state dependent nonanticipatory epsilon entropy rate. For the case of multivariate Gaussian Markov sources with square-error fidelity, the optimal test channel distribution and the complete characterization of the state dependent of nonanticipatory epsilon entropy are derived, and also shown that that the two nonanticipatory epsilon entropies coincide. The derivations are new; they are based on structural properties of the stochastic realizations of the reproduction process that induce the optimal test channel distributions. They are derived using, achievable lower bounds on information theoretic measures, properties of mean-square estimation theory, Hadamard’s inequality, and canonical correlation coefficients of a tuple of multivariate jointly Gaussian random processes. Applications of the nonanticipatory epsilon entropy and its state dependent variation are discussed to the areas of control of unstable Gaussian systems over limited memory channels, design of causal estimators for Gaussian Markov sources with a fidelity criterion, computation of the rate loss of causal and zero-delay codes of Gaussian Markov sources with respect to non-causal codes. [ABSTRACT FROM AUTHOR]

This paper investigates the secret key-authenticated-capacity region, where information-theoretic authentication is defined by the ability of the decoder to accept and decode messages originating from a valid encoder while rejecting messages from other invalid sources. The model considered here consists of a valid encoder-decoder pairing that can communicate through a channel controlled by an adversary who is also able to eavesdrop on the encoder’s transmissions. Prior to the encoder’s transmission, the adversary decides whether or not to replace the decoder’s observation with an arbitrary one of the adversary’s choosing, with the adversary’s objective being to have the decoder accept and decode their observation to a valid message (different from that of the encoder). To combat the adversary, the encoder and decoder share a secret key. The secret key-authenticated-capacity region is defined as the region of jointly achievable message rate, authentication rate (a to be defined per symbol measure that will generally represent the likelihood that an adversary can fool the decoder), and the key-consumption rate (how many bits of secret key are needed per symbol sent). This is the second of a two-part study, with the parts differing in their measure of the authentication rate. For this second study, the probability of false authentication is considered as a function of the system state, where the system state is defined by the message being transmitted, the value of the secret key, the adversary’s channel observations, and the adversary’s (possibly stochastic) choice for the decoder’s observation. Termed the typical-authentication rate, the authentication measure considered here corresponds to an upper bound on the probability of false authentication for the majority of system states. For this measure, we derive matching inner and outer bounds for the secret key-enabled authenticated capacity region in terms of traditional information-theoretic measures. In doing so, it is shown that the typical-authentication rate and the message rate exhibit a one-to-one trade-off in the capacity region. [ABSTRACT FROM AUTHOR]

In this paper, we establish an interesting duality between two different quantum information-processing tasks, namely, classical source coding with quantum side information, and channel coding over classical-quantum channels. The duality relates the optimal error exponents of these two tasks, generalizing the classical results of Ahlswede and Dueck [IEEE Trans. Inf. Theory, 28(3):430–443, 1982]. We establish duality both at the operational level and at the level of the entropic quantities characterizing these exponents. For the latter, the duality is given by an exact relation, whereas for the former, duality manifests itself in the following sense: an optimal coding strategy for one task can be used to construct an optimal coding strategy for the other task. Along the way, we derive a bound on the error exponent for classical-quantum channel coding with constant composition codes which might be of independent interest. Finally, we consider the task of variable-length classical compression with quantum side information, and a duality relation between this task and classical-quantum channel coding can also be established correspondingly. Furthermore, we study the strong converse of this task, and show that the strong converse property does not hold even in the i.i.d. scenario. [ABSTRACT FROM AUTHOR]

This paper investigates the secret-key-authenticated-capacity region, where information-theoretic authentication is defined by the ability of the decoder to accept and decode messages originating from a valid encoder while rejecting messages from other invalid sources. The model considered here consists of a valid encoder-decoder pairing that can communicate through a channel controlled by an adversary who is also able to eavesdrop on the encoder’s transmissions. Over multiple rounds of communication, the adversary first decides whether or not to replace the decoder’s observation with an arbitrary one of the adversary’s choosing, with the goal of the adversary being to have the decoder accept and decode their observation as a valid message (different from that of the encoder). To combat the adversary, the encoder and decoder share a secret key. The secret-key-authenticated-capacity region here is then defined as the region of jointly achievable message rate, authentication rate (a to be defined per symbol measure that will generally represent the likelihood that an adversary can fool the decoder), and the key-consumption rate (how many bits of secret key are needed per symbol sent). This is the first of a two-part study, with the parts differing in their measure of the authentication rate. In this first study, the authentication rate is the exponent of blocklength-normalized exponent of the expected probability of false authentication. For this metric, we provide an inner bound which improves on those existing in the literature. This is achieved by adopting and merging different classical techniques in novel ways. Within these classical secret-key-based authentication techniques, one technique derives authentication capability from secure channel coding to send the secret key with the message, and the other technique derives its authentication capability directly from obscuring the source. [ABSTRACT FROM AUTHOR]

This article studies the zero-error feedback capacity of causal discrete channels with memory. First, by extending the classical zero-error feedback capacity concept, a new notion of uniform zero-error feedback capacity $C_{0f} $ for such channels is introduced. Using this notion a tight condition for bounded stabilization of unstable noisy linear systems via causal channels is obtained, assuming no channel state information at either end of the channel. Furthermore, the zero-error feedback capacity of a class of additive noise channels is investigated. It is known that for a discrete channel with correlated additive noise, the ordinary capacity with or without feedback is equal $\log q-\mathcal {H}_{ch} $ , where $\mathcal {H}_{ch} $ is the entropy rate of the noise process and $q $ is the input alphabet size. In this paper, for a class of finite-state additive noise channels (FSANCs), it is shown that the zero-error feedback capacity is either zero or $C_{0f} =\log q -h_{ch} $ , where $h_{ch} $ is the topological entropy of the noise process. A condition is given to determine when the zero-error capacity with or without feedback is zero. This, in conjunction with the stabilization result, leads to a “Small-Entropy Theorem”, stating that stabilization over FSANCs can be achieved if the sum of the topological entropies of the linear system and the channel is smaller than $\log q$. [ABSTRACT FROM AUTHOR]

Constrained codes are used to prevent errors from occurring in various data storage and data transmission systems. They can help in increasing the storage density of magnetic storage devices, in managing the lifetime of solid-state storage devices, and in increasing the reliability of data transmission over wires. Over the years, designing practical (complexity-wise) capacity-achieving constrained codes has been an area of research gaining significant interest. We recently designed various constrained codes based on lexicographic indexing. We introduced binary symmetric lexicographically-ordered constrained (S-LOCO) codes, $q$ -ary asymmetric LOCO (QA-LOCO) codes, and a class of two-dimensional LOCO (TD-LOCO) codes. These families of codes achieve capacity with simple encoding and decoding, and they are easy to reconfigure. We demonstrated that these codes can contribute to notable density and lifetime gains in magnetic recording (MR) and Flash systems, and they find application in other systems too. In this paper, we generalize our work on LOCO codes by presenting a systematic method that guides the code designer to build any constrained code based on lexicographic indexing once the finite set of data patterns to forbid is known. In particular, we connect the set of forbidden patterns directly to the cardinality of the LOCO code and most importantly to the rule that uncovers the index associated with a LOCO codeword. By doing that, we reveal the secret arithmetic of patterns, and make the design of such constrained codes significantly easier. We give examples illustrating the method via codes based on lexicographic indexing from the literature. We then design optimal (rate-wise) constrained codes for the new two-dimensional magnetic recording (TDMR) technology. Over a practical TDMR model, we show notable performance gains as a result of solely applying the new codes. Moreover, we show how near-optimal constrained codes for TDMR can be designed and used to further reduce complexity and error propagation. All the newly introduced LOCO codes are designed using the proposed general method, and they inherit all the desirable properties in our previously designed LOCO codes. [ABSTRACT FROM AUTHOR]

In this paper we introduce Ouroboros, a new family of Key Exchange protocols based on coding theory. The protocols propose a middle ground between the cryptosystems based on $\mathsf {QC}$ - $\mathsf {MDPC}$ codes, which feature small parameter sizes, but have a security reduction to two problems: the syndrome decoding problem and the indistinguishability of the code, and the HQC protocol, which features bigger parameters but has a security reduction to the syndrome decoding problem only. Ouroboros features a reduction to the syndrome decoding problem with only a small overhead compared to the $\mathsf {QC}$ - $\mathsf {MDPC}$ based cryptosystems. The approach is based on an ideal structure and also works for the rank metric. This yields a simple, secure and efficient approach for key exchange, the Ouroboros family of protocols. For the Hamming metric we obtain the same type of parameters (and almost the same simple decoding) as for $\mathsf {MDPC}$ based cryptosystems, but with a security reduction to decoding random quasi-cyclic codes in the Random Oracle Model. This represents a reduction of up to 38% on the public key size compared to HQC, for the most secure parameters. For the rank metric, we obtain better parameters than for RQC, saving up to 31% on the public key for the most secure set of parameters, using non homogeneous errors in Ouroboros. In this full version, the protocol and decoding algorithm have been slightly improved, additional details are given in the security proof, and the protocol is fully described for the rank metric. [ABSTRACT FROM AUTHOR]

Previous works on age of information and erasure channels have dealt with specific models and computed the average age or average peak age for certain settings. In this paper, given a source that produces a letter every $T_{s}$ seconds and an erasure channel that can be used every $T_{c}$ seconds, we ask what is the coding strategy that minimizes the time-average “age of information” that an observer of the channel output incurs. We first analyze the case where the source alphabet and the channel-input alphabet have the same size. We show that a trivial coding strategy is optimal and a closed form expression for the age can be derived. We then analyze the case where the alphabets have different sizes. We use a random coding argument to bound the average age and show that the average age achieved using random codes converges to the optimal average age of linear block codes as the source alphabet becomes large. [ABSTRACT FROM AUTHOR]

This paper studies reconstruction of strings based upon their substrings spectrum. Under this paradigm, it is assumed that all substrings of some fixed length are received and the goal is to reconstruct the string. While many existing works assumed that substrings are received error free, we follow in this paper the noisy setup of this problem that was first studied by Gabrys and Milenkovic. The goal of this study is twofold. First we study the setup in which not all substrings in the multispectrum are received, and then we focus on the case where the read substrings are not error free. In each case we provide specific code constructions of strings that their reconstruction is guaranteed even in the presence of failure in either model. We present efficient encoding and decoding maps and analyze the cardinality of the code constructions, while studying the cases where the rates of our codes approach 1. [ABSTRACT FROM AUTHOR]

Communication over a random-parameter quantum channel when the decoder is required to reconstruct the parameter sequence is considered. We study scenarios that include either strictly-causal, causal, or non-causal channel side information (CSI) available at the encoder, and also when CSI is not available. This model can be viewed as a form of quantum metrology, and as the quantum counterpart of the classical rate-and-state channel with state estimation at the decoder. Regularized formulas for the capacity-distortion regions are derived. In the special case of measurement channels, single-letter characterizations are derived for the strictly-causal and causal settings. Furthermore, in the more general case of entanglement-breaking channels, a single-letter characterization is derived when CSI is not available. As a consequence, we obtain regularized formulas for the capacity of random-parameter quantum channels with CSI, generalizing previous results by Boche et al., 2016, on classical-quantum channels. Bosonic dirty paper coding is introduced as a consequence, where we demonstrate that the optimal coefficient is not necessarily that of minimum mean-square error estimation as in the classical setting. [ABSTRACT FROM AUTHOR]

In this paper, we formulate the problem to cope with the transmission of extra bits over an existing coded transmission link (referred to as coded payload link) without any cost of extra transmission energy or extra bandwidth. This is possible since a gap to the channel capacity typically exists for a practical code. A new concept, termed as accessible capacity, is introduced to specify the maximum rate at which the superposition transmission of extra bits is reliable and has a negligible effect on the performance of the coded payload link. For a binary-input output-symmetric (BIOS) memoryless channel, the accessible capacity can be characterized as the difference between the channel capacity and the mutual information rate of the coded payload link, which can be numerically evaluated for very short payload codes. For a general payload code, we present a simple lower bound on the accessible capacity, given by the channel capacity minus the coding rate of the payload code. We then focus on the scenarios where low-density parity-check (LDPC) codes are implemented for the payload link. We propose to transmit extra bits by random superposition for encoding, and exhaustive search (with the aid of statistical learning) for decoding. We further propose, by establishing an auxiliary channel (called syndrome channel) induced from “zero-forcing” over the binary field, to transmit extra bits with structured codes such as repetition codes and first-order Reed-Muller (RM) codes. Numerical results show that up to 60 extra bits can be reliably transmitted along with a rate-1/2 LDPC code of length 8064. [ABSTRACT FROM AUTHOR]

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

This paper studies the problem of constructing codes correcting deletions in arrays. Under this model, it is assumed that an $n \times n$ array can experience deletions of rows and columns. These deletion errors are referred to as $({t_{\mathrm {r}}}, {t_{\mathrm {c}}})$ -criss-cross deletions if ${t_{\mathrm {r}}}$ rows and ${t_{\mathrm {c}}}$ columns are deleted, while a code correcting these deletion patterns is called a $({t_{\mathrm {r}}}, {t_{\mathrm {c}}})$ -criss-cross deletion correction code. The definitions for criss-cross insertions are similar. It is first shown that when $t_{r}=t_{c}$ the problems of correcting criss-cross deletions and criss-cross insertions are equivalent. The focus of this paper lies on the case of (1, 1)-criss-cross deletions. A non-asymptotic upper bound on the cardinality of (1, 1)-criss-cross deletion correction codes is shown which assures that the redundancy is at least $2n-3+2\log n$ bits. A code construction with an existential encoding and an explicit decoding algorithm is presented. The redundancy of the construction is at most $2n+4 \log n + 7 +2 \log e$. A construction with explicit encoder and decoder is presented. The explicit encoder adds an extra $5\log n + 5$ bits of redundancy to the construction. [ABSTRACT FROM AUTHOR]

The variable-length source coding problem allowing the error probability up to some constant is considered for general sources. In this problem, the optimum mean codeword length of variable-length codes has already been determined. On the other hand, in this paper, we focus on the overflow (or excess codeword length) probability instead of the mean codeword length. The infimum of overflow thresholds under the constraint that both of the error probability and the overflow probability are smaller than or equal to some constant is called the optimum overflow threshold. In this paper, we first derive finite-length upper and lower bounds on these probabilities so as to analyze the optimum overflow thresholds. Then, by using these bounds, we determine the general formula of the optimum overflow thresholds in both of the first-order and second-order forms. Next, we consider another expression of the derived general formula so as to reveal the relationship with the optimum coding rate in the fixed-length source coding problem. Finally, we apply the general formula derived in this paper to the case of stationary memoryless sources. [ABSTRACT FROM AUTHOR]

Reed-Solomon (RS) codes are widely used in distributed storage systems. In this paper, we study the repair bandwidth and sub-packetization size of RS codes. The repair bandwidth is defined as the amount of transmitted information from surviving nodes to a failed node. The RS code can be viewed as a polynomial over a finite field $GF(q^\ell)$ evaluated at a set of points, where $\ell $ is called the sub-packetization size. Smaller bandwidth reduces the network traffic in distributed storage, and smaller $\ell $ facilitates the implementation of RS codes with lower complexity. Recently, Guruswami and Wootters proposed a repair method for RS codes when the evaluation points are the entire finite field. While the sub-packetization size can be arbitrarily small, the repair bandwidth is higher than the minimum storage regenerating (MSR) bound. Tamo, Ye, and Barg achieved the MSR bound but the sub-packetization size grows faster than the exponential function of the number of the evaluation points. In this paper, we present code constructions and repair schemes that extend these results to accommodate different sizes of the evaluation points. In other words, we design schemes that provide points in between. These schemes provide a flexible tradeoff between the sub-packetization size and the repair bandwidth. In addition, we generalize our schemes to manage multiple failures. [ABSTRACT FROM AUTHOR]

Linear codes over $\mathbb {Z}_{p^{s}}$ of length $n$ are subgroups of $\mathbb {Z}_{p^{s}}^{n}$. These codes are also called $\mathbb {Z}_{p^{s}}$ -additive codes and can be seen as a generalization of linear codes over $\mathbb {Z}_{2}$ and $\mathbb {Z}_{4}$. A $\mathbb {Z}_{p^{s}}$ -linear code is a code over $\mathbb {Z}_{p}$ , not necessarily linear, which is the generalized Gray map image of a $\mathbb {Z}_{p^{s}}$ -additive code. In 2015, a systematic encoding was found for $\mathbb {Z}_{4}$ -linear codes. Moreover, an alternative permutation decoding method, which is suitable for any binary code (not necessarily linear) with a systematic encoding, was established. In this paper, we generalize these results by presenting a systematic encoding for any $\mathbb {Z}_{p^{s}}$ -linear code with $s\geq 2$ and $p$ prime. We also describe a permutation decoding method for any systematic code over $\mathbb {Z}_{p}$ , not necessarily linear, and show some examples of how to use this systematic encoding in this decoding method. [ABSTRACT FROM AUTHOR]

This paper presents the first systematic study of the zero-error capacity regions of noisy networks. First, we consider two simple such networks, each consisting of a stationary memoryless multiple access channel with two binary inputs and one discrete output. There are two users in each network. Each of the two users transmits a message through the network, and the sink(s) of the network can decode both messages with zero error. A graph is used to represent the distinguishability of the inputs of the channel, and a graph set is used to represent the distinguishability of the inputs of the network. We show that for two networks represented by the same graph set, their zero-error capacity regions are the same. We list all the possible graph sets for the two networks and determine the zero-error capacity regions for some of these graph sets. Based on this result, we explore a relation between graph theory and set theory, and then redefine the cancellative pair of families of subsets. We further extend the problem formulation to a general network called the parallel network, which may consist of more than one channel with multiple inputs and multiple outputs. [ABSTRACT FROM AUTHOR]

Sum-rank metric codes have recently attracted the attention of many researchers, due to their relevance in several applications. Mathematically, the sum-rank metric is a natural generalization of both the Hamming metric and the rank metric. In this paper, we provide an Anticode Bound for the sum-rank metric, which extends the corresponding Hamming and rank-metric Anticode bounds. We classify then optimal anticodes, i.e., codes attaining the sum-rank metric Anticode Bound. We use these optimal anticodes to define generalized sum-rank weights and we study their main properties. In particular, we prove that the generalized weights of an MSRD code are determined by its parameters. As an application, in the Appendix we explain how generalized weights measure information leakage in multishot network coding. [ABSTRACT FROM AUTHOR]

This paper studies the second-order coding rates for memoryless channels with a state sequence known non-causally at the encoder. In the case of finite alphabets, an achievability result is obtained using constant-composition random coding, and by using a small fraction of the block to transmit the empirical distribution of the state sequence. For error probabilities less than 0.5, it is shown that the second-order rate improves on an existing one based on independent and identically distributed random coding. In the Gaussian case (dirty paper coding) with an almost-sure power constraint, an achievability result is obtained using random coding over the surface of a sphere, and using a small fraction of the block to transmit a quantized description of the state power. It is shown that the second-order asymptotics are identical to the single-user Gaussian channel of the same input power without a state. [ABSTRACT FROM AUTHOR]

The group testing problem consists of determining a small set of defective items from a larger set of items based on tests on groups of items, and is relevant in applications such as medical testing, communication protocols, pattern matching, and many more. While rigorous group testing algorithms have long been known with runtime at least linear in the number of items, a recent line of works has sought to reduce the runtime to ${\mathrm{ poly}}({k} \log {n})$ , where n is the number of items and k is the number of defectives. In this paper, we present such an algorithm for non-adaptive group testing termed bit mixing coding (BMC), which builds on techniques that encode item indices in the test matrix, while incorporating novel ideas based on erasure-correction coding. We show that BMC achieves asymptotically vanishing error probability with ${O}({k} \log {n})$ tests and ${O}({k}^{2} \cdot \log {k} \cdot \log {n})$ runtime, in the limit as ${n} \to \infty $ (with k having an arbitrary dependence on n). This closes an open problem of simultaneously achieving ${\mathrm{ poly}}({k} \log {n})$ decoding time using ${O}({k} \log {n})$ tests without any assumptions on k. In addition, we show that the same scaling laws can be attained in a commonly-considered noisy setting, in which each test outcome is flipped with constant probability. [ABSTRACT FROM AUTHOR]

A multi-resolution quantizer is a sequence of quantizers where the output of a coarser quantizer can be deduced from the output of a finer quantizer. In this paper, we propose an asymptotically scale-invariant multi-resolution quantizer, which performs uniformly across any choice of average quantization step, when the length of the range of input numbers is large. Scale invariance is especially useful in worst case or adversarial settings, ensuring that the performance of the quantizer would not be affected greatly by small changes of storage or error requirements. We also show that the proposed quantizer achieves a tradeoff between rate and error that is arbitrarily close to the optimum. [ABSTRACT FROM AUTHOR]

Deletion errors are notoriously difficult to correct. The capacity of the binary deletion channel is not yet fully known, and there is no completely satisfactory solution even to the specific problem of correcting only two deletion errors. In this paper, we show that polarization theory, along with the powerful methods of polar coding and successive-cancellation decoding, can be extended to channels with deletion errors. Our results further generalize to channels corrupted by insertion errors and/or combinations of insertions and deletions. It was recently proposed to correct deletion errors using polar codes designed for the BEC, precoded with a sufficiently powerful CRC code. In this approach, in order to correct ${d}$ deletions in a codeword of length ${n}$ , successive-cancellation decoding is run separately for each of the $\binom {n}{d}$ possible deletion patterns, while treating the deleted symbols as erasures. The resulting complexity of decoding is ${O}\bigl ({n}^{d+1}\log {n}\bigr)$. In contrast, we develop herein a natural generalization of successive-cancellation decoding to channels with deletion errors. Our algorithm is based on the recursive structure of polar codes, processing the channel output in ${m} = \log _{2} {n}$ decoding layers, just like the conventional successive-cancellation decoder. Every node in each decoding layer propagates its uncertainty about the deletion pattern to the nodes in the next layer and, eventually, the correct deletion pattern becomes visible at the decoder output, with high probability. This makes it possible to consider at most $\binom {d+2}{2}$ scenarios at each node, and the overall decoding complexity is only ${O}\bigl ({d}^{3} {n} \log {n}\bigr)$ , which scales polynomially rather than exponentially with the number of deletions. Based on the proposed algorithm, we also investigate the channel polarization phenomenon. We are able to prove weak polarization where the number of deletions ${d}$ is small, i.e. ${d}={o}({n})$. We also conjecture the strong polarization for when ${d}={O}(1)$ and provide some evidence to support this conjecture. The strong polarization, if proven, implies that our coding scheme achieves the capacity of any binary-input symmetric channel which furthermore introduces a constant number of deletions. [ABSTRACT FROM AUTHOR]

List decoding of insertions and deletions in the Levenshtein metric is considered. The Levenshtein distance between two sequences is the minimum number of insertions and deletions needed to turn one of the sequences into the other. In this paper, a Johnson-like upper bound on the maximum list size when list decoding in the Levenshtein metric is derived. This bound depends only on the length and minimum Levenshtein distance of the code, the length of the received word, and the alphabet size. It shows that polynomial-time list decoding beyond half the Levenshtein distance is possible for many parameters. Further, we also prove a lower bound on list decoding of deletions with the well-known binary Varshamov–Tenengolts codes, which shows that the maximum list size grows exponentially with the number of deletions. Finally, an efficient list decoding algorithm for two insertions/deletions with VT codes is given. This decoder can be modified to a polynomial-time list decoder of any constant number of insertions/deletions. [ABSTRACT FROM AUTHOR]

This paper investigates the decoding of a remarkable set of lattices: We treat in a unified framework the Leech lattice in dimension 24, the Nebe lattice in dimension 72, and the Barnes-Wall lattices. A new interesting lattice, named $L_{3\cdot 24}$ , is constructed as a simple application of the single parity check on the Leech lattice. The common aspect of these lattices is that they can be obtained via a single parity check or via the $k$ -ing construction. We exploit these constructions to introduce a new efficient paradigm for decoding. This leads to efficient list decoders and quasi-optimal decoders on the Gaussian channel. Both theoretical and practical performance (point error probability and complexity) of the new decoders are provided. [ABSTRACT FROM AUTHOR]

In this article, we present a new construction of evaluation codes in the Hamming metric, which we call twisted Reed–Solomon codes. Whereas Reed–Solomon (RS) codes are MDS codes, this need not be the case for twisted RS codes. Nonetheless, we show that our construction yields several families of MDS codes. Further, for a large subclass of (MDS) twisted RS codes, we show that the new codes are not generalized RS codes. To achieve this, we use properties of Schur squares of codes as well as an explicit description of the dual of a large subclass of our codes. We conclude the paper with a description of a decoder, that performs very well in practice as shown by extensive simulation results. [ABSTRACT FROM AUTHOR]

Quantum LDPC codes are a promising direction for low overhead quantum computing. In this paper, we propose a generalization of the Union-Find decoder as a decoder for quantum LDPC codes. We prove that this decoder corrects all errors with weight up to $An^\alpha $ for some $A, \alpha > 0$ , where $n$ is the code length, for different classes of quantum LDPC codes such as toric codes and hyperbolic codes in any dimension $D \geq 3$ and quantum expander codes. To prove this result, we introduce a notion of covering radius which measures the spread of an error from its syndrome. We believe this notion could find application beyond the decoding problem. We also perform numerical simulations, which show that our Union-Find decoder outperforms the belief propagation decoder in the low error rate regime in the case of a quantum LDPC code with length 3600. [ABSTRACT FROM AUTHOR]

For the recently developed quasi-reversible BCH codes with long lengths and high error-correcting capability, this paper is aimed at proposing a new and faster decoding procedure. It consists of four steps: 1) compute the consecutive syndromes; 2) calculate the syndrome functions by the forward and backward recursions; 3) solve a linear subsystem together with one matrix multiplication in order to find an error-locator polynomial; 4) determine the errors from the obtained polynomial by using the root-finding algorithm. This procedure, especially in Steps 2 and 3, differs greatly from the conventional procedures, which determine an error-locator polynomial directly from solving a linear system with the aid of the consecutive syndromes. The key idea behind this decoding technique is that the computational complexity of such a small subsystem instead of an originally large linear system can be significantly reduced, although there are additional forward and backward syndrome calculations with low complexity increasing. Finally, the illustrative examples and numerical simulations can be helpful to demonstrate the accuracy and efficacy of the presented decoding technique at different error-correcting capabilities. [ABSTRACT FROM AUTHOR]

The group testing problem consists of determining a small set of defective items from a larger set of items based on a number of possibly-noisy tests, and has numerous practical applications. One of the defining features of group testing is whether the tests are adaptive (i.e., a given test can be chosen based on all previous outcomes) or non-adaptive (i.e., all tests must be chosen in advance). In this paper, building on the success of binary splitting techniques in noiseless group testing (Hwang, 1972), we introduce noisy group testing algorithms that apply noisy binary search as a subroutine. We provide three variations of this approach with increasing complexity, culminating in an algorithm that succeeds using a number of tests that matches the best known previously (Scarlett, 2019), while overcoming fundamental practical limitations of the existing approach, and more precisely capturing the dependence of the number of tests on the error probability. We provide numerical experiments demonstrating that adaptive group testing strategies based on noisy binary search can be highly effective in practice, using significantly fewer tests compared to state-of-the-art non-adaptive strategies. [ABSTRACT FROM AUTHOR]

Coded computation techniques provide robustness against straggling workers in distributed computing. However, most of the existing schemes require exact provisioning of the straggling behavior and ignore the computations carried out by straggling workers. Moreover, these schemes are typically designed to recover the desired computation results accurately, while in many machine learning and iterative optimization algorithms, faster approximate solutions are known to result in an improvement in the overall convergence time. In this paper, we first introduce a novel coded matrix-vector multiplication scheme, called coded computation with partial recovery (CCPR), which benefits from the advantages of both coded and uncoded computation schemes, and reduces both the computation time and the decoding complexity by allowing a trade-off between the accuracy and the speed of computation. We then extend this approach to distributed implementation of more general computation tasks by proposing a coded communication scheme with partial recovery, where the results of subtasks computed by the workers are coded before being communicated. Numerical simulations on a large linear regression task confirm the benefits of the proposed scheme in terms of the trade-off between the computation accuracy and latency. [ABSTRACT FROM AUTHOR]

We investigate the equilibrium behavior for the decentralized cheap talk problem for real random variables and quadratic cost criteria in which an encoder and a decoder have misaligned objective functions. In prior work, it has been shown that the number of bins in any equilibrium has to be countable, generalizing a classical result due to Crawford and Sobel who considered sources with density supported on [0, 1]. In this paper, we first refine this result in the context of log-concave sources. For sources with two-sided unbounded support, we prove that, for any finite number of bins, there exists a unique equilibrium. In contrast, for sources with semi-unbounded support, there may be a finite upper bound on the number of bins in equilibrium depending on certain conditions stated explicitly. Moreover, we prove that for log-concave sources, the expected costs of the encoder and the decoder in equilibrium decrease as the number of bins increases. Furthermore, for strictly log-concave sources with two-sided unbounded support, we prove convergence to the unique equilibrium under best response dynamics which starts with a given number of bins, making a connection with the classical theory of optimal quantization and convergence results of Lloyd’s method. In addition, we consider more general sources which satisfy certain assumptions on the tail(s) of the distribution and we show that there exist equilibria with infinitely many bins for sources with two-sided unbounded support. Further explicit characterizations are provided for sources with exponential, Gaussian, and compactly-supported probability distributions. [ABSTRACT FROM AUTHOR]

A new family of codes, called clustering-correcting codes, is presented in this paper. This family of codes is motivated by the special structure of the data that is stored in DNA-based storage systems. The data stored in these systems has the form of unordered sequences, also called strands, and every strand is synthesized thousands to millions of times, where some of these copies are read back during sequencing. Due to the unordered structure of the strands, an important task in the decoding process is to place them in their correct order. This is usually accomplished by allocating part of the strand for an index. However, in the presence of errors in the index field, important information on the order of the strands may be lost. Clustering-correcting codes ensure that if the distance between the index fields of two strands is small, their data fields have large distance. It is shown how this property enables to place the strands together in their correct clusters even in the presence of errors. We present lower and upper bounds on the size of clustering-correcting codes and an explicit construction of these codes which uses only a single symbol of redundancy. The results are first presented for the Hamming metric and are then extended for the edit distance. [ABSTRACT FROM AUTHOR]

We consider a variable-length source coding problem subject to local decodability constraints. In particular, we investigate the blocklength scaling behavior attainable by encodings of $r$ -sparse binary sequences, under the constraint that any source bit can be correctly decoded upon probing at most $d$ codeword bits. We consider both adaptive and non-adaptive access models, and derive upper and lower bounds that often coincide up to constant factors. Such a characterization for the fixed-blocklength analog of our problem, known as the bit probe complexity of static membership, remains unknown despite considerable attention from researchers over the last few decades. We also show that locally decodable schemes for sparse sequences are able to decode 0s (frequent source symbols) of the source with far fewer probes on average than they can decode 1s (infrequent source symbols), thus rigorizing the notion that infrequent symbols require high probe complexity, even on average. Connections to the fixed-blocklength model and to communication complexity are also briefly discussed. [ABSTRACT FROM AUTHOR]

This paper studies a generalization of sparse superposition codes (SPARCs) for communication over the complex additive white Gaussian noise (AWGN) channel. In a SPARC, the codebook is defined in terms of a design matrix, and each codeword is a generated by multiplying the design matrix with a sparse message vector. In the standard SPARC construction, information is encoded in the locations of the non-zero entries of the message vector. In this paper we generalize the construction and consider modulated SPARCs, where information is encoded in both the locations and the values of the non-zero entries of the message vector. We focus on the case where the non-zero entries take values from a phase-shift keying (PSK) constellation. We propose a computationally efficient approximate message passing (AMP) decoder, and obtain analytical bounds on the state evolution parameters which predict the error performance of the decoder. Using these bounds we show that PSK-modulated SPARCs are asymptotically capacity achieving for the complex AWGN channel, with either spatial coupling or power allocation. We also provide numerical simulation results to demonstrate the error performance at finite code lengths. These results show that introducing modulation to the SPARC design can significantly reduce decoding complexity without sacrificing error performance. [ABSTRACT FROM AUTHOR]

Symbol-pair codes were introduced by Cassuto and Blaum in 2010 to protect pair errors in symbol-pair read channels. Recently Yaakobi, Bruck and Siegel (2016) generalized this notion to b-symbol codes in order to consider consecutive b errors for a prescribed integer b ≥ 2, and they gave constructions and decoding algorithms. Cyclic codes were considered by various authors as candidates for symbol-pair codes and they established minimum distance bounds on (certain) cyclic codes. In this paper we use algebraic curves over finite fields in order to obtain tight lower and upper bounds on b-symbol Hamming weights of arbitrary cyclic codes over Fq. Here b ≥ 2 is an arbitrary prescribed positive integer and Fq is an arbitrary finite field. We also present a stability theorem for an arbitrary cyclic code C of dimension k and length n: the b-symbol Hamming weight enumerator of C is the same as the k-symbol Hamming weight enumerator of C if k ≤ b ≤ n−1. Moreover, we give improved tight lower and upper bounds on b-symbol Hamming weights of some cyclic codes related to irreducible cyclic codes. Throughout the paper the length n is coprime to q. [ABSTRACT FROM AUTHOR]

In this paper, we propose a systematic low density generator matrix (LDGM) code ensemble, which is defined by the Bernoulli process. We prove that, under maximum likelihood (ML) decoding, the proposed ensemble can achieve the capacity of binary-input output symmetric (BIOS) memoryless channels in terms of bit error rate (BER). The proof technique reveals a new mechanism, different from lowering down frame error rate (FER), that the BER can be lowered down by assigning light codeword vectors to light information vectors. The finite length performance is analyzed by deriving an upper bound and a lower bound, both of which are shown to be tight in the high signal-to-noise ratio (SNR) region. To improve the waterfall performance, we construct the systematic convolutional LDGM (SysConv-LDGM) codes by a random splitting process. The SysConv-LDGM codes are easily configurable in the sense that any rational code rate can be realized without complex optimization. As a universal construction, the main advantage of the SysConv-LDGM codes is their near-capacity performance in the waterfall region and predictable performance in the error-floor region that can be lowered down to any target as required by increasing the density of the uncoupled LDGM codes. Numerical results are also provided to verify our analysis. [ABSTRACT FROM AUTHOR]