2014年07月20日の日記です


BCD (二進化十進)とは  2014-07-20 13:02:46  コンピュータ

NOP 命令の話を書いたときに、IBM 702 が出てきました。

「BCDを使った10進計算機だった」と書いたところ、ツイッターで思わぬ反響がありました。


電卓なんかは内部で 10進の計算をしている、と書いてある書籍があったが、デジタル回路でどうやって10進計算をしているのか不思議だった、とのこと。


あーなるほど。ここら辺微妙な技術ですね。

2進数がわかる、というのはそれなりにコンピューターに詳しい人だと思いますが、その2進数で10進の計算をする、という話題は、さらにプログラムができる人でないとわからない。


古いコンピューターでは BCD はよく使われた技術なのですが、今ではあまりお目にかかることはありません。

2進数を10進数に変換するのが「当たり前」の技術になったためでもありますが、昔はこの変換も大変で、10進数で結果が欲しいのであれば、最初から 10進数で計算する、というのは悪くないアイディアでした。



2進数を10進数に変換する、というのが当時どれほど大変だったことか、僕が良く挙げる本ですが「ハッカーズ」に書かれています。(第1部 真のハッカーたち 第2章 ハッカー倫理 「芸術や美をコンピューターで作り出すことは可能である」より)


ある時、TX-0 で二進数を十進数に直して表示するルーチンを作る競争が始まります。競争は自然に始まったものですが、誰もが使う基本的なルーチンを少しでも短くできるように、多くの人が知恵を競い合うようになります。

最初は百命令もあったルーチンは、参加者の努力で50命令ちょっとまで削られます。しかし、その後はなかなか進みません。

50命令の壁…誰もがそう感じ、これ以上は1命令たりとも削れないのではないか、という雰囲気が、皆の間に広まります。

その後、寡黙なハッカー、ジェンソンのチャレンジが始まります。彼は誰にも相談せずにアルゴリズムを根本から考え直し、絶妙なテクニックを駆使し、それまでの誰もが思いもつかなかった方法でプログラムを短くするのです。


以下引用。


その内容がようやくハッカー仲間に明らかになったのは、ジェンソンのプログラムが掲示板に張り出されたときだった。十進法プリント・ルーチンを限界まで切り詰めたことをみんなに知らせる彼らしいやり方と言える。


「命令数46」


コードを見つめるみんなの口があんぐりと開いた。マージ・ソーンダースは、その後幾日か、ハッカーたちがいつになく無口だったことを覚えている。

「みんな、これが決定版だってわかったんだよ」と、ボブ・ソーンダースは後に語った。「ついに解脱というわけさ」


今なら2進数を10進数に変換するのは当然の基幹技術で、高級言語では意識することもありませんし、アセンブラでも簡単にできるように命令が揃えられています。


しかし、それ以前は、こんな苦労をして2進数を10進数に変換するか、最初から BCD で計算するかのどちらかだったのです。




さて、BCD の話。


1bit は、 0 か 1 かの2つの状態を表せます。

ここでの足し算は、4種類しかありません。


0+0 = 0

0+1 = 1

1+0 = 1

1+1 = 10


最後だけ、ちょっと特別。繰り上がりが入っているからです。

もし結果も 1bit なら、上の桁は無くなって答えは 0 です。(XOR:排他的論理和、と呼ばれる状態)


繰り上がりは上の桁に足される、と考えれば、何桁に増えようとも、この4つのパターンの組み合わせだけで計算ができます。

これが、2進法計算の原理。


2進法が 2bit なら 2*2 で4種類の状態を表現できます。(00 01 10 11 の4つ)

3bit なら 8 種類、4bit なら 16 種類の状態となります。

10進数一桁(0~9の10種類の状態)を表すのに、3bit では足りないが 4bit なら十分であるとわかります。


そこで、4bit を単位として 10進数を表現することを、BCD と呼びます。

BCD は、Binary Coded Decimalの略。2進数に変換された10進数、という意味合いで、日本語訳は2進化10進。


