What Is New

Help Pages

Help for CASA has been revised. In particular we added some type information to the input and output of CASA functions.

The help pages are available in 3 different formats: (a) Maple online help, (b) printed manual, (c) HTML format on our WEB site http://www.risc.uni-linz.ac.at/software/casa. The contents in each format are the same since they are generated from one source.

Following type faces will be used to expose variables (exampleVariable), unevaluated names (exampleName), and CASA function names (exampleFunction).

Data Structures

Since the start of CASA ten years ago, a data structure has been used to hold the data of an algebraic set in one of 4 different representations (implicit, parametric, or projected representation or a representation by places). The data structure has undergone a complete revision. It now uses its own set of variables to enable CASA to store a property list with the algebraic set that will not become unvalid if the user by accident assigns some user variables. This is accomplished by renaming the given variables and parameters of the algebraic set. Each variable is prepended by the string _casaVariable_ and thus it should be different from any variable on the user level.

We removed any reference to global variables that could interfere with other packages. Apart from the identifiers that are listed in the table casa which contains the short names of CASA functions, all identifiers in CASA start either with casa or an additional underscore in front. WE, THEREFORE, FORBID THE ASSIGNMENT TO SUCH NAMES, OTHERWISE WE CAN NOT GUARANTEE THAT CASA WORKS PROPERLY.

In several functions additional variables must be given for the result. For example, to give the implicit equations of a parametrized curve, two new variables are needed. One can either give them explicitly or let CASA choose new variables.

> A := mkParaAlgSet([a, 0], [a]);

[Maple Math]

> B := toImpl(A, [s,t]);

[Maple Math]

> C := toImpl(A);

[Maple Math]

CASA chooses new variables according to the following rule. Look for the first variable in the list casaDefaultVariables that has no assigned value and does not clash with the input variables. If the list is exhausted, build a variable name that starts with the letter x followed by a natural number and increase the number until an unassigned variable is found.

The variable casaDefaultVariables is preassigned, but can be reassigned by the user to any list of names.

In working with Maple V R5 it became possible to work with strings instead of identifiers. We cleaned up the code in several places, especially for indices in tables CASA now uses strings.

New Functions

There are several new function working with algebraic geometric codes. They will be described in separate chapters below.

As one will notice immediately, CASA now shows algebraic sets in different representation more clearly to the eye. This has been achieved by adding the function `print/_casaAlgebraicSet`.

CASA now more clearly distinguishes between affine and projective space. Usually, CASA creates algebraic sets in affine space. If one wants to create an algebraic set in projective space, one must add a parameter.

> A := mkImplAlgSet([x^2*z - y^3], [x,y,z], ["basespace"="projective"]);

[Maple Math]

One now can use the function toProjective to move a given algebraic set to projective space

> B1 := mkImplAlgSet([x^2 - y^3], [x,y]);

[Maple Math]

> B := toProjective(B1, z);

[Maple Math]

or use toAffine to consider only an affine part of an algebraic set.

> A1 := toAffine(A, z);

[Maple Math]

Checking whether an algebraic set lives in affine or projective space can be done by the function isProjective.

> isProjective(A);

[Maple Math]

> isProjective(A1);

[Maple Math]

And whether two algebraic sets live in the same space can be tested by the function equalBaseSpaces.

> equalBaseSpaces(A, B);

[Maple Math]

Another new function is mkAlgSet. It is meant to safe some typing, but also allows to create an algebraic set with just the variables renamed or shifted.

> B := mkAlgSet(A, [z=a+x, y=-y], [y, a, x]);

[Maple Math]

One could also use this function to consider one variable as a parameter, just shrink the variable list.

> C := mkAlgSet(B1,[],[x]);

[Maple Math]

Some access functions to the internal data of an algebraic set have been renamed. Now use generators instead of represent and variableList instead of varlist. A new function parameterList has been added.

> generators(C);

[Maple Math]

> variableList(C);

[Maple Math]

> parameterList(C);

[Maple Math]

To avoid repeated computations, CASA tries to store in the algebraic set structure some additional information, for example, the dimension if it has once been computed. The new function properties shows all stored information about an algebraic set.

> properties(C);

[Maple Math]

[Maple Math]

> dimension(C);

[Maple Math]

> properties(C);

[Maple Math]

[Maple Math]

[Maple Math]

[Maple Math]

[Maple Math]

[Maple Math]

To ease conversion from one representation to another the following functions are provided: toImpl, toPara, toPlac, and toProj. They are merely wrapper functions around the various conversion routines that exist in CASA for several years. Now it is only necessary to specify the target representation; the source representation can be read from the algebraic set that appears as a parameter.

Algebraic sets that are represented by places are now shown automatically with an approximation up to order 10. One can change this order by the function setPuiseuxExpansion.

