信道编码定ppt课件

《信道编码定ppt课件》由会员分享，可在线阅读，更多相关《信道编码定ppt课件（27页珍藏版）》请在金锄头文库上搜索。

1、第五章：信道第五章：信道编码定理一定理一5.1 离散信道离散信道编码问题编码问题5.23 离散信道离散信道编码编码定理定理5.1 离散信道离散信道编码问题编码问题最简单的检错和纠错单个的字无法检错：扪？词汇可以检错：我扪的我扪的词汇可以纠错：我扪的我们的，我等的，我辈的，我班的，缘由分析：“扪？可以有几万个答案，但“我扪的？的答案却很少。结论：课文以及词汇的概率分布的稀疏性可以用来检错和纠错。5.1 离散信道离散信道编码问题编码问题设信道是一个D元字母输入/ D元字母输出的DMC信道，字母表为0, 1, , D-1。其信道转移概率矩阵为DD矩阵如下。这是一个对称信道。信道传输错误的概率定义为P

2、(输出不等于k|输入为k)= p，k0, 1, , D-1。此处p(1-p)。5.1 离散信道离散信道编码问题编码问题设信源音讯序列经过D元信源编码等长编码或不等长编码后变成了如下的随机变量序列X-2X-1X0X1X2，其中每个随机变量Xl的事件全体都是D元字母表0, 1, , D-1。将此随机变量序列切割成L维随机向量预备输入信道：(X1X2XL), (XL+1XL+2X2L), 。假设直接将(X1X2XL)输入信道，信道的输出为(X1X2XL)，那么当信道传输错误时无法检测到即接纳方无法确知能否正确接纳。正确接纳的概率为P(X1X2XL)=(X1X2XL)=P(X1=X1)P(X2=X2)

3、P(XL=XL)=(1-p)L。 5.1 离散信道离散信道编码问题编码问题将(X1X2XL)进展变换：C(X1X2XL)=(U1U2UN)，其中 (U1U2UN)为N维随机向量，NL，且变换是单射即(X1X2XL)的不同事件映射到(U1U2UN)的不同事件。将(U1U2UN)输入信道；信道的输出为(Y1Y2YN)；再根据(Y1Y2YN)的值猜测出输入信道的值(U1U2UN)，并根据变换式(U1U2UN)=C(X1X2XL)将(U1U2UN)反变换为(X1X2XL)。假设(X1X2XL)=(X1X2XL)，那么正确接纳。5.1 离散信道离散信道编码问题编码问题1(X1X2XL)的事件共有DL个，

4、因此(U1U2UN)的事件共有DL个，占N维向量值的份额为DL/DN=1/DN-L。因此当信道传输错误时，有能够使输出值(Y1Y2YN)不在这1/DN-L份额之内。这就是说，信道传输错误有能够被检测到。2假设精心地设计变换C(X1X2XL)=(U1U2UN)和猜测规那么(Y1Y2YN)(U1U2UN)，那么正确接纳的概率远远大于(1-p)L。 3变换(X1X2XL)(U1U2UN)=C(X1X2XL)称为信道编码，又称为(N, L)码。一个事件的变换值称为该事件的码字。L称为信息长，N称为码长。5.1 离散信道离散信道编码问题编码问题4过程(Y1Y2YN)(U1U2UN)(X1X2XL)称为纠

5、错译码。当(X1X2XL)=(X1X2XL)时称为正确译码实践上就是正确接纳。5N比L大得越多，1/DN-L份额越小，码字的分布越稀疏，信道传输错误不在这1/DN-L份额之内的能够性越大，即信道传输错误越容易被检测到。但N比L大得越多，信道传输的浪费越大。6称R=L/N为编码速率，也称为信息率。似乎与信源编码相互倒置？7注解：“(X1X2XL)不进展编码实践上也是一种编码，称为恒等编码。 此时N=L，事件x=(x1x2xL)的码字就是x本身。5.1 离散信道离散信道编码问题编码问题关于关于译码准那么准那么译码准那么就是猜准那么就是猜测规那么。当信道的那么。当信道的输出出值为y时，将其，将其译为

