信息传输原理

第一章 绪论

信息的含义

信息、信号、消息之间的区别与联系?
1、信息：一个抽象的概念
2、消息：信息的载体,内具体的概念。
如：文字、语音、图像等
3、信号:表示消息的物理量,把消息变换成适合信道传输的物理量。信号携带着消息,是消息的运载工具。
如:电信号、信号等(信号的特性可以通过幅度、频率、相位等参量来描述)

信息论的研究方法

通信的主要任务是将信息的外在形式==准确、快速==地传递给接受者

现代信息论的起源

  • 选择题

    • 狭义信息论

      • 我们研究的

    • 一般信息论

    • 广义信息论

信息论研究问题基本方法

  • 1 形式化假说
    • 用数学方法描述
  • 2 非决定论观点
    • 承认偶然性也承认必然性,利用概率论研究
  • 3 不确定性观点
    • “不知道”与“疑问”就是知识上的一种不确定性
      -接收者获得的信息量用接收前的“不确定性”的消除量来衡量
    • 不确定性是用==概率==来衡量的
      • 消息发生概率越小,此消息含有的信息量越大
      • 消息的随机性越大,此消息含有的信息量越大

信息传输系统基本模型

image-20230222102704509

  • 信道：传输信号的通道。
    • 狭义信道：物理介质【有线信道：比如电线、电缆、光缆等。
      无线信道：比如电磁空间(地波传播、天波传播、视线传播等)】
    • 广义信道：包括调制解调、收发转换装置。

image-20230222104114083

C1、C2都是等长码

变长码(即时码)需要注意歧义

研究信息传输(通信)系统的目的

可靠性、有效性、保密性和认证性四者构成现代通信系统对信息传输的全面要求。

第二章

  • 1、按照信源发出的消息在时间和空间上的分布情况：

    • 时间离散空间离散信源: 离散信源

    • 时间离散空间连续信源： 连续信源

    • 时间连续空间离散信源

    • 时间连续空间连续信源： 波形信源

  • 按照信源在不同时刻发出的消息之间有无依赖关系分为

    • 有记忆信源
    • 无记忆信源
    • 例1：”基于上下文”
      例2：一帧图像

  • 按照信源的平稳特性,也就是信源发出消息序列的统计特性与时间的推移有无关系,分为

    • 平稳信源
    • 非平稳信源
      如果信源发出消息序列的统计特性与时间的推移没有关系,称为
      平稳信源。否则,称为非平稳信源。

2.1 离散信源

定义:

信源发出的消息在时间和空间上的分布都是离散的。

例如：掷骰子、投硬币、书信文字、电报符号等

分类

image-20230227083810266

单符号离散无记忆信源 概率模型

image-20230227084920214

2.2离散信源的自信息、熵及其性质

自信息

image-20230227092626290

$I(a_i)$的物理意义(含义)：

(1)事件$a_i$发生以前,表示事件$a_i$,发生的不确定性;
(2)事件$a_i$发生以后,表示事件$a_i$,所提供(或所含有)的信息量。

image-20230227093439088

计算提示：$log_{10}2 = 0.301$

比如$log_{2}3 = \frac{lg3}{lg2}$

$I(a_i)$的性质：

image-20230227094311486

信息熵

image-20230227094851086

$H(X)$的物理意义(含义)：

  • H(X)表示信源输出前,信源的平均不确定性;
  • H(X)表示信源输出后,每个消息(符号)所提供的平均信息量;
  • H(X)表征了随机变量X的随机性。

例题

image-20230301102615783image-20230301102722148

概率矢量

定义：我们用概率矢量P来表示信源的概率分布P(x)
$$
\overrightarrow P=(p( a_ {1} ),p( a_ {2} ), \cdots ,p( a_ {q} ))=( p_ {1} , p_ {2} , \cdots , p_ {q} ), \ \sum _ {i=1}^ {p} =1, p_ {i} \geqslant 0(i=1,2, \cdots ,q)
$$