There is now a function subresultantChain that computes a subresultant chain and a function rationalPoint that computes a rational point on a conic.

Several auxiliary functions have been added to CASA: equalProjectivePoints, pointInAlgSet, homogeneousForm, leadingForm, numberOfTerms, and homogenize.

A few more types are now available in CASA: `type/homogeneousPolynomial`, `type/neighborhoodTree`, `type/casaVariable`, and `type/casaAttributes`.

Removed Functions

As in the previous version various data is stored into the algebraic set structure once it is computed, however, CASA now makes this invisible to the user. Whenever the user asks for some information about an algebraic set, it is first checked whether this information has already been computed and stored. Thus, the functions Attributes, addattr, hasattr, and hasattrib have been removed.

The function repattr has been removed, because algebraic sets will now show directly in which representation they are when they are printed.

The functionality of convertSpace is now achieved through the functions toAffine and toProjective.

The functionality of all conversion functions like convertRep, impl2para, impl2plac, impl2proj, para2impl, para2plac, para2proj, proj2impl, proj2para, and proj2plac is transferred to the functions toImpl, toPara, toPlac, and toProj.

The functions represent, varlist, shAlgSet, and ratpoint have been renamed generators, variableList, properties, and rationalPoint, respectively.

The functionality of reparametrize has been generalized in mkAlgSet.

The type checking function `type/projalgpoly` has been removed. Use the function `type/homogeneousPolynomial` instead.

The following functions have been removed without replacement: extNewton, dictionary, geoprove, and dixon.

Compatibility

CASA in its current version has been upgraded to Maple V release 5. Our previous version 2.3 works under Maple V release 4 and is available from our download page at http://www.risc.uni-linz.ac.at/software/casa/download. Due to several changes in the Maple language, a CASA version for Maple 6 is not yet available.

Note that due to a stricter type checking the functions mkImplAlgSet, mkParaAlgSet, mkPlacAlgSet, and mkProjAlgSet do not accept all input forms as in the previous version of CASA.

The variable `casa/homvars` has been removed. Homogenizing variables will now be provided in a more flexible way through functions and the list stored in casaDefaultVariables.

Miscellaneous

To prevent CASA from clashing with other packages, the use of global variables has been cut. Indexing into arrays is now done using strings instead of identifiers.

Several bugs have been removed.

It is now possible to check the version of CASA. We introduced 4 new variables that are available globally. The variable `casa/version` contains the version number in a string form, for example, "2.4.3". The other variables will then be: `casa/version/major`=2, `casa/version/minor`=4, and `casa/version/patch`=3.

CASA now supports Maple's quiet option. The CASA logo will be suppressed when one uses

interface(quiet=true): with(casa):

to load CASA.

Algebraic Geometric Codes

Algebraic geometric codes have been treated in [20].

We give here a short tutorial on how to work with the corresponding functions implemented in CASA. For more details and background information see the above paper and the references therein.

In order to obtain additional information during the computation one can set the infolevel to values from 0 (no information) to 9 (detailed information).

> infolevel[`casa/finite`] := 0:

At first we construct a Reed-Solomon code of length 15.

We define the code over the line y=0.

> F := finiteField(16):

> F["In"](alpha);

[Maple Math]

> H := finiteCurve(y, F, [x,y,z]);

[Maple Math]

We choose the divisor G to be G = -1(0:0:1) + 6(1:0:0) and take the remaining F-rational points as another divisor D.

> G := makeDivisor([ [0,0,1], [1,0,0] ], [-1,6]);

[Maple Math]

> Code := GoppaPrimary(H, "rest", G):

This is a code whose parity check matrix looks like this:

> print(Code["H"]);

[Maple Math]

In order to decode a code word we must first initialize an error locator. Since the above code is defined on a curve of genus 0, we can apply the Skorobotatov-Vladut algorithm.

Since we do not have a one point code here, we must specify a divisor A. The space L(A) is used to find an error locator whereas L(G-A) is used as the space of test functions.

> A := makeDivisor([ [1,0,0] ], [3]):

> SV := GoppaPrepareSV(Code, A):

Now let us encode the following message.

> a := [1, alpha^14, alpha^10, alpha^8, 0, alpha^9, alpha^4,

> alpha^11, alpha^4];

[Maple Math]

> c := GoppaEncode(a, Code);

[Maple Math]

Now let us add some errors to the code word c. Our code has minimal distance 7, so it should be no problem if we add 3 errors (in places 1, 7, and 8).

> w := c: w[1] := w[1] + alpha: w[7] := w[7] + alpha:

> w[8] := w[8] + alpha^3:

To decode the code word again, we need the Code and the error locator SV.

