无线激光通信中GF(3)域上的纠错编码研究.doc

第7期 无线激光通信中GF(3)域上的纠错编码研究 · 27 ·
更多电子资料请登录赛微电子网
无线激光通信中GF(3)域上的纠错编码研究*
殷致云 柯熙政 张 波
(西安理工大学自动化与信息工程学院, 西安 710048)
摘 要: 在无线激光通信领域广泛采用L-PPM调制方式, 因此信道编码采用基于有限域GF(q)上纠错码可以和L-PPM更好的映射, 并提供更高的检错和纠错能力。结合初等数论知识, 首先推导出了基于有限域GF(3)上的小于等于4次的首一不可约多项式、本原多项式、极小多项式、不可约多项式和本原多项式的周期等要素; 接下来研究了GF(3)域上的编译码算法, 详细论述了GF(3)域上的Hamming码编译码方法, 包括Hamming[4,2,3]完全码译码流程。其后详细论述了GF(3)域BCH码的编译码方法, 包括BCH[26,17]码的纠错译码流程。最后通过MATLAB程序仿真, 验证了采用3-PPM调制方式, 在受到信道干扰后, 接收端用基于GF(3)域的BCH纠错码能够纠正两位随机错误。
关键词: 不可约多项式；本原多项式；极小多项式；PPM；BCH
中图分类号: TN929.12　　　文献标识码: A　　　国家标准学科分类代码: 510.4030
Research on error-correcting code in wireless laser communications over GF(3)
Yin Zhiyun Ke Xizheng Zhang Bo
(Faculty of Automation and Information Engineering, Xi’an University of Technology, Xi’an 710048, China)
Abstract: L-PPM modulation technique is widely used in wireless laser communication. Corresponding to L-PPM modulation technique, error correcting code over finite field GF(q) is studied to improve correction ability. In this paper, monic irreducible polynomial, primitive polynomial, minimal polynomial, and their periods are deduced over finite field GF(3) connecting with elementary number theory. In addition, arithmetic of encoding and decoding over GF(3) are briefly studied, and Hamming[4,2,3] perfect code and BCH[26,17,5] decoding process are discussed in detail. At last, it is validated by MATLAB simulation that in 3-PPM modulation system, adopting BCH error-correcting code over GF(3) can correct two random error in receiving terminal subjected to channel interference.
Keywords: monic Irreducible function; primitive polynomial;minimal polynomial;PPM; BCH

1 引 言
无线激光通信是以激光束作为载波传递信息的一种技术。由于无线光信道的不稳定性, 信息在传输过程中往往会出现随机或突发性错误, 无线光通信中需要引入纠错编码技术[1]。信源经过信道编码(纠错编码)后, 进行信源编码, 信源编码将信息映射为与调制器相匹配的信号由信道发送出去, 接收方则进行逆的过程。无线激光通信系统一般采用脉冲位置调制(L-PPM)[2-5], L-PPM的一个超帧由若干个子帧组成。由于信道编码采用GF(2)编码[6-7], 而信源编码采用L-PPM编码, 如果由于信道噪声的存在发生误码, 基于GF(2)的纠错码不能具体指示是哪一个子帧出现了错误。这就是信道编码和信源编码不匹配所带来的麻烦。本文结合无线激光通信系统, 提出了采用和信源编码相匹配的GF(q)上纠错码解决此问题, 对纠错码的编码过程进行了详细的理论分析。
2 基础理论
伽罗华域(有限域): 对于有限个符号, 若符号数目是一素数的幂, 可定义加法和乘法, 则构成符号域为有限域。3个符号的域称为伽罗华域GF(3)。
按照代数有限域中的相关理论知识和参考文 献[8]中提到的算法和判定定理, 已经计算出≤4的首一不可约多项式(首项系数为1的不可约多项式)。在本文中考虑F3上的p(x) = x3+2x+1不可约多项式, 用其来构造BCH纠错编码, 于是在三元扩域上, 根据有限域多项式环的加法和乘法运算, 有
(1)
式中: 代表三元域上的带幺交换环, 如表1所列出的27个不同元素。

表1 GF(33)元素
Table 1 GF(33) element
有限域元素
三进制表示(aa2, ba1, ca0)
0
000
0
001
a
010
a2
100
a3=a+2
012
a4= a2+2a
120
a5= 2a2+a+2
212
a6= a2+a+1
111
a7= a2+2a+2
122
a8= 2a2+2
202
a9= a+1
011
a10= a2+a
110
a11= a2+a+2
112
a12= a2+2
102
a13= 2
002
a14=2a
020
a15=2a2
200
a16= 2a+1
021
a17= 2a2+a
210
a18= a2+2a+1
121
a19= 2a2+2a+2
222
a20= 2a2+a+1
211
a21= a2+1
101
a22= 2a +2
022
a23= 2a2+2a
220
a24= 2a2+2a+1
221
a25= 2a2+1
201
a26=1
001

