מהו קוד Hamming: היסטוריה, עבודה ויישומיו

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

מהי איתור ותיקון שגיאות?

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

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

תיקון שגיאות הוא תיקון הנתונים המועברים ממשדר למקלט. ניתן לבצע תיקון שגיאות בשני סוגים.

תיקון שגיאות לאחור

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

תיקון שגיאות קדימה

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

אם יש 'm' מספר סיביות נתונים ו- 'r' מספר סיביות מיותרות, שילובי המידע יהיו 2r.

2r> = m + r + 1

סוגי קודי זיהוי שגיאות

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

בדיקת זוגיות

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

איתור שגיאות

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

בדיקת יתירות אורכית (LRC)

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

בדיקת יתירות מחזורית

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

בדיקת יתירות מחזורית

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

מהו קוד ההאמינג?

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

קוד ההאמינג

היסטוריה של קודי Hamming

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

תהליך קידוד הודעה באמצעות קוד Hamming

תהליך קידוד ההודעה באמצעות קוד ההאמינג על ידי השולח כולל 3 שלבים.

שלב 1: השלב הראשון הוא חישוב מספר הסיביות המיותרות בהודעה

• לדוגמא, אם הודעה מכילה 'n' מספר ביטים ו- 'p' מספר ביטים מיותרים מתווספים להודעה, אז 'np' מציין (n + p + 1) מצבים שונים.
• איפה (n + p) מייצג את המיקום של שגיאה בכל מיקום סיביות
• 1 (מצב נוסף) אינו מייצג שום שגיאה.
• מכיוון ש- p מציין 2 ^ p (2p) מצבים, ששווים למצבי (n + p + 1).

שלב 2: מקם את החלקים המיותרים במיקום מדויק / נכון

סיביות 'p' מוחדרות במיקומי הסיביות שהם כוחם של 2 כמו 1, 2, 4, 8, 16 וכו '. עמדות סיביות אלה מסומנות כ- p1 (מיקום 1), p2 (מיקום 2), p3 (מיקום 4) וכו '.

שלב 3: חשב את הערכים של ביטים מיותרים

• כאן משתמשים בסיביות זוגיות לחישוב הערכים של סיביות מיותרות.
• סיביות זוגיות יכולות להפוך את מספר ה- 1 במסר לשווה או לא זוגי.
• אם המספר הכולל של מס '1 בהודעה הוא שווה, אפילו זוגיות משמשת
• אם המספר הכולל של מס '1 בהודעה הוא אי זוגי, משתמשים בזוגיות אי זוגית.

תהליך פענוח הודעה בקוד Hamming

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

שלב 1: ספר את מספר הביטים המיותרים

הנוסחה לקידוד ההודעה באמצעות סיביות מיותרות היא,

2p≥ n + p + 1

שלב 2: לתקן את המיקומים של כל הביטים המיותרים

מספר 'p' של ביטים מיותרים ממוקמים במצבי כוח קצת של 2 כמו 1,2,4,8,16,32 וכו '

שלב 3: בדיקת זוגיות (זוגיות מוזרה ואפילו זוגיות)

סיביות זוגיות מחושבות על בסיס מספר 1 של סיביות נתונים וסיביות מיותרות.

לדוגמה

הזוגיות של p1 תהיה 1, 3, 5, 7, 9, 11, ...

הזוגיות של p2 תהיה 2, 3, 6, 7, 10, 11, ...

הזוגיות של p3 תהיה 4-7, 12-15, 20-23, ...

יתרונות קוד ההאמינג

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

• זה יכול לספק זיהוי שגיאות וגם מציין את הסיב המכיל שגיאה לתיקון.
• קודי Hamming קלים ביותר והטובים ביותר לשימוש בזיכרון המחשב ותיקון וגילוי שגיאות יחיד.

חסרונות קוד ההאמינג

• זה הכי טוב רק לתיקון וגילוי שגיאות בודדות. אם שגיאות סיביות מרובות, כל זה יכול להיות פגום.
• אלגוריתם קוד ה- Hamming יכול לפתור רק שגיאות של סיביות בודדות.

יישומי קודי Hamming

נעשה שימוש בקודי Hamming ב,

• מחשוב
• טלקומוניקציה
• דחיסת נתונים
• פתרון חידות וקודי טורבו
• לווינים
• CAM פלזמה
• חוטים מוגנים
• מודמים
• זיכרון מחשב
• פתח מחברים
• מערכות מוטמעות ומעבד

שאלות נפוצות

1). האם קוד ה- Hamming יכול לזהות שגיאות של 2 סיביות?

קודי Hamming יכולים לזהות ולתקן עד שגיאות של 2 סיביות בזרם נתונים

2). איך מתקנים את קוד ה- Hamming?

קודי Hamming ממוקמים בכל אורך נתונים בין הנתונים בפועל לבין סיביות מיותרות. קודים אלה הם מקומות עם מרחק מינימלי של 3 ביטים

3). מהו קוד הזוגיות?

קוד זוגיות או ביט זוגיות מוסיף קצת למסגרת שהתקבלה (הנתונים מכילים 1 ו- 0) כדי להפוך את מספר הביטים (1) לסה'כ או לא זוגי.

4). מה מרחק ההאמינג בין הנתונים?

מרחק הדפיקות בין שני זרמי הנתונים השונים באורך שווה הוא מספר 1.

מרחק החיזוק בין שני מיתרי נתונים באורך שווה ניתן לחשב באמצעות פעולת XOR.

לדוגמא, a = 11011001

b = 10011101

ניתן לחשב מרחק דפיקות כ,

11011001 ⊕ 10011101 = 01000100 (מספר 1 סיביות הוא 2)

מרחק השטיפה מציין את מספר ה- 1 בזרם הנתונים שהתקבל

אז, d (11011001, 10011101) = 2

באופן דומה, 010 ⊕ 011 = 001, d (010, 011) = 1.

5). האם קוד Hamming הוא מחזורי?

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

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