信息论与编码第6章(2)

1、信道编码信道编码 1 6.3 线性分组码线性分组码 2 线性分组码线性分组码 3 G gk 1,gk 2 1 0 ,.g ,g T 线性分组码的码空间线性分组码的码空间C 是由是由 k 个线性无关个线性无关的的基底基底 gk-1, ，g1 ，g0 张成的张成的k维维n重重子空间子空间，所有码字都可写成，所有码字都可写成k个个 基底的线性组合，即基底的线性组合，即 c = mk-1 gk-1+ m1 g1+m0 g0 如果如果gi表示第表示第i个基底，并写成行矩阵的形式个基底，并写成行矩阵的形式 gi gi(n 1),gi(n 2),.gi1,gi0, k个基底可以排列成个基底可以排列成k行行n

2、列的形式，如下所示：列的形式，如下所示： . g(k 1)1 . . . g11 . g01 g(k 1)(n 1) . g1(n 1) g0(n 1) g(k 1)0 . g10 g00 6.3.1生成矩阵和校验矩阵生成矩阵和校验矩阵 4 码空间中任何一个码字都可以写成基底的线性组合，即：码空间中任何一个码字都可以写成基底的线性组合，即： C cn 1,cn 2,.,c1,c0 mk 1gk 1 mk 2gk 2 . m1g1 m0g0 mG 当信息元确定后，码字仅由当信息元确定后，码字仅由G矩阵决定，因此我们称这矩阵决定，因此我们称这 kn 矩阵矩阵G为该为该(n,k)线性分组码的线性分组

3、码的生成矩阵生成矩阵。 如果已知线性分组码的生成矩阵，则任何一个如果已知线性分组码的生成矩阵，则任何一个k位信息位信息 组对应的码字都可以由组对应的码字都可以由mG运算得到。运算得到。 生成矩阵生成矩阵 5 (n,k)线性分组码共有多少个码字线性分组码共有多少个码字? 问题问题 答：答：2k个码字。个码字。 6 想要保证想要保证 (n,k)线性分组码能够构成线性分组码能够构成k维维n重子空间，重子空间，G 的的 k 个行矢量个行矢量gk-1, g1, g0必须是必须是线性无关线性无关的，只有这的，只有这 样样才符合作为基底的条件。才符合作为基底的条件。 由于由于k个基底即个基底即G的的k个行矢

4、量线性无关，矩阵个行矢量线性无关，矩阵G的的秩一定秩一定 等于等于k。 由于由于基底不是唯一基底不是唯一的，所以的，所以G也就不是唯一的。也就不是唯一的。 不同的基底有可能生成同一码集，但因编码涉及码集和不同的基底有可能生成同一码集，但因编码涉及码集和 映射两个因素，码集一样而映射方法不同也不能说映射两个因素，码集一样而映射方法不同也不能说 是同是同 样的码。样的码。 生成矩阵生成矩阵G(kn)的特点的特点 7 已知已知(7,4)线性分组码的生成矩阵为线性分组码的生成矩阵为 如果输入的四位信息组为如果输入的四位信息组为m 0,1,1, 0时，其对应的时，其对应的码码字为字为： 举例举例 8 (

5、n,k)码的任何生成矩阵都可以通过码的任何生成矩阵都可以通过行运算行运算（不改变码集，（不改变码集， 只改变映射规则）简化成只改变映射规则）简化成“系统形式系统形式” 。 Ik是是kk单位矩阵，单位矩阵，P是是k(n-k)矩阵。矩阵。 系统形式的生成矩阵系统形式的生成矩阵 G = Ik P = 1 0 0 p(k 1)0 p10 p00 p(k 1)(n k 1) p1(n k 1) p0(n k 1) 0 0 1 0 0 0 1 p(k 1)1 p11 p01 9 前前k位由单位矩阵位由单位矩阵Ik决定，等于把信息组决定，等于把信息组m原封不原封不 动搬到码字的前动搬到码字的前k位；位； 其

