Quelle chap5_mj.html

Sprache: HTML

products/Sources/formale Sprachen/GAP/pkg/guava/doc/chap5_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 5: Generating 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="chap5" 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="chap4_mj.html">[Previous Chapter]</a> <a href="chap6_mj.html">[Next Chapter]</a> </div>

<a href="chap5.html">[MathJax off]</a>
<a id="X87EB64ED831CCE99" name="X87EB64ED831CCE99"></a>
<div class="ChapSects"><a href="chap5_mj.html#X87EB64ED831CCE99">5 Generating Codes</a>
<div class="ContSect"> <a href="chap5_mj.html#X86A92CB184CBD3C7">5.1 
Generating Unrestricted Codes
</a>

<div class="ContSSBlock">
 <a href="chap5_mj.html#X81AACBDD86E89D7D">5.1-1 ElementsCode</a>
 <a href="chap5_mj.html#X86755AAC83A0AF4B">5.1-2 HadamardCode</a>
 <a href="chap5_mj.html#X8122BA417F705997">5.1-3 ConferenceCode</a>
 <a href="chap5_mj.html#X81B7EE4279398F67">5.1-4 MOLSCode</a>
 <a href="chap5_mj.html#X7D87DD6380B2CE69">5.1-5 RandomCode</a>
 <a href="chap5_mj.html#X816353397F25B62E">5.1-6 NordstromRobinsonCode</a>
 <a href="chap5_mj.html#X7880D34485C60BAF">5.1-7 GreedyCode</a>
 <a href="chap5_mj.html#X7C1B374583AFB923">5.1-8 LexiCode</a>
</div></div>
<div class="ContSect"> <a href="chap5_mj.html#X7A11F29F7BBF45BB">5.2 
Generating Linear Codes
</a>

<div class="ContSSBlock">
 <a href="chap5_mj.html#X83F400A681CFC0D6">5.2-1 GeneratorMatCode</a>
 <a href="chap5_mj.html#X7CDDDFE47A10A008">5.2-2 CheckMatCodeMutable</a>
 <a href="chap5_mj.html#X848D3F7B805DEB66">5.2-3 CheckMatCode</a>
 <a href="chap5_mj.html#X7DECB0A57C798583">5.2-4 HammingCode</a>
 <a href="chap5_mj.html#X801C88D578DA6ACA">5.2-5 ReedMullerCode</a>
 <a href="chap5_mj.html#X851592C7811D3D2A">5.2-6 AlternantCode</a>
 <a href="chap5_mj.html#X7EE808BB7D1E487A">5.2-7 GoppaCode</a>
 <a href="chap5_mj.html#X7F9C0A727EE075B7">5.2-8 GeneralizedSrivastavaCode</a>
 <a href="chap5_mj.html#X7A38EB3178961F3E">5.2-9 SrivastavaCode</a>
 <a href="chap5_mj.html#X87F7CB8B7A8BE624">5.2-10 CordaroWagnerCode</a>
 <a href="chap5_mj.html#X865534267C8E902A">5.2-11 FerreroDesignCode</a>
 <a href="chap5_mj.html#X7BCA10CE8660357F">5.2-12 RandomLinearCode</a>
 <a href="chap5_mj.html#X839CFE4C7A567D4D">5.2-13 OptimalityCode</a>
 <a href="chap5_mj.html#X871508567CB34D96">5.2-14 BestKnownLinearCode</a>
</div></div>
<div class="ContSect"> <a href="chap5_mj.html#X858721967BE44000">5.3 
Gabidulin Codes
</a>

<div class="ContSSBlock">
 <a href="chap5_mj.html#X79BE5D497CB2E59E">5.3-1 GabidulinCode</a>
 <a href="chap5_mj.html#X873950F67D4A9184">5.3-2 EnlargedGabidulinCode</a>
 <a href="chap5_mj.html#X7F5BE77B7F343182">5.3-3 DavydovCode</a>
 <a href="chap5_mj.html#X845B4DBE83288D2D">5.3-4 TombakCode</a>
 <a href="chap5_mj.html#X7D6583347C0D4292">5.3-5 EnlargedTombakCode</a>
</div></div>
<div class="ContSect"> <a href="chap5_mj.html#X81F6E4A785F368B0">5.4 
Golay Codes
</a>

<div class="ContSSBlock">
 <a href="chap5_mj.html#X80ED89C079CD0D09">5.4-1 BinaryGolayCode</a>
 <a href="chap5_mj.html#X84520C7983538806">5.4-2 ExtendedBinaryGolayCode</a>
 <a href="chap5_mj.html#X7E0CCCD7866ADB94">5.4-3 TernaryGolayCode</a>
 <a href="chap5_mj.html#X81088A66816BCAE4">5.4-4 ExtendedTernaryGolayCode</a>
</div></div>
<div class="ContSect"> <a href="chap5_mj.html#X8366CC3685F0BC85">5.5 
Generating Cyclic Codes
</a>

<div class="ContSSBlock">
 <a href="chap5_mj.html#X853D34A5796CEB73">5.5-1 GeneratorPolCode</a>
 <a href="chap5_mj.html#X82440B78845F7F6E">5.5-2 CheckPolCode</a>
 <a href="chap5_mj.html#X818F0E6583E01D4B">5.5-3 RootsCode</a>
 <a href="chap5_mj.html#X7C6BB07C87853C00">5.5-4 BCHCode</a>
 <a href="chap5_mj.html#X838F3CB3872CEF95">5.5-5 ReedSolomonCode</a>
 <a href="chap5_mj.html#X8730B90A862A3B3E">5.5-6 ExtendedReedSolomonCode</a>
 <a href="chap5_mj.html#X825F42F68179D2AB">5.5-7 QRCode</a>
 <a href="chap5_mj.html#X8764ABCF854C695E">5.5-8 QQRCodeNC</a>
 <a href="chap5_mj.html#X7F4C3AD2795A8D7A">5.5-9 QQRCode</a>
 <a href="chap5_mj.html#X7F3B8CC8831DA0E4">5.5-10 FireCode</a>
 <a href="chap5_mj.html#X7BC245E37EB7B23F">5.5-11 WholeSpaceCode</a>
 <a href="chap5_mj.html#X7B4EF2017B2C61AD">5.5-12 NullCode</a>
 <a href="chap5_mj.html#X83C5F8FE7827EAA7">5.5-13 RepetitionCode</a>
 <a href="chap5_mj.html#X82FA9F65854D98A6">5.5-14 CyclicCodes</a>
 <a href="chap5_mj.html#X8263CE4A790D294A">5.5-15 NrCyclicCodes</a>
 <a href="chap5_mj.html#X79826B16785E8BD3">5.5-16 QuasiCyclicCode</a>
 <a href="chap5_mj.html#X7BFEDA52835A601D">5.5-17 CyclicMDSCode</a>
 <a href="chap5_mj.html#X7F40AF3B81C252DC">5.5-18 FourNegacirculantSelfDualCode</a>
 <a href="chap5_mj.html#X87137A257E761291">5.5-19 FourNegacirculantSelfDualCodeNC</a>
</div></div>
<div class="ContSect"> <a href="chap5_mj.html#X850A28C579137220">5.6 
Evaluation Codes
</a>

<div class="ContSSBlock">
 <a href="chap5_mj.html#X78E078567D19D433">5.6-1 EvaluationCode</a>
 <a href="chap5_mj.html#X810AB3DB844FFCE9">5.6-2 GeneralizedReedSolomonCode</a>
 <a href="chap5_mj.html#X85B8699680B9D786">5.6-3 GeneralizedReedMullerCode</a>
 <a href="chap5_mj.html#X7EE68B58872D7E82">5.6-4 ToricPoints</a>
 <a href="chap5_mj.html#X7B24BE418010F596">5.6-5 ToricCode</a>
</div></div>
<div class="ContSect"> <a href="chap5_mj.html#X7AE2B2CD7C647990">5.7 
Algebraic geometric codes
</a>

<div class="ContSSBlock">
 <a href="chap5_mj.html#X802DD9FB79A9ACA7">5.7-1 AffineCurve</a>
 <a href="chap5_mj.html#X857EFE567C05C981">5.7-2 AffinePointsOnCurve</a>
 <a href="chap5_mj.html#X857E36ED814A40B8">5.7-3 GenusCurve</a>
 <a href="chap5_mj.html#X8572A3037DA66F88">5.7-4 GOrbitPoint </a>
 <a href="chap5_mj.html#X79742B7183051D99">5.7-5 DivisorOnAffineCurve</a>
 <a href="chap5_mj.html#X8626E2B57D01F2DC">5.7-6 DivisorAddition </a>
 <a href="chap5_mj.html#X865FE28D828C1EAD">5.7-7 DivisorDegree </a>
 <a href="chap5_mj.html#X789DC358819A8F54">5.7-8 DivisorNegate </a>
 <a href="chap5_mj.html#X8688C0E187B5C7DB">5.7-9 DivisorIsZero </a>
 <a href="chap5_mj.html#X816A07997D9A7075">5.7-10 DivisorsEqual </a>
 <a href="chap5_mj.html#X857B89847A649A26">5.7-11 DivisorGCD </a>
 <a href="chap5_mj.html#X82231CF08073695F">5.7-12 DivisorLCM </a>
 <a href="chap5_mj.html#X79C878697F99A10F">5.7-13 RiemannRochSpaceBasisFunctionP1 </a>
 <a href="chap5_mj.html#X856DDA207EDDF256">5.7-14 DivisorOfRationalFunctionP1 </a>
 <a href="chap5_mj.html#X878970A17E580224">5.7-15 RiemannRochSpaceBasisP1 </a>
 <a href="chap5_mj.html#X807C52E67A440DEB">5.7-16 MoebiusTransformation </a>
 <a href="chap5_mj.html#X85A0419580ED0391">5.7-17 ActionMoebiusTransformationOnFunction </a>
 <a href="chap5_mj.html#X7E48F9C67E7FB7B5">5.7-18 ActionMoebiusTransformationOnDivisorP1 </a>
 <a href="chap5_mj.html#X79FD980E7B24DB9C">5.7-19 IsActionMoebiusTransformationOnDivisorDefinedP1 </a>
 <a href="chap5_mj.html#X823386037F450B0E">5.7-20 DivisorAutomorphismGroupP1 </a>
 <a href="chap5_mj.html#X80EDF3D682E7EF3F">5.7-21 MatrixRepresentationOnRiemannRochSpaceP1 </a>
 <a href="chap5_mj.html#X8777388C7885E335">5.7-22 GoppaCodeClassical</a>
 <a href="chap5_mj.html#X8422A310854C09B0">5.7-23 EvaluationBivariateCode</a>
 <a href="chap5_mj.html#X7B6C2BED8319C811">5.7-24 EvaluationBivariateCodeNC</a>
 <a href="chap5_mj.html#X842E227E8785168E">5.7-25 OnePointAGCode</a>
</div></div>
<div class="ContSect"> <a href="chap5_mj.html#X84F3673D7BBF5956">5.8 
Low-Density Parity-Check Codes
</a>

<div class="ContSSBlock">
 <a href="chap5_mj.html#X8020A9357AD0BA92">5.8-1 QCLDPCCodeFromGroup</a>
</div></div>
</div>

<h3>5 Generating Codes</h3>

In this chapter we describe functions for generating codes.

Section <a href="chap5_mj.html#X86A92CB184CBD3C7">5.1</a> describes functions for generating unrestricted codes.

Section <a href="chap5_mj.html#X7A11F29F7BBF45BB">5.2</a> describes functions for generating linear codes.

Section <a href="chap5_mj.html#X858721967BE44000">5.3</a> describes functions for constructing certain covering codes, such as the Gabidulin codes.

Section <a href="chap5_mj.html#X81F6E4A785F368B0">5.4</a> describes functions for constructing the Golay codes.

Section <a href="chap5_mj.html#X8366CC3685F0BC85">5.5</a> describes functions for generating cyclic codes.

Section <a href="chap5_mj.html#X850A28C579137220">5.6</a> describes functions for generating codes as the image of an evaluation map applied to a space of functions. For example, generalized Reed-Solomon codes and toric codes are described there.

Section <a href="chap5_mj.html#X7AE2B2CD7C647990">5.7</a> describes functions for generating algebraic geometry codes.

Section <a href="chap5_mj.html#X84F3673D7BBF5956">5.8</a> describes functions for constructing low-density parity-check (LDPC) codes.

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

<h4>5.1 
Generating Unrestricted Codes
</h4>

In this section we start with functions that creating code from user defined matrices or special matrices (see <code class="func">ElementsCode</code> (<a href="chap5_mj.html#X81AACBDD86E89D7D">5.1-1</a>), <code class="func">HadamardCode</code> (<a href="chap5_mj.html#X86755AAC83A0AF4B">5.1-2</a>), <code class="func">ConferenceCode</code> (<a href="chap5_mj.html#X8122BA417F705997">5.1-3</a>) and <code class="func">MOLSCode</code> (<a href="chap5_mj.html#X81B7EE4279398F67">5.1-4</a>)). These codes are unrestricted codes; they may later be discovered to be linear or cyclic.

The next functions generate random codes (see <code class="func">RandomCode</code> (<a href="chap5_mj.html#X7D87DD6380B2CE69">5.1-5</a>)) and the Nordstrom-Robinson code (see <code class="func">NordstromRobinsonCode</code> (<a href="chap5_mj.html#X816353397F25B62E">5.1-6</a>)), respectively.

Finally, we describe two functions for generating Greedy codes. These are codes that constructed by gathering codewords from a space (see <code class="func">GreedyCode</code> (<a href="chap5_mj.html#X7880D34485C60BAF">5.1-7</a>) and <code class="func">LexiCode</code> (<a href="chap5_mj.html#X7C1B374583AFB923">5.1-8</a>)).

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

