Goto Chapter: Top 1 2 3 4 5 6 7 Bib Ind

### 7 Bounds on codes, special matrices and miscellaneous functions

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

#### 7.1 Distance 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 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)).

##### 7.1-1 UpperBoundSingleton
 > 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 

##### 7.1-2 UpperBoundHamming
 > 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 lfloor(d-1) / 2rfloor. 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 maxmimum 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 

##### 7.1-3 UpperBoundJohnson
 > 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 

##### 7.1-4 UpperBoundPlotkin
 > 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 ] 

##### 7.1-5 UpperBoundElias
 > 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 

##### 7.1-6 UpperBoundGriesmer
 > 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 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 

##### 7.1-7 IsGriesmerCode
 > 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 

##### 7.1-8 UpperBound
 > 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* ell-1) = A(n+1,2* ell), so the UpperBound takes the minimum of the values obtained from all methods for the parameters (n, 2*ell-1) and (n+1, 2* ell).

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

##### 7.1-9 LowerBoundMinimumDistance
 > 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 

##### 7.1-10 LowerBoundGilbertVarshamov
 > 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 

##### 7.1-11 LowerBoundSpherePacking
 > 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 

##### 7.1-12 UpperBoundMinimumDistance
 > 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 

##### 7.1-13 BoundsMinimumDistance
 > 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], http://www.win.tue.nl/~aeb/voorlincod.html 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) 

#### 7.2 Covering radius bounds on codes

 > 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 , 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 

#### 7.3 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 (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)).

##### 7.3-1 KrawtchoukMat
 > 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 ] 

##### 7.3-2 GrayMat
 > 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) ] 

##### 7.3-3 SylvesterMat
 > SylvesterMat( n ) ( function )

SylvesterMat returns the nx 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 nx 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 

##### 7.3-5 VandermondeMat
 > VandermondeMat( X, a ) ( function )

The function VandermondeMat returns the (a+1)x 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 

##### 7.3-6 PutStandardForm
 > PutStandardForm( M[, idleft] ) ( function )

We say that a kx n matrix is in standard form if it is equal to the block matrix (I | A), for some kx (n-k) matrix A and where I is the kx 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 

##### 7.3-7 IsInStandardForm
 > 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 

##### 7.3-8 PermutedCols
 > 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 ] ] 

##### 7.3-9 VerticalConversionFieldMat
 > 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 x 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)).

##### 7.3-10 HorizontalConversionFieldMat
 > 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 x n matrix, the result is a kx mx 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 kx 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)).

##### 7.3-11 MOLS
 > MOLS( q[, n] ) ( function )

MOLS returns a list of n Mutually Orthogonal Latin Squares (MOLS). A Latin square of order q is a qx 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 

##### 7.3-12 IsLatinSquare
 > IsLatinSquare( M ) ( function )

IsLatinSquare determines if a matrix M is a Latin square. For a Latin square of size nx 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 

##### 7.3-13 AreMOLS
 > 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 

#### 7.4 Some functions related to the norm of a code

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].

##### 7.4-1 CoordinateNorm
 > CoordinateNorm( C, coord ) ( function )

CoordinateNorm returns the norm of C with respect to coordinate coord. If C_a = { c in 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 

##### 7.4-2 CodeNorm
 > 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 

##### 7.4-3 IsCoordinateAcceptable
 > 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 

##### 7.4-4 GeneralizedCodeNorm
 > 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 

##### 7.4-5 IsNormalCode
 > 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 

#### 7.5 Miscellaneous functions

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.

##### 7.5-1 CodeWeightEnumerator
 > 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 

##### 7.5-2 CodeDistanceEnumerator
 > 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 ) )' 

##### 7.5-3 CodeMacWilliamsTransform
 > 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 

##### 7.5-4 CodeDensity
 > 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 

##### 7.5-5 SphereContent
 > 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 

##### 7.5-6 Krawtchouk
 > 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 

##### 7.5-7 PrimitiveUnityRoot
 > 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 

##### 7.5-8 PrimitivePolynomialsNr
 > 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 phi(p^n-1)/n.)

