02纠错编码的基本原理 分组码举例 ■设:有一种由3个二进制码元构成的编码,它共有23=8种 不同的可能码组: 000-晴001-云010-阴011-雨 100-雪101-霜110-雾111-雹 这时,若一个码组中发生错码,则将收到错误信息 ■若在此8种码组中仅允许使用4种来传送天气,例如:令 000-晴011-云101-阴110-雨 为许用码组,其他4种不允许使用,称为禁用码组。 这时,接收端有可能发现(检测到)码组中的一个错码。 口这种编码只能检测错码,不能纠正错码。 ■若规定只许用两个码组:例如 000-晴111-雨 就能检测两个以下错码,或纠正一个错码
6 10.2 纠错编码的基本原理 ➢ 分组码举例 ◼ 设：有一种由3个二进制码元构成的编码，它共有2 3 = 8种 不同的可能码组： 000 – 晴 001 – 云 010 – 阴 011 – 雨 100 – 雪 101 – 霜 110 – 雾 111 – 雹 这时，若一个码组中发生错码，则将收到错误信息。 ◼ 若在此8种码组中仅允许使用4种来传送天气，例如：令 000 – 晴 011 – 云 101 – 阴 110 – 雨 为许用码组，其他4种不允许使用，称为禁用码组。 这时，接收端有可能发现（检测到）码组中的一个错码。 这种编码只能检测错码，不能纠正错码。 ◼ 若规定只许用两个码组：例如 000 – 晴 111 – 雨 就能检测两个以下错码，或纠正一个错码
>分组码概念 信息位监督位 分组码=信息位+监督位 分组码符号:(n,k) 晴 00 0 其中,n一码组总长度, k一信息码元数目。 01 r=n-k一监督码元数目 阴 10 右表中的码组为(3,2)码。 雨 11 0 ■分组码的一般结构: an1an2…a,a-1|an2…a k个信息位 r个监督位 码长n=k+ 分组码的结构 ■分组码的参数: 口码重:码组内“1”的个数 口码距:两码组中对应位取值不同的位数,又称汉明距离 口最小码距(d):各码组间的最小距离 7
7 ➢ 分组码概念 ◼ 分组码 ＝ 信息位 ＋ 监督位 ◼ 分组码符号：(n, k) 其中，n － 码组总长度， k － 信息码元数目。 r = n – k － 监督码元数目。 右表中的码组为(3, 2)码。 ◼ 分组码的一般结构： ◼ 分组码的参数： 码重：码组内“1”的个数 码距：两码组中对应位取值不同的位数，又称汉明距离 最小码距(d0 ) ：各码组间的最小距离 信息位 监督位 晴 00 0 云 01 1 阴 10 1 雨 11 0 k个信息位 r个监督位 an-1 an-2 ... ar ar-1 an-2 ... a0 t 码长 n = k + r 分组码的结构
■码距的几何意义:以n=3的编码为例 0,1,0) (0,1,1 0,0 1,0,0 40,n 1,0,1) 般而言,码距是n维空间中单位正多面体顶点之间的汉 明距离
8 ◼ 码距的几何意义：以n = 3的编码为例 ◼ 一般而言，码距是n 维空间中单位正多面体顶点之间的汉 明距离。 (0,0,0) (0,0,1) (1,0,1) (1,0,0) (1,1,0) (0,1,0) (0,1,1) (1,1,1) a2 a0 a1
种编码的纠检错能力:决定于最小码距d的值。 口为了能检测e个错码,要求最小码距 d≥e+1 B汉明距离 码距等于3的两个码组 口为了能纠正t个错码,要求最小码距 dn≥2t+1 B 汉明距离 码距等于5的两个码组
9 ◼ 一种编码的纠检错能力：决定于最小码距d0的值。 为了能检测e个错码，要求最小码距 为了能纠正t 个错码，要求最小码距 d0 e +1 0 1 2 3 A e B 汉明距离 d0 码距等于3的两个码组 d0 2t +1 B t A 汉明距离 0 1 2 3 4 5 t d0 码距等于5的两个码组
口为了能纠正个错码,同时检测e个错码,要求最小码距 do≥e+t+1(e>D 了汉明距离 码距等于(e+t+1)的两个码组 纠检结合工作方式: 当错码数量少时,系统按前向纠错方式工作,以节 省重发时间,提高传输效率 ■当错码数量多时,系统按反馈重发的纠错方式工作, 以降低系统的总误码率
10 为了能纠正t个错码，同时检测e个错码，要求最小码距 纠检结合工作方式： ◼ 当错码数量少时，系统按前向纠错方式工作，以节 省重发时间，提高传输效率； ◼ 当错码数量多时，系统按反馈重发的纠错方式工作， 以降低系统的总误码率。 A B 1 t t 汉明距离 e 码距等于(e+t+1)的两个码组 1 ( ) 0 d e +t + e t