有两种方法可以将字符串打印到控制台:
1. C风格:从普通的C函数打印
2. systemc样式:从systemc模拟内核调用的systemc方法打印




SystemC头文件:
要使用SystemC类库特性，应用程序必须包含以下指定的C头文件之一:
1. `#include<systemc.h>`

a) `system .h`将名称空间`sc_core`和`sc_dt`中的所有名称添加到包含该名称的声明性区域，以及名称`sc_unnamed`和来自标准C或C库(例如`cin`, `cout`, `iostream`)的选定名称。

b) `system .h`是为向后兼容早期版本的SystemC而提供的，可能在本标准的未来版本中被弃用。

2. `#include <systemc>`

Systemc是没有使用的旧systemh
一个常见的做法是包括，然后是"`using namespace sc_core`"。然后，程序员可以根据需要包括其他名称空间。

SystemC入口点:

普通c程序的入口点是`main()`函数，而systemC用户必须使用`int_sc_main(int argc, char* argv[])`作为入口点。
这是因为systemC库已经定义了`main()`函数。`Main()`将调用`sc_main()`并传递命令行参数。

SystemC模块:

systemC模块是继承sc_module基类的类(或结构)。
# helloworld.cpp
```c++
#include <systemc> // 包含systemC头文件
using namespace sc_core; // 使用命名空间

void hello1() { // 一个普通的 C++ 函数
  std::cout << "Hello world using approach 1" << std::endl;
}

struct HelloWorld : sc_module { // 定义 systemC 模块
  SC_CTOR(HelloWorld) {// 构造函数，稍后将解释
    SC_METHOD(hello2); // 将成员函数注册到内核
  }
  void hello2(void) { // systemC 模拟内核的函数，可以省略 ()里的void 
    std::cout << "Hello world using approach 2" << std::endl;
  }
};

int sc_main(int, char*[]) { // 入口点
  hello1(); //方法#1：手动调用普通函数
  HelloWorld helloworld("helloworld"); // 方法 #2，实例化一个 systemC 模块
  sc_start(); // 让 systemC 模拟内核调用 helloworld.hello2（）;
  return 0;
}

```

```结果
 SystemC 2.3.3-Accellera --- Oct  4 2020 22:59:38
        Copyright (c) 1996-2018 by all Contributors,
        ALL RIGHTS RESERVED
Hello world using approach 1
Hello world using approach 2
```

SystemC入门（二）——hello world

# 两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。



示例 1：

输入：`nums = [2,7,11,15], target = 9`
输出：`[0,1]`
解释：因为 `nums[0] + nums[1] == 9` ，返回 `[0, 1]` 。

示例 2：

输入：`nums = [3,2,4], target = 6`
输出：`[1,2]`

示例 3：

输入：`nums = [3,3], target = 6`
输出：`[0,1]`
 

提示：

`2 <= nums.length <= 104`

`-109 <= nums[i] <= 109`

`-109 <= target <= 109`
只会存在一个有效答案
 

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

