定数レートかつ線形時間復号可能な線形符号を作るお話。流れとしてはLDPCに属するのか? 符号に詳しい人の意見を求む。
背景
GallagerがLDPCを提案 (MIT Press 1963)。ランダムな低次数二部グラフの隣接行列を検査行列とする構成。GV限界に迫るレートと最小距離を持つことを示した。
アイデア
グラフを良い性質をもつExpanderグラフに変更する。
準備
今回は$F_2$上で構成。符号長をn, 符号レートをr, 最小相対距離をα, 訂正可能な誤り率をεで書くことにする。
計算モデルとしてはRAMと回路を採用する。事前計算も行うこととする。なので符号毎にアルゴリズムや回路を構成する。
Expanderグラフと構成で利用するグラフ
G = (V,E)をn頂点グラフとする。
任意のm以下の要素数の集合$S \subset V$について
のとき, 任意の高々m頂点の集合が割合δで拡張する (expands) という。
見ての通り頂点集合Sから見て行き先がδ|S|より多いということ。
構成には二部グラフかつexpanderなものを利用する。二部グラフの頂点集合をL,Rとする。辺は(x,y) in L×Rである。
グラフが(c,d)正則であるとは, 左側Lに含まれる頂点の次数はc, 右側Rに含まれる頂点の次数がdであることである。c|L| = d|R|⇔ c/d = |R|/|L| に注意。
グラフが(c,d,ε,δ')-expanderであるとは、1. (c,d)正則グラフかつ 2. L側の任意の高々ε|L|以下の頂点集合がδ以上の割合で拡張 しているときを言う.
Prop.1 Bを|L|=n, |R|=(c/d)nなランダムな(c,d)正則な二部グラフとする. このとき, 任意のα in (0,1)について, 高い確率で
「L中の任意のαn要素の頂点集合の隣接要素の個数は
以上」である。
」
最終更新：2011年03月06日 13:54
