数字通讯原理第4章.ppt

第4章信道编码 4 1信道编码的基础4 2线性分组码4 3循环码4 4卷积码4 5交织码4 6网格编码调制4 7Turbo码习题 4 1信道编码的基础 4 1 1信道编码的基本概念在数字通信中 根据不同的目的 编码可分为信源编码和信道编码 信源编码是为了提高数字通信系统的有效性 即通过各种数据压缩方法尽可能地去除信号中的冗余信息 最大限度地降低传输速率和减少传输频带 信道编码则不同 它是为了提高数字通信系统的可靠性而采取的措施 数字信号在传输过程中 由于噪声干扰和信道特性不理想等都会产生误码 为了提高数字通信系统的性能 可采取诸如合理设计基带信号 选择合适的调制解调方式 采用时域均衡和频域均衡 加大发射功率 采取分集接收等各种抗噪声干扰措施 以尽量减小噪声干扰的影响 若采取上述措施仍难以满足要求 则可以采用信道编码技术 信道编码又称差错控制编码或纠错编码 它的基本思想是 按照某种确定的编码规则在待发送的信息码元序列中加入一些多余的码元 监督码元或校验码元 在接收端利用该规则进行解码 以便发现错误 纠正错误 从而提高信息码元传输的可靠性 1 信道分类 按照噪声或干扰引起传输差错的变化规律 可以将信道分为以下三类 1 随机差错信道 恒参高斯白噪声信道是典型的随机信道 在随机信道中 错码是随机出现的 且各个错码的出现是统计独立的 2 突发差错信道 具有脉冲干扰的信道是典型的突发信道 在突发信道中 错码是相对集中 成串 成群出现的 即在短时间内出现大量错码 3 混合差错信道 短波信道和对流层散射信道是典型的混合信道 在混合信道中 错码既有随机的又有突发的 2 差错控制方式 常用的差错控制方式主要有以下三种 如图4 1所示 1 检错重发 ARQ 在发送信息码元序列中加入一些能够发现错误的码元 接收端能够利用这些检错码元发现接收码元序列中的错码 但不能确定错码的准确位置 此时 接收端通过反向信道通知发送端重发 直到接收端确认收到正确信息码元序列为止 检错重发方式的特点是需要使用反向信道 译码设备简单 适合于突发错误或信道干扰严重的情况 但实时性较差 主要应用于计算机数据通信等 图4 1差错控制方式 a ARQ b FEC c HEC 图4 1差错控制方式 a ARQ b FEC c HEC 2 前向纠错 FEC 发送端发送能够纠错的信息码元序列 接收端不仅能发现错码 而且能确定错码的准确位置 并自动纠正错码 前向纠错方式的特点是无需反向信道 延时小 实时性好 但译码设备比较复杂 随着编码理论和大规模集成电路的发展 性能优良的实用编译码方法不断涌现 FEC方式得到了越来越广泛的应用 3 混合纠错 HEC 它是FEC方式和ARQ方式的结合 即发送端发送具有检错和纠错能力的信息码元序列 接收端检查错码情况 如果错码在其纠错能力范围内 则自动纠错 如果错码超过了其纠错能力 但能检测出来 则通过反向信道请求发送端重发 由于HEC方式具有FEC和ARQ的优点 可实现较低的误码率 因而得到了广泛的应用 3 信道编码分类 1 线性码与非线性码 根据信息码元与监督码元之间的函数关系 信道编码可分为线性码和非线性码 如果信息码元与监督码元之间的函数关系是线性的 即满足一组线性方程式 则称为线性码 否则 称为非线性码 2 分组码与卷积码 根据信息码元与监督码元之间的约束方式 信道编码可分为分组码和卷积码 在分组码中 监督码元只与本码组的信息码元有关 在卷积码中 监督码元不仅与本码组的信息码元有关 而且还与前面几个码组的信息码元有关 3 检错码与纠错码 根据码的用途 信道编码可分为检错码和纠错码 检错码以检错为目的 不一定能纠错 纠错码以纠错为目的 一定能检错 4 系统码与非系统码 根据信息码元在编码前后是否保持原来的形式不变 信道编码可以分为系统码和非系统码 若编码前后信息码元保持原样不变 则称为系统码 反之 则称为非系统码 4 1 2信道编码的基本原理1 分组码的结构 下面以分组码为例来说明纠错编码的基本原理 分组码一般可用符号 n k 表示 如图4 2所示 其中n为码组长度 简称码长 即编码后的码元序列每n位为一组 k是信息码元数目 r n k是码组中的监督码元数目 简而言之 分组码是对每段k位长的信息码元以规定的编码规则增加r个监督码元 组成码长为n的码字 在二进制情况下 共有2k个不同的信息码组 相应地可得到2k个不同的码字 称为许用码组 其余2n 2k个码字未被选用 称为禁用码组 图4 2分组码的结构 2 码重与最小码距 在分组码中 将码组内 1 的个数称为码组的汉明重量 简称为码重 例如码组0011011的码重为4 两个等长码组之间对应位取值不同的位数称为这两个码组的汉明 Hamming 距离 简称为码距 例如码组0011011与1110010之间的距离d 5 码组集中任意两个码组之间距离的最小值称为最小距离 用d0表示 最小码距是一个重要的参数 它是衡量码检错 纠错能力的依据 3 检错和纠错能力 我们以重复码为例来说明纠错编码的检错与纠错能力 若分组码中监督码元是信息码元的简单重复 则称该分组码为重复码 重复码是一种简单实用的检错码 并具有一定的纠错能力 例如 3 1 重复码 假定000和111是两个许用码组 其余为禁用码组 显然最小码距d0 3 接收端译码时 若出现禁用码组001 010 011 100 101 110 则可检出两个错误 或可纠正一个错误 显然 一个分组码的检错和纠错能力取决于最小码距d0的值 分组码的检错和纠错能力与最小码距d0之间有如下关系 1 为了能检测e个错码 要求最小码距d0 e 1 2 为了能纠正t个错码 要求最小码距d0 2t 1 3 为了能纠正t个错码 同时检测e e t 个错码 要求最小码距d0 t e 1 4 1 3纠错编码的信道模型1 随机差错编码信道模型随机差错编码信道的差错是由高斯白噪声 AWGN 引起的 通常随机差错编码信道可分为二进制对称信道 离散无记忆信道和带限波形信道 1 二进制对称信道 BSC 二进制对称信道模型如图4 3所示 它有一个对称二进制输入值集合X 0 1 和二进制输出值集合Y 0 1 以及一组表示输入 输出关系的条件概率 转移概率 若噪声导致差错统计独立且条件概率对称 即 P Y 0 X 1 P Y 1 X 0 P P Y 1 X 1 P Y 0 X 0 1 P 4 1 1 BSC是无记忆的 它的输出仅与对应时刻的输入有关 而与前后输入无关 BSC是研究二进制编码解码最简单 最常用的模型 图4 3二进制对称信道 BSC 2 离散无记忆信道 DMC 离散无记忆信道 DMC 模型如图4 4所示 假设信道的离散输入是q元符号 即输入符号集由q个元素X x0 x1 xq 1 构成 信道的离散输出是Q元符号 即信道输出符号集由Q个元素Y y0 y1 yQ 1 构成 且信道是无记忆的 则信道模型的输入 输出特性可以用一组共qQ个条件概率来描述 即 4 1 2 式中 i 0 1 q 1 j 0 1 Q 1 图4 4离散无记忆信道 DMC 条件概率决定了DMC的特征 可以写成矩阵形式P Pij 其中Pij P yj xi P称为信道转移概率矩阵 即 4 1 3 在信道输入为xi的条件下 由于噪声干扰的存在 信道输出不是一个固定值 而是概率各异的一组值 这种信道称为有扰离散信道 显然输入xi时 各可能输出值yj的概率之和必定为1 即 i 0 1 q 1 如果信道转移概率矩阵的每一行中只包含一个 1 其余元素均为 0 说明信道无干扰 这种信道称为无扰信道 3 离散输入 连续输出信道 假设信道输入符号选自一个有限的 离散的输入符号集X x0 x1 xq 1 而信道输出未经量化 这时的译码器输出可以是实轴上的任意值 即Y 定义这样的信道模型称为离散时间无记忆信道 它的特性由离散输入X 连续输出Y以及一组概率密度函数P Y X xi i 0 1 q 1来决定 这类信道中最重要的一种是加性高斯白噪声 AWGN 信道 对它而言有 Y X G 式中 G是一个零均值 方差为 2的高斯随机变量 即 4 1 5 2 突发差错编码信道模型 上述三种信道模型都是针对随机差错信道的 对于突发差错信道 有大量的信道模型可供研究 其中 最常用的有记忆突发差错信道模型是双状态一阶马尔可夫链模型 也称为吉尔伯特模型 如图4 5所示 吉尔伯特模型有两种状态 G Good 状态和B bad 图4 5吉尔伯特模型 在某一时刻 信道处于两种状态之一 当信道处于B状态时 信道以很大的概率Pbe发生错码 当信道处于G状态时 不产生错误 或与Pbe相比可忽略不计 显然 信道处于B状态意味着有突发差错出现 信道在B和G两种状态之间移动时 在码元周期内 信道从G状态向B状态转移的概率为Pgb 保持在G状态的概率为1 Pgb 同理 信道从B状态向G 状态转移概率为Pgb 保持在B状态的概率为1 Pbg 因此 吉尔伯特模型的参数是 B状态时的误码率Pbe 状态转移概率Pgb和Pbg 可以证明 吉尔伯特模型代表的编码信道的平均误码率为 4 1 6 4 1 4信道编码定理 香农有扰离散信道的信道编码定理指出 每个信道都有一定的信道容量C 对于给定的传信率 码率 Rb Rb C 及码长n 总存在一种编译码方法 使得差错概率 4 1 7 式中 E Rb 为可靠性函数 也称为误差指数 它与C的关系如图4 6所示 信道编码定理表明了错误概率与码长n 信道容量C 信息传输速率Rb之间的转换关系 这是纠错编码的理论基础 图4 6误差指数曲线 4 1 5差错控制的原理1 原理一由信道编码定理的公式可知 降低差错概率应增大码长n或增大可靠性函数E Rb 而要增大E Rb 就要加大信道容量C或减小码率Rb 从图4 6可以看出 1 对于相同的码率Rb 信道容量C大者其可靠性函数E Rb 也大 2 对于相同的信道容量C 码率Rb减小时可靠性函数E Rb 增大 由此 我们可采取如下措施来降低差错概率 1 增大信道容量C 增大信道容量C是提高通信可靠性的基本原理之一 根据信道容量公式 信道容量C与带宽W 信号平均功率S和噪声平均功率N有关 S N为信号噪声功率比 简称信噪比 为此 我们可以 1 扩展频带 例如有线通信从明线 150kHz 双绞线 100MHz 同轴电缆 1GHz 到光纤 25THz 无线通信从中波 短波 超短波到微波 毫米波 2 加大功率 例如提高发射功率 增大天线增益 采用分集接收 点波束等技术 3 降低噪声 例如采用低噪声器件 滤波 屏蔽 接地 低温运行等 2 减小码率Rb 未编码时 一个二进制码元可携带1比特信息 传信率为1比特 符号 编码后 n个二进制码元携带k比特信息 传信率为k n比特 符号 定义Rb k n为二进制分组码的码率 或效率 对于q进制 n k 分组码 k个q元符号编成n个q元符号 其码率Rb klb q n 由此可知降低码率的方法有 1 q n不变而减小k 这意味着降低信息源速率 每秒少传一些信息 2 q k不变而增大n 这意味着提高符号速率 波特率 占用更大带宽 3 n k不变而减小q 这意味着减小信道的输入 输出符号集 在发射信号功率固定时增大信号间的区分度 从而提高可靠性 在一定的通信容量C下减小Rb 等效于拉大C和Rb之差 因此这是用增大信道容量的冗余度来换取可靠性 从20世纪50年代到70年代 主要的纠错编码方法都是以这种冗余度为基础的 3 增加码长n 如果保持码率Rb不变 增加码长n的同时应增大信息位k 以保持k n之比不变 在C和Rb固定的情况下增大n 并没有增加信道容量的冗余度 它是利用了随机编码的特点 随着n增大 矢量空间Xn呈指数量级增大 从统计角度而言 码字间距离也将增大 从而提高了可靠性 另外 码长n越大 其实际差错概率就越符合统计规律 增大码长n所带来的好处同样需要付出某种代价才能换得 代价就是码长越长 编 解码算法就越复杂 编 解码器就越昂贵 香农早在1948年就已指出增大n的途径 但在20世纪70年代前由于器件水平不允许编 解码器做得太复杂 因此 当时实用的纠错编码主要还是靠牺牲功率和频带利用率来换取可靠性的 进入20世纪80年代后 随着超大规模集成电路 VLSI 的发展 编 解码器可以做得越来越复杂 很多编 解码算法可在数字信号处理专用芯片DSP上实现 因此码长允许设计得很长 目前 通过增大码长来提高可靠性已成为纠错编码的主要途径之一 它实际上是以编 解码设备的复杂度来换取可靠性的 从这个意义上说 设备的复杂性是妨碍数字通信系统性能提高的真正限制因素 2 原理二1 利用冗余度 冗余度就是在信息比特流中插入冗余比特 这些冗余比特与信息比特之间存在着特定的相关性 这样 在传输过程中即使个别信息比特出错 也可以利用其相关性从其他未出错的冗余比特中推测出出错比特的原形 保证了信息比特传输的可靠性 例如 如果用 2比特表示四种意义 则无论如何也不能发现差错 因为若有一信息01误成00 则根本无法判断这是传输过程中由01误成00 还是原本发送的就是00 但如果用3比特来表示四种意义 则就有可能发现差错 因为3比特的八种组合能表示八种意义 用它代表四种意义尚剩四种冗余组合 如果传输差错使收到的3比特组合落入四种冗余组合 就可判定一定有错码发生 至于加多少冗余比特 加什么样的相关性最好 这正是纠错编码技术要解决的问题 但必须有冗余 这是纠错编码的基本原理 为了传输这些冗余比特 必然要动用冗余的资源 这些资源可以是 1 时间 例如一个比特重发几次 或一段消息重发几次 或根据收端的反馈重发受损信息比特组等 2 频带 插入冗余比特后传输效率下降 若要保持有用信息的传输速率不变 最直接的方法就是增大符号传送速率 波特率 结果是占用更大的带宽 例如二进制码 1比特 符号 编成 8 4 分组码后 其符号速率增大一倍 占用带宽也增大一倍 3 功率 采用多进制符号 例如用一个八进制ASK符号代替一个四进制ASK符号来传送2比特信息 可腾出位置另传1比特冗余信息 但为了维持信号集各点之间的距离不变 八进制符号的平均功率比四进制时要大 这就是动用冗余的功率资源来传输冗余比特 4 设备复杂性 增大码长n 例如采用网格编码调制 TCM 该方法是在功率 带宽受限信道中实施纠错编码的有效方法之一 其代价是算法复杂度增大 需动用计算 设备 资源 2 噪声均化 噪声均化的基本思想是让差错随机化 设法将危害较大的 较为集中的噪声干扰 称为突发差错 分散开 变为分散的噪声干扰 称为随机差错 从而使不可恢复的信息损伤达到最小 噪声均化将差错均匀分摊给各码组 从而提高了总体差错控制能力 噪声均化的方法主要有以下三种 1 增加码长 例如某BSC信道差错概率Pe 0 01 假如编码后的纠错能力是10 即在长度为n的码字中 只要差错码元个数少于等于n的10 就可以通过译码加以纠正 若码长n 10 则码字中有多于一个码元出错时就会产生译码差错 差错概率为 如果保持码率Rb不变 将码长n增大到40 则当码字中多于四个码元出错时就会产生译码差错 差错概率为 从本例可以看到 只要将码长n由10增长到40 译码差错概率就可以降低两个数量级 这是因为 码长越长 每个码字中错码的比例就越接近统计平均值 即噪声均摊到了各个码字上 2 卷积 在分组码中 是将信息码元序列分割成k位一组 每组再加入r位监督码元后编成n位码字 即码元之间的相关性仅限于在各个码字内 码字之间是彼此无关的 统计独立的 卷积码则不然 它在一定约束长度内的若干码字之间加进了相关性 译码时不是根据单个码字 而是一串码字来进行判决 卷积码是将噪声分摊到码字序列而非一个码字上 从而达到噪声均化的目的 3 交织 也称为交错 交织是对付突发差错最有效的措施之一 突发噪声干扰使码流产生集中成串的 不可纠正的差错 交织码的基本思想是 对编码器输出的码流与信道上的符号流做顺序上的变换 将码流转换为随机的 可纠正的差错 即均化突发信道造成的符号流中的突发差错 4 1 6纠错编码系统的性能指标1 编码效率纠错编码是以降低有效性为代价来提高数字通信系统的可靠性的 对于分组码 n k 来说 定义编码效率 4 1 8 式中 n为码长 k为信息码元的个数 2 纠错编码的误码性能 对于二进制对称信道 BSC 假设在随机差错信道中 发送 0 时的差错概率与发送 1 时的差错率均为Pe 且Pe 1 可以证明 在码长为n的码组中恰好发生i个错误的概率为 4 1 9 则不加纠错时的误码组率为 4 1 10 如果使用可以纠正t位随机误码的纠错码 则译码后的误码组率降低 4 1 11 系统误比特率与具体所采用的编译码算法有关 一般来说 可近似地有 4 1 12 例如 码长n 7 Pe 10 3 此时有 P7 1 7Pe 7 1 3 P7 2 21P2e 2 1 10 5 P7 3 35P3e 3 5 10 8由此可见 在信道误码率较低的情况下 采用纠错编码 即使只能纠正1 2个错码 也能使系统误码率下降几个数量级 对于高斯白噪声信道 AWGN 由第3章可知 在数字调制系统中 误比特率Pb与Eb n0和调制方式有关 例如相干解调2PSK无纠错时的误比特率为 4 1 13 式中 Eb为单位比特能量 n0为噪声功率谱密度 如果在2PSK调制前先进行 n k 分组码纠错编码 则由于加入监督码元 在相同码率情况下 信道中需要传输的符号速率增加了k n倍 因此 误比特率变为 4 1 14 这里 Ec为单位符号能量 它与Eb有如下关系 4 1 15 利用式 4 1 12 4 1 13 和 4 1 14 可以求出编译码后误比特率Pb与Eb n0的关系 3 编码增益在给定误比特率 例如10 5 的条件下 采用纠错编码所节省的信噪比Eb n0称为编码增益 通常用分贝表示 4 1 16 式中 Eb n0 u为未编码时所需的信噪比 dB Eb n0 c为编码后所需的信噪比 dB 显然 编码增益越大越好 4 1 7常用的检错码 1 奇偶监督码奇偶监督码又称奇偶校验码 是一种简单的检错码 在计算机数据通信中应用广泛 奇偶监督码的基本思想是在n 1位信息码元的后面附加上一位监督码元 构成 n n 1 的分组码 监督码元的作用是使得码长为n的码组中 1 的个数是奇数或偶数 码组中 1 的个数是奇数的编码称为奇监督码 码组中 1 的个数是偶数的编码称为偶监督码 奇偶监督码的编码规则是 首先将要发送的二进制信息码元进行分组 然后对所有信息码元和监督码元进行模2加 选择正确的监督码元 以保证模2加的结果为0 偶监督码 或1 奇监督码 假设由n个码元构成的码字为 an 1 an 2 a0 其中前n 1位是信息码元 第n位a0是监督码元 对偶监督码有 4 1 17 a0可以由下式确定 4 1 18 接收端译码时 按式 4 1 17 将码组中的码元进行模2加 若结果为 0 则判定为无错码 若结果为 1 则判定该码组经传输后有奇数个错码 对奇监督码有 4 1 19 a0可以由下式确定 4 1 20 奇偶监督码最小码距为2 无论是奇监督码还是偶监督码 都只能检测出单个或奇数个错码 而不能检测出偶数个错码 奇偶监督码的编码效率为R n 1 n 例如 在ASCII码中 通常采用7位二进制码元来表示128种字符 传输时再加上一个奇偶监督位8位码组 接收端根据是否满足式 4 1 17 或式 4 1 19 来判定传输过程中是否发生错误 2 行列监督码 行列监督码是二维奇偶监督码 又称为矩阵码或方阵码 为了改进奇偶监督码不能发现偶数个错误的情况 行列监督码不仅对水平 行 方向的码元 而且对垂直 列 方向的码元实施了奇偶监督 如图4 7 a 所示 具体编码方法是 将要发送的若干信息码元排列成一个方阵 方阵中的每一行为一个码组 在行的最后一位加上一个监督码元ai0 i 1 2 m 进行奇偶监督 同理 在每列的最后一位也加上一个监督码元ci 1 i 1 2 n 形成行列监督码 图4 7 b 是 66 50 行列监督的一个码字 图4 7奇偶监督码 a 编码方法 b 66 50 行列监督码 行列监督码不仅具有较强的检错能力 还可用来纠正一些错码 例如 当码组仅在一行中出现奇数个错误时 可以确定错码的位置并加以纠正 行列监督码适合于检测突发错误 由于突发错误常常集中成串出现 随后较长一段时间无差错 因此在一行中出现多个奇数或偶数错码的机会较多 而行列监督码有可能检测偶数个错误 尽管每行中的偶数个错误不能由本行的监督码元检出 但按列的方向可能由本列的监督码元检测出来 由于行列监督码只是对构成矩形四角的错码无法检测 故其检错能力较强 3 恒比码 恒比码又称为等比码或等重码 在恒比码中 每个码组中 1 的数目与 0 的数目保持恒定比例 即每个码组都含有相同数目的 1 和 0 接收端译码时 只要检测码组中 1 或 0 的数目是否与规定的数目相同 就可以判定有无错码 例如 目前我国电传通信中普遍采用五位数字保护电码 3 2码 即5中取3的恒比码 每个码组的长度为5 其中有三个 1 准用码组的数目为C35 10 正好表示10个阿位伯数字 0 9 如表4 1所示 每个汉字可以用四位十进制数来表示 表4 15中取3的恒比码 恒比码的最小码距为2 能发现所有奇数个错误 但不能发现所有偶数个错误 实践证明 采用这种恒比码能有效降低汉字电报的差错率 目前国际上通用的ARQ电报通信系统采用3 4码 即7中取3的恒比码 每个码组长度为7 其中有三个 1 准用码组数为C37 35 35个码组分别表示26个字母和其他符号 恒比码的主要优点是简单 实用 适合传送电报或其他键盘设备产生的字母字符 但不适合传送二进制随机数字序列 4 2线性分组码 4 2 1线性分组码的基本概念线性分组码中的分组是指编 译码过程是按分组进行的 一般是按每k个信息码元一组进行编译码 而线性则是指分组码中监督码元按线性方程生成的 即r n k个监督码元是由k个信息码元的线性变换产生 例如在 7 4 线性分组码中 信息码元每四位 一组进行编码 即输入信息码元长度k 4 编码器输出码组长度n 7 监督码元长度r n k 7 4 3 编码效率R k n 4 7 从空间的角度看 n k 线性分组码中的每一个码字都可以看成n维线性空间中的一个矢量 长度为n的码字共有2n个矢量 构成一个n维线性空间 n k 线性分组码中有2k个准用码字 k n 构成了一个k维线性子空间 即 n k 线性分组码是n维线性空间中的一个k维线性子空间 纠错编码的任务就是在n维线性空间的2n种可能组合中选择2k个构成一个k维线性子空间 由于该线性子空间在模2加法运算中构成阿贝尔群 因此线性分组码又称为群码 4 2 2线性分组码编码方程与生成矩阵G 下面以 7 3 二进制线性分组码为例来说明 假设输入信息码组为m m0m1m2 编码器输出码组为C c0c1c2c3c4c5c6 已知输入码与输出码的关系式是c0 m0 c1 m1 c2 m2 c3 m0 m2 c4 m0 m1 m2 c5 m0 m1 c6 m1 m2 因此 可将上述关系式列成如下编码线性方程 4 2 1 可见 输出码组中前三位是信息码元的简单重复 后四位是监督码元 它由前三个信息码元的线性组合构造 写成对应的矩阵形式为 4 2 2 式中 G称为生成矩阵 由G和信息组就可以产生全部码字 G为k n阶矩阵 各行也是线性无关的 生成矩阵也可分为两部分 即 4 2 3 式中 Q为k r阶矩阵 Ik为k阶单位矩阵 G称为典型生成矩阵 非典型生成矩阵经过行列运算可以转化为典型生成矩阵 在本例中 七位二进制数有27 128种组合 而三位信息码组只有23 8种组合 一一对应到八个码字 在以上编码过程中 核心的因素是生成矩阵G 它决定了编码规则 也决定了码字集合 该生成矩阵G可以看成是由三个行矢量组成的 所有码字是这三个行矢量的线性组合 C m0 1001110 m1 0100110 m2 0011101 分别令信息组m m0m1m2 为 000 001 111 不难算出各信息组对应的码字 如表4 2所示 表4 2信息码组与码字对应表 4 2 3线性分组码的监督方程与监督矩阵H若将式 4 2 1 编码方程中后四位监督方程改写 可得 4 2 4 将上述线性方程写成如下矩阵形式 即 或 4 2 5 其中 CT是码空间C的转置 OT是O 0000 的转置 HT是H的转置 4 2 6 4 2 7 其中PT是P的转置 根据以上推导可以看出 监督矩阵H与生成矩阵G之间存在一一对应的关系 即 4 2 8 4 2 9 只要生成矩阵G确定了 监督矩阵H也就确定了 反之亦然 显然 线性分组码可以由生成矩阵G或监督矩阵H完全确定 编码时通常采用生成矩阵G 译码时通常采用监督矩阵H HCT OT 说明H矩阵与码字的转置乘积必为零 可以用来作为判定接收码字C是否出错的依据 4 2 4校正子 伴随式 S与译码假设发送码组C c6c5c4c3c2c1c0 在传输过程中可能发生误码 接收码组B b6b5b4b3b2b1b0 则发送码组与接收码组之差定义为错误图样E 也称为误差矢量 即E B C B C 其中E e6e5e4e3e2e1e0 且 i 0 1 6 4 2 10 当ei 0时 表示该位接收码元正确 当ei 1时 表示该位接收码元有错 令S BHT 称为伴随式或校正子 当接收端译码时 用监督矩阵H进行校验 计算校正子S 即 由于CHT 0 因此校正子S只与错误图样E有关 与发送码字C无关 由此可见 校正子S与错误图样之间有确定的线性变换关系 接收端译码器的任务就是从校正子S确定错误图样E 然后从接收到的码字中减去错误图样 图4 8给出了译码过程框图 4 2 11 图4 8译码过程框图 4 2 12 问题的关键是从S中找出E 只要E正确 译出的码就是正确的 下面以 5 2 线性分组码来说明如何构造该码的标准阵列译码表和译码 假设 5 2 线性分组码的生成矩阵为 其中 n 5 k 2 r 3 由信息组m 00 01 10 11 由式 4 2 2 可求得四个准用码字为C0 00000 C1 10111 C2 01101 C3 11010 由式 4 2 8 可求得监督矩阵 4 2 13 由S EHT可得 4 2 14 由BHT确定S后 对应的E可以有2k 22 4 个解 究竟取哪一个作为差错图样E的解 最简单明了的处理方法是概率译码 即对所有2k个解的重量 差错图样E中1的个数 进行比较 选择重量最小的作为E的估值 由于E B C E重量最小 就是B和C的汉明距离最小 显然 在进行概率译码时 每接收一个码字就要解一次线性方程 非常复杂麻烦 但如果n k不太大 我们可以预先把不同校正子S情况下的所有方程组都预先解出来 将各种情况下的最大概率译码输出列成一个标准阵列译码表 这样 在实际译码时就不必解方程 只要查译码表就可以了 校正子S有2n k 23 8种组合 而错误图样有25 32种 其中 代表无差错的全零错误图样有C05 1种 代表一个差错的错误图样有C15 5种 代表两个差错的错误图样C25 10种 显然 要把八个校正子对应到八个重量最小的错误图样 无疑应先选择 全零错误图样 五种一个差错的错误图样 剩下的两个校正子不得不在10种两个差错的错误图样中选择两个 具体方法是 1 先将全零错误图样E 00000 代入式 4 2 14 可求得对应的S 000 2 再将五种一个差错的错误图样E 10000 01000 00100 00010 00001 代入式 4 2 14 可求得对应的S 111 101 100 010 001 3 剩下的两个校正子是 011 和 110 每个有2 种解 对应22个错误图样 对于校正子 011 的22个解 错误图样E 为 00011 10100 01110 11001 其中 00011 和 10100 具有最小重量 可选择其中之一作为错误图样 例如选择 00011 同理 校正子 110 所对应的重量最小的错误图样之一是 00110 如表4 3所示 表4 3 5 2 线性分组码译码表 若接收码B 10101 可采用以下三种方法之一进行译码 1 直接搜索译码表 查表得 10101 所在列的码字为C1 10111 2 先求校正子S BHT 10101 HT 010 再由010搜索译码表的第五行可找到 10101 可得所在列的码字C1 10111 3 先求校正子S BHT 010 可查到对应的错误图样E 00010 再计算C B E 10101 00010 10111 4 2 5完备码与汉明码 1 完备码对于 n k 线性分组码 它有2k个码字 2r个校正子 若该码要纠正小于等于t个随机错误 则必须满足 满足上式条件的线性分组码称为汉明码 式 4 2 15 指出了n r与t之间的关系 若式 4 2 15 的等式成立 则该线性分组码称为完备码 显然 汉明码是一种完备码 能满足 的完备码并不多见 已发现的二进制完备码有t 1的汉明码 t 3的 23 12 高莱 Golay 码 2 汉明码 汉明码是一种常用的线性分组码 也是纠错能力t 1的完备码 1950年由Hamming提出 汉明码的主要特点有 1 给定监督码元数r 就能确定汉明码的码长为n 2r 1 信息码元数为k 2r r 1 当r 3 4 5 6 时 分别有 7 4 15 11 31 26 63 5 汉明码 2 最小码距d0 3 可以纠正一位错码 常用于FEC系统 3 编码效率为 可以看出 当r 或n 很大时 R趋于1 显然 汉明码是一种高效码 若在汉明码中再加上一位对所有码元都进行校验的监督位 则监督位由r扩展至r 1 信息码元数不变 码长由2r 1增到2r 通常把这种 2r 2r r 1 码称为扩展汉明码 扩展汉明码的最小码距d0 4 能在纠正1位错误的同时检测2位错误 在某些情况下 还可以将原汉明码的码长n及信息码元数k同时缩短s位 即可得到 n s k s 缩短汉明码 扩展汉明码和缩短汉明码都是从汉明码变形得到的 统称为变形的汉明码 上述对汉明码进行扩展和缩短的变形方法可以推广应用到所有其他线性分组码中 以构造任意码长的线性分组码 3 高莱码高莱码是二进制 23 12 线性分组码 最小码距d0 7 纠错能力t 3 由于223 12 2048 1 C123 C223 C323 故也是完备码 在 23 12 码上添加一位监督位即得二进制线性 24 12 高莱码 最小码距d0 8 4 3循环码 4 3 1循环码的概念循环码是1957年由普兰奇 Prange 提出的 它是线性分组码中最重要的一个子类 目前 实用差错控制编码中所使用的线性分组码几乎都是循环码或循环码的子类 循环码除了具有 n k 线性分组码的一般性质外 还具有循环性 即若将其任意一个码字 cn 1 cn 2 c1 c0 的码元向右或向左循环移一位 所得的 c0 cn 1 cn 2 c1 或 cn 2 c1 c0 cn 1 仍然是码字 表4 4是一种 7 3 循环码的全部码字和码多项式 表4 4 7 3 循环码 循环码的结构完全建立在有限域的基础上 可以用代数的方法来描述 为了便于计算 通常用码多项式来表示码字 对于 n k 循环码的码字 cn 1 cn 2 c1 c0 其码多项式为C x cn 1xn 1 cn 2xn 2 c1x c0 例如码字 1101001 对应的码多项式为C x x6 x5 x3 1 其中x只是码元位置的标记 我们并不关心它的取值 4 3 2循环码的码多项式在整数运算中 有模n运算 例如 在模2运算中 1 1 2 0 模2 1 2 3 1 模2 6 0 模2 对于整数m进行模n运算 有 4 3 1 式中 Q为整数 p n 这说明 在模n运算下 一个整数m等于它被n除得的余数 例如 在模3运算中 7 3 2 1 3 1 模3 对码多项式也可以按模运算 若任意一个多项式F x 被一个n次多项式N x 除 得到商式Q x 和一个次数小于n的余式R x 即 F x N x Q x R x 4 3 2 则在按模N x 运算下 有 模N x 此时 码多项式系数仍按模2运算 系数只取0和1 例如F x x4 x2 1被N x x3 1除 得到余式R x x2 x 1 即x4 x2 1 x2 x 1 模 x3 1 在 n k 循环码中 若C x 是一个长度为n的码字 则xiC x 在按模 xn 1 运算下 也是该循环码中的一个码字 即若 xiC x Q x xn 1 C x C x 模 xn 1 4 3 3 则C x 也是该循环码中的一个码组 其中 i为码字左移的位数 Q x 为xiC x 除以xn 1的商式 C x 为xiC x 被xn 1除得的余式 例如码字 1101001 若将此码字左移两位 由式 4 3 3 可得到 x2 x6 x5 x3 1 x 1 x7 1 x5 x2 x 1 即Q x x 1 C x x5 x2 x 1 对应的码字为 0100111 与直接对码字进行循环左移两位的结果相同 4 3 3循环码的生成多项式和生成矩阵1 循环码的生成多项式如果一种码的所有码多项式都是多项式g x 的倍式 则称g x 为该码的生成多项式 循环码的码多项式都是最低次码多项式g x 的倍式 例如表4 3所示的 7 3 循环码中 生成多项式g x x4 x3 x2 1 显然 循环码中次数最低的多项式 除全0码字外 就是生成多项式g x 可以证明 g x 是常数项为1的r次多项式 是xn 1的一个因子 一旦确定了g x 则整个 n k 循环码就被确定了 问题是如何确定任意一个 n k 循环码的生成多项式g x 例如 x7 1 可以分解为 x7 1 x 1 x3 x2 1 x3 x 1 为了求出 7 3 循环码的生成多项式g x 需要从中找到一个r n k 7 3 4次的因子 不难看出 这样的因子有两个 x 1 x3 x2 1 x4 x2 x 1 x 1 x3 x 1 x4 x3 x2 1 这两个因子都可以作为生成多项式 注意选用不同的生成多项式 所产生的循环码的码字不同 n k 循环码的生成多项式满足下面三条性质 1 g x 是一个 n k 次多项式 2 g x 的常数项不为0 3 g x 是xn 1的一个因子 2 循环码的生成矩阵循环码的生成矩阵G常用多项式的形式来表示 即 4 3 4 例如表4 3所示的 7 3 循环码 n 7 k 3 r 4 其生成多项式g x x4 x3 x2 1 代入式 4 3 4 可得 即 显然 G不是典型形式的生成矩阵 但经过简单的变换就很容易化为典型形式的生成矩阵 即 4 3 4循环码的监督多项式和监督矩阵1 循环码的监督多项式 由于g x 能除尽xn 1 因此有 4 3 5 其中 g x 是常数项为1的r次生成多项式 h x 是常数项为1的k次多项式 称为监督多项式 令h x xk hk 1xk 1 h1x 1 h x 的逆多项式h x xk h1xk 1 h2xk 2 hk 1x 1 例如 7 3 循环码中 g x x4 x3 x2 1 则 4 3 6 4 3 7 2 循环码的监督矩阵 由监督多项式很容易得到循环码的监督矩阵 即 4 3 8 例如由式 4 3 7 可得 7 3 循环码的监督矩阵为 4 3 9 即 4 3 10 例4 1 已知 7 4 循环码的全部码组为0000000 0100111 1000101 1100010 0001011 0101100 1001110 1101001 0010110 0110001 1010011 1110100 0011101 0111010 1011000 1111111 试求该循环码的生成多项式 生成矩阵和监督矩阵 解 1 求生成多项式g x 已知 n 7 k 4 r n k 7 4 3 x7 1 x 1 x3 x 1 x3 x2 1 因为生成多项式g x 必须满足 是一个n k 3次多项式 其常数项不为0 是x7 1的一个因子 显然满足上述条件的因子有两个 x3 x 1和x3 x2 1 由于本题给出了循环码的全部码字 因此符合本题条件的生成多项式g x 只有一个 假定g x x3 x 1 2 求生成矩阵G 生成矩阵为 经检验 由g x x3 x 1得到的生成矩阵G能产生本题所给定的全部生成码字 而g x x3 x2 1所生成的循环码与本题所给的码组不符 3 求监督矩阵 4 3 5循环码的编码方法 循环码编码时 首先要根据给定的 n k 值来选定生成多项式g x 即从 xn 1 的因式中选定一个r n k次多项式作为g x 根据循环码中的所有码多项式都可被g x 整除这条原则 就可以对给定的信息码元进行编码 假设编码前的信息码多项式为m x 其次数小于k 用xr乘以m x 得到xrm x 的次数小于n 用g x 除以xrm x 得到余式R x R x 次数必小于g x 的次数 即小于 n k 将此余数R x 加在信息码元之后作为监督位 即将R x 与xrm x 相加 得到的多项式必为码多项式 因为它必能被g x 整除 且高的次数不大于 k 1 因此 循环码的码多项式为 4 3 11 循环码的编码方法可归纳如下 1 用xr乘以m x 该运算的作用是在信息码元后附加上r个 0 例如在 7 3 码中信息码组为 110 它可以写成m x x2 x 由于r n k 7 3 4 所以xrm x x4 x2 x x6 x5 它表示码组1100000 即信息码元后附加四个 0 2 用g x 除以xrm x 得到商Q x 和余式R x 即 4 3 12 若选定g x x4 x2 x 1 则有 4 3 13 即Q x x2 x 1 R x x2 1 上式等效于 4 3 14 3 编码器输出的码字为 C x xrm x R x 1100000 101 110010 4 3 15 4 3 6循环码的译码方法 1 循环码的检错 由于任一码多项式C x 都应能被生成多项式g x 整除 因此在接收端可以将接收码组B x 用生成多项式去除 即 当传输过程中没有发生差错时 接收码组与发送码组相同 C x B x 即接收码组B x 必定能被g x 整除 即R x 0 当传输过程中发生差错时 C x B x B x 除以g x 时必定除不尽而有余项 即R x 0 因此 可以用余项R x 是否为零来判定码组中是否有差错 应当注意 当接收码组中的错误数量超出编码的检错能力时 有错误的接收码组也可能被g x 整除 此时 差错就无法检出 这种错误称为不可检错码 例4 2 已知 15 7 循环码的生成多项式为g x x8 x7 x6 x4 1 试问接收码组B x x x5 x 1是否有误 解因为 所以接收码B x x14 x5 x 1有误 2 循环码的纠错在纠错时 译码方法比检错时复杂 为了能纠错 要求每个可纠正的错误图样必须与一个特定的余式有一一对应关系 只有这样才可能按此余式惟一地决定错误图样 从而纠正错误 循环码的纠错译码方法如下 1 用生成多项式g x 除以接收码组B x 得到余式R x 2 按照余式R x 用查表方法或计算校正子得出错误图样E x 就可以确定错码的位置 3 从B x 中减去E x 便得到已经纠正错码的原发送码组C x 常用的循环码译码方法主要有梅吉特译码 捕错译码和大数逻辑译码等 4 3 7缩短循环码 一般来说 xn 1的因式数目不多 它们所能组合出来的因式次数也是有限的 并非任何 n k 的取值都能产生循环码 为了满足实际中对n k的多种要求和限制 循环码常采用缩短码的形式 即缩短循环码 缩短循环码的基本思想是 从 n k 循环码的2k个码字中挑选出前i 0 i k 个信息码元为0值的码字 即有2k i个这样的码字 删去前i位后作为 n i k i 缩短循环码的码字 由于缩短循环码的码集是 n k 循环码的子集 因此其码多项式也一定能被生成多项式g x 整除 由于在缩短循环码的过程中 并没有删除 1 码 因此缩短循环码的最小码距d0不变 即 n i k i 缩短循环码的检纠错能力与原 n k 循环码的相同 只是编码效率降低了 4 3 8BCH码BCH码是一种非常重要的循环码 它在编码理论研究和实际应用上占有重要地位 BCH码的重要性体现在 它有严密的代数结构 是目前研究得最透彻的一类码 它的生成多项式g x 与最小码距d0之间有密切的关系 人们能根据所要求的纠错能力 对d0的要求 很容易地构造出BCH码 BCH编 译码比较简单 易于实现 是线性分组中应用最为普遍的一类码 首先引入本原多项式的概念 如果一个n次多项式F x 满足以下条件 1 F x 是既约多项式 即不能分解因式的多项式 2 F x 可整除 xp 1 p 2n 1 3 F x 除不尽 xq 1 q p 则称F x 是一个最高次数为n的本原多项式 例如当n 3时 x2n 1 1 x7 1 此时最高次为3的本原多项式为x3 x2 1和x3 x 1 它们都能整除x7 1 但不能整除x6 1 x5 1等 BCH码可分为本原BCH码和非本原BCH码 本原BCH码是指在生成多项式g x 中 含有最高次数为m的一个本原多项式 且码长n 2m 1 而非本原BCH码的生成多项式g x 中不含有这种本原多项式 且码长n是2m 1的一个因子 即码长n一定能除尽2m 1 BCH码的码长n 监督位r和纠错能力t之间的关系如下 对于任意整数m和t m 2 一定存在一个二进制BCH码 其码长n 2m 1 监督位数r n k mt 并能纠正所有不大于t的随机错误 为了便于应用 表4 5给出了码长n 63的本原 BCH 码 表4 6给出了码长n 73的非本原BCH码 其中g x 栏下的数字是八进制数 用于表示生成多项式g x 中的各项系数值 例如表4 5中 由于八进制数 23 对应的二进制码为 010011 故生成多项式g x x4 x 1 表4 5n 63的本原BCH码 表4 6部分非本原BCH码 在实际应用中 如果要求BCH码的码长不是2m 1或它的因子 则可采用前面介绍的缩短码的方法来构造缩短BCH码 4 3 9Fire码Fire 法尔 码是一种纠正单位个突发错误的循环码 其特点是可以根据不同的要求方便地设计所需的码 译码简单 广泛应用于计算机磁盘系统中 令p x 是一个m次的既约多项式 且l与m互素 则Fire码的生成多项式为 g x p x xl 1 4 3 16 该码的码长为 n LCM l e 4 3 17 式中 LCM表示取最小公倍数 e 2m 1 该码的监督位数为 r n k l m 4 3 18 例如p x x4 x 1 令l 7 Fire码的生成多项式为 g x x 4 x 1 x7 1 x11 x8 x7 x4 x 1 码长n LCM 7 24 1 LCM 7 15 105 监督位数r 7 4 11 信息位数k 105 11 94 即 105 94 Fire码 4 3 10RS码RS码是里德 索洛蒙 Reed Solomon 码的简称 它是一种多进制BCH码 具有很强的纠错能力 特别适合在衰落信道中纠正突发错误 在 n k RS码中输入信号分成k m比特一组 每组包括k个符号 每个符号由m比特组成 一个能纠正t个符号错误的RS