信息与编码复习要点

《信息与编码复习要点》由会员分享，可在线阅读，更多相关《信息与编码复习要点（12页珍藏版）》请在装配图网上搜索。

1、信息与编码复习要点2011.12信息的定性描述n 信息传输的基本要求：有效性 可靠性有效性信息传输的速度。可靠性信息传输的质量。n 信息系统模型：信源 信道 信宿 噪声源n 信源编码和解码：有效性，去除冗余n 信道编码和解码：可靠性，添加冗余n 信息 消息 信号n 信息论 香农信息论信息的定量描述n 信息量自信息量 条件自信息量 联合自信息量 互信息量n 平均信息量熵离散信源：自熵 条件熵 联合熵 互熵连续信源：自熵 条件熵 联合熵 互熵n 互熵的性质：非负性 互易性互熵和自熵和条件熵及联合熵关系熵不增性原理n 信源的最大熵：离散信源的最大熵连续信源的最大熵：峰值功率受限，平均功率受限香农定理

2、 若信源的信息速率R小于或等于信道容量C，那么，在理论上总存在一种方法，使信息能够以任意小的差错概率通过该信道传送。当RC时，信息在信道中传输，总要有一定误差，疑义度不会比（RC）更小。（一） 概率公式：1. 概率乘法公式： p(xy)= p (x) p (y/x)= p (y) p (x/y)当且仅当x, y相互独立时, p(xy)= p(x) p(y)2. 全概率公式：3. 逆概率公式：（二） 信息论公式1.（自）信息量：I(x) = log p(x)（自）熵：2. 条件信息量：I(x/y) = log p(x/y)条件熵：3. 联合信息量：I(xy) = log p(xy)联合熵(共熵)

3、： 4. 互信息量：互熵：5.互熵的对称性（互易性）：I(X;Y)=H(X)H(X/Y)=H(Y)H(Y/X )I(X;Y)H(X/Y)H(Y/X)H(X)H(Y)H(XY)信源编码一. 编码是把信源输出的消息变换为便于在信道中传输的信号的过程。它是信息系统中提高有效性和可靠性的关键。二. 信源编码是为了提高信息速率，有效地进行信息传输和存贮，对有剩余的消息所进行的去除剩余的编码，也叫有效（性）编码。三. 除了在传输和恢复消息时所需要的最少信息外，其余出现在消息、信号和系统中的细节都叫做剩余。剩余减小了信源的熵，降低了有效度，增加了通信的可靠性，提高了抗扰度。剩余 = HmH (信源最大熵与实

4、际熵之差) .剩余度 = (HmH)/Hm = 1H/Hm .有效度=H/Hm .四. 如果一种检验，它的结果只能属于两种状态之一，则叫做二态检验。通常把二态检验的两种状态称为“是”和“否”。五. 二态检验定理可表达为：I(平均) = p(是)log p(是)p(否)log p(否)1，当且仅当p(是) = p(否) = 1/2时，上式右端取等号。一次二态检验最多可获得1 bit的信息量；一次三态检验最多可获得log3 = 1.585 bit的信息量；一次q态检验最多可获得log q bit的信息量。六. 信源编码的效率为： = H/ ( log q)，当 q = 2 时， =H/ .其中 为

5、平均码长，H为信源的熵， 1 .七. 费诺码编码步骤：把消息按概率由大到小排序；把序列分成概率尽可能相等的两组，分别配给符号0和1；对每一组又同样分成概率尽可能相等的两组，分别续给符号0和1；重复，直到每一消息都被分隔出来为止；各消息所得到的二进制序列就是它的代码。费诺码编码方法简单，但编码效率不如哈夫曼码，称为“准最佳码”。八. 哈夫曼码编码步骤：将消息按其概率由大到小排列；把两个最小概率概括出来分别配给0和1；将这两个概率相加后再与其他概率比较，重新排序；重复步骤和，直到所有概率都相加完为止；将所配给的符号序列，按照从右到左的顺序作为相应消息的代码。哈夫曼码的编码效率最高，称为“最佳编码”

6、，但编码方法比较复杂。九. 香农码编码步骤：把信源消息的概率由大到小排序；设：p1p2pm按下式求累加概率Qi（令p0 = 0）：求各消息的信息量Ii = log pi，再按下式确定码长ni(整数)：log pinilog pi1将Qi化为二进制数，并取小数点后ni个数码作为消息xi的代码yi .香农码具有很高的理论价值，但编码方法复杂，编码效率不高，实用价值很低。十. 匹配编码就是按编码对象出现的概率，分别给予不同长度的代码，概率大的消息代码短，概率小的消息代码长。十一. 信源编码定理设信源的熵为H，信道容量为C，则：1.从这一信源在每单位时间内不可能传输比C/H个更多的消息数。2.总存在着

7、能传输小于C/H个消息的编码方法。可用下式等效表达：当K时， (K) /KH(X )/logq.十二. 几种熵的关系联合熵定理：H (XY ) H (X )H (Y )条件熵定理：H (Y/X ) H (Y )联合熵与条件熵的关系定理：H (XY ) = H (X )H (Y/X ) .十三. 其他编码方法：变换编码预测变换，函数变换。识别编码关联识别，逻辑识别。信道编码一. 噪声是指信息系统中导致有用信号失真的有害因素。噪声可分为乘性噪声和加性噪声。有扰信道的转移概率p(yj /xi)表示当发送xi时收到的是yj的概率。二元信道的平均错误概率为：二. 信道编码是对抗信道中加性干扰的的有效措施

