Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Combinatorial encoding/decoding
import math
def bin_string(n, size):
l = ['0'] * size
for i in xrange(size):
l[size - 1 - i] = '01'[n % 2]
n /= 2
return ''.join(l)
def gen_binomial_table(n):
c = [[1] + [0] * (n - 1)]
for i in xrange(1, n + 1):
c.append([1] + [c[i - 1][j - 1] + c[i - 1][j] for j in xrange(1, n)])
return c
def encode_rank_to_combination(rank, n):
num_ones = n / 2
codeword = 0
while num_ones:
n = num_ones - 1
while choose_lookup[n + 1][num_ones] <= rank:
n += 1
codeword |= (1 << n)
rank -= choose_lookup[n][num_ones]
num_ones -= 1
return codeword
def decode_combination_to_rank(codeword, n):
num_ones = 1
result = 0
i = 0
while codeword:
if codeword & 1:
result += choose_lookup[i][num_ones]
num_ones += 1
codeword >>= 1
i += 1
return result
if __name__ == '__main__':
n = 12
choose_lookup = gen_binomial_table(n)
num_words = choose_lookup[n][n / 2]
print '%.2f bits to %d balanced bits' % (math.log(num_words) / math.log(2.0), n)
print
print 'Printing coding table'
codewords = [encode_rank_to_combination(i, n) for i in xrange(num_words)]
for i, codeword in enumerate(codewords):
print i, bin_string(codeword, n)
print
print 'Printing decoding table'
for codeword in codewords:
print bin_string(codeword, n), decode_combination_to_rank(codeword, n)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.