Introduction
编码的目的：将信息通过某种方式编码后传输(比如ASCII码将字母变成8位01串)，使之满足下面的某些性质：
- 编码速度快。
- 编码结果易于传输。
- 解码速度快。
- 极大化信息传输率(可以理解为用尽可能少的长度表示尽可能多的信息)。
- 检测/纠正传输错误。
Basic Concepts
Notations
- code alphabet. 用于编码的字符集, 字符集中的元素成为code symbol, 一般用$q$表示字符集的大小。
- 通常用字母C表示编码的集合，其中的元素成为codeword, 每个codeword可以看做是长度为$n$的向量, 向量的每个分量取值来自code alphabet。
- (n, M) code. 长度为$n$, 元素个数为$M$的编码集合。
- Information rate. $\frac{\log_q{|C|}}{n}$
Hamming Distance
Hamming distance $d(x, y)$：逐位比较$x, y$的每一位, 有多少位不同, 即$d(x, y) = \sum_{i=1}^n[x_i\neq y_i]$。
最重要的一点，Hamming距离是满足三角形不等式的, 即$d(x, y) \leq d(x, z) +d(z, y)$.
证明:
实际上Hamming distance对应向量的一范式($d(x, y)=||x-y||_1$), 可以参考关于向量范式的三角形不等式的证明。不过我们没有定义两个码的减法操作。
因为
所以只要证明$[x_i \neq y_i] \leq [x_i\neq z_i] + [y_i \neq z_i]$.
如果$x_i = y_i$显然成立。
如果$x_i \neq y_i$, 左边是1，右边不管$z_i$取0还是1，总有一个是1.
定义编码的距离
Linear Code
线性码就是说$C$是一个线性空间, $C$中的codeword满足线性空间的加法减法数乘的封闭性等。
一般的, 我们默认取线性空间$V:=F_q^n$, 也就是说$C$中的codeword是$n$维向量，向量的每一维取自有限域$F_q$.
$C$是线性码当且仅当满足线性空间的八条性质。$\forall u, v, w\in C, \lambda, \mu \in F_q$ 满足:
- $u+v \in C$.
- $(u+v)+w = u+(v+w)$.
- 存在零元$0 \in C$, $0+v=v+0=v$.
- $u+v=v+u$.
- $\lambda u \in C$.
- $\lambda(u+v) = \lambda u + \lambda v$.
- $(\lambda \mu) u = \lambda (\mu u)$.
- 设$1$是$F_q$的单位元, $1u=u$.
另外有一个小定理，在之后经常会用到:
设$C$是定义在$F_q$上的线性空间$V$的一个非空集合，$C$是 $V$的子空间当且仅当
Definition
- 定义$C$的正交补码$C^{\perp}:= \{v \in F_q^n, v\cdot u = 0 \forall s \in C\}$. 容易验证$C^{\perp}$也是线性码, 且$(C^{\perp})^{\perp} = C$
- ${<}S{>}$表示$S$生成的子空间。 用线性代数的知识很容易证明$dim({<}S{>})+dim(S^{\perp}) = n$.
- 定义某个codeword的重量$w(x)$为$x$非0的分量个数。容易证明$d(C):= \min_{x \in C}{w(x)}$.
证明:- 若$d(C) = d(x, y)$, 那么$x-y \in C$, 因此$d(C) = w(x-y) \geq \min_{x \in C}{w(x)}$.
- 反过来, 设$w(x_0) = \min_{x \in C}{w(x)}$, $ d(C) \leq d(x_0, 0) = w(x_0) = \min_{x \in C}{w(x)}$.
- 用-linear code表示长度为$n$, 维度为$k$的线性码。
Generator Matrix, Check Matrix
- 线性码$C$的generator matrix $G$: 大小为$k*n$, $k=dim(C)$, $k$行恰好是$C$的一组基。
- 线性码$C$的check matrix $H$, 大小为$(n-k)*n, k = dim(C)$, $n-k$行恰好是$C^{\perp}$的一组基。容易验证$HG^T = GH^T = 0$.
下面是一些有用的性质，有些证明我个人认为比较简单，就略去了。
性质1:
$v \in C^{\perp} \Longleftrightarrow vG^T = 0$.
简单地说，就是一个向量和$C$中所有向量点积为0当且仅当它和一组基里的所有向量点积为0.
同理有$v \in C \Longleftrightarrow vH^T = 0$.
性质2：
一个$(n-k)*n$的矩阵$H$是check matrix当且仅当$H$的行线性无关，并且$HG^T = 0$.
性质3：
假设$H$是线性码$C$的check matrix。$d(C) = d$当且仅当$H$的任意$d-1$列线性无关, 存在$d$列线性相关。
证明：
设$h_i$表示$H$的第$i$, $v\in C$, $w(v)=e$, $\{i_1, i_2, \cdots, i_e\}$是$v$非零分量的下标。
根据性质1有$0 = vH^T = \sum_{j=1}^e v_{i_j}h_{i_j}^T$, 这意味着$\{h_{i_j}\}$是线性相关的。
因为$d(C) = \min_{v \in C}{w(v)}$, 因此$H$存在$d(C)$列线性相关.
假设$H$的第 $\{i_1, i_2, \cdots, i_e\}$列线性无关, 即存在一组数$\{a_j\}$, $\sum_{j=1}^e a_jh_{i_j} = 0$. 容易构造一个向量$v$, 使$v_{i_j} = a_j$, 其它分量为0. $v \in C, w(v) = e$. 由此可以推出$H$的任意少于$d(C)$列都是线性无关的, 否则按我们的方法就可以构造出相应的$v \in C$ , $w(v) \lt d(C)$.
反过来，假设$H$的任意$d-1$列线性无关, 存在$d$列线性相关。因为任意$d(C)-1$列线性无关, 所以$d(C)-1 \leq d-1$, 即$d(C)\leq d$. 因为存在$d(C)$列线性相关，所以$d(C) \gt d-1$, 即$d(C) \geq d$.
Encoding and Decoding with a Linear Code
Encoding
取$k*n$的generator matrix $G$, 定义线性码的加密是映射$F^k_q \rightarrow F_q^n$, 将$k$维向量$u$映射到$n$维向量$uG$. 可以看做是用$G$的各行的线性组合。
值得一提的是，一般取$G=(I|X)$这样的矩阵(generator matrix in standard form)。这样$uG = (u, uX)$, 前面$k$位就是原来的信息(message digits)，后面$n-k$位是冗余信息(check digits)，可以用来修正传输时候的噪声。注意编码学不同于密码学，密码学注重信息的安全性，而编码学关注去除传输时出现的噪声 (某些位在传输过程中出现了变化)。
Decoding
解码稍微要复杂一些，因为要考虑到传输过程中出现的错误。
假设传输的是$u$, 收到的是$v$. 定义错误向量$e = v-u$。 根据最近邻居解码原则, 我们认为$e$是使得$v+e\in C$并且$w(e)$最小的(出错的位数最少)。
在这个原则下，提出下面的算法。
算法1：
预处理出所有的coset(涉及一些抽象代数), 即形如$u+C$的集合, $u \in F_q^n$.
$e = v-u \in v + C$, 因此我们查表找到$v$所在的coset中权值最小的向量就是$e$.利用$u = v-e$复原。
这样做需要很大的空间，因为得把$F_q^n$里$q^n$这么多向量全部存下来，只有当$q^n$比较小的时候才可行。
算法2:
终于轮到我们之前提了半天的check matrix $H$出场了。
因为$\forall v \in u+C, vH^T = (u+w)H^T = uH^T+vH^T = uH^T$. 也就是说，同一个coset里的向量，右乘上$H^T$的结果是一样的。
所以我们只要保存每个coset权值最小的向量, 以及coset中的元素右乘$H^T$的结果就可以用算法1的方法解码。存储的空间之和coset个数有关，而根据每个coset的大小都是$q^k$, coset的个数就是$q^{n-k}$，比算法1的$q^n $要好。
这种算法称为Syndrome decoding, $u$的syndrome记作$S(u):= uH^T$。
Weight Distribution
$A_i := |\{ u \mid wt(u)=i \}|$.
$W_c(x, y) = \sum_{i=0}^n{A_ix^iy^{n-i}}$.
MacWilliams’ Identity
$W_{C^{\perp}}(x, y) = \frac{1}{|C|}W_C(x+(q-1)y,x-y)$
当$q=2$时:
$W_{C^{\perp}}(x, y) = \frac{1}{|C|}W_C(x+y,x-y)$
Exercise
记录一些我个人认为比较有趣的课后练习题(可能我的答案是错误的).