• rationales：基本原理
• discourse：语篇
• anticlimax: 虎头蛇尾
• prevail: 流行
• hedging: 模糊的
• bjectivity: 客观的

1 Overview

1-1 Register

register 语域：写作、演讲风格，代表了语言正式的程度

5 Registers

• Static (frozen) 套话
• Formal (regulated)
• Consultative (professional/ academic) 商议的
• Casual (group)
• Personal (intimate)

1-2 Title

S.C.I:

1. specific
2. concise
3. informative

HOW:

1. Choose a topic: interesting
2. Narrow down: specific
3. Paraphrase: noun phrase

1-3 Nominalization 名词化

Why

1. increase information density and facilitate efficiency and accuracy of communication.
2. express abstract concepts (e.g., revolution, possibility) 描述抽象概念
3. hide the agent behind an action
4. improve flow of writing , maintain connections between ideas
5. make writing more “written” and professional

How:

1. a simple sentence
2. nominalized subject
3. second verb
4. finisher idea

1-4 Personal Pronouns

并非完全不能用第一人称

Avoid first and second person pronouns to be impersonal and scientific

Use gender-fair language

• Use "he or she" or "a person" instead of "he"

1-5 Word Choice and Sentence Variety

1-5-1 Word choice

Abstract and concrete words

• Abstract: loyal, love
• Concrete: battle, horse

Generral and specific words

• general: tree
• specific: southern red oak

Denotation and connotation

指示词（客观）和内涵词（带感情色彩的词）

Figurative speech

生动性

employs figures of speech

1. simile，明喻
2. metaphor，隐喻
3. personification，拟人

Choose appropriate vocabulary

1. Avoid using unfamiliar synonyms 避免使用生僻的同义词，不要装逼
2. Avoid slang 避免俚语
3. Avoid wordiness 避免冗长

1-5-2 Sentence variety

四种基础句式：

1. 简单句
2. 并列句
3. 复合句
4. 并列复合句

2 Literature Review

1. Information prominent citation：作者待在括号里
2. Author prominent citation：作者是主语
3. Weak author prominent citation：authors 是主语，一群作者待在括号里

2-1 Reviewing Literature

A literature review is a careful examination of a body of literature pointing toward the answer to your research question.

Include a critical analysis of various opinions from credible sources

2-2 Writing Literature Review

简单文献综述模型：

• 研究兴趣
• 研究话题
• 文献综述
• 研究论文

复杂文献综述模型：在简单模型的基础上增加

• 研究问题
• 研究项目

顺序：

• Chronological（时间） － Trace the development of the topic over time
• Thematic（主题） － Address different aspects of the topic in subsections
• Methodological（方法） － Compare the results & conclusions from different approaches
• Theoretical（理论） － Discuss various theories, models, and definitions of key concepts.

技巧：

1. introduction to topic
2. support from the literature
3. mini summary
4. introduction to next topic.

2-3 Avoiding Plagiarism（剽窃）

方法：

1. Quoting（引用）
2. Paraphrasing（转写）
3. Summarizing（概括）

2-4 Reporting Verbs

2-5 Tenses in Literature review

常用一般现在时、现在完成时

一般现在时：陈述事实或者真理的东西

只有在以下情况可以用一般过去时：

1. 主句出现年份、时间（不是括号）
2. 提到废弃研究

3 Methods and Results

“限制条件”预防了数据失效

3-1 The Structure of the Method Section

==Different titles of the method section==

• Materials and Methods
• Theory and Methods
• Theoretical Framework and Methods

The major elements in the method section

• The method section
  • Methodology
  • The rationales
  • The fundamental reasons or principles of doing things
• Steps
• Materials

避免抄袭：

• 感谢作者
• 熟悉实验设计和实施
• 好好引用

3-2 The Structure of the Results Section

Major elements

• The statement showing where the results can be found
• The statement presenting the most important findings
• The statement commenting on the results

The order of the results

• Research questions
• Research methods

The language focuses

• Sequential markers
• Graphic descriptions
• Comparison and contrast

3-3 Sequential Markers

Importance of sequential markers

• Building up connections between ideas
• Ensuring that sentences and paragraphs flow together smoothly

3-4 Graphic Description

Description of Graphs

1. Introduce the graphic information briefly and indicate the main trend. Normally it includes the place, time, content and purpose of the graph;
2. Describe the relevant and most important or signi ficant data and make some comparison if necessary;
3. Summarize the data/trends

Expressions for highlighting significant data in a table/chart

• some adjectives such as “apparent”, “clear”, “interesting”, “obvious”, “revealing” and “significant”

3-5 Comparison and Contrast

• 比较：相同点
• 对比：不同点

Two major ways of organization:

1. Block comparison or block contrast（分块对比）
   1. To examine one thing thoroughly and then examine the other
2. Alternating comparison or alternating contrast（交替对比）
   1. To examine two things at the same time, discussing them point by point

Tips for making comparison or contrast

• Not all the information has to be compared or contrasted with each other.
• It is not necessary to lay equal emphasis on every change.
• The comparison/contrast should be supported by concrete and relevant facts or data.

4 Discussion & Conclusion

4-1 Structure of Discussion Section

7 elements the Discussion section typically contains:

1. An overview ...
2. A consideration ...
3. Implications ...
4. A careful examination ...
5. Limitations ...
6. Recommendations ...
7. Implications ...

4-1-2 Strategies and steps to structure the Discussion

How to begin the Discussion

1. Remind readers
2. Refer back to the questions
3. ==Refer back to papers==
4. Briefly restate ... from your Results

How to compare my work with those of others

4-2 Structure of Conclusion Section

Key elements of Conclusions section:

1. a very brief revisit of the most important findings ...
2. a final judgment on the importance and significance of those findings ...
3. an indication of the limitations ...
4. suggestions for ...
5. recommendations for ...

Typical issues in structuring the Conclusion

1. Redundancy: repetition of
2. Raising a Totally New Point: introducing less ...
3. Overstatement （夸大）: making immoderate...
4. Anticlimax（虎头蛇尾）：failure to ...

Discussion sections which also have a Conclusion may end:

• Tell your readers ... But you must ... If you repeated
• Suggest ways that
• Say if and / or why you ignored
• Admit ...
• Reiterate your reasons for ...

4-3 Language Focus 1: Cause and Effect

• Identifying causes and effects
• Drafting thesis statements for causes or effects
• Tips on planning causes and effects
  1. Distinguish direct and indirect causes and effects.
  2. Group different causes and effects
  3. Avoid mistaking coincidence (two unrelated things happening together) for cause or effect
  4. Avoid oversimplification
     1. 因为许多问题非常复杂

4-4 Language Focus 2: Paraphrasing

Why

• Plagiarism detection system
• A case of unintentional plagiarism

How

• Lexical（词汇）
  • 同义词
  • 改词性
• Syntactic（句法）
  • 双重否定
  • 主语换位
  • 主被转换
  • 语序转换
• Combined

4-5 Language Focus 3: Strong Restatement of the Research Objective

• Two features of a strong thesis statement
  • It makes a claim that requires ...
  • It makes a claim that offers ...
• Five kinds of weak thesis statements
  • Statements that make no claim
  • Statements that are obviously true or a statement of fact
  • Statements that restate conventional wisdom
  • Statements that offer personal conviction as the basis for the claim
  • Statements that make an overly broad claim

