编码理论基础

-

有限域上的循环码

编码的构成和分类

自对偶码

编码和设计

环码

准循环码

介绍斜多项式环和斜循环码

加性循环码

卷积码

介绍

  卷积码由Peter Elias在1955年提出。它们可以被看作是分组代码的一般化。为了促进这种一般化,考虑一个k×n的生成器矩阵G,其行空间生成一个[n,k]的块代码C,用$F_q$表示有q个元素的有限域。对于消息字序列m_i\inF^k_q, i = 1,…N必须经过编码才能传输码字序列$$c_i = m_iG\inF^n_q, i = 1,…N$$。 使用多项式符号并进行如下定义：

$$m(z):= \sum_{i=1}^{N}m_iz^i \in F_q{[z]}^k \quad and \quad c(z):= \sum_{i=1}^{N}c_iz^i \in F_q{[z]}^k$$

使用分组代码C编码的整个过程可以简单地描述为：

$$(m)z\rightarrow c(z)=m(z)G$$

Elias没有使用常数矩阵G作为编码映射,而是建议使用更一般的形式为G(z)的多项式矩阵,其项由多项式环$F_q[z]$的元素组成。
  自动机理论和系统理论之间有自然的联系,这是由Massey和Sain在1967年首次认识到的。这些联系在卷积码理论的发展中一直是富有成效的;读者也可以参考调查。
  在20世纪70年代,Forney发展了一种数学理论,允许处理具有$m(z):= \sum^{\infty}_{i=1} m_iz^i \in F_q{[[z]]}^k$形式的无限消息块集。注意,形式幂级数$F_q[[z]]$环的梯度场是形式Laurent级数$F_q[[z]]$的场, 在Forney理论中,卷积码被定义为n维向量空间$F_q{((z))}^n$的k维线性子空间,该子空间也具有一个k×n多项式的生成矩阵$G(z)∈F_q{[z]}^{k×n}$。
由Forney首先提出的卷积码理论也可以在Piret的专著和Johanesson以及Zigangirov的教科书中找到;此外,McEliece也提供了一项调查.
  在本章中,我们的起点是有限长度的消息字,即由多项式矩阵$G(z)∈F_q{[z]}^{k×n}$处理后的,形式为$m(z):= \sum^{N}_{i=0} m_iz^i \in F_q{[z]}^k$的多项式向量。并将结果编码以自然的方式在多项式环F_q[z]上变成一个秩k的模。通过对偶性与离散时间线性系统的联系也是自然的,这是由Rosenthal、Schumacher和York首先证明的。

卷积码基础

通过生成器和奇偶校验矩阵定义卷积码

  设$R=F_q[z]$是系数为$F_q$的多项式 环,用$F_q(z)$表示系数为$F_q$的有理函数场。R是一个主理想域(PID)。PID上的模块承认一个基,两个不同的基具有相同数量的元素,称为模块的秩。
  在本章中,我们将用三种符号表示$R^n$中多项式的向量。对于$c(z) \in R^n$,将使用通常的n元组表示法: $c(z) = (c_1(z), c_2(z),…,c_n(z))$,其中对于1≤i≤n,有$c_i(z) \in R$。相关地,c(z)可以写成1×n矩阵$c(z) = [c_1(z) c_2(z)···c_n(z)]$。$c(z)$的度定义为$deg(c(z)) = max_{1≤i≤n} deg(c_i(z))$。 第三种更紧凑的符号是$c(z)=\sum^{deg(c(z))}_{i=0} c_iz^i$,其中$c_i \in F^n_q$。
  速率为k/n的卷积码C是秩为k的$R^ n$的R子模。如果一个在R中的k×n矩阵G(z),其行构成C的基,称为C的生成矩阵。
  回想一下,k×k矩阵U(z)元素在R中是一个单模矩阵如果有一个k×k矩阵V(z)元素在R中是这样的：

$$U(z)V(z)=V(z)U(z)=I_k$$

根据克莱姆法则和行列式的初等性质,当且仅当$det(U(z)) \in F^{*}_q:= F_q$ \{0}时,U(z)是单模的。
  假设G(z)和eG(z)都是相同编码$C=rowspaceR(G(z))=rowspaceR(\widetilde{G}(z))$的生成矩阵。然后我们可以证明存在一个单位模矩阵U(z)

