Informationtheory(信息论与编码)

1、Information theory ?=? ?=? 即是满足保真度准则 ?= ?= ?条件下，？?= ? = ?= ?g?- ?(?/?)这时必须 记住，构造的试验信道是满足 平均交互信息等于 0的条件。即此时？?= ? = 0为什么？即 是说，在保真度要求很低，此时相当于信道独立，不需要传输任何信息。但是这种情况也不可取， 因为没有意义。 (3)?(?) 此时我们来看一般的情况，两种极端我们都分别验证了。不失一般性，可以这样理解平均失真度。 可以理解为信道把符号 ？賢?= 0,1,r)错误的传输为符号？?労？?的错误传递概率。即错误概率？初? H?工?(?？?。 对于?个符号信源来说，平均

2、失真度？?就等于信道的平均错误传递概率?,即 ? ? ? ?=刀刀？(?)?？(？?？=刀？?(?刀?(?/?=刀？?(?刃?？ ? ?=1 ?工?=1?工?=1 ?= ?= ?- ?/? ? ?;?;?= ?(? =? ?-?(?) A 7 V 对于一般的二元离散无记忆信源？来说，r = 2，所以？ = ?:? - ?. 因此，在概率分布为(?,1 - ?)(? 1/2)的二元离散无记忆信源 ？?在汉明失真度下的信息率-失真函 数 ?3 = ?彳？)-?,?客? ? / V 7 ? ?- ? ? ?/? ?/? 当r=2时，此时表明在汉明失真度下，二元 等概离散无记忆信源 X的信息率-失真函

3、数为: ? = ?. ?(? ? ? ?/? ?.? ? TX 实际求解条件熵？?(?/?？?-?)在?TX时的极限值，就相当于把信源X当作无限记忆长度的 信源来处理(unbelievable, harsh!).然而对于某些特殊的离散平稳有记忆信源，如马尔科夫(Markov) 信源，不需测定无穷多维条件概率和联合概率，就可求出条件熵？?(?？/?-?在? t X时的 极限值，极限熵?. 马尔科夫信源的特征：信 源序列中某个符号只于前面m个信源符号有关，与更前面的符号没有 任何关系。这种信源序列 X称为m阶Markov信源(简称m-M信源)。其是有记忆信源，但是记忆 不会延伸至无限长， 只有m阶

4、。离散平稳m阶Markov信源的消息的n步转移概率矩阵p(n),等于 消息的一步转移概率矩阵P的n次连乘.即有 ? = ? 离散平稳各态历经的 m-M信源X的符号集X: ?，则离散平稳各态历经m-M信源的X的 极限熵？X即卩 ?X = ?(?+?/?. ?) 我们考试中遇到的有记忆信源都是马尔科夫信源，不会是无限长记忆的信源，那样根本不现实，计 算太复杂了。另外也只会出现2次扩展，2次扩展的信源其是就可以理解为 2阶的马尔科夫信源， 这样我们计算极限熵就可以直接等于条件熵，这就是理论来源。在实际的解题中也会经常会给出条 件转移概率，然后需要联立方程组求解每个消息的概率。为什么要联立方程组？其实

5、这也是各信源 符号之间还存在相互依赖关系的体现，只有通过联立求解才能得出结果。 例如，某个信源概率空间分布未知，但是已知条件转移概率矩阵如下 P = (0.90.1) (0.20.8) 矩阵的含义为：p(ee1)=0.9, p(e2/e”=0.1, p(ee2)=0.2, p(e2/e2)=0.8.根据此转移概率矩阵的关系，求解 出发送消息?)=刀?(?刀？?(?？ ?工?=1?=1?=1?工? 简单点，所有的错误概率就是将概率转移矩阵中译码正确的概率排除，然后 将所有的译码错误的概率相加。这种译码方式为最大后验概率准则，即选取最大后验概率的码符号 译码。即?(? ?(?/?时，?(? = ?

6、优而？坊?则是将第i行对应的排除正确的转移概率之外的 其他概率相加。 假设在信源等概的情况下，就可以推导出一种极大似然译码准则，此时选取信道转移概率最大的作 为译码信符。 ? ? 1 ?=刀刀？?(?(？?？ = ?产刀？(?？ ?工？=1 ?工？=1 最大似然译码准则的最小平均错误译码概率？?也就是等概信源 X各信源符号在发出的前提下， 用极大似然译码准则所产生的最小错误译码概率？易?的算术平均值。很显然，极大似然译码准则是 最大后验概率译码准则的特殊情况！ ！ 对于给定的通信系统，信道转移概率固定，因此错误概率是由信源概率分布决定的，当信源概率分 布确定后，最小错误概率是固定不变的。最小平

7、均错误概率是给定通信系统的信息特征参量。 最小平均错误概率译码准则：分为极大似然译码准则和最大后验概率译码准则。这两种译码准则的 错误概率都是有信道转移矩阵决定，由于没有增加冗余，所以可靠性很难得到提升。 具体的方式，例子如下: 信道的转移矩阵为 3 tb q 0.5 0.3 0.2 P a2 0.2 0.3 0.5 a3 0.3 0.3 0.4 假定信源概率分布相等，此时根据极大似然准则译码，能使平均错误概率达到最小值。 译码规则为(接收？?译码成？?是任意的，因为三个概率相等) ?) = ? ?) = ? ?) = ? 最小平均错误概率 3 1? ?方?尹刀？韵 ?工?=1？? 1 =-X

8、 (0.2+ 0.3) + (0.3+ 0.3) + (0.2 + 0.4) = 0.57 3 其中 ?=? ?2?) ? ?叼= 0.3 + 0.2 = 0.5 ?=? ?谒 (?=3)? ? ?) 3 ? ?叼= ? ?才 0.2 + 0.3 + 0.3 0.4 0.5 0.7 _ 1 ?=?刀 ? ？=1 0.57 ?；)?=?X (0.5 + 0.5 + 0.7) 3 汉明距离与最小误码率 设给定的信道编码和给定信道的传递特性，如何选择适当的译码规则，使其平均误码率？?达到最小 值?Hamming Distanee给最小平均错误概率注入了新的含义。译码规则的选择可明显地改变码 字误码率

9、的大小。对信道编码系统来说，信道编码、译码规则和信道传递特性，是影响码字误码率 的主要因素。 1. 在信道编码 C的M个码字？?先验等概的条件下，若 ？?,? ?羽?？(i=1,2,M则选 用译码规则？?(?？= ? (j=1,2,.2 n).其平均误码率？?达到最小值？加?？ 2. 在信道编码 C的M个码字？?先验等概的条件下，信道编码C中任何两个不同码字？?和？?的最小 则选择译码规则译码的最小平均错误译 汉明距离min越大，采用最大似然译码准则, ?M? 码概率？?就越小。 信道编码定理： ? ?= -?-? M为码字数，？平均码 香农信道编码定理并没有给出具体的信道编码定理，但是给出了

10、数学上的指导意义。一个通信系统 的好坏，很大程度上取决于其有效性和可靠性的大小。我们根据前面的有效性定义，定义信道编码 有效性的概念。平均每个码字(码符号)能携带的信息量，即码率 长，一般为定长码，比较简单。信道编码定理告诉我们，能存在一种R接近于C且？?接近于0的 信道编码方式。这表明存在一种有效性达到最大，无错误的编码方式。 6. 线性分组码 信道编码最为关键的是求出生成矩阵，一个生成矩阵就对应一种信道编码方式，接下来会有一致 检验矩阵等相关概念。但是在介绍这些复杂的概念之前，我们必须清楚一些基础知识。 前面的信道编码定理可以告诉我们，通过增加冗余位可以有效的增加可靠性，那么怎样去编写这些

11、 冗余位。这个系统的数学模型是什么，这是非常关键的！信源存在信息序列，怎样将其映射成对应 的码字呢？线性分组码的概念就因此提出来了。我们的信息序列有k位，我们现在码字有 n位。其 中n=k+r，r位就是冗余位。按照数学上理解，我们将 k维k重的线性空间映射到k维n重的线性空 间中。线性分组码(n,k)就是一种固定的叫法，我们取不同的值，就会生成常见的码字。(N,N-1)分组 码称为奇偶校验码。 (n.k)分组码能发现小于或等于f个错误的充分必要条件是 (n,k)分组码的最小汉明距离 ？?= ?+ ? (n,k)分组码能自动纠正小于或等于e个错误的充分必要条件是，(n,k)分组码的最小汉明距离

12、?=?+?(n,k)分组码能自动纠正小于或等于e个错误，同时又能发现f(fe)个错误的充分必要 条件是，(n,k)分组码的最小汉明距离 ？?= ?+ ?+ ? 生成矩阵和一致检验矩阵 生成矩阵G的特点：对于(n,k)分组码，其码字有 2k个，信息位也有2k个，冗余位为r。生成矩 阵为k行n列。信息位乘以生成矩阵，就得到相应的码字。信息位矢量为1行k列，生成矩阵位k 行n列，正好计算出对应的 n位码字。生成矩阵中所有的行都线性无关，可以从生成的码字中选取 k行线性无关的码字组成生成矩阵。k 系统码：系统码的生成矩阵的前k列为单位矩阵氓其他的部分为分块矩阵？?,?,?,? 凡是生成矩阵可以表示成该

13、形式的，都可以成为系统码。一个非系统码可以转化为系统码，其纠错 检错能力保持不变。此外，我们引入码字的重量的概念，码字的重量为其非零码符号的个数。(n,k)线 性分组码 W中(2 ?- 1)个非0的码字中的最小重量 ?) = ? (?,? ?, ? ? 又因为两码字的汉明距离定义类似，我们可以这样理解：假设存在一个参考重量，两码字的汉明距 离要最小，实际上就是码字的最小重量。当两个码字相对同一参考码字且做模2加的运算时，可以 不考虑参考的码型(或者理解为参考码型为 全零)，直接用最小重量表示。 这个最小重量决定了码字 的纠错能力和检错能力。当最小重量越小时，能力越差。 一致检验矩阵：首先必须明

14、确该矩阵的代数结构。该矩阵由n-k行n列组成。并且还存在很多代数 特性。一致检验矩阵 H与码字w的关系为： ?= ? ?*?= ? 但是当我们只知道生成矩阵前提下，怎样计算一致检验矩阵呢？ 很显然，一致检验矩阵 H与生成矩阵的关系为 ?= ? ?= ? ?,进行转置，变成？?,?然 我们首先将生成矩阵写成系统码的形式，然后将之前提到的分块矩阵 后在补上单位矩阵？?-?=?这个就是简单的计算形式。?,?,? 一致检验矩阵的k列矢量中，线性无关矢量的个数为检错能力 （汉明距离dmin-1），纠错能力为其一半。 自然检错能力的上限是 n-k（矩阵的秩）或者是（n,k）线性分组码的最小距离为 dmin

15、的上界是n-k+1. 错误图样和伴随式 错误图样是干啥的，为什么要定义错误图样？在（7,3）线性分组码中，若码字w=（0 1 1 1 0 1 0），经过 信道传输后接收到的码字（7 重矢量）为 R=（1 0 0 0 1 1 0）. It is obvious that the transmission is wrong. In order to correct the fault, the mod plus 2 rule has been introduced. We define the vector E=w+R=（1 1 1 1 1 0 0）. Therefore, the positio

16、n which is“因此，我们n可以发现如果能知道矢量E，则任何错 误都能纠正。此时我们正式定义矢量E为码字w的错误图样。任何码字存在自己的错误图样。另外， 码字w，接收码字R和错误图样E之间存在这样的关系： ?= ?+ ? ?= ?+ ? ?= ?+ ? 错误图样的个数问题：当E=（0 0（时，这个错误图样是零错误的错误图样。其他的凡是含有1的 错误图样都是不同错误的错误图样。总的个数为2n-1.因此就是简单的组合关系。 伴随式又是干啥的，他又有什么用？其实很easy,伴随式就是检查接收的码字或发送的码字是不是 （n,k）线性分组码！ !下面我们作如下推到，在此之前必须认可接收的码字和发送

17、的码字有相同的线 性结构。 设信道输出端的接收矢量为R,根据前面的定理有： ? ?尹=? 则可断定接收矢量 R 一定是（n,k）线性分组码的码字，若有 ？?？/工?则一定不是（n,k）线性分组码 的码字。又根据前面的错误图样的关系式：R=w+E，因此我们做出如下变换: ?尹=? ?+ ? =? ?+ ? ?= ? ? 因此令 ?= ? ?*?= ? ? 我们称S为错误图样E的伴随式，亦称为接收序列R的伴随式.？?是伴随式S的转置矩阵。这样就 能根据伴随式S来判断接收码字或者发送码字是否为（n,k）线性分组码的码字。 其实简单的引入这两个矢量是没有多大意义的！科学家往往是为了介绍自己更深层次的作

18、用而做出 的铺垫。我们发现即使有了生成矩阵和一致校验矩阵，每次接收到码字不能都去解方程吧！这样的 工作量是极为庞大的。解方程其实是这样的过程，（前提是知道 H或G）通过接收码字 R可以求出 伴随式E,求出伴随式就可以求出错误图样E,然后就可以求出 w。但是这个过程是针对一个码子， 若是码字比较多时，工作量是非常大的！ 因此，引出了标准阵列和译码表的概念。我们事根据（n,k）线性分组码的生成矩阵将所有的码字w写 岀，然后组成一个表格，这个表格就是一个标准阵列！标准阵列第一列是由伴随式组成，第二列是 由错误图样组成，后面的2k列是由2k个码字组成。 + c2 = d * * Y B- = E: +

19、 Ct = E? e2+c2 耳十q* *! t f * Ej 心 Ej E, + C J亠 * * 爲十G * A r i U J s = E J?岡峠 卄 ?严十c E + C n * - Information theory & coding | Tailong Xiao 问题是这个标准阵列怎么组成？标准阵列的第一行是固定的，首先选择零错误的错误图样E作为第 一个行第一列的元素，然后后面的第一行第二列，第三列的元素依次根据生成矩阵的码字填写。 第二行的第一列的错误图样选择最轻的错误图样(就是含1的个数最小的图样)，但是前提是这个图 样不能和前面出现的码字或错误图样重复，然后本行第2,3,

20、列的元素依次将其所在列的码字与错 误图样相加。直到错图图样选择完全为止。应该有2n-k个。一定会有疑问，为什么选择前面未出现的 最轻的错误图样？现在我先解释“未出现”的这个规定！我们知道若是选择了前面出现的码字或图样， 那么这一行的伴随式将会和重复的哪一行的伴随式重复，这是不容许发生的。因为无论是E还是R 还是w都是和伴随式存在等价变换关系。至于选择最轻的，可能是因为 本着错误最小的原则，或许 我的猜想是正确的，我们肯定先选择译码错误最小的码字！ 值得注意的是：伴随式和错误图样的个数是不一样的！伴随式的个数为2n-k个，但是错误图样的个数 为2k个。一个接收码字对应一个伴随式，然后根据伴随式再

21、去解错误图样，此时得到错误图样的解 个数为2k个，很明显错误图样是不唯一的，因此必须选择最小的错误图样，这样才能使差错控制的 最小。 另外，怎样根据一致校验矩阵H列的线性无关数来判断纠错能力和检错能力。其实存在一种特殊的 关系。为了表达方便，设码字为？加=(?说?十？, ,?) 一致校验矩阵H : ?11 ? ?1? H = ? ? ?1 ? ? ? 设(n,k)线性分组码能纠正小于或等于e个错误，则最小汉明距离与最小重量为2e+1 则证明码字中 有2e+1个仁 (n,k)线性分组码必定满足此关系式： ?11? ?1? ?-1 ?= ?= ? ? ? ? ?=? ?1 ? ? ? 展开即有：

22、?11 ? ?-1 + ?12 ? ?-2 + ? + ?1? ?= 0 ?21 ? ?-1 + ?22 ? ?-2 + ? + ?2? ?= 0 ? ?1? ?-1 + ?2? ?-2 + ? + ? ? ?= 0 即有 ?11?12 ? 1? ? 21?23 -?1 ? ?-1 + ?3 ?-2 + ? + ?j ? =0 ?1 ?2 ? 在上面的表达式中，所有的列向量是非零的。 因为码字C中有2e+1个1则一致校验矩阵中有 2e+1 列是线性相关的，则必有 2e列是线性无关的。e为码字中错误的位数。同时又因为码字有2e+1个 1，则码字的重量就为2e+1，此时最小汉明距离 dmin就是2

23、e+1。我们知道检错能力为 dmin-1，纠错 能力为(dmin-1)/2，所以就能纠正e个错误，能检测2e个错误。总结起来，一致校验矩阵 H中列的线 性无关数为纠错数，为检错数的 2倍。 怎样才能得到生成矩阵呢？(一致校验矩阵？) 最常见的就是汉明码(hamming code),汉明码不是一种码字，而是一类码字。这种码字有什么 characteristics ?首先要有完备码的概念。完备码的必备条件为：(n ,k)线性分组码的陪集首数 ? ? 等式右边表示(n,e)的组合数，这样的码字称为完备码。这其实是大大减小了错误图样的数目，我们对 此不作理论推导。 汉明码特点：错误图样E中只能含有1个

24、1其他的全部为零。同时满足 (n,k) = (2 ?- 1,2?- 1 - r) 因此对应的伴随式也即是一致校验矩阵的列向量。到底存在怎样的对应关系呢？用一个数学公式可 以描述：？?= ?+ ?-?.本式中，将？?看做一个十进制的数。假设(15,11)线性分组码，则根据接 收的码字算出伴随式为0110,则对应的十进制为 6. n-6=9.就表明错误图样 E=(0 0 0 0 0 1 0 0 0 0 0 0 0 0 0).表明这种汉明码只具有 1位纠错能力，2位检错能力。最轻的码字重量含有 3 1. 另外怎样根据一致校验矩阵求出陪首集和伴随式集合呢？前面已经提到，一致校验矩阵的每一列都 对应一个

25、伴随式。因为错误图样只能含有1个T此时错误图样E与一致校验矩阵 H的转置相乘时， 表明只有一列能够保留下来。同时，一致校验矩阵H的编写是固定的，其每一列都是从0n-1的二 进制组成。为了突出顺序，我们一般都是从1写到n-1，这样对应的错误图样就是最高位为1,其他 的位都为0，对应的伴随式就是Hi.其实从矩阵的乘法中也能获得此信息。 (1) 为了优化算法设计，我们对于恢复码字w的运算w=R+E，般采用按位异或的方式，即将接 收到的R矢量与算出的错图图样E进行按位异或就能恢复出正确的码字。 (2) 对于矩阵的乘法，即RHt怎么优化算法？我们仅讨论矩阵的某一行。此时只需将接收矢量R与 一致校验矩阵H

26、的某一行矢量进行按位与，然后将每次得到的结果相加最后进行mod 2运算。得到 的结果就是对应伴随矢量S中某一个元素的值。 补充关于陪首集的个数问题： 根据接受码字 R，不能唯一求解出其对应的错误图样E。我们知道RHt对应唯一的伴随式 S，然后 再反解错误图样 E时，对应的解会出现很多，具体数目为多少？我们假设(n,k)线性分组码的错误图 样？?= (?,?,? ?，根据接受码字求解出的伴随式？?= (?,?,? ?.当然一致校验矩阵是已知，为 1? ? ? ?11 ?= ? ?1 ?11 ?)? ?1 ? ?1? ? ? 因此根据伴随式的定义有: ? ? = (?,?,? ? 展开得到： ?=

27、 ?= ?11 + ? ? ?21 + ?12 + ? + ? ? ?22 + ? + ? ? 1? ? ?2? ?= ? ? ?1 + ? ? ? ?2+ ? + ? ? In the equation set, there are r known variables and n unknown variables. However, only r equations cannot figure out the n variables uniquely.为了分析的简便，我们假定在n个未知量中前r个未知量是确定的， 则还剩下k个未知量是可变的，因此存在2k个解。我们希望得到2r个解，很显然需要挑选出一部分 解。那么挑选的原则是什么？在伴随式S和错误图样E的对应关系中，我们引入标准阵列的概念。 错误图样的选取是在 2k个解中优先选取最轻的错图图样来和伴随式匹配。 与汉明码对应的循环码： 循环码是另外一种信道编码的编码方式。主要是思考的角度就是简化生成矩阵的复杂。生成矩阵G 的每一行都是线性无关的，前面已经提到这些行向量都是有k