通信理论与系统一课件

通信理论与系统（一）主讲：毛雪松1第一讲：连续信源的熵第二讲：一般离散信道、扩展信道的信道容量与连续信道的信道容量第三讲：限失真编码第四讲：信息安全初步2第一讲：连续信源的熵第二讲：一般离散信道、扩展信道的信道容量与连续信道的信道容量第三讲：限失真编码与信息安全初步第四讲：网络信息论初步3连续信源平稳信源非平稳信源连续新源：输出消息在时间和取值上都连续的新源，用随机过程x(t)来描述。统计特性随时间的平移是否变化4平稳信源统计特性与时间起点无关的连续信源。集平均以概率1等于时间平均的平稳随机过程。遍历过程56连续信源的熵几种特殊连续信源的熵连续信源熵的性质及最大连续熵定理熵功率连续信道的信道容量第一讲主要内容7计算连续信源熵的两种方法：将连续信源数字化，再用离散熵计算先进行抽样，再把抽样序列看作量化单位△趋于0时的情况，然后定义计算信源熵。12主要讨论单变量连续新源的信息测度。8一维概率密度函数（边缘概率密度函数）：9其中，F(x)、F(y)满足：条件概率密度函数为：10联合概率密度函数为：边缘概率密度函数为：11单变量连续信源的数学模型为：并满足12中值定理：13xp(x)Oaba+(i-1)∆a+i∆推导连续信源熵：14连续信源熵（相对熵）定义：为了在形式上与离散信源熵统一熵差仍然具有信息的特征1215求均匀分布的连续信源熵例1解答：16连续信源熵

相对熵离散信源熵

绝对熵17其他连续熵的定义：18连续信源的熵几种特殊连续信源的熵连续信源熵的性质及最大连续熵定理熵功率连续信道的信道容量19均匀分布的连续信源的熵12021高斯分布的连续信源的熵22223结论高斯信源的熵仅与方差有关。原因24指数分布的连续信源的熵325返回连续信源的熵几种特殊连续信源的熵连续信源熵的性质及最大连续熵定理熵功率连续信道的信道容量26连续信源熵可为负值连续信源熵的可加性推广到N个变量的情况1227283平均互信息的非负性2930对称性：数据处理定理：31最大连续熵定理4对离散信源，当信源等概分布时，信源熵取极大值；连续信源如果没有限制条件，就没有最大熵，在不同限制条件下，信源的最大熵也不同。信源输出值受限；信源输出的平均功率受限；信源输出值的均值受限。32限峰值功率的最大熵定理

若代表信源的N维随机变量取值被限定在一定范围内，在有限定义域内均匀分布的连续信源有最大熵。133设N维随机变量其均匀分布的概率密度函数为：34可以证明35证明36限平均功率的最大熵定理

平均功率为P，均值m受限，当信源概率密度函数为正态分布时，具有最大熵。237383940

当峰值功率受限、平均功率受限，连续信源的统计特性分别与两种常见噪声——均匀噪声和高斯噪声的统计特性相一致时，信源具有最大连续熵。

因为噪声是一个最不确定的随机过程，而最大的信息量只能从最不确定的事件中获得。41均值受条件下的最大熵定理连续信源输出非负信号的均值受限条件下，指数分布的连续信源具有最大熵。342记指数分布条件下的熵为Hc[p(x),x]，其它任意分布的概率密度函数为q(x)，相应的熵为Hc[q(x),x]，由限制条件有：计算指数分布的信源熵为：43任意分布的信源熵为：44连续信源不存在绝对的最大熵。连续最大熵与信源的限制条件有关。在不同的限制条件下，有不同的最大连续熵。45连续信源的熵几种特殊连续信源的熵连续信源熵的性质及最大连续熵定理熵功率连续信道的信道容量46信息变差：47设连续新源X在概率密度为p(x)时达到最大熵值Hc[p(x),X]，其它概率密度函数q(x)达到的熵Hc[q(x),X]：48测定q(x)之前连续信源的不确定度测定q(x)之后所消除的不确定度剩余的不确定度常见信源是均值为0，平均功率受限信源49信源限定平均功率减小时，最大熵随之变小

熵功率：50

