In this work, we propose a system for joint security and error correction at the physical layer. The proposed approach combines the ideas from the area of wiretap channel coding together with a variant of the McEliece public key cryptosystem. The system makes use of randomly chosen nonbinary low-density parity-check codes with quasi-cyclic base matrices. Such a choice allows for efficient hiding of the structure of the generator matrix of the code, thus allowing for protection of the data against the eavedropper's attacks. At the same time, it also supports an efficient error correction. The analysis of the complexity of the attacks and the simulation results demonstrate the advantages of the proposed system.

An approach for estimation of the maximum-likelihood (ML) decoding error probability for coded shaped QAM signals is proposed. It is based on approximation of the squared Euclidean distance spectra of the coded shaped signal constellations. Two variants of shaping used in the communication system with coded QAM signaling are studied: shaping before coding (SBC) and shaping after coding (SAC). First, the new approach is verified by applying it to short codes. Then, it is used to derive a random coding bound on the ML decoding error probability for the ensemble of binary linear codes. Simulation results for the frame error rate (FER) performance of belief-propagation decoding for the optimized nonbinary (NB) quasicyclic (QC)-LDPC codes used with SBC and SAC, as well as the same performance of the binary QC-LDPC block codes in the 5G standard are compared to the new bound.

This paper studies specific properties of nonbinary low-density parity-check (NB LDPC) codes when used in coded modulation systems. The paper is focused on the practically important NB LDPC codes over the Galois extension fields GF$(2^{m})$with$m\le 6$used with QAM signaling. Performance of NB LDPC coded transmission strongly depends on the mapping of nonbinary symbols to signal constellation points. We obtain a random coding bound on the maximum-likelihood decoding error probability for an ensemble of random irregular NB LDPC codes used with QAM signaling for specific symbol-to-signal point mappings. This bound is based on the ensemble average squared Euclidean distance spectra derived for these mappings. The simulation results for the belief-propagation decoding in the coded modulation schemes with the NB quasi-cyclic (QC)-LDPC codes under different mappings are given. Comparisons with the optimized binary QC-LDPC codes in the WiFi and 5G standards, as well as with the new bound, are performed.

In some lattice-based cryptosystems, the encryption and decryption processes can be interpreted as a noisy communication channel. In this work, we focus on cryptosystems based on the ring learning with errors (RLWE) and module learning with errors (MLWE) problems, e.g. Kyber. We provide new coding schemes for the communication channel involved in these cryptosystems. For encoding we use an error-correction code (ECC) along with modulo Q pulse amplitude modulation (PAM) (for some fixed small prime power Q), and vector dequantization. For decoding we perform vector quantization followed by hard/soft decision decoding (HDD/SDD) for the ECC. This construction provides remarkable reduction in the decryption failure rate (DFR), compared to some earlier proposed coding schemes for the same bitrate. For example, in Kyber encryption scheme, we reduce the DFR from 2−174(uncoded) to 2−1325(using HDD) or 2−1414(using SDD).

Invertible Bloom Filter (IBF) is a data structure, which employs a small set of hash functions. An IBF allows for an efficient insertion and, with high probability, for an efficient extraction of the data. However, the success probability of the extraction depends on the storage overhead of an IBF and the amount of the data stored. In an application, such as set reconciliation, where there is a need to extract data stored in the IBF, the extraction might succeed only partially, by recovering only part of the stored data. In this work, the probability of success for a partial extraction of data from an IBF is analyzed. It is shown that partial extraction could be useful in applications, such as set reconciliation. In particular, it allows for set reconciliation by using the IBF, where the storage overhead is too small to allow full extraction.

We propose a novel approach to optimization of irregular nonbinary (NB) quasi-cyclic (QC)-LDPC codes over small alphabets. In this approach, first, the base parity-check matrices are constructed by a simulated annealing method, and then these matrices are labeled by the field elements while maximizing the so- called generalized girth of the Tanner graph. In order to analyze the performance of the constructed irregular NB LDPC codes, a new ensemble of irregular NB LDPC codes over the extensions of the binary Galois field is introduced. A finite-length random coding bound on the error probability of the maximum-likelihood (ML) decoding over the binary phase shift keying (BPSK) input AWGN channel for the new code ensemble is derived. The frame error rate (FER) performance of the sum-product belief-propagation (BP) decoding of the constructed NB QC-LDPC block codes is compared to that of both the optimized binary QC-LDPC block codes in the 5G standard and the best known NB QC-LDPC codes as well as to the derived random coding bound on the ML decoding error probability. It is shown that the obtained bound predicts the behavior of BP decoding performance of practical NB QC-LDPC codes more accurately than the BP decoding thresholds do.

