Techniques to Construct

IEEE TRANSACTIONS ON COMPUTERS, VOL. C-25, NO. 9, SEPTEMBER 1976

945

Techniques to Construct (2,1) Separating Systems from Linear Error-Correcting Codes DHIRAJ K. PRADHAN, MEMBER, IEEE, AND SUDHAKAR M. REDDY, MEMBER, IEEE Abstract-(2,1) separating systems have earlier been shown to be useful in designing asynchronous sequential circuits [6]. In this paper, techniques to derive (2,1) separating systems from linear error-correcting codes are given. It is shown that the proposed techniques yield better (2,1) separating systems than earlier klown techniques. Index Terms-Asynchronous circuits, linear codes, separating systems, (2,1) separating systems, universal state assignments.

Example 1: Let X = 1101, Y = 1011. Then the transition path from X to Y is {1001, 1011, 1101, 1111} (notice that X and Y differ in the second and the third positions). Definition 2: A is called a (2,1) separating system if and only if for every X,Y,Z ( A and Z 5 X and Z $ Y, Z does not exist in the transition path from X to Y. Notation: Let X, Y E A. X o Y (X (@ Y) be the n-tuple obtained by taking bit by bit AND (EXCLUSIVE OR) of corresponding bits in X and Y. X is the n-tuple obtained by taking bit by bit complement of bits in X, 0 is the allzeros n-tuple, I is the all-ones n-tuple. Definition 3: A is a linear binary code if for every X, Y E A (X V Y) also exists in A. Definition 4: The Hamming distance between X, Y C A [written d(X,Y)] is the number of corresponding positions in which X and Y differ [note that d(X, Y) = number of ones in (X a) Y)]. Definition 5: Weight of an n-tuple X [written wht (X)]

I. INTRODUCTION IN this paper we study the problem of constructing state assignments for asynchronous sequential machines in a new framework. Through this we exhibit techniques for exploiting algebraic structure of linear codes in constructing (2,1) separating systems whose usefulness as universal state assignments for asynchronous sequential machines has already been shown [5]-[7]. Known codes have been successfully used by previous researchers; Huffman's one shot assignment [10], Liu's single transition is the number of ones in X. Note: d(X, Y) = wht (X ED Y). time assignment [2], and more recently by Kashef and Definition 6: The minimum distance (written dmin) of McGhee [8] in deriving multiple transition time assignA, is the ments. min d(X,Y)). This paper has three main sections. In Section II we X,YEA discuss some background material. In Section III we forX$Y mulate the problem of constructing (2,1) separating sysDefinition 7: The maximum distance (written dm:) tems [5] in coding theory framework and derive certain of A, is the necessary and sufficient conditions. In Section IV we max (d(X,Y)). present techniques to use linear codes in constructing (2,1) X, YCA X#Y separating systems. These techniques yield better (2,1) separating systems than earlier known techniques [5]. The III. NECESSARY AND SUFFICIENT CONDITIONS state assignments derived may find practical use in designing asynchronous machines with a large number of In this section two necessary and sufficient conditions states, for example in realizations using read-only memo- on (2,1) separating systems are given. These conditions are ries [11]. used in deriving the (2,1) separating systems of Section III. Lemma 1: A is a (2,1) separating system if and only if for II. NOTATION every X,Y,Z E A, X 5 Z and Y p Z,X and Y have the Let A be a set of binary ordered n-tuples and let n- same value, say e, in some position, say j, and Z has e in position j. tuples X, Y, and Z E A. Proof: Immediate consequence of Definition 2. Definition 1: The transition path from X to Y is the set Lemma 2: A is a (2,1) separating system if and only if for of all ordered n-tuples obtained by arbitrarily specifying the entries in the positions in which X and Y differ. everyX,YZ E A, X # Zand Y s Z, (X @ Z) o (YE Z) 0. Proof: From Lemma 1, A is a (2,1) separating system Manuscript received March 5, 1975; revised October 28, 1975. This if and only if X differs from Z in the jth position and siwork was supported by the NRC under Grant A8981 and the NSF under multaneously Y differs from Z in the jth position, for some Grant ENG72-04142 A02. D. K. Pradhan is with the Department of Computer Science, University j,1 S j < n. Therefore, (X ED Z) and (Y @ Z) have a one in of Regina, Regina, Sask., Canada. S. M. Reddy is with the Division of Information Engineering, Uni- position j (note that e @ e = 1) and (X CD Z) o (Y ED Z) has versity of Iowa, Iowa City, IA 52242. a one in the jth position; and hence, the lemma. Q.E.D.