8、，它是给信息码元人为地按照一定的规则加入多余码元，利用码元之间的约束关系来自动检测或纠正传输中所发生的错码。研究纠错编码的目的是为了更科学地增加多余码元，用较少的剩余换取尽可能多的可靠性，并使编译码设备简单。三. 分组码是指新增加的监督元仅与本码字的信息元有关的一类编码。为使信息组在传输时具有一定的抗干扰能力，把每个k位长的信息组变换成n位长的码字(nk). 这2k个n位长码字的全体称为码长为n，信息位为k的分组码，记为 (n, k) 码。其监督元个数r = nk . 衡量分组码性能的基本参数有：编码效率： R = k / n码重： 二元码时：码距： 二元码时：四. 分组码的纠检能力定理：设A

9、分组码，它的最小码距为dmin，存在正整数t, t1, t2使下列命题成立。（1）当dmint1时，A是检t码；（2）当dmin2t1时，A是纠t码；（3）当dmin2t1t21时，A是纠t1检(t1t2)码。五. 若给定BSC（二元对称信道）的平均错码率为p，则误码字率为；其中t为该编码的纠检能力，n为码长。六. 若要纠正码字中所有t重的错误，则监督元的数目r必须满足其中n为码长。称此式为汉明不等式。能使汉明不等式中等号成立的纠错码称为完备码。设称M为汉明界。它表示准用码组的个数不得超过M . 式中 表示取整数部分。七. 信道编码定理：将熵为H的信源接到信道容量为C的有错系统时，则有：（1）

10、若HC，总存在着无错传输的编码方法；（2）若HC，不可能作这种编码；（3）当HC时，疑义度总能接近(HC)，但不能比它更小。该定理的指数形式为： pwenE(R) .八. 线性分组码的定义和性质定义：设Vn(F2)是定义在F2上的一个n维向量空间，而A是它的一个k维子空间，那么就称A是码长为n，信息位为k的线性分组码，或称为(n , k)线性码。性质：1. 线性分组码是群码；2. 任意两码字之和仍为码字；3. 线性分组码必含有全0码字；4. 线性分组码的最小码距等于最小码重。九. (n , k)线性码A的一组基底向量g1 , g2 , , gk构成一个k行n列的矩阵G，称为A的一个生成矩阵。A

11、中任一码向量Ai = (an1 an2 a1 a0)都可以表示成基底向量的一个线性组合，Ai = MiG . 其中Mi = (mk1 mk2 m1 m0)。它可以是任一信息组。对G进行行初等变换可得到任一个行等价生成矩阵G，G与G生成同一种线性码。若不仅对G进行行初等变换，而且还进行列的置换，总能化成典型阵G0 = Ik , Q，由G0生成的码为系统码。一般地，由G经过行初等变换和列置换得到矩阵G，用G和G所生成的码空间不是同一码空间，但这两种码的纠检能力相同，因此它们互为等价码，并称G与G是互为组合等价的生成矩阵。十. 设线性码A的对偶空间为A*, H是A*的一组基底向量，则称H为A的监督矩

12、阵。H的秩为(nk) = r，并且有H0 AT = O , A*AT = O .假如接收向量为B，相应的发送向量为A，错误图样为E，则：S = BHT = EHT称S为校正子或伴随式。十一. 纠检能力与监督矩阵H的关系定理设A是个线性分组码，H是它的一个监督矩阵。如果H的任意t列都线性无关，而H有(t1)列线性相关，那么A的最小码重等于(t1)，这时A是可以检测所有t重错误的检错码；或者是可以纠正所有t/2重错误的纠错码。其中 表示取整数部分。十二. 若A是k维的，则其对偶空间A*是(nk) = r维的，并且G的秩为k，H的秩为r，G HT = O . H与G任意知道其中一个，就可以求出另一个

13、。H与G的互求方法有：1. 典型矩阵法；2. 对偶空间法；3. 解方程组法；4. 准典型阵互求法。十三. 线性分组码的译码步骤1. 计算伴随式：Si = BiHT2. 找出错误图样Ei ：Si = EiHT, Si与Hi 一一对应。3. 求发送向量的估计值Ai： Ai= BiEi .十四. 循环码的定义：设A是一个(n , k)线性码。如果A中任一码字循环移位后，仍是A中的码字，就称A是循环码。设F2xxn1是数域F2上关于x的以(xn1)为模的多项式的全体所构成的集合，Ax是它的一个理想。Ax中次数最低的一个多项式为g(x)，Ax中所有元素都是g(x) 的倍式，并且g(x) | (xn1)

14、.若 , 那么g(x), xg(x), xk1g(x)就是Ax的一组基。根据Ax和A间的一一对应关系，这一组基所对应的k个行向量就是A的一组基。设g(x) = g r xrg r1 xr1g1xg0则, (共k行)称g(x)为Ax的生成多项式，也叫做A的生成多项式；G是循环码A的生成矩阵。十五. 设h(x)g(x) = xn1，若 , 则 .设h(x) = h k xkh k1 xk1h1 xh0 , (h0 , h k 0) , 且令： , (共r行)称h(x)为监督多项式，H为A的监督矩阵。对于A中每一码字的多项式a(x)有：(a(x)h(x) xn1 = 0 , 且有A HT = O, G HT = O .与接收向量b相应的多项式b(x)的伴随式就是用g(x)除错码多项式所得的余式的相应系数所组成的行矩阵。即：ST = KHbT = eT .其中K为行初等变换的对应矩阵，e= (er1 er2 e1 e0) .