当前位置：文档之家 › 信息论6章 信道的纠错编码(新)

信息论6章 信道的纠错编码(新)

  • 格式：pdf
  • 大小：174.46 KB
  • 文档页数：97

下载文档原格式

  / 97

合集下载

电子科大信息论与编码第6章 离散信道纠错编码

电子科大信息论与编码第6章 离散信道纠错编码


15
N重复码当N很大时，使错误概率Pe降得很低 的同时，信息传输率R也大大降低—如3重复 码的信息率为原信息率的1/3，即该编码的 编码效率仅为1/3 。 需要找这样的纠错码： 足够小的平均译码错误概率Pe 较高的编码效率。
16
1.基本概念：
纠错方式——主要有检错重发(ARQ)、 前向纠错(FEC)和混合纠错(HEC)等。 纠错码——主要有分组码和卷积码两大 类，此外还有1982年提出的将编码与调制 结合在一起的网格编码调制和1993年提出 的将卷积码与随机交织器相结合的Turbo 码、LDPC码等。
p( y j / x*)p( x*)
p( y j / x*)p( x*) p( y j / x i )p( x i )
i 1,2, j 1,2, x* x i
i 1,2, j 1,2, x* x i
6
当信源等概率时，
p(y j / x*) p( y j / x i )
平均译码错误概率:
2 2 2 j 1 2 j 1
i 1,2, j 1,2, x* x i
最小错误概率准则可转换为最大似然译码准 则。
Pe p( y j )p(e / y j ) p( y j )[1 p( x * / y j )]
2 2 j 1 2 j 1 i 1 j 1
7 L 1
i , j 1,2, ,2 , i j
k
例：c1 1011110
d ( c 1 , c 2 ) c 1L c 2 L 3
20
码重(汉明重量):长度为n的码字中非零码 元的个数；对于二元码，码重可表示为：
w (c i ) c i L
n L 1
信息论与纠错编码课后作业答案6

信息论与纠错编码课后作业答案6

第6章习题参考答案6.6 解：（1）首先求联合概率矩阵111412611164121111264XYP ⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦最大后验概率准则即最小错误概率准则，也等同于最大联合概率准则，因此，从联合概率矩阵的每一列中选联合概率最大的发送符号作为译码输出，因此将112233,,y x y x y x →→→此时正确译码概率为11223313()()()344c p p x y p x y p x y =++=⨯=错误概率为114e c p p =-=（2）当信源等概率分布时，极大似然准则等价于最大后验概率准则，因此从信道矩阵的每一列中取转移概率最大的一个发送符号作为相应接收符号的译码输出，即是最佳译码方案，因此将112233,,y x y x y x →→→此时正确译码概率为112233111()()()(3)322c p p x y p x y p x y =++=⨯⨯=错误概率为112e c p p =-=6.10 解：（1）(;)()()D R I X Y H Y H Y X ==- 设信源的四个消息等概率出现，则有0114p p ==，12e p =[]01101111111424222201qq ⎡⎤⎢⎥⎡⎤⎡⎤⎢⎥==⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎢⎥⎣⎦111()()log 2[()(1)2]10.50.5224D R H Y H Y X H H =-=-+⨯=-=bit/符号 （2）按照译码准则译码时，由于后两位始终译为ee ，与发送代码后两位始终相同，故不存在误码；前两位，由于1000→→，1111→→，也不存在译码错误，因此所有码字的错误概率均为0。

或由联合概率矩阵1041188104XYP ⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦ 正确译码的概率为111(00)(11)()1442c p p x y p x y p ee ===+==+=++=（发送e 时始终可以正确译码），因此所有码字的错误概率为0。

信息论与编码_第6章信道编码概述

信息论与编码_第6章信道编码概述


按照编码函数f的线性性 线性码：编码函数f ( f1,f2,…,fn)是线性函数 非线性码：否则，称为非线性码。
12
6.2 信道编码概念
按照编码函数对信息元处理方法: 分组码与卷积码
分组码 设k, n是正整数，k n，则把从EAk到An的编码函数 f : EAn 称为一个(n, k)分组码编码器，或称为(n, k)编码函数。全体 码字构成的集合 C={c =f (m): mE} 称为一个q元 (n, k)分组码 (block code)，或简称为(n, k)码。
23
6.3 信道译码准则
设 x= x1x2…xn, y= y1y2…yn是两个二元码字，容易验证以 下等式成立:
d ( x, y )
n

