汉明编译码

⑴ 什么是译码

译码是编码的逆过程，同时去掉比特流在传播过程中混入的噪声。利用译码表把文字译成一组组数码或用译码表将代表某一项信息的一系列信号译成文字的过程称之为译码。
译码器是电子技术中的一种多输入多输出的组合逻辑电路，负责将二进制代码翻译为特定的对象（如逻辑电平等），功能与编码器相反。译码器一般分为通用译码器和数字显示译码器两大类。
数字电路中，译码器（如n线－2n线BCD译码器）可以担任多输入多输出逻辑门的角色，能将已编码的输入转换成已编码的输出，这里输入和输出的编码是不同的。
输入使能信号必须接在译码器上使其正常工作，否则输出将会是一个无效的码字。译码在多路复用、七段数码管和内存地址译码等应用中是必要的。

⑵ PDF417译码，RS纠错码，求纠错码生成多项式零点问题！

纠错码能够检错或纠错，主要是靠码字之间有较大的差别。这可用码字之间的汉明距离d(x，y)来衡量。它的定义为码字x与y之间的对应位取不同值的码元个数。一种纠错码的最小距离d定义为该种码中任两个码字之间的距离的最小值。一种码要能发现e个错误,它的最小距离d应不小于e+1。若要能纠正t个错误，则d应不小于2t+1。一个码字中非零码元的个数，称为此码字的汉明重量。一种码中非零码字的重量的最小值，称为该码的最小重量。对线性码来说，一种码的最小重量与其最小距离在数值上是相等的。
在构造线性码时，数字上是从n维空间中选一k维子空间，且使此子空间内各非零码字的重量尽可能大。当构造循环码时,可进一步将每一码字看成一多项式,将整个码看成是多项式环中的理想,这一理想是主理想,故可由生成多项式决定；而多项式完全可由它的根规定。这样,就容易对码进行构造和分析。这是BCH码等循环码构造的出发点。一般地说，构造一种码时，均设法将它与某种代数结构相联系，以便对它进行描述，进而推导它的性质，估计它的性能和给出它的译码方法。若一种码的码长为n，码字数为M,或信息位为h,以及最小距离为d，则可把此码记作【n,M,d】码。若此码为线性码，常简记作(n，k)或(n,k,d)码。人们还常用R=log2M/n表示码的信息率或简称码率,单位为比特/码元。R越大,则每个码元所携带的信息量越大，编码效率越高。 纠错码实现中最复杂的部分是译码。它是纠错码能否应用的关键。根据式(1),采用的码长n越大,则误码率越小。但n越大，编译码设备也越复杂,且延迟也越大。人们希望找到的译码方法是:误码率随码长n的增加按指数规律下降;译码的复杂程度随码长n的增加接近线性地增加；译码的计算量则与码长n基本无关。可惜，已经找到的码能满足这样要求的很少。不过由于大规模集成电路的发展，即使应用比较复杂的但性能良好的码，成本也并不太高。因此，纠错码的应用越来越广泛。
纠错码传输的都是数字信号。这既可用硬件实现，也可用软件实现。前者主要用各种数字电路，主要是采用大规模集成电路。软件实现特别适合计算机通信网等场合。因为这时可以直接利用网中的计算机进行编码和译码，不需要另加专用设备。硬件实现的速度较高，比软件可快几个数量级。
在传信率一定的情况下，如果采用纠错码提高可靠性，要求信道的传输率增加，带宽加大。因此，纠错码主要用于功率受限制而带宽较大的信道，如卫星、散射等系统中。纠错码还用在一些可靠性要求较高，但设备或器件的可靠性较差，而余量较大的场合，如磁带、磁盘和半导体存储器等。
在分组码的研究中，谱分析的方法受到人们的重视。纠同步错误码、算术码、不对称码、不等错误纠正码等，也得到较多的研究。 分组码是对信源待发的信息序列进行分组（每组K位）编码，它的校验位仅同本组的信息位有关。自20世纪50年代分组码的理论获得发展以来，分组码在数字通信和数据存储系统中已被广泛应用。
分组码的码长n和码字个数M是一个码的主要构造参数。码长为n的码中所有码字的位数均为n；若要用一个码传送k比特信息，则码字的个数M必须满足。典型的分组码是由k位信息位和r位监督位组成的，这样构成的码一般称为系统码。
分组码中应用最广的线性分组码。线性分组码中的M个码字之间具有一定线性约束关系，即这些码字总体构成了n维线性空间的一个k维子空间。称此k维子空间为（n，k）线性分组码。线性系统码的特点是每个码字的前k位均由这个码字所对应的信息位组成，并通过对这k位信息位的线性运算得到后面n—k是位监督位。
线性分组码中应用最广的是循环码，循环码的主要特征是任何码字在循环移位后个码字。循环码的优点在于其编码和解码手续比一般线性码简单，因而易于在设备上实现。在循环码中，码字可表示为多项式。循环码的码字多项式都可表示成为循环码的生成多项式与这个码字所代表的信息多项式的乘积，即，因此一个循环码可以通过给出其生成多项式来规定。常用的循环码有BCH码和RS码。
网格码有多种描述方法，网格图是常用方法之一，它能表示出编码过程。一个码率为1/2、包含四种状态的网格码的网格图如图所示。图1中00，01，10，11表示编码器所具有的四种状态，以“·”示出，从每一状态出发都存在两条支路，位于上面的一条支路对应于编码器输入为“0”的情况，位于下面的一条支路对应于编码器输入为“1”的情况，而每一支路上所列出的两个二进位码则表示相应的编码输出。因而可知，编码输出不仅决定于编码器的当前输入，还决定于编码器的状态，例如在图中从“00”状态出发；，若输入的二进制数据序列为1011，则编码器的状态转移过程为00→01→10→01→11，而相应的编码输出序列为11010010。在网格图中任意两条从同一状态出发；，经不同的状态转移过程后又归于另一相同状态（该状态也可与初始状态相同）的路径间的距离的最小值称为码的自由距离。如该图中的为5。对于卷积码来说，的计算可简化为始于且终于零状态的非全零路径与全零路径间距离的最小值。是表征网格码纠错能力的重要参数。维特比算法是广泛采用的网格码的译码方法。由于网格码的状态越多，译码越复杂，所以状态个数是度量网格码译码复杂性的重要参数。一般说来可以通过增大译码复杂性来增加，从而提高码的纠错能力。
BCH码、网格码已被广泛地应用于移动通信、卫星通信和频带数据传输中。RS码也被广泛应用于光盘的存储中。
大多数纠错码是设计来纠随机误码的，可以通过交织的方法使它适用于对突发误码的纠错。交织是一种使得集中出现的突发误码在解码时进行分散化的措施，从而使其不超出纠错码的纠错能力范围。 卷积码不对信息序列进行分组编码，它的校验元不仅与当前的信息元有关，而且同以前有限时间段上的信息元有关。卷积码在编码方法上尚未找到像分组码那样有效的数学工具和系统的理论。但在译码方面，不论在理论上还是实用上都超过了分组码，因而在差错控制和数据压缩系统中得到广泛应用。

