PERFECT (D, K)-CODES CAPABLE OF CORRECTING SINGLE PEAK-SHIFTS

Codes, consisting of sequences 0 (alpha1) 10 (alpha2)1 ... 0 (alpha N) 1, where d less-than-or-equal-to alpha(i) less-than-or-equal-to k, and call them (d,k)-codes of reduced length N are considered. We introduc e a definition of arbitrary (d, k)- and perfect (d, k)-codes capable o f correcting single peak-shifts of given size t. For the construction of perfect codes, a general combinatorial method connected with findin g ''good'' weight sequences in Abelian groups is used, and the concept of perfect t-shift N-designs is introduced. Explicit constructions of such designs for t = 1, t = 2, and t = (p - 1)/2 are given, where p i s a prime. This construction is not only effective, but also universal in the sense that it does not depend on the (d, k)-constraints. It al so allows to correct automatically those peak-shifts that violate (d, k)-constraints. Furthermore, our construction is naturally extended to (d, k)-codes of fixed binary length and allows the determination of t he beginning of the next codeword. The question whether the designed c odes can be represented as systematic codes with minimal redundancy is considered as well. In particular, for any (d, k)-code with n q-ary ( q = k - d + 1 > 2) information digits, a method of finding r q-ary che ck digits is given such that the resulting systematic code is capable of correcting single peak-shifts of size 1, where r is determined uniq uely by q(r - 1) - 2(r - 1) < 2n + 1 less-than-or-equal-to q(r) - 2r. This code is perfect if 2n + 1 = q(r) - 2r.