信息论与编码答案

Aaaa

信息论与编码

（第十三讲）

宋 鹏

2014年秋 E-mail：[email protected]

2014-12-31 Department of Electronics and Information, NCUT Song Peng 第1页

“信息论与编码”考核要求

 作业：30%  考试：70%  考试形式：一纸开卷（小于A4的纸）  考试时间：17周周二：3、4节  考试地点：四教东501  答疑时间：16周周日：5、6节  答疑地点：四教603

2014-12-31

Department of Electronics and Information, NCUT

Song Peng

第2页

第一部分：信息论

▼ 信息论研究的内容

 信息论基础：也称狭义信息论/经典信息论/香农信息论。

主要研究信息测度、信道容量、信息率失真函数 与这三个概念相对应的香农三定理，信源编码，信道 编码。

2014-12-31

Department of Electronics and Information, NCUT

Song Peng

第3页

第一部分：信息论

▼ 信息论研究的内容

 一般信息论：主要研究信息传输和处理问题。

除香农基本理论之外，还包括噪声理论、信号滤波和预 测、统计检测和估计理论、调制理论。 后一部分内容以维纳为代表。

2014-12-31

Department of Electronics and Information, NCUT

Song Peng

第4页

第一部分：信息论

▼ 信息论研究的内容

 广义信息论：是一门综合性的新型学科—信息科学。

至今没有严格的定义。 凡是能够用广义通信系统模型描述的过程或系统，都 能用信息基本理论来研究。

2014-12-31

Department of Electronics and Information, NCUT

Song Peng

第5页

第一部分：信息论

(1) 信息量：自信息和互信息 (2) 熵：平均自信息和平均互信息 (3) 信源编码：等长编码和不等长编码 (4) 保真度准则下的信源编码问题

2014-12-31

Department of Electronics and Information, NCUT

Song Peng

第6页

第一部分：信息论

(5) 模拟信道的信道容量

 信道容量为：

 P C＝WT log  1 + N W 0 

   

 单位时间的信道容量为（香农公式）：

 P C t＝W log  1 + N 0W 

P — 信号平均功率

  （比特 / 秒） 

N0W — 高斯白噪声在带宽 W 内的平均功率（其功率密度谱为 N0/2 ）

2014-12-31 Department of Electronics and Information, NCUT Song Peng 第7页

第一部分：信息论

(6) 需要清楚的一些概念

 自信息及其性质  互信息及其性质（正负问题）  熵—平均自信息及其性质（会计算熵和平均互信息）  平均互信息及其性质  数据处理定理：从一个事件提取关于另一个事件的信息量，至多是

另一个事件的 熵 那么多。

 等长编码与不等长编码  无失真信源编码定理

2014-12-31 Department of Electronics and Information, NCUT Song Peng 第8页

第一部分：信息论

(6) 需要清楚的一些概念

 信道与信道容量  香农公式及其含义  信道编码定理  失真度（

失真函数）

 P C t＝W log  1 + N 0W   （比特 / 秒）  

n m

D = E d ( x i , y j ) = E [d ( x , y )] D = ∑ p( x , y )d ( x , y ) = ∑∑ p( x i ) p( y j / x i )d ( x i , y j )

X ,Y i =1 j =1

[

]

 有失真信源编码问题（保真度准则下的信源编码：编码速率与

失真度之间关系的问题）

 信息率失真函数（无失真信源压缩的极限值，有失真信源压缩

的极限值）

2014-12-31 Department of Electronics and Information, NCUT Song Peng 第9页

第二部分：信源编码

 信源编码主要是解决通信系统的有效性问题，信道编码主

要是解决通信系统的可靠性问题。

 冗余度压缩编码：压缩信源中的冗余度，在一定限度内是

可逆的。

 熵压缩编码：不可逆压缩，压缩超过一定限度必然带来失

真。

 当信源给定后，无失真信源压缩的极限值是 信源H(X)；

而有失真信源压缩的极限值是信息率失真函数R(D)。在给 定D后，一般 R(D)

2014-12-31 Department of Electronics and Information, NCUT Song Peng 第10页

第二部分：信源编码

(1) 二元霍夫曼码 (2) m元霍夫曼码 (3) 香农编码 (4) 费诺编码 (5) 香农－费诺－埃利斯码 (6) 算术编码 (7) LZ编码 (8) LZW编码

Song Peng

2014-12-31

Department of Electronics and Information, NCUT

第11页

第二部分：信源编码

举例1：

u7 u8   U   u1 , u2 , u3 , u4 , u5 , u6  例3.1：设有信源：  P (U ) = 0.2 0.19 0.18 0.17 0.15 0.1 0.007 0.003    

0.35 (1) (0) (1) (0) 0.39 (1) 0.61 (0)

(01) (00) (111) (110) (101) (1001) (10001) (10000)