![两数之和](https://qncdn.oleehu.xyz/blog/LeetCode/%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8C.png)


```c++
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::vector<int> vec(2);
        std::vector<int>::iterator it1;
        std::vector<int>::iterator it2;
        for(it1=nums.begin();it1 != nums.end();it1++){
            for(it2=it1+1;it2 != nums.end();it2++){
                if((*it1)+(*it2)==target){
                    vec[0]=it1-nums.begin();
                    vec[1]=it2-nums.begin();
                    
                    goto hello;
                }
                
            }
           
        }
        hello: return vec;
        
    }
};
```

# 题解：哈希表
作者：力扣官方题解

链接：https://leetcode.cn/problems/two-sum/solutions/434597/liang-shu-zhi-he-by-leetcode-solution/

来源：力扣（LeetCod

思路及算法

注意到方法一的时间复杂度较高的原因是寻找 `target - x` 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。

使用哈希表，可以将寻找 `target - x` 的时间复杂度降低到从 `O(N)` 降低到 `O(1)`。

这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 `target - x`，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。

![两数之和（题解）](https://qncdn.oleehu.xyz/blog/LeetCode/%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8C%EF%BC%88%E9%A2%98%E8%A7%A3%EF%BC%89.png)

```C++
class Solution {
public:
    // 定义一个函数twoSum，输入参数为一个整数向量nums和一个目标值target
    vector<int> twoSum(vector<int>& nums, int target) {
        // 使用unordered_map作为哈希表存储已经遍历过的数字及其对应的索引
        unordered_map<int, int> hashtable;
        // 遍历整个nums向量
        for (int i = 0; i < nums.size(); ++i) {
            // 在哈希表中查找是否存在一个数字等于target - nums[i]
            auto it = hashtable.find(target - nums[i]);
            // 如果找到了这样的数字，就返回这两个数字的索引组成的向量
            if (it != hashtable.end()) {
                return {it->second, i};
            }
            // 如果没有找到匹配的数字，就将当前数字nums[i]及其索引i添加到哈希表中
            hashtable[nums[i]] = i;
        }
        // 如果遍历完整个向量后仍然没有找到满足条件的两个数字，函数将返回一个空向量
        return {};
    }
};

```

复杂度分析

时间复杂度：`O(N)`，其中 N 是数组中的元素数量。对于每一个元素 x，我们可以 `O(1)` 地寻找 `target - x`。

空间复杂度：`O(N)`，其中 N 是数组中的元素数量。主要为哈希表的开销。

LeetCode（两数之和）

# 用 Docker 安装 SystemC 环境

- 安装 Docker
  在 Windows 系统上安装 Docker Desktop。[安装教程](https://docs.docker.com/desktop/install/windows-install/)
  其他操作系统类似，不再赘述。
- 下载 SystemC 镜像
  打开终端，下载 systemC docker 镜像，其中包括 Ubuntu 20.04, g9.3.0, gdb 9.1, make, vim 和 systemC 2.3.3:



```shell
docker pull learnwitheexamples / systemC
```

- 运行 SystemC docker 镜像:

```shell
docker Run -it learnwiththeexamples /systemc
```

在 docker 映像中放置了一个“hello world”示例来验证环境设置。构建和运行:

```shell
cd helloworld
make
./out
```
# 用VScode开发和调试Docker容器

虽然你可以直接在 Docker 容器中开发和调试，但我个人建议通过 Visual Studio Code 进行远程开发，就像 VS Code 远程容器中介绍的那样。

- [下载并安装 Visual Studio Code](https://code.visualstudio.com/download)
- 安装扩展

  [Chinese (Simplified) (简体中文) Language Pack for Visual Studio Code](https://marketplace.visualstudio.com/items?itemName=MS-CEINTL.vscode-language-pack-zh-hans)
  
  [Dev Containers](https://marketplace.visualstudio.com/items?itemName=ms-vscode-remote.remote-containers)
  
  [Docker](https://marketplace.visualstudio.com/items?itemName=ms-azuretools.vscode-docker)
  
  [c/c++ extension](https://marketplace.visualstudio.com/items?itemName=ms-vscode.cpptools)
  
  [CMake Tools](https://marketplace.visualstudio.com/items?itemName=ms-vscode.cmake-tools)
  
  [CMake](https://marketplace.visualstudio.com/items?itemName=twxs.cmake)
  [Makefile Tools](https://marketplace.visualstudio.com/items?itemName=jeff-hykin.makefile-tools)
  
  [IntelliCode](https://marketplace.visualstudio.com/items?itemName=VisualStudioExptTeam.vscodeintellicode)
  
docker 容器不能访问您的本地文件，除非您使用“-v”选项挂载它。例如，要将本地路径挂载到容器中的某个位置，可以使用以下命令:

```shell
docker run -it -v local_path:mount_point learnwiththeexamples /systemc
```

其中 Local_path:您希望 docker 容器访问的本地机器的路径,mount_point:是本地路径内容在 Docker 容器中显示的位置。
在 Windows 操作系统中，将本地 C 驱动器挂载到 docker 容器的/home 目录下:

```shell
docker run -it——name systemc -v C:/:/home learnwiththeexamples /systemc
```

SystemC入门（一）——用 Docker 安装 SystemC 环境

- **狭义信息论**是一门应用数理统计方法来研究信息处理和信息传递的科学。它研究存在于通讯和控制系统中普遍存在着的信息传递的共同规律，以及如何提高各信息传输系统的有效性和可靠性的一门通讯理论。

- **一般信息论主**要是研究通讯问题，但还包括噪声理论、信号滤波与预测、调制与信息处理等问题。
- **广义信息论**不仅包括狭义信息论和一般信息论的问题，而且还包括所有与信息有关的领域，如心理学、语言学、神经心理学、语义学等。

- **信源**：产生消息的来源- 信宿：消息传送的终点- 信道：信号传输的媒介![通信系统模型.jpg](https://qncdn.oleehu.xyz/blog/通信系统模型.jpg?img)
- **信号**：消息的载体
- **消息**：信息的载体（具有不确定性）
- **信息**：信息的内涵，即消息中包含的有意义的内容
- **通信系统的目的**：消除或部分消除不确定性，从而获得信息
- **信源编码**：压缩信源冗余度，提高信息传输效率，提高通信系统的有效性
- **信道编码**：增加冗余，提高了纠错检错能力，提高通信系统的可靠性
- **信息的度量**：概率空间，先验概率，自信息，互信息等。
${I \left( x\mathop{{}}\nolimits_{{i}} \left)  \triangleq -log\;p \left( x\mathop{{}}\nolimits_{{i}} \right) \right. \right. }$
 - **自信息**：该事件发生的概率对数负值\
 $$I(x_i;y_j) =I(x_i)-I(x_i|y_j)\qquad(I=1,2...n;j=1,2...m) \\ = \log \;\frac{p(x_i|y_j)}{p(x_i)}$$
 - **互信息**：表示$y_j$出现前后关于事件$x_i$的不确定性减少的量；事件$y_j$出现以后信宿获得的关于事件$x_i$的信息量。
 - - 性质：互信息的对称性；互信息可为正值、负值、或为0；任何两个事件之间的互信息不可能大于其中任一事件的自信息。
 -  **平均自信息**：（信息熵、信源熵、香农熵、无条件熵、熵函数、熵），单位：比特/符号。\
 $H(X) \triangleq E[I(x _i)]=- \sum^{n}_{i=1} p(x_i)log\;p(x_i)$
 - - 含义：
 （1）通信前，信源符号的平均不确定性。\
 （2）通信后，信号平均每个符号提供的信息量。
  - - 性质：
  （1）非负性（离散信源熵）\
  （2）极值性：离散无记忆源输出n个不同的信息符号，当且仅当各符号出现概率相等时熵最大。\
  （3）强可加性：
  $H(XY)=H(X)+H(Y|X)=H(Y)+H(X|Y)$\
  推广：
$H(X_1X_2...X_N)=H(X_1)+H(X_2|X_1)+H(X_3|X_1X_2)+...H(X_N|X_1X_2...X_{N-1})$
  - **联合熵**：随机变量X和Y的联合分布为$P(x_i y_j)$
  $H(XY)=- \sum^{n}_{i=1}\sum^{m}_{j=1}\;log\;p(x_i y_j)$\
  - **条件熵**:随机变量X和Y的条件熵定义为噪声熵： 
 $H(X|Y)=-\sum_i \sum_j p(x_i y_j)log\;p(x_i|y_j)$\
  **损失熵**：
  $H(Y|X)=-\sum_i \sum_j p(x_i y_j)log\;p(y_j|x_i)$\
  条件熵表示已知一个随机变量，对另一个随机变量的平均不确定性。
  - **平均互信息**\
  $I(X;Y)=H(X)-H(X|Y) \\ =H(Y)-H(Y|X) \\ =H(X)+H(Y)-H(XY)$
  $$
\tiny 随机序列=\left\{ \begin{aligned} 非平稳信源\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\\平稳信源\left\{ \begin{aligned}连续平稳信源\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\\离散平稳信源\qquad\left\{ \begin{aligned} 离散无记忆信源\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\\离散有记忆信源\qquad\left\{ \begin{aligned} 记忆长度无限长\qquad\qquad\qquad\qquad\\记忆长度有点长（马尔可夫信源）\qquad\end{aligned} \right.\end{aligned} \right.\end{aligned} \right.\end{aligned} \right.
$$
  - **平稳信源**：各维度联合概率分布与时间起点无关。
  - **信源无记忆**：前后符号间独立。
  - **平均符号熵**：\
  $H_N(X)=\frac{1}{N}(X_1X_2...X_N)$\
  N趋于无穷时：$H_\infty=\lim\limits_{x\rightarrow\infty}H_N(X)$（极限熵）
   - **扩展信源**：把信源输出N长符号序列看成是一个新信源，即N次扩展信源。离散平稳无记忆信源的N次扩展信源的熵等于离散单符号信源熵的N倍：\
   $H ( X ) = H ( X ^ { N } ) = N H ( X )$
  - 离散平稳无记忆信源的熵率\
   $H _ { \infty } = \lim \limits_ { N \rightarrow \infty } H _ { N } ( X ) \\= \lim\limits _ { N \rightarrow \infty } \frac { 1 } { N } \cdot N H ( X ) \\= H ( X )$
- 离散平稳有记忆信源：
设信源输出N长的符号序列，用N维随机矢量$X = X _ { 1 } X _ { 2 } \cdots X _ { n }$来表示信源\
N维随机矢量的联合熵为：\
$H ( X ) = H ( X _ { 1 } X _ { 2 } \cdots X _ { N } )\\= H ( X _ { 1 } ) + H ( X _ { 2 } | X _ { 1 } ) + H ( X _ { 3 } | X _ { 1 } X _ { 2 } ) + \cdots H ( X _ { N } | X _ { 1 } X _ { 2 } \cdots X _ { N } )$ (熵函数链规则)
- - 条件概率阶数：m，记忆长度m+1
- - 定理：
(1)条件熵 $H ( X _ { N } | X _ { 1 } X _ { 2 } \cdots X _ { N - 1 } )$随N的增加而减小。\
(2)N给定时平均符号熵大于等于条件熵：$H _ { N } ( X ) \geqslant H ( X _ { N } | X _ { 1 } X _ { 2 } \cdots X _ { N - 1 } )$\
(3)平均符号熵随N的增加是递减的。\
(4)对于离散平稳信源，如果 $H _ { 1 } ( X ) <\infty$，则有\
$H _ { \infty } = \lim\limits _ { N \rightarrow \infty } H _ { N } ( x ) \\= \lim\limits _ { N \rightarrow \infty } \frac { 1 } { N } H( X _ { 1 } X _ { 2 } \cdots X _ { N } )\\= \lim\limits _ { N \rightarrow \infty } H ( X_ { N } | X _ { 1 } X _ { 2 } \cdots X _ { N - 1 } )$
- **M阶马尔可夫信源**：信源在某时刻发出的符号仅与在此之前发出的m个符号有关。熵率：\
$H _ { \infty } = \lim\limits _ { N \rightarrow \infty } H ( X _ { N } | X _ { 1 } X _ { 2 } \cdots X _ { N - 1 } )\\= \lim \limits_ {  N\rightarrow \infty}H ( X _ { N } | X _ { N - m} X _ { N-m + 1 }  \cdot \cdot \cdot X _ { N })\\= H ( X _ { M + 1 }| X _ { 1 } X _ { 2 } \cdots X _ { m } )\\= H _ { m + 1 }$
- **齐次马尔可夫链**
定义：马氏链状态转移概率与起始时刻无关，随机变量状态仅与上一时刻所处状态有关联，与再之前的状态无关联。\
状态转移概率：（描述马氏链最重要的参数）\
$P _ { i j } ( m , n ) = P \{ { X _ { n } =S _ { j } | X _ { m } = S _ { i } }\}\\= P \{{ X _ { n } = j | X _ { m } = i }\}$
- 马氏链平稳 (稳态)分布
定义：时齐、有限马尔科夫链满足各态历经性，转移步长足够长，最终各状态绝对概率分布达到稳态。\
稳态分布存在条件：设P为马氏链的状态转移矩阵，则该马氏链平稳分布存在的充要条件是存在一个正整数N,使矩阵P^N^中的所有元素均大于零。\
稳态分布求解：求解前必须验证稳态分布是否存在！若W~j~为平稳分布，W~j~是满足方程组WP=W和W~J~≥0，$\sum_{i=1}^J  W_J=1$的唯一解。\
符号间相关性越大，熵越小。熵的相对率:\
$\eta = \frac { H _ { \infty } } { H _ { 0 }}$\
信源的剩余度\
$\gamma = 1 - \eta = 1 - \frac { H _ { \infty} } { H _ { 0 } } = 1 - \frac { H _ { \infty } } { \log q }$
- **信道定义**：信号的传输媒介，传送信息的物理通道。
- - 按输入/输出信号的幅度和时间特性划分：

| 幅度 | 时间 |  信道分类名称|
|--|--|--|
| 离散 | 离散 | 离散信道/数字信道（例如：数字电话） |
| 连续 | 离散 |  连续信道|
| 连续 | 连续 |  模拟信道/波形信道（例如：模拟电话）|
| 离散 |  连续|  (理论和实用价值均很小)|
- - 按输入/输出之间的记忆性来划分：
无记忆信道：信道在某时刻的输出只与信道该时刻的输入有关而与信道其他时刻的输入、输出无关。
有记忆信道：信道在某时刻的输出与其他时刻的输入输出有关。
- - 根据信道的输入/输出是否是确定关系可分为：
有噪声信道、无噪声信道
- - 根据信道的统计特性是否随时间改变可分为：
平稳信道（恒参信道、时不变信道）
 非平稳信道（变参信道、时变信道）
- - 根据输入/输出的个数可分为：
单用户信道：一个输入一个输出单向通信。
多用户信道：双向通信或三个或更多个用户之间相互通信的情况。
![离散信道数学模型](https://qncdn.oleehu.xyz/blog/%E7%A6%BB%E6%95%A3%E4%BF%A1%E9%81%93%E6%95%B0%E5%AD%A6%E6%A8%A1%E5%9E%8B.jpg?img)

$i = 1 , 2 , \cdots , r;j= 1 , 2 , \cdots , s \\ 满足：0 \leqslant p ( y _ { j } | x _ { i } ) \leqslant 1 ( i = 1 , 2 \cdots r ; j = 1 , 2 \cdots s)\\ \sum _ { j = 1 } ^ { s } p ( y _j | x _ { i } ) = 1 ( i = 1 , 2 , \cdots r )$
- **二元对称信道**（BSC：binary symmetric channel)
输出符号集 $A = \{ 0 , 1\}$,输出符号集 $B = \{ 0 ,1\}$，r=s=2.\
传递概率：  $$p( 0 | 0 ) = \overline { p }\\p(0|1)=p  →
\begin{bmatrix}
\overline { p } & p \\
p & \overline { p } \\
\end{bmatrix} 
\\
p(1|0)=p\\
p( 1 | 1 ) = \overline { p }$$
- **二元删除信道输入符号集** $A = \{ 0 , 1 \}$，符号输出集$B = \{ 0 , ? ,1\},r=2,s=3$
信道矩阵为$$p=\begin{bmatrix}
p & 1-p & 0 \\
0 & 1-q & q \\
\end{bmatrix} $$
- 信息传输率R:信道中平均每个符号所传送的信息量。
- 平均互信息$I(X;Y)$:是接收到符号Y后平均获得的关于X的信息量。
- 信道的信息传输率本质就是平均互信息：$R=I(X;Y)$(比特/符号)
- 信道每秒钟平均传输的信息量为：信息传输速率$R_t$
$R_t=I(X;Y)$(比特/秒)
- 最大的信息传输率为信道容量：$C=max_{p(x)}{I(X;Y)}$ (比特/符号)	相应的输入概率分布被称为最佳输入分布。
- 信道容量性质：
- - 与信源的概率分布无关。
- - 描述信道特性的参量；
- - 信道能够传输的最大信息量。
- 无噪无损信道：输入、输出之间有确定的一一对应关系$$P ( y _j| x_i ) = \left\{ \begin{aligned} 1 ; y _ { j } = f ( x _ { i } ) \\ 0; y _ { j } \neq f ( x _ { i } ) \end{aligned} \right.\\I ( X ; Y ) = H ( X ) = H ( Y )\\C = max_{p(x)} I ( X ; Y ) = m a x_{p(x)} H ( X ) = \log r$$
- 行对称信道：信道矩阵P中每行都是第一行的排列。
- 对称信道：信道矩阵中每行都是第一行的排列，每列都是第一列的排
- 强对称信道：
- - 特征：
行列对称。
信道输入与输出消息（符号）数相等，$r=s$。
错误分布是均匀的：信道矩阵中正确传输概率都相等，且错误传输概率均匀地分配到$r-1$个符号上
$$P=
\begin{bmatrix}
\overline { p } & \frac { p } { r-1 } &{\cdots}&\frac { p } { r-1 } \\
\frac { p } { r-1 } &\overline { p }&{\cdots}&\frac { p } { r-1 } \\
{\vdots}&{\vdots}&{\ddots}&{\vdots}\\
\frac { p } { r-1 } &\frac { p } { r-1 } &{\cdots}&\overline { p }\\
\end{bmatrix} 
$$
- 重要引理：对于对称信道，当信道输入概率分布为等概分布时，输出概率分布必为等概分布。此时到达信道容量。
$C = \log s - H ( p _ { 1 }^ { \prime }  , p _ { 2 } ^ { \prime } \cdots p _ { s } ^ { \prime } )$
其中 $p _ { 1 }^ { \prime }  , p _ { 2 }^ { \prime }  \cdots p _ { s } ^ { \prime }$是信道矩阵中的任意一行中的元素。
- 信源编码目的：
使信源适合于信道的传输，用信道能传输的符号来代表信源发出的消息。
在不失真或允许一定失真的条件下，用尽可能少的符号来传递信源消息，提高信息传输率。
- 信源编码作用：
以提高通信有效性为目的。通常通过压缩信源的冗余度来实现。
![信源编码模型](https://qncdn.oleehu.xyz/blog/%E4%BF%A1%E6%BA%90%E7%BC%96%E7%A0%81%E6%A8%A1%E5%9E%8B.jpg?img)
码字$w _ { i } = x _ { i _1} x _ { i_2 } \cdots x _ { i _i}$
将信源符号集中的符号S~i~(或者长为N的信源符号序列)映射成由码符号（码元)x~i~组成的长度为l~i~的一一对应的码符号序列w~i~

- 分组码与非分组码：
将信源符号集中的每个信源符号 $S _ { i }$,固定的映射成某一个码字 $w_ { i }$ ,这样的码称为分组码

- 奇异码与非奇异码：
分组码中所有码字不同，则为非奇异码。

- 唯一可译码与非唯一可译码：
码符号序列被唯一地译为对应的信源符号序列，则称为唯一可译码。

- 即时码与非即时码：
若某个唯一可译码在接收到一个完整的码字时无需参考后续的码符号就能立即译码，则称此码为即时码。

定理：即时码的充要条件：任何一个码字都不是其它码字的前缀。
$$
码=\left\{ \begin{aligned} 非分组码\qquad\qquad\qquad\qquad\qquad\qquad\qquad\\分组码\left\{ \begin{aligned}奇异码\qquad\qquad\qquad\qquad\qquad\qquad\\非奇异码\left\{ \begin{aligned} 非唯一可译码\qquad\qquad\\唯一可译码\left\{ \begin{aligned} 即时码\\非即时码\end{aligned} \right.\end{aligned} \right.\end{aligned} \right.\end{aligned} \right.
$$
对于定长码，非奇异码一定是唯一可译码。
设信源符号集中共有q个符号，$s =\{s_1,s_2 …s_q\}$
码符号集中共有r种码元，$x=\{x_1,x_2…x_r\}$
定长码码长为1，则要满足非奇异性必然有:$q≤r^l$
如果对N次扩展信源进行S^N^定长编码，要满足非奇异性，须满足条件$q^N≤r^l$
- Kraft定理:即时码存在的充要条件是$\sum_{i=1}^qr^{-l_i}\leq1$
- McMillan定理:唯一可译码存在的充要条件是$\sum_{i=1}^qr^{-l_i}\leq1$
说明:
当满足Kraft(或McMillan)不等式时，必然可以构造出即时码(或唯一可译码)，否则不能构造出即时码(或唯一可译码)。
该定理不能作为判断一种码是否是即时码(或唯一可译码)的判断依据。
- 平均码长
 $\overline L=\sum_{i=1}^qp(s_i)l_i$ 码符号/信源符号
对于给定的信源和码符号集，若有一个唯一可译码，其平均长度小于所有其他唯一可译码，则称这种码为紧致码或最佳码。
- 平均码长界限定理
设离散无记忆信源的熵为H(S)，用r个码符号进行编码，则总可找到一种无失真信源编码，构成唯一可译码，使其平均码长满足:
$$\frac{H(S)}{\log r}\leq \overline L < \frac{H(S)}{\log r}+1$$
平均码长=下限值:$p(s_i)=r^{-l_i}\;(i= 1,2...q)$
结论:变长编码过程中，大概率消息用较短的码字表示，小概率消息用较长的码字表示，通过概率匹配可降低平均码长。
- 香农第一定律
设离散无记忆信源的熵为H(S)，它的N次扩展信源为S^N^，对扩展信源S^N^进行编码。总可以找到一种编码方法，构成唯一可译码，使平均码长满足
$$\frac{H(S)}{\log r}\leq \frac{\overline L_N}{N} < \frac{H(S)}{\log r}+\frac1N$$
当$N→\infty$时，有$\lim\limits_{ N \rightarrow \infty }\frac{\overline L_N}{N}=H_r(S)$
信息传输率(码率):$R=H(X)=\frac{H(S)}{\overline L}\;\;\;\;\overline L=\frac{\overline L_N}{N}$
- 编码效率：$\eta =\frac{R}{\log r}=\frac{H(S)/\overline L}{\log r}$
平均码长压缩下限与信源熵有关。
- **费诺码**
- - 编码步骤如下:
将概率按从大到小的顺序排列，令$p(s_1) ≥ p(s_2) ≥ ... ≥p(s_q)$
将依次排列的信源符号按概率分成两组，使每组概率和尽可能接近或相等。
给每一组分配一位码元“0”或“1”。
将每一分组再按同样方法划分，重复步骤2和3，直至概率不再可分为止
费诺码比较适合分组概率相等或者接近的信源编码
- **Huffman码**
- - 编码步骤:
将信源符号按概率从大到小的顺序排列，令$p(s_1) ≥ p(s_2) ≥ …. ≥p(s_q)$
将概率最小的信源符号S~n-1~和S~n~合并成一个新符号并分配一个码元“0”和“1”，用两个最小的概率之和作为新符号的概率，得到一个只包含(n一1)个信源符号的新信源。
将缩减信源概率从大到小顺序排列，重复步骤2，得到只含(n一2)个符号的缩减信源。
重复步骤，直至信源只剩两个符号，从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。
- - 二元Huffman编码特点:
码长与概率是相匹配的
是紧致码、最佳码，平均码长最短，编码效率高。
平均码长未必打到编码定理的下界。(条件:$P_i=2^{-l_i}$)
霍夫曼码需要信源统计特性才能编码。
需要进行差错检测(会降低信息传输有效性)。
- 信道编码概述
- - 目标:
提高通信的可靠性:信道传输错误率最低，信息传输率最高。错误概率与信道统计特性、译码规则有关。
- - 方法:
按照一定的规则给信源编码后的码符号序列增加一些冗余信息，使其变成具有一定数学规律的码符号序列。信道译码，就是按与信道编码器相同的数学规律去掉接收到的码符号序列中的冗余符号。
- - 存在问题:
增加的冗余符号越多，检错和纠错能力就越强。但是，增加的冗余符号越多，传输效率就越低。
- 两种重要的译码规则
- - 最大后验概率(最小错误概率、最优)译码规则(MAP):步骤:
(转移概率矩阵每行乘以P(x)得到联合概率分布矩阵;
每列矩阵最大概率对应的输入概率X作为译码规则。
所有译码结果对应联合概率之和为正确概率，矩阵其余元素之和为错误概率。
- - 极大似然译码规则(ML)步骤:
以转移概率矩阵每列中最大的元素对应的xi作为译码规则。所有译码规则对应转移概率之和乘以一作为正确概率。

说明:当输入符号等概分布时，采用极大似然译码准则等价于最大后验概率准则，平均译码错误概率最小。

- **汉明距离**
概念: 设$X_i=x_{i1}x_{i2}…x_{in}$和 $Y_j=y_{j1}y_{j2}…y_{jn}$ 表示两个长度为n的码符号序列，
定义: $D(x_i,y_j)=\sum_{k=1}^n x_{ik} \bigoplus y_{jk}$
称D(x~i~,y~j~)为码字x~i~和y~j~之间的汉明距离。(两序列符号相异的个数)
- - 最小汉明距离译码准则:
最小码距D~min~越大，则平均错误概率P~E~越小，在选择编码规则时，应使码字之间的距离D~min~越大越好，这样的准则即为最小距离译码准则
编码可纠正u个以内错误充要条件:$D_{min}=2u+1$
编码可检测t个以内错误充要条件:$D_{min}=t+1$
- 香农第二定理
- - 内容:对于离散无记忆平稳信源。信道容量为c若编码速率R<C若码长足够大，至少存在一种编码使得译码错误概率任意小，反之，若编码速率R>C，则码长无论多长，也找不到使得译码错误概率任意小的编码。
- - 说明:
高可靠性:译码错误概率任意小。
高效率:信息传输速率接近信道容量。
存在这中编码必要条件R<C
- - 与香农第一定理的对比:
信源编码部分介绍香农第一定理:实现无失真信源编码时平均码长压缩下限为信源熵。
信道编码部分介绍香农第二定理:实现高可靠性信道编码的信息率极限是信道容量。

两数之和

用 Docker 安装 SystemC 环境

行人可控交通灯控制系统的设计

目 录

目录