当前位置：文档之家 › 第六章 循环码的译码

第六章 循环码的译码

  • 格式：ppt
  • 大小：328.00 KB
  • 文档页数：45

下载文档原格式

  / 45

合集下载

循环码

循环码
a
b
c
u3u2u1u0
u3u2u1u0 c2 c1c0
a
b
c
除法过程： 除法过程：
u3u2u1u0
[ x { x ( x[ u3 x3 ]mod g(x) + u2x3 )mod g(x) + u1x3 }mod g(x) + u0x3 ]mod g(x)
1 0 u 0 1 0 1 1 ×3' c ' 0d 0 0
例如：( 7, 4 )循环码的生成多项式为：g(x)=( x3 + x + 1 )，求其系统码的生成矩阵 )循环码的生成多项式为 循环码的生成多项式为： )， 例如： 1）n = 7，k = 4，因此生成矩阵阶数：4×7。其中单位阵Ik为4×4，Q矩阵4×3 7， 4，因此生成矩阵阶数： 其中单位阵I 矩阵4
BCH码 BCH码
是一类能纠正多个随机错误的循环码 其生成多项式为： 其生成多项式为：
g ( x) = LCM [ m1 ( x), m3 ( x),L , m2t −1 ( x) ]
其中m 为素多项式， 为纠错个数，LCM表示取最小公倍数 其中mi(x)为素多项式，t为纠错个数，LCM表示取最小公倍数，最 表示取最小公倍数， 小码距d 2t 小码距d ≥ 2t+1 BCH码分为两种： BCH码分为两种： 码分为两种 1）本原BCH码：码长n = 2m - 1 本原BCH码 码长n 2）非本原BCH码：码长n为2m - 1的因子 非本原BCH码 码长n 其中m 其中m表示素多项式的次数
有y = c + e，即y(x) = c(x) + e(x) ，则： e， e(
CRC码 CRC码
即循环冗余校验码，广泛用于数据通信和移动通信中，进行数据的校验，具有 即循环冗余校验码，广泛用于数据通信和移动通信中，进行数据的校验， 实现简单，检错能力强。其原理为： 实现简单，检错能力强。其原理为： 然后除以生成多项式g 1）任意长的信息位向左移动r位，即xru(x)，然后除以生成多项式g(x)得到的 任意长的信息位向左移动r 余数附加在信息码之后形成码组c 然后进行发送； 余数附加在信息码之后形成码组c(x)，然后进行发送； 2）接收端接收到码组y(x)，然后除以g(x)，如果能整除则表示无错发生，否 接收端接收到码组y 然后除以g 如果能整除则表示无错发生， 则表示有错 详细过程： 详细过程： 1）信息位为u(x)，先向左移动r位，即xru(x)。求余式[xru(x)]mod g(x)= r(x) 信息位为u 先向左移动r 求余式[ 2）则将c(x) = xru(x) + r(x)发送出去 则将c 3）若用e(x)表示可能的错误，则接收到 y(x) = c(x) + e(x) = xru(x) + r(x)+e(x)， 若用e 表示可能的错误， )+e 那么校验方法： 那么校验方法： [y(x)]mod g(x)=[xru(x) + r(x) + e(x) ]mod g(x) = r(x) + r(x) + [ e(x) ]mod g(x) =[x

第6章 差错控制编码

第6章 差错控制编码
端重发，直到正确收到为止。所谓检测出错码是
指在若干接收码元中知道有一个或一些是错的，
但不一定知道该错码的准确位置。采用这种差错
控制方法需要具备双向信道。
第6章 差错控制编码技术
检错重发法（ARQ）原理方框图
第6章 差错控制编码技术
ARQ方式的主要优点：
（1）只需要少量的多余码元就能获得极低的
输出误码率；
lim
s
c lim
s
B log 2 (1
s ) n0 B
第6章 差错控制编码技术
(2) 减小噪声功率N (或减小噪声功率谱密度n0)可以增加信 道容量，若噪声功率趋于零(或噪声功率谱密度趋于零)，则信 道容量趋于无穷大，即：
s lim 0 c lim 0B log 2 (1 N ) N N
及代码选择由某一事先确定的规则来决定，收端接收到这
样的编码后，根据已知的规则，对接收信息进行检验，发 现、纠正和删除错误。下面我们举例说明差错控制编码的 原理。
第6章 差错控制编码技术
假设要发送一组具有八个状态的数据信息
“000”（晴），“001”（云），“010”（阴）， “011”（雨），“100”（雪），“101”（霜）， “110”（雾），“111”（雹）。我们首先要用二 进制码对数据信息进行编码，显然，用3位二进制
1在一个码组内要想检出e位误码要求最小码距为mine12在一个码组内要想纠正t位误码要求最小码距为min2t13在一个码组内要想纠正t位误码同时检测出e位误码et要求最小码距为minte1差错控制编码技术显然要提高编码的纠检错能力不能仅靠简单地增加监督码元位数即冗余度更重要的是要加大最小码距即码组之间的差异程度而最小码距的大小与编码的冗余度是有关的最小码距增大码元的冗余度就增大但码元的冗余度增大最小码距不一定增大

循环码编译码实验ppt课件

循环码编译码实验ppt课件
X 1 X 1 4 X 1 3 X 1 2 X 1 1 X 9 0 X 8 X 7 X 6 X 5 X 4 X 3 X 2 X 1 X 0
SE•HT
CP K1 K2
1 1 1 1 0 0 1 0 0 0 0 0 0 0 0
0 1 1 1 1 0 0 1 0 0 0 0 0 0 0
0 0 1 1 1 1 0 0 1 0 0 0 0 0 0
2、封锁性：循环码中任两个码组之和〔模2〕必定为该码组集合中的一个码组。 如 0100110+ 0010010=0110100也为一个码组
〔二〕生成多项式与编译码电路的关系
编码：循环码的码多项式可表示为 到的余式，代表监视位。结论：只需知道
，其中 为 就能构造编码器。
与 相除得
译码：由于 就可以构造一个除法电路，把接纳码组除以 字没有错码，否那么有错码。
数字通讯原理实验 循环码编、译码实
验
指点教师:李冰、梁仕文
一、实验目的
❖ 1. 了解生成多项式g(x)在循环码编码器和译码器之间的关系。 ❖ 2.了解码距与纠、检错才干之间的关系。
二、循环码引见
〔一〕循环码是一类很重要的线性码，具有循环性和封锁性。
1、循环性：循环码中任一码组循环一位〔将最右端的码移至左端〕以后，仍为该 码中一个码组。如0100110为一个码组，那么0010011也为一个码组。
随
发生2个错码
其中一个错码在正交位（e14）上 A3 A2 A1 A0中有三个“1”
式
两个错码均在非正交位上
A3 A2 A1 A0中有两个“1”或0个“1”
修
发生3个错码
超出纠错范围，不研究
正
结论：当三个或以上的正交方程为1时，正交位有 错码，需求纠错；当三个以下的正交方程为1时，

循环码的编码电路6.6循环码的译码6.7循环汉明码

循环码的编码电路6.6循环码的译码6.7循环汉明码

*
*
6.5 循环码的编码电路
*
6.5.1 非系统码编码电路
循环码码式是生成多项式倍式。 非系统编码电路/循环码乘法编码电路 输入 a(x)=m(x)， m(x)的次数 <k 输出 a(x)g(x)=C(x)即是码式，C(x)的次数 <n 举例：生成 (7,4) 汉明码的生成多项式为 g(x)=x3+ x2+1，非系统编码电路如图6.13所示。电路共工作7个时钟节拍。
*
6.5.2 系统码编码电路
*
(2) 用 (n－k) 级移位寄存器实现的编码电路 循环码编码电路结构和工作原理 工作原理：二元 (n,k) 循环码的编码是将信息多项式 m(x) 乘 xn－k 后再除以生成多项式 g(x) 求出它的余式，即为监督数字多项式 r(x)。 二元 (n,k) 循环码的编码电路就是以 g(x) 为除式的除法电路，而输入的被除式为 xn－km(x) 。 实际的编码电路如图6.15所示。 其级数等于 g(x) 的次数 (n－k) ； 反馈连接决定于 g(x) 的系数 当 gi=0 时 (i=0,1,2,…, n－k)，反馈断开； 当 gi=1 时，对应级加入反馈。
*
*
6.6.1 接收矢量伴随式计算
设 E(x) 为 R(x) 的错误图样，那么 R(x)=C(x)+E(x)，由于 C(x)为 g(x) 的倍式，所以
S(x)≡C(x)+E(x)≡E(x) (mod g(x)) 上式表明：伴随式是由错误图样决定的，与具体码字无关。 说明：循环码伴随式的表示式 (6.4) 是由系统码推出的，但由于伴随式仅与错误图样有关，因而对非系统码也是适用的。
工作过程：
x7+1=(x+1)(x3+x+1)(x3+x2+1) 任取一个三次因式为监督多项式 h(x)=x3+x+1 得 h3=1, h2=0, h1=1, h0=1

循 环 码

循 环 码

（2） 求 R(x) ： R(x)是 xr m(x)除以 g(x) 得到的余项。
xr g
mx x
Qx
Rx gx
（3）将R(x) 加在信息位之后作为监督码，组成多项式A(x)。
Ax xr mx Rx
则码编码电路
表 10.6 (7,3)循环码的编码过程
现代通信原理
循环码
1.1 循环码的基本概念
循环码是一种具有循环性的线性码(具有封闭性) 。 一个(n, k) 线性分组码, 如果每个码组任意循环移位
后仍然是一个线性分组码 , 则称此码组为循环码。
例（7，3）循环码：g(x)= x4 + x3 + x2+ 1
表 10.5 (7,3)循环码
为了利用代数理论研究循环码，可以将码组用代数多
2. 译码过程
循环码的译码可以分三步进行：
（1）由接收到的码多项式B(x)计算校正子（伴随式）多项 式S(x)； （2）由校正子S(x)确定错误图样E(x)； （3）将错误图样E(x)与B(x)相加，纠正错误。
检错： 设接收码组为B(x), 作B(x) / g(x), 若能除尽（余
式为0），则B(x)为码多项式，表示传输无错码；若余 式不为0，则有错码。
纠错: 建立 B(x) / g(x) 的余式与错误图样的一一对应关
系。根 据余式得到错误图样E(x) , 则A(x)＝ B(x) －E(x)
或通过计算校正子S， 利用类似 表10－4的关系，确定错 码的位置。
由上述分析可知，只要找到循环码的生成多项式g(x)， 就决定了编码、译码、纠错能力。
但在实际的系统设计中，往往要按给定的纠正随机错 误的个数来寻找 g(x)。
＋
D0

第6章 循环码的译码

第6章 循环码的译码
(5.1.9) 式(5.1.7)和 (5.1.9)就是循环码的系统码形式G矩阵和 H矩阵的一般表示形式。
第6章 循环码的译码 章
% x n −1 n−2 % x S = R ⋅ H T = ( rn − 1 , rn − 2 , L r1 , r0 ) M (m od g ( x )) 1 % x x0 % % x n −1 (m od g ( x )) = ( c n −1 , c n − 2 , L c1 , c 0 ) M x0 % % x n −1 + ( e n − 1 , L e1 , e 0 ) M (m od g ( x )) x0 %
第6章 循环码的译码 章
在q进制时， 若码要纠正≤t个错误， 则错误图 样代表共有 t j n − 1 N1 = ∑ ( q − 1) (6.1.6) j − 1 j =1 个。译码时，只要知道此代表图样的伴随式，该类其 它错误图样的伴随式都可由此代表图样伴随式在伴随 式计算电路中得到。这样，就使得循环码译码器的错 误图样识别电路大为简化，由原来识别
共k个， 它们的系数就组成了系统码G矩阵的行。
第6章 循环码的译码 章
(Review2)
1 0 G= M 0
% 0 L 0 − r1 ( x ) %2 ( x ) 1 0 L 0 −r = [ Ik M R] M M M M %k ( x ) 0 1 −r
(5.1.7)
第6章 循环码的译码 章
一、 伴随式计算和错误的检测 设发送的码字C=(cn-1，cn-2，…， c1， c0)， 信道产生的错误图样为E=(en-1，en-2，…， e1， e0)， 译码器收到的n重 R=C+E=(cn-1+en-1， cn-2+en-2， … ， c1+e1， c0+e0) =(rn-1， rn-2， …， r1， r0) r i=c i+e i

循环码的编译码方法..

循环码的编译码方法..***************** 实践教学****************** 兰州理工大学计算机与通信学院2013年秋季学期《计算机通信》课程设计题目：(15,7)循环码的编译码方法专业班级：通信工程一班姓名：学号：指导教师：成绩：摘要本次课程设计研究的是循环码的编译码方法，在设计过程中，首先要介绍了线性分组码的编码和译码原理，并介绍了循环码的定义及其相关内容；其次给定的生成多项式g?x?求解出了生成矩阵和监督矩阵，并且利用MATLAB编写循环码的编码器和译码器代，实现编码及译码功能；求出该码的最小码距，并分析讨论该码的纠错能力以及在高斯信道下的误码性能。

关键词: 循环码；编码；译码；MATLAB 目录一前言............................................................... ..................................................................... .................................. 1 二循环码编译码的基本原理............................................................... ...................................................................2 循环码的简介............................................................... ..................................................................... ......... 2 循环码的定义............................................................... ....................................................................2 线性分组码与循环码的区别............................................................... ............................................3 循环码的最小码距............................................................... ............................................................ 3 循环码的检纠错能力...............................................................环码编译码原理及过程............................................................... (4)循环码的编译码原理............................................................... ........................................................ 4 循环码编译码的............................................................... (5)三系统分析............................................................... ..................................................................... .......................... 7 循环码编译码方法的实现框图............................................................... ................................................. 7 循环码编译码实现过程............................................................... . (8)四系统设计....................................................................................... 10 生成矩阵和监督矩阵............................................................... . (10)循环码的编码............................................................... ..................................................................... ....... 10 循环码的的译码............................................................... ..................................................................... ... 11 循环码在高斯信道下的误码性能............................................................... ............................................ 13 总结............................................................... ..................................................................... .. (14)线性分组码与循环码的区别线性分组码是同时具有分组特性和线性特性的纠错码。

实验6 BCH循环码的编码与译码

实验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 的程序实现。

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

参数如下： 码长：12m n -=校验位数：r n k mt =-≤ 最小码距：min 021d d t ≥=+ 纠错能力：t 。

其中(3)m m ≥和纠错能力t ()12m t t -<是任意整数2.计算方法：（1）有21mn =-算出m ，遭到一个m 次的本原多项式()p x ，产生()2mGF 扩域。

（2）在()2mGF 上找到一个本原a,一般情况下是利用本原多项式()p x 的根，分别计2t 个连续米次根232,,,...,t αααα所对应的()2GF 域上的最小多项式()()()122,,...,t m x m x m x（3）计算2t 个连续奇次幂之根所对应的最小多项式的公倍式，得到生成多项式()()()()132,,...,t g x LCM m x m x m x =⎡⎤⎣⎦（4）由关系式()()()C x m x g x =求得BCH 码字3.程序实现：对于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中提取信息位msgdisplay('信息位：')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编码为codedcoded =zeros(nmsg,n);fori=1:nmsg[q,r]=deconv(xx(i,:),g); %产生余式r=abs(rem(r,2));coded(i,:)=r;endcoded = coded + xx; %产生信息码end②BCH解码debch155.mM=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]));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.mfunction bch_en_decode(msg) %编码ifnargin<1code=enbch155();else code=enbch155(msg); %编码endcode=code+randerr(5,15,1:3); %模拟信道产生错误，每行有1-3个随机错误display('信道传输中干扰后,接收到的信息');coder=rem(code,2) %对2取余，使范围是0、1display('解码后');decode=debch155(coder)end4.进行测试法一：不输入信息位，让系统自动产生信息位，在matlab中输入下面一行代码，得到结果>>bch_en_decode()信息位：msg =0 0 1 1 11 1 1 0 01 1 1 1 11 0 0 0 10 0 0 0 0编码后码元:coded =0 0 1 1 1 1 0 1 0 1 1 0 0 1 01 1 1 0 0 0 0 1 0 1 0 0 1 1 01 1 1 1 1 1 1 1 1 1 1 1 1 1 11 0 0 0 1 1 1 1 0 1 0 1 1 0 00 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 00 1 1 0 0 0 0 1 0 1 1 0 1 1 01 1 1 1 1 1 1 1 0 0 1 0 1 1 11 0 0 0 0 0 1 1 0 1 0 1 1 0 00 0 0 0 0 0 1 1 0 0 0 0 0 1 0 解码后decode =0 0 1 1 11 1 1 0 01 1 1 1 11 0 0 0 10 0 0 0 0法二：输入信息位在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 11 1 1 1 10 0 0 0 10 0 0 1 00 0 0 0 1编码后码元:coded =1 1 0 1 1 1 0 0 0 0 1 0 1 0 01 1 1 1 1 1 1 1 1 1 1 1 1 1 10 0 0 0 1 0 1 0 0 1 1 0 1 1 10 0 0 1 0 1 0 0 1 1 0 1 1 1 00 0 0 0 1 0 1 0 0 1 1 0 1 1 1 信道传输中干扰后,接收到的信息coder =1 1 0 1 1 1 0 0 0 0 1 0 1 0 11 1 1 1 0 0 1 1 1 1 1 1 0 1 10 0 0 0 1 0 1 1 0 1 1 0 1 1 10 0 1 1 0 1 1 0 1 0 0 1 1 1 00 0 1 1 1 0 1 0 0 1 1 0 1 1 1 解码后decode =1 1 0 1 11 1 1 1 10 0 0 0 10 0 0 1 00 0 0 0 1。