IEEE TRANSACTIONS ON COMPUTERS, SEPTEMBER 1976

946

IV. (2,1) SEPARATING SYSTEMS FROM LINEAR CODES In this section we derive a necessary and sufficient condition and also several sufficient conditions for a linear code to be a (2,1) separating system. Theorem 1: A linear code C is a (2,1) separating system if and only if for any X,Y E C, X 0 and Y O, X o Y # 0.

Proof-Necessity: Assume that C is a (2,1) separating system,X,YC C,X 0, Ys OandXo Y= 0.LetXC Y = W. Since C is a linear code W E C. Furthermore, since X 0 and Y 5 0 we have W X and W # Y. By assumption X o Y = O and hence (Y (X Y)) o ((X eD Y) X) = X o Y = 0 (note that Z D Z = 0 for any binary n-tuple Z). Therefore, (Y e W) o (X W) =0 and from Lemma 2 C is not a (2,1) separating system. Since this contradicts our hypothesis we have X o Y 0 if C is a (2,1) separating system. Sufficiency: Assume that for every U, V E C, Uo V 0, if U 0 and V 0. Let X and Z be arbitrary members of C such that X P Z and Y Z. Then (X Z) 0,(YeDZ) 0,(X eZ) C C, and (YeZ) C C. Butby assumnption (X D Z) o (Y Z) 0. Hence, by Lemma 2, Q.E.D. C is a (2,1) separating system. The following lemma can be readily proved. Lemma 3: Given any two binary n-tuples X and Y, X Y) = wht (X) + wht (Y). o Y = O if and only if wht (X Lemma 4: If C is a linear code then C contains n-tuples, say X and Y, with the property wht(X) = dmin and wht(Y) = dmax and the weight of every nonzero member of C is less than or equal to dmax and greater than or equal to dmin. Proof: For every pair of n-tuples U, V E C (U V) E C (since C is a linear code). But d (U, V) = wht(U eD V). Hence, if U,V E C, then an n-tuple W = (U eD V) exists in C such that wht(W) = d(U,V). If dmin (dmax) is the minimum (maximum) distance of C, then there exists a pair of n-tuples, say P and Q (P' and Q'), such that d(P,Q) = dmin (d(P',Q') = dmax). Let P e3 Q = X (P' Q' = Y), = C (Y C C). But wht(X) wht(P e Q) = where X d(P,Q) = dmin (wht(Y) = wht(P' e3 Q') = d(P',Q') = dmax). Since C is a linear code, for any Z C C, Z ED Z = 0 is in C. Therefore, if Z 0 C C, then dmin < d(Z,0) = Q.E.D. wht (Z) < dmax. Theorem 2: A linear binary code C for which dmax < 2dmin is a (2,1) separating system. Proof: To prove Theorem 2, from Theorem 1, it is sufficient to show that for every X, Y C C, X 0 and Y 0. Assume to the contrary, i.e., for 0, implies X o Y O and Y $O X o Y = O and dmax < some X,Y E C, X 2dmin. Since X o Y = 0, we have, from Lemma 3, wht(X @ Y) = wht(X) + wht(Y). But from Lemma 4 the weight of every nonzero code word in a linear code is greater than Y) = wht(X) + or equal to dmin. Therefore, wht(X > wht(Y) 2dmin. But (X Y) E C (since C is a linear

