Showing 1–39 of 39 results for author: Skachek, V

On some batch code properties of the simplex code

Authors: Henk D. L. Hollmann, Karan Khathuria, Ago-Erik Riet, Vitaly Skachek

Abstract: The binary $k$-dimensional simplex code is known to be a $2^{k-1}$-batch code and is conjectured to be a $2^{k-1}$-functional batch code. Here, we offer a simple, constructive proof of a result that is "in between" these two properties. Our approach is to relate these properties to certain (old and new) additive problems in finite abelian groups. We also formulate a conjecture for finite abelian g… ▽ More The binary $k$-dimensional simplex code is known to be a $2^{k-1}$-batch code and is conjectured to be a $2^{k-1}$-functional batch code. Here, we offer a simple, constructive proof of a result that is "in between" these two properties. Our approach is to relate these properties to certain (old and new) additive problems in finite abelian groups. We also formulate a conjecture for finite abelian groups that generalizes the above-mentioned conjecture. △ Less

Submitted 22 January, 2023; v1 submitted 14 October, 2021; originally announced October 2021.

NB QC-LDPC Coded QAM Signals with Optimized Mapping: Bounds and Simulation Results

Authors: Irina E. Bocharova, Boris D. Kudryashov, Evgenii P. Ovsyannikov, Vitaly Skachek

Abstract: The goal of the paper is to study 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 extensions of the Galois field GF$(2^m)$ with $m \le 6$ used with QAM signaling. Performance of NB QC LDPC coded transmission strongly depends on mapping of nonbinary symbols to signal… ▽ More The goal of the paper is to study 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 extensions of the Galois field GF$(2^m)$ with $m \le 6$ used with QAM signaling. Performance of NB QC LDPC coded transmission strongly depends on 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 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. △ Less

Submitted 23 May, 2022; v1 submitted 19 August, 2021; originally announced August 2021.

Comments: arXiv admin note: text overlap with arXiv:2006.12147

Failure Probability Analysis for Partial Extraction from Invertible Bloom Filters

Authors: Ivo Kubjas, Vitaly Skachek

Abstract: 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 ne… ▽ More 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. An upper bound on the number of rounds in an iterative set reconciliation protocol is presented. The numerical results are derived analytically, and confirmed by the computer simulations. △ Less

Submitted 3 August, 2020; originally announced August 2020.

Optimization of NB QC-LDPC Block Codes and Their Performance Analysis

Authors: Irina E. Bocharova, Boris D. Kudryashov, Evgenii P. Ovsyannikov, Vitaly Skachek, Tähvend Uustalu

Abstract: We propose an approach for optimizing nonbinary (NB) quasi-cyclic (QC) LDPC codes. This approach combines constructing of base parity-check matrices by simulated annealing and labeling the obtained base matrices aimed at maximizing the so-called generalized girth of the NB LDPC code Tanner graph. Tightened random coding bounds based on the average binary spectra for ensembles of "almost regular" N… ▽ More We propose an approach for optimizing nonbinary (NB) quasi-cyclic (QC) LDPC codes. This approach combines constructing of base parity-check matrices by simulated annealing and labeling the obtained base matrices aimed at maximizing the so-called generalized girth of the NB LDPC code Tanner graph. Tightened random coding bounds based on the average binary spectra for ensembles of "almost regular" NB LDPC codes of finite lengths over extensions of the binary Galois field are derived. The simulated FER performance of the sum-product BP decoding of "almost regular" NB QC-LDPC block codes are presented and compared with the derived finite-length random coding bounds as well as with the same performance of the optimized binary QC-LDPC block code in the 5G standard. In the waterfall region our finite-length bounds on the error probability of ML decoding are about 0.1--0.2 dB away from the simulated FER performance of BP decoding. △ Less

Submitted 22 October, 2020; v1 submitted 22 June, 2020; originally announced June 2020.

Comments: 26 pages

Proceedings of the 11th Asia-Europe Workshop on Concepts in Information Theory

Authors: A. J. Han Vinck, Kees A. Schouhamer Immink, Tadashi Wadayama, Van Khu Vu, Akiko Manada, Kui Cai, Shunsuke Horii, Yoshiki Abe, Mitsugu Iwamoto, Kazuo Ohta, Xingwei Zhong, Zhen Mei, Renfei Bu, J. H. Weber, Vitaly Skachek, Hiroyoshi Morita, N. Hovhannisyan, Hiroshi Kamabe, Shan Lu, Hirosuke Yamamoto, Kengo Hasimoto, O. Ytrehus, Shigeaki Kuzuoaka, Mikihiko Nishiara, Han Mao Kiah , et al. (2 additional authors not shown)