0000 は 0 。0001 は 1 、0010 は 2 。ここら辺は普通に2進法と10進法が一致します。

1000 は 8 で 1001 は 9 。


この次が重要で、普通に2進数で数えていれば、 1010 になります。(16進数では A と記述される)

でも、2進化10進では繰り上がりが生じて、1 0000 になります。9の次は 10 、という表現です。


足し算も、1bit 単位では2進数と変わりません。でも、計算後に 4bit 単位で結果を見直し、9を超えたら繰り上がって、1の位だけ残すようにします。


#実際にはいろいろややこしいが、特定条件になった時に6を足せばよい。この6は、10進と16進の差分。



そういう回路が組んである場合もあるし、計算後に補正する、なんて面倒を無くすために、最初から足し算を九九みたいな表で持っている機械もありました。


ここまでできれば後は応用。引き算は足し算の逆だし、掛け算は九九の表を持っておけば足し算に変換できます。

(割り算が厄介なのは2進数と同じ)

これで、2進数を使ったデジタル回路で、10進数の計算ができます。


ざっくり言えば、これが BCD の原理です。




昔の BASIC だと、32768 を超えるとエラーになりました。これ、16bit では -32768~32767 しか表せなかったためです。


科学計算では非常に大きな値を扱う可能性がある一方、観測精度の問題も付きまとうため、「おおよその値」がわかれば十分なことが多いです。


だから、たとえば 16bit の範囲の値に「10 倍」とか「10000倍」とか、倍率を付けて(下駄をはかせて)計算しても構いません。

このように下駄をはかせる場合、下駄のことを「指数」と呼びます。


指数があると非常に大きな数も扱えるようになるけど、正確な計算ができるのは、やっぱり最初の 16bit の範囲だけ。これを有効桁数と言います。


現代的には、たとえば Javascript では常に倍精度実数計算をしています。倍精度実数、というのは、有効桁数が 53bit で、指数が 11bit 、符号が 1bit ということ。合計すると 65bit なのですが、ちょっとした数学マジックでごにょごにょ…っとすると、64bit 丁度に収まります。(1bit 得してる)


だから Twitter のステータス(つぶやきにつけられるID)が 53bit を超えてしまったときに騒ぎになったのは記憶に新しいです。



さて、話を戻して、この「有効桁数を持った数値を、指数で大きくして計算」は、コンピューター以前から科学分野では当たり前でした。

IBM の最初のコンピューターである 701 は科学分野向けに作られていたため、当然この方法で計算します。


しかし、これは科学分野では当たり前でも、事務会計分野ではとんでもない話です。

事務会計では、最後の1セントまでキッチリ計算できないと話にならない。桁が大きくなって有効桁数を超えました、なんていって誤差が生じるようでは困るのです。


結果として、科学計算用ほどの速度を求めない代わりに、どんなに桁数が多くても最後の1桁までキッチリ計算する正確さが求められました。

これに応じるように作られていたのが IBM 702 で、BCD を採用しています。


(言語設計上の FORTRAN と COBOL の違いでもあります。FORTRAN は科学技術用で高速性重視、COBOL は事務用で正確さ重視でした。実際、COBOL は内部表現に BCD を使用します。)


BCD の数値はメモリ上に用意され、「終端記号」が現れるまで何桁でも増やすことができました。

もちろん、計算もメモリ・メモリ間で非常に長い桁数同士で行えます。


2進数であっても、レジスタよりも長い有効桁数の計算を行う際に、メモリ上に値を持つことがあります。

このようなものを「多倍長整数演算」と呼びます。多倍長演算すると、ただでさえ厄介な「2進数から10進数への変換」が、さらに厄介になります。

その点、BCD を使った多倍長整数演算なら、10進数への変換は簡単です。IBM 702 は、そのような用途に特化してあったのです。




話は急に変わって、世界初の 1chip CPU である Intel 4004 も IBM の BCD コンピューターの流れを汲む設計でした。


