[發(fā)明專(zhuān)利]快速循環(huán)冗余校驗(yàn)編碼方法及裝置

有效

• 申請(qǐng)?zhí)枺?/td>: 200910085524.4
• 申請(qǐng)日: 2009-05-25
• 公開(kāi)（公告）號(hào): CN101902228A
• 公開(kāi)（公告）日: 2010-12-01
• 發(fā)明（設(shè)計(jì)）人: 李雙喜
• 申請(qǐng)（專(zhuān)利權(quán)）人: 中興通訊股份有限公司
• 主分類(lèi)號(hào): H03M13/09
• 分類(lèi)號(hào): H03M13/09
• 代理公司: 北京派特恩知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 11270
• 代理人: 張穎玲;武晨燕

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

本發(fā)明涉及通信技術(shù)領(lǐng)域中編解碼技術(shù)，尤其涉及一種快速循環(huán)冗余校驗(yàn)(CRC，Cyclic?Redundancy?Check)編碼方法及裝置。

背景技術(shù)

CRC編碼是一種常用的錯(cuò)誤檢測(cè)碼，寬帶碼分多址/時(shí)分-同步碼分多址/長(zhǎng)期演進(jìn)系統(tǒng)(WCDMA/TD-SCDMA/LTE)等各版本的協(xié)議中都使用了多種不同長(zhǎng)度的CRC編碼，以保證各種傳輸格式下信息傳輸?shù)恼_性。

CRC編碼是一種系統(tǒng)循環(huán)碼，編碼后的數(shù)據(jù)分為信息序列和校驗(yàn)序列兩部分，信息序列在左，校驗(yàn)序列在右。CRC編碼作為一種循環(huán)碼，其校驗(yàn)序列每循環(huán)一位，都可能作為某一特定消息序列的校驗(yàn)序列。

現(xiàn)行的CRC編碼方法一般基于以下原理：

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

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

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

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

是生成多項(xiàng)式；

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

是信息多項(xiàng)式，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)

是校驗(yàn)多項(xiàng)式，相應(yīng)的系數(shù)是CRC編碼后輸入比特流的校驗(yàn)位，由式(1.1)

可得

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

由式(1.5)可知求CRC校驗(yàn)位可以通過(guò)以g(x)為模做除法的方式來(lái)實(shí)現(xiàn)，現(xiàn)行CRC編碼器基本都是以該方法實(shí)現(xiàn)的。

除法電路通常使用反饋移位寄存器來(lái)實(shí)現(xiàn)，圖1為現(xiàn)有用r級(jí)移位寄存器來(lái)實(shí)現(xiàn)編碼的CRC編碼器結(jié)構(gòu)示意圖，圖1中D_r-1為移位寄存器，g_r-1為生成多項(xiàng)式g(x)的系數(shù)，Reg為寄存器。采用該結(jié)構(gòu)的CRC編碼器每個(gè)時(shí)鐘只能處理1個(gè)輸入比特，對(duì)于大規(guī)模系統(tǒng)來(lái)說(shuō)，該電路系統(tǒng)開(kāi)銷(xiāo)大，系統(tǒng)運(yùn)行效率低。

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

有鑒于此，本發(fā)明的主要目的在于提供一種快速CRC編碼方法及裝置，能夠在一個(gè)時(shí)鐘對(duì)多個(gè)輸入比特進(jìn)行CRC編碼，節(jié)省系統(tǒng)開(kāi)銷(xiāo)，提高系統(tǒng)運(yùn)行效率。

為達(dá)到上述目的，本發(fā)明的技術(shù)方案是這樣實(shí)現(xiàn)的：

本發(fā)明提供一種快速循環(huán)冗余校驗(yàn)編碼方法，包括：

將循環(huán)冗余校驗(yàn)CRC編碼生成多項(xiàng)式映射生成r+1階轉(zhuǎn)移矩陣J，其中r為生成多項(xiàng)式的最高次數(shù)；

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

根據(jù)所得到的r階轉(zhuǎn)移矩陣T和r×1列矩陣S，獲得CRC編碼的零輸入轉(zhuǎn)移矩陣P和零狀態(tài)轉(zhuǎn)移矩陣Ω；

在輸入比特流前面添加空位比特，添加空位比特后的輸入比特流的比特個(gè)數(shù)為并行運(yùn)算位寬N的整數(shù)倍，N為大于1的正整數(shù)；

根據(jù)所得到的零輸入轉(zhuǎn)移矩陣P、零狀態(tài)轉(zhuǎn)移矩陣Ω和添加空位比特后的輸入比特流，獲得輸入比特流的CRC編碼校驗(yàn)序列。

上述技術(shù)方案中，所述r+1階轉(zhuǎn)移矩陣J的映射生成包括：

生成多項(xiàng)式的系數(shù)gk等于1時(shí)，將轉(zhuǎn)移矩陣J的第r+1-k行第1和第2列設(shè)置為1，其中k＝0，1，2，3，…r；

設(shè)置轉(zhuǎn)移矩陣J的第i行第i+1列設(shè)置為1，其中i＝2，3，...r。