星座图中格雷映射及其实现

发表于 本文字数： 3.2k 阅读时长 ≈ 3 分钟

在数字信号的调制中，AWGN信道下，星座图一般是采用gray code 进行编码。

本文讲述格雷码的概念及其分析在星座图中格雷编码映射的必要性，最后给出其Python 代码实现。

格雷码

先了解一下gray code 的概念：格雷码是二进制数字系统的一种排序方式，使得两个连续值在比特级别上仅仅相差一位。

例如：十进制的1 在自然二进制中的表示通常为001，而2将被编码为010。对应的格雷码为001和011。这样，将一个值从1递增至2 对应的编码仅仅需要更改一位比特，而不是两位。

格雷码广泛用于数字通信系统中的纠错1。

  • \(k\) 位二进制数的格雷码序列可以当作 \(k\) 维空间中的一个超立方体（二维里的正方形，一维里的单位向量)顶点的哈密尔顿回路，其中格雷码的每一位代表一个维度的坐标。

格雷星座映射

在QAM等数字调制方案中，数据通常以4 位或更多位的符号传输，信号的星座图被安排为使得相邻星座点传送的位模式仅相差一位。通过将其与能够纠正单个比特错误的信道编码结合，接收器可以纠正任何导致星座点偏离到相邻点区域的传输错误。这使得传输系统不易受噪声影响。

例如4QAM信号，其自然映射和格雷星座映射为:

:--: :--: :--: :--:
数据比特 十进制 自然映射 格雷映射
00 0 -1-1j -1-1j
01 1 -1+1j -1+1j
10 2 1+1j 1-1j
11 3 1-1j 1+1j

假设AWGN信道下，某码元发送10 数据比特，接收端采用最大似然判决 \(y=x+n\), \(\hat{x}=\arg\min_x ||y-x||\) ，采用不同映射，有以下情形：

  • 自然：对应发送1+1j ，有\(P_1\) 的概率被判决为1-1j(即判为11,误比特数1个), \(P_1\)的 概率被判决为01（误比特2个）,\(P_2(P_2<P_1)\) 的概率被判决为00(误比特1个) ，那么平均误比特\(3P_1+P_2\) 个
  • 格雷：对应发送1-1j,\(P_1\) 的概率判决为11和00，均误比特1个，\(P_2\)的概率判为01,误比特\(2P_1+2P_2\)
  • \(3P_1+P_2>2P_1+2P_2\)

发送其余数据比特时，情形类似。可以发现AWGN信道下格雷映射方案的BER性能是优于自然映射的。相比于正常二进制映射，使用格雷码可以降低总体错误率。这也是星座映射采用格雷映射的原因。

格雷码的构造2

我们观察以下 \(n\) 维的二进制和其格雷码 \(G(n)\)。如果 \(G(n)\) 的二进制第 \(i\) 位为1，仅当 \(n\) 的二进制第 \(i\) 位为 1,第\(i+1\) 位为 \(0\) 或者 第\(i\) 位为 0 ,第 \(i+1\) 位为 1。于是可以当成一个异或运算：

\[G(n)=n\oplus \lfloor\frac{n}{2}\rfloor\]

1
int g(int n) { return n ^ (n >> 1); }

代码实现

  • 二维QAM格雷映射基于这样一种思想: 如果每一维是格雷映射的，那么他们的笛卡尔积也是格雷的。即两个gray mapping 的PAM映射组合起来就是QAM gray mapping.
  • 二维的PSK gray mapping 和一维PAM gray mapping 类似。

点击左侧三角可展开代码

Python 实现 
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
63
64
65
66
67
68
69
70
71
72
73
import numpy as np
def qam_constellation(M,normalize=False):
    """ M must be 2^k ,where k is an even integer
    gray mapping
    param:
        - M: the size of qam set
        - normalize: normalize the average energy qam symbols unit
    return:
        1-D numpy array
    """
    assert np.log2(M).is_integer()
    m = int(np.sqrt(M))
    x = np.zeros(m,np.int32) # gray mapping binding to natural number
    y = np.zeros(m,np.int32) 
    # mappping natural number to gray code in octal
    natural2gray = lambda x: x ^ (x >> 1)
    x[natural2gray(np.arange(0, m))] =  np.arange(0, 2*m,2) -m+1
    y[natural2gray(np.arange(0, m))] =  np.arange(0, 2*m,2) -m+1


    constellation = np.zeros((m, m), dtype=np.cfloat)
    for i in range(m):
        for j in range(m):
            constellation[i][j] = (x[i]+1j* y[j])
    if normalize:
        return constellation.flatten()/(np.linalg.norm(constellation)/m)
    else:
        return constellation.flatten()


def psk_constellation(M):
    """ 
    gray mapping
    param:
        - M: the size of psk set
        - normalize: normalize the average energy qam symbols unit
    return:
        1-D numpy array
    """
    phase = np.arange(0, M) * 2 * np.pi / M
    constellation = np.zeros(M, dtype=np.cfloat)
    natural2gray = lambda x: x ^ (x >> 1)
    constellation[natural2gray(np.arange(0, M))] = np.exp(1j * phase)
    return constellation

def mapping(data, constellation):
    """
    param:
        - data: binary data in 1-D numpy array
        - constellation: 1-D numpy array
    return:
        1-D numpy array
    """
    M = len(constellation)
    assert np.log2(M).is_integer()
    assert len(data) % np.log2(M) == 0
    data = data.reshape(-1, int(np.log2(M)))
    mask = np.array([2**i for i in range(int(np.log2(M))-1, -1, -1)]) # [8,4,2,1]
    index = np.sum(data * mask, axis=1) # left first
    return constellation[index]



if __name__ == "__main__":
    qam_16 = qam_constellation(16)
    psk_4 = psk_constellation(4)
    print(qam_16)
    print(psk_4)
    binary_data = np.random.randint(0, 2, 128)
    psk_symbols = mapping(binary_data, psk_4)
    qam_symbols = mapping(binary_data, qam_16)
    print(psk_symbols)
    print(qam_symbols)

  1. gray code wiki↩︎

  2. 格雷码↩︎