差错控制编码 (2)课件

《差错控制编码 (2)课件》由会员分享，可在线阅读，更多相关《差错控制编码 (2)课件（59页珍藏版）》请在金锄头文库上搜索。

1、1,通信原理,第11章差错控制编码,2,11.1 概述 信道分类：从差错控制角度看 随机信道：错码的出现是随机的 突发信道：错码是成串集中出现的 混合信道：既存在随机错码又存在突发错码 差错控制技术的种类 检错重发 前向纠错 反馈校验 检错删除,3,差错控制编码：常称为纠错编码 信息码元 k 监督码元 n-k 编码效率(简称码率) 信息码元个数与总码元个数之比k/n 冗余度：监督码元数(n-k) 和信息码元数 k 之比。 差错控制以降低信息传输速率为代价换取提高传输可靠性。,4,11.2 纠错编码的基本原理 分组码基本原理： 所有比特用于传送信息 3位二进制数可构成8种不同组合，若将其全部用来

2、表示8种不同天气， “000”（晴），“001”（云）， “010”（阴），“011”（雨）， “100”（雪），“101”（霜）， “110”（雾），“111”（雹）。 问题：其中任一码组在传输中若发生错码都将变成另一个信息码组 接收端将无法发现错误。,许用码组,5,部分比特用于传送信息 若在上述8种码组中只准许使用4种来传送天气，例如： “000”（晴），“001”（云）， “011”（雨）， “010”（阴）， “101”（霜）， “100”（雪）， “110”（雾），“111”（雹）。 发端错一位或三位码，收端可以检测出来 信息量降低，但检错能力提高了 发端错两位码，收端检测不出来?,

3、许用码组,禁用码组,增大冗余度 即增加监督位,6,分组码的结构 将信息码分组，为每组信息码附加若干监督码的编码称为分组码 。 在分组码中，监督码元仅监督本码组中的信息码元。 信息位和监督位的关系，如,7,分组码的一般结构 分组码的符号：(n, k) N 码组的总位数，又称为码组的长度（码长）， k 码组中信息码元的数目， n k r 码组中的监督码元数目，或称监督位数目。,8,分组码的码重和码距 码重：码组中“1”的个数 码距：两个码组中对应位上不同数字的个数，又称汉明距离。 最小码距d0 ：某种编码中各个码组之间距离的最小值)。 码距的几何意义 每个码组的3个码元的值(a1, a2, a3)

4、就是此立方体各顶点的坐标。 码距概念在图中对应于各顶点之间沿立方体各边行走的几何距离。,9,码距和检纠错能力的关系 一种编码的最小码距d0的大小直接关系着这种编码的检错和纠错能力 为检测e个错码，要求最小码距 d0 e + 1 为了纠正t个错码，要求最小码距d0 2t + 1 为纠正t个错码，同时检测e个错码，要求最小码距,10,11.4简单的实用编码 11.4.1 奇偶监督码 奇偶监督码只有一位监督位 偶监督保证码组中“1”的数目为偶数，偶监督关系式： 式中a0为监督位，其他位为信息位。 奇监督保证码组中“1”的数目为奇数，奇监督关系式：,11,11.5 线性分组码 基本概念 代数码：建立在

5、代数学基础上的编码。 线性码：信息位和监督位是由一组线性代数方程联系着的。 汉明码 定义：能够纠正1位错码且编码效率较高的一种线性分组码,12,汉明码的构造原理。 监督关系式 校正子 若S = 0，无错码；若S = 1，有错码 一个校正子S不能指出错码的位置 多个校正子的组合可指出错码位置 增多校正子 增多监督关系式 增多监督位 r个监督关系式能指示1位错码的 个可能位置 指示1位错码的n种可能位置的监督位个数要求,13,例：设分组码(n, k)中k = 4，为了纠正1位错码，由上式可知，要求监督位数 r 3。若取 r = 3，则n = k + r = 7。,错码位置与校正子关系,监督关系式,

