Reed–Solomon符号

同義語：Reed–Solomon codeReed-Solomon符号Reed-Solomon codeリード・ソロモン符号RS符号

概要

前提知識: 有限体, 線形符号, 多項式環, Lagrange補間

有限体 $\mathbb F_q$ の上の次数の低い多項式は、少ない点での値から決まってしまう。次数 $k-1$ 以下の多項式は $k$ 個の点での値で決まり、$0$ でなければ根を $k-1$ 個以下しかもたない。そこで、送りたい $k$ 個の文字を多項式の係数にして、その多項式の $n$ 個の点での値の列を送ることにすると、相異なる 2 つの値の列は少なくとも $n-k+1$ か所で異なる。こうして作る符号を Reed–Solomon 符号（Reed–Solomon code）という。長さ $n$、次元 $k$ の線形符号の最小距離は Singleton の限界により $n-k+1$ を超えないので、Reed–Solomon 符号は長さと次元を決めたときに最小距離が最大の符号である。
この記事では、Reed–Solomon 符号とその一般化を定義し、パラメータが $[n,k,n-k+1]_q$ であること（thm-rs-params）、双対符号がまた同じ形の符号になること（thm-rs-dual）、評価点を原始元の冪にとると根の条件で書ける巡回符号になること（thm-rs-cyclic）、最小距離の半分未満の個数の誤りを連立一次方程式を解くだけで訂正できること（thm-rs-wb）を証明する。

定義

以下、$q$ は素数冪、$\mathbb F_q$ は位数 $q$ の有限体とし、語・重み $\operatorname{wt}$・Hamming 距離 $d(\cdot,\cdot)$・$[n,k,d]_q$ 符号・双対符号 $C^\perp$ は線形符号の記事の意味で使う。$k\ge0$ について、次数が $k-1$ 以下の多項式（$0$ を含む）の全体を $\mathbb F_q[x]_{< k}$ と書く。これは $1,x,\dots,x^{k-1}$ を基底とする $k$ 次元の線形空間である（$\mathbb F_q[x]_{< 0}=\{0\}$）。最小距離が Singleton の限界の等号 $d=n-k+1$ を満たす $[n,k,d]_q$ 符号を MDS 符号 という。

Reed–Solomon 符号と一般化 Reed–Solomon 符号

$1\le k\le n\le q$ とし、$\mathbb F_q$ の相異なる元の列 $\mathbf a=(a_1,\dots,a_n)$ を固定する（$a_i$ を 評価点 という）。線形写像
$$ \operatorname{ev}_{\mathbf a}\colon\mathbb F_q[x]_{< k}\to\mathbb F_q^n,\qquad f\mapsto(f(a_1),\dots,f(a_n)) $$
の像を $\mathrm{RS}_q(\mathbf a,k)$ と書き、Reed–Solomon 符号 という。さらに $0$ でない元の列 $\mathbf v=(v_1,\dots,v_n)\in(\mathbb F_q^\times)^n$ について
$$ \mathrm{GRS}_q(\mathbf a,k,\mathbf v):=\{(v_1f(a_1),\dots,v_nf(a_n)) : f\in\mathbb F_q[x]_{< k}\} $$
を 一般化 Reed–Solomon 符号 という。$\mathbf v=(1,\dots,1)$ のときが Reed–Solomon 符号である。

評価点は相異なるので $n\le q$ でなければならない。符号化は、情報 $m=(m_0,\dots,m_{k-1})\in\mathbb F_q^k$ を多項式 $f_m=m_0+m_1x+\dots+m_{k-1}x^{k-1}$ に写し、その値の列 $\operatorname{ev}_{\mathbf a}(f_m)$ を送ることである（GRS25 Definition 5.2.1、p. 98）。単項式 $1,x,\dots,x^{k-1}$ の像を行に並べると $k\times n$ 行列
$$ G=\begin{pmatrix}1&1&\cdots&1\\a_1&a_2&\cdots&a_n\\\vdots&\vdots&&\vdots\\a_1^{k-1}&a_2^{k-1}&\cdots&a_n^{k-1}\end{pmatrix} $$
が得られ、符号化は $m\mapsto mG$ と書ける。$G$ は（転置した）Vandermondeの行列式の Vandermonde 行列で、その行が一次独立であること、つまり $G$ が生成行列であることは thm-rs-params で示す。
一般化 Reed–Solomon 符号は Reed–Solomon 符号の第 $i$ 座標を $v_i$ 倍したもので、Hamming 距離の性質は同じである。一般化を考えるのは、双対符号をとると自然に現れるからである（thm-rs-dual）。

