コンテンツにスキップ

リード・マラー符号

出典: フリー百科事典『ウィキペディア(Wikipedia)』

リード・マラー符号(リード・マラーふごう、: Reed–Muller code)は、通信で使われる線型誤り訂正符号の1つの種類である。発見者は Irving S. Reed と D. E. Muller である。リード・マラー符号は、R(r, m) で表され、r は符号の次数、m は符号語の長さ n = 2m である。リード・マラー符号は、元が {0, 1} である有限体 GF(2m) におけるバイナリ関数に関連する。

符号 R(0, m) は反復符号[1]、符号 R(1, m) はアダマール符号、符号 R(m − 1, m) はパリティチェック符号である。リード・マラー符号は直交性があるために興味深い特性を持ち、ブール関数空間と見なせる。

構成

[編集]

長さ n = 2m のリード・マラー符号は以下のように構成される。

まず とおく。このとき、部分集合 に対して、指示ベクトル を次で定義する。

また における次の二項演算を「楔積; wedge product」と呼ぶ。

は、 上の m 次元ベクトル空間ゆえ、次のように記述できる。

このとき、n-次元空間 において次のベクトルを定義する。

ここで、Hiにおける超平面 である。リード・マラー 符号 R(r, m) とは、長さ n = 2m、 次数 0 ≤ rm であり、

によって生成される符号のことである。

[編集]

m = 3 とする。すると n = 8 であり、次のようになる。

そして、上の構成と同様に、次のようにおく。

R(1, 3)

[編集]

r = 1 とすると、符号 R(1, 3) は次の集合から生成される。

あるいは、次の行列を生成行列とする符号である。

R(2, 3)

[編集]

r = 2 とすると、符号 R(2, 3) は次の集合から生成される。

あるいは、次の行列を生成行列とする符号である。

特性

[編集]

リード・マラー符号 R (r, m) は次の特性をもつ。

  • m 番目までの vi がとりうる全ての楔積の集合は、 の基底である。
  • ランクは次の通り[2]
  • R (r, m) = R (r, m − 1) | R (r − 1, m − 1) ここで、'|' は2つの符号の bar product を表している。
  • 最小距離は 2mr である[3]

脚注

[編集]

参考文献

[編集]
  • Roman, Steven (1992). Coding and Information Theory. Graduate Texts in Mathematics. 134. Springer-Verlag. ISBN 0-387-97812-7. MR1168212. Zbl 0752.94001. https://books.google.co.jp/books?id=v7EwMbbTvr4C 
  • van Lint, J. H. (1999). Introduction to Coding Theory. Graduate Texts in Mathematics. 86 (Third ed.). Springer-Verlag. ISBN 3-540-64133-5. MR1664228. Zbl 0936.94014. https://books.google.co.jp/books?id=tvQhRUFh7EwC 

関連項目

[編集]