情報理論

戻る

概要解説

シャノンの解説

情報理論の創始者であるシャノン（Claude Elwood Shannon, C.E. Shannonと略）は、1916年（大正5年）4月30日に米国ミシガン州のPetoskeyで生まれた。2001年(平成13年）2月24日に84歳で没した。

幼少時および高校生頃まではミシガン州のGaylordで過ごした。1932年にそこの高校Gaylord High School を卒業し、ミシガン大学に入学した。大学ではブール代数の道に入る専門コースを学んだ。1936年に大学を卒業し、電気工学および数学の学士号をとった。その後、マサチューセッツ工科大学（Massachusetts Institute of Technology, MIT)の大学院に入学した。そこで、ブッシュの微分解析機やアナログ計算機に関する研究を行った。

連載：インターネット・サイエンスの歴史人物館（2）クロード・シャノン　も参考になる。

シャノンの情報理論創始の論文

情報理論の創始となった記念碑的な論文である。掲載されたのは、1948年7月、Bell System Technical Journal (略称B.S.T.J.)である。この雑誌は、米国の電話会社AT&Tの研究部門であるベル研究所（通称ベル研）の社内論文誌である。あまり大部であることからか、２回に分けて掲載された。
1948年7月号、B.S.T.J., vol.27, pp.379-423、Part I Discrete Noiseless Systems, Part II The Discrete Channel with Noise

1948年10月号、B.S.T.J., vol.27, pp.623-656、Part III Mathematical Preliminaries, Part IV The Continuous Channel, Part V The Rate for a Continuous Source

この論文は日本語訳が、『コミュニケーションの数学的理論』（C.E.シャノン, W.ウィーヴァー著 ; 長谷川淳, 井上光洋訳、明治図書出版、1969年）として刊行されている。さらに、同書はすでに入手困難となったため、新訳が復刊書籍『通信の数学的理論』（クロード・シャノン、ワレン・ウィーバー／植松友彦訳、筑摩書房、2009年、ISBN: 9784480092229）として文庫判で出版された。

シャノンのその他の論文

情報理論の解説(Wikipedia)

情報理論の教科書・参考書

情報理論の歴史

情報理論は、その創始者がシャノンであることが広く知られており、歴史的な発展過程が明確である。即ち、シャノンが米国AT&Tのベル研究所時代に発表した論文「A mathematical Theory of Communication」が、情報理論の出発点とされている。このときはまだ情報理論という言葉がなく、通信を数学的に扱う理論という名前で発表された。
この論文の解説は別途行うが、その後多くの研究者によりシャノンの提起した理論が詳細化、厳密化、拡大されて、多くの関連領域を派生させることになった。

情報理論に貢献した人々

情報量

情報量 (Measure of information)

情報という抽象的概念を物理量として扱うために、その大きさ（或いは、多い少ない）の概念を定義したもので、シャノンによって導入された。情報はそれを発生させる元（これを「情報源」という）の種類により、離散的情報（デジタル情報）と連続的情報（アナログ情報）とに分類される。

• （離散的情報の例）数値や文字で表される情報。
• （連続的情報の例）電圧や音圧など連続的に変化する値で表わされる音声、映像。

情報量は、これらの情報が確率的に起きる物理的な量として捉えた概念であり、
『ある事象aが生起確率p(a)で起きる場合の情報量I（ａ）は、I（ａ)=log (1/p(a))=- log p(a)』
と定義される。

自己情報量(Self information)

自己情報量とは上記の情報量のこと。自己というのはある事象（a）に着目しての、という意味で、後に定義される相互情報量と対比させるために明記するものである。

平均情報量 (Expected value of self information)

事象が１つだけでなく複数の事象を発生させる情報源で、事象が完全事象系をなす場合を考える。
完全事象系とは、それぞれの事象のいずれかが必ず起き、かつ異なる事象が同時に起きることはない系である。このような系で、各事象のもつ情報量、I(a)、は上記で定義される値、- log p(a)、であるが、これを全事象について平均したものを平均情報量（平均自己情報量）と呼ぶ。

