fc2ブログ

2009-8 第3問 (5)

X = { xi }, Y = { yi }, Z = { zi }, Z = X + Y とすると、

z0 = x0 ∧ y0
z1 = x1 ∧ y0 ⊕ x0 ∧ y1
z2 = x2 ∧ y0 ⊕ x1 ∧ y1 ⊕ x0 ∧ y2 ⊕ x0 ∧ x1 ∧ y0 ∧ y1
...

のように、任意のiに対してziはx0,...,xi-1とy0,...,yi-1で表せる。

各論理積の計算は並列的に計算可能であり、それぞれの計算コストはO(logN)
排他的論理和の計算コストもO(logN)なので、全体の計算コストはO(logN)

2009-8 第3問 (4)

 

2009-8 第3問 (3)

 


2009-8 第3問 (2)

 

2009-8 第3問 (1)

半加算器
XYZC0
0000
1010
0110
1101

半加算器

全加算器
XYCIZCO
00000
10010
01010
00110
11001
10101
01101
11111




プロフィール

phenan

Author:phenan
東大創造情報学専攻を受験予定の学生

最新記事
最新コメント
最新トラックバック
月別アーカイブ
カテゴリ
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QR