代数方程式とデジタル信号処理

方程式の使い道

中学校や高校で、1次方程式や2次方程式を学びます。場合によっては3次方程式や4次方程式も出てきます。これらの単元では、方程式を立ててその解を求めることがほとんどです。1次方程式では、式変形で、また2次方程式では因数分解や解の公式で全ての解を求めることができます。\(ax^2+bx+ｃ＝0　(a≠0\)　の解は　\(ｘ＝(－ｂ±\sqrt{b^2－4ac})/2a\)　ですね。高校ではここまでですが、大学では、3次、4次方程式の解の公式、5次以降の方程式が演算で解けるための条件である、いわゆるガロワ理論を学びます。ガロワはフランスの天才数学者で群論の創始者で20才でこの理論を確立しています。ここではこれらの方程式の解を使うような応用例について書いてみましょう。ガロワについては、次のリンクを参照してください。　ガロワ

デジタル信号のエラー訂正コード

かつてはaudioやvideo信号は、アナログ信号でしたが、今ではほとんどデジタル信号に代わっています。音楽も映画もデジタルで処理されています。デジタル信号は2進法の世界です。ここでは、音楽信号について考えてみましょう。例えば、CDでは、音のデータを、サンプリング周波数　\(44.4kHz\)　量子化ビット　\(16bit\)　で量子化されます。そしてすべてのデータは、\(0か1\)　で置き換えられます。音の情報は、様々な周波数と振幅の正弦波の合成波で表されます。これを、\(44.4kHz\)　\(16bit\)　で　\(0,1\)　データに変換します。データは電子回路の中で転送され最後には音データとしてスピーカーやイヤホンに出力されています。この時のデジタルデータの転送には、必ず誤り（エラー）が発生するのです。通常何もしなければ、\(10^{-5}\)　程度のエラーが発生します。これは少ないようですが、CDでは1秒あたり　\(44.4kHzｘ２チャンネルｘ16bit＝1.41Mbit\)　のデータが処理されるので、1秒間に　\(14~15回/秒\)　のbit誤りが発生してしまいます。そこで、エラー訂正が必須になり、ここにガロワ理論（ガロワ拡大体）が使われているのです。

エラー訂正におけるガロワ拡大体

エラー訂正の基本は、データセットにパリティを付加することです。簡単な例をあげてみましょう。今入力データが、\(I=(1023)\)　だとしましょう。この出力データが、\(O=(1023)\)　であれば問題ありませんが、これが　\(O’＝(1*23)\)　になったとすると訂正しようがありません。ここで、\(*\)　はデータが消失してしまったデータを表します。そこで、パリティを付加します。入力データの最後に3つのデータの足し算したデータを付加します。つまり　\(IP=(10236)\)　とすると、もし出力データが　\(OP=(1*236)\)　と2番目のデータが消失しても、パリティから　2番目のデータは　\(0\)　と復元できます。これがエラー訂正の基本原理です。これを方程式の解を使って構成するのです。

光ディスクやデジタルデータのポピュラーな符号はリード・ソロモン符号です。リードソロモン符号は、ガロワ体上で構成されます。ガロワ体は、加減乗除の四則演算ができる有限なものをいいます。デジタルデータでは、\(0,1\)　のみの2進演算もガロワ体です。CD、DVD,BD　等では、\(8bit\)　単位でデータを扱いますから、\(GF(2^8)\)　を使います。つまり　\(256\)通りのデータセットを考えます。\(8\)　ビット単位では少し複雑になりますから、ここでは\(2\)　ビットで考えてみましょう。データは　\(2^2＝4\)　通りあります。\((0、1、2、3)\)　では　\(2や3\)の逆元を作ることはできません。そこで規約方程式　\(x^2+x+1=0\)　の解　\(α\)　を付加してガロワ体を拡大するのです。つまり、\(GF(2^2)＝(0、1、α、α^2)\)　とします。ここで　\(α\)　は　\(1\)　の3乗根　の　\(ω＝(－1±\sqrt{3})i/2\)　です。このようなガロワ体をガロワ拡大体といいます。\(GF(２^2)\)　がガロワ体であることを確かめてみてください。

これから、パリティーの生成を行います。記録データを　\(\boldsymbol{V}\)　とします。これは、\(n\)　行　\(1\)　列の列ベクトルです。
データは、
\((0000)＝0\)
\((0001)＝1\)
\(0010)＝α\)
\((0011)＝α^2\)
の組み合わせで　\(α\)　の多項式で表します。パリティは、各データを生成方程式である　\(G(x)＝x^2+x+1\)　で割った余りを付加します。また、パリティ検査行列　\(\boldsymbol{H}\)　を次で定義します。

\(\begin{eqnarray} H = \left(
\begin{array}{cccc} 1 & 1 & \ldots & 1 \\
α^{n-1} & α^{n-2} & \ldots & 1\\
α^{2(n-1)} & α^{2(n-2)} & \ldots & 1\\
\vdots & \vdots & \ddots & \vdots \\
(α^3)^{n-1} & (α^3)^{n-2} & \ldots & 1
\end{array}
\right)
\end{eqnarray}\)

ここで、現データを　\(V=\left( \begin{array}{c} V_0 \\ V_1 \\ \vdots \\ a_{n-1} \end{array} \right)\)　再生データを　\(V’=\left( \begin{array}{c} V’_0 \\ V’_1 \\ \vdots \\ V’_{n-1} \end{array} \right)\)

とし、さらに　シンドローム　\(S\)　を　\(S=H・V’\)　で定義します。

つまり、\(S＝\left( \begin{array}{c} S_1 \\ S_2 \\ S_3\\ S_4 \end{array} \right)\)　となりますが、\(S_k＝\displaystyle \sum_{ k = 1 }^{ 4} α_k・V’_k\)　です。

従って、\(E\)　を途中で混入したデータ誤りとすると、\(V’=V+E\)　ですから
\(S=H・V’＝H･(V+E)＝H・E\)　となり、例えば誤りシンボルが2シンボルとすると、上の連立方程式を解けば、誤り位置の　\(i,j\)　がわかり、さらには誤りデータがわかるという仕組みです。

これが、簡単なデジタルデータの誤り訂正の手順になります。これらのエラー訂正符号は、デジタルデータ転送における誤り訂正に使われ、ハードディスクや光ディスクなどに使われています。