Abstract: This year, 2019 we celebrate 30 years of our friendship between Asian and European scientists at the AEW11 in Rotterdam, the Netherlands. Many of the 1989 participants are also present at the 2019 event. This year we have many participants from different parts of Asia and Europe. It shows the importance of this event. It is a good tradition to pay a tribute to a special lecturer in our community.… ▽ More This year, 2019 we celebrate 30 years of our friendship between Asian and European scientists at the AEW11 in Rotterdam, the Netherlands. Many of the 1989 participants are also present at the 2019 event. This year we have many participants from different parts of Asia and Europe. It shows the importance of this event. It is a good tradition to pay a tribute to a special lecturer in our community. This year we selected Hiroyoshi Morita, who is a well known information theorist with many original contributions. △ Less

Submitted 26 June, 2019; originally announced July 2019.

Batch Codes for Asynchronous Recovery of Data

Authors: Ago-Erik Riet, Vitaly Skachek, Eldho K. Thomas

Abstract: 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 queries arrive at random times and they take varying time to process. We show that the graph-based batch codes studied by et al. are asynchronous. Further, we demonstrate that hypergraphs of Berge girth larger or equal to 4, respectiv… ▽ More 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 queries arrive at random times and they take varying time to process. We show that the graph-based batch codes studied by et 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 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, 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 $ρ(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$, $ρ(k) = O\left({k}^{1/(2-ε)}\right)$ for any small $ε>0$. △ Less

Submitted 5 September, 2020; v1 submitted 2 June, 2018; originally announced June 2018.

Comments: 18 pages

MSC Class: 68P30 (primary) 05D99; 05B40 (secondary) ACM Class: E.4; G.2

Stopping Redundancy Hierarchy Beyond the Minimum Distance

Authors: Yauhen Yakimenka, Vitaly Skachek, Irina E. Bocharova, Boris D. Kudryashov

Abstract: Stopping sets play a crucial role in failure events of iterative decoders over a binary erasure channel (BEC). The $\ell$-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 $\ell$. In this work, a notion of coverable stopping sets is defined. In order to achieve maximum-likelihood performance under iterative deco… ▽ More Stopping sets play a crucial role in failure events of iterative decoders over a binary erasure channel (BEC). The $\ell$-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 $\ell$. In this work, 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 $\ell$, for $1 \le \ell \le 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 $\ell$-th stopping redundancy, $1 \le \ell \le n-k$. The bounds are derived for both specific codes and code ensembles. In the range $1 \le \ell \le d-1$, for specific codes, the new bounds improve on the results in the literature. Numerical calculations are also presented. △ Less

Submitted 29 September, 2018; v1 submitted 18 April, 2018; originally announced April 2018.

Comments: Accepted for publication in IEEE Transactions on Information Theory

MSC Class: 94B65

ML and Near-ML Decoding of LDPC Codes Over the BEC: Bounds and Decoding Algorithms

Authors: Irina E. Bocharova, Boris D. Kudryashov, Vitaly Skachek, Eirik Rosnes, Øyvind Ytrehus

Abstract: 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. The theoretical average spectrum of the Gallager ensemble is computed by using a recurrent procedure and compared to the empirically found average spectrum for the same ensemble as well as to the empirical average spectrum o… ▽ More 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. The theoretical average spectrum of the Gallager ensemble is computed by using a recurrent procedure and compared to the empirically found average spectrum for the same ensemble as well as to the empirical average spectrum of the Richardson-Urbanke ensemble and spectra of selected codes from both ensembles. Distance properties of the random codes from the Gallager ensemble are discussed. A tightened union-type upper bound on the ML decoding error probability based on the precise coefficients of the average spectrum is presented. A new upper bound on the ML decoding performance of LDPC codes from the Gallager ensemble based on computing the rank of submatrices of the code parity-check matrix is derived. A new low-complexity near-ML decoding algorithm for quasi-cyclic LDPC codes is proposed and simulated. Its performance is compared to the upper bounds on the ML decoding performance. △ Less

Submitted 20 November, 2018; v1 submitted 5 September, 2017; originally announced September 2017.

Comments: To appear in IEEE Transactions on Communications

Distance Properties of Short LDPC Codes and their Impact on the BP, ML and Near-ML Decoding Performance

Authors: Irina E. Bocharova, Boris D. Kudryashov, Vitaly Skachek, Yauhen Yakimenka

Abstract: Parameters of LDPC codes, such as minimum distance, stopping distance, stopping redundancy, girth of the Tanner graph, and their influence on the frame error rate performance of the BP, ML and near-ML decoding over a BEC and an AWGN channel are studied. Both random and structured LDPC codes are considered. In particular, the BP decoding is applied to the code parity-check matrices with an increasi… ▽ More Parameters of LDPC codes, such as minimum distance, stopping distance, stopping redundancy, girth of the Tanner graph, and their influence on the frame error rate performance of the BP, ML and near-ML decoding over a BEC and an AWGN channel are studied. Both random and structured LDPC codes are considered. In particular, the BP decoding is applied to the code parity-check matrices with an increasing number of redundant rows, and the convergence of the performance to that of the ML decoding is analyzed. A comparison of the simulated BP, ML, and near-ML performance with the improved theoretical bounds on the error probability based on the exact weight spectrum coefficients and the exact stopping size spectrum coefficients is presented. It is observed that decoding performance very close to the ML decoding performance can be achieved with a relatively small number of redundant rows for some codes, for both the BEC and the AWGN channels. △ Less

Submitted 4 July, 2017; originally announced July 2017.

BP-LED decoding algorithm for LDPC codes over AWGN channels

Authors: Irina E. Bocharova, Boris D. Kudryashov, Vitaly Skachek, Yauhen Yakimenka

Abstract: A new method for low-complexity near-maximum-likelihood (ML) decoding of low-density parity-check (LDPC) codes over the additive white Gaussian noise channel is presented. 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 ve… ▽ More A new method for low-complexity near-maximum-likelihood (ML) decoding of low-density parity-check (LDPC) codes over the additive white Gaussian noise channel is presented. 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 regular and irregular quasi-cyclic LDPC codes of short and moderate lengths are studied by simulations and their performance is compared with the 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 with the BP decoding 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 LDPC code over the extension of the binary Galois field. The obtained simulation results are compared to the upper bound on the ensemble-average performance of the binary image of regular nonbinary LDPC codes. △ Less

Submitted 26 May, 2017; originally announced May 2017.

Comments: Submitted to IEEE Transactions on Information Theory

Explicit Constructions and Bounds for Batch Codes with Restricted Size of Reconstruction Sets

Authors: Eldho K. Thomas, Vitaly Skachek

Abstract: Linear batch codes and codes for private information retrieval (PIR) with a query size $t$ and a restricted size $r$ of the reconstruction sets are studied. New bounds on the parameters of such codes are derived for small values of $t$ or of $r$ by providing corresponding constructions. By building on the ideas of Cadambe and Mazumdar, a new bound in a recursive form is derived for batch codes and… ▽ More Linear batch codes and codes for private information retrieval (PIR) with a query size $t$ and a restricted size $r$ of the reconstruction sets are studied. New bounds on the parameters of such codes are derived for small values of $t$ or of $r$ by providing corresponding constructions. By building on the ideas of Cadambe and Mazumdar, a new bound in a recursive form is derived for batch codes and PIR codes. △ Less

Submitted 4 July, 2017; v1 submitted 26 January, 2017; originally announced January 2017.

Comments: To appear in 5ICMCTA

Two-Party Function Computation on the Reconciled Data

Authors: Ivo Kubjas, Vitaly Skachek

Abstract: In this paper, we initiate a study of a new problem termed function computation on the reconciled data, which generalizes a set reconciliation problem in the literature. Assume a distributed data storage system with two users $A$ and $B$. The users possess a collection of binary vectors $S_{A}$ and $S_{B}$, respectively. They are interested in computing a function $φ$ of the reconciled data… ▽ More In this paper, we initiate a study of a new problem termed function computation on the reconciled data, which generalizes a set reconciliation problem in the literature. Assume a distributed data storage system with two users $A$ and $B$. The users possess a collection of binary vectors $S_{A}$ and $S_{B}$, respectively. They are interested in computing a function $φ$ of the reconciled data $S_{A} \cup S_{B}$. It is shown that any deterministic protocol, which computes a sum and a product of reconciled sets of binary vectors represented as nonnegative integers, has to communicate at least $2^n + n - 1$ and $2^n + n - 2$ bits in the worst-case scenario, respectively, where $n$ is the length of the binary vectors. Connections to other problems in computer science, such as set disjointness and finding the intersection, are established, yielding a variety of additional upper and lower bounds on the communication complexity. A protocol for computation of a sum function, which is based on use of a family of hash functions, is presented, and its characteristics are analyzed. △ Less

Submitted 10 July, 2017; v1 submitted 25 January, 2017; originally announced January 2017.

Batch and PIR Codes and Their Connections to Locally Repairable Codes

Authors: Vitaly Skachek

Abstract: In this survey, two related families of codes are discussed: batch codes and codes for private information retrieval. These two families can be viewed as natural generalizations of locally repairable codes, which were extensively studied in the context of coding for fault tolerance in distributed data storage systems. Bounds on the parameters of the codes, as well as basic constructions, are prese… ▽ More In this survey, two related families of codes are discussed: batch codes and codes for private information retrieval. These two families can be viewed as natural generalizations of locally repairable codes, which were extensively studied in the context of coding for fault tolerance in distributed data storage systems. Bounds on the parameters of the codes, as well as basic constructions, are presented. Connections between different code families are discussed. △ Less

Submitted 5 September, 2017; v1 submitted 29 November, 2016; originally announced November 2016.

Comments: Survey

CONDENSE: A Reconfigurable Knowledge Acquisition Architecture for Future 5G IoT

Authors: Dejan Vukobratovic, Dusan Jakovetic, Vitaly Skachek, Dragana Bajovic, Dino Sejdinovic, Gunes Karabulut Kurt, Camilla Hollanti, Ingo Fischer

Abstract: In forthcoming years, the Internet of Things (IoT) will connect billions of smart devices generating and uploading a deluge of data to the cloud. If successfully extracted, the knowledge buried in the data can significantly improve the quality of life and foster economic growth. However, a critical bottleneck for realising the efficient IoT is the pressure it puts on the existing communication inf… ▽ More In forthcoming years, the Internet of Things (IoT) will connect billions of smart devices generating and uploading a deluge of data to the cloud. If successfully extracted, the knowledge buried in the data can significantly improve the quality of life and foster economic growth. However, a critical bottleneck for realising the efficient IoT is the pressure it puts on the existing communication infrastructures, requiring transfer of enormous data volumes. Aiming at addressing this problem, we propose a novel architecture dubbed Condense, which integrates the IoT-communication infrastructure into data analysis. This is achieved via the generic concept of network function computation: Instead of merely transferring data from the IoT sources to the cloud, the communication infrastructure should actively participate in the data analysis by carefully designed en-route processing. We define the Condense architecture, its basic layers, and the interactions among its constituent modules. Further, from the implementation side, we describe how Condense can be integrated into the 3rd Generation Partnership Project (3GPP) Machine Type Communications (MTC) architecture, as well as the prospects of making it a practically viable technology in a short time frame, relying on Network Function Virtualization (NFV) and Software Defined Networking (SDN). Finally, from the theoretical side, we survey the relevant literature on computing "atomic" functions in both analog and digital domains, as well as on function decomposition over networks, highlighting challenges, insights, and future directions for exploiting these techniques within practical 3GPP MTC architecture. △ Less

Submitted 12 September, 2016; originally announced September 2016.

Comments: 17 pages, 7 figures in IEEE Access, Vol. 4, 2016

Bounds for Batch Codes with Restricted Query Size

Authors: Hui Zhang, Vitaly Skachek

Abstract: We present new upper bounds on the parameters of batch codes with restricted query size. These bounds are an improvement on the Singleton bound. The techniques for derivations of these bounds are based on the ideas in the literature for codes with locality. By employing additional ideas, we obtain further improvements, which are specific for batch codes. We present new upper bounds on the parameters of batch codes with restricted query size. These bounds are an improvement on the Singleton bound. The techniques for derivations of these bounds are based on the ideas in the literature for codes with locality. By employing additional ideas, we obtain further improvements, which are specific for batch codes. △ Less

Submitted 9 February, 2016; v1 submitted 29 October, 2015; originally announced October 2015.

Comments: Submitted to ISIT 2016

New Bounds for Permutation Codes in Ulam Metric

Authors: Faruk Göloğlu, Jüri Lember, Ago-Erik Riet, Vitaly Skachek

Abstract: 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… ▽ More 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. △ Less

Submitted 20 April, 2015; originally announced April 2015.

Comments: To be presented at ISIT 2015, 5 pages

Data Dissemination Problem in Wireless Networks

Authors: Ivo Kubjas, Vitaly Skachek

Abstract: In this work, we formulate and study a data dissemination problem, which can be viewed as a generalization of the index coding problem and of the data exchange problem to networks with an arbitrary topology. We define $r$-solvable networks, in which data dissemination can be achieved in $r > 0$ communications rounds. We show that the optimum number of transmissions for any one-round communications… ▽ More In this work, we formulate and study a data dissemination problem, which can be viewed as a generalization of the index coding problem and of the data exchange problem to networks with an arbitrary topology. We define $r$-solvable networks, in which data dissemination can be achieved in $r > 0$ communications rounds. We show that the optimum number of transmissions for any one-round communications scheme is given by the minimum rank of a certain constrained family of matrices. For a special case of this problem, called bipartite data dissemination problem, we present lower and upper graph-theoretic bounds on the optimum number of transmissions. For general $r$-solvable networks, we derive an upper bound on the minimum number of transmissions in any scheme with $\geq r$ rounds. We experimentally compare the obtained upper bound to a simple lower bound. △ Less

Submitted 9 October, 2015; v1 submitted 2 April, 2015; originally announced April 2015.

Comments: Notation clarification

Refined Upper Bounds on Stopping Redundancy of Binary Linear Codes

Authors: Yauhen Yakimenka, Vitaly Skachek

Abstract: The $l$-th stopping redundancy $ρ_l(\mathcal C)$ of the binary $[n, k, d]$ code $\mathcal C$, $1 \le l \le d$, is defined as the minimum number of rows in the parity-check matrix of $\mathcal C$, such that the smallest stopping set is of size at least $l$. The stopping redundancy $ρ(\mathcal C)$ is defined as $ρ_d(\mathcal C)$. In this work, we improve on the probabilistic analysis of stopping red… ▽ More The $l$-th stopping redundancy $ρ_l(\mathcal C)$ of the binary $[n, k, d]$ code $\mathcal C$, $1 \le l \le d$, is defined as the minimum number of rows in the parity-check matrix of $\mathcal C$, such that the smallest stopping set is of size at least $l$. The stopping redundancy $ρ(\mathcal C)$ is defined as $ρ_d(\mathcal 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 $ρ_l(\mathcal C)$, for $1 \le l \le d$. Our approach is compared to the existing methods by numerical computations. △ Less

Submitted 27 February, 2015; v1 submitted 31 October, 2014; originally announced October 2014.

Comments: 5 pages; ITW 2015

Linear Batch Codes

Authors: Helger Lipmaa, Vitaly Skachek

Abstract: In an application, where a client wants to obtain many elements from a large database, it is often desirable to have some load balancing. Batch codes (introduced by Ishai et al. in STOC 2004) make it possible to do exactly that: the large database is divided between many servers, so that the client has to only make a small number of queries to every server to obtain sufficient information to recon… ▽ More In an application, where a client wants to obtain many elements from a large database, it is often desirable to have some load balancing. Batch codes (introduced by Ishai et al. in STOC 2004) make it possible to do exactly that: the large database is divided between many servers, so that the client has to only make a small number of queries to every server to obtain sufficient information to reconstruct all desired elements. Other important parameters of the batch codes are total storage and the number of servers. Batch codes also have applications in cryptography (namely, in the construction of multi-query computationally-private information retrieval protocols). In this work, we initiate the study of linear batch codes. These codes, in particular, are of potential use in distributed storage systems. We show that a generator matrix of a binary linear batch code is also a generator matrix of classical binary linear error-correcting code. This immediately yields that a variety of upper bounds, which were developed for error-correcting codes, are applicable also to binary linear batch codes. We also propose new methods to construct large linear batch codes from the smaller ones. △ Less

Submitted 10 April, 2014; originally announced April 2014.

Forwarding Without Repeating: Efficient Rumor Spreading in Bounded-Degree Graphs

Authors: Vincent Gripon, Vitaly Skachek, Michael Rabbat

Abstract: We study a gossip protocol called forwarding without repeating (FWR). The objective is to spread multiple rumors over a graph as efficiently as possible. FWR accomplishes this by having nodes record which messages they have forwarded to each neighbor, so that each message is forwarded at most once to each neighbor. We prove that FWR spreads a rumor over a strongly connected digraph, with high prob… ▽ More We study a gossip protocol called forwarding without repeating (FWR). The objective is to spread multiple rumors over a graph as efficiently as possible. FWR accomplishes this by having nodes record which messages they have forwarded to each neighbor, so that each message is forwarded at most once to each neighbor. We prove that FWR spreads a rumor over a strongly connected digraph, with high probability, in time which is within a constant factor of optimal for digraphs with bounded out-degree. Moreover, on digraphs with bounded out-degree and bounded number of rumors, the number of transmissions required by FWR is arbitrarily better than that of existing approaches. Specifically, FWR requires O(n) messages on bounded-degree graphs with n nodes, whereas classical forwarding and an approach based on network coding both require ω(n) messages. Our results are obtained using combinatorial and probabilistic arguments. Notably, they do not depend on expansion properties of the underlying graph, and consequently the message complexity of FWR is arbitrarily better than classical forwarding even on constant-degree expander graphs, as n \rightarrow \infty. In resource-constrained applications, where each transmission consumes battery power and bandwidth, our results suggest that using a small amount of memory at each node leads to a significant savings. △ Less

Submitted 14 August, 2012; originally announced August 2012.

Comments: 16 pages

Optimal Index Codes with Near-Extreme Rates

Authors: Son Hoang Dau, Vitaly Skachek, Yeow Meng Chee

Abstract: 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 u… ▽ More 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. 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. Additionally, a new upper bound on the min-rank of a digraph, the circuit-packing bound, is presented. This bound is often tighter than the previously known bounds. By employing this new bound, we present several families of digraphs whose min-ranks can be found in polynomial time. △ Less

Submitted 18 March, 2013; v1 submitted 6 February, 2012; originally announced February 2012.

Comments: 15 pages, submitted to IEEE Transactions on Information Theory

Error-Correction in Flash Memories via Codes in the Ulam Metric

Authors: Farzad Farnoud, Vitaly Skachek, Olgica Milenkovic

Abstract: 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 \emph{translocation rank codes} account for more general forms of errors that arise in storage systems. Translocations represent a natural extens… ▽ More 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 \emph{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. △ Less

Submitted 21 April, 2013; v1 submitted 4 February, 2012; originally announced February 2012.

Hybrid Noncoherent Network Coding

Authors: Vitaly Skachek, Olgica Milenkovic, Angelia Nedic

Abstract: 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 networks is much smaller then the length of the… ▽ More 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 networks is much smaller then 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 represents a combination 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 subspace decoders. △ Less

Submitted 23 September, 2012; v1 submitted 22 July, 2011; originally announced July 2011.

Comments: 15 pages

Error Correction for Index Coding with Side Information

Authors: Son Hoang Dau, Vitaly Skachek, Yeow Meng Chee

Abstract: 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 h… ▽ More 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 implicit 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. △ Less

Submitted 14 May, 2011; originally announced May 2011.

Comments: 14 pages

On the Pseudocodeword Redundancy of Binary Linear Codes

Authors: Jens Zumbrägel, Vitaly Skachek, Mark F. Flanagan

Abstract: The AWGNC, BSC, and max-fractional pseudocodeword redundancies of a binary linear code are 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 fa… ▽ More The AWGNC, BSC, and max-fractional pseudocodeword redundancies of a binary linear code are 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. △ Less

Submitted 6 March, 2012; v1 submitted 18 March, 2011; originally announced March 2011.

Comments: 14 pages. arXiv admin note: substantial text overlap with arXiv:1005.3486

On the Security of Index Coding with Side Information

Authors: Son Hoang Dau, Vitaly Skachek, Yeow Meng Chee

Abstract: 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… ▽ More 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^\perp$, is $(d-1-t)$-block secure (and hence also weakly secure) if the adversary knows in advance $t \leq 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 $κ_q$ is a generalization of the min-rank over $F_q$ of the side information graph for the ICSI problem in its original formulation in the work of Bar- Yossef et al. △ Less

Submitted 14 February, 2011; originally announced February 2011.

Comments: 14 pages

Index Coding and Error Correction

Authors: Son Hoang Dau, Vitaly Skachek, Yeow Meng Chee

Abstract: 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 h… ▽ More 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. △ Less

Submitted 14 January, 2011; originally announced January 2011.

Comments: 5 pages, submitted

Secure Index Coding with Side Information

Authors: Son Hoang Dau, Vitaly Skachek, Yeow Meng Chee

Abstract: 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 coding schemes for the ICSI problem 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 coding sche… ▽ More 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 coding schemes for the ICSI problem 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 coding scheme for the ICSI problem based on a linear code C of length n, minimum distance d and dual distance d^\perp, is (d-1-t)-block secure (and hence also weakly secure) if the adversary knows in advance t \le d - 2 messages, and is completely insecure if the adversary knows in advance more than n - d^\perp messages. △ Less

Submitted 25 November, 2010; originally announced November 2010.

Comments: 8 pages

Characterization of Graph-cover Pseudocodewords of Codes over $F_3$

Authors: Vitaly Skachek

Abstract: 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 o… ▽ More 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 becom is more involved. In this work, a characterization of the fundamental cone for codes over $F_3$ is discussed. △ Less

Submitted 22 July, 2010; originally announced July 2010.

Comments: 5 pages, to be presented in ITW 2010, Dublin, Ireland

Exploration of AWGNC and BSC Pseudocodeword Redundancy

Authors: Jens Zumbragel, Mark F. Flanagan, Vitaly Skachek

Abstract: The AWGNC, BSC, and max-fractional pseudocodeword redundancy of a code is defined 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 the code. This paper provides new results on the AWGNC, BSC, and max-fractional pseudocodeword redundancies of codes. The pseudocodeword redundancies for all codes of sm… ▽ More The AWGNC, BSC, and max-fractional pseudocodeword redundancy of a code is defined 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 the code. This paper provides new results on the AWGNC, BSC, and max-fractional pseudocodeword redundancies of codes. The pseudocodeword redundancies for all codes of small length (at most 9) are computed. Also, 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. △ Less

Submitted 19 May, 2010; originally announced May 2010.

Comments: 7 pages

On the Pseudocodeword Redundancy

Authors: Jens Zumbragel, Mark F. Flanagan, Vitaly Skachek

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

Submitted 11 January, 2010; originally announced January 2010.

Comments: 5 pages

Correcting a Fraction of Errors in Nonbinary Expander Codes with Linear Programming

Authors: Vitaly Skachek

Abstract: A linear-programming decoder for \emph{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/4 δ_A δ_B (where δ_A and δ_B are the relative minimum distances of the constituent codes). A linear-programming decoder for \emph{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/4 δ_A δ_B (where δ_A and δ_B are the relative minimum distances of the constituent codes). △ Less

Submitted 27 October, 2010; v1 submitted 8 June, 2009; originally announced June 2009.

Comments: Part of this work was presented at the IEEE International Symposium on Information Theory 2009, Seoul, Korea

Recursive Code Construction for Random Networks

Authors: Vitaly Skachek

Abstract: A modification of Koetter-Kschischang codes for random networks is presented (these codes were also studied by Wang et al. 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 modification of Koetter-Kschischang codes for random networks is presented (these codes were also studied by Wang et al. 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. △ Less

Submitted 16 October, 2009; v1 submitted 23 June, 2008; originally announced June 2008.

Comments: Submitted to IEEE Transactions on Information Theory

Linear-Programming Decoding of Nonbinary Linear Codes

Authors: Mark F. Flanagan, Vitaly Skachek, Eimear Byrne, Marcus Greferath

Abstract: A framework for linear-programming (LP) decoding of nonbinary linear codes over rings is developed. This framework facilitates linear-programming based reception for coded modulation systems which use direct modulation mapping of coded symbols. It is proved that the resulting LP decoder has the 'maximum-likelihood certificate' property. It is also shown that the decoder output is the lowest cost… ▽ More A framework for linear-programming (LP) decoding of nonbinary linear codes over rings is developed. This framework facilitates linear-programming based reception for coded modulation systems which use direct modulation mapping of coded symbols. It is proved that the resulting LP decoder has the 'maximum-likelihood certificate' 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 linear-programming 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 the [11,6] ternary Golay code with ternary PSK modulation over 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 LDPC codes with corresponding PSK modulations over AWGN. △ Less

Submitted 4 June, 2009; v1 submitted 28 April, 2008; originally announced April 2008.

Comments: To appear in the IEEE Transactions on Information Theory. 54 pages, 5 figures

Report number: CSI-01-01

Lower Bounds on the Minimum Pseudodistance for Linear Codes with $q$-ary PSK Modulation over AWGN

Authors: Vitaly Skachek, Mark F. Flanagan

Abstract: We present lower bounds on the minimum pseudocodeword effective Euclidean distance (or minimum "pseudodistance") for coded modulation systems using linear codes with $q$-ary phase-shift keying (PSK) modulation over the additive white Gaussian noise (AWGN) channel. These bounds apply to both binary and nonbinary coded modulation systems which use direct modulation mapping of coded symbols. The mi… ▽ More We present lower bounds on the minimum pseudocodeword effective Euclidean distance (or minimum "pseudodistance") for coded modulation systems using linear codes with $q$-ary phase-shift keying (PSK) modulation over the additive white Gaussian noise (AWGN) channel. These bounds apply to both binary and nonbinary coded modulation systems which use direct modulation mapping of coded symbols. The minimum pseudodistance may serve as a first-order measure of error-correcting performance for both linear-programming and message-passing based receivers. In the case of a linear-programming based receiver, the minimum pseudodistance may be used to form an exact bound on the codeword error rate of the system. △ Less

Submitted 12 June, 2008; v1 submitted 26 March, 2008; originally announced March 2008.

Comments: 6 pages, Proceedings 5-th International Symposium on Turbo Codes & related topics

Polytope Representations for Linear-Programming Decoding of Non-Binary Linear Codes

Authors: Vitaly Skachek, Mark F. Flanagan, Eimear Byrne, Marcus Greferath

Abstract: 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 classica… ▽ More 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. △ Less

Submitted 17 April, 2008; v1 submitted 25 December, 2007; originally announced December 2007.

Comments: 5 pages, to appear in 2008 IEEE International Symposium on Information Theory

Linear-programming Decoding of Non-binary Linear Codes

Authors: Mark F. Flanagan, Vitaly Skachek, Eimear Byrne, Marcus Greferath

Abstract: We develop a framework for linear-programming (LP) decoding of non-binary linear codes over rings. We prove that the resulting LP decoder has the `maximum likelihood certificate' property, and we show that the decoder output is the lowest cost pseudocodeword. Equivalence between pseudocodewords of the linear program and pseudocodewords of graph covers is proved. LP decoding performance is illust… ▽ More We develop a framework for linear-programming (LP) decoding of non-binary linear codes over rings. We prove that the resulting LP decoder has the `maximum likelihood certificate' property, and we show that the decoder output is the lowest cost pseudocodeword. Equivalence between pseudocodewords of the linear program and pseudocodewords of graph covers is proved. LP decoding performance is illustrated for the (11,6,5) ternary Golay code with ternary PSK modulation over AWGN, and in this case it is shown that the LP decoder performance is comparable to codeword-error-rate-optimum hard-decision based decoding. △ Less

Submitted 10 October, 2007; v1 submitted 30 July, 2007; originally announced July 2007.

Comments: 6 pages, 1 figure, 7-th International ITG Conference on Source and Channel Coding (SCC'08)

Improved Nearly-MDS Expander Codes

Authors: Ron M. Roth, Vitaly Skachek

Abstract: 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 const… ▽ More 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. △ Less

Submitted 10 May, 2006; v1 submitted 21 January, 2006; originally announced January 2006.

Comments: Part of this work was presented at the 2004 IEEE Int'l Symposium on Information Theory (ISIT'2004), Chicago, Illinois (June 2004). This work was submitted to IEEE Transactions on Information Theory on January 21, 2005. To appear in IEEE Transactions on Information Theory, August 2006. 12 pages

Decoding of Expander Codes at Rates Close to Capacity

Authors: Alexei Ashikhmin, Vitaly Skachek

Abstract: 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-ε)C (C is a capacity of a binary symmetr… ▽ More 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-ε)C (C is a capacity of a binary symmetric channel), whose decoding probability decreases polynomially in 1/N. It is shown that if the decoding probability decreases sufficiently fast, but still only polynomially fast in 1/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/ε, then the decoding time complexity of the presented family is linear in N and polynomial in 1/ε. 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 exponentially decaying (in N) error probability, and at the same time to have decoding time complexity linear in N and polynomial in 1/ε. △ Less

Submitted 22 January, 2007; v1 submitted 12 August, 2005; originally announced August 2005.

Comments: Appears in IEEE Transactions on Information Theory, December 2006. The short version of this paper appears in the proceedings of the 2005 IEEE International Symposium on Information Theory, Adelaide, Australia, September 4-9, 2005