ThemeGallery PowerTemplate

Size: px

Start display at page:

Download "ThemeGallery PowerTemplate"

杂疋曹
5 years ago
Views:

1 第 7 章信道编码 1

2 本章内容绪论线性分组码循环码卷积码 Turbo 码 2

3 7.1 引言在设计数字通信系统时, 首先应从合理地选择调制解调方法合适的发射功率等方面考虑, 若仍不能满足系统误码率要求, 则要考虑采用本章所讲的差错控制编码措施纠错码, 是当消息经过有噪信道传输或要恢复存储的数据时用来纠错的用来传输消息的物理介质叫做信道( 如电话线卫星连接用于移动通信的无线信道等 ) 因为纠错码试图克服信道中噪声造成的损害, 因此其编码过程又称为信道编码, 它是提高数字信号传输可靠性的有效方法之一信源信道编码器调制器信道噪声信宿信道译码器解调器差错控制编码编码调制 3

4 信道编码可分为两个研究领域 : 波形编码 ( 信号设计 ) 和结构化序列 ( 结构冗余 ) 波形编码是将波形转变为更好的波形以减少错误判决 ; 结构化序列是将数据序列转变为更好的序列, 通过冗余比特来检测和纠正传输中的错误波形编码 : 最常见的是正交编码和双正交编码, 通过编码使编码集合中信号间的相关度最小 ( 即信号间的距离最大 ) 如对极信号正交信号正交编码常使用 Hadamard 矩阵, 即 1bit 数据集可用两个数字的正交码字进行变换,2bit 数据集可使用 4 个数字的正交码字进行变换, 依此类推数据集正交码字集数据集正交码字集 1 0 H 1 = H k = H k-1 H k H 2 = = H 1 H 1 H 1 H 1 H k-1 H k-1 4

5 双正交码 : 具有 M 个信号的双正交信号集可由 M/2 个信号的正交信号集获取 B M = H M-1 H M-1 例如, 一个 3bit 数据集可以转变为如下的双正交码字集数据集正交码字集 B 3 =

6 常用的差错控制方式有三种 : 检错重发方式, 又称为自动重发请求 (ARQ), 发送端发送能够发现错误的码, 由接收端判断接收中有无错误发生如果发现错误, 则通过反向信道把这一判决结果反馈给发送端, 然后发送端再把错误的信息重发一次能够发现错误的码发送端接收端应答信号前向纠错方式 (FEC): 发送端发送能够纠正错误的码, 接收端收到后自动纠正传输中的错误, 特点是单向传输发送端可以纠正错误的码接收端 6

7 混合纠错方式 (HEC): 发送端发送既能自动纠错, 又能检测的码接收端收到码流后, 检查差错情况, 如果错误在纠错能力范围以内, 则自动纠错, 如果超过了纠错能力, 但能检测出来, 则经过反馈信道请求发送端重发发送端能够发现和纠正错误的码应答信号接收端 7

8 7.1.1 差错控制编码理论的起源和发展 1948 年,Bell 实验室的 C.E.Shannon 发表的通信的数学理论, 是关于现代信息理论的奠基性论文, 它的发表标志着信息与编码理论这一学科的创立 Shannon 在该文中指出, 任何一个通信信道都有确定的信道容量 C, 如果通信系统所要求的传输速率 R 小于 C, 则存在一种编码方法, 当码长 n 充分大并应用最大似然译码 ( MLD, Maximum Likelihood Decoding) 时, 信息的错误概率可以达到任意小从 Shannon 信道编码定理可知, 随着分组码的码长 n 或卷积码的约束长度 N 的增加, 系统可以取得更好的性能 ( 即更大的保护能力或编码增益 ), 而译码的最优算法是 MLD,MLD 算法的复杂性随 n 或 N 的增加呈指数增加, 因此当 n 或 N 较大时,MLD 在物理上是不可实现的因此, 构造物理可实现编码方案及寻找有效译码算法一直是信道编码理论与技术研究的中心任务 Shannon 指出了可以通过差错控制码在信息传输速率不大于信道容量的前提下实现可靠通信, 但却没有给出具体实现差错控制编码的方法 8

9 20 世纪 40 年代,R.Hamming 和 M.Golay 提出了第一个实用的差错控制编码方案, 使编码理论这个应用数学分支的发展得到了极大的推动通常认为是 R.Hamming 提出了第一个差错控制码当时他作为一个数学家受雇于贝尔实验室, 主要从事弹性理论的研究他发现计算机经常在计算过程中出现错误, 而一旦有错误发生, 程序就会停止运行这个问题促使他编制了使计算机具有检测错误能力的程序, 通过对输入数据编码, 使计算机能够纠正这些错误并继续运行 Hamming 所采用的方法就是将输入数据每 4 个比特分为一组, 然后通过计算这些信息比特的线性组合来得到 3 个校验比特, 然后将得到的 7 个比特送入计算机计算机按照一定的原则读取这些码字, 通过采用一定的算法, 不仅能够检测到是否有错误发生, 同时还可以找到发生单个比特错误的比特的位置, 该码可以纠正 7 个比特中所发生的单个比特错误这个编码方法就是分组码的基本思想,Hamming 提出的编码方案后来被命名为汉明码 9

