《信息理论与编码》课程教学课件（讲稿）第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重维码空 间的一组基底，用这个码字当作行向量组成生成矩阵， 即可生成所有码字