stc/exp/python/stc_lght.py*

   1 from random import *
   2 import numpy as np
   3 from math import *
   4
   5 infinity = 10000
   6
   7
   8
   9 # forward part
  10
  11
  12 def dec(ch,n):
  13     l = len(ch)
  14     acc = 0
  15     for i in range(l):
  16         if ch[i]==1:
  17             acc = acc + 2**(n-i-1)
  18     return acc
  19
  20
  21 def bin(elem,n):
  22     """Convertit un nombre en binaire"""
  23     q = -1
  24     res = [0 for i in range(n)]
  25     i = 1
  26     while q != 0:
  27         q = elem // 2
  28         r = elem % 2
  29         res[n-i] =  r
  30         elem = q
  31         i+=1
  32     return res
  33
  34
  35
  36 def xorb(a,b):
  37     return 1 if a != b else 0
  38
  39 def xor(e1,e2,w):
  40     e1b,e2b  = bin(e1,w),bin(e2,w)
  41     d = dec([xorb(e1b[j],e2b[j]) for j in range(w)],w)
  42     return d
  43
  44
  45 def forward(H_hat,x,message):
  46     (h,w) = int(log(max(H_hat),2))+1, len(H_hat)
  47     path = [[0 for _ in range(len(message))] for _ in range(len(x))]
  48     nbblock = len(message)
  49     wght = [infinity for _ in range(int(2**h))]
  50     wght[0]=0
  51     newwght = [0 for _ in range(int(2**h))]
  52     rho = [1 for _ in range(len(x))]
  53     indx,indm = 0,0
  54
  55     for i in range(nbblock): # pour chaque bit du message
  56         for j in range(w):   # pour chaque colonne de H_hat
  57             for k in range(nbblock): # pour chaque ligne de H
  58                 w0 = wght[k] + x[indx]*rho[indx]
  59                 w1 = wght[xor(k,H_hat[j],w)] + (1-x[indx])*rho[indx]
  60                 path[indx][k] = 1 if w1 < w0 else 0
  61                 newwght[k] = min(w0,w1)
  62             indx +=1
  63             wght = [t for t in newwght]
  64
  65         for j in range(int(2**(h-1))):   # pour chaque colonne de H
  66             wght[j] = wght[2*j + message[indm]]
  67         wght = wght[:int(pow(2,h-1))] + [infinity for _ in range(int(pow(2,h)-pow(2,h-1)))]
  68         indm +=1
  69
  70
  71
  72     return path
  73
  74
  75 def backward(H_hat,x,message,path):
  76     (h,w) = int(log(max(H_hat),2))+1, len(H_hat)
  77     state,indx,indm = message[len(message)-1],len(x)-1,len(message)-2
  78     # l'initialisation de state n'est pas optimale...
  79     nbblock = len(message)
  80     y=[0 for _ in range(len(x))]
  81     for i in range(nbblock):
  82         l = range(w)
  83         l.reverse()
  84         for j in l:   # pour chaque colonne de H_hat
  85             y[indx] = path[indx][state]
  86             state = xor(state,y[indx]*H_hat[j],w)
  87             indx -=1
  88
  89         state = 2*state + message[indm]
  90         indm -=1
  91     return y
  92
  93
  94
  95
  96 def stc(x,message):
  97     H_hat = [3,2]
  98     # reflechir a une optimisation du la matrice H_hat
  99     path = forward(H_hat,x,message)
 100     #print path
 101     return backward(H_hat,x,message,path)
 102
 103
 104
 105 x = [randint(0,1) for _ in range(50000)]
 106 message = [randint(0,1) for _ in range(25000)]
 107
 108 print stc(x,message)