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

[invite936c567e]

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

[invite936c567e]

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

[invite936c567e]

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

[invite936c567e]

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?