下载: -
Gray码的编码规则是使任何两个相邻代码只有一个位的状态不同，其余位必须有相同状态.它的好处在于从某一编码变到下一个编码时只有一位状态发生变化，有利于得到更好的译码波形. Gray码的类型很多，表 1列举的是3种长度为3的3进制Gray码.
第一种类型的Gray码是从全零码字开始，指针在最右边，指针所指的数字加1，其余数字保持不变.如果得到的码字与前面的码字不同，则这是新的码字；如果得到的码字与前面的码字相同，则指针左移.重复上述过程，得到如表 1所示第1类中的Gray码. 表 1所示第2类中的Gray码，也叫反射Gray码[1-3]. 表 1中第3类也是Gray码的一种.这种类型的Gray码与表 1的第1类中的Gray码，不仅具有Gray码的所有特性，而且Gray序中后一个码字与前一个码字不同位置处的数字之间有相同的规律：第1类中后一个码字减去前一个码字得到的数字模3都余1，这种类型的Gray码本文称之为定向距离为1的Gray码；第3类中后一个码字减去前一个码字得到的数字模3都余2，这种类型的Gray码本文称之为定向距离为2的Gray码.
Gray码除了在通信、硬件设计领域中应用以外，在计算机相关科学的其他方面也有广泛的应用[4-9].对Gray码进行详细分类，并给出其生成算法，对Gray码的研究及更广泛的应用有着积极的作用.本文给出定向距离为d的循环Gray码的定义，并给出了两种生成定向距离为d的循环Gray码的方法.
本文中n，m，d都是正整数，a mod m表示m除a的余数.
定义1(n维m进制Gray码) 所有mn个n维m进制向量的一个排列称为(n，m)Gray码，此排列遵循的规则是：任意两个相邻向量只有一个位置上的值不一样.若最后一个向量和第一个向量也只有一个位置上的值不一样，则称此Gray码为(n，m)循环Gray码.
设m是一个正整数，任意一个非负整数都可表示成一个m进制的数.将一个m进制的数看成一个向量，则有下面的定义.
定义2(自然序) 将整数0，1，…，mn-1按顺序分别表示成长为n的m进制向量，就得到所有mn个n维m进制向量的一个排列，这个排列称为所有mn个n维m进制向量的自然序.
定义3(定向距离) 对于a，b∈Zm={0，1，…，m-1}，定义从a到b的定向距离为(b-a) mod m.对U=(a1，a2，…，an)，V=(b1，b2，…，bn)∈Zmn，定义从向量U到向量V的定向距离为
$ \sum\limits_{\mathit{i} = 1}^\mathit{n} {\left( {{\mathit{b}_\mathit{i}} - {\mathit{a}_\mathit{i}}} \right){\rm{mod}}\;\mathit{m}} $ .定义4(定向距离为d的Gray码) 一个(n，m)Gray码称为定向距离为d的(n，m)Gray码，简称为(n，m，d)Gray码，若此Gray码中任一向量到后一个向量的定向距离为d.若最后一个向量到第一个向量的定向距离也为d，则称此Gray码为(n，m，d)循环Gray码.
对于m进制Gary码来说，定向距离最大为m-1，最小为1，不可能出现定向距离为0的情形.下面我们总假设d＜m.
文献[5]将二进制Gray码的概念推广到m进制Gray码，给出了一种生成m进制Gray码的方法；文献[6]给出m进制自然序与m进制Gray码(定向距离为1时)的转换方法，这也是利用自然序来生成定向距离为1的Gray码的一种生成方法.本文对任意正整数d，考虑定向距离为d的Gray码.
全文HTML
-
首先证明下面的引理.
引理1 集合{dt mod m | t=0，1，…，m-1}包含m个元当且仅当gcd(d，m)=1.
证 当gcd(d，m)=1时，若存在0≤t1＜t2≤m-1使得dt1 mod m=dt2 mod m成立，则有m整除d(t2-t1)，因此m整除(t2-t1)，但这是不可能的，因为0＜t2-t1＜m.
当gcd(d，m)＞1时，设m=qgcd(d，m)，则1≤q＜m，而dq mod m=0.此时形如
的元中至少有两个相同：0和qd mod m.
定理1 当gcd(d，m)＞1时不存在(n，m，d)Gary码.
证 当gcd(d，m)＞1时，由引理1知，集合{dt mod m | t=0，1，…，m-1}包含元素的个数少于m，即从0到m-1的数字不可能全部出现.而(n，m，d)Gray码若排成一个矩阵，则每一列上的数字都要包含从0到m-1这m个数字，否则矩阵的行数将少于qk.所以当gcd(d，m)＞1时不存在(n，m，d)Gray码.
下面利用递归的方法来构造(n，m，d)循环Gray码.由定理1，我们假设gcd(d，m)=1.
定义G(1，m，d)=(0，d，2d mod m，…，(m-1)d mod m)T，则由引理1知G(1，m，d)是(1，m，d)循环Gray码.
对0≤i≤m-1，定义G(i)(1，m，d)如下：
由于G(1，m，d)是(1，m，d)循环Gray码，所以G(i)(1，m，d)也是(1，m，d)循环Gray码.
对整数j，t，记
$ {{\mathit{\boldsymbol{j}}}_{\mathit{t}}}={{\overbrace{\left( \mathit{j}\rm{, }\mathit{j}\rm{, }\cdots, \mathit{j} \right)}^{{}}}^{\rm{T}}}$ .令若G(2，m，d)中相邻的两行同时出现在子阵((dt mod m)m，G(t)(1，m，d))中，其中0≤t≤m-1，则这两行的第一个分量都为dt mod m，而它们的第二个分量则是G(t)(1，m，d))中的相邻两行，故这两行的定向距离是d.若G(2，m，d)中相邻的两行一个是子阵((dt mod m)m，G(t)(1，m，d))的最后一行，另一个是子阵((d(t+1) mod m)m，G(t+1)(1，m，d))的第一行，则它们的第二个分量都为(m-t-1) mod m，而它们的第一个分量分别是dt mod m和d(t+1) mod m，因此这两行的定向距离为(d(t+1)-dt) mod m=d，所以G(2，m，d)是(2，m，d)循环Gray码.
对0≤i≤m-1，定义G(i)(2，m，d)如下：
显然G(0)(2，m，d)=G(2，m，d).可以验证G(i)(2，m，d)是(2，m，d)循环Gray码.令
对0≤i≤m-1，定义G(i)(3，m，d)如下：
可以验证G(i)(3，m，d)是(3，m，d)循环Gray码.
对0≤i≤m-1，若m个(n-1，m，d)循环Gray码G(i)(n-1，m，d)已经得到，其中G(n-1，m，d)=G(0)(n-1，m，d)，令
则同样可以验证G(n，m，d)是(n，m，d)循环Gray码.
例1 对m=3，d=2，按上面的方法得(1，3，2)Gray码和G(1)(1，3，2)，G(2)(1，3，2)：
进而又可得(2，3，2)Gray码如下：
再由G(2，3，2)=G(0)(2，3，2)，G(1)(2，3，2)和G(2)(2，3，2)又可得到表 1中第3类的G(3，3，2).
文献[6]中研究的Gray码是本文的一个特例：(n，m，1)循环Gray码.
-
第1节给出的构造G(n，m，d)的方法是个递归的方法，效率较低，在实际应用中不方便.本节给出一个直接的方法.
算法1 DirectionalGrayCodeGen(n，m，d)
输入：整数m≥2，n≥1，1≤d＜m且gcd(d，m)=1
输出：mn×n矩阵G
(g1，g2，…，gn)←(0，0，…，0)1×n//1×n零矩阵
G←(g1，g2，…，gn)
(b1，b2，…，bn)←(m-1，m-1，…，m-1)1×n //计数器向量初始化
p=n //指针初始化
while (b1，b2，…，bn)≠(0，0，…，0)1×n do
while bp=0 and p＞1 do
p=p-1 //指针左移一位
end while
gp←(gp+d) (mod m)
RowAppend (g1，g2，…，gn) toG
bp←bp-1 //p位的计数器减1
if p＜n then
(bp+1，…，bn)←(m-1，…，m-1)1×(n-p) //还原p+1到n位的计数器
p=n //指针复位
end if
end while
return G
定理2 设m，n和d都是正整数.若1≤d＜m，则算法1生成G(n，m，d).
证 当n=1时，易知算法1生成G(1，m，d).当(g1)初始化为G(0)(1，m，d)的最后一个行向量((m-1)d mod m)时，算法生成G(1)(1，m，d).一般地，当(g1)初始化为G(i)(1，m，d)的最后一个行向量((m-i-1)d mod m)时，算法生成G(i+1)(1，m，d).设n＞1，假设当n-1，且对0≤i＜m-1，(g1，…，gn-1)初始化为G(i)(n-1，m，d)的最后一个行向量时，算法生成G(i+1)(n-1，m，d).
对输入n，m，d，随着算法1的运行，当计数器向量由初始值(m-1，m-1，…，m-1)n顺序变为(m-1，0，…，0)1×n时，由归纳假设，算法1将生成(0mn-1，G(0)(n-1，m，d)).由于(m-1，0，…，0)n≠(0，0，…，0)1×n，外部的while循环将继续进行.此时p=2，经过内部的while循环后p=1.此时算法将当前向量，即(0mn-1，G(0)(n-1，m，d))的最后一个行向量，(0，g2，…，gn)的第一个分量加d，生成新的当前向量(d，g2，…，gn).之后计数器向量的第一个分量变为m-2，后面的分量还原，计数器向量更新为(m-2，m-1，…，m-1)1×n.由于(g2，…，gn)是G(0)(n-1，m，d)的最后一个行向量，在经过外部while的mn-1-1次循环后算法将生成(dmn-1，G(1)(n-1，m，d)).此时的计数器向量为(m-2，0，…，0)1×n.这样，经过两轮的mn-1次while循环，算法内部的G为
再经过一次循环，计数器向量更新为(m-3，m-1，…，m-1)1×n，而当前向量为
其中(g2，…，gn)是G(1)(n-1，m，d)的最后一个行向量.
一般地，对1≤i≤m-1，经过i轮的mn-1次while循环，算法内部的G为
再经过一次循环，计数器向量更新为(m-i-1，m-1，…，m-1)1×n，而当前向量为
其中(g2，…，gn)是G(i-1)(n-1，m，d)的最后一个行向量.由归纳假设，经过又一轮mn-1次while循环，算法将生成((id mod m)mn-1，G(i)(n-1，m，d)).因此经过m轮的mn-1次while循环，算法将生成
此时的计数器向量为(0，0，…，0)1×n，满足while循环的终止条件，算法输出G，而G=G(n，m，d).
表 2是输入m=4，n=3，d=3时的一个例子.
-
本文提出定向距离为d(≥1)的概念，并给出了两个生成定向距离为d的循环Gray码的方法，其中一个是用递归的方法生成G(n，m，d)，但递归的方法效率较低，实际使用起来不够方便，本文又给出直接生成G(n，m，d)的算法，对于任意d，只要满足算法的条件，都能生成定向距离为d的Gray码.对于每一种方法，后面都有详细的例子可供理解.