6 Bounds on Codes, Special Matrices and Miscellaneous Functions

UpperBoundSingleton returns the Singleton bound for a code of length n, minimum distance d over a field of size q. This bound is based on the shortening of codes. By shortening an (n, M, d) code d-1 times, an (n-d+1,M,1) code results, with M £ q^n-d+1 (see ShortenedCode). Thus

M £ q n -d +1

Codes that meet this bound are called maximum distance separable (see IsMDSCode).

gap> UpperBoundSingleton(4, 3, 5);
25
gap> C := ReedSolomonCode(4,3);; Size(C);
25
gap> IsMDSCode(C);
true 

The Hamming bound (also known as sphere packing bound) returns an upper bound on the size of a code of length n, minimum distance d, over a field of size q. The Hamming bound is obtained by dividing the contents of the entire space GF(q ) ⁿ by the contents of a ball with radius ë(d -1) / 2û. As all these balls are disjoint, they can never contain more than the whole vector space.

M £  q n V(n ,e)

where M is the maxmimum number of codewords and V(n ,e) is equal to the contents of a ball of radius e (see SphereContent). This bound is useful for small values of d. Codes for which equality holds are called perfect (see IsPerfectCode).

gap> UpperBoundHamming( 15, 3, 2 );
2048
gap> C := HammingCode( 4, GF(2) );
a linear [15,11,3]1 Hamming (4,2) code over GF(2)
gap> Size( C );
2048 

The Johnson bound is an improved version of the Hamming bound (see UpperBoundHamming). In addition to the Hamming bound, it takes into account the elements of the space outside the balls of radius e around the elements of the code. The Johnson bound only works for binary codes.

gap> UpperBoundJohnson( 13, 5 );
77
gap> UpperBoundHamming( 13, 5, 2);
89   # in this case the Johnson bound is better 

The function UpperBoundPlotkin calculates the sum of the distances of all ordered pairs of different codewords. It is based on the fact that the minimum distance is at most equal to the average distance. It is a good bound if the weights of the codewords do not differ much. It results in:

M £  d d -(1-1/q )n

M is the maximum number of codewords. In this case, d must be larger than (1-1/q )n , but by shortening the code, the case d < (1-1/q )n is covered.

gap> UpperBoundPlotkin( 15, 7, 2 );
32
gap> C := BCHCode( 15, 7, GF(2) );
a cyclic [15,5,7]5 BCH code, delta=7, b=1 over GF(2)
gap> Size(C);
32
gap> WeightDistribution(C);
[ 1, 0, 0, 0, 0, 0, 0, 15, 15, 0, 0, 0, 0, 0, 0, 1 ] 

The Elias bound is an improvement of the Plotkin bound (see UpperBoundPlotkin) for large codes. Subcodes are used to decrease the size of the code, in this case the subcode of all codewords within a certain ball. This bound is useful for large codes with relatively small minimum distances.

gap> UpperBoundPlotkin( 16, 3, 2 );
12288
gap> UpperBoundElias( 16, 3, 2 );
10280 

The Griesmer bound is valid only for linear codes. It is obtained by counting the number of equal symbols in each row of the generator matrix of the code. By omitting the coordinates in which all rows have a zero, a smaller code results. The Griesmer bound is obtained by repeating this proces until a trivial code is left in the end.

gap> UpperBoundGriesmer( 13, 5, 2 );
64
gap> UpperBoundGriesmer( 18, 9, 2 );
8        # the maximum number of words for a linear code is 8
gap> Size( PuncturedCode( HadamardCode( 20, 1 ) ) );
20       # this non-linear code has 20 elements 

UpperBound returns the best known upper bound A(n ,d ) for the size of a code of length n, minimum distance d over a field of size q. The function UpperBound first checks for trivial cases (like d =1 or n =d ) and if the value is in the built-in table. Then it calculates the minimum value of the upper bound using the methods of Singleton (see UpperBoundSingleton), Hamming (see UpperBoundHamming), Johnson (see UpperBoundJohnson), Plotkin (see UpperBoundPlotkin) and Elias (see UpperBoundElias). If the code is binary, A(n , 2*l-1) = A(n +1, 2*l), so the UpperBound takes the minimum of the values obtained from all methods for the parameters (n , 2*l-1) and (n +1, 2*l).

gap> UpperBound( 10, 3, 2 );
85
gap> UpperBound( 25, 9, 8 );
1211778792827540 

In this form, LowerBoundMinimumDistance returns a lower bound for the minimum distance of code C.

gap> C := BCHCode( 45, 7 );
a cyclic [45,23,7..9]6..16 BCH code, delta=7, b=1 over GF(2)
gap> LowerBoundMinimumDistance( C );
7     # designed distance is lower bound for minimum distance 

