[發明專利]快速循環冗余校驗編碼方法及裝置

有效

• 申請號: 200910085524.4
• 申請日: 2009-05-25
• 公開（公告）號: CN101902228A
• 公開（公告）日: 2010-12-01
• 發明（設計）人: 李雙喜
• 申請（專利權）人: 中興通訊股份有限公司
• 主分類號: H03M13/09
• 分類號: H03M13/09
• 代理公司: 北京派特恩知識產權代理事務所(普通合伙) 11270
• 代理人: 張穎玲;武晨燕

技術領域

本發明涉及通信技術領域中編解碼技術，尤其涉及一種快速循環冗余校驗(CRC，Cyclic?Redundancy?Check)編碼方法及裝置。

背景技術

CRC編碼是一種常用的錯誤檢測碼，寬帶碼分多址/時分-同步碼分多址/長期演進系統(WCDMA/TD-SCDMA/LTE)等各版本的協議中都使用了多種不同長度的CRC編碼，以保證各種傳輸格式下信息傳輸的正確性。

CRC編碼是一種系統循環碼，編碼后的數據分為信息序列和校驗序列兩部分，信息序列在左，校驗序列在右。CRC編碼作為一種循環碼，其校驗序列每循環一位，都可能作為某一特定消息序列的校驗序列。

現行的CRC編碼方法一般基于以下原理：

我們假設循環碼的生成多項式為g(x)，待編碼的信息多項式為u(x)，g(x)和u(x)的次數分別為r和k-1，由于信息序列在左，校驗序列在右，碼多項式C(x)的第n-1次至n-k次的系數是信息位，其余為校驗位，其中n-k等于r。因為碼多項式C(x)一定是生成多項式的倍式，故有：

C(x)＝u(x)x^n-k+r(x)≡0|_modg(x)????(1.1)

其中，a≡b|_mod(m)表示a和b關于m同余。式(1.1)中

g(x)＝x^r+g_r-1x^r-1+…+g₁x+1????????(1.2)

是生成多項式；

u(x)＝u_k-1x^k-1+u_k-2x_k-2+…+u₁x+u₀?(1.3)

是信息多項式，u_k-1、u_k-2、…u₁、u₀是信息位，且

r(x)＝r_n-k-1x^n-k-1+r_n-k-2x^n-k-2+…+r₁x+r₀????(1.4)

是校驗多項式，相應的系數是CRC編碼后輸入比特流的校驗位，由式(1.1)

可得

r(x)＝C(x)+u(x)x^n-k≡u(x)x^n-k|_modg(x)?????(1.5)

由式(1.5)可知求CRC校驗位可以通過以g(x)為模做除法的方式來實現，現行CRC編碼器基本都是以該方法實現的。

除法電路通常使用反饋移位寄存器來實現，圖1為現有用r級移位寄存器來實現編碼的CRC編碼器結構示意圖，圖1中D_r-1為移位寄存器，g_r-1為生成多項式g(x)的系數，Reg為寄存器。采用該結構的CRC編碼器每個時鐘只能處理1個輸入比特，對于大規模系統來說，該電路系統開銷大，系統運行效率低。

發明內容

有鑒于此，本發明的主要目的在于提供一種快速CRC編碼方法及裝置，能夠在一個時鐘對多個輸入比特進行CRC編碼，節省系統開銷，提高系統運行效率。

為達到上述目的，本發明的技術方案是這樣實現的：

本發明提供一種快速循環冗余校驗編碼方法，包括：

將循環冗余校驗CRC編碼生成多項式映射生成r+1階轉移矩陣J，其中r為生成多項式的最高次數；

刪除所述r+1階轉移矩陣J的第一行以及第一列，獲得r階轉移矩陣T；由所述r+1階轉移矩陣J的第2至r+1行的第一列形成r×1列矩陣S；

根據所得到的r階轉移矩陣T和r×1列矩陣S，獲得CRC編碼的零輸入轉移矩陣P和零狀態轉移矩陣Ω；

在輸入比特流前面添加空位比特，添加空位比特后的輸入比特流的比特個數為并行運算位寬N的整數倍，N為大于1的正整數；

根據所得到的零輸入轉移矩陣P、零狀態轉移矩陣Ω和添加空位比特后的輸入比特流，獲得輸入比特流的CRC編碼校驗序列。

上述技術方案中，所述r+1階轉移矩陣J的映射生成包括：

生成多項式的系數gk等于1時，將轉移矩陣J的第r+1-k行第1和第2列設置為1，其中k＝0，1，2，3，…r；

設置轉移矩陣J的第i行第i+1列設置為1，其中i＝2，3，...r。