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

# 6 Bounds on Codes, Special Matrices and Miscellaneous Functions

### Sections

1. Bounds on codes
2. Special matrices in GUAVA
3. Miscellaneous functions

In this chapter we describe functions that determine bounds on the size and minimum distance of codes (Section Bounds on codes), functions that work with special matrices GUAVA needs for several codes (see Section Special matrices in GUAVA), and constructing codes or performing calculations with codes (see Section Miscellaneous functions).

## 6.1 Bounds on codes

This section describes the functions that calculate estimates for upper bounds on the size and minimum distance of codes. Several algorithms are known to compute a largest number of words a code can have with given length and minimum distance. It is important however to understand that in some cases the true upper bound is unknown. A code which has a size equal to the calculated upper bound may not have been found. However, codes that have a larger size do not exist.

A second way to obtain bounds is a table. In GUAVA, an extensive table is implemented for linear codes over GF(2), GF(3) and GF(4). It contains bounds on the minimum distance for given word length and dimension. For binary codes, it contains entries for word length less than or equal to 257. For codes over GF(3) and GF(4), it contains entries for word length less than or equal to 130.

Firstly, we describe functions that compute specific upper bounds on the code size (see UpperBoundSingleton, UpperBoundHamming, UpperBoundJohnson, UpperBoundPlotkin, UpperBoundElias and UpperBoundGriesmer).

Next we describe a function that computes GUAVA's best upper bound on the code size (see UpperBound).

Then we describe two functions that compute a lower and upper bound on the minimum distance of a code (see LowerBoundMinimumDistance and UpperBoundMinimumDistance).

Finally, we describe a function that returns a lower and upper bound on the minimum distance with given parameters and a description of how the bounds were obtained (see BoundsMinimumDistance).

- `UpperBoundSingleton(` n`,` d`,` q`)`

  `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 £ qn-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

- `UpperBoundHamming(` n`,` d`,` q`)`

  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 ) n 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

- `UpperBoundJohnson(` n`,` d`)`

  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

- `UpperBoundPlotkin(` n`,` d`,` q`)`

  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 ]

- `UpperBoundElias(` n`,` d`,` q`)`

  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

- `UpperBoundGriesmer(` n`,` d`,` q`)`

  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(` n`,` d`,` q`)`

  `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

- `LowerBoundMinimumDistance(` C`)`

  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

- `LowerBoundMinimumDistance(` n`,` k`,` F`)`

  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

- `UpperBoundMinimumDistance(` C`)`

  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

- `UpperBoundMinimumDistance(` n`,` k`,` F`)`

  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

- `BoundsMinimumDistance(` n`,` k`,` F`)`

  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(` n`,` q`)`

  `KrawtchoukMat` returns the n +1 by n +1 matrix K=(kij) defined by kij=Ki(j) for i,j=0,·.·,n. Ki(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(` n`,` F`)`

  `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(` n`)`

  `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(` n`)`

  `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(` q`)`
- `MOLS(` q`,` n`)`

  `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 Fq 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(` M`)`
- `PutStandardForm(` M`,` idleft`)`

  `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(` M`)`
- `IsInStandardForm(` M`,` idleft`)`

  `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(` M`,` P`)`

  `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(` M`,` F`)`

  `VerticalConversionFieldMat` returns the matrix M with its elements converted from a field F =GF(qm), 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(qm) 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(` M`,` F`)`

  `HorizontalConversionFieldMat` returns the matrix M with its elements converted from a field F =GF(qm), 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(qm) 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(` M`)`

  `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(` L`)`

  `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(` n`,` t`,` F`)`

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

  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(` k`,` i`,` n`,` q`)`

  `Krawtchouk` returns the Krawtchouk number Kk (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(` F`,` n`)`

  `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 n =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(` P`)`

  `ReciprocalPolynomial` returns the reciprocal of polynomial P. This is a polynomial with coefficients of P in the reverse order. So if P =a0 + a1 X + ·.·+ an Xn , the reciprocal polynomial is P ¢=an + an -1 X + ·.·+ a0 Xn .

      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

- `ReciprocalPolynomial(` P`,` n`)`

  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(` q`,` 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 ] ]

- `WeightHistogram(` C`)`
- `WeightHistogram(` C`,` h`)`

  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]