第五讲 线性分组码 5.1 一般概念 5.2 一致监督方程和一致监督矩阵 5.3 线性分组码的生成矩阵 5.4 线性分组码的编码

Presentation on theme: "第五讲 线性分组码 5.1 一般概念 5.2 一致监督方程和一致监督矩阵 5.3 线性分组码的生成矩阵 5.4 线性分组码的编码"— Presentation transcript:

1 第五讲 线性分组码 5.1 一般概念 5.2 一致监督方程和一致监督矩阵 5.3 线性分组码的生成矩阵 5.4 线性分组码的编码
第五讲 线性分组码 一般概念 一致监督方程和一致监督矩阵 线性分组码的生成矩阵 线性分组码的编码 线性分组码的最小距离、检错和纠错能力 线性分组码的译码 5.7* 线性分组码的性能 汉明码 5.9* 由已知码构造新码的方法 5.10* 线性分组码的码限 2019/4/24

2 5.6 线性分组码的译码 ① 最佳译码准则（最大似然译码） (2) 纠错译码 通信是一个统计过程，纠、检错能力最终要反映到差错概率上。
对于FEC方式，采用纠错码后的码字差错概率为pwe， p(C)：发送码字C 的先验概率 p(C/R)：后验概率 若码字数为 2k，对充分随机的消息源有p(C)=1/ 2k，所以最小化的pwe等价为最小化p(C’≠C│R )，又等价为最大化p(C’=C│R)； 2019/4/24

3 5.6 线性分组码的译码 对于 BSC 信道：最大化的 p(C’=C│R) 等价于最大化的 p(R│C) ，最大化的p(R│C) 又等价于最小化 d(R,C)，所以使差错概率最小的译码是使接收向量 R 与输出码字 C’ 距离最小的译码。 2019/4/24

4 5.6 线性分组码的译码 码矢参数 译码方法 标准阵列：是对给定的 (n,k) 线性码，将 2n 个 n 重划分为 2k 个子集的一种方法。
② 标准阵列 码矢参数 发送码矢：取自于 2k 个码字集合{C}； 接收矢量：可以是 2n 个 n 重中任一个矢量。 译码方法 把 2n 个 n 重矢量划分为 2k 个互不相交的子集 ，使得在每个子集中仅含一个码矢； 根据码矢和子集间一一对应关系，若接收矢量 Rl 落在子集 Dl中，就把 Rl 译为子集 Dl 含有的码字 Cl； 当接收矢量 R 与实际发送码矢在同一子集中时，译码就是正确的。 标准阵列：是对给定的 (n,k) 线性码，将 2n 个 n 重划分为 2k 个子集的一种方法。 2019/4/24

5 5.6 线性分组码的译码 标准阵列构造方法 先将 2k 个码矢排成一行，作为标准阵列的第一行，并将全0码矢C1=(00…0)放在最左面的位置上； 然后在剩下的 (2n－2k) 个 n 重中选取一个重量最轻的 n 重 E2 放在全0码矢 C1 下面，再将 E2 分别和码矢 相加，放在对应码矢下面构成阵列第二行； 在第二次剩下的 n 重中，选取重量最轻的 n 重 E3，放在 E2 下面，并将 E3 分别加到第一行各码矢上，得到第三行； …，继续这样做下去，直到全部 n 重用完为止。得到表5.2所示的给定 (n,k) 线性码的标准阵列。 2019/4/24

6 5.6 线性分组码的译码 2019/4/24

7 5.6 线性分组码的译码 标准阵列的特性 [证明]：
定理5.5：在标准阵列的同一行中没有相同的矢量，而且 2n 个 n 重中任一个 n 重在阵列中出现一次且仅出现一次。 [证明]： 因为阵列中任一行都是由所选出某一 n 重矢量分别与 2k 个码矢相加构成的，而 2k 个码矢互不相同，它们与所选矢量的和也不可能相同，所以在同一行中没有相同的矢量； 在构造标准阵列时，是用完全部 n 重为止，因而每个 n 重必出现一次； 每个n重只能出现一次。 假定某一 n 重 X 出现在第 l 行第 i 列，那么 X＝El+Ci， 又假设 X 出现在第 m 行第 j 列，那么 X＝Em+Cj，l<m， 2019/4/24

