Richard Hamming：第12章エラー修正コード

「このコースの目標は、技術的な未来に向けて準備することです。」

こんにちは、Habr。 「You and Your Work」という素晴らしい記事（+219、2442のブックマーク、394kの読み取り）を覚えていますか？



そのため、ハミング（はい、はい、自己チェックおよび自己修正ハミングコード ）には、彼の講義に基づいて書かれた本があります。 男が問題を言うので、私たちはそれを翻訳します。



この本はITだけでなく、信じられないほどクールな人々の思考スタイルに関する本です。 「これは単なる肯定的な思考の責任ではありません。 素晴らしい仕事をする可能性を高める条件を説明しています。」



すでに26（30の内）の章を翻訳しています。 そして、 私たちは紙版に取り組んでいます。

第12章エラー修正コード

（翻訳のおかげで、ミハイル・シェブラエフ、「前の章」で私の電話に答えてくれました。）翻訳を手伝いたい人-個人の電子メールまたはmagisterludi2016@yandex.ruに書いてください



この章では2つのトピックについて説明します。1つ目は明らかにエラー訂正コードであり、2つ目はオープニングプロセスが時々発生する方法です。 ご存知のように、私はハミングエラー訂正コードの公式発見者です。 したがって、明らかに、私はそれらがどのように発見されたかを説明する機会があります。 ただし、このタイプのストーリーには注意する必要があります。 実際、当時、私はすでに発見プロセスに非常に興味があり、多くの場合、発見方法は公開されている方法よりも重要であると信じていました。 アスリートが競技の際にテクノロジーについて考えるのではなく、自動的にそれを練習するように、研究中にプロセスについて考えないように十分に知っていました。 また、大規模または小規模な発見の後に戻って、それらにつながったステップを追跡しようとする習慣を開発しました。 しかし、だまされてはいけません。 せいぜい、意識部分と潜在意識部分の小さな先端について説明できますが、潜在意識の魔法はわかりません。



ニューヨークのModel 5リレートランスミッターを使用して、必要なソフトウェア（主に数学プログラム）とともにAberdeen Proving Groundsに出荷する準備をしました。 5つのうち2つのブロックコードを使用してエラーが検出された場合、放置されたマシンは、エラーサイクルを最大3回繰り返してから、それを破棄して新しいタスクを実行し、問題の機器が新しいソリューションに関与しないことを期待できます。 当時、私は彼らが言うように、ジュニア用務員のシニアアシスタントでしたが、週末には金曜日の午後5時から午前8時まで無料の機械時間しかありませんでした-それは多くの時間でした！ そのため、多くのタスクを含む入力テープをダウンロードし、友人たちに、研究部門のあるニュージャージー州マレーヒルに戻り、火曜日までに回答を準備することを約束することができました。 ある週末、金曜日の夕方に出発するとすぐに車は完全に故障し、月曜日までに私はまったく何もありませんでした。 私は友人に謝罪し、来週の火曜日までに彼らに答えを約束しなければなりませんでした。 ああ！ 同じ状況が再び起こりました！ 私はやや怒って、「マシンがエラーの存在を判断できるなら、なぜエラーがどこにあるのか、それを修正しないのかを判断し、ビットを反対に変更するだけですか？」（実際、使用される表現は少し強かった！）



まず、この重要な変化は、私がその瞬間に途方もない感情的なストレスを経験していたために生じたものであり、これは大部分の大きな発見の特徴であることに注意してください。 静かな仕事により、アイデアをより詳細に改善および発展させることができますが、通常、ブレークスルーは多くのストレスと感情的な関与の後にのみもたらされます。 落ち着いた、冷たく、関わりのない研究者は、めったに大きな新しいステップを踏みません。



話に戻りましょう。 もちろん、以前の議論から、比較回路を含む計算機の3つのインスタンスを構築し、多数決方式によるエラー修正を使用することが可能であることを知っていました。 しかし、それはいくらですか？ もちろん、より良い方法がありました。 前の章で説明したように、クールなパリティについても知っていました。 私はそれらの構造を非常に注意深く理解しました。

