מרחק פטיש. אנציקלופדיה גדולה של נפט וגז

על קבוצה של מילים בינאריות באורך m מרחק d(a,b) בין מילים a ו-b הוא מספר המיקומים הלא תואמים של מילים אלו, לדוגמה: המרחק בין מילים a = 01101 ו-b = 00111 הוא 2.

המושג המוגדר בצורה זו נקרא מרחק האמינג.

הוא עונה על אקסיומות המרחק הבאות:

1) d(a,b)  0 ו-d(a,b)=0 אם ורק אם a = b;

2) ד(א,ב) = ד(ב,א) ;

3) d(a,b) + d(b,c)  d(a,c) (אי שוויון במשולש).

המשקל w(a) של מילה הוא מספר היחידות בין הקואורדינטות שלה. אז המרחק בין המילים a ו-b הוא משקל הסכום שלהן a b: d(a,b)=w(a b) , כאשר הסמל  מציין את פעולת חיבור מודולו 2 מבחינה קואורדינטות. באופן אינטואיטיבי, הקוד מתאים יותר לאיתור ותיקון שגיאות, ככל שמילות הקוד שונות יותר. המושג של מרחק האמינג מאפשר לנו להבהיר זאת.

מִשׁפָּטעל מנת שקוד יזהה שגיאות במיקומים k (או פחות), יש צורך ומספיק שהמרחק הקטן ביותר בין מילות קוד יהיה  k + 1.

ההוכחה למשפט זה דומה להוכחה של המשפט הבא.

מִשׁפָּט.על מנת שהקוד יתקן את כל השגיאות במיקומים k (או פחות), יש צורך ומספיק שהמרחק הקטן ביותר בין מילות קוד יהיה  2k + 1.

32. משפט על יכולת התיקון של קודים.

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

המאפיינים העיקריים של קודים מתקנים עצמיים הם:

1. מספר השילובים המותרים והאסורים. אם n הוא מספר הסמלים בבלוק, r הוא מספר סמלי הסימון בבלוק, k הוא מספר סמלי המידע, אז 2n הוא מספר צירופי הקוד האפשריים, 2k הוא מספר צירופי הקוד המותרים, 2n −2k הוא מספר השילובים האסורים.

2. יתירות קוד. הערך rn נקרא היתירות של קוד התיקון.

3. מרחק קוד מינימלי. מרחק הקוד המינימלי d הוא המספר המינימלי של סמלים מעוותים הנדרשים למעבר משילוב מותר אחד לאחר.

4. מספר שגיאות שזוהו ותוקנו. אם g הוא מספר השגיאות שהקוד יכול לתקן, אז זה הכרחי ומספיק ש-d≥2g+1

5. יכולות תיקון של קודים.

33. קידוד מטריקס. קודי קבוצה.

כאשר מציינים במפורש את סכימת הקידוד ב-( m, n)-code צריך לציין 2 מ' מילות קוד, וזה מאוד לא יעיל.

דרך חסכונית אחת לתאר ערכת קידוד היא טכניקת קידוד המטריצה.

בעבר, כל ערכת קידוד תוארה על ידי טבלאות שציינו מילת קוד באורך נ לכל מילת מקור באורך M. עבור בלוקים ארוכים, שיטה זו דורשת כמות גדולה של זיכרון ולכן אינה מעשית. לדוגמה, עבור ( 16, 33 ) הקוד ידרוש 33 * 2 16 = 2,162,688 סיביות.

דורש הרבה פחות זיכרון קידוד מטריצה. לתת ה מטריצת מימד m×n, המורכב מאלמנטים e ij , שבו אני הוא מספר השורה, ו י - מספר עמודה. כל אחד ממרכיבי המטריצה ה ij יכול להיות 0 או 1. הקידוד מיושם על ידי הפעולה b = aE או כאשר מילות קוד נחשבות כווקטורים, כלומר כמטריצות שורה בגודל 1×n.

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

קודי מטריקס נקראים גם קודים ליניאריים. עבור ליניארי (n − r, n)-קודים עם מרחק Hamming מינימלי ד קיים כרכוב תחתון פלוטקין (פלוטקין) עבור המספר המינימלי של סיביות בדיקה רבְּ- n³ 2d − 1,

בינארי (קוד m, n) נקרא קוד קבוצתי אם מילות הקוד שלו יוצרות קבוצה.

שימו לב שהקבוצה של כל המילים הבינאריות באורך m יוצרת קבוצה קומוטטיבית עם פעולת חיבור מודולו 2 מבחינה קואורדינטות, שבה מתקיים היחס a a. כתוצאה מכך, קבוצת מילות ההודעה a באורך m היא קבוצה קומוטטיבית.

קוד חסימה נקרא קְבוּצָה, אם מילות הקוד שלה יוצרות קבוצה.

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

