| is_prime_power?(n:Pos) |
| True if
n, a positive integer, is a power of a prime number,
and false otherwise. Examples: primepower.cc. |
| next_q(x:Real) |
| The first prime power
≥ x. Examples: next_q.cc. |
| floor(x) |
| The greatest integer ≤x, usually denoted ⌊x⌋ |
| ceiling(x) |
| The smallest integer ≥x, usually denoted ⌈x⌉ |
A (block error-correcting) code is represented by a table
C that contains
the relevant data of the code. For example, for an alternant code
the table entries have the labels
h_,
a_,
r_,
b_ and
H_,
and optionally
K_ or
G_ or both.
The values of these fields are, respectively, the vector
h, the
vector
a, the order
r, the vector
b of the reciprocals
of the elements of
a, the alternant control matrix
H associated to
h,
a and
r,
and, when present, the base field
K and a generating matrix
G. The trick of
appending the underscore character to the table field labels produces names
that are unlikely to be used as identifiers elsewhere and yet that are
mnemonic of the meaning of their values. To extrat the value of a field,
say a_,
we form the expression
C(a_),
or
a_\C.
| alternant_code(h,a,r), alternant_code(h,a,r,K), alternant_code(h,a,r) |
| If h and a are vectors of the same length, say n, with entries in a finite field F and r is a positive integer such that r≤n, alternant_code(h,a,r) constructs the alternant code AK(h,a,r) associated to h, a and r over a ground field K that is assumed to be known from the context (usually K=source(F), the field out of which F has been constructed). The call alternant_code(h,a,r,K), where K is a subfield of F, is defined to be alternant_code(h,a,r) | {K_=K}. The call alternant_code(a,r) is defined as alternant_code(a,a,r). |
| BCH(w,d,b), BCH(w,d,b,K), BCH(w,d), BCH(w,d,K) |
| If w is a non-zero element of a finite field F, d>0 an integer such that d < n=order(w), BCH(w,d,b)=alternant(h,a,d-1), where h=geometric_series(wb,n) and a=geometric_series(w,n). This code is the BCH code of lenght n=order(w), design distance d and offset b. On the other hand, BCH(w,d) = BCH(w,d,1), which is called the strict BCH code of length n=order(w) and design distance d. Finally BCH(w,d,b,K) = BCH(w,d,b) | {K_=K} and BCH(w,d,K) = BCH(w,d) | {K_=K}. |
| RS(a,k), RS(F,r) |
| Given a finite field K, a vector a∈Kn, RS(a,k) implements RSa(k) as alternant_code(h,a,n-k) | {G_=vandermonde(a,k), K_=field(a)}, where h is the vector in Kn such that hi=Πj≠i 1/(ai - aj). Note that its generating matrix is included in the data of the code, and also the base field K (since it can be inferred from the vector a, it is not necessary to include it a parameter of the function RS. If F is a finite field and r a non-negative integer, and w is a primitive element of F, RS(F,r) = BCH(w, r+1, F), which is the RS code of dimentions n−r on the vector of non-zero elements of F. |
| volume(n,r,q), volume(n,r) |
| The cardinal of the Hamming ball of radius r in the q-ary Hamming space of length n ( Fn, with |F| = q). |
| ub_singleton(n,d,q), ub_singleton(n,d) |
| The Singleton upper bound on M for codes (n,M,d)q. |
| ub_sphere(n,d,q), ub_sphere(n,d) |
| The sphere (or Hamming) upper bound on M for codes (n,M,d)q. |
| lb_gilbert(n,d,q), lb_gilbert(n,d) |
| The Gilbert lower bound on M for codes (n,M,d)q. |
| lb_gilbert_varshamov(n,d,q), lb_gilbert_varshamov(n,d) |
| The Gilbert-Varshamov lower bound on M for codes (n,M,d)q. |
| hadamard_decoder(y,H) |
| If H is a Hadamard matrix of order n and y is a binary vector of length n, the function decodes y with respect to the Hadamard code associated with H. Reference: TC08-6. |
| meggitt(y,g,E) |
| Given the Meggitt table
E for the cyclic code of length
n over
a finite field
K generated by the monic polynomial
g, and a vector
y∈Kn, this function decodes
y according to Meggitt algorithm.
Reference: TC08-4.
Examples: meggit-table-G2.cc (deconding the binary Golay code) and meggit-table-G3.cc (deconding the ternary Golay code). |
| sugiyama(r0,r1,t) |
| Given non-zero univariate polynomials r0 and r1 in the variable z such that 0< deg(r1) ≤ deg(r0), and an integer t such that t ≤ deg(r1), this function returns a pair {v,r} of univariate polynomials in z such that r ≡ v·r1 mod r0 and deg(r)< t. This function is a key subroutine of the BMS decoder. Reference: TC08-4. |
| alternant_decoder(y,C), alternant_decoder(C), BMS(y,C), BMS(C) |
| If C is an alternant code over the finite field K, and y is a vector in Kn, alternant_decoder(y,C) returns the result of decoding y by the Berlekamp-Masssey-Sugiyama algorithm. The call alternant_decoder(C) returns the function y→alternant_decoder(y,C). Finally, BMS is defined as a synonym of alternant_decoder. Reference: TC08-4. |
| PGZ(y,C), PGZ(C) |
| If C is an alternant code over the finite field K, and y is a vector in Kn, PGZ(y,C) returns the result of decoding y by the Petersen-Gorenstein-Zierler algorithm. The call PGZ(C) returns the function y→PGZ(y,C). Reference: TC08-4. |
| rd_linear_combination(G, K) |
| If G is matrix and K is a field (or a ring), rd_linear_combination(G,K) returns a linear combination of the rows of G with coefficients randomly chosen in K. |
| rd_error_vector(n,s,K), rd_error_vector(s,K) |
| If n and s are positive intgers, s≤n, and K is a field (or a ring), rd_error_vector(n,s,K) produces a vector in Kn of weight s whose non-zero positions and the corresponding values have been chosen randomly. The function rd_error_vector(s,K) is defined as rd_error_vector(q-1,s,K), where q is the cardinal of K. |
| decoder_trial(C,s,K) |
| If C is a code (let n be its length), s a positive integer ≤n, and K a field, decoder_trial(C,s,K) first generates a random vector x of C and a random error pattern e in Kn of weight s, then finds the value x*=alternant_decoder(x+e,C) and presents [x,e,x+e] if x* = x (correct decoding), [x,e,x+e,x*] if x* is a vector ≠ x (undetectable error), and [x,e] if x* is not a vector (decoder error). If the field K is included in C, then we can use decoder_trial(C,s) instead, as this call is defined to be decoder_trial(C, s, K_\C) |
| Zmod(n), Zn(n) |
| If n is an integer
>1, this function constructs the ring
Zn.
Zn is defined as a synonym of
Zmod. If
A=Zmod(n), and
k is any integer, the
expression k:A yields the value
k mod n.
Example: Zmod.cc |
| extension(A, t, p(x)), extension(A, p(x)) source(B) |
| If
A is a ring, p(x) a univariate
monic polynomial in the free variable x with
coefficients in A, and t is a
variable (possibly x),
extension(A, t, p(x)) constructs the
ring A[x]/(p(x)),
and sets t=[x] (the class of
x mod p(x)). The call
extension(A, p(x)) is equivalent to
extension(A, x, p(x)).
After this call, x is no longer free, as it has been
bound to the class of x mod
p(x).
If B=extension(A,t,p(x)), the ring A can be recovered with the function source(B). The elements 1,x,...,xn−1 form a free basis of B over A, in the sense that every element of B has a unique expression in the form a0+ a1x+···+ an−1an−1 . We say that 1,x,...,xn−1 is the standard basis of B over A. Examples: ring.cc If K is a field and p(x)∈K[x] is irreducible, then L=extension(K, t, p(x)) is again a field, and K can be recovered as source(L). The minimum subfield of a field F can be obtained with the function base (or prime_field(F)). Remark. To make sure that x is a free variable before any of the calls explained in this section, use the command clear(x). Examples: field.cc |
| order(x) |
| For
x
a non-zero element of a
GF,
the order of
x.
Examples: order.cc |
| legendre(x,F), QR(F), QNR(F) |
| If
x
is a non-zero element of the finite field
F
of characteristic
≠2,
legendre(x,F)
retuns 1
if x
is quadratic residue in
F and
−1 otherwise.
By convention, legendre(0) is 0.
For x≠0,
legendre(x,F) coincides with
(−1)(q−1)/2, where
q is the cardinal of
F.
QR(F) yields the list of the non-zero quadratic residues of F. Similary, QNR(F) yields the list of the quadratic non-residues of F. Examples: legendre.cc |
| parity_completion(G), left_parity_completion(G) |
| If
G is a
k × n
matrix, it adds to the right of
G the colum formed by the negatives of the sums
of the rows of
G. Thus the sum of every row of the matrix so
obtained is 0.
left_parity_completion(G) works as parity_completion(G), but with the extra column placed on the left of G. Examples: parity-completion.cc |
| paley_matrix(F) |
|
If
F
is a finite field of
q
elements,
paley_matrix(F)
yields the
q × q
matrix
(legendre(xi-xj)),
where
x0,...,xq−1
are the elements of
F in some order.
Examples: paley.cc |
| vandermonde(a,r) |
|
If
a
is a vector,
vandermonde(a,r)
produces the vandermonde matrix of
r rows associated to
a.
Examples: vandermonde.cc |
| cyclic_matrix(g,n), cyclic_normalized_matrix(g,n) |
|
If
g
is a monic univariate polynomial of degree
n-k>0
dividing
Xn−1,
or its vector of coefficents,
cyclic_matrix(g,n)
yields the standard generating matrix of the cyclic code
Cg.
cyclic_normalized_matrix(g,n) works like cyclic_matrix(g,n), but the returned matrix is the normalized generating matrix of the cyclic code Cg. Examples: cyclic-matrix.cc |
| cyclic_control_matrix(g,n), cyclic_normalized_control_matrix(g,n) |
|
If
h
is a monic univariate polynomial of degree
k>0
dividing
Xn−1,
or its vector of coefficents,
cyclic_control_matrix(g,n)
yields the standard control
matrix of the cyclic code Cg,
g=(Xn−1)/h.
cyclic_normalized_control_matrix(g,n) is the standard control matrix associated to cyclic_normalized_matrix(g,n). Examples: cyclic-control-matrix.cc |
| components(x,F), blow(h,F) |
|
If
F
is a finite field and
x
an element of
F,
components(x,F)
the vector of components of
x
with respect to the standard basis of
F over source(F)
(see extension in
Finite rings and fields).
If F is a finite field and h∈Fn, blow(h,F) delivers the vector obtained by replacing each element of h by the sequence of its components with respect to the standard basis of F over source(F). Examples: components.cc |
| blow(H,F), prune(H,F) |
|
If
F
is a finite field and
Hn
is an
r×n
matrix with coefficients in
F,
blow(H,F)
copnstructs the matrix obtained by replacing each entry of
H
by the column of its components with respect to the standard basis of
F
over source(F).
If H is any matrix, prune(H) eliminates each row of H that is a linear combination of the preceding ones. Examples: blow-prune-1.cc, blow-prune-2.cc |
| alternant_matrix(h,a,r), alternant_matrix(a,r), alternant_matrix(P,A) | |||||||||||||||||||
|
The call alternant_matrix(h,a,r) privides
the alternant control matrix of order
r associated to the vectors
h and
a.
The call alternant_matrix(a,r)
is equivalent to
alternant_control_matrix(a,a,r).
The call
alternant_matrix(P,A), where
P=[p1,...,pr]
is assumed to be a vector of univariate polynomials
and A=[a1,...,an]
a vector, constructs the matrix
(pi(aj)), or
Examples:
alternant-matrix.cc
|
| order(k,n) |
|
If
gcd(k,n)=1, the order of
k in Zn*.
Examples: order.cc |
| cyclotomic_class(k,n,q), cyclotomic_class(k,n) |
|
Assuming that
q and n
are positive integers and that
gcd(q,n)=1,
the call
cyclotomic_class(k,n,q) supplies the
q-cyclotomic class of
k mod n, which by definition is the
list
{k, q·k,q2·k,...,qr−1·k},
where the operations are done mod
n and
r is the least positive integer such that
qr·k=1.
The call cyclotomic_class(k,n) is defined as cyclotomic_class(k,n,2). Examples: cyclotomic-classes.cc |
| cycloctomic_classes(n,q), cycloctomic_classes(n) |
|
Assuming that
q and n
are positive integers and that
gcd(q,n)=1,
the function
cycloctomic_classes(n,q)
furnishes the list of all the q-cyclotomic
classes mod n. Finally,
cycloctomic_classes(n) is defined as
cycloctomic_classes(n,2).
Examples: cyclotomic-classes.cc |
| Finite_field, GF |
|
is?(F, Finite_field) is
true
if and only if the object
F is a finite field.
GF is a synonym of
Finite_field.
Examples: GF.cc |
| support(x), weight(x), wt(x) |
| If v is a vector, support(x) yields the vector of the indices i in the range of x such that xi≠0. The value of weight(x) (or of wt(x)) is the length of support(x). |
| hamming_distance(x,y), hd(x,y) |
| If x and y are vectors or lists of the same length, hamming_distance(x,y) (or hd(x,y)) supplies the Hamming distance between x and y, which by definition is the cardinal of the set of indices i in the range of the vectors such that xi ≠ yi. |
| vector(p), polynomial(a, X) |
| If p is a univariate polynomial, vector(p) gives the vector of its coefficients. The construction of the polynomial a0+ a1X+···+ anXn from the vector a=[a0,a1,...,an] and the variable X is accoplished by the call polynomial(a, X). |
| geometric_series(a,x,n), geometric_series(x,n) |
| The first call produces the vector [a,a·x,...,a·xn−1]. The second is defined as geometric_series(1,x,n). |
| invert_entries(a) |
| If a is a vector with no zero entries, the vector [1/a1,...,1/an]. |
| prod(x,y) |
| If x and y are vectors of the same length n, prod(x, y) constructs the vector [ x1·y1,...,xn·yn] . |
| min_weight(X), min_weights(X) |
| If X is a list of vectors of the same length, min_weight(X) supplies the minimum of the weights of the vectors in X. On the other hand min_weights(X) selects the sublist of X formed by the vectors whose weight is min_weight(X). |
| cyclic_shift(a), cyclic_shifts(a) |
| If a is a vector of length n, cyclic_shift(a) yields the vector [a2,...,an, a1]. The function call cyclic_shifts(a) constructs the list of distinct repeated cyclic shifts of a. |