标题

Size: px

Start display at page:

Download "标题"

位移牵芮
5 years ago
Views:

1 第 39 卷第 1 期西南大学学报 ( 自然科学版 ) 2017 年 1 月 Vol.39 No.1 JournalofSouthwestUniversity (NaturalScienceEdition) Jan DOI: /j.cnki.xdzk (41,21,9) 二次剩余码的快速译码武登杰 1, 包小敏 1, 瞿云云 2, 袁治华 1 1. 西南大学数学与统计学院, 重庆 ;2. 贵州师范大学数学科学学院, 贵阳摘要 : 针对 (41,21,9) 二次剩余码, 提出了一种快速的基于校验子重量的译码算法 (FSWDA). 这种译码算法结合了循环码的性质, 又巧用了校验子的汉明重量, 其最大优点是不需要存储校验子和相应的错误模式构成的表, 却能达到查表译码的效果. 另外, 本算法还可以用于其它纠错能力为 4 的二次剩余码. 关键词 : 二次剩余码 ; 查表译码 ; 错误模式 ; 伴随式 ; 汉明重量中图分类号 :O211.4 文献标志码 :A 文章编号 : (2017) 二次剩余码 ( 简称 QR 码 ) 是文献 [1] 提出的一类循环 BCH 码. 由于这类码的码率都大于或等于 1/2, [2] 所以大部分 QR 码都是比较好的纠错码. 例如 (24,12,8)QR 码已被用于航海通信. 在过去的几十年里, 关于 QR 码的译码方法已经提出很多种 [3-9], 但这些译码方法很多都采用了一些代数工具, 需要比较复杂的有限域中的计算, 从而延长了译码时间. 为减少译码复杂性, 查表译码就成为一个比较好的选择. 查表译码需要预先存储由校验子和相应的错误模式构成的表. 对于纠错能力为 4 的 (41,21, 9)QR 码, 它需要存储 4 æ41 ç = 个校验子和相应的错误模式, 存储大小为 (6bytes+ i=1 èi 3bytes) 991.3Kbytes. 文献 [4] 经过改善, 提出的算法需要存储 Kbytes. 事实上, 考虑循环码的特性, 只需存储 4 æ41 ç /41=2751 个校验子和相应的错误模式即可, 此时存储大小仅为 i=1 èi Kbytes [2]. 而文献 [5] 和文献 [6] 又进一步优化, 分别将存储大小减少到 2.47Kbytes 和 2.03Kbytes, 大大节省了存储空间. 本文继续沿用查表译码的思想, 同时又利用校验子与校验矩阵之间的关系, 提出了一种基于校验子重量的快速译码算法 (fastsyndrome-weightdecodingalgorithm,fswda). 这个算法具有运算简单存储量小的特点, 而且可以用于其它纠错能力小于或等于 4 的 QR 码. 1 (41,21,9) 二次剩余码背景知识二次剩余码是由域 GF(2) 上的生成多项式 g(x)=g0 +g1x + +gn-kx n-k 生成的一类线性循环码, 用 (n,k,d) 来表示, 其中 n=8l±1(l 为正整数 ) 为码长,k 为信息长度,d 为码的最小汉明距离.(41,21, 9)QR 码就是其中一种.m 是能满足 n 整除 2m -1 的最小正整数. 设 Qn = {j j x 2 modn,1 x (n- 1)/2}. 当 n=41 时,m =20, 且 Q41={1,2,4,5,8,9,10,16,18,20,21,23,25,31,32,33,36,37, 1 收稿日期 : 基金项目 : 国家自然科学基金项目 ( ); 贵州省教育厅青年科技人才成长项目 ( 黔教合 KY 字 [2016]130). 作者简介 : 武登杰 (1989 ), 山西运城人, 硕士研究生, 主要从事编码理论密码学的研究. 通信作者 : 包小敏, 博士, 教授.

2 2 西南大学学报 ( 自然科学版 ) htp://xbbjb.swu.edu.cn 第 39 卷 39,40}.α 是本原多项式 p(x)=x 20 +x 3 +1 的一个根. 因此, β =α u,u =(2 m -1)/n =(2 20-1)/41= 25575, 是域 GF(2 20 ) 上一个 41 阶本原根. 生成多项式 g(x) 通过 g(x)= i Q41 (x -β i )=x 20 +x 19 +x 17 +x 16 +x 14 +x 11 +x 10 +x 9 +x 6 +x 4 +x 3 +x +1 可以得到. 由 (41,21,9)QR 码的最小汉明距离 d=9, 可知它的纠错能力 t= d -1 2 =4.(41,21,9)QR 码的码字可用多项式 c(x)=c0+c1x + +c40x 40 来表示, 其中 c(x) 是 g(x) 的倍式, 即 c(x)=m(x)g(x), 这里 m(x)=m0+m1x + +m20x 20 为码的信息多项式. 当码字通过一个有噪音的信道, 接收到的多项式 r(x)=r0 +r1x + +r40x 40 是 c(x) 与错误多项式 e(x)=e0 +e1x + +e40x 40 的和. 为简单起见, 信息码字错误模式接收量和校验子分别用向量 m =[m0,m1,,mk-1],c=[c0,c1,,cn-1],e= [e0,e1,,en-1],r=[r0,r1,,rn-1] 和 s=[s0,s1,,sn-k-1] 来表示. QR 码作为循环码, 按下列方法可得它的一个生成多项式 G1[3] : G1 = ég(x) ù ég0 gn-k 0 0 ù xg(x) 0 g0 gn-k 0 = ë x k-1 g(x) û ë g0 gn-k û 对 G1 进行行初等变换, 可以得到形式为 G =[Ik,A] 的生成矩阵, 其中 Ik 是一个 k k 单位矩阵,A 是一个 k (n-k) 矩阵. 由 G 可得形如 H =[-A T,In-k] 的一个校验矩阵. 用 Hi 表示 H T 的第 i 行向量, 即对于 (41,21,9)QR 码, 矩阵 A 为 é H T = -A ù ë In-k û = [H 1 T,H 2 T,,H n T ] T é ù ë û 当给定信息向量 m =[m0,m1,,mk-1], 码字 c 通过

3 第 1 期武登杰, 等 :(41,21,9) 二次剩余码的快速译码 3 c =mg =[m0,m1,,mk-1][ik,ak (n-k)]= [m0,m1,,mk-1,p0,p1,,pn-k-1] 进行编码得到. 向量 [m0,m1,,mk-1] 和 [p0,p1,,pn-k-1] 分别为码字 c 的信息部分和校验部分. 另外, 对于接收向量 r, 它的校验子 s=rh T. 2 译码算法及相关定理为了更好了解 FSWDA 算法, 我们先给出相关的定义和结论. 需要注意的是这些结论都是针对 (n,k, d) 二进制循环码, 所有计算都在域 GF(2) 上进行, 而 H =[A T,I] 是它的一个校验矩阵. 定义 1 一个向量 z 的非零分量的个数称为向量 z 的汉明重量, 记为 w(z). 向量 a-b 的汉明重量 w(ab) 表示向量 a 和向量 b 的不同分量的个数, 又称为向量 a 和向量 b 的汉明距离. 设 e 是错误向量 e=[em ]=[e0,e1,,en-1], 其中 em =[e0,e1,,ek-1] 是信息部分 =[ek, ek+1,,en-1] 是校验部分,w(e) t,s=eh T. 下面这个结论在后面的证明中多次用到 : 定理 1 若 H =[A T,I],e=[eM,01 (n-k)] 0n, 则 w(eh T ) d -w(em ). 证因为码字的重量至少是 d,em [I,A]=[eM,eMA] 是码字, 所以 w(em )+w(ema) d. 而 s=eh T =[em,01 (n-k)][a T,I] T =em A 故 w(eh T )=w(ema) d -w(em ). 在纠错范围内, 定理 2 和定理 3 确定何时错误只出现在校验部分. 定理 2 若 e=[01 k ], 其中 w(ep ) t, 则 w(s)=w(eh T ) t. 证由 H =[A T,I] 的结构可得故 w(s)=w(ep ) t. s=eh T =[01 k ][A T,I] T =ep 定理 3 若 e=[em ], 其中 w(em ) 1,w(eM )+w(ep ) t, 则 w(s)=w(eh T ) t+1. 证此时 w(eh T )=w([em,01 (n-k)]h T + [01 k ]H T ) (d -w(em ))-w(ep )= d - (w(em )+w(ep )) 故结论成立. d -t t+1 推论 1 若 w(e) t, 则 w(eh T ) t 当且仅当 e=[01 k,eh T ]. 当 e=[em ] 时, 下面的定理给出了 ep 与 e 的伴随式和 em 的伴随式之间的一个关系. 定理 4 设 e=[em ]. 若 [em,01 (n-k)]h T =sm, 则 ep =eh T -sm. 证因为 w(ep ) w(e) t, 所以 [01 k ]=[01 k,(e- [em,01 (n-k)])h T ]= [01 k,eh T - [em,01 (n-k)]h T ]= [01 k,eh T -sm ] 结论得证. 下面的定理是我们的查表译码算法正确性的理论基础. 定理 5 设 w(e) t,e=[em ],w(em ) 1. 若 eh T =s, 则存在唯一一个 e =[e M,0] 及相应的校验子 s, 使得 w(s-s )+w(e M ) t. 此时一定有 e=[e,s-s ]. 证当 e M =em 时, 由定理 4 知 ep =s-s, 故 w(s-s )+w(e M )=w(e p )+w(em ) t, 说明存在

4 4 西南大学学报 ( 自然科学版 ) htp://xbbjb.swu.edu.cn 第 39 卷性成立. 下面只需证当 e M em 时必有 w([s-si,e i M ]) t+1, 可证明唯一性也成立. 实际上 w(s-s )+w(e M )=w([em ]H T - [e M,0]H T )+w(e M )= w([em -e M,0]H T - [0 ]H T )+w(e M ) w([em -e M,0]H T )-w([0 ]H T )+w(e M ) d -w(em -e M )-w(ep )+w(e M ) d - (w(em )+w(e M ))-w(ep )+w(e M )= d -w(e) d -t t+1 当得到接收向量 r 时, 向右循环 i 个比特可以得到 r (i) = [rn-i,,rn-1,r0,,rn-i-1]. 通过 s (i) = r (i) H 可以得到 r (i) 的校验子. 由 r=c+e 易得 r (i) =c (i) +e (i). 换句话说, 如果 r 的错误模式是 e, 那么 e (i) 是 r (i) 相应的错误模式. 根据推论 1, 若 1 w(s) 4, 则错误仅出现在 r 的校验部分 ; 若 1 w(s (n-k) ) 4, 则错误仅出现在 r 的信息部分. 设 e0 =[1,0,,0] 是 n 维向量, ej 为仅在下标为 j 的位置有错误的 n 维向量 ( 除第 j 位为 1 外, 其它位均为 0), 相应的校验子 sj = e j H T =H j,0 j k-1. 显然, 在第 i 位和第 j 位比特发生错误可用 ei + e j 来表示,Hi +H j 是 ei + e j 的校验子, 其中 0 i j k-1. 在这里可以看出, 校验子校验矩阵和错误模式的紧密联系, 这就是不需要存储校验子和错误模式构成的表却仍可查表译码的原因. 设 sdw 为第 w 步校验子 s 与 hi 的差值, 即 s-hi,fswda 算法通过 sdw 的汉明重量, 能很快地确定错误模式. 用大写字母 F,M 和 P 分别表示 r 的第一个信息比特其余信息比特和校验比特. 对于 (41,21,9)QR 码, 共有 24 种错误情况 (P,PP,PPP,PPPP,M,MM,MMM,MMMM,F,FP,MP,FPP,MPP, FPPP,MPPP,FM,FMM,MMP,FMMM,MMMP,FMP,FMPP,MMPP,FMMP), 覆盖了所有 4 i=1 æ41 ç = 个错误模式. 如果 w(s)=0, 那么接收向量 r 没有错误. 如果 1 w(s) 4 或者 1 èi w(s (20) ) 4, 那么可以解决 8 种错误情况 (P,PP,PPP,PPPP,M,MM,MMM,MMMM). 计算 sd3 = (s-hi),0 i 20. 如果 1 w(sd3) 3, 那么又可解决 7 种错误情况 (F,FP,MP,FPP,MPP,FPPP, MPPP). 若还没解决, 则继续计算 sd4 =(s (20) -hi),0 i 20. 如果 1 w(sd4) 3, 那么又有 5 种错误情况 (FM,FMM,MMP,FMMM,MMMP) 被检测解决. 若仍未解决, 则再计算 sd5 =(s-hi -h j ), 0 i 19,i+1 j 20. 如果 1 w(sd5) 2, 那么 3 种错误情况 (FMP,FMPP,MMPP) 能被检测解决. 若上述还不能找到错误, 则需要计算 sd6 =(s (20) -h20 -hi),0 i 19. 如果 w(sd6)=2, 那么一定属于 (FMMP) 这种错误情况. 表 1 列出了 FSWDA 算法每一步能解决的错误情况及相应的错误模式数量. FSWDA 算法具体译码步骤如下 : 1) 错误情况为 (P,PP,PPP,PPPP). 根据推论 1, 计算 s 和 w(s). 如果 0 w(s) 4, 那么错误模式 e=[01 21,s]. 跳至 7); 2) 错误情况为 (M,MM,MMM,MMMM). 根据推论 1, 计算 w(s (20) ). 如果 1 w(s (20) ) 4, 那么错误模式 e (20) =[01 21,s (20) ], 也就是说,e=[01 1,s (20),01 20], 跳至 7); 3) 错误情况为 (F,FP,MP,FPP,MPP,FPPP,MPPP). 计算 sd3 =(s-hi),0 i 20. 如果 0 w(sd3) 3, 那么错误向量 e= ei + [01 21,sd3]. 跳至 7); 4) 错误情况为 (FM,FMM,MMP,FMMM,MMMP). 计算 sd4=(s (20) -hi),0 i 20. 如果 1 w(sd4) 3, 那么错误向量 e (20) = ei + [01 21,sd4], 也就是说,e= e[i-20]+ [01 1,sd4,01 20], 其中, e 的下标 [x] 表示 x 模 41. 跳至 7); 5) 错误情况为 (FMP,FMPP,MMPP). 计算 sd5 =(s-hi -h j ),0 i 19,i+1 j 20. 如果 1 w(sd5) 2, 那么错误向量 e= ei + e j + [01 21,sd5]. 跳至 7);

5 第 1 期武登杰, 等 :(41,21,9) 二次剩余码的快速译码 5 6) 错误情况为 (FMMP). 计算 sd6 =(s (20) -h20 -hi),0 i 19. 如果 1 w(sd6) 2, 那么错误模式 e (20) = e20 + ei + [01 21,sd6]. 也就是说,e= e0 + e[i-20]+ [01 1,sd6,01 20], 跳至 7); 7) 计算 c=r+e. 跳至 8); 8) 结束. 表 1 (41,21,9)QR 码的错误情况及相应的错误模式数量步骤错误情况错误模式数量错误情况错误模式数量 P PPP M MMM PP PPPP MM MMMM F 1 FP MP MPPP MPPP FM MMP MMMP FMP MMPP 6 FMMP ç ç =400 FPP FPPP ç ç =22800 FMM FMMM ç ç =22800 ç ç =400 FMPP ç ç =36100 ç =4845 è4 ç =4845 è4 本文利用 Matlab 对 (41,21,9) 码纠错范围内的所有种错误进行模拟测试, 所需平均译码时间大约为 s, 并与文献 [5-6] 中提出的算法进行对比, 运算速度基本相当, 但其突出特点是能够节省存储空间, 对于存储能力有限的终端, 特别是移动终端来说具有一定实际意义. 参考文献 : [1] PRANGEE.SomeCyclicError-CorrectingCodeswithSimpleDecodingAlgorithms[R].Cambridge:AirForceCambridgeResearchCenter,1958. [2] WICKERSB.ErrorControlSystemsforDigitalCommunicationandStorage[M].NewJersey:PrenticeHal,1995. [3] MCELIECERJ.TheTheoryofInformationandCoding [M].2nded. 北京 : 电子工业出版社,2002. [4] CHEN Y H,CHIENCH,HUANGCH,etal.EficientDecodingofSystematic(23,12,7)and(41,21,9)QuadraticResidueCodes[J].JournalofInformationScienceandEngineering,2010,26: [5] LIN TC,LEE HP,CHANG H C,etal.HighSpeedDecodingoftheBinary(47,24,11)QuadraticResidueCode[J].