The following properties of linear codes are needed to derive the results given later in this section. Good references for this material are [1] and [9]. Property 1: If C is a linear code then C contains 0 and has exactly 2k members for some k > 0. Property 2: If C is a linear code with 2k n-tuples then there exists a generator matrix Gc with k linearly independent rows and n columns such that every code word is equal to a linear combination of the rows of Gc. Conversely, every k X n binary matrix Gc with k linearly independent rows generates a linear code C with 2k elements. C is obtained by taking all possible linear combinations of the rows of Gc. Property 3: If C is a linear code with the all ones n-tuple Iin it, then a generator matrix of C, Gc, can be found such that

Gc =

O =1[11...1] *: G(/

where Gc' is the generator matrix for a linear code C' with 2K-1 (n -1)-tuples. Definition 8: If C is a linear code with 2k n-tuples, then C is called an (n,k) code. Definition 9: An (n,k) linear code C is said to be in systematic or separable form if C = {X:X = IXPX where X C C, Ix is a k-tuple, Px is an (n - k)-tuple and all the 2k binary k -tuples appear in lx portion of the code words}. If C is in systematic form the Ix portion of the code word X is referred to as the information positions and Px portion is referred to as the redundant or parity positions of X. It is known that all linear codes can be put into systematic form by appropriate permutations of the code words [1]. Unless otherwise specified, throughout this paper we assume that all linear codes are in systematic form. Definition 10: If C is an (n,k) code containing I, then the code C' corresponding to Gc' given in P3 is called the shortened code derived from C. Note that C' is an (n - 1, k - 1) code. Lemma 5: Let C be an (n,k) code containing the all ones n-tuple I, C' be the shortened code obtained from C, d1 be the dmin of C, and d2 the dmin of C'. C' has the following properties: d2 > di dmax of C' is less than or equal to n - dl. Proof: Since GcC is obtained by deleting the first column and the first row of Gc every member of C' can be made into a member of C by appending a 0 on the left, i.e., C'}. < code) and hence from Lemma 4 wht (X Y) dmax. OX is in C if X E C'. Let C" =-Y:Y = AOX, X = = Y X in C", OQ OP and C" C. For every > C Clearly, Therefore, dmx 2dmin which contradicts the hypothesis. = = dmin Therefore, d d (P, Q). wht wht and (Y,X) (P) (Y) Q.E.D.

947

PRADHAN AND REDDY: (2,1) SEPARATING SYSTEMS

and dmax of C" are equal to the dmin and dmax, of C', respectively. Since C" C C, dmin of C" is greater than or equal to d1 and hence d2 the dmin of C' is greater than oir equal to d1. Assume that dmax of C' is greater than n - d1. From Lemma 4 there exists an (n -1)-tuple, say X, in C' such that wht(X) > n - d1. Let Y = OX. But Y E C" and hence Y E C and since I C C, (Y a 1) = Y is in C. But wht(Y) = n -wht(Y) = n-wht(OX) = n -wht(X) < n - (n - di) = d1. Therefore, Y E C and wht(Y) < d1, contradicting Lemma 4. Therefore, wht(X) < (n - d1) and hence dma: of C' is less than or equal to (n - dmin)Q.E.D. Theorem 4: If C is an (n,k) linear code containing Iand d1, the dmin of C, is greater than or equal to (n + 1)/3, then the shortened code C' derived from C is a (2,1) separating system. Proof: From Lemma 5 we have that dmax of C' is less than or equal to n - di < n - (n + 1)/3 = (2(n - 1))/3. But, from Lemma 5, dmin of C' is greater than or equal to d1 and hence dmax of C' is less than or equal to 2dmin > (2(n + 1))/3. Therefore, from Theorem 2, C is a (2,1) separating Q.E.D. system. Sometimes the length of the code words in C' can be further reduced without reducing the number of words in C' (this process is called puncturing [9]). Definition 11: Let C be an (n,k) linear code. If C" is an (n - t,k) linear code obtained from C by deleting t positions in each element of C, then C" is called a punctured code obtained from C. It is known that all linear (n,k) codes can be punctured by deleting t of the (n - k) redundant or parity positions. The following lemma is a direct consequence of Definition 10. Lemma 6: Let C be an (n,k) linear code with dmin = d, and dma. = d2. If C" is an (n - t,k) punctured code derived from C, then the dmin of C" is greater than or equal to d, - t and dmax of C" is less than or equal to d2. Next we give examples of how to derive (2,1) separating systems from some well-known linear codes called BoseChaudhuri-Hoquenghem (BCH) codes (extensive litera-' ture on these codes is given in [1] and [9]). We will need only the parameters of these codes and Lemma 7, which is given later. We will not attempt to prove Lemma 7 here as it would require some properties of finite fields and BCH codes. First we give a simple example to illustrate the use of Theorem 4 and Lemma 6 in deriving (2,1) separating systems. If A is a (2,1) separating system with r n-tuples, then A can be used for state assignment of an asynchronous flow table with up to r states and n state variables will be required for this assignment [5]-[7], [10]. Therefore, one can say that the smaller the value of n for given r, the better the separating system. In deriving the (2,1) separating systems of Example 2 and Table I, we will attempt to minimize n by using Theorems 2 and 4, Lemma 6, the properties of linear codes, and the results known on puncturing [9]. Example 2: Let C be the (15,5) BCH code [1] with minimum distance 7. It is known that C contains L

