アイテックでは、月に1回メルマガを配信しています。
ちょっと強面、でも心優しいユニークキャラの技術者たちが提供するその名も、「マル得！無線通信」
開発の現場でおこるあれこれや、アイテック技術陣の日々の奮闘ぶりなどアイテックのエンジニアによるコラムをお届けします。

2007/09/14

リードソロモンの符号生成

今回担当します高沢です。

今回は地上波ディジタル放送、衛星通信、ADSLやDVTR、
身近なところではCDやDVDの誤り訂正に使われている
『リードソロモン』のエラー訂正の実装方法［その１］を説明します。
数式は使わずに実データを例に説明していきます。

実装する訂正の諸元は

　　訂正種類　　：リードソロモン（４０，３２）
　　ガロア拡大体：ＧＦ（２＾８）　※２＾８は２の８乗を表しています。

　　　　　　　　※４０シンボルを通信符号
　　　　　　　　　３２シンボルを情報符号
　　　　　　　　　　８シンボルを検査符号　と定義します。

この諸元から３２シンボルの情報符号に８シンボルの検査符号を
付加しますので４シンボルの訂正が可能ということが読み取れます。
一般的に訂正する場合には、実情報符号に検査符号を付加しますので
無線区間のビットレートは下がります。
どの程度低下するかは検査符号をどの程度冗長させるかで変わってきます。
今回の諸元では４０シンボルで８シンボルが検査符号となるので無線区間
ビットレートは20％遅くなります。

それでは符号の生成を始めましょう。

◆１．生成多項式G(x)を求めます

　生成多項式G(x)は次式で表します。

G(x)=(x+1)(x+α)(x+α^2)...(x+α^2t-1) t:最大訂正可能シンボル数

今回の最大訂正可能シンボル数は４シンボルなので
　G(x)=(x+1)(x+α)(x+α^2)(x+α^3)(x+α^4)(x+α^5)(x+α^6)(x+α^7)
=x^8+α^175x^7+α^238x^6+α^208x^5+α^249x^4+α^215x^3+
　　　　α^252x^2+α^196x+α^28　　→(式1)
　
計算過程は省略します。ガロア体の演算を理解する上でもご自分で
計算してみて下さい。
理解度が違ってきます。
ガロア体の演算についてはインターネット上に多数解説がありますので
ここでは省略します。

◆２．検査符号を求めます

　情報符号を生成多項式G(x)で割った余りが検査符号になります。
　例えば{FE,02,03,78,05,06,07,08,
11,12,13,14,25,26,27,28,
31,32,33,34,45,46,47,48,
5A,6B,7C,8D,9E,AF,55,B1} というＨＥＸデータを送信したい場合、

　検査符号
=情報符号÷生成多項式G(x)
={α^88x^39 ,α^1x^38 ,α^25x^37 ,α^78x^36 ,α^50x^35 ,
　　α^26x^34,α^198x^33,α^3x^32 ,α^100x^31,α^224x^30,
　　α^14x^29 ,α^52x^28 ,α^36x^27 ,α^15x^26,α^33x^25 ,
　　α^53x^24 ,α^181x^23,α^194x^22,α^125x^21,α^106x^20,
　　α^221x^19,α^48x^18,α^253x^17,α^226x^16,α^19x^15 ,
　　α^84x^14 ,α^115x^13,α^197x^12,α^137x^11,α^97x^10,
　　α^150x^9 ,α^86x^8 ,0 ,0 ,0 ,
　　0 ,0 ,0 ,0 ,0 }　→(式2)
÷
{x^8+α^175x^7+α^238x^6+α^208x^5+α^249x^4+α^215x^3+
　　α^252x^2+α^196x+α^28}
={α^247x^7,α^55x^6,α^38x^5,α^67x^4,α^33x^3,α^27x^2,
　　α^146x,α^19}　→(式3)

検査符号も自分で計算してみてください。
ここで検査符号が求まればガロア体の計算は完璧です。

◆３．通信符号F(x)の生成

(式3)を(式2)に代入します

通信符号F(x)
={α^88x^39 ,α^1x^38 ,α^25x^37 ,α^78x^36 ,α^50x^35 ,
　　α^26x^34,α^198x^33,α^3x^32 ,α^100x^31,α^224x^30,
　　α^14x^29 ,α^52x^28 ,α^36x^27 ,α^15x^26,α^33x^25 ,
　　α^53x^24 ,α^181x^23,α^194x^22,α^125x^21,α^106x^20,
　　α^221x^19,α^48x^18,α^253x^17,α^226x^16,α^19x^15 ,
　　α^84x^14 ,α^115x^13,α^197x^12,α^137x^11,α^97x^10,
　　α^150x^9 ,α^86x^8 ,α^247x^7 ,α^55x^6 ,α^38x^5 ,
　　α^67x^4 ,α^33x^3 ,α^27x^2 ,α^146x ,α^19 }　→(式4)

これで送信側の通信符号F(x)が生成されました。
受信側はこの通信符号F(x)からシンドロームの計算、誤り位置の計算、
誤り訂正係数の計算と進んで訂正が完了します。

今回はリードソロモンの符号生成で終了します。
次回からは受信側の復号方法を説明予定です。

それでは今回はこの辺で。

●○●　ナビゲーター　高沢弘光のプロフィールはこちら　●○●

某通信機メーカーにて開発設計に10数年携わる。
2006年11月アイテックに入社。ソフトウェアを担当。
趣味は洋風茶道（ドリップコーヒー）。
夢はポルシェでアウトバーンを駆け抜けること。
-------------------------------------------------------------------
→今回の解説はフォント設定などによって式の書式が崩れて見える
場合がございます。恐れ入りますが、予めご了承ください。

┏━━━━━━━━━━━━━━━━━━━━━━┓
　　　　　　今月の用語解説
┗━━━━━━━━━━━━━━━━━━━━━━┛

【水晶発振器】
水晶発振子を共振器にして、発振させる周波数安定度の高い発振器である。
水晶の結晶軸からの切り出し角度に依存し温度特性が変化する。
カットアングルとして、DTカット、XYカット、ATカット等がある。

• 前の記事は : 「フィルターについて」
• 次の記事は : 「電源について」」
• 最新の記事は : 「6月は電波と環境保護の月です」