信息论与编码第6章信道编码.ppt

1,第6章 信道编码,信道编码的目的：实现信息在信道上正确传输，包括：线路编码正确接收载有信息的信号的编码 纠错编码 避免少量差错信号对信息内容的影响，包括差错控制、检错、纠错,学习得来终觉浅，绝知此事要自悟,本章内容,信道编码的概念和分类线性分组码循环码卷积码编码与调制的结合TCM码运用级联、分集与信息迭代概念的纠错码,6.1 信道编码的概念,信源编码降低相关，去除冗余，提高通信系统有效性。信道编码增加冗余(监督码)，检纠错误，提高通信系统可靠性。定义：为了与信道的统计特性相匹配，并且区分通路和提高通信的可靠性，在信源编码的基础上，按一定规律加入一些称之为监督码元的新的码元，以实现检错和纠错目的的编码方法。,6.1.1 信道编码的分类,差错控制的基本方式 有反馈方式：反馈重发（Automatic Repeat Request）信息反馈（IRQ，Information Repetition Request）混合纠错（HEC,Hybird Error Correction）无反馈的方式：前向纠错（Forward Error Correction，FEC）,纠错码的分类,根据监督码元与信息组之间的关系,分组码卷积码,信息码元是否发生变化,系统码非系统码,构造编码的数学方法,代数码几何码算术码,根据监督码元和信息码元的关系,线性码非线性码,根据码的功能,检错码纠错码纠删码,按纠误的类型,纠随机差错码纠突发差错码纠混合差错码,按码字中码元的取值,二元码多元码,按对信息元的保护能力,等保护纠错码不等保护纠错码,纠错码的具体分类,信息元 监督元 码字 分组码 卷积码 线性码与非线性码 码字的汉明距离和汉明重量 错误图样,6.1.2 纠错码的相关概念,有扰信道编码错误概率满足 纠错检错就是使。方法有:,可靠性函数，包括：信道容量 或者减小码率 冗余度纠错检错原理。例如，如果用2bit表示4种意义，是无法发现差错的。如果用3bit来表示4种意义，就有可能发现差错，因为3bit有8种组合，用其表示4种意义，还有4种冗余组合，如果传输差错使得收到的3bit组合落入4种冗余组合中，就可以断定一定有差错位。,6.1.3 纠错检错基本原理,噪声均化纠错检错原理,噪声均化差错均匀分摊给各个码字 噪声的总量、分布共同决定干扰的危害 突发差错集中的噪声干扰 随机差错分散的噪声干扰 例如:7个码元上产生2个差错。如果2个差错集中在前7码元(同一码字)上，该码字将出错。如果差错分散在前后两个码字上，每个码字承受一个差错，则每个码字差错的个数都没有超出其纠错能力范围，这两个码字将全部正确解码。,6.1.4 有噪信道编码定理,有噪信道编码定理-香农第二编码定理1、译码规则对码元译码的影响 例：在二元无记忆对称的信道中，单个符号的错误传递概率是，正确传递的概率为。,二元对称无记忆信道,假设p=3/4，如果接收到符号“0”就译码为发送的符号为“0”，接收到符号“1”就译码为发送的符号为“1”，按此译码规则，平均错误概率为 相反，如果译码规则改变为接收到符号“1”，译为符号“0”，接收到符号“0”，译为符号“1”，平均错误概率为 结 论：即使同样的信道，选择的编码方法不同，所得到的对码元的译码效果是不同的。,2、译码方法 最大后验概率准则，也称“最小错误准则”;最大似然译码准则;最小距离译码准则;3、重复传送与编码的可靠性 如图所示的二元对称无记忆信道 在该信道中，要发送消息符号“0”，连续发送三次；同样，发送消息“1”也连续发送三次,输入端的许用码字仅仅有,输出端有8种可能的输出码字，其信道矩阵为,根据最大似然译码规则，如果输入等概率，那么译码函数为：,平均错误概率为,非重复编码平均错误概率为0.01，重复编码大大地降低了错误概率，同时，也降低了信息传输率。如何折衷这个矛盾？香农第二定理，即有噪信道编码定理。离散无记忆信道 是信道传递概率，信道容量为。在传输率,码长 足够长，可以在输入 符号集中找到 个码字组成的一组码 和相应的译码规则，使译码的评均错误概率任意小。,有噪信道编码逆定理,设离散无记忆信道，当 时，找不到编码，译码错误概率任意小。定理6-3 带限高斯白噪声加性信道(1)若，存在编码方法，使信号传输率为 时，平均错误概率任意小。(2)若，这样的编码方法不存在。,6.2 线性分组码,6.2.1 线性分组码的数学基础1、群定义：在非空集合S上定义加法或乘法运算，满足(1)封闭性；(2)结合性；(3)可逆性；(4)单位元存在；基本概念：加法群；乘法群；阿贝尔群；无限群；有限群；循环群；群的生成元。,2、环、域和伽罗华域,同时规定加和乘两种代数运算，并满足如下条件的集合R称为环。(1)是加法交换群。(2)乘法满足封闭性。(3)乘法满足结合律。(4)分配律。,基本概念:带幺环,多项式环，环的左（右）零因子，整环，环的理想，真理想，主理想；同余类。,域和伽罗华域,定义：同时规定加法和乘法两种代数运算的集合F，并满足：(1)集合F对规定的加法运算构成交换群。(2)集合F中的全体非零元素对乘法运算构成交换群；(3)对加法和乘法运算满足分配律。,有无限个元素的域称为无限域，有限个元素的域称为有限域，有限域又称为伽罗华域(Galois Field)，含q个元素的域称为GF(q)。,基本概念:,子域，扩域，域的特征,3、多项式理论,域F上的n次多项式 定理 设 中有唯一的多项式 满足 整除：同余：最小公倍式：最大公因式：,域上多项式集合,是有单位元的交换环,素(既约)多项式,若 中只有因式 则称 为域F上的不可约多项式。多项式剩余类环 用 或者 表示所有这样多项式的集合 表示 的同余类的集合多项式剩余类环,例6-9,取 上的多项式，将 中任意多项式除以，余式只有，相应的剩余类用 来标记,那么,其加法和乘法如下,定理 若 次首一多项式 在 上是既约多项式，则以 为模的多项式剩余类环 是一个有 个元素的有限域，又记其为（证明参考教材p193),例,以既约多项式 为模，求有限域 即 解：剩余类的一般表达式为：16个代表元依次为,4有限域的性质和代数结构,1）有限域 的结构 对 满足 的最小正整数，称为元素 的周期。定理6-6：在有限域 中(1)是循环加群，它的非零元素的周期等于其域的特征；(2)是循环乘群，共有 个乘群的生成元。乘群 的生成元 称有限域 的本原元，的阶为，即，且,本原元性质定理6-7,(1)的元素的阶都是 的因子，的所有元恰是 的根。(2)若 是 的本原元，则当且仅当 时，也是本原元。非本原元 的阶是例 2是 的生成元，即是 的本原元。另一元素，但2和 不互素,故4不是本原元。,2）有限的多项式 域的结构,定理6-8 设F是有限域，是其子域，那么F的元素的个数(记作|F|)一定是q的一个幂次，即 为素数。定理6-9 设 是有 个元的有限域，是 其素子域，为特征。若 是 的含 个元的子域，则 存在，使 且。反之，若，则 一定有唯一的一个子域，其元为，且若 和 是 的两个子域，当且仅当 时，,定理6-10,(1)的乘法群 是循环群，其生成元 称为 的本原元。的阶数是。的其它元的阶是 的因子，特别地，的阶数为 的本原元共有 个。对 来说，一切元的阶数都是奇数。(2)设F是特征为 的域，则恒有：,续,(3)设 是 次多项式，若 使得，则 也是 的根。次多项式 只有 个根，根系列中只有 个根的重复 极小多项式与本原多项式。,3）极小多项式与本原多项式,F是有限域，上以 为根，次数最低的首一多项式，称 在 上的极小多项式。极小多项式的性质定理：(1)F是有限域,对,在 上有唯一的既约极小多项式，也就 是，特别地：,(2)设F是有限域，中的 阶元，则有。若 中的阶是，那么 上的极小多项式 就是 次多项式，而且 是 的 个两两互异的根，其在 中的阶均为。特别地，当F是 时，中的本原元在 上的极小多项式是 次多项式，其 个根都是 的本原元。也就是，的极小多项式为,（续）,以 中的本原元为根的多项式，称为本原多项式 本原元的阶为，若 是本原元，则 的本原多项式的共轭根系为：因此，上的本原多项式必是 次多项式,例 求以 为模的多项式的本原元,解：无一次因式和三次因式。二次多项式可能为：，显然 不是 的因式。又因为 所以 不存在二次因子，是既约的。由于在 中，1是1阶元，非本原元，对，计算如下：,(计算过程),因此，是 阶元。所以，是本原元。其非本原元 的阶数是 即，由此求得其余元的阶数，见表6-7所示：,表6-7 元的本原元的 幂的表示及阶数,的计算方法：,5有限域上的线性代数,1)线性空间的基本概念在域F上非空集合V上定义加和乘运算：并满足：(1)是加法交换群；(2)线性性；则称V是域F上的线性空间，即矢量空间，其元称矢量,几种典型的矢量空间,或者,或者,矢量的线性组合,矢量的线性相关与线性无关,可由S中的矢量线性表示,空间V由空间S线性生成,空间的基底S，维数dimV,矢量的正交,正交补,两个正交补空间V1和V2满足,6.2.2 线性分组码的基本概念,分组码的编码步骤:划分消息组；消息变换：,标记为,数域为，则消息为，较大，,编码器存储容量会很大,为什么要编码？,线性分组码 个 重矢量的集合 构成 维线性空间的一个 维子空间,6.2.3 生成矩阵和一致校验矩阵,信息输出码字 生成矩阵 结论：对 码，所有码字均可表示为维数为 的 个线性无关码字的线性组合，任何一组线性无关的码字均是码空间的一个基底，一组基底所构成的矩阵就是一个生成矩阵。,的生成方法：,寻找 个线性无关的 维矢量。再作行列变换，可得到标准生成矩阵 例：以为基底，设计(7,3)线性分组码。解：生成矩阵 域中，消息 构成的矢量共8个，是其中一个消息矩阵，因此,码字矩阵,标准生成矩阵的分块形式,一致校验矩阵,或者,一致校验矩阵H 所对应的方程称为一致校验方程,一致校验矩阵和生成矩阵的关系,综前述必有同理例：二元(7,3)码的生成矩阵G1如下，计算生成的(7,3)码。,解：根据公式，计算结果如下,例：二元(7,3)码的生成矩阵G2如下，计算生成的(7,3)码。,解：生成矩阵是系统阵，按系统阵计算公式计算，结果如下：,6.2.4 线性分组码的纠错能力与码最小距离的关系,在重复的分组码中，如果最小汉明距离,两个码字在传输后发生一位码元随机错误的接收序列是两个互不相交的集合，也就是 与 不会产生交集。因此，根据最小距离译码准则译码就能纠正发生的一位码元的随机错误。其三维空间解释图如下：,分组码 的纠错能力和检错能力结论,定理：分组码 最小汉明距离为，则(1)检测 个随机错误的充要条件是(2)纠正 个随机错误的充要条件是(3)纠正 个随机错误，同时检测 个随机错误，则需满足,的线性分组码 与 的关系,定理：设 线性分组码 的校验矩阵为,码的最小距离为 的充要条件是 中任意 个列向量线性无关,且 个列向量线性相关.码 的 矩阵是,其秩为 从定理6-12知,称 为最小距离的辛莱顿限。,6.2.5 伴随式及标准阵列译码,1、纠错原理：标记 或者 为伴随式，由伴随式可判断错误图样，进而检测和纠正差错。伴随式与发送码子无关，仅与错误图样有关,例：下表的(7,3)线性分组码的一致校验矩阵为(1)如果传输无差错，则(2)如果有1个码元出错，假设 则,例题续,(3)如果传输有两个码元差错，假设将其表示为，则，容易验证,因此，不能确定,2个错误码元的位置，只能判断发生了2位码元,的错误。,2、标准阵列译码和译码表,实际应用中，对于 线性分组码，将所有 个长为 的接收序列划分为 个互不相交的子集 并使之与许用码字 按最大似然译码准则一一对应，并列成表格，这个表格称为标准阵列译码表。(n,k)线性分组码的标准阵列表,，,例6-18 设(5,2)系统线性码的生成矩阵为,详细解答过程参考教材p204结论：任意 线性码，有个 伴随式，可以纠正小于等于 个随机错误,构造该码的标准阵列译码表。,伴随式的汉明限、完备码：,定义：能纠正一位随机错误的完备的线性分组码。根据定义：二元汉明码：,6.2.6 汉明码,例：构造 的(7,4)汉明码,解：非零长为3的全部二元序列对应的一致校验矩阵 其对应的一个系统校验矩阵为 对应的标准生成矩阵为,根据 计算码字，所得系统码如下表,汉明码,6.3 循环码,6.3.1 循环码的多项式描述码多项式:循环码多项式:性质：,6.3.2 循环码的生成矩阵,循环码的 次生成多项式 模 的生成多项式循环码的生存矩阵,6.3.3 系统循环码,系统循环码，必须每个码字前面 位码元为信息元，后面 位码元为校验元.对应多项式，对应 的高次幂。,结论：系统循环码的构造步骤,1、信息多项式 乘;2、用 除 得余式；3、构造码字。系统循环码的标准生成矩阵获得方式：选择,其矩阵形式为 就是，即,例 如下表所示(7,4)系统汉明码，能构成循环 码，其生成多项式 求信息组 对应系统循环码的码字，及其系统循环码的生成矩阵,解：对应的信息多项式为 则,续,(7,4)系统汉明码,6.3.4 多项式运算电路,多项式运算符号移位寄存器 2输入与门 模2加 乘法器多项式加乘法电路,多项式乘法电路多项式除法电路,6.3.5 循环码的编码器与实现电路,循环码的多项式可表示为:编码步骤:首先，用 乘。其次，用 除，得商 和余式,6.3.6 循环码的解码器,判别原理：余项是否为零 纠错步骤：用 除，得余式 按余式，用查表的方法或通过某种计算得到错误图样从 中减去，便得到已经纠正错码的原发送码组,6.3.7 常用的循环码,1、截短循环码2、BCH码解决汉明码只能纠错1位的不足 本原BCH码：生成多项式 中含有最高次数为m的本原多项式，码长，纠错数3、RS码 生成多项式根是GF(q)域的本原根 纠错数：；码长：；校验位数目：最小距离：,6.4 卷积码,卷积码基本定义与编码原理标记：原理方框图：,例：卷积码 的工作过程,编码器的序列描述方法,树状图,网格图状态图,卷积码的解析表示,生成矩阵以 码为例移位寄存器起始状态全为零，输出第二个信息比特 输入时，输出 当第个 信息比特 输入时，输出为,上式用矩阵形式表达为：未稳定前,多项式表示,输入序列的一般多项式表示：表示延时算子，用多项式表示移位寄存器各级与模2加的连接关系 例如教材图6-17的卷积码编码器相应的生成多项式可表示为,生成矩阵与生成多项式的关系,已知卷积码的生成序列为 或 其中,卷积码的最大似然译码维特比算法,1、分支度量、路径度量和最大似然译码(2,1,2)卷积码原理图 其生成多项式矩阵为其对应的网格图,消息序列码字接收序列发送序列 的似然函数其估计 其每一分量 称为分支度量。,2、Viterbi译码算法,最大似然译码就是要在网格图上所有可能的路径上选一条具有最大路径度量的路。也就是寻找幸存路径 例 对前述(2,1,2)网格图所描述的卷积码，若接收到的二元对称信道输出序列为 试寻找最大似然路径。,6.5 编码与调制的结合TCM码,调制与编码作为一个整体的通信系统模型 信号通过AWGN信道，那么接收端收到的信号为 在收端采用最大似然相干检测(MLSE),则解调器输出的错误概率为,欧几里德距离,信噪比,归一化欧氏距离,因此，针对不同的调制方式和映射规则，寻找有最大,的卷积码，是编码与调制结合的一个最关键的问题。,编码的作用：,使信号网格图中信号序列之间的欧氏距离增加二、四进制的无记忆已调信号中使用的卷积码 QPSK;2PSK;ASK;进制调制的无记忆已调信号中所用的卷积码 8PSK;16QAM;UB码；,6.6 运用级联、分集的纠错码,6.6.1 乘积码与级联码1、级联码产生背景：降低复杂度，产生长码 串行级联码 维比特Viberti最大似然译码算法适合于约束度较小的卷积码，级联码的内码常用卷积码，外码采用分组码如RS码，BCH码等等,卷积码+分组码+突发差错信道，需要安装交织器,其结构如下图交织器的作用：对数据块作伪随机的置换，使差错随机化。交织器用于内码外码间，能随机化Verterbi译码产生的突发差错。,带交织器的串行级联分组码(SCBC),结构图如下：2、乘积码乘积码：对交织块的行和列都作编码。乘积码码阵图如下：,6.6.2 Turbo码,Turbo码开创了香浓随机编码理论的应用研究之先河。Turbo码PCCC并行级联卷积码 1、Turbo码的编码 编码器的构造,2、Turbo码的译码,Turbo码译码器与编码器对应，有两个分量译码器，二者可以为串行连接或者并行连接。并行级联译码器,串行级联译码器其他编码方法：(1)低密度奇偶校验码；(2)空时码,我们致力于使得本书上达思想与方法，下及实现与应用，但是力所不及，欢迎多提宝贵意见至http:/,学习得来终觉浅，绝知此事要自悟,