6 6 西南大学学报 ( 自然科学版 ) htp://xbbjb.swu.edu.cn 第 39 卷 InformationSciences,2010,180: [6] LEE H P,CHANG H C.A MemoryImprovementonDecodingofthe(41,21,9)QuadraticResidueCode[J].InternationalJournalofComputerTheoryandEngineering,2012,4: [7] ELIA M.AlgebraicDecodingofthe(23,12,7)GolayCodes[J].IEEETransactionsonInformationTheory,1987,33: [8] WOLFMANNJ.APermutationDecodingofthe(24,12,8)Golaycode[J].IEEETransactionsonInformationTheory, 1983,29: [9] HER,REEDIS,TRUONGTK,etal.Decodingthe(47,24,11)QuadraticResidueCode[J].IEEETransactionson InformationTheory,2001,47: OnFastDecodingof(41,21,9)QuadraticResidueCode WU Denḡjie 1, BAO Xiao-min 1, QU Yunȳun 2, YUANZhi-hua 1 1.SchoolofMathematicsandStatistics,SouthwestUniversity,Chongqing400715,China; 2.SchoolofMathematicsScience,GuizhouNormalUniversity,Guiyang550001,China Abstract:ThebinaryQRcodesareafamilyoflinearcyclicBCH codes.inthispaper,afastsyndromeweightdecodingalgorithm (FSWDA)hasbeenpresentedtodecodeuptofourpossibleerrorsinabinary systematic(41,21,9)quadraticresidue(qr)code.themainideaoffswdaisbasedonthepropertyof cycliccodestogetherwiththeweightofsyndromediference.theadvantageofthefswdadecodingalgorithmovertheprevioustablelook-up methodsisthatithasnoneedofalook-uptabletostorethesyndromesandtheircorrespondingerrorpaternsinthememory.moreover,itcanbeextendedtodecodeal four-error-correctingbinaryqrcodes. Keywords:quadraticresiduecode;tablelook-updecoding;errorpatern;syndrome;hammingweight 责任编辑张栒

7 第 1 期武登杰, 等 :(41,21,9) 二次剩余码的快速译码 7

标题

第 35 卷第期西南大学学报 ( 自然科学版 ) 3 年月 Vol.35 No. JouralofSouthwestUiversity (NaturalScieceEditio) Feb. 3 文章编号 :673 9868(3) 69 4 一类积分型 Meyer-KiḡZeler-Bzier 算子的点态逼近赵晓娣, 孙渭滨宁夏大学数学计算机学院, 银川 75 摘要 : 应用一阶 DitziaṉTotik