誤り訂正符号化とは、データを扱うとき一部に欠損があっても、正しい情報を復元できるようなものです。ネットワークを通してデータを送信するとき、例えば通信経路上で電圧の変動があったりすると 0と1が正しく送られなかったりします。また、CD-ROMに傷が付いてしまったり、バーコードがかすれていたり… と、世の中にデータが欠損してしまう例はいくらでもあります。
これを防ぐため、一般に符号化が行われます。たとえば、[0,1,0]というデータを送るのに、各データを三回繰り返して送ることにします。([0,0,0,1,1,1,0,0,0]となります) すると、この中の信号の一つが0から1に誤ってしまっても、正しくデータを復元できます。しかし、元々のデータに比べて伝えるデータは長くなってしまいます。このように、送るべきデータを変換することを符号化といいます。特にデータサイズを減らす符号化は圧縮と呼ばれ、符号化というとエラー訂正用のものを指すことが多いようです。

エラー訂正 (線形符号) 超入門

ここではエラー訂正についての符号化を説明します。エラー訂正は「虫食い算を解く」のと同じようなものです。例えば x と y を送るとき、普通に

x y

と送ると、x または y がエラーで誤った値になっても、受け取る側は誤りに気付きません。
これに対し、

z = (x + y)

を計算して、この z も一緒に送ることにします。

x y z

こうすると、x が失われたら

z = (? + y)

の ? を解いて、残った z と y から (z - y) によって x が求められるし、y が失われたら (z - x) によって x が求められます。
もう少し一般化すると、エラー訂正の対象となるるデータは、有限の長さのビット列です。エラー訂正の理論では、元のデータ {d0, d1, ... } を関数 f(d0, d1, ...) に代入して、エラー訂正データ {c0, c1, ...} を計算します。関数 f はとりあえず一次式を考えることにすると、

c0 = a00 * d0 + a01 * d1 + a02 * d2 +...
c1 = a10 * d0 + a11 * d1 + a12 * d2 +...

みたいな計算でc0, c1...を計算します。(a00, a01, a10 は定数)
もしもいずれかのデータが失われたら、分からないデータを ? とおいて「虫食い算」(方程式) を解けばいいわけです。元々のc0, c1,...を上のような「定数倍の和」で計算している場合は、連立一次方程式を解くという問題に帰着されます。
例をあげます。d0, d1, d2, d3というデータがあるとき、c0, c1を以下のように計算します。 (d0, d1, d2, d3は普通の整数だと思ってください)

c0 = 1 * d0 + 1 * d1 + 1 * d2 + 1 * d3
c1 = 1 * d0 + 2 * d1 + 3 * d2 + 4 * d3

ここで、

c0かc1(またはその両方)が失われたら、上の式から再計算
d0, d1, d2, d3の中で最大二つが失われたら、上式を変数二つの一次方程式と見て解く
(c0かc1の片方)と(d0,d1,d2,d3のどれか)が同時に失われたら、まず失われたdを上の式から求め、さらにcを再計算

として、データ6個中2個の欠損に対応することができます。
注意しないといけないのはもa00とかの定数をある程度工夫しないと、連立一次方程式が解けなくなってしまう場合があることです。例えばa00 = a10, a01 = a11 ,...だとc0は常にc1となり、データ二つの欠損に対応できなくなります。このため、用いる行列としてはある程度制限がかかってきます。線形台数の理論の方で、a_ijとしては、"Vandermonde行列"を用いると常に方程式が解け、また後の連立一次方程式も解きやすいことが知られています。 Vandermond行列は以下のようなものです。

1   1   1   1
1   2   3   4
1   4   9  16
1   8  27  32

a_ij = i^jです。なかなか覚えやすい形ですね。

普通の四則演算への不満

ここまでは、"普通の"数学として見てきましたが、エラー訂正が使われるのは主にコンピュータの世界です。コンピュータが扱う数値は、普通の数値とは少し異なって、最大値と最小値が決まっているのが普通です。文字を表す char (unsigned) だと、最小が 0, 最大が 255 だったり、32bit 整数 (int) だと最大が 2147483647 で最小が -2147483648 だったりします。
ここで、先ほどのエラー訂正の一次方程式の演算を考えてみると、計算中に桁があふれてしまうことが問題になります。
例えば、8ビットのデータa,bを符号化する場合を考えます。例えば次のような演算があったとします。

c = a + b;
d = a * b;