xi yi ,
i 1
其中是模二加法 汉明距离的性质 定理6-1 设x、y与z是长为n的码字，那么汉明距离满足 以下性质： (1) 非负性：d(x, y) 0。且d(x, y) = 0的充分必要条件是 x = y； (2) 对称性：d(x, y) = d(y, x)； (3) 三角不等式：d(x, y) d(x, z)+ d( z, y)。
7
第6章
6.1 6.2 6.3 6.4 6.5
信道编码
信道差错概率 信道编码概念 信道信道译码准则 码的检错与纠错能力 信道编码定理
8
6.2 信道编码概念
信道编码器是一个映射f，它把信源符号序列m变换成 信道符号序列c = f (m)，f称为信道编码函数，或称为纠 错编码函数。信道编码也称为纠错编码。
20
6.2 信道编码概念
例6.1 重复码 重复码是一个(n, 1)分组码，其编码规 则是将每位信息元重复n 1次，也称为n次重复码。 即C ={00…0, 11…1}。对重复码，可以采用大数准 则译码。即如果接收序列中0的个数多于1的个数， 则译为0；否则，译为1。 例如，2元3次重复码的编码规则如下： “0” “000”， “1” “111”。 它是一个2元(3, 1)分组码C={000, 111} 。
信息论与编码原理信道编码

信息论与编码原理信道编码

介于中间的纠随机/突发差错码。 构码理论：代数码、几何码、算术码、组
合码等
差错控制系统分类
前向纠错（FEC）：发端信息经纠错编码 后传送，收端通过纠错译码自动纠正传递 过程中的差错
反馈重发（ARQ）：收端通过检测接收码 是否符合编码规律来判断，如判定码组有 错，则通过反向信道通知发端重发该码
生成的码字C
前k位由单位矩阵Ik决定，等于把信息组m原封不 动搬到码字的前k位；
其余的n-k位叫冗余位或一致校验位，是前k个信 息位的线性组合。
这样生成的（n,k）码叫做系统码。 若生成矩阵G不具备系统形式，则生成的码叫做
非系统码。 系统化不改变码集，只是改变了映射规则。
校验矩阵
将H空间的n-k个基底排列起来可构成一个(nk)×n矩阵，称为校验矩阵H。用来校验接收到 的码字是否是正确的；
用这种方法不能得知最优码是如何具体编 出来的，却能得知最优码可以好到什么程 度，并进而推导出有扰离散信道的编码定 理，对指导编码技术具有特别重要的理论 价值。
6.1.3随机编码
在(N,K)分组编码器中随机选定的码集有qNM种 第m个码集(记作{c}m )被随机选中的概率是
P({c}m)q(NM)
qk
<
qn
构造线性分组码的方法就是构造子空间的方法,即 在n维n重矢量空间的n个基底中选取k个基底张 成一个k维n重子空间
空间构成
n维n重空间有相互 正交的n个基底
选择k个基底构成码 空间C
选择另外的(n-k)个 基底构成空间H
C和H是对偶的
CHT＝0,码的生成矩阵，H是它的校验矩阵； H是(n,n-k)对偶码的生成矩阵，它的每一行是
一个基底。 G则是它的校验矩阵。 GHT=0 ，H＝[－ PT In-k ]，二进制时，负号
信息论与编码 第6章 信道编码

信息论与编码 第6章 信道编码

• 特点：
– 单向连续传输,实时性好 – 译码电路复杂
消息m
码字C
接收向量R
消息m’
纠错编码
信道
纠错译码
FEC
13
差错控制系统分类
• 自动请求重发(ARQ)：
– 发端发送检错码,收端译码器判断当前码字传 输是否出错；
– 当有错时按某种协议通过一个反向信道请求 发送端重传已发送的码字（全部或部分）。
1
个差错
⑶可以检测出任意小于等于l同时纠正小于等于t 个差错，
– 是指信号差错概率 • 比特差错率 /比特误码率：
– 在传输的比特总数中发生差错的比特数所占比例 – 是指信息差错概率 • 对二进制传输系统,符号差错等效于比特差错;对多进 制系统,一个符号差错对应多少比特差错却难以确定
5
差错率
• 根据不同的应用场合对差错率有不同的要求: – 在电报传送时,允许的比特差错率约为: 10－4～10－5； – 计算机数据传输,一般要求比特差错率小于: 10－8～10－9； – 在遥控指令和武器系统的指令系统中,要求有 更小的误比特率或码组差错率
6
差错图样
• 为定量地描述信号的差错,定义差错图样E
E=C－R (模M )
• 最常用的二进制码可当作特例来研究,其差错图 样等于收码与发码的模2加,即
E = C⊕R 或 C = R⊕E • 设发送的码字C 1 1 1 1 1 1 1 1 1 1
0:传输中无错 1:传输中有错
接收的码字R 1 0 0 1 0 0 1 1 1 1
• 纠错编码所提高的可靠性,是以牺牲信道利用率 为代价换取的。
• 监督码引入越多,检错、纠错能力越强,但信道的 传输效率下降也越多。
20
陈运-信息论与编码-第六章 信道编码

