CRC校驗程式設計

CRC程式設計

程式的宗旨：通過編寫CRC的校驗程式，加深對CRC原理的了解，同時學會将書本上的原理運用于實際，動手實踐才能學得更快。

注：本文關于CRC原理那部分内容，來自網絡搜集。

1. 需求分析

編寫一個CRC校驗的模拟程式，該程式實作的功能如下：

輸入：一串二進制比特串

輸出：CRC校驗碼

2. CRC校驗原理分析

在此，我們主要從适合于程式設計實作的角度分析CRC校驗的算法原理，而不隻是書本上關于CRC原理的介紹。

Cyclic Redundancy Check循環備援檢驗，是基于資料計算一組效驗碼，用于核對資料傳輸過程中是否被更改或傳輸錯誤。

假設資料傳輸過程中需要發送15位的二進制資訊g=101001110100001，這串二進制碼可表示為代數多項式g(x) = x^14 + x^12 + x^9 + x^8 + x^7 + x^5 + 1，其中g中第k位的值，對應g(x)中x^k的系數。将g(x)乘以x^m，既将g後加m個0，然後除以m階多項式h(x)，得到的(m-1)階餘項r(x)對應的二進制碼r就是CRC編碼。 

h(x)可以自由選擇或者使用國際通行标準，一般按照h(x)的階數m，将CRC算法稱為CRC-m，比如CRC-8、CRC-32、CRC-64等。

g(x)和h(x)的除運算，可以通過g和h做xor（異或）運算。比如将11001與10101做xor運算：

例如使用CRC-8算法求101001110100001的效驗碼。CRC-8标準的h(x) = x^8 + x^7 + x^6 + x^4 + x^2 + 1，即h是9位的二進制串111010101。

經過疊代運算後，最終得到的r是10001100，這就是CRC效驗碼。

3  概要設計

基于以上原理，我們對軟體進行了初步的規劃和設計：

（1） 由于h(x)的選擇有多種标準，其原理都是類似的，故我們就選用CRC-8标準來實作CRC校驗的模拟。

（2） 由上述算法原理可知，程式中需要使用到數組或者隊列來實作資料的存儲和運算，由于c++中支援許多封裝得很好的容器來組織資料，例如：Deque容器，故使用c++語言可以更加高效地完成所需要的功能。故我們的程式設計語言采用c++。

（3） 為了提供友好的使用者界面，我們采用Visual C++的MFC架構建構應用程式，使用一個簡單的對話框程式，包含一個輸入編輯框和一個輸出編輯框

4 詳細設計

4.1 資料結構的設計

    定義三個bool型的隊列，deque<bool>，分别代表：輸入串寄存器、操作串寄存器、剩餘串寄存器。

    其中：

    輸入串寄存器：用于存放使用者輸入的二進制串

    操作串寄存器：用于存放目前的被減數

    剩餘串寄存器：用于存放輸入串寄存器沒有進入操作串寄存器的剩餘部分

定義一個bool型的數組，存放H（x）

const int CRC8_HX_LENGTH = 9; // 采用CRC-8算法,故H(x)的長度為9 

bool hx[CRC8_HX_LENGTH] = {1,1,1,0,1,0,1,0,1};    //!< H(x)

定義兩個Cstring型的變量，存放輸入的資料和輸出的資料。

4.2 子產品劃分

子產品功能概述：

    輸入子產品：擷取使用者的輸入二進制串，并判斷輸入的正确性

寄存器初始化子產品：将使用者的輸入字元串轉化成0、1形式的數字串存放到輸入串寄存器中，并取出前9位數存放到操作寄存器中作為目前的被減數。

    校驗碼計算子產品：對操作寄存器的每一位與H（x）的對應的每一位進行異或，并将結果存放在操作寄存器的對應位置

    操作寄存器移位子產品：讓目前操作寄存器隊列隊首的所有0出隊，并從剩餘寄存器中補充對應個數的資料到操作寄存器隊列隊尾，供下一次異或操作。

顯示子產品：将操作寄存器最終的CRC校驗碼轉化成字元串的形式以供輸出。

4.3 程式流程圖

5  程式運作效果及驗證

 輸入字元串驗證

本文轉自 Jhuster 51CTO部落格，原文連結：http://blog.51cto.com/ticktick/176981，如需轉載請自行聯系原作者