《第11章 纠错编码.doc》由会员分享，可在线章 纠错编码.doc（63页珍藏版）》请在点石文库上搜索。
1、第11章 纠错编码本章目录11.1 编码信息传输模型11.2 无差错信息传输原理11.3 纠错编码与译码基本原理11.4 线 线 二元线性卷积码本章内容要点（1） 纠错编码传输模型，信道编码定理，香农限以及编码增益；（2） 码的基本参量，基本编码方法，译码模式和纠错码的应用方式；（3） 典型码例，伴随式、标准阵列、比特翻转译码方法；（4） 循环码，BCH码和RS码；（5） 卷积码，维特比译码，Turbo码。11.1 编码信息传输模型信息的表述 在概率意义上，信息是随机事件，消息是其样本，信息量是样本空间的概率度量。 在数据结构上，样本表述为消息码元组成的数据分组
2、任何信息总可以表述为二元随机序列或随机向量 当的概率分布为均匀分布，则一个具有一个比特信息（信息量单位比特）。 任何二元数据串或向量的一个分量称为一个比特数据（数据个数单位比特）。冗余编码（Coding）与调制（Modulation） 编码（与调制）：数据分组到信号的转换， 或 码字（Codeword）：与离散信号的一对一数据向量，称为编码码元，简称码元（Code Symbol）。 冗余性：无误差信息传输的基本途径图11.1.1 编码在信息传输、数据传输与信号传输中作用常规通信信号基带传输模型 是等效幅度衰落系数，常为参数的瑞利（Rayleigh）分布随机变量，均值，方差。 是等效叠加噪声值
3、常为均值、方差的正态或高斯（Gaussian）分布随机变量。 在时间与频谱特性上，为白噪声过程，功率谱密度值为，故称相应信道为AWGN信道（加性白高斯噪声，Additive White Gaussian Noise）。B-AWGN信道及信噪比 信道描述：输入/传输/输出分别为BPSK信号（幅度）；，白噪声； 传输符号差错概率：对相干硬判决解调，能量， 信噪比：信号平均功率与噪声平均功率之比，由带宽得到，随机差错与突发差错 传输差错：在传输符号层次上，编码信道抽象为符号的概率转移过程，总有差错。 随机差错（Random Error）：符号差错在传输符号序列中均匀分布。通常认为单纯AWGN信道上
4、的差错是随机差错。随机差错的一个必要条件是信道无记忆性或有独立性。 突发差错（Burst Error）：符号差错在传输符号序列中有局部高密度分布（如）。瑞利衰落总会导致突发差错。不同突发密度区间的最大长度称为突发长度。无记忆二元对称信道模型BSC(p)（1/2） BSC（Binary Symmetric Channel）是最简单的硬判决随机差错模型，信道输入，输出，干扰 对BPSK调制和相干解调，称为BSC的信道转移概率 BSC图形模型码元符号图11.1.2 BSC图形模型无记忆二元对称信道模型BSC(p)（2/2） BSC代数与概率模型模二（）加算术运算规则：， 差错图案（Error Pat
5、tern）：，当且仅当传输分组中的第i位符号差错。纠错编码传输特征（1/2） 逻辑上，纠错编码传输的单位是分组或向量或码字，而不是符号或比特。图11.1.4 编码信道的分组传输模型 物理上，对于时间顺序上逐个符号调制与传输，纠错编码传输在物理实现上是逐个符号或波形的传输。 基本分析上，不考虑任何处理延时和信道传输时延。纠错编码传输特征（2/2）记消息比特持续时间，带宽，发送比特能量，有： 总有，且比值称为传输码率。 数据传输时延为。 消息传输总时不变，则传输信号带宽。 消息传输总能量不变，则比特传输能量。 消息传输总时和总能均不变，则有无编码的传输功率不变，即。BSC的常见概率计算对于以及比特
6、的分组：（1） 恰有错概率：（2） 平均错数：信道平均差错率。（3） 错数方差：（4） 差错数越少的图案出现概率越大，分组编码与分组码 分组编码（映射）：以某种约束关系而成逻辑整体，并称为码字，为码元。 元分组码（Block Code）或： 个相同约束关系的码字且(符号集)，称为码长 元分组码：且为整数，称为消息（位）长，称为校验（位）长。 编码码率（Code Rate，码率）：平均每个码元等效传输的消息符号数，例11.1 二元n-重复码 构造方法：每个码字的码元都是同一个码元的次重复。 3-重复码例：在长为3的8个不同二元向量中选择向量集合构成的分组码，并有：， 编码与调制对应：用3-重复码
7、和BPSK调制传输1个比特消息数据的对应关系为，例11.2 四元重复码 构造：四元2-重复码是一个 ， 码率：四元2-重复码的每个码元平均传输的消息比特数为比特，一个码字传输的消息比特数为比特。 直接调制：由于比特，所以四元码的逐个符号调制是四元调制，如QPSK。例11.3 二元等比码 构造：5元组中恒定有3个分量为1；二元等比码有； 常用于传输10进制数字符号，码率为 由于不是整数值，所以不存在整数值的消息位长和冗余位长。11.2 无差错信息传输原理信道容量 信道容量：信道上符号信息传输的最大速率（计量单位为比特/符号）。BSC(p) ：AWGN样点信道：B-AWGN符号信道：AWGN波形信
8、道： （比特/秒）信道容量特征 是通过调整信源符号的概率分布达到。 是AWGN信道在信道输入幅度值呈高斯分布条件下获得的，仅作为任意信道的信道容量的理论上限。 符号信道容量与时间波形信道容量的关系为，“比特/秒（）”参量不同物理概念、相同“比特/秒（）计量单位”参量除信道容量外，还有： 发信率（或信源速率）：单位时间内信源发送出的表示信息的消息比特数。 传输率（或信道速率）：单位时间内信道传输的二元符号（比特）数。 传信率（或信息速率）（Information Rate）：单位时间内信道传输的信息量。 “比特/秒（）”参量间关系 一个信道应有。 不考虑同步以及帧开销时，。 信道容量计算并不区分
9、比特差错是消息比特差错还是冗余比特差错，所以为互信息量，为折算等价BSC信道容量。 无损失信息传输：数据传输的差错特性（1/2）信息本身的传输减损只能通过对表示信息的消息数据的差错统计特性间接描述。（1）信道误码率（传输误码率）：传输中等效的二元符号的差错数与等效的总发送二元符号数的比值。对均匀信源和BPSK，。（2）信息误码率（消息比特误码率）：传输中的差错消息比特数与总发送消息比特数的比值。与具体编码译码方式有关，在译码门限之上有。无纠错编码时，。数据传输的差错特性（2/2）（3）信息减损率：传输中减损的信息量与总发送信息量的比值。由总传输时间和，例11.4 信息减损率与传信率的计算与分析
11、传信率并不能由所确定的消息比特差错比例直接获得。只表明100个消息比特传输中平均有5个消息比特差错，对无冗余的，传信率并非等于。（4）统计意义上可大于，但传信意义上总小于等于，大于实际表明一半以上的信息传输减损。例11.5 n-重复码的差错概率计算与分析择多判决准则译码的消息比特差错概率（1）并有，传信率。（2）虽然可有，但总有，。n-重复码不能获得意义上的有效信息传输。无损失信息传输的可能与不可能 不可能实现由传输符号能量而使并进而。 不可能由不恰当的编码获得有效的无信息损失传输，且。 无损失信息传输可能性？香农（Shannon）信道编码定理！最小差错概率译码（1/2）记表示接收向量，译码输
12、出码字为，则码字译码差错概率最小当且仅当后验概率最大运用贝叶斯准则得最大后验概率译码准则称为发送收到的似然值。如果为常数，得最大似然（ML）译码准则最小差错概率译码（2/2）离散信道上，与的差异由两向量间不同分量的个数（汉明距离）确定。对于BSC有，至此最大似然译码准则简化为汉明距离意义上的最小距离（MD）译码准则，即定理11.2.1（香农信道编码定理）对q元信道，若容量为（比特/符号），则存在一种的分组码，在时，按最大似然译码的。反之，若，则不存在任何条件下的分组码可使。 。 。 可有且（）。 不是构造性定理，至少不能依此衡量不同码的极限（或）性能。通信的极限目标、基本资源与评估指标 通信的
13、极限目标是消息比特差错概率趋于0。 通信的基本开销或基本资源是时间，频率和能量。 通信的基本评估指标是信息比特谱效率和香农限（Shannon Limit）两个极限参量信息比特谱效率 信息传输的信息比特谱效率是单位时间单位带宽上传输的信息比特数，即 （比特/秒.赫兹） 值越小，系统的开销或代价越大或耗用通信资源的效率越低。 信息传输效率而非消息或数据传输效率的归一化衡量参量。香农限香农限是传输一个信息比特所需的最小（功率）信噪比。记传输一个符号比特的能量为，则传输一个消息比特的等效能量为，显然消耗100的能量并不表示无差错传输了100个信息比特，于是记为无差错传输一个信息比特的能量，那么信息比特
14、谱效率与香农限的关系 由得信息比特信噪比与信息比特谱效率的关系为 狭义香农限：任何系统传输一个信息比特所需信噪比的最小值，能量带宽效率平面 由参量对界定的二维平面可达区域不可达区域0.693系统A系统B系统C1图11.2.1 编码信息传输系统的能量带宽效率平面BSC-相干BPSK信道的香农限当码率时的香农限为，B-AWGN-BPSK理想软判决信道的香农限（1/2）其中。B-AWGN信道与之间的数值关系，见表11.2.2。B-AWGN-BPSK理想软判决信道的香农限（2/2）表11.2.2 B-AWGN的0.010.050.100.150.200.250.300.350.4
17、0042（9.033dB）8.0006（9.031dB）8.0481（9.057 dB）例11.6 n-重复码的效率分析（5/5）（1） 传输比特能量可小于香农限，但等价总大于香农限。例如-10dB（2） 不恰当的编码反会导致性能恶化。例如5-重复码性能劣于无编码性能，3-重复码性能优于无编码性能，（3） 纠错码需在信噪比大于译码阈值时显现性能改善特性。不同的纠错码存在不同的译码门限值。（4） 单纯增加重复码码长不能改善性能。例11.7 Turbo码和低密度校验码LDPC码由C. Berrou等人于1993年提出的一种8状态码率码长为5000的Turbo码在采用8至10次迭代译码的条件下，可以
18、在dB时实现，而码率的香农限为-0.51dB。Sae-Young Chung等四人在2001年发现并计算机仿真验证了一种码率的LDPC码在码长达到时，实现，离香农限仅有。编码增益编码增益是相同时，两个信息传输系统的的比值 能量差错概率平面（1/3） 与所确定的二维平面。 信息比特谱效率以及香农限不能有效分析容忍一定差错时的极限特性。 分析系统实际至香农限的距离更有意义。 具有“瀑布”曲线所示。 应当与有单调关系，存在常数使得满足，能量差错概率平面（2/3）能量差错概率平面（3/3）（1）编码系统由于编码后等效的码元符号能量降低而存在门限现象。门限值取决于码的结构和具体的译
20、ing Weight）：若存在可定义为0的零码元，则 汉明距离（Hamming Distance）： 最小码距（Minimum Code Distance）：具有最小码距的或分组码记为或分组码。纠错码基本结构特征间的简单关系 符号集上的加法与减法推广到向量的加法和减法， 因必然使的汉明重量加1，从而 记全零向量为，并有以及在时，则例11.8 汉明距离和汉明重量计算例纠错码设计第一目标 纠错码设计第一目标（纠错力最大）：给定和， 最大，即 辛格里顿限（Singleton Bound）： 最大距离可分码（MDS Code, Maximum Distance Separable Code）：达到辛格
21、里顿限的码，如RS（Reed-Solomon）码。纠错码设计第二目标（1/2） 纠错码设计第二目标（传信率最大）：给定和， 最大，即 最优码（Optimal Code）：给定和，最大。 球填充问题：n维空间中填充最多个半径为的互不交叠的汉明球。 汉明限（Hamming Bound）：,，纠错码设计第二目标（2/2） 完备码（Perfect Code）：达到汉明限的码。 完备码的码结构效率最高，且有两个重要特性：（1）d为奇数，即；（2）达到汉明限，即。 全部完备码是：汉明码；二元或三元葛莱码（Golay Codes）；奇数码长重复码。例11.9 二元-重复码。例11.10 传输2比特信息的几种
22、码构造（1/4）（1）随机选择码，（2）每两位消息比特重复一次，传输2比特信息的几种码构造（2/4）（3）选择个（恰仅有个）重量等于的元组（获得一个3/4等比码），传输2比特信息的几种码构造（3/4）（4）四元4-重复码， ， 传输2比特信息的几种码构造（4/4）（5）一种三元码选择， 检错译码的基本原理 检错译码：利用码的结构特性判断接收向量是否是码字。 实现检错译码前提：发收具有完全相同码。 检错译码适用于硬判决信道，即DMC信道。 检错译码基本准则：，则判断存在传输差错。 检错码：专用于检错的纠错码。 检错码设计目标：不可检差错概率最小，即使所有最可能出现的差错图案均不能导致任意码字。检
23、错译码的基本方法（1/3）例11.11 n-重复码用于检错时的全0/1判断法。表11.3.1 3-重复码检错译码操作表0？111无错有错有错有错有错有错有错无错记接收向量为，利用全0/1判决方法对n-重复码的一般性检错方法为：若，则有错；否则无错。检错译码的基本方法（2/3）例11.12 二元偶或奇校验法 偶校验编码：k长消息组扩展为长的码组，总使码组中1码元的个数为偶数或零，新增码元为偶校验位。 偶校验码结构参数：， ， ， 4,3偶校验码见表11.3.2所示。表11.3.2 4,3偶校验码编码表消息10111
24、0111码字11检错译码的基本方法（3/3） 偶校验码的检错译码方法：若接收分组中1的个数为偶数或零（称偶校验有效），则认为该码字传输无错，否则有错，即若偶数或零，则无错；否则有错。 偶校验码的偶校验是否有效方法对所有奇数个码元的差错检测做出正确判断。纠错译码的基本原理 纠错译码：利用码的结构特性，首先判断接收向量中传输差错符号的位置，然后计算差错符号的差错值，最后修正差错符号。 实现纠错译码前提之一：发送方和接收方具有完全相同的码。 实现纠错译码前提之二：差错图案重量越小其出现概率越大。 纠错译码既适用于硬判决信道，也适用于软判决信
25、道。纠错译码的基本方法（1/4）例11.13 择多判决法 择多判决法适用于对重复码的纠错译码。 一个分组中两个比特错误的概率小于一个比特错误的概率；3-重复码的纠错操作见表11.3.3和图11.3.1。表11.3.3 3-重复码纠错译码操作表译码状态010111正确译码正确译码正确译码错误译码错误译码正确译码正确译码正确译码纠错译码的基本方法（2/4）图11.3.1 纠1位差错的3-重复码纠错译码的基本方法（3/4） n-重复码的择
26、大判决译码操作以汉明重量检测描述为： n-重复码的译码操作以汉明距离描述为：纠错译码的基本方法（4/4）例11.14 阵列偶校验法 二维9,4偶校验阵列码：分别是第1，2行的偶校验码元，分别是第1，2列的偶校验码元，是第3行或第3列的偶校验码元。 任意1位错误一定在某特定行和某特定列上同时导致偶校验失效，从而由二维坐标体系确定此码元错误位置。纠错译码模式（1/5） 译码模式或译码器工作模式：译码器对接收分组进行纠检错的处理方式。 译码模式分检错、纠错和混合纠检错三类。（1）检错模式对任意只并给出有无传输差错的标志或者输出，其中纠错译码模式（2/5）（2）纠错模式 对任意总输出码字，即。 译码正
27、确指；译码错误指。 最小距离纠错译码准则，纠错译码模式（3/5）（3）混合纠检错模式或限定距离译码模式 对任意或者输出码字或者输出预设向量或输出，即对于某个预定的不可译向量集合，纠错译码模式（4/5） 译码成功指；译码成功中，译码正确指，译码错误指。 译码失败指。 限定距离的最小距离混合纠检错译码准则为，纠错译码模式（5/5）混合纠检错译码并非是先纠错译码后又检错译码或者先检错译码后又纠错译码，译码器只能在三种译码模式的某一种模式下工作。图11.3.2 译码正确（），译码错误（）与译码失败（）检纠错数定理最大检错数和最大纠错数是可以检测或纠正任意位置上码元差错的最大数目。定理11.3.1（检纠
28、错数定理）：若分组码有最小码距，那么该码的和满足：（1） 在检错模式时，。（2） 在纠错模式时，。（3） 在混合纠检错模式时，且，即：或纠正个错或检个错，当且仅当。例11.15 6-重复码检纠错数分析 检错模式时的最大检错数为5。纠错模式时的最大纠错数为2。混合纠检错模式时若纠1个错，则可检4个错；若纠2个错，则可检3个错。 注意最大检错数和最大纠错数指码字上任意位置上的差错数目。 一个设计良好的译码算法可以检测超越个差错，也可以纠正超越个差错。 最大检错数和最大纠错数并不能全面反映一个码的检纠错能力，而要用差错概率来全面评估码的检纠错能力。差错控制方式纠错码的基本应用方式：FEC、ARQ、I
29、RQ三类。图11.3.4 差错控制方式FEC，ARQ与IRQ纠错码基本分类 分组码与卷积码：消息分组与码字的对应关系是一对一与多对一。 循环码与非循环码：码字向量是否具有循环移位不变。 线性码与非线性码：码字集合是否为线性空间。 域上码与非域上码：码元集合是否为有限域。 汉明空间码与非汉明空间码：向量度量是否是汉明距离。 时域码与空域码：时域冗余与空域冗余。常规纠错码均是时域码，空时码是空域码，TCM（Trellis Coded Modulation）码有空间冗余性也有时间冗余性。纠错码的研究范畴 码构造：具体码或某一类码的构造和实现。 码限：码或某一类码的整体性能、极限特性或性能界。 译码：
30、具体码或某一类码的译码方法及其相应的纠检错性能。 码的应用纠错码的发展渊源二十世纪四十年代末两个几乎同期但相互独立的工程性研究工作。 解决噪声中的可靠通信问题：创新性代表成果是香农信道容量分析和编码定理，其随机编码思想促进了数字通信理论以及信号设计与编码的发展和应用。 解决数据存储中少量比特差错纠正问题：创新性代表成果是汉明和葛莱的代数与组合构造码，其数学内涵促使了“纠错码”作为一个数学分支的诞生和发展。11.4 线性分组码线性分组码（Linear Block Code）定义 二元线性分组码或：由行秩为k 的生成矩阵（Generator Matrix）确定的有个n长向量构成的集合， 矩阵运算为
31、整数模二加和整数模二乘。 群码：线性分组码；群和线） 全零向量一定是码字，即。 对有。 。 不唯一。的任意行初等变换生成相同的码，并称为行初等变换等价码。线） 给定n和k，不同（不等价）二元线性分组码的个数为， 编码影射为布尔逻辑方程组，线性分组码的系统码形式 系统码：某k个码字码元与k个消息码元恒等， 标准形系统码（仍记）：，为单位阵 任何线性分组码均可由行初等变换转换为系统码，但并非都可等价为标准形系统码。 系统码或标准形系统码与原码有相同码率和最小码距。 行等价可以有，但不一定有。线性分组码的编码方程组与校验方程组（1/2） 标
32、准系统码编码方程组，线性分组码的编码方程组与校验方程组（2/2） 校验方程组由标准系统码编码方程组中后r个方程构成，线性分组码的校验矩阵校验方程组矩阵形式，称为线性分组码的一致校验矩阵，简称校验矩阵。线性分组码的基本特性再分析 向量是码字当且仅当，故 校验矩阵与生成矩阵满足，其中和分别为和的任意行初等变换。 校验矩阵的行秩等于r。 对于系统码 对偶码，且。线性分组码最小码距判定定理（1/2）一个较易确定最小码距的方法。 定理11.4.1（最小码距判别定理）：等于校验矩阵的最小线性相关的列数。线性分组码最小码距判定定理（2/2） 推论1：当且仅当中任意列线性无关，某列线、及其生成矩阵的列置换不改变码的最小距离。 注意：并不等于矩阵的(列)秩（的最大线性无关列数或某列无关但任意列相关）。 推论3（辛格里顿，Singleton，限）：任意线）偶校验码， ， 简单码例（2/4）例11.18 2元码 该码无全零向量为码字，不构成群，所以不是线性分组码，不存在生成矩阵描述。 该码不可能构成系统码。 该码。简单码例（3/4）例11.19 一个线性分组码， ， 到行初等变换：（表示第行）。 。由于的第1列和第5列相同而线续 不同生成矩阵构造的码字和对偶码的码字
34、见下表。表11.4.1 线性分组码生成码字生成码字对偶码的码字0011汉明码（1/8） 汉明（Richard W. Hamming）1950年首次发现的一类纠正单个错误的线性分组码。 二元m阶汉明码：校验阵是以全部二元非零m维向量为列向量的矩阵 二元m阶汉明码的基本特性有： ，正整数。 。 ，。 是完备码，即，汉明码（2/8）二元码基本特性续 满足如下递归关
35、系： 记为重量i的码字的个数，则二元汉明码的重量分布多项式为，汉明码（3/8）二元码基本特性续 在汉明码的一致校验矩阵构造中，每一种不同的非零列向量的排列顺序或者对已有的任意列初等置换，均获得不同形式的校验矩阵。 不同形式的所定义的码在编码映射意义上虽然不同，但是它们都具有相同的上述汉明码的基本特性，称为是在码结构参数意义上等价的汉明码。 存在满足汉明码前三个基本特性的却不等价为汉明码的非线 二元汉明码的两种等价的校验矩阵分别为，汉明码（5/8）例11.21 二元汉明码可以推广到多元汉明码。例如一个三元3阶汉明码的一致校验矩阵为，汉明码（6/8）例11.22 二元3阶
，表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
