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

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

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

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

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

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

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

מודעות פרסומת

כתיבת תגובה

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

הלוגו של WordPress.com

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

תמונת Twitter

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

תמונת Facebook

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

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

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

מתחבר ל-%s