汉明码的编码和作用（含编码过程的Python脚本）

卢旺收录于类别生物信息和系列 Python Scripts

2023-04-22 2023-04-22 约 657 字预计阅读 2 分钟

最近在调研转录组和亚细胞结构的关系，找到了庄小威老师在2015年的一篇Science文章，其使用汉明编码，通过多轮荧光标记拍摄来定位RNA在亚细胞结构中的位置（ultiplexed errorrobust FISH，MERFISH），十分有趣。这里简单探究了下汉明码的编码和作用。

Chen, K. H., Boettiger, A. N., Moffitt, J. R., Wang, S. & Zhuang, X. Spatially resolved, highly multiplexed RNA profiling in single cells. Science 348, aaa6090 (2015).

汉明码编码过程

利用海明不等式计算海明校验码所需要的位数

$$2^r \ge k+r+1$$

其中，r表示校验位的长度，k表示数据位的长度
校验位只能出现在 1 2 4 8…（ $2^N$ ）的位置

例如PPDPDDDPDD，P表示校验位，D表示数据位
校验位的计算
- 确定每一个校验位与哪些数据位进行异或运算（对应的二进制位为1的数据位）
- 令其异或运算的结果为0，求解校验位（这里可以反向计算）
得出最后的海明码

汉明码的功能

在出现1位错误时，海明码可以用来检错和纠错（纠正单比特错误）
- 将海明码校验位及其二进制位对应的数据位进行异或运算，得出结果
- 将从右到左的校验位结果排列，得出的二进制数字，即为发生错误的位置
在出现2位错误时，海明码可以用来检错（发现双比特错误）

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


from math import log
xor = lambda a,b: 0 if a==b else 1

def getHammingCRC(i,x):
    N = int(log(i,2))+1
    r = []
    res = 0
    for i in range(1, len(x)+1):
        if str.zfill(bin(i)[2:], N)[-N] == '1':
            r.append(x[i-1])
    for i in r[1:]:
        res = xor(res,int(i))
    return '0' if res == 0 else '1'

def hammingcode(x):
    r = 0
    while 2**r - r < len(x)+1:
        r+=1
    hs = [2**i for i in range(r)]
    l = len(x) + r
    res = []
    j = 0
    for i in range(1,l+1):
        if i in hs:
            res.append(' ')
        else:
            res.append(x[j])
            j += 1
    for i in range(1,l+1):
        if i in hs:
            res[i-1] = getHammingCRC(i,''.join(res))
    return ''.join(res)

调用hammingcode('101101')，即可得到编码后的结果0010011101