小さい Reed–Solomon 符号

$q=3$、$\mathbf a=(0,1,2)$、$k=2$ とする。$1$ 次以下の多項式 $m_0+m_1x$ の値の列 $(m_0,\ m_0+m_1,\ m_0+2m_1)$ の全体で、$9$ 個の符号語は
$$ 000,\ 111,\ 222,\ 012,\ 120,\ 201,\ 021,\ 102,\ 210 $$
である。$0$ でない符号語の重みは $2$ か $3$ なので、$[3,2,2]_3$ 符号である。
$q=7$、$\mathbf a=(1,2,3,4,5,6)$、$k=2$ とすると $[6,2,5]_7$ 符号になる（thm-rs-params）。$f=2+3x$ の符号語は $(5,1,4,0,3,6)$ である。この符号は ex-rs-wb で復号の例に使う。

主定理：パラメータ

Reed–Solomon 符号のパラメータ

$1\le k\le n\le q$ とし、$\mathbf a$ を相異なる評価点の列、$\mathbf v\in(\mathbb F_q^\times)^n$ とする。

写像 $f\mapsto(v_if(a_i))_{i}$ は $\mathbb F_q[x]_{< k}$ から $\mathbb F_q^n$ への単射であり、$\mathrm{GRS}_q(\mathbf a,k,\mathbf v)$ は $[n,k,n-k+1]_q$ 符号、すなわち MDS 符号である。
$\lvert S\rvert=k$ を満たす任意の座標の番号の集合 $S\subset\{1,\dots,n\}$ について、符号語を $S$ の座標に制限する写像 $\mathrm{GRS}_q(\mathbf a,k,\mathbf v)\to\mathbb F_q^S$ は全単射である。

1：$f\in\mathbb F_q[x]_{< k}$ が $0$ でないとき、$f$ の根は高々 $\deg f\le k-1$ 個である（多項式環の定理「根の個数」）。$v_i\neq0$ なので、$v_if(a_i)=0$ となる番号 $i$ は $f(a_i)=0$ となる番号で、評価点が相異なるからその個数は $k-1$ 以下である。よって符号語 $(v_if(a_i))_i$ の重みは $n-k+1$ 以上で、とくに $0$ でない。したがって写像は単射な線形写像で、像の次元は $k$ である。線形符号の命題「最小距離と最小の重み」により最小距離は $n-k+1$ 以上であり、線形符号の定理「Singleton の限界」により $n-k+1$ 以下だから、$n-k+1$ に等しい。
2：制限写像は線形である。符号語 $c$ の $S$ への制限が $0$ なら、$c$ の重みは $n-k$ 以下なので、1 により $c=0$ である。よって制限写像は単射で、両辺の次元はともに $k$ だから全単射である。$\square$

$\mathbf v=(1,\dots,1)$ の場合は GRS25 Theorem 5.2.4（p. 100）にある。2 の逆写像は具体的に書ける。$S=\{i_1,\dots,i_k\}$ と値 $w_{i_1},\dots,w_{i_k}$ が与えられたら、$f(a_{i_s})=w_{i_s}/v_{i_s}$（$s=1,\dots,k$）を満たす $f\in\mathbb F_q[x]_{< k}$ を Lagrange補間の補間公式で作り、$(v_if(a_i))_i$ を返せばよい。

消失の訂正

$\mathrm{GRS}_q(\mathbf a,k,\mathbf v)$ の符号語は、高々 $n-k$ 個の座標の値が失われても、残りの座標の値から一意に復元できる。

残る座標は $k$ 個以上あるので、そこから $k$ 個を選んで $S$ とし、thm-rs-params の 2 の全単射の逆写像を当てればよい。$\square$

