見本 PDF特集

特集

らくらく！ エラー訂正符号入門

第 8 章 ハミングの最初の論文に難解な数学は登場しない“Error Detecting and Error
Correcting Codes” 抄訳
R. W. ハミング 著 / 中本 伸一 訳
R. W. Hamming/Shinichi Nakamoto

本 章 で は，1950 年 4 月 に ベ ル 研（ 当 時 ）の 社 内 誌
Bell System Technical Journal
BSTJ に掲載されたハミング博士の論文（1）の前半にあたる部分を掲載します．この論文はハミング符号の動作原理を解説しています．
この論文をきっかけに，様々なエラー訂正符号の誕生につながっていきました．ハミング博士の論文の内容は驚くほどわかりやすく，難解な数学は登場しません．オリジナルの才能とはそういうものなのでしょう．

§ 1 序章この論文のテーマは最終的な結果を得るまで，ただ一つのエラーも無く処理されなければならない大規模な計算機システムの検討から導かれたものです．
このすべてを完璧に処理しなければならないというテーマは，今に始まったことではありません．過去から電話局において膨大な通話を処理する中で，間違い電話を完全に無くすことはできませんでしたが，自己検査回路を使うことで，ある程度の対策が行われていました．しかし，こうした検査をすり抜けて，ごく稀に発生する間違い電話は，間違った相手に接続された顧客が不満を漏らすことがあっても，ほかの電話局の機能はすべて問題なく機能していました．
しかしディジタル計算機においては，たった 1 ビットの間違いが，すべての連続した処理を止めてしまい，完全な失敗を招くことになります．言い方を代えれば，電話局においては，お互いに関連性のない数多くの処理が並行して行われるのに対して，ディジタル計算機
では，結果が得られるまで同じ部分を何度も通過する，大変に長い道のりを通らなければなりません．
ある場所からほかの場所に情報を送信する場合，ディジタル機器は，単に数値や命令の種類を割り当てた符号を使用します．その際にはエラー検出を目的とした符号もよく使われます．例えばベル・リレー・コン2 out of 5
ピュータ内で一般的な遠隔操作に使われる 5 −2 選符号
3 out of 7や，無線電報で使用される 7 −3 選符号や，電報の最後に付加されるワード数などです．
しかし，ある状況ではエラー検出だけでは不十分で
Aberdeen Proving Groundす．例えば米軍のアバディーン性能試験場で使用されNo.32ているベル研製のリレー・コンピュータ・モデル 5 では，初期の観察において，二つのコンピュータに使用されている 8900 個のリレーが 1 日に 2 個か 3 個のエラーを起こすことが報告されています．
エラーを起こす頻度は，2 〜 3 百万回のリレー動作に対して 1 度程度です．自己診断の失敗は，エラーを検出できないことを意味します．
このコンピュータは，夜間や週末などで監視員が不在の間に連続で運転されますが，こうしたエラーにより，問題を解く半ばにして頻繁な停止を起こすことになります．最近ではリレーより高速で信頼性の高い電子式のコンピュータに移行する傾向にあります．しかし，こうした電子式でも，いったんエラーが発生すれば重大な障害が発生することに変わりありません．
このような背景から，エラー検出の次の段階であるエラー訂正に進むことが求められています．
私たちは，情報を送信する機器は，0 と 1 から構成される 2 進数を扱っていることに注目すべきです．この事実は数学的な利便性とともに，リレーの ON とOFF，フリップフロップ回路，モールス通信のドッ
トとダッシュ，穴あき紙テープのような，さまざまな通信に利用される方式との相性の良さから来ています．伝送する符号は0と1の組み合わせで表現されます．
systematic codes
この論文で扱う符号は組織符号と呼ばれています．
組織符号とは，全部がn 個の桁で構成されていて，そのうちのm 個の桁を情報伝達に使用して，残りのk（訳注：つまり n − m 個）の桁をエラー検出とエラー訂正に使う符号と定義されます．またこの定義から，R ＝redundancy
n/m で定義される冗長度R も導き出せます．冗長度Rとは，ある情報を伝達する際に必要になる最低の桁数を表します．この冗長度は本論文で扱う伝送効率を議論する際に便利な指標となります．冗長度が小さければ，それだけ伝送効率が良い符号になります．
エラー訂正技術は最近になって注目されてきました
が市場的な効果はほとんど知られていません．はっきりいえるのは，この符号を使用すると追加の符号化と復号化の装置が必要になり，上記で説明したように伝送効率も低下します．しかしこの符号は以下のような

Courtesy of Alcatel-Lucent Ⓒ［1950］Alcatel−Lucent.
All Rights Reserved.

85

用途に対して無くてはならないものになるでしょう．

