Search

Consider a file synchronization problem at two remote nodes A and B connected by a noiseless link. The node A has a binary file $X$ , and node B has a binary file $Y$ which is an edited version of $X$ with random insertions and deletions (indels). The goal is to reconstruct $X$ at node B from $Y$ with minimal exchange of information between A and B. In this letter, we design a single-round, thus low latency, file synchronization scheme with low redundancy. In particular, a series of redundancy bits, including markers, check symbols of Reed-Solomon (RS) codes for hashes and Varshamov-Tenengolts (VT) syndromes, are constructed from $X$ at node A and send to node B. According to the received redundancy and $Y$ , we develop a recovery algorithm at node B to reconstruct $X$. The amount of exchanged information of the proposed scheme is significantly reduced when compared with the existing single-round synchronization scheme under random indels. [ABSTRACT FROM AUTHOR]

The prefixed Varshamov-Tenengolts (VT) codes, which are subsets of VT codes with predetermined prefixes, can be used for error correction over segmented edit channels. In this paper, we investigate the construction and analysis of this class of codes. First, we derive upper bounds on the size of zero-error codes for segmented edit channels with segment-by-segment decoding. Second, we establish a one-to-one correspondence between prefixed VT codes and Levenshtein codes. Based on this relation, we can obtain explicit formulas on the size of prefixed VT codes via the existing results on the size of Levenshtein codes. Third, we construct a new zero-error prefixed VT code and show that the size of the constructed code is strictly larger than that of the existing prefixed VT code for the segmented deletion channel. Finally, an efficient systematic encoding method of prefixed VT codes is proposed for the segmented edit channels. [ABSTRACT FROM AUTHOR]

Guess & check (GC) codes can correct multiple deletions with high probability by guessing all possible deletion patterns at a polynomial complexity. This paper investigates an efficient way of guessing deletion patterns with the aid of markers. The marker are inserted as block identifiers into GC codewords and examined for implementing maximum-likelihood inference of deletion patterns in trellis graph. The resulting number of guesses for decoding marker GC codes can be reduced significantly by an increasing order of magnitude as the code length grows. [ABSTRACT FROM AUTHOR]

The alternating direction method of multipliers (ADMM) has been adapted for decoding low-density parity-check (LDPC) codes over intersymbol interference (ISI) channels in order to reduce the complexity of the traditional Turbo equalization (TE) method. However, the error rate performance of ADMM decoding may be degraded in certain ISI channels when compared with the TE at high signal-to-noise ratio regions. In order to address the problem, we derive a novel ADMM-based decoding method, called l2-box ADMM decoding, for LDPC codes over ISI channels. By introducing suitable penalty functions to l2-box ADMM decoding, we present an enhanced method, called l2-box ADMM penalized decoding, to further improve the performance. Simulation results on several ISI channels indicate that the proposed l2-box ADMM penalized decoding can achieve better error rate performances compared with the TE and the existing ADMM penalized decoding methods, especially for ISI channels with long memory, while maintaining the low-complexity advantage of the ADMM penalized decoding. [ABSTRACT FROM AUTHOR]

Permutation codes are widely studied due to their promising applications in flash memories. Based on the theory of permutation groups and subgroups, two classes of permutation codes are constructed to correct a single burst deletion of length up to a designated parameter. The proposed codes can achieve larger rates than available codes while maintaining simple interleaving structures. The decoding methods for the proposed codes are provided in proofs and verified by examples. [ABSTRACT FROM AUTHOR]

Multi-permutation codes for rank modulation scheme have been recently proposed for efficiently storing data in flash memories. In this letter, we investigate the problem of a single burst unstable deletion (BUD) of length $t$ in a $t$ -balanced multi-permutation and this problem can be decomposed into the sub-problems of a single permutation-invariant deletion (PID) in $t$ permutations by a rank demodulation method. Based on the rank demodulation method and the interleaving of $t$ single-PID-correcting permutation codes, we construct two classes of $t$ -balanced multi-permutation codes that are capable of correcting a single BUD of length $t$. Moreover, the constructed codes can achieve higher rates compared with the existing code. The decoding methods are provided in the proofs and verified by some examples. [ABSTRACT FROM AUTHOR]

