格雷码

格雷码（循环二进制单位距离码）是任意两个相邻数的代码只有一位二进制数不同的编码，它与奇偶校验码同属可靠性编码。

简介

格雷码（Gray code）是由贝尔实验室的Frank Gray在1940年提出，用于在PCM（脉冲编码调变）方法传送讯号时防止出错，并于1953年三月十七日取得美国专利。格雷码是一个数列集合，相邻两数间只有一个位元改变，为无权数码，且格雷码的顺序不是唯一的。

格雷码能避免讯号传送错误的原理

传统的二进制系统例如数字3的表示法为011，要切换为邻近的数字4，也就是100时，装置中的三个位元都得要转换，因此于未完全转换的过程时装置会经历短暂的，010,001,101,110,111等其中数种状态，也就是代表着2、1、5、6、7，因此此种数字编码方法于邻近数字转换时有比较大的误差可能范围。格雷码的发明即是用来将误差之可能性缩减至最小，编码的方式定义为每个邻近数字都只相差一个位元，因此也称为最小差异码，可以使装置做数字步进时只更动最少的位元数以提高稳定性。 数字0～7的编码比较如下：

十进制 　 格雷码　二进制

0  　　 000    000
1  　　 001    001
2   　　011    010
3   　　010    011
4   　　110    100
5   　　111    101
6   　　101    110
7   　　100    111

直接排列

以二进制为0值的格雷码为第零项，第一项改变最右边的位元，第二项改变右起第一个为1的位元的左边位元，第三、四项方法同第一、二项，如此反复，即可排列出n个位元的格雷码。

4位元的格雷码排列

镜射排列

二进制格雷码镜射建构法

n位元的格雷码可以从n-1位元的格雷码以上下镜射后加上新位元的方式快速的得到，如右图所示一般。

下面详述镜射排列（binary-reflected Gray code）构造n位元的格雷码的构造原理。在这个方法中，n位元的格雷码是透过递回地镜射n-1位元的格雷码（也就是复制一份并翻转顺序，放在原列表下方），并在两份列表最前面分别放上0和1，以产生格雷码。比如说，对于n=4，我们有下面步骤：

4位元的格雷码：0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111, 1110, 1010, 1011, 1001, 1000

镜射后的格雷码：1000, 1001, 1011, 1010, 1110, 1111, 1101, 1100, 0100, 0101, 0111, 0110, 0010, 0011, 0001, 0000

将原格雷码加上0：00000, 00001, 00011, 00010, 00110, 00111, 00101, 00100, 01100, 01101, 01111, 01110, 01010, 01011, 01001, 01000

将镜射后的格雷码加上1：11000, 11001, 11011, 11010, 11110, 11111, 11101, 11100, 10100, 10101, 10111, 10110, 10010, 10011, 10001, 10000

最终产生的5位元格雷码：00000, 00001, 00011, 00010, 00110, 00111, 00101, 00100, 01100, 01101, 01111, 01110, 01010, 01011, 01001, 01000, 11000, 11001, 11011, 11010, 11110, 11111, 11101, 11100, 10100, 10101, 10111, 10110, 10010, 10011, 10001, 10000

在这个递回行为中，我们使用了基底情况1位元的格雷码，也就是G₁ = (0, 1)。这也可以想成是0位元的格雷码G₀ = (Λ)（也就是空字串）所生成的结果。更进一步地，我们可以透过这个流程，看出这个标准格雷码所给出的一些性质。下面使用G_n表示这样生成出的n位元的格雷码，则对于任何${\displaystyle n\geq 0}$，我们有：

• G_n是数字0, 1, 2, ..., 2ⁿ-1在二进制中的某个排列，换言之，这些数字的二进制在n为元的格雷码中都恰好出现一次。
• G_n可以看成是被镶入在G_n+1的前半段之中的。
• 由上可看出这个编码是稳定的，即，当某个二进制数出现在这个编码当中之后，它都将占据相同的位置，不论编码的位数n变得多大。这也允许我们谈论“编码中第几个号码”，因为这是被良好定义的。
• 任两个相邻的号码都相差恰好一个位元，即，他们的汉明距离为一。
• 最后一个号码（必为2^n-1的n位元二进制编码）总是与第一个号码（0的n位元二进制编码）相差恰好一个位元。换言之，这个编码是循环的。

