Kategória: Python

Zmenené: 5. január 2017

CRC binárnych dát

Vysokoúrovňové moduly bezdrôtovej komunikácie zvyknú mať zabudovanú kontrolu chýb (RFM69 s opakovaním a HC-11 bez opakovania prenosu). I tak som sa rozhodol skúsiť aplikovať jednoduchú kontrolu chýb, a to pomocou kontrolného súčtu CRC-16.

Kontrolný súčet

CRC (Cyclic Redundancy Ceck) je kód na zistenie chýb prenosu, ktorý sa vyznačuje jednoduchosťou a nenáročnosťou. Princíp je prostý – pri odoslaní vypočíta odosielajúca CRC, pripojí ho k správe a na strane prijímateľa je z prijatej správy (samozrejme bez CRC) rovnakým algoritmom vyrátaný kontrolný súčet, ktorý je potom porovnaný s CRC pripojeným k správe. Ak sú oba kontrolné súčty rovnaké, možno správu považovať za prenesenú bez chýb. V opačnom prípade nastala pri prenose chyba a prijaté dáta nemožno považovať za správne.

Princípom výpočtu CRC sa zaoberať nebudem, no spomeniem, že nie je CRC ako CRC. Existuje viacero implementácií výpočtu CRC, ktoré sa líšia najmä šírkou polynómu (zvyčajne násobky 8 – CRC-8, CRC-16, CRC-32), použitým polynómom a počiatočnou hodnotou, preto je dôležité na oboch koncoch komunikácie použiť rovnakú implementáciu, v opačnom prípade nikdy nedostanete rovnakú hodnotu nepoškodenej správy.

Pri výbere algoritmu treba vychádzať z dostupných algoritmov. Pre AVR existuje implementácia v avr-libc (util/crc16.h), kde je viacero implementácií 8- a 16-b CRC. Na šírke CRC a použitom polynóme závisí koľko zmenených bitov v správe dokáže identifikovať. Keď to celkom zjednoduším tak CRC-8 je vhodné na správy dĺžky niekoľko málo bajtov s nízkou pravdepodobnosťou chyby (teda nie na bezdrôtový prenos), a tak ostáva CRC-16, ktoré má v avr-libc viac implementácií:

  • _crc16_update() – polynóm 0xa001, poč. hodnota 0xffff
  • _crc_xmodem_update() – polynóm 0x1021, poč. hodnota 0x0
  • _crc_ccitt_update() – polynóm 0x8408, poč. hodnota 0xffff

Vybrať vhodnú implementáciu z týchto už prekračuje moje znalosti o CRC, tak som na ďalšie pokusy zvolil _crc16_update() v nádeji, že to bude stačiť. Čas ukáže…

Tip

Po napísaní tohoto článku som niekoľko testov, mnou použitý algoritmus CRC-8 poskytuje 100% kontrolu chýb len na správu dĺžky 1 bajt, pri 2 B zlyhá pri zmene štyroch bitov a potom pri 16 B správe zlyhá už pri zmene dvoch bitov. Pri CRC-16 je 100% kontrola do 2 bajtov a potom tiež zlyhá už pri zmene štyroch bitov.

Takou zaujímavosťou je, že oba algoritmy zlyhávajú pri párnom počte zmenených bitov (2, 4, 6, atď), ale hlavne, počet rovnakých CRC pri zmenených bitoch nepresahuje 0,1 % všetkých možností, tzn. nie každá zmena napr. štyroch bitov nutne spôsobí falošné overenie, a tak na moje potreby plne postačí aj CRC-8 (pri správach < 16 B).

Výpočet CRC

Začnem výpočtom CRC v AVR (Arduino), pretože aby som mohol CRC porovnať, musím ho najprv vyrátať pekne bajt po bajte, takže tu sa mi zišli moje experimenty s posielaním binárnych dát (Binárne dáta cez UART), kde som implementoval šablónu na posielanie ľubovoľnej štruktúry po sériovej linke v Arduino. Avšak, tento experiment nemožno implementovať priamo, ale je potrebné štruktúrou prechádzať po jednotlivých bajtoch a každý tento bajt poslať funkcii na výpočet CRC (a zároveň ho aj posielam). Nakoniec, samozrejme, treba vypočítané CRC k správe pripojiť.

Použil som teda princíp šablóny z predošlého experimentu, kde som však musel pridať prechádzanie štruktúrou po bajtoch:

#include <util/crc16.h>

template <typename T> void sendCRC (const T data)
{
    uint16_t crc;
    uint8_t size;
    uint8_t *addr;

    addr = (uint8_t *)&data;
    crc  = 0xffff;
    size = sizeof(data);

    while (size--)
    {
        // calculate CRC
        crc = _crc16_update(crc, *addr);
        // send struct's byte
        Serial.write(*addr);
        addr++;
    }

    // send CRC
    Serial.write(crc);
    Serial.write(crc>>8);
}