Based on the extended Reed-Solomon (RS) code that has two information symbols over the field ${\mathbb F}_{q}$ , we can construct a binary regular matrix ${ {\boldsymbol{\textstyle H}}}(\gamma,\rho)$ , where $q:=2^{r}$ for some positive integer $r$ , $\gamma $ and $\rho $ are two positive integers such that $\gamma \le q$ and $\rho \le q$. The matrix ${ {\boldsymbol{\textstyle H}}}(\gamma,\rho)$ specifies a low-density parity-check (LDPC) code ${\mathcal C}(\gamma,\rho)$ , called an RS-LDPC code. In this letter, we provide more results on the minimum distance and stopping distance of this class of codes (denoted by $d({\mathcal C}(\gamma,\rho))$ and $s({ {\boldsymbol{\textstyle H}}}(\gamma,\rho))$) for the case $\gamma =6$. For $\rho =q$ , we derive an upper bound on $s({ {\boldsymbol{\textstyle H}}}(6,q))$ and $d(\mathcal {C}(6,q))$ , which is conjectured to be tight for $q\ge 32$. For $\rho < q$ , we investigate the choices of $\rho $ such that $d(\mathcal {C}(6,\rho))$ (resp., $s({ {\boldsymbol{\textstyle H}}}(6,\rho))$) can be improved compared with the original $d(\mathcal {C}(6,q))$ (resp., $s({ {\boldsymbol{\textstyle H}}}(6,q))$). [ABSTRACT FROM AUTHOR]

This letter investigates the application of alternating direction method of multipliers (ADMM) in decoding low-density parity-check (LDPC) codes over partial response (PR) channels. Unlike the ADMM decoding in memoryless channels, the ADMM decoding in PR channels becomes involved with the correlation among adjacent code symbols. As the update equations for code symbols constitute the most complicated part of the ADMM decoding in PR channels, this letter focuses on their derivation by making use of the iterative fashion of ADMM and incorporating the use of a penalty function. A notable advantage of the proposed ADMM penalized decoding algorithm is that its complexity increases linearly with the memory length of PR channels. Simulation results show that the proposed algorithm can achieve error performance comparable with that of Turbo equalization (TE) in the waterfall region. It can also outperform TE at high signal-to-noise ratios as iteration grows. [ABSTRACT FROM AUTHOR]

The rank-modulation scheme has been recently proposed to write and store data in flash memories efficiently. In this paper, a new construction of systematic error-correcting codes for permutations is presented under the Chebyshev distance. By constructing a subgroup code and using its coset codes to partition the set of information permutations, the proposed code construction can achieve much larger code cardinality and hence higher code rates. To facilitate the encoding and decoding of the constructed codes, we also investigate the concepts of ranking and unranking for permutations, and generalize them to $M$ -ranking and $M$ -unranking for multi-permutations. Examples are provided to demonstrate the relevant concepts and the encoding/decoding algorithms. [ABSTRACT FROM AUTHOR]

Codes over permutations and multi-permutations have been recently proposed for efficiently storing data in flash memories. Based on the interleaving techniques for permutations, we construct two classes of permutation codes which can correct a single burst symbol-invariant deletion (SID) of length up to $t$. Moreover, a class of balanced multi-permutation codes capable of correcting a single burst SID of length up to $t$ is presented. The simple decoding procedures for the constructed codes are included in proofs and verified by examples. [ABSTRACT FROM AUTHOR]

Linear programming decoding with the alternating direction method of multipliers (ADMM) is a promising decoding technique for low-density parity-check (LDPC) codes, where the computational complexity of Euclidean projections onto check polytopes becomes a prominent problem. In this paper, the problem is circumvented by building lookup tables (LUTs) and quantizing the inputs to approach approximate Euclidean projections at low computational complexities. To challenge the huge memory cost of LUTs, we first propose two commutative compositions of Euclidean projection and self-map, and show the existence of a small quantization range which does not alter the Euclidean projection. Then, we investigate the design and simplification of the LUTs by exploiting the commutative compositions and check node decomposition techniques. An efficient algorithm for the LUT-based projection is demonstrated by using one simplification method. Simulation results show that for both the regular and irregular LDPC codes, the ADMM decoding using LUT-based projection can substantially reduce the decoding time while maintaining the error rate performance at a comparatively large memory cost. [ABSTRACT FROM PUBLISHER]

Similar to the belief propagation decoder, linear programming decoding based on the alternating direction method of multipliers (ADMM) can also be seen as an iterative message-passing decoding algorithm. How to schedule messages efficiently is an important aspect since it will influence the convergence rate of iterative decoders. In this letter, we investigate the node-wise scheduling for ADMM decoders, named NS-ADMM. In particular, we propose a reduced-complexity method for the NS-ADMM decoder by avoiding Euclidean projections involved in the calculation of message residuals. Simulation results show that the proposed method converges much faster than the flooding and layered scheduling while keeping a lower complexity when compared with the NS-ADMM decoder. [ABSTRACT FROM PUBLISHER]

