ch7线性分组纠错编码.ppt

第七章 线性分组纠错编码 本章主要内容 信道编码的基本概念、原理 线性分组（纠错）码的一般概念 线性分组（纠错）码的生成矩阵和校验矩阵 线性分组（纠错）码的编码 线性分组（纠错）码的译码 二元Hamming码 从一个已知线性分组码来构造一个新的线性分组码 信道编码的基本概念 信道编码的目的 提高信息传输的可靠性（加冗余度）。 基本思想 根据一定规律在待发的信息中加入一些多余的码元（监督码元），以保证传输质量。 研究内容 怎样构造最小冗余度、最大抗干扰性能的“好码”。 检错码 纠错码 信道编码的基本原理 香农信道编码定理：RC，无差错传输。 对于一个给定的有干扰信道，如果信道容量为C，只要发送端以低于C的速率R发送信息(R为编码器输入的二元码元速率)，则一定存在一种编码方法，使编码错误概率p随着码长n的增加，按指数下降到任意小的值。 基本原理 在被传输的信息序列上附加一些码元(称为监督码元)，这些多余的码元与信息(数据)码元之间以某种确定的规则相互关联着。接收端根据既定的规则检验信息元与监督元之间的这种关系，如传输过程中发生差错，则信息元与监督元之间的这一关系将受到破坏，从而使接收端可以发现传输中的错误，乃至纠正错误。 检错和纠错 “好”——0 “坏”——1 无检错纠错能力 “好”——00 “坏”——11 接收： 00 01 10 11 译出： 好 ？ ？ 坏 检1位错码，无纠错能力 “好”——000 “坏”——111 接收： 000 001 010 011 100 101 110 111 译出： 好 ？ ？ ？ ？ ？ ？ 坏 译出： 好 好 好 坏 好 坏 坏 坏 检至少2位错码，或检1位错码并纠正 “好”——0000 “坏”——1111 接收： 0000 0001 0010 0011 0100 0101 0110 0111 译出： 好 好 好 ？ 好 ？ ？ 坏 接收： 1000 1001 1010 1011 1100 1101 1110 1111 译出： 好 ？ ？ 坏 ？ 坏 坏 坏 检2位错码，并能纠正1位错码 线性分组码的基本概念 (n,k)线性分组码 分组 k个信息元一组 变换 n个码元 线性 监督元与信息元之间呈线性关系 信源可发出 种不同的消息组。 (n,k)分组码共 个码字（许用码字），其中只有k个是线性独立的。 R=k/n 编码速率/码率 R越小，冗余度就越大，检错和纠错的能力越强；但也降低了传输信息的实际速率。R越大，码的效率也就越高或传信率越高。  系统码结构示意图(r=n-k) 例：(7，3)线性分组码设该码的码字为c6c5c4c3c2c1c0，其中c6、c5、c4为信息元；c3、c2、c1、c0为监督元，每个码元取值为“0”或“1”，即ci∈GF(2)。监督元可按下式计算： 码重：在信道编码中，定义码字中非零码元的数目为码字的汉明（Hamming)重量，简称码重。例如“010”码字的码重为1，记为 。“011”码字的码重为2，记为 码距：把两个码字之间对应码位上具有不同二元码元的位数定义为两码字的汉明距离，简称码距。例如dH(010,011)=1 最小汉明距离：码字集合中任意两码字间的最小距离，称为这一编码的最小汉明距离，以dmin表示；在非零码字中，重量最小者称为该码的最小汉明重量，它等于dmin 。 汉明距离三个性质： (1)对称性：d(C1，C2)＝d(C2，C1)； (2)非负性：d(C1，C2)≥0； (3)满足距离三角不等式： d(C1，C2)≤d(C1，C3)＋d(C3，C2)。 （n，k，dmin）：表示最小距离为dmin，码率为R＝k／n的线性分组码， dmin表示了码的纠错能力。 纠错码的基本任务：构造出R一定且dmin尽可能大的码，或dmin一定且R尽可能大的码。 MDS码：(n，k，d)线性分组码的最小距离dmin≤n－k＋1。若系统码的最小距离 dmin＝n－k＋1，则称此码为极大最小距离可分码，简称MDS码。 线性分组码的检错和纠错能力 结论 1.检测