新万博竞彩app > 新万博竞彩app下载 >

信息论5章 有噪信道编码定理

  第5章有噪信道编码信息论 哈尔滨工业大学(威海) 计算机科学与技术学院 第1节引言第2节错误概率与译码规则 第3节错误概率与编码方法 第4节有噪信道编码定理 第5节联合信源信道编码 第5章有噪信道编码 无噪信道编码定理:若信道的信息传输率R不大于信道容量C,总能对信源的输出进行适当的编 码,使得在无噪无损信道上能无差错的以最大信 息传输率C传输信息;若R大于C,则无差错传输 是不可能的。 本章的核心问题(有噪信道编码):在有噪信道中怎样使消息通过传输后发生的错误 最少? 理论基础:香农在1948年发表的论文《通信的数学理论》中 提出并证明了的信道编码定理(香农第二定理)。 第1节引言第2节错误概率与译码规则 第3节错误概率与编码方法 第4节有噪信道编码定理 第5节联合信源信道编码 第5章有噪信道编码 信源编码器 信道 译码器 消息信号 信号+干扰 消息 噪声源 信源编码 信道编码 加密编码 信道译码 信源译码 解密译码 干扰 2.1 错误概率与译码规则 信道编码器f信道 信道译码器F 为了提高传输的可靠性,可在信道的前端和后端分别加入 信道编码器和信道译码器,从而组成一个新的信息传输通 道——编码信道: 编码信道2.1 错误概率与译码规则 2.1错误概率与译码规则 信道译码也是一个函数,记为F。与信源编码一样,信道编码也是一一对应变换。 信息到达信道输出端后,要经过译码过程才到达信宿。译码过程和译码规则对系统的错误概率影 响很大。 译码规则对错误概率的影响:例:设有一个二元对称信道,其输入符号等概率分布 0.20.8 0.8 0.2 当信道输出端接收到符号0时,译码器若把它译成0,则译对的可 能性只有0.2,译错的可能性是0.8,此时,译码错误概率为0.8。 反之,若译码器根据这个特殊信道制定出一种译码规则,把输出端 的0译成1,把1译成0,则译错的可能性就减少了,为0.2;译对的可 能性增大了,为0.8。此时,译码错误概率为0.2。 可见,错误概率既与信道的统计特性有关,又与译码规则有关。 10 定义5.1 信道译码函数F是从输出符号集B到输入符号集A 的映射 其含义是:将接收到的符号 译为某个输入符号 译码函数又称译码规则。 信道信道译码器F 2.1错误概率与译码规则 11 对于同一个信道可制定出多种译码规则。 0.80.2 0.1 0.9 2.1错误概率与译码规则 12 同一个信道可供选择的译码规则有多种,我们必须从中 找出一个“好”的译码规则,“好”的标准是什么? 平均差错率最小。 在信道输出端接收到符号b 译为,若此时信道输入刚好是 ,则称为译码 正确,否则称为译码错误。b 的译码错误概率为: 2.1错误概率与译码规则 13 译码错误概率的统计平均值称为平均译码错误或平均差错 率,记为 显然,与译码规则F有关。使 小的译码规则才是 好的译码规则。为方便计算,可将 的计算式化为: 2.1错误概率与译码规则 14 0.80.2 0.1 0.9 例:假设P(0)=0.4,分别求出4种译码规则所对应的平均差错率。 2.1错误概率与译码规则 15例:参见前图,假设P(0)=0.4,分别求出4种译码规则所 对应的平均差错率。 解:信道输入矩阵和转移矩阵分别为: ]=[0.40.6] 0.80.2 0.10.9 则联合概率矩阵为:XY 0.32 0.08 0.060.54 (0.320.08) 0.6 2.1错误概率与译码规则 16 其他译码规则所对应的平均差错率分别为: )=0.864种规则相比, 最差。2.1 错误概率与译码规则 17 从这个例子可以看出,对于给定信道,可以制定出多种 译码规则,这些规则有好有坏,那么如何定出好的规则 如果把所有译码规则都穷举出来,算出所有的平均差错率,再进行比较,当然能找出最好的规则,但太费力。 下面我们讨论找出好规则的方法。 2.1 错误概率与译码规则 18 极大似然译码规则2.1 错误概率与译码规则 19 2.2 最佳译码规则 最佳译码规则:使P 达到最小的译码规则。由平均差错率的表达式可以看出,要减小P 必须增大各个符号的译码正确概率 。译码正确概率 与译码规则密切相关,如果所有的 (j=1,2,…,s)都是最大的,那么P 20可按如下方法来确定最佳译码规则: 比较后验概率:其中必有一个最大,则 它对于每一个输出符号均译成具有最大后验概率的那个输入符号,所以又称最大后验概率译码规则。 2.2 最佳译码规则 21 思考:是否可以等价成最大联合概率条件? 所以又称最大联合概率译码规则。2.2 最佳译码规则 22 结论: 最佳译码规则最大后验概率译码规则 (在后验概率矩阵中的每一列寻找最大的那个) 最大联合概率译码规则 (在联合概率矩阵中的每一列寻找最大的那个) 2.2 最佳译码规则 二者等价,都是最佳译码规则,但使用起来后者更方便。 23 结论:最佳译码规则(平均差错率最小) 最佳译码规则最大后验概率译码规则 (在后验概率矩阵中的每一列寻找最大的那个数) 最大联合概率译码规则 (在联合概率矩阵中的每一列寻找最大的那个数) 2.2 最佳译码规则 二者等价,都是最佳译码规则,但使用起来后者更方便。 24例:求前例的最佳译码规则,设P(a )=0.4。已求出联合概率矩阵为: XY 0.32 0.08 0.060.54 2.2最佳译码规则 25 若按后验概率算: 得到同样的译码规则:XY 0.8421 0.1290 0.15790.8710 2.2最佳译码规则 26 最佳译码规则所对应的平均差错率最小,从这个意义上讲, 是最好的译码规则。但实际应用中,经常只知道信道的统计 特性,就是只知道转移概率,而不知道信源的统计特性,这 时,求不出联合概率和后验概率,因此,无法确定最佳译码 规则。那怎么办? 按最大转移概率条件来确定的译码规则,称为极大似然译码 规则. 那只能按照转移概率的某种约束条件制定译码规则。 2.3 极大似然译码规则 27 极大似然译码规则的平均差错率不是最小,因此不是最佳的,但容易找出,只需已知信道的特性即可。 2.3 极大似然译码规则 28 例:信道矩阵如下,试确定译码规则: 0.50.3 0.2 0.20.3 0.5 0.3 0.3 0.4 由于已知条件中只给出了转移概率,因此无法求出极大似然译码规则对应的差错率。 2.3 极大似然译码规则 29 本例中,没有告知输入概率,只能采用极大似然译码规则, 而且还不知道差错率是多少,使用该规则是否可靠? 这种担心是多余的。因为,在实际系统中,信源发出的序列 在送到信道之前都经过信源编码,经过有效信源编码,输出 码元的概率分布会均匀化,所以信道的输入分布近似为等概 率分布。 当信道输入概率等概率时,极大似然译码规则也是最佳的。 怎么证明? 2.3 极大似然译码规则 30 这样,就得到了最大联合概率条件,由此说明,输入等概时,极大似然译码规则与最大联合概率译码规则等价,因 此是最佳的。 这一结论有很大实际意义,因为信道前级有信源编码器存 在,使得信道输入近似等概,采用最方便的译码规则—— 极大似然译码规则,尽管不会使平均差错率最小,但也接 近,因此可以放心使用。 2.3极大似然译码规则 31 例:设有一信道矩阵,其信道转移矩阵为: )=1/4,分别按最小错误概率准则(最佳译码规则)与极大似然译码规则确定译码规 则,并计算相应的平均错误概率。 2.4 最佳译码规则与极大似然译码规则举例 32 按最小错误概率准则(最佳译码规则):24 11 2.4最佳译码规则与极大似然译码规则举例 33 第1节引言 第2节错误概率与译码规则 第3节错误概率与编码方法 第4节有噪信道编码定理 第5节联合信源信道编码 第5章有噪信道编码 34 0.50.5 P=0.99P=0.01 P=0.01 0.99 3.1错误概率与编码方法 例:二元对称信道 在信源与信道之间不加信道编码时,由于信道输入等概 率,这时极大似然译码规则就是最佳译码规则。 求极大似然译码规则?平均差错率? 35 转移矩阵: 0.990.01 0.010.99 (0.990.99) 10 一般来说,信息传输系统的平均差错率要求控制在10-6 以下,而10 -2 太高,采取什么措施减低平均差错率? 3.1 错误概率与编码方法 36 即使选择最佳译码规则,也只能使其有限的减少,难以满足信息传递系统可靠性要求 要进一步降低平均差错率,必须先对信源(包括信源编码器)送来的序列进行可靠性变换——信道编码,然后 送入信道传送。 3.1 错误概率与编码方法 37 信道编码(纠错编码):增加“冗余”码元来克服或减轻噪声的影响。 这里所说的“冗余”是相对于信息的表示而言,对提高传送可靠 性来说,“冗余”码元却提供了极宝贵的可靠性信息。 信源编码与信道编码作比较: 信源编码和信道编码都是用码元来 表示消息符号,但目的不一样,因此所采用的方法也不一样。 信源编码的目的是为了改造信源的自然属性,通过去“冗余”来 提高信源的信息含量效率,常采用变长编码方法; 信道编码的目的是为了提高传输可靠性,需要增加“冗余”码元 来附加一些可靠性信息到传送序列中,常采用定长编码方法。 3.1 错误概率与编码方法 38 0.50.5 P=0.99P=0.01 P=0.01 0.99 信源编码器信道 信道编码器3.1 错误概率与编码方法 39 3.1 错误概率与编码方法 对符号串编码40 3.2 “简单重复”编码 启发:与人交流,重复一遍或多遍,别人会听的更清楚。 数字通信中,将符号重复传送几次,也会提高传送的可 例如,为实现“重复2次”传送,可在信源与信道之间加入编码器,对信源符号进行“重复2次”编码。 41 000111 没有使用的码字 用做消息的码字 000001 010 011 100 101 110 111 000111 3.2“简单重复”编码 信道编码器f 42“重复2次”编码规则为: pppp pppp 按极大似然译码规则译码:3.2 “简单重复”编码 43 000001 000 010 100 011101 111 110 111 这实际是一种择多译码方法,即:比较接收序列中0和1的个数,0多则译为0,1多则译为1。或者说,将接收 序列译为与之最相似的输入序列。 译码的平均差错率为: 3.2“简单重复”编码 44 降低了近2个数量级,原因在于这种编码和译码能够纠正1位码元的错误。若增加“重复”的次数,会使P 进一步降低。可见,当n很大时,使P 很小是可能的。但是,在重复编码次数增大,平均错误概率P 下降的同时,信息率也要减小。编码后信道的信息传输率为: 若信源等概率分布,则:3.2 “简单重复”编码 45编码之后的信息率下降了,原因在于信道编码用较多的码元 来传递同样多的信息,分摊到各个码元上的信息降低了。随 着“重复”次数的增加,P 比元 比特 码元 比特 码元 比特 码元 比特 码元 3.2 “简单重复”编码 46 “重复2次”编码,是对信源的单个符号进行编码,即把一 个符号看作一则消息,那么二元信源有2种不同的消息。 随着“重复”次数增加,码长n增大,编码后的信息率R必然 下降。 为了提高R,可以增加信源的消息个数q。如下面我们要 介绍的对符号串进行编码。 3.2 “简单重复”编码 47 对于二元信源U,若取二元符号串“00,01,10,11”作 为消息,则消息个数增加为4个。对信源U的二元符号串 进行编码,相当于对2次扩展信源U 进行编码。因为原信源等概率分布,那么扩展信源也等概率分布。 还是取码长为N=3,则编码后的信息率为: 比原来的R= 增大了一倍。R增大,是我们所希望的。 3.3对符号串编码 bit/symbol loglog 48码长=3时,可供选择的码字有8个: =111要从8个可选的码字中选出4个分别赋给4个信源消 息,共有 种不同的选法或编码方法。 00000 01 010 10100 11 110 3.3对符号串编码 49 转移矩阵为: pppp pppp pppp 3.3对符号串编码 50 译码的平均差错率为: 比q=2时的平均差错(3*10-4 )率大,与我们的愿望相反。 有70种编码函数可供选择,编码函数不同,差错率也会 有差异。可以算一下,都比q=2时的差错率高。 因此,增多消息个数q在提高信息率的同时,会使平均差 错率增大。 3.3 对符号串编码 51 提高。增大码长N,同时适当增多消息个数q,有可能使平均差 降低到要求的范围之内,而又能使信息率R不降低,或降低不多。 3.3 对符号串编码 52 例如,取q=4,N=5。四个消息记为: =11编码函数为: 供选择的码字共有2 3.3对符号串编码 53 其码长为5,码字的前2个码元是信息位,后3个码元是校验位; (N,K)分组码:码长为N,信息位数目为K,那么校验位数目为N-K。 编码采用(5,2)分组码,译码采用极大似然规则,则:3.3 对符号串编码 54 00 00000 01 01101 10 10111 11 11010 0000000001 00010 00100 01000 10000 10001 00011 01101 01100 01111 01001 00101 11101 11100 01110 00000 10111 10110 10101 10011 11111 00111 00110 10100 11010 11011 11000 11110 10010 01010 01011 11001 0110110111 11010 5次扩展信道 无需求出5次扩展信道的转移矩阵,用下面我们要介绍的 “汉明距离”。 3.3 对符号串编码 55 这种情况下,编码后的信息率R和平均差错率P 分别为:log 比元 却下降了2个数量级;与q=2,N=3的重复码相比,信息率R增大, 平均差错率P 处在同一个数量级。因此,增大码长N且适当增多消息个数M,对降低P 时又使R不降低或降低不多,是有效的。3.3 对符号串编码 56 前面已经讨论过,可将接收序列译为最“相似”的输入序列 (码字)。如何定量描述符号序列之间的“相似”程度呢? 汉明受距离概念的启发,在符号序列之间引入汉明距离,用 来定量描述符号序列之间的“相似”程度。 定义: 两个等长符号序列 注意:汉明距离只对等长符号序列才有定义,对于不等长符号序列无定义。 3.4 汉明距离 57 例如: 101111 例如:100111 111000 111111 的相似程度高于与的相似程度。 3.4 汉明距离 58 不难证明,汉明距离 满足如下性质(距离公理): 如果是二元序列,记 3.4汉明距离 59 对于二元序列,还可引入汉明重量的概念。二元序列 含“1”的个数,称为的汉明重量,记为 3.4汉明距离 60 最小码间距离dmin min小,其中有些码字受干扰后容易变成另一码字,译 码时就会出错; 信道编码在选择码字组成一个码时,尽量使码的最小码间距离大一些为好。 3.4 汉明距离 码C的最小码间距离:min min[ 61对于二元对称信道,可以根据汉明距离来决定译码规则。 信道编码器f 信源有q个消息,二元对称信道的输入符号集和输出符号集分别为A={0,1}和B={0,1},其N次扩展信道的入口符号集A 3.4汉明距离 62 3.4汉明距离 63 根据信道无记忆性质,转移概率为: =1-p,于是转移概率又可表示为: 3.4汉明距离 64 正常情况下,正确概率 大于错误概率 ,或者说p

  C,任何编码的P 同无失真信源编码定理类似,信道编码定理也是一个理想编码的存在性定理,它指出信道容量是一个临界值,只要信息 率不超过这个临界值,信道就可几乎无失真地把信息传送过 去。否则就会产生失线节错误概率与译码规则 第3节错误概率与编码方法 第4节有噪信道编码定理 第5节联合信源信道编码 第5章有噪信道编码 73 多数通信系统都是数字通信系统,它比模拟通信系统有许多优点。在实际数字通信系统中,常常信道是共同公用的数字信 道,一般为二元信道。无论是语音、音乐、图像、数据都用同 一通信信道来传输。 将语音、图像等首先数字化,再对数字化的语音、图像等信源进行不同的信源编码。针对各自信源的不同特点,进行不同 的数据压缩,用最有效的二元码来表达这些不同的信源。 对共同传输的数字信道而言,输入端只是一系列二元码。所以,信道编码只需针对信道特性而进行,不用考虑不同信源 的不同特性。这样通过信道编码可以纠正信道中带来的错误, 就可做到既有效又可靠的传输信息。 第5节联合信源信道编码 74 分两步处理的方法,其信源压缩编码只与信源有关,不 依赖于信道;而信道编码只与信道有关,不依赖于信源 。这样做,可以大大降低通信系统的复杂度。 正因为通过分别进行信源的数据压缩编码和信道的数据 传输编码,既能做到有效又可靠的传输信息,又能大大 的简化通信系统的设计,因此在实际通信系统中得到广 泛应用。针对各种不同信源如文本、语音、静止图像等 数据压缩的研究形成了数据压缩理论与技术;而针对信 道编码问题的研究又形成了另一独立的分支——纠错码 理论。 第5节联合信源信道编码