当前位置：文档之家 › BCH码迭代译码算法及软件实现方法

BCH码迭代译码算法及软件实现方法

  • 格式：pdf
  • 大小：201.58 KB
  • 文档页数：4

２ Ｂ Ｈ 码 的 译 码 方 法 Ｃ
关 于 Ｂ Ｈ码的译码问题 ， Ｃ 一直是编码 理论研究 中
最感兴趣 的课 题 之 一。评价 一个 码 的译码 算 法 的好
Ａｂ ｔａ ｔＢａｅ ｎｔ ｅｃ ａａ ｔｒｓｉｓｏ ｓｒ ｃ ： ｓｄ ｏ ｈ ｈ ｒｃｅｉｔ ｆ ｃ ＢＣＨ ｏ ｅａ ｄ ｃｍ ｐ ｉｇ ｗｉｈｔ ｅＹ Ｙ—ｂｉａｙ Ｂ ｃ ｄ ｎ ｏ ａ ｎ ｔ ｈ ｌ ｌ ｒ Ｏ ｎ ｒ ＣＨ ｏ ｅｔ ｈ ｉａｙ Ｂ ｃ ｄ ｏ ｔｅｂｎ ｒ ＣＨ ｏ ｅ ｔ ｅｃ ｉｃｌ ｃ ｄ ，ｈ ｒｔ ａ ｉ ｃ ｄ ｆＢＭ ｌｏ ｉ ｍ ｓｐ ｅｅ ｔｄ ｗｉｈ ｅ ｈ ｓｓｏ ｈ ｕ ｄ ｍｅ ａｓｏ ｏ ｅｏ ａｇ ｒｔ ｈ ｉ ｒｓ ｎ ｅ ｔ ｍｐ ａ ｉ ｎ ｔ ｅ ｆｎ ａ ｎｔ ｆＢＭ ｌｏ ｉｈ ． ｒｈ ｍ ａｒ ， ｃｏ ｄｎ ｏｔ ｅ ｂ ｓｃａｇ ｒ ｈ ｌ ａｇ ｒｔ ｍ Ｆｕｔ ｅ ｏ ｅ ａｃ ｒ ｉｇ ｔ ｈ ａｉ ｌｏｉｍ ｔ
Ｂ Ｈ（ ａｅ ｈ ｕｈ ｒ—Ｈｏｑ ｅｇ ｅ 码 是 １５ Ｃ Ｂ ｓ —Ｃ ａｄ ｕｉ ｃｕｎ ｈｍ） ９９
意义 。在所有的译码 算法 中常用 的有 ： ｅ ｒ ｎ 法、 Ｐｔ ｓ 算 ｅｏ Ｂ ｒ ｋｍｐ ｅｌ ａ —Ｍａ ｅ 迭代算法 （ ｅ ｓｙ ｓ 简称 Ｂ 法） 欧几里得 Ｍ 、 （ ｕｌ ） Ｅ ｃｄ算法 。Ｐ ｔ ｓｎ算法适 用 纠错数较 少 的译码 ， ｉ ｅｒ ｅｏ 它 的计算量在上述 三种算法 中最大 ； 对于纠错 数较大 的Ｒ Ｓ译码器 ， 一般采用 Ｂ 算法和 Ｅ ｃｄ Ｍ ｕｌ 算法 ， ｕｌ ｉ Ｅ ｃｄ ｉ 算法 比 Ｂ 迭代 算法 容 易理 解 ， 运算 量 较大 ， 比 Ｍ 但 且 Ｂ 迭代 算法 的硬 件 结构 复 杂。另 外考 虑到 二进 制 Ｍ Ｂ Ｈ码 的特殊性 ， 以在本设 计 中采 用译码 速度快而 Ｃ 所 最常用的 Ｂ 迭代算法… Ｍ １。 在实 际应用 中用 得最多 的是码 元取 自有 限域 Ｇ Ｆ
（） ２ 中的 二进制 Ｂ Ｈ码 ， Ｃ 对于一 个正整数 ｚ 有 ： 则 取 ，ｎ １ 艿＝２ ＋１设 ａ是伽罗华域 Ｇ （ ） ７ ＝ ， ７ ｔ ， Ｆ ２ 的本原 域元素 ， 则码 以 ａ ａ ， ， 为根生成多项式 ： ， … ａ
ｇ ）＝ Ｌ Ｍ （ １ ＂２ｚ … Ⅲ２（ ） （ Ｃ （ １ （） ） １ ９ ） ｒ
维普资讯
第
７ 期 ２ ０ ４ 月 ０７ 年
计 算 机 技 术 与 发 展
（ ’ ＰＵＴＥＲ ０～Ｉ ＴＥＣＨＮＯＬ Ｘ； Ａ （ Ｙ ｒ Ⅵ 』） ｛ １ Ｐ Ｎ Ｆ
Ｖｏ１ １ Ｎ Ｏ． ．７ ４ Ａｐ ． ２ ０ ｒ ０７
Ｂ ＣＨ码迭 代译 码 算 法及 软 件 实现 方 法
李志 国， 张伟 功
（ 西安微 电子技 术研 究所 ， 西 西安 ７ ０ ７ ） 陕 １ ０ ５
摘 要 ： 合 Ｂ Ｈ码 的特点 ， 点研究 ’ ＫＨ码 中 Ｂ 迭代 译码 算法 的基本 原 理 ， 二进制 Ｉ＇ 结 Ｃ 重 Ｔｔ２ Ｍ 对 Ｋ Ｈ码与 非二 进制 Ｂ Ｈ码 怍 Ｃ
ｓ ｐ ｆ Ｍ，ｈ ｒｃｉ ｌｈｒｅｅ ｏ ｅ（０，２ ｉａａ ｚｄｔｒｕｈｔｅｔｒｅ ｔｇ ｉｅｎ ｌ ｒｈ ｃ ｉｃｕｅ Ｉ ｅｌａｉｎｂ ｔ ｓ ｔｅｐａｔ ａ ｓｏｔｎｄｃｄ ５ ３ ） ｌ ｅ ｈ ｇ ｈ ｈｅ —ｓａｅｐｐｌ ｅａ ｏｉ ａ ｈｔ ｔｒ．ｔ ｒ ｉ ｔ ｙ ｅ ｏＢ ｃ ｓｎ ｙ ｏ ｉ ｇ ｔ ｒ ｅ ｍ ｓ ａｚ ｏ
年由霍 昆格 姆 （ ｏｑｅｇ ｅ ， ９０年 由博斯 （ ｓ） Ｈ ｃｕｎ ｈｍ） １６ ａ Ｂ ｅ 和雷 ・ 查德胡里 （ ａ ｈｕｈ ｒ 提 出的纠正多个 随机 Ｒ ｙＣ ａｄ ｕｉ ） 错 误的循环码 ， 可以用生成多项式 ｇ ） （ 的根来 描述 。 它是具有严格 的代数 结构 ， 纠错能力ห้องสมุดไป่ตู้强 、 构造 简单 、 编 码较其它码容易等特点的线性分组码 。
Ｓ ｆｗａ ｅ Ｒｅ ｌｚ ｔｏ ｏ ｔ ｒ ａ ｉａ ｉ ｎ
ＬＩＺ ｉ ｕ ， ＨＡＮＧ ｅ ｇ ｎ ｈ— ｏ Ｚ ｇ Ｗ ｉ ｏｇ —
（ ｉａ ｃｏｌ ｔ ｎｃ Ｔｅｈ ｏ ｇ ｓｉ ｔ， ｉａ １０ ５ Ｃ ｉ ） Ｘ ’１Ｍｉ ｅ ｃｒ ｉ ｃｎ ｌ ｙＩ ｔ ｕｅＸ ’１ ０ ７ ， ｈｎ ２ ｒ ｅ ｏ ｓ ｏ ｎ ｔ ｉ７ ａ
Ｃ／ Ｃ＋ ＋ ｉ ｓ ｕ ｏ ｗａｄ ｓａ ｏ ｐ ｔｆｒ ｒ ． ｌ Ｋｅ ｒ ｓ： ｙ ｗｏ ｄ ＢＣＨ ｏ ｅ； ｅｏ ｉ ； ｌｉ ｆ ｌ ｓｏ ｅ ｅ ｏ ｅ；ｌｏ ｉｈ ｃｄ ｄ ｄ ｎ Ｇａｏｓ ｉｄ；ｈ ｒ ｎ ｄｃ ｄ ａｇ ｒｔｍ ｃ ｇ ｅ ｔ
１ Ｂ Ｈ码简 介 Ｃ
中图 分类号 ： Ｐ １ ５ Ｔ ３１ ２ 文献标 识码 ： Ａ 文章编 号 ：６ ３ ２ Ｘ ２ ０ ）４ １ １ ０ １７ —６ ９ （０ ７ ０ —０ ７ — ４
Ｂｉ ｒ ｎａ ｙ ＢＣＨ ｄｅ ＢＭ ｃ ｄ ｎ ｇ ｒ ｔ ｍ ｎｄ Ｃｏ Ｄｅ ｏ ｉ ｇ Ａｌ ｏ ｉｈ ａ
了简单 的 比较 ． 给出 了算法 的关 键代码 。根 据 Ｂ 迭代 译码 算法 的基本 步 骤 ， 三级 流水算 法结 构并 对实 际应 用的缩 短 Ｍ 采用
码 （０ ３ ）纠二检 四） ５ ，２ （ 译码进 行分 析 ， 同时 阐明如何应 用 Ｃ Ｃ＋＋语 言实现 该算 法 。 ／ 关键 词 ：Ｃ Ｂ Ｈ码 ； 译码 ； 限域 ； 短 码 ； 有 缩 算法

合集下载

[经济学]第四章 BCH码

[经济学]第四章 BCH码


4.5 BCH码的译码
se1 se12 ...... s1e se1
se11
se2
...... ......
s2e
se2
BCH码译码的一般原理 s2e11 s2e2 2 ... see s2e
由于BCH码是循环码的一个子类，因此BCH 码的编码可采用与循环码同样的方法。 编码方程 实际应用中，通常采用系统码形式。 其编码方程为： C(x)=xn-km(x)+[xn-km(x)]Mod g(x)
4.4 BCH码的编码
编码电路
实际应用的BCH码通常为高码率码 实现中采用n-k级编码电路
门 1~k
4.5 BCH码的译码
BCH码译码的一般原理
因此求解错误位置的问题转化成为解线性方程 组的问题。
求出系数σK得到错误位置多项式σ(x) ； 再求σ(x)的根x； 根据x=xk-1，求出xk 由xk=βLk，得到Lk，即知道错误发生的位置
EC~
4.5 BCH码的译码
BCH码译码的一般原理
因此求解错误位置的问题转化成为解线性方程组的
si = R(β i)
s6=(s3)2=(α7)2= α14
se1 se12 ...... s1e se1
4.5 BCH码的译码
se11
se2
...... ......
s2e
se2
BCH码译码的一般原理s2e11 s2e2 2 ... see s2e
Peterson译码举例：
根据求得的伴随式构造方程组：
d=2t+1 C(x)=cn-1xn-1+cn-2xn-2+…+c1x+c0 R(x)=rn-1xn-1+rn-2xn-2+…+r1x伴+随r式0译码步骤 E(x)=en-1xn-1+en-2xn-2+…1+) e根1据xR+(xe)计0算伴随式S；
BCH循环码的编码与译码

