信息论基础 第四章 信息率失真函数.

Presentation on theme: "信息论基础 第四章 信息率失真函数."— Presentation transcript:

1 信息论基础 第四章 信息率失真函数

2 4.1 基本概念 基本概念 失真 信道编码定理：若 R < C，总能找到一种编码，能在信道上以任意小的错误概率和任意接近于C的传输率来传送信息。若 R > C，则传输总要产生失真。 无失真信源编码定理： 要做到几乎无失真信源编码，R必须大于信源熵。故有H(X)≤R≤C 在实际生活中，人们不一定要求完全无失真的恢复消息，也就是允许有一定的失真。如语音、图像。 那么在允许一定程度失真的条件下，能够把信源信息压缩到什么程度，也就是，允许一定程度失真的条件下，如何能快速的传输信息，这就是信息率失真理论所要讨论的问题。

3 4.1 基本概念 信息率失真理论 信息率失真理论——香农于1959年在《保真度准则下的离散信源编码定理》中提出。定义了信息率失真函数R(D),明确提出：在允许一定失真度D的情况下，信源输出的信息率可压缩到R(D)值。 信息率失真理论是量化、数模转换、频带压缩和数据压缩的理论基础。 I(X;Y)——P(X)、P(Y/X)的二元函数 固定P(Y/X) ，改变P(X)得I(X;Y)最大值(上凸函数) ——信道容量 固定P(X)，改变P(Y/X) 得I(X;Y)最小值(下凸函数) ——率失真函数

4 4.1 基本概念 信息率失真函数 信息率～失真——允许失真↑→所需信息率↓ 若固定P(X)，改变P(Y/X) 得I(X;Y)最小值。
当p(bj|ai)=p(bj) 时，即X和Y相互统计独立，该最小值等于零。这样求得的极小值就没有任何意义，因为信道不能传递任何信息，或者信源的信息全部损失掉了。 如果限定一个失真度，则在失真度一定的情况下(小于信源熵)，求信息率的极小值就具有非常重要的意义，它需要的信道资源最小。 信息率～失真——允许失真↑→所需信息率↓

5 4.1 基本概念 失真函数与平均失真度 失真函数 信源 信源编码 信道编码 信道 信道译码 信源译码 信宿 干扰
根据信道编码定理，我们可以把信道编码、信道和信道解码等价成是一个没有任何干扰的广义信道，这样收信者收到消息后，所产生的失真只是由信源编码带来的。我们也可以把信源编码和信源译码等价成一个信道。

6 4.1 基本概念 设离散无记忆信源为 其概率分布为 接收端变量为 其概率分布为 信道矩阵为 对于每一对(ai,bj)，我们指定一个非负的函数
称为单个符号的失真度（或称失真函数）

7 4.1 基本概念 失真函数用来表征信源发出一个符号 ，而在接收端再现成符号 所引起的误差或失真。d越小表示失真越小，等于0表示没有失真。
可以将所有的失真函数排列成矩阵的形式： 我们称它为失真矩阵。n行m列

8 4.1 基本概念 例：设信源符号序列X=[0,1]，接收端收到的符号序列为 Y=[0,1,2],规定失真函数为： 失真矩阵为： 2 yj
1 2 yj xi 0.5 失真矩阵为：

9 4.1 基本概念 (1) 失真矩阵为： 对所有不同的i和j引起的误差都一样，所以定义失真度为常数a。 若a=1,则为汉明失真函数

10 4.1 基本概念 (2) d(ai,bj) = (bj–ai)2 ——平方误差失真函数
失真矩阵称为平方误差失真矩阵。较大幅度的失真要比较小幅度的失真引起的错误更为严重，严重程度用平方表示。 说明: 最常用的失真函数 均方失真函数： d(ai,bj)=(ai-bj)2 绝对失真函数： d(ai,bj)=|ai-bj| 相对失真函数： d(ai,bj)=|ai-bj|/|ai| 误码失真函数： d(ai,bj)=

11 4.1 基本概念 (2)最常用的失真函数及其适用性 均方失真函数,绝对失真函数, 相对失真函数适用于连续信源; 误码失真函数适用于离散信源。
(3)失真函数困难性比较 均方失真和绝对失真只与(ai-bj)有关，而不是分别与ai及bj有关，在数学处理上比较方便；相对失真与主观特性比较匹配，因为主观感觉往往与客观量的对数成正比，但在数学处理中就要困难得多。

12 4.1 基本概念 平均失真度 失真函数的数学期望，平均意义上表示信道每传递一个符号所引起的失真的大小。 [说明]
①由于xi和yj都是随机变量，所以失真函数d(xi,yj)也是随机变量，只能用它的数学期望或统计平均值，因此将失真函数的数学期望称为平均失真。是在平均意义上，对系统失真的总体描述 ②是信源统计特性p(xi)的函数 是信道统计特性p(yj| xi)的函数 是规定失真度d(xi, yj)的函数 若保持p(xi)、d(xi, yj)不变，则平均失真度就是信道特性p(yj|xi)的函数，是传输过程所产生的失真的总体度量。

