176 IEEE TRANSACTIONS ON COMPUTERS, VOL. C-22, NO.

2, FEBRUARY 1973

Distance-2 Cyclic Chaining of Constant-Weight Codes

DONALD T. TANG AND C. N. LIU

Abstract-The cyclic distance-2 chaining of constant-weight weight m, one can readily see that a distance-2 cyclic
codes has applications in A/D conversions as well as in combina- chaining of constant-weight n-vectors provides a means
torial problems involving the exhaustion of m-out-of-n combinations.
It is shown in this paper that such a chaining can be obtained from to achieve this goal.
the Gray code circuit and its transformations. Algorithms based on
several theorems derived have been developed and programmed in I I. SOME BASIC PROPERTIES
APL. Gray codes are related to conventional binary codes
in the following fashion: for a given binary n-vector
Index Terms-Constant-weight codes, enumeration of m-out-
of-n combinations, Gray codes, Hamiltonian circuits. b= (bn, * .*, b2,b1), there corresponds a Gray code
4= (gan . .*, g2, g.). The mapping is characterized by
I. INTRODUCTION the following relations:
A N n-dimensional binary Gray code G. is an ordered gn = bn
cyclic sequence of 2n binary n-vectors such that gi-bi+l + bi, mod 2 for i= 1,*y , n-1 .

any two adjacent vectors differ in just a single n-i+l

place [1]-[3]. Such codes correspond to Hamiltonian bi E gi+j-1 =
mod 2for i = 1,. * * *, n -1.
circuits on the n-cube Qn. Gray codes are widely used in jl-

