信息论与编码-第6章-第17、18讲-信道编码-线性分组码.ppt

2020 1 22 1 6 1一般概念6 2一致监督方程和一致监督矩阵6 3线性分组码的生成矩阵6 4线性分组码的编码6 5线性分组码的最小距离 检错和纠错能力6 6线性分组码的译码6 7线性分组码的性能6 8汉明码 6线性分组码 2020 1 22 2 线性分组码的编码 线性分组码的编码过程分为两步 把信息序列按一定长度分成若干信息码组 每组由k位组成 编码器按照预定的线性规则 可由线性方程组规定 把信息码组变换成n重 n k 码字 其中 n k 个附加码元是由信息码元的线性运算产生的 信息码组长k位 有2k个不同的信息码组 则有2k个码字与它们一一对应 6 1一般概念 2020 1 22 3 名词解释线性分组码 通过预定的线性运算将长为k位的信息码组变换成n重的码字 n k 由2k个信息码组所编成的2k个码字集合 称为线性分组码 码矢 一个n重的码字可以用矢量来表示C Cn 1 Cn 2 C1 C0 所以码字又称为码矢 n k 线性码 信息位长为k 码长为n的线性码 编码效率 编码速率 码率 传信率 R k n 它说明了信道的利用效率 R是衡量码性能的一个重要参数 6 1一般概念 2020 1 22 4 1 一致监督方程编码就是给已知信息码组按预定规则添加监督码元 以构成码字 在k个信息码元之后附加r r n k 个监督码元 使每个监督元是其中某些信息元的模2和 举例 k 3 r 4 构成 7 3 线性分组码 设码字为 C6 C5 C4 C3 C2 C1 C0 C6 C5 C4为信息元 C3 C2 C1 C0为监督元 每个码元取 0 或 1 监督元可按下面方程组计算 6 2一致监督方程和一致监督矩阵 2020 1 22 5 一致监督方程 一致校验方程 确定由信息元得到监督元规则的一组方程称为监督方程 校验方程 由于所有码字都按同一规则确定 又称为一致监督方程 一致校验方程 由于一致监督方程是线性的 即监督元和新信源之间是线性运算关系 所以由线性监督方程所确定的分组码是线性分组码 6 2一致监督方程和一致监督矩阵 2020 1 22 6 2 举例信息码组 101 即C6 1 C5 0 C4 1代入 6 2 1 得 C3 0 C2 0 C1 1 C0 1由信息码组 101 编出的码字为 1010011 其它7个码字如表6 2 1 6 2一致监督方程和一致监督矩阵 2020 1 22 7 3 一致监督矩阵为了运算方便 将式 6 2 1 监督方程写成矩阵形式 得式 6 2 2 可写成H CT 0T或C HT 0CT HT 0T分别表示C H 0的转置矩阵 6 2一致监督方程和一致监督矩阵 2020 1 22 8 系数矩阵H的后四列组成一个 4 4 阶单位子阵 用I4表示 H的其余部分用P表示 6 2一致监督方程和一致监督矩阵 2020 1 22 9 推广到一般情况 对 n k 线性分组码 每个码字中的r r n k 个监督元与信息元之间的关系可由下面的线性方程组确定 6 2一致监督方m程和一致监督矩阵 2020 1 22 10 令上式的系数矩阵为H 码字行阵列为C 6 2一致监督方程和一致监督矩阵 2020 1 22 11 4 一致监督矩阵特性对H各行实行初等变换 将后面r列化为单位子阵 于是得到下面矩阵 行变换所得方程组与原方程组同解 监督矩阵H的标准形式 后面r列是一单位子阵的监督矩阵H H阵的每一行都代表一个监督方程 它表示与该行中 1 相对应的码元的模2和为0 6 2一致监督方程和一致监督矩阵 2020 1 22 12 H的标准形式还说明了相应的监督元是由哪些信息元决定的 例如 7 3 码的H阵的第一行为 1011000 说明此码的第一个监督元等于第一个和第三个信息元的模2和 依此类推 H阵的r行代表了r个监督方程 也表示由H所确定的码字有r个监督元 为了得到确定的码 r个监督方程 或H阵的r行 必须是线性独立的 这要求H阵的秩为r 若把H阵化成标准形式 只要检查单位子阵的秩 就能方便地确定H阵本身的秩 6 2一致监督方程和一致监督矩阵 2020 1 22 13 1 线性码的封闭性线性码的封闭性 线性码任意两个码字之和仍是一个码字 定理6 2 1 设二元线性分组码CI CI表示码字集合 是由监督矩阵H所定义的 若U和V为其中的任意两个码字 则U V也是CI中的一个码字 证明 由于U和V是码CI中的两个码字 故有HUT 0T HVT 0T那么H U V T H UT VT HUT HVT 0T即U V满足监督方程 所以U V一定是一个码字 6 3线性分组码的生成矩阵 2020 1 22 14 2 线性分组码的生成矩阵 n k 线性码是n维线性空间Vn中的一个k维子空间Vk 在这个k维子空间中 一定存在k个线性独立的码字 g1 g2 gk 那么 任何码字C都可以表示为这k个码字的一种线性组合 即 6 3线性分组码的生成矩阵 2020 1 22 15 G中每一行gi gi1 gi2 gin 都是一个码字 对每一个信息组m 由矩阵G都可以求得 n k 线性码对应的码字生成矩阵 由于矩阵G生成了 n k 线性码 称矩阵G为 n k 线性码的生成矩阵 n k 线性码的每一个码字都是生成矩阵G的行矢量的线性组合 6 3线性分组码的生成矩阵 2020 1 22 16 线性系统分组码通过行初等变换 将G化为前k列是单位子阵的标准形式 6 3线性分组码的生成矩阵 2020 1 22 17 线性系统分组码 用标准生成矩阵Gk n编成的码字 前面k位为信息数字 后面r n k位为校验字 这种信息数字在前校验数字在后的线性分组码称为线性系统分组码 当生成矩阵G确定之后 n k 线性码也就完全被确定了 只要找到码的生成矩阵 编码问题也同样被解决了 6 3线性分组码的生成矩阵 2020 1 22 18 3 举例 7 4 线性码的生成矩阵为 6 3线性分组码的生成矩阵 2020 1 22 19 4 生成矩阵与一致监督矩阵的关系由于生成矩阵G的每一行都是一个码字 所以G的每行都满足Hr nCTn 1 0Tr 1 则有Hr nGTn k 0Tr k或Gk nHTn r 0k r线性系统码的监督矩阵H和生成矩阵G之间可以直接互换 6 3线性分组码的生成矩阵 2020 1 22 20 举例已知 7 4 线性系统码的监督矩阵为 6 3线性分组码的生成矩阵 2020 1 22 21 5 对偶码对偶码 对一个 n k 线性码CI 由于Hr nGTn k 0Tr k 如果以G作监督矩阵 而以H作生成矩阵 可构造另一个码CId 码CId是一个 n n k 线性码 称码CId为原码的对偶码 例如 7 4 线性码的对偶码是 7 3 码 7 3 码的监督矩阵H 7 3 是 7 4 码生成矩阵G 7 4 6 3线性分组码的生成矩阵 2020 1 22 22 7 3 码的生成矩阵G 7 3 是 7 4 码监督矩阵H 7 4 6 3线性分组码的生成矩阵 2020 1 22 23 n k 线性码的编码就是根据线性码的监督矩阵或生成矩阵将长为k的信息组变换成长为n n k 的码字 利用监督矩阵构造 7 3 线性分组码的编码电路 设码字矢量为C C6C5C4C3C2C1C0 码的监督矩阵为 6 4线性分组码的编码 2020 1 22 24 根据方程组可直接画出 7 3 码的并行编码电路和串行编码电路 如图6 2 2 6 4线性分组码的编码 2020 1 22 25 1 汉明距离 汉明重量和汉明球汉明距离 距离 在 n k 线性码中 两个码字U V之间对应码元位上符号取值不同的个数 称为码字U V之间的汉明距离 例如 7 3 码的两个码字U 0011101 V 0100111 它们之间第2 3 4和6位不同 因此 码字U和V的距离为4 线性分组码的一个码字对应于n维线性空间中的一点 码字间的距离即为空间中两对应点的距离 因此 码字间的距离满足一般距离公理 6 5线性分组码的最小距离 检错和纠错能力 2020 1 22 26 最小距离 dmin 在 n k 线性码的码字集合中 任意两个码字间距离最小值 叫做码的最小距离 若C i 和C j 是任意两个码字 则码的最小距离表示为码的最小距离是衡量码的抗干扰能力 检 纠错能力 的重要参数 码的最小距离越大 码的抗干扰能力就越强 汉明球 以码字C为中心 半径为t的汉明球是与C的汉明距离 t的向量全体SC t 任意两个汉明球不相交最大程度取决于任意两个码字之间的最小汉明距离dmin 6 5线性分组码的最小距离 检错和纠错能力 2020 1 22 27 6 5线性分组码的最小距离 检错和纠错能力 2020 1 22 28 汉明重量 码字重量 W 码字中非0码元符号的个数 称为该码字的汉明重量 在二元线性码中 码字重量就是码字中含 1 的个数 最小重量 Wmin 线性分组码CI中 非0码字重量最小值 叫做码CI的最小重量 Wmin min W V V CI V 0 最小距离与最小重量的关系 线性分组码的最小距离等于它的最小重量 证明 设线性码CI 且U CI V CI 又设U V Z 由线性码的封闭性知 Z CI 因此 d U V W Z 由此可推知 线性分组码的最小距离必等于非0码字的最小重量 6 5线性分组码的最小距离 检错和纠错能力 2020 1 22 29 2 最小距离与检 纠错能力一般地说 线性码的最小距离越大 意味着任意码字间的差别越大 则码的检 纠错能力越强 检错能力 如果一个线性码能检出长度 l个码元的任何错误图样 称码的检错能力为l 纠错能力 如果线性码能纠正长度 t个码元的任意错误图样 称码的纠错能力为t 6 5线性分组码的最小距离 检错和纠错能力 2020 1 22 30 最小距离与纠错能力 n k 线性码能纠t个错误的充要条件是码的最小距离为 证明 设 发送的码字为V 接收的码字为R U为任意其它码字 则 矢量V R U间满足距离的三角不等式 d R V d R U d U V 6 2 16 设 信道干扰使码字中码元发生错误的实际个数为t 且t td R V t t 6 2 17 由于d U V dmin 2t 1 代入式 6 2 16 得d R U d U V d R V 2t 1 t t 6 2 18 6 5线性分组码的最小距离 检错和纠错能力 2020 1 22 31 上式表明 如果接收字R中错误个数t t 那么接收字R和发送字V间距离 t 而与其它任何码字间距离都大于t 按最小距离译码把R译为V 此时译码正确 码字中的错误被纠正 几何意义 6 5线性分组码的最小距离 检错和纠错能力 2020 1 22 32 最小距离与检错能力 n k 线性码能够发现l个错误的充要条件是码的最小距离为dmin l 1或l dmin 1 6 2 19 证明 设 发送的码字为V 接收的码字为R U为任意其它码字 则 矢量V R U间满足距离的三角不等式 d R V d R U d U V 6 2 20 设 信道干扰使码字中码元发生错误的实际个数为l 且l ld R V l l 6 2 21 由于d U V dmin l 1 代入式 6 2 20 得d R U d U V d R V l 1 l 0 6 2 22 6 5线性分组码的最小距离 检错和纠错能力 2020 1 22 33 上式表明 由于接收字R与其它任何码字U的距离都大于0 则说明接收字R不会因发生l 个错误变为其它码字 因而必能发现错误 几何意义 6 5线性分组码的最小距离 检错和纠错能力 2020 1 22 34 最小距离与检 纠错能力 n k 线性码能纠t个错误 并能发现l个错误 l t 的充要条件是码的最小距离为dmin t l 1或t l dmin 1 6 2 23 证明 因为dmin 2t 1 根据最小距离与纠错能力定理 该码可纠t个错误 因为dmin l 1 根据最小距离与检错能力定理 该码有检l个错误的能力 纠错和检错不会发生混淆 设发送码字为V 接收字为R 实际错误数为l 且tt 1 t 6 2 24 因而不会把R误纠为U 6 5线性分组码的最小距离 检错和纠错能力 2020 1 22 35 几何意义 6 5线性分组码的最小距离 检错和纠错能力 2020 1 22 36 6 5线性分组码的最小距离 检错和纠错能力 2020 1 22 37 当 n k 线性码的最小距离dmin给定后 可按实际需要灵活安排纠错的数目 例如 对dmin 8的码 可用来纠3检4错 或纠2检5错 或纠1检6错 或者只用于检7个错误 6 5线性分组码的最小距离 检错和纠错能力 2020 1 22 38 3 线性码的最小距离与监督矩阵的关系定理6 2 2 设H为 n k 线性码的一致监督矩阵 若H中任意S列线性无关 而H中存在 S 1 列线性相关 则码的最小距离为 S 1 矩阵H的秩为S 定理6 2 3 若码的最小距离为 S 1 则该码的监督矩阵的任意S列线性无关 而必存在有相关的 S 1 列 定理6 2 4 在二元线性码的监督矩阵H中 如果任一列都不是全 0 且任两列都不相等 则该码能纠一个错误 6 5线性分组码的最小距离 检错和纠错能力 2020 1 22 39 1 伴随式和错误检测 用监督矩阵编码 也用监督矩阵译码 接收到一个接收字R后 校验H RT 0T是否成立 若关系成立 则认为R是一个码字 否则判为码字在传输中发生了错误 H RT的值是否为0是校验码字出错与否的依据 伴随式 监督子 校验子 S R HT或ST H RT 如何纠错 设发送码矢C Cn 1 Cn 2 C0 信道错误图样为E En 1 En 2 E0 其中Ei 0 表示第i位无错 Ei 1 表示第i位有错 i n 1 n 2 0 6 6线性分组码的译码 2020 1 22 40 接收字R为R Rn 1 Rn 2 R0 C E Cn 1 En 1 Cn 2 En 2 C0 E0 求接收字的伴随式 接收字用监督矩阵进行检验 ST H RT H C E T H CT H ET 6 2 25 由于H CT 0T 所以ST H ET设H h1 h2 hn 其中hi表示H的列 代入式 6 2 25 得到 6 6线性分组码的译码 2020 1 22 41 总结伴随式仅与错误图样有关 而与发送的具体码字无关 即伴随式仅由错误图样决定 伴随式是错误的判别式 若S 0 则判为没有出错 接收字是一个码字 若S 0 则判为有错 不同的错误图样具有不同的伴随式 它们是一一对应的 对二元码 伴随式是H阵中与错误码元对应列之和 6 6线性分组码的译码 2020 1 22 42 举例 7 3 码接收矢量R的伴随式计算设发送码矢C 1010011 接收码字R 1010011 R与C相同 6 6线性分组码的译码 2020 1 22 43 若接收字中有一位错误 6 6线性分组码的译码 2020 1 22 44 当码元错误多于1个时 6 6线性分组码的译码 2020 1 22 45 伴随式计算电路伴随式的计算可用电路来实现 以 7 3 码为例 设接收字为R R6R5R4R3R2R1R0 伴随式为根据上式可画出伴随式计算电路 如图6 2 7所示 6 6线性分组码的译码 2020 1 22 46 根据上式可画出伴随式计算电路 如图6 2 7所示 6 6线性分组码的译码 作业 补充1 已知 7 4 汉明码的生成矩阵为 1 求该码的全部码字 2 求该码的监督矩阵 3 若接收码字为1101101 计算伴随式 2020 1 22 48 补充2 已知 8 4 系统线性码的监督方程为式中m m3 m2 m1 m0 为信息矢量 C3 C2 C1 C0为编码监督数字 求这个码的监督矩阵和生成矩阵 证明该码的最小距离为4 作业 作业 补充3 设5元线性码L的生成矩阵为 1 确定码L的标准型生成矩阵 2 确定码L的标准型校验矩阵 3 求码L的最小距离