位置の分かっている誤り（消失）は $n-k$ 個まで直せるのに対し、位置の分からない誤りは、最小距離 $d=n-k+1$ から線形符号の定理「訂正できる誤りの個数」により $\lfloor(n-k)/2\rfloor$ 個までしか一意に直せない。その個数の誤りを実際に直す計算が thm-rs-wb である。

双対符号

Reed–Solomon 符号の双対符号は、評価点を変えずに次元を $n-k$ にし、座標に重みを掛けたものになる。鍵になるのは、多項式の値の重み付き和についての次の恒等式である。

値の重み付き和

$n\ge2$ とし、$a_1,\dots,a_n\in\mathbb F_q$ を相異なる元とする。$w_i:=\prod_{j\neq i}(a_i-a_j)^{-1}$ とおくと、次数 $n-2$ 以下の任意の多項式 $h$ について
$$ \sum_{i=1}^nw_i\,h(a_i)=0 $$
が成り立つ。

要点：$h$ を Lagrange の補間公式で書き、$x^{n-1}$ の係数を比べる。

詳しい証明を開く

補間点 $a_1,\dots,a_n$ に対する Lagrange の基本多項式 $L_i(x)=\prod_{j\ne i}\frac{x-a_j}{a_i-a_j}$ は次数 $n-1$ で、$x^{n-1}$ の係数は $w_i$ である。$h$ は次数 $n$ 未満なので、Lagrange補間の定理「Lagrange 補間」により $h=\sum_{i=1}^nh(a_i)L_i$ と書ける。両辺の $x^{n-1}$ の係数を比べると、左辺は $\deg h\le n-2$ なので $0$、右辺は $\sum_iw_ih(a_i)$ である。$\square$

双対符号

$1\le k\le n-1$、$n\le q$ とし、$\mathbf a$ を相異なる評価点の列、$\mathbf v\in(\mathbb F_q^\times)^n$ とする。
$$ u_i:=\Bigl(v_i\prod_{j\neq i}(a_i-a_j)\Bigr)^{-1}\qquad(i=1,\dots,n) $$
とおくと
$$ \mathrm{GRS}_q(\mathbf a,k,\mathbf v)^\perp=\mathrm{GRS}_q(\mathbf a,n-k,\mathbf u) $$
である。とくに、一般化 Reed–Solomon 符号の双対符号は一般化 Reed–Solomon 符号であり、MDS 符号である。

$f\in\mathbb F_q[x]_{< k}$、$g\in\mathbb F_q[x]_{< n-k}$ に対応する 2 つの符号語の内積は、$w_i$ を lem-rs-sum のものとして
$$ \sum_{i=1}^n v_if(a_i)\cdot u_ig(a_i)=\sum_{i=1}^n w_i\,(fg)(a_i) $$
である。$fg$ は $0$ か次数 $(k-1)+(n-k-1)=n-2$ 以下の多項式なので、lem-rs-sum によりこの和は $0$ である。よって右辺の符号は左辺の符号の双対符号に含まれる。thm-rs-params により右辺の次元は $n-k$ であり、線形符号の命題「双対符号の次元」により左辺の双対符号の次元も $n-k$ だから、両者は等しい。最後の主張は thm-rs-params を右辺に当てればよい。$\square$

この主張は GRS25 Exercise 5.10（pp. 104–105）に演習として挙げられている。thm-rs-dual は $\mathrm{RS}_q(\mathbf a,k)$ の検査行列を具体的に与える。$u_i=\prod_{j\ne i}(a_i-a_j)^{-1}$ として、$(n-k)\times n$ 行列
$$ H=\begin{pmatrix}u_1&u_2&\cdots&u_n\\u_1a_1&u_2a_2&\cdots&u_na_n\\\vdots&\vdots&&\vdots\\u_1a_1^{n-k-1}&u_2a_2^{n-k-1}&\cdots&u_na_n^{n-k-1}\end{pmatrix} $$
の行は $\mathrm{GRS}_q(\mathbf a,n-k,\mathbf u)$ の基底であり、線形符号の命題「双対符号の次元」の 2 により $H$ は $\mathrm{RS}_q(\mathbf a,k)$ の検査行列である。
評価点が $\mathbb F_q$ の全体のときは、重み $u_i$ がすべて等しくなる。