analog-to-digital conversions to minimize the digital The integer value =1 bi2 -1 represented by the con-
error due to an ambiguous analog signal between two ventional binary code is also assigned as the value of the
adjacent quantum levels. In some A/D conversions, it is corresponding Gray code and this is denoted by VG(4).
desirable to incorporate additional error protection [4]- A Gray code may be conveniently represented by its
[6]. transition sequence T(Gn) [8]. The transition sequence
In this paper we are concerned with protection against for an n-dimensional Gray code is a cyclically ordered
asymmetrical errors, to which constant-weight codes listing of the bit positions that change as one proceeds
have been shown to be effective [71. Our objective here along the Gray code circuit. Normally, the starting code
is to construct a class of codes with the combined fea- vector is taken to be the all-0 n-vector. For example, the
tures of both Gray codes and constant-weight codes. transition sequence for a four-dimensional Gray code is
The problem is essentially the following: given a set of as follows:
(m) binary n-vectors of weight m, it is desired to order
them in a cyclic chain such that any two adjacent n-vec- T(G4) = 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 4.
tors in the chain differ in exactly two places. Before If the starting code vector is different from the all-0
going into the derivation of our solution to this prob- n-vector, then the same transition sequence T(Gn) will
lem, we wish to point out that such cyclic chaining of clearly result in a Gn' which is obtainable from G,n by
constant weight n-vectors has applications in other complementing all positions corresponding to the non-
areas. In combinatorial problems involving n compo- zero positiqns in the starting code vector. We shall show
nents, for instance, one may wish to exhaust totally or in what follows that if we take a set of code vectors con-
partially the (.) combinations of m components. Since sisting of all constant-weight vectors while preserving
each component may be associated with a large data set their order on the Gray code circuit, we will have a dis-
which may need further processing, a minimal replace- tance-2 cyclic chaining of constant-weight codes. We
ment of components between two consecutive combina- shall first make a few observations.
tions often leads to significant savings in both computa- If one takes a set of code vectors consisting.of all
tion and data retrieval time. The ideal situation is to n-vectors with a particular position constrained to a con-
enumerate all (f) combinations such that exactly one stant, that is, for some i, gi = 0 (or gi = 1), while preserv-
replacement is needed from one combination to the next. ing their order on the Gray code circuit, then the (n-1)
If one represents each combination by an n-vector of subcube resulting from the deletion of gt forms a Gray
code Gn-l' such that Gn-l' is identical to G.-, (or if
Manuscript received July 24, 1971; revised August 17, 1972. This gi= 1, G.-,' is identical to Gn-, except that gi-, is com-
paper was presented in part at the 5th Annual Princeton Conference plemented). One also observes that, in a transition se-
on Information Sciences and Systems, March 1971.
The authors are with the IBM T. J. Watson Research Center, quence between two adjacent occurrences of any i
Yorktown Heights, N. Y. 10598. (i= 1, * **, n), gi on the corresponding Gray code cir-

Authorized licensed use limited to: POLO BIBLIOTECARIO DI INGEGNERIA. Downloaded on May 06,2021 at 07:45:46 UTC from IEEE Xplore. Restrictions apply.
TANG AND LIU: DISTANCE-2 CYCLIC CHAINING 177

cuit must stay constant. Furthermore, between two than two, then there exist u and v, also n-vectors of
adjacent occurrences of any i in a transition sequence, weight m, which interleave with x and y on the Gray
every j #i, except one, must appear an even number of code circuit Gn.
times [8]. It can be shown that, with the constraint Proof: From the constant-weight property of these
gi 0, the resulting transition sequence can be obtained n-vectors, the Hamming distance between any pair of
by the following procedure: subsequences between the such n-vectors must be even with exactly half of the dis-
first and the second, the third and the fourth i's, etc., are tance resulting from 0-1 changes and the other half from
replaced by the numbers each of which appears exactly 1-0 changes. Since the Hamming distance between x
once in their corresponding subsequence. For gi = 1, the and y is assumed to be greater than two, it must be four
procedure is the same except that the subsequences are or more. Let the positions where x and y differ be in-
taken between the second and third i's, etc., as well as dexed by ii, i2, * *, i2k-1 i2k, where il > i2, ' * ', > i2k-1
-

the last and the first i's. As an example, let us consider >i2k, k>2, and let us consider the subcube circuit G2k'
G4 constrained by g2 = 0. The subsequences of the transi- obtained by constraining all other positions to the cor-
tion sequence T(G4) are shown in brackets: responding values in x and y. From earlier observations,
T(G4) = 1[2 1 3 1 2]1 4 1[2 1 3 1 2]1 4. the bit patterns at i1 and i2 in G2k' are the patterns of G2'
with each bit pattern repeated consecutively 22k-2 times.
Replacing these subsequences by 3's, we obtain the Since the Hamming distance between (xi,, xi2) and
transition sequence corresponding to G3', (Yil, yi2) is two, there must exist (uil, ui2) and (vil, vi2)
T(G3') = 1 3 1 4 1 3 1 4. interleaving (xil, xi2) and (yil, yi2) on G2'. Furthermore,
there are 22k-2 consecutive 2k-vectors on G2k' each start-
If g2 =1 we have different subsequences as shown below: ing out with one of the four bit pairs described above.
T(G4) = 1 2] 1 3 1 [2 1 4 1 2] 1 3 1 [2 1 4. Consider the set of 2k-vectors starting with ui1 and ui2.
One of the 2 2k-2 vectors takes the following form:
Replacing these subsequences by 4's, we obtain the ui1t ui2, (1 -uil), (1 -ui9), 1, 0, * . , 1, 0. Clearly this
-

transition sequence corresponding to G3", 2k-vector is of weight k, and thus u, the corresponding
T(G3") 1 3 1 4 1 3 1 4. n-vector (by restoring the constrained bits previously
defined in x and y) must be of weight m. The same argu-
Note that T(G3') and T(Gs') are the same, and are ment can be used to establish the existence of another
equivalent to, when reindexed, the ordinary T(G3). How- n-vector, v. Since the four sets of constrained n-vectors
ever, Gs' can be obtained from T(G3') with a starting were seen to interleave, so do x and y with respect to
vector of (000) while G3" can be obtained from the same u and v.
transition sequence with a different starting vector of Theorem 2: The set of (4 ) n-vectors of weight m, when
(001). Consequently, G3' can be obtained directly from chained according to the ordering on the Gray code G.,
GS' by complementing position 1. In general, if the con- has a Hamming distance of exactly two between every
straint is gi= 0, then G.-,', when reindexed, is the same pair of adjacent code vectors.
as G.-,. On the other hand, if the constraint is gi= 1 Proof: From Theorem 1, if any two n-vectors of
(i* 1), then G,,-1', when reindexed, is the same as G.- weight m differ by a Hamming distance of greater than
except that the position i-I is complemented. If, how- two, they cannot be adjacent on the distance-2 chain
ever, an arbitrary number of n-k positions are con- defined by the ordering of G. on the set of (8 ) n-vectors
strained, then by applying the above argument re- of weight m.
peatedly, one arrives at the following assertion: Gk',
when reindexed, is the same as Gk except that each posi- III. ALGORITHMS
tion immediately after (i.e., with a smaller index) a run In Section II we derived a solution to our problem,
of constrained positions should be complemented if this the distance-2 cyclic chaining of constant-weight codes.
run has an odd number of positions constrained to one. We shall next investigate methods of determinating the
One further observes that, since Gk' can be obtained subsequent constant-weight code vectors on a Gray code
from Gk by complementing at some bit positions, the circuit Gn given a starting code vector. One can obvi-
following basic property of a conventional Gray code ously generate the complete Gn and extract from it the
must be-retained in Gk': For any k'<k, the bit patterns code vectors with a desired weight, starting from the
of the highest k' positions in Gk' can be obtained from a given code. However, this straightforward method can
Gk' code (by further constraining Gk' -the lowest k-k' be shown to be rather inefficient as n becomes large.
positions) with each code vector repeated consecutively This is because we are interested in only (,) code vectors
2k-' times. We are now ready to prove the following out of 2n possible ones, and the ratio of (n) to 2" tends to
theorems. zero as n grows indefinitely.
Tkeorem 1: If x and y are two n-vectors of weight m, An immediate improvement can be obtained by ob-
and if the Hamming distance between x and y is greater serving that constant weightness in g implies that