陈运-信息论与编码-第六章 信道编码

• 系统码
线性(N，k)码生成矩阵G具有形式
G Ik , A
由此产生的码称为系统码。系统码的一致 监督矩阵具有形式
H AT , INk
二元有限域上的 -AT=AT
29
6.4 线性分组码
• 线性分组码的性质
零向量 是一个码字，称为零码字
两码字之和或差仍是一个码字 线性性
在码的所有码字上减去任一特 定的码字，结果仍是这同一码 的全部码字。
对称性
二元有限域上最小码距
最小码重。
30
6.5 线性循环码
• 汉明码的对偶码
• 线性循环码
1 0 1 1 1 0 0 G 0 1 0 1 1 1 0
0 0 1 0 1 1 1
1 1 0 1 0 0 0 H 0 1 1 0 1 0 0
C c c bi,bC C x cx cx bi x,bxC x
37
例 6.3.2 如下确定的CA是线性循环码，CB 是非循环的线性分组码，CC是非线性的循环
码。
，，
38
定理： （n,k）循环码C( x)中存在唯一的一个
非零的，首一的和最低次为r（r<n）的码
(a0 b0 ,a1 b1, ,am1 bm1)
• 乘法 ab=c
不可约 多项式
c0 c1x cm1xm1
(a0 a1x am1xm1)(b0 b1x bm1xm1) mod p(x)
11
6.4 线性分组码
• 线性分组码的基本参数
u0 u1 u2 u3 c4 c5 c6
c0 c1 c2 c3 c4 c5 c6
c4 u0 u1 u2
信息论与纠错编码编码习题答案

信息论与纠错编码编码习题答案


1 225.6( Bit ) 52! 52! （2） I ( xi ) log q( xi ) log 13 4 13!39! 1 （3） H (U ) －log log 52 log 4 3 2 log 13 7.4( Bit / 符号) 52 1 （4） H ( X ) log log 13 3.7( Bit / 符号) 13
x0 x0 x0 x1 x1 x0 x1 x1 1 / 16 3 / 16 3 / 16 9 / 16 n 1.6875 0.96 x1 x0 x0 3 / 64 x1 x0 x1 9 / 64 x1 x1 x0 9 / 64 x1 x1 x1 27 / 64
n 1.633
0.89
3.21 （1）D=2
消息 码字 x1 111 x2 101 x3 100 x4 011 x5 001 x6 000 x7 1101 x8 1100 x9 0101 x10 0100
n 3.26
0.99
n 2.11
（2）D=3
消息 码字 x1 22 x2 21 x3 20 x4 12 x5 10 x6 02 x7 01 x8 00 x9 111 x10 110
0.966
3.22
方法一：概率之和与原信源某概率相等，概率之和往上排； 方法二：概率之和与原信源某概率相等，概率之和往下排； 第一种方法对实用更好
3.24 （1）H(X) = (1/4)log4 + (3/4)log(4/3) = 0.811
3
(2） q (0)＝1/4，q (1)=3/4 （3）扩展信源 Fano 编码 消息 码字 (4) 扩展信源 x0x0 111 x0x1 110 x1x0 10 x1x1 0
第六章信道编码

第六章信道编码


2 0010 1
10 1 0 1 0 0
3 0011 0
11 1 0 1 1 1
4 0100 1
12 1 1 0 0 0
5 0101 0
13 1 1 0 1 1
6 0110 0
14 1 1 1 0 1
7 0111 1
15 1 1 1 1 0
本次您浏览到是第十四页，共一百零八页。
a4 a3 a2 a1
本书讨论的信道编码主要指纠错编码，而衡量纠错编 码性能的指标主要是误比特率的改善程度。
本次您浏览到是第三页，共一百零八页。
二、检错和纠错（差错控制）的基本原理：
举例说明： A、B两消息，可用一位二进制数表示，A=1、B=0
出错时无法判定 。
增加一个监督位，取11→A、00→B,若收到01或10时，
最小距离与检错和纠错能力之间满足如下关系：
1) 设码组能检错个数为e，则有
d0e1
2) 设码组能纠错个数为t，则有
d02t 1
3) 若码组能检错个数为e，又能纠错t个，则有 d0et1(et)
对任何纠错编码都适用。
本次您浏览到是第十一页，共一百零八页。
三、编码效率
对于分组码（n,k），编码效率定义为信息位在码字中所
（1）
线性码，非线性码
（2） 根据监督码元是否仅与本组信息元有关 分组码，卷积码
（3）
根据纠错码组中信息元是否隐蔽分：
系统码，非系统码
（4）
根据码的用途分：
检错码 ，纠错码
（5） 根据码元的取值：
二进制码，多进制码
（6） 根据构造编码的数学方法：
代数，几何码，算术码
本次您浏览到是第七页，共一百零八页。
信息论与编码(第三版) 第6章 信道编码理论