エントロピー (Entropy)

もともと、物理学の分野で物質の属性を表す量で、物質の乱雑さの度合いを示す量。熱力学あるいは統計力学における気体分子の無秩序さを示す量が、−�捻i log Pi,の形であらわせることが知られていたが、情報理論における平均情報量の定義も同様な形となり、意味的にも同類の性質をあらわすことが分かり、エントロピーと呼ばれることとなった。

相互情報量 (Mutual information)

「自己情報量」はある１つの事象系について定義される量であるが、２つ（以上）の事象系について、両者の緊密度あるいは共通度を計る量として定義されるものが「相互情報量」。典型的な例として、入力事象系Aと出力事象系Bとが通信路を介して情報を送受信する場合を考える。Aの平均情報量（エントロピー）＝H(A)は、出力Ｂを観測しない状況で入力Aがもつ曖昧さを表す。出力Bを観測した時に入力Aが持っている曖昧さは「条件付情報量H(Ａ｜Ｂ)」で表される。これらの差、H(A)-H(A｜B）＝I（A；B）、を「相互情報量」と呼ぶ。もし、AとBが全く独立のときは、Bを観測してもAの曖昧さは減少しないので、H(A｜B）＝H（A）、従ってI（A；B）＝0となる。

条件付情報量(Conditional entropy)

２つ（以上）の事象系において、一方の事象に関する結果を知ったときに、他方の事象系のもつ情報量を表す量として、条件付情報量が定義される。上記の入力事象系Aと出力事象系Bとが通信路を介して情報を送受信する場合は、Bを観測するとAに関する情報（＝不確かさでもある）は減少する課も知れないし、替わらないかもしれない、あるいは増大するかもしれない。これらは、H（A｜B）＝−�這廃 (ai, bj) log p (ai|bj),により与えられる量であり、条件付エントロピーとも呼ぶ。

完全事象系

互いに排反なn個の事象が発生する事象の集合＝標本空間S={E₁，E₂，E₃，…，E_n}があり、各事象の生起確率をP(E₁)，P(E₂)，P(E₃)，…，P(E_n)とする。このとき、次の関係：
　　　Σ P(E_i)=1
　　　∪_k=1...n (E_k)=S
　　　Ei ∩Ej=φ
が成り立つ場合，Sを完全事象系といい、一般に次のような行列表現で表わす。
E=　E₁　　　E₂　　　E₃　　　…　　E_n
　P(E₁)　P(E₂)　P(E₃)　…　　P(E_n）

完全事象系は、

確率論

数学の一分野で、非決定論的な過程を研究するもの。情報理論の基礎理論のひとつ。

情報理論と確率論の関係

情報理論は確率論（と統計論）を基礎に置いている。シャノンが情報理論の最初の論文（通信の数学的理論）を発表したとき、情報を発生する源（ソース）を確率的事象系としてとらえ、事象が生起する確率をもとに情報量を定義した。この考え方は、直感的解釈とよく合致するとともに理論的取り扱いもうまくいき、情報理論を発展させる原因となった。

確率変数

確率的な試行において、試行結果に対応して変わる値を変数として定義したもの。例えば、コイン投げの試行において、表が出る場合と裏が出る場合がある。これらを表すのに、確立変数Xを、X(表）＝０、X（裏）＝１のように定義する。

確率分布

確率変数（ｘ）とそれに対応する確率P(x)との対応関係。例えば、さいころを６回投げるとき、E=「１の目が出る」確率P(E)は1/6となる。ｘ＝「Eが発生する回数」とすると、ｘ＝０，１，２，３，４，５，６の７とおりの値をとる確率変数で、その確率値P(x=i)は二項分布をなす。

確率密度、確率密度関数

確率変数Xが連続確率変数のとき、特定された点xでの確率、P｛X=x｝ を与えることができない。そこで、xの周囲を含めて、区間において、確率変数Xの与える値を考えることにすると、その確率は、 で表される。この値を区間の幅、2で割った値は、区間における、Xの起きる確率に対する平均値を与えるであろう。すなわちこの値は次式で表される。

ここで、をどんどん小さくし、極限値として点xにおける確率変数Xの値が得られものを、確率密度と定義する。

条件付確率

２つの事象（AとB）があるとき，事象Bが起きるという条件のもとで，事象Aが起きる確率を条件付き確率といい，P（A|B）という記号で表す．もしBとAが互いに無関係（独立）ならば，Bが起きるという条件はAが起きることに影響を与えないので，P(A|B)＝P(A)となる．

確率過程

確率的な事象が時間的に起きる場合，すなわち確率変数が時間とともに変化する（時間に依存する）ものを確率過程という．

マルコフ過程（連鎖）

確率過程において，次（更に引き継き未来）に起きる事象の確率が，現在の状態にのみ依存して決まるものをマルコフ過程という．現在の状態が直前の結果にのみ依存する場合を単純マルコフ，２つ前までの結果に依存するものを二重マルコフ，という．3重，4重マルコフも同様に定義される．特に離散的値をとる（たとえば，天気の種別が晴，雨，曇，雪の４つに減退される場合の）マルコフ過程をマルコフ連鎖という．

情報源: Information Source

情報が生成される（発生する）場をモデル化してとらえた概念．例えば，さいころ投げを行う場合，ある一定の目の数を出すので，さいころ投げの情報源（この場合は，離散的情報源）ととらえる．

離散情報源

確率的な事象において離散的情報を発生させる情報源．さいころ投げ，コイン投げ，じゃんけん，トランプカードの引当て，などが典型的な例．

連続情報源

確率的な事象において，連続値（アナログで計測される値）を発生させる情報源．音声・音楽・映像など自然現象で情報源と見なされる場合が代表的な例．

情報源シンボル

情報源が発生する記号や数字，文字をシンボルという．さいころ投げの場合は，１，２，３，４，５，６がシンボル．コイン投げでは表，裏がシンボル．

無記憶情報源

情報源の出力シンボルが，互いに統計的に独立である場合，その情報源は無記憶（記憶を持たない）という。例えば，さいころ投げで各回に出る目の数は互いに独立なので無記憶情報源と言える。

記憶をもつ情報源

情報源の出力シンボルが，互いに統計的独立でない（依存関係がある）場合，有記憶（記憶を持つ）情報源という．下記のマルコフ情報源が代表的なもの．

マルコフ情報源

記憶を持つ情報源としてはいろいろあるが、最も簡単にモデル化でき、実用上も重要な情報源としてマルコフ情報源がある。

マルコフ情報源とは、情報源の出力シンボルが，その時点をさかのぼるｍ個の出力シンボルのみに依存し，それ以前の出力シンボルには依存しないような情報を発生させる情報源、をいう。

情報源符号化: Source Coding

情報源符号化

情報源から発生する記号系列を別の記号系列に変換すること。変換の仕方はたくさんあるが、その中で情報の確率的な性質を利用してできるだけ短い記号系列に変換する「高能率符号化（データ圧縮ともいう）」が重要である。

シャノンの情報源符号化定理

雑音のない通信路における符号化定理とも呼ばれるもので，情報源（S)が与えられたとき，情報源シンボルあたりのｒ元符号シンボルの平均個数（符号長）は，ｒ元単位で測った情報源のエントロピーＨ（Ｓ)にいくらでも近づけることができるが，この値より小さくできない．すなわち，2元符号の場合は，Ｈ（Ｓ）に近い符号長をもつ符号に符号化できる．

符号効率

情報源符号化定理により、情報源の通報を符号化する場合、最も符号長の短い符号は情報源のエントロピーに近い符号であることが示されている。しかし実際にはエントロピーに等しい符号長の符号が存在するとは限らず、一般には実現可能な符号の符号長はエントロピーより大きくなる。この実際に符号化を行った時の符号長とエントロピーとの比は、符号化の良さを測る尺度となり、符号効率と呼ぶ。

最適符号化

一意に復号可能な符号化の中で、最も平均符号長の短い符号を最適符号化という。よく知られた最適符号化として、ハフマン符号化がある。

一意復号可能

符号を元のメッセージに戻すことを復号化（decoding)というが、ある符号が唯一のメッセージにユニークに復号化できることを一意復号可能という。

瞬時復号可能

符号を復号化する場合、符号語の最後のシンボルを受信した瞬間に復号化できる場合、瞬時復号可能な符号という。これが成り立つ符号は、符号語の長さに一定の制約が存在する。これを明らかにしたのが、クラフトの不等式、マクミランの不等式である。

クラフトの不等式

瞬時復号可能な符号を作ることができるために、各符号語の長さが満たさなければならない制約を与える定理。米国ＭＩＴのクラフトによって証明された（1949年）。

マクミランの不等式

クラフトの不等式は瞬時復号可能な符号が存在する条件を示したものであるが、非瞬時符号でも一意に復号可能ならば符号語の長さはクラフトの不等式を満たさなければならないことを、米国ベル研のマクミランが示した（1956年）。

ハフマン符号

シャノンの情報源符号化定理は、適切な符号化を行えば、平均符号長（Ｌ）が情報源のエントロピーＨ（Ｓ）にいくらでも近づけることができることを示したが、このＬが最も小さい符号（コンパクト符号）の具体的な構成法として米国ＭＩＴのハフマンにより示されたもの。

シャノン・ファノ符号

必ずしもコンパクト符号であることは保証されていないが、それに近い（即ち、エントロピーＨ（Ｓ)に近い）符号長を与えるものとして、シャノン、ファノにより構成法が示されたもの。歴史的にはハフマン符号より古い。

通信路符号化: Channel Coding

通信路 (Channel)

情報源より発せられる情報（通報）を受信者に伝達するための媒体（メディア）のこと．しかし一般には，情報源からの通報はそのままの形では通信路で伝達することができないので，媒体に適した形に変換して送る必要がある．（→通信路符号化）

雑音 (Noise)

情報を通信路で送る場合、電気信号（電圧の大きさ、パルスの有無など）に変えて送る。しかし通信路ではこの信号に擾乱を与える要素、不規則あるいはバースト的に連続して発生する雑音（ノイズ）、ひずみ（Distortion）、などが存在する。これらを総称して「雑音」と呼ぶ。

通信路符号化 (Channel Coding)

情報源符号化により符号化された系列を、通信路で発生する雑音を考慮して、これに打ち勝ち、受信側で復号誤りをできるだけ小さくするように符号化することを通信路符号化という。情報源符号化ではできるだけ平均符号長を小さくしたコンパクト符号が最適であったが、通信路符号化では逆に一定の冗長性を挿入して長さはある程度犠牲にしても復号誤りを小さくする方法が求められる点が特徴である。

シャノンの通信路符号化定理 (Channel Coding Theorem)

雑音がある通信路で受信誤り率を0に近づけるためには、冗長性を与える必要があるため、伝送速度は下がる特性がある。しかしこの速度限界が通信路容量（Ｃ）で与えられることを示したのがシャノンの本定理である。すなわち、伝送速度（Ｒ）が、Ｒ＜Ｃなる条件であれば、任意に小さな復号誤り率の符号が存在することを示した。

