線型符号

線型符号の概要

線型符号とは、誤りの検出や訂正に用いられるブロック符号の一形態です。この符号は、特に通信路における情報の送受信時に発生しうる誤りを管理するために設計されています。線型符号の主な特徴は、符号化と復号の処理が効率的に行える点です。

線型符号の定義

線型符号は、特定の有限体を基にした n 次元線型空間の部分空間で定義されます。ここで、有限体は q 個の元からなり、これに基づいて k 次元の部分空間 C を定義します。このとき、C の次元 k は、

$$ ext{dim}_F C = k$$

と表され、これが線型符号 C を (n, k) 線型符号とみなす基準となります。基底を使って行列 G を構築し、これを線型符号の生成行列と呼びます。この G 行列を用いて、

$$C = egin{pmatrix} xG \ x ext{は } F^k ext{の元} \\ \\ $$

が成り立ちます。さらに、C が持つパリティ検査行列 H を用いることで、

$$C = egin{pmatrix} y ext{は } F^n ext{の元} \ y H^t = 0 \\ \\ $$

という形でも定義することが可能です。ここで、n-k 次元の行列 H は C の誤りを検出する役割を果たします。

符号化と復号の過程

線型符号の符号化は、生成行列 G を使って行われます。具体的には、情報系列を G 行列に掛け算することで符号語を生成します。たとえば、情報系列 x を (0, 1, 0, 1) とした場合、符号化を経ることで得られる符号語は以下のように計算されます。

$$xG = (0, 1, 0, 1, 0, 1, 0)$$

出力された符号語の末尾部分には、パリティ検査記号が含まれます。

一方、受信側ではこれらの符号語が誤りを伴って受信されることがあります。このため、受信語 y のシンドロームを計算し、コセット・リーダを見つけ出すことで復号処理が行われます。受信語 y が誤りを含む場合、シンドロームは以下のようになります。

$$y H^t$$

シンドロームとコセット・リーダに基づき、符号語が再構築されて元の情報系列に復号されます。

例と特性

具体的な例として、(7, 4) 線型符号を挙げることができます。この場合、生成行列 G とパリティ検査行列 H は次のように定義されます。

$$G = egin{pmatrix} 1 & 0 & 0 & 0 & 0 & 1 & 1 \ 0 & 1 & 0 & 0 & 1 & 0 & 1 \ 0 & 0 & 1 & 0 & 1 & 1 & 0 \ 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ \\ $$

$$H = egin{pmatrix} 0 & 1 & 1 & 1 & 1 & 0 & 0 \ 1 & 0 & 1 & 1 & 0 & 1 & 0 \ 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ \\ $$

情報系列 x を (0, 1, 0, 1) とはし、これを G にかけることで得られた符号語には最初の部分に情報が含まれています。もし通信中に誤りが発生し、受信語が変わった場合でも、シンドローム復号によって元の情報を復元することが可能です。

このように、線型符号は効率的に情報を伝送し、同時に誤りを修正する能力も兼備しています。たとえば、誤り訂正符号の一つであるリチャード・ハミング符号は、1947年に提唱され、その後も多くの通信技術に革命をもたらしました。

線型符号の応用

現在、線型符号は様々な電子機器やデータストレージにおいて広範に利用されています。特に、コンパクトディスクにデジタルデータを格納する際に使用されるリード・ソロモン符号は、その良い例です。また、ISBN番号の計算は、11元体上の一次方程式を使って、線型符号の一形態として表現されます。

まとめ

このように、線型符号は誤り検出・訂正のための強力なツールであり、通信やデータ保存の分野において不可欠な技術といえます。

もう一度検索