リード・ソロモン符号

の骨格を教えてちょ！

No.2 ベストアンサー 回答者： ありものがたり 回答日時： 2025/02/26 22:02

リード・ソロモン符号の基本骨格は、線型符号化です。

コンピュータの中のデータは全て数値で表されていますから、
データを順次送り出す通信は、数列だと解釈できます。
その数列を、固定長の短い列の並びへ区切ると、
ベクトルの列だとみなすことができます。

ベクトルの列を通信路へ送り出すに先立ち、
各ベクトルを一次変換によって、より高次元のベクトル空間の中へ
写像しておくと、変換の値域は終域であるベクトル空間の
真部分空間となり、受信するデータの中に
現れ得るベクトルと現れ得ないベクトルが区別できるようになります。
この違いを用いて、通信にエラーがあったかどうかを検査するのが、
線型符号化による誤り検出符号です。
誤り検出ができるかできないかは、使った一次変換の性質によります。

更に上手に一次変換を選んでおくと、異なるデータを送信したときに
それぞれにエラーを加えた受信ベクトルが同じにならないように
設計することもできます。これを用いて、エラーを含む受信データを
もとのデータに復元するのが、線型符号化による誤り訂正符号です。

線型符号化には、使う一次変換によって種々のものがあり、
リード・ソロモン符号より素朴なハミング符号なんかも有名ですね。

リード・ソロモン符号の場合は、データを m×k ビットづつに区切って
有限体 F = GF(2^m) をスカラーとするベクトル空間 F^k の元と見て、
一次変換によって F^n (ただし n > k) の元へ移します。
その際、変換後のベクトルの n 個の成分のうち
k 個は変換前の F^k のベクトルの成分がそのまま現れるようにしておきます。
その k 個の成分を通信データの情報部分,
残り n-k 個の成分を通信データの検査部分と呼び、
一次変換の係数行列をこの符号化の生成行列と呼びます。

リード・ソロモン符号の具体的な生成行列については、
ネット検索でもして読んでみてください。
多くのサイトでは、いきなりガロア群とか多項式とか出てきて
何を説明しているのか判りづらい感じになっていますが、
上記の枠組みを踏まえて具体的な行列を示す説明をしているのだ
と思えば、話の筋が掴みやすいのではないかと思います。

この回答へのお礼

ありがとう・・・


＞ベクトルを一次変換によって、より高次元のベクトル空間の中へ
写像しておくと、変換の値域は終域であるベクトル空間の
真部分空間となり、受信するデータの中に
現れ得るベクトルと現れ得ないベクトルが区別できるようになります。
この違いを用いて、通信にエラーがあったかどうかを検査するのが、
線型符号化による誤り検出符号です。
ーー＞
符号空間と非符号空間の分離・・・

ガロア体ですね・・・

訂正メカニズムはさらに難しそうですね！

お礼日時：2025/02/26 22:51

No.3 回答者： ありものがたり 回答日時： 2025/02/27 02:25

デジタルデータは 0 または 1 が並んだものなわけだけれど、

この列をまず mk 個づつに区切り、更にその中を m 個づつに区切る。
そうすると、データは m 桁の 2 進数を成分に持つ k 次元ベクトルの列
と見ることができます。

2 進数の k 個組をベクトルと見るためには、
m 桁の 2 進数の加減乗除が体でないといけません。
パソコンのプログラミングで通常「整数演算」と呼ばれるものは、
レジスタの幅を r ビットとして剰余環 Z/(2^r)Z での計算です。
この環では除算を行うことができず、体にはなっていません。

その代わりにスカラーとして使えるのが、有限体 GF(2^m) です。
有限体 GF(q) は、q が素数または素数の自然数乗のときに存在し、
q = p^m のときには、GF(p) の元を係数に持つ多項式の環 GF(p)[X] と
この環上で既約な m 次多項式 f(X) によって
剰余環 GF(p)[X] / f(X)GF(p)[X] として構成できるのでした。

ここで、有限体(ガロア体)だの多項式だのが登場するんですね。

この回答へのお礼

符号の体化ですね！
演算可能化・・・

お礼日時：2025/02/27 03:00

No.1 回答者： Tacosan 回答日時： 2025/02/25 01:32

https://ja.wikipedia.org/wiki/%E3%83%AA%E3%83%BC …

この回答へのお礼

うひょひょ・・・

お礼日時：2025/02/25 01:58