一方、パスツールは次のように述べています。「幸運は訓練された人を愛しています。」 ご覧のとおり、私は以前の仕事で準備ができていました。 私は2-of-5コーディングを知っていて、それらを基本的に理解し、パリティの一般的な結果を理解しました。







図 12.I



少し考えてから、メッセージシンボルのビットを長方形に入れて各列と各行のパリティを書き込むと、2つのパリティチェックに失敗すると1つのエラーの座標が表示され、これには角度付きパリティビットが追加されることがわかりました（これに応じて設定できます）奇数の値があった場合）図 12.I. 冗長性、つまり使用するものと最小必要量の比率は







分析を研究した人なら誰でも、長方形を正方形に近づけるほど、同じサイズのメッセージの冗長性が減ることは明らかです。 そして、もちろん、mとnの大きな値は小さな値よりも優れていますが、エンジニアリングの観点からすると、二重エラーのリスクは大きくなります。 2つのエラーが発生した場合は、次のことに注意してください。（1）同じ行または列にない場合は、2行2列にエラーが含まれているだけで、どの対角線のペアが原因かわかりません。 （2）同じ行（または列）で2つのエラーが発生した場合、1行（列）ではなく1列（行）しかありません。



数週間後に早送りします。 ニューヨークに着くには、少し早くニュージャージー州マレーヒルに行き、そこで働いて、会社に郵便を配達する車に乗らなければなりませんでした。 ええ、はい、早朝のニュージャージー州北部の旅行はあまり絵に描いたようなものではないので、ペンが自動的に回転するように私の業績をレビューする習慣になりました。 特に、頭の中で長方形のコードをねじった。 突然、この理由がわかりませんが、三角形を取り、パリティビットを対角線上に配置して、各ビットが列と行を同時にチェックすると、より許容できる冗長性が得られることがわかりました（図12.II）。



私の自己満足はすぐに消えました！ 今回は最高のコードを取得できましたか？ このことについて数マイル考えた後（ニュージャージー州北部の景観に気を散らすものは何もないことを思い出してください）、各平面にパリティがあり、3軸すべてに沿って軸にパリティがある情報ビットの立方体がエラーの3つの座標を与えることに気付きました長さn ^ 3の整数コード化メッセージの3n-2パリティチェックのみのコストで。 より良い！ しかし、これが最良の解決策でしたか？ いや！ 数学者として、私はすぐに、4次元の立方体（内部接続を示すためだけに、そのようなビットを配置するべきではありません）がさらに優れていることに気付きました。 したがって、さらに高い次元がさらに優れています。 すぐに明らかになりました（たとえば、5マイル後に）、n + 1パリティを持つ2x2x2x ... x2キューブの方が良いことは明らかです-明らかに！







しかし、一度指を火傷すると、見栄えに同意するつもりはありませんでした-以前にこの間違いを犯していたのです！ これが最良のソリューションであることを証明できますか？ それを証明するには？ 1つの明らかなアプローチは、パラメータをカウントしようとすることでした。n+ 1ビットの文字列にマッピングされたn + 1制御ビットがありました。 長さn + 1ビットの2進数。これは長さ2 ^ {n + 1}の任意のオブジェクトを表すことができます。 しかし、必要なのは2 ^ n + 1ビット、キューブ内の2 ^ nポイントと1ビットだけで、メッセージが正しいことを確認しました。 私は考慮のビットのほぼ半分を考慮しませんでした。 ああ！ 私は会社のドアに到着し、登録して会議に行き、アイデアを横にした。



気を散らす出来事の数日後にアイデアに戻ったとき（結局、私は会社のチームの努力に貢献したと想定されていました）、最終的に、エラーの場所を示すバイナリ番号としてエラーシンドロームを使用することが良いアプローチであると最終的に決定しました正しい結果の場合はゼロビット（ほとんどのコンピューターのすべてのユニットよりも簡単なテスト）。 バイナリシステム（当時は普及していなかった（1947-1948））に精通していることは、私の構造において顕著な役割を繰り返し果たしていたことに注意してください。 これは、必要な情報をすぐに知るための料金です！

