אם תצליח להבין משהוא תעדכן אותי..בחלק זה תינתן הקדמה תאורטית על שגיאות בעולם בתקשורת, מאיפה הן מגיעות, למה חשוב להתמודד אתם, על ההבדל בין זיהוי שגיאה לתיקונה.
ניתן לפשט את עולם התקשורת הדיגיטלית לפעולה בסיסית של שליחת מידע מצד אחד, השולח, אל עבר הצד השני, המקבל.
תכן המידע אשר נשלח הינו מגוון ומשתנה, המידע יכול לייצג קול (בשיחת טלפון) תמונה, וידאו, דף אינטרנט ועוד. אמנם המידע עצמו שונה בכל פרוטוקול תקשורת אך אופן הצגת המידע נשאר זהה.המידע מיוצג בצורה בינרית, כלומר כרצף של '1' (אחדות) ו – '0' (אפסים) למשל:
"1110010101000010101011000100101010000100100000100100101010”.
המידע עובר דרך ערוץ התקשורת. ערוץ התקשורת יכול להיות כבל תקשורת רגיל (כפי שבטח יוצא לכם מכרטיס הרשת כשאתם קוראים את המסמך), כבל אופטי מסוג כלשהו או אפילו פשוט האוויר ( כשאתם מדברים בפלאפון).
מה קורה כשהערוץ עצמו משבש את המידע שנשלח, שיבוש שגורם ל'1' להתפרש כ'0' או להפך. במצב כזה הצד המקבל יקבל מידע לא נכון, אשר יפורש בצורה בלתי נכונה.
הפתרון הפשוט היה להשתמש בערוץ תקשורת אמין במאת האחוזים, כלומר ערוץ שיבטיח לנו שלא יהיו שום שיבושים בשליחת המידע. לרוע המזל ערוצים כאלה אינם קיימים, ובשל מגבלות פיסיות הרי שבכל ערוץ, בהסתברות מסוימת (גדולה מאפס) תהיה שגיאה בהעברת הנתונים.
מה לעשות? האם איבדנו כל יכולת לשמור על אמינות בשליחת המידע?
התשובה כמובן שלילית, הפתרון נעוץ בקודים לגילוי שגיאות. קוד לגילוי שגיאות הינו סוג חדש של מידע, שמתווסף למידע הראשי ומאפשר למקבל לדעת האם המידע שהתקבל תקין או לא.
קוד לתיקון שגיאות, הינו קוד שלא רק מזהה את השגיאה, אלא מסוגל לתקנה.
גילוי שגיאות ותיקונם, כמו דברים רבים וטובים אחרים, התאפשר בזכות המתמטיקה. כמובן שלכל קוד ישנם מגבלות, ולא כל קוד יהיה אמין כמו קוד אחר. בעבודה זאת , תשתמשו בכלים שהכרתם עד כה בשפת ג'אווה על מנת לממש 4 קודים שונים לגילוי שגיאות. הקודים שיוצגו בגוף העבודה, הינם קודים מעשיים שמשתמשים בהם לגילוי שגיאות (תיקון שגיאות הינה פעולה יותר נדירה בפועל) ברשתות תקשורת מודרניות (וכמובן שברשת האינטרנט).
ייצוג מידע בעבודה
בעבודה זאת רצף מידע ייוצג באמצעות מערך מסוג int.
משימה 1:
מכיוון שבחרנו לייצג את המידע במערך נתחיל בכתיבת פונקציה פשוטה המקבלת מערך ובודקת האם הוא תקין. מערך יחשב כתקין אם הערכים המרכיבים אותו הינם אחדות ואפסים בלבד. השלימו מתודה אשר מקבלת מערך ומחזירה TRUE במידה והוא מערך בינרי חוקי, כלומר כל הקלט שלו הינו 0 או 1.
4. חלק א' - סיבי(ו)ת זוגיות
4.1 סיבית זוגיות
בחלק זה יש לממש את גילוי השגיאה באמצעות סיבית זוגיות.
סיבית הזוגיות הינו הקוד הפשוט ביותר לגילוי שגיאות, הרעיון הכללי הינו לוודא שבחבילה הנשלחת מספר האחדות (או האפסים תלוי בגרסה שבה משתמשים) הינו זוגי, אם מספר האחדות בחבילה המקורית הינו זוגי הרי שערך סיבית הזוגיות יהיה אפס, ולהפך, אם מספר האחדות אי זוגי הרי שערך סיבית הזוגיות יהיה אחד (כך סך כל מספר האחדות בחבילה הנשלחת עדיין זוגי). בצד המקבל את החבילה יש לבדוק אם מספר האחדות בחבילה הנקלטת זוגי. במידה ומספר האחדות אינו זוגי הרי שהתגלתה שגיאה.
שיטה זאת מסוגלת לגלות כל מספר אי זוגי של שגיאות , אך לא תגלה מספר זוגי של שגיאות. השיטה אינה מאפשרת תיקון שגיאות.
משימה 2
כיתבו מתודה אשר מקבלת מערך שמייצג מידע בינרי, המתודה תחזיר מערך חדש עם המידע המקודד לאחר שהתווספה סיבית הזוגיות.
כיתבו מתודה המקבלת מערך ומבצעת עליו בדיקת זוגיות, על המתודה להחזיר אינדיקטור שיציין
התקבל מערך לא בינרי (שגיאת קלט)
התקבל מערך בינרי שלא עבר את בדיקת הזוגיות
התקבל מערך בינרי שעבר את בדיקת הזוגיות
4.2 חלק ב' - סיבית זוגיות דו מימדית
שיטה זאת הינה הרחבה של סיבית הזוגיות .בשיטה זאת מתייחסים למידע כמערך דו מימדי כאשר השורה האחרונה והעמודה האחרונה משמשים לבדיקה, כמתואר בתרשים :
משימה 3
על מנת לממש שיטה זאת יש לייצג את המידע כמערך דו-מימדי.
כתבו מתודה אשר מקבלת מערך חד מימדי של מידע והופכת אותו למערך דו מימדי. אנו נניח, כי מספר העמודות הינו 8.
הגדירו את המשתנה:
public static final int COL_NUM 8
במידה והפונקציה תקבל מערך שאינו מתחלק ב-שמונה יש לשרשר אפסים למערך החדש. כפי שניתן לראות בתרשים
בזמן הקידיוד למידע מתווספים עמודה ושורה שכל אחת מהם משמש סיבית זוגיות של השורה\עמודה הרלוונטית. במידה והייתה שגיאה אחת הרי שניתן יהיה לאתרה ולתקנה. מדוגמה הנ"ל הביט השבעי- "0" (שורה שנייה עמודה שנייה) שגוי וניתן לתקנו ל-"1" (הדבר אינו נכון עבור יותר משגיאה אחת).
כיתבו מתודה אשר מקבלת מערך דו-מימדי של מידע ומקודדת אותו ע"י בניית מערך חדש אשר התווספו לו שורת ועמודת זוגיות
כיתבו מתודה המקבלת מערך בינרי דו-מימדי ומפענחת אותו ע"י בדיקת זוגיות ובמידת האפשר מתקנת את המידע. על המתודה להחזיר אינדיקטור שיציין. (בעבודה נניח כי ניתן לתקן שגיאה רק אם הייתה שגיאה אחת) הפונקציה תחזיר :
התקבל מערך לא בינרי (שגיאת קלט)
לא התגלו שגיאות
התגלתה שגיאה בודדת ותוקנה
התגלתה יותר משגיאה אחת ולא תוקנה.
5. חלק ג' - סכום ביקורת - Check Sum
אחת השיטות הנפוצות ביותר, ואשר נמצאת בשימוש בפרוטוקול TCP שמהווה חלק עיקרי מהאינטרנט. בשיטה זאת סכומם של כל בתי (שימו לב, בתים ולא ביטים) המידע מחושב על מנת ליצור בית נוסף באופן הבא:
1. חשב את סכום כל הבתים (ראה נספח א)
2. הסר מהתוצאה את החלקים העולים על ערכו בית (למשל עבור הסכום ההקסדצימאלי 0x345 יילקח החלק 0x45). בצורה פורמלית יותר יש להסיר את הביט(ים) הנושאים של הסכום. יש לקחת את שמונת הביטים הראשונים של הסכום.
3. למספר המתקבל חשב את המשלים לשתיים (ראה נספח ב)
4. שלח את המספר הזה בתור הCheck Sum
בצד המקבל נלקח המספר ומתווסף לו ה Check Sum, במידה ולא התגלו שגיאות התוצאה חייבת להיות מהסוג 0xY00 כאשר Y יכול להיות ערך כלשהו, אך שמונת הביטים הראשונים של התוצאה (הבית הראשון) חייבים להיות 0.
שיטה זאת תגלה שגיאה ברוב המקרים, אך לא תצליח לגלות שגיאה במקרים בהם סדר הבתים התחלף (כי סכומם יישאר זהה), במקרים בהם יהיו שגיאות שיסכמו לאפס או הוספת אפסים לפריים במקומות חדשים.השיטה אינה מאפשרת תיקון שגיאות.
משימה4
כיתבו מתודה אשר מקבלת חבילה, בודקת שהינה תקינה, ובמידה והמידע תקין מקודדת אותו ע"י הוספת CheckSum המייצג את החבילה. חבילה תקינה היא כזאת שבה המערך שהתקבל הינו בינרי. במידה ובחבילה ישנה שארית (כלומר אינה מתחלקת בשמונה) הרי שביטים אלו יחשבו הביטים הראשונים של בית חדש שבסופו אפסים.
• כיתבו מתודה אשר מקבלת מידע מקודד (בשיטת CheckSum) ומחזירה האם התגלתה שגיאה. יש לוודא את תקינות הקלט.
6. חלק ד' – CRC
קוד CRC הינו אחד הקודים המרכזיים המשמשים לגילוי שגיאות ונחשב לחזק ביותר מבחינת יכולת זיהוי השגיאות שלו. הבנת הקוד מבחינה מתמטית הינה טיפה מורכבת ועלולה להיות מסובכת בשלב זה, עם זאת, בחלק זה תגלו שמימוש השיטה אינו כל כך מסובך.
באופן כללי, קוד CRC מכיל 3 פרמטרים:
1. פולינום יוצר G אשר ידוע גם לשולח וגם למקבל
2. המידע D שהשולח רוצה לשלוח
3. השארית r שנשלחת יחד עם המידע.
בצד השולח מתצבעת פעולה מתטית על D באמצעות G לקבלת r ובצד המקבל מבצעת פעולה על r ו-D באמצעות G על מנת לבדוק האם המידע מכיל שגיאות.
בצד השולח:
בצד השולח מתבצעת חלוקה מודולו 2, בין D ו- G . לפני החלוקה יש לשרשר ל D מספר אפסים (כאשר מספר אפסים זה הינו מספר הביטים ב-G פחות 1). בחלוקה מודולו 2 עובדים מעל שדה המספרים {0,1} ומתעלמים משאריות כלשהן. בסוף החלוקה השארית הנה r כאשר גודל r בביטים יהיה ביט אחד פחות מ G.
ראו דוגמה לחלוקה כזו: (בדוגמה זו הגודל של G הינו 4 ביטים, לכן שירשרנו ל D 3 אפסים וגודלו של r הינו 3 ביטים.)
בצד המקבל:
הצד המקבל מקבל את D ו r וכאמור יודע את G. על הצד המקבל לשרשר את r ל D ולבצע שוב חלוקה של השרשור ב G. במידה ולא היו שגיאות הרי שהשארית תהיה 0. שארית שאינה 0 מעידה על שגיאה.
תחילה הגדירו את המשתנה הבא:
static final int G ={1,0,0,0,0,0,1,1,1}
שימו לב הגדירו משתנה זה תחת הגדרת הClass ולפני הגדרת הפונקציות כךשבמהלך הבדיקה יהיה ניתן לשנותו.
משימה 5
כיתבו מתודה אשר מקבלת את המידע D, המתודה תחזיר מערך מקודד הכולל את r ו D.
כיתבו מתודה המקבלת את D ו r ומחזירה האם התגלו שגיאות.
בשתי המתודות יש לוודא שהקלט הינו מערך בינארי תקין.
7. חלק ה' - איחוד החלקים לכדי תכנית בדיקה אחת
בחלק זה תיבנו ממשק משתמש שמטרתו לבדוק את התכנית.
הרעיון הכללי הינו לקבל\ליצור סדרה של מחרוזות לשידור, עבור כל אחת מהן להגדיר מחרוזות נקלטות. לאחר מכן להשתמש במחרוזות הנקלטות. על מנת להפעיל את כל אחת מהשיטות לגילוי השגיאות שהוכנו בסעיפים הקודמים.
ממשק התוכנית:
התוכנית תציג למשתמש את התפריט הבא:
Main Menu:
--------------
1. Manually enter data to encode
2. Automatically generate data to encode
3. Encode data
4. Manually enter data to decode
5. Automatically insert artificial errors to data
6. Decode data
7. Print original data
8. Print encoded data
9. Exit
Enter choice:
התוכנית תגיב בהתאם לבחירת המשתמש, באופן המתואר להלן:
אפשרות 1: התוכנית תציג למשתמש את ההודעה הבאה:
Enter binary data string (leave empty to finish):
המשתמש יכניס מחרוזת רציפה של אפסים ואחדות (דוגמה: 00101110100010). עליכם להמיר מחרוזת זו למערך המתואר בתחילת התרגיל. לאחר מכן יש להציג שורה זו שוב ולקלוט מחרוזת נוספת וכן הלאה, עד שהמשתמש יכניס מחרוזת ריקה, ובכך יסיים את הכנסת הקלט. מידע זה יהיה המידע המקורי. לאחר מכן יש לחזור לתפריט הראשי.
אפשרות 2: התוכנית תציג למשתמש את ההודעה הבאה:
Enter number of data strings to generate:
המשתמש יכניס את מספר המחרוזות לייצור. לאחר מכן תוצג ההודעה:
Enter max size of a single data string:
המשתמש יכניס את האורך המקסימלי למחרוזת בודדת.
לאחר-מכן התוכנית תייצר באופן אקראי מספר מחרוזות בינאריות עפ"י בחירת המשתמש כאשר בכל מחרוזת יש בין 0 ספרות למספר הספרות שהמשתמש בחר. מידע זה יהיה המידע המקורי. לאחר-מכן התוכנית תחזור
אפשרות 3: התוכנית תציג למשתמש את התפריט הבא לבחירת אלגוריתם קידוד:
Select encoding algorithm:
--------------------------------
1. Parity bit
2. Two dimensional parity check code
3. TCP checksum
4. CRC
5. Cancel
Enter choice:
המשתמש יבחר את האלגוריתם הרצוי. במידה והאפשרות שנבחרה אינה Cancel, התוכנית תקודד בנפרד כל מחרוזת במידע המקורי (שנקלט באמצעות אפשרויות 1 או 2 בתפריט הראשי) באמצעות האלגוריתם שנבחר בתפריט זה ותשמור אותו בתור המידע המקודד. לאחר-מכן התוכנית תחזור לתפריט הראשי.
שימו-לב: אין לדרוס את המידע המקורי עם המידע המקודד. יש לשמור את המידע המקודד בנפרד.
אפשרות 4: אפשרות זו תציג למשתמש ממשק דומה לזה המוצג באפשרות 1, כלומר תציג את השורה:
Enter binary data string (leave empty to finish):
ותקלוט מהמשתמש מחרוזות עד לקבלת מחרוזת ריקה. ההבדל בין אפשרות זו לאפשרות 1, היא שאפשרות זו תשמור את המידע שהתקבל בתור המידע המקודד ולא בתור המידע המקורי.
אפשרות 5: אפשרות זו תציג למשתמש את ההודעה הבאה:
Enter error probability for each bit:
המשתמש יכניס את ההסתברות לקבלת שגיאה בכל ביט, כמספר ממשי בין 0 ל-1 (יש לוודא שזה אכן כך!). לאחר מכן התוכנית תעבור על כל ביט בכל מחרוזת במידע המקודד ובהתאם להסתברות שהוכנסה ע"י המשתמש תהפוך אותו מ-0 ל-1 או להיפך.
לדוגמה: אם המשתמש הכניס הסתברות 0.1, כ-10% מהביטים במידע המקודד אמורים "להתהפך". לאחר-מכן יש לחזור לתפריט הראשי.
הערה: פעולה זו מתבצעת במקום, תוך דריסת המידע המקודד הקיים.
אפשרות 6: התוכנית תציג למשתמש את תפריט בחירת האלגוריתם:
Select decoding algorithm:
--------------------------------
1. Parity bit
2. Two dimensional parity check code
3. TCP checksum
4. CRC
5. Cancel
Enter choice:
במידה והמשתמש לא בחר באפשרות Cancel, התוכנית תנסה לפענח את המידע המקודד השמור (אשר קודד ע"י שימוש באפשרות 3 או נקלט ידנית מהמשתמש באמצעות אפשרות 4 בתפריט הראשי) באמצעות האלגוריתם שנבחר ע"י המשתמש.
לאחר תהליך הפיענוח התוכנית תציג את הנתונים הבאים:
מספר המחרוזות בהן הייתה שגיאה במחרוזת המתקבלת
האורך הממוצע של המחרוזות שבהן הייתה שגיאה
מספר השגיאות שהשיטה הצליחה לאתר (שימו לב שיש מקרים ספציפיים שכל שיטה לא יכולה לגלות ולכן יש להשוות בצורה "מפורשת")
מספר השגיאות שהשיטה לא הצליחה לאתר
אורך הממוצע של מחרוזת בה הייתה שגיאה שלא ניתנה לאיתור
אחוזי ההצלחה באיתור השגיאות
מספר השגיאות שהשיטה הצליחה לתקן
אחוזי ההצלחה בתיקון השגיאות
הערה:
הנתונים מס' 4,5,6 דורשים השוואה מול המידע המקורי, ולכן יש להציג אותם רק אם המידע המקורי אכן קיים (אינו ריק).
הנתונים מס' 7,8 רלוונטיים רק לאלגוריתם ספרת זוגיות דו-מימדית ולכן יש להציג אותם רק אם המשתמש בחר באלגוריתם זה.
כמו-כן, אם המידע המקודד היה ללא שגיאות, או אם התוכנית הצליחה לתקן את כל השגיאות במידע, המידע המפוענח (ללא נתוני בקרת-השגיאות) יועתק בתור המידע המקורי.
לאחר-מכן התוכנית תחזור לתפריט הראשי.
אפשרות 7: התוכנית תדפיס את כל המידע המקורי, מחרוזת אחת בכל שורה, וכל מחרוזת תודפס כרצף ספרות ללא רווחים. לדוגמה:
001011101011001
001111000110101011011110001
לאחר-מכן התוכנית תחזור לתפריט הראשי.
אפשרות 8: התוכנית תדפיס את כל המידע המקודד, מחרוזת אחת בכל שורה, וכל מחרוזת תודפס כרצף ספרות ללא רווחים. לאחר-מכן התוכנית תחזור לתפריט הראשי.
אפשורת 9: יציאה.
כמה מילים נוספות...
במהלך כל התכנית יש לבצע בדיקת קלט, התכנית תבדוק כל קלט אפשרי ובמידה והוא שגוי תציג הודעות רלוונטיות למשתמש. נושא בדיקת הקלט הוא משמעותי במיוחד ולמרות שהסטודנט המצוי יכול להרגיש כי הנושא מתסכל משהו זכרו כי כאשר אתם כותבים תוכנה ללקוח לא תרצו שעבור משתמש לא חכם התכנית תתרסק (למשל משתמש שיקיש 2 בתור ערך של מערך בינרי), אחרי הכל, השקעתם\ן בכתיבת הקוד זמן רב ותרצו שהקוד יעבוד בכל תסריט אפשרי.
ניתן ורצוי במיוחד להשתמש במתודות עזר פנימיות עבור מימוש האלגוריתמים השונים. עצתנו היא לנסות ולכתוב את המתודות בצורה הכללית ביותר האפשרית בצורה כזאת שניתן יהיה להשתמש באותן מתודות בחלקים שונים של התכנית.
נחזור ונדגיש את חשיבות התכנון, המילים שיאמרו עכשיו אינן בבחינת מס שפתיים: תכננו את העבודה לפני שאתם כותבים אותה! שאלו את עצמכם באיזה פונקציות תרצו להשתמש, איזה פרמטרים הן יקבלו ואיזה פרמטרים הן יחזירו. כמובן שכל תכנון הינו בסיס לשינוי כאשר תכתבו את הקוד, עם זאת, סטודנטים שיקדישו זמן לתכנון כל אחד מחלקי התכנית ולאינטגרציה ביניהם ימצאו את העבודה יותר מעניינת ויותר קלה למימוש.
בהצלחה!
גירסת הדפסה
סגן המנהל
מפקח
Winner
צל"ש
מומחה
התחלת הלימודים באוניברסיטה היא תמיד קשה.