זה נובע מהקשר ד(ב אני ,ב י ) = w(b אני + ב י ).

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

שורות שגיאה כאלה מתרגמות מילת קוד אחת לאחרת.

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

קבוצה של כל המילים הבינאריות a = א 1 ... א M אורך Mיוצר קבוצה אבלית (קומוטטיבית) ביחס לחיבור סיבי.

לתת ה - קידוד m×n-מטריקס שיש לו M × M-תת-מטריקס עם דטרמיננט שאינו אפס, למשל, זהות. ואז המיפוי a → a Eמתרגם קבוצה של כל המילים הבינאריות באורך M לקבוצה של מילות קוד באורך נ.

הבה נניח כי אז בשביל נקבל

כְּלוֹמַר לכן, מיפוי אחד לאחד של קבוצת מילים בינאריות באורך M באמצעות מטריצה נתונה ה שומר על המאפיינים של פעולת קבוצה, כלומר מילות הקוד יוצרות קבוצה.

מאפיין קוד קבוצתי: מרחק הקוד המינימלי בין וקטורי קוד שווה למשקל המינימלי של וקטורים שאינם אפס. משקל וקטור הקוד שווה למספר האחדים בשילוב הקוד.

נוח לציין קודי קבוצה באמצעות מטריצות, שהממד שלהן נקבע על ידי הפרמטרים k ו-n. מספר השורות הוא k, ומספר העמודות הוא n = k+m.

הקודים שנוצרו על ידי מטריצות אלו נקראים (n, k)-קודים, והמטריצות המתאימות נקראות מחוללות (גנרטורים).

עמוד 1

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

