除算器 その1
この記事はkivantium Advent Calendarの10日目です
昨日までで四則演算のうち3つが揃ったので今日からは最難関の割り算をやります
回復法（引き戻し法）
話を簡単にするため、まずは符号なし整数の割り算を考えます。
割り算の場合も基本の考え方は筆算です。
10進数の場合は
14
7)-----
100
7
---
30
28
----
2のように、商として取れる最大の値を推測して掛け算し、その値を引いていくことで計算を進めます。
筆算で一番難しいのは「最大の値」を推測することですが、2進数の場合は可能性が0と1しかないので注目している部分が除数より大きいか小さいかだけ調べれば商が決まります。大小比較は引き算してみてキャリーが発生しなければ大きい、発生したら小さいと確定するので、キャリーのNOTがその桁の商になります。そこでA÷Bを計算する回路として次のような設計が考えられます。
- 被除数の左側にBと同じbit数の0をつめたシフトレジスタを用意し、左から順にBのbit数ずつ取り出して、減算器に入れます。
- キャリーの否定をシフトレジスタの右側の入力として商とします。
- キャリーが0（=引くことができる）のときは差が、キャリーが1（=引くことができない）のときは元の値がシフトレジスタの左側に入るようにします。
- 1サイクルごとにシフトレジスタを左にシフトしていけば、Aのbit数と同じサイクル数でシフトレジスタで元Aがあった位置に商が入ります。
しかし、この方法ではAのbit数と同じサイクル数が必要となるため時間がかかります。また、符号なし整数の除算にも対応できません。そこで次回はこれを克服する非回復法について説明します。
今日は帰宅即おふとんしてたので内容が短いです‥‥