0.4 - טבלאות אמת - הרצאה

דיסקליימר:
התמונות והאילוסטרציות בהרצאה זו לקוחות מהמשחק "Turing complete"

הקדמה

אז למדנו שמעבד יכול לשמור מידע בבינארית.
הוא יכול לשמור ביטים, והוא שומר ביטים באוגרים, בRAM ובעוד מקומות.
בהרצאה זו פחות נתעסק באיך הוא שומר ביטים, אלה מה הוא עושה איתם.
איך המעבד מבצע פעולות עם מספרים בינארים? איך הוא יודע לחבר אותם?
לדוגמה,
בהינתן 3 אוגרים, כל אחד בגודל של 8 ביטים:
נניח שאוגר מספר 1 מחזיק במספר 1010 (10)
ואוגר מספר 2 מחזיק במספר 1111 (15)
כיצד המעבד יודע לקחת את שני המספרים האלו, לחבר אותם ולהחזיר את התשובה 11001 (25)?
בזה בדיוק נעסוק בשיעור הזה.

ההמצאה של המאה

מה שהופך את כל זה לאפשרי זה ה"Nand gate", שער הNand הוא צ'יפ קטן שנראה כך:

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

אופן פעולתו של הצ'יפ הוא כך,
)

אם הוא מקבל באחד מרגלי הקלט את המספר 1 (זרם גבוהה), הוא גם מחזיר ברגל הפלט את המספר 1 (זרם גבוהה).


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

בדרך כלל נהוג לבטא התנהגות של צ'יפים עם "טבלאות אמת".
טבלאת אמת, היא טבלאה שמציגה את התנהגות הצ'יפ- הנה לדוגמה טבלאה שמגדירה את התנהגות הNAND Gate

כאשר ירוק מסמן זרם גבוה, ואדום מסמן זרם נמוך.

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

לא נדבר בהרצאה זו כיצד הצ'יפ בנוי, כי אנחנו לא בשיעור פיסיקה.

עוד צ'יפים

באמצעות הNAND gate נבנה עוד צ'יפים, שמייצרים טבלאות אמת שונות.
אחרי שנבנה הרבה צ'יפים שונים, נוכל להשתמש בכולם כדי לבנות את המעבד שלנו.

שער הNOT

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

כאשר הוא מקבל כקלט 1, הוא מחזיר 0- וכשהוא מקבל כקלט 0, הוא מחזיר 1.
כדי לבנות את השער, אנחנו נקח שער NAND- ונחבר את שני רגלי הקלט שלו.

כאשר NAND מקבל בשני רגלי הקלט שלו 1, הוא מחזיר 0, וכשהוא מקבל 0 הוא מחזיר 1.
למעשה- כך אפשר לממש את שער הNOT.

שער הNOT הוא שער שהופך כל ביט שהוא מקבל , 0->1 ו- 1->0

שער הAND

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

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

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

שער הAND הוא שער שדולק רק ששני הרגליים שלו דולקים.
- שם השער מרמז לנו על פעולותו, כי גם הרגל הראשונה וגם הרגל השניה צריכה להיות דולקים כדי שידלוק ולכן הוא AND (וגם)
שער הNAND הוא שער שהפוך ממנו, הוא שער שדולק רק כאשר שני הרגליים שלו כבויים.
- שם השער מרמז לנו על פעולתו כי הוא הפוך מAND, אז הוא נקרא NAND- קיצור של NOT AND.

שער הOR

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

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

שער הOR דולק רק שלפחות אחד מרגליו דולקים.
- שם השער מרמז לנו על פעולותו, כי אם הרגל הראשונה דולקת או הרגל השניה דולקת השער ידלוק, ולכן הוא OR (או)

שער הNOR

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

למעשה שער הNOR הוא ההפך של שער הOR
NOR = not or
וכדי לבנות אותו, ניתן פשוט להוסיף את שער NOT ברגל הפלט של שער OR.

שער הXOR

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

