数信息论

格雷码

字数统计: 3.1k字   |   阅读时长: 13分
, , ,

摘要: 格雷码的枚举和计算，异或与动态规划

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在通信中，由于信息码元序列是一种随机序列，接收端无法预知码元的取值，也无法识别其中有无错码。所以在发送端需要在信息码元序列中增加一些差错控制码元，它们称为监督码元（校验元）。在信息码元序列中加监督码元就称为差错控制编码，差错控制编码属于信道编码。

信息码元和监督码元之间有确定的关系，关系不同，形成的码类型也不同。可分为两大类：分组码和卷积码。其中，分组码是把信息码元序列以每 k 个码元分组，编码器将每个信息组按照一定规律产生 r 个多余的码元（称为校验元），形成一个长为 $n=k+r$ 的码字。

当分组码的信息码元与监督码元之间的关系为线性关系时（用线性方程组联系），这种分组码就称为线性分组码。包括汉明码和循环码等。

线性分组码是由 $(n, k)$ 形式表示。编码器将一个 $k$ 比特信息分组（k 个码元形成的信息矢量）转变成一个更长的由给定符号集组成的 $n$ 比特编码分组（n 个码元形成的编码矢量）。若符号集有 $q$ 种符号，也就是每个码元取值有 $q$ 种，则共有 $q^{k}$ 个码字。

对于一个 $(n, k)$ 线性分组码 C，若它的任一个码字的每次循环移位都是 C 的另一个码字，则称 C 是一个循环吗。循环码是线性分组码的一个重要的子类，它有以下两大特点：

  • 第一，码的结构可以用代数方法来构造和分析，并且可以找到各种实用的译码方法；
  • 第二，由于其循环特性，编码运算和伴随式计算，可用反馈移位寄存器来实现，硬件实现简单。

格雷码是一种重要的循环码，本文我们系统学习格雷码的枚举和计算，以及与二进制码的互相转换。

$0 格雷码

格雷码是一个二进制数系统，其中两个相邻数的二进制位只有一位不同。这样在码值上下变化过程中，每次只改变一位码，从而传输、读数的错码率最小。

例如 3 位(0~7)的格雷码：

1
2
3
4
5
6
7
8
G(0) = 000
G(1) = 001
G(2) = 011
G(3) = 010
G(4) = 110
G(5) = 111
G(6) = 101
G(7) = 100

格雷码的应用

  • k 位二进制数的格雷码序列可以视为 k 维空间中的一个超立方体顶点的哈密顿回路，其中格雷码的每一位代表一个维度的坐标。
  • 汽车制动系统的角度传感器，通过产生的数字值来指示机械位置，连续码字之间只有一位变化，避免边界位置的错误。
  • 简化逻辑函数时，可以通过按格雷码排列的卡诺图完成。
  • 通信领域的模拟-数字转换器。
  • 模拟九连环游戏。
  • 模拟汉诺塔。

$1 枚举和计算格雷码

下面以一个模板题来看一下枚举和计算格雷码的算法和代码模板。

n 位格雷码序列 是一个由 2n 个整数组成的序列，其中：

  • 每个整数都在范围 [0, 2n - 1] 内（含 0 和 2n - 1）
  • 第一个整数是 0
  • 一个整数在序列中出现 不超过一次
  • 每对 相邻 整数的二进制表示 恰好一位不同 ，且
  • 第一个 和 最后一个 整数的二进制表示 恰好一位不同

给你一个整数 n ，返回任一有效的 n 位格雷码序列 。

示例 1：
输入：n = 2
输出：[0,1,3,2]
解释：
[0,1,3,2] 的二进制表示是 [00,01,11,10] 。

  • 00 和 01 有一位不同
  • 01 和 11 有一位不同
  • 11 和 10 有一位不同
  • 10 和 00 有一位不同
    [0,2,3,1] 也是一个有效的格雷码序列，其二进制表示是 [00,10,11,01] 。
  • 00 和 10 有一位不同
  • 10 和 11 有一位不同
  • 11 和 01 有一位不同
  • 01 和 00 有一位不同

示例 2：
输入：n = 1
输出：[0,1]

提示：

1
1 <= n <= 16

(1) 枚举 n 位格雷码

算法1：搜索构造法

