Basic Terminology

• Before proceeding with the text topic (combinational logic circuits), we have to introduce a few basic terminologies that we will need:

  • Literal — The appearance of a variable or its complement (i.e. $A$ and $\bar{A}$). Each appearance of a variable or its complement is counted.
    • One measurement of the complexity of a Boolean expression is the number of literals
  • Product term — One or more literals connected by AND operation.
    • A single literal is also a product term

  

  • Standard product term or minterm — A product term that includes each variable of the problem, either uncomplemented or complemented. (ก็คือพจน์นั้นต้องมีทุก Variable ที่อยู่ใน Problem)
    • For example, if an expression contains 4 variables ($A,B,C,D$) then $AB\bar{C}D$ and $\bar{A}B\bar{C}\bar{D}$ are minterms
    • but $\bar{A}B\bar{D}$ is not.
    • Minterms are often referred to by number, obtained from converting the binary number in the input row of the truth table to its decimal value. (เริ่มที่ 0 ไปเรื่อย ๆ)

• The concept of minterms is illustrated for two-variable ($A, B$) and three-variable ($A,B,C$) expressions below:
  

• The following minterm notations are commonly used to express the truth table with two variables $A$ and $B$, where it is assumed that there are 1s at the three rows in the output column that correspond to the minterm numbers 1, 2, and 3:

  $$X(A,B)=\bar{A}B+A\bar{B}+AB=m_1+m_2+m_3=\sum m(1,2,3)$$

Truth Table to SOP Boolean Expression

จำไว้ว่าเราใช้ SOP ในการเข้ามหาลัย ดังนั้นอันนี้คือ Default ปกติสุด

• Boolean expressions and truth tables are common methods for describing how a logic circuit operates. It is therefore important to know how to convert information between these two formats.
• Consider the following two-variable truth table of the OR gate:
  

  Idea อยู่ตรงที่ว่า เรารู้ว่าอันนี้มันเป็น OR Gate เพราะมันเขียน บอกอยู่นี่ไง $X=A+B$ แต่ถ้าสมมติว่าเราไม่รู้ แล้วอยากจะได้สมการ อยากต่อไอ่เจ้าตัวนี้ โดยป้อน Input ตามนี้ แล้ว Output ตามนี้ ก็เลยต้องใช้ Minterm (ดูตรงที่ Output เป็น 1 แล้วเอามา OR กัน)

• Each row of the truth table corresponds to a product term. A sum of products (SOP) expression is formed by ORing those minterms corresponding to rows of the truth table for which the function or output is 1. $$X=\sum m(1,2,3)=\bar{A}B+A\bar{B}+AB=A+B$$

Truth Table to POS Boolean Expression

• To obtain a Boolean expression in the product of sums (POS) form, it is convenient to use the fact that if a function is in the SOP form, then its complement is in the POS form (duality principle).
• Consider the following truth table. Begin by constructing a new column for the complement of the output.
  

  อันนี้คือเราจะมีอีกแถวเพิ่มขึ้นมาเป็น $\bar{X}$ แล้วก็ดู 1 — จริง ๆ ก็ดูที่เป็น 0 นั่นแหละสำหรับ POS แต่อันนี้ใช้วิธีการดู Minterm เหมือนเดิม เลยต้องมีอีกแถวเพิ่มขึ้นมา

• From the minterms, find the SOP expression of the complement variable. $$\bar{X}=\bar{A}\bar{B}\bar{C}+AB\bar{C}+ABC$$
  • Use the involution and De Morgan’s laws to obtain the output variable as a POS Boolean expression. ==(คนผิดเยอะมาก เราต้องหา $X$ ไม่ใช่ $\bar{X}$ นะจ๊ะะ!!)== $$\begin{aligned} X=&\bar{\bar{X}}\\ =& \overline{\bar{A}\bar{B}\bar{C}+AB\bar{C}+ABC}\\ =&(A+B+C)(\bar{A}+\bar{B}+C)(\bar{A}+\bar{B}+\bar{C}) \end{aligned}$$

Boolean Expression to Truth Table

เราทำจาก Table มาเป็น สมการแล้ว ตอนนี้ถ้าสมมติว่าเรามีสมการแล้วอยากแปลงกลับเป็น Table ล่ะ? ทำยังไงดีน้อออออ

• A reverse procedure can be used to easily convert an SOP Boolean expression into a truth table.
  • Each minterm corresponds to exactly one row in the truth table where the output is 1.
  • Any non-standard product term will produce more than one row in the truth table where the output is 1.
  • All other rows will be zero.
• Consider the following 3-variable SOP Boolean expression:
  
  • Notice that the last term is a non-standard product term where $A$ and $B$ must be equal to 1. However, the third variable $C$ is unspecified and therefore can be either 0 or 1. Thus, it corresponds to both minterms!! (เห็นป้ะ หลังสุดเป็นอะไรก็ได้ 110, 111 ก็ใส่ 1 ให้ทั้งสองไปเลยสิ)
