最后更新: 2025-12-24 17:14 查看: 47 次纠错评论(0) 课件开VIP

环在编码和密码中的应用

现代通信系统中用数字代表信息，在信息传递的过程中既要解决信息传递的
可靠性问题，也要解决信息的保密性问题，这就需要用到相应的编码和密码技术.
为了有效检测或者纠正数字信息在信道传输过程中出现的错误，通常需要对
信息进行编码，比如重复码、奇偶校验码、汉明码等都是常用的纠错码.特别地，基于有限域上的多项式环可以构造一类重要的纠错码一一循环码.

有限域 $\mathbf{F}_q$ 上 $n$ 维线性空间 $\mathbf{F}_q^n$ 的每个非空子集 $C$ 都称为一个 $q$ 元纠错码， $C$ 中的每个向量 $c=\left(c_0, c_1, \cdots, c_{n-1}\right)$ 称为一个码字，$n$ 称为该码的码长，$K= |C|$ 为码字个数，$k=\log _q K$ 称为信息位数，$\frac{k}{n}$ 称为码率．

设 $u=\left(u_0, u_1, \cdots, u_{n-1}\right), v=\left(v_0, v_1, \cdots, v_{n-1}\right) \in \mathbf{F}_q^n, u$ 中非零分量 $u_i(0 \leqslant i \leqslant n-1)$ 的个数称为向量 $u$ 的汉明重量，记为 $w_{\mathrm{H}}(u)$ ．向量 $u$ 和 $v$ 中不同的分量的个数称为向量 $u$ 和 $v$ 的汉明距离，记为 $d_{\mathrm{H}}(u, v)$ ，即有 $d_{\mathrm{H}}(u, v)= w_{\mathrm{H}}(u-v)$ ．对任意 $u, v, w \in \mathbf{F}_q^n$ ，容易验证下面的三角不等式成立：

$$
d_{\mathrm{H}}(u, v) \leqslant d_{\mathrm{H}}(u, w)+d_{\mathrm{H}}(w, v) .
$$

码 $C$ 的最小距离 $d(C)$ 定义为 $C$ 中不同码字之间汉明距离的最小值．码的最小距离反映了码的纠错能力．由最小距离的定义和三角不等式可以证明：最小距离为 $d$ 的纠错码可以检查 $\leqslant d-1$ 位错误，也可以纠正 $\leqslant\left[\frac{d-1}{2}\right]$ 位错误，这里的 $[x]$ 表示不超过 $x$ 的最大整数．

对于参数为 $(n, K, d)$ 的 $n$ 长 $q$ 元码 $C$ ，如果 $K \leqslant q^{n-d+1}$ 或者 $k \leqslant n-d$ +1 （满足辛格尔顿（Singleton）界），则称 $C$ 为 MDS（maximal distance separa－ ble）码．这是一类性质较好的纠错码．分组密码中的最优扩散层变换也经常基于这类码构造．

对于 $q$ 元纠错码 $C$ ，如果 $C$ 能够构成 $\mathbf{F}_q^n$ 的一个线性子空间，则 $C$ 是一个 $q$元线性码．进而，如果码 $C$ 的每个码字 $c=\left(c_0, c_1, \cdots, c_{n-1}\right)$ 的任意循环移位还是 $C$ 的一个码字，比如 $c^{\prime}=\left(c_1, \cdots, c_{n-1}, c_0\right) \in C$ ，则称 $C$ 为一个循环码。

对于线性码 $C$ ，如果把码字 $c=\left(c_0, c_1, \cdots, c_{n-1}\right)$ 写成多项式 $c(x)=c_0+ c_1 x+\cdots+c_{n-1} x^{n-1}$ ，它可以看成多项式环 $\mathbf{F}_q[x]$ 的商环 $R=\left(\mathbf{F}_q[x]\right) /\left(x^n-1\right)$ 中的元素．容易看出，$R$ 是 $\mathbf{F}_q$ 上以 $1, x, \cdots, x^{n-1}$ 为基的 $n$ 维线性空间，而线性码 $C$ 是 $R$ 的一个线性子空间．将码字 $c=\left(c_0, c_1, \cdots, c_{n-1}\right)$ 与 $R$ 中码多项式 $c(x)=c_0+c_1 x+\cdots+c_{n-1} x^{n-1}$ 等同，注意到在 $R$ 中有

$$
x c(x)=c_0 x+c_1 x^2+\cdots+c_{n-1} x^n=c_{n-1}+c_0 x+c_1 x^2+\cdots+c_{n-2} x^{n-1},
$$

于是 $C$ 为循环码当且仅当由 $c(x) \in C$ 总可以得到 $x c(x) \in C$ ．进而，对每个多项式 $a(x)$ ，也有 $a(x) c(x) \in C$ ．因此可以得到
$C$ 为循环码当且仅当 $C$ 为环 $R$ 的一个理想．
由于 $\mathbf{F}_q[x]$ 为主理想整环，商环 $R$ 也是主理想环，并且 $R$ 的每个理想对应于 $\mathbf{F}_q[x]$ 中包含 $\left(x^n-1\right)$ 的主理想 $(g(x))$ ，其中 $g(x) \mid\left(x^n-1\right)$ ．因此， $\mathbf{F}_q$ 上码长为 $n$的循环码 $C$ 可以表示为

$$
C=(g(x))=\{a(x) g(x) \in R \mid a(x) \in R\} .
$$

