用匯編語(yǔ)言實(shí)現BCH解碼校驗算法
加入技術(shù)交流群
摘要：介紹數據傳輸中BCH解碼校驗用匯編語(yǔ)言實(shí)現的算法。算法包含BCH碼的差錯檢驗、差錯位查找和差錯糾正，同時(shí)列出相關(guān)主要子程序清單并予說(shuō)明。
數據傳輸通信中，常常因傳輸差錯造成誤碼錯碼，尤其在無(wú)線(xiàn)通信中，空中的突發(fā)或隨機干擾噪聲會(huì )造成編碼差錯。為了提高傳輸的正確率，往往采用一些校驗方法，以檢驗糾正傳輸差錯。通信中校驗的方法很多，其中的BCH編碼有其獨特的優(yōu)點(diǎn)：不僅可以檢糾突發(fā)差錯，還能檢糾隨機差錯，被廣泛地采用在微機級的通信中。但對更低層的單片機級的數據傳輸通信糾錯，往往采用奇偶校驗等簡(jiǎn)單的校驗方法。BCH校驗因其算法復雜，尤其是動(dòng)態(tài)實(shí)時(shí)的無(wú)線(xiàn)通信中，單片機的通信往往無(wú)法采用BCH解碼檢糾。
筆者近幾年在工業(yè)測控和無(wú)線(xiàn)通信系統開(kāi)發(fā)，摸索了BCH解碼檢糾在實(shí)時(shí)的、動(dòng)態(tài)的、單片機級的通信中的算法，并取得十分突出的效果。以下以BCH(31：21)碼為例進(jìn)行探討。
1 BCH碼結構
BCH碼是一種檢糾能力較強的循環(huán)碼。它由信息多項式M（X）和校驗多項式J（X）組成，如以T（X）表示整個(gè)BCH（31：21）碼字的31位碼組多項式，則：
T（X）=M(X)+J(X) (1)
在31位BCH碼的后面再加上1位，以保證整個(gè)碼字32位中“1”的個(gè)數為偶數。該位稱(chēng)偶校驗位。這樣就形成BCH（31：21）加1位偶校驗位的標準碼字，其結構為：
其中校驗多項式J（X）由公式（2）計算：
| X0X1……X20 | X21……X30 | X31 |
| T（X） | J（X） | 偶校驗位 |
J（X）=M(X)/S(X) (2)
式中S（X）是BCH（31：21）碼的生成多項式，見(jiàn)式（3）：
生成多項式S（X）的值在BCH（31:21）碼的值是固定的。
BCH碼是一種循環(huán)碼，循環(huán)碼是利用除法來(lái)糾錯的。由于任一碼組多項式T（X）都能被生成多項式S（X）整除，所以在接收端可以將接收碼組R（X）用S（X）去除。若在傳輸中未發(fā)生錯誤，接收碼與發(fā)送碼相同，即R（X）=T(X)，故接收碼組R（X）必定能被生成多項式S（X）整除；若碼組在傳輸中發(fā)生錯誤，即R（X）≠T（X），R（X）被S（X）除時(shí)，可能除不盡而有余項Y（X），因此，可根據余項是否為零來(lái)判斷碼中有無(wú)錯誤（檢錯），如有余項，通過(guò)一定的運算就可以確定錯誤位置，從而加以糾正（糾錯）。
這里R（X）被S（X）除，是32位被11除，這在非實(shí)時(shí)靜態(tài)的微機級實(shí)現非常簡(jiǎn)單；但在實(shí)時(shí)的、動(dòng)態(tài)的、單片機級的通信中實(shí)現要快速巧妙的算法才能實(shí)現，否則，現有的碼未檢錯及糾錯完畢，下一個(gè)碼已經(jīng)到了。因為動(dòng)態(tài)中位和位的時(shí)距t往往只有幾十μs，以9.6b/s的短信為例，t=104μs。在這104μs中要完成檢錯、定位和糾錯三個(gè)算法程序，才是一個(gè)完整的解碼檢糾過(guò)程。
2 檢錯
根據上述原理，檢錯過(guò)程也就是求算R（X）被S（X）除的余項Y（X）的過(guò)程，如余項Y（X）=0，則R（X）=T(X)，傳輸無(wú)差錯；如余項Y（X）≠0，則R（X）≠T（X），檢出傳輸差錯。
在算法語(yǔ)言中，所有的運算總歸于二種運算：加和減。這是電子計算機的二進(jìn)制基本電路特性所決定的，也是匯編語(yǔ)言唯一的算術(shù)運算方法。為此，這里把除法用模二加法再加右移位實(shí)現。
已知：S（X）=11101101001
R(X)=r3r4r5r6 （ri為8位寄存器）
調用下面的模二加法右移子程序，得到R（X）/S(X)的余項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 ;右移總次數為16次
ret
余項Y（X）的高8位在r3寄存器中，低3位在r4的高3位。
3 定位
如果Y（X）=r3r4≠0，表示接收到的碼組R（X）有差錯，下一步則由Y（X）的值推算差錯在R（X）中的位置。
理論上要找出R（X）中差錯的位置，必須計算出差錯校驗子C（X）。在實(shí)踐中，校驗子C（X）的計算不僅費時(shí)間，而且多位檢糾還需多個(gè)校驗子C（X）。為此，經(jīng)過(guò)幾年的實(shí)踐，把Y（X）（即r3r4）直接作為綜合校驗子，通過(guò)快速查表找到差錯位置。查找程序的大小和檢糾差錯位數有關(guān)，這里以檢糾4位差錯為例，說(shuō)明定位糾錯的方法。
；4位差錯位址查找子程序
bitposi:mov b,0 ;對R（X）高位至低位的移動(dòng)計數
mov r2,#1fh ；設表格長(cháng)度
bto a: mov a,b
inc b
acall tabsub ;調用表格子程序，讀入表格值
clr c
subb a,r3 ;Y（X）中的r3 和表格值比較
jnz binc1 :不相等，轉出
mov a,b ；相等，繼續
acall tabsub
clr
subb a,r4 ;Y(X)中的r4和表格值比較
jnz r2decl:不相等，轉出
setb f0 ;相等，置標志位返回
ret
bincl:inc b
r2decl:djnz r2,btoa
ret ;表格查畢，沒(méi)有相等的值，不置標志位返回
從查找子程序返回的B寄存器的值，即為差錯在R（X）中從高位到低位的位數值。
；4位差錯表格子程序
tabsub:inc a
movc a,@a+pc;將相對位置的表格送入a寄存器
ret
db 0ebh ;表格開(kāi)始，長(cháng)度為查找子程序中
db 00 ；r2寄存器的預置值
db 76h
.
.
.
4 糾錯
找到了差錯在R（X）位置，就可以糾錯了。
糾錯的原理比較簡(jiǎn)單，因為單片機處理的是二進(jìn)制數，而二進(jìn)制數只有二個(gè)狀態(tài)，即不是“0”就是“1”。也就是說(shuō)，R（X）中差錯位是“0”，則改為“1”；差錯位是“1”，則改為“0”。所以糾錯要對所在位求反就行了，程序見(jiàn)本刊網(wǎng)絡(luò )補充版（http://www.dpj.com.cn）。
至此，整個(gè)檢錯、定位、糾錯的BCH碼校驗檢糾過(guò)程結束。BCH碼校驗算法，經(jīng)過(guò)實(shí)踐的檢驗，不失為單片機級的數據傳輸校驗好算法。這種方法可以對多位隨機差錯和多位突發(fā)差錯進(jìn)行檢驗和糾錯，具體位數的多少僅受單片機工作頻率的限制，而不受方法的限制。
電能表相關(guān)文章:電能表原理
評論