6、14,由监督关系式得出的信息位与监督位,接收端收到每个码组后，先计算出S1、S2和S3，再查表判断错码情况。,表中所列的(7, 4)汉明码的最小码距d0 = 3。因此，这种码能够纠正1个错码或检测2个错码。由于码率k/n = (n - r) /n =1 r/n，故当n很大和r很小时，码率接近1。可见，汉明码是一种高效码。,15,线性分组码的一般原理 线性分组码的构造 H矩阵（监督阵）,H AT = 0T 或 A HT = 0,监督阵,16,H矩阵的性质： H的行数就是监督关系式的数目，等于监督位个数r。 典型监督阵可分解为P Ir形式，P为r k阶矩阵，Ir 为r r阶单位方阵。 由代数理论可

7、知，H矩阵的各行应该是线性无关的,17,G矩阵（生成矩阵）,Q为一k r阶矩阵，Q = PT 在信息位给定后，用信息位的行矩阵乘矩阵Q就产生出监督位,18,生成阵,如果找到了码的生成矩阵G，则编码的方法就完全确定了。 具有IkQ形式的生成矩阵称为典型生成矩阵。,系统码,19,G矩阵的性质： G矩阵的各行是线性无关的。 G的各行本身就是一个码组。 如果已有k个线性无关的码组，则可以用其作 为生成矩阵G。,20,错误图样,B A = E,错误图样,接收码,发送码,21,线性分组码的性质 封闭性：是指一种线性码中的任意两个码组之和仍为这种码中的一个码组。 两个码组(A1和A2)之间的距离（即对应位不

8、同的数目）必定是另一个码组(A1 + A2)的重量（即“1”的数目）。 码组间的最小距离就是码组的最小重量（除全“0”码组外）。,22,11.6 循环码 11.6.1 循环码原理 循环性：指任一码组循环移位（即将最右端的一个码元移至左端，或反之）以后，仍为该码中的一个码组。 一种(7, 3)循环码的全部码组(an-1 an-2 a0),23,码多项式 码组的多项式表示法 把码组中各码元当作是一个多项式的系数，即一个长为n的码组表示为 xn仅是码元位置的标记，不关心xn的取值。 码多项式的按模运算 整数运算中的模n运算 若一个整数m可以表示为 式中，Q 整数，则在模 n 运算下，有 m p (模

9、n) 即，在模 n 运算下，一个整数m等于它被 n 除得的余数。,24,码多项式运算中的模运算。 若一任意多项式F(x)被一 n 次多项式N (x)除，得到商式Q(x)和一个次数小于n的余式R(x)，即 则写为 码多项式系数仍按模2 运算，即系数只取 0 和1。 如， 因为,注意，由于在模2运算中，用加法代替了减法,25,循环码的生成矩阵G k个线性不相关的已知码组可构成生成矩阵G 用g(x)表示(n, k)循环码中前(k-1)位皆为“0”的码组，则g(x)，x g(x)，x2 g(x)，xk-1 g(x)都是码组，且是线性无关的。(左移) g(x)必须是一个常数项不为“0”的(n - k)次

10、多项式，而且是(n, k)码中次数为(n k)的唯一多项式（线性无关） 唯一的(n k)次多项式g(x)为码的生成多项式 循环码的生成矩阵G可得,26,所有码多项式T(x)都可被g(x)整除，且任意一个次数不大于(k 1)的多项式乘g(x)都是码多项式 循环码的码多项式 在循环码中，若T(x)是一个长为n的许用码组，则xiT(x)在按模xn + 1运算下，也是该编码中的一个许用码组，即若 则T (x)也是该编码中的一个许用码组。,27,如何寻找任一(n, k)循环码的生成多项式 循环码的生成多项式应该是(xn +1)的一个(n k)次因式 为了求(7, 3)循环码的生成多项式g(x) 需要从(

11、x7 + 1)中找到一个(n k) = 4次的因子,上两式都可作为生成多项式。 选用的生成多项式不同，产生出的循环码码组也不同,28,11.6.2 循环码的编解码方法 循环码的编码方法 编码原则 从(xn + 1)的因子中选一个(n - k)次多项式作为g(x)。 所有码多项式T(x)都可以被g(x)整除。 编码步骤： 用xn - k乘m(x) 用g(x)除xn - k m(x)，得到商Q(x)和余式r(x) 编出的码组T(x)为 T(x) = xn - k m(x) + r(x),29,循环码的解码方法 解码要求：检错和纠错。 检错解码原理：在接收端将接收码组R(x)用原生成多项式g(x)去

