Gilbert-Varshamov Bound

Problem

Return the Gilbert-Varshamov lower bound on the maximum size of a binary code of length n and minimum distance d:

M >= ceil(2^n / sum_{i=0}^{d-1} C(n, i))

Return the value of the right-hand side as an integer.

Hint

For d = 1 the ball volume is 1 and the bound is the whole space.

case 1

in: [7,3]

expected: 5

case 2

in: [7,1]

expected: 128

case 3

in: [15,3]

expected: 271

case 4

in: [5,3]

expected: 2

case 5

in: [10,5]

expected: 3

Starter codePython

import math
def gilbert_varshamov_bound(n, d):
    # Your code here
    pass

5 test cases · run your code against them in the editor