格雷码编解码学习(一)：格雷码编码原理与C++代码实现

格雷码(Gray Code)又称循环二进制单位距离码，是任意两个相邻的代码只有一位二进制数不同的编码，它与奇偶校验码同属可靠性编码。Gray Code由贝尔实验室的Frank Gray在1940年代提出，用于在PCM（脉冲编码调变）方法传送讯号时防止出错，并于1953年三月十七日取得美国专利。格雷码是一个数列集合，相邻两数间只有一个位元改变，为无权数码，且格雷码的顺序不是唯一的。具体介绍可参考：https://www.wikiwand.com/zh-cn/%E6%A0%BC%E9%9B%B7%E7%A0%81

直接排列：以二进制为0值的格雷码为第零项，第一项改变最右边的位元，第二项改变右边起第一个为1的位元的左边位元，第三、四方法同第一、二项，如此反复，即可排列出n个位元的格雷码（结合上图理解）。
      镜像排列构建：n位元的格雷码可以从n-1位元的格雷码以上下镜射后加上新位元的方式快速的得到，如下图所示：

说明：水平灰色分割线为镜像分割线，分割线上数值对应镜像数值以箭头相连，增加的新位元以分割线为界，分割线以上最左边添0，分割线以下最左边添1。
       C++代码实现与运行结果：

#include <iostream>
#include <vector>
#include <string>

using namespace std;

///产生n位格雷码(镜像排列方法构建)
vector<string> generateGraycode(int n)
{
	vector<string> nGraycode;
	if (n == 1)
	{
		nGraycode.push_back("0");
		nGraycode.push_back("1");
	}
	else
	{
		vector<string> mid_ans = generateGraycode(n - 1);
		for (vector<string>::iterator iter = mid_ans.begin(); iter != mid_ans.end(); ++iter)
		{
			string temp = *iter;
			temp.insert(0, "0");
			nGraycode.push_back(temp);
		}
		for (int i = mid_ans.size() - 1; i >= 0; --i)
		{
			string temp = mid_ans[i];
			temp.insert(0, "1");
			nGraycode.push_back(temp);
		}
	}
	return nGraycode;
}

int main()
{
	vector<string>nGraycode;
	nGraycode = generateGraycode(3);
	for(int i = 0; i < nGraycode.size(); i++)
		cout << nGraycode.at(i) << endl;
	return 0;
}

另外一种直接排列方法构建 C++ 代码：

///产生n位格雷码(直接排列方法构建)
void generateGraycode2(int n)
{
	int i;
	char code[20];

	for (i = 0; i < n; i++)
		code[i] = '0';
	code[n] = '\0';
	printf("%s\n", code);

	while (1)
	{
		if (code[n - 1] == '0')
			code[n - 1] = '1';
		else
			code[n - 1] = '0';
		printf("%s\n", code);

		i = n - 1;
		while (code[i] == '0') i--;
		if (i == 0)
			break;

		if (code[i - 1] == '0')
			code[i - 1] = '1';
		else
			code[i - 1] = '0';

		printf("%s\n", code);
	}
}