digital_logic

logic symbols

Symbol	Name	Description
\(A \land B = A \cdot B = AB\)	AND gate	true when both A and B are true
\(A \lor B = A + B\)	OR gate	true when either A or B is true
\(\lnot A = \overline{A} = A'\)	NOT gate	true when A is false
\(A \oplus B\)	XOR gate	true when A and B differ
\(A \equiv B\)	XNOR gate	true when A and B are the same

logic gates representation

• mux gate
  • \(Y = S \cdot D1 + \overline{S} \cdot D0\)
  • if S = 0, Y = D0
  • if S = 1, Y = D1

basic logic expressions

• identity laws
  • \(A + 0 = A\)
  • \(A \cdot 1 = A\)
  • \(A + 1 = 1\)
  • \(A \cdot 0 = 0\)
• idempotent laws
  • \(A + A = A\)
  • \(A \cdot A = A\)
  • \(A + \overline{A} = 1\)
  • \(A \cdot \overline{A} = 0\)
• commutative laws
  • \(A + B = B + A\)
  • \(A \cdot B = B \cdot A\)
  • \(A \oplus B = B \oplus A\)
• associative laws
  • \(A + (B + C) = (A + B) + C\)
  • \(A \cdot (B \cdot C) = (A \cdot B) \cdot C\)
  • \(A \oplus (B \oplus C) = (A \oplus B) \oplus C\)
• distributive laws
  • \(A \cdot (B + C) = A \cdot B + A \cdot C\)
  • \(A + (B \cdot C) = (A + B) \cdot (A + C)\)
  • \(A \oplus (B \cdot C) = (A \oplus B) \cdot (A \oplus C)\)
• De Morgan's laws
  • \(\overline{A + B} = \overline{A} \cdot \overline{B}\)
  • \(\overline{A \cdot B} = \overline{A} + \overline{B}\)
  • \(\overline{A \oplus B} = A \equiv B\)
• absorption laws
  • \(A + A \cdot B = A\)
  • \(A \cdot (A + B) = A\)
• complement laws
  • \(A + \overline{A} = 1\)
  • \(A \cdot \overline{A} = 0\)
• exclusive OR properties
  • \(A \oplus N = \overline{A}B + A\overline{B}\)
  • \(A \oplus 0 = A\)
  • \(A \oplus 1 = \overline{A}\)
  • \(A \oplus A = 0\)
  • \(A \oplus \overline{A} = 1\)
• exclusive nor properties
  • \(A \equiv N = AB + \overline{A}\,\overline{B}\)
  • \(A \equiv 0 = \overline{A}\)
  • \(A \equiv 1 = A\)
  • \(A \equiv A = 1\)
  • \(A \equiv \overline{A} = 0\)
• ** adder, and subtractor properties**
  • 2's complement: \(a - b = a + \overline{b} + 1 = a + (b ^ 1) + 1\)

combinational logic circuits

Karnaugh map (K-map)

• a graphical representation of truth table
• for example, 4-variable K-map:

AB\CD	00	01	11	10
00
01
11
10

• SOP: group 1s
• POS: group 0s

sum of the products (SOP)

• a logic expression consisting of ANDed terms (products) that are ORed together
• example: \(F(A,B,C) = \overline{A}BC + A\overline{B}C + AB\overline{C}\)
• assume that input is 1

product of the sums (POS)

• a logic expression consisting of ORed terms (sums) that are ANDed together
• example: \(F(A,B,C) = (A + B + \overline{C})(A + \overline{B} + C)(\overline{A} + B + C)\)
• assume that input is 0

Examples

Question: decoder boolean expressionsolution

given the following decoder, what is the boolean expression for output Y?

craft kmap for data2:

A1\A0	0	1
0	0	1
1	1	0

group 1s:

\(Y = \overline{A1}A0 + A1\overline{A0} = A1 \oplus A0\)

craft kmap for data1:

A1\A0	0	1
0	1	1
1	0	1

group 0s:

\(Y = A0 + \overline{A1}\)

craft kmap for data0:

A1\A0	0	1
0	1	0
1	0	0

group 1s:

\(Y = \overline{A1} \overline{A0}\)

---

question: reduce the muxsolution

use mux to express the following function: \(Y = AB\)

draft the kmap:

A\B	0	1
0	0	0
1	0	1

note when A is 0, it is always 0, when A is 1, it is B

therefore, we can use A as select line, D0 = 0, D1 = B

Bit operations

bit slicing

Syntax	Description
[high:low]	selects bits from high to low (inclusive)
[index]	selects a single bit at the given index
[:]	selects all bits
[start +: width]	selects width bits starting from start, count up (eg: [2 +: 3] selects [2, 3, 4])
[start -: width]	selects width bits starting from start, count down (eg: [2 -: 3] selects [2, 1, 0])

NOTE: cause error if out of bound, eg: [1 -: 3]