信息论与编码(第三版) 第6章 信道编码理论


(2,1,2)卷积码编码器
定义6.3两个n重(x，y)之间对应码元取值不同的个数， 称为这两个重之间的汉明距离，记做d(x,y)
定义6.4 n重x非零码元的个数称为汉明重量，简称重 量,用w(x)表示
X:(10101) y:(00111)
w(x)=3 w(y)=3 d(x,y)=2
定义6.5 （n,k）分组码中，任意两个码字x、y之间的 汉明距离的最小值，称为该分组码的最小汉明距离， 简称为最小距离，用d0表示
6.3.1两种译码规则
最大概率译码(MAP) 错误译码的概率最小，也称最小错误概率译码
最大似然译码(MLD)
MAP的简化形式
单个符号传输情况(二元信道)
信道
输入X
0 1 pe
信道 输出Y
0
根据接收符号y来估计 发送符号x是0还是1
计算后验概率p(xi|y)
估值准则
x$ max P(xi | y)
结果是译码错误最 小，所以也称最小
d0
min {d(x,
x, y(n,k )
y)}
计算最小汉明距离方法1 将所有许用码字进行比较，记录每次比较的 汉明距离，最后取汉明距离的最小值即可
总的比较次数为 1 2 3 L 2k 1 (2k 1)2k
2
无论是否 线性分组
码
这种方法 都有效
特点：计算量很 大但是很简洁
❖ 例6.1 （3,2）码共有四个码字，分别为000，011，101， 110，显然d0 =2。 最小汉明距离d0是分组码的重要参数之一，表明 了该分组码抗干扰能力的大小，与码字的检错、 纠在错相能同力的有译关码，规则d0下越，大错，误码译的码抗的干概扰率能越力小越。强，
(4) 纠正t个随机错误, ρ个删除,则要求码的最小距离满足 d0 ≥ ρ +2t+1
信息论与编码第6章信道编码

信息论与编码第6章信道编码


素(既约)多项式
若 p( x) f ( x), deg( p( x)) 1且p( x)在F[ x] 中只有因式 c和cp( x) 则称 p( x) 为域F上的不可约多项式。
的集合
余类环
多项式剩余类环 n n1 f ( x) an x an1x ... a1x a ai Fq 用 Fq [ x] 或者 GF (q)[ x] 表示所有这样多项式
纠错码的分类
根据监督码元与信息组之间的关系 系统码 信息码元是否发生变化 非系统码 代数码 几何码 算术码 线性码 非线性码 分组码 卷积码
构造编码的数学方法
根据监督码元和信息码元的关系
根据码的功能
按纠误的类型
检错码 纠错码 纠删码 纠随机差错码 纠突发差错码 纠混合差错码 二元码 多元码 等保护纠错码 不等保护纠错码
3 3 2 2 3 2 3 2
x x , x x, x x 1, x 1, x ,
3 3 3 3
x x 1, x x, x 1, x , x 1, x,1, 0
2 2 2 2
4．有限域的性质和代数结构
1）有限域 Fq 的结构 对 a Fq , a 0, 满足 na 0, 的最小正整 数 n ，称为元素 a 的周期。 定理6-6：在有限域 Fq中 (1) ( Fq , ) 是循环加群，它的非零元素的周期等于其 域的特征； (2) ( Fq* , ) 是循环乘群，共有 (q 1) 个乘群的生成 元。 a 乘群 ( Fq* , ) 的生成元 a 称有限域 Fq 的本原元， 的阶为 q 1 ，即 a q 1 e ，且 F * a
q
本原元性质定理6-7
* F (1) q
的元素的阶都是 q 1 的因子， Fq* 的所 q 1 x e 0 的根。 有元恰是 (2) 若 a 是 Fq 的本原元，则当且仅当(k , q 1) 1 k k a 时， 也是本原元。非本原元 a 的阶是
信息论 第六章 信道编码(2)

