（应用数学专业论文）由hadamard矩阵构造的纠错码的若干问题的研究.pdf

由h a d a m a r d 矩阵构造的纠错码的若干问题的研究 摘要 h a d a m a r d 矩阵l 是特殊( - 1 ，1 ) 矩阵，不同行是相互正交。 h a d a m a r d 矩阵巩有标准型h a d a m a r d 矩阵、斜型h a d a m a r d 矩阵、斜 标准型h a d a m a r d 矩阵，复h a d a m a r d 矩阵，对称型h a d a m a r d 矩阵，以及 由多种不同方式定义的广义h a d a m a r d 矩阵等等。 若标准型吃中的1 被0 替换，- 1 被1 替换，h a d a m a r d 矩阵风就变成 二元矩阵4 ，由矩阵4 l 生成的码称为h a d a m a r d 码，h a d a m a r d 码在通信 等领域有着广泛的应用。 本文利用标准型h a d a m i i r d 矩阵，斜标准型h a d a m a r d 矩阵以及斜标准 型h a d a m a r d 矩阵的核，构造了新的( 0 ，1 ) 、( 0 ，- 1 ，1 ) 矩阵，以它们为生 成矩阵生成了一类特殊的码。这些码具有一些性质，分别给出了那些特殊 的码是自正交码的充分必要条件，以及码是自对偶码的充分必要条件等 血生 t r6 关键词：标准型h a d a m a r d 矩阵斜标准型h a d a m a r d 矩阵斜标准型 h a d a m a r d 矩阵的核生成矩阵自正交码自对偶码 r e s e a r c ho ns o m ep r o b l e m so fe r r o r c o r r e c t i n gc o d e s c o n s t r u c t e df r o mh a d a m a r dm a t r i c e s a b s t r a c t h a d a m a r dm a t r i c e sa r e s p e c i a l m a t r i c e sa n dd i f f e r e n tr o w sa r e o r t h o g o n a l h a d a m a r dm a t r i c e si n c l u d e sn o r m a lh a d a m a r d m a t r i c e s ，s k e w h a d a m a r dm a t r i c e s ，s k e w - n o r m a lh a d a m a r dm a t r i c e s ，c o m p l e xh a d a m a r d m a t r i c e s ， s y m m e t r i ch a d a m a r dm a t r i c e sa n dm o r eg e n e r a l i z e dm a t r i c e s e t c l e t 以b e an o r m a l i z e dh a d a m a r dm a t r i c e s ，i f + 1 sa r cr e p l a c e db y o sa n d 一1 sb y1 s ，巩i sc h a n g e di n t ot h eb i n a r yh a d a m a r dm a t r i x4 ， c o d e sc o n s t r u c t e df r o m4a r eh a d a m a r dc o d e s i n t h i st e x t ，n e w ( 0 ，1 ) a n d ( 0 ，- 1 ，1 ) m a t r i c e sc o n s t r u c t e df r o m n o r m a lh a d a m a r dm a t r i c e s ，s k e w n o r m a lh a d a m a r dm a t r i c e sa n dt h ec o r eo f s k e w n o r m a lh a d a m a r dm a t r i c e s c o d e sa r eg e n e r a t e df r o mt h e m t h ec o d e s p r o p e r t i e sa r er e s e a r c h e d ，i ti sp r o v e ds u f f i c i e n tc o n d i t i o na n dn e c e s s a r y c o n d i t i o nt h a tt h ec o d e si ss e l f - o r t h o g o n a lc o d e sa n ds e l f - d u a lc o d e s k e yw o r d s ：n o r m a lh a d a m a r dm a t r i c e s ，s k e w n o r m a lh a d a m a r dm a t r i c e s ， t h ec o r eo fs k e w n o r m a lh a d a m a r dm a t r i c e s ，g e n e r a t o rm a t r i x ， s e l f - o r t h o g o n a lc o d e s ，s e l f - d u a lc o d e s 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写 过的研究成果，也不包含为获得 盒厦王些太堂或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示谢意。 学位论文作者签名：办拼二 签字日助旷年易月7 日 学位论文版权使用授权书 本学位论文作者完全了解金月巴王业太堂有关保留、使用学位论文的规定，有权保留 并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权金 起王些太堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：确、址 辨嗍佻易月7 日 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师 签字 电话： 邮编： 乡 乏7 月9 日 致谢 本人在三年的硕士研究生课程学习和撰写学位论文的过程中，自始至 终得到了我的导师朱士信教授的悉心指导，无论从课程学习、论文选题， 还是到收集资料、论文成稿，都倾注了朱士信老师的心血，由衷感谢朱士 信老师在学业指导及各方面所给予我的关心以及从言传身教中学到的为 人品质和道德情操，老师广博的学识、严谨的治学作风、诲人不倦的教育 情怀和对事业的忠诚，必将使我终身受益，并激励我勇往直前。 同时，真诚感谢数学系的全体老师，他们热心的关怀和无私的帮助， 并创造了许多必要条件和学习机会；感谢感谢我的家人，在我研究生学习 阶段对我提供的物质帮助和精神鼓励。正是家人的无私的帮助和奉献，才 使我在研究生阶段全身心的投入到学习之中。 感谢所有的同学给予的帮助。 作者：孙琳 2 0 0 8 年5 月2 8 日 1 1 引言 第一章绪论 s h a n n o n ，在1 9 4 8 年发表的论文“am a t h e m a t i c a l t h e o r y o f c o m m u n i c a t i o n ，【l j 中首次提出了著名的有扰信道编码定理，开创了纠错码 理论的研究方向，奠定了纠错码理论的基石。根据s h a n n o n 的思想， h a m m i n g ，b o s e ，c h a u d h u r i ，h o c q u e n g h e m ( b c h ) ，m a s s e y ，m a e w i l l i a m s ， g o p p a 、n e c h a e v 、冯贵良等纠错码理论专家先后给出了一系列设计好码 和有效译码的方法。而后，纠错码受到了越来越多的通信和数学工作者， 特别是数学家的重视，使纠错码无论在理论上还是在实际中都得到飞速发 展。迄今，纠错码已有五十多年的历史，其发展过程大致分为以下几个阶 段： 2 0 纪5 0 年代至6 0 年代初，主要研究各种有效的编、译码方法，奠 定了线性分组码的理论基础，提出了著名的b c h 码，同时也给出了纠错 码的基本码限。这是纠错码从无到有得到迅速发展的年代。 2 0 纪6 0 年代至7 0 年代初，这是纠错码发展过程中最为活跃的时期。 不仅提出了许多有效的编译码方法，而且注意到了纠错码的实用化问题， 讨论了与实用有关的各种问题，所有这些问题的研究为纠错码的实用打下 了坚实基础。在此期间，以代数方法特别以有限域理论为基础的线性分组 码理论已趋成熟。 2 0 纪7 0 年代至8 0 年代初，这是纠错码发展史中具有极其重要意义 的时期。在理论上以g o p p a 为首的一批学者，构造了一类g o p p a 码，其 中一类子码能达到s h a n n o n 在信道编码定理中所提出的s h a n n o n 码所能达 到的性能，这是纠错码历史上具有划时代意义。在这期间大规模集合电路 和微机的迅速发展，为纠错码的实用打下了坚实的物质基础，因而与实用 相关的各种技术及有关问题得到了极大关注，并在实用中取得了巨大的成 功。 自2 0 纪8 0 年代初至今，g o p p a 等从几何观点讨论分析码，利用代数 曲线构造了一类代数几何码，在这些码中，某些码的性能达到了s h a n n o n 码所能达到的性能。由于代数几何码是一类范围非常广的码，在理论上已 证明它具有优越性能，因而受到了编码理论研究者，尤其是代数几何学家 的重视，使代数几何码的研究得到迅速发展，取得了许多成果。自上世纪 7 0 年代末以来，纠错码技术已开始渗透到很多领域。利用纠错码中的许 多编、译码原理和方法，与通信系统中其它有关技术相结合，得到了一些 令人惊喜的结果。如：纠错码与调制技术相结合所产生的t c m 技术，已 作为国际通信中标准技术而推广使用；纠错码与密码结合，可以构造出一 类既能加密签名，又具有纠错功能的密码系统；纠错码与信源编码相结合 的结果，使得通信系统更为有效与可靠。不仅如此，纠错码中的许多译码 思想和方法，与神经元网络中的能量函数有密切关系，可以用来解决神经 元网络中的一些问题。因此，可以预料，随着科学的进步和实际需要，纠 错码理论必将进一步发展，它的应用范围必将进一步扩大。 1 2 本文的主要内容 本文根据标准型h a d a m a r d 矩阵，斜型h a d a m a r d 矩阵，斜型h a d a m a r d 矩阵的核，分别用不同的构造方法构造了新的( 0 ，1 ) 、( 0 ，- i ，1 ) 矩阵， 以它们为生成矩阵构造出一类特殊的码，并研究它们的一些性质，分别给 出了那些特殊的码是自正交码的充分必要条件，以及码是自对偶码的充分 必要条件等等。 2 第二章域上的线性码 从1 9 4 8 年s h a n n o n n 3 开创纠错码理论以后，人们利用有限域理论作为 工具，建立了系统的有限域上的纠错码理论，这些理论在文献 2 一 1 4 中有全面的研究。 2 1 线性分组码 2 1 1 分组码的基本概念 在数字通信中，经常利用纠错码来进行差错控制，其中一类重要的纠 错码就是分组码。 定义2 1 1分组码是对每段k 位长的信息组，以一定规则增加 厂= n - - k 个校验元，组成长为n 的序列：( c 。，c l 一，c 川) ，称这个序列为码 字( 码组，码矢) ，在二进制情况下，信息组共有2 个，因此通过编码器 后，相应的码字也有2 个，称这2 个码字的集合为( 力，k ) 分组码。 ，l 长序列的可能排列总共有2 ”种( 每一以长序列称为n 重) ，而( 刀，k ) 分 组码的码字集合只有2 种，所以分组码的编码问题就是定出一套规则， 以便从2 “个n 重中选出2 个码字。不同的选取规则就得到不同的码。 定义2 1 2 两个行重x ，y 之间对应位取值不同的个数，称为它们之 间的h a m m i n g 距离，用d ( x ，y ) 表示。 定义2 1 3以重x 中非零码元的个数，称为它的h a m m i n g 重量，简 称重量，用w ( x ) 表示。 定义2 1 4( 刀，七) 分组码中，任两个码字之间汉明距离的最小值， 称为该分组码的最小h a m m i n g 距离d o ，简称最小距离d o = m i ，n ，、p ( x ，y ) 。 以是( 刀，k ) 分组码的另一重要参数，它表明了分组码抗干扰能力的 大小，为方便起见，今后d 。简称为d 。 2 1 2 线性分组码 一个【 ，七】线性码，是把信息划成七个码元为一段，通过编码器变成 长为九个码元的一组作为【栉，七】线性分组码的一个码字。若每位码元的取 值有g 种( q 为素数幂) ，则共有q k 个码字，若q k 个码字集合构成了上 所有n 重构成的以维线性空间的一个k 维线性子空间，则称它是一个 【刀，k 】线性分组码，简称为i n ，七】线性码。 定义2 1 5 【疗，k 】线性码是e 上挖维线性空间圪中的一个七维子空 间y 。由于该线性子空间在加法运算下构成a b e l 群，所以线性码又称 为群码。 因线性分组码是分组码的一类，因此有关分组码的参数，如码率，码 字的距离与码的最小距离，码字的重量等定义，对线性分组码均适用，这 里不再赘述。 显然，k ，d 是分组码的两个最重要参数，因此今后我们用 刀，k ，d 】( 或 【1 ，k 】) 表示线性分组码，而用( 行，m ，d ) 表示码字数目为m 的任何码。 【刀，k ，d 】分组码是一个群码，因此若码字c 。，c 2 “疗，k ，d 】，则由群的 封闭性知c l + c 2 m ，k ，d 】，即c l + 1 7 2 也必是【，z ，k ，棚分组码的一个码字，所 以码字c l ，c 2 之间距离d ( c l ，c 2 ) ，必等于第三个码字c l + c 2 的汉明重量，因 此，一个【刀，k ，d 】分组码的最小距离必等于码中非零码字的最小重量，由 此可得到： 命题2 1 6 【r l ，k ，d 】线性分组码的最小距离等于非零码字的最小重 量即d = r a i n 扣( c ，) ic f 【以，七】 2 1 3 线性码的生成矩阵 i n ，k ，d 】分组码的编码问题就是在玎维线性空间圪中，如何找出满足一 定要求的，有2 个矢量组成的k 维线性空间圪。或者说，在满足给定条 件下，如何从已知的k 个信息元求得，= 刀一k 个校验元。这相当于建立一 线性方程组，已知k 个系数，要求玎一k 个未知数，使得到的码恰好有所要 求的最小距离d 。 二元【胛，k ，d 】分组码共有2 个码字，2 个向量，组成了一个k 维子空 间，因此这2 个码完全可由k 个独立向量所组成的基底而生成。 定义2 1 7以【以，k 线性码圪的基底向量e l = ( u l ，v 1 2 ，) ， e 2 = 【v 2 1 ，v 2 ) ，2 t k l ，2 ，j 构成的矩阵g = 8 l 乞 ： e k h 。 吃。 ： 则称该矩阵为线性码【力，k ，d 】的生成矩阵。 4 嵫； 由于子空间可以有不只一个基底，因而一个帆k 】线性码也可以有多 个生成矩阵。 生成矩阵是编码时的重要工具，可以通过生成矩阵制订如下的编码规 则。假如m = ( m l ，坞，i n k ) 是一个消息组，则m 所对应的码向量是 朋g = ( 确，m z ，m k ) e i 乞 ： 2 白m + e 2 r n 2 + + e k m k = r 啊( v l i ，v 1 2 ，1 1 1 n ) + 矾2 ( v 2 l ，v 2 2 ，v 2 n ) + + ( v 女l ，k 2 ，1 k ) 2 【v l l + 鸭v 2 l + + m k v k l ，v 1 2 + v 2 2 + + 唯2 ， ， 码v l n + 鸭v 2 。+ + m k j 换言之，对应于消息组m = ( m ，m k ) 的码字是其生成矩阵g 的诸 行的线性组合。 若线性码 刀，k ，d 】生成矩阵为g ，k 个信息元组成的信息组为m ，则 有： c = 所g 因为线性码由其生成矩阵完全确定，所以编码器的存储量可以大大减 少，它不必存储全部2 个( 指二元码) 码向量而只需存储生成矩阵的k 行。 当然，编码器除存储器外，还需要有进行线性组合运算的运算器。对编码 的基本要求是，编码设备越简单越好。综上所述，线性空间是符合比马需 要的良好的数学结构。一般而言，线性码的编码是容易实现的。 适当地选取生成矩阵，还可以进一步简化编码设备。 定义2 1 8 若生成矩阵形如g = ( 五彳) 的【刀，k 】线性码称为 【力，k 】系统码。其中厶是k xk 单位矩阵，彳是k x ( n - k ) 矩阵。 【r l ，k 】系统码的特点是，码字的前k 位与对应的消息组相同，后n - k 位是多余数字。 定理2 1 9两个线性码等价的充分必要条件是：其中一个线性码 的生成矩阵可以通过行初等变换和列的置换化成另一个线性码的生成矩 阵。 若能够通过列的置换将一个线性码的全体码字变为另一个线性码的 全体码字，则称这两个线性码是彼此等价的。 定理2 1 1 0 任意线性码都等价系统码。 2 1 4 线性码的一致校验矩阵 定义2 1 11 若定义一个一七) 胛矩阵h 满足： h c r = 0 r 5 或：c h r = 0 其中c 为 栉，k 】的任一码字；h 的每一行向量均线性无关，则称日为码 【7 ，k 】的一致校验矩阵。 显然目矩阵的每一行代表一个线性方程的参数，它表示求一个校验元 的线性方程，故若日确定了，则码 力，k 】也就确定了。 h g t = 0 t g h t ：0 即g 与日的行生成的空间互为零空间。 定理2 1 12 如果【珂，k 】系统码c 的生成矩阵为g = ( 厶a ) ，其 中，厶是k k 单位矩阵，么是k x ( n k ) 矩阵，则码c 的一致校验矩阵为 日= ( 一彳7 厶一t ) 。 2 1 5 对偶码 疗，k ，d 】码是, 维线性空间的一个k 维子空间矿。，由一组基即g 的 行张成，由线性代数知识可知，它的零空间必是一个疗一k 维的线性子空 间矿。一。，并由月一k 个独立向量张成，这i r , i k 个向量就是何矩阵的行， 因此，若把胃矩阵看成是【r , ，l 一七，d 】码的生成矩阵，而把【以，k ，d 】码的g 看 成是它的一致校验矩阵，则我们称由g 生成【刀，k ，d 】线性码c 与由日生成 的线性码c 上 刀，力- k ，d 】为对偶码，相应地，称y 行，女与y ”一i 互为对偶空间， 由此可如下定义对偶码。 定义2 1 13 设线性码c 【玎，七，d 】，c 上全 x 匕lx y = 0 ，对c ， 式中z y 表示x 与y 的内积，则称c 上为c 的对偶码，或正交码。 码c 上是【栉，l k 】线性码。 定理2 1 14【胛，k ，d 】线性码c 的生成矩阵为g ，一致校验矩阵日的 充分必要条件是：c 上的生成矩阵为日，一致校验矩阵为g 。 码c 是 刀，k ，d 】线性码，c 上的生成矩阵日为c 的一致校验矩阵。 2 1 6 由已知码构造新码 定义2 1 15 设c 是上的一个长为刀的码， 弓全t ( c l ，巳，巳，巳+ t ) l ( c - ，c 2 ，巳) c ，善n + l q 5 o ，则称弓为c 的扩充码。 fl 性质2 1 1 6如果c 是以g 为生成矩阵、以为一致校验矩阵的线 6 性码，则扩充码岙有生成矩阵召和一致校验矩阵豆，其中，吞是由g 加上 一列得到，满足召每行之和为0 ：h 一= 定理2 1 17若c 是最小距离为奇数d 的码，则扩充码e 的所有重量 和距离都是偶数，扩充码e 的最小距离为d + l 。 ， 定义2 1 1 8设c 为码c 的扩充码，即c 加上一个额外分位( 称为奇 偶校验位) 来扩充码，其逆过程就是一个删减码。 定义2 1 1 9取码c 中最后一个分量相同的全部码字，然后去掉它 们的最后这个分量，称得到的新码为缩短码。 这个过程虽然减少了码的长度和数量，但并不减少最小距离。 一般而言，如果去掉的符号不是o ，那么该过程将一个线性码变成一 个非线性码。 还有，由两个码构造的一个新码等等。 7 2 2 自正交码 循环码是一类最重要的线性码，它具有严谨的代数结构，又具有循环 的特性，从而性能易于分析，且编译码电路尤其是编码电路简单且易于实 现，现今已发现的大部分线性码与循环码有密切联系，因此循环码特别引 人注目，对它的研究也比较深入和系统化。 2 2 1 基本概念 定义2 2 1 线性码c 【，l ，k ，d 】的对偶码c 上，若cc _ c 上，则称码c 为 自正交码。 自正交码有两个特点： ( 1 ) 自正交码c 中任意码字都和它自身正交。在二元自正交码中， 所有码字的重量都是偶数，在三元自正交码中，所有码字的重量都是3 的倍数。 ( 2 ) c 中任意两个码字都相互正交。 2 2 2 自正交码的生成矩阵 定理2 2 2设二元线性码c 的生成矩阵为g ，如果g 的行重量皆 为偶数，且各行彼此自交，则码c 是自正交码，反之亦真。 定理2 2 3设三元线性码c 的生成矩阵为g ，则g 的行重量皆为3 的倍数，各行彼此自交的充分必要条件是码c 是自正交码。 定理2 2 4设二元线性码c 的生成矩阵为g ，如果g 的行重量皆为 4 的倍数，且各行彼此自交，则c 为自正交码，且c 中所有码字重量都是 4 的倍数。 定理2 。2 5 设c 为二元【 ，； 】自正交码，其中玎为奇数，则对偶 z 码c 上是 疗，坐】码，且c 上= c + ，其中，h 为全为l 的向量。 8 2 3 自对偶码 2 3 1 基本概念 定义2 3 1 c 是【力，k 】码，若c = c 上，则称码c 为自对偶码。 2 3 2 自对偶码的主要结论 定理2 3 2 设c 为i n ，七】自对偶码，则以为偶数，七= 詈，即c 是【纷，詈】 自对偶码。 定理2 3 3设c 为【刀，七】自对偶码的充分必要条件是：c 是【刀，昙】自 二 正交码，其中玎为偶数。 定理2 3 4设码c 是 玎，昙】自对偶码，g = ( 丘4 ) 是码c 的生成矩 阵，其中，厶是k x k 单位矩阵，a 是七( 刀一七) 矩阵，则( 一么r 厶一。) 也是码 c 的生成矩阵。 定理2 3 5 三元【刀，昙】自对偶码的充分必要条件是玎是4 的倍数。 定义2 3 6若码c 中重量为f 的码字有a 。个，称集合 彳； 为码c 的 重量分布。 任意线性码都含有零向量，因此，总有a 。= 1 a 对偶码c 上的重量分布常常用集合 召0 表示。 定理2 3 7 v i 4 t ，a j = 0 ，称二元i n , 睾】自对偶码c 为双偶码。 二 定理2 3 8 。双偶【刀，昙】码存在的充分必要条件是刀是8 的倍数。 9 第三章h a d a m a r d 矩阵 h a d a m a r d 矩阵风是特殊的( - 1 ，1 ) 的y 矩阵，巩羁r = ，以，其中厶是 r ，z 单位矩阵。h a d a m a r d 矩阵的不同行是相互正交，任何行和它本身的实 内积是”。 h a d a m a r d 矩阵风有标准型h a d a m a r d 矩阵、斜型h a d a m a r d 矩阵、斜标 准型h a d a m a r d 矩阵，复h a d a m a r d 矩阵，对称型h a d a m a r d 矩阵，还有由多 种不同方式定义的广义h a d a m a r d 矩阵等等。 文献 15 5 6 详细地介绍了h a d a m a r d 矩阵、标准型h a d a m a r d 矩阵和 斜型h a d a m a r d 矩阵等等。 3 1h a d a m a r d 矩阵 3 1 1 基本概念 定义3 1 1y x 拧矩阵日。，其元素仅仅为1 或一1 ，并且满足 见风7 = n z ，其中厶是刀门单位矩阵，称以为n 阶h a d a m a r d 矩阵。 性质3 1 2以的任何两个不同行的实内积是零，也就是说，不同 行是正交的，任何行和它本身的实内积是, ；列也具有同样的性质。 t - 了 研1 = 兰l ，以r 见= 帆，所以，列也具有同样的性质。 ” 性质3 1 3h a d a m a r d 矩阵任何行或列乘以一1 ，则它就变成另一个 h a d a m a r d 矩阵。我们通过这种变换，我们可以把h a d a m a r d 矩阵日。的第 一行或第一列全部都变成1 定义3 1 4若h a d a m a r d 矩阵日。的第1 行和第1 列全都是1 ，则称 这样的h a d a m a r d 矩阵风为h a d a m a r d 矩阵的标准型。 定义3 1 5 若交换h a d a m a r d 矩阵风的行或列，用一1 乘以行或列所 得的新h a d a m a r d 矩阵，称这两个h a d a m a r d 矩阵是等价的。 很容易得出，阶为1 ，2 ，4 的h a d a m a r d 矩阵只有一个等价类。 1 0 3 1 2h a d a m a r d 矩阵的主要结论 定理3 1 6 若玎阶h a d a m a r d 矩阵域存在，则挎是1 ，2 或是4 的倍 数。 h a d a m a r d 矩阵风的构造方法有：加倍构造，p a l e y 构造等等。 3 2s k e w h a d a m a r d 矩阵 3 2 1 基本概念 定义3 2 1 1 n 矩阵4 | ，其元素仅仅为1 或一1 ，若4 t l 是反对称 矩阵，其中l 是玎n 单位矩阵，则称4 i 是捍刀斜对称型矩阵。 定义3 2 2 刀阶h a d a m a r d 矩阵以，如果以= 最+ 厶，其中，最是r l x n 矩阵，l 是刀玎单位矩阵，并且& = 一，最研= ( ，z 一1 ) 厶，则称峨是疗阶 斜h a d a m a r d 矩阵。 定义3 2 3 聆，z 斜h a d a m a r d 矩阵h 。，如果鼠可以写成 风= ( ! r 芸一。 + 厶= ( 一，1 形一。：厶一。 ，其中，l 是，z 单位矩阵， e = ( 1 ，l ，i ) 是lx ( n - 1 ) 矩阵，则称刀阶斜h a d a m a r d 矩阵以是刀阶斜 h a d a m a r d 矩阵日。的斜标准型。 式子中的呢一。是( 以一1 ) ( 玎一1 ) 矩阵，则称呢一。是以阶斜h a d a m a r d 矩阵 风的核。 3 2 2s k e w h a d a m a r d 矩阵的主要结论 定理3 2 4 ( ，z 1 ) ( 刀一1 ) 矩阵睨一。是以阶斜h a d a m a r d 矩阵也的核， 则呢一。阡尝。= ( 刀一1 ) 厶一。一以一。，形一。以一。= o ，乃尝。= 一形一。 斜h a d a m a r d 矩阵巩的构造方法有：w il l i a m s o n 构造， g o e t h a l s s e i d e l 构造，w a l l i s w h i t e m a n 构造，利用亲和矩阵构造， p a l e y 构造，加倍构造等等。 1 2 第四章由h a d a m a r d 矩阵构造的码 h a d a m a r d 矩阵是特殊的二元( 一1 ，1 ) 矩阵，它的不同行是相互正交的， 任何行和它本身的实内积是刀。若标准型h a d a m a r d 矩阵中的元素l 被0 替 换，一l 被1 替换，那么h a d a m a r d 矩阵就变成二元( 0 ，1 ) 矩阵以，4 的任意 两行在昙个位置上是相同的，在等个位置上是不同的。由二元( o ，1 ) 矩阵 zz 。 4 生成的码称为h a d a m a r d 码，h a d a m a r d 码在通信等领域有着广泛的应用。 文献 2 讨论了h a d a m a r d 码。 4 1 由h a d a m a r d 矩阵构造的码 本节的h a d a m a r d 矩阵风均为标准型。 本节根据标准型h a d a m a r d 矩阵风，用不同的构造方法构造出一类特 殊的码，并研究它的一些性质。 4 1 1 构造方法 定义4 1 1 令巧= 皇咤立，其中以是元素全为1 i 鬟jn xn 矩阵，则e 是一个n x n 拘( 0 ，1 ) 矩阵。 性质4 1 2 k 除第一行之外，每行有兰个1 和三个o 。 性质4 1 3 令巧= ，则乙一- 的每行有旦2 一1 个1 ，兰个 0 ，瓦一。是( n - 1 ) x ( n - 1 ) 的( 0 ，1 ) 矩阵。 定义4 1 4 令g ( 州k ：。- 2 ) = ( l - l ，乏一t ) 是( 丹一1 ) ( 2 n 一2 ) 矩阵，设以 g ( 川卜( ：川) 为生成矩阵的码为码c ，则码c 是二元【2 一2 ，刀一1 】码。 4 1 2 主要结论 _ 4 ， 乙 i l- j 定理4 1 5 码c 【2 n - 2 ，n - 1 】是自正交码的充分必要条件是 以兰4 ( r o o d 8 ) 。 觚耻( 割= ( p r 葛r = ( g r + 乏一。p re + e l n 。_ z l r e r e + l 。k 一。r = ( ：z ，丫+ 厶，r一。乙一1 7 jl o 鸠- 1 j i e + e l 一i r = o f比_ r = 一e 所以， ，+ 厶一1 p 7 = 0 ；即 厶一l ，= 呻r l 口r p + 厶一i 厶一i r = 鸠一ll 厶一i 厶一l r = ，以一l - a 一1 于是，以一。厶一。r = 中厶一。以一= 一以一。 脚一i - i + j = ( e 1 t e 厶一1 + ，州 2 - 小 则 嵋= 毕( 半) r = 扣“厶- i j , , - i + j - i l r - i + j n - l j n - i ) = 丢( 儿r ，一，一“+ ( 川) ，) = 丢( 以l - l + ( 九一4 ) ，) 因此，g ( 川m ：柚) 的行重量1 + 三一1 = 詈， 又力是4 的倍数，所以g ( 州m ：神) 的行重量是偶数。 设g ( 川m ：。一：) 的第f 行为( q ，f j ) ，其中e l 是l 一- 的第f 行，是z 一- 的第所亍。 1 4 、 r d 厶叱 + + 口 p ， ，l、l，一 p k ， ，。l i一 聆一4 l一 刀一4 l一 行一2 _ 一 ； 栉一4 l一 以一2 l一 聆一4 l一 万一2 i一 刀一4 i一 疗一4 当f 歹时，( q ，1 ) ( e j ，t j ) = e i e + t i t j = t ；t j 。 级中不同行的实内积为0 ，则只的每一行有昙个1 ，昙个一l 。任见取 一行( 除第一行外) ，与其它各行( 除第一行外) ，有罢个相同的1 ，旱个 44 相同的一1 ，兰个不同。 z 所以，瓦一- 中不同行有三一1 个相同的1 ，三个相同的0 ，兰个不同。 因此，瓦一l 中任意不同两行内积之和为詈一1 = 2 k ，即以= 8 k + 4 ， 于是，刀量4 ( r o o d 8 ) 。 反之，当n 量4 ( m o d 8 ) 时， g ( 川m ：。一2 ) 的行重量等是偶数，且各行彼此正交。 因此，码c 2 万一2 ，刀一1 1 是自正交码。 定理4 1 6 码c 2 甩一2 ，刀一1 1 是自正交码的充分必要条件是码 c ( 2 甩一2 ，拧一1 ) 是自对偶码。 证明：2 n 一2 是偶数，码c 2 万一2 ，玎一1 1 是自正交码的充分必要条件是 码cf 2 以一2 ，刀一1 1 是自对偶码。 例如1 2 阶h a d a m a r d 矩阵 q 2 = 1 5 ，l l ，l 1 1 l ，i 1一 1一 一 1 1 1 1 1 1 一 一 一 1 1 1 1 一 一 l，ll，l，工，工 1 一 一 一 1 1 1 1 一 一 1工l工-i 1 一 一 l 1 1 1 一 一 1 一iiil工l 1 1 1 1 1 一 一 1 一 一ii_ 1 1 1 l l 一 一 1 一 一 一 l i 1 1，ll 1 l 1 1 一 一 1 一 一 一 1 1 1 1 一 一 1 一 一 一 1 1 -tiil_ 1 1 一 一 1 一 一 一 l 1 1 ，i 1，i，l 1 ，l 1 1一 一 1一 一 一 1 1 1 一 ，上1 l 1 工 1，工，l 1 一 一 1一 一 1 1 1 1 g l l 。2 2 = 以g l 。恐为生成矩阵的码c 是二元 2 2 ，1 1 】码，它是自正交码，是自对偶码。 1 6 o 1 0 0 o 1 1 1 0 1 o 1 0 0 o 1 1 1 0 1 0 o o 0 o 1 l 1 o l 0 o 1 o o l 1 1 o 1 0 0 1 0 0 1 1 1 0 1 o o 1 o o 1 1 l o 1 o o 1 o 0 0 1 1 0 1 o 0 l o 0 0 1 1 0 1 0 0 1 o o 0 l 1 o l o o 1 o 0 o 1 l 1 1 0 0 1 o 0 0 1 1 l o 0 o 1 o o o 1 1 1 0 1 o o 0 0 0 o o 0 o o 1 o o 0 0 0 o 0 0 0 1 o 0 0 o o o 0 o 0 1 o o o o 0 0 o 0 o 1 o o o 0 o o o o 0 l o o 0 0 o o 0 o 0 1 0 o o 0 o o o o o 1 o 0 0 o o o o o o 1 0 o 0 o o o o o 0 1 o o o o o o o 0 o 1 0 0 o 0 o 0 0 o o 1 o o 0 o o 0 o o o 0 4 2 由s k e w h a d a m a r d 矩阵构造的三元码 本节的h a d a m a r d 矩阵鼠均为斜标准型。 本节根据斜标准型h a d a m a r d 矩阵巩，构造出一类特殊的码，并研究 它的一些性质。 4 2 1 构造方法 定义4 2 1 n 阶斜标准型h a d a m a r d 矩阵见，以= 最+ 厶，其中，最 是玎阶矩阵，l 是疗阶单位矩阵，e = 一，鼠爵= ( ，l 一1 ) z ，则刀阶矩阵最是 ( o ，1 ，一1 ) 矩阵。 性质4 2 2 n 阶矩阵最除第一行之外，每行都罢一1 个l 和昙个o 。 z二 。定义4 2 3 令q 幽= ( 厶，s 。) 是以2 n 矩阵，设以q 幽为生成矩阵的 码为码c ，则码c 是三元【2 n ，疗】码。 4 2 2 主要结论 定理4 2 - 4 三元【2 n ，n 】码c 是自正交码的充分必要条件是 刀三0 ( m o d l 2 ) 。 证明：设三元 2 n ，z 】码的生成矩阵为q 咖= ( l ，s 。) 。 以= 最+ l ，其中，瓯是以阶矩阵，厶是n 阶单位矩阵， 并且，最= 一，最爵= ( 力一1 ) 厶， 于是，力刀矩阵鼠是( 0 ，l ，一1 ) 矩阵， 并且，以是1 ，2 或是4 的倍数。 q 砌= ( 厶，s 。) ，则q 咖的行重量1 + ( 詈一ll = 詈， 因为，三元【2 n ，l 】码c 是自正交码， 所以，q m 的行重量昙是3 的倍数。 设瓯咖的第f 行为( e t ，) ，其中e ，是厶的第i 行，毛是最的第f 行 当i j 时，( q ，毋) ( 勺，勺) = 白巳+ 丑o = s - s j 。 又最= ( n - 1 ) i ， 则最中不同行的实内积为0 ， 1 7 于是，g 幽= ( j l t ，s 。) 的不同行彼此自交。 因此，z 善o ( m o d l 2 ) 。 反之，当挖暑o ( m o d l 2 ) 时， q 砌的行重量力是偶数，且各行彼此正交。 于是，三元2 协船1 码c 是自正交码。 定理4 2 5 三元【2 n ，栉】码c 是自对偶码充分必要条件三元【2 n ，力】 码c 是自正交码。 证明：由于三元【力，昙】自对偶码的充分必要条件是疗是4 的倍数， 又因为三元2 n ，刀1 码c 是自正交码的充分必要条件是n 基o ( m o d l 2 ) ， 所以，三元f 2 协珂1 码c 是自对偶码。 1 8 4 3 由s k e w h a d a m a r d 矩阵的核构造的二元码 本节的h a d a m a r d 矩阵峨均为斜标准型。 本节根据斜标准型h a d a m a r d 矩阵见，构造出一类特殊的码，并研究 它的一些性质。 4 3 1 构造方法 定义4 3 1以阶斜标准型h a d a m a r d 矩阵峨，以= 最+ 厶， 风= ( ! r 芸一，) 厶其中，厶是胛阶单位矩阵，p = ( 1 ，1 ，1 ) 是1 ( 力_ 1 ) 矩阵，最是以阶矩阵，s 。= 一，s 。= ( n - 1 ) i 。，n - 1 阶矩阵既一是刀阶斜 h a d a m a r d 矩阵亿的核。 令疋= j _ - h ，其中以是元素全为1 的刀阶矩阵，则疋是一个疗阶 ( 0 ，1 ) 矩阵，e = ( 1 ，1 ，1 ) 是l ( 刀一1 ) 矩阵。 性质4 3 2 k o 除第一行之外，每行有昙个l 和昙个0 。 性质4 3 3 令疋= ，n t 一t 的每行有三一1 个1 ，三个 0 ，瓦一。是n - 1 阶的( 0 ，1 ) 矩阵。 定义4 3 4 令g ( 川) x ( ：帕) = ( l 一- ，乙一i ) 是一1 ) ( 2 玎一2 ) 矩阵，设以 g ( 卜( 2 柚) 为生成矩阵的码为码c ，则码c 是二元【2 疗一2 ，疗一1 】码。 4 3 2 主要结论 定理4 3 5码c 【2 n - 2 ，n - 1 】是自正交码的充分必要条件是 刀兰4 ( r o o d s ) 。 证明：设码c 【2 n - 2 ，万一1 】是自正交码，g ( 川m ：柚) 为码c 的生成矩阵。 设n n 阶c ah a d a m a r d 矩阵以= 最+ 厶，其中，最是n 阶矩阵，厶是刀阶 单位矩阵，& = 一，最爵= ( 甩一1 ) 厶， 1 9 0 一 一 一 瓦 oo l；1 阵。 书乏。 = ( ! r 甜似忙 卜一， 则 h n h ： 怕甜啦r 甜厶丁 一f l + e e r p + p ( 呢- l + 厶一。) r 1 i 一，+ ( 呢一。+ 一。e r ，e + ( 呢一。+ 厶一。) ( 呢一。；厶一，) 7 j i - e + e ( 呢一+ 厶一。) 2 = o 呻r + ( 呢一，+ 厶一。) ，= o l e t e + w n l 一l r + 一l + 呢一i r + l l = 鸠一l i p 形一1 7 = 0 即 呢一。，。= 0 【形一形一r = ( 刀一1 ) o 。一以一。一形一。一形一r 于是， 以一l 呒一l r = 0 ， 形一1 以一l = 0 一。形一。r - - ( n - 1 ) i , , 一。一以一， 又巧= j ，一h n r n - l 砭l = 2 形一l + 形一1 7 = o 。 = 二年 = ( e o ，川一形一1 2 一l lfj n - 1 - - r v r n l 一厶一l 2 ) r 1 ) 是l x ( n - 1 ) 矩 圳 则 = 三( ，川，“一，川哗。一，川l - l - 睨一。，川+ 形一。咤。+ 呢_ l - ，州+ 嚷。+ 厶一。) = 丢( ( 以一1 ) 刀一。一。一。一。+ ( 力一1 ) 厶一。一j 。一+ l 一) = 丢( 以厶一。+ ( 刀一4 ) j 。一) l 0 + 麓外形 一 ， r 口 、l， q + 刀 q + 叩 ，f、 r ，刮0 所 ， 、 、j 加 d嘶瓦 0 n 1 n 1 r 1 1 244 一n 一1 旦1 旦一1 424 ： 。 ： 一n 1 n 1 旦一1 因此，g ( 州m 2 心) 的行重量1 + 詈一1 = 詈， 又”是4 的倍数，所以g ( 。q 翻一：) 的行重量是偶数。 设g ( 川m ：心) 的第衍j ：为( 巳，) ，其中b 是l 一。的第纤于，是乙一- 的第衍亍。 当i ，时，( q ，) 。( 勺，o ) = q 巳+ t , t j = t s 。 峨