‣ DistRandCSS( HX, HZ, num, mindist[, debug]: field := GF(2), maxav := fail ) | ( function ) |
Returns: An upper bound on the CSS distance d_Z
Computes an upper bound on the distance d_Z of the q-ary code with stabilizer generator matrices H_X, H_Z whose rows are assumed to be orthogonal (orthogonality is not verified). Details of the input parameters
HX, HZ: the input matrices with elements in the Galois field F
num: number of information sets to construct (should be large)
mindist - the algorithm stops when distance equal or below mindist is found and returns the result with negative sign. Set mindist to 0 if you want the actual distance.
debug: optional integer argument containing debug bitmap (default: 0)
1 (0s bit set) : print 1st of the vectors found
2 (1st bit set) : check orthogonality of matrices and of the final vector
4 (2nd bit set) : show occasional progress update
8 (3rd bit set) : maintain cw count and estimate the success probability
field (Options stack): Galois field, default: \mathop{\rm GF}(2).
maxav (Options stack): if set, terminate when \langle n\rangle>maxav, see Section 3.3. Not set by default. See Section 3.1 for the description of the algorithm.
‣ DistRandStab( G, num, mindist[, debug]: field := GF(2), maxav := fail ) | ( function ) |
Returns: An upper bound on the code distance d
Computes an upper bound on the distance d of the F-linear stabilizer code with generator matrix G whose rows are assumed to be symplectic-orthogonal, see Section 3.1-5 (orthogonality is not verified).
Details of the input parameters:
G: the input matrix with elements in the Galois field F with 2n columns (a_1,b_1,a_2,b_2,\ldots,a_n,b_n). The remaining options are identical to those in the function DistRandCSS 4.1.
num: number of information sets to construct (should be large)
mindist - the algorithm stops when distance equal or smaller than mindist is found - set it to 0 if you want the actual distance
debug: optional integer argument containing debug bitmap (default: 0)
1 (0s bit set) : print 1st of the vectors found
2 (1st bit set) : check orthogonality of matrices and of the final vector
4 (2nd bit set) : show occasional progress update
8 (3rd bit set) : maintain cw count and estimate the success probability
field (Options stack): Galois field, default: \mathop{\rm GF}(2).
maxav (Options stack): if set, terminate when \langle n\rangle>maxav, see Section 3.3. Not set by default.
Here are a few simple examples illustrating the use of distance functions. In all examples, we use functions DistRandCSS and DistRandStab with debug=2 to ensure that row orthogonality in the input matrices is verified.
gap> F:=GF(5);; gap> Hx:=One(F)*[[1,-1,0,0 ],[0,0,1,-1]];; gap> Hz:=One(F)*[[1, 1,1,1]];; gap> DistRandCSS(Hz,Hx,100,0,2 : field:=F); 2
Now, if we set the minimum distance mindist 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.
gap> DistRandCSS(Hz,Hx,100,2,2 : field:=F); -2
The function DistRandStab 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.
gap> F:=GF(5);; gap> H:=One(F)*[[1,0, -1,0, 0,0, 0,0 ], # original Hx in odd positions > [0,0, 0,0, 1,0, -1,0 ], > [0,1, 0,1, 0,1, 0,1 ]];; # original Hz in even positions gap> DistRandStab(H,100,0,2 : field:=F); 2
‣ ReadMTXE( FilePath[, pair]: field := GF(2) ) | ( function ) |
Returns: a list [field, pair, Matrix, array_of_comment_strings]
Read matrix from an MTX file, an extended version of Matrix Market eXchange coordinate format supporting finite Galois fields and two-block matrices (A|B) with columns A=(a_1, a_2, \ldots , a_n) and B=(b_1, b_2, \ldots , b_n), see Chapter 5.
FilePath name of existing file storing the matrix
pair (optional argument): specifies column ordering; must correlate with the variable type in the file
pair=0 for regular single-block matrices (e.g., CSS) type=integer (if pair not specified, pair=0 is set by default for integer)
pair=1 intercalated columns with type=integer (a_1, b_1, a_2, b_2,\ldots)
pair=2 grouped columns with type=integer (a_1, a_2, \ldots, a_n\; b_1, b_2,\ldots, b_n)
pair=3 this is the only option for type=complex with elements specified as "complex" pairs
field (Options stack): Galois field, default: \mathop{\rm GF}(2).
Must match that given in the file (if any). Notice: with pair=1 and pair=2, the number of matrix columns specified in the file must be even, twice the block length of the code. This version of the format is deprecated and should be avoided.
1st line of file must read:
%%MatrixMarket matrix coordinate `type` general
with type being either integer or complex
2nd line (optional) may contain:
% Field: `valid_field_name_in_Gap`
or
% Field: `valid_field_name_in_Gap` PrimitiveP(x): `polynomial`
Any additional entries in the second line are silently ignored. By default, \mathop{\rm GF}(2) is assumed; the default can be overriden by the optional field 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.
See Chapter 5 for the details of how the elements of the group are represented depending on whether the field is a prime field ( q a prime) or an extension field with q=p^m , p prime, and m>1.
‣ WriteMTXE( StrPath, pair, matrix[, comment[, comment]]: field := GF(2) ) | ( function ) |
Returns: no output
Export a matrix in Extended MatrixMarket format, with options specified by the pair argument.
StrPath - name of the file to be created;
pair: parameter to control the file format details, must match the storage type of the matrix.
pair=0 for regular matrices (e.g., CSS) with type=integer
pair=1 for intercalated columns (a_1, b_1, a_2, b_2, \ldots) with type=integer (deprecated)
pair=2 for grouped columns with type=integer (this is not supported!)
pair=3 for columns specified in pairs with type=complex.
Columns of the input matrix must be intercalated unless pair=0
optional comment: one or more strings (or a single list of strings) to be output after the MTX header line.
The second line specifying the field will be generated automatically only if the GAP Option field is present. As an option, the line can also be entered explicitly as the first line of the comments, e.g., "% Field: GF(256)"
See Chapter 5 for the details of how the elements of the group are represented depending on whether the field is a prime field ( q a prime) or an extension field with q=p^m , m>1 .
‣ QDR_AverageCalc( vector ) | ( function ) |
Calculate the average of the components of a numerical vector
‣ QDR_SymplVecWeight( vector, field ) | ( function ) |
Returns: symplectic weight of a vector
Calculate the symplectic weight of a vector with an even number of entries from the field field. The elements of the pairs are intercalated: (a_1, b_1, a_2, b_2,\ldots).
Note: the parity of vector length and the format are not verified!!!
‣ QDR_WeightMat( matrix ) | ( function ) |
Returns: number of non-zero elements
count the total number of non-zero entries in a matrix.
‣ QDR_DoProbOut( vector, n, num ) | ( function ) |
Returns: nothing
Aux function to print out the relevant probabilities given the list vector of multiplicities of the codewords found. Additional parameters are n, the code length, and num, the number of repetitions; these are ignored in the present version of the program. See 3.3 for related discussion.
‣ QDR_ParseFieldStr( str ) | ( function ) |
Returns: the corresponding Galois field
Parse a string describing a Galois field Supported formats: Z(p), GF(q), and GF(q^m), where p must be a prime, q a prime or a power of a prime, and m a natural integer. No spaces are allowed.
‣ QDR_ParsePolyStr( F, str ) | ( function ) |
Returns: the corresponding polynomial
Parse string str as a polynomial over the field F. Only characters in "0123456789*+-^x" are allowed in the string. In particular, no spaces are allowed.
‣ QDR_FieldHeaderStr( F ) | ( function ) |
Returns: the created header string
Create a header string describing the field F for use in the function WriteMTXE. If F is a prime Galois field, just specify it: For an extension field \mathop{\rm GF}(p^m) with p prime and m>1, also give the primitive polynomial which should not contain any spaces. For example, See Chapter 5 for details.
‣ QDR_ProcessFieldHeader( recs, optF ) | ( function ) |
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 QDR_ProcEntry()
Process the field header (second line in the MTXE file format), including the field, PrimitiveP record, and anything else. Supported format options:
Field: `field` PrimitiveP(x): `polynomial` Format: `format`
Here the records should be separated by one or more spaces; while field, polynomial, and format should not contain any spaces. Any additional records in this line will be silently ignored.
The field option should specify a valid field, \mathop{\rm GF}(q) or \mathop{\rm GF}(p^m), where q>1 should be a power of the prime p.
The polynomial should be a valid expanded monic polynomial with integer coefficients, with a single independent variable x; it should contain no spaces. An error will be signaled if polynomial is not a valid primitive polynomial of the field. This argument is optional; by default, Conway polynomial will be used.
The optional format string (not implemented) should be "AdditiveInt" (the default for prime fields), "PowerInt" (the default for extension fields with m>1) or "VectorInt".
AdditiveInt indicates that values listed are expected to be in the corresponding prime field and should be interpreted as integers mod p. PowerInt 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. VectorInt 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.
On input, recs should contain a list of tokens obtained by splitting the field record line; optF should be assigned to ValueOption("field") or fail.
‣ QDR_ProcEntry( str, fmt, FileName, LineNo ) | ( function ) |
Returns: the converted field element
Convert a string entry which should represent an integer to the Galois Field element as specified in the fmt.
str is the string representing an integer.
fmt is a list [Field, ConversionDegree, FormatIndex]
Field is the Galois field \mathop{\rm GF}(p^m) of the code
ConversionDegree c : every element x read is replaces with x^c. This may be needed if a non-standard primitive polynomial is used to define the field.
FormatIndex in {0,1,2}. 0 indicates no conversion (just a modular integer). 1 indicates that the integer represents a power of the primitive element, or -1 for 0. 2 indicates that the integer encodes coordinates of a length m vector as the digits of a p-ary integer (not yet implemented).
FileName, LineNo are the line number and the name of the input file; these are used to signal an error.
gap> QDR_AverageCalc([2,3,4,5]); 3.5
gap> F:=GF(3);; gap> x:=Indeterminate(F,"x");; poly:=One(F)*(1-x);; gap> n:=5;; gap> mat:=QDR_DoCirc(poly,n,2*n,F);; # make a circulant matrix with 5 rows gap> Display(mat); 1 2 . . . . . . . . . . 1 2 . . . . . . . . . . 1 2 . . . . . . . . . . 1 2 . . . . . . . . . . 1 2
These examples illustrate the allowed format of field definitions in the header of an MTXE file:
gap> QDR_ParseFieldStr("Z(5)"); Z(5) gap> QDR_ParseFieldStr("Z(17)"); Z(17) gap> QDR_ParseFieldStr("GF(5^2)"); GF(5^2) gap> QDR_ParseFieldStr("GF(25)"); GF(5^2) gap> QDR_ParseFieldStr("GF(125^2)"); GF(5^6)
gap> QDR_ParsePolyStr(GF(25),"x^2+1"); x^2+Z(5)^0
‣ QDR_MakeH( matrix, field ) | ( function ) |
Returns: H (the check matrix constructed)
Given a two-block matrix with intercalated columns (a_1, b_1, a_2, b_2, \ldots) , calculate the corresponding check matrix H with columns (-b_1, a_1, -b_2, a_2, \ldots) .
The parity of the number of columns is verified.
‣ QDR_DoCirc( poly, m, n, field ) | ( function ) |
Returns: m by 2*n circulant matrix constructed from the polynomial coefficients
Given the polynomial poly a_0+b_0 x+a_1x^2+b_1x^3 +\ldots with coefficients from the field F, constructs the corresponding m by 2n double circulant matrix obtained by m repeated cyclic shifts of the coefficients' vector by s=2 positions at a time.
generated by GAPDoc2HTML