We propose a new model of asynchronous batch codes that allow for parallel recovery of information symbols from a coded database in an asynchronous manner, i.e. when requests arrive at random times and they take varying time to process. We show that the graph-based batch codes studied by Rawatet al.are asynchronous. Further, we demonstrate that hypergraphs of Berge girth larger or equal to 4, respectively larger or equal to 3, yield graph-based asynchronous batch codes, respectively private information retrieval (PIR) codes. We prove a hypergraph-theoretic proposition that the maximum number of hyperedges in a hypergraph of a fixed Berge girth equals the quantity in a certain generalization of the hypergraph-theoretic (6,3)-problem, first posed by Brown, Erdős and Sós. We then apply the constructions and bounds by Erdős, Frankl and Rödl about this generalization of the (6,3)-problem, known as the ($3\varrho $-3,$\varrho $)-problem, to obtain batch code constructions and bounds on the redundancy of the graph-based asynchronous batch and PIR codes. We derive bounds on the optimal redundancy of several families of asynchronous batch codes with the query size$t=2$. In particular, we show that the optimal redundancy$\rho (k)$of graph-based asynchronous batch codes of dimension$k$for$t=2$is$2\sqrt {k}$. Moreover, for graph-based asynchronous batch codes with$t \ge 3$,$\rho (k) = O\left ({{k}^{1/(2-\epsilon)}}\right)$for any small$\epsilon >0$.

Properties of non-binary (NB) LDPC codes used in conjunction with coded modulation systems are studied. It is observed that the performance of the NB LDPC coded transmission schemes strongly depends on the mapping between the NB symbols and the signal constellation points. The Euclidean distance spectra for an ensemble of random NB LDPC codes for specific mappings are derived. The simulation results for belief-propagation decoding in the coded modulation schemes with the NB QC-LDPC codes under different mappings are presented.

A finite-length random coding bound on the maximum-likelihood decoding error probability for an ensemble of irregular nonbinary (NB) low-density parity-check (LDPC) codes with QAM signaling for specific code symbol-to-signal mappings is derived. Simulation results for the frame error rate (FER) performance of belief-propagation decoding for the optimized NB quasi-cyclic (QC)-LDPC codes used in various coded modulation schemes are presented. Comparison with the same performance of the optimized binary QC-LDPC block codes in the WiFi and 5G standards, as well as with the new bound, is performed.

We propose a novel approach for optimization of nonbinary (NB) quasi-cyclic (QC)-LDPC codes. In this approach, the base parity-check matrices are constructed by the simulated annealing method, and then labeled while maximizing the so-called generalized girth of the NB LDPC code Tanner graph. Random coding bounds on the ML decoding error probability for ensembles of "almost regular" NB LDPC codes of finite lengths over extensions of the binary Galois field are derived. These bounds are based on the average bit weight spectra for the ensembles of NB LDPC codes. The observed FER performance of the sum-product BP decoding of "almost regular" NB QC-LDPC block codes is presented and compared to the finite-length random coding bounds, as well as to the performance of the optimized binary QC-LDPC block code in the 5G standard. In the waterfall region, the gap between the finite-length bounds on the error probability of the ML decoding and the simulation performance of the BP decoding is about 0.1 – 0.2 dB.

One of the most efficient approaches to improving the frame error rate (FER) performance of low-density parity-check (LDPC) codes is based on adding both auxiliary variable nodes (AVN) and the corresponding redundant parity checks (RPC) to the binary parity-check matrices of the code. It is known that for the LDPC codes, whose Tanner graphs contain length four cycles, this technique allows for substantial improvement in the FER performance of the belief-propagation (BP) decoding on the binary erasure channel (BEC) channel. The AVN-based technique followed by adding orthogonal redundant parity-checks is known to be efficient for both the BEC and additive white Gaussian noise (AWGN) channels. In this paper, firstly, the AVN-based approach is generalized to efficiently removing cycles of length larger than four. Secondly, the AVN-based technique is reformulated in terms of labeled base matrices of quasi-cyclic (QC) LDPC codes. An improved iterative decoding of QC LDPC codes is proposed, which is applied to the labeled base matrices of QC LDPC codes extended by the AVN-RPC technique.

