第6章：信道编码2024/7/2816.1 信道编码的概念信道编码的概念 6.2 线形分形分组码 6.3 循循环码 6.4 卷卷积码2024/7/2826.1.1信道编码的作用和分类6.1.2：编码信道6.1.3：检错和纠错原理6.1.4：检错和纠错方式和能力2024/7/283作用作用提高信息传输时的抗干扰能力提高信息传输时的抗干扰能力目的目的增加信息传输的可靠性增加信息传输的可靠性手段手段增加信息冗余度增加信息冗余度名称名称信道码、数据传输码、差错控制码信道码、数据传输码、差错控制码42024/7/28信道编码是在数据传输/存储中所采用的降低系统差错率，提高系统可靠性的一种数字处理技术。狭义信道编码：纠错编码2024/7/285“明天明天14:0014:0016:0016:00开会开会”举例举例“明天明天10:0010:0016:0016:00开会开会”由于某种原因，由于某种原因，产生错误产生错误待发通知待发通知“明天明天下午下午14:0014:0016:0016:00开会开会”“明天明天下午下午10:0010:0016:0016:00开会开会”增加的冗余码增加的冗余码具有检错能力具有检错能力“明天明天下午下午14:0014:0016:0016:00开会开会两小时两小时”增加的冗余码具有增加的冗余码具有检纠错能力检纠错能力差错控制编码的基本思想：2024/7/286u信道编码的对象：是信源编码器输出的信息序列m。通常是二元符号1、0组成的序列。u差错控制编码的基本思想：按一定规则给数字序列m增加一些多余的码元，使不具有规律性的信息序列m变换为具有某种规律性的码序列C；码序列中的信息序列码元与多余码元之间是相关的；信道译码器利用这种预知的编码规则译码。检验接收到的数字序列R是否符合既定的规则，从而发现R中是否有错，或者纠正其中的差错；u编码的实质利用冗余降低差错概率。2024/7/287 描述编码描述编码用于对特定数据信号的描述用于对特定数据信号的描述约束约束编码编码用于对特定信号特性的约束用于对特定信号特性的约束扩频编码扩频编码用于扩展信号频谱为近似白噪声谱并满足某些相用于扩展信号频谱为近似白噪声谱并满足某些相关特性关特性 纠错编码纠错编码用于检测与纠正信号传输过程中因噪声干扰导致用于检测与纠正信号传输过程中因噪声干扰导致的差错的差错12342024/7/288三、纠错码的分类(1)根据纠错码各码组信息元和监督元的函数关系，可分为线性码和非线性码。如果函数关系是线性的，即满足一组线性方程式，则称为线性码，否则为非线性码。(2)根据上述关系涉及的范围，可分为分组码和卷积码。分组码的各码元仅与本组的信息元有关；卷积码中的码元不仅与本组的信息元有关，而且还与前面若干组信息元有关。(3)根据码的用途，可分为检错码和纠错码。检错码以检错为目的，不一定能纠错；而纠错码以纠错为目的，一定能检错。u对纠错码的基本要求是:检错和纠错能力尽量强；编码效率尽量高；编码规律尽量简单。2024/7/2896.1.1：信道编码的作用和分类6.1.2编码信道6.1.3：检错和纠错原理6.1.4：检错和纠错方式和能力2024/7/28102024/7/2811信源：输出的是信息序列（信息码元）信源：输出的是信息序列（信息码元）信道：广义信道，也称编码信道信道：广义信道，也称编码信道编码信道：是研究纠错编码和译码的一种模型。编码信道无线通信中的发射机、天线、自由空间、接收机等的全体；有线通信中的如调制解调器、电缆等的全体；Internet网的多个路由器、节点、电缆、底层协议等的全体；计算机的存储器（如磁盘等）的全体。2024/7/28122024/7/2813信源编码后的消息m=0110，长度为k=4信源编码后的消息记作：信道编码后的码字c=01100，长度为n=5信道编码记作：新增加的r位称为监督位:此例r=1记作（n，k）码，此例中该码为（5，4）码传输到接收端接收到的向量r=11100接收向量记作：当码字当码字C C和接收向量和接收向量R R均由二元序列均由二元序列表示，表示，称编称编码信道为码信道为二进制信道如果如果对于任意对于任意的的NN都都有：有：P(P(r/c)=)=p(p(ri i/ /ci i) )则则称此二进制信道为称此二进制信道为无记忆二进制信道。p(0/1)=p(1/0)=p(0/1)=p(1/0)=pb b则称此信道为则称此信道为无记忆二进制对称信道BSCi=0三、无记忆二元对称信道（三、无记忆二元对称信道（BSCBSC）1 1、定义、定义2024/7/2814BSC转移概率转移概率BSC编码信道编码信道BSC输入输出关系等效为输入输出关系等效为2024/7/2815差错图案：随机序列称为差错图案，第位上的一个随机错误：突发错误：第i至第j位之间有很多错误时，称为一个ji+1长的突发错误2024/7/28162024/7/2817例：发送序列C：（1111100000），收到的序列R：（1000010000），第二、三、四、五、六位产生了错误，因此差错图案e的二、三、四、五、六位取值为1，即e：(0111110000)对于差错图案中，第一个“1”和最后一个“1”之间的码元总个数称为突发长度，其图样称为突发图样。该例中，突发图样是（11111），称为5长的突发错误。6.1.1：信道编码的作用和分类6.1.2：编码信道6.1.3检错和纠错原理6.1.4：检错和纠错方式和能力2024/7/28182024/7/2819检错与纠错：根据信道输出的序列r，来判断r是否为发送的c，如果不是将其纠正为c.信道编码器的编码速率R（编码效率/传信率/码率）：每码元携带的平均信息量。它说明了信道的利用效率，是衡量信道编码性能的一个重要参数。冗余编码：码字的长度一定大于消息的长度分组码及参数分组码：将信息序列分成k位一组，按照一定的校验关系增加r位校验位，构成n(n=k+r)位码分组，称为码字（Codewords)，所有可能码字构成的集合称为一个分组码，记为(n,k)分组码分组码的校验关系仅限于一个码分组之内2024/7/2820分组码及参数主要参数：信息分组：m=(mk-1mk-2m1m0)码字：C=(cn-1cn-2c1c0)码长n，信息位个数k，校验位个数r=n-k码字个数(二进制)：2k编码效率：R=k/n2024/7/28211、偶（或奇）校验方法：l一个偶校验位是对消息使得如下校验方程成立的二进制符号，即一个偶校验码码字一个偶校验码码字 c的全体C是(k+1,k)码。u校验方程为1表明一定有奇数个差错，校验方程为0表明可能有偶数个差错u可以检测任意奇数个错误2024/7/2822多个奇偶校验位一个校验位可以由信息位的部分或全部按校验方程产生；例如C是一个对阵列消息进行垂直与水平校验以及总校验的码字；其码率为l当校验位数增加时，可以检测到差错图案种类数也增加，同时码率减小。2024/7/28232、重复消息位方法n重复码：若分组码码字中的监督元在信息元之后，而且是信息元的简单重复，则称该分组码为重复码。码率为1/n，仅有两个码字C0和C1，传送1比特(k=1)消息；C0=(000)，C1=(111)n重复码可以纠正出任意小于n/2个差错的错误图案BSC信道：pb1/2，n比特传输中发生差错数目越少，概率越大(1pb)npb(1pb)n1pbt(1pb)ntpbn总认为发生差错的图案是差错数目较少的图案2024/7/2824重重复复码码可可以以检检测测出出任任意意小小于于 个个差差错错的的错错误误图案，纠正任意小于图案，纠正任意小于 个差错的错误图案。个差错的错误图案。2024/7/28253、等重码/定比码码重：对于二进制码组，码组中“1”码元的个数称为码重，用W(C)表示.等重码码字中“1”和“0”的个数保持相同的比例，即每个码字中1的个数相同。这种码在检测时，只要计算接收码元中1的数目是否正确，就知道有无错误。等重码是一种检错码,一般用在电报。除了1错成0正好等于0错成1的误码外，定比码可以检测出所有其他错误方式，适用于有限字母、符号，不适用于传输信源二元序列。2024/7/28262024/7/2827等重码/定比码例：发汉字电报时，每个汉字用4位阿拉伯数字表示，每个阿拉伯数字用5个比特的码字表示。由于阿拉伯数字只有10个，因此从32种可能的码字中挑出10个1的个数为3的码字作为阿拉伯数字的编码方式。阿拉伯数字阿拉伯数字编码编码阿拉伯数字阿拉伯数字编码编码101011610101211001711100310110801110411010910011500111001101 6.1.1：信道：信道编码的作用和分的作用和分类 6.1.2：编码信道信道 6.1.3：检错和和纠错原理原理6.1.4 检错和纠错方式和能力检错和纠错方式和能力2024/7/28282024/7/2829前向纠错方式（FEC）自动请求重发方式（ARQ）混合方式（HEC）2024/7/2830一、差错控制的基本方式一、差错控制的基本方式前向前向纠错方式方式 (Forward Error Correction, FEC)工作原理：发送端的信道编码器将信息码组编成具有一定纠错能力的码。接收端信道译码器对接收码字进行译码，若传输中产生的差错数目在码的纠错能力之内时，译码器对差错进行定位并加以纠正。不需要反馈信道，实时性好。随着纠错能力的提高，编译码设备复杂。2024/7/2831自动请求重发方式(AutomaticRepeatreQuest,ARQ)工作原理：发送端发送的是检错码，通过信道传输到接收端，接收端译码器只需根据编码规则判断是否有错误，并把判决信号通过反馈信道送回发送端。发送端根据判决信号将收端认为有错误的重新发送，直到接收端检查无误为止。发端发端收端收端检错码检错码判决信号判决信号优点：1.译码设备简单2.纠错能力强3.对信道的适应性强缺点：1.需反馈信道2.控制电路复杂3.传送信息的实时性、连贯性差2024/7/2832一、一、 差错控制的基本方式差错控制的基本方式混合纠错方式(HybridErrorCorrection,HEC)工作原理：结合FEC和ARQ的系统，在纠错能力范围内，自动纠正错误，超出纠错范围则要求发送端重新发送。折衷方案。2024/7/2833二、检错与纠错能力指标二、检错与纠错能力指标码重（汉明重量）、码距（汉明距离）码重：码字中非0码元的个数，又称汉明重量。例如码字x=(11000)，则码重w(x)=2码距：码字x与码字y对应位取值不同的个数，又称为汉明距离。例如：x=(10111101)，y=(01110101)2024/7/2834二、检错与纠错能力指标二、检错与纠错能力指标汉明距离与汉明重量的关系二进制n维向量：U=(u0，u1,un-1)，V=(v0,v1,vn-1)则有：d(U,V)=w(U+V)其中：U+V=(u0+v0,u1+v1,un-1+vn-1)n例如：C=(10110011),R=(01011011)则：d(C,R)=w(C+R)=w(11101000)2024/7/2835二、检错与纠错能力指标二、检错与纠错能力指标最小码距（最小汉明距离）最小码距：（n，k）分组码中，任何两个码字之间距离的最小值，称为该分组码的最小汉明距离，简称最小距离，用表示。最小码距描述分组码特性的重要参量，决定了码的纠错、检错性能。(n,k)分组码通常也记为(n,k,d)分组码。u最小距离与检、纠错能力一般地说，线性码的最小距离越大，意味着任意码字间的差别越大，则码的检、纠错能力越强。检错能力：如果一个线性码能检出长度l l 个码元的任何错误图案，称码的检错能力为l l。纠错能力：如果线性码能纠正长度t个码元的任意错误图样，称码的纠错能力为t。二、检错与纠错能力指标二、检错与纠错能力指标2024/7/2836定理对一个最小距离为纠错码，如下三个结论仅有其中任意一个结论成立，（1）可以检测出任意小于等于个差错；（2）可以纠正任意小于等于个差错；（3）可以检测出任意小于等于l同时纠正小于等于t个差错，其中l和t满足二、检错与纠错能力指标二、检错与纠错能力指标2024/7/2837最小码距与检纠错能力最小码距与检纠错能力 2024/7/28382024/7/2839最小汉明距离译码准则：在许用码组中，判断与接收序列r“最近”的码字为发送码字即最小差错概率译码等价为使接收向量与输出码字距离最小的最小距离译码。例：例：C=111000,001011,010110,101110,接收接收到的向量到的向量为110110，问将将r译码为哪个哪个发送送码字字错误概率最小？概率最小？二、检错与纠错能力指标二、检错与纠错能力指标信息比特信噪比：传输一个比特信息所需的最小信噪比比特差错概率(又称误码率)与信噪比的关系如下图所示，采用纠错码后，达到同样比特差错概率实际需要的信噪比减小量称为编码增益。编码增益：编码增编码增益：编码增益反映的是一定误益反映的是一定误码率要求下具体的码率要求下具体的编码方案对信噪比编码方案对信噪比的改善程度。的改善程度。2024/7/2840 6.2 6.2 线性码线性码6.2.1线性分组码的矩阵描述6.2.2线性分组码的译码6.2.3码例与码的重构2024/7/2841线性分组码在(n,k)分组码中，若每一个监督元都是码组中某些信息元按模二和而得到的，即监督元是按线性关系相加而得到的，则称线性分组码。或者说，可用线性方程组表述码规律性的分组码称为线性分组码。一、基本概念2024/7/2842线性分组码的编码：线性分组码的编码过程分为两步：把信息序列按一定长度分成若干信息码组，每组由k位组成；编码器按照预定的线性规则(可由线性方程组规定)，把信息码组变换成n位(nk)码字，其中(nk)个校验码元是由信息码元的线性运算产生的。信息码长k位，有2k个不同的信息码组，则有2k个码字与它们一一对应。一、基本概念2024/7/2843以下通过一个实例来介绍校验矩阵和生成矩阵的有关概念编码就是给已知信息码组按预定规则添加监督码元，以构成码字。在k个信息码元之后附加r(r=nk)个监督码元，使每个监督元是其中某些信息元的模2和。举例：k=3,r=4，构成(7,3)线性分组码。设码字为(C1,C2,C3,C4,C5,C6,C7)C1,C2,C3为信息元，C4,C5,C6,C7为校验元，每个码元取“0”或“1”监督元可按下面方程组计算二、校验矩阵与生成矩阵2024/7/2844一致监督方程/一致校验方程：确定信息元得到校验元规则的一组方程称为监督方程/校验方程。由于所有码字都按同一规则确定，又称为一致监督方程/一致校验方程。由于一致校验方程是线性的，即监督元和信息元之间是线性运算关系，所以由线性监督方程所确定的分组码是线性分组码。2024/7/28451、一致校验矩阵校验方程可改写为：u为了运算方便，将监督方程写成矩阵形式，得:系数矩阵H的后四列组成一个(44)阶单位子阵，用I4表示，H的其余部分用P表示推广到一般情况：对(n,k)线性分组码，每个码字中的r(r=nk)个监督元与信息元之间的关系可由下面的线性方程组确定令上式的系数矩阵为H，码字行阵列为C若把校验方程补充为下列方程若把校验方程补充为下列方程 2024/7/2850令令C=C=mG,mG,则方程可改写为矩阵的形式：则方程可改写为矩阵的形式：2、线性分组码的生成矩阵定义对与(n,k)线性分组码有如下关系式：其中C为n维矢量，m为k维信息矢量，G为线性分组码C的生成矩阵。G为一个k*n阶矩阵利用生成矩阵G可将信息码编成对应的码字，当已知码的生成矩阵时，编码问题就解决了。系统分组码通过行初等变换，将G化为前k列是单位子阵的标准形式 系统分组码：用标准生成矩阵Gkn编成的码字，前面k位为信息码，后面r=nk位为校验码，这种信息码在前校验码在后的线性分组码称为线性系统分组码。当生成矩阵G确定之后，(n,k)线性码也就完全被确定了，只要找到码的生成矩阵，编码问题也同样被解决了。3、生成矩阵与一致校验矩阵的关系由于生成矩阵G的每一行都是一个码字，所以G的每行都满足HrnCTn1=0Tr1，则有HrnGTnk=0Trk或GknHTnr=0kr线性系统码的监督矩阵H和生成矩阵G之间可以相互转换。对于系统码有4、对偶码对偶码：对一个(n,k)线性码CI，由于HrnGTnk=0Trk，如果以G作监督矩阵，而以H作生成矩阵，可构造另一个码CId，码CId是一个(n,nk)线性码，称码CId为原码的对偶码。当生成矩阵给定时线性分组码有如下性质：（1）零向量一定是一个码字，称为零码字；（2）任意两码字的和仍是一个码字；（3）任意码字是的行向量的线性组合；（4）线性分组码的最小距离等于最小非零码字重量。2024/7/28555、线性分组码的性质由一致校验矩阵可以比较容易确定线性分组码的最小码距定理线性分组码的最小码距为，当且仅当其一致校验矩阵H中任意列线性无关，某列线性相关。2024/7/28566、校验矩阵与最小码距关系 6.2 6.2 线性码线性码6.2.1线性分组码的描述6.2.2线性分组码的译码6.2.3码例与码的重构2024/7/2857译码的概念译码的概念2024/7/2858一、伴随式和错误检测纠错译码的译码成功状态：译码器能够在达到译码码字差错概率最小条件下输出一个确切的码字，即。纠错译码的译码失败状态：译码器不能输出一个确切的码字，通常此时的输出y与检错译码输出相同。2024/7/2859检错译码：译码器输出为当前接收向量r和r是否有差错的标志s，即一、伴随式和错误检测用校验矩阵编码，也用校验矩阵译码：接收到一个接收码字r后，校验H rT=0T或r HT=0是否成立：若关系成立，则认为r是一个码字；否则判为码字在传输中发生了错误；伴随式/监督子/校验子：S=r HT或ST=H rT。二、伴随式和差错图案的关系设发送码字C=(C0,Cn2,Cn1)信道错误图案为E=(E0,En2,En1)其中Ei=0，表示第i位无错；Ei=1，表示第i位有错。接收字r为r=(r0,rn2,rn1)=C+E=(C0+E0,Cn2+En2,Cn1+En1)求接收字的伴随式（接收字用监督矩阵进行检验）ST=H rT=H (C+E)T=H CT+H ET由于H CT=0T，所以ST=H ETS=E HT二、伴随式和差错图案的关系 由此可见，伴随式S与错误图样E之间有确定的线性变换关系。接收端译码器的任务就是从伴随式确定错误图样，然后从接收到的码字中减去错误图样。 举例：(7,3)码接收矢量R的伴随式计算设发送码矢C=1010011，接收码字R1010011，R与C相同。若接收字中有一位错误当码元错误多于1个时定理可纠t个错的2元线性分组码一定满足2024/7/2865三、纠错能力与校验位数的关系四、伴随式纠错译码的通用译码方法（1）按最可能出现的个差错图案，计算相应的伴随式，并构造伴随式差错图案表；（2）对接收向量计算伴随式；（3）查表得；（4）纠错计算。2024/7/28666.2.1线性分组码的描述6.2.2线性分组码的译码6.2.3码例与码的重构2024/7/2867汉明码是汉明于1950年提出的纠一个错误的线性码，也是第一个纠错码。由于它编码简单，因而是在通信系统和数据存储系统中得到广泛应用的一类线性码。汉明码的结构参数：一、汉明码二元Hamming码是一种的完备码，满足其中列向量为全部可能的非零元组。 汉明码监督矩阵构成的两种方式构成H阵的标准形式，H=QIm，其中Im为m阶单位子阵，子阵Q是构造Im后剩下的列任意排列。用这种形式的H阵编出的汉明码是系统码。按m重表示的二进制顺序排列。按这种形式H阵编出的码是非系统码。当发生可纠的单个错误时，伴随式为H阵中对应的列，所以伴随式的二进制数值就是错误位置号，有时这种码译码比较方便。 常常常常见见的的的的线线形分形分形分形分组码组码有重复有重复有重复有重复码码，汉汉明明明明码码，里德，里德，里德，里德- -穆勒穆勒穆勒穆勒码码，戈雷戈雷戈雷戈雷码码（1）汉明明码：二元二元 HammingHamming码是一种码是一种 的完备码，的完备码，满足满足 其中列向量其中列向量 为全部可能的非零为全部可能的非零 元组。元组。 2024/7/2870Hamming码的对偶码是一个线性分组码，称为最大长度码，由于所有非零码字的重量均为，又称为等距码或单形（simplex）码。2024/7/2871例例6.2.4 6.2.4 一个二元（一个二元（7 7，4 4）HammingHamming码的系统码形码的系统码形式的矩阵和校验矩阵分别为式的矩阵和校验矩阵分别为等价的编码方程为等价的编码方程为2024/7/2872伴随式计算方程伴随式计算方程2024/7/2873（2 2）HadamardHadamard码码 HadamardHadamard码是由码是由HadamardHadamard矩阵派生出的一种纠错码矩阵派生出的一种纠错码。 阶实阶实HadamardHadamard矩阵由元素为矩阵由元素为+1+1，-1-1的矩的矩阵递归定义为阵递归定义为 例如例如 2024/7/28742024/7/2875 Hadamard矩阵为正交矩阵，即 中的任意不同两行（列）的点积为0，即 超正交矩阵 ：Hadamard矩阵 中的第1列（全+1列）去掉后由于任两行的点积为-1。 将Hadamard矩阵元素+1/-1映射为0/1，则Hadamard矩阵映射后的行向量为一个二元向量，以这些二元向量的部份或全体就构成标准0/1二元意义上的分组码，并称为Hadamard码。具体的Hadamard码的选择构成有正交码、双正交码和超正交码三种形式。 2024/7/2876（A）正交码：以 的全部行向量的0/1映射向量为码字。 （B）双正交码：以 和- 的全部行向量的0/1映射向量为码字。 2024/7/2877（C）超正交码：以 的全部行向量的0/1映射向量为码字。 可以证明正交码、双正交码和超正交码均是线性分组码。2024/7/2878例例6.2.56.2.5（7 7，3 3）超正交码的超正交矩阵）超正交码的超正交矩阵 和生和生成矩阵成矩阵G G分别为分别为2024/7/2879(3)里德里德-穆勒（穆勒（Reed-Muller）阶码阶码 是一种是一种线性分组码，满足线性分组码，满足2024/7/2880其中各个子矩阵的定义为其中各个子矩阵的定义为 1 1） 为为 矩阵，由全矩阵，由全1 1向量构成。向量构成。2 2） 为为 矩矩阵阵，由由所所有有可可能能的的m m元元组组组成矩阵的列向量。组成矩阵的列向量。3 3） 为为 的的所所有有两两不不同同行行向向量量的的叉叉积积构构成其全部行向量的矩阵。两向量的叉积成其全部行向量的矩阵。两向量的叉积为为4 4） 为为 的的所所有有三三不不同同行行向向量量的的叉叉积积构构成其全部行向量的矩阵。成其全部行向量的矩阵。5 5） 为为 的所有的所有 个不同行向量的叉个不同行向量的叉积积构成其全部行向量的矩阵。构成其全部行向量的矩阵。 r2024/7/2881例例6.2.66.2.6 的 阶RM码的各个子矩阵有2024/7/2882码的对偶码仍是一个Reed-Muller码，为 码。2024/7/2883（4 4）戈雷码）戈雷码二元戈雷二元戈雷二元戈雷二元戈雷码码是一种就是一种就是一种就是一种就纠纠3 3个个个个错错的完的完的完的完备线备线形形形形分分分分组码组码，满满足：足：足：足：n=23n=23 k=12 k=122024/7/2884由于由于因此某种二元（因此某种二元（23,12）码一定可以纠正任）码一定可以纠正任意小于等于意小于等于3 3个差错，所以个差错，所以2024/7/2885 6.3 6.3 循环码循环码 6.3.1 6.3.1循循循循环码环码的多的多的多的多项项式描述式描述式描述式描述6.3.2循环码的生成矩阵循环码的生成矩阵6.3.4多项式运算电路多项式运算电路6.3.3系统循环码系统循环码6.3.5循环码的编码电路循环码的编码电路6.3.6循环码的伴随多项式与检测循环码的伴随多项式与检测6.3.7BCH码与码与RS码码2024/7/2886 循循环环码码组组中中任任一一码码字字循循环环移移位位所所得得的的码码字仍为该码组中的一个码字。字仍为该码组中的一个码字。 在在代代数数理理论论中中，常常用用码码多多项项式式表表示示码码字字。(n,k)循循环环码码的的码码字字，其其码码多多项项式式(以以降降幂幂顺顺序序排列排列)为为 2024/7/2887(7,3)循环码2024/7/28882024/7/28892024/7/2890定义定义：如果一个线性分组码的任意一个码字如果一个线性分组码的任意一个码字c (n元组元组)都是另外一个码字都是另外一个码字c的循环移位的循环移位,称此称此线性分组码为一个循环码线性分组码为一个循环码. 将循环码的码字用多项式将循环码的码字用多项式c(x)，称为码多，称为码多项式（简称码式）表示后，循环码集合表示项式（简称码式）表示后，循环码集合表示为为C(x)2024/7/2891例6.3.2如下确定的如下确定的CA是线性循环码，是线性循环码，CB是是非循环的线性分组码，非循环的线性分组码，CC是非线性的循环码。是非线性的循环码。，2024/7/2892生成多项式及生成矩阵生成多项式及生成矩阵 如果一种码的所有码多项式都是多项式如果一种码的所有码多项式都是多项式g(x)的的倍倍式式，则则称称g(x)为为该该码码的的生生成成多多项项式式。在在(n,k)循循环环码码中中任任意意码码多多项项式式A(x)都都是是最最低低次次码多项式的倍式。码多项式的倍式。 因因此此，循循环环码码中中次次数数最最低低的的多多项项式式( (全全0 0码码字字除除外外) )就就是是生生成成多多项项式式g g( (x x) )。可可以以证证明明，g g( (x)是是常常数数项项为为1的的r=n-k 次次多多项项式式，是是xn+1 的一个因式。的一个因式。 2024/7/2893定理：定理：( (n,kn,k) )循循循循环码环码C( x)C( x)中存在唯一的一个非零的，中存在唯一的一个非零的，中存在唯一的一个非零的，中存在唯一的一个非零的，首一的和最低次首一的和最低次首一的和最低次首一的和最低次为为r r（rnrn）的）的）的）的码码多多多多项项式式式式g(x)g(x)满满足：足：足：足：g(xg(x)=)=g gr-1r-1x xr r+ +g gr-1r-1x xr-1r-1+.+g+.+g1 1X X+g+g0 0 g g0 0 0 0r=n-kr=n-k并且并且并且并且A(x)A(x)是是是是码码式当且式当且式当且式当且仅仅当当当当c(x)c(x)是是是是g(x)g(x)的倍式的倍式的倍式的倍式由上述定理确定的码式由上述定理确定的码式g(x)g(x)称为循环码称为循环码(n,k)(n,k)的的生成多项式生成多项式. . 2024/7/2894 因因此此(n,k)(n,k)循循环环码码的的构构造造是是如如何何构构造造生生成成多多项式项式g(x)g(x)。 循环码由生成多项式的倍式组成循环码由生成多项式的倍式组成2024/7/2895定理：定理： g(x)是（是（n,k）循）循环码的生成的生成多多项式，式，当且当且仅当当g(x)是是xn-1的的r=n-k次因式。次因式。2024/7/28962024/7/28972024/7/28982024/7/2899(n,k)(n,k)循循循循环码环码的生成矩的生成矩的生成矩的生成矩阵为阵为2024/7/28100循环码的生成矩阵常用多项式的形式来表示循环码的生成矩阵常用多项式的形式来表示 其中其中 即即 2024/7/28101例如例如(7,3)循环码，循环码，n=7, k=3, r=4, 其生成多项式其生成多项式及生成矩阵分别为及生成矩阵分别为 2024/7/28102监督多项式及监督矩阵监督多项式及监督矩阵 h(x)是是常常数数项项为为1的的k次次多多项项式式，称称为为监监督督多多项式项式。同理，可得监督矩阵。同理，可得监督矩阵H 2024/7/28103是是h(x)的逆多项式。例如的逆多项式。例如(7，3)循环码，循环码，其中其中 则则 2024/7/28104(n,k)循环码的校验矩阵为循环码的校验矩阵为2024/7/281052024/7/281066.3.3 6.3.3 系统循环码系统循环码循循循循环码环码的系的系的系的系统码码统码码式式式式为为2024/7/28107循循环环码码中中的的所所有有码码多多项项式式都都可可被被g(x)整整除除，根根据据这这条条原原则则，就就可可以以对对给给定定的的信信息息进进行行编编码码。用用xr乘乘m(x)，得得到到xrm(x)的的次次数数小小于于n。用用g(x)去去除除xrm(x)，得得到到余余式式p(x), p(x)的的次次数数必必小小于于g(x)的的次次数数，即即小小于于(n-k)。将将此此余余式式加加于于信信息息位位之之后后作作为为监监督督位位，即即将将p(x)与与xrm(x)相相加加，得得到到的的多多项项式式必必为为一一码码多多项项式式，因因为为它它必必能能被被g(x)整整除除，且且商商的次数不大于的次数不大于(k-1)。循环码的码多项式可表示为。循环码的码多项式可表示为 其其中中，xrm(x)代代表表信信息息位位，p(x)是是xrm(x)与与g(x)相相除除得到的余式，代表监督位。得到的余式，代表监督位。 2024/7/28108编码方法和电路编码方法和电路 在在编编码码时时，首首先先要要根根据据给给定定的的(n,k)值值选选定定生生成成多多项项式式g(x)，即即应应在在xn+1的的因因式式中中选选一一r=n-k次次多多项项式式作作为为g(x)。设设编编码码前前的的信信息息多多项式项式m(x)为为 2024/7/281092024/7/28110(7,3)循环码编码电路循环码编码电路 编编码码电电路路的的主主体体由由生生成成多多项项式式构构成成的的除除法法电电路路 ， 再再 加加 上上 适适 当当 的的 控控 制制 电电 路路 组组 成成 。g(x)=x4+x3+x2+1 时时，(7,3)循循环环码码的的编编码码电电路路如如图图 所示。所示。 2024/7/28111(7,3)循环码的编码过程循环码的编码过程 2024/7/2811210.4.4 译码方法和电路译码方法和电路 接接收收端端译译码码的的目目的的是是检检错错和和纠纠错错。由由于于任任一一码码多多项项式式A(x)都都应应能能被被生生成成多多项项式式g(x)整整除除，所所以以在在接接收收端端可可以以将将接接收收码码组组B(x)用用生生成成多多项项式式去去除除。当当传传输输中中未未发发生生错错误误时时，接接收收码码组组和和发发送送码码组组相相同同，即即A(x)=B(x)，故故接接收收码码组组B(x)必必定定能能被被g(x)整整除除。 若若码码组组在在传传输输中中发发生生错错误误，则则B(x)A(x)，B(x)除除以以g(x)时时除除不不尽尽而而有有余余项项。在在接接收收端端采采用用译译码码方方法法来来纠纠错错自自然然比比检检错错更更复复杂杂。同同样样，为为了了能能够够纠纠错错，要要求求每每个个可可纠纠正正的的错错误误图图样样必必须须与一个特定余式有一一对应关系。与一个特定余式有一一对应关系。 2024/7/28113(7,3)循环码译码电路循环码译码电路 2024/7/281146.3.4 6.3.4 多项式运算电路多项式运算电路因为多项式因为多项式因为多项式因为多项式表示时间序列表示时间序列所以多项式的计算表现为对时间序列的操作.2024/7/28115多项式多项式a(x)与与b(x相加电路相加电路2024/7/28116 a(x)与与g(x)的一般乘法电路的一般乘法电路2024/7/281172024/7/281186.3.16.3.16.3.16.3.1循环码的多项式描述循环码的多项式描述循环码的多项式描述循环码的多项式描述6.3.26.3.26.3.26.3.2循环码的生成矩阵循环码的生成矩阵循环码的生成矩阵循环码的生成矩阵6.3.36.3.36.3.36.3.3系统循环码系统循环码系统循环码系统循环码6.3.46.3.46.3.46.3.4多项式运算电路多项式运算电路多项式运算电路多项式运算电路6.3.5 循环码的编码电路循环码的编码电路6.3.66.3.66.3.66.3.6循环码的伴随多项式与检测循环码的伴随多项式与检测循环码的伴随多项式与检测循环码的伴随多项式与检测6.3.7BCH6.3.7BCH6.3.7BCH6.3.7BCH码与码与码与码与RSRSRSRS码码码码2024/7/281191.1.非循环码编码器非循环码编码器 根据根据多项式乘法电路和循环码码式是生多多项式乘法电路和循环码码式是生多多项式乘法电路和循环码码式是生多多项式乘法电路和循环码码式是生多项式倍式原理，多项式乘法电路项式倍式原理，多项式乘法电路项式倍式原理，多项式乘法电路项式倍式原理，多项式乘法电路( ( ( (图图图图6.3.4) 6.3.4) 6.3.4) 6.3.4) 是循环是循环是循环是循环码的非系统码电路，又称为码的非系统码电路，又称为码的非系统码电路，又称为码的非系统码电路，又称为循环码乘法编码电路循环码乘法编码电路图图 6.3.46.3.42024/7/281202. 2. 系统编码电路系统编码电路循循循循环码环码系系系系统编码电统编码电路由乘法路由乘法路由乘法路由乘法电电路，求余式路，求余式路，求余式路，求余式电电路以及路以及路以及路以及加法开关加法开关加法开关加法开关电电路路路路组组成成成成, ,如如如如图图6.3.146.3.14所示所示所示所示, ,电电路工作路工作路工作路工作过过程如程如程如程如表表表表6.3.26.3.2所示所示所示所示. .图图 6.3.142024/7/28121表表 6.3.2 6.3.2 循环码系统码编码电路工作过程循环码系统码编码电路工作过程2024/7/281226.3.1 6.3.1 6.3.1 6.3.1 循环码的多项式描述循环码的多项式描述循环码的多项式描述循环码的多项式描述6.3.2 6.3.2 6.3.2 6.3.2 循环码的生成矩阵循环码的生成矩阵循环码的生成矩阵循环码的生成矩阵6.3.3 6.3.3 6.3.3 6.3.3 系统循环码系统循环码系统循环码系统循环码6.3.4 6.3.4 6.3.4 6.3.4 多项式运算电路多项式运算电路多项式运算电路多项式运算电路6.3.5 6.3.5 6.3.5 6.3.5 循环码的编码电路循环码的编码电路循环码的编码电路循环码的编码电路6.3.6 6.3.6 循环码的伴随多项式与检测循环码的伴随多项式与检测6.3.7 BCH6.3.7 BCH6.3.7 BCH6.3.7 BCH码与码与码与码与RSRSRSRS码码码码2024/7/28123循循循循环码环码的的的的译码译码分成分成分成分成检错译码检错译码与与与与纠错译码纠错译码两两两两类类. .1.1.检错译码原理检错译码原理2024/7/281242.2.纠错译码纠错译码 循环码的纠错译码要达到码的最小距离依赖于循环码的纠错译码要达到码的最小距离依赖于具体的循环码的结构具体的循环码的结构.2024/7/281256.3.16.3.16.3.16.3.1循环码的多项式描述循环码的多项式描述循环码的多项式描述循环码的多项式描述6.3.26.3.26.3.26.3.2循环码的生成矩阵循环码的生成矩阵循环码的生成矩阵循环码的生成矩阵6.3.36.3.36.3.36.3.3系统循环码系统循环码系统循环码系统循环码6.3.46.3.46.3.46.3.4多项式运算电路多项式运算电路多项式运算电路多项式运算电路6.3.56.3.56.3.56.3.5循环码的编码电路循环码的编码电路循环码的编码电路循环码的编码电路6.3.66.3.66.3.66.3.6循环码的伴随多项式与检测循环码的伴随多项式与检测循环码的伴随多项式与检测循环码的伴随多项式与检测6.3.7 BCH6.3.7 BCH码与码与RSRS码码2024/7/28126BCHBCH码码是一是一是一是一类类能能能能够够先确定先确定先确定先确定纠错纠错能力能力能力能力t t，然后，然后，然后，然后设计码长设计码长和生和生和生和生成多成多成多成多项项式的式的式的式的码码。对对于任意的整数于任意的整数于任意的整数于任意的整数mm和可达到和可达到和可达到和可达到纠错纠错数数数数t t，都可以构造出一个都可以构造出一个都可以构造出一个都可以构造出一个设计设计距离距离距离距离为为d d0 0的二元本原的二元本原的二元本原的二元本原BCHBCH码满码满足：足：足：足：n=2n=2mm-1,r=n-kmt,d-1,r=n-kmt,dminmindd0 0=2t+1=2t+12024/7/28127RSRS码码是多元是多元是多元是多元BCHBCH码码的一个子的一个子的一个子的一个子类类，码码字向量字向量字向量字向量的每个分量可以表示的每个分量可以表示的每个分量可以表示的每个分量可以表示 为为mm比特，其基本参数比特，其基本参数比特，其基本参数比特，其基本参数为为：码长码长：n=2n=2mm-1( -1( 符号符号符号符号)=m(2)=m(2mm-1)-1)（比特）（比特）（比特）（比特）校校校校验验位位位位长长： r=n-k=2t(r=n-k=2t(符号符号符号符号)=m)=m 2t2t其中其中其中其中t t为为RSRS码码可以可以可以可以纠纠正的差正的差正的差正的差错错符号数符号数符号数符号数. .2024/7/281286.4 6.4 卷积码卷积码 6.4.26.4.2卷积码的多项式描述卷积码的多项式描述 6.4.36.4.3卷积码的状态转移图与格描述卷积码的状态转移图与格描述6.4.46.4.4维特比（维特比（ViterbiViterbi）译码算法）译码算法6.4.16.4.1卷积码的矩阵描述卷积码的矩阵描述2024/7/281296.4.1 卷积码的矩阵描述卷积码的矩阵描述6.4.2卷卷积码的多的多项式描述式描述6.4.3卷卷积码的状的状态转移移图与格描述与格描述6.4.4维特比（特比（Viterbi）译码算法算法2024/7/28130卷积码编码卷积码编码：当前输出 不仅与当前输入消息 相关，还与此前输入的 个消息 相关， 二元线性卷积码二元线性卷积码： 是仅由模二加运算组成的布尔函数布尔函数 2024/7/28131的长度恒为 比特， 的长度恒为长度恒为 n比特，均称为一段 2024/7/28132任意一输入段 与输出段 的关系都是一个特殊的 线性分组码的编码线性分组码的编码 2024/7/28133卷积编码的离散卷积表达式卷积编码的离散卷积表达式卷积码的记忆长度（段）： 约束长度（段）： 或或 2024/7/28134结尾处理结尾处理：额外输入 段无效的0数据 比特，保证编码器回到全全0 0的初态的初态 有限 段长消息的编码速率为： 渐近编码速率渐近编码速率： 2024/7/28135卷积码的生成矩阵卷积码的生成矩阵 二元线性 卷积码 定义定义2024/7/28136基本生成矩阵基本生成矩阵 ：生成矩阵 的前 行， 列组成的子矩阵 第 个生成元 ： 的第 行，描述 了所有各段输入中的第 位输入比特 对所有输出比特输出比特的影响 2024/7/28137将 的元素 的列下标 表示为表示为 则输入移位寄存器移位寄存器中的第 段的第 位输入比特 参与第 位输出比特的编码 不参与第 位输出比特的编码 2024/7/28138卷积码卷积码的子生成元或生成序列生成序列： 元组 2024/7/28139线性卷积码的矩阵（或向量）描述描述： 2024/7/28140生成矩阵 ，基本生成矩阵基本生成矩阵 ，生成序列（生成元） 系统卷积码系统卷积码：卷积码每段输出的 位中有 位（如当前 位）恒等于每段输入的 位 2024/7/28141其中 均为均为 矩阵。 2024/7/28142由于对每个独立的输入段输入段（每段 比特，共3段）分别有分别有 基本生成矩阵 为 ，生成矩阵为 ，生成元为 ，生成 2024/7/28143序列为序列为 2024/7/281446.4.1卷卷积码的矩的矩阵描述描述6.4.2 6.4.2 卷积码的多项式描述卷积码的多项式描述6.4.3卷卷积码的状的状态转移移图与格描述与格描述6.4.4维特比（特比（Viterbi）译码算法算法2024/7/281456.4.2 6.4.2 卷积码的多项式描述卷积码的多项式描述消息段序列的多项式表示消息段序列的多项式表示2024/7/28146多项式描述更直接的描述了描述了（二元） 卷积码作为一个 （比特）入， （比特） 出的编码关系编码关系 编码输出段序列的多项式表示编码输出段序列的多项式表示2024/7/28147线性 卷积码的多项式表达式为 线性 卷积码的多项式矩阵 ：为 的多项式矩阵 又称又称 为卷积码的延迟算子生成矩阵延迟算子生成矩阵。 2024/7/28148定理定理 线性 卷积码的多项式生成矩阵 对 满足 的 幂次项系数幂次项系数等于 生成序列 的第 个分量， 1 12024/7/28149即的最大次数最大次数等于卷积码的记 忆长度，即22024/7/28150例例6.4.56.4.5 前述例（2,1,2）卷积码重画如图 2024/7/281516.4.1卷卷积码的矩的矩阵描述描述6.4.2卷卷积码的多的多项式描述式描述6.4.3 6.4.3 卷积码的状态卷积码的状态 转移图与格描转移图与格描述述6.4.4维特比（特比（Viterbi）译码算法算法2024/7/28152卷卷卷卷积码积码与分与分与分与分组码组码的的的的明明显区区别是卷是卷是卷是卷积码编积码编码码器要存器要存器要存器要存储储mm段信息，段信息，段信息，段信息，这这些信息数据既要些信息数据既要些信息数据既要些信息数据既要因新的因新的因新的因新的输输入而改入而改入而改入而改变变，又要影响当前的，又要影响当前的，又要影响当前的，又要影响当前的编码编码 输输出，因此称存出，因此称存出，因此称存出，因此称存储储表达表达表达表达这这些数据的参量些数据的参量些数据的参量些数据的参量为为卷卷卷卷积编码积编码器的内部状器的内部状器的内部状器的内部状态态，简称状称状态。2024/7/28153状态状态：既要因新的输入而改变，又要影响当前的编码输出的数据编码输出的数据。卷积编码器有效的存贮单元存贮单元数为2024/7/28154其中为每个输入移位寄存器的有效级数有效级数（寄存单元数）。因此二元卷积码的状态变量记为状态向量或简记为简记为2024/7/28155状态数状态数：二元卷积码共有个不同的状态，记为状态转移状态转移：当状态为（或）时，输入段（或）产生编码输出段编码输出段（或），并使该状态改变（称为转移）到新的状态（或）。2024/7/28156转移分支转移分支： 到 的转移过程，记为 （ ， ）或（ ， ），并标 记为 或 分支为有向边描述卷积码的所有不同状态 转移的有向图 状态转移图：以状态为结点，转移 2024/7/28157状态转移方程状态转移方程：与的关系输出方程输出方程： 与的关系2024/7/28158尽管卷积码有个状态，但是由于每段的输入为比特只有种状态的变化，每个状态只转移到个状态的某个子集（个状态）中去，每个状态也只能由某个状态的状态子集转移状态子集转移而来。2024/7/28159例例 6.4.106.4.102024/7/28160状态转移图（闭合形）状态转移图（闭合形） 2024/7/28161状态转移图（开放形）状态转移图（开放形）状态转移方程和输出方程分别为 2024/7/28162卷积编码器工作过程：卷积编码器工作过程： * 卷积编码器工作初态为 （全0状态）* 消息段序列 产生输出段序列* 消息段序列产生状态序列2024/7/28163栅格图或篱笆图栅格图或篱笆图：开放形的状态转移图按时间顺序级联编码路径编码路径：状态序列 在栅格图中形成一条有向路径一个卷积码码字一个卷积码码字：有向路径始于全0状态 ，又终于 时的一条有向路径对于 的卷积码，常用实线表示时输入产生的转移分支，用虚线表示时输入产生的转移分支2024/7/28164例 6.4.13 前述例6.4.1（2，1，2）码的栅格图及几条路径例 2024/7/28165路径A消息A（100）输出A（111011）路径B消息B（10110）输出B（1110000101）路径C 消息C（110100） 输出C（11 01 10 01 11）2024/7/28166（1）卷积码的一个分支或转移是栅格图（或状态图）中接续状态的容许连接。（2） 卷积码的一条路径是可容许连接的分支串。（3）卷积码的码字是始于零状态并首次终于零状态的路径。结论结论2024/7/281676.4.16.4.1卷积码的矩阵描述卷积码的矩阵描述6.4.26.4.2卷积码的多项式描述卷积码的多项式描述6.4.36.4.3卷积码的状态转移图与格描述卷积码的状态转移图与格描述6.4.4 维特比（特比（Viterbi）译码算法算法 2024/7/28168卷积码的最大似然译码的基本方法卷积码的最大似然译码的基本方法： 寻找一条路径 使似然值（概率）或对数似然值最大* 对应于发送码字或路径的接收段序列为* 各个码字假设为等概发送 2024/7/28169对于无记忆信道和有限 段接收序列，最大似然译码是寻求一条路径 ，使得其中 表示一条段记号从 到 的 段长路径2024/7/28170分分支支似似然然值值：第时刻连接至状态的分支的分支度量值，简记连接至连接至 最大累积度量值最大累积度量值 ：路径的分支度量值之和的最大值，简记定义定义定义定义2024/7/28171连接至状态连接至状态 幸幸存存路路径径：具有最大累积度量值的路径的幸存分支：的幸存分支： 的最后分支显然每个状态有 个可能的分支度量，每个状态只有一条幸存路径，每个时刻有 个可能的分支度量，每个时刻有 条幸存路径定义定义2024/7/28172有限长度有限长度 的的ViterbiViterbi算法算法： （1.1）段计数=0（1.2）最大累积度量值（1.3）幸存路径（1）初始化2024/7/28173（2）迭代 （2.1）接收序列段（2.2）段计数加1，（2.3）对 重复进行（2.3.1）对分别计算分支度量值（2.3.2）对 分别计算累积度量值（2.3.3）计算最大累积度量值（2.3.4）形成第 状态 的幸存分支，并存贮到达此状态的幸存路径2024/7/28174（3）输出 （3.1）若 ，则返回第（2）步迭代（3.2）若 ，则求最大累积度量值为的幸存路径 并输出该条路径对应的消息序列 。 2024/7/28175例例6.4.146.4.14 对例6.4.1非系统（2，1，2）卷积码的Viterbi译码例 设编码器输出为全0比特序列，经过BSC，接收序列 为* 在Viterbi译码的极小（大）计算中，如果有两条以上路径的累积路径值相等，则任选一条为幸存路径* 当差错图案是可纠正的情形时，Viterbi译码过程会产生路径合并现象 =（10 00 01 00 00 00 00 ）2024/7/281762024/7/281772024/7/281782024/7/281792024/7/281802024/7/28181自由距离自由距离 ：所有非零码字路径的最小Hamming重量，即其中 是长为 段的非零消息， 是对应的卷积编码码字。例例6.4.156.4.15对例6.4.1非系统（2，1，2）码其自由距离 =5定义定义2024/7/28182同学们同学们来学校和回家的路上要注意安全同学们同学们来学校和回家的路上要注意安全