H(X)表示方法说明：

  • 用H(X)表示以离散随机变量X描述的信源的信息熵;
  • 用H($\overrightarrow P$)或Hp(P1 P2,….,pq)表示概率矢量为P=(P1,P2,.,pq)的q个消息信源的信息熵。
  • 若当 q=2 时,因为 pi+p2=1,可以将两个消息的熵函数写成H(p1)或H(p2)。

信息熵又可表示为:
$$
H(X)=- \sum _ {p_ {1}}^q pi\log {p_ {i}} =H( p_ {1} , p_ {2} , \cdots , p_ {q} )=H(\overrightarrow P)
$$

$H(X)$的性质：

  • 对称性

    • 当变量$p1,P2,….p_q$的顺序任意互换时,熵函数的值不变。

  • 确定性

    • $$
      H(1,0)=H(1,0,0,0)= \cdots =H(1,0, \cdots ,0)=0
      $$

  • 非负性(仅适用于离散信源)

    目前我们研究的基本上都是离散信源

    • 这种非负性对离散信源的熵是合适的,对连续信源来说这一性质并不存在。在相对熵的概念下,可能出现负值。

      可以出判断题:比如问信源信息熵都是正值就是错的

  • 扩展性

    • 信源消息数增多时,若这些消息对应的概率很小(接近于0),则信源的熵不变。

  • 可加性

    • 统计==独立==的信源X和Y的联合信源的熵等于信源X和Y各自的熵之和。
      $$
      H(XY) = H(X)+H(Y)
      $$
    • image-20230301112559289

  • 强可加性

    • 两个==互相关联==的信源X和Y的联合信源的熵等于信源X的熵加上在X已知X的条件下信源Y的条件熵。
      $$
      H(XY) = H(X)+H(Y|X) = H(Y)+H(Y|X)
      $$

      其实可以知道当X Y独立时,$H(Y|X) = H(Y)$

    • 推广
      $$
      H(X_1X_2…X_N) = H(X1)+H(X2|X1)+…H(X_n|X1X2…X_{N-1})
      $$

  • 极值性

    • 在离散信源情况下,信源各符号等概率分布时,熵值达到最大。
      $$
      H( P_ {1} , P_ {2} , \cdots , P_ {q} ) \leqslant H( \frac{1}{q} , \frac {1}{q} ,\cdots
      , \frac {1}{q} )= \log {q}
      $$

    • 对于具有q个符号的离散信源,只有在q个信源符号等可能出现的情况下,信源熵才能达到最大值,称为最大离散熵定理。

    • 推广

      • 条件熵小于等于无条件熵
        $H(Y|X)<H(Y)$
      • 多条件熵小于等于少条件熵
        $H(Z|XY)<H(Z|X)$

  • 上凸性

    • 熵函数H(P)是概率矢量P=(P1,P2,pq)的严格是∩型函数。

条件熵的计算

$$
H(Y|X) =-\sum _ {i=1}^r \sum _ {j=1}^s p(x_iy_j)\log{(x_i|y_j)}
$$

2.3 离散无记忆扩展信源

image-20230306083311450

随机矢量X组成的新信源称为离散无记忆信源X的N次扩展信源,一般记为X^N^。

image-20230306083633982

因为信源X是无记忆的(彼此统计独立),则有：$p( \alpha _ {i} )=p( a_ {i1} \cdots a_ {iN} )=\prod\limits_{k=1}^Np( a_ {ik} )$

根据熵的计算公式：

$$
H(X)=H(X^N)=NH(X)
$$

image-20230306085248701

2.4 离散平稳信源(相当于非独立条件)

  • 定义:假设信源输出的是平稳的随机序列,即信源所输出的符号序列的概率分布与时间起点无关。
    • 一维离散平稳信源:无论在什么时刻均按 p(x)的概率分布输出符号。
    • 二维离散平稳信源:二维离散平稳信源在任何时刻,连续输出两个符号的联合概率分布完全相等。

image-20230308105220642

性质：

  • 对于离散平稳信源,当$H_1(X)<\infty$ 时,具有以下四点性质:

