|
|
|
|
Quelle chap5.html
Sprache: HTML
|
|
| products/sources/formale Sprachen/GAP/pkg/guava/doc/chap5.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>
<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"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chap8.html">8</a> <a href="chap9.html">9</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap4.html">[Previous Chapter]</a> <a href="chap6.html">[Next Chapter]</a> </div>
<p id="mathjaxlink" class="pcenter"><a href="chap5_mj.html">[MathJax on]</a></p>
<p><a id="X87EB64ED831CCE99" name="X87EB64ED831CCE99"></a></p>
<div class="ChapSects"><a href="chap5.html#X87EB64ED831CCE99">5 <span class="Heading">Generating Codes</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap5.html#X86A92CB184CBD3C7">5.1 <span class="Heading">
Generating Unrestricted Codes
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X81AACBDD86E89D7D">5.1-1 ElementsCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X86755AAC83A0AF4B">5.1-2 HadamardCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X8122BA417F705997">5.1-3 ConferenceCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X81B7EE4279398F67">5.1-4 MOLSCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7D87DD6380B2CE69">5.1-5 RandomCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X816353397F25B62E">5.1-6 NordstromRobinsonCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7880D34485C60BAF">5.1-7 GreedyCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7C1B374583AFB923">5.1-8 LexiCode</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap5.html#X7A11F29F7BBF45BB">5.2 <span class="Heading">
Generating Linear Codes
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X83F400A681CFC0D6">5.2-1 GeneratorMatCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7CDDDFE47A10A008">5.2-2 CheckMatCodeMutable</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X848D3F7B805DEB66">5.2-3 CheckMatCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7DECB0A57C798583">5.2-4 HammingCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X801C88D578DA6ACA">5.2-5 ReedMullerCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X851592C7811D3D2A">5.2-6 AlternantCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7EE808BB7D1E487A">5.2-7 GoppaCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7F9C0A727EE075B7">5.2-8 GeneralizedSrivastavaCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7A38EB3178961F3E">5.2-9 SrivastavaCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X87F7CB8B7A8BE624">5.2-10 CordaroWagnerCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X865534267C8E902A">5.2-11 FerreroDesignCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7BCA10CE8660357F">5.2-12 RandomLinearCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X839CFE4C7A567D4D">5.2-13 OptimalityCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X871508567CB34D96">5.2-14 BestKnownLinearCode</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap5.html#X858721967BE44000">5.3 <span class="Heading">
Gabidulin Codes
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X79BE5D497CB2E59E">5.3-1 GabidulinCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X873950F67D4A9184">5.3-2 EnlargedGabidulinCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7F5BE77B7F343182">5.3-3 DavydovCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X845B4DBE83288D2D">5.3-4 TombakCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7D6583347C0D4292">5.3-5 EnlargedTombakCode</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap5.html#X81F6E4A785F368B0">5.4 <span class="Heading">
Golay Codes
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X80ED89C079CD0D09">5.4-1 BinaryGolayCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X84520C7983538806">5.4-2 ExtendedBinaryGolayCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7E0CCCD7866ADB94">5.4-3 TernaryGolayCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X81088A66816BCAE4">5.4-4 ExtendedTernaryGolayCode</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap5.html#X8366CC3685F0BC85">5.5 <span class="Heading">
Generating Cyclic Codes
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X853D34A5796CEB73">5.5-1 GeneratorPolCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X82440B78845F7F6E">5.5-2 CheckPolCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X818F0E6583E01D4B">5.5-3 RootsCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7C6BB07C87853C00">5.5-4 BCHCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X838F3CB3872CEF95">5.5-5 ReedSolomonCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X8730B90A862A3B3E">5.5-6 ExtendedReedSolomonCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X825F42F68179D2AB">5.5-7 QRCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X8764ABCF854C695E">5.5-8 QQRCodeNC</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7F4C3AD2795A8D7A">5.5-9 QQRCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7F3B8CC8831DA0E4">5.5-10 FireCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7BC245E37EB7B23F">5.5-11 WholeSpaceCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7B4EF2017B2C61AD">5.5-12 NullCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X83C5F8FE7827EAA7">5.5-13 RepetitionCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X82FA9F65854D98A6">5.5-14 CyclicCodes</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X8263CE4A790D294A">5.5-15 NrCyclicCodes</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X79826B16785E8BD3">5.5-16 QuasiCyclicCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7BFEDA52835A601D">5.5-17 CyclicMDSCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7F40AF3B81C252DC">5.5-18 FourNegacirculantSelfDualCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X87137A257E761291">5.5-19 FourNegacirculantSelfDualCodeNC</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap5.html#X850A28C579137220">5.6 <span class="Heading">
Evaluation Codes
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X78E078567D19D433">5.6-1 EvaluationCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X810AB3DB844FFCE9">5.6-2 GeneralizedReedSolomonCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X85B8699680B9D786">5.6-3 GeneralizedReedMullerCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7EE68B58872D7E82">5.6-4 ToricPoints</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7B24BE418010F596">5.6-5 ToricCode</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap5.html#X7AE2B2CD7C647990">5.7 <span class="Heading">
Algebraic geometric codes
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X802DD9FB79A9ACA7">5.7-1 AffineCurve</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X857EFE567C05C981">5.7-2 AffinePointsOnCurve</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X857E36ED814A40B8">5.7-3 GenusCurve</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X8572A3037DA66F88">5.7-4 GOrbitPoint </a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X79742B7183051D99">5.7-5 DivisorOnAffineCurve</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X8626E2B57D01F2DC">5.7-6 DivisorAddition </a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X865FE28D828C1EAD">5.7-7 DivisorDegree </a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X789DC358819A8F54">5.7-8 DivisorNegate </a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X8688C0E187B5C7DB">5.7-9 DivisorIsZero </a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X816A07997D9A7075">5.7-10 DivisorsEqual </a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X857B89847A649A26">5.7-11 DivisorGCD </a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X82231CF08073695F">5.7-12 DivisorLCM </a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X79C878697F99A10F">5.7-13 RiemannRochSpaceBasisFunctionP1 </a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X856DDA207EDDF256">5.7-14 DivisorOfRationalFunctionP1 </a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X878970A17E580224">5.7-15 RiemannRochSpaceBasisP1 </a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X807C52E67A440DEB">5.7-16 MoebiusTransformation </a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X85A0419580ED0391">5.7-17 ActionMoebiusTransformationOnFunction </a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7E48F9C67E7FB7B5">5.7-18 ActionMoebiusTransformationOnDivisorP1 </a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X79FD980E7B24DB9C">5.7-19 IsActionMoebiusTransformationOnDivisorDefinedP1 </a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X823386037F450B0E">5.7-20 DivisorAutomorphismGroupP1 </a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X80EDF3D682E7EF3F">5.7-21 MatrixRepresentationOnRiemannRochSpaceP1 </a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X8777388C7885E335">5.7-22 GoppaCodeClassical</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X8422A310854C09B0">5.7-23 EvaluationBivariateCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7B6C2BED8319C811">5.7-24 EvaluationBivariateCodeNC</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X842E227E8785168E">5.7-25 OnePointAGCode</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap5.html#X84F3673D7BBF5956">5.8 <span class="Heading">
Low-Density Parity-Check Codes
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X8020A9357AD0BA92">5.8-1 QCLDPCCodeFromGroup</a></span>
</div></div>
</div>
<h3>5 <span class="Heading">Generating Codes</span></h3>
<p>In this chapter we describe functions for generating codes.</p>
<p>Section <a href="chap5.html#X86A92CB184CBD3C7"><span class="RefLink">5.1</span></a> describes functions for generating unrestricted codes.</p>
<p>Section <a href="chap5.html#X7A11F29F7BBF45BB"><span class="RefLink">5.2</span></a> describes functions for generating linear codes.</p>
<p>Section <a href="chap5.html#X858721967BE44000"><span class="RefLink">5.3</span></a> describes functions for constructing certain covering codes, such as the Gabidulin codes.</p>
<p>Section <a href="chap5.html#X81F6E4A785F368B0"><span class="RefLink">5.4</span></a> describes functions for constructing the Golay codes.</p>
<p>Section <a href="chap5.html#X8366CC3685F0BC85"><span class="RefLink">5.5</span></a> describes functions for generating cyclic codes.</p>
<p>Section <a href="chap5.html#X850A28C579137220"><span class="RefLink">5.6</span></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.</p>
<p>Section <a href="chap5.html#X7AE2B2CD7C647990"><span class="RefLink">5.7</span></a> describes functions for generating algebraic geometry codes.</p>
<p>Section <a href="chap5.html#X84F3673D7BBF5956"><span class="RefLink">5.8</span></a> describes functions for constructing low-density parity-check (LDPC) codes.</p>
<p><a id="X86A92CB184CBD3C7" name="X86A92CB184CBD3C7"></a></p>
<h4>5.1 <span class="Heading">
Generating Unrestricted Codes
</span></h4>
<p>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.html#X81AACBDD86E89D7D"><span class="RefLink">5.1-1</span></a>), <code class="func">HadamardCode</code> (<a href="chap5.html#X86755AAC83A0AF4B"><span class="RefLink">5.1-2</span></a>), <code class="func">ConferenceCode</code> (<a href="chap5.html#X8122BA417F705997"><span class="RefLink">5.1-3</span></a>) and <code class="func">MOLSCode</code> (<a href="chap5.html#X81B7EE4279398F67"><span class="RefLink">5.1-4</span></a>)). These codes are unrestricted codes; they may later be discovered to be linear or cyclic.</p>
<p>The next functions generate random codes (see <code class="func">RandomCode</code> (<a href="chap5.html#X7D87DD6380B2CE69"><span class="RefLink">5.1-5</span></a>)) and the Nordstrom-Robinson code (see <code class="func">NordstromRobinsonCode</code> (<a href="chap5.html#X816353397F25B62E"><span class="RefLink">5.1-6</span></a>)), respectively.</p>
<p>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.html#X7880D34485C60BAF"><span class="RefLink">5.1-7</span></a>) and <code class="func">LexiCode</code> (<a href="chap5.html#X7C1B374583AFB923"><span class="RefLink">5.1-8</span></a>)).</p>
<p><a id="X81AACBDD86E89D7D" name="X81AACBDD86E89D7D"></a></p>
<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>
<p><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.</p>
<p>If <var class="Arg">L</var> contains a codeword more than once, it is removed from the list and a GAP set is returned.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">M := Z(3)^0 * [ [1, 0, 1, 1], [2, 2, 0, 0], [0, 1, 2, 2] ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">C := ElementsCode( M, "example code", GF(3) );</span>
a (4,3,1..4)2 example code over GF(3)
<span class="GAPprompt">gap></span> <span class="GAPinput">MinimumDistance( C );</span>
4
<span class="GAPprompt">gap></span> <span class="GAPinput">AsSSortedList( C );</span>
[ [ 0 1 2 2 ], [ 1 0 1 1 ], [ 2 2 0 0 ] ]
</pre></div>
<p><a id="X86755AAC83A0AF4B" name="X86755AAC83A0AF4B"></a></p>
<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>
<p>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>.</p>
<p>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 <span class="SimpleMath">t^th</span> kind from the Hadamard matrix <var class="Arg">H</var> In case only <var class="Arg">H</var> is given, <span class="SimpleMath">t = 3</span> is used.</p>
<p>By definition, a Hadamard matrix is a square matrix <var class="Arg">H</var> with <span class="SimpleMath">H⋅ H^T = -n⋅ I_n</span>, where <span class="SimpleMath">n</span> is the size of <var class="Arg">H</var>. The entries of <var class="Arg">H</var> are either 1 or -1.</p>
<p>The matrix <var class="Arg">H</var> is first transformed into a binary matrix <span class="SimpleMath">A_n</span> by replacing the <span class="SimpleMath">1</span>'s by 0's and the <span class="SimpleMath">-1</span>'s by 1s).
<p>The Hadamard matrix of the <em>first kind</em> (<span class="SimpleMath">t=1</span>) is created by using the rows of <span class="SimpleMath">A_n</span> as elements, after deleting the first column. This is a <span class="SimpleMath">(n-1, n, n/2)</span> code. We use this code for creating the Hadamard code of the <em>second kind</em> (<span class="SimpleMath">t=2</span>), by adding all the complements of the already existing codewords. This results in a <span class="SimpleMath">(n-1, 2n, n/2 -1)</span> code. The <em>third kind</em> (<span class="SimpleMath">t=3</span>) is created by using the rows of <span class="SimpleMath">A_n</span> (without cutting a column) and their complements as elements. This way, we have an <span class="SimpleMath">(n, 2n, n/2)</span>-code. The returned code is generally an unrestricted code, but for <span class="SimpleMath">n = 2^r</span>, the code is linear.</p>
<p>The command <code class="code">HadamardCode(n,t)</code> returns a Hadamard code with parameter <var class="Arg">n</var> of the <span class="SimpleMath">t^th</span> kind. For the command <code class="code">HadamardCode(n)</code>, <span class="SimpleMath">t=3</span> is used.</p>
<p>When called in these forms, <code class="code">HadamardCode</code> first creates a Hadamard matrix (see <code class="func">HadamardMat</code> (<a href="chap7.html#X8014A1F181ECD8AA"><span class="RefLink">7.3-4</span></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.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">H4 := [[1,1,1,1],[1,-1,1,-1],[1,1,-1,-1],[1,-1,-1,1]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">HadamardCode( H4, 1 );</span>
a (3,4,2)1 Hadamard code of order 4 over GF(2)
<span class="GAPprompt">gap></span> <span class="GAPinput">HadamardCode( H4, 2 );</span>
a (3,8,1)0 Hadamard code of order 4 over GF(2)
<span class="GAPprompt">gap></span> <span class="GAPinput">HadamardCode( H4 );</span>
a (4,8,2)1 Hadamard code of order 4 over GF(2)
<span class="GAPprompt">gap></span> <span class="GAPinput">H4 := [[1,1,1,1],[1,-1,1,-1],[1,1,-1,-1],[1,-1,-1,1]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">C := HadamardCode( 4 );</span>
a (4,8,2)1 Hadamard code of order 4 over GF(2)
<span class="GAPprompt">gap></span> <span class="GAPinput">C = HadamardCode( H4 );</span>
true
</pre></div>
<p><a id="X8122BA417F705997" name="X8122BA417F705997"></a></p>
<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>
<p><code class="code">ConferenceCode</code> returns a code of length <span class="SimpleMath">n-1</span> constructed from a symmetric 'conference matrix' <var class="Arg">H</var>. A <em>conference matrix</em> <var class="Arg">H</var> is a symmetric matrix of order <span class="SimpleMath">n</span>, which satisfies <span class="SimpleMath">H⋅ H^T = ((n-1)⋅ I</span>, with <span class="SimpleMath">n ≡ 2 mod 4</span>. The rows of <span class="SimpleMath">frac12(H+I+J)</span>, <span class="SimpleMath">frac12(-H+I+J)</span>, plus the zero and all-ones vectors form the elements of a binary non-linear <span class="SimpleMath">(n-1, 2n, (n-2)/2)</span> code.</p>
<p><strong class="pkg">GUAVA</strong> constructs a symmetric conference matrix of order <span class="SimpleMath">n+1</span> (<span class="SimpleMath">n≡ 1 mod 4</span>) and uses the rows of that matrix, plus the zero and all-ones vectors, to construct a binary non-linear <span class="SimpleMath">(n, 2(n+1), (n-1)/2)</span>-code.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">H6 := [[0,1,1,1,1,1],[1,0,1,-1,-1,1],[1,1,0,1,-1,-1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">[1,-1,1,0,1,-1],[1,-1,-1,1,0,1],[1,1,-1,-1,1,0]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">C1 := ConferenceCode( H6 );</span>
a (5,12,2)1..4 conference code over GF(2)
<span class="GAPprompt">gap></span> <span class="GAPinput">IsLinearCode( C1 );</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">C2 := ConferenceCode( 5 );</span>
a (5,12,2)1..4 conference code over GF(2)
<span class="GAPprompt">gap></span> <span class="GAPinput">AsSSortedList( C2 );</span>
[ [ 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>
<p><a id="X81B7EE4279398F67" name="X81B7EE4279398F67"></a></p>
<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>
<p><code class="code">MOLSCode</code> returns an <span class="SimpleMath">(n, q^2, n-1)</span> code over <span class="SimpleMath">GF(q)</span>. The code is created from <span class="SimpleMath">n-2</span> 'Mutually Orthogonal Latin Squares' (MOLS) of size <span class="SimpleMath">q × q</span>. The default for <var class="Arg">n</var> is <span class="SimpleMath">4</span>. <strong class="pkg">GUAVA</strong> can construct a MOLS code for <span class="SimpleMath">n-2 ≤ q</span>. Here <var class="Arg">q</var> must be a prime power, <span class="SimpleMath">q > 2</span>. If there are no <span class="SimpleMath">n-2</span> MOLS, an error is signalled.</p>
<p>Since each of the <span class="SimpleMath">n-2</span> MOLS is a <span class="SimpleMath">q× q</span> matrix, we can create a code of size <span class="SimpleMath">q^2</span> 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 <span class="SimpleMath">n</span>.</p>
<p>The MOLS codes are MDS codes (see <code class="func">IsMDSCode</code> (<a href="chap4.html#X789380D28018EC3F"><span class="RefLink">4.3-7</span></a>)).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">C1 := MOLSCode( 6, 5 );</span>
a (6,25,5)3..4 code generated by 4 MOLS of order 5 over GF(5)
<span class="GAPprompt">gap></span> <span class="GAPinput">mols := List( [1 .. WordLength(C1) - 2 ], function( nr )</span>
<span class="GAPprompt">></span> <span class="GAPinput"> local ls, el;</span>
<span class="GAPprompt">></span> <span class="GAPinput"> ls := NullMat( Size(LeftActingDomain(C1)), Size(LeftActingDomain(C1)) );</span>
<span class="GAPprompt">></span> <span class="GAPinput"> for el in VectorCodeword( AsSSortedList( C1 ) ) do</span>
<span class="GAPprompt">></span> <span class="GAPinput"> ls[IntFFE(el[1])+1][IntFFE(el[2])+1] := el[nr + 2];</span>
<span class="GAPprompt">></span> <span class="GAPinput"> od;</span>
<span class="GAPprompt">></span> <span class="GAPinput"> return ls;</span>
<span class="GAPprompt">></span> <span class="GAPinput"> end );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">AreMOLS( mols );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">C2 := MOLSCode( 11 );</span>
a (4,121,3)2 code generated by 2 MOLS of order 11 over GF(11)
</pre></div>
<p><a id="X7D87DD6380B2CE69" name="X7D87DD6380B2CE69"></a></p>
<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>
<p><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 <span class="SimpleMath">GF(q)^n</span>.</p>
<p>The function <code class="code">RandomLinearCode</code> returns a random linear code (see <code class="func">RandomLinearCode</code> (<a href="chap5.html#X7BCA10CE8660357F"><span class="RefLink">5.2-12</span></a>)).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">C1 := RandomCode( 6, 10, GF(8) );</span>
a (6,10,1..6)4..6 random unrestricted code over GF(8)
<span class="GAPprompt">gap></span> <span class="GAPinput">MinimumDistance(C1);</span>
2
<span class="GAPprompt">gap></span> <span class="GAPinput">C2 := RandomCode( 6, 10, GF(8) );</span>
a (6,10,1..6)4..6 random unrestricted code over GF(8)
<span class="GAPprompt">gap></span> <span class="GAPinput">C1 = C2;</span>
false
</pre></div>
<p><a id="X816353397F25B62E" name="X816353397F25B62E"></a></p>
<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>
<p><code class="code">NordstromRobinsonCode</code> returns a Nordstrom-Robinson code, the best code with word length <span class="SimpleMath">n=16</span> and minimum distance <span class="SimpleMath">d=6</span> over <span class="SimpleMath">GF(2)</span>. This is a non-linear <span class="SimpleMath">(16, 256, 6)</span> code.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">C := NordstromRobinsonCode();</span>
a (16,256,6)4 Nordstrom-Robinson code over GF(2)
<span class="GAPprompt">gap></span> <span class="GAPinput">OptimalityCode( C );</span>
0
</pre></div>
<p><a id="X7880D34485C60BAF" name="X7880D34485C60BAF"></a></p>
<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>
<p><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>.</p>
<p>Greedy codes are often linear codes.</p>
<p>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.html#X7C1B374583AFB923"><span class="RefLink">5.1-8</span></a>)).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">C1 := GreedyCode( Tuples( AsSSortedList( GF(2) ), 5 ), 3, GF(2) );</span>
a (5,4,3..5)2 Greedy code, user defined basis over GF(2)
<span class="GAPprompt">gap></span> <span class="GAPinput">C2 := GreedyCode( Permuted( Tuples( AsSSortedList( GF(2) ), 5 ),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> (1,4) ), 3, GF(2) );</span>
a (5,4,3..5)2 Greedy code, user defined basis over GF(2)
<span class="GAPprompt">gap></span> <span class="GAPinput">C1 = C2;</span>
false
</pre></div>
<p><a id="X7C1B374583AFB923" name="X7C1B374583AFB923"></a></p>
<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>
<p>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>.</p>
<p>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>.</p>
<p>Note that binary lexicodes are always linear.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">C := LexiCode( 4, 3, GF(5) );</span>
a (4,17,3..4)2..4 lexicode over GF(5)
<span class="GAPprompt">gap></span> <span class="GAPinput">B := [ [Z(2)^0, 0*Z(2), 0*Z(2)], [Z(2)^0, Z(2)^0, 0*Z(2)] ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">C := LexiCode( B, 2, GF(2) );</span>
a linear [3,1,2]1..2 lexicode over GF(2)
</pre></div>
<p>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.html#X7880D34485C60BAF"><span class="RefLink">5.1-7</span></a>)).</p>
<p><a id="X7A11F29F7BBF45BB" name="X7A11F29F7BBF45BB"></a></p>
<h4>5.2 <span class="Heading">
Generating Linear Codes
</span></h4>
<p>In this section we describe functions for constructing linear codes. A linear code always has a generator or check matrix.</p>
<p>The first two functions generate linear codes from the generator matrix (<code class="func">GeneratorMatCode</code> (<a href="chap5.html#X83F400A681CFC0D6"><span class="RefLink">5.2-1</span></a>)) or check matrix (<code class="func">CheckMatCode</code> (<a href="chap5.html#X848D3F7B805DEB66"><span class="RefLink">5.2-3</span></a>)). All linear codes can be constructed with these functions.</p>
<p>The next functions we describe generate some well-known codes, like Hamming codes (<code class="func">HammingCode</code> (<a href="chap5.html#X7DECB0A57C798583"><span class="RefLink">5.2-4</span></a>)), Reed-Muller codes (<code class="func">ReedMullerCode</code> (<a href="chap5.html#X801C88D578DA6ACA"><span class="RefLink">5.2-5</span></a>)) and the extended Golay codes (<code class="func">ExtendedBinaryGolayCode</code> (<a href="chap5.html#X84520C7983538806"><span class="RefLink">5.4-2</span></a>) and <code class="func">ExtendedTernaryGolayCode</code> (<a href="chap5.html#X81088A66816BCAE4"><span class="RefLink">5.4-4</span></a>)).</p>
<p>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.html#X851592C7811D3D2A"><span class="RefLink">5.2-6</span></a>), <code class="func">GoppaCode</code> (<a href="chap5.html#X7EE808BB7D1E487A"><span class="RefLink">5.2-7</span></a>), <code class="func">GeneralizedSrivastavaCode</code> (<a href="chap5.html#X7F9C0A727EE075B7"><span class="RefLink">5.2-8</span></a>) and <code class="func">SrivastavaCode</code> (<a href="chap5.html#X7A38EB3178961F3E"><span class="RefLink">5.2-9</span></a>)).</p>
<p>Finally, we describe a function for generating random linear codes (see <code class="func">RandomLinearCode</code> (<a href="chap5.html#X7BCA10CE8660357F"><span class="RefLink">5.2-12</span></a>)).</p>
<p><a id="X83F400A681CFC0D6" name="X83F400A681CFC0D6"></a></p>
<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>
<p><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 <span class="SimpleMath">n</span>, dimension <span class="SimpleMath">k</span> if <var class="Arg">G</var> is a <span class="SimpleMath">k × n</span>-matrix. If <span class="SimpleMath">GF(q)</span> is the field of the code, the size of the code will be <span class="SimpleMath">q^k</span>.</p>
<p>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.html#X817224657C9829C4"><span class="RefLink">4.7-1</span></a>)).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">G := Z(3)^0 * [[1,0,1,2,0],[0,1,2,1,1],[0,0,1,2,1]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">C1 := GeneratorMatCode( G, GF(3) );</span>
a linear [5,3,1..2]1..2 code defined by generator matrix over GF(3)
<span class="GAPprompt">gap></span> <span class="GAPinput">C2 := GeneratorMatCode( IdentityMat( 5, GF(2) ), GF(2) );</span>
a linear [5,5,1]0 code defined by generator matrix over GF(2)
<span class="GAPprompt">gap></span> <span class="GAPinput">GeneratorMatCode( List( AsSSortedList( NordstromRobinsonCode() ),</span>
<span class="GAPprompt">></span> <span class="GAPinput">x -> VectorCodeword( x ) ), GF( 2 ) ); # This is the smallest linear code that contains the N-R code </span>
a linear [16,11,1..4]2 code defined by generator matrix over GF(2)
</pre></div>
<p><a id="X7CDDDFE47A10A008" name="X7CDDDFE47A10A008"></a></p>
<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>
<p><code class="code">CheckMatCodeMutable</code> is the same as <code class="code">CheckMatCode</code> except that the check matrix and generator matrix are mutable.</p>
<p><a id="X848D3F7B805DEB66" name="X848D3F7B805DEB66"></a></p>
<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>
<p><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, <span class="SimpleMath">c⋅ H^T = 0</span> where <span class="SimpleMath">c</span> is an element of the code. If <var class="Arg">H</var> is a <span class="SimpleMath">r× n</span>-matrix, the code has word length <span class="SimpleMath">n</span>, redundancy <span class="SimpleMath">r</span> and dimension <span class="SimpleMath">n-r</span>.</p>
<p>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.html#X85D4B26E7FB38D57"><span class="RefLink">4.7-2</span></a>)).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">G := Z(3)^0 * [[1,0,1,2,0],[0,1,2,1,1],[0,0,1,2,1]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">C1 := CheckMatCode( G, GF(3) );</span>
a linear [5,2,1..2]2..3 code defined by check matrix over GF(3)
<span class="GAPprompt">gap></span> <span class="GAPinput">CheckMat(C1);</span>
[ [ 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 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">C2 := CheckMatCode( IdentityMat( 5, GF(2) ), GF(2) );</span>
a cyclic [5,0,5]5 code defined by check matrix over GF(2)
</pre></div>
<p><a id="X7DECB0A57C798583" name="X7DECB0A57C798583"></a></p>
<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>
<p><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.html#X7A42FF7D87FC34AC"><span class="RefLink">4.10-1</span></a>)) makes use of this property.</p>
<p>If <span class="SimpleMath">q</span> is the size of its field <var class="Arg">F</var>, the returned Hamming code is a linear <span class="SimpleMath">[(q^r-1)/(q-1), (q^r-1)/(q-1) - r, 3]</span> code.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">C1 := HammingCode( 4, GF(2) );</span>
a linear [15,11,3]1 Hamming (4,2) code over GF(2)
<span class="GAPprompt">gap></span> <span class="GAPinput">C2 := HammingCode( 3, GF(9) );</span>
a linear [91,88,3]1 Hamming (3,9) code over GF(9)
</pre></div>
<p><a id="X801C88D578DA6ACA" name="X801C88D578DA6ACA"></a></p>
<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>
<p><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 <span class="SimpleMath">2^k</span> and minimum distance <span class="SimpleMath">2^k-r</span> (see for example, section 1.10 in <a href="chapBib.html#biBHP03">[HP03]</a>). By definition, the <span class="SimpleMath">r^th</span> order binary Reed-Muller code of length <span class="SimpleMath">n=2^m</span>, for <span class="SimpleMath">0 ≤ r ≤ m</span>, is the set of all vectors <span class="SimpleMath">f</span>, where <span class="SimpleMath">f</span> is a Boolean function which is a polynomial of degree at most <span class="SimpleMath">r</span>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">ReedMullerCode( 1, 3 );</span>
a linear [8,4,4]2 Reed-Muller (1,3) code over GF(2)
</pre></div>
<p>See <code class="func">GeneralizedReedMullerCode</code> (<a href="chap5.html#X85B8699680B9D786"><span class="RefLink">5.6-3</span></a>) for a more general construction.</p>
<p><a id="X851592C7811D3D2A" name="X851592C7811D3D2A"></a></p>
<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>
<p><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 <span class="SimpleMath">H=([a_i^j y_i])</span>, where <span class="SimpleMath">0 ≤ j≤ r-1</span>, <span class="SimpleMath">1 ≤ i≤ n</span>, and where <span class="SimpleMath">[...]</span> is as in <code class="func">VerticalConversionFieldMat</code> (<a href="chap7.html#X7B68119F85E9EC6D"><span class="RefLink">7.3-9</span></a>)). If no <var class="Arg">alpha</var> is specified, the vector <span class="SimpleMath">[1, a, a^2, .., a^n-1]</span> is used, where <span class="SimpleMath">a</span> is a primitive element of a Galois field <var class="Arg">F</var>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Y := [ 1, 1, 1, 1, 1, 1, 1];; a := PrimitiveUnityRoot( 2, 7 );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">alpha := List( [0..6], i -> a^i );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">C := AlternantCode( 2, Y, alpha, GF(8) );</span>
a linear [7,3,3..4]3..4 alternant code over GF(8)
</pre></div>
<p><a id="X7EE808BB7D1E487A" name="X7EE808BB7D1E487A"></a></p>
<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>
<p><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 <span class="SimpleMath">GF(q)</span>. <var class="Arg">L</var> must be a list of elements in <span class="SimpleMath">GF(q)</span>, 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 <span class="SimpleMath">H=([a_i^j / G(a_i)])_0 ≤ j ≤ deg(g)-1, a_i ∈ L</span>, where <span class="SimpleMath">a_i∈ L</span> and <span class="SimpleMath">[...]</span> is as in <code class="func">VerticalConversionFieldMat</code> (<a href= | | |
