Quelle chap4_mj.html

Sprache: HTML

products/Sources/formale Sprachen/GAP/pkg/guava/doc/chap4_mj.html

<?xml version="1.0" encoding="UTF-8"?>

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<script type="text/javascript"
 src="https://cdn.jsdelivr.net/npm/mathjax@2/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<title>GAP (guava) - Chapter 4: Codes</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap4" onload="jscontent()">

<div class="chlinktop">Goto Chapter: <a href="chap0_mj.html">Top</a> <a href="chap1_mj.html">1</a> <a href="chap2_mj.html">2</a> <a href="chap3_mj.html">3</a> <a href="chap4_mj.html">4</a> <a href="chap5_mj.html">5</a> <a href="chap6_mj.html">6</a> <a href="chap7_mj.html">7</a> <a href="chap8_mj.html">8</a> <a href="chap9_mj.html">9</a> <a href="chapBib_mj.html">Bib</a> <a href="chapInd_mj.html">Ind</a> </div>

<div class="chlinkprevnexttop"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap3_mj.html">[Previous Chapter]</a> <a href="chap5_mj.html">[Next Chapter]</a> </div>

<a href="chap4.html">[MathJax off]</a>
<a id="X85FDDF0B7B7D87FB" name="X85FDDF0B7B7D87FB"></a>
<div class="ChapSects"><a href="chap4_mj.html#X85FDDF0B7B7D87FB">4 Codes</a>
<div class="ContSect"> <a href="chap4_mj.html#X7ECE60E1873B49A6">4.1 Comparisons of Codes</a>

<div class="ContSSBlock">
 <a href="chap4_mj.html#X8686D5FA839F1A3D"><code>4.1-1 \=</code></a>
</div></div>
<div class="ContSect"> <a href="chap4_mj.html#X832DA51986A3882C">4.2 
Operations for Codes
</a>

<div class="ContSSBlock">
 <a href="chap4_mj.html#X82E2E5127CD25168"><code>4.2-1 \+</code></a>
 <a href="chap4_mj.html#X7EFA08EE7BA22261"><code>4.2-2 \*</code></a>
 <a href="chap4_mj.html#X84D8B18F7C494A58"><code>4.2-3 \*</code></a>
 <a href="chap4_mj.html#X8744BA5E78BCF3F9">4.2-4 InformationWord</a>
</div></div>
<div class="ContSect"> <a href="chap4_mj.html#X864091AA7D4AFE86">4.3 
Boolean Functions for Codes
</a>

<div class="ContSSBlock">
 <a href="chap4_mj.html#X87BDB89B7AAFE8AD">4.3-1 in</a>
 <a href="chap4_mj.html#X79CA175481F8105F">4.3-2 IsSubset</a>
 <a href="chap4_mj.html#X7F71186281DEA83A">4.3-3 IsCode</a>
 <a href="chap4_mj.html#X7B24748A7CE8D4B9">4.3-4 IsLinearCode</a>
 <a href="chap4_mj.html#X850C23D07C9A9B19">4.3-5 IsCyclicCode</a>
 <a href="chap4_mj.html#X85E3BD26856424F7">4.3-6 IsPerfectCode</a>
 <a href="chap4_mj.html#X789380D28018EC3F">4.3-7 IsMDSCode</a>
 <a href="chap4_mj.html#X80166D8D837FEB58">4.3-8 IsSelfDualCode</a>
 <a href="chap4_mj.html#X7B2A0CC481D2366F">4.3-9 IsSelfOrthogonalCode</a>
 <a href="chap4_mj.html#X8358D43981EBE970">4.3-10 IsDoublyEvenCode</a>
 <a href="chap4_mj.html#X79ACAEF5865414A0">4.3-11 IsSinglyEvenCode</a>
 <a href="chap4_mj.html#X7CE150ED7C3DC455">4.3-12 IsEvenCode</a>
 <a href="chap4_mj.html#X7B6DB8CC84FCAC1C">4.3-13 IsSelfComplementaryCode</a>
 <a href="chap4_mj.html#X7AFD3844859B20BF">4.3-14 IsAffineCode</a>
 <a href="chap4_mj.html#X861D32FB81EF0D77">4.3-15 IsAlmostAffineCode</a>
</div></div>
<div class="ContSect"> <a href="chap4_mj.html#X86442DCD7A0B2146">4.4 
Equivalence and Isomorphism of Codes
</a>

<div class="ContSSBlock">
 <a href="chap4_mj.html#X843034687D9C75B0">4.4-1 IsEquivalent</a>
 <a href="chap4_mj.html#X874DED8E86BC180B">4.4-2 CodeIsomorphism</a>
 <a href="chap4_mj.html#X87677B0787B4461A">4.4-3 AutomorphismGroup</a>
 <a href="chap4_mj.html#X79F3261F86C29F6D">4.4-4 PermutationAutomorphismGroup</a>
</div></div>
<div class="ContSect"> <a href="chap4_mj.html#X866EB39483DDAE72">4.5 
Domain Functions for Codes
</a>

<div class="ContSSBlock">
 <a href="chap4_mj.html#X808A4061809A6E67">4.5-1 IsFinite</a>
 <a href="chap4_mj.html#X858ADA3B7A684421">4.5-2 Size</a>
 <a href="chap4_mj.html#X86F070E0807DC34E">4.5-3 LeftActingDomain</a>
 <a href="chap4_mj.html#X7E6926C6850E7C4E">4.5-4 Dimension</a>
 <a href="chap4_mj.html#X856D927378C33548">4.5-5 AsSSortedList</a>
</div></div>
<div class="ContSect"> <a href="chap4_mj.html#X823827927D6A8235">4.6 
Printing and Displaying Codes
</a>

<div class="ContSSBlock">
 <a href="chap4_mj.html#X7AFA64D97A1F39A3">4.6-1 Print</a>
 <a href="chap4_mj.html#X81FB5BE27903EC32">4.6-2 String</a>
 <a href="chap4_mj.html#X83A5C59278E13248">4.6-3 Display</a>
 <a href="chap4_mj.html#X7CD08C8C780543C4">4.6-4 DisplayBoundsInfo</a>
</div></div>
<div class="ContSect"> <a href="chap4_mj.html#X7D0F48B685A3ECDD">4.7 
Generating (Check) Matrices and Polynomials
</a>

<div class="ContSSBlock">
 <a href="chap4_mj.html#X817224657C9829C4">4.7-1 GeneratorMat</a>
 <a href="chap4_mj.html#X85D4B26E7FB38D57">4.7-2 CheckMat</a>
 <a href="chap4_mj.html#X78E33C3A843B0261">4.7-3 GeneratorPol</a>
 <a href="chap4_mj.html#X7C45AA317BB1195F">4.7-4 CheckPol</a>
 <a href="chap4_mj.html#X7F4CB9DB7CD97178">4.7-5 RootsOfCode</a>
</div></div>
<div class="ContSect"> <a href="chap4_mj.html#X8170B52D7C154247">4.8 
Parameters of Codes
</a>

<div class="ContSSBlock">
 <a href="chap4_mj.html#X7A36C3C67B0062E8">4.8-1 WordLength</a>
 <a href="chap4_mj.html#X7E33FD56792DBF3D">4.8-2 Redundancy</a>
 <a href="chap4_mj.html#X7B31613D8538BD29">4.8-3 MinimumDistance</a>
 <a href="chap4_mj.html#X813F226F855590EE">4.8-4 MinimumDistanceLeon</a>
 <a href="chap4_mj.html#X84EDF67B86B4154C">4.8-5 MinimumWeight</a>
 <a href="chap4_mj.html#X823B9A797EE42F6D">4.8-6 DecreaseMinimumDistanceUpperBound</a>
 <a href="chap4_mj.html#X7A679B0A7816B030">4.8-7 MinimumDistanceRandom</a>
 <a href="chap4_mj.html#X7A195E317D2AB7CE">4.8-8 CoveringRadius</a>
 <a href="chap4_mj.html#X81004B007EC5DF58">4.8-9 SetCoveringRadius</a>
</div></div>
<div class="ContSect"> <a href="chap4_mj.html#X806384B4815EFF2E">4.9 
Distributions
</a>

<div class="ContSSBlock">
 <a href="chap4_mj.html#X7AEE64467FB1E0B9">4.9-1 MinimumWeightWords</a>
 <a href="chap4_mj.html#X8728BCC9842A6E5D">4.9-2 WeightDistribution</a>
 <a href="chap4_mj.html#X871FD301820717A4">4.9-3 InnerDistribution</a>
 <a href="chap4_mj.html#X87AD54F87C5EE77E">4.9-4 DistancesDistribution</a>
 <a href="chap4_mj.html#X8495870687195324">4.9-5 OuterDistribution</a>
</div></div>
<div class="ContSect"> <a href="chap4_mj.html#X7D9A39BF801948C8">4.10 
Decoding Functions
</a>

<div class="ContSSBlock">
 <a href="chap4_mj.html#X7A42FF7D87FC34AC">4.10-1 Decode</a>
 <a href="chap4_mj.html#X7D870C9387C47D9F">4.10-2 Decodeword</a>
 <a href="chap4_mj.html#X7D48DE2A84474C6A">4.10-3 GeneralizedReedSolomonDecoderGao</a>
 <a href="chap4_mj.html#X7CFF98D483502053">4.10-4 GeneralizedReedSolomonListDecoder</a>
 <a href="chap4_mj.html#X80E17FA27DCAB676">4.10-5 BitFlipDecoder</a>
 <a href="chap4_mj.html#X7B88DEB37F28404A">4.10-6 NearestNeighborGRSDecodewords</a>
 <a href="chap4_mj.html#X825E35757D778787">4.10-7 NearestNeighborDecodewords</a>
 <a href="chap4_mj.html#X7D02E0FE8735D3E6">4.10-8 Syndrome</a>
 <a href="chap4_mj.html#X7B9E71987E4294A7">4.10-9 SyndromeTable</a>
 <a href="chap4_mj.html#X8642D0BD789DA9B5">4.10-10 StandardArray</a>
 <a href="chap4_mj.html#X83231E717CCB0247">4.10-11 PermutationDecode</a>
 <a href="chap4_mj.html#X85B692177E2A745D">4.10-12 PermutationDecodeNC</a>
</div></div>
</div>

<h3>4 Codes</h3>

A code is a set of codewords (recall a codeword in GUAVA is simply a sequence of elements of a finite field \(GF(q)\), where \(q\) is a prime power). We call these the elements of the code. 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 <a href="chap3_mj.html#X836BAA9A7EBD08B1">3.</a>.

In GUAVA, codes can be a set specified by its elements (this will be called an unrestricted code), by a generator matrix listing a set of basis elements (for a linear code) or by a generator polynomial (for a cyclic code).

Any code can be defined by its elements. If you like, you can give the code a name.

<div class="example"><pre>
gap> C := ElementsCode(["1100", "1010", "0001"], "example code", GF(2) );
a (4,3,1..4)2..4 example code over GF(2)
</pre></div>

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 (except in the case where the code is a random linear codes, where these are not printed for efficiency reasons). So

<pre class="normal">

a (4,3,1..4)2..4 code over GF(2)

</pre>

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

<div class="example"><pre>
gap> C := ElementsCode(["1100", "1010", "0001"], "example code", GF(2) );
a (4,3,1..4)2..4 example code over GF(2)
gap> MinimumDistance(C);
2
gap> C;
a (4,3,2)2..4 example code over GF(2)
</pre></div>

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. By definition, the rows of the generator matrix is a basis for the code (as a vector space over \(GF(q)\)). By definition, the rows of the parity check matrix is a basis for the dual space of the code,

\[
C^* = \{ v \in GF(q)^n\ |\ v\cdot c = 0,\ for \ all\ c \in C \}.
\]

<div class="example"><pre>
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)
</pre></div>

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 codewords (regarded as \(n\)-tuples) are again codewords, the code is called cyclic. All elements of a cyclic code are multiples of the monic polynomial modulo a polynomial \(x^n -1\), where \(n\) is the word length of the code. Such a polynomial is called a generator polynomial The generator polynomial must divide \(x^n-1\) and its quotient is called a check polynomial. Multiplying a codeword in a cyclic code by the check polynomial yields zero (modulo the polynomial \(x^n -1\)). In GUAVA, a cyclic code can be defined by either its generator polynomial or check polynomial.

<div class="example"><pre>
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)
</pre></div>

It is possible that GUAVA does not know that an unrestricted code is in fact linear. This situation occurs for example when a code is generated from a list of elements with the function <code class="code">ElementsCode</code> (see <code class="func">ElementsCode</code> (<a href="chap5_mj.html#X81AACBDD86E89D7D">5.1-1</a>)). By calling the function <code class="code">IsLinearCode</code> (see <code class="func">IsLinearCode</code> (<a href="chap4_mj.html#X7B24748A7CE8D4B9">4.3-4</a>)), GUAVA tests if the code can be represented by a generator matrix. If so, the code record and the operations are converted accordingly.