(1) 条件熵 $H(X_N \mid X_1 X_2 \ldots X_{N-1})$ 随 $N$ 的增加是非递增的;
(2) $N$ 给定时, 平均符号熵 $\geq$ 条件熵, 即$H_N(\mathbf{X}) \geq H(X_N \mid X_1 X_2 \ldots X_{N-1}) $;
(3) 平均符号熵 $H_N(\mathbf{X})$ 随 $N$ 的增加也是非递增的;
(4) $H_{\infty}=\lim {N arrow \infty} H_N(\mathbf{X})$ 存在, 并且$H{\infty}=\lim _{N arrow \infty} H_N(\mathbf{X})=\lim {N arrow \infty} H(X_N \mid X_1 X_2 \ldots X{N-1})$

2.5 m阶马尔可夫信源及其熵

2.5.1 基本定义

定义：马尔可夫信源就是一类有限记忆长度的非平稳离散信源,信源发出的消息是非平稳的随机序列,它们的各维概率分布可能会随时间的推移而改变。

特点：马尔可夫信源的输出,不仅和之前输出的若干个符号有关**(有记忆),输出符号还与信源所处的状态**有关。

image-20230310083839297

满足条件：

image-20230310084437981

2.5.1m阶马尔可夫信源

image-20230310084217862

m阶有限记忆离散信源,它在任何时刻符号发生的概率只与前m个符号有关。

画状态转移图

计算熵

  • 极限概率(稳定概率)

简单说,从转移图看,计算目标来源的加权概率