二进制数转格雷码

（假设以二进制为0的值做为格雷码的0）
G：格雷码 B：二进制码 n：正在计算的位
根据格雷码的定义可得：
G(n) = B(n+1) XOR B(n)
即
G(n) = B(n+1) + B(n)
自低位至高位运算即可，无需考虑进位，例略。

2位元格雷码 00 01 11 10

3位元格雷码 000 001 011 010 110 111 101 100

4位元格雷码 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000

4位元2进制原始码 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

上述简单且快速的方法可以从格雷码的刻画中看出，以将任意的2进位数值转换为其对应的格雷码。这里给出一个更详尽的解释。要得到该数值，对于所有${\displaystyle 1\leq k\leq n}$，如果第k位元是1，则将第k-1位元反转，否则不修改第k-1位。如此制造的数值即为所求。事实上，我们可以使用异或的布林逻辑来描述，我们得到${\displaystyle g_{m}=m\oplus \left\lfloor {\frac {m}{2}}\right\rfloor }$，其中，g_m是数字m对应到的格雷码。下面给出两个范例：

当m = 13时，其4位元的二进制表示法为1101，因此，其对应的格雷码即为1011。

当m = 8320123时，其23位元的二进制表示法为11111101111010001111011，因此，其对应的格雷码为10000011000111001000110。

有趣的是，这个算法的每个位元可以平行计算，因此理想上所需的时间是固定的。我们接下来证明这个方法的正确性。我们使用数学归纳法。在n=1时此方法成立。而当n<k+1时，如果此方法是正确的，那么对于n=k+1而言，由于前2^k个编码（即${\displaystyle 0\leq m<2^{n}}$时）是被镶入的，并且格雷码是稳定的，从而n=k的计算在n=k+1也成立。接下来，我们仅须证明用此方法计算的${\displaystyle a=g_{m}}$与${\displaystyle b=g_{2^{k+1}-1-m}}$恰好相差2^k即可。注意到${\displaystyle 2^{k+1}-1-m}$其实就是m的反转，并且因为异或运算的性质两输入反转并不影响结果，因此除了最大的位元，a, b两者其余位元的运算结果必相同。然而，显然最大的位元（第k位）必为1，因此，两者恰好相差2^k，证明完毕。

下面给出一段程式码转换任意位数的二进制数值与其格雷码：

在这段 python 程式码中，函式BinaryToGray将一个二进制数字m转换成其对应的格雷码。该格雷码的长度和m的二进制表示法的长度相等。

def BinaryToGray(m: int):
    return m ^ (m >> 1)

格雷码转二进制数

由于G(n) = B(n+1) + B(n)
故而B(n) = B(n+1)-G(n)
自高位至低位运算即可，无需考虑借位。

例： 格雷码0111，为4位数，故设二进制数自第5位至第1位分别为：0 b3 b2 b1 b0。
b3= 0-0 =0
b2=b3-1=0-1=1
b1=b2-1=1-1=0
b0=b1-1=0-1=1
因此所转换为之二进制码为0101

下面给出一段程式码转换任意位数的格雷码与其二进制数值：

这段 python 程式码将一个格雷码 g 转换成其对应的二进制数 。

def GrayToBinary(g: int):
    mask = g
    while(mask):
        mask >>= 1
        g ^= mask
    return g

四维超立方体图与4位元格雷码

超立方体图与格雷码

一个n维超立方体图(Hypercube graph)是指由点集${\displaystyle \{0,1\}^{n}}$构成的图Q_n，其中的边集为数对汉明距离为一的点对。显然的，一个n为元的格雷码与一个n维超立方体图上的一个哈密尔顿循环（或路径）之间有一一对应。因此，我们可以转为研究超立方体图。

