纠错码Lecture2-基本概念

Lecture2

基本概念2内容信道模型与错误图样差错控制系统分类纠错码的基本原理最大似然译码汉明距离与重量码纠错能力及编码增益信道编码定理与信道容量3信道模型与错误图样三种判决方法

硬判决：勉强作出是0还是1的判决

删除符号：对该码元暂且不作判决，而输出一个未知或待定的信号“x”

软判决：输出一种有关该码元的信息，例如关于0和1的后验概率和似然概率4信道模型与错误图样BSC：二进制对称信道Z信道1-p1-ppp001111-pp0011信道模型与错误图样DMC:离散无记忆信道BEC:二进制删除信道50110q-2q-1P(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-ppp1-p001e1…6信道模型与错误图样BIAWGN:离散输入连续输出信道假定信道编码器的输出符号取自，译码器输入为连续值Y=R，我们称这类信道为离散输入连续输出信道，典型的有：二元输入高斯白噪声信道（BIAWGN）和二元拉普拉斯(Laplace)信道BIAWGN输入输出可表示为

Y=X+N其中，N为加性高斯白噪声，其均值为零，方差为。给定一个输入，，则Y是均值为xk，方差为的高斯变量其他信道:有记忆（突发）信道，组合信道

7信道模型与错误图样错误图样发送序列C:(1111011000)错误图样E:(1001001110)接收序列R:(0110010110)R=C+EorE=C+R突发图样:(100100111)；突发长度：9二进制运算规则⊕00110011模2加⊙00110100模2乘8差错控制系统分类FEC:前向纠错方式；ARQ:重传反馈方式HEC:混合纠错方式;IRQ:狭义信息反馈系统可纠正错误的码发收FEC能够发现错误的码发收ARQ应答信号能够发现和纠正错误的码发收HEC应答信号信息信号发收IRQ信息信号差错控制系统分类FEC:前向纠错方式

优点：不需要反馈信道，译码实时性好，控制电路简单

缺点：译码设备复杂，信道适应性较差ARQ:重传反馈方式优点：编译设备简单，纠错能力强，系统适应性强缺点：控制电路复杂，传送消息的连贯性和实时性较差HEC:混合纠错方式

特点：综合了FEC和ARQ的优点IRQ:狭义信息反馈系统9纠错码的基本原理分组码

分组码是对每段k位长的信息组，以一定的规则增加r=n-k个校验元，组成长为n的序列(cn-1,cn-2,

…,c1,c0)，称这个序列为码字（码组、码矢）。卷积码(n0,k0,m0)卷积码是对每段k0长的信息组以一定的规则增加r0=n0-k0个校验元，组成长为n0的码段。r0=n0-k0个校验元不仅与本段的信息元有关，且与前m段信息元有关，当信息元不断输入时，输出的码序列是一个半无限长序列。1011纠错码的基本原理以重复码为例00…00

11…11其他所有二进制组合为禁用码组(字)若将每个比特重复n次，则构成一个码长为n，信息位长度为1的(n,1)重复码,且编码效率(码率)R=1/nn=2时许用码组：00,11

禁用码组：01,10

可能接收码字：00,01,10,11

能够发现一个错误，但不能纠正错误许用码组(字)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,1100,1001,1010,0111,1101,1110,1011能够纠正一个错误同时发现两个错误；或发现三个错误译码正确译码失败译码错误13纠错码的基本原理译码失败：译码器根据接收到的信号无法作出明确判断,不完备译码;译码错误：译码器根据接收到的信号作出错误判断;完备译码：根据接收信号，译码器一定能作出是哪一组信息的判断纠错码的基本原理：在信息序列之后按照一定的规则添加一定长度的保护比特(校验比特或监督比特)14最大似然译码译码问题MCR；如何根据接收信号R估计发送序列C’,进而估计信息序列M’设计译码算法的原则：使译码错误概率最小最大后验概率(MAP:MaximumPosteriorProbability)译码最大似然译码在先验等概的情况下，MAP简化为ML

由贝叶斯公式

若发端发送每个码字的概率均相同，则1516汉明距离与重量汉明距离两个n重x、y之间，对应位取值不同的个数，称为它们之间的汉明距离，用d(x,y)表示。例如，若x=10101，y=01111，则d(x,y)=3。汉明重量n重x中非零码元的个数，称为它的汉明重量，简称重量，用w(x)表示。

w(x)=3,w(y)=4最小距离(n,k)分组码中，任意两个码字之间距离的最小值，称为该分组码的最小汉明距离d0，简称最小距离。汉明距离与重量在BSC信道中，最大似然译码=最小汉明距离译码

由

可知，MLD译码器寻求可能出现的错误图样，就是在码字集中，寻求与R的汉明距离最小的码字Ci，为最可能发送码字，即最小汉明距离译码。1718码纠错能力及编码增益任一(n,k)分组码，若要在码字内：1)检测e个随机错误，则要求码的最小汉明距离d0>=e+12)纠正t个随机错误，则要求d0>=2t+13)纠正t个随机错误，同时检测e(e>=t)个错误，则要求d0>=e+t+14)纠正t个随机错误和ρ个删除，则要求d0>=2t+ρ+1编码增益：给定性能前提下，

编码增益=未编码时需要的信噪比(dB)–编码时需要的信噪比(dB)19信道编码定理与信道容量信道编码定理任意离散输入无记忆平稳有噪信道都有一个被称为信道容量的值C，它标志着信道传输能力的上限，只要

信息传输速率R≤C，就存在一种编码方式，当平均码长足够大时，译码错误概率可以做到任意小；反之，则无论采用何种编码方式也不可能保证错误概率任意小。信道容量信道容量定义为信道输入与信道输出的互信息，它表征了信道可靠传输的最大速率。这个容量仅在输入服从高斯分布的情况下可以达到。如果输入信号调制受限，那么容量将会小于上面这个值。

20信道编码定理与信道容量BSC