第六章循环码的译码


由（1）式得w(ep(x))= w(s(x)- sI(x) )，所以
w(s(x)- sI(x) ) t-w(Q(x)) 作为判断信息位错误图样是否是Q(x)的条件（充分条
件未证）。
e(x)=Q(x)xn-k+s(x)-sI(x)
对于戈莱码：Q1(x)=0, Q2(x)=x5, Q3(x)=x6。 取g(x)=x11+x10+x6+x5+x4+x2+1 由（2）可得：
三、扩展汉明码的译码
报警 异 或
r(x)
+
s0
+ s1
s2
+ s∞
7级缓冲器
e(x)=x6
+ c(x)
s0/s1/s2 s 0
1
0 01
无错
1 10
t 3, 不能 纠错
t2，不 能纠错
t=1，可 以纠错
四、缩短循环码的译码
缓存：k->k-i r(x)先移位i次
五、捕错译码----原理
1. 原理
12
C023
C123
C
2 23
C323
=1+23+23*22/2+23*22*21/(2*3) 0
11
223-12=211=2048
=1+23+23*11+23*77 =1+23(1+11+77) =1+23*89 =2048
1
10
2
监督元位
9
3
4
8
5
6
7
对于错误图样e(x)=x22+x11（图中打叉的两个点）或e(x)=x17+x11+x6 （图中三个空 心园点）,不能通过循环移位把所有的错误移动11个监督位中，所以不能采用简单 的捕错译码法。