שער הXOR הוא שער מיוחד, שדלוק רק כשאחד הרגליים הוא 1 אבל לא ששניהם 1 ולא ששניהם 0.
כדי לבנות אותו, עלינו לחבר NAND, OR ו- AND.

הצ'יפים שבנינו יהיו אבני היסוד של המעבד. ובאמצעותן נוכל לבנות את כל חלקי המעבד שלנו.
AND
NAND
OR
NOR
NOT
XOR

הALU

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

חיבור מספרים בינארים

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

דוגמה:

נחבר את המספרים הבינאריים:

   1011  
+  1101  

נחבר מימין לשמאל:

ספרה	חיבור	תוצאה	העברה
1 + 1	= 10	0	1
1 + 0 + 1 (שארית)	= 10	0	1
0 + 1 + 1 (שארית)	= 10	0	1
1 + 1 + 1 (שארית)	= 11	1	1

בסוף נוסיף את השארית:

 1 (last remainder)
  1011  
+ 1101  
-------
11000

תוצאה:

1011₂ + 1101₂ = 11000₂
או בדצימלי:
11 + 13 = 24, ובאמת 11000₂ = 24₁₀.

ה HALF ADDER

שער הHALF ADDER הוא שער שממש חיבור בין שתי ביטים. כאשר הוא מקבל ברגלי הקלט שלו שני ביטים שעליו לחבר, ומחזיר ברגל אחת את התוצאה של החיבור, וברגל שנייה את ה"CARRY", רגל שמסמנת אם נשאר שארית.
זוהי טבלאת האמת של השער:

כאשר אם נחבר שני ביטים ששווים 0, נקבל 0.
אם נחבר ביט דולק וביט כבוי נקבל 1.
ואם נחבר שני ביטים דולקים, נקבל את המספר 10, כך ברגל הSUM נקבל 0, וברגל הCARRY נקבל 1- כי יש שארית.
כדי לבנות HALF ADDER נשתמש בADD ו- XOR

שער הFULL ADDER

הבעיה בשער HALF ADDER, שכמו שראינו למעלה, כשמחשבים חיבור של מספר בינארי וכל מספר, יכול להיות שיהיה "שארית" שגם אותה תצטרכו לחבר. כך שאם נרצה לבנות שער גדול שמחבר מספרים בינארים, נצטרך לבנות שער שיודע לחבר 3 ביטים- בשביל 2 הביטים שצריך לחבר + שארית שאולי צריך לחבר.
כך יראה טבלאת אמת של FULL ADDER

ובצורה דומה לHALF ADDER, הFULL ADDER יכיל 2 XOR-ים ו2 AND-ים, כדי לחבר 3 ביטים.

חיבור בינארים

באמצעות שער הFULL ADDER, נוכל לחבר מספרים בינארים עם כמות לא מוגבלת של ביטים!
אם נרצה לחבר 2 מספרים בינארים כאשר כל אחד מהמספרים עם 8 ביטים, נוכל לבצע זאת עם חיבור של 8 FULL ADDER-ים.

סיכום

מטרת השיעור הייתה לחשוף אתכם על רגל אחת כיצד פועל המעבד.
- למדנו כיצד באמצעות השער הלוגי NAND, בנינו מכונה שיודעת לחבר שתי מספרים. וממש מימשנו בעצמנו את הוראת "ADD" במעבד המומצא שלנו.
- הכרנו את השערים הלוגים הבסיסים, AND, NAND, NOT, OR, NOR, XOR ואת אופן פעולתם.
- אם תרצו לבנות בעצמכם מעבד עם שערים לוגים, מעבד עם ALU שלם, אוגרים, RAM, ועוד- אני ממליץ לכם מאוד לקנות את המשחק "Turing complete"- המשחק מאפשר לכם לבנות מעבד שלם ממש משער NAND פשוט- ואפילו מאפשר לכם לתכנת ולבנות משחקים על המחשב שבניתם.
- בנוסף אם התחום מעניין אתכם, אני ממליץ לעשות את הקורס האקדמי "NAND2TETRIS", שבו תלמדו כיצד לבנות מעבד מNAND ולתכנת מעליו את המשחק TETRIS.