
吉祥5. 6线性分组码信道编码的目的是为了降低平均差错率,又称纠错编码香农的有噪声信道定理的意义在于,它告我们什么是通过努力可以做到的事情,什么是不可能做到的事情。但香农并没有给出切实可行的实现方法。,香农提出的随机编码方法,是一种为避免寻找好码而采取的权宜之计,有理论意义而无实用价值。有实用价值的码须用适当的数学工具来构造,使得构造出的码具有很好的结构特性,以便于译码。纠错编码理论几乎与信息论同时创立,创始人是汉明纠错编码理论发展到现在,已形成以近世代数为理论基础的系统编码理论,又称代数编码理论
1 5.6 线性分组码 信道编码的目的是为了降低平均差错率,又称纠错编码。 香农的有噪声信道定理的意义在于,它告诉我们什么是通 过努力可以做到的事情,什么是不可能做到的事情。但香 农并没有给出切实可行的实现方法。 香农提出的随机编码方法,是一种为避免寻找好码而采取 的权宜之计,有理论意义而无实用价值。 有实用价值的码须用适当的数学工具来构造,使得构造出 的码具有很好的结构特性,以便于译码。 纠错编码理论几乎与信息论同时创立,创始人是汉明。 纠错编码理论发展到现在,已形成以近世代数为理论基础 的系统编码理论,又称代数编码理论

吉纠错编码的基本概念纠错编码的基本思路:引入可控允余,即在信息序列中加入一些余码元(或称校验码元)。1译码:利用码元之间的相关性质来检测错误和纠正错误。分组码:先将信息序列分成K个符号一组,称为信息组,然后在信息组中加入一些校验码元组成N长码字,由此得到的码称为(N,K)分组码。分组码中的任一码字的码长为N,所含的信息位数目为K、校验位数目为N-K.线性码:线性码的最重要性质是线性特性,即信息位和监督位之间的关系为线性关系,码中任意两个码字的和仍为该编码的码字。否则为非线性码。循环码:循环码是线性码的一个子集。循环码中任一码字循环移位后仍为该码的码字。否则为非循环码。2
2 纠错编码的基本概念 纠错编码的基本思路:引入可控冗余,即在信息序列中 加入一些冗余码元(或称校验码元)。 译码:利用码元之间的相关性质来检测错误和纠正错误。 分组码:先将信息序列分成K个符号一组,称为信息组, 然后在信息组中加入一些校验码元组成N长码字,由此 得到的码称为(N,K)分组码。分组码中的任一码字 的码长为N,所含的信息位数目为K、校验位数目为NK。 线性码:线性码的最重要性质是线性特性,即信息位和 监督位之间的关系为线性关系,码中任意两个码字的和 仍为该编码的码字。否则为非线性码。 循环码:循环码是线性码的一个子集。循环码中任一码 字循环移位后仍为该码的码字。否则为非循环码

