第五章信道编码定理(一)

1、2022-4-261第五章：第五章：信道编码定理（一）5.1 离散信道编码问题离散信道编码问题5.23 离散信道编码定理离散信道编码定理2022-4-2625.1 离散信道编码问题离散信道编码问题设信道是一个D元字母输入/ D元字母输出的DMC信道，字母表为0, 1, , D-1。其信道转移概率矩阵为DD矩阵如下。这是一个对称信道。信道传输错误的概率定义为P(输出不等于k|输入为k)= p，k0, 1, , D-1。此处pL，且变换是单射（即(X1X2XL)的不同事件映射到(U1U2UN)的不同事件）。将(U1U2UN)输入信道；信道的输出为(Y1Y2YN)；再根据根据(Y1Y2YN)的值猜测

2、出输入信道的值的值猜测出输入信道的值(U1U2UN)，并根据变换式(U1U2UN)=C(X1X2XL)将(U1U2UN)反变换为(X1X2XL)。如果(X1X2XL)=(X1X2XL)，则正确接收。2022-4-2655.1 离散信道编码问题离散信道编码问题（1）(X1X2XL)的事件共有DL个，因此(U1U2UN)的事件共有DL个，占N维向量值的份额为DL/DN=1/DN-L。因此当信道传输错误时，有可能使输出值(Y1Y2YN)不在这1/DN-L份额之内。这就是说，信道传输错误有可能被检测到。（2）如果精心地设计变换C(X1X2XL)=(U1U2UN)和猜测规则(Y1Y2YN)(U1U2UN

3、)，则正确接收的概率远远大于(1-p)L。 （3）变换(X1X2XL)(U1U2UN)=C(X1X2XL)称为信道编码信道编码，又称为(N, L)码码。一个事件的变换值称为该事件的码字码字。L称为信息长，N称为码长。2022-4-2665.1 离散信道编码问题离散信道编码问题（4）过程(Y1Y2YN)(U1U2UN)(X1X2XL)称为纠错译码纠错译码。当(X1X2XL)=(X1X2XL)时称为正确译码（实际上就是正确接收）。（5）N比L大得越多，1/DN-L份额越小，信道传输错误不在这1/DN-L份额之内的可能性越大，即信道传输错误越容易被检测到。但N比L大得越多，信道传输的浪费越大。（6）

4、称R=L/N为编码速率，也称为信息率。（似乎与信源编码相互倒置？）2022-4-2675.1 离散信道编码问题离散信道编码问题关于译码准则关于译码准则当信道的输出值为y时，将其译为哪个码字u最合理？最大后验概率准则最大后验概率准则简记b(u|y)=P(U1U2UN)=u|(Y1Y2YN)=y)。称b(u|y)为后验概率。最大后验概率准则：。译为码字将输出值时，当跑遍所有码字)0()0()|(max)|(uyyubyubu2022-4-2685.1 离散信道编码问题离散信道编码问题后验概率的计算：记q(u)=P(U1U2UN)=u)，称q(u)为先验概率；pN(y|u)=P( (Y1Y2YN)=

5、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)d(1-p)N-d，其中d是(y1y2yN)与(u1u2uN)对应位置值不相同的位数；（以后将称d为Hamming距离）2022-4-2695.1 离散信道编码问题离散信道编码问题记w(y)=P(Y1Y2YN)=y)。我们知道（贝叶斯公式）；（全概率公式）；跑遍所有的码字跑遍所有的码字cNNNuNcypcquypuqywuypuqyubuypuqyw)|()()|()()()|()()|()|()()(2022-4-

6、26105.1 离散信道编码问题离散信道编码问题最大似然概率准则最大似然概率准则最小距离准则（最小错误准则）最小距离准则（最小错误准则）y与u的Hamming距离定义为(y1y2yN)与(u1u2uN)对应位置值不相同的位数，记为d(y, u)。译为码字将输出值时，当跑遍所有码字)0()0()|(max)|(uyuypuypNuN。译为码字将输出值时，当跑遍所有码字)0()0(),(min),(uyuyduydu2022-4-26115.1 离散信道编码问题离散信道编码问题命题命题 最大似然概率准则等价于最小距离准则。证明 pN(y|u)=P(Y1=y1|U1=u1)P(Y2=y2|U2=u2

7、)P(YN=yN|UN=uN)=(p/D)d(1-p)N-d，其中d是y与u的Hamming距离。注意到p/D(1-p)。所以pN(y|u)达到最大，当且仅当y与u的Hamming距离达到最小。得证。2022-4-26125.1 离散信道编码问题离散信道编码问题命题命题 如果每个码字是等概出现的，则最大后验概率准则等价于最大似然概率准则。证明)|(max)()()()|()(max)|(max)0(uypywuqywuypuqyubNuNuu跑遍所有码字跑遍所有码字跑遍所有码字2022-4-26135.1 离散信道编码问题离散信道编码问题对两种译码准则的评述对两种译码准则的评述最大后验概率准则

8、具有很好的直观合理性。收到y的条件下，最可能发送的是哪个码字，就认为发送的是哪个码字”。最大似然概率准则（最小距离准则）所具有的直观合理性弱一些。发送哪个码字的条件下，最可能收到y，就认为发送的是哪个码字。最大似然概率准则（最小距离准则）的实现比最大后验概率准则的实现更简单：前者只需要看哪个码字与y的Hamming距离最小；后者需要知道各码字的概率分布，然后用贝叶斯公式计算并比较后验概率。两种准则都可以用在没有编码（直接发送）情况下的纠错译码。2022-4-26145.1 离散信道编码问题离散信道编码问题例例5.1.1(p115) BSC信道的转移概率矩阵为取L=1。如果直接将X1输入信道，信

9、道的输出为X1，则当信道传输错误时无法检测到。正确接收的概率为P(X1=X1)=1-p。今取L=1，N=4，二元(4, 1)码如下：00000，11111。 pppp112022-4-26155.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。译码规则显然是最小距离准则。最小距离准

10、则。 2022-4-26165.1 离散信道编码问题离散信道编码问题何时检测到信道传输错误？当(Y1Y2Y3Y4)不是一个码字时，检测到信道传输错误。换句话说，(Y1Y2Y3Y4)与原发码字(U1U2U3U4) 的Hamming距离1且3时，检测到信道传输错误。因此，信道传输有错误但能检测出错误的概率为133422243114)1 ()1 ()1 (ppCppCppC2022-4-26175.1 离散信道编码问题离散信道编码问题何时正确译码（正确接收）？当(Y1Y2Y3Y4)与原发码字(U1U2U3U4) 的Hamming距离1时，正确译码；当(Y1Y2Y3Y4)与原发码字(U1U2U3U4) 的Hamming距离=2时，一半能正确译码，另一半不能正确译码；当(Y1Y2Y3Y4)与原发码字(U1U2U3U4) 的Hamming距离3时，不能正确译码。正确译码（正确接收）的概率为222431144004)1 (21)1 ()