The performance of maximum-likelihood (ML) decoding on the binary erasure channel for finite-length low-density parity-check (LDPC) codes from two random ensembles is studied. A tightened union-type upper bound on the ML decoding error probability based on the precise coefficients of the average weight spectrum is presented. For LDPC codes from the Gallager ensemble and the Richardson-Urbanke ensemble, new upper bounds on the ML decoding performance based on computing the rank of submatrices of the code parity-check matrix are derived. A new lower bound on the ML decoding threshold followed from the latter error probability bound is obtained. An improved lower bound on the error probability for codes with a known estimate on the minimum distance is presented as well. A new low-complexity near-ML decoding algorithm for quasi-cyclic LDPC codes is proposed and simulated. Its performance is compared to the simulated belief propagation and ML decoding performance and simulated performance of the best known improved iterative decoding techniques, as well as, with the derived upper bounds on the ML decoding performance and with decoding thresholds obtained by the density evolution technique.

A new method is presented for low-complexity near-maximum-likelihood (ML) decoding of low-density parity-check (LDPC) codes over the additive white Gaussian noise channel. The proposed method termed belief-propagation-list erasure decoding (BP-LED) is based on erasing carefully chosen unreliable bits performed in case of BP decoding failure. A strategy of introducing erasures into the received vector and a new erasure decoding algorithm are proposed. The new erasure decoding algorithm, called list erasure decoding, combines ML decoding over the BEC with list decoding applied if the ML decoder fails to find a unique solution. The asymptotic exponent of the average list size for random regular LDPC codes from the Gallager ensemble is analyzed. Furthermore, a few examples of irregular quasi-cyclic LDPC as well as randomly constructed regular LDPC codes of short and moderate lengths are studied by simulations and their performance is compared to the tightened upper bound on the LDPC ensemble-average performance and the upper bound on the average performance of random linear codes under ML decoding. A comparison of the BP decoding and BP-LED performance of the WiMAX standard codes and performance of the near-ML BEAST decoding are presented. The new algorithm is applied to decoding a short nonbinary (NB) LDPC code over extensions of the binary Galois field. The obtained simulation results are compared to the tightened upper bound on the ensemble-average performance of the binary image of regular NB LDPC codes.

Stopping sets play a crucial role in failure events of iterative decoders over a binary erasure channel (BEC). The ℓth stopping redundancy is the minimum number of rows in the parity-check matrix of a code, which contains no stopping sets of size up to ℓ. In this paper, a notion of coverable stopping sets is defined. In order to achieve maximum-likelihood performance under iterative decoding over the BEC, the parity-check matrix should contain no coverable stopping sets of size ℓ, for 1 ≤ ℓ ≤ n-k, where n is the code length, k is the code dimension. By estimating the number of coverable stopping sets, we obtain upper bounds on the ℓth stopping redundancy, 1 ≤ ℓ ≤ n-k. The bounds are derived for both specific codes and code ensembles. In the range 1 ≤ ℓ ≤ d-1, for specific codes, the new bounds improve on the results in the literature. Numerical calculations are also presented.

A new decoding algorithm for LDPC codes on the AWGN channel is proposed. The algorithm is based on the idea of using redundant parity checks and additional variable nodes. The new key element in the proposed algorithm is the use of the orthogonal subsets of parity checks for computing soft decisions for different variable nodes. This allows for significant improvement in the decoding error performance of the algorithm compared to the known counterparts. Furthermore, new bounds on the error performance of the BP decoding applied to the parity-check matrices with redundant parity-checks are obtained.

We propose a new model of asynchronous batch codes that allow for parallel recovery of information symbols from a coded database in an asynchronous manner, i.e. when different queries take different time to process. Then, we show that the graph-based batch codes studied by Rawat et al. are asynchronous. Further, we demonstrate that hypergraphs of Berge girth at least 4, respectively at least 3, yield graph-based asynchronous batch codes, respectively private information retrieval (PIR) codes. We prove the hypergraph-theoretic proposition that the maximum number of hyperedges in a hypergraph of a fixed Berge girth equals the quantity in a certain generalization of the hypergraph-theoretic (6,3)-problem, first posed by Brown, Erdos and Sós. We then apply the constructions and bounds by Erdos, Frankl and Rödl about this generalization of the (6,3)problem, known as the (3r-3,r)-problem, to obtain batch code constructions and bounds on the redundancy of the graph-based asynchronous batch and PIR codes. Finally, we show that the optimal redundancy ρ(k) of graph-based asynchronous batch codes of dimension k with the query size t = 3 is 2√k. Moreover, for a general fixed value of t ≥ 4, ρ(k) = O (k1/(2-ε)) for any small ε > 0. For a general value of t ≥ 4, limk→∞ρ(k)√k = ∞.