<div class="example"><pre>
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
gap> C;
a linear [3,2,1]1 user defined unrestricted code over GF(2)
</pre></div>

Of course the same holds for unrestricted codes that in fact are cyclic, or codes, defined by a generator matrix, that actually are cyclic.

Codes are printed simply by giving a small description of their parameters, the word length, size or dimension and perhaps the minimum distance, followed by a short description and the base field of the code. The function <code class="code">Display</code> 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 functions <code class="code">Decode</code> or <code class="code">Decodeword</code>. For more information about encoding and decoding, see sections <a href="chap4_mj.html#X832DA51986A3882C">4.2</a> and <a href="chap4_mj.html#X7A42FF7D87FC34AC">4.10-1</a>.

<div class="example"><pre>
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. Corrected by Guava.
[ 1 0 1 1 ]
</pre></div>

Sections <a href="chap4_mj.html#X7ECE60E1873B49A6">4.1</a> and <a href="chap4_mj.html#X832DA51986A3882C">4.2</a> describe the operations that are available for codes. Section <a href="chap4_mj.html#X864091AA7D4AFE86">4.3</a> describe the functions that tests whether an object is a code and what kind of code it is (see <code class="code">IsCode</code>, <code class="func">IsLinearCode</code> (<a href="chap4_mj.html#X7B24748A7CE8D4B9">4.3-4</a>) and <code class="code">IsCyclicCode</code>) and various other boolean functions for codes. Section <a href="chap4_mj.html#X86442DCD7A0B2146">4.4</a> describe functions about equivalence and isomorphism of codes (see <code class="func">IsEquivalent</code> (<a href="chap4_mj.html#X843034687D9C75B0">4.4-1</a>), <code class="func">CodeIsomorphism</code> (<a href="chap4_mj.html#X874DED8E86BC180B">4.4-2</a>) and <code class="func">AutomorphismGroup</code> (<a href="chap4_mj.html#X87677B0787B4461A">4.4-3</a>)). Section <a href="chap4_mj.html#X866EB39483DDAE72">4.5</a> describes functions that work on domains (see Chapter "Domains and their Elements" in the GAP Reference Manual). Section <a href="chap4_mj.html#X823827927D6A8235">4.6</a> describes functions for printing and displaying codes. Section <a href="chap4_mj.html#X7D0F48B685A3ECDD">4.7</a> describes functions that return the matrices and polynomials that define a code (see <code class="func">GeneratorMat</code> (<a href="chap4_mj.html#X817224657C9829C4">4.7-1</a>), <code class="func">CheckMat</code> (<a href="chap4_mj.html#X85D4B26E7FB38D57">4.7-2</a>), <code class="func">GeneratorPol</code> (<a href="chap4_mj.html#X78E33C3A843B0261">4.7-3</a>), <code class="func">CheckPol</code> (<a href="chap4_mj.html#X7C45AA317BB1195F">4.7-4</a>), <code class="func">RootsOfCode</code> (<a href="chap4_mj.html#X7F4CB9DB7CD97178">4.7-5</a>)). Section <a href="chap4_mj.html#X8170B52D7C154247">4.8</a> describes functions that return the basic parameters of codes (see <code class="func">WordLength</code> (<a href="chap4_mj.html#X7A36C3C67B0062E8">4.8-1</a>), <code class="func">Redundancy</code> (<a href="chap4_mj.html#X7E33FD56792DBF3D">4.8-2</a>) and <code class="func">MinimumDistance</code> (<a href="chap4_mj.html#X7B31613D8538BD29">4.8-3</a>)). Section <a href="chap4_mj.html#X806384B4815EFF2E">4.9</a> describes functions that return distance and weight distributions (see <code class="func">WeightDistribution</code> (<a href="chap4_mj.html#X8728BCC9842A6E5D">4.9-2</a>), <code class="func">InnerDistribution</code> (<a href="chap4_mj.html#X871FD301820717A4">4.9-3</a>), <code class="func">OuterDistribution</code> (<a href="chap4_mj.html#X8495870687195324">4.9-5</a>) and <code class="func">DistancesDistribution</code> (<a href="chap4_mj.html#X87AD54F87C5EE77E">4.9-4</a>)). Section <a href="chap4_mj.html#X7D9A39BF801948C8">4.10</a> describes functions that are related to decoding (see <code class="func">Decode</code> (<a href="chap4_mj.html#X7A42FF7D87FC34AC">4.10-1</a>), <code class="func">Decodeword</code> (<a href="chap4_mj.html#X7D870C9387C47D9F">4.10-2</a>), <code class="func">Syndrome</code> (<a href="chap4_mj.html#X7D02E0FE8735D3E6">4.10-8</a>), <code class="func">SyndromeTable</code> (<a href="chap4_mj.html#X7B9E71987E4294A7">4.10-9</a>) and <code class="func">StandardArray</code> (<a href="chap4_mj.html#X8642D0BD789DA9B5">4.10-10</a>)). In Chapters <a href="chap5_mj.html#X87EB64ED831CCE99">5.</a> and <a href="chap6_mj.html#X866FC1117814B64D">6.</a> which follow, we describe functions that generate and manipulate codes.

<a id="X7ECE60E1873B49A6" name="X7ECE60E1873B49A6"></a>

<h4>4.1 Comparisons of Codes</h4>

<a id="X8686D5FA839F1A3D" name="X8686D5FA839F1A3D"></a>

<h5><code>4.1-1 \=</code></h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ \=</code>( <var class="Arg">C1</var>, <var class="Arg">C2</var> )</td><td class="tdright">( method )</td></tr></table></div>
The equality operator <code class="code">C1 = C2</code> evaluates to `true' if the codes <var class="Arg">C1</var> and <var class="Arg">C2</var> are equal, and to `false' otherwise.

The equality operator is also denoted <code class="code">EQ</code>, and <code class="code">Eq(C1,C2)</code> is the same as <code class="code">C1 = C2</code>. There is also an inequality operator, < >, or <code class="code">not EQ</code>.

Note that codes are equal if and only if their set of elements are equal. Codes can also be compared with objects of other types. Of course they are never equal.

<div class="example"><pre>
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
</pre></div>

Another way of comparing codes is <code class="code">IsEquivalent</code>, which checks if two codes are equivalent (see <code class="func">IsEquivalent</code> (<a href="chap4_mj.html#X843034687D9C75B0">4.4-1</a>)). By the way, this called <code class="code">CodeIsomorphism</code>. For the current version of GUAVA, unless one of the codes is unrestricted, this calls Leon's C program (which only works for binary linear codes and only on a unix/linux computer).

<a id="X832DA51986A3882C" name="X832DA51986A3882C"></a>

<h4>4.2 
Operations for Codes
</h4>

<a id="X82E2E5127CD25168" name="X82E2E5127CD25168"></a>

<h5><code>4.2-1 \+</code></h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ \+</code>( <var class="Arg">C1</var>, <var class="Arg">C2</var> )</td><td class="tdright">( method )</td></tr></table></div>
The operator `+' evaluates to the direct sum of the codes <var class="Arg">C1</var> and <var class="Arg">C2</var>. See <code class="func">DirectSumCode</code> (<a href="chap6_mj.html#X79E00D3A8367D65A">6.2-1</a>).

<div class="example"><pre>
gap> C1:=RandomLinearCode(10,5);
a [10,5,?] randomly generated code over GF(2)
gap> C2:=RandomLinearCode(9,4);
a [9,4,?] randomly generated code over GF(2)
gap> C1+C2;
a linear [19,9,1..2]4..9 direct sum code
</pre></div>

<a id="X7EFA08EE7BA22261" name="X7EFA08EE7BA22261"></a>

<h5><code>4.2-2 \*</code></h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ \*</code>( <var class="Arg">C1</var>, <var class="Arg">C2</var> )</td><td class="tdright">( method )</td></tr></table></div>
The operator `*' evaluates to the direct product of the codes <var class="Arg">C1</var> and <var class="Arg">C2</var>. See <code class="func">DirectProductCode</code> (<a href="chap6_mj.html#X7BFBBA5784C293C1">6.2-3</a>).

<div class="example"><pre>
gap> C1 := GeneratorMatCode( [ [1, 0,0,0], [0, 1,0,0] ], GF(2) );
a linear [4,2,1]1..2 code defined by generator matrix over GF(2)
gap> C2 := GeneratorMatCode( [ [0,0,1, 1], [0,0,0, 1] ], GF(2) );
a linear [4,2,1]1..2 code defined by generator matrix over GF(2)
gap> C1*C2;
a linear [16,4,1]4..12 direct product code
</pre></div>

<a id="X84D8B18F7C494A58" name="X84D8B18F7C494A58"></a>

<h5><code>4.2-3 \*</code></h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ \*</code>( <var class="Arg">m</var>, <var class="Arg">C</var> )</td><td class="tdright">( method )</td></tr></table></div>
The operator <code class="code">m*C</code> evaluates to the element of <var class="Arg">C</var> belonging to information word ('message') <var class="Arg">m</var>. Here <var class="Arg">m</var> may be a vector, polynomial, string or codeword or a list of those. This is the way to do encoding in GUAVA. <var class="Arg">C</var> must be linear, because in GUAVA, encoding by multiplication is only defined for linear codes. If <var class="Arg">C</var> is a cyclic code, this multiplication is the same as multiplying an information polynomial <var class="Arg">m</var> by the generator polynomial of <var class="Arg">C</var>. If <var class="Arg">C</var> is a linear code, it is equal to the multiplication of an information vector <var class="Arg">m</var> by a generator matrix of <var class="Arg">C</var>.

To invert this, use the function <code class="code">InformationWord</code> (see <code class="func">InformationWord</code> (<a href="chap4_mj.html#X8744BA5E78BCF3F9">4.2-4</a>), which simply calls the function <code class="code">Decode</code>).

<div class="example"><pre>
gap> C := GeneratorMatCode( [ [1, 0,0,0], [0, 1,0,0] ], GF(2) );
a linear [4,2,1]1..2 code defined by generator matrix over GF(2)
gap> m:=Codeword("11");
[ 1 1 ]
gap> m*C;
[ 1 1 0 0 ]
</pre></div>

<a id="X8744BA5E78BCF3F9" name="X8744BA5E78BCF3F9"></a>

<h5>4.2-4 InformationWord</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ InformationWord</code>( <var class="Arg">C</var>, <var class="Arg">c</var> )</td><td class="tdright">( function )</td></tr></table></div>
Here <var class="Arg">C</var> is a linear code and <var class="Arg">c</var> is a codeword in it. The command <code class="code">InformationWord</code> returns the message word (or 'information digits') \(m\) satisfying <code class="code">c=m*C</code>. This command simply calls <code class="code">Decode</code>, provided <code class="code">c in C</code> is true. Otherwise, it returns an error.

To invert this, use the encoding function <code class="code">*</code> (see <code class="func">\*</code> (<a href="chap4_mj.html#X84D8B18F7C494A58">4.2-3</a>)).

<div class="example"><pre>
gap> C:=HammingCode(3);
a linear [7,4,3]1 Hamming (3,2) code over GF(2)
gap> c:=Random(C);
[ 0 0 0 1 1 1 1 ]
gap> InformationWord(C,c);
[ 0 1 1 1 ]
gap> c:=Codeword("1111100");
[ 1 1 1 1 1 0 0 ]
gap> InformationWord(C,c);
Error, ERROR: codeword must belong to code
gap> C:=NordstromRobinsonCode();
a (16,256,6)4 Nordstrom-Robinson code over GF(2)
gap> c:=Random(C);
[ 0 0 0 1 0 0 0 1 0 0 1 0 1 1 0 1 ]
gap> InformationWord(C,c);
"ERROR: code must be linear"
</pre></div>

<a id="X864091AA7D4AFE86" name="X864091AA7D4AFE86"></a>

<h4>4.3 
Boolean Functions for Codes
</h4>

<a id="X87BDB89B7AAFE8AD" name="X87BDB89B7AAFE8AD"></a>

