《信道编码2》由会员分享，可在线阅读，更多相关《信道编码2（33页珍藏版）》请在金锄头文库上搜索。
1、 对二进制编码，对二进制编码， c c 和和 m m 都是二元向量，都是二元向量， ， 向量与矩阵，矩阵与矩阵之间的运算是模二加和模向量与矩阵，矩阵与矩阵之间的运算是模二加和模 二乘运算。二乘运算。 下表是模二加和模二乘法运算表：下表是模二加和模二乘法运算表： 模二加法模二加法 模二乘法模二乘法 +0 1 0 1 0 1 1 0 0 1 0 1 0 0 0 1 例例1 1 (4, 3)(4, 3)偶校验码是一个偶校验码是一个(4, 3)(4, 3)线性分组码，其生成线性分组码，其生成 矩阵为矩阵为 这里的运算都是模二加和模二乘运算。这里的运算都是模二加和模二乘运算。 线性分组码的性质：线性分组
2、码的性质： (1)(1)零向量零向量 是一个码字，称为零码字。是一个码字，称为零码字。 (2)(2)任意两个任意两个码字的和是一个码字。码字的和是一个码字。 (3)(3)任意任意码字都是码字都是G G的的行向量行向量 的线性组合的线性组合 。 定理： ( (n n, , k k) )线性分组码是线性分组码是n n维线性空间中维线性空间中 的的n n长长向量构成的一个向量构成的一个k k维线性子空间。维线性子空间。 (4)(4)线性分组码的最小距离等于最小非零码字重量。线性分组码的最小距离等于最小非零码字重量。 (2)(2) 因为对二元向量因为对二元向量, ,有有 所以所以 由由(4)(4)可给
3、出线性分组码的最小距离的计算和其可给出线性分组码的最小距离的计算和其 检纠错能力。检纠错能力。 由偶校验码的检错方法，可计算接收向量由偶校验码的检错方法，可计算接收向量 r r 的校验方的校验方 程是否是程是否是0 0来判断传输是否可能有错，那么应该存在一来判断传输是否可能有错，那么应该存在一 个矩阵满足个矩阵满足 (3)(3) H H T T 的每一列的每一列( (H H的的每一行每一行) )确定了线性分组码的一个可能确定了线性分组码的一个可能 校验方程，校验方程， H H的线性不相关行数的线性不相关行数k k最少要等于该码字的最少要等于该码字的 校验方程数。校验方程数。 H H称为称为(
4、(n,kn,k) )线性分组码的一致校验矩阵线性分组码的一致校验矩阵 。 列向量 因生成矩阵因生成矩阵G G的每一行都是一个码字，再由的每一行都是一个码字，再由(3)(3)式，有式，有 (4)(4) 由线性空间理论，当由线性空间理论，当H H的行秩的行秩 r r 时，时， H H的作为一个的作为一个 ( (n,rn,r) )线性分组码的生成矩阵所生成的码与线性分组码的生成矩阵所生成的码与G G对应空间对应空间 正交的正交的r r 维线性子空间，称为维线性子空间，称为( (n,kn,k) )线性分组码的对偶线性分组码的对偶 码或对偶空间，其维数关系为码或对偶空间，其维数关系为 (5)(5) 再由
5、再由(4)(4)式可得一个重要结论：式可得一个重要结论： 定理定理：任何满足：任何满足 的的n n维向量维向量 称都是称都是( (n,kn,k) )线性分组码的一个码字。线性分组码的一个码字。 G G行初等变换化为：行初等变换化为： (7)(7) 由由 生成生成 ( (n,kn,k) )线性分组码称为系统码。对系统码容线性分组码称为系统码。对系统码容 易求出相应的一致校验矩阵易求出相应的一致校验矩阵H H S S (8)(8) G G和和H H s s 仍然满足仍然满足 例例2 2 一个一个(5,3)(5,3)线性码的生成矩阵为线性码的生成矩阵为 得得(5,3)(5,3)线性码和对偶码线性码和
6、对偶码 定理定理：线性分组码的最小码距：线性分组码的最小码距 ，当且仅当，当且仅当 一致校验矩阵一致校验矩阵H H为中为中d d1 1列线性无关且存在列线性无关且存在d d 列线列线 性相关。性相关。 消息mG生成码字Gs生成码字 对偶码对偶码码字 000 001 010 011 100 101 110 111 00000 11010 01011 1001 10110 01100 11101 00111 00000 00111 01011 01100 10001 10110 11010 11101 00000 11101 01110 10011 6.2.1 线性分组码的译码 (9) 图图1 1
7、 译码的概念 译码的概念 定义定义: (: (n n, , k k) )线性分组码的伴随式是一个线性分组码的伴随式是一个r r( (r=n-kr=n-k) )维向维向 量量s s (10)(10) 根据根据(6)(6)和和(9)(9)式可得式可得 (11)(11) cr e m 编码器 编码器 y 因此，若 ，则传输出错因此，若 ，则传输出错; ; 若 若 ，则传输，则传输 中要么无差错，要么差错图案恰好是一个码字。中要么无差错，要么差错图案恰好是一个码字。 译码方法译码方法I I：采用伴随式纠错译码采用伴随式纠错译码 (1)(1)构造差错图案表构造差错图案表( (s s, , e e) )。
8、 (2)(2)由接收向量由接收向量r r计算伴随式计算伴随式s s 。 (3)(3)查查( (s s, , e e) )表得表得e .e . (4)(4)纠错计算纠错计算 译码方法译码方法II II：采用标准阵列译码采用标准阵列译码 下表是标准阵列表： 下表是标准阵列表： 由码字组成 c1为全零码字 e1(00) 对越小的i，ei 选择越容易出现的差错图案，对BSC，ei满足 Bj Ai 完备译码：完备译码： 限定距离译码：限定距离译码： ci er ci er 完备译码完备译码 限定距离译码限定距离译码 译码成功 译码失败 发送码字发送码字 c c c c t t t t c c 信道信道
9、c c t t cc D r = 纠错 检错 错误译码 不可检测错误 图图3 3 各种译码情况 各种译码情况 以下以 以下以BSCBSC信道为分析模型：信道为分析模型： A Ai i 为线性分组码中重量为为线性分组码中重量为 i i 和码的个数，称集合和码的个数，称集合 A A 0 0 , , A A1 1 , , A A2 2 , , , , A A d d minmin , , , , A An n 为码的重量分布为码的重量分布 ，重量分布多项式：，重量分布多项式： （1313） 一个码的重量分布多项式一个码的重量分布多项式 A A( (x x) ) 与其对偶码的重量分与其对偶码的重量分
10、布多项式布多项式 A A( (x x) )的关系满足马克威廉斯的关系满足马克威廉斯( (Mac Williams)Mac Williams) 恒等式恒等式: : 线性分组码的不可检测概率线性分组码的不可检测概率p pud ud是差错图案恰为一个非 是差错图案恰为一个非 零码字的概率，对于二元码在零码字的概率，对于二元码在p pud ud p p 的的BSCBSC上有）上有） (14)(14) 如果一个码的对偶码有较大的如果一个码的对偶码有较大的d dmin min = = d ,d ,则则 n n 足够大时，有不可检测概率足够大时，有不可检测概率 （1515） 纠正小于等于纠正小于等于t t
11、个差错的概率个差错的概率 (16)(16) 记记D D i i 是重量为是重量为i i 且译为错误码字的接收向量的且译为错误码字的接收向量的r r 个个 数，即数，即 错误译码的概率错误译码的概率 译码失败的概率译码失败的概率 若考虑码字是等概率发送的，则错误译码的误码率若考虑码字是等概率发送的，则错误译码的误码率 (19)(19) 在统计意义下，有在统计意义下，有 二元消息源 纠错 编码 数字 信道 消息 恢复 纠错 译码 图图4 4 译码率统计译码率统计 发送全0码字，并 错为j 重码的概率 字错必然至少有字错必然至少有2t+12t+1位码字比特错，每个码字平位码字比特错，每个码字平 均有
12、 消息位比特错，有以下渐近关系均有 消息位比特错，有以下渐近关系 译码失败的概率译码失败的概率 (20)(20) 译码后总误码率译码后总误码率 (21)(21) 一个线性分组码的结构参数一个线性分组码的结构参数( (称为码限称为码限) )主要有：主要有： (1)(1)码长码长n n . . (2) (2)消息位长消息位长k k ，码率码率R R= =k k/ /n n和校验位长和校验位长r r = = n n k k . . (3) (3)码的字数码的字数 M M ，对，对q q 元分组码元分组码 M M = = q q k k . . (4) (4)最小码距最小码距 d d ，可纠差错数可纠
13、差错数t t =( =(d d - 1)/2- 1)/2。 对于一个对于一个(n, k, d )(n, k, d )二元线性分组码存在如下码限：二元线性分组码存在如下码限： (1)(1)辛格里顿限辛格里顿限(S(S限限) ) (22)(22) (2)(2)普罗特金限普罗特金限(P(P限限) ) (23)(23) 当当n n ，充分大时，有充分大时，有 (3)(3)汉明限汉明限(H(H限限) ) 对于一个对于一个( (n n, , k k, 2, 2t t + 1 ) + 1 ) 码满足码满足 (24)(24) 使使(24)(24)式等式成立的码称为完备码。式等式成立的码称为完备码。 当当n n
14、 充分大时，有充分大时，有 其中其中 (4)(4)瓦尔沙莫夫瓦尔沙莫夫- -吉尔伯特限吉尔伯特限(VG(VG限限) ) 存在某个二元存在某个二元( (n n, , k k, d ) , d ) 码满足码满足 (25)(25) 当当n n 充分大时，存在某个二元充分大时，存在某个二元( (n n, , k k, d ) , d ) 码满足码满足 图二元分组码的主要码限图二元分组码的主要码限 辛格里顿限辛格里顿限 普罗特金限普罗特金限 汉明限汉明限 VGVG限限 0.156 0.25 0.50.156 0.25 0.5 0.40.4 1 1 好码区 6.2.3 6.2.3 码例与码的重构码例与码的
15、重构 汉汉明码明码 二元二元( (n n, , k k, d ) , d ) 汉明码是一种汉明码是一种d d = 3= 3的完备码，满足的完备码，满足 (24)(24) (27) (27) 其中 其中 是全部可能的非零是全部可能的非零m m 元组元组 。由于的任意两列都不相同，存在三列线性相关。由于的任意两列都不相同，存在三列线性相关 ，所以，所以d d = 3= 3。 汉明码的对偶码是一个汉明码的对偶码是一个(2(2m m - 1, - 1, m m ) ) 的线性分组码的线性分组码, ,其 其 所有非零码字重量都是所有非零码字重量都是2 2 m m ，称为最大长度码、等 ，称为最大长度码、等 距码或单型码。距码或单型码。 例例. (7,4). (7,4)汉明码，其系统码汉明码，其系统码 编码方程编码方程 编码电
