Càlcul de controls de redundància cíclica

Com a exemple d'implementació de la divisió polinomial al maquinari, suposem que estem intentant calcular un CRC de 8 bits d'un missatge de 8 bits fet del caràcter ASCII "W", que és binari 01010111₂, decimal 87 ₁₀ o hexadecimal 57 ₁₆. Per il·lustració, utilitzarem el polinomi CRC-8-ATM (HEC). ${\displaystyle x^{8}+x^{2}+x+1}$ . Escriure el primer bit transmès (el coeficient de la potència més alta de ${\displaystyle x}$ ) a l'esquerra, correspon a la cadena de 9 bits "100000111".

El valor del byte 57 ₁₆ es pot transmetre en dos ordres diferents, depenent de la convenció d'ordenació de bits utilitzada. Cadascun genera un polinomi de missatge diferent ${\displaystyle M(x)}$ . Msbit primer, això és ${\displaystyle x^{6}+x^{4}+x^{2}+x+1}$ = 01010111, mentre que lsbit-primer, ho és ${\displaystyle x^{7}+x^{6}+x^{5}+x^{3}+x}$ = 11101010. Després es poden multiplicar per ${\displaystyle x^{8}}$ per produir dos polinomis de missatges de 16 bits ${\displaystyle x^{8}M(x)}$ .

El càlcul de la resta consisteix llavors a restar múltiples del polinomi generador ${\displaystyle G(x)}$ . Això és com una divisió llarga decimal, però encara més senzill perquè els únics múltiples possibles a cada pas són 0 i 1, i les restes prenen prestades "de l'infinit" en lloc de reduir els dígits superiors. Com que no ens importa el quocient, no cal registrar-lo.

Observeu que després de cada resta, els bits es divideixen en tres grups: al principi, un grup que és tot zero; al final, un grup que no canvia respecte a l'original; i un grup ombrejat blau al mig que és "interessant". El grup "interessant" té una longitud de 8 bits, que coincideix amb el grau del polinomi. A cada pas, es resta el múltiple adequat del polinomi per fer el grup zero un bit més llarg, i el grup sense canvis es fa un bit més curt, fins que només queda la resta final.

En l'exemple msbit-primer, el polinomi restant és ${\displaystyle x^{7}+x^{5}+x}$ . Convertint a un nombre hexadecimal utilitzant la convenció que la potència més alta de x és el msbit; això és A2 ₁₆. A lsbit-first, la resta és ${\displaystyle x^{7}+x^{4}+x^{3}}$ . Convertint a hexadecimal utilitzant la convenció que la potència més alta de x és lsbit, això és 19 ₁₆.

Escriure el missatge complet a cada pas, tal com es fa a l'exemple anterior, és molt tediós. Les implementacions eficients utilitzen un ${\displaystyle n}$ -Registre de desplaçament de bits per contenir només els bits interessants. Multiplicant el polinomi per ${\displaystyle x}$ equival a desplaçar el registre d'un lloc, ja que els coeficients no canvien de valor sinó que només es mouen cap al següent terme del polinomi.

Aquí teniu un primer esborrany d'algun pseudocodi per calcular un CRC de n bits. Utilitza un tipus de dades compost per a polinomis, on x no és una variable entera, sinó un constructor que genera un objecte polinomi que es pot afegir, multiplicar i exponenciar. A xor dos polinomis és sumar-los, mòdul dos; és a dir, excloure OR els coeficients de cada terme coincident dels dos polinomis.