רק פוני אחד לטריק – על מימוש שערים לוגיים

בשתי רשימות קודמות סיפרתי על האלגברה הבוליאנית ועל איך ניתן לעשות בה שימוש באלקטרוניקה דיגיטלית. ערכי המשתנים באלגברה בוליאנית, 'שקר' או 'אמת', 'אפס' או 'אחד', מתורגמים באלקטרוניקה למתח גבוה או מתח נמוך. בעזרת הפעולות הבוליאניות 'וגם' ו-'או' ניתן לתכנן מעגל שיקבל החלטות נכונות לפי חוקים ידועים מראש, למשל ידליק נורה אך ורק אם התנאים הנכונים מתקיימים.

הפעם אני רוצה לספר על איך זה קורה באמת. כיצד ניתן לממש את השערים הלוגיים, כלומר את הפעולות 'וגם' ו-'או' ופעולות נוספות.

***

הרכיב הבסיסי שעומד מאחורי כל השערים הלוגיים 'בעולם האמיתי' הוא המתג.

חישבו על מתג כעל ברז במרכז צינור מים. בהנחה שאני דוחף בלחץ מים דרך הצינור, המים נשפכים החוצה אם הברז פתוח ולא נשפכים אם הברז סגור. המתג עובד באופן דומה. אם המתג פתוח, זרם חשמלי יעבור דרכו ללא הפרעה ואם הוא סגור הזרם אינו עובר. בעגה נאמר שבאופן אידיאלי כאשר המתג פתוח הרכיב הוא 'קצר' במעגל וכאשר הוא סגור הרכיב הוא 'נתק' במעגל.

ישנן מספר דרכים לבנות מתג עבור מעגלים חשמליים בזרם נמוך (למשל בשבבים למחשבים). בעבר היו משתמשים בשפופרות ואקום והיום אנחנו משתמשים בטרנזיסטורים שהם רכיבים שבנויים מחומרים שנקראים 'מוליכים למחצה' ועל המצאתם הוענק פרס נובל בפיזיקה בשנת 1956.

כדי לא להאריך היכן שיש לקצר ולא לקצר היכן שיש להאריך לא אעסוק ברשימה זאת בבפנוכו של הטרנזיסטור. אני רק אציין שלרכיב יש שלושה טרמינלים, כלומר שלוש נקודות חיבור למעגל. נקודה אחת נקראת 'gate' והיא הברז. שתי הנקודות האחרות נקראות 'source' ו-'drain' והן שני צדדי הצינור. מתח מתאים בחיבור ה-gate יפתח את הרכיב לזרם חשמלי.

מכאן ואילך אני פשוט אניח שיש ברשותי את הרכיב הדרוש.

איור 1: סימון במעגל חשמלי לטרנזיסטור. G מסמן את כניסת ה-Gate, S את כניסת ה-Source ו-D את כניסת ה-Drain. אם נחבר מתח חשמלי בין S ל-D ונדאג למתח ב-G שמספיק לפתיחתו של הטרנזיסטור אז זרם חשמלי יזרום מ-S ל-D.

***

כעת, כשיש לנו את אבן הבסיס, המתג, נשתמש בו כדי לממש את השער הפשוט ביותר: 'המהפך' (inverter). ברשימה הקודמת הראיתי שבתכנון המעגלים הדיגיטליים יש צורך ברכיב שהופך גבוה לנמוך ונמוך לגבוה. השער הלוגי הזה גורם להיפוך של האות החשמלי ומכאן שמו.

כיצד, אם כן, נשתמש במתג כדי לקבל מהפך? נבחן את החיבור הבא:

איור 2: מעגל מהפך. המקור לאיור: ויקיפדיה (עם תוספות שלי), לשם הועלה על יד המשתמש Fresheneesz.