See also the GAP function RandomPrimitivePolynomial, RandomPrimitivePolynomial (2.2-2).

 gap> PrimitivePolynomialsNr(3,4); 12 

##### 7.5-9 IrreduciblePolynomialsNr
 > IrreduciblePolynomialsNr( n, F ) ( function )

PrimitivePolynomialsNr returns the number of irreducible polynomials over F=GF(q) of degree n.

 gap> IrreduciblePolynomialsNr(3,4); 20 

##### 7.5-10 MatrixRepresentationOfElement
 > MatrixRepresentationOfElement( a, F ) ( function )

Here F is either a finite extension of the base field'' GF(p) or of the rationals Q}, and ain 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 1x 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 gap> 

##### 7.5-11 ReciprocalPolynomial
 > 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] ); 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 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 

##### 7.5-12 CyclotomicCosets
 > 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 ] ] 

##### 7.5-13 WeightHistogram
 > 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 

##### 7.5-14 MultiplicityInList
 > 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 

##### 7.5-15 MostCommonInList
 > 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 

##### 7.5-16 RotateList
 > 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] 

##### 7.5-17 CirculantMatrix
 > 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); 

#### 7.6 Miscellaneous polynomial functions

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

##### 7.6-1 MatrixTransformationOnMultivariatePolynomial
 > MatrixTransformationOnMultivariatePolynomial ( A, f, R ) ( function )

A is an nx 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 fcirc A.

##### 7.6-2 DegreeMultivariatePolynomial
 > 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 

##### 7.6-3 DegreesMultivariatePolynomial
 > 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 ] ] ] gap> 

##### 7.6-4 CoefficientMultivariatePolynomial
 > 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 

##### 7.6-5 SolveLinearSystem
 > 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) 

##### 7.6-6 GuavaVersion
 > GuavaVersion( ) ( function )

Returns the current version of Guava. Same as guava\_version().

 gap> GuavaVersion(); "2.7" 

##### 7.6-7 ZechLog
 > 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 

##### 7.6-8 CoefficientToPolynomial
 > 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 

##### 7.6-9 DegreesMonomialTerm
 > 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 ] 

##### 7.6-10 DivisorsMultivariatePolynomial
 > 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, [GG03], 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"]); PolynomialRing(..., [ 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 ] 

#### 7.7 GNU Free Documentation License

GNU Free Documentation License Version 1.2, November 2002

Copyright (C) 2000,2001,2002 Free Software Foundation, Inc. 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA Everyone is permitted to copy and distribute verbatim copies of this license document, but changing it is not allowed.

0. PREAMBLE

The purpose of this License is to make a manual, textbook, or other functional and useful document "free" in the sense of freedom: to assure everyone the effective freedom to copy and redistribute it, with or without modifying it, either commercially or noncommercially. Secondarily, this License preserves for the author and publisher a way to get credit for their work, while not being considered responsible for modifications made by others.

This License is a kind of "copyleft", which means that derivative works of the document must themselves be free in the same sense. It complements the GNU General Public License, which is a copyleft license designed for free software.

We have designed this License in order to use it for manuals for free software, because free software needs free documentation: a free program should come with manuals providing the same freedoms that the software does. But this License is not limited to software manuals; it can be used for any textual work, regardless of subject matter or whether it is published as a printed book. We recommend this License principally for works whose purpose is instruction or reference.

1. APPLICABILITY AND DEFINITIONS

This License applies to any manual or other work, in any medium, that contains a notice placed by the copyright holder saying it can be distributed under the terms of this License. Such a notice grants a world-wide, royalty-free license, unlimited in duration, to use that work under the conditions stated herein. The "Document", below, refers to any such manual or work. Any member of the public is a licensee, and is addressed as "you". You accept the license if you copy, modify or distribute the work in a way requiring permission under copyright law.

A "Modified Version" of the Document means any work containing the Document or a portion of it, either copied verbatim, or with modifications and/or translated into another language.