13 4.1 基本概念 保真度准则 如果规定平均失真度 不能超过某一限定的值D，即 在满足保真度准则前提下，求信息率最小值，即为信息率失真函数。

14 4.1 基本概念 离散无记忆信道的N次扩展信道 输入序列XN=X1X2…XN N位,每位n种,共有nN种序列 输出序列 YN=Y1Y2…YN
N位,每位m种,共有mN种序列 (1)输入序列 和输出序列 之间的失真函数 (2)N次离散无记忆扩展信源和扩展信道的平均失真度——是单符号时的N倍 保真度准则

15 4.1 基本概念 例：设离散矢量信源N=3,输出矢量序列为X=X1X2X3,其中Xi,i=1,2,3的取值为{0,1}；经信道传输后的输出为Y=Y1Y2Y3，其中Yi,i=1,2,3的取值为{0,1}。定义失真函数为： 失真函数为：

16 4.1 基本概念 信息率失真函数 D允许信道(试验信道)
如果信息传输率R大于信道容量C,就应该对信源压缩，使其压缩后的信息率R'小于信道容量C，但要保证压缩引入的失真不超过预先规定的限度。 若平均失真度 不大于我们所允许的失真D，我们称此为保真度准则。 凡满足保真度准则的这些试验信道称为D允许信道（D允许的试验信道）。把所有D允许信道组成一个集合，用符号 表示。 离散无记忆信源的N次扩展信源和离散无记忆信道的N次扩展信道：

17 4.1 基本概念 信息率失真函数的定义 当信源和失真函数给定后，我们总希望在满足保真度准则下寻找平均互信息的最小值，也就是在 中找一个信道，使平均互信息取极小值。这个最小值就是在 的条件下，信源必须传输的最小平均信息量。 改变试验信道求平均互信息的最小值，实质上是选择一种编码方式使信息传输率为最小。R(D)是假定信源给定的情况下，在用户可以容忍的失真度内，再现信源消息所必须获得的最小平均互信息量。它反映的是信源的可压缩程度。 试验信道的范围：只有能够满足保真度准则的那些信道。从而使I(X,Y)的最小值具有实用意义。

18 4.1 基本概念 对于离散无记忆信源的N次扩展信源和离散无记忆信道的N次扩展信道，其信息率失真函数为:
由于信源和信道的无记忆性，容易证明： RN(D) =NR(D)

19 4.1 基本概念 率失真函数与信道容量的比较 信道容量C 率失真函数R(D) 数学上
固定p(yj|xi)，改变p(xi),求得I(X;Y)最大值 固定p(xi),改变p(yj|xi),求得I(X;Y)最小值 概念上 (反映) 固定信道，改变信源，使信息率最大。C只跟信道有关，反映信道传输能力 固定信源，改变信道，使信息率最小。R只跟信源有关，反映信源可压缩程度 通信上 使传输信息量最大，Pe→0——信道编码 用尽可能少的码符号传送——信源编码

20 4.1 基本概念 信息率失真函数R(D)的性质 1) R(D)的定义域和值域
D为允许平均失真度，也就是平均失真度 的上限值。D的选择必须根据信源的统计特性P(X)和失真函数d(ai, bj)，在平均失真度 的可能取值范围内，合理地选择某一值作为允许的平均失真度。 是失真函数的数学期望，为非负函数，其下限为0。D 的下限也必然为0，这就是不允许任何失真的情况。 信源的最小平均失真度 只有当失真矩阵中每行至少有一个为0时，允许失真度D取得最小值，即Dmin=0。 R(0)=H(X)，即信息率至少为信源的信息熵。

21 4.1 基本概念 因为D越大，R(D)越小，最小为0，当D再大时，R(D)也只能为0。因此，Dmax是满足R(D)=0的所有平均失真度D中最小值。 令试验信道特性p(bj|ai)=p(bj)(i=1,2,…,n),则X和Y相互独立，等效于通信中断，必有I(X,Y)=0,即R(D)=0。 对满足p(bj|ai)=p(bj)的所有试验信道， 计算平均失真度，其最小值即为Dmax D* Dmax D R(D) H(X) R(D*) 则 令

22 4.1 基本概念 [例]离散二元信源 ，求Dmax [例]离散二元信源 ，求Dmax x1 y1 (1/3) y2 x2 (2/3)
xi dij yj 1 [例]离散二元信源 ，求Dmax

