Hamming Bound Redundancy

Problem

For a binary code of block length n with minimum distance d, let t = floor((d - 1) / 2). The sphere-packing bound requires 2^r syndromes to cover a radius-t ball of size sum_{i=0}^{t} C(n, i), where r is the number of redundancy bits. Return the smallest r >= 0 that satisfies 2^r >= that sphere size.

Hint

Increasing the redundancy by one bit doubles the number of available syndromes.

Test cases

case 1

in: [7,3]

expected: 3

case 2

in: [15,3]

expected: 4

case 3

in: [7,7]

expected: 6

case 4

in: [4,3]

expected: 3

case 5

in: [3,3]

expected: 2

Starter codePython

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

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