A "Secondary Section" is a named appendix or a front-matter section of the Document that deals exclusively with the relationship of the publishers or authors of the Document to the Document's overall subject (or to related matters) and contains nothing that could fall directly within that overall subject. (Thus, if the Document is in part a textbook of mathematics, a Secondary Section may not explain any mathematics.) The relationship could be a matter of historical connection with the subject or with related matters, or of legal, commercial, philosophical, ethical or political position regarding them.

The "Invariant Sections" are certain Secondary Sections whose titles are designated, as being those of Invariant Sections, in the notice that says that the Document is released under this License. If a section does not fit the above definition of Secondary then it is not allowed to be designated as Invariant. The Document may contain zero Invariant Sections. If the Document does not identify any Invariant Sections then there are none.

The "Cover Texts" are certain short passages of text that are listed, as Front-Cover Texts or Back-Cover Texts, in the notice that says that the Document is released under this License. A Front-Cover Text may be at most 5 words, and a Back-Cover Text may be at most 25 words.

A "Transparent" copy of the Document means a machine-readable copy, represented in a format whose specification is available to the general public, that is suitable for revising the document straightforwardly with generic text editors or (for images composed of pixels) generic paint programs or (for drawings) some widely available drawing editor, and that is suitable for input to text formatters or for automatic translation to a variety of formats suitable for input to text formatters. A copy made in an otherwise Transparent file format whose markup, or absence of markup, has been arranged to thwart or discourage subsequent modification by readers is not Transparent. An image format is not Transparent if used for any substantial amount of text. A copy that is not "Transparent" is called "Opaque".

Examples of suitable formats for Transparent copies include plain ASCII without markup, Texinfo input format, LaTeX input format, SGML or XML using a publicly available DTD, and standard-conforming simple HTML, PostScript or PDF designed for human modification. Examples of transparent image formats include PNG, XCF and JPG. Opaque formats include proprietary formats that can be read and edited only by proprietary word processors, SGML or XML for which the DTD and/or processing tools are not generally available, and the machine-generated HTML, PostScript or PDF produced by some word processors for output purposes only.

The "Title Page" means, for a printed book, the title page itself, plus such following pages as are needed to hold, legibly, the material this License requires to appear in the title page. For works in formats which do not have any title page as such, "Title Page" means the text near the most prominent appearance of the work's title, preceding the beginning of the body of the text.

A section "Entitled XYZ" means a named subunit of the Document whose title either is precisely XYZ or contains XYZ in parentheses following text that translates XYZ in another language. (Here XYZ stands for a specific section name mentioned below, such as "Acknowledgements", "Dedications", "Endorsements", or "History".) To "Preserve the Title" of such a section when you modify the Document means that it remains a section "Entitled XYZ" according to this definition.

The Document may include Warranty Disclaimers next to the notice which states that this License applies to the Document. These Warranty Disclaimers are considered to be included by reference in this License, but only as regards disclaiming warranties: any other implication that these Warranty Disclaimers may have is void and has no effect on the meaning of this License.

2. VERBATIM COPYING

You may copy and distribute the Document in any medium, either commercially or noncommercially, provided that this License, the copyright notices, and the license notice saying this License applies to the Document are reproduced in all copies, and that you add no other conditions whatsoever to those of this License. You may not use technical measures to obstruct or control the reading or further copying of the copies you make or distribute. However, you may accept compensation in exchange for copies. If you distribute a large enough number of copies you must also follow the conditions in section 3.

You may also lend copies, under the same conditions stated above, and you may publicly display copies.

3. COPYING IN QUANTITY

If you publish printed copies (or copies in media that commonly have printed covers) of the Document, numbering more than 100, and the Document's license notice requires Cover Texts, you must enclose the copies in covers that carry, clearly and legibly, all these Cover Texts: Front-Cover Texts on the front cover, and Back-Cover Texts on the back cover. Both covers must also clearly and legibly identify you as the publisher of these copies. The front cover must present the full title with all words of the title equally prominent and visible. You may add other material on the covers in addition. Copying with changes limited to the covers, as long as they preserve the title of the Document and satisfy these conditions, can be treated as verbatim copying in other respects.