<h5>4.3-1 in</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ in</code>( <var class="Arg">c</var>, <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
The command <code class="code">c in C</code> evaluates to `true' if <var class="Arg">C</var> contains the codeword or list of codewords specified by <var class="Arg">c</var>. Of course, <var class="Arg">c</var> and <var class="Arg">C</var> must have the same word lengths and base fields.

<div class="example"><pre>
gap> C:= HammingCode( 2 );; eC:= AsSSortedList( C );
[ [ 0 0 0 ], [ 1 1 1 ] ]
gap> eC[2] in C;
true
gap> [ 0 ] in C;
false
</pre></div>

<a id="X79CA175481F8105F" name="X79CA175481F8105F"></a>

<h5>4.3-2 IsSubset</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsSubset</code>( <var class="Arg">C1</var>, <var class="Arg">C2</var> )</td><td class="tdright">( function )</td></tr></table></div>
The command <code class="code">IsSubset(C1,C2)</code> returns `true' if <var class="Arg">C2</var> is a subcode of <var class="Arg">C1</var>, i.e. if <var class="Arg">C1</var> contains all the elements of <var class="Arg">C2</var>.

<div class="example"><pre>
gap> IsSubset( HammingCode(3), RepetitionCode( 7 ) );
true
gap> IsSubset( RepetitionCode( 7 ), HammingCode( 3 ) );
false
gap> IsSubset( WholeSpaceCode( 7 ), HammingCode( 3 ) );
true
</pre></div>

<a id="X7F71186281DEA83A" name="X7F71186281DEA83A"></a>

<h5>4.3-3 IsCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsCode</code>( <var class="Arg">obj</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">IsCode</code> returns `true' if <var class="Arg">obj</var>, which can be an object of arbitrary type, is a code and `false' otherwise. Will cause an error if <var class="Arg">obj</var> is an unbound variable.

<div class="example"><pre>
gap> IsCode( 1 );
false
gap> IsCode( ReedMullerCode( 2,3 ) );
true
</pre></div>

<a id="X7B24748A7CE8D4B9" name="X7B24748A7CE8D4B9"></a>

<h5>4.3-4 IsLinearCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsLinearCode</code>( <var class="Arg">obj</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">IsLinearCode</code> checks if object <var class="Arg">obj</var> (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 <var class="Arg">obj</var> exists that generates the elements of <var class="Arg">obj</var>. If so, \(G\) is recorded as a generator matrix of <var class="Arg">obj</var> and the function returns `true'. If not, the function returns `false'.

<div class="example"><pre>
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
</pre></div>

<a id="X850C23D07C9A9B19" name="X850C23D07C9A9B19"></a>

<h5>4.3-5 IsCyclicCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsCyclicCode</code>( <var class="Arg">obj</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">IsCyclicCode</code> checks if the object <var class="Arg">obj</var> 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 <var class="Arg">obj</var>. If so, \(g\) is recorded as a generator polynomial of <var class="Arg">obj</var> and the function returns `true'. If not, the function returns `false'.

<div class="example"><pre>
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
</pre></div>

<a id="X85E3BD26856424F7" name="X85E3BD26856424F7"></a>

<h5>4.3-6 IsPerfectCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsPerfectCode</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">IsPerfectCode(C)</code> returns `true' if <var class="Arg">C</var> is a perfect code. If \(C\subset GF(q)^n\) then, by definition, this means that for some positive integer \(t\), the space \(GF(q)^n\) is covered by non-overlapping spheres of (Hamming) radius \(t\) centered at the codewords in <var class="Arg">C</var>. For a code with odd minimum distance \(d = 2t+1\), this is the case when every word of the vector space of <var class="Arg">C</var> is at distance at most \(t\) from exactly one element of <var class="Arg">C</var>. Codes with even minimum distance are never perfect.

In fact, a code that is not "trivially 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 (see section 1.12 in <a href="chapBib_mj.html#biBHP03">[HP03]</a>).

<div class="example"><pre>
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
</pre></div>

<a id="X789380D28018EC3F" name="X789380D28018EC3F"></a>

<h5>4.3-7 IsMDSCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsMDSCode</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">IsMDSCode(C)</code> returns true if <var class="Arg">C</var> is a maximum distance separable (MDS) code. 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 <var class="Arg">C</var> meets the Singleton bound (see <code class="func">UpperBoundSingleton</code> (<a href="chap7_mj.html#X8673277C7F6C04C3">7.1-1</a>)). 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 <var class="Arg">C</var>.

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.

<div class="example"><pre>
gap> C1 := ReedSolomonCode( 6, 3 );
a cyclic [6,4,3]2 Reed-Solomon code over GF(7)
gap> IsMDSCode( C1 ); # verify it is an MDS code, as 6-3+1 = 4
true
gap> IsMDSCode( QRCode( 23, GF(2) ) );
false
</pre></div>

<a id="X80166D8D837FEB58" name="X80166D8D837FEB58"></a>

<h5>4.3-8 IsSelfDualCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsSelfDualCode</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">IsSelfDualCode(C)</code> returns `true' if <var class="Arg">C</var> is self-dual, i.e. when <var class="Arg">C</var> is equal to its dual code (see also <code class="func">DualCode</code> (<a href="chap6_mj.html#X799B12F085ACB609">6.1-14</a>)). A code is self-dual if it contains all vectors that its elements are orthogonal to. If a code is self-dual, it automatically is self-orthogonal (see <code class="func">IsSelfOrthogonalCode</code> (<a href="chap4_mj.html#X7B2A0CC481D2366F">4.3-9</a>)).

If <var class="Arg">C</var> is a non-linear code, it cannot be self-dual (the dual code is always linear), so `false' is returned. A linear code can only be self-dual when its dimension \(k\) is equal to the redundancy \(r\).

<div class="example"><pre>
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
</pre></div>

<a id="X7B2A0CC481D2366F" name="X7B2A0CC481D2366F"></a>

<h5>4.3-9 IsSelfOrthogonalCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsSelfOrthogonalCode</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">IsSelfOrthogonalCode(C)</code> returns `true' if <var class="Arg">C</var> is self-orthogonal. A code is self-orthogonal if every element of <var class="Arg">C</var> is orthogonal to all elements of <var class="Arg">C</var>, including itself. (In the linear case, this simply means that the generator matrix of <var class="Arg">C</var> multiplied with its transpose yields a null matrix.)

<div class="example"><pre>
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
</pre></div>

<a id="X8358D43981EBE970" name="X8358D43981EBE970"></a>

<h5>4.3-10 IsDoublyEvenCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsDoublyEvenCode</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">IsDoublyEvenCode(C)</code> returns `true' if <var class="Arg">C</var> is a binary linear code which has codewords of weight divisible by 4 only. According to <a href="chapBib_mj.html#biBHP03">[HP03]</a>, a doubly-even code is self-orthogonal and every row in its generator matrix has weight that is divisible by 4.

<div class="example"><pre>
gap> C:=BinaryGolayCode();
a cyclic [23,12,7]3 binary Golay code over GF(2)
gap> WeightDistribution(C);
[ 1, 0, 0, 0, 0, 0, 0, 253, 506, 0, 0, 1288, 1288, 0, 0, 506, 253, 0, 0, 0,
 0, 0, 0, 1 ]
gap> IsDoublyEvenCode(C); 
false
gap> C:=ExtendedCode(C); 
a linear [24,12,8]4 extended code
gap> WeightDistribution(C);
[ 1, 0, 0, 0, 0, 0, 0, 0, 759, 0, 0, 0, 2576, 0, 0, 0, 759, 0, 0, 0, 0, 0, 0,
 0, 1 ]
gap> IsDoublyEvenCode(C); 
true
</pre></div>

<a id="X79ACAEF5865414A0" name="X79ACAEF5865414A0"></a>

<h5>4.3-11 IsSinglyEvenCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsSinglyEvenCode</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">IsSinglyEvenCode(C)</code> returns `true' if <var class="Arg">C</var> is a binary self-orthogonal linear code which is not doubly-even. In other words, <var class="Arg">C</var> is a binary self-orthogonal code which has codewords of even weight.

<div class="example"><pre>
gap> x:=Indeterminate(GF(2)); 
x_1
gap> C:=QuasiCyclicCode( [x^0, 1+x^3+x^5+x^6+x^7], 11, GF(2) );
a linear [22,11,1..6]4..7 quasi-cyclic code over GF(2)
gap> IsSelfDualCode(C); # self-dual is a restriction of self-orthogonal
true
gap> IsDoublyEvenCode(C);
false
gap> IsSinglyEvenCode(C);
true
</pre></div>

<a id="X7CE150ED7C3DC455" name="X7CE150ED7C3DC455"></a>

<h5>4.3-12 IsEvenCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsEvenCode</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">IsEvenCode(C)</code> returns `true' if <var class="Arg">C</var> is a binary linear code which has codewords of even weight--regardless whether or not it is self-orthogonal.

<div class="example"><pre>
gap> C:=BinaryGolayCode();
a cyclic [23,12,7]3 binary Golay code over GF(2)
gap> IsSelfOrthogonalCode(C);
false
gap> IsEvenCode(C);
false
gap> C:=ExtendedCode(C);
a linear [24,12,8]4 extended code
gap> IsSelfOrthogonalCode(C);
true
gap> IsEvenCode(C);
true
gap> C:=ExtendedCode(QRCode(17,GF(2)));
a linear [18,9,6]3..5 extended code
gap> IsSelfOrthogonalCode(C);
false
gap> IsEvenCode(C);
true
</pre></div>

<a id="X7B6DB8CC84FCAC1C" name="X7B6DB8CC84FCAC1C"></a>

<h5>4.3-13 IsSelfComplementaryCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsSelfComplementaryCode</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">IsSelfComplementaryCode</code> returns `true' if

\[
v \in C \Rightarrow 1 - v \in C,
\]

where \(1\) is the all-one word of length \(n\).

<div class="example"><pre>
gap> IsSelfComplementaryCode( HammingCode( 3, GF(2) ) );
true
gap> IsSelfComplementaryCode( EvenWeightSubcode(
> HammingCode( 3, GF(2) ) ) );
false
</pre></div>

<a id="X7AFD3844859B20BF" name="X7AFD3844859B20BF"></a>

<h5>4.3-14 IsAffineCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsAffineCode</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">IsAffineCode</code> returns `true' if <var class="Arg">C</var> is an affine code. A code is called affine if it is an affine space. In other words, a code is affine if it is a coset of a linear code.

<div class="example"><pre>
gap> IsAffineCode( HammingCode( 3, GF(2) ) );
true
gap> IsAffineCode( CosetCode( HammingCode( 3, GF(2) ),
> Codeword([ 1, 0, 0, 0, 0, 0, 0 ]) ) );
true
gap> IsAffineCode( NordstromRobinsonCode() );
false
</pre></div>

<a id="X861D32FB81EF0D77" name="X861D32FB81EF0D77"></a>

<h5>4.3-15 IsAlmostAffineCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsAlmostAffineCode</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">IsAlmostAffineCode</code> returns `true' if <var class="Arg">C</var> is an almost affine code. A code is called almost affine if the size of any punctured code of <var class="Arg">C</var> is \(q^r\) for some \(r\), where \(q\) is the size of the alphabet of the code. Every affine code is also almost affine, and every code over \(GF(2)\) and \(GF(3)\) that is almost affine is also affine.

<div class="example"><pre>
gap> code := ElementsCode( [ [0,0,0], [0,1,1], [0,2,2], [0,3,3],
> [1,0,1], [1,1,0], [1,2,3], [1,3,2],
> [2,0,2], [2,1,3], [2,2,0], [2,3,1],
> [3,0,3], [3,1,2], [3,2,1], [3,3,0] ],
> GF(4) );;
gap> IsAlmostAffineCode( code );
true
gap> IsAlmostAffineCode( NordstromRobinsonCode() );
false
</pre></div>

<a id="X86442DCD7A0B2146" name="X86442DCD7A0B2146"></a>

<h4>4.4 
Equivalence and Isomorphism of Codes
</h4>

<a id="X843034687D9C75B0" name="X843034687D9C75B0"></a>

<h5>4.4-1 IsEquivalent</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsEquivalent</code>( <var class="Arg">C1</var>, <var class="Arg">C2</var> )</td><td class="tdright">( function )</td></tr></table></div>
We say that <var class="Arg">C1</var> is permutation equivalent to <var class="Arg">C2</var> if <var class="Arg">C1</var> can be obtained from <var class="Arg">C2</var> by carrying out column permutations. <code class="code">IsEquivalent</code> returns true if <var class="Arg">C1</var> and <var class="Arg">C2</var> are equivalent codes. At this time, <code class="code">IsEquivalent</code> only handles binary codes. (The external unix/linux program desauto from J. S. Leon is called by <code class="code">IsEquivalent</code>.) Of course, if <var class="Arg">C1</var> and <var class="Arg">C2</var> are equal, they are also equivalent.

Note that the algorithm is very slow for non-linear codes.

More generally, we say that <var class="Arg">C1</var> is equivalent to <var class="Arg">C2</var> if <var class="Arg">C1</var> can be obtained from <var class="Arg">C2</var> by carrying out column permutations and a permutation of the alphabet.

<div class="example"><pre>
gap> x:= Indeterminate( GF(2), "x" );; pol:= x^3+x+1; 
x^3+x+Z(2)^0
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

# verify that H is equivalent to a Hamming code
gap> IsEquivalent(H, HammingCode(3, GF(2)));
true
gap> CodeIsomorphism(H, HammingCode(3, GF(2)));
(3,4)(5,6,7)
</pre></div>

<a id="X874DED8E86BC180B" name="X874DED8E86BC180B"></a>

<h5>4.4-2 CodeIsomorphism</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CodeIsomorphism</code>( <var class="Arg">C1</var>, <var class="Arg">C2</var> )</td><td class="tdright">( function )</td></tr></table></div>
If the two codes <var class="Arg">C1</var> and <var class="Arg">C2</var> are permutation equivalent codes (see <code class="func">IsEquivalent</code> (<a href="chap4_mj.html#X843034687D9C75B0">4.4-1</a>)), <code class="code">CodeIsomorphism</code> returns the permutation that transforms <var class="Arg">C1</var> into <var class="Arg">C2</var>. If the codes are not equivalent, it returns `false'.

At this time, <code class="code">IsEquivalent</code> only computes isomorphisms between binary codes on a linux/unix computer (since it calls Leon's C program desauto).

<div class="example"><pre>
gap> x:= Indeterminate( GF(2), "x" );; pol:= x^3+x+1; 
x^3+x+Z(2)^0
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
</pre></div>

<a id="X87677B0787B4461A" name="X87677B0787B4461A"></a>

<h5>4.4-3 AutomorphismGroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AutomorphismGroup</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">AutomorphismGroup</code> returns the automorphism group of a linear code <var class="Arg">C</var>. For a binary code, the automorphism group is the largest permutation group of degree \(n\) such that each permutation applied to the columns of <var class="Arg">C</var> again yields <var class="Arg">C</var>. GUAVA calls the external program desauto written by J. S. Leon, if it exists, to compute the automorphism group. If Leon's program is not compiled on the system (and in the default directory) then it calls instead the much slower program <code class="code">PermutationAutomorphismGroup</code>.

See Leon <a href="chapBib_mj.html#biBLeon82">[Leo82]</a> for a more precise description of the method, and the <code class="file">guava/src/leon/doc</code> subdirectory for for details about Leon's C programs.

The function <code class="code">PermutedCode</code> permutes the columns of a code (see <code class="func">PermutedCode</code> (<a href="chap6_mj.html#X79577EB27BE8524B">6.1-4</a>)).

<div class="example"><pre>
gap> R := RepetitionCode(7,GF(2));
a cyclic [7,1,7]3 repetition code over GF(2)

# verify that every permutation keeps R identical, that is, the
# automorphism group is Sym(7)
gap> AutomorphismGroup(R);
Sym( [ 1 .. 7 ] )
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
</pre></div>

<a id="X79F3261F86C29F6D" name="X79F3261F86C29F6D"></a>

<h5>4.4-4 PermutationAutomorphismGroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PermutationAutomorphismGroup</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">PermutationAutomorphismGroup</code> returns the permutation automorphism group of a linear code <var class="Arg">C</var>. This is the largest permutation group of degree \(n\) such that each permutation applied to the columns of <var class="Arg">C</var> again yields <var class="Arg">C</var>. It is written in GAP, so is much slower than <code class="code">AutomorphismGroup</code>.

When <var class="Arg">C</var> is binary <code class="code">PermutationAutomorphismGroup</code> does not call <code class="code">AutomorphismGroup</code>, even though they agree mathematically in that case. This way <code class="code">PermutationAutomorphismGroup</code> can be called on any platform which runs GAP.

The older name for this command, <code class="code">PermutationGroup</code>, will become obsolete in the next version of GAP.

<div class="example"><pre>
gap> R := RepetitionCode(3,GF(3));
a cyclic [3,1,3]2 repetition code over GF(3)
gap> G:=PermutationAutomorphismGroup(R);;
gap> G=SymmetricGroup(3);
true
</pre></div>

<a id="X866EB39483DDAE72" name="X866EB39483DDAE72"></a>

<h4>4.5 
Domain Functions for Codes
</h4>

These are some GAP functions that work on `Domains' in general. Their specific effect on `Codes' is explained here.

<a id="X808A4061809A6E67" name="X808A4061809A6E67"></a>

<h5>4.5-1 IsFinite</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsFinite</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">IsFinite</code> is an implementation of the GAP domain function <code class="code">IsFinite</code>. It returns true for a code <var class="Arg">C</var>.

<div class="example"><pre>
gap> IsFinite( RepetitionCode( 1000, GF(11) ) );
true
</pre></div>

<a id="X858ADA3B7A684421" name="X858ADA3B7A684421"></a>

<h5>4.5-2 Size</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Size</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">Size</code> returns the size of <var class="Arg">C</var>, the number of elements of the code. If the code is linear, the size of the code is equal to \(q^k\), where \(q\) is the size of the base field of <var class="Arg">C</var> and \(k\) is the dimension.

<div class="example"><pre>
gap> Size( RepetitionCode( 1000, GF(11) ) );
11
gap> Size( NordstromRobinsonCode() );
256
</pre></div>

<a id="X86F070E0807DC34E" name="X86F070E0807DC34E"></a>

<h5>4.5-3 LeftActingDomain</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LeftActingDomain</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">LeftActingDomain</code> returns the base field of a code <var class="Arg">C</var>. Each element of <var class="Arg">C</var> 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 \(F^n\). If <var class="Arg">C</var> is a cyclic code, its elements are interpreted as polynomials with coefficients over \(F\).

<div class="example"><pre>
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)
</pre></div>

<a id="X7E6926C6850E7C4E" name="X7E6926C6850E7C4E"></a>

<h5>4.5-4 Dimension</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Dimension</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">Dimension</code> returns the parameter \(k\) of <var class="Arg">C</var>, the dimension of the code, or the number of information symbols in each codeword. The dimension is not defined for non-linear codes; <code class="code">Dimension</code> then returns an error.

<div class="example"><pre>
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
</pre></div>

<a id="X856D927378C33548" name="X856D927378C33548"></a>

<h5>4.5-5 AsSSortedList</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AsSSortedList</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">AsSSortedList</code> (as strictly sorted list) returns an immutable, duplicate free list of the elements of <var class="Arg">C</var>. For a finite field \(GF(q)\) generated by powers of \(Z(q)\), the ordering on

\[
GF(q)=\{ 0 , Z(q)^0, Z(q), Z(q)^2, ...Z(q)^{q-2} \}
\]

is that determined by the exponents \(i\). These elements are of the type codeword (see <code class="func">Codeword</code> (<a href="chap3_mj.html#X7B9E353D852851AA">3.1-1</a>)). 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 <code class="code">CodewordNr</code> (see <code class="func">CodewordNr</code> (<a href="chap3_mj.html#X7E7ED91C79BF3EF3">3.1-2</a>)).

<div class="example"><pre>
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 ] ]
</pre></div>

<a id="X823827927D6A8235" name="X823827927D6A8235"></a>

<h4>4.6 
Printing and Displaying Codes
</h4>

<a id="X7AFA64D97A1F39A3" name="X7AFA64D97A1F39A3"></a>

<h5>4.6-1 Print</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Print</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">Print</code> prints information about <var class="Arg">C</var>. This is the same as typing the identifier <var class="Arg">C</var> at the GAP-prompt.

If the argument is an unrestricted code, information in the form

<pre class="normal">

a (n,M,d)r ... code over GF(q)

</pre>

is printed, where <var class="Arg">n</var> is the word length, <var class="Arg">M</var> the number of elements of the code, <var class="Arg">d</var> the minimum distance and <var class="Arg">r</var> the covering radius.

If the argument is a linear code, information in the form

<pre class="normal">

a linear [n,k,d]r ... code over GF(q)

</pre>

is printed, where <var class="Arg">n</var> is the word length, <var class="Arg">k</var> the dimension of the code, <var class="Arg">d</var> the minimum distance and <var class="Arg">r</var> the covering radius.

Except for codes produced by <code class="code">RandomLinearCode</code>, if <var class="Arg">d</var> is not yet known, it is displayed in the form

<pre class="normal">

lowerbound..upperbound

</pre>

and if <var class="Arg">r</var> is not yet known, it is displayed in the same way. For certain ranges of \(n\), the values of <var class="Arg">lowerbound</var> and <var class="Arg">upperbound</var> are obtained from tables.

The function <code class="code">Display</code> gives more information. See <code class="func">Display</code> (<a href="chap4_mj.html#X83A5C59278E13248">4.6-3</a>).

<div class="example"><pre>
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).
</pre></div>

