Application of Boolean Algebra / Minterm and Maxterm Expansion-數位邏輯設計筆記

一定愛配王俊堯教授開放課程食用:課程連結

Application of Boolean Algebra / Minterm and Maxterm Expansion

Conversion of Sentences to Boolean Equations

Ex:

• 

Truth Table-based Logic Design

Ex:

• By “1's” Function

  1. AND every literals of the truth table that the result equals to "1" => inverse 0.
  2. OR each terms.
  3. Simplfy it.

  

  

• By “0's” Function

  1. OR every literals of the truth table that the result equals to "0" => inverse 1.
  2. AND each terms.
  3. Simplfy it.

  

  

• By f'

  • From “1's” Perspective

    1. OR every literals of the truth table that the result equals to "0" => inverse 1.
    2. AND each terms.
    3. Do Demorgan's Transformation.
    4. Simplfy it.

  • From “0's” Perspective

    1. AND every literals of the truth table that the result equals to "1" => inverse 0.
    2. OR each terms.
    3. Do Demorgan's transformation.
    4. Simplfy it.

    

    

Minterm and Maxterm Expansions

Variables vs Literals

• Variables: X, Y, Z... A, B, C.
• Literals: X, X', Y, Y'...
• Ex:
  • => 3 variables, 7 literals

Minterms vs Maxterms

Reference: link

• Minterms(最小項)

  • AND every literals in the truth table that the result equals to "1".

• Maxterms(最大項)

  • OR every literals in the truth table that the result equals to "0".

• Relations

  • ( is the complement of )

  • when

    

  • ( is the dual form of )

  • ( is the dual form of )

• Ex:

  

• Other forms of Minterm/Maxterm Expansions

  

  • Minterm

    • If exist => must be 1.

  • Maxterm

    • If does not exist => must be 1.

  • Ex:

    

  • General Form

    

  • Property

    • =>(取兩方程式交集)

    • Ex:

      

Incompletely Specified Functions

• is called "primary output".

• The output of depends on the output of .

• The primary output that does not exist in the output of can be specified as both .

• Ex:

  

  • The circuit with "don't care" is called "incomplete specified circuit".
  • The function will be specified as:

Binary Adders and Subtractors

Adder

• Half Adder

  • Without Carry-Out and Carry-In.

• Full Adder

  • With Carry-Out and Carry-In.

• Parallel Adder(Ripple Carry Adder)
  • Consists of multiple full adders.

• Binary Subtractions
  • Consists of multiple full adders.
  • Long dealy(2n delay for n-bit adder)

• Multifunctional Parallel Adder

Subtractor

• Half Subtractor

• Full Subtractor

• Parallel Subtractor
  • Consist of multiple full subtractors.

Speeding Up Integer Addition

Carry Lookahead Adder(CLA)

Reference:link

• Knowing the carry-out before doing the mathemetic.
• Delay of 4-bit adder:
  • Ripple Carry Adder:
  • Carry Lookahead Adder: =5 ### Carry Select Adder

Reference:link

• Two additions are performed in parallel.
  • One assumes the carry-in is 1
  • Another assumes it's 0.
• When the carry-in is finally known, the correct sum is selected. (has been precomputed)

Binary Multiplication