第5章 线性分组码-抗干扰信道编码.ppt

第5章抗干扰信道编码 预备知识译码规则基本概念和原理线性分组码及其性质线性分组码的群表示线性分组码的线性空间表示线性分组码的生成矩阵及编码标准阵列译码一致校验矩阵伴随式译码线性分组码的残留误码率完备码海明码 众所周知 信道总是要受到噪声干扰 所以我们收到的符号不一定与发送符号一致 也就是说 当我们收到一个符号时 并不能确定发送的是哪个符号 对于某一个具体的物理信道 其可靠性是确定的 但是在不同的具体通信系统中 有不同的可靠性要求 在具体应用时 我们可以通过信道编码提高通信系统的可靠性 使其满足具体应用要求 下面我们通过两个具体的例子来说明 第1节预备知识 1概述 1 奇偶校验码 以偶校验码为例 首先 我们将发送的比特流划分成k比特的分组 然后在每个分组后面添加一位 确保每个分组中符号 1 的个数为偶数 最后将处理后的比特流送入信道中 编码 第1节预备知识 解码 首先 我们将接收到比特流划分成k 1个比特的分组 然后检查每个分组中符号 1 的个数 若为奇数个 则说明信道出错 请求对方重发 若为偶数个 则认为信道没有出错 将最后一个比特丢掉 剩余的k个比特交给信源解码设备 信源 101001100100111010010001 取k 8101001100100111010010001 偶校验编码 101001100010011100100100011 例 第1节预备知识 如果没有错误发生 分组中的符号 1 的个数仍为偶数个 接收机将接收到的分组中最后一个比特丢掉 然后将剩余比特送到信源解码设备 如果分组中有奇数个错误发生 则接收分组中一定符号 1 的个数一定是奇数个 故接收方一定能够发现错误 并请求对方重发 ARQ 如果分组中有偶数个错误发生 则接收分组中仍有偶数个符号 1 接收者不能发现错误 同样将最后一个比特丢掉后送到信源解码器 此类错误不能发现 第一节预备知识 假设每个比特出错的概率为p 则一个分组出错但不能被检测出的概率为 编码效率 第1节预备知识 如果p 0 02 则 而不编码的分组错误概率为 奇偶校验码是一种检错码 是所有差错控制编码中效率最高的编码 第1节预备知识 2 重复编码 000000 111111 如果少于3个错误发生 我们可以纠正错误 如果少于5个错误发生 我们可以发现错误 101011111000001111100000 编码效率 重复编码是一种纠错码 是所有差错控制编码中效率最低的一种 第1节预备知识 第1节预备知识 差错控制编码的基本原理是在信号送入信道之前 在原始信息的基础上增加一些可控的冗余 额外的符号 在接收端 如果错误的符号数在差错控制编码的设计范围内 则错误可以被纠正或发现 常见的差错控制编码包括奇偶校验码 循环码 海明码 卷积码等等 第1节预备知识 2 几个概念 1 分组 由信源码符号流按划分成的 k个信源码符号组成的 符号组 2 信道码符号 构成信道有效码字的符号集 信源 信源编码 信道编码 信道 信道译码 信源译码 信宿 信源符号 信源码符号 信道码符号 信源符号 信源码符号 信道码符号 第1节预备知识 例 若信源码符号集为 0 1 则信源编码后输出为由0 1组成的符号序列 若信道编码如下 1 将3 k 3 个信源码符号组成的分组编码成4 n 4 个信道码符号组成的信道有效码字 2 信道码符号集为 0 1 2 第1节预备知识 有效 信道 码字 与分组一一对应的 由n个信道码符号组成的的序列 禁用 信道 码字 除了有效码字之外的 由n个信道码符号的序列 字 有效码字 禁用码字 有效码字集 0000 0011 0022 1100 2200 1212 2121 1122 禁用码字集 I 有效码字 字集 I 第3节信道编码中的基本概念 如在重复编码中 将 1 编码成 11111 将 0 编码成 00000 则 11111 和 00000 称为有效码字 除了这两个码字外 还有30个码字没有被使用 这30个码字都称为禁用码字 如果信道不出错 则输出的只有可能是两种有效码字中的一个 如果输出的不是这两个有效码字 则一定信道一定出错 第1节预备知识 思考 1 信道编码是否要考虑前缀编码条件问题 2 如果信道丢失了一个信道符号 会对译码造成什么样的影响 第1节预备知识 1 纠错检错的能力 主要用最小海明距离衡量 2 编码的效率 或者叫信道的信息率 3 编码的软件硬件实现效率和困难程度 对于一种抗干扰信道编码 衡量其性能的标准主要有以下几个方面 2信道编码的评价标准 1 后验概率译码 1 后验概率译码 第2节译码规则 例 译码规则 接收为b1时正确译码的概率 等于在接收为b1的条件下发送符号为a1的概率 第2节译码规则 正确译码概率 错误译码的概率等于在接收为b1的条件下 发送符号不是a1的概率 平均错误概率 第2节译码规则 译码规则 或 讨论 若在接收为某符号的条件下 发送为某几个符号的概率相同 则可任选一个作为译码 第2节译码规则 2 推广 第2节译码规则 例 已知信源空间为 信道转移概率矩阵为 第2节译码规则 求Pe 第2节译码规则 第2节译码规则 第2节译码规则 第2节译码规则 第2节译码规则 第2节译码规则 2 最大似然译码 如果所有信源都是等概率的 则有 1 最大似然译码 第2节译码规则 我们可以得到这样的结论 如果信源符号等概率出现 可以利用信道转移概率构成译码规则 第2节译码规则 2 平均错误译码概率 第2节译码规则 第2节译码规则 例 已知信源概率空间为 信道转移概率为 第2节译码规则 平均错误概率 第2节译码规则 第2节译码规则 1 分组码 信源码符号流被划分成k个符号的分组 然后编码成唯一对应的n个比特的信道码字 例子 k 2 n 3 第3节信道编码中的基本概念和原理 2 汉明重量 码字中非零符号的个数 用w表示 3 汉明距离 两个码字中相同位置的不同符号的个数 用d表示 第3节信道编码中的基本概念 4 最小汉明重量w 在一种编码种所有码字的海明重量的最小值 第3节信道编码中的基本概念 5 最小汉明距离d 一种编码中任意两个码字的的海明距离的最小值 第3节信道编码中的基本概念 例 第3节信道编码中的基本概念 6 解码球 第3节信道编码中的基本概念 1 字的球模型如左图所示 与字000海明距离为1的字在以字000为球心 半径为1的球面上 同理 与字000海明距离为2 或3 的字在以字000为球心 半径为的2 或3 球面上 同样 我们也可以以其它字为球心 如左下图中 就是以字010为球心 建立的分别以1 2或3为半径的球面 第3节信道编码中的基本概念 2 解码球在分组码中 分别以各有效码字为球心 建立半径为e的球 且各球互不相交 如果接收的字落到某各球内 则译码成球心处对应的码字 这样的球叫解码球 例 已知分组码 分别建立以有效码字000和111为球心 半径为1的球 如下图所示 1 信道编码纠检错能力取决于这种编码的最小海明距离 最小海明距离越大 纠检错能力越强 2 如果分组码能纠正所有的e个符号的错误 则最小汉距明离应满足 第3节信道编码中的基本概念 7 线性分组码的纠检错能力 例 重复编码 000000 111111 C 00000 11111 第3节信道编码中的基本概念 3 如果分组码能检测所有的f个符号的错误 则最小海明距离应满足 有效码字1 有效码字2 例 C 000 010 101 111 f 1 例 C 00000 11111 第3节信道编码中的基本概念 4 如果分组码能检测所有的f个符号的错误 并能纠正所有的e为错误 则最小海明距离应满足 有效码字1 e 1 有效码字2 f 第3节信道编码中的基本概念 8 抗干扰信道编码定理 抗干扰信道编码定理也就是香农第二定理 其表述形式如下 设信道有r个码符号 当信道的信息传输率R C时 只要码长N足够长 总可以从输入集合中 rN个长度为N的字 找到M个码字 代表分别M个消息 组成一种信道编码 选择相应的译码规则 使最小译码错误概率任意小 香农第二定理说明 平均错误译码概率趋近于0 信道信息传输率R趋近于信道容量C的抗干扰信道编码是存在的 第3节信道编码中的基本概念 第3节信道编码中的基本概念 我的理解 信源编码的码率为 Rbit 信源码符号 每k个信源码符号分为一组 编码为n个信道码符号 如果要使信息完全传递 则每个信道码符号携带的信息量应为 如果信道的容量C满足 bit 信道码符号 则这样的编码总是可以找到的 P532T7 4T7 6T7 9 作业 1线性分组编码的定义 一个线性编码具有以下的性质 信息序列被划分成等长的k个符号的分组 每个分组被编码成n个比特的码字 其中r n k为冗余 任意个有效码字的线性组合仍然是一个有效码字 全0字也一定是一个有效码字 例1C 010 011 100 110 例3C 010 000 100 110 111 例2C 000 010 101 111 第4节线性分组码定义及性质 2 线性分组码的性质 线性分组码的最小汉海明距离等于它的非零码字的最小海明重量 因为如果字C1和C2都是有效码字 则C3 C1 C2必然也是一个有效码字 假设C1和C2之间的海明距离为线性分组码的最小海明距离 则该线性分组码的最小海明距离等于码字C3的海明重量 第4节线性分组码定义及性质 3 说明 我们通常用 群 域 和 线性空间 的理论来描述和研究现行分组码 第4节线性分组码定义及性质 例2C 000 010 101 111 1群 i 封闭性 1 群的定义 G是一个非空集合 在这个集合上定义了一种运算 可以是乘法或加法 如果满足以下四点性质 则称之为群 记作 G 第5节线性分组码的群表示 ii 结合律 iii 集合中存在唯一单位元 第5节线性分组码的群表示 vi 集合中每个元素都存在唯一逆元 例1定义了 整数集合是一个加法群 唯一单位元 唯一逆元 封闭性 结合律 第5节线性分组码的群表示 例2定义了乘法运算的正数集合是一个乘法群 唯一的单位元 唯一逆元 封闭性 结合律 讨论 是不是加法群 第5节线性分组码的群表示 例3 所有的m n阶矩阵的集合是一个加法群 唯一的单位元 唯一逆元 封闭性 结合律 讨论 是不是乘法群 第5节线性分组码的群表示 例5 集合 0 1 2 3 4 运算为模5和 唯一的单位元 唯一逆元 封闭性 结合律 讨论 是不是乘法群 第5节线性分组码的群表示 例6 集合 1 2 3 4 模5乘法运算 唯一的单位元 唯一逆元 封闭性 结合律 讨论 是不是加法群 第5节线性分组码的群表示 例7 G 000 010 101 111 按位模2加法 唯一的单位元 唯一逆元 封闭性 结合律 第5节线性分组码的群表示 提示 集合S 1 2 3 q 1 在模q乘法运算下是一个群的充分必要条件是 q是素数 质数 集合S 1 2 3 在模4乘法运算下不是群 第5节线性分组码的群表示 2 群的分类 i 按照不同的运算可分为加法群和乘法群 ii 按照集合中元素的个数可分为有限群和无限群 i 交换群 则称之为交换群 也叫做阿贝尔群 3 两种特殊的群 如果一个群中的元素满足交换率 即 第5节线性分组码的群表示 说明 加法群一定不是乘法群 乘法群一定不是加法群 ii 循环群 如果群中的元素可用如下的形式表示 则称之为循环群 如果循环中的元素是有限的 则称之为有限循环群 可表示为 例 G i i 1 1 是一个乘法群 也是一个有限循环群 G i0 i1 i2 i3 G i 0 i 1 i 2 i 3 第5节线性分组码的群表示 1 元素a称为生成元 例 G 1 i i 1 乘法运算 说明 2 循环群一定是阿贝尔群 3 循环群中元素的个数称为循环群的阶 4 循环群中生成元的个数不一定唯一 第5节线性分组码的群表示 例 G 1 2 3 4 模5乘法运算 G 20 21 22 23 G 30 31 32 33 第5节线性分组码的群表示 4 子群 例6 G 1 i i 1 S 1 1 如果G是一个群 集合SG且在同样的运算规则下满足群的四点性质 我们将S称为G的子群 例7 G 000 010 101 111 S 000 111 第5节线性分组码的群表示 5 陪集和陪集首 陪集的定义若G是一个群 S是G的子群 a为群G中的任意一个元素 我们把集合 a S a x x C 叫做一个陪集 第5节线性分组码的群表示 例 G 000 001 010 011 100 101 110 111 S 000 010 101 111 Coset1 000 S 000 010 101 111 Coset2 001 S 001 011 100 110 Coset1 010 S 010 000 111 101 Coset2 011 S 011 001 110 100 Coset2 100 S 100 110 001 011 Coset1 101 S 101 111 000 010 Coset2 110 S 110 100 011 001 Cose1 111 S 111 101 010 000 第5节线性分组码的群表示 陪集1 000 S 010 S 101 S 111 S 000 010 101 111 陪集2 001 S 011 S 100 S 110 S 001 011 100 110 G 陪集1 陪集2 由上面的例子我们可以看出 所有的陪集中 只有两个不同的陪集 这两个陪集中的元素构成了群G中的所有元素 第5节线性分组码的群表示 群G的任何一个元素必在它的某个陪集中 两个陪集要么完全相同 要么完全不同 不存在两个陪集中的元素部分相同的情况 如果a S是S的一个陪集且b a S 则有b S a S iv 陪集中的元素的个数一定与子群中元素的个数相同 v 互不相同的陪集的个数为 第5节线性分组码的群表示 陪集的性质 陪集1 陪集2 在构成每个陪集的元素中 我们选取海明重量最小的一个来构成陪集 这个元素叫做陪集首 第5节线性分组码的群表示 陪集首 第5节线性分组码的群表示 说明 例G 000 011 101 110 按位模2加 a 线性分组码中的所有有效码字构成在按位模2加运算下的加法子群 因此可以用群去描述线性分组码 可以用群的理论去分析线性分组码 信道编码 信道 010011010110 例 G 0000 1111 0011 按位模2加 第5节线性分组码的群表示 信道编码 信道 0122110210210 例 G 000 111 222 按位模3加 第5节线性分组码的群表示 信道编码 信道 0122110210210 第5节线性分组码的群表示 b 不同的陪集代表不同的出错情况下的信道输出 第5节线性分组码的群表示 第5节线性分组码的群表示 c 陪集首代表最有可能出错的情况 纠错译码的基本原理 讨论 如果k 17 n 23 则表一共有2k 217行 每一行有n k 40个比特 所以在发送端我们需要40 217个比特的存储空间 而在接收端需要40 223个存储单元 表越大 需要的存储空间越大 检索越困难 第5节线性分组码的群表示 在集合F上定义了两种 和 运算 并且在这两种运算下满足以下八点性质 则称F是一个域 记做 F 加法和乘法的封闭性 满足交换律 1 域的定义 第5节线性分组码的群表示 2域 第5节线性分组码的群表示 满足结合律 存在唯一加法单位元 存在唯一乘法单位元 iv 满足结合律 集合F中的任何一个元素 都存在唯一的加法逆元 集合F中的任何一个非零元素 都存在唯一的加法逆元 第5节线性分组码的群表示 第5节线性分组码的群表示 域中的元素可以是有限或无限个 如果域中的元素是有限的q个 则称为伽罗瓦域 记做GF q 2 伽罗瓦域 例 集合F 0 1 2 3 4 它的模5加法与模5乘法下是一个5阶伽罗瓦域 由乘法和加法表 可以很直观地看出 它是一个伽罗瓦域 第5节线性分组码的群表示 1 写出一个加法群和一个乘法群 要求群中元素不少于5个 一定要指明其运算法则 并对其定义中的四点性质进行说明 2 写出一个循环群 先说明它是一个群 然后写出生成元 3 写出一个群以及它的一个子群 并写出该子群的陪集 指明陪集首 4 写出一个域的例子 并对其八点性质进行说明 作业 5 令G取一切有理数对 a b 所构成的集合 且a 0 若定义有理数对的乘法规则为 a1 b1 a2 b2 a1a2 a2b1 b2 问G对于该乘法是否构成群 为什么 作业 3基于子群的线性分组码的一种可行的编码方法 由前面线性分组码所定义可知 它必须满足以下条件 i 全零码字必须包含在其中 ii 几个码字的线性组合必为另外一个有效码字 所以二进制线性分组码能够被看作一个在按位模2和运算下的加法子群 其加法单位元就是全零码字 例 000 010 101 111 第5节线性分组码的群表示 例 写出包含下列元素的线性分组码 1 1100 0100 0011 二进制伽罗瓦域 1100 0100 10001100 0011 1111 0100 0011 01111100 0100 0011 1011 C 0000 1100 0100 0011 1000 1111 0111 1011 线性分组码C的最小海明距离为1 第5节线性分组码的群表示 第5节线性分组码的群表示 2 12 21 GF 3 12 21 0012 2 21 21 2 12 21 12 C 00 12 21 最小海明距离为2 第5节线性分组码的群表示 2 12 2 21 00 1一个简单的例子 之所以要介绍线性空间 是因为任何一个字都可以看作线性空间的一个矢量 所有线性分组码的编码过程就可以看作矢量的空间变换过程 第6节线性分组码的线性空间表示 假设编码为二进制 k 2 n 3 也就是将需要编码的比特流划分成2比特的分组 然后编码成3比特 其编码过程如下图所示 两比特的分组的可能组合有以下四种 00 01 10 11在二维空间表示如右图所示 第6节线性分组码线性空间表示 第6节线性分组码线性空间表示 如果将该二维空间的矢量搬移到如图所示的三位空间的二维子空间 则可得到如中图所示的黄色平面 右图为编码 可以清楚看出 进行该变换后 码字之间的距离明显拉大了 也就是海明距离发生了变化 第6节线性分组码线性空间表示 在上述的编码中 部分码字的海明距离增加了 但最小海明距离仍为1 总体来说不是一种很好的编码 但如果我们将原始码的二维空间映射左下图的黄色平面上 则可得到最小海明距离为2的编码 第6节线性分组码线性空间表示 注意 在二进制中 点 1 1 2 和点 1 1 0 是同一个点 因此左图黄色平面与中图黄色平面为同一平面 2线性空间 1 线性空间的定义 定义域 F 上的所有的n重矢量集合V Vi 其中Vi vi1 vi2 vi3 vin 矢量的集合叫做F域上的n维空间 第6节线性分组码线性空间表示 说明 1 矢量是可以平移的 2 线性空间的每一个点与一个以原点为起点的矢量一一对应 3 线性空间与域有关 例 在域GF 2 上 二维空间有无穷多个一维子空间 而在GF 2 上 二维空间只有三个一维子空间 第6节线性分组码线性空间表示 在域GF 3 上 三维空间有无穷多个二维子空间 而在域GF 2 3上 三维空间只有七个二维子空间 第6节线性分组码线性空间表示 2 线性空间的性质 i 任意矢量与实数域中任意元素的乘积仍为原空间的一个矢量 第6节线性分组码线性空间表示 ii 满足分配律和结合律 iii k维空间所有矢量的集合是一个加法群 第6节线性分组码线性空间表示 3 线性相关 设vi是n维空间的矢量 ai是GF q 上的不全为零的元素 若能够找到一组ai使等式 则称这些矢量线性相关 第6节线性分组码线性空间表示 4 线性空间的基础矢量 如果我们有k个线性无关的矢量V1 V2 Vk 它们可以构成一个k为线性空间Vk 我们将这k个矢量称作空间Vk的一组基础矢量 第6节线性分组码线性空间表示 例 在一维空间 任意选择一个矢量 其它所有矢量都可以用这个矢量的线性形式表示 例 在二维空间 任意选择两个线性无关的矢量 其它所有矢量都可以用两个矢量的线性组合形式表示 第6节线性分组码线性空间表示 5 线性子空间 如果矢量Vs是矢量群V的一个子群 我们称空间Vs为空间V的子空间 V1 1 0 0 一维三重空间 第6节线性分组码线性空间表示 S 000 001 010 011 100 101 110 111 S1 000 011 101 110 V2 0 1 0 V1 1 0 0 二维三重空间 第6节线性分组码线性空间表示 如果我们从n维空间中选取k个线性无关的是矢量 则这些矢量可以确定一个n重k维子空间 子空间中的任意一个矢量均可以用这k个线性无关矢量的线性组合表示出来 第6节线性分组码线性空间表示 6 正交矢量与正交空间 i 正交矢量 如果两个矢量的内积为0 则这两个矢量正交 第6节线性分组码线性空间表示 如果两个矢量 其内积为 如果两个矢量正交 则有 第6节线性分组码线性空间表示 ii 如果一个空间中的任何一个非0矢量与另外一个空间中的任何一个非0矢量正交 则这两个空间正交 第6节线性分组码线性空间表示 6 对偶空间 i S1 S且S2 S ii dimension S1 dimension S2 dimension S 两个子空间S1和S2同属线性空间S 两个子空间的维数之和等于线性空间S的维数 两个子空间只相交于坐标原点 且两个子空间正交 则这两个子空间互为对偶空间 iii S1 S2 0 注意 互为对偶空间的两个空间的并集并不等于原空间 第6节线性分组码线性空间表示 iv S1和S2正交 第6节线性分组码线性空间表示 1 任何码字都可以看作一个n重矢量 2 K个线性无关的矢量可以决定一个n重k维子空间 3 所有的许用码字构成n重k维子空间 结论 4 在所有的码字中选出k个线性无关的码字 其它码字都可以由这些码字的线性组合得到 第6节线性分组码线性空间表示 线性分组码的一种可行的编码和解码方法如下图所示 在发送端有一个编码表 表中的原码与信道编码码字一一对应 如果要发送一个原码 则在表中查找该原码对应的码字并将发送出去 在接收端也有一个解码表 表示接收到某个字后应如何译码 第7节线性分组码的生成矩阵及编码 信道编码 信道译码 信道 在二进制编码中 k比特的分组可以有2k个不同的分组 编码后成为2k个n比特的码字 1 几个简单例子 我们知道 线性分组码 n k 是将k个信源码符号的信息序列编码成n个信道码符号组成的码字 即 第7节线性分组码的生成矩阵及编码 码字是由信息序列决定的 即有以下关系 其中fi是线性映射 第7节线性分组码的生成矩阵及编码 第7节线性分组码的生成矩阵及编码 例1 我们知道信息序列的长度k 3 码字长度n 6 码字和信息序列的关系如左图所示 则其编码如右图所示 信息序列 码字 第7节线性分组码的生成矩阵及编码 例2 我们知道信息序列与码字的关系为 k 1 n 5 信息序列 码字 第7节线性分组码的生成矩阵及编码 例3 已知码字和信息序列的关系 偶校验码k 3 n 4 信息序列 码字 一般表达形式 第7节线性分组码的生成矩阵及编码 第7节线性分组码的生成矩阵及编码 此处 C 是线性分组码 I 是信息序列 G 叫做生成矩阵 说明 如果利用生成矩阵 编码是只需要保存生成矩阵 即需要n k比特的存储空间 思考 是不是可以对生成矩阵的元素任意赋值 该如何得到生成矩阵 第7节线性分组码的生成矩阵及编码 1 写出GF 3 上的四维空间的一个三维子空间 列出这个空间的一组基础矢量 2 写出五维空间的一个二维子空间 列出该子空间的一组基础矢量 并指出该子空间的对偶空间 第7节线性分组码的生成矩阵及编码 第7节线性分组码的生成矩阵及编码 由第6节的内容我们知道 任何的 n k 线性分组码都可以看作域GF q n的一个线性子空间 我们可以利用一组基础矢量来生成这个n重k维线性子空间的全部矢量 换句话说就是可以利用k个线性无关的码字的线性组合来得到整个码空间 2 生成矩阵的构成 假设我们知道n重k维子空间的k个线性无关的矢量 则这个空间的所有矢量均可用这k个线性无关矢量的线性组合表示 即 各矢量线性无关说明 第7节线性分组码的生成矩阵及编码 同理 如果知道n重k维码空间的k个线性无关的码字Ci i 1 2 k 则任何一个码字C都可以用这k个线性无关码字的线性组合表示 即 第7节线性分组码的生成矩阵及编码 这k个线性无关的码字可以看作k个线性无关的n重矢量 可表示以下形式 第7节线性分组码的生成矩阵及编码 第7节线性分组码的生成矩阵及编码 由此可以看出 生成矩阵具有以下性质 1 生成矩阵的每一行是一个有效码字 这些码字线性无关 2 生成矩阵是一个k行n列的矩阵 它的秩一定等于k 3 信息序列I 码字C以及生成矩阵G的关系式为 4 对应一种线性分组码 其生成矩阵不唯一 一个空间可以有不同的基础矢量组 许用码字码空间也是这样 因此可以选择k个不同的线性无关码字组构成不同的生成矩阵 第7节线性分组码的生成矩阵及编码 第7节线性分组码的生成矩阵及编码 例 设GF 2 上的线性分组码为C 000 010 101 111 下面分别用不同的基础矢量组构造生成矩阵 由上面的例子可以看出 从qk 22 4个码字中选取k 2个线性无关的码字可以构造生成矩阵 两种不同的生成矩阵得到的许用码字空间相同 这是一个 3 2 线性分组码 3 利用生成矩阵编码 第7节线性分组码的生成矩阵及编码 因此我们可以得到利用生成矩阵进行线性分组码编码的一般原理方框图 K个符号的信息序列分组 送入编码器中 与生成矩阵相乘 得到n符号的码字 并将码字放到信道上 第7节线性分组码的生成矩阵及编码 第7节线性分组码的生成矩阵及编码 例 设有一个GF 2 上的线性分组码 7 3 4 其信息序列及码字如图所示 第7节线性分组码的生成矩阵及编码 如果我们选择红色的三个码字作为基底 即 可以得到如下所示的3 7生成矩阵 通过将简单地将信息序列与生成矩阵相乘 就可以得到该信息序列对应的码字 第7节线性分组码的生成矩阵及编码 可得到如下的生成矩阵 如果选择三个绿色的码字作为基底 即 编码过程如下所示 第7节线性分组码的生成矩阵及编码 第7节线性分组码的生成矩阵及编码 由上面的例子可以看出 生成矩阵的不同只会使得信息序列与码字的对应关系不同 不影响码空间 也不会使得编码的最小海明距离不同 4 系统矩阵及系统码 但是在前一个生成矩阵 1 系统矩阵和系统码 第7节线性分组码的生成矩阵及编码 编码时 我们发现一个有趣的现象 就是码字的前3个符号与信息序列相同 同时我们注意到 生成矩阵的前面的3 3的分块矩阵是一个单位矩阵 假设生成矩阵可以表示成以下的形式 这样的生成矩阵叫做系统矩阵 由系统矩阵得到的编码叫做系统码 第7节线性分组码的生成矩阵及编码 若信息序列为M 则有 我们可以直观看出 码字中的前k个符号等于信息序列 这就是系统码的特点 第7节线性分组码的生成矩阵及编码 2 系统码的编码 系统码的编码方框图如上所示 利用系统矩阵 可以减小编码器需要存储的数据 同时大大减小了计算量 因此系统码是线性分组码编码的首选 第7节线性分组码的生成矩阵及编码 3 生成矩阵的初等变换 如果我们知道一个非系统矩阵的生成矩阵 为了得到一个系统矩阵 是否需要将所有码字写出来并选择适当的码字构成系统矩阵 答案是否定的 我们可以通过矩阵的初等变换来构造一个等效的系统矩阵 生成矩阵的初等变换主要包括以下几个方面 2 矩阵的行乘以一个非0的量 1 矩阵的行与行交换 4 矩阵的列与列之间交换 3 矩阵的行与行之间线性相加 第7节线性分组码的生成矩阵及编码 矩阵行与行之间的变换 不改变码空间 只会影响信息序列与码字的对应关系 列与列之间的变换可能会改变码空间 但两个码空间的各自海明距离一定相同 从而这两种编码也是等效码 第7节线性分组码的生成矩阵及编码 例 P534T16 设线性分组码的生成矩阵为 1 运用矩阵的列变换将G变换为系统形式 第7节线性分组码的生成矩阵及编码 1 6列互换 2 4列互换 3 6列互换 2 写出生成矩阵G对应的所有有效码字 第7节线性分组码的生成矩阵及编码 第7节线性分组码的生成矩阵及编码 4 比较两种编码的特点和它们的纠检错能力 并说明其原因 由G0得到的是系统码 每个码字的的前3个比特正好等于对应的信息序列 两种编码的最小海明距离都是3 能够纠正所有的一位错误或发现所有的两位错误 纠检错能力相同 这是因为G0是由G经过初等变换得到 故两种编码互为等效码 第7节线性分组码的生成矩阵及编码 P534T14 T15 作业 信道是有噪声的 接收到的字通常情况下不是发送的码字 此时接收方首先要根据接收的字判断信道是否出错 如果出错的话 要么请求对方重发 要么根据冗余信息将错误纠正 这就是译码过程了 此前我们并未涉及 这一节主要给大家介绍线性分组码的一种译码方法 标准阵列译码 1 错误矢量 在介绍译码之前 先介绍一下错误矢量这个概念 设发送码字矢量为W 接收字矢量为R 接收字矢量与发送码字之间的差值即为错误矢量E 第8节标准阵列译码 在二进制下 加法运算和减法运算相同 即有 第8节标准阵列译码 错误矢量的海明距离代表接收矢量中出错的位数 对于一个 n k 线性分组码 海明重量为0的错误矢量只有一个 即全0矢量 海明重量为1的错误矢量有n个 海明重量为2的错误矢量有n n 1 2个 依此类推 海明重量为i n i 0 的错误是矢量个数为 第8节标准阵列译码 2 陪集与陪集首 我们知道 码空间是一个n重k维子空间 也是一个子群 包含有qk个元素 对应的群是一个包含qn个元素 任意从群中取一个字 就可以构成码空间的陪集 互不相同的陪集一共有q n k 个 第8节标准阵列译码 例 q 2 n 3 k 2也就是将两个比特的信息序列编码成3个比特 其码空间和完整空间表示为 G 000 001 010 011 100 101 110 111 C 000 011 101 110 陪集1 000 C 000 011 101 110 陪集2 001 C 001 010 100 111 第8节标准阵列译码 从上面的表中可以看出 如果发生错误为000 则接收矢量为表中第二行所示 如果错误矢量为001 则接收矢量为第三行 所有码空间的陪集实际上代表在某种出错情况下接收矢量的集合 第8节标准阵列译码 第8节标准阵列译码 因为k 3 n 7 所有每个陪集中的元素个数为8 一共有16个陪集 由于篇幅关系 我只列出了其中的8个陪集 第8节标准阵列译码 定义 每个陪集中的海明重量最小的一个叫做陪集首 如果有超过一个的元素具有最小海明重量 则任选取一个作为陪集首 第8节标准阵列译码 例 已知群G子群 000 001 010 011 100 101 110 111 及它一个子群S 000 010 101 111 因此有k 2 n 3 这个子群有两个不同的陪集 陪集1 000 S 010 S 101 S 111 S 000 010 101 111 陪集2 001 S 011 S 100 S 110 S 001 011 100 110 G 陪集1 陪集2 第8节标准阵列译码 在第一个陪集中 海明在量最小的是000 因此它就是陪集首 在第二个陪集中海明中量最小的元素有两个 我们任意选取一个作为陪集首 如001 陪集1 陪集2 由上面的例子我们可以看出 所有的陪集中 只有两个不同的陪集 这两个陪集中的元素构成了群G中的所有元素 第8节标准阵列译码 c将第一个和第二个陪集中都没有出现的码字中海明重量最小的一个作为陪集首 构造第三个陪集 如果有多个海明重量最小的一个 则任选一个 d重复以上过程 直到群中所有的qn个元素出现并且只出现一次 这样的陪集共有qn k个 第8节标准阵列译码 从以上分析可以看出 为了找出所有的陪集首并构造所有的陪集而不出差错 一般需要按如下的步骤进行 a将全0码字作为陪集首 构造第一个陪集 b将第一个陪集中没有出现的码字中海明重量最小的一个作为陪集首 构造第二个陪集 如果有多个海明重量最小的一个 则任选一个 第8节标准阵列译码 3 标准阵列 1 定义 一种 n k 线性分组码C的标准阵列是一个qn k qk的矩阵 每一行对应编码C的一个陪集 2 构造标准阵列的步骤 与寻找陪集首的步骤相同 例 写出GF 2 上的线性分组码C 0000 1011 0101 1110 的标准阵列 第8节标准阵列译码 例 写出GF 2 上的线性分组码C 0000 1011 0101 1110 的标准阵列 首先确定n 4 k 2 q 2 写出标准阵列 0000 0001 0010 1000 第8节标准阵列译码 4 标准阵列译码 设信道中每个码符号出错的概率为p 则对于GF 2 上的 n k 线性分组码 不出错的概率为 一位出错的概率为 二位出错的概率为 下面我们介绍利用标准阵列译码的方法 1 标准阵列译码条件 第8节标准阵列译码 i n i 1 位出错的概率为 i 1 n 1 i 0 位出错的概率为 如果要求 即 第8节标准阵列译码 第8节标准阵列译码 其中 互不相同的陪集有 满足 个 也就是有 个陪集首 其中海明重量为 0的有个 海明重量为1的有个 海明重量为2的有个 海明重量为i的应该有小于或等于个 即i为海明重量最大的陪集首的海明重量 第8节标准阵列译码 若 则我可以得到这样的结论 不出错的可能性 大于1位出错的可能性 1位出错的可能性大于两位出错的可能性 依此类推 n 1位出错的可能性小于n位出错的可能性 如果单个符号出错概率大于 i 1 n 1 则上述译码不一定成立 因此接收字最可能是离它最近的码字出错后而来 也就是说接收到一个字后 将之译码成与其海明距离最小的有效码字时出错的可能性最小 这就是满足条件时的译码规则 第8节标准阵列译码 2 标准阵列译码 在满足条件 时 将接收的字译码成与它 海明距离最小的有效码字 一种可行的方法就是将接收字与每个有效码字相减 比较差值的海明重量 选择海明重量最小的一个差值作为错误矢量 但是这种方法不直观 而且比较繁琐 第8节标准阵列译码 回过头来看看标准阵列 我们可以发现 如果将每个接收字译码成这个字在表中所在列的最上面的一个码字 恰好能满足将海明距离最小的有效码字的条件 因此标准阵列译码的译码方法就是 将接收的字译码它在标准阵列中所在列的最上面一个码字 第8节标准阵列译码 第8节标准阵列译码 例 已知GF 2 上的线性分组码C 0000 1011 0101 1110 试利用标准阵列译码方法对接收矢量R 1101进行译码 1 写出标准阵列 d 1101 0000 3 d 1101 1011 2d 1101 0101 1 d 1101 1110 2 讨论 2 标准阵列译码 我们发现1101在第三列 对应的码字为W 0101 对应的错误矢量为E 1000 第8节标准阵列译码 从上一节我们知道 通过生成矩阵 大大地提高了线性分组码地编码效率 那么能否找到一种类似的方法 用以提高解码效率呢 答案是肯定的 这就是一致校验矩阵 一种有效的线性分组码是一个n重k维子空间 子空间中的每一个矢量对应一个码字 码空间的对偶空间是一个n重 n k 维子空间 对偶空间与码空间正交 因此对偶空间中的任意非0矢量与码空间中的任意非0矢量正交 1 一致校验矩阵的定义 第9节一致校验矩阵 假设已经找到了对偶空间的r个线性无关矢量 并用这r个矢量构成了一个矩阵 那么这个矩阵就叫做一致校验矩阵 记作 H 码空间的k个线性无关矢量的线性组合何以用来表示码空间的任意矢量 也就是任何码字 同样对偶空间的r n k个线性无关的矢量可以表示对偶空间的任意矢量 第9节一致校验矩阵 2 一致校验矩阵的特征 1 一致校验矩阵是一个r n阶矩阵 2 一致校验矩阵各行组成的矢量线性无关 3 若c是任意码字 H是一致校验矩阵 则必有 3 一致校验矩阵与生成矩阵的关系 第9节一致校验矩阵 4 一致校验矩阵的构造 假设已知生成矩阵 设一致校验矩阵为 第9节一致校验矩阵 第9节一致校验矩阵 说明 一致校验矩阵不唯一 不方便直接求出 如果我们找到一个r n的矩阵 各行互不相关 且与生成矩阵的乘积为0矩阵 则这个矩阵就是与该生成矩阵对应的一个一致校验矩阵 第9节一致校验矩阵 定理 若生成矩阵为系统矩阵 即 则矩阵 是G0的一致校验矩阵 证明 因为H0右边是一个r r的单位矩阵 所以r个行向量 一定线性无关 生成矩阵确定 则码空间确定 对偶空间也将确定 但是一致校验矩阵不唯一 第9节一致校验矩阵 5 一致校验矩阵与线性分组码检纠错能力的关系 定理 线性分组码的最小海明距离等于一致校验矩阵最小线性相关列向量数 证明 如果一致校验矩阵H已知 则对偶空间确定 任何与对偶空间正交的矢量一定落在码空间 令 第9节一致校验矩阵 将一致校验矩阵按列划分成n个分块矩阵 根据分块矩阵的乘法可以得到上式 第9节一致校验矩阵 第9节一致校验矩阵 假设一致校验矩阵中有s列线性相关 即 现有一个字 满足 即 a必然是一个有效码字 且a的海明重量为s 若一致校验矩阵中有s列线性相关 则必然至少有一个海明重量为s的码字 如果一致校验矩阵中最少有d列线性相关 则对应的码字的最小海明重量为d 因为线性分组码的最小海明距离等于其非0码字的最小海明重量 所有这种编码的最小海明距离也应为d 第9节一致校验矩阵 第9节一致校验矩阵 第9节一致校验矩阵 例 有一个 7 4 线性分组码 其生成矩阵如下 分析 试求出其最小海明距离 因为第1 2 6列相加为0 且没有任何两列相加为0 所以该线性分组码的最小海明距离为3 第9节一致校验矩阵 例 构造一个 4 3 2 线性分组码 分析 d 2 第9节一致校验矩阵 第9节一致校验矩阵 生成矩阵为 标准阵列译码虽然直观 但如果n k太大 存在存储空间大检索困难的问题 因此我们要寻求更为方便和快捷的方法 这就是伴随式译码 1 伴随式 Syndrome症状 我们知道 任何一个有效码字与一致校验矩阵的转置的乘积为0矩阵 那么可以得到以下等式 我们把S叫作R的伴随式 第10节伴随式译码 2 译码表 线性分组码有多少陪集 就有多上陪集首 就有多少伴随式 也就是说陪集首与伴随式一一对应 对于GF q 上的 n k 线性分组码 有m qn k个陪集 每个陪集首称为一个错误模式 或者叫错误图样 因此可以得到如下形式的表 第10节伴随式译码 这样的表称为译码表 第10节伴随式译码 3 伴随式译码方法 从上面的等式我们可以看出 任何错误矢量相同的接收字都具有相同的伴随式 而标准阵列中的每一行 一个陪集 的所有字都具有相同错误矢量 因此具有相同的错误矢量 伴随式相同 也就是具有相同的 症状 因此我们可以用伴随式确定错误矢量 再利用公式 求出接收矢量译码后的码字 第10节伴随式译码 第10节伴随式译码 例已知线性分组码C 0000 1011 0101 1110 标准阵列如下图所示 写出译码表并对接收矢量1111进行译码 1 由C很容易知道 k 2 n 4 n k 2 其生成矩阵不唯一 为了计算方便选择系统生成矩阵 第10节伴随式译码 一致校验矩阵为 根据下面的公式 第10节伴随式译码 很容易计算出每一行的伴随式相同且为下表中最后一列 相应的译码表为 第10节伴随式译码 2 如果接收矢量为R 1111 则其伴随式为 查译码表 伴随式S 01对应的错误图样为E 0001 所有接收矢量R译码后的码字为 W R E 1111 0001 1110 与标准阵列译码比较 二者译码后的结果完全相同 第10节伴随式译码 4 伴随式译码的步骤 根据S EHT写出译码表 计算接收矢量R的伴随式 从译码表中找到R的伴随式所对应的错误矢量 也就是错误图样E 从接收矢量R中减去错误样图E 得到的结果就是R所对应的码字 第10节伴随式译码 5 存在的问题 有时需要列出标准阵列之后才能写出译码表 在下一节我们将了解到 完备码不需要知道标准阵列就可以直接写出译码表 第10节伴随式译码 P535T21 设 6 3 线性分组码的生成矩阵为 1 写出所有的有效码字 2 排除标准阵列 并进行译码 3 写出相应的一致校验矩阵 4 写出译码表 5 若接收序列为R1 111100 R2 100001 R3 001011 利用译码表进行译码 第10节伴随式译码 1 写出所有的有效码字 第10节伴随式译码 2 排除标准阵列 并进行译码 第10节伴随式译码 接收的字译码成该字在标准阵列中的所在列的最上面一个元素 3 写出相应的一致校验矩阵 第10节伴随式译码 4 写出译码表 第10节伴随式译码 5 若接收序列为R1 111100 R2 100001 R3 001011 利用译码表进行译码 若R1 111100 则其伴随式为 从译码表中可以看出 对应的错误样图为 所以译码后的码字为 若R2 100001 则其伴随式为 从译码表中可以看出 对应的错误样图为 所以译码后的码字为 第10节伴随式译码 若R3 001011 则其伴随式为 从译码表中可以看出 对应的错误样图为 所以译码后的码字为 第10节伴随式译码 生成矩阵 分组 信道 分组 一致校验矩阵 译码表 至此 我们写出线性分组码编解码过程的方框图 在发送端 利用生成矩阵信源符号进行编码 然后将码字送入信道 在接收端 利用译码表和一致校验矩阵进行解码 第11节线性分组码的残留误码率 在上一节我们提到 只有当单个符号出错的概率p小于 i 1 n 1 时 也就是说i个符号出错的概率小于i 1个符号出错的概率时 并且错误矢量正好时错误图样中的一种时 利用标准阵列或伴随式的译码方法才不会出错 实际上码字在信道中传输时 不同的自然信道单个符号出错的可能性不同 而且错误矢量也不一定是错误样图 因此 即使经过信道编码 译码之后的编码信道 也可能会出错 也就是说有一定的残留误码率 假设在所有的错误图样中 海明重量为i有 i个 也就是说能够纠正 i种i位出错的情况 因为二进制单符号信道是最典型的信道 因此我们假设该信道单个符号出错的概率为p 则 第11节线性分组码的残留误码率 一个码字不出错或出错后能纠正的概率为 因此 一个码字出错后不能纠正的概率为 Example考虑一种编码C 0000 1011 0101 1110 求其残余误码率Perr 分析 先写出标准阵列 并写出译码表 为了方便起见 将它们放在同一个表里 第11节线性分组码的残留误码率 从表中可以看出 能构纠正的0位错误有1种 即 0 1 一位出错的情况有四种 但是能够纠正的1位出错情况只有三种 即 1 3 能够纠正的两位及两位以上的情况为0 即 i 0 i 2 那么残留误码率为 第11节线性分组码的残留误码率 讨论 当p 0 01时 则不进行信道编码时 每个信息序列出错的可能性为 当不进行信道编码时 每个信息序列不出错的可能性为 第11节线性分组码的残留误码率 不进行信道编码时 每个信息序列出错的可能性为 若p 0 1 则残留误码率为 作业 作业 P535T21T25 1 2 3 4 5 第12节完备码 对于GF q 上的线性分组码 n k 任何一个以某个码字为球心半径为1的球上有个字 半径为2的球面上有 个字 依