12、除，判断余式。 纠错解码原理：为了能够纠错，要求每个可纠正的错误图样必须与一个特定余式有一一对应关系。步骤如下： 用生成多项式g(x)除接收码组R(x)，得出余式r(x)。 按余式r(x)，用查表的方法或通过某种计算得到错误图样E(x)； 从R(x)中减去E(x)，便得到已经纠正错码的原发送码组T(x)。 通常，一种编码可以有几种纠错解码方法，上述解码方法称为捕错解码法。,30,11.7 卷积码 非分组码概念： 卷积码是一种非分组码，更适用于前向纠错。 卷积码监督码元不仅和当前的k比特信息段有关，而且还同前面m = (N 1)个信息段有关。 约束度：一个码组中的监督码元监督的信息段的个数N 卷

13、积码记作(n, k, N),31,11.7.1 卷积码的基本原理 编码器原理方框图,32,例： (n, k, N) = (3, 1, 3)卷积码编码器 方框图 设输入信息比特序列是bi-2 bi-1 bi bi+1，输入bi与输出比特ci di ei关系如下：,33,虚线示出了信息位bi的监督位和各信息位之间的约束关系，约束长度nN等于9。,34,11.7.2 卷积码的代数表述 卷积码也是一种线性码。 一个线性码完全由一个监督矩阵H或生成矩阵G所确定。 监督矩阵H 设上图中在第1个信息位b1进入编码器之前，各级移存器都处于“0”状态。 监督位di、ei和信息位bi之间的关系可表示为：,35,左

14、式可以改写为,36,与11.5节公式H AT = 0T对比，可以看出监督矩阵,37,卷积码的H是一个有头无尾的半无穷矩阵。 监督矩阵的每3列的结构是相同的，只是后3列比前3列向下移了 两行。 自第7行起，每两行的左端比上两行多了3个“0”。,38,截短监督矩阵的结构形式如下图： H1的最左边是n列(n-k)N行的一个子矩阵，且向右的每n列均相对于前n列降低(n - k)行。 截短监督矩阵一旦确定，卷积码的监督矩阵就可完全确定。,39,此例中码的截短监督矩阵可以写成如下形式： 式中 2阶单位方阵； Pi 2 1阶矩阵，i = 1, 2, 3； O2 2阶全零方阵。,40,一般说来，卷积码的截短监

15、督矩阵具有如下形式： In-k (n k)阶单位方阵； Pi (n k) k阶矩阵； On-k (n k)阶全零方阵。 H1的末行称为基本监督矩阵h h = PN On-k PN-1 On-k PN-2 On-k P1 In-k h是卷积码的一个最重要的矩阵，因为只要给定了h，可完整的监督阵H 就确定了。,41,生成矩阵G 上例中的输出码元序列可以写成 b1 d1 e1 b2 d2 e2 b3 d3 e3 b4 d4 e4 = b1 b1 b1 b2 b2 (b2 + b1) b3 (b3 + b1) (b3 + b2 + b1) b4 (b4 + b2) (b4 + b3 + b2) ,42,此码的生成矩阵G即为上式最右矩阵：,43,截短生成矩阵：类似地，也有截短生成矩阵 式中 I1 一阶单位方阵； Qi 1 2阶矩阵。 与H1矩阵比较可见，Qi是矩阵Pi的转置： Qi = PiT (i = 1, 2, ) 截短生成矩阵具有如下形式：,44,式中 Ik k阶单位方阵； Qi k (n k)阶矩阵； Ok k阶全零方阵。 基本生成矩阵：上式中矩阵第一行 g Ik Q1 Ok Q2 Ok Q3Ok QN 如果基本生成矩阵g已经给定，则可以从已知的信息位得到整个编码序列。,45,11.7.3 卷积码的解码 分类： 代数