In this form, LowerBoundMinimumDistance returns a lower bound for the minimum distance of the best known linear code of length n, dimension k over field F. It uses the mechanism explained in section BoundsMinimumDistance.

gap> LowerBoundMinimumDistance( 45, 23, GF(2) );
10 

In this form, UpperBoundMinimumDistance returns an upper bound for the minimum distance of code C. For unrestricted codes, it just returns the word length. For linear codes, it takes the minimum of the possibly known value from the method of construction, the weight of the generators, and the value from the table (see BoundsMinimumDistance).

gap> C := BCHCode( 45, 7 );;
gap> UpperBoundMinimumDistance( C );
9 

In this form, UpperBoundMinimumDistance returns an upper bound for the minimum distance of the best known linear code of length n, dimension k over field F. It uses the mechanism explained in section BoundsMinimumDistance.

gap> UpperBoundMinimumDistance( 45, 23, GF(2) );
11 

The function BoundsMinimumDistance calculates a lower and upper bound for the minimum distance of an optimal linear code with word length n, dimension k over field F. The function returns a record with the two bounds and an explenation for each bound. The function Display can be used to show the explanations.

The values for the lower and upper bound are obtained from a table. GUAVA has tables containing lower and upper bounds for q=2 (n £ 257), 3 and 4 (n £ 130). These tables were derived from the table of Brouwer & Verhoeff. For codes over other fields and for larger word lengths, trivial bounds are used.

The resulting record can be used in the function BestKnownLinearCode (see BestKnownLinearCode) to construct a code with minimum distance equal to the lower bound.

gap> bounds := BoundsMinimumDistance( 7, 3 );; DisplayBoundsInfo( bounds );
an optimal linear [7,3,d] code over GF(2) has d=4
------------------------------------------------------------------------------
Lb(7,3)=4, by shortening of:
Lb(8,4)=4, u u+v construction of C1 and C2:
Lb(4,3)=2, dual of the repetition code
Lb(4,1)=4, repetition code
------------------------------------------------------------------------------
Ub(7,3)=4, Griesmer bound
# The lower bound is equal to the upper bound, so a code with
# these parameters is optimal.
gap> C := BestKnownLinearCode( bounds );; Display( C );
a linear [7,3,4]2..3 shortened code of
a linear [8,4,4]2 U U+V construction code of
U: a cyclic [4,3,2]1 dual code of
   a cyclic [4,1,4]2 repetition code over GF(2)
V: a cyclic [4,1,4]2 repetition code over GF(2)

6.2 Special matrices in GUAVA

This section explains functions that work with special matrices GUAVA needs for several codes.

Firstly, we describe some matrix generating functions (see KrawtchoukMat, GrayMat, SylvesterMat, HadamardMat and MOLS).

Next we describe two functions regarding a standard form of matrices (see PutStandardForm and IsInStandardForm).

Then we describe functions that return a matrix after a manipulation (see PermutedCols, VerticalConversionFieldMat and HorizontalConversionFieldMat).

Finally, we describe functions that do some tests on matrices (see IsLatinSquare and AreMOLS).

KrawtchoukMat returns the n +1 by n +1 matrix K=(k_ij) defined by k_ij=K_i(j) for i,j=0,·.·,n. K_i(j) is the Krawtchouk number (see Krawtchouk). n must be a positive integer and q a prime power. The Krawtchouk matrix is used in the MacWilliams identities, defining the relation between the weight distribution of a code of length n over a field of size q, and its dual code. Each call to KrawtchoukMat returns a new matrix, so it is safe to modify the result.

gap> PrintArray( KrawtchoukMat( 3, 2 ) );
[ [   1,   1,   1,   1 ],
  [   3,   1,  -1,  -3 ],
  [   3,  -1,  -1,   3 ],
  [   1,  -1,   1,  -1 ] ]
gap> C := HammingCode( 3 );; a := WeightDistribution( C );
[ 1, 0, 0, 7, 7, 0, 0, 1 ]
gap> n := WordLength( C );; q := Size( LeftActingDomain( C ) );;
gap> k := Dimension( C );;
gap> q^( -k ) * KrawtchoukMat( n, q ) * a;
[ 1, 0, 0, 0, 7, 0, 0, 0 ]
gap> WeightDistribution( DualCode( C ) );
[ 1, 0, 0, 0, 7, 0, 0, 0 ] 

GrayMat returns a list of all different vectors (see Vectors) of length n over the field F, using Gray ordening. n must be a positive integer. This order has the property that subsequent vectors differ in exactly one coordinate. The first vector is always the null vector. Each call to GrayMat returns a new matrix, so it is safe to modify the result.