循环码编译码工作过程

循环码编译码工作过程可以概括为以下几个步骤：一、循环码编码过程1. 生成多项式选择：循环码的编码过程中，需要选择合适的生成多项式，以便将输入的数据符号转换成循环码序列。

常见的生成多项式有GF(2^m)中的最小多项式、标准多项式等。

2. 输入数据符号的编码：将输入的数据符号转换成二进制码字，可以采用简单的模2加法或利用编码算法进行转换。

3. 生成多项式扩展：将二进制码字通过生成多项式进行扩展，得到循环码的码字。

由于循环码是循环移位对称的，因此可以通过将码字循环移位得到不同的码字。

4. 校验位添加：根据循环码的校验规则，添加校验位，以确保编码后的码字是正确的循环码序列。

二、循环码解码过程1. 循环移位：将接收到的码字进行循环移位，使其与发送的码字匹配。

2. 校验位检查：根据循环码的校验规则，检查接收到的码字中的校验位是否正确。

3. 错误检测与纠正：如果校验位不正确，需要根据错误的位置和大小进行错误检测和纠正。

如果错误数量较少且位置相对固定，可以采用简单的错误纠正算法；如果错误数量较多或位置不固定，则需要利用更复杂的算法进行错误检测和纠正。

4. 数据恢复：根据解码过程中得到的正确的二进制码字，恢复原始数据符号。