6、余的其余的n-k位叫冗余位或位叫冗余位或一致校验位一致校验位，是前，是前k个信个信 息位的线性组合。息位的线性组合。 这样生成的（这样生成的（n,k）码叫做）码叫做系统码系统码。 若生成矩阵若生成矩阵G不具备系统形式，则生成的码叫做不具备系统形式，则生成的码叫做 非系统码非系统码。 系统化系统化不改变码集不改变码集，只是改变了，只是改变了映射规则映射规则。 系统系统码码 10 已知已知(7,3)线性分组码的生成矩阵为线性分组码的生成矩阵为 如果输入的三位信息组为如果输入的三位信息组为m 0,1,1时，其对应的时，其对应的码码字为：字为： 特点：特点： 码字的前面码字的前面k位就是信息组中的位就

7、是信息组中的k位，而后面的校验位，而后面的校验 位为位为信息组的线性组合信息组的线性组合。 系统系统码码 11 n维维n重空间有相互正重空间有相互正 交的交的n个基底个基底 选择选择k个基底构成码个基底构成码 空间空间C 选择另外的选择另外的(n-k)个基个基 底构成空间底构成空间D C和和D是对偶的是对偶的 n维维n重空间重空间V k维维k重重 信息组信息组 空间空间m k维维n重重 n-k维维 码空间码空间 n重重D C H G 空间构成空间构成 12 将将D空间的空间的n-k个基底排列起来可构成一个个基底排列起来可构成一个(n-k)n矩矩 阵，称为阵，称为校验矩阵校验矩阵H，也称，也称监

8、督矩阵监督矩阵。用来校验接收。用来校验接收 到的码字是否是正确的；到的码字是否是正确的； 即：若即：若c为码空间为码空间C中的任意码字，则中的任意码字，则 若不满足此等式，则若不满足此等式，则c必定不是码空间必定不是码空间C中的码字。中的码字。 校验矩阵校验矩阵 13 G是是(n,k)码的码的生成矩阵生成矩阵，H是它的是它的校验矩阵校验矩阵； H是是(n,n-k)对偶码的对偶码的生成矩阵生成矩阵，它的每一行是，它的每一行是 对偶码的一个码字。对偶码的一个码字。 G则是它的则是它的校验矩阵校验矩阵。 GHT=0 ，H PT In-k ，二进制时，负号可，二进制时，负号可 省略。省略。 校验矩阵校

9、验矩阵 14 校验矩阵与生成矩阵的关系校验矩阵与生成矩阵的关系 15 某线性分组码，其生成矩阵是某线性分组码，其生成矩阵是 求：求： (1)计算码集，列出信息组与码字的映射关系。计算码集，列出信息组与码字的映射关系。 (2)将该码系统化处理后，计算系统码码集并列出映射将该码系统化处理后，计算系统码码集并列出映射 关系。关系。 (3)计算系统码的校验矩阵计算系统码的校验矩阵H。若收码。若收码r = 100110, 检检 验它是否码字？验它是否码字？ (4)根据系统码生成矩阵画出编码器电原理图。根据系统码生成矩阵画出编码器电原理图。 1 1 1 0 1 0 G= 1 1 0 0 0 1 0 1 1

10、 1 0 1 例例6-26-2 16 码集与映射关系码集与映射关系 信息信息 000 001 010 011 100 101 110 111 码字码字 000000 011101 110001 101100 111010 100111 001011 010110 系统码字系统码字 000000 001011 010110 011101 100111 101100 110001 111010 例例6-26-2 17 二元二元(6,3)线性分组码编码器线性分组码编码器 输入输入输出输出 m0 m1 m2 c0 c1 c2 例例6-26-2 18 下面是某线性二元码的全部码字：下面是某线性二元码的全