6、哪个哪个码字字u最合理？最合理？最大后最大后验概率准那么概率准那么简记b(u|y)=P(U1U2UN)=u|(Y1Y2YN)=y)。称。称b(u|y)为后后验概率。概率。最大后最大后验概率准那么：概率准那么：5.1 离散信道离散信道编码问题编码问题后验概率的计算：记q(u)=P(U1U2UN)=u)，称q(u)为先验概率；pN(y|u)=P( (Y1Y2YN)=y|(U1U2UN)=u)，我们知道p(y|u)是信道呼应特性，而且pN(y|u)=P(Y1=y1|U1=u1)P(Y2=y2|U2=u2)P(YN=yN|UN=uN)=(p/(D-1)d(1-p)N-d，其中d是(y1y2yN)与(u

7、1u2uN)对应位置值不一样的位数；以后将称d为Hamming间隔5.1 离散信道离散信道编码问题编码问题记w(y)=P(Y1Y2YN)=y)。我们知道5.1 离散信道离散信道编码问题编码问题最大似然概率准那么最大似然概率准那么最小最小间隔准那么最小隔准那么最小错误准那么准那么y与与u的的Hamming间隔定隔定义为(y1y2yN)与与(u1u2uN)对应位置位置值不一不一样的位数，的位数，记为d(y, u)。5.1 离散信道离散信道编码问题编码问题命命题 最大似然概率准那么等价于最小最大似然概率准那么等价于最小间隔准那么。隔准那么。证明明 pN(y|u)=P(Y1=y1|U1=u1)P(Y2

8、=y2|U2=u2)P(YN=yN|UN=uN)=(p/(D-1)d(1-p)N-d，其中其中d是是y与与u的的Hamming间隔。隔。留意到留意到p/(D-1)(1-p)。所以。所以pN(y|u)到达最大，当且到达最大，当且仅当当y与与u的的Hamming间隔到达最小。隔到达最小。得得证。5.1 离散信道离散信道编码问题编码问题命题命题 假设每个码字是等概出现的，那么最大后验概率准那么假设每个码字是等概出现的，那么最大后验概率准那么等价于最大似然概率准那么。等价于最大似然概率准那么。证明证明5.1 离散信道离散信道编码问题编码问题对两种译码准那么的评述对两种译码准那么的评述最大后验概率准那么

9、具有很好的直观合理性。收到最大后验概率准那么具有很好的直观合理性。收到y的条件下，的条件下，最能够发送的是哪个码字，就以为发送的是哪个码字。最能够发送的是哪个码字，就以为发送的是哪个码字。最大似然概率准那么最小间隔准那么所具有的直观合理最大似然概率准那么最小间隔准那么所具有的直观合理性弱一些。发送哪个码字的条件下，最能够收到性弱一些。发送哪个码字的条件下，最能够收到y，就以为，就以为发送的是哪个码字。发送的是哪个码字。最大似然概率准那么最小间隔准那么的实现比最大后验最大似然概率准那么最小间隔准那么的实现比最大后验概率准那么的实现更简单：前者只需求看哪个码字与概率准那么的实现更简单：前者只需求看

10、哪个码字与y的的Hamming间隔最小；后者需求知道各码字的概率分布，然间隔最小；后者需求知道各码字的概率分布，然后用贝叶斯公式计算并比较后验概率。后用贝叶斯公式计算并比较后验概率。两种准那么都可以用在没有编码直接发送情况下的纠错两种准那么都可以用在没有编码直接发送情况下的纠错译码。译码。5.1 离散信道离散信道编码问题编码问题例例5.1.1(p143) BSC信道的信道的转移概率矩移概率矩阵为取取L=1。假。假设直接将直接将X1输入信道，信道的入信道，信道的输出出为X1，那么，那么当信道当信道传输错误时无法无法检测到。到。正确接正确接纳的概率的概率为P(X1=X1)=1-p。今取今取L=1，

11、N=4，二元，二元(4, 1)码如下：如下：00000，11111。 5.1 离散信道离散信道编码问题编码问题译码规那么如下：当(Y1Y2Y3Y4)中1的个数为3或4时，(Y1Y2Y3Y4)(1111)1；当(Y1Y2Y3Y4)中1的个数为0或1时，(Y1Y2Y3Y4)(0000)0；当(Y1Y2Y3Y4)中1的个数为2时，(0011)、(1100)、(1001)(0000) 0，(0101)、(1010)、(0110)(1111) 1。译码规那么显然是最小间隔准那么。 5.1 离散信道离散信道编码问题编码问题何时检测到信道传输错误？当(Y1Y2Y3Y4)不是一个码字时，检测到信道传输错误。换

12、句话说，(Y1Y2Y3Y4)与原发码字(U1U2U3U4) 的Hamming间隔1且3时，检测到信道传输错误。因此，信道传输有错误但能检测出错误的概率为5.1 离散信道离散信道编码问题编码问题何时正确译码正确接纳？当(Y1Y2Y3Y4)与原发码字(U1U2U3U4) 的Hamming间隔1时，正确译码；当(Y1Y2Y3Y4)与原发码字(U1U2U3U4) 的Hamming间隔=2时，一半能正确译码，另一半不能正确译码；当(Y1Y2Y3Y4)与原发码字(U1U2U3U4) 的Hamming间隔3时，不能正确译码。正确译码正确接纳的概率为5.1 离散信道离散信道编码问题编码问题5.23 离散信道离

13、散信道编码编码定理定理首先需求阐明，上述离散信道编码的编码速率信息率R 本来是设备所确定的。当信源每秒产生ns个字母，信道编码所运用的设备每秒产生nc个字母，那么设备所确定的编码速率就是R = ns/nc。其次，实践编码速率实践信息率L/N 必需不小于设备所确定的编码速率：L/N R。于是对离散信道编码有了以下两条相互矛盾的要求：1实践编码速率L/N 尽能够小以便使正确译码正确接纳的概率尽能够接近1。2实践编码速率不小于设备所确定的编码速率L/N R。5.23 离散信道离散信道编码编码定理定理设信源序列经过信源编码后变成了如下的序列X-2X-1X0X1X2。设各随机变量独立同分布。记H(X)为

14、X0的熵，C为信道容量。假设设备所确定的编码速率RC/H(X)，那么不可以同时满足这两条要求。假设设备所确定的编码速率R=C/H(X)，那么情况如何？很复杂，属于边境情况，没有简单整齐的结论。 5.23 离散信道离散信道编码编码定理定理定理定理5.3.1(p152) Shannon信道信道编码定理假定理假设设备所确所确定的定的编码速率速率RC/H(X)，那么，那么对任何正整数任何正整数LL=1，2，存在，存在D元元(N, L)码和和对应的的译码方法，使方法，使习题课习题课5.l 设有一DMC，其转移概率矩阵如下。假设Q(x1)l/2，Q(x2)Q(x3)1/4，试求最正确译码判决以及误码率。习

15、题课习题课5.l的解答 最正确译码判决指的是最大后验概率译码。记(Q(x1), Q(x2), Q(x3)信道的输入随机变量X的概率向量，又称为先验概率向量， (W(y1), W(y2), W(y3)为信道的输出随机变量Y的分布概率向量。那么(Q(x1), Q(x2), Q(x3)=(1/2,1/4, 1/4)，习题课习题课P(X, Y)=(x1, y1)=1/4P(X, Y)=(x2, y1)=1/24P(X, Y)=(x3, y1)=1/12P(X, Y)=(x1, y2)=1/6P(X, Y)=(x2, y2)=1/8P(X, Y)=(x3, y2)=1/24P(X, Y)=(x1, y3

16、)=1/12P(X, Y)=(x2, y3)=1/12P(X, Y)=(x3, y3)=1/8P(X=x1|Y=y1)=P(X, Y)=(x1, y1)/W(y1)=2/3P(X=x2|Y=y1)=P(X, Y)=(x2, y1)/W(y1)=1/9P(X=x3|Y=y1)=P(X, Y)=(x3, y1)/W(y1)=2/9P(X=x1|Y=y2)=P(X, Y)=(x1, y2)/W(y2)=1/2P(X=x2|Y=y2)=P(X, Y)=(x2, y2)/W(y2)=3/8P(X=x3|Y=y2)=P(X, Y)=(x3, y2)/W(y2)=1/8P(X=x1|Y=y3)=P(X, Y

17、)=(x1, y3)/W(y3)=2/7P(X=x2|Y=y3)=P(X, Y)=(x2, y3)/W(y3)=2/7P(X=x3|Y=y3)=P(X, Y)=(x3, y3)/W(y3)=3/7习题课习题课收到“Y=y1时，译作“X=x1，误码率译码错误的概率为1/3；收到“Y=y2时，译作“X=x1，误码率译码错误的概率为1/2；收到“Y=y3时，译作“X=x3，误码率译码错误的概率为4/7。习题课习题课补充内容 试求最大似然译码。最大似然译码不需求先验概率向量，只需求转移概率矩阵。收到“Y=y1时，P(Y=y1|X=x1)=maxxP(Y=y1|X=x)，译作“X=x1 ；收到“Y=y2时，P(Y=y2|X=x2)=maxxP(Y=y2|X=x)，译作“X=x2 ；收到“Y=y3时，P(Y=y3|X=x3)=maxxP(Y=y3|X=x)，译作“X=x3 。