卷积码（convolutional code）-Toy模板网

这篇具有很好参考价值的文章主要介绍了卷积码（convolutional code）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Convolutional Code

分块码（block code）：数据流（datastream）被切分为包含 $k$ 个数据符号（data symbol）的块，叫做数据字（dataword），然后将它们分别编码为包含 $n$ 个码符号（code symbol）的块，叫做码字（codeword），拼接成码流（codestream）。单个码字仅仅依赖于单个数据字。

Hamming码、BCH码，都是分块码。

格码（trellis code）： $q$ 元（ $q - a r y$ ）数据流（datastream）被切分为包含 $k$ 个数据符号（data symbol）的块，叫做数据帧（dataframe），然后将它们分别编码为包含 $n$ 个码符号（code symbol）的块，叫做码帧（codeframe），拼接成码流（codestream）。单个码帧要依赖于多个数据帧。

格码往往被描述为移位寄存器编码器（shift-register encoder）。编码器中可以存储 $m$ 个大小为 $k$ 的数据帧，这里 $m$ 叫做帧内存（frame memory）。

卷积码（convolutional code）

从零时刻开始，数据流按帧不间断地移位进编码器；每一跳（each clock time），一个新的数据帧移入寄存器，同时最旧的数据帧移出寄存器被丢弃；此时，寄存器中包含 $m k$ 个数据符号，编码器根据它们计算单个长度为 $n$ 的码帧。这是一个 $(n, k)$ 格码，码率 $R = k / n$ 。

如果每一时刻， $n$ 长码帧的前 $k$ 个位置就是数据帧的内容，那么我们称它为系统编码的（systematically encoded）。

最小编码器中 $q$ 元内存元胞的数量，叫做约束长度（constraint length），记做 $v$ ，且明显 $\le mk$

注意，虽然格码被描述为移位寄存器编码器，但同一个格码有很多不同的编码器，编码器不是描述格码所必须的。

一种重要的格码是卷积码（convolutional code），它满足：

加法线性（additional linearity）：两个数据流的任意线性组合的码流，等于码流的线性组合，
$G(\beta a_1 + \gamma a_2) = \beta G(a_1) + \gamma G(a_2)$
这里的 $a_1,a_2$ 是无限长数据流， $\beta,\gamma \in GF(q)$ ， $G(\cdot)$ 是无限长的码流。
时不变性（time-invariance）：数据流通过填充全零的前导数据帧（a leading dataframe of zeros）来延迟单个数据帧（delayed by a single dataframe），那么码流会延迟单个码帧，它的前导码帧是全零的（a leading codeframe of zeros），
$G(\pmb 0\|a) = \pmb 0 \| G(a)$
左边的 $\pmb 0$ 是 $k$ 长的单个全零数据帧，右边的 $\pmb 0$ 是 $n$ 长的单个全零码帧。

一般卷积码的 $k$ 都很小，甚至是 $k = 1$ 。因此，它们的码率都远远达不到 $1$ ，这不像分组码可以达到 $R = 1$ 。

只有很少的卷积码构造类已知，大多数卷积码都是计算机搜索的。没有拥有令人满意的代数结构的一类卷积码已知，也没有令人满意的长约束长度的一类卷积码的构造方法已知。

Trellis description

网格图（trellis）：一个有向图，每个节点上都有关于起始节点的良定义的深度（即从起始节点到达它的所有路径的长度相同）。

我们考虑向右半无限的（semi-infinite to the right）网格图，它的每一列包含 $q^v$ 个点，对应编码器的 $q^v$ 种状态，这一列点的深度相同。每个节点上都有 $q^k$ 个有向分支。相邻两列节点之间的连接方式是相同的。每一列都被用整数 $l$ 标记，它叫做时刻（time）。时刻 $l$ 上的节点表示编码器当前状态 $s_l$ ，再根据最新的数据帧来选择一条分支，到达 $l + 1$ 时刻的一个节点 $s_{l+1}$ 。

对于的 $2,1)_2$ 卷积码，网格图为：

卷积码（convolutional code）

对应的编码器为：

卷积码（convolutional code）

我们利用网格图来描述卷积码，而不必使用编码器。

我们可以构造一个系统编码的 $2,1)_2$ 卷积码，

卷积码（convolutional code）

可以看出，任意的 $n,k)_q$ 卷积码，都可以被 $n$ 组有限脉冲响应滤波器（finite-impulse-response filter）所编码，每个滤波器由 $k$ 个前反馈移位寄存器（feedforward shift registers）所组成。

Polynomial description

我们可以用生成器多项式（generator polynomials）来表示卷积码的一个编码器。对于 $n,k)_q$ 卷积码的帧内存 $m$ 的编码器（注意，描述的不是code，而是encoder），定义多项式生成矩阵（polynomial generator matrix）：
$[g_{ij}(x)] \in (GF(q)[x])^{k \times n}$
包含 $n k$ 个多项式，它们的度数不超过 $m$ 。并且需要至少有一个多项式不以 $x$ 为因式。如果 $G (x)$ 中所有多项式都以 $x$ 为根，那么就可以同时提取出 $x$ 来，从而使得码流延迟单个码帧。

