编码理论 | Smera1d0's Blog

线性码（linear codes）

域的定义： 一个域 $\mathbb{F}$ 是由一个元素集合 $\mathbb{F}$ 以及其上的加法和乘法运算组成的代数结构 $(\mathbb{F},+,\cdot)$
性质：
- $+$ 构成交换群，单位元为 0
- 排除 0 元的 $\cdot$ 构成交换群，单位元为 1
- 乘法对加法满足分配律 $a,b,c \in \mathbb{F},a\cdot(b+c) = a\cdot b+a\cdot c$
素域： 对于素数 $p$，集合 $\{0,1,\dots p-1\}$ 上的模 $p$ 的加法和乘法构成一个域，记作 $\mathbb{F}_p$
有限域的大小和存在性： 任何有限域的大小都是 $p^s$ 的形式，其中 $p$ 是一个素数；反之，对于任何素数 $p$ 和整数 $s$，都存在大小为 $p^s$ 的域，记作 $\mathbb{F}_{p^s}$
重要性质： 对于 $a,b \in \mathbb{F}_{p^s}$
- $p \cdot a = 0$
- $a^{p^s}=a$
- $(a+b)^p = a^p+b^p$

向量空间： $V$ 是一个在域 $\mathbb{F}$ 上的向量空间，对任意的 $a,b \in \mathbb{F}$ 和 $u,v \in V$，我们有
- $(a+b) \cdot u = a \cdot u + b \cdot u$
- $a\cdot(u+v) = a \cdot u +a \cdot v$
- $(ab)\cdot u= a(b \cdot u)$
- $1 \cdot u = u$
线性子空间： 一个非空子集 $S \subseteq \mathbb{F}^n$ 构成线性子空间，需要满足
- 对任意的 $x,y \in S,x+y \in S$
- 对任意的 $a \in \mathbb{F},x \in S,a\cdot x \in S$
张成空间(Span)：
- 给定集合 $B = \{v_1, \cdots,v_l\}$，B 张成的向量空间为 $\{\sum_{i=1}^la_i \cdot v_i:a_i \in \mathbb{F}_q\}$
线性相关： 如果存在不全为0的标量使得一组向量的线性组合为0，则这组向量线性相关；否则线性无关。
内积：
- $u = (u_1,u_2,\dots ,u_n),v = (v_1,v_2,\dots,v_n)$，内积 $\lang u,v \rang = u_1v_1+u_2v_2+ \cdots+u_nv_n$
- $\lang u,v \rang = u \cdot v^T $

$\mathcal{S} \subseteq \mathbb{F}^n_q$ 是一个线性子空间，有如下性质：

$| \mathcal{S}|=q^k$ ,$k$ 称为 $\mathcal{S}$ 的维数
可以找到 $k$ 个线性无关的 $n$ 长的向量 $g_1,g_2,\dots,g_k$，对任意的 $x \in \mathcal{S}$，有：$x = a_1g_1+a_2g_2+\cdots+a_kg_k$
矩阵形式：$a = (a_1,a_2,\dots ,a_n),G=(g_1,g_2,\dots,g_k)^T_{(k\times n)}$ ，有 $x = a \cdot G$，矩阵 $G$ 的每一个行向量可以作为码字的基向量。
线性方程组的解空间：对于任意的 $x \in \mathcal{S}$ ，有 $H \cdot x^T=0$，其中 $H$ 是大小为 $(n-k)\times n$ 的满秩矩阵
矩阵 $G$ 和矩阵 $H$，满足 $G \cdot H^T = 0$

$[n,k,d]_q$ 表示在 $\mathbb{F}_q^n$ 的线性子空间的维数为 $k$，极小距离为 $d$ 的码

$$ C = \{x\cdot G|x\in \mathbb{F}_q^k\} $$

$$ C = \{y \in \mathbb{F}_q^n|H\cdot y^T=0\} $$