ב-Online
 
 
 
 
 
 
 
לפרק את הבייט 
מלך השערים 
 
 תדמיינו שזה שער, ושהמפתחות נראים בצורה של 1 או 0    צילום: GettyImages    
לפרק את הבייט |
 

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

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

הביטים נקראים גם משתנים בוליאניים, על שם המתמטיקאי ג'ורג' בוּל (1815-1864) שהמציא את האלגברה של משתני אמת/שקר. האלגברה הבוליאנית מגדירה אוסף פעולות בסיסיות שניתן לבצע על ביטים, ולשמחתנו אפשר לממש את הפעולות האלה באמצעות רכיבי חומרה זעירים שנקראים "שערים לוגיים" וליצור את המעבדים שהם הלב והמוח של כל מחשב.
 

נא להכיר: שערים לוגיים

 
השער הלוגי הפשוט ביותר הוא שער NOT. הוא מקבל כקלט ביט יחיד ומוציא כפלט את הביט ההפוך. כלומר, אם התקבל 0 הוא יוציא 1, ואם התקבל 1 הוא יוציא 0. הפעולה של שער NOT היא פעולה אונרית (Unary), כלומר מתבצעת על קלט בודד. כל השערים ה"קלאסיים" האחרים מבצעים פעולות בינאריות (Binary), על שני קלטים. לדוגמה, שער OR מקבל כקלט שני ביטים ומוציא 0 כפלט אם שניהם 0, או 1 כפלט אם לפחות אחד מהם הוא 1. שער AND מקבל גם כן שני ביטים, ומוציא 1 כפלט רק אם שניהם 1. בכל מקרה אחר הוא יוציא 0. איור מס' 1 מציג את הסמלים המוסכמים של השערים הלוגיים הבסיסיים ואת טבלאות האמת שלהם, שמציגות את הקומבינציות האפשריות של קלטים ופלט עבור כל שער.
 
איור 1: שערים לוגיים בסיסיים (איורי שערים: ויקיפדיה, עיבוד: עידו גנדל)
 איור 1: שערים לוגיים בסיסיים (איורי שערים: ויקיפדיה, עיבוד: עידו גנדל) 
 
שילוב של שער NOT עם השערים האחרים מפיק עוד שלושה שערים בסיסיים: שער NAND (קיצור של NOT AND), שער NOR ושער XNOR. השערים האלה מבצעים את אותן פעולות כמו השערים המקוריים, אך "הופכים" את התוצאה. במקום שבו שער OR ייתן פלט 1, שער NOR ייתן פלט 0 ולהיפך. הסמלים של השערים הללו זהים לאלה המקוריים פרט לעיגול הקטן שמתווסף לפני הקלט, כמו בשער NOT שבאיור. למעשה, אם משתמשים בפלט של שערים מסוימים כקלט של שערים אחרים, אפשר ליצור את כל השערים הנ"ל משערי NAND או NOR בלבד. על מימושים שכאלה נדבר בשבוע הבא.
 
 

XOR להצפנה, XOR לסימון

הדגמה של פעולת XOR (איור: עידו גנדל)
 הדגמה של פעולת XOR (איור: עידו גנדל)   
הפעם נתמקד בשער אחד מסוים – שער XOR (קיצור של eXclusive OR). אם נתבונן על טבלת האמת שלו, אפשר לראות שהוא מוציא 1 כפלט רק כאשר שני הקלטים שונים זה מזה. זוהי התנהגות שימושית ביותר. בואו ונקפוץ כמה וכמה רמות למעלה ונבין למה.

בשפות תכנות גבוהות קיימים אופרטורים (פעולות שמבוצעות על משתנים) מקבילים לשערים הלוגיים הבסיסיים. נניח שיש לי שלושה משתנים, a, b ו-c מסוג בייט (8 ביטים). בשפת דלפי, לדוגמה, אני יכול לכתוב את הפקודה "a := b XOR c". התוכנית תעבור על הביטים המקבילים של b ושל c, זוג אחרי זוג, תבצע על כל זוג שכזה פעולת XOR, ותכניס את התוצאה לביט המתאים ב-a. האיור משמאל מדגים את התהליך עבור 4 מתוך 8 הביטים. עכשיו, דמיינו ש-c הוא בעצם משתנה קוד, מעין מפתח שנועד להצפנה, ואילו b הוא הנתון שאנחנו רוצים להצפין. קיבלנו ב-a ערך מוצפן שונה מהערך המקורי. כעת, אם נרצה לשחזר את b המקורי מתוך a, כל מה שצריך לעשות זה לבצע XOR של a ושל c!
 
התוצאה שקיבלנו ב-a יכולה להיות תוצאה של הרבה קומבינציות שונות של מפתח ושל נתון. למשל, אם b היה 1010 ו-c היה 0100, או אם B היה 0000 ו-c היה 1110, היינו מקבלים את אותה התוצאה בדיוק. אדם שאינו יודע מה הערך של c יתקשה לפענח את הערכים המקוריים.

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

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

כל הזכויות שמורות 2011 © נענע 10 בע"מ
 
 
 
 
כל הזכויות שמורות © Nana10 בע"מ
Video powered by