Condensat d'intégrité indépendant du format physique et du codage ?

Francois Grieu

04/04/2007 à 14:30

Dans l'article <4612d6ea$0$5080$,
"Phil l'ancien" wrote:

Francois Grieu

En fait, un bête OU exclusif, ou une addition modulo 2^40,
c'est un compromis sensé entre efficacité et complexité
dès lors que la transmission de chaque morceau de liste
est faite avec contrôle cryptographique (qui est "orthogonal"
à cette vérification); c'est insensible à l'ordre (mais pas
à la présence de numéros en double), et la probabilité de
ne pas détecter une erreur aléatoire est de 1 sur un million
de million, avec des hypothèses raisonables sur le caractère
aléatoire de chaque élément de liste transmis.

L'addition modulo 2^40 me conviendrait encore mieux
que la valeur de contrôle à base de 2 premiers.
Beaucoup plus simple, et si le risque est effectivement
de 1/2^40, c'est tout à fait correct.

Le risque de non détection ne peut être valablement évalué
sans un modèle des erreurs. Il est facile de démontrer que
l'addition modulo 2^40 d'une liste de nombres de 40 bits:

- détecte toutes les erreurs modifiant un seul des nombres,
donc a fortiori tout erreur affectant un seul bit de
l'expression en binaire de la liste;

- a une chance sur 2^40 de ne pas détecter un changement
aléatoire massif;

- détecte la supression d'un segment de la liste sauf quand
la somme des nombres supprimés est exactement 2^40;
on peut admettre que pour une modification aléatoire,
cette probabilité est de une chance sur 2^40; si l'on
suppose que la moyenne des nombres supprimés est petite,
la probabilité de détection est plutôt meilleure, sauf
si le nombre 0 est autorisé; dans ce cas on peut conseiller
d'ajouter le nombre d'élément de la liste, ce qui revient
à ajouter 1 à chaque nombre, donc à éliminer 0;

- détecte franchement MAL les erreurs affectant 2 bits;
la probabilité que 2 erreurs se compensent est un peu
supérieur à 1/80 dans un modèle où les erreurs changent
2 bits pris au hasard parmis les bits de la liste (modèle
valable pour les erreurs provoquées par les rayons
cosmiques) et un peu supérieure à 1/2 dans un modèle où
les erreurs changent 2 bits au hasard ET de même rang,
ce qui est un modèle plus plausible pour des erreurs
affectant une mémoire quand la cause réelle de l'erreur
l'amplificateur de lecture d'une colonne de la mémoire
(encore que le plus souvent, l'erreur tend à changer
toujours les bits dans le mêem sens, ce qui améliore
un peu la capacité de détection).

En résumé: si l'on vise à détecter une erreur liée au
stockage de la liste dans une mémoire, surtout en binaire,
la somme de contrôle modulo 2^40 est une MAUVAISE méthode;
idem si la supression du nombre 0 est plausible. Face à une
modification "aléatoire", ou à la pluspart des altérations
correspondant à un modèle réaliste et non intentionnel auquel
l'auteur de ces lignes peut penser, cela fonctionne bien.

