第5章 有噪信道编码.pptVIP

5.6 线性分组码 信道编码的目的是为了降低平均差错率，又称纠错编码。 香农第二编码定理告诉我们，只要信息率小于信道容量，那么就可使平均差错率接近于零，但香农并没有给出切实可行的实现方法。香农的有噪声信道定理的意义在于，它告诉我们什么是通过努力可以做到的事情，什么是不可能做到的事情。 纠错编码理论几乎与信息论同时创立，创始人是汉明。 纠错编码的基本思路：引入可控冗余，即在信息序列中加入一些冗余码元（或称校验码元）。 译码：利用码元之间的相关性质来检测错误和纠正错误。 纠错编码的基本概念 分组码：先将信息序列分成K个符号一组，称为信息组，然后在信息组中加入一些校验码元组成N长码字，由此得到的码称为（N，K）分组码。分组码中的任一码字的码长为N，所含的信息位数目为K、校验位数目为N-K。 线性码：线性码的最重要性质是线性特性，即码中任意两个码字的和仍为码字。否则为非线性码。 循环码：循环码是线性码的一个子集。循环码中任一码字循环移位后仍为该码的码字。否则为非循环码。 一致性校验矩阵H 1、线性分组码的生成矩阵和校验矩阵 （以（5，2）分组码为例） 码字长度N=5： 编码函数： 信息组长度 K=2： 码字由信息元的模2线性组合生成，因此是二元线性分组码，简称为线性码。 编码函数的矩阵表示： 校验方程的矩阵表示： 生成矩阵G 二元（N，K）线性码 码字，N 维行阵： 信息组， K 维行阵： 码字生成式： 校验方程： G ：K×N 生成矩阵，其元素取值于二元集合 {0，1}。 H：r×N 一致性校验矩阵，其元素取值于二元集合 {0，1}。 r =N－ K ：校验位数目。 二元（N，K）线性码（续一） （1）G 的每个向量都是一个码字。 例： (2)二元(N，K)线性码C={c}可看成一个N重K维线性空间，G的K个相互独立的行向量是它的一组基底。 (3)任意K个相互独立的N长码字都可作为N重维码空间的一组基底，用这个码字当作行向量组成生成矩阵，即可生成所有码字。 二元（7,3）分组码 G1 000 001 010 011 100 101 110 111 码 0000000 0011101 0100111 0111010 1001110 1010011 1101001 1110100 G2 000 001 010 011 100 101 110 111 码 0000000 1110100 1010011 0100111 1001110 0111010 0011101 1101001 G3 000 001 010 011 100 101 110 111 码 0000000 0011110 0100111 0111001 1001011 1010101 1101100 1110010 二元（N，K）线性码（续二） 系统码：码字的前（或后）K 位照搬信息组的K个信息元。 对于前K位为信息元的系统码，生成矩阵G可分块成 ： 校验方程： gi 是码字，满足校验方程 。 验证： 例： 2、汉明距离与码的纠、检错能力 检错：译码器能检测到是否有错误发生，码的检错能力用检测到的错误位数td描述； 纠错：译码器不但能检测到是否有错误发生，而且能纠正发生的错误，码的纠错能力用纠正错误的位数tc描述。 无法检出或纠正的错误：码字出错而变为另一码字。这种情况最易发生在较为相似的码字之间。 码的纠、检错能力与码的最小汉明距离关系密切，具体结论如下： (1)一个码能够检测出td 个错误的充要条件： dmin≥td +1 (2)一个码能够纠正tc个错误的充要条件： dmin≥2tc +1 (3)一个码能够纠正tc个错误，同时又能够检测出td个错误的充要条件：dmin2tc +1和dmin≥tc +td+1 二元线性分组码的最小汉明距离 结论：二元线性分组码的最小汉明距离等于该码非零码字的最小汉明重量。 例：C={00000,01101,10111,11010}，求最小汉明距离。 Wmin=3 dmin=Wmin=3 例 “重复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 检错： 接收序列 译码 000 0 001 0 010 0 011 1 100 0 101 1 110 1 111 1 纠错： 例 比较(5，2)线性码和“重复2次”码 (5，2)线性码： 信息组m 码字c 00 00000 01 01101 10 10111 11 11010 与“重复2次”码的