A Geometry of Coding Theory

A Geometry of Coding Theory

PARTHA PRATIM DEY

Department of Computer Science

NorthSouthUniversity

12 Kemal Ataturk Rd., Banani, Dhaka

BANGLADESH

Abstract: - The connection between projective planes and quantum mechanics is well known [1]. In this paper, we explore the connection of finite projective planes with the theory of coding. The focus is the dimension of the linear codes that are obtained from the incidence systems of projective planes. A good many valuable features of a linear code like its size, number of data and check bits in a codeword, the transmission rate and dimensions of encoder and decoder matrices are obtained when the dimension of the code is known. Compact disk players [2], hard disk drives [3], high-speed modems [4] are some of the components of classical computers, which make use of some of these linear codes to improve reliability of transmission of information over some noisy channel. The idea of quantum information processing on the other hand is inconceivable [5] without the error-correction facilities of these codes or their quantum adaptations.

Key-Words:- Projective planes, dimension, cartesian pair, incidence matrix, codes, centralizers.

1 Introduction

After Euclidean geometry, one of the first to become popular was projective geometry. It was the painters of Italian Renaissance who initiated the study of this geometry [6]. Finite projective planes came from two-dimensional projective geometry.

Suppose is any field. The space of all vectors is called the projective geometry of dimension over , denoted . The zero vector is the void space, and we say that the void space has dimension . A point of dimension is the set of vectors

where and ranges over all elements of . More generally if are independent vectors, the set of all vectors , is a subspace of dimension . A subspace of dimension is called a hyperplane. If it can be shown that the set of all vectors satisfying

is a hyperplane, and conversely, that every hyperplane can be defined this way, and defining the same point.

If the field is the field then writing , there are vectors . Each of the vectors different from zero determines a point, and since and , determine the same point, there are points. In the same way, since and , determine the same hyperplane, there are hyperplanes. If are independent vectors, then ,gives vectors. Excluding the zero vector, we have different points in the space of dimension . Thus a hyperplane has different points. Singer [7] has proved that the hyperplanes of ,as blocks, points as objects, form a symmetric design with

and .

Ifthen and . This special-dimensional-symmetric design is called a projective plane of order.

However there is another approach to projective plane that is far more general than the approach above. In this approach, a projective plane of orderis an incidence structure withpoints and lines. Any two distinct points are contained on exactly one line and two distinct lines intersect in a unique point. Each line consists ofpoints and each point belongs to precisely lines. For each lineof the plane, we may form the derived design whose points are thepoints of the set and whose lines are thelines obtained by deleting the points offrom each line of. This design, denoted by , is called the affine plane afforded by. Hall has shown [8], it is possible to coordinatize any projective plane by means of a ternary ring. When the ternary ring is a field, the plane is called Desarguesian.

2 Cartesian Connection of the Incidence Matrix

A Cartesian group of order is an automorphism group of with elements called elations. Each nontrivial elation of fixes pointwise a distinguished line (called the axis of ) and fixes no other point. Dually, contains a distinguished point (called the center of ) and each element of fixes the lines incident with and no further lines. The groupis called a transitivity as transitively permutes the points of for any line containing . This implies that there are precisely point orbits for of length and exactly singleton point orbits. Likewise permutes the lines so that there are line orbits of length and exactly fixed lines.

Let us now assume that is a plane of order and =is a Cartesian group with axisand center. Let denote the lines of incident with and different from. Set and choose a base point . Then as acts transitively onand the sets partition the points of the affine plane \. Likewise, if denote the points of different from, we may pick a base line so that is the set of lines of different from and incident with . The sets partition thelines of which do not contain and we define to be the incidence matrix for the pair . That is, has entry one if the point is incident with the line . Because the lines of correspond to a parallel class of the affine plane, is a permutation matrix and the matrix is an incidence matrix for the lines and points not fixed by .

We may enlarge to an incidence matrix of by the addition of more columns and rows with the last columns corresponding the points of and the last rows labeled by the lines . We obtain a matrix,

,

where are rectangular matrices of size and respectively. Note that the first rows of are the characteristic vectors for the sets and independent of the base point chosen. Each entry in the last row and column of is one and all other entries are zero.

Theorem[9]. Assume is a Cartesian group of order and is the incidence matrix. Then is a matrix of orderwhose entries belong to the regular permutation representation . Moreover, for the sequence

contains each element of exactly once.

The matrix in Theorem is called a generalized Hadamard matrix of order for . Since , we may identify the elements of with those of so that is also a generalized Hadamard matrix for of order . We calla Cartesian group anda Cartesian pair.

3 Codes of the Planes

Letdenote the finite field withelements, and letdenote the set of-tupleswhere. A codeoveris a linear subspace of of dimension. The vectors of are called codewords, and sometimes more briefly words. The dual codeis the subspace orthogonal tounder the usual scalar product on. That is