The Gallager ensembles of binary regular LDPC codes and binary images of nonbinary regular LDPC codes are studied. Recurrent procedure for computing average spectra for these two ensembles is presented. By using the existing bounding techniques, estimates on the error probability of the maximum-likelihood (ML) decoding over an AWGN channel with BPSK signaling for short codes from different ensembles of LDPC codes are obtained. The numerical results show performance of the ML decoding for different code ensembles. Conclusions drawn based on the average code spectra are then verified by near-ML decoding simulations for both randomly selected and the best known short codes. The asymptotic ML decoding thresholds for AWGN and BSC channels are calculated. As expected, codes with the ML decoding performance superior to that of the average code in the ensemble, are easy to find. However, comparison of the the presented results with simulation results for belief propagation (BP) decoding shows that the ML decoding performance should not be used as a target for searching for good iteratively decodable codes.

The exact values of finite length average weight distributions for both binary ensembles and binary images of nonbinary ensembles of regular LDPC codes are computed. The exact average stopping set size distribution for the binary ensemble is also obtained. The computed spectra are applied in order to bound from above the average stopping redundancy of the ensemble of binary regular LDPC codes. The asymptotic typical normalized minimum distances for the binary image of the ensemble of nonbinary regular LDPC codes and the typical minimum stopping distances for the binary regular LDPC codes are also presented.

A novel method for decoding of low-density parity-check codes on the AWGN channel is presented. In the proposed method, first, a standard belief-propagation decoder is applied, then a certain number of positions is erased using a combination of a reliability criterion and a set of masks. A list erasure decoder is then applied to the resulting word. The performance of the proposed method is analyzed mathematically and demonstrated by simulations.

Minimum Pearson Distance (MPD) detection offers resilience against unknown channel gain and varying offset. MPD detection is used in conjunction with a set, S, of 2-ary codewords having specific properties. In this work, we study the properties of the codewords of S, compute the size of S, and derive its redundancy for asymptotically large values of the codeword length n. The redundancy of S is approximately 3/2 log2n + α; where α = log2√π/24 = -1.467.. for n odd and α = -0.467.. for n even.

Batch codes are of potential use in load balancing, private information retrieval and distributed storage. In this article, we present new bounds on the parameters of linear batch codes with restricted query size. The derivation techniques are partly based on ideas in the literature for codes with locality, combined with additional ideas.

This paper proposes a new technique of spatially-coupled low-density parity-check (SC-LDPC) code-based soft information relaying scheme for a two-way relay system. We introduce an optimized SC-LDPC codes in relay channels. A more precise model is proposed to characterize the soft noise on the soft symbols, using a pre-calculated look-up table at the destination. This requires less signalling overhead compared to existing soft noise modelling techniques. We also introduce a variance correction factor to provide a rectification to the equivalent total noise variance at the destination. Finally, we modify the LLR former at the destination which is tailored to the proposed soft information relaying technique. Simulation results demonstrate that the proposed relay protocol yields an improved BER performance compared to competitive schemes proposed in the literature.

We consider the transmission and storage of data that use coded binary symbols over a channel, where a Pearson distance-based detector is used for achieving resilience against additive noise, unknown channel gain, and varying offset. We study minimum Pearson distance (MPD) detection in conjunction with a set, S, of codewords satisfying a center-of-mass constraint. We investigate the properties of the codewords in S, compute the size of S, and derive its redundancy for asymptotically large values of the codeword length n. The redundancy of S is approximately (3/2) log2n + α, where α = log2(π/24)1/2= -1.467.. for n odd and α = -0.467.. for n even. We describe a simple encoding algorithm whose redundancy equals 2 log2n+ o(logn). We also compute the word error rate of the MPD detector when the channel is corrupted with additive Gaussian noise.

New bounds on the cardinality of permutation codes equipped with the Ulam distance are presented. First, an integer-programming upper bound is derived, which improves on the Singleton-type upper bound in the literature for some lengths. Second, several probabilistic lower bounds are developed, which improve on the known lower bounds for large minimum distances. The results of a computer search for permutation codes are also presented.

The l-th stopping redundancy ρι(C) of the binary [n, k, d] code C, 1 ≤ l ≤ d, is defined as the minimum number of rows in the parity-check matrix of C, such that the smallest stopping set is of size at least l. The stopping redundancy ρ(C) is defined as ρd(C). In this work, we improve on the probabilistic analysis of stopping redundancy, proposed by Han, Siegel and Vardy, which yields the best bounds known today. In our approach, we judiciously select the first few rows in the parity-check matrix, and then continue with the probabilistic method. By using similar techniques, we improve also on the best known bounds on ρι(C), for 1 ≤ l ≤ d. Our approach is compared to the existing methods by numerical computations.

