CRC循環(huán)校驗碼詳解02

城市軌道交通專用通信設(shè)備維護課程CRC校驗碼設(shè)計差錯檢測

循環(huán)冗余校驗碼(CRC，CyclicRedundancycheck)編碼對于一個碼長為n，信息碼元為k位的循環(huán)碼(n，k),其構(gòu)成形式為：12knk+1k+2n位信息碼元k位校驗碼元r位差錯檢測

循環(huán)冗余校驗碼(CRC，CyclicRedundancycheck)若生成多項式G(x)為r階(即r＋1位位串)，原幀為m位，其多項式為M(x)，則在原幀后面添加r個0，即循環(huán)左移r位，幀成為m+r位，相應(yīng)多項式成為xrM(x);按模2除法用G(x)對應(yīng)的位串去除對應(yīng)于xrM(x)的位串,得余數(shù)R(x)；按模2減法(即模2加)從對應(yīng)于xrM(x)的位串中減去(加上)余數(shù)R(x),結(jié)果即傳送的帶校驗和的幀多項式T(x)。另一個例子例m(x)=x9+x8+x6+x4+x3+x+1,k=10(3)1101011011.000010011(模二除)商數(shù)：1100001010

余數(shù)：1110

r(x)=x3+x2+x+0所需的循環(huán)編碼C(x)為C(x)=xn·m(x)+r(x)=

1101011011，1110設(shè)編碼的信息碼元為1101011011(1)假設(shè)G(x)=x4+x+1系數(shù)形成的位串為10011則將m(x)·x4余數(shù)取4位(2)x4·m(x)=1101011011，0000另一個例子多項式除法1101011011,0000100111001110011100111011010011101001001111101100001010商數(shù)被除數(shù)m(x)余數(shù)r(x)除數(shù)P(x)1101011011.000010011模2運算①模2加法運算定義為：（對應(yīng)于邏輯異或）0＋0＝00＋1＝11＋0＝11＋1＝0例如0101＋0011＝0110，列豎式計算：0101＋0011──────0110異或計算為：1^1=00^0=01^0=10^1=1多項式的算術(shù)運算采用代數(shù)域理論的規(guī)則，加法沒進位，減法沒借位，加法和減法都等同于異或。模2運算②模2減法運算定義為：（對應(yīng)于邏輯異或）0－0＝00－1＝11－0＝11－1＝0例如0110－0011＝0101，列豎式計算：0110－0011──────0101異或計算為：1^1=00^0=01^0=10^1=1模2運算③模2乘法運算定義為：0×0＝00×1＝01×0＝01×1＝1例如1011×101＝100111，列豎式計算：1011×101──────10110000＋1011────────100111模2運算④模2除法運算定義為：0÷1＝01÷1＝1模二除法是利用模二減求余數(shù)的，余數(shù)最高位為“1”，則商“1”，否則商“0”，每商1位則余數(shù)減少一位，直到余數(shù)位數(shù)少于除數(shù)位數(shù)。1110────────1011〕1100100－1011──────1111－1011──────1000－1011──────0110－0000──────110位運算按位與運算按位與運算符"&"是雙目運算符。其功能是參與運算的兩數(shù)各對應(yīng)的二進位相與。只有對應(yīng)的兩個二進位均為1時，結(jié)果位才為1，否則為0。參與運算的數(shù)以補碼方式出現(xiàn)。例如：9&5可寫算式如下：00001001(9的二進制補碼)&00000101(5的二進制補碼)00000001可見9&5=1。按位或運算按位或運算符“|”是雙目運算符。其功能是參與運算的兩數(shù)各對應(yīng)的二進位相或。只要對應(yīng)的二個二進位有一個為1時，結(jié)果位就為1。參與運算的兩個數(shù)均以補碼出現(xiàn)。例如：9|5可寫算式如下：00001001|0000010100001101(十進制為13)可見9|5=13求反運算符～為單目運算符，具有右結(jié)合性。其功能是對參與運算的數(shù)的各二進位按位求反。例如～9的運算為：~(0000000000001001)結(jié)果為：1111111111110110位運算按位異或運算按位異或運算符“^”是雙目運算符。其功能是參與運算的兩數(shù)各對應(yīng)的二進位相異或，當(dāng)兩對應(yīng)的二進位相異時，結(jié)果為1。參與運算數(shù)仍以補碼出現(xiàn)，例如9^5可寫成算式如下：00001001^0000010100001100(十進制為12)左移運算左移運算符“<<”是雙目運算符。其功能把“<<”左邊的運算數(shù)的各二進位全部左移若干位，由“<<”右邊的數(shù)指定移動的位數(shù)，高位丟棄，低位補0。例如：a<<4指把a的各二進位向左移動4位。如a=00000011(十進制3)，左移4位后為00110000(十進制48)。右移運算右移運算符“>>”是雙目運算符。其功能是把“>>”左邊的運算數(shù)的各二進位全部右移若干位，“>>”右邊的數(shù)指定移動的位數(shù)。例如：設(shè)a=15，