Digital Weekly Jurnal#4 :: KARNAUGH MAPS

      ในเรื่องการยุบวงจร Logic Gates นั้น ซึ่งจาก Block ที่แล้วนั้นได้รู้จักกับ Boolean Expression แล้ว ซึ่งถ้าคนที่แม่นทางคณิตศาสตร์ก็สามารถนำวิธีนี้ไปใช้ยุบวงจรได้  แต่เนื่องด้วยความซับซ้อนส่วนบุคคลนั้นจะทำให้เราได้รู้จักการยุบวงจรอีกหนึ่งวิธีซึ่งก็คือ Karnaugh Maps.

       Karnaugh Maps
           เป็นการเขียน Output ในรูปแบบตาราง Matrix เพื่อให้ดูง่ายต่อการลดรูปวงจร แถวยังรวดเร็วด้วย

       การใส่ค่า Truth Table ลง K-map.
         - มุมซ้ายของตาราง กำหนดให้เป็นช่องของ A แล้วไล่ 0 1 ลงมา
         - บนหัวตารางเป็นของช่อง B ใสเลข 0 1 เรียงไปทางขวา
          - นั่งเทียบผล Output ว่าตรงกันช่องไหน แล้วเขียนลงไป

           - จากนั้นก็ทำการ วงกลม เลข '1' (กรณีทำ SOP) หรือเลข '0' (กรณีทำ POS) ที่อยู่ติดกันเฉพาที่อยู่ในด้าน บน - ล่าง - ซ้าย - ขวา เท่านั้น (ห้ามวงเฉียงหรือวงแบบโดนัทเด็ดขาด)

       - การวงต้องวงให้ครอบคลุมจำนวน 2^n โดยไม่มีเลข '0' (กรณีทำ SOP) หรือเลข '1' (กรณีทำ POS) อยู่ด้วย

กรณีทำ K-map 3 Input.

         คราวนี้ตารางมีหน้าตาเปลี่ยนไปเป็นแบบ 2*3 แล้ว (ไม่ใช่ 3*3 นะแจ๊ะ) การเขียนตารางเพื่อไล่เขียน Output นั้น ต้องมีฝั่งใดฝั่งหนึ่งมี 2 ตัวแปร(เพื่อนรัก)อยู่ด้วยกัน และอีกฝั่งก็มีเพียงตัวแปรเดียวเหมือนเดิม จะเขียนได้เป็น (A กับ BC)หรือ(AB กับC) แบบนี้ แต่ การเรียงเลขบนตาราง K-map นั้นจะเรียงจาก 00 -> 01 -> 11 -> 10 ทำไม ?? ทำไมมันไม่เรียงตาม Binary ทำไม TT

แล้วอะไรคือ Gray Code ???

คือรหัสที่แต่ละค่าเปลี่ยนแปลงไป จะมีค่าต่างจากค่อก่อนหน้า 1 bit เสมอ 

Decimal	Binary	Gray Code
0	0000	0000
1	0001	0001
2	0010	0011
3	0011	0010
4	0100	0110
5	0101	0111

     
     เป็นรหัสตัวเลขที่ไม่เหมาะแก่การนำไปคำนวณ แต่มีข้อดีคือโอกาสเกิด error ในการส่งข้อมูลจะลดลง ซึ่ง Gray Code ถูกนำมาใช้ใน K-map เพื่อช่วยทำให้ Boolean ที่ร่วมกันมาอยู่ในช่องที่ติดกัน
                 เกร็ดความรู้เกี่ยวกับ Gray Code.

                ขั้นตอนการแปลงเลขฐานสอง เป็น รหัสเกรย์
            1.) เริ่มจากบิตแรกซึ่งถือว่ามีนัยสำคัญมากที่สุด (MSB) ดึงมาไว้เป็นบิตแรกเช่นเดิม
            2.) นำบิตแรกไปบวกกับบิตตัวที่ 2
            3.) นำบิตตัวที่ 2 ไปบวกกับบิตตัวที่ 3
            4.) นำบิตตัวที่ 3 ไปบวกกับบิตตัวที่ 4 ไปเรื่อยๆจนหมด ผลบวกที่เราได้ ก็คือ Gray Code เช่น
                   . Binary________1110011001
                   . Gray Code_____1001010101
                ขั้นตอนการแปลงจากรหัสเกรย์ เป็นเลขฐานสอง
            มีหลักคล้ายๆกับ การแปลงเลข Binary ให้เป็น Gray Code โดยเริ่มต้นจาก MSB เช่นเดียวกัน นั่นคือ
           1.) MSB ของเลข Binary จะมีค่าเหมือนกับ MSB ของ Gray Code
           2.) นำ MSB ของเลข Binary บวกกับบิตที่ 2 (นับจาก MSB) ของ Gray Code ผลบวกที่ได้คือ บิตที่ 2 ของเลข Binary
           3.) บิตที่ 2 ของเลข Binary บวกกับบิตที่ 3 ของ Gray Code ผลบวกที่ได้คือ บิตที่ 3 ของเลข Binary
           4.) บวกกันเช่นนี้ไปเรื่อยๆจนหมด เช่น
                 . Gray Code_______1110111010
                 . Binary__________10110100011
        เอาหล่ะ พอหอมปากหอมคอกับ Gray Code กับแล้ว กลับมาสู่เรื่องของ K-Map แบบ 3 input อีกครั้งเถอะนะ.