> b := GoppaDecode(w, Code, SV);

[Maple Math]

We obtain back the message we started with.

> evalm(b-a);

[Maple Math]

Let us consider the Hermitian code defined over the smooth curve x^5+y^4z+yz^4 over the Galois field with 16 elements. This is a code of length 64.

> H := finiteCurve(x^5+y^4*z+y*z^4, F, [x,y,z]);

[Maple Math]

> `casa/finite/Curve/genus`(H);

[Maple Math]

Now we can already construct the primary Goppa code. The divisor D is taken as the sum of the affine F-rational points. The third argument specifies that the divisor G should be taken as 25 times the single point at infinity.

> Code := GoppaPrimary(H, "affine", 25):

To decode, we must initialize an error locator. Since this code is defined on a curve of genus greater than zero, we can use the Duursma-algorithm.

The Duursma-algorithm is implemented only for one point codes, so no extra arguments are necessary. It is sufficient to specify which code is used.

> Du := GoppaPrepareDu(Code):

Let us take the following message.

> a := [alpha^8, alpha^5, 1, alpha^10, 0, alpha^9, alpha^4,

> alpha^7, 1, 1, alpha^14, alpha^10, alpha^8, 0, alpha^9,

> alpha^4, alpha^11, alpha^4, alpha^10, alpha^4, alpha^5,

> alpha^13, alpha^9, alpha^12, alpha^12, alpha^4, alpha^13,

> alpha^5, 1, alpha^5, alpha^6, alpha^8, alpha^3, alpha^2,

> alpha^9, 1, alpha^11, alpha^3, alpha^4, alpha^6, alpha^10,

> alpha, alpha^4, 0

> ];

[Maple Math]
[Maple Math]

Encoding is performed by a simple matrix multiplication.

> c := GoppaEncode(a, Code);

[Maple Math]
[Maple Math]
[Maple Math]

Since the code has minimal distance of at least 15, we can correct up to 7 errors. Let us add some randomness.

> w := c:

> w[20] := w[20] + alpha^7:

> w[21] := w[21] + alpha^10:

> w[23] := w[23] + alpha^5:

> w[35] := w[35] + alpha:

> w[52] := w[52] + alpha^7:

> w[56] := w[56] + alpha:

> w[58] := w[58] + alpha^14:

In order to decode the received word, the code and the error locator must be given. For the entries of order s=26 we really need the voting process. This is not the typical case, however, it might take some tries to find an example where not all error locator candidates give the same estimate. (Detailed information about the computation can be optained by increasing the infolevel.)

> b := GoppaDecode(w, Code, Du);

[Maple Math]
[Maple Math]

We obtain back the message we started with.

> evalm(b-a);

[Maple Math]

Multivariate Polynomial Codes

Multivariate polynomial codes have been treated in [22].

We give here a short tutorial on how to work with the corresponding functions implemented in CASA. For more details and background information see the above paper and the references therein.

Since there is a lot of computation to be done with polynomials over finite fields, several functions are supplied for the basic operations of polynomials in two variables x and y over a finite field.

Generate the field of coefficients of the polynomials;

> F := finiteField(16):

Generate a polynomial in RootOf form

> g := InPolynomial(alpha*x + alpha^2*x^2*y, F);

[Maple Math]

Substitute (x, y) by (1, alpha).

> SubsPolynomial([1, alpha], g, F);

[Maple Math]