通信路容量: Channel Capacity

通信路容量

通信路の送信系列（A)と受信系列（B)の間の相互情報量I(A;B)は、受信系列（B)を知ることによって送信系列（A)に関して得られる情報量、つまり通信路によって運ばれる情報伝達量、を表す。これは、送信記号の発生確率p(a_i)に依存して変わる量である。例えば、送信系列のエントロピーがH(A)=0のときは、送信側から情報が送り出されていないので、I（A;B)＝０となる。このように、I(A;B)は通信路自体が備えている能力を表すには不適当である。そこで、送信系列をいろいろ変えたとき、伝達量が最大になる量を定義し、これを通信路容量という。

注水定理

帯域が制限された相加性ガウス通信路において、信号の電力スペクトル密度関数S（ｆ）、雑音の電力スペクトルN(f)とし、信号の平均電力が一定値（P)に制限されている場合、相互情報量を最大にするS（ｆ）は、S(ｆ）＋N(ｆ）＝一定値を満たすことが知られている。この物理的意味は、雑音N(f)が与えられたとき、N(f)+S(f)＝P（一定）を満たすように、即ち、N(f)の小さいところから池に水をため込むように信号S（ｆ）を与えれば相互情報量I(X;Y)が最大となり、通信路容量を達成する。これが注水定理と呼ばれる。

符号理論: Coding Theory

通信路符号化定理（シャノンの第２定理）は、雑音のある（即ち、誤りが発生する）通信路においても、その通信路の通信路容量Cより小さい転送速度R（＜C)で送れば、受信側での誤り率をいくらでもゼロに近づけることができることを述べている。

しかし、そのような具体的な符号化の方法はシャノンは示さなかった。シャノン以後の多くの研究者は、通信路符号化定理を実現する具体的（構成的）な符号を見つける作業を続けている。この研究分野を符号理論という。

誤り訂正

雑音を発生する通信路においては様々な誤りが発生する。シャノンの通信路符号化定理によれば、適切な符号化をしてかつ符号長を十分長くとれば、通信路で誤りが発生しても復号誤り率を限りなくゼロに近づけることができる。このように、誤りが生じたとき、正しい元の符号に復号することを誤り訂正という。

誤り検出

誤りが発生したとき、誤りが生じたこと（存在すること）のみを受信側でわかるようにすることを誤り検出という。受信側では送信側に再送を求めたりする。

FEC

前方向誤り訂正（Forward error correction)のこと。誤り訂正では、受信側で系列を調べて、誤り箇所や内容を判別し、送信側に問い合わせることをしない。この方式は後ろ（送信側）に戻さないため、前向きの誤り訂正という。

