Pocsag Checksumme berechnen

[Sebastian M. (mccrazy)]

Hallo Leute,
ich versuche gerade einen POCSAG-Encoder selbst zu Programmieren mit 
einem AtMega16.
Leider hänge ich gerade an der Berechnung der Prüfsumme fest. Kann mir 
einer erklären wie das berechnet wird und vor allem wie ich sowas in C 
umsetze?
Ist das Generatorpolynom immer 0x769?

Danke für die Hilfe.

[Stefan W. (dl6dx)]

Hallo Sebastian,

eine Integritätsprüfung mit einem CRC-Verfahren arbeitet einfach erklärt 
so, dass der Sender alle Bytes der Nachricht mit der CRC-Funktion 
verknüpft und den am Ende erhaltenen Wert hinterher sendet.

Der Empfänger berechnet mit der gleichen Funktion über alle erhaltenen 
Bytes (einschließlich des vom Sender errechneten CRC-Ergebnisses). Sind 
die Daten gleich, erhält er einen bestimmten (von der benutzten Funktion 
abhängigen) Wert.

Da die Berechnung (ganz grob gesagt) mit einer Polynomdivision (und noch 
einigem mehr) zu tun hat, spricht man von einem Generatorpolynom.

Das von dir genannte Generatorpolynom 0x769 entspricht übrigens
x^10 + x^9 + x^8 + x^6 + x^5 + x^3 + 1

Der sog. CRC-CCITT (verwendet im HDLC-Protokoll) verwendet 
beispielsweise das Polynom x^15 + x^12 + x^5 + 1. Eine Übersicht über 
weitere verwendete Generatorpolynome hat 
http://de.wikipedia.org/wiki/Zyklische_Redundanzpr%C3%BCfung#Polynome_und_Typen

Und hier noch ein paar Links:

http://www.ross.net/crc/
http://www.ross.net/crc/links.html
http://www.lammertbies.nl/comm/info/crc-calculation.html

Mit dem Codegenerator aus
http://www.tty1.net/pycrc/index_en.html
solltest du auch deine CRC-Funktion generieren können.

Grüße

Stefan

PS: Kennst du eigentlich das: 
http://www.mikrocontroller.net/attachment/69807/GUTE_Beschreibung_POCSAG_eng.pdf 
?

[Sebastian M. (mccrazy)]

Hallo Stefan,

ich werde heute abend den Generator einmal ausprobieren und damit etwas 
spielen. Wenn ich es also richtig verstanden habe dann wird beim Pocsag 
ein eigenen "Algorhytmus" verwendet als Standart-CRC, aber die 
vorgehensweise ist dieselbe?
Das PDF kenne ich und daher habe ich auch schon viele Informationen 
gezogen. ist nur etwas schwer verständlich wie es mit der Berechnung 
läuft.
Bin mal gespannt ob ich es heute abend zum laufen bekomme

Viele Grüße
Sebastian

[Stefan W. (dl6dx)]

Hallo Sebastian,

"das" Standard-CRC-Verfahren gibt es sowieso nicht. Sehr viele Verfahren 
haben ihre eigene Definition.

Folgendes solltest du noch im Hinterkopf haben:

Für die Implementation einer CRC-Prüfung ist nicht nur das 
Generatorpolynom wichtig, sondern ein Verfahren wird beschrieben durch:

- die Länge des CRC-Worts
- das Generatorpolynom
- den Startwert des CRC-Worts
- die Details der Übertragung des CRC-Worts
- das zu erwartende Endergebnis bei der Prüfung

Zum besseren Verständnis mal ohne weiteren Kommentar der Header mit der 
"Gebrauchsanweisung" eines vor Jahren geschriebenen Moduls mit dem 
CCITT-CRC:

/* crcccitt.h 03.09.91 (s.w.) */

/*
CCITT-CRC (Generatorpolynom x^16 + x^12 + x^5 + 1)

Einsatz von crc_ccitt():

Sender:
Der Initialwert des CRC ist CRC_START.
Für jedes Byte der Nachricht wird der CRC weitergerechnet.
Der üüber alle Bytes der Nachricht berechnete CRC wird invertiert
(Einerkomplement!) und in der Reihenfolge low byte, high byte übertragen.

Empfänger:
Der Initialwert von crc ist CRC_START.
Der Empfänger berechnet den CRC über alle empfangenen Zeichen ein-
schliesslich der beiden übertragenen CRC-Bytes, das Ergebnis der
Berechnung muss CRC_OK sein.
*/

#define CRC_START  0xFFFF
#define CRC_OK    0xF0B8

uint16_t crc_ccitt(uint16_t crc, uint8_t datum);

/* eof */

Grüße

Stefan

[Georg G. (df2au)]

Wer wenig Rechenleistung hat, dafür aber Platz im Programmspeicher, 
berechnet den CRC über eine Tabelle.

Das sieht dann in etwa so aus:
unsigned int crc_table[] PROGMEM = {
    0x0000, 0xc0c1, 0xc181, 0x0140, 0xc301, 0x03c0, 0x0280, 0xc241,
    0xc601, 0x06c0, 0x0780, 0xc741, 0x0500, 0xc5c1, 0xc481, 0x0440,
und noch einige Zeilen mehr, 256 Worte insgesamt

void update_crc(unsigned int *crc, unsigned char c) {
  *crc = (*crc >> 8) ^ pgm_read_word(&crc_table[(*crc ^ c) & 0xFF]);

[Stefan W. (dl6dx)]

Hallo Georg,

abhängig vom Generatorpolynom kann die direkte Berechnung manchmal 
trotzdem konkurrenzfähig sein.

Ich hab im Archiv noch einen Artikel von Michael (DC4OX) aus dem Jahr 
1989, der einen schnellen Algorithmus für den CCITT-CRC enthält. Die 
Implementation war selbst auf einem mit nur 4 MHz laufenden 80C32 
absolut "konkurrenzfähig".

Für den, der es gebrauchen kann, hier der Pseudocode:

xor  datum,low(crc)
mov  low(crc),high(crc)
mov  high(crc),datum
mov  high(shifter),datum
mov  low(shifter),0
ror  shifter
xor  low(shifter),datum
ror  shifter
ror  shifter
ror  shifter
and  datum,0fh
xor  high(shifter),datum
ror  shifter
xor  low(shifter),datum
xor  crc,shifter

crc und shifter sind 16bit unsigned, datum 8 bit unsigned
ror rotiert die Bits rechts herum (Rechtsshift, das heraus geschobene 
LSB wandert ins MSB).

Grüße

Stefan

PS: Hab letztlich noch die Disketten mit dem Sourcecode des 
Q/C-Compilers gefunden. Lang ist's her...

[Stefan W. (dl6dx)]

Stefan Wagner schrieb:
> Ich hab im Archiv noch einen Artikel von Michael (DC4OX) aus dem Jahr
> 1989

Angehängt der Artikel. Möglicherweise ist er ja für den einen oder 
anderen hilfreich.

Grüße

Stefan

PS: Der Text wurde 1989 von Michael Röhner (DC4OX) veröffentlicht und 
steht nach meinem Wissen unter der ALAS 
(http://nordlink.dyndns.org/cms/uploads/media/alas-eng.pdf )