gap> GrayMat(3);
[ [ 0*Z(2), 0*Z(2), 0*Z(2) ], [ 0*Z(2), 0*Z(2), Z(2)^0 ],
  [ 0*Z(2), Z(2)^0, Z(2)^0 ], [ 0*Z(2), Z(2)^0, 0*Z(2) ],
  [ Z(2)^0, Z(2)^0, 0*Z(2) ], [ Z(2)^0, Z(2)^0, Z(2)^0 ],
  [ Z(2)^0, 0*Z(2), Z(2)^0 ], [ Z(2)^0, 0*Z(2), 0*Z(2) ] ]
gap> G := GrayMat( 4, GF(4) );; Length(G);
256          # the length of a GrayMat is always $q^n$
gap> G[101] - G[100];
[ 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2) ] 

SylvesterMat returns the n by n Sylvester matrix of order n. This is a special case of the Hadamard matrices (see HadamardMat). For this construction, n must be a power of 2. Each call to SylvesterMat returns a new matrix, so it is safe to modify the result.

gap> PrintArray(SylvesterMat(2));
[ [   1,   1 ],
  [   1,  -1 ] ]
gap> PrintArray( SylvesterMat(4) );
[ [   1,   1,   1,   1 ],
  [   1,  -1,   1,  -1 ],
  [   1,   1,  -1,  -1 ],
  [   1,  -1,  -1,   1 ] ] 

HadamardMat returns a Hadamard matrix of order n. This is an n by n matrix with the property that the matrix multiplied by its transpose returns n times the identity matrix. This is only possible for n =1, n =2 or in cases where n is a multiple of 4. If the matrix does not exist or is not known, HadamardMat returns an error. A large number of construction methods is known to create these matrices for different orders. HadamardMat makes use of two construction methods (among which the Sylvester construction (see SylvesterMat)). These methods cover most of the possible Hadamard matrices, although some special algorithms have not been implemented yet. The following orders less than 100 do not have an implementation for a Hadamard matrix in GUAVA: 28, 36, 52, 76, 92·

gap> C := HadamardMat(8);; PrintArray(C);
[ [   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,  -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 ] ]
gap> C * TransposedMat(C) = 8 * IdentityMat( 8, 8 );
true 

MOLS returns a list of n Mutually Orthogonal Latin Squares (MOLS). A Latin square of order q is a q by q matrix whose entries are from a set F_q of q distinct symbols (GUAVA uses the integers from 0 to q) such that each row and each column of the matrix contains each symbol exactly once.

A set of Latin squares is a set of MOLS if and only if for each pair of Latin squares in this set, every ordered pair of elements that are in the same position in these matrices occurs exactly once.

n must be less than q. If n is omitted, two MOLS are returned. If q is not a prime power, at most 2 MOLS can be created. For all values of q with q > 2 and q ¹ 6, a list of MOLS can be constructed. GUAVA however does not yet construct MOLS for q mod 4 = 2. If it is not possible to construct n MOLS, the function returns false.

MOLS are used to create q-ary codes (see MOLSCode).

gap> M := MOLS( 4, 3 );;PrintArray( M[1] );
[ [  0,  1,  2,  3 ],
  [  1,  0,  3,  2 ],
  [  2,  3,  0,  1 ],
  [  3,  2,  1,  0 ] ]
gap> PrintArray( M[2] );
[ [  0,  2,  3,  1 ],
  [  1,  3,  2,  0 ],
  [  2,  0,  1,  3 ],
  [  3,  1,  0,  2 ] ]
gap> PrintArray( M[3] );
[ [  0,  3,  1,  2 ],
  [  1,  2,  0,  3 ],
  [  2,  1,  3,  0 ],
  [  3,  0,  2,  1 ] ]
gap> MOLS( 12, 3 );
false 

PutStandardForm puts a matrix M in standard form, and returns the permutation needed to do so. idleft is a boolean that sets the position of the identity matrix in M. If idleft is set to true, the identity matrix is put in the left side of M. Otherwise, it is put at the right side. The default for idleft is true.

The function BaseMat also returns a similar standard form, but does not apply column permutations. The rows of the matrix still span the same vector space after BaseMat, but after calling PutStandardForm, this is not necessarily true.

gap> M := Z(2)*[[1,0,0,1],[0,0,1,1]];; PrintArray(M);
[ [    Z(2),  0*Z(2),  0*Z(2),    Z(2) ],
  [  0*Z(2),  0*Z(2),    Z(2),    Z(2) ] ]