ตัวอย่างการเขียน K-map แบบ 3 Input

Hint :: คราวนี้ ตารางของเรานั้นสามารถม้วนเข้าหากันเพื่อให้วงกลมนั้นมันเชื่อมต่อกันได้ด้วยนะ

คราวนี้ลองมาเขียน K-map ของตัวอย่างข้างบนกันเถอะ

จะเห็นว่า มันช่างง่ายและดูดีกว่านั่งไล่ Boolean Expression แล้วไปเข้า Boolean Algieba ชะอีกเมื่อเปรียบเที่ยบ

 

K-map แบบ 4 ตัวแปร

              การเขียนตารางก็เหมือนแบบ 3 input แต่เป็นแบบ 4*4 และทั้งทางซ้ายและบัวบนมีตัวแปร 2 ตัวและไล่รหัส Gray Code เหมือนเดิม

 

       Hint :: คราวนี้ ตารางของเรานั้นสามารถพับเข้าหากันเพื่อให้วงกลมนั้นมันเชื่อมต่อกันได้ด้วยนะ

เช่นกันนั้น เราสามารถทำในรูปของ POS ได้เช่นกันดังที่กล่าวไว้แล้วในข้างต้น

Don't care Term.

            กรณีที่ Output ของ State หรือเงื่อนไขของ Input นั้น ไม่ส่งผลใดๆต่อการทำงานของระบบ ไม่ว่า Output นั้นจะให้ค่าเป็น '0' หรือ '1' ก็ตาม

             ลองมาดู CASE ของ Don't care term กันบ้างดีกว่า

 CASE ไฟแสดงความเร็วในการปั่นจักรยาน

 Truth Table ของวงจรแสดงไฟ

 ทำ K-Map ของแต่ละ Output

 แปลงเป็น Digital logic circuit.

 เรื่อง Don't care บางกรณีก็คิดได้ ถ้ามันส่งผลให้ได้ Gate Minimize ก็ควรนำมันไปคำนวณด้วย แต่ถ้ามันไม่ได้ช่วย ก็ควรละทิ้งมันไป อิอิ  

K - Map กรณี 5 ตัวแปร.

      - ลักษณะจะเป็นตาราง 4*8 ที่มีเส้นคั่นอยู่ตรงกลาง

      - ฝั่งหนึ่งมีตัวแปร 2 ตัว อีกฝั่งมีตัวแปร 3 ตัว เรียงรหัส gray code

      - มองโดยรวมแล้วจะเป็นเหมือนขนมชั้นที่มีแค่ 2 ชั้นเท่านั้น

K - Map 6 ตัวแปร.

      - ลักษณะจะเป็นตาราง 8*8 ที่มีเส้นคั่นอยู่ตรงระหว่างกลาง

      - มีตัวแปรฝั่งละ 3 ตัว เรียงรหัส gray code

      - มองโดยรวมแล้วจะเป็นเหมือนขนมชั้นที่มีอยู่ 4 ชั้นด้วยกัน

      - ซับซ้อนสุดๆๆ