מרחק האמינג d (u, v) בין שתי מילים u ו-v באורך זהה שווה למספר הספרות המתפצלות של מילים אלו. הוא משמש בתורת קודי הבלוק (V.

באמצעות המאפיינים המטריים של מרחק ההאמינג, מאמתים ישירות ש-/l הוא מטרי על Xt, אך אינו מטרי על קבוצת הרצפים המעורבים-מחזוריים.

פונקציית קרבה זו מקבילה למרחק האמינג.

המדד p באלגוריתם KLOP מוגדר על ידי מרחק ההאמינג.

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

השוואה של תת-הקבוצות המטושטשות B ו-B3, דרגות הטשטוש, כמו גם מרחק ההאמינג מראה שתת-הקבוצות המטושטשות הנבדקות שונות. עם זאת, אם ניקח כערך המחושב את האלמנט m2 G Uz, שמידתו שייכת לקבוצת המשנה המטושטשת המתקבלת היא מקסימלית, אזי ניתן להצדיק את השימוש ביחס המטושטש R המחושב בצורה זו. יחד עם העובדה שבגישה זו ניתן לתאר את חוסר הלינאריות של הקשר בין הטמפרטורה המקסימלית באזור השני של הכור לבין קצב זרימת ההיתוך של הפוליאתילן, שיטה זו אינה לוקחת בחשבון את האופי הלא נייח של הכור. תהליך השגת LDPE, הקשור לשינויים במאפייני התהליך הטכנולוגי.

פונקציית ההעברה של קוד זה מצביעה על כך שיש נתיב בודד עם מרחק Hamming d - מהנתיב הכל-אפס, שמתמזג עם נתיב הכל-אפס בצומת נתון. מתרשים המצב המוצג באיור. 8.2.6, או דיאגרמת הסבכה המוצגת באיור. 8.2.5, ברור שהנתיב מ-d6 הוא acbe. שוב מתרשים המצב או הסריג אנו רואים שהנתיבים הללו הם acdbe ו-acbcbe. האיבר השלישי ב- (8.1.2) מציין שיש ארבעה נתיבים עם מרחק d 0 וכן הלאה. לפיכך, פונקציית ההעברה נותנת לנו את מאפייני המרחק של הקוד הקונבולוציוני.

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

בספרו של סטפן צווייג "השעות היפות של האנושות" יש סיפור נפלא "הגאונות של לילה אחד" על קצין הצבא הצרפתי Rouget de Lisle, שכתב את "La Marseillaise" המפורסם במהלך לילה אחד בלהט ההשראה שאחזה בו. זה היה ב-1792 במרסיי המהפכנית. השיר התפשט ברחבי צרפת תוך מספר ימים, זכה במהירות לפופולריות עצומה ברחבי העולם והפך לאחר מכן להמנון הלאומי של הרפובליקה הצרפתית. ההיסטוריה שימרה את השם Rouget בזיכרון הדורות הודות לשיר היחיד הזה.

באנלוגיה, ניתן לכנות את ריצ'רד האמינג "גאון של רעיון אחד". הוא ניסח אותו ב-1950 במאמרו המדעי היחיד שהוקדש לקודי תיקון שגיאות. המאמר הכיל בנייה של קוד בלוק המתקן שגיאות בודדות המתרחשות במהלך העברת הודעות.

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

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

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

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

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

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

במאמר זה, שאנון, מצטט מחקר שנעשה בשנת 1947 על ידי עמיתו למעבדות בל, ריצ'רד האמינג, תיאר כדוגמה קוד פשוט באורך 7 שתיקן את כל השגיאות הבודדות. פרסום החומר המקורי של האמינג נדחה עד אפריל 1950 מסיבות פטנט. יש לציין שהדוגמה של קוד תיקון שגיאות שניתנה במאמר המוזכר של שאנון יזמה את המחקר של מדען אמריקאי אחר, M. E. Golay. גולאי, ללא תלות בהאמינג, גילה קודים שמתקנים שגיאות בודדות. בשנת 1949 (כלומר, לפני האמינג) הוא פרסם הערה קצרה (חצי עמוד בלבד) על תוצאותיו בהליכי ה-IEEE. בהערה זו, הוא התייחס לא רק לקודים בינאריים, אלא גם לקודים כלליים, שצירופים שלהם שייכים לשדה סופי (קבוצה מתמטית של יסודות עם פעולות מסוימות של חיבור, חיסור, חילוק וכפל) עם יסודות pn (p הוא ראשוני , ו-n הוא מספר שלם).

יש לציין שמספר רעיונות בסיסיים של תורת התקשורת היו ידועים כתוצאות מתמטיות פרטיות עוד לפני שהחלו ליישם אותם על ידי מדענים הפותרים בעיות של העברת מסרים בערוצי תקשורת. בספרו "תורת הקידוד האלגברית", אמר מומחה אמריקאי בולט בתחום תורת הקידוד, E. Berlekamp, הערה מעניינת מאוד. הוא ציין כי העיצוב של קודי האמינג תואר בהקשר אחר עוד בשנת 1942 על ידי המתמטיקאי האמריקאי המפורסם ר.א. פישר, בעבודה שהוקדשה לתיאוריית ניתוח הגורמים (אחד מענפי הסטטיסטיקה המתמטית) והקשר שלה עם המתמטי. תורת הקבוצות. אגב, המשפט של V.A. Kotelnikov, המציין את האפשרות לייצוג אותות אנלוגיים בצורה דיגיטלית, התגלה גם כאחת התוצאות המתמטיות החלקיות של תורת אינטרפולציית הפונקציות בתחילת המאה העשרים על ידי המתמטיקאים האנגלים E.T. ו-J.M. Whitker. יש להדגיש כי לא פישר ולא המדענים האנגלים המוזכרים קשרו את תוצאותיהם עם הבעיות החשובות ביותר לעולם המודרני של העברת מידע בערוצי תקשורת.

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

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

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

בביטוי זה, ניתן לתקן את מספר השגיאות e על ידי קוד בלוק מתקן באורך N, בעל M צירופי קוד (CjN הוא המקדם הבינומי).

עבודתו של המינג מילאה תפקיד מפתח בפיתוח של תורת הקידוד ועוררה מחקר מקיף שבוצע בשנים שלאחר מכן. בשנת 1956, דייוויד סלפיאן היה הראשון שהציג את התיאוריה של קוד בדיקת זוגיות על בסיס מתמטי רציני. שינוי גדול בתחום תורת הקידוד התרחש כאשר המדען הצרפתי א. הוקוונגהם (1959) והאמריקאים R. K. Bose ו-D. K. Roy-Chowdhury (1960) מצאו מחלקה גדולה של קודים (קודי BCH) המתקנים שגיאות מרובות. החוקרים האמריקאים I. S. Reed and G. Solomon (1960) מצאו מחלקה של קודים לערוצים לא-בינאריים הקשורים לקודי BCH.

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

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

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

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

למרחק האמינג יש את המאפיינים של מדד, המקיים את התנאים הבאים:

מרחק הפטיש בביואינפורמטיקה ובגנומיקה

סִפְרוּת

ריצ'רד וו. האמינג. קודי איתור שגיאות ותיקון שגיאות, Bell System Technical Journal 29(2):147-160, 1950.
ריצ'רד בליכוט. תיאוריה ופרקטיקה של קודי בקרת שגיאות. מ., "מיר", 1986

קישורים

ריצ'רד האמינג ותחילתה של תורת הקידוד // מוזיאון מחשבים וירטואליים

קרן ויקימדיה. 2010.

ראה מה זה "מרחק המינג" במילונים אחרים:

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

מרחק קוד- מרחק חבטות מינימלי שנלקח על כל הרצועות של מילות קוד שונות בקוד אחיד. [אוסף תנאים מומלצים. גיליון 94. תורת העברת המידע. האקדמיה למדעים של ברית המועצות. ועדת מינוח טכני. 1979] תורת הנושאים... ... מדריך למתרגם טכני

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

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

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