<a id="X81FB5BE27903EC32" name="X81FB5BE27903EC32"></a>

<h5>4.6-2 String</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ String</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">String</code> returns information about <var class="Arg">C</var> in a string. This function is used by <code class="code">Print</code>.

<div class="example"><pre>
gap> x:= Indeterminate( GF(3), "x" );; pol:= x^2+1;
x^2+Z(3)^0
gap> Factors(pol);
[ x^2+Z(3)^0 ]
gap> H := GeneratorPolCode( pol, 8, GF(3));
a cyclic [8,6,1..2]1..2 code defined by generator polynomial over GF(3)
gap> String(H);
"a cyclic [8,6,1..2]1..2 code defined by generator polynomial over GF(3)"
</pre></div>

<a id="X83A5C59278E13248" name="X83A5C59278E13248"></a>

<h5>4.6-3 Display</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Display</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">Display</code> prints the method of construction of code <var class="Arg">C</var>. With this history, in most cases an equal or equivalent code can be reconstructed. If <var class="Arg">C</var> is an unmanipulated code, the result is equal to output of the function <code class="code">Print</code> (see <code class="func">Print</code> (<a href="chap4_mj.html#X7AFA64D97A1F39A3">4.6-1</a>)).

<div class="example"><pre>
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)
</pre></div>

<a id="X7CD08C8C780543C4" name="X7CD08C8C780543C4"></a>

<h5>4.6-4 DisplayBoundsInfo</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DisplayBoundsInfo</code>( <var class="Arg">bds</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">DisplayBoundsInfo</code> prints the method of construction of the code \(C\) indicated in <code class="code">bds:= BoundsMinimumDistance( n, k, GF(q) )</code>.

<div class="example"><pre>
gap> bounds := BoundsMinimumDistance( 20, 17, GF(4) );;
gap> DisplayBoundsInfo(bounds);
an optimal linear [20,17,d] code over GF(4) has d=3
------------------------------------------------------------------------------
Lb(20,17)=3, by shortening of:
Lb(21,18)=3, by applying construction B to a [81,77,3] code
Lb(81,77)=3, by shortening of:
Lb(85,81)=3, reference: Ham
------------------------------------------------------------------------------
Ub(20,17)=3, by considering shortening to:
Ub(7,4)=3, by considering puncturing to:
Ub(6,4)=2, by construction B applied to:
Ub(2,1)=2, repetition code
------------------------------------------------------------------------------
Reference Ham:
%T this reference is unknown, for more info
%T contact A.E. Brouwer (aeb@cwi.nl)
</pre></div>

<a id="X7D0F48B685A3ECDD" name="X7D0F48B685A3ECDD"></a>

<h4>4.7 
Generating (Check) Matrices and Polynomials
</h4>

<a id="X817224657C9829C4" name="X817224657C9829C4"></a>

<h5>4.7-1 GeneratorMat</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GeneratorMat</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">GeneratorMat</code> returns a generator matrix of <var class="Arg">C</var>. The code consists of all linear combinations of the rows of this matrix.

If until now no generator matrix of <var class="Arg">C</var> 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 <var class="Arg">C</var> is a non-linear code, the function returns an error.

<div class="example"><pre>
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> Display(last);
1 1 1 . . . .
1 . . 1 1 . .
. 1 . 1 . 1 .
1 1 . 1 . . 1
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) ) );
[ ]
</pre></div>

<a id="X85D4B26E7FB38D57" name="X85D4B26E7FB38D57"></a>

<h5>4.7-2 CheckMat</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CheckMat</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">CheckMat</code> returns a parity check matrix of <var class="Arg">C</var>. 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 <var class="Arg">C</var> (if possible), whichever is available.

If <var class="Arg">C</var> is a non-linear code, the function returns an error.

<div class="example"><pre>
gap> CheckMat( HammingCode(3, GF(2) ) );
[ [ 0*Z(2), 0*Z(2), 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), 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 ] ]
gap> Display(last);
. . . 1 1 1 1
. 1 1 . . 1 1
1 . 1 . 1 . 1
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) ) );
[ ]
</pre></div>

<a id="X78E33C3A843B0261" name="X78E33C3A843B0261"></a>

<h5>4.7-3 GeneratorPol</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GeneratorPol</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">GeneratorPol</code> returns the generator polynomial of <var class="Arg">C</var>. The code consists of all multiples of the generator polynomial modulo \(x^{n}-1\), where \(n\) is the word length of <var class="Arg">C</var>. The generator polynomial is determined from either the check polynomial, the generator or check matrix or the elements of <var class="Arg">C</var> (if possible), whichever is available.