ここでa,bは8ビット、つまり{0 <= a,b < 256}ですが、c はこの範囲に収まらない可能性があります。例えば a = 200, b = 100だとc = 300、d = 20000になりるので、c には9ビット、d には16ビットの符号長が必要になります。もっと複雑な演算を繰り返すと、c や d に割り当てなければいけないビット数はどんどん長くなります。
しかし、このようなビットの使い方は本質的に無駄があります。例えば d は {0 < d < 65535}の範囲になりますが、a も b も 255 以下の整数なので、d = 263 (素数)となることは決してありません。実際、エラー訂正における演算は「後で元のデータをちゃんと回復できる」ことが大事なので、正確に + (足し算) や * (かけ算) の計算結果を用いる必要はありません。ちゃんと一次方程式が解ければ、+の代わりに(+')みたいなのを用いてもOKです。

この一次方程式が解ける、という条件ですが、これは演算の一意性に関係しています。
例えば、

1 (+') 2 = 3, 1 (+') 5 = 3, 2 ≠ 5

という世界では、

1 (+') ? = 2

という方程式が一意には解けません。( ? が 2 か 5 か分からない)
つまり、必要なのは

c = a (+') b

のとき、

c = ? (+') b

の?を埋める値がただ一つ、確実に定まる(そしてそれは当然 a に等しい)というものです。これは、(-')という演算が成立して

a = c (-') b

となる、というのと同義です。ここで、a(+')bが{0 <= a,b < 256}に収まるようにできれば、先ほどのように無駄に符号長が長くなる問題を回避できます。
積の場合もほぼ同じですが、少し異なるのは0の存在です。

c = a * b

のとき、

c = ? * b

を満たす?は、(b!=0)のときは一通りですが、b = 0の時は ? はなんでもよくて、むしろ c == 0 が必要になります。
また、適当に (+') や (*') の意味を決めてしまうと、交換則 (a + b = b + a) や結合則((a + b) + c) = (a + (b + c))・分配則( (a + b) * c = a * c + b * c) が成立しなくなってしまうので、普通の一次方程式の解き方が出来なくなってしまいます。このため、最低限この3つの法則は成り立つのが都合が良いです。

どんな演算が欲しいか

少し条件を整理してみます。
普通にエラー訂正を足し算、かけ算で構成しようとすると、計算に必要な桁数がどんどん増えてしまう可能性があり、コンピュータの演算では不都合です。なので、計算しても、桁数が増えない (有限の元で閉じている) 四則演算を定義しよう、というのが動機です。
まず、この演算の元の集合を S とおきます。S の元の数はは有限です。

足し算の存在: 任意の a, b ∈ S に対し、a + b = c となる c ∈ S がただ一つ存在する
引き算 (足し算の逆演算) の一意性: 任意の a, b, c ∈ S に対し、a + b = c なら a - c = b

あと、交換則も成り立つと便利です。

交換則: a + b = b + a

また、

a - a = b

を満たす S には、0 元となる c ∈ S がただ一つ存在する
このとき a + ? = c なら ? == b ここで、a + b = a まとめると、以下の 5 つが成り立ってほしいことが分かります。

0 の存在: a + 0 = a
1 の存在: a + 0 = a
足し算の一意性: a + b = c のとき a + ? = c なら ? == b
足し算の一意性: a + b = c なら

では、このような都合が良い (+') や (*') なんて演算はあるのでしょうか。これを与えてくれるのがガロア体上での演算です。

数学の世界へ (体)

先ほど、a(+')bが{0 <= a,b < 256}に収まってくれればいい、と書きましたが、これは数学の世界では(+')という演算が「閉じている」と表現されます。これは、a, bが属する{0 <= a,b < 256}という集合に対し、a(+')bの結果もこの集合の中に収まっていることを示します。つまり、求める体系は

対象とするのは{0 <= a,b < 256}などの、閉じた整数集合
この集合に閉じた演算(+')、(*')が定義されている
(+')と(*')によって構成された一次方程式が解ける

となります。最後のが少し曖昧ですが、このあたり(演算子に求められる条件)を長々書いてもあまり面白くないので、とりあえず進みます。で、とにかくどんな方法でもいいから、これに相当する(+')と(*')の演算を定義すればいいわけです。
このように集合とその中での演算を考えるのを「代数」と言います。演算は適当に決めれば作れるのですが、「方程式が解ける」みたいな条件を課すにはどんな演算でもいいというわけではありません。数学の世界では、ある特定の性質を満たす集合と演算の組に「環」や「体」などの名前を付けています。ここでは「体」について説明します。
「体」とは、以下の性質を満たす集合Fと演算(+,*)のことをいいます。
まずFの任意の元a,b,cと+についての性質です。

a + b = d のとき、dは必ずFに含まれる
(a + b) + c = a + (b + c)
0(零元)が存在し、0 + a = a + 0 = a　ここで0はFに含まれる
-a(逆元)が存在し、a + (-a) = (-a) + a = 0　ここで(-a)はFに必ず含まれる

これらの性質をまとめて、F, +が加法群であると言います。これに加えて、演算の順番を変えてもいい、という

a + b = b + a

も加えられています。これを加えると「加法可換群」と呼ばれます。

次にFのなかで0を除く任意の元a,b,cと*についての性質です。

a * b = d のとき、dは必ずFに含まれる
(a * b) * c = a * (b * c)
1(単位元)が存在し、1 * a = a * 1 = a　ここで1はFに含まれる
a^-1(逆元)が存在し、a * a^-1 = a^-1 * a = 1　ここでa^-1はFに必ず含まれる

これらの性質をまとめて、F, *が乗法群であると言います。これに加えて、演算の順番を変えてもいい、という

a * b = b * a

も加えられています。これを加えると「乗法可換群」と呼ばれます。

これに、分配法則

(a + b) * c = a * c + b * c

を加えて、「体」の定義が完了です。(意外と長かった…)
このようにかなり厳しい定義なので、演算は普通の+や*と同じようにできます。それに加えてうれしいのは、

a + b = cのとき、cはF(元の集合)に含まれる
a * b = dのとき、dはF(元の集合)に含まれる

という条件です。Fを(0-255)の整数、という集合として定義しておけば、Fの中の元をどのように四則演算しても、その値は0-255の範囲を超えることはありません。しかも、交換法則・結合法則などが確保されているので、一次方程式は普通の四則演算とまったく同じように解けます。あとはこんなうまい演算+や*が見つかるか、という話になるわけですが…
あ、「体」と「ガロア体」の違いですが、体の集合Fが有限集合(元の数が有限)のとき、これを「有限体」とか「ガロア体」と呼びます。符号理論で扱うのは有限長のデータなので、ガロア体上での演算が役立つわけです。

リード・ソロモン符号化

はじめに

エラー訂正 (線形符号) 超入門

普通の四則演算への不満

どんな演算が欲しいか

数学の世界へ (体)

どんな演算なのか