这边利用超立方体图给出一个证明格雷码存在的证明：

使用数学归纳法。注意到n=2时图为循环图，因此必有哈密尔顿循环。假设n=k时图Q_n有哈密尔顿循环，则当n=k+1时，因为图Q_n为图Q_k与图K2的笛卡尔乘积，因此其也有哈密尔顿循环，证明完毕。

格雷等距同构

注意到格雷码诱导了一个在两个赋距空间上的等距同构，分别是有限体${\displaystyle \mathbb {Z} _{2}^{2m}}$（其上的距离由汉明距离给出）以及有限环${\displaystyle \mathbb {Z} _{4}^{m}}$（其上的距离由李距离给出）。

举例而言，考虑m=1，我们有同构${\displaystyle 0\mapsto 00,1\mapsto 01,2\mapsto 11,3\mapsto 10}$。

其他种类的格雷码

在实际使用时，格雷码几乎都是指二进制的镜射排列格雷码（BRGC），然而，数学家们也发现了其他不同种类的格雷码。如同镜射排列格雷码一样，他们两两相邻的编码汉明距离都恰好是一。

长度不足2ⁿ的n位元格雷码

事实上我们可以构造出n位元但长度不足2的n次方的格雷码，前提是长度必须是偶数。比如，从一个平衡格雷码开始，移出一对头尾或中间的值，以获得想要的格雷码。

n进位格雷码

除了采用二进制的格雷码，我们也可以考虑使用n进位的格雷码，也称非布林格雷码。恰如其名，它允许使用除了0和1以外的数字做为运算。

举例而言，3进位的格雷码使用了0、1、2三种数字。更广义的来说，一个(n, k)格雷码使用n进位以及k个位元来建立编码。比如(3, 2)格雷码有一个例子是：00, 01, 02, 12, 11, 10, 20, 21, 22。

这样的格雷码也能够使用递回构造出来。这里提供一个递回构造(n, k)格雷码的程式码范例：

程式中的n与k分别为格雷码使用的底数与位数，x为输入待转换的数值。

def toGray(n: int, k:int , x:int):
    temp = []
    for i in range(k):
        ans.append(0)
        temp.append(x%n)
        x /= n
    shift = 0
    for i in range(k-1, -1, -1)
        ans[i] = (temp[i] + shift) % n
        shift += n - ans[i]
    return ans

这里完整地将所有0~26的3进位格雷码都列出来：

000, 001, 002, 012, 011, 010, 020, 021, 022, 122, 121, 120, 110, 111, 112, 102, 101, 100, 200, 201, 202, 212, 211, 210, 220, 221, 222

平衡格雷码

平衡格雷码相较镜射格雷码，将各个位元位置在整个格雷码编码周期的变化次数平衡，将之间的差异降到最小。若一个格雷码是“均匀的”，则所有位元位置的变化次数相等。在${\displaystyle n}$为2的幂次时，共有${\displaystyle n=2^{k}}$个编码，${\displaystyle 2^{k}}$个位元改变（因为每次编码增加，会有一个位元位置发生改变），则必然可以分配在${\displaystyle k}$个位元，每个位元在一个周期里发生${\displaystyle {\frac {2^{k}}{k}}}$次改变。其应用可以参考格雷码#以最小努力在状态之间移动

长游程格雷码

长游程格雷码最大化最小“相邻两次同一个位元位置被更改”距离。比如${\displaystyle n}$位元的镜射格雷码的最后两个位元在整个周期中更新了两次，距离皆为${\displaystyle 2^{n-1}}$。我们想要最大化最小的这个数字。

盒中蛇编码

在${\displaystyle n}$维超立方体图中的诱导路径会形成格雷码，称作盒中蛇编码（snake-in-the-box codes）因为称立方体的每条边皆平行于座标轴，因此沿着其边移动，每次只会有一个座标分量被改变。