If the required texts for either cover are too voluminous to fit legibly, you should put the first ones listed (as many as fit reasonably) on the actual cover, and continue the rest onto adjacent pages.

If you publish or distribute Opaque copies of the Document numbering more than 100, you must either include a machine-readable Transparent copy along with each Opaque copy, or state in or with each Opaque copy a computer-network location from which the general network-using public has access to download using public-standard network protocols a complete Transparent copy of the Document, free of added material. If you use the latter option, you must take reasonably prudent steps, when you begin distribution of Opaque copies in quantity, to ensure that this Transparent copy will remain thus accessible at the stated location until at least one year after the last time you distribute an Opaque copy (directly or through your agents or retailers) of that edition to the public.

It is requested, but not required, that you contact the authors of the Document well before redistributing any large number of copies, to give them a chance to provide you with an updated version of the Document.

4. MODIFICATIONS

You may copy and distribute a Modified Version of the Document under the conditions of sections 2 and 3 above, provided that you release the Modified Version under precisely this License, with the Modified Version filling the role of the Document, thus licensing distribution and modification of the Modified Version to whoever possesses a copy of it. In addition, you must do these things in the Modified Version:

A. Use in the Title Page (and on the covers, if any) a title distinct from that of the Document, and from those of previous versions (which should, if there were any, be listed in the History section of the Document). You may use the same title as a previous version if the original publisher of that version gives permission.

B. List on the Title Page, as authors, one or more persons or entities responsible for authorship of the modifications in the Modified Version, together with at least five of the principal authors of the Document (all of its principal authors, if it has fewer than five), unless they release you from this requirement.

C. State on the Title page the name of the publisher of the Modified Version, as the publisher.

D. Preserve all the copyright notices of the Document.

F. Include, immediately after the copyright notices, a license notice giving the public permission to use the Modified Version under the terms of this License, in the form shown in the Addendum below.

G. Preserve in that license notice the full lists of Invariant Sections and required Cover Texts given in the Document's license notice.

H. Include an unaltered copy of this License.

I. Preserve the section Entitled "History", Preserve its Title, and add to it an item stating at least the title, year, new authors, and publisher of the Modified Version as given on the Title Page. If there is no section Entitled "History" in the Document, create one stating the title, year, authors, and publisher of the Document as given on its Title Page, then add an item describing the Modified Version as stated in the previous sentence.

J. Preserve the network location, if any, given in the Document for public access to a Transparent copy of the Document, and likewise the network locations given in the Document for previous versions it was based on. These may be placed in the "History" section. You may omit a network location for a work that was published at least four years before the Document itself, or if the original publisher of the version it refers to gives permission.

K. For any section Entitled "Acknowledgements" or "Dedications", Preserve the Title of the section, and preserve in the section all the substance and tone of each of the contributor acknowledgements and/or dedications given therein.

L. Preserve all the Invariant Sections of the Document, unaltered in their text and in their titles. Section numbers or the equivalent are not considered part of the section titles.

M. Delete any section Entitled "Endorsements". Such a section may not be included in the Modified Version.

N. Do not retitle any existing section to be Entitled "Endorsements" or to conflict in title with any Invariant Section.

O. Preserve any Warranty Disclaimers.

If the Modified Version includes new front-matter sections or appendices that qualify as Secondary Sections and contain no material copied from the Document, you may at your option designate some or all of these sections as invariant. To do this, add their titles to the list of Invariant Sections in the Modified Version's license notice. These titles must be distinct from any other section titles.

You may add a section Entitled "Endorsements", provided it contains nothing but endorsements of your Modified Version by various parties--for example, statements of peer review or that the text has been approved by an organization as the authoritative definition of a standard.

You may add a passage of up to five words as a Front-Cover Text, and a passage of up to 25 words as a Back-Cover Text, to the end of the list of Cover Texts in the Modified Version. Only one passage of Front-Cover Text and one of Back-Cover Text may be added by (or through arrangements made by) any one entity. If the Document already includes a cover text for the same cover, previously added by you or by arrangement made by the same entity you are acting on behalf of, you may not add another; but you may replace the old one, on explicit permission from the previous publisher that added the old one.