Použitie funkcie je prosté. Na začiatku treba deklarovať typ štruktúry a naplniť ju nejakými dátami (zase sa mi osvedčili konkrétne hodnoty, na prosté porovnanie v prijímacej časti):

typedef struct __attribute__ ((packed))
{
    int8_t   prva;    // 1 B
    int16_t  druha;   // 2 B
    uint8_t  tretia;  // 1 B
    uint16_t stvrta;  // 2 B
    float    piata;   // 4 B
} TMyStruct;

TMyStruct mystruct;

// add some values
mystruct.prva = -21;
mystruct.druha = 11999;
mystruct.tretia = 255;
mystruct.stvrta = 31888;
mystruct.piata = 27.35456;

Potom už stačí odoslať dĺžku a odovzdať samotnú štruktúru funkcii:

// send message length
Serial.write(sizeof(mystruct));
// send message with CRC
sendCRC(mystruct);

Teraz už to vyzerá jednoducho, ale priznám sa, že pri implementácii prechádzania bajtmi štruktúry som sa poriadne zapotil. V ukazovateľoch a nepriamom adresovaní som sa strácal už v dobe Turbo Pascalu, ale nakoniec som na to prišiel – chybu som robil v priradení adresy štruktúry do premennej, kde si to vyžiadalo explicitné pretypovanie a zrazu to všetko začalo fungovať.

Kontrola CRC

Naďalej používam na prijímanie Python a jeho modul struct (viď Binárne dáta cez UART). Na prácu s CRC-16 som použil modul crcmod, s ktorým je práca naozaj prostá – najprv treba inicializovať ten správy algoritmus CRC:

import crcmod

crc16 = crcmod.predefined.Crc("crc-16")
# init CRC
crc16.crcValue = 0xffff

Pretože používam preddefinovaný algoritmus, musím len nastaviť rovnakú východziu hodnotou (0xffff) rovnakú ako v AVR. Práca v Pythone je jednoduchšia o to, že netreba prechádzať prijatú správu bajt po bajte, ale možno ju funkcii poslať celú naraz (ako pole bajtov – bytes) a na konci už len stačí výsledné CRC porovnať s hodnotou CRC pripojenou na koniec správy. Celé to potom vyzerá takto:

import serial
from struct import unpack
import crcmod

SERPORT = "/dev/ttyACM0"
crc16 = crcmod.predefined.Crc("crc-16")

# init CRC
crc16.crcValue = 0xffff

with serial.Serial(SERPORT, baudrate=9600) as ser:
    // read message length
    length = ser.read(1)

    // read message with given length
    ser.timeout = 1
    packet = ser.read(length[0])

    // calculate CRC of message
    crc16.update(packet)

    // read CRC
    crc = ser.read(2)

    // compare CRC and show result
    if unpack("<H", crc)[0] == crc16.crcValue:
        print ("CRC OK")
        print ( unpack("<bhBHf", packet) )
    else:
        print ("CRC Failed")

Samozrejme, nie je to žiadny kompletný program, čisto len ukážka ako zo sériového rozhrania prečítať správu, vypočítať CRC a porovnať výsledok.

Záver

Chvíľu som uvažoval nad tým, či do výpočtu CRC zahrnúť aj posielanú dĺžku správy. Prvá myšlienka bola, že áno, pretože teraz neviem, či je prijatá dĺžka správna. Avšak, čo sa stane ak nastane chyba prenosu dĺžky? Jednoducho program, tak ako je teraz napísaný, prečíta iný počet bajtov správy a nakoniec i inú hodnotu CRC (pretože bude na inom mieste), a tak výsledná kontrola musí (s vysokou pravdepodobnosťou) i tak zlyhať. Inými slovami, i keď bajt s dĺžkou správy nie je súčasťou CRC, nebude to mať významný vplyv na kontrolu správnosti, pretože chyba sa i tak prejaví a ušetrím tým pár desiatok mikrosekúnd času procesora.

Aj tentokrát som so sebou i výsledkom spokojný. Podarilo sa mi zvíťaziť nad konverziou štruktúry na (skoro) pole bajtov v C++, zvládol som výpočet CRC i jeho porovnanie. Menej spokojný som s tým, že vlastne netuším, aká je pravdepodobnosť, že kontrola CRC je naozaj správna – ako som spomínal, závisí to nie len od šírky CRC, ale aj od voľby polynómu (tu 0xa001) a počiatočnej hodnote. Možno skúsim nejaké experimenty i s cielenou zmenu prijatej správy.