维普资讯 http://www.cqvip.com 第２＝２鲞第３期 ２０吆年６月 ＪＯＵＲＮＡＬＯＦ ｓｌｉ＾ ＣＲＡＯＮＤｌ ｌＡＬ００ｌ工日ＧＥ 上饶师范学院学报 Ｖｄ．２２。Ｎｏ．３ ＪＩＩＩ．２１００ｃ２ 计算机纠错码中的０—１矩阵 谭国律 （上饶师范学院数学计算机系，江西上饶３３４００１） 摘要：在计算机纠错码技术中，０—１矩阵是重要的理论基础和工具。本文就模２有限城上的０—１矩阵，给出了 几个在应用中有重要作用的基础性结论。 关键词：Ｏ—ｌ矩阵；线性相关性；纠错码 中图分类号：ＴＦ３（／２．８ 文献标识码：Ａ 文章编号：１００４—２２３７（２００２）０３—００２１—０３ 在计算机进行数据存储、传输等过程中，广泛使用各种信息编码技术，其主要目的是增强数据的正确性。 在这些技术中，模２的剩余类环上的矩阵起到重要的作用，它为这些技术提供了有力的理论基础和工具。 记ＧＦ（２）＝｛０，ｌ｝，它按模２的加法和数乘构成一个有限域。ｎ个二进制数组成一个码字，可把它看成是 ＧＦ（２）上的一个ｎ维向量。所谓线性分组码就是这样一些码字所组成的ＧＦ（２）上一个线性子空间，它的生成 矩阵和一致校验矩阵就是元素取自ＧＦ（２）上的矩阵。在信息编码技术中，这些矩阵扮演着重要的角色。由 于在ＧＦ（２）上有：ｌ＋ｌ＝ｏ，而在一般数域上这是不成立的，由此导致矩阵１ｌ ０ ｌ ｌ ｌ在ＣＦ（２）上是不可逆的， Ｊ ｌ ｏ ｌ而在一般数域上它却是可逆的。所以，ＧＦ（２）上的矩阵与一般数域上的矩阵存在差异，利用ＧＦ（２）上矩阵去 研究信息编码时，有些地方需特别小心。对于ＧＦ（２）上的矩阵，有些基础性的结果有必要重新审视。本文主 要讨论ＧＦ（２）上矩阵的有关性质，无特别声明，文中的矩阵均指ＣＦ（２）上的矩阵。 与一般数域上矩阵一样，可以类似地定义ＧＦ（２）上矩阵的初等行（列）变换及初等矩阵，而且矩阵的初等 行（列）变换可借助于在该矩阵的左（右）边乘以相应的初等矩阵来实现。同样可定义上矩阵的行（列）向量的 收稿日期＂２００２—０４—０８ ｆ㈠ｏ］ 作者简介：谭国律（１９５７一 ），男，江西余干人，硕士，上饶师院数学计算机系副教授，从事计算机应用研究。 维普资讯 http://www.cqvip.com 上饶师范学院学报 ２００２（第２２卷） 线性关系及其矩阵的行秩和列秩。 引理１（１）列（行）变换不改变矩阵行（列）的线性关系。 （２）设矩阵 经初等行（列）变换化成Ｂ ，则 的行（列）向量线性无（相）关的充分必要条件是 Ｂ 的行（列）向量线性无（相）关。 证明设有矩阵Ａ＝（ ） ，其．ｍ个行向量为ａ。，ａ２，…， ，ｎ个列向量为岛，＆，…，＆。 １）由于ＧＦ（２）中只有一个非零元１，故列的数乘初等变换显然不改变行的线性关系。 ２）同样显然，交换列也不影响行的线性关系。 ３）若对Ａ施行把第ｉ列的１倍加到第ｊ列（ｉ＃ｊ），这样得到的矩阵的第ｊ列成为ｐ．＋ｐｊ，其它列与Ａ一 样。任取Ａ的ｔ行 ， ，…～，．考虑 ｘＩａｑ＋ｘ２％＋…＋）【ｌ ０ 即线性方程组： 】（｜％ ＝０ Ｐ＝１，２，…，ｎ （＊） 线性方程组（＊）已包含两个方程 ｘ．ｃｑ｜－０，∑】（｜ ｊ＝０ 把线性方程组（＊）中的第ｊ个方程换为∑】（｜（ａｉ ＋ ，）＝０所得到的线性方程组记为（＊＊），则（＊）与 （＊＊）是同解的，这说明第三种列变换也不改变矩阵的行的线性关系。 以上１）２）３）已证明一次列变换不改变行的线性关系，从而若干次列初等变换也不会改变矩阵行的线性 关系。 至于行变换不改变列的线性关系可同理证明，或考虑Ａ的转置矩阵Ａ 即可。 以上证明了（１），可类似地证明（２）。 证毕 引理２ ＧＦ（２）上的初等矩阵在ＧＦ（２）上可逆，且逆矩阵就是它自身。 证明对于第一、二类的初等矩阵，其结论是明显的。至于第三类的初等矩阵，是由于在ＧＦ（２）上，元素１的 负元还是它自身之故。 证毕 定理３设Ａ是ｋ×ｎ矩阵（ｎ≥ｋ），且它的ｋ个行线性无关，则在Ａ中必存在ｋ个线性无关的列。 证明设Ａ的任意ｋ个列线性相关。记Ａ＝（ａ ，ａ２，…，％），其中ａｉ是Ａ的第ｉ个列向量，则ａ 一， 线性相 ｋ 关，即存在不全为零的ａ 一， ∈ＧＦ（２），使得 ａｉ ＝０。由于每个ａｉ非０则１，故不妨设ａ。＝１，则ａ。＝ ａｉ啦。这意味着通过第三类的初等列变换可把Ａ化成含有一列全零的矩阵。继续这种过程，最终可把化成 ｉ＝２ 形式为（Ａｌ０）的一个矩阵，其中Ａ。为ｋＸ（ｋ一１）的。由于Ａ的ｋ个行线性无关，由引理１知，Ａ。的ｋ个行也 线性无关。但这是不可能的，因为Ａ 可通过初等行变换化成一个至少含有一行零的矩阵。 定理４矩阵的行秩等于列秩。 证明 由定理３可证明，矩阵的列秩不小于它的行秩。再考虑矩阵的转置矩阵，就可证明矩阵的行秩不小于 它的列秩，从而矩阵的行秩等于它的列秩。 证毕 基于定理４，ＧＦ（２）上矩阵的秩定义为它的行秩或列秩。 维普资讯 http://www.cqvip.com 第３期 谭国律：计算机纠错码中的０—１矩阵 ２３ 定理５设Ａ是ｋ阶方阵，则它的秩等于ｋ的充分必要条件是它在ＧＦ（２）上可逆。 证明容易明白，在ＧＦ（２）上，Ａ可通过初等变换化成对角矩阵，从这点出发可容易证明本定理。 证毕 定理６设Ａ是ｋ ｘ ｎ矩阵（ｎ≥ｋ），且它的ｋ个行线性无关，则存在ｋ阶可逆矩阵Ｐｌ和ｎ阶置换矩阵Ｐ２，使得 Ｐ。ＡＰ２＝（Ｌ，Ｂ），其中 为ｋ阶单位矩阵，Ｂ为ｋ ｘ（ｎ—ｋ）矩阵。 证明 由定理３知，Ａ中存在ｋ个线性无关的列，故可通过列交换把它们换到前面ｋ列位置，即存在ｎ阶置 换矩阵Ｐ２，使得ＡＰ２＝（Ａ。Ａ２），其中Ａｌ是ｋ阶方阵，且它的ｋ个列线性无关，Ａ２是ｋ ｘ（ｎ—ｋ）矩阵。由定理５ 知Ａｌ是可逆矩阵。所以Ａｆ ＡＰ２＝（ Ａｆ Ａ２）。令ＰＩ＝Ａｆ ，则ＰｌＡＰ２＝（ＩｋＢ），其中Ｂ＝Ａ１ Ａ２。 推论设Ａ是ｋ ｘ ｎ矩阵，且它的秩等于ｒ，则线性方程组ＡＸ＝０的解空间是ｎ—ｒ维的。 证毕 定理６将是一个重要的结论，可以预料，由它可以把线性分组码的编码问题化成对系统码的编码问题，从 而使编码容易实现。关于这一点，本文不再讨论。 参考文献： ［１］王新梅，张焕国，等．计算机中的纠错码技术［Ｍ］．北京：人民邮电出版社，１９９９． ［２］Ｗｅｍｅｒ Ｇｒｅｕｂ．Ｌｉｎｅｒ Ａｌｇｅｂｒａ［Ｍ］，Ｆｏｕｒｔｈ Ｅｄｉｔｉｏｎ．Ｎｅｗ Ｙｏｒｋ Ｈｅｉｄｅｌｂｅｅｒｇ Ｂｅｄｉｎ：Ｓｐｒｉｅｒ－ＶｅａｌＳ，１９８１． Ｔｈｅ ０—１ Ｍａｔｒｉｘ ｏｎ Ｅｒｒｏｒ—Ｃｏｎｔｒｏｌ Ｃｏｄｉｎｇ ｉｎ Ｃｏｍｐｕｔｅｒ ＴＡＮ ＧＵＯ－ｌＵ （ＳｈａｎｇｒａｏＮｏｒｍａｌＣｏｌｌｅｇｅ，Ｓｈａｎｇｒａｏ Ｊｉａｎｇｘｉ ３３４００１，Ｃｈｉｎａ） Ａ 础：Ｏｎ ｅｒｏｒｒ－ｃｖｂｔｒｏｌ∞ Ｉｌｇ ｉｎ ｃｏｍｐｕｔｅｒ，０—１ ｍａｔｉｒｘ ｉｓ ａｎ ｉｍｐｏｒｔａｎｔ ｔｈｅｏｒｅｉｔｃａｌ ｆｏｕｎｄａｔｉｏｎ ａｎｄ ｔｏｏ１．Ｔｈｉｓ ｐａｐｅｒ ｇｉＶ鹳ｓ０ｍｅ ｂａｓｉｃ ｃｏｎｃｌｕｓｉｏｎｓ，ｗｈｉｃｈ ｐｌａｙｓ ａｎ ｉｍｐｏｒｔａｎｔ ｒｏｌｅ ｏｎ ｅｒｒｏｒ－ｃｏｎｔｒｏｌ ｃｏｄｉｎｇ ｉｎ ｃｏｍｐｕｔｅｒ． Ｋｅｙ Ｗｏｒｄｓ：０—１ Ｍａｔｒｉｘ；Ｌｉｎｅａｒｌｙ Ｄｅｐｅｎｄｅｎｃｅ；Ｅｒｒｏｒ－Ｃｏｎｔｒｏｌ
