通信路符号化の歴史と展望
スポンサーリンク
概要
- 論文の詳細を見る
1948年, C.E.Shannonは後に情報理論と呼ばれる理論体系を独りで構築した[Sha48]. その中で, 通信路符号化は情報源符号化と並んで情報理論の双壁をなしている. Shannonによる通信路符号化定理 [Sha48] は, その後 A.Feinstein[Fei54], R.M.Fano[fan61], R.G.Gallager[Gal65], A.J.Viterbi[Vit67], S.Arimoto[Ari73]らにより精密化され定量化されたが現在でも尚, 最も重要な結論であることには変わりない. しかも1967年のShannonら[SGB67]の論文以降本質的には何も変わっていない. さて, 通信路符号化は雑音のある通信路において, 符号化により高信頼化を図る問題を取り扱う. そして正の情報伝送速度 R で符号長 N を大とすることにより, 復号誤り確率 P(ε) を指数的に 0 に収束できる符号化が存在するという工学的に極めて重要な結論が導かれている. この P(ε) の 0 への収斂速度を与える信頼度関数に関する研究は, この分野の中心的話題である. 現在でも低情報伝送速度では信頼度関数の上界と下界との間に差があり, 真にきつい限界式は求まっていない. これは情報理論の最も基本的問題であるが, 未だ解決されていない. 漸近的距離比δ(R) がGilbert下界式[Gil52]を等式で満たすという Shannon ら[SGB67]の推測によれば, 削除誤り指数E_<ex>(R)が真の信頼度関数を与えるが, この推測に反例はないが証明もされていない. 1980年代, I.Csiszar と J.Korner[CK81], R.E.Blahut [Bla87]らにより情報理論の再構築が図られ, 通信路符号化に対し新しい視点や新しい解釈が与えられた. しかし上の未解決問題は依然として残されたままである. 一方, 代数学を背景にもつ符号理論は数多くの実用的な誤り訂正符号を与えてきた. 通信路符号化のもう一つの重要な問題は, ランダム符号化により証明された通信路符号化定理を非ランダムな構成的符号化により証明することである. 連接符号を用いた試み[DP82][Tho87]があるが, その信頼度関数の下界は連接符号化誤り指数[For66]には及ばない. 最近, 植松らにより連接符号化誤り指数に一致する代数的符号構成法が示されたことは注目に値する[UMN94]. なお, 通信路符号化定理で存在することが保証された最良符号を求めることも困難とされている[Bla87]. 以下では, 離散的無記憶通信路を仮定し, ブロック符号についてのみとり上げる. たたみ込み符号や連接符号の詳しい議論については, 筆者らの論文[AH90]を参照されたい.
- 1997-03-06
論文 | ランダム
- The Impact of the Palm Oil Industry on the Factors of Production and Households in Indonesia
- Diotima und Frau Susette Gontard
- グリム・メルヘンに登場する4人の 「魔女」 たち : 魔女・魔法使いの女・賢女・老婆
- 日常生活史-E女の場合「1900年から1933年までのブラウンシュヴァイクにおける労働者の日常生活」(その五)(原田 稔名誉教授記念号)
- Onarigami. Die heilige Frau in Okinawa. By Monika Wacker