ARQ

自動再送要求（Automatic Repeat Request)のこと。受信側で誤りを検出した時、送信側に再送を要求して、再送を待って訂正する一連の手順を自動的に行う方式。

誤り制御

FEC方式とARQ方式の両方を総称して誤り制御（Error Control)という。

誤りパターン

誤りが発生したとき、その誤りの位置を示すn次元ベクトルで表わされる系列（但し、ｎは符号語の長さ）。即ち、第ｉ番目に生じた誤りは、ｅ_ｉ＝（0,0,..,1,0,..0)と表わされる。誤り系列ともいう。

誤り訂正の原理

情報源を符号化する場合、通信路で雑音が生じなければできるだけ符号長を短くする符号が効率が良い。これに対して、雑音が発生する通信路に情報を送出する場合、受信側で誤りなく復号できることが必要である。このためには、符号語の中にある程度冗長なビットを追加することである。この原理は、符号語をｎ次元空間の点（頂点）のサブセットと考え、一定の誤りパターンの距離だけ離して配置すれば、途中で一定限度以下の誤り（誤りパターン）が生じても、元に戻せる（復号できる）、という考え方である。

ランダム符号化

情報源の系列を符号化する場合に、固定された符合語の割り当てかたを考えるのでなく、長さ（ｎ）の系列の中から無作為（ランダム）に1個ずつ符号語として系列を選び割り当てる方法をいう。この方法は実用的ではなく、極端な場合はすべての情報源系列に同じ符号語が割り当てられることもある。しかし、このランダム符号化法は、誤り率上界の推測、評価が容易になるメリットがあり、シャノンが初めて通信路符号化定理を証明する際に導入した。

