信息论与编码课程笔记
信息论与编码
第一章 信息论与编码理论概述
信息论与编码理论概述
自从汉明码开始，各种信道编码获得了长足的发展，如
- 格雷码，Reed-Muller码，循环码，Reed-Solomon码,BCH码
- 卷积码，Turbo码，LDPC码，Polar码
- 级联码，网格编码调制，代数几何码
- 编织卷积码，纠删码，空时码
- 网络编码，量子纠错码，二维码
- 基于信息论与编码理论的安全技术
编码机制
- 编码：信息从一种形式或格式转换为另一种形式的过程。
- 编码机制：用预先规定的方法将文字、数字或其它对象编成数码，或将信息、数据转换成规定的电脉冲信号。
信源编码
目的：提高通信的有效性，即以更少的符号来表示原始消息
通过减少消息符号序列中的冗余度，提高平均信息量
随机错误
- 随机错误：接收序列中的传输错误是随机出现的。
- 随机错误信道：这样的信道称为随机错误信道。
突发错误
突发错误：不同状态特性下，错误出现的概率不一样，这种错误为突发错误。
纠错码
目的：检测和纠正由于非人为(自然)因素引起的传输错误
设计机制：通过对消息符号序列加入冗余信息，使得接收方收到信号后，可以通过这些冗余信息进行检错和纠错
数字通信系统的组成及各种信道
数字通信系统模型
无记忆信道和有记忆信道
无记忆信道：如果在给定时间间隔上，检测器的输出只与在该时间间隔上传送的信号有关，而与任何前面时间的传送的信号无关，称此信道为无记忆信道。该信道可以用如下公式表示：
$$
P(Y/X)= \prod_n p(y_n/x_n)
$$
有记忆信道：一种M元输入、Q元输出的信道模型。该信道可以用如下公式表示：
$$
P(y_n/x_{n-k+1},…,x_{n-1},x_n)
$$
离散无记忆(DMC)信道
是一种M元输入、Q元输出的信道模型。
条件概率P(Y/X)是描述该信道的最好方式，也叫做转移概率，其中X表示调制器输入符号，Y表示解调器输出符号，P(Y/X)表示发送为X接收为Y的概率。
二元对称(BSC)信道
信道矩阵：一个信道也可由它的转移概率组成的矩阵来表示。
信道矩阵
一般离散单符号信道的信道矩阵为：
$$
\begin{bmatrix} P(b_1|a_1) & P(b_2|a_1) & \dots & P(b_s|a_1) \ P(b_1|a_2) & P(b_2|a_2) & \dots & P(b_s|a_2) \ \vdots & \vdots & \ddots & \vdots \P(b_1|a_r) & P(b_2|a_r) & \dots & P(b_s|a_r) \end{bmatrix}
$$
加性高斯白噪声(AWGN)信道
- 加性噪声：叠加在信号上的一种噪声。
- 白噪声：噪声的功率谱密度在所有的频率上均为一常数。
- 高斯白噪声：白噪声取值的概率分布服从高斯分布，其自相关系数为无延时的冲击函数。
通信系统涉及的一些基本概念
信息传输率
- 符号传输率：为1/T，每T秒传输一个编码符号，即单位时间内传输的符号个数。
- 码速率：编码后的数据流中有用部分的比例，对于(n,k)线性分组码，码速率为R=k/n，即k个信息比特对应于传送n个符号。
- 信息传输率(数据率)：在编码系统中，若码速率是R=k/n，则信息传输率(数据率)为R/T(bit/s)。
信道带宽
除了噪声的作用造成信号改变外，所有的通信系统都会因为带宽有限而造成信号失真。
- 最小信道带宽：为基本保证信号不因带宽原因而失真，粗略估计等于W=1/(2T)(Hz)。
- 未编码系统：数据率1/T=2W，受到带宽影响。
- 二元编码系统：数据率R/T=2RW。同未编码系统相比，若要保持数据率不变，则要求带宽扩展1/R倍。
AWGN信道的分组编码系统
译码器的条件错误概率：已知接收序列Y时
$$
P_e(H_m/Y),P_e(X_m/Y)
$$
译码器的错误概率：
$$
P_e(H_m)=P_e(X_m)=\sum_Y P_e(X_m/Y)P(Y)
$$
最佳译码规则和最大后验概率译码
最佳译码规则：能够使译码错误概率P(E)达到最小的译码规则
由于接收序列Y是译码前产生的，所以P(Y)与译码规则无关
最佳译码规则必须对所有Y，使得
$$
P(E/Y)\cong P(Y \neq X/Y)
$$`最小，即 P(Y=X/Y) 最大。
最大后验概率译码：对于每个输入Y，如果译码器能在码字集合中选择一个码字，作为发送码字的估值，并且使P(X/Y)最大，则这种译码规则一定能使译码器输出的错误概率最小。
似然函数
Bayes公式：
$$
\uparrow P(X/Y)=\frac{P(Y/X)P(X)}{P(Y)} \公式(1)
$$
- 对于给定的Y，可选择能使公式(1)右边最大的向量作为X的估计值。
- 如果所有码字都是等可能的，即P(X)是常数，那么公式(1)左边最大，就推导出P(Y/X)最大。
- P(Y/X)：叫做似然函数、信道转移概率。
最大似然译码
定义：若能在码字集合选择合适的码字X，使得P(Y/X)最大，则这种译码规则被称为最大似然译码。
对数似然函数：由于lnx与x是单调关系，故有lnP(Y/X)。
对于离散无记忆信道，由于
$$
P(Y/X)=\sum_n P(y_i/x_i)
$$所以
$$
\ln P(Y/X)=\sum_n \ln P(y_i/x_i)
$$MLD：对应的译码器称为最大似然译码器。
MLD规则：是最为可行的一种译码规则。
对于DMC和BSC信道是一种最佳译码准则。但是在某些情况下并不是最佳的译码规则，如当发送端不是以等概率发送码字的时候。
BSC信道的最大似然译码
$$
P(y_i/x_i)=\begin{cases} 1-p& y_i=x_i\p& y_i\neq x_i \end{cases}
$$
Y为二元序列，用d(Y, X)表示Y和X之间的距离，即不同位数的个数
$$
\ln P(Y/X)=d(y,X)\ln p+(n-d(Y,X))\ln (1-p) =\ d(Y,X)\ln \frac {p}{1-p} +n\ln(1-p)
$$
即想要P(Y/X)最大，则需要d(Y, X)最小
最小距离译码器：在BSC中，MLD规则变成了选择能使Y和X之间的汉明距离为最小的向量，作为码字X的估计值
数据安全中的数学问题
语义
语法：01比特
语用
信道编码
y=Ax+b mod q
分组码
循环码
卷积码
LDPC码
有低密度的稀疏矩阵，就表示是LDPC码
压缩感知
y=Ax+b
如果x稀疏，A满足一定的条件，通过y A可以找到x
由于A不可逆，无法通过求找到x
现实中的x一般并不稀疏，进过一个变化之后，再一组正交基上可以进行稀疏表示
矩阵A与x维数不匹配
格密码，编码，压缩感知都有对测量矩阵尺寸多样性的需求
半张量积压缩感知
$$
y=a\ltimes x+b
$$
第二章 信息论基础与信源编码理论
信息的定义：信息是事物运动状态或存在方式不确定性的描述
自信息
定义：考虑离散随机变量X，其样本空间为{xi, i=1, 2,…,n}，则事件X=xi的自信息的定义为
$$
I(x_i)=log(\frac{1}{P(x_i)})=-logP(x_i)
$$
自信息的单位由对数的底来决定，以2为底，单位就是比特(bits)，以e为底就是奈特(nats)。自信息非负。
互信息
定义： xi和yi之间的互信息定义为
$$
I(x_i;y_i)=log(\frac{P(x_i|y_i)}{P(x_i)})
$$
互信息的性质：
性质1：互易性 I(xi;yi)= I(yi;xi)。
性质2：当xi和yi是统计上独立的，即P(xi|yi)= P(xi)，则I(xi;yi)=0。
性质3：互信息量可以是正的，也可以是负的。
思考题：计算二元对称(BSC)信道的互信息量?
计算二元对称信道（Binary Symmetric Channel，BSC）的互信息量（Mutual Information）可以使用以下的LaTeX公式表示：
I(X;Y)=H(Y)−H(Y∣X)
其中：
I(X;Y) 表示信道输入 X 和输出 Y 之间的互信息量。
H(Y) 表示接收端输出 Y 的熵（Entropy），可以用以下公式计算：
$$
H(Y) = -\sum_{i=1}^{2} P(Y=y_i) \cdot \log_2(P(Y=y_i))
$$这里的 y1 和 y2 分别表示接收到的0和1的可能性，P(Y=yi) 是接收到符号 yi 的概率。
H(Y∣X) 表示在已知输入 X 的条件下，接收端输出 Y 的条件熵（Conditional Entropy），可以用以下公式计算：
$$
H(Y|X) = -\sum_{i=1}^{2} \sum_{j=1}^{2} P(X=x_j, Y=y_i) \cdot \log_2\left(\frac{P(X=x_j, Y=y_i)}{P(X=x_j)}\right)
$$对于二元对称信道（BSC），错误概率 p 相等，即 P(Y=0∣X=1)=P(Y=1∣X=0)=p，而 P(Y=0∣X=0)=P(Y=1∣X=1)=1−p。因此，可以使用这些概率值来计算上述公式中的各项。
平均自信息量(信息熵)
定义：离散随机变量X的平均自信息定义为，其样本空间为{xi, i=1, 2,…,n}，则事件X=xi的平均自信息量的定义为
$$
H(X)=E{log(\frac{1}{P(x_i)})}=\sum^n_{i=1}P(x_i)I(x_i)=-\sum^n_{i=1}P(x-_i)logP(x_i)
$$
其中H(X)表示每个信源符号的平均信息量。
平均条件自信息量(条件熵)
定义：平均条件自信息H(X|Y)定义为
$$
H(X|Y)=\sum^n_{i=1}\sum^m_{j=1}P(x_iy_i)log\frac{1}{P(x_i|y_i)}
$$
思考题：计算二元对称(BSC)信道的平均条件自信息量(条件熵)?
无失真信源编码
等长信源编码定理
定理: 一个熵为H(X)的离散无记忆信源，若对信源长为N的符号序列进行等长编码，设码字是从r个字母的码符号集合中，选取l个码元组成。对于任意的ε>0，只要满足
$$
\frac{l}{N}\geq \frac{H(X)+\varepsilon}{log\gamma}
$$
则当N足够大时，可实现几乎无失真编码，即译码错误概率可为任意小。
变长码
| 字母 | 码字 | 字母 | 码字 |
|---|---|---|---|
| A | 0 | E | 10 |
| B | 1 | F | 11 |
| C | 00 | G | 000 |
| D | 01 | H | 111 |
若对字母序列ABADCAB进行编码，则得到0 1 0 01 00 0 1
译码不唯一：可能被译为DADAAAB(01 0 01 0 0 0 1)
或者AEDGB(0 10 01 000 1)
注：变长码必须是惟一可译码，才能实现无失真编码。
变长信源编码定理
定理:一个熵为H(X)的离散无记忆信源，并有r个码元的码符号集合，总可以找到一种无失真编码方法，构成惟一可译码，使其平均码长满足
$$
\frac{H(X)}{logr}\leq\bar{L}<\frac{H(X)}{logr}+1
$$
则当N足够大时，可实现几乎无失真编码，即译码错误概率可为任意小。
信道的信息传输率
变长信源编码定理中的极限值H(X)/logr同等长信源编码定理中的极限值是一致的。
定义：信道的信息传输率(码率)为
$$
R=\frac{H(X)}{logr}
$$
得到编码后信道的信息传输率为
$$
R\le\bar{L}
$$
经典的信源编码方法
信源编码—霍夫曼(Huffman)编码
一个离散无记忆信源有7个符号xi, i=1,..,7，P(X=x1)=0.37, P(X=x2)=0.33, P(X=x3)=0.16, P(X=x4)=0.07, P(X=x5)=0.04, P(X=x6)=0.02, P(X=x7)=0.01, 将7个信源符号按照概率递减的顺序进行排序，构造如图8所示的霍夫曼树。
按照编码路径从后往前返回，就得到对应的码字x7=111111, x6=111110, x5=11110, x4=1110，x3=110, x2=10，x1=0。
思考题：如何编程序实现霍夫曼编码?
- 构建霍夫曼树：
- 统计输入数据中每个字符的频率。
- 创建叶子节点，每个叶子节点代表一个字符，并将频率作为节点的权重。
- 将叶子节点放入一个优先队列（最小堆）中，以便频率最低的节点位于队列的前面。
- 重复以下步骤，直到只剩下一个节点为止：
- 从队列中弹出两个频率最低的节点。
- 创建一个新的节点，其权重等于这两个节点的权重之和。
- 将新节点插入队列中。
- 最后队列中剩下的节点就构成了霍夫曼树。
- 生成霍夫曼编码：
- 遍历霍夫曼树，从根节点开始，分别向左和向右遍历树的边。
- 每次向左移动时，将编码中添加一个 0，每次向右移动时，将编码中添加一个 1。
- 当到达叶子节点时，您就得到了字符的霍夫曼编码。
- 构建编码表：
- 将每个字符与其对应的霍夫曼编码存储在一个编码表中，以便在编码和解码过程中使用。
- 编码和解码：
- 使用编码表将输入数据编码为霍夫曼编码。
- 使用霍夫曼树将霍夫曼编码解码为原始数据。
游程编码
游程：信源输出的字符序列中，各种字符连续的重复出现的字符串的个数。
游程编码：就是将这种字符序列映射成字符串的长度和字符串的位置的标志序列。
游程编码常用作图形文件的编码方式，如.bmp和.tiff。
例子：考虑比特序列11111111111111100000000000000000001111，可以被表示成(15,1),(19,0),(4,1)，字符最长的重复的数目为19，因此，把该比特序列编码为(01111,1), (10011,0), (00100,1)，此时压缩率为18:38=1:2.11。
思考题：如何编程序实现游程编码?
- 统计字符频率：
- 首先，需要扫描输入文本并统计每个字符的频率。这是构建霍夫曼树的基础，因为频率高的字符将具有较短的编码。
- 构建霍夫曼树：
- 基于字符频率，构建霍夫曼树。通常，使用一个优先队列（最小堆）来管理节点，每个节点代表一个字符及其频率。在构建过程中，反复合并两个最小频率的节点，创建一个新的节点，并将其插入回队列，直到队列中只剩下一个节点，即根节点，表示整个霍夫曼树已构建完成。
- 生成霍夫曼编码：
- 遍历霍夫曼树，从根节点开始，每当沿着左子树移动时添加0，沿着右子树移动时添加1。当到达叶子节点时，记录下当前路径所对应的字符的编码。
- 构建编码表：
- 将每个字符和它对应的霍夫曼编码存储在一个编码表中，以便在编码和解码过程中使用。
- 编码文本：
- 使用编码表将输入文本中的字符编码为霍夫曼编码。
- 解码文本：
- 使用霍夫曼树将霍夫曼编码解码为原始文本。
LZ(Lemple-Ziv)编码
分段的方法：1)游程先取第一个符号作为第一段，然后再继续分段；2)若有出现与前面符号一样时，就再添加紧跟后面的一个符号一起组成一段；3)尽可能取最少个连着的符号并保证各段都不相同；4)以此类推，直至信源符号序列结束。
编码方法：首先去掉最后一个符号，然后看剩下的字符串在字典中的排序，这个排序值转换成二进制数作为指针X的值，最后一个信源符号作为码字第2项d的值，即得到码字(X, d)。
例子：考虑比特序列101011011010101011，根据上面的编码方法可把该比特序列分段为1, 0, 10, 11, 01, 101, 010, 1011。
码字为：(000,1),( 000,0), (001,0), (001,1), (010,1), (011,1), (101,0), (110,1)。
思考题：如何编程序实现LZ编码?
- 初始化字典：创建一个空的字典，其中包含所有可能的单个字符作为初始词条。
- 扫描输入数据：从左到右扫描输入数据，逐步构建编码输出。开始时，当前扫描位置指向输入数据的第一个字符。
- 查找最长匹配：在字典中查找与当前扫描位置匹配的最长字符串（前缀），这个字符串必须存在于字典中。如果找到匹配，就将扫描位置移动到匹配字符串的末尾，否则将当前字符作为一个字典词条。
- 输出编码：将匹配字符串的索引（或编码）输出到结果中，并将匹配字符串后的字符作为下一个字典词条的一部分。
- 更新字典：将新的字典词条添加到字典中，以便下次匹配时使用。
- 重复步骤3到步骤5，直到扫描完成整个输入数据。
纠错码的理论基础
信道容量
定义：考虑某种概率分布为P(x)的离散无记忆信源，对于一个固定的信道，信道容量被定义为最大的平均互信息，此时传输每个符号平均获得的信息量最大，即对于每个固定的信道可以达到最大的信息传输率，即
$$
C=\max_{P(X_j)}I(X;Y)=\max_{P(X_J)}\sum^{q-1}{j=1}\sum^{r-1}{i=o}P(x_j)P(y_i|x_j)\log \frac {P(y_i|x_j)}{P(y_i)}
$$
其约束条件为
$$
P(x_j)\ge0\ ,\sum^{q-1}_{j=0}P(x_j)=1
$$
思考题：如何计算给定某种信道的信道容量?
确定信道模型：首先，需要明确定义所使用的信道模型。不同的信道（例如二进制对称信道、高斯信道、无线信道等）具有不同的数学表示和特性。你需要了解信道的概率分布和噪声性质。
计算信道容量：使用香农-哈特利定理来计算信道容量。该定理的公式如下：
$$
C+B·\log_2(1+SNR)
$$其中，
- C 表示信道容量（比特每秒，bps）。
- B 表示信道的带宽（赫兹，Hz），它表示信号传输的频率范围。
- SNRSNR 表示信噪比，定义为信号功率与噪声功率之比。通常以对数（以分贝为单位）表示。
SNR计算：计算信噪比（SNR）是信道容量计算的关键。SNR的计算方式取决于信道的特性。例如，在高斯信道中，SNR通常表示为信号功率与噪声功率之比。
确定带宽：带宽（B）是信号传输的频率范围，通常以赫兹（Hz）表示。带宽的选择与具体的通信系统和应用有关。
纠错编码的理论基础
香农编码定理：如果系统的传输率小于信道容量，那么适当选择编码技术就能实现可靠通信，即可以将差错率减小到任意小的程度。
信道编码定理
定理：假设DMS有信源字符集X，熵为每信源符号H(X)比特，而且信源每Ts秒产生一个符号，那么信源的平均信息率为每秒H(X)/Ts比特，假设信道可以每Tc秒使用一次，而信道容量为每次信道使用C比特，那么每单位时间的信道容量为每秒钟C/Tc比特。如果H(X)/Ts≤ C/Tc，那么就存在编码方案使得在有噪声的信道上传输的信源消息，能够以任意小的错误概率进行恢复。
第三章 线性分组
分组码
分组码：将消息序列分组进行编码
每组消息u有k个信息位，共有$2^k$个不同的消息
码字：编码器按照一定规则将每个输入消息u变换成二元n重v，n>k，这个二元n重v称作消息u的码字或码矢。
所有$2^k$个码字组成的集合称作是分组码
为什么在分组码中码字的个数是$2^k$个?
当编码字的位数是$2^k$时，这些码字可以更容易地排列成矩阵，例如二维数组，以便进行操作和计算。这种排列方式在编码和解码时通常更加高效。
线性分组码
线性分组码即具有线性性质的分组码
定义：长为n，有$2^k$个码字的分组码，当且仅当其$2^k$个码字构成GF(2)上所有n重矢量空间的一个k维子空间时，称作线性(n, k)分组码。
生成矩阵
∵ 线性(n,k)分组码C是一个k维子空间
∴ 在码C中能找到k个线性独立的码字$g_0, g_1,…, g_{k-1}，$使得C中的每个码字v都是这k个码字的一种线性组合，即 $v=u_0g_0+u_1g_1+…+u_{k-1}g_{k-1}$
生成矩阵：将k个线性独立的码字作为行，得到k×n阶矩阵
$$
G=
\begin{pmatrix}
g_0\g_1\ \vdots \g_{k-1}
\end{pmatrix}=\begin{pmatrix}
g_{00}&g_{01}&\dots&g_{0n-1}\g_{10}&g_{11}&\dots&g_{1n-1}\ \vdots \g_{(k-1)0}&g_{(k-1)1}&\dots&g_{(k-1)n-1}
\end{pmatrix}
$$
一致校验(监督)矩阵
∵ (n,k)线性码有r(r=n-k)个校验码元
∴ 必须有r个独立的线性方程
对于任一码字c, 有cHT=0
$∵c=iG\
∴ GH^T=0$
校验矩阵：该矩阵由r行n列组成，即
$$
H=\begin{pmatrix}
h_{1,n}&h_{1,n-1}&\dots&h_{1,1}\h_{2,n}&h_{2,n-1}&\dots&h_{2,1}\ \vdots \h_{r,n}&h_{r,n-1}&\dots&h_{r,1}
\end{pmatrix}
$$
一致校验矩阵的标准形式：经过初等变换，得到$H=[Q I_r]$
线性系统分组码
定义：若(n,k)线性分组码C的生成矩阵形如$G=[P I_k]$或$G=[I_k P])$，此时称C为线性系统分组码。
$$
G=
\begin{pmatrix}
g_0\g_1\ \vdots \g_{k-1}
\end{pmatrix}=[P \ I_k]=\begin{pmatrix}
p_{0,0}&p_{0,1}&\dots&p_{0,n-k-1}& \vdots&1&0&0&\dots&0 \p_{1,0}&p_{1,1}&\dots&p_{1,n-k-1}& \vdots&0&1&0&\dots&0 \ p_{2,0}&p_{2,1}&\dots&p_{2,n-k-1}& \vdots&0&0&1&\dots&0\ \vdots\ p_{k-1,0}&p_{k-1,1}&\dots&p_{k-1,n-k-1}& \vdots&0&0&0&\dots&1
\end{pmatrix}
$$
此时，如果用任意消息u同G做乘法，就会发现每个码字都可以被分成两个部分：消息部分和冗余部分
一致校验方程
对于线性系统分组码
$$
v=u·G=(u_0,u_1,\dots,u_{k-1})·\begin{pmatrix}
p_{0,0}&p_{0,1}&\dots&p_{0,n-k-1}& \vdots&1&0&0&\dots&0 \p_{1,0}&p_{1,1}&\dots&p_{1,n-k-1}& \vdots&0&1&0&\dots&0 \ p_{2,0}&p_{2,1}&\dots&p_{2,n-k-1}& \vdots&0&0&1&\dots&0\ \vdots\ p_{k-1,0}&p_{k-1,1}&\dots&p_{k-1,n-k-1}& \vdots&0&0&0&\dots&1
\end{pmatrix}
$$
对应于消息$u=(u_0,u_1,\dots,u_{k-1})$的码字是$v=(v_0,v_1,\dots,v_{n-1})=u·G$，即$v_{n-k+i}=u_i , 0≤i≤k-1$
$v_j=u_0p_{0j}+u_1p{1j}+…+u_{k-1}p_{k-1j}, 0≤j≤n-k-1$
上面两个式子正好反映系统的组成特性，最后这n-k个方程称为码C的一致校验方程。
对偶码
定义：令S是$V_n$的k维子空间，并令$S_d$是$V_n$中这样矢量的集合，即对S中的任意u和$S_d$中的任意v，有u·v=0，则$S_d$也是$V_n$的一个子空间，它称为S的对偶空间或零化空间。
定理：令S是$V_n$中的一个k维子空间，则S的对偶空间的 维数是n-k。
对偶码：以H为生成矩阵得到的(n,n-k)码称为码C的对偶码,记为$C_d$。
系统码的一致校验矩阵
若码C的生成矩阵具有系统形式$G=[P I_k]$或$[I_k P]$，则其一致校验矩阵形如H=$[I_{n-k} P^T]$或$H=[P^T I_{n-k}]$。
伴随式
伴随式：当接收到r后，译码器计算下述n-k重$S=r·H……T =(s_0, s_1,…, s_{n-k-1})$则称S为r的伴随式。
当且仅当是一个码字(即无传输错误)时有S=0，否则错误矢量本身就是一个码字，此时出现了不可检错误。只要码C设计适当，就几乎不会出现不可检错误。
伴随式纠错
根据伴随式定义， 我们有$S=r·H^T =(v+e)·H^T=v·H^T+e·H^T=e·H^T$
可以看出，伴随式是错误图样的组合，即伴随式包含了一定程度的错误图样信息，因而可以用来纠错——伴随式纠错。
考虑某(7,3)码，该码的生成矩阵G和H为
$$
G=\begin{pmatrix} 0&1&1&1&1&0&0\ 1&0&1&1&0&1&0\ 1&1&1&0&0&0&1\end{pmatrix}, H=\begin{pmatrix} 1&0&0&0&0&1&1\ 0&1&0&0&1&0&1\ 0&0&0&1&1&1&0\ 0&0&0&1&1&1&0\end{pmatrix}
$$令u=(101),v=(1001101)是发送码字，r=(0001101)是接收矢量，收到r后首先计算S=r·HT =(1000)≠0，由伴随式和错误图样的关系方程有：1=e0+e5+e6, 0=e1+e4+e6, 0=e2+e4+e5+e6, 0=e3+e4+e5, 则得到23=8个错误图样(1000000), (1010111), (1101011), … …, 其中(1000000)是非零分量最少的图样，考虑BSC信道，则(1000000)是最为可能的错误矢量，因而确定v=r+e=(0001101)+ (1000000)=(1001101)
汉明重量
汉明重量：令v=(v0, v1,…, vn-1)是二元n重，v的汉明重量w(v) 定义为v中非零分量的个数。
举例：设有两个码字{0100,1111},则它们的汉明重量为 w(0100)=1, w(1111)=4
重量分布：对于码长为n的一个分组码, 不同的码字可能具有 相同的汉明重量, 若记Ai为该码中汉明重量为i的码字个数, 称{A0, A1,…, An}是该码的重量分布。
汉明距离
定义：令u=(u0, u1,…, un-1)和v=(v0, v1,…, vn-1)是两个二元n重， 则u和v之间的汉明距离d(u, v)定义为u+v的汉明重量。
举例：设有两个码字{0100,1111},则它们的汉明距离 d(0100, 1111)=3
汉明距离的性质：
- 非负性，d(u, v)≥0；
- d(u, v)=0，当且仅当u=v的时候；
- 对称性： d(u, v) =d(v, u) ；
- 三角不等式： d(u, v)+d(v, w)≥d(u, w)
距离分布
定义：在(n,k)码中，任意两个码字之间都有一个汉明距离， 两组不同码字之间可能有相同的汉明距离。若记 Di(0≤i≤n)为距离为i的码字组数，那么称{D0, D1,…,Dn}为此分组码的距离分布，并且称能够使Di≠0的那个最小整数i为该码的最小码间距离。
特别的，对于线性分组码，有如下定理：(n,k)线性码的最小码间距离等于非零码字的最 小汉明重量。
定理：设(n,k)线性码C的最小码间距离为d，则1)若 d≥t+1，则码C能检测t个随机错误；2)若d≥2t+1 ，则码C能纠正t个随机错误；3)若d≥t+e+1，则 码C能纠正t (t≤e)个随机错误，同时还能检测e个 随机错误。
定理：(n,k,d*)线性码C的最小码间距离d满足d≤n-k+1
定义：若(n,k)线性码的最小码间距离d满足d=n-k+1，那么称 该码为最大距离可分码，简称MDS码。
标准阵
令(n,k)线性码C的所有码字是接收矢量r是一个n重，则按如下的方式构造码C的标准阵：
$$
\begin{bmatrix} v_1=0&v_2&\dots&v_i&\dots&v_{2^k}\ e_2&e_2+v_2&\dots&e_2+v_i&\dots&e_2+v_{2^k}\ e_3&e_3+v_2&\dots&e_3+v_i&\dots&e_3+v_{2^k}\ \vdots \ e_{2^{n+k}}&e_{2^{n+k}}+v_2&\dots&e_{2^{n+k}}+v_i&\dots&e_{2^{n+k}}+v_{2^k}\ \end{bmatrix}
$$
性质1：同一行中任意两个n重之和为一个码字。
性质2：在标准阵中，同一行没有两个n重是相同的，每个n重在且仅在一行中出现。
性质2的证明：
- 假设第l行有2个n重是相同的，如对i≠j有$e_l+v_i=e_l+v_j$，即$v_i=v_j$，这与标准阵的构造相矛盾，故性质2的第一句话得证。
- 首先由定义知每个n重至少出现一次，假设一个n重在第l行和第m行(l<m)都出现，则必存在i，使得该n重等于$e_l+v_i$，且存在j，使得该n重等于$e_m+v_j$，即有$e_m=e_l+(v_i+v_j)=e_l+v_s$，这意味着$e_m$在第l行，这与标准阵的构造定义相矛盾。
陪集
定义：标准阵中共有$2_{n-k}$行，它们称为码C的陪集。
陪集首：每个陪集中的第一个n重$e_i$称为陪集首。陪集中的任 何一个元素都可以作为陪集首，需要做置换操作。
对于一个码字$v_i$, 如果信道造成的错误图样是陪集首, 则接收矢量r在陪集中, 此时, 可以将接收矢量正确的译码为$v_i$; 否则, 若信道造成的错误图样不是陪集首, 则会造成错误译码。
定理：陪集首是可纠正的错误图样，共有2n-k个可纠正的错误图样。
基于标准阵的译码方法
方法：如果接收矢量r落在标准阵中的第i行第j列，那么就将r 译码为vj，同时错误图样为ei，即$r=e_i+v_j$。
缺点：当所考虑的码C的n和k的值都很大的时候，标准阵列的长度就变得非常的巨大，此时，用标准阵来译码就变得不实用了。
最小距离译码方法
方法：对BSC信道，为了使译码错误概率最小，可以选择汉 明重量最小的n重做为陪集首，即将接收矢量r译码为 与r的汉明距离最小的那个码字。
举例：考虑码C={00000,01010,10101,11111}，
该码的最小距离是2。
如果传输的码字是11111，接收的矢量是11110，那么，
d(11110, 00000)=4, d(11110, 01010)=2,
d(11110, 10101)=3, d(11110, 11111)=1。
用最小距离译码方法可以得出传输的码字就是11111这 样的结论。
思考题：有办法来给标准阵降阶么?
结合前面计算伴随式的例子，可以知道伴随式比标准阵的长度短很多。因此，可以用伴随式译码来代替标准阵译码方法。
伴随式译码
定理：一个陪集的所有$2^k$个n重有同样的伴随式。不同陪集的 伴随式不同。
证明：如果x,y属于同一个陪集，那么
$$
\Leftrightarrow x+C=y+C\ \Leftrightarrow x-y \in C\ \Leftrightarrow(x-y)H^T=0\ \Leftrightarrow xH^T=yH^T\ \Leftrightarrow S(x)=S(y)
$$
伴随式译码举例:
举例：考虑码C={0000,1011,0101,1110}，对应的标准阵就是
$$
\begin{matrix} 0000&1011&0101&1110&00\ 1000&0011&1101&0110&11\ 0100&1111&0001&1010&01\ 0010&1001&0111&1100&10\ 陪集首&&&&伴随式\end{matrix}
$$
如果接收矢量是v=(1101)，先通过公式$S=vH^T$求出伴随式(11)，确定对应的陪集首(1000)，这就是错误向量e。然后根据e+v=(1000)+(1101)求出传输的码字为(0101)
完备码
定义：一个能达到汉明界的码成为完备码，满足
$$
M\begin{Bmatrix}\begin{pmatrix}n\0 \end{pmatrix}+ \begin{pmatrix}n\1 \end{pmatrix}(q-1)+ \begin{pmatrix}n\2 \end{pmatrix}(q-1)^2+ \dots+\begin{pmatrix}n\t \end{pmatrix}(q-1)^t \end{Bmatrix} =q^n
$$
其中, M为码字数目, q是q元, n是码长, t是纠错能力
特殊的, 对于二元完备码, 满足$2^{n-k}=\sum^{t}_{i=0}\begin{pmatrix}n\i \end{pmatrix}$
汉明码
定理：q元汉明码Ham(r,q)是参数为(n,k,d)的线性码，其中, $r=n-k, n=(q^r-1)/(q-1), k=(q^r-1)/(q-1)-r, d_{min}=3$。
特殊的, 对于二元汉明码, 满足$(n, k)=(2^r-1, 2^r-1-r)$。
构造汉明码的两种方法：
- 构造H阵的标准形式H=[Q Ir], Q是构造Ir后剩下的2r-1-r列任意排列。
- H阵的列是按r重表示的二进制数的顺序排列。
第四章 循环码
循环移位：将n重$v=(v_{n-1}, v_{n-2}, … , v_1, v_0)$的分量循环左移一位, 得到另一个n重$v(1)=(v_{n-2}, … , v_1, v_0, v_{n-1})$, 称为v的循环移位。若v的分量循环左移i位, 得到$v(i)=(v_{n-i-1}, … , v_1, v_0, v_{n-1}, … , v_{n-i})$。
循环码的定义：一个(n, k)线性码C，若它的每个码字的任何循环移位都仍然是一个码字，则称此码为循环码。
循环码的优势：具有许多固有的代数结构，可以找到各种实用的译码方法，使用具有反馈的线性移位寄存器可以容易的实现编码和伴随式计算。
码字多项式
码字多项式：为研究循环码的代数特性，将码字$v=(v_{n-1}, v_{n-2}, … , v_1, v_0)$的各个分量看成是多项式
$$
v(x)=\sum^{n-1}{i=0}v_ix^i=v{n-1}x^{n-1}+\dots+v_1x+v_0
$$
的系数，此多项式称为v的码字多项式。
对应于码矢v(i)=( vn-i-1, … , v1, v0, vn-1, … , vn-i)的码字多项式为$v^{(i)}(x)=v_{n-i-1}x^{n-1}+v_{n-i-2}x^{n-2}+…+v_1x^{i+1}+v_0x^i+v_{n-1}x^{i-1}+…+v_{n-i+1}x+v_{n-i}$
码字多项式$v^{(i)}(x)$就是$x^iv^{(0)}(x)/(x^n+1)$的余式。
循环码的代数性质
定理1：循环码C中次数最低的非零码字多项式是唯一的。
证明：令$g(x)=\sum^r_{i=0}g_ix_i,g_r=1$是C中次数最低的码字多项式，若g(x)不唯一，则存在另一个码字多项式$g*(x)=\sum^r_{i=0}g^*_ix_i,g^*_r=1$ ，由线性性质可知，g(x)+g*(x)也是一个码字多项式，但它的次数小于r，和前提矛盾，因此，循环码C中次数最低的非零码字多项式是唯一的。证毕。
定理2：若$g(x)=x^r+g_{r-1}x^{r-1}+…+g_1x+g_0$是(n, k)循环码C中次数最低的非零码字多项式, 则必有$g_0=1$。
证明：若$g_0=0$，则$g(x)=x(x^{r-1}+g_{r-1}x^{r-2}+…+g_2x+g_1)$，将g(x)循环左移n-1位之后，可以得到一个次数更低的码字多项式，其次数为r-1，和前提矛盾，则必有$g_0=1$。证毕。
结合定理1和定理2，知在(n,k)循环码中，次数最低的非零码字多项式形如$g(x)=x^r+g_{r-1}x^{r-1}+…+g_1x+1$。
考虑多项式$g^{(1)}(x)=xg(x), g^{(2)}(x)=x^2g(x),…，g^{(n-r-1)}(x)=x^{n-r-1}g(x)$都是g(x)的循环移位, 它们都是码字多项式, 次数分别为r+1, r+2, …, n-1。
根据码字多项式的线性性质可知，它们的任意线性组合
$v(x)=u_{n-r-1}x^{n-r-1}g(x)+…+u_1xg(x)+u_0g(x)=(u_{n-r-1}x^{n-r-1}+…+u_1x+u_0)g(x)$也是C的码字多项式。
(n, k)循环码的码字多项式, 次数分别为r, r+1, r+2, … , n-1，次数小于或等于n-1并且是g(x)的倍式的二元多项式共有$2^{n-r}$个, 它们是(n, k)循环码C的所有码字, 因此, 必有k=n-r或r=n-k。
定理3：若g(x)是(n, k)循环码C中次数最低的非零码字多项式，一个次数小于或等于n-1的二元多项式f(x)是码字多项式当且仅当f(x)是g(x)的倍式。
证明：反证法。设f(x)是码字多项式且其次数小于或等于n-1, 假设f(x)=a(x)g(x)+b(x), deg(b(x))<r，
由线性性质知b(x)=f(x)+a(x)g(x)也是一个码字多项式,而deg(b(x))<deg(g(x))，这和前提矛盾，则只能当f(x)是g(x)的倍式的时候，f(x)是码字多项式。证毕。
生成多项式
定理1：在(n,k)循环码C中存在且仅存在一个次数为n-k的码字多项式$g(x)=x^{n-k}+g_{n-k-1}x^{n-k-1}+…+g_2x^2+g_1x+1$，称为生成多项式，使得每个次数小于或等于n-1的二元多项式是码字多项式当且仅当此多项式是g(x)的倍式。
定理2：(n, k)循环码的生成多项式g(x)是$x^n+1$的因式。
证明：根据：码字多项式$v^{(i)}(x)$就是$x^iv^{(0)}(x)/(x^n+1)$的余式。则有$x^kg(x)=(x^n+1)+g^{(k)}(x)$，而$g^{(k)}(x)$是g(x)的k次循环移位，也是码字多项式，因此，它是g(x)的倍式。
定理3：若g(x)是一个n-k次多项式，并且是$x^n+1$的因式，则g(x)生成一个(n, k)循环码。
循环码的生成矩阵
考虑以$g(x)=\sum^{n-k}_{i=0}g_ix^i$为生成矩阵的(n,k)循环码C，由于$g(x), xg(x), … , x^{k-1}g(x)$张成C，将这k个多项式的k个n重做为k×n阶矩阵的行，一般选择前k-1位为0的向量作为g(x)，则得到C的生成矩阵为
$$
G(x)=\begin{bmatrix} x^{K-1}g(x)\ \dots \xg(x)\g(x) \end{bmatrix}=\begin{bmatrix} g_{n-k}&\dots&g_2&g_1&g_0&0&0&0&\dots&0\ 0&g_{n-k}&\dots&g_2&g_1&g_0&0&0&\dots&0\ 0&0&g_{n-k}&\dots&g_2&g_1&g_0&0&\dots&0\ \dots&&&\dots&&&&&&\dots \ 0&0&\dots&0&0&g_{n-k}&\dots&g_2&g_1&g_0\end{bmatrix}
$$
其中$g_0=g_{n-k}=1$
一致校验矩阵
因为生成多项式g(x)是$x^{n+1}$的因式, 所以存在另一个多项式$h(x)=\sum^k_{i=0}h_ix^i,h_k=h_0=1$ , 使得g(x)h(x)=xn+1, 此多项式h(x)称为码C的校验多项式h(x), 故可以得到码C的一致校验矩阵H。
设$v=(v_{n-1}, … , v_1,v_0 )$是C的一个码矢, 则v(x)=a(x)g(x), 有$v(x)h(x)=a(x)g(x)h(x)=a(x)(x^n+1)=a(x)x^n+a(x)$, 由于deg(a(x))≤k-1, 故在$a(x)x^n+a(x)$中不会出现$x^{n-1}, … , x^{k+1}, x^k$等各次幂, 于是v(x)h(x)的展开式中$x^{n-1}, … , x^{k+1}, x^k$的系数等于零。
因此, 得到以下n-k个方程$h_0v_{n-j}+h_1v_{n-j-1}+…+h_kv_{n-j-k}=0, j=1, … , n-k$。则码C的一致校验矩阵为
$$
H=\begin{bmatrix} h_k&h_{k-1}&h_{k-2}&\dots&h_0&0&0&\dots&0\ 0&h_k&h_{k-1}&\dots&h_1&h_0&0&\dots&0\ \dots\ 0&0&0&\dots&h_k&h_{k-1}&h_{k-2}&\dots&h_0\end{bmatrix}
$$
系统循环码的编码方法
给定循环码的生成多项式g(x), 可以使该码成为系统形式。
假定待编码的消息是$u=(u_{k-1}, … , u_1, u_0 )$, 则对应的消息多项式为$u(x)=u_{k-1}x^{k-1}+…+u_2x^2+u_1x+u_0$, 从而有$x^{n-k}u(x)=u_{k-1}x^{n-1}+…+u_1x^{n-k+1}+u_0x^{n-k}$。
用生成多项式g(x)除xn-ku(x), 得到xn-ku(x)= a(x)g(x)+b(x), deg(b(x))<n-k。
循环码的编码是由多项式的乘法、除法以及加法运算完成的, 这些运算都可以由移位寄存器、加法器以及门电路来实现。
系统循环码的编码步骤如下：
步骤1：先用xn-k乘以消息多项式$u(x)=u_{k-1}x^{k-1}+…+u_2x^2+u_1x+u_0$；
步骤2：用生成多项式g(x)除$x^{n-k}u(x)$，得到余式b(x)；
步骤3：联合b(x)和$x^{n-k}u(x)$，得到码字多项式$v(x)=x^n-ku(x)+b(x)$
复习：多项式的除法
g(x)除法电路编码器
伴随式计算和错误检测
伴随式定义为$S=rH^T$
对系统循环码而言, $r(x)=\sum^{n-1}{i=0}r_ix^i$是接收多项式$g(x)=\sum^{n-k-1}{i=0}g_ix^i$,
是生成多项式, 用g(x)去除r(x)所得的余式, 就是伴随式s(x), 即r(x)=a(x)g(x)+s(x)。
∵ r(x)=v(x)+e(x), v(x)=q(x)g(x), r(x)=a(x)g(x)+s(x)
∴ q(x)g(x)+e(x)=a(x)g(x)+s(x)
∴ e(x)=[q(x)+a(x)]g(x)+s(x)
伴随式的性质
性质1：令s(x)是接收多项式r(x)的伴随式, 则用生成多项式g(x)除xs(x)所得的余式$s^{(1)}(x)$就是r(x)循环移位一次$r^{(1)}(x)$的伴随式。
性质2：(n, k)循环码能够检测长度小于等于n-k的任何突发错误, 换句话说, 每个长度小于等于n-k的突发错误的伴随式不等于0。
性质3：伴随式等于生成多项式除错误图样后所得的余式。
伴随式的这些性质对于译码非常有用。举例来说, 若e(x)是可以纠正的错误图样, 则e(x)的循环移位也是可以纠正的错误图样。
循环码的译码
循环码的译码分为3步：1)计算伴随式; 2)由伴随式得到错误图样; 3)纠正错误。
第五章 BCH码
BCH码简介
BCH码的优势：纠错能力强, 能够纠正多个随机错误的循环码; 编译码设备不太复杂; 到目前为止, 对于其他线性码的研究方法, 都是先构造一个码, 然后找出它的最小距离, 以估计该码的纠错能力, 对于BCH码, 反过来, 从先指定这个码能纠正多少个随机错误开始进行研究。
本原元和本原多项式
本原元：有限域上存在元素a，使得G中的每个非零元素都是a的某次幂的形式，该元素a称为本原元。
本原多项式：有限域GF(q)上的本原多项式f(x),是系数取自GF(q)上，以扩域$GF(q^m)$中本原元为根的最小多项式。
定理1：若$b_1,b_2,..,b_{q-1}$是有限域GF(q)上的所有非零元素，则$x^{q-1}-1=(x-b_1)(x-b_2)…(x-b_{q-1})$。
举例: GF(23)上的乘法运算
选择本原元a=x, 本原多项式$p(x)=x^3+x+1$
| $a^{-\infty}=x^{-\infty}=0$ | 000 |
|---|---|
| $a^0=x^0=1$ | 001 |
| $a^1=x$ | 010 |
| $a^2=x^2$ | 100 |
| $a^3=x+1$ | 011 |
| $a^4=x^2+x$ | 110 |
| $a^5=x^2+x+1$ | 111 |
| $a^6=x^2+1$ | 101 |
| $a^7=a^0=1$ |
乘法运算：
$$
(010)·(100)
\leftrightarrow a^3·a^4=1
\leftrightarrow001\ (011)·(110)
\leftrightarrow a^6·a^5=a^4
\leftrightarrow110
$$
因为本原元a=x, 所以p(a)=0
$$
a^3+a+1=(x+1)+x+1=0\ (011)+(010)+(001)=(000)
$$
GF(2)上多项式根的特点
定理：若f(x)是系数取自GF(2)的多项式, 令b是GF(2)扩域中的元素, 若b是f(x)的根, 则对任意的l≥0, $b^{2l}$也是f(x)的根。
注：元素$b^{2l}$称为b的共轭元，以上定理说明若是b多项式f(x)的根，则b的所有共轭元$b^{2l}$也是f(x)的根。
举例：${a^1, a^2, a^4}$是共轭的元素，因为它们都是极小多项式$f_2(x)=x^3+x+1$的根。
最低公倍式：若f(x)为a(x)与b(x)的所有公倍式中次数最低的，并且首项系数为1，记为LCM(a(x), b(x))。
BCH码的定义
BCH码的定义：给定任一有限域GF(q)及其扩域$GF(q^m)$, 其中, q是素数或者素数幂, m为一个正整数。若码元是取自GF(q)上的一个循环码, 它的生成多项式g(x)的根集合R中含有以下2t个连续根${b^p, b^{p+1},.., b^{p+2t-1}}$, 则由g(x)生成的循环码称为q进制的BCH码, 其中$b∈GF(q^m)$是域中的n阶元素, $b^{p+i} ∈GF(q^m) (0≤i≤2t-1)$, p是任意整数。对于常见的情况, p等于0或者1。若p=1, 称之为狭义的BCH码。
本原BCH码的定义：若g(x)的根中有一个是$GF(q^m)$的本原元, 码长$n=q^m-1$, 此时就称g(x)生成的BCH码为本原BCH码; 否则就称为非本原BCH码, 其码长是$q^m-1$的因子。
BCH码的构造
构造方法：设$f_i(x)$和$q_i$分别是$b^{p+i}(0≤i≤2t-1)$的最小多项式和阶, 则BCH码的生成多项式g(x)和码长n可分别表示为$g(x)=LCM(f_0(x), f_1(x),…, f_{2t-1}(x)), n=LCM(q_0, q_1,…, q_{2t-1})$。
构造可以纠t个错误的BCH码(其码长$n=q^m-1$)的生成多项式的步骤如下：
步骤1：选择一个阶数为m的本原多项式, 构造扩域$GF(q^m)$;
步骤2：找到对应于$b^i(i=1,…,p)$的极小多项式$f_i(x)$;
步骤3：能纠t个错误的BCH码的生成多项式为$g(x)=LCM(f_1(x), f_2(x),…, f_{2t}(x))$。
BCH码限定理
定理1：若BCH码的生成多项式g(x)的根含有2t个连续根, 则该码的最小距离d≥2t+1。
d=2t+1称为该码的设计距离。
注：一旦固定n和t, 就可以得到该BCH码的生成多项式, 信息位的长度k可以由生成多项式的阶数得到。
当n不变的情况下，较大的t，就会使得k较小；即冗余度高，可以纠更多的错误。
思考题：如何在由GF(2)生成的扩域GF(24)上构造BCH码的生成多项式？
考虑本原多项式$p(z)=z^4+z+1$, 本原元a=z, a的幂次可以生成$GF(2^4)$上的所有非零元素。
| a的幂次 | $GF(2^4)$上的非零元素 | 极小多项式 |
|---|---|---|
| $a^1$ | $z$ | $x^4+x+1$ |
| $a^2$ | $z^2$ | $x^4+x+1$ |
| $a^3$ | $z^3$ | $x^4+x^3+x^2+x+1$ |
| $a^4$ | $z+1$ | $x^4+x+1$ |
| $a^5$ | $z^2+z$ | $x^2+x+1$ |
| $a^6$ | $z^3+z^2$ | $x^4+x^3+x^2+x+1$ |
| $a^7$ | $z^3+z+1$ | $x^4+x^3+1$ |
| $a^8$ | $z^2+1$ | $x^4+x+1$ |
| $a^9$ | $z^3+z$ | $x^4+x^3+x^2+x+1$ |
| $a^{10}$ | $z^2+z+1$ | $x^2+x+1$ |
| $a^{11}$ | $z^3+z^2+z$ | $x^4+x+1$ |
| $a^{12}$ | $z^3+z^2+z+1$ | $x^4+x^3+x^2+x+1$ |
| $a^{13}$ | $z^3+z^2+1$ | $x^4+x^3+1$ |
| $a^{14}$ | $z^3+1$ | $x^4+x^3+1$ |
| $a^{15}$ | 1 | x+1 |
如果想要构造可以纠1个错误的BCH码的生成多项式, 即t=1, 码长n=15
BCH码的生成多项式为$g(x)=LCM(f_1(x), f_2(x),…, f_{2t}(x))$
根据上页的表格来获得极小多项式f1(x)和f2(x)
因此, 得到如下的可以纠正一个错误的BCH码的生成多项式$g(x)=LCM(f_1(x), f_2(x))= LCM(x^4+x+1, x^4+x+1)=x^4+x+1$
∵deg(g(x))=4, ∴n-k=4, k=11, 这样就得到了一个可以纠一个错误的BCH(15, 11)码, 该码的设计距离d=2t+1=3
可以计算出该码的最小距离也是3，即该码的设计距离等于该码的最小距离
如果想要构造可以纠2个错误的BCH码的生成多项式, 即t=2, 码长n=15
BCH码的生成多项式为$g(x)=LCM(f_1(x), f_2(x),…, f_{2t}(x))= LCM(f_1(x), f_2(x), f_3(x), f_4(x))$
根据11页的表格来获得极小多项式f1(x)-f4(x)
于是得到$g(x)=LCM(f_1(x), f_2(x) , f_3(x), f_4(x))= LCM(x^4+x+1, x^4+x+1, x^4+x^3+x^2+x+1, x^4+x +1)=(x^4+x+1)(x^4+x^3+ x^2+x+1) =x^8+x^7+x^6+x^4+1$
∵deg(g(x))=8，∴n-k=8，k=7, 这样就得到了一个可以纠一个错误的BCH(15,7)码，该码的设计距离d=2t+1=5
可以计算出该码的最小距离也是5。
第六章 RM码
RM码的优点和缺点
缺点：与BCH码相比，除了一阶RM码和中等码长的RM码外，RM码的最小距离比同样码长的BCH码的最小距离小。RM码的纠错性能不如Turbo码和LDPC码
优点：RM码能用大逻辑译码算法，比BCH码用的迭代算法简单。译码延时短，无错误平层现象，其误码率会随着信噪比增加无限接近于零。因此，RM码可以适应多种不同的信道，满足有实时性要求的应用环境，既可以单独使用，也可以作为内码与RS码等级联使用，从而大大提升纠错性能
线性码
定义：一个码长为n的p元码C叫做线性码，是指C是向量空间$F_p^n$的向量子空间，即C满足如下的性质：对$F_p^n$中任意元素α和β，如果$c_1$和$c_2$属于C，则$αc_1+βc_2$也属于C。
定理：设C是参数为(n,k)的p元线性码。
1)若G是C的一个生成矩阵，而H是Fp上一个(n−k)行n列的矩阵。则H是C的一个校验矩阵当且仅当$rank(H)=n−k$，并且$HG^T=0_{n−k,k}$；
2) 若$G=(I_k,P), H=(−P^T,I_{n−k})，$则G是C的一个生成矩阵当且仅当H是C的一个校验矩阵。
向量外积
定义：设$a=(a_{n−1},a_{n−2},···,a_0),b=(b_{n−1},b_{n−2},···,b_0)$是GF(2)上的两个n维向量，则向量$(a_{n−1}b_{n−1},a_{n−2}b_{n−2},···,a_0b_0)$称为a与b的外积，记为a×b。
布尔函数
定义：设m为正整数，一个m元布尔函数$f=f(x_1,···,x_m)$是由$F_2^m$到$F_2$的映射，即m个变量$x_1,···,x_m$均取值于$F_2$，并且函数值也属于$F_2$。
由于$F_2^m$中向量的个数为$2^m$，而f在每个向量的取值均彼此独立地可取1或0，所以m元布尔函数共有$2^{2^m}$个。
例子：一元布尔函数f(x)共有$2^{2^1}=4$个，它们是：
1）f(0)=f(1)=0，即f(x)≡0；
2）f(0)=f(1)=1,即f(x)≡1；
3）f(0)=0,f(1)=1，即f(x)=x；
4）f(0)=1,f(1)=0，即f(x)=x+1。
定理：每个m元布尔函数$g(x_1,···,x_m)$均可唯一地表示成$g(x_1,···,x_m)=c+c_1x_1 + ··· +c_mx_m+c_{12}x_1x_2+c_{13}x_1x_3+ ··· + c_{m-1,m}x_{m-1}x_m+c_{123}x_1x_2x_3+ ··· + c_{12···m}x_1x_2···x_m$，其中所有系数和常数都属于$F_2$。
令$v_0=(0,0,···,0), v_1=(1,0,···,0), v_2=(0,1,···,0), v_3=(1,1,···,0), ··· ,v_n-1=(1,1,···,1), n= 2^m，$然后便可把每个m元布尔函数$f(x_1,···, x_m)$表示成$F_2^n$中的向量(也叫 f 的真值表或向量表示)，具体为$c_f=(f(v_0), f(v_1),···, f(v_{n-1}))∈F_2^n, n= 2^m$
这时布尔函数相加和相乘分别对应于向量按分量相加和相乘。
RM码
定义：设$m≥1, n=2^m, 0≤r≤m$。向量空间$F_2^n$的子集合
$RM(r,m)={c_f=(f(v_0), f(v_1),···, f(v_{n-1}))∈F_2^n|f∈B_m,deg(f)≤r}$
叫做r阶的Reed-Muller码(简称RM码)，这里$v_i∈F_2^m$。
定理：RM码RM(r,m)是线性码，基本参数为$(n,k,d)=(2^m,∑_{t=0}^r\begin{pmatrix}m\t\end{pmatrix}),2^{m-r})$
生成矩阵
对于每一对正整数r和m(m>r),有一个码长为$2^m$的RM码，称为码长为$2^m$的r阶RM码。它的生成矩阵是由矩阵块$G_0,G_1,···,G_r$组成的，即$G=\begin{pmatrix}G_0\G_1\\dots\G_r\end{pmatrix}$
G0是码长为$n=2^m$的全“1”向量
G1是$m×2^m$阶矩阵，即$G_1$是由所有长度为m的二进制的列向量组成的。$G_1$的最左边一列是全“0”向量，最后一列为全“1”向量，其他各列则是从左至右依递增顺序排列的二进制m重列向量
$G_l$的行是由所有$G_l$的l个行向量作外积所得的向量组成，因而$G_l$是一个$\begin{pmatrix} m\l\end{pmatrix}*2^m$阶矩阵。显然在G的行是线性无关的条件下，r阶RM码的信息位为$k=1+\begin{pmatrix} m\l\end{pmatrix}+\begin{pmatrix} m\2\end{pmatrix}+\dots+\begin{pmatrix} m\r\end{pmatrix}$。
RM码的构造
从RM码的定义可以看出，一个r阶RM码可以通过增广一个(r-1)阶RM码得到，而一个(r-1)阶RM码可以由删信一个r阶RM码而获得，即通过简单计算，增加一个G矩阵分量或直接删除一个G矩阵分量
RM码的构造简单，纠错能力强，很容易根据需要设计出不同码长的RM码
译码算法
从RM码的生成矩阵G中可以看出，Gl的每行重量为$2^{m-l}$，这个结论对于一般的r阶RM码都是对的，因此，G的每行都有偶重量
在GF(2)上，因为两个偶重量向量之和必为偶重量，所以G的行线性组合有偶重量。即RM码的所有码字重量皆为偶数
由于Gr行的重量为$2^{m-l}$，因而r阶RM码的最小重量不大于$2^{m-l}$
里德算法是专门为RM码设计的译码算法
里德算法使用择多逻辑判决的方法从接收矢量直接恢复信息，而不计算错误图样
里德算法可以纠正r阶RM码出现的$(1/2)×2^{m-r}−1$个随机错误，并恢复k位信息。这说明码的最小重量至少为$2^{m-r}−1$，又RM码的最小重量为偶数，因而r阶RM码最小重量至少为$2^{m-r}$
综上所述，r阶RM码最小重量为$2^{m-r}$，即RM码最小距离为$2^{m-r}$
将信息向量分成r+1段，即写成$m=(I_0,I_1,⋯,I_r)$,其中$I_i$包含$\begin{pmatrix} m\l\end{pmatrix}$个信息位，于是编程可表示为$v=I_0G_0+I_1G_1+⋯+I_rG_r$ (1.1)
如果接收码字$r=v+e=I_0G_0+I_1G_1+⋯+I_rG_r+e$ (1.2)， 其中e为错误图样
通过对r阶RM码的译码计算，由接收码字r恢复了第r段信息Ir，然后计算
$r(1)=r-I_rG_r=I_0G_0+I_1G_1+⋯+I_{r-1}G_{r-1}+e$ (1.3)
这就把由接收码字r恢复m的问题简化成由r(1)恢复信息$m^{(1)}=(I_0,I_1,⋯,I_{r-1})$的问题
继续采用同样方法就可逐步恢复所有信息，最终完成r阶RM码的译码
第七章 卷积码
卷积码与分组码的区别
卷积码有记忆性，分组码无记忆性
卷积码充分利用了各组信息之间的相关性，信息序列不被分段，而是被连续处理
通常，卷积码的n和k比分组码的n和k要小的多
在同样的编码效率下，卷积码的性能优于分组码
在相似的纠错能力下，卷积码的实现比分组码简单
卷积码必须用序列逻辑电路来实现，更适用于前向纠错系统；分组码是用组合逻辑电路来实现
离散序列的非循环卷积运算
定义：设f(n)和g(n)是两个序列，则序列f和g的离散卷积运算为
$$
(f*g)(m)=\sum_nf(n)g(m-n)
$$
二元(2,1,2)卷积码的编码器
编码器主要由m=2级移位寄存器，n=2个模2加法器组成。所有的卷积码编码器都可以用这种类型的线性前馈移位寄存器来实现。
冲激响应
冲激响应：编码器的冲激响应就是通过令u=(100…)所得到的两个输出序列。
因为编码器有m个存储单元，所以冲激响应(生成序列)至多持续m+1个时间单元，且可以写成
$$
g^{(1)}=(g^{(1)}_0,g^{(1)}_1,…,g^{(1)}_m),g^{(2)}=(g^{(2)}_0,g^{(2)}_1,…,g^{(2)}_m)
$$
其中上标表示第几个输出端
图6.1的(2,1,2)卷积码的冲激响应为$g^{(1)}=(111), g^{(2)}=(101)$
另外，冲激响应向量还可以表示输入、移位寄存器和输出之间的连接关系，1表示有连接，0表示没有连接
输出序列
信息序列$u=(u_1,u_2,u_3,…)$每次进入编码器1比特，编码器的两个输出序列
$$
v^{(1)}=(v^{(1)}_0,v^{(1)}_1,…), v^{(2)}=(v^{(2)}_0,v^{(2)}_1,…)
$$
可以通过输入序列u和编码器的两个冲激响应作卷积运算而得到。
若u=(1011), 图6.1的(2,1,2)卷积码的冲激响应为$g……{(1)}=(111), g^{(2)}=(101)$，则该卷积码的输出序列为$V^{(1)}=u^g^{(1)}=(110001)$, $V^{(2)}=u^g^{(2)}=(100111)$
码字
输出序列分别为$v^{(1)}=(v^{(1)}_0,v^{(1)}_1,…), v^{(2)}=(v^{(2)}_0,v^{(2)}_1,…)$的$(2,1,m)$的卷积码的码字，为$V^{(1)}$和$V^{(2)}$的交错，即
$$
v=(v^{(1)}_0,v^{(2)}_0,v^{(1)}_1,v^{(2)}_1,…)
$$
图6.1的(2,1,2)卷积码，若u=(1011), 冲激响应为$g^{(1)}=(111)$, $g^{(2)}=(101)$，该卷积码的输出序列为$V^{(1)}=u^g^{(1)}=(110001)$, $V^{(2)}=u^*g^{(2)}=(100111)$*，得到的码字为v=(11,10,00,01,01,11)
以u=(u1,u2,u3,…)为输入, 以$g^{(1)}=(g^{(1)}_0,g^{(1)}_1,…,g^{(1)}_m),g^{(2)}=(g^{(2)}_0,g^{(2)}_1,…,g^{(2)}_m)$
为生成序列的(2,1,m)卷积码的输出序列分别由方程$V^{(1)}=u^*g^{(1)}$和$V^{(2)}=u^g^{(2)}$*得到。
图6.1的(2,1,2)卷积码的编码方程为
另外，编码方程中每一项的系数，还可以表示输入、移位寄存器和输出之间的连接关系，1表示有连接，0表示没有连接。$$
\begin{cases} V_l^{(1)}=u_l+u_{l-1}+u_{l-2}\ V_l^{(2)}=u_l+u_{l-2} \end{cases},[V_l^{(1)}V_l^{(2)}]=[u_lu_{l-1}u_{l-2}]\begin{bmatrix} 1&1\1&0\1&1\end{bmatrix}
$$
生成矩阵
(2,1, m)卷积码的生成矩阵：将生成序列g(1)和g(2)交织后形成的半无限矩阵
$$
G=\begin{bmatrix}g^{(1)}_0&g^{(2)}_0&g^{(1)}_1&g^{(2)}_1&g^{(1)}_2&g^{(2)}_2&\dots&g^{(1)}_m&g^{(2)}_m&0&0&0&0&\dots\ 0&0&g^{(1)}_0&g^{(2)}_0&g^{(1)}1&g^{(2)}1&\dots &g^{(1)}{m-1}&g^{(2)}{m-1}&g^{(1)}m&g^{(2)}m&0&0&\dots \0&0&0&0&g^{(1)}0&g^{(2)}0&\dots&g^{(1)}{m-2}&g^{(2)}{m-2}&g^{(1)}{m-1}&g^{(2)}{m-1}&g^{(1)}_m&g^{(2)}_m&\dots\ &&&&&&\ddots\end{bmatrix}
$$
以u=(u1,u2,u3,…)为输入, G为生成矩阵的(2,1,m)的卷积码的码字为V=uG。
二元(3,2,1)卷积码的编码器
编码器主要有2个输入，3个输出，主要由m=1级移位寄存器，n=3个模2加法器组成。
二元(3,2,m)卷积码的输入序列
对于一般的(3,2,m)卷积码，由于k=2，即每次有2比特进入编码器，所以输入序列u可以写成$v=(v^{(1)}_0,v^{(2)}_0,v^{(1)}_1,v^{(2)}_1,…)$或分开写成2个序列$v^{(1)}=(v^{(1)}_0,v^{(1)}_1,…), v^{(2)}=(v^{(2)}_0,v^{(2)}_1,…)$
二元(3,2,m)卷积码的冲激响应$g^{(j)}i=(g^{(j)}{i0},g^{(j)}{i1},…,g^{(j)}{im}),i=1,2,j=1,2,3$
输出序列分别为
$$
v^{(1)}=(v^{(1)}_0,v^{(1)}_1,…), v^{(2)}=(v^{(2)}_0,v^{(2)}_1,…), v^{(3)}=(v^{(3)}_0,v^{(3)}_1,…)
$$
的(3,2,m)的卷积码的码字为
$$
v=(v^{(1)}_0,v^{(2)}_0,v^{(3)}_0,v^{(1)}_1,v^{(2)}_1,v^{(3)}_1,…)
$$
卷积码编码器的存储级数
对于(n,k,m)卷积码，当k>1时，编码器及用来描述它的符号都比较复杂，并且该编码器所含的k个移位寄存器的长度未必相同。
存储级数：若ki是第i个移位寄存器的长度，则称所有k个移位寄存器中的最大长度为存储级数，即编码器的存储级数m定义为$m=\max_{1<i<k}k_i$
卷积码编码器的约束长度和码速率
对于(n, k, m)卷积码，编码器中每个信息位要保持m+1时间个单位，每个时间单位都可以影响编码器输出中的任何一个，这由移位寄存器的连接决定。
约束长度：对于(n,k,m)卷积码，编码器的约束长度定义为$n_A=n(m+1)$
约束长度可以解释成1比特信息对编码器输出可以造成影响的最大数目。
码速率：对于(n,k,m)卷积码，其码速率r=k/n
(2, 1, m)卷积码的多项式描述
信息序列：$u$表示成$u(x)$
生成多项式：$g^{(1)}$表示成$g^{(1)}(x)$, $g^{(2)}$表示成$g^{(2)}(x)$
输出序列：$V^{(1)}$表示成$V^{(1)}(x)$, $V^{(2)}$表示成$V^{(2)}(x),$
码字：$V$表示成$V(x)$。于是$V^{(1)}(x)=u(x)g^{(1)}(x), V^{(2)}(x)=u(x)g^{(2)}(x),$
码字：$V(x)=V^{(1)}(x^2)+xV^{(2)}(x^2)$
(n, k, m)卷积码的转移函数矩阵
于编码器是线性系统, 同任何有k个输入n个输出的线性系统一样，总共有k×n个转移函数。k×n阶转移函数矩阵为
$$
G(x)=\begin{bmatrix}g_1^{(1)}&g_1^{(1)}&\dots&g_1^{(1)}\ g_2^{(1)}&g_2^{(1)}&\dots&g_2^{(1)}\ \dots \ g_k^{(1)}&g_k^{(1)}&\dots&g_k^{(1)}\ \end{bmatrix}
$$
于是，码字$V(x)=u(x)G(x)$, 其中, $u(x)=(u^{(1)}(x), u^{(2)}(x),…, u^{(k)}(x)), V(x)=(V^{(1)}(x), V^{(2)}(x),…, V^{(n)}(x))$, 并路之后, 码字变成$V(x)=V^{(1)}(x^n)+xV^{(2)}(x^n)+…+x^{n-1}V^{(n)}(xn)$
维特比(Viterbi)译码系统
(n,k,m)卷积码, 如输入序列为x，输出码字为c，经过有噪声的信号传输后，得到接收序列r，然后经过Viterbi译码器，得到序列y。
对于码率为r的(n,k,m) 卷积码, 输入的信息长度为L，则输入序列为
$x=(x_0^{(1)}, x_0^{(2)},…, x_0^{(k)}, x_1^{(1)}, x_1^{(2)},…, x_1^{(k)},…, x_{L+m-1}^{(1)}, x_{L+m-1}^{ (2)},…, x_{L+m-1 }^{(k)})$
对应输出的码字序列为
$c=(c_0^{(1)}, c_0^{(2)},…, c_0^{(n)}, c_1^{(1)}, c_1^{(2)},…, c_1^{(n)},…, c_{L+m-1}^{(1)}, c_{L+m-1 }^{(2)},…, c_{L+m-1}^{ (n)})$
其中下标表示时间。
消息序列的尾部需要m个0比特使得移位寄存器的状态归0。一般的，默认移位寄存器从全零状态开始，最终还是以全零状态结束。
第八章 Turbo码
Turbo码的优点
在信噪比较低的高噪声环境下性能优越（信道条件差的移动通信系统中有很大的应用潜力），而且具有很强的抗衰落、抗干扰能力。
Turbo码具有超乎寻常的优异的译码性能，可以纠正高速率数据传输时发生的误码。在直扩（CDMA）系统中采用Turbo码技术可以进一步提高系统的容量。
在短帧情况下的仿真结果表明短交织Turbo码在AWGN信道和Rayleigh衰落信道下仍具有接近信道容量的纠错能力。
Turbo码的缺点
为获得较高的性能，Turbo码的编译码方式较为复杂。
具有较大的译码时延，这是由于block长度较大、译码需要多次迭代造成的。这样非常不利实时业务或高速数据的传输。
BER(比特出错概率)在10−5后会出现误码平层，这是由于Turbo码的重量分布造成的。对于某些对BER要求较高的应用就不适合，当然通过交织器的设计能够提供更大的码间最小距离，从而降低误码平层。
分量码
卷积码的类型多样，如非递归卷积码(NRC)、非系统卷积码(NSC)、递归系统卷积码(RSC)。
在实际的系统中，由于RSC有突出的优点而被广泛采用。RSC码在具有良好的译码性能，且存在较高的交织增益，译码性能也会随着交织长度增加而提高。
交织器
交织器的主要功能是使码重分布合理，降低数据序列的相关性，增大输出码字的最小汉明距，实现随机编码。
分组交织器：将数据序列按行的顺序写入m×n的矩阵，然后按列的顺序读出，即完成交织过程。相应的解交织过程就是将交织后的数据序列按列写入m×n矩阵，再按照行的顺序读出。
伪随机交织器：指交织映射随机生成的交织器，每个长度为N的伪随机交织器共有N！种可能的交织形式。这种交织器采用给定的随机地址交织映射，由这个已知的交织表对输入信息序列进行映射。
删余处理
在编码完成后，将分量码输出的两路校验信息输入删余器，按照一定的规则删除一部分校验信息，减小信息的冗余度，从而提高编码效率。
Turbo码编码器的结构
三种：并行级联卷积码(PCCC)、串行级联卷积码(SCCC)和混合级联卷积码(HCCC)
并行级联卷积码(PCCC)
随机交织器：将信息序列U进行比特位置重排列得到U1（内容不变）
分量编码器：生成校验序列 $X_{p1}$ 和 $X_{p2}$（一般两个编码器结构相同）
删余矩阵：为了提高码率，周期地删除一些校验位，形成校验位序列Xp
复接：未编码序列Xs与Xp经过复接后，生成Turbo码序列X
Turbo码的码率
若两个分量码的码率分别为R1和R2，则Turbo码的码率为
$$
R=\frac{R_1R_2}{R_1+R_2-R_1R_2}
$$
Turbo码的译码
Turbo码有一重要特点是其译码较为复杂，比常规的卷积码要复杂的多。
这种复杂不仅在于其译码要采用迭代的过程，而且采用的算法本身也比较复杂。
译码算法
MAP算法：MAP算法采用递推、迭代方法，将最大似然对数比函数作为软判决的输出。但由于该算法需要多次迭代，复杂度较高，运算量非常大，而且对数和指数的运算在数字电路中比较难以实现，导致其在工程实现上受到了很大程度的限制。
Max-log-MAP算法：即最大值运算，在MAP算法基础上通过减少格图搜索状态来达到简化的目的。Max-log-MAP对MAP所做的修改是在对数域里对一些函数进行计算，这样省去了很多的指数的运算和对数域的运算，很大程度上降低了运算的复杂度，大大简化了运算量；但是由于在计算过程有一些近似处理，所以Max-log-MAP算法不是最优的。
Log-MAP算法：即对数域算法，Robertson等人在Max-log-MAP算法基础上进行了一些修改，使得Log-MAP算法相比于Max-log-MAP算法只多了一些查表及加法运算，尽管提高了一点复杂度但是性能却得到很大的提高。
SOVA算法：即软输出Viterbi译码，SOVA算法在标准Viterbi译码算法上进行了一些修改：在进行最大似然路径选择时必须参考其先验信息；不但需要给出每个比特译码的准确结果，还需要计算出每个比特译码的可靠性，通过一些计算从中获取一些关于译码比特的先验信息，从而为下次迭代做好准备，大大减小了运算量，但性能受到了损失，大约损失了1dB。
第九章 二维码
二维码的概念与原理
行排式二维码，又称堆积式二维码或层排式二维码，其编码原理是建立在一维条码基础之上，按需要堆积成二行或多行。
矩阵式二维码，又称棋盘式二维码，它是在一个矩形空间通过黑、白像素在矩阵中的不同分布进行编码。
二维码的特点
可靠性强
条形码的读取准确率远远超过人工记录，平均每15000个字符才会出现一个错误。
效率高
条形码的读取速度很快，相当于每秒40个字符。
易于制作
条形码的编写很简单，制作也仅仅需要印刷，被称为“可印刷的计算机语言”。
高密度
二维码通过利用垂直方向的堆积来提高条码的信息密度，而且采用高密度图形表示。
构造简单
条形码识别设备的构造简单，使用方便。
灵活实用
条形码符号可以手工键盘输入，也可以和有关设备组成识别系统实现自动化识别，还可以和其他控制设备联系起来实现整个系统的自动化管理。
成本低
与其它自动化识别技术相比较，条形码技术仅仅需要一小张贴纸和相对构造简单的光学扫描仪，成本相当低廉。
纠错功能
二维码不仅能防止错误，而且能纠正错误，即使条形码部分损坏，也能将正确的信息还原出来。
多语言形式，可表示图像
二维码具有字节表示模式，即提供了一种表示字节流的机制。不论何种语言文字它们在计算机中存储时以机内码的形式表现，而内部码都是字节码，可识别多种语言文字的条码。
具有加密体制
可以先用一定的加密算法将信息加密，再用二维码表示在识别二维条码时，再加以一定的解密算法，便可以恢复所表示的信息。
QR码的生成与识别
寻像图形、位置探测图形：
协助扫描软件定位QR码并转换坐标系。
寻像图形包括三个相同的位置探测图形，分别位于图形中的左上角、右上角和左下角。每个位置探测图形由7*7个模块组成。如图，寻像图形为黑色区域。
位置探测图形分隔符：
区分功能图形和编码区域。
每个位置探测图形和编码区域之间有宽度为1个模块的分隔符。位置探测图形分隔符为灰色区域，此区域应为空白。
定位图形：
确定符号的密度和版本，提供决定模块坐标的基准位置。
定位图形为图中的茶色区域，水平和垂直的定位图形分别始于第6行和第6列。
校正图形：
在图像有一定程度损坏的情况下，译码软件可以通过它同步图像模块的坐标映像。
矫正图形的数量视符号和版本号而定，版本1没有校正图形，版本2及以上均含有校正图形。
格式信息：
存放纠错等级和掩模信息。
格式信息是一个15位数据，由2位纠错指示符+3位掩模图形参考+10位纠错码组成，为图中深蓝色区域。
同时，左下角格式信息编号8上方的橙色区域，此区域永远为深色模块，不用于存放任何信息。
版本信息：
用于存放QR码的版本号。
为图中红色区域，两个3*6模块。
扩展图形：
最初的目的是用于将来对QR码功能的扩展，并不用于对数据的编码。
扩展图形由位于符号右下角的一个4个模块组成的方块以及位于符号右边和下边的一些8个模块的块组成。8个模块的块的数目取决于符号的版本，计算公式为：
8模块的数目=2*(N DIV 2)
其中N为版本号，DIV表示除法运算。
扩展图形为图中红框区域，即版本7中有6个8模块组成的块和1个4模块组成的块。
QR码的纠错能力：
| 级别 | 纠错能力 |
|---|---|
| L | 约7% |
| M | 约15% |
| Q | 约25% |
| H | 约30% |
举例说明QR码的编码过程。
识别步骤
条码定位
条码分割
解码
条码定位
定位采用以下步骤：
1.利用点运算的阈值理论将采集到的图像变为二值图像，即对图像进行二值化处理；
2.得到二值化图像后，对其进行膨胀运算；
3.对膨胀后的图像进行边缘检测得到条码区域的轮廓。
4.确定寻像图形
5.探测图形中心坐标
6.确定两个举例
7.确定版本号
8.构造位图
9.得到纠错等级和掩模图形
条码分割
分割采用以下步骤：
1.将原图像按比例缩小进行分割，计算其特征值；
2.分块继承父块纹理类别，结合其周围纹理类型进行修正；
3.重复步骤二直至图像被划分为2*2大小，分割结束；
4.分割结束后，图中可能出现的孤立的小区域可作为噪声删除。
解码
得到一幅标准的条码图像后，对该符号进行网络取样，对网格每一个交点上的图像像素取样，并根据阈值确定是深色块还是浅色块。构造一个位图，用二进制的“1”表示深色像素，“0”表示浅色像素，从而得到条码的原始二进制序列值，然后对这些数据进行纠错和译码：
1.异或处理（XOR）
2.确定符号码字
3.重新排列码字序列
4.执行错误检测和纠错译码程序
最后根据条码的逻辑编码规则把这些原始的数据位流转换成数据码字。
第十章 极化码
极化码概述与研究现状
极化码优点：
1、是目前唯一的香农信道容量可达的编码方式
2、有坚实的理论基础
3、编解码复杂度低
4、精细的码率调整机制（信息块长度可以一比特一比特的递减）
5、极化码的递归特性易于通过硬件实现（母码长度为N的Polar码可以用两个母码长度为N/2的Polar码实现）
极化码缺点：
1、汉明距离较小，在短码情况下影响解码性能，一定程度上可以通过选择合适的冻结比特位置进行规避。适合长码编码。
2、SC译码延时较大。
极化（Polar）码起源
截止频率越高，系统响应越快
因此Polar码的最初设计的出发点是为了提升截止频率
在随机编码和最大似然条件下，信道截止速率R0决定了相应的码块的错误概率：
$$
P_e=2^{−N∙R_0}
$$
其中，N为码块长度。实际信道的传输速率R小于R_0、使用随机编码和ML编码时，信道平均错误概率：
$$
P _e=2^{−N（R_0−R）}
$$
极化码的基本原理
对于Polar码基本原理可以归结为三点：信道合并、信道分离、信道极化。其中信道合并和信道极化是在编码时完成的；信道分离是在解码时完成。
信道选择：
对于编码方案通常根据某种信道设计，Polar码主要考虑以下信道进行分析：
二进制离散无记忆信道（B-DMC）:二进制删除信道（BEC）;二进制对称信道（BSC）
wechat- alipay