Find the roots of g over the finite field F. Print these roots in `nice' alpha form.

> map(F["mapOut"], PolynomialRoots(g, F));

[Maple Math]
[Maple Math]
[Maple Math]

Generate a polynomial h.

> h := InPolynomial(alpha^2*x*y + 1, F);

[Maple Math]

Find the common roots of g and h.

> map(F["mapOut"], PolynomialRoots([g, h], F));

[Maple Math]

Two-dimensional BCH codes can be constructed by the function BCH2. The arguments required are the domain of the code, the parameter delta and the finite field. The function CyclicEncode can be used for encoding. The two arguments required are the message which should be encoded and the code. The function BCHDecode can be used for decoding. Its parameters are the received word and the code.

There is a function GoppaPrimary to construct primary Goppa codes. One-point algebraic geometric codes are special primary Goppa codes, therefore you can use this method to construct a 1-point algebraic geometric code. The arguments required are the curve C, and two divisors D and G = mQ.

Encoding can be done by GoppaEncode. Its parameters are the message and the code.

For decoding, one has to initialize the method one would like to use for decoding. GoppaPrepareSa prepares all preprocessing steps to use Sakata's approach to decoding. Its argument is the code and its result is a table of the results of all the computation which has to be done only once for a given code. GoppaPrepareDu initializes Duursma's method and if the genus of the curve is low one can also use GoppaPrepareSV to initialize the basic algorithm, which doesn't use majority voting for unknown syndroms.

After this initialization one can use GoppaDecode or SakataDecode to decode a received word. The parameters of this methods are the code, the result of the initialization, and the received word.

Three example sessions will follow. In each session a code is constructed, a message encoded, some errors are added and finally the received word is decoded.

The first example is a Reed-Solomon code over GF(16) with designed minimum distance 5. We force the generator polynomial to vanish on 4 subsequent powers of alpha, namely 1, alpha, alpha^2, alpha^3.

This code can be regarded as a 2-dimensional BCH-code of domain (1,15) and delta = (4,0).

> infolevel[`casa/finite`] := 11:

> F := finiteField(16):

> C := BCH2(1,15, [4,0], F):

[Maple Math]

[Maple Math]

[Maple Math]

[Maple Math]

[Maple Math]

One can easily obtain some information about the code.

> eval(C["Delta"]);

[Maple Math]

> eval(C["k"]);

[Maple Math]

> eval(C["Roots"]);

[Maple Math]

> eval(C["ExtField"]["seq"]);

[Maple Math]

Now encode the message and make two errors.

> a := [seq(1, i=1..11)];

[Maple Math]

> c := CyclicEncode(a, C);

[Maple Math]

> w := evalm(c):

> w[7] := w[7] + alpha^5:

> w[13] := w[13] + alpha^8:

> print(w);

[Maple Math]

Decode the message.

> b := BCHDecode(w, C);

[Maple Math]
[Maple Math]

[Maple Math]

[Maple Math]

[Maple Math]

[Maple Math]

[Maple Math]

[Maple Math]

[Maple Math]

[Maple Math]

[Maple Math]

[Maple Math]

[Maple Math]

[Maple Math]

[Maple Math]

[Maple Math]

[Maple Math]

[Maple Math]

[Maple Math]

[Maple Math]

Obviously, this is the message that we started with.

In the next example, we want to constract an at least 2-error correcting code. We choose delta = (4,0) and domain (7,7) over the finite field GF(4)

> infolevel[`casa/finite`] := 10:

> F := finiteField(4):

> C := BCH2(7, 7, [4,0], F):

[Maple Math]
[Maple Math]

[Maple Math]

[Maple Math]

Now encode the message and make two errors.

> a := [seq(1, i=1..27)];

[Maple Math]

> c := CyclicEncode(a, C);

[Maple Math]
[Maple Math]

> w := evalm(c):

> w[1] := w[1] + alpha^2:

> w[19] := w[19] + alpha:

> print(w);

[Maple Math]
[Maple Math]

Decode the message.

> b := BCHDecode(w, C);

[Maple Math]

[Maple Math]

[Maple Math]

[Maple Math]

[Maple Math]

[Maple Math]

[Maple Math]

[Maple Math]

[Maple Math]

[Maple Math]

[Maple Math]

[Maple Math]

[Maple Math]

[Maple Math]

[Maple Math]

[Maple Math]

[Maple Math]
[Maple Math]

[Maple Math]
[Maple Math]

[Maple Math]

Again, this is the message that we started with.

As the last example, we take an Hermitian code defined over the curve H4 = V(x^5 + y^4 * z + y * z^4) over the field GF(16).

This is a 7-error correcting code of length 64. We will show how to decode it using Sakata's approach.

> infolevel[`casa/finite`] := 9:

> F := finiteField(16):

> F["In"](alpha);

[Maple Math]

> H4 := finiteCurve(x^5 + y^4 * z + y * z^4, F);

[Maple Math]

> g := `casa/finite/Curve/genus`(H4);

[Maple Math]

> C := GoppaPrimary(H4, "affine", 25);

[Maple Math]

[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]
[Maple Math]

[Maple Math]
[Maple Math]

[Maple Math]

[Maple Math]

Now encode the message and make 7 errors.

> a := [seq(1, i=1..C["k"])];

[Maple Math]

> c := GoppaEncode(a, C);

[Maple Math]
[Maple Math]

> w := evalm(c):

> for i in [[11,13], [27,5], [39,14], [44, 5], [47,6], [61,5],[62,5]] do

> w[i[1]] := w[i[1]] + alpha^i[2]; od:

> print(w);

[Maple Math]
[Maple Math]

To decode the message with Sakata's approach, we have to initialize the decoding procedure first. (For detailed information about the computation one should increase the infolevel.)

> infolevel[`casa/finite`] := 0:

> H := GoppaPrepareSa(C):

Now we can decode the received word w using the Extended Algorithm.

> b := SakataDecode(w, C, H);

[Maple Math]

We obtain the message that we started with

> evalm(b-a);

[Maple Math]

[Previous][Up][Next]