ハミング距離

符号の誤り訂正（あるいは 誤り検出）能力を示す指標として符号語の間の距離がある。２元符号の場合、符号語は２元シンボルの系列で表されるが、これ幾何学的に長さｎの2元シンボルの系列ｕ、ｖを考える。すなわち、ｕ＝（u1, u2, u3,...,un)、v=(v1, v2, v3,..., vn)とする。各成分ui, vjは0か1かである。このとき、ｕとｖとの間のハミング距離H(u, v)は、次のように定義される。

ｕ＝（u1, u2, u3,...,un)、v=(v1, v2, v3,..., vn)のハミング距離 H(u, v)は、
H(u, v)=Σ_i δ(u_i, v_i)
ここで、δ(u_i, v_i) =0 (ui=vi); δ(u_i, v_i) =1 (ui≠vi)
で定義される。

すなわち、ハミング距離は２つの系列の相対応する位置にあるシンボル（文字）が互いに異なる場合の全体総和として定義される。例：u=(1,1,1,1,1), v=(1,0,1,0,1)、の場合、H(u,v)=2、となる。
ある符号のすべての符号語の間のハミング距離は一定ではなく、異なるのが通常である。

最小距離

算術距離

モジュラ算術距離

線形符号

パりティ検査符号

パりティ検査方程式

パりティ検査行列

シンドローム

ハミング符号

ランダム誤り

バースト誤り

インターリーブ

群符号

CRC符号

Cycle Relundancy Codeの略。

BCH符号

巡回ハミング符号

算術符号

AN符号

畳み込み符号

生成多項式

符号多項式

検査多項式

最小多項式

原始多項式

最尤復号

Viterbiアルゴリズム

逐次復号

暗号理論: Cryptography Theory

暗号理論は、情報理論の

逐次暗号

ブロック暗号

ストリーム暗号

転置暗号

暗号安全性

シャノン暗号理論

暗号鍵

秘密鍵暗号

DES暗号

FEAL暗号

公開鍵暗号

RSA暗号

離散対数問題

楕円曲線暗号

認証

ディジタル署名

暗号プロトコル

ギャンブルと情報理論

ユニバーサルギャンブリング

データ圧縮と賭け

アナログ情報理論

標本化定理: Sampling Theorem

標本化

量子化

帯域制限信号

シャノン染谷の標本化定理

時間領域の標本化定理

周波数領域の標本化定理

標本化定理の変形版

データ圧縮: Data Compression

データ圧縮

高能率符号化

速度歪理論

英語ではレート・ディストーション(Rate-Distortion)理論という。

無歪情報圧縮: Lossless Data Compression

無歪圧縮

圧縮限界

エントロピ符号化

FV符号

VF符号

アルファベット順符号

有歪情報圧縮: Lossy Data Compression

有歪圧縮

RSA暗号: RSA Cryptography

RSA暗号

安全性

ゼロ知識証明: Zero-Knowledge

対話証明

ゼロ知識

識別不可能性

完全識別不可能性

統計的識別不可能性

計算量的識別不可能性

ゼロ知識証明

楕円暗号: Ecliptic Cryptography

楕円曲線

指数計算法

楕円エルガマル暗号

楕円RSA暗号

量子情報理論: Quantum Information Theory

量子力学

量子情報

量子計算

量子誤り訂正符号

量子暗号

ユニバーサル符号: Universal Code

LZ符号

Rissanen符号

MDL原理

漸近的最良性

情報幾何: Information Geometry

情報源の幾何学

ダイバージェンス

低密度パリティ検査符号: Low Density Parity Check Code

ターボ符号

LDPC符号

反復復号法

sum-product符号

BP原理

密度発展法

２部グラフ

タナーグラフ