The author(s) and publisher(s) of the Document do not by this License give permission to use their names for publicity for or to assert or imply endorsement of any Modified Version.

5. COMBINING DOCUMENTS

You may combine the Document with other documents released under this License, under the terms defined in section 4 above for modified versions, provided that you include in the combination all of the Invariant Sections of all of the original documents, unmodified, and list them all as Invariant Sections of your combined work in its license notice, and that you preserve all their Warranty Disclaimers.

The combined work need only contain one copy of this License, and multiple identical Invariant Sections may be replaced with a single copy. If there are multiple Invariant Sections with the same name but different contents, make the title of each such section unique by adding at the end of it, in parentheses, the name of the original author or publisher of that section if known, or else a unique number. Make the same adjustment to the section titles in the list of Invariant Sections in the license notice of the combined work.

In the combination, you must combine any sections Entitled "History" in the various original documents, forming one section Entitled "History"; likewise combine any sections Entitled "Acknowledgements", and any sections Entitled "Dedications". You must delete all sections Entitled "Endorsements".

6. COLLECTIONS OF DOCUMENTS

You may make a collection consisting of the Document and other documents released under this License, and replace the individual copies of this License in the various documents with a single copy that is included in the collection, provided that you follow the rules of this License for verbatim copying of each of the documents in all other respects.

You may extract a single document from such a collection, and distribute it individually under this License, provided you insert a copy of this License into the extracted document, and follow this License in all other respects regarding verbatim copying of that document.

7. AGGREGATION WITH INDEPENDENT WORKS

A compilation of the Document or its derivatives with other separate and independent documents or works, in or on a volume of a storage or distribution medium, is called an "aggregate" if the copyright resulting from the compilation is not used to limit the legal rights of the compilation's users beyond what the individual works permit. When the Document is included in an aggregate, this License does not apply to the other works in the aggregate which are not themselves derivative works of the Document.

If the Cover Text requirement of section 3 is applicable to these copies of the Document, then if the Document is less than one half of the entire aggregate, the Document's Cover Texts may be placed on covers that bracket the Document within the aggregate, or the electronic equivalent of covers if the Document is in electronic form. Otherwise they must appear on printed covers that bracket the whole aggregate.

8. TRANSLATION

Translation is considered a kind of modification, so you may distribute translations of the Document under the terms of section 4. Replacing Invariant Sections with translations requires special permission from their copyright holders, but you may include translations of some or all Invariant Sections in addition to the original versions of these Invariant Sections. You may include a translation of this License, and all the license notices in the Document, and any Warranty Disclaimers, provided that you also include the original English version of this License and the original versions of those notices and disclaimers. In case of a disagreement between the translation and the original version of this License or a notice or disclaimer, the original version will prevail.

If a section in the Document is Entitled "Acknowledgements", "Dedications", or "History", the requirement (section 4) to Preserve its Title (section 1) will typically require changing the actual title.

9. TERMINATION

You may not copy, modify, sublicense, or distribute the Document except as expressly provided for under this License. Any other attempt to copy, modify, sublicense or distribute the Document is void, and will automatically terminate your rights under this License. However, parties who have received copies, or rights, from you under this License will not have their licenses terminated so long as such parties remain in full compliance.

10. FUTURE REVISIONS OF THIS LICENSE

The Free Software Foundation may publish new, revised versions of the GNU Free Documentation License from time to time. Such new versions will be similar in spirit to the present version, but may differ in detail to address new problems or concerns. See http://www.gnu.org/copyleft/.

Each version of the License is given a distinguishing version number. If the Document specifies that a particular numbered version of this License "or any later version" applies to it, you have the option of following the terms and conditions either of that specified version or of any later version that has been published (not as a draft) by the Free Software Foundation. If the Document does not specify a version number of this License, you may choose any version ever published (not as a draft) by the Free Software Foundation.

Goto Chapter: Top 1 2 3 4 5 6 7 Bib Ind

generated by GAPDoc2HTML