|
|
|
|
Quellcode-Bibliothek chap4.html
Sprache: HTML
|
|
| products/sources/formale Sprachen/GAP/pkg/guava/doc/chap4.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 4: Codes</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap4" onload="jscontent()">
<div class="chlinktop"><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="chap3.html">[Previous Chapter]</a> <a href="chap5.html">[Next Chapter]</a> </div>
<p id="mathjaxlink" class="pcenter"><a href="chap4_mj.html">[MathJax on]</a></p>
<p><a id="X85FDDF0B7B7D87FB" name="X85FDDF0B7B7D87FB"></a></p>
<div class="ChapSects"><a href="chap4.html#X85FDDF0B7B7D87FB">4 <span class="Heading">Codes</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4.html#X7ECE60E1873B49A6">4.1 <span class="Heading">Comparisons of Codes</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X8686D5FA839F1A3D"><code>4.1-1 \=</code></a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4.html#X832DA51986A3882C">4.2 <span class="Heading">
Operations for Codes
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X82E2E5127CD25168"><code>4.2-1 \+</code></a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7EFA08EE7BA22261"><code>4.2-2 \*</code></a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X84D8B18F7C494A58"><code>4.2-3 \*</code></a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X8744BA5E78BCF3F9">4.2-4 InformationWord</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4.html#X864091AA7D4AFE86">4.3 <span class="Heading">
Boolean Functions for Codes
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X87BDB89B7AAFE8AD">4.3-1 in</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X79CA175481F8105F">4.3-2 IsSubset</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7F71186281DEA83A">4.3-3 IsCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7B24748A7CE8D4B9">4.3-4 IsLinearCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X850C23D07C9A9B19">4.3-5 IsCyclicCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X85E3BD26856424F7">4.3-6 IsPerfectCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X789380D28018EC3F">4.3-7 IsMDSCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X80166D8D837FEB58">4.3-8 IsSelfDualCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7B2A0CC481D2366F">4.3-9 IsSelfOrthogonalCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X8358D43981EBE970">4.3-10 IsDoublyEvenCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X79ACAEF5865414A0">4.3-11 IsSinglyEvenCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7CE150ED7C3DC455">4.3-12 IsEvenCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7B6DB8CC84FCAC1C">4.3-13 IsSelfComplementaryCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7AFD3844859B20BF">4.3-14 IsAffineCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X861D32FB81EF0D77">4.3-15 IsAlmostAffineCode</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4.html#X86442DCD7A0B2146">4.4 <span class="Heading">
Equivalence and Isomorphism of Codes
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X843034687D9C75B0">4.4-1 IsEquivalent</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X874DED8E86BC180B">4.4-2 CodeIsomorphism</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X87677B0787B4461A">4.4-3 AutomorphismGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X79F3261F86C29F6D">4.4-4 PermutationAutomorphismGroup</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4.html#X866EB39483DDAE72">4.5 <span class="Heading">
Domain Functions for Codes
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X808A4061809A6E67">4.5-1 IsFinite</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X858ADA3B7A684421">4.5-2 Size</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X86F070E0807DC34E">4.5-3 LeftActingDomain</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7E6926C6850E7C4E">4.5-4 Dimension</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X856D927378C33548">4.5-5 AsSSortedList</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4.html#X823827927D6A8235">4.6 <span class="Heading">
Printing and Displaying Codes
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7AFA64D97A1F39A3">4.6-1 Print</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X81FB5BE27903EC32">4.6-2 String</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X83A5C59278E13248">4.6-3 Display</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7CD08C8C780543C4">4.6-4 DisplayBoundsInfo</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4.html#X7D0F48B685A3ECDD">4.7 <span class="Heading">
Generating (Check) Matrices and Polynomials
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X817224657C9829C4">4.7-1 GeneratorMat</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X85D4B26E7FB38D57">4.7-2 CheckMat</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X78E33C3A843B0261">4.7-3 GeneratorPol</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7C45AA317BB1195F">4.7-4 CheckPol</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7F4CB9DB7CD97178">4.7-5 RootsOfCode</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4.html#X8170B52D7C154247">4.8 <span class="Heading">
Parameters of Codes
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7A36C3C67B0062E8">4.8-1 WordLength</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7E33FD56792DBF3D">4.8-2 Redundancy</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7B31613D8538BD29">4.8-3 MinimumDistance</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X813F226F855590EE">4.8-4 MinimumDistanceLeon</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X84EDF67B86B4154C">4.8-5 MinimumWeight</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X823B9A797EE42F6D">4.8-6 DecreaseMinimumDistanceUpperBound</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7A679B0A7816B030">4.8-7 MinimumDistanceRandom</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7A195E317D2AB7CE">4.8-8 CoveringRadius</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X81004B007EC5DF58">4.8-9 SetCoveringRadius</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4.html#X806384B4815EFF2E">4.9 <span class="Heading">
Distributions
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7AEE64467FB1E0B9">4.9-1 MinimumWeightWords</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X8728BCC9842A6E5D">4.9-2 WeightDistribution</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X871FD301820717A4">4.9-3 InnerDistribution</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X87AD54F87C5EE77E">4.9-4 DistancesDistribution</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X8495870687195324">4.9-5 OuterDistribution</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4.html#X7D9A39BF801948C8">4.10 <span class="Heading">
Decoding Functions
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7A42FF7D87FC34AC">4.10-1 Decode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7D870C9387C47D9F">4.10-2 Decodeword</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7D48DE2A84474C6A">4.10-3 GeneralizedReedSolomonDecoderGao</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7CFF98D483502053">4.10-4 GeneralizedReedSolomonListDecoder</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X80E17FA27DCAB676">4.10-5 BitFlipDecoder</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7B88DEB37F28404A">4.10-6 NearestNeighborGRSDecodewords</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X825E35757D778787">4.10-7 NearestNeighborDecodewords</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7D02E0FE8735D3E6">4.10-8 Syndrome</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7B9E71987E4294A7">4.10-9 SyndromeTable</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X8642D0BD789DA9B5">4.10-10 StandardArray</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X83231E717CCB0247">4.10-11 PermutationDecode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X85B692177E2A745D">4.10-12 PermutationDecodeNC</a></span>
</div></div>
</div>
<h3>4 <span class="Heading">Codes</span></h3>
<p>A <em>code</em> is a set of codewords (recall a codeword in <strong class="pkg">GUAVA</strong> is simply a sequence of elements of a finite field <span class="SimpleMath">GF(q)</span>, where <span class="SimpleMath">q</span> is a prime power). We call these the <em>elements</em> of the code. Depending on the type of code, a codeword can be interpreted as a vector or as a polynomial. This is explained in more detail in Chapter <a href="chap3.html#X836BAA9A7EBD08B1"><span class="RefLink">3.</span></a>.</p>
<p>In <strong class="pkg">GUAVA</strong>, codes can be a set specified by its elements (this will be called an <em>unrestricted code</em>), by a generator matrix listing a set of basis elements (for a linear code) or by a generator polynomial (for a cyclic code).</p>
<p>Any code can be defined by its elements. If you like, you can give the code a name.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">C := ElementsCode(["1100", "1010", "0001"], "example code", GF(2) );</span>
a (4,3,1..4)2..4 example code over GF(2)
</pre></div>
<p>An <span class="SimpleMath">(n,M,d)</span> code is a code with word <em>length</em> <span class="SimpleMath">n</span>, <em>size</em> <span class="SimpleMath">M</span> and <em>minimum distance</em> <span class="SimpleMath">d</span>. If the minimum distance has not yet been calculated, the lower bound and upper bound are printed (except in the case where the code is a random linear codes, where these are not printed for efficiency reasons). So</p>
<pre class="normal">
a (4,3,1..4)2..4 code over GF(2)
</pre>
<p>means a binary unrestricted code of length <span class="SimpleMath">4</span>, with <span class="SimpleMath">3</span> elements and the minimum distance is greater than or equal to <span class="SimpleMath">1</span> and less than or equal to <span class="SimpleMath">4</span> and the covering radius is greater than or equal to <span class="SimpleMath">2</span> and less than or equal to <span class="SimpleMath">4</span>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">C := ElementsCode(["1100", "1010", "0001"], "example code", GF(2) );</span>
a (4,3,1..4)2..4 example code over GF(2)
<span class="GAPprompt">gap></span> <span class="GAPinput">MinimumDistance(C);</span>
2
<span class="GAPprompt">gap></span> <span class="GAPinput">C;</span>
a (4,3,2)2..4 example code over GF(2)
</pre></div>
<p>If the set of elements is a linear subspace of <span class="SimpleMath">GF(q)^n</span>, the code is called <em>linear</em>. If a code is linear, it can be defined by its <em>generator matrix</em> or <em>parity check matrix</em>. By definition, the rows of the generator matrix is a basis for the code (as a vector space over <span class="SimpleMath">GF(q)</span>). By definition, the rows of the parity check matrix is a basis for the dual space of the code,</p>
<p class="pcenter">
C^* = \{ v \in GF(q)^n\ |\ v\cdot c = 0,\ for \ all\ c \in C \}.
</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">G := GeneratorMatCode([[1,0,1],[0,1,2]], "demo code", GF(3) );</span>
a linear [3,2,1..2]1 demo code over GF(3)
</pre></div>
<p>So a linear <span class="SimpleMath">[n, k, d]r</span> code is a code with word <em>length</em> <span class="SimpleMath">n</span>, <em>dimension</em> <span class="SimpleMath">k</span>, <em>minimum distance</em> <span class="SimpleMath">d</span> and <em>covering radius</em> <span class="SimpleMath">r</span>.</p>
<p>If the code is linear and all cyclic shifts of its codewords (regarded as <span class="SimpleMath">n</span>-tuples) are again codewords, the code is called <em>cyclic</em>. All elements of a cyclic code are multiples of the monic polynomial modulo a polynomial <span class="SimpleMath">x^n -1</span>, where <span class="SimpleMath">n</span> is the word length of the code. Such a polynomial is called a <em>generator polynomial</em> The generator polynomial must divide <span class="SimpleMath">x^n-1</span> and its quotient is called a <em>check polynomial</em>. Multiplying a codeword in a cyclic code by the check polynomial yields zero (modulo the polynomial <span class="SimpleMath">x^n -1</span>). In <strong class="pkg">GUAVA</strong>, a cyclic code can be defined by either its generator polynomial or check polynomial.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">G := GeneratorPolCode(Indeterminate(GF(2))+Z(2)^0, 7, GF(2) );</span>
a cyclic [7,6,1..2]1 code defined by generator polynomial over GF(2)
</pre></div>
<p>It is possible that <strong class="pkg">GUAVA</strong> does not know that an unrestricted code is in fact linear. This situation occurs for example when a code is generated from a list of elements with the function <code class="code">ElementsCode</code> (see <code class="func">ElementsCode</code> (<a href="chap5.html#X81AACBDD86E89D7D"><span class="RefLink">5.1-1</span></a>)). By calling the function <code class="code">IsLinearCode</code> (see <code class="func">IsLinearCode</code> (<a href="chap4.html#X7B24748A7CE8D4B9"><span class="RefLink">4.3-4</span></a>)), <strong class="pkg">GUAVA</strong> tests if the code can be represented by a generator matrix. If so, the code record and the operations are converted accordingly.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">L := Z(2)*[ [0,0,0], [1,0,0], [0,1,1], [1,1,1] ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">C := ElementsCode( L, GF(2) );</span>
a (3,4,1..3)1 user defined unrestricted code over GF(2)
# so far, GUAVA does not know what kind of code this is
<span class="GAPprompt">gap></span> <span class="GAPinput">IsLinearCode( C );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">C;</span>
a linear [3,2,1]1 user defined unrestricted code over GF(2)
</pre></div>
<p>Of course the same holds for unrestricted codes that in fact are cyclic, or codes, defined by a generator matrix, that actually are cyclic.</p>
<p>Codes are printed simply by giving a small description of their parameters, the word length, size or dimension and perhaps the minimum distance, followed by a short description and the base field of the code. The function <code class="code">Display</code> gives a more detailed description, showing the construction history of the code.</p>
<p><strong class="pkg">GUAVA</strong> doesn't place much emphasis on the actual encoding and decoding processes; some algorithms have been included though. Encoding works simply by multiplying an information vector with a code, decoding is done by the functions Decode or Decodeword. For more information about encoding and decoding, see sections 4.2 and 4.10-1.
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">R := ReedMullerCode( 1, 3 );</span>
a linear [8,4,4]2 Reed-Muller (1,3) code over GF(2)
<span class="GAPprompt">gap></span> <span class="GAPinput">w := [ 1, 0, 1, 1 ] * R;</span>
[ 1 0 0 1 1 0 0 1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Decode( R, w );</span>
[ 1 0 1 1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Decode( R, w + "10000000" ); # One error at the first position. Corrected by Guava.</span>
[ 1 0 1 1 ]
</pre></div>
<p>Sections <a href="chap4.html#X7ECE60E1873B49A6"><span class="RefLink">4.1</span></a> and <a href="chap4.html#X832DA51986A3882C"><span class="RefLink">4.2</span></a> describe the operations that are available for codes. Section <a href="chap4.html#X864091AA7D4AFE86"><span class="RefLink">4.3</span></a> describe the functions that tests whether an object is a code and what kind of code it is (see <code class="code">IsCode</code>, <code class="func">IsLinearCode</code> (<a href="chap4.html#X7B24748A7CE8D4B9"><span class="RefLink">4.3-4</span></a>) and <code class="code">IsCyclicCode</code>) and various other boolean functions for codes. Section <a href="chap4.html#X86442DCD7A0B2146"><span class="RefLink">4.4</span></a> describe functions about equivalence and isomorphism of codes (see <code class="func">IsEquivalent</code> (<a href="chap4.html#X843034687D9C75B0"><span class="RefLink">4.4-1</span></a>), <code class="func">CodeIsomorphism</code> (<a href="chap4.html#X874DED8E86BC180B"><span class="RefLink">4.4-2</span></a>) and <code class="func">AutomorphismGroup</code> (<a href="chap4.html#X87677B0787B4461A"><span class="RefLink">4.4-3</span></a>)). Section <a href="chap4.html#X866EB39483DDAE72"><span class="RefLink">4.5</span></a> describes functions that work on <em>domains</em> (see Chapter "Domains and their Elements" in the GAP Reference Manual). Section <a href="chap4.html#X823827927D6A8235"><span class="RefLink">4.6</span></a> describes functions for printing and displaying codes. Section <a href="chap4.html#X7D0F48B685A3ECDD"><span class="RefLink">4.7</span></a> describes functions that return the matrices and polynomials that define a code (see <code class="func">GeneratorMat</code> (<a href="chap4.html#X817224657C9829C4"><span class="RefLink">4.7-1</span></a>), <code class="func">CheckMat</code> (<a href="chap4.html#X85D4B26E7FB38D57"><span class="RefLink">4.7-2</span></a>), <code class="func">GeneratorPol</code> (<a href="chap4.html#X78E33C3A843B0261"><span class="RefLink">4.7-3</span></a>), <code class="func">CheckPol</code> (<a href="chap4.html#X7C45AA317BB1195F"><span class="RefLink">4.7-4</span></a>), <code class="func">RootsOfCode</code> (<a href="chap4.html#X7F4CB9DB7CD97178"><span class="RefLink">4.7-5</span></a>)). Section <a href="chap4.html#X8170B52D7C154247"><span class="RefLink">4.8</span></a> describes functions that return the basic parameters of codes (see <code class="func">WordLength</code> (<a href="chap4.html#X7A36C3C67B0062E8"><span class="RefLink">4.8-1</span></a>), <code class="func">Redundancy</code> (<a href="chap4.html#X7E33FD56792DBF3D"><span class="RefLink">4.8-2</span></a>) and <code class="func">MinimumDistance</code> (<a href="chap4.html#X7B31613D8538BD29"><span class="RefLink">4.8-3</span></a>)). Section <a href="chap4.html#X806384B4815EFF2E"><span class="RefLink">4.9</span></a> describes functions that return distance and weight distributions (see <code class="func">WeightDistribution</code> (<a href="chap4.html#X8728BCC9842A6E5D"><span class="RefLink">4.9-2</span></a>), <code class="func">InnerDistribution</code> (<a href="chap4.html#X871FD301820717A4"><span class="RefLink">4.9-3</span></a>), <code class="func">OuterDistribution</code> (<a href="chap4.html#X8495870687195324"><span class="RefLink">4.9-5</span></a>) and <code class="func">DistancesDistribution</code> (<a href="chap4.html#X87AD54F87C5EE77E"><span class="RefLink">4.9-4</span></a>)). Section <a href="chap4.html#X7D9A39BF801948C8"><span class="RefLink">4.10</span></a> describes functions that are related to decoding (see <code class="func">Decode</code> (<a href="chap4.html#X7A42FF7D87FC34AC"><span class="RefLink">4.10-1</span></a>), <code class="func">Decodeword</code> (<a href="chap4.html#X7D870C9387C47D9F"><span class="RefLink">4.10-2</span></a>), <code class="func">Syndrome</code> (<a href="chap4.html#X7D02E0FE8735D3E6"><span class="RefLink">4.10-8</span></a>), <code class="func">SyndromeTable</code> (<a href="chap4.html#X7B9E71987E4294A7"><span class="RefLink">4.10-9</span></a>) and <code class="func">StandardArray</code> (<a href="chap4.html#X8642D0BD789DA9B5"><span class="RefLink">4.10-10</span></a>)). In Chapters <a href="chap5.html#X87EB64ED831CCE99"><span class="RefLink">5.</span></a> and <a href="chap6.html#X866FC1117814B64D"><span class="RefLink">6.</span></a> which follow, we describe functions that generate and manipulate codes.</p>
<p><a id="X7ECE60E1873B49A6" name="X7ECE60E1873B49A6"></a></p>
<h4>4.1 <span class="Heading">Comparisons of Codes</span></h4>
<p><a id="X8686D5FA839F1A3D" name="X8686D5FA839F1A3D"></a></p>
<h5><code>4.1-1 \=</code></h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ \=</code>( <var class="Arg">C1</var>, <var class="Arg">C2</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>The equality operator <code class="code">C1 = C2</code> evaluates to `true' if the codes C1 and C2 are equal, and to `false' otherwise.</p>
<p>The equality operator is also denoted <code class="code">EQ</code>, and <code class="code">Eq(C1,C2)</code> is the same as <code class="code">C1 = C2</code>. There is also an inequality operator, < >, or <code class="code">not EQ</code>.</p>
<p>Note that codes are equal if and only if their set of elements are equal. Codes can also be compared with objects of other types. Of course they are never equal.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">M := [ [0, 0], [1, 0], [0, 1], [1, 1] ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">C1 := ElementsCode( M, GF(2) );</span>
a (2,4,1..2)0 user defined unrestricted code over GF(2)
<span class="GAPprompt">gap></span> <span class="GAPinput">M = C1;</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">C2 := GeneratorMatCode( [ [1, 0], [0, 1] ], GF(2) );</span>
a linear [2,2,1]0 code defined by generator matrix over GF(2)
<span class="GAPprompt">gap></span> <span class="GAPinput">C1 = C2;</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">ReedMullerCode( 1, 3 ) = HadamardCode( 8 );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">WholeSpaceCode( 5, GF(4) ) = WholeSpaceCode( 5, GF(2) );</span>
false
</pre></div>
<p>Another way of comparing codes is <code class="code">IsEquivalent</code>, which checks if two codes are equivalent (see <code class="func">IsEquivalent</code> (<a href="chap4.html#X843034687D9C75B0"><span class="RefLink">4.4-1</span></a>)). By the way, this called <code class="code">CodeIsomorphism</code>. For the current version of <strong class="pkg">GUAVA</strong>, unless one of the codes is unrestricted, this calls Leon's C program (which only works for binary linear codes and only on a unix/linux computer).
<p><a id="X832DA51986A3882C" name="X832DA51986A3882C"></a></p>
<h4>4.2 <span class="Heading">
Operations for Codes
</span></h4>
<p><a id="X82E2E5127CD25168" name="X82E2E5127CD25168"></a></p>
<h5><code>4.2-1 \+</code></h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ \+</code>( <var class="Arg">C1</var>, <var class="Arg">C2</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>The operator `+' evaluates to the direct sum of the codes C1 and C2. See DirectSumCode (6.2-1).
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">C1:=RandomLinearCode(10,5);</span>
a [10,5,?] randomly generated code over GF(2)
<span class="GAPprompt">gap></span> <span class="GAPinput">C2:=RandomLinearCode(9,4);</span>
a [9,4,?] randomly generated code over GF(2)
<span class="GAPprompt">gap></span> <span class="GAPinput">C1+C2;</span>
a linear [19,9,1..2]4..9 direct sum code
</pre></div>
<p><a id="X7EFA08EE7BA22261" name="X7EFA08EE7BA22261"></a></p>
<h5><code>4.2-2 \*</code></h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ \*</code>( <var class="Arg">C1</var>, <var class="Arg">C2</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>The operator `*' evaluates to the direct product of the codes C1 and C2. See DirectProductCode (6.2-3).
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">C1 := GeneratorMatCode( [ [1, 0,0,0], [0, 1,0,0] ], GF(2) );</span>
a linear [4,2,1]1..2 code defined by generator matrix over GF(2)
<span class="GAPprompt">gap></span> <span class="GAPinput">C2 := GeneratorMatCode( [ [0,0,1, 1], [0,0,0, 1] ], GF(2) );</span>
a linear [4,2,1]1..2 code defined by generator matrix over GF(2)
<span class="GAPprompt">gap></span> <span class="GAPinput">C1*C2;</span>
a linear [16,4,1]4..12 direct product code
</pre></div>
<p><a id="X84D8B18F7C494A58" name="X84D8B18F7C494A58"></a></p>
<h5><code>4.2-3 \*</code></h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ \*</code>( <var class="Arg">m</var>, <var class="Arg">C</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>The operator <code class="code">m*C</code> evaluates to the element of <var class="Arg">C</var> belonging to information word ('message') <var class="Arg">m</var>. Here <var class="Arg">m</var> may be a vector, polynomial, string or codeword or a list of those. This is the way to do encoding in <strong class="pkg">GUAVA</strong>. <var class="Arg">C</var> must be linear, because in <strong class="pkg">GUAVA</strong>, encoding by multiplication is only defined for linear codes. If <var class="Arg">C</var> is a cyclic code, this multiplication is the same as multiplying an information polynomial <var class="Arg">m</var> by the generator polynomial of <var class="Arg">C</var>. If <var class="Arg">C</var> is a linear code, it is equal to the multiplication of an information vector <var class="Arg">m</var> by a generator matrix of <var class="Arg">C</var>.</p>
<p>To invert this, use the function <code class="code">InformationWord</code> (see <code class="func">InformationWord</code> (<a href="chap4.html#X8744BA5E78BCF3F9"><span class="RefLink">4.2-4</span></a>), which simply calls the function <code class="code">Decode</code>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">C := GeneratorMatCode( [ [1, 0,0,0], [0, 1,0,0] ], GF(2) );</span>
a linear [4,2,1]1..2 code defined by generator matrix over GF(2)
<span class="GAPprompt">gap></span> <span class="GAPinput">m:=Codeword("11");</span>
[ 1 1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">m*C;</span>
[ 1 1 0 0 ]
</pre></div>
<p><a id="X8744BA5E78BCF3F9" name="X8744BA5E78BCF3F9"></a></p>
<h5>4.2-4 InformationWord</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ InformationWord</code>( <var class="Arg">C</var>, <var class="Arg">c</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Here <var class="Arg">C</var> is a linear code and <var class="Arg">c</var> is a codeword in it. The command <code class="code">InformationWord</code> returns the message word (or 'information digits') <span class="SimpleMath">m</span> satisfying <code class="code">c=m*C</code>. This command simply calls <code class="code">Decode</code>, provided <code class="code">c in C</code> is true. Otherwise, it returns an error.</p>
<p>To invert this, use the encoding function <code class="code">*</code> (see <code class="func">\*</code> (<a href="chap4.html#X84D8B18F7C494A58"><span class="RefLink">4.2-3</span></a>)).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">C:=HammingCode(3);</span>
a linear [7,4,3]1 Hamming (3,2) code over GF(2)
<span class="GAPprompt">gap></span> <span class="GAPinput">c:=Random(C);</span>
[ 0 0 0 1 1 1 1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">InformationWord(C,c);</span>
[ 0 1 1 1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">c:=Codeword("1111100");</span>
[ 1 1 1 1 1 0 0 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">InformationWord(C,c);</span>
Error, ERROR: codeword must belong to code
<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">c:=Random(C);</span>
[ 0 0 0 1 0 0 0 1 0 0 1 0 1 1 0 1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">InformationWord(C,c);</span>
"ERROR: code must be linear"
</pre></div>
<p><a id="X864091AA7D4AFE86" name="X864091AA7D4AFE86"></a></p>
<h4>4.3 <span class="Heading">
Boolean Functions for Codes
</span></h4>
<p><a id="X87BDB89B7AAFE8AD" name="X87BDB89B7AAFE8AD"></a></p>
<h5>4.3-1 in</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ in</code>( <var class="Arg">c</var>, <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The command <code class="code">c in C</code> evaluates to `true' if C contains the codeword or list of codewords specified by c. Of course, c and C must have the same word lengths and base fields.
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">C:= HammingCode( 2 );; eC:= AsSSortedList( C );</span>
[ [ 0 0 0 ], [ 1 1 1 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">eC[2] in C;</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">[ 0 ] in C;</span>
false
</pre></div>
<p><a id="X79CA175481F8105F" name="X79CA175481F8105F"></a></p>
<h5>4.3-2 IsSubset</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsSubset</code>( <var class="Arg">C1</var>, <var class="Arg">C2</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The command <code class="code">IsSubset(C1,C2)</code> returns `true' if C2 is a subcode of C1, i.e. if C1 contains all the elements of C2.
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSubset( HammingCode(3), RepetitionCode( 7 ) );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSubset( RepetitionCode( 7 ), HammingCode( 3 ) );</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSubset( WholeSpaceCode( 7 ), HammingCode( 3 ) );</span>
true
</pre></div>
<p><a id="X7F71186281DEA83A" name="X7F71186281DEA83A"></a></p>
<h5>4.3-3 IsCode</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsCode</code>( <var class="Arg">obj</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">IsCode</code> returns `true' if obj, which can be an object of arbitrary type, is a code and `false' otherwise. Will cause an error if <var class="Arg">obj</var> is an unbound variable.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsCode( 1 );</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsCode( ReedMullerCode( 2,3 ) );</span>
true
</pre></div>
<p><a id="X7B24748A7CE8D4B9" name="X7B24748A7CE8D4B9"></a></p>
<h5>4.3-4 IsLinearCode</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsLinearCode</code>( <var class="Arg">obj</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">IsLinearCode</code> checks if object <var class="Arg">obj</var> (not necessarily a code) is a linear code. If a code has already been marked as linear or cyclic, the function automatically returns `true'. Otherwise, the function checks if a basis G of the elements of obj exists that generates the elements of obj. If so, G is recorded as a generator matrix of obj and the function returns `true'. If not, the function returns `false'.
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">C := ElementsCode( [ [0,0,0],[1,1,1] ], GF(2) );</span>
a (3,2,1..3)1 user defined unrestricted code over GF(2)
<span class="GAPprompt">gap></span> <span class="GAPinput">IsLinearCode( C );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsLinearCode( ElementsCode( [ [1,1,1] ], GF(2) ) );</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsLinearCode( 1 );</span>
false
</pre></div>
<p><a id="X850C23D07C9A9B19" name="X850C23D07C9A9B19"></a></p>
<h5>4.3-5 IsCyclicCode</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsCyclicCode</code>( <var class="Arg">obj</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">IsCyclicCode</code> checks if the object <var class="Arg">obj</var> is a cyclic code. If a code has already been marked as cyclic, the function automatically returns `true'. Otherwise, the function checks if a polynomial g exists that generates the elements of obj. If so, g is recorded as a generator polynomial of obj and the function returns `true'. If not, the function returns `false'.
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">C := ElementsCode( [ [0,0,0], [1,1,1] ], GF(2) );</span>
a (3,2,1..3)1 user defined unrestricted code over GF(2)
<span class="GAPprompt">gap></span> <span class="GAPinput"># GUAVA does not know the code is cyclic</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsCyclicCode( C ); # this command tells GUAVA to find out</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsCyclicCode( HammingCode( 4, GF(2) ) );</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsCyclicCode( 1 );</span>
false
</pre></div>
<p><a id="X85E3BD26856424F7" name="X85E3BD26856424F7"></a></p>
<h5>4.3-6 IsPerfectCode</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsPerfectCode</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">IsPerfectCode(C)</code> returns `true' if C is a perfect code. If C⊂ GF(q)^n then, by definition, this means that for some positive integer t, the space GF(q)^n is covered by non-overlapping spheres of (Hamming) radius t centered at the codewords in C. For a code with odd minimum distance d = 2t+1, this is the case when every word of the vector space of C is at distance at most t from exactly one element of C. Codes with even minimum distance are never perfect.
<p>In fact, a code that is not "trivially perfect" (the binary repetition codes of odd length, the codes consisting of one word, and the codes consisting of the whole vector space), and does not have the parameters of a Hamming or Golay code, cannot be perfect (see section 1.12 in <a href="chapBib.html#biBHP03">[HP03]</a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">H := HammingCode(2);</span>
a linear [3,1,3]1 Hamming (2,2) code over GF(2)
<span class="GAPprompt">gap></span> <span class="GAPinput">IsPerfectCode( H );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsPerfectCode( ElementsCode([[1,1,0],[0,0,1]],GF(2)) );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsPerfectCode( ReedSolomonCode( 6, 3 ) );</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsPerfectCode( BinaryGolayCode() );</span>
true
</pre></div>
<p><a id="X789380D28018EC3F" name="X789380D28018EC3F"></a></p>
<h5>4.3-7 IsMDSCode</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsMDSCode</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">IsMDSCode(C)</code> returns true if <var class="Arg">C</var> is a maximum distance separable (MDS) code. A linear <span class="SimpleMath">[n, k, d]</span>-code of length <span class="SimpleMath">n</span>, dimension <span class="SimpleMath">k</span> and minimum distance <span class="SimpleMath">d</span> is an MDS code if <span class="SimpleMath">k=n-d+1</span>, in other words if <var class="Arg">C</var> meets the Singleton bound (see <code class="func">UpperBoundSingleton</code> (<a href="chap7.html#X8673277C7F6C04C3"><span class="RefLink">7.1-1</span></a>)). An unrestricted <span class="SimpleMath">(n, M, d)</span> code is called <em>MDS</em> if <span class="SimpleMath">k=n-d+1</span>, with <span class="SimpleMath">k</span> equal to the largest integer less than or equal to the logarithm of <span class="SimpleMath">M</span> with base <span class="SimpleMath">q</span>, the size of the base field of <var class="Arg">C</var>.</p>
<p>Well-known MDS codes include the repetition codes, the whole space codes, the even weight codes (these are the only <em>binary</em> MDS codes) and the Reed-Solomon codes.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">C1 := ReedSolomonCode( 6, 3 );</span>
a cyclic [6,4,3]2 Reed-Solomon code over GF(7)
<span class="GAPprompt">gap></span> <span class="GAPinput">IsMDSCode( C1 ); # verify it is an MDS code, as 6-3+1 = 4</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsMDSCode( QRCode( 23, GF(2) ) );</span>
false
</pre></div>
<p><a id="X80166D8D837FEB58" name="X80166D8D837FEB58"></a></p>
<h5>4.3-8 IsSelfDualCode</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsSelfDualCode</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">IsSelfDualCode(C)</code> returns `true' if C is self-dual, i.e. when C is equal to its dual code (see also DualCode (6.1-14)). A code is self-dual if it contains all vectors that its elements are orthogonal to. If a code is self-dual, it automatically is self-orthogonal (see IsSelfOrthogonalCode (4.3-9)).
<p>If <var class="Arg">C</var> is a non-linear code, it cannot be self-dual (the dual code is always linear), so `false' is returned. A linear code can only be self-dual when its dimension k is equal to the redundancy r.
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSelfDualCode( ExtendedBinaryGolayCode() );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">C := ReedMullerCode( 1, 3 );</span>
a linear [8,4,4]2 Reed-Muller (1,3) code over GF(2)
<span class="GAPprompt">gap></span> <span class="GAPinput">DualCode( C ) = C;</span>
true
</pre></div>
<p><a id="X7B2A0CC481D2366F" name="X7B2A0CC481D2366F"></a></p>
<h5>4.3-9 IsSelfOrthogonalCode</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsSelfOrthogonalCode</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">IsSelfOrthogonalCode(C)</code> returns `true' if C is self-orthogonal. A code is self-orthogonal if every element of C is orthogonal to all elements of C, including itself. (In the linear case, this simply means that the generator matrix of C multiplied with its transpose yields a null matrix.)
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">R := ReedMullerCode(1,4);</span>
a linear [16,5,8]6 Reed-Muller (1,4) code over GF(2)
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSelfOrthogonalCode(R);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSelfDualCode(R);</span>
false
</pre></div>
<p><a id="X8358D43981EBE970" name="X8358D43981EBE970"></a></p>
<h5>4.3-10 IsDoublyEvenCode</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsDoublyEvenCode</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">IsDoublyEvenCode(C)</code> returns `true' if C is a binary linear code which has codewords of weight divisible by 4 only. According to [HP03], a doubly-even code is self-orthogonal and every row in its generator matrix has weight that is divisible by 4.
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">C:=BinaryGolayCode();</span>
a cyclic [23,12,7]3 binary Golay code over GF(2)
<span class="GAPprompt">gap></span> <span class="GAPinput">WeightDistribution(C);</span>
[ 1, 0, 0, 0, 0, 0, 0, 253, 506, 0, 0, 1288, 1288, 0, 0, 506, 253, 0, 0, 0,
0, 0, 0, 1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">IsDoublyEvenCode(C); </span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">C:=ExtendedCode(C); </span>
a linear [24,12,8]4 extended code
<span class="GAPprompt">gap></span> <span class="GAPinput">WeightDistribution(C);</span>
[ 1, 0, 0, 0, 0, 0, 0, 0, 759, 0, 0, 0, 2576, 0, 0, 0, 759, 0, 0, 0, 0, 0, 0,
0, 1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">IsDoublyEvenCode(C); </span>
true
</pre></div>
<p><a id="X79ACAEF5865414A0" name="X79ACAEF5865414A0"></a></p>
<h5>4.3-11 IsSinglyEvenCode</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsSinglyEvenCode</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">IsSinglyEvenCode(C)</code> returns `true' if C is a binary self-orthogonal linear code which is not doubly-even. In other words, C is a binary self-orthogonal code which has codewords of even weight.
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x:=Indeterminate(GF(2)); </span>
x_1
<span class="GAPprompt">gap></span> <span class="GAPinput">C:=QuasiCyclicCode( [x^0, 1+x^3+x^5+x^6+x^7], 11, GF(2) );</span>
a linear [22,11,1..6]4..7 quasi-cyclic code over GF(2)
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSelfDualCode(C); # self-dual is a restriction of self-orthogonal</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsDoublyEvenCode(C);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSinglyEvenCode(C);</span>
true
</pre></div>
<p><a id="X7CE150ED7C3DC455" name="X7CE150ED7C3DC455"></a></p>
<h5>4.3-12 IsEvenCode</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsEvenCode</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">IsEvenCode(C)</code> returns `true' if C is a binary linear code which has codewords of even weight--regardless whether or not it is self-orthogonal.
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">C:=BinaryGolayCode();</span>
a cyclic [23,12,7]3 binary Golay code over GF(2)
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSelfOrthogonalCode(C);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsEvenCode(C);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">C:=ExtendedCode(C);</span>
a linear [24,12,8]4 extended code
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSelfOrthogonalCode(C);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsEvenCode(C);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">C:=ExtendedCode(QRCode(17,GF(2)));</span>
a linear [18,9,6]3..5 extended code
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSelfOrthogonalCode(C);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsEvenCode(C);</span>
true
</pre></div>
<p><a id="X7B6DB8CC84FCAC1C" name="X7B6DB8CC84FCAC1C"></a></p>
<h5>4.3-13 IsSelfComplementaryCode</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsSelfComplementaryCode</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">IsSelfComplementaryCode</code> returns `true' if
<p class="pcenter">
v \in C \Rightarrow 1 - v \in C,
</p>
<p>where <span class="SimpleMath">1</span> is the all-one word of length <span class="SimpleMath">n</span>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSelfComplementaryCode( HammingCode( 3, GF(2) ) );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSelfComplementaryCode( EvenWeightSubcode(</span>
<span class="GAPprompt">></span> <span class="GAPinput">HammingCode( 3, GF(2) ) ) );</span>
false
</pre></div>
<p><a id="X7AFD3844859B20BF" name="X7AFD3844859B20BF"></a></p>
<h5>4.3-14 IsAffineCode</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsAffineCode</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">IsAffineCode</code> returns `true' if C is an affine code. A code is called affine if it is an affine space. In other words, a code is affine if it is a coset of a linear code.
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsAffineCode( HammingCode( 3, GF(2) ) );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsAffineCode( CosetCode( HammingCode( 3, GF(2) ),</span>
<span class="GAPprompt">></span> <span class="GAPinput">Codeword([ 1, 0, 0, 0, 0, 0, 0 ]) ) );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsAffineCode( NordstromRobinsonCode() );</span>
false
</pre></div>
<p><a id="X861D32FB81EF0D77" name="X861D32FB81EF0D77"></a></p>
<h5>4.3-15 IsAlmostAffineCode</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsAlmostAffineCode</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">IsAlmostAffineCode</code> returns `true' if C is an almost affine code. A code is called almost affine if the size of any punctured code of C is q^r for some r, where q is the size of the alphabet of the code. Every affine code is also almost affine, and every code over GF(2) and GF(3) that is almost affine is also affine.
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">code := ElementsCode( [ [0,0,0], [0,1,1], [0,2,2], [0,3,3],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [1,0,1], [1,1,0], [1,2,3], [1,3,2],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [2,0,2], [2,1,3], [2,2,0], [2,3,1],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [3,0,3], [3,1,2], [3,2,1], [3,3,0] ],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> GF(4) );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsAlmostAffineCode( code );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsAlmostAffineCode( NordstromRobinsonCode() );</span>
false
</pre></div>
<p><a id="X86442DCD7A0B2146" name="X86442DCD7A0B2146"></a></p>
<h4>4.4 <span class="Heading">
Equivalence and Isomorphism of Codes
</span></h4>
<p><a id="X843034687D9C75B0" name="X843034687D9C75B0"></a></p>
<h5>4.4-1 IsEquivalent</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsEquivalent</code>( <var class="Arg">C1</var>, <var class="Arg">C2</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>We say that <var class="Arg">C1</var> is <em>permutation equivalent</em> to <var class="Arg">C2</var> if <var class="Arg">C1</var> can be obtained from <var class="Arg">C2</var> by carrying out column permutations. <code class="code">IsEquivalent</code> returns true if <var class="Arg">C1</var> and <var class="Arg">C2</var> are equivalent codes. At this time, <code class="code">IsEquivalent</code> only handles <em>binary</em> codes. (The external unix/linux program <strong class="button">desauto</strong> from J. S. Leon is called by <code class="code">IsEquivalent</code>.) Of course, if <var class="Arg">C1</var> and <var class="Arg">C2</var> are equal, they are also equivalent.</p>
<p>Note that the algorithm is <em>very slow</em> for non-linear codes.</p>
<p>More generally, we say that <var class="Arg">C1</var> is <em>equivalent</em> to <var class="Arg">C2</var> if <var class="Arg">C1</var> can be obtained from <var class="Arg">C2</var> by carrying out column permutations and a permutation of the alphabet.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x:= Indeterminate( GF(2), "x" );; pol:= x^3+x+1; </span>
x^3+x+Z(2)^0
<span class="GAPprompt">gap></span> <span class="GAPinput">H := GeneratorPolCode( pol, 7, GF(2)); </span>
a cyclic [7,4,1..3]1 code defined by generator polynomial over GF(2)
<span class="GAPprompt">gap></span> <span class="GAPinput">H = HammingCode(3, GF(2));</span>
false
# verify that H is equivalent to a Hamming code
<span class="GAPprompt">gap></span> <span class="GAPinput">IsEquivalent(H, HammingCode(3, GF(2)));</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">CodeIsomorphism(H, HammingCode(3, GF(2)));</span>
(3,4)(5,6,7)
</pre></div>
<p><a id="X874DED8E86BC180B" name="X874DED8E86BC180B"></a></p>
<h5>4.4-2 CodeIsomorphism</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CodeIsomorphism</code>( <var class="Arg">C1</var>, <var class="Arg">C2</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>If the two codes <var class="Arg">C1</var> and <var class="Arg">C2</var> are permutation equivalent codes (see <code class="func">IsEquivalent</code> (<a href="chap4.html#X843034687D9C75B0"><span class="RefLink">4.4-1</span></a>)), <code class="code">CodeIsomorphism</code> returns the permutation that transforms <var class="Arg">C1</var> into <var class="Arg">C2</var>. If the codes are not equivalent, it returns `false'.
<p>At this time, <code class="code">IsEquivalent</code> only computes isomorphisms between <em>binary</em> codes on a linux/unix computer (since it calls Leon's C program desauto).
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x:= Indeterminate( GF(2), "x" );; pol:= x^3+x+1; </span>
x^3+x+Z(2)^0
<span class="GAPprompt">gap></span> <span class="GAPinput">H := GeneratorPolCode( pol, 7, GF(2)); </span>
a cyclic [7,4,1..3]1 code defined by generator polynomial over GF(2)
<span class="GAPprompt">gap></span> <span class="GAPinput">CodeIsomorphism(H, HammingCode(3, GF(2)));</span>
(3,4)(5,6,7)
<span class="GAPprompt">gap></span> <span class="GAPinput">PermutedCode(H, (3,4)(5,6,7)) = HammingCode(3, GF(2));</span>
true
</pre></div>
<p><a id="X87677B0787B4461A" name="X87677B0787B4461A"></a></p>
<h5>4.4-3 AutomorphismGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AutomorphismGroup</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">AutomorphismGroup</code> returns the automorphism group of a linear code <var class="Arg">C</var>. For a binary code, the automorphism group is the largest permutation group of degree <span class="SimpleMath">n</span> such that each permutation applied to the columns of <var class="Arg">C</var> again yields <var class="Arg">C</var>. <strong class="pkg">GUAVA</strong> calls the external program <strong class="button">desauto</strong> written by J. S. Leon, if it exists, to compute the automorphism group. If Leon's program is not compiled on the system (and in the default directory) then it calls instead the much slower program PermutationAutomorphismGroup.
<p>See Leon <a href="chapBib.html#biBLeon82">[Leo82]</a> for a more precise description of the method, and the <code class="file">guava/src/leon/doc</code> subdirectory for for details about Leon's C programs.
<p>The function <code class="code">PermutedCode</code> permutes the columns of a code (see <code class="func">PermutedCode</code> (<a href="chap6.html#X79577EB27BE8524B"><span class="RefLink">6.1-4</span></a>)).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">R := RepetitionCode(7,GF(2));</span>
a cyclic [7,1,7]3 repetition code over GF(2)
# verify that every permutation keeps R identical, that is, the
# automorphism group is Sym(7)
<span class="GAPprompt">gap></span> <span class="GAPinput">AutomorphismGroup(R);</span>
Sym( [ 1 .. 7 ] )
<span class="GAPprompt">gap></span> <span class="GAPinput">C := CordaroWagnerCode(7);</span>
a linear [7,2,4]3 Cordaro-Wagner code over GF(2)
<span class="GAPprompt">gap></span> <span class="GAPinput">AsSSortedList(C);</span>
[ [ 0 0 0 0 0 0 0 ], [ 0 0 1 1 1 1 1 ], [ 1 1 0 0 0 1 1 ], [ 1 1 1 1 1 0 0 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">AutomorphismGroup(C);</span>
Group([ (3,4), (4,5), (1,6)(2,7), (1,2), (6,7) ])
<span class="GAPprompt">gap></span> <span class="GAPinput">C2 := PermutedCode(C, (1,6)(2,7));</span>
a linear [7,2,4]3 permuted code
<span class="GAPprompt">gap></span> <span class="GAPinput">AsSSortedList(C2);</span>
[ [ 0 0 0 0 0 0 0 ], [ 0 0 1 1 1 1 1 ], [ 1 1 0 0 0 1 1 ], [ 1 1 1 1 1 0 0 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">C2 = C;</span>
true
</pre></div>
<p><a id="X79F3261F86C29F6D" name="X79F3261F86C29F6D"></a></p>
<h5>4.4-4 PermutationAutomorphismGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PermutationAutomorphismGroup</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">PermutationAutomorphismGroup</code> returns the permutation automorphism group of a linear code <var class="Arg">C</var>. This is the largest permutation group of degree <span class="SimpleMath">n</span> such that each permutation applied to the columns of <var class="Arg">C</var> again yields <var class="Arg">C</var>. It is written in GAP, so is much slower than <code class="code">AutomorphismGroup</code>.</p>
<p>When <var class="Arg">C</var> is binary <code class="code">PermutationAutomorphismGroup</code> does <em>not</em> call <code class="code">AutomorphismGroup</code>, even though they agree mathematically in that case. This way <code class="code">PermutationAutomorphismGroup</code> can be called on any platform which runs GAP.</p>
<p>The older name for this command, <code class="code">PermutationGroup</code>, will become obsolete in the next version of GAP.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">R := RepetitionCode(3,GF(3));</span>
a cyclic [3,1,3]2 repetition code over GF(3)
<span class="GAPprompt">gap></span> <span class="GAPinput">G:=PermutationAutomorphismGroup(R);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">G=SymmetricGroup(3);</span>
true
</pre></div>
<p><a id="X866EB39483DDAE72" name="X866EB39483DDAE72"></a></p>
<h4>4.5 <span class="Heading">
Domain Functions for Codes
</span></h4>
<p>These are some GAP functions that work on `Domains' in general. Their specific effect o | | |
