- 1、下载文档前请自行甄别文档内容的完整性,平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益,请联系客服反馈,我们会尽快为您处理(人工客服工作时间:9:00-18:30)。
举例: k=4 ──> r≥3
即n=7 (7,4)码
汉明码 —构造一种能纠正一位错码的编码
用a6 a5 a4 a3 a2 a1 a0表示这7个码元,
用S1,S2, S3表示三个监督关系式的校正子。
S1S2S3 错码位置 S1S2S3 错码位置
001
a0
101
a4
010
a1
110
a5
100
a2
数字码 保护码 国际码 数字码 保护码 国际码 1 01011 11101 6 10101 10101 2 11001 11001 7 11100 11100 3 10110 10000 8 01110 01100 4 11010 01010 9 10011 00011 5 00111 00001 0 01101 01101
(a n1 , a n2 , a n3 ,...a1 , a 0 ) (a n1 , a n2 ,..., a r , a r1 ,...a1 , a 0 )
|k个信息| | r个监督|
汉明距离:两个码组对应位上数字不同的位娄称 码距.
码重:每个码中的"1"个数.
最小码距的与检错和纠错能力的关系 为检测E个错码,要求最小码距 :
H
AT
0
┌┐
┌
┐ │A6│ ┌ ┐
│1110100│ │A5│ │0│
│1101010│ │A4│ = │0│
│1011001│ │A3│ │0│
└
┘ │A2│ └ ┘
│A1│
│A0│
└┘
线性码
记为
H.AT=0T 或A.HT=0
其中H称为监督矩阵,A为一码组.
┌
┐┌
┐
│1110100│ │1110 100│
e
d≥e+1
最小码距的与检错和纠错能力的关系
为纠正t个错码,要求最小码距
t
d≥2t+1
最小码距的与检错和纠错能力的关系
为纠正t个错码,同时检测e个错误,要 求
e条件:t≤e t 1 ⒈
d≥t+e+1
2、常用的简单编码 ——奇偶监督码
n
Ci mod 2 偶校少,监 督位只一位,它使码 组中 “1”的数目为 偶数,即要求
常用的简单编码 ——恒比码
检错能力: 可检所有奇数个码元的错误及部分偶数个 码元的错误,但不能检测同时"1"变"0"和"0" 变"1"的偶个码元的错误.
例子
常用的简单编码 ——正反码
编码:正反码的监督位数目和信息位数目相同, 监督码元信息码元相同或相反,则由信息码中 "1"的个数而定.
设码长N=10,R=5,K=5
"0"位置 3. 有4个"0",1个"1" 4. 其它错码多于1个
常用的简单编码 ——交织码
在原有检错能力条件下,解决连续错误
3、线性码
1. 各种编码依据的原理不同 2. 奇偶监督码的编码原理利用了代数关系式
代数码:建立在代数学基础上的编码,其中有线 性码,•线性码中信息位和监督位是由一些线性 代数方程构成的.
汉明码
偶数监督码的构成.
n
S= Ci
i
S只有两种情况 0--无错 1---有错 若把监督位设为两位,有四种情况: 00---无错, 01,10,11表示1位错码的3种不同位
置,同理R•位监督可指示一位错位的(22 -1)个不 同位置.
汉明码 —构造一种能纠正一位错码的编码
设码长为n,信息位数为k,则监督位数r=n- k,要r位监督位数能指示一位错码的几种可能 位置,则要求: 2r-1>=n 或2r>=k+r+1
n
Ci 1 mod 2 奇校验 i 1
常用的简单编码 ——二维奇偶监督码
奇数个错误数字可检测 可能检测偶数个错误 不能检测的情况有构成 矩形的四个错码
常用的简单编码 ——恒比码
在恒比码中,每个码组含有相同数目的"1"(和"0)).检测 时,•只计算接收码组中"1"的数目是否对
电传机传输汉字钟"与口取了"的恒比码
H=│1101010│= │1101 010│ =[PIr]
│1011001│ │1011 001│
└
┘└
┘
H矩阵的各行是线性无关,即秩为R.
线性码
由生成式可得: ┌ ┐ ┌ ┐┌ ┐ │ A2│ │1110││A6│ │ A1│=│1101││A5│ │ A0│ │1011││A4│ └ ┘ └ ┘└A3┘ ┌┐
11001----1100111001 (奇数"1") 10001----1000101110 (偶数"1")
常用的简单编码 ——正反码
解码:信息位和监督位按位模2相加,得一合成 的码组,若信息位有奇个"1",为检验码组,若信 息位有偶个,则取反码为校验码组,校验规则如 下:
1. 全为"0",元错码 2. 有4个"1",1个"0"信息码中有一位错码,与
[A2A1A0]=[A6A5A4A3] │1 1 1│ =[A6A5A4A3].Q │1 1 0│ │1 0 1│ │0 1 1│ └┘
Q=PT
线性码
┌
┐
│1000 111│
a0=a3+a4+a6 a1=a3+a5+a6 监督位的生成式 a2=a4+a5+a6
信息码(1010)可得码(1010010)
a3
1011010错位<──
线性码
➢ 1.A6+1.A5+1.A4+0.A3+1.A2+0.A1+0.A0=0 ➢ 1.A6+1.A5+0.A4+1.A3+0.A2+1.A1+0.A0=0 ➢ 1.A6+0.A5+1.A4+1.A3+0.A2+0.A1+1.A0=0
计算机网络与通信
主讲:蔡伟鸿 汕头大学工学院计算机系
第三章、数 据 通 信
概论 差错控制编码 数据通信基础 传输控制电路 时钟同步技术
第六节 差错控制编码
纠错编码的基本原理 常用的简单编码 线性码 循环码原理
数据通信系统模型
1、纠错编码的基本原理
例子:“晴”,“雨”的编码 分组码:由信息码分组,附加若干监督码组成
111
a6
011
a3
000
无错
汉明码 —构造一种能纠正一位错码的编码
S1=a2+a4+a5+a6 S2 =a1+a3+a5+a6 S3 =a0+a3+a4+a6 当无错时,
S1=S2 =S3 =0
a2+a4+a5+a6=0
a1+a3+a5+a6=0
a0+a3+a4+a6=0
汉明码 —构造一种能纠正一位错码的编码