编码理论基础
-
有限域上的循环码
编码的构成和分类
自对偶码
编码和设计
环码
准循环码
介绍斜多项式环和斜循环码
加性循环码
卷积码
介绍
卷积码由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_izi \in F_q{[z]}^k \quad and \quad c(z):= \sum_{i=1}{N}c_izi \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]}$。
由Forney首先提出的卷积码理论也可以在Piret的专著和Johanesson以及Zigangirov的教科书中找到;此外,McEliece也提供了一项调查.
在本章中,我们的起点是有限长度的消息字,即由多项式矩阵$G(z)∈F_q{[z]}^{k×n}$处理后的,形式为$m(z):= \sum^{N} 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}
hz & h(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$,