Error correcting codes from quasi-Hadamard matrices
Abstract
Levenshtein described in [5] a method for constructing error correcting codes which meet the Plotkin bounds, provided suitable Ha- damard matrices exist. Uncertainty about the existence of Hadamard matrices on all orders multiple of 4 is a source of difficulties for the prac- tical application of this method. Here we extend the method to the case of quasi-Hadamard matrices. Since efficient algorithms for constructing quasi-Hadamard matrices are potentially available from the literature (e.g. [7]), good error correcting codes may be constructed in practise. We illustrate the method with some examples.
Full text
Error correcting co des from quasi-Hadamard matrices V. Alvarez, J.A. Armario, M.D. Frau, E. Martin, and A. Osuna ? Dpto. Matematica Aplicada I, Universidad de Sevilla, Avda. Reina Mercedes s/n 41012 Sevilla, Spain, f valvarez,armario,mdfrau,emartin,ao suna g @us.es Abstract. Levenshtein describ ed in [5] a metho d for constructing error correcting co des which meet the Plotkin bounds, provided suitable Hadamard matrices exist. Uncertainty about the existence of Hadamard matrices on all orders multiple of 4 is a source of diÆculties for the practical application of this method. Here we extend the method to the case of quasi-Hadamard matrices. Since eÆcient algorithms for constructing quasi-Hadamard matrices are potentially available from the literature (e.g. [7]), good error correcting co des maybe constructed in practise. We illustrate the method with some examples. Keywords: Error correcting co de, Hadamard matrix, Hadamard co de. 1 Intro duction One of the main goals in Coding Theory is the design of optimal error correcting co des. For given length n and minimum distance d ,theterm optimal means a co de whichconsistsofasetofcodewords as large as possible. For (not necessarily linear) binary co des ( n; M ; d ), Plotkin found out in [10] the following b ounds for the number M of co dewords: M 2 b d 2 d n c if d is even and d n< 2 d , (1) M 2 n if d is even and n =2 d , (2) M 2 b d +1 2 d +1 n c if d is o dd and d n< 2 d +1, (3) M 2 n +2 if d is o dd and n =2 d +1. (4) Levenshtein proved in [5] that the Plotkin b ounds are tight, in the sense that there exist binary co des which meet these bounds, provided that enough Hadamard matrices exist. Unfortunately, the Hadamard Conjecture ab out the ? All authors are partially supported by the PAICYT research pro ject FQM{296 from Junta de Andaluca (Spain).
existence of Hadamard matrices in all orders multiple of 4 remains still op en. Moreover, there are innite orders for which no Hadamard matrices have b een found. This means that, though theoretically correct, Levenshtein's method could not b e useful in practise. In the sequel a matrix for which the inner product of rows two by two is mostly zero is called a quasi-Hadamard matrix. We will use Levenshtein's metho d in this pap er to show that \good" error-correcting co des may be analogously constructed from quasi-Hadamard matrices. Here the term \go o d" refers to a co de formed from a signicantly large number of co de words, for given length and minimum distance. Wemust emphasize that quasi-Hadamard matrices may b e straightforwardly obtained in all orders multiple of 4, so that the asso ciated error-correcting codes may b e constructed in practise. We organize the paper as follows. In Section 2 weintro duce the notion of quasi-Hadamard matrices, and some pro cesses to construct them, which are available in the literature. Section 3 is devoted to explain how to construct go o d error-correcting codes from suitable quasi-Hadamard matrices. Some examples are discussed in Section 4. 2 Quasi-Hadamard matrices A Hadamard matrix H of order n is an n n matrix of +1's and 1's entries such that HH T = nI . That is, the inner pro duct of anytwo distinct rows of H is zero. Wenow generalize this notion. We dene a quasi-Hadamard matrix of order n as an n n matrix M of +1's and 1's entries such that the inner pro duct of rows twobytwo is mostly zero. Sometimes it is necessary to precise the largest number q of rows in M which are orthogonal one to each other. The larger q is, the closer M is from being a Hadamard matrix. In these circumstances, M is termed a quasi-Hadamard matrix of depth q . In some sense, a quasi-Hadamard matrix could b e thought as a Hadamard matrix in which some rows have been substituted, so that the Hadamard character is generally lost in turn. Constructing Hadamard matrices is hard. How ab out constructing quasi- Hadamard matrices? Wenow attend to another characterization of Hadamard matrices, in terms of cliques of graphs (that is, a collection of n vertices and n ( n 1) 2 edges of a graph G which form a complete subgraph K n of G ). Consider the graph G 4 t whose vertices are all the tuples of length 4 t formed from 2 t ones and 2 t minus ones, with the restriction that precisely t ones haveto app ear within the rst 2 t p ositions (byanalogy, precisely t ones app ear within the last 2 t p ositions). There is an edge b etween twovertices if andonlyif the inner pro duct of the corresp ondent tuples is zero. A Hadamard matrix of order 4 t exists if and only if G 4 t contains a clique of size 4 t 2. Furthermore, the vertices
of such a clique and the normalized rows ( 4 t z}| { 1 ;::: 1) and ( 2 t z }| { 1 ;:::; 1 ; 2 t z }| { 1 ;:::; 1)form a Hadamard matrix. This is a particular typ e of Hadamard Graph, as dened in [8, 9]. Unfortunately, the problem of nding out the maximum clique in a graph hasbeenproven to b e NP-hard [4]. Moreover, even its approximations within a constant factor are NP-hard [2, 3]. So one should exp ect that nding out Hadamard matrices from G ,oreven quasi-Hadamard matrices for large depths close to 4 t , are to b e hard problems. In fact, they are. Hop efully, heuristic methods for the maximum clique problem can b e found in the literature, which output pretty large cliques [7]. These metho ds can be used in turn to construct quasi-Hadamard matrices of large depth as well. 3 Quasi-Hadamard co des We rstly recall Levenshtein's metho d [5] for constructing optimal error correcting co des from suitable Hadamard matrices. Starting from a normalized (i.e. the rst row and column formed all of 1's) Hadamard matrix H of order 4 t , some co des (which are termed Hadamard codes) may b e constructed (see [6], for instance). More concretely, consider the matrix A 4 t related to H 4 t ,which consists in replacing the +1's by 0's and the 1's by 1's. Since the rows of H 4 t are orthogonal, any two rows of A 4 t agree in 2 t places and dier in 2 t places, and so have Hamming distance 2 t apart. In these circumstances, one may construct: 1. An (4 t 1 ; 4 t; 2 t ) co de, A 4 t , consisting of the rows of A 4 t with the rst column deleted. This is optimal for the Plotkin bound (1). 2. An (4 t 1 ; 8 t; 2 t 1) co de, B 4 t , consisting of A 4 t together with the complements of all its co dewords. This is optimal for the Plotkin b ound (4). 3. An (4 t; 8 t; 2 t ) co de, C 4 t , consisting of the rows of A 4 t and their complements. This is optimal for the Plotkin b ound (2). 4. An (4 t 2 ; 2 t; 2 t ) co de, D 4 t , formed from the co dewords in A 4 t whichbegin with 0, with the initial zero deleted. This is optimal for the Plotkin b ound (1). Furthermore, as explained in [6], for any d n < 2 d ,an optimal co de attending to the Plotkin b ound (1) may b e obtained from a suitable combination of co des of the abovetyp e. More concretely, given d even so that 2 d>n d , dene k = b d 2 d n c and a = d (2 k +1) n ( k +1) ; b = kn d (2 k 1) : Then a and b are nonnegativeintegers satisfying that n =(2 k 1) a +(2 k +1) b and d = ka +( k +1) b . Moreover, if n is even then so are a and b . Analogously, if n is o dd and k even, then b is even. Finally, if b oth of n and k are o dd, then a is even.
Dep ending on the parityof n and k , dene the co de C to b e: { If n is even, C = a 2 D 4 k b 2 D 4 k +4 . { If n is o dd and k even, C = a A 2 k b 2 D 4 k +4 . { If n and k are o dd, C = a 2 D 4 k b A 2 k +2 . Here denotes the following \summation" of codes. Supp ose that C 1 and C 2 are ( n 1 ;M 1 ;d 1 )and( n 2 ;M 2 ;d 2 ) co des, resp ectively. Assume, for instance, that M 2 M 1 .For nonnegativeintegers a; b ,thecode a C 1 b C 2 consists in pasting a copies of C 1 , side by side, followed by b copies of the co de obtained from C 2 by omitting the last M 2 M 1 co dewords. By construction, a C 1 + b C 2 is shown to be an ( an 1 + bn 2 ;M 1 ;d ) code, for d ad 1 + bd 2 . This way, the co de C dened ab ove meets the Plotkin b ound (1), since it has length n , minimum distance d , and contains 2 k =2 b d 2 d n c co dewords. Wenow extend Levenshtein's metho d for constructing optimal error correcting co des from Hadamard matrices to the case of quasi-Hadamard matrices. The co des so obtained are termed quasi-Hadamard co des. Consider a normalized quasi-Hadamard matrix M 4 t of order 4 t and depth q .We dene the matrix A 0 4 t related to M 4 t in the following way: select a q -set of rows of M 4 t which are orthogonal one to each other (notice that there is no larger set with this prop erty, since q is the depth of M 4 t ), and replace the +1's by 0's and the 1's by 1's. Theorem 1. In the circumstances above, the fol lowing quasi-Hadamard codes may beconstructed: 1. An (4 t 1 ;q; 2 t ) code, A 0 4 t ,consisting of the rows of A 0 4 t with the rst column deleted. 2. An (4 t 1 ; 2 q; 2 t 1) code, B 0 4 t ,consisting of A 0 4 t together with the complements of al l its codewords. 3. An (4 t; 2 q; 2 t ) code, C 0 4 t ,consisting of the rows of A 0 4 t and their complements. 4. An (4 t 2 ;h; 2 t ) code, D 0 4 t ,formedfrom the h codewords in A 0 4 t which begin with 0 , with the initial zero deleted (we only know that h q ). Pro of. It is a straightforward extension of the case of usual Hadamard codes coming from Hadamard matrices, since: { A 0 4 t consists of q rows. { Anytworows of A 0 4 t agree in 2 t places and dier in 2 t places (since they are pairwise orthogonal), and so have Hamming distance 2 t apart. The result follows. ut
Remark 1. Obviously, the closer q is from 4 t , the better co des A 0 4 t , B 0 4 t , C 0 4 t and D 0 4 t are. In the sense that the number of codewords is very close to the optimal value indicated in the Plotkin b ound. Theorem 2. For d evensothat 2 d>n d , dene k = b d 2 d n c and a = d (2 k +1) n ( k +1) ; b = kn d (2 k 1) : as before. A good error correcting code C 0 of length n and minimum distance d may be obtained, from suitable quasi-Hadamard matrices. More concretely, depending on the parity of n and k , dene the code C 0 to be: { If n is even, C 0 = a 2 D 0 4 k b 2 D 0 4 k +4 . { If n is odd and k even, C 0 = a A 0 2 k b 2 D 0 4 k +4 . { If n and k areodd, C 0 = a 2 D 0 4 k b A 0 2 k +2 . Pro of. From Levenshtein's method [5] describ ed b efore, it is readily checked that C 0 consists of co dewords of length n .Furthermore: { If n is even, select a normalized quasi-Hadamard matrix 1 M 4 k of order 4 k and depth q 1 , and a normalized quasi-Hadamard matrix 2 M 4 k +4 of order 4 k +4 and depth q 2 . Denote i A 0 a q i -set of pairwise orthogonal rows in i M with their rst entry dropp ed, and where the +1's and the 1's have b een replaced by 0's and 1's, resp ectively. Denote i D 0 the h i -set of rows in i A 0 whichbegin with 0, for 0 h i q i . In these circumstances, C 0 = a 2 ( 1 D 0 4 k ) b 2 ( 2 D 0 4 k +4 ) consists in a ( n; min f h 1 ;h 2 g ;d )-co de. { If n is o dd and k even, select a normalized quasi-Hadamard matrix 1 M 2 k of order 2 k and depth q 1 , and a normalized quasi-Hadamard matrix 2 M 4 k +4 of order 4 k +4 and depth q 2 . Denote i A 0 a q i -set of pairwise orthogonal rows in i M with their rst entry dropped, and where the +1's and the 1's have been replaced by 0's and 1's, resp ectively. Denote 2 D 0 the h 2 -set of rows in 2 A 0 whichb egin with 0, for 0 h 2 q 2 .Inthese circumstances, C 0 = a ( 1 A 0 2 k ) b 2 ( 2 D 0 4 k +4 ) consists in a ( n; min f q 1 ;h 2 g ;d )-co de. { If n and k are odd, select a normalized quasi-Hadamard matrix 1 M 4 k of order 4 k and depth q 1 , and a normalized quasi-Hadamard matrix 2 M 2 k +2 of order 2 k +2 and depth q 2 . Denote i A 0 a q i -set of pairwise orthogonal rows in i M with their rst entry dropped, and where the +1's and the 1's have been replaced by 0's and 1's, resp ectively. Denote 1 D 0 the h 1 -set of rows in 1 A 0 whichb egin with 0, for 0 h 1 q 1 .Inthese circumstances, C 0 = a 2 ( 1 D 0 4 k ) b ( 2 A 0 2 k +2 ) consists in a ( n; min f h 1 ;q 2 g ;d )-co de. The \go o dness" of the co de C 0 dep ends on the choices of q i and h i ,sothat the number of codewords is not far from the Plotkin b ound (1). ut
4 Examples The examples below illustrate that suitable quasi-Hadamard matrices giveraise to go o d error correcting co des, even optimal ones. In the sequel we write \ " instead of \ 1" for simplicity. 4.1 Example 1: an optimal quasi-Hadamard co de. Consider the Hadamard matrices H 8 = 0 B B B B B B B B B B @ 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 C C C C C C C C C C A ; H 12 = 0 B B B B B B B B B B B B B B B B B B @ 111111111111 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 111 1 1 1 111 1 1 1 111 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 C C C C C C C C C C C C C C C C C C A As it is shown in [6], Levenshtein's metho d provide a (27 ; 6 ; 16) Hadamard co de C from H 8 and H 12 . Assuming the notation of the precedent section, this co de is constructed as the summation 2 D 12 A 8 ,sothat C = 0 B B B B B B @ 0000000000000 0 00 0 0 00 0000000 1101000111110 1 00 0 1 11 1001011 1110110100111 0 11 0 1 00 1100101 0111011010011 1 01 1 0 10 1110010 0011101101001 1 10 1 1 01 1011100 1000111011100 0 11 1 0 11 0111001 1 C C C C C C A Taking into account Theorem 2, the same optimal co de C may b e obtained as the summation 2( 1 D 0 12 ) ( 2 A 0 8 ) from the following quasi-Hadamard matrices: { A quasi-Hadamard matrix 1 M 8 of order 8 and depth 6, which consists in randomly substituting the last tworows of H 8 . { A quasi-Hadamard matrix 12 M 12 of order 12 and depth 6, which consists in randomly substituting those rows of H 12 which begin with (1 ::: ). ut
4.2 Example 2: a go o d (non optimal) quasi-Hadamard co de. The section \Finding out a liar" in ([1], chap. 17) has provided inspiration for this example. Supp ose that someone thinks of a number between 1 and 10, and that you are supp osed to guess whichnumber it is. The rules of the game let you to ask 8 questions (with \yes" or \no" answers), and no more than one lie is allowed. In order to win, it suÆces to get a code capable of correcting up to 1 error, formed from at least 10 co dewords (one for every numb er in the given range). Writing 1 for \yes" and 0 for \no", nowcho ose the questions so that the binary tuple that the answers generates in each case coincides with the corresp onding co deword. This requires that the length of the co de should coincide with the number of questions. Summing up, you need a ( n; M ; d )co de so that n =8, M 10 and d allows to correct at least 1 error. Your elementary background on the Theory of Codes indicates that in order to correct e errors you need to use aco de of minimum distance d suchthat b d 1 2 c e .Since e =1, you need d 3. Assume that d =4. Taking into account the Plotkin b ound (2), it follows that n =2 d = 8 and the number M of co dewords is always M 2 n =16. Attending to Levenshtein's metho d, the co de C 8 C 8 = 0 B B B B B B B B B B B B B B B B B B B B B B B B B B @ 00000000 01001011 01100101 01110010 01011100 00111001 00101110 00010111 11111111 10110100 10011010 10001101 10100011 11000110 11010001 11101000 1 C C C C C C C C C C C C C C C C C C C C C C C C C C A related to the matrix H 8 ab ove is optimal for given length 8 and minimum distance 4. Since C 8 consists of 16 codewords, C 8 maybeusedtosolve the game. In spite of this fact, a smaller (8 ;M; 4) code may b e used as well, provided M 10.
Consider the quasi-Hadamard matrix M 8 obtained from H 8 by randomly changing the entries lo cated at the 1st, 7th and 8th rows, M 8 = 0 B B B B B B B B B B @ 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 C C C C C C C C C C A Taking into account Theorem 1, wemay construct the (8 ; 10 ; 4) co de C 0 8 , C 0 8 = 0 B B B B B B B B B B B B B B @ 01001011 01100101 01110010 01011100 00111001 10110100 10011010 10001101 10100011 11000110 1 C C C C C C C C C C C C C C A related to the matrix M 8 ab ove. Map every integer i in the range [1 ; 10]tothe i -th co deword c i in C 0 8 . Nowyou should ask the following questions: 1. Is the number greater than 5? 2. Is it less or equal to 4 mo dulo 10? 3. Is it in the set f 2 ; 3 ; 5 ; 6 ; 9 g ? 4. Is it in the range [3 ; 7]? 5. Is it in the set f 1 ; 4 ; 5 ; 7 ; 8 g ? 6. Is it even? 7. Is it in the set f 1 ; 3 ; 7 ; 9 ; 10 g ? 8. Is it in the set f 1 ; 2 ; 5 ; 8 ; 9 g ? Assume that the vector of answers is a = ( a 1 ;:::;a 8 ). Select the unique co deword c i in C 0 8 whose summation with a mo dulo 2 pro duces a tuple with at most one non zero entry.Thenthe correct number is i , and the player lied precisely when he answered the question which corresp onds to the column with the non zero entry. ut Remark 2. Notice that any quasi-Hadamard matrix of order 8 and depth 5 could have b een used as well in order to solve the game. The only variation is the questions to ask. In fact, the questions should be formulated so that if the number to guess is i , then the answer to the j -th question is the i -th entry of the j -th co deword of the co de.
Summarizing, depending on the needs of the user, suitable quasi-Hadamard matrices have to b e constructed in order to p erform the desired error correcting co de. Notice that working with quasi-Hadamard matrices and co des instead of Hadamard ones does not mean that functionality is lost (see example 1, for instance). In fact, it often occurs that not all codewords of a given code are actually used for transmissions in practise (see example 2 ab ove). So quasi-Hadamard matrices and quasi-Hadamard codes may suÆce to p erform transmissions at the entire satisfaction of users, including optimal detection and correction aairs. Acknowledgments The authors want to express their gratitude to the referees for their suggestions, whichhaveled toanumb er of improvements of the pap er. References 1. P.J. Cameron. Combinatorics: topics, techniques, algorithms. Cambridge University Press , (1994). 2. U. Feige, S. Goldwasser, S. Safra, L. Lovasz and M. Szegedy. Approximating clique is almost NP-complete. Proceedings 32nd Annual Symposium on the Foundations of Computer Science, FOCS , 2{12, (1991). 3. J. Hastad. Clique is hard to approximate within n 1 . Proceedings 37th Annual IEEE Symposium on the Foundations of Computer Science, FOCS , 627{636, (1996). 4. R.M. Karp. Reducibility among combinatorial problems. Complexity of Computer Computations , 85{103, 1972. 5. V.I. Levenshtein. Application of the Hadamard matrices to a problem in co ding. Problems of Cybernetics , 5 , 166{184, 1964. 6. F.J. MacWilliams and N.J.A. Sloane N.J.A. The theory of error-correcting co des. North Holland, New York, 1977. 7. E. Marchiori. Genetic, Iterated and Multistart Lo cal Search for the Maximum Clique Problem. Proceedings EvoWorkshops 2002 . Eds. S. Cagnoni et al. LNCS 2279 , Springer-Verlag, Berlin Heidelb erg, 112{121, (2002). 8. I. Nob oru. Hadamard Graphs I. Graphs Combin. 1 ,vol. 1, 57{64, 1985. 9. I. Nob oru. Hadamard Graphs II. Graphs Combin. 1 ,vol. 4, 331{337, 1985. 10. M. Plotkin. Binary co des with sp ecied minimum distances. IEEE Trans. Information Theory , 6 , 445{450, 1960.