Syndrome Encoder

from itertools import product K=GF(2) C=[(0,0,0),(1,0,1),(1,0,1),(1,1,0)] 

C.remove((0,0,0))#C.remove(3*(0,)) 

G=matrix(K,C) 

G.echelonize() 

G 

[1 0 1]
[0 1 1]
[0 0 0]

[1 0 1]
[0 1 1]
[0 0 0]

G.pivot_rows() 

[0, 1]

[0, 1]

G=matrix(K,[G.row(i) for i in G.pivot_rows()]) G 

[1 0 1]
[0 1 1]

[1 0 1]
[0 1 1]

def make_generator(code,field): n=len(code[0])#the length of the code try: code.remove(n*(0,)) except ValueError: pass A=matrix(field,code) A.echelonize() G=matrix(field,[A.row(i) for i in A.pivot_rows()]) return G 

def make_pcm(code, field): G = make_generator(code, field) rows = G.nrows() pivots = G.pivots() for c in range(len(pivots)): G.swap_columns(c, pivots[c]) X = G[:, rows:] X = -X.transpose() I = identity_matrix(field, X.nrows()) Hp = X.augment(I) for c in range(len(pivots)): Hp.swap_columns(pivots[c], c) return Hp 

def encode(message,generator): K=generator[0,0].parent()#this is the base field v=vector(K,message) return v*G 

# return true if word is a codeword # word must be an integer list, can't be over field... def check(word,PCM): K=PCM[0,0].parent()#the base field v=vector(K,word) return max(PCM*v).is_zero() 

pcm = make_pcm([(1,1,1,0,1),(1,0,1,1,0),(0,1,0,1,1),(1,1,0,1,0)],GF(2)) pcm 

[0 1 1 1 0]
[1 1 1 0 1]

[0 1 1 1 0]
[1 1 1 0 1]

def coset_leader(coset, field): min = coset[0]; minlist = set() for c in coset: if(wt(c) < wt(min)): min = c; minlist.clear() minlist.add(c); if(wt(c) == wt(min)): minlist.add(c); return list(minlist); 

def wt(word): w = 0; for c in word: if(c != 0): w += 1; return w 

def addl(w1, w2, field): w3 = [] for i in range(len(w1)): w3.append(field(w1[i] + w2[i])); return tuple(w3) 

def make_coset_dictionary(code, field): cosets = [code] prod = product(range(len(field)), repeat=len(code[0])) prod.next() #skip the zero vector for i in range(2^len(code[0])): try: e = prod.next() except StopIteration: break; #print not_in_coset(cosets, e), e if(not_in_coset(cosets, e)): cosets.append(map(lambda x: addl(e, x, field), code)) return cosets def not_in_coset(coset, word): for cos in coset: if(word in cos): return false return true 

#makes a python dict, right now coset leader returns a list of ties! def make_SDA(code, field): coder = code[:] sda = dict() cosets = make_coset_dictionary(coder, field) H = make_pcm(code, field) for cos in cosets: cos_lead = coset_leader(cos, field) syndrome = matrix(field, [cos_lead[0]])*H.transpose() syndrome.set_immutable() #print syndrome[0], cos_lead sda[syndrome] = list(cos_lead) # changed from tuple to just the syndrome (immutable) return sda 

sda = make_SDA([(0,0,0,0),(1,0,1,1),(0,1,0,1),(1,1,1,0)], GF(2)) 

def decode(word, code, field): H = make_pcm(code, field) sda = make_SDA(code, field); syndrome=matrix(field, word)*H.transpose() syndrome.set_immutable() e = vector(field,sda[syndrome][0]) return addl(e, word, field); 

# uh.. decode clearly doesn't work field = GF(2) word = vector(field,[0,1,0,1,0,1]) code=[(0,0,0,0,0,0),(0,1,0,1,0,1),(1,1,1,1,1,1),(1,0,1,0,1,0)] decode(word,code,field) H = make_pcm(code, field) sda = make_SDA(code, field); syndrome=matrix(field, word)*H.transpose() syndrome.set_immutable() e = vector(field,sda[syndrome][0]) m = addl(e, word, field);