18/3

Forum pour les étudiants de la préparation agreg option C de Grenoble

Modérateur : xcasadmin

parisse
Messages : 5346
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

18/3

Message par parisse » mer. mars 18, 2020 7:55 am

Fin du TP de codes https://www-fourier.univ-grenoble-alpes ... tpcode.pdf
(reference du cours: section 16.5 du manuel Algorithmes de Xcas, accessible depuis le menu Aide>Manuels).

Ecriture de programmes pour un code de Hamming binaire corrigeant une erreur, en utilisant une méthode naive, puis une permutation pour corriger une erreur, ou bien en utilisant une extension de Z/2Z (code polynomial de polynome generateur un polynome irreductible primitif).
J'ai mis en ligne 2 exemples de sessions sur viewforum.php?f=28, si vous séchez, ils peuvent vous inspirer pour écrire un code équivalent pour le code de Hamming binaire n=15, k=11 (sans utiliser d'extension de corps), ou pour un autre code de Hamming binaire (en utilisant une extension de corps).

Vous pouvez poser des questions en repondant a ce sujet ou en creant un nouveau sujet ou par mail.

etuagreg
Messages : 24
Inscription : mar. mars 17, 2020 3:55 pm

Re: 18/3

Message par etuagreg » mer. mars 18, 2020 9:33 am

H1 := [[0,0,0,0,1,1,1,1,1,1,1],[0,1,1,1,0,0,0,1,1,1,1],[1,0,1,1,0,1,1,0,0,1,1],[1,1,0,1,1,0,1,0,1,0,1]]

H:= concat(idn(11),H1)

Voici la matrice que j'obtiens pour le code de Hamming 15,11. Est-ce la bonne matrice ?

Anthony

parisse
Messages : 5346
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: 18/3

Message par parisse » mer. mars 18, 2020 9:40 am

ca a l'air bon: pour verifier j'ai fait la manip suivante
size(eval(convert(tran(concat(H1,idn(4))),set)))
explication: j'ajoute l'identite (pour faire la matrice de controle), puis je convertis en ensemble pour eliminer les occurences doubles, puis je calcule la taille, ca donne 15 on a donc bien tous les entiers de 1 a 15 ecrits en base 2.

Il y a bien sur plusieurs matrices possibles, on peut echanger les colonnes de H1.

etuagreg
Messages : 24
Inscription : mar. mars 17, 2020 3:55 pm

Re: 18/3

Message par etuagreg » mer. mars 18, 2020 9:50 am

Merci, je suis passé à la matrice de décodage du coup. On a un vecteur qui est de taille 15. Si j'ai bien compris on multiplie le vecteur par concat(H1,idn(4)) si cela fait 0 le vecteur est dans l'image sinon on doit changer le bit associé au résultat du produit. La méthode naïve consisterait à parcourir tous les vecteurs de la matrice pour trouver le bon et l'autre méthode serait d'utiliser les permutations ? Si oui je ne sais pas comment on peut modéliser une permutation.

Anthony

parisse
Messages : 5346
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: 18/3

Message par parisse » mer. mars 18, 2020 9:56 am

etuagreg a écrit :
mer. mars 18, 2020 9:50 am
Merci, je suis passé à la matrice de décodage du coup. On a un vecteur qui est de taille 15. Si j'ai bien compris on multiplie le vecteur par concat(H1,idn(4)) si cela fait 0 le vecteur est dans l'image sinon on doit changer le bit associé au résultat du produit.
oui
La méthode naïve consisterait à parcourir tous les vecteurs de la matrice pour trouver le bon et l'autre méthode serait d'utiliser les permutations ? Si oui je ne sais pas comment on peut modéliser une permutation.
La methode naive a laquelle j'avais pense consiste a changer le bit 0 du vecteur recu et a tester si le syndrome est nul, puis le bit 1, etc.
Les permutations dans Xcas sont stockees comme la liste des images de 0 a n-1. On peut alors utiliser les commandes du menu Cmds>Permutation, par exemple perminv qui calcule l'inverse d'une permutation.

parisse
Messages : 5346
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: 18/3

Message par parisse » mer. mars 18, 2020 10:02 am

Un programme pour generer un code de Hamming binaire. On ecrit les entiers de 1 a 2^N-1 qui ne sont pas des puissances de 2 en base 2 en ligne et on transpose.

Code : Tout sélectionner

def genham(n):
    N=logb(n+1,2)
    if type(N)!=integer: return "n doit etre de la forme 2**N-1"
    res=[]
    for j in range(1,n+1):
        # on saute les puissances de 2
        if type(logb(j,2))==integer: 
            continue 
        l=makelist(N)
        l=l+convert(j,base,2)
        res.append(l)
    return tran(res)

etuagreg
Messages : 24
Inscription : mar. mars 17, 2020 3:55 pm

Re: 18/3

Message par etuagreg » mer. mars 18, 2020 10:24 am

J'ai déjà fait ce programme :

Code : Tout sélectionner

def dhamming11_15(w):
    H4:=concat([[0,0,0,0,1,1,1,1,1,1,1],[0,1,1,1,0,0,0,1,1,1,1],[1,0,1,1,0,1,1,0,0,1,1],[1,1,0,1,1,0,1,0,1,0,1]] mod 2,idn(4) mod 2)
    w0:=w*H4 mod 2
    if w0==[0,0,0,0]:
        return(True,w)
    for k in range(15):
        if w0[0]==H4[0][k] :
            if w0[1]==H4[1][k]:
                if w0[2]==H4[2][k] :
                    if w0[3]==H4[3][k]:
                        w[k] = w[k] + 1 mod 2
                        return(w)
mais il ne semble pas fonctionner. Si je fais w1=dhamming11_15(w) puis dhamming11_15(w1) je suis censé tomber sur 0 mais je retombe sur w
Et je pense aussi qu'il est bien trop lourd surtout si n-k est très grand.

Je vais essayer de programmer la méthode par permutation.

Anthony

parisse
Messages : 5346
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: 18/3

Message par parisse » mer. mars 18, 2020 10:31 am

Il faut faire H4*w, pas w*H4 (w est le vecteur ligne recu avec 15 composantes)
Et si on ne trouve pas [0,0,0,0], on fait une boucle pour j de 1 a 15, on cree une copie ww de w, on pose ww[j]=1-ww[j] et on calcule H4*ww, si ca fait [0,0,0,0] c'est bon (i.e. il faut corriger le bit j de w)

Répondre