10 虽然汉明码的思想是比较先进的, 但是它也存在许多难以接受的缺点首先, 汉明码的编码效率比较低, 它每 4 个比特编码就需要 3 个比特的冗余校验比特另外, 在一个码组中只能纠正单个的比特错误 M.Golay 研究了汉明码的这些缺点, 并提出了两个以他自己的名字命名的高性能码字 : 一个是二元 Golay 码, 在这个码字中 Golay 将信息比特每 12 个分为一组, 编码生成 11 个冗余校验比特相应的译码算法可以纠正 3 个错误另外一个是三元 Golay 码, 它的操作对象是三元而非二元数字三元 Golay 码将每 6 个三元符号分为一组, 编码生成 5 个冗余校验三元符号这样由 11 个三元符号组成的三元 Golay 码码字可以纠正 2 个错误 10

11 汉明码和 Golay 码的基本原理相同它们都是将 q 元符号按每 k 个分为一组. 然后通过编码得到 n-k 个 q 元符号作为冗余校验符号, 最后由校验符号和信息符号组成有 n 个 q 元符号的码字符号得到的码字可以纠正 t 个错误, 编码码率为为 k/n 这种类型的码字称为分组码, 一般记为 (q,n,k,t) 码, 二元分组码可以简记为 (n,k,t) 码或者 (n,k) 码汉明码和 Golay 码都是线性的, 任何两个码字经过模 q 的加操作之后, 得到的码字仍旧是码集合中的一个码字在 Golay 码提出之后最主要的一类分组码就是 Reed-Muller 码它是 Muller 在 1954 年提出的, 此后 Reed 在 Muller 提出的分组码的基础上得到了一种新的分组码, 称为 Reed-Muller 码, 简记为 RM 码在 1969 年到 1977 年之间,RM 码在火星探测方面得到了极为广泛的应用即使在今天,RM 码也具有很大的研究价值, 其快速的译码算法非常适合于光纤通信系统 11

12 在 RM 码提出之后人们又提出了循环码的概念循环码实际上也是一类分组码, 但它的码字具有循环移位特性, 即码字比特经过循环移位后仍然是码字集合中的码字这种循环结构使码字的设计范围大大增加, 同时大大简化了编译码结构循环码的另一个特点就是它可以用一个幂次为 n-k 的多项式来表示, 这个多项式记为 g(d), 称为生成多项式, 其中 D 为延迟算子循环码也称为循环冗余校验 (CRC,Cyclic Redundancy Check) 码, 并且可以用 Meggitt 译码器来实现译码由于 Meggitt 译码器的译码复杂性随着纠错能力 t 的增加而呈指数形式的增加, 因此通常 CRC 码用于纠正只有单个错误的应用情况, 常用做检错码而非纠错码循环码的一个非常重要的子集就是分别由 Hocquenghem 在 1959 年 Bose 和 Ray-Chaudhuri 研究组在 1960 年几乎同时提出的 BCH 码 (BCH,Bose Chaudhuri Hocquenghem),BCH 码的码字长度为 n=q m -1, 其中 m 为一个整数二元 BCH 码 (q=2) 的纠错能力限为 t<(2 m -1)/ 年,Reed 和 Solomon 将 BCH 码扩展到非二元 ( q>2 ) 的情况, 得到了 RS( Reed- Solomon) 码 1967 年,Berlekamp 给出了一个非常有效的译码算法后, RS 码得到了广泛的应用此后,RS 码在 CD 播放器 DVD 播放器中得到了很好的应用 12

13 虽然分组码在理论分析和数学描述方面已经非常成熟, 并且在实际的通信系统中也已经得到了广泛的应用, 但分组码固有的缺陷大大限制了它的进一步发展首先, 由于分组码是面向数据块的, 因此, 在译码过程中必须等待整个码字全部接收到之后才能开始进行译码在数据块长度较大时, 引入的系统延时是非常大的分组码的第二个缺陷是它要求精确的帧同步, 即需要对接收码字或帧的起始符号时间和相位精确同步另外, 大多数基于代数的分组码的译码算法都是硬判决算法, 而不是对解调器输出未量化信息的软译码, 从而造成了一定程度的增益损失 13

