原理與MATLAB仿真：從逐位法到查表法全解析)
簡(jiǎn)介這是一份基于MATLAB環(huán)境的CRC循環(huán)冗余校驗(yàn)仿真程序包面向通信工程、數(shù)據(jù)存儲(chǔ)及嵌入式方向的初學(xué)者與研發(fā)人員用于解決數(shù)據(jù)傳輸完整性校驗(yàn)的原理理解與仿真實(shí)現(xiàn)問(wèn)題。資源共包含4個(gè)M文件涵蓋主程序、編碼函數(shù)、解碼函數(shù)與完整校驗(yàn)流程壓縮包僅2KB代碼精簡(jiǎn)便于逐行閱讀與二次擴(kuò)展。程序圍繞生成多項(xiàng)式、預(yù)處理左移、模2除法及余數(shù)校驗(yàn)等核心步驟展開(kāi)并給出了從原始數(shù)據(jù)附加校驗(yàn)碼、發(fā)送、接收端再次相除并判定余數(shù)是否為零的完整鏈路同時(shí)支持人為翻轉(zhuǎn)比特位模擬信道干擾直觀檢驗(yàn)CRC的檢錯(cuò)能力。除常規(guī)生成、添加與驗(yàn)證流程外也可對(duì)照代碼分析不同生成多項(xiàng)式對(duì)檢錯(cuò)效果的影響適合串聯(lián)起《通信原理》《計(jì)算機(jī)網(wǎng)絡(luò)》課程實(shí)驗(yàn)與畢業(yè)設(shè)計(jì)。已有940人學(xué)習(xí)下載對(duì)于希望快速掌握CRC算法并完成MATLAB仿真的讀者是一份輕量而實(shí)用的參考資料。 做通信和嵌入式調(diào)試的朋友應(yīng)該都遇到過(guò)這個(gè)場(chǎng)景串口收到一包數(shù)據(jù)沒(méi)人敢保證這包數(shù)據(jù)在傳輸過(guò)程中沒(méi)被干擾過(guò)固件升級(jí)文件拷貝到一半也沒(méi)人能肉眼看出文件是不是少了幾字節(jié)。CRC循環(huán)冗余校驗(yàn)就是用來(lái)解決這類問(wèn)題的經(jīng)典方案也是我這些年調(diào)試鏈路、設(shè)計(jì)通信協(xié)議時(shí)用得最多的校驗(yàn)手段之一。之前我整理過(guò)一個(gè)基于MATLAB的CRC仿真程序把CRC-8、CRC-16、CRC-32的生成、拼接、校驗(yàn)、錯(cuò)誤注入全都在一個(gè)腳本里跑通了。這篇文章就把這個(gè)仿真程序的設(shè)計(jì)思路、完整代碼和踩過(guò)的坑拆開(kāi)講適合做通信、嵌入式、上位機(jī)開(kāi)發(fā)的工程師也適合正在學(xué)數(shù)據(jù)鏈路層課程但被教材繞暈的在校生。這套仿真最大的價(jià)值在于先用MATLAB把算法和協(xié)議參數(shù)驗(yàn)證清楚等邏輯完全沒(méi)問(wèn)題了再往C語(yǔ)言、Verilog或者單片機(jī)上移植可以省掉大量在硬件上反復(fù)燒錄調(diào)試的時(shí)間。下面從原理開(kāi)始一步步帶你搭一個(gè)能跑的CRC仿真環(huán)境。1. 項(xiàng)目整體思路為什么需要CRC為什么用MATLAB1.1 校驗(yàn)的本質(zhì)給數(shù)據(jù)加一道“冗余保險(xiǎn)”任何校驗(yàn)算法本質(zhì)上干的都是同一件事發(fā)送端在有效數(shù)據(jù)后面附加一段冗余信息這段冗余信息由原始數(shù)據(jù)通過(guò)某種規(guī)則計(jì)算得出接收端拿到完整數(shù)據(jù)后用同樣的規(guī)則重新計(jì)算再把計(jì)算結(jié)果和收到的冗余信息對(duì)比一致就認(rèn)為數(shù)據(jù)沒(méi)問(wèn)題不一致就說(shuō)明傳輸過(guò)程中發(fā)生了錯(cuò)誤。這就像寄快遞時(shí)發(fā)件人會(huì)在包裹上貼一張寫了重量的標(biāo)簽。收件人收到快遞后如果把包裹放到秤上一稱重量和標(biāo)簽對(duì)不上就知道包裹要么在半路被調(diào)包了要么內(nèi)部東西壞了。不過(guò)“重量校驗(yàn)”太粗糙了數(shù)據(jù)包里哪怕只翻轉(zhuǎn)了一個(gè)比特如果剛好有另一個(gè)比特也跟著翻轉(zhuǎn)總量可能不變這就會(huì)出現(xiàn)漏檢。CRC比這種簡(jiǎn)單校驗(yàn)強(qiáng)的地方在于它不是簡(jiǎn)單加和而是把數(shù)據(jù)當(dāng)成一個(gè)大的二進(jìn)制數(shù)通過(guò)多項(xiàng)式除法把錯(cuò)誤特征“攤開(kāi)”到整個(gè)數(shù)據(jù)長(zhǎng)度上單比特翻轉(zhuǎn)、雙比特翻轉(zhuǎn)這類常見(jiàn)錯(cuò)誤基本都能抓住。1.2 CRC的數(shù)學(xué)原理二進(jìn)制多項(xiàng)式除法CRC的全稱是Cyclic Redundancy Check核心思想聽(tīng)起來(lái)有點(diǎn)嚇人其實(shí)拆開(kāi)了很簡(jiǎn)單。把待發(fā)送的數(shù)據(jù)看成一個(gè)二進(jìn)制多項(xiàng)式比如字節(jié)0x0B二進(jìn)制00001011可以對(duì)應(yīng)成多項(xiàng)式“x^3 x 1”。發(fā)送端把這個(gè)數(shù)據(jù)多項(xiàng)式左移r位r是校驗(yàn)位寬度然后除以一個(gè)發(fā)送端和接收端約定好的“生成多項(xiàng)式”取余數(shù)這個(gè)余數(shù)就是CRC校驗(yàn)碼。這里的除法不是普通十進(jìn)制除法而是模2除法說(shuō)人話就是按位異或。整個(gè)過(guò)程只有0和1的異或運(yùn)算沒(méi)有進(jìn)位也沒(méi)有借位。因?yàn)檫\(yùn)算規(guī)則簡(jiǎn)單硬件上只需要移位寄存器和異或門就能實(shí)現(xiàn)這也是CRC在串口通信、網(wǎng)卡、存儲(chǔ)設(shè)備里被用了這么多年依然不過(guò)時(shí)的原因。生成多項(xiàng)式的選擇很有講究常見(jiàn)的CRC-8、CRC-16、CRC-32都有標(biāo)準(zhǔn)定義。比如CRC-16常用的多項(xiàng)式0x8005寫成二進(jìn)制就是“1000 0000 0000 0101”代表“x^16 x^15 x^2 1”。選用標(biāo)準(zhǔn)多項(xiàng)式的好處是檢錯(cuò)能力經(jīng)過(guò)充分驗(yàn)證而且不同設(shè)備之間能互相兼容。我自己見(jiàn)過(guò)不少人在實(shí)際項(xiàng)目里自己“發(fā)明”多項(xiàng)式結(jié)果檢錯(cuò)效果一塌糊涂這個(gè)問(wèn)題后面專門說(shuō)。1.3 為什么選MATLAB做仿真而不是直接上單片機(jī)做CRC校驗(yàn)最后肯定要落到C語(yǔ)言或者硬件電路里但在起步階段用MATLAB做仿真有三個(gè)明顯優(yōu)勢(shì)。第一個(gè)優(yōu)勢(shì)是調(diào)試直觀。MATLAB里數(shù)組、矩陣、位操作都是原生支持變量值隨時(shí)可以在工作區(qū)點(diǎn)開(kāi)看還能用disp直接打印每步的中間結(jié)果。相比之下C語(yǔ)言里面做位操作得時(shí)刻小心數(shù)據(jù)類型溢出、無(wú)符號(hào)整型的移位方向調(diào)試起來(lái)心智負(fù)擔(dān)重很多。第二個(gè)優(yōu)勢(shì)是測(cè)試方便。MATLAB寫腳本不需要交叉編譯不需要下載到板子改一行代碼立刻能看到結(jié)果。做錯(cuò)誤注入實(shí)驗(yàn)時(shí)只要用bitxor把數(shù)據(jù)里的某幾個(gè)比特翻轉(zhuǎn)一下就能快速驗(yàn)證CRC的檢錯(cuò)能力這在硬件環(huán)境里做要麻煩得多。第三個(gè)優(yōu)勢(shì)是知識(shí)遷移容易。把MATLAB里的算法邏輯理清楚之后移植到C語(yǔ)言就是機(jī)械翻譯連變量名都能一一對(duì)應(yīng)。我后面給出的一段查表法代碼就幾乎可以直接照搬到嵌入式平臺(tái)上。2. 仿真程序的功能設(shè)計(jì)與模塊拆分2.1 程序整體要解決什么問(wèn)題這套仿真程序一開(kāi)始定下的目標(biāo)很明確輸入任意字節(jié)數(shù)組能輸出對(duì)應(yīng)的CRC校驗(yàn)碼接收端能通過(guò)重新計(jì)算校驗(yàn)碼來(lái)確認(rèn)數(shù)據(jù)是否被篡改同時(shí)支持人為翻轉(zhuǎn)數(shù)據(jù)比特用來(lái)演示CRC的檢錯(cuò)過(guò)程。圍繞這個(gè)目標(biāo)我把程序拆成了四個(gè)模塊模塊功能說(shuō)明對(duì)應(yīng)函數(shù)參數(shù)配置模塊設(shè)定生成多項(xiàng)式、初始值、結(jié)果異或值、是否反轉(zhuǎn)腳本頭部參數(shù)區(qū)CRC計(jì)算模塊實(shí)現(xiàn)逐位法和查表法兩種算法crc16_calc、crc_table函數(shù)收發(fā)鏈路模塊模擬發(fā)送端附加校驗(yàn)碼、接收端重新校驗(yàn)主腳本流程錯(cuò)誤注入模塊翻轉(zhuǎn)單個(gè)或多個(gè)比特測(cè)試檢錯(cuò)效果主腳本中的位操作這種拆法的好處是CRC計(jì)算函數(shù)是純算法不依賴任何外部環(huán)境拿出去就能復(fù)用到其他項(xiàng)目收發(fā)鏈路和錯(cuò)誤注入只是用來(lái)驗(yàn)證算法正確性的驅(qū)動(dòng)代碼。模塊之間通過(guò)函數(shù)接口隔離不會(huì)因?yàn)楦牧艘粋€(gè)地方的參數(shù)導(dǎo)致別的模塊跟著出問(wèn)題。2.2 為什么用函數(shù)封裝而不是一個(gè)腳本從頭寫到尾很多初學(xué)者喜歡把所有代碼堆在一個(gè)腳本里這樣跑起來(lái)確實(shí)快但一旦程序復(fù)雜起來(lái)就麻煩了。我這次特意把CRC計(jì)算封裝成獨(dú)立函數(shù)因?yàn)樵趯?shí)際工程里CRC計(jì)算往往要嵌入到不同的業(yè)務(wù)流程里比如上位機(jī)發(fā)送文件、下位機(jī)解析報(bào)文、存儲(chǔ)系統(tǒng)校驗(yàn)數(shù)據(jù)塊每個(gè)場(chǎng)景調(diào)用的方式都不一樣。把算法封裝成函數(shù)參數(shù)傳進(jìn)去、結(jié)果返回來(lái)完全不用關(guān)心內(nèi)部實(shí)現(xiàn)細(xì)節(jié)。另一個(gè)考慮是代碼復(fù)用。逐位法和查表法雖然算法思路不同但函數(shù)簽名可以保持一致這樣主腳本里只要換一行調(diào)用就能對(duì)比兩種算法的結(jié)果是否一致。函數(shù)封裝好了后面想再加CRC-32或者CRC-8只需要復(fù)制函數(shù)改幾個(gè)參數(shù)即可。3. 核心代碼實(shí)現(xiàn)與逐段講解3.1 先寫一個(gè)最直觀的逐位法非反射模型逐位法是最接近CRC原理的寫法每處理一個(gè)字節(jié)就把這個(gè)字節(jié)左移8位放到16位CRC寄存器的低8位上然后逐位判斷寄存器最高位是否為1如果是就左移一位后異或生成多項(xiàng)式否則只左移一位。這里用MATLAB實(shí)現(xiàn)有一個(gè)地方特別提醒MATLAB的位操作函數(shù)bitxor、bitshift、bitand默認(rèn)要求輸入是整數(shù)類型。如果你直接往函數(shù)里塞一個(gè)double類型運(yùn)算結(jié)果很可能不是你想要的。所以進(jìn)入函數(shù)后第一步就是把數(shù)據(jù)強(qiáng)制轉(zhuǎn)成uint16類型。function crc crc16_calc(data, poly, init) % 非反射模型MSB-first % data: 待計(jì)算CRC的字節(jié)數(shù)組uint16或double均可 % poly: 生成多項(xiàng)式例如0x8005 % init: CRC寄存器初始值 crc uint16(init); data uint16(data(:)); poly uint16(poly); for i 1:length(data) crc bitxor(crc, bitshift(data(i), 8)); for bit 1:8 if crc 32768 % 判斷最高位是否為1 crc bitxor(bitshift(crc, 1), poly); else crc bitshift(crc, 1); end end end end代碼里判斷最高位用crc 32768而不是bitand(crc, 0x8000)是因?yàn)閷?duì)uint16類型的變量來(lái)說(shuō)最高位是第15位從0開(kāi)始計(jì)這一位為1時(shí)數(shù)值必然大于等于32768。這樣寫避免了bitand函數(shù)里類型不匹配的麻煩邏輯也更清晰。函數(shù)跑完后返回的crc值就是CRC-16校驗(yàn)碼。但是要注意這個(gè)函數(shù)實(shí)現(xiàn)的是最簡(jiǎn)模型沒(méi)有做輸入反轉(zhuǎn)也沒(méi)有做結(jié)果異或所以它算出來(lái)的結(jié)果和某些協(xié)議標(biāo)準(zhǔn)里的CRC-16可能對(duì)不上。對(duì)不上不代表算法錯(cuò)了而是因?yàn)閰f(xié)議參數(shù)不同下一小節(jié)會(huì)細(xì)說(shuō)。3.2 查表法把8次循環(huán)換成1次查表逐位法雖然好懂但效率確實(shí)不高。每處理一個(gè)字節(jié)內(nèi)部要循環(huán)8次判斷處理1000個(gè)字節(jié)就要循環(huán)8000次。在MATLAB仿真里無(wú)所謂但到了單片機(jī)上這會(huì)白白消耗大量CPU時(shí)間。查表法的優(yōu)化思路很巧妙既然CRC計(jì)算就是對(duì)每個(gè)字節(jié)重復(fù)做“異或后左移”的操作而一個(gè)字節(jié)的取值范圍只有0到255共256種可能那不如預(yù)先算出這256種情況下CRC寄存器的變化值存成一張表。后面每次處理字節(jié)時(shí)用查表代替循環(huán)處理一個(gè)字節(jié)只需要幾次異或運(yùn)算。function table crc16_table_gen(poly) table zeros(256, 1, uint16); poly uint16(poly); for i 0:255 crc uint16(bitshift(i, 8)); for bit 1:8 if crc 32768 crc bitxor(bitshift(crc, 1), poly); else crc bitshift(crc, 1); end end table(i 1) crc; end end function crc crc16_table_calc(data, table, init) crc uint16(init); data uint16(data(:)); for i 1:length(data) idx double(bitxor(bitshift(crc, -8), data(i))) 1; crc bitxor(bitshift(crc, 8), table(idx)); end end這段代碼里有幾個(gè)細(xì)節(jié)非?？简?yàn)基本功。第一個(gè)細(xì)節(jié)是MATLAB的數(shù)組索引從1開(kāi)始而表的序號(hào)從0到255所以取表的時(shí)候idx必須加1。這個(gè)坑我當(dāng)年踩過(guò)用C語(yǔ)言的思維寫MATLAB代碼結(jié)果查表總是錯(cuò)一位最后打印中間值才發(fā)現(xiàn)索引問(wèn)題。第二個(gè)細(xì)節(jié)是表里的每一項(xiàng)代表“當(dāng)前字節(jié)對(duì)CRC寄存器的影響值”。計(jì)算時(shí)先取出CRC寄存器的高8位和當(dāng)前字節(jié)做異或得到一個(gè)0到255的索引值查表得到對(duì)應(yīng)的變換值再把CRC寄存器左移8位和這個(gè)變換值異或。這比逐位法少了一個(gè)內(nèi)層循環(huán)處理一個(gè)字節(jié)的時(shí)間基本固定性能提升非常明顯。第三個(gè)細(xì)節(jié)是double(...)強(qiáng)轉(zhuǎn)。因?yàn)閎itxor返回的是uint16直接加1再作為索引也沒(méi)有問(wèn)題但MATLAB偶爾會(huì)給提示干脆轉(zhuǎn)成double索引運(yùn)算更干凈。3.3 完整CRC模型初值、反轉(zhuǎn)、結(jié)果異或一個(gè)都不能少真正做項(xiàng)目時(shí)你會(huì)發(fā)現(xiàn)光是“CRC-16”這個(gè)名字根本沒(méi)法確定最終校驗(yàn)碼是什么。同樣是CRC-16MODBUS協(xié)議、CCITT協(xié)議、IBM協(xié)議算出來(lái)的結(jié)果完全不同原因就是參數(shù)表不同。一個(gè)完整的CRC模型需要五個(gè)參數(shù)多項(xiàng)式poly、初始值init、輸入反轉(zhuǎn)refin、輸出反轉(zhuǎn)refout、結(jié)果異或值xorout。以CRC-16/MODBUS為例它的完整模型是poly0x8005init0xFFFFrefintruerefouttruexorout0x0000。refin和refout為true意味著計(jì)算前對(duì)每個(gè)輸入字節(jié)按位反轉(zhuǎn)計(jì)算后對(duì)結(jié)果也按位反轉(zhuǎn)。這種看似很小的差別會(huì)讓最終校驗(yàn)碼天差地別。針對(duì)refin和refout為true的情況工程上有一個(gè)等價(jià)實(shí)現(xiàn)把整個(gè)算法反過(guò)來(lái)處理判斷最低位而不是最高位右移而不是左移多項(xiàng)式也要預(yù)先反轉(zhuǎn)。下面這段代碼就是CRC-16/MODBUS的完整實(shí)現(xiàn)也是最常見(jiàn)的反射算法function crc crc16_modbus(data) % CRC-16/MODBUS % poly0x8005, init0xFFFF, refintrue, refouttrue, xorout0x0000 poly uint16(0xA001); % 0x8005的位反轉(zhuǎn) crc uint16(0xFFFF); data uint16(data(:)); for i 1:length(data) crc bitxor(crc, data(i)); for bit 1:8 if bitand(crc, uint16(1)) % 判斷最低位 crc bitxor(bitshift(crc, -1), poly); else crc bitshift(crc, -1); end end end % xorout為0無(wú)需額外異或 end這段代碼的正確性驗(yàn)證很簡(jiǎn)單。網(wǎng)上公開(kāi)的CRC-16/MODBUS測(cè)試向量是對(duì)ASCII字符串“123456789”計(jì)算結(jié)果應(yīng)該是0x4B37。你在MATLAB命令行輸入以下代碼驗(yàn)證data uint16(123456789); crc crc16_modbus(data); fprintf(0x%04X\n, crc);如果能打印出0x4B37說(shuō)明參數(shù)沒(méi)配錯(cuò)。這也是我強(qiáng)烈建議的做事方式寫任何CRC代碼先找公開(kāi)測(cè)試向量驗(yàn)證別拿自己的數(shù)據(jù)盲測(cè)。測(cè)試向量都沒(méi)過(guò)的話后面全白搭。常見(jiàn)CRC模型參數(shù)如下表方便你對(duì)照調(diào)試協(xié)議名稱多項(xiàng)式初始值refinrefoutxoroutCRC-16/MODBUS0x80050xFFFFtruetrue0x0000CRC-16/CCITT0x10210xFFFFfalsefalse0x0000CRC-16/XMODEM0x10210x0000falsefalse0x0000CRC-320x04C11DB70xFFFFFFFFtruetrue0xFFFFFFFF4. 仿真驗(yàn)證從正確鏈路到錯(cuò)誤注入4.1 收發(fā)鏈路基線驗(yàn)證算法寫好了先別急著做花活第一件事是驗(yàn)證一條完全正確的數(shù)據(jù)鏈路能不能通過(guò)校驗(yàn)。這一步是用來(lái)確認(rèn)“CRC計(jì)算本身沒(méi)毛病”的。我寫了一個(gè)簡(jiǎn)單的主腳本發(fā)送端定義一組測(cè)試數(shù)據(jù)調(diào)用crc16_calc或crc16_table_calc算出校驗(yàn)碼然后模擬接收端拿到同樣的數(shù)據(jù)后再算一次兩次結(jié)果一致就打印“校驗(yàn)通過(guò)”。data uint16([0x01, 0x02, 0x03, 0x04, 0x05]); poly 0x8005; init 0x0000; table crc16_table_gen(poly); crc_tx crc16_table_calc(data, table, init); crc_rx crc16_table_calc(data, table, init); if crc_tx crc_rx disp(校驗(yàn)通過(guò)); else disp(校驗(yàn)失敗); end這個(gè)腳本跑通之后你可以順手做一個(gè)小實(shí)驗(yàn)把CRC校驗(yàn)碼按高字節(jié)在前、低字節(jié)在后的順序拼接在數(shù)據(jù)后面然后對(duì)“數(shù)據(jù)校驗(yàn)碼”整體重新計(jì)算一次CRC結(jié)果會(huì)變成0。這是CRC的一個(gè)數(shù)學(xué)性質(zhì)可以用來(lái)快速驗(yàn)證自己的拼接邏輯是否正確不過(guò)這個(gè)方法只適用于非反射模型反射模型要反過(guò)來(lái)拼。4.2 錯(cuò)誤注入模擬單比特翻轉(zhuǎn)和突發(fā)錯(cuò)誤鏈路驗(yàn)證通過(guò)接下來(lái)就該測(cè)試CRC的檢錯(cuò)能力了。真實(shí)通信鏈路里最常見(jiàn)的錯(cuò)誤有兩種單比特翻轉(zhuǎn)和突發(fā)錯(cuò)誤。單比特翻轉(zhuǎn)就是數(shù)據(jù)中某一個(gè)比特由0變成1或由1變成0突發(fā)錯(cuò)誤是連續(xù)幾個(gè)比特都被干擾比如電機(jī)啟動(dòng)瞬間串口收到的亂碼。在MATLAB里模擬這兩種情況非常方便data_correct uint16([0x01, 0x02, 0x03, 0x04, 0x05]); crc_original crc16_table_calc(data_correct, table, init); % 模擬單比特翻轉(zhuǎn)翻轉(zhuǎn)第3字節(jié)的第4位 data_error data_correct; data_error(3) bitxor(data_error(3), uint16(0x08)); crc_error crc16_table_calc(data_error, table, init); if crc_error crc_original disp(錯(cuò)誤未被檢出); else disp(單比特翻轉(zhuǎn)已被檢出); end % 模擬突發(fā)錯(cuò)誤連續(xù)翻轉(zhuǎn)第2字節(jié)到第4字節(jié)的部分比特 data_burst data_correct; data_burst(2) bitxor(data_burst(2), uint16(0xF0)); data_burst(3) bitxor(data_burst(3), uint16(0x3C)); data_burst(4) bitxor(data_burst(4), uint16(0x0F)); crc_burst crc16_table_calc(data_burst, table, init); if crc_burst crc_original disp(突發(fā)錯(cuò)誤未被檢出); else disp(突發(fā)錯(cuò)誤已被檢出); end運(yùn)行下來(lái)你會(huì)發(fā)現(xiàn)CRC對(duì)這兩種錯(cuò)誤基本都能檢出來(lái)。原因在于模2除法的數(shù)學(xué)特性只要錯(cuò)誤多項(xiàng)式不是生成多項(xiàng)式的倍數(shù)余數(shù)就不為零最終CRC值就會(huì)變化。CRC能檢測(cè)所有單比特錯(cuò)誤、所有雙比特錯(cuò)誤、所有奇數(shù)個(gè)錯(cuò)誤以及所有長(zhǎng)度不超過(guò)校驗(yàn)位寬度的突發(fā)錯(cuò)誤。但要注意CRC不是萬(wàn)能的如果錯(cuò)誤多項(xiàng)式恰好是生成多項(xiàng)式的整數(shù)倍CRC值就會(huì)陰差陽(yáng)錯(cuò)地保持一致這就是所謂“漏檢”。雖然概率很低但你心里得有個(gè)數(shù)。4.3 用測(cè)試向量校準(zhǔn)協(xié)議參數(shù)在調(diào)試真實(shí)項(xiàng)目時(shí)還會(huì)遇到一種情況CRC代碼邏輯完全正確但和對(duì)方的協(xié)議對(duì)不上。這種問(wèn)題八成是參數(shù)表不匹配。我在幫一個(gè)朋友調(diào)MODBUS-RTU通信時(shí)就發(fā)現(xiàn)他代碼里用的多項(xiàng)式是0x8005但初始值寫成了0x0000而MODBUS標(biāo)準(zhǔn)要求init0xFFFF。結(jié)果就是通信雙方都以為自己在算CRC可算出來(lái)的校驗(yàn)碼永遠(yuǎn)對(duì)不上。解決辦法是先找一個(gè)權(quán)威的在線CRC計(jì)算工具或者用公開(kāi)的測(cè)試向量校準(zhǔn)自己的代碼。我測(cè)試CRC-16/MODBUS通用做法就是直接跑“123456789”這個(gè)向量一旦輸出0x4B37就說(shuō)明參數(shù)全對(duì)接下來(lái)再去查業(yè)務(wù)層邏輯。5. 常見(jiàn)問(wèn)題與踩坑實(shí)錄5.1 結(jié)果和參考工具不一致怎么辦這是被問(wèn)得最多的問(wèn)題。拿到一個(gè)參考CRC結(jié)果用自己程序算出來(lái)不一樣第一反應(yīng)別急著怪算法先核對(duì)五個(gè)參數(shù)多項(xiàng)式、初始值、輸入反轉(zhuǎn)、輸出反轉(zhuǎn)、結(jié)果異或。五個(gè)參數(shù)里只要有一個(gè)不一樣結(jié)果肯定不一樣。還有個(gè)隱蔽問(wèn)題有些資料里多項(xiàng)式會(huì)省略最高位的1。以CRC-16為例完整多項(xiàng)式是x^16 x^15 x^2 1寫作二進(jìn)制是1 1000 0000 0000 0101最高位這個(gè)1是固定的十六進(jìn)制就是0x18005。但實(shí)際使用時(shí)因?yàn)樽罡呶粎⑴c運(yùn)算最后一定被消掉所以很多資料直接寫0x8005。如果你看到0x8005和0x18005別慌它們是同一個(gè)多項(xiàng)式。5.2 下載或解壓時(shí)遇到的7-zip CRC error很多人在搜CRC相關(guān)資料時(shí)會(huì)搜到“安裝顯卡驅(qū)動(dòng)提示7-zip CRC error”這類問(wèn)題。這里多說(shuō)一句7-Zip在解壓時(shí)也會(huì)用CRC校驗(yàn)來(lái)確認(rèn)壓縮包是否完整如果解壓時(shí)報(bào)出CRC error通常意味著壓縮包下載不完整、存儲(chǔ)介質(zhì)有壞道或者內(nèi)存不穩(wěn)定導(dǎo)致數(shù)據(jù)讀取出錯(cuò)。解決辦法一般是重新下載安裝包或者換一個(gè)鏡像源下載順便檢查一下硬盤和內(nèi)存。這也說(shuō)明CRC在文件完整性校驗(yàn)中的應(yīng)用遠(yuǎn)比我們?nèi)粘ｊP(guān)注到的要廣泛。5.3 MATLAB位操作的數(shù)據(jù)類型坑MATLAB的位操作函數(shù)對(duì)數(shù)據(jù)類型極其敏感。bitxor(uint16(1), double(1))這種寫法會(huì)直接報(bào)錯(cuò)提示兩個(gè)輸入類型不一致。所以寫MATLAB的CRC代碼一定要養(yǎng)成“所有參與位操作的數(shù)據(jù)先統(tǒng)一轉(zhuǎn)成uint16或uint32”的習(xí)慣。另外bitshift對(duì)于無(wú)符號(hào)整數(shù)的“溢出”處理是靜默截?cái)?。比如bitshift(uint16(0xFFFF), 1)的結(jié)果不是0x1FFFE而是0xFFFE高位丟掉了。這個(gè)行為在CRC算法里其實(shí)正是我們需要的因?yàn)樽笠坪笞罡呶槐緛?lái)就不參與計(jì)算但如果你沒(méi)意識(shí)到這一點(diǎn)中間調(diào)試時(shí)會(huì)暈頭轉(zhuǎn)向。這里建議你打印每一輪循環(huán)的crc值親眼看一下數(shù)據(jù)變化規(guī)律跑通一遍之后CRC在腦子里就不再是抽象公式了。5.4 查表法索引錯(cuò)位前面提到過(guò)MATLAB數(shù)組下標(biāo)從1開(kāi)始而查表法的索引是從0開(kāi)始。把C語(yǔ)言代碼翻譯成MATLAB時(shí)這個(gè)差異最容易引發(fā)bug。我在代碼里專門用了idx double(bitxor(bitshift(crc, -8), data(i))) 1就是為了把索引從0到255映射到1到256。如果你得到的CRC結(jié)果忽大忽小而且明顯沒(méi)有規(guī)律優(yōu)先檢查這一行是不是少了加1。還有個(gè)相關(guān)細(xì)節(jié)bitshift(crc, -8)對(duì)uint16類型是右移8位得到的是高8位值范圍0到255和當(dāng)前字節(jié)異或后也還是0到255所以索引是安全的。6. 個(gè)人使用心得與后續(xù)擴(kuò)展建議這個(gè)MATLAB CRC仿真程序我陸陸續(xù)續(xù)用了一年多從最初的逐位法到后來(lái)的查表法再到支持refin/refout的完整模型每次迭代都讓我對(duì)CRC的認(rèn)識(shí)更深一層。我最大的體會(huì)是CRC這個(gè)技術(shù)看起來(lái)“老”但它在串口通信、以太網(wǎng)幀校驗(yàn)、NFV文件系統(tǒng)完整性校驗(yàn)里都是底層基石值得花時(shí)間把原理徹底搞透。如果你想把這套仿真真正用到自己的項(xiàng)目里我建議你往兩個(gè)方向擴(kuò)展。第一個(gè)方向是增加多協(xié)議支持?，F(xiàn)在函數(shù)里寫死了16位寬度你可以把crc16_calc改成通用的參數(shù)化函數(shù)傳入poly、init、refin、refout、xorout寬度也作為參數(shù)這樣CRC-8、CRC-16、CRC-32一套代碼全搞定。第二個(gè)方向是自動(dòng)做錯(cuò)誤注入統(tǒng)計(jì)。我現(xiàn)在會(huì)寫一個(gè)循環(huán)隨機(jī)翻轉(zhuǎn)數(shù)據(jù)里的多個(gè)比特統(tǒng)計(jì)CRC成功檢出的次數(shù)和漏檢次數(shù)用來(lái)評(píng)估不同生成多項(xiàng)式的檢錯(cuò)能力。這個(gè)對(duì)比實(shí)驗(yàn)在做協(xié)議設(shè)計(jì)時(shí)很實(shí)用可以驗(yàn)證自己選的多項(xiàng)式是否靠譜。最后再分享一個(gè)調(diào)試技巧無(wú)論你用什么語(yǔ)言寫CRC第一版代碼一定要先跑公開(kāi)測(cè)試向量別拿自己的業(yè)務(wù)數(shù)據(jù)試。業(yè)務(wù)數(shù)據(jù)出錯(cuò)了你不知道是算法問(wèn)題還是參數(shù)問(wèn)題而測(cè)試向量能幫你把算法和參數(shù)一次性隔離出來(lái)。這個(gè)習(xí)慣幫我節(jié)省了大量排查時(shí)間今天也一并寫在這里。本文還有配套的精品資源點(diǎn)擊獲取 CRC校驗(yàn)原理與MATLAB仿真：從逐位法到查表法全解析
簡(jiǎn)介這是一份基于MATLAB環(huán)境的CRC循環(huán)冗余校驗(yàn)仿真程序包面向通信工程、數(shù)據(jù)存儲(chǔ)及嵌入式方向的初學(xué)者與研發(fā)人員用于解決數(shù)據(jù)傳輸完整性校驗(yàn)的原理理解與仿真實(shí)現(xiàn)問(wèn)題。資源共包含4個(gè)M文件涵蓋主程序、編碼函數(shù)、解碼函數(shù)與完整校驗(yàn)流程壓縮包僅2KB代碼精簡(jiǎn)便于逐行閱讀與二次擴(kuò)展。程序圍繞生成多項(xiàng)式、預(yù)處理左移、模2除法及余數(shù)校驗(yàn)等核心步驟展開(kāi)并給出了從原始數(shù)據(jù)附加校驗(yàn)碼、發(fā)送、接收端再次相除并判定余數(shù)是否為零的完整鏈路同時(shí)支持人為翻轉(zhuǎn)比特位模擬信道干擾直觀檢驗(yàn)CRC的檢錯(cuò)能力。除常規(guī)生成、添加與驗(yàn)證流程外也可對(duì)照代碼分析不同生成多項(xiàng)式對(duì)檢錯(cuò)效果的影響適合串聯(lián)起《通信原理》《計(jì)算機(jī)網(wǎng)絡(luò)》課程實(shí)驗(yàn)與畢業(yè)設(shè)計(jì)。已有940人學(xué)習(xí)下載對(duì)于希望快速掌握CRC算法并完成MATLAB仿真的讀者是一份輕量而實(shí)用的參考資料。 做通信和嵌入式調(diào)試的朋友應(yīng)該都遇到過(guò)這個(gè)場(chǎng)景串口收到一包數(shù)據(jù)沒(méi)人敢保證這包數(shù)據(jù)在傳輸過(guò)程中沒(méi)被干擾過(guò)固件升級(jí)文件拷貝到一半也沒(méi)人能肉眼看出文件是不是少了幾字節(jié)。CRC循環(huán)冗余校驗(yàn)就是用來(lái)解決這類問(wèn)題的經(jīng)典方案也是我這些年調(diào)試鏈路、設(shè)計(jì)通信協(xié)議時(shí)用得最多的校驗(yàn)手段之一。之前我整理過(guò)一個(gè)基于MATLAB的CRC仿真程序把CRC-8、CRC-16、CRC-32的生成、拼接、校驗(yàn)、錯(cuò)誤注入全都在一個(gè)腳本里跑通了。這篇文章就把這個(gè)仿真程序的設(shè)計(jì)思路、完整代碼和踩過(guò)的坑拆開(kāi)講適合做通信、嵌入式、上位機(jī)開(kāi)發(fā)的工程師也適合正在學(xué)數(shù)據(jù)鏈路層課程但被教材繞暈的在校生。這套仿真最大的價(jià)值在于先用MATLAB把算法和協(xié)議參數(shù)驗(yàn)證清楚等邏輯完全沒(méi)問(wèn)題了再往C語(yǔ)言、Verilog或者單片機(jī)上移植可以省掉大量在硬件上反復(fù)燒錄調(diào)試的時(shí)間。下面從原理開(kāi)始一步步帶你搭一個(gè)能跑的CRC仿真環(huán)境。1. 項(xiàng)目整體思路為什么需要CRC為什么用MATLAB1.1 校驗(yàn)的本質(zhì)給數(shù)據(jù)加一道“冗余保險(xiǎn)”任何校驗(yàn)算法本質(zhì)上干的都是同一件事發(fā)送端在有效數(shù)據(jù)后面附加一段冗余信息這段冗余信息由原始數(shù)據(jù)通過(guò)某種規(guī)則計(jì)算得出接收端拿到完整數(shù)據(jù)后用同樣的規(guī)則重新計(jì)算再把計(jì)算結(jié)果和收到的冗余信息對(duì)比一致就認(rèn)為數(shù)據(jù)沒(méi)問(wèn)題不一致就說(shuō)明傳輸過(guò)程中發(fā)生了錯(cuò)誤。這就像寄快遞時(shí)發(fā)件人會(huì)在包裹上貼一張寫了重量的標(biāo)簽。收件人收到快遞后如果把包裹放到秤上一稱重量和標(biāo)簽對(duì)不上就知道包裹要么在半路被調(diào)包了要么內(nèi)部東西壞了。不過(guò)“重量校驗(yàn)”太粗糙了數(shù)據(jù)包里哪怕只翻轉(zhuǎn)了一個(gè)比特如果剛好有另一個(gè)比特也跟著翻轉(zhuǎn)總量可能不變這就會(huì)出現(xiàn)漏檢。CRC比這種簡(jiǎn)單校驗(yàn)強(qiáng)的地方在于它不是簡(jiǎn)單加和而是把數(shù)據(jù)當(dāng)成一個(gè)大的二進(jìn)制數(shù)通過(guò)多項(xiàng)式除法把錯(cuò)誤特征“攤開(kāi)”到整個(gè)數(shù)據(jù)長(zhǎng)度上單比特翻轉(zhuǎn)、雙比特翻轉(zhuǎn)這類常見(jiàn)錯(cuò)誤基本都能抓住。1.2 CRC的數(shù)學(xué)原理二進(jìn)制多項(xiàng)式除法CRC的全稱是Cyclic Redundancy Check核心思想聽(tīng)起來(lái)有點(diǎn)嚇人其實(shí)拆開(kāi)了很簡(jiǎn)單。把待發(fā)送的數(shù)據(jù)看成一個(gè)二進(jìn)制多項(xiàng)式比如字節(jié)0x0B二進(jìn)制00001011可以對(duì)應(yīng)成多項(xiàng)式“x^3 x 1”。發(fā)送端把這個(gè)數(shù)據(jù)多項(xiàng)式左移r位r是校驗(yàn)位寬度然后除以一個(gè)發(fā)送端和接收端約定好的“生成多項(xiàng)式”取余數(shù)這個(gè)余數(shù)就是CRC校驗(yàn)碼。這里的除法不是普通十進(jìn)制除法而是模2除法說(shuō)人話就是按位異或。整個(gè)過(guò)程只有0和1的異或運(yùn)算沒(méi)有進(jìn)位也沒(méi)有借位。因?yàn)檫\(yùn)算規(guī)則簡(jiǎn)單硬件上只需要移位寄存器和異或門就能實(shí)現(xiàn)這也是CRC在串口通信、網(wǎng)卡、存儲(chǔ)設(shè)備里被用了這么多年依然不過(guò)時(shí)的原因。生成多項(xiàng)式的選擇很有講究常見(jiàn)的CRC-8、CRC-16、CRC-32都有標(biāo)準(zhǔn)定義。比如CRC-16常用的多項(xiàng)式0x8005寫成二進(jìn)制就是“1000 0000 0000 0101”代表“x^16 x^15 x^2 1”。選用標(biāo)準(zhǔn)多項(xiàng)式的好處是檢錯(cuò)能力經(jīng)過(guò)充分驗(yàn)證而且不同設(shè)備之間能互相兼容。我自己見(jiàn)過(guò)不少人在實(shí)際項(xiàng)目里自己“發(fā)明”多項(xiàng)式結(jié)果檢錯(cuò)效果一塌糊涂這個(gè)問(wèn)題后面專門說(shuō)。1.3 為什么選MATLAB做仿真而不是直接上單片機(jī)做CRC校驗(yàn)最后肯定要落到C語(yǔ)言或者硬件電路里但在起步階段用MATLAB做仿真有三個(gè)明顯優(yōu)勢(shì)。第一個(gè)優(yōu)勢(shì)是調(diào)試直觀。MATLAB里數(shù)組、矩陣、位操作都是原生支持變量值隨時(shí)可以在工作區(qū)點(diǎn)開(kāi)看還能用disp直接打印每步的中間結(jié)果。相比之下C語(yǔ)言里面做位操作得時(shí)刻小心數(shù)據(jù)類型溢出、無(wú)符號(hào)整型的移位方向調(diào)試起來(lái)心智負(fù)擔(dān)重很多。第二個(gè)優(yōu)勢(shì)是測(cè)試方便。MATLAB寫腳本不需要交叉編譯不需要下載到板子改一行代碼立刻能看到結(jié)果。做錯(cuò)誤注入實(shí)驗(yàn)時(shí)只要用bitxor把數(shù)據(jù)里的某幾個(gè)比特翻轉(zhuǎn)一下就能快速驗(yàn)證CRC的檢錯(cuò)能力這在硬件環(huán)境里做要麻煩得多。第三個(gè)優(yōu)勢(shì)是知識(shí)遷移容易。把MATLAB里的算法邏輯理清楚之后移植到C語(yǔ)言就是機(jī)械翻譯連變量名都能一一對(duì)應(yīng)。我后面給出的一段查表法代碼就幾乎可以直接照搬到嵌入式平臺(tái)上。2. 仿真程序的功能設(shè)計(jì)與模塊拆分2.1 程序整體要解決什么問(wèn)題這套仿真程序一開(kāi)始定下的目標(biāo)很明確輸入任意字節(jié)數(shù)組能輸出對(duì)應(yīng)的CRC校驗(yàn)碼接收端能通過(guò)重新計(jì)算校驗(yàn)碼來(lái)確認(rèn)數(shù)據(jù)是否被篡改同時(shí)支持人為翻轉(zhuǎn)數(shù)據(jù)比特用來(lái)演示CRC的檢錯(cuò)過(guò)程。圍繞這個(gè)目標(biāo)我把程序拆成了四個(gè)模塊模塊功能說(shuō)明對(duì)應(yīng)函數(shù)參數(shù)配置模塊設(shè)定生成多項(xiàng)式、初始值、結(jié)果異或值、是否反轉(zhuǎn)腳本頭部參數(shù)區(qū)CRC計(jì)算模塊實(shí)現(xiàn)逐位法和查表法兩種算法crc16_calc、crc_table函數(shù)收發(fā)鏈路模塊模擬發(fā)送端附加校驗(yàn)碼、接收端重新校驗(yàn)主腳本流程錯(cuò)誤注入模塊翻轉(zhuǎn)單個(gè)或多個(gè)比特測(cè)試檢錯(cuò)效果主腳本中的位操作這種拆法的好處是CRC計(jì)算函數(shù)是純算法不依賴任何外部環(huán)境拿出去就能復(fù)用到其他項(xiàng)目收發(fā)鏈路和錯(cuò)誤注入只是用來(lái)驗(yàn)證算法正確性的驅(qū)動(dòng)代碼。模塊之間通過(guò)函數(shù)接口隔離不會(huì)因?yàn)楦牧艘粋€(gè)地方的參數(shù)導(dǎo)致別的模塊跟著出問(wèn)題。2.2 為什么用函數(shù)封裝而不是一個(gè)腳本從頭寫到尾很多初學(xué)者喜歡把所有代碼堆在一個(gè)腳本里這樣跑起來(lái)確實(shí)快但一旦程序復(fù)雜起來(lái)就麻煩了。我這次特意把CRC計(jì)算封裝成獨(dú)立函數(shù)因?yàn)樵趯?shí)際工程里CRC計(jì)算往往要嵌入到不同的業(yè)務(wù)流程里比如上位機(jī)發(fā)送文件、下位機(jī)解析報(bào)文、存儲(chǔ)系統(tǒng)校驗(yàn)數(shù)據(jù)塊每個(gè)場(chǎng)景調(diào)用的方式都不一樣。把算法封裝成函數(shù)參數(shù)傳進(jìn)去、結(jié)果返回來(lái)完全不用關(guān)心內(nèi)部實(shí)現(xiàn)細(xì)節(jié)。另一個(gè)考慮是代碼復(fù)用。逐位法和查表法雖然算法思路不同但函數(shù)簽名可以保持一致這樣主腳本里只要換一行調(diào)用就能對(duì)比兩種算法的結(jié)果是否一致。函數(shù)封裝好了后面想再加CRC-32或者CRC-8只需要復(fù)制函數(shù)改幾個(gè)參數(shù)即可。3. 核心代碼實(shí)現(xiàn)與逐段講解3.1 先寫一個(gè)最直觀的逐位法非反射模型逐位法是最接近CRC原理的寫法每處理一個(gè)字節(jié)就把這個(gè)字節(jié)左移8位放到16位CRC寄存器的低8位上然后逐位判斷寄存器最高位是否為1如果是就左移一位后異或生成多項(xiàng)式否則只左移一位。這里用MATLAB實(shí)現(xiàn)有一個(gè)地方特別提醒MATLAB的位操作函數(shù)bitxor、bitshift、bitand默認(rèn)要求輸入是整數(shù)類型。如果你直接往函數(shù)里塞一個(gè)double類型運(yùn)算結(jié)果很可能不是你想要的。所以進(jìn)入函數(shù)后第一步就是把數(shù)據(jù)強(qiáng)制轉(zhuǎn)成uint16類型。function crc crc16_calc(data, poly, init) % 非反射模型MSB-first % data: 待計(jì)算CRC的字節(jié)數(shù)組uint16或double均可 % poly: 生成多項(xiàng)式例如0x8005 % init: CRC寄存器初始值 crc uint16(init); data uint16(data(:)); poly uint16(poly); for i 1:length(data) crc bitxor(crc, bitshift(data(i), 8)); for bit 1:8 if crc 32768 % 判斷最高位是否為1 crc bitxor(bitshift(crc, 1), poly); else crc bitshift(crc, 1); end end end end代碼里判斷最高位用crc 32768而不是bitand(crc, 0x8000)是因?yàn)閷?duì)uint16類型的變量來(lái)說(shuō)最高位是第15位從0開(kāi)始計(jì)這一位為1時(shí)數(shù)值必然大于等于32768。這樣寫避免了bitand函數(shù)里類型不匹配的麻煩邏輯也更清晰。函數(shù)跑完后返回的crc值就是CRC-16校驗(yàn)碼。但是要注意這個(gè)函數(shù)實(shí)現(xiàn)的是最簡(jiǎn)模型沒(méi)有做輸入反轉(zhuǎn)也沒(méi)有做結(jié)果異或所以它算出來(lái)的結(jié)果和某些協(xié)議標(biāo)準(zhǔn)里的CRC-16可能對(duì)不上。對(duì)不上不代表算法錯(cuò)了而是因?yàn)閰f(xié)議參數(shù)不同下一小節(jié)會(huì)細(xì)說(shuō)。3.2 查表法把8次循環(huán)換成1次查表逐位法雖然好懂但效率確實(shí)不高。每處理一個(gè)字節(jié)內(nèi)部要循環(huán)8次判斷處理1000個(gè)字節(jié)就要循環(huán)8000次。在MATLAB仿真里無(wú)所謂但到了單片機(jī)上這會(huì)白白消耗大量CPU時(shí)間。查表法的優(yōu)化思路很巧妙既然CRC計(jì)算就是對(duì)每個(gè)字節(jié)重復(fù)做“異或后左移”的操作而一個(gè)字節(jié)的取值范圍只有0到255共256種可能那不如預(yù)先算出這256種情況下CRC寄存器的變化值存成一張表。后面每次處理字節(jié)時(shí)用查表代替循環(huán)處理一個(gè)字節(jié)只需要幾次異或運(yùn)算。function table crc16_table_gen(poly) table zeros(256, 1, uint16); poly uint16(poly); for i 0:255 crc uint16(bitshift(i, 8)); for bit 1:8 if crc 32768 crc bitxor(bitshift(crc, 1), poly); else crc bitshift(crc, 1); end end table(i 1) crc; end end function crc crc16_table_calc(data, table, init) crc uint16(init); data uint16(data(:)); for i 1:length(data) idx double(bitxor(bitshift(crc, -8), data(i))) 1; crc bitxor(bitshift(crc, 8), table(idx)); end end這段代碼里有幾個(gè)細(xì)節(jié)非?？简?yàn)基本功。第一個(gè)細(xì)節(jié)是MATLAB的數(shù)組索引從1開(kāi)始而表的序號(hào)從0到255所以取表的時(shí)候idx必須加1。這個(gè)坑我當(dāng)年踩過(guò)用C語(yǔ)言的思維寫MATLAB代碼結(jié)果查表總是錯(cuò)一位最后打印中間值才發(fā)現(xiàn)索引問(wèn)題。第二個(gè)細(xì)節(jié)是表里的每一項(xiàng)代表“當(dāng)前字節(jié)對(duì)CRC寄存器的影響值”。計(jì)算時(shí)先取出CRC寄存器的高8位和當(dāng)前字節(jié)做異或得到一個(gè)0到255的索引值查表得到對(duì)應(yīng)的變換值再把CRC寄存器左移8位和這個(gè)變換值異或。這比逐位法少了一個(gè)內(nèi)層循環(huán)處理一個(gè)字節(jié)的時(shí)間基本固定性能提升非常明顯。第三個(gè)細(xì)節(jié)是double(...)強(qiáng)轉(zhuǎn)。因?yàn)閎itxor返回的是uint16直接加1再作為索引也沒(méi)有問(wèn)題但MATLAB偶爾會(huì)給提示干脆轉(zhuǎn)成double索引運(yùn)算更干凈。3.3 完整CRC模型初值、反轉(zhuǎn)、結(jié)果異或一個(gè)都不能少真正做項(xiàng)目時(shí)你會(huì)發(fā)現(xiàn)光是“CRC-16”這個(gè)名字根本沒(méi)法確定最終校驗(yàn)碼是什么。同樣是CRC-16MODBUS協(xié)議、CCITT協(xié)議、IBM協(xié)議算出來(lái)的結(jié)果完全不同原因就是參數(shù)表不同。一個(gè)完整的CRC模型需要五個(gè)參數(shù)多項(xiàng)式poly、初始值init、輸入反轉(zhuǎn)refin、輸出反轉(zhuǎn)refout、結(jié)果異或值xorout。以CRC-16/MODBUS為例它的完整模型是poly0x8005init0xFFFFrefintruerefouttruexorout0x0000。refin和refout為true意味著計(jì)算前對(duì)每個(gè)輸入字節(jié)按位反轉(zhuǎn)計(jì)算后對(duì)結(jié)果也按位反轉(zhuǎn)。這種看似很小的差別會(huì)讓最終校驗(yàn)碼天差地別。針對(duì)refin和refout為true的情況工程上有一個(gè)等價(jià)實(shí)現(xiàn)把整個(gè)算法反過(guò)來(lái)處理判斷最低位而不是最高位右移而不是左移多項(xiàng)式也要預(yù)先反轉(zhuǎn)。下面這段代碼就是CRC-16/MODBUS的完整實(shí)現(xiàn)也是最常見(jiàn)的反射算法function crc crc16_modbus(data) % CRC-16/MODBUS % poly0x8005, init0xFFFF, refintrue, refouttrue, xorout0x0000 poly uint16(0xA001); % 0x8005的位反轉(zhuǎn) crc uint16(0xFFFF); data uint16(data(:)); for i 1:length(data) crc bitxor(crc, data(i)); for bit 1:8 if bitand(crc, uint16(1)) % 判斷最低位 crc bitxor(bitshift(crc, -1), poly); else crc bitshift(crc, -1); end end end % xorout為0無(wú)需額外異或 end這段代碼的正確性驗(yàn)證很簡(jiǎn)單。網(wǎng)上公開(kāi)的CRC-16/MODBUS測(cè)試向量是對(duì)ASCII字符串“123456789”計(jì)算結(jié)果應(yīng)該是0x4B37。你在MATLAB命令行輸入以下代碼驗(yàn)證data uint16(123456789); crc crc16_modbus(data); fprintf(0x%04X\n, crc);如果能打印出0x4B37說(shuō)明參數(shù)沒(méi)配錯(cuò)。這也是我強(qiáng)烈建議的做事方式寫任何CRC代碼先找公開(kāi)測(cè)試向量驗(yàn)證別拿自己的數(shù)據(jù)盲測(cè)。測(cè)試向量都沒(méi)過(guò)的話后面全白搭。常見(jiàn)CRC模型參數(shù)如下表方便你對(duì)照調(diào)試協(xié)議名稱多項(xiàng)式初始值refinrefoutxoroutCRC-16/MODBUS0x80050xFFFFtruetrue0x0000CRC-16/CCITT0x10210xFFFFfalsefalse0x0000CRC-16/XMODEM0x10210x0000falsefalse0x0000CRC-320x04C11DB70xFFFFFFFFtruetrue0xFFFFFFFF4. 仿真驗(yàn)證從正確鏈路到錯(cuò)誤注入4.1 收發(fā)鏈路基線驗(yàn)證算法寫好了先別急著做花活第一件事是驗(yàn)證一條完全正確的數(shù)據(jù)鏈路能不能通過(guò)校驗(yàn)。這一步是用來(lái)確認(rèn)“CRC計(jì)算本身沒(méi)毛病”的。我寫了一個(gè)簡(jiǎn)單的主腳本發(fā)送端定義一組測(cè)試數(shù)據(jù)調(diào)用crc16_calc或crc16_table_calc算出校驗(yàn)碼然后模擬接收端拿到同樣的數(shù)據(jù)后再算一次兩次結(jié)果一致就打印“校驗(yàn)通過(guò)”。data uint16([0x01, 0x02, 0x03, 0x04, 0x05]); poly 0x8005; init 0x0000; table crc16_table_gen(poly); crc_tx crc16_table_calc(data, table, init); crc_rx crc16_table_calc(data, table, init); if crc_tx crc_rx disp(校驗(yàn)通過(guò)); else disp(校驗(yàn)失敗); end這個(gè)腳本跑通之后你可以順手做一個(gè)小實(shí)驗(yàn)把CRC校驗(yàn)碼按高字節(jié)在前、低字節(jié)在后的順序拼接在數(shù)據(jù)后面然后對(duì)“數(shù)據(jù)校驗(yàn)碼”整體重新計(jì)算一次CRC結(jié)果會(huì)變成0。這是CRC的一個(gè)數(shù)學(xué)性質(zhì)可以用來(lái)快速驗(yàn)證自己的拼接邏輯是否正確不過(guò)這個(gè)方法只適用于非反射模型反射模型要反過(guò)來(lái)拼。4.2 錯(cuò)誤注入模擬單比特翻轉(zhuǎn)和突發(fā)錯(cuò)誤鏈路驗(yàn)證通過(guò)接下來(lái)就該測(cè)試CRC的檢錯(cuò)能力了。真實(shí)通信鏈路里最常見(jiàn)的錯(cuò)誤有兩種單比特翻轉(zhuǎn)和突發(fā)錯(cuò)誤。單比特翻轉(zhuǎn)就是數(shù)據(jù)中某一個(gè)比特由0變成1或由1變成0突發(fā)錯(cuò)誤是連續(xù)幾個(gè)比特都被干擾比如電機(jī)啟動(dòng)瞬間串口收到的亂碼。在MATLAB里模擬這兩種情況非常方便data_correct uint16([0x01, 0x02, 0x03, 0x04, 0x05]); crc_original crc16_table_calc(data_correct, table, init); % 模擬單比特翻轉(zhuǎn)翻轉(zhuǎn)第3字節(jié)的第4位 data_error data_correct; data_error(3) bitxor(data_error(3), uint16(0x08)); crc_error crc16_table_calc(data_error, table, init); if crc_error crc_original disp(錯(cuò)誤未被檢出); else disp(單比特翻轉(zhuǎn)已被檢出); end % 模擬突發(fā)錯(cuò)誤連續(xù)翻轉(zhuǎn)第2字節(jié)到第4字節(jié)的部分比特 data_burst data_correct; data_burst(2) bitxor(data_burst(2), uint16(0xF0)); data_burst(3) bitxor(data_burst(3), uint16(0x3C)); data_burst(4) bitxor(data_burst(4), uint16(0x0F)); crc_burst crc16_table_calc(data_burst, table, init); if crc_burst crc_original disp(突發(fā)錯(cuò)誤未被檢出); else disp(突發(fā)錯(cuò)誤已被檢出); end運(yùn)行下來(lái)你會(huì)發(fā)現(xiàn)CRC對(duì)這兩種錯(cuò)誤基本都能檢出來(lái)。原因在于模2除法的數(shù)學(xué)特性只要錯(cuò)誤多項(xiàng)式不是生成多項(xiàng)式的倍數(shù)余數(shù)就不為零最終CRC值就會(huì)變化。CRC能檢測(cè)所有單比特錯(cuò)誤、所有雙比特錯(cuò)誤、所有奇數(shù)個(gè)錯(cuò)誤以及所有長(zhǎng)度不超過(guò)校驗(yàn)位寬度的突發(fā)錯(cuò)誤。但要注意CRC不是萬(wàn)能的如果錯(cuò)誤多項(xiàng)式恰好是生成多項(xiàng)式的整數(shù)倍CRC值就會(huì)陰差陽(yáng)錯(cuò)地保持一致這就是所謂“漏檢”。雖然概率很低但你心里得有個(gè)數(shù)。4.3 用測(cè)試向量校準(zhǔn)協(xié)議參數(shù)在調(diào)試真實(shí)項(xiàng)目時(shí)還會(huì)遇到一種情況CRC代碼邏輯完全正確但和對(duì)方的協(xié)議對(duì)不上。這種問(wèn)題八成是參數(shù)表不匹配。我在幫一個(gè)朋友調(diào)MODBUS-RTU通信時(shí)就發(fā)現(xiàn)他代碼里用的多項(xiàng)式是0x8005但初始值寫成了0x0000而MODBUS標(biāo)準(zhǔn)要求init0xFFFF。結(jié)果就是通信雙方都以為自己在算CRC可算出來(lái)的校驗(yàn)碼永遠(yuǎn)對(duì)不上。解決辦法是先找一個(gè)權(quán)威的在線CRC計(jì)算工具或者用公開(kāi)的測(cè)試向量校準(zhǔn)自己的代碼。我測(cè)試CRC-16/MODBUS通用做法就是直接跑“123456789”這個(gè)向量一旦輸出0x4B37就說(shuō)明參數(shù)全對(duì)接下來(lái)再去查業(yè)務(wù)層邏輯。5. 常見(jiàn)問(wèn)題與踩坑實(shí)錄5.1 結(jié)果和參考工具不一致怎么辦這是被問(wèn)得最多的問(wèn)題。拿到一個(gè)參考CRC結(jié)果用自己程序算出來(lái)不一樣第一反應(yīng)別急著怪算法先核對(duì)五個(gè)參數(shù)多項(xiàng)式、初始值、輸入反轉(zhuǎn)、輸出反轉(zhuǎn)、結(jié)果異或。五個(gè)參數(shù)里只要有一個(gè)不一樣結(jié)果肯定不一樣。還有個(gè)隱蔽問(wèn)題有些資料里多項(xiàng)式會(huì)省略最高位的1。以CRC-16為例完整多項(xiàng)式是x^16 x^15 x^2 1寫作二進(jìn)制是1 1000 0000 0000 0101最高位這個(gè)1是固定的十六進(jìn)制就是0x18005。但實(shí)際使用時(shí)因?yàn)樽罡呶粎⑴c運(yùn)算最后一定被消掉所以很多資料直接寫0x8005。如果你看到0x8005和0x18005別慌它們是同一個(gè)多項(xiàng)式。5.2 下載或解壓時(shí)遇到的7-zip CRC error很多人在搜CRC相關(guān)資料時(shí)會(huì)搜到“安裝顯卡驅(qū)動(dòng)提示7-zip CRC error”這類問(wèn)題。這里多說(shuō)一句7-Zip在解壓時(shí)也會(huì)用CRC校驗(yàn)來(lái)確認(rèn)壓縮包是否完整如果解壓時(shí)報(bào)出CRC error通常意味著壓縮包下載不完整、存儲(chǔ)介質(zhì)有壞道或者內(nèi)存不穩(wěn)定導(dǎo)致數(shù)據(jù)讀取出錯(cuò)。解決辦法一般是重新下載安裝包或者換一個(gè)鏡像源下載順便檢查一下硬盤和內(nèi)存。這也說(shuō)明CRC在文件完整性校驗(yàn)中的應(yīng)用遠(yuǎn)比我們?nèi)粘ｊP(guān)注到的要廣泛。5.3 MATLAB位操作的數(shù)據(jù)類型坑MATLAB的位操作函數(shù)對(duì)數(shù)據(jù)類型極其敏感。bitxor(uint16(1), double(1))這種寫法會(huì)直接報(bào)錯(cuò)提示兩個(gè)輸入類型不一致。所以寫MATLAB的CRC代碼一定要養(yǎng)成“所有參與位操作的數(shù)據(jù)先統(tǒng)一轉(zhuǎn)成uint16或uint32”的習(xí)慣。另外bitshift對(duì)于無(wú)符號(hào)整數(shù)的“溢出”處理是靜默截?cái)?。比如bitshift(uint16(0xFFFF), 1)的結(jié)果不是0x1FFFE而是0xFFFE高位丟掉了。這個(gè)行為在CRC算法里其實(shí)正是我們需要的因?yàn)樽笠坪笞罡呶槐緛?lái)就不參與計(jì)算但如果你沒(méi)意識(shí)到這一點(diǎn)中間調(diào)試時(shí)會(huì)暈頭轉(zhuǎn)向。這里建議你打印每一輪循環(huán)的crc值親眼看一下數(shù)據(jù)變化規(guī)律跑通一遍之后CRC在腦子里就不再是抽象公式了。5.4 查表法索引錯(cuò)位前面提到過(guò)MATLAB數(shù)組下標(biāo)從1開(kāi)始而查表法的索引是從0開(kāi)始。把C語(yǔ)言代碼翻譯成MATLAB時(shí)這個(gè)差異最容易引發(fā)bug。我在代碼里專門用了idx double(bitxor(bitshift(crc, -8), data(i))) 1就是為了把索引從0到255映射到1到256。如果你得到的CRC結(jié)果忽大忽小而且明顯沒(méi)有規(guī)律優(yōu)先檢查這一行是不是少了加1。還有個(gè)相關(guān)細(xì)節(jié)bitshift(crc, -8)對(duì)uint16類型是右移8位得到的是高8位值范圍0到255和當(dāng)前字節(jié)異或后也還是0到255所以索引是安全的。6. 個(gè)人使用心得與后續(xù)擴(kuò)展建議這個(gè)MATLAB CRC仿真程序我陸陸續(xù)續(xù)用了一年多從最初的逐位法到后來(lái)的查表法再到支持refin/refout的完整模型每次迭代都讓我對(duì)CRC的認(rèn)識(shí)更深一層。我最大的體會(huì)是CRC這個(gè)技術(shù)看起來(lái)“老”但它在串口通信、以太網(wǎng)幀校驗(yàn)、NFV文件系統(tǒng)完整性校驗(yàn)里都是底層基石值得花時(shí)間把原理徹底搞透。如果你想把這套仿真真正用到自己的項(xiàng)目里我建議你往兩個(gè)方向擴(kuò)展。第一個(gè)方向是增加多協(xié)議支持?，F(xiàn)在函數(shù)里寫死了16位寬度你可以把crc16_calc改成通用的參數(shù)化函數(shù)傳入poly、init、refin、refout、xorout寬度也作為參數(shù)這樣CRC-8、CRC-16、CRC-32一套代碼全搞定。第二個(gè)方向是自動(dòng)做錯(cuò)誤注入統(tǒng)計(jì)。我現(xiàn)在會(huì)寫一個(gè)循環(huán)隨機(jī)翻轉(zhuǎn)數(shù)據(jù)里的多個(gè)比特統(tǒng)計(jì)CRC成功檢出的次數(shù)和漏檢次數(shù)用來(lái)評(píng)估不同生成多項(xiàng)式的檢錯(cuò)能力。這個(gè)對(duì)比實(shí)驗(yàn)在做協(xié)議設(shè)計(jì)時(shí)很實(shí)用可以驗(yàn)證自己選的多項(xiàng)式是否靠譜。最后再分享一個(gè)調(diào)試技巧無(wú)論你用什么語(yǔ)言寫CRC第一版代碼一定要先跑公開(kāi)測(cè)試向量別拿自己的業(yè)務(wù)數(shù)據(jù)試。業(yè)務(wù)數(shù)據(jù)出錯(cuò)了你不知道是算法問(wèn)題還是參數(shù)問(wèn)題而測(cè)試向量能幫你把算法和參數(shù)一次性隔離出來(lái)。這個(gè)習(xí)慣幫我節(jié)省了大量排查時(shí)間今天也一并寫在這里。本文還有配套的精品資源點(diǎn)擊獲取