第三章线性分组码.ppt

第三章线性分组码 一 线性分组码的一般性定义 定义 通过预定的线性运算将k维q元 q为素数幂 信息数组变换成n维 n k 码数组 称码字 由qk个码字所成的集合 称为 n k 线性分组码 简称分组码 码字用 cn 1 cn 2 cn k cn k 1 c1 c0 表示 码率 传信率 信道利用率 r k n表示信息位所占的比重 最简单的情况 在后面添加n k个监督元 叫系统码 定义3 2 2 cn k 1 h1 n 1cn 1 h1 n 2cn 2 h1 n kcn 1cn k 2 h2 n 1cn 1 h2 n 2cn 2 h2 n kcn 1 c0 hn k n 1cn 1 hn k n 2cn 2 hn k n kcn 1 h1 n 1h1 n 2 h1 n k10 0cn 1h2 n 1h2 n 2 h2 n k01 0cn 2 0 hn k n 1hn k n 2 hn k n k00 1c0 hct 0t 二 线性分组码的严格数学定义 1 定义gf q 中的元素 q为素数幂 组成的 n k n矩阵 其秩为n k 满足方程hct 0t的矢量c cn 1 cn 2 ci c0 ci gf q 的集合称为 n k 线性分组码 h称为监督 检验 矩阵 hct 0t称为 一致 监督矩阵 为什么秩为n k 一致 同一规则 对h进行初等变换 化为 h1 n 1h1 n 2 h1 n k10 0h2 n 1h2 n 2 h2 n k01 0 hn k n 1hn k n 2 hn k n k00 1 qin k 的形式 称为 h的标准形式 h称为典型监督矩阵 二 线性分组码的严格数学定义2 2 定理1 码的封闭性 设ch为由监督矩阵h定义的分组码 则 c1 c2 ch c1 c2 ch 证明 由c1 ch 得hc1t 0t 由c2 ch 得hc2t 0t 所以h c1 c2 t h c1t c2t hc1t hc2t 0tc1 c2满足hct 0t 所以c1 c2 ch 3 定理2 n k 线性分组码对矢量相加构成阿贝尔群 封闭性 定理1 结合律 有恒等元和逆元 二 线性分组码的严格数学定义3 3 定理3 n k 线性分组码是gf q 上的n维线性空间vn中的一个k维子空间 证 设ch是由监督矩阵h定义的 n k 线性码 1 先证ch为子空间 1 ch是阿贝尔群 定理2 2 a gf q c ch ac ch 3 分配律 c1 c2 ch a b gf q a c1 c2 ac1 ac2且 a b c1 ac1 bc1 4 结合律成立 a1 a2 gf q c ch a1a2 c a1 a2c 2 再证维数为k设 c ch 则hct 0t c与h的每一行矢量正交 故c在由h的行矢量张成的n k维线性子空间vn n k的零空间中 第2章定理17 定理2 6 9 ch中每个码字和h张成的子空间的矢量正交 所以ch为h张成的子空间的零空间 第2章定理16 定理2 6 8 维数为k 第2章定理18 定理2 6 10 二 线性分组码的严格数学定义4 由第2章定理3可知 必存在k个线性独立的码字g1 g2 gk 使 c ch c mn 1g1 mn 2g2 mn kgk mg g1 n 1g1 n 2 g1 0g2 n 1g2 n 2 g2 0 gk n 1gk n 2 gk 0 g g称为 n k 码的生成矩阵 g的标准形式 ikp 称为典型生成矩阵 基不同 g不同 但生成的空间是一样的 不同的g的意义是什么 秩是多少 三 g与h的关系 g的行矢量是码字 hgit 0t 有hgt 0t h与g所张成的空间互为零空间 ch h校验 g生成 cg g校验 h生成 互为对偶码 若ch cg 则称为自对偶码 p62 qin k ikp t qin k iktpt t q pt 0所以p qt或q pt由此得g ikp ik qt h qin k ptin k 三 g与h的关系2 例 已知 7 3 码 p52 例3 1 101 1000111 0100110 0010011 0001 h c c6c5c4c3c2c1c0 由hct 0t得c3 c6 c4c2 c6 c5 c4c1 c6 c5c0 c5 c4 111001111101 p qt g ikp 100 1110010 0111001 1101 三 g与h的关系3 设信息组m m6m5m4 c6 m6c5 m5c4 m4c3 m6 m4 c6 c4c2 m6 m5 m4 c6 c5 c4c1 m6 m5 c6 c5c0 m5 m4 c5 c4 考虑如何用串行方式 三 g与h的关系4 m4m5m6 m4m5 m5m6 m6 m6 m5 m6 m6 m4 m4m5m6 m6 m6 m6 m5 m6 m5 m6 m5 m6 m5 m6 m5 m4 m5 m4 m6 m5 m6 m5 m4 m6 m4 设信息组m m6m5m4 c6 m6c5 m5c4 m4c3 m6 m4 c6 c4c2 m6 m5 m4 c6 c5 c4c1 m6 m5 c6 c5c0 m5 m4 c5 c4 三 g与h的关系5 g 100 1110010 0111001 1101 写成多项式 g1 x x6 x3 x2 x x x5 x2 x 1 x x 1 x4 x3 x2 1 g2 x x5 x2 x 1 x 1 x4 x3 x2 1 g3 x x4 x3 x2 1 g1 x x6 x3 x2 x x x 1 x4 x3 x2 1 x x 1 g3 x g2 x x5 x2 x 1 x 1 x4 x3 x2 1 x 1 g3 x c x m6g1 x m5g2 x m4g3 x m6g1 x m5g2 x m4g3 x m6x x 1 g3 x m5 x 1 g3 m4g3 x m6x2 m6x m5x m5 m4 g3 x m x g3 x 所有码字多项式都是g3 x 的倍式又因为是系统码c x m x xn k r x 0 modg3 x 信息位左移n k位加上监督位 r x m x xn k modg3 x 除法电路 见168页 x6x5x4x3x2x 四 线性分组码的最小距离 检错和纠错能力 检 纠错的必要条件 码字在一些码元发生错误后 还没有变成其它码字 为使码具有强的检错 纠错能力 各码字的距离差别 汉明距离 足够大 线性分组码的最小距离d 最小汉明距离 若 n k 线性分组码的最小距离为d 记为 n k d 定理4 n k 分组码的最小距离d满足 d c1 c2 w c1 c2 w c3 定理5 gf 2 上的 n k d 分组码中任何码字c1 c2满足 w c1 c2 w c1 w c2 2 c1 c2 内积或d c1 c2 w c1 w c2 推论1 gf 2 上的 n k 分组码满足 c1 c2 c3 n k d c1 c2 d c2 c3 d c1 c3 c1 c2 c3 d c1 c2 d c1 c3 d c2 c3 四 线性分组码的最小距离 检错和纠错能力2 定理6 p12定理1 3 1 任一 n k d 若要 1 检测e个错误 则要求d e 1 2 纠正t个错误 则要求d 2t 1 3 纠正t个错误 或检测e t 个错误 则要求d t e 1 4 纠正t个错误和 个删除 则要求d 2t 1 e e 1 t t 1 t t t t 1 e e t t t t 五 线性分组码的译码 1 伴随式 c r c e e hct 0thrt h c e t hct het het定义s rht称为接收字r的伴随式 校正子 h1 n 1h1 n 2 h1 0h2 n 1h2 n 2 h2 0 hn k n 1hn k n 2 hn k 0 h hn 1 hn 2 h1 h0 设e en 1 en 2 e1 e0 0 ei1 ei2 eit 0 s eht 0 ei1 ei2 eit 0 hn 1thn 2t h1th0t ei1hi1t ei2hi2t eithitt 发生错误的位所对应的列向量的线性组合 五 线性分组码的译码2 例 7 3 码 h 101 1000111 0100110 0010011 0001 s rht r6r5r4r3r2r1r0 101 1000111 0100110 0010011 0001 t r6 r4 r3r6 r5 r4 r2r6 r5 r1r5 r4 r0 t s3s2s1s0 五 线性分组码的译码3 c 1010011 e 0100000 r 1110011 s rht eht 0100000 101 1000111 0100110 0010011 0001 t 0111 t c 1010011 e 1001000 r 0011011 s rht eht 1001000 101 1000111 0100110 0010011 0001 t 1110 t t 1000 0110 五 线性分组码的译码4 若e 0 0 ei 0 0 s eihit若为二进制 则s hit若要各列彼此区分 各列互不相同 即任意两列线性无关h n k n最多可构成2n k 1个互不相同的非零列 即必须保证2n k 1 n取下限 得2n k 1 n 即为汉明码 2 汉明码 定义 定义3 3 1 gf 2 上的线性分组码 n k d 称为汉明码 若满足下列条件 1 n 2m 1 m n 且m 3 2 k 2m m 1 3 n k m 4 d 3 五 线性分组码的译码5 构造办法 a 按h的二进制数的顺序排列 例gf 2 上的 7 4 3 的汉明码 m 3 23 1 7个非零列 3维矢量按0 7的二进制数排列 111100011001101010101 h b 系统码 111010011010101011001 h 五 线性分组码的译码6 定理7 若 n k 线性码的监督矩阵h任意s列线性无关 而存在s 1列线性相关 则d s 1 反之 若d s 1 则h的任意s列线性无关 而必存在有相关的s 1列 e1 s1 e1hte2 s2 e2ht若e1 e2 希望s1 s2 即保证e与s有一一对应关系 设e1 0 ei1 ei2 eit e2 0 ej1 ej2 ejt s1 ei1hi1t ei2hi2t eithitts2 ej1hi1t ej2hj2t ejthjtt若要s1 s2 则s1 s2 ei1hi1t ei2hi2t eithitt ej1hi1t ej2hj2t ejthjtt 0任2t列线性无关 d 2t 1 3 线性分组码的最小距离与h的关系 问题 d 2t 1越大越好 能大到什么程度 五 线性分组码的译码6 问题 d 2t 1越大越好 能大到什么程度 h的秩为n k 有n k列线性无关 但任n k 1列线性相关 所以d n k 1 推论3 3 1 取上限 得d n k 1 称为singleton限 达到singleton限的码称为极大最小距离可分码 mds rs码达到此限 五 线性分组码的译码7 由于线性分组码 n k d 是方程hct 0t的解空间 任一码字c满足cth 0 若c经过信道到达终端变为r c e 如没有发生错误 e 0 则rth 0 如果发生错误即e 0 这时有两种情况 e n k d 这时r n k d 也就是r变成了另外一个码字 rth仍等于0 e n k d 这时rth cth eth eth 0 只与e有关 由此可见 如果码字间的距离足够大以至发生了错误也不会变成另一个码字 则可从s rth判断码字在传输中是否有错 错误的图样是什么 s称为伴随式 通过伴随式与错误的图样的一一对应关系来译码叫伴随式译码 4 伴随式译码 s计算电路 s e组合逻辑电路 r e电路 r s 五 线性分组码的译码8 5 标准阵列译码 c1 0c2 ci cj c2ke2c2 e2 ci e2 cj e2 c2k e2e3c2 e3 ci e3 cj e3 c2k e3 emc2 em ci em cj em c2k em e2n kc2 e2n k ci e2n k cj e2n k c2k e2n k 最佳码 使w w e2 w e3 w em w e2n k 为最小的码不是唯一 p64表3 3 p15表1 2 由于fq上线性码c n k 是n维矢量线性空间v的qk阶加法子群 故v可划分为qn qk qn k个c的不同陪集 包括c 如果第一个陪集c e2的陪集首e2取v c中重量最小者 第二个陪集c e3的陪集首e3取v c c e2 中重量最小者 依次类推可得c的各个陪集 由它们排列成译码的标准阵列 群码c 译为cj 错误图样 em的陪集 以剩余矢量中重量最小者为陪集首 五 线性分组码的译码9 c1 0c2 ci cj c2ke2c2 e2 ci e2 cj e2 c2k e2e3c2 e3 ci e3 cj e3 c2k e3 emc2 em ci em cj em c2k em e2n kc2 e2n k ci e2n k cj e2n k c2k e2n k 证明标准阵列译码符合最小距离译码准则 即证 d ci em ci d ci em cj 证明 d ci em ci w em d ci em cj w ci cj em w cq em 由标准阵列的生成规则 得w em w cq em 下证不相等 由d cq em d cq em cq d cq em em 得w cq em w em w cq w cq em w cq w em 又若d cq 0 2w em 1 则w cq 2w em 1 所以w cq em 2w em 1 w em w em 1w em w cq em cq em cq em 五 线性分组码的译码10 最佳码 使w w e0 w e1 w e2n k 为最小的码 不是唯一 表3 3 表1 2 5 完备码 定理8 gf 2 上的 n k 线性码能纠2n k个错误图样 错误图样数 所以2n k n k 监督元数目 t 纠错能力 取下限 得2n k 满足这个条件的叫完备码 定义3 3 2 可见 完备码的纠错能力达到极限 问题 如果是多元码 情况会怎样 五 线性分组码的译码11 汉明码 2m 1 2m 1 m 3 是能纠一个错的2元完备码 1 2m 1 2m 定义 定义3 3 1 gf 2 上的线性分组码 n k d 称为汉明码 若满足下列条件 1 n 2m 1 m n 且m 3 2 k 2m m 1 3 n k m 4 d 3 戈莱 golay 码 23 12 7 p202 203 是目前唯一已知能纠多个错误的2元完备码 六 由一个已知码构造新码的简单方法 扩展码 增加一个检验位 n k n 1 k 加奇偶校验位 一般为偶校验 h 对于汉明码 2m 1 2m 1 m 3 由于d 3 h任两列线性无关同时存在线性相关的3列 而在h 中 任三列线性无关 最后一位3个1相加不为0 但存在线性相关的4列 原在h中线性相关的3列加上h 的最后一列 所以h 确定了扩展汉明码 2m 2m 1 m 4 2 删除码 删去一个检验位 和扩展码相反 n k n 1 k 六 由一个已知码构造新码的简单方法2 3 增广码 增信删余码 增加一个信息元 删去一个校验元 n k n k 1 4 增余删信码删去一个信息元 增加一个校验元 n k n k 1 5 延长码先增广 后扩展 n k n k 1 n 1 k 1 扩展 原码 增余删信 扩展 删除 缩短 n k n 1 k n k 1 延长 增余删信 增信删余 6 缩短码删去一个信息元缩短循环码 p157 5 4节 n k n 1 k 1 七