8 5.6 线性分组码的译码 这意味着 Em 是第 l行中的一个矢量，但Em是第m行(m>l)的第 一个元素，
因此El+Ci = Em+Cj ，移项得Em = El+Ci+Cj 而Ci+Cj也是一个码矢，设为Cs ，于是Em = El+Cs， 这意味着 Em 是第 l行中的一个矢量，但Em是第m行(m>l)的第 一个元素， 而按阵列构造规则，后面行的第一个元素是前面行中未曾出 现过的元素，这就和阵列构造规则相矛盾。 2019/4/24

9 5.6 线性分组码的译码 定理5.6 (线性码纠错极限定理)：二元 (n,k) 线性码能纠 2n－k 个错误图样。这 2n－k 个可纠的错误图样，包括0矢量在内，即把无错的情况也看成一个可纠的错误图样。 [证明]： (n,k) 线性码的标准阵列有 2k 列（和码矢矢量相等），2n/2k= 2n－k行，且任何两列和两行都没有相同的元素。 陪集：标准阵列的每一行叫做码的一个陪集。 陪集首：每个陪集的第一个元素叫做陪集首。 每一列包含 2n－k 个元素，最上面的是一个码矢，其它元素是陪集首和该码矢之和，例如第 j 列为 2019/4/24

10 5.6 线性分组码的译码 若发送码矢为 Cj，信道干扰的错误图样是陪集首，则接收矢量 R 必在 Dj 中；
当且仅当错误图样为陪集首时，译码才是正确的。 可纠正的错误图样：这 2n－k 个陪集首称为可纠正的错误图样。 2019/4/24

11 5.6 线性分组码的译码 上式中等式成立时的线性码称为完备码。即 [证明]：
线性码纠错能力与监督元数目的关系：一个可纠 t 个错误的线性码必须满足 上式中等式成立时的线性码称为完备码。即 [证明]： 纠一个错误的 (n,k) 线性码，必须能纠正 个错误图样，因此 2019/4/24

12 5.6 线性分组码的译码 对纠两个错误的 (n,k) 线性码，必须能纠 个错误图样，所以
依此类推，一个纠 t 个错误的 (n,k) 线性码必须满足 对于完备码，由码的纠错能力所确定的伴随式数恰好等于可纠的错误图样数，所以完备码的 (n－k) 个监督码元得到了充分的利用。 2019/4/24

13 5.6 线性分组码的译码 定义：(n,k) 线性码的所有 2n－k 个伴随式，在译码过程中若都用来纠正所有小于等于 个随机错误，以及部分大于 t 的错误图样，则这种译码方法称为完备译码。 限定距离译码：任一个 (n,k) 线性码，能纠正 个随机错误，如果在译码时仅纠正 t’ <t 个错误，而当错误个数大于t’时，译码器不进行纠错而仅指出发生了错误，称这种方法为限定距离译码。 2019/4/24

14 5.6 线性分组码的译码 从多维矢量空间的角度看完备码：
假定围绕每一个码字 Ci 放置一个半径为 t 的球，每个球内包含了与该码字汉明距离小于等于 t 的所有接收码字 R 的集合； 这样，在半径为 t=[(dmin－1)/2] 的球内的接收码字数是 因为有 2k 个可能发送的码字，也就有2k 个不相重叠的半径为t的球。包含在2k个球中的码字总数不会超过2n个可能的接收码字。 于是一个纠 t 个差错的码必然满足不等式 如果上式中等号成立，表示所有的接收码字都落在 2k 个球内，而球外没有一个码，这就是完备码。 2019/4/24