需要注意的是，循环码的编码和解码过程都涉及到多项式的运算，因此需要选择合适的算法和工具进行实现。

同时，为了保证编码和解码的正确性和效率，还需要对传输过程中的干扰和噪声等因素进行考虑和处理。

在实现循环码的过程中，可以采用硬件或软件的方式。

对于硬件实现，可以利用数字电路和微处理器等技术进行设计；对于软件实现，可以利用编程语言和算法库等进行编写。

在实际应用中，需要根据具体的需求和环境选择合适的方式。

总之，循环码是一种重要的编码技术，具有较高的可靠性和效率。

了解循环码的编译码工作过程，对于在实际应用中实现循环码、优化编码和解码性能、提高通信系统的性能具有重要意义。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

6
2
mod x x 1
mod x
3

3


x 1
循环汉明码译码电路
[7,4,3]循环汉明码的生成多项式为x3+x+1
6 ~ H x

T
~ x5
T
~ x4
T
~ x3
T
~ x2
T
~ x1
T
1 1 1 0 1 0 0 0 1 1 1 0 1 0 1 1 0 1 0 0 1
State Key Laboratory of Integrated Services Networks
第六章 循环码的译码
循环码的译码
一般译码原理 捕错译码 大数逻辑译码
State Key Laboratory of Integrated Services Networks
一、一般译码原理
基本思想与线性分组码类似
软判决译码准则
码字错误概率最低：广义最小距离译码、Chase 译码 码元错误概率最低：APP译码、逐位译码、重量 删除译码
几类最佳译码 最小欧几里德距离译码
max p( R | Cl ) min (ri cli ) 2
i 1 n
最大内积译码（最大相关译码）
min dE max R Cl
错误集中在n-k个校验元上的条件
纠正t个错误的GF(q)上的[n,k]循环码，捕错译码 过程中，已把t个错误集中在Ri(x)的最低次n-k 位 以内的充要条件是：
wS i x t
其中w(Si(x))是伴随式Si(x)的重量
Ex en1 x n1 enk x nk enk 1 x nk 1 e0
en k x
nk
k 1 x
k 1
en k