n 位的格雷码可以通过搜索的方式构造。搜索的每一次迭代得到一个新的格雷码，起点为全 0 格雷码：

  • 翻转最低位得到下一个格雷码
  • 把最右边的 1 的左边的位翻转得到下一个格雷码

交替按照上述策略生成 $2^{k} - 1$ 次，可得到 k 位的格雷码序列。

代码 (模板，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
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    vector<int> grayCode(int n) {
        if(n == 0) 
            return vector<int>({0});
        vector<int> result(1 << n);
        for(int i = 1; i < result.size(); ++i)
        {
            if(i & 1)
                result[i] = flip(result[i - 1], 0);
            else
                result[i] = flip(result[i - 1], right1(result[i - 1]) + 1);

        }
        return result;
    }

    int right1(int x)
    {
        // x 最右边的 1 是第几位
        if(x == 0)
            return -1;
        int ans = 0;
        while(x > 0 && ((x & 1) == 0))
        {
            x >>= 1;
            ++ans;
        }
        return ans;
    }

    int flip(int x, int i)
    {
        // 翻转 x 的第 i 位
        x ^= (1 << i);
        return x;
    }
};

算法2：镜像构造法

n 位的格雷码可以从 n - 1 位的格雷码上下镜射后加上新位的方式快速的得到：

gray_code.png

这种方法类似于动态规划的方式。生成 n 位格雷码，首先生成 n - 1 位格雷码，然后在 n - 1 位的格雷码上做些操作就得到 n 位的答案。

求数字 x 对应的格雷码也可以通过这个对应关系找到动态规划的转移方程。

代码 (模板，C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> grayCode(int n) {
        if(n == 0) 
            return vector<int>({0});
        vector<int> result({0, 1});
        for(int i = 2; i <= n; ++i)
        {
            int m = result.size();
            for(int j = m - 1; j >= 0; --j)
                result.push_back(result[j] + (1 << (i - 1)));
        }
        return result;
    }
};

(2) 计算 x 对应的格雷码

二进制码转为格雷码，两种编码均以十进制数的形式表示。求 x 对应的格雷码 gray[x]。

算法1: 动态规划

要求数字 x 对应的格雷码 dp[x]，参考枚举格雷码的镜像构造法，找到转移方程：

1
2
3
4
5
6
7
8
9
10
状态定义：
dp[x] := 二进制数 x 对应的格雷码

初始化：
dp[0] = 0, dp[1] = 1

状态转移：
y = high_bit(x) << 1
y == x: dp[x] = y - 1
y != x: dp[x] = (y >> 1) + dp[y - 1 - x]

代码 (模板，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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    vector<int> grayCode(int n) {
        if(n == 0) 
            return vector<int>({0});
        int X = (1 << n) - 1; // [0, X]
        dp = vector<int>(1 << n, -1);
        dp[0] = 0, dp[1] = 1;
        for(int x = 0; x <= X; ++x)
            solve(x);
        return dp;
    }

private:
    vector<int> dp;

    int low_bit(int x)
    {
        return x & (-x);
    }

    int high_bit(int n)
    {
        int p = low_bit(n);
        while(p != n)
        {
            n -= p;
            p = low_bit(n);
        }
        return p;
    }

    int solve(int x)
    {
        if(dp[x] != -1)
            return dp[x];
        int y = high_bit(x) << 1;
        if(y == x)
            return dp[x] = y - 1;
        else
            return dp[x] = (y >> 1) + solve(y - 1 - x);
    }
};

算法2: 位运算

观察 x 的二进制和 G[x]，如果 G[x] 的二进制第 i 位为 1，则一定有以下两种情况之一：

  • x 的二进制第 i 位为 1，i + 1 位为 0
  • x 的二进制第 i 位为 0，i + 1 位为 1

这两种情况可以用异或运算表示：

1
G[x] = x ^ (x >> 1);

代码 (模板，C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> grayCode(int n) {
        if(n == 0) 
            return vector<int>({0});
        int X = (1 << n) - 1; // [0, X]
        vector<int> g(1 << n, -1);
        g[0] = 0, g[1] = 1;
        for(int x = 0; x <= X; ++x)
            g[x] = solve(x);
        return g;
    }

private:
    int solve(int x)
    {
        return x ^ (x >> 1);
    }
};

题目：1238. 循环码排列