15 5.6 线性分组码的译码 完备码特性：围绕 2k 个码字，汉明距离为t=[(dmin－1)/2]的所有球都是不相交的，每一个接收码字都落在这些球中之一，因此接收码与发送码的距离至多为 t，这时所有重量≤t的错误图样都能用最佳（最小距离）译码器得到纠正，而所有重量≥t+1的错误图样都不能纠正。 2019/4/24

16 5.6 线性分组码的译码 所有汉明码都是完备码（满足2n－k = 2m=n+1）。 标准阵列译码=最小距离译码法=最佳译码法
举例：对纠一个错误的 (7,4) 汉明码， 可见，(7,4)汉明码是一个完备码。 所有汉明码都是完备码（满足2n－k = 2m=n+1）。 标准阵列译码=最小距离译码法=最佳译码法 陪集首是可纠正的错误图样，为了使译码错误概率最小，应选取出现概率最大的错误图样作陪集首； 重量较轻的错误图样出现概率较大，所以在构造标准阵列时是选取重量最轻的 n 重作陪集首； 这样，当错误图样为陪集首时（可纠的错误图样），接收矢量与原发送码矢间的距离（等于陪集首）最小； 2019/4/24

17 5.6 线性分组码的译码 定理5.7：在标准阵列中，一个陪集的所有 2k 个 n 重有相同的伴随式，不同的陪集伴随式互不相同。 [证明]：
因此，选择重量最轻的元素作陪集首，按标准阵列译码就是按最小距离译码； 所以标准阵列译码法也是最佳译码法。 定理5.7：在标准阵列中，一个陪集的所有 2k 个 n 重有相同的伴随式，不同的陪集伴随式互不相同。 [证明]： 设 H 为给定 (n,k) 线性码的监督矩阵，在陪集首为 El 的陪集中的任意矢量 R 为 R=El+Ci, i=1,2,…,2k 其伴随式为 S=RHT=(El+Ci)HT=ElHT+CiHT =ElHT 上式表明：陪集中任意矢量的伴随式等于陪集首的伴随式。即同一陪集中所有伴随式相同。 不同陪集中，由于陪集首不同所以伴随式不同。 2019/4/24

18 5.6 线性分组码的译码 ③ 结论 任意 n 重的伴随式决定于它在标准阵列中所在陪集的陪集首。
标准阵列的陪集首和伴随式是一一对应的，因而码的可纠错误图样和伴随式是一一对应的，应用此对应关系可以构成比标准阵列简单得多的译码表，从而得到 (n,k) 线性码的一般译码步骤。 (n,k) 线性码的一般译码步骤 计算接收矢量 R 的伴随式 ST=HRT ； 根据伴随式和错误图样一一对应的关系，利用伴随式译码表，由伴随式译出 R 的错误图样 E； 将接收字减错误图样，得发送码矢的估值 C’=R－E 。 2019/4/24

19 5.6 线性分组码的译码 上述译码法称为伴随式译码法或查表译码法。 线性分组码一般译码器
译码器如图5.9。这种查表译码法具有最小的译码延迟和最小的译码错误概率，原则上可用于任何 (n,k) 线性码。 2019/4/24

20 5.7* 线性分组码的性能 在通信中检纠错码的实际性能是在统计上体现出来的。以下分析均以BSC信道为模型。 (1)不可检错误概率
(2)译码错误概率 (3)译码失败概率 (4)比特误码率 2019/4/24

21 5.7* 线性分组码的性能 (1)不可检错误概率 pud 由 (n,k) 线性码的重量分布求 pud
令Ai为码的重量分布，表示重量为i的码字个数，i=0,1,2,…,n； 由于仅当错误图样与码矢集合中的非0码矢相同时，才不能检出错误，所以 举例： (7,3) 码的重量分布是 A0=1,A1=A2=A3=0,A4=7，其不可检错误概率为 pud＝7×p4(1－p)3，若p=0.01，则 pud≈6.8×10－8。 利用 (n,k) 码重量分布与其对偶码的重量分布关系求 pud 设A0,A1,A2, …,An 是 (n,k) 码的重量分布； B0,B1,B2, …,Bn 是它的对偶码的重量分布； 2019/4/24

