Electronic – Finding an input sequence given a generating polynomial and CRC

crc

I am working on a circuit that inputs a 31-bit pseudo-random binary string into a CCITT CRC-16 block which generates a 16-bit CRC output.

I know that M(x)/G(x) = Q(x) + R(x) and the transmitted code will be R(x) appended to M(x). [Q(x) is discarded].

When I simulated the circuit, I got a CRC of 1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0. From the help file of the software (VisSim/Comm), I know that the generating polynomial is G(x) = 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1.

How do I determine the 31-bit input sequence that generated the CRC result?

Since M(x)/G(x) = Q(x) + R(x), we can say that M(x) = [Q(x) + R(x)]G(x). But we don't know Q(x). Assuming the 16-bit CRC is equal to R(x) and the G(x) is given, how do I go about finding M(x) without knowing Q(x)?

Best Answer

What this is telling you is that there is an infinite number of messages that will produce the same CRC, one for each possible Q(x). All you need to do is pick some particular value of Q(x) and generate the correesponding M(x).

Related Solutions

Electronic – Reverse-engineering IR check bits/CRC

First of all, it's pretty clear that the "XX" bits are part of the channel designation, since that's the only thing they depend on. The "XX" bits may simply be a check on the "Ch" bits.

The check bits are a simple bitwise XOR of 24 of the 26 data bits: If you take the 6 Yaw bits, the 6 LSBs of the Throttle, the 6 Pitch bits, and the next 6 bits, and XOR these quantities together, you get the 6 check bits. It appears that the upper 2 bits of the Throttle do not affect the check bits at all.

The following Perl script verifies this.

#!/usr/bin/perl

# crc.pl - verify decoding of check bits

# On the lines starting with '1', just keep the '0's and '1's in an array. 
while (<>) {
    my @letters = split '', $_;
    next unless $letters[0] eq '1';
    @letters = grep /[01]/, @letters;
    @letters = @letters[1..32];
    $a = string2bin (@letters[0..5]);
    $b = string2bin (@letters[8..13]);
    $c = string2bin (@letters[14..19]);
    $d = string2bin (@letters[20..25]);
    $e = string2bin (@letters[26..31]);
    $f = $a ^ $b ^ $c ^ $d;
    printf "%02X %02X %02X %02X %02X %02X %s\n", $a, $b, $c, $d, $e, $f,
        $e == $f ? '-' : '###';
}

sub string2bin {
    my $temp = 0;
    for (@_) {
        $temp = ($temp << 1) + ($_ eq '1' ? 1 : 0);
    }
    $temp;
}

Electronic – CRC polynomial and Parity Error detection

This is a general rule , in youre case k = 6

Short Burst Errors

(Length b ≤ k, number of redundant bits)

-->All errors up to length k are detected

Long Burst Errors (Length b = k+1)

Undetectable only if burst error is the same as g(x)

g(x) = x^k+ … + 1       k-1 bits between xk and x0 
e(x) = x^k + … + 1      must match

Probability of not detecting the error is 2^(-(k-1))

Longer Burst Errors (Length m > k+1)

Probability of not detecting the error is 2^(-k)

Best Answer

Related Solutions

Electronic – Reverse-engineering IR check bits/CRC

Electronic – CRC polynomial and Parity Error detection

Related Topic