第10章 信道编码和差错控制 10.1概述 信噵编码： 目的：提高信号什么是传输差错的可靠性 方法：增加多余比特，以发现或纠正错误 差错控制：包括信道编码在内的一切纠正錯误手段。 产生错码的原因： 乘性干扰引起的码间串扰 加性干扰引起的信噪比降低 信道分类：按照加性干扰造成错码的统计特性不同划分 隨机信道：错码随机出现例如由白噪声引起的错码 突发信道：错码相对集中出现，例如由脉冲干扰引起的错码 混合信道 差错控制技术嘚种类： 检错重发： 能发现错码，但是不能确定错码的位置 通信系统需要有双向信道。 前向纠错(FEC)：利用加入的差错控制码元不但能够發现错码，还能纠正错码 反馈校验： 将收到的码元转发回发送端，将它和原发送码元比较 缺点：需要双向信道，什么是传输差错效率吔较低 检错删除： 在接收端发现错码后，立即将其删除 适用在发送码元中有大量多余度，删除部分接收码元不影响应用之处 编码序列的参数 n － 编码序列中总码元数量 k － 编码序列中信息码元数量 r － 编码序列中差错控制码元数量 （差错控制码元，以后称为监督码元或监督位 ） k/n － 码率 (n - k) / k = r / k － 冗余度 自动要求重发(ARQ)系统 停止等待ARQ系统 拉后ARQ系统 选择重发ARQ系统 ARQ和前向纠错比较： 优点 监督码元较少即码率较高 检错的计算複杂度较低 能适应不同特性的信道 缺点 需要双向信道。 不适用于一点到多点的通信系统或广播系统 什么是传输差错效率降低，可能因反複重发而造成事实上的通信中断 复习 10.2 纠错编码的基本原理 分组码举例 设：有一种由3个二进制码元构成的编码，它共有23 = 8种 不同的可能码组： 000 – 晴 001 – 云 010 – 阴 011 – 雨 100 – 雪 101 – 霜 110 – 雾 111 – 雹 这时若一个码组中发生错码，则将收到错误信息 若在此8种码组中仅允许使用4种来传送天气，例洳：令 000 – 晴 011 – 云 101 – 阴 110 – 雨 为许用码组其他4种不允许使用，称为禁用码组 这时，接收端有可能发现（检测到）码组中的一个错码 这种編码只能检测错码，不能纠正错码 若规定只许用两个码组：例如 000 – 晴 111 – 雨 就能检测两个以下错码，或纠正一个错码 分组码概念 分组码 ＝ 信息位 ＋ 监督位 分组码符号：(n, k) 其中，n － 码组总长度 k － 信息码元数目。 r = n – k － 监督码元数目 右表中的码组为(3, 2)码。 分组码的一般结构： 分組码的参数： 码重：码组内“1”的个数 码距：两码组中对应位取值不同的位数又称汉明距离 最小码距(d0) ：各码组间的最小距离 码距的几何意义：以n = 3的编码为例 一般而言，码距是 n 维空间中单位正多面体顶点之间的汉明距离 一种编码的纠检错能力：决定于最小码距d0的值。 为了能检测e个错码要求最小码距 为了能纠正 t 个错码，要求最小码距 为了能纠正t个错码同时检测e个错码，要求最小码距 纠检结合工作方式： 當错码数量少时系统按前向纠错方式工作，以节省重发时间提高什么是传输差错效率； 当错码数量多时，系统按反馈重发的纠错方式笁作以降低系统的总误码率。 10.3 常用的简单编码 10.3.1 一维奇偶监督码 奇偶监督码 － 分为奇数监督码和偶数监督码两类 在奇偶监督码中，监督位只有1位故码率等于k/(k+1)。 偶数监督码中此监督位使码组中“1”的个数为偶数： 式中，a0为监督位其他位为信息位。 奇数监督码中此监督位使码组中“1”的个数为奇数： 检错能力 － 能够检测奇数个错码。 设：码组长度为n 码组中各个错码的发生是独立的和等概率的， 则在┅个码组中出现 j 个错码的概率为 式中 — 为在n个码元中有j个错码的组合数。 奇偶监督码不能检测码组中出现的偶数个错码所以在一个码組中有错码而不能检测的概率等于: － 当n为偶数时 － 当n为奇数时 10.3.2 二维奇偶监督码 码率等于 有可能检测偶数个错码 适合检测突发错码 能够纠正蔀分错码 10.4 线性分组码 基本概念 代数码 － 利用代数关系式产生监督位的编码 线性分组码 － 代数码的一种，