14 分组码所存在的固有缺点可以通过采用其他的编码方法来改善, 这种编码方法就是卷积码, 是 Elias 等人在 1955 年提出的卷积码与分组码的不同在于分组码在编码之前先将信息序列按照一定的数据块长度分组, 然后对每一组信息进行独立编码, 即对于 (n,k) 分组码来说, 码字中的 n-k 个检验元仅与本码字的 k 个信息元有关, 而与其他码字的信息元无关同样, 在分组码的译码时也是针对每一个接收码字进行独立译码的, 在一个接收码字内部提取译码相关信息, 与其他码字无关而在卷积编码中则充分利用了各个信息块之间的相关性通常卷积码记为 (n,k,n) 码卷积码的编码过程是连续进行的, 依次连续将每 k 个信息元输入编码器, 得到 n 个码元, 得到的码元中的检验元不仅与本码的信息元有关, 还与以前时刻输入到编码器的信息元 ( 反映在编码寄存器的内容上 ) 有关同样, 在卷积码的译码过程中, 不仅要从本码中提取译码信息, 还要充分利用以前和以后时刻收到的码组. 从这些码组中提取译码相关信息, 而且译码也是可以连续进行的, 这样可以保证卷积码的译码延时相对比较小通常, 在系统条件相同的条件下, 在达到相同译码性能时, 卷积码的信息块长度和码字长度都要比分组码的信息块长度和码字长度小, 相应译码复杂性也小一些 14

15 卷积码的译码通常有如下几个比较流行的译码算法 : 由 Wozencraft 和 Reiffen 在 1961 年提出 Fano 和 Jelinek 分别在 1963 年和 1969 年进行改进了的序贯译码算法该算法是基于码字树图结构的一种次最优概率译码算法由 Massey 在 1963 年提出的门限译码算法这个算法利用码字的代数结构进行代数译码由 Viterbi 在 1967 年提出的 Viterbi 算法该算法是基于码字格图结构的一种最大似然译码算法, 是一种最优译码算法在 Viterbi 译码算法提出之后, 卷积码在通信系统中得到了极为广泛的应用如 GSM 3G 商业卫星通信系统等 15

16 在信道编码定理的指引下, 人们一直致力于寻找能满足现代通信业务要求, 结构简单性能优越的好码, 并在分组码卷积码等基本编码方法和最大似然译码算法的基础上提出了许多构造好码及简化译码复杂性的方法, 提出了乘积码代数几何码低密度校验码 (LDPC,Low Density Parity Check) 分组- 卷积级联码等编码方法和逐组最佳译码软判决译码等译码方法以及编码与调制相结合的网格编码调制 (TCM,Trellis Coded Modulation) 技术其中对纠错码发展贡献比较大的有级联码软判决译码和 TCM 技术等 16