11、部码字： 求求n, k的值；的值； 构造这码的生成矩阵构造这码的生成矩阵G； 构成这码的一致校验矩阵构成这码的一致校验矩阵H。 C1 000000 C2 001111C3 010001C4 011110 C5 100011C6 101100C7 1110010 C8 111101 举例举例 19 mC=(cn-1,c1,c0)R=(rn-1,r1,r0) (n,k)信道信道 定义定义差错图案差错图案E E(en1,e1,e0) RC (rn-1cn-1,r1c1,r0c0) 二进制码中模二进制码中模2加与模加与模2减是等同的，因此有减是等同的，因此有 E=R C 及及R=C E 6.3.2伴随

12、式与标准阵列译码伴随式与标准阵列译码 20 因为因为CHT = 0 所以所以RHT (CE)HT CHT EHT= EHT 如果如果收码无误收码无误：必有：必有RC即即E0， 则则EHT= 0 RHT = 0。 如果如果收码有误收码有误：即：即E 0， 则则RHT= EHT 0。 在在HT固定的前提下，固定的前提下，RHT仅仅与差错图案仅仅与差错图案E有关，有关， 而与发送码而与发送码C无关。定义无关。定义 RHT的运算结果为的运算结果为伴随式伴随式S S = (sn-k-1,s1,s0) = RHT = EHT 伴随式伴随式的定义的定义 21 ?RHT = S R S C = RE E C

13、只要只要E正确，译出的码也就是正确的。正确，译出的码也就是正确的。 从物理意义上看，伴随式从物理意义上看，伴随式S并不反映发送的码字是什并不反映发送的码字是什 么，而只是么，而只是反映信道对码字造成怎样的干扰反映信道对码字造成怎样的干扰。 差错图案差错图案E是是n重矢量重矢量，共有，共有2n个可能的组合，而伴随个可能的组合，而伴随 式式S是是(n-k)重矢量重矢量，只有，只有 2n-k 个可能的组合，因此不同个可能的组合，因此不同 的差错图案可能有相同的伴随式。的差错图案可能有相同的伴随式。 接收端收到接收端收到R后，因为已知后，因为已知HT，可求出，可求出 SRHT ；如；如 果能知道对应的

14、果能知道对应的E，则通过，则通过C = RE而求得而求得C。 伴随式伴随式的意义的意义 22 译码过程框图译码过程框图 译码过程译码过程 23 差错图案差错图案E E的求解的求解(1)(1) 24 上述方程组中有上述方程组中有n个未知数个未知数en1, e1,e0 ，却只有，却只有n-k 个方程，可知方程组有多解。个方程，可知方程组有多解。 在有理数或实数域中，少一个方程就可能导致无限多在有理数或实数域中，少一个方程就可能导致无限多 个解，而在二元域中，少一个方程导致两个解，少两个解，而在二元域中，少一个方程导致两个解，少两 个方程四个解，以此类推，少个方程四个解，以此类推，少n-( n-k)

15、 = k个方程导致个方程导致 每个未知数有每个未知数有2k个解。个解。 概率译码：概率译码：把所有把所有 2k 个解的重量个解的重量(差错图案差错图案E中中1的个的个 数数)作比较，选择其中最轻者作为作比较，选择其中最轻者作为E的估值。该方法概的估值。该方法概 念上很简单但计算效率不高。念上很简单但计算效率不高。 差错图案差错图案E E的求解的求解(2)(2) 25 依据：依据：若若BSC信道的差错概率是信道的差错概率是 p，则长度，则长度n的码中错误概率的码中错误概率 0个错个错1个错个错2个错个错n个错个错 概率概率 (1-p)np(1-p)n-1p2(1-p)n-2pn 由于由于p p(

16、1-p)n-1 p2(1-p)n-2 pn 出错越少的情况，发生概率越大，出错越少的情况，发生概率越大，E的重量越轻，所以该的重量越轻，所以该 译码方法实际上体现了译码方法实际上体现了最小距离译码准则最小距离译码准则，即最大似然译码。，即最大似然译码。 显然，在进行概率译码时，每接收一个码字就要解一次线显然，在进行概率译码时，每接收一个码字就要解一次线 性方程，非常复杂麻烦。但如果性方程，非常复杂麻烦。但如果nk不太大，我们可以预先不太大，我们可以预先 把不同校正子把不同校正子S情况下的所有方程组都预先解出来，将各种情情况下的所有方程组都预先解出来，将各种情 况下的最大概率译码输出列成一个况下

