差错控制编码技术

差错控制编码技术第一页，共五十二页，编辑于2023年，星期六8.1差错控制编码的基本概念1.差错控制的工作方式按照噪声或干扰的变化规律，可把信道分为三类：随机信道、突发信道和混合信道。恒参高斯白噪声信道是典型的随机信道，其中差错的出现是随机的，而且错误之间是统计独立的。具有脉冲干扰的信道是典型的突发信道，错误是成串成群出现的，即在短时间内出现大量错误。第二页，共五十二页，编辑于2023年，星期六差错控制的基本工作方式有4种：前向纠错、检错重发、混合纠错和反馈校验。（1）前向纠错方式前向纠错方式记作FEC。发端发送能够纠正错误的码，收端收到信码后自动地纠正传输中的错误。其特点是单向传输，实时性好，但译码设备较复杂。（2）检错重发方式检错重发方式又称自动请求重传方式，记作ARQ。第三页，共五十二页，编辑于2023年，星期六（3）混合纠错方式 混合纠错方式记作HEC，是FEC和ARQ方式的结合。（4）信息反馈方式 信息反馈方式记作IF，信息反馈是收端将接收的消息原封不动地送回发端，由发端将反馈信息和原发送信息进行比较，发现错误进行重发，其优点是方法和设备简单，无需纠（检）错编译系统。第四页，共五十二页，编辑于2023年，星期六2.差错控制编码的分类 （1）按照差错控制编码的用途不同可分为检错码、纠错码和纠删码。 （2）按照信息码元和监督码元之间的函数关系可分为线性码和非线性码。 （3）按照对信息元处理方式的不同可分为分组码和卷积码。第五页，共五十二页，编辑于2023年，星期六（4）按照码组中信息码元在编码前后是否相同可分为系统码和非系统码。（5）按照纠（检）错误的类型可分为纠（检）随机错误码、纠（检）突发错误码和既能纠（检）随机错误同时又能纠（检）突发错误码。（6）按照每个码元的取值可分为二进码和多进码。第六页，共五十二页，编辑于2023年，星期六3.差错控制编码的基本原理 差错编码的基本思想是在被传输信息中增加一些冗余码，利用附加码元和信息码元之间的约束关系加以校验，以检测和纠正错误，增加冗余码的个数可增加纠检错能力。第七页，共五十二页，编辑于2023年，星期六（1）码长、码重、码距 编码码组的码元总位数称为码组的长度，简称码长。 码组中，“1”码元的数目称为码组的重量，简称码重。 两个等长码组之间对应位上码元不同的数目称为这两个码组的距离，简称码距。第八页，共五十二页，编辑于2023年，星期六（2）检错和纠错能力 ①检测e个随机错误，则要求最小码距d0≥e+1； ②纠正t个随机错误，则要求最小码距d0≥2t+1； ③纠正t个同时检测e（e＞t）个随机错误，则要求最小码距d0≥t+e+1。第九页，共五十二页，编辑于2023年，星期六（3）编码效率 用差错控制编码提高通信系统的的可靠性，是以降低有效性为代价换来的。定义编码效率R来衡量有效性：R=k/n其中，k是信息元的个数，n为码长。第十页，共五十二页，编辑于2023年，星期六4.常用的几种简单编码（1）奇偶监督码 奇偶监督码是在原信息码后面附加一个监督元，使得码组中“1”的个数是奇数或偶数，或者说，它是含一个监督元，码重为奇数或偶数的（n，n-1）系统分组码。奇偶监督码又分为奇监督码和偶监督码。第十一页，共五十二页，编辑于2023年，星期六（2）行列监督码 奇偶监督码不能发现偶数个错误。为了改善这种情况，引入行列监督码。这种码不仅对水平（行）方向的码元，而且对垂直（列）方向的码元实施奇偶监督。第十二页，共五十二页，编辑于2023年，星期六（3）恒比码 码字中1的数目与0的数目保持恒定比例的码称为恒比码。由于恒比码中，每个码组均含有相同数目的1和0，因此恒比码又称等重码，定1码。这种码在检测时，只要计算接收码元中1的个数是否与规定的相同，就可判断有无错误。第十三页，共五十二页，编辑于2023年，星期六（4）群计数码 群计数码是将信息码元分组后，计算每组码元中“1”的个数，然后将这个数目的二进制表示作为监督码元，一起送往发送端。第十四页，共五十二页，编辑于2023年，星期六8.2线性分组码1.线性分组码的定义和特点 线性分组码，是指信息码元与监督码元之间的关系可以用一组线性方程来表示的分组码，即在（n，k）分组码中，每一个监督码元都是码组中某些信息码元按模2和而得到的，线性分组码是一类重要的纠错码，应用很广。第十五页，共五十二页，编辑于2023年，星期六2.监督矩阵H和生成矩阵G（1）监督矩阵第十六页，共五十二页，编辑于2023年，星期六我们把H称为监督矩阵，或称一致校验矩阵，一旦H给定，信息位和监督位之间的关系也就确定了。H为r×n阶矩阵，H矩阵每行之间是彼此线性无关的。H矩阵可分成两部分，其中P为r×k阶矩阵，Ir为r×r阶单位阵。能写成H=［PIr］形式的矩阵称为典型监督矩阵。第十七页，共五十二页，编辑于2023年，星期六（2）生成矩阵第十八页，共五十二页，编辑于2023年，星期六 称为生成矩阵，由G和信息组就可以产生全部码字。G为k×n阶矩阵，各行也是线性无关的。生成矩阵也可以分为两部分：其中Q为k×r阶矩阵，Ik为k阶单位阵，可以写成式（8-12）形式的G矩阵，称为典型生成矩阵。非典型形式的矩阵经过运算也一定可以化为典型矩阵形式。第十九页，共五十二页，编辑于2023年，星期六（3）监督矩阵H和生成矩阵G之间的关系 由上可知，监督矩阵H和生成矩阵G之间有一一对应的关系。由于G的每一行都为码字，因此它必然满足式（8-7）HAT=0T即HGT=0T第二十页，共五十二页，编辑于2023年，星期六3.线性分组码的译码——伴随式（校正子）S 若某一码字为许用码组，则它必然满足式（8-7）。利用这一关系，在接收端将收到的码组和事先与发端约定好的监督矩阵相乘，看是否为零。若满足条件，则认为接收正确；反之，则认为传输过程中发生了错误，进而设法确定错误的数目和位置。第二十一页，共五十二页，编辑于2023年，星期六 令S=BHT，称为伴随式或校正子。S=BHT=（A+E）HT=EHT 由此可见，伴随式S与错误图样E之间有确定的线性变换关系，与发送码组A无关。接收端译码器的任务就是从伴随式确定错误图样，然后从接收到的码字中减去错误图样。第二十二页，共五十二页，编辑于2023年，星期六从以上分析可以得出线性分组码译码的基本步骤：①计算接收码组B的伴随式S；②根据S找出错误图样E，判定误码位置；③根据E纠正错误，得到正确的码组A=E+B。第二十三页，共五十二页，编辑于2023年，星期六4.汉明码 汉明码是一类常见的线性分组码，是一种能够纠正单个错误的完备码。要纠正码组中的单个错误，则要求与单个错误图样对应的伴随式各不相同，且不能为全零。若码长为n，监督码元的个数为r，则要求2r-1≥n。码组为汉明码时取等号。即用来纠正单个错误时，汉明码所用的监督码元个数最少，效率最高。第二十四页，共五十二页，编辑于2023年，星期六汉明码的特点如下。（1）监督码元的个数r=n-k，码长满足n=2r-1，则k=n-r。r≥2。（2）无论码长n为多少，汉明码最小码距d0=3。（3）其编码效率为η=k/n=2r-1-r/2r-1=1-r/n。第二十五页，共五十二页，编辑于2023年，星期六8.3循环码 循环码是另一类重要的线性分组码，它除了具有线性码的一般性质外，还具有循环性，即循环码组中任一码组循环移位所得的码组仍为该循环码中的一许用码组。 在代数理论中，为了便于计算，常用码多项式表示码字。（n，k）循环码的码字，其码多项式（以降幂顺序排列）为A（x）=an-1xn-1+an-2xn-2+…+a1x+a0第二十六页，共五十二页，编辑于2023年，星期六1.生成多项式和生成矩阵 如果一种码的所有码多项式都是多项式g（x）的倍式，则称g（x）为该码的生成多项式。在（n，k）循环码中任意码多项式A（x）都是最低次码多项式的倍式。如表8-5的（7，3）循环码中g（x）=A1（x）=x4+x3+x2+1第二十七页，共五十二页，编辑于2023年，星期六 循环码的生成矩阵可以很容易的由生成多项式得到，常用矩阵的形式表示。第二十八页，共五十二页，编辑于2023年，星期六2.监督多项式和监督矩阵 为了便于对循环码编译码，通常还定义监督多项式，令其中g（x）是常数项为1的r次多项式，是生成多项式；h（x）是常数项为1的k次多项式，称为监督多项式。同理，它的监督矩阵H第二十九页，共五十二页，编辑于2023年，星期六第三十页，共五十二页，编辑于2023年，星期六3.循环码的编解码方法和电路（1）循环码的编码 在编码时，首先要根据给定的（n，k）值选定生成多项式g（x），即从xn+1的因式中选一个r次多项式作为g（x）。第三十一页，共五十二页，编辑于2023年，星期六根据上述原理，循环码编码步骤可归纳如下。①用xr乘m（x）。这一运算实际上是把信息码后附加上r个“0”，给监督位留出地方。②用g（x）去除xr·m（x），得到商Q（x）和余式r（x）。③编出的码组为A（x）=xr·m（x）+r（x）。第三十二页，共五十二页，编辑于2023年，星期六（2）循环码的译码 原则上纠错可按下述步骤进行： ①用生成多项式g（x）去除接收码组B（x）=A（x）+E（x），得出余式r（x）； ②按余式r（x）用查表的方法或通过某种运算得到错误图样E（x），就可以确定错码位置。 ③从B（x）中减去E（x），便得到已纠正错误的原发送码组A（x）。第三十三页，共五十二页，编辑于2023年，星期六8.4卷积码 卷积码又称连环码，是1955年提出来的一种纠错码，它和分组码有明显的区别，属于非分组码。1.卷积码编码 卷积码常用符号（n，k，m）表示。其中，n为码长，k为码组中信息码元的个数，m为相互关联的码组的个数。第三十四页，共五十二页，编辑于2023年，星期六 卷积码同样也可以用矩阵的方法描述，但较抽象。因此，采用图解的方法直观描述其编码过程。常用的图解法有3种：树图、状态图和格图。（1）树图 树图描述的是在任何数据序列输入时，码字所有可能的输出。对应于图8-4所示的（2，1，2）卷积码的编码电路，可以画出其树图如图8-5所示。第三十五页，共五十二页，编辑于2023年，星期六图8-4卷积码（2，1，2）编码器第三十六页，共五十二页，编辑于2023年，星期六图8-5（2，1，2）卷积码的树图第三十七页，共五十二页，编辑于2023年，星期六（2）状态图 除了用树图表示编码器的工作过程外，还可以用状态图来描述。图8-6所示的是该（2，1，2）卷积编码器的状态图。（3）格图 格图也称网络图或篱笆图，它由状态图在时间上展开而得到。第三十八页，共五十二页，编辑于2023年，星期六图8-6（2，1，2）卷积码的状态图第三十九页，共五十二页，编辑于2023年，星期六2.卷积码的译码 卷积码的译码可分为代数译码和概率译码两大类。卷积码不是分组码，但仍属于线性码，同样可由生成矩阵G和监督矩阵H来确定。代数译码就是利用生成矩阵和监督矩阵来译码，最主要的方法是代数逻辑译码。第四十页，共五十二页，编辑于2023年，星期六（1）维特比译码 维特比译码。它是一种最大似然译码算法。最大似然译码算法的基本思路是，把接收码字与所有可能的码字比较，选择一种码距最小的码字作为解码输出。第四十一页，共五十二页，编辑于2023年，星期六（2）序列译码 当m很大时，可以采用序列译码法。其过程如下。 译码先从码树的起始节点开始，把接收到的第一个子码的n个码元与自始节点出发的两条分支按照最小汉明距离进行比较，沿着差异最小的分支走向第二个节点。在第二个节点上，译码器仍以同样原理到达下一个节点，依此类推，最后得到一条路径。第四十二页，共五十二页，编辑于2023年，星期六若接收码组有错，则自某节点开始，译码器就一直在不正确的路径中行进，译码也一直错误。因此，译码器有一个门限值，当接收码元与译码器所走的路径上的码元之间的差异总数超过门限值时，译码器判定有错，并且返回试走另一分支。经数次返回找出一条正确的路径，最后译码输出。第四十三页，共五十二页，编辑于2023年，星期六8.5网格编码调制（TCM） 引入了编码和调制相结合统一进行设计的方法，也就是网络编码调制（TrellisCodedModulation，TCM）技术。它是利用编码效率为n/（n+1）的卷积码，并将每一码段映射为2n+1个调制信号集中的一个信号，使信号点之间相互依赖。第四十四页，共五十二页，编辑于2023年，星期六它有两个基本特点。（1）在信号空间中的信号点数目比无编码的调制情况下对应的信号点数目要多，这些增加的信号点使编码有了冗余，而不牺牲带宽。（2）采用卷积码的编码规则，使信号点之间引入相互依赖关系。仅有某些信号点图样或序列是允许用的信号序列，并可模型化成为网格状结构，因此又称为“格状”编码。第四十五页，共五十二页，编辑于2023年，星期六在收端采用维特比算法执行最大似然检测。编码网格状图中的每一条支路对应于一个子集，而不是一个信号点。检测的第一