Tanner图

置信传播（BP）算法在Tanner图上进行迭代消息传递，是线性码解码的主流方法，但在某些码型和信道条件下收敛性和解码精度不理想。

Tanner图是描述线性码结构的二分图，一侧是变量节点（对应码字比特），另一侧是校验节点（对应校验方程），当某个比特参与某个校验方程时两者之间连一条边。

BP解码在Tanner图上交替进行变量节点向校验节点发送后验信息和校验节点向变量节点回传校验信息的迭代。

Tanner图的稀疏性决定了BP的计算复杂度，而图中短环（girth）的存在会影响消息的独立性假设，进而造成收敛困难。