If <var class="Arg">C</var> is not a cyclic code, the function returns `false'.

<div class="example"><pre>
gap> GeneratorPol(GeneratorMatCode([[1, 1, 0], [0, 1, 1]], GF(2)));
x_1+Z(2)^0
gap> GeneratorPol( WholeSpaceCode( 4, GF(2) ) );
Z(2)^0
gap> GeneratorPol( NullCode( 7, GF(3) ) );
x_1^7-Z(3)^0
</pre></div>

<a id="X7C45AA317BB1195F" name="X7C45AA317BB1195F"></a>

<h5>4.7-4 CheckPol</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CheckPol</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">CheckPol</code> returns the check polynomial of <var class="Arg">C</var>. The code consists of all polynomials \(f\) with

\[
f\cdot h \equiv 0 \ ({\rm mod}\ x^n-1),
\]

where \(h\) is the check polynomial, and \(n\) is the word length of <var class="Arg">C</var>. The check polynomial is computed from the generator polynomial, the generator or parity check matrix or the elements of <var class="Arg">C</var> (if possible), whichever is available.

If <var class="Arg">C</var> if not a cyclic code, the function returns an error.

<div class="example"><pre>
gap> CheckPol(GeneratorMatCode([[1, 1, 0], [0, 1, 1]], GF(2)));
x_1^2+x_1+Z(2)^0
gap> CheckPol(WholeSpaceCode(4, GF(2)));
x_1^4+Z(2)^0
gap> CheckPol(NullCode(7,GF(3)));
Z(3)^0
</pre></div>

<a id="X7F4CB9DB7CD97178" name="X7F4CB9DB7CD97178"></a>

<h5>4.7-5 RootsOfCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RootsOfCode</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">RootsOfCode</code> returns a list of all zeros of the generator polynomial of a cyclic code <var class="Arg">C</var>. These are finite field elements in the splitting field of the generator polynomial, \(GF(q^m)\), \(m\) is the multiplicative order of the size of the base field of the code, modulo the word length.

The reverse process, constructing a code from a set of roots, can be carried out by the function <code class="code">RootsCode</code> (see <code class="func">RootsCode</code> (<a href="chap5_mj.html#X818F0E6583E01D4B">5.5-3</a>)).

<div class="example"><pre>
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
</pre></div>

<a id="X8170B52D7C154247" name="X8170B52D7C154247"></a>

<h4>4.8 
Parameters of Codes
</h4>

<a id="X7A36C3C67B0062E8" name="X7A36C3C67B0062E8"></a>

<h5>4.8-1 WordLength</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ WordLength</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">WordLength</code> returns the parameter \(n\) of <var class="Arg">C</var>, the word length of the elements. Elements of cyclic codes are polynomials of maximum degree \(n-1\), as calculations are carried out modulo \(x^{n}-1\).

<div class="example"><pre>
gap> WordLength( NordstromRobinsonCode() );
16
gap> WordLength( PuncturedCode( WholeSpaceCode(7) ) );
6
gap> WordLength( UUVCode( WholeSpaceCode(7), RepetitionCode(7) ) );
14
</pre></div>

<a id="X7E33FD56792DBF3D" name="X7E33FD56792DBF3D"></a>

<h5>4.8-2 Redundancy</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Redundancy</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">Redundancy</code> returns the redundancy \(r\) of <var class="Arg">C</var>, which is equal to the number of check symbols in each element. If <var class="Arg">C</var> is not a linear code the redundancy is not defined and <code class="code">Redundancy</code> returns an error.

If a linear code <var class="Arg">C</var> has dimension \(k\) and word length \(n\), it has redundancy \(r=n-k\).

<div class="example"><pre>
gap> C := TernaryGolayCode();
a cyclic [11,6,5]2 ternary Golay code over GF(3)
gap> Redundancy(C);
5
gap> Redundancy( DualCode(C) );
6
</pre></div>

<a id="X7B31613D8538BD29" name="X7B31613D8538BD29"></a>

<h5>4.8-3 MinimumDistance</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MinimumDistance</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">MinimumDistance</code> returns the minimum distance of <var class="Arg">C</var>, the largest integer \(d\) with the property that every element of <var class="Arg">C</var> has at least a Hamming distance \(d\) (see <code class="func">DistanceCodeword</code> (<a href="chap3_mj.html#X7CDA1B547D55E6FB">3.6-2</a>)) to any other element of <var class="Arg">C</var>. 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] \neq 0\), where \(w=(w[1],w[2],...,w[n])\) is the weight distribution of <var class="Arg">C</var> (see <code class="func">WeightDistribution</code> (<a href="chap4_mj.html#X8728BCC9842A6E5D">4.9-2</a>)). For unrestricted codes, \(d\) is the smallest positive value with \(w[d+1] \neq 0\), where \(w\) is the inner distribution of <var class="Arg">C</var> (see <code class="func">InnerDistribution</code> (<a href="chap4_mj.html#X871FD301820717A4">4.9-3</a>)).

For codes with only one element, the minimum distance is defined to be equal to the word length.

For linear codes <var class="Arg">C</var>, the algorithm used is the following: After replacing <var class="Arg">C</var> by a permutation equivalent <var class="Arg">C'</var>, one may assume the generator matrix has the following form \(G=(I_{k} \, | \, A)\), for some \(k\times (n-k)\) matrix \(A\). If \(A=0\) then return \(d(C)=1\). Next, find the minimum distance of the code spanned by the rows of \(A\). Call this distance \(d(A)\). Note that \(d(A)\) is equal to the the Hamming distance \(d(v,0)\) where \(v\) is some proper linear combination of \(i\) distinct rows of \(A\). Return \(d(C)=d(A)+i\), where \(i\) is as in the previous step.

This command may also be called using the syntax <code class="code">MinimumDistance(C, w)</code>. In this form, <code class="code">MinimumDistance</code> returns the minimum distance of a codeword <var class="Arg">w</var> to the code <var class="Arg">C</var>, also called the distance from <var class="Arg">w</var> to <var class="Arg">C</var>. This is the smallest value \(d\) for which there is an element \(c\) of the code <var class="Arg">C</var> which is at distance \(d\) from <var class="Arg">w</var>. So \(d\) is also the minimum value for which \(D[d+1] \neq 0\), where \(D\) is the distance distribution of <var class="Arg">w</var> to <var class="Arg">C</var> (see <code class="func">DistancesDistribution</code> (<a href="chap4_mj.html#X87AD54F87C5EE77E">4.9-4</a>)).

Note that <var class="Arg">w</var> must be an element of the same vector space as the elements of <var class="Arg">C</var>. <var class="Arg">w</var> does not necessarily belong to the code (if it does, the minimum distance is zero).

<div class="example"><pre>
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 ]
gap> C := MOLSCode(7);; w := CodewordNr( C, 17 );
[ 3 3 6 2 ]
gap> MinimumDistance( C, w );
0
gap> C := RemovedElementsCode( C, w );; # so w no longer belongs to C 
gap> MinimumDistance( C, w );
3
</pre></div>

See also the GUAVA commands relating to bounds on the minimum distance in section <a href="chap7_mj.html#X87C753EB840C34D3">7.1</a>.

<a id="X813F226F855590EE" name="X813F226F855590EE"></a>

<h5>4.8-4 MinimumDistanceLeon</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MinimumDistanceLeon</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">MinimumDistanceLeon</code> returns the ``probable'' minimum distance \(d_{Leon}\) of a linear binary code <var class="Arg">C</var>, using an implementation of Leon's probabilistic polynomial time algorithm. Briefly: Let <var class="Arg">C</var> be a linear code of dimension \(k\) over \(GF(q)\) as above. The algorithm has input parameters \(s\) and \(\rho\), where \(s\) is an integer between \(2\) and \(n-k\), and \(\rho\) is an integer between \(2\) and \(k\).

<ul>
<li>Find a generator matrix \(G\) of \(C\).

</li>
<li>Randomly permute the columns of \(G\).

</li>
<li>Perform Gaussian elimination on the permuted matrix to obtain a new matrix of the following form:

\[
G=(I_{k} \, | \, Z \, | \, B)
\]

with \(Z\) a \(k\times s\) matrix. If \((Z,B)\) is the zero matrix then return \(1\) for the minimum distance. If \(Z=0\) but not \(B\) then either choose another permutation of the rows of <var class="Arg">C</var> or return `method fails'.

</li>
<li>Search \(Z\) for at most \(\rho\) rows that lead to codewords of weight less than \(\rho\).

</li>
<li>For these codewords, compute the weight of the whole word in <var class="Arg">C</var>. Return this weight.

</li>
</ul>
(See for example J. S. Leon, <a href="chapBib_mj.html#biBLeon88">[Leo88]</a> for more details.) Sometimes (as is the case in GUAVA) this probabilistic algorithm is repeated several times and the most commonly occurring value is taken. (This function actually has two optional arguments: <code class="code">p</code> and <code class="code">num</code>. The command <code class="code">MinimumDistanceLeon(C,p,num)</code> allows a bit more flexibility for the user - see the GAP code in codeops.gi for details.)

<div class="example"><pre>
gap> C:=RandomLinearCode(50,22,GF(2));
a [50,22,?] randomly generated code over GF(2)
gap> MinimumDistanceLeon(C); #time; #Uncomment the call to "time;"" to see performance data
6
gap> MinimumDistance(C); #time; #Uncomment the call to "time;"" to see performance data
6
</pre></div>

<a id="X84EDF67B86B4154C" name="X84EDF67B86B4154C"></a>

<h5>4.8-5 MinimumWeight</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MinimumWeight</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">MinimumWeight</code> returns the minimum Hamming weight of a linear code <var class="Arg">C</var>. At the moment, this function works for binary and ternary codes only. The <code class="code">MinimumWeight</code> function relies on an external executable program which is written in C language. As a consequence, the execution time of <code class="code">MinimumWeight</code> function is faster than that of <code class="func">MinimumDistance</code> (<a href="chap4_mj.html#X7B31613D8538BD29">4.8-3</a>) function.

The <code class="code">MinimumWeight</code> function implements Chen's <a href="chapBib_mj.html#biBChen69">[Che69]</a> algorithm if <var class="Arg">C</var> is cyclic, and Zimmermann's <a href="chapBib_mj.html#biBZimmermann96">[Zim96]</a> algorithm if <var class="Arg">C</var> is a general linear code. This function has a built-in check on the constraints of the minimum weight codewords. For example, for a self-orthogonal code over GF(3), the minimum weight codewords have weight that is divisible by 3, i.e. 0 mod 3 congruence. Similarly, self-orthogonal codes over GF(2) have codeword weights that are divisible by 4 and even codes over GF(2) have codewords weights that are divisible by 2. By taking these constraints into account, in many cases, the execution time may be significantly reduced. Consider the minimum Hamming weight enumeration of the \([151,45]\) binary cyclic code (second example below). This cyclic code is self-orthogonal, so the weight of all codewords is divisible by 4. Without considering this constraint, the computation will finish at information weight \(10\), rather than \(9\). We can see that, this 0 mod 4 constraint on the codeword weights, has allowed us to avoid enumeration of \(b(45,10) = 3,190,187,286\) additional codewords, where \(b(n,k)=n!/((n-k)!k!)\) is the binomial coefficient of integers \(n\) and \(k\).

Note that the C source code for this minimum weight computation has not yet been optimised, especially the code for GF(3), and there are chances to improve the speed of this function. Your contributions are most welcomed.

If you find any bugs on this function, please report it to ctjhai@plymouth.ac.uk.

<div class="example"><pre>
gap> # Extended ternary quadratic residue code of length 48
gap> n := 47;;
gap> x := Indeterminate(GF(3), "x");;
gap> F := Factors(x^n-1);;
gap> v := NullVector(n,GF(3));;
gap> v := v + ShallowCopy(VectorCodeword( Codeword(F[2]) ));;
gap> G := CirculantMatrix(24, v);;
gap> for i in [1..Size(G)] do; s:=Zero(GF(3));
> for j in [1..Size(G[i])] do; s:=s+G[i][j]; od; Append(G[i], [ s ]);
> od;;
gap> C := GeneratorMatCodeNC(G, GF(3));
a [48,24,?] randomly generated code over GF(3)
gap> MinimumWeight(C);
15
gap> # Binary cyclic code [151,45,36]
gap> n := 151;;
gap> x := Indeterminate(GF(2), "x");;
gap> F := Factors(x^n-1);;
gap> C := CheckPolCode(F[2]*F[3]*F[3]*F[4], n, GF(2));
a cyclic [151,45,1..50]31..75 code defined by check polynomial over GF(2)
gap> MinimumWeight(C);
36
</pre></div>

<a id="X823B9A797EE42F6D" name="X823B9A797EE42F6D"></a>

