x2(1+x2+x3+x4) +
同余号
x3(1+x2+x3+x4) 三(1+x3+x5+x6) + + x4(1+x2+x3+x4)三(1+x1+x4+x6) + + x5(1+x2+x3+x4) 三(1+x+x2+x6) + + x6(1+x2+x3+x4) 三(1+x2+x3+x6) + + x7(1+x2+x3+x4) 三(1+x2+x3+x4) + +
则这组码元称为(7,3)线性分组码
上式可以完整地表示为: 左式可以用矩阵表示为
C6=1.C6+0.C5+0.C4 C5=0.C6+1.C5+0.C4 C4=0.C6+0.C5+0.C4 C3=1.C6+0.C5+1.C4 C2=1.C6+1.C5+1.C4 C1=1.C6+1.C5+0.C4 C0=0.C6+1.C5+1.C4 模2加
思考:若重复4次可检出几个差错? 纠正几个差错呢? 答:检4个,纠正2个差错 结论:重复N次的重复码,可检出N 个或纠正N/2个差错
7.2.4 恒比码
从确定码长的码组中挑选那些1和0的比例为恒 定值的码组作为许用码. 通过计算接收码组中"1"的数目是否正确,判 断是否有误. 我国邮电部门采用五中取三的恒比码作为数 字保护电码. 能够检测出码组中所有奇数个及部分偶数个 错误
恒比码
例:五位保护电码表
数字 0 1 2 3 4 电码 01101 01011 11001 10110 11010 数字 5 6 7 8 9 电码 00111 10101 11100 01110 10011
ISBN国际统一图书编号
7.2.5 线性分组码
如果信息码元与监督码元之间的关系可 以用一组线性方程来表示,且监督码元 仅由本码组的信息码元来确定,而与其 他码组的码元无关,则称该编码为线性 分组码 特点: 1. 封闭性:任意两个许用码组相加后(按 位进行模2加,所得编码仍是许用码组) 2. 最小码距等于非零码的最小码重
三,差错控制编码分类
0 0 1 1 0 1 0 1 0 1 1 0
监督码
信息码
根据信息码元和附加的监督码元之间的检验关 系可分为:线性码和非线性码.即监督码是否为 信息码的线性组合来确定线性和非线性. 根据信息码元和监督码元之间的约束方式可 分为:分组码和卷积码.
7.2 几种简单的检错码:
奇偶监督码 二维奇偶监督码 重复码 恒比码 ISBN国际统一图书编号
例:(6,3)循环校验码
移位 次数
监督码元 C0 C1 C2 0 0 1 0 1 1 1 0 0 1 0 1 1 1 0 0 1 0 1 1 1 0 0 1
C3 0 1 1 1 0 0 1 0
信息码元 C4 C5 C6 1 1 1 0 0 1 0 1 1 1 0 0 1 0 1 1 1 0 0 1 0 1 0 1
4
x x
1
x
2
x
3
x
5
x
6
0 1 2 3 4 5 6 7
1 0 0 1 0 0 1 0 1 1 1 1 0 1 1 0
1 0 1 0 0 1 1 1
1 1 0 1 0 0 1 1
1 1 1 0 1 0 0 1
0 1 1 1 0 1 0 0
0 0 1 1 1 0 1 0
1+x2+x3+x4 +
x(1+x2+x3+x4) +
系统循环码的编码方法 一些概念: 一些概念:
C(x) C(x):循环码的许用码组; g(x):常数项不为0的n-k阶多项式.用 n g(x) 来生成循环码的多项式,叫循环码生成 多项式; d(x):表示信息码元的k阶码多项式 d(x): k 循环码的表示式为:c(x)=d(x).g(x) c(x)=d(x).g(x) 系统循环码:前k位为信息码,后n-k位 k n 为监督码的循环码组
0 1 1 0 行 监 督 码
监 督 码
1 1 1 1 0 1 1 1 1 0
1 0 0 1 0
0 1 1 0 0
行 监 督 码
列监督码
列监督码 1 0 行 0 1 监 0 1 督 0 码 1 0 0
列监督码
7.2.2
重复码
在每位信息码元之后用简单重复的方 法编码 译码采用多数表决法
重复码
如: 111-传输1码 000-传输0码 出现2个或3个1时判1 出现2个或3个0时判0 可纠1个差错,或检出2个差错
0 1 2 3 4 5 6 7
码多项式:对于任意一个码组
C=(C0 C1…….Cn-1),都可以用一 个次数不超过n-1次的多项式按下 式唯一确定:
C(x)=C0+C1X+C2X2+…+Cn-1X n-1 则称相应的C(X)为码多项式
(6,3)码循环移位特性
移 位 次 数
码组
0
循环码多项式( 为模) 循环码多项式(以( 1+x7 )为模) x
这是本 节重点
7.2.1 奇偶监督码(奇偶校验码)
0 0 1 1 0 1 0 1 0 1 1 0
1的个数为偶数 个,称偶校验码 偶校验码
监督码
i = n 1 i =每组中1的个数为奇数个, i = n 1 则称奇校验码 奇校验码 ( ∑ ai = 1) 奇偶校验只能发现单个和奇数个错误, 而不能检测出偶数个错误
信源
编码器
正向 信道
译码器
用户
1,原理:发送端发出能够纠正错误的编码; 原理:
接收端接收到这些码组后,通过译码能自动 发现并纠正传输中的错误 特点: 2,特点:只有正向信道,适合于只能提供 单向信道的场合以及一点发送多点接收的同 单向信道 同 播系统; 播系统 优点: 3,优点:接收信号时延小,实时性好 实时性好
7.1.2 检错重发 reQ (ARQ: Automatic Repect reQuest )
信源 编码器 缓冲与 控制 正向 信道 反向 信道 译码器 缓冲与 用户 控制
1,原理:发送端发送能够检错的编码;接收端接收到后 原理: 进行检测,通过反向信道反馈一个应答信号给发端,发 端分析应答信号,如果接收有误,将存储在缓冲器中的 码组读出后重复传输,直到接收端认为已正确接收; 2,特点:接收端只检错不纠错 特点: 3,分类:停发等候重发,返回重发和选择重发. 分类:
特点: 1,传输效率最高
t
2,发端和收端都需要缓存器,设备复杂昂贵;
7.1.3 混合纠错
(HEC:Hybrid Error Correct)
信源 ARQ FEC 正向 信道 反向 信道 FEC ARQ 用户
1,原理:内层采用FEC方式,纠正部分差错;外层采 原理: 用ARQ方式,重传那些虽已检出但未纠正的差错. 2,特点:在实时性和译码复杂性方面是FEC和ARQ方 特点: 式的折中,适于环路延迟大的高速数据传输系统
TD
TW
停发等候重发
2 NCK 2 2 3 ACK 3 4 ACK 4 4 4 t NCK 4 ACK 4 t
发
1
2
ACK
NCK
收
1
特点: 1,时延较大,使传输效率受影响 2,工作原理及设备都比较简单;用于计算机 通信系统
返回重发
发
1 2 3 4 5 6 2 3 4 5 6 7 8 4 5 6 7 8 9
差错控制的基本方式
常用的三种差错控制方式:
1,前向纠错(FEC:Forward Error Correct) 2,检错重发(ARQ: Automatic Repect reQuest,直译为自动重传请求) 3 ,混合纠错(HEC:Hybrid Error Correct)
7.1 .1 前向纠错 Correct) (FEC:Forward Error Correct)
每个信息码组长度k=3,则有23=8个不同的信 息码组 每个信息组加四个监督码元, C6 C5 C4 C3 C2 C1 C0 信息码 监督码 且监督码元是由某些信息码元按加的关系得到 的; C 3 = C 6 ⊕ C4 模2加 例如: C 2 = C 6 ⊕ C 5 ⊕ C 4
C1 = C 6 ⊕ C 5 C = C5 ⊕ C4 0
例题
再来练习: 1,若D=[0100],g(x)=x3+x+1,求余式,系 统码多项式及系统循环码.
2,若D=[1001],g(x)=x3+x+1,求余式, 系统码多项式及系统循环码.
7 差错控制
课程目标
理解差错控制编码的基本概念和原理 理解差错控制编码的基本概念和原理 掌握简单的检错码的原理和规则 掌握简单的检错码的原理和规则 了解线性分组码的编码原理和规则 了解线性分组码的编码原理和规则 掌握循环码的编码原理和规则 掌握循环码的编码原理和规则
为什么采用差错控制编码? 为什么采用差错控制编码?
编码的最小 最小码距直接关系到这种码 最小 的检错和纠错能力,因此,最小码 距是信道编码的一个重要参数. (1)在一个码组内检测e个误码,要求 最小码距dmin>=e+1 (2)在一个码组内纠正t个误码,要求 最小码距dmin>=2t+1 (2)在一个码组内纠正t个误码,同时 检测e个误码,要求最小码距 dmin>=e+t+1(e>=t)