线性分组码及其应用

2023-06-21 理论教育版权反馈

【摘要】：在分组码中，如果信息码元与监督码元之间的关系又为线性关系时，则这种分组码就称为线性分组码。如果希望用r个监督位构造出r个监督关系式来纠正一位或一位以上错误的线性码，则必要求特别的，2r1=n的线性分组码称为汉明码。线性分组码是建立在代数群论基础之上的，各许用码组的集合构成了代数中的群，它们的主要性质如下。任意两许用码之和仍为一许用码，也就是说，线性分组码具有封闭性。

前面已经谈到，分组码是对信息码元按固定长度分段，每k个信息码元为一段，然后由这k个信息码按照一定的规律产生r个监督码元，从而组成码长为n=k+r的码组，也称（n，k）分组码。在分组码中，如果信息码元与监督码元之间的关系又为线性关系时，则这种分组码就称为线性分组码。

前面介绍的奇偶校验码就是一种最简单的线性分组码，如采用偶校验，我们可以将方程（10-3-1）改写为

式（10-4-1）称为监督关系式，S称为校正子。在接收端解码时，实际上就是计算S的值。当S=0时，认为该码组无错码；S=1时，认为该码组有错码。

由于只有一位监督码元，一个监督关系式，S只有“1”和“0”两种取值，因此只能表示“有错”和“无错”两种信息，而不能指出错误的位置。如果增加一位监督位，就可以组成两个监督关系式，有两个校正子S1和S2，有00、01、10、11共4种组合，就可以表示4种信息。除00表示无错外，其余3个信息就可以表示3种不同的错码信息。

一般来说，若有r位监督码元，就可以构成r个监督关系式，计算得到的校正子就有r位，可以用来指出2r−1种不同的错误信息。当只有一位误码时，就可以指出2r−1个错码位置。

若码长为n，信息位数为k，则监督位数r=n−k。如果希望用r个监督位构造出r个监督关系式来纠正一位或一位以上错误的线性码，则必要求

特别的，2r−1=n的线性分组码称为汉明码。下面通过一个例子来说明汉明码是构建监督关系式及差错控制编码的过程。

设分组码（n，k）中k=4。为了纠正1位错码，由式（10-4-2）可知，要求监督位数r≥3。若取r=3，则n=k+r=7。用a6a5…a0表示这7个码元，用S1、S2、S3表示3个监督关系式中的校正子，则S1、S2、S3的值与错码位置的对应关系可以规定如表 10-4-1（当然，也可以规定成另一种对应关系，这不影响讨论的一般性）所示。

表10-4-1　（7，4）码校正子与误码位置

由表中规定可见，仅当错码位置在a2、a4、a5或a6时，校正子 S1为 1；否则 S1为 0。这就意味着a2、a4、a5和a6这4个码元构成偶数监督关系：

同理，a1、a3、a5和a6构成偶数监督关系：

a0、a3、a4和a6构成偶数监督关系：

在发送端编码时，信息位a6a5a4a3的值决定于输入信号，因此是随机的。监督位a2a1a0应根据信息位的取值按监督关系来确定，即监督位应使上式中S1、S2和S3的值为零（表示编成的码组中应无错码）。即

式（10-4-6）中已经将“⊕”简写成“＋”，经移项运算，解出监督位为

由式（10-4-7）可得表 10-4-2 所示的 16 个许用码组。

表10-4-2　（7，4）码校正子与误码位置

接收端在收到每个传输码组后，计算出S1S2S3的值，如果该值不全为0，说明有误码产生，将予以纠正。例如，接收码组为0000011，可算出S1S2S3=011，由表 10-4-2 可知，在a3位置上有一误码。

不难看出，上述（7，4）汉明码的最小码距d0=3，因此，它能纠正一个误码或检测两个误码。另外，当n很大和r很小时，汉明码的码率接近1。可见，汉明码是一种高效码。

线性分组码是建立在代数群论基础之上的，各许用码组的集合构成了代数中的群，它们的主要性质如下。

（1）任意两许用码之和（对于二进制码这个和的含义是模2和）仍为一许用码，也就是说，线性分组码具有封闭性。