כאשר המתח גבוה ב-gate של הטרנזיסטור הוא פתוח ולכן מהווה קצר, כלומר אפשר להחליף אותו בחוט מתכת. אם כן, המתח בנקודת היציאה מוכתב ישירות על ידי נקודת ההארקה שהיא בהגדרה אפס. כלומר, נכנס גבוה יוצא נמוך. לחלופין, אם מתח הכניסה נמוך אז הטרנזיסטור סגור ולכן אין זרם. כתוצאה מכך אין נפילת מתח על הנגד וניתן להחליף את הטרנזיסטור בחוט מנותק. המתח ביציאה מוכתב כעת על ידי מקור המתח העליון שערכו הלוגי הוא '1'. כלומר, נכנס נמוך יצא גבוה.

אז יש לנו מהפך.

לפני שאני עובר הלאה, אני אתעכב מעט כדי להצביע על בעיה פרקטית במהפך הזה ועל פתרון אפשרי. נניח שבאופן ממוצע בחצי מזמן פעולתו של המעגל נכנס למהפך אות גבוה ולכן הטרנזיסטור פתוח. כתוצאה, בחצי מהזמן זורם זרם במעגל דרך הנגד כך שנשלם לחברת החשמל על חימום. זאת תוצאת לוואי מאוד לא רצויה מכיוון שישנם מעגלים שבהם יש מיליוני טרנזיסטורים, ונהיה שם חם. מאוד.

בואו ונניח שיש טרנזיסטור מאוד דומה לזה שהוצג, אך הוא עובד הפוך. הוא נפתח רק אם מתח ה-gate שלו נמוך. נסמן אותו בסימון דומה אך עם נקודה ב-gate. נבחן את החיבור הבא:

איור 3: מעגל מהפך בטכנולוגית CMOS. המקור לאיור: ויקיפדיה (עם תוספות שלי), לשם הועלה על ידי המשתמש inductiveload.

מתח גבוה יגרום לפתיחת הטרנזיסטור התחתון וסגירת העליון, כך שהיציאה נמוכה. מתח נמוך יגרום לפתיחת הטרנזיסטור העליון וסגירת התחתון ולכן היציאה גבוהה. היתרון במעגל זה הוא שברוב זמן פעולתו לא זורם בו זרם, בזבוז ההספק עליו נמוך באופן משמעותי ולכן הוא מתחמם פחות. החיסרון הוא שיש בו צורך בעוד טרנזיסטור ובעוד שטח על גבי המעגל המודפס, וזה עולה כסף. צורת המהפך הזאת היא חלק מטכנולוגיה בסיסית של מעגלים שנקראת CMOS.

***

בואו וננסה שער יותר מורכב.

ה-'nand' הוא שער שמורכב מ-'וגם' שאחריו מהפך (not-and). טבלת האמת שלו היא:

נבחן את המעגל הבא:

איור 4: מעגל nand. המקור לאיור: ויקיפדיה (עם תוספות שלי), לשם הועלה על יד המשתמש Fresheneesz.

נבחין שזרם במעגל יזרום רק אם שני המתגים פתוחים ובמקרה הזה היציאה נקבעת על ידי ההארקה, כלומר יציאה נמוכה. כל מקרה אחר נקבל יציאה גבוהה וזה בדיוק מה שנדרש לפי הטבלה.

ניתן לממש את ה-nand, כמובן, גם בטכנולוגית CMOS. אני ממליץ לכם לנסות לשרטט את הפתרון בעצמכם.

אז יש לנו nand.

וזהו, סיימנו.

מה? למה?

***

להלן שלושה תרגילים קצרים באלגברה בוליאנית. מי שלא מכיר או לא זוכר יכול לעיין ברשימה קודמת בנושא.

התרגיל הראשון מראה שניתן ליצר מהפך משער nand. התרגיל השני מראה שניתן לייצר שער 'וגם' באמצעות שערי nand ומהפך. התרגיל השלישי מראה שניתן לייצר שער 'או' באמצעות שער nand ושני מהפכים.

מסקנה: ניתן לממש את כל השערים הלוגיים באמצעות צירופים של שערי nand בלבד.

