循環(huán)冗余校驗(yàn)(crc)算法實(shí)現(xiàn)(編輯修改稿)
2025-07-26 00:48 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 碼。通過示例，可以發(fā)現(xiàn)一些規(guī)律，依據(jù)這些規(guī)律調(diào)整算法：（1）每次迭代，根據(jù)gk的首位決定b，b是與gk進(jìn)行運(yùn)算的二進(jìn)制碼。若gk的首位是1，則b=h，如圖24所示；若gk的首位是0，則b=0，或者跳過此次迭代，如圖25所示，上面的例子中就是碰到0后直接跳到后面的非零位。圖24 gk首位為1時(shí)的情況圖25 gk首位為0時(shí)的情況（2）每次迭代，gk的首位將會(huì)被移出，如圖26所示，所以只需考慮第2位后計(jì)算即可。這樣就可以舍棄h的首位，將b取h的后m位。比如CRC8的h是111010101，b只需是11010101。圖26 首位移出過程 （3）每次迭代，受到影響的是gk的前m位，所以構(gòu)建一個(gè)m位的寄存器S，此寄存器儲(chǔ)存gk的前m位。每次迭代計(jì)算前先將S的首位拋棄，將寄存器左移一位，同時(shí)將g的后一位加入寄存器。若使用此種方法，計(jì)算步驟如圖27所示：圖27 使用寄存器計(jì)算的步驟三、過程論述了解到CRC的具體計(jì)算過程后，可以開始構(gòu)造基本程序架構(gòu)。以for循環(huán)來(lái)建立迭代運(yùn)算，按照題目要求，可將程序分為四個(gè)部分進(jìn)行編寫。 第一部分該部分利用數(shù)組模擬網(wǎng)絡(luò)數(shù)據(jù)包結(jié)構(gòu)，編碼實(shí)現(xiàn)CRC求余算法。程序流程圖如圖31所示。開始構(gòu)建數(shù)組M、取其長(zhǎng)度L、構(gòu)建生成多項(xiàng)式添加冗余位、k=0初始化余數(shù)數(shù)組Rk=k+1構(gòu)造與R等長(zhǎng)度的除數(shù)數(shù)組PY判斷R的首位是否為0被除數(shù)所有位置0NR = P xor R恢復(fù)除數(shù)數(shù)組去除被除數(shù)第一位NkL?Y結(jié)束圖31 第一部分程序流程圖 第二部分該部分將得到的校驗(yàn)位附加到網(wǎng)絡(luò)數(shù)據(jù)包相應(yīng)的位置，并將添加了幀檢驗(yàn)序列FCS的數(shù)據(jù)繼續(xù)以模2除法進(jìn)行CRC檢驗(yàn)。程序流程圖如圖32所示。NY顯示碼元傳輸發(fā)生錯(cuò)誤結(jié)束輸出原始序列YN判斷余數(shù)是否為0kLlength(CRC_P)+1恢復(fù)除數(shù)數(shù)組、去除被除數(shù)第一位R = P xor R被除數(shù)所有位置0NY判斷R的首位是否為0構(gòu)造與R等長(zhǎng)度的除數(shù)數(shù)組Pk=k+1取冗余編碼長(zhǎng)度L、初始化余數(shù)數(shù)組R、令k=0將生成余數(shù)序列的冗余位疊加到編碼序列開始圖32 第二部分程序流程圖 第三部分該部分實(shí)現(xiàn)了根據(jù)數(shù)據(jù)包的長(zhǎng)度，隨機(jī)生成一個(gè)數(shù)據(jù)包產(chǎn)生突變的位置，并對(duì)該位置的bit位模擬突變產(chǎn)生的過程。按照要求，先利用i=ceil(rand(1,1)*r)函數(shù)來(lái)隨機(jī)抽取數(shù)組中的一個(gè)位，其中r為該數(shù)組的長(zhǎng)度。再將該位的值進(jìn)行取反再放回，生成一個(gè)某位發(fā)生突變的新數(shù)組。重新利用CRC算法校驗(yàn)該數(shù)據(jù)包，并指出產(chǎn)生的結(jié)果。由于檢驗(yàn)方法與第二部分一致，因此程序流程圖與第二部分的流程圖（圖32）基本一致，此處不再繪制。第四部分該部分構(gòu)造出了一個(gè)無(wú)法被CRC檢錯(cuò)的實(shí)例，來(lái)驗(yàn)證CRC是否能夠檢出所有的錯(cuò)誤。通過查閱資料，我了解到了CRC校驗(yàn)的檢錯(cuò)性能。CRC校驗(yàn)碼的檢錯(cuò)能力與其生成多項(xiàng)式密切相關(guān)。生成多項(xiàng)式的次數(shù)越高，其檢錯(cuò)能力越強(qiáng)。若CRC校驗(yàn)的生成多項(xiàng)式的最高次冪為r，則該CRC校驗(yàn)碼的檢錯(cuò)性能如下：（1） 可檢出所有奇數(shù)個(gè)錯(cuò)誤；（2） 可檢出所有2bit個(gè)錯(cuò)誤；（3） 可檢出所有長(zhǎng)度=r個(gè)bit的突發(fā)錯(cuò)誤；（4） 對(duì)于長(zhǎng)度=（r+1)個(gè)bit的突發(fā)錯(cuò)，其漏檢率僅為：1/2^(r1）。（5） 對(duì)于長(zhǎng)度（r+1)個(gè)bit的突發(fā)錯(cuò)，其漏檢率僅為：1/2^r。事實(shí)證明CRC雖具有良好的檢錯(cuò)能力，但不能夠檢出所有的錯(cuò)誤。構(gòu)造該無(wú)法檢錯(cuò)的實(shí)例的思路：由于生成多項(xiàng)式的次數(shù)越高，CRC的檢錯(cuò)能力越強(qiáng)，故我在程序中自主構(gòu)建一個(gè)相對(duì)簡(jiǎn)單的生成多項(xiàng)式便于實(shí)例的構(gòu)造?；仡機(jī)RC檢驗(yàn)的方法，先將添加了冗余碼FCS后發(fā)送的序列與求余過程中的生成多項(xiàng)式進(jìn)行模2運(yùn)算，再來(lái)判斷求得的余數(shù)是否為0？若為0則證明傳輸過程無(wú)差錯(cuò)；若不為0則證明傳輸過程中有差錯(cuò)。因此我進(jìn)行大膽猜測(cè)：如若添加了冗余碼FCS后發(fā)送的數(shù)據(jù)發(fā)生突變，但突變后的數(shù)據(jù)恰巧也能被原生成多項(xiàng)式整除，即存在“同余”的錯(cuò)誤，是不是CRC便無(wú)法檢測(cè)出該已經(jīng)發(fā)生了突變的錯(cuò)誤數(shù)據(jù)？因此我在該部分構(gòu)造了一個(gè)與原發(fā)送數(shù)據(jù)不同的錯(cuò)誤序列，經(jīng)驗(yàn)算，該錯(cuò)誤序列也能被原定的生成多項(xiàng)式整除。再利用第二部分的檢驗(yàn)方式，觀察最終輸出結(jié)果與預(yù)測(cè)是否一致，最后加上一個(gè)判斷語(yǔ)句顯示最終結(jié)果。由于檢驗(yàn)方式與第二部分一致，故對(duì)于檢驗(yàn)的流程圖不再繪制，對(duì)于判斷結(jié)果的程序流程圖如圖33所示。結(jié)束實(shí)際傳輸數(shù)據(jù)錯(cuò)誤實(shí)際傳輸數(shù)據(jù)正確NYerror_sequence == M？已知錯(cuò)誤序列error_sequence編寫原序列M開始圖33 第四部分判斷結(jié)果的程序流程圖 結(jié)果分析將程序運(yùn)行后可以得到所有的輸出，現(xiàn)將輸出分三個(gè)部分展示。 CRC算法的實(shí)現(xiàn)編程實(shí)現(xiàn)利用數(shù)組模擬網(wǎng)絡(luò)數(shù)據(jù)包結(jié)構(gòu)實(shí)現(xiàn)CRC算法，并將得到的校驗(yàn)位附加到網(wǎng)絡(luò)數(shù)據(jù)包相應(yīng)的位置。程序中，M表示原始帶傳送數(shù)據(jù)；CRC_P表示生成多項(xiàng)式；crc_M表示經(jīng)計(jì)算得到的添加了冗余碼FCS后的數(shù)據(jù)。若輸出一組名為original_sequence的數(shù)據(jù)則表明本次校驗(yàn)結(jié)果正確；若輸出err=1則表明本次校驗(yàn)結(jié)果錯(cuò)誤。令M=101110；生成多項(xiàng)式P(X)=X^3+1。結(jié)果如圖41所示。圖41 CRC校驗(yàn)結(jié)果展示分析：從結(jié)果中看出crc_M的結(jié)果為101110011，即所得冗余碼FCS=011，與驗(yàn)算結(jié)果一致。且經(jīng)校驗(yàn)后輸出了一組名為original_sequence的數(shù)據(jù)，該數(shù)據(jù)與M一致，說明校驗(yàn)結(jié)果正確
職業(yè)教育相關(guān)推薦
鄂ICP備17016276號(hào)-1