- 相關(guān)推薦
用匯編語言實(shí)現(xiàn)BCH解碼校驗(yàn)算法
摘要:介紹數(shù)據(jù)傳輸中BCH解碼校驗(yàn)用匯編語言實(shí)現(xiàn)的算法。算法包含BCH碼的差錯(cuò)檢驗(yàn)、差錯(cuò)位查找和差錯(cuò)糾正,同時(shí)列出相關(guā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:mov r7,#00
m2ddgx:mov a,r3
xrl a,#0edh ;S(x)的高位=oed(h)
mov r3a
mov a,r4
cpl acc.5 ;S(x)的低3位=001(b)
mov r4,a
mov a,r3
acc7e10:jb acc.7m2addgx ;R(x)的最高位為“0”,則R(x)右移
mov a,r6
rlc a
mov r6,a
mov a,r5
rlc a
mov r5,a
mov a,r4
rlc a
mov r4,a
mov a,r3
rlc a
mov r3,a
mov r7
cjne r7,#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:mov b,0 ;對(duì)R(X)高位至低位的移動(dòng)計(jì)數(shù)
mov r2,#1fh ;設(shè)表格長(zhǎng)度
bto a: mov a,b
inc b
acall tabsub ;調(diào)用表格子程序,讀入表格值
【用語言實(shí)現(xiàn)BCH解碼校驗(yàn)算法】相關(guān)文章:
圖像拼接算法及實(shí)現(xiàn)03-03
FFT算法的研究與DSP實(shí)現(xiàn)03-07
網(wǎng)頁模糊歸類算法的應(yīng)用與實(shí)現(xiàn)03-19
ADPCM語音編解碼電路設(shè)計(jì)及FPGA實(shí)現(xiàn)03-18
嵌入式MPEG—4解碼系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)03-19