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

[inviteb9c2ac19]

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
-----

[PA5CAL]

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.

[inviteb9c2ac19]

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

[PA5CAL]

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

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.

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).

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 n^ième bit du message à coder et B est le n^ième bit de la séquence pseudo-aléatoire du LFSR, alors C = A xor B est le n^ième bit du message codé.

Coté décodeur, il suffit de refaire un ou-exlusif avec le n^iè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 !

[A voir en vidéo sur Futura]

[inviteb9c2ac19]

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

[invitee89c80ca]

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"?

[PA5CAL]

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.

[invitee89c80ca]

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.

[invitee89c80ca]

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é.

[PA5CAL]

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 ?

[invitee89c80ca]

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)?

[invitee89c80ca]

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?

[PA5CAL]

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

[jiherve]

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

[invité576543]

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,

[invitee89c80ca]

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?

[invitee89c80ca]

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é.

[invité576543]

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,

[invitee89c80ca]

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

[PA5CAL]

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.

[jiherve]

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

[invitee89c80ca]

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;
}

[invité576543]

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...

[invitee89c80ca]

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}

[invité576543]

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,

[invitee89c80ca]

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

Merci a tout de suite

[invitee89c80ca]

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.

[invité576543]

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,