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

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

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

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

סוף.

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

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

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

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

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

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

תמונה 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 כדי לקבל את התוצאה הרצויה?

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

הבה ונתכתשה – כמה מילים על השאלה האם כל תחום בפיזיקה הוא מדעי והאם זה משנה

נתחיל בשאלה פרובוקטיבית.

ידוע שפיזיקה היא ענף במדעי הטבע ושמדען הוא אדם שעוסק במחקר מדעי.

האם כל מדען שחוקר בתחום הפיזיקה עוסק במדע? האם כל תחום בפיזיקה הוא מדעי?

על פניו, נראה שהתשובה ברורה, לא?

אז בואו ושמעו סיפור.

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

במה דברים אמורים?

***

הויכוח לא נולד אתמול וגם לא לפני שנה אבל מישהו בחש בקלחת והנושא התעורר מחדש ביתר שאת. בדצמבר 2014 התפרסם מאמר דעה במגזין המדעי המוביל 'Nature' פרי עטם של שני פיזיקאים מכובדים. כותרת המאמר היתה :"Defend the integrity of physics", לא פחות.

צילומסך של כותרת המאמר.

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

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

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

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

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

צילומסך של כותרת הכתבה שמדווחת על הכנס.

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

***

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

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

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

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