??d?H(v,ci)?tei?1,2,,M?c??ci??dH(v,ci)?tei?1,2,,M?s?1
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ 纠错译码模式（5/5）
混合纠检错译码并非是先纠错译码后又检错译码或者
先检错译码后又纠错译码，译码器只能在三种译码模式的某一种模式下工作。
图11.3.2 译码正确（vc），译码错误（ve）与译码失败（vf） ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
检纠错数定理
最大检错数td和最大纠错数tc是可以检测或纠正任意
位置上码元差错的最大数目。
定理11.3.1（检纠错数定理）：若分组码有最小码距d，那么该码的td和tc满足：
（1） 在检错模式时，td?d?1。 （2） 在纠错模式时，tc??(d?1)2?。
（3） 在混合纠检错模式时，tc?td?d?1且tc?td，即：或纠正tc个错或检tc?1, tc?2,,tc?t??td个错，
当且仅当d?2tc?t?。
例11.15 6-重复码检纠错数分析
? 检错模式时的最大检错数为5。纠错模式时的最大纠错
数为2。混合纠检错模式时若纠1个错，则可检4个错；若纠2个错，则可检3个错。 ? 注意最大检错数和最大纠错数指码字上任意位置上的
差错数目。 ? 一个设计良好的译码算法可以检测超越td个差错，也可
以纠正超越tc个差错。
? 最大检错数和最大纠错数并不能全面反映一个码的检
纠错能力，而要用差错概率来全面评估码的检纠错能力。 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
差错控制方式
纠错码的基本应用方式：FEC、ARQ、IRQ三类。
4-21
图11.3.4 差错控制方式FEC，ARQ与IRQ
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
纠错码基本分类
? 分组码与卷积码：消息分组与码字的对应关系是一对一
与多对一。 ? 循环码与非循环码：码字向量是否具有循环移位不变。 ? 线性码与非线性码：码字集合是否为线性空间。 ? 域上码与非域上码：码元集合是否为有限域。 ? 汉明空间码与非汉明空间码：向量度量是否是汉明距
离。 ? 时域码与空域码：时域冗余与空域冗余。常规纠错码均
是时域码，空时码是空域码，TCM（Trellis Coded Modulation）码有空间冗余性也有时间冗余性。 纠错码的研究范畴
? 码构造：具体码或某一类码的构造和实现。
? 码限：码或某一类码的整体性能、极限特性或性能界。 ? 译码：具体码或某一类码的译码方法及其相应的纠检错
性能。 ? 码的应用
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
纠错码的发展渊源
二十世纪四十年代末两个几乎同期但相互独立的工程性研究工作。
? 解决噪声中的可靠通信问题：创新性代表成果是香农信
道容量分析和编码定理，其随机编码思想促进了数字通信理论以及信号设计与编码的发展和应用。 ? 解决数据存储中少量比特差错纠正问题：创新性代表成
果是汉明和葛莱的代数与组合构造码，其数学内涵促使了“纠错码”作为一个数学分支的诞生和发展。 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
11.4 线性分组码
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
线性分组码（Linear Block Code）定义
? 二元(n,k)线性分组码C(n,k)或C：由行秩为k 的
11-22
k?n生成矩阵（Generator Matrix）G确定的有M?2k个n长向量构成的集合，
C???c0,,cn?1?? ??cc?u?G; u?(u,u
0,k?1); uj?0,1??g?g0??g0,00,n?1?G?????? ?g??k-1??gk?1,0g?k?1,n?1?? 矩阵运算为整数模二加和整数模二乘。 ? 群码：线性分组码；群和线性子空间。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
线性分组码基本特性（1/2）
? 全零向量一定是码字，即θ?C。
? 对c,c??C有c?c???c0?c?0,,cn?1?cn??1??C。 ? d?c?minθ, c?C?wH(c)?。
?
G不唯一。G的任意行初等变换生成相同的码，并称
为行初等变换等价码。 线性分组码基本特性（2/2）
? 给定n和k，不同（不等价）二元线性分组码的个数为
N?n,k?，
N?n,k??(2n?1)(2n?1?1)(2n?k?1?1)(2k?1)(2k?1?1)(2?1)
?N?n?1,k??2n?kN?n?1,k?1?? 编码影射c?u?G为布尔逻辑方程组，
??c0??0(u0,,uk?1)? ??cn?1??n?1(u0,,uk?1)＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
线性分组码的系统码形式
? 系统码CS：某k个码字码元与k个消息码元恒等，
cij?uj, j?0,1,,k?1, ij??0,1,,n?1?
? 标准形系统码CNS（仍记CS）：G?GS，
GS??IkQk?r?k?n，GS??Qk?rIk?k?n，Ik为单位阵
? 任何线性分组码均可由行初等变换转换为系统码，但并
非都可等价为标准形系统码。 ? 系统码或标准形系统码与原码有相同码率和最小码距。 ? 行等价可以有C?CS，但不一定有uG?uGS。 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
线性分组码的编码方程组与校验方程组（1/2）
? 标准系统码编码方程组，
4-23
?cj?uj?c???(u,,u)j?k0k?1?j
?cj?uj, j?0,1,,k?1???cj???j?k(c0,,ck?1), j?k,k?1,,n?1＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
线性分组码的编码方程组与校验方程组（2/2） ? 校验方程组??i???由标准系统码编码方程组中后r个方
程构成，
??j?k(c0,,ck?1)?cj?0???j??k(c0,,ck?1,ck,,cn?1)?0, j?k,k?1,,n?1
hc??h0,n?1cn?1?0??0,00?? ??hr?1,0c0??hr?1,n?1cn?1?0＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
线性分组码的校验矩阵 校验方程组??i???矩阵形式，
cHT??c0,,cn?1?HT?(0,r,0)?θ(r), ?c?C
?h0??h0,0???H???h??h?r?1??r?1,0矩阵。
h0,n?1????h? ??i,j?r?nhr?1,n?1?H称为(n,k)线性分组码C的一致校验矩阵，简称校验
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
线性分组码的基本特性再分析
T(r)? 向量v是码字当且仅当v?H?θ，故
C?vv?HT?θ(r); v??v0,? 校验矩阵H与生成矩阵G满足
?,vn?1?; vj?0,1
T?G?HT??0?k?r，G???H????0?k?n
其中G?和H?分别为G和H的任意行初等变换。 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ ? 校验矩阵H的行秩等于r。 ? 对于系统码
THS????Qk?r?Ir??GS??IkQk?r?k?n
????? C?n,k?对偶码C?C?n,n?k?，且G?H。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
线性分组码最小码距判定定理（1/2）
一个较易确定最小码距dmin?d的方法。
d等于校验矩阵H的? 定理11.4.1（最小码距判别定理）：
11-24
最小线性相关的列数。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
线性分组码最小码距判定定理（2/2）
? 推论1：dmin?d当且仅当H中任意d?1列线性无关，
某d列线性相关。
? 推论2：校验矩阵及其生成矩阵的列置换不改变码的最
小距离。 ? 注意：dmin?d并不等于矩阵H的(列)秩r（H的最大
线性无关列数r或某r列无关但任意r?1列相关）。 ? 推论3（辛格里顿，Singleton，限）：任意?n,k?线性分
组码有
dmin?r?1?n?k?1
简单码例（1/4） 例11.16 4-重复码
??1001?G?1111?, H???0101?， dmin?4
?0011??例11.17 （4,3）偶校验码
??c0?u0??c1?u1， G???10010101??, H??1111?， ?c2?u2??c3?u0?u??0011??1?u2d?2
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
简单码例（2/4）
例11.18 2元?n,k???4,2?码
C?{(0111),(1110),(1101),(1011)}
? 该码无全零向量为码字，不构成群，所以不是线性分组
码，不存在生成矩阵描述。 ? 该码不可能构成系统码。 ? 该码dmin?minc?c??dH(c,c?)??2。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
简单码例（3/4）
例11.19 一个(5,3)线性分组码
?10110??10001?G???00??01011?， G111?11010?S????01011?， H?00111?S????11101?? ? G到GS
行初等变换：
R3?R3?R2;R1?R1?R3;R1?R3（Ri表示第i行）。
4-25