17、的最大概率译码输出列成一个标准阵列译码表标准阵列译码表。这样，在。这样，在 实际译码时就不必解方程，只要查译码表就可以了。实际译码时就不必解方程，只要查译码表就可以了。 差错图案差错图案E E的求解的求解依据依据 26 伴随式伴随式S的数目是有限的的数目是有限的2n-k个，如果个，如果n-k不太大不太大，我们可，我们可 以预先把不同以预先把不同S下的方程组解出来，把各种情况下的最大概下的方程组解出来，把各种情况下的最大概 率译码输出率译码输出列成一个码表列成一个码表。这样，在实时译码时就不必再。这样，在实时译码时就不必再 去解方程，而只要象查字典那样查一下码表就可以了。这去解方程，而只要象查字

18、典那样查一下码表就可以了。这 样构造的表格叫做样构造的表格叫做标准阵列译码表标准阵列译码表。 表中所列码字是接收到的码字表中所列码字是接收到的码字R； 将将没有任何差错没有任何差错时的收码时的收码R放在第一行，放在第一行，收码等于发码收码等于发码 R=C(C Ci,i =0,1,2k-1), 差错图案为全零差错图案为全零E0=(0,00)，伴随，伴随 式为全零式为全零S0=(0,00)。由于有。由于有2k个码字，码表有个码字，码表有 2k 列列。 标准阵列译码表标准阵列译码表的构成的构成 27 在在第第2到第到第n+1的的n行中差错图案的所有行中差错图案的所有重量为重量为1 (共共n个个)。

19、如果如果(1+ n)2n-k，再在下面行写出全部带有，再在下面行写出全部带有2个差错的图个差错的图 案案 (共共 n 个个)。 2 如果如果总行数总行数(1+n+ 差错的图案，以此类推，直到放满差错的图案，以此类推，直到放满2n-k行，每行一个行，每行一个Ej, 对应一个不同的伴随式对应一个不同的伴随式Sj。这样，表的。这样，表的行数行数2n-k正好等正好等 于伴随式的数目于伴随式的数目。 n 2 2 )仍然仍然小于小于2n-k，再列出带有，再列出带有3个个 标准阵列译码表标准阵列译码表的构成的构成 28 标准阵列译码表标准阵列译码表 29 解：解：(1)构造标准阵列译码表。分别以信息组构造标

20、准阵列译码表。分别以信息组m= (00)、 (01) 、(10)、(11)及已知的及已知的G求得求得4个许用码字为个许用码字为C1 =(00000)、C2 = (10111) 、C3 = (01101)、C4 = (11010)。 一个一个(5,2)系统线性码的生成矩阵是系统线性码的生成矩阵是 设收码设收码R = (10101)，构造，构造标准阵列译码表标准阵列译码表，译出发码，译出发码 i 的估值的估值 c 求出校验矩阵：求出校验矩阵： 例例6-36-3 30 列出方程组：列出方程组： s2 e4h24 e3h23 e2h22 e1h21 e0h20 e4 e3 e2 s1 e4h14 e3

21、h13 e2h12 e1h11 e0h10 e4 e1 s0 e4h04 e3h03 e2h02 e1h01 e0h00 e4 e3 e0 由由RHT确定确定S后，对应的后，对应的E可以有可以有2k(22=4)个解，究竟取哪一个解，究竟取哪一 个作为差错图样个作为差错图样E的解的解? 最简单明了的处理方法是最简单明了的处理方法是概率译码概率译码，即，即 对所有对所有2k个解的重量个解的重量(差错图样差错图样E中中1的个数的个数)进行比较，选择重量进行比较，选择重量 最小的作为最小的作为E的估值。由于的估值。由于E=R+C，E重量最小重量最小，就是，就是R和和C的汉的汉 明距离最小。明距离最小。

