Q's CRC calcs.
| Optical Storage Technical Discussions Discuss, Q's CRC calcs. at Computer Hardware forum; The general data format of channel Q shall be: S0 (1 bit), S1 (1 bit) | CONTROL (4 bits) | ADR (4 bits) |DATA-Q (72 bits) | CRC (16 bits) | S0, S1 ... CRC: A 16-bit CRC on CONTROL, ADR and DATA-Q, MSB is first out. On the disc |
Posted: 07-01-2006 - #1
| The general data format of channel Q shall be: S0 (1 bit), S1 (1 bit) | CONTROL (4 bits) | ADR (4 bits) |DATA-Q (72 bits) | CRC (16 bits) | S0, S1 ... CRC: A 16-bit CRC on CONTROL, ADR and DATA-Q, MSB is first out. On the disc the parity bits are inverted. The syndrome shall be compared with 0. Polynomial: P(X) = X^16 + X^12 + X^5 +1 How does one use that poly? Thanks in advance. |
- Today (MyCE Staff)
- Posts: 15,596
| |
Posted: 07-01-2006 - #2
| To prevent getting overly mathematical (the theory on which CRC codes are based requires some understanding of algebra), I will mainly show it with an example. Here are five (consecutive) 96 bit Q-channel bitstrings from an actual CD: 000000010000001100000001000000000000011101000011000000000000100001010100011010000100101110 100010 000000010000001100000001000000000000011101000100000000000000100001010100011010010011110001 010111 000000010000001100000001000000000000011101000101000000000000100001010100011100000001010100 011110 000000010000001100000001000000000000011101000110000000000000100001010100011100011110101111 101101 000000010000001100000001000000000000011101000111000000000000100001010100011100100111000111 011111 Prior to doing the CRC calculation, a preparatory step is that the last 16 bits need to be inverted. With CRCs, this is a standard trick to prevent certain types of errors going undetected (such the insertion of spurious zeroes in a run of zeroes). Let's look at the first 96 bit Q channel: 000000010000001100000001000000000000011101000011000000000000100001010100011010000100101110 100010 First, invert the last 16 bits gives the q channel poly: q(x) = 000000010000001100000001000000000000011101000011000000000000100001010100011010001011010001 011101 Now comes the difficult part: mathematically, this bitstring can be viewed as a polynomial where the zeroes and ones represent coefficients. The bitstring above, for example, is: q(x) = 0*x^95 + 0 * x^ 94 + 0 * x ^ 93 + ..... + 1 * x^3 + 1 * x^2 + 0 * x^1 + 1 * x^0. The other way around, it is possible to represent the so-called 'generator' polynomial of the CRC, which is g(x) = x^16 + x^12 + x^5 + 1, as a bitstring: g(x) = 10001000000100001. Multiplying this by x just means adding a zero. For example, x^3 * g(x) can be represented as the bitstring 10001000000100001000 - it's just g(x) with three zeroes added on the right. We'll need this later on! Adding two polynomials is done 'modulo 2', mathematically. In the 'bitstring' view, this corresponds to a XOR operation. For polynomials modulo-2, we have the funny property that p(x)+q(x) == p(x)-q(x); addition and subtraction are basically the same operation (the XOR, when thinking about the polys as bitstrings). Now the defining property of the CRC as it applies to this case: *** The 16-bit CRC (prior to inverting!) is chosen in such a way that q(x) is divisible by g(x). *** If bits are inverted due to error, this will almost always show up because the property above no longer holds. In fact, well-chosen CRC generator polynomials have some nice, guaranteed properties in this respect: they detect any odd number of bit errors; they detect all double bit-errors; and they detect any 'burst errors' that are limited to a stretch of bits less than or equal to the degree of the polynomial. So now we get to the answer to your question: how do we use g(x) ? We use it to check whether q(x) is divisible by g(x). Now, how do we do /that/ ? Conceptually, this is easy: to check whether something is divisible by a certain divisor, we subtract multiples of the divisor from it. Either we will reach zero (in case the original was divisible by the divisor), or a value from which we no longer can subtract the divisor without going below zero (in case the original wasn't divisible). Make sure you understand this simple mathematical gem: it works for normal numbers, 'line lengths', and polynomials - it doesn't matter. So to get back to our example: we need to check if g(x) divides q(x) by repeatedly subtracting multiples of g(x). We start with... q(x) = 000000010000001100000001000000000000011101000011000000000000100001010100011010001011010001 011101 = 1000000110000000100000000000001110100001100000000000010000101010001101000101101000101110 (the leading zeroes can be ignored - compare this to normal numbers where this is also true. As an aside: normal numbers really /are/ polynomials in a way, except that we normally use 10 (the 'base') instead of x. Think about it: if f(x) = 1*x^2+2*x^1+3*x^0, then f(10) is our number 123! -- end of aside). Now division by g(x) proceeds pretty similar to regular 'longhand' division - only it is MUCH simpler since subtracting is just a XOR (we don't have 'carry'). The division can get pretty long though (yes I did the example below by hand ...  )The calculation q(x) / g(x) proceeds as follows: we repeatedly subtract multiples of g(x) (remember, a multiple of g(x) or x^n * g(x) is just g(x) with n zeroes appended) until this is no longer possible: Code: 10000001100000001000000000000011101000011000000000000100001010100011010001011010001011101
10001000000100001000000000000000000000000000000000000000000000000000000000000000000000000 -
=========================================================================================
1001100100000000000000000011101000011000000000000100001010100011010001011010001011101
1000100000010000100000000000000000000000000000000000000000000000000000000000000000000 -
=====================================================================================
1000100010000100000000011101000011000000000000100001010100011010001011010001011101
1000100000010000100000000000000000000000000000000000000000000000000000000000000000 -
==================================================================================
10010100100000011101000011000000000000100001010100011010001011010001011101
10001000000100001000000000000000000000000000000000000000000000000000000000 -
=========================================================================
11100100100010101000011000000000000100001010100011010001011010001011101
10001000000100001000000000000000000000000000000000000000000000000000000 -
=======================================================================
1101100100110100000011000000000000100001010100011010001011010001011101
1000100000010000100000000000000000000000000000000000000000000000000000 -
======================================================================
101000100100100100011000000000000100001010100011010001011010001011101
100010000001000010000000000000000000000000000000000000000000000000000 -
======================================================================
1010100101100110011000000000000100001010100011010001011010001011101
1000100000010000100000000000000000000000000000000000000000000000000 -
===================================================================
10000101110110111000000000000100001010100011010001011010001011101
10001000000100001000000000000000000000000000000000000000000000000 -
==============================================================
1101110010110000000000000100001010100011010001011010001011101
1000100000010000100000000000000000000000000000000000000000000 -
=============================================================
101010010100000100000000100001010100011010001011010001011101
100010000001000010000000000000000000000000000000000000000000 -
============================================================
1000010101000110000000100001010100011010001011010001011101
1000100000010000100000000000000000000000000000000000000000 -
==========================================================
110101010110100000100001010100011010001011010001011101
100010000001000010000000000000000000000000000000000000 -
======================================================
10111010111100010100001010100011010001011010001011101
10001000000100001000000000000000000000000000000000000 -
=====================================================
110010111000011100001010100011010001011010001011101
100010000001000010000000000000000000000000000000000 -
===================================================
10000111001011110001010100011010001011010001011101
10001000000100001000000000000000000000000000000000 -
==================================================
1111001111111001010100011010001011010001011101
1000100000010000100000000000000000000000000000 -
==============================================
111101111101001110100011010001011010001011101
100010000001000010000000000000000000000000000 -
=============================================
11111111100001100100011010001011010001011101
10001000000100001000000000000000000000000000 -
============================================
1110111100101101100011010001011010001011101
1000100000010000100000000000000000000000000 -
===========================================
110011100111101000011010001011010001011101
100010000001000010000000000000000000000000 -
==========================================
10001100110101010011010001011010001011101
10001000000100001000000000000000000000000 -
=========================================
100110001011011010001011010001011101
100010000001000010000000000000000000 -
====================================
100001010011000001011010001011101
100010000001000010000000000000000 -
=================================
11010010000011011010001011101
10001000000100001000000000000 -
=============================
1011010000111010010001011101
1000100000010000100000000000 -
============================
11110000101010110001011101
10001000000100001000000000 -
==========================
1111000101110111001011101
1000100000010000100000000 -
=========================
111100101100111101011101
100010000001000010000000 -
========================
11110101101111111011101
10001000000100001000000 -
=======================
1111101101011110011101
1000100000010000100000 -
======================
111001101001110111101
100010000001000010000 -
=====================
11011101000110101101
10001000000100001000 -
====================
1010101000010100101
1000100000010000100 -
===================
10001000000100001
10001000000100001 -
=================
0
Hope this helps. |
Posted: 07-01-2006 - #3
| Quote:
A simple, straightforward implementation: http://www.eagleairaust.com.au/code/crc16.htm Or a table-driven implementation: http://dsl.ee.unsw.edu.au/dsl-cdrom/.../cyg/crc/crc.h http://dsl.ee.unsw.edu.au/dsl-cdrom/...nt/src/crc16.c Both run at tens or hundreds of megabytes per second on a modern desktop CPU.
__________________ Frequently used/favorite: BenQ 1640 1800 LG H22N H42N Sony BWU-100A Occasionally used/retired: BenQ 1620 DQ60 1655 1680 LG 4163B 4166B H10N H50N H55N Lite-On 165P6S 18A1P 20A1P NEC 3540A Pioneer A09XL 110 111D 112D Plextor 716A Samsung S182D S203B Sony 820A |
Posted: 07-01-2006 - #4
| I ran the first, simpler implementation on the fifth packet from the example by reddish, and it is correct. Split into bytes, we have 80 data bits + 16 parity bits: 00000001 00000011 00000001 00000000 00000111 01000111 00000000 00001000 01010100 01110010 01110001 11011111. In hexadecimal, 01 03 01 00 07 47 00 08 54 72 71 df. Running the first 10 bytes through the calculation, we expect to get 0x71df in unsigned short crc. And we do. unsigned char data[10] = { 0x01, 0x03, 0x01, 0x00, 0x07, 0x47, 0x00, 0x08, 0x54, 0x72 }; unsigned short crc = 0; for (int i = 0; i < 10; i++) { crc = (unsigned char)(crc >> 8) | (crc << 8); crc ^= data[i]; crc ^= (unsigned char)(crc & 0xff) >> 4; crc ^= (crc << 8) << 4; crc ^= ((crc & 0xff) << 4) << 1; } crc ^= 0xffff; assert(crc == 0x71df);
__________________ Frequently used/favorite: BenQ 1640 1800 LG H22N H42N Sony BWU-100A Occasionally used/retired: BenQ 1620 DQ60 1655 1680 LG 4163B 4166B H10N H50N H55N Lite-On 165P6S 18A1P 20A1P NEC 3540A Pioneer A09XL 110 111D 112D Plextor 716A Samsung S182D S203B Sony 820A |
Posted: 07-01-2006 - #5
| Quote:
|
Posted: 07-01-2006 - #6
| Quote:
__________________ Frequently used/favorite: BenQ 1640 1800 LG H22N H42N Sony BWU-100A Occasionally used/retired: BenQ 1620 DQ60 1655 1680 LG 4163B 4166B H10N H50N H55N Lite-On 165P6S 18A1P 20A1P NEC 3540A Pioneer A09XL 110 111D 112D Plextor 716A Samsung S182D S203B Sony 820A |
There's more to MyCE.com
Listen up, we've got more. Product information on 107,830 products. Our experts have written 523 articles. We've gathered 16,128 news items for you to always keep updated.