$$\widetilde{G}(z)=U(z)G(z)$$

注意,这在k×k生成矩阵集上引出了一个等价关系:G(z)和eG(z)当且仅当$\widetilde{G} (z) = U(z)G(z)$对于某个单模矩阵U(z)是等价的。这种等价关系的标准形式是列Heimite形式。
定义 10.2.1 设$G(z) \in R,k×n$,$k≤n$,则存在一个单模矩阵$U(z)\in R^{k×k}$，使

$$H(x)=U(z)G(z)=\begin{bmatrix} h_{11}z & h_{12}(z) & \cdots & h_{1k}(z) & h_{1,k+1}(z) & \cdots & h_{1n}(z) \\ & h_{22}(z) & \cdots & h_{2k}(z) & h_{2,k+1}(z) & \cdots & h_{2n}(z) \\ & \ddots & \vdots & \vdots & \vdots & & \vdots \\ & & & h_{kk}(z) & h_{k,k+1}z & \cdots & h_{kn}(z) \end{bmatrix}$$

其中$h_{ii}(z),i=1,2,...,k$，为一元多项式，使得$j<i$时有$deg h_ii > deg h_ji$.$H(z)$是G(z)的(唯一)列Hermite形式.

  其它等价关系由与一个单模矩阵的右乘法或与一个单模矩阵的左右乘法引起。这种等价关系的标准形式分别是行Hermite形式和Smith形式。

定义10.2.2 设$G(z)\in R^{k\times n},k\leq n$.存在一个单模矩阵$U(z)\in R^{n\times n}$,使

$$H(x)=G(z)U(z)=\begin{bmatrix} h_{11}(z) & & & & & 0 & 0 \\ h_{21}(z) & h_{22}(z) & & & & \vdots & \vdots \\ \cdots & \vdots & \ddots & & & \cdots & \cdots \\ h_{k1}(z) & h_{k2}(z) & \cdots & h_{kk}(z) & 0 & \cdots & 0 \end{bmatrix}$$

其中$h_{ii}(z),i=1,2,..,k$为一元多项式，使得对于$j<i$，有$deg h_ii > deg h_ij$.$H(z)$是$G(z)$的（唯一）行Hermite形式。

定义 10.2.3 设$G(z)\in R^{k\times n},k \leq n$,则存在单模矩阵$U(z)\in R^{k\times k},V(z)\in R^{n\times n}$，使

$$S(z)=U(z)G(z)V(z)=\begin{bmatrix} \gamma_{1}(z) & & & & 0 & \cdots & 0 \\ & \gamma_{2}(z) & & & \vdots & & \vdots \\ & & \ddots & & \vdots & & \vdots \\ & & & \gamma_{k}(z) & 0 & & 0 \end{bmatrix}$$

其中，$\gamma_{i}(z),i=1,2,...,k$，对于$i=1,2,...,k-1$有,$\gamma_{i+1}(k)|\gamma_{i}(z)$一元多项式.这些多项式由G(z)唯一确定，称为G(z)的不变多项式.S(z)是G(z)的Smith形式.
  由于两个等价的生成矩阵因为左乘一个单模矩阵而不同，所以它们具有相等的$k\times k$(全尺寸)余子，直到乘上一个常数。卷积码C的生成矩阵的全尺寸次(称为其内度)的最大次称为C的度(或复杂度),通常用$\delta$表示。速率k/n和度$\delta$的卷积码也称为$(n,k,\delta)$卷积码.在本章中，$L:= \lfloor \frac{\delta}{k} \rfloor+\lfloor \frac{\delta}{n-k} \rfloor$

  对于$i=1,...,k$,矩阵$G(z) \in R^{k\times n}$的第i行任意项的最大次是$v_i$.很明显，如果G(z)是一个生成矩阵，且$v_1,v_2,...,v_k$,为G(z)的行度,则$\delta \leq v_1+v_2+...+v_k$.G(z)的行度之和称为外度.如果内度和外度重合,则称G(z)为行约化矩阵，称为最小生成矩阵.因此,代码的度可以等效地定义为C的最小生成矩阵的外部度.