信息论 第六章 信道编码(2)


0 0 1 0
0 0 0 1
所以
H( 7 ,3 ) P4×3 I4
(6.2.5)
第六章 信道编码
6.2.2 一致监督方程和一致监督矩阵
推广到一般情况：对 (n,k) 线性分组码，每个码字中的 r(r=n－k) 个监督元与信息元之间的关系可由下面的线性 方程组确定
6.2 线 性 分 组 码
6.2 线 性 分 组 码
(3) 一致监督矩阵
令 c c6 c5 c4 c3 c2 c1 c0 0 0 0 0 0 1 1 H 1 0 0 1 1 1 1 1 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1
第六章 信道编码
p11 p 21 Hr ×n pr1
p12 p22 pr 2
p1k 1 0 p2 k 0 1 prk 0 0
0 0 1
(6.2.9)
监督矩阵H 的标准形式：后面 r 列是一单位子阵的监督矩阵H。
H 阵的每一行都代表一个监督方程，它表示与该行中“1”相对应的 码元的模2和为0。
(6.2.11)
6.2 线 性 分 组 码
G中每一行 gi=(gi1,gi2,…, gin ) 都是一个码字；
对每一个信息组m，由矩阵G都可以求得 (n,k) 线性码对应的码字。 生成矩阵：由于矩阵 G 生成了 (n,k) 线性码，称矩阵 G 为 (n,k) 线性码的生成矩阵。 (n,k) 线性码的每一个码字都是生成矩阵 G 的行矢量的线性组合， 所以它的 2k 个码字构成了由 G 的行张成的 n 维空间的一个 k 维 子空间 Vk。
第六章 信道编码
思维世界的发展，在某 种意义上说，就是对惊奇的 不断摆脱。

信息论与编码第六章课后习题答案(曹雪虹)

第六章：信道编码(本章复习大纲我重新修改了一下，尤其要关注红色内容)1、基本概念：差错符号、差错比特；差错图样：随机差错、突发差错；纠错码分类：检错和纠错码、分组码和卷积码、线性码与非线性码、纠随机差错码和纠突发差错码；矢量空间、码空间及其对偶空间； 有扰离散信道的编码定理：-()NE R e P e （掌握信道编码定理的内容及减小差错概率的方法）；线形分组码的扩展与缩短（掌握奇偶校验码及缩短码的校验矩阵、生成矩阵与原线形分组码的关系）。

2、线性分组码(封闭性)：生成矩阵及校验矩阵、系统形式的G 和H 、伴随式与标准阵列译码表、码距与纠错能力、完备码(汉明码)、循环码的生成多项式及校验多项式、系统形式的循环码。

作业：6-1、6-3、6-4、6-5和6-6选一、6-7 6-8和6-9选一 6-1 二元域上4维4重失量空间的元素个数总共有24=16个，它们分别是(0,0,0,0),(0,0,0,1)…(1,1,1,1)，它的一个自然基底是(0,0,0,1),(0,0,1,0),(0,1,0,0)和(1,0,0,0)；其中一个二维子空间含有的元素个数为22个，选取其中一个自然基底为(0,0,0,1)和(0,0,1,0)，则其二维子空间中所包含的全部矢量为(0,0,0,0,),(0,0,0,1),(0,0,1,0)和(0,0,1,1)(注选择不唯一)；上述子空间对应的对偶子空间可以有三种不同的选择：(0,0,0,0) ,(0,1,0,0),(1,0,0,0)，(1,1,0,0)或(0,0,0,0) ,(0,1,0,0)或(0,0,0,0) (1,0,0,0)。