זה נקרא בעגה Functional completeness.

היתרון: צריך רק פוני אחד לטריק, רק חותמת אחת, רק ראש אחד במדפסת וכולי.

החיסרון: יש צורך בהרבה יותר טרנזיסטורים.

סוף.

הקשר בין השעון המעורר שלי לאלגברה בוליאנית

ברשימה קודמת הצגתי את האלגברה הבוליאנית, בה כל משתנה יכול לקבל שני ערכים בלבד: שקר או אמת, 0 או 1. הפעולות האפשריות היחידות בין משתנים הן פעולת 'או' ופעולת 'וגם'. בסיום הרשימה ציינתי ששני השימושים הידועים ביותר לאלגברה הזאת הם לוגיקה ואלקטרוניקה דיגיטלית.

"איך אלגברה בוליאנית קשורה לאלקטרוניקה?" אתם שואלים. קחו דוגמה.

תמונה 1: תצוגה של שעון דיגיטלי.

***

זקני השבט מבינכם אולי זוכרים שלפני המסכים החכמים היה מקובל לקרוא לשעון 'דיגיטלי' אם במקום מחוגים (מה זה?) השעה היתה מוצגת בספרות. כל ספרה היתה מורכבת מ-7 נורות מלבניות שעל ידי הדלקה של חלק מהן היינו רואים ספרה בין 0 ל-9 כפי שניתן לראות באנימציה. (נקרא בעגה seven segment display).

אנימציה 2: תצוגה דיגיטלית של ספרות באמצעות 7 נורות. המקור לאנימציה: ויקיפדיה, לשם הועלתה על ידי המשתמש Artur perm.

מבחינתינו כמתכנני השעון אנחנו מעוניינים להזין מספר ושכל אחת מ-7 הנורות תדלק או תישאר כבויה כך שהמידע הנכון יוצג. כיצד 'יודעות' הנורות האם להידלק או לא?

המידע על הספרה מוזן בצורה בינארית. כדי לייצג את הספרות 0-9 יש צורך ב-4 סיביות מכיוון שכל אחת מייצגת חזקה של 2 (בדומה לייצוג עשרוני בו כל ספרה מייצגת חזקה של 10). נרצה לייצר מעגל שמקבל את 4 הסיביות הקלט ופולט 7 סיביות שקובעות ל-7 הנורות האם להידלק או להישאר כבויות.

נסמן את סיביות הקלט באותיות A,B,C ו-D. הערכים של החזקות של שתיים מסודרות כך ש-D זה 1, C זה 2, B זה 4 ו-A זה 8.

את הנורות נסמן  באותיות a עד f כאשר מקובל לשייך אותן לנורות כפי שמתואר באיור 3.

איור 3: תצוגה ב-7 נורות עם סימוני אותיות על כל נורה. המקור לחלק קטן מהאיור: ויקיפדיה, לשם הועלה על ידי המשתמש h2g2bob.

נתחיל בלתאר את כל המצבים האפשריים שאליהם נדרש המעגל. נרכז את כל האפשריות בטבלה הבאה:

כדי לוודא שהבנו את הטבלה נעבור על שתי אפשריות. עבור הספרה '0' הקלט הוא אפס בכל בחזקות של 2 וכדי להציגו כל הנורות נדלקות מלבד נורה g המרכזית..

עבור הספרה 7 הקלט הוא 1+2+4 ולכן אפס ושלושה אחדות. להצגת המספר נדרשות שלוש נורות דלוקות, העליונה והשתיים הימניות, כלומר נורות a,b ו-c.

כעת כשהבנו את מלאכת התרגום הנדרשת בין סיביות הכניסה ליציאה בואו ונתפלש בפרטים הקטנים כדי ליצור מעגל שעושה את זה.