沃1、线性分组码的生成矩阵和校验矩阵(以(5,2)分组码为例)编码函数:信息组长度K=2码字由信息元的[c=m模2线性组合生成m=[m m];m, e(0,1)c, =m,因此是二元线性码字长度N=5:f : c, =m,m, =c,④c,分组码,简称为C4 = m = Ci线性码。C=[C C2 C C4 CsC, =m,甲m, =C,甲c编码函数的矩阵表示:[c C2CC4 Ics]=[一/致性校验矩阵Hc=mG生成矩阵G校验方程的矩阵表示:00C二m, 甲m2 =c, c,C 甲c, 甲cC, = 00C4 =m = CIc, ④c4 = 0Cs = m, 甲m, = C 甲c,C甲c, 甲C, = 0cH0一-3
3 一 致 性 校 验 矩 阵 H 1、线性分组码的生成矩阵和校验矩阵 (以(5,2)分组码为例) 1 2 ; {0,1} m m m mi c c c c c c 1 2 3 4 5 3 1 2 1 1 2 2 1 2 4 1 1 5 1 2 1 2 : c m m c c c m c c m m c m c m f c c 码字长度N=5: 信息组长度 K=2: 编码函数: 码字由信息元的 模2线性组合生成, 因此是二元线性 分组码,简称为 线性码。 c m G 编码函数的矩阵表示: 1 2 3 4 5 1 2 1 0 1 1 1 0 1 1 0 1 c c c c c m m 1 2 3 4 5 0 0 1 1 1 0 0 1 0 0 1 0 1 1 0 0 1 0 c c c c c T cH 0 T Hc 0 3 1 2 1 2 4 1 1 5 1 2 1 2 c m m c c c m c c m m c c 1 2 3 1 4 1 2 5 0 0 0 c c c c c c c c 校验方程的矩阵表示: 生成矩阵G

111111二元(N,K)线性码11m.. mk], m,e{0,1)信息组,K维行阵:m=[m码字,N维行阵:c=[GC2... C], C, {0,1)E111码字生成式:c=mG1-G:K×N生成矩阵,其元素取值于二元集合{0,1.cHT=0校验方程:Hc=011票H:r×N校验矩阵,其元素取值于二元集合!{0,1]。校验位数目。K: r=N-111111E福1111[1111111111141111111
4 二元(N,K)线性码 码字,N 维行阵: 信息组, K 维行阵: 码字生成式: c m G T cH 0 T 校验方程: Hc 0 1 2 , {0,1} m m m m m K i 1 2 , {0,1} N i c c c c c G :K×N 生成矩阵,其元素取值于二元集合 {0,1}。 H:r×N 校验矩阵,其元素取值于二元集合 {0,1}。 r =N- K :校验位数目

二元(N,K)线性码(续一)g11giNgig12g2Ng2g21g22④...@mkgkc=mG=mg,④mg,G:gkgkigk1gkN1(1)G的每个向量都是一个码字例: m=1, m2 =m,=..=mk=0c=g(2)二元(N,K)线性码C-Ic/可看成一个N重维线性空间,G的K个相互独立的行向量是它的一组基底(3)任意K个相互独立的N长码字都可作为N重维码空间的一组基底,用这个码字当作行向量组成生成矩阵,即可生成所有码字5
5 二元(N,K)线性码(续一) 11 12 1 21 22 2 1 1 1 2 N N K K K KN g g g g g g g g g g g g G G m m m 1 1 2 2 K K c m = g g g (1)G 的每个向量都是一个码字。 例: m m m m 1 2 3 = 1, = 0 K 1 c g (2)二元(N,K)线性码C={c}可看成一个N重维线性空 间, G的K个相互独立的行向量是它的一组基底。 (3)任意K个相互独立的N长码字都可作为N重维码空 间的一组基底,用这个码字当作行向量组成生成矩阵, 即可生成所有码字

吉祥二元(N,K)线性码(续二)系统码:码字的前(或后)K位照搬信息组的K个信息元S00auaira12g1对于前K位为信息01福a21a22a2rg2元的系统码,生成 G=[Ikxk......*:.矩阵G可分成2块:0akiakrgkak2校验方程:cHT =0招景g;是码字,满足g,HT=0 ,i=12....,K校验方程GHT=01AG=[IkxkA.福福验证:GH =[IkxkAkxll Ax I16
6 二元(N,K)线性码(续二) 11 12 1 2 1 1 22 2 2 1 2 1 0 0 0 1 0 0 0 1 r r K K K r K K Kr K a a a a a a a a a g g A g G I 系统码:码字的前(或后)K 位照搬信息组的K个信息元 对于前K位为信息 元的系统码,生成 矩阵G可分成2块 : T 校验方程: cH 0 gi 是码字,满足 校验方程 。 , 1, 2, , T i g H 0 i K T GH 0 T K r r r H A I G I A K K K r T T T K r K K K r K r r r K K K r K r K r r r 0 A GH I A A I I A A A I 验证:

吉群2、汉明距离与码的纠、检错能力检错:译码器能检测到是否有错误发生,码的检错能力用检测到的错误位数t,描述;纠错:译码器不但能检测到是否有错误发生,而且能纠正发生的错误,码的纠错能力用纠正错误的位数t.描述。无法检出或纠正的错误:码字出错而变为另一码字。这种情况最易发生在较为相似的码字之间。码的纠、检错能力与码的最小汉明距离关系:(1)一个码能够检测出ta个错误的充要条件:dmin≥ta+1(2)=个码能够纠正t.个错误的充要条件:dmin≥2t。+1(3)一个码能够纠正t.个错误,同时又能够检测出t个错误的充要条件:dmin≥t.十
7 2、汉明距离与码的纠、检错能力 检错:译码器能检测到是否有错误发生,码的检错能力用 检测到的错误位数td描述; 纠错:译码器不但能检测到是否有错误发生,而且能纠正 发生的错误,码的纠错能力用纠正错误的位数t c描述。 无法检出或纠正的错误:码字出错而变为另一码字。这种 情况最易发生在较为相似的码字之间。 码的纠、检错能力与码的最小汉明距离关系: (1)一个码能够检测出td 个错误的充要条件: dmin ≥ td +1 (2)一个码能够纠正t c个错误的充要条件: dmin ≥ 2t c +1 (3)一个码能够纠正t c个错误,同时又能够检测出td个错误的充 要条件: dmin ≥ t c +td+1 (td >t c )

二元线性分组码的最小汉明距离结论:二元线性分组码的最小汉明距离等于该码非零码字的最小汉明重量。E1例: C={00000,01101,10111,11010},求最小汉明距离11111W=311min酒W3-minmin福1111福8111
8 二元线性分组码的最小汉明距离 结论:二元线性分组码的最小汉明距离等于 该码非零码字的最小汉明重量。 例:C={00000,01101,10111,11010},求最小汉明 距离。 Wmin=3 dmin =Wmin=3

例“重复2次”编码的检错和纠错能力养编码:(“重复2次”0→000,码字:C={000, 111],dmm=31-111dmin ≥ta +1纠错:dmin ≥2t+1检错:dmin =3=2×1+1dmin =3=2+1译码译码接收序列接收序列000000000001001Error0010010Error0111011Error0100100Error1011101Error1101110Error111111119
9 例 “重复2次”编码的检错和纠错能力 “重复2次”编码:0→000, 1→111 码字:C ={000,111},dmin=3 接收序列 译码 000 0 001 Error 010 Error 011 Error 100 Error 101 Error 110 Error 111 1 min 1 d 检错: d t min d 3 2 1 接收序列 译码 000 0 001 0 010 0 011 1 100 0 101 1 110 1 111 1 min 2 1 c 纠错: d t min d 3 2 1 1

V“重复2次”码例比较(5,2)线性码和0码字c信息组m(5,2)线性码:0011110000000C=mG= 30101101min1010111与“重复2次”码的最小汉明距1111010离相同因此,检、纠错能力相同:能检出2个错误或纠正1个错误111111“重复2次”码:P=3×10-4R=1/3 bit/符号P, = 7.86×10-4R=2/5bit/符号(5,2)线性码:10怡蒙
10 例 比较(5,2)线性码和“重复2次”码 (5,2)线性码: 1 0 1 1 1 0 1 1 0 1 G 信息组m 码字c 00 00000 01 01101 10 10111 11 11010 c m G min d 3 与“重复2次”码的最小汉明距 离相同,因此,检、纠错能力相同: 能检出2个错误或纠正1个错误。 “重复2次”码: (5,2)线性码: 4 7.86 10 P e 4 3 10 P e R 2 5 R 1 3 bit/符号 bit/符号