<?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" />
</head>
<body>
<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="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0.html">Top of Book</a> <a href="chap3.html">Previous Chapter</a> <a href="chap5.html">Next Chapter</a> </div>
<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="nocss"> </span><a href="chap4.html#X7ECE60E1873B49A6">4.1 <span class="Heading">Comparisons of Codes</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X8123456781234567">4.1-1 =</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap4.html#X832DA51986A3882C">4.2 <span class="Heading">
Operations for Codes
</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7F2703417F270341">4.2-1 +</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X8123456781234567">4.2-2 *</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X8123456781234567">4.2-3 *</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X8744BA5E78BCF3F9">4.2-4 InformationWord</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap4.html#X864091AA7D4AFE86">4.3 <span class="Heading">
Boolean Functions for Codes
</span></a>
<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 class="ContSect"><span class="nocss"> </span><a href="chap4.html#X86442DCD7A0B2146">4.4 <span class="Heading">
Equivalence and Isomorphism of Codes
</span></a>
<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 class="ContSect"><span class="nocss"> </span><a href="chap4.html#X866EB39483DDAE72">4.5 <span class="Heading">
Domain Functions for Codes
</span></a>
<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 class="ContSect"><span class="nocss"> </span><a href="chap4.html#X823827927D6A8235">4.6 <span class="Heading">
Printing and Displaying Codes
</span></a>
<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 class="ContSect"><span class="nocss"> </span><a href="chap4.html#X7D0F48B685A3ECDD">4.7 <span class="Heading">
Generating (Check) Matrices and Polynomials
</span></a>
<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 class="ContSect"><span class="nocss"> </span><a href="chap4.html#X8170B52D7C154247">4.8 <span class="Heading">
Parameters of Codes
</span></a>
<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 class="ContSect"><span class="nocss"> </span><a href="chap4.html#X806384B4815EFF2E">4.9 <span class="Heading">
Distributions
</span></a>
<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 class="ContSect"><span class="nocss"> </span><a href="chap4.html#X7D9A39BF801948C8">4.10 <span class="Heading">
Decoding Functions
</span></a>
<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>
<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 GF(q), where q 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"><b>3.</b></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>
<table class="example">
<tr><td><pre>
gap> C := ElementsCode(["1100", "1010", "0001"], "example code", GF(2) );
a (4,3,1..4)2..4 example code over GF(2)
</pre></td></tr></table>
<p>An (n,M,d) code is a code with word <em>length</em> n, <em>size</em> M and <em>minimum distance</em> d. If the minimum distance has not yet been calculated, the lower bound and upper bound are printed (except in the case where the code is a random linear codes, where these are not printed for efficiency reasons). So</p>
<pre class="normal">
a (4,3,1..4)2..4 code over GF(2)
</pre>
<p>means a binary unrestricted code of length 4, with 3 elements and the minimum distance is greater than or equal to 1 and less than or equal to 4 and the covering radius is greater than or equal to 2 and less than or equal to 4.</p>
<table class="example">
<tr><td><pre>
gap> C := ElementsCode(["1100", "1010", "0001"], "example code", GF(2) );
a (4,3,1..4)2..4 example code over GF(2)
gap> MinimumDistance(C);
2
gap> C;
a (4,3,2)2..4 example code over GF(2)
</pre></td></tr></table>
<p>If the set of elements is a linear subspace of GF(q)^n, 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 GF(q)). 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>
<table class="example">
<tr><td><pre>
gap> G := GeneratorMatCode([[1,0,1],[0,1,2]], "demo code", GF(3) );
a linear [3,2,1..2]1 demo code over GF(3)
</pre></td></tr></table>
<p>So a linear [n, k, d]r code is a code with word <em>length</em> n, <em>dimension</em> k, <em>minimum distance</em> d and <em>covering radius</em> r.</p>
<p>If the code is linear and all cyclic shifts of its codewords (regarded as n-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 x^n -1, where n is the word length of the code. Such a polynomial is called a <em>generator polynomial</em> The generator polynomial must divide x^n-1 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 x^n -1). In <strong class="pkg">GUAVA</strong>, a cyclic code can be defined by either its generator polynomial or check polynomial.</p>
<table class="example">
<tr><td><pre>
gap> G := GeneratorPolCode(Indeterminate(GF(2))+Z(2)^0, 7, GF(2) );
a cyclic [7,6,1..2]1 code defined by generator polynomial over GF(2)
</pre></td></tr></table>
<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"><b>5.1-1</b></a>)). By calling the function <code class="code">IsLinearCode</code> (see <code class="func">IsLinearCode</code> (<a href="chap4.html#X7B24748A7CE8D4B9"><b>4.3-4</b></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>
<table class="example">
<tr><td><pre>
gap> L := Z(2)*[ [0,0,0], [1,0,0], [0,1,1], [1,1,1] ];;
gap> C := ElementsCode( L, GF(2) );
a (3,4,1..3)1 user defined unrestricted code over GF(2)
# so far, GUAVA does not know what kind of code this is
gap> IsLinearCode( C );
true # it is linear
gap> C;
a linear [3,2,1]1 user defined unrestricted code over GF(2)
</pre></td></tr></table>
<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 <code class="code">Decode</code> or <code class="code">Decodeword</code>. For more information about encoding and decoding, see sections <a href="chap4.html#X832DA51986A3882C"><b>4.2</b></a> and <a href="chap4.html#X7A42FF7D87FC34AC"><b>4.10-1</b></a>.</p>
<table class="example">
<tr><td><pre>
gap> R := ReedMullerCode( 1, 3 );
a linear [8,4,4]2 Reed-Muller (1,3) code over GF(2)
gap> w := [ 1, 0, 1, 1 ] * R;
[ 1 0 0 1 1 0 0 1 ]
gap> Decode( R, w );
[ 1 0 1 1 ]
gap> Decode( R, w + "10000000" ); # One error at the first position
[ 1 0 1 1 ] # Corrected by Guava
</pre></td></tr></table>
<p>Sections <a href="chap4.html#X7ECE60E1873B49A6"><b>4.1</b></a> and <a href="chap4.html#X832DA51986A3882C"><b>4.2</b></a> describe the operations that are available for codes. Section <a href="chap4.html#X864091AA7D4AFE86"><b>4.3</b></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"><b>4.3-4</b></a>) and <code class="code">IsCyclicCode</code>) and various other boolean functions for codes. Section <a href="chap4.html#X86442DCD7A0B2146"><b>4.4</b></a> describe functions about equivalence and isomorphism of codes (see <code class="func">IsEquivalent</code> (<a href="chap4.html#X843034687D9C75B0"><b>4.4-1</b></a>), <code class="func">CodeIsomorphism</code> (<a href="chap4.html#X874DED8E86BC180B"><b>4.4-2</b></a>) and <code class="func">AutomorphismGroup</code> (<a href="chap4.html#X87677B0787B4461A"><b>4.4-3</b></a>)). Section <a href="chap4.html#X866EB39483DDAE72"><b>4.5</b></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"><b>4.6</b></a> describes functions for printing and displaying codes. Section <a href="chap4.html#X7D0F48B685A3ECDD"><b>4.7</b></a> describes functions that return the matrices and polynomials that define a code (see <code class="func">GeneratorMat</code> (<a href="chap4.html#X817224657C9829C4"><b>4.7-1</b></a>), <code class="func">CheckMat</code> (<a href="chap4.html#X85D4B26E7FB38D57"><b>4.7-2</b></a>), <code class="func">GeneratorPol</code> (<a href="chap4.html#X78E33C3A843B0261"><b>4.7-3</b></a>), <code class="func">CheckPol</code> (<a href="chap4.html#X7C45AA317BB1195F"><b>4.7-4</b></a>), <code class="func">RootsOfCode</code> (<a href="chap4.html#X7F4CB9DB7CD97178"><b>4.7-5</b></a>)). Section <a href="chap4.html#X8170B52D7C154247"><b>4.8</b></a> describes functions that return the basic parameters of codes (see <code class="func">WordLength</code> (<a href="chap4.html#X7A36C3C67B0062E8"><b>4.8-1</b></a>), <code class="func">Redundancy</code> (<a href="chap4.html#X7E33FD56792DBF3D"><b>4.8-2</b></a>) and <code class="func">MinimumDistance</code> (<a href="chap4.html#X7B31613D8538BD29"><b>4.8-3</b></a>)). Section <a href="chap4.html#X806384B4815EFF2E"><b>4.9</b></a> describes functions that return distance and weight distributions (see <code class="func">WeightDistribution</code> (<a href="chap4.html#X8728BCC9842A6E5D"><b>4.9-2</b></a>), <code class="func">InnerDistribution</code> (<a href="chap4.html#X871FD301820717A4"><b>4.9-3</b></a>), <code class="func">OuterDistribution</code> (<a href="chap4.html#X8495870687195324"><b>4.9-5</b></a>) and <code class="func">DistancesDistribution</code> (<a href="chap4.html#X87AD54F87C5EE77E"><b>4.9-4</b></a>)). Section <a href="chap4.html#X7D9A39BF801948C8"><b>4.10</b></a> describes functions that are related to decoding (see <code class="func">Decode</code> (<a href="chap4.html#X7A42FF7D87FC34AC"><b>4.10-1</b></a>), <code class="func">Decodeword</code> (<a href="chap4.html#X7D870C9387C47D9F"><b>4.10-2</b></a>), <code class="func">Syndrome</code> (<a href="chap4.html#X7D02E0FE8735D3E6"><b>4.10-8</b></a>), <code class="func">SyndromeTable</code> (<a href="chap4.html#X7B9E71987E4294A7"><b>4.10-9</b></a>) and <code class="func">StandardArray</code> (<a href="chap4.html#X8642D0BD789DA9B5"><b>4.10-10</b></a>)). In Chapters <a href="chap5.html#X87EB64ED831CCE99"><b>5.</b></a> and <a href="chap6.html#X866FC1117814B64D"><b>6.</b></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="X8123456781234567" name="X8123456781234567"></a></p>
<h5>4.1-1 =</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> =</code>( <var class="Arg">C1, C2</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The equality operator <code class="code">C1 = C2</code> evaluates to `true' if the codes <var class="Arg">C1</var> and <var class="Arg">C2</var> are equal, and to `false' otherwise.</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>
<table class="example">
<tr><td><pre>
gap> M := [ [0, 0], [1, 0], [0, 1], [1, 1] ];;
gap> C1 := ElementsCode( M, GF(2) );
a (2,4,1..2)0 user defined unrestricted code over GF(2)
gap> M = C1;
false
gap> C2 := GeneratorMatCode( [ [1, 0], [0, 1] ], GF(2) );
a linear [2,2,1]0 code defined by generator matrix over GF(2)
gap> C1 = C2;
true
gap> ReedMullerCode( 1, 3 ) = HadamardCode( 8 );
true
gap> WholeSpaceCode( 5, GF(4) ) = WholeSpaceCode( 5, GF(2) );
false
</pre></td></tr></table>
<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"><b>4.4-1</b></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>
<p><a id="X832DA51986A3882C" name="X832DA51986A3882C"></a></p>
<h4>4.2 <span class="Heading">
Operations for Codes
</span></h4>
<p><a id="X7F2703417F270341" name="X7F2703417F270341"></a></p>
<h5>4.2-1 +</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> +</code>( <var class="Arg">C1, C2</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The operator `+' evaluates to the direct sum of the codes <var class="Arg">C1</var> and <var class="Arg">C2</var>. See <code class="func">DirectSumCode</code> (<a href="chap6.html#X79E00D3A8367D65A"><b>6.2-1</b></a>).</p>
<table class="example">
<tr><td><pre>
gap> C1:=RandomLinearCode(10,5);
a [10,5,?] randomly generated code over GF(2)
gap> C2:=RandomLinearCode(9,4);
a [9,4,?] randomly generated code over GF(2)
gap> C1+C2;
a linear [10,9,1]0..10 unknown linear code over GF(2)
</pre></td></tr></table>
<p><a id="X8123456781234567" name="X8123456781234567"></a></p>
<h5>4.2-2 *</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> *</code>( <var class="Arg">C1, C2</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The operator `*' evaluates to the direct product of the codes <var class="Arg">C1</var> and <var class="Arg">C2</var>. See <code class="func">DirectProductCode</code> (<a href="chap6.html#X7BFBBA5784C293C1"><b>6.2-3</b></a>).</p>
<table class="example">
<tr><td><pre>
gap> C1 := GeneratorMatCode( [ [1, 0,0,0], [0, 1,0,0] ], GF(2) );
a linear [4,2,1]1 code defined by generator matrix over GF(2)
gap> C2 := GeneratorMatCode( [ [0,0,1, 1], [0,0,0, 1] ], GF(2) );
a linear [4,2,1]1 code defined by generator matrix over GF(2)
gap> C1*C2;
a linear [16,4,1]4..12 direct product code
</pre></td></tr></table>
<p><a id="X8123456781234567" name="X8123456781234567"></a></p>
<h5>4.2-3 *</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> *</code>( <var class="Arg">m, C</var> )</td><td class="tdright">( function )</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"><b>4.2-4</b></a>), which simply calls the function <code class="code">Decode</code>).</p>
<table class="example">
<tr><td><pre>
gap> C := GeneratorMatCode( [ [1, 0,0,0], [0, 1,0,0] ], GF(2) );
a linear [4,2,1]1 code defined by generator matrix over GF(2)
gap> m:=Codeword("11");
[ 1 1 ]
gap> m*C;
[ 1 1 0 0 ]
</pre></td></tr></table>
<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, 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') m satisfying <code class="code">c=m*C</code>. This command simply calls <code class="code">Decode</code>, provided <code class="code">c in C</code> is true. Otherwise, it returns an error.</p>
<p>To invert this, use the encoding function <code class="code">*</code> (see <code class="func">*</code> (<a href="chap4.html#X8123456781234567"><b>4.2-3</b></a>)).</p>
<table class="example">
<tr><td><pre>
gap> C:=HammingCode(3);
a linear [7,4,3]1 Hamming (3,2) code over GF(2)
gap> c:=Random(C);
[ 0 0 0 1 1 1 1 ]
gap> InformationWord(C,c);
[ 0 1 1 1 ]
gap> c:=Codeword("1111100");
[ 1 1 1 1 1 0 0 ]
gap> InformationWord(C,c);
"ERROR: codeword must belong to code"
gap> C:=NordstromRobinsonCode();
a (16,256,6)4 Nordstrom-Robinson code over GF(2)
gap> c:=Random(C);
[ 0 0 0 1 0 0 0 1 0 0 1 0 1 1 0 1 ]
gap> InformationWord(C,c);
"ERROR: code must be linear"
</pre></td></tr></table>
<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, 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 <var class="Arg">C</var> contains the codeword or list of codewords specified by <var class="Arg">c</var>. Of course, <var class="Arg">c</var> and <var class="Arg">C</var> must have the same word lengths and base fields.</p>
<table class="example">
<tr><td><pre>
gap> C:= HammingCode( 2 );; eC:= AsSSortedList( C );
[ [ 0 0 0 ], [ 1 1 1 ] ]
gap> eC[2] in C;
true
gap> [ 0 ] in C;
false
</pre></td></tr></table>
<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, C2</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The command <code class="code">IsSubset(C1,C2)</code> returns `true' if <var class="Arg">C2</var> is a subcode of <var class="Arg">C1</var>, i.e. if <var class="Arg">C1</var> contains all the elements of <var class="Arg">C2</var>.</p>
<table class="example">
<tr><td><pre>
gap> IsSubset( HammingCode(3), RepetitionCode( 7 ) );
true
gap> IsSubset( RepetitionCode( 7 ), HammingCode( 3 ) );
false
gap> IsSubset( WholeSpaceCode( 7 ), HammingCode( 3 ) );
true
</pre></td></tr></table>
<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 <var class="Arg">obj</var>, which can be an object of arbitrary type, is a code and `false' otherwise. Will cause an error if <var class="Arg">obj</var> is an unbound variable.</p>
<table class="example">
<tr><td><pre>
gap> IsCode( 1 );
false
gap> IsCode( ReedMullerCode( 2,3 ) );
true
</pre></td></tr></table>
<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 <var class="Arg">obj</var> exists that generates the elements of <var class="Arg">obj</var>. If so, G is recorded as a generator matrix of <var class="Arg">obj</var> and the function returns `true'. If not, the function returns `false'.</p>
<table class="example">
<tr><td><pre>
gap> C := ElementsCode( [ [0,0,0],[1,1,1] ], GF(2) );
a (3,2,1..3)1 user defined unrestricted code over GF(2)
gap> IsLinearCode( C );
true
gap> IsLinearCode( ElementsCode( [ [1,1,1] ], GF(2) ) );
false
gap> IsLinearCode( 1 );
false
</pre></td></tr></table>
<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 <var class="Arg">obj</var>. If so, g is recorded as a generator polynomial of <var class="Arg">obj</var> and the function returns `true'. If not, the function returns `false'.</p>
<table class="example">
<tr><td><pre>
gap> C := ElementsCode( [ [0,0,0], [1,1,1] ], GF(2) );
a (3,2,1..3)1 user defined unrestricted code over GF(2)
gap> # GUAVA does not know the code is cyclic
gap> IsCyclicCode( C ); # this command tells GUAVA to find out
true
gap> IsCyclicCode( HammingCode( 4, GF(2) ) );
false
gap> IsCyclicCode( 1 );
false
</pre></td></tr></table>
<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 <var class="Arg">C</var> is a perfect code. If Csubset GF(q)^n then, by definition, this means that for some positive integer t, the space GF(q)^n is covered by non-overlapping spheres of (Hamming) radius t centered at the codewords in <var class="Arg">C</var>. For a code with odd minimum distance d = 2t+1, this is the case when every word of the vector space of <var class="Arg">C</var> is at distance at most t from exactly one element of <var class="Arg">C</var>. Codes with even minimum distance are never perfect.</p>
<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>
<table class="example">
<tr><td><pre>
gap> H := HammingCode(2);
a linear [3,1,3]1 Hamming (2,2) code over GF(2)
gap> IsPerfectCode( H );
true
gap> IsPerfectCode( ElementsCode([[1,1,0],[0,0,1]],GF(2)) );
true
gap> IsPerfectCode( ReedSolomonCode( 6, 3 ) );
false
gap> IsPerfectCode( BinaryGolayCode() );
true
</pre></td></tr></table>
<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 [n, k, d]-code of length n, dimension k and minimum distance d is an MDS code if k=n-d+1, in other words if <var class="Arg">C</var> meets the Singleton bound (see <code class="func">UpperBoundSingleton</code> (<a href="chap7.html#X8673277C7F6C04C3"><b>7.1-1</b></a>)). An unrestricted (n, M, d) code is called <em>MDS</em> if k=n-d+1, with k equal to the largest integer less than or equal to the logarithm of M with base q, the size of the base field of <var class="Arg">C</var>.</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>
<table class="example">
<tr><td><pre>
gap> C1 := ReedSolomonCode( 6, 3 );
a cyclic [6,4,3]2 Reed-Solomon code over GF(7)
gap> IsMDSCode( C1 );
true # 6-3+1 = 4
gap> IsMDSCode( QRCode( 23, GF(2) ) );
false
</pre></td></tr></table>
<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 <var class="Arg">C</var> is self-dual, i.e. when <var class="Arg">C</var> is equal to its dual code (see also <code class="func">DualCode</code> (<a href="chap6.html#X799B12F085ACB609"><b>6.1-14</b></a>)). A code is self-dual if it contains all vectors that its elements are orthogonal to. If a code is self-dual, it automatically is self-orthogonal (see <code class="func">IsSelfOrthogonalCode</code> (<a href="chap4.html#X7B2A0CC481D2366F"><b>4.3-9</b></a>)).</p>
<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.</p>
<table class="example">
<tr><td><pre>
gap> IsSelfDualCode( ExtendedBinaryGolayCode() );
true
gap> C := ReedMullerCode( 1, 3 );
a linear [8,4,4]2 Reed-Muller (1,3) code over GF(2)
gap> DualCode( C ) = C;
true
</pre></td></tr></table>
<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 <var class="Arg">C</var> is self-orthogonal. A code is <em>self-orthogonal</em> if every element of <var class="Arg">C</var> is orthogonal to all elements of <var class="Arg">C</var>, including itself. (In the linear case, this simply means that the generator matrix of <var class="Arg">C</var> multiplied with its transpose yields a null matrix.)</p>
<table class="example">
<tr><td><pre>
gap> R := ReedMullerCode(1,4);
a linear [16,5,8]6 Reed-Muller (1,4) code over GF(2)
gap> IsSelfOrthogonalCode(R);
true
gap> IsSelfDualCode(R);
false
</pre></td></tr></table>
<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 <var class="Arg">C</var> is a binary linear code which has codewords of weight divisible by 4 only. According to <a href="chapBib.html#biBHP03">[HP03]</a>, a doubly-even code is self-orthogonal and every row in its generator matrix has weight that is divisible by 4.</p>
<table class="example">
<tr><td><pre>
gap> C:=BinaryGolayCode();
a cyclic [23,12,7]3 binary Golay code over GF(2)
gap> WeightDistribution(C);
[ 1, 0, 0, 0, 0, 0, 0, 253, 506, 0, 0, 1288, 1288, 0, 0, 506, 253, 0, 0, 0, 0, 0, 0, 1 ]
gap> IsDoublyEvenCode(C);
false
gap> C:=ExtendedCode(C);
a linear [24,12,8]4 extended code
gap> WeightDistribution(C);
[ 1, 0, 0, 0, 0, 0, 0, 0, 759, 0, 0, 0, 2576, 0, 0, 0, 759, 0, 0, 0, 0, 0, 0, 0, 1 ]
gap> IsDoublyEvenCode(C);
true
</pre></td></tr></table>
<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 <var class="Arg">C</var> is a binary self-orthogonal linear code which is not doubly-even. In other words, <var class="Arg">C</var> is a binary self-orthogonal code which has codewords of even weight.</p>
<table class="example">
<tr><td><pre>
gap> x:=Indeterminate(GF(2));
x_1
gap> C:=QuasiCyclicCode( [x^0, 1+x^3+x^5+x^6+x^7], 11, GF(2) );
a linear [22,11,1..6]4..7 quasi-cyclic code over GF(2)
gap> IsSelfDualCode(C); # self-dual is a restriction of self-orthogonal
true
gap> IsDoublyEvenCode(C);
false
gap> IsSinglyEvenCode(C);
true
</pre></td></tr></table>
<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 <var class="Arg">C</var> is a binary linear code which has codewords of even weight--regardless whether or not it is self-orthogonal.</p>
<table class="example">
<tr><td><pre>
gap> C:=BinaryGolayCode();
a cyclic [23,12,7]3 binary Golay code over GF(2)
gap> IsSelfOrthogonalCode(C);
false
gap> IsEvenCode(C);
false
gap> C:=ExtendedCode(C);
a linear [24,12,8]4 extended code
gap> IsSelfOrthogonalCode(C);
true
gap> IsEvenCode(C);
true
gap> C:=ExtendedCode(QRCode(17,GF(2)));
a linear [18,9,6]3..5 extended code
gap> IsSelfOrthogonalCode(C);
false
gap> IsEvenCode(C);
true
</pre></td></tr></table>
<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>
<p class="pcenter">
v \in C \Rightarrow 1 - v \in C,
</p>
<p>where 1 is the all-one word of length n.</p>
<table class="example">
<tr><td><pre>
gap> IsSelfComplementaryCode( HammingCode( 3, GF(2) ) );
true
gap> IsSelfComplementaryCode( EvenWeightSubcode(
> HammingCode( 3, GF(2) ) ) );
false
</pre></td></tr></table>
<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 <var class="Arg">C</var> is an affine code. A code is called <em>affine</em> if it is an affine space. In other words, a code is affine if it is a coset of a linear code.</p>
<table class="example">
<tr><td><pre>
gap> IsAffineCode( HammingCode( 3, GF(2) ) );
true
gap> IsAffineCode( CosetCode( HammingCode( 3, GF(2) ),
> [ 1, 0, 0, 0, 0, 0, 0 ] ) );
true
gap> IsAffineCode( NordstromRobinsonCode() );
false
</pre></td></tr></table>
<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 <var class="Arg">C</var> is an almost affine code. A code is called <em>almost affine</em> if the size of any punctured code of <var class="Arg">C</var> is q^r for some r, where q is the size of the alphabet of the code. Every affine code is also almost affine, and every code over GF(2) and GF(3) that is almost affine is also affine.</p>
<table class="example">
<tr><td><pre>
gap> code := ElementsCode( [ [0,0,0], [0,1,1], [0,2,2], [0,3,3],
> [1,0,1], [1,1,0], [1,2,3], [1,3,2],
> [2,0,2], [2,1,3], [2,2,0], [2,3,1],
> [3,0,3], [3,1,2], [3,2,1], [3,3,0] ],
> GF(4) );;
gap> IsAlmostAffineCode( code );
true
gap> IsAlmostAffineCode( NordstromRobinsonCode() );
false
</pre></td></tr></table>
<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, 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>
<table class="example">
<tr><td><pre>
gap> x:= Indeterminate( GF(2) );; pol:= x^3+x+1;
Z(2)^0+x_1+x_1^3
gap> H := GeneratorPolCode( pol, 7, GF(2));
a cyclic [7,4,1..3]1 code defined by generator polynomial over GF(2)
gap> H = HammingCode(3, GF(2));
false
gap> IsEquivalent(H, HammingCode(3, GF(2)));
true # H is equivalent to a Hamming code
gap> CodeIsomorphism(H, HammingCode(3, GF(2)));
(3,4)(5,6,7)
</pre></td></tr></table>
<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, 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"><b>4.4-1</b></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>
<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 <strong class="button">desauto</strong>).</p>
<table class="example">
<tr><td><pre>
gap> x:= Indeterminate( GF(2) );; pol:= x^3+x+1;
Z(2)^0+x_1+x_1^3
gap> H := GeneratorPolCode( pol, 7, GF(2));
a cyclic [7,4,1..3]1 code defined by generator polynomial over GF(2)
gap> CodeIsomorphism(H, HammingCode(3, GF(2)));
(3,4)(5,6,7)
gap> PermutedCode(H, (3,4)(5,6,7)) = HammingCode(3, GF(2));
true
</pre></td></tr></table>
<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 n 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 <code class="code">PermutationAutomorphismGroup</code>.</p>
<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>
<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"><b>6.1-4</b></a>)).</p>
<table class="example">
<tr><td><pre>
gap> R := RepetitionCode(7,GF(2));
a cyclic [7,1,7]3 repetition code over GF(2)
gap> AutomorphismGroup(R);
Sym( [ 1 .. 7 ] )
# every permutation keeps R identical
gap> C := CordaroWagnerCode(7);
a linear [7,2,4]3 Cordaro-Wagner code over GF(2)
gap> AsSSortedList(C);
[ [ 0 0 0 0 0 0 0 ], [ 0 0 1 1 1 1 1 ], [ 1 1 0 0 0 1 1 ], [ 1 1 1 1 1 0 0 ] ]
gap> AutomorphismGroup(C);
Group([ (3,4), (4,5), (1,6)(2,7), (1,2), (6,7) ])
gap> C2 := PermutedCode(C, (1,6)(2,7));
a linear [7,2,4]3 permuted code
gap> AsSSortedList(C2);
[ [ 0 0 0 0 0 0 0 ], [ 0 0 1 1 1 1 1 ], [ 1 1 0 0 0 1 1 ], [ 1 1 1 1 1 0 0 ] ]
gap> C2 = C;
true
</pre></td></tr></table>
<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 n such that each permutation applied to the columns of <var class="Arg">C</var> again yields <var class="Arg">C</var>. It is written in GAP, so is much slower than <code class="code">AutomorphismGroup</code>.</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>
<table class="example">
<tr><td><pre>
gap> R := RepetitionCode(3,GF(3));
a cyclic [3,1,3]2 repetition code over GF(3)
gap> G:=PermutationAutomorphismGroup(R);
Group([ (), (1,3), (1,2,3), (2,3), (1,3,2), (1,2) ])
gap> G=SymmetricGroup(3);
true
</pre></td></tr></table>
<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 on `Codes' is explained here.</p>
<p><a id="X808A4061809A6E67" name="X808A4061809A6E67"></a></p>
<h5>4.5-1 IsFinite</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsFinite</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">IsFinite</code> is an implementation of the GAP domain function <code class="code">IsFinite</code>. It returns true for a code <var class="Arg">C</var>.</p>
<table class="example">
<tr><td><pre>
gap> IsFinite( RepetitionCode( 1000, GF(11) ) );
true
</pre></td></tr></table>
<p><a id="X858ADA3B7A684421" name="X858ADA3B7A684421"></a></p>
<h5>4.5-2 Size</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Size</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">Size</code> returns the size of <var class="Arg">C</var>, the number of elements of the code. If the code is linear, the size of the code is equal to q^k, where q is the size of the base field of <var class="Arg">C</var> and k is the dimension.</p>
<table class="example">
<tr><td><pre>
gap> Size( RepetitionCode( 1000, GF(11) ) );
11
gap> Size( NordstromRobinsonCode() );
256
</pre></td></tr></table>
<p><a id="X86F070E0807DC34E" name="X86F070E0807DC34E"></a></p>
<h5>4.5-3 LeftActingDomain</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> LeftActingDomain</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">LeftActingDomain</code> returns the base field of a code <var class="Arg">C</var>. Each element of <var class="Arg">C</var> consists of elements of this base field. If the base field is F, and the word length of the code is n, then the codewords are elements of F^n. If <var class="Arg">C</var> is a cyclic code, its elements are interpreted as polynomials with coefficients over F.</p>
<table class="example">
<tr><td><pre>
gap> C1 := ElementsCode([[0,0,0], [1,0,1], [0,1,0]], GF(4));
a (3,3,1..3)2..3 user defined unrestricted code over GF(4)
gap> LeftActingDomain( C1 );
GF(2^2)
gap> LeftActingDomain( HammingCode( 3, GF(9) ) );
GF(3^2)
</pre></td></tr></table>
<p><a id="X7E6926C6850E7C4E" name="X7E6926C6850E7C4E"></a></p>
<h5>4.5-4 Dimension</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Dimension</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">Dimension</code> returns the parameter k of <var class="Arg">C</var>, the dimension of the code, or the number of information symbols in each codeword. The dimension is not defined for non-linear codes; <code class="code">Dimension</code> then returns an error.</p>
<table class="example">
<tr><td><pre>
gap> Dimension( NullCode( 5, GF(5) ) );
0
gap> C := BCHCode( 15, 4, GF(4) );
a cyclic [15,9,5]3..4 BCH code, delta=5, b=1 over GF(4)
gap> Dimension( C );
9
gap> Size( C ) = Size( LeftActingDomain( C ) ) ^ Dimension( C );
true
</pre></td></tr></table>
<p><a id="X856D927378C33548" name="X856D927378C33548"></a></p>
<h5>4.5-5 AsSSortedList</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AsSSortedList</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">AsSSortedList</code> (as strictly sorted list) returns an immutable, duplicate free list of the elements of <var class="Arg">C</var>. For a finite field GF(q) generated by powers of Z(q), the ordering on</p>
<p class="pcenter">
GF(q)=\{ 0 , Z(q)^0, Z(q), Z(q)^2, ...Z(q)^{q-2} \}
</p>
<p>is that determined by the exponents i. These elements are of the type codeword (see <code class="func">Codeword</code> (<a href="chap3.html#X7B9E353D852851AA"><b>3.1-1</b></a>)). Note that for large codes, generating the elements may be very time- and memory-consuming. For generating a specific element or a subset of the elements, use <code class="code">CodewordNr</code> (see <code class="func">CodewordNr</code> (<a href="chap3.html#X7E7ED91C79BF3EF3"><b>3.1-2</b></a>)).</p>
<table class="example">
<tr><td><pre>
gap> C := ConferenceCode( 5 );
a (5,12,2)1..4 conference code over GF(2)
gap> AsSSortedList( C );
[ [ 0 0 0 0 0 ], [ 0 0 1 1 1 ], [ 0 1 0 1 1 ], [ 0 1 1 0 1 ], [ 0 1 1 1 0 ],
[ 1 0 0 1 1 ], [ 1 0 1 0 1 ], [ 1 0 1 1 0 ], [ 1 1 0 0 1 ], [ 1 1 0 1 0 ],
[ 1 1 1 0 0 ], [ 1 1 1 1 1 ] ]
gap> CodewordNr( C, [ 1, 2 ] );
[ [ 0 0 0 0 0 ], [ 0 0 1 1 1 ] ]
</pre></td></tr></table>
<p><a id="X823827927D6A8235" name="X823827927D6A8235"></a></p>
<h4>4.6 <span class="Heading">
Printing and Displaying Codes
</span></h4>
<p><a id="X7AFA64D97A1F39A3" name="X7AFA64D97A1F39A3"></a></p>
<h5>4.6-1 Print</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Print</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">Print</code> prints information about <var class="Arg">C</var>. This is the same as typing the identifier <var class="Arg">C</var> at the GAP-prompt.</p>
<p>If the argument is an unrestricted code, information in the form</p>
<pre class="normal">
a (n,M,d)r ... code over GF(q)
</pre>
<p>is printed, where <var class="Arg">n</var> is the word length, <var class="Arg">M</var> the number of elements of the code, <var class="Arg">d</var> the minimum distance and <var class="Arg">r</var> the covering radius.</p>
<p>If the argument is a linear code, information in the form</p>
<pre class="normal">
a linear [n,k,d]r ... code over GF(q)
</pre>
<p>is printed, where <var class="Arg">n</var> is the word length, <var class="Arg">k</var> the dimension of the code, <var class="Arg">d</var> the minimum distance and <var class="Arg">r</var> the covering radius.</p>
<p>Except for codes produced by <code class="code">RandomLinearCode</code>, if <var class="Arg">d</var> is not yet known, it is displayed in the form</p>
<pre class="normal">
lowerbound..upperbound
</pre>
<p>and if <var class="Arg">r</var> is not yet known, it is displayed in the same way. For certain ranges of n, the values of <var class="Arg">lowerbound</var> and <var class="Arg">upperbound</var> are obtained from tables.</p>
<p>The function <code class="code">Display</code> gives more information. See <code class="func">Display</code> (<a href="chap4.html#X83A5C59278E13248"><b>4.6-3</b></a>).</p>
<table class="example">
<tr><td><pre>
gap> C1 := ExtendedCode( HammingCode( 3, GF(2) ) );
a linear [8,4,4]2 extended code
gap> Print( "This is ", NordstromRobinsonCode(), ". \n");
This is a (16,256,6)4 Nordstrom-Robinson code over GF(2).
</pre></td></tr></table>
<p><a id="X81FB5BE27903EC32" name="X81FB5BE27903EC32"></a></p>
<h5>4.6-2 String</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> String</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">String</code> returns information about <var class="Arg">C</var> in a string. This function is used by <code class="code">Print</code>.</p>
<table class="example">
<tr><td><pre>
gap> x:= Indeterminate( GF(3) );; pol:= x^2+1;
x_1^2+Z(3)^0
gap> Factors(pol);
[ x_1^2+Z(3)^0 ]
gap> H := GeneratorPolCode( pol, 8, GF(3));
a cyclic [8,6,1..2]1..2 code defined by generator polynomial over GF(3)
gap> String(H);
"a cyclic [8,6,1..2]1..2 code defined by generator polynomial over GF(3)"
</pre></td></tr></table>
<p><a id="X83A5C59278E13248" name="X83A5C59278E13248"></a></p>
<h5>4.6-3 Display</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Display</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">Display</code> prints the method of construction of code <var class="Arg">C</var>. With this history, in most cases an equal or equivalent code can be reconstructed. If <var class="Arg">C</var> is an unmanipulated code, the result is equal to output of the function <code class="code">Print</code> (see <code class="func">Print</code> (<a href="chap4.html#X7AFA64D97A1F39A3"><b>4.6-1</b></a>)).</p>
<table class="example">
<tr><td><pre>
gap> Display( RepetitionCode( 6, GF(3) ) );
a cyclic [6,1,6]4 repetition code over GF(3)
gap> C1 := ExtendedCode( HammingCode(2) );;
gap> C2 := PuncturedCode( ReedMullerCode( 2, 3 ) );;
gap> Display( LengthenedCode( UUVCode( C1, C2 ) ) );
a linear [12,8,2]2..4 code, lengthened with 1 column(s) of
a linear [11,8,1]1..2 U U+V construction code of
U: a linear [4,1,4]2 extended code of
a linear [3,1,3]1 Hamming (2,2) code over GF(2)
V: a linear [7,7,1]0 punctured code of
a cyclic [8,7,2]1 Reed-Muller (2,3) code over GF(2)
</pre></td></tr></table>
<p><a id="X7CD08C8C780543C4" name="X7CD08C8C780543C4"></a></p>
<h5>4.6-4 DisplayBoundsInfo</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> DisplayBoundsInfo</code>( <var class="Arg">bds</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">DisplayBoundsInfo</code> prints the method of construction of the code C indicated in <code class="code">bds:= BoundsMinimumDistance( n, k, GF(q) )</code>.</p>
<table class="example">
<tr><td><pre>
gap> bounds := BoundsMinimumDistance( 20, 17, GF(4) );
gap> DisplayBoundsInfo(bounds);
an optimal linear [20,17,d] code over GF(4) has d=3
--------------------------------------------------------------------------------------------------
Lb(20,17)=3, by shortening of:
Lb(21,18)=3, by applying contruction B to a [81,77,3] code
Lb(81,77)=3, by shortening of:
Lb(85,81)=3, reference: Ham
--------------------------------------------------------------------------------------------------
Ub(20,17)=3, by considering shortening to:
Ub(7,4)=3, by considering puncturing to:
Ub(6,4)=2, by construction B applied to:
Ub(2,1)=2, repetition code
--------------------------------------------------------------------------------------------------
Reference Ham:
%T this reference is unknown, for more info
%T contact A.E. Brouwer (aeb@cwi.nl)
</pre></td></tr></table>
<p><a id="X7D0F48B685A3ECDD" name="X7D0F48B685A3ECDD"></a></p>
<h4>4.7 <span class="Heading">
Generating (Check) Matrices and Polynomials
</span></h4>
<p><a id="X817224657C9829C4" name="X817224657C9829C4"></a></p>
<h5>4.7-1 GeneratorMat</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GeneratorMat</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">GeneratorMat</code> returns a generator matrix of <var class="Arg">C</var>. The code consists of all linear combinations of the rows of this matrix.</p>
<p>If until now no generator matrix of <var class="Arg">C</var> was determined, it is computed from either the parity check matrix, the generator polynomial, the check polynomial or the elements (if possible), whichever is available.</p>
<p>If <var class="Arg">C</var> is a non-linear code, the function returns an error.</p>
<table class="example">
<tr><td><pre>
gap> GeneratorMat( HammingCode( 3, GF(2) ) );
[ [ an immutable GF2 vector of length 7],
[ an immutable GF2 vector of length 7],
[ an immutable GF2 vector of length 7],
[ an immutable GF2 vector of length 7] ]
gap> Display(last);
1 1 1 . . . .
1 . . 1 1 . .
. 1 . 1 . 1 .
1 1 . 1 . . 1
gap> GeneratorMat( RepetitionCode( 5, GF(25) ) );
[ [ Z(5)^0, Z(5)^0, Z(5)^0, Z(5)^0, Z(5)^0 ] ]
gap> GeneratorMat( NullCode( 14, GF(4) ) );
[ ]
</pre></td></tr></table>
<p><a id="X85D4B26E7FB38D57" name="X85D4B26E7FB38D57"></a></p>
<h5>4.7-2 CheckMat</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> CheckMat</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">CheckMat</code> returns a parity check matrix of <var class="Arg">C</var>. The code consists of all words orthogonal to each of the rows of this matrix. The transpose of the matrix is a right inverse of the generator matrix. The parity check matrix is computed from either the generator matrix, the generator polynomial, the check polynomial or the elements of <var class="Arg">C</var> (if possible), whichever is available.</p>
<p>If <var class="Arg">C</var> is a non-linear code, the function returns an error.</p>
<table class="example">
<tr><td><pre>
gap> CheckMat( HammingCode(3, GF(2) ) );
[ [ 0*Z(2), 0*Z(2), 0*Z(2), Z(2)^0, Z(2)^0, Z(2)^0, Z(2)^0 ],
[ 0*Z(2), Z(2)^0, Z(2)^0, 0*Z(2), 0*Z(2), Z(2)^0, Z(2)^0 ],
[ Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2), Z(2)^0 ] ]
gap> Display(last);
. . . 1 1 1 1
. 1 1 . . 1 1
1 . 1 . 1 . 1
gap> CheckMat( RepetitionCode( 5, GF(25) ) );
[ [ Z(5)^0, Z(5)^2, 0*Z(5), 0*Z(5), 0*Z(5) ],
[ 0*Z(5), Z(5)^0, Z(5)^2, 0*Z(5), 0*Z(5) ],
[ 0*Z(5), 0*Z(5), Z(5)^0, Z(5)^2, 0*Z(5) ],
[ 0*Z(5), 0*Z(5), 0*Z(5), Z(5)^0, Z(5)^2 ] ]
gap> CheckMat( WholeSpaceCode( 12, GF(4) ) );
[ ]
</pre></td></tr></table>
<p><a id="X78E33C3A843B0261" name="X78E33C3A843B0261"></a></p>
<h5>4.7-3 GeneratorPol</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GeneratorPol</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">GeneratorPol</code> returns the generator polynomial of <var class="Arg">C</var>. The code consists of all multiples of the generator polynomial modulo x^n-1, where n is the word length of <var class="Arg">C</var>. The generator polynomial is determined from either the check polynomial, the generator or check matrix or the elements of <var class="Arg">C</var> (if possible), whichever is available.</p>
<p>If <var class="Arg">C</var> is not a cyclic code, the function returns `false'.</p>
<table class="example">
<tr><td><pre>
gap> GeneratorPol(GeneratorMatCode([[1, 1, 0], [0, 1, 1]], GF(2)));
Z(2)^0+x_1
gap> GeneratorPol( WholeSpaceCode( 4, GF(2) ) );
Z(2)^0
gap> GeneratorPol( NullCode( 7, GF(3) ) );
-Z(3)^0+x_1^7
</pre></td></tr></table>
<p><a id="X7C45AA317BB1195F" name="X7C45AA317BB1195F"></a></p>
<h5>4.7-4 CheckPol</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> CheckPol</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">CheckPol</code> returns the check polynomial of <var class="Arg">C</var>. The code consists of all polynomials f with</p>
<p class="pcenter">
f\cdot h \equiv 0 \ ({\rm mod}\ x^n-1),
</p>
<p>where h is the check polynomial, and n is the word length of <var class="Arg">C</var>. The check polynomial is computed from the generator polynomial, the generator or parity check matrix or the elements of <var class="Arg">C</var> (if possible), whichever is available.</p>
<p>If <var class="Arg">C</var> if not a cyclic code, the function returns an error.</p>
<table class="example">
<tr><td><pre>
gap> CheckPol(GeneratorMatCode([[1, 1, 0], [0, 1, 1]], GF(2)));
Z(2)^0+x_1+x_1^2
gap> CheckPol(WholeSpaceCode(4, GF(2)));
Z(2)^0+x_1^4
gap> CheckPol(NullCode(7,GF(3)));
Z(3)^0
</pre></td></tr></table>
<p><a id="X7F4CB9DB7CD97178" name="X7F4CB9DB7CD97178"></a></p>
<h5>4.7-5 RootsOfCode</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> RootsOfCode</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">RootsOfCode</code> returns a list of all zeros of the generator polynomial of a cyclic code <var class="Arg">C</var>. These are finite field elements in the splitting field of the generator polynomial, GF(q^m), m is the multiplicative order of the size of the base field of the code, modulo the word length.</p>
<p>The reverse process, constructing a code from a set of roots, can be carried out by the function <code class="code">RootsCode</code> (see <code class="func">RootsCode</code> (<a href="chap5.html#X818F0E6583E01D4B"><b>5.5-3</b></a>)).</p>
<table class="example">
<tr><td><pre>
gap> C1 := ReedSolomonCode( 16, 5 );
a cyclic [16,12,5]3..4 Reed-Solomon code over GF(17)
gap> RootsOfCode( C1 );
[ Z(17), Z(17)^2, Z(17)^3, Z(17)^4 ]
gap> C2 := RootsCode( 16, last );
a cyclic [16,12,5]3..4 code defined by roots over GF(17)
gap> C1 = C2;
true
</pre></td></tr></table>
<p><a id="X8170B52D7C154247" name="X8170B52D7C154247"></a></p>
<h4>4.8 <span class="Heading">
Parameters of Codes
</span></h4>
<p><a id="X7A36C3C67B0062E8" name="X7A36C3C67B0062E8"></a></p>
<h5>4.8-1 WordLength</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> WordLength</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">WordLength</code> returns the parameter n of <var class="Arg">C</var>, the word length of the elements. Elements of cyclic codes are polynomials of maximum degree n-1, as calculations are carried out modulo x^n-1.</p>
<table class="example">
<tr><td><pre>
gap> WordLength( NordstromRobinsonCode() );
16
gap> WordLength( PuncturedCode( WholeSpaceCode(7) ) );
6
gap> WordLength( UUVCode( WholeSpaceCode(7), RepetitionCode(7) ) );
14
</pre></td></tr></table>
<p><a id="X7E33FD56792DBF3D" name="X7E33FD56792DBF3D"></a></p>
<h5>4.8-2 Redundancy</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Redundancy</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">Redundancy</code> returns the redundancy r of <var class="Arg">C</var>, which is equal to the number of check symbols in each element. If <var class="Arg">C</var> is not a linear code the redundancy is not defined and <code class="code">Redundancy</code> returns an error.</p>
<p>If a linear code <var class="Arg">C</var> has dimension k and word length n, it has redundancy r=n-k.</p>
<table class="example">
<tr><td><pre>
gap> C := TernaryGolayCode();
a cyclic [11,6,5]2 ternary Golay code over GF(3)
gap> Redundancy(C);
5
gap> Redundancy( DualCode(C) );
6
</pre></td></tr></table>
<p><a id="X7B31613D8538BD29" name="X7B31613D8538BD29"></a></p>
<h5>4.8-3 MinimumDistance</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> MinimumDistance</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">MinimumDistance</code> returns the minimum distance of <var class="Arg">C</var>, the largest integer d with the property that every element of <var class="Arg">C</var> has at least a Hamming distance d (see <code class="func">DistanceCodeword</code> (<a href="chap3.html#X7CDA1B547D55E6FB"><b>3.6-2</b></a>)) to any other element of <var class="Arg">C</var>. For linear codes, the minimum distance is equal to the minimum weight. This means that d is also the smallest positive value with w[d+1] <> 0, where w=(w[1],w[2],...,w[n]) is the weight distribution of <var class="Arg">C</var> (see <code class="func">WeightDistribution</code> (<a href="chap4.html#X8728BCC9842A6E5D"><b>4.9-2</b></a>)). For unrestricted codes, d is the smallest positive value with w[d+1] <> 0, where w is the inner distribution of <var class="Arg">C</var> (see <code class="func">InnerDistribution</code> (<a href="chap4.html#X871FD301820717A4"><b>4.9-3</b></a>)).</p>
<p>For codes with only one element, the minimum distance is defined to be equal to the word length.</p>
<p>For linear codes <var class="Arg">C</var>, the algorithm used is the following: After replacing <var class="Arg">C</var> by a permutation equivalent <var class="Arg">C'</var>, one may assume the generator matrix has the following form G=(I_k , | , A), for some kx (n-k) matrix A. If A=0 then return d(C)=1. Next, find the minimum distance of the code spanned by the rows of A. Call this distance d(A). Note that d(A) is equal to the the Hamming distance d(v,0) where v is some proper linear combination of i distinct rows of A. Return d(C)=d(A)+i, where i is as in the previous step.</p>
<p>This command may also be called using the syntax <code class="code">MinimumDistance(C, w)</code>. In this form, <code class="code">MinimumDistance</code> returns the minimum distance of a codeword <var class="Arg">w</var> to the code <var class="Arg">C</var>, also called the <em>distance from <var class="Arg">w</var> to</em> <var class="Arg">C</var>. This is the smallest value d for which there is an element c of the code <var class="Arg">C</var> which is at distance d from <var class="Arg">w</var>. So d is also the minimum value for which D[d+1] <> 0, where D is the distance distribution of <var class="Arg">w</var> to <var class="Arg">C</var> (see <code class="func">DistancesDistribution</code> (<a href="chap4.html#X87AD54F87C5EE77E"><b>4.9-4</b></a>)).</p>
<p>Note that <var class="Arg">w</var> must be an element of the same vector space as the elements of <var class="Arg">C</var>. <var class="Arg">w</var> does not necessarily belong to the code (if it does, the minimum distance is zero).</p>
<table class="example">
<tr><td><pre>
gap> C := MOLSCode(7);; MinimumDistance(C);
3
gap> WeightDistribution(C);
[ 1, 0, 0, 24, 24 ]
gap> MinimumDistance( WholeSpaceCode( 5, GF(3) ) );
1
gap> MinimumDistance( NullCode( 4, GF(2) ) );
4
gap> C := ConferenceCode(9);; MinimumDistance(C);
4
gap> InnerDistribution(C);
[ 1, 0, 0, 0, 63/5, 9/5, 18/5, 0, 9/10, 1/10 ]
gap> C := MOLSCode(7);; w := CodewordNr( C, 17 );
[ 3 3 6 2 ]
gap> MinimumDistance( C, w );
0
gap> C := RemovedElementsCode( C, w );; MinimumDistance( C, w );
3 # so w no longer belongs to C
</pre></td></tr></table>
<p>See also the <strong class="pkg">GUAVA</strong> commands relating to bounds on the minimum distance in section <a href="chap7.html#X87C753EB840C34D3"><b>7.1</b></a>.</p>
<p><a id="X813F226F855590EE" name="X813F226F855590EE"></a></p>
<h5>4.8-4 MinimumDistanceLeon</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> MinimumDistanceLeon</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">MinimumDistanceLeon</code> returns the ``probable'' minimum distance d_Leon of a linear binary code <var class="Arg">C</var>, using an implementation of Leon's probabilistic polynomial time algorithm. Briefly: Let <var class="Arg">C</var> be a linear code of dimension k over GF(q) as above. The algorithm has input parameters s and rho, where s is an integer between 2 and n-k, and rho is an integer between 2 and k.</p>
<ul>
<li><p>Find a generator matrix G of C.</p>
</li>
<li><p>Randomly permute the columns of G.</p>
</li>
<li><p>Perform Gaussian elimination on the permuted matrix to obtain a new matrix of the following form:</p>
<p class="pcenter">
G=(I_{k} \, | \, Z \, | \, B)
</p>
<p>with Z a kx s matrix. If (Z,B) is the zero matrix then return 1 for the minimum distance. If Z=0 but not B then either choose another permutation of the rows of <var class="Arg">C</var> or return `method fails'.</p>
</li>
<li><p>Search Z for at most rho rows that lead to codewords of weight less than rho.</p>
</li>
<li><p>For these codewords, compute the weight of the whole word in <var class="Arg">C</var>. Return this weight.</p>
</li>
</ul>
<p>(See for example J. S. Leon, <a href="chapBib.html#biBLeon88">[Leo88]</a> for more details.) Sometimes (as is the case in <strong class="pkg">GUAVA</strong>) this probabilistic algorithm is repeated several times and the most commonly occurring value is taken. (This function actually has two optional arguments: <code class="code">p</code> and <code class="code">num</code>. The command <code class="code">MinimumDistanceLeon(C,p,num)</code> allows a bit more flexibility for the user - see the GAP code in codeops.gi for details.)</p>
<table class="example">
<tr><td><pre>
gap> C:=RandomLinearCode(50,22,GF(2));
a [50,22,?] randomly generated code over GF(2)
gap> MinimumDistanceLeon(C); time;
6
211
gap> MinimumDistance(C); time;
6
1204
</pre></td></tr></table>
<p><a id="X84EDF67B86B4154C" name="X84EDF67B86B4154C"></a></p>
<h5>4.8-5 MinimumWeight</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> MinimumWeight</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">MinimumWeight</code> returns the minimum Hamming weight of a linear code <var class="Arg">C</var>. At the moment, this function works for binary and ternary codes only. The <code class="code">MinimumWeight</code> function relies on an external executable program which is written in C language. As a consequence, the execution time of <code class="code">MinimumWeight</code> function is faster than that of <code class="func">MinimumDistance</code> (<a href="chap4.html#X7B31613D8538BD29"><b>4.8-3</b></a>) function.</p>
<p>The <code class="code">MinimumWeight</code> function implements Chen's <a href="chapBib.html#biBChen69">[Che69]</a> algorithm if <var class="Arg">C</var> is cyclic, and Zimmermann's <a href="chapBib.html#biBZimmermann96">[Zim96]</a> algorithm if <var class="Arg">C</var> is a general linear code. This function has a built-in check on the constraints of the minimum weight codewords. For example, for a self-orthogonal code over GF(3), the minimum weight codewords have weight that is divisible by 3, i.e. 0 mod 3 congruence. Similary, self-orthogonal codes over GF(2) have codeword weights that are divisible by 4 and even codes over GF(2) have codewords weights that are divisible by 2. By taking these constraints into account, in many cases, the execution time may be significantly reduced. Consider the minimum Hamming weight enumeration of the [151,45] binary cyclic code (second example below). This cyclic code is self-orthogonal, so the weight of all codewords is divisible by 4. Without considering this constraint, the computation will finish at information weight 10, rather than 9. We can see that, this 0 mod 4 constraint on the codeword weights, has allowed us to avoid enumeration of b(45,10) = 3,190,187,286 additional codewords, where b(n,k)=n!/((n-k)!k!) is the binomial coefficient of integers n and k.</p>
<p>Note that the C source code for this minimum weight computation has not yet been optimised, especially the code for GF(3), and there are chances to improve the speed of this function. Your contributions are most welcomed.</p>
<p>If you find any bugs on this function, please report it to ctjhai@plymouth.ac.uk.</p>
<table class="example">
<tr><td><pre>
gap> # Extended ternary quadratic residue code of length 48
gap> n := 47;;
gap> x := Indeterminate(GF(3));;
gap> F := Factors(x^n-1);;
gap> v := List([1..n], i->Zero(GF(3)));;
gap> v := v + MutableCopyMat(VectorCodeword( Codeword(F[2]) ));;
gap> G := CirculantMatrix(24, v);;
gap> for i in [1..Size(G)] do; s:=Zero(GF(3));
> for j in [1..Size(G[i])] do; s:=s+G[i][j]; od; Append(G[i], [ s ]);
> od;;
gap> C := GeneratorMatCodeNC(G, GF(3));
a [48,24,?] randomly generated code over GF(3)
gap> MinimumWeight(C);
[48,24] linear code over GF(3) - minimum weight evaluation
Known lower-bound: 1
There are 2 generator matrices, ranks : 24 24
The weight of the minimum weight codeword satisfies 0 mod 3 congruence
Enumerating codewords with information weight 1 (w=1)
Found new minimum weight 15
Number of matrices required for codeword enumeration 2
Completed w= 1, 48 codewords enumerated, lower-bound 6, upper-bound 15
Termination expected with information weight 6 at matrix 1
-----------------------------------------------------------------------------
Enumerating codewords with information weight 2 (w=2) using 2 matrices
Completed w= 2, 1104 codewords enumerated, lower-bound 6, upper-bound 15
Termination expected with information weight 6 at matrix 1
-----------------------------------------------------------------------------
Enumerating codewords with information weight 3 (w=3) using 2 matrices
Completed w= 3, 16192 codewords enumerated, lower-bound 9, upper-bound 15
Termination expected with information weight 6 at matrix 1
-----------------------------------------------------------------------------
Enumerating codewords with information weight 4 (w=4) using 2 matrices
Completed w= 4, 170016 codewords enumerated, lower-bound 12, upper-bound 15
Termination expected with information weight 6 at matrix 1
-----------------------------------------------------------------------------
Enumerating codewords with information weight 5 (w=5) using 2 matrices
Completed w= 5, 1360128 codewords enumerated, lower-bound 12, upper-bound 15
Termination expected with information weight 6 at matrix 1
-----------------------------------------------------------------------------
Enumerating codewords with information weight 6 (w=6) using 1 matrices
Completed w= 6, 4307072 codewords enumerated, lower-bound 15, upper-bound 15
-----------------------------------------------------------------------------
Minimum weight: 15
15
gap>
gap> # Binary cyclic code [151,45,36]
gap> n := 151;;
gap> x := Indeterminate(GF(2));;
gap> F := Factors(x^n-1);;
gap> C := CheckPolCode(F[2]*F[3]*F[3]*F[4], n, GF(2));
a cyclic [151,45,1..50]31..75 code defined by check polynomial over GF(2)
gap> MinimumWeight(C);
[151,45] cyclic code over GF(2) - minimum weight evaluation
Known lower-bound: 1
The weight of the minimum weight codeword satisfies 0 mod 4 congruence
Enumerating codewords with information weight 1 (w=1)
Found new minimum weight 56
Found new minimum weight 44
Number of matrices required for codeword enumeration 1
Completed w= 1, 45 codewords enumerated, lower-bound 8, upper-bound 44
Termination expected with information weight 11
-----------------------------------------------------------------------------
Enumerating codewords with information weight 2 (w=2) using 1 matrix
Completed w= 2, 990 codewords enumerated, lower-bound 12, upper-bound 44
Termination expected with information weight 11
-----------------------------------------------------------------------------
Enumerating codewords with information weight 3 (w=3) using 1 matrix
Found new minimum weight 40
Found new minimum weight 36
Completed w= 3, 14190 codewords enumerated, lower-bound 16, upper-bound 36
Termination expected with information weight 9
-----------------------------------------------------------------------------
Enumerating codewords with information weight 4 (w=4) using 1 matrix
Completed w= 4, 148995 codewords enumerated, lower-bound 20, upper-bound 36
Termination expected with information weight 9
-----------------------------------------------------------------------------
Enumerating codewords with information weight 5 (w=5) using 1 matrix
Completed w= 5, 1221759 codewords enumerated, lower-bound 24, upper-bound 36
Termination expected with information weight 9
-----------------------------------------------------------------------------
Enumerating codewords with information weight 6 (w=6) using 1 matrix
Completed w= 6, 8145060 codewords enumerated, lower-bound 24, upper-bound 36
Termination expected with information weight 9
-----------------------------------------------------------------------------
Enumerating codewords with information weight 7 (w=7) using 1 matrix
Completed w= 7, 45379620 codewords enumerated, lower-bound 28, upper-bound 36
Termination expected with information weight 9
-----------------------------------------------------------------------------
Enumerating codewords with information weight 8 (w=8) using 1 matrix
Completed w= 8, 215553195 codewords enumerated, lower-bound 32, upper-bound 36
Termination expected with information weight 9
-----------------------------------------------------------------------------
Enumerating codewords with information weight 9 (w=9) using 1 matrix
Completed w= 9, 886163135 codewords enumerated, lower-bound 36, upper-bound 36
-----------------------------------------------------------------------------
Minimum weight: 36
36
</pre></td></tr></table>
<p><a id="X823B9A797EE42F6D" name="X823B9A797EE42F6D"></a></p>
<h5>4.8-6 DecreaseMinimumDistanceUpperBound</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> DecreaseMinimumDistanceUpperBound</code>( <var class="Arg">C, t, m</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">DecreaseMinimumDistanceUpperBound</code> is an implementation of the algorithm for the minimum distance of a linear binary code <var class="Arg">C</var> by Leon <a href="chapBib.html#biBLeon88">[Leo88]</a>. This algorithm tries to find codewords with small minimum weights. The parameter <var class="Arg">t</var> is at least 1 and less than the dimension of <var class="Arg">C</var>. The best results are obtained if it is close to the dimension of the code. The parameter <var class="Arg">m</var> gives the number of runs that the algorithm will perform.</p>
<p>The result returned is a record with two fields; the first, <code class="code">mindist</code>, gives the lowest weight found, and <code class="code">word</code> gives the corresponding codeword. (This was implemented before <code class="code">MinimumDistanceLeon</code> but independently. The older manual had given the command incorrectly, so the command was only found after reading all the <em>*.gi</em> files in the <strong class="pkg">GUAVA</strong> library. Though both <code class="code">MinimumDistance</code> and <code class="code">MinimumDistanceLeon</code> often run much faster than <code class="code">DecreaseMinimumDistanceUpperBound</code>, <code class="code">DecreaseMinimumDistanceUpperBound</code> appears to be more accurate than <code class="code">MinimumDistanceLeon</code>.)</p>
<table class="example">
<tr><td><pre>
gap> C:=RandomLinearCode(5,2,GF(2));
a [5,2,?] randomly generated code over GF(2)
gap> DecreaseMinimumDistanceUpperBound(C,1,4);
rec( mindist := 3, word := [ 0*Z(2), Z(2)^0, Z(2)^0, 0*Z(2), Z(2)^0 ] )
gap> MinimumDistance(C);
3
gap> C:=RandomLinearCode(8,4,GF(2));
a [8,4,?] randomly generated code over GF(2)
gap> DecreaseMinimumDistanceUpperBound(C,3,4);
rec( mindist := 2,
word := [ Z(2)^0, 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), Z(2)^0 ] )
gap> MinimumDistance(C);
2
</pre></td></tr></table>
<p><a id="X7A679B0A7816B030" name="X7A679B0A7816B030"></a></p>
<h5>4.8-7 MinimumDistanceRandom</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> MinimumDistanceRandom</code>( <var class="Arg">C, num, s</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">MinimumDistanceRandom</code> returns an upper bound for the minimum distance d_random of a linear binary code <var class="Arg">C</var>, using a probabilistic polynomial time algorithm. Briefly: Let <var class="Arg">C</var> be a linear code of dimension k over GF(q) as above. The algorithm has input parameters num and s, where s is an integer between 2 and n-1, and num is an integer greater than or equal to 1.</p>
<ul>
<li><p>Find a generator matrix G of C.</p>
</li>
<li><p>Randomly permute the columns of G, written G_p..</p>
</li>
<li><p class="pcenter">
G=(A, B)
</p>
<p>with A a kx s matrix. If A is the zero matrix then return `method fails'.</p>
</li>
<li><p>Search A for at most 5 rows that lead to codewords, in the code C_A with generator matrix A, of minimum weight.</p>
</li>
<li><p>For these codewords, use the associated linear combination to compute the weight of the whole word in <var class="Arg">C</var>. Return this weight and codeword.</p>
</li>
</ul>
<p>This probabilistic algorithm is repeated <var class="Arg">num</var> times (with different random permutations of the rows of G each time) and the weight and codeword of the lowest occurring weight is taken.</p>
<table class="example">
<tr><td><pre>
gap> C:=RandomLinearCode(60,20,GF(2));
a [60,20,?] randomly generated code over GF(2)
gap> #mindist(C);time;
gap> #mindistleon(C,10,30);time; #doesn't work well
gap> a:=MinimumDistanceRandom(C,10,30);time; # done 10 times -with fastest time!!
This is a probabilistic algorithm which may return the wrong answer.
[ 12, [ 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0
1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 ] ]
130
gap> a[2] in C;
true
gap> b:=DecreaseMinimumDistanceUpperBound(C,10,1); time; #only done once!
rec( mindist := 12, word := [ 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2),
Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2),
0*Z(2), Z(2)^0, Z(2)^0, 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2), 0*Z(2),
Z(2)^0, 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2),
0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2),
0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2),
0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2) ] )
649
gap> Codeword(b!.word) in C;
true
gap> MinimumDistance(C);time;
12
196
gap> c:=MinimumDistanceLeon(C);time;
12
66
gap> C:=RandomLinearCode(30,10,GF(3));
a [30,10,?] randomly generated code over GF(3)
gap> a:=MinimumDistanceRandom(C,10,10);time;
This is a probabilistic algorithm which may return the wrong answer.
[ 13, [ 0 0 0 1 0 0 0 0 0 0 1 0 2 2 1 1 0 2 2 0 1 0 2 1 0 0 0 1 0 2 ] ]
229
gap> a[2] in C;
true
gap> MinimumDistance(C);time;
9
45
gap> c:=MinimumDistanceLeon(C);
Code must be binary. Quitting.
0
gap> a:=MinimumDistanceRandom(C,1,29);time;
This is a probabilistic algorithm which may return the wrong answer.
[ 10, [ 0 0 1 0 2 0 2 0 1 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 2 2 2 0 ] ]
53
</pre></td></tr></table>
<p><a id="X7A195E317D2AB7CE" name="X7A195E317D2AB7CE"></a></p>
<h5>4.8-8 CoveringRadius</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> CoveringRadius</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">CoveringRadius</code> returns the <em>covering radius</em> of a linear code <var class="Arg">C</var>. This is the smallest number r with the property that each element v of the ambient vector space of <var class="Arg">C</var> has at most a distance r to the code <var class="Arg">C</var>. So for each vector v there must be an element c of <var class="Arg">C</var> with d(v,c) <= r. The smallest covering radius of any [n,k] binary linear code is denoted t(n,k). A binary linear code with reasonable small covering radius is called a <em>covering code</em>.</p>
<p>If <var class="Arg">C</var> is a perfect code (see <code class="func">IsPerfectCode</code> (<a href="chap4.html#X85E3BD26856424F7"><b>4.3-6</b></a>)), the covering radius is equal to t, the number of errors the code can correct, where d = 2t+1, with d the minimum distance of <var class="Arg">C</var> (see <code class="func">MinimumDistance</code> (<a href="chap4.html#X7B31613D8538BD29"><b>4.8-3</b></a>)).</p>
<p>If there exists a function called <code class="code">SpecialCoveringRadius</code> in the `operations' field of the code, then this function will be called to compute the covering radius of the code. At the moment, no code-specific functions are implemented.</p>
<p>If the length of <code class="code">BoundsCoveringRadius</code> (see <code class="func">BoundsCoveringRadius</code> (<a href="chap7.html#X8320D1C180A1AAAD"><b>7.2-1</b></a>)), is 1, then the value in</p>
<pre class="normal">
C.boundsCoveringRadius
</pre>
<p>is returned. Otherwise, the function</p>
<pre class="normal">
C.operations.CoveringRadius
</pre>
<p>is executed, unless the redundancy of <var class="Arg">C</var> is too large. In the last case, a warning is issued.</p>
<p>The algorithm used to compute the covering radius is the following. First, <code class="code">CosetLeadersMatFFE</code> is used to compute the list of coset leaders (which returns a codeword in each coset of GF(q)^n/C of minimum weight). Then <code class="code">WeightVecFFE</code> is used to compute the weight of each of these coset leaders. The program returns the maximum of these weights.</p>
<table class="example">
<tr><td><pre>
gap> H := RandomLinearCode(10, 5, GF(2));
a [10,5,?] randomly generated code over GF(2)
gap> CoveringRadius(H);
3
gap> H := HammingCode(4, GF(2));; IsPerfectCode(H);
true
gap> CoveringRadius(H);
1 # Hamming codes have minimum distance 3
gap> CoveringRadius(ReedSolomonCode(7,4));
3
gap> CoveringRadius( BCHCode( 17, 3, GF(2) ) );
3
gap> CoveringRadius( HammingCode( 5, GF(2) ) );
1
gap> C := ReedMullerCode( 1, 9 );;
gap> CoveringRadius( C );
CoveringRadius: warning, the covering radius of
this code cannot be computed straightforward.
Try to use IncreaseCoveringRadiusLowerBound( code ).
(see the manual for more details).
The covering radius of code lies in the interval:
[ 240 .. 248 ]
</pre></td></tr></table>
<p>See also the <strong class="pkg">GUAVA</strong> commands relating to bounds on the minimum distance in section <a href="chap7.html#X817D0A647D3331EB"><b>7.2</b></a>.</p>
<p><a id="X81004B007EC5DF58" name="X81004B007EC5DF58"></a></p>
<h5>4.8-9 SetCoveringRadius</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> SetCoveringRadius</code>( <var class="Arg">C, intlist</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">SetCoveringRadius</code> enables the user to set the covering radius herself, instead of letting <strong class="pkg">GUAVA</strong> compute it. If <var class="Arg">intlist</var> is an integer, <strong class="pkg">GUAVA</strong> will simply put it in the `boundsCoveringRadius' field. If it is a list of integers, however, it will intersect this list with the `boundsCoveringRadius' field, thus taking the best of both lists. If this would leave an empty list, the field is set to <var class="Arg">intlist</var>. Because some other computations use the covering radius of the code, it is important that the entered value is not wrong, otherwise new results may be invalid.</p>
<table class="example">
<tr><td><pre>
gap> C := BCHCode( 17, 3, GF(2) );;
gap> BoundsCoveringRadius( C );
[ 3 .. 4 ]
gap> SetCoveringRadius( C, [ 2 .. 3 ] );
gap> BoundsCoveringRadius( C );
[ [ 2 .. 3 ] ]
</pre></td></tr></table>
<p><a id="X806384B4815EFF2E" name="X806384B4815EFF2E"></a></p>
<h4>4.9 <span class="Heading">
Distributions
</span></h4>
<p><a id="X7AEE64467FB1E0B9" name="X7AEE64467FB1E0B9"></a></p>
<h5>4.9-1 MinimumWeightWords</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> MinimumWeightWords</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">MinimumWeightWords</code> returns the list of minimum weight codewords of <var class="Arg">C</var>.</p>
<p>This algorithm is written in GAP is slow, so is only suitable for small codes.</p>
<p>This does not call the very fast function <code class="code">MinimumWeight</code> (see <code class="func">MinimumWeight</code> (<a href="chap4.html#X84EDF67B86B4154C"><b>4.8-5</b></a>)).</p>
<table class="example">
<tr><td><pre>
gap> C:=HammingCode(3,GF(2));
a linear [7,4,3]1 Hamming (3,2) code over GF(2)
gap> MinimumWeightWords(C);
[ [ 1 0 0 0 0 1 1 ], [ 0 1 0 1 0 1 0 ], [ 0 1 0 0 1 0 1 ], [ 1 0 0 1 1 0 0 ], [ 0 0 1 0 1 1 0 ],
[ 0 0 1 1 0 0 1 ], [ 1 1 1 0 0 0 0 ] ]
</pre></td></tr></table>
<p><a id="X8728BCC9842A6E5D" name="X8728BCC9842A6E5D"></a></p>
<h5>4.9-2 WeightDistribution</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> WeightDistribution</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">WeightDistribution</code> returns the weight distribution of <var class="Arg">C</var>, as a vector. The i^th element of this vector contains the number of elements of <var class="Arg">C</var> with weight i-1. For linear codes, the weight distribution is equal to the inner distribution (see <code class="func">InnerDistribution</code> (<a href="chap4.html#X871FD301820717A4"><b>4.9-3</b></a>)). If w is the weight distribution of a linear code <var class="Arg">C</var>, it must have the zero codeword, so w[1] = 1 (one word of weight 0).</p>
<p>Some codes, such as the Hamming codes, have precomputed weight distributions. For others, the program WeightDistribution calls the GAP program <code class="code">DistancesDistributionMatFFEVecFFE</code>, which is written in C. See also <code class="code">CodeWeightEnumerator</code>.</p>
<table class="example">
<tr><td><pre>
gap> WeightDistribution( ConferenceCode(9) );
[ 1, 0, 0, 0, 0, 18, 0, 0, 0, 1 ]
gap> WeightDistribution( RepetitionCode( 7, GF(4) ) );
[ 1, 0, 0, 0, 0, 0, 0, 3 ]
gap> WeightDistribution( WholeSpaceCode( 5, GF(2) ) );
[ 1, 5, 10, 10, 5, 1 ]
</pre></td></tr></table>
<p><a id="X871FD301820717A4" name="X871FD301820717A4"></a></p>
<h5>4.9-3 InnerDistribution</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> InnerDistribution</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">InnerDistribution</code> returns the inner distribution of <var class="Arg">C</var>. The i^th element of the vector contains the average number of elements of <var class="Arg">C</var> at distance i-1 to an element of <var class="Arg">C</var>. For linear codes, the inner distribution is equal to the weight distribution (see <code class="func">WeightDistribution</code> (<a href="chap4.html#X8728BCC9842A6E5D"><b>4.9-2</b></a>)).</p>
<p>Suppose w is the inner distribution of <var class="Arg">C</var>. Then w[1] = 1, because each element of <var class="Arg">C</var> has exactly one element at distance zero (the element itself). The minimum distance of <var class="Arg">C</var> is the smallest value d > 0 with w[d+1] <> 0, because a distance between zero and d never occurs. See <code class="func">MinimumDistance</code> (<a href="chap4.html#X7B31613D8538BD29"><b>4.8-3</b></a>).</p>
<table class="example">
<tr><td><pre>
gap> InnerDistribution( ConferenceCode(9) );
[ 1, 0, 0, 0, 63/5, 9/5, 18/5, 0, 9/10, 1/10 ]
gap> InnerDistribution( RepetitionCode( 7, GF(4) ) );
[ 1, 0, 0, 0, 0, 0, 0, 3 ]
</pre></td></tr></table>
<p><a id="X87AD54F87C5EE77E" name="X87AD54F87C5EE77E"></a></p>
<h5>4.9-4 DistancesDistribution</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> DistancesDistribution</code>( <var class="Arg">C, w</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">DistancesDistribution</code> returns the distribution of the distances of all elements of <var class="Arg">C</var> to a codeword <var class="Arg">w</var> in the same vector space. The i^th element of the distance distribution is the number of codewords of <var class="Arg">C</var> that have distance i-1 to <var class="Arg">w</var>. The smallest value d with w[d+1] <> 0, is defined as the <em>distance to</em> <var class="Arg">C</var> (see <code class="func">MinimumDistance</code> (<a href="chap4.html#X7B31613D8538BD29"><b>4.8-3</b></a>)).</p>
<table class="example">
<tr><td><pre>
gap> H := HadamardCode(20);
a (20,40,10)6..8 Hadamard code of order 20 over GF(2)
gap> c := Codeword("10110101101010010101", H);
[ 1 0 1 1 0 1 0 1 1 0 1 0 1 0 0 1 0 1 0 1 ]
gap> DistancesDistribution(H, c);
[ 0, 0, 0, 0, 0, 1, 0, 7, 0, 12, 0, 12, 0, 7, 0, 1, 0, 0, 0, 0, 0 ]
gap> MinimumDistance(H, c);
5 # distance to H
</pre></td></tr></table>
<p><a id="X8495870687195324" name="X8495870687195324"></a></p>
<h5>4.9-5 OuterDistribution</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> OuterDistribution</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The function <code class="code">OuterDistribution</code> returns a list of length q^n, where q is the size of the base field of <var class="Arg">C</var> and n is the word length. The elements of the list consist of pairs, the first coordinate being an element of GF(q)^n (this is a codeword type) and the second coordinate being a distribution of distances to the code (a list of integers). This table is <em>very</em> large, and for n > 20 it will not fit in the memory of most computers. The function <code class="code">DistancesDistribution</code> (see <code class="func">DistancesDistribution</code> (<a href="chap4.html#X87AD54F87C5EE77E"><b>4.9-4</b></a>)) can be used to calculate one entry of the list.</p>
<table class="example">
<tr><td><pre>
gap> C := RepetitionCode( 3, GF(2) );
a cyclic [3,1,3]1 repetition code over GF(2)
gap> OD := OuterDistribution(C);
[ [ [ 0 0 0 ], [ 1, 0, 0, 1 ] ], [ [ 1 1 1 ], [ 1, 0, 0, 1 ] ],
[ [ 0 0 1 ], [ 0, 1, 1, 0 ] ], [ [ 1 1 0 ], [ 0, 1, 1, 0 ] ],
[ [ 1 0 0 ], [ 0, 1, 1, 0 ] ], [ [ 0 1 1 ], [ 0, 1, 1, 0 ] ],
[ [ 0 1 0 ], [ 0, 1, 1, 0 ] ], [ [ 1 0 1 ], [ 0, 1, 1, 0 ] ] ]
gap> WeightDistribution(C) = OD[1][2];
true
gap> DistancesDistribution( C, Codeword("110") ) = OD[4][2];
true
</pre></td></tr></table>
<p><a id="X7D9A39BF801948C8" name="X7D9A39BF801948C8"></a></p>
<h4>4.10 <span class="Heading">
Decoding Functions
</span></h4>
<p><a id="X7A42FF7D87FC34AC" name="X7A42FF7D87FC34AC"></a></p>
<h5>4.10-1 Decode</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Decode</code>( <var class="Arg">C, r</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">Decode</code> decodes <var class="Arg">r</var> (a 'received word') with respect to code <var class="Arg">C</var> and returns the `message word' (i.e., the information digits associated to the codeword c in C closest to <var class="Arg">r</var>). Here <var class="Arg">r</var> can be a <strong class="pkg">GUAVA</strong> codeword or a list of codewords. First, possible errors in <var class="Arg">r</var> are corrected, then the codeword is decoded to an <em>information codeword</em> m (and not an element of <var class="Arg">C</var>). If the code record has a field `specialDecoder', this special algorithm is used to decode the vector. Hamming codes, cyclic codes, and generalized Reed-Solomon have such a special algorithm. (The algorithm used for BCH codes is the Sugiyama algorithm described, for example, in section 5.4.3 of <a href="chapBib.html#biBHP03">[HP03]</a>. A special decoder has also being written for the generalized Reed-Solomon code using the interpolation algorithm. For cyclic codes, the error-trapping algorithm is used.) If <var class="Arg">C</var> is linear and no special decoder field has been set then syndrome decoding is used. Otherwise (when <var class="Arg">C</var> is non-linear), the nearest neighbor decoding algorithm is used (which is very slow).</p>
<p>A special decoder can be created by defining a function</p>
<pre class="normal">
C!.SpecialDecoder := function(C, r) ... end;
</pre>
<p>The function uses the arguments <var class="Arg">C</var> (the code record itself) and <var class="Arg">r</var> (a vector of the codeword type) to decode <var class="Arg">r</var> to an information vector. A normal decoder would take a codeword <var class="Arg">r</var> of the same word length and field as <var class="Arg">C</var>, and would return an information vector of length k, the dimension of <var class="Arg">C</var>. The user is not restricted to these normal demands though, and can for instance define a decoder for non-linear codes.</p>
<p>Encoding is done by multiplying the information vector with the code (see <a href="chap4.html#X832DA51986A3882C"><b>4.2</b></a>).</p>
<table class="example">
<tr><td><pre>
gap> C := HammingCode(3);
a linear [7,4,3]1 Hamming (3,2) code over GF(2)
gap> c := "1010"*C; # encoding
[ 1 0 1 1 0 1 0 ]
gap> Decode(C, c); # decoding
[ 1 0 1 0 ]
gap> Decode(C, Codeword("0010101"));
[ 1 1 0 1 ] # one error corrected
gap> C!.SpecialDecoder := function(C, c)
> return NullWord(Dimension(C));
> end;
function ( C, c ) ... end
gap> Decode(C, c);
[ 0 0 0 0 ] # new decoder always returns null word
</pre></td></tr></table>
<p><a id="X7D870C9387C47D9F" name="X7D870C9387C47D9F"></a></p>
<h5>4.10-2 Decodeword</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Decodeword</code>( <var class="Arg">C, r</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">Decodeword</code> decodes <var class="Arg">r</var> (a 'received word') with respect to code <var class="Arg">C</var> and returns the codeword c in C closest to <var class="Arg">r</var>. Here <var class="Arg">r</var> can be a <strong class="pkg">GUAVA</strong> codeword or a list of codewords. If the code record has a field `specialDecoder', this special algorithm is used to decode the vector. Hamming codes, generalized Reed-Solomon codes, and BCH codes have such a special algorithm. (The algorithm used for BCH codes is the Sugiyama algorithm described, for example, in section 5.4.3 of <a href="chapBib.html#biBHP03">[HP03]</a>. The algorithm used for generalized Reed-Solomon codes is the ``interpolation algorithm'' described for example in chapter 5 of <a href="chapBib.html#biBJH04">[JH04]</a>.) If <var class="Arg">C</var> is linear and no special decoder field has been set then syndrome decoding is used. Otherwise, when <var class="Arg">C</var> is non-linear, the nearest neighbor algorithm has been implemented (which should only be used for small-sized codes).</p>
<table class="example">
<tr><td><pre>
gap> C := HammingCode(3);
a linear [7,4,3]1 Hamming (3,2) code over GF(2)
gap> c := "1010"*C; # encoding
[ 1 0 1 1 0 1 0 ]
gap> Decodeword(C, c); # decoding
[ 1 0 1 1 0 1 0 ]
gap>
gap> R:=PolynomialRing(GF(11),["t"]);
GF(11)[t]
gap> P:=List([1,3,4,5,7],i->Z(11)^i);
[ Z(11), Z(11)^3, Z(11)^4, Z(11)^5, Z(11)^7 ]
gap> C:=GeneralizedReedSolomonCode(P,3,R);
a linear [5,3,1..3]2 generalized Reed-Solomon code over GF(11)
gap> MinimumDistance(C);
3
gap> c:=Random(C);
[ 0 9 6 2 1 ]
gap> v:=Codeword("09620");
[ 0 9 6 2 0 ]
gap> GeneralizedReedSolomonDecoderGao(C,v);
[ 0 9 6 2 1 ]
gap> Decodeword(C,v); # calls the special interpolation decoder
[ 0 9 6 2 1 ]
gap> G:=GeneratorMat(C);
[ [ Z(11)^0, 0*Z(11), 0*Z(11), Z(11)^8, Z(11)^9 ],
[ 0*Z(11), Z(11)^0, 0*Z(11), Z(11)^0, Z(11)^8 ],
[ 0*Z(11), 0*Z(11), Z(11)^0, Z(11)^3, Z(11)^8 ] ]
gap> C1:=GeneratorMatCode(G,GF(11));
a linear [5,3,1..3]2 code defined by generator matrix over GF(11)
gap> Decodeword(C,v); # calls syndrome decoding
[ 0 9 6 2 1 ]
</pre></td></tr></table>
<p><a id="X7D48DE2A84474C6A" name="X7D48DE2A84474C6A"></a></p>
<h5>4.10-3 GeneralizedReedSolomonDecoderGao</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GeneralizedReedSolomonDecoderGao</code>( <var class="Arg">C, r</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">GeneralizedReedSolomonDecoderGao</code> decodes <var class="Arg">r</var> (a 'received word') to a codeword c in C in a generalized Reed-Solomon code <var class="Arg">C</var> (see <code class="func">GeneralizedReedSolomonCode</code> (<a href="chap5.html#X810AB3DB844FFCE9"><b>5.6-2</b></a>)), closest to <var class="Arg">r</var>. Here <var class="Arg">r</var> must be a <strong class="pkg">GUAVA</strong> codeword. If the code record does not have name `generalized Reed-Solomon code' then an error is returned. Otherwise, the Gao decoder <a href="chapBib.html#biBGao03">[Gao03]</a> is used to compute c.</p>
<p>For long codes, this method is faster in practice than the interpolation method used in <code class="code">Decodeword</code>.</p>
<table class="example">
<tr><td><pre>
gap> R:=PolynomialRing(GF(11),["t"]);
GF(11)[t]
gap> P:=List([1,3,4,5,7],i->Z(11)^i);
[ Z(11), Z(11)^3, Z(11)^4, Z(11)^5, Z(11)^7 ]
gap> C:=GeneralizedReedSolomonCode(P,3,R);
a linear [5,3,1..3]2 generalized Reed-Solomon code over GF(11)
gap> MinimumDistance(C);
3
gap> c:=Random(C);
[ 0 9 6 2 1 ]
gap> v:=Codeword("09620");
[ 0 9 6 2 0 ]
gap> GeneralizedReedSolomonDecoderGao(C,v);
[ 0 9 6 2 1 ]
</pre></td></tr></table>
<p><a id="X7CFF98D483502053" name="X7CFF98D483502053"></a></p>
<h5>4.10-4 GeneralizedReedSolomonListDecoder</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GeneralizedReedSolomonListDecoder</code>( <var class="Arg">C, r, tau</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">GeneralizedReedSolomonListDecoder</code> implements Sudans list-decoding algorithm (see section 12.1 of <a href="chapBib.html#biBJH04">[JH04]</a>) for ``low rate'' Reed-Solomon codes. It returns the list of all codewords in C which are a distance of at most <var class="Arg">tau</var> from <var class="Arg">r</var> (a 'received word'). <var class="Arg">C</var> must be a generalized Reed-Solomon code <var class="Arg">C</var> (see <code class="func">GeneralizedReedSolomonCode</code> (<a href="chap5.html#X810AB3DB844FFCE9"><b>5.6-2</b></a>)) and <var class="Arg">r</var> must be a <strong class="pkg">GUAVA</strong> codeword.</p>
<table class="example">
<tr><td><pre>
gap> F:=GF(16);
GF(2^4)
gap>
gap> a:=PrimitiveRoot(F);; b:=a^7;; b^4+b^3+1;
0*Z(2)
gap> Pts:=List([0..14],i->b^i);
[ Z(2)^0, Z(2^4)^7, Z(2^4)^14, Z(2^4)^6, Z(2^4)^13, Z(2^2), Z(2^4)^12, Z(2^4)^4,
Z(2^4)^11, Z(2^4)^3, Z(2^2)^2, Z(2^4)^2, Z(2^4)^9, Z(2^4), Z(2^4)^8 ]
gap> x:=X(F);;
gap> R1:=PolynomialRing(F,[x]);;
gap> vars:=IndeterminatesOfPolynomialRing(R1);;
gap> y:=X(F,vars);;
gap> R2:=PolynomialRing(F,[x,y]);;
gap> C:=GeneralizedReedSolomonCode(Pts,3,R1);
a linear [15,3,1..13]10..12 generalized Reed-Solomon code over GF(16)
gap> MinimumDistance(C); ## 6 error correcting
13
gap> z:=Zero(F);;
gap> r:=[z,z,z,z,z,z,z,z,b^6,b^2,b^5,b^14,b,b^7,b^11];;
gap> r:=Codeword(r);
[ 0 0 0 0 0 0 0 0 a^12 a^14 a^5 a^8 a^7 a^4 a^2 ]
gap> cs:=GeneralizedReedSolomonListDecoder(C,r,2); time;
[ [ 0 a^9 a^3 a^13 a^6 a^10 a^11 a a^12 a^14 a^5 a^8 a^7 a^4 a^2 ],
[ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ] ]
250
gap> c1:=cs[1]; c1 in C;
[ 0 a^9 a^3 a^13 a^6 a^10 a^11 a a^12 a^14 a^5 a^8 a^7 a^4 a^2 ]
true
gap> c2:=cs[2]; c2 in C;
[ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
true
gap> WeightCodeword(c1-r);
7
gap> WeightCodeword(c2-r);
7
</pre></td></tr></table>
<p><a id="X80E17FA27DCAB676" name="X80E17FA27DCAB676"></a></p>
<h5>4.10-5 BitFlipDecoder</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> BitFlipDecoder</code>( <var class="Arg">C, r</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The iterative decoding method <code class="code">BitFlipDecoder</code> must only be applied to LDPC codes. For more information on LDPC codes, refer to Section <a href="chap5.html#X84F3673D7BBF5956"><b>5.8</b></a>. For these codes, <code class="code">BitFlipDecoder</code> decodes very quickly. (Warning: it can give wildly wrong results for arbitrary binary linear codes.) The bit flipping algorithm is described for example in Chapter 13 of <a href="chapBib.html#biBJH04">[JH04]</a>.</p>
<table class="example">
<tr><td><pre>
gap> C:=HammingCode(4,GF(2));
a linear [15,11,3]1 Hamming (4,2) code over GF(2)
gap> c:=Random(C);
[ 0 0 0 1 0 0 1 0 0 1 1 0 1 0 1 ]
gap> v:=List(c);
[ 0*Z(2), 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2),
Z(2)^0, Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2), Z(2)^0 ]
gap> v[1]:=Z(2)+v[1]; # flip 1st bit of c to create an error
Z(2)^0
gap> v:=Codeword(v);
[ 1 0 0 1 0 0 1 0 0 1 1 0 1 0 1 ]
gap> BitFlipDecoder(C,v);
[ 0 0 0 1 0 0 1 0 0 1 1 0 1 0 1 ]
</pre></td></tr></table>
<p><a id="X7B88DEB37F28404A" name="X7B88DEB37F28404A"></a></p>
<h5>4.10-6 NearestNeighborGRSDecodewords</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> NearestNeighborGRSDecodewords</code>( <var class="Arg">C, v, dist</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">NearestNeighborGRSDecodewords</code> finds all generalized Reed-Solomon codewords within distance <var class="Arg">dist</var> from <var class="Arg">v</var> <em>and</em> the associated polynomial, using ``brute force''. Input: <var class="Arg">v</var> is a received vector (a <strong class="pkg">GUAVA</strong> codeword), <var class="Arg">C</var> is a GRS code, <var class="Arg">dist</var> > 0 is the distance from <var class="Arg">v</var> to search in <var class="Arg">C</var>. Output: a list of pairs [c,f(x)], where wt(c-v)<= dist-1 and c = (f(x_1),...,f(x_n)).</p>
<table class="example">
<tr><td><pre>
gap> F:=GF(16);
GF(2^4)
gap> a:=PrimitiveRoot(F);; b:=a^7; b^4+b^3+1;
Z(2^4)^7
0*Z(2)
gap> Pts:=List([0..14],i->b^i);
[ Z(2)^0, Z(2^4)^7, Z(2^4)^14, Z(2^4)^6, Z(2^4)^13, Z(2^2), Z(2^4)^12,
Z(2^4)^4, Z(2^4)^11, Z(2^4)^3, Z(2^2)^2, Z(2^4)^2, Z(2^4)^9, Z(2^4),
Z(2^4)^8 ]
gap> x:=X(F);;
gap> R1:=PolynomialRing(F,[x]);;
gap> vars:=IndeterminatesOfPolynomialRing(R1);;
gap> y:=X(F,vars);;
gap> R2:=PolynomialRing(F,[x,y]);;
gap> C:=GeneralizedReedSolomonCode(Pts,3,R1);
a linear [15,3,1..13]10..12 generalized Reed-Solomon code over GF(16)
gap> MinimumDistance(C); # 6 error correcting
13
gap> z:=Zero(F);
0*Z(2)
gap> r:=[z,z,z,z,z,z,z,z,b^6,b^2,b^5,b^14,b,b^7,b^11];; # 7 errors
gap> r:=Codeword(r);
[ 0 0 0 0 0 0 0 0 a^12 a^14 a^5 a^8 a^7 a^4 a^2 ]
gap> cs:=NearestNeighborGRSDecodewords(C,r,7);
[ [ [ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ], 0*Z(2) ],
[ [ 0 a^9 a^3 a^13 a^6 a^10 a^11 a a^12 a^14 a^5 a^8 a^7 a^4 a^2 ], x_1+Z(2)^0 ] ]
</pre></td></tr></table>
<p><a id="X825E35757D778787" name="X825E35757D778787"></a></p>
<h5>4.10-7 NearestNeighborDecodewords</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> NearestNeighborDecodewords</code>( <var class="Arg">C, v, dist</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">NearestNeighborDecodewords</code> finds all codewords in a linear code <var class="Arg">C</var> within distance <var class="Arg">dist</var> from <var class="Arg">v</var>, using ``brute force''. Input: <var class="Arg">v</var> is a received vector (a <strong class="pkg">GUAVA</strong> codeword), <var class="Arg">C</var> is a linear code, <var class="Arg">dist</var> > 0 is the distance from <var class="Arg">v</var> to search in <var class="Arg">C</var>. Output: a list of c in C, where wt(c-v)<= dist-1.</p>
<table class="example">
<tr><td><pre>
gap> F:=GF(16);
GF(2^4)
gap> a:=PrimitiveRoot(F);; b:=a^7; b^4+b^3+1;
Z(2^4)^7
0*Z(2)
gap> Pts:=List([0..14],i->b^i);
[ Z(2)^0, Z(2^4)^7, Z(2^4)^14, Z(2^4)^6, Z(2^4)^13, Z(2^2), Z(2^4)^12,
Z(2^4)^4, Z(2^4)^11, Z(2^4)^3, Z(2^2)^2, Z(2^4)^2, Z(2^4)^9, Z(2^4),
Z(2^4)^8 ]
gap> x:=X(F);;
gap> R1:=PolynomialRing(F,[x]);;
gap> vars:=IndeterminatesOfPolynomialRing(R1);;
gap> y:=X(F,vars);;
gap> R2:=PolynomialRing(F,[x,y]);;
gap> C:=GeneralizedReedSolomonCode(Pts,3,R1);
a linear [15,3,1..13]10..12 generalized Reed-Solomon code over GF(16)
gap> MinimumDistance(C);
13
gap> z:=Zero(F);
0*Z(2)
gap> r:=[z,z,z,z,z,z,z,z,b^6,b^2,b^5,b^14,b,b^7,b^11];;
gap> r:=Codeword(r);
[ 0 0 0 0 0 0 0 0 a^12 a^14 a^5 a^8 a^7 a^4 a^2 ]
gap> cs:=NearestNeighborDecodewords(C,r,7);
[ [ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ],
[ 0 a^9 a^3 a^13 a^6 a^10 a^11 a a^12 a^14 a^5 a^8 a^7 a^4 a^2 ] ]
</pre></td></tr></table>
<p><a id="X7D02E0FE8735D3E6" name="X7D02E0FE8735D3E6"></a></p>
<h5>4.10-8 Syndrome</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Syndrome</code>( <var class="Arg">C, v</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">Syndrome</code> returns the syndrome of word <var class="Arg">v</var> with respect to a linear code <var class="Arg">C</var>. <var class="Arg">v</var> is a codeword in the ambient vector space of <var class="Arg">C</var>. If <var class="Arg">v</var> is an element of <var class="Arg">C</var>, the syndrome is a zero vector. The syndrome can be used for looking up an error vector in the syndrome table (see <code class="func">SyndromeTable</code> (<a href="chap4.html#X7B9E71987E4294A7"><b>4.10-9</b></a>)) that is needed to correct an error in v.</p>
<p>A syndrome is not defined for non-linear codes. <code class="code">Syndrome</code> then returns an error.</p>
<table class="example">
<tr><td><pre>
gap> C := HammingCode(4);
a linear [15,11,3]1 Hamming (4,2) code over GF(2)
gap> v := CodewordNr( C, 7 );
[ 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 ]
gap> Syndrome( C, v );
[ 0 0 0 0 ]
gap> Syndrome( C, Codeword( "000000001100111" ) );
[ 1 1 1 1 ]
gap> Syndrome( C, Codeword( "000000000000001" ) );
[ 1 1 1 1 ] # the same syndrome: both codewords are in the same
# coset of C
</pre></td></tr></table>
<p><a id="X7B9E71987E4294A7" name="X7B9E71987E4294A7"></a></p>
<h5>4.10-9 SyndromeTable</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> SyndromeTable</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">SyndromeTable</code> returns a <em>syndrome table</em> of a linear code <var class="Arg">C</var>, consisting of two columns. The first column consists of the error vectors that correspond to the syndrome vectors in the second column. These vectors both are of the codeword type. After calculating the syndrome of a word <var class="Arg">v</var> with <code class="code">Syndrome</code> (see <code class="func">Syndrome</code> (<a href="chap4.html#X7D02E0FE8735D3E6"><b>4.10-8</b></a>)), the error vector needed to correct <var class="Arg">v</var> can be found in the syndrome table. Subtracting this vector from <var class="Arg">v</var> yields an element of <var class="Arg">C</var>. To make the search for the syndrome as fast as possible, the syndrome table is sorted according to the syndrome vectors.</p>
<table class="example">
<tr><td><pre>
gap> H := HammingCode(2);
a linear [3,1,3]1 Hamming (2,2) code over GF(2)
gap> SyndromeTable(H);
[ [ [ 0 0 0 ], [ 0 0 ] ], [ [ 1 0 0 ], [ 0 1 ] ],
[ [ 0 1 0 ], [ 1 0 ] ], [ [ 0 0 1 ], [ 1 1 ] ] ]
gap> c := Codeword("101");
[ 1 0 1 ]
gap> c in H;
false # c is not an element of H
gap> Syndrome(H,c);
[ 1 0 ] # according to the syndrome table,
# the error vector [ 0 1 0 ] belongs to this syndrome
gap> c - Codeword("010") in H;
true # so the corrected codeword is
# [ 1 0 1 ] - [ 0 1 0 ] = [ 1 1 1 ],
# this is an element of H
</pre></td></tr></table>
<p><a id="X8642D0BD789DA9B5" name="X8642D0BD789DA9B5"></a></p>
<h5>4.10-10 StandardArray</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> StandardArray</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">StandardArray</code> returns the standard array of a code <var class="Arg">C</var>. This is a matrix with elements of the codeword type. It has q^r rows and q^k columns, where q is the size of the base field of <var class="Arg">C</var>, r=n-k is the redundancy of <var class="Arg">C</var>, and k is the dimension of <var class="Arg">C</var>. The first row contains all the elements of <var class="Arg">C</var>. Each other row contains words that do not belong to the code, with in the first column their syndrome vector (see <code class="func">Syndrome</code> (<a href="chap4.html#X7D02E0FE8735D3E6"><b>4.10-8</b></a>)).</p>
<p>A non-linear code does not have a standard array. <code class="code">StandardArray</code> then returns an error.</p>
<p>Note that calculating a standard array can be very time- and memory- consuming.</p>
<table class="example">
<tr><td><pre>
gap> StandardArray(RepetitionCode(3));
[ [ [ 0 0 0 ], [ 1 1 1 ] ], [ [ 0 0 1 ], [ 1 1 0 ] ],
[ [ 0 1 0 ], [ 1 0 1 ] ], [ [ 1 0 0 ], [ 0 1 1 ] ] ]
</pre></td></tr></table>
<p><a id="X83231E717CCB0247" name="X83231E717CCB0247"></a></p>
<h5>4.10-11 PermutationDecode</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> PermutationDecode</code>( <var class="Arg">C, v</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">PermutationDecode</code> performs permutation decoding when possible and returns original vector and prints 'fail' when not possible.</p>
<p>This uses <code class="code">AutomorphismGroup</code> in the binary case, and (the slower) <code class="code">PermutationAutomorphismGroup</code> otherwise, to compute the permutation automorphism group P of <var class="Arg">C</var>. The algorithm runs through the elements p of P checking if the weight of H(p* v) is less than (d-1)/2. If it is then the vector p* v is used to decode v: assuming <var class="Arg">C</var> is in standard form then c=p^-1Em is the decoded word, where m is the information digits part of p* v. If no such p exists then ``fail'' is returned. See, for example, section 10.2 of Huffman and Pless <a href="chapBib.html#biBHP03">[HP03]</a> for more details.</p>
<table class="example">
<tr><td><pre>
gap> C0:=HammingCode(3,GF(2));
a linear [7,4,3]1 Hamming (3,2) code over GF(2)
gap> G0:=GeneratorMat(C0);;
gap> G := List(G0, ShallowCopy);;
gap> PutStandardForm(G);
()
gap> Display(G);
1 . . . . 1 1
. 1 . . 1 . 1
. . 1 . 1 1 .
. . . 1 1 1 1
gap> H0:=CheckMat(C0);;
gap> Display(H0);
. . . 1 1 1 1
. 1 1 . . 1 1
1 . 1 . 1 . 1
gap> c0:=Random(C0);
[ 0 0 0 1 1 1 1 ]
gap> v01:=c0[1]+Z(2)^2;;
gap> v1:=List(c0, ShallowCopy);;
gap> v1[1]:=v01;;
gap> v1:=Codeword(v1);
[ 1 0 0 1 1 1 1 ]
gap> c1:=PermutationDecode(C0,v1);
[ 0 0 0 1 1 1 1 ]
gap> c1=c0;
true
</pre></td></tr></table>
<p><a id="X85B692177E2A745D" name="X85B692177E2A745D"></a></p>
<h5>4.10-12 PermutationDecodeNC</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> PermutationDecodeNC</code>( <var class="Arg">C, v, P</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Same as <code class="code">PermutationDecode</code> except that one may enter the permutation automorphism group <var class="Arg">P</var> in as an argument, saving time. Here <var class="Arg">P</var> is a subgroup of the symmetric group on n letters, where n is the word length of <var class="Arg">C</var>.</p>
<div class="chlinkprevnextbot"> <a href="chap0.html">Top of Book</a> <a href="chap3.html">Previous Chapter</a> <a href="chap5.html">Next Chapter</a> </div>
<div class="chlinkbot"><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="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<hr />
<p class="foot">generated by <a href="http://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
5e1854624d3bc613bdd0dd13d1ef9ac7
>
files
>
1811
