This paper presents a successive cancellation (SC) decoding of polar codes modified for insertion/deletion/substitution (IDS) error channels, in which insertions and deletions are described by drift values. The recursive calculation of the original SC decoding is modified to include the drift values as stochastic variables. The computational complexity of the modified SC decoding is O (D3) with respect to the maximum drift value D, and O (N log N) with respect to the code length N. The symmetric capacity of polar bit channel is estimated by computer simulations, and frozen bits are determined according to the estimated symmetric capacity. Simulation results show that the decoded error rate of polar code with the modified SC list decoding is lower than that of existing IDS error correction codes, such as marker-based code and spatially-coupled code.

Turbo equalization is an iterative equalization and decoding technique that can achieve impressive performance gains for communication systems. In this letter, we investigate the turbo equalization method for the decoding of the Davey-MacKay (DM) construction over the IDS-AWGN channels, which indicates a cascaded insertion, deletion, substitution (IDS) channel and an additive white Gaussian noise (AWGN) channel. The inner decoder for the DM construction can be seen as an maximum a-posteriori (MAP) detector. It receives the beliefs generated by the outer LDPC decoder when turbo equalization is used. Two decoding schemes with different kinds of inner decoders, namely hard-input inner decoder and soft-input inner decoder, are investigated. Simulation results show that significant performance gains are obtained for both decoders with respect to the insertion/deletion probability at different SNR values.

Nonbinary M-ary data processed by data entry systems, such as keyboard devices and character recognition systems, often have various types of error, such as symbol-substitution errors, deletion errors, insertion errors, and adjacent-symbol-transposition errors. This paper proposes nonsystematic M-ary codes capable of correcting these errors. The code is defined as a set of codewords that satisfy three conditions required to correct substitution, deletion/insertion, and adjacent-symbol-transposition errors. Since symbol-substitution errors in data entry systems are usually asymmetric, this paper also presents asymmetric-symbol-substitution error correcting codes capable of correcting deletion, insertion, and adjacent-symbol-transposition errors. For asymmetric-symbol-substitution error correction, we employ a mapping derived from the vertex coloring in an error directionality graph. The evaluation shows that the asymmetric codes have three to five times larger number of codewords than the symmetric codes.

This paper presents a class of binary block codes capable of correcting single synchronization errors and single reversal errors with fewer check bits than the existing codes by 3 bits. This also shows a decoding circuit and analyzes its complexity.