(注意本题中所包含的关于矢量空间的一些基本概念)6-3 由题设可以写出该系统(8,4)码的线形方程组如下：736251403320231012100321v u v u v u v u v u u u v u u u v u u u v u u u=⎧⎪=⎪⎪=⎪=⎪⎨=++⎪⎪=++⎪=++⎪⎪=++⎩(注：系统码高四位与信息位保持一致，u i 为信息位) 把上述方程组写成矩阵形式，可以表示为 V =U G ，其中V 为码字构成的矢量，即V =(v 7,v 6,v 5,v 4,v 3,v 2,v 1,v 0)，U 为信息位构成的矢量，即U =( u 3,u 2,u 1,u 0)，观察方程组可得系统生成矩阵为：[]44*41000110101001011G I |P 0010011100011110⎡⎤⎢⎥⎢⎥==⎢⎥⎢⎥⎣⎦由系统生成矩阵和校验矩阵的关系可得：4*441101100010110100H P |I 0111001011100001T ⎡⎤⎢⎥⎢⎥⎡⎤==⎣⎦⎢⎥⎢⎥⎣⎦由校验矩阵可以看出，矩阵H 的任意三列都是线性无关的(任意三列之和不为0)，但存在四列线性相关的情况(如第1、5、6、8列，这四列之和为0)，即校验矩阵H 中最小的线性相关的列数为4，从而得该线性分组码的最小码距为4。

信道的纠错编码


25
线性分组码
线性系统分组码：用标准生成矩阵 Gk×n 编成的
码字，前面 k 位为信息数字，后面 r=n－k 位
为校验数字，这种信息数字在前校验数字在后 的线性分组码称为线性系统分组码。
Cn-1 信 息 码 Cn-k Cn-k-1 C0
监 督 码
26
线性分组码
例：(7,4) 线性码的生成矩阵为 1 0 0 0
3
错误图样
⑴ 当系统无干扰时 R=C ⑵ 当系统有干扰时 R=C+E 其中，E称为信道的错误图样， E=(e0,e1,…,en-1)；ei∈{ 0,1}；当ei=1，则第i位上有错；反 之，无错。 例： C = 0 0 1 0 1 1 0 1 E= 01001001 R= 01100100 由信道的对称性可知 p(0/1)=p(1/0)=p(e=1)=p 反之，若已知R ，E 则可求出C，这就是纠错码的原理，如： E= 01001001 R= 01100100 4 C= 00101101
对应码字 0000000 0011101 0100111 0111010 1001110 1010011 1101001 1110100
18
线性分组码

为了运算方便，将监 督方程写成矩阵形式， 得:
C6 0 C4 C3 0 0 0 0 C C C 0 C 0 0 0 6 5 4 2 C6 C5 0 0 0 C1 0 0 0 C5 C4 0 0 0 C0 0
20
线性分组码
一致监督阵H
21
线性分组码
⒉ 监督阵与生成阵的关系
由于生成矩阵G的每一行都是一个码字， 所以G 的每行都满足Hr×nCTn×1=0Tr×1，

信道编码的纠错原理

