A coding scheme for single peak-shift correction in (d, k)-constrained channels

A two step coding scheme for peak-shift correction in (d, k)-constrained sequences is described. The first step is based on q-ary (q=k-d+1 is a prime) block codes that allow correction of specific types of double errors caused by single peak-shifts. The second step is a simple conversion of q-ary symbols to binary strings of the type 00. . .01. The concatenation of these strings satisfies the (d,k)-constraint within the codeword and in concatenation with neighboring words. The length of the codewords is controlled and, if necessary, can be fixed. The rate R₁ of the overall encoding approaches (2 log₂ (k-d+1)/(k+d+2) for large codeword lengths. Codes for correction of peak-shift, deletions, and insertions of zeros are presented as well. Encoding and decoding are done by simple algorithms without using look-up tables, enumeration or denumeration procedures and, therefore, the codelength may be large