第3章 线性分组码 第第3章章 线性分组码线性分组码o3.1 线性分组码的基本概念线性分组码的基本概念 o3.2 码的一致校验矩阵与生成矩阵码的一致校验矩阵与生成矩阵 o3.3 伴随式与标准阵列及其它译码伴随式与标准阵列及其它译码 o3.4 线性码的覆盖半径 o3.5 由一个已知码构造新码的简单方法由一个已知码构造新码的简单方法 o3.6 用多个已知码构造新码的方法用多个已知码构造新码的方法 o3.7 线性码的重量分布与译码错误概率线性码的重量分布与译码错误概率 o3.8 线性码的纠错能力1 第3章 线性分组码 3.1 线性分组码的基本概念线性分组码的基本概念 o线性空间n设设V 是一个非空集合是一个非空集合, P 是一个数域是一个数域, 在集合在集合V 中定中定义了一种代数运算，叫做义了一种代数运算，叫做加法加法: 即对在即对在V 中都存在唯中都存在唯一的一个元素一的一个元素λ，称，称λ为α与β的的和和，记为：，记为： ；在；在P与与V的元素之间还定义了一种运算，的元素之间还定义了一种运算，叫做叫做数量乘法数量乘法：即：即在在V中都存在唯一的一个元素中都存在唯一的一个元素δ与它们对应，称与它们对应，称δ为为 的的数量乘积数量乘积，记为，记为 如果加法和数量乘法如果加法和数量乘法还满足下述规则，则称还满足下述规则，则称V 为数域为数域P上的上的线性空间线性空间：：2 第3章 线性分组码 3.1 线性分组码的基本概念线性分组码的基本概念 加法满足下列四条规则：加法满足下列四条规则： ①① ④④ 对对 都有都有V中的一个元素中的一个元素ββ，使得 ，使得 ③③ 在在V中有一个元素中有一个元素0，对，对（具有这个性质的元素（具有这个性质的元素0称为称为V的的零元素零元素）） ; ;（（ββ称为称为 的的负元素负元素）） ②② 3 第3章 线性分组码 3.1 线性分组码的基本概念线性分组码的基本概念 ⑤⑤ ⑥⑥ 数量乘法与加法满足下列两条规则：数量乘法与加法满足下列两条规则： ⑦⑦ 数量乘法满足下列两条规则数量乘法满足下列两条规则 :⑧⑧ 4 第3章 线性分组码 3.1 线性分组码的基本概念线性分组码的基本概念 o线性空间的性质n零元素是唯一的零元素是唯一的n负元素是唯一的，负元素是唯一的， - 唯一唯一n关于关于0元素有元素有n如果如果 如果如果＝＝0，那么，那么k＝＝0或或 ＝＝0. 5 第3章 线性分组码 3.1 线性分组码的基本概念线性分组码的基本概念 o线性分组码定义n[n, k]线性分组码是GF(q)上的n维线性空间中的一个k维子空间。
n线性分组码的基本特性：Ø线性结构即如果 c1、c2 分别是信息序列 m1、m2的码字，则 c1+c2 必定是信息序列 m1+m2 的码字Ø两码字C1和C2之间的距离d(C1, C2)必等于第三个码字C1+C2的汉明重量Ø[n,k,d]线性分组码的最小距离等于非零码字的最小重量6 第3章 线性分组码 3.1 线性分组码的基本概念线性分组码的基本概念 oGF(2)上［n ， k ， d］线性分组码中， 任何两个码字C1， C2之间有如下关系： w(C1+C2)=w(C1)+w(C2)-2w(C1·C2)或 d(C1， C2)≤w(C1)+w(C2) 式中， C1·C2是两个码字的内积oGF(2)上线性分组码任3个码字C1， C2， C3之间的汉明距离， 满足以下三角不等式d(C1， C2)+d(C2， C3)≥d(C1， C3)o任何［n ， k ， d］线性分组码， 码字的重量或全部为偶数， 或者奇数重量的码字数等于偶数重量的码字数7 第3章 线性分组码 3.2 码的一致校验矩阵与生成矩阵码的一致校验矩阵与生成矩阵 o［n ， k ， d］分组码o在n 维线性空间Vn 中， 如何找出满足一定要求的， 有2k 个矢量组成的k 维线性子空间Vn , k 。
o 在满足给定条件(码的最小距离d或码率R)下， 如何从已知的k 个信息元求得r=n -k 个校验元8 第3章 线性分组码 3.2 码的一致校验矩阵与生成矩阵码的一致校验矩阵与生成矩阵 o码的生成矩阵（ k 维线性子空间）n由于[n,k,d]线性分组码是一个k维线性空间因此必可找到k个线性无关的矢量，能张成该线性空间设 是k个线性无关的矢量，则对任意，可有：G称为该分组码的生成矩阵9 第3章 线性分组码 3.2 码的一致校验矩阵与生成矩阵码的一致校验矩阵与生成矩阵 n例：一个[7, 3 ]码，m2 m1 m0 → c6 c5 c4 c3 c2 c1 c0 ，如果码字的生成规则为： 若用矩阵形式表示这些线性方程组， 则： 10 第3章 线性分组码 3.2 码的一致校验矩阵与生成矩阵码的一致校验矩阵与生成矩阵 o则矩阵 就是该[7, 3 ]码的生成矩阵注：1)生成矩阵生成矩阵G中的每一行都是一个码字中的每一行都是一个码字2)任意任意k个线性独立的码字都可以作为生成矩阵个线性独立的码字都可以作为生成矩阵3)给定一个给定一个[n,k,d]线性分组码，其生成矩阵可有多个线性分组码，其生成矩阵可有多个11 第3章 线性分组码 3.2 码的一致校验矩阵与生成矩阵码的一致校验矩阵与生成矩阵 o码的校验矩阵(求r=n -k 个校验元)n-k个校验位可用k个已知的信息位表示出来12 第3章 线性分组码 3.2 码的一致校验矩阵与生成矩阵码的一致校验矩阵与生成矩阵 校验矩阵校验矩阵H与任意一个码字之积为零，因此有13 第3章 线性分组码 3.2 码的一致校验矩阵与生成矩阵码的一致校验矩阵与生成矩阵 n例 c6 +c4+c3 =0 c6+c5+c4 +c2 =0 c6+c5 +c1 =0 c5+c4 +c0 =014 第3章 线性分组码 3.2 码的一致校验矩阵与生成矩阵码的一致校验矩阵与生成矩阵 c6 +c4+c3 =0 c6+c5+c4 +c2 =0 c6+c5 +c1 =0 c5+c4 +c0 =015 第3章 线性分组码 3.2 码的一致校验矩阵与生成矩阵码的一致校验矩阵与生成矩阵 o系统码、对偶码和缩短码n系统码n若信息组以不变的形式在码组的任意k 位(通常在最前面： cn -1， cn -2， …， cn -k )中出现的码称为系统码，生成矩阵和校验矩阵应该具有性质k 位信息位 n -k 位校验位 16 第3章 线性分组码 3.2 码的一致校验矩阵与生成矩阵码的一致校验矩阵与生成矩阵 o［7， 3， 4］码17 第3章 线性分组码 3.2 码的一致校验矩阵与生成矩阵码的一致校验矩阵与生成矩阵 o对偶码设C是［n , k , d］码， 则它的对偶码C⊥是 C⊥＝{x∈V n , (n -k )； 对所有y∈C使x·y=0} 式中， x·y为x与y的内积。
n由G生成的［n, k, d］码C与由H生成的［n, n-k, d］码C⊥互为对偶码18 第3章 线性分组码 3.2 码的一致校验矩阵与生成矩阵码的一致校验矩阵与生成矩阵 o缩短码 缩短码是k 维子空间Vn,k 中取前i位均为0的码字组成的一个子集,该子集组成了一个［n –i, k -i］分组码n［ n –i, k -i］缩短码的纠错能力至少与原［n, k ］码相同n［n –i, k -i］缩短码是［n , k ］码缩短i位得到的， 因而码率R 比原码要小， 但纠错能力不一定比原码强19 第3章 线性分组码 3.3 伴随式与标准阵列及译码伴随式与标准阵列及译码o伴随式(校正子)o设发送的码字C=(cn -1，cn -2， …， c1， c0)， 通过有扰信道传输， 信道产生的错误图样错误图样 E=(en -1， en -2， …， e1， e0) 接收端译码器收到的n 重为R=(rn -1， rn -2， …， r1， r0)， R=C+E， ri=ci+ei， ci， ri， ei∈GF(q)或GF(2)中oR·HT=(C+E)·HT=C·HT+E·HT=E·HT 令 S=R·HT=E·HT 称为接收向量R的伴随式伴随式(校正子校正子)20 第3章 线性分组码 3.3 伴随式与标准阵列及译码伴随式与标准阵列及译码第i1， i2， …， it位有错： E =(0， …， ei1， 0， …， ei2， 0， …， eit， 0， …， 0)21 第3章 线性分组码 3.3 伴随式与标准阵列及译码伴随式与标准阵列及译码o［n ， k ， d］码要纠正≤t个错误， 则要求≤t 个错误的所有可能组合的错误图样， 都应该有不同的伴随式与之对应，则其充要条件是H矩阵中任何2t列线性无关。
ei1hi1+ei2hi2+…+eithit≠ej1hj1+ej2hj2+…+ejthjtei1hi1+ei2hi2+…+eithit-ej1hj1-ej2hj2-…-eithjt≠0To定理:［n ， k ， d］线性分组码有最小距离等于d的充要条件是， H矩阵中任意d-1列线性无关22 第3章 线性分组码 3.3 伴随式与标准阵列及译码伴随式与标准阵列及译码o(Singleton 限) ［n ， k ， d］线性分组码的最大可能的最小距离等于n -k +1， 即d≤n -k +1o若系统码的最小距离d=n -k +1， 则称此码为极大最小距离可分码， 简称MDS码23 第3章 线性分组码 3.3 伴随式与标准阵列及译码伴随式与标准阵列及译码o汉明码（纠正单个错误）oGF(2)上汉明码的H矩阵的列， 是由所有的非零的二进制m维向量组成 o该码有如下参数： n =2m-1， k =2m-1-m， R=(2m-1-m)／(2m-1)， d=3o纠正一个错误的［n ， k ， d］分组码， 要求其H矩阵中任意两列线性无关， 且不能全为0 若为二进制码， 则要求H矩阵中每列互不相同， 且不能全为0。
24 第3章 线性分组码 3.3 伴随式与标准阵列及译码伴随式与标准阵列及译码o例 构造GF(2)上的［7， 4， 3］汉明码 n =2m-1， k =2m-1-m， R=(2m-1-m)／(2m-1)，d=3o取m =3， 所有23=8个三重为： 000， 100， 010， 001， 011， 101， 110， 111o若码字传输中第一位发生错误， 则相应的伴随式S=(001)， 它就是“1”的二进制表示， 若第五位发生错误， 伴随式S=(101)， 是“5”的二进制表示25 第3章 线性分组码 3.3 伴随式与标准阵列及译码伴随式与标准阵列及译码26 第3章 线性分组码 3.3 伴随式与标准阵列及译码伴随式与标准阵列及译码o标准阵列［n , k , d］分组码的译码步骤可归结为以下三步： (1) 由接收到的R， 计算伴随式S=R·HT； (2) 若S=0， 则认为接收无误 若S≠0 ， 则由由S找出错误图样找出错误图样 ； (3) 由 和R找出 。
汉明码译码简单，由S可直接找到 ，其他码比较复杂 27 第3章 线性分组码 3.3 伴随式与标准阵列及译码伴随式与标准阵列及译码o以2k 个码字为基础，把n 维空间的2n 个元素划分陪集， 则得到如下所示的译码表o2n-k 个陪集， 称C1， E2， E3， …， 为陪集首 按这种方法构成的表称为标准阵译码表， 简称标准阵28 第3章 线性分组码 3.3 伴随式与标准阵列及译码伴随式与标准阵列及译码o问题是： 如何划分陪集使译码错误概率最小？n挑选重量最轻的n 重为陪集首， 放在标准阵中的第一列， 而以全为0码字作为子群的陪集首n也称为最小距离译码，在BSC下等效于最大似然译码 o用这种标准阵译码， 需要把2n 个n 重存储在译码器中 译码器的复杂性随n 指数增长， 很不实用o简化译码表n错误图样与伴随式一一对应29 第3章 线性分组码 3.3 伴随式与标准阵列及译码伴随式与标准阵列及译码o［6， 3］码标准阵30 第3章 线性分组码 3.3 伴随式与标准阵列及译码伴随式与标准阵列及译码o即使用简化译码表， 译码器的复杂性还是很高的 例如， 一个［100， 70］分组码， 一共有230≈109个伴随式及错误图样。
31 第3章 线性分组码 3.5 由一个已知码构造新码的简单方法由一个已知码构造新码的简单方法o扩展码 设C是一个最小距离为d的二进制［n ， k ， d］线性分组码，若对每一个码字(cn-1，cn-2，…， c1，c0)增加一个校验元c’0， 满足以下校验关系： cn -1+cn -2+…+c1+c0+c’0=0 称c’0为全校验位32 第3章 线性分组码 3.5 由一个已知码构造新码的简单方法由一个已知码构造新码的简单方法o删余码 删余码是由扩展码的逆过程而得到的 它在原［n ， k ］码C的基础上， 删去一个校验元而构成， 变为［n -1， k ］删余码C* C*码的最小距离可能比原码小1， 也可能不变33 第3章 线性分组码 3.6 用多个已知码构造新码的方法用多个已知码构造新码的方法o直和 设C1和C2分别是［n 1，k 1，d1］和 ［n 2，k 2，d2］二进制码， 且n1=n2， C1∩C2=0， 则定义C1和C2码的直和码C1⊕C2=C是［n，k1+ k2 ，d］ C={(a⊕b)｜a∈C1， b∈C2}d≤min {d1， d2}34 第3章 线性分组码 3.6 用多个已知码构造新码的方法用多个已知码构造新码的方法o笛卡儿积 由C1和C2码的笛卡儿积C1×C2得到的码是 C=C1×C2={(a， b)｜a∈C1， b∈C2} C码是一个［n 1+n 2， k 1+k 2， min {d1， d2}］码。
35 第3章 线性分组码 3.6 用多个已知码构造新码的方法用多个已知码构造新码的方法o直积(Kronecker积) C1和C2码的直积C1 C2=C， 是一个［n1n2，k1k2，d1d2］码式中， gij是C1码生成矩阵中第i行第j列元素 36 第3章 线性分组码 3.7 线性码的重量分布与译码错误概率线性码的重量分布与译码错误概率o设Ai是［n， k， d］分组码中重量为i的码字数目， 则集合{A0， A1， …， An}称为该分组码的重量分布重量分布 称A(x)为码的重量估值算子， 简称重量算子重量算子 例如［7， 4， 3］汉明码的重量分布为{Ai}={A0， A1， A2， A3， A4， A5， A6， A7} ={1， 0， 0， 7， 7， 0， 0， 1}其中， 一个全0码字(A0=1)是任何线性码所必须有的 37 第3章 线性分组码 3.7 线性码的重量分布与译码错误概率线性码的重量分布与译码错误概率o定理： 设二进制［n， k］线性分组码及其［n， n-k］对偶码的重量算子分别是： 则它们之间有如下关系： 称此式为马克威伦( MacWilliams)恒等式。
38 第3章 线性分组码 3.7 线性码的重量分布与译码错误概率线性码的重量分布与译码错误概率o若码字等概发送，［n， k， d］二进制线性分组码的不可检错误概率不可检错误概率39 。