推广到N维，假定各随机变量统计独立51第一讲：连续信源的熵与连续信道的信道容量第二讲：一般离散信道、扩展信道的信道容量与连续信道的信道容量第三讲：限失真编码第四讲：信息安全初步52一般离散信道的信道容量扩展信道（多符号离散信道）的信道容量连续信道的信道容量53定理一：设f(X)是定义在所有分量均非负的半n维空间上的凸函数，其中X=(x1,x2,…,xn)，假定f(X)的一阶偏导数存在，且在定义空间上连续，则f(X)在定义空间上点X=X*处取最大值的充要条件是54I(X;Y)是PX的上凸函数，可得出I(X;Y)达到最大值，即信道容量解的充要条件。55先定义一个新的互信息量：称为偏互信息，只对输出Y求统计平均，代表从输出Y中得到关于输入ai的信息。得出I(X;Y)是I(ai;Y)关于ai求统计平均。56定理二（一般DMC信道容量解的充要条件）：一般DMC{X,Y,PY|X}，其平均互信息量I(X;Y)在输入分布为时取最大值的充要条件是57证明：根据定义，DMC的信道容量就是I(X;Y)在约束条件下的最大值。定义将条件约束极值问题转化为无条件约束极值问题。上凸函数PX的线性函数也是上凸函数58根据定理一，上凸函数f(PX)在取最大值的充要条件是59计算偏导数60计算偏导数61于是充要条件变为：为确定常数λ，对第一式两边关于ai求统计平均当信道平均互信息量达到最大，所有概率非零的输入符号都传送相同的平均互信息量62例1.设信道转移矩阵为求信道容量C和最佳输入分布解答：信道为一般信道，设最佳输入分布为PX*

=

{p*(a1),p*(a2),p*(a3)}，3个输入概率外加信道容量C需列4个方程，根据定理二有6364化简得：解得：65转移概率p(bj|ai)已知，输出分布p(bj)已求出，根据求出p(ai*)66例2：求Z型信道的信道容量C解答：根据定理二列出方程化简得67解得信道容量的迭代算法681972年，S.Arimoto和R.E.Blahut给出DMC信道容量计算的迭代算法：设DMC的转移概率矢量为，记是任意给定的一组初始输入分布，其所有分量均不为零，按下式不断对输入分布进行迭代、更新其中一般信道容量计算的迭代流程69开始yesno一般离散信道的信道容量扩展信道（多符号离散信道）的信道容量连续信道的信道容量70多符号离散信道71离散信道噪声N次扩展信道模型单符号信道：输入和输出都只有一个随机变量多符号信道：序列的传送，也叫扩展信道72N次扩展信道模型转移概率矩阵N次扩展信道的数学模型：离散无记忆信道的N次扩展信道和独立并联信道的信道容量N次扩展信道离散无记忆：YK仅与XK有关73例1求二进制对称信道的2次扩展信道的数学模型74解答：单符号二进制对称信道的输入和输出符号集合为二次扩展信道的输入和输出符号集合为75计算转移概率以此类推得到二次扩展信道的转移概率矩阵扩展信道的平均互信息量76定理1：信源发出的N元随机变量序列77通过信道传送输出N元随机变量序列若信道无记忆，则有证明：78798081定理2：信源发出的N元随机变量序列81通过信道传送输出N元随机变量序列若信源无记忆，则有证明：82因为信源无记忆，故83推论：信源发出的N元随机变量序列通过信道传送输出N元随机变量序列若信源和信道均无记忆，则有84N次扩展信道的信道容量（离散无记忆信道）对同一信道，所有Ck均相同，所以有85串联信道信道IQ1信道IIQ2XYZ86设N个单元信道的转移概率矩阵分别为Q1Q2

…QN，则整个串联信道的转移概率矩阵为两级串联信道的数据处理定理：两级串联信道，消息经过多级处理，随着处理器数目的增多，输入消息与输出消息之间的平均互信息量趋于减小。I(X;Z)≤I(Y;Z)I(X;Z)≤I(X;Y)数据处理定理的证明两式相减同理可得假定在Y已知的情况下，X与Z独立87数据处理定理的举例已知：计算：重写转移概率的表示形式：行表示输入，列表示输出88a1a2b1b2c1c2XYZ8990例：求两个相同二元对称信道组成的串联信道的信道容量(BSC)解答：单个BSC的转移概率矩阵为串联信道转移概率矩阵为串联信道仍为二元对称信道91如果N个BSC相串联，可用正交变换的方法求出总的转移概率矩阵也是对称矩阵92可以看出，只要BSC有噪声，0<p

