Difference-Preserving Codes, Circuit Codes and (m,n)-Codes

摘要

An ordered list of integers coded as binary words of length n is called adifference-preserving code (DP-code) if the following two properties hold: (1) the list distance between two words, i.e. the absolute value of the difference of their indices, is equal to their Hamming distance, as long as the list distance does not exceed a certain threshold t; (2) if the list distance exceeds t, then so does the Hamming distance. Slight modifications of such a structure are known as circuit codes, snake-in-the-box codes, or (m,n) codes. The paper discusses each one of these. A detailed example of a construction technique for a certain class of DP-codes is then presented. Finally, a list is given containing known upper and lower bounds for the lengths of the various types of ordered codes discussed.