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

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

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

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

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

האם יצליח יצחק במשימה?

תמונה 1: כבשים במכון מחקר בארה"ב. המקור לתמונה: אתר המשרד לחקלאות של ארה"ב, דרך ויקיפדיה. הצלם: Keith Weller. בעעעע!

***

ראשית נתרגם את הבעיה לשפה בוליאנית.

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

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

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

***

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

איור 2: שני מהפכים מחוברים בטור. המתח החשמלי המסומן כ-x ו-y הוא יציב בזמן והפוך אחד לשני.

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

נבחן את המבנה המשופר הבא:

איור 3: משמאל שני מהפכים בטור מוצגים בצורה שונה. מימין במקום המהפכים יש שערי NOR. יש לנו שתי כניסות שליטה, S ו-R. היציאה מסומנת ב-Q. המקור לתמונה הימנית: ויקיפדיה, לשם הועלתה על ידי המשתמש Napalm Llama.

נשים לב שלמרות הסידור המבלבל, המעגל המוצג באיור 3 משמאל הוא עדיין שני מהפכים מחוברים בטור. כעת נחליף את המהפכים בשערי NOR, כלומר שערי 'או' עם מהפך ביציאה. בסידור זה נשארנו עם שני מהפכים בטור, אבל הרווחנו עוד שתי ידיות לשליטה שמסומנות באיור 3 משמאל באותיות S ו-R (משמעותן set ו-reset בהתאמה). היציאות של המעגל מסומנות באותיות Q ו-Q'. מכיוון שהן תמיד הפוכות אחת לשניה, נניח ש-Q היא היציאה ו-Q' היא ההיפוך של היציאה.

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

נניח שכעת הערך השמור ברכיב הוא Q, והזנו ערכים מסוימים עבור הידיות R ו-S. מה יהיה הערך השמור ברכיב בסיבוב הבא?

אם ערך שתי הידיות הוא 0 אז הרכיב שומר על ערכו הקודם.

אם S=0 ו-R=1 אז הערך השמור ברכיב הופך ל-0 ללא תלות במה היה בו קודם.

אם S=1 ו-R=0 אז הערך השמור ברכיב הופך ל-1 ללא תלות במה היה בו קודם.

אם S=1 ו-R=1 אז הערך השמור ברכיב למעשה לא מוגדר היטב כי מתקבלת סתירה.

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

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

אם יש ברכיב 0 ואנחנו רוצים שישאר 0, אנחנו בטוח צריכים ללחוץ על S, ואז לפי טבלה 4 זה כבר לא משנה אם לוחצים על R או לא.

אם יש ברכיב 0 ואנחנו רוצים שישתנה ל-1, אנחנו חייבים ללחוץ על S, ולא ללחוץ על R. אין עוד אופציה.

אם יש ברכיב 1 ואנחנו רוצים שישתנה ל-0, אנחנו חייבים לא ללחוץ על S, וכן ללחוץ על R. אין עוד אופציה.

אם יש ברכיב 1 ואנחנו רוצים שישאר 1, אנחנו בטוח לא צריכים ללחוץ על R, ואז לפי טבלה 4 זה כבר לא משנה אם לוחצים על S או לא.

התוצאות מסוכמות בטבלה הבאה:

***

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

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

השאלה כעת היא מה על יצחק לעשות כדי השתמש ברכיב ה- SR-Latch כדי לקבל את התוצאה הרצויה?

על כך בחלק ב' של הרשימה.