<1，则1YNY93独立并联信道信道是独立无记忆的，因此一般离散信道的信道容量扩展信道（多符号离散信道）的信道容量连续信道的信道容量94连续信道的数学模型95连续信道XYfX|Y(y|x)RRZ单维连续信道的数学模型：{X,fX|Y(y|x),Y}多维随机变量序列：无记忆信道取值上连续的信道单维连续信道96连续信道的平均互信息量且连续信道的信道容量97连续信道的信道容量与输入概率密度函数有关找出fX(x)为何种函数时I(X;Y)达到最大值不加条件约束实际情况：b(X)为限制条件:b(X)E(X2)≤Ps98连续信道在输入平均功率受限时的信道容量或只对特殊信道，如加性噪声信道，给出解析解加性高斯噪声信道的信道容量99如果信道的输入X，输出Y以及噪声Z这三个随机变量之间满足：Y=X

+Z且输入X与干扰无关，则称该信道为加性噪声信道。100求信道容量转化为求h(Y)的最大值101最常见的加性噪声为高斯噪声均值为0，方差为PN=σ2的加性高斯噪声微分熵为：于是当输入平均功率受限时求信道容量关键在于求Y关于fX(x)的最大熵求h(Y)最大熵的步骤假定信道输入X的均值为0，则信道输出Y的均值为E(Y)=0平均功率E[Y2]=E[(X+Z)2]=E[X2]+E[Z2]+2E[XZ]

=E[X2]+E[Z2]

≤PS+PN当平均功率受限时，随机变量只有服从高斯分布时熵才能达到最大值，因此102已知X和Y的最佳分布后，求出Y关于概率密度函数的最大熵103X=Y-Z推出X也服从高斯分布上述推导说明，在加性高斯噪声信道中传输信息，高斯分布的输入信号是最有效的，信道容量与PS/PN有关；反之，对无记忆加性噪声信道，假设输入信号服从高斯分布，则服从高斯分布的噪声使信道的平均互信息量最小（高斯分布的噪声最有害）。104一般加性噪声信道的信道容量的界对于一般的无记忆加性噪声信道，假设输入信号的平均功率受限于PS，噪声的平均功率受限于PN，则信道容量的上、下界限为105其中是Z的熵功率，h(Z)为微分熵。106证明：先证下界，假设输入信号和噪声均值均为0，因为信道容量是平均互信息的最大值，即而107再证上界：输入XPS噪声ZPN，输出信号Y

PS+PNY服从高斯分布时，熵最大比特形式已知条件波形信道输入输出随时间连续取值、且取值是连续区间的信道，也称模拟信道108波形信道X(t)Y(t)Z(t)连续信道采样用N维连续信道近似波形信道波形信道的信道容量109波形信道为无穷维连续信道一般性研究在数学上相当困难。带限、加性高斯白噪声信道110白噪声的功率谱密度相关函数平均功率111根据采样定理，带限为B，限时为T的随机信号Z(t)可用N=2BT个相互独立的随机变量序列来近似表示。设Z(t)服从均值为0的高斯分布，采样后得到的2BT个独立分量也服从均值为0的高斯分布，各独立分量的平均功率等于[0,T]时段内总功率除以分量个数112按下面步骤求出带限B、限时T的加性高斯白噪声信道的信道容量：(1)因为是加性信道，Y(t)=X(t)+Z(t)用N=2BT个采样点近似113(2)信道无记忆、噪声相互独立连续信道一维连续加性噪声信道并联…

…Zk均值为0、平均功率N0/2的高斯分布。114Xk平均功率受限，高斯分布时达到信道容量子分量必须适当分配各子信道的平均功率，才能使I(X(t);Y(t))达到最大115(3)求连续信道的信道容量，相当于在约束条件下求凸函数在约束条件下求极值的问题116由拉格朗日乘法：当所有输入分量的平均功率都相等时，出现最大值，即信道容量为单位化为bit/s香农信道容量公式用频带换信噪比，即扩频技术117增大B提高信道容量可用于频率资源丰富的环境下。扩频方法提高信道容量的作用有限：用信噪比，B不变，增大PS/PN可增大C，但方法也有局限性。因为PS/PN的增大是靠增大输入功率PS来实现的，而118随着PS的增大，C(PS)的增长率逐步变小，直至为0。表明：当PS大到一定程度后，即使PS增加很多，C(PS)的增长幅度却很小。第一讲：连续信源的熵与连续信道的信道容量第二讲：一般离散信道与扩展信道的信道容量第三讲：限失真编码第四讲：信息安全初步119失真测度信息率失真函数及其性质信息率失真函数的计算限失真信源编码定理120限失真编码保熵变换并非总是必须的；保熵编码并非总是可能的；降低信息率有利于传输和处理。121定义：在信源编码时，引入一定的失真。主要任务：在允许的失真范围内把编码后的信息率压缩得最小引入限失真编码原因：失真测度122信源信道（信源编码器）U{u1,u2,…,ur}V{v1,v2,…,vs}无失真编码无损信道H(U|V)=0损失熵H(V|U)=0噪声熵限失真编码有损信道ui和vj之间的误差用一个非负实值函数d(ui,vj)表示，称为失真测度。失真测度的矩阵表示123将r×s个d(ui,vj)排成矩阵形式，称为失真矩阵对所有符号的失真度{d(ui,vj)}i,j取统计平均，称为平均失真度，即例1设信源U取值于{0,1}，编码器输出取值于{0,1,2}，编码器相当于一个二元删除信道，规定失真度为：d(0,0)

