Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- """ La définition de la classe ReedSolomon suit celle écrite précédemment.
- -k est la longueur des messages à encoder, en nombre de bytes (la longueur totale du message est donc k*8 bits)
- -n est la longueur des messages encodés,
- -x est un vecteur de n éléments distincts du corps décrit par BinaryField. Par exemple, avec n=5, x pourrait être ['01010000', '00000011', '10010010', '00000011', '01000100']. Il s'agit donc d'une liste de strings. """
- class ReedSolomon():
- def __init__(self, k, n, x):
- self.f = BinaryField()
- self.k = k
- self.n = n
- self.x = x
- def encoding(self, msg_original):
- """ Encode le message a stocké sous forme d'une liste comportant k bytes. La valeur de retour est
- une liste comportant n bytes.
- Par exemple:
- - k = 3, n = 5, x = ['00000000', '00000001', '00000010', '00000011', '00000100'];
- - a = ['11010000', '10110001', '11100110'];
- la fonction retourne ['11010000', '10000111', '00011100', '01001011', '11000000']
- """
- # à compléter
- return ['00000000'] * self.n
- def _lagrangian_interpolation(self, X, Y):
- """ Retourne les coefficients (ci) de la fonction A(Xi) = c0 + c1*Xi + c2*Xi^2 + c3*Xi^3 partant de 4 points (Xi,A(Xi)).
- Par exemple:
- - X = ['00000000', '00000001', '00000010', '00000011']
- - Y = ['11001100', '01100000', '10100101', '11001111']
- """
- if len(X) != 4 and len(Y) !=4:
- raise ValueError("Il faut exactement 4 points pour l'interpolation Lagrangienne.")
- x0, x1 = self.f.toBinary(0), self.f.toBinary(1)
- Ytild = [x1] * self.k
- out = [x0] * self.k
- for (j, xj, yj) in zip(range(len(X)), X, Y):
- acc = [x1, x0, x0, x1]
- for k, xk in enumerate(X):
- if k != j:
- Ytild[j] = self.f.multiply(Ytild[j], self.f.add(xj, xk))
- acc[2] = self.f.add(acc[2], xk)
- for xl in [X[l] for l in range(k) if l != j]:
- acc[1] = self.f.add(acc[1], self.f.multiply(xl, xk))
- acc[0] = self.f.multiply(acc[0], xk)
- Ytild[j] = self.f.multiply(yj, self.f.inverse(Ytild[j]))
- for i in range(len(out)):
- out[i] = self.f.add(out[i], self.f.multiply(Ytild[j], acc[i]))
- return out
- def decoding(self, msg_corrompu):
- """ Renvoie le message original (uniquement si k=4) qui correspond au message corrompu reçu.
- Dans le message corrompu, au maximum n-4 bytes peuvent être corrompus. Une corruption est le remplacement d'un bit par 'e'.
- Par exemple:
- - Si k=4, n=6;
- - msg_corrompu est de la forme ['11001100', 'e00100e0', '01100000', '10100101', '11e0011e', '11001111']
- """
- if self.k != 4:
- raise ValueError("Le décodage n'est prévu que pour des message de longueur 4.")
- # à compléter
- return ['00000000'] * self.k
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement