汉明码的编码和作用(含编码过程的Python脚本)
最近在调研转录组和亚细胞结构的关系,找到了庄小威老师在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脚本来计算编码
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