=

d(1,1)

=0;d(0,1)

=d(1,0)=1;d(0,2)=d(1,2)=0.5则失真矩阵为：124失真度的函数形式失真度函数唯一限制条件是d(ui,vj)非负。常用的失真度函数有：125离散信源连续信源a1

b1a2b2anbn126汉明失真127符号序列的失真度函数设编码器输入αh和输出βl均为N长符号序列，即128将N长符号序列的失真度定义为第k位符号的失真度符号序列的平均失真度129将N长符号序列的平均失真度定义为当信源和信道均无记忆时单符号的平均失真度失真测度信息率失真函数及其性质信息率失真函数的计算限失真信源编码定理130保真度准则131要求平均失真度保真度准则满足保真度准则的信道称为D允许信道。所有D允许信道的转移概率组成一个集合，记为BD，即在满足保真度准则下实现限失真编码。信息率失真函数132在BD中找一个PU|V，使I(U;V)最小，这个最小的平均互信息量称为信息率失真函数，记为R(D)。或者离散信源保真准则下必须传输的信息率序列的信息率失真函数133要求平均失真度的信道集合保真度准则BND中，使I(UN;VN)最小的转移概率，为N次扩展信源的信息率失真函数，记为R(ND)。134若信源信道无记忆，则编码信道的信息率R为通过信道的平均互信息量I(U;V)。为便于传输，希望将R压缩到最小值R(D)。若R<R(D)，则不满足保真度准则。信息率失真函数的性质RD的定义域是[0,Dmax]135证明：RD是D的函数；D的下界是0；Dmax定义为满足R(D)=0的所有D中最小值。136例：设输入概率和失真矩阵分别为求Dmax137R(D)是D的下凸函数：若有λ1、λ2以及D1、D2满足λ1+λ2=1和D=λ1D1+λ2D2，则有R(D)≤λ1D1+λ2D2138证明：同一信源，两种转移概率根据率失真函数定义：139定义一个新的转移概率在该转移概率下编码器的平均失真140设编码器的平均互信息量为I(U;V)，则由于平均互信息量是关于转移概率的下凸函数，则得到因此得到R(D)是定义域上的非增函数141证明：设D2≥D1，则对应编码信道转移概率有如下关系也就是即R(D)是定义域上的非增函数R(D)的函数曲线142R(D)DDminDmax失真测度信息率失真函数及其性质信息率失真函数的计算限失真信源编码定理143信息率失真函数的计算条件已知信源的概率分布144145失真函数为d(ui,vj),

i=1,…,r；

j=1,…,s，选取合适的试验信道p(v|u)，计算平均互信息I(U;V)的极小值。计算的约束条件为：计算方法：应用拉格朗日乘子法得出146其中例：设输入、输出符号集合为U=V={0,1}，输入概率密度分布为p(0)=p，p(1)=1-p，且0<p<1/2，失真矩阵为147求信息率失真函数R(D)。解答：(1)确定R(D)的定义域每行最小值都等于0，因此最小失真度148得出R(D)的定义域为(0,

p)149（2）求λ1和λ2150（3）求p(v1)和p(v2)151（4）求D(S)152（5）求R(D)153求R(D)完整表达式迭代计算信息率失真函数154155k=0;S=-Np(vj|ui)(0)

p(vj|ui)p(vj)p(vj|ui)R(k)(D)R(k)(D)|R(k)(D)-R(k-1)(D)|<

？S=S+stepS:toend?plot(S,R)k=k+1nonoyesyes123156123失真测度信息率失真函数及其性质信息率失真函数的计算限失真信源编码定理157香农第三编码定理：设离散无记忆平稳信源的信息率失真函数为R(D)，只要满足R>R(D)，当信源序列K足够长时，一定存在一种编码方法，其译码失真小于或等于D+，其中是任意小的正数；反过来，若R<R(D)，则无论采用什么样的编码方法，其译码失真必大于D。158第一讲：连续信源的熵与连续信道的信道容量第二讲：一般离散信道与扩展信道的信道容量第三讲：限失真编码第四讲：信息安全初步159密码基本知识古典密码体制现代密码体制密码体制的安全性测度160重要事件