u1 u2 u3 u4 u5 u6 u7 u8

0.20 0.19 0.18 0.17 0.15 0.10 0.007 0.003

0.26 (1) (0) (1) (1) (1) (0) (0) 0.01 (0) 0.11

1.0

图3.2 二元Huffman编码

Song Peng 第12页

2014-12-31

Department of Electronics and Information, NCUT

第二部分：信源编码

举例1：

 例3.1：

H (U ) = − ∑ p( ui ) log 2 p( ui ) = 2.62 （比特 / 符号）

i =1

8

R = L = ∑ p( ui )l i = 2.73（比特 / 符号）

i =1

8

R = L log m

H (U ) H (U ) 2.62 η= = = = 95.97% R L 2.73

2014-12-31

Department of Electronics and Information, NCUT

Song Peng

第13页

第二部分：信源编码

算术编码

 利用码树图说明概率 p(un) 和累积概率 F(un) 的递推算法

0 0 1 0 1 0 s=u4 0 1 1 1

T1

T2

T3

图3.6 算术编码累积概率的计算树

2014-12-31

Department of Electronics and Information, NCUT

Song Peng

第14页

第二部分：信源编码

算术编码

 利用码树图说明概率 p(un) 和累积概率 F(un) 的递推算法 

Tu1u2 uk −1 ------从枝点

u1 u 2  u k −1

长出的子树，其概

率与累积概率为：

P ( Tu u

n

1 2u k −1

) = p ( u1 u 2  u k −1 )

P (T ) ∑ n

F (u ) =

y

p( y n ) = ∑ n n

T：在u 左边的T

2014-12-31

Department of Electronics and Information, NCUT

Song Peng

第15页

第二部分：信源编码

 举例：已输入二元符号序列为 s=“011”，接着再输入符

号为“1”，得序列累积分布函数为：

F(s1)=F(0111)=F(s=“011”)+P(011)P(0) =F(s=“01”)+P(01)P(0)+P(011)P(0) =F(s=“0”)+P(0)P(0) +P(01)P(0)+P(011)P(0) =0+P(00)+P(010)+P(0110) 对应的区间宽度为： A(s1)=P(s=“011”)P(1)=P(011)P(1)=P(0111)