因此, a 的阶为33-1=26, a 是的本原元, 所以p(a)为F3域上的本原多项式, 周期为26。
3 GF(3)域Hamming码的编译码[9]
Hamming码采用在原有数据中插入若干校验码的方式进行检错和纠错的编码技术, 是一种能够纠正单个错误的线性分组码。
设m≥2, 中共有非零向量3m-1个, 若其中任意两个非零向量是线性相关的, 那么就满足射影等价关系。在每一个等价类中共有2个向量, 所以共有个等价类, 从每个等价类中依次取一个代表向量, 可以得到码长为n, 信息位为k及最小码矩为d的Hamming完全线性码Ham[n, k, d], 记为

Ham[4,2,3]的标准生成矩阵为, 具体的译码过程如图1所示。

图1 Ham[4,2,3]译码流程
Fig. 1 Ham[4,2,3] decoding process

其中, 图1中伴随式译码列表, 是陪集代表元和相应的伴随排在一列得到的。从中看出Ham[4,2,3]可以纠正一位错误, 在有用码字个数不是很多的情况下, 采用伴随式译码方法, 不需要占用很大的存储空间, 并且译码速度有明显的提高, 传输码率为R=50%。
4 GF(3)域BCH码的编译码
BCH码是1959年由A.Hocquenghem及1960年由R.C.Bose和D.K.Ray-Chaudhuri提出的一类重要的循环码, 它的纠错性能很好, 而且具有很好的代数结构, 此码构造简单, 在工程上BCH的编码和译码相对较容易实现。
定义[9]: 设(n,q)=1, a 是Fq的扩域中的n阶元素(有(n,q)=1成立时, 一定存在a, l和d 是正整数, 2≤d≤n-1, 以为根的码长为n的q元循环码

(2)
为设计距离为d 的 BCH码。由定义可以得到BCH码的校验矩阵

由文献[9-12]中的定义可知码长为n且设计距离为d 的q元BCH码的生成矩阵为

式中: mi(x)是ai在Fq的极小多项式, 1≤i≤d -1; d 为设计距离; Lcm[]指取括号内所有多项式的最小公 倍式。
主要研究GF(3m)域上的生成多项式, 关于GF(3m)域上元素幂的表达式可查看表5-1。当m=3时, 设a是GF(33)域上本原元素, a3+2a+1是本原多项式, 根据分圆陪集可计算出以下满足条件的极小多项式。
1) a的极小多项式:

2) a2的极小多项式:

3) a4的极小多项式:

4) a5的极小多项式

5) a7的极小多项式:

6) a8的极小多项式:

设纠正错误的个数为t, 可以根据实际要求的纠错能力得到参数不同的BCH码。
当t=1时, 则

由deg( g(x))=6, 其deg()表示方阵的阶, n = 26, k = n-deg(g(x))=20, 所以可构造以g1(x)为生成多项式的BCH[26,20]。
当t=2时, 则

由deg( g(x))=9, n = 26, k = n-deg(g(x))=17, 可构造以g2(x)为生成多项式的BCH[26,17]。
当t=3时, 则
由deg( g(x))=12, n = 26, k = n-deg(g(x))=14 可构
造以g3(x)为生成多项式的BCH[26,14]。
BCH[26,17]具体的译码算法如下:
设错误多项式(错误图样)为
,
式中: 。

式中: 。
若有,
因为mk(x)是以ak的极小多项式, 有mk(ak)=0 成立,
所以
(3)
式(3)中, 当有错误发生时, 是GF(3)域不全为零的n重向量, 假定最多有t个错误发生, 则有
(4)
式(4)中, 为出错位的错误值; 发生出错位的位置。
根据上面推导过程, 可以得到以下方程组

在此假定所构成的错误位置多项 式为
(5)
公式(5)两端乘以, 代入并且从1到t求和, 可以得到

即有
(6)
由公式(6), 得出所有校正子方程组, 将它表示为矩阵形式
(7)
在接收端的具体译码流程如图2所示。
验证在通信中用BCH[26,17], 发送码字为C= , 假设信道的差错向量为E=, 经过信道传输后, 在接收端经信号检测后为R= , 即接收多项式为

若用极小多项式mk(x)除R(x), 余项为rk(x), 则有R(x)= q(x)mk(x)+rk(x), 且有

图2 BCH译码流程
Fig. 2 BCH decoding process

图3 计算校正子电路图
Fig. 3 Computing syndrome circuit
计算S1, S3如图3, 同样的方法, 可以用线性反馈移位寄存器(LFSR)电路计算出校正子S2, S4。
S1 = a17, S2 = a22, S3 = a25, S4=a22
令

所以可以得出错误位置多项式

