折叠 Reed–Solomon 码 | Codeboy's Blog

形式陈述

设 $\gamma$ 是有限域 $\mathbb F_q^\times$ 的生成元，取 $n\le q-1$ 且折叠参数 $m\mid n$ 。底层Reed–Solomon 码把次数小于 $k$ 的多项式 $f$ 依次评价于

1,\gamma,\gamma^2,\ldots,\gamma^{n-1}.

$m$ -folded RS 码把连续 $m$ 个评价组成一个符号：

\operatorname{FRS}(f)_j =\bigl( f(\gamma^{jm}),f(\gamma^{jm+1}),\ldots, f(\gamma^{jm+m-1}) \bigr), \quad 0\le j<N=\frac nm.

新块长是 $N=n/m$ ，字母表是 $\mathbb F_q^m$ ，消息数仍为 $q^k$ ，故按新字母表归一化的码率为

\frac{\log_{q^m}q^k}{N} =\frac{k}{n}.

折叠没有添加评价，也没有改变底层信息量；它改变的是错误按“大符号”计数的方式，以及译码器能否同时利用同一轨道上 $f(X),f(\gamma X),\ldots$ 的相关性。若一个 folded symbol 为零，则对应 $m$ 个互异评价点全是根；因此非零次数小于 $k$ 的多项式至多有 $\lfloor(k-1)/m\rfloor$ 个全零折叠符号，距离至少

N-\left\lfloor\frac{k-1}{m}\right\rfloor.

直觉

普通 RS 译码逐点评价 $f(\alpha)$ 。折叠把同一乘法轨道上的一小段“连续镜头”交给算法：若接收的一个大符号正确，译码器同时得到 $f(X),f(\gamma X),\ldots$ 在相关点上的一致观测。多元插值可把大量正确块转化为一个关于这些移位多项式的代数关系，再用线性代数或因式结构约束候选 $f$ 。

关键不只是把 alphabet 变大。任意把不相关 RS 坐标分组会改变符号错误口径，却没有乘法移位关系；容量型译码使用的正是 $\gamma$ 轨道结构。评价点必须互异，分组也不能重叠，否则距离计数和插值方程都会改变。

例子与边界

在 $\mathbb F_7$ 中， $3$ 生成乘法群，幂次依次为

1,3,2,6,4,5.

取 $n=6,m=2$ 与 $f(x)=x^2+1$ 。六个评价为

f(1)=2,\ f(3)=3,\ f(2)=5,\ f(6)=2,\ f(4)=3,\ f(5)=5 \pmod7,

所以折叠码字是

\bigl((2,3),(5,2),(3,5)\bigr).

消息多项式有三个系数时 $k=3$ ，按 $\mathbb F_7^2$ 字母表计，码率为 $3/6=1/2$ ，而不是把块长三直接误算成 $3/3$ 。

Guruswami–Rudra 的容量型结论是一个参数族陈述：对任意固定 $0<R<1$ 与 $\varepsilon>0$ ，可选择域、折叠和插值参数，显式得到码率至少 $R$ 、可在多项式时间从 $1-R-\varepsilon$ 比例符号错误中列表译码的 FRS 码。列表大小与运行时间的多项式次数、alphabet 大小都依赖 $\varepsilon$ 。若改成列表恢复，还必须写出每坐标输入列表上界 $\ell$ 、agreement 与输出列表界；不能只把“列表译码容量”换一个名词。

推论与应用

FRS 首次给出显式、可高效译码并达到大字母表列表译码容量的码族，说明普通 RS 的已知译码半径限制不来自 MDS 距离本身，而来自逐点算法没有利用更丰富的相关结构。后续线性代数译码减少了原始多元插值的复杂度，并把 folded RS 与重数码放进相近的函数方程框架。

折叠后的单个符号包含 $m\log q$ bit；bit 错误、底层 RS 符号错误与 folded-symbol 错误是三种不同口径。应用到分组存储或级联码时，应明确噪声如何映射到大符号，不能只报告 $1-R-\varepsilon$ 而省略封装模型。

参考资料

Venkatesan Guruswami and Atri Rudra, “Explicit Codes Achieving List Decoding Capacity: Error-Correction with Optimal Redundancy,” IEEE Transactions on Information Theory 54(1), 2008, 135–150.
Venkatesan Guruswami, “Linear-Algebraic List Decoding of Folded Reed–Solomon Codes,” Proceedings of CCC, 2011, 77–85.
Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, and Mary Wootters, “Improved List Decoding of Folded Reed–Solomon and Multiplicity Codes,” SIAM Journal on Computing 49(3), 2020, 661–693.

形式陈述 ​

形式陈述