Addition dans corps fini (F256) contexte des codes correcteu

[tist]

Bonjour,

En m'intéressant aux codes correcteurs je suis tombé sur cette page qui m'intrigue au niveau du calcul:

http://www.swetake.com/qr/qr3_en.html

j'essaie de faire la synthèse du contexte: Pour les codes correcteurs, je "connais" un peu le principe en binaire, on code avec des 0 et des 1, donc sur F2, on envoie un message sous forme d'un polynôme de F2[X] et avec une division euclidienne on envoie une sécurité pour réparer les erreurs. ok

dans cette page, on code semble-t-il dans F256, j'imagine que l'avantage est qu'une information est beaucoup plus riche, mais a un moment ils font une division euclidienne aussi, et je ne comprends pas comment on peut faire car on ne sait pas bien additionner dans F256.

Dans le site, ils donnent une table de conversion entre la représentation entière des éléments de F256 et la représentation comme puissance de a ou a est un générateur de F256* mais je ne vois pas à quoi ça sert (et est-ce possible d'ailleurs?) car dans les calculs (à un moment ils calculent une somme, "somme exclusive de polynômes") il semble que par exemple 65+70 ne fasse pas 135 mais 7, que 205+168 (cad 205-168 sauf autre erreur de ma part) ne fasse pas 37 mais 101...

Je me pose par ailleurs plusieurs questions:
- sait-on additionner facilement dans F256?
- dans les calculs dans F256 est-ce que la structure de F2 espace vectoriel sert?
- par exemple 32 + 32 =0 car c'est 2 fois 32 mais comment calculer 32+33 par exemple?

et une question de curiosité: pourquoi utiliser un corps de type F 2^n et non pas un corps Fp avec p grand, dans lequel on sait beaucoup mieux additionner?

J'espère que vous aurez compris ce que je veux dire et que mes questions ont bien un sens et merci si vous pouvez m'aider!

[Skullkid]

Salut, en fait ils jonglent entre trois façons de représenter .

La première est la représentation "en octets", c'est-à-dire que les éléments de sont écrits sous la forme d'une suite de 8 bits (ou d'un élément de pour parler matheux). Sous cette forme, l'addition est immédiate : c'est le ou exclusif bit à bit. Ainsi, 01001001 + 01100111 = 00101110 par exemple. Cette forme n'est pas adaptée pour faire la multiplication.

La deuxième est la représentation "en entiers", c'est-à-dire que les éléments de sont représentés comme les entiers de 0 à 255. Sous cette forme, ni l'addition, ni la multiplication ne sont immédiates. En revanche, on peut facilement passer de cette forme à la forme en octets et vice versa : c'est la représentation binaire des entiers de 0 à 255. Par exemple 65 est égal à 01000001 et 70 est égal à 01000110. Ainsi, le résultat de l'addition 65+70 c'est 00000111, c'est-à-dire 7.

La troisième est la représentation "cyclique", où avec . Sous cette forme, c'est la multiplication qui est facile mais pas l'addition (par exemple ). Pour passer de cette forme à la forme avec des entiers et vice versa, il faut utiliser les tables qui sont fournies.

Pour résumer : pour faire l'addition (qui est égale à la soustraction, comme tu l'as remarqué), il faut utiliser la représentation en octets (qui est la représentation de en tant que -espace vectoriel) et pour faire la multiplication, il faut utiliser la représentation cyclique. La représentation avec des entiers sert surtout à faire le lien entre les deux (et elle permet aussi de rendre la représentation en octets plus lisible pour un humain, c'est pour ça qu'ils l'utilisent comme représentation principale).

Comme tu l'as dit, 32 + 32 = 0 (de manière générale x + x = 0 pour tout x de ), mais attention : . Comme tu as pris un entier relativement petit (32), le résultat de la multiplication semble encore naturel dans la représentation avec les entiers, mais par exemple . Quant à 32 + 33, ça fait 1.

Pour ce qui est de l'utilisation de au lieu de, par exemple, , c'est parce que les opérations sont plus faciles à faire dans le premier que dans le second pour un ordinateur (même si c'est le contraire pour un humain).

[tist]

Merci pour ta réponse super claire et super complète c'est parfait!

Salut, en fait ils jonglent entre trois façons de représenter .

La première est la représentation "en octets", c'est-à-dire que les éléments de sont écrits sous la forme d'une suite de 8 bits (ou d'un élément de pour parler matheux). Sous cette forme, l'addition est immédiate : c'est le ou exclusif bit à bit. Ainsi, 01001001 + 01100111 = 00101110 par exemple. Cette forme n'est pas adaptée pour faire la multiplication.

La deuxième est la représentation "en entiers", c'est-à-dire que les éléments de sont représentés comme les entiers de 0 à 255. Sous cette forme, ni l'addition, ni la multiplication ne sont immédiates. En revanche, on peut facilement passer de cette forme à la forme en octets et vice versa : c'est la représentation binaire des entiers de 0 à 255. Par exemple 65 est égal à 01000001 et 70 est égal à 01000110. Ainsi, le résultat de l'addition 65+70 c'est 00000111, c'est-à-dire 7.

La troisième est la représentation "cyclique", où avec . Sous cette forme, c'est la multiplication qui est facile mais pas l'addition (par exemple ). Pour passer de cette forme à la forme avec des entiers et vice versa, il faut utiliser les tables qui sont fournies.

Pour résumer : pour faire l'addition (qui est égale à la soustraction, comme tu l'as remarqué), il faut utiliser la représentation en octets (qui est la représentation de en tant que -espace vectoriel) et pour faire la multiplication, il faut utiliser la représentation cyclique. La représentation avec des entiers sert surtout à faire le lien entre les deux (et elle permet aussi de rendre la représentation en octets plus lisible pour un humain, c'est pour ça qu'ils l'utilisent comme représentation principale).

Comme tu l'as dit, 32 + 32 = 0 (de manière générale x + x = 0 pour tout x de ), mais attention : . Comme tu as pris un entier relativement petit (32), le résultat de la multiplication semble encore naturel dans la représentation avec les entiers, mais par exemple . Quant à 32 + 33, ça fait 1.

Pour ce qui est de l'utilisation de au lieu de, par exemple, , c'est parce que les opérations sont plus faciles à faire dans le premier que dans le second pour un ordinateur (même si c'est le contraire pour un humain).

[geegee]

Salut, en fait ils jonglent entre trois façons de représenter .

La première est la représentation "en octets", c'est-à-dire que les éléments de sont écrits sous la forme d'une suite de 8 bits (ou d'un élément de pour parler matheux). Sous cette forme, l'addition est immédiate : c'est le ou exclusif bit à bit. Ainsi, 01001001 + 01100111 = 00101110 par exemple. Cette forme n'est pas adaptée pour faire la multiplication.

La deuxième est la représentation "en entiers", c'est-à-dire que les éléments de sont représentés comme les entiers de 0 à 255. Sous cette forme, ni l'addition, ni la multiplication ne sont immédiates. En revanche, on peut facilement passer de cette forme à la forme en octets et vice versa : c'est la représentation binaire des entiers de 0 à 255. Par exemple 65 est égal à 01000001 et 70 est égal à 01000110. Ainsi, le résultat de l'addition 65+70 c'est 00000111, c'est-à-dire 7.

La troisième est la représentation "cyclique", où avec . Sous cette forme, c'est la multiplication qui est facile mais pas l'addition (par exemple ). Pour passer de cette forme à la forme avec des entiers et vice versa, il faut utiliser les tables qui sont fournies.

Pour résumer : pour faire l'addition (qui est égale à la soustraction, comme tu l'as remarqué), il faut utiliser la représentation en octets (qui est la représentation de en tant que -espace vectoriel) et pour faire la multiplication, il faut utiliser la représentation cyclique. La représentation avec des entiers sert surtout à faire le lien entre les deux (et elle permet aussi de rendre la représentation en octets plus lisible pour un humain, c'est pour ça qu'ils l'utilisent comme représentation principale).

Comme tu l'as dit, 32 + 32 = 0 (de manière générale x + x = 0 pour tout x de ), mais attention : . Comme tu as pris un entier relativement petit (32), le résultat de la multiplication semble encore naturel dans la représentation avec les entiers, mais par exemple . Quant à 32 + 33, ça fait 1.

Pour ce qui est de l'utilisation de au lieu de, par exemple, , c'est parce que les opérations sont plus faciles à faire dans le premier que dans le second pour un ordinateur (même si c'est le contraire pour un humain).

Bonjour,

Le produit se transforme en somme
somme= ou exclusif

[Skullkid]

Bonjour,

Le produit se transforme en somme
somme= ou exclusif

Tu me montres comment calculer 2*200 en ne faisant que des ou exclusif ?