基于匯編語言的BCH解碼校驗(yàn)算法

　　摘要：介紹數(shù)據(jù)傳輸中BCH解碼校驗(yàn)用匯編語言實(shí)現(xiàn)的算法。算法包含BCH碼的差錯(cuò)檢驗(yàn)、差錯(cuò)位查找和差錯(cuò)糾正，同時(shí)列出相關(guān)主要子程序清單并予說明。

　　關(guān)鍵詞：BCH解碼校驗(yàn)算法匯編語言

　　數(shù)據(jù)傳輸通信中，常常因傳輸差錯(cuò)造成誤碼錯(cuò)碼，尤其在無線通信中，空中的突發(fā)或隨機(jī)干擾噪聲會(huì)造成編碼差錯(cuò)。為了提高傳輸?shù)恼�確率，往往采用一些校驗(yàn)方法，以檢驗(yàn)糾正傳輸差錯(cuò)。通信中校驗(yàn)的方法很多，其中的BCH編碼有其獨(dú)特的優(yōu)點(diǎn)：不僅可以檢糾突發(fā)差錯(cuò)，還能檢糾隨機(jī)差錯(cuò)，被廣泛地采用在微機(jī)級(jí)的通信中。但對(duì)更低層的單片機(jī)級(jí)的數(shù)據(jù)傳輸通信糾錯(cuò)，往往采用奇偶校驗(yàn)等簡(jiǎn)單的校驗(yàn)方法。BCH校驗(yàn)因其算法復(fù)雜，尤其是動(dòng)態(tài)實(shí)時(shí)的無線通信中，單片機(jī)的通信往往無法采用BCH解碼檢糾。

　　筆者近幾年在工業(yè)測(cè)控和無線通信系統(tǒng)開發(fā)，摸索了BCH解碼檢糾在實(shí)時(shí)的、動(dòng)態(tài)的、單片機(jī)級(jí)的通信中的算法，并取得十分突出的效果。以下以BCH(31：21)碼為例進(jìn)行探討。

　　1、BCH碼結(jié)構(gòu)

　　BCH碼是一種檢糾能力較強(qiáng)的循環(huán)碼。它由信息多項(xiàng)式M（X）和校驗(yàn)多項(xiàng)式J（X）組成，如以T（X）表示整個(gè)BCH（31：21）碼字的31位碼組多項(xiàng)式，則：

　　T（X）=M(X)+J(X)(1)

　　在31位BCH碼的后面再加上1位，以保證整個(gè)碼字32位中“1”的個(gè)數(shù)為偶數(shù)。該位稱偶校驗(yàn)位。這樣就形成BCH（31：21）加1位偶校驗(yàn)位的標(biāo)準(zhǔn)碼字，其結(jié)構(gòu)為：

　　其中校驗(yàn)多項(xiàng)式J（X）由公式（2）計(jì)算：

　　X0X1……X20X21……X30X31T（X）J（X）偶校驗(yàn)位

　　J（X）=M(X)/S(X)(2)

　　式中S（X）是BCH（31：21）碼的生成多項(xiàng)式，見式（3）：

　　生成多項(xiàng)式S（X）的值在BCH（31:21）碼的值是固定的。

　　BCH碼是一種循環(huán)碼，循環(huán)碼是利用除法來糾錯(cuò)的。由于任一碼組多項(xiàng)式T（X）都能被生成多項(xiàng)式S（X）整除，所以在接收端可以將接收碼組R（X）用S（X）去除。若在傳輸中未發(fā)生錯(cuò)誤，接收碼與發(fā)送碼相同，即R（X）=T(X)，故接收碼組R（X）必定能被生成多項(xiàng)式S（X）整除；若碼組在傳輸中發(fā)生錯(cuò)誤，即R（X）≠T（X），R（X）被S（X）除時(shí)，可能除不盡而有余項(xiàng)Y（X），因此，可根據(jù)余項(xiàng)是否為零來判斷碼中有無錯(cuò)誤（檢錯(cuò)），如有余項(xiàng)，通過一定的運(yùn)算就可以確定錯(cuò)誤位置，從而加以糾正（糾錯(cuò)）。

　　這里R（X）被S（X）除，是32位被11除，這在非實(shí)時(shí)靜態(tài)的微機(jī)級(jí)實(shí)現(xiàn)非常簡(jiǎn)單；但在實(shí)時(shí)的、動(dòng)態(tài)的、單片機(jī)級(jí)的通信中實(shí)現(xiàn)要快速巧妙的算法才能實(shí)現(xiàn)，否則，現(xiàn)有的碼未檢錯(cuò)及糾錯(cuò)完畢，下一個(gè)碼已經(jīng)到了。因?yàn)閯?dòng)態(tài)中位和位的時(shí)距t往往只有幾十μs，以9.6b/s的短信為例，t=104μs。在這104μs中要完成檢錯(cuò)、定位和糾錯(cuò)三個(gè)算法程序，才是一個(gè)完整的解碼檢糾過程。

　　2、檢錯(cuò)

　　根據(jù)上述原理，檢錯(cuò)過程也就是求算R（X）被S（X）除的余項(xiàng)Y（X）的過程，如余項(xiàng)Y（X）=0，則R（X）=T(X)，傳輸無差錯(cuò)；如余項(xiàng)Y（X）≠0，則R（X）≠T（X），檢出傳輸差錯(cuò)。

