第6章信道编码.

第6章信道编码信道编码是以信息在信道上的正确传输为目标的编码，可分为两个层次上的问题：如何正确接收载有信息的信号－－线路编码如何避免少量差错信号对信息内容的影响－－纠错编码描述编码：用于对特定数据信号的描述:不归零码（NotReturntoZero，NRZ）约束编码：用于对特定信号特性的约束:HDB3码扩频编码：用于扩展信号频谱为近似白噪声谱并满足某些相关特性:m序列纠错编码：用于检测与纠正信号传输过程中因噪声干扰导致的差错：循环码信道编码的作用和分类011011,,,,0,1,,,,0,1ninicccccrrrrr消息m信道编码编码信道信道译码码字C接收向量R消息^m编码信道模型编码信道n-1当码字C和接受向量R均由二元序列表示，称编码信道为二元信道。如果对于任意的n都有：P(r/c)=∏p(ri/ci)则称此二进制信道为无记忆二元信道如果转移概率：p(0/1)=p(1/0)=pb则称此信道为无记忆二元对称信道BSC几个概念BSC转移概率BSC编码信道mod2(1),(0)1bbrcepeppepBSC输入输出关系等效为差错图案：随机序列或ie],,,[110neeee第i位上的一个随机错误：1ie差错图案e例如:C=[10000],e=[01000],R=?R=(11000)码元的组成及关系消息序列m总以k个码元为一组传输，称k个码元的码组为信息码组。信道编码器按一定规则对每个信息码组附加一些多余的码元，构成长为n个码元的码组c（信道编码）。附加的r=n-k个码元称为监督码元。检纠错是根据信道输出序列r,判断r是否可能是发送的c，或纠正导致r不等于c的错误。冗余编码：码字c的长度n一定大于消息m的长度k110,,,kmmmm110,,,ncccc纠错编码编码码率R：每个码字的序列符号（或码元）平均传送的消息比特数R/kn检错和纠错目的性质偶（或奇）校验方法：实现检纠错目的的一个基本方法。一个偶校验位P是对消息m使得如下校验方程成立的二进制符号，即2mod01210pmmmmk2mod110kmmmp一个偶校验码码字pmmmmck,,,,,1210c校验方程为1表明一定有奇数个差错，校验方程为0表明可能有偶数个差错。检错和纠错方法重复消息位：实现检纠错目的第二个基本方法一个n重复码是一个码率R为1/n的码，仅有两个码字C0和C1，传送1比特（k=1）消息。111,00010ccn重复码可以检测出任意小于n个差错的错误图案，纠正任意小于n/2个差错的错误图案。纠错码的应用方式：前向纠错方式（FEC），自动请求重发（ARQ）方式，混合纠错（HEC）方式以及信息反馈（IRQ方式）FEC与ARQ纠错应用方式检错和纠错方式常用汉明距离来描述检纠差错的数目，对于两n长向量u，v汉明距离为：最小汉明距离dmin（最小码距d）：任意两码字之间的汉明距离的最小值。',min'minccddcc1,1ni,iiduvuv检错和纠错能力定理:对一个最小距离为dmin纠错码，如下三个结论仅有其中任意一个结论成立，（1）可以检测出任意小于等于个差错；1mindl（2）可以纠正任意小于等于个差错；21mindt（3）可以检测出任意小于等于l同时纠正小于等于t个差错，其中l和t满足min1ltdtl最小码距与检纠错能力纠错码的分类根据信息元和监督元之间的关系分为：线性码：信息元与监督元之间呈线性，可用一组线性方程联系起来；非线性码：信息元与监督元之间不具有线性关系。§6.2线性分组码§6.2.1线性分组码的矩阵描述根据对信息码元处理方法的不同分为：分组码：信息序列以每k个码元进行分组，每组k个信息元按一定规律产生r个监督码元，输出序列长为n=k+r，r只与k个信息位有关，记（n，k）。分组码分为循环码和非循环码。卷积码：以k个码元分段，r不仅与k个信息位有关，还与前面L段的信息元有关，记为（n，k，L）。线性分组码：通过预定的线性运算将长为k的信息码组变成长为n的码字（nk），由2n个码字组成的集合称为线性分组码。（n，k）线性码：信息位长k，码字长n，监督位r=n-k，编码效率kRn线性分组码线性分组码的矩阵描述一个（n,k）线性分组码C是称为码字c的n维向量的集合C={c|c=mG}其中m为任意的k维向量并称为消息向量。线性分组码的生成矩阵例:(6,3)二进制分组码的输入信息组是m=(m2m1m0),码组输出是c=(c5c4c3c2c1c0)。已知输入、输出码元之间的关系式c5=m2,c4=m1,c3=m0,c2=m2+m1,c1=m2+m1+m0,c0=m2+m0，求码集C以及编码时的映射算法。解：将关系式列成线性方程组，然后写成矩阵形式如下：5241302211210020cmcmcmcmmcmmmcmm012345012110100)()011010111001cmGccccccmmm生成矩阵信息组(m2m1m0)码字（c5c4c3c2c1c0)000000000000001011010010110011011101100100111101101100110110001111111010例6.2.13重复码是一个（3，1）线性分组码111G0000210,,111,,mmmmccc例6.2.2（4，3）偶校验码是一个（4，3）线性分组码110010101001G2102102103210,,,110010101001,,,,,mmmmmmmmmccccn-k个校验位可用k个已知的信息位表示出来个校验位个信息位knknknkknnncccccc0212111,111,221,22,112,222,00,110,220,nknknnnknnnknknknknknnnknnnknknknnnnnknkchchchcchchchcchchchc一致校验矩阵1,11,12,12,20,101,0()100001000010nknnknknnknnknknnnknknhhchhchhc校验矩阵行，列一致校验矩阵H与任意一个码字之积为零，因此有0GHT由G的每一行都是一个码字，因此有rkTGH0TcH一直校验矩阵与生成矩阵的关系G是k行n列的秩为k（n≥k）的生成矩阵11121,21222,,1k2,nnkknknggggggGggg行初等变换11121,21221,121,100010001nknkskknkkrkknqqqqqqGGqIQqq系统码：生成矩阵G具有如下形式rkksQIGG对于系统码相应的一致校验矩阵Hs],[rTrksIQHH对偶码：以线性分组码的一致校验矩阵为生成矩阵称为原线性分组码的对偶码。例6.2.3一个（5，3）线性分组码的ssHGG,,010111101001101G100010101100111sG其中到的行初等变换过程为：？GsG0111011101sH31311233,,RRRRRRRR例：考虑一个（7，4）码，其生成矩阵是：41000101010011100101100001011GIP①对于信息组m=(1011),编出的码字是什么？②若接收到一个7位码r=(1001101),检验它是否为码字？解：设输入信息组3210[]mmmmm编码后的码字6543210[]cccccccc①由c=mG可知，将m和G的值代入，可得对应码字本题由于是系统码，3210210()cmmmmccc前4位不必计算，后3个校验位可以根据生成矩阵G的分块阵P列出现行方程组如下232112100320(cmmmcmmmcmmm式中“”指模2加）将代入方程组，得所以码字为c=[1011000]。32101,0,1,1mmmm2100,0,0ccc②H矩阵如下：1110100[]01110101101001TnkHPI根据式，如果接受到的r是属于码集C的某码字，必有；反之，如，说明r必定不是码字。将H和r=[1001101]代入式，得：0TcH0TrH0TrH0TcH(011)(000)TrH说明r与H不正交，接收的r=(1001101)不是码字。检错译码：译码器输出为当前接收向量r和r是否有差错的标志s，即y=(r,s)。§6.2.2线性分组码的译码伴随式S：(n,k）线性分组码的伴随式是一个r(r=n-k)维向量110,,,rTsssrHsTeHs，则传输中一定有错误发生。s，则传输中要么无差错发生，要么差错图案恰好为一个码字。s0TcHrce（1）汉明码汉明码不是指一个码，而是代表一类码；汉明码码长n和信息位k服从以下规律：(n,k)=(2m-1,2m-m-1)；汉明码的最小距离d=3；所以，纠错能力t=1；§6.2.3码例与码的重构例6.2.4一个二元（7，4）Hamming码的系统码形式的矩阵和校验矩阵分别为1101000011010011100101010001G100101101011100010111H等价的编码方程为3106321521043,2,1,0,mmmcmmmcmmmcimcii伴随式计算方程：631025321142100rrrrsrrrrsrrrrsTSrH（2）Hadamard码Hadamard码是由Hadamard矩阵派生出的一种纠错码阶实Hadamard矩阵由元素为+1，-1的矩阵递归定义：mNN21/2/2/2/21-NNNNNHHHHHH1111111111111111,111142HHHadamard矩阵为正交矩阵，即中的任意不同两行（列）的点积为0，即NH10,NijikjkkhhhhijNTNNINHH超正交矩阵：Hadamard矩阵中的第1列（全+1列）去掉后任两行的点积为-1。NH~NH将Hadamard矩阵元素+1/-1映射为0/1，则Hadamard矩阵映射后的行向量为一个二元向量，以这些二元向量的部份或全体就构成标准0/1二元意义上的分组码，并称为Hadamard码。具体的Hadamard码的选择构成有正交码、双正交码和超正交码三种形式。（A）正交码：以的全部行向量的0/1映射向量为码字。NH1222/log22mmmNdmNkNMNn最小码距信息位长码字数码长（B）双正交码：以和-的全部行向量的0/1映射向量为码字。NHNH1122/222mmmNdNMNn（C）超正交码：以的全部行向量的0/1映射向量为码字。NH~122/2121mmmNdNMNn例6.2.5（7，3）超正交码的超正交