5 Publication

5-1 Abstract

Essential elements：

• the background
• the problem
• the methods
• the results
• the implications

• 背景/目标：一般现在时
• 过程/方法：一般过去时
• 结果

The Types of abstracts

1. Informative abstract
2. Structured abstract
   1. 分段，每段开头为粗体的 Aim, Methods, Results, Research limitations/implications 或 Conclusion

5-2 Keywords

Definition of keywords:

• standout within the Abstract
• important words in the abstract
• emphasize the key information for readers

Purpose of keywords:

• increase the probability that a paper will be read and retrieved
• potentially improve citation counts and journal impacts
• know what words reflect the key information of the paper
• read more carefully when meeting these words in the paper

Categories:

• Discipline
• Topic
• Location
• Methods
• Data source

Number of keywords

• can’t be too few or many
• 3~5 in journals
• trade-off between the keywords to meet the limitation requirements for keywords
• choose the keywords from recent or often-cited titles close to their contribution

5-3 Reference

• IEEE: [编号]. 作者名缩写. 作者姓, “文章题目,” 斜体期刊名称, 城市, 洲, 国家, 月日, 年, 页码
• MLA: 作者姓, 作者名. “文章题目.” 斜体期刊名称, vol. 期刊号, no. 发行号, 发行年份, pp. 页码

Functions

• used to avoid plagiarism
• tell editors and readers what sources have been cited in the paper
• help readers to use the materials to refer to when they write papers

Standard of a good reference:

1. Authoritative
2. Up-to-date
3. Journal-targeted

5-4 Acknowledgement

Two main types of acknowledgements

• One is in a paper, and expresses the thanks to the organizations or projects or funds.
• The other is in a dissertation（大论文） as mentioned in the first part.

5 Submitting: writing the journal submission cover letter

Why a convincing cover letter?

• Highlighting the merit and significance
• Interesting the editor

What is included in the cover letter ?

• Follow the author guide.
• include essential information
• claim the originality of the paper

What should be avoided in the cover letter?

• Don't use too much jargon and acronyms.
• Don’t exaggerate.
• Don't make it lengthy.
• Don't try to be entertaining.

20 分钟做完客观题

• empty introductory phrases：空的介绍性短语，客观

• hedging language：模糊语，客观，避免过于绝对

• trivial：琐碎的

• current study

• this study set out to tackle ...

• The project undertaken

• aimed to

• show our gratitude

• manuscript：稿子

• Please find the attached manuscript

• subject to：受...影响，屈服于

• bring about：引起

• syntax：句法

• plunge：骤降

• prevalent：普遍的

• By contrast

• proportion：比例

• expenditure：开支

• bead：珠子

• reaffirm：重申

• diffuse

• quantitative/qualitative analysis

• graduate student：研究生

Basic Research or otherwise called as pure or fundamental research, is one that focuses on advancing scientific knowledge for the complete understanding of a topic or certain natural phenomenon

基础研究是扩展科学知识

注意事项

改写句子不一定就是被动句，也可以加名词让句子复杂化

用 including 而不是 etc.

少用否定：not much（选择题里看见就排除）

句子不要太短

选项多于空的要考虑多选题

highlight adj.：不是结论本身的性质的形容词，只是强调、突出

有疑问的选项就尝试带进去理解，说不定是整个句子理解错了

conclusion 不能引用了

作文素材

形容词

• considerable：可观的
• numerous
• uncertain
• principal：主要的

动词

• obtain
• fluctuate：起伏
• encounter
• concur with：与...一致认为
• perform
• accord with：与... 一致

名词

• consequence

• administer/complete questionnaire

易错

名词化

• increase
• eliminate
• specificity
• specialization
• speciality
• sufficiency
• inequality

课程内容和要求

• 教材：《信息论与编码》，参考书：《信息论——基础理论与应用》
• 开卷考试，卷面占总成绩 60%，可以带计算器

简答题就简答，不要太多

信息度量和三大定理

主要计算题：信源编码和信道编码

$I(X;Y)$ 的最大值就是信道容量 $C$

平均功率 $\mathrm{E}\left\{y^2\right\}=\mathrm{E}\left\{(x+n{)}^2\right\}=\mathrm{E}\left\{x^2\right\}+\mathrm{E}\left\{n^2\right\}=S+{\sigma }^2=S+N$

平均交流功率就是方差，就是自相关函数的峰值

熵和信道容量要写单位

导数和积分表

• 给定方差情况下，高斯信源的信息率失真函数最大，即最难压缩；
• 给定方差情况下，噪声服从高斯分布时的信道容量最小

设函数求导比大小

• $a_n=n{p}^n$
• ${\sum }_{i=1}^n{a}_n=\frac{p-p^{n+1}}{(1-p{)}^2}-\frac{n{p}^{n+1}}{1-p}$

高斯：$f(x)=\frac{1}{\sigma \sqrt{2\pi }}{e}^{-\frac{{\left(x-\mu \right)}^2}{2{\sigma }^2}}$

切比雪夫不等式：$P(|X-E(X)|\ge b)\le \frac{Var(X)}{b^2}$

第二章

Jensen 不等式（凹函数定义）：${\sum }_{i=1}^N{p}_i\mathrm{lb}(x_i)\le \mathrm{lb}\left({\sum }_{i=1}^N{p}_i{x}_i\right)$

消息中平均每个符号携带的信息量有别于离散平均无记忆信源平均每个符号携带的信息量，后者是信息熵

若信源熵居然大于等概分布的信源熵，则一定是 信源空间不满足概率空间的完备集，譬如概率之和不为1

• $I(x_i)=-\mathrm{lb}P(x_i)$ bit
• $H(X)=-{\sum }_{i=1}^{N}P(x_i)\mathrm{lb}P(x_i)$ bit/符号
• $H(XY)=H(X)+H(Y|X)$
• $H(X|Y)=-{\sum }_{x\in X,y\in Y}P(xy)\mathrm{lb}P(x|y)$
• K 重扩展信源的熵：$H(X^K)$
• 平均符号熵：$H_K(X_1{X}_2\dots X_K)=\frac{1}{K}H(X_1{X}_2\dots X_K)$
• 互信息量：$I(x_i;y_j)=I(x_i)-I(x_i|y_i)=\mathrm{lb}\frac{P(x_i|y_j)}{P(x_i)}=\mathrm{lb}\frac{P(x_i{y}_j)}{P(x_i)P(y_j)}=\mathrm{lb}\frac{P(y_j|x_i)}{P(y_j)}=I(y_j;x_i)$，没有负号！
• 平均互信息量 ：$I(X;Y)={\sum }_{XY}P(xy)\mathrm{lb}\frac{P(x|y)}{P(x)}$
• $I(X;Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)$

第三章

联合熵与条件熵的关系：$H(X_1{X}_2{X}_3)=H(X_3|X_1{X}_2)+H(X_1{X}_2)$

• 信源的冗余度：$R=\frac{H_{max}-H}{H_{max}}\times 100\%$

第四章

平均码长是加权的，且 K 重扩展的平均码长单位为 码元/K个符号，往往要再除以 K

${\sum }_i\frac{i}{2^i}=2$：乘公比错位相减

单义可译码：