Assume that two users possess two different subspaces of an ambient linear space. We show that the problem of synchronization of such vector spaces can be easily solved by an efficient algorithm. By building on this observation, we propose an algorithm for synchronization of two collections of binary files of length n each, stored in the cloud in a distributed manner. By further employing techniques akin to network coding, we propose a more efficient file synchronization algorithm that has communication complexity O(d · n) bits and computational complexity O(k2· n) operations, where k is the total number of files and d is the number of files that differ. The algorithm successfully reconciles two sets of files in 3 communication rounds with high probability.

In this article, we study properties and algorithms for constructing sets of constant weight codewords with bipolar symbols, where the sum of the symbols is a constant q, q\neq 0. We show various code constructions that extend Knuth's balancing vector scheme, q=0, to the case where q>0. We compute the redundancy of the new coding methods. Finally, we generalize the proposed methods to encoding of imbalanced arrays in two or more dimensions.

The min-rank of a digraph was shown to represent the length of an optimal scalar linear solution of the corresponding instance of the Index Coding with Side Information (ICSI) problem. In this paper, the graphs and digraphs of near-extreme min-ranks are studied. Those graphs and digraphs correspond to the ICSI instances having near-extreme transmission rates when using optimal scalar linear index codes. In particular, it is shown that the decision problem whether a digraph has min-rank two is NP-complete. By contrast, the same question for graphs can be answered in polynomial time. In addition, a circuit-packing bound is revisited, and several families of digraphs, optimal with respect to this bound, whose min-ranks can be found in polynomial time, are presented.

A problem of index coding with side information was first considered by Birk and Kol in 1998. In this study, a generalization of index coding scheme, where transmitted symbols are subject to errors, is studied. Error-correcting methods for such a scheme, and their parameters, are investigated. In particular, the following question is discussed: given the side information hypergraph of index coding scheme and the maximal number of erroneous symbols δ , what is the shortest length of a linear index code, such that every receiver is able to recover the required information? This question turns out to be a generalization of the problem of finding a shortest length error-correcting code with a prescribed error-correcting capability in the classical coding theory. The Singleton bound and two other bounds, referred to as the α-bound and the κ -bound, for the optimal length of a linear error-correcting index code (ECIC) are established. For large alphabets, a construction based on concatenation of an optimal index code with a maximum distance separable classical code is shown to attain the Singleton bound. For smaller alphabets, however, this construction may not be optimal. A random construction is also analyzed. It yields another inexplicit bound on the length of an optimal linear ECIC. Further, the problem of error-correcting decoding by a linear ECIC is studied. It is shown that in order to decode correctly the desired symbol, the decoder is required to find one of the vectors, belonging to an affine space containing the actual error vector. The syndrome decoding is shown to produce the correct output if the weight of the error pattern is less or equal to the error-correcting capability of the corresponding ECIC. Finally, the notion of static ECIC, which is suitable for use with a family of instances of an index coding problem, is introduced. Several bounds on the length of static ECICs are derived, and constructions for static ECICs are discussed. Connections of these codes to weakly resilient Boolean functions are established.

We consider rank modulation codes for flash memories that allow for handling arbitrary charge-drop errors. Unlike classical rank modulation codes used for correcting errors that manifest themselves as swaps of two adjacently ranked elements, the proposed translocation rank codes account for more general forms of errors that arise in storage systems. Translocations represent a natural extension of the notion of adjacent transpositions and as such may be analyzed using related concepts in combinatorics and rank modulation coding. Our results include derivation of the asymptotic capacity of translocation rank codes, construction techniques for asymptotically good codes, as well as simple decoding methods for one class of constructed codes. As part of our exposition, we also highlight the close connections between the new code family and permutations with short common subsequences, deletion and insertion error-correcting codes for permutations, and permutation codes in the Hamming distance.

We describe a novel extension of subspace codes for noncoherent networks, suitable for use when the network is viewed as a communication system that introduces both dimension and symbol errors. We show that when symbol erasures occur in a significantly large number of different basis vectors transmitted through the network and when the min-cut of the network is much smaller than the length of the transmitted codewords, the new family of codes outperforms their subspace code counterparts. For the proposed coding scheme, termed hybrid network coding, we derive two upper bounds on the size of the codes. These bounds represent a variation of the Singleton and of the sphere-packing bound. We show that a simple concatenated scheme that consists of subspace codes and Reed-Solomon codes is asymptotically optimal with respect to the Singleton bound. Finally, we describe two efficient decoding algorithms for concatenated subspace codes that in certain cases have smaller complexity than their subspace decoder counterparts.