<h5>4.8-6 DecreaseMinimumDistanceUpperBound</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DecreaseMinimumDistanceUpperBound</code>( <var class="Arg">C</var>, <var class="Arg">t</var>, <var class="Arg">m</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">DecreaseMinimumDistanceUpperBound</code> is an implementation of the algorithm for the minimum distance of a linear binary code <var class="Arg">C</var> by Leon <a href="chapBib_mj.html#biBLeon88">[Leo88]</a>. This algorithm tries to find codewords with small minimum weights. The parameter <var class="Arg">t</var> is at least \(1\) and less than the dimension of <var class="Arg">C</var>. The best results are obtained if it is close to the dimension of the code. The parameter <var class="Arg">m</var> gives the number of runs that the algorithm will perform.

The result returned is a record with two fields; the first, <code class="code">mindist</code>, gives the lowest weight found, and <code class="code">word</code> gives the corresponding codeword. (This was implemented before <code class="code">MinimumDistanceLeon</code> but independently. The older manual had given the command incorrectly, so the command was only found after reading all the *.gi files in the GUAVA library. Though both <code class="code">MinimumDistance</code> and <code class="code">MinimumDistanceLeon</code> often run much faster than <code class="code">DecreaseMinimumDistanceUpperBound</code>, <code class="code">DecreaseMinimumDistanceUpperBound</code> appears to be more accurate than <code class="code">MinimumDistanceLeon</code>.)

<div class="example"><pre>
gap> C:=RandomLinearCode(5,2,GF(2));
a [5,2,?] randomly generated code over GF(2)
gap> DecreaseMinimumDistanceUpperBound(C,1,4);
rec( mindist := 3, word := [ 0*Z(2), Z(2)^0, Z(2)^0, 0*Z(2), Z(2)^0 ] )
gap> MinimumDistance(C);
3
gap> C:=RandomLinearCode(8,4,GF(2));
a [8,4,?] randomly generated code over GF(2)
gap> DecreaseMinimumDistanceUpperBound(C,3,4);
rec( mindist := 2,
 word := [ Z(2)^0, 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), Z(2)^0 ] )
gap> MinimumDistance(C);
2
</pre></div>

<a id="X7A679B0A7816B030" name="X7A679B0A7816B030"></a>

<h5>4.8-7 MinimumDistanceRandom</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MinimumDistanceRandom</code>( <var class="Arg">C</var>, <var class="Arg">num</var>, <var class="Arg">s</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">MinimumDistanceRandom</code> returns an upper bound for the minimum distance \(d_{random}\) of a linear binary code <var class="Arg">C</var>, using a probabilistic polynomial time algorithm. Briefly: Let <var class="Arg">C</var> be a linear code of dimension \(k\) over \(GF(q)\) as above. The algorithm has input parameters \(num\) and \(s\), where \(s\) is an integer between \(2\) and \(n-1\), and \(num\) is an integer greater than or equal to \(1\).

<ul>
<li>Find a generator matrix \(G\) of \(C\).

</li>
<li>Randomly permute the columns of \(G\), written \(G_p\)..

</li>
<li>\[
G=(A, B)
\]

with \(A\) a \(k\times s\) matrix. If \(A\) is the zero matrix then return `method fails'.

</li>
<li>Search \(A\) for at most \(5\) rows that lead to codewords, in the code \(C_A\) with generator matrix \(A\), of minimum weight.

</li>
<li>For these codewords, use the associated linear combination to compute the weight of the whole word in <var class="Arg">C</var>. Return this weight and codeword.

</li>
</ul>
This probabilistic algorithm is repeated <var class="Arg">num</var> times (with different random permutations of the rows of \(G\) each time) and the weight and codeword of the lowest occurring weight is taken.

<div class="example"><pre>
gap> C:=RandomLinearCode(60,20,GF(2));
a [60,20,?] randomly generated code over GF(2)
gap> #mindist(C); #time;
gap> #mindistleon(C,10,30); #time; #doesn't work well
gap> a:=MinimumDistanceRandom(C,10,30); #time; # done 10 times -with fastest time!!

This is a probabilistic algorithm which may return the wrong answer.
[ 12, [ 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0
 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 ] ]
gap> a[2] in C;
true
gap> b:=DecreaseMinimumDistanceUpperBound(C,10,1); #time; #only done once!
rec( mindist := 12, word := [ 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2),
 Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2),
 0*Z(2), Z(2)^0, Z(2)^0, 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2), 0*Z(2),
 Z(2)^0, 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2),
 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2),
 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2),
 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2) ] )
gap> Codeword(b!.word) in C;
true
gap> MinimumDistance(C); #time; #Uncomment the call to "time;"" to see performance data
12
gap> c:=MinimumDistanceLeon(C); #time; #Uncomment the call to "time;"" to see performance data
12
gap> C:=RandomLinearCode(30,10,GF(3));
a [30,10,?] randomly generated code over GF(3)
gap> a:=MinimumDistanceRandom(C,10,10); #time; #Uncomment the call to "time;"" to see performance data

This is a probabilistic algorithm which may return the wrong answer.
[ 13, [ 0 0 0 1 0 0 0 0 0 0 1 0 2 2 1 1 0 2 2 0 1 0 2 1 0 0 0 1 0 2 ] ]
gap> a[2] in C;
true
gap> MinimumDistance(C); #time; #Uncomment the call to "time;"" to see performance data
9
gap> c:=MinimumDistanceLeon(C);
Code must be binary. Quitting.
0
gap> a:=MinimumDistanceRandom(C,1,29); #time; #Uncomment the call to "time;"" to see performance data

This is a probabilistic algorithm which may return the wrong answer.
[ 10, [ 0 0 1 0 2 0 2 0 1 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 2 2 2 0 ] ]
</pre></div>

<a id="X7A195E317D2AB7CE" name="X7A195E317D2AB7CE"></a>

<h5>4.8-8 CoveringRadius</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CoveringRadius</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">CoveringRadius</code> returns the covering radius of a linear code <var class="Arg">C</var>. This is the smallest number \(r\) with the property that each element \(v\) of the ambient vector space of <var class="Arg">C</var> has at most a distance \(r\) to the code <var class="Arg">C</var>. So for each vector \(v\) there must be an element \(c\) of <var class="Arg">C</var> with \(d(v,c) \leq r\). The smallest covering radius of any \([n,k]\) binary linear code is denoted \(t(n,k)\). A binary linear code with reasonable small covering radius is called a covering code.

If <var class="Arg">C</var> is a perfect code (see <code class="func">IsPerfectCode</code> (<a href="chap4_mj.html#X85E3BD26856424F7">4.3-6</a>)), the covering radius is equal to \(t\), the number of errors the code can correct, where \(d = 2t+1\), with \(d\) the minimum distance of <var class="Arg">C</var> (see <code class="func">MinimumDistance</code> (<a href="chap4_mj.html#X7B31613D8538BD29">4.8-3</a>)).

If there exists a function called <code class="code">SpecialCoveringRadius</code> in the `operations' field of the code, then this function will be called to compute the covering radius of the code. At the moment, no code-specific functions are implemented.

If the length of <code class="code">BoundsCoveringRadius</code> (see <code class="func">BoundsCoveringRadius</code> (<a href="chap7_mj.html#X8320D1C180A1AAAD">7.2-1</a>)), is 1, then the value in

<pre class="normal">

C.boundsCoveringRadius

</pre>

is returned. Otherwise, the function

<pre class="normal">

C.operations.CoveringRadius

</pre>

is executed, unless the redundancy of <var class="Arg">C</var> is too large. In the last case, a warning is issued.

The algorithm used to compute the covering radius is the following. First, <code class="code">CosetLeadersMatFFE</code> is used to compute the list of coset leaders (which returns a codeword in each coset of \(GF(q)^n/C\) of minimum weight). Then <code class="code">WeightVecFFE</code> is used to compute the weight of each of these coset leaders. The program returns the maximum of these weights.

<div class="example"><pre>
gap> H := RandomLinearCode(10, 5, GF(2));
a [10,5,?] randomly generated code over GF(2)
gap> CoveringRadius(H);
3
gap> H := HammingCode(4, GF(2));; IsPerfectCode(H);
true
gap> CoveringRadius(H); # Hamming codes have minimum distance 3
1
gap> CoveringRadius(ReedSolomonCode(7,4));
3
gap> CoveringRadius( BCHCode( 17, 3, GF(2) ) );
3
gap> CoveringRadius( HammingCode( 5, GF(2) ) );
1
gap> C := ReedMullerCode( 1, 9 );;
gap> CoveringRadius( C );
CoveringRadius: warning, the covering radius of
this code cannot be computed straightforward.
Try to use IncreaseCoveringRadiusLowerBound( <code> ).
(see the manual for more details).
The covering radius of <code> lies in the interval:
[ 240 .. 248 ]
</pre></div>

See also the GUAVA commands relating to bounds on the minimum distance in section <a href="chap7_mj.html#X817D0A647D3331EB">7.2</a>.

<a id="X81004B007EC5DF58" name="X81004B007EC5DF58"></a>

<h5>4.8-9 SetCoveringRadius</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SetCoveringRadius</code>( <var class="Arg">C</var>, <var class="Arg">intlist</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">SetCoveringRadius</code> enables the user to set the covering radius herself, instead of letting GUAVA compute it. If <var class="Arg">intlist</var> is an integer, GUAVA will simply put it in the `boundsCoveringRadius' field. If it is a list of integers, however, it will intersect this list with the `boundsCoveringRadius' field, thus taking the best of both lists. If this would leave an empty list, the field is set to <var class="Arg">intlist</var>. Because some other computations use the covering radius of the code, it is important that the entered value is not wrong, otherwise new results may be invalid.

<div class="example"><pre>
gap> C := BCHCode( 17, 3, GF(2) );;
gap> BoundsCoveringRadius( C );
[ 3, 4 ]
gap> SetCoveringRadius( C, [ 2 .. 3 ] );
gap> BoundsCoveringRadius( C );
[ [ 2, 3 ] ]
</pre></div>

<a id="X806384B4815EFF2E" name="X806384B4815EFF2E"></a>

<h4>4.9 
Distributions
</h4>

<a id="X7AEE64467FB1E0B9" name="X7AEE64467FB1E0B9"></a>

<h5>4.9-1 MinimumWeightWords</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MinimumWeightWords</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">MinimumWeightWords</code> returns the list of minimum weight codewords of <var class="Arg">C</var>.

This algorithm is written in GAP and is rather slow. It is only suitable for small codes.

This does not call the very fast function <code class="code">MinimumWeight</code> (see <code class="func">MinimumWeight</code> (<a href="chap4_mj.html#X84EDF67B86B4154C">4.8-5</a>)).

<div class="example"><pre>
gap> C:=HammingCode(3,GF(2));
a linear [7,4,3]1 Hamming (3,2) code over GF(2)
gap> MinimumWeightWords(C);
[ [ 1 0 0 0 0 1 1 ], [ 0 1 0 1 0 1 0 ], [ 0 1 0 0 1 0 1 ], [ 1 0 0 1 1 0 0 ],
 [ 0 0 1 0 1 1 0 ], [ 0 0 1 1 0 0 1 ], [ 1 1 1 0 0 0 0 ] ]
</pre></div>

<a id="X8728BCC9842A6E5D" name="X8728BCC9842A6E5D"></a>

<h5>4.9-2 WeightDistribution</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ WeightDistribution</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">WeightDistribution</code> returns the weight distribution of <var class="Arg">C</var>, as a vector. The \(i^{th}\) element of this vector contains the number of elements of <var class="Arg">C</var> with weight \(i-1\). For linear codes, the weight distribution is equal to the inner distribution (see <code class="func">InnerDistribution</code> (<a href="chap4_mj.html#X871FD301820717A4">4.9-3</a>)). If \(w\) is the weight distribution of a linear code <var class="Arg">C</var>, it must have the zero codeword, so \(w[1] = 1\) (one word of weight 0).

Some codes, such as the Hamming codes, have precomputed weight distributions. For others, the program WeightDistribution calls the GAP program <code class="code">DistancesDistributionMatFFEVecFFE</code>, which is written in C. See also <code class="code">CodeWeightEnumerator</code>.

<div class="example"><pre>
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 ]
</pre></div>

<a id="X871FD301820717A4" name="X871FD301820717A4"></a>

<h5>4.9-3 InnerDistribution</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ InnerDistribution</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">InnerDistribution</code> returns the inner distribution of <var class="Arg">C</var>. The \(i^{th}\) element of the vector contains the average number of elements of <var class="Arg">C</var> at distance \(i-1\) to an element of <var class="Arg">C</var>. For linear codes, the inner distribution is equal to the weight distribution (see <code class="func">WeightDistribution</code> (<a href="chap4_mj.html#X8728BCC9842A6E5D">4.9-2</a>)).

Suppose \(w\) is the inner distribution of <var class="Arg">C</var>. Then \(w[1] = 1\), because each element of <var class="Arg">C</var> has exactly one element at distance zero (the element itself). The minimum distance of <var class="Arg">C</var> is the smallest value \(d > 0\) with \(w[d+1] \neq 0\), because a distance between zero and \(d\) never occurs. See <code class="func">MinimumDistance</code> (<a href="chap4_mj.html#X7B31613D8538BD29">4.8-3</a>).

<div class="example"><pre>
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 ]
</pre></div>