Therefore, by Theorem 4 the shortened (14,4) code C' derived from C is a (2,1) separating system. We can do better by puncturing C'. Since C' has ten parity or redundant bits we can delete two of them obtaining a (12,4) code C" with minimum distance at least equal to 5 and maximum distance at most 8. Therefore, by Theorem 2, C" is a (2,1) separating system. A class of codes called primitive BCH codes are well known [1], [9]. The lengths of these codes are of the form (2m - 1), m > 2. Lemma 7: All primitive BCH codes contain I. Thus, primitive BCH codes whose dmin is greater than or equal to (n + 1)/3 are suitable for deriving (2,1) separating systems. By using the table of primitive BCH codes in [1] we derive Table I. In deriving Table I we have used the concepts of shortening and puncturing. Next we give a method for constructing (2,1) separating systems from known (2,1) separating systems. Here we use the concept of product codes. Definition 12: Let C1 and C2 be (n1,k1) and (n2,k2) linear codes, respectively, and G1 and G2 be their respective generator matrices. Then code C, called the product code (written C = Cl X C2) is defined by the generator matrix Gc obtained as follows. Every 1 in G1 is replaced by G2 and every 0 in G1 replaced by a k2 X n2 matrix of all zeros. Note that Gc is a (k, X K2) (ni X n2) matrix and C is a (n1 * n2, ki * k2) code. The following example will illustrate the product codes. Example 3: Let G=

1 0 1

=

and I 0 01 G2= ° 1 0 1.

Then'

LO

0 1

1J

1001 0000 1001 0101 0000 0101 00n 0000 0011 0000 1001 1001 0000 0101 0101 0000 0011 0011

Theorem 5: If two linear codes C1 and C2 are (2,1) separating systems, then C = C1 X C2 is also a (2,1) separating system.

Proof: From the construction of Gc it can be seen that every Xc in C can be viewed as being obtained by replacing 1 Gc is not in the systematic form and C is not a systematic code. But if desired, C can be put into systematic form by an appropriate permutation. To prove Theorem 5, we do not need C to be in systematic form.

948

IEEE TRANSACTIONS ON COMPUTERS, SEPTEMBER 1976

TABLE I

TABLE II Different Values of e and Corresponding n and k

(2,1) Separating Systems Derived from Primitive BCH Codes Selected BCH Code

Derived Codes (2,1) Separating Systems

k

dm;n

n

15

5

7

12

31

11

11

n

dMAY

dmin

4

8

5

10

20

11

k

30t *

