这一章我们讲讲编码
首先思考一个问题，我们如何防止一个未经授权的人获取我们的信息？我们假设帕特问麦克要艾拉电话，但麦克回答的时候有一只狗在叫，由于这个噪声，帕特不确信他真的听到了电话号码，并一次要求麦克重复一遍。有可能的大多数情况下，在一次或者两次后的重复才能保证帕特听到艾拉的电话号码。但简单的重复一个信息可数次是不可行的，例如地球上的科学家查看来自火星或者木星的照片就是一个很好的例子。在2004年，在这些星球上的机器人用照相机将每一个图片用下述的方式编码成二进制数字，一个图片会被分成1024 $\times$ 1024的格点$p_{ij}$，他一共存在$2^{10}\times 2^{10} = 1~048~576$个格点。每一个格点都带有一个$12$位的二进制数$c_{ij}$，用于描述它的颜色，密度等等。而这个$2^{10}\times 2^{10}$矩阵$[c_{ij}]$被写为一个2进制数，从第一行到第二行直到第1024行。那么在这种情况下一个图片传达的信息大约有$12~000~000$节信息，但太空是“嘈杂的”，因为存在宇宙射线会干扰电磁信号。所以多次的重复依然有可能在收到的信息中是不存在一样的消息的。所以我们来寻找一些可行的信息编码的方式，使得我们在接受信息时，错误可被察觉，当然，我们希望能够修正。
分组码
将一个信息在一个嘈杂的渠道上传输涉及三步
- 对信息编码（编制冗余码）
- 传递信息
- 对信息译码
现在我们来定义一些东西
记号：我们用$B$表示有限域$F_2$
定义：一个有限集$A$被称为字母表，若其元素为字母，设$m,n$是正整数。一个编码函数是单射的函数$E:A^m\to A^n$，$A^m$或者$A^n$的元素$\omega$称为字，集合$C = \mathrm{im} E\subseteq A^n$称为$A$上的$[n,m]$分组码，$C$的元素称为码字。若$A = B$，则一个$[n,m]$分组码称为一个二进制码。
编码涉及到冗余，这是因为一般情况下为$m<n$（理由看一开始的简介），$m$的选择是不受控制的，因为一个任意长的信息可以被细分为长度$\leq m$的更短的子字。一个传输的信息可能是从外层空间到地球的一张照片，当然，这是我们想要的。如果没有任何干扰，则任意码字$c = E(\omega)$都是可以用$\omega = E^{-1}(c)$译码，由于编码函数是一个单射，这是因为有可能出现错误，因此我们的任务就是给一个码加上足够多的冗余码，使得我们可以从中有效的回复出原来的码字。
例子
一
奇偶性校验$[m+1,m]$码
定义编码函数$E:B^m \to B^{m+1}$为
其中$b = \sum^m_{i=1} a_i$，容易验证$E$是一个单射，且有码字$C = \mathrm{im} E\subseteq B^{m+1}$ 如下给出：
那么，我们定义了一个集合$C$，它的元素由$B^{m+1}$中坐标的和为0给定。不妨取$\omega\in B^m$，则$E(\omega)$的奇偶性为偶当其的坐标的和在$B$中为0，若我们收到一个奇偶性为奇的信息，则我们知道一定在传输中出了错，若存在一对错误，则不能被察觉出，注意$2\equiv 0 \mod 2$。C的作用我们等一下再说。
二、三重重复$[12,4]$码
我们考虑定义为$E(\omega) = (\omega,\omega,\omega)$的编码函数$E:B^4\to B^{12}$，那么$C$由如下的形式组成：
我们现在开始传输$(a_1,a_2,a_3,a_4)$，设收到的消息为$y = (r_1,\cdots,r_{12})$，由于干扰，可能由
对收到的字$y$译码如下：若传输中无错误，就有$r_1 =r_5=r_9$。那么这三个码可能的取值只有2种。所以在任何情况下，至少里面的值有两个是相等的。定义$b_1$为在取得最多的值，类似的我们再定义$b_2,b_3,b_4$，那么我们重译$y$为$(b_1,b_2,b_3,b_4)$，若$r_i,r_{i+4},r_{i+8}$不全等，我们知道就存在一个错误。但情况没那么糟糕，我们可以修正这个错误。若收到一个信息$y$的错误，则$y$可以被替换成除一个字母外其余与$y$的字母一样的码字。
度量
其次，我们来了解一下度量在$A^n$上字的距离
定义：设$X$是一个集合，$X$上的度量是满足下列条件的一个函数$\delta:X\times X\to R$
- $\delta(a,b)\geq 0$，对所有$a,b\in X$成立且$\delta(a,b) = 0$ 当且仅当$a = b$
- $\delta(a,b) = \delta(b,a)$
- 三角不等式：
例 1-出租车度量
若$X = R$，则$\delta(x,y) = \mid x-y\mid $是一个度量。
该度量被称为出租车度量，记为$l^1$
例2-欧几里得度量
若$X = R^n$，$x= (x_1,\cdots,x_n)$，$y = (y_1,\cdots,y_n)$，则$\delta(x,y) = \sqrt{\sum^n_{i=1}(x_i-y_i)^2}$是一个度量，注意当$n=1$时$\sqrt{x^2} = \mid x\mid$变成了例1
例3-$L^2$度量
设$L^2[a,b]$表示所有平方可积函数构成的集合，即$L^2[a,b] = \{f:[a,b]\to R:\int^b_a f^2(x)dx < \infty\}$，则
是$L^2[a,b]$上的一个度量
例4-$p$进制度量
若$p$是一个素数，$n\in Z$是非零的，则$n = p^ku$，其中$k\geq 0$且$p\nmid u$，即$p^k$是整除$n$的p的最大方幂。记为$k =k(n)$，若我们定义$n\neq m$，$\delta(n,n) =0$和$\delta(n,m) = p^{-k(n-m)}$，则$\delta$是$Z$上的一个度量。
定义：汉明距离
设$A$是一个字母表，$\omega = (a_1,\cdots,a_n)$，$\omega’ = (a_1’,a_2’,\cdots,a_n’)\in A^n$，定义函数$\delta:A^n\times A^n\to R$如下
称为汉明距离
命题
若$A$是一个字母表，$n\geq 1$，则汉明距离是$A^n$上的一个度量。
证明： 定义$\omega=(a_1,\cdots,a_n)$和$\omega'=(a_1',\cdots,a_n')\in A^n$，显然$\delta(\omega,\omega')\geq 0$。$\delta(\omega,\omega) =0$是一定的。其次，若$\delta(\omega,\omega') = 0$，则对所有$i$都存在$a_i = a_i'$，则有$\omega = \omega'$。现在，我们只需要证明三角不等式成立即可。
若定义$\delta_i(\omega,\omega’)=1$，则$a_i\neq a_i’$，若$\delta_i(\omega,\omega’) = 0$，则$a_i = a_i’$，则
我们只需要证明对每个$i$都有$\delta_i(\omega,\omega’) \leq \delta_i(\omega,z)+\delta_i(z,\omega’)$，其中$z = (b_1,\cdots,b_n)$，若$\delta(\omega,\omega’) = 0$，则不等式成立,否则$\delta_i(\omega,\omega’) =1$，则对于$ \delta_i(\omega,z)+\delta_i(z,\omega’)$有三种可能，$0,1,2$。若等于0，则$ \delta_i(\omega,z) = \delta_i(z,\omega’)$，则对于里面的元素就有$a_i = b_i = a_i’$，但$\delta(\omega,\omega’) =1$，这是一个矛盾。
定义：最小距离
若$A$是字母表，$C\subseteq A^n$是一个码，则其最小距离是：
其中$\delta(\omega,\omega’)$是汉明距离
现在我们说一些记号
$A$上的一个$(n,M,d)$码指的是码$C\subseteq A^n$，其中$A$是一个字母表，$M =\mid C\mid$，$d$是最小距离。
然后我们给出查错与纠错的定义：
定义
设$A$是一个字母表，$C\subseteq A^n$是一个码，码$C$可以查$s>0$个错若至多$s$处改变一个码字$c\in C$使得得不到码字。
例如奇偶校验，我们更改里面一个坐标就可以把偶变成奇。
定义：最靠近码字
设$A$是一个字母表，$C\subseteq A^n$是一个码，若$y\in A^n$则称$c\in C$是一个与$y$最靠近的码字，若对所有$c’\in C$有$\delta(y,c)\leq \delta(y,c’)$
定义：纠错
设$A$是字母表，$C\subseteq A^n$是码，称码$C$可以纠$t$个错，若至多$t$处改变一个码字$c$，得到一个字$y\in A^n$且$y$的唯一最靠近码字为$c$
命题1
设$A$是一个字母表，$C\subseteq A^n$是一个$(n,M,d)$码
- 设$d\geq 2t+1$且$y\in A^n$，如果满足$\delta(y,c)\leq t$的码字$c\in C$存在的话，则它一定唯一。
- 若$d\geq s+1$，则$C$可以查$s$个错
- 若$d\geq 2t+1$，则$C$可纠$t$个错
证明1：设$c.c'$是满足$\delta(y,c) = \delta(y,c')\leq t$的码字，则利用三角不等式得到$\delta(c,y)+\delta(y,c') \leq 2t$但不同码字之间的最小距离$d(C)\geq \delta(c,c')+2t = 2t+1$，因此$c = c'$
证明2：若$\omega\neq c$与$c$至多在$s$处不同，则$0<\delta(c,\omega) \leq s$，若$\omega\in c$，则有$s\geq \delta(c,\omega)\geq d> s$矛盾
证明3：若$\omega$是改变$c$的至多$t$处所得，则$\delta(c,\omega)\leq t$，利用定义，我们设一个最靠近的码字$c'$满足$\delta(c',\omega) < \delta(c,\omega)$，由三角不等式得
例子
一个奇偶性校验$[m+1,m]$码是一个$(m+1,2^m,2)$码，是由$B^{m+1}$中具有偶数个1的字构成的，极小距离至少是2，因为改边具有偶数个1的字一处，则产生一个具有奇数个1的字，这个码可以查一个错，但不能纠错。
一个码若具有很大的极小距离，例如，一个$101-$次二重重复码，它是$[101m,m]-$码，它的编码函数$E:B^m\to B^{101m}$。将一个$m$位字重复$101$次，此时$d = 101$利用命题1的3，我们知道其可纠$101\geq 2*50+1$，也就是50个错。但$C$显然不符合实际，所以我们现在要做的就是测量码的实际性。
定义：信息率
一个$[n.m]$码的信息率定义为$\frac{m}{n}$，若$\mid A\mid = q$，那么$M = q^m$，因此一个$(n,M,d)$码的信息率就是$(\log_q M)/n$
信息率指的是，$n$个字母被用于发送$m$位的信息，例如我们刚才说的多重复码$[101m,m]$码，它的效率比较低，信息率为$\frac{1}{101}$，这个效率是非常低的，它意味着发送一段非常短的信息需要庞大数量的字母。反过来，无冗余码$[m,m]$码函数为$1_{A^m}:A^m\to A^m$。它的信息率是$1$，但它仅仅是无改变的重复信息。因此我们发现，信息率低的码可以纠多个错，但信息率大的则不能查错。所以$d$越大，它越精确。我们要做的，就是在精确和便捷找一个比较折中的方法。
线性码
设$A$是任一集合，函数$E:A^m\to A^n$的定义可能很复杂，另一方面，若$A$是一个域，则$A^m$和$A^n$都是带有标准基的向量空间，若$E$是线性变换，则我们用下面的公式可高效的描述其：存在一个$m\times n$的矩阵$G$使得$E(\omega) = \omega G$。其中$\omega$是$1\times m$的行向量。
定义：线性码
有限域$k$上的一个$[n,m]$线性码$C$指的是$k^n$的一个$m$维子空间，$C$的一个编码函数$E:k^m\to k^n$是一个满足$E(k^m)= C$的单射线性变换。
若$k = F_q$是一个具有$q$个元素的有限域，则一个$[n.m]$线性码就是一个$(n,q^m,d)$码。其中$d$是极小距离，我们来展示线性码中另一种求极小距离的方法。
定义：支撑
若$\omega = (a_1,\cdots,a_n)\in k^n$，其中$k$是域，则$\omega$的支撑定义指的是
若$C$是一个线性$(n,M,d)-$码,则$\omega$的汉明权是
汉明权就是$\omega$中非零坐标的个数，而$\omega$的零集就是$\mathrm{Supp}(\omega)$的补集:
注意的是，汉明权又可以被我们重写为$\mathrm{wt}(\omega) = \delta(\omega,0)$，其中$\delta$是汉明距离。且$0 = (0,\cdots,0)$。
命题2
若$C$是有限域$F_q$上的一个线性$(n,M,d)-$码，则
因此，$d$是非零码字的最小权数。
证明：由于$C$是子空间，那么我们由$\omega-\omega'\in C$
$\begin{aligned}
d =& \min_{w,w’\in C,w\neq w’}\delta(\omega,\omega’)\\
=& \min_{w,w’\in C,w\neq w’}\{\mathrm{wt}(\omega-\omega’\neq 0)\} \\
=& \min_{c\in C,c\neq 0}\{\mathrm{wt}(c):c\in C\}
\end{aligned}$
我们来引入一个可描述给定线性码的矩阵，为此先介绍关于一个矩阵U的划分
设$A$是一个$m\times r$的矩阵$m\times r$矩阵，而$B$是一个$m\times s$的矩阵。则
是一个$m\times (r+s)$矩阵。它的头$r$列是矩阵$A$后s列是矩阵$B$。
设$\sigma\in S_{n}$是一个置换，$Q_\sigma$是对单位矩阵使用置换$\sigma$置换其列得到的$n\times n$矩阵，若$k$是一个域，$c = (c_1,\cdots,c_n)\in k^n$是一个$1\times n$行向量，则
其中$c_{\sigma_{(j)}} = c\cdot e_{\sigma_{(j)}} = (c_1,\cdots,c_n) \cdot (0,\cdots,1,\cdots,0)$
所以，若$Q_\sigma$是一个$n\times n$的置换矩阵，则定义$\sigma_{*}:k^n\to k^n$为
置换等价
定义：域$k$上的两个$[n,m]$线性码$C,C’$是置换等价的，若存在$\sigma\in S_n$使得$\sigma_*(C) = C’$。
即$c = (a_1,\cdots,a_n)\in C$当且仅当$(a_{\sigma(1)},\cdots,a_{\sigma(n)})\in C’$
命题3
若$C$是域$k$上一个线性$[n,m]$码，则存在置换等价于$C$的线性码$C’$和一个具有形式$G = [I\mid B]$的$m\times n$的矩阵$G$，其中$I$是$m\times m$的单位矩阵，使得
因此，$C’$是矩阵$G$的行空间。
证明：设$e_1,\cdots,e_m$是$k^m$的标准基，而$\gamma_1,\cdots,\gamma_m$是$C$的某组基。我们定义$E(e_i) = \gamma_i$决定线性映射$E:k^m\to k^n$，$E$是一个单射和满的。事实上，$E$是一个同构$k^m\cong C$，那么就有$E(\omega) = A\omega^T$。其中$\omega\in k^m$是一个$1\times m$的行向量。而$A$是列为向量$E(e_i)^T$的$n\times m$的矩阵。因为我们将$k^m$的元素看做行向量而不是列向量，则重记$E(\omega) = \omega N$。其中$N = A^T$是一个$m\times n$的矩阵。
利用高斯消元法，它将矩阵$N$变为一个阶梯型矩阵$G$，存在一个非奇异矩阵$m\times n$矩阵$P$和一个$n\times n$的置换矩阵$Q_\sigma$使得$G = PNQ_\sigma = [U\mid B]$，其中$U$是一单位矩阵。现在，因为$E$是单射的，基的数量为$m$。则阶梯型矩阵$U$是$m\times m$的。因此$B$是$m\times (n-m)$矩阵。从而$G = [I\mid B]$。定义
由于$e_1G,\cdots,e_mG$是线性无关的表，那么由$m\leq \dim(C’)$。我们断言$C,C’$是置换等价的，也就是有$C’ = \sigma_*(C’)$。不妨设$c’ = \omega’G\in C’$。定义$\omega =\omega’P$和$c = \omega N$。注意$c\in C$，因为$\omega N = E(\omega) \in C$。则有
因此，$C’\subseteq \sigma_* (C)$，从而我们由$m\leq \dim(C’)\leq \dim( \sigma_*(C)) = \dim(C) =m$。那么由于$C’$是$\sigma_*(C)$的子空间而维数相同，则$\sigma_*(C)= C’$，因此$C,C’$是置换等价的码。
定义：生成矩阵
若$C$是域$k$上的一个$[n,n]$线性码，则满足$C = \mathrm{ROW}(G) = \{\omega G:\omega\in k^n\}$的$m\times n$矩阵称为$C$的生成矩阵，C的阶梯型生成矩阵具有形式$G = [I\mid B]$的生成矩阵，其中$I$是$m\times m$矩阵。
每一个线性码$C$都有一个生成矩阵，例如：任一由其行向量构成$C$的一组基的$m\times n$的矩阵就是$C$的一个生成矩阵。再利用命题3，我们可以假设每一个线性码都有一个阶梯型生成矩阵。
例1
一个奇偶性校验$[m+1,m]$码$C$，码字是满足$\sum b_i=0$的$c = (b_1,\cdots,b_{m+1})\in B^{m+1}$，这些码构成一个子空间，因此$C$是一个线性码。现在，我们看看映射$E:B^m\to B^{m+1}$，它被定义为
其中$b = \sum^m_{i=1} a_i$，显然这是一个线性变换，它的阶梯型生成矩阵可以写为如下的$m\times (m+1)$的矩阵
用记号划分，$G = [I\mid B]$，其中$I$是$m\times m$的单位矩阵，$B$是所有元素为1的列向量。
例2
三重复$[3m,m]$码的阶梯型生成矩阵是$G = [I\mid I\mid I]$
命题4
设$G = [I\mid B]$是域$k$上的一个线性$[m+p,m]$码的$m\times (m+p)$的阶梯型生成矩阵。则$\omega\in k^{m+p}$落在$C$中当且仅当$\omega[-B^T\mid J^T] =0$其中$J$是$p\times p$的单位矩阵。
证明：记$(m+p)\times p$的矩阵$[-B^{T}\mid J]$为$H$。由于$C$是$G$的行空间，那么每个码字$c$是$G$的行的一个线性组合。$G$的第$i$行是$e_i G$，其中$e_i,i = 1,2,\cdots,m$是$k^m$的标准基。那么$c = \sum_i a_i(e_iG)$，其中$a_i\in k$。我们只要证明$GH^T =0$即可。因为这样子就得到$cH^T = \sum_i a_ie_iGH^T = 0$
$v,w\in k^{m+p}$的点积等于矩阵的乘积$v\cdot w = vw^T$。而$GH^T$的$ij$位元素是$\mathrm{ROW_G(i)} \cdot \mathrm{\mathrm{COL}_{H^T(j)}} = \mathrm{ROW_G(i)} \cdot \mathrm{\mathrm{COL}_{H^T(j)}}^T$，那么$G$的第$i$行是
而$H^T$的第$j$列是$H^T(e’_j)^T$，其中$e_1’,\cdots,e_p’$是$k^p$上的标准基。且$(e_j’)^T$是列向量。那么
但$e’_jB^T$是$B^T$的第$j$行，这是$B$的第$j$列。那么
且
因此$GH^T$的$ij$位元素是
注意这里我们用$(0,\cdots,e_i,\cdots,0)$去简写为$e_i$，由于$e_i$是$1\times m+p$的行向量而$e_j’$是$1\times m+p$的行向量那么对于$e_i$做内积我们得到$b_{ij}$，同样的我们得到$-b_{ij}$，那么结果就是0。
反之，我们考虑其次方程组$[-B^T\mid J]^Tx^T = 0$和其解空间$S = \{v^T\in k^{m+p}:[-B^T\mid J]^Tv^T = 0\}$，那么就有$v[-B^T\mid J] = 0$，由我们一开始写的就有$C\subseteq S$。但$\dim(C) = m$,，而$\dim(S) = m+p-r$，其中$r = rank([-B^T\mid J]^T) =p$，那么就有$\dim(S) = m+p-p=m$，由$C = S$，因此，若$w[-B^T\mid J]^T = 0$，那么$w\in S$有$W\in C$
定义：奇偶校验矩阵
设$C$是域$k$上的一个线性$[(m+p),m]$码，一个$m\times (m+p)$的句子$H$称为$C$的一个奇偶性校验矩阵，若对所有$w\in k^{m+p}$都有$wH^T =0$当且仅当$w\in C$
定义：
若$A$是域上一个$m\times n$矩阵，其中$m<n$，则由它的列组成的表是线性相关的，定义：
若$A$是一个$m\times n$的矩阵，$m<n$和$\mathrm{rank} = r$，那么
推论1
设$C$是域$k$上的一个线性$[n,m]$码，$H$是$C$的一个奇偶校验矩阵，则
- $d(C) = \mu(H)$
- $d(C) \leq m+1$
证明：设$\beta_1,\cdots,\beta_n$是$H$的列向量，由于$H$是$C$的一个奇偶校验矩阵，那么字$y = (y_1,\cdots,y_n)\in C$当且仅当$yH^T = 0$。而$yH^T =0$当且仅当$Hy^T =0$，即
设$d(C) =d $，取权位$d$的码字$y\in C$，设$y_{i_1},\cdots,y_{i_d}$为$y$的非零坐标。由于$y$是一个非零的码字，所以
则这个线性组合是线性相关的。那么$\mu(H) \leq d$。另外，我们设存在线性相关表，但长度有$p<d$，则存在不全为零的纯量$z = z_{j_1},\cdots,z_{j_p}$，将$z$扩充成一组基，那么就有$Hz^T = 0$使得$z\in C$但$d(z) \neq d$矛盾。
证明2：$\mu(H)\leq r+1$，其中$r = \mathrm{rank}(H) =r$，因此$r =m$
若$k$是一个域，其中$f(x)\in k[x]$，$I = (f(x))$是由$f(x)$生成的主理想。则$k[x]/I$是$k$上的一个向量空间，基为$1,z,\cdots,z^{n-1}$。并且我们可以找到一个与其同构的$n$维线性空间$k^n$。我们记$k^n$中的字为$(a_0,\cdots,a_{n-1})$而不是$(a_1,\cdots,a_n)$。则$(a_0,\cdots,a_{n-1})\to a_0+\cdots+a_{n-1}z^{n-1}$是$k^n\to k[x]/I$的一个同构。
定义：循环码
定义域上长度为$n$的循环码是一个满足以下条件的线性码$C$
命题5
令$k$是有限域，再令$I = (x^n-1)$是由$x^n-1$生成，在$k[x]$中的主理想。再令$z=x+I$。则$C\subseteq k[x]/I$是循环码当且仅当$C$是交换环$k[x]/I$中的主理想。更多的，$C = (g(z))$，其中$g(x)$是$x^n-1$在$k[x]$中的首一因子
证明： 令$C$是$k[x]/I$中的理想，再令$c = a_0+a_1z+\cdots +a_{n-1}z^{n-1}$，则$C$包含$zc = a_0z+a_1z^2+\cdots +a_{n-2}z^{n-1} + a_{n-1}z^n$。但$z^n =1$。这是因为$z$是$x^n-1$的根。那么$a_{n-1}+a_0z+\cdots a_{n-2}z^{n-1}\in C$，因此$C$是循环的。
反之，我们设$C$是循环码，由于$C$是线性码，$C$对$k$中元素在加法和乘法下封闭。乘$z$相当于是向左移动一步。然后就可以让$a_{n-1}$变成常数项。由于对加法和乘法封闭，那么$0\in I$，取$f(z),g(z)\in k[x]/I$，那么$f+g = (a_0+b_0)+\cdots + (a_{n-1}+b_{n-1})z^{n-2}\in C$。最后，由于$z$是$x^n-1$的根，那么对于任意的$n$，$z^ng(z)$是关于字$(a_0,\cdots,a_{n-1})$的一个置换，那么依然在$C$中，综上所述。$C$是一个理想
现在，令$\beta:k[x] \to k[x]/I$是一个自然映射。且考虑逆像$J = \beta^{-1}(C) = \{f(x)\in k[x]:f(z)\in C\}$。现在我们利用下面的习题辅助证明：
令$R,S$是交换环，再令$\psi:R\to S$是同态，其中$\ker\psi = I$。若$J$是$S$中的理想，证明$\psi^{-1}(J)$是理想且包含$I$
证明：由于$\psi$是同态，$\ker =I$，那么有$\psi(0) =0$，其次，由于$I$是$S$中的真理想，那么就有$\psi(a+b) =\psi(a)+\psi(b) =0$成立，其中$a,b\in I$。最后，由于$a\in R,b\in I$使得$\psi(ab) = 0$。都在$J$中，一定的，对于$\psi^{-1}(J)$就有$a+b,ab\in\psi^{-1}(J)$中。因此$\psi^{-1}(J)$是包含$I$的理想。
那么$J$是一个在$k[x]$中包含$x^n-1$的理想。但$k[x]$中的理想都是主理想。那么就存在一首一多项式$g(x)\in k[x]$使得$J = (g(x))$成立。因此$x^n-1\in J$。我们有$x^n-1=h(x)g(x)$对某个多项式$h(x)$成立。所以，$g(x)\mid (x^n-1)$。最后，由于$J$是由$g(x)$生成的，它表明$C = \beta(J)$是由$\beta(g(x))=g(z)$生成的。
定义：生成多项式
令$C\subseteq k[x]/I$是循环码，其中$I = (x^n-1)$。若$C = (g(z))$，其中$g(x)\in k[x]$。我们说$g(x)$是生成$C$的生成多项式。其中$z = x+I$
由上面的命题5，长度为n的一个循环码的生成多项式$g(x)$是$x^n-1$的一个因子。
引理1
若$C$是域$k$上长度为$n$的循环码，其生成多项式为$g(x)$，则$\dim(C) = n-\deg(g)$
证明：由于$g(x)\mid (x^n-1)$，那么就存在一个理想的包含$I=(x^n-1)\subseteq (g(x))=J$。$k[x]$和其商环也仅仅是作为$k$上的向量空间。那么由$h(x)+I \to h(x)+J$给出的陪集的拓展函数：$\gamma:k[x]/I\to k[x]/J$是一个满的线性变换。现在，为了计算$\ker\gamma$，我们考虑一个关系：
其中$\alpha,\beta$是自然映射，而$\beta = \gamma\circ \alpha$。并且$\alpha,\beta,\gamma$是满射。我们引入习题来辅助证明：
令$A,B$和$C$是群，且令$\alpha,\beta,\gamma$是同态映射使得$\gamma\circ\alpha =\beta$。若$\alpha$是满射，证明$\ker\gamma = \alpha(\ker\beta)$
证明：$\gamma\circ\alpha = \beta$，我们设$a\in \ker\beta$，那么$\beta (a) = \gamma\circ\alpha (a)=1$，那么就有$\beta(\ker\beta) = \gamma\circ\alpha(\ker\beta) =1 \Rightarrow \ker\gamma = \alpha(\ker\beta)$
其次，若有$b\in \beta$且属于$\ker\gamma$。由于$\alpha$是满射，那么就存在$\alpha^{-1}$的一个集合：$\alpha^{-1}(\ker\gamma) = \alpha^{-1}(\alpha(\ker\beta))=\ker\beta$
让我们继续证明。那么
其中$z=x+I$，我们把其看做线性空间。那么由第一同构定理，$(k[x]/I)/C\cong k[x]/J$，因此
但$\dim(k[x]/I) = \deg(x^n-1) =n$和$\dim(k[x]/J) = \dim(k[x]/g(x))=\deg(g)$，因此$\dim(C) = n-\deg(g)$
引理2
若$C$是长度为$n$的循环码，其生成多项式$g(x) =g_0+g_1x+\cdots+g_sx^s$，则$C$的生成矩阵是$(n-s)\times n$矩阵
证明：由于$C$是理想，那么$g(x),xg(x),x^2g(x)\cdots x^{n-s}g(x)$都是码字，而且这些码字对应于$G$的行。记$G = [T\mid B]$，其中$T$是$(n-s)\times(n-s)$的子阵，由$G$的前$n-s$列组成。而$T$是一个上三角矩阵，它的对角线的元素都是$g_0$，那么$\det(T) =g_0^s$。现在$g_0$是$g(x)$所有乘积的根。但$g(x)$的根是单位根。因为$g(x)\mid (x^n-1)$，所以$g_0\neq 0$。所以$\det(T)\neq 0$。那么前$n-s$行是线性无关的。所以$\dim(C) =n-s$。那么这$n-s$行构成一个$C$的基，所以$G$是$C$的生成矩阵。
命题6
有限域$F_q$存在$q$个元素，设$n$是正整数，则$F_q$的某个扩域存在一个$n$次单位根在当且仅当$(n,q)=1$
Proof:我们设$(n,q)=1$和$E/F_q$是$f(x)=x^n-x$在$F_q$上的分裂域。现在，导数$f’(x) = nx^{n-1}-1\neq 0$，那么$(f,f’)=1$，我们知道$f(x)$是无重根的。若$K$是所有根的集合，由于$f(x)$的根都是$n$次单位根，则$K$是阶为$n$的乘法群。但$K$是循环群，则$K$的生成元一定是$n$次单位根
反之，我们设存在一个$n$次单位根，现在$q = p^s$对某个素数$p$成立。若$(n,q)\neq 1$，则$p\mid n$，那么$n =pu$对某个整数$u$成立。则$x^n-1 = x^{pu}-1 = (x^u-1)^p$，那么我们发现所有$n$次单位根组成的集合元素个数少于$n$，那就不存在$n$次单位根了。
定理介绍的足够多了，我们来构造一些能纠很多错的码。
定理1 Bose-Chaudhuri-Hoequenghem
令$F_q$是具有$q$个元素的域，再设$n$是正整数使得$(n,q)=1$，并且$C$是由$g(x)$生成的循环码。若$\zeta$是$n$次单位根，且它连续的幂次$\zeta^u,\zeta^{u+1},\cdots,\zeta^{u+l}$是$g(x)$的根，其中$u+l< n$，则$d = d(C) \geq l+2$
证明：码字$c = (c_0,c_1,\cdots,c_{n-1})\in (F_q)^n$确定一个多项式$c_0+c_1x+\cdots+c_{n-1}x^{n-1}\in F_q[x]$，它的权$\mathrm{wt}(c)$是系数中不为零的数量。利用命题2，我们开始只需要证明每个非零码字有至少$l+2$个非零系数。我们用反证法，设存在权$\mathrm{wt}(c)< l+2$的码字$c$。那么$c(x) = c_{i_1}x^{i_1}+\cdots+c_{i_{l+1}}x^{i_{l+1}}$，其中$i_1 < \cdots <\cdots <i_{l+1}$。若$\alpha\in F_q$，那么$c(\alpha)$可以写为
现在我们构造一个$(l+1)\times(l+1)$矩阵$W$，其第$j$列由$\zeta^{n+j}$得到，其中$0\leq j\leq l$。
若$c_* = [c_{i_1}~\cdots ~c_{i_{l+1}}]$，那么由题设，$\zeta^u$的连续幂次是一个$c[x]$的根，则
把$W$变一下，我们有发现每一列都是第一个元素的幂次，只需要用第一行去除剩下的行就得到简化的$(l+1)\times (l+1)$矩阵$V$：
这是一个行列式为范德蒙行列式的矩阵，那么其行列式的值
若$\zeta^{i_j}$不是互异的，那么行列式的值是0。这和我们一开始声称的一系列n次单位根矛盾。所以$\det(W)\neq 0$。其次，由于$c^T_*\neq 0$，$Wc^T_*=0$，这是一个矛盾，因为$W$是非退化的，但由$c^T_* \neq 0$推出$W = 0$。因此权$<l+2$的码字不存在，$d(C)\geq l+2$
定义：BCH-code
域$k$上的线性码是长度为$n$的BCH码，我们说他是一个具有最小可能次数的生成多项式$g(x)$的循环码，且$g(x)$的根中存在连续方幂$\zeta^{u},\zeta^{u+1},\ldots,\zeta^{u+\ell}$，其中$\zeta$是$n$次单位根且$0\leq u\leq u+l < n$
引理3
设$C$是一个长度为$n$的$BCH$码，其生成多项式是$g(x)$，若连续方幂$\zeta^u,\zeta^{u+1},\cdots,\zeta^{u+l}$出现在$g(x)$的根中，其中$l =2t$或者$l=2t+1$且$u+l < n$，则$C$可以纠t个错
Proof：利用定理1，我们知道$d(C) \geq l+2 \geq 2t+1$，所以$C$能纠t个错
引理4
对每个素数$p$和任意正整数$t$，则存在$F_p$上的$BCH$码$C$可以纠$t$个错。
Proof： 我们令$k = F_q$，其中$q$是$p$的幂次1且$2t+1 \leq q-1$。那么$F_q$是一个$q-1$阶的乘法群。它的生成元$\zeta$是$q-1$次的本元单位根。因此$\zeta,\cdots,\zeta^{2t+1}$是互异的元素，对每个$j$，我们可以利用根构造不可约多项式$h_j(x)\in k[x]$使得其以$\zeta^j$作为根，最后，定义
并定义$C$是由$g(x)$生成的$BCH$码，利用定理$1$我们知道$d(C)\geq 2t+1$，然后再利用引理3即可证明完毕。
例子
我们来讨论$F_8$，它是一个元素非零阶为7的乘法群，那么他有一个$7$次本原单位根$\zeta$，也是生成元。那么就有一些不可约多项式$g(x)\in F_2[x]$将$\zeta$作为其根。那么$\deg(m) = 3 = \dim_{F_2}(F_8)$。事实上，这些多项式是$x^3+x+1$和$x^3+x^2+1$。他们在$F_2[x]$中是不可约的。那么，我们首先来选择一个根$\zeta$作为第一个多项式的根，它是
由于$1 +1 \equiv 2 =0$，那么$F_8$作为$F_2$上的扩张域特征为$2$。其次，由于加法交换，那么其加法表是一个对称矩阵，我们只需要计算其上三角部分即可
利用这个表，我们可以清楚的看到根和根之间的联系
以此类推可以得到其他元素。
定义：里德-所罗门码
一个域$F_q$上的里德-所罗门码是由生成多项式
生成的$\mathrm{BCH}$码，其中$1<d < q-1 $，且$\zeta$是$F_q$中$q-1$次本原单位根。
推论2
由上面的定义，这里存在一个可纠$t$个错，在$F_{2^{2t+1}}$上的$\mathrm{BCH}$码，且信息率是$1-[2t/(2^{2t+1}-1)]$
证明：设$\zeta$是$F_q$中的本原元素，其中$q = 2^{2t+1}$，那么由$\mathrm{BCH}$码的定义，其长度为$q-1$，现在我们定义$g(x)$是
则由定理1，$g(x)\geq 2t+1$。那么现在，$\dim(g)=2t$，$C$的长度为$q-1$，现在，我们只需要求出$C$的秩就可以得到信息率了。
由于$\deg(g)=2t$，而$\dim(C) = q-1-2t$，所以$\dim(C) = 2^{2t+1}-1$。$C$是特别的线性码，他的生成矩阵$[I\mid B]$中$I$是满秩的，因此$\dim(C)$就是原码的长度，而码长$q-1$，因此信息率就是$m/n = \frac{q-1-2t}{q-1} = 1-[2t/(2^{2t+1}-1)]$
利用引理2和里德-所罗门码，我们构造一些例子
例子
在$F_7$中，$[3]$是一个$6$次本原单位根，用多项式
为生成多项式的码$C$是$F_7$上可纠2个错的里德-所罗门码，那么$C$的一个生成矩阵是
那么$C$就是行空间$\mathrm{Row}(G)$
译码
到目前为止，我们考虑了线性码及其编码函数，为了解码，我们必须考虑由传输功能引起的错误，因此解码功能必须能够覆盖这一错误。
定义：错误向量
令$C\subseteq k^n$是一线性码，若$y\in k^n$且$c\in C$。错误向量指的是：
当然，$\mathrm{wt}(\epsilon)$就是$y$和$c$中不相同的非零坐标个数。
向量空间$F^n_q$是一个加法交换群，$C$是一个子群，给定$y$，则所有错误向量$y-c$的总体就是陪集$y+C$，$c\in C$。在这层意思上谈论最近码字的时候就是在谈错误向量$\epsilon(y,c) = y-c$在$y+C$中权最小的那个。也就是考虑形如$y-c$中$\delta(y,c) = \mathrm{wt}(y-c)$。
定义：陪集的头字
若$C\subseteq F^n_q$是线性$[n,m]$码，而$y+C$是$F^n_q$中的一个陪集，则陪集的头字指的是一个权最小的向量$e\in y+C$
定义：和声
设$H$是一个线性$[n,m]$码$C\subseteq F^n_q$的检验矩阵，若$y\in F^n_q$，则它的和声指的是$S(y) = yH^T$
$C$的检验矩阵$H$不必是唯一的，但和声$yH^T$却依赖$H$的选取，为对一个收到的字$y$进行译码，首先计算它的和声$S(y) = yH^T$，接着计算陪集的头字$e_j$的合身$S(y) = yH^T$，直到$S(e_j) = S(y)$成立。但只有一个这样的陪集$e_j+C$成立，因为若$S(e_j)=S(e_k)$，我们就有$S(e_j-e_k) =0$,$e_j-e_k\in C$，从而得到$e_j+C = e_k+C$。若$c = y-e_j$是与$y$最接近的码字，则$y$译成$c$。但这种方法还是不太实用，因为$C$是$F_q$上的一个$[n,m]$分组码，则$C$存在$q^{n-m}$个陪集。
注：一般来说，我们在考虑向量$y = (y_0,\cdots,y_{q-2})\in F_q^{q-1}$看做是多项式$y(x) = y_0+y_1x+\cdots+y_{q-2}x^{q-2}\in F_q[x]$。
命题7：
设$\zeta$是$F_q$的本原元素，$C\subseteq F^{q-1}_q$是$F_q$上的一个纠$t$个错的里德-所罗门码，其生成多项式$g(x) = (x-\zeta)(x-\zeta^2)\cdots(x-\zeta^{2t})$，定义$2t\times (q-1)$的矩阵
- 若$y = (y_0,\cdots,y_{q-2})\in F^{q-1}_q$，则
其中$y(\zeta^i) = y_0+y_1\zeta^i+\cdots+y_{q-2}\zeta^{i(q-2)}$
- 设$f(x) = f_0+f_1x+\cdots + f_rx^r\in F_q[x]$，其中$r\leq t$，若我们记$f = (f_0,\cdots,f_r,0,\cdots,0)\in F^{2t}_q$，则
- U是$C$的一个检验矩阵
- 若$e = y-c$是一个错误向量，则$e$和$y$有相同的和声
因此对所有的$j\leq 2t$，$e(\zeta^i) = y(\zeta^i)$
证明：注意到$U$上$F_q$上的一个矩阵，这是因为$\zeta\in F_q$，而$yU^T$的$ij$位元素是点积
因此
证明2： $fU$的$ij$位元素是点积
证明3： 若$C\subseteq F_q^{q-1}$是一个以$g(x)$为生成多项式的循环码，那么$y = (y_0,y_1,\cdots,y_{q-2})\in F_q^{q-1}$落在$C$中当且仅当$y(\eta) = 0$，不难证明，$g(x)$生成$C$，$C$是一个主理想，是$k[x]/I$中由$g(x)+I$生成的主理想，$I = x^n-1$，$y\in C$则$y = (g)$，存在$f(x)\in k[x]$满足$y(x)+I = f(x)g(x)+I$，因此$y-fg\in I $。那有
由于$\eta$是$g$的根，由命题5，$g(x)\mid (x^n-1)$，因此$\eta^n =1$我们有$y(\eta) = 0$
其中$\eta$是$g(x)$的根。因此，若$U$是检验矩阵，就有$yU^T = 0$，事实上也确实如此。所以$U$是检验矩阵。
证明4：最后，$eU^T = (y-c)U^T = yU^T-cU^T = yU^T$。
设$C$是$F_q$上的一个纠t个错的里德-所罗门码，$U$是上述命题中的检验矩阵，通过求错误向量$e = y-c$来译接收到的字$y$，其中最困难的一步是确定$e$的非零坐标的位置。反正，若$C$是二进制码，则$e$的非零坐标实际上决定了e
若$A=[a_{ij}],B=[b_{ij}]$是域$k$上的$m\times n$矩阵，则他们的阿马达积是$A\circ B = [a_{ij}b_{ij}]$，特别的，$1\times n$向量的阿达马积被定义为
定义：错误定位向量
若$e$是错误向量，则$e\circ u = 0$的非零向量称为错误定位向量。
引理5
若$e= (e_0,\cdots,e_{q-2})$和$u=(u_0,\cdots,u_{q-2})$都在$F^{q-1}_q$中，则$e\circ u = (0,\cdots,0)$可推出
证明：设$e\circ u= 0$对所有$j$都得到$e_ju_j=0$，若$j\in \mathrm{Supp}(e)$，则$e_j \neq 0$，但$e_ju_j =0$，其中元素在域中，那么就有$u_j = 0$，所以$j\in Z(u)$
定义：错误定位多项式
设$C$是$F_q$上的一个可纠$t$个错的里德-所罗门码，设$y$是接收到的字，设$e = y-c = (e_0,\cdots,e_{q-2})$是错误向量，若$\mathrm{wt}\leq t$且$\mathrm{Supp}(e) \leq t$，且$\mathrm{Supp(e)} = \{j_1,\cdots,j_r\}$，其中$r\leq t$，则 错误多项式指的是
我们记$f_r = 1$，把多项式变成$f = (f_0,f_1,\cdots,r_{r-1},1,0,\cdots,0) \in F_q^{2t}$。（因此我们就可以定义$fU$了，其中U是检验矩阵）
引理6
设$C$是$F_q$上一个纠$t$个错的里德-所罗门码，设$U$是命题7中的检验矩阵，如果$y$是一个接收到的字，$e = y-c = (e_0,\cdots,e_{q-2})$是一个满足$\mathrm{wt}(e)\leq t$的错误向量，若$fU = (f(1),\zeta f(\zeta),\cdots,\zeta^{q-2} f(\zeta^{q-2}))$，其中$f = (f_0,f_1,\cdots,f_{r-1},1,0,\cdots,0)\in F^{2t}_q$是错误定位多项式，则$U$是一个错误定位向量且
证明：设$\mathrm{Supp}(e) = \{j_1,\cdots,j_r\}$，其中$r\leq t$，设$f(x) = \sum^r_{i=1}f_ix^i$是错误定位多项式，为了证明$U$是错误定位向量，我们断言有$e\circ u = 0$，若$j_v\in \mathrm{Supp}(e)$，则由引理5，有$f(\zeta^{j_v}) =0$，进而有$e_{j_v} u_{j_v} = 0$，若$j_v\not\in\mathrm{Supp}(e)$，则$e_j =0$，所以$e\circ u = 0$。我们有$u$是错误定位向量。由引理5可知$\mathrm{Supp}(e) \subseteq Z(u)$。
若$u_j= 0$，但对某个$j\not\in \{j_1,\cdots,j_r\}$得到$\zeta^j f(\zeta^j) = 0$，进一步有$f(\zeta^j)=0$，我们就发现了另一个根，但多项式的次数$r\leq t$，这是一个矛盾，我们得到了r+1个根，所以这不可能是一个真包含的关系，有$\mathrm{Supp}(e) = Z(u)$
定义：和声矩阵
设$C$是$F_q$上一个能纠$t$个错的里德-所罗门码，设$\zeta$是一个$F_q$的本原根，$y = (y_0,\cdots,y_{q-2})\in F^{q-1}_q$，$e=y-c$是一个满足$\mathrm{wt}(e) = r\leq t$的错误向量，则和声矩阵指的是$r\times r$矩阵
命题8
设$C$是$F_q$上一个纠$t$个错的里德-所罗门码，$y = (y_0,y_1,\cdots,y_{q-2})\in F_q^{q-1}$，$e = y-c$是一个满足$\mathrm{wt}(e) = r\leq t$的错误向量，那么
$e$和$y$具有相同的和声矩阵，$\sum(e) = \sum(y)$
若$f(x) = f_0+f_1x+\cdots+f_{r-1}x^{r-1} +x^r$是错误多项式，则
是线性方程组
的一个解，其中$h=[-y(\xi^{r+1}),-y(\xi^{r+2}),\cdots,-y(\xi^{2r})]$
和声矩阵$\sum(y)$是非奇异的
证明 利用命题7的三，我们知道$e$和$y$的和声是一样的，再由二，对所有$j< 2t$，有$e(\zeta^j) = y(\zeta^i)$，因此$\sum(e) = \sum(y)$
证明2： 对$v = 1,2,\cdots,r$，每一个$\zeta^{ij_v}$是错误多项式$f(x)$的一个根，则$f(\zeta^{ij_v}) = 0$是一定的，现在，对每个$i = 1,2,\cdots,r $，我们用$\zeta^{ij_v}$乘在方程中，展开则有
$f_0\zeta^{ij_v}+f_1\zeta^{(i+1)j_v}+\cdots+\zeta^{(i+r)j_v} = 0$ 其次，我们回忆$e(x) = e_{j_1}x^{j_1} + \cdots + e_{j_r}x^{j_r}$，我们将$v = 1,2,\cdots,r$的方程连加，就得到
现在，这是$i=1,2,\cdots,r$中的一条方程，只需要吧这r条方程联立起来，那么他就是我们要求的方程，而这$r$个方程构成一个非奇次$r\times r$的线性方程组
其中$h = [-y(\zeta^{r+1}),\cdots,-y(\zeta^{2r})]^T$。由命题1，有$\sum(e) = \sum(y)$，那么命题得证。
最后，命题8可以求出错误向量$e$的错误位置$j_1,\cdots,j_r$，而通过解线性方程组$\sum(y)f^T =h^T$可以求出错误定位多项式$f(x)$，其唯一性由和声矩阵的非奇异性保证。$f = (f_0,f_1,\cdots,f_{r-1})$，那么$f(x)=f_0+f_1x+\cdots+f_{r-1}x^{r-1}+x^r$。首一多项式$f(x)$确定错误定位向量$u = fU$，其中$U$是命题7的检验矩阵。而$\{j_1,\cdots,j_r\} \mathrm{Supp}(e)=Z(u)$。要译码$y$，只需要去掉元素$y_{j_1},\cdots,y_{j_r}$，将这些错误元素替换为真实值即可。现在我们给出一个例子，他可以译里德-所罗门码，还可以推广到所有$BCH$码上。
定理1
设$C$是$F_q$上一个可纠$t$个错的里德-所罗门码，$y$是一个字，存在一个满足$\mathrm{wt}(e)\leq t$的错误向量$e$，则$y$可以被有效译码。
证明：这很简单，只要错误的地方少于我们给出修正的地方，那么我们就能修正，利用命题8，我们求出错误向量$e$不为零的位置$j_1,\cdots,j_r$，由于$\mathrm{Supp}(e) = Z(fU)$，其中$U$是检验矩阵。
我们设$r = t$，设$U^*$是去除$j_1,\cdots,j_r$行外的其他行得到的矩阵。
现在引入如下命题：
设$Ax = b$是域$k$上的一个$m\times n$的矩阵，试证明存在一个满足$x_{j_1} = 0 = x_{j_2} = \cdots = x_{j_s}$的解$x = (x_1,\cdots,x_n)$当且仅当$m\times (n-s)$方程组$A^*x^* = b$有解，其中$s\leq n$，$A^*$是从$A$中删掉第$j_1,j_2,\cdots,j_s$列后得到的矩阵。
回到证明上来，我们可以通过解$U^*e^* = Uy^T$求出$e$的非零坐标。我们约定一下符号：$e^*$表示$1\times t$向量$(e_{j_1},\cdots,e_{j_t})$。由上引入的习题，我们知道更小的非奇次线性方程是可解的，只需要用高斯消元法。现在若$\mathrm{rank}(U^*)= t$，那么$U$的任意$t$行就构成一个非奇异的$t\times t$的范德蒙矩阵。而且其行是不同的，所以$U$的任意$t$行构成一线性无关的表，那么只要有$e^*$，我们就能得到$e$。注意，求出来的是非零值，其他地方补上0即可。那么我们就能以此得到一个码字$c = y-e$，并且$c$是唯一的，我们吧$y$译为$E^{-1}(c)$，其中$E$是编码函数。
例子
我们设$C$是$F_7$上一个纠2个错的里德-所罗门码。$3$是其中$6$次本原单位根：
那么$t = 2,q=7$，它的检验性矩阵是下列的$4\times 7$矩阵
设存在一个满足$\mathrm{wt}(e)\leq 2$的错误向量$e$，我们来译字$y = (4,0,5,1,0,1)$
- 和声$S(y) = yU^T = (4,1,0,3)$
- 和声矩阵是$2\times 2$矩阵，它的元素由$y\cdot U^T = (y(\zeta),y(\zeta^2),\cdots,y(\zeta^{2t}))$
现在，$t=2$，我们只需要计算$y(\zeta),y(\zeta^2),y(\zeta^3)$，即可，那么和声矩阵就是
- 现在，解$\sum(y)f^T - h^T$，$h^T = (0,4)^T$，就有$f = (4,5)$，错误多项式为$f(x) = 4+5x+x^2$
然后计算$u = fU = (3,0,1,0,6,4)$，那么$Z(u) = \{1,3\}$，所以$\mathrm{Supp}(e) = \{1,3\}$，即错误向量的非零位置在1和3，现在我们求这两个数字
解$U^*e^* = Uy^T$
那么$e^* = (1,6)$，错误向量就是$e=(0,1,0,6,0,0)$，最后$y$就是
被译为$E^{-1}(c)$，$E$是编码函数。