"コミュニケーションとコンピュテーション" 稲垣康善 著

本書は、情報通信と計算技術を支える理論についての教科書である。教科書であるからには、今更感は否めない。

しかしながら、初心に返る意味でも、教科書的な存在は意外と大きい。なにやら忘れかけたものを思い出させてくれるような...

コンピュータ工学における情報と計算は、物理学における物質やエネルギーと同様、基礎概念として君臨している。

それぞれの歴史を紐解けば、クロード・シャノンは情報の内容を問わず、ひたすら情報の量に着目して数学的理論を打ち出した。

アラン・チューリングは計算可能性を追求した抽象的な計算機理論、いわゆる、チューリングマシンを提唱した。

ここでは、通信路モデルと計算機モデルの融合という観点から、コンピュータ工学を物語ってくれる。

「コミュニケーション(通信)とコンピュテーション(計算)は、情報の学問と技術の核心である。」

1. 通信路モデル

まず、あの有名な式を押さえておこう。

  H(X) = -ΣP(x) log P(x)

そう、情報理論のエントロピーだ。この用語は捉えどころが難しく、通信理論においてもカオスのまま。

そして、シャノンの第一基本定理と呼ばれる「情報源符号化定理」と、これに雑音特性を付加したシャノンの第二基本原理と呼ばれる「通信路符号化定理」を経て、より現実な世界へと導かれる。

そこで、根幹となる技術が誤り検出と誤り訂正符号である。今日のデジタルシステムを根幹から支えているのは、この技術と言ってもいいだろう。完璧な誤り訂正システムは存在しない。情報効率を高めようとすれば、尚更。そして、確率論に持ち込まれる。通信媒体や記憶媒体によっては、用いる符号も違う。

ちなみに、本書では扱われないが、リードソロモン符号などはデジタルシステムでよく用いられ、符号化と復号化が複雑な分、訂正能力が高く、バイト単位で処理できるのも記憶媒体と相性がいい。

そして、生成多項式とにらめっこする羽目に... というのが、おいらの仕事の定番である。

2. 計算機モデル

まず、有限オートマトンを押さえておこう。論理で構成できれば、言語化や記号化ができる。プログラミングとは、まさに言語化、記号化の世界。

それは、データを記憶領域内でどのように表現し、どのような手順で処理するかを記述すること。そう、アルゴリズムってやつだ。プログラミングでは、このアルゴリズムの設計が基本となる。そして、論理システムは、有限集合のステートマシンで記述できる。

計算可能性では、状態遷移関数が帰納的関数であるかどうかが鍵となる。これこそが、「チャーチ(=チューリング)の定立」ってやつだ。

さて、万能マシンは可能であろうか。それは、多項式時間で計算可能か、そんなアルゴリズムが存在するか、という問題と絡み、さらに停止性問題と絡む。ゴルディアスの結び目のごとく...

「構造ないしは構造物の複雑さを計る尺度がないことは、情報科学とコンピュータ科学の理論的支柱の間の最も基本的なギャップであると考えている。」

... F. P. ブルックス