gap> PutStandardForm(M);                   # identity at the left side
(2,3)
gap> PrintArray(M);
[ [    Z(2),  0*Z(2),  0*Z(2),    Z(2) ],
  [  0*Z(2),    Z(2),  0*Z(2),    Z(2) ] ]
gap> PutStandardForm(M, false);            # identity at the right side
(1,4,3)
gap> PrintArray(M);
[ [  0*Z(2),    Z(2),    Z(2),  0*Z(2) ],
  [  0*Z(2),    Z(2),  0*Z(2),    Z(2) ] ]

IsInStandardForm determines if M is in standard form. idleft is a boolean that indicates the position of the identity matrix in M. If idleft is true, IsInStandardForm checks if the identity matrix is at the left side of M, otherwise if it is at the right side. The default for idleft is true. The elements of M may be elements of any field. To put a matrix in standard form, use PutStandardForm (see PutStandardForm).

gap> IsInStandardForm(IdentityMat(7, GF(2)));
true
gap> IsInStandardForm([[1, 1, 0], [1, 0, 1]], false);
true
gap> IsInStandardForm([[1, 3, 2, 7]]);
true
gap> IsInStandardForm(HadamardMat(4));
false 

PermutedCols returns a matrix M with a permutation P applied to its columns.

gap> M := [[1,2,3,4],[1,2,3,4]];; PrintArray(M);
[ [  1,  2,  3,  4 ],
  [  1,  2,  3,  4 ] ]
gap> PrintArray(PermutedCols(M, (1,2,3)));
[ [  3,  1,  2,  4 ],
  [  3,  1,  2,  4 ] ] 

VerticalConversionFieldMat returns the matrix M with its elements converted from a field F =GF(q^m), q prime, to a field GF(q). Each element is replaced by its representation over the latter field, placed vertically in the matrix.

If M is a k by n matrix, the result is a k*m by n matrix, since each element of GF(q^m) can be represented in GF(q) using m elements.

gap> M := Z(9)*[[1,2],[2,1]];; PrintArray(M);
[ [    Z(3^2),  Z(3^2)^5 ],
  [  Z(3^2)^5,    Z(3^2) ] ]
gap> DefaultField( Flat(M) );
GF(3^2)
gap> VCFM := VerticalConversionFieldMat( M, GF(9) );; PrintArray(VCFM);
[ [  0*Z(3),  0*Z(3) ],
  [  Z(3)^0,    Z(3) ],
  [  0*Z(3),  0*Z(3) ],
  [    Z(3),  Z(3)^0 ] ]
gap> DefaultField( Flat(VCFM) );
GF(3) 

A similar function is HorizontalConversionFieldMat (see HorizontalConversionFieldMat).

HorizontalConversionFieldMat returns the matrix M with its elements converted from a field F =GF(q^m), q prime, to a field GF(q). Each element is replaced by its representation over the latter field, placed horizontally in the matrix.

If M is a k by n matrix, the result is a k*m by n*m matrix. The new word length of the resulting code is equal to n*m, because each element of GF(q^m) can be represented in GF(q) using m elements. The new dimension is equal to k*m because the new matrix should be a basis for the same number of vectors as the old one.

ConversionFieldCode uses horizontal conversion to convert a code (see ConversionFieldCode).

gap> M := Z(9)*[[1,2],[2,1]];; PrintArray(M);
[ [    Z(3^2),  Z(3^2)^5 ],
  [  Z(3^2)^5,    Z(3^2) ] ]
gap> DefaultField( Flat(M) );
GF(3^2)
gap> HCFM := HorizontalConversionFieldMat(M, GF(9));; PrintArray(HCFM);
[ [  0*Z(3),  Z(3)^0,  0*Z(3),    Z(3) ],
  [  Z(3)^0,  Z(3)^0,    Z(3),    Z(3) ],
  [  0*Z(3),    Z(3),  0*Z(3),  Z(3)^0 ],
  [    Z(3),    Z(3),  Z(3)^0,  Z(3)^0 ] ]
gap> DefaultField( Flat(HCFM) );
GF(3) 

A similar function is VerticalConversionFieldMat (see VerticalConversionFieldMat).

IsLatinSquare determines if a matrix M is a latin square. For a latin square of size n by n, each row and each column contains all the integers 1,...,n exactly once.

gap> IsLatinSquare([[1,2],[2,1]]);
true
gap> IsLatinSquare([[1,2,3],[2,3,1],[1,3,2]]);
false 

AreMOLS determines if L is a list of mutually orthogonal latin squares (MOLS). For each pair of latin squares in this list, the function checks if each ordered pair of elements that are in the same position in these matrices occurs exactly once. The function MOLS creates MOLS (see MOLS).

