INDEX

• Combinatorics
• Arithmetic
• Modular arithmetic
• Vectors
• Polynomials
• Finite rings and fields
• Matrices
• Code constructors
• Decoders
• Decoding tools
• Random resources

Combinatorics

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.

» index | PyCC

Arithmetic

» index | PyCC

Modular arithmetic

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).

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).

» index | PyCC

Vectors

hd (x, y)

If x and y are vectors or lists of the same length, 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.

coeffs (p)

If p is a polynomial, coeffs(p) gives the list of its coefficients, from highest to lowest degree. The multivariable polynomials are considered univariate polynomials in the last variable with coefficients in the polynomial ring of the previous variables.

geometric_series (x, n, s0) geometric_series (x, n)

The first call produces the vector [s0,s0·x,...,s0·xn−1]. The second is defined as geometric_series(x,n,1), which therefore supplies the vector [1, x,...,xn−1].

invert_entries (a)

If a is a vector with no zero entries, the vector [1/a1,...,1/an].

prod (x, y) dot (x, y)

If x and y are lists or vectors of the same length n, prod(x, y) constructs the vector [ x1·y1,...,xn·yn] and dot(x, y) yields the sum x1·y1+···+xn·yn

» index | PyCC

Polynomials

Finite rings and fields

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

» index | dic | ict |

Codes

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 length 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.

» index | dic | ict |

Decoders

     RS_ID(a,k,y):=
     begin
	local n=length(a), t=floor((n-k)/2), P, Q, PQ, T
	P=vandermonde(a,n-t)'
	Q=vandermonde(a,n-k-t+1)'
	Q=[(y.j)*(Q.j) with j in 1..n]
        PQ=kernel((P|Q))'.1
        P=polynomial(take(PQ,n-t),T)
        Q=polynomial(take(PQ,-(n-k-t+1)),T)
        if remainder(P,Q)==0 then pad(vector(-P/Q),k) else "ID Error" end
     end;
     #
     RS_ID(a,k):= y --> RS_ID(a,k,y;

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.

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. 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.

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.

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).

» index | dic | ict |

Decoding tools

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)

» index | dic | ict |

Huffman trees and codes

» index | dic | ict |

Matrices

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 p1(a1) · · · p1(an) · · · · · · pr(a1) · · · pr(an)

Examples: alternant-matrix.cc

» index | dic | ict |

Random resources

rd_choice (X) rd_choice (X, m) = rd_choice (m, X)

If X is a list or a vector, rd_choice (X) returns one of its elements selected at random. If m is a positive integer, not greater than the length of X, then the second form returns a list or a vector of m elements of X selected at random.

rd_choice (n, m)

If n and m are positive integers with m < n, this function returns a choice, structured as a list, of m distinct integers chosen at random in the range 1..n.

rd (A) rd (m, A) = rd (A,m)

If A is a ring, the first call yields an element of A chosen at random. The second form yields, if m is a positive integer, a list of m elements of A, not necessarily distinct, chosen at random.

rd_nonzero (A) rd _nonzero (m, A) = rd _nonzero (A, m)

If A is a ring, the first expression supplies a non-zero an element of A chosen at random. The second form provides, if m is a positive integer, a list of m non-zero elements of A, not necessarily distinct, chosen at random.

rd_linear_combination (G, A)

If A is a ring and G a matrix with entries in A, this function call returns a linear combination of the rows of G with coefficients of A chosen at random.

rd_error_vector (n, m, A) rd_error_vector (m, A) rd_error_vector (n, m)

If A is a ring and n and m are positive integers with m ≤ n, the first form returns a vector of weight m and length n with entries in A. The second form is like the first, but with n equal to the cardinal of A minus 1, that is, n = cardinal(A)-1. Finally, the third form is like the first, but with A = Z2. So the latter is appropriate for obtaining binary vectors of length n with exactly m bits equal to 1 in positions chosen at random.

» index | dic | ict |

Types and Boolean predicates

Hleaf, Hbtree, Htree, Hforest

These Boolean functions refer to Huffman trees, which are either a Huffman leave or a Huffman binary tree. We represent Huffman leaves as {p,x}, where p is a probability and x a symbol from the source alphabet. The Huffman binary trees have the form {p, L,R}, where L and R are Huffman trees. A Huffman forest is a list of Huffman trees. Now Hleaf(T) returns true if T is a Huffman leave and false otherwise. The expressions Hbtree(T), Htree(T), Hforest(T) have a similar meaning with respect to Huffman binary trees, Huffman trees and Huffman forests. See Huffman trees and codes for some basic functions related to these data types. Examples: huffman-trees&codes-I.cc, huffman-trees&codes-II.cc, huffman-trees&codes-III.cc.

» index | dic | ict |