もともと、Intel に「計算機用 LSIの開発」を依頼したビジコン社では、計算する内容をすべてレジスタに入れる形式を考えていたそうです。10進10桁を想定していて、36bit 必要だった、とのこと。(内部演算は2進だったのかな)


想定されていた LSI は、40pin パッケージが必要でした。

しかし、当時の Intel はメモリを作っている会社で、18pin が生産できる LSI の限界でした。


ビジコンから交渉に出向いていた嶋正利はこの技術的限界に気付かずに作りたいチップの仕様を挙げますが、どうも話がかみ合わないまま2か月が過ぎます。


ある日 Intel のテッド・ホフが「電卓なら、4bit で BCD 計算すれば十分では?」とアイディアを思いつきます。

これが、4bit CPU 誕生に結びつきます。出来上がった LSI は 16pin パッケージに収まりました。


テッドは、BCD コンピューターの IBM 1620 を使ったことがありました。

(先に書いた、「足し算も表をひいて行う」コンピューターです)

また、PDP-8 も使ったことがあり、4004 の命令などは PDP-8 の影響が強いです。


訂正 2017.8.28

当初 40pin を想定、と書いてしまいましたが、勘違いでした。


当初は 24pin で8個ほどに分割した LSI を想定。これは大規模すぎて Intel では作れない、とテッド・ホフが 4bit 計算のアイディアを持ってきます。


ところが、ホフのアイディアでは内部回路は単純化されるが、外部は 40pin にかえって大きくなってしまったそうです。

でも、アイディアが良かったので外部 pin 数を減らす工夫を考え、4004 が完成したという話。


また、「2進から10進に変換するためには高価なチップを使えない」ので、4004にはBCD命令を持たせた、という記述がありました。(計算機屋かく戦えり)


どうも、当初は内部2進数演算を想定していた、ということで間違いなさそうです。




時代が飛び回りますが、IBM 702 より古い話。

ENIAC の設計者が後に作った、世界初の「商用マシン」である UNIVAC I では、 XS-3 と呼ばれる特殊な BCD で計算を行います。


先に書いた通り、4bit では 16 の状態があり、BCD ではこのうち10個を使います。

残る状態は 6 個。これを半分にして、BCD の「上下」に3個づつ割り振る、という方法です。


簡単に言えば、2進数の 0000 を 10進数の -3 に割り当てます。

2進数の 0011 が 10進数の 0 。1100 が 9 にあたり、 1111 は 12 です。


1桁づつ計算を行うとき、「繰り上がり」や「繰り下がり」が発生します。

数値範囲には上下に幅がありますから、一旦「2進数として」上の桁を +1 -1 しても問題ありません。

(0000 を 0 とする BCD で -1 すると、 1111 になってしまいおかしくなる)


他にもメリットがあります。0111 が 4 で、1000 が 5 ですから、「最上位ビットが立っているかどうか」を見るだけで、四捨五入ができるようになります。


さらに、ビット反転するだけで「補数」が求められます。

補数とは、簡単に言えば符号が逆の数なのですが、BCD 1桁には 0~9 しかないため、「符号を逆にしたのと同じ意味になる」数を意味します。

もっと言えば、10 進数の場合「10から元の数を引いたもの」が補数です。


たとえば、0100 は 2 ですが、ビット反転して 1011 にすると 8 。

5-2 = 3 となりますが、補数を足すと 5+8 = 13。

1桁で考えると、両者とも結果が「3」となり、同じです。


ビット反転が補数になる、というのは XS-3 の利点です。


…などなど、BCD をちょっと改良しただけなのですが、メリットが沢山。

うまいこと考えたなぁ、と思います。


(実は、UNIVAC I はそれほど詳しくなくて、XS-3 は存在を知っているだけ。

 そのうち詳細を調べたいマシンの1つです)




話は戻って IBM 702。

BCD は1桁を 4bit で示す、と書きましたが、702 では 6bit で表しました。

