当前位置：文档之家 › 4.2 离散无记忆信源R(D)的计算解析

4.2 离散无记忆信源R(D)的计算解析

  • 格式：ppt
  • 大小：119.00 KB
  • 文档页数：16

下载文档原格式

  / 16

合集下载

信息率失真函数

信息率失真函数
平均失真 ：
描述某个信源在某一试验信道传输下的 失真大小,它对信源和信道进行了统计平 均,是从总体上描述整个系统的失真
8
3、L长序列编码平均失真
❖ 如X编长l…果 码 符假 后 号Xn,定 序}输,其离 列出中散y符j=L信[号长y源j1序符y输j2列号…入Y序y=符j列L{Y]号x1iY序=2[…列xi1YXxil＝2……{YXxmi1L}X],,其经2…中信L源
❖ 离散无记忆信源
13
例2 已知编码器输入的概率分布为p(x)={0.5 ,0.5} 信道矩阵 求互信息
14
若编码器输入的概率分布不变仍为p(x)={0.5 ,0.5} 但信道矩阵 求互信息
• 可见当p(x)一定时,I (X,Y)随信道矩阵p(yj|xi)而变。 • 因为p(x)分布一定时,信道受干扰不同所能传递的
信道容量：
信息率失真函数：
16
信道容量和信息率失真函数的区别
2、反映的事物不同
• 信道容量：
– 假定信道固定的前提下,选择一种试验信源使信息 传输率最大。
– 它所反映的是信道传输信息的能力,是信道可靠传 送的最大信息传输率。
• 一旦找到了信道容量,它就与信源不再有关,而是信
道特性的参量,随信道特性的变化而变化
6
4.11、.2单平符号均离失散信真源的平均失真
❖ x是i和随y机j都变是量随,有机限变失量真,所时以的失信真源函（数总d(体xi,）yj)失也 真值只能用数学期望表示
❖ 将失真函数的数学期望称为平均失真：
7
2、两者的区别平均失真
失真函数d(xi,yj)： 描述了某个信源符号通过传输后失真的 大小
信息量是不同的。 • 当p(x)一定时,I (X,Y)是关于p(yj|xi)的下凸函数。 • 因此当改变p(yj|xi)时,I (X,Y)有一极小值。

信息论与编码2016(第4章)

信息论与编码2016(第4章)

§4.2 离散无记忆信道 对称DMC容量的计算

P的所有列都是第一列的一种置换，信 道是关于输出对称的
0 .8 0 .2 P 0 .5 0 .5 0 .2 0 .8
§4.2 离散无记忆信道
命题2 若DMC关于输出为对称的，则当输入分布等概时，输 出分布等概。 证明 此时{p(y|x)，x=0~ K-1}与{p(0|x)，x=0~ K-1}互为置换。 设q(x)=1/K，x∈{0, 1, …, K-1}。则
q( z ) p( y | z )
都取一个相同的值；对任何满足q(k)=0的k，I(X=k; Y)都 不大于此相同的值。 （2）此时此相同的值恰好就是信道容量C。
§4.2 离散无记忆信道
注解
如果对DMC信道没有任何简化，要计算最佳输 入分布并不容易。但是，通常使用的DMC是很简单 的（比如，以下的准对称信道和对称信道），最佳 输入分布很容易求出。
§4.2 ቤተ መጻሕፍቲ ባይዱ散无记忆信道
定理4.2.2(p91) （1）输入概率分布{x, q(x), x∈{0, 1, …, K-1}}是最佳输入分 布的充分必要条件为：对任何满足q(k)>0的k，
I ( X k ; Y ) p( y | k ) log K 1
y 0 z 0 J 1
p( y | k )
第四章：信道及其容量
§4.1 §4.2 §4.5 §4.6 §4.7 信道分类 离散无记忆信道 信道的组合 时间离散的无记忆连续信道 波形信道
5
§4.1 信道分类

所有信道都有一个输入集A，一个输出集B以及 两者之间的联系，如条件概率P(y│x)，x∈A， y∈B。这些参量可用来规定一条信道。

《信号处理原理》 第4章 信息失真率

《信号处理原理》 第4章 信息失真率

d(0,2)=d(1,2)=0.5
则得失真矩阵
d

0 1
1 0
0.5 0.5
4.1 平均失真和信息率失真函数
说明：失真函数d (xi, yj) 的数值是依据实际应 用情况，用 yj代替xi, 所导致的失真大小是人为决 定的。比如上例中，用y=2代替x=0和x=1所导致 的失真程度相同，用0.5表示；而用y=0代替x=1 所导致的失真程度要大，用1表示。失真函数d (xi, yj) 的函数形式可以根据需要任意选取，例如平方 代价函数、绝对代价函数、均匀代价函数等。
信源编码器的目的是使编码后所需的信 息传输率R尽量小，然而R越小，引起的平 均失真就越大。给出一个失真的限制值D，
在满足平均失真 D D的条件下，选择一种
编码方法使信息率R尽可能小。信息率R就 是所需输出的有关信源X的信息量。
16
4.1 平均失真和信息率失真函数
将此问题对应到信道，即为接收端Y需要 获得的有关X的信息量，也就是互信息 I(X;Y)。这样，选择信源编码方法的问题就 变成了选择假想信道的问题，符号转移概 率p(yj/xi)就对应信道转移概率。
输入符号集 X:{a1, a2, …, an}中有n种不同的符 号xi (i =1, 2, …, n) ；输出符号集Y:{b1, b2, …, bm}中有m种不同的符号yj (j =1, 2, …, m)；对于 图所示的系统，对应于每一对(xi, yj)(i = 1, 2, …,n；j=1, 2, …, m)，定义一个非负实值函数
平均失真D是对给定信源分布p(ai)经过某一种 转移概率分布为p(bj|ai)的有失真信源编码器后产 生失真的总体量度。
13
4.1 平均失真和信息率失真函数

信息论与编码第三版 第4章

信息论与编码第三版 第4章
C max H ( X ) log 3
p( x)
信息论与编码
3. 根据平均互信息量I（X; Y）达到信道容量的充要条件式对C进行验证：
p ( y j ) p ( xi ) p ( y j / xi )
i 1 3
1 P 0 0
0 1/ 2 0
0 1/ 2 0
0 0 1/6
x1 x2 x3 x4 x5
1 1 1 1 1
y1 y2 y3 y4 y5
1 0 P 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
【解】 该信道的信道容量为：
C max I ( X ; Y ) max H ( X ) log 5
C max I ( X ; Y ) max H (Y )
p( x) p( x)
由于
p( y ) p( x) p( y / x)，由于信道转移概率是确定的，求使H (
X
Y)
达到最大值的p ( x )的最佳分布就转化为求p ( y )的最佳分布。由极大离 散熵定理知，在p ( y )等概率分布时，H ( Y ) 达到最大，则
I ( x2 ; Y ) p ( y j / x2 ) log
j 1 2
p ( y j / x2 ) p( y j ) p ( y j / x3 ) p( y j ) p ( y j / x4 ) p( y j ) p ( y j / x5 ) p( y j )
1 log
1 1/ 2
log 2
I ( x3 ; Y ) p ( y j / x3 ) log
j 1 2
1 log

离散无记忆信道的信道容量计算实验报告PPT课件

离散无记忆信道的信道容量计算实验报告PPT课件
演讲人：XXXXXX 时 间：XX年XX月XX日
2.信道容量算法
信道容量是互信息的最大值，首先要将信道容量求极值得问题表示 为二重交替优化问题。
（1）
• 运行结 果
(2)
实验结果(1)：输入概率转移矩阵是之前例题中的概率转移矩阵，迭代 次数为11和70次，经验证，迭代程序结果比例题中的一般信道容量算 法更为精确。
实验结果(2)：迭代次数为4，迭代结果为1.3219，经验算发现此输入 概率转移矩阵的实际结果为1.329，误差不大，符合要求，另外精度越 高，结果越接近。
离散无记忆信道的迭代运算
一、为什么要迭代？
(*)
（1）解方程组求出的输入分布 {P(x)}可能不唯一，因为可能有多个 极值点；
（2）需要验证求出的输入分布序列 是否符合要求。
（2）从达到DMC的信道容量的充要条件出发:
二、Blahut-Arimoto算法
1.交替优化
（2）、通过轮流固定f的其中一个自变量，对另一个没固定的 自变量求极值，由此来确定受此自变量影响下的最值。下一 次对另一个自变量也如此操作，循环往复形成迭代。
程序部分
• 程序设计思路
• （1）参数输入模块
• （2）判断模块
判断矩阵中的元素是否 >=0且<=1
判断矩阵的行相加是否 都为1
• （3）迭代模块1
• （4）迭代模块2
• （5）输出模块Байду номын сангаас
• P116 4.3 (b)
• 一般的DMC
• 一般的DMC
概率矩阵：
参考文献
[1]王育民、李晖 .《信息论与编码理论第二版》[M]北京：高等教育出版社，2013.4 96-101 [2]辛英.《离散信道容量的迭代算法及其实现》[D]山东：山东工商学院，1994 [3]徐伟业 耿苏燕 马湘蓉 冯月芹.《任意DMC信道容量的计算与仿真》[D]南京：南京工程学院 2017

信息论基础与编码课件第四章 信息率失真函数

信息论基础与编码课件第四章 信息率失真函数

同样，可得Pij时的平均互信息为 I''(X;Y)0.37b9i/t符号
从此例我们可以看到，若固定P(x)不变时，平均互信息量随信
道的转移概率的变化而变化。这是因为信道受到干扰的作用 不同，传递的信息量也不同。可以证明这样一个结论：P(x)一 定时，平均互信息量I(X;Y)是关于信道的转移概率的下凸函数， 即存在一极小值。
m × n个 p i j 的值，代入平均失真的公式中，可解出随S参数值变
化的D值，即
D (S ) p ip j id ij p ip ij ie S d ijd ij （4-16）
ij
ij
25
离散信源的R(D)函数及其计算(续)
信源的信息率失真函数R(D)为
R (S ) i
j
pi p j i e Sdij
源输出符号序列 X (X 1 ,X 2 , ,X L ) ，其中L长符号序列样
值 Y(Y 1,Y 2, ,Y L) ，经信源编码后，输出符号序
列 x i (x i1 ,x i2 , ,x iL )
，其中L长符号序列样
值 y i (y i1 ,y i2 , ,y iL )，则失真函数定义为：
1L
dL(xi,yj)Ll1d(xil,yjl)
其中d(xil，yjl)是信源输出L长符号样值 x i 中的第l个符号xil时，
编码输出L长符号样值 中的y i 第l个符号yjl的失真函数。
7
平均失真
定义平均失真度为失真函数的数学期望，即 d ( xi , yj ) 在 X 和 Y的 联合概率空间 P(XY ) 中的统计平均值
nm
D E [d (x i,y j)] p (x i)p (y j|x i)d (x i,y j) （4-4） i 1j 1

第5讲离散无记忆信源


尤为重要的是：
一类重要的符号序列有记忆离散信源----马尔可夫 信源： 某一个符号出现的概率只与前面一个或有限个 符号有关，而不依赖更前面的那些符号。
2.2 离散无记忆扩展信源
1. 单个符号的离散信源----每次只发出一个符号代表一 个消息，且消息数量有限。
a1 X P p ( a1 ) a2 p ( a2 ) p ( ar ) ar
则称此信源为离散平稳信源。 注：平稳信源既是指在发出符号不变的前提下，发出符号 概率不依时间而改变，今后不特别说明时，我们提到的信 源都是平稳信源。
2、平稳信源等价条件
p ( xk ) p ( xt ) p( x x ) p( x x ) k k 1 t t 1 (1) p ( xk xk N ) p ( xt xt N )
符号集
X {a1 , a2 ,
r
, ar },
i
p ai 0
p(a ) 1
i 1
2. 发出符号序列离散信源－－每次发出一组 含两个以上的符号序列来代表一个消息
信源X输出用N维随机序列（随机矢量）
X X 1 X2 Xl X N 来描述信源输出的消息，
用联合概率分布来表示信源特性。在上述随机矢量 中，若每个随机变量 X i (i 1, 2,
中每个符号才能使得X i 有r N 个，因此相当如后式中的i1 ,
, iN 都从
注2、
H(XN)=NH(X):每个消息所能提供的平均信息量为每个信源
符号平均信息量的N倍。
X a1 例1、设信源空间 1 P 4 信源的熵？
解：X 2的概率空间为
a2 1 2

4.2 离散无记忆信源R(D)的计算_万方通信

4.2 离散无记忆信源R(D)的计算 4.3 连续无记忆信源R(D)的计算 4.4 信道容量和信息率失真函数的比较
2019/1/14
7
例：求d(x,y)=(y-x)2的Dmax和信息率失真 函数R(D)。 min[ p( x)d ( x, y)dx] 解：连续信源的Dmax， D
max y
y

而 （x ）p( x)dx ，即 x p( x)dx
2 2 2
2
D
Dmax min[ 2 2 2 y y 2 ]
y
2
2019/1/14
10
结论：

若失真函数为均方失真，即d(x,y)=(x-y)2时,连续 1 D 信源的信息率失真函数 R( D) ln( max ) ，且
第4章 信息率失真函数
2019/1/14
1


4.1 基本概念
4.2 离散无记忆信源R(D)的计算 4.3 连续无记忆信源R(D)的计算 4.4 信道容量和信息率失真函数的比较
2019/1/14
2
4.2 离散无记忆信源R(D)的计算

参量表达式法求R(D)及P(Y/X)，具体推导略， 见p111页。
X x1 x2 0 1 ，其中 p ，失真矩阵为 D , 输出Y 0,1 P( X ) p 1 p 2 0

Dj 解：（1） Dmax min j 0 min p 1 p j 0 min(1 p ) , p
依据：平均互信息I是信源概率分布p(xi)的严格上 凸函数。

（2）信息率失真函数：求选择某一试验信道（转 移概率分布）的情况下，依据保真度准则，求平均 互信息的极小值。

信息论与编码技术Chap4 思考题与习题 khdaw


， λ 满足
∑D
k =1
K
k
=D
(a) m
(b ) m
≥ ∑ h( x i ) − ∑ h( x i | x ˆi ) i =1 i =1
m
m
m
(c) m
i =1
(d ) m
其中 D = E ( X − ˆ i X
课
真函数定义，（d）高斯变量的率失真函数。式中有两个不等号，其中 （b）
当q( x | x ˆ i) = ∏ q( x i | x ˆ i)时，等号成立。
或
D =λ
i
'
D m
D 2 ≤ min{σ i } 时 i m
这表示当失真分配给各分量时，最佳分配方案是每个分量等失真。但这仅当 才可行，当某个分量的
σ
2
i
小于
D 时 就 不 行 了 ， 必 须 利 用 K-T 条 件 来 解 ， 即 选 λ 使 m
2 ⎧ 1 1 ∂J ⎪ 0, D i < σ i =− +λ⎨ 2 2 Di ∂D ⎪ ⎩≤ 0, D i ≥ σ i
⎡1 0 ⎤ ⎡0 1⎤ ⎡α 1 − α ⎤ ⎥ ⎢ ⎥ ⎢ ⎥ 0 ≤α ≤1 [ P(υ j | u i )] = ⎢ ⎢1 0 ⎥ , ⎢0 1⎥ 或 ⎢α 1 − α ⎥ ， ⎢ ⎣1 0 ⎥ ⎦ ⎢ ⎣0 1⎥ ⎦ ⎢ ⎣α 1 − α ⎥ ⎦
w. kh d
aw .
co m
3
1 [1 + 1 + 1] = 1 3
所以
无噪无损信道中进行传输，而信道每秒钟只传递二个二元符号。 (1)试问信源能否在此信道中进行无失真的传输。 解：（1）此信源的熵 H(s)=1 （比特/符号）

第4章 离散无记忆信源无失真编码

第4章离散无记忆信源无失真编码主要内容1、基本概念2、码的唯一可译性3、定长编码定理和定长编码方法4、变长编码定理5 变长编码方法6 几种实用的无失真信源编码1、基本概念信源发出的消息序列通常不能直接送给信道传输，需要经过信源编码和信道编码。

信道编码的目的是降低差错率，提高传送的可靠性。

信源编码的目的是为了降低冗余度，提高通信的有效性。

编码是一种映射，是将输入符号映射成码字。

无失真编码，映射一一对应，可逆。

编码器模型：码长：码字所含码元的个数定长编码：所有码字均有相同的码长，对应的码叫做定长码(FLC ，Fixed Length code)；否则为变长编码。

编码器12{,,,}q u u u 12{,,,}r x x x WU12{,,,}q w w w X信源平均码长：码中所有码字码长的统计平均，即码元/符号编码效率：编码后的实际信息率与编码后的最大信息率之比冗余度：l l l2、码的唯一可译性（1）基本概念奇异码：一组码中含相同码字。

非奇异码：所有的码字都不相同。

唯一可译性：码字组成的任意有限长码字序列都能恢复成唯一的信源序列。

续长码：有些码字是在另一些码字后面添加码元得来的。

及时码：码字的最后一个码元出现时，译码器能立即判断一个码字已经结束，可以立即译码。

非续长码：任一码字都不是其它码字的延长。

唯一可译码定长非奇异码非续长码非奇异码5种不同的码35124121142183184()00001000100001001101001110011111110111111i P u W W W W W U u u u u（2）码树和Kraft不等式从树根开始，生长r个树枝，在节点处再各自生长r个树枝。

节点：树枝与树枝的交点。

l阶节点：经过l根树枝到达的节点。

整树：节点长出的树枝数等于r定理：对于任一r进制非续长码，各码字的码长必须满足Kraft不等式：反过来，若上式成立，就一定能构造一个r 进制非续长码。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

Dmax min p( xi )d ij
Y X
因为离散信源：

均方失真的连续信源的R(D)
R( D)
1 Dmax ln( ) 2 D
可直接当结论来应用
2018/10/12
8
例：设某连续信源X服从高斯分布，均值μ=0， 方差σ2，失真函数为均方失真即d(x,y)=(y-x)2

求它的信息率失真函数R(D)和Dmax。

例：已知离散无记忆信源
x2 X x1 0 1 ，求 P( X ) p 1 p ，其中p 2 ，失真矩阵为D 0 , 输出Y 0,1 Dmax，率失真函数R( D)。
2018/10/12
3
4.2 离散无记忆信源R(D)的计算
y

min[ x 2 p( x)dx 2 y xp( x)dx y 2 p( x)dx]
y
D
min[ 2 0 y 2 ]
y
2
2018/10/12 9
上题的扩展：若连续信源服从（μ，σ2）的高 斯分布，则再求上题。

解：先求Dmax：
服从(0, 2 )的高斯分布的概率密度 函数为： p ( x) 1 e 2

2、

（1）信道容量C一旦求出来，则与信源分布无关（只是 证明存在这样的满足信道容量的信源分布），只和信道 转移概率分布p(yj/xi)有关。即信道容量和信源特性无 关，反映信道特性。 （2）信息率失真函数R(D)一旦求出来，则与信道转移 概率分布无关（只是证明存在达到最小信息率的试验信 道），只和信源概率分布p(xi)有关。即信息率失真函数 和信道特性无关，反映信源特性。
4.2 离散无记忆信源R(D)的计算 4.3 连续无记忆信源R(D)的计算 4.4信道容量和信息率失真函数的比较
2018/10/12
12
4.4 信道容量和信息率失真函数的比较

相同点：二者都是求平均互信息的极值 不同点：

1、

（1）信道容量：选择某一信源分布的情况下，求 平均互信息的极大值。
j
1 (1 p ) , 当p 2 时 1 p , 当p 时 2

（2）
D R( D) H ( p) H ( )

2018/10/12
4

R(D)随D的变化曲线
H(p)
Dmax=αp
2018/10/12
5
结论：

对于n元等概信源，有 p( x ) n , 其中 i 1, n，当失真 函数为对称失真时，
y ( x )2 2 2
Dmax min[ p( x)d ( x, y )dx] min[ p( x)(x y ) dx]
2 y
代入得
1 2 R ( D ) ln( ) 2 D ln
2
min[ x 2 p( x)dx 2 y xp( x)dx y 2 p( x)dx]
X x1 x2 0 1 ，其中 p ，失真矩阵为 D , 输出Y 0,1 P( X ) p 1 p 2 0

Dj 解：（1） Dmax min j 0 min p 1 p j 0 min(1 p ) , p
第4章 信息率失真函数
2018/10/12
1


4.1 基本概念
4.2 离散无记忆信源R(D)的计算 4.3 连续无记忆信源R(D)的计算 4.4 信道容量和信息率失真函数的比较
2018/10/12
2
4.2 离散无记忆信源R(D)的计算

参量表达式法求R(D)及P(Y/X)，具体推导略， 见p111页。
是均方失真 解： 1 Dmax R( D) ln( ) 2 D

因此，需求Dmax
2 服从 ( 0 , )的高斯分布的概率密度 函数为： ：
p( x)
1 ( D ) ln( ) 2 D ln
Dmax min[ p( x)d ( x, y )dx] min[ p( x)(x y ) 2 dx]

依据：平均互信息I是信源概率分布p(xi)的严格上 凸函数。

（2）信息率失真函数：求选择某一试验信道（转 移概率分布）的情况下，依据保真度准则，求平均 互信息的极小值。

依据：平均互信息I是信道转移概率分布p(yj/xi)的 严格下凸函数。
13
2018/10/12
4.4 信道容量和信息率失真函数的比较
2 D
Dmax min[ p( x)d ( x, y)dx]
y

同理：当失真函数为绝对失真即d(x,y)=|x-y|时， 指数分布的连续信源，当概率密度函数为
p( x)

2
e | x|时， R( D) ln
1 1 , Dmax D
2018/10/12
11


4.1 基本概念
4.2 离散无记忆信源R(D)的计算 4.3 连续无记忆信源R(D)的计算 4.4 信道容量和信息率失真函数的比较
2018/10/12
7
例：求d(x,y)=(y-x)2的Dmax和信息率失真 函数R(D)。 min[ p( x)d ( x, y)dx] 解：连续信源的Dmax， D
max y
i
1
0, i j时 即 d ij ，i j
此时下式成立：
1 Dmax (1 ) n
D / D D R( D) ln(n) ln (1 ) ln(1 ) (n 1) D
可直接当结论来应用
2018/10/12
6


4.1 基本概念
y

而 （x ）p( x)dx ，即 x p( x)dx
2 2 2
2
D
Dmax min[ 2 2 2 y y 2 ]
y
2
2018/10/12
10
结论：

若失真函数为均方失真，即d(x,y)=(x-y)2时,连续 1 D 信源的信息率失真函数 R( D) ln( max ) ，且