» נושאי לימוד
» נושאי לימוד
יום שבת 20 באפריל 2024
שקפים 8,9 - חישוב שארית
דף ראשי  פרק 6 - יחידת החישוב הלוגית  שקפים 8,9 - חישוב שארית גרסה להדפסה

שקפים 8 ו-9 - "חישוב שארית בהסתכלות קדימה"

 

השקפים הללו עוסקים בשיטה מהירה לחישוב שאריות.

בשיטה הרגילה, כאשר אנו רוצים לחבר מספר סיביות, אנו צריכים לחבר את הסיביות הראשונות ביחידה הראשונה (כלומר במחבר מלא Full adder) ולקבל תוצאה ושארית. את השארית מעבירים ליחידה הבאה שבה מחוברות הסיביות השניות ושוב, תוצאה ושארית. ההמשך ידוע, והשארית מתקדמת מיחידה ליחידה עד לקבלת השארית מהיחידה האחרונה, שהיא השארית של כל תוצאת החיבור (מובן שהשארית יכולה להיות רק 0 או 1 כי אנו עוסקים במספרים בינאריים).

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

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

 

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

 Generate– האם חיבור הסיבית ה-i תחזיר שארית?

 Propagate– האם אנו "סוחבים שארית" עד לנקודה זאת (עד לסיבית ה-i)?

 

כעת, באמצעות 3 נוסחאות נוכל לחשב את השאריות בצורה רקורסיבית.

השאריות, יחד עם המימוש הרקורסיבי שלהם מוצגות בשקף.

 

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

 

 

 

 

 

בשקף 9 אנו נראה מימוש דומה אך הפעם לגבי חיבור מילה בגודל 16 סיביות. היתרון פה הוא השימוש ב-4 יחידות מהסוג הקודם (כמו שהודגמו בשקף 8) וחיבור שלהם בתצורה שמאפשרת חישוב מהיר.

 

 

 

 

 

 

 

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

מובאת פה טבלה הקושרת בין מס' הסיביות לחיבור (n) , לבין סיבוכיות החיבור:

 

 

סיבוכיות זמן חישוב

סיבוכיות חומרה

 

O(n)

O(n)

שיטת הגל (הבסיסית) לחישוב שאריות

O(logn)

O(nlogn)

שיטת "חישוב בהסתכלות קדימה" לחישוב שאריות

 

 

 22-02-04 / 20:31  עודכן ,  31-01-04 / 22:54  נוצר ע"י אפרת ליברך  בתאריך 
 שקף 5 - חיסור ביחידת חישוב לוגית - הקודםהבא - פרק 8 - יחידת האוגרים 
תגובות הקוראים    תגובות  -  0
דרכונט
מהי מערכת הדרכונט?
אינך מחובר, להתחברות:
דוא"ל
ססמא
נושאי לימוד
חיפוש  |  לא פועל
משלנו  |  לא פועל
גולשים מקוונים: 4