目录

1. 概要

1.1 格雷码的定义[1]

1.2 格雷码的特点[1]

2. 二进制格雷码生成方法

2.1 镜像法

2.2 异或转换[1]

2.3 奇偶项

2.4 低位优先更新法

 2.5 验证

3. 任意进制格雷码生成方法

1. 概要

        本文介绍几种常用的二进制格雷码生成方法及并给出几种python实现代码。

        进一步，将二进制格雷码的基本定义扩展到任意M进制的格雷码，并给出任意M进制的格雷码的一种编码算法及其python代码实现。

1.1 格雷码的定义[1]

        典型的二进制格雷码（Binary Gray Code）简称格雷码，因1953年公开的弗兰克·格雷（Frank Gray，18870913-19690523）专利“Pulse Code Communication”而得名，当初是为了通信，现在则常用于模拟－数字转换和位置－数字转换中。法国电讯工程师波特（Jean-Maurice-Émile Baudot，18450911-19030328）在1880年曾用过的波特码相当于它的一种变形。1941年George Stibitz设计的一种8元二进制机械计数器正好符合格雷码计数器的计数规律。

        我们通常所说的格雷码一般是指二进制格雷码，其（通俗非严谨）定义为：在一个固定长度的二进制编码中，若任意两个相邻的代码（包括首尾，即最大值与最小值之间）只有一位二进制数不同，则称这种编码为格雷码（Gray Code）。由于最大数与最小数之间也仅一位数不同，即“首尾相连”，因此又称循环码或反射码（???）。

        在数字系统中，计数器的设计要求数码按一定顺序变化。例如，4比特二进制数按自然数递增计数，若采用8421码，则数0111变到1000时四位均要变化，而在实际电路中，4位的变化不可能绝对同时发生，则计数中可能出现短暂的其它代码（1100、1111等）。在特定情况下可能导致电路状态错误或输入错误。使用格雷码可以避免这种错误。

        格雷码在很多场合都有应用，比如通信系统中的编码，比如数字设计中的状态机的编码，比如数字系统中异步FIFO设计中的计数器的编码等等。

1.2 格雷码的特点[1]

1. 格雷码属于可靠性编码，是一种错误最小化的编码方式。因为，虽然自然二进制码可以直接由数/模转换器转换成模拟信号，但在某些情况，例如从十进制的3转换为4时二进制码的每一位都要变，能使数字电路产生很大的尖峰电流脉冲。而格雷码则没有这一缺点，它在相邻位间转换时，只有一位产生变化。它大大地减少了由一个状态到下一个状态时逻辑的混淆。由于这种编码相邻的两个码组之间只有一位不同，因而在用于方向的转角位移量－数字量的转换中，当方向的转角位移量发生微小变化（而可能引起数字量发生变化时，格雷码仅改变一位，这样与其它编码同时改变两位或多位的情况相比更为可靠，即可减少出错的可能性。
2. 格雷码是一种绝对编码方式，典型格雷码是一种具有反射特性和循环特性的单步自补码，它的循环、单步特性消除了随机取数时出现重大误差的可能，它的反射、自补特性使得求反非常方便。
3. 由于格雷码是一种变权码，每一位码没有固定的大小，很难直接进行比较大小和算术运算，也不能直接转换成十进制数，要经过一次码变换，变成自然二进制码，再由上位机读取。 [3]
4. 典型格雷码是一种采用绝对编码方式的准权码，其权的绝对值为2^i-1(设最低位i=1)。
5. 格雷码的十进制数奇偶性与其码字中1的个数的奇偶性相同。

2. 二进制格雷码生成方法

2.1 镜像法

        如上图所示，(n+1)比特格雷码可以基于n比特格雷码进行构造，方法如下：

1. 将n比特格雷码沿纵向翻转得到它的“镜像”
2. 上半部分（即原n比特格雷码）左边添加一个0，下半部分（即镜像部分）左边添加一个1

        实现代码如下：

def bin_gray1_2(N: int):    
    #print('bin_gray1_2...')
    grayList = []
    grayList.append('0')
    grayList.append('1')    
    # print(grayList)
    for k in range(2,N+1):
        for m in range(2**(k-1),2**k):
            grayList.append('1' + grayList[2**k - m - 1])
        for m in range(2**(k-1)):
            grayList[m] = '0' + grayList[m]
    return grayList

2.2 异或转换[1]

        二进制码→格雷码（编码）：

        此方法从对应的n位二进制码字中直接得到n位格雷码码字，步骤如下：