評価点が体全体のときの双対

$\mathbf a$ を $\mathbb F_q$ の $q$ 個の元を並べた列とすると、$1\le k\le q-1$ について $\mathrm{RS}_q(\mathbf a,k)^\perp=\mathrm{RS}_q(\mathbf a,q-k)$ である。とくに $q$ が偶数なら $\mathrm{RS}_q(\mathbf a,q/2)$ は自己双対である。

要点：$x^q-x=\prod_j(x-a_j)$ を微分して $a_i$ を代入すると $\prod_{j\ne i}(a_i-a_j)=-1$ が分かり、thm-rs-dual の重みがすべて $-1$ になる。

詳しい証明を開く

有限体の系「有限体における $x^q=x$」により $x^q-x=\prod_{j=1}^q(x-a_j)$ である。両辺を形式微分する。右辺の微分は積の微分の規則（多項式環の命題「微分の規則」）により $\sum_{l=1}^q\prod_{j\ne l}(x-a_j)$ で、$x=a_i$ を代入すると $l=i$ の項だけが残り $\prod_{j\ne i}(a_i-a_j)$ になる。左辺の微分は $qx^{q-1}-1=-1$ である（$\mathbb F_q$ の標数は $q$ を割り切る）。よって $\prod_{j\ne i}(a_i-a_j)=-1$ がすべての $i$ について成り立ち、thm-rs-dual の $\mathbf u$ は $(-1,\dots,-1)$ になる。符号は線形空間なので各座標を $-1$ 倍しても変わらず、$\mathrm{RS}_q(\mathbf a,k)^\perp=\mathrm{RS}_q(\mathbf a,q-k)$ である。$q$ が偶数で $k=q/2$ なら $q-k=k$ で、自己双対である。$\square$

$\mathbf v=(1,\dots,1)$ でも評価点が体全体でないと、双対符号は一般には Reed–Solomon 符号そのものにはならない（ex-rs-dual-counter）。

反例：重みが要る双対

$q=5$、$\mathbf a=(0,1,2)$、$k=1$ とする。$\mathrm{RS}_5(\mathbf a,1)$ は定数の値の列 $(c,c,c)$ の全体で、その双対符号は $x_1+x_2+x_3=0$ で定まる $2$ 次元の符号である。一方 $\mathrm{RS}_5(\mathbf a,2)$ は $f=x$ の符号語 $(0,1,2)$ を含み、$0+1+2=3\neq0$ なので双対符号と一致しない。thm-rs-dual の重みは $\prod_{j\ne i}(a_i-a_j)=2,\,-1,\,2$ の逆元で $\mathbf u=(3,4,3)$ であり、実際 $3\cdot0+4\cdot1+3\cdot2=10=0$ である。

原始元の冪で評価する場合と巡回性

評価点を原始元の冪 $1,\alpha,\alpha^2,\dots$ の順に並べると、Reed–Solomon 符号は「ある連続した冪で $0$ になる多項式」の係数の列として書き直せる。$\alpha$ を $\mathbb F_q$ の原始元（乗法群 $\mathbb F_q^\times$ の生成元。有限体の定理「有限体の乗法群の構造」により存在する）とし、$n=q-1$ とする。この節では符号語の座標の番号を $0$ から始め、語 $c=(c_0,\dots,c_{n-1})$ に多項式 $c(x)=c_0+c_1x+\dots+c_{n-1}x^{n-1}$ を対応させる。

根の条件による記述

$n=q-1$、$1\le k\le n$、$\alpha$ を $\mathbb F_q$ の原始元とし、$\mathbf a=(1,\alpha,\alpha^2,\dots,\alpha^{n-1})$ とする。このとき
$$ \mathrm{RS}_q(\mathbf a,k)=\{c\in\mathbb F_q^n : c(\alpha^j)=0\ (j=1,2,\dots,n-k)\} $$
である。とくに $\mathrm{RS}_q(\mathbf a,k)$ は巡回シフト $(c_0,\dots,c_{n-1})\mapsto(c_{n-1},c_0,\dots,c_{n-2})$ で閉じている。

