第3章 线性分组码.ppt
233页
第第3章章 线性分组码线性分组码 第第3章章 线性分组码线性分组码 3.1 线性分组码的基本概念线性分组码的基本概念 3.2 码的一致校验矩阵与生成矩阵码的一致校验矩阵与生成矩阵 3.3 伴随式与标准阵列及其它译码伴随式与标准阵列及其它译码 3.4 线性码的覆盖半径线性码的覆盖半径 3.5 由一个已知码构造新码的简单方法由一个已知码构造新码的简单方法 3.6 用多个已知码构造新码的方法用多个已知码构造新码的方法 3.7 线性码的重量分布与译码错误概率线性码的重量分布与译码错误概率 3.8 线性码的纠错能力线性码的纠错能力习题习题 第第3章章 线性分组码线性分组码 3.1 线性分组码的基本概念线性分组码的基本概念 第一章第三节已叙述了分组码的某些重要概念， 如分组码的表示、 码率、 距离、 重量等 如果我们把每一码字看成是一个n维数组或n维线性空间中的一个矢量， 则可以从线性空间的角度， 比较深入地讨论线性分组码 第第3章章 线性分组码线性分组码 一个［n， k］线性分组码， 是把信息划成k个码元为一段(称为信息组)， 通过编码器变成长为n个码元的一组， 作为［n， k］线性分组码的一个码字。
若每位码元的取值有q种(q为素数幂)， 则共有qk个码字 n长的数组共有qn组， 在二进制情况下， 有2n个数组 显然， qn个n维数组(n重)组成一个GF(q)上的n维线性空间 如果qk(或2k)个码字集合构成了一个k维线性子空间， 则称它是一个［n， k］线性分组码 第第3章章 线性分组码线性分组码 定义3.1.1 ［n， k］线性分组码是GF(q )上的n维线性空间Vn中的一个k维子空间Vn,k 由于该线性子空间在加法运算下构成阿贝尔群， 所以线性分组码又称为群码 为简单起见， 今后若没有特别说明， 所说的分组码均指线性分组而言， 且用(cn-1， cn-2， …， c1， c0)表示［n， k］码的一码字， 其中每一分量ci∈GF(q) 第第3章章 线性分组码线性分组码 例3.1 n =7， k =3的［7， 3］线性分组码的8个码字和信息组如表 3 - 1所示 这8个码字在模2加法运算下构成一个阿贝尔加群 信息组 码 字 000 001 010 011 100 101 110111 0000000 00111010100111 0111010 1001110 1010011 11010011110100 第第3章章 线性分组码线性分组码 由于线性分组码是分组码的一类， 因此第一章中有关分组码的参数， 如码率R=k ／n 、 码字的距离与码的最小距离、 码字的重量等定义， 以及说明最小距离与纠错能力之间关系的定理1.3.1， 对线性分组码均适用， 这里不再赘述。
显然， R和d是分组码的两个最重要的参数， 因此今后我们用［n ， k ， d］(或［n ， k ］)表示线性分组码 而用(n ， M， d)表示码字数目为M的任何码， 此时码率R=n –1 logqM 第第3章章 线性分组码线性分组码 ［n ， k ， d］分组码是一个群码， 因此若码字C1∈［n ， k ， d］、 C2∈［n ， k ， d］， 则由群的封闭性可知， 码字C1与C2之和C1+C2∈［n ， k ， d］， 即C1+C2也必是［n ， k ， d］分组码的一个码字 所以， 两码字C1和C2之间的距离d(C1， C2)必等于第三个码字C1+C2的汉明重量 第第3章章 线性分组码线性分组码 如例3.1中的两个码字： (1010011)， (1101001)， 它们之间的距离是4， 它就是(0111010)码字的重量， 即 d(C1， C2)=w(C1+C2) 因此， 一个［n ， k ， d］分组码的最小距离必等于码中非零码字的最小重量， 由此可得如下定理。
定理3.1.1 ［n ， k ， d］线性分组码的最小距离等于非零码字的最小重量 第第3章章 线性分组码线性分组码 定理3.1.2 GF(2)上［n ， k ， d］线性分组码中， 任何两个码字C1， C2之间有如下关系： w(C1+C2)=w(C1)+w(C2)-2w(C1·C2) (3.1.1)或 d(C1， C2)≤w(C1)+w(C2) (3.1.2)式中， C1·C2是两个码字的内积 请同学自己证明 第第3章章 线性分组码线性分组码 推论3.1.1 GF(2)上线性分组码任3个码字C1， C2， C3之间的汉明距离， 满足以下三角不等式d(C1， C2)+d(C2， C3)≥d(C1， C3) (3.1.3) 证明 设码字Ca=C1+C2， Cb=C2+C3， 由式(3.1.2)可知： w(Ca+Cb)=w(C1+C2+C2+C3)=w(C1+C3) =d(C1， C3)≤w(Ca)+w(Cb)=w(C1+C2)+w(C2+C3)。
所以 d(C1， C3)≤d(C1， C2)+d(C2， C3) 第第3章章 线性分组码线性分组码 定理3.1.3 任何［n ， k ， d］线性分组码， 码字的重量或全部为偶数， 或者奇数重量的码字数等于偶数重量的码字数 证明略 第第3章章 线性分组码线性分组码 §3.2 码的一致校验矩阵与生成矩阵码的一致校验矩阵与生成矩阵 一、 码的校验矩阵与生成矩阵 ［n ， k ， d］分组码的编码问题就是在n 维线性空间Vn 中， 如何找出满足一定要求的， 有2k 个矢量组成的k 维线性子空间Vn ， k 或者说， 在满足给定条件(码的最小距离d或码率R)下， 如何从已知的k 个信息元求得r=n -k 个校验元 第第3章章 线性分组码线性分组码 这相当于建立一组线性方程组， 已知k 个系数， 要求n-k 个未知数， 使得到的码恰好有所要求的最小距离d 上例中的［7， 3， 4］码， 若c6， c5， c4代表3个信息元， 则c3， c2， c1， c0 这 4 个校验元， 可由以下线性方程组求得： 1·c3=1·c6+0·c5+1·c4 1·c2=1·c6+1·c5+1·c4 1·c1=1·c6+1·c5+0·c4 1·c0=0·c6+1·c5+1·c4 (3.2.1) 第第3章章 线性分组码线性分组码 c6 +c4+c3 =0 c6+c5+c4 +c2 =0 c6+c5 +c1 =0 c5+c4 +c0 =0 第第3章章 线性分组码线性分组码 例3.2 c6=1， c5=0， c4=1， 求c3， c2， c1， c0。
由上述线性方程组可知： c3=c6+c4=1+1=0 c2=c6+c5+c4=1+0+1=0 c1=c6+c5=1+0=1 c0=c5+c4=0+1=1由此得到的码字为： (1010011) 第第3章章 线性分组码线性分组码 可以检验例3.1中的［7， 3， 4］码的8个码字均满足式(3.2.1)和式(3.2.2) 若用矩阵形式表示这些线性方程组， 则式(3.2.1)或式(3.2.2)可表示为： 第第3章章 线性分组码线性分组码 或 第第3章章 线性分组码线性分组码 称上式中的4行7列矩阵为［7， 3， 4］码的一致校验矩阵， 通常用H 表示， 该码的 第第3章章 线性分组码线性分组码 一般情况下，任何一个［n ， k ， d］码的H矩阵可表示为(3.2.3) 第第3章章 线性分组码线性分组码 它是一个(n -k )×n 阶矩阵 由此H矩阵可以很快地建立码的线性方程组： (3.2.4) 第第3章章 线性分组码线性分组码 或 (3.2.5)简写为H·CT=0T (3.2.6)或C·HT=0 (3.2.7) 第第3章章 线性分组码线性分组码 可知H矩阵的每一行代表一个线性方程组的系数， 它表示求一个校验元的线性方程。
因此任何一个 ［n ， k ， d］码的H矩阵必须有n -k 行， 且每行必须线性独立 若把H的每一行看成一个矢量， 则这n -k 个矢量必然张成了n 维线性空间中的一个n -k 维子空间 Vn ， n -k 第第3章章 线性分组码线性分组码 由于［n ， k ， d］码的每一码字必须满足式(3.2.6)或式(3.2.7)， 即它的每一码字必然在由H矩阵的行所张成的Vn ，n -k空间中的零空间中 由定理2.6.10可知， Vn ，n -k 的零空间必然是一个k 维子空间Vn ， k ， 而这正是［n ， k ， d］码的码字集合全体 所以， Vn ，n -k与［n ， k ， d］码的每一码字均正交， 也就是H矩阵的每一行与它的码的每一码字的内积均为0 第第3章章 线性分组码线性分组码 ［n ， k ， d］分组码的2k 个码字组成了一个k 维子空间， 因此这2k 个码字完全可由k 个独立矢量所组成的基底而张成 设基底为 C1=(g1， n -1， g1， n -2， …， g1， 0) C2=(g2， n -1， g2， n -2， …， g2， 0) … Ck =(gk ， n -1， gk ， n -2， …， gk ， 0) 第第3章章 线性分组码线性分组码 若把这组基底写成矩阵形式， 则有 g1， n -1， g1， n -2， …， g1， 0 g2， n -1， g2， n -2， …， g2， 0 … gk ， n -1， gk ， n -2， …， gk ， 0 G= (3.2.8) 第第3章章 线性分组码线性分组码 ［n ， k ， d］码中的任何码字， 都可由这组基底的线性组合生成， 即C=m·G=［mn -1 mn -2… mn -k ］ g1， n -1， g1， n -2， …， g1， 0 g2， n -1， g2， n -2， …， g2， 0 … gk ， n -1， gk ， n -2， …， gk ， 0 (3.2.9) 第第3章章 线性分组码线性分组码 式中， m=(mn -1， mn -2， …， mn -k )是k 个信息元组成的信息组。
因此， 若已知信息组m， 通过式(3.2.9)可求得相应的码字， 称式(3.2.8)的G为 ［n ， k ， d］码的生成矩阵 第第3章章 线性分组码线性分组码 如表 3 - 1中的［7， 3， 4］码， 可从它的8个码字中任意挑出k =3个线性无关的码字： (1001110)， (0100111)， (0011101)作为码的生成矩阵的行， 则 (3.2.10) 第第3章章 线性分组码线性分组码 若已知信息组m=(011)， 则相应的码字为 第第3章章 线性分组码线性分组码 显然， 一个矢量空间的基底可以不止一个， 因此作为码的生成矩阵G也可以不止一种形式 但不论哪一种形式， 它们都生成相同的矢量空间， 即生成同一个［n ， k ， d］码 第第3章章 线性分组码线性分组码 G中的每一行及其线性组合均为［n ， k ， d］码的一个码字， 所以由式(3.2.6)和式(3.2.7)可知 G·HT=0 (3.2.11)或 H·GT=0T (3.2.12) 第第3章章 线性分组码线性分组码 二、 对偶码 ［n ， k ， d］码是n 维线性空间中的一个k 维子空间Vn ， k ， 由一组基底即G的行张成。
由前可知， 它的零空间必是一个n -k 维的线性子空间Vn ， n -k ， 并由n -k 个独立矢量张成 由式(3.2.11)和式(3.2.12)可知， 这n-k 个矢量就是H矩阵的行 因此， 若把H矩阵看成是［n ， n -k ， d’］码的生成矩阵G， 而把［n ， k ， d］码的G看成是它的校验矩阵H， 则我们称由G生成的［n ， k ， d］码C与由H生成的［n ， n -k ， d’］码C⊥互为对偶码 相应地， 称Vn ， k与Vn ， n -k空间互为对偶空间 由此可如下定义对偶码 第第3章章 线性分组码线性分组码 定义3.2.1 设C是［n ， k ， d］码， 则它的对偶码C⊥是 C⊥{x∈Vn ,(n -k )； 对所有y∈C使x·y=0} 式中， x·y为x与y的内积 第第3章章 线性分组码线性分组码 如例3.1中的［7，3，4］码， 它的对偶码必是 ［7，4，3］码， 其生成矩阵G［7，4］就是 ［7， 3， 4］码的校验矩阵H［7， 3］G［7， 4］=H［7， 3］= 由此生成矩阵， 已知信息组m， 根据式(3.2.9)就可求得［7， 4， 3］码的16个码字。
第第3章章 线性分组码线性分组码 若一个码的对偶码就是它自己， 即C=C⊥则称C码为自对偶码 显然， 自对偶码必定是［2m， m， d］形式的分组码 如［2， 1， 2］重复码就是一个自对偶码 如果自对偶码的最小距离d是4的倍数， 则称为双偶自对偶码， 可以证明双偶自对偶码的码长n 必是8的整数倍 第第3章章 线性分组码线性分组码 三、 系统码 定义3.2.2 若信息组以不变的形式在码组的任意k 位(通常在最前面： cn -1， cn -2， …， cn -k )中出现的码称为系统码， 否则为非系统码 系统码的一种结构形式如图 3 - 1所示 表 3 - 1中所列的［7， 3， 4］码就是系统码形式 显然， 系统码的信息位与校验位很容易区分开， 所以这种码也称可分码 k 位信息位 n -k 位校验位 第第3章章 线性分组码线性分组码 由于系统码的码字前k 位是原来的信息组， 故由式(3.2.8)可知， G矩阵左边k 列必组成一个单位方阵Ik ， 因此系统码的生成矩阵通常为 G=［Ik P］ (3.2.13) 式中， P是k ×(n -k )阶矩阵。
如果信息组不在码字的前k 位， 而在码字的后k 位， 则G矩阵中的Ik 方阵在P矩阵的右边 因为G与H矩阵所组成的空间互为零空间， 所以与式(3.2.13)相应的H矩阵为 H=［-PTIn -k ］ (3.2.14) 第第3章章 线性分组码线性分组码 式中， -PT是一个(n -k )×k 阶矩阵， 它是P矩阵的转置， “-”号表示-PT阵中的每一元素是P阵中对应元素的逆元， 在二进制情况下， 仍是该元素自己 显然， 由此得到的H满足 第第3章章 线性分组码线性分组码 通常， 我们称式(3.2.13)与式(3.2.14)中的G和H矩阵为码的典型(标准)生成矩阵和典型校验矩阵 如 ［7， 3， 4］码的典型生成矩阵 第第3章章 线性分组码线性分组码 相应地， 典型校验矩阵由式(3.2.14)为 第第3章章 线性分组码线性分组码 系统码的编码相对而言较为简单， 且由G可以方便地得到H(反之亦然)， 容易检查编出的码字是否正确 同时， 对分组码而言， 系统码与非系统码的纠错能力完全等价。
因此， 今后若无特别声明， 仅讨论系统码形式 第第3章章 线性分组码线性分组码 四、 缩短码 在某些情况下， 如果不能找到一种比较合适的码长或信息位个数， 则可把某一［n ， k ， d］码进行缩短， 以满足要求 第第3章章 线性分组码线性分组码 在［n ， k ， d］码的码字集合中， 挑选前i个信息位数字均为0的所有码字， 组成一个新的子集 由于该子集的前i位信息位均取0， 故传输时可以不送它们， 仅只要传送后面的n -i 位码元即可 这样该子集组成了一个［n -i， k -i， d］分组码， 称它为［n ， k ， d］码的缩短码 由于缩短码是k 维子空间Vn ， k 中取前i位均为0的码字组成的一个子集， 显然该子集是Vn ， k 空间中的一个k -i维的子空间Vn ， k -i， 因此［n -i， k -i， d］缩短码的纠错能力至少与原［n ， k ， d］码相同 第第3章章 线性分组码线性分组码 如例3.1中的［7， 3， 4］码， 若挑出第一个信息位均为0的码字： (0000000)， (0011101)， (0100111)， (0111010)， 则可组成一个［6， 2， 4］缩短码： (000000)， (011101)， (100111)， (111010)。
缩短码的G矩阵只要在原［n ， k ， d］码的G矩阵中， 去掉左边i列和上边i行即可 如上例中， ［6， 2， 4］缩短码的G矩阵可由［7， 3， 4］码的G矩阵(式(3.2.10))去掉第一行及左边第一列得到 第第3章章 线性分组码线性分组码 G［6， 2］= 而H矩阵， 只要在原码的H矩阵中去掉第一列即可 如该例的H矩阵为 第第3章章 线性分组码线性分组码 ［n -i， k -i］缩短码是［n ， k ］码缩短i位得到的， 因而码率R 比原码要小， 但纠错能力不一定比原码强 因此总的看来， 缩短码比原码的性能要差 第第3章章 线性分组码线性分组码 §3.3 伴随式与标准阵列及其它译码伴随式与标准阵列及其它译码 一、 伴随式(校正子) 本节讨论如何译码 设发送的码字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)中。
第第3章章 线性分组码线性分组码 ［n ， k ， d］码的每一码字C， 都必须满足式(3.2.6)或式(3.2.7) 因此， 收到R后用该两式之中的任一式进行检验： R·HT=(C+E)·HT=C·HT+E·HT=E·HT (3.3.1)若E=0， 则R·HT=0， E ≠0则R·HT≠0 说明R·HT仅与错误图样有关， 而与发送的是什么码字无关 令 S=R·HT=E·HT 或 ST= H·RT=H·ET (3.3.2) 第第3章章 线性分组码线性分组码 由前知， ［n ， k ， d］码的校验矩阵 第第3章章 线性分组码线性分组码 式中， hn-i为H矩阵的第i列， 它是一个n -k 重列矢量 设E =(en -1， en -2， …， e1， e0) =(0， …， ei1， 0， …， ei2， 0， …， ei3， 0， …， eit， 0， …， 0)第i1， i2， …， it位有错， 则 第第3章章 线性分组码线性分组码 第第3章章 线性分组码线性分组码 从上面分析看出， 一个［n ， k ， d］码要纠正≤t个错误， 则要求≤t 个错误的所有可能组合的错误图样， 都应该有不同的伴随式与之对应。
这等效于： 若(0， …， 0， ei1， ei2， …， eit， 0， …， 0)≠(0， …， 0， ej1， ej2， …， eit， 0， …， 0) 第第3章章 线性分组码线性分组码 则要求： ei1hi1+ei2hi2+…+eithit≠ej1hj1+ej2hj2+…+ejthjt (3.3.4)或ei1hi1+ei2hi2+…+eithit-ej1hj1-ej2hj2-…-eithjt≠0T (3.3.5)由此可得到如下重要结论 第第3章章 线性分组码线性分组码 结论：一个［n ， k ， d］线性分组码， 若要纠正≤t个错误， 则其充要条件是H矩阵中任何2t列线性无关 由于d=2t+1， 所以也相当于要求H矩阵中d-1列线性无关 由此结论可得到以下重要定理 定理3.3.1 ［n ， k ， d］线性分组码有最小距离等于d的充要条件是， H矩阵中任意d-1列线性无关 第第3章章 线性分组码线性分组码 证明 先证明必要性。
即码有最小距离为d， 证明H中的任意d-1列线性无关 用反证法 若H中某一d-1列线性相关， 则由线性相关定义可知： ci1hi1+ci2hi2+…+ci(d-1)hi(d-1)=0T 第第3章章 线性分组码线性分组码 式中， cij∈GF(q)， hij是H矩阵的列矢量 现作一个码字C， 它在i1， i2， …， i(d-1)位处的值分别等于ci1， ci2， …， ci(d-1)， 而其它各位取值均为0， 所以得到的码字C是: (0， …， ci1， 0， …， 0， ci2， 0， …， 0， ci(d-1)， 0， …， 0)， 由此 H·CT=ci1hi1+ci2hi2+…+ci(d-1)hi(d-1)=0T 故C是一个码字， 而C的非0分量个数只有d-1个， 这与码有最小距离为d的假设相矛盾， 故H中的任意d-1列必线性无关 第第3章章 线性分组码线性分组码 下面证明： 若H中任意d-1列线性无关， 则［n ， k ， d］码有最小距离为d。
若H中任意d-1列线性无关， 则H中至少需要d列才能线性相关 我们将能使H中某些d列线性相关的列的系数， 作为码字中对应的非0分量， 而码字的其余分量均为0， 则该码字至少有d个非0分量， 故 ［n ， k ， d］码有最小距离为d 第第3章章 线性分组码线性分组码 定理3.3.1异常重要， 它是构造任何类型线性分组码的基础 由该定理看出， 交换H矩阵的各列， 并不会影响码的最小距离 因此， 所有列相同但排列位置不同的H所对应的分组码， 在纠错能力和其它码参数上完全等价 推论3.3.1 (Singleton 限) ［n ， k ， d］线性分组码的最大可能的最小距离等于n -k +1， 即d≤n -k +1 若系统码的最小距离d=n -k +1， 则称此码为极大最小距离可分码， 简称MDS码 构造MDS码是编码理论中一个重要课题 第第3章章 线性分组码线性分组码 二、 汉明码与极长码 汉明码是1950年由汉明首先构造， 用以纠正单个错误的线性分组码。
由于它的编译码非常简单， 很容易实现， 因此用得很普遍， 特别是在计算机的存贮和运算系统中更常用到 此外， 它与某些码类的关系很密切， 因此这是一类特别引人注意的码 第第3章章 线性分组码线性分组码 由定理3.3.1知， 纠正一个错误的［n ， k ， d］分组码， 要求其H矩阵中至少两列线性无关， 且不能全为0 若为二进制码， 则要求H矩阵中每列互不相同， 且不能全为0 一个［n ， k ， d］分组码有n -k 位校验元， 在二进制码情况下， 这n-k 个校验元能组成2n -k 列不同的n-k 重， 其中有2n-k -1列不全为0 所以， 如果用这 2n-k -1列作为H矩阵的每一列， 则由此H就产生了一个纠正单个错误的［n ， k ， 3］码， 它就是汉明码 第第3章章 线性分组码线性分组码 定义3.3.1 GF(2)上汉明码的H矩阵的列， 是由不全为0， 且互不相同的二进制m重组成 该码有如下参数： n =2m-1， k =2m-1-m， R=(2m-1-m)／(2m-1)， d=3。
第第3章章 线性分组码线性分组码 例3.3 构造GF(2)上的［7， 4， 3］汉明码 这时取m =3， 所有23=8个三重为： 000， 100， 010， 001， 011， 101， 110， 111 挑出其中7个非0 的三重构成 第第3章章 线性分组码线性分组码 若码字传输中第一位发生错误， 则相应的伴随式S=(001)， 它就是“1”的二进制表示， 若第五位发生错误， 伴随式S=(101)， 是“5”的二进制表示 因此， 哪一位发生错误， 它的伴随式就是该位号码的二进制表示， 所以能很方便地进行译码 第第3章章 线性分组码线性分组码 由前知， 任意调换H中各列位置， 并不会影响码的纠错能力 因此， 汉明码的H矩阵形式， 除了上述表示外， 还可以有其它形式 若把汉明码化成系统码形式， 则其(3.3.6) 第第3章章 线性分组码线性分组码 相应地 (3.3.7) 第第3章章 线性分组码线性分组码 可以把GF(2)上的汉明推广到GF(q)上， 得到多进制汉明码， 此时码有如下参数： 码 长 n =(qm-1)／(q-1) 信 息 位 k =n -m 码 率 R=(n -m)／n 最小距离 d=3 显然， 当n →∞时， R→1， 因此汉明码是纠正单个错误的高效码。
第第3章章 线性分组码线性分组码 二进制［2m-1， 2m-1-m， 3］汉明码的对偶码C⊥H是一个［2m-1， m， 2m-1］码， 也称为单纯码或极长码 以后将看到， 它可以由m级线性移存器产生， 所以也称最长线性移存器码 第第3章章 线性分组码线性分组码 三、 标准阵列 由前面的讨论中可知， ［n ， k ， d］分组码的译码步骤可归结为以下三步： (1) 由接收到的R， 计算伴随式S=R·H T； (2) 若S=0， 则认为接收无误 若S≠0 ， 则由S找出错误图样 ； (3) 由 和R找出 第第3章章 线性分组码线性分组码 ［n ， k ， d］码的2k 个码字， 组成了n 维线性空间中的一个k 维子空间， 显然是一子群 若以此子群为基础， 把整个n 维空间的2n 个元素划分陪集， 则得到如表 3 - 2所示的译码表。
其中， 2k 个码字放在表中的第一行， 该子群的恒等元素C1(全为0码字)放在最左边， 然后在禁用码组中挑出一个n 重E2放在恒等元素C1的下面，并相应求出E2+C2， E2+C3， …， E2+C2k ， 分别放在C2， C3， …， C2k 码字的下边构成第二行， 这是码空间的一个陪集 第第3章章 线性分组码线性分组码 再选一个未写入表中前一行的n 重E3， 用以上方法构成另一陪集成为表中的第三行， 依此类推， 一共构成2n -k 个陪集， 把所有2n 个矢量划分完毕， 称C1， E2， E3， …， 为陪集首 按这种方法构成的表称为标准阵译码表， 简称标准阵 第第3章章 线性分组码线性分组码 表3 - 2 标准阵译码表 第第3章章 线性分组码线性分组码 收到的n 重R落在某一列中， 则译码器就译成相应于该列最上面的码字 因此， 若发送的码字为Ci， 收到的R=Ci+Ej(1≤j≤2n -k ， E1是全0矢量)， 则能正确译码 如果收到的R=Ck +Ej， 则产生了错误译码 现在的问题是： 如何划分陪集使译码错误概率最小？这归结到如何挑选陪集首。
因为一个陪集的划分主要决定于子群， 而子群就是2k 个码字， 这已决定， 因此余下的问题就是如何决定陪集首 第第3章章 线性分组码线性分组码 在第一章中已提出， 在pe≤0.5的BSC中， 产生1个错误的概率比产生2个的大， 产生2个的比3个的大…… 总之， 错误图样重量越小的产生的可能性越大 因此， 译码器必须首先保证能正确纠正这种可能性出现最大的错误图样， 也就是重量最轻的错误图样 这相当于在构造译码表时要求挑选重量最轻的n 重为陪集首， 放在标准阵中的第一列， 而以全为0码字作为子群的陪集首 这样得到的标准阵， 能得到最小的译码错误概率 由于这样安排的译码表使得C i+Ej与Ci的距离保证最小， 因而也称为最小距离译码， 在BSC下， 它们等效于最大似然译码 第第3章章 线性分组码线性分组码 在标准阵中， 所有陪集首重量之和称为陪集首的总重量 应当指出， 在给定的n 、 k 条件下， 如果在2n 组中选择不同的2k 组作为子群， 则相应的标准阵中， 陪集首元素的总重量不一定相同 若所选的Vn ， k 子空间， 能做到使标准阵中陪集首元素的总重量最轻， 则此码能得到最大正确译码概率， 因而称该Vn ， k子空间构成的［n ， k ， d］码为最佳码。
如果在n 维空间中， 能找到两个或更多个Vn ， k子空间， 都能做到使标准阵中陪集首元素的总重量最轻， 则这些子空间构成的不同的［n ， k ， d］码均为最佳码， 因此对固定的n 和k 来说， 最佳码不是唯一的 第第3章章 线性分组码线性分组码 例3.4 ［7， 4， 3］汉明码的缩短码［6， 3， 3］码， 它的8个码组， 可由式(3.3.7)的G矩阵中去掉第一行和第一列后的G［6,3］中的行线性组合而得到 该码的标准阵如表 3 - 3所示 第第3章章 线性分组码线性分组码 表3 - 3 ［6， 3］码标准阵 第第3章章 线性分组码线性分组码 该［6， 3， 3］码标准阵陪集首的总重量为8， 而表1-2中码标准阵陪集首的总重量也为8， 这说明这两个［6， 3］码均是最佳码 由该表可以看到， 用这种标准阵译码， 需要把2n 个n 重存储在译码器中 所以， 这种译码方法译码器的复杂性随n 指数增长， 很不实用 第第3章章 线性分组码线性分组码 根据错误图样与伴随式之间的一一对应关系，可把上述标准阵译码表进行简化，得到一个简化译码表。
如上例中的[6,3,3]码标准阵，可简化为表3 – 4所示的译码表 译码器收到R后，与H进行运算得到伴随式S，由S查表得到错误图样 ，从而译出码字 因此，这种译码器中不必存储所有2n个n重，而只存储错误图样E与2n-k个(n-k)重S 第第3章章 线性分组码线性分组码 由于［n ， k ， d］分组码的n 、 k 通常都比较大， 即使用这种简化译码表， 译码器的复杂性还是很高的 例如， 一个［100， 70］分组码， 一共有230≈109个伴随式及错误图样， 译码器要存贮如此多的图样和(n -k )重是不太可能的 因此， 性分组码理论中， 如何寻找简化译码器是最中心的研究课题之一， 这将在以后有关章节讨论 第第3章章 线性分组码线性分组码 四、 完备译码与限定距离译码 例3.4中的［6， 3， 3］码利用标准阵译码时， 能纠正所有单个错误及一种两个错误， 码的所有23=8个伴随式都与某种类型的错误图样对应 因此， 译码器必然要对收到的R进行判决发送的是何码字， 这种译码方法称为完备译码。
第第3章章 线性分组码线性分组码 定义3.3.2 ［n ， k ， d］线性分组码的所有2n -k 个伴随式， 在译码过程中若都用来纠正所有小于等于 个随机错误， 以及部分大于t的错误图样， 则这种译码方法称为完备译码 否则， 称为非完备译码 任一个［n ， k ， d］码， 能纠正 个随机错误 如果在译码时仅纠正t′＜t个错误， 而当错误个数大于t′时， 译码器不进行纠错而仅指出发生了错误， 称这种译码方法为限定距离译码 第第3章章 线性分组码线性分组码 如［15， 4， 8］极长码， 它能纠正3个错误及部分4个错误 如果设计译码器时， 仅使它纠正1个错误， 而在≥2个错误时， 只指出接收的R有错， 但不进行纠正； 则这种译码器就称为限定距离译码器 第第3章章 线性分组码线性分组码 可知限定距离译码， 就是设计译码器时， 在0至 范围内， 事先由设计者指定纠错能力t′。
当实际产生的错误个数≤t′时， 译码器进行纠错译码； 当大于t′时， 译码器进行检错而不纠错 可见， 限定距离译码可以是完备译码， 也可以是非完备译码， 它完全由译码设计者决定 应当指出， 无论是何种译码方法， 为了使译码错误概率最小， 在设计译码器时都必须遵循最大似然译码准则(码字为等概发送时)， 在对称无记忆信道中也就是最小汉明距离译码准则 第第3章章 线性分组码线性分组码 §3.4 线性码的覆盖半径线性码的覆盖半径 从几何上讲， 码的陪集划分就是把n 维线性空间Vn ， 按［n ， k ， d］码C划分空间 标准阵译码表中的第j列， 相当于Vn 中球心为码字C j、 半径为ρ=d(Cj， Cj+E)=w(Ei)的一个球Bj(C)， 球中的点也就是Cj列中的n 重： {V∈Vn ｜ d(v， Cj)≤ρ} j=0， 1， 2， …， 2k -1 第第3章章 线性分组码线性分组码 表中共有2k 列， 相当于有2k 个这种互不相交的球， 把整个Vn 空间覆盖完毕 可知Bj(C)球的半径ρ， 就是码C的最大可能的纠错数目。
表 3 - 3中［6,3］码的ρ是2， 也就是它至多可能纠正两个错误， 但不能纠正所有两个错误的图样 第第3章章 线性分组码线性分组码 如果在Vn 空间中， 以码字为圆心， 为半径作球， 如图1-15所示， 则也有2k 个互不相交的球， 但这些球一般并不能把整个Vn 空间全部覆盖完毕 称这些球的半径为码C的球半径s(C) 可知码C的球半径 (3.4.1) 能把整个Vn 空间覆盖完毕的Bj(C)球的半径ρ称为码的覆盖半径t(C) 可知t(C)与s(C)均是码的重要的几何参数 第第3章章 线性分组码线性分组码 定义3.4.1 码C的覆盖半径t(C)=max{min {d(v， Cj)｜ Cj∈C}； v∈Vn } (3.4.2) 通常称Cj+v为码字Cj的平移(Cj∈C， v∈Vn )， 称有minw(v)的v为平移首， 因此t(C)就是有最大重量的平移首的重量。
对线性码来说， 就是陪集首的最大重量， 而球半径s(C)是码一定能全部纠正的错误数目 显然 s(C)≤t(C)≤d-1 (3.4.3) 第第3章章 线性分组码线性分组码 如果码C的t(C)=s(C)， 则称C码是完备码， 如果 t(C)=s(C)+1 (3.4.4) 则称为准完备码 当n 为奇数时， ［n ， 1， n ］重复码是完备码； 而当n 为偶数时是准完备码 重复码又称为平凡码 第第3章章 线性分组码线性分组码 由最大似然译码原理可知， 要使译码错误概率最小， 必 须使译码表中陪集首的重量最轻 因此， 在同样的码参数下， t(C)越小的码译码错误概率越小， 因而最好 可知t(C)是衡量纠错码性能的又一重要参数 在同样的n 与码字数目下， 完备码与准完备码都能使t(C)最小， 因而是最佳码 第第3章章 线性分组码线性分组码 一般情况下， 我们希望在同样的n ， k 下， 构造出具有最大距离的码， 并且具有最小的t(C)。
但是， 由于构造方法的不同， 这二者之间并不完全一致， 有最大距离的码， 其覆盖半径不一定小 在同样的n ， k 下， 码所能达到的最小覆盖半径用t(n ， k )表示， 线性码用t［n ， k ］表示 下面几个定理说明了二进制分组码的s(C)与t(C)的关系 第第3章章 线性分组码线性分组码 定理3.4.1 对任何二进制(n ， k )码C， 必满足： (3.4.5) 式中， K是码字数目 若C为［n ， k ］线性码， 且n 为偶数， 则必须满足： (3.4.6) 第第3章章 线性分组码线性分组码 该定理称为球包和球包覆盖限， 证明它比较容易 由该定理不难得到t(C)的下限 定理 3.4.2 二进制(n ， k ， d)码的覆盖半径： (3.4.7)和 (3.4.8) (3.4.9) 下面给出t(C)的上限 第第3章章 线性分组码线性分组码 定理 3.4.3 若2≤k ≤1+ln n ， 则［n ， k ］线性码的(3.4.10) 定理 3.4.4 对某一给定的k ， 存在有整数n 1， n 2， …， n q使(3.4.11) 则当n ≥k 时有 第第3章章 线性分组码线性分组码 式中， 表示不小于x的最小整数， 表示x的整数部分。
有关这些限的证明， 和其它各种情况下的上、 下限及目前已知的各种码的覆盖半径， 以及t(n ， k )和 t［n ， k ］， 请参阅文献［6-9］ 如同寻求一个码的实际最小距离一样， 当码长和信息位较大时， 如何分析寻求一个码的覆盖半径是一个很困难的问题 覆盖半径不仅与译码错误概率及码的最小距离有关， 而且还涉及到其它问题， 如好码的构造、 数据压缩中的失真度等问题， 近来日益引起人们的广泛注意 第第3章章 线性分组码线性分组码 §3.5 由一个已知码构造新码的简单方法由一个已知码构造新码的简单方法 一、 扩展码 设C是一个最小距离为d的二进制［n ， k ， d］线性分组码， 它的码字有奇数重量也有偶数重量 若对每一个码字(cn -1， cn -2， …， c1， c0)增加一个校验元c′0， 满足以下校验关系： cn -1+cn -2+…+c1+c0+c′0=0 (3.5.1)称c′0为全校验位 第第3章章 线性分组码线性分组码 若原码的校验矩阵为H， 则扩展码 的校验矩阵 为 ［2m-1， 2m-1-m， 3］汉明码的扩张码是［2m， 2m-1-m， 4］码， 它的 中的H是汉明码的校验 矩阵。
第第3章章 线性分组码线性分组码 例3.5 对例3.3中的［7， 4， 3］汉明码， 附加一个全校验， 则得到了一个［8， 4， 4］扩展汉明码， 它的校验矩阵由式(3.3.6)可得： (3.5.3)可以检验它是一个双偶自对偶码 第第3章章 线性分组码线性分组码 二、 删余码 删余码是由扩展码的逆过程而得到的 它在原［n ， k ］码C的基础上， 删去一个校验元而构成， 变为［n -1， k ］删余码C* C*码的最小距离可能比原码小1， 也可能不变 例如把上例中的［8， 4， 4］码， 删去最后一个校验位c′0， 便变成了［7， 4， 3］汉明码 第第3章章 线性分组码线性分组码 三、 增广码(增信删余码) 增广码Ca是在原码C的基础上， 增加一个信息元， 删去一个校验元得到的 因此， 码长与原码同， 但信息位增加了一个 设原码C是一个没有全 1 码字的 ［n ， k ， d］二进制码， 在它的 G 矩阵上增加一组全为“1”的行， 便得到了增广码Ca的生成矩阵Ga 第第3章章 线性分组码线性分组码 或 Ca=C∪(1+Ci) i=1， 2， …， 2k (3.5.4) 可知增广码Ca是一个［n ， k +1， da］分组码， 其最小距离da由下式决定： da=min {d， n -d′} (3.5.5)式中， d′是原码C中码字的最大重量。
第第3章章 线性分组码线性分组码 如例 3.1 中的［7， 3， 4］码对它进行增广变成为［7， 4， 3］汉明码， 它的生成矩阵由式(3.2.10)为(3.5.6) 第第3章章 线性分组码线性分组码 四、 增余删信码 和增广码构造过程相反的是增余删信码 它是在原码的基础上， 删去一个信息位增加一个校验位得到的， 其实这个过程就是在原来的二进制［n ， k ， d］(d为奇数)码上， 挑选所有偶数重量的码字组成一个新码， 该码就是增余删信码 由定理 3.3.1 可知， 偶数重量码字数是原码字数的一半， 因此增余删信码是一个［n ， k -1， d+1］码 如在［7， 4， 3］汉明码中挑出所有重量为 4 的码字， 便得到一个［7， 3， 4］增余删信汉明码 第第3章章 线性分组码线性分组码 五、 延长码(增信码)与RM码 延长码是在原［n ， k ］码C的基础上， 先进行增广然后再加一个全校验位构成的 因此， 延长码是一个［n +1， k +1］分组码。
延长码的码率 比原码的码率R=k ／n 要大一些， 其码的最小距离也可能与原码相同 第第3章章 线性分组码线性分组码 例如， 可把［7， 3， 4］增余删信汉明码先进行增广， 变成［7， 4， 3］汉明码， 然后再增加一个全校验位， 变成［8， 4， 4］扩展汉明码 该码比原来的［7， 3， 4］码的R要高， 而最小距离相同 现以［7， 3， 4］汉明码为例， 把上述各类码之间的关系， 画于图 3 - 2 中 第第3章章 线性分组码线性分组码 图 3 - 2 汉明码的各类修正码之间的关系图 第第3章章 线性分组码线性分组码 如果把(2m-1， 2m-1-m， 3)汉明码的对偶码， 也就是单纯码(2m-1， m， 2m-1)进行延长， 就得到一个(2m， m+1， 2m-1)码， 称它为一阶里德-谬勒尔( Reed-Muller码)用RM(1， m)表示 RM码是Muller于 1954 年提出其构造方法， 同年Reed用大数逻辑译码方法解决了它的译码 RM码最早是从线性空间的角度出发构造的， 以后发现它与循环码、 几何码和格等有密切关系， 因此这是一类很重要的线性码［2,3］。
第第3章章 线性分组码线性分组码 一般而言， r阶RM码RM(r， m)是［2m， k ， 2m-r］码，其中 所以它的对偶码［2m， 2m-k ， 2r］码是一个m-r-1阶的RM(m-r-1， m)码 第第3章章 线性分组码线性分组码 现以m=3为例说明RM码的生成， RM(r， 3)码从以下矢量中挑选构造G矩阵的行 V0=(11111111) V3=(00001111) V2=(00110011) V1=(01010101) V3V2=(00000011) V3V1=(00000101) V2V1=(00010001) V3V2V1=(00000001) 第第3章章 线性分组码线性分组码 如果码以V0， V3， V2， V1作为G矩阵的行， 则得到一个RM(1， 3)码的生成矩阵 可以证明， RM(1， 3)码是一个E8格 如果挑选V0至V2V1等 7 个矢量作为G矩阵的行， 则得到一个二阶RM(2， 3)码 可以验证用这种方法构造的RM(1， 3)码， 经过适当的线性组合就是［7， 3， 4］单纯码进行延长得到的码。
有关RM码的详细讨论及译码方法请参阅［2］ 第第3章章 线性分组码线性分组码 *§3.6 用多个已知码构造新码的方法用多个已知码构造新码的方法 一、 直和 设C1和C2分别是［n 1， k 1， d1］和 ［n 2， k 2， d2］二进制码， 且n 1=n 2， C1∩C2=0， 则定义C1和C2码的直和码C1⊕C2=C是 C={(a⊕b)｜a∈C1， b∈C2} (3.6.1) 第第3章章 线性分组码线性分组码 式中， ⊕表示a， b两个码字按位模 2 加 直和码C的生成矩阵(3.6.2) 第第3章章 线性分组码线性分组码 式中， G1和G2分别是C1和C2码的生成矩阵 由此G矩阵就生成一个［n ， k 1+k 2， d)码， d≤min {d1， d2} 例如， C1是一个［7， 1， 7］重复码， C2是 ［7， 3， 4］单纯码， 且C1∩C2=0。
它们的生成矩阵分别是： (3.6.3) 第第3章章 线性分组码线性分组码 则C1⊕C2=C码的生成矩阵可知这是一个［7， 4， 3］汉明码 第第3章章 线性分组码线性分组码 若用l个等码长， 且除全 0 码字外均互不相交的线性分组码C1， C2， …， Cl直和， 则得到一个 ［n ， k 1+k 2+…+k l， d］线性分组码， d≤min {d1， d2， …， dl}， G矩阵与式(3.6.2)形式相同， 为l个生成矩阵之和 如果C1和C2码的覆盖半径分别是t(C1)和t(C2)， 则直和码C的覆盖半径 t(C)≤min (t(C1)， t(C2)) (3.6.4) 上例中t(C)≤min (3， 2)， 实际上t(C)=1 若为多个码直和， 则 t(C)≤min (t(C1)， t(C2)， …， t(Cl)) 第第3章章 线性分组码线性分组码 二、 笛卡儿积 由C1和C2码的笛卡儿积C1×C2得到的码是 C=C1×C2={(a， b)｜a∈C1， b∈C2} (3.6.5)可知， C码是一个［n 1+n 2， k 1+k 2， min {d1， d2}］码。
该码的生成矩阵(3.6.6) 第第3章章 线性分组码线性分组码 式中， 01和02分别是k 2×n 1阶和k 1×n 2阶全0阵 例如， C1是［3， 1， 3］重复码， C2是［7， 3， 4］单纯码， 则它们的笛卡儿积码C的生成矩阵 第第3章章 线性分组码线性分组码 由此得到一个［10， 4， 3］码 笛卡儿积C1×C2=C码的覆盖半径 t(C)=t(C1)+t(C2) (3.6.7) 该例中t(C)=t(C1)+t(C2)=1+2=3 第第3章章 线性分组码线性分组码 三、 链接 C1和C2码的链接码C=C1+C2， 是一个 ［n 1+n 2， k 2， d］码， 这里要求k 2≥k 1， d≥min {d1， d2} 链接码C的生成矩阵 第第3章章 线性分组码线性分组码 式中， 0 是(k 2-k 1)×n 1阶全 0 矩阵。
如C1码是 ［3， 1， 3］重复码， C2是［7， 3， 4］单纯码， 则C=C1+C2 码的生成矩阵 第第3章章 线性分组码线性分组码 得到一个［10， 3， 4］码 链接码的覆盖半径 t(C)≥t(C1)+t(C2) (3.6.9)该例中C1+C2=C码的覆盖半径是 3 第第3章章 线性分组码线性分组码 四、 ［C1， C1+C2］构造 设n1=n2， 且C2C1， 则C码是 C={(a， a+b)； a∈C1， b∈C2} (3.6.10) 可知要求C1与C2码的码长相等， n1=n2=n C码的生成矩阵(3.6.11) 第第3章章 线性分组码线性分组码 五、 直积(Kronecker积) C1和C2码的直积C1C2=C， 是一个 ［n1n2， k1k2， d1d2］码 C码的生成矩阵 (3.6.13) 式中， gij是C1码生成矩阵中第i行第j列元素 第第3章章 线性分组码线性分组码 §3.7 线性码的重量分布与译码错误概率线性码的重量分布与译码错误概率 ［n， k， d］线性分组码的不可检错误概率和译码错误概率的计算， 是估计FEC和ARQ等差错控制系统性能的基础。
但译码错误概率和不可检错误概率的计算， 又与码的重量分布密切相关 第第3章章 线性分组码线性分组码 一、 线性码的重量分布 所谓码的重量分布是指一个［n， k， d］线性分组码或非线性码的码字重量的分布情况， 它不仅是计算各种译码错误概率的主要依据之一， 而且也是探索码结构的重要窗口， 通过它能透彻地了解码的内部关系 第第3章章 线性分组码线性分组码 设Ai是［n， k， d］分组码中重量为i的码字数目， 则集合{A0， A1， …， An}称为该分组码的重量分布 例如［7， 4， 3］汉明码的重量分布为{Ai}={A0， A1， A2， A3， A4， A5， A6， A7} ={1， 0， 0， 7， 7， 0， 0， 1}其中， 一个全0码字(A0=1)是任何线性码所必须有的 第第3章章 线性分组码线性分组码 也可把码的重量分布{A0， A1， …， An}写成如下形式的多项式： (3.7.1) 称A(x)为码的重量估值算子， 简称重量算子。
第第3章章 线性分组码线性分组码 定理3.7.1 设二进制［n， k］线性分组码及其 ［n， n-k］对偶码的重量算子分别是： 则它们之间有如下关系： (3.7.2)称此式为马克威伦( MacWilliams)恒等式 第第3章章 线性分组码线性分组码 证明 设C是二进制n重， 它的汉明重量w(C)=w， 产生该n重的概率定义为 P(C)=εw(1-ε)n-w 0≤ε≤1 设H为码的校验矩阵， 则C的伴随式S(C)=HCT=S， 这里CT是C的转置 令E是使S(C)=0 的事件， 现计算事件E出现的概率P(E) 第第3章章 线性分组码线性分组码 二、 线性分组码的不可检错误概率 根据不同的译码方法和译码器， 一般译码错误概率分为不可检错误概率、 译码失败概率和译码错误概率 正确计算一个码的不可检错误概率， 在ARQ和HEC差错控制系统的性能分析中起着重要作用 第第3章章 线性分组码线性分组码 码字通过BSC传输时， 若由于干扰变成了另一码字， 则检错译码器就不能发现此种类型的错误， 产生了不可检错误。
所以码长为n， 有M个码字， 最小距离为d的(n， M， d)二进制分组码的平均不可检错误概率 (3.7.12) 第第3章章 线性分组码线性分组码 式中， pe是BSC的误码率， Pj是发第j个码字的概率， Aj， i是与第j个码字的距离为i的码字数 设Aj(x)=Aj， 0+Aj, 1 x+Aj,2 x2+…+Aj, nxn j=1， 2， …， M是(n， M， d)码中第j个码字的距离分布多项式 若对码中所有码字恒有 Aj(x)=A(x)=A0+A1x+A2x2+…+Anxn则此码称为不变距离分布码或同距离分布码 第第3章章 线性分组码线性分组码 对线性码而言， 由于码的封闭性， 可知是同距离分布码， 且码的距离分布就等于码的重量分布 可知， 对［n， k， d］二进制线性分组码的不可检错误概率， 由式(3.7.12)可得为 (3.7.13) 若码字等概发送， 则上式成为 (3.7.14) 第第3章章 线性分组码线性分组码 式中， Ai是［ n， k， d］码的重量为i的码字数， 由于码的最小距离等于d， 所以A1=A2=…=Ad-1=0。
第第3章章 线性分组码线性分组码 定理3.7.2［4］ 二进制［n， k］线性分组码集合中， 码的平均不可检错误概率 (3.7.18) 式中， pe是BSC的误码率 通常情况下， 1-(1-pe)k≤1， 所以 (3.7.19) 第第3章章 线性分组码线性分组码 是在所有2k(n-k)-1个［n， k］分组码构成的码集合中的平均不可检错误的概率 因此， 在0≤pe≤1／2时， 必定在该集合中存在有不可检错误概率Pud≤2-(n-k)的二进制码， 称这类码为最佳检错码 类似地， 对于q进制［n， k］线性码， 有 ≤q-(n-k) (3.7.20) 在q进制信道的误码率0≤pe≤(q-1)／q范围内， 满足该式的码也称为最佳检错码 第第3章章 线性分组码线性分组码 那么， 如何判断一个［n， k］码， 在BSC的误码率满足0≤pe≤1／2范围内， 其不可检错误概率是否服从Pud≤2-(n-k)的上限呢？显然， 如果我们能够证明任何码(线性或非线性码)的Pud是pe的单调增函数， 即 (3.7.21) 第第3章章 线性分组码线性分组码 则该［n， k］码的Pud服从2-(n-k)的上限， 对非线性码而言， 则是最佳的。
因为当pe=1／2时， 所有2n个n重在接收端出现的机会均等， 其概率是2-n， 在这2n个中仅有2k个是码字， 其中之一是发的码字 因此， 当pe=1／2时， ［n， k］码的不可检错误概率 Pud(1／2)=(2k-1)2-n=2-(n-k)-2-n＜2-(n-k) (3.7.22)说明在最大误码率情况下， Pud不会超过2-(n-k) 可知2-(n-k)是不可检错误概率的上限 第第3章章 线性分组码线性分组码 三、 译码错误与译码失败概率 如果［n， k， d］码的译码器， 用来纠t个错误， 同时检测e个错误， 则称为teD译码器， 此时要求d≥t+e+1， e≥t 0eD是纯检错译码器， 这时e≤d-1； t0D是纯纠错译码器， 此时t≤［(d-1)／2］ 显然， teD译码器是一类限定距离译码器 teD译码器正确译码的码字概率 (3.7.23) 这里及以后pe均指BSC的误码率， 且码字等概发送 第第3章章 线性分组码线性分组码 译码中， 若teD译码器输出的码字与发送的码字不相同， 则产生了译码错误。
如果译码器不能译出码字， 而仅指出收到的码字有错， 则称为译码失败 下面先讨论译码错误概率 由于线性码的封闭性， 不失一般性我们认为发的是全 0 码字 当接收到的n重进入除全 0 码字以外的其它码字的译码区域内时， 则产生了译码错误 这里所指的每个码字的译码区域， 是在n维线性空间中以该码字为中心、 以t为半径的球 显然， 当收到的n重落入该球内时， 则该n重译成处在球心的码字 第第3章章 线性分组码线性分组码 令Bi表示重量为 2i， 落入除全0码字以外的全部(2k-1个)码字译码区域内的所有n重数目， 因此译码错误概率(3.7.24) 设u是A码的一个码字， φ(i， j， s)表示满足下列条件的n重v的数目： w(u)=j w(v)=i d(u， v)=s 0≤s≤t 第第3章章 线性分组码线性分组码 设u和v两个n重的组成如下： ｜←j→｜←n-j→｜ u： (1…11…10…00…0) ｜←x→｜←s-x→｜ v： (0…01…11…10…0) ｜←i→｜ 由此可以看出， x=(j-i+s)／2， 且要求0≤j≤s， s-x≤n-j。
由此可得： 第第3章章 线性分组码线性分组码 x=(j-i+s)／2， 是整数， 且 min(2n-i-j， i+j)≥s≥｜j-i｜ 其它 所以 (3.7.25) 第第3章章 线性分组码线性分组码 式中， Aj是线性码A的重量为j的码字数目 可知译码错误概率(3.7.26) 而译码失败概率 Pwf=1-Pwc-Pwe 第第3章章 线性分组码线性分组码 四、 误码率计算 误码率是衡量一个数字通信系统质量的重要指标 下面讨论如何计算teD译码器的误码率 设发送的仍为全0码字， 接收的n重落入重量为j的码字的译码区域时， 译码器输出重量为j的码字， 因此产生了j个码元错误 产生这种事件的概率为(3.7.27) 第第3章章 线性分组码线性分组码 设j个错误在n长码字内均匀分布， 则译码后的误码率(3.7.28) 而译码失败引起的误码率(3.7.29)pb+p′b称为etD译码器的输出误码率 式中Bi由式(3.7.25)决定 第第3章章 线性分组码线性分组码 §3.8 线性码的纠错能力线性码的纠错能力 一、 普洛特金 (Plotkin)限(P限) 定理3.8.1 GF(q)上(n， M， d)分组码的最小距离d为(3.8.1) 第第3章章 线性分组码线性分组码 证明 GF(q)上(n， M， d)码的码字 (cn-1， cn-2， …， c1， c0)中， ci∈GF(q)。
设GF(q)中的q个元素是{α1， α2， …， αq} M个码字中， 第一位(cn-1)取值为αi的码字假设有Mi个， 则M1+M2+…+Mq=M 第一位取值不是αi的共有M-Mi个码字 因此， 第一位取值为αi的码字与其它(M-Mi)个码字， 由于这一位不同而带来的总距离是Mi(M-Mi) 第第3章章 线性分组码线性分组码 cn-1这一位可以有q种不同取值， 因此由于cn-1不同所带来的总距离 s1 =M1(M-M1)+M2(M-M2)+…+Mq(M-Mq) =M2-(M21+M22+…+M2q) 第第3章章 线性分组码线性分组码 为了使s1最大， 就必须要求M最大、 最小， 仅当M1=M2=…=Mq=M／q时才能满足此要求 因而s1≤M2(q-1)／q， 该式是仅考虑码中第一位不同的所有码对给出的总距离 由于每个码字有n位， 因此码中所有不同码对所给出的总距离是nM2(q-1)／q (n， M， d)码中共有M(M-1)对不同的码字对， 因此不同码字对之间的平均距离码的最小距离d不可能大于平均距离dav， 因此d≤nM(q-1)／［(M-1)q］。
第第3章章 线性分组码线性分组码 若为q进制线性分组码， 则码字数M=qk， 因而由式(3.8.1)立刻可得 d≤nqk-1(q-1)／(qk-1) (3.8.2) 由此定理还可推出给定n、 d条件下的M的上限， 以及给定k和d条件下码长n的最小值 第第3章章 线性分组码线性分组码 二、 汉明限(球包限、 H限) 定理3.8.2 长为n纠t个错误的q进制分组码为(3.8.3) 第第3章章 线性分组码线性分组码 证明 由式(3.8.3)可立即得到q进制［n， k， 2t+1］线性分组码校验位数目的下限为 (3.8.4) 在二进制情况下， 上式可简化为 (3.8.5) 第第3章章 线性分组码线性分组码 三、 沃尔沙莫夫-吉尔伯特(V-G)限定理3.8.3 若码的校验元数目n-k满足(3.8.6) 的最小整数， 则一定可以构造出一个长为n、 最小距离为d的［n， k］线性分组码 第第3章章 线性分组码线性分组码 四、 讨论 Plotkin限和汉明限都是构成码的必要条件， 任何码都必须满足此必要条件， 越接近它就越有效， 等于它时就达到最佳。
而V-G限是充分条件， 并限定于线性码， 满足这一条件必存在一个最小距离为d的［n， k］线性码 但是， 当n→∞时， 满足V-G限的线性码目前仅找到两类： 某些代数几何码(包括Goppa码)和Justesen码 有些码类， 如［2m， m］二进制准循环码， 码字重量为4m的线性二进制自对偶码， 已证明能接近V-G限， 但遗憾的是直到目前还未找到具体的构造方法 第第3章章 线性分组码线性分组码 当n→∞时， 比较这3个限所表示的n、 R、 d之间的关系(只限于二进制码)： (1) 当n→∞时由P限可推出 k／n≤1-2d／n (3.8.8) (2) 由汉明限可得到 k／n≤1-H2(d／2n) (3.8.9) (3) 由V-G限可导出 k／n≥1-H2(d／n) (3.8.10) 第第3章章 线性分组码线性分组码 式中 H2(x)=-xlog2x-(1-x)log2(1-x) 由图 3 - 3可以看出， 当n、 d给定时， P限和汉明限给出了传信率R的上限， 而V-G限提供了R的下限。
当n、 k给定时， P限和汉明限给出了最小距离d的上限， 而V-G限给出了最小距离的下限 在相同条件下， 最小距离越接近于上限的码越好 第第3章章 线性分组码线性分组码 图 3 - 3 二进制下三个码限比较图 第第3章章 线性分组码线性分组码 从图可以看到P限和汉明限有一个交叉点在R=0.4， d／2n=0.156 附近 当d／2n＜0.156时(高码率， 低纠错力的码)应用汉明限较精确， 而当d／2n≥0.156时(低码率， 强纠错能力的码)则应用P限较精确 图中的所有斜线区是可能实现部分， 而双重斜线部分是必能实现的部分 在相同条件下， 越接近斜线区上边缘的码越好 第第3章章 线性分组码线性分组码 某些高码率的里德-缪勒尔(Reed-Muller， RM)码和汉明码， 以及某些BCH码与汉明限符合， 故为最佳码 而低码率的RM码及BCH码等， 与P限符合， 也为最佳码 第第3章章 线性分组码线性分组码 香农的编码定理指出存在有n→∞， 码率接近信道容量， 译码误码率接近0的分组码(称这种码为Shannon码或渐近好码)， 而V-G限也保证存在有这种性能的码， 因此达到或超过V-G限的码是渐进好码。
但上述的这两类码当n→∞时， 高码率码的R→1， 而其纠错能力d／2n→0； 而低码率码在n→∞时， d／2n→1／4， 但R→0 此外， 对于中等速率的码来说， 如某些BCH码和中码率RM码， 在保证码率k／n不为零条件下， 当n→∞时， d／2n→0， 因此都不符合Shannon码的要求 第第3章章 线性分组码线性分组码 直到1970年Goppa才找到了一类线性码——Goppa码， 这类码中的一个子类能达到n→∞时性能接近V-G限 但当n→∞时， 如何具体构造出这类码仍很困难， 而且达到V-G限的译码方法至今仍没有解决 1972年Justesen构造的Justesen码也能做到n→∞， R一定时， d／2n＞0， 但遗憾的是当码率R＜0.3时离V-G限还有相当距离 第第3章章 线性分组码线性分组码 80年代初Goppa把分组码看成是射影平面上的曲线， 从而把代数几何引入了分组码的构造 1982年， 斯法斯曼(Tsfasman)等人利用模(Modular)曲线构造了一类代数几何码， 当q≥49时， 其性能超过了V-G限 这具有重大的理论意义， 说明从理论上讲， 利用代数几何方法可以构造出Shannon码。
但是， 正如同Goppa码所遇到的困难一样， 当n→∞时， 如何构造这类码以及如何译码， 都没有完全解决 这也说明如何具体地构造Shannon码仍是一个没有解决的问题， 也是当前编码理论研究的热门课题之一 第第3章章 线性分组码线性分组码 ＊＊§3.9 不等保护能力线性分组码不等保护能力线性分组码 前面所介绍的线性分组码， 都是等保护能力的， 也就是对码字中每个码元的保护能力均相等 例如， ［7， 4， 3］汉明码， 它能纠一个随机错误， 不论这一个错误产生在被传码字中的哪一位， 译码时均能纠正， 可知每个码元平均的抗干扰能力为1／7 也就是码对每位码元或信息元均一视同仁的按照1／7的能力保护 对一般的［n， k， d］分组码来说， 每位码元平均的保护能力为t／n或d／n 第第3章章 线性分组码线性分组码 然而， 在很多实际场合中， 某些信息位的重要性比其余的要高得多 例如， 在银行数据传输中， 前面的收、 支符号及高值位的数据， 如亿、 万、 千等， 比低值位的数据角、 分等重要得多 又例如， 在多用户数据传输中， 某些用户的数据比其余的重要得多。
因此， 就提出了一个要求： 对不同的数据(信息元)， 要按照其重要程度， 分别予以不同的抗干扰保护 能完成这种不等保护能力的纠错码， 称为不等保护能力码， 简称UEP码 若线性码具有不等保护能力， 则称为LUEP码 第第3章章 线性分组码线性分组码 一、 UEP码的基本概念 下面先通过一具体例子， 说明UEP码的基本概念 若要传输的两个信息元是m1、 m2， 现要求编成长为4的码 下表给出了［4， 2］码的两种不同编码方法得到的C1和C2码 第第3章章 线性分组码线性分组码 可知C1和C2码的 但C2码是系统码， 而C1码是非系统码 C1与C2码的最小距离均为2， 由定理1.3.1知， 它们均不能纠正单个错误 但是对C1码来说， 却可以纠正m2信息位的错误 第第3章章 线性分组码线性分组码 设发送的码字是(0000)， 接收的是(0100)， 按最小汉明距离译码方法， 译码器译成(0000)或(1100) 但无论译成谁， 对应的信息位m2均是0， 也就是该码能纠正信息位m2的一位错误， 但不能纠正m1中的错误。
因此， C1码是一个不等纠错能力保护码 由此看出， 对不等纠错能力保护码来说， 即使整个码组可能译错了， 但却能保证受高等级保护能力的信息位是正确的 如上例中C1码的d虽然只有2， 却能纠正信息位m2的错误， 但不能纠正m1的错误 第第3章章 线性分组码线性分组码 对一个码字来说， 我们仅关心其中信息位的保护能力， 因此对每一信息位， 定义一个保护能力大小的度量 如同用码的最小距离定义码的抗干扰能力一样， 我们也可对每一位信息位定义一个最小距离， 这k个最小距离所组成的矢量， 称为码的分离矢量 第第3章章 线性分组码线性分组码 定义3.9.1 称k重矢量s=(s1， s2， …， sk)为GF(q)(q=pm， p为素数)上［n， k］线性系统分组码C的分离矢量， 其中 si=min{w(MG)； M∈GF(q)k， mi≠0， i=1， 2， …， k} (3.9.1)M=(m1， m2， …， mk)是信息组， G是C码的生成矩阵， GF(q)k是GF(q)上的k维线性空间。
第第3章章 线性分组码线性分组码 式(3.9.1)说明对任何α， β∈GF(q)， 当α≠β时， 集合{MG；M∈GF(q)k， mi=α}和{MG； M∈GF(q)k， mi=β}的最小距离为si， i=1， 2， …， k 由定义3.9.1可知， 码的最小距离d=min{si， i=1， 2， …， k}， 如果码的分离矢量s中的k个si分量不完全相同， 则该码称为线性不等保护能力码(LUEP)， 否则就是一般的等保护能力码 第第3章章 线性分组码线性分组码 引理3.9.1 ［n， k］线性码的第i位信息位有保护能力为ti的充要条件是： 第i位信息位为非零的码字之间的最小距离di≥2ti+1； 或分离矢量的第i个分量si≥2ti+1， 即第i位信息元mi≠0的码字的重量w(Ci)≥2ti+1 第第3章章 线性分组码线性分组码 二、 LUEP 码的生成矩阵和校验矩阵 下面定理给出了 LUEP 码的码字集合所必须满足的条件 定理3.9.1 为了使［n， k］码V的不少于k*个信息元有保护能力为δ， 则其充要条件是码字集合{CM}={Ci∈V， w(Ci)≤2δ}所组成的线性子空间的维数不大于k-k*。
第第3章章 线性分组码线性分组码 推论3.9.1 ［n， k］码V的k*个信息元有保护能力为δ的充要条件是： 码V=V*V′， V′码的维数为k*， 而所有重量不大于2δ的码字在V*中 由此推论可得到有k*个信息元的保护能力至少为δ的LUEP码的生成矩阵(3.9.2) 第第3章章 线性分组码线性分组码 对式(3.9.2)的G矩阵进行初等行变换可得到LUEP码的典型G矩阵 第第3章章 线性分组码线性分组码 (3.9.3) 第第3章章 线性分组码线性分组码 由式(3.9.3)所生成的码并不是系统码， 必须对该矩阵再进行初等行变换才能得到系统码形式的生成矩阵 如V′与V*码均是二进制［10， 2］码， 它们的生成矩阵分别是： 第第3章章 线性分组码线性分组码 则二进制［10， 4］LUEP码的典型形式的生成矩阵是 第第3章章 线性分组码线性分组码 对它进行初等行变换可得到如下的系统码形式的生成矩阵和校验矩阵： 第第3章章 线性分组码线性分组码 可以检验， 该码的分离矢量s=(5， 5， 4， 4)， 是一个［10， 4， 4］LUEP码， 前两个信息元具有纠 2 个错误的保护能力， 后两个信息元只具有纠 1 个错误的保护能力。
可以把定理3.9.1的结果推广到具有多级保护能力的码 第第3章章 线性分组码线性分组码 定理3.9.2 为了对［n， k］线性码V的不少于li个信息元提供ti保护能力， i=1， 2， …， u 其充要条件是： 对任何码字集合{C i}={Ci∈V； w(Ci)≤2ti}所组成的子空间具有维数不大于k-li 这里， t1≤t2≤…≤tu， ， 显然li=k 第第3章章 线性分组码线性分组码 定理3.9.3 ［n， k］线性分组码V的第i个码元有保护能力为ti的充要条件是， V的校验矩阵H的第i列与任意的不少于2ti列线性相关， 或与任意的2ti-1或更少列线性无关 该定理与定理3.3.1相似， 其证明方法也相同 第第3章章 线性分组码线性分组码 三、 LUEP 码的构造 根据定理3.9.1和定理3.9.2或定理3.9,3， 利用已知分组码通过上节介绍的各种组合方法， 就可构造各种LUEP码。
1. 码的直和构造 定理3.9.2和定理3.9.3告诉我们， 利用多个不同纠错能力分组码， 构造LUEP码所必须满足的条件 下面定理以更明确的形式给出用m个不同码， 利用直和方法构造LUEP码所必须满足的条件 第第3章章 线性分组码线性分组码 定理3.9.4［13］ 令Ci是［n， ki］二进制线性分组码， i=1， 2， …， m 令C=C1 C2…Cm是C1， C2， …， Cm的直和， 若以下的距离条件满足： (1) Cm中的任一非零码字的重量至少是dm； (2) 在C-Ci+1Ci+2…Cm中， 任一码字的重量至少是di， i=1， 2， …， m， 且d1＞d2…＞dm 则C是一个m级LUEP码， 有分离矢量s=(s1， s2， …， sm)， 这里si≥di， i=1， 2， …， m 第第3章章 线性分组码线性分组码 该定理的证明类似于定理3.9.1［10,13］ 设C1， C2， …， Cm码的生成矩阵分别是G1， G2， …， Gm， 则C码的生成矩阵 G=［GT1 GT2 … GTm］T (3.9.5) 2. 码的链接构造 第第3章章 线性分组码线性分组码 定理 3.9.5 由式(3.9.6)G矩阵生成了一个GF(q)上的［n1+n2， k1， ］码C， 有k2个信息元具有 t2=［(d1+d2-1)／2］级保护能力。
第第3章章 线性分组码线性分组码 一般而言， 式(3.9.6)的G矩阵是与式(3.9.3)不同的非典型形式， 为了得到等价的典型形式， 可先对G1矩阵进行初等行变换， 成为 G2=［ P2］ 由此得到C码的典型形式生成矩阵(3.9.7) 然而再对式(3.9.7)的G进行初等行变换就可得到系统码的生成矩阵 第第3章章 线性分组码线性分组码 四、 有关码限 在给定码的维数(即信息元的数目)和分离矢量下， 使码长最短或使校验元数目最少， 从而使码具有最大的码率， 是构造LUEP码的基本问题之一 定义3.9.2 定义nqs是分离矢量至少为s， 信息元数目为k的q进制LUEP码的最短的码长 neqs表示分离矢量恰好为s， 信息元数目为k的q进制LUEP码的最佳码长 第第3章章 线性分组码线性分组码 用［n， k， s］表示分离矢量为s的LUEP码 如果当t≥s， t≠s时， 不存在任何的q进制［nqs， k， t］LUEP码， 则称可以构造出的［nqs， k， t］码是最佳码。
显然 nqs≤neqs (3.9.8) s≤tneqs≤nqt (3.9.9) s≤tneqs≤neqt (3.9.10)今后规定： 若si≥ti， i=1， 2， …， k， 则分离矢量s=(s1， s2， …， sk)≥t=(t1， t2， …， tk) 第第3章章 线性分组码线性分组码 1. 码长上限 定理3.9.6 对任一q=pm，k，v和分离矢量s=(s1，s2，…，sv)，这里si=(si1，si2，…，sim)， 且 下式成立： (3.9.11) 对nqs也有同样的不等式 第第3章章 线性分组码线性分组码 证明 对u=1， 2， …， v， 令Gu是码长为neqsu分离矢量是su的LUEP码的生成矩阵， 则由 (3.9.12) 生成的码有分离矢量s=(s1， s2， …， sv)， 码长为neqsu， 而该码显然是最长码长的LUEP码。
第第3章章 线性分组码线性分组码 推论3.9.2 对任何k， s=(s1， s2， …， sk)， q=pm， 有(3.9.13) 第第3章章 线性分组码线性分组码 证明 应用定理3.9.6， 令v=k， Gu=［1 1 … 1］， 对所有u=1， 2， …， k， su=1， 即可得到 因此可知， 对任何s， 有可能构造出k维的有分离矢量为s的q进制LUEP码， 当然所构造出的码不一定是最佳的， 如用式(3.9.12)的G矩阵所生成的码， 就不一定是最佳的 第第3章章 线性分组码线性分组码 2.码长下限 定理 3.9.7 对任何q=pm， k和s=(s1， s2， …， sk)， s′=(s1-1， s2-1， …， sk-1)有 nqs≥nqs′+1 (3.9.14) 证明 在［nqs， k， s］LUEP码的生成矩阵G中， 删去一列， 就得到［nqs-1， k， s′］的LUEP码。
第第3章章 线性分组码线性分组码 定理 3.9.8 对任何q=pm， k和s=(s1， s2， …， sk)， 且s1≥s2≥…≥sk， 满足以下不等式： (3.9.15) 式中， ［x］表示不小于x的最小整数 第第3章章 线性分组码线性分组码 该定理的证明比较长， 请参阅［12］ 上面这些定理给出了当k、 s给定时LUEP码的码长上、 下限 下面我们讨论当k和s给定时， 具有二级保护能力的LUEP码的校验元数目r， 所必须满足的下限， 当然此限与上面讨论的码长的限是一致的 第第3章章 线性分组码线性分组码 定理3.9.9 对任何k和s=(sk1， sk2)， sk1=(2t1+1， …， 2t1+1)和sk2=(2t2+1， …， 2t2+1)分别是长为k1和k2的整数序列， t2≥t1， k=k1+k2， 则［n， k， s］二进制LUEP码的校验元数目(3.9.16) 第第3章章 线性分组码线性分组码 证明 由前一节知， 为了使码能纠正t个错误， 则必须使≤t 个错误的所有可能的错误图样， 均有不同的伴随式与之一一对应。
式(3.9.16)不等式的右边第一项表示没有错误， 需一个全0伴随式与之对应； 第二项表示≤t1个错误时， 所有可能的错误图样； 第三项表示在n-k2个码元中产生i个错误， 在k2个信息元中产生t2-i个错误的所有错误图样； 而所有这些错误图样之和应小于2r 第第3章章 线性分组码线性分组码 能使式(3.9.16)成立的LUEP码， 称为完备LUEP码， 完备码当然是最佳的 但到目前为止， 还没有找到一个完备LUEP码， 在GF(q)上是否存在有完备LUEP码， 还是一个没有解决的问题 第第3章章 线性分组码线性分组码 *§3.10 纠非对称、纠非对称、 单向错误及单向错误及t-ECAUED码码 一、 基本概念 首先， 再次明确一下什么是对称错误、 非对称错误和单向错误 对称错误(随机错误)： 在对称信道中(如BSC和DMC)所引起的错误， 称为对称错误 非对称错误： 在Z信道中所产生的错误称为非对称错误 也就是在该信道中仅产生 1 错误或 0 错误， 并且产生什么类型的错误事前是已知的。
若无特别说明， 以后均指产生 1 错误的非对称信道 第第3章章 线性分组码线性分组码 单向错误： 在接收的一个码字中既可能是 1 错误， 也可能是 0 错误 但是， 在任何一个接收的码字中， 仅产生一种类型的错误(或者是 1 错误， 或者是 0 错误)， 即 0 错误或 1 错误不能同时在一个接收码字中并存 产生这种错误类型的信道简称单向信道 第第3章章 线性分组码线性分组码 下面介绍一下适用于这些信道纠错码的有关距离函数 设 u=(un-1， …， u1， u0)∈Vn v=(vn-1， …， v1， v0)∈Vn 令 N(u， v)={i｜ui=1∧(同时)vi=0}也即N(u， v)是对应位分量中， ui为 1， vi为 0 的数目 N(u， v)=0， 则称为矢量u被矢量v所包含， 或 v包含u， 用v≥u表示之 第第3章章 线性分组码线性分组码 定义3.10.1 设所传输的矢量u∈Vn， 而接收的矢量为f∈Vn， 并有 (a) 若{N(u， f)+N(f， u)=t}， 则称u有t个随机错误； (b) 若{N(f， u)=0∧N(u， f)=t}， 则称u有t个非对称错误(1错误)； 第第3章章 线性分组码线性分组码 (c) 若{N(u， f)=0∧N(f， u)=t∨(或者)(N(u， f )=t∧N(f， u)=0)}， 则称u有t个单向错误。
例如： 令n=10， 且 u=1111100000 f1=1100010001 f2=1110000000 f3=1111100001 第第3章章 线性分组码线性分组码 当在对称信道中传输u时， 接收端可能收到有f1(t=5)， f2(t=2)， f3(t=1) 当u在非对称信道传输时， 则仅可能收到 f2， 而决不可能收到f1或f3 若在单向信道传输时， 则仅可能收到f2或f3， 而决不可能收到f1 为了研究分组码C的纠错能力， 必须定义针对对称、 非对称与单向信道纠错码的距离度量 显然， §1.3定义的汉明距离 d(u， v)=N(u， v)+N(v， u) (3.10.1) 第第3章章 线性分组码线性分组码 定义3.10.2 令u∈Vn， v∈Vn， 则 (1) da(u， v)=2max{N(u， v)， N(v， u)} du(u， v) 若N(u， v)＝0∨N(v， u)=0 (2) du(u， v)= da(u， v) 若N(u， v)＞0∧N(v， u)＞0 称da(u， v)为u、 v之间的非对称距离， du( u， v)为单向距离， 而汉明距离d(u， v)称为对称距离。
第第3章章 线性分组码线性分组码 这三种距离之间的关系显而易见为da(u， v)=d(u， v)+［w(u)-w(v)］ (3.10.2)若w(u)=w(v)， 则d(u， v)=da(u， v)-du(u， v) (3.10.3) 一个分组码C的单向距离与非对称距离定义为： du=min{du(u， v)｜u， v∈C， u≠v} da=min{da(u， v)｜u， v∈C， u≠v} 第第3章章 线性分组码线性分组码 例如， C是码长为8， 含有以下4个码字的集合： C1=(10000000) C2=(01110000) C3=(00001110) C4=(11101101) 显然， 该码是非线性分组码， 它的汉明、 非对称和单向距离分别是d=4， da=6， du=5 与定理1.3.1相似， 下面定理给出了分组码C能纠正t个非对称错误或单向错误的充要条件 第第3章章 线性分组码线性分组码 定理3.10.1(1) 当且仅当da≥2t+1时， 码C能纠正≤t个非对称错误； (2) 当且仅当du≥2t+1时， 码C能纠正≤t个单向错误。
证明 先证明(2)， 定义S0(x)={a∈Vn｜a≥x∧w(a)-w(x)≤t}， x∈Vn S1(x)={a∈Vn｜x≥a∧w(x)-w(a)≤t}， x∈Vn S(x)=S0(x)∪S1(x) 第第3章章 线性分组码线性分组码 定理 3.10.2 一个码C能纠正t个随机错误， 同时检测e个(e＞t)单向错误(t-EC／e-UED)的充要条件是： (1) d(C1， C2)=t+e+1 C1， C2∈C， C1≠C2； 或 (2) N(C1， C2)≥t+1， N(C2， C1)≥t+1 第第3章章 线性分组码线性分组码 推论3.10.1 码C能纠正t个随机错误， 同时检测所有单向错误(t-EC／AUED)的充要条件是对码中的任何两个码字C1、 C2， C1≠C2， 有 N(C1， C2)≥t+1及N(C2， C1)≥t+1 (3.10.4) 由于在计算机存贮系统(ROM和RAM)中， 所产生的错误大部分是单向错误和少量的随机错误并存， 因此下面主要讨论t-EC／AUED码的构造。
有关纠非对称错误分组码及纠单向错误码的构造及性质请参阅参考文献［14～16］ 第第3章章 线性分组码线性分组码 二、 t-EC／AUED码的构造 在一个码字中若仅产生单个错误， 则这个错误既可看成随机错误又可看成单向错误 因此， 对于纠单个错误码来说， 不必区分它是纠随机错误还是纠单向错误的码 所以汉明码既是纠单个随机错误的最佳码， 也是纠单个单向错误的最佳码 但是， 对于t-EC／AUED码来说， 由式(3.10.4)可知， 该码中一定没有全0和全1码字， 因此不可能是线性码， 而纠不对称与单向错误的码则可以是线性码 第第3章章 线性分组码线性分组码 构造t-EC／AUED码的方法通常有两种： 一是在已知的纠t个随机错误或不对称错误分组码的基础上， 加必要的校验元， 使码具有检测所有单向错误(AUED)的能力； 二是从已知的AUED码的基础上， 加上必要的校验元， 使码具有纠正t个随机错误的能力 第第3章章 线性分组码线性分组码 (1) 由已知的AUED码构造 最常用的一类AUED码是等重码。
一个长为n、 重量为w、 距离为d的(n， d， w)等重码， 就是n中取w码 我国电传通信用的(5， 2， 3)码， 就是5中取3码， 而(7， 2， 3)码就是7中取3码， 它们的距离均为2 (n， d， w)等重码是非线性码， 可以证明码字之间的汉明距离必是偶数［17］， 因而等重码一般用(n， 2δ， w)表示 对于(n， 2， w)码Cw来说， 由于码字之间的距离必是偶数， 因此对于任何C1， C2∈Cw， 必有 N(C1， C2)≥1 N(C2， C1)≥1 由式(3.10.4)知， 该码必能检测码字中的所有单向错误 第第3章章 线性分组码线性分组码 定理 3.10.3 纠t个错误的(n， 2δ， w)等重码中， 任何两个码字C1、 C2之间必满足： N(C1， C2)≥δ=t+1 N(C2， C1)≥δ=t+1 第第3章章 线性分组码线性分组码 请读者证明该定理 由此可知， 任何(n， 2δ， w)等重码， 一定是一个(δ-1)-EC／AUED码。
例如(8， 4， 4)等重码， 它的14个码字是： (10110001)， (01011001)， (00101101)， (00010111)， (10001011)， (11000101)， (01100011)， (01001110)， (10100110)， (11010010)， (11101000)， (01110100)， (00111010)， (10011100) 可以检验出每个码字之间的距离等于4， 且任两码字C1、 C2之间的N(C1， C2)≥2和N(C2， C1)≥2， 因而这是一个1-EC／AUED码 第第3章章 线性分组码线性分组码 定理3.10.4 由上述方法构造的等重码Ci， 它的各码字之间的距离至少为4， 且对任何C1， C2∈Ci， 有N(C1， C2)≥2， N(C2， C1)≥2 证明 设C1、 C2是Ci中的任二码字 若它们之间的距离不为4， 设为2， 则由于每个码字的重量均为w， 除了两个位置如r和s以外， C1、 C2之间的相应分量应相等， 如下所示： C1： x … x 0 x … x 1 x … x C2： x … x 1 x … x 0 x … x 0 … r … s … n-1 第第3章章 线性分组码线性分组码 由于T(C1)=T(C2)≡i(mod n)， 所以由式(3.10.5)可知： T(C1)=b+s≡i (mod n) T(C2)=b+r≡i (mod n) 式中， b∈Zn， 是除了r和s坐标以外的所有其余坐标之和(mod n)。
可知s≡r(mod n)， 但由于s、 r均小于n， 因而s≡r(mod n)， 所以C1、 C2之间的距离不能为 2， 至少为 4 第第3章章 线性分组码线性分组码 定理3.10.5 令C是［n， k， 2t+1］分组码， C1， C2∈C， 且w(C1)≥w(C2)， 则有： N(C1， C2)≥t+1 N(C2，C1)≥max{0，t+1-［(w(C1)-w(C2))／2］} (3.10.6) 第第3章章 线性分组码线性分组码 由该定理可知， 若w(C1)＞w(C2)， 则在C 2后面所加的校验元的重量至少应为t+1或［(w(C1)-w(C2))／2］， 以保证式(3.10.4)满足 根据不同的加校验码元的方法就得到了不同的码 其中最早和最重要的一种方法， 是伯杰(Berger)在构造纠非对称错误码时提出的构造方法(B方法)［20］。
第第3章章 线性分组码线性分组码 令C表示［n， k， 2t+1］系统分组码， C*表示 (n*， k) t-EC／AUED系统码 C*的码字有如下形式： x0 x1 x2 … xt+1 x0∈C (3.10.7) 也就是C*中每一码字， 是在C中码字x0后面加一些校验元x1， x2， …， xt+1 构成 这里， xi(i=1， 2， …， t+1)是用B方法产生： xi是x0， x1， …， xi-1中 0 数目的二进制表示序列 可知用这种方法构造的C*码是系统码 第第3章章 线性分组码线性分组码 表3 - 5 用B和THL方法得到的系统 1 -EC／AUED码 第第3章章 线性分组码线性分组码 定理 3.10.6［26］ 由［n， k， 2t+1］线性系统分组码构造的系统t-EC／AUED码， 其校验元 r≤(n-k)+(t+1)log2 n (3.10.9) 定理 3.10.7［27］ k长信息位的二进制系统 t-EC／AUED码的校验元 (1) r≥［log2 (k+1)］ 当t=0 (2) r≥［(t+1)log2 k-log2 ((t+1)!)］ 当1≤t≤4 (3) r≥［(t+1)log2 k-log2 ((t+1)!)］-1 当t≥s且k>>t 第第3章章 线性分组码线性分组码 上述这些码限以及码字数目的限， 请参阅文献［22， 27， 28］。
由于系统t-EC／AUED码在计算机纠、 检错系统中有较大作用， 因此有关这类码的研究方兴未艾［23， 24， 27］， 值得注意 特别是Rao等近来出版了一本计算机纠错码的专著， 详细讨论了上述这些码的构造原理、 方法和性能， 有兴趣读者可参阅［29］ 第第3章章 线性分组码线性分组码 习习 题题 1. 证明［n， k］线性分组码的最大距离为n-k+1 2. 设一个［7， 4］码的生成矩阵为 第第3章章 线性分组码线性分组码 (1) 求出该码的全部码矢； (2) 求出该码的一致校验矩阵； (3) 作出该码的标准阵译码表 第第3章章 线性分组码线性分组码 3. 证明定理3.1.3 4. 一个［8， 4］系统码， 它的一致校验方程为： c0=m1+m2+m3 c1=m0+m1+m2 c2=m0+m1+m3 c3=m0+m2+m3 式中， m0， m1， m2， m3是信息位， c0， c1， c2， c3是校验位。
找出该码的G和H， 并证明该码的最小距离为4 第第3章章 线性分组码线性分组码 5.构造第 4 题中码的对偶码 6.设H1是［n， k］线性分组码C1的校验矩阵， 且有奇数最小距离为d 作一个新的码C2， 它的校验矩阵为 第第3章章 线性分组码线性分组码 (1) 证明C2是一个(n+1， k)分组码； (2) 证明C2中每一码字的重量为偶数； (3) 证明C2码的最小重量为d+1 第第3章章 线性分组码线性分组码 7. 设C1是一个有最小距离为d1的［n1， k］线性系统码， 生成矩阵为G1=［P1Ik］ C2是一个有最小距离为d2的［n2， k］线性系统码， 它的生成矩阵 G2=［P2Ik］ 对满足下述一致校验矩阵的［n1+n2， k］线性码， 证明它有最小距离至少为d1+d2 第第3章章 线性分组码线性分组码 8. 设一个二进制［n， k］码C的G矩阵不含全零列， 将C的所有码字排成2k×n的阵 证明： (a) 阵中不含有全零列； (b) 阵中的每一列由2k-1个零和2k-1个1组成； (c) 在一特定分量上为0的所有码字构成C的一个子空间， 问该子空间的维数是多少？ 第第3章章 线性分组码线性分组码 9. 令Γ是所有二进制［n， k］线性系统码的集合。
证明非零二进制n重V或者恰巧含于Γ的2(k-1)(n-k)个码中， 或者不在Γ的任一码中 10. 证明二进制［23， 12， 7］Golay码和三进制的［11， 6， 5］Golay码是完备码 11. 若d是码C的最小重量， 且为偶数， t=［(d-1)／2］ 证明有两个重量均为t+1的矢量必在C码的同一陪集中 第第3章章 线性分组码线性分组码 12. 求出d=3， 至多只有3个校验元的二进制码的码长n； 和d=5， 至多只有8个校验元的二进制码的码长n 13. 计算二进制［24， 12， 8］扩张Golay码的覆盖半径， 及［8， 4］RM码的覆盖半径 14. 证明定理3.9.3 第第3章章 线性分组码线性分组码 15. 构造三个二进制的［10， 3， 5］LUEP码， 其分离矢量分别为(8， 2， 2)， (7， 4， 4)， (6， 4， 4) 写出它们标准形式的G和系统码形式的G 16. 证明定理3.10.3。
17. 构造一个具有最高码率的k=10， t=2的2-EC／AUED码 18. 证明定理3.10.6。