S I j x x
nk
Qx modg x
修正捕错译码原理
因此，如果能找到一个k-1次多项式Q(x) ，使 错误图样E(x)或E(x)的循环移位在前k位码段 内与Q(x)一致，即可找到最终的错误图样
覆盖多项式的数目
对于纠正t个错误的GF(q)上的[n, k]循环码， 当且仅当R<2/t时，覆盖多项式集合必存在。 对于t=2，覆盖多项式{Qj(x)}中，最少的多 项式数目为
j n /(2(n k ))
State Key Laboratory of Integrated Services Networks
0 T ~ x mod g x
非门
与门
输入R(x) 门
七级缓存
循环汉明码译码电路 (需要14移位)
Example：设计一个由g(x)=x4+x3+1 生成的[15,11]循环汉明码译码电路。
基本要求：需要一个除法电路和一个逻辑电路
要设计逻辑电路，须知道该码可纠正的错误图样及伴随式 汉明码可纠一个错误，只需知道一个错误图样的伴随式
修正的捕错译码
当循环码的信息比特数k等于n/t或比n/t稍大时，可 采用某种方法，将大部分错误集中在n-k位上，而 把个别错误集中在固定的某几位上，即可实现修正 的捕错译码
固定几位错误 大部分错误
修正捕错译码原理
E I x en 1 x x x
nk nk
n 1
Qx
e
编码增益和软判决增益
在某一误码率下，应用一定的纠错码系统后，相对于没有 应用时所获得的信噪比减少的分贝数称为此纠错码的编码 增益 高信噪比时所获得的编码增益称为渐进编码增益 码率R,纠t个错误，AWGN信道，硬判决译码 t 1 pb Kpe K (Q((2REb / N0 )1/ 2 ))t 1 未应用纠错码，AWGN信道
伴随式又可由校验矩阵H得到
扩展汉明码的译码
缩短循环码的译码
扩展汉明码的译码
扩展汉明码的码长是8的整数倍。 扩展汉明码d=4，能纠正一个错误同时发现两个错 误。 译码电路主要部分与循环汉明码译码器相同，需 要加上检错电路。
State Key Laboratory of Integrated Services Networks
1、根据接收序列R计算伴随式S=RHT(n-k维向量) 2、根据伴随式S寻找错误图样E 3、根据错误图样E估计码向量C’， 进而计算信息序列
伴随式计算的多项式表示
R Rx rn1 x
n1
rn2 x
c n 2 x en 2 x
n 2
r0
c 0 e0
S1 x xS x
mod g x
循环码计算伴随式电路的特点
推论：xjR(x)的伴随式Sj(x)≡xjS(x) (mod g(x))， j=0， 1， …， n-1。 而任意多项式a(x)乘R(x)所对应的伴随式 Sa(x)≡a(x)S(x) (mod g(x))
在 q 进制时， 若码要纠正 ≤ t 个错误， 则错误图样代表共有 t j n 1 N1 ( q 1) j 1 j 1
' ' pb KQ[(2Eb / N0 )1/ 2 ]
dh 1 ) 硬判决渐进编码增益：G 10 lg R(t 1) 10 lg R( 2
C Cx cn1 x E Ex en1 x
n1
n 2
n1
n 2
nk 1 n k 2 S S x s nk 1 x s n k 2 x s0
系统循环码的一致校验矩阵H
n 1 T ~ n 2 ~ H x , x
使得循环码译码器的错误图样识别电路大为简 化， 由原来识别N2个图样减少到N1个
N2
j 1
t
n j j ( q 1)
Example:循环码生成多项式g(x)=x3+x+1， 计算E(x)=x6和E(x)=x5的伴随式
x x 1
x x x 1
5 2


T
1 T ~0 ~ , x , x

T

(mod g ( x))
S RH T
~ x n 1 ~ x n2 rn 1 , rn 2 , r0 x n 1 x n 1 n2 n2 ~ ~ x x c n1 , c n 2 , c0 mod g x e n 1 , e n 2 , e0 mod g x 0 0 ~ ~ x x
n2
m
m k i 0 i
r
nk
m r 1

i 0
m i
r阶RM码是r+1步大数逻辑可译 码
极长码
对任何整数m>=2，均存在有如下参数的极 长码：n=2m-1，k=m, d=2m-1。码的生成多 项式g(x)=(xn-1)/p(x)。p(x)是一个m次本原 多项式。 极长码是汉明码的对偶码。 一步大数逻辑译码
软判决译码
软判决译码是最佳译码的折衷
软判决译码
软判决距离：二进制输入Q元输出的DMC中，最 大似然译码近似等价于最小软判决距离译码 软判决重量wls 软重量和汉明重量关系：wls=(Q-1)wlh 一个最小距离为dh的二进制[n,k]线性分组码，有 最小软距离ds=(Q-1)dh,它一定能纠正软重量为 ts<(Q-1)dh/2的任何错误图样 有最小距离为dh的二进制线性分组码，在Q进制 输出的DMC中，当信噪比很高时，应用最小软判 决距离译码，能纠正dh-1个硬判决错误
汉明码的对偶码，极长码
大数逻辑译码
如果某一码元位置集合{ci1,ci2,…,cil}的线性组合 ai1ci1+ai2ci2+…+ailcil 在A1，A2,…,AJ的一致校验和式中均出现，而其 余码元位置集合至多在其中一个校验和式中出现， 则说A1，A2,…,AJ在集合{ci1,ci2,…,cil}上正交，称 A1，A2,…,AJ是正交于该码元位置集合的正交一 致校验和式。 例：[7,4,3]循环汉明码，两步大数逻辑可译码
1 0 1 1 0 0 0 H0 1 1 0 0 0 1 0 1 0 0 0 1 0 1
H0CT 0
大数逻辑译码
A1=c6+c4+c3=0 A2=c6+c5+c1=0 A3=c6+c2+c0=0 该校验方程的特点：c6含在每一方程中，c5, c4, c3, c2, c1, c0只含在某一方程中。称为正交于c6码元位的 正交校验方程。H0称为正交一致校验矩阵。 定义：若某一特定码元位出现在H0矩阵中J行的 每一行中，其他码元位至多在其中一行出现，则 称H0为正交于该码元位的正交一致校验矩阵。
若前面k位没有错误，则可用捕错译码实现
若前面k位也有错误，此时伴随式S(x)为：
S x E P x E I x mod g x E P x S I x
若EI(x)和SI(x)已知，可由此得到EP(x)， 进而确定E(x)= EI(x) +EP(x)，即是修正捕错译码
大数逻辑可译码
RM码 极长码（汉明码的对偶码） 差集循环码 复数旋转码
RM码
G0是长为N的全1矢量，G1是 G0 m×2m阶矩阵，其各列由2m个 G m重矢量组成；Gi是从G1中选 G 1 ... 取i行进行矢量与运算所得到的 矢量构造的。 Gr r阶RM码
State Key Laboratory of Integrated Services Networks
四 软判决译码
软判决译码
能够充分利用接收信号波形信息 比硬判决译码能得到额外的2～3dB的增益 适合中等码长和中等纠错能力的码 信噪比可以在很宽的范围内变化 硬判决译码<软判决译码<最大后验概率译 码