DT                   T a m á s  D é n e s mathematician                                       TD

free-lance expert

 

titoktan@freemail.hu

 

 


LATIN SQUARES AND CODES

 

 

 

The idea of code construction with the aid of latin squares is older one than algebraic theory of information itself. In 1930 E.Schönhardt wrote a paper on latin squares. Some of his results were used by R. Schauffler to construct error detecting codes.

Let (a1,a2,…,ak) be a word of k message digits which one wishes to transmit. If these q symbols are the integers 0,1,2,……….,q-1 and if one adjoins an addition parity check digit

(1)                                                  ak+1 = a1+a2+...+ak

to k message digits, where addition is modulo q the resulting code words (a1,a2,…,ak,ak+1) of length k+1 each will have minimum Hamming distance 2 and will detect single errors. If one adjoins further check digits ak+2,ak+3,… each defined by means of (1) equations involving some or all the remaining digits, one may make the code multiple error detecting or multiple error correcting. R. Schauffler has pointed out that the equations connecting the code word digits may be chosen so as to involve more than one operation. If Q denots the code word alphabet of q symbols, one may define a set of quasigroups (Q,) on the set Q, exhibiting the multiplication table of each as a bordered latin square. The check digit ak+1 may then be determined by an equation of the form

(2)                                        

where the single operation of addition modulo q previously used has been replaced by a number of different quasigroup operations.

One may easily realize that the decoding procedure of the above code requires the indication of bracketing. R.Schauffler has proposed to eliminate the bracketing by choosing the quasigroups (Q,) to be members of an associative system of quasigroups. V.D. Belousov proved in 1958 the members of an associative system of quasigroups must all be isotopes of one and the same group.

S.W.Golomb and E.C. Posner has proved in 1964 that the existence of a set of t mutually orthogonal latin squares of order q is equivalent to the existence of a code of word length t+2 and minimum Hamming distance t+1 having q2 words constructed from a q-symbol alphabet. Golomb-Posner theorem has been generalized in [3]. For definitions which are not included in this paper the reader is refered to [2] (pages 353-355).

It might be interesting to add at this point that the maximum number of mutually orthogonal latin squares of order n which is denoted by N(n) has been investigated by R.M.Wilson (see [10]). He showed, for large n

(3)                                                   

In addition, it has been proven by the same author that N(n) ³ 6 whenever n > 90. Obviously Wilson’s results can be combined with the result of Golomb and Posner to obtain codes with q2 code words.

One may ask  „What is the maximum number of codewords in a code whose codewords have length n and minimum Hamming distance apart equal to d?”  D.D. Joshi has shown in [6] that this maximum number is at most qn-d+1 called the Joshi bound. Since in the above code q=n, d=n-1 and nn-(n-1)+1 = q2 the Joshi bound was attained which means that the Golomb-Posner codes have maximum number of code words.

We shall give an example of the construction of Golomb-Posner code based on a pair of orthogonal latin squares L1 and L2 (see Figure 1).

       

Figure 1.

 

 

In Fig.1. the entries in the quadruples are respectively row index (i), column index (j) entry in L1  (L1(i,j)), and entry in L2  (L2(i,j)), and the code word is  as it can see in Fig.1.

The orthogonality of latin rectangles can be defined similarly to latin squares. Namely we say that two latin rectangles of the same size are orthogonal if, when one is superimposed on the other, each ordered pair of symbols occurs in at most one cell of the superimposed pair.

Also, a set of n-1 latin rectangles of size n x m, with n > m, is a complete system if each pair of the set is an orthogonal pair. (It is easy to see that we cannot have more than n-1 mutually orthogonal n x m latin rectangles if n ³ m.) P.Quattrocchi has proved the following result in [7].

„For every prime number p and every integer q³ p such that each prime divisior of q is not less than p, there exists at least one complete system of mutually orthogonal pq x p latin rectangles.”

Since the proof of Quattrocchi’s theorem is constructive one can obtain very easily a code with p2q code words corresponding to a complete system of mutually orthogonal pq x p latin rectangles.

For p=2, q=3 we shall consider the following complete system of mutually orthogonal latin rectangles (See R1, R2, R3, R4, R5 in Fig.2.).

 

 

Fig. 2.

The corresponding code can be obtained by a construction analogous to the case of Golomb-Posner codes (see Fig. 1.). The code words which corresponds to the complete system of orthogonal latin rectangles (R1, R2, R3, R4, R5) will be exhibited in Fig. 3.

 

 

Fig. 3.

 

 

We shall compare the number of code words in a code corresponding to a complete set of orthogonal p x pq latin rectangles with the Varshamov-Gilbert lower bound (see [9]).

Since the number of code words in our code p2q, it is over a pq-nary alphabet, each code word has length pq+1 and the minimum Hamming distance is equal to pq-1, the validity of the following inequality should be proven:

(4)                                                

 

(5)  

 

      

 

 

This inequality holds, since

 

(6)     

           

 

 

One can obtain a similar bound to the Varshamov-Gilbert lower bound with the aid of the theorem of Turán (See [8]). Turán theorem can be formulated as follows:

„Every graph with n vertices and with  edges (where n ≡ r mod (k-1), 0£ r <k-1) contains as subgraph a complete graph with at least k vertices. Let us construct a graph in the following way:

There are qn vertices labelled by all the different n-tuples over a q-nary alphabet. Two vertices a and b are connected with an edge if and only if the Hamming distance d between a and b is at least d. Obviously our graph Gq,n,d  has  edges.

A q-nary code with word length n and minimum Hamming distance d has at most as many code words as the number of vertices of the largest complete subgraph of Gq,n,d . By Turán’s theorem if

(7)                                    

 

holds then Gq,n,d  has a subgraph  Kk   i.e. the complete graph with k vertices.

 

To compare the maximum of k in this inequality with the Varshamov-Gilbert lower bound in this respect one can prove that

 

(8)                                                      

 

holds.

 

Since there exist several algorithms how to find complete subgraphs of a given graph, with the aid of Turán’s theorem it is easy to construct codes with „good” parameters.

G.B. Belyavskaya introduced r-orthogonality of latin squares and studied its properties (see [1]). Her definition of r-orthogonality is as follows:

„Two latin squares of the same size are r-orthogonal if, when one is superimposed on the other, exactly r different ordered pair of symbols occur in the cells of the superimposed pair.” (Obviosly n2-orthogonality means that two latin squares of order n are orthogonal).

A set of latin squares of the same size form a system of r-orthogonal latin squares if they are mutually r-orthogonal. Let us suppose that S is a system of r-orthogonal latin squares whose members are L1, L2,……,Lk. Clearly a pair of latin squares say Li and Lj (i, j = 1, …..,k) determines a set of r elements, namely r different ordered pairs of symbols occur in the cells of the superimposed pair. Let be denoted the set which corresponds to Li and Lj by Hij. We shall give an example of a pair of 12-orthogonal latin squares of order 4. (see Fig.4.)

 

 

Fig. 4.

 

A well known theorem on latin squares says that a set of mutually n2-orthogonal latin squares of order n has at most n-1 elements.

Since every latin square of order n is n-orthogonal to itself, there are systems of n-orthogonal latin squares of order n which have infinitely many members. Our example shows that the above theorem is not valid for system of r-orthogonal latin squares if r is arbitrarily chosen.

 

Obviosly, a simple encoding procedure is the following one: let Hij be encoded by ij and let us suppose that at the destination the systems of r-orthogonal latin squares L1, L2,…..,Lk are also stored. Then with the aid of Li and Lj Î Hij can be easily decoded.

 

Three problems arise:

 

a)      What is the maximum value of k such that at least one system of r-orthogonal latin squares of order n exists?

b)      For which value of  r   (pair of r-orthogonal latin squares of order n ) exists?

c)      How one can characterize the sets Hij such that there exists a corresponding pair of r-orthogonal latin squares of order n  say Li and Lj.

 

Problem b) has been studied by G.B.Belyavskaya who proved that

1.      r ¹ n2-1

2.      r ³ n

3.      r ¹ n+1

4.      r ¹ n+2  if n is a prime number and the latin square represents a group

5.      If  n > 4, r =n+k,  where 2£ k £ , then there exists a pair of r-orthogonal latin squares.

 

She also gave necessary and sufficient condition for the existence of r-orthogonal pairs.

Problem a. and c. were not studied sofar. We hope to return to that problems in the future.

 

 

 

References

 

 

[1]  G.B.Belyavskaya:  r-ortogonalnüje kvazigruppü I., II.

                                      Mat. Iszszl. Vüp. 39.  32-39.,

                                      Kvazigruppü i Kombinatorika

                                       Mat. Iszszl. Vüp. 43.  39-49., Kisinyev 1976.

 

[2]  J.Dénes – A.D.Keedwell:  Latin squares and their applications

                                                  Akadémiai Kiadó, Budapest, 1974.

 

[3]  J.Dénes – E.Gergely:  Grupoids and codes

                                           Proc. Information Theory Conf., Hungary, 1975.

 

[4]  E.N.Gilbert:  A comparison of signalling Alphabets

                             Bell System Tchn. J., 31/1952. pp. 504-522.

 

[5]  S.W.Golomb – E.C.Posner:  Rook domains, latin squares, affine planes and error

                                                     distributing codes

                                                     IEEE Trans. Information Theory, IT-10, 1964, pp. 196-208

 

[6]  D.D.Joshi:  A note on upper bounds for minimum distance codes

                          Information and Control, 1/1958., pp. 289-295

 

[7]  P.Quattocchi:  S-spazi e sistemi di rectangoli latini

                               Atti Sem.Mat.Fis.Univ.Modena, 17/1968,  61-71

 

[8]  Turán Pál:  A gráfelmélet egy szélsõérték feladatáról

                          Matematikai Fizikai Lapok, 48/1941, 436-452.

 

[9]  R.R.Varshamov:  Ocenka csiszla szignalov v kodah sz korrekcijej osibok

                                    (English translation: Algebraic Coding Theory, Ed. By I.F.Blake

                                     Dowden, Hutchinson and Ross Inc., Stroudsburg Pennsylvania, 1973.)

 

[10]  R.M.Wilson:  Concerning the number of mutually orthogonal latin squares

                                Discrete Math., 9/1974, 181-198