HDLC

HDLC (Highlevel Data Link Control) on bittisynkroninen datasiirtomenettely, jolla lähetetään dataa kehyksinä - "paketteina".

Toisin kuin tavallisimpien asynkronisten sarjaporttien tapauksessa, tässä tarvitaan dataa saattamaan myös siirtokello joka saadaan modeemilta joko suoraan, tai se voidaan joissain tapauksissa regeneroida epäsuoralla tekniikalla.

HDLC on kansainvälisen standardistatuksen (ISO 3309) saanut versio IBM:n SDLC:stä (Synchronous Data Link Control), jossa yhden bitin merkitys käännettiin päinvastaiseksi.

HDLC:n bittivirralla on kyky kehystää hyötydataa siten, että datan sisältö voi olla mielivaltaista, eikä itse datan tarvitse alkaa tietyllä merkkisarjalla (joita käytetään ns. byte-synkronisten siirtoprotokollien tapauksessa.) HDLC saavuttaa tämän kyvyn siten, että se ei koskaan lähetä enempää kuin 5 perättäistä ykkösbittiä datassaan. Ainoana poikkeuksena on kehyksien reunamerkit (FLAG), jotka ovat bittikuvioita: 01111110 eli niissä on 6 perättäistä ykkösbittiä.

Jos lähetettävässä datassa on enemmän kuin 5 perättäistä ykkösbittiä, lähetetään ensin 5 bittiä ja sitten lisätään väliin yksi nollabitti. Vastaanotossa nämä lisätyt (bit stuffed) nollabitit otetaan pois.

Jos linkillä ei kulje dataa, siellä lähetetään perättäisiä kehysten reunamerkkejä.

HDLC kehyksen alussa on aina Address ja Control tavuja, joille on esim. AX.25 protokollassa annettu omat merkityksensä. Kehyksen lopussa on 2 tavuinen CRC-16 tarkistussumma ennen seuraavaa reunamerkkiä.

HDLC:ssä lähetetään kaikki kehyksen sisäiset tavut alkaen alimmasta bitistään (0), poikkeuksena kuitenkin 16 bitin tarkistussumma joka lähetetään ylin bitti (15) edellä.

16-bit CRC-CCITT tarkistussumma

Kyseessä on syklinen polynomi: $P(x)=x^{16}+x^{12}+x^{5}+1$ jonka kerroin voidaan esittää heksakoodina: 0x11021. Tavallisesti se kuitenkin esitetään ilman ylintä bittiään: 0x1021 ja tuo ylin bitti syntyy laskentaimplementaatiosta.

Asiasta viitataan AX.25 protokollamäärityksessä:

http://www.tapr.org/pub_ax25.html

että kyseessä on HDLC:n tarkistussumma:

http://en.wikipedia.org/wiki/High-Level_Data_Link_Control

joka viittaa artikkeliin:

http://en.wikipedia.org/wiki/Cyclic_redundancy_check

Menetelmän ominaisuus on, että tarkistus voidaan tehdä syöttämällä data ja vastaanotettu CRC arvo laskentaan ja lopputuloksena syntyvän uuden tarkistussumman pitää olla nolla.

Mikropiiri joka implementoi useita CRC algoritmeja, myös tämän 16-bit CRC-CCITT:n:

http://www.datasheetcatalog.com/datasheets_pdf/7/4/F/4/74F401.shtml

datalehdestä näkee kytkennän jolla nämä tehdään sisäisesti sarjamuodossa ja miten sieltä otetaan tulos ulos — ja miksi speksi sanoo "otetaan ylin bitti edellä ulos."

N1VG kirjoittaa omista kokemuksistaan:

Frame Check Sequence

One detail of the AX.25 format that deserves attention is the Frame Check Sequence (FCS) checksum. This is a two-byte checksum added to the end of every frame. It's generated using the CRC-CCITT polynomial, and is sent low-byte first.

The CRC-CCITT algorithm has plenty of published code examples, but the one I needed, and had trouble finding, was the algorithm for calculating the FCS one bit at a time, rather than a byte at a time. That algorithm is as follows:

Start with the 16-bit FCS set to 0xffff. For each data bit sent, shift the FCS value right one bit. If the bit that was shifted off (formerly bit 1) was not equal to the bit being sent, exclusive-OR the FCS value with 0x8408. After the last data bit, take the ones complement (inverse) of the FCS value and send it low-byte first.

Jos N1VG:n algoritmi vaikuttaa jotenkin kummalta, syynä on se, että hän on kääntänyt laskentapolynomin implementaation peilikuvaksi jotta kahden tavun puskuriin kertynyt summa voidaan lähettää samalla koodilla ulos, kuin varsinainen pakettisisältökin — alin bitti edellä. Hän myös laskee tavun bittejä alkaen ykkösestä.

Lisää asiasta löytyy myös:

http://www.joegeluso.com/software/articles/ccitt.htm

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