צפה בסרטון "Incredible Robots – The Future of Mankind – Extreme Machines – Discovery Channel Documentary" ב-YouTube

צפה בסרטון "Turning & the Lathe" ב-YouTube

סרטון זה מציג בקצרה סוגי עיבוד שבבי שונים בעזרת מחרטה

Daphne Koller: What we're learning from online education

Daphne Koller: What we're learning from online education #TED : http://on.ted.com/lAEv

צפה בסרטון "This is how you solve a Rubik's cube in 5 seconds." ב-YouTube

צפה בסרטון "Rubik´s Cube Solver Lego MindStorms NXT 2.0" ב-YouTube

חופשה נעימה לכולם. להתראות בשנה הבאה

גבי

בניית דיאגרמת שערים לוגיים בעזרת שער יחיד

בבניה

צמצום ביטויים בעזרת מפת קרנו

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

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

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

התהליך מורכב מהשלבים הבאים:

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

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

מיפוי מטבלת אמת למפת קרנו

מפת קרנו היא טבלה המכילה מספר שורות ועמודות. סך כל התאים שיש בטבלה שווה למספר השורות בטבלת האמת ממנה אנו ממפים – למשל, אם יש לי 3 משתנים לוגיים, אני אבנה טבלת אמת של 8 שורות, וגם מפת קרנו תכיל 8 תאים (ראה ציור בהמשך). באותו אופן לטבלת אמת של 4 משתנים יש 16 שורות, וגם למפת קרנו המתאימה יהיו 16 תאים.

מפת קרנו ל-3 משתנים:

מפת קרנו ל-4 משתנים:

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

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

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

אנחנו מתעלמים מהשורות בעמודת הפסוק בהן יש ערך אפס (0).

תהליך המיפוי מפונקציה קנונית עושה שימוש בכותרות הנמצאות מעל עמודות המפה ומשמאלם. מפת קרנו מתנהגת כמו לוח הכפל. כל תא במפה מייצג את תוצאת המכפלה של הביטוי המופיע בראש העמודה עם הביטוי המופיע משמאל לעמודה. אם נסתכל על מפת קרנו של 4 משתנים נראה כי בראשי העמודות יש פעולות כפל (AND) של שני המשתנים הראשונים A ו- B, ואילו משמאל לעמודות מופיעים פעולות כפל של שני המשתנים  הנותרים C ו- D.

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

סימון קבוצות:

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

כללים לסימון קבוצות:

1. קבוצת תאים המכילה את הערך אחד (1) יכולה לכלול כמות של תאים מתוך הגדלים הבאים בלבד: 1,2,4,8,16,32, וכו (חזקות של 2)

2. צריך לזהות ולהקיף קבוצות תאים כמה שיותר גדולות. ככל שהקבוצות גדולות יותר מתקבל ביטוי מצומצם יותר

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

4. קבוצת תאים מסומנת צריכה להיות חסומה במלבן.

5. צריך לשאוף לכמה שפחות קבוצות מסומנות.

6. למפת קרנו תכונת גליליות/כדוריות – ניתן לכופף את המפה לצורת גליל באופן שהגבול העליון של המפה נוגע בגבול התחתון של המפה או בהתאמה הגבולות מימין ומשמאל. במצב בו הגבולות נוגעים ניתן לסמן קבוצות שחוצות את גבול ובכך להשיג קבוצות גדולות יותר.
מקרה מיוחד הוא מצב שבו 4 הפינות של המפה הופכים לקבוצה אחת.

7. יש סימון מיוחד שנקרא DON'T CARE ??? שמציין מצבים של מערכת הבקרה שלא יכולים להתרחש במציאות אבל כן מופיעים כאחד המצבים בטבלת האמת. תא בו מופיע הסימן המיוחד מתייחסים אליו לפעמים כמו 1 ולפעמים כמו אפס (0). אם הסימן תורם ליצירת קבוצה גדולה יותר אזי מייחסים אליו כמו 1, אם אינו תורם כלום מתייחסים אליו כמו אפס (0).

תהליך הסימון מסתיים כאשר לא נותרו תאים במפה שאינם משוייכים לשום קבוצה.

הוצאת ביטוי לוגי:

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

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

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

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

באופן מעשי התהליך הוא פשוט מאוד. ראה דוגמא להלן:

TBD

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

צמצום ביטויים לוגיים בעזרת חוקים

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

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

חוקי הצמצום מתחלקים למספר קבוצות, והתהליך של הצמצום מתחיל בביטוי המקורי.

• אם הביטוי המקורי אינו מכיל קטעים עם סוגריים, אז עלינו לנסות למצוא גורם משותף רחב ביותר בין קטעים של הביטוי. על ידי הוצאת הגורם המשותף אנחנו רוצים לקבל בתוך הסוגריים ביטויים פשוטים מתוך רשימת החוקים ועל ידי שימוש בחוק אנחנו נחליף את הביטוי בסוגריים לביטוי פשוט עוד יותר ובכך נקטין את כמות הפעולות הלוגיות בביטוי המקורי. תהליך זה חוזר על עצמו מספר פעמים עד שלא ניתן יותר מצוא גורם משותף שיאפשר לי צמצום בעזרת חוק.
• אם הביטוי המקורי מכיל סוגריים, אז אנחנו ננסה לפתוח את הסוגריים ולראות מה הביטוי המורחב כולל ובשלב זה להפעיל חוקי צמצום.
• ישנם 3 חוקים (דה-מורגן) שמתייחסים באופן ספציפי לשערי: NAND, NOR ו- XOR. בביטויים במכילים פעולות אלו, נשתמש בחוקים אלו כדי להפוך את הביטויים כך שיכילו רק פעולות AND, OR ו- NOT ובאופן זה יותר קל להפעיל את חוקי הצמצום.

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

מימוש בעזרת מפסקים חשמליים

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

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

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

אם למפסק אחד נקרא A ולשני נקרא B, והם יקבלו ערך 1 כאשר הם מופעלים (סוגרים מעגל חשמלי), וכן נקרא לנורה F והיא תקבל ערך 1 כאשר היא דולקת, אזי הקשר בין A,B ו- F הוא קשר AND – רק ש-A וגם B יהיו 1 אז F תדלק.

שער OR:

מאופיין על ידי שתי כניסות של מידע מחיישנים, ומוציא אות אמת (1) אם אחת משתי הכניסות הן אמת (1). אם  שתי הכניסות היא שקר (0), אז השער מוציא שקר (0) .

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

אם למפסק בענף העליון נקרא A ולמפסק בענף התחתון נקרא B, והם יקבלו ערך 1 כאשר הם מופעלים (סוגרים מעגל חשמלי), וכן נקרא לנורה F והיא תקבל ערך 1 כאשר היא דולקת, אזי הקשר בין A,B ו- F הוא קשר OR – מספיק ש-A או B יהיו 1 אז F תדלק.

שער NOT:

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

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

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

מפסק רגיל סגור הוא האופן בו ממשים פעולה לוגית NOT במעגלים חשמליים.

סימוני מפסקים:

יש מספר סימונים מקובלים למפסקים. בתמונה הבאה ניתן לראות 3 סוגי סימונים מקובלים למפסקים מסוג רגיל פתוח ורגיל סגור.