📄 crc_v3.txt
字号:
because we don't know that x is 2. In this true polynomial arithmeticthe relationship between all the coefficients is unknown and so thecoefficients of each power effectively become strongly typed;coefficients of x^2 are effectively of a different type tocoefficients of x^3.With the coefficients of each power nicely isolated, mathematicianscame up with all sorts of different kinds of polynomial arithmeticssimply by changing the rules about how coefficients work. Of theseschemes, one in particular is relevant here, and that is a polynomialarithmetic where the coefficients are calculated MOD 2 and there is nocarry; all coefficients must be either 0 or 1 and no carries arecalculated. This is called "polynomial arithmetic mod 2". Thus,returning to the earlier example:(x^3 + x^2 + x^0)(x^3 + x^1 + x^0)= (x^6 + x^4 + x^3 + x^5 + x^3 + x^2 + x^3 + x^1 + x^0)= x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0Under the other arithmetic, the 3*x^3 term was propagated using thecarry mechanism using the knowledge that x=2. Under "polynomialarithmetic mod 2", we don't know what x is, there are no carries, andall coefficients have to be calculated mod 2. Thus, the resultbecomes:= x^6 + x^5 + x^4 + x^3 + x^2 + x^1 + x^0As Knuth [Knuth81] says (p.400): "The reader should note the similarity between polynomial arithmetic and multiple-precision arithmetic (Section 4.3.1), where the radix b is substituted for x. The chief difference is that the coefficient u_k of x^k in polynomial arithmetic bears little or no relation to its neighboring coefficients x^{k-1} [and x^{k+1}], so the idea of "carrying" from one place to another is absent. In fact polynomial arithmetic modulo b is essentially identical to multiple precision arithmetic with radix b, except that all carries are suppressed."Thus polynomical arithmetic mod 2 is just binary arithmetic mod 2 withno carries. While polynomials provide useful mathematical machinery inmore analytical approaches to CRC and error-correction algorithms, forthe purposes of exposition they provide no extra insight and someencumbrance and have been discarded in the remainder of this documentin favour of direct manipulation of the arithmetical system with whichthey are isomorphic: binary arithmetic with no carry.5. Binary Arithmetic with No Carries------------------------------------Having dispensed with polynomials, we can focus on the real arithmeticissue, which is that all the arithmetic performed during CRCcalculations is performed in binary with no carries. Often this iscalled polynomial arithmetic, but as I have declared the rest of thisdocument a polynomial free zone, we'll have to call it CRC arithmeticinstead. As this arithmetic is a key part of CRC calculations, we'dbetter get used to it. Here we go:Adding two numbers in CRC arithmetic is the same as adding numbers inordinary binary arithmetic except there is no carry. This means thateach pair of corresponding bits determine the corresponding output bitwithout reference to any other bit positions. For example: 10011011 +11001010 -------- 01010001 --------There are only four cases for each bit position: 0+0=0 0+1=1 1+0=1 1+1=0 (no carry)Subtraction is identical: 10011011 -11001010 -------- 01010001 --------with 0-0=0 0-1=1 (wraparound) 1-0=1 1-1=0In fact, both addition and subtraction in CRC arithmetic is equivalentto the XOR operation, and the XOR operation is its own inverse. Thiseffectively reduces the operations of the first level of power(addition, subtraction) to a single operation that is its own inverse.This is a very convenient property of the arithmetic.By collapsing of addition and subtraction, the arithmetic discards anynotion of magnitude beyond the power of its highest one bit. While itseems clear that 1010 is greater than 10, it is no longer the casethat 1010 can be considered to be greater than 1001. To see this, notethat you can get from 1010 to 1001 by both adding and subtracting thesame quantity: 1010 = 1010 + 0011 1010 = 1010 - 0011This makes nonsense of any notion of order.Having defined addition, we can move to multiplication and division.Multiplication is absolutely straightforward, being the sum of thefirst number, shifted in accordance with the second number. 1101 x 1011 ---- 1101 1101. 0000.. 1101... ------- 1111111 Note: The sum uses CRC addition -------Division is a little messier as we need to know when "a number goesinto another number". To do this, we invoke the weak definition ofmagnitude defined earlier: that X is greater than or equal to Y iffthe position of the highest 1 bit of X is the same or greater than theposition of the highest 1 bit of Y. Here's a fully worked division(nicked from [Tanenbaum81]). 1100001010 _______________10011 ) 11010110110000 10011,,.,,.... -----,,.,,.... 10011,.,,.... 10011,.,,.... -----,.,,.... 00001.,,.... 00000.,,.... -----.,,.... 00010,,.... 00000,,.... -----,,.... 00101,.... 00000,.... -----,.... 01011.... 00000.... -----.... 10110... 10011... -----... 01010.. 00000.. -----.. 10100. 10011. -----. 01110 00000 ----- 1110 = RemainderThat's really it. Before proceeding further, however, it's worth ourwhile playing with this arithmetic a bit to get used to it.We've already played with addition and subtraction, noticing that theyare the same thing. Here, though, we should note that in thisarithmetic A+0=A and A-0=A. This obvious property is very usefullater.In dealing with CRC multiplication and division, it's worth getting afeel for the concepts of MULTIPLE and DIVISIBLE.If a number A is a multiple of B then what this means in CRCarithmetic is that it is possible to construct A from zero by XORingin various shifts of B. For example, if A was 0111010110 and B was 11,we could construct A from B as follows: 0111010110 = .......11. + ....11.... + ...11..... .11.......However, if A is 0111010111, it is not possible to construct it out ofvarious shifts of B (can you see why? - see later) so it is said to benot divisible by B in CRC arithmetic.Thus we see that CRC arithmetic is primarily about XORing particularvalues at various shifting offsets.6. A Fully Worked Example-------------------------Having defined CRC arithmetic, we can now frame a CRC calculation assimply a division, because that's all it is! This section fills in thedetails and gives an example.To perform a CRC calculation, we need to choose a divisor. In mathsmarketing speak the divisor is called the "generator polynomial" orsimply the "polynomial", and is a key parameter of any CRC algorithm.It would probably be more friendly to call the divisor something else,but the poly talk is so deeply ingrained in the field that it wouldnow be confusing to avoid it. As a compromise, we will refer to theCRC polynomial as the "poly". Just think of this number as a sort ofparrot. "Hello poly!"You can choose any poly and come up with a CRC algorithm. However,some polys are better than others, and so it is wise to stick with thetried an tested ones. A later section addresses this issue.The width (position of the highest 1 bit) of the poly is veryimportant as it dominates the whole calculation. Typically, widths of16 or 32 are chosen so as to simplify implementation on moderncomputers. The width of a poly is the actual bit position of thehighest bit. For example, the width of 10011 is 4, not 5. For thepurposes of example, we will chose a poly of 10011 (of width W of 4).Having chosen a poly, we can proceed with the calculation. This issimply a division (in CRC arithmetic) of the message by the poly. Theonly trick is that W zero bits are appended to the message before theCRC is calculated. Thus we have: Original message : 1101011011 Poly : 10011 Message after appending W zeros : 11010110110000Now we simply divide the augmented message by the poly using CRCarithmetic. This is the same division as before: 1100001010 = Quotient (nobody cares about the quotient) _______________10011 ) 11010110110000 = Augmented message (1101011011 + 0000)=Poly 10011,,.,,.... -----,,.,,.... 10011,.,,.... 10011,.,,.... -----,.,,.... 00001.,,.... 00000.,,.... -----.,,.... 00010,,.... 00000,,.... -----,,.... 00101,.... 00000,.... -----,.... 01011.... 00000.... -----.... 10110... 10011... -----... 01010.. 00000.. -----.. 10100. 10011. -----. 01110 00000 ----- 1110 = Remainder = THE CHECKSUM!!!!The division yields a quotient, which we throw away, and a remainder,which is the calculated checksum. This ends the calculation.Usually, the checksum is then appended to the message and the resulttransmitted. In this case the transmission would be: 11010110111110.At the other end, the receiver can do one of two things: a. Separate the message and checksum. Calculate the checksum for the message (after appending W zeros) and compare the two checksums. b. Checksum the whole lot (without appending zeros) and see if it comes out as zero!These two options are equivalent. However, in the next section, wewill be assuming option b because it is marginally mathematicallycleaner.A summary of the operation of the class of CRC algorithms: 1. Choose a width W, and a poly G (of width W). 2. Append W zero bits to the message. Call this M'. 3. Divide M' by G using CRC arithmetic. The remainder is the checksum.That's all there is to it.7. Choosing A Poly------------------Choosing a poly is somewhat of a black art and the reader is referredto [Tanenbaum81] (p.130-132) which has a very clear discussion of this⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -