讲义51纠错编码原理

纠错编码原理

从这一章开始介绍有噪声信道编码的问题，有噪声信道编码的主要目的是提高传输可靠性，增加抗干扰能力，因此也称为纠错编码或抗干扰编码。在这一章里将首先介绍信道编码定理和纠错编码的基本原理。

信源编码之后的码字序列抗干扰能力很脆弱，在信道噪声的影响下容易产生差错，为了提高通信系统的有效性和可靠性，要在信源编码器和信道之间加上一个信道编码器， 5-1 译码准则 5-1-1 译码准则的含义

(1) 一个例子

影响通信系统可靠性的一个重要问题是译码方式，可以通过一个例子看一下； 有一个BSC信道，如图所示。

1 1-p=1/4 1

对于这样一个信道，如果采用自然的译码准则，即收0判0，收1判1；这时可以明显看到，当信源先验概率的等概时p(0)=p(1)=1/2；这时收到Y判X的后验概率等于信道转移概率，系统正确的译码概率为1/4，错误译码概率为3/4。但如果采用另一种译码准则，收0判1，收1判0；则系统正确的译码概率为3/4，错误译码概率为1/4，通信的可靠性提高了。

(2) 译码准则

设一个有噪声离散信道，输入符号集X，输出符号集Y，信道转移概率为P(Y/X);

xi yj

X:{x1,x2,…..,xn} Y:{y1,y2,……ym}

P(Y/X):{p(yj/xi); i=1,2,…n; j=1,2,…m

这时定义一个收到yj后判定为xi的单值函数，即： F(yj)=xi (i=1,2,…n; j=1,2,…m)；这个函数称为译码函数。它构成一个译码函数组，这些函数的值组成了译码准则。

对于有n个输入，m个输出的信道来说，可以有nm个不同的译码准则。例如上面例子中有4中译码准则分别为：

A:{F(0)=0;F(1)=0} B:{F(0)=0;F(1)=1} C:{F(0)=1;F(1)=0} D:{F(0)=1;F(1)=1} 5-1-2 译码错误概率

当译码准则确定之后，当接收端收到一个yj后，则按译码准则译成F(yj)=xi，这时如果发送的为xi则为正确译码，如果发送的不是xi则为错误译码。所以接收到yj后正确译码的概率就是接收端收到yj后，推测发送端发出xi的后验概率：

Prj=P{F(yj)=xi/yj}

而错误译码的概率为收到yj后，推测发出除了xi之外其它符号的概率：

Pej=P{e/yj}=1-P{F(yj)=xi/yj}

其中e表示除了xi之外的所有其它信源符号的集合。 然后对所有的yj取平均，则平均正确译码概率为：

Pr P(yj)Prj p(yj) p{F(yj) xi/yj}

j 1

j 1

mm

同样可以得到平均错误译码概率为：

P1 P[F(yj) xi/yj]} e p(yj)P{e/yj} p(yj){

j 1

j 1

mm

这就是平均错误译码概率的基本表达式，在通信系统设计和分析时，总是希望得到最可能小的平均错误译码概率。因此所有通信系统都将平均译码错误概率作为系统可靠性的一个重要指标。

5-1-3 最大后验概率准则

由平均错误译码概率的表达式可以看出，错误译码概率与信道输出端随机变量Y的概率分布p(yj)有关，也与译码准则有关。当信道信道转移概率p(yj/xi)确定后，而且信源统计特性p(xi)确定之后，信道输出端的p(yj)也就确定了。因为：p(xi,yj)=p(xi)p(yj/xi); 而p(yj)可以由p(xi,yj)的(i=1,2, n)求和得到。

因此，在这种情况下，平均错误译码概率只与译码准则有关了。通过选择译码准则可以使平均译码概率达到最小值。

当式中的每一项的P{F(yj)=xi/yj}达到最大值时，平均错误译码概率就可以为最小值。 设信源X的信源空间为：

X: x1 x2 … xn

[X,P]:

P(X): p(x1) p(x2) … p(xn)

信道的转移矩阵为：

y1 y2 … ym

x1 p(y1/x1) p(y2/x1) … p(ym/x1) x2 p(y1/x2) p(y2/x2) … p(ym/x2)

[P]=

… … … … … xn p(y1/xn) p(y2/xn) … p(ym/xn)

收到每一个yj(j=1,2,…m)后，推测发送为xi(i=1,2,…n)的后验概率共有n个，为： p(x1/yj),p(x2/yj),……p(xn/yj)。

这其中必有一个为最大的，设其为：p(x*/yj)，即有： p(x*/yj)≥p(xi/yj) (对一切的i)

这表明：收到符号yj后就译为输入符号x*，即译码函数选为： F(yj)=a* (j==1,2,…m)

这种译码准则称为“最大后验概率准则”。

利用这种准则就可以使平均译码错误概率公式中的s项求和的每一项：{1-P[F(yj) = xi/yj]}达到最小值{1-[F(yj)=x*/yj]}。这时的平均错误译码概率的最小值为：

P1 p(x*/yj)} emin p(yj) {

i 1

m

p(x,y

i

i 1

j 1

nm

j

) p(x*,yj)

j 1

m

p(y

i 1

m

j

) p(yj)p(x*/yj)

i 1

m

p(xi,yj) p(xi)p(yj/xi)

j 1i

j 1i

mm

这个表达式平均错误译码概率的最小值，是把每一个yj对应的后验概率排除后再连续求和。

从表达式中可以看到，这个最小值与信源先验概率和信道转移概率有关，特别是信

道转移概率，如果除了p(yj/x*)外，其它的项多很小，错误译码概率会减小。 5-1-4 最大似然准则

使用最大后验概率译码准则必须已知后验概率，但信道的统计特性描述总是给出信道转移概率，因此利用信道转移概率的译码准则。

由概率中的贝叶斯定理可有： p(xi/yj)

p(xi)p(yj/xi)

p(yj)

p(x*/yj)

p(x*)p(yj/x )

p(yj)

这样，根据最大后验概率译码准则，如果

p(x*)p(yj/x*)≥p(xi)p(yj/xi) (i=1,2,……n) 就等于：p(x*/yj)≥p(xi/yj)

则选择译码准则：F(yj)=x* (j=1,2,……n)

这样，可以看到当信道输入符号集X的先验概率为等概时[p(xi)=1/n]，比较上面三个式子，最 …… 此处隐藏：10358字，全部文档内容请下载后查看。喜欢就下载吧 ……