F (s 1) = F (s ) + P (s ) ⋅ P (0) = s 1) P ( = s 1) P (s ) ⋅ P (1) A(

2014-12-31 Department of Electronics and Information, NCUT Song Peng 第16页

第三部分：信道编码

线性分组码

 最大后验概率准则：根据最大后验概率进行判决译码，一

定是译码错误概率最小。

 最大似然译码就相当于最小距离译码。  M个码字中，任何两个不同的码字间的汉明距离要尽量大。

也就是说，挑选出来的M个码字之间越不相似越好。这即 是随机编码必须遵循的原则。

 最小距离和检、纠错能力

2014-12-31

Department of Electronics and Information, NCUT

Song Peng

第17页

第三部分：信道编码

线性分组码

 监督矩阵与生成矩阵  系统码生成矩阵与监督矩阵关系  编码电路  伴随式与伴随式计算电路  标准阵列与译码表  译码步骤与译码电路  看PPT

Department of Electronics and Information, NCUT Song Peng

2014-12-31

第18页

第三部分：信道编码

循环码

 群、环、域的概念  域上的乘法和加法：域的特征（或元素的周期）表明了域上加

法运算的循环特性。域中元素的级说明了乘法运算的循环特性。

 域上多项式（二元域）

1. 本原元素 2. 最小多项式及其性质 3. 本原多项式及其根系 4. 如何求最小多项式

2014-12-31

Department of Electronics and Information, NCUT

Song Peng

第19页

第三部分：信道编码

循环码

 运算电路，特别是除法电路  构成系统循环码的步骤

 用 xn－k 乘以消息多项式 m(x) ；  用生成多项式 g(x) 除 xn－k · m(x) ，得到余式 b(x) （即监督位

多项式）；

 构成码多项式：C(x)= xn－k · m(x)+ b(x)。

2014-12-31

Department of Electronics and Information, NCUT

Song Peng

第20页

第三部分：信道编码

循环码

 用除法电路实现的编码、译码电路，特别是循环汉明码

（汉明码） 。

 接收矢量的循环移位（模 xn +1运算下 ）与伴随式在模

g(x)运算下 （或在除以g(x)的伴随式计算电路中）的循环 移位是一一对应的。

 循环码生成多项式与监督多项式之间的关系：

（xn+1= g(x)·h(x) ）

2014-12-31

Department of Electronics and Information, NCUT

Song Peng

第21页

7.5 循环汉明码

(2) (7, 4) 循环汉明码的译码

 (7, 4) 循环码是纠一个错误的循环汉明码；  由于码字和伴随式的循环移位特性，可将译码电路设计成

纠正最高阶位上的一个错误；

 当实际错误不在

最高阶而在其它位上时，接收矢量和伴随

式（在 g(x) 除法运算电路中）同时进行移位，一旦错误到 达最高阶位上，就将产生确定的伴随式；

 只需要一个简单的组合逻辑电路对这一确定的伴随式进行

检测就可完成纠错。

2014-12-31 Department of Electronics and Information, NCUT Song Peng 第22页

7.5 循环汉明码

(2) (7, 4) 循环汉明码的译码

 由 g(x) = x3 + x + 1 生成的 (7, 4) 循环汉明码的译码电路如

图 7.5.1 所示。

R(x)

D0

D1

D2

门控制信号 门 门 门

D0

D1

D2

输出

7级移位寄存器

2014-12-31

Department of Electronics and 图 Information, NCUT Song Peng 7.5.1 (7,4)循环码的译码电路

第23页

7.5 循环汉明码

(2) (7, 4) 循环汉明码的译码

 (7, 4) 循环汉明码的译码电路工作过程

① 接收矢量送入伴随式计算电路，经 7 次移位得到伴随 式，同时接收矢量移入缓存器；

2014-12-31

Department of Electronics and Information, NCUT

Song Peng

第24页

7.5 循环汉明码

(2) (7, 4) 循环汉明码的译码

 (7, 4) 循环汉明码的译码电路工作过程

② 将前一步所计算的伴随式转入伴随式自发运算电路，当错

误恰好在最高阶位上时，伴随式为 (101)，与门检测此状态 并输出“1”，而当最高阶位移出缓存器时即被纠正；若错误 不在最高阶位上而在其它位上，比如在 x4 位上时，错误图样 经过两次移位变成 x2x4 = x6，经两次移位后的伴随式为 s2(x) = x2 + 1（mod g(x)），检测到此状态时与门输出“1”，而对 应的接收符号也正好移到最高阶位上，因而错误得到纠正； [x6/(x3+x+1)=x2+1]

2014-12-31 Department of Electronics and Information, NCUT Song Peng 第25页

7.5 循环汉明码

(2) (7, 4) 循环汉明码的译码

 (7, 4) 循环汉明码的译码电路工作过程

③ 当接收矢量全部移出缓存器后，完成一个码组的译码。 在接收矢量开始移出缓存器时，下一个接收矢量紧跟着移 入伴随式计算电路和缓存器，重复第②步的的过程，可实 现连续对接收矢量进行纠错。

2014-12-31

Department of Electronics and Information, NCUT

Song Peng

第26页

第三部分：信道编码

多元BCH码

 二元本原BCH码、多元BCH码、RS码的定义  本原BCH码的最小距离：本原BCH码的最小距离 dmin≥d

（d－1是 g(x) 相邻根的个数）

 d − 1  如何构造一个BCH码：纠 t =  个错误的BCH码的生   2 

成多项式为：

g(x)=LCM [m1(x), m3(x), …, m2t－1(x)]

2014-12-31

Department of Electronics and Information, NCUT

Song Peng

第27页

第三部分：信道编码

多元BCH码

 二元BCH码之间的参数关系：对任一给定的正整数 m 和 t

(t

 码长：n≤2m－1  监督位数：n－k ≤mt  最小距离：dmin≥2t+1  设

计距离：d=2t+1，是所构造的码要达到的距离

2014-12-31

Department of Electronics and Information, NCUT

Song Peng

第28页

第三部分：信道编码

多元BCH码

 二元BCH码的作法  多元BCH码，讨论 q=2m 的 GF(2m)上RS码的编码。  BCH码译码的基本原理和步骤

2014-12-31

Department of Electronics and Information, NCUT

Song Peng

第29页

第三部分：信道编码

卷积码

 冲击响应（生成序列）、生成序列、生成元

g(1)=(g0(1) g1(1) g2(1))=(1 1 1) g(2)=(g0(2) g1(2) g2(2))=(1 0 1)

 卷积码的生成矩阵

G 0 G1 G 2 G 3  G 0 G1 G 2 G 3  G=  G 0 G1 G 2    

2014-12-31

 Gm    G m −1 G m   G m − 2 G m −1 G m       

Song Peng 第30页

Department of Electronics and Information, NCUT

第三部分：信道编码

卷积码

 卷积码的图描述：树图；网格图；状态图  卷积码的编码

 串行输入、串行输出的编码电路  (n－k)m 级移位寄存器构成的并行编码电路（Ⅰ型编码电路）  km级移位寄存器构成的并行编码电路（Ⅱ型编码电路）

 给出编码器图，会写出生成序列、生成矩阵、状态图。或

者相反过程。

2014-12-31

Department of Electronics and Information, NCUT

Song Peng

第31页

2014-12-31

Department of Electronics and Information, NCUT

Song Peng

第32页