論理回路基礎 9. 演算回路 五島 正裕 論理回路基礎 今日の内容 演算回路 加算器 二の補数 シフト演算器 論理回路基礎 加減算器 論理回路基礎 二進数の加算 0 +) 0 0 +) 1 1 0 +) 1 0 1 +) 1 1 10 桁上げ carry 1 1 1 0 1 +) 0 1 1 0 1 1 0 1 +) 1 1 1 0 0 1 1 1 1 +) 0 1 1 0 0 和 sum 1 1 +) 1 1 1 1 0 ← 桁上げ 論理回路基礎 半加算器，全加算器 桁上げ carry 和 sum x y cout s cin x y cout s 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 1 0 0 1 0 1 0 0 1 1 1 1 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 半加算器 (half adder) 全加算器 (full adder) 論理回路基礎 全加算器 xy cin 00 01 0 1 11 xy 10 cin 1 1 1 00 0 1 01 11 1 1 1 10 1 1 s = x ^ y ^ cin cout = xy + ycin + cin x x y x cout cin y cin s 論理回路基礎 桁上げ伝搬加算器 (ripple carry adder) 桁上げ伝搬加算器 (ripple carry adder) n 個の全加算器の cin と cout を順に接続 桁上げ (carry) が下位から伝播 伝搬遅延時間：O(n) xn-1 yn-1 x1 y1 FA cn-1 x0 y0 FA cout x y s sn-1 cin cn-2 c1 c-1 = 0 FA cout x y s s1 cin c0 cout x y s s0 cin 論理回路基礎 桁上げ先見加算器 (carry-lookahead adder) 桁上げ先見加算器 (carry-lookahead adder) 桁上げを先読み 伝搬遅延時間： O(log n) xn-1 yn-1 x1 y1 x0 y0 c-1 = 0 carry lookahead generator x y s sn-1 cin x cn-2 y s s1 cin x c0 y s s0 cin 論理回路基礎 桁上げ先見器 (carry lookahead generator) ci = xy + yci-1 + ci-1 x = xiyi + (xi + yi ) ci-1 = gi + pi ci-1 gi：（下位からのキャリーに関わらず）キャリーが生成 (generate) pi：（下位からのキャリーが 1 のとき）キャリーが伝播 (propagate) 1 ? 1 1 1 ? +) 1 ? ? ? gi = 1 1 1 0 ? +) 1 ? 0 ? 1 1 1 ? +) 0 ? 0 ? pi = 1 1 ? +) 1 ? ? ? 論理回路基礎 桁上げ先見器 (carry lookahead generator) ci = xiyi + (xi ^ yi ) ci-1 = gi + pi ci-1 gi：（下位からのキャリーに関わらず）キャリーが生成 (generate) pi：（下位からのキャリーが 1 のとき）キャリーが伝播 (propagate) c3 = g3 + p3c2 = g3 + p3 (g2 + p2c1) = g3 + p3 (g2 + p2(g1 + p1c0)) = g3 + p3 (g2 + p2(g1 + p1(g0 + p0c−1))) = g3 + p3g2 + p3p2g1 + p3p2p1g0 + p3p2p1p0c-1 c2 = g2 + p2g1 + p2p1g0 + p2p1p0c-1 c1 = g1 + p1g0 + p1p0c-1 c0 = g0 + p0c-1 論理回路基礎 桁上げ先見器 (carry lookahead generator) g3 p3 g2 p2 g1 p1 g0 p0 c-1 P G c3 c2 c1 c0 論理回路基礎 桁上げ先見器のツリー接続 c0 g0 p0 c15 g15 p15 GP c-1 GP c-1 GP c-1 GP c-1 c-1 GP c-1 論理回路基礎 補数表現 論理回路基礎 負の数の表現 表現される値 補数 (complement) 表現： 「上半分」を負数に充てる n 進数 n の補数 n-1 の補数 二進数 二の補数 (two’s complement) 一の補数 (one’s complement) O 元の値 論理回路基礎 補数表現 n 進数 の補数 n n から引いた値 表現される値 n-1 の補数 n-1 から引いた値 十進数 十の補数 100…0 から引いた値 九の補数 099…9 から引いた値 O 二進数 二の補数 (two’s complement) 100…0 から引いた値 一の補数 (one’s complement) 011…1 から引いた値 元の値 論理回路基礎 十進数 補数表現 0 1 2 3 4 5 6 7 8 9 表現される値 0 1 2 3 4 −4 −3 −2 −1 −0 九の補数（1桁） 補数表現 0 1 2 3 4 5 6 7 8 9 表現される値 0 1 2 3 4 −5 −4 −3 −2 −1 十の補数（1桁） 論理回路基礎 二進数 補数表現 000 001 010 011 100 101 110 111 表現される値 0 1 2 3 −3 −2 −1 −0 一の補数（3桁） 補数表現 000 001 010 011 100 101 110 111 表現される値 0 1 2 3 −4 −3 −2 −1 二の補数（3桁） 論理回路基礎 補数表現 表現される値 表現される値 00 00 O 01 元の値 10 11 一の補数 O 100 01 10 11 二の補数 元の値 論理回路基礎 二進数の補数表現 符号ビット (sign bit) 最上位桁（ビット）が符号を表す（0 が正，1 が負） 一の補数 と 二の補数 一の補数： ビット反転で得られる 計算が困難 二の補数 ビット反転後，+1 計算が容易 論理回路基礎 二の補数の加算 二の補数の加減算 基本的には，特に気にしなくてよい 符号ビットからの桁上げは無視 オーバフロー (overflow) 結果が表現できる範囲にない 符号ビットがおかしなことになる – 0+0→1 – 1+1→0 論理回路基礎 二の補数の加算 111 1 1 1 … −1 1 1 1 … −1 +) 1 1 1 0 … −2 符号ビットからの桁 上げ +) 1 11 11 0 1 1 … +3 0 1 1 … +3 0 0 1 … +1 1 0 0 … −4 +) 0 1 1 … +3 1 1 0 0 … −4 +) 1 1 0 … −2 オーバフロー 1 1 1 … −1 1 0 1 1 … +3 1 0 0 … −4 +) 1 0 0 … −4 1 0 0 0 … +0 論理回路基礎 符号なし加算 z=x+y 2 2 overflow n +1 n 2 n y O 2 n x 論理回路基礎 二の補数の加算 top view 2 n −, + overflow O −, − +, + +, − 2 n O 2 2 underflow n n−1 O −2 n−1 −2 n side view 論理回路基礎 二の補数の加算 2 overflow n +1 −1 n 2 −1 n 2 −1 O O n 2 −1 符号なし加算 符号なし加算結果を 二の補数とみなす 論理回路基礎 n -bit 二の補数の和 符号ありの値 n +1 −1 2 0 1...1 n −1 2 1 0 1...1 −1 0 0...0 符号なしの値 1 0 0...0 O 1 1...1 n −1 −2 1 0...0 1 1 0...0 1 1 1...1 論理回路基礎 二の補数の加算 overflow underflow 符号あり加算 符号なし加算結果を 二の補数とみなす 論理回路基礎 加算器による減算 入力の一方（y）を二の補数に： y の各ビットを反転 c−1 を 1 に xn-1 yn-1 x1 y1 x0 y0 sub c-1 FA cn-1 FA cout x y s sn-1 cin cn-2 c1 FA cout x y s s1 cin c0 cout x y s s0 cin 論理回路基礎 シフタ 論理回路基礎 シフト演算 シフト演算 左／右 算術／論理 論理シフト演算 (logical shift)： 左シフト（1桁）： 10100 ⇒ 01000 右シフト（1桁）： 10100 ⇒ 01010 算術シフト演算 (arithmetic shift)：符号ビットを保存 左シフト（1桁）： 10100 ⇒ 11000 右シフト（1桁）： 10100 ⇒ 11010 （ローテート） 左シフト（1桁）： 10100 ⇒ 01001 右シフト（1桁）： 10100 ⇒ 01010 論理回路基礎 算術シフト演算 n 進数，k 桁のシフト： n k 倍（左），1/n k 倍（右） 2進数，k 桁のシフト： 2 k 倍（左），1/2 k 倍（右） 粒度が小さいので，使いやすい （小さい整数）倍：算術シフト ＆ 加算 3x = 2x + x 5x = 4x + x 7x = 8x - x 論理回路基礎 バレル・シフタ x7 x6 x5 x4 x3 x2 x1 x0 shamt0 shamt1 shamt2 z7 z6 z5 z4 z3 z2 8b バレル・ローテータ z1 z0 論理回路基礎 今日のまとめ 論理回路基礎 今日のまとめ 演算回路 加減算器 シフト演算器 論理回路基礎 今後の予定 1/12 1/19 （最後） 3/ 2 試験 （9:00～10:30）
© Copyright 2024 ExpyDoc
