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

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

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

***

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

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

ישנן מספר דרכים לבנות מתג עבור מעגלים חשמליים בזרם נמוך (למשל בשבבים למחשבים). בעבר היו משתמשים בשפופרות ואקום והיום אנחנו משתמשים בטרנזיסטורים שהם רכיבים שבנויים מחומרים שנקראים 'מוליכים למחצה' ועל המצאתם הוענק פרס נובל בפיזיקה בשנת 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).

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

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

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

הדרך הלא נכונה לתכנן מסיבה מוצלחת – כמה מילים על אלגברה בוליאנית

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

משרתו חושב מספר שניות ועונה: "אתה מתכוון בעצם שכדי שהמסיבה תרים את הגג או שפורתוס חייב להיות שם או שגם אתוס וגם אראמיס חייבים להיות שם?"

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

המשרת מגרד בפדחתו, נאנח ועונה: "כן אדוני. שאני אגיש את היין?"

"כן, מוטב שכך". עונה ד'ארטאניאן.

ארבעת המוסקיטרים. איור מתוך מהדורה של 'שלושת המוסקיטרים' שפורסמה ב-1894. המקור: ויקיפדיה.

***

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

האמירה "פורתוס יגיע למסיבה" תסומן על ידי המשתנה A.

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

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

נסמן את האמירה "אתוס יגיע למסיבה" על ידי המשתנה B, ואת האמירה "אראמיס יגיע למסיבה" במשתנה C.

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

***

ישנן שתי פעולות בלבד שניתן לבצע בין משתנים בעולמנו החדש. האחת פעולת 'וגם' והשניה פעולת 'או'. לדוגמה: "או שפורתוס יגיע למסיבה או שאתוס יגיע למסיבה". האמירה האחרונה למעשה מייצגת פעולת 'או' בין המשתנים A ו-B. כדי שהאמירה המורכבת תהיה נכונה מספיק ש-A יהיה נכון או ש-B יהיה נכון.

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

נסמן את פעולת 'או' בסימן '+' (כמו חיבור במתמטיקה) ואת פעולת 'וגם' בסימן '·' (כמו כפל). כלומר שהרישום A·B משמעו "גם פורתוס וגם אתוס יגיעו למסיבה" והרישום A+B משמעו "או פורתוס או אתוס יגיעו למסיבה".

כעת נוכל לתרגם את אמירתו המורכבת של ד'ארטאניאן לגבי התנאים להצלחת המסיבה: "או פורתוס או אתוס יגיעו למסיבה" וגם "או אראמיס או פורתוס יגיעו למסיבה". נכתוב באמצעות המשתנים: (A+B)·(A+C).

לעומתו טוען המשרת: "או שפורתוס יגיע או שאראמיס וגם אתוס יגיעו". ובמשתנים: (A+(B·C.

האם שתי האמירות מתקיימות או שאינן מתקיימות תחת אותם תנאים? במילים אחרות האם מתקיים:

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

***

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

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

A·0=0

A+1=1

חישבו לבד מדוע גם ההיגדים הבאים נכונים תמיד:

A·1=A

A+0=A

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

ניצור טבלה של כל התרחישים האפשריים עבור האמירות B, A ו-C. מספר האפשריות הוא 2 בחזקת מספר המשתנים:

תרחיש 1 הוא שאף אחד משלושת החברים לא מגיע. תרחיש 8 הוא שכולם מגיעים וכך הלאה.

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

נוסיף טור נוסף עבור A או (B וגם C). נעקוב אחרי הטורים הצהובים:

נעשה את אותם רצף של פעולות כדי למצוא את הטור עבור (A+B)·(A+C):

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

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

***

אז למה זה טוב?

למיטב ידיעתי, ואני לא מומחה בנושא, אלגברה בוליאנית שימושית לשני דברים עיקריים: לוגיקה ואלקטרוניקה דיגיטלית.

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

אדגים זאת מתישהו ברשימה נפרדת.