若为超立方体图中的诱导循环，则称为盒中线圈（coil-in-the-box）。

给定一个超立方体的维度，可以容纳的最大的格雷码编码数量成为多个研究的内容。

单调格雷码

单调编码在互联网结构中特别有用，尤其是在最小化处理器的线性阵列的扩张的时候。我们不妨定义一个二进制字串的权重为其含有的一的个数。那么，显然格雷码是不可能拥有严格递增的权重的。然而，我们可以透过放宽要求来逼近这个要求。以白话文解释而言，我们转而要求在使用权重w的边之后，就不能再使用权种小于w-1的边了。

下面我们具体的来描述单调格雷码。考虑一个n维超立方体图${\displaystyle Q_{n}=(V_{n},E_{n})}$，我们可以将其依照权种大小来分割成n+1个点集，也就是说，对于${\displaystyle 0\leq i\leq n}$我们可以定义

${\displaystyle V_{n}(i)=\{v\in V_{n}\mid v{\text{ has weight}}i\}}$

那么我们就有${\displaystyle \left|V_{n}(i)\right|={\binom {n}{i}}}$。令${\displaystyle Q_{n}(i)}$为被${\displaystyle V_{n}(i)\cup V_{n}(i+1)}$所诱导的子图，以及令${\displaystyle E_{n}(i)}$为${\displaystyle Q_{n}(i)}$之中的边，那么我们定义一个单调格雷码为在${\displaystyle Q_{n}}$中的一个哈密尔顿路径，使得其满足对于所有${\displaystyle \delta _{1}\in E_{n}(i),\delta _{2}\in E_{n}(j)}$，其中在该路径中${\displaystyle \delta _{1}}$比${\displaystyle \delta _{2}}$先出现，都有${\displaystyle i\leq j}$。

我们考察一个优雅的构造单调n位元格雷码的方法。定义

${\displaystyle P_{1,0}=(0,1)}$

${\displaystyle P_{m,j}=\emptyset \ \forall j<0\lor j\geq n}$

${\displaystyle P_{n+1,j}=1P_{n,j-1}^{\pi _{n}},0P_{n,j}\forall 0\leq j<n}$

其中${\displaystyle \pi _{n}}$是某一个${\displaystyle S_{n}}$中的排列，而${\displaystyle P^{\pi }}$为${\displaystyle P}$的座标被${\displaystyle \pi }$作用的结果。从这里我们有

${\displaystyle G_{n}^{(1)}:=P_{n,0}P_{m,1}^{R}P_{n,2}P_{n,3}^{R}\dots ,\quad G_{n}^{(2)}=P_{n,0}^{R}P_{n,1}P_{n,2}^{R}P_{n,3}\dots }$

其中${\displaystyle P^{R}}$表示其逆路径。

单轨格雷码

此编码方式使用一个共用的长编码，各个位元的数值为取共用编码的某个位置的值，以下是以5个位元表达30个格雷码数值的例子。

track = "111111001111011100000110000000" 
for i in range(30):
    a = [
        track[(0 + i) % 30],
        track[(6 + i) % 30],
        track[(12 + i) % 30],
        track[(18 + i) % 30],
        track[(24 + i) % 30],
    ]
    print(a)

由于此类型的格雷码主要用在旋转编码器上，且对该编码器结构有了解后比较容易理解，因此更多解释和应用请参考格雷码#单轨格雷码编码器。

应用

和格雷码有相同数学模式的玩具

中国的古老益智玩具九连环有着和格雷码完全相同的数学模式，美国一款名为Spinout的玩具也运用了与之相同的数学模式。^[1]

电报编码

法国工程师Émile Baudot于1875^[2]或1876年^[3][4]改进了他的印字电报机（英语：Printing telegraph）的编码，将6位编码改为5位编码，使用镜射建构法的格雷码，被称为博多码。波特率的名称Baud也是从他而来。

其中，所有母音以字母顺序放在镜射格雷码中第四和第五位元为零的区域，剩下的子音也以字母顺序放在剩下的区域。这个编码方式是设计给五个钢琴键的键盘使用的，左手输入第四和第五位元，右手则是剩下的三个位元。博多码于1932年被用作国际电报电码表第一号 (International Telegraph Alphabet No.1, ITA1)。^[5][6][7]

类比数位转换器

法兰克·格雷（英语：Frank Gray）发明了一个使用真空管将类比讯号转换为镜射建构法二进制码的方式，于1953年取得专利^[8]。此编码因而被称为“格雷”。

格雷构想的脉冲编码调变真空管被贝尔实验室的Raymond W. Sears制作出来^[9]。

格雷的专利封面部分内容，图中15号为以镜射格雷码的编码片

格雷使用的这种编码方式能最小化类比转数位产生的错误。直到今日，他的编码仍然被广泛用在这种应用。

位置编码器

用于侦测旋转角度的绝对型旋转编码器，使用3位元的镜射式格雷码

使用13位元格雷码的光学旋转编码器，顶盖（上）包含着光源和光栅，基板（下）灰色部分为光线感测器

格雷码被广泛用在线性和旋转编码器。若要将类比的位置资讯转换为数字信号，一个简单的作法是将输出的每个位元各作为一个轨道，每个轨道有不同的图样，表示该位元在对应的位置为0或1。

最直接的做法是将二进制数字依序排列一周，每个位元为一个轨道，分别读取每个轨道在对应位置的数值，就可以得到转换为数位的位置资讯。然而，在进位的时候我们将会遇到问题。位置3 (011)和位置4 (100)之间看似没有其他数值了，但实际上，我们无法让所有位元变化发生在同一个时间。假如第一个位元先变为1了，则我们会在两数之间短暂读到7 (111)；又或者假如第二个位元先变为0，则我们会短暂读到1 (001)。

这会使得编码器读取到的位置不连续且难以预估，也让读取到的位置和实际位置相差巨大，或在距离很远的位置之间跳动。只要一个位元的变化和其他不完全同步，就可以造成显著的数值偏差。对于绝对型编码器，这会造成位置测量错误，而对于增量型编码器，这会破坏位置追踪。

格雷码相邻的两个编码只相差一个位元，因此位置之间的转换仅有一个位元有变化，完全解决了两个位置之间转换过程的问题。反观二进制编码在进位时会有多个位元产生变化，基本上无可避免读取到错误的数值，而这个错误可以高达全部行程的一半。

单轨格雷码编码器

单轨格雷码编码器

另外一种格雷码是“单轨格雷码”（Single-track Gray code, STGC），由Norman B. Spedding^[10][11]提出，由Hiltgen, Paterson和Brandestini在Single-track Gray Codes (1996).^[12][13]中被精炼。

用作旋转编码器时，编码条只需要一个轨道，且各位元的感测器可以分开放置在一周，可以做得比多轨的编码器小。比如前述的13位元光学旋转编码器将光线侦测器排列在一起，可以想见若制造工艺较差，无法把感测器摆放得很靠近而不互相干扰，则编码盘直径就必须增加，来容纳全部的轨道。若将光线感测器错开，排列到圆形的一周，并相对应的改变编码盘，则可能可以把整体装置做得更小，或减少制造精度要求。

有很多年，数学家们认为没有办法透过调整编码，将编码盘缩减到一轨并透过不同摆放位置的侦测器，让所有侦测器共用一个编码盘，实现格雷码旋转编码器。因此若需要高分辨率的编码器，常见的做法是改用增量型编码器，即可在低至两个位元（两个位元的编码器又称作正交编码器，Quadrature encoder）辨别角度改变。缺点是若转速过快，无法正确读取或记录到每一个位元的改变，则位置资料将会永久错误，直到重新校正回零。