Dans la catégorie des méthodes fonctionnant bien face à la
pluspart des modèles d'erreur, et très répandues sous de
nombreuses variantes, il y a le CRC sur 32 bits (sous réserve
que la me, mais cela n'est pas "indépendant du codage", et
encore moins associatif (c'est à dire indépendant de l'ordre).

Dans la catégorie indépendant du codage, simple, associatif,
et relativement efficace contre les erreurs suceptibles
d'affecter une mémoire AVEC L'HYPOTHESE QUE LES ERREURS
AFFECTENT TOUS LES BITS DANS LE MEME SENS, il me reste
la somme modulo 2^40-1. Noter que en assembleur, c'est
particulièrement efficace à implémenter (pratiquement aussi
rapide que modulo 2^40), en faisant entrer la retenue de
l'addition du précédent nombre dans l'addition du suivant.
Je crains hélas de ne pas trouver de référence pour cette
technique "addition with carry rollover", ancienne et
inconnue de Google.

J'aurai besoin de pouvoir indiquer le nom de la méthode,
et de documenter un minimum le risque.

Addition modulo 2^40, je ne connais pas d'autre nom.
Pour 8 ou 16 bits, on dit aussi vaguement "checksum",
sans que ce terme précise si l'on parle d'addition ou
de XOR, ni si on transmet le résultat, ou son complément,
ou autre chose.

Pouvez-vous m'indiquer une référence, un article de
wikipedia, ou quelque chose de ce genre ?

Désolé, pas trouvé.

François Grieu

Dans l'article <4612d6ea$0$5080$ba4acef3@news.orange.fr>,
"Phil l'ancien" <nicetry@noway.com> wrote:

Francois Grieu

En fait, un bête OU exclusif, ou une addition modulo 2^40,
c'est un compromis sensé entre efficacité et complexité
dès lors que la transmission de chaque morceau de liste
est faite avec contrôle cryptographique (qui est "orthogonal"
à cette vérification); c'est insensible à l'ordre (mais pas
à la présence de numéros en double), et la probabilité de
ne pas détecter une erreur aléatoire est de 1 sur un million
de million, avec des hypothèses raisonables sur le caractère
aléatoire de chaque élément de liste transmis.

L'addition modulo 2^40 me conviendrait encore mieux
que la valeur de contrôle à base de 2 premiers.
Beaucoup plus simple, et si le risque est effectivement
de 1/2^40, c'est tout à fait correct.

Le risque de non détection ne peut être valablement évalué
sans un modèle des erreurs. Il est facile de démontrer que
l'addition modulo 2^40 d'une liste de nombres de 40 bits:

- détecte toutes les erreurs modifiant un seul des nombres,
donc a fortiori tout erreur affectant un seul bit de
l'expression en binaire de la liste;

- a une chance sur 2^40 de ne pas détecter un changement
aléatoire massif;

- détecte la supression d'un segment de la liste sauf quand
la somme des nombres supprimés est exactement 2^40;
on peut admettre que pour une modification aléatoire,
cette probabilité est de une chance sur 2^40; si l'on
suppose que la moyenne des nombres supprimés est petite,
la probabilité de détection est plutôt meilleure, sauf
si le nombre 0 est autorisé; dans ce cas on peut conseiller
d'ajouter le nombre d'élément de la liste, ce qui revient
à ajouter 1 à chaque nombre, donc à éliminer 0;

- détecte franchement MAL les erreurs affectant 2 bits;
la probabilité que 2 erreurs se compensent est un peu
supérieur à 1/80 dans un modèle où les erreurs changent
2 bits pris au hasard parmis les bits de la liste (modèle
valable pour les erreurs provoquées par les rayons
cosmiques) et un peu supérieure à 1/2 dans un modèle où
les erreurs changent 2 bits au hasard ET de même rang,
ce qui est un modèle plus plausible pour des erreurs
affectant une mémoire quand la cause réelle de l'erreur
l'amplificateur de lecture d'une colonne de la mémoire
(encore que le plus souvent, l'erreur tend à changer
toujours les bits dans le mêem sens, ce qui améliore
un peu la capacité de détection).

En résumé: si l'on vise à détecter une erreur liée au
stockage de la liste dans une mémoire, surtout en binaire,
la somme de contrôle modulo 2^40 est une MAUVAISE méthode;
idem si la supression du nombre 0 est plausible. Face à une
modification "aléatoire", ou à la pluspart des altérations
correspondant à un modèle réaliste et non intentionnel auquel
l'auteur de ces lignes peut penser, cela fonctionne bien.

Dans la catégorie des méthodes fonctionnant bien face à la
pluspart des modèles d'erreur, et très répandues sous de
nombreuses variantes, il y a le CRC sur 32 bits (sous réserve
que la me, mais cela n'est pas "indépendant du codage", et
encore moins associatif (c'est à dire indépendant de l'ordre).

Dans la catégorie indépendant du codage, simple, associatif,
et relativement efficace contre les erreurs suceptibles
d'affecter une mémoire AVEC L'HYPOTHESE QUE LES ERREURS
AFFECTENT TOUS LES BITS DANS LE MEME SENS, il me reste
la somme modulo 2^40-1. Noter que en assembleur, c'est
particulièrement efficace à implémenter (pratiquement aussi
rapide que modulo 2^40), en faisant entrer la retenue de
l'addition du précédent nombre dans l'addition du suivant.
Je crains hélas de ne pas trouver de référence pour cette
technique "addition with carry rollover", ancienne et
inconnue de Google.

J'aurai besoin de pouvoir indiquer le nom de la méthode,
et de documenter un minimum le risque.

Addition modulo 2^40, je ne connais pas d'autre nom.
Pour 8 ou 16 bits, on dit aussi vaguement "checksum",
sans que ce terme précise si l'on parle d'addition ou
de XOR, ni si on transmet le résultat, ou son complément,
ou autre chose.

Pouvez-vous m'indiquer une référence, un article de
wikipedia, ou quelque chose de ce genre ?

Désolé, pas trouvé.

François Grieu

Vous avez filtré cet utilisateur ! Consultez son message

Dans l'article <4612d6ea$0$5080$,
"Phil l'ancien" wrote:

Francois Grieu

En fait, un bête OU exclusif, ou une addition modulo 2^40,
c'est un compromis sensé entre efficacité et complexité
dès lors que la transmission de chaque morceau de liste
est faite avec contrôle cryptographique (qui est "orthogonal"
à cette vérification); c'est insensible à l'ordre (mais pas
à la présence de numéros en double), et la probabilité de
ne pas détecter une erreur aléatoire est de 1 sur un million
de million, avec des hypothèses raisonables sur le caractère
aléatoire de chaque élément de liste transmis.

L'addition modulo 2^40 me conviendrait encore mieux
que la valeur de contrôle à base de 2 premiers.
Beaucoup plus simple, et si le risque est effectivement
de 1/2^40, c'est tout à fait correct.

Le risque de non détection ne peut être valablement évalué
sans un modèle des erreurs. Il est facile de démontrer que
l'addition modulo 2^40 d'une liste de nombres de 40 bits:

- détecte toutes les erreurs modifiant un seul des nombres,
donc a fortiori tout erreur affectant un seul bit de
l'expression en binaire de la liste;

- a une chance sur 2^40 de ne pas détecter un changement
aléatoire massif;

- détecte la supression d'un segment de la liste sauf quand
la somme des nombres supprimés est exactement 2^40;
on peut admettre que pour une modification aléatoire,
cette probabilité est de une chance sur 2^40; si l'on
suppose que la moyenne des nombres supprimés est petite,
la probabilité de détection est plutôt meilleure, sauf
si le nombre 0 est autorisé; dans ce cas on peut conseiller
d'ajouter le nombre d'élément de la liste, ce qui revient
à ajouter 1 à chaque nombre, donc à éliminer 0;

- détecte franchement MAL les erreurs affectant 2 bits;
la probabilité que 2 erreurs se compensent est un peu
supérieur à 1/80 dans un modèle où les erreurs changent
2 bits pris au hasard parmis les bits de la liste (modèle
valable pour les erreurs provoquées par les rayons
cosmiques) et un peu supérieure à 1/2 dans un modèle où
les erreurs changent 2 bits au hasard ET de même rang,
ce qui est un modèle plus plausible pour des erreurs
affectant une mémoire quand la cause réelle de l'erreur
l'amplificateur de lecture d'une colonne de la mémoire
(encore que le plus souvent, l'erreur tend à changer
toujours les bits dans le mêem sens, ce qui améliore
un peu la capacité de détection).

En résumé: si l'on vise à détecter une erreur liée au
stockage de la liste dans une mémoire, surtout en binaire,
la somme de contrôle modulo 2^40 est une MAUVAISE méthode;
idem si la supression du nombre 0 est plausible. Face à une
modification "aléatoire", ou à la pluspart des altérations
correspondant à un modèle réaliste et non intentionnel auquel
l'auteur de ces lignes peut penser, cela fonctionne bien.

Dans la catégorie des méthodes fonctionnant bien face à la
pluspart des modèles d'erreur, et très répandues sous de
nombreuses variantes, il y a le CRC sur 32 bits (sous réserve
que la me, mais cela n'est pas "indépendant du codage", et
encore moins associatif (c'est à dire indépendant de l'ordre).

Dans la catégorie indépendant du codage, simple, associatif,
et relativement efficace contre les erreurs suceptibles
d'affecter une mémoire AVEC L'HYPOTHESE QUE LES ERREURS
AFFECTENT TOUS LES BITS DANS LE MEME SENS, il me reste
la somme modulo 2^40-1. Noter que en assembleur, c'est
particulièrement efficace à implémenter (pratiquement aussi
rapide que modulo 2^40), en faisant entrer la retenue de
l'addition du précédent nombre dans l'addition du suivant.
Je crains hélas de ne pas trouver de référence pour cette
technique "addition with carry rollover", ancienne et
inconnue de Google.

J'aurai besoin de pouvoir indiquer le nom de la méthode,
et de documenter un minimum le risque.

Addition modulo 2^40, je ne connais pas d'autre nom.
Pour 8 ou 16 bits, on dit aussi vaguement "checksum",
sans que ce terme précise si l'on parle d'addition ou
de XOR, ni si on transmet le résultat, ou son complément,
ou autre chose.

Pouvez-vous m'indiquer une référence, un article de
wikipedia, ou quelque chose de ce genre ?

Désolé, pas trouvé.

François Grieu

Arnold McDonald $AMcD$

04/04/2007 à 16:38

Francois Grieu wrote:

Désolé, pas trouvé.

Erf, ça y est tu as été pris en défaut ! Note que ça a pris du temps :p.

--
Arnold McDonald (AMcD)

http://arnold.mcdonald.free.fr/

Francois Grieu

04/04/2007 à 22:07

Correction: la somme modulo 2^40 détecte la supression
d'un segment de la liste sauf quand la somme des nombres
supprimés est exactement DIVISIBLE PAR 2^40

François Grieu

Phil l'ancien

04/04/2007 à 22:23

Arnold McDonald (AMcD)

Francois Grieu

Désolé, pas trouvé.

Erf, ça y est tu as été pris en défaut !
Note que ça a pris du temps :p.

Il me reste un peu de recherche à faire, mais
j'ai ma solution, c'est déjà très bien !

D'ailleurs la somme modulo a aussi un autre
intérêt dans mon application : c'est insensible
à l'utilisation ou non de zéros à gauche dans
les implémentations (problème trivial mais
archi-fréquent).

Merci François Grieu !

Phil l'ancien-

Phil l'ancien

05/04/2007 à 06:53

Francois Grieu

Correction: la somme modulo 2^40 détecte la supression
d'un segment de la liste sauf quand la somme des nombres
supprimés est exactement DIVISIBLE PAR 2^40

On est d'accord.
Encore une dernière remarque : indépendamment
de la difficulté ou facilité de mise en oeuvre, temps
d'exécution, etc., utiliser un nombre premier
plutôt que 2^40 a-t-il un intérêt quelconque ?

Par exemple le plus petit nombre premier P
strictement supérieur à la borne sup. des entiers
de la liste.

Il me semble que ça aurait une fiabilité
démontrablement meilleure que 2^40,
puisque des erreurs de certains modèles
seraient détectées avec P et pourraient ne pas
l'être avec 2^40.

(erreurs d'ajouts ou de soustractions d'un
diviseur de 2^40)

Ca rejoint votre remarque sur l'utilisation
de 2^40-1 (si je reformule ce que vous avez
dit, son avantage provient du fait qu'il n'est
divisible par aucune puissance de 2, et donc meilleur
pour détecter les "bousillages de bits" dans
les implémentations très courantes en binaire).

Un nombre premier (P) semble apporter
le même genre d'avantage que 2^40-1, tout
en ne faisant pas d'hypothèse sur une
implémentation en binaire.

C'est correct ?

Si c'est correct, il me reste à trouver le
plus petit nombre premier supérieur à 2^40...

Phil l'ancien-

Francois Grieu

06/04/2007 à 09:57

Dans l'article <4614801f$0$27366$,
"Phil l'ancien" a écrit:

Encore une dernière remarque : indépendamment
de la difficulté ou facilité de mise en oeuvre, temps
d'exécution, etc., utiliser un nombre premier
plutôt que 2^40 a-t-il un intérêt quelconque ?

Il me semble que ça aurait une fiabilité
démontrablement meilleure que 2^40,
puisque des erreurs de certains modèles
seraient détectées avec P et pourraient ne pas
l'être avec 2^40.

(erreurs d'ajouts ou de soustractions d'un
diviseur de 2^40)

Ca rejoint votre remarque sur l'utilisation
de 2^40-1 (si je reformule ce que vous avez
dit, son avantage provient du fait qu'il n'est
divisible par aucune puissance de 2, et donc meilleur
pour détecter les "bousillages de bits" dans
les implémentations très courantes en binaire).

Oui.
Si on s'intéresse aux "bousillages de bits", utiliser
un nombre impair, de préférence à l'écriture binaire bien
arbitraire, a l'avantage de rendre beaucoup moins probable
que des erreurs de 1 bit affectant tous les bits dans le
même sens ne soient pas détectées. C'est assez satisfaisant
pour se protéger contre une panne d'un amplificateur de
lecture dans une mémoire FLASH ou DRAM, par exemple.
Mais cela améliore relativement peu la probabilité que des
erreurs aléatoires de 1 bit ne soient pas détectées.
Exemple les listes 10,31 et 14,27 qui diffèrent de 2 bits
dans leur expression binaire, sont en collision quel que
soit le module.
C'est une limitation potentiellement sérieuse de toutes
les "checksums" par addition modulo n: une telle checksum
détecte MAL les erreurs causée par les rayons cosmiques
dans de la RAM statique. Les ingénieurs qui étudient la
fiabilité des systèmes le savent (satellites et avions à
haute altitude encaissent beaucoup de rayons cosmiques,
ainsi que dans une moindre mesure les équipements au sol
employés dans l'anomalie magnétique sud-atlantique).

Par exemple le plus petit nombre premier P
strictement supérieur à la borne sup. des entiers
de la liste.

Pourquoi pas; dans votre cas c'est 2^40 + 15. Peut-être
qu'un premier à l'écriture binaire moins remarquable
donnerais une légèrement meilleure protection.

Rappel: v := (v*m)%n avec m j premiers distincts choisis
"arbitrairement" n'est pas associatif (est dépendant de
l'ordre des aj), mais est "démontrablement" sur contre
les erreurs non intentionelles de toutes natures.
Pour le rendre associatif (et indépendant des doublons),
il suffit de commencer par trier les aj en ordre croissant
(et éliminer les doublons). En prime cela facilite la
recherche dans la liste.

François Grieu

Dans l'article <4614801f$0$27366$ba4acef3@news.orange.fr>,
"Phil l'ancien" <nicetry@noway.com> a écrit:

Encore une dernière remarque : indépendamment
de la difficulté ou facilité de mise en oeuvre, temps
d'exécution, etc., utiliser un nombre premier
plutôt que 2^40 a-t-il un intérêt quelconque ?

Il me semble que ça aurait une fiabilité
démontrablement meilleure que 2^40,
puisque des erreurs de certains modèles
seraient détectées avec P et pourraient ne pas
l'être avec 2^40.

(erreurs d'ajouts ou de soustractions d'un
diviseur de 2^40)

Ca rejoint votre remarque sur l'utilisation
de 2^40-1 (si je reformule ce que vous avez
dit, son avantage provient du fait qu'il n'est
divisible par aucune puissance de 2, et donc meilleur
pour détecter les "bousillages de bits" dans
les implémentations très courantes en binaire).

Oui.
Si on s'intéresse aux "bousillages de bits", utiliser
un nombre impair, de préférence à l'écriture binaire bien
arbitraire, a l'avantage de rendre beaucoup moins probable
que des erreurs de 1 bit affectant tous les bits dans le
même sens ne soient pas détectées. C'est assez satisfaisant
pour se protéger contre une panne d'un amplificateur de
lecture dans une mémoire FLASH ou DRAM, par exemple.
Mais cela améliore relativement peu la probabilité que des
erreurs aléatoires de 1 bit ne soient pas détectées.
Exemple les listes 10,31 et 14,27 qui diffèrent de 2 bits
dans leur expression binaire, sont en collision quel que
soit le module.
C'est une limitation potentiellement sérieuse de toutes
les "checksums" par addition modulo n: une telle checksum
détecte MAL les erreurs causée par les rayons cosmiques
dans de la RAM statique. Les ingénieurs qui étudient la
fiabilité des systèmes le savent (satellites et avions à
haute altitude encaissent beaucoup de rayons cosmiques,
ainsi que dans une moindre mesure les équipements au sol
employés dans l'anomalie magnétique sud-atlantique).

Par exemple le plus petit nombre premier P
strictement supérieur à la borne sup. des entiers
de la liste.

Pourquoi pas; dans votre cas c'est 2^40 + 15. Peut-être
qu'un premier à l'écriture binaire moins remarquable
donnerais une légèrement meilleure protection.

Rappel: v := (v*m)%n avec m j premiers distincts choisis
"arbitrairement" n'est pas associatif (est dépendant de
l'ordre des aj), mais est "démontrablement" sur contre
les erreurs non intentionelles de toutes natures.
Pour le rendre associatif (et indépendant des doublons),
il suffit de commencer par trier les aj en ordre croissant
(et éliminer les doublons). En prime cela facilite la
recherche dans la liste.

François Grieu

Vous avez filtré cet utilisateur ! Consultez son message

Dans l'article <4614801f$0$27366$,
"Phil l'ancien" a écrit:

Encore une dernière remarque : indépendamment
de la difficulté ou facilité de mise en oeuvre, temps
d'exécution, etc., utiliser un nombre premier
plutôt que 2^40 a-t-il un intérêt quelconque ?

Il me semble que ça aurait une fiabilité
démontrablement meilleure que 2^40,
puisque des erreurs de certains modèles
seraient détectées avec P et pourraient ne pas
l'être avec 2^40.

(erreurs d'ajouts ou de soustractions d'un
diviseur de 2^40)

Ca rejoint votre remarque sur l'utilisation
de 2^40-1 (si je reformule ce que vous avez
dit, son avantage provient du fait qu'il n'est
divisible par aucune puissance de 2, et donc meilleur
pour détecter les "bousillages de bits" dans
les implémentations très courantes en binaire).

Oui.
Si on s'intéresse aux "bousillages de bits", utiliser
un nombre impair, de préférence à l'écriture binaire bien
arbitraire, a l'avantage de rendre beaucoup moins probable
que des erreurs de 1 bit affectant tous les bits dans le
même sens ne soient pas détectées. C'est assez satisfaisant
pour se protéger contre une panne d'un amplificateur de
lecture dans une mémoire FLASH ou DRAM, par exemple.
Mais cela améliore relativement peu la probabilité que des
erreurs aléatoires de 1 bit ne soient pas détectées.
Exemple les listes 10,31 et 14,27 qui diffèrent de 2 bits
dans leur expression binaire, sont en collision quel que
soit le module.
C'est une limitation potentiellement sérieuse de toutes
les "checksums" par addition modulo n: une telle checksum
détecte MAL les erreurs causée par les rayons cosmiques
dans de la RAM statique. Les ingénieurs qui étudient la
fiabilité des systèmes le savent (satellites et avions à
haute altitude encaissent beaucoup de rayons cosmiques,
ainsi que dans une moindre mesure les équipements au sol
employés dans l'anomalie magnétique sud-atlantique).

Par exemple le plus petit nombre premier P
strictement supérieur à la borne sup. des entiers
de la liste.

Pourquoi pas; dans votre cas c'est 2^40 + 15. Peut-être
qu'un premier à l'écriture binaire moins remarquable
donnerais une légèrement meilleure protection.

Rappel: v := (v*m)%n avec m j premiers distincts choisis
"arbitrairement" n'est pas associatif (est dépendant de
l'ordre des aj), mais est "démontrablement" sur contre
les erreurs non intentionelles de toutes natures.
Pour le rendre associatif (et indépendant des doublons),
il suffit de commencer par trier les aj en ordre croissant
(et éliminer les doublons). En prime cela facilite la
recherche dans la liste.

François Grieu

Francois Grieu

06/04/2007 à 11:54

Dans l'article <4614801f$0$27366$,
"Phil l'ancien" a écrit:

Encore une dernière remarque : indépendamment
de la difficulté ou facilité de mise en oeuvre, temps
d'exécution, etc., utiliser un nombre premier
plutôt que 2^40 a-t-il un intérêt quelconque ?

Il me semble que ça aurait une fiabilité
démontrablement meilleure que 2^40,
puisque des erreurs de certains modèles
seraient détectées avec P et pourraient ne pas
l'être avec 2^40.

(erreurs d'ajouts ou de soustractions d'un
diviseur de 2^40)

Ca rejoint votre remarque sur l'utilisation
de 2^40-1 (si je reformule ce que vous avez
dit, son avantage provient du fait qu'il n'est
divisible par aucune puissance de 2, et donc meilleur
pour détecter les "bousillages de bits" dans
les implémentations très courantes en binaire).

Oui.
Si on s'intéresse aux "bousillages de bits", utiliser
un nombre impair, de préférence à l'écriture binaire bien
arbitraire, a l'avantage de rendre beaucoup moins probable
que des erreurs de 1 bit affectant tous les bits dans le
même sens ne soient pas détectées. C'est assez satisfaisant
pour se protéger contre une panne d'un amplificateur de
lecture dans une mémoire FLASH ou DRAM, par exemple.
Mais cela améliore relativement peu la probabilité que des
erreurs aléatoires de 1 bit ne soient pas détectées.
Exemple les listes 10,31 et 14,27 qui diffèrent de 2 bits
dans leur expression binaire, sont en collision quel que
soit le module.
C'est une limitation potentiellement sérieuse de toutes
les "checksums" par addition modulo n: une telle checksum
détecte MAL les erreurs causée par les rayons cosmiques
dans de la RAM statique. Les ingénieurs qui étudient la
fiabilité des systèmes le savent (satellites et avions à
haute altitude encaissent beaucoup de rayons cosmiques,
ainsi que dans une moindre mesure les équipements au sol
employés dans l'anomalie magnétique sud-atlantique).

Par exemple le plus petit nombre premier P
strictement supérieur à la borne sup. des entiers
de la liste.

Pourquoi pas; dans votre cas c'est 2^40 + 15. Peut-être
qu'un premier à l'écriture binaire moins remarquable
donnerais une légèrement meilleure protection.

Rappel: v := (v*m + aj)%n avec m n premiers distincts
choisis "arbitrairement" n'est pas associatif (est dépendant
de l'ordre des aj), mais est "démontrablement" sur contre
les erreurs non intentionelles de toutes natures.
Pour le rendre associatif (et indépendant des doublons),
il suffit de commencer par trier les aj en ordre croissant
(et éliminer les doublons). En prime cela facilite la
recherche dans la liste.

François Grieu

Dans l'article <4614801f$0$27366$ba4acef3@news.orange.fr>,
"Phil l'ancien" <nicetry@noway.com> a écrit:

Encore une dernière remarque : indépendamment
de la difficulté ou facilité de mise en oeuvre, temps
d'exécution, etc., utiliser un nombre premier
plutôt que 2^40 a-t-il un intérêt quelconque ?

Il me semble que ça aurait une fiabilité
démontrablement meilleure que 2^40,
puisque des erreurs de certains modèles
seraient détectées avec P et pourraient ne pas
l'être avec 2^40.

(erreurs d'ajouts ou de soustractions d'un
diviseur de 2^40)

Ca rejoint votre remarque sur l'utilisation
de 2^40-1 (si je reformule ce que vous avez
dit, son avantage provient du fait qu'il n'est
divisible par aucune puissance de 2, et donc meilleur
pour détecter les "bousillages de bits" dans
les implémentations très courantes en binaire).

Oui.
Si on s'intéresse aux "bousillages de bits", utiliser
un nombre impair, de préférence à l'écriture binaire bien
arbitraire, a l'avantage de rendre beaucoup moins probable
que des erreurs de 1 bit affectant tous les bits dans le
même sens ne soient pas détectées. C'est assez satisfaisant
pour se protéger contre une panne d'un amplificateur de
lecture dans une mémoire FLASH ou DRAM, par exemple.
Mais cela améliore relativement peu la probabilité que des
erreurs aléatoires de 1 bit ne soient pas détectées.
Exemple les listes 10,31 et 14,27 qui diffèrent de 2 bits
dans leur expression binaire, sont en collision quel que
soit le module.
C'est une limitation potentiellement sérieuse de toutes
les "checksums" par addition modulo n: une telle checksum
détecte MAL les erreurs causée par les rayons cosmiques
dans de la RAM statique. Les ingénieurs qui étudient la
fiabilité des systèmes le savent (satellites et avions à
haute altitude encaissent beaucoup de rayons cosmiques,
ainsi que dans une moindre mesure les équipements au sol
employés dans l'anomalie magnétique sud-atlantique).

Par exemple le plus petit nombre premier P
strictement supérieur à la borne sup. des entiers
de la liste.

Pourquoi pas; dans votre cas c'est 2^40 + 15. Peut-être
qu'un premier à l'écriture binaire moins remarquable
donnerais une légèrement meilleure protection.

Rappel: v := (v*m + aj)%n avec m n premiers distincts
choisis "arbitrairement" n'est pas associatif (est dépendant
de l'ordre des aj), mais est "démontrablement" sur contre
les erreurs non intentionelles de toutes natures.
Pour le rendre associatif (et indépendant des doublons),
il suffit de commencer par trier les aj en ordre croissant
(et éliminer les doublons). En prime cela facilite la
recherche dans la liste.

François Grieu

Vous avez filtré cet utilisateur ! Consultez son message

Dans l'article <4614801f$0$27366$,
"Phil l'ancien" a écrit:

Encore une dernière remarque : indépendamment
de la difficulté ou facilité de mise en oeuvre, temps
d'exécution, etc., utiliser un nombre premier
plutôt que 2^40 a-t-il un intérêt quelconque ?

Il me semble que ça aurait une fiabilité
démontrablement meilleure que 2^40,
puisque des erreurs de certains modèles
seraient détectées avec P et pourraient ne pas
l'être avec 2^40.

(erreurs d'ajouts ou de soustractions d'un
diviseur de 2^40)

Ca rejoint votre remarque sur l'utilisation
de 2^40-1 (si je reformule ce que vous avez
dit, son avantage provient du fait qu'il n'est
divisible par aucune puissance de 2, et donc meilleur
pour détecter les "bousillages de bits" dans
les implémentations très courantes en binaire).

Oui.
Si on s'intéresse aux "bousillages de bits", utiliser
un nombre impair, de préférence à l'écriture binaire bien
arbitraire, a l'avantage de rendre beaucoup moins probable
que des erreurs de 1 bit affectant tous les bits dans le
même sens ne soient pas détectées. C'est assez satisfaisant
pour se protéger contre une panne d'un amplificateur de
lecture dans une mémoire FLASH ou DRAM, par exemple.
Mais cela améliore relativement peu la probabilité que des
erreurs aléatoires de 1 bit ne soient pas détectées.
Exemple les listes 10,31 et 14,27 qui diffèrent de 2 bits
dans leur expression binaire, sont en collision quel que
soit le module.
C'est une limitation potentiellement sérieuse de toutes
les "checksums" par addition modulo n: une telle checksum
détecte MAL les erreurs causée par les rayons cosmiques
dans de la RAM statique. Les ingénieurs qui étudient la
fiabilité des systèmes le savent (satellites et avions à
haute altitude encaissent beaucoup de rayons cosmiques,
ainsi que dans une moindre mesure les équipements au sol
employés dans l'anomalie magnétique sud-atlantique).

Par exemple le plus petit nombre premier P
strictement supérieur à la borne sup. des entiers
de la liste.

Pourquoi pas; dans votre cas c'est 2^40 + 15. Peut-être
qu'un premier à l'écriture binaire moins remarquable
donnerais une légèrement meilleure protection.

Rappel: v := (v*m + aj)%n avec m n premiers distincts
choisis "arbitrairement" n'est pas associatif (est dépendant
de l'ordre des aj), mais est "démontrablement" sur contre
les erreurs non intentionelles de toutes natures.
Pour le rendre associatif (et indépendant des doublons),
il suffit de commencer par trier les aj en ordre croissant
(et éliminer les doublons). En prime cela facilite la
recherche dans la liste.

François Grieu

Phil l'ancien

07/04/2007 à 07:08

Francois Grieu

Phil l'ancien

Par exemple le plus petit nombre premier P
strictement supérieur à la borne sup. des entiers
de la liste.

Pourquoi pas; dans votre cas c'est 2^40 + 15. Peut-être
qu'un premier à l'écriture binaire moins remarquable
donnerais une légèrement meilleure protection.

Les contributeurs de fr.sci.maths on donné 2^40 + 15 aussi.

Je vais utiliser un autre nombre premier sans écriture
binaire remarquable (j'ai Pari/gp maintenant ;-).

Rappel: v := (v*m + aj)%n avec m n premiers distincts
choisis "arbitrairement" n'est pas associatif (est dépendant
de l'ordre des aj), mais est "démontrablement" sur contre
les erreurs non intentionelles de toutes natures.
Pour le rendre associatif (et indépendant des doublons),
il suffit de commencer par trier les aj en ordre croissant
(et éliminer les doublons). En prime cela facilite la
recherche dans la liste.

Oui, mais il y a des vieux coucous dans le parc
informatique cible, et le temps de réponse est un
facteur limitant de l'application.
Je préfère éviter d'imposer un tri.

Merci pour tout !

Phil l'ancien-

Condensat d'intégrité indépendant du format physique et du codage ?

8 réponses

Veuillez sélectionner un problème