<a id="X87AD54F87C5EE77E" name="X87AD54F87C5EE77E"></a>

<h5>4.9-4 DistancesDistribution</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DistancesDistribution</code>( <var class="Arg">C</var>, <var class="Arg">w</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">DistancesDistribution</code> returns the distribution of the distances of all elements of <var class="Arg">C</var> to a codeword <var class="Arg">w</var> in the same vector space. The \(i^{th}\) element of the distance distribution is the number of codewords of <var class="Arg">C</var> that have distance \(i-1\) to <var class="Arg">w</var>. The smallest value \(d\) with \(w[d+1] \neq 0\), is defined as the distance to <var class="Arg">C</var> (see <code class="func">MinimumDistance</code> (<a href="chap4_mj.html#X7B31613D8538BD29">4.8-3</a>)).

<div class="example"><pre>
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); # distance to H 
5
</pre></div>

<a id="X8495870687195324" name="X8495870687195324"></a>

<h5>4.9-5 OuterDistribution</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OuterDistribution</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
The function <code class="code">OuterDistribution</code> returns a list of length \(q^n\), where \(q\) is the size of the base field of <var class="Arg">C</var> and \(n\) is the word length. The elements of the list consist of pairs, the first coordinate being an element of \(GF(q)^n\) (this is a codeword type) and the second coordinate being a 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 <code class="code">DistancesDistribution</code> (see <code class="func">DistancesDistribution</code> (<a href="chap4_mj.html#X87AD54F87C5EE77E">4.9-4</a>)) can be used to calculate one entry of the list.

<div class="example"><pre>
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
</pre></div>

<a id="X7D9A39BF801948C8" name="X7D9A39BF801948C8"></a>

<h4>4.10 
Decoding Functions
</h4>

<a id="X7A42FF7D87FC34AC" name="X7A42FF7D87FC34AC"></a>