• The resulting truth table is determined as:
  

  ง่ายมากเห็นมั้ย ได้ตารางกลับมาจาก Boolean expression ละ หู้ววววเจ๋ง!

• When dealing with a POS Boolean expression, follow these additional steps:
  • Use the involution and De Morgan’s laws to obtain the complement of the expression in SOP form.
  • Perform the above procedures to obtain the truth table of the complement of the output variable.
  • Invert all values in the truth table of the complement to obtain the actual output.

  อันนี้ต้องระวังนิดนึง เวลาได้สมการมาเป็นแบบ POS คือใส่ NOT ทั้งสมการ แล้วแปลงกลับเป็น SOP ก่อน: จะได้กลับมาเป็น $\bar{X}$ นะ แล้วใส่ตารางต้องระวัง จะเพิ่ม Column นึงเป็น $\bar{X}$ ก่อนก็ได้ แล้วใส่ 1 นะ!

Combinational logic Analysis

#NotOnTheExam

• Combinational logic or combinatorial logic is a type of digital logic implemented by Boolean circuits in which the output is a pure function of the present input only (with no memory or storage of information).

  ก็บอกแค่ไม่ได้มีหน่วยความจำอะไรนะ Output ได้มาจาก Input ล้วน ๆ ถ้าการให้มันจำค่าจะไปอยู่ที่ 08 Latches and Flip-Flops (Sequential Logic) (หลัง Midterm)

• Basic combinational logic circuits include:
  • AND-OR logic
  • AND-OR-Invert logic.
  • Exclusive-OR logic.
  • Exclusive-NOR logic.
• Examples of digital circuits constructed using combinational logic include: เดี๋ยวได้เรียนบางตัวอีกทีใน 07 Applications of Combinational Logic
  • Arithmetic logic unit (ALU).
  • Half and full adders.
  • Half and full subtractors.
  • Multiplexers and demultiplexers.
  • Encoders and decoders.

AND-OR Logic

• Any SOP expression can be implemented using an AND gate for each product term and one OR gate for summing all of the product terms.

  กล่าวไว้ว่า SOP expression ทั่วโลกเนี่ย ทุกอย่างสามารถใช้แค่ AND และ OR เอามายำ ๆ กันแล้วได้แบบนั้นได้ ก็แน่อยู่แล้วสิ เพราะว่า ในแต่ละ Product Term ก็เอามา AND กัน แล้วแต่ละ Product Term ก็เอามา OR กัน

• This is called AND-OR logic and is the basic form for realizing standard Boolean functions.

AND-OR-Invert Logic

• When the output of an AND-OR circuit is complemented (inverted), it results in an AND-OR-Invert (AOI) circuit, which can be used to implement any POS expressions.
  

XOR Logic

XNOR Logic

Gate Conversions (NOT)

Universal Gates

มาถึงช่วงที่ออกสอบกันแล้วท่านผู้ชม! Universal Gate มีสองตัวคือ NAND/NOR gate (very useful ✨)— using only one of these (อย่างใดอย่างนึง) you can build ANY logic gate

• Circuit จริง ๆ ก็ไม่ได้มี AND/OR/NOT ไปเรื่อยนะ ก็มีแต่ Universal Gate เนี่ยแหละ → เวลาซื้อเยอะ ๆ มันก็ได้ราคาส่งไง ดีกว่ามานั่งแยก จะซื้อ AND เท่าไหร่ OR เท่าไหร่ ถูกมั้ย!
• ข้อเสียก็คือมันจะให้ Boolean expression ที่มี Bar เยอะมาก (ด้วยความที่เป็น Not อะนะ) ทำให้อ่านยาก/ผิดง่าย → วิธีแก้คือการใช้ Twin (dual symbol)

• อาจารย์มีให้ดูด้วย

NAND Gate

• We have seen how the NAND gate can function as either a NAND or a negative-OR logic (using DeMorgan’s Theorem). This means that the ==NAND symbol and the negative-OR symbol are dual symbols.==
• When drawing a NAND logic diagram, always use the gate symbols in such a way that every connection between a gate output and a gate input is either bubble-to-bubble or nonbubble-to-nonbubble. In general ,a bubble output should not be connected to a non bubble input or vice versa in a logic diagram.

ก็คือน่าจะเข้าใจอยู่แล้ว เราจะพยายามไม่ต่อให้เกิด Bubble-to-non-bubble connection ดังนั้นถ้ามันเกิดเช่นนั้น ให้ใช้ Dual symbol ของตัวนั้น ๆ แล้วจะสามารถ Cancel Bubble ได้นะ!

• ถ้าเกิด Bubble-to-non-bubble เยอะ ๆ เราจะได้ Bar แล้วก็ต้องมาทำ De Morgan’s อีก

Universal Gate: Implementing Logic Gates Using NAND

NOR Gate

• Similarly, a NOR gate can function as either a NOR or a negative-AND logic (again using De Morgan’s Theorem), which are dual symbols.
• As with NAND logic, the dual symbols of NOR and negative-AND logic can make the NOR logic diagram easier to read and analyze.

Universal Gate: Implementing Logic Gates Using NOR