In this chapter we describe functions that determine bounds on the size and minimum distance of codes (Section 7.1), functions that determine bounds on the size and covering radius of codes (Section 7.2), functions that work with special matrices GUAVA needs for several codes (see Section 7.3), and constructing codes or performing calculations with codes (see Section 7.5).
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 equalto 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. It contains entries for word lengths less than or equal to 257, 243 and 256 for codes over GF(2), GF(3) and GF(4) respectively. These entries were obtained from Brouwer's tables as of 11 May 2006. For the latest information, please see A. E. Brouwer's tables [Bro06] on the internet.
Firstly, we describe functions that compute specific upper bounds on the code size (see UpperBoundSingleton (7.1-1), UpperBoundHamming (7.1-2), UpperBoundJohnson (7.1-3), UpperBoundPlotkin (7.1-4), UpperBoundElias (7.1-5) and UpperBoundGriesmer (7.1-6)).
Next we describe a function that computes GUAVA's best upper bound on the code size (see UpperBound (7.1-8)).
Then we describe two functions that compute a lower and upper bound on the minimum distance of a code (see LowerBoundMinimumDistance (7.1-9) and UpperBoundMinimumDistance (7.1-12)).
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 (7.1-13)).
‣ UpperBoundSingleton( n, d, q ) | ( function ) |
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 (6.1-9)). Thus
M \leq q^{n-d+1}.
Codes that meet this bound are called maximum distance separable (see IsMDSCode (4.3-7)).
gap> UpperBoundSingleton(4, 3, 5); 25 gap> C := ReedSolomonCode(4,3);; Size(C); 25 gap> IsMDSCode(C); true
‣ UpperBoundHamming( n, d, q ) | ( function ) |
The Hamming bound (also known as the 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 \leq {q^n \over V(n,e)},
where M is the maximum number of codewords and V(n,e) is equal to the contents of a ball of radius e (see SphereContent (7.5-5)). This bound is useful for small values of d. Codes for which equality holds are called perfect (see IsPerfectCode (4.3-6)).
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 ) | ( function ) |
The Johnson bound is an improved version of the Hamming bound (see UpperBoundHamming (7.1-2)). 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 ) | ( function ) |
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 \leq {d \over {d-(1-1/q)n}},
where 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 ) | ( function ) |
The Elias bound is an improvement of the Plotkin bound (see UpperBoundPlotkin (7.1-4)) 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 gap> UpperBoundElias( 20, 10, 3 ); 16255
‣ UpperBoundGriesmer( n, d, q ) | ( function ) |
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 process 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
‣ IsGriesmerCode( C ) | ( function ) |
IsGriesmerCode returns `true' if a linear code C is a Griesmer code, and `false' otherwise. A code is called Griesmer if its length satisfies
n = g[k,d] = \sum_{i=0}^{k-1} \lceil \frac{d}{q^i} \rceil.
gap> IsGriesmerCode( HammingCode( 3, GF(2) ) ); true gap> IsGriesmerCode( BCHCode( 17, 2, GF(2) ) ); false
‣ UpperBound( n, d, q ) | ( function ) |
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 (7.1-1)), Hamming (see UpperBoundHamming (7.1-2)), Johnson (see UpperBoundJohnson (7.1-3)), Plotkin (see UpperBoundPlotkin (7.1-4)) and Elias (see UpperBoundElias (7.1-5)). If the code is binary, A(n, 2⋅ ℓ-1) = A(n+1,2⋅ ℓ), so the UpperBound takes the minimum of the values obtained from all methods for the parameters (n, 2⋅ℓ-1) and (n+1, 2⋅ ℓ).
gap> UpperBound( 10, 3, 2 ); 85 gap> UpperBound( 25, 9, 8 ); 1211778792827540
‣ LowerBoundMinimumDistance( C ) | ( function ) |
In this form, LowerBoundMinimumDistance returns a lower bound for the minimum distance of code C.
This command can also be called using the syntax 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 7.1-13.
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 gap> LowerBoundMinimumDistance( 45, 23, GF(2) ); 10
‣ LowerBoundGilbertVarshamov( n, d, q ) | ( function ) |
This is the lower bound on the size of a linear code due (independently) to Gilbert and Varshamov. It says that for each n and d, there exists a linear code having length n and minimum distance d at least of size q^k, where k is the largest integer such that q^k < q^n/SphereContent(n-1,d-2,GF(q)).
gap> LowerBoundGilbertVarshamov(24,8,2); 64 gap> LowerBoundGilbertVarshamov(7,3,2); 16 gap> LowerBoundMinimumDistance(7,4,2); 3 gap> LowerBoundGilbertVarshamov(3,3,2); 1 gap> LowerBoundMinimumDistance(3,3,2); 1 gap> LowerBoundGilbertVarshamov(25,10,2); 16
‣ LowerBoundSpherePacking( n, d, q ) | ( function ) |
This is the (weaker) Gilbert-Varshamov bound valid for unrestricted codes over an alphabet of size q (where q is an integer > 1). It says that for each n and r, there exists an unrestricted code at least of size q^n/SphereContent(n,d,GF(q)) minimum distance d.
gap> LowerBoundSpherePacking(3,2,2); 2 gap> LowerBoundSpherePacking(3,3,2); 1
‣ UpperBoundMinimumDistance( C ) | ( function ) |
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 7.1-13).
This command can also be called using the syntax 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 7.1-13.
gap> C := BCHCode( 45, 7 );; gap> UpperBoundMinimumDistance( C ); 9 gap> UpperBoundMinimumDistance( 45, 23, GF(2) ); 11
‣ BoundsMinimumDistance( n, k, F ) | ( function ) |
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 explanation 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 (n ≤ 243), 4 (n ≤ 256). (Current as of 11 May 2006.) These tables were derived from the table of Brouwer. (See [Bro06], https://www.codetables.de for the most recent data.) 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 (5.2-14)) 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)
‣ BoundsCoveringRadius( C ) | ( function ) |
BoundsCoveringRadius returns a list of integers. The first entry of this list is the maximum of some lower bounds for the covering radius of C, the last entry the minimum of some upper bounds of C.
If the covering radius of C is known, a list of length 1 is returned. BoundsCoveringRadius makes use of the functions GeneralLowerBoundCoveringRadius and GeneralUpperBoundCoveringRadius.
gap> BoundsCoveringRadius( BCHCode( 17, 3, GF(2) ) ); [ 3 .. 4 ] gap> BoundsCoveringRadius( HammingCode( 5, GF(2) ) ); [ 1 ]
‣ IncreaseCoveringRadiusLowerBound( C[, stopdist][, startword] ) | ( function ) |
IncreaseCoveringRadiusLowerBound tries to increase the lower bound of the covering radius of C. It does this by means of a probabilistic algorithm. This algorithm takes a random word in GF(q)^n (or startword if it is specified), and, by changing random coordinates, tries to get as far from C as possible. If changing a coordinate finds a word that has a larger distance to the code than the previous one, the change is made permanent, and the algorithm starts all over again. If changing a coordinate does not find a coset leader that is further away from the code, then the change is made permanent with a chance of 1 in 100, if it gets the word closer to the code, or with a chance of 1 in 10, if the word stays at the same distance. Otherwise, the algorithm starts again with the same word as before.
If the algorithm did not allow changes that decrease the distance to the code, it might get stuck in a sub-optimal situation (the coset leader corresponding to such a situation - i.e. no coordinate of this coset leader can be changed in such a way that we get at a larger distance from the code - is called an orphan).
If the algorithm finds a word that has distance stopdist to the code, it ends and returns that word, which can be used for further investigations.
The variable InfoCoveringRadius can be set to Print to print the maximum distance reached so far every 1000 runs. The algorithm can be interrupted with ctrl-C, allowing the user to look at the word that is currently being examined (called `current'), or to change the chances that the new word is made permanent (these are called `staychance' and `downchance'). If one of these variables is i, then it corresponds with a i in 100 chance.
At the moment, the algorithm is only useful for codes with small dimension, where small means that the elements of the code fit in the memory. It works with larger codes, however, but when you use it for codes with large dimension, you should be very patient. If running the algorithm quits GAP (due to memory problems), you can change the global variable CRMemSize to a lower value. This might cause the algorithm to run slower, but without quitting GAP. The only way to find out the best value of CRMemSize is by experimenting.
gap> C:=RandomLinearCode(10,5,GF(2)); a [10,5,?] randomly generated code over GF(2) gap> IncreaseCoveringRadiusLowerBound(C,10); Number of runs: 1000 best distance so far: 3 Number of runs: 2000 best distance so far: 3 Number of changes: 100 Number of runs: 3000 best distance so far: 3 Number of runs: 4000 best distance so far: 3 Number of runs: 5000 best distance so far: 3 Number of runs: 6000 best distance so far: 3 Number of runs: 7000 best distance so far: 3 Number of changes: 200 Number of runs: 8000 best distance so far: 3 Number of runs: 9000 best distance so far: 3 Number of runs: 10000 best distance so far: 3 Number of changes: 300 Number of runs: 11000 best distance so far: 3 Number of runs: 12000 best distance so far: 3 Number of runs: 13000 best distance so far: 3 Number of changes: 400 Number of runs: 14000 best distance so far: 3 user interrupt at... # # used ctrl-c to break out of execution # ... called from IncreaseCoveringRadiusLowerBound( code, -1, current ) called from function( arguments ) called from read-eval-loop Entering break read-eval-print loop ... you can 'quit;' to quit to outer loop, or you can 'return;' to continue brk> current; [ Z(2)^0, Z(2)^0, Z(2)^0, Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2), Z(2)^0 ] brk> gap> CoveringRadius(C); 3
‣ ExhaustiveSearchCoveringRadius( C ) | ( function ) |
ExhaustiveSearchCoveringRadius does an exhaustive search to find the covering radius of C. Every time a coset leader of a coset with weight w is found, the function tries to find a coset leader of a coset with weight w+1. It does this by enumerating all words of weight w+1, and checking whether a word is a coset leader. The start weight is the current known lower bound on the covering radius.
gap> C:=RandomLinearCode(10,5,GF(2)); a [10,5,?] randomly generated code over GF(2) gap> ExhaustiveSearchCoveringRadius(C); Trying 3 ... [ 3 .. 5 ] gap> CoveringRadius(C); 3
‣ GeneralLowerBoundCoveringRadius( C ) | ( function ) |
GeneralLowerBoundCoveringRadius returns a lower bound on the covering radius of C. It uses as many functions which names start with LowerBoundCoveringRadius as possible to find the best known lower bound (at least that GUAVA knows of) together with tables for the covering radius of binary linear codes with length not greater than 64.
gap> C:=RandomLinearCode(10,5,GF(2)); a [10,5,?] randomly generated code over GF(2) gap> GeneralLowerBoundCoveringRadius(C); 2 gap> CoveringRadius(C); 3
‣ GeneralUpperBoundCoveringRadius( C ) | ( function ) |
GeneralUpperBoundCoveringRadius returns an upper bound on the covering radius of C. It uses as many functions which names start with UpperBoundCoveringRadius as possible to find the best known upper bound (at least that GUAVA knows of).
gap> C:=RandomLinearCode(10,5,GF(2)); a [10,5,?] randomly generated code over GF(2) gap> GeneralUpperBoundCoveringRadius(C); 4 gap> CoveringRadius(C); 3
‣ LowerBoundCoveringRadiusSphereCovering( n, M[, F], false ) | ( function ) |
This command can also be called using the syntax LowerBoundCoveringRadiusSphereCovering( n, r, [F,] true ). If the last argument of LowerBoundCoveringRadiusSphereCovering is false, then it returns a lower bound for the covering radius of a code of size M and length n. Otherwise, it returns a lower bound for the size of a code of length n and covering radius r.
F is the field over which the code is defined. If F is omitted, it is assumed that the code is over GF(2). The bound is computed according to the sphere covering bound:
M \cdot V_q(n,r) \geq q^n
where V_q(n,r) is the size of a sphere of radius r in GF(q)^n.
gap> C:=RandomLinearCode(10,5,GF(2)); a [10,5,?] randomly generated code over GF(2) gap> Size(C); 32 gap> CoveringRadius(C); 3 gap> LowerBoundCoveringRadiusSphereCovering(10,32,GF(2),false); 2 gap> LowerBoundCoveringRadiusSphereCovering(10,3,GF(2),true); 6
‣ LowerBoundCoveringRadiusVanWee1( n, M[, F], false ) | ( function ) |
This command can also be called using the syntax LowerBoundCoveringRadiusVanWee1( n, r, [F,] true ). If the last argument of LowerBoundCoveringRadiusVanWee1 is false, then it returns a lower bound for the covering radius of a code of size M and length n. Otherwise, it returns a lower bound for the size of a code of length n and covering radius r.
F is the field over which the code is defined. If F is omitted, it is assumed that the code is over GF(2).
The Van Wee bound is an improvement of the sphere covering bound:
M \cdot \left\{ V_q(n,r) - \frac{{n \choose r}}{\lceil\frac{n-r}{r+1}\rceil} \left(\left\lceil\frac{n+1}{r+1}\right\rceil - \frac{n+1}{r+1}\right) \right\} \geq q^n
gap> C:=RandomLinearCode(10,5,GF(2)); a [10,5,?] randomly generated code over GF(2) gap> Size(C); 32 gap> CoveringRadius(C); 3 gap> LowerBoundCoveringRadiusVanWee1(10,32,GF(2),false); 2 gap> LowerBoundCoveringRadiusVanWee1(10,3,GF(2),true); 6
‣ LowerBoundCoveringRadiusVanWee2( n, M, false ) | ( function ) |
This command can also be called using the syntax LowerBoundCoveringRadiusVanWee2( n, r [,true] ). If the last argument of LowerBoundCoveringRadiusVanWee2 is false, then it returns a lower bound for the covering radius of a code of size M and length n. Otherwise, it returns a lower bound for the size of a code of length n and covering radius r.
This bound only works for binary codes. It is based on the following inequality:
M \cdot \frac{\left( \left( V_2(n,2) - \frac{1}{2}(r+2)(r-1) \right) V_2(n,r) + \varepsilon V_2(n,r-2) \right)} {(V_2(n,2) - \frac{1}{2}(r+2)(r-1) + \varepsilon)} \geq 2^n,
where
\varepsilon = {r+2 \choose 2} \left\lceil {n-r+1 \choose 2} / {r+2 \choose 2} \right\rceil - {n-r+1 \choose 2}.
gap> C:=RandomLinearCode(10,5,GF(2)); a [10,5,?] randomly generated code over GF(2) gap> Size(C); 32 gap> CoveringRadius(C); 3 gap> LowerBoundCoveringRadiusVanWee2(10,32,false); 2 gap> LowerBoundCoveringRadiusVanWee2(10,3,true); 7
‣ LowerBoundCoveringRadiusCountingExcess( n, M, false ) | ( function ) |
This command can also be called with LowerBoundCoveringRadiusCountingExcess( n, r [,true] ). If the last argument of LowerBoundCoveringRadiusCountingExcess is false, then it returns a lower bound for the covering radius of a code of size M and length n. Otherwise, it returns a lower bound for the size of a code of length n and covering radius r.
This bound only works for binary codes. It is based on the following inequality:
M \cdot \left( \rho V_2(n,r) + \varepsilon V_2(n,r-1) \right) \geq (\rho + \varepsilon) 2^n,
where
\varepsilon = (r+1) \left\lceil\frac{n+1}{r+1}\right\rceil - (n+1)
and
\rho = \left\{ \begin{array}{l} n-3+\frac{2}{n}, \ \ \ \ \ \ {\rm if}\ r = 2\\ n-r-1 , \ \ \ \ \ \ {\rm if}\ r \geq 3 . \end{array} \right.
gap> C:=RandomLinearCode(10,5,GF(2)); a [10,5,?] randomly generated code over GF(2) gap> Size(C); 32 gap> CoveringRadius(C); 3 gap> LowerBoundCoveringRadiusCountingExcess(10,32,false); 0 gap> LowerBoundCoveringRadiusCountingExcess(10,3,true); 7
‣ LowerBoundCoveringRadiusEmbedded1( n, M, false ) | ( function ) |
This command can also be called with LowerBoundCoveringRadiusEmbedded1( n, r [,true] ). If the last argument of LowerBoundCoveringRadiusEmbedded1 is 'false', then it returns a lower bound for the covering radius of a code of size M and length n. Otherwise, it returns a lower bound for the size of a code of length n and covering radius r.
This bound only works for binary codes. It is based on the following inequality:
M \cdot \left( V_2(n,r) - {2r \choose r} \right) \geq 2^n - A( n, 2r+1 ) {2r \choose r},
where A(n,d) denotes the maximal cardinality of a (binary) code of length n and minimum distance d. The function UpperBound is used to compute this value.
Sometimes LowerBoundCoveringRadiusEmbedded1 is better than LowerBoundCoveringRadiusEmbedded2, sometimes it is the other way around.
gap> C:=RandomLinearCode(10,5,GF(2)); a [10,5,?] randomly generated code over GF(2) gap> Size(C); 32 gap> CoveringRadius(C); 3 gap> LowerBoundCoveringRadiusEmbedded1(10,32,false); 2 gap> LowerBoundCoveringRadiusEmbedded1(10,3,true); 7
‣ LowerBoundCoveringRadiusEmbedded2( n, M, false ) | ( function ) |
This command can also be called with LowerBoundCoveringRadiusEmbedded2( n, r [,true] ). If the last argument of LowerBoundCoveringRadiusEmbedded2 is 'false', then it returns a lower bound for the covering radius of a code of size M and length n. Otherwise, it returns a lower bound for the size of a code of length n and covering radius r.
This bound only works for binary codes. It is based on the following inequality:
M \cdot \left( V_2(n,r) - \frac{3}{2} {2r \choose r} \right) \geq 2^n - 2A( n, 2r+1 ) {2r \choose r},
where A(n,d) denotes the maximal cardinality of a (binary) code of length n and minimum distance d. The function UpperBound is used to compute this value.
Sometimes LowerBoundCoveringRadiusEmbedded1 is better than LowerBoundCoveringRadiusEmbedded2, sometimes it is the other way around.
gap> C:=RandomLinearCode(15,5,GF(2)); a [15,5,?] randomly generated code over GF(2) gap> Size(C); 32 gap> CoveringRadius(C); 6 gap> LowerBoundCoveringRadiusEmbedded2(10,32,false); 2 gap> LowerBoundCoveringRadiusEmbedded2(10,3,true); 7
‣ LowerBoundCoveringRadiusInduction( n, r ) | ( function ) |
LowerBoundCoveringRadiusInduction returns a lower bound for the size of a code with length n and covering radius r.
If n = 2r+2 and r ≥ 1, the returned value is 4.
If n = 2r+3 and r ≥ 1, the returned value is 7.
If n = 2r+4 and r ≥ 4, the returned value is 8.
Otherwise, 0 is returned.
gap> C:=RandomLinearCode(15,5,GF(2)); a [15,5,?] randomly generated code over GF(2) gap> CoveringRadius(C); 5 gap> LowerBoundCoveringRadiusInduction(15,6); 7
‣ UpperBoundCoveringRadiusRedundancy( C ) | ( function ) |
UpperBoundCoveringRadiusRedundancy returns the redundancy of C as an upper bound for the covering radius of C. C must be a linear code.
gap> C:=RandomLinearCode(15,5,GF(2)); a [15,5,?] randomly generated code over GF(2) gap> CoveringRadius(C); 5 gap> UpperBoundCoveringRadiusRedundancy(C); 10
‣ UpperBoundCoveringRadiusDelsarte( C ) | ( function ) |
UpperBoundCoveringRadiusDelsarte returns an upper bound for the covering radius of C. This upper bound is equal to the external distance of C, this is the minimum distance of the dual code, if C is a linear code.
This is described in Theorem 11.3.3 of [HP03].
gap> C:=RandomLinearCode(15,5,GF(2)); a [15,5,?] randomly generated code over GF(2) gap> CoveringRadius(C); 5 gap> UpperBoundCoveringRadiusDelsarte(C); 13
‣ UpperBoundCoveringRadiusStrength( C ) | ( function ) |
UpperBoundCoveringRadiusStrength returns an upper bound for the covering radius of C.
First the code is punctured at the zero coordinates (i.e. the coordinates where all codewords have a zero). If the remaining code has strength 1 (i.e. each coordinate contains each element of the field an equal number of times), then it returns fracq-1qm + (n-m) (where q is the size of the field and m is the length of punctured code), otherwise it returns n. This bound works for all codes.
gap> C:=RandomLinearCode(15,5,GF(2)); a [15,5,?] randomly generated code over GF(2) gap> CoveringRadius(C); 5 gap> UpperBoundCoveringRadiusStrength(C); 7
‣ UpperBoundCoveringRadiusGriesmerLike( C ) | ( function ) |
This function returns an upper bound for the covering radius of C, which must be linear, in a Griesmer-like fashion. It returns
n - \sum_{i=1}^k \left\lceil \frac{d}{q^i} \right\rceil
gap> C:=RandomLinearCode(15,5,GF(2)); a [15,5,?] randomly generated code over GF(2) gap> CoveringRadius(C); 5 gap> UpperBoundCoveringRadiusGriesmerLike(C); 9
‣ UpperBoundCoveringRadiusCyclicCode( C ) | ( function ) |
This function returns an upper bound for the covering radius of C, which must be a cyclic code. It returns
n - k + 1 - \left\lceil \frac{w(g(x))}{2} \right\rceil,
where g(x) is the generator polynomial of C.
gap> C:=CyclicCodes(15,GF(2))[3]; a cyclic [15,12,1..2]1..3 enumerated code over GF(2) gap> CoveringRadius(C); 3 gap> UpperBoundCoveringRadiusCyclicCode(C); 3
This section explains functions that work with special matrices GUAVA needs for several codes.
Firstly, we describe some matrix generating functions (see KrawtchoukMat (7.3-1), GrayMat (7.3-2), SylvesterMat (7.3-3), HadamardMat (7.3-4) and MOLS (7.3-11)).
Next we describe two functions regarding a standard form of matrices (see PutStandardForm (7.3-6) and IsInStandardForm (7.3-7)).
Then we describe functions that return a matrix after a manipulation (see PermutedCols (7.3-8), VerticalConversionFieldMat (7.3-9) and HorizontalConversionFieldMat (7.3-10)).
Finally, we describe functions that do some tests on matrices (see IsLatinSquare (7.3-12) and AreMOLS (7.3-13)).
‣ KrawtchoukMat( n, q ) | ( function ) |
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 (7.5-6)). 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 ) | ( function ) |
GrayMat returns a list of all different vectors (see GAP's Vectors command) of length n over the field F, using Gray ordering. 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 ) | ( function ) |
SylvesterMat returns the n× n Sylvester matrix of order n. This is a special case of the Hadamard matrices (see HadamardMat (7.3-4)). 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 ) | ( function ) |
HadamardMat returns a Hadamard matrix of order n. This is an n× 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 (as of 1998), 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 (the Paley Type I and II constructions, and the Sylvester construction -- see SylvesterMat (7.3-3)). 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 yet have an implementation for a Hadamard matrix in GUAVA: 52, 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
‣ VandermondeMat( X, a ) | ( function ) |
The function VandermondeMat returns the (a+1)× n matrix of powers x_i^j where X is a list of elements of a field, X={ x_1,...,x_n}, and a is a non-negative integer.
gap> M:=VandermondeMat([Z(5),Z(5)^2,Z(5)^0,Z(5)^3],2); [ [ Z(5)^0, Z(5), Z(5)^2 ], [ Z(5)^0, Z(5)^2, Z(5)^0 ], [ Z(5)^0, Z(5)^0, Z(5)^0 ], [ Z(5)^0, Z(5)^3, Z(5)^2 ] ] gap> Display(M); 1 2 4 1 4 1 1 1 1 1 3 4
‣ PutStandardForm( M[, idleft] ) | ( function ) |
We say that a k× n matrix is in standard form if it is equal to the block matrix (I | A), for some k× (n-k) matrix A and where I is the k× k identity matrix. It follows from a basis result in linear algebra that, after a possible permutation of the columns, using elementary row operations, every matrix can be reduced to standard form. 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. (The default for idleft is `true'.) If idleft is set to `true', the identity matrix is put on the left side of M. Otherwise, it is put at the right side. (This option is useful when putting a check matrix of a code into standard form.) 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) ] ] gap> C := BestKnownLinearCode( 23, 12, GF(2) ); a linear [23,12,7]3 punctured code gap> G:=MutableCopyMat(GeneratorMat(C));; gap> PutStandardForm(G); () gap> Display(G); 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 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
‣ IsInStandardForm( M[, idleft] ) | ( function ) |
IsInStandardForm determines if M is in standard form. idleft is a boolean that indicates the position of the identity matrix in M, as in PutStandardForm (see PutStandardForm (7.3-6)). IsInStandardForm checks if the identity matrix is at the left side of M, otherwise if it is at the right side. The elements of M may be elements of any field.
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 ) | ( function ) |
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 ) | ( function ) |
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, using the GF(p)-vector space isomorphism
[...] : GF(q)\rightarrow GF(p)^m,
with q=p^m.
If M is a k by n matrix, the result is a k⋅ m × 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 (7.3-10)).
‣ HorizontalConversionFieldMat( M, F ) | ( function ) |
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 × n matrix, the result is a k× m× 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 (6.1-15)).
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 (7.3-9)).
‣ MOLS( q[, n] ) | ( function ) |
MOLS returns a list of n Mutually Orthogonal Latin Squares (MOLS). A Latin square of order q is a q× 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. However, GUAVA does not yet construct MOLS for q≡ 2 mod 4. If it is not possible to construct n MOLS, the function returns `false'.
MOLS are used to create q-ary codes (see MOLSCode (5.1-4)).
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
‣ IsLatinSquare( M ) | ( function ) |
IsLatinSquare determines if a matrix M is a Latin square. For a Latin square of size n× n, each row and each column contains all the integers 1,dots,n exactly once.
gap> IsLatinSquare([[1,2],[2,1]]); true gap> IsLatinSquare([[1,2,3],[2,3,1],[1,3,2]]); false
‣ AreMOLS( L ) | ( function ) |
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 (7.3-11)).
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
In this section, some functions that can be used to compute the norm of a code and to decide upon its normality are discussed. Typically, these are applied to binary linear codes. The definitions of this section were introduced in Graham and Sloane [GS85].
‣ CoordinateNorm( C, coord ) | ( function ) |
CoordinateNorm returns the norm of C with respect to coordinate coord. If C_a = { c ∈ C | c_coord = a }, then the norm of C with respect to coord is defined as
\max_{v \in GF(q)^n} \sum_{a=1}^q d(x,C_a),
with the convention that d(x,C_a) = n if C_a is empty.
gap> CoordinateNorm( HammingCode( 3, GF(2) ), 3 ); 3
‣ CodeNorm( C ) | ( function ) |
CodeNorm returns the norm of C. The norm of a code is defined as the minimum of the norms for the respective coordinates of the code. In effect, for each coordinate CoordinateNorm is called, and the minimum of the calculated numbers is returned.
gap> CodeNorm( HammingCode( 3, GF(2) ) ); 3
‣ IsCoordinateAcceptable( C, coord ) | ( function ) |
IsCoordinateAcceptable returns `true' if coordinate coord of C is acceptable. A coordinate is called acceptable if the norm of the code with respect to that coordinate is not more than two times the covering radius of the code plus one.
gap> IsCoordinateAcceptable( HammingCode( 3, GF(2) ), 3 ); true
‣ GeneralizedCodeNorm( C, subcode1, subscode2, ..., subcodek ) | ( function ) |
GeneralizedCodeNorm returns the k-norm of C with respect to k subcodes.
gap> c := RepetitionCode( 7, GF(2) );; gap> ham := HammingCode( 3, GF(2) );; gap> d := EvenWeightSubcode( ham );; gap> e := ConstantWeightSubcode( ham, 3 );; gap> GeneralizedCodeNorm( ham, c, d, e ); 4
‣ IsNormalCode( C ) | ( function ) |
IsNormalCode returns `true' if C is normal. A code is called normal if the norm of the code is not more than two times the covering radius of the code plus one. Almost all codes are normal, however some (non-linear) abnormal codes have been found.
Often, it is difficult to find out whether a code is normal, because it involves computing the covering radius. However, IsNormalCode uses much information from the literature (in particular, [GS85]) about normality for certain code parameters.
gap> IsNormalCode( HammingCode( 3, GF(2) ) ); true
In this section we describe several vector space functions GUAVA uses for constructing codes or performing calculations with codes.
In this section, some new miscellaneous functions are described, including weight enumerators, the MacWilliams-transform and affinity and almost affinity of codes.
‣ CodeWeightEnumerator( C ) | ( function ) |
CodeWeightEnumerator returns a polynomial of the following form:
f(x) = \sum_{i=0}^{n} A_i x^i,
where A_i is the number of codewords in C with weight i.
gap> CodeWeightEnumerator( ElementsCode( [ [ 0,0,0 ], [ 0,0,1 ], > [ 0,1,1 ], [ 1,1,1 ] ], GF(2) ) ); x^3 + x^2 + x + 1 gap> CodeWeightEnumerator( HammingCode( 3, GF(2) ) ); x^7 + 7*x^4 + 7*x^3 + 1
‣ CodeDistanceEnumerator( C, w ) | ( function ) |
CodeDistanceEnumerator returns a polynomial of the following form:
f(x) = \sum_{i=0}^{n} B_i x^i,
where B_i is the number of codewords with distance i to w.
If w is a codeword, then CodeDistanceEnumerator returns the same polynomial as CodeWeightEnumerator.
gap> CodeDistanceEnumerator( HammingCode( 3, GF(2) ),[0,0,0,0,0,0,1] ); x^6 + 3*x^5 + 4*x^4 + 4*x^3 + 3*x^2 + x gap> CodeDistanceEnumerator( HammingCode( 3, GF(2) ),[1,1,1,1,1,1,1] ); x^7 + 7*x^4 + 7*x^3 + 1 # `[1,1,1,1,1,1,1]' $\in$ `HammingCode( 3, GF(2 ) )'
‣ CodeMacWilliamsTransform( C ) | ( function ) |
CodeMacWilliamsTransform returns a polynomial of the following form:
f(x) = \sum_{i=0}^{n} C_i x^i,
where C_i is the number of codewords with weight i in the dual code of C.
gap> CodeMacWilliamsTransform( HammingCode( 3, GF(2) ) ); 7*x^4 + 1
‣ CodeDensity( C ) | ( function ) |
CodeDensity returns the density of C. The density of a code is defined as
\frac{M \cdot V_q(n,t)}{q^n},
where M is the size of the code, V_q(n,t) is the size of a sphere of radius t in GF(q^n) (which may be computed using SphereContent), t is the covering radius of the code and n is the length of the code.
gap> CodeDensity( HammingCode( 3, GF(2) ) ); 1 gap> CodeDensity( ReedMullerCode( 1, 4 ) ); 14893/2048
‣ SphereContent( n, t, F ) | ( function ) |
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 (3.6-2) 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 partition the whole ambient vector space, 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 ) | ( function ) |
Krawtchouk returns the Krawtchouk number K_k(i). q must be a prime power, 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 (7.3-1)). This number is the value at x=i of the polynomial
K_k^{n,q}(x) =\sum_{j=0}^n (-1)^j(q-1)^{k-j}b(x,j)b(n-x,k-j),
where $b(v,u)=u!/(v!(v-u)!)$ is the binomial coefficient if $u,v$ are integers. For more properties of these polynomials, see [MS83].
gap> Krawtchouk( 2, 0, 3, 2); 3
‣ PrimitiveUnityRoot( F, n ) | ( function ) |
PrimitiveUnityRoot returns a primitive n-th root of unity in an extension field of F. This is a finite field element a with the property a^n=1 in F, 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
‣ PrimitivePolynomialsNr( n, F ) | ( function ) |
PrimitivePolynomialsNr returns the number of irreducible polynomials over F=GF(q) of degree n with (maximum) period q^n-1. (According to a theorem of S. Golomb, this is ϕ(p^n-1)/n.)
See also the GAP function RandomPrimitivePolynomial, RandomPrimitivePolynomial (8.2-2).
gap> PrimitivePolynomialsNr(3,4); 12
‣ IrreduciblePolynomialsNr( n, F ) | ( function ) |
PrimitivePolynomialsNr returns the number of irreducible polynomials over F=GF(q) of degree n.
gap> IrreduciblePolynomialsNr(3,4); 20
‣ MatrixRepresentationOfElement( a, F ) | ( function ) |
Here F is either a finite extension of the ``base field'' GF(p) or of the rationals Q}, and a∈ F. The command MatrixRepresentationOfElement returns a matrix representation of a over the base field.
If the element a is defined over the base field then it returns the corresponding 1× 1 matrix.
gap> a:=Random(GF(4)); 0*Z(2) gap> M:=MatrixRepresentationOfElement(a,GF(4));; Display(M); . gap> a:=Random(GF(4)); Z(2^2) gap> M:=MatrixRepresentationOfElement(a,GF(4));; Display(M); . 1 1 1
‣ ReciprocalPolynomial( P ) | ( function ) |
ReciprocalPolynomial returns the reciprocal of polynomial P. This is a polynomial with coefficients of P in the reverse order. So if P=a_0 + a_1 X + ... + a_n X^n, the reciprocal polynomial is P'=a_n + a_n-1 X + ... + a_0 X^n.
This command can also be called using the syntax ReciprocalPolynomial( P , n ). In this form, the number of coefficients of P is assumed to be less than or equal to n+1 (with zero coefficients added in the highest degrees, if necessary). Therefore, the reciprocal polynomial also has degree n+1.
gap> P := UnivariatePolynomial( GF(3), Z(3)^0 * [1,0,1,2] ); -x_1^3+x_1^2+Z(3)^0 gap> RecP := ReciprocalPolynomial( P ); x_1^3+x_1-Z(3)^0 gap> ReciprocalPolynomial( RecP ) = P; true gap> P := UnivariatePolynomial( GF(3), Z(3)^0 * [1,0,1,2] ); -x_1^3+x_1^2+Z(3)^0 gap> ReciprocalPolynomial( P, 6 ); x_1^6+x_1^4-x_1^3
‣ CyclotomicCosets( q, n ) | ( function ) |
CyclotomicCosets returns the cyclotomic cosets of q mod 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. A q-cyclotomic coset of s mod n is a set of the form {s,sq,sq^2,...,sq^r-1}, where r is the smallest positive integer such that sq^r-s is 0 mod n. In other words, each coset contains all multiplications of the coset representative by q mod 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[, h] ) | ( function ) |
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
‣ MultiplicityInList( L, a ) | ( function ) |
This is a very simple list command which returns how many times a occurs in L. It returns 0 if a is not in L. (The GAP command Collected does not quite handle this "extreme" case.)
gap> L:=[1,2,3,4,3,2,1,5,4,3,2,1];; gap> MultiplicityInList(L,1); 3 gap> MultiplicityInList(L,6); 0
‣ MostCommonInList( L ) | ( function ) |
Input: a list L
Output: an a in L which occurs at least as much as any other in L
gap> L:=[1,2,3,4,3,2,1,5,4,3,2,1];; gap> MostCommonInList(L); 1
‣ RotateList( L ) | ( function ) |
Input: a list L
Output: a list L' which is the cyclic rotation of L (to the right)
gap> L:=[1,2,3,4];; gap> RotateList(L); [2,3,4,1]
‣ CirculantMatrix( k, L ) | ( function ) |
Input: integer k, a list L of length n
Output: kxn matrix whose rows are cyclic rotations of the list L
gap> k:=3; L:=[1,2,3,4];; gap> M:=CirculantMatrix(k,L);; gap> Display(M);
In this section we describe several multivariate polynomial GAP functions GUAVA uses for constructing codes or performing calculations with codes.
‣ MatrixTransformationOnMultivariatePolynomial ( A, f, R ) | ( function ) |
A is an n× n matrix with entries in a field F, R is a polynomial ring of n variables, say F[x_1,...,x_n], and f is a polynomial in R. Returns the composition f∘ A.
‣ DegreeMultivariatePolynomial( f, R ) | ( function ) |
This command takes two arguments, f, a multivariate polynomial, and R a polynomial ring over a field F containing f, say R=F[x_1,x_2,...,x_n]. The output is simply the maximum degrees of all the monomials occurring in f.
This command can be used to compute the degree of an affine plane curve.
gap> F:=GF(11);; gap> R2:=PolynomialRing(F,2); PolynomialRing(..., [ x_1, x_2 ]) gap> vars:=IndeterminatesOfPolynomialRing(R2);; gap> x:=vars[1];; y:=vars[2];; gap> poly:=y^2-x*(x^2-1);; gap> DegreeMultivariatePolynomial(poly,R2); 3
‣ DegreesMultivariatePolynomial( f, R ) | ( function ) |
Returns a list of information about the multivariate polynomial f. Nice for other programs but mostly unreadable by GAP users.
gap> F:=GF(11);; gap> R2:=PolynomialRing(F,2); PolynomialRing(..., [ x_1, x_2 ]) gap> vars:=IndeterminatesOfPolynomialRing(R2);; gap> x:=vars[1];; y:=vars[2];; gap> poly:=y^2-x*(x^2-1);; gap> DegreesMultivariatePolynomial(poly,R2); [ [ [ x_1, x_1, 1 ], [ x_1, x_2, 0 ] ], [ [ x_2^2, x_1, 0 ], [ x_2^2, x_2, 2 ] ], [ [ x_1^3, x_1, 3 ], [ x_1^3, x_2, 0 ] ] ]
‣ CoefficientMultivariatePolynomial( f, var, power, R ) | ( function ) |
The command CoefficientMultivariatePolynomial takes four arguments: a multivariant polynomial f, a variable name var, an integer power, and a polynomial ring R containing f. For example, if f is a multivariate polynomial in R = F[x_1,x_2,...,x_n] then var must be one of the x_i. The output is the coefficient of x_i^power in f.
(Not sure if F needs to be a field in fact ...)
Related to the GAP command PolynomialCoefficientsPolynomial.
gap> F:=GF(11);; gap> R2:=PolynomialRing(F,2); PolynomialRing(..., [ x_1, x_2 ]) gap> vars:=IndeterminatesOfPolynomialRing(R2);; gap> x:=vars[1];; y:=vars[2];; gap> poly:=y^2-x*(x^2-1);; gap> PolynomialCoefficientsOfPolynomial(poly,x); [ x_2^2, Z(11)^0, 0*Z(11), -Z(11)^0 ] gap> PolynomialCoefficientsOfPolynomial(poly,y); [ -x_1^3+x_1, 0*Z(11), Z(11)^0 ] gap> CoefficientMultivariatePolynomial(poly,y,0,R2); -x_1^3+x_1 gap> CoefficientMultivariatePolynomial(poly,y,1,R2); 0*Z(11) gap> CoefficientMultivariatePolynomial(poly,y,2,R2); Z(11)^0 gap> CoefficientMultivariatePolynomial(poly,x,0,R2); x_2^2 gap> CoefficientMultivariatePolynomial(poly,x,1,R2); Z(11)^0 gap> CoefficientMultivariatePolynomial(poly,x,2,R2); 0*Z(11) gap> CoefficientMultivariatePolynomial(poly,x,3,R2); -Z(11)^0
‣ SolveLinearSystem( L, vars ) | ( function ) |
Input: L is a list of linear forms in the variables vars.
Output: the solution of the system, if its unique.
The procedure is straightforward: Find the associated matrix A, find the "constant vector" b, and solve A*v=b. No error checking is performed.
Related to the GAP command SolutionMat( A, b ).
gap> F:=GF(11);; gap> R2:=PolynomialRing(F,2); PolynomialRing(..., [ x_1, x_2 ]) gap> vars:=IndeterminatesOfPolynomialRing(R2);; gap> x:=vars[1];; y:=vars[2];; gap> f:=3*y-3*x+1;; g:=-5*y+2*x-7;; gap> soln:=SolveLinearSystem([f,g],[x,y]); [ Z(11)^3, Z(11)^2 ] gap> Value(f,[x,y],soln); # checking okay 0*Z(11) gap> Value(g,[x,y],col); # checking okay 0*Z(11)
‣ GuavaVersion( ) | ( function ) |
Returns the current version of Guava. Same as guava\_version().
gap> GuavaVersion(); "3.19"
‣ ZechLog( x, b, F ) | ( function ) |
Returns the Zech log of x to base b, ie the i such that $x+1=b^i$, so $y+z=y(1+z/y)=b^k$, where k=Log(y,b)+ZechLog(z/y,b) and b must be a primitive element of F.
gap> F:=GF(11);; l := One(F);; gap> ZechLog(2*l,8*l,F); -24 gap> 8*l+l;(2*l)^(-24); Z(11)^6 Z(11)^6
‣ CoefficientToPolynomial( coeffs, R ) | ( function ) |
The function CoefficientToPolynomial returns the degree d-1 polynomial c_0+c_1x+...+c_d-1x^d-1, where coeffs is a list of elements of a field, coeffs={ c_0,...,c_d-1}, and R is a univariate polynomial ring.
gap> F:=GF(11); GF(11) gap> R1:=PolynomialRing(F,["a"]);; gap> var1:=IndeterminatesOfPolynomialRing(R1);; a:=var1[1];; gap> coeffs:=Z(11)^0*[1,2,3,4]; [ Z(11)^0, Z(11), Z(11)^8, Z(11)^2 ] gap> CoefficientToPolynomial(coeffs,R1); Z(11)^2*a^3+Z(11)^8*a^2+Z(11)*a+Z(11)^0
‣ DegreesMonomialTerm( m, R ) | ( function ) |
The function DegreesMonomialTerm returns the list of degrees to which each variable in the multivariate polynomial ring R occurs in the monomial m, where coeffs is a list of elements of a field.
gap> F:=GF(11); GF(11) gap> R1:=PolynomialRing(F,["a"]);; gap> var1:=IndeterminatesOfPolynomialRing(R1);; a:=var1[1];; gap> b:=X(F,"b",var1); b gap> var2:=Concatenation(var1,[b]); [ a, b ] gap> R2:=PolynomialRing(F,var2); PolynomialRing(..., [ a, b ]) gap> c:=X(F,"c",var2); c gap> var3:=Concatenation(var2,[c]); [ a, b, c ] gap> R3:=PolynomialRing(F,var3); PolynomialRing(..., [ a, b, c ]) gap> m:=b^3*c^7; b^3*c^7 gap> DegreesMonomialTerm(m,R3); [ 0, 3, 7 ]
‣ DivisorsMultivariatePolynomial( f, R ) | ( function ) |
The function DivisorsMultivariatePolynomial returns the list of polynomial divisors of f in the multivariate polynomial ring R with coefficients in a field. This program uses a simple but slow algorithm (see Joachim von zur Gathen, Jürgen Gerhard, [vzGG03], exercise 16.10) which first converts the multivariate polynomial f to an associated univariate polynomial f^*, then Factors f^*, and finally converts these univariate factors back into the multivariate polynomial factors of f. Since Factors is non-deterministic, DivisorsMultivariatePolynomial is non-deterministic as well.
gap> R2:=PolynomialRing(GF(3),["x1","x2"]); GF(3)[x1,x2] gap> vars:=IndeterminatesOfPolynomialRing(R2); [ x1, x2 ] gap> x2:=vars[2]; x2 gap> x1:=vars[1]; x1 gap> f:=x1^3+x2^3;; gap> DivisorsMultivariatePolynomial(f,R2); [ x1+x2, x1+x2, x1+x2 ]
generated by GAPDoc2HTML