纠错码Lecture2-基本概念

1、信道编码理论信道编码理论 邢莉娟、李卓，西安电子科技大学邢莉娟、李卓，西安电子科技大学 Lecture 2 Lecture 2 基本概念基本概念 信道编码理论信道编码理论 2 信道模型与错误图样信道模型与错误图样 差错控制系统分类差错控制系统分类 纠错码的基本原理纠错码的基本原理 最大似然译码最大似然译码 汉明距离与重量汉明距离与重量 码纠错能力及编码增益码纠错能力及编码增益 信道编码定理与信道容量信道编码定理与信道容量 Lecture 2 Lecture 2 基本概念基本概念 信道编码理论信道编码理论 3 三种判决方法三种判决方法 硬判决：勉强作出是硬判决：勉强作出是0还是还是1的判决的判决

2、 删除符号：对该码元暂且不作判决，而输出一个删除符号：对该码元暂且不作判决，而输出一个 未知或待定的信号未知或待定的信号“x” 软判决：输出一种有关该码元的信息，例如关于软判决：输出一种有关该码元的信息，例如关于 0和和1 的后验概率和似然概率的后验概率和似然概率 Lecture 2 Lecture 2 基本概念基本概念 信道编码理论信道编码理论 4 BSC：二进制对称信道：二进制对称信道 Z信道信道 1-p 1-p p p 00 11 1 1-p p 00 11 Lecture 2 Lecture 2 基本概念基本概念 信道编码理论信道编码理论 DMC:离散无记忆信道离散无记忆信道 BEC:

3、二进制删除信道二进制删除信道 5 0 1 1 0 q-2 q-1 P(0|0) P(1|0) P(q-2|0) P(q-1|0) P(q-2|0) P(q-2|1) P(1|1) P(0|1) 1-p p p 1-p 00 1 e 1 Lecture 2 Lecture 2 基本概念基本概念 信道编码理论信道编码理论 6 BIAWGN:离散输入连续输出信道离散输入连续输出信道 假定信道编码器的输出符号取自 ，译码器输入 为连续值Y=R，我们称这类信道为离散输入连续输出信道，典型 的有：二元输入高斯白噪声信道（BIAWGN）和二元拉普拉斯 (Laplace)信道 BIAWGN输入输出可表示为 Y

4、=X+N 其中，N为加性高斯白噪声，其均值为零，方差为 。给定一个输 入 ， ，则Y是均值为xk，方差为 的 高斯变量 其他信道其他信道:有记忆（突发）信道，组合信道有记忆（突发）信道，组合信道 011 , q x xx X 2 k Xx0,1,1kq 2 2 1 ( |)exp ()/2 2 kk p y Xxyx Lecture 2 Lecture 2 基本概念基本概念 信道编码理论信道编码理论 7 错误图样错误图样 发送序列发送序列C: (1111011000) 错误图样错误图样E: (1001001110) 接收序列接收序列R: (0110010110) R=C+E or E=C+R

5、突发图样突发图样: (100100111)；突发长度：；突发长度：9 二进制运算规则二进制运算规则 0 0 1 1 0 0 1 1 模2加 0 0 1 1 0 1 0 0 模2乘 Lecture 2 Lecture 2 基本概念基本概念 信道编码理论信道编码理论 8 FEC: 前向纠错方式前向纠错方式； ARQ: 重传反馈方式重传反馈方式 HEC: 混合纠错方式混合纠错方式; IRQ: 狭义信息反馈系统狭义信息反馈系统 可纠正错误的码 发收 FEC 能够发现错误的码 发收 ARQ 应答信号 能够发现和纠正错误的码 发收 HEC 应答信号 信息信号 发收 IRQ 信息信号 Lecture 2 L

6、ecture 2 基本概念基本概念 信道编码理论信道编码理论 FEC: 前向纠错方式前向纠错方式 优点：不需要反馈信道，译码实时性好，控制电路简单优点：不需要反馈信道，译码实时性好，控制电路简单 缺点：译码设备复杂，信道适应性较差缺点：译码设备复杂，信道适应性较差 ARQ: 重传反馈方式重传反馈方式 优点：编译设备简单，纠错能力强，系统适应性强优点：编译设备简单，纠错能力强，系统适应性强 缺点：控制电路复杂，传送消息的连贯性和实时性较差缺点：控制电路复杂，传送消息的连贯性和实时性较差 HEC: 混合纠错方式混合纠错方式 特点：综合了特点：综合了FEC和和ARQ的优点的优点 IRQ: 狭义信息反

7、馈系统狭义信息反馈系统 9 Lecture 2 Lecture 2 基本概念基本概念 信道编码理论信道编码理论 分组码分组码 分组码是对每段分组码是对每段k位长的信息组，以一定的规则位长的信息组，以一定的规则 增加增加r=n-k个校验元，组成长为个校验元，组成长为n的序列的序列(cn-1,cn-2, ,c1,c0)，称这个序列为码字（码组、码矢）。，称这个序列为码字（码组、码矢）。 卷积码卷积码 (n0,k0,m0)卷积码是对每段卷积码是对每段k0长的信息组以一定的长的信息组以一定的 规则增加规则增加r0=n0-k0个校验元，组成长为个校验元，组成长为n0的码段。的码段。 r0=n0-k0个校

8、验元不仅与本段的信息元有关，且与个校验元不仅与本段的信息元有关，且与 前前m段信息元有关，当信息元不断输入时，输出段信息元有关，当信息元不断输入时，输出 的码序列是一个半无限长序列。的码序列是一个半无限长序列。 10 Lecture 2 Lecture 2 基本概念基本概念 信道编码理论信道编码理论 11 以重复码为例以重复码为例 0000 1111 其他所有二进制组合为禁用码组(字) 若将每个比特重复n次，则构成一个码长为n，信息位 长度为1的(n,1)重复码,且编码效率(码率) R=1/n n=2时 许用码组：00, 11 禁用码组：01, 10 可能接收码字：00, 01, 10, 11

9、 能够发现一个错误，但不能纠正错误能够发现一个错误，但不能纠正错误 许用码组(字) Lecture 2 Lecture 2 基本概念基本概念 信道编码理论信道编码理论 12 n=3 许用码组：000, 111 禁用码组：001, 010, 100, 101, 110, 011 可能接收码字： 000, 001, 010, 100, 101, 110, 011, 111 能够发现两个错误，纠正一个错误能够发现两个错误，纠正一个错误 n=4 许用码组：0000，1111 假定发送码字为：00000 禁用码组：0001, 0010, 0100, 1000, 0011, 0101, 0110, 110

10、0, 1001, 1010, 0111, 1101, 1110, 1011 能够纠正一个错误同时发现两个错误；或能够纠正一个错误同时发现两个错误；或发现三个错误发现三个错误 译码正确 译码失败 译码错误 Lecture 2 Lecture 2 基本概念基本概念 信道编码理论信道编码理论 13 译码失败译码失败：译码器根据接收到的信号无法作出明 确判断,不完备译码; 译码错误译码错误：译码器根据接收到的信号作出错误判 断; 完备译码完备译码：根据接收信号，译码器一定能作出是 哪一组信息的判断 纠错码的基本原理：纠错码的基本原理： 在信息序列之后按照一定的规则添加一定长度的保护在信息序列之后按照一

11、定的规则添加一定长度的保护 比特比特(校验比特或监督比特校验比特或监督比特) Lecture 2 Lecture 2 基本概念基本概念 信道编码理论信道编码理论 14 译码问题译码问题 MC R；如何根据接收信号R估计发送序列C,进而 估计信息序列M 设计译码算法的原则：使译码错误概率最小 最大后验概率最大后验概率(MAP: Maximum Posterior Probability)译码译码 R E RPREPPRCCPREP RCCMinPREMinPMinPE 1MinP CC RMinP CC R RCCMaxP Lecture 2 Lecture 2 基本概念基本概念 信道编码理论信