By making the pseudocodewords more costly than codewords, the alternating direction method of multipliers (ADMM) penalized decoder can improve the error rate performances significantly for low-density parity-check (LDPC) codes at low signal-to-noise ratios. In this letter, we design two improved piecewise penalty functions for ADMM penalized decoder by increasing the slope of the penalty function at the points near $x=0$ and $x=1$ . The improved penalty functions can punish pseudocodewords more quickly and thus increase the decoding speed. Simulation results over two LDPC codes show that the proposed method improves the error rate performances and reduces the decoding time considerably. [ABSTRACT FROM PUBLISHER]

The Euclidean projection onto check polytopes is the most time-consuming operation in the linear programming (LP) decoding based on alternating direction method of multipliers (ADMM) for low-density parity-check (LDPC) codes. In this letter, instead of reducing the complexity of Euclidean projection itself, we propose a new method to reduce the decoding complexity of ADMM-based LP decoder by decreasing the number of Euclidean projections. In particular, if all absolute values of the element-wise differences between the input vector of Euclidean projection in the current iteration and that in the previous iteration are less than a predefined value, then the Euclidean projection at the current iteration will be no longer performed. Simulation results show that the proposed decoder can still save roughly 20% decoding time even if both the over-relaxation and early termination techniques are used. [ABSTRACT FROM PUBLISHER]

Based on linear programming (LP) decoding with alternating direction method of multipliers (ADMM), Liu et al. proposed an ADMM penalized decoder for low-density parity-check (LDPC) codes that can improve the error rate performance at low signal-to-noise ratios. In this letter, we propose a new ADMM penalized decoder to improve the error rate performance further for irregular LDPC codes. The proposed decoder modifies the penalty term of the objective function by assigning different penalty parameters for different variable node degrees. Simulations over three irregular LDPC codes show that the proposed decoder performs considerably better than the ADMM penalized decoder. [ABSTRACT FROM PUBLISHER]

A $(v,g)$-cage is a (not necessarily unique) smallest $v$-regular graph of girth $g$. On such a graph, a nonbinary $(2,v)$-regular low-density parity-check (LDPC) code can be defined such that the Tanner graph has girth $2g$ and the code length achieves the minimum possible. In this paper, we focus on two aspects of this class of codes, structural property and code optimization. We find that, in addition to those found previously, many cages can be used to construct structured LDPC codes. We show that all cages with even girth can be structured as protograph-based codes, many of which have block-circulant Tanner graphs. We also find that four cages with odd girth can be structured as protograph-based codes with block-circulant Tanner graphs. For code optimization, we develop an ontology-based approach. All possible inter-connected cycle patterns that lead to low symbol-weight codewords are identified to put together the ontology. By doing so, it becomes handleable to estimate and optimize distance spectrum of equivalent binary image codes. We further analyze some known codes from the Consultative Committee for Space Data Systems recommendation and design several new codes. Numerical results show that these codes have reasonably good minimum bit distance and perform well under iterative decoding. [ABSTRACT FROM PUBLISHER]

For the linear programming decoding (LPD) proposed by Feldman et al., the number of constraints increases exponentially with check degrees. By decomposing a high-degree check node into a number of degree-3 check nodes, the number of constraints grows linearly with check degrees. In this letter, we show that the size of the LPD can be reduced by decomposing a high-degree check node into a number of degree-4 check nodes. The LPD using the degree-4 decomposition leads to almost the same number of constraints as using the degree-3 decomposition, while the number of auxiliary variable nodes is less than half of the one using the degree-3 decomposition. Moreover, when decomposing a high degree check node into a number of check nodes with degree d, d>4, the number of constraints increases rapidly and the size of the LPD becomes larger than the degree-4 decomposition. It is demonstrated on an LDPC code and a BCH code that the decoding time of the degree-4 decomposition is the smallest among the different decomposition methods. [ABSTRACT FROM PUBLISHER]

The Davey-MacKay (DM) construction is a promising concatenated coding scheme for the binary-input, binary-output, insertion-deletion-substitution (IDS) channel. Many practical channels however have continuous output. We therefore develop a soft-input inner decoder for this coding scheme under a cascaded channel model consisting of the IDS channel followed by a binary-input, continuous-output, additive white Gaussian noise (AWGN) channel. We show that at low signal-to-noise ratios (SNRs), applying the proposed inner decoder to the unquantized AWGN channel output, yields significant performance improvements over the original coding scheme when the channel output is 1-bit quantized, although the performance gains do decrease as SNR increases. [ABSTRACT FROM PUBLISHER]