信道编码和纠错编码相关概念

1、2.2.2 信 道 编 码 信道编码和纠错编码相关概念 信源编码(有效性编码) 去除冗余 降低传输速率 信道编码(可靠性编码) 添加冗余 降低差错率：牺牲通信的有效性（信息传输 速率）来提高可靠性 信道编码和纠错编码相关概念 基本概念基本概念 信道编码的目的信道编码的目的 信道编码是为了保证信息传输的可靠性、提高传输质量 而设计的一种编码。它是在信息码中增加一定数量的多余 码元，使码字具有一定的抗干扰能力。 信道编码的实质信道编码的实质 信道编码的实质就是在信息码中增加一定数量的多余码 元（称为监督码元），使它们满足一定的约束关系，这样 由信息码元和监督码元共同组成一个由信道传输的码字。 举例

2、而言，欲传输k位信息，经过编码得到长为n(nk)的 码字，则增加了 n - k = r 位多余码元，我们定义 R = k / n 为编码效率。 信道编码和纠错编码相关概念 分类分类 根据码的规律性可分为：正交编码和检、纠错 码 根据监督元与信息组之间关系可分为：分组码 和卷积码 根据监督元与信息元之间关系可分为：线性码 和非线性码 根据码的功能可分为：检错码和纠错码 信道编码和纠错编码相关概念 信 道 编 码 检 纠 错 码 正 交 编 码 分组码 卷积码 m序列 L序列 非线性码 线性码 恒比码 群计数码 非循环码 循环码 非系统卷积码 系统卷积码 正交码 W-A码 岩垂码 扩散码 奇偶校验

3、码 汉明码 BCH码 RS码 信道编码和纠错编码相关概念 1、分组码、分组码 信道编码和纠错编码相关概念 kkkk kkkk n （1）工作原理）工作原理 图中，n k，Rk/n，称为编码率。 分组码的基本原理是将信息码分成K比特一组，然后将 每组的比特数扩展成n（ n k），也就是说在信息比特 中插入n-k个比特。 另一种看法：将2k矢量空间映射到2n矢量空间。 信道编码和纠错编码相关概念 工作原理（续）工作原理（续） 定义几个参数： 码重：一组二进制码中“1”的个数 码距d：二组二进制码之间“0”或“1”不同的位数 定理： （1）为检查出e个错误，要求：dmin e+1 （2）为纠正t个错

4、误，要求：dmin 2t+1 （3）为纠正t个错误，同时检查出e个错误，要求： dmin e+t+1 （e t） 信道编码和纠错编码相关概念 （2）线性分组码）线性分组码-举例举例 奇偶监督码 汉明码 BCH码 RS码 CRC码 信道编码和纠错编码相关概念 奇偶监督码奇偶监督码 采用奇偶校验原理。 只能检错，不能纠错。 只能检查出某一分组的单个错误或奇数个错误， 而不能发现偶数个错误。 最小码距为2。 水平奇偶监督码 水平垂直奇偶监督码。 信道编码和纠错编码相关概念 汉明汉明码码 （Hamming码）码） 是一种纠正单个错误的线性分组码。 特点：码长 n = 2m-1 信息码位 k = 2n-

5、m-1 监督码位 r = n-k = m 最小码距 d = 3 纠错能力 t = 1 扩展的汉明码：将监督码位由m增至m+1，信息位 不变，这时最小码距增加到d = 4，能纠正1位错误 同时检查出2位错误。 信道编码和纠错编码相关概念 BCH码码 （Bose-Chaudhuri-Hocquenghem码）码） 是线性分组码中循环码的一种重要子类，有严 密的代数结构，是目前研究较多、应用较广的 一种线性分组码。 具有纠正多个随机错误的能力。 根据对纠错能力的要求，选择参数，并根据代 数结构构造编译码算法。 如：n = 7, k = 4, t = 1; n = 15, k = 7, t = 2;

6、n = 31, k = 16, t = 3; n = 127, k = 50, t = 13。 信道编码和纠错编码相关概念 RS码码 （Reed-Solomon码）码） 是一种非二进制的BCH码。即：在（n,k）RS码 中，输入信息被分成km比特一组，每组包括k个 符号，每个符号由m比特组成。 纠正t个符号错误的RS码参数如下： 码长 n = 2m-1符号，或m(2m-1)比特 信息段 k符号，或km比特 监督段 n-k=2t符号，或m(n-k)比特 最小码距 d=2t+1符号，或m(2t+1)比特 信道编码和纠错编码相关概念 CRC码码 （循环冗余校验码）（循环冗余校验码） 是一种循环码，用