このような 1 ビットのエラー・チェックはパリティa．ほぼ常時稼働する機器の，長期に渡る無人運用検査と呼ばれ，この論文でも何度か登場します．このb．たった一つのエラーがシステム全体に重大な障例で紹介したのは，偶数パリティ検査ですが，これと害を与える厳格で大規模なシステムc．ノイズの除去が不可能または経済性に見合わない伝送路での通信
このような状況はよく発生します．とくに最初の二つの例は，大規模なコンピュータを運用する際によくjamming当てはまります．また三つ目の例はジャミングが強い環境で役に立ちます．
エラー検出と訂正符号の原理は，この論文の最初の部分で説明します．
この符号を実現するための回路は，よく知られた技術を駆使すれば実現可能ですが，この問題はここでは扱いません．この論文のパートⅡでは，以下の三つの場合について，どうやって最低の冗長度を持つ符号を特定して構築するかを解説します．
a．1 ビットのエラー検出が可能な符号b．1 ビットのエラー訂正が可能な符号
c．1 ビットのエラー訂正に加えて 2 ビットのエラー検出が可能な符号パートⅡでは，パートⅠで示したこれらの符号が最良であることを仮定して，その一般的な理論とその証明を解説します．

パートⅠ 特別な符号§2

1 ビットのエラー検出が可能な符号

まず n ビットの桁を持つ 1 ビットのエラーを検出可能な符号を考えます．この符号は最初の n − 1 ビットに情報を格納します．
最後の 1 ビットである n 番目のビットには全体の 1の数が偶数になるように 0 または 1 を格納します．この符号は確実に 1 ビットのエラーを検出可能です．1ビットのエラーが全体の1の数を奇数にするからです．
この符号の冗長度R は，上記の情報伝達に使用するビット数のm がn − 1 であることから，

n1＝1＋n −1n −1となります．冗長度 R を低くする（訳注：つまり伝送効率を上げる）には，n を大きくすれば良いですが，nを大きくするとどれか 1 ビットがエラーする確率が高くなりますし，エラー検出が不能になる 2 ビット・エラーの確率もまた大きくなります．例えば 1 ビットがエラーする確率を p とします．p は 1 よりもかなり小さいものと仮定します．符号長 n が長くなって，1/pに近くなると，1 ビットのエラー訂正が発生する確率は 1/e ＝ 0.3679…となり，2 ビット・エラーする確率は 1/（2e）＝ 0.1839…となります．
R＝86

は逆に奇数パリティを正常な状態とする場合もあります．さらにパリティ検査は，必ずしもすべての部分に適用する必要は無く，選択した部分だけに適用しても良いでしょう．
（訳注：その方が n が小さくなるためエラーに強くなる）§3

1 ビットのエラー訂正が可能な符号1ビットのエラー訂正が可能な符号を構築するには，まず最初に全体の符号長n に対して，データ部の長さm をどう割り当てるかを考えます．
私たちは m を固定長で考えていましたが，その具体的な長さについては，後に決定することにします．
次に残された検査部の長さk を考えます．このk の値は，選択されたビット位置に対するパリティ検査の方法を基にして決定されるべきです．
実際にエラーがあるかないかわからない符号を受信した場合を想像します．その符号にk 回のパリティ検査を順に行って，その結果が正しければ 0 を書き込み，間違っていれば 1 を書き込むとします．このようにして k 回のパリティ検査の判定結果によって書かれた k個の 0 と 1 の並びは，2 進数の値だとみなすことがでchecking number
きます．この値のことを検査値と呼ぶことにします．
この検査値には，もしエラーが無ければ 0 になって欲しいですし，もしエラーがあれば，そのビット位置を表してくれれば大変好都合です．それゆえに検査値は最低でも m ＋ k ＋ 1（ 訳注：データ部のビット長＋検査部のビット長＋エラーなし状態）の，異なった状態を表現できる能力が必要になります．
2 k ≧m ＋k ＋ 1
この式を満たす k が，k の条件となります．ここでn ＝ m ＋ k なので k ＝ n − m となり，これを両辺に代入すると，
2（n −m ）≧m ＋（n −m ）＋ 12n≧n ＋ 12m
両辺の逆数をとると，2m12nm≦≦となり，22nn ＋1n ＋1を得ます．この式から得られる，n と m と k の取り得る値を一覧表にしたのが表 1 です．この表を見ると全体の符号長のn から求められるデータ部のm の最大値，または同じことですが，m から求められるn の最小値が求められます．
それではどのビット位置にパリティ検査を行うかを決めていきましょう．検査値は，右側から左側に 1 桁ずつ，パリティ検査の結果に基づいて対応する 0 か 1No.32