23 4.1 基本概念 2) R(D)对允许平均失真的下凸性 对任一0≤θ≤1和任意平均失真度D',D" ≤Dmax，有
率失真函数R(D)的定义域为(Dmin, Dmax)。一般情况下: (1)Dmin=0, R(Dmin) = H(X)； (2)当D≥Dmax时，R(D)=0； (3)当Dmin<D<Dmax时，H(X) >R(D) > 0 2) R(D)对允许平均失真的下凸性 对任一0≤θ≤1和任意平均失真度D',D" ≤Dmax，有 3) R(D)函数的单调递减性和连续性

24 4.1 基本概念 结论: 1. R(D)是非负函数； 定义域0～Dmax , 值域0～H(X) 2. R(D)是单调不增、下凸的连续函数
D* Dmax D R(D) H(X) R(D*) 结论: 1. R(D)是非负函数； 定义域0～Dmax , 值域0～H(X) 2. R(D)是单调不增、下凸的连续函数 3.意义:对规定的失真D*，可算得R(D*)，于是 (1) R(D*)是理论极限—— 为满足D≤D*，实际R≥R(D*) (2) 压缩比极限——K=H(X)/R(D*)

25 4.2离散信源的信息率失真函数 离散信源信息率失真函数的参量表达式
对于固定的信源p(ai)和失真函数d(ai,bj)，在满足保真度准则的条件 下，在试验信道PD中选择p(bj|ai)，使得平均互信息I(X;Y)取得最小值。 自然对数 并且 和 可采用拉格朗日乘子法，构造一个新的目标函数进行求解。

26 4.2离散信源的信息率失真函数 其中，S和 为拉格朗日乘子。 对p(bj|ai)求偏导数，并令导数为零，即

27 4.2离散信源的信息率失真函数 两边除以p(ai), 并令

28 4.2离散信源的信息率失真函数 两边对j求和 两边乘以p(ai),再对i求和 或 可求解出以S为参量的p(bj)和p(bj|ai)

29 4.2离散信源的信息率失真函数 选择使p(bj)非负的所有S,得到的D和R值，可以得到R(D)曲线. 可得以S为参量的平均失真函数

30 4.2离散信源的信息率失真函数 [具体方法] (1) 选择使p(yj)非零、非负的S值，由(4.2.12)得i
(2) 再由(4.2.14)、 (4.2.15)解得D(S)、R(S) (3) 可得R～D曲线上一点，并得R～D曲线 (4) S(D)=dR(D)/dD ——R～D曲线斜率

31 4.2离散信源的信息率失真函数 两边对S为求导

32 4.2离散信源的信息率失真函数 两边乘以p(bj)并对j求和，可得 由于 可得 S就是R(D)函数的斜率

33 4.2离散信源的信息率失真函数 [S(D) ～D曲线性质] ①由于R(D)的严格递减和下凸性，斜率为负——S(D)＜0
②单调递增—— dS(D)/dD＞0 ③Smin→-∞ ，D=0处R(D)的斜率 ④当D→Dmax时， Smax多为某一负值，最大值为0。然后在Dmax点处，S曲线突跳到零。 R(D) S(D) Dmax D

34 4.2离散信源的信息率失真函数 二元及等概率离散信源的信息率失真函数 设二元信源 对称失真矩阵
输出符号集Y: {0,1}, 计算信息率失真函数R(D) (1) 求Dmax

35 4.2离散信源的信息率失真函数 (2) 计算S和Smax 由 P115错误 P108错误

36 4.2离散信源的信息率失真函数 由于

37 4.2离散信源的信息率失真函数 由于

38 4.2离散信源的信息率失真函数

39 由 显式表达式 可得 令 ，可得

40 4.2离散信源的信息率失真函数 (3) 计算R(D) 由 信源熵 因容忍一定的失真度而可能压缩的信息率

41 4.2离散信源的信息率失真函数 (4) R(D)曲线和S(D)曲线( =1) 1)  =1，即d(xi, yj)为误码个数，
其数学期望为误码率 D——允许的误码率，于是 2) R(D)~D曲线还与p有关 p=1/2时，若D=0.5，则R=0 p=1/4时，若D=0.25，则R=0 D R(D) P=1/2 S(D) p=1/4 A 3) 等概时R(D)曲线在最上，面对相同的D，等概时R(D)最大 4) S(D)曲线只有一条，但定义域不同 p=1/2时，S(D)定义域：D=0~0.5， 连续， Smax=0 p=1/4时，S(D)定义域：D = 0~0.25，在0.25处断开

42 4.2离散信源的信息率失真函数 对于二元信源呈等概率分布时

43 4.2离散信源的信息率失真函数 对于n元信源呈等概率分布时

44 4.2离散信源的信息率失真函数 信源熵 因容忍一定的失真度而可能压缩的信息率