22 5.7* 线性分组码的性能 对偶码的重量枚举式：下面的多项式称为 (n,k) 码和它的对偶码的重量枚举式。
MacWilliams恒等式：若已知线性码的对偶码的重量分布，就可确定该码本身的重量分布。 由式(5.23)得 2019/4/24

23 5.7* 线性分组码的性能 令 将这个恒等式代入式 (6.2.26) 得 将恒等式和 (6.2.25) 代入上式得. 2019/4/24

24 5.7* 线性分组码的性能 pud =2－3[1+7×(1－2p)4]－(1－p)7
当k <(n－k) 时，用式(6.2.28)计算 pud 比较简单； 当k >(n－k) 时，用式(6.2.29)计算 pud 则更容易。 举例：已知 (7,4) 码的监督矩阵 H(7,4)，它等于其对偶码的生成矩阵 G(7,3)，即 由此生成矩阵的行的线性组合，可得到(7,3)码的8个码字 由此得到 (7,3) 对偶码的重量枚举式为 B(x)=1+7x4 利用式 (5.29) 得出 (7,4) 码的未检出错误概率为 pud =2－3[1+7×(1－2p)4]－(1－p)7 设 p=0.01，则 pud =6×10－6 。 2019/4/24

25 5.7* 线性分组码的性能 (2) 译码错误概率pwe 正确译码概率pwc：纠正小于等于t个差错的概率 译码错误概率 pwe
译码错误发生在差错数目大于 t，接收向量 R 与另一码字 C’ 的距离小于等于 t 的情况； Di 是重量 i 并译为错误码字的可能的接收向量 R 的数目，即 译码错误概率pwe为 2019/4/24

26 5.7* 线性分组码的性能 (3)译码失败概率pwf
由于仍存在不满足式 (6.2.30) 的接收码矢 R，对于限定距离译码器来说就处于译码失败状态，即 pwf=1－pwc 图6.2.30中 RA—正确译码概率 RB—译码错误概率 RC—译码失败概率 2019/4/24

27 5.7* 线性分组码的性能 (4) 比特误码率 pbc：信道的比特差错概率，对于BSC信道，pbc等于信道转移概率p。
pbd：译码错误导致的码字之间的比特差错率。 pbm：消息源与消息接收终端之间的比特差错概率。 一般认为消息和码字之间的映射不改变码字差错导致在整个码长内比特差错的均匀分布特性，在统计意义上有 pbm ≈ pbd 2019/4/24

28 5.7* 线性分组码的性能 pbe 译码错误的误码率：设码字是等概率发送，则 Pbc 与 pwe的关系
是发送全0码字并错为 j 重码字的概率； Pbc 与 pwe的关系 字错必然有至少 2t+1位码字比特错； 每个码字平均有 位消息比特错，所以pbc与pwe有如下渐进关系 2019/4/24

29 5.7* 线性分组码的性能 pbf 译码失败造成的误码率 pbd译码后总的误码率： pbd = pbe+pbf 2019/4/24

30 5.8 汉明码 汉明码是汉明于1950年提出的纠一个错误的线性码，也是第一个纠错码。由于它编码简单，因而是在通信系统和数据存储系统中得到广泛应用的一类线性码。 汉明码的结构参数： 纠一个错误的线性码，其最小距离 dmin=3 ；监督矩阵任意两列线性无关/ H 的任两列互不相同；没有全0的列。 监督元个数 n－k=r；H 阵中每列有 r 个元素，至多可构成 2r－1种互不相同的非0列。 对于任意正整数 m≥3，汉明码的结构参数为 码长： n=2m－1 信息位数： k=2m－m－1 监督位数： n－k=m 码的最小距离：dmin=3(t=1) 2019/4/24

