A Method for Constructing Circuit Codes

ABSTRACT

A d-dimensional circuit code of spread s (also called SIBs, code or circuit code of minimum distance s) is a simple circuit Q in the graph of the d-dimensional cube [0, 1]d such that any two vertices of Q differing in exactly r coordinates, with r < s, can be joined by a path formed from r edges of Q. Such codes are designed to introduce error detection into certain analog-to-digital conversion systems. Longer codes correspond to increased accuracy of the system, and hence there is interest in determining the maximum length C(d, s) of d-dimensional circuit codes of spread s. In the present study the author contributes to this problem for even values of s by describing a method of combining a code of spread s with a suitably related code of spread s-1 so as to produce a longer code of spread s.

REFERENCES

• 1: ABBOTT, H. L. Some problems in combimtorial analysis, Ph,d. thesis, U. of Alberta, Edlnontol b Canada 1965,
• 2: CHIEN, R. T., FREMAN, C. V., AND TANG D. T, Error correctioa and circuits oF the n-cube, Proc, Second Almual kllerton Conf, oa Circuit arid System Theory, Sepember 28--30, 1964, U. of Illinois AlLerton Holse, Mont, icello, Ill., pp. 899-912.
• 3: DANZER, L., AND KLEE, V, Lengths of snakes in boxes. J. ConSinatorial Theory 2 (19671 (to appear).
• 4: DaVIES, 11. W. Longest "separated" paths and loops ira an N cube. IEEE Tran.. EC.-11 (1965), 261
• 5: EVEN, S. Snake-in-the-box codes. IEEE Trans. EC-12 (1963), 18.
• 6: KAUTz, W. tt. Unit-distauce error-checking eodes. IRE Trans. EC-7 (19581, 179-180.
• 7: KLEE, V, Long paths aLd circuits on polyopes, in Convex Polytopes, Griiabmm, B., Wiley, New York, 1967, pp. 356489.
• 8: PETmSON, W.W. Error Correcting Codes. M.I.T. Press, Cambridge, Mass., arid Wiley, New York, 1961.
• 9: RAMANUJACIIARYIU, C., AND MENON, V. V. A note on the snake-in-the-box prohlern. Publ. Inst. Stativt. Univ. Paris I3 (1964), 131-135.
• 10: SINLlerON, R. C. Generalized snake-in-the-box codes. IEEE Trans, EC-15 (1966), 596-602.
• 11: VASIIEV, ,IL L. On the length of a cycle in an n-dimensional trait cube. Soviet Math. Dolcl. 4 (1963), 160.163. Translated from Dokl. Acad, Nauk SSSR I8 (19631, 753-755
• 12: ZUaAVLEV, ,hL I. Set-theoretic methods in a Boolean algebra. Probl. Kibernetiki, No. 8 (1962), 5-44 (in RussiaN).

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Design, Measurement, Performance, Theory, Verification