信息论与编码理论基础第五章

信息论与编码理论基础第五章第一页，共二十七页，2022年，8月28日2023/3/131§5.1离散信道编码问题最简单的检错和纠错单个的字无法检错：扪→？词汇能够检错：我扪的→我扪的词汇能够纠错：我扪的→我们的，我等的，我辈的，我班的，…原因分析：“扪→？”可以有几万个答案，但“我扪的→？”的答案却很少。结论：课文以及词汇的概率分布的稀疏性可以用来检错和纠错。第二页，共二十七页，2022年，8月28日2023/3/132§5.1离散信道编码问题设信道是一个D元字母输入/D元字母输出的DMC信道，字母表为{0,1,…,D-1}。其信道转移概率矩阵为D×D矩阵如下。这是一个对称信道。信道传输错误的概率定义为P(输出不等于k|输入为k)=p，k∈{0,1,…,D-1}。此处p<(1-p)。第三页，共二十七页，2022年，8月28日2023/3/133§5.1离散信道编码问题设信源消息序列经过D元信源编码（等长编码或不等长编码）后变成了如下的随机变量序列…X-2X-1X0X1X2…，其中每个随机变量Xl的事件全体都是D元字母表{0,1,…,D-1}。将此随机变量序列切割成L维随机向量准备输入信道：(X1X2…XL),(XL+1XL+2…X2L),…。如果直接将(X1X2…XL)输入信道，信道的输出为(X1’X2’…XL’)，则①当信道传输错误时无法检测到（即接收方无法确知是否正确接收）。②正确接收的概率为P((X1’X2’…XL’)=(X1X2…XL))=P(X1’=X1)P(X2’=X2)…P(XL’=XL)=(1-p)L。