The min-rank of a digraph was shown by Bar-Yossef et al. (2006) to represent the length of an optimal scalar linear solution of the corresponding instance of the Index Coding with Side Information (ICSI) problem. In this work, the graphs and digraphs of near-extreme min-ranks are characterized. Those graphs and digraphs correspond to the ICSI instances having near-extreme transmission rates when using optimal scalar linear index codes. It is also shown that the decision problem of whether a digraph has min-rank two is NP-complete. By contrast, the same question for graphs can be answered in polynomial time.

We consider rank modulation codes for flash memories that allow for handling arbitrary charge drop errors. Unlike classical rank modulation codes used for correcting errors that manifest themselves as swaps of two adjacently ranked elements, the proposed translocation codes account for more general forms of errors that arise in storage systems. Translocations represent a natural extension of the notion of adjacent transpositions and as such may be analyzed using related concepts in combinatorics and rank modulation coding. Our results include deriving the asymptotic capacity of translocation rank codes, construction techniques for asymptotically good codes and a simple decoding algorithm.

We consider the problem of efficient and lossless representation of a multiset of m words drawn with repetition from a set of size 2n. One expects that encoding the (unordered) multiset should lead to significant savings in rate as compared to encoding an (ordered) sequence with the same words, since information about the order of words in the sequence corresponds to a permutation. We propose and analyze a practical multiset encoder/decoder based on the trie data structure. The act of encoding requires O(m(n + log m)) operations, and decoding requires O(mn) operations. Of particular interest is the case where cardinality of the multiset scales as m = 1/c2nfor some c >; 1, as n → ∞. Under this scaling, and when the words in the multiset are drawn independently and uniformly, we show that the proposed encoding leads to an arbitrary improvement in rate over encoding an ordered sequence with the same words. Moreover, the expected length of the proposed codes in this setting is asymptotically within a constant factor of 5/3 of the lower bound.

Security aspects of the index coding with side information (ICSI) problem are investigated. Building on the results of Bar-Yossef (2006), the properties of linear index codes are further explored. The notion of weak security, considered by Bhattad and Narayanan (2005) in the context of network coding, is generalized to block security. It is shown that the linear index code based on a matrixL, whose column space codeC(L) has lengthn, minimum distanced, and dual distanced⊥, is (d-1-t) -block secure (and hence also weakly secure) if the adversary knows in advancet≤d-2 messages, and is completely insecure if the adversary knows in advance more thann-d⊥messages. Strong security is examined under the conditions that the adversary: 1) possessestmessages in advance; 2) eavesdrops at most μ transmissions; 3) corrupts at most δ transmissions. We prove that for sufficiently largeq, an optimal linear index code which is strongly secure against such an adversary has length κq+μ+2δ . Here, κqis a generalization of the min-rank over Fqof the side information graph for the ICSI problem in its original formulation in the work of Bar-Yossef et al.

For a binary linear code, the pseudocodeword redundancy with respect to the additive white Gaussian noise channel, the binary symmetric channel, or the max-fractional weight is defined to be the smallest number of rows in a parity-check matrix such that the corresponding minimum pseudoweight is equal to the minimum Hamming distance of the code. It is shown that most codes do not have a finite pseudocodeword redundancy. Also, upper bounds on the pseudocodeword redundancy for some families of codes, including codes based on designs, are provided. The pseudocodeword redundancies for all codes of small length (at most 9) are computed. Furthermore, comprehensive results are provided on the cases of cyclic codes of length at most 250 for which the eigenvalue bound of Vontobel and Koetter is sharp.

Security aspects of the Index Coding with Side Information (ICSI) problem are investigated. Building on the results of Bar-Yossef et al. (2006), the properties of linear index codes are further explored. The notion of weak security, considered by Bhattad and Narayanan (2005) in the context of network coding, is generalized to block security. It is shown that the linear index code based on a matrix L, whose column space code C(L) has length n, minimum distance d and dual distance d⊥, is (d-1-t)-block secure (and hence also weakly secure) if the adversary knows in advance t ≤ d - 2 messages, and is completely insecure if the adversary knows in advance more than n-d⊥messages. Strong security is examined under the conditions that the adversary: (i) possesses t messages in advance; (ii) eavesdrops at most μ transmissions; (iii) corrupts at most δ transmissions. We prove that for sufficiently large q, an optimal linear index code, which is strongly secure against such an adversary, has length κq+μ+2δ. Here κqis a generalization of the min-rank over Fqof the side information graph for the ICSI problem in its original formulation in the work of Bar-Yossef et al.