例如，非系统的 $2,1)_2$ 卷积码，
$\begin{bmatrix} x^2+1 & x^2+x+1 \end{bmatrix}$
令数据多项式为：
$[a_{00},a_{01},\cdots,a_{0,k-1}] + [a_{10},a_{11},\cdots,a_{1,k-1}] x + \cdots$
每一个系数都是一个数据帧的向量，它本身是 $k$ 个无限长多项式所组成的行向量。

编码过程为：
$c (x) = a (x) G (x)$
令码多项式为：
$[c_{00},c_{01},\cdots,c_{0,n-1}] + [c_{10},c_{11},\cdots,c_{1,n-1}] x + \cdots$
每一个系数都是一个码帧的向量，它本身是 $n$ 个无限长多项式所组成的行向量。

截断卷积码（truncated convolutional code）：对于无限长的 $a (x)$ ，我们丢弃 $c (x)$ 后面的无限个系数。这是分块码。

终止卷积码（terminated convolutional code）：限制 $a (x)$ 为有限长多项式，计算得到有限长的 $c (x)$ 。这是分块码。

生成矩阵可以通过列置换以及初等行变换，得到等价生成矩阵（equivalent generator matrices），它们生成相同的卷积码，仅仅是数据符号的对应方式不同。系统的生成矩阵：
$\begin{bmatrix} I & P(x) \end{bmatrix}$
一般地，由于多项式环 $G F (q) [x]$ 上的元素不可逆，从而无法化作系统编码的。如果我们做分式域（包含整环的最小域）：
$\{a(x)/b(x):\,\, a(x),b(x) \in GF(q)[x],\,\, b(x) \neq 0 \}$
注意这里的 $a (x) / b (x)$ 就是一个有序二元组，不要试图做除法。

让矩阵 $G (x)$ 里的多项式取自这个分式域，叫做实矩阵（rational matrix）。如果 $\nmid b(x)$ ，我们说元素 $a (x) / b (x)$ 是可实数化的（realizable）。如果一个实的生成矩阵的每个元素都是可实数化的，我们说它是可实数化生成矩阵（realizable generator matrix）

例如，将非系统的 $2,1)_2$ 卷积码转换成系统的，
$\begin{aligned} G'(x) &= \begin{bmatrix} \dfrac{x^2+1}{x^2+1} & \dfrac{x^2+x+1}{x^2+1} \end{bmatrix}\\ &= \begin{bmatrix} 1 & 1 + \dfrac{x}{x^2+1} \end{bmatrix}\\ \end{aligned}$
这里的分母 $x^2+1$ 导致了编码器电路中包含反馈（feedback）。

明显， $G (x) = T (x) G^{'} (x)$ ，这里 $T (x)$ 是分式域 $G F (q) (x)$ 上的 $\times k$ 非奇异矩阵。

$\times n$ 的 $G (x)$ 上， $\times k$ 的子矩阵的行列式叫做主行列式（principal determinant）。定义内度（internal degree）
$\deg_{int} G(x) = \max_{l \in [{n \choose k}]} [\deg \det G_l (x)]$
定义外度（external degree）
$\deg_{ext} G(x) = \sum_{i=0}^{k-1} \max_j [\deg g_{ij}(x)]$
容易看出， $\deg_{int} G(x) \le \deg_{ext} G(x)$

如果生成矩阵 $G (x)$ 无法从更小内度的生成矩阵乘以 $T (x)$ 得到，那么称它为基生成矩阵（basic generator matrix），令它的内度为 $v$ ，它就是约束长度。由于根据 $G (x)$ 的定义 $m = \max_i \max_j [\deg g_{ij}(x)]$ ，因此有
$\le km$
它测量了编码器的帧内存大小。

输入跨度（input span）：
$K = k \max_{i,j} [\deg g_{ij}(x) + 1]$
它测量了能够影响单个码符号的数据符号序列的长度。

输出跨度（output span）：
$N = n \max_{i,j} [\deg g_{ij}(x) + 1]$
它测量了单个数据符号能够影响的码符号序列的长度。

Matrix description

卷积码是包含无限个无限长的码字的线性码，从而可以用 $G F (q)$ 上的无限大的生成矩阵来表示。

对于 $\times n$ 个生成器多项式：
$g_{ij}(x) = \sum_{l=0}^m g_{ijl} x^l$
我们将它们的系数重新排列，令 $G_l = [g_{ijl}] \in GF(q)^{k \times n}$ ，那么生成矩阵为：
$\begin{bmatrix} G_0 & G_1 & \cdots & G_m & 0 & 0 & \cdots\\ 0 & G_0 & \cdots & G_{m-1} & G_{m} & 0 & \cdots\\ \vdots\\ \end{bmatrix}$
其中的 $\pmb 0$ 表示 $\times n$ 的零矩阵， $G$ 是向下向右无限延伸的。