令s(z)=0,可以计算出发生错误的位置s1=a15, s2= a。
令错误位置的错误值为y1, y2则有
(8)
所以通过解式(8)可以正确的得出发生在错误位置上的错误值为y1=1, y2=1。通过以上的计算可以看出, 若在BCH纠错能力内, 在接收端通过译码程序, 能够得到正确的发送信息。
5 结 论
设计并实现了3PPM的纠错码, 通过理论分析和仿真实验对这种纠错码进行了验证, 结果表明, 这种思路在理论上的正确性和实际中的可行性。一般无线激光通信采用16PPM编码, 进一步的工作是设计GF(17)码, 以便使信道编码可与信源编码更加紧密结合。
参考文献:
[1] 谢伟良, 刘璐, 汤俊雄. 无线光通信差错控制系统的时间参数特性[J]. 中国激光, 2004, 31(5): 575-578.
XIE W L, LIU L, TANG J X. Characterization of time parameter of error control scheme in optical wireless communication [J]. Chinese Journal of Lasers, 2004, 31(5): 575-578.
[2] 柯熙政, 席晓莉. 无线激光通信概论[M]. 北京: 北京邮电大学出版社, 2004: 148-155.
KE X ZH, X X L. Wireless laser communication conspectus [M]. Beijing: Beijing University of Posts and Telecommunications Press, 2004: 148-155.
[3] 秦岭, 柯熙政. 一种二脉冲的MPPM编码映射方法研究[J]. 西安理工大学学报, 2007, 23(3): 269-272.
QIN L, KE X ZH. A study of mapping scheme for dual-pulse MPPM[J]. Journal of Xi’an University of Technology, 2007, 23(3): 269-272.
[4] 丁德强, 柯熙政. 大气激光通信PPM调制解调系统设计与仿真研究[J]. 光通信技术, 2005. (1): 50-52.
DING D Q, KE X ZH. Design of PPM for laser communication in atmosphere[J]. Optical Communication Technology, 2005, (1): 50-52.
[5] 赵黎, 柯熙政, 刘健. OWC中DPPM调制解调技术研究[J]. 激光杂志, 2007, 28(2): 63-64.
ZHAO L, KE X ZH, LIU J. Research on differential pulse-position modulation in optical wireless communication [J]. Laser Journal, 2007, 28(2): 63-64.
[6] 许晶晶, 柯熙政. RS纠错码技术的一种应用[J]. 宇航计测技术, 2005, 25(3): 41-44.
XU J J, KE X ZH. An application of reed-solomon code technology[J]. Journal of Astronautic Metrology and Measuremen, 2005, 25(3): 41-44.
[7] 杜安源, 柯熙政. 大气激光通信系统中RS码的研究与实现[J]. 光电工程, 2004, (31): 44-47.
DU AN Y, KE X ZH. study and implementation of Reed-Solomon code in an atmospheric laser communication system[J]. Opto-Electronic Engineering, 2004, (31): 44-47.
[8] 万哲先. 代数引导[M], 北京:科学出版社, 2004: 307-339.
WAN ZH X. algebra introduction[M].Beijing: Science Press, 2004, 307-339.
[9] 陈鲁生, 沈世镒. 编码理论基础[M], 北京: 高等教育出版社, 2005: 156-158.
CHEN L SH, SH SH Y. Coding theory foundation [M], Beijing: Higher Education Press, 2005: 156-158.
[10] 冯克勤. 纠错码的代数理论[M]. 北京: 清华大学出版社, 2005: 67-75.
FENG K Q. Algebraic theory of error-correcting codes [M]. Beijing: Tsinghua University Press, 2005: 67-75.
[11] 王新梅, 肖国镇. 纠错码—— 原理与方法[M]. 西安:西安电子科技大学出版社, 2006: 242-243.
WANG X M, XIAO G ZH. Error-correcting—Theory & method[M]. Xi’an: Xi’an Electronic Science and Technology University Press, 2006: 242-243.
[12] 李军科, 张俊, 顾亚平. BCH分组码原理、实现及纠错性能分析[J]. 仪器仪表学报, 2004, 25(z1).
LI J K, ZHANG J, GU Y P. BCH encoding application and analysis of error-correcting property[J]. Chinese Journal of Scientific Instrument, 2004, 25, z1.
[13] 柯熙政, 殷致云. 无线激光通信系统中的编码理论[M]. 北京: 科学出版社, 2009: 12-38.
KE X ZH, YIN ZH Y. Coding theory in wireless laser communication system[M]. Beijing: Science Press, 2009, 12-38.
作者简介:
殷致云: 1979年出生, 博士研究生, 西安理工大学自动化与信息工程学院, 研究方向为无线激光通信系统。
E-mail: yinzy@
Yin Zhiyun: born in 1979, PhD candidate, main research interests: wireless laser communication system.

第3期 汤清虎 等: 非晶态Mn-Ce-O催化芒香醇选择氧化 7