for all

Here is acode.

Definition. The codeof a planeof orderis defined as the linear subspace ofspanned by the rows of its incidence matrix considered as vectors overwhereis the number of points (lines) in.

Hamming codes, BCH codes etc. are examples of such codes.

The dimension of the code of a Desarguesian projective plane of order is equal to .

This formula for rank was conjectured by Rudolph and has been proved, using different methods , by Goethals and Delsarte [10], by MacWilliams and Mann [11] and finally by Smith [12].

But in the case of non-Desarguesian planes we do not have similar formulas. The only known result [13]states that if is a plane of order , its code over and divides exactly to the first power, then

and

and is a subcode of of codimension However, there is a similar theorem [14] for the code of an affine plane. It states that ifis the code of an affine planeof order, then

whendivides exactly to the first power. Moreover if affords atransitivity, thenis a-invariant subcode. We have been able [15] to prove that if is a code overandis a group of linear transformations leavinginvariant, then

wherewith,are generators of subgroups of order , andare centralizers of andrespectively.

VanAken has been able to determine the dimension of the code of a biaffine plane under the assumption that dividesexactly to the first power. A biaffine plane of order is an incidence system which is obtained by deleting just one point from an affine plane.

Theorem (VanAken). Let be an affine difference set of order in a group , . If is a prime divisor of and does not divide , the code overof the development of has dimension .

We conclude this section with a brief discussion on the extended code of a projective plane of order . The extended code of is the span of the rows of the extended incidence matrix given as follows.

where is the incidence matrix of. Instead of ordinary dot product we define the bilinear form by

for and with . This form is called the Minkowski product. One checks that if and are rows of then or . Thus . The extended code is thus self orthogonal with respect to the Minkowskii product. In fact the following theorem states that when divides exactly to the first power, is actually self-dual.

Theorem[16] Let be a projective plane of order . If divides exactly to the first power, then the extended code of has dimension and is self-dual with respect to the Minkowskii product .

The above theorem fails completely if . In general the dimension of is much smaller than . The dimension of of for example, has been computed exactly by the coding theorists. According to this computation, if the order of the plane is then [length, dimension] ofis given by .

References:

[1] V. S. Varadarajan, Geometry of Quantum

Mechanics, Springer-Verlag, Berlin, 2nd ed.,1985

[2] J. B. H. Peek, Communications Aspects of the Compact Disk Digital Audio System, IEEE Commun.Mag.,23, 7-15, Feb. 1985.

[3] B. H. Marcus, P.H. Siegel, and J.K. Wolf, Finite State Modulation Codes for Data Storage, IEEE J.Select. Areas Commu.,10,5-37,1992.

[4] G. D. Forney, Jr., L. Brown, M.V. Eyuboglu, and J.L. Moran III, The V.34 high-speed modem standard, IEEE Commun. Mag.,34, 28-33, Dec. 1996.

[5] A. M. Steane, Dark Matter in Cosmology, Quantum Measurements and Experimental Gravitation, Proc. XXXIst Recontres de Moriond, January 1996.

[6] Roger Mohr and Bill Triggs, Projective Geometry for Image Analysis, A Tutorial given at ISPRS, Vienna, July 1996.

[7] J. Singer, A Theorem in Finite Projective Geometry and Some Applications to Number Theory, Trans.

Amer. Math. Soc.,43,377-385, 1938.

[8] M. Hall, The Theory of Groups, New York: The Macmillan Company, 1959.

[9] P. P. Dey and J.L. Hayden, On Symmetric Incidence Matrices of Projective Planes, Designs, Codes andCryptography,6,179-188, 1995.

[10] I. M.Goethals and P. Delsarte, On a Class of Majority Logic Decodable Codes, presented at the San Remo International Symposium on Information Theory, 1967.

[11] J. MacWilliams and H.B.Mann, On the p-rank of the Design Matrix of a Difference Set, MathResearch Center, Technical Report, No. 803, University of Wisconsin, 1967.

[12] K.J.C. Smith, On the p-rank of the Incidence Matrix of Points and Hyperplanes in a Finite Projective Geometry, J. of Comb. Theory,7, 122-129, 1969.

[13] M. Hall, Combinatorial Theory, New York-Chichester-Brisbane-Toronto-Singapore: Interscience, 1986

[14] P. P. Dey, Code of an Affine Plane, Proceedings of International Conference on Computer &Information Technology, 244-248, 2000.

[15] P. P. Dey, Invariant Linear Codes and their Dimensions, accepted for Proceedings of International Multi-conference on Information and Knowledge Engineering 2003.

[16] E. S. Lander, Symmetric Designs: An Algebraic Approach, London-New York-New Rochelle- Melbourne-Sydney: Cambridge Press, 1983.

.