　　在算法語言中，所有的運(yùn)算總歸于二種運(yùn)算：加和減。這是電子計(jì)算機(jī)的二進(jìn)制基本電路特性所決定的，也是匯編語言唯一的算術(shù)運(yùn)算方法。為此，這里把除法用模二加法再加右移位實(shí)現(xiàn)。

　　已知：S（X）=11101101001

　　R(X)=r3r4r5r6（ri為8位寄存器）

　　調(diào)用下面的模二加法右移子程序，得到R（X）/S(X)的余項(xiàng)Y（X）=r3r4。

　��；32位/16位模二加法右移子程序

　　m2add:movr7,#00

　　m2ddgx:mova,r3

　　xrla,#0edh;S(x)的高位=oed(h)

　　movr3a

　　mova,r4

　　cplacc.5;S(x)的低3位=001（b）

　　movr4,a

　　mova,r3

　　acc7e10:

　　jbacc.7m2addgx;R（x）的最高位為“0”，則R（x）右移

　　mova,r6

　　rlca

　　movr6,a

　　mova,r5

　　rlca

　　movr5,a

　　mova,r4

　　rlca

　　movr4,a

　　mova,r3

　　rlca

　　movr3,a

　　movr7

　　cjner7,#10h,acc7e10;右移總次數(shù)為16次

　　ret

　　余項(xiàng)Y（X）的高8位在r3寄存器中，低3位在r4的高3位。

　　3、定位

　　如果Y（X）=r3r4≠0，表示接收到的碼組R（X）有差錯(cuò)，下一步則由Y（X）的值推算差錯(cuò)在R（X）中的位置。

　　理論上要找出R（X）中差錯(cuò)的位置，必須計(jì)算出差錯(cuò)校驗(yàn)子C（X）。在實(shí)踐中，校驗(yàn)子C（X）的計(jì)算不僅費(fèi)時(shí)間，而且多位檢糾還需多個(gè)校驗(yàn)子C（X）。為此，經(jīng)過幾年的實(shí)踐，把Y（X）（即r3r4）直接作為綜合校驗(yàn)子，通過快速查表找到差錯(cuò)位置。查找程序的大小和檢糾差錯(cuò)位數(shù)有關(guān)，這里以檢糾4位差錯(cuò)為例，說明定位糾錯(cuò)的方法。

　　；4位差錯(cuò)位址查找子程序

　　bitposi:movb,0;對(duì)R（X）高位至低位的移動(dòng)計(jì)數(shù)

　　movr2,#1fh；設(shè)表格長度

　　btoa:mova,b

　　incb

　　acalltabsub;調(diào)用表格子程序，讀入表格值

　　clrc

　　subba,r3;Y（X）中的r3和表格值比較

　　jnzbinc1:不相等，轉(zhuǎn)出

　　mova,b；相等，繼續(xù)

　　acalltabsub

　　clr

　　subba,r4;Y(X)中的r4和表格值比較

　　jnzr2decl:不相等，轉(zhuǎn)出

　　setbf0;相等，置標(biāo)志位返回

　　ret

　　bincl:incb

　　r2decl:djnzr2,btoa

　　ret;表格查畢，沒有相等的值，不置標(biāo)志位返回

　　從查找子程序返回的B寄存器的值，即為差錯(cuò)在R（X）中從高位到低位的位數(shù)值。

　��；4位差錯(cuò)表格子程序

　　tabsub:inca

　　movca,@a+pc;將相對(duì)位置的表格送入a寄存器

　　ret

　　db0ebh;表格開始，長度為查找子程序中

　　db00；r2寄存器的預(yù)置值

　　db76h

　　4、糾錯(cuò)

　　找到了差錯(cuò)在R（X）位置，就可以糾錯(cuò)了。

　　糾錯(cuò)的原理比較簡(jiǎn)單，因?yàn)閱纹瑱C(jī)處理的是二進(jìn)制數(shù)，而二進(jìn)制數(shù)只有二個(gè)狀態(tài)，即不是“0”就是“1”。也就是說，R（X）中差錯(cuò)位是“0”，則改為“1”；差錯(cuò)位是“1”，則改為“0”。所以糾錯(cuò)要對(duì)所在位求反就行了，程序見本刊網(wǎng)絡(luò)補(bǔ)充版。

　　至此，整個(gè)檢錯(cuò)、定位、糾錯(cuò)的BCH碼校驗(yàn)檢糾過程結(jié)束。BCH碼校驗(yàn)算法，經(jīng)過實(shí)踐的檢驗(yàn)，不失為單片機(jī)級(jí)的數(shù)據(jù)傳輸校驗(yàn)好算法。這種方法可以對(duì)多位隨機(jī)差錯(cuò)和多位突發(fā)差錯(cuò)進(jìn)行檢驗(yàn)和糾錯(cuò)，具體位數(shù)的多少僅受單片機(jī)工作頻率的限制，而不受方法的限制。

【基于語言的BCH解碼校驗(yàn)算法】相關(guān)文章：

用匯編語言實(shí)現(xiàn)BCH解碼校驗(yàn)算法08-07

基于不同解碼類型的8PSK軟解調(diào)算法研究08-13

基于DSP的信道譯碼算法優(yōu)化10-13

基于階梯細(xì)化的圖像放大算法10-13

基于GP算法的知識(shí)發(fā)現(xiàn)系統(tǒng)07-31

基于遺傳算法的OD分布09-14

基于DSP的FFT算法實(shí)現(xiàn)的研究07-01

基于Tvp5150的低功耗視頻解碼模塊09-23

基于ICA的魯棒圖像水印算法07-31

基于移動(dòng)平均的加窗DFT算法06-04