Authorized licensed use limited to: POLO BIBLIOTECARIO DI INGEGNERIA. Downloaded on May 06,2021 at 07:45:46 UTC from IEEE Xplore. Restrictions apply.
178 IEEE TRANSACTIONS ON COMPUTERS, FEBRUARY 1973

Fig. 1. The tree of ending patterns for binary vectors corresponding to constant-weight Gray codes.

bi Ij=1 gj (mod 2) equals a constant (i.e., either 1 or 0). described above. We shall develop such a procedure in
One therefore needs to exhaust no more than 2n-1 code the following section.
vectors. Since this only reduces the amount of computa- If the set of constant weight Gray codes is trans-
tion by a factor of 2, it does not change the asymptotic formed into the corresponding set of binary codes, the
behavior of the procedure for large n. Substantial im- constraint of constant weightness becomes a constraint
provements can be obtained as a result of the following of constant number of changes between 0 and 1, and
theorem. vice versa (assuming the vector is augmented by a run
Theorem 3: Given x as an n-vector of weight m, let y of 0's at its most significant end). Given a binary code
be the next n-vector of weight m on the Gray code G, vector of m 1-0, 0-1 changes, our problem is to find
then there exists a uniquej such that VG(X) - VG(Y) 2 another vector with the same number of changes such
mod 2 , where .<j<max [m, n-m]. that the increment (mod 2") in the corresponding binary
The validity of this theorem will become evident in a value is the smallest. To do this, let us examine Case 1
subsequent analysis. As a result of Theorem 3, one can corresponding to the top branch of the tree shown in
envision the following algorithm to determine the sub- Fig. 1. In this case m is even and the binary vector has
sequent constant-weight code vectors. an ending pattern in its least significant position con-
Step 1: For the given weight m code vector g0, find its sisting of exactly k(k22) O's:
value VG(go). x ... x 1 0 -0,
Step 2: Add successively 2i, j = 1, 2, * , max [im, k O'S, -(k > 2)
n-rm] to V0(go) and find the smallest j =j' that results
in a Gray code vector of weight m. where x's indicate DON'T CARE bits. It is not difficult to
Step 3: Add 2P' to V0(g0) and from the sum (mod 2X) see that when we increase successively by 1 the value of
find the corresponding Gray vector gi. this vector, the first resultant binary vector to satisfy
Step 4: With go = gi, repeat Steps 1-3 until all (n ) vec- the constraint of constant 1-0, 0-1 change must have
tors are obtained. the following ending:
A more desirable algorithm would be based on a direct (k1 - 10
determination of j' without the trial and test procedure (kE-1)0'S.

Authorized licensed use limited to: POLO BIBLIOTECARIO DI INGEGNERIA. Downloaded on May 06,2021 at 07:45:46 UTC from IEEE Xplore. Restrictions apply.
TANG AND LIU: DISTANCE-2 CYCLIC CHAINING 179

TABLE I If the ending is

VARIOUS ENDING PATTERNS OF b (THEOREM 3)
x.. x 1 1 0... 0 1 1*.*1
Case Ending pattern of a
given binory vector
Ending pattern or the
next binory vector
Increment j'(>1)O's j('=odd)l's
*.x..xlO ... 0
_ 's, knl
..... x,l10 ...°
(kn-lO's
k.-. then pi =j+ 1 and P2 =j+j'+ 2.
... x 0010 .... 10 x ...x10010 ..... 10 k-I
If the ending is
(k/2) (lO)s, k = even (k/2) -1 (lO)s
1 0 ... 0 1 1* I1
x... x
101 ... 1 1 0 ... 1 0 x
... x 1 1 0 ... 0 1 0 ... 1 0
B3 k' I 's (k/2) (lO)s, kI even k' 0's (k/2) (lO)s 2 allO's j(=m-1)1's
E
4
x ..x 1 ... 1 1 0 ... I
n-----.-' x ..x O1 0 ... 0"----'
I0 . I 2 Ik- 1

1 110 ...O
k'Il's (k/2)(1O)s, k=even
0
(k'+2)0's (k/2)-l (lO)s
.10 ...10
then pi=j+I and p2=n.
(n- k) l's (k/2)(IO)s, k= m (n-k) O's (k/2)(10)s 2 (mad 2 Rule 2: m is odd.
6
x ,xlOl ... I
',-
x...xl10-... 01
2
a) If the ending is
k 1 's, ka2 (k-I1)l's
xOOl001 10I 1
xv. x 1 1 0 0 ...0
x x ... ... k
7_ 2
c
k tI's, kz>2 (k+l) 1l's j 0's
8 < ....~'2k-2
(k/2) (01)s, k =even (k/2) -1 (01)s then pi=1 and P2=j+ 2.
c X .. xlI Ol ... 101 . 01 X ...Xil ....l 101 .01.. Is
If the ending is
I k' I's (k/2) (01)s, k-even k?2 ('-l)0's (0/2)(01)s
o 10 x x00 ... 101,.01 ... nX lO...
0's
0,10
0 . 01 e x ..x 0 1 0 0 .0
k' l's (k/2)(01)s, k=even k>2 k' (k/2)(01)s
_ I I 01 .01 010 1 01...01 01 j O's
__'2k+__mo__2_
...
11 w
(n- k) I1'5 (k/2) (01)s k - m -1 (n-k-l)O's (k/2)(01)s to
then pi =j+ 1, P2-j+2.
b) If the ending is
In this case the increment of the binary values equals to
2k-1. This together with increments of other cases are x . ..x 0 1 1*.1
summarized in Table I. Since the cases considered in j= odd) l's
Table I are exhaustive (as depicted in Fig. 1), the valid-
ity of Theorem 3 is established. Moreover, an algo- then pi=max (1, j-1), P2=j+I.
rithmic implementation can be readily obtained. If the ending is
An analogous analysis can be carried out directly on x ...x 1 0 .. 0 1 1 ... 1 I
Gray code vectors. As a result, the two positions to be j'(>1)0's j(n= even)l's
complemented to chain a Gray code vector to the next
one can be directly determined by its ending pattern. then pl=j and P2=j+j'+2.
This is summarized in the following theorem. If the ending is
Theorem 4: Given a Gray code vector g = (gn, gn-i, x- I
x 1 1 0.. 0 1** 1 1
1
. gi)
gi of weight m, the next code vector of weight m
on the Gray code circuit can be obtained by comple- j'(> 1)O's j(= even) l's
menting two positions, Pi, P2 (Pl, P2= 1, 2, * *, n) in 4 then pi=j+ 1, P2=j+ji +2.
according to the following rules. If the vector is
Rule 1: m is even.
a) If the ending of 4 is 1 0 0 1 1.**1
x x 1 0 .-0 allO's j(=m-1)l's
O's then pi=j+1, p2=n.
then Pi=j and P2=j+1. Clearly, Theorem 4 can be readily translated into an
b) If the ending is algorithm for distance-2 cyclic chaining of constant-
weight codes.
x *xO 1 1**. 1 1 To demonstrate how this algorithm works, let us con-
j(= even) l's sider the following example. Suppose n = 7 and m =4.
The complete set of (7) = 35 code vectors generated by a
then pi=max (1,j-1) and p2=j+1l program implementing this algorithm is shown in Fig. 2.
If the ending is Notice the distance-2 cyclic chaining of these vectors.
x...x 0 1 0...0 1 1 ... 1 Let us take the 5th code vector (O 0 1 0 1 1 1) from
the list. Since m = 4 and the ending pattern is a run of 3
I'(.>)O's j(=odd)l's (odd) l's, this falls into the class described by the second
then pi=j and p2=i+i'+2. ending pattern considered in Rule lb) of Theorem 4.

Authorized licensed use limited to: POLO BIBLIOTECARIO DI INGEGNERIA. Downloaded on May 06,2021 at 07:45:46 UTC from IEEE Xplore. Restrictions apply.
 ISO IEEE TRANSACTIONS ON COMPUTERS, FEBRUARY 1973

vG(g) b R n. The algorithm based on Theorem 4 has the additional

10 0001010 0001111
advantage of almost constant computation time per
18 0010010 0 0110 11 code word for all n-vectors of weight m.
20 0010100 0 011110 In a recent note [9], a different algorithm was pre-
22 0010110 0 011101 sented to exhaust (Q) combinations. Using that algo-
26 0 011010 00101 11 rithm one can obtain a distance-2 chaining of a complete
34 0 100010 01100 11 set of constant weight codes. A cyclic chaining, how-
36 0100100 0 1101 10 ever, is not always possible. Moreover, the algorithm
38 0 100110 0 1101 01 starts with a fixed-code vector of (0 0 . . . 0 1 1 . * * 1).
40 0 101000 01111 00
42 0101100 0 1110 10 REFERENCES
44 0101110 0 1110 01
[11 F. Gray, 'Pulse code communication," U. S. Patent 2 632 058,
50 0 110010 01010 11 Mar. 17, 1953.
52 0110100 0 1011 10 [2] I. Flores, "Reflected number systems," IRE Trans. Electron.
54 0110110 01011 01
Comput., vol. EC-5, pp. 79-82, June 1956.
[3] E. N. Gilbert, "Gray codes and paths on the n-cube," Bell Syst.
58 0 111010 0 1001 11 Tech. J., vol. 37, pp. 815-826, 1958.
66 1000010 1 1000 11 [4] W. H. Kautz, "Unit-distance error-checking codes," IRE Trans.
Electron. Comput. (Corresp.), vol. EC-7, pp. 179-180, 1958.
68 1000100 11001 10 [5] R. T. Chien, C. V. Freiman, and D. T. Tang, "Error correction
70 1000110 1 100101 and circuits on the n-cube," in Proc. 2nd Annu. Allerton Conf.
72 1001000 1 101 00
Circuit and Syst. Theory, 1964, pp. 899-912.
[6] R. C. Singleton, "Generalized snake-in-the-box codes,' IEEE
76 1001100 11010 10 Trans. Electron. Comput., vol. EC-15, pp. 596-602, Aug. 1966.
78 1001110 1 1010 01 [71 C. V. Freiman, "Optimal error detection codes for completely
80 1 010000 11110 00 asymmetric binary channels," Inform. Contr., vol. 5, pp. 64-71,
1962.
88 1 011000 1 110100 [8] W. H. Kautz, "A readily implemented single-error-correcting
92 1 011100 1 1100 10 unit-distance counting code," IEEE Trans. Comput. (Short
Notes), vol. C-19, pp. 972-975, Oct. 1970.
94 1 011110 1 1100 01 [9] P. J. Chase, "Combinations of M out of N objects," Commun.
98 1100010 1 0100 11 Ass. Comput. Mach., p. 368, June 1970.
100 1100100 1010110
1 02 1100110 100 1 01 *.-
104 1101000 1OiIOO
108 1101100 1 0110 10 Donald T. Tang (M'65) was born in Fukien,
110 1101110 1011001 China, on May 9, 1932. He received the B.S.
1 14 1 110010 1 0010 11 degree in electrical engineering from Taiwan
116 1110100 1001110 Uniiversity, Taipei, Taiwan, in 1953 and the
Ph.D. degree from the University of Illinois,
118 1110110 1001101 Urbana, in 1960.
1 22 1111010 1000111 Since 1960 he has been a member of the
Fig. 2. The set of 35 binary vectors of length 7 and weight 4. Research Staff at the IBM T. J. Watson Re-
Underlined characters are boldface in text. search. Center, Yorktown Heights, N. Y.
From 1965-1966 he was a Visiting Professor
at Taiwan University, on leave of absence
from IBM. His research interests include network flows, error-
Here we have j=3, and j'=1, hence Pi=j=3 and control coding, magnetic recording, computer algorithms, and com-
munications system theory.
P2=i+j'+2=6. Upon complementing the bits in posi- Dr. Tang is a member of Eta Kappa Nu and Sigma Xi.
tions 3 and 6 in (0 0 1 0 1 1 1) we obtain (0 1 1 0 0 1 1)
which is seen to be the sixth code vector in the list.

CONCLUDING REMARKS C. N. Liu (M'67) was born in Nanking, China,

on January 2, 1935. He received the B.S.E.E.
The analysis presented in this paper leads to several degree from the South Dakota School of
algorithms for distance-2 cyclic chaining of constant- Mines and Technology, Rapid City, in 1956,
weight codes, all of which are based upon some intrinsic and the M.S. and Ph.D. degrees in electrical
engineering from the University of Illinois,
properties of Gray codes. These algorithms have been Urbana, in 1957 and 1961, respectively.
implemented in APL programs. Experimental runs of In 1957 he joined the IBM Research Divi-
these programs indicated that as n becomes large (e.g., sion. From 1958 to 1961 he was a Research
Assistant in the Digital Computer Labora-
x > 20), the algorithms based on Table I and Theorem 4 tory, University of Illinois, Urbana, where he
become more efficient than others. The average com- worked on l1iigh-speed computer design projects. Since 1961 he has
putation times per code word for the algorithms based been with the IBM T. J. Watson Research Center, Yorktown
Heights, N. Y., where he has worked on character recognition and
on Table I and Theorem 4 were found to be not sig- small computer systems. In 1968 he was a Visiting Associate Profes-
nificantly different from each other. Furthermore, the sor at Purdue University, on leave of absence from IBM, and in 1972
computation time per code word in both cases was ob- he was a Visiting Research Professor at the Institute of Mathematics,
Academia Sinica, Taiwan, also on leave from IBM.
served to be relatively insensitive to the values of m and Dr. Liu is a member of the Association for Computing Machinery.

Authorized licensed use limited to: POLO BIBLIOTECARIO DI INGEGNERIA. Downloaded on May 06,2021 at 07:45:46 UTC from IEEE Xplore. Restrictions apply.