17 虽然软判决译码级联码和编码调制技术都对信道码的设计和发展产生了重大影响, 但是其增益与 Shannon 理论极限始终都存在 2~3dB 的差距在 1993 年于瑞士日内瓦召开的国际通信会议 (1CC'93) 上, 两位任教于法国不列颠通信大学的教授 C.Berrou A.Glavieux 和他们的缅甸籍博士生 P.Thitimajshima 首次提出了一种新型信道编码方案 Turbo 码, 由于它很好地应用了 Shannon 信道编码定理中的随机性编译码条件, 从而获得了几乎接近 Shannon 理论极限的译码性能仿真结果表明, 在采用长度为的随机交织器并译码迭代 18 次情况下, 在信噪比 Eb/N0>=0.7dB 并采用二元相移键控 (BPSK) 调制时, 码率为 1/2 的 Turbo 码在加性高斯白噪声信道上的误比特率 (BER)<=10-5, 达到了与 Shannon 极限仅相差 0.7dB 的优异性能 (1/2 码率的 Shannon 极限是 0dB) 17

18 7.1.2 差错控制编码的基本原理在信息码元序列中附加一些监督码元, 在两者之间建立某种校验关系, 当这种校验关系因传输错误而受到破坏时, 可以被发现和纠正不同的编码方法, 有不同的检错和纠错能力一般来说, 付出的代价越大, 检 ( 纠 ) 错的能力就越强这里所说的代价, 指增加的监督码元的多少例如, 若编码序列中, 平均每两个信息码元就有一个监督码元, 则这种编码的多余度为 1/3, 或者说, 这种编码的编码速率为 2/3, 可见, 差错控制编码是以降低信息传输速率来换取信息传递的可靠性提高 18

19 7.1.3 差错控制编码的分类根据信息码元和监督码元的函数关系, 可分为线性码和非线性码根据信息码元和监督码元之间的约束方式, 可分为分组码和卷积码在分组码中, 监督码元仅与本码组的信息码元有关, 而在卷积码中, 监督码元不仅与本组的信息码元有关, 还与前面若干组的信息码元有关 19

20 7.1.4 误差控制编码的目标用可以纠正的错误个数来衡量的纠错能力 ; 快速有效地对消息进行编码 ; 快速有效地对消息进行解码 ; 矛盾! 折衷! 单位时间内所能传输的信息 bit 数尽量大 ( 即尽量减少冗余度 ) 20

21 使用纠错编码的原因权衡 1: 差错性能和带宽 ; 权衡 2: 功率与带宽 ; 权衡 3: 数据速率与带宽 ; 权衡 4: 容量与带宽 ; 21

22 7.2 几种常用的简单检错码奇偶监督码就是在原信息码元后面附加一个监督码元, 使得码组中的 1 的个数为奇数或偶数接收端译码时, 对各码元进行模 2 加运算, 其结果为 0 或 1, 如果传输过程中任何一位发生错误, 就会使校验条件不满足, 但当有偶数个错误发生时, 这种编码就无能为力了行列监督码 ( 水平奇偶监督码 ) 对行和列都实施奇偶监督恒比码 : 即码字中 1 和 0 的数目保持恒定比例的码 22

23 7.3 基本名词定义在信道编码中, 非零码元的数目称为汉明重量 (Hamming Weight), 也称为码重记为 w(c) 两个等长码组之间相应位取值不同的数目称为这两个码组的汉明距离 ( Hamming Distance), 简称码距记为 d(c 1,c 2 ), 可得 d(c 1,c 2 )=w(c 1 -c 2 ) 例 : 考虑有两个码字 {0100,1111} 的码 C, 则 w(0100)=1, w(1111)=4, 这两个码字间的汉明距离为 3 通过观察, 有 w( )=w(1011)=3 =d(0100,1111) 码组集中任意两个码字之间距离的最小值称为最小码距 d min, 它关系着这种编码的检错和纠错能力为检测出 e 个错码, d min e+1 为纠正 t 个错码, d min 2t+1 为检测出 e 个错码, 同时纠正 t 个错码,d min e+t+1 且 e t 23

24 线性码具有下述性质两个属于该码的码字的和仍是一个属于该码的码字 ; 全零码字总是一个有效码字 ; 一个线性码的两个码字之间的最小距离等于任何非零码字的最小汉明重量例 : 码 C={0000,1010,0101,1111} 是一个分组长度为 4 的线性分组码分组码一般以 (n,k) 表示,k 是信息码元数目,n 是码组总码元数, 又称为码长, 因此,n-k=r 就是监督码元的数目信道编码可表示为由编码前的信息码元空间 U k 到编码后的码字空间 C n 的一个映射 f, 即 f:u k C n, 编码速率为 R=k/n 在二进制情况下, 共有 2 k 个不同的信息组, 相应地有 2 k 个不同的码字, 称为许用码组, 其余 2 n -2 k 个就称为禁用码组 24

25 7.4 (7,4) 线性分组码举例基本概念分组码 : 将信息码分组, 为每组信码附加若干监督码的编码, 称为分组码线性分组码 : 每个监督码元都是码组中某些信息码元的线性相加得到的下面以 (7,4) 分组码进行说明其码字 A =[a 6 a 5 a 4 a 3 a 2 a 1 a 0 ] 信息码元监督码元 a 2 =a 6 +a 5 +a 4 a 1 =a 6 +a 5 +a 3 a 0 =a 6 +a 4 +a 3 据此, 可得到 16 个码字,d min =3, 能检测出 2 个错误, 纠正 1 个错误 25

26 7.4.2 监督矩阵 H 和生成矩阵 G 将上面的方程重写为 : 1 a6 + 1 a5 + 1 a4 + 0 a3 + 1 a2 + 0 a1+ 0 a0 = 0 1 a6 + 1 a5 + 0 a4 + 1 a3 + 0 a a0 = 0 1 a6 + 0 a5 + 1 a4 + 1 a3 + 0 a2 + 0 a1+ 1 a0 = T [ ] a a a a a a a = 这就是监督矩阵!! 26

27 H 矩阵是一个 r n 的矩阵, 它的每行之间是线性无关的将 H 矩阵分为两部分 : 所以,P 矩阵是一个 r k 阶的矩阵,I r 是 r 阶的单位阵可写为 H=[P I r ] 形式的矩阵称为典型监督矩阵如果监督矩阵 H 不是一个典型矩阵, 可以对它进行初等行变换, 化为典型监督矩阵 HA T =0 T H = = [ P I r ] 这个式子说明 H 矩阵与码字的转置乘积为零, 据此可作为接收码字 A 是否出错的依据 27

28 若把监督方程补充为下列方程 : a6 = a6 a5 = a5 a4 = a4 a3 = a3 a = a + a + a a = a + a + a a = a + a + a 定义 : 则有 : G = a a a6 a a5 a3 = a 4 a a3 a a T [ ] [ ] T T A = G a6 a5 a4 a3 A= a6 a5 a4 a3 G 因此, 由信息码元和生成矩阵 G 就可产生全部码字 28

29 观察 G, 可得 G=[I k Q] 其中 : Q= = P T 因此, 可写为上式形式的 G 矩阵就称为典型生成矩阵 a6 c6 a5 c5 a4 c4 (7,4) 线性分组码编码器 a3 c3 c2 c1 c0 29

30 例 : 已知 (6,3) 码的生成矩阵为求 (1) 编码码组和各个码组的码重 ; (2) 最小码距 d min 和该码的差错控制能力 ; 解 : (1) 由 3 位码组成的信息码组矩阵为 : G = D = A= DG = 码重

31 (2) 最小码距 d min =3, 该码能检错 2 位, 或纠错 1 位, 或纠错 1 位同时检错 1 位的能力 a5 c5 (6,3) 线性分组码编码器 G = a4 a c4 c3 c2 c1 c0 31

32 7.4.3 伴随式 ( 校正子 )S 码组在传输中可能由于干扰而出错, 例如发送码组为 A, 接收到的码组却是 B, 它们都是 n 位码的行矢量, 我们就定义 E=B-A 为错码矩阵其中 E=[e n-1 e n-2 e 1 e 0 ], 因此有 B=A+E e i 0 = 1 定义 S=B H T 为伴随式, 则 S = (A+E) H T = A H T + E H T = E H T 如果传输无错,S 矩阵为零矩阵 ; 如果有错误,S 就是一个非零矢量, 就能从伴随式确定错误图样, 然后从接收到的码字中减去错误图样, 即 A=B-E, 注意这里的加减都是模 2 加运算, 就可得到正确的码组了 b b i i = ai a i 32

33 应该注意的是, 上式的解答不是唯一的我们知道,B 是一个 1 n 的矩阵,H T 是一个 n r 的矩阵, 所以 S 是一个 1 r 的矩阵, 因此它有 2 r 种可能而错误图样 E 的个数远大于 2 r, 因此, 必然有多个错误图样对应同一个校正子 S 而错误图样等于 B-A, 即与接收到的码组是一一对应的, 为了选择正确的结果, 要使用最大似然比准则, 选择与 B 最相似的 A 从几何意义上来说, 就是选择与 B 距离最小的码组, 也就是差错矢量 E 中 1 码最少的矢量 33

34 对于 (7,4) 码来说, 它的伴随式与错误图样的对应关系如下表所示 : 由表可以看出, 伴随式 S 的 2 r 种形式分别代表 A 码无错和 2 r -1 种有错的图样 34

例 : 仍以上面的例题, 已知生成矩阵 G 如下, 列出 S 与 E 的对照表当收到码组 B=[1 1 1 0 1 1] 时, 解出对应的信息码组 D 解 : 已知生成矩阵为 : 1 0 0 1 0 1 G = 0 1 0 0 1 1 0 0 1 1 1 0 I k Q T H

35 例 : 仍以上面的例题, 已知生成矩阵 G 如下, 列出 S 与 E 的对照表当收到码组 B=[ ] 时, 解出对应的信息码组 D 解 : 已知生成矩阵为 : G = I k Q T H = [ Q I r ] = S 有 2 3 种形式, 相应的码重最小的 E 矢量有 8 种 S 与 E 的对照表如下 : T H =

36 (6,3) 码具有纠错 1 位的能力,S=111 时对应双错情况, 即超出了该码的纠错能力范围 S T = BH = [ ] = [0 1 1] 查表我们可知,E 矢量为 : E=[ ] 这样我们就可得到正确的码组 A, 即 A=B-E=B+E=[ ] 所以, 信息码组为 :D=[1 0 1] 36

37 伴随式译码器伴随式译码步骤归纳如下 : 1. 原始发送矢量为 A; 2. 计算接收矢量 B 的伴随式 S=B H T ; 3. 由伴随式 S 决定相对应的错误图样 E; 4. 将 B 译成 Â=B+E B 接收矢量缓存器 b0 b1 bn-1 伴随式计算电路 s0 s1 sn-k-1 错误图样检测电路 b0 e0 b1 e1 bn-1 en-1 â0 â aˆ 1 n 1 37

38 例 :(7,4) 线性分组码的译码电路前面已经给出 (7,4) 线性分组码的生成矩阵 G 和监督矩阵 H 为 G = H T = 假设消息序列为 (0010), 则经过编码后的序列为 A=( ), 接收后为 B=( ), 如何通过译码电路纠正错误! 38

39 根据公式 S=BH T, 其中 S=[s 2,s 1,s 0 ], B=[b 6,b 5,b 4,b 3,b 2,b 1,b 0 ], 可得以下关系 : s 2 = b 6 +b 5 + b 4 + b 2 s 1 = b 6 +b 5 + b 3 + b 1 s 0 = b 6 +b 4 + b 3 + b 0 根据公式 S=EH T, 其中 E=[e 6,e 5,e 4,e 3,e 2,e 1,e 0 ], 可得以下关系 : e 6 = s 2 + s 1 + s 0 ; e 5 = s 2 + s 1 e 4 = s 2 + s 0 ; e 3 = s 1 + s 0 e 2 = s 2 ; e 1 = s 1 ; e 0 = s 0 39

40 b6 b5 b4 b3 b2 b1 b 校正子 S 与错误图样 E 对照表 S2=1 S1=1 S0=1 e6 =1 b6 =1 a6 =0 e5 =0 b5 =0 a5 =0 e4 =0 b4 =1 a4 =1 e3 =0 b3 =0 a3 =0 e2 =0 b2 =1 a2 =1 e1 =0 b1 =0 a1 =0 e0 =0 b0 =1 a0 =1 纠正了错误, 输出变为了 !! 40

41 7.5 线性分组码生成矩阵 G 和校验矩阵 H 设 C 表示一个 (n,k) 线性分组码, 生成矩阵 G 是一个 k n 的矩阵, 表示为 G 任何一个码字 v0 v0,0 v0,1 v0, n 1 v v v v v v v v 1 1,0 1,1 1, n 1 = = v k 1 k 1,0 k 1,1 k 1, n 1 v C 可表示为 = uv + uv + + u v k 1 k 1 41

42 其中 ū=(u 0,u 1,,u k-1 ) 表示信息向量,u i {0,1}, 1 i<k 这样就有 : v = ug 生成矩阵 G 和校验矩阵 H 的关系满足 GH T =0, 从而有这是线性分组码解码的重要基础! vh T = 0 对系统分组码来说, 其生成矩阵又可写为 G sys =( I k Q ) 的形式其中 q0,0 q0,1 q0, n k 1 q1,0 q1,1 q1, n k 1 Q = qk 1,0 qk 1,1 q k 1, n k 1 由于 GH T =0, 校验矩阵的系统形式可写为 H sys =(Q T I n-k ) 42

43 7.6 汉明码 (Hamming) 为了指示所有单错位置和无错情况, 线性分组码的码长 n 信息码元长度 k 和监督码元长度 r 之间满足不等式 :2 r n+1; 取等号时, 就是汉明码汉明码仅能纠正单个错误, 是 Hamming 于 1949 年提出的此时,n k r 的关系为 :n = 2 r 1,k = n r = 2 r r 1 其中 r 为 2 的正整数由 2 r =n+1, 我们可知,r=n-k=log 2 (n+1), n=k+log 2 (n+1) 上式在给定信息码组长度 k 后, 可以求出能纠正单错的码组最小长度 n, 而且 d min =3 这样我们就可知道,k=1/4/11 时,n=3/7/15 构成 (3,1) (7,4) (15,11) 码汉明码的编码效率为 : 当 r 很大时,η 趋于 1 r k 2 r 1 r η = = = r 1 r n

44 7.7 循环码引言生成多项式 g(d) 及生成矩阵 G 监督多项式 h(d) 和监督矩阵 H 循环码的编码和译码 44

45 7.7.1 引言在处理线性分组码时, 在分组码的结构上加入了线性限制的条件, 这些结构上的性质可以帮助我们寻找好的能够快速简易地编码和译码的线性分组码 ; 本章, 我们将研究线性分组码中的一个重要子类 : 循环码, 该码在结构上有另外的限制, 即一个码字任意循环移位的结果仍是一个有效码字循环码是 1957 年由 Prange 首先提出的, 其特点是 : (1) 可以用反馈移位寄存器很容易实现编码和伴随式计算 ; (2) 由于循环码有很多固有的代数结构, 从而可以找到各种简单使用的译码方法 45

46 多项式的运算加法 :f 1 (D)=D 3 +D+1, f 2 (D)=D+1 则 f 1 (D)+f 2 (D)=D 3 乘法 : f 1 (D)* f 2 (D)=D 4 +D 2 +D+D 3 +D+1 = D 4 + D 3 +D 2 +1 除法 : f 1 (D)/ f 2 (D) D 2 +D D+1 D 3 + D+1 D 3 +D 2 D 2 +D+1 D 2 +D 1 46

47 一个 (n,k) 线性码具有以下的属性, 则称为循环码 (cyclic code): 如果 n 元组 c={c 0,c 1,,c n-1 } 是子空间 S 的一个码字, 则经过循环移位的 c (1) ={c n-1, c 0,, c n-2 } 也同样是 S 中的一个码字, 经过 j 次循环移位后的 c (j) ={c n-j,c n-j+1,,c n-1,c 0,c 1,,c n-j-1 } 也是 S 中的一个码字码字 c={c n-1 c 1,c 0 } 的各个分量可以看作是多项式 c(d) 的系数, 即 c(d)= c n-1 D n c 1 D + c 0 每一项的存在或不存在对应了 n 元组中相应的位置为 1 或 0, 如果 c n-1 非 0, 那么多项式的阶数为 n-1 47

48 如 (7,3) 循环码的全部码字为 : 为了便于计算, 常用码多项式表示码字, 如 (n,k) 循环码, 其多项式表示为 :A(D)=a n-1 D n-1 +a n-2 D n-2 + +a 1 D+a 0 如第 2 号码字可用多项式表示为 :A 2 (D)=D 5 +D 2 +D+1 48

49 7.7.2 生成多项式 g(d) 及生成矩阵 G 如果一种码的所有码多项式都是多项式 g(d) 的倍式, 则称 g(d) 为该码的生成多项式在循环码中, 次数最低的多项式 (0 除外 ) 就是生成多项式 g(d), 其他码多项式都是其倍数且该 g(d) 的阶数为 r = n k, 常数项为 1, 是 D n +1 的一个因式为了寻求生成多项式, 必须对 D n +1 进行因式分解以 D 7 +1 为例 : D 7 +1=(D+1)(D 3 +D+1)(D 3 +D 2 +1) (n,k) g(d) (7,6) D+1 (7,4) D 3 +D+1 或 D 3 +D 2 +1 (7,3) (D+1)(D 3 +D+1) 或 (D+1)(D 3 +D 2 +1) (7,1) (D 3 +D+1)(D 3 +D 2 +1) 49

50 循环码的生成矩阵多项式为 : GD ( ) k 1 D gd ( ) k 2 D gd ( ) = Dg( D) gd ( ) 然后将系数提出就得到生成矩阵 G 50

51 例 : 已知 (7,4) 码的生成多项式 g(d)=d 3 +D 2 +1, 求生成矩阵解 :k=4 k 1 D gd ( ) D D D k 2 D gd ( ) D + D + D GD ( ) = = 4 3 D + D + D Dg( D) 3 2 gd ( ) D + D + 1 这样我们就可直接得到生成矩阵 G 为 : G =

52 由 A=MG, 其中 M=[m k-1 m k-2 m 1 m 0 ] 表示输入信息码元序列, 我们可求出编码后的输出码组序列, 但这样得到的循环码不是一个系统码所谓系统码, 指的是码组 A 的左边 k 位与 M 中的 k 个元素相同, 而后面 n k 位是 M 中元素的线性组合, 表示监督码元为了得到系统码, 就要求 G 矩阵的左边是一个 k 阶的单位阵, 即是一个典型生成矩阵 G = [I k Q] 形式这样的系统码用多项式表示即为 : A(D)=D n-k M(D)+r(D) 式中 M(D) 是不大于 k-1 次多项式,D n-k M(D) 是不大于 n-1 次多项式, r(d) 是不大于 r-1 次多项式, 称为监督码多项式, 它等于 D n-k M(D) 除以 g(d) 得到的余式, 表示为 r(d) = D n-k M(D) mod g(d) 或 r( D) n k D M( D) = rem gd ( ) 52

53 由于典型生成矩阵 G = [I k Q] 形式, 与单位矩阵 I k 每行对应的信息多项式为 : D n-k m i (D)=D n-k D k-i =D n-i,i=1,2,,k r i (D) = D n-i mod g(d) 由此得到生成矩阵中每行的码生成多项式为 : C i (D) = D n-i + r i (D), i = 1,2,,k 这样系统循环码生成矩阵多项式的一般表示式为 : GD ( ) n 1 C1 ( D) D + r1 ( D) n 2 C2( D) D + r2 ( D) = = C ( ) n k k D D + rk ( D) 53

54 例 7.6: 我们再对前面的例题进行求解, 已知 g(d)=d 3 +D 2 +1, 求系统循环码的生成矩阵解 :r 1 (D)=D 6 mod g(d) = D 2 +D r 2 (D)=D 5 mod g(d) = D+1 r 3 (D)=D 4 mod g(d) = D 2 +D+1 r 4 (D)=D 3 mod g(d) = D 2 +1 所以, 我们可写出生成矩阵多项式为 : 生成矩阵 G 可写为 : G = = [ Ik Q] D + D + D 5 D + D+ 1 GD ( ) = 4 2 D + D + D D + D + 1 其实这个矩阵我们也可以通过初等变换前面的生成矩阵得到 54

55 第二行加到第一行第三行加到第一行第二行第四行加到第二行第三行 55

56 7.7.3 监督多项式 h(d) 和监督矩阵 H 由于 GH T =0, 对循环码相应的有 g(d)h(d) 0,mod(D n +1) 监督矩阵多项式可写为 : n D + 1 k k 1 h( D) = = D + hk 1D hd gd ( ) 其中系数不同!! n k 1 D h ( D) H( D) = D h ( D) h ( D) k h ( D) = D + hd h D+ 1 k 1 1 k 1 56

57 例 :(7,3) 循环码的生成多项式为 g(d)=d 4 +D 3 +D 2 +1, 求其监督矩阵解 : 7 D + 1 hd = = D + D + gd ( ) 3 2 ( ) 1 h D D D 3 ( ) = H( D) D ( D + D+ 1) D + D + D D ( D + D+ 1) D + D + D = = D ( D + D+ 1) D + D + D 3 3 ( D + D+ 1) D + D+ 1 H =

58 7.7.4 循环码的编码和译码我们知道, 系统码用多项式表示即为 : A(D)=D n-k M(D)+r(D), 编码的关键是求出 r(d), 而 r(d) 则要通过 r(d)=rem[d n-k M(D)/g(D)] 来求解例 : 已知 (7,4) 系统循环码的生成多项式为 g(d)=d 3 +D 2 +1, 若信息码为 1001, 求编码后的循环码组解 : 信息码多项式为 M(D) = D 3 + 1, 3 3 D ( D + 1) r( D) = rem = D D + D + 1 AD D D D D D D ( ) = ( + 1) = 其对应的码组为

59 多项式除法可以用带反馈的线性移位寄存器来实现 g(d) 与移位寄存器的反馈逻辑相对应如假设 g(d)=d 6 +D 5 +D 4 +D 3 +1, 则采用内接异或门的电路如下图所示, g(d)= D + D 5 + D 6 + D 输入输出以 ( 7, 4 ) 系统循环码为例, 已知它的生成多项式为 g(d)=d 3 +D 2 +1, 所对应的编码电路入下图所示与门 1 & 0 拍 ~3 拍 4 拍 ~6 拍 D D1 D2 3 输入信息 & 与门 2 或码字 59

60 与门 1 在 0 拍 ~3 拍接通, 其余时间断开 ; 与门 2 在 4 拍 ~6 拍接通, 其余时间断开用 3 级移位寄存器 D1 D2 和 D3 以及两个模 2 加法器实现除法电路, 反馈逻辑与 g(d) 相对应或门把信息码元和校验码元合路, 输出编码码组 A(D) 由于输入信息码组直接加到除法电路的高端, 相当于自动乘以 D 3 当信息码组 M=[ ] 时, 编码过程如下表所示在 0 拍时对移位寄存器状态清零节拍信息码元 D D D 输出编码

61 我们知道, 发送码组多项式 A(D) 是多项式 g(d) 的倍式, 如果经过信道传输后发生错误, 接收码组多项式 B(D) 不再是 g(d) 的倍式, 可表示为 : BD ( ) SD ( ) = xd ( ) + gd ( ) gd ( ) 或写成 :S(D)= rem[b(d)/g(d)] 其中 S(D) 是 B(D) 除以 g(d) 后的余式, 是不大于 r-1 次的码组多项式, 称为伴随多项式或校正子多项式 61

62 接收码组多项式 B(D) 可表示为发送码组多项式与差错多项式之和, 即 :B(D) = A(D)+E(D) AD ( ) + ED ( ) ED ( ) S( D) = rem rem gd ( ) = gd ( ) 由 S(D) 就可进一步确定 E(D) 对于一个 S(D),E(D) 可能有多种形式由 S(D) 确定 E(D) 时同样使用最大似然比准则对最小码重的差错多项式 E(D), 由上式求出对应的伴随多项式 S(D), 将 E(D) 与 S(D) 的对应关系列成译码表当收到任一码组 B(D) 后, 利用 S(D)=rem[B(D)/g(D)] 求出 S(D), 对照译码表找到 E(D), 再用 B(D) = A(D)+E(D) 求 A(D), 即 A(D) = B(D) + E(D) 62

63 例 : 已知 (7,4) 系统循环码的生成多项式为 g(d)=d 3 +D 2 +1, 试构成译码表若接收码组 B = [ ], 求发送码组解 : 根据 S(D)=rem[B(D)/g(D)], 对码重为 1 的差错多项式 E(D), 求出相应的多项式 S(D), 将其对应结果列成译码表如下 : E(D) D 6 D 5 D 4 D 3 D 2 D 1 S(D) D 2 +D D+1 D 2 +D+1 D 2 +1 D 2 D 1 当接收码组无误时,E(D)=0, 则 S(D)=0 本题给出的接收码组为 :B = [ ], 接收码组多项式为 : B(D)=D 6 +D 2 +1 伴随多项式 S(D) 为 : 6 2 D + D + 1 S( D) = rem = D D + D + 1 查表得到 :E(D)=D 5 63

64 由 B(D) 和 E(D) 可得到译码码组多项式 : A(D)=B(D)+E(D)=D 6 +D 5 +D 2 +1 相应的码组为 :A=[ ] 由于是系统循环码, 所以信息码组为 : M=[ ] 其译码电路如下 : 输入校正子计算电路 1 2 n-k 错误图样识别器缓存器纠错后输出 64

65 由于循环码具有很强的检测能力, 因此常用于 CRC 校验, 目前已有四个国际标准 : CRC-12: g(d)=d 12 +D 11 +D 3 +D 2 +D+1 CRC-16: g(d)=d 16 +D 15 +D 2 +1 CRC-CCITT: g(d)=d 16 +D 12 +D 5 +1 CRC-32: g(d)=d 32 +D 26 +D 23 +D 22 +D 16 +D 12 +D 11 +D 10 +D 8 +D 7 +D 5 +D 4 +D 2 +D+1 65

66 作业 (P288~292)

PowerPoint 演示文稿

PowerPoint 演示文稿编码理论周武旸 wyzhou@ustc.edu.cn 636485 第一章绪论课程内容. 信道编码的历史及研究现状.2 简单编码方式回顾.2. 线性分组码.2.2 循环码第二章基础理论 2. 信道编码定理 2.2 硬判决与软判决 2.3 基本信道模型及其信道容量 2.4 MAP 与 ML 算法 2.5 因子图与和积算法第三章 BCH 码 2 第四章卷积码 4. 卷积码的编码 4.2 卷积码的结构特性