一般の \([n,k]\) RS 符号では、有限体 \(\mathbb{F}_q\) 上で互いに異なる評価点 \(\alpha_1,\alpha_2,\dots,\alpha_n\) を固定し、長さ \(k\) のメッセージ
\[ m = (m_0, m_1, \dots, m_{k-1}) \in \mathbb{F}_q^k \]
を係数とする「次数高々 \(k-1\)」の多項式
\[ f(x) = m_0 + m_1 x + \cdots + m_{k-1} x^{k-1} \]
を作ります。ここで \(\deg f \le k-1\)、すなわち「送信された曲線は \(k\) 次未満の多項式曲線」です。
評価点で多項式を評価すると、コード語（送信語）
\[ c = (c_1, \dots, c_n), \qquad c_i = f(\alpha_i) \]
を得ます。これは「評価点 \(\alpha_i\) における評価値 \(f(\alpha_i)\) を並べたもの」です。 このアプリでは、有限体の代わりに実数上で
\[ \alpha_i = i \quad (i = 1,\dots,n) \]
とおき、実数係数の多項式 \(f(x)\) を用いて“RS符号風”の状況を可視化しています。 青い点が送信値 \(c_i = f(\alpha_i)\) です。
送信途中で誤りが入ると、受信側では
\[ y_i = c_i + e_i = f(\alpha_i) + e_i \]
のように、誤りベクトル \(e = (e_1,\dots,e_n)\) が加わった受信語 \(y = (y_1,\dots,y_n)\) を観測します。 RS 符号の最小距離は \(d_{\min} = n - k + 1\) で、訂正能力は
\[ t = \left\lfloor \frac{d_{\min} - 1}{2} \right\rfloor \]
と与えられ、理論的には \(t\) 個までの誤りを訂正できます。このアプリでは 「常に \(e = t\) 個」の誤りを入れた例を表示しています。
評価点 \(\alpha_i\) が互いに異なるとき、 任意の \(k\) 個のペア \((\alpha_{i_1}, v_{i_1}),\dots,(\alpha_{i_k}, v_{i_k})\) に対して、 \[ g(x) = a_0 + a_1 x + \cdots + a_{k-1} x^{k-1} \] という形の多項式で \[ g(\alpha_{i_j}) = v_{i_j} \quad (j = 1,\dots,k) \] を満たすものは「ちょうど 1 つ」だけ存在します。
つまり「次数 \( < k \) の多項式は、k 個の評価点での値を指定すると一意に決まる」ので、 \(k\) 個の正しい評価点 \((\alpha_i, f(\alpha_i))\) が分かれば、 元の送信多項式 \(f(x)\) を完全に復元でき、その結果、すべての \(f(\alpha_i)\) が分かります。
実際に多項式 \(g(x)\) を構成する方法の 1 つが「ラグランジュ補間多項式」です。 \(k\) 個の評価点 \((\alpha_{i_1}, v_{i_1}),\dots,(\alpha_{i_k}, v_{i_k})\) に対して、ラグランジュ基底多項式
\[ L_j(x) = \prod_{\substack{m=1 \\ m \ne j}}^{k} \frac{x - \alpha_{i_m}}{\alpha_{i_j} - \alpha_{i_m}} \quad (j = 1,\dots,k) \]
を定義すると、
\[ g(x) = \sum_{j=1}^{k} v_{i_j} \, L_j(x) \]
が、すべての評価点を通る次数高々 \(k-1\) の多項式になります。 このアプリで描いている緑の曲線 \(g(x)\) は、 「選択した \(k\) 個の評価点を通る唯一の次数 \(< k\) の多項式」という意味で、 ラグランジュ補間多項式と同じ役割を果たしています （実装上は線形方程式を解いていますが、理論的にはラグランジュ公式と同値です）。
このアプリでは、常に訂正能力と同じ個数 \(e = t\) の誤りを入れた受信語を表示しています。
エラーのない点だけを \(k\) 個選べば、補間多項式 \(g(x)\) は真の送信多項式 \(f(x)\) と一致し、
送信語全体を正しく復元できます。
一方、選んだ \(k\) 個の中に誤り位置が混ざると、\(g(x)\) は \(f(x)\) からずれてしまい、
青い送信点を通らない別の曲線になります。これが「誤り訂正限界 \(t\)」の直感的なイメージです。