格雷码剖析

前段时间做结构光三维重建的时候用到了格雷码编码方法,这里正好做一下总结。

这里讨论的是典型的二进制格雷码(Binary Gray Code),简称格雷码,由贝尔电话实验室研究物理学家Frank Gray提出。Frank Gray 1969年过世,这里所提的Gray码是他在1940年研究出来的,用来在PCM(Puslue Code Modulation)方法传送信号时避免错误。1953年3月17日,Gray取得美国专利,这是格雷码第一次出版的日期。

在一组数的编码中,若任意两个相信的代码只有一位二进制数不同,则称这种编码为格雷码,另外由于最大数与最小数之间也仅一位数不同,即“首尾相连”,因此又称循环码或反射码。前面提到格雷码的提出是为了避免讯号传送错误,原理是什么呢?很简单,在数字系统中,常要求代码按一定顺序变化。比如数字3(二进制011)切换到相信的数字4(二进制100),装置的三个位元都要转换,但是在实际电路中,3位变换不可能绝对同时发生,则计数中可能出现短暂的其它代码,可能导致电路状态错误。格雷码可以避免这种错误。

1
2
3
4
5
6
7
8
十进制 格雷码 二进制
0 000 000
1 001 001
2 011 010
3 010 011
4 110 100
5 111 101
6 101 110

下面谈一下一个喜闻乐见的问题:格雷码生成。
格雷码有一种天然的递归算法:如果要求n位的格雷码,那就先n-1位的;假设G(n-1)表示所有n-1位的格雷码,于是n位格雷码可以用下面的两步构造出来,第一步,把G(n-1)中各个元素左边都加一个0.第二步,把G(n-1)中各个元素的顺序反过来排列,并且在前面都加一个1.由此得到的合集就是格雷码G(n)。


1
2
3
4
5
G(1)={0,1}
G(2)=0{0,1}∪1{1,0}={00,01,11,10}
G(3)={000,001,011,010,110,111,101,100}
G(4)={0000,0001,0011,0010,0110,0111,0101,0100,
1100,1101,1111,1110,1010,1011,1001,1000}

证明也很简单,数学归纳法。当n=1时,{0,1}。如果比n-1小或等于的格雷码都可以用那两条规则构造出来。对于G(n)的前半部分,把0去除显然满足格雷码的性质,加上0同样满足;后半部分亦然。接口部分差异在于第一位的0和1,即只相差1位。G(n)的元素个数为G(n-1)的两倍,即2的n次方,完备性。证毕。简单用C++实现如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
vector<string> generateGraycode(int n)
{
  vector<string> ans;

  if(n==1)
  {
  ans.push_back("0");
  ans.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");
  ans.push_back(temp);
  }
  for(int i=mid_ans.size()-1; i>=0; --i)
  {
  string temp = mid_ans[i];
  temp.insert(0, "1");
  ans.push_back(temp);
  }
  }
  return ans;
}

另一种方法直接生成。稍微仔细观察一下不难发现,最后一位交替改变(0变1,1变0),在每两步改变之间,改变最右边的1的左边的位元(0变1,1变0)。比如G(4),0000,先改变最后一位0,得到0001,然后改变最右边1的左边的位元得0011;然后再次改变最后一位得0010,直到1000.简单实现~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void gray(int n)
{

  int i;
  char code[MAXN];

  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);
  }
}

等等,写到这里还没有结束。还记得汉诺塔问题吗?一定要记得啊,因为我不想再复述了:D。
那么汉诺塔问题与格雷码有什么关系呢?我们知道汉诺塔问题要求一次移动一个圆盘,对应到格雷码,如果我们把最小的圆盘对应为格雷码的最后一位,我们会发现格雷码的改变位元正好对应相应的圆盘。还有个问题,就是第1块圆盘的移动有两种选择。不过不要紧,再稍加观察一下,我们就会发现第1块圆盘的移动是有规律的。假设圆盘最开始所在的柱子编号为1,最终都要移动到编号为2的柱子上,另外一个柱子编号为3。我们发现当盘子总数为奇数时,第1块圆盘的移动序列为123123…;总数为偶数时,移动序列为132132…。至于其它圆盘的移动,稍加判断就可以了。那么一个解汉诺塔问题的非递归算法就出来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
void gray_hanoi(int n)
{

  //3 pegs
  stack<int> *peg = new stack<int>[3];
  //1 disk moving order
  vector<int> order;
  order.push_back(1);

  for(int i=n; i>0; i--)
  peg[0].push(i);

  char code[N];
  for(int i=0; i<n; i++)
  code[i] = '0';
  code[n] = '\0';

  //针对n的奇偶性构造disk1的移动序列
  if(n%2)
  {
  order.push_back(2);
  order.push_back(3);
  }
  else{
  order.push_back(3);
  order.push_back(2);
  }

  int times = 0;
  while(1)
  {
  if(code[n-1]=='0')
  code[n-1] = '1';
  else
  code[n-1] = '0';
  cout << "Move 1 from peg" << order[times%3] << " to peg" << order[(times+1)%3] << endl;
  peg[order[times%3]-1].pop();
  peg[order[(times+1)%3]-1].push(1);
  times++;

  int pos = n-1;
  while(code[pos]=='0') pos--;
  if(pos==0)
  break;
  pos--;
  if(code[pos]=='0')
  code[pos]='1';
  else
  code[pos]='0';

  int from, to;
  for(int i=0; i<3; i++)
  {
  if(!peg[i].empty() &amp;&amp; peg[i].top()==n-pos)
  from = i;
  else if(peg[i].empty() || peg[i].top()>n-pos)
  to = i;
  }
  peg[from].pop();
  peg[to].push(n-pos);
  cout << "Move " << n-pos << " from peg" << from+1 << " to peg" << to+1 << endl;
  }
}

下面是当圆盘总数为4个时候的运行结果
gray_hanoi
无聊的同学可以手动验证一下:)

其实还有一个类似很有趣的问题:九连环问题。篇幅有限,这里就先不写了。大家回去自己看看吧!另外在集合的分割问题中,格雷码也有应用,等下次有空再写吧!

Happy New Year! Happy Weekend!

参考:《C语言名题精选百则》

wiki: 格雷码、汉诺塔、九连环, etc