Discussion :

[crimetime]

Bonjour à tous,

Je suis en train de travailler avec une trame de 64 bits :

$ BC 00 00 0E 60 B4 14 01

Je dois vérifier la "validité" de cette trame.

En fait il faut faire un OU-Exclusif de chaque octet avec une valeur contenue dans un tableau de 256 valeurs.

J'aimerai savoir si quelqu'un connaissait une autre méthode que cette dernière.

Merci.

Bonne Journée

[Invité]

Bonjour,
J'ai l'impression que je n'ai pas compris.
Qu'y a-t-il dans ce tableau de 256 valeurs? Des champs de 64 bits ou des octets?
Le ou-exclusif compare qui et quoi?
Si ma mémoire est bonne XOR est identique AND après avoir fait NOT de l'une des deux valeurs.
A XOR B identique à A AND (NOT B)
Bonne journée

[crimetime]

Bonjour,

En fait l'algorithme est basé sur un polynome de 8 bits :

x^8 + x^5 + x^4 + 1

Le constructeur Dallas montre que la résultante peut s'écrire sous la forme d'un tableau de 256 valeurs.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
 unsigned char crc_array[256] = {   
 
 0x00, 0x5e, 0xbc, 0xe2, 0x61, 0x3f, 0xdd, 0x83,    
 0xc2, 0x9c, 0x7e, 0x20, 0xa3, 0xfd, 0x1f, 0x41,    
 0x9d, 0xc3, 0x21, 0x7f, 0xfc, 0xa2, 0x40, 0x1e,    
 0x5f, 0x01, 0xe3, 0xbd, 0x3e, 0x60, 0x82, 0xdc,    
 0x23, 0x7d, 0x9f, 0xc1, 0x42, 0x1c, 0xfe, 0xa0,    
 0xe1, 0xbf, 0x5d, 0x03, 0x80, 0xde, 0x3c, 0x62,    
 0xbe, 0xe0, 0x02, 0x5c, 0xdf, 0x81, 0x63, 0x3d,    
 0x7c, 0x22, 0xc0, 0x9e, 0x1d, 0x43, 0xa1, 0xff,    
 0x46, 0x18, 0xfa, 0xa4, 0x27, 0x79, 0x9b, 0xc5,    
 0x84, 0xda, 0x38, 0x66, 0xe5, 0xbb, 0x59, 0x07,    
 0xdb, 0x85, 0x67, 0x39, 0xba, 0xe4, 0x06, 0x58,    
 0x19, 0x47, 0xa5, 0xfb, 0x78, 0x26, 0xc4, 0x9a,    
 0x65, 0x3b, 0xd9, 0x87, 0x04, 0x5a, 0xb8, 0xe6,    
 0xa7, 0xf9, 0x1b, 0x45, 0xc6, 0x98, 0x7a, 0x24,    
 0xf8, 0xa6, 0x44, 0x1a, 0x99, 0xc7, 0x25, 0x7b,    
 0x3a, 0x64, 0x86, 0xd8, 0x5b, 0x05, 0xe7, 0xb9,    
 0x8c, 0xd2, 0x30, 0x6e, 0xed, 0xb3, 0x51, 0x0f,    
 0x4e, 0x10, 0xf2, 0xac, 0x2f, 0x71, 0x93, 0xcd,    
 0x11, 0x4f, 0xad, 0xf3, 0x70, 0x2e, 0xcc, 0x92,    
 0xd3, 0x8d, 0x6f, 0x31, 0xb2, 0xec, 0x0e, 0x50,    
 0xaf, 0xf1, 0x13, 0x4d, 0xce, 0x90, 0x72, 0x2c,    
 0x6d, 0x33, 0xd1, 0x8f, 0x0c, 0x52, 0xb0, 0xee,    
 0x32, 0x6c, 0x8e, 0xd0, 0x53, 0x0d, 0xef, 0xb1,    
 0xf0, 0xae, 0x4c, 0x12, 0x91, 0xcf, 0x2d, 0x73,    
 0xca, 0x94, 0x76, 0x28, 0xab, 0xf5, 0x17, 0x49,    
 0x08, 0x56, 0xb4, 0xea, 0x69, 0x37, 0xd5, 0x8b,    
 0x57, 0x09, 0xeb, 0xb5, 0x36, 0x68, 0x8a, 0xd4,    
 0x95, 0xcb, 0x29, 0x77, 0xf4, 0xaa, 0x48, 0x16,    
 0xe9, 0xb7, 0x55, 0x0b, 0x88, 0xd6, 0x34, 0x6a,    
 0x2b, 0x75, 0x97, 0xc9, 0x4a, 0x14, 0xf6, 0xa8,    
 0x74, 0x2a, 0xc8, 0x96, 0x15, 0x4b, 0xa9, 0xf7,    
 0xb6, 0xe8, 0x0a, 0x54, 0xd7, 0x89, 0x6b, 0x35,    
 };

CRC = Table [ (Index du code courant CRC) XOR (octet lu dans la clé) ]

par exemple pour debuter on fait :
$01 XOR 00 -> 01

ensuite on prend crc-array[1] -> 5e

puis on utilise le 2nd octet :

$ 5e XOR 14 ->...

etc

Le XOR a pour table de vérité

b a | s
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 0

Je voulais savoir si quelqu'un connaissait une autre méthode que celle ci.

Merci

Bonne journée

[jabbounet]

Il y'a plein d'exemple sur le web qui sont facile à adapter au langage que tu utilise.

la méthode sans tableau consiste pratiquer la division (XOR) du polynôme sur tes données d'entrée et de jouer avec les operateur de manipulation de bits (^, >>, ...)

l'utilisation du tableau est en fait une optimisation, car les résultats pour chaque valeur possible d'un octet sont pré-calculé, il ne reste qu'a récupérer le résultat dans la bonne case et les combiner correctement.


Il existe un tutoriel dessus dans la section tutoriel de ce site
http://dvsoft.developpez.com/Articles/CRC/

il existe aussi un paquet d'exemple disponible sur le net (google -> crc algorithm).

http://en.wikipedia.org/wiki/Cyclic_redundancy_check
http://www3.rad.com/networks/1994/err_con/crc_how.htm
http://www.experts-exchange.com/Prog..._21192644.html

[Jean-Marc.Bourguet]

Si ma mémoire est bonne XOR est identique AND après avoir fait NOT de l'une des deux valeurs.
A XOR B identique à A AND (NOT B)

Ta memoire n'est pas bonne.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
A xor B = (A and not B) or (not A and B)
            = not((A or not B) and (not A or B))