#include <math.h>
#include <stdio.h>
#define mm 4 /* RS code over GF(2**4) - change to suit */
#define nn 15 /* nn=2**mm -1 length of codeword */
#define tt 3 /* number of errors that can be corrected */
{ elp[u+1][i] ^= elp[u][i] ;
elp[u][i] = index_of[elp[u][i]] ; /*convert old elp value to index*/
}
}
u_lu[u+1] = u-l[u+1] ;
/* form (u+1)th discrepancy */
int count=0, syn_error=0, root[tt], loc[tt], z[tt+1], err[nn], reg[tt+1] ;
/* first form the syndromes */
for (i=1; i<=nn-kk; i++)
{ s[i] = 0 ;
for (j=0; j<nn; j++)
{
/* form polynomial z(x) */
for (i=1; i<=l[u]; i++) /* Z[0] = 1 always - do not need */
{ if ((s[i]!=-1) && (elp[u][i]!=-1))
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
z 将这三类信道编码统称为纠错码或抗干扰码。
15
第3节 纠错码分类
2) 按应用目的分类： • 检错码：只能够检测出错误的码； • 纠错码：既能检测出错误又能自动纠正错误的码； • 纠删码：能够纠正被删除了信息的错误的码。
• 这三类码之间并没有本质区别，每类码都可由采用的译码 方法不同而作为另两类码使用。
23
4.1 线性分组码的生成矩阵和校验矩阵
二元线性分组码: (5,2)分组码: 码长为5，信息位为2。
c1 = m1 c2 = m2 c3 = m1 ⊕ m2 = c1 ⊕ c2 c4 = m1 = c1 c5 = m1 ⊕ m2 = c1 ⊕ c2
用矩阵表示为: c=mG
c = [c1
c2 L
c5 ] = mG = [m1
• 其生成矩阵G的K个相互独立的行向量{g1,g2,…,gK}是它 的一组基底;
例：前面的（5，2）系统码： c1 = m1
G
=
⎡1 ⎢⎣0
0 1
1 1
11⎤ 0 1⎥⎦
2×5
c2 = m2 c3 = m1 ⊕ m2 = c1 ⊕ c2 c4 = m1 = c1
c5 = m1 ⊕ m2 = c1 ⊕ c2
c1 = m1 c2 = m2 c3 = m1 ⊕ m2 = c1 ⊕ c2 c4 = m1 = c1 c5 = m1 ⊕ m2 = c1 ⊕ c2
G
=
⎡1 ⎢⎣0
0 1
1 1
11⎤ 0 1⎥⎦
m1=1, m2=0 m1=0, m2=1
28
4.1 线性分组码的生成矩阵和校验矩阵
• 二元(N,K)线性码C={c}可看成一个N重K维线性空间;
⎪⎪c2 = m2
c1 + c2 + c3 = 0
⎪c3 = m2 + m3 = c1+ c2 ⎨⎪c4 = m1
8) 按码字的结构分类：
• 系统码：信息元以不变形式出现在各码字C的任意k位上；
• 非系统码：没有系统码的特性。
21
第6章 信道的纠错编码
第1节 引言 第2节 差错控制的基本形式 第3节 纠错码分类 第4节 线性分组码 第5节 循环码
22
第4节 线性分组码
4.1 线性分组码的生成矩阵和校验矩阵 4.2 汉明距离和码的纠、检错 4.3 线性码的伴随式和伴随式译码
33
4.1 线性分组码的生成矩阵和校验矩阵
（1）（6，3）
⎡0 0 0 1 1 1⎤
（2）G = ⎢⎢0 1 1 0 0 1⎥⎥
⎢⎣1 0 1 0 1 1⎥⎦
⎡0 0 0 1 1 1⎤ C = mG = (m1,m2,m3 )⎢⎢0 1 1 0 0 1⎥⎥
⎢⎣1 0 1 0 1 1⎥⎦
（3）
⎧c1 = m3
第1节 引言 第2节 差错控制的基本形式 第3节 纠错码分类 第4节 线性分组码 第5节 循环码
14
第3节 纠错码分类
1) 按纠正错误类型分类： z 纠随机差错码：信道对信息有衰减、畸变、干扰和噪 声等多种影响；
z 纠突发差错码：有记忆信道的噪声可造成突发性的成 群的差错；
z 纠混合差错码：上述两种差错并存。
G = [1,1,1]
(c0 , c1, c2 ) = (m0 )[1,1,1] = (m0 , m0 , m0 )
一般情况：
⎡ g11 g12 ... g1N ⎤
C=mG=源自(m1,m2 ,...,mk
⎢ )⎢⎢
g 21 ...
g 22 ...
... ...
g
2
N
⎥ ⎥
... ⎥
⎢ ⎣
g
k1
gk2
...
发送端
信息信号 信息信号
接收端
12
第2节 差错控制的基本形式
1. 前向纠错（FEC) 方式：接收端直接纠错 2. 反馈重发（ARQ) 方式：收信端将判决结果反馈给发送端 3. 混合纠错（HEC) 方式：前向纠错和反馈重发方式结合 4. 信息反馈（IRQ) （回程校验）方式：全部反馈
13
第6章 信道的纠错编码
• 为了提高信息传输的准确性，使其具有较好的抵抗信道中 噪声干扰的能力，在通信系统中需要采用专门的检、纠错 误方法，即差错控制。
4
第1节 引言
• 差错控制的任务是：发现所产生的错误、并指出 发生错误的信号或者校正错误
• 差错控制是采用可靠、有效的信道编码方法来实 现的。
• 信道编码器要对信源编码输出的符号进行变换， 使其尽量少受噪声干扰的影响，减少传输差错， 提高通信可靠性。
31
4.1 线性分组码的生成矩阵和校验矩阵
一般而言，二元（N，K）线性码的信息组用K维行矩阵表示
m = [m1 m2 Lmk ], mi ∈{0,1}
码字c用N维行阵表示为: c = [c1 c2 LcN ], ci ∈{0,1} 码字生成式为：c=mG. G有几行？几列？ 式中G是K×N生成矩阵，G的元素取值于二元集合{0,1}。
g kN
⎥ ⎦
26
4.1 线性分组码的生成矩阵和校验矩阵
把生成矩阵G写成行向量形式：
⎡ g11 g12 ... g1N ⎤
⎡ g1 ⎤
C
=
mG
=
(m1,m2
,...,mk
⎢ )⎢⎢
g 21 ...
g 22 ...
... ...
g2N ...
⎥ ⎥ ⎥
=
(m1,m2 ,...mk
⎢ )⎢⎢
g2 M
⎥ ⎥ ⎥
10
第2节 差错控制的基本形式
3. 混合纠错（HEC) 方式：前向纠错和反馈重发方式结合
发送端
可以发现和纠正错误的码 应答信号
接收端
性能介于两者之间：设备不太复杂；误码率低；实时和连 续性好
适用：范围很广，特别在卫星通信中
11
第2节 差错控制的基本形式
4. 信息反馈（IRQ) （回程校验）方式：全部反馈
c3 = c1 ⊕ c2 c4 = c1 c5 = c1 ⊕ c2
c1 ⊕ c2 ⊕ c3 = 0 c1 ⊕ c4 = 0 c1 ⊕ c2 ⊕ c5 = 0
校验方程的矩阵形式则为： cH T = 0或HcT = 0 式中H称为一致性校验矩阵： ⎡1 1 1 0 0⎤
H = ⎢⎢1 0 0 1 0⎥⎥ ⎢⎣1 1 0 0 1⎥⎦
3
第1节 引言
• 在通信系统中，要提高信息传输的有效性，我们将信源的 输出经过信源编码用较少的符号来表达信源消息，这些符 号剩余度很小，效率很高，但对噪声干扰的抵抗能力很 弱。
• 信息传输要通过各种物理信道，由于干扰、设备故障等影 响，被传送的信源符号可能会发生失真，使有用信息遭受 损坏，接收信号造成误判。这种在接收端错误地确定所接 收的信号叫做差错。
⎢ ⎣
g
k1
gk2
...
g kN
⎥ ⎦
⎢ ⎣
g
k
⎥ ⎦
则码字可表示成：c = mG = m1g1 ⊕ m2g2 ⊕L⊕ mk gk
码字c是G的行向量{gi}的（模2）线性组合。当信息组m中 只有一个非零元素时，码字就是G的某一行向量，所以G 的每个行向量都是一个码字。
27
4.1 线性分组码的生成矩阵和校验矩阵
8
第2节 差错控制的基本形式
2. 反馈重发（ARQ) 方式：收信端将判决结果反馈给发送端
发送端
能够发现错误的码
接收端
应答信号
优点：译码设备简单；误码率小
缺点：效率可能降低，使连续性、实时性变差
适用：计算机局域网、分组交换网；短波、有线等干扰情 况复杂的信道；卫星通信、移动通信
9
第2节 差错控制的基本形式
第6章 信道的纠错编码
信息论
哈尔滨工业大学（威海） 计算机科学与技术学院
刘杨 llyy.2000@
第6章 信道的纠错编码
第1节 引言 第2节 差错控制的基本形式 第3节 纠错码分类 第4节 线性分组码 第5节 循环码
2
第1节 引言
• 信道编码的目的是为了降低平均差错率，又称纠错编码。 • 纠错编码理论几乎与信息论同时创立，都是在二战结束后的 短短几年内。 • 纠错编码理论的创始人是汉明，他与信息论的创始人香农都 在贝尔实验室工作。 • 香农信息论主要涉及信息的测度以及信息传输所能达到的极 限。但香农并没有给出切实可行的实现方法。 • 香农的有噪信道编码定理的意义在于：它告诉我们什么是通 过努力可以做到的事情，什么是不可能做到的事情。
17
第3节 纠错码分类
4) 按码的数学结构中校验元与信息元关系分类： • 线性码：校验元与信息元之间呈线性关系；
• 非线性码：校验元与信息元之间不呈线性关系。
目前，线性码的理论已较成熟，但许多好码是非线性码。
18
第3节 纠错码分类
5) 按码是否具有循环性分类： • 循环码：分组码中的任一码字的码元循环移位后仍是 这组的码字；
发送端
能够发现错误的码
接收端
应答信号
具体实现检错重发方式：
• 停止等待式(SW-ARQ): 逐帧发送，然后等待接收端发回确 认的信息或要求重发的信息
• 回退N步式(GBN-ARQ): 发送端保存前面已发送的N帧，并 连续发送，一旦接到重发请求，必须退回到重发请求前的一 段N帧，从那个帧开始重发
• 选择重发式(SR-ARQ): 连续发送，两端都有帧的缓存器， 接收端要求重发时必须指明要求重发哪一帧，发送端则从要 求重发的帧开始连续传输。
c1 = m1 c2 = m2 c3 = m1 ⊕ m2 = c1 ⊕ c2 c4 = m1 = c1 c5 = m1 ⊕ m2 = c1 ⊕ c2