例11.24 一个?10,2,4?规则LDPC码。
?110H=?10110010000?010??0000001101001100010010?00111000?11? 1??校验节点z1z2z3z4z5x1x2x3x4x5x6x7x8x9x10消息节点 线性分组码伴随式译码（1/2）
? 接收向量或接收序列v
v?(v0,,vn?1)?(c0,,cn?1)?(e0,,en?1)?c?e
?
v是码字当且仅当v?HT?θ。
? 伴随式向量或伴随式：s?v?HT, v?V ? s仅与差错图案相关
s?v?HT?c?HT?e?HT?θ?e?HT?e?HT?Vr(Fq)
? 伴随式检错译码准则：
??若s?θ，则一定存在差错?若s?θ，则无传输差错或差错图案恰为某个码字 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
线性分组码伴随式译码（2/2）
? 伴随式译码表?(s,e)?：伴随式与差错图案之间的一对
一对应。
? 伴随式纠错译码算法：
（1）构造?(s,e)?：选择最大概率e；计算s?eHT；存储表?(s,e)?。
（2）计算伴随式：s?v?HT。
（3）查表纠错：查表获取e??(?s,e)?s；纠错c??v?e?。 ? 不同伴随式的数目为?s??2r，汉明限约束有，
t?t2rc??n t?0?t?＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
线性分组码标准阵列（Standard Array）译码 （1/3）
表11.4.2 标准阵列
e1 a11?e1?c1 a1j?e1?cj a1,2k?e1?c2k
4-31
ei ai1?ei?c1 aij?ei?cj a2r,j?e2r?cj ai,2k?ei?c2k a2r,2k?e2r?c2k er a2r,1?e2r?c1 2＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
线性分组码标准阵列（Standard Array）译码（2/3）
记Ai?aij1?j?2准正列译码准则为：
（1） 检错译码：若v?A1，则有传输差错。
?k?，B??ajij1?i?2r，则标
???cj。 （2） 完备译码：若v?Bj，则z?c（3） 限定距离译码：若v?Bj? mi?1Ai，则
???cj，否则z??v,s?。 z?c线性分组码标准阵列（Standard Array）译码（3/3）
cj cj e …… v e …… v v 完备译码
限定距离译码
图11.4.5 标准阵列纠错译码
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
??cj，译码失败限定距离译码中，译码成功z?c，或者z??v,s?，选择m使2m??0?t?tnctwH(em)?t?weH(?1。)cm ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
??例11.25 例11.19中的(5,3)线性分组码的译码（1/2）
表11.4.3 伴随式译码表
s e 00 00000 01 00001 10 00010 11 01000 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
例11.19中的(5,3)线性分组码的译码（2/2）
表11.4.4 标准阵列
00000 11010 01011 10001 10110 01100 11101 00111 11-32
00001 11011 01010 10000 10111 01101 11100 00110 00010 11000 01001 10011 10100 01110 11111 00101 01000 10010 00011 11001 11110 00100 10101 01111 此例中，由于单个差错的差错图案不能穷尽所有单个差
错情形，即，2r?22??n1???51??5 因而，单错图案的不同选择可有多种形式，相应的伴随式译码表和标准阵列也有多种形式。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
比特翻转译码原理（1/2）
?
H的第i行hi??hi,0,,hi,n?1?确定一个校验方程
hi,0v0??hi,n?1v?n?1s；ihi,j?1表示接收码元vj参
与第i个校验方程的校验；si,j为有vj参与校验的第i个校验方程的校验值；vj可参与多个校验方程的校验。 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
比特翻转译码原理（2/2）
? 如果vj所参与的全部校验方程的校验中有多数次校验
失败，则vj出错可能性较大。
? 如果vj所参与的全部校验方程的校验中校验失败的次
数是全部接收码元的各自全部校验失败次数之最大，则vj出错可能性最大。 ? 翻转v?(v0,,vn?1)中最可能出错vj，则获得新的测
试“接收向量”v??(v?0,,v?n?1)；m次翻转可能达到无错检验，即s(m)i,j?0。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
单个比特翻转译码算法（1/2）
（1）输入v?(v0,,vn?1)和H???hij??m?n；t?1；
（2）对i?0,,m?1以及j?0,,n?1，计算
si,j?hi,0v0??hi,jvj??hi,n?1vn?1, hi,j?1
（3）若对所有i?0,,m?1和 j?0,,n?1均有
si,j?0，则输出v?(v0,,vn?1)；
（4）t?t?1；
（5）若t?tTH，则输出v?(v0,,vn?1)；
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
单个比特翻转译码算法（2/2） （6）计算vj校验失败的次数zj，
zj??si,jsi,j?1, i?0,,m?1?, j?0,,n?1
4-33
（7）若zl?maxj?0,,n?1?z?，则vjl，?(vl?1)（翻转vl）
vj?vj, j?l；
（8）返回（2）。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
11.5 线性循环码
纠错码的有效构造
? 纠错码的有效构造甚至有效译码总会使码具有更精致
的数学结构。 ? 精致的数学结构带来更多的约束条件：
? 分组特性； ? 线性特性； ? 循环特性； ? 卷积特性； ? ??
? 更多的数学应用。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
二元域与域上多项式
? 二元域（Binary Field）F2：一个仅由整数0和1构成
的集合F2??0,1?，其中集合元素的加法运算和乘法运算分别为模二加法运算和模二乘法运算。
? 二元域上的多项式：多项式系数vi均取自二元域F2的
多项式，
v(x)?vn?1xn?1?vn?2xn?2??v2x2?v1x?v0，vi?F2
? 多项式次数??v?x??max ivi?0,i?0,1,? 首一式：多项式的最高次数项系数为1。
??。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
域上多项式的运算
? 两多项式相加：同幂次项系数相加，
a?x??b?x???a0?b0???a1?b1?x???an?bn?xn
? 两多项式相乘：两多项式系数的卷积，
?a?x?b?x??c?x??c0?c1x??clxl?n?m?i?i? ?a?b ???ji?j? x?i?0?j?0????l???c?x????a?x????b?x??n?m＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
长除法
例11.26 求(x5?x4?x2?x?1)mod(x3?x?1)。
11-34
x2?x?1 x3?x?1x5?x4?x2?x?1
x5?x3?x2 x4?x3?x?1 x4?x2?x x3?x2?1 x3?x?1 x2?x ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ 所以
(x5?x4?x2?x?1)mod?x3?x?1??x2?x
x5?x4?x2?x?1?(x2?x?1)(x3?x?1)?(x2?x) 向量的循环移位 ? 向量v?(v0,v1,,vn?2,vn?1)的1次或j次循环右移移
位变换：
v(1)?(vn?1,v0,v1,,vn?3,vn?2)
??v(j)?(vn?j,,vn?1,v0,v1,,vj,,vn?j?1) j?0,1,2,,n?1 ?? 向量v的j次循环左移等于n?j次循环右移v?(n?j)
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
向量的多项式表示（1/2）
? 向量、向量移位以及多项式表示：
??v?(v0,v1,,vn?2,vn?1)?v(x)?vn?1n?2?v2n?1x?vn?2x?2x?v1x?v ?0?v?1??x??vn?2xn?1?vn?3xn?2??v1x2?v0x?vn?1v?1??x??vn?2xn?1?vn?2n?3x??v1x2?v0x?vn?1 ?x?vn?1n?1x?vn?2xn?2??v1x1?v0? ?x?vn?1
n?1x??vn?1 ?x?v?x??vn?1(xn?1)＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
向量的多项式表示（2/2）
? n维向量的i次循环右移等价为其相应描述多项式的i次升幂后取模为xn?1的模多项式剩余。
由?v(1)(x)?n以及多项式模运算原理有，
4-35