残る 2bit を使って、数字だけでなく文字も表せます。計算専用ではなく、事務書類の作成も含めて「事務処理用」だったわけです。


この文字コード、先頭 2bit が 00 の時は、下 4bit が 0000 ~ 1001 で 0~9 を示します。BCD 数値と文字コードの 0~9 が一致しているのです。

だから、計算結果をそのまま表示することが可能でした。

(本当は少し違うけど、大まかに言えばそういうこと)



最後の桁には、「終わり」を意味するため、先頭の 2bit を特別扱いします。

符号などもここで扱いました。



現代の 8bit コードでも、下 4bit を BCD にして、上 4bit を 0011 にすると、0~9 の文字が出せます。(ASCII の場合)

この形式を「ゾーン BCD」と呼びます。頭 4bit で BCD の範囲(ゾーン)を示すから、ゾーン BCD というわけです。

最後の桁でフラグを持たせる、というのは IBM 702 の時からの伝統…とも言えなくて、処理するシステムによってマチマチ。決まっているのは頭が 0011 だということだけ。


僕が以前に Javascript で作った「開平法計算機」では、Javascript の扱える値の範囲を超えて計算をするために、多倍長演算を行っています。

…といっても、実際は数値を文字列にして、8桁づつ範囲を区切って数値化して計算しているだけ。


文字列として数値を保持して計算しているのですから、ゾーン BCD だと言えます。


先に書いた、Twitter が 53bit を超えてしまったときの対処も、「ID 数値を文字列として表現」でした。これもゾーン BCD です。




ゾーン BCD は、8bit で10進数1桁しか表せません。

8bit に 4bit の数値2桁を一緒に入れれば、もっとメモリを節約できます。

こちらは、2桁を詰め込む(packed)ため、パックド BCD と呼ばれます。


先に書いた、BCD を前提として 4bit に設計された CPU 4004 の後継機種に、8bit の 8080 があります。


8080 には、加算結果を BCD に直してくれる10進補正命令(DAA)がありました。

加算してから BCD 補正、を桁ごとに繰り返す形になりますが、CPU が最初から BCD を扱えるように設計されているのです。


8080 では加算専用だったのですが、Z80 では減算にも対応しました。

GB CPU は 8080 ベースですが、この部分は Z80 互換になってます。


6502 にも BCD 命令があります。というか、BCD 「モード」にすると、ADC と SBC (キャリー付可算と、ボロー付減算)計算命令の動作が変化して、パックド BCD を対象とするようになります。

こちらのやり方では、8080 と違っていちいち補正命令を使う必要はありません。

(実は、Z80 では6個、GB CPU では4個のフラグのうち、2個は BCD 補正命令のためだけについています。6502 にはこの無駄がありません)


ただ、僕はファミコンで 6502 を覚えたので、実際にこのモードを使ったことはありません。

ファミコンでは、回路規模削減のためにこのモードは削除されていたんですよね。


68000 にも BCD 命令があって、加算命令の名前が ABCD です。Add BCD の略、というだけなのだけど、名前に美しさを感じました。

(ABCD に意味を持たせるなんて、他には ABCD包囲陣くらいしか知らない)


その理由だけでこの命令を使いたくて、大学時代に自作したシューティングゲームでは得点を BCD で扱っています。

でも、これは失敗だった。BCD 命令は加減算と符号反転(補数を得る)しかなくて、特別な方法で敵を倒すと得点が何倍、とかの計算すら困る状態でした。


良く理解しない技術に手を出すな、という教訓ですね (^^;






同じテーマの日記(最近の一覧)

コンピュータ

関連ページ

クリストファー・レイサム・ショールズ 命日(1890)【日記 15/02/17】

IBM - SSEC

訂正・NOP命令の誕生

続・6502は遅かったのか?【日記 14/09/06】

Programming Tips

別年同日の日記

02年 衝動買い

15年 高校部活の同窓会


申し訳ありませんが、現在意見投稿をできない状態にしています


戻る
トップページへ

-- share --

17005

-- follow --




- Reverse Link -