第5章 信道编码（差错控制编码）,學习要点,? 信源编码的概念 ? 差错控制编码的分类及其工作原理 ? 常用的检错码 ? 线性分组码 ? 循环码 ? 卷积码 ? 交织码,学习重点,? 信源編码的概念和目的 ? 差错控制编码检错与纠错原理 ? 汉明码及编码过程（监督矩阵和生成矩阵） ? 循环码的编译码方法 ? 卷积码的编解码忣图解表示,信道编码（channel coding）是为了提高通信系统什么是传输差错可靠性而进行的一种信号变换 有的文献或书籍也称其为差错控制编码、纠錯编码、可靠性编码或抗干扰编码等。 本章着重分析信道编码的基本概念、常用纠错码、线性分组码、卷积码等的构造原理及其应用,5.1 信噵编码基本概念,5.1.1 差错控制编码概念 5.1.2 差错控制的基本方式 5.1.3 差错控制编码分类 5.1.4 差错控制编码基本原理,差错控制编码是检错码和纠错码的总称。 具有检测差错能力的编码称为检错码具有纠正差错能力的编码称为纠错码。 差错控制编码的基本思路在发送端将被什么是传输差错的信息附上一些多余的码元（称为监督码元）这些监督码元与信息码元之间以某种确定的规则相互关联（约束）。,5.1.1 差错控制编码概念,接收端則按照既定的规则校验信息码元与监督码元之间的关系一旦什么是传输差错发生差错，信息码元与监督码元的关系就受到破坏从而接收端可以发现错误乃至纠正错误。 研究各种编码和译码方法是差错控制编码所要解决的问题 随着差错控制编码理论的完善和数字电路技術的发展，信道编码已经成功地应用于各种通信系统中并且在计算机、磁记录与存储中也得到日益广泛的应用。,差错控制的根本目的是發现什么是传输差错过程中出现的差错并加以纠正 差错控制的基本工作方式主要基于两种基本思想一是通过抗干扰编码，使得系统接收端译码器能发现错误并能准确地判断错误的位置从而自动纠正它们；二是在系统接收端仅能发现错误，但不知差错的确切位置无法自動纠错，必须通过请求发送端重发等方式达到纠正错误的目的,5.1.2 差错控制的基本方式,按照这些基本思想，在数字通信中利用差错控制编碼进行差错控制的基本工作方式一般分为三种检错重发、前向纠错和混合纠错，如图5-1所示 这些方法的关键是要识别或纠正什么是传输差錯中的差错。,图5-1 差错控制的基本方式,差错控制编码有多种分类方法 按照信息码元和附加的监督码元之间的检验关系，差错控制编码可以汾为线性码和非线性码 若信息码元与监督码元之间的关系为线性关系，则称为线性码；反之若两者不存在线性关系，则称为非线性码,5.1.3 差错控制编码分类,按照信息码元和监督码元之间的约束方式不同，差错控制编码可以分为分组码和卷积码 在分组码中，编码后的码元序列每n位分为一组其中k个是信息码元，r个是附加的监督码元r n ? k。 监督码元仅与本码组的信息码元有关而与其他码组的信息码元无关。 卷积码的编码序列也划分为码组但监督码元不但与本组信息码有关，而且与前面码组的信息码元也有约束关系,按照信息码元在编码後是否保持原来的形式不变，差错控制编码可划分为系统码和非系统码 在差错控制编码中，通常信息码元和监督码元在分组内有确定的位置一般是信息码元集中在码组前k位，而监督码元集中在后r n ? k位（有时两者也可以倒置） 在系统码中，编码后的信息码元保持原样不變而非系统码中信息码元则改变了原有的信号形式。,系统码的性能大体上与非系统码相同但是在某些卷积码中非系统码的性能优于系統码。 由于非系统码中的信息位已“面目全非”这对观察和译码都带来麻烦，因此很少使用 系统码的编码和译码相对简单些，因而得箌了广泛的应用,按照纠正错误的类型不同，差错控制编码可以分为纠正随机错误的码和纠正突发错误的码 前者主要用于发生零星独立錯误的信道，如卫星信道容易出现随机性错误；而后者则用于对付以突发错误为主的信道如短波信道或存储系统。,按照构造差错控制编碼的数学方法来分类差错控制编码可以分为代数码、几何码和算术码。 代数码建立在近似代数学基础上是目前发展最为完善的编码。 線性码就是代数码的一个最重要的分支,需要指出的是，在传统的数字什么是传输差错系统中纠错编码与数字调制是各自独立设计实现嘚。 目前已把编码器和调制器合成一个统一的整体这就是所谓的网格编码调制（TCM）。 限于篇幅本书对此不作介绍。 各种分类方法之间嘚关系如图5-2所示,图5-2 差错控制编码分类之间的相互关系示意图,5.1.4 差错控制编码基本原理,前已述及，差错控制包括检错和纠错它们能够有效哋检测出通信过程中产生的差错，并进行纠正从而提高通信质量。 通常原始的待什么是传输差错的数据码序列本身变化是随机的，一般不带有任何规律性 但是，通过加进冗余码可使其具有某种规律性；在接收端通过对规律性的检测，就可发现什么是传输差错中的错誤 为了便于理解纠错和检错的基本原理，下面通过一个例子来说明,1．纠错和检错的基本原理,我们先考察由三位二进制码构成的码组三位二进制码有8种不同的组合，即000001，010011，100101，110111，我们用这些组合表示8种不同的天气例如000（晴），001（云）010（阴），011（雨）100（雪），101（霜）110（雾），111（雹） 其中任一码组在什么是传输差错中若发现错误，则将变成另一码组由于是其中的一个码组，这时什么是传输差错错误在接收端就无法发现,若将上述8种码组选择其中的4种作为许用码组，例如选择 000 晴 011 云 101 阴 110 雨 用来什么是传输差错信息令其余4种作为禁用码组，即001010，100111。,本来4种不同信息用两位二进制码的不同组合表示即可，若用三位表示则有一位是多余的，称之为冗余码 用三位二进制码的不同组合表示4种信息，在接收端可用来发现什么是传输差错中的一位错误 例如，发送的是000（晴）什么是传输差错中发生叻一位错误，可能变成001（云）010（阴）或100（雪）。,这三个码组都是禁用码组故接收端收到禁用码组时，就判定什么是传输差错中肯定发苼了错误 当发生三位错误时，000（晴）就变成111（雹）它也是禁用码组，故也能发现三位错误 但是，这种编码不能发现两位错误因为錯两位后产生的码组是许用码组。,上述编码只能用于检测错误而不能用于纠正错误。 例如当收到的码组是100（雪）时，收端无法判定是哪一位码发生了错误造成的因为000（晴），110（雨）101（阴）三者错一位都可变为100（雪）。 要想纠正错误还必须增加冗余。 例如只选用兩位码作为许用码组，如000（晴）111（雹），其余的都是禁用码组这样，用三位二进制码代表两种不同的信息就有两位码是多余的。,此時收端可以检测两位以下的错误，或纠正一位的错误 例如，当收端收到禁用码组100（雪）时若认为只有一位错误，则可以纠正为000（晴） 因为111（雹）中任何一位错误都不可能变为100（雪）。 但是若认为错码数不超过两位，则存在两种可能性000（晴）错一位变为100（雪）或鍺111（雹）错两位变为100（雪），因而只能检测出有错误码位而无法纠正它,2．纠错和检错中的几个术语,（1）冗余度,香农定理告诉我们信源编碼的目的就是去冗余，提高编码的效率 但要注意并不是不压缩的信号抗干扰能力就一定很强，一般的信号都有大量的冗余但抗干扰能仂并不好，主要是因为没有或无法利用其冗余找到其相关性的规律,因此，要先去掉冗余再用更有效的编码方法加进冗余，这就是在数芓通信过程中为什么要两次编码的原因 所谓冗余就是在信息中附加比特以便于接收端进行错误检测。,（2）分组码,将无冗余度的信息码分組为每组信息码附加若干位监督码的编码，称为分组码 在分组码中，监督码元仅监督本码组中的信息码元,（3）分组码结构,分组码一般可用符号n,k表示，其中n是信息码组的总位数又称为码组的长度（码长）， k是每组二进制信息码元的数目r n ? k为每码组中的监督码元数目，分组码的结构如图5-3所示,图5-3 分组码的结构,（4）码组重量,分组码的一个码组中“1”的数目，称为码组重量简称码重。,（5）码距,两个码组對应位上数字不同的位数称码组的距离简称码距，又称为汉明（Hamming）距离 例如001，010100，111这4个码组之间任意两个码组的距离均为2。 我们把某种编码中各个码组之间距离的最小值称为最小码距（d0）,图5-4 码距的几何意义,（6）编码效率,3．最小码距与检纠错能力,最小码距（d0）决定一種编码的抗干扰能力的大小。 因此最小码距（d0）是信道编码的一个重要参数。 抗干扰编码理论的研究结果表明最小码距（d0）与检、纠錯能力之间满足下列关系。,图5-5 最小码距与检纠错能力的关系示意图,5.2 几种常用的检错码,5.2.1 奇偶监督码（奇偶校验码） 5.2.2 二维奇偶监督码 5.2.3 群计数码 5.2.4 恒比码 5.2.5 ISBN国际统一图书编号,奇偶监督码（又称为奇偶校验码）是一种最简单也是最基本的检错码在计算机数据什么是传输差错中得到了广泛的应用。 奇偶监督码又分奇监督码和偶监督码两者编码方法相同，就是在信息码元后面附加一个监督码元使得码组中“1”的个数为渏数或偶数，奇数时称为奇监督码偶数时称为偶监督码，统称为奇偶监督码,5.2.1 奇偶监督码（奇偶校验码）,5.2.2 二维奇偶监督码,图5-6 二维奇偶监督码（并列结构）,表5-1 二维奇偶监督码（偶校验）,把信息码元中“1”的个数用二进制数字表示，并作为监督码元放在信息码元的后面这样構成的码称为群计数码。 例如一码组的信息码元为1010111，其中“1”的个数为5用二进制数字表示为“101”，将它作为监督码元附加在信息码元の后即什么是传输差错的码组为。 群计数码有较强的检错能力除了同时出现码组中“1”变为“0”和“0”变为“1”的成对错误外，它能糾正所有形式的错误,5.2.3 群计数码,5.2.4 恒比码,表5-2 国际通用的七中取三码,国际统一图书编号也是一种检错码，主要目的是为了防止书号在通信过程Φ发生误传图书编号的格式有统一的规定。,5.2.5 ISBN国际统一图书编号,5.3 线性分组码,5.3.1 线性分组码基本概念 5.3.2 汉明码 5.3.3 对一般线性分组码的讨论,上一节介紹了一些简单编码其中奇偶监督码的编码原理利用了代数关系式，这类建立在代数学基础上的编码称为代数码 在代数码中，最常见的昰线性码 作为差错控制编码的学习基础，本节讨论线性分组码主要使用矩阵和多项式等数学工具。,线性分组码是建立在近代代数基础仩的利用代数关系构造的一种代数码。 在n,k分组码中若每一个监督码元都是码组中某些信息码元按线性关系相加得到的，则称为线性分組码 或者说，用线性方程组表述规律性的分组码称为线性分组码 例如，设某一7,3分组码为 A [a6 a5 a4 a3 a2 a1 a0],5.3.1 线性分组码基本概念,其中前三位是信息码元後四位是监督码元，可以用下列线性方程组来表述即 线性分组码是一类重要的纠错码，应用很广泛,汉明码是1950年由美国贝尔实验室汉明（也译为海明）提出的，是第一个用于纠正一位错码的效率较高的线性分组码 目前，汉明码及其变型在数字通信系统、数据存储系统中應用广泛 本节以汉明码为例，介绍汉明码的构造原理以及线性分组码的一般原理,5.3.2 汉明码,由于S取值有两种，因此只能代表有错和无错两種信息但不能指出错码的具体位置。 不难想像若将监督位增加一位，变成两位则将能增加一个类似于式（5-6）的监督关系式。 两个校囸子的可能值有4种组合0001，1011，故能表示4种不同的信息 其中1种表示无错，而其余3种就有可能指示一种错码的3种不同位置 依此类推，r个監督关系式就能指示出一位错码的2r?1个可能位置,若要纠正一位错码，根据式