然而Etzion和Paterson^[14]推论没有办法用${\displaystyle n}$个侦测器，用一个共用的轨道区分${\displaystyle 2^{n}}$个位置，但可以做到接近。若${\displaystyle n}$是2的幂，则可以区分${\displaystyle 2^{n}-2n}$个位置；若${\displaystyle n}$是质数，则可以区分${\displaystyle 2^{n}-2}$个位置。

9位元格雷码编码、1度分辨率的单轨编码器

5个位元可以区分30个位置，而Gary Williams于2008年找到9位元、1度分辨率（360个位置）的解法。

布林代数精简化

卡诺图范例。

卡诺图 (Karnaugh map) 被用作一个精简化布林代数的方式，由莫里斯·卡诺于1953年发明。^[15][16]其轴以格雷码标记，方便以图形的方式视觉地找出可以消去的变数，比如图中蓝色区块，在C=0, D=0下，AB变数以格雷码顺序排列时，产生了相邻的1。若可以圈出大小为${\displaystyle 2^{n}}$的方格皆为1，则${\displaystyle n}$个变数就可以被削去。比如原本蓝色区块内的方格为A'BC'D' + ABC'D'，因为AB轴以格雷码标记，相邻的两格只相差一个位置，蓝色区块对应到的是A变化，因此可以化简为BC'D'。

以最小努力在状态之间移动

若一个系统会需要依序地在一些二元控件的所有状态中循环，且改变一个控件会花费非零的努力（金钱、时间、寿命、劳力等等），则格雷码可以最小化改变控件的花费，低到切换状态都只需改变一个控件。测试管路系统的所有阀门开关排列组合就是一个例子，切换位于管路不同位置的阀门需要时间、劳力，甚至阀门寿命，因此最小化改变阀门状态的次数是理想的。

平衡格雷码相较镜射格雷码，每个位元位置的变化次数都尽可能相同。在一个完整的4位元格雷码编码中（4个位元就是16种组合，因此也共会有16个位元改变），平衡格雷码将把16个位元变化分配到四个位元，也就是每个控件需要开关两次。

由于开关有使用寿命，使用机械开关的格雷码编码器可以使用平衡格雷码让各个位元的开关损耗更均匀，延长寿命。

格雷码定址

若将记忆体或总线的定址编码使用格雷码编排，则在序列读取时（比如依序读取记忆体内容）可以减少定址晶体管开关次数，从而减少电路功率和发热。

格雷码计数器和算数

在两个时脉不同步的系统之间以序列的方式传递计数器数值，格雷码是理想的编码方式。因为相邻两个计数只相差一个位元，尽管计数器在以序列方式传递过程中被更改了，也不会产生错误的数值。只要整个传递过程中计数器最多改变1，则接收到的数值只有可能是改变前的或改变后的数值。

又或者计数器是以并列的方式传输，但每条线路可能有不同的传播延迟，尽管时脉不同步，或者传播延迟过大导致部分线路的数值无法在取样时间内抵达，收到的数值也只可能是改变前或改变后的数值。

前者利用格雷码相邻的编码只相差一个位置，因此若将两相邻数字各取前后缀后相接，则结果必然会是两数其中之一。后者利用格雷码相邻的编码只相差一位，无论各个位元有没有及时接收，也只会有一个位元位置是有影响的，其他的位置都没有变化，因此是否收到更新后的数值只跟该位元是否有及时接收到有关，且不会产生其他数值。

无论如何，这都解决了使用一般二进制编码，若没有正确得接收到每一个位元的更新值，则数值将完全错乱的问题。使用格雷码最多只会错误地接收到旧的值，这在某些应用中是可以接受的。

参考来源

文献

• 柯利弗德·皮寇弗; 陈以礼（翻译）. The Math Book:From Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics [数学之书]. 时报文化. 2013-04-16. ISBN 978-957-135-699-0 （中文（繁体））.

{{reflist|refs= ^{[2] [3] [4] [5] [6] [7] [8] [17] [9] [16] [15] [18] [10] [11] [12] [13] [14]}