לשם דוגמה ננתח את הדרישות עבור יציאה שתתן הוראות לנורה e. מהטבלה ניתן לראות שישנם 4 מקרים בהם הנורה דולקת (עבור הספרות: 0,2,6,8). המקרה הראשון הוא שכל סיביות הקלט באפס. נסמן זאת כך: 'A'·B'·C'·D, כאשר הגרש מסמנת משתנה שעבר היפוך ערכים, כלומר נדרשת כניסה של 0 כדי לקבל 1 מהמשתנה. במילים אחרות, אחת האפשריות עבור נורה e להידלק, כלומר ערך 1, היא שגם כניסה A נמוכה, גם B נמוכה, גם C וגם D נמוכות. ישנן עוד שלוש אפשריות. נסכם בכיתוב בוליאני:

'e= A'·B'·C'·D' +A'·B'·C·D'+ A'·B·C·D'+ A·B'·C'·D

ניתן לבנות את המעגל המתואר על ידי המשוואה הזאת. כל פעולת 'וגם' או פעולת 'או' תצריך מאיתנו מימוש של עוד שער לוגי (שמאחורי מימושו במציאות עומדים המון רכיבים אלקטרוניים) ולכן הפתרון הזה הוא בזבזני במיוחד ולא יעיל.

מבט חטוף על הביטוי מראה שיש בו המון חזרות של משתנים ולכן סביר או אפילו ודאי שניתן לקבל את אותה תוצאה בפחות שערים.

ישנן מספר שיטות למינימיזציה של ביטויים בוליאניים ומדובר בפעולות טכניות מאוד. מכיוון שאין בכוונתי להעביר כאן קורס במערכות ספרתיות אני פשוט אכתוב את התשובה שיוצאת מאלגוריתם מינימיזציה שנקרא 'מפת קרנו' ואתן לכם לבדוק ולהשתכנע שהתוצאה זהה.

'e=B'·D'+C·D

עבור פתרון זה אנחנו נדרשים לשלושה שערים בלבד (מלבד המהפכים). שימו לב שמסתבר שהכניסה A כלל אינה נחוצה עבור הפתרון!

נבדוק עבור הקלט של הספרה 0:

A=B=C=D=0

e=0'·0'+0·0'=1·1+0·1=1+0=1

כלומר, עבור הקלט של הספרה 0 הנורה e דלוקה כנדרש.

נבדוק עבור הקלט של הספרה 1:

A=0,B=0,C=0,D=1

e=0'·1'+0·1'=1·0+0·0=0+0=0

נורה e כבויה כנדרש. וכך הלאה.

ניתן להמשיך ולבדוק את כל הספרות. היו סמוכים ובטוחים שזה עובד.

האם ניתן עוד לשפר?

אם אתם זוכרים את הרשימה הקודמת, שם דנתי במשפט הדיסטריביוטיביות הראשון של האלגברה הבוליאנית. לפי משפט זה:

(A+B)·(A+C)= A+(B·C)

אם נהפוך כל סימן כפל לחיבור וכל סימן חיבור לכפל נקבל עדיין משפט נכון ולכן עבור המקרה שלנו:

(e=B'·D'+C·D'=D'·(B'+C

וכך חסכנו עוד שער באמצעות אלגברה בוליאנית.

***

מעגלים דיגיטליים נשענים על שימוש באלגברה בוליאנית ובאלגוריתמים הנסמכים עליה כדי למצוא את הדרך הטובה ביותר לממש את המעגל הדרוש. המעגל שמפענח וממיר את מתחי הכניסות למתחי היציאות הנכונים עבור הנורות נקרא בעגה מפענח בינארי (Binary decoder).

אז אני מקווה שקיבלתם איזשהו מושג איך אלגברה בוליאנית קשורה לאלקטרוניקה.

לסיום נשים לב שעד עכשיו עסקנו באבסטרקציה של עניין השערים הלוגיים למרות שדיברנו על מעגל חשמלי מוחשי. איך בעצם מממשים במציאות את כל השערים האלה?

על כך בפעם אחרת.