31 5.8 汉明码 汉明码监督矩阵构成的两种方式 由于汉明码可纠的错误图样数为
构成 H 阵的标准形式，H=[Q Im]，其中 Im 为 m 阶单位子阵，子阵 Q 是构造 Im 后剩下的列任意排列。用这种形式的 H 阵编出的汉明码是系统码。 按m重表示的二进制顺序排列。按这种形式 H 阵编出的码是非系统码。当发生可纠的单个错误时，伴随式为 H 阵中对应的列，所以伴随式的二进制数值就是错误位置号，有时这种码译码比较方便。 由于汉明码可纠的错误图样数为 2019/4/24

32 5.9* 由已知码构造新码的方法 (1) 扩展/Extending和打孔/Puncturing
(2) 增广/Augmenting和删信/Expunging/Expurgating (3) 延长/Lengthening和缩短/Sportening (4) 乘积/Product (5) 级联/Concatenating (6) 交织/Interleaving 2019/4/24

33 5.9* 由已知码构造新码的方法 (1) 扩展/Extending和打孔/Puncturing
扩展：保持码字数 k 不变，增加冗余位数以增加码长。 打孔：保持 k 不变，减小冗余位。可以认为是扩展的逆过程。 (2) 增广/Augmenting和删信/Expunging/Expurgating 增广：保持 n 不变，增加码字数目 k。 删信：保持 n 不变减小 k。 (3) 延长/Lengthening和缩短/Sportening 延长：同时增加 k 和 n。 缩短：同时减小 k 和 n。 2019/4/24

34 5.9* 由已知码构造新码的方法 举例： (7,4,3) 汉明码的各种修正关系如图5.31所示。 2019/4/24

35 5.9* 由已知码构造新码的方法 (4) 乘积/Product (5) 级联/Concatenating
消息作为阵列，分别进行行列编码。 (5) 级联/Concatenating 对消息编码后的码字再进行一次编码。 级联编码的第一次所用码称外码；第二次所用码称内码。 级联编码常用于既有随机差错又有突发差错的信道编码。 (6) 交织/Interleaving 交织编码分为分组交织和卷积交织两种。 如果交织编码所用的 (n,k) 码可以纠正 t 个随机差错，那么交织深度为 D 的交织编码可以纠正 Dt 长的突发错误。 2019/4/24

36 5.9* 由已知码构造新码的方法 举例：视盘存储的纠错编码采用对(31,21)纠双错的BCH码进行256深度的交织，可以有效纠正因为介质损坏、磁（光）头污染或者定时抖动等引起的连续差错。 2019/4/24

37 5.10* 线性分组码的码限 (1) 研究码限的意义 研究码的纠错能力，也就是分析码的 n,k,d 之间的关系，不仅能从理论上指出哪些码可以构造出，哪些码不能构造出，而且也为工程实验提供了对各种码性能估计的理论依据。 研究码的纠错能力始终是编码理论中一个重要的课题。 在纠错编码实现上总希望在尽可能小的 n 和 r 条件下获得尽可能大的 k,d 或 t。 满足码限的码称为最佳码。 2019/4/24

38 5.10* 线性分组码的码限 (2) 三个码限 普罗特金(Plotkin)限(P限) 对任意二元 (n,k,d) 码满足 2019/4/24

39 5.10* 线性分组码的码限 汉明限(H限) 对任意二元 (n,k,2t+1) 码满足 2019/4/24

40 5.10* 线性分组码的码限 瓦尔沙莫夫－吉尔伯特(Varshamov-Gilbert)(V-G限) 存在某个二元(n,k,d)码满足
2019/4/24

41 5.10* 线性分组码的码限 在 n 充分大时各个码限的关系曲线如图5.33所示。图中以 V-G 限为下限，H 限和 P 限为上限所围的区域(兰色区域)是好码（满足所有上述码限的 (n,k,d)码）。 2019/4/24

42 课外思考题 构造 (15,11) 汉明码的一致监督矩阵并设计译码器。 2019/4/24