⑶ LDPC码的码的构造

对LDPC码来说，不考虑码长和次数分布的情况下，校验矩阵的结构就成了影响其性能的重要因素，反映在二分图上对编码性能有重要影响的就是图中环的长度分布，需要采用一定的方法对校验矩阵进行构造，获得好的编码。
目前LDPC码的构造方法主要可以分为两大类：随机或伪随机构造方法和代数的构造方法。
随机或伪随机的构造方法主要考虑的是码的性能，在码长比较长(接近或超过10000) 时，性能非常接近香农限。代数的构造方法通常考虑的是降低编译码的复杂度，在码长比较短的时候更有优势。
1. Gallager LDPC码
用和乘积算法(SPA:Sum-pordcuct algorithm)进行译码取得最大后验概率的译码性能的条件是二分图中没有小的环，即girth为4的环，无4环的条件反映到二分图中就是任意两行中1的交迭数目不超过1个。无4环的二元高比特率LDPc码可以通过随机生成行构成，一般来说，这种方法不能生成固定行重量的矩阵。
Gallaegr提出了一种替代的方法：采用随机置换的方法来构造规则LDPC码。对于码长为N的(j，k)正则码，将M*N矩阵H通过j个大小为(M/j)*N的子矩阵构成，每个子矩阵本身也是LDPC矩阵，列重量为1，行重量为k，第一个子矩阵为阶梯型，即第1行的k个1的列号是从(i-1)*k l到1*k，而其他子矩阵都是第一个子矩阵的随机列置换，这样每个子矩阵每行都有k个1，每列都有1个1。这种构造方法要求M必须是j的整数倍。
(20，3，4)LDPC码的校验矩阵
Gallager曾给出了一个码长为20的规则(3，4）LDPC码的校验矩阵，如图所示。图中的第一个子矩阵就是一个阶梯型矩阵，而第2个和第3个矩阵都是第一个子矩阵的列置换。
Gallager同时证明了随机置换得到的GaHager LDPC码的最小汉明距离能够随着码长的增加而线性增加，而且在对称无记忆信道中，采用最大似然译码时，其误码率随着码长的增加而呈指数形式下降，这说明随机置换得到的Gallager LDPC码是一类相当好的码。
但是，Gallager在构造LDPC码时采用的是随机置换，这就给实现带来了麻烦，就需要大量的存储单元来存储校验矩阵中这些1的位置。
2. 确定性结构的LDPC码
确定性结构的DLPC码也称为准循环LDPC码。相对于随机结构的矩阵是很容易获得的确定性结构的矩阵，这种矩阵可以通过更少的参数来定义LDPC码。确定性结构的LDPC码的构造方法基于“阵列码”(Array Code)。阵列码是用来检测和纠正突发差错的二维码。
通过三个参数定义LDPC码。一个基本参数p和两个整数j和k。令H为jp*kp的矩阵，定义为：
LDPC码
其中这里的I是p*p的单位阵，Bi.j是Ip*p的左循环移位Bm.n或右循环移位Bm.n的置换矩阵。显然，H矩阵中1的分布就只与循环位数Bm.n有关。对LDPC码的分析就可以转换为对Bm.n的分析。
将各小矩阵的循环移动位数写成一个矩阵为
LDPC码
上面的校验矩阵提供了一个可以用于SAP译码的稀疏矩阵。而且，这个校验矩阵结构上没有四线循环。

⑷ 信道编码技术及电子系统工程应用的探讨论文

信道编码技术及电子系统工程应用的探讨论文

根据信道编码理论及编码、译码方法和技术的发展，结合工程实际从理论到实践进行了简要的阐述。

随着信息及信号传输技术的发展，应用电子领域也随之扩大并得到发展。通过对信源编码、信道编码、编码的方法，以及对压缩后的信息进行纠错编码，以抗击信道、网络及传输过程的误码或数据丢失，即信道编码问题的系统认识与理解对实际工程应用具有重要的意义。从电子系统工程的应用角度，对相关知识的理解与应用体会更为深刻。在此，就实际应用中贯穿其中的相关知识及带来的思考与启发扼要介绍。

一、信道编码理论及编、译码问题

衡量任何一个信号通信系统性能优劣的基本因素是有效性和可靠性，有效性是信道传输信息的速度快慢，可靠性是信道传输信息的准确程度。在数字通信系统中，信源编码是为了提高有效性，信道编码是为了提高可靠性，而在一个通信系统中，有效性和可靠性是互相矛盾的，也是可以互换的。我们可以用降低有效性的办法提高可靠性，也可以用用降低可靠性的办法提高有效性。而纠错编码，即信道编码问题是重点。

(一)编、译码问题

信道编码是以香农第二定理和香农第三定理为理论支持。在错误控制编码方面，主要是纠错线性分组码与非分组的卷积码。对于线性分组码，采用增加冗余码作为监督码，这样编出的码具有一定的检错和纠错能力。在译码方面，根据最大似然法译码，判断码的汉明距离，找到汉明距离最小的码，那就是在发送端传输过来的码。编码是一个比较抽象的概念，采用矩阵的描述方式表示编码，将输入的信息序列与生成矩阵相乘，那么就可以得到编码后的符号。在译码方面，通过奇偶校验矩阵就可以检测译码是否正确。

(二)关于卷积码

卷积码是编码不一样的领域，因为这种码在判决时用到过去的信息，也就是说，它是需要记忆的。这也就是卷积码得名的由来。卷积码的编码器由一个移位寄存器和相关逻辑电路组成，对每一个进入的信息帧，编码器都产生一个码字帧。当然，还可以画编码器的状态图，比较直观表示编码器根据输入情况而变化。根据状态图可画出网格图;由网格图很容易地知道卷积码的距离，这是卷积码译码的一个依据。卷积码用一个生成多项式矩阵表示，在编码方面极为方便，编码操作可以简单地描述为信息量矩阵与生成矩阵的乘积。而更加严谨、方便地表达，则需要生成函数。通过修改状态图，很容易得到生成函数。对生成函数的级数展开，可以很直观地得到汉明距离和输入路径的信息，最后还可以知道给定汉明距离全零路径的数量。

(三)Turbo码和LDPC码

Turbo码与LDPC码是两种性能接近香农极限的信道编码。Turbo码在低信噪比的情况下，性能比其他编码要好。Turbo码的优良性能在非实时数据通信方面被广泛采用。Turbo码是分组码和卷积码的“准”混合物。Turbo码有并行级联卷积码、串行级联卷积码和混杂级联卷积码三种不同的排列。因为有交织器的存在，所以编码器的纠错能力很好。LDPC码是一类可以用非常稀疏的校验矩阵或二分图定义的线性分组码，其特点是：译码算法具有线性复杂度可采用并行迭代方式，具有译码自校验特性，在高信噪比条件下能有效降低译码复杂度，提高误比特率性能;可以满足高性能信号通信要求。LDPC码以最低的复杂度提供了最好的性能。这意味着在同等性能情况下， LDPC码的复杂度只有Turbo码的1/4。与Turbo码相比，LDPC码尤其是非规则LDPC码具有非常出色的性能，优于迄今为止已知的其它编码方式。LDPC码与其它编码相比还有一些独特的优点：译码可以完全并行，因此可以获得更高的译码速度;译码器的复杂度大幅降低;译码是可验证的;非规则LDPC码具有天然的不等错误保护能力。

二、从信道编码定理看编、译码方法的发展

(一)信道编、译码方法的多样性

信道编码的'核心是“纠错”;信道编、译码的最终目的是实现信道与信号通信系统在可靠性指标下的优化。其方法是纠错编码，即抗干扰编码。奇偶校验码是一种检错分组码;由此原理派生出改进的：水平奇偶校验码、垂直奇偶校验码、群计数码等。定比码是一种只能发现错误的简单检错码，且需通过反向信道系统方能实现抗干扰。而重复码是前向纠错码，也是一种最简单的纠错码，实际应用较广泛。而由汉明码引出的线性分组码是一种具有线性代数关系的编码。在实际应用中，为得到希望的码长和信息位长度，将信息位缩减而得到原码的缩短码。在汉明码的基础上增加一位监督元，则产生增余汉明码或扩展汉明码，使纠错能力得到提高。而由完备码产生的完备译码、非完备译码，则反映了分组码的纠错能力是全部用于纠错，还是部分纠错检错。循环码是线性分组码中重要的一类码，从应用角度其编码与译码电路较为简单，易于实现;且编、译码方法方便、成熟。

(二)信道编、译码方法的发展过程与启示

不难看出，信道编码的方法是丰富多彩的。也是渐进发展，逐步完善的过程。由此可见，理论指导是发展的方向。对信道编码的理论支撑及方向的指引，使得信道编码方法沿着丰富而日臻完善、接近而趋于极限的方向发展。从这一发展过程可以看出，任何一种新的或衍生的方法，都是有局限性的。但这种局限和不完善性，并不会阻碍新的方法的产生和发展。旧的矛盾解决的同时，新的矛盾又会出现。正如，纠错检错能力的提高，对信息进行错误保护，以抵御信道或网络等信息传输过程的干扰所产生的误码或数据丢失的同时，也将使编码及信息传输效率降低。由于信道编码增加了数据量，其结果只能是以降低传送有用信息码率为代价。因此，不同的编码方式，其纠、检错的能力不同，编码效率(信息传输效率)也有所不同。

三、从工程应用实例看理论支撑点

(一)智能住宅小区建设中信道编码技术的应用

在工程中首次接触的，应用于数字电视地面广播(DTTB)的编码调制方案中，涉及到：以多级分组乘积码代替传统的串行级联编码结构，提高了频谱效率;同时采用一种多分辨率星座图，可在一个DTTB信道中提供3种级别的服务.在接收端采用基于MAX—LOG—MAP准则的迭代Turbo译码算法以获得可靠接收。仿真结果表明，在视觉门限BER=3×10-6处，高优先级码流的比特信噪比约为7dB，适用于高可靠性的服务.中优先级和低优先级码流可支持室外固定接收。由此，也加深了对并行级联卷积码的反馈迭代结构的理解。

(二)网络编码与网络安全

在网络工程中，接触到多址信道中联合网络编码和信道编码的设计方案。该方案利用LDPC码和网络编码的线性特性以及软输入软输出模块设计，不仅减少了编译码的复杂度，而且提高了编译码效率。同时，了解了网络——信道编码分离定理，以及该定理成立的条件，即当网络中的信道是确定型广播信道时，分离定理不成立。而信道安全编码与网络安全编码同样重要，又有所区别。信道编码问题，其核心是对传送的信息进行错误保护，以抗击信道或网络等信息传输媒介所带来的误码或数据丢失。而网络中的通信安全是网络编码研究的重要课题之一，网络安全编码更侧重于网络使用者信息及使用的安全层面。网络编码技术的发展可以大幅度提高网络的吞吐量。

四、结束语

专业技术的专长与拓展并存，这是专业技术发展的必然趋势。身处信息时代，信息科学是研究信息的获取、传输以及应用的科学，是信息资源与技术开发及其推广应用的理论基础，是信息技术及信息产业的核心。通信工程、电子信息工程、计算机科学、计算机应用等众多应用技术与信息科学、信息技术及信息产业息息相关。信道编码从理论上要解决理想编码器、译码器的存在性问题，即解决信道能传送的最大信息率的可能性和超过这个最大值时的传输问题;同时构造性的编码方法以及这些方法能达到的性能界限。筒言之，通过信道编码器和译码器来实现的用于提高信道可靠性的理论和方法。