エラー修正コードのこの特別なケースをどのように構築しますか？ 簡単！ バイナリコードで位置を記述します。







シンドロームの右半分のパリティチェックには、右の列に1があるすべての位置が含まれている必要があることは明らかです。 右側の2番目の数字には、2番目の列に1が含まれる数字などを含める必要があります。 したがって、あなたが持っている：







したがって、特定のカテゴリでエラーが発生すると、対応するパリティチェック（およびこれらのみ）が失敗し、シンドロームで1が返されます。これは、エラー位置のバイナリ表現を正確に構成します。 簡単です！



コードの動作を確認するために、メッセージ用に4ビットと3つの制御位置に制限しています。 これらの数値は条件を満たす







これは明らかに必要条件であり、平等で十分です。 チェックビットの位置を選択します（パリティが容易になるように）制御ビット1、2、4。メッセージの位置-3、5、6 7。



1001



（1）メッセージを最上行に書き込み、（2）次の行をエンコードし、（3）次の行の位置6にエラーを挿入し、（4）次の3行に、3つのパリティチェックを計算します。







受信したメッセージにパリティチェックを適用します。







2進数110->6。したがって、位置6で変更し、チェックディジット1、2、および4を破棄すると、元のメッセージ1001を受け取ります。



これが魔法のように思える場合、制御位置が0であるすべて0からのメッセージを考えてから、1ビットの変化を想像すると、エラーの位置がどのように移動するかがわかり、それに応じてシンドロームの2進数が変化し、エラーの位置と正確に一致します。 次に、2つの有効なメッセージの合計がまだ有効なメッセージであることに注意してください（パリティチェックは2を法とする加法であるため、正しいメッセージは2を法とする加法グループを形成します）。 正しいメッセージはすべてゼロを与えるため、正しいメッセージの合計と1つのカテゴリのエラーは、送信されるメッセージに関係なくエラー位置を示します。 パリティチェックはエラーに焦点を合わせ、メッセージを無視します。



これで、チャネルの両端で一致した2つ以上の列を交換しても、重要な効果がないことがすぐにわかります。 コードは同等になります。 同様に、任意の列で0と1を再配置しても、大幅に異なるコードは生成されません。 特に、（いわゆる）ハミングコードは単純な美しい並べ替えであり、実際には、メッセージの途中に分散させるのではなく、メッセージの最後にある制御ビットを確認できます。



二重の間違いはどうですか？ 二重エラーをキャッチする（ただし、修正しない）場合は、送信するメッセージ全体に単一の新しいパリティチェックを追加します。 チャンネルの最後で何が起こるか見てみましょう。







多くの場合、単一エラー訂正と二重エラー検出のバランスが取れています。 もちろん、4ビットのショートメッセージ（現在は4チェックビット）の冗長性は悪いですが、チェックビットの数はメ​​ッセージ長の対数として（おおよそ）増加します。 メッセージが長すぎると、二重の修正不可能なエラー（1つのエラーを修正したコードを使用して3番目のエラーで「修正」できる）、メッセージが短すぎるというリスクが発生し、冗長性のコストが高すぎます。 繰り返しますが、特定のケースに応じたエンジニアリング上の考慮事項...



分析ジオメトリから、補完的な代数的および幾何学的表現を使用することの重要性を学びました。 ビット列の自然な表現は、n次元の立方体を使用することで、その各行は立方体の頂点です。 この画像を使用して、メッセージの1つのエラーがメッセージを1つのエッジに沿って移動させたり、2つのエラーを2つのエッジに沿って移動させたりすることに気づき、スペース$ L_1 $で行動する必要があることに徐々に気付きました。 要素間の距離は、要素が異なる桁数です。 したがって、空間にメトリックがあり、距離の3つの標準条件を満たします（L_1の標準距離については、第10章を参照してください）。







したがって、ピタゴラス距離関数の抽象化として知っていたことを真剣に受けとめるべきでした。