45 4.2离散信源的信息率失真函数 信息率失真函数与信息价值 香农信息论的信息量——客观 信息量的重要性因人而异——主观
把平均失真理解为平均损失，便可衡量价值 一、例——某工厂 生产：合格品—x1，p(x1)=0.99 废 品—x2，p(x2)=0.01 检验：合格品—y1，合格品报废—损失1元 废 品—y2，废品出厂—损失100元 建模型 检验不正确引起的损失——信道传输失真 信源 信道 X (生产) (检验) Y

46 4.2离散信源的信息率失真函数 1.产品未经检验全部出厂 p(y1/x1) = p(y1/x2) = 1
[结论]产品未经检验全部出厂引起损失1元 信源 信道 X (生产) (检验) Y

47 4.2离散信源的信息率失真函数 2.产品未经检验全部报废 p(y1/x1) = p(y1/x2) = 0
[结论] ①产品未经检验全部报废引起损失0.99元 ②出厂一个废品比报废99个合格品的损失大 ③根据Dmax定义， Dmax = 0.99 ④若允许损失为0.99元，则无需检验，把产品报废即可 信源 信道 X (生产) (检验) Y

48 4.2离散信源的信息率失真函数 3. 检验完全正确 p(y1/x1) = p(y2/x2) = 1
[结论] ①为达无错检验，需要0.081bit信息量 ② 0.081bit信息量避免了0.99元的损失 每bit价值 = 0.99/0.081=12.2元/bit 信源 信道 X (生产) (检验) Y

49 4.2离散信源的信息率失真函数 4. 检验有一定误差(设错判概率为0.1) p(y1/x1) = p(y2/x2) = 0.9
[结论1] 比最大损失(0.99元)减少了0.791元， 原因是检验获得了信息量I(X;Y) p(x1) 0.99 p(x2) 0.01 p(y1) p(y2) 0.9 0.1

50 4.2离散信源的信息率失真函数 每bit价值=0.791/0.025=31.6元/bit [结论1]
p(x1) 0.99 p(x2) 0.01 p(y1) p(y2) 0.9 0.1 每bit价值=0.791/0.025=31.6元/bit

51 4.2离散信源的信息率失真函数 检验完全正确 检验有一定误差 产品未经检验全部报废 [结论2] 有误差检验的信息价值比无误差检验的高！
[结论2] 有误差检验的信息价值比无误差检验的高！ 可画出信息(R) ～损失(D)曲线 反之， D(R) ——信息率为R时的平均损失 D(元) R(D)(bit) H(X) 0.081 0.025 Dmax 检验完全正确 检验有一定误差 产品未经检验全部报废

52 4.2离散信源的信息率失真函数 信息价值 1. 价值——V = Dmax– D(R) —曲线上某点与Dmax间纵轴距，表明损失减少量
2. 价值率 —每bit信息提供的损失减少量 [性质] S——R(D)曲线斜率 表明， R↑→V ↑ 概念：提供的信息量越大,价值越大,损失越小 R(bit) H(X) 0.081 0.025 Dmax 0.99 0.199 D(R)

53 4.2离散信源的信息率失真函数 [上例] 1) 不检验，全部报废 —D = Dmax=0.99 元情况 2) 无错检验
—D = 0，R=H(X)=0.081bit情况 此时, V = Dmax– 0 = 0.99 元 v = V/R = 12.2 元/bit 3) 有错检验 —D = 0.199元，R=0.025bit情况 此时, V = Dmax– D = 元 v = V/R = 31.6 元/bit R(bit) H(X) 0.081 0.025 Dmax 0.99 0.199 D(R)

54 4.4限失真信源编码定理 限失真信源编码定理 设有一离散、平稳、无记忆信源，其率失真函数为R(D)。则对任意选定的D≥0，当传信率R>R(D)时，只要信源序列长度L足够长，必存在一种编码方式C，使译码后的失真 并且当L→∞时，→0 反之, 若R<R(D), 则无论采用什么编码方式，都有

55 4.4限失真信源编码定理 [说明] 1.若系统R>R(D) 则必可设计一种编码方式,满足 若系统R< R(D) 则无法满足 要求
则无法满足 要求 2.[逆定理]若已规定满足失真度准则 , 则对所有设计均有R≥R(D) 3. R<R(D)与 不能同时满足

56 4.4限失真信源编码定理 香农信息论： 4. 任何设计所得到的工作点必 在率失真函数曲线R(D)上面 RQ与R1之比——
理论上存在的最大可能压缩比 香农信息论： 三个基本概念—信源熵、信道容量、率失真函数，都是临界值 三个编码定理—无失真信源编码、限失真信源编码、信道编码， 都是存在性定理 D Dmax D R(D) H(X) R1 RQ Q