1. 等长码，且各消息对应码字不同
2. 变长码，且不能用不同的多个码字拼出相同的一串序列，譬如$a_1{a}_2=a_3{a}_4{a}_5$
3. 也可以直接算单义可译码和即时码的必要条件： ${\sum }_{i=1}^N{D}^{-b_i}\le 1$ ，$b_i$ 为各码长，D 为符号种数
   • 满足 Kraft 不等式只是表明这种码长分布可以构造单义可译码和即时码
   • 即时码仅是单义可译码的一种排布，没有更严格的要求

最佳编码：具有最短的代码组平均长度或编码效率接近于 1 的信源编码

• 二元霍夫曼编码

${\bar{L}}_N$：N 个信源符号的平均编码符号长度

• 编码效率：$\eta =\frac{H(X^K)/\bar{B}}{\mathrm{lb}D}\times 100\%$

先试扩展倍数小的，不够再加

第五章

信道矩阵：（给出信道特性） $$\Pi ={\left[\begin{array}{cccc}P\left(y_1\mid x_1\right)& P\left(y_2\mid x_1\right)& \cdots & P\left(y_L\mid x_1\right)\\ P\left(y_1\mid x_2\right)& P\left(y_2\mid x_2\right)& \cdots & P\left(y_L\mid x_2\right)\\ & \ddots & & \\ P\left(y_1\mid x_M\right)& P\left(y_2\mid x_M\right)& \cdots & P\left(y_L\mid x_M\right)\end{array}\right]}_{M\times L}$$

对称离散信道： 信道矩阵的所有行由相同元素组成，所有列也由相同元素组成

二进制对称信道容量：$C_{BSC}=1+\epsilon \mathrm{lb}\epsilon +(1-\epsilon )\mathrm{lb}(1-\epsilon )$ bit/符号

离散准对称信道：

• 定义：信道矩阵可以按列分解为若干互不相交的子集，每个子集构成的矩阵都对应对称信道
• 设信源符号个数和信宿符号个数分别为 r 和 s， 当信源符号消息等概分布时，达到信道容量 C，且 $C=\mathrm{lb}r+{\sum }_{j=1}^s{p}_j\mathrm{lb}{p}_j-{\sum }_{k=1}^n{N}_k\mathrm{lb}{M}_k$ 比特/符号， 其中 $\{p_1,\dots ,p_s\}$ 是信道矩阵每一行的元素，n 表示子矩阵个数， $N_k$表示第k个子矩阵行元素之和，$M_k$表示第k个子矩阵列元素之和。

译码准则：规定把 什么 y 判成 什么 x

• 先画香农线图
• 最小错误概率：对每个 $y_j$，取最大的 $P(x_i|y_j)$（其实也就是最大 $P(xy)$
  1. 列出发送码字到接收码字的转移概率矩阵 $P(xy)$
  2. 每列求和得到 $P(y)$，每列除以它
  3. 每列取最大的
• 最大似然：对每个 $y_j$，取最大的 $P(y_j|x_i)$
• 错误概率：先求正确概率 $P_C=P(x_1)P(y_{c1}|x_1)+P(x_2)P(y_{c2}|x_2)$

码率：$R=(\mathrm{lb}M)/N$ 比特/码元，M 为码字种数

第六章

• 相对熵：$h(x)=-{\int }_{-\infty }^{\infty }p(x)\mathrm{lb}p(x)\mathrm{d}x$

将随机变量 $X$ 和 $Y$ 的变换关系记作 $X=f(Y)$，则有$h(y)=h(x)-E_X\left\{\log \left|J\left(\frac{X}{Y}\right)\right|\right\}$，其中 $J\left(\frac{X}{Y}\right)=\frac{\mathrm{d}f(Y)}{\mathrm{d}Y}$（是反的导数！f是Y到X！

若 $p(xy)=p(x)p(y)$，则平均互信息量为 0

相对熵积分要复习一下

熵功率：达到指定熵所需的最小功率

6.3 需要仔细看（特别是6.3.2）

第八章

• ${\bar{D}}_{max}$：选一列取得最小失真度
• ${\bar{D}}_{min}$：取得最小失真度
• 二元离散信源的率失真函数：$R(D)=H(X)-H(\frac{D}{\alpha })$
• 等概离散信源的率失真函数：$R(D)=\mathrm{lb}r-H(\frac{D}{\alpha })-D\mathrm{lb}(r-1)$
  • $H(D)=-[D\log D+(1-D)\log (1-D)]{\sum }_{V}P(v)$，${\sum }_{V}P(v)$ 通常为 1
  • $\alpha$ 为失真矩阵中的非零元

$R(D)$ 是比特 / 信源符号，$R_t$ 是比特 / 秒

第十章

陪集首不能属于对应子群，且汉明重应最小

• 线性分组码的最小距离等于非零码字的最小重量
• 设C是 $(n,k)$线性分组码，其纠错能力为t。如果用且只用不大于t个错误的全部错误图样作陪集首就能构成标准阵，那么就称这个码为完备码。

第十一章

有可能满足循环性但不是线性码！线性：两个码字相加也是码字

第一章 信息科学及其发展

1-1 通信系统的基本概念

信源：消息的提供者

• 可分为离散和连续

信道：传递消息的通道

• 可分为同轴电缆、光纤、波导等
• 也可分为 有/无干扰信道，离散/连续信道，单用户/多用户信道 等

信宿：信息的接收者

通信系统传输的是信号，信号是消息的载体，消息中的未知成分是信息

1-2 信息科学的有关概念

信息的特征：

• 未知性（不确定性）
• 由未知到知，等效为不确定性集合元素的减少
• 可以度量

1-3 信息理论的研究内容

• 狭义信息论：信息量、信道容量、熵、香农三定理
• 广义信息论：包含主观因素

微弱信号检测（最佳接收）

1-4 香农信息论梗概

围绕 有效性和可靠性

1. 信息的度量
2. 有效性：信源编码
   1. 香农第一、第三定理
3. 可靠性：信道编码
   1. 香农第二定理
4. 网络信息理论
5. 保密信息理论

第二章 信息的度量

2-1 度量信息的基本思路

定义 2.1：若信源发出的消息是离散的、有限或无限可数的符号或数字，且一个符号代表一条完整的消息，则为单符号离散信源

定义 2.2： 若信源的输出是随机事件 X，其出现概率为 $P(X)$，则它们所构成的集合称为 信源的概率空间 或 信源空间