距離の概念を使用して、中心から一定の距離にあるすべてのポイント（頂点はすべて頂点のセットで考慮されるため）として球を定義できます。 たとえば、簡単に描画できる3次元の立方体では、図 12.III、ポイント（0,0,1）、（0,1,0）、および（1,0,0）は（0,0,0）から単位距離にあり、ポイント（1、 1,0）、（1,0,1）、および（0,1,1）はさらに2の距離にあり、最後に点（1,1,1）は原点から3の距離にあります。



次に、n次元の空間に移動し、各点の周りに単位半径の球を描き、球が交差しないと仮定します。 明らかに、球体の中心はコード要素であり、これらのポイントのみであるため、メッセージ内の単一のエラーを受信した結果は「非コード」ポイントとなり、このエラーの原因を理解できます。 これは、私が送ったコードポイントの周りの球の中にあります。これは、受け取ったコードポイントの周りの半径1の球に相当します。 したがって、エラー修正コードがあります。 コードポイント間の最小距離は3です。半径2の非交差球を使用する場合、結果のポイントが他のどのポイントよりも元のコードポイントに近くなるため、二重エラーを修正できます。 二重補正の最小距離は5です。次の表は、コードポイント間の距離とエラーの「修正可能性」の等価性を示しています。







したがって、エラー修正を使用したコードの構築は、n次元空間でのコードポイントのセットの構築とまったく同じです。







上記の条件が必要かつ十分であるため、法的通信の間に必要な最小距離があります。 また、エラーの修正を検出と交換できることも明らかです。1つのエラーの修正を拒否すると、代わりにさらに2つのエラーの検出を受け取ります。



前に、最小距離が1.2、3、または4の場合に条件を満たすコードを開発する方法を示しました。最小距離が大きいコードは簡単に記述できません。この方向に進むことはありません。 コード距離がどれだけ大きいかについての上限を見つけるのは簡単です。 明らかに、半径kの球内の点の数は（C（n、k）は二項係数です）







したがって、空間全体の体積2 ^ nを球の体積で除算すると、商は分離した球の数の上位の推定値になります。 対応するスペースのコードポイント。 追加のエラー検出を取得するには、以前と同様に完全なパリティチェックを追加し、最小距離を2k + 1から2k + 2に増やします（最小距離の2つのポイントは同じパリティを持つため、最小距離を1増やします）



私たちが今いる場所を要約しましょう。 コードを適切に構築することで、信頼性の低いパーツのシステムを作成し、はるかに信頼性の高いマシンを取得できることがわかります。このレベルのエラー修正を備えたコンピューターを作成する場合、計算速度のコストは調べませんでしたが、この機器にいくら支払う必要があるかがわかります。 しかし、私は以前にもう1つの利点、つまり操作中のメンテナンスについて言及しました。もう一度思い出したいと思います。 より洗練された機器、そして私たちが明らかにこの方向に進んでいると、メンテナンスがより緊急になります。エラー修正コードは、機器が（おそらく）正しい答えを与えるだけでなく、スキルの低い人でも正常にサービスを受けることができることを意味します



私たちの社会では、エラー検出コードとエラー修正コードの使用が絶えず増えています。 遠方の惑星に送信された宇宙船からメッセージを送信するとき、私たちはしばしば20ワット以下の電力（おそらく5ワット）を持ち、1つのメッセージブロックで数百のエラーを修正するコードを使用します-修正はもちろん地球上で行われます。 上記の状況または「意図的な輻輳」の場合のようにノイズを克服する準備ができていない場合、このようなコードはこの状況で唯一の既知の方法です。