<h5>5.1-1 ElementsCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ElementsCode</code>( <var class="Arg">L</var>[, <var class="Arg">name</var>], <var class="Arg">F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">ElementsCode</code> creates an unrestricted code of the list of elements <var class="Arg">L</var>, in the field <var class="Arg">F</var>. <var class="Arg">L</var> must be a list of vectors, strings, polynomials or codewords. <var class="Arg">name</var> can contain a short description of the code.

If <var class="Arg">L</var> contains a codeword more than once, it is removed from the list and a GAP set is returned.

<div class="example"><pre>
gap> M := Z(3)^0 * [ [1, 0, 1, 1], [2, 2, 0, 0], [0, 1, 2, 2] ];;
gap> C := ElementsCode( M, "example code", GF(3) );
a (4,3,1..4)2 example code over GF(3)
gap> MinimumDistance( C );
4
gap> AsSSortedList( C );
[ [ 0 1 2 2 ], [ 1 0 1 1 ], [ 2 2 0 0 ] ]
</pre></div>

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

<h5>5.1-2 HadamardCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ HadamardCode</code>( <var class="Arg">H</var>[, <var class="Arg">t</var>] )</td><td class="tdright">( function )</td></tr></table></div>
The four forms this command can take are <code class="code">HadamardCode(H,t)</code>, <code class="code">HadamardCode(H)</code>, <code class="code">HadamardCode(n,t)</code>, and <code class="code">HadamardCode(n)</code>.

In the case when the arguments <var class="Arg">H</var> and <var class="Arg">t</var> are both given, <code class="code">HadamardCode</code> returns a Hadamard code of the \(t^{th}\) kind from the Hadamard matrix <var class="Arg">H</var> In case only <var class="Arg">H</var> is given, \(t = 3\) is used.

By definition, a Hadamard matrix is a square matrix <var class="Arg">H</var> with \(H\cdot H^T = -n\cdot I_n\), where \(n\) is the size of <var class="Arg">H</var>. The entries of <var class="Arg">H</var> are either 1 or -1.

The matrix <var class="Arg">H</var> is first transformed into a binary matrix \(A_n\) by replacing the \(1\)'s by \(0\)'s and the \(-1\)'s by \(1\)s).

The Hadamard matrix of the first kind (\(t=1\)) is created by using the rows of \(A_n\) as elements, after deleting the first column. This is a \((n-1, n, n/2)\) code. We use this code for creating the Hadamard code of the second kind (\(t=2\)), by adding all the complements of the already existing codewords. This results in a \((n-1, 2n, n/2 -1)\) code. The third kind (\(t=3\)) is created by using the rows of \(A_n\) (without cutting a column) and their complements as elements. This way, we have an \((n, 2n, n/2)\)-code. The returned code is generally an unrestricted code, but for \(n = 2^r\), the code is linear.

The command <code class="code">HadamardCode(n,t)</code> returns a Hadamard code with parameter <var class="Arg">n</var> of the \(t^{th}\) kind. For the command <code class="code">HadamardCode(n)</code>, \(t=3\) is used.

When called in these forms, <code class="code">HadamardCode</code> first creates a Hadamard matrix (see <code class="func">HadamardMat</code> (<a href="chap7_mj.html#X8014A1F181ECD8AA">7.3-4</a>)), of size <var class="Arg">n</var> and then follows the same procedure as described above. Therefore the same restrictions with respect to <var class="Arg">n</var> as for Hadamard matrices hold.

<div class="example"><pre>
gap> H4 := [[1,1,1,1],[1,-1,1,-1],[1,1,-1,-1],[1,-1,-1,1]];;
gap> HadamardCode( H4, 1 );
a (3,4,2)1 Hadamard code of order 4 over GF(2)
gap> HadamardCode( H4, 2 );
a (3,8,1)0 Hadamard code of order 4 over GF(2)
gap> HadamardCode( H4 );
a (4,8,2)1 Hadamard code of order 4 over GF(2)
gap> H4 := [[1,1,1,1],[1,-1,1,-1],[1,1,-1,-1],[1,-1,-1,1]];;
gap> C := HadamardCode( 4 );
a (4,8,2)1 Hadamard code of order 4 over GF(2)
gap> C = HadamardCode( H4 );
true
</pre></div>

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

<h5>5.1-3 ConferenceCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ConferenceCode</code>( <var class="Arg">H</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">ConferenceCode</code> returns a code of length \(n-1\) constructed from a symmetric 'conference matrix' <var class="Arg">H</var>. A conference matrix <var class="Arg">H</var> is a symmetric matrix of order \(n\), which satisfies \(H\cdot H^T = ((n-1)\cdot I\), with \(n \equiv 2 \pmod 4\). The rows of \(\frac{1}{2}(H+I+J)\), \(\frac{1}{2}(-H+I+J)\), plus the zero and all-ones vectors form the elements of a binary non-linear \((n-1, 2n, (n-2)/2)\) code.

GUAVA constructs a symmetric conference matrix of order \(n+1\) (\(n\equiv 1 \pmod 4\)) and uses the rows of that matrix, plus the zero and all-ones vectors, to construct a binary non-linear \((n, 2(n+1), (n-1)/2)\)-code.

<div class="example"><pre>
gap> H6 := [[0,1,1,1,1,1],[1,0,1,-1,-1,1],[1,1,0,1,-1,-1],
> [1,-1,1,0,1,-1],[1,-1,-1,1,0,1],[1,1,-1,-1,1,0]];;
gap> C1 := ConferenceCode( H6 );
a (5,12,2)1..4 conference code over GF(2)
gap> IsLinearCode( C1 );
false
gap> C2 := ConferenceCode( 5 );
a (5,12,2)1..4 conference code over GF(2)
gap> AsSSortedList( C2 );
[ [ 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 ] ]
</pre></div>

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

<h5>5.1-4 MOLSCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MOLSCode</code>( [<var class="Arg">n</var>, ]<var class="Arg">q</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">MOLSCode</code> returns an \((n, q^2, n-1)\) code over \(GF(q)\). The code is created from \(n-2\) 'Mutually Orthogonal Latin Squares' (MOLS) of size \(q \times q\). The default for <var class="Arg">n</var> is \(4\). GUAVA can construct a MOLS code for \(n-2 \leq q\). Here <var class="Arg">q</var> must be a prime power, \(q > 2\). If there are no \(n-2\) MOLS, an error is signalled.

Since each of the \(n-2\) MOLS is a \(q\times q\) matrix, we can create a code of size \(q^2\) by listing in each code element the entries that are in the same position in each of the MOLS. We precede each of these lists with the two coordinates that specify this position, making the word length become \(n\).

The MOLS codes are MDS codes (see <code class="func">IsMDSCode</code> (<a href="chap4_mj.html#X789380D28018EC3F">4.3-7</a>)).

<div class="example"><pre>
gap> C1 := MOLSCode( 6, 5 );
a (6,25,5)3..4 code generated by 4 MOLS of order 5 over GF(5)
gap> mols := List( [1 .. WordLength(C1) - 2 ], function( nr )
> local ls, el;
> ls := NullMat( Size(LeftActingDomain(C1)), Size(LeftActingDomain(C1)) );
> for el in VectorCodeword( AsSSortedList( C1 ) ) do
> ls[IntFFE(el[1])+1][IntFFE(el[2])+1] := el[nr + 2];
> od;
> return ls;
> end );;
gap> AreMOLS( mols );
true
gap> C2 := MOLSCode( 11 );
a (4,121,3)2 code generated by 2 MOLS of order 11 over GF(11)
</pre></div>

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

<h5>5.1-5 RandomCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RandomCode</code>( <var class="Arg">n</var>, <var class="Arg">M</var>, <var class="Arg">F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">RandomCode</code> returns a random unrestricted code of size <var class="Arg">M</var> with word length <var class="Arg">n</var> over <var class="Arg">F</var>. <var class="Arg">M</var> must be less than or equal to the number of elements in the space \(GF(q)^n\).

The function <code class="code">RandomLinearCode</code> returns a random linear code (see <code class="func">RandomLinearCode</code> (<a href="chap5_mj.html#X7BCA10CE8660357F">5.2-12</a>)).

<div class="example"><pre>
gap> C1 := RandomCode( 6, 10, GF(8) );
a (6,10,1..6)4..6 random unrestricted code over GF(8)
gap> MinimumDistance(C1);
2
gap> C2 := RandomCode( 6, 10, GF(8) );
a (6,10,1..6)4..6 random unrestricted code over GF(8)
gap> C1 = C2;
false
</pre></div>

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

<h5>5.1-6 NordstromRobinsonCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NordstromRobinsonCode</code>( )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">NordstromRobinsonCode</code> returns a Nordstrom-Robinson code, the best code with word length \(n=16\) and minimum distance \(d=6\) over \(GF(2)\). This is a non-linear \((16, 256, 6)\) code.

<div class="example"><pre>
gap> C := NordstromRobinsonCode();
a (16,256,6)4 Nordstrom-Robinson code over GF(2)
gap> OptimalityCode( C );
0
</pre></div>

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

<h5>5.1-7 GreedyCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GreedyCode</code>( <var class="Arg">L</var>, <var class="Arg">d</var>, <var class="Arg">F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">GreedyCode</code> returns a Greedy code with design distance <var class="Arg">d</var> over the finite field <var class="Arg">F</var>. The code is constructed using the greedy algorithm on the list of vectors <var class="Arg">L</var>. (The greedy algorithm checks each vector in <var class="Arg">L</var> and adds it to the code if its distance to the current code is greater than or equal to <var class="Arg">d</var>. It is obvious that the resulting code has a minimum distance of at least <var class="Arg">d</var>.

Greedy codes are often linear codes.

The function <code class="code">LexiCode</code> creates a greedy code from a basis instead of an enumerated list (see <code class="func">LexiCode</code> (<a href="chap5_mj.html#X7C1B374583AFB923">5.1-8</a>)).

<div class="example"><pre>
gap> C1 := GreedyCode( Tuples( AsSSortedList( GF(2) ), 5 ), 3, GF(2) );
a (5,4,3..5)2 Greedy code, user defined basis over GF(2)
gap> C2 := GreedyCode( Permuted( Tuples( AsSSortedList( GF(2) ), 5 ),
> (1,4) ), 3, GF(2) );
a (5,4,3..5)2 Greedy code, user defined basis over GF(2)
gap> C1 = C2;
false
</pre></div>

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

<h5>5.1-8 LexiCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LexiCode</code>( <var class="Arg">n</var>, <var class="Arg">d</var>, <var class="Arg">F</var> )</td><td class="tdright">( function )</td></tr></table></div>
In this format, <code class="code">Lexicode</code> returns a lexicode with word length <var class="Arg">n</var>, design distance <var class="Arg">d</var> over <var class="Arg">F</var>. The code is constructed using the greedy algorithm on the lexicographically ordered list of all vectors of length <var class="Arg">n</var> over <var class="Arg">F</var>. Every time a vector is found that has a distance to the current code of at least <var class="Arg">d</var>, it is added to the code. This results, obviously, in a code with minimum distance greater than or equal to <var class="Arg">d</var>.

Another syntax which one can use is <code class="code">LexiCode( B, d, F )</code>. When called in this format, <code class="code">LexiCode</code> uses the basis <var class="Arg">B</var> instead of the standard basis. <var class="Arg">B</var> is a matrix of vectors over <var class="Arg">F</var>. The code is constructed using the greedy algorithm on the list of vectors spanned by <var class="Arg">B</var>, ordered lexicographically with respect to <var class="Arg">B</var>.

Note that binary lexicodes are always linear.

<div class="example"><pre>
gap> C := LexiCode( 4, 3, GF(5) );
a (4,17,3..4)2..4 lexicode over GF(5)
gap> B := [ [Z(2)^0, 0*Z(2), 0*Z(2)], [Z(2)^0, Z(2)^0, 0*Z(2)] ];;
gap> C := LexiCode( B, 2, GF(2) );
a linear [3,1,2]1..2 lexicode over GF(2)
</pre></div>

The function <code class="code">GreedyCode</code> creates a greedy code that is not restricted to a lexicographical order (see <code class="func">GreedyCode</code> (<a href="chap5_mj.html#X7880D34485C60BAF">5.1-7</a>)).

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

<h4>5.2 
Generating Linear Codes
</h4>

In this section we describe functions for constructing linear codes. A linear code always has a generator or check matrix.

The first two functions generate linear codes from the generator matrix (<code class="func">GeneratorMatCode</code> (<a href="chap5_mj.html#X83F400A681CFC0D6">5.2-1</a>)) or check matrix (<code class="func">CheckMatCode</code> (<a href="chap5_mj.html#X848D3F7B805DEB66">5.2-3</a>)). All linear codes can be constructed with these functions.

The next functions we describe generate some well-known codes, like Hamming codes (<code class="func">HammingCode</code> (<a href="chap5_mj.html#X7DECB0A57C798583">5.2-4</a>)), Reed-Muller codes (<code class="func">ReedMullerCode</code> (<a href="chap5_mj.html#X801C88D578DA6ACA">5.2-5</a>)) and the extended Golay codes (<code class="func">ExtendedBinaryGolayCode</code> (<a href="chap5_mj.html#X84520C7983538806">5.4-2</a>) and <code class="func">ExtendedTernaryGolayCode</code> (<a href="chap5_mj.html#X81088A66816BCAE4">5.4-4</a>)).

A large and powerful family of codes are alternant codes. They are obtained by a small modification of the parity check matrix of a BCH code (see <code class="func">AlternantCode</code> (<a href="chap5_mj.html#X851592C7811D3D2A">5.2-6</a>), <code class="func">GoppaCode</code> (<a href="chap5_mj.html#X7EE808BB7D1E487A">5.2-7</a>), <code class="func">GeneralizedSrivastavaCode</code> (<a href="chap5_mj.html#X7F9C0A727EE075B7">5.2-8</a>) and <code class="func">SrivastavaCode</code> (<a href="chap5_mj.html#X7A38EB3178961F3E">5.2-9</a>)).

Finally, we describe a function for generating random linear codes (see <code class="func">RandomLinearCode</code> (<a href="chap5_mj.html#X7BCA10CE8660357F">5.2-12</a>)).

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

<h5>5.2-1 GeneratorMatCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GeneratorMatCode</code>( <var class="Arg">G</var>[, <var class="Arg">name</var>], <var class="Arg">F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">GeneratorMatCode</code> returns a linear code with generator matrix <var class="Arg">G</var>. <var class="Arg">G</var> must be a matrix over finite field <var class="Arg">F</var>. <var class="Arg">name</var> can contain a short description of the code. The generator matrix is the basis of the elements of the code. The resulting code has word length \(n\), dimension \(k\) if <var class="Arg">G</var> is a \(k \times n\)-matrix. If \(GF(q)\) is the field of the code, the size of the code will be \(q^k\).

If the generator matrix does not have full row rank, the linearly dependent rows are removed. This is done by the GAP function <code class="code">BaseMat</code> and results in an equal code. The generator matrix can be retrieved with the function <code class="code">GeneratorMat</code> (see <code class="func">GeneratorMat</code> (<a href="chap4_mj.html#X817224657C9829C4">4.7-1</a>)).

<div class="example"><pre>
gap> G := Z(3)^0 * [[1,0,1,2,0],[0,1,2,1,1],[0,0,1,2,1]];;
gap> C1 := GeneratorMatCode( G, GF(3) );
a linear [5,3,1..2]1..2 code defined by generator matrix over GF(3)
gap> C2 := GeneratorMatCode( IdentityMat( 5, GF(2) ), GF(2) );
a linear [5,5,1]0 code defined by generator matrix over GF(2)
gap> GeneratorMatCode( List( AsSSortedList( NordstromRobinsonCode() ),
> x -> VectorCodeword( x ) ), GF( 2 ) ); # This is the smallest linear code that contains the N-R code 
a linear [16,11,1..4]2 code defined by generator matrix over GF(2)
</pre></div>

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

<h5>5.2-2 CheckMatCodeMutable</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CheckMatCodeMutable</code>( <var class="Arg">H</var>[, <var class="Arg">name</var>], <var class="Arg">F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">CheckMatCodeMutable</code> is the same as <code class="code">CheckMatCode</code> except that the check matrix and generator matrix are mutable.

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

<h5>5.2-3 CheckMatCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CheckMatCode</code>( <var class="Arg">H</var>[, <var class="Arg">name</var>], <var class="Arg">F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">CheckMatCode</code> returns a linear code with check matrix <var class="Arg">H</var>. <var class="Arg">H</var> must be a matrix over Galois field <var class="Arg">F</var>. <var class="Arg">[name.</var> can contain a short description of the code. The parity check matrix is the transposed of the nullmatrix of the generator matrix of the code. Therefore, \(c\cdot H^T = 0\) where \(c\) is an element of the code. If <var class="Arg">H</var> is a \(r\times n\)-matrix, the code has word length \(n\), redundancy \(r\) and dimension \(n-r\).

If the check matrix does not have full row rank, the linearly dependent rows are removed. This is done by the GAP function <code class="code">BaseMat</code>. and results in an equal code. The check matrix can be retrieved with the function <code class="code">CheckMat</code> (see <code class="func">CheckMat</code> (<a href="chap4_mj.html#X85D4B26E7FB38D57">4.7-2</a>)).

<div class="example"><pre>
gap> G := Z(3)^0 * [[1,0,1,2,0],[0,1,2,1,1],[0,0,1,2,1]];;
gap> C1 := CheckMatCode( G, GF(3) );
a linear [5,2,1..2]2..3 code defined by check matrix over GF(3)
gap> CheckMat(C1);
[ [ Z(3)^0, 0*Z(3), Z(3)^0, Z(3), 0*Z(3) ],
 [ 0*Z(3), Z(3)^0, Z(3), Z(3)^0, Z(3)^0 ],
 [ 0*Z(3), 0*Z(3), Z(3)^0, Z(3), Z(3)^0 ] ]
gap> C2 := CheckMatCode( IdentityMat( 5, GF(2) ), GF(2) );
a cyclic [5,0,5]5 code defined by check matrix over GF(2)
</pre></div>

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

<h5>5.2-4 HammingCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ HammingCode</code>( <var class="Arg">r</var>, <var class="Arg">F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">HammingCode</code> returns a Hamming code with redundancy <var class="Arg">r</var> over <var class="Arg">F</var>. A Hamming code is a single-error-correcting code. The parity check matrix of a Hamming code has all nonzero vectors of length <var class="Arg">r</var> in its columns, except for a multiplication factor. The decoding algorithm of the Hamming code (see <code class="func">Decode</code> (<a href="chap4_mj.html#X7A42FF7D87FC34AC">4.10-1</a>)) makes use of this property.

If \(q\) is the size of its field <var class="Arg">F</var>, the returned Hamming code is a linear \([(q^r-1)/(q-1), (q^r-1)/(q-1) - r, 3]\) code.

<div class="example"><pre>
gap> C1 := HammingCode( 4, GF(2) );
a linear [15,11,3]1 Hamming (4,2) code over GF(2)
gap> C2 := HammingCode( 3, GF(9) );
a linear [91,88,3]1 Hamming (3,9) code over GF(9)
</pre></div>

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

<h5>5.2-5 ReedMullerCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ReedMullerCode</code>( <var class="Arg">r</var>, <var class="Arg">k</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">ReedMullerCode</code> returns a binary 'Reed-Muller code' <var class="Arg">R(r, k)</var> with dimension <var class="Arg">k</var> and order <var class="Arg">r</var>. This is a code with length \(2^k\) and minimum distance \(2^{k-r}\) (see for example, section 1.10 in <a href="chapBib_mj.html#biBHP03">[HP03]</a>). By definition, the \(r^{th}\) order binary Reed-Muller code of length \(n=2^m\), for \(0 \leq r \leq m\), is the set of all vectors \(f\), where \(f\) is a Boolean function which is a polynomial of degree at most \(r\).

<div class="example"><pre>
gap> ReedMullerCode( 1, 3 );
a linear [8,4,4]2 Reed-Muller (1,3) code over GF(2)
</pre></div>

See <code class="func">GeneralizedReedMullerCode</code> (<a href="chap5_mj.html#X85B8699680B9D786">5.6-3</a>) for a more general construction.

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

<h5>5.2-6 AlternantCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AlternantCode</code>( <var class="Arg">r</var>, <var class="Arg">Y</var>[, <var class="Arg">alpha</var>], <var class="Arg">F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">AlternantCode</code> returns an 'alternant code', with parameters <var class="Arg">r</var>, <var class="Arg">Y</var> and <var class="Arg">alpha</var> (optional). <var class="Arg">F</var> denotes the (finite) base field. Here, <var class="Arg">r</var> is the design redundancy of the code. <var class="Arg">Y</var> and <var class="Arg">alpha</var> are both vectors of length <var class="Arg">n</var> from which the parity check matrix is constructed. The check matrix has the form \(H=([a_i^j y_i])\), where \(0 \leq j\leq r-1\), \(1 \leq i\leq n\), and where \([...]\) is as in <code class="func">VerticalConversionFieldMat</code> (<a href="chap7_mj.html#X7B68119F85E9EC6D">7.3-9</a>)). If no <var class="Arg">alpha</var> is specified, the vector \([1, a, a^2, .., a^{n-1}]\) is used, where \(a\) is a primitive element of a Galois field <var class="Arg">F</var>.

<div class="example"><pre>
gap> Y := [ 1, 1, 1, 1, 1, 1, 1];; a := PrimitiveUnityRoot( 2, 7 );;
gap> alpha := List( [0..6], i -> a^i );;
gap> C := AlternantCode( 2, Y, alpha, GF(8) );
a linear [7,3,3..4]3..4 alternant code over GF(8)
</pre></div>

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

<h5>5.2-7 GoppaCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GoppaCode</code>( <var class="Arg">G</var>, <var class="Arg">L</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">GoppaCode</code> returns a Goppa code <var class="Arg">C</var> from Goppa polynomial <var class="Arg">g</var>, having coefficients in a Galois Field \(GF(q)\). <var class="Arg">L</var> must be a list of elements in \(GF(q)\), that are not roots of <var class="Arg">g</var>. The word length of the code is equal to the length of <var class="Arg">L</var>. The parity check matrix has the form \(H=([a_i^j / G(a_i)])_{0 \leq j \leq deg(g)-1,\ a_i \in L}\), where \(a_i\in L\) and \([...]\) is as in <code class="func">VerticalConversionFieldMat</code> (<a href="chap7_mj.html#X7B68119F85E9EC6D">7.3-9</a>), so \(H\) has entries in \(GF(q)\), \(q=p^m\). It is known that \(d(C)\geq deg(g)+1\), with a better bound in the binary case provided \(g\) has no multiple roots. See Huffman and Pless <a href="chapBib_mj.html#biBHP03">[HP03]</a> section 13.2.2, and MacWilliams and Sloane <a href="chapBib_mj.html#biBMS83">[MS83]</a> section 12.3, for more details.

One can also call <code class="code">GoppaCode</code> using the syntax <code class="code">GoppaCode(g,n)</code>. When called with parameter <var class="Arg">n</var>, GUAVA constructs a list \(L\) of length <var class="Arg">n</var>, such that no element of <var class="Arg">L</var> is a root of <var class="Arg">g</var>.

This is a special case of an alternant code.

<div class="example"><pre>
gap> x:=Indeterminate(GF(8),"x");
x
gap> L:=Elements(GF(8));
[ 0*Z(2), Z(2)^0, Z(2^3), Z(2^3)^2, Z(2^3)^3, Z(2^3)^4, Z(2^3)^5, Z(2^3)^6 ]
gap> g:=x^2+x+1;
x^2+x+Z(2)^0
gap> C:=GoppaCode(g,L);
a linear [8,2,5]3 classical Goppa code over GF(2)
gap> xx := Indeterminate( GF(2), "xx" );; 
gap> gg := xx^2 + xx + 1;; L := AsSSortedList( GF(8) );;
gap> C1 := GoppaCode( gg, L );
a linear [8,2,5]3 classical Goppa code over GF(2)
gap> y := Indeterminate( GF(2), "y" );; 
gap> h := y^2 + y + 1;;
gap> C2 := GoppaCode( h, 8 );
a linear [8,2,5]3 classical Goppa code over GF(2)
gap> C1=C2;
true
gap> C=C1;
true
</pre></div>

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

<h5>5.2-8 GeneralizedSrivastavaCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GeneralizedSrivastavaCode</code>( <var class="Arg">a</var>, <var class="Arg">w</var>, <var class="Arg">z</var>[, <var class="Arg">t</var>], <var class="Arg">F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">GeneralizedSrivastavaCode</code> returns a generalized Srivastava code with parameters <var class="Arg">a</var>, <var class="Arg">w</var>, <var class="Arg">z</var>, <var class="Arg">t</var>. \(a =\{ a_1, ..., a_n\}\) and \(w =\{ w_1, ..., w_s\}\) are lists of \(n+s\) distinct elements of \(F=GF(q^m)\), \(z\) is a list of length \(n\) of nonzero elements of \(GF(q^m)\). The parameter <var class="Arg">t</var> determines the designed distance: \(d \geq st + 1\). The check matrix of this code is the form

\[
H=([\frac{z_i}{(a_i - w_j)^k}]),
\]

\(1\leq k\leq t\), where \([...]\) is as in <code class="func">VerticalConversionFieldMat</code> (<a href="chap7_mj.html#X7B68119F85E9EC6D">7.3-9</a>). We use this definition of \(H\) to define the code. The default for <var class="Arg">t</var> is 1. The original Srivastava codes (see <code class="func">SrivastavaCode</code> (<a href="chap5_mj.html#X7A38EB3178961F3E">5.2-9</a>)) are a special case \(t=1\), \(z_i=a_i^\mu\), for some \(\mu\).

<div class="example"><pre>
gap> a := Filtered( AsSSortedList( GF(2^6) ), e -> e in GF(2^3) );;
gap> w := [ Z(2^6) ];; z := List( [1..8], e -> 1 );;
gap> C := GeneralizedSrivastavaCode( a, w, z, 1, GF(64) );
a linear [8,2,2..5]3..4 generalized Srivastava code over GF(2)
</pre></div>

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

<h5>5.2-9 SrivastavaCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SrivastavaCode</code>( <var class="Arg">a</var>, <var class="Arg">w</var>[, <var class="Arg">mu</var>], <var class="Arg">F</var> )</td><td class="tdright">( function )</td></tr></table></div>
\(SrivastavaCode\) returns a Srivastava code with parameters <var class="Arg">a</var>, <var class="Arg">w</var> (and optionally <var class="Arg">mu</var>). \(a =\{ a_1, ..., a_n\}\) and \(w =\{ w_1, ..., w_s\}\) are lists of \(n+s\) distinct elements of \(F=GF(q^m)\). The default for <var class="Arg">mu</var> is 1. The Srivastava code is a generalized Srivastava code, in which \(z_i = a_i^{mu}\) for some <var class="Arg">mu</var> and \(t=1\).

J. N. Srivastava introduced this code in 1967, though his work was not published. See Helgert <a href="chapBib_mj.html#biBHe72">[Hel72]</a> for more details on the properties of this code. Related reference: G. Roelofsen, On Goppa and Generalized Srivastava Codes PhD thesis, Dept. Math. and Comp. Sci., Eindhoven Univ. of Technology, the Netherlands, 1982.

<div class="example"><pre>
gap> a := AsSSortedList( GF(11) ){[2..8]};;
gap> w := AsSSortedList( GF(11) ){[9..10]};;
gap> C := SrivastavaCode( a, w, 2, GF(11) );
a linear [7,5,3]2 Srivastava code over GF(11)
gap> IsMDSCode( C ); # Always true if F is a prime field 
true
</pre></div>

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

<h5>5.2-10 CordaroWagnerCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CordaroWagnerCode</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">CordaroWagnerCode</code> returns a binary Cordaro-Wagner code. This is a code of length <var class="Arg">n</var> and dimension \(2\) having the best possible minimum distance \(d\). This code is just a little bit less trivial than <code class="code">RepetitionCode</code> (see <code class="func">RepetitionCode</code> (<a href="chap5_mj.html#X83C5F8FE7827EAA7">5.5-13</a>)).

<div class="example"><pre>
gap> C := CordaroWagnerCode( 11 );
a linear [11,2,7]5 Cordaro-Wagner code over GF(2)
gap> AsSSortedList(C); 
[ [ 0 0 0 0 0 0 0 0 0 0 0 ], [ 0 0 0 0 1 1 1 1 1 1 1 ],
 [ 1 1 1 1 0 0 0 1 1 1 1 ], [ 1 1 1 1 1 1 1 0 0 0 0 ] ]
</pre></div>

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

<h5>5.2-11 FerreroDesignCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FerreroDesignCode</code>( <var class="Arg">P</var>, <var class="Arg">m</var> )</td><td class="tdright">( function )</td></tr></table></div>
Requires the GAP package SONATA

A group \(K\) together with a group of automorphism \(H\) of \(K\) such that the semidirect product \(KH\) is a Frobenius group with complement \(H\) is called a Ferrero pair \((K, H)\) in SONATA. Take a Frobenius \((G,+)\) group with kernel \(K\) and complement \(H\). Consider the design \(D\) with point set \(K\) and block set \(\{ a^H + b\ |\ a, b \in K, a \not= 0 \}\). Here \(a^H\) denotes the orbit of a under conjugation by elements of \(H\). Every planar near-ring design of type "*" can be obtained in this way from groups. These designs (from a Frobenius kernel of order \(v\) and a Frobenius complement of order \(k\)) have \(v(v-1)/k\) distinct blocks and they are all of size \(k\). Moreover each of the \(v\) points occurs in exactly \(v-1\) distinct blocks. Hence the rows and the columns of the incidence matrix \(M\) of the design are always of constant weight.

<code class="code">FerreroDesignCode</code> constructs binary linear code arising from the incdence matrix of a design associated to a "Ferrero pair" arising from a fixed-point-free (fpf) automorphism groups and Frobenius group.

INPUT: \(P\) is a list of prime powers describing an abelian group \(G\). \(m > 0\) is an integer such that \(G\) admits a cyclic fpf automorphism group of size \(m\). This means that for all \(q = p^k \in P\), OrderMod(\(p\), \(m\)) must divide \(q\) (see the SONATA documentation for <code class="code">FpfAutomorphismGroupsCyclic</code>).

OUTPUT: The binary linear code whose generator matrix is the incidence matrix of a design associated to a "Ferrero pair" arising from the fixed-point-free (fpf) automorphism group of \(G\). The pair \((H,K)\) is called a Ferraro pair and the semidirect product \(KH\) is a Frobenius group with complement \(H\).

AUTHORS: Peter Mayr and David Joyner

<div class="example"><pre>
gap> G:=AbelianGroup([5,5] );
<pc group of size 25 with 2 generators>
gap> FpfAutomorphismGroupsMaxSize( G );
[ 24, 2 ]
gap> L:=FpfAutomorphismGroupsCyclic( [5,5], 3 );
[ [ [ f1, f2 ] -> [ f1*f2^2, f1*f2^3 ] ],
 <pc group of size 25 with 2 generators> ]
gap> D := DesignFromFerreroPair( L[2], Group(L[1][1]), "*" );
<a 2 - ( 25, 3, 2 ) nearring generated design>
gap> M:=IncidenceMat( D );; Length(M); Length(TransposedMat(M));
25
200
gap> C1:=GeneratorMatCode(M*Z(2),GF(2));
a linear [200,25,1..24]62..100 code defined by generator matrix over GF(2)
gap> MinimumDistance(C1);
24
gap> C2:=FerreroDesignCode( [5,5],3);
a linear [200,25,1..24]62..100 code defined by generator matrix over GF(2)
gap> C1=C2;
true
</pre></div>

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

<h5>5.2-12 RandomLinearCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RandomLinearCode</code>( <var class="Arg">n</var>, <var class="Arg">k</var>, <var class="Arg">F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">RandomLinearCode</code> returns a random linear code with word length <var class="Arg">n</var>, dimension <var class="Arg">k</var> over field <var class="Arg">F</var>. The method used is to first construct a \(k\times n\) matrix of the block form \((I,A)\), where \(I\) is a \(k\times k\) identity matrix and \(A\) is a \(k\times (n-k)\) matrix constructed using <code class="code">Random(F)</code> repeatedly. Then the columns are permuted using a randomly selected element of <code class="code">SymmetricGroup(n)</code>.

To create a random unrestricted code, use <code class="code">RandomCode</code> (see <code class="func">RandomCode</code> (<a href="chap5_mj.html#X7D87DD6380B2CE69">5.1-5</a>)).

<div class="example"><pre>
gap> C := RandomLinearCode( 15, 4, GF(3) );
a [15,4,?] randomly generated code over GF(3)
gap> Display(C);
a linear [15,4,1..6]6..10 random linear code over GF(3)
</pre></div>

The method GUAVA chooses to output the result of a <code class="code">RandomLinearCode</code> command is different than other codes. For example, the bounds on the minimum distance is not displayed. Howeer, you can use the <code class="code">Display</code> command to print this information. This new display method was added in version 1.9 to speed up the command (if \(n\) is about 80 and \(k\) about 40, for example, the time it took to look up and/or calculate the bounds on the minimum distance was too long).

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

<h5>5.2-13 OptimalityCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OptimalityCode</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">OptimalityCode</code> returns the difference between the smallest known upper bound and the actual size of the code. Note that the value of the function <code class="code">UpperBound</code> is not always equal to the actual upper bound \(A(n,d)\) thus the result may not be equal to \(0\) even if the code is optimal!

<code class="code">OptimalityLinearCode</code> is similar but applies only to linear codes.

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

<h5>5.2-14 BestKnownLinearCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BestKnownLinearCode</code>( <var class="Arg">n</var>, <var class="Arg">k</var>, <var class="Arg">F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">BestKnownLinearCode</code> returns the best known (as of 11 May 2006) linear code of length <var class="Arg">n</var>, dimension <var class="Arg">k</var> over field <var class="Arg">F</var>. The function uses the tables described in section <code class="func">BoundsMinimumDistance</code> (<a href="chap7_mj.html#X7B3858B27A9E509A">7.1-13</a>) to construct this code.

This command can also be called using the syntax <code class="code">BestKnownLinearCode( rec )</code>, where <var class="Arg">rec</var> must be a record containing the fields `lowerBound', `upperBound' and `construction'. It uses the information in this field to construct a code. This form is meant to be used together with the function <code class="code">BoundsMinimumDistance</code> (see <code class="func">BoundsMinimumDistance</code> (<a href="chap7_mj.html#X7B3858B27A9E509A">7.1-13</a>)), if the bounds are already calculated.

<div class="example"><pre>
gap> C1 := BestKnownLinearCode( 23, 12, GF(2) );
a linear [23,12,7]3 punctured code
gap> C1 = BinaryGolayCode(); # it's constructed differently
false
gap> C1 := BestKnownLinearCode( 23, 12, GF(2) );
a linear [23,12,7]3 punctured code
gap> G1 := MutableCopyMat(GeneratorMat(C1));;
gap> PutStandardForm(G1);
()
gap> Display(G1);
1 . . . . . . . . . . . 1 . 1 . 1 1 1 . . . 1
. 1 . . . . . . . . . . 1 1 1 1 1 . . 1 . . .
. . 1 . . . . . . . . . 1 1 . 1 . . 1 . 1 . 1
. . . 1 . . . . . . . . 1 1 . . . 1 1 1 . 1 .
. . . . 1 . . . . . . . 1 1 . . 1 1 . 1 1 . 1
. . . . . 1 . . . . . . . 1 1 . . 1 1 . 1 1 1
. . . . . . 1 . . . . . . . 1 1 . . 1 1 . 1 1
. . . . . . . 1 . . . . 1 . 1 1 . 1 1 1 1 . .
. . . . . . . . 1 . . . . 1 . 1 1 . 1 1 1 1 .
. . . . . . . . . 1 . . . . 1 . 1 1 . 1 1 1 .
. . . . . . . . . . 1 . 1 . 1 1 1 . . . 1 1 1
. . . . . . . . . . . 1 . 1 . 1 1 1 . . . 1 1
gap> C2 := BinaryGolayCode();
a cyclic [23,12,7]3 binary Golay code over GF(2)
gap> G2 := MutableCopyMat(GeneratorMat(C2));;
gap> PutStandardForm(G2);
()
gap> Display(G2); ## Despite their generator matrices are different, they are equivalent codes, see below.
1 . . . . . . . . . . . 1 . 1 . 1 1 1 . . . 1
. 1 . . . . . . . . . . 1 1 1 1 1 . . 1 . . 1
. . 1 . . . . . . . . . 1 1 . 1 . . 1 . 1 . 1
. . . 1 . . . . . . . . 1 1 . . . 1 1 1 . 1 1
. . . . 1 . . . . . . . 1 1 . . 1 1 . 1 1 . .
. . . . . 1 . . . . . . . 1 1 . . 1 1 . 1 1 .
. . . . . . 1 . . . . . . . 1 1 . . 1 1 . 1 1
. . . . . . . 1 . . . . 1 . 1 1 . 1 1 1 1 . .
. . . . . . . . 1 . . . . 1 . 1 1 . 1 1 1 1 .
. . . . . . . . . 1 . . . . 1 . 1 1 . 1 1 1 1
. . . . . . . . . . 1 . 1 . 1 1 1 . . . 1 1 .
. . . . . . . . . . . 1 . 1 . 1 1 1 . . . 1 1
gap> IsEquivalent(C1,C2);
true
gap> CodeIsomorphism(C1,C2);
(4,14,6,12,5)(7,17,18,11,19)(8,22,13,21,16)(10,23,15,20)
gap> Display( BestKnownLinearCode( 81, 77, GF(4) ) );
a linear [81,77,3]2..3 shortened code of
a linear [85,81,3]1 Hamming (4,4) code over GF(4)
gap> C:=BestKnownLinearCode(174,72);
a linear [174,72,31..36]26..87 code defined by generator matrix over GF(2)
gap> bounds := BoundsMinimumDistance( 81, 77, GF(4) );
rec(
 construction :=
 [ <Operation "ShortenedCode">,
 [ [ <Operation "HammingCode">, [ 4, 4 ] ], [ 1, 2, 3, 4 ] ] ], k := 77,
 lowerBound := 3,
 lowerBoundExplanation := [ "Lb(81,77)=3, by shortening of:",
 "Lb(85,81)=3, reference: Ham" ], n := 81, q := 4,
 references :=
 rec(
 Ham := [ "%T this reference is unknown, for more info",
 "%T contact A.E. Brouwer (aeb@cwi.nl)" ],
 cap := [ "%T this reference is unknown, for more info",
 "%T contact A.E. Brouwer (aeb@cwi.nl)" ] ), upperBound := 3,
 upperBoundExplanation := [ "Ub(81,77)=3, by considering shortening to:",
 "Ub(18,14)=3, reference: cap" ] )
gap> C := BestKnownLinearCode( bounds );
a linear [81,77,3]2..3 shortened code
gap> C = BestKnownLinearCode(81, 77, GF(4) );
true
</pre></div>

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

<h4>5.3 
Gabidulin Codes
</h4>

These five binary, linear codes are derived from an article by Gabidulin, Davydov and Tombak <a href="chapBib_mj.html#biBGDT91">[GDT91]</a>. All these codes are defined by check matrices. Exact definitions can be found in the article. The Gabidulin code, the enlarged Gabidulin code, the Davydov code, the Tombak code, and the enlarged Tombak code, correspond with theorem 1, 2, 3, 4, and 5, respectively in the article.

Like the Hamming codes, these codes have fixed minimum distance and covering radius, but can be arbitrarily long.

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

<h5>5.3-1 GabidulinCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GabidulinCode</code>( <var class="Arg">m</var>, <var class="Arg">w1</var>, <var class="Arg">w2</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">GabidulinCode</code> yields a code of length \(5\) . \(2^{m-2}-1\), redundancy \(2m-1\), minimum distance \(3\) and covering radius \(2\). <var class="Arg">w1</var> and <var class="Arg">w2</var> should be elements of \(GF(2^{m-2})\).

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

<h5>5.3-2 EnlargedGabidulinCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EnlargedGabidulinCode</code>( <var class="Arg">m</var>, <var class="Arg">w1</var>, <var class="Arg">w2</var>, <var class="Arg">e</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">EnlargedGabidulinCode</code> yields a code of length \(7\). \(2^{m-2}-2\), redundancy \(2m\), minimum distance \(3\) and covering radius \(2\). <var class="Arg">w1</var> and <var class="Arg">w2</var> are elements of \(GF(2^{m-2})\). <var class="Arg">e</var> is an element of \(GF(2^m)\).

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

<h5>5.3-3 DavydovCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DavydovCode</code>( <var class="Arg">r</var>, <var class="Arg">v</var>, <var class="Arg">ei</var>, <var class="Arg">ej</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">DavydovCode</code> yields a code of length \(2^v + 2^{r-v} - 3\), redundancy <var class="Arg">r</var>, minimum distance \(4\) and covering radius \(2\). <var class="Arg">v</var> is an integer between \(2\) and \(r-2\). <var class="Arg">ei</var> and <var class="Arg">ej</var> are elements of \(GF(2^v)\) and \(GF(2^{r-v})\), respectively.

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

<h5>5.3-4 TombakCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ TombakCode</code>( <var class="Arg">m</var>, <var class="Arg">e</var>, <var class="Arg">beta</var>, <var class="Arg">gamma</var>, <var class="Arg">w1</var>, <var class="Arg">w2</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">TombakCode</code> yields a code of length \(15 \cdot 2^{m-3} - 3\), redundancy \(2m\), minimum distance \(4\) and covering radius \(2\). <var class="Arg">e</var> is an element of \(GF(2^m)\). <var class="Arg">beta</var> and <var class="Arg">gamma</var> are elements of \(GF(2^{m-1})\). <var class="Arg">w1</var> and <var class="Arg">w2</var> are elements of \(GF(2^{m-3})\).

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

<h5>5.3-5 EnlargedTombakCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EnlargedTombakCode</code>( <var class="Arg">m</var>, <var class="Arg">e</var>, <var class="Arg">beta</var>, <var class="Arg">gamma</var>, <var class="Arg">w1</var>, <var class="Arg">w2</var>, <var class="Arg">u</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">EnlargedTombakCode</code> yields a code of length \(23 \cdot 2^{m-4} - 3\), redundancy \(2m-1\), minimum distance \(4\) and covering radius \(2\). The parameters <var class="Arg">m</var>, <var class="Arg">e</var>, <var class="Arg">beta</var>, <var class="Arg">gamma</var>, <var class="Arg">w1</var> and <var class="Arg">w2</var> are defined as in <code class="code">TombakCode</code>. <var class="Arg">u</var> is an element of \(GF(2^{m-1})\).

<div class="example"><pre>
gap> GabidulinCode( 4, Z(4)^0, Z(4)^1 );
a linear [19,12,3]2 Gabidulin code (m=4) over GF(2)
gap> EnlargedGabidulinCode( 4, Z(4)^0, Z(4)^1, Z(16)^11 );
a linear [26,18,3]2 enlarged Gabidulin code (m=4) over GF(2)
gap> DavydovCode( 6, 3, Z(8)^1, Z(8)^5 );
a linear [13,7,4]2 Davydov code (r=6, v=3) over GF(2)
gap> TombakCode( 5, Z(32)^6, Z(16)^14, Z(16)^10, Z(4)^0, Z(4)^1 );
a linear [57,47,4]2 Tombak code (m=5) over GF(2)
gap> EnlargedTombakCode( 6, Z(32)^6, Z(16)^14, Z(16)^10,
> Z(4)^0, Z(4)^0, Z(32)^23 );
a linear [89,78,4]2 enlarged Tombak code (m=6) over GF(2)
</pre></div>

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

<h4>5.4 
Golay Codes
</h4>

<q> The Golay code is probably the most important of all codes for both practical and theoretical reasons. </q> (<a href="chapBib_mj.html#biBMS83">[MS83]</a>, pg. 64). Though born in Switzerland, M. J. E. Golay (1902-1989) worked for the US Army Labs for most of his career. For more information on his life, see his obit in the June 1990 IEEE Information Society Newsletter.

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

<h5>5.4-1 BinaryGolayCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BinaryGolayCode</code>( )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">BinaryGolayCode</code> returns a binary Golay code. This is a perfect \([23,12,7]\) code. It is also cyclic, and has generator polynomial \(g(x)=1+x^2+x^4+x^5+x^6+x^{10}+x^{11}\). Extending it results in an extended Golay code (see <code class="func">ExtendedBinaryGolayCode</code> (<a href="chap5_mj.html#X84520C7983538806">5.4-2</a>)). There's also the ternary Golay code (see <code class="func">TernaryGolayCode</code> (<a href="chap5_mj.html#X7E0CCCD7866ADB94">5.4-3</a>)).

<div class="example"><pre>
gap> C:=BinaryGolayCode();
a cyclic [23,12,7]3 binary Golay code over GF(2)
gap> ExtendedBinaryGolayCode() = ExtendedCode(BinaryGolayCode());
true
gap> IsPerfectCode(C);
true
gap> IsCyclicCode(C);
true
</pre></div>

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

<h5>5.4-2 ExtendedBinaryGolayCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ExtendedBinaryGolayCode</code>( )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">ExtendedBinaryGolayCode</code> returns an extended binary Golay code. This is a \([24,12,8]\) code. Puncturing in the last position results in a perfect binary Golay code (see <code class="func">BinaryGolayCode</code> (<a href="chap5_mj.html#X80ED89C079CD0D09">5.4-1</a>)). The code is self-dual.

<div class="example"><pre>
gap> C := ExtendedBinaryGolayCode();
a linear [24,12,8]4 extended binary Golay code over GF(2)
gap> IsSelfDualCode(C);
true
gap> P := PuncturedCode(C);
a linear [23,12,7]3 punctured code
gap> P = BinaryGolayCode();
true
gap> IsCyclicCode(C);
false
</pre></div>

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

<h5>5.4-3 TernaryGolayCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ TernaryGolayCode</code>( )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">TernaryGolayCode</code> returns a ternary Golay code. This is a perfect \([11,6,5]\) code. It is also cyclic, and has generator polynomial \(g(x)=2+x^2+2x^3+x^4+x^5\). Extending it results in an extended Golay code (see <code class="func">ExtendedTernaryGolayCode</code> (<a href="chap5_mj.html#X81088A66816BCAE4">5.4-4</a>)). There's also the binary Golay code (see <code class="func">BinaryGolayCode</code> (<a href="chap5_mj.html#X80ED89C079CD0D09">5.4-1</a>)).

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

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

<h5>5.4-4 ExtendedTernaryGolayCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ExtendedTernaryGolayCode</code>( )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">ExtendedTernaryGolayCode</code> returns an extended ternary Golay code. This is a \([12,6,6]\) code. Puncturing this code results in a perfect ternary Golay code (see <code class="func">TernaryGolayCode</code> (<a href="chap5_mj.html#X7E0CCCD7866ADB94">5.4-3</a>)). The code is self-dual.

<div class="example"><pre>
gap> C := ExtendedTernaryGolayCode();
a linear [12,6,6]3 extended ternary Golay code over GF(3)
gap> IsSelfDualCode(C);
true
gap> P := PuncturedCode(C);
a linear [11,6,5]2 punctured code
gap> P = TernaryGolayCode();
true
gap> IsCyclicCode(C);
false
</pre></div>

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

<h4>5.5 
Generating Cyclic Codes
</h4>

The elements of a cyclic code \(C\) are all multiples of a ('generator') polynomial \(g(x)\), where calculations are carried out modulo \(x^n-1\). Therefore, as polynomials in \(x\), the elements always have degree less than \(n\). A cyclic code is an ideal in the ring \(F[x]/(x^n-1)\) of polynomials modulo \(x^n - 1\). The unique monic polynomial of least degree that generates \(C\) is called the generator polynomial of \(C\). It is a divisor of the polynomial \(x^n-1\).

The check polynomial is the polynomial \(h(x)\) with \(g(x)h(x)=x^n-1\). Therefore it is also a divisor of \(x^n-1\). The check polynomial has the property that

\[
c(x)h(x) \equiv 0 \pmod{x^n-1},
\]

for every codeword \(c(x)\in C\).

The first two functions described below generate cyclic codes from a given generator or check polynomial. All cyclic codes can be constructed using these functions.

Two of the Golay codes already described are cyclic (see <code class="func">BinaryGolayCode</code> (<a href="chap5_mj.html#X80ED89C079CD0D09">5.4-1</a>) and <code class="func">TernaryGolayCode</code> (<a href="chap5_mj.html#X7E0CCCD7866ADB94">5.4-3</a>)). For example, the GUAVA record for a binary Golay code contains the generator polynomial:

<div class="example"><pre>
gap> C := BinaryGolayCode();
a cyclic [23,12,7]3 binary Golay code over GF(2)
gap> Set(NamesOfComponents(C));
[ "Dimension", "GeneratorMat", "GeneratorPol",
 "GeneratorsOfLeftOperatorAdditiveGroup", "LeftActingDomain",
 "MinimumWeightOfGenerators", "Redundancy", "Size", "SpecialDecoder",
 "UpperBoundOptimalMinimumDistance", "WeightDistribution", "WordLength",
 "boundsCoveringRadius", "lowerBoundMinimumDistance", "name",
 "upperBoundMinimumDistance" ]
gap> C!.GeneratorPol;
x^11+x^10+x^6+x^5+x^4+x^2+Z(2)^0
</pre></div>

Then functions that generate cyclic codes from a prescribed set of roots of the generator polynomial are described, including the BCH codes (see <code class="func">RootsCode</code> (<a href="chap5_mj.html#X818F0E6583E01D4B">5.5-3</a>), <code class="func">BCHCode</code> (<a href="chap5_mj.html#X7C6BB07C87853C00">5.5-4</a>), <code class="func">ReedSolomonCode</code> (<a href="chap5_mj.html#X838F3CB3872CEF95">5.5-5</a>) and <code class="func">QRCode</code> (<a href="chap5_mj.html#X825F42F68179D2AB">5.5-7</a>)).

Finally we describe the trivial codes (see <code class="func">WholeSpaceCode</code> (<a href="chap5_mj.html#X7BC245E37EB7B23F">5.5-11</a>), <code class="func">NullCode</code> (<a href="chap5_mj.html#X7B4EF2017B2C61AD">5.5-12</a>), <code class="func">RepetitionCode</code> (<a href="chap5_mj.html#X83C5F8FE7827EAA7">5.5-13</a>)), and the command <code class="code">CyclicCodes</code> which lists all cyclic codes (<code class="func">CyclicCodes</code> (<a href="chap5_mj.html#X82FA9F65854D98A6">5.5-14</a>)).

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

<h5>5.5-1 GeneratorPolCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GeneratorPolCode</code>( <var class="Arg">g</var>, <var class="Arg">n</var>[, <var class="Arg">name</var>], <var class="Arg">F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">GeneratorPolCode</code> creates a cyclic code with a generator polynomial <var class="Arg">g</var>, word length <var class="Arg">n</var>, over <var class="Arg">F</var>. <var class="Arg">name</var> can contain a short description of the code.

If <var class="Arg">g</var> is not a divisor of \(x^n-1\), it cannot be a generator polynomial. In that case, a code is created with generator polynomial \(gcd( g, x^n-1 )\), i.e. the greatest common divisor of <var class="Arg">g</var> and \(x^n-1\). This is a valid generator polynomial that generates the ideal \((g)\). See <code class="func">Generating Cyclic Codes</code> (<a href="chap5_mj.html#X8366CC3685F0BC85">5.5</a>).

<div class="example"><pre>
gap> x:= Indeterminate( GF(2), "x" );; P:= x^2+1;
x^2+Z(2)^0
gap> C1 := GeneratorPolCode(P, 7, GF(2));
a cyclic [7,6,1..2]1 code defined by generator polynomial over GF(2)
gap> GeneratorPol( C1 );
x+Z(2)^0
gap> C2 := GeneratorPolCode( x+1, 7, GF(2)); 
a cyclic [7,6,1..2]1 code defined by generator polynomial over GF(2)
gap> GeneratorPol( C2 );
x+Z(2)^0
</pre></div>

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

<h5>5.5-2 CheckPolCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CheckPolCode</code>( <var class="Arg">h</var>, <var class="Arg">n</var>[, <var class="Arg">name</var>], <var class="Arg">F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">CheckPolCode</code> creates a cyclic code with a check polynomial <var class="Arg">h</var>, word length <var class="Arg">n</var>, over <var class="Arg">F</var>. <var class="Arg">name</var> can contain a short description of the code (as a string).

If <var class="Arg">h</var> is not a divisor of \(x^n-1\), it cannot be a check polynomial. In that case, a code is created with check polynomial \(gcd( h, x^n-1 )\), i.e. the greatest common divisor of <var class="Arg">h</var> and \(x^n-1\). This is a valid check polynomial that yields the same elements as the ideal \((h)\). See <a href="chap5_mj.html#X8366CC3685F0BC85">5.5</a>.

<div class="example"><pre>
gap> x := Indeterminate( GF(3), "x" );; P:= x^2+2;
x^2-Z(3)^0
gap> H := CheckPolCode(P, 7, GF(3));
a cyclic [7,1,7]4 code defined by check polynomial over GF(3)
gap> CheckPol(H);
x-Z(3)^0
gap> Gcd(P, X(GF(3))^7-1);
x-Z(3)^0
</pre></div>

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

<h5>5.5-3 RootsCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RootsCode</code>( <var class="Arg">n</var>, <var class="Arg">list</var> )</td><td class="tdright">( function )</td></tr></table></div>
This is the generalization of the BCH, Reed-Solomon and quadratic residue codes (see <code class="func">BCHCode</code> (<a href="chap5_mj.html#X7C6BB07C87853C00">5.5-4</a>), <code class="func">ReedSolomonCode</code> (<a href="chap5_mj.html#X838F3CB3872CEF95">5.5-5</a>) and <code class="func">QRCode</code> (<a href="chap5_mj.html#X825F42F68179D2AB">5.5-7</a>)). The user can give a length of the code <var class="Arg">n</var> and a prescribed set of zeros. The argument <var class="Arg">list</var> must be a valid list of \(n^{th}\) roots of unity in a splitting field \(GF(q^m)\). The resulting code will be over the field \(GF(q)\). The function will return the largest possible cyclic code for which the list <var class="Arg">list</var> is a subset of the roots of the code. From this list, GUAVA calculates the entire set of roots.

This command can also be called with the syntax <code class="code">RootsCode( n, list, q )</code>. In this second form, the second argument is a list of integers, ranging from \(0\) to \(n-1\). The resulting code will be over a field \(GF(q)\). GUAVA calculates a primitive \(n^{th}\) root of unity, \(\alpha\), in the extension field of \(GF(q)\). It uses the set of the powers of \(\alpha\) in the list as a prescribed set of zeros.

<div class="example"><pre>
gap> a := PrimitiveUnityRoot( 3, 14 );
Z(3^6)^52
gap> C1 := RootsCode( 14, [ a^0, a, a^3 ] );
a cyclic [14,7,3..6]3..7 code defined by roots over GF(3)
gap> MinimumDistance( C1 );
4
gap> b := PrimitiveUnityRoot( 2, 15 );
Z(2^4)
gap> C2 := RootsCode( 15, [ b, b^2, b^3, b^4 ] );
a cyclic [15,7,5]3..5 code defined by roots over GF(2)
gap> C2 = BCHCode( 15, 5, GF(2) );
true
gap> C3 := RootsCode( 4, [ 1, 2 ], 5 );
a cyclic [4,2,2..3]2 code defined by roots over GF(5)
gap> RootsOfCode( C3 );
[ Z(5), Z(5)^2 ]
gap> C3 = ReedSolomonCode( 4, 3 );
true
</pre></div>

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

<h5>5.5-4 BCHCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BCHCode</code>( <var class="Arg">n</var>[, <var class="Arg">b</var>], <var class="Arg">delta</var>, <var class="Arg">F</var> )</td><td class="tdright">( function )</td></tr></table></div>
The function <code class="code">BCHCode</code> returns a 'Bose-Chaudhuri-Hockenghem code' (or BCH code for short). This is the largest possible cyclic code of length <var class="Arg">n</var> over field <var class="Arg">F</var>, whose generator polynomial has zeros

\[
a^{b},a^{b+1}, ..., a^{b+delta-2},
\]

where \(a\) is a primitive \(n^{th}\) root of unity in the splitting field \(GF(q^m)\), <var class="Arg">b</var> is an integer \(0\leq b\leq n-delta+1\) and \(m\) is the multiplicative order of \(q\) modulo <var class="Arg">n</var>. (The integers \(\{b,...,b+delta-2\}\) typically lie in the range \(\{1,...,n-1\}\).) Default value for <var class="Arg">b</var> is \(1\), though the algorithm allows \(b=0\). The length <var class="Arg">n</var> of the code and the size \(q\) of the field must be relatively prime. The generator polynomial is equal to the least common multiple of the minimal polynomials of

\[
a^{b}, a^{b+1}, ..., a^{b+delta-2}.
\]

The set of zeroes of the generator polynomial is equal to the union of the sets

\[
\{a^x\ |\ x \in C_k\},
\]

where \(C_k\) is the \(k^{th}\) cyclotomic coset of \(q\) modulo \(n\) and \(b\leq k\leq b+delta-2\) (see <code class="func">CyclotomicCosets</code> (<a href="chap7_mj.html#X7AEA9F807E6FFEFF">7.5-12</a>)).

Special cases are \(b=1\) (resulting codes are called 'narrow-sense' BCH codes), and \(n=q^m-1\) (known as 'primitive' BCH codes). GUAVA calculates the largest value of \(d\) for which the BCH code with designed distance \(d\) coincides with the BCH code with designed distance <var class="Arg">delta</var>. This distance \(d\) is called the Bose distance of the code. The true minimum distance of the code is greater than or equal to the Bose distance.

Printed are the designed distance (to be precise, the Bose distance) \(d\), and the starting power \(b\).

The Sugiyama decoding algorithm has been implemented for this code (see <code class="func">Decode</code> (<a href="chap4_mj.html#X7A42FF7D87FC34AC">4.10-1</a>)).

<div class="example"><pre>
gap> C1 := BCHCode( 15, 3, 5, GF(2) );
a cyclic [15,5,7]5 BCH code, delta=7, b=1 over GF(2)
gap> DesignedDistance( C1 );
7
gap> C2 := BCHCode( 23, 2, GF(2) );
a cyclic [23,12,5..7]3 BCH code, delta=5, b=1 over GF(2)
gap> DesignedDistance( C2 ); 
5
gap> MinimumDistance(C2);
7
</pre></div>

See <code class="func">RootsCode</code> (<a href="chap5_mj.html#X818F0E6583E01D4B">5.5-3</a>) for a more general construction.

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

<h5>5.5-5 ReedSolomonCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ReedSolomonCode</code>( <var class="Arg">n</var>, <var class="Arg">d</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">ReedSolomonCode</code> returns a 'Reed-Solomon code' of length <var class="Arg">n</var>, designed distance <var class="Arg">d</var>. This code is a primitive narrow-sense BCH code over the field \(GF(q)\), where \(q=n+1\). The dimension of an RS code is \(n-d+1\). According to the Singleton bound (see <code class="func">UpperBoundSingleton</code> (<a href="chap7_mj.html#X8673277C7F6C04C3">7.1-1</a>)) the dimension cannot be greater than this, so the true minimum distance of an RS code is equal to <var class="Arg">d</var> and the code is maximum distance separable (see <code class="func">IsMDSCode</code> (<a href="chap4_mj.html#X789380D28018EC3F">4.3-7</a>)).

<div class="example"><pre>
gap> C1 := ReedSolomonCode( 3, 2 );
a cyclic [3,2,2]1 Reed-Solomon code over GF(4)
gap> IsCyclicCode(C1);
true
gap> C2 := ReedSolomonCode( 4, 3 );
a cyclic [4,2,3]2 Reed-Solomon code over GF(5)
gap> RootsOfCode( C2 );
[ Z(5), Z(5)^2 ]
gap> IsMDSCode(C2);
true
</pre></div>

See <code class="func">GeneralizedReedSolomonCode</code> (<a href="chap5_mj.html#X810AB3DB844FFCE9">5.6-2</a>) for a more general construction.

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

<h5>5.5-6 ExtendedReedSolomonCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ExtendedReedSolomonCode</code>( <var class="Arg">n</var>, <var class="Arg">d</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">ExtendedReedSolomonCode</code> creates a Reed-Solomon code of length \(n-1\) with designed distance \(d-1\) and then returns the code which is extended by adding an overall parity-check symbol. The motivation for creating this function is calling <code class="func">ExtendedCode</code> (<a href="chap6_mj.html#X794679BE7F9EB5C1">6.1-1</a>) function over a Reed-Solomon code will take considerably long time.

<div class="example"><pre>
gap> C := ExtendedReedSolomonCode(17, 13);
a linear [17,5,13]9..12 extended Reed Solomon code over GF(17)
gap> IsMDSCode(C);
true
</pre></div>

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

<h5>5.5-7 QRCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ QRCode</code>( <var class="Arg">n</var>, <var class="Arg">F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">QRCode</code> returns a quadratic residue code. If <var class="Arg">F</var> is a field \(GF(q)\), then \(q\) must be a quadratic residue modulo <var class="Arg">n</var>. That is, an \(x\) exists with \(x^2 \equiv q \pmod n\). Both <var class="Arg">n</var> and \(q\) must be primes. Its generator polynomial is the product of the polynomials \(x-a^i\). \(a\) is a primitive \(n^{th}\) root of unity, and \(i\) is an integer in the set of quadratic residues modulo <var class="Arg">n</var>.

<div class="example"><pre>
gap> C1 := QRCode( 7, GF(2) );
a cyclic [7,4,3]1 quadratic residue code over GF(2)
gap> IsEquivalent( C1, HammingCode( 3, GF(2) ) );
true
gap> IsCyclicCode(C1);
true
gap> IsCyclicCode(HammingCode( 3, GF(2) ));
false
gap> C2 := QRCode( 11, GF(3) );
a cyclic [11,6,4..5]2 quadratic residue code over GF(3)
gap> C2 = TernaryGolayCode();
true
gap> Q1 := QRCode( 7, GF(2));
a cyclic [7,4,3]1 quadratic residue code over GF(2)
gap> P1:=AutomorphismGroup(Q1); IdGroup(P1);
Group([ (1,2)(5,7), (2,3)(4,7), (2,4)(5,6), (3,5)(6,7), (3,7)(5,6) ])
[ 168, 42 ]
</pre></div>

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

<h5>5.5-8 QQRCodeNC</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ QQRCodeNC</code>( <var class="Arg">p</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">QQRCodeNC</code> is the same as <code class="code">QQRCode</code>, except that it uses <code class="code">GeneratorMatCodeNC</code> instead of <code class="code">GeneratorMatCode</code>.

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

<h5>5.5-9 QQRCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ QQRCode</code>( <var class="Arg">p</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">QQRCode</code> returns a quasi-quadratic residue code, as defined by Proposition 2.2 in Bazzi-Mittel <a href="chapBib_mj.html#biBBM03">[BM06]</a>. The parameter <var class="Arg">p</var> must be a prime. Its generator matrix has the block form \(G=(Q,N)\). Here \(Q\) is a \(p\times \) circulant matrix whose top row is \((0,x_1,...,x_{p-1})\), where \(x_i=1\) if and only if \(i\) is a quadratic residue mod \(p\), and \(N\) is a \(p\times \) circulant matrix whose top row is \((0,y_1,...,y_{p-1})\), where \(x_i+y_i=1\) for all \(i\). (In fact, this matrix can be recovered as the component <code class="code">DoublyCirculant</code> of the code.)

<div class="example"><pre>
gap> C1 := QQRCode( 7);
a linear [14,7,1..4]3..5 code defined by generator matrix over GF(2)
gap> G1:=GeneratorMat(C1);;
gap> Display(G1);
. 1 1 . 1 . . . . . 1 . 1 1
. . 1 1 . 1 . 1 . . . 1 . 1
. . . 1 1 . 1 1 1 . . . 1 .
1 . . . 1 1 . . 1 1 . . . 1
. 1 . . . 1 1 1 . 1 1 . . .
1 . 1 . . . 1 . 1 . 1 1 . .
1 1 . 1 . . . . . 1 . 1 1 .
gap> Display(C1!.DoublyCirculant);
. 1 1 . 1 . . . . . 1 . 1 1
. . 1 1 . 1 . 1 . . . 1 . 1
. . . 1 1 . 1 1 1 . . . 1 .
1 . . . 1 1 . . 1 1 . . . 1
. 1 . . . 1 1 1 . 1 1 . . .
1 . 1 . . . 1 . 1 . 1 1 . .
1 1 . 1 . . . . . 1 . 1 1 .
gap> MinimumDistance(C1);
4
gap> C2 := QQRCode( 29); MinimumDistance(C2);
a linear [58,28,1..14]8..29 code defined by generator matrix over GF(2)
12
gap> Aut2:=AutomorphismGroup(C2); IdGroup(Aut2);
<permutation group of size 812 with 4 generators>
[ 812, 7 ]
</pre></div>

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

<h5>5.5-10 FireCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FireCode</code>( <var class="Arg">g</var>, <var class="Arg">b</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">FireCode</code> constructs a (binary) Fire code. <var class="Arg">g</var> is a primitive polynomial of degree \(m\), and a factor of \(x^r-1\). <var class="Arg">b</var> an integer \(0 \leq b \leq m\) not divisible by \(r\), that determines the burst length of a single error burst that can be corrected. The argument <var class="Arg">g</var> can be a polynomial with base ring \(GF(2)\), or a list of coefficients in \(GF(2)\). The generator polynomial of the code is defined as the product of <var class="Arg">g</var> and \(x^{2b-1}+1\).

Here is the general definition of 'Fire code', named after P. Fire, who introduced these codes in 1959 in order to correct burst errors. First, a definition. If \(F=GF(q)\) and \(f\in F[x]\) then we say \(f\) has order \(e\) if \(f(x)|(x^e-1)\). A Fire code is a cyclic code over \(F\) with generator polynomial \(g(x)= (x^{2t-1}-1)p(x)\), where \(p(x)\) does not divide \(x^{2t-1}-1\) and satisfies \(deg(p(x))\geq t\). The length of such a code is the order of \(g(x)\). Non-binary Fire codes have not been implemented.

.

<div class="example"><pre>
gap> x:= Indeterminate( GF(2), "x" );; G:= x^3+x^2+1;
x^3+x^2+Z(2)^0
gap> Factors( G );
[ x^3+x^2+Z(2)^0 ]
gap> C := FireCode( G, 3 );
a cyclic [35,27,1..4]2..6 3 burst error correcting fire code over GF(2)
gap> MinimumDistance( C ); # Still it can correct bursts of length 3 
4
</pre></div>

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

<h5>5.5-11 WholeSpaceCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ WholeSpaceCode</code>( <var class="Arg">n</var>, <var class="Arg">F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">WholeSpaceCode</code> returns the cyclic whole space code of length <var class="Arg">n</var> over <var class="Arg">F</var>. This code consists of all polynomials of degree less than <var class="Arg">n</var> and coefficients in <var class="Arg">F</var>.

<div class="example"><pre>
gap> C := WholeSpaceCode( 5, GF(3) );
a cyclic [5,5,1]0 whole space code over GF(3)
</pre></div>

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

<h5>5.5-12 NullCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NullCode</code>( <var class="Arg">n</var>, <var class="Arg">F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">NullCode</code> returns the zero-dimensional nullcode with length <var class="Arg">n</var> over <var class="Arg">F</var>. This code has only one word: the all zero word. It is cyclic though!

<div class="example"><pre>
gap> C := NullCode( 5, GF(3) );
a cyclic [5,0,5]5 nullcode over GF(3)
gap> AsSSortedList( C );
[ [ 0 0 0 0 0 ] ]
</pre></div>

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

<h5>5.5-13 RepetitionCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RepetitionCode</code>( <var class="Arg">n</var>, <var class="Arg">F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">RepetitionCode</code> returns the cyclic repetition code of length <var class="Arg">n</var> over <var class="Arg">F</var>. The code has as many elements as <var class="Arg">F</var>, because each codeword consists of a repetition of one of these elements.

<div class="example"><pre>
gap> C := RepetitionCode( 3, GF(5) );
a cyclic [3,1,3]2 repetition code over GF(5)
gap> AsSSortedList( C );
[ [ 0 0 0 ], [ 1 1 1 ], [ 2 2 2 ], [ 4 4 4 ], [ 3 3 3 ] ]
gap> IsPerfectCode( C );
false
gap> IsMDSCode( C );
true
</pre></div>

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

<h5>5.5-14 CyclicCodes</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CyclicCodes</code>( <var class="Arg">n</var>, <var class="Arg">F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">CyclicCodes</code> returns a list of all cyclic codes of length <var class="Arg">n</var> over <var class="Arg">F</var>. It constructs all possible generator polynomials from the factors of \(x^n-1\). Each combination of these factors yields a generator polynomial after multiplication.

<div class="example"><pre>
gap> CyclicCodes(3,GF(3));
[ a cyclic [3,3,1]0 enumerated code over GF(3),
 a cyclic [3,2,1..2]1 enumerated code over GF(3),
 a cyclic [3,1,3]2 enumerated code over GF(3),
 a cyclic [3,0,3]3 enumerated code over GF(3) ]
</pre></div>

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

<h5>5.5-15 NrCyclicCodes</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NrCyclicCodes</code>( <var class="Arg">n</var>, <var class="Arg">F</var> )</td><td class="tdright">( function )</td></tr></table></div>
The function <code class="code">NrCyclicCodes</code> calculates the number of cyclic codes of length <var class="Arg">n</var> over field <var class="Arg">F</var>.

<div class="example"><pre>
gap> NrCyclicCodes( 23, GF(2) );
8
gap> codelist := CyclicCodes( 23, GF(2) );
[ a cyclic [23,23,1]0 enumerated code over GF(2),
 a cyclic [23,22,1..2]1 enumerated code over GF(2),
 a cyclic [23,11,1..8]4..7 enumerated code over GF(2),
 a cyclic [23,0,23]23 enumerated code over GF(2),
 a cyclic [23,11,1..8]4..7 enumerated code over GF(2),
 a cyclic [23,12,1..7]3 enumerated code over GF(2),
 a cyclic [23,1,23]11 enumerated code over GF(2),
 a cyclic [23,12,1..7]3 enumerated code over GF(2) ]
gap> BinaryGolayCode() in codelist;
true
gap> RepetitionCode( 23, GF(2) ) in codelist;
true
gap> CordaroWagnerCode( 23 ) in codelist; # This code is not cyclic 
false
</pre></div>

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

<h5>5.5-16 QuasiCyclicCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ QuasiCyclicCode</code>( <var class="Arg">G</var>, <var class="Arg">s</var>, <var class="Arg">F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">QuasiCyclicCode( G, k, F )</code> generates a rate \(1/m\) quasi-cyclic code over field <var class="Arg">F</var>. The input <var class="Arg">G</var> is a list of univariate polynomials and \(m\) is the cardinality of this list. Note that \(m\) must be at least \(2\). The input <var class="Arg">s</var> is the size of each circulant and it may not necessarily be the same as the code dimension \(k\), i.e. \(k \le s\).

There also exists another version, <code class="code">QuasiCyclicCode( G, s )</code> which produces quasi-cyclic codes over \(F_2\) only. Here the parameter <var class="Arg">s</var> holds the same definition and the input <var class="Arg">G</var> is a list of integers, where each integer is an octal representation of a binary univariate polynomial.

<div class="example"><pre>
gap> #
gap> # This example show the case for k = s
gap> #
gap> L1 := PolyCodeword( Codeword("10000000000", GF(4)) );
Z(2)^0
gap> L2 := PolyCodeword( Codeword("12223201000", GF(4)) );
x^7+Z(2^2)*x^5+Z(2^2)^2*x^4+Z(2^2)*x^3+Z(2^2)*x^2+Z(2^2)*x+Z(2)^0
gap> L3 := PolyCodeword( Codeword("31111220110", GF(4)) );
x^9+x^8+Z(2^2)*x^6+Z(2^2)*x^5+x^4+x^3+x^2+x+Z(2^2)^2
gap> L4 := PolyCodeword( Codeword("13320333010", GF(4)) );
x^9+Z(2^2)^2*x^7+Z(2^2)^2*x^6+Z(2^2)^2*x^5+Z(2^2)*x^3+Z(2^2)^2*x^2+Z(2^2)^2*x+\
Z(2)^0
gap> L5 := PolyCodeword( Codeword("20102211100", GF(4)) );
x^8+x^7+x^6+Z(2^2)*x^5+Z(2^2)*x^4+x^2+Z(2^2)
gap> C := QuasiCyclicCode( [L1, L2, L3, L4, L5], 11, GF(4) );
a linear [55,11,1..32]24..41 quasi-cyclic code over GF(4)
gap> MinimumDistance(C);
29
gap> Display(C);
a linear [55,11,29]24..41 quasi-cyclic code over GF(4)
gap> #
gap> # This example show the case for k < s
gap> #
gap> L1 := PolyCodeword( Codeword("02212201220120211002000",GF(3)) );
-x^19+x^16+x^15-x^14-x^12+x^11-x^9-x^8+x^7-x^5-x^4+x^3-x^2-x
gap> L2 := PolyCodeword( Codeword("00221100200120220001110",GF(3)) );
x^21+x^20+x^19-x^15-x^14-x^12+x^11-x^8+x^5+x^4-x^3-x^2
gap> L3 := PolyCodeword( Codeword("22021011202221111020021",GF(3)) );
x^22-x^21-x^18+x^16+x^15+x^14+x^13-x^12-x^11-x^10-x^8+x^7+x^6+x^4-x^3-x-Z(3)^0
gap> C := QuasiCyclicCode( [L1, L2, L3], 23, GF(3) );
a linear [69,12,1..37]27..46 quasi-cyclic code over GF(3)
gap> MinimumDistance(C);
34
gap> Display(C);
a linear [69,12,34]27..46 quasi-cyclic code over GF(3)
gap> #
gap> # This example show the binary case using octal representation
gap> #
gap> L1 := 001;; # 0 000 001
gap> L2 := 013;; # 0 001 011
gap> L3 := 015;; # 0 001 101
gap> L4 := 077;; # 0 111 111
gap> C := QuasiCyclicCode( [L1, L2, L3, L4], 7 );
a linear [28,7,1..12]8..14 quasi-cyclic code over GF(2)
gap> MinimumDistance(C);
12
gap> Display(C);
a linear [28,7,12]8..14 quasi-cyclic code over GF(2)
</pre></div>

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

<h5>5.5-17 CyclicMDSCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CyclicMDSCode</code>( <var class="Arg">q</var>, <var class="Arg">m</var>, <var class="Arg">k</var> )</td><td class="tdright">( function )</td></tr></table></div>
Given the input parameters <var class="Arg">q</var>, <var class="Arg">m</var> and <var class="Arg">k</var>, this function returns a \([q^m + 1, k, q^m - k + 2]\) cyclic MDS code over GF(\(q^m\)). If \(q^m\) is even, any value of \(k\) can be used, otherwise only odd value of \(k\) is accepted.

<div class="example"><pre>
gap> C:=CyclicMDSCode(2,6,24);
a cyclic [65,24,42]31..41 MDS code over GF(64)
gap> IsMDSCode(C);
true
gap> C:=CyclicMDSCode(5,3,77);
a cyclic [126,77,50]35..49 MDS code over GF(125)
gap> IsMDSCode(C);
true
gap> C:=CyclicMDSCode(3,3,25);
a cyclic [28,25,4]2..3 MDS code over GF(27)
gap> GeneratorPol(C);
x^3+Z(3^3)^7*x^2+Z(3^3)^20*x-Z(3)^0
</pre></div>

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

<h5>5.5-18 FourNegacirculantSelfDualCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FourNegacirculantSelfDualCode</code>( <var class="Arg">ax</var>, <var class="Arg">bx</var>, <var class="Arg">k</var> )</td><td class="tdright">( function )</td></tr></table></div>
A four-negacirculant self-dual code has a generator matrix \(G\) of the the following form

<pre class="normal">

 - -
 | | A | B |
G = | I_2k |-----+-----|
 | | -B^T| A^T |
 - -

</pre>

where \(AA^T + BB^T = -I_k\) and \(A\), \(B\) and their transposed are all \(k \times k\) negacirculant matrices. The generator matrix \(G\) returns a \([2k, k, d]_q\) self-dual code over GF(\(q\)). For discussion on four-negacirculant self-dual codes, refer to <a href="chapBib_mj.html#biBHHKK07">[HHKK07]</a>.

The input parameters <var class="Arg">ax</var> and <var class="Arg">bx</var> are the defining polynomials over GF(\(q\)) of negacirculant matrices \(A\) and \(B\) respectively. The last parameter <var class="Arg">k</var> is the dimension of the code.

<div class="example"><pre>
gap> ax:=PolyCodeword(Codeword("1200200", GF(3)));
-x^4-x+Z(3)^0
gap> bx:=PolyCodeword(Codeword("2020221", GF(3)));
x^6-x^5-x^4-x^2-Z(3)^0
gap> C:=FourNegacirculantSelfDualCode(ax, bx, 14);;
gap> MinimumDistance(C);;
gap> CoveringRadius(C);;
gap> IsSelfDualCode(C);
true
gap> Display(C);
a linear [28,14,9]7 four-negacirculant self-dual code over GF(3)
gap> Display( GeneratorMat(C) );
1 . . . . . . . . . . . . . 1 2 . . 2 . . 2 . 2 . 2 2 1
. 1 . . . . . . . . . . . . . 1 2 . . 2 . 2 2 . 2 . 2 2
. . 1 . . . . . . . . . . . . . 1 2 . . 2 1 2 2 . 2 . 2
. . . 1 . . . . . . . . . . 1 . . 1 2 . . 1 1 2 2 . 2 .
. . . . 1 . . . . . . . . . . 1 . . 1 2 . . 1 1 2 2 . 2
. . . . . 1 . . . . . . . . . . 1 . . 1 2 1 . 1 1 2 2 .
. . . . . . 1 . . . . . . . 1 . . 1 . . 1 . 1 . 1 1 2 2
. . . . . . . 1 . . . . . . 1 1 2 2 . 2 . 1 . . 1 . . 1
. . . . . . . . 1 . . . . . . 1 1 2 2 . 2 2 1 . . 1 . .
. . . . . . . . . 1 . . . . 1 . 1 1 2 2 . . 2 1 . . 1 .
. . . . . . . . . . 1 . . . . 1 . 1 1 2 2 . . 2 1 . . 1
. . . . . . . . . . . 1 . . 1 . 1 . 1 1 2 2 . . 2 1 . .
. . . . . . . . . . . . 1 . 1 1 . 1 . 1 1 . 2 . . 2 1 .
. . . . . . . . . . . . . 1 2 1 1 . 1 . 1 . . 2 . . 2 1
gap> ax:=PolyCodeword(Codeword("013131000", GF(7)));
x_1^5+Z(7)*x_1^4+x_1^3+Z(7)*x_1^2+x_1
gap> bx:=PolyCodeword(Codeword("425435030", GF(7)));
Z(7)*x_1^7+Z(7)^5*x_1^5+Z(7)*x_1^4+Z(7)^4*x_1^3+Z(7)^5*x_1^2+Z(7)^2*x_1+Z(7)^4
gap> C:=FourNegacirculantSelfDualCodeNC(ax, bx, 18);
a linear [36,18,1..13]0..36 four-negacirculant self-dual code over GF(7)
gap> IsSelfDualCode(C);
true
</pre></div>

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

<h5>5.5-19 FourNegacirculantSelfDualCodeNC</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FourNegacirculantSelfDualCodeNC</code>( <var class="Arg">ax</var>, <var class="Arg">bx</var>, <var class="Arg">k</var> )</td><td class="tdright">( function )</td></tr></table></div>
This function is the same as <code class="code">FourNegacirculantSelfDualCode</code>, except this version is faster as it does not estimate the minimum distance and covering radius of the code.

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

<h4>5.6 
Evaluation Codes
</h4>

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

<h5>5.6-1 EvaluationCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EvaluationCode</code>( <var class="Arg">P</var>, <var class="Arg">L</var>, <var class="Arg">R</var> )</td><td class="tdright">( function )</td></tr></table></div>
Input: <var class="Arg">F</var> is a finite field, <var class="Arg">L</var> is a list of rational functions in \(R=F[x_1,...,x_r]\), <var class="Arg">P</var> is a list of \(n\) points in \(F^r\) at which all of the functions in <var class="Arg">L</var> are defined. Output: The 'evaluation code' \(C\), which is the image of the evaluation map

\[
Eval_P:span(L)\rightarrow F^n,
\]

given by \(f\longmapsto (f(p_1),...,f(p_n))\), where \(P=\{p_1,...,p_n\}\) and \(f \in L\). The generator matrix of \(C\) is \(G=(f_i(p_j))_{f_i\in L,p_j\in P}\).

This command returns a "record" object <code class="code">C</code> with several extra components (type <code class="code">NamesOfComponents(C)</code> to see them all): <code class="code">C!.EvaluationMat</code> (not the same as the generator matrix in general), <code class="code">C!.points</code> (namely <var class="Arg">P</var>), <code class="code">C!.basis</code> (namely <var class="Arg">L</var>), and <code class="code">C!.ring</code> (namely <var class="Arg">R</var>).

<div class="example"><pre>
gap> F:=GF(11);
GF(11)
gap> R := PolynomialRing(F,2);;
gap> indets := IndeterminatesOfPolynomialRing(R);;
gap> x:=indets[1];; y:=indets[2];;
gap> L:=[x^2*y,x*y,x^5,x^4,x^3,x^2,x,x^0];;
gap> Pts:=[ [ Z(11)^9, Z(11) ], [ Z(11)^8, Z(11) ], [ Z(11)^7, 0*Z(11) ],
 [ Z(11)^6, 0*Z(11) ], [ Z(11)^5, 0*Z(11) ], [ Z(11)^4, 0*Z(11) ],
 [ Z(11)^3, Z(11) ], [ Z(11)^2, 0*Z(11) ], [ Z(11), 0*Z(11) ],
 [ Z(11)^0, 0*Z(11) ], [ 0*Z(11), Z(11) ] ];;
gap> C:=EvaluationCode(Pts,L,R);
a linear [11,8,1..3]2..3 evaluation code over GF(11)
gap> MinimumDistance(C);
3

</pre></div>

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

<h5>5.6-2 GeneralizedReedSolomonCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GeneralizedReedSolomonCode</code>( <var class="Arg">P</var>, <var class="Arg">k</var>, <var class="Arg">R</var> )</td><td class="tdright">( function )</td></tr></table></div>
Input: R=F[x], where <var class="Arg">F</var> is a finite field, <var class="Arg">k</var> is a positive integer, <var class="Arg">P</var> is a list of \(n\) points in \(F\). Output: The \(C\) which is the image of the evaluation map

\[
Eval_P:F[x]_k\rightarrow F^n,
\]

given by \(f\longmapsto (f(p_1),...,f(p_n))\), where \(P=\{p_1,...,p_n\}\subset F\) and \(f\) ranges over the space \(F[x]_k\) of all polynomials of degree less than \(k\).

This command returns a "record" object <code class="code">C</code> with several extra components (type <code class="code">NamesOfComponents(C)</code> to see them all): <code class="code">C!.points</code> (namely <var class="Arg">P</var>), <code class="code">C!.degree</code> (namely <var class="Arg">k</var>), and <code class="code">C!.ring</code> (namely <var class="Arg">R</var>).

This code can be decoded using <code class="code">Decodeword</code>, which applies the special decoder method (the interpolation method), or using <code class="code">GeneralizedReedSolomonDecoderGao</code> which applies an algorithm of S. Gao (see <code class="func">GeneralizedReedSolomonDecoderGao</code> (<a href="chap4_mj.html#X7D48DE2A84474C6A">4.10-3</a>)). This code has a special decoder record which implements the interpolation algorithm described in section 5.2 of Justesen and Hoholdt <a href="chapBib_mj.html#biBJH04">[JH04]</a>. See <code class="func">Decode</code> (<a href="chap4_mj.html#X7A42FF7D87FC34AC">4.10-1</a>) and <code class="func">Decodeword</code> (<a href="chap4_mj.html#X7D870C9387C47D9F">4.10-2</a>) for more details.

The weighted version has implemented with the option <code class="code">GeneralizedReedSolomonCode(P,k,R,wts)</code>, where \(wts = [v_1, ..., v_n]\) is a sequence of \(n\) non-zero elements from the base field \(F\) of <var class="Arg">R</var>. See also the generalized Reed--Solomon code \(GRS_k(P, V)\) described in <a href="chapBib_mj.html#biBMS83">[MS83]</a>, p.303.

The list-decoding algorithm of Sudan-Guraswami (described in section 12.1 of <a href="chapBib_mj.html#biBJH04">[JH04]</a>) has been implemented for generalized Reed-Solomon codes. See <code class="func">GeneralizedReedSolomonListDecoder</code> (<a href="chap4_mj.html#X7CFF98D483502053">4.10-4</a>).

<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> V:=[Z(11)^0,Z(11)^0,Z(11)^0,Z(11)^0,Z(11)];
[ Z(11)^0, Z(11)^0, Z(11)^0, Z(11)^0, Z(11) ]
gap> C:=GeneralizedReedSolomonCode(P,3,R,V);
a linear [5,3,1..3]2 weighted generalized Reed-Solomon code over GF(11)
gap> MinimumDistance(C);
3
</pre></div>

See <code class="func">EvaluationCode</code> (<a href="chap5_mj.html#X78E078567D19D433">5.6-1</a>) for a more general construction.

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

<h5>5.6-3 GeneralizedReedMullerCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GeneralizedReedMullerCode</code>( <var class="Arg">Pts</var>, <var class="Arg">r</var>, <var class="Arg">F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">GeneralizedReedMullerCode</code> returns a 'Reed-Muller code' \(C\) with length \(|Pts|\) and order \(r\). One considers (a) a basis of monomials for the vector space over \(F=GF(q)\) of all polynomials in \(F[x_1,...,x_d]\) of degree at most \(r\), and (b) a set \(Pts\) of points in \(F^d\). The generator matrix of the associated Reed-Muller code \(C\) is \(G=(f(p))_{f\in B,p \in Pts}\). This code \(C\) is constructed using the command <code class="code">GeneralizedReedMullerCode(Pts,r,F)</code>. When \(Pts\) is the set of all \(q^d\) points in \(F^d\) then the command <code class="code">GeneralizedReedMuller(d,r,F)</code> yields the code. When \(Pts\) is the set of all \((q-1)^d\) points with no coordinate equal to \(0\) then this is can be constructed using the <code class="code">ToricCode</code> command (as a special case).

This command returns a "record" object <code class="code">C</code> with several extra components (type <code class="code">NamesOfComponents(C)</code> to see them all): <code class="code">C!.points</code> (namely <var class="Arg">Pts</var>) and <code class="code">C!.degree</code> (namely <var class="Arg">r</var>).

<div class="example"><pre>
gap> Pts:=ToricPoints(2,GF(5));
[ [ Z(5)^0, Z(5)^0 ], [ Z(5)^0, Z(5) ], [ Z(5)^0, Z(5)^2 ],
 [ Z(5)^0, Z(5)^3 ], [ Z(5), Z(5)^0 ], [ Z(5), Z(5) ], [ Z(5), Z(5)^2 ],
 [ Z(5), Z(5)^3 ], [ Z(5)^2, Z(5)^0 ], [ Z(5)^2, Z(5) ], [ Z(5)^2, Z(5)^2 ],
 [ Z(5)^2, Z(5)^3 ], [ Z(5)^3, Z(5)^0 ], [ Z(5)^3, Z(5) ],
 [ Z(5)^3, Z(5)^2 ], [ Z(5)^3, Z(5)^3 ] ]
gap> C:=GeneralizedReedMullerCode(Pts,2,GF(5));
a linear [16,6,1..11]6..10 generalized Reed-Muller code over GF(5)
</pre></div>

See <code class="func">EvaluationCode</code> (<a href="chap5_mj.html#X78E078567D19D433">5.6-1</a>) for a more general construction.

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

<h5>5.6-4 ToricPoints</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ToricPoints</code>( <var class="Arg">n</var>, <var class="Arg">F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">ToricPoints(n,F)</code> returns the points in \((F^{\times})^n\).

<div class="example"><pre>
gap> ToricPoints(2,GF(5));
[ [ Z(5)^0, Z(5)^0 ], [ Z(5)^0, Z(5) ], [ Z(5)^0, Z(5)^2 ],
 [ Z(5)^0, Z(5)^3 ], [ Z(5), Z(5)^0 ], [ Z(5), Z(5) ], [ Z(5), Z(5)^2 ],
 [ Z(5), Z(5)^3 ], [ Z(5)^2, Z(5)^0 ], [ Z(5)^2, Z(5) ], [ Z(5)^2, Z(5)^2 ],
 [ Z(5)^2, Z(5)^3 ], [ Z(5)^3, Z(5)^0 ], [ Z(5)^3, Z(5) ],
 [ Z(5)^3, Z(5)^2 ], [ Z(5)^3, Z(5)^3 ] ]
</pre></div>

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

<h5>5.6-5 ToricCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ToricCode</code>( <var class="Arg">L</var>, <var class="Arg">F</var> )</td><td class="tdright">( function )</td></tr></table></div>
This function returns the toric codes as in D. Joyner <a href="chapBib_mj.html#biBJo04">[Joy04]</a> (see also J. P. Hansen <a href="chapBib_mj.html#biBHan99">[Han00]</a>). This is a truncated (generalized) Reed-Muller code. Here <var class="Arg">L</var> is a list of integral vectors and <var class="Arg">F</var> is the finite field. The size of <var class="Arg">F</var> must be different from \(2\).

This command returns a record object <code class="code">C</code> with an extra component (type <code class="code">NamesOfComponents(C)</code> to see them all): <code class="code">C!.exponents</code> (namely <var class="Arg">L</var>).

<div class="example"><pre>
gap> C:=ToricCode([[1,0],[3,4]],GF(3));
a linear [4,1,4]2 toric code over GF(3)
gap> Display(GeneratorMat(C));
1 1 2 2
gap> Elements(C);
[ [ 0 0 0 0 ], [ 1 1 2 2 ], [ 2 2 1 1 ] ]
</pre></div>

See <code class="func">EvaluationCode</code> (<a href="chap5_mj.html#X78E078567D19D433">5.6-1</a>) for a more general construction.

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

<h4>5.7 
Algebraic geometric codes
</h4>

Certain GUAVA functions related to algebraic geometric codes are described in this section.

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

<h5>5.7-1 AffineCurve</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AffineCurve</code>( <var class="Arg">poly</var>, <var class="Arg">ring</var> )</td><td class="tdright">( function )</td></tr></table></div>
This function simply defines the data structure of an affine plane curve. In GUAVA, an affine curve is a record <var class="Arg">crv</var> having two components: a polynomial <var class="Arg">poly</var>, accessed in GUAVA by <var class="Arg">crv.polynomial</var>, and a polynomial ring over a field \(F\) in two variables <var class="Arg">ring</var>, accessed in GUAVA by <var class="Arg">crv.ring</var>, containing <var class="Arg">poly</var>. You use this function to define a curve in GUAVA.

For example, for the ring, one could take \({\mathbb{Q}}[x,y]\), and for the polynomial one could take \(f(x,y)=x^2+y^2-1\). For the affine line, simply taking \({\mathbb{Q}}[x,y]\) for the ring and \(f(x,y)=y\) for the polynomial.

(Not sure if \(F\) needs to be a field in fact ...)

To compute its degree, simply use the <code class="func">DegreeMultivariatePolynomial</code> (<a href="chap7_mj.html#X80433A4B792880EF">7.6-2</a>) command.

<div class="example"><pre>
gap> F:=GF(11);;
gap> R2:=PolynomialRing(F,2);
GF(11)[t,x_2]
gap> vars:=IndeterminatesOfPolynomialRing(R2);;
gap> x:=vars[1];; y:=vars[2];;
gap> poly:=y;; crvP1:=AffineCurve(poly,R2);
rec( polynomial := x_2, ring := GF(11)[t,x_2] )
gap> degree_crv:=DegreeMultivariatePolynomial(poly,R2);
1
gap> poly:=y^2-x*(x^2-1);; ell_crv:=AffineCurve(poly,R2);
rec( polynomial := -t^3+x_2^2+t, ring := GF(11)[t,x_2] )
gap> degree_crv:=DegreeMultivariatePolynomial(poly,R2);
3
gap> poly:=x^2+y^2-1;; circle:=AffineCurve(poly,R2);
rec( polynomial := t^2+x_2^2-Z(11)^0, ring := GF(11)[t,x_2] )
gap> degree_crv:=DegreeMultivariatePolynomial(poly,R2);
2
gap> q:=3;;
gap> F:=GF(q^2);;
gap> R:=PolynomialRing(F,2);;
gap> vars:=IndeterminatesOfPolynomialRing(R);
[ x, x_2 ]
gap> x:=vars[1];
x
gap> y:=vars[2];
x_2
gap> crv:=AffineCurve(y^q+y-x^(q+1),R);
rec( polynomial := -x^4+x_2^3+x_2, ring := GF(3^2)[x,x_2] )
</pre></div>

In GAP, a point on a curve defined by \(f(x,y)=0\) is simply a list <var class="Arg">[a,b]</var> of elements of \(F\) satisfying this polynomial equation.

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

<h5>5.7-2 AffinePointsOnCurve</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AffinePointsOnCurve</code>( <var class="Arg">f</var>, <var class="Arg">R</var>, <var class="Arg">E</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">AffinePointsOnCurve(f,R,E)</code> returns the points \((x,y) \in E^2\) satisying \(f(x,y)=0\), where <var class="Arg">f</var> is an element of \(R=F[x,y]\).

<div class="example"><pre>
gap> F:=GF(11);;
gap> R := PolynomialRing(F,["x","y"]);
GF(11)[x,y]
gap> indets := IndeterminatesOfPolynomialRing(R);;
gap> x:=indets[1];; y:=indets[2];;
gap> P:=AffinePointsOnCurve(y^2-x^11+x,R,F);
[ [ Z(11)^9, 0*Z(11) ], [ Z(11)^8, 0*Z(11) ], [ Z(11)^7, 0*Z(11) ],
 [ Z(11)^6, 0*Z(11) ], [ Z(11)^5, 0*Z(11) ], [ Z(11)^4, 0*Z(11) ],
 [ Z(11)^3, 0*Z(11) ], [ Z(11)^2, 0*Z(11) ], [ Z(11), 0*Z(11) ],
 [ Z(11)^0, 0*Z(11) ], [ 0*Z(11), 0*Z(11) ] ]
</pre></div>

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

<h5>5.7-3 GenusCurve</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GenusCurve</code>( <var class="Arg">crv</var> )</td><td class="tdright">( function )</td></tr></table></div>
If <var class="Arg">crv</var> represents \(f(x,y)=0\), where \(f\) is a polynomial of degree \(d\), then this function simply returns \((d-1)(d-2)/2\). At the present, the function does not check if the curve is singular (in which case the result may be false).

<div class="example"><pre>
gap> q:=4;;
gap> F:=GF(q^2);;
gap> a:=Indeterminate(F, "a");;
gap> R1:=PolynomialRing(F,[a]);;
gap> var1:=IndeterminatesOfPolynomialRing(R1);;
gap> b:=Indeterminate(F, "b");;
gap> R2:=PolynomialRing(F,[a,b]);;
gap> var2:=IndeterminatesOfPolynomialRing(R2);;
gap> crv:=AffineCurve(b^q+b-a^(q+1),R2);
rec( polynomial := a^5+b^4+b, ring := GF(2^4)[a,b] )
gap> GenusCurve(crv);
6
</pre></div>

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

<h5>5.7-4 GOrbitPoint </h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GOrbitPoint </code>( <var class="Arg">G</var>, <var class="Arg">P</var> )</td><td class="tdright">( function )</td></tr></table></div>
<var class="Arg">P</var> must be a point in projective space \(\mathbb{P}^n(F)\), <var class="Arg">G</var> must be a finite subgroup of \(GL(n+1,F)\), This function returns all (representatives of projective) points in the orbit \(G\cdot P\).

The example below computes the orbit of the automorphism group on the Klein quartic over the field \(GF(43)\) on the ``point at infinity''.

<div class="example"><pre>
gap> R:= PolynomialRing( GF(43), 3 );;
gap> vars:= IndeterminatesOfPolynomialRing(R);;
gap> x:= vars[1];; y:= vars[2];; z:= vars[3];;
gap> zz:=Z(43)^6;
Z(43)^6
gap> zzz:=Z(43);
Z(43)
gap> rho1:=zz^0*[[zz^4,0,0],[0,zz^2,0],[0,0,zz]];
[ [ Z(43)^24, 0*Z(43), 0*Z(43) ], [ 0*Z(43), Z(43)^12, 0*Z(43) ],
 [ 0*Z(43), 0*Z(43), Z(43)^6 ] ]
gap> rho2:=zz^0*[[0,1,0],[0,0,1],[1,0,0]];
[ [ 0*Z(43), Z(43)^0, 0*Z(43) ], [ 0*Z(43), 0*Z(43), Z(43)^0 ],
 [ Z(43)^0, 0*Z(43), 0*Z(43) ] ]
gap> rho3:=(-1)*[[(zz-zz^6 )/zzz^7,( zz^2-zz^5 )/ zzz^7, ( zz^4-zz^3 )/ zzz^7],
> [( zz^2-zz^5 )/ zzz^7, ( zz^4-zz^3 )/ zzz^7, ( zz-zz^6 )/ zzz^7],
> [( zz^4-zz^3 )/ zzz^7, ( zz-zz^6 )/ zzz^7, ( zz^2-zz^5 )/ zzz^7]];
[ [ Z(43)^9, Z(43)^28, Z(43)^12 ], [ Z(43)^28, Z(43)^12, Z(43)^9 ],
 [ Z(43)^12, Z(43)^9, Z(43)^28 ] ]
gap> G:=Group([rho1,rho2,rho3]);; #PSL(2,7)
gap> Size(G);
168
gap> P:=[1,0,0]*zzz^0;
[ Z(43)^0, 0*Z(43), 0*Z(43) ]
gap> O:=GOrbitPoint(G,P);
[ [ Z(43)^0, 0*Z(43), 0*Z(43) ], [ 0*Z(43), Z(43)^0, 0*Z(43) ],
[ 0*Z(43), 0*Z(43), Z(43)^0 ], [ Z(43)^0, Z(43)^39, Z(43)^16 ],
[ Z(43)^0, Z(43)^33, Z(43)^28 ], [ Z(43)^0, Z(43)^27, Z(43)^40 ],
[ Z(43)^0, Z(43)^21, Z(43)^10 ], [ Z(43)^0, Z(43)^15, Z(43)^22 ],
[ Z(43)^0, Z(43)^9, Z(43)^34 ], [ Z(43)^0, Z(43)^3, Z(43)^4 ],
[ Z(43)^3, Z(43)^22, Z(43)^6 ], [ Z(43)^3, Z(43)^16, Z(43)^18 ],
[ Z(43)^3, Z(43)^10, Z(43)^30 ], [ Z(43)^3, Z(43)^4, Z(43)^0 ],
[ Z(43)^3, Z(43)^40, Z(43)^12 ], [ Z(43)^3, Z(43)^34, Z(43)^24 ],
[ Z(43)^3, Z(43)^28, Z(43)^36 ], [ Z(43)^4, Z(43)^30, Z(43)^27 ],
[ Z(43)^4, Z(43)^24, Z(43)^39 ], [ Z(43)^4, Z(43)^18, Z(43)^9 ],
[ Z(43)^4, Z(43)^12, Z(43)^21 ], [ Z(43)^4, Z(43)^6, Z(43)^33 ],
[ Z(43)^4, Z(43)^0, Z(43)^3 ], [ Z(43)^4, Z(43)^36, Z(43)^15 ] ]
gap> Length(O);
24
</pre></div>

Informally, a divisor on a curve is a formal integer linear combination of points on the curve, \(D=m_1P_1+...+m_kP_k\), where the \(m_i\) are integers (the ``multiplicity'' of \(P_i\) in \(D\)) and \(P_i\) are (\(F\)-rational) points on the affine plane curve. In other words, a divisor is an element of the free abelian group generated by the \(F\)-rational affine points on the curve. The support of a divisor \(D\) is simply the set of points which occurs in the sum defining \(D\) with non-zero ``multiplicity''. The data structure for a divisor on an affine plane curve is a record having the following components:

<ul>
<li>the coefficients (the integer weights of the points in the support),

</li>
<li>the support,

</li>
<li>the curve, itself a record which has components: polynomial and polynomial ring.

</li>
</ul>
<a id="X79742B7183051D99" name="X79742B7183051D99"></a>

<h5>5.7-5 DivisorOnAffineCurve</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DivisorOnAffineCurve</code>( <var class="Arg">cdiv</var>, <var class="Arg">sdiv</var>, <var class="Arg">crv</var> )</td><td class="tdright">( function )</td></tr></table></div>
This is the command you use to define a divisor in GUAVA. Of course, <var class="Arg">crv</var> is the curve on which the divisor lives, <var class="Arg">cdiv</var> is the list of coefficients (or ``multiplicities''), <var class="Arg">sdiv</var> is the list of points on <var class="Arg">crv</var> in the support.

<div class="example"><pre>
gap> q:=5;
5
gap> F:=GF(q);
GF(5)
gap> R:=PolynomialRing(F,2);;
gap> vars:=IndeterminatesOfPolynomialRing(R);
[ x, x_2 ]
gap> x:=vars[1];
x
gap> y:=vars[2];
x_2
gap> crv:=AffineCurve(y^3-x^3-x-1,R);
rec( polynomial := -x^3+x_2^3-x-Z(5)^0, ring := GF(5)[x,x_2] )
gap> Pts:=AffinePointsOnCurve(crv!.polynomial,R,F);;
gap> supp:=[Pts[1],Pts[2]];
[ [ 0*Z(5), Z(5)^0 ], [ Z(5)^0, Z(5) ] ]
gap> D:=DivisorOnAffineCurve([1,-1],supp,crv);
rec( coeffs := [ 1, -1 ],
 curve := rec( polynomial := -x^3+x_2^3-x-Z(5)^0, ring := GF(5)[x,x_2] ),
 support := [ [ Z(5)^0, Z(5)^0 ], [ Z(5)^0, Z(5) ] ] )
</pre></div>

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

<h5>5.7-6 DivisorAddition </h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DivisorAddition </code>( <var class="Arg">D1</var>, <var class="Arg">D2</var> )</td><td class="tdright">( function )</td></tr></table></div>
If \(D_1=m_1P_1+...+m_kP_k\) and \(D_2=n_1P_1+...+n_kP_k\) are divisors then \(D_1+D_2=(m_1+n_1)P_1+...+(m_k+n_k)P_k\).

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

<h5>5.7-7 DivisorDegree </h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DivisorDegree </code>( <var class="Arg">D</var> )</td><td class="tdright">( function )</td></tr></table></div>
If \(D=m_1P_1+...+m_kP_k\) is a divisor then the degree is \(m_1+...+m_k\).

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

<h5>5.7-8 DivisorNegate </h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DivisorNegate </code>( <var class="Arg">D</var> )</td><td class="tdright">( function )</td></tr></table></div>
Self-explanatory.

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

<h5>5.7-9 DivisorIsZero </h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DivisorIsZero </code>( <var class="Arg">D</var> )</td><td class="tdright">( function )</td></tr></table></div>
Self-explanatory.

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

<h5>5.7-10 DivisorsEqual </h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DivisorsEqual </code>( <var class="Arg">D1</var>, <var class="Arg">D2</var> )</td><td class="tdright">( function )</td></tr></table></div>
Self-explanatory.

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

<h5>5.7-11 DivisorGCD </h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DivisorGCD </code>( <var class="Arg">D1</var>, <var class="Arg">D2</var> )</td><td class="tdright">( function )</td></tr></table></div>
If \(m=p_1^{e_1}...p_k^{e_k}\) and \(n=p_1^{f_1}...p_k^{f_k}\) are two integers then their greatest common divisor is \(GCD(m,n)=p_1^{min(e_1,f_1)}...p_k^{min(e_k,f_k)}\). A similar definition works for two divisors on a curve. If \(D_1=e_1P_1+...+e_kP_k\) and \(D_2n=f_1P_1+...+f_kP_k\) are two divisors on a curve then their greatest common divisor is \(GCD(m,n)=min(e_1,f_1)P_1+...+min(e_k,f_k)P_k\). This function computes this quantity.

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

<h5>5.7-12 DivisorLCM </h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DivisorLCM </code>( <var class="Arg">D1</var>, <var class="Arg">D2</var> )</td><td class="tdright">( function )</td></tr></table></div>
If \(m=p_1^{e_1}...p_k^{e_k}\) and \(n=p_1^{f_1}...p_k^{f_k}\) are two integers then their least common multiple is \(LCM(m,n)=p_1^{max(e_1,f_1)}...p_k^{max(e_k,f_k)}\). A similar definition works for two divisors on a curve. If \(D_1=e_1P_1+...+e_kP_k\) and \(D_2=f_1P_1+...+f_kP_k\) are two divisors on a curve then their least common multiple is \(LCM(m,n)=max(e_1,f_1)P_1+...+max(e_k,f_k)P_k\). This function computes this quantity.

<div class="example"><pre>
gap> F:=GF(11);
GF(11)
gap> R1:=PolynomialRing(F,["a"]);;
gap> var1:=IndeterminatesOfPolynomialRing(R1);; a:=var1[1];;
gap> b:=X(F,"b",var1);
b
gap> var2:=Concatenation(var1,[b]);
[ a, b ]
gap> R2:=PolynomialRing(F,var2);
GF(11)[a,b]
gap> crvP1:=AffineCurve(b,R2);
rec( polynomial := b, ring := GF(11)[a,b] )
gap> div1:=DivisorOnAffineCurve([1,2,3,4],[Z(11)^2,Z(11)^3,Z(11)^7,Z(11)],crvP1);
rec( coeffs := [ 1, 2, 3, 4 ],
 curve := rec( polynomial := b, ring := GF(11)[a,b] ),
 support := [ Z(11)^2, Z(11)^3, Z(11)^7, Z(11) ] )
gap> DivisorDegree(div1);
10
gap> div2:=DivisorOnAffineCurve([1,2,3,4],[Z(11),Z(11)^2,Z(11)^3,Z(11)^4],crvP1);
rec( coeffs := [ 1, 2, 3, 4 ],
 curve := rec( polynomial := b, ring := GF(11)[a,b] ),
 support := [ Z(11), Z(11)^2, Z(11)^3, Z(11)^4 ] )
gap> DivisorDegree(div2);
10
gap> div3:=DivisorAddition(div1,div2);
rec( coeffs := [ 5, 3, 5, 4, 3 ],
 curve := rec( polynomial := b, ring := GF(11)[a,b] ),
 support := [ Z(11), Z(11)^2, Z(11)^3, Z(11)^4, Z(11)^7 ] )
gap> DivisorDegree(div3);
20
gap> DivisorIsEffective(div1);
true
gap> DivisorIsEffective(div2);
true
gap> ndiv1:=DivisorNegate(div1);
rec( coeffs := [ -1, -2, -3, -4 ],
 curve := rec( polynomial := b, ring := GF(11)[a,b] ),
 support := [ Z(11)^2, Z(11)^3, Z(11)^7, Z(11) ] )
gap> zdiv:=DivisorAddition(div1,ndiv1);
rec( coeffs := [ 0, 0, 0, 0 ],
 curve := rec( polynomial := b, ring := GF(11)[a,b] ),
 support := [ Z(11), Z(11)^2, Z(11)^3, Z(11)^7 ] )
gap> DivisorIsZero(zdiv);
true
gap> div_gcd:=DivisorGCD(div1,div2);
rec( coeffs := [ 1, 1, 2, 0, 0 ],
 curve := rec( polynomial := b, ring := GF(11)[a,b] ),
 support := [ Z(11), Z(11)^2, Z(11)^3, Z(11)^4, Z(11)^7 ] )
gap> div_lcm:=DivisorLCM(div1,div2);
rec( coeffs := [ 4, 2, 3, 4, 3 ],
 curve := rec( polynomial := b, ring := GF(11)[a,b] ),
 support := [ Z(11), Z(11)^2, Z(11)^3, Z(11)^4, Z(11)^7 ] )
gap> DivisorDegree(div_gcd);
4
gap> DivisorDegree(div_lcm);
16
gap> DivisorEqual(div3,DivisorAddition(div_gcd,div_lcm));
true
</pre></div>

Let \(G\) denote a finite subgroup of \(PGL(2,F)\) and let \(D\) denote a divisor on the projective line \(\mathbb{P}^1(F)\). If \(G\) leaves \(D\) unchanged (it may permute the points in the support of \(D\) but must preserve their sum in \(D\)) then the Riemann-Roch space \(L(D)\) is a \(G\)-module. The commands in this section help explore the \(G\)-module structure of \(L(D)\) in the case then the ground field \(F\) is finite.

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

<h5>5.7-13 RiemannRochSpaceBasisFunctionP1 </h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RiemannRochSpaceBasisFunctionP1 </code>( <var class="Arg">P</var>, <var class="Arg">k</var>, <var class="Arg">R2</var> )</td><td class="tdright">( function )</td></tr></table></div>
Input: <var class="Arg">R2</var> is a polynomial ring in two variables, say \(F[x,y]\); <var class="Arg">P</var> is an element of the base field, say \(F\); <var class="Arg">k</var> is an integer. Output: \(1/(x-P)^k\)

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

<h5>5.7-14 DivisorOfRationalFunctionP1 </h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DivisorOfRationalFunctionP1 </code>( <var class="Arg">f</var>, <var class="Arg">R</var> )</td><td class="tdright">( function )</td></tr></table></div>
Here \(R = F[x,y]\) is a polynomial ring in the variables \(x,y\) and \(f\) is a rational function of \(x\). Simply returns the principal divisor on \({\mathbb{P}}^1\) associated to \(f\).

<div class="example"><pre>

gap> F:=GF(11);
GF(11)
gap> R1:=PolynomialRing(F,["a"]);;
gap> var1:=IndeterminatesOfPolynomialRing(R1);; a:=var1[1];;
gap> b:=X(F,"b",var1);
b
gap> var2:=Concatenation(var1,[b]);
[ a, b ]
gap> R2:=PolynomialRing(F,var2);
GF(11)[a,b]
gap> pt:=Z(11);
Z(11)
gap> f:=RiemannRochSpaceBasisFunctionP1(pt,2,R2);
(Z(11)^0)/(a^2+Z(11)^7*a+Z(11)^2)
gap> Df:=DivisorOfRationalFunctionP1(f,R2);
rec( coeffs := [ -2 ], curve := rec( polynomial := a, ring := GF(11)[a,b] ),
 support := [ Z(11) ] )
gap> Df.support;
[ Z(11) ]
gap> F:=GF(11);;
gap> R:=PolynomialRing(F,2);;
gap> vars:=IndeterminatesOfPolynomialRing(R);;
gap> a:=vars[1];;
gap> b:=vars[2];;
gap> f:=(a^4+Z(11)^6*a^3-a^2+Z(11)^7*a+Z(11)^0)/(a^4+Z(11)*a^2+Z(11)^7*a+Z(11));;
gap> divf:=DivisorOfRationalFunctionP1(f,R);
rec( coeffs := [ 3, 1 ], curve := rec( polynomial := t, ring := GF(11)[t,x] ),
 support := [ Z(11), Z(11)^7 ] )
gap> denf:=DenominatorOfRationalFunction(f); RootsOfUPol(denf);
t^4+Z(11)*t^2+Z(11)^7*t+Z(11)
[ ]
gap> numf:=NumeratorOfRationalFunction(f); RootsOfUPol(numf);
t^4+Z(11)^6*t^3-t^2+Z(11)^7*t+Z(11)^0
[ Z(11)^7, Z(11), Z(11), Z(11) ]
</pre></div>

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

<h5>5.7-15 RiemannRochSpaceBasisP1 </h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RiemannRochSpaceBasisP1 </code>( <var class="Arg">D</var> )</td><td class="tdright">( function )</td></tr></table></div>
This returns the basis of the Riemann-Roch space \(L(D)\) associated to the divisor <var class="Arg">D</var> on the projective line \({\mathbb{P}}^1\).

<div class="example"><pre>
gap> F:=GF(11);
GF(11)
gap> R1:=PolynomialRing(F,["a"]);;
gap> var1:=IndeterminatesOfPolynomialRing(R1);; a:=var1[1];;
gap> b:=X(F,"b",var1);
b
gap> var2:=Concatenation(var1,[b]);
[ a, b ]
gap> R2:=PolynomialRing(F,var2);
GF(11)[a,b]
gap> crvP1:=AffineCurve(b,R2);
rec( polynomial := b, ring := GF(11)[a,b] )
gap> D:=DivisorOnAffineCurve([1,2,3,4],[Z(11)^2,Z(11)^3,Z(11)^7,Z(11)],crvP1);
rec( coeffs := [ 1, 2, 3, 4 ],
 curve := rec( polynomial := b, ring := GF(11)[a,b] ),
 support := [ Z(11)^2, Z(11)^3, Z(11)^7, Z(11) ] )
gap> B:=RiemannRochSpaceBasisP1(D);
[ (Z(11)^0)/(a+Z(11)^7), (Z(11)^0)/(a+Z(11)^8),
 (Z(11)^0)/(a^2+Z(11)^9*a+Z(11)^6), (Z(11)^0)/(a+Z(11)^2),
 (Z(11)^0)/(a^2+Z(11)^3*a+Z(11)^4), (Z(11)^0)/(a^3+a^2+Z(11)^2*a+Z(11)^6),
 (Z(11)^0)/(a+Z(11)^6), (Z(11)^0)/(a^2+Z(11)^7*a+Z(11)^2),
 (Z(11)^0)/(a^3+Z(11)^4*a^2+a+Z(11)^8),
 (Z(11)^0)/(a^4+Z(11)^8*a^3+Z(11)*a^2+a+Z(11)^4), Z(11)^0 ]
gap> DivisorOfRationalFunctionP1(B[1],R2).support;
[ ]
gap> DivisorOfRationalFunctionP1(B[2],R2).support;
[ Z(11)^2 ]
gap> DivisorOfRationalFunctionP1(B[3],R2).support;
[ Z(11)^3 ]
gap> DivisorOfRationalFunctionP1(B[4],R2).support;
[ Z(11)^3 ]
gap> DivisorOfRationalFunctionP1(B[5],R2).support;
[ Z(11)^7 ]
gap> DivisorOfRationalFunctionP1(B[6],R2).support;
[ Z(11)^7 ]
gap> DivisorOfRationalFunctionP1(B[7],R2).support;
[ Z(11)^7 ]
gap> DivisorOfRationalFunctionP1(B[8],R2).support;
[ Z(11) ]
gap> DivisorOfRationalFunctionP1(B[9],R2).support;
[ Z(11) ]
gap> DivisorOfRationalFunctionP1(B[10],R2).support;
[ Z(11) ]
gap> DivisorOfRationalFunctionP1(B[11],R2).support;
[ Z(11) ]
</pre></div>

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

<h5>5.7-16 MoebiusTransformation </h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MoebiusTransformation </code>( <var class="Arg">A</var>, <var class="Arg">R</var> )</td><td class="tdright">( function )</td></tr></table></div>
The arguments are a \(2\times 2\) matrix \(A\) with entries in a field \(F\) and a polynomial ring <var class="Arg">R</var>of one variable, say \(F[x]\). This function returns the linear fractional transformatio associated to <var class="Arg">A</var>. These transformations can be composed with each other using GAP's <code class="code">Value</code> command.

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

<h5>5.7-17 ActionMoebiusTransformationOnFunction </h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ActionMoebiusTransformationOnFunction </code>( <var class="Arg">A</var>, <var class="Arg">f</var>, <var class="Arg">R2</var> )</td><td class="tdright">( function )</td></tr></table></div>
The arguments are a \(2\times 2\) matrix \(A\) with entries in a field \(F\), a rational function <var class="Arg">f</var> of one variable, say in \(F(x)\), and a polynomial ring <var class="Arg">R2</var>, say \(F[x,y]\). This function simply returns the composition of the function <var class="Arg">f</var> with the Möbius transformation of <var class="Arg">A</var>.

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

<h5>5.7-18 ActionMoebiusTransformationOnDivisorP1 </h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ActionMoebiusTransformationOnDivisorP1 </code>( <var class="Arg">A</var>, <var class="Arg">D</var> )</td><td class="tdright">( function )</td></tr></table></div>
A Möbius transformation may be regarded as an automorphism of the projective line \(\mathbb{P}^1\). This function simply returns the image of the divisor <var class="Arg">D</var> under the Möbius transformation defined by <var class="Arg">A</var>, provided that <code class="code">IsActionMoebiusTransformationOnDivisorDefinedP1(A,D)</code> returns true.

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

<h5>5.7-19 IsActionMoebiusTransformationOnDivisorDefinedP1 </h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsActionMoebiusTransformationOnDivisorDefinedP1 </code>( <var class="Arg">A</var>, <var class="Arg">D</var> )</td><td class="tdright">( function )</td></tr></table></div>
Returns true of none of the points in the support of the divisor <var class="Arg">D</var> is the pole of the Möbius transformation.

<div class="example"><pre>
gap> F:=GF(11);
GF(11)
gap> R1:=PolynomialRing(F,["a"]);;
gap> var1:=IndeterminatesOfPolynomialRing(R1);; a:=var1[1];;
gap> b:=X(F,"b",var1);
b
gap> var2:=Concatenation(var1,[b]);
[ a, b ]
gap> R2:=PolynomialRing(F,var2);
GF(11)[a,b]
gap> crvP1:=AffineCurve(b,R2);
rec( polynomial := b, ring := GF(11)[a,b] )
gap> D:=DivisorOnAffineCurve([1,2,3,4],[Z(11)^2,Z(11)^3,Z(11)^7,Z(11)],crvP1);
rec( coeffs := [ 1, 2, 3, 4 ],
 curve := rec( polynomial := b, ring := GF(11)[a,b] ),
 support := [ Z(11)^2, Z(11)^3, Z(11)^7, Z(11) ] )
gap> A:=Z(11)^0*[[1,2],[1,4]];
[ [ Z(11)^0, Z(11) ], [ Z(11)^0, Z(11)^2 ] ]
gap> ActionMoebiusTransformationOnDivisorDefinedP1(A,D);
false
gap> A:=Z(11)^0*[[1,2],[3,4]];
[ [ Z(11)^0, Z(11) ], [ Z(11)^8, Z(11)^2 ] ]
gap> ActionMoebiusTransformationOnDivisorDefinedP1(A,D);
true
gap> ActionMoebiusTransformationOnDivisorP1(A,D);
rec( coeffs := [ 1, 2, 3, 4 ],
 curve := rec( polynomial := b, ring := GF(11)[a,b] ),
 support := [ Z(11)^5, Z(11)^6, Z(11)^8, Z(11)^7 ] )
gap> f:=MoebiusTransformation(A,R1);
(a+Z(11))/(Z(11)^8*a+Z(11)^2)
gap> ActionMoebiusTransformationOnFunction(A,f,R1);
-Z(11)^0+Z(11)^3*a^-1
</pre></div>

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

<h5>5.7-20 DivisorAutomorphismGroupP1 </h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DivisorAutomorphismGroupP1 </code>( <var class="Arg">D</var> )</td><td class="tdright">( function )</td></tr></table></div>
Input: A divisor <var class="Arg">D</var> on \(\mathbb{P}^1(F)\), where \(F\) is a finite field. Output: A subgroup \(Aut(D)\subset Aut(\mathbb{P}^1)\) preserving <var class="Arg">D</var>.

Very slow.

<div class="example"><pre>
gap> F:=GF(11);
GF(11)
gap> R1:=PolynomialRing(F,["a"]);;
gap> var1:=IndeterminatesOfPolynomialRing(R1);; a:=var1[1];;
gap> b:=X(F,"b",var1);
b
gap> var2:=Concatenation(var1,[b]);
[ a, b ]
gap> R2:=PolynomialRing(F,var2);
GF(11)[a,b]
gap> crvP1:=AffineCurve(b,R2);
rec( polynomial := b, ring := GF(11)[a,b] )
gap> D:=DivisorOnAffineCurve([1,2,3,4],[Z(11)^2,Z(11)^3,Z(11)^7,Z(11)],crvP1);
rec( coeffs := [ 1, 2, 3, 4 ],
 curve := rec( polynomial := b, ring := GF(11)[a,b] ),
 support := [ Z(11)^2, Z(11)^3, Z(11)^7, Z(11) ] )
gap> agp:=DivisorAutomorphismGroupP1(D);; #time; #Uncomment the call to "time;"" to see performance data
gap> IdGroup(agp);
[ 10, 2 ]
</pre></div>

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

<h5>5.7-21 MatrixRepresentationOnRiemannRochSpaceP1 </h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MatrixRepresentationOnRiemannRochSpaceP1 </code>( <var class="Arg">g</var>, <var class="Arg">D</var> )</td><td class="tdright">( function )</td></tr></table></div>
Input: An element <var class="Arg">g</var> in \(G\), a subgroup of \(Aut(D)\subset Aut(\mathbb{P}^1)\), and a divisor <var class="Arg">D</var> on \(\mathbb{P}^1(F)\), where \(F\) is a finite field. Output: a \(d\times d\) matrix, where \(d = dim\, L(D)\), representing the action of <var class="Arg">g</var> on \(L(D)\).

Note: <var class="Arg">g</var> sends \(L(D)\) to \(r\cdot L(D)\), where \(r\) is a polynomial of degree \(1\) depending on <var class="Arg">g</var> and <var class="Arg">D</var>.

Also very slow.

The GAP command <code class="code">BrauerCharacterValue</code> can be used to ``lift'' the eigenvalues of this matrix to the complex numbers.

<div class="example"><pre>
gap> F:=GF(11);
GF(11)
gap> R1:=PolynomialRing(F,["a"]);;
gap> var1:=IndeterminatesOfPolynomialRing(R1);; a:=var1[1];;
gap> b:=X(F,"b",var1);
b
gap> var2:=Concatenation(var1,[b]);
[ a, b ]
gap> R2:=PolynomialRing(F,var2);
GF(11)[a,b]
gap> crvP1:=AffineCurve(b,R2);
rec( polynomial := b, ring := GF(11)[a,b] )
gap> D:=DivisorOnAffineCurve([1,1,1,4],[Z(11)^2,Z(11)^3,Z(11)^7,Z(11)],crvP1);
rec( coeffs := [ 1, 1, 1, 4 ],
 curve := rec( polynomial := b, ring := GF(11)[a,b] ),
 support := [ Z(11)^2, Z(11)^3, Z(11)^7, Z(11) ] )
gap> agp:=DivisorAutomorphismGroupP1(D);; #time; #Uncomment the call to "time;"" to see performance data
gap> IdGroup(agp);
[ 20, 5 ]
gap> g:=Random(agp);
[ [ Z(11)^4, Z(11)^9 ], [ Z(11)^0, Z(11)^9 ] ]
gap> rho:=MatrixRepresentationOnRiemannRochSpaceP1(g,D);
[ [ Z(11)^0, 0*Z(11), 0*Z(11), 0*Z(11), 0*Z(11), 0*Z(11), 0*Z(11), 0*Z(11) ],
[ Z(11)^0, 0*Z(11), 0*Z(11), Z(11), 0*Z(11), 0*Z(11), 0*Z(11), 0*Z(11) ],
 [ Z(11)^7, 0*Z(11), Z(11)^5, 0*Z(11), 0*Z(11), 0*Z(11), 0*Z(11), 0*Z(11) ],
[ Z(11)^4, Z(11)^9, 0*Z(11), 0*Z(11), 0*Z(11), 0*Z(11), 0*Z(11), 0*Z(11) ],
 [ Z(11)^2, 0*Z(11), 0*Z(11), 0*Z(11), Z(11)^5, 0*Z(11), 0*Z(11), 0*Z(11) ],
[ Z(11)^4, 0*Z(11), 0*Z(11), 0*Z(11), Z(11)^8, Z(11)^0, 0*Z(11), 0*Z(11) ],
 [ Z(11)^6, 0*Z(11), 0*Z(11), 0*Z(11), Z(11)^7, Z(11)^0, Z(11)^5, 0*Z(11) ],
[ Z(11)^8, 0*Z(11), 0*Z(11), 0*Z(11), Z(11)^3, Z(11)^3, Z(11)^9, Z(11)^0 ] ]
gap> Display(rho);
 1 . . . . . . .
 1 . . 2 . . . .
 7 . 10 . . . . .
 5 6 . . . . . .
 4 . . . 10 . . .
 5 . . . 3 1 . .
 9 . . . 7 1 10 .
 3 . . . 8 8 6 1

</pre></div>

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

<h5>5.7-22 GoppaCodeClassical</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GoppaCodeClassical</code>( <var class="Arg">div</var>, <var class="Arg">pts</var> )</td><td class="tdright">( function )</td></tr></table></div>
Input: A divisor <var class="Arg">div</var> on the projective line \({\mathbb{P}}^1(F)\) over a finite field \(F\) and a list <var class="Arg">pts</var> of points \(\{P_1,...,P_n\}\subset F\) disjoint from the support of <var class="Arg">div</var>. Output: The classical (evaluation) Goppa code associated to this data. This is the code

\[
C=\{(f(P_1),...,f(P_n))\ |\ f\in L(D)_F\}.
\]

<div class="example"><pre>
gap> F:=GF(11);;
gap> R2:=PolynomialRing(F,2);;
gap> vars:=IndeterminatesOfPolynomialRing(R2);;
gap> a:=vars[1];;b:=vars[2];;
gap> cdiv:=[ 1, 2, -1, -2 ];
[ 1, 2, -1, -2 ]
gap> sdiv:=[ Z(11)^2, Z(11)^3, Z(11)^6, Z(11)^9 ];
[ Z(11)^2, Z(11)^3, Z(11)^6, Z(11)^9 ]
gap> crv:=rec(polynomial:=b,ring:=R2);
rec( polynomial := x, ring := GF(11)[t,x] )
gap> div:=DivisorOnAffineCurve(cdiv,sdiv,crv);
rec( coeffs := [ 1, 2, -1, -2 ],
 curve := rec( polynomial := x, ring := GF(11)[t,x] ),
 support := [ Z(11)^2, Z(11)^3, Z(11)^6, Z(11)^9 ] )
gap> pts:=Difference(Elements(GF(11)),div.support);
[ 0*Z(11), Z(11)^0, Z(11), Z(11)^4, Z(11)^5, Z(11)^7, Z(11)^8 ]
gap> C:=GoppaCodeClassical(div,pts);
a linear [7,2,1..6]4..5 code defined by generator matrix over GF(11)
gap> MinimumDistance(C);
6
</pre></div>

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

<h5>5.7-23 EvaluationBivariateCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EvaluationBivariateCode</code>( <var class="Arg">pts</var>, <var class="Arg">L</var>, <var class="Arg">crv</var> )</td><td class="tdright">( function )</td></tr></table></div>
Input: <code class="code">pts</code> is a set of affine points on <code class="code">crv</code>, <code class="code">L</code> is a list of rational functions on <code class="code">crv</code>. Output: The evaluation code associated to the points in <code class="code">pts</code> and functions in <code class="code">L</code>, but specifically for affine plane curves and this function checks if points are "bad" (if so removes them from the list <code class="code">pts</code> automatically). A point is ``bad'' if either it does not lie on the set of non-singular \(F\)-rational points (places of degree 1) on the curve.

Very similar to <code class="code">EvaluationCode</code> (see <code class="func">EvaluationCode</code> (<a href="chap5_mj.html#X78E078567D19D433">5.6-1</a>) for a more general construction).

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

<h5>5.7-24 EvaluationBivariateCodeNC</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EvaluationBivariateCodeNC</code>( <var class="Arg">pts</var>, <var class="Arg">L</var>, <var class="Arg">crv</var> )</td><td class="tdright">( function )</td></tr></table></div>
As in <code class="code">EvaluationBivariateCode</code> but does not check if the points are ``bad''.

Input: <code class="code">pts</code> is a set of affine points on <code class="code">crv</code>, <code class="code">L</code> is a list of rational functions on <code class="code">crv</code>. Output: The evaluation code associated to the points in <code class="code">pts</code> and functions in <code class="code">L</code>.

<div class="example"><pre>
gap> q:=4;;
gap> F:=GF(q^2);;
gap> R:=PolynomialRing(F,2);;
gap> vars:=IndeterminatesOfPolynomialRing(R);;
gap> x:=vars[1];;
gap> y:=vars[2];;
gap> crv:=AffineCurve(y^q+y-x^(q+1),R);
rec( polynomial := x^5+xx^4+xx, ring := GF(2^4)[x,xx] )
gap> L:=[ x^0, x, x^2*y^-1 ];
[ Z(2)^0, x, x^2/xx ]
gap> Pts:=AffinePointsOnCurve(crv.polynomial,crv.ring,F);;
gap> C1:=EvaluationBivariateCode(Pts,L,crv); #time; #Uncomment the call to "time;"" to see performance data

Automatically removed the following 'bad' points (either a pole or not on the\
curve):
[ [ 0*Z(2), 0*Z(2) ] ]

a linear [63,3,1..60]51..59 evaluation code over GF(16)
gap> P:=Difference(Pts,[[ 0*Z(2^4)^0, 0*Z(2)^0 ]]);;
gap> C2:=EvaluationBivariateCodeNC(P,L,crv); #time; #Uncomment the call to "time;"" to see performance data
a linear [63,3,1..60]51..59 evaluation code over GF(16)
gap> C3:=EvaluationCode(P,L,R); #time; #Uncomment the call to "time;"" to see performance data
a linear [63,3,1..56]51..59 evaluation code over GF(16)
gap> MinimumDistance(C1);
56
gap> MinimumDistance(C2);
56
gap> MinimumDistance(C3);
56
</pre></div>

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

<h5>5.7-25 OnePointAGCode</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OnePointAGCode</code>( <var class="Arg">f</var>, <var class="Arg">P</var>, <var class="Arg">m</var>, <var class="Arg">R</var> )</td><td class="tdright">( function )</td></tr></table></div>
Input: <var class="Arg">f</var> is a polynomial in R=F[x,y], where <var class="Arg">F</var> is a finite field, <var class="Arg">m</var> is a positive integer (the multiplicity of the `point at infinity' \(\infty\) on the curve \(f(x,y)=0\)), <var class="Arg">P</var> is a list of \(n\) points on the curve over \(F\). Output: The \(C\) which is the image of the evaluation map

\[
Eval_P:L(m \cdot \infty)\rightarrow F^n,
\]

given by \(f\longmapsto (f(p_1),...,f(p_n))\), where \(p_i \in P\). Here \(L(m \cdot \infty)\) denotes the Riemann-Roch space of the divisor \(m \cdot \infty\) on the curve. This has a basis consisting of monomials \(x^iy^j\), where \((i,j)\) range over a polygon depending on \(m\) and \(f(x,y)\). For more details on the Riemann-Roch space of the divisor \(m \cdot \infty\) see Proposition III.10.5 in Stichtenoth <a href="chapBib_mj.html#biBSt93">[Sti93]</a>.

This command returns a "record" object <code class="code">C</code> with several extra components (type <code class="code">NamesOfComponents(C)</code> to see them all): <code class="code">C!.points</code> (namely <var class="Arg">P</var>), <code class="code">C!.multiplicity</code> (namely <var class="Arg">m</var>), <code class="code">C!.curve</code> (namely <var class="Arg">f</var>) and <code class="code">C!.ring</code> (namely <var class="Arg">R</var>).

<div class="example"><pre>
gap> F:=GF(11);
GF(11)
gap> R := PolynomialRing(F,["x","y"]);
PolynomialRing(..., [ x, y ])
gap> indets := IndeterminatesOfPolynomialRing(R);
[ x, y ]
gap> x:=indets[1]; y:=indets[2];
x
y
gap> P:=AffinePointsOnCurve(y^2-x^11+x,R,F);;
gap> C:=OnePointAGCode(y^2-x^11+x,P,15,R);
a linear [11,8,1..0]2..3 one-point AG code over GF(11)
gap> MinimumDistance(C);
4
gap> Pts:=List([1,2,4,6,7,8,9,10,11],i->P[i]);;
gap> C:=OnePointAGCode(y^2-x^11+x,PT,10,R);
a linear [9,6,1..4]2..3 one-point AG code over GF(11)
gap> MinimumDistance(C);
4
</pre></div>

See <code class="func">EvaluationCode</code> (<a href="chap5_mj.html#X78E078567D19D433">5.6-1</a>) for a more general construction.

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

<h4>5.8 
Low-Density Parity-Check Codes
</h4>

Low-density parity-check (LDPC) codes form a class of linear block codes whose parity-check matrix--as the name implies, is sparse. LDPC codes were introduced by Robert Gallager in 1962 <a href="chapBib_mj.html#biBGallager.1962">[Gal62]</a> as his PhD work. Due to the decoding complexity for the technology back then, these codes were forgotten. Not until the late 1990s, these codes were rediscovered and research results have shown that LDPC codes can achieve near Shannon's capacity performance provided that their block length is long enough and soft-decision iterative decoder is employed. Note that the bit-flipping decoder (see <code class="code">BitFlipDecoder</code>) is a hard-decision decoder and hence capacity achieving performance cannot be achieved despite having a large block length.

Based on the structure of their parity-check matrix, LDPC codes may be categorised into two classes:

<ul>
<li>Regular LDPC codes

This class of codes has a fixed number of non zeros per column and per row in their parity-check matrix. These codes are usually denoted as \((n,j,k)\) codes where \(n\) is the block length, \(j\) is the number of non zeros per column in their parity-check matrix and \(k\) is the number of non zeros per row in their parity-check matrix.

</li>
<li>Irregular LDPC codes

The irregular codes, on the other hand, do not have a fixed number of non zeros per column and row in their parity-check matrix. This class of codes are commonly represented by two polynomials which denote the distribution of the number of non zeros in the columns and rows respectively of their parity-check matrix.

</li>
</ul>
<a id="X8020A9357AD0BA92" name="X8020A9357AD0BA92"></a>

<h5>5.8-1 QCLDPCCodeFromGroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ QCLDPCCodeFromGroup</code>( <var class="Arg">m</var>, <var class="Arg">j</var>, <var class="Arg">k</var> )</td><td class="tdright">( function )</td></tr></table></div>
<code class="code">QCLDPCCodeFromGroup</code> produces an \((n,j,k)\) regular quasi-cyclic LDPC code over GF(2) of block length \(n = mk\). The term quasi-cyclic in the context of LDPC codes typically refers to LDPC codes whose parity-check matrix \(H\) has the following form

<pre class="normal">

 - -
 | I_P(0,0) | I_P(0,1) | ... | I_P(0,k-1) |
 | I_P(1,0) | I_P(1,1) | ... | I_P(1,k-1) |
H = | . | . | . | . |,
 | . | . | . | . |
 | I_P(j-1,0) | I_P(j-1,1) | ... | I_P(j-1,k-1) |
 - -

</pre>

where \(I_{P(s,t)}\) is an identity matrix of size \(m \times m\) which has been shifted so that the \(1\) on the first row starts at position \(P(s,t)\).

Let \(F\) be a multiplicative group of integers modulo \(m\). If \(m\) is a prime, \(F=\{0,1,...,m-1\}\), otherwise \(F\) contains a set of integers which are relatively prime to \(m\). In both cases, the order of \(F\) is equal to \(\phi(m)\). Let \(a\) and \(b\) be non zeros of \(F\) such that the orders of \(a\) and \(b\) are \(k\) and \(j\) respectively. Note that the integers \(a\) and \(b\) can always be found provided that \(k\) and \(j\) respectively divide \(\phi(m)\). Having obtain integers \(a\) and \(b\), construct the following \(j \times k\) matrix \(P\) so that the element at row \(s\) and column \(t\) is given by \(P(s,t) = a^tb^s\), i.e.

<pre class="normal">

 - -
 | 1 | a | . . . | a^{k-1} |
 | b | ab | . . . | a^{k-1}b |
P = | . | . | . | . |.
 | . | . | . | . |
 | b^{j-1} | ab^{j-1} | . . . | a^{k-1}b^{j-1} |
 - -

</pre>

The parity-check matrix \(H\) of the LDPC code can be obtained by replacing each element of matrix \(P\), i.e. \(P(s,t)\), with an identity matrix \(I_{P(s,t)}\) of size \(m \times m\).

The code rate \(R\) of the constructed code is given by

\[
 R \geq 1 - \frac{j}{k}
\]

where the sign \(\geq\) is due to the possible existence of some non linearly independent rows in \(H\). For more details, refer to the paper by Tanner et al <a href="chapBib_mj.html#biBTSSFC04">[TSS+04]</a>.

<div class="example"><pre>
gap> C := QCLDPCCodeFromGroup(7,2,3);
a linear [21,8,1..6]5..10 low-density parity-check code over GF(2)
gap> MinimumWeight(C);
6
gap> # The quasi-cyclic structure is obvious from the check matrix
gap> Display( CheckMat(C) );
1 . . . . . . . 1 . . . . . . . . 1 . . .
. 1 . . . . . . . 1 . . . . . . . . 1 . .
. . 1 . . . . . . . 1 . . . . . . . . 1 .
. . . 1 . . . . . . . 1 . . . . . . . . 1
. . . . 1 . . . . . . . 1 . 1 . . . . . .
. . . . . 1 . . . . . . . 1 . 1 . . . . .
. . . . . . 1 1 . . . . . . . . 1 . . . .
. . . . . 1 . . . . . 1 . . . . 1 . . . .
. . . . . . 1 . . . . . 1 . . . . 1 . . .
1 . . . . . . . . . . . . 1 . . . . 1 . .
. 1 . . . . . 1 . . . . . . . . . . . 1 .
. . 1 . . . . . 1 . . . . . . . . . . . 1
. . . 1 . . . . . 1 . . . . 1 . . . . . .
. . . . 1 . . . . . 1 . . . . 1 . . . . .
gap> # This is the famous [155,64,20] quasi-cyclic LDPC codes
gap> C := QCLDPCCodeFromGroup(31,3,5);
a linear [155,64,1..24]24..77 low-density parity-check code over GF(2)
gap> # An example using non prime m, it may take a while to construct this code
gap> C := QCLDPCCodeFromGroup(356,4,8);
a linear [2848,1436,1..120]312..1412 low-density parity-check code over GF(2)
</pre></div>

<div class="chlinkprevnextbot"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap4_mj.html">[Previous Chapter]</a> <a href="chap6_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.74 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.