右辺を $D$ とおく。$f=\sum_{m=0}^{k-1}f_mx^m$ の符号語 $c$（$c_i=f(\alpha^i)$）と $1\le j\le n-k$ について
$$ c(\alpha^j)=\sum_{i=0}^{n-1}f(\alpha^i)\alpha^{ij}=\sum_{m=0}^{k-1}f_m\sum_{i=0}^{n-1}\alpha^{i(m+j)} $$
である。$1\le m+j\le n-1$ なので $\beta=\alpha^{m+j}\ne1$（$\alpha$ の位数は $n$）で、$(\beta-1)\sum_{i=0}^{n-1}\beta^i=\beta^n-1=0$ から内側の和は $0$ である。よって $\mathrm{RS}_q(\mathbf a,k)\subset D$ である。
$D$ は $(n-k)\times n$ 行列 $M=\bigl((\alpha^j)^i\bigr)_{1\le j\le n-k,\ 0\le i\le n-1}$ の核で、$M$ の階数は $n-k$ である（下の詳細）。次元定理により $\dim D=k$ で、$\mathrm{RS}_q(\mathbf a,k)$ の次元も $k$（thm-rs-params）なので両者は等しい。

詳細

$M$ の最初の $n-k$ 列からなる正方行列は、相異なる元 $\alpha,\alpha^2,\dots,\alpha^{n-k}$（$n-k< n$ なので相異なる）の Vandermonde 行列 $V(\alpha,\alpha^2,\dots,\alpha^{n-k})$ なので、Vandermondeの行列式の命題「正則性の判定」により正則である。

巡回性：$c\in D$ の巡回シフト $c'$ は $c'(x)\equiv xc(x)\pmod{x^n-1}$ を満たし、$(\alpha^j)^n=1$ なので $c'(\alpha^j)=\alpha^jc(\alpha^j)=0$ である。よって $c'\in D$ である。$\square$

この記述は GRS25 Exercise 5.9（p. 104）に演習として挙げられている。thm-rs-cyclic は、$\mathrm{RS}_q(\mathbf a,k)$ が巡回符号であり、その生成多項式が $g(x)=\prod_{j=1}^{n-k}(x-\alpha^j)$ であることを意味する。巡回符号の側から見ると、thm-rs-params の最小距離の評価は、連続した $n-k$ 個の冪 $\alpha,\dots,\alpha^{n-k}$ を根にもつことから最小距離が $n-k+1$ 以上になるという BCH の限界（巡回符号の定理「BCH の限界」）の特別な場合である。歴史的には、Reed と Solomon は値の列として符号を定義し、のちに Gorenstein と Zierler がこの根による記述と BCH 符号との関係を示した（GRS25 第 5 章の文献の注、p. 112）。
評価点を原始元の冪の順に並べることは巡回性に効いている。同じ $\mathbb F_q^\times$ の元を別の順に並べた符号は、座標の並べ替えで $\mathrm{RS}_q(\mathbf a,k)$ と移り合うので距離の性質は同じだが、巡回シフトで閉じるとは限らない（下の反例の表の 5 行目）。

復号

Welch–Berlekamp の方法

送った符号語を $\operatorname{ev}_{\mathbf a}(f)$、受け取った語を $y=(y_1,\dots,y_n)$ とし、$y_i\neq f(a_i)$ となる番号 $i$ の集合（誤りの位置）を $I$ とする。$E(x)=\prod_{i\in I}(x-a_i)$ は誤りの位置で $0$ になる多項式で、すべての $i$ について $f(a_i)E(a_i)=y_iE(a_i)$ が成り立つ（$i\in I$ なら両辺が $0$、$i\notin I$ なら $f(a_i)=y_i$）。$f$ も $E$ も分からないので、この等式は未知の係数どうしの積を含むが、積 $Q:=fE$ を新しい未知数にすると、$Q(a_i)=y_iE(a_i)$ は $E$ と $Q$ の係数についての連立一次方程式になる。次の定理は、この一次方程式のどの解からも $f$ が $Q/E$ として取り出せることを述べる。

