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.

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.