คำแนะนำในการแปลงวงจร Logic Gate. 

    - 1-2 ตัวแปรแนะนำ Boolean Algrbra

    - 3-4 ตัวแปรแนะนำ K - Maps.

    - 5-6 ตัวแปรอาจจะ powerful ใช้ K-map หรือ Computer ก็ได้

    - มากกว่า 7 ตัวแปร ใช้ Computer คำนวณเถอะนะ...

     ในปัจจุบันการลดรูป Logic โดยใช้คอมพิวเตอร์นั้นก็กำลังนิยมมาก ซึ่งผู้พัฒนา Software นั้นก็ต้องเชี่ยวชาญเรื่องการลดวงจรโดยใช้มืออย่างถ่องแท้แน่นอน

     แนะนำโปรแกรมลดรูปวงจร Logic Friday ใช้งานง่ายเพียงแค่ปลายนิ้วกด Enter เท่านั้น ดาวน์โหลดโล้ด 

**** หมายเหตุ เรื่องเกี่ยวกับ DeMorgan's Theorems นั้นผมขอลงไว้ที่ลิ้งของ Week 3 แล้วครับ****  คลิ๊กที่ตรงนี้^^

Ref :: เกี่ยวกับ Logic Friday 

ปัญหาที่เกิดขึ้นจากบทเรียนนี้

   - เรียนครั้งแรกยังเข้าใจอยู่ครับ แต่พอขึ้น 3 Input เริ่มสับสนแล้วครับว่าจะจับประเด็นเขียนตารางลง Output อย่างไร

   - ที่สับสนยิ่งกว่านั้นคือ การวงตัวเลข 1 นั้น ที่มันสามารถพับ หรือ ม้วนได้ ยิ่งทำให้ช่วงแรกๆดูยากแต่พอได้ลองทำจริงแล้ว เข้าใจขึ้นมาบ้าง และดู output เข้าใจมากขึ้น

Digital Weekly Jurnal#3 :: CONVERTING TRUTH TABLES INTO BOOLEAN EXPRESSIONS

      การออกแบบวงจร Logic นั้น บางที่เราต้องการ Input 3 Input ขึ้นไปนั้น และให้ Output เป็น 1 โดยที่ มี Input เป็น 1 นั้น 2 Input เป็นต้นไป ซึ่งการออกแบบ Truth Tables นั้นในบางกรณี ดังเช่น

            เมื่อเรามาคำนวณ GATE ดังตัวอย่างนี้ เราจำเป็นต้องใช้ GATE จำนวน 3 Input เป็นอย่างต่ำ เพื่อให้ได้ผลลัพท์ตาม Truth Tables ดังกล่าว และในการต่อวงจรนั้น สุดท้ายแล้วเราก็ยังไม่รู้ว่าจะต้แงต่อวงจรยังไงและใช้จำนวน GATE เท่าไร อะไรบ้าง

     ซึ่งคราวนี้จะมาดูว่าเราสามารถกระทำอะไรกับตาราง Truth Table นี้ได้บ้าง

1.) Sum - of - products ( SOP )

     Sum of products คือการทำ Boolean Expression ในรูปของการบวกกันของผลคุณ เช่น ABC+AC+BC 

**เสริม Boolean Expression คือ การแปลงจาก Truth Tables ที่เราสนใจนั้น ให้อยู่ในรูปของสมการ **

กรณีนี้ เราเขียน Boolean Expression ในรูปผลคุณของ Input ใดที่ทำให้ Output เป็น "1"

จากนั้นก็เขียน Boolean Expression ให้อยู่ในรูปของ Sum of products จะได้

      จากนั้น เราก็จะได้ Logic Gates เป็นหน้าตา ดังนี้

ยังไงก็ตามวงจรนี้ก็ยังดูซับซ้อนมากต่อการ implement ดังนี้เราสามารถลดรูปลงได้ โดยใช้เทคนิคของ Boolean Algebra

           Boolean Algebra หรือ พีชคณิตของบูลีน เป็นหลักทางคณิตศาสตร์ที่ใช้วิเคราะห์ปัญหาทางตรรก ถูกคิดค้นโดยนักคณิตศาสตร์ชาวอังกฤษ ชื่อ จอร์จ บูล( George Boole ) ค่อมาก็มีผู้พัฒนาให้สมบูรณ์ขึ้นอีกหลายคน ปัจจุบันนี้เราใช้พีชคณิตของบูลีนในการออกแบบวงจร Logic Gates ซึ่งเป็นการลดความยุ่งยากของวงจรลง

        1.) เอกลักษณ์ของบูลีในการบวก

            1.1 A + 0 = A เพราะว่า ต่อให้ A=0 ผลที่ได้คือ 0 + 0 = 0 และถ้า A = 1 ผลที่ได้คือ  1 + 0 = 1 ดังนั้นจึงสรุปว่า A + 0 = A

            1.2 A + 1 = 1 เพราะว่า ต่อให้ A=0 ผลที่ได้คือ 0 + 1 = 1 และถ้า A = 1 ผลที่ได้คือ  1 + 1 = 1 ดังนั้นจึงสรุปว่า A + 1 = 1

            1.3 A + A = A เพราะว่า เราเอาขา Input มาต่อร่วมกัน เลยทำให้ A=0 ผลที่ได้คือ 0 + 0 = 0 และถ้า A = 1 ผลที่ได้คือ  1 + 1 = 1 ดังนั้นจึงสรุปว่า A + A = A

            1.4 A +`A= 1 เพราะว่า เราเอาขา Input มาต่อร่วมกันและมีขาหนึ่งที่ต่อแบบ Inverts ไว้ เลยทำให้ A=0 ผลที่ได้คือ 0 + 1 = 1 และถ้า A = 1 ผลที่ได้คือ  1 + 0 = 1 ดังนั้นจึงสรุปว่า A +`A= 1

หมายเหตุ `A คือ Inverts ของ A เช่นกัน

      2.) เอกลักษณ์ของบูลีในการคุณ

            2.1 0A = 0 เพราะว่า ต่อให้ A=0 ผลที่ได้คือ 00 = 0 และถ้า A = 1 ผลที่ได้คือ  01 = 0 ดังนั้นจึงสรุปว่า 0A = 0

            2.2 1A = A เพราะว่า ต่อให้ A=0 ผลที่ได้คือ 10 = 0 และถ้า A = 1 ผลที่ได้คือ  11 = 1 ดังนั้นจึงสรุปว่า 1A = A

            2.3 AA = A เพราะว่า เราเอาขา Input มาต่อร่วมกัน เลยทำให้ A=0 ผลที่ได้คือ 00 = 0 และถ้า A = 1 ผลที่ได้คือ  11 = 1 ดังนั้นจึงสรุปว่า AA = A

            2.4 A`A= 0 เพราะว่า เราเอาขา Input มาต่อร่วมกันและมีขาหนึ่งที่ต่อแบบ Inverts ไว้ เลยทำให้ A=0 ผลที่ได้คือ 01 = 0 และถ้า A = 1 ผลที่ได้คือ  10 = 0 ดังนั้นจึงสรุปว่า A`A= 0

หมายเหตุ `A คือ Inverts ของ A เช่นกัน

สรุป เอกลักษณ์ของบูลีนจะเป็นไปตามนี้

*** เพิ่มเติม : ถ้าเราต่อ Inverts 2 ชั้น ผลที่ได้คือ จะได้ผลลัพธ์เหมือน input ทันที

          คุณสมบัติของบูลีน

             1. การสลับที่ (Commutative law)

 A + B = B + A   และ  AB = BA

             2. กฎการจัดหมู่ (Associative law)

(A + B)+C = A+(B + C)  และ (AB)C = A(BC)

             3. กฎการกระจาย (Distributive law)

A(B + C) = AB+AC และ A+(BC) = (A+B)(A+C)

สรุป คุณสมบัติของบูลีนเป็นไปตามนี้

           การลดรูปโดยใช้กฎของบูลีน

              1. A + AB = A

                   เกิดจาก...