Welch–Berlekamp の復号

$1\le k\le n\le q$、$\mathbf a$ を相異なる評価点の列、$e:=\lfloor(n-k)/2\rfloor$ とし、語 $y\in\mathbb F_q^n$ について、多項式の組 $(E,Q)$ に関する次の条件を (WB) とよぶ。
$$ E\neq0,\quad\deg E\le e,\quad Q=0\ \text{または}\ \deg Q\le e+k-1,\quad Q(a_i)=y_iE(a_i)\ \ (i=1,\dots,n). $$
$f\in\mathbb F_q[x]_{< k}$ が $d(y,\operatorname{ev}_{\mathbf a}(f))\le e$ を満たすとする。

$E$ が次数 $e$ のモニック多項式であって (WB) を満たす組 $(E,Q)$ が存在する。
(WB) を満たす任意の組 $(E,Q)$ について、$E$ は $Q$ を割り切り、$Q/E=f$ である。

1：$I=\{i : y_i\neq f(a_i)\}$ とおくと $\lvert I\rvert\le e$ である。$E_0:=x^{e-\lvert I\rvert}\prod_{i\in I}(x-a_i)$ は次数 $e$ のモニック多項式で、$Q_0:=fE_0$ は $0$ か次数 $(k-1)+e$ 以下である。$i\in I$ なら $E_0(a_i)=0$ なので $Q_0(a_i)=0=y_iE_0(a_i)$、$i\notin I$ なら $y_i=f(a_i)$ なので $Q_0(a_i)=f(a_i)E_0(a_i)=y_iE_0(a_i)$ である。よって $(E_0,Q_0)$ は (WB) を満たす。
2：$(E,Q)$ が (WB) を満たすとし、1 の $(E_0,Q_0)$ を使って $R:=QE_0-Q_0E$ とおく。$R$ は $0$ か次数 $(e+k-1)+e=2e+k-1$ 以下で、$2e\le n-k$ だから次数は $n-1$ 以下である。各 $i$ について
$$ R(a_i)=Q(a_i)E_0(a_i)-Q_0(a_i)E(a_i)=y_iE(a_i)E_0(a_i)-y_iE_0(a_i)E(a_i)=0 $$
なので、$R$ は相異なる $n$ 個の根 $a_1,\dots,a_n$ をもち、多項式環の定理「根の個数」により $R=0$ である。よって $QE_0=Q_0E=fE_0E$ で、$E_0\neq0$ と $\mathbb F_q[x]$ が整域であることから $Q=fE$ である。$\square$

この定理から次の復号の手順が得られる（GRS25 Algorithm 12.1.1・Theorem 12.1.3、p. 241）。

$E=x^e+\sum_{l=0}^{e-1}\varepsilon_lx^l$、$Q=\sum_{l=0}^{e+k-1}\kappa_lx^l$ とおき、$n$ 本の一次方程式 $Q(a_i)=y_iE(a_i)$ を $2e+k$ 個の未知数 $\varepsilon_l,\kappa_l$ について掃き出し法で解く。
解がなければ、または $E\nmid Q$ ならば、距離 $e$ 以内に符号語はないと答える。
$f:=Q/E$ とし、$\deg f\le k-1$ かつ $d(y,\operatorname{ev}_{\mathbf a}(f))\le e$ なら $f$ を、そうでなければ「距離 $e$ 以内に符号語はない」を返す。
距離 $e$ 以内に $\operatorname{ev}_{\mathbf a}(f)$ があれば、1 により手順 1 は解をもち、2 によりどの解からも同じ $f$ が得られるので、手順は $f$ を返す。距離 $e$ 以内に符号語がなければ、手順 3 まで進んでも確かめを通らないので、手順 2 か手順 3 で必ず「ない」と答える。同じ組 $(E,Q)$ を、拡張 Euclid の互除法の途中に現れる多項式として求める方法もある（Sho08 §17.5.2、pp. 476–477。この記事では証明しない）。

長さ $6$ の符号の 2 個の誤りの訂正

