6 信道编码

null第六章　信道编码第六章　信道编码6.1　信道编码的概念 6.2　线性分组码 6.3　循环码 6.4　卷积码6.1　信道编码的概念*6.1　信道编码的概念6.1.1　信道编码的作用与分类 6.1.2　编码信道 6.1.3　检错与纠错原理 6.1.4　检错与纠错方式和能力6.1.1　信道编码的作用与分类广义的信道编码是为特定信道传输而进行的传输信号的设计与实现，常见的信道编码有以下几种： 描述编码：用于描述特定的数据信号，如 ASCII 码、不归零(NRZ)码、格雷(Gray)码 约束编码：用于对信号特性进行约束，如用于减少直流分量的HDB-3码，用于相位与同步检测的巴克(Brarker)码 扩频编码：用于扩展信号频谱为近似白噪声谱以满足某些相关特性，如 m 序列、戈尔德(Gold)序列 纠错编码：用于检测与纠正信号传输过程中因噪声干扰导致的差错，如重复码、循环码、BCH 码、卷积码 通信的目的是要把对方不知道的信息及时可靠地(有时是秘密地)传送给对方，纠错编码是提高信号传输可靠性的是主要找施之一；因此本章主要学习纠错编码*6.1.1　信道编码的作用与分类6.1.1　信道编码的作用与分类对于无噪无损信道只要对信源进行适当的编码，总能以信道容量无差错的传递信息；但是一般信道总会存在噪声和干扰，信息传输会造成损失 信道编码的目的是改善通信系统的传输质量。由于实际信道存在噪声干扰，使发送的码字与信道传输后接收的码字之间存在差异，这种差异称为差错 一般而言信道噪声、干扰越大，码字产生差错的概率也越大 在有噪信道中怎样才能使消息通过传输后发生的差错最少 差错概率与那些因素有关 有无 办法 鲁班奖评选办法下载鲁班奖评选办法下载鲁班奖评选办法下载企业年金办法下载企业年金办法下载 控制 能控制到什么程度 在有噪信道中无差错传输可以达到的最大信息传输率？*6.1.1　信道编码的作用与分类差错信道随机差错信道：在无记忆信道中，噪声独立随机地影响每个传输码元，因此接收的码元序列中的错误是独立随机出现的；太空信道、卫星信道、同轴电缆、光缆信道以及大多数视距微波接力信道均属于这一类型信道 突发差错信道：在有记忆信道中，噪声干扰的影响往往是前后相关的，错误会成串出现；典型的有短波信道、移动通信信道、散射信道以及受大的脉冲干扰和串话影响的明线和电缆信道，甚至还包括在磁记录中，划痕、涂层缺损将造成成串的差错 混合差错信道：有些实际信道既有独立随机差错也有突发性成串差错，其差错是这两种差错的综合 为降低平均差错率，可先对消息进行编码再送入信道传送，这种为降低平均差错率进行的编码称为信道编码*差错信道信道编码的作用信道编码的基本思想是根据一定的规律在待发送的信息码中加入一些多余的码元(校验码元)，以保证传输过程的可靠性 在带宽固定的信道中，总的信息传输率是固定的，由于信道编码增加了数据量，其结果只能是以降低传送有用信息码率为代价，所以增加的冗余符号越多，检错和纠错能力就越强，但传输效率越低 信道编码的任务是构造出以最小多余度代价换取最大抗干扰性能的“好码”，使系统具有一定的纠错能力和抗干扰能力，降低误码率 信源编码与信道编码的不同： 信道编码是为了消除噪声和干扰的影响，以提高传输可靠性作为主要考虑因素，通过增加冗余码元来实现，一般采用定长编码方法 信源编码是为改造信源的属性，通过去冗余提高信源的信息含量效率以提高传输效率，通常采用变长编码方法*信道编码的作用信道编码的分类按对信息码元的处理方法分 分组码：将 k 个信息码元划分成 1 组，然后由这 k 个码元按照一定的规则产生 r 个校验码元，从而组成长度为 k + r 的码字；在分组码中，校验码元仅校验本码字中的信息码元；分组码一般用符号 ( n, k ) 表示，并且将分组码的结构 规定 关于下班后关闭电源的规定党章中关于入党时间的规定公务员考核规定下载规定办法文件下载宁波关于闷顶的规定 为前面 k 位为信息位，后面附加 r 个校验位 循环码：的特点是，若将其全部码字分成若干组，则每组中任一码字的码元循环移位后仍是这组的码字 非循环码：任意一个码字中码元循环移位后不一定再是该码中的码字 卷积码：每组的校验码元不但与本码组的信息码元有关，而且还与前面若干组信息码元有关，即不是分组的特点，而是每个校验码元对它的前后码元都实行校验，前后相连，因此有时也称为连环码*信道编码的分类信道编码的分类(续)信道编码的分类(续)*按码的结构(校验码元与信息码元的关系)分: 线性码：校验码元与信息码元之间是线性关系，可用一组线性代数方程联系起来 非线性码：校验码元与信息码元之间是非线性关系 按校验码字对差错的处理能力分 检错码：仅能检测误码 纠错码：可纠正误码 纠删码：兼纠错和检错能力 按抗干扰模式分 纠随机差错码 纠突发差错码 纠混合差错码 纠同步差错码按信息码元在编码后是否保持原形式不变 系统码：信息码元与监督码元在分组内有确定位置，编码后的信息码元保持不变 非系统码：信息位打乱，与编码前不同 按编、译码理论所用数学工具分 代数码：近世代数 几何码：投影几何 算术码：数论和高等算术 组合码：排列组合和数论 6.1.2　编码信道*6.1.2　编码信道转移概率 p ( r | c ) 描述了 2 进制信道噪声干扰程度2 进制信道：码字 c 和接收向量 r 均由二元序列表示的编码信道无记忆 2 进制信道：对于任意的 n，均有： 无记忆 2 进制对称信道(BSC)：发生差错的概率相同的无记忆 2 进制信道，即：若噪声是白噪声，则 2 进制信道可等效为一个 BSCBSC 的输入/输出关系也可表示为 ：2 进制硬判决信道null*差错图案：码字 c 的每一码元经过编码信道由于噪声或干扰引起的差错序列，即：无记忆编码信道的每一个二元符号输出也可以用多个比特表示，理想情况下为实数(无穷多个比特)，则无记忆二进制信道又称为 2 进制软判决信道译码规则*译码规则同一个信道，可以有多种译码规则；在所有可能的译码规则中，应选择一个使平均差错率最小者作为译码规则共有 4 种译码规则平均差错率*平均差错率译码正确的概率： 译码错误的概率： 平均译码正确概率： 平均译码错误概率(平均差错率)： 当信道输入是等概率时： null解：信道输入概率矩阵、信道转移概率矩阵和联合概率矩阵为：*求四种译码规则所对应的平均差错率译码规则 译码规则 译码规则 译码规则 最佳译码规则采用穷举法可以构造给定信道的所有译码规则，通过计算求出平均差错率最小的译码规则，这就是最好的译码规则，但这样做的工作量非常大 最佳译码规则：使平均差错率达到最小的译码规则*最佳译码规则最大后验概率译码规则最大联合概率译码规则null解：信道输入概率矩阵、信道转移概率矩阵和联合概率矩阵为：*求最佳译码规则两种方法得到相同的结果最大似然译码规则如果仅知道信道的统计特性而不知道信源的统计特性时，可只按最大转移概率来确定译码规则*最大似然译码规则最大似然译码规则最大似然译码规则的平均差错率不一定是最小，因此不一定是最佳码，但容易找到，只要知道信道的统计特性即可 由于信源输出序列在进入信道前已进行了信源编码(主要作用之一是使输出符号概率均匀化)，经过有效的信源编码，信源编码器的输出码元概率分布已经均匀化，因此信道的输入分布近似为等概率分布 可以证明当输入等概率分布时，最大似然译码规则与最佳译码规则是等价的6.1.3　检错与纠错原理检纠错的目的在于从信道的输出信号序列 r 判断 r 是否可能是发送的码字 c，或者纠正导致 r 不等于 c 的差错 由于 BSC 信道的消息 m 和码字 c 均是 2 进制序列，且 c 中含有具有检纠错功能的校验码，因此 c 的长度必然大于 m 的长度*6.1.3　检错与纠错原理对于信道编码而言，消息 m 实质上是信源 X 的一系列信源编码码元所构成的长为 k 的 2 进制序列 信道编码一般采用等长编码，所有码字的长度均相等；实际上，码字c 的长度等于消息 m 与校验位的长度和当消息足够长时，信道的编码效率为： 描述了信息位在码字中的比重偶(奇)校验法*偶(奇)校验法显然 c 中必含有偶数个“1”，确定偶校验位 q 的编码方程为通过校验方程的计算结果可得： 1： m 中一定有奇数个错误 0： m 中可能有奇数个错误对阵列消息进行垂直和水平校验及总校验重复消息位对同一信源符号进行多次重复编码，如果重复次数为 n，则信息传输率为 1/n n 重复码传送 1 比特的消息(k = 1)只有两个正确的码字：*重复消息位n 重复码可以检测出消息 m 中任意小于 n 的差错就信道本身而言，这样的信道是很好的 　　如不进行信道编码，由极大似然译码规则和转移概率矩阵可得：null*信道的转移概率矩阵为：按极大似然译码规则得： 3 重复码的平均差错率比不进行信道编码降低了 2 个数量级，译码时能纠正一位码元错误；增加重复次数会使平均差错率进一步降低，但代价是信息传输率的下降0 多译为0，1多译为1等重码(定比码)*等重码(定比码)码字重量 w ( c )：码字中非“0”符号的个数；对于 2 进制码，则为“1”的个数 等重码的码字重量恒为常数 W，即等重码是由全体码字重量恒等于 W 的 s 维向量组成：例如用于表示十进制数 0～9 的 5 中取 3 等重码的码表为：可以验证：5 中取 3 等重码可以检测出全部奇数位差错和部分偶数位差错 5 中取 3 等重码的信息传输率为：6.1.4　检错与纠错方式和能力前向纠错(FEC)：发送端信息经纠错编码后再进行传送，接收端通过纠错译码自动纠正传递过程中的错误；这里的“前向”指纠错过程在接收端独立进行不存在信息的反馈 自动请求重发(ARQ)：发送端发送检错码，接收端通过检测接收码是否符合编码规律来判断该码是否存在差错；如果判定该码有错，则通过反向信道通知发送端重发全部或部分该码字；如此反复，直到接收端认为正确接收为止 混合纠错(HEC)：前向纠错与自动请求重发的结合；发送端发送的码同时具有检错和纠错的能力；接收端收到码字后检查差错情况 如果差错不超过码的纠错能力，则自动进行纠错 如果判断码字的差错数量已超过码的纠错能力，此时通过反馈信道给发送端发一个要求重发的信息 狭义信息反馈系统(IRQ)：接收端将收到的消息原封不动地反馈到发送端，由发送端将反馈的消息进行比较，如发现错误就再次重传*6.1.4　检错与纠错方式和能力检错与纠错能力译码规则要求采用选多译码方法，即将接收序列译为与之最相似的输入系列(码字)；通常用汉明距离来定量描述这种相似程度，它也是二元编码间差异的常用测度 汉明距离：两个长度相等的码字(均为 n 维二元向量) u 和 v 中对应码位上的不同码元符号的个数，简称为码距*检错与纠错能力非负性：d (u, v )  0，当且仅当 u = v 时等号成立 对称性：d (u, v ) = d ( v, u )   满足三角不等式：d (u, v ) + d (v, w )  d (u, w )汉明距离与码字重量的关系：若 c, ci , cj 均为 n 长的二元码字：检错与纠错能力(续)汉明球：所有与码字 c 的汉明距离不超过 R 的 n 维向量的全体*检错与纠错能力(续)一个纠错码的每个码字均可形成一个汉明球，要能够纠正不多 于 R 位的差错，则纠错码的所有汉明球均不能相交最小汉明距离 dmin 表示了码的纠错能力，是衡量码性能的重要参数；dmin 越小，说明其中有些码字受干扰后越容易变为另外一个码字，译码时出错的概率就越大 因此，进行信道编码时，应使码的最小汉明距离 dmin 大一些为好，同时也可以通过汉明距离确定相应的译码规则最小汉明距离译码规则对于 BSC 信道，由于其无记忆性，因此：*最小汉明距离译码规则检错与纠错能力(续)*检错与纠错能力(续)纠错码 C 可以检测出 L 个差错同时纠正其中的 T 个差错，其中：请同学们自行推导6.2　线性分组码*6.2　线性分组码6.2.1　线性分组码的描述 6.2.2　线性分组码的译码 6.2.3　码例与码的重构 汉明码 哈达码 里德－穆勒码 戈雷码 码的重构6.2.1　线性分组码的描述 分组码的编码包括两个基本步骤 首先将信源的输出序列分为 k 位一组的信息组 然后信道编码器根据一定的编码规则将 k 位信息组变换成n 个码元的码字 信息组和码字用矩阵表示如下：*6.2.1　线性分组码的描述 通常对编码器附加一个线性约束条件，使得码字的校验位与信息位之间呈线性关系，这种码称为 (n, k ) 线性分组码 采用线性分组码进行信道编码，就是给已知信息组按预定规则添加校验码元以构成码字。在 k 个信息元之后附加 r = n - k 个校验码元，使每个校验码元是其中某些信息码元的和线性分组码的描述*线性分组码的描述线性方程组的后 4 个方程确定了由信息码元得到校验码元的规则，这 4 个方程称为校验方程。由于所有码字都按同一规则确定，因此又称为一致校验方程，所得到的校验码元称为一致校验码元 上述这种编码方法称为一致校验编码。由于一致校验方程是线性的，亦即校验码元和信息码元间是线性运算关系，所以由线性校验方程所确定的分组码是线性分组码 利用上式每给出一个 3 位的信息组，就可编出一个码字，结果如表所示线性分组码的生成矩阵 和一致校验矩阵在 (n, k ) 线性分组码中，编码器输出的码字可以由如下方程组来决定：*线性分组码的生成矩阵 和一致校验矩阵 则方程组的矩阵表示为：c = mG 所有满足上式码字(n 维向量)的全体构成 (n, k) 线性分组码 C生成矩阵生成矩阵 G 是一个 k 行 n 列(n  k)秩为 k 的矩阵，它 建立了消息向量与码字的一一对应关系，它起着编码器的变换作用 G 的每一行都是一个码字，分别是 k 维消息向量组 1000, 01000, , 00010, 00001 所对应的码字m 是任意 k 维消息向量运算：模 2 加、模 2 乘线性分组码的生成矩阵的性质*线性分组码的生成矩阵的性质封闭性：任意两个码字的和仍是一个码字，即：线性分组码的最小码距等于最小非零码字重量：(n, k ) 线性分组码实质上是 n 维 n 长向量构成的线性空间中的一个 k 维线性子空间系统码*系统码生成矩阵 G 的选择不是惟一的；如下面的G1 和 G2 都可作为同一个 (6, 3) 码的生成矩阵，所对应的码字如右表所示：系统码的编码器仅需存储 k  (n - k) 个数字(非系统码要存储 k  n 个数字)，译码时仅需对前 k 个信息位纠错即可恢复信息；可见系统码的编码和译码比较简单，而性能与非系统码一样，所以系统码得到了十分广泛的应用虽然二者用了不同形式的生成矩阵，却都是 (6, 3) 线性分组码，因此它们的检错和纠错能力是一样的，但是 G2 生成的码，其前 k 位与消息码完全相同，这种码称为系统码，其生成矩阵和一致校验矩阵分别记为 Gs , Hs线性分组码的生成矩阵 和一致校验矩阵的相互转换系统码的生成矩阵可用分块矩阵表示为*线性分组码的生成矩阵 和一致校验矩阵的相互转换在系统码字 c 中，前 k 位是信息位 m，后 r 位为码字的校验位 q，并且 c = mGs，所以： 对于 2 进制编码 H 矩阵的每一行都代表一个校验方程线性分组码的生成矩阵 和校验矩阵的关系*线性分组码的生成矩阵 和校验矩阵的关系由于 G 的每一行都是一个码字，所以 G 的每一行 c i 都满足：在码字集合不变的前提下，给定任何一个线性分组码，通过其生成矩阵 G 实施行初等变换，均可以转换为某个系统码当且仅当线性分组码一致校验矩阵 H 中任意 d - 1 个列线性无关而某 d 列线性相关时，线性分组码的最小码距为 dmin = d6.2.2　线性分组码的译码*6.2.2　线性分组码的译码线性分组码用生成矩阵 G 编码，用校验矩阵 H 译码：当收到一个接收向量 r 后，检验 r 是否满足校验方程 r H T = 0，若关系式成立，则认为 r 是一个码字，否则判为码字在传输中发生了错误。因此 r H T 的值是否为 0 是接收向量出错与否的依据伴随式仅与差错图案有关，与发送的具体码字无关，它反映了信道被干扰的情况不同的差错图案可以具有相同的伴随式伴随式是差错的判别式：若 s = 0，则接收向量是一个码字说明传输过程中或者没有发生差错，或者差错图案恰为一个码字；若 s  0 ，则传输过程中一定发生了差错null* 译码器判接收向量 r 无错，即传输中没有发生错误，发送码字为：null*伴随式纠错译码*伴随式纠错译码对接收向量 r 计算伴随式 s 　　线性分组码的性能除用各种差错概率定量描述外，还可以用码的结构参数关系(码限)直观表述，主要的结构参数为：码长 n信息位长 k，或由此衍生的编码效率  和校验位长 r在尽可能小的 n 和 r 的条件下获得尽可能大的 k, d 或 T常见码限辛格里顿限(S 限)*常见码限普罗特金限(P 限)汉明限(H 限)瓦尔沙莫夫－吉尔伯特限限(VG 限)汉明(Hamming)码*汉明(Hamming)码汉明码是一类能纠正一位差错的线性分组码，其参数为：汉明码 H 矩阵的构造方式： 按 m 位的 2 进制数的自然顺序从左到右排列(不包括全 0 列)，当发生可纠的单个差错时，伴随式为 H 矩阵中对应的列，译码比较方便 将上述非 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 形式的 H 矩阵通过列初等置换变成标准形式的校验矩阵，纠错能力保持不变null*(7,4) 汉明码编码电路(7,4) 汉明码译码电路哈达玛(Hadamard)码哈达玛矩阵：经递归定义得到，其所有元素均为 +1, -1*哈达玛(Hadamard)码哈达玛矩阵经过行列交换后得到的矩阵仍然是正交矩阵哈达玛码(续)对哈达玛矩阵行的选择方式不同，可以构成不同的哈达玛码：*哈达玛码(续)将哈达玛码的码元 +1, -1 映射为 0, 1 即获昨 0, 1 二元意义上的线性分组码里德－穆勒(Reed-Muller)码*里德－穆勒(Reed-Muller)码r 阶里德－穆勒码 RM ( r, m ) 是一种 ( n, k, d ) 线性分组码：r 阶 RM 码的生成矩阵 G 的构成方法：里德－穆勒码(续)*里德－穆勒码(续)例： m = 3 的 r 阶 RM 码的生成矩阵为：戈雷(Golay)码*戈雷(Golay)码二元戈雷码 G23 是一种能纠正 3 个差错的完备线性分组码：二元戈雷码是典型的循环码，它由二进制码导出的，特点是序号相邻的两组码字只有一位码元不同(包括头尾两组码字)，具有循环性去掉二元戈雷码 G24 的任何一个坐标位置所产生的码是相互等价的，它们就是二元戈雷码 G23，所以 G24可由 G23 增加一个奇校验位得到码的重构码的重构*扩展：保持码字数 M 不变，增加冗余位数以增加码长 　例如：增加一个全校验位，使 (n, k) 码扩展成为 (n + 1, k) 码，扩展后的一致校验矩阵为： 若原码的最小码距为 d 且为奇数，则扩展后的最小码距为：打孔：保持 M 不变，减少冗余位数 　打孔是扩展的逆过程，它把 (n, k) 码中所有码字的某一个校验位分量删除掉，得到一个新的 (n - 1, k) 线性码；其最小码距比原码最多减小 1增广：保持码长 n 不变，增加码字数 M 或增加信息位长 k 　　例如：若 (n, k) 码生成矩阵 G 中没有全 1 行，则一种增广方法为： 可以证明上述增广得到的 (n, k + 1) 线性分组码的最小码距为:删信：保持码长 n 不变，减小 M 或 k 　删信是增广的逆过程，例如：若 (n, k) 码的最小码距为 d 且为奇数，那么可以挑选出全部偶数重量的码字组成 (n, k -1, d + 1) 线性分组码码的重构(续)码的重构(续)*延长：同时增加码字数 M (或信息位长 k )和码长 n 　 　　 例如：在原 (n, k) 码的基础上通过增加一个全 1 向量码宇来增广这个码，然后再增加一个全校验位来扩展它，这样构成一个 (n + 1, k + 1) 码 　码的恰当延长可不改变最小码距 d 且增加码的编码效率缩短：同时减少 M (或 k )和 n 　 　缩短是延长的逆过程，例如十字切法，它删除某特定信息位对应的码字位，从而将 (n, k, d ) 线性分组码缩短 (n - 1, k - 1, d ) 码乘积：消息作为阵列，分别进行行列编码码的重构(续)码的重构(续)*级联：对消息编码后的码字再进行一次编码　　交织：改变码字的传送顺序，通常有分组交织和卷积交织两种类型6.3　循环码*6.3　循环码6.3.1　循环码的多项式描述 6.3.2　循环码的生成矩阵 6.3.3　系统循环码 6.3.4　多项式运算电路 6.3.5　循环码的编码电路 6.3.6　循环码的伴随多项式与检错 6.3.7　BCH 码与 RS 码6.3.1　循环码的多项式描述*6.3.1　循环码的多项式描述易证：对任意 i ( 0  i  n -1 )， 左、右循环移位满足： 　　可见左、右循环移位彼此等价的，在不引起混淆的情况下统称为循环移位 　　上表给出的 (7, 3) 分组码的所有 8 个码字在移位(左移或右移)之下是封闭的，此码是一个循环码 循环码：线性分组码的任意一个码字任意循环移位后得到的码字是封闭的(仍是许用码字)6.3.1　循环码的多项式描述(续)一般采用一元多项式来描述循环码*6.3.1　循环码的多项式描述(续)多项式的次数：自变量 x 的幂的最高次数，即：多项式的加减法：x 同幂次项系数相加减多项式的乘法：类似于卷积，所有 x 同幂次项系数合并在一起多项式的模运算：类似于整数的模运算，可用长除法称 f ( x ), g ( x ) 为 h ( x ) 的因式 称 h ( x ) 为 f ( x ), g ( x ) 的倍式商式余式6.3.1　循环码的多项式描述(续)码多项式 c ( x )：其多项式系数恰好一一对应于某循环码 c 的各码元，由此循环码的全体 C 可由码多项式全体 C ( x ) 表示 对于 2 进制码，码多项式的每个系数不是 0 就是 1 x 仅是码元位置的标记，一般不需关心 x 的取值*6.3.1　循环码的多项式描述(续)null*(n, k) 循环码 C( x ) 中存在唯一一个非零、首一、最低次为 r (r < n) 的码多项式 g( x ) 满足 c(x) 是码多项式当且仅当 c(x) 是 g(x) 的倍式 g0  0：若 g0 = 0，因 r < n ，所以: 也是码式，所以次数小于 n 的 g ( x ) 的倍式 a ( x ) g ( x ) 必是码式 反之：若 f ( x ) 是码式，由欧几里德除法可得： 若 r ( x )  0 则 r ( x ) = f ( x ) - a ( x ) g ( x ) 必是码式，且次数小于 r，与 g ( x ) 是最低次码式矛盾，故 r ( x ) = 0，因此码式 f ( x ) = a ( x ) g ( x ) 一定是 g ( x ) 的倍式r = n - k：由于码式是 g ( x ) 的任意次数小于 n 的倍式，不同的码式共有 2 n - r 个 而 ( n, k ) 循环码恰好有 2k 个码字，所以：r = n - k( n, k ) 循环码的生成多项式：由上述定理确定的码多项式 g ( x ) null*必要性：若 g ( x ) 是 (n, k) 循环码的生成多项式，则由欧几里德除法有： 可见 r ( x ) 也是循环码的码式，所以：充分性：设 r ( r = n - k ) 次多项式 g ( x ) 是 x n - 1 的因式，则线性组合： 是循环码的码多项式，对于任意的码多项式 c ( x ) = a ( x ) g ( x ) ，有： 要使上式成立，必有码式 c ( x ) 的一次循环移位式 c ( 1 )( x ) 也是 g ( x ) 的倍式，即 同理可证任意码式 c ( x ) 的任意次循环移位式 c ( i )( x ) 均是 g ( x ) 的倍式，故 g ( x ) 是 (n, k) 循环码的生成多项式6.3.2　循环码的生成矩阵*6.3.2　循环码的生成矩阵根据循环码的循环特性，可由一个码字的循环移位得到其它非 0 码字循环码的一致校验矩阵*循环码的一致校验矩阵 对于码多项式 c ( x ) = a ( x ) g ( x )由于 g( x ) 是 x n - 1 的因式，则 (n, k) 循环码的一致校验多项式为：null*注意：生成矩阵的向行量为 g( x ) 系数的降幂排列，而一致校验矩阵的行向量为 h( x ) 系数的升幂排列；若 G 为升幂排列，则 H 应为降幂排列6.3.3　系统循环码( n, k ) 循环码的生成多项式为 r ( r = n - k ) 次多项式 g ( x )，则任何码多项式必为 g ( x ) 的倍式；反之，g ( x ) 的任何一个 n - 1 次倍式对应一个码多项式*6.3.3　系统循环码将 k - 1 次消息多项式 m ( x ) 和 r 次生成多项式 g ( x ) 相乘即得相应的 n - 1 次码多项式 c ( x ) = m ( x ) g ( x )，但这样产生的码不一定是系统循环码，即相应的 k 位消息数据不一定是集中在码字矢量的左侧(高位)null*因此可以采用以下方法得到系统循环码：消息数据位于码式的高 k 位null*6.3.4　多项式运算电路*6.3.4　多项式运算电路对 2 进制多项式系统的基本运算：模 2 加(异或)、模2乘(与)以下如不作特别说明，则规定：多项式系数进入寄存器的顺序为由低位到高位依次进入，输出时也遵循这种先低后高的顺序；并且电路中所有的延迟寄存器初态为 0多项式乘法电路*多项式乘法电路多项式 a ( x ) 乘以 x 等价于时间序列 a 延迟一位 多项式 a ( x ) 与 g ( x ) 相乘等价于 a ( x ) 的不同移位后然后相加多项式乘法电路(续)*多项式乘法电路(续)两种典型的多项式乘法电路，其中  表示 2 进制乘(与)，在实现上相当于 gi 为 1 时线路接通，为 0 时线路断开多项式模运算若 g ( x ) = 1，则 a ( x ) 对 g ( x ) 取模所得的余式必为 0*多项式模运算若 g ( x ) 是单项式 g ( x ) = x k，则 a ( x ) 对 g ( x ) 取模所得的余式是所有小于 g ( x ) = k 的低幂次部分，即：相应的电路是先对 a ( x ) 低幂次部分的存储然后再输出之为了电路实现的方便，规定多项式模运算时，按照由高位到低位的顺序依次输入；输出时也遵循这种先高后低的顺序多项式模运算(续)*多项式模运算(续)对于任意的 a ( x )， a ( x ) = n，有：相应的电路如下，其中寄存器的初态为 0；当 a ( x ) 输入完成之后，寄存器的内容即为余式 A 0 = a ( x ) mod (1 + x )；输入 a ( x ) 时 K A 接通， K B 断开； a ( x ) 输入完成后，K A 断开，K B 接通对于 2 进制多项式：多项式模运算(续)*多项式模运算(续)多项式模运算(续)*多项式模运算(续)多项式模运算(续)*多项式模运算(续)同理可得到对于一般的多项式模 g ( x ) 运算路；图中移位寄存器初态均为 0非系统循环码的编码电路非系统循环码 c ( x ) = m ( x ) g ( x )，因此可用多项乘法电路实现*非系统循环码的编码电路系统循环码的编码电路*系统循环码的编码电路输入输出均为 先高位后低位消息 m ( x ) 由多项式模运算电路的最后级反馈端输入，等价于 m ( x ) 延迟 r 位，即完成 x r m ( x ) 运算null*6.3.6　循环码的伴随多项式与检错对于循环码，可以分别将码字 c、差错图案 e 和接收向量 r 表示多项式形式：*6.3.6　循环码的伴随多项式与检错将接收多项式 r ( x ) 除以生成多项式 g ( x ) 可得：由于码多项式 c ( x ) 是生成多项式 g ( x ) 的倍式，故上式中的余式 s ( x ) 是由差错多项式 e ( x ) 决定的，与码多项式 c ( x ) 无关；当没有差错时，e ( x ) = 0，则 s ( x ) 必等于 0，故将 s ( x ) 称为伴随多项式或校验式，即：null*若 s ( x )  0，则传输过程中一定有某种差错产生 若 s ( x ) = 0，则传输过程中或者没有差错发生，或者发生了不可检测的差错(其差错图案满足：e ( x ) mod g ( x ) = 0) 循环码的检错可以采用多项式模运算电路实现，每工作 n 个时钟节拍即输出 ，给出一个码字所对应的接收向量有无差错的指示 循环码的伴随多项式与检错(续)循环码的编码和检错均比较简单，所以在 ARQ 方式中应用十分广泛 用于 ARQ 方式的循环码的生成多项式称为 CRC 多项式，常用的 CRC 多项式主要有：*循环码的伴随多项式与检错(续) IBM 公司 ITU 国际电信联盟 此外在 3G 移动信中采用 8 位或 24 位 CRC：6.3.7　BCH 码与 RS 码BCH 码是是现阶段比较容易实现的一种循环码，它能够根据事先确定的纠错能力 T 设计码长和生成多项式 BCH 码具有良好的通用性和较高的编码效率，解码算法简单实用，当码长较长时，BCH 码的性能超过了所有具有相同码长和编码效率的其它编码，是香农第二定理的很好体现 明确界定了码长、一致校验位数目、码的最小距离，在同样的编码效率情况下，纠、检错的能力均较强 特别适合于不太长的码，在无线通信系统中获得广泛应用 对任意正整数 m 和可达到的纠错位数 T ( m  3, T < 2 m - 1)，都可以设计一个最小码距为 d 的 2 元本原 BCH 码，满足：*6.3.7　BCH 码与 RS 码BCH 码所谓构造 BCH 码，实质上就是找出它的生成多项式； 除了找 x n + 1 的因式外，BCH 码的构造有更简单的办法，即生成多项式由它的取自伽罗华域 GF( 2m ) 中的根来确定 m = 3, 4, 5, 6, 7, 8 的 2 元本原 BCH 码的生成多项式如下：*BCH 码表中生成多项式 g ( x ) 为 8 进制表示，例如：RS 码多进制信道编码有时具有更佳的性能： 考虑一个二进制码 (n, k) = (7, 3)，整个 n 元组空间共有 2n = 27 = 128 个 n 元组，其中 2k = 23 = 8 是码字，许用码字所占的比例为 1/16 再考虑一个非二进制码 (n, k) = (7, 3)，每个码元由 m = 3 比特组成，n 元组空间共有 2mn = 221 = 2097152个 n 元组，其中 2mk = 29 = 512 是码字，许用码字所占的比例为1/4096，并且这个比例随着 m 的增大而减小 更重要的是，n 元组中用于码字的比例越小，获得的最小 码距 dmin 越大，检纠错能力就越强 RS 码是多元 BCH 码的一个子类，其输入消息分成 m  k 比特一组，每组包括 k 个符号，每个符号由 m 比特构成，而不是 2 进制 BCH 码中的 1 个比特*RS 码RS 码(续)一个可纠 T 个差错的 RS 码具有如下参数：*RS 码(续)RS 码特别适用于纠正短的突发差错，可纠正的差错图案为：RS 码的生成多项式具有如下形式： 其中 a 是伽罗华域 GF( a m ) 的根6.4 卷积码*6.4 卷积码6.4.1　卷积码的矩阵描述 6.4.2　卷积码的多项式描述 6.4.3　卷积码的状态转移图与栅格描述 6.4.4　维特比(Viterbi)译码算法6.4.1　卷积码的矩阵描述在分组码中，消息序列被分成长度为 k 的分组，每个分组被编成长度为 n 的码字，且当前编码器输出的码字仅与本组内的消息有关，与以前的分组消息无关，即无记忆性； 由于分组码将消息序列分割成组后孤立地进行编译码，忽略了各信息分组之间的联系，必然会丧失一部分相关信息，且消息序列被分割得越碎(码字越短)，丧失的相关信息就越多 虽然可以增大分组码长 m 以避免消息序列被分割得过碎提高尽量搞大，但过长的分组码使译码复杂度大大增加 卷积码是一种有记忆的信道编码，它也将信息序列分割成长度为 k 的一个个分组，某一分组编码输出的 n 个码元不仅与当前时刻的分组有关，还与以前的 L 个分组有关；为了突出特征参数一般记为 (n, k, L) 卷积码 可见任意时刻 (n, k, L) 卷积码均有 L + 1 的个消息分组相关关联，称 L + 1 为卷积码的约束长度*6.4.1　卷积码的矩阵描述卷积码编码电路*卷积码编码电路卷积码编码器是由一个有 k 个输入位(端)、n 个输出位(端)且具有 m 位移位寄存器所构成的有限状态的有记忆系统；典型的卷积码一般选择较小的 n 和 k 值和较大的 L 值以获得既简单又具有较高性能的信道编码编码器为按段工作方式，通过串/并变换和并/串变换实现每经过 k 个节拍就输出一个码字每一码元是 k  ( L + 1)个消息位的线性组合卷积码的离散卷积表达式*卷积码的离散卷积表达式卷积码的矩阵描述*卷积码的矩阵描述null*git = 1：记忆阵列的第 t 列(以前的第 t 组消息数据)的第 i 个消息位参与当前第 j 位码元的编码输出git = 0：不参当前第 j 位码元的编码输出卷积码的子生成元(生成序列){g (i, j )}记忆阵列的各行(各组消息数据 )的第 i 个消息位对当前第 j 位码元的编码影响系统卷积码：每时刻输出码字的左边 k 位恒等于当前输入消息组的 k 位卷积码的结尾处理：输入 N 组消息数据，当最后一组数据进入记忆阵列编码完成后，此时记忆阵列中还保存有 L 组以前的消息数据；需要继续输入 L 组 0 数据，将记忆阵列中残存的消息数据编码输出，最终使记忆阵列回复为全 0 的初态卷积码的编码效率：(3, 1, 2)卷积码矩阵描述举例*(3, 1, 2)卷积码矩阵描述举例(3, 2, 2)卷积码矩阵描述举例*(3, 2, 2)卷积码矩阵描述举例6.4.2　卷积码的多项式描述*6.4.2　卷积码的多项式描述null*卷积码多项式生成矩阵(3, 2, 2)卷积码多项式 生成矩阵举例*(3, 2, 2)卷积码多项式 生成矩阵举例6.4.3　卷积码的状态转移图 与栅格描述卷积码编码器在 t 时刻编出的码字不仅取决于本时刻的输入信息组 mt ，还取决于 t 时刻之前存入记忆阵列的 L 个信息组，将记忆阵列中存入的 t 时刻以前 L 个信息组的内容称为卷积码编码器所处的状态*6.4.3　卷积码的状态转移图 与栅格描述虽然卷积码编码器总共有 2 kL 个状态，但每一时刻输入一组 k 比特的信息最多只可能引起 2 k 个的状态变化；因此每个状态只能转移到 2 kL 个状态的某个子集(2 k 个状态)中去，每个状态也只能由某 2 k 个状态组成的状态子集转移而来null*卷积码的栅格描述卷积码的闭合形状态转移图适用于描述编码器在任意时刻的工作状况，但不能记录下状态转移的轨迹 将开放形状态图添加一根时间轴，将各时刻的状态转移按时间顺序级联便形成栅格图；栅格图有助于发现卷积码的性能特征和推导译码算法，是 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 研究卷积码的最得力上具之一 编码路径：各时刻编码器所处的状态组成的状态序列所对应于栅格图中的一条有向路径 卷积码的编码路径始于全 0 状态 S0，经过若干时刻最终又回复到全 0 状态 S0，表明所有消息组全部编码完成 一次状态转移(转移分支)是栅格图中后续状态的容许连接，并输出一个码字 一条编码路径是可容许连接的分支串 待编所有消息组的码字集对应于一条始于全 0 状态并首次终止于全 0 状态的编码路径*卷积码的栅格描述null*6.4.4　维特比(Viterbi)译码算法*6.4.4　维特比(Viterbi)译码算法卷积码的极大似然译码：寻找一条编码路径使得似然值 p ( R | P ) 或对数似然值 log p ( R | P ) 最大幸存路径和幸存分支*幸存路径和幸存分支幸存分支：t 时刻的幸存路径 PS 的最后一条分支 null*每个状态有 2k 个可能的分支度量，对应于栅格图中有 2k 个可能的分支接入每个节点；而每个状态只有一条幸存路径 每个时刻可能的状态总数为 2q ，则每个时刻共有 2k +q 个可能的分支度量和 2q 条幸存路径可见卷积码的最大似然译码就是寻求一条最大幸存路径，其中幸存路径的求解是一个不断迭代的过程维特比译码算法描述分支度量值 g 的计算方式随不同的信道特性而有所不同初 始化时间计数器、每个状态的最大累积度量值和幸存路径为 0 (或为空) 接收一个接收向量，计算进入每个状态的编码分支的分支度量值并选择最大值，然后累加到前一时刻的最大累积度量，同时存储每个状态下的幸存路径，时间计数器加 1 如此循环直至所有消息组(含记忆阵列中残存的消息组)全部译码完成，然后从 2q 个最大累积度量值中选择最大者，从而找出最大幸存路径 根据上述的最大幸存路径回溯即可输出相应的消息组序列 　　　由上述过程可见：维特比译码算法最费时间和空间的是迭代求解 2q 个最大累积度量值并存储相应的幸存路径，当接收向量序列非常长时，输出最大幸存路径需要很长的时间甚至在实现上是不可能，因此一般对接收向量序列逐段译码输出*维特比译码算法描述最小距离维特比译码算法*最小距离维特比译码算法对不同的信道特性，分支度量值 g 的计算方式也不同最小距离维特比译码算法与前述的维特比译码算法基本相同，只是计算并选择最大分支度量时，需要选择由最小汉明距离计算出的分支度量值作业6.1 6.2 6.3(1 ～ 4) 6.5 6.7 6.8 6.9 6.18(1, 3, 4, 5)*作业