-
软件平台：
操作系统：Windows 10专业版，64位操作系统
开发软件：Microsoft Visual Studio Premium 2012
-
硬件配置：
CPU：Intel i7-9700 内存：16GB
- 编程语言：C++、MFC框架
- 编译选项：使用Release选项、本地Windows调试器
程序运行界面如图所示，提供下述功能点:
ASCII编码与解码- Huffman编码与解码
- Hamming码纠错与检错功能
- OOK信号调制与解调
- 自定义OOK调制周期
- 为OOK调制添加指定方差的高斯白噪声
- 动态绘制OOK解调与调制图像
给定传输内容，理解霍夫曼编码对内容的压缩作用，设计并实现霍夫曼编码和解码算法，展示编码和解码的结果，分析霍夫曼编码的效率和数据压缩率。
霍夫曼编码使用不定长编码，而非固定位数的二进制编码方法。依据特定字符串中不同字符出现频率的差别，来构造一棵二叉树，使这棵树叶子结点的带权路径之和最小。该编码方法极为有效地提升了编码的效率以及数据压缩率。
由于霍夫曼编码采用的是不定长编码，因此其编码方法必须保证任一字符的编码都不是另一个字符的编码的前缀，这种编码方法又被称为前缀码。
霍夫曼编码使用二叉树构造前缀码，让权值大的树更靠近树根，也就是让出现频率高的字符编码更短，这就使带权路径之和取得了最小值。在具体的实现过程中，我使用优先队列保存树节点，在优先队列中出现频率最低的节点被放在了队列的头部，只要优先队列中存在超过两个节点，就不断地进行pop操作，构造新的父节点；对于解码过程，只需要将接收到的二进制字符串不断地从根节点向下遍历即可（遇零走左分支，遇一走右分支），伪代码以及实现细节详见代码说明文档。
计算机中的字符都用ASCII码表示，而ASCII码是定长编码，所有字符的编码都是8位，但是在平常遇到的字符串中并不一定所有字符都会出现，在这种情况下，可以用霍夫曼编码极大提升数据压缩率和编码效率，事先统计字符串中各个字符出现的频率，然后构造哈夫曼树和哈夫曼编码，并把编码作为字典保存，这样文件就得到了压缩。
使用霍夫曼编码和ASCII编码对《sense 8》美剧中的一段台词进行编码，并将两者编码结果详细展示。此外还对随机生成的数字序列和英文字符序列进行编码，分析其平均码长和数据压缩率。
《sense8》字幕（共161字符）：
The improbable unfolding of recent events have led me to consider that no one thing is one thing only. It is in this unfamiliar realm, we find new possibilities.
霍夫曼编码（668字符）：
00000111011001111001010000000101100011010111000101111110001110101111000001011110011110101110100011010111111100111010100011111010001011000100011111110011100110011010111111100100101101011010111001101011110111010110001111010000011110100110101100001001010111100100100001101110001110100110110101111001110111110101101010111101111010011011001011111110011100100010110101011110111101001101100101111111001110101011111110100001110011001100000010100111001000101100101111110100110110010001011000001011110011110111100000101110101010111100011101000101110111111011000000001101100000000111100011101011110001111011110110000001100001011010001000100101110000101110101010010100110010001100
0101010001101000011001010010000001101001011011010111000001110010011011110110001001100001011000100110110001100101001000000111010101101110011001100110111101101100011001000110100101101110011001110010000001101111011001100010000001110010011001010110001101100101011011100111010000100000011001010111011001100101011011100111010001110011001000000110100001100001011101100110010100100000011011000110010101100100001000000110110101100101001000000111010001101111001000000110001101101111011011100111001101101001011001000110010101110010001000000111010001101000011000010111010000100000011011100110111100100000011011110110111001100101001000000111010001101000011010010110111001100111001000000110100101110011001000000110111101101110011001010010000001110100011010000110100101101110011001110010000001101111011011100110110001111001001011100010000001001001011101000010000001101001011100110010000001101001011011100010000001110100011010000110100101110011001000000111010101101110011001100110000101101101011010010110110001101001011000010111001000100000011100100110010101100001011011000110110100101100001000000111011101100101001000000110011001101001011011100110010000100000011011100110010101110111001000000111000001101111011100110111001101101001011000100110100101101100011010010111010001101001011001010111001100101110
霍夫曼编码和ASCII编码的平均码长见下表：
| 平均码长 | 霍夫曼编码 | ASCII编码 | 数据压缩率 |
|---|---|---|---|
| 《sense 8》 | 4.14907 | 8 | |
| 随机英文字符（100位） | 4.07000 | 8 | |
| 随机数字（100位） | 3.31000 | 8 |
数据压缩率的计算（以《sense 8》台词为例）：相对于ASCII编码，其数据压缩率为：$1-(668/1288)=48.1%$
编码后的数据通过信道进行传输，试设计一种调制解调方法通过信道传输数据。
无论是模拟调制，还是数字调制，都是采用调制信号去控制载波信号的三要素：幅度、频率和相位，分别称为调幅、调频和调相。本文采用数字调制ASK中的特例：OOK调制实现信号在信道上的传输，该调制方法只有比特1有信号，比特0没有信号，所以称为On-Off Keying，简称OOK调制。
基于正弦信号实现OOK调制，给定编码周期period，那么对于每一个待编码的比特，都可按照公式$t[n]=x[n]sin(\Omega_cn)$来进行调制，其中$\Omega_c=2\pi/period$，$x[n]$的取值只有两种即0或1。在进行解码时，使用相似的公式$z[n]=t[n]sin(\Omega_cn)$进行解调。而后对$z[n]$进行滑动平均滤波得到最终结果$r[n]$，伪代码以及实现细节详见代码说明文档。
周期设定为16，对二进制序列01100110进行OOK调制的结果如上图所示，可以看到y轴取值在$[0, 1]之间，x轴长度为128，对该波形进行解调，得到结果如下图所示。
在理论情况下信道中不存在噪声，因此该解码结果较为理想，在下一节会详细讲述添加噪声之后的编码结果与分析。
在真实传输中，数据传输可能会有噪声产生影响，试在生成的传输信号上添加噪声，测试噪声对解码成功率的影响。
对于一个纯随机过程来说，若其期望为0，方差为常数，则称之为白噪声过程。高斯噪声则是指概率密度函数服从正态分布的噪声。高斯分布，记为$N(\mu, \sigma^2)$，其中$\mu$为高斯分布的均值（数学期望），$\sigma^2$为高斯分布的方差。由于高斯白噪声能够反映实际通信信道中的噪声情况，能够比较真实的反映信道噪声的一些特性，并且可以用具体的数学表达式表示，适合分析、计算系统的抗噪声性能，所以广泛应用于通信系统的理论分析。
对于高斯白噪声的生成方式，经过调研，在C++中存在封装好的库函数，使用normal_distribution进行调用即可实现，伪代码以及实现细节详见代码说明文档。
由于对通过信道传输数据的调制方式采用OOK的方法进行传输，因此单独查看高斯白噪声在每个采样节点的分布，只需要对全零的二进制序列，进行调制后添加噪声即可。噪声的均值为0，对于不同方差，生成的图像分别如下图所示。其中对于不同噪声对于解码成功率的影响，详见下一节的比较。
此外，为了验证生成数据的正确性，单独将normal_distribution所生成的数据（均值为0，方差0.4）保存在data.txt文件中，而后编写python脚本对生成的数据进行直方图统计，左图是数据量为1000的分布，右图是数据量为10000的分布，可以发现其分布基本满足正态分布。
import matplotlib.pyplot as plt
fd = open('data.txt', 'r')
li = []
for line in fd.readlines():
li.append(float(line))
plt.hist(li, bins=100, color='steelblue', density=True)
plt.show() 理解纠错检错的原理，展示方法如何在数据发生错误时能够对数据进行一定程度检错或者纠错。思考相关方法怎么能够在有噪声的情况下提高网络性能，并展示相关方法的效果。
Hamming Code（汉明码）是一种线性纠错码，与其他的错误校验码类似，汉明码也利用了奇偶校验位的概念，通过在数据位后面增加一些比特，验证数据的有效性。汉明码不仅可以用来检测传输数据时发生的错误，还可以用来修正错误。（汉明码只能修正一位错误，对于两位或者两位以上的错误无法正确纠正）
假设数据由m个数据位（信息）和r个冗余位（校验）组成，其中r个校验位是由与之相关的m个数据位的函数计算获得的（也可理解为矩阵运算），令数据块的总长度为$n = m + r$，则利用汉明码进行校验所需的最小校验位个数需满足公式$2^r\geq(m+r+1)$，在汉明码中二的幂次方的位(1, 2, 4, ...)是校验位，其余位用来填充数据，根据码率的计算公式$R=m/n=1-\frac{r+1}{2^r-1}$可知，使用(7, 4)汉明码进行编码得到的码率最高，因此在具体实现时也采用该方法，伪代码以及实现细节详见代码说明文档。
本节以model为例，进行编码和调制解调，并且增加不同数值的噪声，对比不同方法的鲁棒性和解码正确性。
不失一般性，假设高斯白噪声的方差为0.2，固定编码周期为16，对汉明码编码后的二进制字符串进行OOK调制和解调的图片分别如下：
除此之外，在周期不同、高斯白噪声方差不同的情况下，对不同的编解码方式进行了详细的比较，截图不进行一一列举，将结果进行整理，表格如下（随机数种子固定为1222，方差取值为$[0.1, 1]$，步长为0.1）：
| Noise | period=8 | period=16 | period=24 |
|---|---|---|---|
| ASCII Code | 0.5 | 0.6 | 0.6 |
| Huffman Code | 0.5 | 0.5 | 0.9 |
| Hamming Code | 1.0 | 1.0 | 0.9 |
该表中统计了不同编码方式，在OOK编码不同周期的情况下，噪声方差取何值时出现错误，例如使用Hamming Code编码方式，OOK编码周期为8时，噪声方差为1.0时解码报错。由此表可知，Hamming Code由于提供纠错检错机制，因此其抵抗噪声的效果最佳。
注：虽然随机数种子固定，但是由于不同编码方式的编码长度不同，因此其进行调制时的高斯白噪声也有所差别，在不同情况下结果可能会有微小差别。
### 六、实验总结 通过本次《网络建模与分析》课程，系统全面地学习了如何对网络进行建模，以及报文在网络信道中传输可能会遇到的各种情况和报文传输的整体流程，从对字符内容的二进制编码开始，再到经由信道传输调制后的信号。由于信道当中噪声的存在，还需要为信息增加纠错检错机制，使得数据能够在一定程度上纠错。
由各项实验结果可知，汉明码有效的提高了信道的整体容错机制。如果不使用汉明码进行编码，当高斯白噪声的方差取0.6左右时，对于其他没有纠错功能的编码方式，很容易报错或者解码错误；而使用汉明码这一编码方式，能够在有噪声的情况下，传递更多完整的信息到达对端，从而有效地提高网络性能。