A problem of index coding with side information was first considered by Y. Birk and T. Kol (IEEE INFOCOM, 1998). In the present work, a generalization of index coding scheme, where transmitted symbols are subject to errors, is studied. Error-correcting methods for such a scheme, and their parameters, are investigated. In particular, the following question is discussed: given the side information hypergraph of index coding scheme and the maximal number of erroneous symbols δ, what is the shortest length of a linear index code, such that every receiver is able to recover the required information? This question turns out to be a generalization of the problem of finding a shortest-length error-correcting code with a prescribed error-correcting capability in the classical coding theory. The Singleton bound and two other bounds, referred to as the α-bound and the κ-bound, for the optimal length of a linear error-correcting index code (ECIC) are established. For large alphabets, a construction based on concatenation of an optimal index code with an MDS classical code, is shown to attain the Singleton bound. For smaller alphabets, however, this construction may not be optimal. A random construction is also analyzed. It yields another inexplicit bound on the length of an optimal linear ECIC. Finally, the decoding of linear ECIC's is discussed. The syndrome decoding is shown to output the exact message if the weight of the error vector is less or equal to the error-correcting capability of the corresponding ECIC.

In this article, we study properties and algorithms for constructing sets of `constant weight' codewords with bipolar symbols, where the sum of the symbols is a constant q, q ≠ 0. We show various code constructions that extend Knuth's balancing vector scheme, q = 0, to the case where q >; 0. We compute the redundancy of the new coding methods.

A linear-programming decoder for nonbinary expander codes is presented. It is shown that the proposed decoder has the nearest-neighbor certificate properties. It is also shown that this decoder corrects any pattern of errors of a relative weight up to approximately 1/4δAδB(where δAand δBare the relative minimum distances of the constituent codes).

We define the AWGNC, BSC, and max-fractional pseudocodeword redundancy p(C) of a code C as the smallest number of rows in a parity-check matrix such that the corresponding minimum pseudoweight is equal to the minimum Hamming distance of C. We show that most codes do not have a finite p(C). We also provide bounds on the pseudocodeword redundancy for some families of codes, including codes based on designs.

Linear-programming pseudocodewords play a pivotal role in our understanding of the linear-programming decoding algorithms. These pseudocodewords are known to be equivalent to the graph-cover pseudocodewords. The latter pseudocodewords, when viewed as points in the multidimensional Euclidean space, lie inside a fundamental cone. This fundamental cone depends on the choice of a parity-check matrix of a code, rather than on the choice of the code itself. The cone does not depend on the channel, over which the code is employed. The knowledge of the boundaries of the fundamental cone could help in studying various properties of the pseudocodewords, such as their minimum pseudoweight, pseudoredundancy of the codes, etc. For the binary codes, the full characterization of the fundamental cone was derived by Koetter et al. However, if the underlying alphabet is large, such characterization becomes more involved. In this work, a characterization of the fundamental cone for codes over F3is discussed.

A modification of Ko¿tter-Kschischang codes for random networks is presented (these codes were also studied by Wang in the context of authentication problems). The new codes have higher information rate, while maintaining the same error-correcting capabilities. An efficient error-correcting algorithm is proposed for these codes.

A linear-programming (LP) decoder for nonbinary expander codes is presented. It is shown that the proposed decoder has the maximum-likelihood certificate properties. It is also shown that this decoder corrects any pattern of errors of a relative weight up to approximately 1/4deltaAdeltaB(where deltaAand deltaBare the relative minimum distances of the constituent codes).

A framework for linear-programming (LP) decoding of nonbinary linear codes over rings is developed. This framework facilitates LP-based reception for coded modulation systems which use direct modulation mapping of coded symbols. It is proved that the resulting LP decoder has the ldquomaximum-likelihood (ML) certificaterdquo property. It is also shown that the decoder output is the lowest cost pseudocodeword. Equivalence between pseudocodewords of the linear program and pseudocodewords of graph covers is proved. It is also proved that if the modulator-channel combination satisfies a particular symmetry condition, the codeword error rate performance is independent of the transmitted codeword. Two alternative polytopes for use with LP decoding are studied, and it is shown that for many classes of codes these polytopes yield a complexity advantage for decoding. These polytope representations lead to polynomial-time decoders for a wide variety of classical nonbinary linear codes. LP decoding performance is illustrated for ternary Golay code with ternary phase-shift keying (PSK) modulation over additive white Gaussian noise (AWGN), and in this case it is shown that the performance of the LP decoder is comparable to codeword-error-rate-optimum hard-decision-based decoding. LP decoding is also simulated for medium-length ternary and quaternary low-density parity-check (LDPC) codes with corresponding PSK modulations over AWGN.

In previous work, we demonstrated how decoding of a non-binary linear code could be formulated as a linear-programming problem. In this paper, we study different polytopes for use with linear-programming decoding, and show that for many classes of codes these polytopes yield a complexity advantage for decoding. These representations lead to polynomial-time decoders for a wide variety of classical non-binary linear codes.

The decoding error probability of codes is studied as a function of their block length. It is shown that the existence of codes with a polynomially small decoding error probability implies the existence of codes with an exponentially small decoding error probability. Specifically, it is assumed that there exists a family of codes of length N and rate R=(1-epsiv)C (C is a capacity of a binary-symmetric channel), whose decoding probability decreases inverse polynomially in N. It is shown that if the decoding probability decreases sufficiently fast, but still only inverse polynomially fast in N, then there exists another such family of codes whose decoding error probability decreases exponentially fast in N. Moreover, if the decoding time complexity of the assumed family of codes is polynomial in N and 1/epsiv, then the decoding time complexity of the presented family is linear in N and polynomial in 1/epsiv. These codes are compared to the recently presented codes of Barg and Zemor, "Error Exponents of Expander Codes", IEEE Transactions on Information Theory, 2002, and "Concatenated Codes: Serial and Parallel", IEEE Transactions on Information Theory, 2005. It is shown that the latter families cannot be tuned to have exponentially decaying (in N) error probability, and at the same time to have decoding time complexity linear in N and polynomial in 1/epsiv

A construction of expander codes is presented with the following three properties: i) the codes lie close to the Singleton bound, ii) they can be encoded in time complexity that is linear in their code length, and iii) they have a linear-time bounded-distance decoder. By using a version of the decoder that corrects also erasures, the codes can replace maximum-distance separable (MDS) outer codes in concatenated constructions, thus resulting in linear-time encodable and decodable codes that approach the Zyablov bound or the capacity of memoryless channels. The presented construction improves on an earlier result by Guruswami and Indyk in that any rate and relative minimum distance that lies below the Singleton bound is attainable for a significantly smaller alphabet size

The concatenation of nearly-MDS expander codes of Roth and Skachek, "On Nearly-MDS Expander Codes," Proc. IEEE ISIT'04, with 'typical' LDPC codes is investigated. It is shown that for the rates R = (1 - epsi)C (C is the capacity of the binary symmetric channel (BSC)), under certain condition on the parameters of LDPC codes, these concatenated codes have decoding time linear in their length and polynomial in 1/epsi, and the decoding error probability decays exponentially. These codes are compared to the recently presented codes of Barg and Zemor, "Error Exponents of Expander Codes," IEEE Trans. Inform. Theory, 2002, and "Concatenated Codes: Serial and Parallel," IEEE Trans. Inform. Theory, 2005. It is shown that the latter families can not be tuned to have all the aforementioned properties

A construction of expander codes is presented with the following three properties: (i) the codes lie close to the Singleton bound, (ii) they can be encoded in time complexity that is linear in their code length, and (iii) they have a linear-time bounded-distance decoder. By using a version of the decoder that corrects also erasures, the codes can replace MDS outer codes in concatenated constructions, thus resulting in linear-time encodable and decodable codes that approach the Zyablov bound or the capacity of memoryless channels. The presented construction improves on an earlier result by Guruswami and Indyk in that any rate and relative minimum distance that lies below the Singleton bound is attainable for a significantly smaller alphabet size.

Recently, G. Zemor (see IEEE Trans. Inf. Theory, vol.47, p.835-7, 2001) proposed an improvement on the Sipser-Spielman analysis of expander codes (Sipser, M. and Spielman, D.A., IEEE Trans. Inf. Theory, vol.42 , p.1710-22, 1996) and presented a linear-time iterative decoder that can correct a number of errors up to approximately 1/4 the known lower bound on the minimum distance of the code. We propose an improvement on Zemor's decoder for F=GF(2), with the number of correctable errors becoming close to half the lower bound on the minimum distance. The improvement is obtained by inserting into the decoding algorithm features akin to generalized minimum distance decoding of concatenated codes.

An efficient algorithm is presented for encoding unconstrained information sequences into a third-order spectral-null code of length n and redundancy 9log/sub 2/ n+O(log log n). The encoding can be implemented using O(n) integer additions and O(nlog n) counter increments.