信源空间的描述： $$[\mathbf{X}\cdot P]:\{\begin{array}{ccccc}\mathbf{X}:& x_1,& x_2,& \dots ,& x_N\\ P(\mathbf{X}):& P\left(x_1\right),& P\left(x_2\right),& \dots ,& P\left(x_N\right)\end{array}$$

有 ${\sum }_{i=1}^{N}P(x_i)=1$

信源输出的事件的概率越小，信息量越大，即信息量是概率的减函数

自信息量 $I(x_i)$ 表示 $x_i$ 发生所带来的信息量

定义 2.3 自信息量$I(x_i)=\log \frac{1}{P(x_i)}=-\log P(x_i)$

信息量的单位：

• 以 2 为底：比特 bit
• 以 e 为底；奈特 nat
• 以 10 为底：哈特 Hart
• $1nat\approx 1.44bit,1Hart\approx 3.32bit$

自信息量和不确定度的关系

• 联系：
  • 两者都是事件概率的函数，数值和量纲一致
• 区别：
  • 不确定度是一个统计量，静态状态下也存在；
  • 自信息量只有该随机事件发生时才给出，是动态的概念

2-2 信源熵和条件熵

定义 2.4 信源熵： $$H(X)=\sum _{x\in X}P(x)I(x)=\sum _{i=1}^{N}P(x_i)I(x_i)=-\sum _{i=1}^{N}P(x_i)\mathrm{lb}P(x_i)=H(p_1,\dots ,p_N)$$ 其中定义 $0\mathrm{lb}0=0$

• 信源熵只与信源符号概率分布有关，是一种先验熵
• 对给定概率分布的信源，信源熵是定值，代表信源每发出一个符号给出的平均信息量，其量纲为 信息量单位 / 信源符号

性质：

1. 对称性：交换变量顺序不改变熵的值
2. 确定性：若有一个事件必然发生，则熵为 0
3. 非负性
4. 可加性：对于统计独立的信源 X 和 Y，$H(XY)=H(X)+H(Y)$
5. 强可加性对于任意两个信源 X 和 Y，$H(XY)=H(X)+H(Y|X)$（对数相乘，显然）
6. 极值性：等概分布的信源的熵最大，$H(p_1,\dots ,p_N)\le H(\frac{1}{N},\dots ,\frac{1}{N})=\mathrm{lb}N$
7. 递增性：信源中一个符号划分为 m 个符号，且这 m 个符号的概率和等于原符号概率，则新信源的熵增加，$H\left(p_1,\cdots ,p_{n-1},q_1,\cdots ,q_m\right)=H\left(p_1,\cdots ,p_{n-1},p_n\right)+p_{n}H\left(\frac{q_1}{p_n},\cdots ,\frac{q_m}{p_n}\right)$
   • 多元信源的熵可以表达为若干二元信源的熵的线性组合
8. 严格上凸特性

Jensen 不等式（凹函数定义）：${\sum }_{i=1}^N{p}_i\mathrm{lb}(x_i)\le \mathrm{lb}\left({\sum }_{i=1}^N{p}_i{x}_i\right)$

二进制熵函数 $H_b(p)=-p\mathrm{lb}p-(1-p)\mathrm{lb}(1-p)$，有 $H_b(0)=H_b(1)=0,H_b(\frac{1}{2})=1$

定义 2.5 条件自信息量：$I(x_i|y_j)=-\mathrm{lb}P(x_i|y_j)$

条件概率仅由信道特性决定，看作信道给出的信息量。信源信宿对调也可得到条件自信息量

==$H(X|Y)=-{\sum }_{x\in X,y\in Y}P(xy)\mathrm{lb}P(x|y)$==

定义 2.6 条件熵：对于联合符号集 XY，在给定 Y 的条件下，用联合概率 $P(xy)$ 对 X 集合的条件自信息量进行加权的统计平均值。

条件熵表示信道所给出的平均信息量

2-3 互信息量和平均互信息量

定义 2.7 互信息量：对两个离散随机事件集合 X 和 Y，事件 $y_j$ 的出现给出关于事件 $x_i$ 的信息量 $I(x_i;y_j)$

1. 信道没有干扰：$I(x_i;y_j)=I(x_i)$
2. 信道存在干扰：$I(x_i;y_j)=I(x_i)-I(x_i|y_i)=\mathrm{lb}\frac{P(x_i|y_j)}{P(x_i)}$ x的不确定度-收到y后对x尚存的不确定度=收到y对x所消除的不确定度 当 $P(x_i|y_j)=P(x_i)$ 即互信息量 $I(x_i;y_j)=0$ 时，没有信息的流通

性质：

1. 对称性：$I(x_i;y_j)=\mathrm{lb}\frac{P(x_i|y_j)}{P(x_i)}=\mathrm{lb}\frac{P(x_i{y}_j)}{P(x_i)P(y_j)}=\mathrm{lb}\frac{P(y_j|x_i)}{P(y_j)}=I(y_j;x_i)$
2. 值域为实数：可正可负可零，为负即后验概率小于先验概率，表示收到 y 后对信源是否发送 x 的正确概率小于 x 在信源集合中的概率
3. 不大于其中任一事件的自信息量
   • 互信息量描述信息流通特性的物理量，流通量的数值不可能大于被流通量的数值

$I(x_i;y_j)=I(x_i)-I(x_i|y_i)=I(y_j)-I(y_i|x_i)=I(x_i)+I(y_j)-I(x_i{y}_i)$

条件互信息量 $I(x_i;y_j{z}_k)=\mathrm{lb}\frac{P(x_i|y_j{z}_k)}{P(x_i)}=\mathrm{lb}\frac{P(x_i|z_k)}{P(x_i)}+\mathrm{lb}\frac{P(x_i|y_j{z}_k)}{P(x_i|z_k)}=I(x_i;z_k)+I(x_i;y_j|z_k)$，其中 $I(x_i;y_j|z_k)$ 即为条件互信息量

$I(x_i;y_j|z_k)=I(x_i|z_k)-I(x_i|y_j{z}_k)$，助记：把 $|z_k$ 看作后缀，则简化为互信息量的公式

定义 2.8 平均互信息量： $$I(X;Y)=\sum _{XY}P(xy)\mathrm{lb}\frac{P(x|y)}{P(x)}$$

1. $I(X;Y)$ 为互信息量 $I(x_i;y_j)$ 的联合概率加权的统计平均值
2. $I(x_i;y_j)$ 在条件概率空间中的统计平均为 $I(X;y_j)={\sum }_{x\in X}P(x|y_j)I(x;y_j)={\sum }_{i=1}^{N}P(x_i|y_j)I(x_i;y_j)$

性质：

1. 对称性：$I(X;Y)=I(Y;X)$
2. 与各种熵的关系：$I(X;Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)=H(X)+H(Y)-H(XY)$，$H(XY)$ 为共熵，或称联合熵
3. 非负性，当且仅当 $X,Y$ 独立时取零
4. 上界：$I(X;Y)\le min\{H(X),H(Y)\}$
5. 平均互信息量仅和信源概率分布 $P(x)$ 和信道传递概率 $P(y|x)$ 有关

• 给定信道传递概率 $P(y|x)$ 时，$I(X;Y)$ 是 $P(x)$ 的上凸函数
• 给定信源概率分布 $P(x)$ 时，$I(X;Y)$ 是 $P(y|x)$ 的下凸函数

最大平均互信息量：信道容量

平均互信息量的物理意义

$I(X;Y)=H(X)-H(X|Y)$

• 平均互信息量为 信源熵减掉一个条件熵
• 表示以信源为参考，在接收端平均每收到一个符号所获得的信息量
• 条件熵 $H(X|Y)$ 表示了干扰或噪声，又称疑义度

$I(Y;X)=H(Y)-H(Y|X)$

• 平均互信息量为 信源熵减掉一个条件熵
• 表示以信源为参考，在接收端平均每收到一个符号所获得的信息量
• 条件熵 $H(X|Y)$ 唯一确定信道噪声和干扰所需的平均互信息量，又称噪声熵、散布度

信源空间题：TODO

1. 先求各联合概率
2. 再求 $H(X)H(Y)H(XY)$
3. 最后求题目要求的

定义 2.9 若对应于 x 有两种分布 $p(x),q(x)$，则 $$D(p||q)=\sum _{X}p(x)\mathrm{lb}p(x)-\sum _{X}p(x)\mathrm{lb}q(x)=\sum _{X}p(x)\mathrm{lb}\frac{p(x)}{q(x)}$$ 称为这两种分布的相对熵，又称 熵差

定义 2.10 平均互信息量用相对熵定义： $$I(X;Y)=\sum _{XY}p(xy)\mathrm{lb}\frac{p(xy)}{p(x)p(y)}=E_{p(xy)}\left\{\mathrm{lb}\frac{p(xy)}{p(x)p(y)}\right\}=D(p(xy)\Vert p(x)p(y))$$

平均条件互信息量：条件互信息量在概率空间 $XYZ$ 的统计平均 $$I(X;Y|Z)=\sum _{x\in X,y\in Y,z\in Z}P(xyz)I(x;y|z)=\sum _{x\in X,y\in Y,z\in Z}P(xyz)\mathrm{lb}\frac{P(x|yz)}{P(x|z)}$$

有：（去掉$|Z$就超简单）

• $I(X;Y|Z)=H(X|Z)-H(X|YZ)=H(Y|Z)-H(Y|XZ)=H(X|Z)+H(Y|Z)-H(XY|Z)$
• $I(X;YZ)=I(X;Y)+I(X;Z|Y)=I(X;Z)+I(X;Y|Z)$

2-4 多维随机变量的熵

二维随机变量的共熵： $H(X_1{X}_2)=H(X_1)+H(X_2|X_1)$（对数相乘）

多维随机变量的共熵，又称熵的链接准则： $H(X_1{X}_2\dots X_n)=H(X_1)+H(X_2{X}_3|X_1)={\sum }_{i=1}^{n}H(X_i|X_{i-1}{X}_{i-2}\dots X_1)$

熵的条件似乎可以直接“忽略”

多维信源的平均互信息量，又称信息链接准则： $I(X_1{X}_2\dots X_n;Y)={\sum }_{i=1}^{n}I(X_i;Y|X_{i-1}{X}_{i-2}\dots X_1)$

定理 2.1 n 维随机变量的共熵不大于其各自熵之和，即 $H(X_1{X}_2\dots X_n)\le {\sum }_{i=1}^{n}H(X_i)$，称为熵的界

当 $X$ 同分布时，上界变为 $nH(X)$

常用：$0\le I(X;Y)=H(X)-H(X|Y)\Rightarrow H(X|Y)\le H(X)$

定理 2.2 数据处理定理 若 $X\to Y\to Z$（马氏链，有 $P(Z|X)=P(Z)$），则有数据处理不等式 $I(X;Y)\ge I(X;Z)$

当消息通过级联处理时，其输入和输出消息之间的平均互信息量，不会超过输入消息与中间消息之间的平均互信息量，也不会超过中间消息与输出消息之间平均互信息量；即 级联只会使得输入与输出间的平均互信息量变小

数据处理只是变换形态，不会创造新的信息

第三章 离散信源

3-1 离散信源的分类及其描述

根据时域：

• 单符号信源：信源每次只输出一个符号，可用随机变量描述信源输出的消息
• 符号序列信源：信源每次输出一个时域离散的符号序列，可用随机向量描述信源输出的消息
• 波形信源：信源每次输出时域连续的消息，可用随机过程描述信源输出的消息，采样后即为符号序列信源

根据时间和取值分布：

• 离散信源：在时间和取值上均离散，可用离散随机变量/随机向量/随机过程描述
• 连续信源：在时间或取值上连续，可用连续随机变量/随机向量/随机过程描述，采样后为信号、脉冲信号

根据平稳特性：

• 平稳：信源概率分布/密度不随时间改变
• 非平稳

根据记忆特性：

• 无记忆：信源在不同时刻发出的消息统计独立
• 有记忆（记忆长度有限的信源为马尔可夫信源）

信源编码：尽可能少的码元符号或尽可能低的数据速率来描述信源输出的消息

3-2 离散信源的熵

信息熵

定义 3.5 若信源发出 N 个不同符号 $x_1,x_2,\dots ,x_i,\dots ,x_N$ 分别代表 N 种不同消息，各符号概率为 $P_1,P_2,\dots ,P_i,\dots ,P_N$ 且相互统计独立，则为单符号离散无记忆信源

其信息熵为 $$H(X)=\sum _{i=1}^N{P}_{i}I(x_i)=-\sum _{i=1}^N{P}_i\mathrm{lb}{P}_i$$

定义 3.6 若信源发出的消息是由 K 个离散符号构成的符号序列，且各消息相互统计独立，则为发出符号序列消息的离散无记忆信源

K 重符号序列信源：每次发送都在 N 个符号里随机选 K 个（可重复）

定义 3.7 若单符号离散无记忆信源的信源空间为 $[X\cdot P]$，对其 K 重扩展得到符号序列 $X=X_1{X}_2\dots X_K$，则称扩展后的信源为离散无记忆信源 $[X\cdot P]$ 的 K 重扩展信源，扩展得到的符号序列记为 $X^K$

若 $X^K$ 彼此统计独立，则定义 3.7 与 3.6 等价，也是发出符号序列消息的离散无记忆信源

发出符号序列消息的离散无记忆信源的熵为 $$H(X^K)=KH(X)=-K\sum _{i=1}^N{P}_i\mathrm{lb}{P}_i$$

定义 3.8 若信源发出的消息是由 K 个离散符号构成的符号序列，且各消息相互统计相关，则为发出符号序列消息的离散有记忆信源

有记忆信源的符号序列之间的关联程度可以用转移概率描述

符号间非独立（有关联）会使得信源输出的信息量减少

马尔可夫信源熵：是一般信源熵的特例 $$H(X|Y)=-\sum _{XY}P(xy)\mathrm{lb}P(x|y)$$

时间熵

时间熵 单位时间内发出的平均信息量 $H_t$，单位 b/s 或 bps

定义 3.9 若信源为具有 N 个单个符号消息的离散信源，第 i 个符号消息占用的时间为 $b_i$ 秒，概率为 $P_i$，则称 $b_i$ 的统计平均值为该信源符号消息的平均时间长度 $\overline{b}$ 或 平均长度，单位为秒/符号 $\overline{b}={\sum }_{i=1}^N{P}_i{b}_i$ 秒/符号

若信源平均每秒发送 n 个符号，则 $\overline{b}=1/n$ 秒/符号

对于单符号离散无记忆信源： $$H_t=\frac{H(X)}{\overline{b}}b/s$$

K 重扩展的符号序列的时间熵

K 重扩展的离散无记忆信源的符号消息平均长度 $$\overline{B}=K\overline{b}=K\sum _{i=1}^N{P}_i{b}_i$$

仍有 $H_t=\frac{H(X^K)}{K\overline{b}}=\frac{H(X)}{\overline{b}}b/s$

若信源平均每秒发送 n 个 K 重符号序列消息，则 $\overline{b}=1/nK$ 秒/符号， 有$H_t=nKH(X)b/s$

若为有记忆信源，有 $H_t=\frac{H(X^K)}{K\overline{b}}<\frac{H(X)}{\overline{b}}b/s$， 其时间熵小于无记忆信源的

消息之间的关联性体现在信源熵而非平均长度

3-3 信源的冗余度

3-3-1 最大信源熵

定理3.1 最大熵定理 设信源 X 中包含 M 个不同符号，其信源熵为 $H(X)$，有 $$H(X)\le \mathrm{lb}M$$ 当且仅当 X 中各个符号的概率全相等时取等，此时得到最大熵 $$H(X{)}_{max}=\mathrm{lb}M$$ 即熵的极值性，第二章证过

定理 3.2 两个集合 X、Y 的共熵 $H(XY)$ 与这两个集合的信源熵 $H(X),H(Y)$ 之间有 $$H(XY)\le H(X)+H(Y)$$ 当且仅当两个集合相互独立时取等，此时取得最大熵 $$H(XY{)}_{max}=H(X)+H(Y)$$

定理 3.3 对于初始信源 X 经过 K 重扩展的信源，若初始信源熵为 $H(X)$，扩展后为 $H(X^K)$，有 $$H(X^K)\le KH(X)$$ 当且仅当 K 重符号序列消息的各个符号间相互独立时取等，此时取得最大熵 $$H(X^K{)}_{max}=KH(X)$$

符号不等概或符号间有相关性都会损失信源熵

• 信源编码中要压缩冗余度来提高传输的有效性
• 信道编码中要注入冗余度来提高传输的可靠性

定义 3.10 设信源实际的熵为 H，该种信源可能的最大熵为 $H_{max}$，则信源的冗余度为 $$R=\frac{H_{max}-H}{H_{max}}\times 100\%$$ 即信源在发出消息时无用信息量的百分比

3-4 信源符号序列分组定理

设离散无记忆信源的信源空间为 $$[\mathbf{X}\cdot P]:\{\begin{array}{ccccc}\mathbf{X}:& x_1,& x_2,& \dots ,& x_N\\ P(\mathbf{X}):& P\left(x_1\right),& P\left(x_2\right),& \dots ,& P\left(x_N\right)\end{array}$$

K 重扩展后，各符号序列为 ${\mathbf{x}}_i=(x_{i1},x_{i2},\dots ,x_{iK})$，这样的符号序列有 $N^K$ 个。

当 K 足够大时，一个序列中任一符号 $x_i$ 出现的次数都会趋近于 $K{P}_i$，即扩展后很多序列的概率组成相同，是等概的 $$P(x_1,\dots ,x_N)=\sum _{i=1}^N(P_i{)}^{K{P}_i}$$

具有上述结构的序列称为 典型序列 $G_1$，其余的序列为 非典型序列 $G_2$

典型序列的自信息量也相等，为 $I({\mathbf{x}}_1)=I({\mathbf{x}}_2)=\cdots =I({\mathbf{x}}_i)=-\mathrm{lb}{P}_i$

自信息量的期望，即信息熵，为 $E\{I({\mathbf{x}}_i)\}=KH(X)$

当典型序列的概率之和很大时，就可以用典型序列来代表扩展信源（这正是数据压缩的本质）

信源符号序列分组定理说明上述分组是存在的，且可以估算其典型序列的数目

定理 3.4 信源符号序列分组定理 AEP（渐进均分特性） 设离散无记忆信源的信源符号为 $x_1,x_2,\dots ,x_i,\dots ,x_N$，各符号概率为 $P_1,P_2,\dots ,P_i,\dots ,P_N$，将该信源进行 K 重扩展得到 K 重符号序列 $\mathbf{x}$，则任意给定 $\epsilon >0,\delta >0$，总有对应整数 $K_0$，使得 $K>K_0$ 时，有 $$P\left\{\left|\frac{1}{K}\mathrm{lb}P(\mathbf{x})+H(\mathbf{X})\right|<\delta \right\}>1-\epsilon$$ 即信息熵与自信息量的差趋近于0

所谓渐近等分性：序列的越长，典型序列的总概率越接近于1，它的各个序列的出现概率越趋于相等

• 每个典型序列的概率
  • 对于任意小的正数 $\delta$，当 K 足够大时，$2^{-K(H(X)+\delta )}<P(x)<2^{-K(H(X)-\delta )}$，可近似于 $P(\mathbf{x})=2^{-KH(X)}$
• 典型序列个数
  • 对于任意小的正数 $\epsilon ,\delta$，当 K 足够大时，$(1-\epsilon )2^{K(H(X)-\delta )}\le |G_1|\le 2^{K(H(X)+\delta )}$，可近似于 $G_1=2^{KH(X)}$
• 典型序列占的比例
  • $\xi =\frac{|G_1|}{N^K}\le \frac{2^{K(H(X)+\delta }}{N^K}=2^{-K(\mathrm{lb}N-H(X)-\delta )}$
  • 根据最大熵定理，一般有 $\mathrm{lb}N-H(X)-\delta >0$
  • 随着 K 增大，典型序列占的比例逐渐趋于 0，典型序列出现概率高不等于典型序列种类多

$|G_1|$ 表示 $G_1$ 里的元素个数

信源符号序列分组定理表明，对于 K 重扩展信源，只考虑少量典型符号序列对信源特性带来的损失可以忽略，这给出了信源压缩编码的理论依据

3-5 平稳离散信源及其性质

平稳：概率分布不随时间变化

大部分实际信源在较短的一段时间都可以看作平稳信源

定义 3.10 若一个离散信源发出的符号序列 $(x_1,x_2,\dots ,x_K)$ 其出现概率与另一符号序列 $(x_{j+1},x_{j+2},\dots ,x_{j+K})$ 的出现概率相等，则为平稳离散信源

• 改变其符号序列的起始位置，其概率和条件概率均不变，即平稳离散信源对应的随机过程是严平稳的

平稳离散信源的极限熵

有记忆离散信源每发一个符号所提供的平均信息量为 $$H_{\infty }=\underset{K\to \infty }{\lim }\frac{1}{K}H(X_1{X}_2\dots X_K)\triangleq \underset{K\to \infty }{\lim }{H}_K(X_1{X}_2\dots X_K)$$

称 $H_K(X_1{X}_2\dots X_K)=\frac{1}{K}H(X_1{X}_2\dots X_K)$ 为平均符号熵，$H_{\infty }$ 为平稳离散有记忆信源的极限熵，又称熵率

平稳离散信源熵的性质

定理 3.5 若信源 X 是平稳离散信源，则有 $$H(X)=H(X_1{X}_2\dots X_K)=H(X_1)+H(X_2|X_1)+H(X_3|X_1{X}_2)+\cdots +H(X_K|X_1{X}_2\dots X_{K-1})$$ 即 $H(X)$ 是 X 中起始时刻随机变量 $X_1$ 的熵与各阶条件熵之和。也即熵的链接准则。

定理 3.6 平稳离散信源的条件熵随 K 的增加是非递增的，即 $H(X_K|X_1{X}_2\dots X_{K-1})\le H(X_{K-1}|X_1{X}_2\dots X_{K-2})$

特别的，由于平稳性，$H(X_1)=H(X_2)$，故 $H(X_2|X_1)\le H(X_2)=H(X_1)$

推论 1：给定 K 时，平稳离散信源的条件熵小于等于平均符号熵，即 $H(X_K|X_1{X}_2\dots X_{K-1})\le (1/K)H(X_1{X}_2\dots X_K)$

推论 2：平稳离散信源的平均符号熵随 K 的增加是非递增的，即 $H_K(X_1{X}_2\dots X_K)\le H_{K-1}(X_1{X}_2\dots X_{K-1})$

定理 3.7 极限熵的第二种形式 对于平稳离散信源，令 $H_K(X_1{X}_2\dots X_K)=\frac{1}{K}H(X_1{X}_2\dots X_K)$，若 $H(X_1)<\infty$，则 $H_K(X)$ 的极限值存在且有 $$H_{\infty }=\underset{K\to \infty }{\lim }{H}_K(X)=\underset{K\to \infty }{\lim }H(X_K|X_1{X}_2\dots X_{K-1})$$

• 一般离散平稳有记忆信源每发一个符号所提供的平均信息量等于极限熵 $H_{\infty }$
• $H_{\infty }$ 较难计算，但当 K 不是很大时，其平均符号熵 $H_K(X)$ 或条件熵 $H(X_K|X_1{X}_2\dots X_{K-1})$ 就非常接近于 $H_{\infty }$，可用作极限熵的近似值

第四章 离散信源的信源编码

4-1 信源编码的模型

信源编码

• 含义：将信源产生的消息变换为数字序列的过程
• 主要任务：把消息信号数字化为由信道基本符号构成的代码组（码字），并压缩冗余度，提高编码效率

编码是否会损失信源消息的信息量：

• 不损失信息量：无失真信源编码 -> 香农第一定理
• 会损失信息量：限失真信源编码 -> 香农第三定理

1. 选择合适的信道基本符号（码元），使映射后的代码适应信道
2. 用编码将信源发出的消息转换为代码组，即码字，其长度称为码长
3. 编码应使消息集合与代码组集合中的元素一一对应

称上述一一映射的信源编码器为正规编码器，编出来的码为非奇异码

可以把信源和正规编码器合称等效信源，编码器的输入为初始信源

正规编码器的一一对应确保了编码不损失信息量，因此等效信源的熵必定等于初始信源的熵

研究信源编码时将信道编译码看作信道的一部分

• 若码字长度相等，称为等长码，反之为变长码
• 若信源符号与编码码字一一对应，称为非奇异码，反之为奇异码
• 若每个码元所占时间相同，称为同价码，反之为非同价码（例如莫尔斯电码）
• N 重扩展码：针对 N 重扩展信源编码得到的码字序列集合
• 若任意一串码字序列只能唯一的译为对应的信源符号序列，称为单义可译码，反之称为非单义可译码
  • 不但要求信源符号与编码码字一一对应，即为非奇异码，还要求任意长的信源符号序列对应的码字序列一一对应，即任意 N 重扩展码均为非奇异码
  • 非单义可译码会发生译码错误，导致失真

4-2 信息传输速率和编码效率

4-2-1 信息传输率

定义4.1 对于信源编码器的输出序列，其每个码元所包含的信息量称为 信源编码器的信息传输率，简称 码率 R

• R 的单位为 bit/码元
• 若每个码元时间为 t 秒，则可以定义信息传输速率 $R_t=R/tbit/s$

等长码：

• 单符号离散信源：设信源熵为 $H(X)$，对其等长编码，每码字 b 个码元，则其信息传输率为 $R=H(X)/bbit/码元$
• K 重扩展信源：设信源熵为 $H(X^K)$，对其等长编码，每码字 B 个码元，则其信息传输率为 $R=H(X^K)/Bbit/码元$

变长码：

• 先求其代码组的平均长度
• 单符号离散信源：设信源有 N 个单符号消息 $x_1,x_2,\dots ,x_N$，变长码编码器输出的代码组长度对应为 $b_1,b_2,\dots ,b_N$，其出现概率分别为 $P(b_1),P(b_2),\dots ,P(b_N)$，则该变长码的平均长度为 $\bar{b}={\sum }_{i=1}^{N}P(b_i)b_i$，信息传输率为 $R=H(X)/\bar{b}$ bit/码元
• K 重扩展信源：设信源有 N 个 K 重扩展的符号序列消息 $x_1,x_2,\dots ,x_N$，变长码编码器输出的代码组长度对应为 $B_1,B_2,\dots ,B_N$，其出现概率分别为 $P(B_1),P(B_2),\dots ,P(B_N)$，则该变长码的平均长度为 $\bar{B}={\sum }_{i=1}^{N}P(B_i)B_i$，信息传输率为 $R=H(X^K)/\bar{B}$ bit/码元

4-2-2 编码效率

信道容量：信道的极限传输能力（平均互信息量的最大值）。根据平均互信息量的定义，在不失真传输的条件下，信道容量等于信源熵的最大值，$C=\max I(X;Y)=H(X)-H(X|Y)=H(X)$

对于含有 D 个元素的信道基本符号集合，等效信源的最大熵等于 $\mathrm{lb}D$ bit/码元，因此 $C=\mathrm{lb}D$ bit/码元

定义 4.3 信源编码器输出代码组的信息传输率与信道容量之比，称为信源编码器的编码效率，即 $\eta =\frac{R}{C}\times 100\%$

• R = C 时，信源编码能充分利用信道
• R > C 时，信源编码输出信息的速率超过了信道传输能力，必然失真
• R < C 时，未充分利用信道

编码效率： $$\eta =\frac{H(X^K)/\bar{B}}{\mathrm{lb}D}\times 100\%$$

要提高编码效率可以减小代码组的平均长度

通常称具有最短的代码组平均长度或编码效率接近于 1 的信源编码为最佳信源编码，亦简称为最佳编码

要达到最佳编码，通常需遵循下面两个原则：

1. 对信源中出现概率大的消息（或符号），尽可能用短的代码组（码字）来表示，简称短码；反之用长码
2. 不使用间隔即可区分码字
   • 要求单义可译性

原则一可以描述为：

定理4.1 设信源有 N 个消息分别为 $x_1,x_2,\dots ,x_N$，出现概率分别为 $P(x_1),P(x_2),\dots ,P(x_N)$，信源编码器输出的 N 个代码组分别为 $s_1,s_2,\dots ,s_N$，对应长度分别为 $b_1,b_2,\dots ,b_N$，若信源消息的概率分布满足 $P(x_1)>P(x_2)>\cdots >P(x_N)$，而信源编码器输出的代码组长度满足 $b_1<b_2<\cdots <b_N$，则该代码组的平均长度为最短。

最佳编码应满足 $b_i\ge {\log }_D\frac{1}{P(x_i)}$，即可满足单义可译

4-3 单义可译定理

定义 4.4 对任何一个有限长度的信源消息序列，如果编码得到的码字序列不与其他任何信源消息序列所对应的码字序列相同，则称这样的码为单义可译码。

即时码：译码时不需要考察后续码元，一定为单义可译码

定理 4.2 设 $s_i(a_{i1}{a}_{i2}\dots a_{ik})$ 是码 S 中的任一码字，码 S 为即时码的充要条件是：对于任意的 m＜k ，任意码字 $s_j(a_{j1}{a}_{j2}\dots a_{jm})$ 都不是码字 $s_i(a_{i1}{a}_{i2}\dots a_{ik})$ 的前缀。

等长码都是即时码

即时码 ⊆ 单义可译码 ⊆ 非奇异码 ⊆ 所有码

定理 4.3 单义可译定理 即时码存在定理 设信源消息集合为 $X=\{x_1,x_2,\dots ,x_N\}$，信道基本符号的种类为 D，码字集合为 $S=s_1,s_2,\dots ,s_N$，对应的码长集合为 $b=b_1,b_2,\dots ,b_N$，则存在即时码的充分必要条件是：D、N 和码长应满足如下不等式： $$\sum _{i=1}^N{D}^{-b_i}\le 1$$ 上式称为 Kraft 不等式。

任何一个结构为 $N,D,b_i(i=1,2,\dots ,N)$ 的即时码一定满足 Kraft 不等式；而满足 Kraft 不等式的 $N,D,b_i$ 又至少可构成一种结构为 $N,D,b_i$ 的即时码

定理 4.4 平均码长界定定理 若一个离散无记忆信源 X，具有熵 $H(X)$，对其编码用 D 种基本符号，则总可以找到一种无失真信源编码，构成单义可译码，使其平均码长满足 $$\frac{H(X)}{\mathrm{lb}D}\le \bar{b}\le \frac{H(X)}{\mathrm{lb}D}+1$$

平均码长界定定理的物理意义：

• 下界证明是充要性证明，因此单义可译前提下平均码长的下界值为 ${\bar{b}}_{min}=\frac{H(X)}{\mathrm{lb}D}$
• 也可以从信息传输率的角度理解下界，即 $\frac{H(X)}{\bar{b}}\le \mathrm{lb}D$，信息传输率不能超过信道容量，否则无法实现单义可译，从而造成译码错误
• 由于上界证明仅仅是充分性证明，因此平均码长大于定理中的上界也可能是单义可译码
• 给定信源空间 $\{X，P(X)\}$ 的离散信源，其熵 $H(X)$ 是确定值，如果信道基本符号数 D 也给定，则 ${\bar{b}}_{min}$也就定了。为此，需要改变信源本身统计特性，例如进行扩展
  • 扩展后，可能使得每个消息的长度 $B_i/K<b_i$，这样平均长度也应减小

4-4 无失真信源编码定理

二进制编码和无记忆信源条件下香农第一定理：

• 对于二进制编码，D=2。根据平均码长界定定理有 $H(X)\le \bar{b}\le H(X)+1$
• 类似地，对初始信源进行 K 重扩展，有 $H(X^K)\le \bar{B}\le H(X^K)+1$
• 对于无记忆信源，$H(X^K)=KH(X)$ 成立，因此 $H(X)\le \frac{\bar{B}}{K}\le H(X)+\frac{1}{K}$
• 当 $K\to \infty$，有 ${\lim }_{K\to \infty }\frac{\bar{B}}{K}=H(X)$
• 上式即是二进制编码和无记忆信源条件下香农第一定理的数学表示式

定理 4.5 香农第一定理 无失真信源编码定理 变长码信源编码定理： 设离散无记忆信源 X 包含 N 个符号 $\{x_1,x_2,\dots ,x_N\}$，信源发出 K 重符号序列， 则此信源可发出 $N^K$ 个不同的符号序列消息，其中第 j 个符号序列消息的出现概率为 $P_{Kj}$， 其信源编码后所得的 D 进制代码组长度为 $B_j$，代码组的平均长度为 $\bar{B}={\sum }_{j=1}^{N^K}{P}_{Kj}{B}_j$， 总可以找到一种编码构成单义可译码，使得 $\bar{B}$ 满足 $$\frac{H(X)}{\mathrm{lb}D}\le \frac{\bar{B}}{K}\le \frac{H(X)}{\mathrm{lb}D}+\frac{1}{K}$$ 当K趋于无限大时，${\lim }_{K\to \infty }\frac{\bar{B}}{K}=\frac{H(X)}{\mathrm{lb}D}$

定理指出

• 要做到无失真的信源编码，每个信源符号平均所需要最少的 D 进制码元数，就是信源的熵值（熵定义中的log底数为D），或记为 $H_D(X)\triangleq \frac{H(X)}{\mathrm{lb}D}$
• 扩展信源可以减少平均码元数，但有极限
• 此外，减少平均码元数是以增加编码的复杂性（存储复杂度）为代价的
• 从编码效率角度理解，不等式取到下界时，编码效率为 100%，可见无失真信源编码的实质就是对离散信源进行适当的变换，使变换后新的符号序列信源尽可能为等概率分布，以使新信源的每个码符号平均所含的信息量达到最大，进而使信息传输率R达到信道容量C，实现信源和信道理想的统计匹配

4-5-1 香农编码方法

1. 先将信源消息的概率按 $P(x_1)\ge P(x_2)\ge \cdots \ge P(x_N)$降序排列，然后计算 $P_i={\sum }_{k=1}^{i-1}P(x_i)$，即 $P_i$ 为前 i–1 个概率的累加
2. 再把 $Pi$ 变为二进制小数，取小数点后的 $b_i$ 位数作为第 i 消息的码字，其中 $b_i$ 满足 $$b_i=\lceil {\log }_D\frac{1}{P(x_i)}\rceil$$

二进制小数：将小数部分一直乘 2，积的整数部分顺序取出

特点：

• 先得到码长，再得到码字
• 码字集合唯一
• 并非一定最优

4-5-2 费诺编码方法

又称子集分解法

1. 将信源消息符号按其出现的概率大小依次排列
2. 将依次排列的信源符号按概率值分为两大组，使两个组的概率之和接近相同，并对各组赋予一个二进制码元“0”和“1”
3. 将每一大组的信源符号进一步再分成两个组，使分解后的两个组的概率之和接近于相同，并又赋予两个组一个二进制符号“0”和“1”
4. 如此重复，直至每个组只剩下一个信源符号为止

特点：

• 先得到码字，再得到码长
• 码字集合唯一

4-5-3 霍夫曼编码

本科数字通信笔记第四页，这里使用 as low as possible 或者 as high as possible 都可以

特点：

• 码字集合不唯一

• 二元霍夫曼编码是最佳编码

• r 元霍夫曼编码可能需要扩展原信源，使得霍夫曼最后一步的信源有 r 个符号，故需扩展到 $(r-1)\theta +r$ 个信源符号

4-5-4 Lempel-Ziv 编码

与本科数字通信所学不一样

未出现过的子列用 0 开头

特点：

• 独立于信源的统计特性，是一种变长到定长的编码方案
• 利用了已编码信息来进行当前的编码，是等长码，编码的过程就是建立码地址和将待编码消息序列分段的过程，所有的码段内容都是不同的
• 对于长的消息序列，压缩比较明显
• 地址会不断变长，可以用相对地址解决
  • 将编码结果表示为3部分内容：<相对地址，可利用的已编码信息长度，本次编码新增加字符>，称之为编码包
  • 可利用的只要是已经编码过的信息就行，不需要是一整个包什么的
  • 第一部分：利用的已编码信息在当前信息之前多少 位，是按序列数的，不是按包
  • 第二部分：利用的已编码信息长度
  • 两个相当于是 数组首地址（相对） 和 数组长度
  • 如果下一个要编码的刚好是上一个已编码符号 x 的 n次重复，则写为 <1,n x>

4-5-5 等长码的信源编码定理

设等长码的信源的消息符号集合为$X=(x_1,x_2,\dots ,x_N)$，进行 K 重扩展后，符号序列消息的总数为 $N^K$；设信道有 D 种基本符号，每个码字有 B 个码元，故最多有 $D^B$ 种码字，要满足单义可译性，应满足 $D^B\ge N^K$ ，即 $$B\ge K\frac{\mathrm{lb}N}{\mathrm{lb}D}$$ 或 $$\frac{B}{K}\mathrm{lb}D\ge \mathrm{lb}N=H(X{)}_{max}$$