7、于检错。 具有很强的检错能力，而且编码器及译码器都很容 易实现。因而在数据通信中得到广泛应用。 可以检测出的错误如下： （1）突发长度n-k的突发错误； （2）大部分突发长度n-k+1的错误； （3）大部分突发长度n-k+1的错误； （4）所有与许用码组的码距dmin-1的错误； （5）所有奇数个随机错误。 信道编码和纠错编码相关概念 线性分组码中的一类重要码，且为系统码 与一般线性分组码相比，循环码还具有循环特性： 若（an-1，an-2，a1，a0)是一(n，k)循环码的码组， 则（an-2，an-3，a1，a0 ，an-1) （an-3，an-4， ， a0 ， an-1 ，an-2)

8、（ a0 ，an-1 ， an-2，an-3，a2，a1) 也都是该循环码的码组 2、 循环码 信道编码和纠错编码相关概念 信道编码和纠错编码相关概念 3、卷积码、卷积码 信道编码和纠错编码相关概念 （1）概述）概述 分组码卷积码 固定窗型滑动窗型 kkkkkkkk nnnnnnnn kkkkkkkk nnnnnnnn 信道编码和纠错编码相关概念 概述（续）概述（续） 例：R1/2卷积码 kk kkkkkk Ik ak bk 信道编码和纠错编码相关概念 （2）编码原理）编码原理 原理图 映射 uj0 uj1 uj,k-1 uj-m,k-1 uj-m,1 uj-m,0 xj0 xj1 xj,n-

9、1 . . . . . . m stage delay 信道编码和纠错编码相关概念 编码原理（续）编码原理（续） 几个例子 + + uj xj0 xj1 uj xj0 xj1 (4) (1) + (2) xj0 xj1 uj + + + xj0 xj1 xj2 uj0 uj1 (3) 返回 信道编码和纠错编码相关概念 编码原理（续）编码原理（续） 卷积码的参数 约束长度N， 输入比特k， 输出比特n， 编码率Rk/n 信道编码和纠错编码相关概念 编码原理（续）编码原理（续） 状态转移图和trellis（交织）图表示 0110 11 00 1；10 1；01 0；01 0；10 1；00 1；1

10、1 0；11 0；00 0/00 1/11 0/000/000/00 1/11 1/111/11 1/01 0/10 1/101/10 0/010/01 1/001/00 0/11 0/11 1/00 0/100/10 00 10 01 11 1/00 信道编码和纠错编码相关概念 （3）译码原理）译码原理-方法分类方法分类 代数译码：纠错译码的经典方法。利用 纠错码的代数结构，经过一定的代数运 算，消除误差，恢复正确的信息。常用 的有：大数译码逻辑。特点：电路简单， 编码增益低。 概率译码：纠错译码的新方法。考虑到 信道的统计特性。常用的有：序列译码、 维特比译码。特点：电路复杂，编码增 益高

