Répondre à la discussion
Affichage des résultats 1 à 28 sur 28

Codage et décodage de données avec un linear Feedback shift register



  1. #1
    totoc1001

    Post Codage et décodage de données avec un linear Feedback shift register

    Bonsoir a tous,

    J'ai un petit problème de codage et décodage avec un linear shift register (LFSR).
    Je dois générer et coder un message en morse mais surtout le redécoder par la suite.
    Et j'avoue que je suis assez perdu.

    Ce que je veux envoyer en morse va se traduire par la séquence binaire suivante "249bits quelconques suivi de001010", soit 255 bits au total.
    JE vais envoyer ces données en série sur l'entrée de mon LFSR 8bits.
    Les taps sont 0x8E soit 10001110.
    Celui-ci va me générer une suite aléatoire de caractères.
    Mais voila comment décoder cette suite pour récupérer les données importantes dans ce message de 255bits, a savoir "001010"?

    Avez vous une idée? C'est très important,
    merci beaucoup
    Thomas

    -----


  2. Publicité
  3. #2
    PA5CAL

    Re : Codage et décodage de données avec un linear Feedback shift register

    Bonjour

    Plus précisément, de quelle manière codes-tu ton message ? Pour moi, un LSFR 8 bits est à la base un générateur sans entrée autre que les 8 bits d'initialisation. Il y a deux moyens évidents de coder un messages avec un système faisant appel à ce dispositif:
    1- faire simplement un ou-exclusif du message à coder avec la séquence pseudo-aléatoire sortant du LSFR
    2- "ouvrir" le LSFR, et faire un ou-exclusif entre la sortie du LSFR et le message à coder, pour l'injecter à l'entrée

    Dans les deux cas, la clé du code réside dans l'octet d'initialisation du LSFR et une synchronisation correcte entre l'encodeur et le décodeur.

    Dans le premier cas, la séquence du LSFR est indépendante du message, et le décodage peut se faire selon un accès aléatoire. La séquence étant connue par avance, il est possible de décoder n'importe quel bit sans connaître les autres bits du message (notamment, on peut décoder les bits 001010 de la fin du message d'origine sans connaître les 249 premiers bits). C'est le type de codage qu'on trouve par exemple dans les systèmes GPS.

    Dans le second cas, la séquence du LSFR de l'encodeur est modifiée par le message codé, et le décodage doit se faire séquentiellement. Sauf cas très exceptionnel clairement identifié, on ne peut pas décoder un bit sans connaître les bits du message qui le précèdent.

    En réfléchissant un peu à la manière dont cela fonctionne, la conception du décodeur est évidente. Dans le premier cas, le décodeur est strictement identique à l'encodeur. Dans le second cas, on utilise un LSFR "ouvert", on injecte le message codé à son entrée, et on obtient le message décodé en faisant un ou-exclusif entre l'entrée et la sortie.

  4. #3
    totoc1001

    Re : Codage et décodage de données avec un linear Feedback shift register

    Merci pour ta réponse.
    Pourrais-tu me décrire plus précisément la méthode 1 stp?
    Si j'ai bien compris pour le codage, tu fais un XOR entre ton code de 255bits "a coder" et ton code aléatoire. Ceci devrait te donner "0" en sortie du XOR lorsque le random code et ta séquence sont identiques, "1" dans les autres cas, c'est bien cela?
    A l'initialisation, le LFSR doit etre rempli avec des valeur quelconque?
    Et en ce qui concerne le décodeur, je suis désolé mais je ne vois pas comment cela peut etre identique? JE ne vois pas comment je pourrais récupérer ma séquence "001010" car le code a été randomly modifié.
    Si j'utilise un second LFSR avec les meme tap "0x8E" suivi d'un XOR, je ne comprend pas comment je pourrais obtenir le bon résultat.

    MErci encore pour ton aide, j'espère que tu pourras répondre a toutes mes questions
    Thomas
    "La chance sourit a ceux qui y sont préparés" Pasteur

  5. #4
    PA5CAL

    Re : Codage et décodage de données avec un linear Feedback shift register

    Je joins ci-après les schémas de principe des deux méthodes.

    Citation Envoyé par totoc1001 Voir le message
    Si j'ai bien compris pour le codage, tu fais un XOR entre ton code de 255bits "a coder" et ton code aléatoire. Ceci devrait te donner "0" en sortie du XOR lorsque le random code et ta séquence sont identiques, "1" dans les autres cas, c'est bien cela?
    Oui.

    Citation Envoyé par totoc1001 Voir le message
    A l'initialisation, le LFSR doit etre rempli avec des valeur quelconque?
    Non. D'une part, ce doit être une valeur connue à la fois de l'encodeur et du décodeur, car il s'agit ni plus ni moins de la clé de cryptage. D'autre part, certaines valeurs provoquent le blocage du LFSR (ou éventuellement le rebouclage sur une séquence courte).

    Citation Envoyé par totoc1001 Voir le message
    Et en ce qui concerne le décodeur, je suis désolé mais je ne vois pas comment cela peut etre identique? JE ne vois pas comment je pourrais récupérer ma séquence "001010" car le code a été randomly modifié.
    Si j'utilise un second LFSR avec les meme tap "0x8E" suivi d'un XOR, je ne comprend pas comment je pourrais obtenir le bon résultat.
    La séquence du LFSR de l'encodeur est peut-être aléatoire, mais elle est connue du décodeur, qui se contente de refaire la même.

    Une propriété remarquable du ou-exclusif est que, pour toutes valeurs de A et B, on a (A xor B) xor B = A

    Si A est le nième bit du message à coder et B est le nième bit de la séquence pseudo-aléatoire du LFSR, alors C = A xor B est le nième bit du message codé.

    Coté décodeur, il suffit de refaire un ou-exlusif avec le nième bit de la séquence pseudo-aléatoire du LFSR pour retrouver le message d'origine:
    C xor B = (A xor B) xor B = A

    CQFD !
    Images attachées Images attachées

  6. #5
    totoc1001

    Re : Codage et décodage de données avec un linear Feedback shift register

    Je te remercie beaucoup.
    C'est parfait.

    Je vais essayer d'implémenter ca et ensuite de le coder en verilog.
    Je te tiens au courant quand je l'ai terminé


    Merci
    Thomas
    "La chance sourit a ceux qui y sont préparés" Pasteur

  7. A voir en vidéo sur Futura
  8. #6
    santu

    Re : Codage et décodage de données avec un linear Feedback shift register

    Dans votre réponse vous avez détallé la premiere technique pour décoder les données avec le LFSR, mais pas la deuxiéme.

    Ma question est comment faire pour décoder les données en cas d'un LFSR "ouvert"?

  9. Publicité
  10. #7
    PA5CAL

    Re : Codage et décodage de données avec un linear Feedback shift register

    Citation Envoyé par santu Voir le message
    Ma question est comment faire pour décoder les données en cas d'un LFSR "ouvert"?
    Le deuxième schéma du post #4 indique comment procéder.

    Chaque bit reçu par le décodeur est injecté sur l'entrée du générateur LFSR ouvert.

    Les bits successifs du message décodé sont obtenus en faisant un ou exclusif entre l'entrée et la sortie de ce générateur.

  11. #8
    santu

    Re : Codage et décodage de données avec un linear Feedback shift register

    Et comment on arrive à décoder le message? Le probleme c'est que je ne connait pas la clé d'initialisation du LFSR. Je me demande comment le retrouver.

  12. #9
    santu

    Re : Codage et décodage de données avec un linear Feedback shift register

    En gros j'écris un programme en C qui reçoit un message codé, avec un LFSR ouvert, et décode le le message. Pour le moment je retrouve le LFSR utilisé pour le codage du message mais seulement la suite qu'il génère n'est pas bonne car j'ai pas la bonne clé.

  13. #10
    PA5CAL

    Re : Codage et décodage de données avec un linear Feedback shift register

    Citation Envoyé par santu Voir le message
    la suite qu'il génère n'est pas bonne car j'ai pas la bonne clé.
    C'est un peu le principe du codage, non ?

    Si on pouvait décoder instantanément n'importe quel message sans en connaître la clé, quel serait l'intérêt ?

  14. #11
    santu

    Re : Codage et décodage de données avec un linear Feedback shift register

    En gros la cle il faut la chercher à la main?

    Est-ce quec'est possible de connaître la si je connaît le message codé et le message clair ( le message d'origine)?

  15. #12
    santu

    Re : Codage et décodage de données avec un linear Feedback shift register

    Citation Envoyé par santu Voir le message
    En gros la cle il faut la chercher à la main?

    Est-ce que c'est possible de connaître la cle, si je connais le message codé et le message clair ( le message d'origine)?
    En passant par le LFSR est-ce possible de retrouver la cle avec ces deux messages élements?

  16. Publicité
  17. #13
    PA5CAL

    Re : Codage et décodage de données avec un linear Feedback shift register

    Connaissant une portion suffisamment longue du message codé et du message original, on peut effectivement retrouver la clé.

  18. #14
    jiherve

    Re : Codage et décodage de données avec un linear Feedback shift register

    Bonsoir
    pour abonder dans le sens de Pa5cal se souvenir qu'un LFSR ne génère pas une suite aléatoire mais pseudo aléatoire et périodique.
    Exemple célèbre de décryptage : le codage C+ des début celui était basiquement dérivé d'un LFSR 11bits en plus avec le rebouclage canonique cela n'a résisté longtemps.
    JR

  19. #15
    invité576543
    Invité

    Re : Codage et décodage de données avec un linear Feedback shift register

    Citation Envoyé par PA5CAL Voir le message
    Connaissant une portion suffisamment longue du message codé et du message original, on peut effectivement retrouver la clé.
    Dans le cas précis, la longueur des deux séquences à connaître est celle du registre, soit 8 bits. Mathématiquement, on se retrouve avec 8 équations linéaires (dans Z/2Z) à 8 inconnues, suffit d'appliquer une méthode de résolution algébrique des plus classiques pour calculer les valeurs d'initialisation.

    Cordialement,

  20. #16
    santu

    Re : Codage et décodage de données avec un linear Feedback shift register

    Merci pour votre aide.

    Une autre question : A propos ECC plus précisement le code Reed-Solomon.
    Est-ce possible de retrouver grâce à un message capté le code correcteur qui a été utilisé (dans mon cas le Reed-Solomon)? Si oui comment?

  21. #17
    santu

    Re : Codage et décodage de données avec un linear Feedback shift register

    Merci pour votre aide sur le LFSR.

    Une autre question : A propos d' ECC (Code Correcteur d'Erreur) plus précisement le code Reed-Solomon.
    Est-ce possible de retrouver grâce à un message capté le code correcteur qui a été utilisé (dans mon cas le Reed-Solomon)? Si oui comment?

    En gros le probleme que J'avais c'est que je travaille sur le canal de transmission.
    Le message reçu a été d'abord codé puis corrigé. maintenant il faut retrouver les éléments de communications utilisés en occurrence le LFSR et le code correcteur d'erreur utilisé.

  22. #18
    invité576543
    Invité

    Re : Codage et décodage de données avec un linear Feedback shift register

    Citation Envoyé par santu Voir le message
    Une autre question : A propos ECC plus précisement le code Reed-Solomon.
    Est-ce possible de retrouver grâce à un message capté le code correcteur qui a été utilisé (dans mon cas le Reed-Solomon)? Si oui comment?
    La question n'est pas tant est-ce possible (ça peut l'être!), mais le nombre de mots de code qu'il est nécessaire ou suffisant de connaître pour y arriver.

    Un autre point est ce que l'on connais a priori (taille du symbole, corps de bas, taille de la redondance, etc...).

    Dans les cas simples, la connaissance des caractéristiques de base permet de consulter les listes de codes usuels, il n'y a plus qu'à tester Quand on choisit un code RS, on prend en général ceux qu'on trouve tout faits!

    Dans les cas les plus complexes, le comment demande quelque bagage mathématique, le bagage nécessaire pour comprendre ce qu'est un anneau de polynomes modulo un polynome, et l'algèbre linéaire sur un tel anneau.

    Cordialement,

  23. Publicité
  24. #19
    santu

    Re : Codage et décodage de données avec un linear Feedback shift register

    Bonjour

    Quelqu'un a déjà travaillé avec des Galois_LFSR? Je cherche une suite de bits générée par un LFSR de ce type pour vérifiér mon générateur

  25. #20
    PA5CAL

    Re : Codage et décodage de données avec un linear Feedback shift register

    Citation Envoyé par santu Voir le message
    Quelqu'un a déjà travaillé avec des Galois_LFSR? Je cherche une suite de bits générée par un LFSR de ce type pour vérifiér mon générateur
    Oui. Je pense qu'avec Google, tu peux trouver un générateur tout fait. Il y a plein sur Internet, en langage C, qui fonctionnent à partir de tables précalculées.

  26. #21
    jiherve

    Re : Codage et décodage de données avec un linear Feedback shift register

    Citation Envoyé par santu Voir le message
    Bonjour

    Quelqu'un a déjà travaillé avec des Galois_LFSR? Je cherche une suite de bits générée par un LFSR de ce type pour vérifiér mon générateur
    Bonsoir
    Oui moi comme tout ceux qui ont travaillé dans ce domaine car tout repose sur les travaux d' E Galois!
    JR

  27. #22
    santu

    Re : Codage et décodage de données avec un linear Feedback shift register

    J'ai un code que voici. Mais je ne suis pas sûr car les suites qu'il génère ne correspondent pas à ceux attendu mais la période est bien 2^L - 1.

    unsigned int LFSR::Galois_LFSR(){
    unsigned int ans = this->bits[this->n - 1];
    for(unsigned int i= this->n - 1 ; i >= 1 ; i--){
    if( c[i] == i ){
    this->bits[i] = this->bits[i-1] ^ ans;
    }
    else{
    this->bits[i] = this->bits[i-1];
    }
    }
    this->bits[0] = ans;
    return ans;
    }

  28. #23
    invité576543
    Invité

    Re : Codage et décodage de données avec un linear Feedback shift register

    Je ne lis pas ce langage dans le texte, mais il me semble que les coeffs du polynome sont dans c[i], dont les valeurs ne sont explicitées nulle part dans le code. Or c'est l'information principale!

    Et quand tu dis "ceux attendus", selon quelle méthode détermines-tu "ceux attendus"?

    Cordialement,

    Edit: ce ne serait pas plutôt c[i]==1 le test? c[i]==i, c'est bizarre...

  29. #24
    santu

    Re : Codage et décodage de données avec un linear Feedback shift register

    C : contient les coefficent du polynome de retroaction
    bits : la clé d'initialisation

    unsigned int LFSR::Galois_LFSR(){
    unsigned int ans = this->bits[this->n - 1];
    for(unsigned int i= this->n - 1 ; i >= 1 ; i--){
    if( c[i] == i ){
    this->bits[i] = this->bits[i-1] ^ ans;
    }
    else{
    this->bits[i] = this->bits[i-1];
    }
    }
    this->bits[0] = ans;
    return ans;
    }[/QUOTE]

    Pour tester, j'ai une suite générée par un LFSR du même type (Galois_LFSR) et un polynome de retro-action qui lui correspond. A chaque top d'horloge, j'appelle la fonction Galois_LFSR() qui me retourne un bit(0/1). Celle-ci, doit me générée la suite de départ.

    la ligne C[i]==i permet de placer la contre réaction la où il faut. C[i] contient l'emplacement des contre_reaction.
    Ex : si P(x) = 1 + x + x^3 + x^4 alors si C[]={0,1,3,4}
    Dernière modification par santu ; 16/07/2007 à 17h26.

  30. Publicité
  31. #25
    invité576543
    Invité

    Re : Codage et décodage de données avec un linear Feedback shift register

    Citation Envoyé par santu Voir le message
    C : contient les coefficent du polynome de retroaction
    bits : la clé d'initialisation
    J'avais compris cela, ça ne change rien aux remarques.

    T'es vraiment sûr de ton test c[i]==i

    la ligne C[i]==i permet de placer la contre réaction la où il faut. C[i] contient l'emplacement des contre_reaction.
    Ex : si P(x) = 1 + x + x^3 + x^4 alors si C[]={0,1,3,4}
    Je ne comprend pas. Ce serait un test c[j]==i, avec une boucle sur j, pas c[i]==i

    Cordialement,

  32. #26
    santu

    Re : Codage et décodage de données avec un linear Feedback shift register

    D'acoord je vais faire une modif de la ligne C[i]==i

    Merci a tout de suite

  33. #27
    santu

    Re : Codage et décodage de données avec un linear Feedback shift register

    Citation Envoyé par santu Voir le message
    C : contient les coefficent du polynome de retroaction
    bits : la clé d'initialisation

    unsigned int LFSR::Galois_LFSR(){
    unsigned int ans = this->bits[this->n - 1];
    for(unsigned int i= this->n - 1 ; i >= 1 ; i--){
    if( c[i] == i ){
    this->bits[i] = this->bits[i-1] ^ ans;
    }
    else{
    this->bits[i] = this->bits[i-1];
    }
    }
    this->bits[0] = ans;
    return ans;
    }
    la ligne C[i]==i permet de placer la contre réaction la où il faut. C[i] contient l'emplacement des contre_reaction.
    Ex : si P(x) = 1 + x + x^3 + x^4 alors si C[]={0,1,0,3,4}[/QUOTE]

    Avec la boucle for je parcours simultanément deux tabeaux C[] et bits[] qui ont la même taille. Sachant que bits représente le registre. Donc a chaque fois que C[i]== i, je pourrais mettre dans bits[i] le résultat de la contre réaction du bits[i-1] et du denier pour réaliser la contre reaction.

    Je ne sais pas si ça vous semble correcte.

  34. #28
    invité576543
    Invité

    Re : Codage et décodage de données avec un linear Feedback shift register

    Citation Envoyé par santu Voir le message
    Je ne sais pas si ça vous semble correct.
    Je crois avoir fait comprendre que cela ne me semblait pas correct. Mais ce n'est qu'une opinion...

    Cordialement,

Sur le même thème :

Discussions similaires

  1. codage/decodage
    Par tech53 dans le forum Électronique
    Réponses: 3
    Dernier message: 24/11/2007, 23h11
  2. Shift Light avec LM358
    Par laurent77380 dans le forum Électronique
    Réponses: 1
    Dernier message: 10/10/2007, 20h18
  3. Problème de codage avec Word
    Par kingax dans le forum Logiciel - Software - Open Source
    Réponses: 2
    Dernier message: 27/08/2007, 14h16
  4. Gel Shift : problème avec la compétition
    Par kloklo2 dans le forum Biologie
    Réponses: 4
    Dernier message: 01/02/2007, 01h08