Quellcodebibliothek Statistik Leitseite products/sources/formale Sprachen/GAP/pkg/qdistrnd/doc/   (Algebra von RWTH Aachen Version 4.15.1©)  Datei vom 7.11.2024 mit Größe 32 kB image not shown  

Quelle  chap4.html   Sprache: HTML

 
 products/sources/formale Sprachen/GAP/pkg/qdistrnd/doc/chap4.html


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

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

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<title>GAP (QDistRnd) - Chapter 4: All Functions</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap4"  onload="jscontent()">


<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a>  <a href="chap1.html">1</a>  <a href="chap2.html">2</a>  <a href="chap3.html">3</a>  <a href="chap4.html">4</a>  <a href="chap5.html">5</a>  <a href="chapBib.html">Bib</a>  <a href="chapInd.html">Ind</a>  </div>

<div class="chlinkprevnexttop"> <a href="chap0.html">[Top of Book]</a>   <a href="chap0.html#contents">[Contents]</a>    <a href="chap3.html">[Previous Chapter]</a>    <a href="chap5.html">[Next Chapter]</a>   </div>

<p id="mathjaxlink" class="pcenter"><a href="chap4_mj.html">[MathJax on]</a></p>
<p><a id="X7C6522597D7E72FE" name="X7C6522597D7E72FE"></a></p>
<div class="ChapSects"><a href="chap4.html#X7C6522597D7E72FE">4 <span class="Heading">All Functions</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4.html#X826856C47F9890F3">4.1 <span class="Heading">Functions for computing the distance</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X83CF58308216037F">4.1-1 DistRandCSS</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X7894F0027B144AB8">4.1-2 DistRandStab</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X7A489A5D79DA9E5C">4.1-3 <span class="Heading">Examples</span></a>
</span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4.html#X7E4EA2B38128F66B">4.2 <span class="Heading">Input/Output Functions</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X86210A658573655F">4.2-1 ReadMTXE</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X82F72B6082EEDDF9">4.2-2 WriteMTXE</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4.html#X7BD4785D8488BAD5">4.3 <span class="Heading">Helper Functions</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X80975EC07BDC757B">4.3-1 QDR_AverageCalc</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X8615F38C79B4684C">4.3-2 QDR_SymplVecWeight</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X80BB67727F7F99C3">4.3-3 QDR_WeightMat</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X8441E8807AE9C477">4.3-4 QDR_DoProbOut</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X7B6713FC7A5124A8">4.3-5 QDR_ParseFieldStr</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X810D9FD7796AD286">4.3-6 QDR_ParsePolyStr</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X8638277B86B97B56">4.3-7 QDR_FieldHeaderStr</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X8388DFBC816EF47D">4.3-8 QDR_ProcessFieldHeader</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X82A75836794421A8">4.3-9 QDR_ProcEntry</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X7A489A5D79DA9E5C">4.3-10 <span class="Heading">Examples</span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X8020FCA787C830FE">4.3-11 QDR_MakeH</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X819DC3247F3F7B4F">4.3-12 QDR_DoCirc</a></span>
</div></div>
</div>

<h3>4 <span class="Heading">All Functions</span></h3>

<p><a id="X826856C47F9890F3" name="X826856C47F9890F3"></a></p>

<h4>4.1 <span class="Heading">Functions for computing the distance</span></h4>

<p><a id="X83CF58308216037F" name="X83CF58308216037F"></a></p>

<h5>4.1-1 DistRandCSS</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DistRandCSS</code>( <var class="Arg">HX</var>, <var class="Arg">HZ</var>, <var class="Arg">num</var>, <var class="Arg">mindist</var>[, <var class="Arg">debug</var>]<var class="Arg">:</var> <var class="Arg">field</var> <var class="Arg">:=</var> <var class="Arg">GF(2)</var>, <var class="Arg">maxav</var> <var class="Arg">:=</var> <var class="Arg">fail</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: An upper bound on the CSS distance <span class="Math">d_Z</span></p>

<p>Computes an upper bound on the distance <span class="Math">d_Z</span> of the <span class="Math">q</span>-ary code with stabilizer generator matrices <span class="Math">H_X</span>, <span class="Math">H_Z</span> whose rows are assumed to be orthogonal (<em>orthogonality is not verified</em>). Details of the input parameters</p>


<ul>
<li><p><code class="code">HX</code>, <code class="code">HZ</code>: the input matrices with elements in the Galois <code class="code">field</code> <span class="Math">F</span></p>

</li>
<li><p><code class="code">num</code>: number of information sets to construct (should be large)</p>

</li>
<li><p><code class="code">mindist</code> - the algorithm stops when distance equal or below <code class="code">mindist</code> is found and returns the result with negative sign. Set <code class="code">mindist</code> to 0 if you want the actual distance.</p>

</li>
<li><p><code class="code">debug</code>: optional integer argument containing debug bitmap (default: <code class="code">0</code>)</p>


<ul>
<li><p>1 (0s bit set) : print 1st of the vectors found</p>

</li>
<li><p>2 (1st bit set) : check orthogonality of matrices and of the final vector</p>

</li>
<li><p>4 (2nd bit set) : show occasional progress update</p>

</li>
<li><p>8 (3rd bit set) : maintain cw count and estimate the success probability</p>

</li>
</ul>
</li>
<li><p><code class="code">field</code> (Options stack): Galois field, default: <span class="Math">\mathop{\rm GF}(2)</span>.</p>

</li>
<li><p><code class="code">maxav</code> (Options stack): if set, terminate when <span class="Math">\langle n\rangle</span>><code class="code">maxav</code>, see Section <a href="chap3.html#X7CCA4B9B834960EE"><span class="RefLink">3.3</span></a>. Not set by default. See Section <a href="chap3.html#X7DDF42DF7D7F87EF"><span class="RefLink">3.1</span></a> for the description of the algorithm.</p>

</li>
</ul>
<p><a id="X7894F0027B144AB8" name="X7894F0027B144AB8"></a></p>

<h5>4.1-2 DistRandStab</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DistRandStab</code>( <var class="Arg">G</var>, <var class="Arg">num</var>, <var class="Arg">mindist</var>[, <var class="Arg">debug</var>]<var class="Arg">:</var> <var class="Arg">field</var> <var class="Arg">:=</var> <var class="Arg">GF(2)</var>, <var class="Arg">maxav</var> <var class="Arg">:=</var> <var class="Arg">fail</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: An upper bound on the code distance <span class="Math">d</span></p>

<p>Computes an upper bound on the distance <span class="Math">d</span> of the <span class="Math">F</span>-linear stabilizer code with generator matrix <span class="Math">G</span> whose rows are assumed to be symplectic-orthogonal, see Section <a href="chap3.html#X7D97C75283D26EE5"><span class="RefLink">3.1-5</span></a> (<em>orthogonality is not verified</em>).</p>

<p>Details of the input parameters:</p>


<ul>
<li><p><code class="code">G</code>: the input matrix with elements in the Galois <code class="code">field</code> <span class="Math">F</span> with <span class="Math">2n</span> columns <span class="Math">(a_1,b_1,a_2,b_2,\ldots,a_n,b_n)</span>. The remaining options are identical to those in the function <code class="code">DistRandCSS</code> <a href="chap4.html#X826856C47F9890F3"><span class="RefLink">4.1</span></a>.</p>

</li>
<li><p><code class="code">num</code>: number of information sets to construct (should be large)</p>

</li>
<li><p><code class="code">mindist</code> - the algorithm stops when distance equal or smaller than <code class="code">mindist</code> is found - set it to 0 if you want the actual distance</p>

</li>
<li><p><code class="code">debug</code>: optional integer argument containing debug bitmap (default: <code class="code">0</code>)</p>


<ul>
<li><p>1 (0s bit set) : print 1st of the vectors found</p>

</li>
<li><p>2 (1st bit set) : check orthogonality of matrices and of the final vector</p>

</li>
<li><p>4 (2nd bit set) : show occasional progress update</p>

</li>
<li><p>8 (3rd bit set) : maintain cw count and estimate the success probability</p>

</li>
</ul>
</li>
<li><p><code class="code">field</code> (Options stack): Galois field, default: <span class="Math">\mathop{\rm GF}(2)</span>.</p>

</li>
<li><p><code class="code">maxav</code> (Options stack): if set, terminate when <span class="Math">\langle n\rangle</span>><code class="code">maxav</code>, see Section <a href="chap3.html#X7CCA4B9B834960EE"><span class="RefLink">3.3</span></a>. Not set by default.</p>

</li>
</ul>
<p><a id="X7A489A5D79DA9E5C" name="X7A489A5D79DA9E5C"></a></p>

<h5>4.1-3 <span class="Heading">Examples</span></h5>

<p>Here are a few simple examples illustrating the use of distance functions. In all examples, we use functions <code class="code">DistRandCSS</code> and <code class="code">DistRandStab</code> with <code class="code">debug=2</code> to ensure that row orthogonality in the input matrices is verified.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">F:=GF(5);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Hx:=One(F)*[[1,-1,0,0 ],[0,0,1,-1]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Hz:=One(F)*[[1, 1,1,1]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">DistRandCSS(Hz,Hx,100,0,2 : field:=F);</span>
2
</pre></div>

<p>Now, if we set the minimum distance <code class="code">mindist</code> parameter too large, the function terminates immediately after a codeword with such a weight is found; in such a case the result is returned with the negative sign.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">DistRandCSS(Hz,Hx,100,2,2 : field:=F);</span>
-2
</pre></div>

<p>The function <code class="code">DistRandStab</code> takes only one matrix. This example uses the same CSS code but written into a single matrix. Notice how the values from the previous example are intercalated with zeros.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">F:=GF(5);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">H:=One(F)*[[1,0, -1,0,  0,0,  0,0 ], # original Hx in odd positions</span>
<span class="GAPprompt">></span> <span class="GAPinput">           [0,0,  0,0,  1,0, -1,0 ],</span>
<span class="GAPprompt">></span> <span class="GAPinput">           [0,1,  0,1,  0,1,  0,1 ]];; # original Hz in even positions</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">DistRandStab(H,100,0,2 : field:=F);</span>
2
</pre></div>

<p><a id="X7E4EA2B38128F66B" name="X7E4EA2B38128F66B"></a></p>

<h4>4.2 <span class="Heading">Input/Output Functions</span></h4>

<p><a id="X86210A658573655F" name="X86210A658573655F"></a></p>

<h5>4.2-1 ReadMTXE</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ReadMTXE</code>( <var class="Arg">FilePath</var>[, <var class="Arg">pair</var>]<var class="Arg">:</var> <var class="Arg">field</var> <var class="Arg">:=</var> <var class="Arg">GF(2)</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a list [<code class="code">field</code>, <code class="code">pair</code>, <code class="code">Matrix</code>, <code class="code">array_of_comment_strings</code>]</p>

<p>Read matrix from an MTX file, an extended version of Matrix Market eXchange coordinate format supporting finite Galois fields and two-block matrices <span class="Math"> (A|B) </span> with columns <span class="Math">A=(a_1, a_2, \ldots , a_n)</span> and <span class="Math">B=(b_1, b_2, \ldots , b_n)</span>, see Chapter <a href="chap5.html#X7D0187B5831B764D"><span class="RefLink">5</span></a>.</p>


<ul>
<li><p><code class="code">FilePath</code> name of existing file storing the matrix</p>

</li>
<li><p><code class="code">pair</code> (optional argument): specifies column ordering; must correlate with the variable <code class="code">type</code> in the file</p>


<ul>
<li><p><code class="code">pair=0</code> for regular single-block matrices (e.g., CSS) <code class="code">type=integer</code> (if <code class="code">pair</code> not specified, <code class="code">pair</code>=0 is set by default for <code class="code">integer</code>)</p>

</li>
<li><p><code class="code">pair=1</code> intercalated columns with <code class="code">type=integer</code> <span class="Math"> (a_1, b_1, a_2, b_2,\ldots) </span></p>

</li>
<li><p><code class="code">pair=2</code> grouped columns with <code class="code">type=integer</code> <span class="Math"> (a_1, a_2, \ldots, a_n\; b_1, b_2,\ldots, b_n) </span></p>

</li>
<li><p><code class="code">pair=3</code> this is the only option for <code class="code">type=complex</code> with elements specified as "complex" pairs</p>

</li>
</ul>
</li>
<li><p><code class="code">field</code> (Options stack): Galois field, default: <span class="Math">\mathop{\rm GF}(2)</span>.</p>

</li>
</ul>
<p><em>Must</em> match that given in the file (if any). <em>Notice</em>: with <code class="code">pair</code>=1 and <code class="code">pair</code>=2, the number of matrix columns specified in the file must be even, twice the block length of the code. <em>This version of the format is deprecated and should be avoided.</em></p>

<p>1st line of file must read:</p>


<div class="example"><pre>
 %%MatrixMarket matrix coordinate `type` general 
</pre></div>

<p>with <code class="code">type</code> being either <code class="code">integer</code> or <code class="code">complex</code></p>

<p>2nd line (optional) may contain:</p>


<div class="example"><pre>
 % Field: `valid_field_name_in_Gap` 
</pre></div>

<p>or</p>


<div class="example"><pre>
 % Field: `valid_field_name_in_Gap` PrimitiveP(x): `polynomial` 
</pre></div>

<p>Any additional entries in the second line are silently ignored. By default, <span class="Math">\mathop{\rm GF}(2)</span> is assumed; the default can be overriden by the optional <code class="code">field</code> argument. If the field is specified both in the file and by the optional argument, the corresponding values must match. Primitive polynomial (if any) is only checked in the case of an extension field; it is silently ignored for a prime field.</p>

<p>See Chapter <a href="chap5.html#X7D0187B5831B764D"><span class="RefLink">5</span></a> for the details of how the elements of the group are represented depending on whether the field is a prime field (<span class="Math"> q </span> a prime) or an extension field with <span class="Math"> q=p^m </span>, <span class="Math">p</span> prime, and <span class="Math">m>1</span>.</p>

<p><a id="X82F72B6082EEDDF9" name="X82F72B6082EEDDF9"></a></p>

<h5>4.2-2 WriteMTXE</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ WriteMTXE</code>( <var class="Arg">StrPath</var>, <var class="Arg">pair</var>, <var class="Arg">matrix</var>[, <var class="Arg">comment</var>[, <var class="Arg">comment</var>]]<var class="Arg">:</var> <var class="Arg">field</var> <var class="Arg">:=</var> <var class="Arg">GF(2)</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: no output</p>

<p>Export a <code class="code">matrix</code> in Extended MatrixMarket format, with options specified by the <code class="code">pair</code> argument.</p>


<ul>
<li><p><code class="code">StrPath</code> - name of the file to be created;</p>

</li>
<li><p><code class="code">pair</code>: parameter to control the file format details, must match the storage <code class="code">type</code> of the matrix.</p>


<ul>
<li><p><code class="code">pair=0</code> for regular matrices (e.g., CSS) with <code class="code">type=integer</code></p>

</li>
<li><p><code class="code">pair=1</code> for intercalated columns <span class="Math"> (a_1, b_1, a_2, b_2, \ldots) </span> with <code class="code">type=integer</code> (<em>deprecated</em>)</p>

</li>
<li><p><code class="code">pair=2</code> for grouped columns with <code class="code">type=integer</code> <em>(this is not supported!)</em></p>

</li>
<li><p><code class="code">pair=3</code> for columns specified in pairs with <code class="code">type=complex</code>.</p>

</li>
</ul>
</li>
<li><p>Columns of the input <code class="code">matrix</code> must be intercalated unless <code class="code">pair=0</code></p>

</li>
<li><p>optional <code class="code">comment</code>: one or more strings (or a single list of strings) to be output after the MTX header line.</p>

</li>
</ul>
<p>The second line specifying the field will be generated automatically <em>only</em> if the GAP Option <code class="code">field</code> is present. As an option, the line can also be entered explicitly as the first line of the comments, e.g., <code class="code">"% Field: GF(256)"</code></p>

<p>See Chapter <a href="chap5.html#X7D0187B5831B764D"><span class="RefLink">5</span></a> for the details of how the elements of the group are represented depending on whether the field is a prime field (<span class="Math"> q </span> a prime) or an extension field with <span class="Math"> q=p^m </span>, <span class="Math"> m>1 </span>.</p>

<p><a id="X7BD4785D8488BAD5" name="X7BD4785D8488BAD5"></a></p>

<h4>4.3 <span class="Heading">Helper Functions</span></h4>

<p><a id="X80975EC07BDC757B" name="X80975EC07BDC757B"></a></p>

<h5>4.3-1 QDR_AverageCalc</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ QDR_AverageCalc</code>( <var class="Arg">vector</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Calculate the average of the components of a numerical <code class="code">vector</code></p>

<p><a id="X8615F38C79B4684C" name="X8615F38C79B4684C"></a></p>

<h5>4.3-2 QDR_SymplVecWeight</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ QDR_SymplVecWeight</code>( <var class="Arg">vector</var>, <var class="Arg">field</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: symplectic weight of a vector</p>

<p>Calculate the symplectic weight of a <code class="code">vector</code> with an even number of entries from the field <code class="code">field</code>. The elements of the pairs are intercalated: <span class="Math">(a_1, b_1, a_2, b_2,\ldots)</span>.</p>

<p><em>Note: the parity of vector <code class="code">length</code> and the format are not verified!!!</em></p>

<p><a id="X80BB67727F7F99C3" name="X80BB67727F7F99C3"></a></p>

<h5>4.3-3 QDR_WeightMat</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ QDR_WeightMat</code>( <var class="Arg">matrix</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: number of non-zero elements</p>

<p>count the total number of non-zero entries in a matrix.</p>

<p><a id="X8441E8807AE9C477" name="X8441E8807AE9C477"></a></p>

<h5>4.3-4 QDR_DoProbOut</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ QDR_DoProbOut</code>( <var class="Arg">vector</var>, <var class="Arg">n</var>, <var class="Arg">num</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: nothing</p>

<p>Aux function to print out the relevant probabilities given the list <code class="code">vector</code> of multiplicities of the codewords found. Additional parameters are <code class="code">n</code>, the code length, and <code class="code">num</code>, the number of repetitions; these are ignored in the present version of the program. See <a href="chap3.html#X7CCA4B9B834960EE"><span class="RefLink">3.3</span></a> for related discussion.</p>

<p><a id="X7B6713FC7A5124A8" name="X7B6713FC7A5124A8"></a></p>

<h5>4.3-5 QDR_ParseFieldStr</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ QDR_ParseFieldStr</code>( <var class="Arg">str</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: the corresponding Galois field</p>

<p>Parse a string describing a Galois field Supported formats: <code class="code">Z(p)</code>, <code class="code">GF(q)</code>, and <code class="code">GF(q^m)</code>, where <code class="code">p</code> must be a prime, <code class="code">q</code> a prime or a power of a prime, and <code class="code">m</code> a natural integer. No spaces are allowed.</p>

<p><a id="X810D9FD7796AD286" name="X810D9FD7796AD286"></a></p>

<h5>4.3-6 QDR_ParsePolyStr</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ QDR_ParsePolyStr</code>( <var class="Arg">F</var>, <var class="Arg">str</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: the corresponding polynomial</p>

<p>Parse string <code class="code">str</code> as a polynomial over the field <code class="code">F</code>. Only characters in "0123456789*+-^x" are allowed in the string. In particular, no spaces are allowed.</p>

<p><a id="X8638277B86B97B56" name="X8638277B86B97B56"></a></p>

<h5>4.3-7 QDR_FieldHeaderStr</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ QDR_FieldHeaderStr</code>( <var class="Arg">F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: the created header string</p>

<p>Create a header string describing the field <code class="code">F</code> for use in the function <code class="code">WriteMTXE</code>. If <code class="code">F</code> is a prime Galois field, just specify it: For an extension field <span class="Math">\mathop{\rm GF}(p^m)</span> with <span class="Math">p</span> prime and <span class="Math">m>1</span>, also give the primitive polynomial <em>which should not contain any spaces</em>. For example, See Chapter <a href="chap5.html#X7D0187B5831B764D"><span class="RefLink">5</span></a> for details.</p>

<p><a id="X8388DFBC816EF47D" name="X8388DFBC816EF47D"></a></p>

<h5>4.3-8 QDR_ProcessFieldHeader</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ QDR_ProcessFieldHeader</code>( <var class="Arg">recs</var>, <var class="Arg">optF</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: the list [Field, ConversionDegree, FormatIndex] (plus anything else we may need in the future); the list is to be used as the second parameter in <code class="code">QDR_ProcEntry()</code></p>

<p>Process the field header (second line in the MTXE file format), including the field, PrimitiveP record, and anything else. Supported format options:</p>


<div class="example"><pre>
 Field: `field` PrimitiveP(x): `polynomial` Format: `format`
</pre></div>

<p>Here the records should be separated by one or more spaces; while <code class="code">field</code>, <code class="code">polynomial</code>, and <code class="code">format</code> <em>should not contain any spaces.</em> Any additional records in this line will be silently ignored.</p>

<p>The <code class="code">field</code> option should specify a valid field, <span class="Math">\mathop{\rm GF}(q)</span> or <span class="Math">\mathop{\rm GF}(p^m)</span>, where <span class="Math">q>1</span> should be a power of the prime <span class="Math">p</span>.</p>

<p>The <code class="code">polynomial</code> should be a valid expanded monic polynomial with integer coefficients, with a single independent variable <code class="code">x</code>; it should contain no spaces. An error will be signaled if <code class="code">polynomial</code> is not a valid primitive polynomial of the <code class="code">field</code>. This argument is optional; by default, Conway polynomial will be used.</p>

<p>The optional <code class="code">format</code> string (<em>not implemented</em>) should be "AdditiveInt" (the default for prime fields), "PowerInt" (the default for extension fields with <span class="Math">m>1</span>) or "VectorInt".</p>

<p><code class="code">AdditiveInt</code> indicates that values listed are expected to be in the corresponding prime field and should be interpreted as integers mod <span class="Math">p</span>. <code class="code">PowerInt</code> indicates that field elements are represented as integers powers of the primitive element, root of the primitive polynomial, or <span class="Math">-1</span> for the zero field element. <code class="code">VectorInt</code> corresponds to encoding coefficients of a degree-<span class="Math">(m-1)</span> <span class="Math">p</span>-ary polynomial representing field elements into a <span class="Math">p</span>-ary integer. In this notation, any negative value will be taken mod <span class="Math">p</span>, thus <span class="Math">-1</span> will be interpreted as <span class="Math">p-1</span>, the additive inverse of the field <span class="Math">1</span>.</p>

<p>On input, <code class="code">recs</code> should contain a list of tokens obtained by splitting the field record line; <code class="code">optF</code> should be assigned to <code class="code">ValueOption("field")</code> or <code class="code">fail</code>.</p>

<p><a id="X82A75836794421A8" name="X82A75836794421A8"></a></p>

<h5>4.3-9 QDR_ProcEntry</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ QDR_ProcEntry</code>( <var class="Arg">str</var>, <var class="Arg">fmt</var>, <var class="Arg">FileName</var>, <var class="Arg">LineNo</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: the converted field element</p>

<p>Convert a string entry which should represent an integer to the Galois Field element as specified in the <code class="code">fmt</code>.</p>


<ul>
<li><p><code class="code">str</code> is the string representing an integer.</p>

</li>
<li><p><code class="code">fmt</code> is a list [Field, ConversionDegree, FormatIndex]</p>


<ul>
<li><p><code class="code">Field</code> is the Galois field <span class="Math">\mathop{\rm GF}(p^m)</span> of the code</p>

</li>
<li><p><code class="code">ConversionDegree</code> <span class="Math">c</span> : every element <span class="Math">x</span> read is replaces with <span class="Math">x^c</span>. This may be needed if a non-standard primitive polynomial is used to define the field.</p>

</li>
<li><p><code class="code">FormatIndex</code> in {0,1,2}. <code class="code">0</code> indicates no conversion (just a modular integer). <code class="code">1</code> indicates that the integer represents a power of the primitive element, or <span class="Math">-1</span> for 0. <code class="code">2</code> indicates that the integer encodes coordinates of a length <span class="Math">m</span> vector as the digits of a <span class="Math">p</span>-ary integer (<em>not yet implemented</em>).</p>

</li>
</ul>
</li>
<li><p><code class="code">FileName</code>, <code class="code">LineNo</code> are the line number and the name of the input file; these are used to signal an error.</p>

</li>
</ul>
<p><a id="X7A489A5D79DA9E5C" name="X7A489A5D79DA9E5C"></a></p>

<h5>4.3-10 <span class="Heading">Examples</span></h5>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">QDR_AverageCalc([2,3,4,5]);</span>
3.5
</pre></div>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">F:=GF(3);; </span>
<span class="GAPprompt">gap></span> <span class="GAPinput">x:=Indeterminate(F,"x");; poly:=One(F)*(1-x);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">n:=5;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">mat:=QDR_DoCirc(poly,n,2*n,F);; # make a circulant matrix with 5 rows </span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(mat);</span>
 1 2 . . . . . . . .
 . . 1 2 . . . . . .
 . . . . 1 2 . . . .
 . . . . . . 1 2 . .
 . . . . . . . . 1 2
</pre></div>

<p>These examples illustrate the allowed format of field definitions in the header of an <code class="code">MTXE</code> file:</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">QDR_ParseFieldStr("Z(5)");</span>
Z(5)
<span class="GAPprompt">gap></span> <span class="GAPinput">QDR_ParseFieldStr("Z(17)");</span>
Z(17)
<span class="GAPprompt">gap></span> <span class="GAPinput">QDR_ParseFieldStr("GF(5^2)");</span>
GF(5^2)
<span class="GAPprompt">gap></span> <span class="GAPinput">QDR_ParseFieldStr("GF(25)");</span>
GF(5^2)
<span class="GAPprompt">gap></span> <span class="GAPinput">QDR_ParseFieldStr("GF(125^2)");</span>
GF(5^6)
</pre></div>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">QDR_ParsePolyStr(GF(25),"x^2+1");</span>
x^2+Z(5)^0
</pre></div>

<p><a id="X8020FCA787C830FE" name="X8020FCA787C830FE"></a></p>

<h5>4.3-11 QDR_MakeH</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ QDR_MakeH</code>( <var class="Arg">matrix</var>, <var class="Arg">field</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: <code class="code">H</code> (the check matrix constructed)</p>

<p>Given a two-block <code class="code">matrix</code> with intercalated columns <span class="Math"> (a_1, b_1, a_2, b_2, \ldots) </span>, calculate the corresponding check matrix <code class="code">H</code> with columns <span class="Math"> (-b_1, a_1, -b_2, a_2, \ldots) </span>.</p>

<p>The parity of the number of columns is verified.</p>

<p><a id="X819DC3247F3F7B4F" name="X819DC3247F3F7B4F"></a></p>

<h5>4.3-12 QDR_DoCirc</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ QDR_DoCirc</code>( <var class="Arg">poly</var>, <var class="Arg">m</var>, <var class="Arg">n</var>, <var class="Arg">field</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: <code class="code">m</code> by <code class="code">2*n</code> circulant matrix constructed from the polynomial coefficients</p>

<p>Given the polynomial <code class="code">poly</code> <span class="Math">a_0+b_0 x+a_1x^2+b_1x^3 +\ldots</span> with coefficients from the field <code class="code">F</code>, constructs the corresponding <code class="code">m</code> by 2<code class="code">n</code> double circulant matrix obtained by <code class="code">m</code> repeated cyclic shifts of the coefficients' vector by s=2 positions at a time.




<div class="chlinkprevnextbot"> <a href="chap0.html">[Top of Book]</a>   <a href="chap0.html#contents">[Contents]</a>    <a href="chap3.html">[Previous Chapter]</a>    <a href="chap5.html">[Next Chapter]</a>   </div>


<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="chapBib.html">Bib</a>  <a href="chapInd.html">Ind</a>  </div>

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

100%


¤ Dauer der Verarbeitung: 0.21 Sekunden  ¤

*© Formatika GbR, Deutschland




Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

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

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.