mmeier@emdeng.Dayton.NCR.COM (Marlin.Meier) (09/22/88)
Could someone please explain what this means:
The frame check sequence is generated using the following standard
generator polynomial:
G(X) = X^32 + X^26 + X^23 + X^22 + X^16 + X^12 + X^11 + X^10 + X^8
+ X^7 + X^5 + X^4 + X^2 + X^1 + X^0.
The frame check sequence is one's complement of the sum (modulo 2) of
the following:
1. The remainder of X**k(X^31 + X^30 + ... + X^2 + X + 1)
divided (modulo 2) by G(X), where k is the number of bits
in the frame control field, destination and source addresses,
optional routing information field, and information field.
2. The remainder after multiplication by X^32 and then division
(modulo 2) by G(X) of the content (treated as a polynomial)
of the frame control field, destination and source addresses,
optional routing information field, and information field.
Any explaination especially with an example would be greatly appreciated.
Thanks in advance.
Marlin Meierrpw3@amdcad.UUCP (Rob Warnock) (09/23/88)
In article <549@emdeng.Dayton.NCR.COM> mmeier@emdeng.Dayton.NCR.COM (Marlin.Meier) writes: +--------------- | Could someone please explain what this means: | Any explaination especially with an example would be greatly appreciated. | Thanks in advance. | Marlin Meier +--------------- I'll give it a quick go, but for more details see any book on error control coding (a.k.a. algebraic coding theory). +--------------- | The frame check sequence is generated using the following standard | generator polynomial: | G(X) = X^32 + X^26 + X^23 + X^22 + X^16 + X^12 + X^11 + X^10 + X^8 | + X^7 + X^5 + X^4 + X^2 + X^1 + X^0. +--------------- This is the same as the "Ethernet" CRC-32, and there is a reference in the Ethernet spec to the Rome Air Defense Center report which showed why this polynomial was selected for Autodin-II. A full discussion of CRCs would be too long, but basically you consider the entire message to stand for the coefficients of one big binary polynomial (binary means the sums are computed modulo-2). Then you divide the message polynomial by a check polynomial (the "CRC-whatever", CRC-16, CRC-32, etc.) and send the remainder (which, note, is a polynomial too) after the data -- or rather, you send the coefficients of the remainder. All this is pretty standard, but the CRC-32 has a few wrinkles not found in other CRCs. +--------------- | The frame check sequence is one's complement of the sum (modulo 2) of | the following: | 1. The remainder of X**k(X^31 + X^30 + ... + X^2 + X + 1) | divided (modulo 2) by G(X), where k is the number of bits | in the frame control field, destination and source addresses, | optional routing information field, and information field. +--------------- What (1) is supposed to be saying is that the CRC register starts out as all_ones (that "X^31+...+X+1" term) instead of the all_zeros used in earlier CRCs. This offers more protection against the communications link possibly dropping a multiple of 32 zeroes in a row. So it's just like a regular CRC, but you start with all ones, and then just before starting to send the actual CRC (the result in the register after the data was shifted in) you switch in an inverter so that the CRC bits are sent inverted. This causes one minor glitch: At the receiver, to get a "zero" (good) CRC on the message, you need to start the receive CRC register at all ones (that's easy), and you need to turn off the feedback path just as the CRC bytes are coming in. That's harder, because you don't know where the CRC bytes are until the message ends. So you leave the feedback path on, and a "good" CRC is therefore not zeroes in the receiver CRC register, but the magic pattern (binary) 11000111000001001101110101111011. (See pages 97-98 of the Ethernet spec for details.) If you are interested, this "magic pattern" is just the initial 32 bits of ones shifted through the CRC generator 32 times. +--------------- | 2. The remainder after multiplication by X^32 and then division | (modulo 2) by G(X) of the content (treated as a polynomial) | of the frame control field, destination and source addresses, | optional routing information field, and information field. +--------------- This is just saying that when computing the transmitted CRC you stick 32 bits of zero on the end as placeholders for the CRC bits you're going to send. Again, pretty standard. Becuase the CRC-32 offers much more protection than the older CRC-16 and fixes several of the vulnerabilities of older CRCs to inserting/dropping runs of zeros, virtually all new physical media (802.5, FDDI) have adopted the CRC-32. Again, the Ethernet spec (pages 29-30, 97-98) offers some more details. Rob Warnock Systems Architecture Consultant UUCP: {amdcad,fortune,sun}!redwood!rpw3 ATTmail: !rpw3 DDD: (415)572-2607 USPS: 627 26th Ave, San Mateo, CA 94403
rpw3@amdcad.AMD.COM (Rob Warnock) (09/23/88)
In article <549@emdeng.Dayton.NCR.COM> mmeier@emdeng.Dayton.NCR.COM (Marlin.Meier) writes: +--------------- | Could someone please explain what this means: | Any explaination especially with an example would be greatly appreciated. | Thanks in advance. | Marlin Meier +--------------- I'll give it a quick go, but for more details see any book on error control coding (a.k.a. algebraic coding theory). +--------------- | The frame check sequence is generated using the following standard | generator polynomial: | G(X) = X^32 + X^26 + X^23 + X^22 + X^16 + X^12 + X^11 + X^10 + X^8 | + X^7 + X^5 + X^4 + X^2 + X^1 + X^0. +--------------- This is the same as the "Ethernet" CRC-32, and there is a reference in the Ethernet spec to the Rome Air Defense Center report which showed why this polynomial was selected for Autodin-II. A full discussion of CRCs would be too long, but basically you consider the entire message to stand for the coefficients of one big binary polynomial (binary means the sums are computed modulo-2). Then you divide the message polynomial by a check polynomial (the "CRC-whatever", CRC-16, CRC-32, etc.) and send the remainder (which, note, is a polynomial too) after the data -- or rather, you send the coefficients of the remainder. All this is pretty standard, but the CRC-32 has a few wrinkles not found in other CRCs. +--------------- | The frame check sequence is one's complement of the sum (modulo 2) of | the following: | 1. The remainder of X**k(X^31 + X^30 + ... + X^2 + X + 1) | divided (modulo 2) by G(X), where k is the number of bits | in the frame control field, destination and source addresses, | optional routing information field, and information field. +--------------- What (1) is supposed to be saying is that the CRC register starts out as all_ones (that "X^31+...+X+1" term) instead of the all_zeros used in earlier CRCs. This offers more protection against the communications link possibly dropping a multiple of 32 zeroes in a row. So it's just like a regular CRC, but you start with all ones, and then just before starting to send the actual CRC (the result in the register after the data was shifted in) you switch in an inverter so that the CRC bits are sent inverted. This causes one minor glitch: At the receiver, to get a "zero" (good) CRC on the message, you need to start the receive CRC register at all ones (that's easy), and you need to turn off the feedback path just as the CRC bytes are coming in. That's harder, because you don't know where the CRC bytes are until the message ends. So you leave the feedback path on, and a "good" CRC is therefore not zeroes in the receiver CRC register, but the magic pattern (binary) 11000111000001001101110101111011. (See pages 97-98 of the Ethernet spec for details.) If you are interested, this "magic pattern" is just the initial 32 bits of ones shifted through the CRC generator 32 times. +--------------- | 2. The remainder after multiplication by X^32 and then division | (modulo 2) by G(X) of the content (treated as a polynomial) | of the frame control field, destination and source addresses, | optional routing information field, and information field. +--------------- This is just saying that when computing the transmitted CRC you stick 32 bits of zero on the end as placeholders for the CRC bits you're going to send. Again, pretty standard. Becuase the CRC-32 offers much more protection than the older CRC-16 and fixes several of the vulnerabilities of older CRCs to inserting/dropping runs of zeros, virtually all new physical media (802.5, FDDI) have adopted the CRC-32. Again, the Ethernet spec (pages 29-30, 97-98) offers some more details. Rob Warnock Systems Architecture Consultant UUCP: {amdcad,fortune,sun}!redwood!rpw3 ATTmail: !rpw3 DDD: (415)572-2607 USPS: 627 26th Ave, San Mateo, CA 94403