数信息论

信道纠错码的辅助：格雷码的原理与算法

字数统计: 3.2k字   |   阅读时长: 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