1949年，香农发表了著名论文“密码体制的通信理论”。将密码推向科学轨道。161密码发展：

手工密码简单器械密码机械密码机电密码电子密码现代分组密码公钥密码162密码学

密码编码学

密码分析是破译密码的科学和技术

是密码体制的设计学163保密通信系统模型：164明文空间P：全体明文的集合密文空间C：全体密文的集合密钥空间K：全体密钥的集合也可以用数学方式描述：1

2

3

165解密算法D：解密密钥控制的解密变换的集合加密算法E：4

加密密钥控制的加密变换的集合5

166安全概念

无条件安全

计算安全

好的密码体制至少满足两个条件：已知明文和加密密钥，计算密文容易；未知解密密钥，由密文推知明文困难。安全等级：167密码分析攻击有6类

惟密文攻击

已知明文攻击

选择明文攻击

自适应选择明文攻击

选择密文攻击

选择密钥攻击

168分析方法

数学方法

边信道攻击

169数学方法

穷举搜索

统计分析

逆向推理

线性分析

差分分析

相关分析

170边信道攻击

时间攻击

能量攻击

电磁攻击

故障攻击

171密码基本知识古典密码体制现代密码体制密码体制的安全性测度172加密基本思想

代替换位173单表密码

凯撒密码

密钥词组密码

乘法密码

仿射密码

随机代替

174明文abcdefghijklm密文DEFGHIJKLMNOP明文nopqrstuvwxyz密文QRSTUVWXYZABC1．凯撒密码

175【例】

明文：thisisabook密文：WKLVLVDERRN该算法表示为（7.2.1）c代表密文，p代表明文176

设密钥为TIME【例】2．密钥词组密码明文abcdefghijklm密文TIMEABCDFGHJK177nopqrstuvwxyzLNOPQRSUVWXYZ如果明文为code，则密文为MNEA

明文密文178多表密码

普莱费尔密码维吉尼亚密码希尔密码博福特密码

179【例】

密钥是monarchy，则构造的字母矩阵：MONARCHYBDEFGI/JKLPQSTUVWXZ字母矩阵表1．普莱费尔密码180加密算法：

ci

pi+ki(mod26)解密算法：

pi

ciki

(mod26)2．维吉尼亚密码181该密码算法取m个连续的明文字母，并用m个密文字母代替若m

3，该系统可以描述为3．希尔密码182这可以用列向量和矩阵表示为:

或

C

KP（mod26）183例如

考虑明文为keyworder，使用的加密密钥为:K

该明文的前三个字母被表示为向量（10

4

24），

运算结果为KMS

184换位密码

【例】

明文为cryptographyisanappliedscience假设密钥是creny将明文按照密钥的长度逐行列出，185密钥14235cryptographyisanappliedscience换位表186然后依照密钥决定的次序按列依次读出因此，密文为COHNIIYRIPDNPASPSCRGYAEETPALCE187密码基本知识古典密码体制现代密码体制密码体制的安全性测度188现代密码体制

对称密码体制

非对称密码体制

消息摘要技术

1891.对称密码

对称密码模型190发送方通过加密算法根据输入的消息P和密钥K生成密文即

191接收方通过解密算法根据输入的密文C和密钥K恢复明文即

192数据加密标准（DES）算法

初始置换IP64位明文

乘积变换末置换IP-1密钥产生64位密文

19364位明文L1=R0R0L0R1=L0⊕f(R0,K1)L15=R14L16=R15L2=R1R2=L1⊕f(R1,K2)R16=L15⊕f(R15,K16)R15=L14⊕f(R14,K15)64位密文+f+f+f初始置换IPIP-1k1k2k16194一轮迭代的过程P盒换位1953DES

三重DES方法需要执行三次常规的DES加密步骤，但最常用的三重DES算法中仅仅用两个56位DES密钥196IDEAIDEA的密钥长度128位在目前技术条件下具有足够的安全强度是一种迭代分组加密算法分组长度64位，8轮迭代，还有一轮输出变换1972.非对称密码

公钥密码体制的提出

非对称密码模型198公钥密码体制的基本原理

公钥密码体制加密的算法是基于单向陷门函数

199单向陷门函数是满足下列条件的函数f：

给定x，计算y

f(x)是容易的；

给定y，计算