[JAVA] Computazione di 4 bit di crc

[xirc85]

Ciao a tutti!
Devo computare 4 bit di crc su un'insieme di bit di numero variabile.
Però non so se esiste un modo tramite api java oppure se devo farmelo a mano...

Grazie in anticipo

[andbin]

Originariamente inviato da xirc85

Devo computare 4 bit di crc su un'insieme di bit di numero variabile.
Però non so se esiste un modo tramite api java oppure se devo farmelo a mano...

No, non c'è nulla di già fatto, almeno per quanto riguarda il framework standard (che io sappia, ovviamente). Tra l'altro un CRC di 4 bit è alquanto inconsueto.

Piuttosto, indica:
* Il polinomio da usare
* Il valore di inizializzazione
* Se le "parole" in input vanno riflesse
* Se il CRC finale va riflesso
* Se il CRC finale va XORato con un certo valore

Questi sono i parametri che vengono usati tipicamente per descrivere un algoritmo CRC.

[xirc85]

In effetti non saprei risponderti con esattezza, poichè mi è stata data piena libertà a riguardo , ma non avendo molta esperienza non so da dove iniziare...

[andbin]

Originariamente inviato da xirc85

In effetti non saprei risponderti con esattezza, poichè mi è stata data piena libertà a riguardo , ma non avendo molta esperienza non so da dove iniziare...

Uhm ... allora è un problema in più.

Innanzitutto inizia a vedere qui: http://en.wikipedia.org/wiki/Cyclic_redundancy_check

Un CRC a 4 bit in effetti c'è.

[xirc85]

Ho letto quanto mi hai suggerito...
In linea di principio credo ci aver capito più o meno come devo fare...
Correggimi se sbaglio, dato il polinomio devo fare un xor iterativamente sui bit fino a che non arrivo ad avere un uno a destra in posizione numero_bit-numero_bit_polinomio e a questo punto applicando ancora xor, ottengo i miei bit di crc. Giusto?
Ho però un dubbio per quanto riguarda il polinomio da usare. Mi spiego meglio: nell'esempio fornito (da Wiki) si faceva riferimento a un crc a 3-bit e non ho capito come ha ottenuto il divisore a 4 bit.

Grazie mille

[andbin]

Ti faccio un esempio: tra i vari CRC elencati nella pagina di Wikipedia che ho indicato, c'è un CRC-8 ATM. È abbastanza semplice perché il valore iniziale è 0, non c'è riflessione per input/output e non c'è XOR sull'output.

Tradotto in codice:

public class TestCrc8
{
    // Polinomio CRC-8 ATM: x^8 + x^2 + x + 1
    public static final byte CRC8ATM_POLY = 0x07;

    public static void main (String[] args)
    {
        // sequenza di test '123456789'
        byte[] data = { 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39 };

        byte crc = crc8Atm (data);

        System.out.format ("CRC 8-ATM = %02X%n", crc);
    }

    public static byte crc8Atm (byte[] v)
    {
        byte crc = 0;

        for (byte b : v)
        {
            crc = (byte) (crc ^ b);

            for (int i = 0; i < 8; i++)
                crc = (byte) (crc << 1 ^ ((crc & 0x80) != 0 ? CRC8ATM_POLY : 0));
        }
        
        return crc;
    }
}

Il CRC-8 ATM della sequenza '123456789' è F4h

[xirc85]

Grazie per il codice che mi hai fornito
Un'ultima cosa: come faccio a calcolarmi il polinomio? credo che sia una cosa del tipo x^4+x+1, ma non so cosa ne risulta...

Grazie ancora

[xirc85]

Credo di aver trovato la soluzione.. bastava pensare in maniera ovvia

Grazie ancora

[andbin]

Originariamente inviato da xirc85

Grazie per il codice che mi hai fornito

Prego, ma è solo un esempio, che comunque devi adattare al CRC che poi scegli.

Originariamente inviato da xirc85

Un'ultima cosa: come faccio a calcolarmi il polinomio? credo che sia una cosa del tipo x^4+x+1, ma non so cosa ne risulta...

Una cosa è se devi studiare tu un polinomio (deve avere delle proprietà ben precise), un'altra se devi "tradurlo" in un valore da usare nel codice.
La traduzione è semplice: Il bit più alto lo togli, per il resto, x lo fai diventare 2. Per il CRC-8 ATM che è:

x^8 + x^2 + x + 1

2^2 + 2 + 1 = 7

Il monomio più a sinistra (quello che dà il grado del polinomio) si toglie per un motivo. Nota che nel codice c'è uno shift a sinistra del CRC. Quando un bit a 1 "sbuca" fuori a sinistra (è poi il test che si fa con (crc & 0x80) ), si fa lo XOR con il polinomio. Quindi il bit 1 che sbuca andrebbe concettualmente in XOR con il bit più alto del polinomio (= 0). Per questo non lo si usa.


EDIT: aggiungo ancora una cosa. La implementazione che ho fatto è a "bit", ovviamente poco performante. Per velocizzare la computazione si usa in genere una implementazione "table based", in cui si precalcolano i CRC delle N parole, poi si combinano in modo "particolare" (adesso su due piedi non ricordo di preciso come).