22、 例例6-36-3 31 例例6-36-3 32 S0=000E0+C0=00000C1=10111C2=01101C3=11010 S1=111E1=10000001111110101010 S2=101E2=01000111110010110010 S3=100E3=00100100110100111110 S4=010E4=00010101010111111000 S5=001E5=00001101100110011011 S6=011E6=00011101000111011001 S7=110E7=00110100010101111100 例例6-36-3 标准阵列译码表标准阵列译码表

23、 33 将接收码将接收码R10101译码译码 可选以下三种方法之一译码：可选以下三种方法之一译码： 直接搜索码表直接搜索码表，查得，查得(10101)所在列的子集头是所在列的子集头是 (10111)，因此译码输出取为，因此译码输出取为(10111)。 先求先求伴随式伴随式RHT = (10101) HT = (010) = S4，确定，确定S4所所 在行，再沿着行对码表作一维搜索找到在行，再沿着行对码表作一维搜索找到(10101), 最后最后 顺着所在列向上找出码字顺着所在列向上找出码字(10111)。 先求出伴随式先求出伴随式RHT = (010) = S4并确定并确定S4所对应的所对应的陪

24、集陪集 首首（差错图案差错图案）E4=(00010)，再将，再将陪集首与收码陪集首与收码相加相加 得到码字得到码字C= R+ E4= (10101)+ (00010)= (10111)。 例例6-36-3 34 对例对例 6-3的分析的分析 在制定标准阵列译码表的过程中，由在制定标准阵列译码表的过程中，由S决定差错图案决定差错图案E 时只有前时只有前6行真正体现了最大似然译码准则，而第行真正体现了最大似然译码准则，而第7、8行行 的差错图案选择不是唯一的。比如第的差错图案选择不是唯一的。比如第7行可有行可有(00011)和和 (10100)两个选择，如果当时选的不是两个选择，如果当时选的不是(

25、00011)而是而是(10100)， 那么码表第那么码表第7行就不是现在这样了。那么在译码时最后的行就不是现在这样了。那么在译码时最后的 结果也就不一样了。结果也就不一样了。 为什么会出现这种情况呢？为什么会出现这种情况呢？ 伴随式的个数伴随式的个数2n-k与与n、k及纠错能力及纠错能力t 有一定的数量关系。有一定的数量关系。 例例6-36-3 35 N重码矢重码矢c = (cn-1,c n-2,c1,c0)可与可与N维矢量空间维矢量空间 XN中的中的一个点对应一个点对应，全体码字所对应的点构成，全体码字所对应的点构成 矢量空间里的一个子集矢量空间里的一个子集 发码一定在这个子集里，传输发码一

26、定在这个子集里，传输无误时无误时的收码也的收码也 一定位于该子集一定位于该子集 当出现差错时，接收的当出现差错时，接收的N重矢量重矢量: 对应到子集对应到子集外空间某一点外空间某一点 对应到该子集，却对应到该子集的对应到该子集，却对应到该子集的另一点上另一点上 6.3.3码距码距、纠错能力、纠错能力、MDC码及重量谱码及重量谱 36 dmin=3 t d=7 d=5 C1 C2 C3 C4 C5 码集各码字间的距离是码集各码字间的距离是 不同的，码距最小者不同的，码距最小者决决 定码的特性定码的特性，称之为，称之为最最 小距离小距离dmin 这里这里dmin=3，纠错能力，纠错能力 是是1，检