第四页，共二十七页，2022年，8月28日2023/3/134§5.1离散信道编码问题将(X1X2…XL)进行变换：C(X1X2…XL)=(U1U2…UN)，其中(U1U2…UN)为N维随机向量，N≥L，且变换是单射（即(X1X2…XL)的不同事件映射到(U1U2…UN)的不同事件）。将(U1U2…UN)输入信道；信道的输出为(Y1Y2…YN)；再根据(Y1Y2…YN)的值猜测出输入信道的值(U1’U2’…UN’)，并根据变换式(U1’U2’…UN’)=C(X1’X2’…XL’)将(U1’U2’…UN’)反变换为(X1’X2’…XL’)。如果(X1’X2’…XL’)=(X1X2…XL)，则正确接收。第五页，共二十七页，2022年，8月28日2023/3/135§5.1离散信道编码问题（1）(X1X2…XL)的事件共有DL个，因此(U1U2…UN)的事件共有DL个，占N维向量值的份额为DL/DN=1/DN-L。因此当信道传输错误时，有可能使输出值(Y1Y2…YN)不在这1/DN-L份额之内。这就是说，信道传输错误有可能被检测到。（2）如果精心地设计变换C(X1X2…XL)=(U1U2…UN)和猜测规则(Y1Y2…YN)→(U1’U2’…UN’)，则正确接收的概率远远大于(1-p)L。（3）变换(X1X2…XL)→(U1U2…UN)=C(X1X2…XL)称为信道编码，又称为(N,L)码。一个事件的变换值称为该事件的码字。L称为信息长，N称为码长。第六页，共二十七页，2022年，8月28日2023/3/136§5.1离散信道编码问题（4）过程(Y1Y2…YN)→(U1’U2’…UN’)→(X1’X2’…XL’)称为纠错译码。当(X1’X2’…XL’)=(X1X2…XL)时称为正确译码（实际上就是正确接收）。（5）N比L大得越多，1/DN-L份额越小，码字的分布越稀疏，信道传输错误不在这1/DN-L份额之内的可能性越大，即信道传输错误越容易被检测到。但N比L大得越多，信道传输的浪费越大。（6）称R=L/N为编码速率，也称为信息率。（似乎与信源编码相互倒置？）（7）注解：“(X1X2…XL)不进行编码”实际上也是一种编码，称为恒等编码。此时N=L，事件x=(x1x2…xL)的码字就是x自身。第七页，共二十七页，2022年，8月28日2023/3/137§5.1离散信道编码问题关于译码准则译码准则就是猜测规则。当信道的输出值为y时，将其译为哪个码字u最合理？最大后验概率准则简记b(u|y)=P((U1U2…UN)=u|(Y1Y2…YN)=y)。称b(u|y)为后验概率。最大后验概率准则：第八页，共二十七页，2022年，8月28日2023/3/138§5.1离散信道编码问题后验概率的计算：记q(u)=P((U1U2…UN)=u)，称q(u)为先验概率；pN(y|u)=P((Y1Y2…YN)=y|(U1U2…UN)=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是(y1y2…yN)与(u1u2…uN)对应位置值不相同的位数；（以后将称d为Hamming距离）第九页，共二十七页，2022年，8月28日2023/3/139§5.1离散信道编码问题记w(y)=P((Y1Y2…YN)=y)。我们知道第十页，共二十七页，2022年，8月28日2023/3/1310§5.1离散信道编码问题最大似然概率准则最小距离准则（最小错误准则）y与u的Hamming距离定义为(y1y2…yN)与(u1u2…uN)对应位置值不相同的位数，记为d(y,u)。第十一页，共二十七页，2022年，8月28日2023/3/1311§5.1离散信道编码问题命题最大似然概率准则等价于最小距离准则。证明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是y与u的Hamming距离。注意到p/(D-1)<(1-p)。所以pN(y|u)达到最大，当且仅当y与u的Hamming距离达到最小。得证。第十二页，共二十七页，2022年，8月28日2023/3/1312§5.1离散信道编码问题命题如果每个码字是等概出现的，则最大后验概率准则等价于最大似然概率准则。证明第十三页，共二十七页，2022年，8月28日2023/3/1313§5.1离散信道编码问题对两种译码准则的评述最大后验概率准则具有很好的直观合理性。收到y的条件下，最可能发送的是哪个码字，就认为发送的是哪个码字”。最大似然概率准则（最小距离准则）所具有的直观合理性弱一些。发送哪个码字的条件下，最可能收到y，就认为发送的是哪个码字。最大似然概率准则（最小距离准则）的实现比最大后验概率准则的实现更简单：前者只需要看哪个码字与y的Hamming距离最小；后者需要知道各码字的概率分布，然后用贝叶斯公式计算并比较后验概率。两种准则都可以用在没有编码（直接发送）情况下的纠错译码。第十四页，共二十七页，2022年，8月28日2023/3/1314§5.1离散信道编码问题例(p143)BSC信道的转移概率矩阵为取L=1。如果直接将X1输入信道，信道的输出为X1’，则①当信道传输错误时无法检测到。②正确接收的概率为P(X1’=X1)=1-p。今取L=1，N=4，二元(4,1)码如下：0→0000，1→1111。第十五页，共二十七页，2022年，8月28日2023/3/1315§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。译码规则显然是最小距离准则。

第十六页，共二十七页，2022年，8月28日2023/3/1316§5.1离散信道编码问题何时检测到信道传输错误？当(Y1Y2Y3Y4)不是一个码字时，检测到信道传输错误。换句话说，(Y1Y2Y3Y4)与原发码字(U1U2U3U4)的Hamming距离≥1且≤3时，检测到信道传输错误。因此，信道传输有错误但能检测出错误的概率为第十七页，共二十七页，2022年，8月28日2023/3/1317§5.1离散信道编码问题何时正确译码（正确接收）？当(Y1Y2Y3Y4)与原发码字(U1U2U3U4)的Hamming距离≤1时，正确译码；当(Y1Y2Y3Y4)与原发码字(U1U2U3U4)的Hamming距离=2时，一半能正确译码，另一半不能正确译码；当(Y1Y2Y3Y4)与原发码字(U1U2U3U4)的Hamming距离≥3时，不能正确译码。正确译码（正确接收）的概率为第十八页，共二十七页，2022年，8月28日2023/3/1318§5.1离散信道编码问题第十九页，共二十七页，2022年，8月28日2023/3/1319§5.2~3离散信道编码定理首先需要说明，上述离散信道编码的编码速率（信息率R

）本来是设备所确定的。当信源每秒产生ns个字母，信道编码所使用的设备每秒产生nc个字母，则设备所确定的编码速率就是R=ns/nc。其次，实际编码速率（实际信息率L/N

）必须不小于设备所确定的编码速率：L/N≥R。于是对离散信道编码有了以下两条相互矛盾的要求：（1）实际编码速率L/N尽可能小以便使正确译码（正确接收）的概率尽可能接近1。（2）实际编码速率不小于设备所确定的编码速率L/N≥R。第二十页，共二十七页，2022年，8月28日2023/3/1320§5.2~3离散信道编码定理设信源序列经过信源编码后变成了如下的序列…X-2X-1X0X1X2…。设各随机变量独立同分布。记H(X)为X0的熵，C为信道容量。如果设备所确定的编码速率R<C/H(X)，则能够同时满足以下两条要求：（1）L/N使正确译码（正确接收）的概率尽可能接近1。（2）L/N≥R。如果设备所确定的编码速率R>C/H(X)，则不能够同时满足这两条要求。（如果设备所确定的编码速率R=C/H(X)，则情况如何？很复杂，属于边界情况，没有简单整齐的结论。）第二十一页，共二十七页，2022年，8月28日2023/3/1321§5.2~3离散信道编码定理定理(p152)（Shannon信道编码定理）如果设备所确定的编码速率R<C/H(X)，则对任何正整数L（L=1，2，…），存在D元(N,L)码和对应的译码方法，使第二十二页，共二十七页，2022年，8月28日2023/3/1322习题课5.l设有一DMC，其转移概率矩阵如下。若Q(x1)＝l/2，Q(x2)＝Q(x3)＝1/4，试求最佳译码判决以及误码率。第二十三页，共二十七页，2022年，8月28日2023/3/1323习题课[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)，第二十四页，共二十七页，2022年，8月28日2023/3/1324习题课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))=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|