解题报告之格雷码

 |   

格雷码(Gray Code)是指在一组数的编码中,任意两个相邻的代码只有一位二进制数不同,则称这种代码为格雷码。另外由于最大数和最小数之间也仅有一位数不同,即“首尾相连”,因此又称为循环码反射码。这篇博文主要介绍怎样用递归的方式构造格雷码以及格雷码与 8421 码之间的转换。

简介

在数字系统中,通常要求代码按一定顺序变化。例如,按自然数递增计数,若采用8421码,则数 0111 变到 1000 时四位均需要变化,而在实际电路中,四位的变化不可能绝对同时发生,则计数中可能出现短暂的其他编码(1100,1111等),在特定情况下可能导致电路状态或输出错误。而使用格雷码可以避免这种错误。这也是格雷码循环码的原因。而叫它反射码的原因在于常见的编码生成方式是反射或镜像。

题目

题目的来源有两个,一个是最近腾讯笔试的编程题:给定一个编码位数n,用递归的方式输出这串n位格雷码,而另一题目是 LeetCode上的第 87 题,就是给出一个编码位数n,以十进制的方式输出这串 n 位格雷码。

思路

  1. 反射或镜像 之所以称格雷码反射码,是因为通过反射可以构造格雷码。下面这附图通过n的增大来体现何为反射码.
    gray.png

图中的虚线就是反射的反射面,也是镜像的镜面。而由 n 变化到 n+1,只需将 n 的格雷码镜像翻转后,上面的镜像前面添 0,下面的镜像前面添 1。除此之外,还可以发现以下的规律:

> 假定正常顺序是先出现 0 再出现1,那么:
> 如果第i位前面出现偶数个 1,那么第i位就是正常顺序;
> 如果第i位前面出现奇数个 1,那么第i位就是不正常顺序。
  1. 格雷码和 8421码的转换 其实格雷码和我们经常使用的 8421码之间是可以直接转换的,也就是说给定一个数值为 k 的 8421码可以直接得出第 k 个格雷码。当然给定一个格雷码也可以直接获得这个格雷码对应的8421码。那么这就需要知道格雷码和8421码之间的对应关系。下图将给个详细的解释。
    8421.png

图中第一个矩形表示的是格雷码和8421码的对应关系。

> **Tips:**  
> 对于格雷码的序列有多种,这里采用的是最常见的一种方式。

图中第二个矩形表示的是格雷码和8421码之间的转换关系。由图中可以看出由格雷码转换到8421码时,有如下的对应关系: $$ 8421[0]=Gray[0]; i=0 $$$$ 8421[i]=Gray[i] \wedge Gray[i-1]; i>0 $$ 同理我们可以得到8421码到格雷码的转换,转换关系如下: $$ Gray[0]=8421[0]; i=0 $$$$ Gray[i]=\backsim (8421[i] \wedge 8421[i-1]); i>0 $$

算法说明

  1. 通过递归的方式构造格雷码

     1// bin[]    存放二进制编码
     2// ind      确定第ind的编码
     3// sum      前ind位有多少个1
     4// num      编码的位数
     5void GrayCode(int bin[], int ind, int sum, int num){
     6    int i;
     7    if(ind==num){
     8        // 输出显示
     9        for(i=0; i<num; i++)
    10            printf("%d ",bin[i]);
    11        printf("\n");
    12        return;
    13    }else {
    14        if(sum%2==0){
    15            // 前ind位有偶数个1,正常顺序
    16            bin[ind]=0;
    17            GrayCode(bin,ind+1,sum,num);
    18            bin[ind]=1;
    19            GrayCode(bin,ind+1,sum+1,num);
    20        }else{
    21            // 前ind位有奇数个1,不正常顺序
    22            bin[ind]=1;
    23            GrayCode(bin,ind+1,sum+1,num);
    24            bin[ind]=0;
    25            GrayCode(bin,ind+1,sum,num);
    26        }
    27    }
    28}
    

    源码

  2. 8421码转换到格雷码

     1// n        编码位数
     2// returnSize   存放返回8421码数组的长度
     3// return   8421码数组
     4int* GrayCode(int n, int* returnSize) {
     5    int i;
     6    // 数组长度
     7    *returnSize = 1<<n;
     8    int* gray=malloc((*returnSize)*sizeof(int));
     9    for(i=0; i<*returnSize; i++){
    10        // 格雷码转换为8421码,一步到位
    11        gray[i]=i^(i>>1);
    12    }
    13
    14    return gray;
    15}
    

    源码

举一反三

格雷码转换到8421码也可以用位运算一步解决: $$ 8421=~(Gray \wedge (Gray»1)); $$

技术茶话会
< 前一篇