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

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

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

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

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

***

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

7-segments_Indicator
אנימציה 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.

7 segment display edited
איור 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).

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

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

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

Advertisements

כתיבת תגובה

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

הלוגו של WordPress.com

אתה מגיב באמצעות חשבון WordPress.com שלך. לצאת מהמערכת / לשנות )

תמונת Twitter

אתה מגיב באמצעות חשבון Twitter שלך. לצאת מהמערכת / לשנות )

תמונת Facebook

אתה מגיב באמצעות חשבון Facebook שלך. לצאת מהמערכת / לשנות )

תמונת גוגל פלוס

אתה מגיב באמצעות חשבון Google+ שלך. לצאת מהמערכת / לשנות )

מתחבר ל-%s

%d בלוגרים אהבו את זה: