Quelle chap5.html Sprache: HTML

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

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

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

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

<div class="chlinktop">Goto Chapter: <a href="chap0.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="chap4.html">[Previous Chapter]</a> <a href="chapBib.html">[Next Chapter]</a> </div>

<a href="chap5_mj.html">[MathJax on]</a>
<a id="X7D0187B5831B764D" name="X7D0187B5831B764D"></a>
<div class="ChapSects"><a href="chap5.html#X7D0187B5831B764D">5 Extended MTX (MTXE) File Format</a>
<div class="ContSect"> <a href="chap5.html#X7E294E8678035D23">5.1 General information</a>

<div class="ContSSBlock">
 <a href="chap5.html#X8269F2367856BB1E">5.1-1 Representation of field elements via integers</a>

 <a href="chap5.html#X86FBB72C7BC3B8D2">5.1-2 Matrix storage format</a>

 <a href="chap5.html#X80B886F0796AF0D5">5.1-3 Explicit format of each line</a>

 <a href="chap5.html#X80F0F8AB7FD73B0E">5.1-4 Matrix Storage Implementation Details</a>

</div></div>
<div class="ContSect"> <a href="chap5.html#X7F2C657F869D90AD">5.2 Example MTXE files</a>

</div>
</div>

<h3>5 Extended MTX (MTXE) File Format</h3>

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

<h4>5.1 General information</h4>

The code supports reading matrices from an MTX file using <code class="code">ReadMTXE</code> and writing new MTX file using <code class="code">WriteMTXE</code> functions. Below a description of the format is given.

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

<h5>5.1-1 Representation of field elements via integers</h5>

Every finite field is isomorphic to a Galois field F=\mathop{\rm GF}(q), where q is a power of a prime, q=p^m.

<ul>
<li>For a prime field, with q=p a prime, F is a prime field, isomorphic to the ring Z(q) of integers modulo q. In such a case, elements of the field are stored directly as integers. After reading, these are taken modulo p, thus, e.g., with p=7, values -1, 6, or 13 are all equivalent.

</li>
</ul>

<ul>
<li>When q=p^m with m > 1, F is an extension field. Non-zero elements of such a field can be represented as integer powers of a primitive element \alpha, a primitive root of unity in the field. Primitive element is a root of a primitive polynomial f(x), that is, an irreducible polynomial with coefficients in the corresponding prime field \mathop{\rm GF}(p), with the property that the smallest integer n such that f(x) divides x^n-1 is n=p^m-1. Alternatively, field elements can be represented as p-ary polynomials modulo the chosen primitive polynomial f(x).

</li>
</ul>
Either definition requires that the primitive polynomial be specified. By default, GAP uses Conway polynomials to represent field elements. For details, as well as a large collection of Conway polynomials, please see the web page maintained by Frank Luebeck <a href="chapBib.html#biBConwayPol-2022">[L\t21]</a>.

In the actual file format, three different and mutually exclusive storage options for elements of an extension field can in be used.

<ul>
<li>First, assuming all elements needed are actually in the corresponding prime field \mathop{\rm GF}(p), the integer values (mod p) directly correspond to the values of field elements. This is the case, e.g., with 0,\pm1 matrices which obey the orthogonality condition already over integers, and retain orthogonality over Z(q) with any q (what is more relevant here, the same matrix would work with any prime field). (this is currently not implemented)

</li>
</ul>

<ul>
<li>Second option, and the only option currently implemented for extension fields, is to store the powers of the primitive element for each non-zero element in the field, and -1 for zero.

</li>
</ul>

<ul>
<li>Third option, is to take the coefficients of p-ary polynomial a_0+a_1x+a_2x^2+\ldots +a_{m-1}x^{m-1} as digits of a p-ary integer (a_{m-1}a_{m-2}\ldots a_2a_1)_p. (this is currently not implemented)

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

<h5>5.1-2 Matrix storage format</h5>

There are two recommended storage formats.

1. For CSS matrices stored in separate files, the MTX header should use the <code class="code">integer</code> type, with matrix elements stored in the usual order.

2. For general stabilizer codes, or to store both CSS matrices in a single file, the MTX header should use the <code class="code">complex</code> type. In this case the block matrix (A,B) is stored as a complex matrix A+iB.

In both format versions, the number of columns specified in the file coincides with the code length.

Two additional matrix format versions supported by <code class="code">ReadMTXE</code> and <code class="code">WriteMTXE</code> are provided for compatibility. Here, the columns a_i and b_i in the blocks A and B are listed individually, and are either intercalated [the ordering (a_1, b_1, a_2,b_2,\ldots,a_n,b_n)] or are separated into column blocks (a_1,\ldots,a_n,b_1,\ldots,b_n). In both cases the number of columns in the matrix stored is twice the code length.

The ordering of the columns is governed by a parameter <code class="code">pair</code>, optional in the function <code class="code">ReadMTXE</code> and required in <code class="code">WriteMTXE</code>.

<ul>
<li>With <code class="code">pair=0</code> the matrix elements are stored in the usual order. In this case the MTX header should use the <code class="code">integer</code> type. This is the defailt storage format for stabilizer generator matrices of CSS codes, and also the internal matrix format for single-block matrices accepted by the function <code class="code">DistRandCSS</code>, see Section <a href="chap4.html#X826856C47F9890F3">4.1</a>.

</li>
</ul>

<ul>
<li>With <code class="code">pair=1</code> the block matrix (A,B) is stored with intercalated columns (a_1,b_1,\ldots,a_n,b_n); the MTX header should use the <code class="code">integer</code> type. This is the internal matrix format for two-block matrices accepted by the functions <code class="code">DistRandStab</code> (<a href="chap4.html#X826856C47F9890F3">4.1</a>) and <code class="code">WriteMTXE</code> (<a href="chap4.html#X7E4EA2B38128F66B">4.2</a>), and returned by <code class="code">ReadMTXE</code> (<a href="chap4.html#X7E4EA2B38128F66B">4.2</a>).

</li>
</ul>

<ul>
<li>With <code class="code">pair=2</code> the block matrix (A,B) is stored with separated columns (a_1,\ldots,a_n, b_1,\ldots,b_n); the MTX header should also use the <code class="code">integer</code> type.

</li>
</ul>

<ul>
<li>With <code class="code">pair=3</code> the block matrix (A,B) is stored as a complex matrix A+iB, with columns (a_1 + i b_1,\ldots,a_n + i b_n). In this case <code class="code">type=complex</code>, since matrix elements are represented as complex integers.

</li>
</ul>
By default, <code class="code">pair=0</code> corresponds to <code class="code">type=integer</code> and <code class="code">pair=3</code> corresponds to <code class="code">type=complex</code>. It is strongly recommended that matrices intended for use by others should only use these two variants of the MTXE format.

For efficiency reasons, the function <code class="code">DistRandStab</code> (<a href="chap4.html#X826856C47F9890F3">4.1</a>) assumes the generator matrix with intercalated columns.

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

<h5>5.1-3 Explicit format of each line</h5>

The first line must have the following form:

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

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

The second line is optional and specifies the field, the primitive polynomial used (in the case of an extension field), and the storage format of field elements.

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

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> should not contain any spaces. Any additional records in this line will be silently ignored.

The <code class="code">field</code> option should specify a valid field, <code class="code">GF(q)</code> or <code class="code">GF(p^m)</code>, where q>1 should be a power of the prime 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; if not specified, one may assume that the Conway polynomial should be used.

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

<ul>
<li><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 p.

</li>
</ul>

<ul>
<li><code class="code">PowerInt</code> indicates that field elements are represented as integers powers of the primitive element, root of the primitive polynomial, or -1 for the zero field element.

</li>
</ul>

<ul>
<li><code class="code">VectorInt</code> corresponds to encoding coefficients of a degree-(m-1) p-ary polynomial representing field elements into a p-ary integer. In this notation, any negative value will be taken mod p, thus -1 will be interpreted as p-1, the additive inverse of the field 1.

</li>
</ul>
The primitive polynomial must be written explicitly as x^m+a_{m-1}*x^{m-1}+\ldots+a_1*x+a_0, where the integer coefficients a_i will be interpreted modulo <code class="code">p</code>. The primitive polynomial should not contain any spaces.

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

For example, with q=5^2, the Conway polynomial f_{5,2}(x)=x^2-x+2, and the second line can read

<div class="example"><pre>
% Field: GF(25) PrimitiveP(x): x^2-x+2 Format: PowerInt
</pre></div>

The following is an equivalent form of the same polynomial and can also be used

<div class="example"><pre>
% Field: GF(25) PrimitiveP(x): x^2+4*x+2
</pre></div>

The field may be left undefined; by default, it is \mathop{\rm GF}(2), or it can be specified by hand when reading the matrices. If the primitive polynomial is undefined, it will be assumed that the Conway polynomial used internally by <code class="code">GAP</code> should be used.

Next follows the comment section, with each line either empty or starting with the <code class="code">%</code> symbol:

<div class="example"><pre>
% Example of the comment line
</pre></div>

After the comment section, in agreement with MTX format, goes the line giving the dimensions of the matrix and the number of non-zero elements:

<div class="example"><pre>
rows columns `(number of non-zero elements)`
</pre></div>

Then all non-zero elements are listed as three or four integers according to the <code class="code">type</code>:

<ul>
<li><code class="code">type=integer</code>:

</li>
</ul>

<div class="example"><pre>
i j element[i,j]
</pre></div>

<ul>
<li><code class="code">type=complex</code>:

</li>
</ul>

<div class="example"><pre>
i j a[i,j] b[i,j]
</pre></div>

Notice that column and row numbers must start with 1, as prescribed in the original MTX format.

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

<h5>5.1-4 Matrix Storage Implementation Details</h5>

Neither the <code class="code">WriteMTXE</code> nor <code class="code">ReadMTXE</code> currently support the <code class="code">Format:</code> parameter. Prime field elements are only stored "as is", i.e., as integers to be taken modulo <code class="code">p</code>, while extension field elements are only stored in the <code class="code">PowerInt</code> format, i.e., with the power of the primitive element specified, or "-1" for zero.

The function <code class="code">WriteMTXE</code> can only save field elements with the primitive polynomial used internally by <code class="code">GAP</code>, i.e., the Conway polynomial.

The function <code class="code">ReadMTXE</code> can read matrix elements specified (in the case of an extension field) with any primitive polynomial as specified in the file.

Given the field \mathop{\rm GF}(p^m) and the primitive polynomial p(x) specified in the file, the function <code class="code">ReadMTXE</code> first checks that the degree of p(x) is indeed m and that it is a primitive polynomial in the corresponding prime field \mathop{\rm GF}(p). If either of these tests fail, <code class="code">ReadMTXE</code> produces an error. Otherwise, it will attempt to find the conversion coefficient c such that \alpha^c is a root of p(x), starting with c=1. When found, the multiplicative inverse s such that sc\equiv 1\bmod (q-1) will be used to convert the elements being read, i.e., for any matrix element y read, y^s will be used instead.

Notice that, unless the Conway polynomial was used (in which case c=s=1, and the conversion is trivial), this search can be slow for large fields, as all integer values in [1,2,\ldots,q-2] will be tested sequentially. To help ensure that the correct polynomial is used, it is recommended that orthogonality of matrices be checked.

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

<h4>5.2 Example MTXE files</h4>

In this section we give two sample MTXE files storing the stabilizer generator matrix of 5-qubit codes.

First, matrix (with one redundant linearly-dependent row) stored with <code class="code">type=integer</code> and <code class="code">pair=1</code> (intercalated columns [a_1,b_1,a_2,b_2,\ldots]) is presented. Notice that the number of columns is twice the actual length of the code. Even though the field is specified explicitly, this matrix would work with any prime field.

<div class="example"><pre>
%%MatrixMarket matrix coordinate integer general
% Field: GF(7)
% 5-qubit code generator matrix / normal storage with intercalated cols
5 10 20
1 1 1
1 4 1
1 6 -1
1 7 -1
2 3 1
2 6 1
2 8 -1
2 9 -1
3 1 -1
3 5 1
3 8 1
3 10 -1
4 2 -1
4 3 -1
4 7 1
4 10 1
5 2 1
5 4 -1
5 5 -1
5 9 1
</pre></div>

This same matrix is stored in the file <code class="code">matrices/n5k1A.mtx</code>. This is how the matrix can be read and distance calculated:

<div class="example"><pre>
gap> filedir:=DirectoriesPackageLibrary("QDistRnd","matrices");;
gap> lis:=ReadMTXE(Filename(filedir,"n5k1A.mtx" ));;
gap> Print("field ",lis[1],"\n");
field GF(7)
gap> dist:=DistRandStab(lis[3],100,0 : field:=lis[1]);
3
</pre></div>

The same matrix can also be stored with <code class="code">type=complex</code> and <code class="code">pair=3</code> (complex pairs [a_1+i b_1,a_2+i b_2,\ldots]). In this format, the number of columns equals the code length.

<div class="example"><pre>
%%MatrixMarket matrix coordinate complex general
% works with any prime field
% 5-qubit code generator matrix / normal storage with intercalated cols
% [[5,1,3]]_p
4 5 16
1 1 1 0
1 2 0 1
1 3 0 -1
1 4 -1 0
2 2 1 0
2 3 0 1
2 4 0 -1
2 5 -1 0
3 1 -1 0
3 3 1 0
3 4 0 1
3 5 0 -1
4 1 0 -1
4 2 -1 0
4 4 1 0
4 5 0 1
</pre></div>

The matrix above is written in the file <code class="code">matrices/n5k1.mtx</code>. To calculate the distance, we need to specify the field [unless we want to use the default binary field].

<div class="example"><pre>
gap> lis:=ReadMTXE(Filename(filedir,"n5k1.mtx" ));;
gap> Print("field ",lis[1],"\n");
field GF(2)
gap> dist:=DistRandStab(lis[3],100,0,2 : field:=lis[1]);
3
gap> q:=17;;
gap> lis:=ReadMTXE(Filename(filedir,"n5k1.mtx") : field:= GF(q));;
gap> Print("field ",lis[1],"\n");
field GF(17)
gap> dist:=DistRandStab(lis[3],100,0,2 : field:=lis[1]);
3
</pre></div>

Finally, the following is an example of a five-qudit code over \mathop{\rm GF}(2^3) constructed by the script <code class="code">examples/cyclic.g</code>.

<div class="example"><pre>
%%MatrixMarket matrix coordinate complex general
% Field: GF(2^3) PrimitiveP(x): x^3+x+1
% code [[5,1,3]]_8
% cyclic w=4 x^6+Z(2^3)^4*x^5+Z(2^3)^4*x^3+Z(2)^0
% Powers of GF(8) primitive element and -1 for Zero are given
5 5 20
1 1 0 -1
1 2 -1 4
1 3 -1 4
1 4 0 -1
2 2 0 -1
2 3 -1 4
2 4 -1 4
2 5 0 -1
3 1 0 -1
3 3 0 -1
3 4 -1 4
3 5 -1 4
4 1 -1 4
4 2 0 -1
4 4 0 -1
4 5 -1 4
5 1 -1 4
5 2 -1 4
5 3 0 -1
5 5 0 -1
</pre></div>

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

<div class="chlinkbot">Goto Chapter: <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 />
generated by <a href="https://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a>
</body>
</html>

quality100%

¤ Dauer der Verarbeitung: 0.19 Sekunden (vorverarbeitet) ¤

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.