We introduce a probabilistic burst insertion/deletion channel (BIDC) model and investigate practical concatenated coding schemes for BIDCs with multiple burst errors. First, the existence of channel capacity for BIDCs is established, and the capacity upper and lower bounds for BIDCs are analyzed and computed. For the capacity upper bound, genie-aided information is provided to the receiver, and then the informationtheoretic upper bound can be computed via the Blahut-Arimoto algorithm. For the capacity lower bound, the achievable information rates of BIDCs with independent and identically distributed inputs are computed by using trellis structures of the corresponding channels. Second, marker codes, constructed by concatenating marker bits with low-density parity-check (LDPC) codes, are investigated for BIDCs. The forward and backward (FB) detection algorithm of marker codes, initially designed for random insertion/deletion errors, may not be optimal for BIDCs. Therefore, a new FB detection algorithm of marker codes is designed according to the characteristics of BIDCs. Furthermore, an inter-frame interleaving scheme is proposed to enhance the decoding performance of marker codes over BIDCs. Simulation results show that the error rate performance of our newly designed FB algorithm for BIDCs is superior to that of the original FB algorithm when the burst characteristics of the channel are explicitly considered. Furthermore, the performance of the proposed algorithm is also better than that of the recently designed deep learning-based decoding method for marker codes over insertion/deletion channels.

A message block transmitted over a torn paper channel (TPC) will be split into small pieces of different sizes without overlaps. Moreover, these pieces are shuffled and thus out of order. Nested Varshamov-Tenengolts (VT) codes proposed by Nassirpouret al. can be used to reassembly these pieces, but there are significant gaps between the rates of nested VT codes and channel capacities. In this paper, by investigating the minimum Hamming distance of nested VT codes, we explain why the decoder of nested VT codes is prone to output two or more candidate sequences. We also show that embedded information in nested VT codes indeed plays a role as a hash function, but the number of effective hash bits is significantly less than the number of check bits used in nested VT codes. Motivated by this, we investigate nested hash codes for TPCs with different well-known hash algorithms, such as the message-digest algorithm 5 (MD5), cyclic redundancy check (CRC) and MurmurHash. Simulation results show that the proposed nested hash codes are better than nested VT codes in terms of error rate, failure rate, and reassembly complexity. Moreover, simulations indicate that there is a significant improvement in rates for the proposed codes when compared with existing coding schemes.

Pseudocodewords, and in particular minimal pseudocodewords, play an important role in understanding the performance of linear programming (LP) decoding. In this paper, we investigate minimal pseudocodewords of binary Hamming codes described by full-rank parity-check matrices. We first provide some general results on minimal pseudocodewords with support size 3 of a binary parity-check matrix. We also prove a lower bound on the minimum binary symmetric channel (BSC) pseudoweight of a binary parity-check matrix. Then we prove that a full-rank parity-check matrix of a binary Hamming code has minimal pseudocodewords of certain types whose support sizes are larger than 3. Interestingly enough, the BSC pseudoweight of all these minimal pseudocodewords is 2. Using this fact as well as the above-mentioned lower bound, we further prove that a full-rank parity-check matrix of a binary Hamming code has minimum BSC pseudoweight 2. Moreover, the additive white Gaussian noise channel (AWGNC) pseudoweight of all these minimal pseudocodewords is 3. Based on numerical observations, we conjecture that a full-rank parity-check matrix of a binary Hamming code has minimum AWGNC pseudoweight 3. Finally, we provide more properties of a subset of minimal pseudocodewords of a full-rank parity-check matrix of a binary Hamming code.

Marker code is an effective coding scheme to protect data from insertions and deletions. It has potential applications in future storage systems, such as DNA storage and racetrack memory. When decoding marker codes, perfect channel state information (CSI), i.e., insertion and deletion probabilities, are required to detect insertion and deletion errors. Sometimes, the perfect CSI is not easy to obtain or the accurate channel model is unknown. Therefore, it is deserved to develop detecting algorithms for marker code without the knowledge of perfect CSI. In this paper, we propose two CSI-agnostic detecting algorithms for marker code based on deep learning. The first one is a model-driven deep learning method, which deep unfolds the original iterative detecting algorithm of marker code. In this method, CSI become weights in neural networks and these weights can be learned from training data. The second one is a data-driven method which is an end-to-end system based on the deep bidirectional gated recurrent unit network. Simulation results show that error performances of the proposed methods are significantly better than that of the original detection algorithm with CSI uncertainty. Furthermore, the proposed data-driven method exhibits better error performances than other methods for unknown channel models.

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.

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.

The Euclidean projection involved in the decoding of low-density parity-check (LDPC) codes with the alternating direction method of multipliers (ADMM) can be simplified by jointly using uniform quantization and look-up tables (LUTs). However, the memory requirement for the original LUT-based ADMM decoding is comparatively large. In this letter, a nonuniform quantization method is proposed to save the memory cost by minimizing the mean square error of the outputs of Euclidean projections during quantization. Simulation results over two exemplified LDPC codes show that the proposed method can achieve similar error-rate performances when compared with the original LUT-based ADMM decoding by using significantly less memory units.

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.

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.

The inner decoder of the Davey-MacKay (DM) construction for combating insertions, deletions and substitution errors, has high complexity and produces bursts of output likelihoods of greatest uncertainty in the vicinity of insertions and deletions. We therefore propose (i) a lookup-table-based implementation of the inner decoder to reduce its complexity, (ii) the use of interleaved LDPC codes as outer codes in the DM construction to spread the uncertain likelihoods produced by the inner decoder over several constituent LDPC codewords. Simulation results show that the proposed lookup table approach reduces the complexity of the inner decoder considerably while a significant improvement in frame error rate (FER) performance can be obtained with small interleaving depths. Our lookup table approach culminates in an iterative decoding scheme which yields improved FER performance over its non-iterative counterparts, yet with only a modest increase in decoding complexity, when the insertion/deletion probability is small.