1. 对n位二进制的码字，从右(LSB)到左(MSB)，以0(LSB)到n-1(MSB)编号
2. 如果二进制码字的第i位和i+1位相同，则对应的格雷码的第i位为0，否则为1（当i+1=n时，二进制码字的第n位被缺省认为是0—可以视为为计算方便的权宜，因此第n-1位不变）

        公式表示（G：格雷码，B：二进制码）：

        如下图所示为4比特2进制的格雷码编码过程示意图([1])。

         实现代码如下：

def bin_gray2(N: int):
    grayList = []
    for i in range(2**N):
        i_gray = i ^ (i>>1)
        grayList.append(i_gray) 
    return grayList

         格雷码→二进制码（解码）：

        从左边第二位起，将每位与左边一位解码后的值异或，作为该位解码后的值（最左边一位依然不变）。依次异或，直到最低位。依次异或转换后的值（二进制数）就是格雷码转换后二进制码的值。

        公式表示：（G：格雷码，B：二进制码）：

        实现代码待补充。

  

2.3 奇偶项

        从0对应N比特的全零格雷码开始：

1. 当k为奇数时，在前一个偶数的格雷码的基础上翻转最右边位元（LSB）即得k的格雷码编码
2. 当k为偶数时，在前一个偶数的格雷码的基础上，搜索它从右到左的第一个为1的位元，然后翻转该位元的左边的位元k的格雷码编码

        实现代码如下：

def bin_gray3(N: int):
    grayList = []
    grayList.append(0)
    prev = 0
    for k in range(1,2**N):
        if k%2 == 1: # odd number
            grayList.append(prev^1)
            prev = prev^1
        else: # even number
            pstr = bin(prev)[2:]
            # print(pstr)
            i = len(pstr)-1
            while i>=0:
                # print(i)
                if pstr[i] == '1':
                    break
                else:
                    i -= 1
            cur  = prev ^ (1<<(len(pstr)-i))
            grayList.append(cur)
            prev = cur  
    return grayList

2.4 低位优先更新法

        自己杜撰的方法和名词，不知道有无雷同^-^

        由于格雷码的定义要求每两个相邻数字的格雷码最多只能有一个比特不同，因此以下基于深度优先搜索（DFS）的思路来给出二进制格雷码编码方法。

        假定0~(k-1)的n比特格雷码已经生成好，接下来考虑k的格雷码的生成：以(k-1)的格雷码为基础，尝试从最右边码元（LSB）开始寻找第一个满足条件的可以翻转的比特。算法流程如下：

        实现代码如下：

def bin_gray4(N: int):
    grayList    = []
    grayList.append(0)
    prevGray    = 0
    for k in range(1,2**N):
        cnt = 0
        while 1:
            curGray = prevGray ^ (1< 
        这个算法因为是从最根本的角度来考虑的，因此它具有普适性，即可以适用于任意M进制的格雷码生成。而上面几种生成方法都是只能适用于二进制格雷码的生成方法。当然从实际生成结果来看，可以看出以上几种特定的二进制格雷码的生成方法与本算法的生成结果是一致的。从这个算法出发修改搜索策略的话，可以很容易的地生成其它形式的二进制格雷码编码. 
 
 2.5 验证 
        以下以4比特二进制格雷码为例运行以上各函数看看生成结果：
 
# -*- coding: utf-8 -*-
"""
Created on Fri Oct  1 08:11:24 2021

@author: chenxy
"""

import sys
import time
import datetime
import math
# import random
from   typing import List
# from   queue import Queue
from   collections import deque
import itertools as it
import numpy as np

# Each function's definition

if __name__ == '__main__':                         
    print('bin_gray1_2...')
    grayList  = bin_gray1_2(N)
    print(grayList, 'n')
    
    grayList = bin_gray2(N)
    print('bin_gray2...')
    print([format(grayList[k],'#06b')[2:] for k in range(len(grayList))])
    print('n')
    
    grayList = bin_gray3(4)
    print('bin_gray3...')
    print([format(grayList[k],'#06b')[2:] for k in range(len(grayList))])
    print('n')
    
    grayList = bin_gray4(4)
    print('bin_gray4...')
    print([format(grayList[k],'#06b')[2:] for k in range(len(grayList))])    
    print('n')
 
 运行结果：
 
 
 
3. 任意进制格雷码生成方法 
        如上所述，2.4节所述算法是一个具有通用性的算法，以下在此基础上给出任意N进制的格雷码生成方法及其python代码实现。
 
        敬请期待。。。
 
 
[1] https://baike.baidu.com/item/格雷码/6510858