A code basically is nothing more than a set of codewords. We call
these the elements of the code. A codeword is a sequence of elements of
a finite field GF(q) where q is a prime power. Depending on the
type of code, a codeword can be interpreted as a vector or as a
polynomial. This is explained in more detail in Chapter Codewords.
In GUAVA, codes can be defined by their elements (this will be called an unrestricted code), by a generator matrix (a linear code) or by a generator polynomial (a cyclic code).
Any code can be defined by its elements. If you like, you can give the code a name.
gap> C := ElementsCode(["1100", "1010", "0001"], "example code", > GF(2) ); a (4,3,1..4)2..4 example code over GF(2)
An (n,M,d) code is a code with word length n, size M and minimum distance d. If the minimum distance has not yet been calculated, the lower bound and upper bound are printed. So
a (4,3,1..4)2..4 code over GF(2)
means a binary unrestricted code of length 4, with 3 elements and the minimum distance is greater than or equal to 1 and less than or equal to 4 and the covering radius is greater than or equal to 2 and less than or equal to 4.
gap> MinimumDistance(C); 2 gap> C; a (4,3,2)2..4 example code over GF(2)
If the set of elements is a linear subspace of GF(q)n, the code is called linear. If a code is linear, it can be defined by its generator matrix or parity check matrix. The generator matrix is a basis for the elements of a code, the parity check matrix is a basis for the nullspace of the code.
gap> G := GeneratorMatCode([[1,0,1],[0,1,2]], "demo code", GF(3) ); a linear [3,2,1..2]1 demo code over GF(3)
So a linear [n, k, d]r code is a code with word length n, dimension k, minimum distance d and covering radius r.
If the code is linear and all cyclic shifts of its elements are again codewords, the code is called cyclic. A cyclic code is defined by its generator polynomial or check polynomial. All elements are multiples of the generator polynomial modulo a polynomial xn -1 where n is the word length of the code. Multiplying a code element with the check polynomial yields zero (modulo the polynomial xn -1).
gap> G := GeneratorPolCode(Indeterminate(GF(2))+Z(2)^0, 7, GF(2) ); a cyclic [7,6,1..2]1 code defined by generator polynomial over GF(2)
It is possible that GUAVA does not know that an unrestricted code is
linear. This situation occurs for example when a code is generated from a
list of elements with the function ElementsCode (see ElementsCode).
By calling the function IsLinearCode (see IsLinearCode), GUAVA
tests if the code can be represented by a generator matrix. If so, the
code record and the operations are converted accordingly.
gap> L := Z(2)*[ [0,0,0], [1,0,0], [0,1,1], [1,1,1] ];;
gap> C := ElementsCode( L, GF(2) );
a (3,4,1..3)1 user defined unrestricted code over GF(2)
# so far, {\GUAVA} does not know what kind of code this is
gap> IsLinearCode( C );
true # it is linear
gap> C;
a linear [3,2,1]1 user defined unrestricted code over GF(2)
Of course the same holds for unrestricted codes that in fact are cyclic, or codes, defined by a generator matrix, that in fact are cyclic.
Codes are printed simply by giving a small description of their
parameters, the word length, size or dimension and minimum distance,
followed by a short description and the base field of the code. The
function Display gives a more detailed description, showing the
construction history of the code.
GUAVA doesn't place much emphasis on the actual encoding and decoding
processes; some algorithms have been included though. Encoding works
simply by multiplying an information vector with a code, decoding is done
by the function Decode. For more information about encoding and
decoding, see sections Operations for Codes and Decode.
gap> R := ReedMullerCode( 1, 3 ); a linear [8,4,4]2 Reed-Muller (1,3) code over GF(2) gap> w := [ 1, 0, 1, 1 ] * R; [ 1 0 0 1 1 0 0 1 ] gap> Decode( R, w ); [ 1 0 1 1 ] gap> Decode( R, w + "10000000" ); # One error at the first position [ 1 0 1 1 ] # Corrected by Guava
Sections Comparisons of Codes and Operations for Codes describe the operations that are available for codes.
Section Boolean Functions for Codes describe the functions that tests whether an object is a code and what kind of code it is (see IsCode, IsLinearCode and IsCyclicCode) and various other boolean functions for codes.
Section Equivalence and Isomorphism of Codes describe functions about equivalence and isomorphism of codes (see IsEquivalent, CodeIsomorphism and AutomorphismGroup).
Section Domain Functions for Codes describes functions that work on domains (see Chapter Domains and their Elements in the GAP Reference Manual).
Section Printing and Displaying Codes describes functions for printing and displaying codes.
Section Generating (Check) Matrices and Polynomials describes functions that return the matrices and polynomials that define a code (see GeneratorMat, CheckMat, GeneratorPol, CheckPol, RootsOfCode).
Section Parameters of Codes describes functions that return the basic parameters of codes (see WordLength, Redundancy and MinimumDistance).
Section Distributions describes functions that return distance and weight distributions (see WeightDistribution, InnerDistribution, OuterDistribution and DistancesDistribution).
Section Decoding Functions describes functions that are related to decoding (see Decode, Syndrome, SyndromeTable and StandardArray).
In Chapters Generating Codes and Manipulating Codes we follow on, describing functions that generate and manipulate codes.
= C2 <> C2
The equality operator = evaluates to true if the codes C1 and
C2 are equal, and to false otherwise. The inequality operator
<> evaluates to true if the codes C1 and C2 are not equal,
and to false otherwise.
Note that codes are equal if and only if their elements are equal. Codes can also be compared with objects of other types. Of course they are never equal.
gap> M := [ [0, 0], [1, 0], [0, 1], [1, 1] ];; gap> C1 := ElementsCode( M, GF(2) ); a (2,4,1..2)0 user defined unrestricted code over GF(2) gap> M = C1; false gap> C2 := GeneratorMatCode( [ [1, 0], [0, 1] ], GF(2) ); a linear [2,2,1]0 code defined by generator matrix over GF(2) gap> C1 = C2; true gap> ReedMullerCode( 1, 3 ) = HadamardCode( 8 ); true gap> WholeSpaceCode( 5, GF(4) ) = WholeSpaceCode( 5, GF(2) ); false
Another way of comparing codes is IsEquivalent, which checks if two
codes are equivalent (see IsEquivalent).
+ C2
The operator + evaluates to the direct sum of the codes C1 and
C2. See DirectSumCode.
+ c + C
The operator + evaluates to the coset code of code C after adding c
to all elements of C. See CosetCode.
* C2
The operator * evaluates to the direct product of the codes C1
and C2. See DirectProductCode.
* C
The operator * evaluates to the element of C belonging to information
word x. x may be a vector, polynomial, string or codeword or a list
of those. This is the way to do encoding in GUAVA. C must be linear,
because in GUAVA, encoding by multiplication is only defined for
linear codes. If C is a cyclic code, this multiplication is the same as
multiplying an information polynomial x by the generator polynomial of
C (except for the result not being a codeword type). If C is a linear
code, it is equal to the multiplication of an information vector x by
the generator matrix of C (again, the result then is not a codeword
type).
To decode, use the function Decode (see Decode).
in C
The in operator evaluates to true if C contains the codeword or
list of codewords specified by c. Of course, c and C must have the
same word lengths and base fields.
gap> C:= HammingCode( 2 );; eC:= AsSSortedList( C ); [ [ 0 0 0 ], [ 1 1 1 ] ] gap> eC[2] in C; true gap> [ 0 ] in C; false
IsSubset(C1,C2)
returns true if C2 is a subcode of C1,
i.e. if C1 contains at least all the elements of C2.
gap> IsSubset( HammingCode(3), RepetitionCode( 7 ) ); true gap> IsSubset( RepetitionCode( 7 ), HammingCode( 3 ) ); false gap> IsSubset( WholeSpaceCode( 7 ), HammingCode( 3 ) ); true
IsCode( obj )
IsCode returns true if obj, which can be an object of arbitrary
type, is a code and false otherwise. Will cause an error if obj is an
unbound variable.
gap> IsCode( 1 ); false gap> IsCode( ReedMullerCode( 2,3 ) ); true
IsLinearCode( obj )
IsLinearCode checks if object obj (not necessarily a code) is a
linear code. If a code has already been marked as linear or cyclic, the
function automatically returns true. Otherwise, the function checks if
a basis G of the elements of obj exists that generates the elements
of obj. If so, G is a generator matrix of obj and the function
returns true. If not, the function returns false.
gap> C := ElementsCode( [ [0,0,0],[1,1,1] ], GF(2) ); a (3,2,1..3)1 user defined unrestricted code over GF(2) gap> IsLinearCode( C ); true gap> IsLinearCode( ElementsCode( [ [1,1,1] ], GF(2) ) ); false gap> IsLinearCode( 1 ); false
IsCyclicCode( obj )
IsCyclicCode checks if the object obj is a cyclic code. If a code has
already been marked as cyclic, the function automatically returns true.
Otherwise, the function checks if a polynomial g exists that generates
the elements of obj. If so, g is a generator polynomial of obj and
the function returns true. If not, the function returns false.
gap> C := ElementsCode( [ [0,0,0], [1,1,1] ], GF(2) ); a (3,2,1..3)1 user defined unrestricted code over GF(2) gap> # GUAVA does not know the code is cyclic gap> IsCyclicCode( C ); # this command tells GUAVA to find out true gap> IsCyclicCode( HammingCode( 4, GF(2) ) ); false gap> IsCyclicCode( 1 ); false
IsPerfectCode( C )
IsPerfectCode returns true if C is a perfect code. For a code with
odd minimum distance d = 2t+1, this is the case when every word of the
vector space of C is at distance at most t from exactly one element
of C. Codes with even minimum distance are never perfect.
In fact, a code that is not trivial perfect (the binary repetition codes of odd length, the codes consisting of one word, and the codes consisting of the whole vector space), and does not have the parameters of a Hamming- or Golay-code, cannot be perfect.
gap> H := HammingCode(2); a linear [3,1,3]1 Hamming (2,2) code over GF(2) gap> IsPerfectCode( H ); true gap> IsPerfectCode( ElementsCode( [ [1,1,0], [0,0,1] ], GF(2) ) ); true gap> IsPerfectCode( ReedSolomonCode( 6, 3 ) ); false gap> IsPerfectCode(BinaryGolayCode()); true
IsMDSCode( C )
IsMDSCode returns true if C is a Maximum Distance Seperable code,
or MDS code for short. A linear [n, k, d]-code of length n, dimension
k and minimum distance d is an MDS code if k=n-d+1, in other words
if C meets the Singleton bound (see UpperBoundSingleton). An
unrestricted (n, M, d) code is called MDS if k=n-d+1, with k equal
to the largest integer less than or equal to the logarithm of M with base
q, the size of the base field of C.
Well known MDS codes include the repetition codes, the whole space codes, the even weight codes (these are the only binary MDS Codes) and the Reed-Solomon codes.
gap> C1 := ReedSolomonCode( 6, 3 ); a cyclic [6,4,3]2 Reed-Solomon code over GF(7) gap> IsMDSCode( C1 ); true # 6-3+1 = 4 gap> IsMDSCode( QRCode( 23, GF(2) ) ); false
IsSelfDualCode( C )
IsSelfDualCode returns true if C is self-dual, i.e. when C is
equal to its dual code (see also DualCode). If a code is self-dual, it
automatically is self-orthogonal (see IsSelfOrthogonalCode).
If C is a non-linear code, it cannot be self-dual, so false is
returned. A linear code can only be self-dual when its dimension k is
equal to the redundancy r.
gap> IsSelfDualCode( ExtendedBinaryGolayCode() ); true gap> C := ReedMullerCode( 1, 3 ); a linear [8,4,4]2 Reed-Muller (1,3) code over GF(2) gap> DualCode( C ) = C; true
IsSelfOrthogonalCode( C )
IsSelfOrthogonalCode returns true if C is self-orthogonal. A
code is self-orthogonal if every element of C is orthogonal to all
elements of C, including itself. In the linear case, this simply means
that the generator matrix of C multiplied with its transpose yields a
null matrix.
In addition, a code is self-dual if it contains all vectors that its elements are orthogonal to (see IsSelfDualCode).
gap> R := ReedMullerCode(1,4); a linear [16,5,8]6 Reed-Muller (1,4) code over GF(2) gap> IsSelfOrthogonalCode(R); true gap> IsSelfDualCode(R); false
IsEquivalent( C1, C2 )
IsEquivalent returns true if C1 and C2 are equivalent
codes. This is the case if C1 can be obtained from C2 by
carrying out column permutations. GUAVA only handles binary codes. The
external program desauto from J.S. Leon is used to compute the
isomorphism between the codes. If C1 and C2 are equal, they
are also equivalent.
Note that the algorithm is very slow for non-linear codes.
gap> x:= Indeterminate( GF(2) );; pol:= x^3+x+1; Z(2)^0+x_1+x_1^3 gap> H := GeneratorPolCode( pol, 7, GF(2)); a cyclic [7,4,1..3]1 code defined by generator polynomial over GF(2) gap> H = HammingCode(3, GF(2)); false gap> IsEquivalent(H, HammingCode(3, GF(2))); true # H is equivalent to a Hamming code gap> CodeIsomorphism(H, HammingCode(3, GF(2))); (3,4)(5,6,7)
CodeIsomorphism( C1, C2 )
If the two codes C1 and C2 are equivalent codes (see
IsEquivalent), CodeIsomorphism returns the permutation that
transforms C1 into C2. If the codes are not equivalent, it
returns false.
gap> x:= Indeterminate( GF(2) );; pol:= x^3+x+1; Z(2)^0+x_1+x_1^3 gap> H := GeneratorPolCode( pol, 7, GF(2)); a cyclic [7,4,1..3]1 code defined by generator polynomial over GF(2) gap> CodeIsomorphism(H, HammingCode(3, GF(2))); (3,4)(5,6,7) gap> PermutedCode(H, (3,4)(5,6,7)) = HammingCode(3, GF(2)); true
AutomorphismGroup( C )
AutomorphismGroup returns the automorphism group of a binary code
C. This is the largest permutation group of degree n such that each
permutation applied to the columns of C again yields C. GUAVA uses
the external program desauto from J.S. Leon to compute the
automorphism group. The function PermutedCode permutes the columns of a
code (see PermutedCode).
gap> R := RepetitionCode(7,GF(2));
a cyclic [7,1,7]3 repetition code over GF(2)
gap> AutomorphismGroup(R);
Sym( [ 1 .. 7 ] )
# every permutation keeps R identical
gap> C := CordaroWagnerCode(7);
a linear [7,2,4]3 Cordaro-Wagner code over GF(2)
gap> AsSSortedList(C);
[ [ 0 0 0 0 0 0 0 ], [ 0 0 1 1 1 1 1 ], [ 1 1 0 0 0 1 1 ], [ 1 1 1 1 1 0 0 ] ]
gap> AutomorphismGroup(C);
Group([ (3,4), (4,5), (1,6)(2,7), (1,2), (6,7) ])
gap> C2 := PermutedCode(C, (1,6)(2,7));
a linear [7,2,4]3 permuted code
gap> AsSSortedList(C2);
[ [ 0 0 0 0 0 0 0 ], [ 0 0 1 1 1 1 1 ], [ 1 1 0 0 0 1 1 ], [ 1 1 1 1 1 0 0 ] ]
gap> C2 = C;
true
3.5 Domain Functions for Codes
These are some GAP functions that work on Domains in general. Their
specific effect on Codes is explained here.
IsFinite( C )
IsFinite is an implementation of the GAP domain function
IsFinite. It returns true for a code C.
gap> IsFinite( RepetitionCode( 1000, GF(11) ) ); true
Size( C )
Size returns the size of C, the number of elements of the code. If
the code is linear, the size of the code is equal to qk, where q is
the size of the base field of C and k is the dimension.
gap> Size( RepetitionCode( 1000, GF(11) ) ); 11 gap> Size( NordstromRobinsonCode() ); 256
LeftActingDomain( C )
LeftActingDomain returns the base field of a code C. Each element of C
consists of elements of this base field. If the base field is F, and
the word length of the code is n, then the codewords are elements of
Fn. If C is a cyclic code, its elements are interpreted as
polynomials with coefficients over F.
gap> C1 := ElementsCode([[0,0,0], [1,0,1], [0,1,0]], GF(4)); a (3,3,1..3)2..3 user defined unrestricted code over GF(4) gap> LeftActingDomain( C1 ); GF(2^2) gap> LeftActingDomain( HammingCode( 3, GF(9) ) ); GF(3^2)
Dimension( C )
Dimension returns the parameter k of C, the dimension of the code,
or the number of information symbols in each codeword. The dimension is
not defined for non-linear codes; Dimension then returns an error.
gap> Dimension( NullCode( 5, GF(5) ) ); 0 gap> C := BCHCode( 15, 4, GF(4) ); a cyclic [15,9,5]3..4 BCH code, delta=5, b=1 over GF(4) gap> Dimension( C ); 9 gap> Size( C ) = Size( LeftActingDomain( C ) ) ^ Dimension( C ); true
AsSSortedList( C )
AsSSortedList returns a list of the elements of C. These elements are of
the codeword type (see Codewords). Note that for large codes,
generating the elements may be very time- and memory-consuming. For
generating a specific element or a subset of the elements, use
CodewordNr (see CodewordNr).
gap> C := ConferenceCode( 5 ); a (5,12,2)1..4 conference code over GF(2) gap> AsSSortedList( C ); [ [ 0 0 0 0 0 ], [ 0 0 1 1 1 ], [ 0 1 0 1 1 ], [ 0 1 1 0 1 ], [ 0 1 1 1 0 ], [ 1 0 0 1 1 ], [ 1 0 1 0 1 ], [ 1 0 1 1 0 ], [ 1 1 0 0 1 ], [ 1 1 0 1 0 ], [ 1 1 1 0 0 ], [ 1 1 1 1 1 ] ] gap> CodewordNr( C, [ 1, 2 ] ); [ [ 0 0 0 0 0 ], [ 0 0 1 1 1 ] ]
CodewordNr( C, list )
CodewordNr returns a list of codewords of C. list may be a list of
integers or a single integer. For each integer of list, the
corresponding codeword of C is returned. The correspondence of a number
i with a codeword is determined as follows: if a list of elements of
C is available, the ith element is taken. Otherwise, it is
calculated by multiplication of the ith information vector by the
generator matrix or generator polynomial, where the information vectors
are ordered lexicographically.
So CodewordNr(C, i) is equal to AsSSortedList(C)[i]. The latter
function first calculates the set of all the elements of C and then
returns the ith element of that set, whereas the former only
calculates the ith codeword.
gap> R := ReedSolomonCode(2,2); a cyclic [2,1,2]1 Reed-Solomon code over GF(3) gap> AsSSortedList(R); [ [ 0 0 ], [ 1 1 ], [ 2 2 ] ] gap> CodewordNr(R, [1,3]); [ [ 0 0 ], [ 2 2 ] ] gap> C := HadamardCode( 16 ); a (16,32,8)5..6 Hadamard code of order 16 over GF(2) gap> AsSSortedList(C)[17] = CodewordNr( C, 17 ); true
Print( C )
Print prints information about C. This is the same as typing the
identifier C at the GAP-prompt.
If the argument is an unrestricted code, information in the form
a (<n>,<M>,<d>)<r> ... code over GF(q)
is printed, where n is the word length, M the number of elements of the code, d the minimum distance and r the covering radius.
If the argument is a linear code, information in the form
a linear [<n>,<k>,<d>]<r> ... code over GF(q)
is printed, where n is the word length, k the dimension of the code, d the minimum distance and r the covering radius.
In all cases, if d is not yet known, it is displayed in the form
<lowerbound>,..,<upperbound>
and if r is not yet known, it is displayed in the same way.
The function Display gives more information. See Display.
gap> C1 := ExtendedCode( HammingCode( 3, GF(2) ) ); a linear [8,4,4]2 extended code gap> Print( "This is ", NordstromRobinsonCode(), ". \n"); This is a (16,256,6)4 Nordstrom-Robinson code over GF(2).
String( C )
String returns information about C in a string. This function is used
by Print (see Print).
Display( C )
Display prints the method of construction of code C. With this
history, in most cases an equal or equivalent code can be
reconstructed. If C is an unmanipulated code, the result is equal to
output of the function Print (see Print).
gap> Display( RepetitionCode( 6, GF(3) ) ); a cyclic [6,1,6]4 repetition code over GF(3) gap> C1 := ExtendedCode( HammingCode(2) );; gap> C2 := PuncturedCode( ReedMullerCode( 2, 3 ) );; gap> Display( LengthenedCode( UUVCode( C1, C2 ) ) ); a linear [12,8,2]2..4 code, lengthened with 1 column(s) of a linear [11,8,1]1..2 U U+V construction code of U: a linear [4,1,4]2 extended code of a linear [3,1,3]1 Hamming (2,2) code over GF(2) V: a linear [7,7,1]0 punctured code of a cyclic [8,7,2]1 Reed-Muller (2,3) code over GF(2)
GeneratorMat( C )
GeneratorMat returns a generator matrix of C. The code consists of
all linear combinations of the rows of this matrix.
If until now no generator matrix of C was determined, it is computed from either the parity check matrix, the generator polynomial, the check polynomial or the elements (if possible), whichever is available.
If C is a non-linear code, the function returns an error.
gap> GeneratorMat( HammingCode( 3, GF(2) ) );
[ <an immutable GF2 vector of length 7>, <an immutable GF2 vector of length 7>
, <an immutable GF2 vector of length 7>,
<an immutable GF2 vector of length 7> ]
gap> GeneratorMat( RepetitionCode( 5, GF(25) ) );
[ [ Z(5)^0, Z(5)^0, Z(5)^0, Z(5)^0, Z(5)^0 ] ]
gap> GeneratorMat( NullCode( 14, GF(4) ) );
[ ]
CheckMat( C )
CheckMat returns a parity check matrix of C. The code consists of all
words orthogonal to each of the rows of this matrix. The transpose of the
matrix is a right inverse of the generator matrix. The parity check
matrix is computed from either the generator matrix, the generator
polynomial, the check polynomial or the elements of C (if possible),
whichever is available.
If C is a non-linear code, the function returns an error.
gap> CheckMat( HammingCode(3, GF(2) ) );
[ <an immutable GF2 vector of length 7>, <an immutable GF2 vector of length 7>
, <an immutable GF2 vector of length 7> ]
gap> CheckMat( RepetitionCode( 5, GF(25) ) );
[ [ Z(5)^0, Z(5)^2, 0*Z(5), 0*Z(5), 0*Z(5) ],
[ 0*Z(5), Z(5)^0, Z(5)^2, 0*Z(5), 0*Z(5) ],
[ 0*Z(5), 0*Z(5), Z(5)^0, Z(5)^2, 0*Z(5) ],
[ 0*Z(5), 0*Z(5), 0*Z(5), Z(5)^0, Z(5)^2 ] ]
gap> CheckMat( WholeSpaceCode( 12, GF(4) ) );
[ ]
GeneratorPol( C )
GeneratorPol returns the generator polynomial of C. The code consists
of all multiples of the generator polynomial modulo xn-1 where n
is the word length of C. The generator polynomial is determined from
either the check polynomial, the generator or check matrix or the
elements of C (if possible), whichever is available.
If C is not a cyclic code, the function returns false.
gap> GeneratorPol(GeneratorMatCode([[1, 1, 0], [0, 1, 1]], GF(2))); Z(2)^0+x_1 gap> GeneratorPol( WholeSpaceCode( 4, GF(2) ) ); Z(2)^0 gap> GeneratorPol( NullCode( 7, GF(3) ) ); -Z(3)^0+x_1^7
CheckPol( C )
CheckPol returns the check polynomial of C. The code consists of all
polynomials f with f*h = 0 (mod xn-1), where h is the check
polynomial, and n is the word length of C. The check polynomial is
computed from the generator polynomial, the generator or parity check
matrix or the elements of C (if possible), whichever is available.
If C if not a cyclic code, the function returns an error.
gap> CheckPol(GeneratorMatCode([[1, 1, 0], [0, 1, 1]], GF(2))); Z(2)^0+x_1+x_1^2 gap> CheckPol(WholeSpaceCode(4, GF(2))); Z(2)^0+x_1^4 gap> CheckPol(NullCode(7,GF(3))); Z(3)^0
RootsOfCode( C )
RootsOfCode returns a list of all zeros of the generator polynomial of
a cyclic code C. These are finite field elements in the splitting field
of the generator polynomial, GF(qm), m is the multiplicative order
of the size of the base field of the code, modulo the word length.
The reverse proces, constructing a code from a set of roots, can be
carried out by the function RootsCode (see RootsCode).
gap> C1 := ReedSolomonCode( 16, 5 ); a cyclic [16,12,5]3..4 Reed-Solomon code over GF(17) gap> RootsOfCode( C1 ); [ Z(17), Z(17)^2, Z(17)^3, Z(17)^4 ] gap> C2 := RootsCode( 16, last ); a cyclic [16,12,5]3..4 code defined by roots over GF(17) gap> C1 = C2; true
WordLength( C )
WordLength returns the parameter n of C, the word length of the
elements. Elements of cyclic codes are polynomials of maximum degree
n-1, as calculations are carried out modulo xn-1.
gap> WordLength( NordstromRobinsonCode() ); 16 gap> WordLength( PuncturedCode( WholeSpaceCode(7) ) ); 6 gap> WordLength( UUVCode( WholeSpaceCode(7), RepetitionCode(7) ) ); 14
Redundancy( C )
Redundancy returns the redundancy r of C, which is equal to the
number of check symbols in each element. If C is not a linear code the
redundancy is not defined and Redundancy returns an error.
If a linear code C has dimension k and word length n, it has redundancy r=n-k.
gap> C := TernaryGolayCode(); a cyclic [11,6,5]2 ternary Golay code over GF(3) gap> Redundancy(C); 5 gap> Redundancy( DualCode(C) ); 6
MinimumDistance( C )
MinimumDistance returns the minimum distance of C, the largest
integer d with the property that every element of C has at least a
Hamming distance d (see DistanceCodeword) to any other element of
C. For linear codes, the minimum distance is equal to the minimum
weight. This means that d is also the smallest positive value with
w[d+1] ¹ 0, where w is the weight distribution of C (see
WeightDistribution). For unrestricted codes, d is the smallest
positive value with w[d+1] ¹ 0, where w is the inner distribution
of C (see InnerDistribution).
For codes with only one element, the minimum distance is defined to be equal to the word length.
gap> C := MOLSCode(7);; MinimumDistance(C); 3 gap> WeightDistribution(C); [ 1, 0, 0, 24, 24 ] gap> MinimumDistance( WholeSpaceCode( 5, GF(3) ) ); 1 gap> MinimumDistance( NullCode( 4, GF(2) ) ); 4 gap> C := ConferenceCode(9);; MinimumDistance(C); 4 gap> InnerDistribution(C); [ 1, 0, 0, 0, 63/5, 9/5, 18/5, 0, 9/10, 1/10 ]
MinimumDistance( C, w )
In this form, MinimumDistance returns the minimum distance of a
codeword w to the code C, also called the distance to C. This is
the smallest value d for which there is an element c of the code C
which is at distance d from w. So d is also the minimum value for
which D[d+1] ¹ 0, where D is the distance distribution of w to
C (see DistancesDistribution).
Note that w must be an element of the same vector space as the elements of C. w does not necessarily belong to the code (if it does, the minimum distance is zero).
gap> C := MOLSCode(7);; w := CodewordNr( C, 17 ); [ 3 3 6 2 ] gap> MinimumDistance( C, w ); 0 gap> C := RemovedElementsCode( C, w );; MinimumDistance( C, w ); 3 # so w no longer belongs to C
WeightDistribution( C )
WeightDistribution returns the weight distribution of C, as a
vector. The ith element of this vector contains the number of
elements of C with weight i-1. For linear codes, the weight
distribution is equal to the inner distribution (see
InnerDistribution).
Suppose w is the weight distribution of C. If C is linear, it must have the zero codeword, so w[1] = 1 (one word of weight 0).
gap> WeightDistribution( ConferenceCode(9) ); [ 1, 0, 0, 0, 0, 18, 0, 0, 0, 1 ] gap> WeightDistribution( RepetitionCode( 7, GF(4) ) ); [ 1, 0, 0, 0, 0, 0, 0, 3 ] gap> WeightDistribution( WholeSpaceCode( 5, GF(2) ) ); [ 1, 5, 10, 10, 5, 1 ]
InnerDistribution( C )
InnerDistribution returns the inner distribution of C. The ith
element of the vector contains the average number of elements of C at
distance i-1 to an element of C. For linear codes, the inner
distribution is equal to the weight distribution (see
WeightDistribution).
Suppose w is the inner distribution of C. Then w[1] = 1, because each element of C has exactly one element at distance zero (the element itself). The minimum distance of C is the smallest value d > 0 with w[d+1] ¹ 0, because a distance between zero and d never occurs. See MinimumDistance.
gap> InnerDistribution( ConferenceCode(9) ); [ 1, 0, 0, 0, 63/5, 9/5, 18/5, 0, 9/10, 1/10 ] gap> InnerDistribution( RepetitionCode( 7, GF(4) ) ); [ 1, 0, 0, 0, 0, 0, 0, 3 ]
OuterDistribution( C )
The function OuterDistribution returns a list of length qn, where
q is the size of the base field of C and n is the word length. The
elements of the list consist of an element of (GF(q))n (this is a
codeword type) and the distribution of distances to the code (a list of
integers). This table is very large, and for n > 20 it will not fit
in the memory of most computers. The function DistancesDistribution
(see DistancesDistribution) can be used to calculate one entry of the
list.
gap> C := RepetitionCode( 3, GF(2) );
a cyclic [3,1,3]1 repetition code over GF(2)
gap> OD := OuterDistribution(C);
[ [ [ 0 0 0 ], [ 1, 0, 0, 1 ] ], [ [ 1 1 1 ], [ 1, 0, 0, 1 ] ],
[ [ 0 0 1 ], [ 0, 1, 1, 0 ] ], [ [ 1 1 0 ], [ 0, 1, 1, 0 ] ],
[ [ 1 0 0 ], [ 0, 1, 1, 0 ] ], [ [ 0 1 1 ], [ 0, 1, 1, 0 ] ],
[ [ 0 1 0 ], [ 0, 1, 1, 0 ] ], [ [ 1 0 1 ], [ 0, 1, 1, 0 ] ] ]
gap> WeightDistribution(C) = OD[1][2];
true
gap> DistancesDistribution( C, Codeword("110") ) = OD[4][2];
true
DistancesDistribution( C, w )
DistancesDistribution returns a distribution of the distances of all
elements of C to a codeword w in the same vector space. The ith
element of the distance distribution is the number of codewords of C
that have distance i-1 to w. The smallest value d with w[d+1] ¹ 0 is defined as the distance to C (see MinimumDistance).
gap> H := HadamardCode(20);
a (20,40,10)6..8 Hadamard code of order 20 over GF(2)
gap> c := Codeword("10110101101010010101", H);
[ 1 0 1 1 0 1 0 1 1 0 1 0 1 0 0 1 0 1 0 1 ]
gap> DistancesDistribution(H, c);
[ 0, 0, 0, 0, 0, 1, 0, 7, 0, 12, 0, 12, 0, 7, 0, 1, 0, 0, 0, 0, 0 ]
gap> MinimumDistance(H, c);
5 # distance to H
Decode( C, c )
Decode decodes c with respect to code C. c is a codeword or a
list of codewords. First, possible errors in c are corrected, then the
codeword is decoded to an information codeword x. If the code record
has a field specialDecoder, this special algorithm is used to decode
the vector. Hamming codes and BCH codes have such a special algorithm.
Otherwise, syndrome decoding is used. Encoding is done by multiplying the
information vector with the code (see Operations for Codes).
A special decoder can be created by defining a function
C!.SpecialDecoder := function(C, c) ... end;
The function uses the arguments C, the code record itself, and c, a vector of the codeword type, to decode c to an information word. A normal decoder would take a codeword c of the same word length and field as C, and would return a information word of length k, the dimension of C. The user is not restricted to these normal demands though, and can for instance define a decoder for non-linear codes.
gap> C := HammingCode(3);
a linear [7,4,3]1 Hamming (3,2) code over GF(2)
gap> c := "1010"*C; # encoding
[ 1 0 1 1 0 1 0 ]
gap> Decode(C, c); # decoding
[ 1 0 1 0 ]
gap> Decode(C, Codeword("0010101"));
[ 1 1 0 1 ] # one error corrected
gap> C!.SpecialDecoder := function(C, c)
> return NullWord(Dimension(C));
> end;
function ( C, c ) ... end
gap> Decode(C, c);
[ 0 0 0 0 ] # new decoder always returns null word
Syndrome( C, c )
Syndrome returns the syndrome of word c with respect to a code
C. c is a word of the vector space of C. If c is an element of
C, the syndrome is a zero vector. The syndrome can be used for looking
up an error vector in the syndrome table (see SyndromeTable) that is
needed to correct an error in c.
A syndrome is not defined for non-linear codes. Syndrome then returns
an error.
gap> C := HammingCode(4);
a linear [15,11,3]1 Hamming (4,2) code over GF(2)
gap> v := CodewordNr( C, 7 );
[ 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 ]
gap> Syndrome( C, v );
[ 0 0 0 0 ]
gap> Syndrome( C, Codeword( "000000001100111" ) );
[ 1 1 1 1 ]
gap> Syndrome( C, Codeword( "000000000000001" ) );
[ 1 1 1 1 ] # the same syndrome: both codewords are in the same
# coset of C
SyndromeTable( C )
SyndromeTable returns a syndrome table of a linear code C,
consisting of two columns. The first column consists of the error vectors
that correspond to the syndrome vectors in the second column. These
vectors both are of the codeword type. After calculating the syndrome of
a word c with Syndrome (see Syndrome), the error vector needed to
correct c can be found in the syndrome table. Subtracting this vector
from c yields an element of C. To make the search for the syndrome as
fast as possible, the syndrome table is sorted according to the syndrome
vectors.
gap> H := HammingCode(2);
a linear [3,1,3]1 Hamming (2,2) code over GF(2)
gap> SyndromeTable(H);
[ [ [ 0 0 0 ], [ 0 0 ] ], [ [ 1 0 0 ], [ 0 1 ] ],
[ [ 0 1 0 ], [ 1 0 ] ], [ [ 0 0 1 ], [ 1 1 ] ] ]
gap> c := Codeword("101");
[ 1 0 1 ]
gap> c in H;
false # c is not an element of H
gap> Syndrome(H,c);
[ 1 0 ] # according to the syndrome table,
# the error vector [ 0 1 0 ] belongs to this syndrome
gap> c - Codeword("010") in H;
true # so the corrected codeword is
# [ 1 0 1 ] - [ 0 1 0 ] = [ 1 1 1 ],
# this is an element of H
StandardArray( C )
StandardArray returns the standard array of a code C. This is a
matrix with elements of the codeword type. It has qr rows and qk
columns, where q is the size of the base field of C, r is the
redundancy of C, and k is the dimension of C. The first row
contains all the elements of C. Each other row contains words that do
not belong to the code, with in the first column their syndrome vector
(see Syndrome).
A non-linear code does not have a standard array. StandardArray then
returns an error.
Note that calculating a standard array can be very time- and memory- consuming.
gap> StandardArray(RepetitionCode(3)); [ [ [ 0 0 0 ], [ 1 1 1 ] ], [ [ 0 0 1 ], [ 1 1 0 ] ], [ [ 0 1 0 ], [ 1 0 1 ] ], [ [ 1 0 0 ], [ 0 1 1 ] ] ]
[Up] [Previous] [Next] [Index]
GUAVA manual