11、。 信道编码和纠错编码相关概念 译码原理译码原理-序列译码序列译码 原理：在码树图中每向前走一步，在决定 走哪一个分支时根据该分支子码与该时刻 接收子码之间的相似程度来判断。亦称为 逐分支译码。 一般采用对数似然值度量该相似程度 log P(R|C)=logiP(ri|ci)=ilog(p(ri|ci) 堆栈译码和费诺译码 信道编码和纠错编码相关概念 译码原理译码原理-序列译码（续）序列译码（续） 优点 运算量和约束长度无关。 缺点 运算量和信道质量有关。 没有利用卷积码的记忆特性，不是最优算法。 信道编码和纠错编码相关概念 译码原理译码原理-维特比译码维特比译码 最大后验与最大似然译码 MA

12、P: ML: 硬判决和软判决 硬判决：解调器直接判0，1 软判决：解调器对输出进行量化 )|(maxarg ii S i SrfPS i )|(maxarg i S i SrfS i 信道编码和纠错编码相关概念 译码原理译码原理-维特比译码（续）维特比译码（续） Viterbi译码原理 Viterbi译码是建立在最大似然译码基础上的译 码方法 在译码过程中只需考虑整个路径集合中那些能 使似然函数最大的路径 最大似然序列译码要求序列有限，因此对卷积 码来说，要求能收尾 1 0 )( )( ),(),( mL j i jj i i xrxr 信道编码和纠错编码相关概念 译码原理译码原理-维特比译码

13、（续）维特比译码（续） Viterbi译码举例 设对于编码前信息比特为(0,0,0,0,0,0)的接收序 列为 则硬判结果为 基于软判决时，采用如下路径度量 9 . 0, 2 . 15 . 0 , 2 . 06 . 0, 5 . 03 . 1, 5 . 09 . 0, 1 . 03 . 0 , 1 . 1 r 0 , 01 , 10 , 00 , 00 , 11 , 0 r )1()1( , )0()0( , ),( jpijpipij rxrxxr 信道编码和纠错编码相关概念 译码原理译码原理-维特比译码（续）维特比译码（续） 1 1 1 2 2 3 2 1 3 3 2 2 3 3 2 3

14、2 2 2 3 3 3 00 10 01 11 基于硬判决的Viterbi译码 Trellis图 信道编码和纠错编码相关概念 译码原理译码原理-维特比译码（续）维特比译码（续） 0.8 0.2 0 1.6 -1.8 3.4 2.0 0.8 -0.8 3.8 5.2 2.2 2.6 4.5 2.3 2.1 1.9 5.9 4.3 4.9 5.5 00 10 01 11 -0.8 基于软判决的Viterbi译码 Trellis图 信道编码和纠错编码相关概念 译码原理译码原理-维特比译码（续）维特比译码（续） Viterbi译码的特点 维特比算法是最大似然的序列译码算法 译码复杂度与信道质量无关 运

15、算量和存贮量都与码长呈线性关系 运算量和存贮量都与状态数呈线性关系 状态数随k及m呈指数关系 信道编码和纠错编码相关概念 4、Turbo码码 信道编码和纠错编码相关概念 （1）产生背景）产生背景 交织 块交织：行写入，列读出 卷积交织： L LL LLL LLLL LLLLL 0 1 2 3 W-2 W-1 入出 信道编码和纠错编码相关概念 产生背景（续）产生背景（续） 串行级联码 优点：性能较一般短码有很大改善 缺点：编码效率低；当R/C 1时性能迅速恶化 外 码 编 码 内 码 编 码 交 织 器 信 息 数 据 编 码 输 出 编 码 器 内 码 译 码 外 码 译 码 解 交 织 接

16、收 信 号 译 码 输 出 译 码 器 信道编码和纠错编码相关概念 产生背景（续）产生背景（续） 软输入软输出和迭代译码 对数似然比LLR )()()()()()( )()()()|( ) 1( ) 1( log ) 1|( ) 1|( log )| 1( )| 1( log)|()( dLdLxLdLdLdL dLxLdLdxL dP dP dxP dxP xdP xdP xdLdL ece c 信道编码和纠错编码相关概念 产生背景（续）产生背景（续） 软输入软输出和迭代译码 Soft-in soft-out decoder feedback for the next iteration L

17、e(d) L(d)Lc(x) L(d) L(d): priori values Lc(x): channel values Le(d): extrinsic values L(d): posterori values output LLR = Le(d)+ L(d) 返回 信道编码和纠错编码相关概念 （2）编译码原理）编译码原理 编码原理 编 码 器 1 编 码 器 2 交 织 器 开 关 单 元 复 接 器 编 码 输 出 信 息 数 据 信道编码和纠错编码相关概念 编译码原理（续）编译码原理（续） 译码原理 软 输 出 译 码 器 1 软 输 出 译 码 器 2 外 信 息 Z1k 交 织

18、 交 织 似然值L1k 解交织 信 息 符 号 序 列 校验序列y2k校验序列 y1k 判决器 译码输出 似然值L2k 外信息Z2k xk 迭代译码 信道编码和纠错编码相关概念 几点说明几点说明 Turbo码具有优越性能 具备构造好码的规律（分量码构造，交织 器构造等） 译码延时大，译码算法复杂 广泛应用于移动通信、军事通信、深空及 卫星通信等 信道编码和纠错编码相关概念 2.2.3 纠错编码的 基本原理 信道编码和纠错编码相关概念 1、差错控制编码 理论依据：香农信道编码定理 基本思想：通过对信息码元序列作某种变换,使原 来彼此相互独立,没有关联的信息码元序列,经过 这种变换后,产生某种规律

19、性或相关性,使在接收 端可根据这种规律性来检查,以至纠正传输序列中 的差错 实现：发送端按照某种规则在信息序列上附加监 督码元，接收端则按照同一规则检查两者间关 系 简单例子 信道编码和纠错编码相关概念 对于一给定的有干扰信道，若其信道容量 为C，只要发送端以低于C的速率R发送 信息，则一定存在一种编码方法，使编 码错误概率P随着码长n的增加，按指数 下降到任意小的值。 香农信道编码定理 信道编码和纠错编码相关概念 举例说明：假如要传送A、B两个消息 编码一：编码一： 消息A-“0”；消息B-“1” 若传输中产生错码（“0”错成“1”或“1” 错成“0”）收端无法发现，该编码无检错纠 错能力。

20、 信道编码和纠错编码相关概念 编码二：编码二： 消息A-“00”；消息B-“11” 若传输中产生一位错码，则变成“01”或 “10”，收端判决为有错（因“01”“10”为 禁用码组），但无法确定错码位置，不能纠正， 该编码具有检出一位错码的能力。 这表明增加一位冗余码元后码具有检出一位错 码的能力 信道编码和纠错编码相关概念 编码三：编码三： 消息A-“000”；消息B-“111” 传输中产生一位即使两位错码，都将变成禁用码组， 收端判决传输有错。该编码具有检出两位错码的能力。 在产生一位错码情况下，收端可根据“大数”法则进 行正确判决，能够纠正这一位错码。该编码具有纠正 一位错码的能力。 这

21、表明增加两位冗余码元后码具有检出两位错码及纠 正一位错码的能力。 信道编码和纠错编码相关概念 可见 纠错编码之所以具有检错和纠错能力，确实 是因为在信息码元外添加了冗余码元（监督 码元） 一般说来，添加的冗余越多，码的检错、纠 错能力越强，但信道的传输效率下降也越多。 信道编码和纠错编码相关概念 涉及概念：检错、纠错；许用码组/字、禁 用码组/字；错误译码 信道编码和纠错编码相关概念 随机差错独立差错 差错的出现随机，且差错之间是统计独立的 由随机噪声引起 存在这种差错的信道称为随机信道无记忆信道 突发差错 差错在短时间成串出现，而在其间又存在较长的无差 错区间，且差错之间相关 因脉冲噪声，也

22、可能是由存储系统中磁带的缺陷或读 写头接触不良引起 存在这种差错的信道称为突发信道有记忆信道 2、差错分类 信道编码和纠错编码相关概念 例 设发送数据序列为：111111111 接收数据序列为：111001001 则差错序列为： 110110 差错序列：发送数据序列与接收序列对应码位的模 和 发生了两个长度分别为和的突发差错，其错误图 样分别为和11011 突发长度：指突发差错首位与末位之间的长度（中间 可能有没错的码位） 差错序列或错误图样中的“”表示对应码位没错， 而“”表示有错 实际信道很复杂，所出现的差错并不是单一的，往往 是随机和突发差错并存，只不过以某种错误为主 信道编码和纠错编码

23、相关概念 码重：码字中非零码元的数目定义为该码字的重量， 简称码重。如“10011”码字的码重为3。 码距：两个码字中对应码位上具有不同二进制码元 的位数定义两码字的距离，称为汉明（Hamming） 距离,简称码距。如两码字“10011”与“11010” 间码距为2。 最小码距：在一个码中，任意两个码字间距离的最 小值，即码字集合中任意两元素间的最小距离，记 为d0 3、几个概念 信道编码和纠错编码相关概念 4、最小码距与检、纠错能力关系 一个码能检测e个错码，则要求其最小码距 d0e+1 反之，若码的最小距离为d0，则最多能检测d0-1个 错码。 一个码能纠正t个错码，则要求其最小码距 d0

24、2t+1 反之，若码的最小距离为d0，则最多能纠正(d0- 1)/2个错码。 一个码能纠正t个错码，同时能检测e个错码，则要 求其最小码距 d0e+t+1 (et) 信道编码和纠错编码相关概念 信道编码和纠错编码相关概念 5、编码效率 指一个码组中信息位所占比重，用表示 =k/n，其中k为信息码元的数目，n为码 长 信道编码和纠错编码相关概念 6、 差错控制方式 能够发现错误的码 判决信号 发收 (a) 检错重发（ARQ） 信道编码和纠错编码相关概念 能够纠正错误的码 发收 (b) 前向纠错（FEC） 信道编码和纠错编码相关概念 能够发现和纠正错误的码 发收 (c)混合纠错检错（HEC） 判决信号 信道编码和纠错编码相关概念 数据信息 发收 (d)信息反馈 数据信息 信道编码和纠错编码相关概念 检错重发/ARQ 接收端按一定规则对收到的码组进行有无 错误的判别。若发现有错，则通知发送端 重发，直到正确收到为止。 具体实现时，通常有3种形式： 信道编码和纠错编码相关概念 2发送端： 接收端： 133 1 23 ACK ACKNAK 发现错误 (a) 停发等候重发 TiTw 信道编码和纠错编码相关概念 (a) 停发等候重发 发端在Tw时间内送出一个码组，收端收到后检查 如果未发现错误，则发回一个认可信号（ACK）给 发送端，发送端收到ACK信号