$q=7$、$\mathbf a=(1,2,3,4,5,6)$、$k=2$ とすると $e=\lfloor4/2\rfloor=2$ である。$f=2+3x$ の符号語 $(5,1,4,0,3,6)$ を送り、第 2・第 5 座標が化けて $y=(5,2,4,0,1,6)$ を受け取ったとする。$E=x^2+\varepsilon_1x+\varepsilon_0$、$Q=\kappa_0+\kappa_1x+\kappa_2x^2+\kappa_3x^3$ について $6$ 本の方程式 $Q(a_i)=y_iE(a_i)$ を解くと、解は
$$ E=x^2+3,\qquad Q=3x^3+2x^2+2x+6 $$
の 1 組だけである。実際、$E(a_i)$ は順に $4,0,5,5,0,4$、$y_iE(a_i)$ と $Q(a_i)$ はどちらも順に $6,0,6,0,0,3$ になる。割り算をすると $Q=(3x+2)(x^2+3)$ で、$Q/E=3x+2=f$ が復元される。$E$ の根は $x^2=-3=4$ の解 $x=2,5$ で、化けた座標の評価点にちょうど一致する。

$E$ の根が誤りの位置を表すことから、$E$ を 誤り位置多項式 という。(WB) の解では $Q=fE$ なので $E(a_i)(y_i-f(a_i))=0$ となり、$E$ は誤りの位置で $0$ になる。よって上の例のように誤りがちょうど $e$ 個なら、次数 $e$ のモニックな解 $E$ は誤りの位置で決まるが、誤りが $e$ 個より少ないとモニックな解 $E$ も一意でない。それでも thm-rs-wb の 2 により商 $Q/E$ は変わらない。

バースト誤り

$q=2^m$ のとき、$\mathbb F_q$ は $\mathbb F_2$ の上の $m$ 次元の線形空間なので（有限体の命題「有限体の位数」）、基底を 1 つ固定すれば各文字を $m$ ビットの列で表せる。$\mathrm{RS}_q(\mathbf a,k)$ の符号語を文字ごとに $m$ ビットに展開して $nm$ ビットの列として送ると、連続したビットがまとめて化ける誤り（バースト誤り）に強い。

バースト誤りが触れる文字の個数

$q=2^m$、$t\ge1$ とする。$nm$ ビットの列の中の連続する $b$ ビット（$b\le(t-1)m+1$）は、高々 $t$ 個の文字の範囲にしか含まれない。したがって $t\le\lfloor(n-k)/2\rfloor$ なら、長さ $(t-1)m+1$ 以下のバースト誤りは thm-rs-wb で訂正できる。

要点：バーストの先頭が文字の境目からずれていても、触れる文字の番号の差は $t-1$ 以下になる。

詳しい証明を開く

ビットの番号を $0$ から $nm-1$、第 $l$ 文字が受け持つビットを $lm,\dots,lm+m-1$ とする。バーストがビット $s,\dots,s+b-1$ を占めるとき、触れる文字の番号は $\lfloor s/m\rfloor$ から $\lfloor(s+b-1)/m\rfloor$ までである。$s=\lfloor s/m\rfloor m+r$（$0\le r\le m-1$）と書くと

$$\Bigl\lfloor\frac{s+b-1}m\Bigr\rfloor-\Bigl\lfloor\frac sm\Bigr\rfloor=\Bigl\lfloor\frac{r+b-1}m\Bigr\rfloor\le\Bigl\lfloor\frac{(m-1)+(t-1)m}m\Bigr\rfloor=t-1$$

なので、触れる文字は $t$ 個以下である。よって化けた文字は $t$ 個以下で、$t\le\lfloor(n-k)/2\rfloor$ なので後半は thm-rs-wb から従う。$\square$

ビット単位で $(t-1)m+1$ 個もの誤りを、文字単位では $t$ 個の誤りとして扱えることがこの使い方の利点である（GRS25 Exercise 5.16、p. 107 も参照）。

一意に復号できる範囲を超えて

