Delsarte, a.k.a. Linear Programming (LP), upper bounds.

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:

  • Dmitrii V. (Dima) Pasechnik (2012-10): initial implementation.
sage.coding.delsarte_bounds.Krawtchouk(n, q, l, i)

Compute K^{n,q}_l(i), the Krawtchouk polynomial: see Wikipedia article Kravchuk_polynomials. It is given by

\[K^{n,q}_l(i)=\sum_{j=0}^l (-1)^j(q-1)^{(l-j)}{i \choose j}{n-i \choose l-j}\]

EXAMPLES:

sage: Krawtchouk(24,2,5,4)
2224
sage: Krawtchouk(12300,4,5,6)
567785569973042442072
sage.coding.delsarte_bounds.delsarte_bound_additive_hamming_space(n, d, q, d_star=1, q_base=0, return_data=False, solver='PPL', isinteger=False)

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:

  • n – the code length
  • d – the (lower bound on) minimal distance of the code
  • q – the size of the alphabet
  • d_star – the (lower bound on) minimal distance of the dual code; only makes sense for additive codes.
  • q_base – if 0, the code is assumed to be nonlinear. Otherwise, q=q_base^m and the code is linear over F_{q_base}.
  • return_data – if True, return a triple (W,LP,bound), where W is 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, or, if isinteger==False, even have integer entries.
  • solver – the LP/ILP solver to be used. Defaults to PPL. It is arbitrary precision, thus there will be no rounding errors. With other solvers (see MixedIntegerLinearProgram for the list), you are on your own!
  • isinteger – if True, uses an integer programming solver (ILP), rather that an LP solver. Can be very slow if set to True.

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
sage.coding.delsarte_bounds.delsarte_bound_hamming_space(n, d, q, return_data=False, solver='PPL')

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

  • return_data – if True, return a triple (W,LP,bound), where W is

    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.

  • solver – the LP/ILP solver to be used. Defaults to PPL. It is arbitrary

    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.

Previous topic

Canonical forms and automorphisms for linear codes over finite fields.

Next topic

Huffman Encoding

This Page