Checksummenberechnungsalgorithmen

Computer: Software & Programmierung Programmierung allgemein
#1

Hallo Experten.

Parallel zu meiner Anfrage bezüglich COM-Port-Parametern im Forum „Nostalgie“ nun hier eine Frage zu Checksummenberechnungsalgorithmen.

Kurz der Hintergund: Ich übertrage 14 Byte über den COM-Port. Die Bytes eins bis dreizehn enthalten die Datenlast, das 14. die Checksumme.
Ich berechne die Sache sehr einfach. Die Summe der ersten 13 Bytes, das Ergebnis hat also den Wertebereich 0 bis 3315, Modulo 255, womit sich für die Checksumme der Wertebereich 0 bis 254 ergibt.

Es naht eine Prüfung und mir schwant, daß man mich nach alternativen Checksummenberechnungen fragen wird.
Beim googlen fand ich eine Seite zum CRC-Algorithmus, den ich derzeit zu verstehen versuche *schwitz*.

Ich bin über Namen von einigen Algorithmen (zum gezielteren googlen) ebenso dankbar wie über Literaturhinweise (die sind sehr willkommen).

Weniger ist mehr. Mir reichen 2 oder 3 einfachere Algorithmen!
(KEIN Sourcecode, ich muß -wenn- *nur* alternativen aufzeigen. Also einige Namen fallen lassen und (Prüfungs-GAU) grob beschreiben)

Erklärungen, Beispiele hier bitte nur in der Form, daß man sie ohne Promotion und ohne Mathematikstudium verstehen kann :wink:

TIA, Michael

#2

Moin

Ich bin über Namen von einigen Algorithmen (zum gezielteren
googlen) ebenso dankbar wie über Literaturhinweise (die sind
sehr willkommen).

Weniger ist mehr. Mir reichen 2 oder 3 einfachere Algorithmen!

Such dir passende aus:
http://en.wikipedia.org/wiki/Adler-32
http://en.wikipedia.org/wiki/SHA-1
http://en.wikipedia.org/wiki/MD5

http://en.wikipedia.org/wiki/Fletcher’s_checksum
http://en.wikipedia.org/wiki/Parity_bit
http://en.wikipedia.org/wiki/Luhn_algorithm
http://en.wikipedia.org/wiki/Check_digit

die ersten 3 werden eher bei grossen Datenmengen, die untern 4 eher bei kleinen Datenmenge angewendet.

Erklärungen, Beispiele hier bitte nur in der Form, daß man sie
ohne Promotion und ohne Mathematikstudium verstehen kann :wink:

Für CRC:
http://en.wikipedia.org/wiki/Cyclic_redundancy_check

cu

#3

Moinmoin :wink:

Moin
http://en.wikipedia.org/wiki/Adler-32
http://en.wikipedia.org/wiki/SHA-1
http://en.wikipedia.org/wiki/MD5

http://en.wikipedia.org/wiki/Fletcher’s_checksum
http://en.wikipedia.org/wiki/Parity_bit
http://en.wikipedia.org/wiki/Luhn_algorithm
http://en.wikipedia.org/wiki/Check_digit

die ersten 3 werden eher bei grossen Datenmengen, die untern 4
eher bei kleinen Datenmenge angewendet.

Vielen Dank für die Namen bzw. Links!
Das sollte reichen denke ich :smile:

Liebe Grüße, Michael.

#4

Hallo Michael,

Ich berechne die Sache sehr einfach. Die Summe der ersten 13
Bytes, das Ergebnis hat also den Wertebereich 0 bis 3315,
Modulo 255, womit sich für die Checksumme der Wertebereich 0
bis 254 ergibt.

Weniger ist mehr. Mir reichen 2 oder 3 einfachere Algorithmen!
(KEIN Sourcecode, ich muß -wenn- *nur* alternativen aufzeigen.
Also einige Namen fallen lassen und (Prüfungs-GAU) grob
beschreiben)

Üblich ist es auch die Prüfsumme zuerst mit -1 zu laden. Dann kann man die Prüfsumme noch als 1er oder 2er Komplement übertragen, sind alles Verfahren welche in der Praxis verwendet werden.

Das vorbelegen mit -1 oder die Verwendun des 1er Komplements hat den Sinn eine Fehlerhafte Übertragung, also Leitung z.b. immer auf „0“, von einem echten Datenblock mit 0ern unterscheiden zu können.

Prinzipiell hast du bei einer Prüfsumme das Problem, dass du nicht erkennen kannst, wenn 2 Byte vertauscht werden, bzw. du entsprechende Bitfehler bei der Übertragung hast.
Also 1+2+3 = 3+2+1

Bei der CRC werden die einzelnen Zeichen noch gewichtet. Dies wird im einfachsten Fall einfach durch rotieren der Zwischensumme nach jeder Addition erreicht.
Wenn du jetzt als zwischen summe einen 8-Bit-Wert nimmst gehen dir nur Vertauschungen von Zeichen im Abstand von einem vielfachen von 8 „durch die Latten“.
Eine echte CRC verwendet nun nicht eine einfache rotation der Zwischenwerte, sondern bewerkstelligt noch eine Rückkopplung verschiedener Bits und verknüpft diese dann oft noch mit ExOR mit einem anderen Bit. Somit wird es noch unwahrscheinlich, dass dir Bitfehler „durch die Latten“ gehen.

MfG Peter(TOO)