Opened 10 years ago

Last modified 9 years ago

#12418 closed enhancement

adding Delsarte bound for codes — at Version 15

Reported by: dimpase Owned by: wdj
Priority: major Milestone: sage-5.12
Component: coding theory Keywords:
Cc: jpang, kini, wdj, ncohen, ppurka, ptrrsn_1 Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #12533, #13650 Stopgaps:

Status badges

Description (last modified by dimpase)

Delsarte bound for codes, aka Linear Programming bound, is easy to implement in Sage.

See the attached prototype implementation for details.

One obstacle for this to work well in big dimensions is a lack of arbitrary precision LP solver backend available in Sage. This is taken care of by #12533, which is a dependence for this ticket.

Apply 12418_delsart_bounds.patch

Change History (16)

comment:1 Changed 10 years ago by dimpase

Last edited 10 years ago by dimpase (previous) (diff)

comment:2 Changed 10 years ago by dimpase

  • Cc kini added

comment:3 Changed 10 years ago by dimpase

  • Cc wdj added

comment:4 Changed 10 years ago by dimpase

  • Cc ncohen added
  • Description modified (diff)

comment:5 Changed 10 years ago by ncohen

(GLPK can solve non-integer rational LP. It is not exposed, but may not be too hard either)

comment:6 Changed 10 years ago by dimpase

  • Cc ppurka added

comment:7 Changed 10 years ago by ppurka

The function named delsarte_bound should be renamed to something like delsarte_bound_hamming_space. This is so that in future other functions like delsarte_bound_johnson_space, delsarte_bound_permutation_space, etc can be added easily, without having inconsistencies in naming.

comment:8 Changed 10 years ago by dimpase

  • Cc ptrrsn_1 added

comment:9 Changed 10 years ago by dimpase

  • Description modified (diff)

comment:10 Changed 10 years ago by dimpase

  • Dependencies set to #12533
  • Description modified (diff)

Changed 10 years ago by dimpase

a prototype implementation

comment:11 Changed 10 years ago by dimpase

  • Description modified (diff)
  • Status changed from new to needs_review

comment:12 follow-up: Changed 10 years ago by ppurka

I think the Krawtchouk polynomial could be computed explicitly by not making repeated calls to binomial. This should speed it up. I have something like this in mind:

def Krawtchouk2(n,q,l,i):
    # Use the expression in equation (55) of MacWilliams & Sloane, pg 151
    # We write jth term = some_factor * (j-1)th term
    kraw = jth_term = (q-1)**l * binomial(n, l) # j=0
    for j in range(1,l+1):
        jth_term *= -q*(l-j+1)*(i-j+1)/((q-1)*j*(n-j+1))
        kraw += jth_term
    return kraw

n,q,l,i = 10,8,7,5
timeit('Krawtchouk2(n,q,l,i)')
timeit('Krawtchouk (n,q,l,i)')
print Krawtchouk2(n,q,l,i) == Krawtchouk(n,q,l,i)

625 loops, best of 3: 53.3 µs per loop
625 loops, best of 3: 205 µs per loop
True

I noticed that sage handles nonintegral components in the binomial, so the expression for the Krawtchouk already works with nonintegral n and x.

n,q,l,i = 10.6,8,7,5.4
#timeit('Krawtchouk3(n,q,l,i)')
timeit('Krawtchouk2(n,q,l,i)')
timeit('Krawtchouk (n,q,l,i)')
print Krawtchouk2(n,q,l,i) == Krawtchouk(n,q,l,i)
print Krawtchouk2(n,q,l,i), Krawtchouk(n,q,l,i)

625 loops, best of 3: 382 µs per loop
125 loops, best of 3: 4.74 ms per loop
False
93582.0160001147 93582.0159999999

comment:13 Changed 10 years ago by ppurka

Can you mention when it guarantees a weight spectrum? Would doing an ILP make it a proper weight spectrum?

   - ``return_data`` -- if ``True``, return a weights vector, which actually need not 
     be a proper weight enumerator, or even have integer entries, and the LP. 

Also, I think the term weight enumerator refers to the weight enumerator polynomial. Perhaps using weight distribution or distance distribution is more appropriate here.

comment:14 in reply to: ↑ 12 Changed 10 years ago by dimpase

Replying to ppurka:

I think the Krawtchouk polynomial could be computed explicitly by not making repeated calls to binomial. This should speed it up.

It's probably even faster to compute by using recurrence relations, but I don't think it's important here: LP solving timing clearly dominates the rest.

By the way, would it be interesting to include an option to compute bounds on codes with a prescribed forbidden set of distances, rather than just [1..d] ? It's a trivial add-on. I did this in a prototype code for Johnson schemes, here.

Any other interesting schemes to include? (Johnson scheme takes care of constant weight binary codes, as you know.)

comment:15 Changed 10 years ago by dimpase

  • Dependencies changed from #12533 to #12533, #13650
  • Description modified (diff)
  • Milestone changed from sage-5.4 to sage-5.5
Note: See TracTickets for help on using tickets.