LDPC的比特翻转算法与和积译码算法的python实现
- LDPC码简介
LDPC码即低密度奇偶校验码（Low Density Parity Check Code，LDPC），它由Robert G.Gallager博士于1963年提出的一类具有稀疏校验矩阵的线性分组码，不仅有逼近Shannon限的良好性能，而且译码复杂度较低, 结构灵活，是近年信道编码领域的研究热点，已广泛应用于深空通信、光纤通信、卫星数字视频和音频广播等领域。
LDPC码的校验矩阵只含有很少量非零元素，因此称为“低密度”奇偶校验码。LDPC码的译码方法和经典分组码不同，由于其码长较长，所以通常通过其校验矩阵的图像表达进行迭代译码。
- LDPC码编码原理
LDPC码的编码原理是将信息位按照一定的规则与校验位进行组合，形成一个码字。LDPC码的编码过程是将信息位按照一定的规则与校验位进行组合，形成一个码字。LDPC码的校验矩阵只含有很少量非零元素，因此称为“低密度”奇偶校验码。LDPC码的译码方法和经典分组码不同，由于其码长较长，所以通常通过其校验矩阵的图像表达进行迭代译码。以下是一个LDPC编码的例子。
A = np.array([[1,1,1,0],[0,1,1,1],[1,0,1,1]])
H = np.concatenate((A,np.eye(3)),axis=1)#校验矩阵
G = np.concatenate((np.eye(4),A.T),axis=1)#生成矩阵
Kdec = np.random.randint(0, 256,size=(1024))#产生随机符号
Kbin = np.array([int(_) for _ in ''.join(vec_dec2bin(Kdec))])
KbinRe = Kbin.reshape(-1, 4)
encoded = np.mod(np.matmul(KbinRe, G), 2)#经过LDPC编码后的比特- LDPC码译码原理
LDPC码的译码原理是基于迭代译码的思想，通过迭代计算来逐步减小误码率。LDPC码的译码过程是将接收到的码字与校验矩阵进行乘积运算，得到一个校验方程组。然后，利用迭代算法对这个方程组进行求解，得到一个估计值。如果估计值与接收到的码字不同，则将估计值作为新的输入，重新进行迭代。
- LDPC码比特翻转译码原理
LDPC码的比特翻转译码原理是指，当硬解调之后的比特信息不满足校验方程组时，统计所有比特不满足校验方程的个数，并翻转不满足个数最多的比特值，用更新之后的码组再次译码，直至所有校验方程均得到满足或者达到迭代次数的上限。以下代码可以实现比特翻转的功能。
def match_cols(H, C):
#在H中匹配C校验和，返回匹配到的列数，该列对应需要翻转的比特
H_tmp = np.hstack((H,np.zeros((H.shape[0],1))))*2-1
C_tmp = C*2-1
maxMat = np.matmul(C_tmp, H_tmp)
flip = np.argmax(maxMat,axis=1)
return flip
def flip_function(flip, modulatedRe):
#根据翻转位进行翻转
flip_mask = flip!=max(flip)
flip_mask = flip_mask.squeeze()
modulatedRe[flip_mask,flip[flip_mask].squeeze()] = np.logical_not(modulatedRe[flip_mask,flip[flip_mask].squeeze()])
return modulatedRe
#比特翻转算法
def bitFlip(received, H):
#received: 接收信号
#H：校验矩阵
demodulated = np.array(received>0)
demodulatedRe = demodulated.reshape(-1, H.shape[1])
checkSum = np.mod(np.matmul(demodulatedRe, H.T), 2)#m,3
flip = match_cols(H, checkSum)
decoded = flip_function(flip, demodulatedRe.copy())
return decoded.flatten()
- LDPC码和积译码原理
LDPC码和积译码算法是一种前向纠错码的译码算法。LDPC码采用迭代译码，校验矩阵H使用Tanner图表示，围绕校验矩阵H的特性进行设计，本身的结构引入了交织(interleaving)。和积译码算法是一种软判决译码方法，将概率域BP算法中的乘法运算转换为加法运算，大大降低了运算量。步骤如下：
初始化Lvj→ci=Cvj(1)；
校验节点更新mci→vj=2×atanh(∏vb∈N(ci)\\vjtanh(2Lvb→ci))(2)；
变量节点更新Lvj→ci=∑ca∈N(vj)\\cimca→vj+Cvj(3)；
后验概率信息更新Lj=∑ca∈N(vj)mca→vj+Cvj(4).
以下代码实现和积译码的功能。
#初始化概率
def pfunction(received, sigma=1):
return 1/(1+np.exp(2*received/sigma**2))
#校验节点更新
def check2bit(qNeg, H_mask):
shape = qNeg.shape# 3,7
rPos,rNeg = np.zeros(shape),np.zeros(shape)
qTmp = qNeg[H_mask].reshape(shape[0],4) #4为列重
qTmp = 1-2*qTmp
colProduct = np.product(qTmp, axis=1)
rTmpPos = 0.5+0.5*np.divide(np.full(qTmp.shape, colProduct.reshape(shape[0],1)),qTmp)#
rTmpNeg = 1-rTmpPos
rPos[H_mask] = rTmpPos.flatten()
rNeg[H_mask] = rTmpNeg.flatten()
return rPos, rNeg
#比特节点更新
def bit2check(rPos, receivedPzero, neg=False):
rPosMask = rPos == 0
rPos[rPosMask] = 1
rowProductPos = np.product(rPos,axis=0)
rPostmp = np.divide(np.full(rPos.shape, rowProductPos), rPos)
rPos[rPosMask] = 0
rPostmp[rPosMask] = 0
if not neg:
qPostmp2 = np.multiply(1-receivedPzero, rPostmp)
else:
qPostmp2 = np.multiply(receivedPzero, rPostmp)
return rowProductPos, qPostmp2
#和积译码算法
def sumProduct(received, H, sigma, maxiter=10):
#initial
decoded = np.zeros(received.shape[1])
receivedP = pfunction(received,sigma)
receivedP = receivedP.reshape(-1, H.shape[1])
#循环words
for j in range(len(receivedP)):
receivedPzero = receivedP[j]
qNeg = np.multiply(receivedPzero,H) #3,7
#Pass information from check nodes to bit nodes
H_mask= H!= 0
k = np.zeros(qNeg.shape)
for _ in range(maxiter):
rPos, rNeg = check2bit(qNeg,H_mask)
# bit nodes to check nodes
rowProductPos, qPostmp2 = bit2check(rPos, receivedPzero)
rowProductNeg, qNegtmp2 = bit2check(rNeg, receivedPzero, neg=True)
k[H_mask] = np.divide(1,qPostmp2[H_mask]+qNegtmp2[H_mask])
qNeg = np.multiply(k,qNegtmp2)
QtmpPos = np.multiply(1-receivedPzero, rowProductPos)
QtmpNeg = np.multiply(receivedPzero, rowProductNeg)
K = np.divide(1,QtmpPos+QtmpNeg)
QPos = np.multiply(K,QtmpPos)
decoded[j*H.shape[1]:j*H.shape[1]+H.shape[1]] = QPos>0.5
return decoded
- LDPC码仿真结果
LDPC码可广泛应用于第四代移动通信系统、深空通信、光纤通信、卫星通信、电缆调制解调器、高速与甚高速率数字用户线（Digital Subscriber Line，DSL）、光和磁记录系统等。这是因为LDPC码的错误校正能力非常接近理论最大值（即香农极限）。
附上一张仿真结果。
最后附上完整代码（可免费下载），欢迎小伙伴们下载下来玩耍。