This module provides LP upper bounds for the parameters of codes. Exact LP solver, PPL, is used by defaut, ensuring that no rounding/overflow problems occur.
AUTHORS:
Compute K^{n,q}_l(i), the Krawtchouk polynomial: see Wikipedia article Kravchuk_polynomials. It is given by
EXAMPLES:
sage: Krawtchouk(24,2,5,4)
2224
sage: Krawtchouk(12300,4,5,6)
567785569973042442072
Find the Delsarte LP bound on F_{q_base}-dimension of additive codes in Hamming space H_q^n of minimal distance d with minimal distance of the dual code at least d_star. If q_base is set to non-zero, then q is a power of q_base, and the code is, formally, linear over F_{q_base}. Otherwise it is assumed that q_base==q.
INPUT:
EXAMPLES:
The bound on dimension of linear \(F_2\)-codes of length 11 and minimal distance 6:
sage: delsarte_bound_additive_hamming_space(11, 6, 2)
3
sage: a,p,val=delsarte_bound_additive_hamming_space(11, 6, 2, return_data=True)
sage: [j for i,j in p.get_values(a).iteritems()]
[1, 0, 0, 0, 0, 0, 5, 2, 0, 0, 0, 0]
The bound on the dimension of linear \(F_4\)-codes of length 11 and minimal distance 3:
sage: delsarte_bound_additive_hamming_space(11,3,4)
8
The bound on the \(F_2\)-dimension of additive \(F_4\)-codes of length 11 and minimal distance 3:
sage: delsarte_bound_additive_hamming_space(11,3,4,q_base=2)
16
Such a d_star is not possible:
sage: delsarte_bound_additive_hamming_space(11,3,4,d_star=9)
Solver exception: 'PPL : There is no feasible solution' ()
False
Find the classical Delsarte bound [1] on codes in Hamming space H_q^n of minimal distance d
INPUT:
n – the code length
d – the (lower bound on) minimal distance of the code
q – the size of the alphabet
a weights vector, and LP the Delsarte bound LP; both of them are Sage LP data. W need not be a weight distribution of a code.
precision, thus there will be no rounding errors. With other solvers (see MixedIntegerLinearProgram for the list), you are on your own!
EXAMPLES:
The bound on the size of the \(F_2\)-codes of length 11 and minimal distance 6:
sage: delsarte_bound_hamming_space(11, 6, 2)
12
sage: a, p, val = delsarte_bound_hamming_space(11, 6, 2, return_data=True)
sage: [j for i,j in p.get_values(a).iteritems()]
[1, 0, 0, 0, 0, 0, 11, 0, 0, 0, 0, 0]
The bound on the size of the \(F_2\)-codes of length 24 and minimal distance 8, i.e. parameters of the extened binary Golay code:
sage: a,p,x=delsarte_bound_hamming_space(24,8,2,return_data=True)
sage: x
4096
sage: [j for i,j in p.get_values(a).iteritems()]
[1, 0, 0, 0, 0, 0, 0, 0, 759, 0, 0, 0, 2576, 0, 0, 0, 759, 0, 0, 0, 0, 0, 0, 0, 1]
The bound on the size of \(F_4\)-codes of length 11 and minimal distance 3:
sage: delsarte_bound_hamming_space(11,3,4)
327680/3
Such an input is invalid:
sage: delsarte_bound_hamming_space(11,3,-4)
Solver exception: 'PPL : There is no feasible solution' ()
False
REFERENCES:
[1] | P. Delsarte, An algebraic approach to the association schemes of coding theory, Philips Res. Rep., Suppl., vol. 10, 1973. |