הדילמה של יצחק, חלק ב' (מימוש) – כמה מילים על רכיבי זיכרון במערכות סדרתיות

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

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

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

זהירות: רשימה טכנית!

***

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

A – הקלט הקודם היה 0

B – הקלט הקודם היה 1

C – השניים הקודמים היו 1

D – השלושה הקודמים היו 1

כל מצב נוסף הוא מיותר ונכלל כבר במצבים A-D.

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

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

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

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

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

להלן הטבלה לאחר קידוד:

השלב הבא הוא להשתמש בטבלת העירור של SR-Latch כדי לדעת מה יש להזין לכל רכיב זיכרון על מנת לעבור מ- y₁y₂ של המצב הנוכחי לזה של המצב הבא. לדוגמה המצב הראשון y₁y₂ (בשורה הראשונה) הוא 00 ולפי טבלת המצבים המקודדת עבור כניסת קלט x=0 המצב הבא הוא 00. טבלת העירור של SR-Latch (ראו רשימה קודמת) מנחה אותנו שכדי לעבור מ-0 ל-0 יש ללחוץ S=0 ואז לא משנה מה לוחצים ב-R. אם כן, גם רכיב זיכרון 1 וגם 2 צריכים לקבל כניסות של S=0 , R=d כפי שניתן לראות בשורה הראשונה של טבלת המימוש. ה-d מסמל don't care.

השלב האחרון לפני מימוש הוא למצוא את הפונקציה הבוליאנית המתאימה עבור כל הכניסות והיציאות של המעגל, כלומר עבור: S₁, R₁, S₂, R₂ ו-Z הפלט. כל המידע הדרוש כבר קיים בטבלאות שבנינו. נותר רק למצוא את הפתרון המינימלי.

נשתמש בשיטה הנקראת מפת קרנו. נסביר את השיטה תוך פתרון עבור S₁. נרכז את הידע שלנו על S₁ בטבלה כך שהשורות מוגדרות לפי y₁y₂ והטורים לפי X הקלט. התוכן של תאי הטבלה הוא הערכים המתאימים של S₁. למשל בשורה y₁y₂=01 עבור x=0 דרוש S₁=0 ועבור x=1 דרוש S₁=1. להלן הטבלה המלאה:

כדי לקבל פתרון מינימלי יש לסמן ברצף את כל ה-1-דים בטבלה, בודדים, זוגות, רביעיות, שמיניות וכו'. ה-1 היחיד בטבלה של S₁ ממוקם בתא שמשמעותו הבוליאנית היא בעצם x_·y₁'_·y₂  כלומר נקבל 1 אם  x ו-y₂ שווים 1 ו-y₁ שווה 0 (הגרש מסמן מעבר במהפך). נשים לב שמתחת ל-1 יש d, כלומר לא אכפת לי. יש לנו חופש לבחור אותו כ-1 ואז לסמן גם אותו. כעת הטבלה מראה לנו ש-y1 יכול להיות 0 או 1 ולכן S₁ בעצם לא תלוי בו. אם כן נוכל לרשום את הפונקציה הבוליאנית המינימלית הבאה: S₁=x·y₂.

נתבונן במפת קרנו עבור R₁:

ניתן לסמן את שני ה-1-דים ולקבל פתרון דומה לקודם שמצריך שער 'וגם' אחד. נשים לב שאם נבחר את שני ה-d מעל ה-1-דים כ-1 ונסמן גם אותם נקבל שהפתרון המינימלי הוא פשוט 'x, ללא תלות ב- y₁y₂ ולכן נבחר פתרון זה, 'R₁=x.

לסיכום הפונקציות הבוליאניות עבור הכניסות והיציאות הן:

S₁=x·y₂

'R₁=x

'S₂=x·y₁

R₂=x'+ y₁

'z=x· y₁·y₂

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

השאר כבר על יצחק.

סוף.