63

16

23

60

15

40

21

127

29

43

126t

28

84

43

255

45

87

25*

44

168

85

Slt

75

340

171

120

680

341

511

76

171

1023

121

343

1020

Shortened and punctured codes t Shortened codes

l's in some code word, say Xc1, of C1 by code words of C2. Furthermore, Xc = 0 if and only if Xc, = 0. Let Xc and Yc be two nonzero code words of C and let Xc, and YC1 be the corresponding code words of C1 from which Xc and Yc are obtained as noted above. Clearly, Xc1 and YC1 are not equal to 0 and hence, from Theorem 2, xcl o Ycl $ 0. Therefore, Xcl and YC1 contain l's, in at least one corresponding position, say the jth position. Let Uj and Vj be the code words of C2 that were used to replace the l's in the jth position of Xc0 and YCi, respectively, to obtain Xc and YC. Clearly, Uj and Vj are not equal to 0 and hence, from Theorem 2, Uj o Vj $ 0 and hence Xc ° Yc 0. Therefore, from Theorem 2, C is a (2,1) separating system. Q.E.D. By iteratively applying, (i - 1) times, Theorem 5 to an (n,k) code which is a (2,1) separating system, we can obtain an (n ,ki) code that is also a (2,1) separating system. By expressing n in terms of k the parameters for the iteratively generated product codes can be expressed as (N,K) = (kfe,k') where e = log n/log k. The best known value of e, for a constructive technique to derive (2,1) separating systems, is given in [5] and is 1.59. The value of e for the separating systems derived by applying Theorem 5 to some of the separating systems is given in Table II. It can be noted that except for the second entry the value of e for the proposed separating systems is less than 1.59. Earlier it has been shown that there exist (2,1) separating systems with 2k members if n > 7.1k [5] (no constructive technique to obtain such (2,1) separating systems is known). It is shown in the Appendix that there are (n,k) lifiear codes that are also (2,1) separating systems if n > 14(k + 1). Therefore, for practical purposes one can concentrate on linear codes to obtain good (2,1) separating systems.

k

n

log log k

e

3

2

12

4

1.792

30

10

1.477 1.511

1.59

60

15

126

28

1.45

252

44

1.461

510

75

1.443

1021

120

1. 447

This is the code 1110, 101, 011, 0001. codes used are from Table I.

Rest of the

It is hoped that the relationships established between (2,1) separating systems and linear codes can be extended to (2,2) separating systems. It is further suggested that properties of linear codes which allow for better application of Theorems 1 and 2 merit further research.

APPENDIX Theorem 6: There exists (n,k) linear codes which are also (2,1) separating systems if n > 14(k + 1). Proof: The following auxiliary result can be proved by using arguments similar to the ones used to derive the well-known Varsharmov-Gilbert bound for block codes [1]. Details of the derivation are omitted. It is possible to construct (n,k) linear codes of length dmax < 2dmin if n-k >-1 + [0log2 E ()]

(where rx1 denotes the smallest integer greater than or equal to x). Thus, there exist linear codes of length n, which are also (2,1) separating systems, if n=

k+

n

n-3/3 n

1E 1092 c=O

+

.)+ 1.

(1)

I/

One has n-3/3 i=O

Inf

n-3/3( n)

i=O

n-i (n

i=2n+3/3 (

(n

i= 2n/3 (

2-2n/3

1-n/3

3

3

The above inequality follows from the known upper bound on the partial sum of binomial coefficients [1] given by

V. CONCLUSIONS In this paper we have given several techniques to derive (I < X-xp (1 -)-(l-x)p (2,1) separating systems from linear codes. By applying i=Tup Theorems 2-4 and Lemma 6, jointly, (2,1) separating systems with a wide range of parameters can be obtained. Thus we have

for X> 1/2.

949

PRADHAN AND REDDY: (2,1) SEPARATING SYSTEMS 1 n-3/3 -2,/3 ( 1 )-n/31 J log2 E7.4 (n)