Conversation

冗長2進加算器は、冗長な2進表現、すなわち桁集合として{-1, 0, 1}を採用する。入力2つを冗長2進数だとして（普通の2進数は冗長2進数）、まず中間和と中間けた上げを計算し（ステップ1）その次にそれらを足し合わせて最終的な冗長2進表現の和を計算する（ステップ2）。この方法のキモは、ステップ1をうまく構成することでステップ2で桁上げをなくすことができることである。ステップ1は各桁独立に計算できるので、結果効率的に計算できる。もちろん結果を通常の2新表現に直すには桁上げが伝播する減算器を使用する必要があるので、単純な加算に用いるのは非効率。代わりに、乗算器の部分和の計算において、二分木状に足し合わせるようにして使い、最後に一度だけ（高速な）桁上げ加算を行う。これによって乗算器全体の回路段数はlog nに比例し素子数はn^2になる。

要するに部分和の計算を桁上げ伝播なしに行えるっちゅーことだな。桁上げ保存加算とアイデアは似てる気がする。