给你两个整数 n 和 start。你的任务是返回任意 (0,1,2,,…,2^n-1) 的排列 p，并且满足：

  • p[0] = start
  • p[i] 和 p[i+1] 的二进制表示形式只有一位不同
  • p[0] 和 p[2^n -1] 的二进制表示形式也只有一位不同

提示：

1
2
1 <= n <= 16
0 <= start < 2^n

示例 1：
输入：n = 2, start = 3
输出：[3,2,0,1]
解释：这个排列的二进制表示是 (11,10,00,01)
所有的相邻元素都有一位是不同的，另一个有效的排列是 [3,1,0,2]

示例 2：
输入：n = 3, start = 2
输出：[2,6,7,5,4,0,1,3]
解释：这个排列的二进制表示是 (010,110,111,101,100,000,001,011)

算法：构造 n 位格雷码

构造 n 位格雷码，然后记录目标格雷码的位置，最后以该位置旋转数组。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> circularPermutation(int n, int start) {
        // 0 -> 1
        vector<int> result(1 << n);
        int idx = -1;
        for(int i = 0; i < (1 << n); ++i)
        {
            result[i] = i ^ (i >> 1);
            if(result[i] == start)
                idx = i;
        }
        rotate(result.begin(), result.begin() + idx, result.end());
        return result;
    }
};

$2 计算格雷码的逆运算

下面以一个模板题看一下格雷码如何转为二进制码，也就是计算格雷码的逆运算。同样有动态规划和位运算两种算法。

给你一个整数 n，你需要重复执行多次下述操作将其转换为 0 ：

  • 翻转 n 的二进制表示中最右侧位（第 0 位）。
  • 如果第 (i-1) 位为 1 且从第 (i-2) 位到第 0 位都为 0，则翻转 n 的二进制表示中的第 i 位。

返回将 n 转换为 0 的最小操作次数。

提示：

1
0 <= n <= 1e9

示例 1：
输入：n = 3
输出：2
解释：3 的二进制表示为 “11”
“11” -> “01” ，执行的是第 2 种操作，因为第 0 位为 1 。
“01” -> “00” ，执行的是第 1 种操作。

示例 2：
输入：n = 6
输出：4
解释：6 的二进制表示为 “110”.
“110” -> “010” ，执行的是第 2 种操作，因为第 1 位为 1 ，第 0 到 0 位为 0 。
“010” -> “011” ，执行的是第 1 种操作。
“011” -> “001” ，执行的是第 2 种操作，因为第 0 位为 1 。
“001” -> “000” ，执行的是第 1 种操作。

算法1：动态规划

1
2
3
4
5
6
dp[x] := 格雷码 x 对应的二进制数
dp[0] = 0, dp[1] = 1

y = high_bit(x)
y == x: return dp[x] = dp[x / 2] * 2 + 1;
y != x: return dp[x] = dp[y] - dp[x - y];

代码 (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
28
29
30
31
32
33
34
35
36
37
38
39
40
int low_bit(int n)
{
    return n & (-n);
}

int high_bit(int n)
{
    int p = low_bit(n);
    while(p != n)
    {
        n -= p;
        p = low_bit(n);
    }
    return p;
}

class Solution {
public:
    int minimumOneBitOperations(int n) {
        if(n <= 1) return n;
        dp[1] = 1;
        return solve(n);
    }

private:
    unordered_map<int, int> dp;

    int solve(int x)
    {
        if(dp.count(x) != 0)
            return dp[x];

        int highbit = high_bit(x);
        int y = x - highbit;
        if(y == 0)
            return dp[x] = solve(x / 2) * 2 + 1;
        else
            return dp[x] = solve(highbit) - solve(y);
    }
};

算法2：位运算

格雷码 x -> 原数 n。从格雷码的高位遍历到低位，x[i] 表示格雷码第 i 位(从 1 开始)，n[i] 表示原数的二进制第 i 位(从 1 开始)。

位数从高位 k 到低位 1

1
2
3
4
n[k] = x[k]
n[k - 1] = x[k - 1] ^ n[k]
n[k - 2] = x[k - 2] ^ n[k - 1]
n[k - 3] = x[k - 3] ^ n[k - 2]
1
2
3
4
5
while(x)
{
    n ^= x;
    x >>= 1;
}

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int minimumOneBitOperations(int n) {
        if(n <= 1) return n;
        int ans = 0;
        while(n)
        {
            ans ^= n;
            n >>= 1;
        }
        return ans;
    }
};
Share