27、错能力是，检错能力是2 码距码距 37 dmin = min w (C i)C i C 及及C i 0 定理定理6.1 任何最小距离任何最小距离dmin的线性分组码，其的线性分组码，其检错能力检错能力为为 （dmin-1）, 纠错能力纠错能力t为为 最小距离最小距离dmin表明码集中各码字差异的程度，差异越大越表明码集中各码字差异的程度，差异越大越 容易区分，抗干扰能力就越强，是衡量分组码性能的最容易区分，抗干扰能力就越强，是衡量分组码性能的最 重要的指标之一。重要的指标之一。 定理定理6.2 线性分组码的线性分组码的最小距离最小距离等于码集中等于码集中非零码字非零码字的的最最 小重量小重量

28、纠错能力纠错能力 38 于于 (n-k+1), 即即 dmin (n-k+1) 定理定理6.3 (n,k) 线性分组码最小距离等于线性分组码最小距离等于dmin的的充充 要条件要条件是：校验矩阵是：校验矩阵H中有中有（dmin-1)列线性无关。列线性无关。 定理定理6.4 (n,k) 线性分组码的最小距离必定线性分组码的最小距离必定小于等小于等 纠错能力纠错能力 39 例：例： H(7，4)线性码线性码 各列都不相同，任意各列都不相同，任意2列之和不等于列之和不等于0，2列列 线性无关线性无关；任意；任意2列之和一定等于矩阵中某一列之和一定等于矩阵中某一 列，列，任意任意3列线性相关列线性相关

29、。所以该码的。所以该码的最小距离最小距离 为为3，小于，小于n-k +14。 纠错能力纠错能力 40 d0 2t 1 (1)为为检测检测e个错码，要求最小码距个错码，要求最小码距 d0 e 1 (2)为为纠正纠正t个错码，要求最小码距个错码，要求最小码距 (3)为为纠正纠正t个错码，同时个错码，同时检测检测e 个错码，要求最小码距个错码，要求最小码距 d0 t e 1 最小码距与检错能力图示最小码距与检错能力图示 41 （n,k）线性码最小距离）线性码最小距离dmin的上边界是的上边界是n-k 我们设计的（我们设计的（n,k）线性码的）线性码的dmin达到了达到了n-k 达到了设计性能的极点。

30、因此，达到了设计性能的极点。因此，dmin n-k 为为极大最小距离码极大最小距离码 (MDC Maximized +1。如果。如果 +1，就是，就是 +1的码称的码称 minimum Distance Code)。 (1) 二进制码中，除了将一位信息重复二进制码中，除了将一位信息重复n 次的次的 （n,1） 码外，不存在其它二进制码外，不存在其它二进制MDC码；码； (2) 非二进制码中，非二进制码中，MDC码是存在的，如码是存在的，如RS码码 （reed-solomon)。 MDC码码(Maximized minimum Distance Code) 42 含义：在码长含义：在码长n的码集

31、里，包含重量为的码集里，包含重量为0的码字的码字A0个，个， 重量为重量为1的码字的码字A1个，个，-，重量为，重量为n的码字的码字An个。个。 纠错能力纠错能力t只是说明距离只是说明距离t的差错一定能纠，的差错一定能纠，并非说并非说距距 离大于离大于t的差错一定不能纠。（除非完备码）的差错一定不能纠。（除非完备码） 总体的、平均的纠错能力不但与总体的、平均的纠错能力不但与最小距离最小距离有关，而且有关，而且 与与其余码距其余码距或者说与码字的或者说与码字的重量分布特性重量分布特性有关。把码有关。把码 距（码重）的分布特性称为距（码重）的分布特性称为距离（重量）谱距离（重量）谱，其中最，其中最 小重量就是小重量就是dmin。当所有码距相差不大时（重量谱为。当所有码距相差不大时（重量谱为 窄谱），性能较好。重量谱多项式表示：窄谱），性能较好。重量谱多项式表示： 重量谱重量谱 43 任何一个二元任何一个二元(n,k)线性分组码都有线性分组码都有2n-k个伴随式，假如个伴随式，假如 该码的纠错能力是该码的纠错能力是t