1961年の夏の終わりに、教授の休暇で、私はカリフォルニア州スタンフォードからニュージャージーのベル電話研究所まで全国を走りました。 私はイリノイ州モリスに停止を計画しました。そこでは、電話会社が最初の電子電話交換機を設置していましたが、これは実験的ではありませんでした。 ステーションがハミングコードを積極的に使用していることは知っていました。もちろん、招待されました。 これほど簡単にインストールできることはなかったと言われました。 「もちろん、それは私が過去10年間説教してきたことです。」 初期セットアップ中にすべてのモジュールがインストールされ、正常に動作している場合（そして、ある意味でこれは自己チェックと調整によるものであることがわかります）、何か問題が発生した場合は次のステップに進みます。機器がそれについて教えてくれます！ 初期インストールの容易さとその後のメンテナンスは、肉眼で簡単に見ることができました！ 誇張することはできません。エラーを修正すると、操作中に正しい結果が得られるだけでなく、正しく適用されると、現場でのインストールとメンテナンスが大幅に容易になります。 そして、機器が高度になるほど、これらのことはより重要になります！



この章の別の部分を参照したいと思います。エラー訂正コードの検出の各段階で私が遭遇したことの多くと、私がやったことを注意深く話した。これには2つの理由があります。まず第一に、私はあなたに正直になり、パスツールのルール「幸運の笑顔は準備ができている」に従って、単に成功のために自分自身を準備するだけで成功することを簡単に示したいと思いました。はい、発見には幸運の要素がありました。しかし、ほとんど同じ状況で他の多くの人々がいました、そして、彼らはそれをしませんでした！なんで 幸運にも、確かに、私は自分の身の回りのことを理解する準備をしました-私の周りの他の人たちよりも、起こったときに現象に反応し、表面の下に隠されたものについて深く考えないでください。



私は今あなたに挑戦します。私がいくつかのページに書き留めたものは、会社での私の職務の通常の遂行時に、主に労働者を中心に、合計約3〜6ヶ月にわたって行われました。 （特許の公開は1年以上遅れました）。私の代わりに、彼はこれをやっていなかったと言うことができますか？はい、あなたは私がそれをするのと同じくらい能力がありました-あなたがそこにいて、あなたも準備ができていたなら！



もちろん、あなたの人生を生きて、あなたは知りません何を準備するか-重要なことを成し遂げ、「科学のドアマン」としてあなたの人生全体を費やしたくない、または他に何をするのか。もちろん、運は重要な役割を果たします。しかし、私が見る限り、人生はあなたに大きな何かをする多くの機会を与えます（自分でそれを定義します）、訓練された人は通常1回以上成功し、準備のできていない人はほとんど毎回失敗します。



上記の意見は、この経験に基づいているのではなく、単に私自身の出来事に基づいているのではなく、多くの偉大な科学者の生活を研究した結果です。私は科学者になりたかったので、彼らを研究しました。そして、私がいた場所で起こった発見を研究し、これをした人々に質問をしました。この意見も常識に基づいています。あなたは自分自身で大きな成果の達成スタイルを成長させ、その後、機会が見つかると、行動の最大の急勾配にほぼ自動的に反応します。適切な方法で考え、行動するように訓練しました。



言及する必要のある厄介な論文が1つありますが、時代において偉大であるということは、その後の数年間で明らかにする必要があるものではないということです。。したがって、将来の素晴らしい成果に備えて自分自身を準備する際に（そして、その機会はあなたが思うよりも一般的で達成しやすいです、これはあなたの鼻の下で起こるとしばしば素晴らしい成果を認識しないためです）、あなたはあなたがいる未来の性質について考える必要があります生きるために。過去は部分的なガイドであり、歴史以外にあなたが持っている唯一のものはあなた自身の想像力の絶え間ない使用です。繰り返しますが、ランダムな決定のランダムな検索は、あなたの未来がどうあるべきかというあなた自身のビジョンで下された決定に関する限り、あなたをどこにも連れて行きません。



私は両方ともあなたに素晴らしい方法を教え、示しました。今、あなたはこれをしない理由はありません！



継続するには...



誰が本の翻訳、レイアウト、出版を手伝いたいのか-個人のメールまたはメールで書くmagisterludi2016@yandex.ru



ちなみに、私たちはまた別のクールな本の翻訳を開始しました- 「The Dream Machine：The History of the Computer Revolution」 ）