75、编码理论中的重要界限与卷积码介绍

编码理论中的重要界限与卷积码介绍

1. 重温 Gilbert–Varshamov 界限

在编码理论中，Gilbert–Varshamov 界限是一个重要的概念。若设 $\delta = d/n$，对相关式子取以 $q$ 为底的对数并除以 $n$，可得到：
$n^{-1}[\log_q(\delta n) + \log_q V_q(n, \delta n)] < \frac{t_e}{n} + n^{-1}, \log_q [1 - q^{-t_e/2 + 1}]$

当 $n$ 趋近于无穷大时，根据引理 2.10.3 可得 $H_q(\delta) \leq \lim_{n \to \infty} \frac{t_e}{n}$ 或者 $1 - H_q(\delta) \geq 1 - \lim_{n \to \infty} \frac{t_e}{n}$。由于 $t = \log_q n$，我们可以选择一个增长足够快的 $e$ 序列，使得不等式 (13.13) 得以维持，这保证了存在一系列长度不断增加（$n = q^t$）且相对最小距离至少为 $\delta n$ 的 Goppa 码，并且 $1 - H_q(\delta) = 1 - \lim_{n \to \infty} \frac{t_e}{n}$。根据定理 13.2.1，该序列中的码率至少为 $1 - \frac{t_e}{n}$，因此这个序列满足渐近 Gilbert–Varshamov 界限。

2. 代数几何码超越 Gilbert–Varshamov 界限

1982 年，Tsfasman、Vlǎdut 和 Zink 的研究首次表明，存在一系列码，当码长趋于无穷大时，其相对距离趋近于 $