《信息理论与编码》课程教学课件（讲稿）第5章 有噪信道编码 5.6 线性分组码

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

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

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

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

沃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/符号