[發(fā)明專利]一種循環(huán)冗余校驗CRC碼的實現(xiàn)方法和裝置

無效

• 申請?zhí)枺?/td>: 200910132682.0
• 申請日: 2009-04-07
• 公開（公告）號: CN101527615A
• 公開（公告）日: 2009-09-09
• 發(fā)明（設(shè)計）人: 張玉琳
• 申請（專利權(quán)）人: 華為技術(shù)有限公司
• 主分類號: H04L1/00
• 分類號: H04L1/00
• 代理公司: 北京中博世達專利商標代理有限公司
• 代理人: 申 健

技術(shù)領(lǐng)域

本發(fā)明涉及通信系統(tǒng)中的差錯控制技術(shù)，尤其涉及一種循環(huán)冗余校驗CRC碼的實現(xiàn)方法和裝置。

背景技術(shù)

為保證通信系統(tǒng)中數(shù)據(jù)傳輸?shù)恼_性，需要對通信過程進行差錯控制。循環(huán)冗余校驗(Cyclic?Redundancy?Check，CRC)，由于其編碼簡單且誤判概率很低，是通信系統(tǒng)中常用的差錯控制方式。

CRC是分組線性碼的分支，基本的原理是利用線性編碼理論，在發(fā)送端根據(jù)要傳送的k位信息碼序列，以一定的規(guī)則產(chǎn)生r位校驗用的監(jiān)督碼(即CRC碼)，并附在原信息碼序列后邊，構(gòu)成一個新的共(k+r)位的序列，然后將包含了CRC碼的新的序列發(fā)送出去。在接收端，則根據(jù)信息碼序列和CRC碼之間所遵循的規(guī)則進行檢驗，以確定傳送中是否出錯。

例如，待傳送的k位二進制信息碼序列為D＝{d[p-1]d[p-2]......d[1]d[0]}，通過將序列D左移r位，除以一個(r+1)位的生成多項式，得到r位的余式R＝{r[r-1]r[r-2]......r[1]r[0]}，將余式R作為序列D的CRC碼，生成(k+r)位的新的二進制碼序列M＝{d[p-1]d[p-2]......d[1]d[0]r[r-1]r[r-2]......r[1]r[0]}，進行傳輸。

在實際應(yīng)用中，CRC碼可以通過硬件邏輯電路來實現(xiàn)，典型的實現(xiàn)電路有串行電路和并行電路。串行電路計算CRC碼時是逐位地進行計算，例如，如圖1(a)所示，對于4位的CRC碼(CRC-4)，首先將四個寄存器清0；然后，把信息序列碼元作為輸入數(shù)據(jù)，串行的移位輸入，即每個時鐘周期輸入一個比特信息序列碼元。經(jīng)過4個時鐘周期以后，就可以將信息碼元的前4比特輸入到寄存器中。后續(xù)將寄存器中的數(shù)據(jù)逐位左移并與輸入的信息碼元異或，計算CRC碼。如圖1(b)所示，以生成多項式為x⁴+x+1的CRC-4為例，顯示了一種無需等待信息碼元移入寄存器之后再計算CRC碼的串行電路。

并行電路的實現(xiàn)是基于上述串行電路的，其原理是：由于n位信息碼同時輸入并行電路所產(chǎn)生的CRC余數(shù)與n位信息碼逐位輸入串行電路產(chǎn)生的CRC余數(shù)相同，所以可以認為并行電路和串行電路是等效的，從而根據(jù)串行電路中各寄存器和輸入信息位的變化可得出并行電路的邏輯關(guān)系式。利用并行電路可一次輸入n位待傳送的信息碼，通過多次輸入n位信息碼最終可以得到該信息碼序列的CRC校驗碼。如圖2所示，顯示了一種通用的并行電路。

在實現(xiàn)本發(fā)明的過程中，發(fā)明人發(fā)現(xiàn)現(xiàn)有技術(shù)中至少存在如下問題：

現(xiàn)有技術(shù)中基于線反饋移位寄存器的串行電路每個時鐘周期只能移入1比特數(shù)據(jù)，效率非常低，只能用在對性能要求較低的低速CRC校驗電路中，當需要高速的CRC數(shù)據(jù)校驗處理時，串行電路無法滿足要求；

現(xiàn)有技術(shù)中的并行電路進行多位數(shù)據(jù)并行處理時，隨著并行數(shù)據(jù)位寬的不斷增加，并行電路所用到的異或邏輯電路層次也越來越大，導致相應(yīng)的電路延遲過大，電路的時鐘頻率越來越低。由于電路的運算性能或數(shù)據(jù)吞吐率是與電路的時鐘頻率和數(shù)據(jù)位寬成正比的，現(xiàn)有技術(shù)在增加數(shù)據(jù)處理位寬時降低了電路的時鐘頻率，從而無法通過并行數(shù)據(jù)位寬的線性增加使電路的性能或數(shù)據(jù)的吞吐率也線性的增加，當需要處理高速CRC數(shù)據(jù)時，現(xiàn)有技術(shù)中的并行電路也是無法滿足需求的。

發(fā)明內(nèi)容

為解決現(xiàn)有技術(shù)中存在的問題，本發(fā)明的實施例提供了一種循環(huán)冗余校驗CRC碼的實現(xiàn)方法和裝置，能夠顯著提高實現(xiàn)CRC碼時系統(tǒng)的運算性能，滿足高速CRC數(shù)據(jù)處理時的運算需求。

為達到上述目的，本發(fā)明的實施例采用如下技術(shù)方案：

一種循環(huán)冗余校驗CRC碼的實現(xiàn)方法，所述方法包括：

對并行輸入的信息碼進行至少一次異或，且在所述異或過程中進行至少一次流水，獲取第一結(jié)果；

將前一次獲得的CRC碼進行異或，得到第二結(jié)果；

將所述第二結(jié)果和所述第一結(jié)果進行異或，獲取當前的CRC碼。

一種循環(huán)冗余校驗CRC碼的實現(xiàn)裝置，所述裝置包括：

信息碼異或單元，用于對并行輸入的信息碼進行至少一次異或，且在所述異或過程中進行至少一次流水，獲取第一結(jié)果；

CRC碼異或單元，用于將前一次獲得的CRC碼進行異或，得到第二結(jié)果；

CRC碼獲取單元，用于將所述信息碼異或單元獲取的第一結(jié)果和所述CRC碼異或單元獲取的第二結(jié)果進行異或，獲取當前的CRC碼。