Gray Code

基本概念

格雷码是一种准权码，具有一种反射特性和循环特性的单步自补码，它的循环、单步特性消除了随机取数时出现重大误差的可能，它的反射、自补特性使得求反非常方便。格雷码属于可靠性编码，是一种错误最小化的编码方式。

自然二进制码可以直接由数/模转换器转换成模拟信号，但是在某些情况下，例如从十进制的3转换到4的二进制时，每一位都要变。3的二进制位：011，而4的二进制位：100，所以这就会使数字电路产生很大的尖峰电流脉冲。而格雷码则没有这一缺点，它是一种数字排序系统，其中的所有相邻整数在它们的数字表示中只有一个数字不同。它在任意两个相邻的数之间转换时，只有一个数位发生变化。它大大地减少了由一个状态到下一个状态时逻辑的混淆。另外由于最大数与最小数之间也仅一个位不同，故通常又叫格雷反射码或循环码。

二进制和格雷码的转换

二进制码编码成格雷码的准则：从二进制码的最右一位起，依次将每一位与左边一位异或（XOR）运算，其结果作为对应位格雷码的值，最左位不变。

设有 N 位二进制数 B(i)，其中 0 <= i <= N - 1；它可以变换成为同样位数的格雷码 G(i)。
二进制数与格雷码的转换公式如下：

　　G(i) = B(i+1) XOR B(i); 0 <= i < N - 1
　　G(i) = B(i);      i = N - 1

格雷码解码成二进制码的准则：从左边第二位起，将每位与左边一位解码后的值异或，作为该位解码后的值（最左边一位依然不变）。

设有 N 位格雷码 G(i)，把它转换成自然二进制数的算法如下。

自然二进制码的最高位等于雷码的最高位；
自然二进制码的次高位为最高位自然二进制码与次高位格雷码相异或；
自然二进制码的其余各位与次高位自然二进制码的求法相类似。
转换公式如下：

　　B(i) = G(i);      i = N - 1
　　B(i) = B(i+1) XOR G(i); 0 <= i < N - 1

下表给出了二进制码与格雷码的对应关系，十进制数用4为二进制码表示。

十进制数	二进制数	格雷码
0	0000	0000
1	0001	0001
2	0010	0011
3	0011	0010
4	0100	0110
5	0101	0111
6	0110	0101
7	0111	0100
8	1000	1100
9	1001	1101
10	1010	1111
11	1011	1110

位运算符

& 与运算
| 或运算
^ 异或运算
~ 非运算(求补)
> > 右移运算
< < 左移运算

下面代码会用到异或运算符。

C++实现二进制码编码成格雷码

#include "stdafx.h"
#include <iostream>
#include <cmath>
using namespace std;

#define MAX 1000

int BCD[MAX];
int GRAYCODE[MAX];
int temp[MAX];
//BCD码转换成格雷码
void bcdToGraycode(int bcd[], int gray[], int rightIndex)
{
    if (rightIndex == 0)
    {
        gray[rightIndex] = bcd[rightIndex];
        return;
    }
    else
    {
        gray[rightIndex] = bcd[rightIndex] ^ bcd[rightIndex - 1];
        bcdToGraycode(bcd, gray, rightIndex - 1);
    }
}


int main()
{
    int number;
    //二进制数组长度
    int index = 0;
    int len;
    int m = 2;
    int t;
    //输入一个十进制数
    cin >> number;
    //转换成二进制数
    while (number)
    {
        temp[index++] = number % 2;
        number = number >> 1;
    }
    //按照标准格式输出，位数为2的整数次幂
    while (1)
    {
        t = pow(2, m);
        if (index <= t)
        {
            len = t - 1;
            break;
        }
        else
        {
            m++;
        }
    }

    for (int i = 0; i <= len; i++)
    {
        BCD[i] = 0;
    }
    t = index - 1;
    for (int i = 0; i < index; i++)
        BCD[len - index + 1 + i] = temp[t--];
    bcdToGraycode(BCD, GRAYCODE, len);
    for (int i = 0; i <= len; i++)
        cout << GRAYCODE[i] << ' ';
    return 0;
}