-
格雷码在计算机科学中非常实用，它可以大大减少电路由一个状态到下一个状态过程中产生的混淆，并且它在信息量转换过程中误码率低，容易将物理信号转换为电信号，在水位测量、气象观测等方面都有着广泛应用.而均衡格雷码等一些特殊的格雷码具有更好的可靠性和稳定性.由于格雷码相邻码字间只有1个位置不同，用数列的形式(变化序)去表示一个格雷码显得十分的简便[1-9].我们也可以把格雷码看作一个哈密尔顿圈[10].本文利用文献[2]的方法，并通过引入变化矩阵研究格雷码的变化序，给出了格雷码变化序的一个结论，它可以由一个特殊的格雷码变化序生成另一个格雷码的变化序，该结论能用于构造一些特殊类型的格雷码.
HTML
-
定义1 把2n个二进制n元组有顺序地放在一起，构成一个排列，称这个排列为n阶全码.
定义2 若一个n阶全码相邻的码字只有一个元素不同，称这个全码为n阶格雷码.
由于格雷码相邻的码字只有一个元素不同，我们用一个数字表示相邻码字不同的元素所在的位置(一个二进制n元组的位置从右往左用数字1到n来表示)，这些数字构成一个数列，称为格雷码的变化序.
而全码相邻的码字往往有多个元素不同，我们用变化矩阵来刻画全码相邻码字的变化.
定义3 将一个n阶全码的k(k=2n)个码字均以行向量的形式表示，把这k个行向量拼成一个k行n列的矩阵Ak×n，称A为这个全码的码字矩阵.
定义4 A是一个n阶全码的码字矩阵，它的k个行向量分别记为a1，a2，…，ak，定义
将b1，b2，…，bk拼成一个k行n列的矩阵Bk×n，称B为这个全码对应的变化矩阵.
若一个变化矩阵每行只有一个元素为1，其余元素全为0，则它对应的全码为格雷码.把每行1所在的列标(矩阵列标从右往左记为1到n)依次写成一个数列，即为格雷码的变化序.反过来，格雷码的变化序对应着一个变化矩阵.
定义5 对一个全码的变化矩阵B作如下行变换：
其余行不变，得到矩阵B′，称对变化矩阵进行了一次(i，j)行变换.
定理1 对一个全码的变化矩阵B进行一次(i，j)行变换后，得到的矩阵B′仍然是一个全码的变化矩阵.
证 设一个全码的全码矩阵为A，对应的变化矩阵为B.显然，一个全码交换第i个码字和第j个码字后仍然是一个全码，因此，交换全码矩阵A的ai和aj，得到矩阵A′仍然是一个全码矩阵.且有
设A′对应的变化矩阵为B′，根据变化矩阵的定义：b′i=a′i+1⊕a′i，B′与B不同的行有四行：
类似地，可以得到
变化矩阵B′正是由B进行一次(i，j)行变换得到，结论得证.
-
下面介绍3个定理，都是由一个格雷码的变化序构造另一个格雷码的变化序.其中前两个定理是通过构造新的格雷码得出，最后一个是本文的主要结论，利用变化矩阵给出证明.
定理2 若c1，c2，…，ck是一个n阶格雷码的变化序，则c2，…，ck，c1也是一个n阶格雷码的变化序.
证 设有一个n元组是一个n阶格雷码，其变化序是c1，c2，…，ck，码字矩阵为A，先把A的第一行移到最后一行，再把A的第一行中元素为1所在的列做一次异或.根据格雷码的定义易知，所得到的矩阵仍然是一个格雷码的码字矩阵，且第一行为全零向量，其变化序为c2，…，ck，c1.
定理3 若c1，c2，…，ck是一个n阶格雷码的变化序，则c1，c2，…，ck-1，n+1，ck-1，…，c2，c1，n+1是一个n+1阶格雷码的变化序.
证 设有一个n元组是一个n阶格雷码，其变化序是c1，c2，…，ck.在每个n元组的最左端添加一个0，然后，以n阶格雷码所给顺序的相反顺序列出n元组，并把1添加到各n元组的最左端.根据格雷码的定义，容易看出按上述方法构造的是一个n+1阶格雷码，且其变化序为c1，c2，…，ck-1，n+1，ck-1，…，c2，c1，n+1.
既然格雷码的变化矩阵与变化序是一一对应的，我们可以将一个格雷码的变化序写成变化矩阵，并对它做一系列的(i，j)行变换，所得到的变化矩阵如果每行也只有一个元素为1，那么说明它是另一个格雷码的变化矩阵.将它写成数列形式，则必为一个格雷码的变化序.
定理4 若c1，…，ci-t，…，ci，…，ci+t，…，ck-1，n+1，ck-1，…，ci+t，…，ci，…，ci-t，…，c1，n+1是一个n+1阶格雷码的变化序，且满足ci-1=ci+1，ci-2=ci+2，…，ci-t=ci+t，则将此变化序前半部分的ci-t，…，ci-1，ci+1，…，ci+t删除，并在后半部分的ci+t，…，ci，…，ci-t中每两个间各嵌入一个n+1后得到的数列：c1，…，ci-t-1，ci，ci+t+1，…，ck-1，n+1，ck-1，…，ci+t，n+1，ci+t-1，…，n+1，ci，n+1，…，ci-t+1，n+1，ci-t，…，c1，n+1也是一个n+1阶格雷码的变化序.
证 设有一个n+1阶格雷码，它的变化序是
将它写成变化矩阵的形式，记为B，记B的行向量为b1，b2，…，b2k，则满足
对变化矩阵B依次做(i-t+1，i+t+1)行变换，(i-t+2，i+t+2)行变换，(i-t+3，i+t+3)行变换，……，(2k-i-t-1，2k-i+t+1)行变换.根据定理1，所得到的矩阵B′也是一个变化矩阵.
在做(i-t+1，i+t+1)行变换时，
之后所做的行变换中，第i-t行不会再变，即b′i-t=bi.
在做(i-t+1，i+t+1)行变换时，
在做(i-t+2，i+t+2)行变换时，
之后所做的行变换中，第i-t+1行不会再变，即b′i-t+1=bi+t+1.
依次类推，可以发现B′中每个行向量都是B中的某个行向量，即B′每行恰有一个元素为1，其余元素为0.因此它是一个格雷码的变化矩阵，将它写成变化序为：c1，…，ci-t-1，ci，ci+t+1，…，ck-1，n+1，ck-1，…，ci+t，n+1，ci+t-1，…，n+1，ci，n+1，…，ci-t+1，n+1，ci-t，…，c1，n+1.
-
有了上节的3个结论，可以构造一些特殊类型的格雷码的变化序，现以构造均衡格雷码为例.先介绍格雷码的变化数和均衡格雷码的定义.
定义6 设一个n阶格雷码的变化序为c1，c2，…，ck，则称(dn，dn-1，…，d1)为此格雷码的变化数，其中di为变化序c1，c2，…，ck中i出现的次数.
定义7 若一个n阶格雷码的变化数(dn，dn-1，…，d1)满足|di-dj|≤2，i，j∈{1，2，…，n}.则称此格雷码为均衡格雷码.
下面介绍一个构造均衡格雷码的实例，3阶反射格雷码的变化序：
1，2，1，3，1，2，1，3
它的变化数为(2，2，4)，是一个均衡格雷码.利用定理2可知2，1，3，1，2，1，3，1是一个3阶格雷码的变化序，它的变化数仍为(2，2，4).利用定理3，可以构造一个4阶格雷码的变化序：
2，1，3，1，2，1，3，4，3，1，2，1，3，1，2，4
它的变化数为(2，4，4，6)，利用定理4，将变化序中第一个3两边的两个1去掉，在倒数第一个3两边添加两个4，得到的仍然是一个4阶格雷码的变化序：
2，3，2，1，3，4，3，1，2，1，4，3，4，1，2，4
它的变化数为(4，4，4，4)，是一个4阶均衡格雷码.利用定理3可以构造一个5阶格雷码的变化序：
2，3，2，1，3，4，3，1，2，1，4，3，4，1，2，5
2，1，4，3，4，1，2，1，3，4，3，1，2，3，2，5
它的变化数为(2，6，8，8，8)，利用定理4，将变化序中第一个3两边的两个2和第一个4两边的两个3分别去掉，再在倒数第一个3和倒数第一个4两边各添加两个5，得到的仍然是一个5阶格雷码的变化序：
3，1，4，1，2，1，4，3，4，1，2，5，2，1，4，3
4，1，2，1，3，5，4，5，3，1，2，5，3，5，2，5
它的变化数为(6，6，6，6，8)，是一个5阶均衡格雷码.继续利用上述方法，构造出6阶均衡格雷码，变化数为(10，10，10，12，10，12)，变化序为：
3，4，2，1，3，1，5，1，4，3，4，1，2，1，3，5
4，5，3，1，2，5，3，5，2，6，2，5，3，5，2，1
3，5，4，5，3，1，2，1，4，3，4，1，2，6，5，6
2，1，4，6，3，6，4，1，2，1，6，4，6，1，3，6
类似地，可以构造更高阶的均衡格雷码，以及构造一些其它类型的对变化数有特殊要求的格雷码.
-
本文引入变化矩阵的概念去刻画码字的变化，并利用此给出了一个关于格雷码变化序构造的结论，该结论对格雷码变化序的构造有一定帮助.在研究过程中，笔者还发现了一个有趣的规律，对R进制的格雷码的变化矩阵实施矩阵的3种初等列变换，变换过后的矩阵仍然是一个R进制的格雷码的变化矩阵，但笔者并未给出证明.若能给出证明，利用该结论和本文给出的方法可以得出更多格雷码变化序的构造方法，有兴趣的读者可以研究这个问题.
DownLoad: