バーレカンプ–ウェルチアルゴリズム
バーレカンプ–ウェルチアルゴリズム, または ウェルチ–バーレカンプアルゴリズムは，エルウィン・バーレカンプと Lloyd R. Welch から命名された復号アルゴリズムで，メッセージ m 1 , ⋯ , m k {\displaystyle m_{1},\cdots ,m_{k}} を多項式 F ( a i ) {\displaystyle F(a_{i})} の係数として使用するか，ラグランジュ補間に用いるかの何れかによって a 1 , ⋯ , a k {\displaystyle a_{1},\cdots ,a_{k}} を入力とする k {\displaystyle k} 次未満の多項式 F ( a i ) {\displaystyle F(a_{i})} を生成し，次に F ( a i ) {\displaystyle F(a_{i})} に a k + 1 , ⋯ , a n {\displaystyle a_{k+1},\cdots ,a_{n}} を代入して符号語 c 1 , ⋯ , c n {\displaystyle c_{1},\cdots ,c_{n}} を生成するという，元来のリード・ソロモン符号における誤り訂正において効果的である。 復号アルゴリズムの目的は，分かっている入力 a 1 , ⋯ , a n {\displaystyle a_{1},\cdots ,a_{n}} と，誤りを含む可能性のある受信した符号語 b 1 , ⋯ , b n {\displaystyle b_{1},\cdots ,b_{n}} を用いて，もともとの符号化多項式 F ( a i ) {\displaystyle F(a_{i})} を復元することである。