שיחה:קוד תיקון שגיאות

עריכות

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

אפשר להשתמש באמצעים אלגבריים מתוחכמים לבניית קודים מאוד חזקים מבחינת כמות המילים שניתן לקודד בהם, לעומת המרחק המינימלי בין מילות הקוד. לדוגמה, ניתן ליצור קוד תיקון שגיאות שישדר מידע של שלושה ביטים, A, B ,C. הקוד יורכב משלוש אותיות שהן פשוט הביטים עצמם ואחריהן שלוש קומבינציות ה-XOR ביניהם - AxB, AxC, BxC. קוד זה הוא בן 8 מילים שונות (מידע של שלושה ביטים), אורכו הוא 6 והמרחק בין כל שתי מילים שונות בקוד גדול או שווה ל-3.

קיימים קודים חזקים כלליים כמו קודי המינג, קוד LDPC,‏ Trellis, קוד ריד-סולומון ועוד.

באופן כללי, קודי התיקון מתחלקים לשתי קבוצות: קוד בלוק ו קוד קונוולוציה.

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

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

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

שיטת Check Sum היא שיטה יחסית פשוטה. במידה ויש שתי טעויות באותו המקום (1 כלפי מעלה ו1 כלפי מטה) אז לא מתקבלת הודעת שגיאה.

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

שיטת Code Hamming בניית code hamming: 1. רושמים מספרים החל מ-1 בסדר עולה. מקומות של 4^2 (1,2,4,8..) ומסמנים ב-X. 2. מעבירים מספר מהקסה לבינארי. 3. לוקחים מיקום של כל האחדים שנמצאים בשידור ורושמים בצד את המיקום שלו בבינארי. 4. עושים xor בין כל המספרים שנמצאים בעמודה. המס' המתקבל הוא code hamming. 5. ניתן לשדר את המידע ו- code hamming ב-2 שיטות: שיטה ראשונה- שולחים מידע ואז שולחים קוד. שיטה שנייה- מעתיקים קוד לתוך מילת שידור במקומות שבהם נמצא x ואז שולחים את המידע יחד עם קוד בפנים.

קפטן הוך - שיחה 01:14, 29 בדצמבר 2020 (IST)

בהמשך לעריכה שלמעלה, החלפתי גם את החלקים הבאים:

• מחקתי את כל החלק ניסוח פורמלי, שלא כללה ניסוחים מדויקים מספיק ולא כללה הגדרות של תכונות בסיסיות של קוד. ראו את תת-החלק (קוד במובן של המינג) הגדרה בדף החדש. הקטע שמחקתי:

קוד הוא קבוצת מילים, המורכבות ממספר קבוע של אותיות. כך, אם נסמן את קבוצת האותיות שבהן אנו משתמשים ב- $\Sigma$, ואת אורך כל מילה בקוד ב-n, אז קוד הוא תת קבוצה של $\Sigma ^{n}$ (כלומר, תת-קבוצה של מכפלה קרטזית של $\Sigma$ בעצמה n פעמים - קבוצת ה-n-יות הסדורות של איברים מ-$\Sigma$). לעיתים משתמשים בשם קוד לתיקון שגיאות לתיאור מיפוי חד-חד-ערכי מקבוצה $D$ כלשהי אל $\Sigma ^{n}$, כלומר למיפוי $e:D\to \Sigma ^{n}$. במקרה זה, הכוונה היא לקבוצת כל המילים בטווח $e(D)$. הפונקציה $e$ נקראת פונקציית הקידוד.

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

• מחקתי את החלק קודי תיקון שגיאות פשוטים, שכן הדוגמאות שם מקבלות ניסוח מסורבל מדי בשביל דוגמאות טריוויאליות. שכתבתי דומגאות אלה; הן מופיעות בתת-החלק (קוד במובן של המינג) דוגמאות בסיסיות בדף החדש. הנה מה שמחקתי:

הקוד הפשוט ביותר לתיקון שגיאות הוא פשוט קוד החזרה- חוזרים על המסר המשודר מספר פעמים. אם בתחילה המרחק המינימלי שבין שתי מילים בקוד היה d אז בקוד שבו יש חזרה נוספת על המסר, המרחק המינימלי הוא כבר 2d וכן הלאה- קוד שמילותיו הן פשוט n חזרות על מילות הקוד המקורי הוא קוד שהמרחק המינימלי בין מילותיו הוא nd.

לדוגמה נניח שהקוד המקורי הוא פשוט {0,1} (הקוד הבינארי הפשוט), קוד זה הוא בעל מרחק 1, ובו לא ניתן לזהות שגיאות. אם נחזור על כל דבר פעמיים, נקבל את הקוד {00,11}. זה קוד עם מרחק 2, ולכן ניתן לזהות שגיאה בשידור (תתקבל המילה 01 או 10, שבוודאי לא שודרה), אבל לא לתקן אותה: אם התקבל 01 לא ניתן לדעת אם שודר במקור 00 או 11. אם נחזור על כל דבר שלוש פעמים, נקבל את קוד החזרה {000,111}. זה קוד עם מרחק 3, ובו כבר ניתן לא רק לזהות, אלא גם לתקן טעות אחת: אם התקבל 001 אז כנראה שודר 000.

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

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

$\ C^{+}=\left\{(x_{1},...,x_{k},x_{k+1}):x_{1}+...x_{k}+x_{k+1}=0\right\}$

קפטן הוך - שיחה 22:40, 29 בדצמבר 2020 (IST)

הצפנה פוסט-קוונטית

ממליץ להוסיף לערך את ההקשר להצפנה פוסט קוונטית, כדוגמת הצפנת מקאליס. זה ינחמנו - שיחה 17:48, 29 בדצמבר 2020 (IST)

רעיון טוב. בכל אופן בתכנון שלי להרחיב את החלק על שימושים. קפטן הוך - שיחה 17:13, 30 בדצמבר 2020 (IST)