image-20230310090135179
$$
\left[\begin{array}{l}Q\left(E_1\right)=0.8 Q\left(E_1\right)+0.5 Q\left(E_3\right) \ Q\left(E_2\right)=0.2 Q\left(E_1\right)+0.5 Q\left(E_3\right) \ Q\left(E_3\right)=0.5 Q\left(E_2\right)+0.2 Q\left(E_4\right) \ Q\left(E_4\right)=0.5 Q\left(E_2\right)+0.8 Q\left(E_4\right) \ Q\left(E_1\right)+Q\left(E_2\right)+Q\left(E_3\right)+Q\left(E_4\right)=1\end{array}\right.
\\
\begin{aligned}
& Q\left(E_1\right)=Q\left(E_4\right)=5 / 14 \
& Q\left(E_2\right)=Q\left(E_3\right)=1 / 7
\end{aligned}
$$

  • 从极限概率算熵

$$
公式：H_{\infty}=\sum_{i=1}^J Q\left(E_i\right) H\left(X \mid E_i\right)
$$

题解:
$$
\begin{aligned}
&H_{\infty} \
&=Q\left(E_1\right) H\left(X \mid E_1\right)+Q\left(E_2\right) H\left(X \mid E_2\right)+Q\left(E_3\right) H\left(X \mid E_3\right)+Q\left(E_4\right) H\left(X \mid E_5\right) \
&=\frac{5}{14} H(0.8,0.2)+\frac{1}{7} H(0.5,0.5)+\frac{1}{7} H(0.5,0.5)+\frac{5}{14} H(0.8,0.2) \
& =\frac{5}{7} \times 0.722+\frac{2}{7} \times 1=0.801(\text { 比特/符号 })\end{aligned}
$$

2.6 离散信源的剩余度

2.6.1 定义

  • 熵的相对率：一个信源实际的信息熵与具有同样符号集的最大熵的比值称为相对率:$\eta=\frac{H_{\infty}}{H_0}$
  • 信源的剩余度：衡量信源的相关性程度$\gamma=1-\eta=1-\frac{H_{\infty}}{H_0}$

2.6.2 物理意义

  • 信源剩余度的大小能很好地反映离散信源输出的符号序列中符号之间依赖关系的强弱。
  • 剩余度$\gamma$越大,实际熵$H_{\infty}$越小。表明信源符号之间的依赖关系越强,即符号之间的记忆长度越长。
  • 剩余度$\gamma$越小,实际熵$H_{\infty}$越大。表明信源符号之间的依赖关系越弱,即符号之间的记忆长度越短。
  • $\gamma = 0$时,信源的实际熵等于最大熵Ho:表明信源符号之间不但统计独立无记忆,而且各符号还是等概率分布。

第三章

3.1 信道的数学模型及分类

3.1.1 研究的模型

1 离散信道

image-20230313091445437

其中$\sum^s_{j=1}p(b_j|a_i) = 1$说明输入一个a1,都有输出,而且输出的信号也满足完备集

2 单符号离散无记忆信道

数学模型

image-20230313091838003

也可以写作$[X,p(Y|X),Y]$

3.1.2 信道描述方法

  • 1.图示法
    image-20230313092016810

  • 2.信道矩阵法
    image-20230313092207327

3.3.3 几种常见的离散信道

  • 1、理想信道(无噪无损信道/无噪一一对应信道)

    • 离散无噪无损信道的输入和输出符号之间有确定的一一对应关系,且信道矩阵为单位矩阵(信道的条件概率/传递概率/转移概率为1)。image-20230313092603575 image-20230313092630847

  • 2.二进制对称信道(BSC)

    image-20230313092933515 p表示传输中发生错误的概率

  • 3.二进制删除信道(BEC)

    image-20230313092952558

3.2离散信道相关的五种概率

image-20230313093503902
  • 先验概率 $p(a_i)$ ：在接收到一个输出符号以前, 输入符号 $a_i$ 的概率。
  • 后验概率 $p(a_i \mid b_j)$ ：在接收到一个输出符号以后,输入符号的概率; 已知信道输出端接收到符号为 $b_j$ 但发送端的输入符号为 $a_i$ 的概率, 也称为后向概率。
  • 前向概率 $p(b_j \mid a_i)$ : 发送为 $a_i$, 通过信道传输接收到为 $b_j$ 的概率, 也是信道传递概率。
  • 联合概率 $p(a_i b_j)$ : 发送为 $a_i$, 且接收为 $b_j$ 的概率。
  • $p(b_j)$ : 信道输出端接收到符号 $b_j$ 的概率。
  • 贝叶斯公式: $p(a_i \mid b_j)=\frac{p(a_i b_j)}{p(b_j)}$

一般来说知道先验概率和后验概率求其他

3.3 交互信息量、信道疑义度

3.3.1 交互信息量

$$
\begin{aligned}
& I(a_i ; b_j)=I(a_i)-I(a_i \mid b_j) 定义式\
& =\log \frac{1}{p(a_i)}-\log \frac{1}{p(a_i \mid b_j)} \
& =\log \frac{p(a_i \mid b_j)}{p(a_i)}=\log \frac{p(a_i b_j)}{p(a_i) p(b_j)}=\log \frac{p(b_j \mid a_i)}{p(b_j)} \text { bit }计算式
\end{aligned}
$$

交互信息量可正可负数

3.3.2 计算步骤

3.4 平均互信息及其性质

3.4.1 定义:交互信息量的统计平均值。

$$
I(X;Y)=\sum^r_{i=1}\sum^s_{j=1}p(a_ib_j)I(a_i;b_j)
$$

物理意义：信道中每传输一个符号所获得的平均信息量。

3.4.2 计算式:

把公式中的$I(a_i;b_j)$用上一节的计算式展开:
$$
\begin{aligned}
I(X ; Y) & =\sum_{i=1}^r \sum_{j=1}^s p\left(a_i b_j\right) I\left(a_i ; b_j\right) \
& =\sum_{i=1}^r \sum_{j=1}^s p\left(a_i b_j\right) \log \frac{p\left(a_i \mid b_j\right)}{p\left(a_i\right)} \
& =\sum_{i=1}^r \sum_{j=1}^s p\left(a_i b_j\right) \log \frac{p\left(a_i b_j\right)}{p\left(a_i\right) p\left(b_j\right)} \
& =\sum_{i=1}^r \sum_{j=1}^s p\left(a_i b_j\right) \log \frac{p\left(b_j \mid a_i\right)}{p\left(b_j\right)} \quad \text { bit / 符号 }
\end{aligned}
$$

3.4.3 平均互信息与各类熵的三种关系表达式

$$
\begin{aligned}
&I(X ; Y)=H(X)-H(X \mid Y)\
&I(X ; Y)=H(X)+H(Y)-H(X Y)\
&I(X ; Y)=H(Y)-H(Y \mid X)
\end{aligned}
$$

3.4.4 各类熵的物理意义

  • $I(X ; Y)=H(X)-H(X \mid Y)$中是先验熵 - 后验熵

    • $H(X \mid Y)$—–后验熵 也可以可以叫做:
      • 信道疑义度
      • 损失熵
    • 推论:
      • 如果是无噪——对应信道：$H(X \mid Y)=0$
      • $H(X)\leqslant H(X \mid Y)\to I(X;Y)\geqslant0$
      • $H(X \mid Y)=H(X)-I(X ; Y)$

  • $I(X ; Y)=H(Y)-H(Y \mid X)$

    • $H(Y \mid X)$ — 噪声熵\散布度

  • 一般情况下信源的信息熵并不等于所获得的信息量。

    • 只在无噪情况下才等于
    • 一般情况下信息量是两熵之差

两种极端情况的信道的平均互信息

1、理想信道(无噪无损信道/无噪——对应信道)

平均互信息达到最大,信源的信息量可以全部传递过来。

2、噪声极大信道(全损信道)

相当于输入和输出的独立的:$p(x|y)=p(x)$

没有任何信息量:$I(X;Y)=0$

image-20230315112621385
$$
\begin{aligned}
& I(X ; Y)=H(X)-H(X \mid Y)=0 \
& I(X ; Y)=H(Y)-H(Y \mid X)=0 \
& H(X \mid Y)=H(X)相当于损失信息等于输入信息 \
& H(Y \mid X)=H(Y) \
& I(X ; Y)=0 \quad
\end{aligned}
$$

3.4.2 性质

1.非负性

$$
I(X;Y)\geqslant 0
$$

  • 说明:
    • 观察一个离散信道的输出,从平均的角度来看,总能消除一些不确定性,接收到一定的信息。
    • 除非信道输入和输出是统计独立时,才接收不到任何信息。

2.极值性

$$
I(X;Y)\leqslant min[H(X),H(Y)]
$$

  • 说明
    • 收到Y,提取关于X的信息量,最多只有X的信息熵那么多,不会超过X自身所含有的信息量。

3.交互性(对称性)

$$
p(xy)=p(yx) \to I(X;Y)=I(Y;X)
$$

  • 说明
    • 输出过去的信息量反过来也一样
    • 当X和Y—一对应时,从一个随机变量可以充分获得关于另一个随机变量的信息,$I(X;Y)=I(Y;X)=H(X)=H(Y)$
    • 当X和Y统计独立时,不可能从一个随机变量获得关于另一个随机变量的信息,$I(X;Y)=I(Y;X)=0$

4.凸函数性

image-20230315114127991image-20230315114139256

平均互信息 $I(X;Y)$只是输入信源X的概率分布 $p(x)$和信道传递概率$p(y|x)$的函数。

形成马鞍形图形

image-20230315114308132

  • 定理1:若信道固定,就是说p(y|x)固定,I(X;Y)是输入信源概率分布p(x)的上凸型函数。

    对二元对称信道,当输入等概分布时,I(X;Y)达到最大值。

    二元对称信道

    image-20230313092933515

  • 定理2：若信源固定,就是说p(x)固定,I(X;Y)是信道传递概率 p(ylx)的下凸型函数。
    对二元信源固定后,存在一种二元对称信道p(y|x)=0.5(就是全损信道)
    使在信道输出端获得的信息量最小,等于0。

3.5离散扩展信道的平均互信息

3.5.1 对于一般离散信道$[X,p(y|x),Y]$

  • 若信道是无记忆的, 即信道传递概率满足$ p(\mathbf{y} \mid \mathbf{x})=\prod_{i=1}^{N} p(y_{j} \mid x_{i}) $
    则有 $ I(\mathbf{X} ; \mathbf{Y}) \leq \sum_{i=1}^{N} I(X_{i} ; Y_{i}) $
    就是说信源可能有记忆,重的自信息小于各个自信息之和
  • 若信道的输入信源是无记忆的, 即满足 $p(\mathbf{x})=\prod_{i=1}^{N} p(x_{i}) $
    则有 $ I(\mathbf{X} ; \mathbf{Y}) \geq \sum_{i=1}^{N} I(X_{i} ; Y_{i}) $
    就是说重的自信息大于各个自信息之和,因为可能信道有记忆,导致输出不仅仅和当前的输入有关系,还和之前的输入有关系
  • 若信道和信源都是无记忆时, 上述两个条件都满足
    则有 $ I(\mathbf{X} ; \mathbf{Y})=\sum_{i=1}^{N} I(X_{i} ; Y_{i}) $

3.6 两个特殊信道

3.6.1.独立并联信道的平均互信息

image-20230320180144778

每一个信道的输出Yi只与本信道的输入Xi有关，与其他信道的输入和输出都无关。即信道是无记忆的。
$$
I(\mathbf{X} ; \mathbf{Y}) \leq \sum_{i=1}^{N} I\left(X_{i} ; Y_{i}\right)
$$

3.6.2. 串联信道平均互信息

image-20230320180429637

满足:
$$
I(X;Z)\le I(X;Y)\
I(X;Z)\le I(Y;Z)
$$
满足定理:信息不增性原理

3.7 信道容量

3.7.1 信道容量

1 定义

对于一个固定的信道，总存在一种信源$(p(x))$，使信道中每传输一个符号所携带的信息量达到最大，这个最大的信息量称为该信道的

  • “信道容量”—C。

$$
C=\max_{p(x)}{I(X;Y)}\qquad bit/符号
$$

  • 相对应的信源概率分布p(x)为”最佳输入分布“

2 性质

  • 表征的是信道的最大信息传输能力

  • 只与信道传递概率p(y|x)有关,与信源无关

3.7.2 简单信道容量计算

1 无噪无损信道(理想信道)

image-20230320182437101

$H(X|Y = 0) \to I(X;Y)=H(X)=H(Y)$
$$
C=\max _{p(x)}{I(X ; Y)}=\max _{p(x)}{H(X)}=\max _{p(x)}{H(Y)}=\log r \text { bit / 符号 }
$$

2 有噪无损信道

image-20230320182802828 $$ C=\max _{p(x)}\{I(X ; Y)\}=\max _{p(x)}\{H(X)\}=\log r \text { bit / 符号 } $$ 2 无噪有损信道 image-20230320182859559 $$ C=\max _{p(x)}\{I(X ; Y)\}=\max _{p(x)}\{H(Y)\}=\log r \text { bit / 符号 } $$

3.7.3 对称信道容量计算

1对称信道定义

  • 对称离散信道
    • 每一行是{p1，p2，… ps}的不同排列
    • 每一列是{q1，q2，…qs}的不同排列
    • image-20230320192101836

2 容量计算

当$p(x) = \frac{1}{r}$时,$p(y_1)=p(y_2)=…p(y_s)$也等概,$H(Y) = logs$最大
$$
C=\max _{p(x)}{I(X ; Y)}=\log s-H\left(p_1^{\prime}, p_2^{\prime}, \ldots, p_s^{\prime}\right) \quad \text { bit / symbol }
$$
image-20230320192724393

3 强对称信道(r=s)

image-20230320192824321

$$
\begin{aligned}
C & =\log r-H\left(\bar{p}, \frac{p}{r-1}, \frac{p}{r-1}, \ldots, \frac{p}{r-1}\right) \
& =\log r+\bar{p} \log \bar{p}+\frac{p}{r-1} \log \frac{p}{r-1}+\frac{p}{r-1} \log \frac{p}{r-1}+\ldots+\frac{p}{r-1} \log \frac{p}{r-1} \
& \Rightarrow C=\log r-p \log (r-1)-H(p) \quad \text { bit } / \text { symbol }
\end{aligned}
$$
其中对于二进制对称信道
$$
C = 1-H(p)
$$

4 N次扩展离散无记忆信道的信道容量

$$
C^N=NC
$$

3.8 信道剩余度

1.信道容量C：信道平均每个符号所能传送的最大信息量。

$$
C=\max _{p(x)} I(X ; Y) \mathrm{bit} / \text { symbol }
$$

2.信道的最大信息传输速率：信道在单位时间内能传输的最大信息量。
$$
C_{t}=\frac{1}{t} \max _{p(x)} I(X ; Y) \mathrm{bit} / \text { second }
$$
3.信道的信息传输率 $R$ ： 信道中平均每个符号所能传送的信息量。
$$
R=I(X ; Y)=H(X)-H(X \mid Y) \text { bit } / \text { symbol }
$$
平均互信息 $I(X ; Y)$ : 接收到符号Y后平均每个符号获得的关于X的信息量。

4.信道的信息传输速率：信道在单位时间内平均传输的信息量。
$$
R_{t}=\frac{1}{t} I(X ; Y) \mathrm{bit} / \text { second }
$$

3.8.1 信道剩余度定义

信道剩余度 $\quad \gamma=C-I(X ; Y)=C-R$

信道相对剩余度 $\quad \gamma=1-\frac{I(X ; Y)}{C}$

对于无损信道: $C=\log r$

无损信道的剩余度 $\quad \gamma=\log r-I(X ; Y)=\log r-H(X)$

无损信道的相对剩余度 $\quad \gamma=1-\frac{H(X)}{\operatorname{logr}}$

信源的剩余度： $\gamma=1-\frac{H_{\infty}}{H_{0}}$

对于无损信道, 可通过信源编码, 减小信源的剩余度, 提高信道的信息传输率, 使之达到C。

第五、八章

4.1 编码器

4.1.1 定义

  • 信源符号集S: {s1 ,s2 ,…sq}
  • 码符号集X: {x1 ,x2 ,…,xr}
  • 码字集合C : {W1 ,W2 ,…Wq}

image-20230329103100676

image-20230329103256764

总结：无失真信源编码器的作用就是将信源符号——对应地变换成码字，而码字是由适合信道传输的码符号序列组成。

4.1.2 二元码

定义:若码符号集为{0,1}，所得码字都是一些二元序列，称为二元码。

4.2 等长码,变长码

  • 等长码:码字集合中所有码字的长度都相等。
  • 变长码:码字集合中码字长度长短不一（一定有不相同的码长）。
image-20230329103738605

4.3 如何确定等长码的码长

4.3.1 X:{0,1}时

$$
2^{l_i}\geqslant q\
l_i\geqslant log_2q
$$

4.3.2 二次扩展时

$$
2^{l_i}\geqslant q^N\
l_i\geqslant N*log_2q\
N为扩展位数
$$

image-20230329104653812

4.4 如何设计变长码中的即时码

4.4.1 补充定义

1 奇异码

就是看有没有一样的

  • 若码字集合中的所有码字都互不相同，则称此分组码为非奇异码。
  • 若码字集合中有相同的码字，则称此分组码为奇异码。

2 唯一可译码

定义 任意一串有限长的码符号序列，只能被唯一翻译成对应的信源符号序列，则称之为唯一可译码。

首先就要满足非奇异码

要找唯一可译码就要扩展

image-20230329110129015image-20230329110138316

但是这里a2和s3有重复所以不是唯一可译码

image-20230329111308242

这里C2,C3是唯一可译码

4.4.2 即时码

定义 无需考虑后续的码符号即可以从码符号序列中译出码字，这样的唯一可译码称为即时码。也叫非延长码,逗点码

image-20230329111431619

就是说有收尾的

即时码是唯一可译码

  • 非延长的意思就是编码过程中,每一个码不是上一个码的延长
    a w1 0
    b w2 10\11
    c w3 110\111
    d w4 111\1111

4.4.3 两个定理

image-20230329112509382

可能出选择题

4.5 平均码长的概念以及如何计算平均码长

4.5.1 平均码长

公式：
$$
\bar{L}=\sum_{i=1}^q p\left(s_i\right) l_i\
单位:码符号/信源符号
$$
物理意义：平均每个信源符号需要用的码符号数。

  • 等长码：$\bar{L} = l$
  • 变长码:image-20230329114523556

4.5.2 码率

码率: $R=H(X)=\frac{H(S)}{\bar{L}}$

单位:比特/码符号

要使H(X)最大,就是X等概,$H(X)=logr$所以 $R \leq \log r$

另外$R_{t}=\frac{H(S)}{t \bar{L}} \quad \text { 比特 } / \text { 秒 }$

4.5.3编码效率

编码效率: $\quad \eta=\frac{\frac{H(S)}{\log r}}{\bar{L}} \leq 1$

4.5.4 两个定理

  • 定理 1 :

    • 若一个离散无记忆信源 $S$ 具有嫡为 $H(S)$, 并有 $r$ 个码元的码符号集
      $$
      X={x_{1}, x_{2}, \cdots, x_{r}}
      $$
      • 则总可找到一种无失真编码方法,构成唯一可译码,使其平均码长满足
        $$
        \frac{H(S)}{\log r} \leqslant \bar{L}<1+\frac{H(S)}{\log r}
        $$
      • 定理告诉我们码字的平均长度 $\bar{L}$ 不能小于极限值 $\frac{H(S)}{\log r}$, 否则唯一可译码不存在。

  • 定理2:

    • (无失真变长信源编码定理,即香农第一定理) 离散无记忆信源 $S$ 的 $N$ 次扩展信源 $S^{N}={\alpha_{1}, \alpha_{2}, \cdots, \alpha_{q}^{N}}$, 其樀为 $H(S^{N})$, 并有码符号 $X={x_{1}, \cdots, x_{r}}$ 。对信源 $S^{N}$ 进行编码, 总可以找 到一种编码方法,构成唯一可译码,使信源 $S$ 中每个信源符号所需的平均码长满足
      $$
      \frac{H(S)}{\log r}+\frac{1}{N}>\frac{\bar{L}{N}}{N} \geqslant \frac{H(S)}{\log r}
      $$
      或者
      $$
      H      {r}(S)+\frac{1}{N}>\frac{\bar{L}{N}}{N} \geqslant H{r}(S)
      $$
      当 $N arrow \infty$ 时,则得

$$
\lim {N \rightarrow \infty} \frac{\bar{L}{N}}{N}=H_{r}(S)
$$

编码效率: $\eta=\frac{\frac{H(S)}{\log r}}{\bar{L}} \leq 1 \quad \mathbf{r}=\mathbf{2}$ 时, $\eta=\frac{H(S)}{\bar{L}}=H(X)=R$

4.5.5编码剩余度:

$$
\quad \gamma=1-\eta=1-\frac{\frac{H(s)}{\log r}}{\bar{L}}=1-\frac{H_{r}(s)}{\bar{L}}
$$

物理意义:衡量各种编码与最佳码的差距。

4.6 几种重要的信源编码方法

4.6.1 香农编码

1、排序: 将信源的 $q$ 个消息符号按概率递减排序。
$$
p_{1} \geq p_{2} \geq \ldots \geq p_{q}
$$

2、算码长：计算第 个个消息的二进制码字的码长,并往上取整。
$$
l_{i}=\left[\log \frac{1}{p\left(x_{i}\right)}\right]
$$

3、计算累加概率：为了编成唯一可译码，首先计算第讱消息的 累加概率函数。
$$
P_{i}=\sum_{k=1}^{i-1} p\left(x_{k}\right)
$$

4、概率转二进制：将累加概率函数 $P_{i}$ (为小数) 转成二进制数。

5、读取码字: 去除小数点，并根据码长 $li$, 取小数点后/位作为 第i个消息的码字。