CRC16 durch verkürzten CRC32 ersetzen?

[Nils P. (torus)]

Mal 'ne Frage:

Ich hab ein Protocol wo ich zwei Byte Platz für eine Prüfsumme habe. 
Vorgesehen ist eigentlich ein CRC16. Soweit, so einfach.

Allerdings habe ich gute Gründe kein CRC16 einzusetzen. Da wäre 
Beispielsweise die Code Größe, die ein Thema ist also auch die Tatsache, 
das ich auf meiner Platform bereits Hardware Support für CRC32 habe.

Nun dachte ich mir: ich könnte ja statt:

  Checksum16 = CRC16(data)

sowas machen:

  Checksum16 = LSB16(CRC32(data))

oder

  Checksum16 = MSB16(CRC32(data))

oder gar beide Teile von CRC32 verwursten:

  Checksum16 = LSB16(CRC32(data)) ^ MSB16(CRC32(data))


Wie CRC funktioniert habe ich verstanden, und mir ist klar, das ich im 
Prinzip eine einigermaßen brauchbare Prüfsumme zur Fehlererknnung 
bekomme.  Allerdings kann ich nicht abschätzen, wie sehr dieser Hack der 
Fehlererkennung schadet. D.h. wie viel schlechter die Benutzung einer 
verkürzen CRC32 im Vergleich zu CRC16 ist.

Hat da jemand Erfahrung oder einen Tip wie ich mathematisch an das Thema 
heran gehen kann?

[Mike (Gast)]

Mit XOR könntest Du die oberen und unteren 16 Bit zu einer 16 Bit 
Prüfsumme verwursteln, verlierst halt damit enstprechend viel Redunanz, 
aber 16 Bit reichen für die meisten Fälle, (solange die Übertragung im 
Normalfall fehlerfrei läuft)

Handkerum benötigt ein ein Software CRC16-Generator wenig Speicher, Code 
und CPU-Power.

[Nop (Gast)]

Auf den Plattformen, die CRC32-Support in Hardware haben, ist die 
Codegröße kein Thema. Klar, wenn Du mit Lookup-Tabelle über volle Bytes 
herangehst, dann brauchst Du 256 * 2 Bytes, also 512 Bytes. Der Code 
selber ist minimal. Sind 512 Bytes (ROM!) zuviel, kannst Du die 
Lookup-Tabelle aber auch bloß auf Halbbytes machen, dann brauchst Du 16 
* 2 Bytes, also 32 Bytes dafür.

Vorteil, wenn Du das in Software machst: Das kann dann jede Gegenstelle. 
Bei CRC in Hardware hängt es sehr davon ab, was genau denn implementiert 
wurde. Welcher CRC-Initwert, mit Einerkomplement am Ende oder ohne.

[Bernd K. (prof7bit)]

Nils P. schrieb:
> Allerdings habe ich gute Gründe kein CRC16 einzusetzen. Da wäre
> Beispielsweise die Code Größe, die ein Thema ist also auch die Tatsache,
> das ich auf meiner Platform bereits Hardware Support für CRC32 habe.

Für manche CRC16 Polynome gibt es sehr kompakte C-Implementationen, zum 
Beispiel CRC16-CCITT (Kermit):

Geklaut aus den AVR standard libraries:

uint16_t crc16_ccitt_kermit_update(uint16_t crc, char data) {
  data ^= (crc & 0xff);
  data ^= data << 4;
  return ((((uint16_t)data << 8) | (crc >> 8)) ^ (uint8_t)(data >> 4) ^ ((uint16_t)data << 3));
}

wird auf nem Cortex-M0 zu 13 Instruktionen kompiliert:

00000514 <crc16_ccitt_kermit_update>:
 514:  4041        eors  r1, r0
 516:  b249        sxtb  r1, r1
 518:  b2cb        uxtb  r3, r1
 51a:  011b        lsls  r3, r3, #4
 51c:  4059        eors  r1, r3
 51e:  b2c9        uxtb  r1, r1
 520:  020b        lsls  r3, r1, #8
 522:  0a00        lsrs  r0, r0, #8
 524:  4318        orrs  r0, r3
 526:  090b        lsrs  r3, r1, #4
 528:  00c9        lsls  r1, r1, #3
 52a:  4059        eors  r1, r3
 52c:  4048        eors  r0, r1
 52e:  4770        bx  lr

Jetzt subtrahiere zum Vergleich davon das Bitgeschubse das nötig wäre um 
die Hardware CRC zu initialisieren, sie zu bedienen, das Ergebnis auf 16 
Bit zu kürzen und dann bleibt nicht mehr viel Vorteil bzgl 
Flashverbrauch.

Einzig die Laufzeit der Hardware wird kürzer sein. Aber Dir ging es ja 
primär um den Flashverbrauch wenn ich das richtig verstanden habe.

[georg (Gast)]

Nils P. schrieb:
> Allerdings habe ich gute Gründe kein CRC16 einzusetzen

Dann musst du das allerdings auf beiden Seiten implementieren. Wenn 
Kompatibilität kein Problem ist kannst du natürlich machen was du 
willst.

Nils P. schrieb:
> D.h. wie viel schlechter die Benutzung einer
> verkürzen CRC32 im Vergleich zu CRC16 ist.

Bei geeignetem Polynom dürfte es keinen Unterschied geben, aber hast du 
da überhaupt Einfluss drauf?

Bei einer halbwegs brauchbaren Verbindung macht das sowieso nichts aus, 
da würde auch eine einfache Prüfsumme genügen.

Georg

[Nils P. (torus)]

Bernd K. schrieb:
> uint16_t crc16_ccitt_kermit_update(uint16_t crc, char data) {
>   data ^= (crc & 0xff);
>   data ^= data << 4;
>   return ((((uint16_t)data << 8) | (crc >> 8)) ^ (uint8_t)(data >> 4) ^
> ((uint16_t)data << 3));
> }


Danke alle miteinander. Ich wusste gar nicht, das es eine so kompakte 
Implementation gibt. Da gibt es wirklich keine Ausreden mehr.

Gruß,
  Nils