从二进制格雷码到任意进制格雷码(1)

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）。由于最大数与最小数之间也仅一位数不同，即“首尾相连”，因此又称循环码或反射码（reflected binary code(RBC)）。

在数字系统中，计数器的设计要求数码按一定顺序变化。例如，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<<cnt)
            if curGray not in grayList:
                grayList.append(curGray)
                prevGray = curGray
                break
            else:                
                cnt += 1
    return grayList   

这个算法因为是从最根本的角度来考虑的，因此它具有普适性，即可以适用于任意M进制的格雷码生成。而上面几种生成方法都是只能适用于二进制格雷码的生成方法。当然从实际生成结果来看，可以看出以上几种特定的二进制格雷码的生成方法与本算法的生成结果是一致的。从这个算法出发修改搜索策略的话，可以很容易的地生成其它形式的二进制格雷码编码。

2.6验证

以下以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. 后记

本篇中给出了4种二进制格雷码的生成方式，但是实际上，前三种都是利用了二进制格雷码的已知码结构特征的特殊的生成方法。这些生成方法没有通用性，因为它们是属于事后诸葛亮式，是先设计出了格雷码，然后再根据码的结构特征写出各种技巧性的代码。而且它们也仅仅代表了很多种可能的二进制格雷码中的特殊的一种（当然也是最常用的一种）而已。

只有最后一种方法是从基本定义（the first principle）出发的生成方法，是具有通用性的。而且，即便是二进制的格雷码，也有很多种设计方式，以上各种生成方法只代表了其中一个特定的方法（当然也是最常用的一种）。

下一篇我们将格雷码推广到任意M进制，并给出任意M进制的格雷码的生成方式。任意M进制格雷码可能因为缺乏（最常用的）二进制格雷码那种明显的结构特征，因此二进制格雷码的特定的生成方法就无法适用。但是从基本定义（the first principle）出发的生成方法则是可以通用的。参见下一篇：从二进制格雷码到任意进制格雷码(2)

2021-10-06

Hann Yang在评论区提供了一个很简洁紧凑的二进制的自然码与格雷码相互转换的程序，列举如下供大家参考：

# Hann Yang
def N2G(n,m=1):
    return bin(n^n>>1)[2:].rjust(m,'0')
 
def G2N(G):
    for i in range(2**len(G)):
        if G==bin(i^i>>1)[2:]:break
    return i

[1]https://baike.baidu.com/item/格雷码/6510858

[2]Gray code - Wikipedia