gap> M := MOLS(4,2);
[ [ [ 0, 1, 2, 3 ], [ 1, 0, 3, 2 ], [ 2, 3, 0, 1 ], [ 3, 2, 1, 0 ] ],
  [ [ 0, 2, 3, 1 ], [ 1, 3, 2, 0 ], [ 2, 0, 1, 3 ], [ 3, 1, 0, 2 ] ] ]
gap> AreMOLS(M);
true 

6.3 Miscellaneous functions

In this section we describe several functions GUAVA uses for constructing codes or performing calculations with codes.

SphereContent returns the content of a ball of radius t around an arbitrary element of the vectorspace F ⁿ . This is the cardinality of the set of all elements of F ⁿ that are at distance (see DistanceCodeword) less than or equal to t from an element of F ⁿ .

In the context of codes, the function is used to determine if a code is perfect. A code is perfect if spheres of radius t around all codewords contain exactly the whole vectorspace, where t is the number of errors the code can correct.

gap> SphereContent( 15, 0, GF(2) );
1    # Only one word with distance 0, which is the word itself
gap> SphereContent( 11, 3, GF(4) );
4984
gap> C := HammingCode(5);
a linear [31,26,3]1 Hamming (5,2) code over GF(2)
#the minimum distance is 3, so the code can correct one error
gap> ( SphereContent( 31, 1, GF(2) ) * Size(C) ) = 2 ^ 31;
true 

Krawtchouk returns the Krawtchouk number K_k (i ). q must be a primepower, n must be a positive integer, k must be a non-negative integer less then or equal to n and i can be any integer. (See KrawtchoukMat).

gap> Krawtchouk( 2, 0, 3, 2);
3 

PrimitiveUnityRoot returns a primitive nth root of unity in an extension field of F. This is a finite field element a with the property a ⁿ =1 mod n, and n is the smallest integer such that this equality holds.

gap> PrimitiveUnityRoot( GF(2), 15 );
Z(2^4)
gap> last^15;
Z(2)^0
gap> PrimitiveUnityRoot( GF(8), 21 );
Z(2^6)^3 

ReciprocalPolynomial returns the reciprocal of polynomial P. This is a polynomial with coefficients of P in the reverse order. So if P =a₀ + a₁ X + ·.·+ a_n Xⁿ , the reciprocal polynomial is P ¢=a_n + a_{n -1} X + ·.·+ a₀ Xⁿ .

gap> P := UnivariatePolynomial( GF(3), Z(3)^0 * [1,0,1,2] );
Z(3)^0+x_1^2-x_1^3
gap> RecP := ReciprocalPolynomial( P );
-Z(3)^0+x_1+x_1^3
gap> ReciprocalPolynomial( RecP ) = P;
true 

In this form, the number of coefficients of P is considered to be at least n (possibly with zero coefficients at the highest degrees). Therefore, the reciprocal polynomial P álso has degree at least n.

gap> P := UnivariatePolynomial( GF(3), Z(3)^0 * [1,0,1,2] );
Z(3)^0+x_1^2-x_1^3
gap> ReciprocalPolynomial( P, 6 );
-x_1^3+x_1^4+x_1^6

In this form, the degree of P is considered to be at least n (if not, zero coefficients are added). Therefore, the reciprocal polynomial P álso has degree at least n.

CyclotomicCosets returns the cyclotomic cosets of q modulo n. q and n must be relatively prime. Each of the elements of the returned list is a list of integers that belong to one cyclotomic coset. Each coset contains all multiplications of the coset representative by q, modulo n. The coset representative is the smallest integer that isn't in the previous cosets.

gap> CyclotomicCosets( 2, 15 );
[ [ 0 ], [ 1, 2, 4, 8 ], [ 3, 6, 12, 9 ], [ 5, 10 ],
  [ 7, 14, 13, 11 ] ]
gap> CyclotomicCosets( 7, 6 );
[ [ 0 ], [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ] ] 

The function WeightHistogram plots a histogram of weights in code C. The maximum length of a column is h. Default value for h is 1/3 of the size of the screen. The number that appears at the top of the histogram is the maximum value of the list of weights.

gap> H := HammingCode(2, GF(5));
a linear [6,4,3]1 Hamming (2,5) code over GF(5)
gap> WeightDistribution(H);
[ 1, 0, 0, 80, 120, 264, 160 ]
gap> WeightHistogram(H);
264----------------
               *
               *
               *
               *
               *  *
            *  *  *
         *  *  *  *
         *  *  *  *
+--------+--+--+--+--
0  1  2  3  4  5  6 

[Up] [Previous] [Next] [Index]