BCH循环码的编码与译码

中南大学物理与电子学院信息论与编码理论实验报告实验名称：BCH循环码的编码与译码专业班级：电子信息科学与技术1104姓名：学号：实验6 BCH循环码的编码与译码一、实验内容用VC或Matlab软件编写循环BCH码的编码与译码程序。

利用程序对教科书的例题做一个测试。

二、实验环境1.计算机2.Windows 2000 或以上3.Microsoft Visual C++ 6.0 或以上4.Matlab 6.0或以上三、实验目的1.通过BCH循环码的编码与译码程序的编写，彻底了解并掌握循环BCH的编码与译码原理2.通过循环BCH码的编码与译码程序的编写，提高编程能力。

四、实验要求1.提前预习实验，认真阅读实验原理以及相应的参考书。

2.对不同信道的进行误码率分析。

特别是对称信道，画出误码性能图。

即信道误码率与循环汉明码之间的关系。

3.认真填写实验报告。

五、实验原理1.循环BCH的编码与译码原理(略)2.循环BCH的程序实现。

六、实验步骤232t)()2(，其系数在GFα,...,α,α,α是GF2上的一个本原，t是整数，含有2t 个跟αm1.基本概念：设1-2m=为循环码生成多项式，并称为而原本预案BCH码。

参数如下：码长：n)x(上，并且最低次多项式gmt≤k-n=校验位数：r1+2t=d0≥最小码距：dmin纠错能力：t。

)(2是任意整数<3)和纠错能力ttt≥1其中m(m-m2.计算方法：，产生GF2扩域。

m)x(1算出m，遭到一个m次的本原多项式p-2=m（1）有n)()(的根，分别计2t个连续米次根)x(m（2）在GF2上找到一个本原a,一般情况下是利用本原多项式p)x(,...,m2t)x(,m2)x(域上的最小多项式m1)2(2t所对应的GFα3,...,α2,α,α⎦⎤)x(,...,m2t)x(,m3)x(m1⎣⎡LCM=)x(（3）计算2t个连续奇次幂之根所对应的最小多项式的公倍式，得到生成多项式g求得BCH码字)x(g)x(m=)x(（4）由关系式C3.程序实现：对于BCH（15,5）,有matlab实现程序如下：①BCH编码 enbch155.mfunction coded = bch155(msg_seq) %定义函数bch编码 % 输入为msg_seq信息位 % 输出为编码后的码元codedg=[1 0 1 0 0 1 1 0 1 1 1]; %生成多项式系数n=15;k=5; %默认为BCH（15，5） %% 从输入msg_seq中提取信息位msg display('信息位：')if nargin<1 %判断输入信息 ,若未输入,系统自动产生5组信息码，并显示出信息位 nmsg=5;msg=randi([0,1],[nmsg,k]) elselmsg = length(msg_seq); nmsg = ceil(lmsg/k);msg = [msg_seq(:);zeros(nmsg*k-lmsg,1)];msg = reshape(msg,k,nmsg).' endxx = [msg zeros(nmsg,n-k)]; %将输入信息码msg拓展为矩阵形式的xx %% 进行编码,将xx编码为coded coded =zeros(nmsg,n); fori=1:nmsg[q,r]=deconv(xx(i,:),g); %产生余式 r=abs(rem(r,2)); coded(i,:)=r; end coded = coded + xx; %产生信息码 end②BCH解码debch155.m M=4;code = gf(code,M); [m , n]=size(code); decode=[]; code1=[]; T2=6; N=15; mat=gf(2,M,code.prim_poly).^([N-1:-1:0]'*([1:T2]));第2/5页Tx = [0 1 zeros(1,T2-1)]; fori=1:m ;code1=code(i,:); M=code1.m;T2=6;N=15; S = code1* ((gf(2,M,code1.prim_poly)).^([N-1:-1:0]'*([1:T2]))); LambdaX = gf([1 zeros(1,T2)],M,code1.prim_poly); Tx = [0 1 zeros(1,T2-1)]; L=0; for k = 1:T2;LambdaXTemp = LambdaX;Delta = S(k) - LambdaXTemp(1+[1:L])*(S(k-[1:L]))'; ifDelta.x;LambdaX = LambdaXTemp - Delta*Tx; if 2*L < k;L = k-L; Tx = LambdaXTemp/Delta; end; end;Tx = [0 Tx(1:T2)]; end;LambdaXValue = LambdaX.x;LambdaX = gf(LambdaXValue(1:max(find(LambdaXValue))), M, code1.prim_poly); errLoc_int = roots(LambdaX);errLoc = log(errLoc_int); fori =1:length(errLoc); errorMag = 1;code1(N-errLoc(i)) = code1(N-errLoc(i)) - errorMag; end;decode=[decode;code1]; end;ccode = double(decode.x); decode = ccode(:,1:5); end③测试文件 bch_en_decode.m function bch_en_decode(msg) %编码 ifnargin<1 code=enbch155();else code=enbch155(msg); %编码 end第3/5页code=code+randerr(5,15,1:3); %模拟信道产生错误，每行有1-3个随机错误display('信道传输中干扰后,接收到的信息');coder=rem(code,2) %对2取余，使范围是0、1 display('解码后');decode=debch155(coder) end4.进行测试不输入信息位，让系统自动产生信息位，在matlab中输入下面一行代码，得到结果>>bch_en_decode() 信息位： msg =0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 0 1 0 0 0 0 0 编码后码元: coded =0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 1 1 1 0 0 0 0 1 0 1 0 0 1 1 0 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 信道传输中干扰后,接收到的信息 coder =0 0 0 1 1 1 0 1 0 1 1 0 0 1 0 0 1 1 0 0 0 0 1 0 1 1 0 1 1 0 1 1 1 1 1 1 11 0 0 1 0 1 1 1 1 0 0 0 0 0 1 1 0 1 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 解码后 decode =0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 0 1 0 0 0 0 0第4/5页输入信息位在matalb中输入下面两行代码，得到结果如下>>msg=[1 1 0 1 1 1 1 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1]; >>bch_en_decode(msg) 信息位： msg =1 1 0 1 1 1 1 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 编码后码元: coded =1 1 0 1 1 1 1 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 信道传输中干扰后,接收到的信息 coder =1 1 0 1 1 1 1 1 1 0 0 0 0 0 1 0 0 1 1 0 0 0 1 1 1 解码后 decode =1 1 0 1 1 1 1 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 11 0 0 1 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 1 0 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 1 1 1 0 0 1 1 0 0 1 1 1 1 0 1 1 1 0 0 0 1 1 0 1 0 1 1 1 0 1 1 1 1 1 0 1 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 0 1 1 0 1 1 1 1 0 1。

BCH码的译码

BCH码的译码

BCH码的常用译码方法优点：译码速度快，而且硬件实现比较容易；缺点：当错误位数比较多时，存储表格将会消耗大量的硬件资源；优点：使用的硬件资源相对较少，对错误位数不敏感；缺点：运算速度与纠错位数成线性关系，硬件复杂度较高；Gorenstein-Zierler 译码算法对于线性分组码的纠错来说，我们需要两个信息就可以确定码中存在的错误：（1） 错误发生的位置；（2） 错误的大小；Gorenstein-Zierler迭代算法的译码过程，就是利用BCH码的生成多项式的特点确定这两个信息的过程。

12211e x e x e x e e(x)n n n n ++++=---- vv i i i i i i xe x e x e e(x)+++= 2211其中 表示第 k 个错误的大小。

k i e 对于一个码长为n的BCH码，其纠错能力为t，其错误多项式.,,,21v i i i 假设实际发生了v 个错误， 0 ≤ v ≤ t。

错误发生位置为它的系数中最多有t个非零系数。

在域元素 处的伴随式其中：其中 是第k个错误的位置， 是这个位置对应的域元素。

错误大小：错误位置：在j=1,2,…,2t处，有V个未知的错误大小Y1,Y2,…,Y v)xX ()xX )(xX (x Λx Λx ΛΛ(x)v v v v v ---=+++=--111121111 错误位置的倒数 就是这个多项式的零点。

1-k X定义错误位置多项式为：⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡---=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡ΛΛΛ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡++---++-v v v v v v v v v v v v v S S S S S S S S S S S S S S S 2211112221132121 通过解这个方程组，就可以求出错误位置多项式的所有系数 的值。

i Λ1) 先尝试设 ，计算伴随式矩阵的行列式 。

tv =)det(M ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=--++-12221132121v v v v v v v v S S S S S S S S S S S S M 如果 ，说明伴随式矩阵是奇异的，接收码字中没有发生t 个错误。

缩短BCH码_16_8_5_编译码算法及其实现

缩短BCH码_16_8_5_编译码算法及其实现

2009年第2期空间电子技术S PAC E ELEC TRON IC TECHNOLO GY33缩短B CH码( 16 , 8 , 5)编译码算法及其实现李雄飞李振华邱乐德(西安空间无线电技术研究所,西安710000)摘要BCH码由于编译码简单、纠错性能好而广泛应用于工程实践中。

文章从传统编译码方法的原理、性能、优缺点及应用情况出发,推导出一种缩短BCH 码( 16, 8, 5 )的查表编译码方法。

经过VHDL仿真验证,该方法简单实用,占用硬件资源少,是工程实践中一种较好的方法。

关键词BCH码缩短BCH码查表编译码VHDL0 引言BCH码是1959年由Hocquenghem、1960年由Bose和Ray2Chaudhuri分别提出的、纠正多个随机错误的循环码,是迄今为止所发现的一类很好的线性纠错码类。

它建立在严格的数学基础上,具有很强的纠错能力,特别是在中等码长的情况下,其性能接近理论值,构造方便,编码简单,是目前应用得最为广泛的码类之一。

BCH码译码问题一直是编码理论研究中最活跃的课题之一。

BCH 码与其他各类码有及其密切的关系,因此,研究BCH码的译码无论从实际上还是在理论上都有着重要的意义。

1960年Peterson奠定了二进制BCH码译码的理论基础,稍后G o re和Zierler推广到多进制情况。

1965年Forney解决了BCH码的纠错纠删码。

1966 年Berlekamp 提出了迭代译码算法,节省了计算量,加快了译码速度,因而从实际上解决了BCH码的译码问题。

自此以后,很多学者又不断提出了新的译码方法,如欧几里得、连分式等译码算法。

1978年勃莱哈特提出了频域译码。

此后,很多作者研究了超BCH码限的超设计距离的译码问题,如能达到HT限和Ross限的译码问题。

1986年姚明余等提出了一种逐位判决纠正的BCH码译码算法,这种译码算法的译码速度较迭代译码稍快,但要求有较多的存储设备。

1996年, Lu E H和Chang T给出了一种step 2by2step 译码算法,这种译码算法的译码步骤简单,占用硬件资源较少[ 1 ] 。