211service.com
コードクエスト
1948年、世界はまだアナログの場所でした。 CandidCameraとEdSullivanは、テレビでのロングランを始めたばかりでした。ジャックベニーのラジオ番組には、数千万人のリスナーがいました。しかし、悪いレセプションは人生の事実でした。電磁干渉、送電鉄塔と受信機の間の物理的な障害物、およびエンジニアがノイズと呼ぶその他の原因により、ベニーの独白やサリバンのゲストのパフォーマンスが日常的に混乱しました。ほとんどの地域では、少なくとも一部の放送局では、人々は雪に覆われた画像や静的に問題のある音声に辞任しました。
クロード・シャノン、1948年
しかし、その同じ年、Claude Shannon、SM ‘40、PhD ‘40は、多くのノイズが存在する場合でも、事実上エラーなしで情報を送信できることを数学的に証明した画期的な論文を発表しました。それはアナログの世界でしたが、シャノンの驚くべき結論は、デジタルで考える能力の結果でした。シャノンは、あらゆる媒体の情報は、2進数、つまりビットを使用して表すことができると主張しました。これは、彼の論文が世界に紹介した単語です。通信チャネルのノイズによってビットが破損する可能性がある一方で、既知のアルゴリズム（エラー訂正コード）によって元のビットに関連するビットを追加すると、元のシーケンスを推測できるようになると彼は説明しました。
チャネルのノイズが多いほど、エラー訂正を可能にするために、より多くの情報を追加する必要があります。そして、より多くの追加情報が含まれるほど、送信は遅くなります。シャノンは、最小のエラーを保証できる最小の余分なビット数を計算する方法を示しました。したがって、エラーのないデータ送信が可能な最高のレートです。しかし、彼は実際のコーディングスキームがどのように見えるかを言うことができませんでした。
研究者は45年かけて1つを探しました。最後に、1993年に、フランスのエンジニアのペアが、シャノンの理論上の限界に近いデータレートを達成する一連のコード（ターボコード）を発表しました。最初の反応は信じられないほどでしたが、その後の調査で研究者の主張が確認されました。それはまた、さらに驚くべき事実を明らかにしました。同じタイプの数学的トリックにさえ依存するターボ符号と同じくらい優れた符号は、30年以上前にロバート・ギャラガー、SMのMIT博士論文で導入されました。 57、ScD'60。何十年にもわたる怠慢の後、ギャラガーのコードはついに実用化されました。それらは衛星テレビや無線データの送信に使用され、それらをデコードするための専用チップは商用携帯電話にあります。
情報理論の誕生
ギャラガーは1956年にMITに来ました。同じ年、ベル研究所で15年間過ごした後、シャノン自身が教授として戻ってきました。しかし、シャノンと一緒に仕事をするという見通しがなかったため、彼はエール大学よりもMITを選びました。そこでは、彼も大学院に出願していました。私は軍隊にいて、意味のない任務に就いていました。博士号を取得してから40年以上MITで教鞭をとり、大学院生に名誉教授としてエレクトロニクス。 MITはエール大学より1週間早く開始しました。そして、私は軍隊から抜け出すことをとても切望していたので、それがMITに来る唯一の理由でした。
ギャラガーは、シャノンの1948年の論文から生まれた、急成長している新しい分野である情報理論を研究したいとさえ確信していませんでした。しかし、陸軍通信部隊に加わる前は、ギャラガーもベル研究所で数年間働いていました。そこでは、電気工学の最新の進歩について学ぶために、週に3日教室で過ごしました。彼はシャノンに会ったことがありませんでしたが、その経験は彼が彼の達成の範囲を認識するのに役立ちました。私は彼を一種の神と見なしただけだ、とギャラガーは言う。
確かに、シャノンがMITの教員に加わったとき、彼は未成年の有名人でした。早くも1953年に、フォーチュン誌の情報理論に関する記事が宣言されました。人間の平和の進歩と戦争の安全は、爆弾のいずれかでの物理的なデモンストレーションよりも、情報理論の実りある応用に依存していると言っても過言ではありません。または発電所では、アインシュタインの有名な方程式が機能します。
人々の想像力をかきたてたのは、テキスト、オーディオ、ビデオなど、あらゆる多様性の情報を1と0の単なるシーケンスにまとめることができるという考えでした。商用のデジタルデバイスはまだ存在していなかったため、001001010101000101011101が交響曲の一部、映画の一部、色、または本の線を表す可能性があることに人々は驚かされました。しかし、シャノンが彼の論文で指摘したように、彼のベル研究所の同僚であるラルフ・ハートレーは、20年前に同様の提案をしていました。シャノンの仲間のエンジニアを魅了し、魅了し続けている論文の側面は、チャネルの容量までエラーのないデータ送信を生成できるコードが必要であることを彼が証明した独創的な方法でした。
エラー訂正コードがどのように機能するかを理解するために、ノイズの多いチャネルを介して4ビットメッセージを送信しようとしている人を考えてみてください。ノイズによってビットの1つが反対に反転する場合、受信機はエラーが発生したことを知る方法がありません。メッセージを繰り返すだけで、0011が00110011になり、その問題が解決されます。1つのビットが反対に反転した場合、メッセージの2つのバージョンが一致しないため、受信者はエラーがあることを認識します。しかし、どちらが正しいかを判断することは不可能です。メッセージをエンコードするより良い方法は、メッセージビットに関する情報を表すために4つの追加ビットを使用する場合があります。たとえば、5番目のビットは、メッセージの最初の2ビットが同じ値か異なる値かを示します。 6番目のビットはビット3と4で同じことを実行でき、7番目はビット1と3で、8番目はビット2と4で同じことを実行できます。最初の4ビットの1つが反転した場合、最後の4ビットはそれを識別できます。最後の4ビットの1つが反転した場合、他の3つはそれを補うのに十分な情報を伝達する可能性があります。
ただし、シャノンの論文は、実際にコードを作成する方法についてのそのような反論を避けています。代わりに、完全にランダムに選択されたコードの一般的なプロパティを統計的に分析することにより、エラー訂正の概念にアプローチします。彼のアプローチを理解するには、4ビットメッセージをエンコードする仮想の8ビットシーケンスにどのように適用できるかを確認することが役立つ場合があります。
考えられる4ビットメッセージは16あり、シャノンの方法では、それぞれにランダムに選択された独自の8ビットシリアル番号（コードワード）が割り当てられます。受信者は、送信者と同様に、16個の可能な4ビットメッセージを16個のランダムな8ビットコードワードと相関させるコードブックを持っています。 8ビットの可能なシーケンスは256あるため、コードブックに表示されないシーケンスは240あります。これらの240のシーケンスの1つを受け取った人は、エラーがデータに忍び込んだことを知っています。ただし、許可されている16のコードワードが互いに十分に異なる限り、破損したシーケンスに最も近いのは1つだけである可能性があります。たとえば、00000001と11111110はどちらも有効なコードワードであるが、00000011はそうではない場合、シーケンス00000011を受け取った人は、意図したコードワードが11111110よりも00000001である可能性がはるかに高いと結論付けることができます。
もちろん、実際には、4ビットのメッセージを送信することを心配する人は誰もいません。しかし、統計分析を使用することにより、シャノンは、任意の量のノイズを伴うチャネルを介して送信された、任意の長さのエンコードされたメッセージについて結論を出すことができました。特に、彼はランダムに選択されたコードワード間の差異の程度と、破損したシーケンスがそれらの1つにのみ類似する可能性の両方を厳密に定量化することができました。 2つの8ビットシーケンスが類似する可能性は比較的高いですが、シャノンは、コードワードが長くなるにつれて、類似の可能性が指数関数的に減少することを示しました。実際、彼の最も驚くべき結果の1つは、長いメッセージの場合、ランダムに割り当てられたほとんどのコードワードは、可能な限り互いにほぼ同じように異なるということでした。つまり、ほとんどすべてのコーディングスキーム（これらの単語を生成する方法）により、ノイズの多いチャネルを介して最大レートに近いエラーのない伝送が可能になります。
1996年にMITに戻ったCodexCorporationとMotorolaの元副社長であるDavidForney、SM '63、ScD '65は、完全にランダムなコードが平均してかなり良いコードであると考えるのに多くの直感が必要でした。非常勤教授として。これにより、平均的なケースの分析を実行できるようになったため、分析が大幅に簡素化されることがわかりました。フォーニーは少しの間立ち止まり、それから付け加えます。それが完全に単純だったとは言えません。数学の分野ではないにしても、少なくともいくつかの定理を発明しなければなりませんでした。しかし、ギャラガーは同意します。シャノンの1948年の論文について、彼は次のように述べています。2年間研究した後、それは非常に単純に思えます。とても多くの人があなたに「それは本当にとても簡単です」と言うでしょう。そしてあなたがそれを理解した後、それはそうです。
たまらない挑戦
シャノンの情報の数学的記述には、多くの影響がありました。彼の1948年の論文では、データ圧縮、つまり同じ情報をより少ないビットで表現するというアイデアも紹介されました。圧縮は、WinZipやStuffItなどのプログラムがファイルを縮小して、電子メールサーバーを圧倒しないようにするものであり、ディスクドライブのスペースを節約するために使用されます。情報理論はまた、暗号化の研究をより安全な数学的基盤に置きます。実際、ギャラガーは、ベル研究所でのシャノンの戦時中の暗号化作業が、彼のコミュニケーションの斬新な再認識につながったと信じています。
しかし、シャノンがMITに戻るまでに、彼は自分の理論を取り巻く熱意がそのかなりのメリットさえも超えていると感じ始めていました。バンドワゴンと呼ばれる1956年の記事で、彼は生物学、心理学、言語学、基礎物理学、経済学、組織論などの分野に情報理論を適用する試みを引用し、この状況で節度のメモを注入することを約束しました。
シャノンの脚光を浴びることへの嫌悪感は、排他性に隣接しています。情報理論の発展について本を書いているサンノゼ州立大学の経営学部の教授であるJoelWest ‘79によると、シャノンはMITでの22年間に7人の大学院生にしかアドバイスしていませんでした。彼はかなり恥ずかしがり屋で引退していたので、彼を監督者にしたければ、本当に積極的にならなければならなかったとギャラガーは言います。私も恥ずかしがり屋で引退していて、その男と話をするのに十分な自信がありませんでした。
教師として、シャノンはなじみのある退屈さに対してほとんど忍耐力がありませんでした。カリフォルニア大学バークレー校の数学名誉教授であり、シャノンの共著者であったエルウィン・バーレカンプ'62、SM '62、PhD '64は、古いものよりも新しいものにはるかに興味を持っていたと述べています。最終的に発表された論文。
彼は多くを教えていませんでした、とギャラガーは言います。しかし、彼が教えたとき、それは研究の話をするようなものでした。学期中に約25回の講義を行ったことがあり、いずれも新しい研究成果であったことを覚えています。彼はそれらを次々と行い、何か面白いものを思いつくことに失敗することはありませんでした。本当に素晴らしい時期でした。
私の意見では、シャノンは学界では少し場違いだったと、ETHチューリッヒの情報理論家で名誉教授であるジェームズL.マッセイ（SM ‘60、PhD ‘62）は言います。彼の本当のジャンルは、独立した研究者であり、彼自身の非常に個性的な方法で物事を行うことでした。
シャノンが単に褒め言葉に不快感を覚えていたのかもしれません。 Berlekampは、IEEE Information Theory Societyがシャノンに講演を依頼し、1973年にイスラエルで初のシャノン賞を受賞したときのことを思い出します。彼よりも蝶が多い人を見たことがない、と彼は言います。話が始まる5分前、彼はバーにいて、かなり落ち込んでいます。彼はステージに上がり、みんなをがっかりさせることを本当に恐れています。もちろん彼らは神を期待しているのですが、それは真実であり、彼は神のように演じることができないことを知っています。
しかし、シャノンが情報理論の若い学生の直接の指導者になることはめったになかった場合、彼は彼らに魅力的な挑戦を設定しました。ランダムコーディングは実際には機能しません。シャノンの架空のコードブックのサイズは、メッセージにビットが追加されるたびに2倍になります。インターネット上を移動する単一の1,000ビットデータパケットのコードブックには、宇宙に存在する原子よりも多くのエントリが必要になります。ただし、元のメッセージを繰り返したり、メッセージビットを記述したビットを追加したりするなど、より実用的なコーディングメカニズムは、同じコードワードを生成するという点で、ランダムなコーディングスキームと同等でした。そして、ランダムコーディングスキームの大部分が容量に近づいていることを実証することにより、シャノンは実用的なものの1つも同様であるという希望を提供しました。
とらえどころのないコード
コードブックを使用してコードワードとメッセージを照合する代わりに、実用的なコーディングスキームは、コードワードからメッセージを計算で抽出する方法を提供します。一連の数学演算は、精度の高い確率で、ノイズの多いチャネルを介して受信された、破損している可能性のあるビットシーケンスのエラーを識別して修正できます。
優れたエンコーディングアルゴリズムが必ずしも優れたデコーディングアルゴリズムを意味するわけではないことは、エラー訂正コードの特徴の1つです。シャノンと同様の統計分析を使用して、コーディング理論家は、特定のコードが容量に近づいていること、つまりコードワード間の違いを最大化することを示すことができました。しかし、それは彼らがそれをデコードする効率的な方法を持っているという意味ではありませんでした。
シャノンの論文が発表されてから1990年代初頭にかけて、研究者たちはより優れたコードと、より優れたデコードアルゴリズムを提案しました。しかし、実際の容量に近づくコードは、とらえどころのないままでした。 Forney氏によると、コーディング理論家の間では、考えられるすべてのコードを除いて、ほとんどすべてのコードが優れていると言われていました。
Gallagerが1960年の博士論文で提示したコードは、デコード効率を犠牲にすることなく、シャノンの仮説システムのランダム性の一部を維持する試みでした。以前の多くのコードと同様に、Gallagerはいわゆるパリティビットを使用しました。これは、他のビットグループの合計が偶数か奇数かを示します。しかし、以前のコードは体系的な方法でパリティビットを生成しました。最初のパリティビットは、メッセージビット1から3の合計が偶数であるかどうかを示す場合があります。次のパリティビットは、メッセージビット2〜4に対して同じことを行い、3番目はビット3〜5に対して同じことを行う可能性があります。対照的に、ギャラガーのコードでは、パリティビットとメッセージビットの相関関係はランダムでした。最初のパリティビットは、たとえば、メッセージビット4、27、および83の合計を表す場合があります。次は、メッセージビット19、42、および65に対して同じことを行う可能性があります。
Gallagerは、長いメッセージの場合、彼の疑似ランダムコードが容量に近づいていることを数学的に示すことができました。容量に近づいている他のことも知っていた以外は、彼は言います。どのコードが優れているかという問題ではありませんでした。それは常に、どのような種類のデコードアルゴリズムを考案できるかという問題でした。
ギャラガーが突破口を開いたのはそのためです。彼のコードは反復デコードを使用していました。つまり、デコーダーはデータを数回通過し、各ビットのIDについてますます洗練された推測を行います。たとえば、パリティビットがビットのトリプレットを記述している場合、任意の2ビットに関する信頼できる情報が3分の1に関する情報を伝達する可能性があります。 Gallagerの反復デコードアルゴリズムは、彼自身のコードをデコードするだけでなく、ターボコードもデコードするために今日最も一般的に使用されているものです。また、多くの人工知能システムで使用されているタイプの統計的推論にも適用されています。
反復法では、受信したビットが何であるかを最初に推測し、信頼性に応じて重みを付けます、とForney氏は言います。次に、他のビットとのパリティチェックに関係しているため、より多くの情報が得られる可能性があります。これにより、信頼性の見積もりが改善されます。最終的に、フォーニーは、推測はメッセージのすべてのビットの一貫した解釈に向かって収束するはずだと言います。
ギャラガーは、シャノンに顧問を依頼する勇気を奮い立たせることができなかったが、論文を書いている間、シャノンと3、4回話をしたと言っている。クロードと3、4回話すことは、ほとんどの人と50回話すようなものだったことを除けば、彼は言います。彼は本当に非常に速くアイデアを理解した人でした。彼は技術的な詳細についてはまったく素晴らしかった。しかし、何かの構造を見て、なぜそれが機能する必要があるのか、そして何がそれをより良くするのかを知るために、彼は確かに私が今まで出会った中で最も賢い人でした。
それでも、シャノンはギャラガーのコードの成功を予見していませんでした。私の記憶では、彼は彼らが面白いと思っていましたが、彼が彼らに興奮しているという感覚はありませんでした、とGallagerは言います。彼はその理由を理解しています。 Gallagerのコードは、長くなるにつれてチャネル容量に近づきました。しかし、それらが長くなるにつれて、デコードプロセスもより複雑になり、当時のコンピューターには複雑すぎました。もちろん、コーディング研究者はコンピューターが改善されることを知っていました。しかし、それらの改善が誰のコードを支持するかは誰も知りませんでした。
それにもかかわらず、MITは彼の論文の強さですぐに教員としてギャラガーを雇いました。その後の数年間、彼自身のコーディングスキームはあいまいになりましたが、マッセイ、フォーニー、バーレカンプなどの優秀な学生の波を教え、指導しました。彼らのコーディング理論への貢献は、彼自身よりも直接的な実践的な意味合いを持っていました。
しかし、ギャラガーは、最近の復活と同じように、彼のコードを長い間無視していたことで、おそらく彼が常に長い視野を持っていたために、波立たないように見えます。彼は、人々が突然それがかなり良いものであることに気付くまで、何十年も休眠しているものを発明するコツを持っています、とVincent Chan '71、MS '71、EE '72、PhD '74、電気工学の教授はまだ彼の机は、かつてシャノンと共有していたオフィスの玄関板です。 Chanは、ある大手ソフトウェア会社のラボを最近訪れたことを思い出します。そこでは、研究者が、ビデオファイルが現在の100分の1のメモリしか使用できない新しい圧縮技術を誇っていました。チャンは、ギャラガーが1974年にこの手法を導入したことを指摘する義務があると感じました。これらのアイデアの多くは、熟考するのにかなりの時間がかかります。 。そして、どれが正しいかを判断する前に、本当に慎重に、そしておそらく長期間にわたって考える必要があります。ボブはそれをたくさんします。
エレクトロニクス研究所の情報理論家であるMurielMédard‘89、‘90、MS ‘91、ScD ‘95も同意します。ボブは出版しようとして走り回っていなかったし、彼がすくわれていないことを確認した、と彼女は言います。たとえば、メダールは、ギャラガーと著名な若い情報理論家との会話を思い出します。彼は自分の作品を説明する際に、それが依存している最近証明された定理を引用しました。ボブは、彼と同じように、物事をくまなく探し始めます、とメダールは言います。最終的に、彼は自分の論文の1つのボロボロのコピーを作成しました。彼はこの小さな証拠を持っていた、とメダールは言います。そしてそれは脚注のようでした。太い脚注ですが、脚注です。 「彼らはそれを名付けましたか？」「ええ、ボブ、それは今の主要な定理です。」
現在、Gallagerのコードは、特定の通信チャネルの最大データレートに最も近いアプローチの根底にあります。ターボコードよりも近いものです。電気通信でのアプリケーションに加えて、ディスクドライブやその他のストレージデバイスのデータを保護するために使用されていた古いコードに取って代わり始めています。
コーディング理論の黄金時代と呼ばれるMITにいたフォーニーのような人々にとって、シャノンの1948年の論文によって発行された課題が解決されたという事実はややほろ苦いものです。コーディングを知っていて大好きな私たちの人々は、問題が完全に解決されたとは言いたがりません、とフォーニーは言います。しかし、ほとんどの人が他のことに移っているのは事実です。
1950年から1965年まで、MITは情報理論の温床でしたとJoelWestは言います。本当に黄金時代でした。 