<h5>4.10-1 Decode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Decode</code>( <var class="Arg">C</var>, <var class="Arg">r</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">Decode</code> decodes <var class="Arg">r</var> (a 'received word') with respect to code <var class="Arg">C</var> and returns the `message word' (i.e., the information digits associated to the codeword \(c \in C\) closest to <var class="Arg">r</var>). Here <var class="Arg">r</var> can be a GUAVA codeword or a list of codewords. First, possible errors in <var class="Arg">r</var> are corrected, then the codeword is decoded to an information codeword \(m\) (and not an element of <var class="Arg">C</var>). If the code record has a field `specialDecoder', this special algorithm is used to decode the vector. Hamming codes, cyclic codes, and generalized Reed-Solomon have such a special algorithm. (The algorithm used for BCH codes is the Sugiyama algorithm described, for example, in section 5.4.3 of <a href="chapBib_mj.html#biBHP03">[HP03]</a>. A special decoder has also being written for the generalized Reed-Solomon code using the interpolation algorithm. For cyclic codes, the error-trapping algorithm is used.) If <var class="Arg">C</var> is linear and no special decoder field has been set then syndrome decoding is used. Otherwise (when <var class="Arg">C</var> is non-linear), the nearest neighbor decoding algorithm is used (which is very slow).

A special decoder can be created by defining a function

<pre class="normal">

C!.SpecialDecoder := function(C, r) ... end;

</pre>

The function uses the arguments <var class="Arg">C</var> (the code record itself) and <var class="Arg">r</var> (a vector of the codeword type) to decode <var class="Arg">r</var> to an information vector. A normal decoder would take a codeword <var class="Arg">r</var> of the same word length and field as <var class="Arg">C</var>, and would return an information vector of length \(k\), the dimension of <var class="Arg">C</var>. The user is not restricted to these normal demands though, and can for instance define a decoder for non-linear codes.

Encoding is done by multiplying the information vector with the code (see <a href="chap4_mj.html#X832DA51986A3882C">4.2</a>).

<div class="example"><pre>
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")); # one error corrected
[ 1 1 0 1 ]
gap> C!.SpecialDecoder := function(C, c)
> return NullWord(Dimension(C));
> end;
function( C, c ) ... end
gap> Decode(C, c); # new decoder always returns null word 
[ 0 0 0 0 ]
</pre></div>

<a id="X7D870C9387C47D9F" name="X7D870C9387C47D9F"></a>

<h5>4.10-2 Decodeword</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Decodeword</code>( <var class="Arg">C</var>, <var class="Arg">r</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">Decodeword</code> decodes <var class="Arg">r</var> (a 'received word') with respect to code <var class="Arg">C</var> and returns the codeword \(c \in C\) closest to <var class="Arg">r</var>. Here <var class="Arg">r</var> can be a GUAVA codeword or a list of codewords. If the code record has a field `specialDecoder', this special algorithm is used to decode the vector. Hamming codes, generalized Reed-Solomon codes, and BCH codes have such a special algorithm. (The algorithm used for BCH codes is the Sugiyama algorithm described, for example, in section 5.4.3 of <a href="chapBib_mj.html#biBHP03">[HP03]</a>. The algorithm used for generalized Reed-Solomon codes is the ``interpolation algorithm'' described for example in chapter 5 of <a href="chapBib_mj.html#biBJH04">[JH04]</a>.) If <var class="Arg">C</var> is linear and no special decoder field has been set then syndrome decoding is used. Otherwise, when <var class="Arg">C</var> is non-linear, the nearest neighbor algorithm has been implemented (which should only be used for small-sized codes).

<div class="example"><pre>
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> Decodeword(C, c); # decoding
[ 1 0 1 1 0 1 0 ]
gap> R:=PolynomialRing(GF(11),["t"]);
GF(11)[t]
gap> P:=List([1,3,4,5,7],i->Z(11)^i);
[ Z(11), Z(11)^3, Z(11)^4, Z(11)^5, Z(11)^7 ]
gap> C:=GeneralizedReedSolomonCode(P,3,R);
a linear [5,3,1..3]2 generalized Reed-Solomon code over GF(11)
gap> MinimumDistance(C);
3
gap> c:=Random(C);
[ 0 9 6 2 1 ]
gap> v:=Codeword("09620");
[ 0 9 6 2 0 ]
gap> GeneralizedReedSolomonDecoderGao(C,v);
[ 0 9 6 2 1 ]
gap> Decodeword(C,v); # calls the special interpolation decoder
[ 0 9 6 2 1 ]
gap> G:=GeneratorMat(C);
[ [ Z(11)^0, 0*Z(11), 0*Z(11), Z(11)^8, Z(11)^9 ],
 [ 0*Z(11), Z(11)^0, 0*Z(11), Z(11)^0, Z(11)^8 ],
 [ 0*Z(11), 0*Z(11), Z(11)^0, Z(11)^3, Z(11)^8 ] ]
gap> C1:=GeneratorMatCode(G,GF(11));
a linear [5,3,1..3]2 code defined by generator matrix over GF(11)
gap> Decodeword(C,v); # calls syndrome decoding
[ 0 9 6 2 1 ]
</pre></div>

<a id="X7D48DE2A84474C6A" name="X7D48DE2A84474C6A"></a>

<h5>4.10-3 GeneralizedReedSolomonDecoderGao</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GeneralizedReedSolomonDecoderGao</code>( <var class="Arg">C</var>, <var class="Arg">r</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">GeneralizedReedSolomonDecoderGao</code> decodes <var class="Arg">r</var> (a 'received word') to a codeword \(c \in C\) in a generalized Reed-Solomon code <var class="Arg">C</var> (see <code class="func">GeneralizedReedSolomonCode</code> (<a href="chap5_mj.html#X810AB3DB844FFCE9">5.6-2</a>)), closest to <var class="Arg">r</var>. Here <var class="Arg">r</var> must be a GUAVA codeword. If the code record does not have name `generalized Reed-Solomon code' then an error is returned. Otherwise, the Gao decoder <a href="chapBib_mj.html#biBGao03">[Gao03]</a> is used to compute \(c\).

For long codes, this method is faster in practice than the interpolation method used in <code class="code">Decodeword</code>.

<div class="example"><pre>
gap> R:=PolynomialRing(GF(11),["t"]);
GF(11)[t]
gap> P:=List([1,3,4,5,7],i->Z(11)^i);
[ Z(11), Z(11)^3, Z(11)^4, Z(11)^5, Z(11)^7 ]
gap> C:=GeneralizedReedSolomonCode(P,3,R);
a linear [5,3,1..3]2 generalized Reed-Solomon code over GF(11)
gap> MinimumDistance(C);
3
gap> c:=Random(C);
[ 0 9 6 2 1 ]
gap> v:=Codeword("09620");
[ 0 9 6 2 0 ]
gap> GeneralizedReedSolomonDecoderGao(C,v); 
[ 0 9 6 2 1 ]
</pre></div>

<a id="X7CFF98D483502053" name="X7CFF98D483502053"></a>

<h5>4.10-4 GeneralizedReedSolomonListDecoder</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GeneralizedReedSolomonListDecoder</code>( <var class="Arg">C</var>, <var class="Arg">r</var>, <var class="Arg">tau</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">GeneralizedReedSolomonListDecoder</code> implements Sudans list-decoding algorithm (see section 12.1 of <a href="chapBib_mj.html#biBJH04">[JH04]</a>) for ``low rate'' Reed-Solomon codes. It returns the list of all codewords in C which are a distance of at most <var class="Arg">tau</var> from <var class="Arg">r</var> (a 'received word'). <var class="Arg">C</var> must be a generalized Reed-Solomon code <var class="Arg">C</var> (see <code class="func">GeneralizedReedSolomonCode</code> (<a href="chap5_mj.html#X810AB3DB844FFCE9">5.6-2</a>)) and <var class="Arg">r</var> must be a GUAVA codeword.

<div class="example"><pre>
gap> F:=GF(16);
GF(2^4)
gap> a:=PrimitiveRoot(F);; b:=a^7;; b^4+b^3+1; 
0*Z(2)
gap> Pts:=List([0..14],i->b^i);
[ Z(2)^0, Z(2^4)^7, Z(2^4)^14, Z(2^4)^6, Z(2^4)^13, Z(2^2), Z(2^4)^12,
 Z(2^4)^4, Z(2^4)^11, Z(2^4)^3, Z(2^2)^2, Z(2^4)^2, Z(2^4)^9, Z(2^4),
 Z(2^4)^8 ]
gap> x:=X(F);;
gap> R1:=PolynomialRing(F,[x]);;
gap> vars:=IndeterminatesOfPolynomialRing(R1);;
gap> y:=X(F,vars);;
gap> R2:=PolynomialRing(F,[x,y]);;
gap> C:=GeneralizedReedSolomonCode(Pts,3,R1); 
a linear [15,3,1..13]10..12 generalized Reed-Solomon code over GF(16)
gap> MinimumDistance(C); ## 6 error correcting
13
gap> z:=Zero(F);;
gap> r:=[z,z,z,z,z,z,z,z,b^6,b^2,b^5,b^14,b,b^7,b^11];; 
gap> r:=Codeword(r);
[ 0 0 0 0 0 0 0 0 a^12 a^14 a^5 a^8 a^7 a^4 a^2 ]
gap> cs:=GeneralizedReedSolomonListDecoder(C,r,2); #time; #Uncomment the call to "time;"" to see performance data
[ [ 0 a^9 a^3 a^13 a^6 a^10 a^11 a a^12 a^14 a^5 a^8 a^7 a^4 a^2 ],
 [ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ] ]
gap> c1:=cs[1]; c1 in C;
[ 0 a^9 a^3 a^13 a^6 a^10 a^11 a a^12 a^14 a^5 a^8 a^7 a^4 a^2 ]
true
gap> c2:=cs[2]; c2 in C;
[ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
true
gap> WeightCodeword(c1-r);
7
gap> WeightCodeword(c2-r);
7
</pre></div>

<a id="X80E17FA27DCAB676" name="X80E17FA27DCAB676"></a>

<h5>4.10-5 BitFlipDecoder</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BitFlipDecoder</code>( <var class="Arg">C</var>, <var class="Arg">r</var> )</td><td class="tdright">( function )</td></tr></table></div>
The iterative decoding method <code class="code">BitFlipDecoder</code> must only be applied to LDPC codes. For more information on LDPC codes, refer to Section <a href="chap5_mj.html#X84F3673D7BBF5956">5.8</a>. For these codes, <code class="code">BitFlipDecoder</code> decodes very quickly. (Warning: it can give wildly wrong results for arbitrary binary linear codes.) The bit flipping algorithm is described for example in Chapter 13 of <a href="chapBib_mj.html#biBJH04">[JH04]</a>.

<div class="example"><pre>
gap> C:=HammingCode(4,GF(2));
a linear [15,11,3]1 Hamming (4,2) code over GF(2)
gap> c:=Random(C);
[ 0 0 0 1 0 0 1 0 0 1 1 0 1 0 1 ]
gap> v:=List(c);
[ 0*Z(2), 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2),
 Z(2)^0, Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2), Z(2)^0 ]
gap> v[1]:=Z(2)+v[1]; # flip 1st bit of c to create an error
Z(2)^0
gap> v:=Codeword(v);
[ 1 0 0 1 0 0 1 0 0 1 1 0 1 0 1 ]
gap> BitFlipDecoder(C,v);
[ 0 0 0 1 0 0 1 0 0 1 1 0 1 0 1 ]
</pre></div>

<a id="X7B88DEB37F28404A" name="X7B88DEB37F28404A"></a>

<h5>4.10-6 NearestNeighborGRSDecodewords</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NearestNeighborGRSDecodewords</code>( <var class="Arg">C</var>, <var class="Arg">v</var>, <var class="Arg">dist</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">NearestNeighborGRSDecodewords</code> finds all generalized Reed-Solomon codewords within distance <var class="Arg">dist</var> from <var class="Arg">v</var> and the associated polynomial, using ``brute force''. Input: <var class="Arg">v</var> is a received vector (a GUAVA codeword), <var class="Arg">C</var> is a GRS code, <var class="Arg">dist</var> > 0 is the distance from <var class="Arg">v</var> to search in <var class="Arg">C</var>. Output: a list of pairs \([c,f(x)]\), where \(wt(c-v)\leq dist-1\) and \(c = (f(x_1),...,f(x_n))\).

<div class="example"><pre>
gap> F:=GF(16);
GF(2^4)
gap> a:=PrimitiveRoot(F);; b:=a^7; b^4+b^3+1;
Z(2^4)^7
0*Z(2)
gap> Pts:=List([0..14],i->b^i);
[ Z(2)^0, Z(2^4)^7, Z(2^4)^14, Z(2^4)^6, Z(2^4)^13, Z(2^2), Z(2^4)^12,
 Z(2^4)^4, Z(2^4)^11, Z(2^4)^3, Z(2^2)^2, Z(2^4)^2, Z(2^4)^9, Z(2^4),
 Z(2^4)^8 ]
gap> x:=X(F);;
gap> R1:=PolynomialRing(F,[x]);;
gap> vars:=IndeterminatesOfPolynomialRing(R1);;
gap> y:=X(F,vars);;
gap> R2:=PolynomialRing(F,[x,y]);;
gap> C:=GeneralizedReedSolomonCode(Pts,3,R1);
a linear [15,3,1..13]10..12 generalized Reed-Solomon code over GF(16)
gap> MinimumDistance(C); # 6 error correcting
13
gap> z:=Zero(F);
0*Z(2)
gap> r:=[z,z,z,z,z,z,z,z,b^6,b^2,b^5,b^14,b,b^7,b^11];; # 7 errors
gap> r:=Codeword(r);
[ 0 0 0 0 0 0 0 0 a^12 a^14 a^5 a^8 a^7 a^4 a^2 ]
gap> cs:=NearestNeighborGRSDecodewords(C,r,7);
[ [ [ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ], 0*Z(2) ],
 [ [ 0 a^9 a^3 a^13 a^6 a^10 a^11 a a^12 a^14 a^5 a^8 a^7 a^4 a^2 ],
 x_1+Z(2)^0 ] ]
</pre></div>

<a id="X825E35757D778787" name="X825E35757D778787"></a>

<h5>4.10-7 NearestNeighborDecodewords</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NearestNeighborDecodewords</code>( <var class="Arg">C</var>, <var class="Arg">v</var>, <var class="Arg">dist</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">NearestNeighborDecodewords</code> finds all codewords in a linear code <var class="Arg">C</var> within distance <var class="Arg">dist</var> from <var class="Arg">v</var>, using ``brute force''. Input: <var class="Arg">v</var> is a received vector (a GUAVA codeword), <var class="Arg">C</var> is a linear code, <var class="Arg">dist</var> > 0 is the distance from <var class="Arg">v</var> to search in <var class="Arg">C</var>. Output: a list of \(c \in C\), where \(wt(c-v)\leq dist-1\).

<div class="example"><pre>
gap> F:=GF(16);
GF(2^4)
gap> a:=PrimitiveRoot(F);; b:=a^7; b^4+b^3+1;
Z(2^4)^7
0*Z(2)
gap> Pts:=List([0..14],i->b^i);
[ Z(2)^0, Z(2^4)^7, Z(2^4)^14, Z(2^4)^6, Z(2^4)^13, Z(2^2), Z(2^4)^12,
 Z(2^4)^4, Z(2^4)^11, Z(2^4)^3, Z(2^2)^2, Z(2^4)^2, Z(2^4)^9, Z(2^4),
 Z(2^4)^8 ]
gap> x:=X(F);;
gap> R1:=PolynomialRing(F,[x]);;
gap> vars:=IndeterminatesOfPolynomialRing(R1);;
gap> y:=X(F,vars);;
gap> R2:=PolynomialRing(F,[x,y]);;
gap> C:=GeneralizedReedSolomonCode(Pts,3,R1);
a linear [15,3,1..13]10..12 generalized Reed-Solomon code over GF(16)
gap> MinimumDistance(C);
13
gap> z:=Zero(F);
0*Z(2)
gap> r:=[z,z,z,z,z,z,z,z,b^6,b^2,b^5,b^14,b,b^7,b^11];;
gap> r:=Codeword(r);
[ 0 0 0 0 0 0 0 0 a^12 a^14 a^5 a^8 a^7 a^4 a^2 ]
gap> cs:=NearestNeighborDecodewords(C,r,7);
[ [ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ],
 [ 0 a^9 a^3 a^13 a^6 a^10 a^11 a a^12 a^14 a^5 a^8 a^7 a^4 a^2 ] ]
</pre></div>

<a id="X7D02E0FE8735D3E6" name="X7D02E0FE8735D3E6"></a>

<h5>4.10-8 Syndrome</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Syndrome</code>( <var class="Arg">C</var>, <var class="Arg">v</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">Syndrome</code> returns the syndrome of word <var class="Arg">v</var> with respect to a linear code <var class="Arg">C</var>. <var class="Arg">v</var> is a codeword in the ambient vector space of <var class="Arg">C</var>. If <var class="Arg">v</var> is an element of <var class="Arg">C</var>, the syndrome is a zero vector. The syndrome can be used for looking up an error vector in the syndrome table (see <code class="func">SyndromeTable</code> (<a href="chap4_mj.html#X7B9E71987E4294A7">4.10-9</a>)) that is needed to correct an error in \(v\).

A syndrome is not defined for non-linear codes. <code class="code">Syndrome</code> then returns an error.

<div class="example"><pre>
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" ) ); # the same syndrome: both codewords are in the same coset of C 
[ 1 1 1 1 ]
</pre></div>

<a id="X7B9E71987E4294A7" name="X7B9E71987E4294A7"></a>

<h5>4.10-9 SyndromeTable</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SyndromeTable</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">SyndromeTable</code> returns a syndrome table of a linear code <var class="Arg">C</var>, 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 <var class="Arg">v</var> with <code class="code">Syndrome</code> (see <code class="func">Syndrome</code> (<a href="chap4_mj.html#X7D02E0FE8735D3E6">4.10-8</a>)), the error vector needed to correct <var class="Arg">v</var> can be found in the syndrome table. Subtracting this vector from <var class="Arg">v</var> yields an element of <var class="Arg">C</var>. To make the search for the syndrome as fast as possible, the syndrome table is sorted according to the syndrome vectors.

<div class="example"><pre>
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; # c is not an element of H
false
gap> Syndrome(H,c); # according to the syndrome table, the error vector [ 0 1 0 ] belongs to this syndrome
[ 1 0 ]
gap> c - Codeword("010") in H; # so the corrected codeword is [ 1 0 1 ] - [ 0 1 0 ] = [ 1 1 1 ], this is an element of H 
true
</pre></div>

<a id="X8642D0BD789DA9B5" name="X8642D0BD789DA9B5"></a>

<h5>4.10-10 StandardArray</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ StandardArray</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">StandardArray</code> returns the standard array of a code <var class="Arg">C</var>. This is a matrix with elements of the codeword type. It has \(q^r\) rows and \(q^k\) columns, where \(q\) is the size of the base field of <var class="Arg">C</var>, \(r=n-k\) is the redundancy of <var class="Arg">C</var>, and \(k\) is the dimension of <var class="Arg">C</var>. The first row contains all the elements of <var class="Arg">C</var>. Each other row contains words that do not belong to the code, with in the first column their syndrome vector (see <code class="func">Syndrome</code> (<a href="chap4_mj.html#X7D02E0FE8735D3E6">4.10-8</a>)).

A non-linear code does not have a standard array. <code class="code">StandardArray</code> then returns an error.

Note that calculating a standard array can be very time- and memory- consuming.

<div class="example"><pre>
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 ] ] ]
</pre></div>

<a id="X83231E717CCB0247" name="X83231E717CCB0247"></a>

<h5>4.10-11 PermutationDecode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PermutationDecode</code>( <var class="Arg">C</var>, <var class="Arg">v</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">PermutationDecode</code> performs permutation decoding when possible and returns original vector and prints 'fail' when not possible.

This uses <code class="code">AutomorphismGroup</code> in the binary case, and (the slower) <code class="code">PermutationAutomorphismGroup</code> otherwise, to compute the permutation automorphism group \(P\) of <var class="Arg">C</var>. The algorithm runs through the elements \(p\) of \(P\) checking if the weight of \(H(p\cdot v)\) is less than \((d-1)/2\). If it is then the vector \(p\cdot v\) is used to decode \(v\): assuming <var class="Arg">C</var> is in standard form then \(c=p^{-1}Em\) is the decoded word, where \(m\) is the information digits part of \(p\cdot v\). If no such \(p\) exists then ``fail'' is returned. See, for example, section 10.2 of Huffman and Pless <a href="chapBib_mj.html#biBHP03">[HP03]</a> for more details.

<div class="example"><pre>
gap> C0:=HammingCode(3,GF(2));
a linear [7,4,3]1 Hamming (3,2) code over GF(2)
gap> G0:=GeneratorMat(C0);;
gap> G := List(G0, ShallowCopy);;
gap> PutStandardForm(G);
()
gap> Display(G);
1 . . . . 1 1
. 1 . . 1 . 1
. . 1 . 1 1 .
. . . 1 1 1 1
gap> H0:=CheckMat(C0);;
gap> Display(H0);
. . . 1 1 1 1
. 1 1 . . 1 1
1 . 1 . 1 . 1
gap> c0:=Random(C0);
[ 0 0 0 1 1 1 1 ]
gap> v01:=c0[1]+Z(2)^2;;
gap> v1:=List(c0, ShallowCopy);;
gap> v1[1]:=v01;;
gap> v1:=Codeword(v1);
[ 1 0 0 1 1 1 1 ]
gap> c1:=PermutationDecode(C0,v1);
[ 0 0 0 1 1 1 1 ]
gap> c1=c0;
true
</pre></div>

<a id="X85B692177E2A745D" name="X85B692177E2A745D"></a>

<h5>4.10-12 PermutationDecodeNC</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PermutationDecodeNC</code>( <var class="Arg">C</var>, <var class="Arg">v</var>, <var class="Arg">P</var> )</td><td class="tdright">( function )</td></tr></table></div>
Same as <code class="code">PermutationDecode</code> except that one may enter the permutation automorphism group <var class="Arg">P</var> in as an argument, saving time. Here <var class="Arg">P</var> is a subgroup of the symmetric group on \(n\) letters, where \(n\) is the word length of <var class="Arg">C</var>.

<div class="chlinkprevnextbot"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap3_mj.html">[Previous Chapter]</a> <a href="chap5_mj.html">[Next Chapter]</a> </div>

<div class="chlinkbot">Goto Chapter: <a href="chap0_mj.html">Top</a> <a href="chap1_mj.html">1</a> <a href="chap2_mj.html">2</a> <a href="chap3_mj.html">3</a> <a href="chap4_mj.html">4</a> <a href="chap5_mj.html">5</a> <a href="chap6_mj.html">6</a> <a href="chap7_mj.html">7</a> <a href="chap8_mj.html">8</a> <a href="chap9_mj.html">9</a> <a href="chapBib_mj.html">Bib</a> <a href="chapInd_mj.html">Ind</a> </div>

<hr />
generated by <a href="https://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a>
</body>
</html>

Messung V0.5 in Prozent

¤ Dauer der Verarbeitung: 0.55 Sekunden (vorverarbeitet am 2026-04-28) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung und die Messung sind noch experimentell.