まず、必要なワイヤの数は、電源用を除けば、一般に、 （使用するゲートの数）×２＋（出力ビット数） となる。（notゲートを使用しないため。） １）nビットの全加算器について まず、出力ビット数＝（n＋１） １−１）高速化を行わなかった場合 nビットの全加算器を作るには、１ビットの全加算器をn個並べればよい。 １ビットの全加算器には、二個の半加算器とorゲートが必要。 半加算器は、xorゲート１つと、andゲート１つから構成される。 よって必要なゲートは全部で、 andゲート：2n orゲート :n xorゲート:2n を合わせた、5n個。 ゆえに、必要なワイヤの数は、 （５n ×２）＋（n＋１）＝１１n＋１ 本 である。 １−２）高速化を行った場合 １−２−１）桁上げ先見方式について（166ページあたりからの説明は、よく理解できなかったので、それ以前の式で、考えてみました。) c(n)の計算に必要なゲート数は、 c(n)＝Σ(i=-1→n-1)(x(i)y(i)Π(j=i+1→n-1)(x(j)+y(j))) (ただし x(-1)+y(-1)=c(0),Π(j=n→n-1)(x(j)+u(j))=1) より 1+(2(n-1)+1) + Σ(i=0→n-2)(2+(2(n-1-(i+1))+1)) + 1 =2n + (n-1)(n+1) + 1 =n^2+2n 個 よって c(1)〜c(n) を求めるのに必要なゲート数は、 Σ(i=1→n)(i^2+2i) =n(n+1)(2n+7)/6 個 今回、x(i),y(i),c(i)から、s(i)のみを求めればよいので、 s(i)=x(i)y(i)c(i) とすればよく、必要な全ゲート数は先の式に２nを加えればよい。よって必要なワイヤの数は、 (n(n+1)(2n+7)/6+2n)×２ + (n+1) ＝ n(n+1)(2n+7)/3 +5n+1 本である。 n^3 のオーダではひどいですね...。 １−２−２）桁上げ選択方式について（これも、今ひとつよく分かりません...) まず、n=2^k (kは自然数）とする。 すると、n/2ビット加算器が、３つ必要。すると、n/4ビット加算器が、それぞれに３つ必要、というようになり、結局１ビット全加算器が、 k^3 個 必要で、このために必要なゲート数は、 5(k^3) 個。 続いて、マルチプレクサは、n/2ビット出力のものが１つ、n/4ビット出力のものが、３つ必要、というように、n/2^iビット出力のものが、3^(i-1)個必要。(i=1〜k) jビット出力のマルチプレクサには、 orゲート、andゲート、nandゲートj個ずつの、合計３j 個の論理ゲートが必要。 よって全マルチプレクサで、必要なゲート数は、 nΣ(i=1→k)(3/2)^i =3n((3/2)^k-1) 個。 よって必要なワイヤの数は、 (5(k^3)+3n((3/2)^k-1)) ×2 +(n+1) = 10(k^3)+ 6n(3/2)^k -5n+1 =30log n + 6n^(2(log3-1)) -5n+1 本。 (一般のNに対しては、 nを、 (log n)-1 < log N <= log n かつ、n=2^k(kは自然数）を満たす数とすればよい。） ２）nビット加減算器について 出力ビット数＝（n＋１） ２−１）高速化を行わなかった場合 _ s/ａからの入力が１であった時に、y(1)〜y(n)の入力を反転させるため、 xorゲートがn個 １−１に加えて必要。 よって必要なワイヤの数は、 ((５n＋n) ×２)＋(n＋１)＝ １３n＋１ 本 である。 ２−２−１）桁上げ先見方式について 同様にして、 (n(n+1)(2n+7)/3 +5n+1)+2n =(n(n+1)(2n+7)/3 +7n+1) 本である。 ２−２−２）桁上げ選択方式について 同様にして、 30log N + 6N^(2(log3-1)) -3N+1 本。 ただし、Nは、 (log N)-1 < log n <= log N かつ、N=2^k(kは自然数）を満たす数。 ３）レジスタについて nビットのレジスタには、Dフリップフロップが、n個必要。 Dフリッププロップには、RSフリップフロップが２つとnandゲート（notゲートの代わりに使う）が一つ必要。 RSフリップフロップにはnandゲートが四つ必要。 結局必要な全論理ゲートは、 (４×２＋１）n ＝ ９n 個。 また、出力は、n＋１ ビットであるから、 必要なワイヤの数は、 ９n ×２ ＋ n＋１ ＝ １９n＋１ 本である。
「桁上げ先見方式」，「桁上げ選択方式」に関しては，ナイーブにやると上の レポートのようになると思われるのですが，実際は共有できるゲートがあるの で，ゲート数は小さくなります．ただ，そうすると規則性がなくなるのが問題 ですね．
レジスタに関しては，上のレポートはちょっと間違っています．教科書の図7.18 にあるように，マスタースレーブ型RSフリップフロップ（MSFF)は同期式RSフリップフロップ(RSFF)が二つとNOTゲートからなり，DフリップフロップはMSFFとNOTゲートから成るので，DフリップフロップはRSFFが二つとNOTゲート二つから成るということになります．