layout | title | categories | tags | keywords | description | order |
---|---|---|---|---|---|---|
post |
【纠错码】理论和Rust实现 |
0x58_密码学 |
59003 |
前一篇文章介绍了 Reed-Solomon 做擦除码,它允许丢失
用 Reed-Solomon 做 ECC(Error correction capabilities),可以纠错
- ECC can correct up to (n-k)/2 errors, or n-k erasures, or any combinations of erasures/errors
原理
算法规格选取
- 有的实现是按照幂升序来写的,有的按照降序来写,两种都可以,但不能混用。本文统一用降序
- 生成多项式(下面会解释)为
$g(x) = (x-\alpha^i)(x-\alpha^{i+1})...(x-\alpha^{i+n-k-1})$ ,- i 决定了第一个根,可以是 1 或者 0 。在 CD/QR/DVB-T 中,i = 0,本文统一用i = 0
-
$\alpha$ 是本源元,本文统一取 2 - 按照上面的取值,$g(x) = (x-\alpha^0)(x-\alpha^1)...(x-\alpha^{n-k-1}) = x^{n-k} + g_1 x^{n-k-1} + ... + g_{n-k+1}x + g_{n-k}$
超参数:
- 信息 message 有 k 个,$\mathbf m = [m_0, m_1, ..., m_k]$
- 校验位 parity 有 l 个,(因此 encode 后的信息长度为 n = l + k)
列出多项式:
- 根据 message 的 k 个字节列出:
$p(x) = m_0 x^{k-1} + m_1 x^{k-1} + ... + m_{k-2} x + m_{k-1}$ - 生成多项式为
$g(x) = (x-2^0)(x-2^1)...(x-2^{l-1}) = g_0 x^l +g_1 x^{l-1} + ... + g_{l}$ ,可以计算得到
显然,
然后使用多项式的除法计算
- 因为
$g(x)$ 的最高次幂为 l,所以$r(x)$ 最高次幂小于等于 l-1,记为$r(x) = r_0 x^{l-1} + r_1 x^{l-2} + ... + r_{l-1}$
它们合并起来
由于在 Galois Filed 有
上面这个多项式的系数就是 encode 后结果
一些定理:
- 因为
$r(x) = (p(x) x^{n-k}) \mathrm {mod} g(x)$ ,并且$s(x) = (p(x) x^{n-k}) - r(x)$ ,就有结论:$s(x) \mathrm{mod} g(x) = 0$ - encode 后结果 (
$s(x)$ 的系数),就是原始数据+校验位
encode 简单,但 decode 复杂很多,包括几个算法:
- syndromes:判断是否有错误
Si = syndromes(recv)
-
Si
为 syndromes polynomial(症状多项式)的系数 - 其根为$a^j$,也就是说,
$syn(a^j) = 0$
-
- Berlekamp-Massey:
Lambda = BerlekampMassey(Si)
,- 得到的
Lambda
就是错误定位多项式(error locator polynomial)的系数 - 算法迭代 n-k 次
- 得到的
- ChienSearch:
Xi = ChienSearch(Lambda)
- error locator:用来定位错误的位置,
Xi
就是错误的位置 - error locations Xi, roots of Lambda: 通过快速求根来定位错误
- error locator:用来定位错误的位置,
- error magnitudes Yi(Forney algorithm):用来计算错误的幅度
Yi = ForneyAlgo(Xi, Si)
,复杂度$O(n^2)$ - error corrector:计算错误
error = BuildFrom(Xi, Yi)
,进而获得纠错后的内容:corrected = recv - error
假设传输过程中发生错误,接收到了
- 如果不知道哪些位错误,则
$v\leq (n-k)/2$ - 如果知道哪些位错误则
$v \leq n-k$ ,如果达不到要求,就不能纠错。 - 如果有些知道,有些不知道,则数量是以上的组合
如果我们计算得到
从上面的推导知道,$s(x) \mathrm{mod} g(x) = 0$,并且
因此,$y(a^j) = s(a^j) + e(a^j) = 0 + e(a^j), 0 \leq j \leq l - 1$ 共得到 l 个数
// 前面写了,本文都用 fcr = 0
fn syndrome(r: Polynomial, l: usize, fcr: u8) -> Vec<u8> {
(0..l).iter().map(|j| r.eval(gf8.exp2(j + fcr))).collect::<Vec<u8>>()
}
假如我们知道哪些数据出错了,问题和方法都变成纠错码:
- 也就是知道
$e(x) = e_0 x^{n-1} + ... + e_{n-1}$ 的哪些系数非零 - 把
$x = a^j, y = y(a^j)$ 代入$e(x)$ ,得到 l 个方程。 - 也就是说,只要出错的数据小于等于l个,并且知道它们的位置,就可以解 l 个方程,得到 l 个
$e(x)$ 的系数,从而得到$e(x)$,进而还原出$s(x)$ - 这需要解一个线性方程组,复杂度为
$O(n^3)$ - 如果引入错误定位多项式,复杂度可以减少为
$O(n^2)$
引入多项式 Error locator polynomial
- 它满足
$\Lambda(X_i^{-1})=0$ ,其中$X_i$ 是错误发生的位置,我们的目标就是求出它,不过在 forney 这个步骤中,我们假设已经求出它了
引入多项式 Error evaluator polynomial
- 其中,$S(x)$ 是上面计算的 syndrome polynomial
$S(x) = S_0 +S_1 x^1 + S_2 x^2 +...+ S_{n-k-1} n^{n-k-1}$ - 取模操作$\mathrm{mod} x^{n-k}$,相当于取出低于
$n-k$ 阶的那些系数
计算可得
- 其中
$j_0$ 是前面写的第一个根,前面写了本文里面统一取0 - 一阶导数
$\Lambda'(X_i^{-1}) =\sum\limits_{i=1}^v i \cdot \lambda_i x^{i-1}$ -
$i \cdot \lambda_i$ 不是有限域上的乘法,而是连加,因此如果$i \cdot \lambda_i = \lambda_i \ \mathrm{if}\ i \ \mathrm{is \ odd, else \ 0}$
此算法的目的是找到错误定位多项式 Error locator polynomial
它是一个迭代算法