12、道编码理论 在在先验等概的情况下，先验等概的情况下，MAP简化为简化为ML 由贝叶斯公式由贝叶斯公式 若发端发送每个码字的概率均相同，则若发端发送每个码字的概率均相同，则 15 | | ii i pp p p CR C CR R 1,2,1,2, , max|max| kk ii ii pp CRR C , 22 Lecture 2 Lecture 2 基本概念基本概念 信道编码理论信道编码理论 16 汉明距离汉明距离 两个n重x、y之间，对应位取值不同的 个数，称为它们之间的汉明距离，用d(x,y)表示。 例如，若x=10101，y=01111，则 d(x,y)=3。 汉明重量汉明重量 n重

13、x中非零码元的个数，称为它的汉明 重量，简称重量，用w(x)表示。 w(x)=3,w(y)=4 最小距离最小距离 (n, k)分组码中，任意两个码字之间距 离的最小值，称为该分组码的最小汉明距离d0，简 称最小距离。 0 ,(n,k) min, x y dd x y Lecture 2 Lecture 2 基本概念基本概念 信道编码理论信道编码理论 在在BSC信道中，最大似然译码信道中，最大似然译码=最小汉明距离译码最小汉明距离译码 由由 可知，可知，MLD译码器寻求可能出现的错误图样，就译码器寻求可能出现的错误图样，就 是在码字集中，寻求与是在码字集中，寻求与R的汉明距离最小的码字的汉明距离

14、最小的码字 Ci，为最可能发送码字，即最小汉明距离译码。，为最可能发送码字，即最小汉明距离译码。 17 1,2,1,2, , max|max| kk ii ii pp CRR C , 22 ERC Lecture 2 Lecture 2 基本概念基本概念 信道编码理论信道编码理论 18 任一任一(n, k)分组码，若要在码字内：分组码，若要在码字内： 1) 检测e个随机错误，则要求码的最小汉明距离 d0=e+1 2) 纠正t个随机错误，则要求d0=2t+1 3) 纠正t个随机错误，同时检测e (e=t)个错误，则要求 d0=e+t+1 4) 纠正t个随机错误和个删除，则要求 d0=2t+1 编

15、码增益：编码增益： 给定性能前提下， 编码增益编码增益=未编码时需要的信噪比未编码时需要的信噪比(dB) 编码时需要的编码时需要的 信噪比信噪比(dB) Lecture 2 Lecture 2 基本概念基本概念 信道编码理论信道编码理论 19 信道编码定理信道编码定理 任意离散输入无记忆平稳有噪信道都有一个被称为信信 道容量道容量的值C，它标志着信道传输能力的上限上限，只要只要 信息传输速率信息传输速率RC，就存在一种编码方式，当平均码，就存在一种编码方式，当平均码 长足够大时，译码错误概率可以做到任意小；反之，长足够大时，译码错误概率可以做到任意小；反之， 则无论采用何种编码方式也不可能保证

16、错误概率任意则无论采用何种编码方式也不可能保证错误概率任意 小。小。 信道容量信道容量 信道容量定义为信道输入与信道输出的互信息信道输入与信道输出的互信息，它表 征了信道可靠传输的最大速率。 这个容量仅在输入服从高斯分布的情况下输入服从高斯分布的情况下可以达到。 如果输入信号调制受限，那么容量将会小于上面这个 值。 Lecture 2 Lecture 2 基本概念基本概念 信道编码理论信道编码理论 20 BSC 对转移概率为对转移概率为p的二进制对称信道而言，当输的二进制对称信道而言，当输 入等概时，互信息取得最大值，信道容量为入等概时，互信息取得最大值，信道容量为 其中其中 是二元熵函数。是二元熵函数。 BEC 对于删余概率为对于删余概率为p的二进制删除信道，其信道的二进制删除信道，其信道 容量为容量为 22 1log(1)log (1) 1(