จะได้รูปวงจรดังนี้

              2. A + `AB = A+B

                   เกิดจาก...

จะได้รูปวงจรดังนี้

หมายเหตุ `A คือ Inverts ของ A เช่นกัน

              3. (A+B)(`A+C) = A + BC  

                   เกิดจาก...

จะได้วงจรดังรูปต่อไปนี้

สรุป การลดรูปโดยใช้กฏของบูลีนจะเป็นดังนี้

หมายเหตุ `A คือ Inverts ของ A เช่นกัน

    เกี่ยวกับ The Exclusive - OR Function (XOR)

                XOR 1 ตัว จะมีลักษณะเหมือนกับ A`B + `AB 

     ลองลดรูปวงจรโดยการใช้กฎของบูลีนกันเถอะ

            จากวงจรนี้ เราสามารถลดรูปวงจรโดยใช้บูลีนได้เป็นดังนี้

         

จะเหลือรูปวงจรเพียงแค่นี้

          อารัมภบทต่อมา เราต้องเพิ่ม Output ขึ้นมาอีก 1 หล่ะ คราวนี้เราจะทำเยี่ยงใย???

            ถ้าเห็นอย่างนี้เราคงทำ SOP อย่างแน่นอนซึ่งผลของ Boolean Expression ก็จะได้แบบนี้

         ซึ่งเราสามารถนำ Boolean Expression นี้ไปลดรูปได้ปกติแต่จะมีโอกาสผิดสูงมากเพราะมีจำนวนพจน์ถึง 6 พจน์ด้วยกัน ซึ่งมากพอสมควร ซึ่งเราจะมาเรียนรูปวิธีลดต่อไปคือ

2.) Products - of - sum ( POS )

       Products of sum  คือการทำ Boolean Expression ในรูปของการคูณกันของผลบวก เช่น (A+B+C)(A+C)(B+C) แต่คราวนี้เราจะสนใจที่ Output เป็น "0"

ซึ่งจะทำให้ได้วงจรเพิ่มเต็มเป็นดังนี้

และเช่นเดียวกันเราสามารถลดรูปวงจรนี้ได้โดยใช้ Boolean Algebra ได้เช่นกัน

       DeMorgan's theorem

     ทฤษฏีที่สำคัญอีกทฤษฎีของ Digital Logic โดยพื้นฐานแล้วมันมีไว้เพื่อแปลงรูปนิเสธของ logic เพื่อช่วยให้ง่ายต่อการคำนวณ Boolean Algebra และบทเด่นของมันคือ ยุบ bar กรณีที่มี 2 bar ขึ้นไปได้

 ตัวอย่างของ DeMorgan ในการแทนอุปกรณ์

 ตัวอย่างการใช้ DeMorgan Law.

  Ref :: http://www.electrical4u.com/de-morgans-theorem-and-demorgans-laws/

***ทิ้งทายด้วย***

ทำไม Sum (บวก) ต้องแทนด้วย OR Gates??

ทำไม Product (คูณ) ต้องแทนด้วย AND Gate??

นั่นก็เพราะ.......ตามนั้นนะ

Class Work

1.) ทำการต่อวงจร SOP ดังตัวอย่างวงจรข้างบน พบว่า สายเยอะมาก และการทดลองเป็นไปด้วยดี

2.) ทำการเพิ่มวงจรในส่วนของ POS ลงไปด้วย ซึ่งได้ลดรูปวงจรจากตัวอย่างแล้วได้เป็น

ทำให้ได้หน้าตาวงจรออกมาเป็นดังนี้

และนี้คือผลของการต่อวงจรจริง

หน้าตาเหมือนข้างบนมากแทบแยกไม่ออก

ซึ่งผลจากการทดลองก็ได้สรุปเป็นวีดีโอเป็นที่เรียบร้อยแล้ว

ปัญหาหลักๆก็คือ

1) เราไม่มี Gate input แบบ 3 ขา ซึ่งผลตรงนี้เราก็สามารถประยุกต์ได้โดยใช้ OR Gates 2 ตัวต่อร่วมกัน                                              

2) ลองพยายมลดรูป POS โดยไม่ใช่ XOR ผลปรากฎว่า เยอะยิ่งกว่าเดิมซะอีก เลยต้องทำใจยอมใช้ XOR

**หมายเหตุ ที่ต่อวงจร POS ลง Output ที่ช่องตรวจสอบสถานะ Logic เพราะเพื่อจะดูความแตกต่างของ SOP และ POS ได้ชัดเจนยิ่งขึ้น และจากโจทย์คือ เราต้องตรวจสอบ Input ทั้งสามด้วยว่า เราป้อน Input ที่เหมือนกันหรือเปล่า ถ้าเหมือนกัน ไฟ Output สีเขียวก็ติด แต่ถ้ามี input ใดที่ต่างจากเพื่อน ไฟ output จากสีเขียวก็กลายเป็นสีแดง