取 $g(x)$ 为满足 $g(x) \mid\left(x^n-1\right)$ 的首项系数为 1 的多项式，则 $g(x)$ 由码 $C$ 唯一确定，称 $g(x)$ 为循环码 $C$ 的生成多项式．不妨设 $\operatorname{deg} g(x)=n-k(0 \leqslant k \leqslant n)$ ，则存在首项系数为 1 的 $k$ 次多项式 $h(x)$ 使得 $x^n-1=g(x) h(x)$ ，称 $h(x)$ 为循环码 $C$ 的校验多项式．

对于以 $g(x)$ 为生成多项式的循环码 $C$ ，由于 $\operatorname{deg} g(x)=n-k$ ，每个码字 $a(x) g(x)$ 能唯一地表示成

$$
\left(a_0+a_1 x+\cdots+a_{k-1} x^{k-1}\right) g(x),
$$

因此 $g(x), x g(x), \cdots, x^{k-1} g(x)$ 是码 $C$ 的一组基，从而 $C$ 的信息位数为 $k$ ．
令 $g(x)=g_0+g_1 x+\cdots+g_{n-k} x^{n-k}\left(g_{n-k}=1\right), h(x)=h_0+h_1 x+\cdots+h_k x^k \left(h_k=1\right)$ ，则码 $C$ 的生成矩阵为

$$
\begin{aligned}
G & =\left(\begin{array}{c}
g(x) \\
x g(x) \\
\vdots \\
x^{k-1} g(x)
\end{array}\right) \\
& =\left(\begin{array}{cccccccc}
g_0 & g_1 & \cdots & g_{n-k-1} & g_{n-k} & 0 & \cdots & 0 \\
0 & g_0 & g_1 & \cdots & g_{n-k-1} & g_{n-k} & \cdots & 0 \\
\vdots & \ddots & \ddots & \ddots & & \ddots & \ddots & \vdots \\
0 & \cdots & 0 & g_0 & g_1 & \cdots & g_{n-k-1} & g_{n-k}
\end{array}\right)
\end{aligned}
$$

校验矩阵为
$$
H=\left(\begin{array}{cccccccc}
h_k & h_{k-1} & \cdots & h_1 & h_0 & 0 & \cdots & 0 \\
0 & h_k & h_{k-1} & \cdots & h_1 & h_0 & \cdots & 0 \\
\vdots & \ddots & \ddots & \ddots & & \ddots & \ddots & \vdots \\
0 & \cdots & 0 & h_k & h_{k-1} & \cdots & h_1 & h_0
\end{array}\right) .
$$

确定一般循环码的最小距离并不容易．设 $\alpha$ 是 $\mathbf{F}_q$ 的一个本原元，$n=q-1$ ， $2 \leqslant d \leqslant n$ ，可以证明形如

$$
C=\left\{c(x)=\sum_{i=0}^{n-1} c_i x^i \in \mathbf{F}_q[x] \mid c(\alpha)=c\left(\alpha^2\right)=\cdots=c\left(\alpha^{d-1}\right)=0\right\}
$$

的 Reed－Solomon 码是 MDS 码，其中码 $C$ 的生成多项式为 $g(x)=(x-\alpha)(x- \left.\alpha^2\right) \cdots\left(x-\alpha^{d-1}\right)$ ，最小距离为 $d$ ，信息位数 $k=n-\operatorname{deg} g(x)=n-d+1$ ．Reed－ Solomon 码是 BCH 码的一种，编码和译码都可以有效实现。

作为环论知识在密码中的应用，下面介绍著名的 RSA 算法和 ElGamal 算法．
RSA 算法 设 $N=p q$ ，其中 $p, q$ 为两个不同的大素数， $\mathbf{Z}_N$ 为整数模 $N$ 的剩余类环。明文和密文都取自 $\mathbf{Z}_N$ 。记 $\varphi(N)=(p-1)(q-1)$ 为欧拉函数，在 1 到 $\varphi(N)$ 中任取一个与 $\varphi(N)$ 互素的整数 $e$ ，则必然存在整数 $d$ ，使得 $e d \equiv 1(\bmod N)$ ，称 $e$ 为加密指数，$d$ 为解密指数．$N, e$ 为公开密钥，$d$ 为秘密密钥．RSA 算法的加密变换为

$$
c=E_e(m)=m^e(\bmod N),
$$

解密变换为

$$
m=D_d(c)=c^d(\bmod N)
$$

由欧拉定理知，当 $a, N$ 互素时 $a^{\varphi(N)} \equiv 1(\bmod N)$ ，由此可以证明加解密的正确性．

RSA 密码算法的安全性依赖于大整数分解问题的困难性．目前已经可以分解 768 比特的整数，为保证安全性，建议选用 1024 或者 2048 比特的模数 $N$ 。

ElGamal 算法 设 $p$ 是一个大素数，$\alpha$ 是 $\mathbf{Z}_p^*$ 的本原元。随机选择正整数 $a$ ，并计算 $\beta=\alpha^a(\bmod p) . p, \alpha, \beta$ 为公开密钥，$a$ 为秘密密钥．ElGamal 算法的加密变换为

选择秘密随机数 $k, 1 \leqslant k \leqslant p-2$ ，并计算

$$
c_1=\alpha^k(\bmod p), \quad c_2=m \beta^k(\bmod p)
$$

则密文为 $\left(c_1, c_2\right)$ ．解密变换为

$$
m=c_2 \cdot\left(c_1^a\right)^{-1}(\bmod p) .
$$

ElGamal 算法的安全性依赖于 $\mathbf{Z}_p^*$ 上离散对数问题求解的困难性，即已知 $\alpha$ ， $\beta$ ，求满足 $\beta=\alpha^k(\bmod p)$ 的正整数 $k, 1 \leqslant k \leqslant p-2$ ．

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：整环的商域

下一篇：没有了

本文对您是否有用？有用 (0) 无用 (0)