定理 10.2.4 设$G(z)\in R^{k\times n}$,行度$v_1,v_2,...,v_k$,令[G]hr是最高的行度系数矩阵，定义为第i行由G(z)的第i行中$z^{v_i}$的系数组成的矩阵.那么当且仅当[G]hr是行满秩时，$\delta =v_1+v_2+...+v_k$,即G(z)行约简.

  设G(z)是行约化矩阵，行度$v_1,v_2,...,v_k$和$c(z)=u(z)G(z)$,$u(z)=[u_1(z) u_2(z) ... u_k(z)]\in R^k$.显然,$degc(z)\leq \mathop{\max}\limits_{i:u_i(z)\neq 0} \{v_i+deg u_i(z)\}$.设$\varLambda = \mathop{\max}\limits_{i:u_i(z)\neq 0} \{v_i+deg u_i(z)\}$，则对于$i=1,2,...,k$的式子$deg r_i(z)<\varLambda-v_i$,有$u_i(z)=\alpha_{i}z^{\varLambda-v_i}+r_i(z)$.那么

$$c(z)=([ \alpha z^{\varLambda-v_1} \alpha z^{\varLambda-v_2} ... \alpha z^{\varLambda-v_k}]+[r_1(z) r_2(z) ... r_k(z)]) \times (\begin{bmatrix} z^{v_1} & & & \\ & z^{v_2} & & \\ & & \ddots & \\ & & & z^{v_k} \end{bmatrix} [G]_hr+G_rem(z))$$

其中在$G_rem(z)\in R^{k\times n}$中,对于$i=1,2,...,k$,有第i行的度小于$v_i$.c(z)的度的系数$\varLambda$,

卷积码的距离

优化距离的卷积码的构造

MDS卷积码的构造

MDP卷积码的构造

系统理论的连接

卷积码解码

在擦除信道的解码

$\delta$的情形

一般情形

Viterbi解码算法

二维卷积码

使用生成矩阵和奇偶校验矩阵的2D卷积码的定义

ISO表示

与符号动力学的联系

秩度量码

线性规划界限

纠错码的半定编程界

编码理论与伽罗瓦几何

代数几何编码及应用

介绍

历史

代数编码应用

章节构成

定义

曲线和函数域

曲线、点、函数域和位置

除子

曲线和回调的态射

微分形式

规范化除子

余数

属和罗曼罗素定理

代数几何编码基础

代数几何编码、定义和基础结果

属0、广义Reed-Solomon和经典Goppa代码

CL解释

CΩ解释

代数几何编码的渐近参数

序论

Tsfasman–Vl˘ adut ¸–Zink界

子域子码和Katsman–Tsfasman–Wirtz界

非线性码

下界最小距离的优化

有序界

进阶界

嵌入曲线编码的几何界

解码算法

解码距离低于设计距离的一半

基础算法

摆脱代数几何：纠错对

将间距缩小到设计距离的一半

译码到设计距离的一半：Feng-Rao算法和纠错阵列

列表解码和Guruswami-Sudan算法

公钥密码学的应用：McEliece密码体制

历史

McEliece使用二进制经典Goppa码的原始提议

McEliece方案的优点和缺点

JanWa和Moreno使用AG码的提案

安全

级联码不安全

AG码不安全

结论：只有AG码的子域子码才不会被破解

*乘相关的应用：防框架码、乘法算法和秘密共享

AG码的角度看*乘

基本属性

*乘的维度

维度和距离的关节界

自同构

分布式存储系统的应用：本地可恢复码

动机

关于局部参数的一个上界

Tamo-Berg码

代数曲线覆盖的局部可恢复码：Barg–Tamo–Vl˘ adut码

优化：较大局部距离的局部可恢复码

曲线的纤维积和可用性问题

群代数中的编码

有限交换链环上的常循环码

有限环上迹码的权值分布

双重码

函数的线性编码

图上的编码

替换指标

算法方法

插值解码

伪随机噪声序列

点阵编码

量子错误控制码

时空码

网络编码

擦除码和喷泉码的编码

分布式存储编码

Polar码

线性编码的秘密共享

基于编码的密码学