平成 27 年度「計算機アーキテクチャ１」演習９解答例１．(1) 桁上げ飛び越し加算器、(2) 桁上げ選択加算器について、それぞれ 200 字程度で説明しなさい。 (1) 桁上げ飛び越し加算器は、順次桁上げ加算器をいくつかのブロックに分け、各ブロックに桁上げ飛び越し回路を付加したものである。各ブロックの桁上げ飛び越し回路では、桁上げ伝搬条件、すなわち、ブロック内のすべての桁で被加数と加数の一方が１で他方が０であることが成り立つかどうかを求め、条件が成立する場合、下位からの桁上げがブロックを飛び越して上位に伝搬するようにする。 (2) 桁上げ選択加算器は、順次桁上げ加算器をいくつかのブロックに分け、最下位を除く各ブロックで、順次桁上げ加算器を二組用意し、下位からの桁上げが０の場合と１の場合のそれぞれについて和と桁上げを計算しておき、下位からの桁上げによりセレクタ（マルチプレクサ）でいずれかを選択するようにしたものである。選択され確定した桁上げが、次のブロックのセレクタの制御入力になる。２．(1) 配列型乗算器、(2) Wallace 木乗算器について、それぞれ 200 字程度で説明しなさい。 (1) 配列型乗算器では、まず、すべての部分積を並列に生成する。次に、これらを順次、桁上げ保存加算で加え合わせて行く。最後に、桁上げ保存形で求まっている積を桁上げが伝搬する加算により通常の２進表現に変換する。配列型乗算器は、全加算器を２次元配列状に並べた構成になる。演算数のビット長がｎの場合、回路の段数はｎに比例し、素子数は n2 に比例する。規則正しいセル配列構造でレイアウトが容易である。 (2) Wallace 木乗算器では、まず、すべての部分積を並列に生成する。次に、これらを三つずつのグループに分け、各グループの三つの２進数を桁上げ保存加算器で合計を保存して二つの２進数に変換するという計算を全グループで並列に行い、部分積の個数を３分の２にする。この計算を部分積が二数になるまで繰り返えす。最後に、この二数を桁上げが伝搬する加算により通常の２進表現に変換する。最終加算に桁上げ先見加算器などを用いれば、演算数のビット長がｎの場合、回路の段数は log n に比例する。