$\lfloor(n-k)/2\rfloor$ 個を超える誤りがあると、最も近い符号語が送った符号語とは限らない（下の反例の表の 4 行目）。それでも、近い符号語の候補を少数に絞ることはできる。情報率 $R=k/n$ の Reed–Solomon 符号について、誤りの割合が $1-\sqrt R$ までなら、受け取った語に近い符号語をすべて多項式時間で列挙するアルゴリズムがある（Guruswami–Sudan のリスト復号。正確な主張は GRS25 Theorem 12.2.12、p. 257、由来は第 12 章の文献の注、pp. 269–270。この記事では証明しない）。$0< R< 1$ なら $(1-\sqrt R)^2>0$ から $1-\sqrt R>(1-R)/2$ なので、この範囲は一意に復号できる誤りの割合 $(1-R)/2$ より広い。

反例

外す条件	反例	成り立たなくなること
評価点が相異なる（thm-rs-params）	$q=3$、$\mathbf a=(0,0,1)$、$k=2$	最小距離が $n-k+1$ に等しい
$k\le n$（thm-rs-params）	$q=3$、$\mathbf a=(0,1,2)$、$k=4$	$\operatorname{ev}_{\mathbf a}$ が単射で次元が $k$
評価点が $\mathbb F_q$ の全体（cor-rs-dual-full）	$q=5$、$\mathbf a=(0,1,2)$、$k=1$	$\mathrm{RS}_q(\mathbf a,k)^\perp=\mathrm{RS}_q(\mathbf a,n-k)$
誤りが $\lfloor(n-k)/2\rfloor$ 個以下（thm-rs-wb）	$q=5$、$\mathbf a=(0,1,2,3,4)$、$k=3$ で $0$ を送り $(0,0,2,1,0)$ を受け取る	最も近い符号語が送った符号語である
評価点を原始元の冪の順に並べる（thm-rs-cyclic）	$q=5$、$\mathbf a=(1,2,3,4)$、$k=2$	巡回シフトで閉じる

反例の確認

各行の反例は、外した条件のほかはすべての仮定を満たす。

各行の確認を開く

1 行目：$n=3\le q$、$k=2$ で、$f=x$ の値の列 $(0,0,1)$ は重み $1$ の $0$ でない符号語なので、最小距離は $1< 2=n-k+1$ である。

2 行目：評価点は相異なり $n=q=3$ だが $k=4>n$ である。$x^3-x$ は $0$ でない次数 $3\le k-1$ の多項式で、有限体の系「有限体における $x^q=x$」により $\mathbb F_3$ のすべての元で $0$ になるので、$\operatorname{ev}_{\mathbf a}$ は単射でなく、像の次元は $3< 4$ である。

3 行目：ex-rs-dual-counter のとおりである。評価点は $\mathbb F_5$ の全体でない。

4 行目：$e=\lfloor2/2\rfloor=1$ だが誤りは第 3・第 4 座標の $2$ 個である。$f=x^2-x$ の符号語は $(0,0,2,1,2)$ で、受け取った語からの距離は $1$ であり、送った $0$ からの距離 $2$ より小さい。

5 行目：評価点は $\mathbb F_5^\times$ の全体だが、原始元 $2$ の冪の順 $(1,2,4,3)$ ではない。$f=x$ の符号語 $(1,2,3,4)$ の巡回シフト $(4,1,2,3)$ が符号語なら、$f(1)=4$、$f(2)=1$ を満たす $1$ 次以下の $f$ は $f=2+2x$ だけで、$f(3)=8=3\neq2$ となり矛盾する。原始元の冪の順 $(1,2,4,3)$ に並べ直せば、thm-rs-cyclic により巡回シフトで閉じる。

補足

Reed–Solomon 符号は、多項式の根の個数という初等的な事実から Singleton の限界の等号を実現し、符号化も復号も多項式の計算で書けるので、実際の通信や記録でも広く使われている（GRS25 第 5 章の冒頭、p. 93）。長さは $n\le q$ に限られるので、二元のような小さい文字の集合で使うには、prop-rs-burst のように文字をビットの列に展開するか、成分が部分体に入る符号語だけをとる（二元の BCH 符号はこうして得られる。GRS25 Exercise 5.11、p. 105）。後者は元の符号の部分集合なので、最小距離は $n-k+1$ 以上のままである。