Architecture: n-bit circuits; multiplexers

COSC 208, Introduction to Computer Systems, 2023-10-11

Announcements

• Labs will meet as usual this week
• Project 2 due Thurs, Oct 19 @ 11pm

Outline

• Warm-up
• n-bit circuits
• Multiplexer circuit

n-bit Logical Circuits

• Q1: Complete the truth-table for A > B when A and B are two bits

• How did you determine this?
  • Convert to decimal — not an option for hardware
  • Compare 1st bits, then, if necessary, compare 2nd bits — (A1 > B1) OR ((A1 == B1) AND (A0 > B0))
• What if there were 3 bits?
  • Compare 1st bits, then, if necessary, 2nd bits, then, if necessary, 3rd bits
  • (A2 > B2) OR ((A2 == B2) AND (A1 > B1)) OR ((A2 == B2) AND (A1 == B1) AND (A0 > B0))
• What do you need to know about previous bits?
  • Is some previous bit greater?
  • Are all previous bits equal?
• N-bit greater-than circuit
  • Inputs
    • Ai
    • Bi
    • Gi
    • Ei
  • Outputs — What are the formulas for these?
    • Gi: G(i+1) OR (E(i+1) AND (Ai > Bi))
    • Ei: E(i+1) AND (Ai == Bi)
  • Circuit
    
    

n-bit arithmetic circuits

• Ripple adder
  • Adder
    • Inputs – A, B, carry in
    • Outputs - sum, carry out
    • Circuit
      
  • Inputs – An, …, A1, Bn, …, B1
  • Outputs – Sn, …, S1
  • Circuit
    

Multiplexer circuit

• Semantics

    select == 1 ==> output A's value
    select == 0 ==> output B's value
  

• Truth-table

• Logical formula

    (NOT(select) AND NOT(A) AND (B)) OR
    (NOT(select) AND (A) AND (B)) OR
    (select AND (A) AND (B)) OR
    (select AND (A) AND NOT(B)) OR
  

• Simplified logical formula

    (NOT(select) AND (B)) OR (select AND (A))
  

• Circuit

• Given n selection bits, mux select between 2^n different inputs