מרחק המינג

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

מרחק המינג בין המחרוזת 1011101 למחרוזת 1001001 הוא 2.
מרחק המינג בין המחרוזת 2143896 למחרוזת 2233796 הוא 3.
מרחק המינג בין המחרוזת "toned" למחרוזת "roses" הוא 3.

משקל המינג של מחרוזת הוא מרחק המינג שלה ממחרוזת בעלת אותו אורך שכולה אפסים. למעשה זהו מספר הסימנים שאינם אפס. במחרוזת סיביות זהו מספר הסיביות שערכן 1. דוגמה: משקל המינג של המחרוזת 11101 הוא 4.

מרחק המינג קרוי על שמו של ריצ'רד המינג, שהציג רעיון זה במאמרו הבסיסי error-detecting and error-correcting codes משנת 1950, מאמר שבו הציע את קוד המינג.

מאפיינים

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

את מרחק המינג בין שתי מחרוזות ניתן לראות גם כהפרש ביניהן, על-פי הגדרה נאותה של פעולת החיסור. לשתי מחרוזות בינאריות ההפרש הוא מספר הביטים הדלוקים בתוצאה של פעולת XOR ביניהן, או מספר הביטים הדלוקים לאחר חיסור רגיל במרחב הווקטורי $\mathbb {Z} _{2}^{n}$ כאשר מזהים את התו 0 עם המספר 0 (מודולו 2) ואת התו 1 עם הספרה 1 (מודולו 2).

ראו גם

לקריאה נוספת

Hamming, Richard W. (1950). "Error detecting and error correcting codes" (PDF). Bell System Technical Journal. 29 (2): 147–160. doi:10.1002/j.1538-7305.1950.tb00463.x. MR 0035935.
Pilcher, C. D.; Wong, J. K.; Pillai, S. K. (במרץ 2008). "Inferring HIV transmission dynamics from phylogenetic sequence relationships". PLoS Med. 5 (3): e69. doi:10.1371/journal.pmed.0050069. PMC 2267810. PMID 18351799. {{cite journal}}: (עזרה)
Wegner, Peter (1960). "A technique for counting ones in a binary computer". Communications of the ACM. 3 (5): 322. doi:10.1145/367236.367286.
Ayala, Jose (2012). Fast Propagation of Hamming and Signal Distances for Register-Transfer Level Datapaths. Integrated Circuit and System Design. Vol. 1. p. 62.
MacKay, David J. C. (2003). Information Theory, Inference, and Learning Algorithms. Cambridge: Cambridge University Press. ISBN 0-521-64298-1.

קישורים חיצוניים

מרחק המינג, באתר MathWorld (באנגלית)

Read other articles:

Ioannis Maniatis

Ioannis Maniatis Informasi pribadiNama lengkap Ioannis ManiatisTanggal lahir 12 Oktober 1986 (umur 37)Tempat lahir Livadeia, YunaniTinggi 1,78 m (5 ft 10 in)Posisi bermain BekInformasi klubKlub saat ini OlympiakosNomor 2Karier junior2002–2003 AO ThivaKarier senior*Tahun Tim Tampil (Gol)2003–2011 Panionios 164 (8)2011– Olympiacos 31 (0)Tim nasional‡2006-2007 Yunani U-21 14 (1)2010- Yunani 8 (0) * Penampilan dan gol di klub senior hanya dihitung dari liga domestik&#...

Executive Order 10925

Establishing the President's Committee on Equal Employment Opportunity Executive Order 10925, signed by President John F. Kennedy on March 6, 1961, required government contractors, except in special circumstances, to take affirmative action to ensure that applicants are employed and that employees are treated during employment without regard to their race, creed, color, or national origin. It established the President's Committee on Equal Employment Opportunity (PCEEO), which was chaired by t...

Pemilihan umum legislatif Indonesia 1987

Pemilihan umum legislatif Indonesia 19871982199223 April 1987 (1987-04-23)400 kursi Dewan Perwakilan RakyatKandidat Partai pertama Partai kedua Partai ketiga Ketua Sudharmono Jailani Naro Soerjadi Partai Golkar PPP PDI Pemilu sebelumnya 242 kursi, 64,34% 94 kursi, 27,78% 24 kursi, 7,88% Kursi yang dimenangkan 299 61 40 Perubahan kursi 57 33 16 Suara rakyat 62.783.680 13.701.428 9.384.708 Persentase 73,11% 15,96% 10,93% Swing 8,77% 11,82% 3,05% Logo...

Энциклопедия Криворожья

Энциклопедия Криворожьяукр. Енциклопедія Криворіжжя Автор сост. В. Ф. Бухтияров Жанр энциклопедия Язык оригинала украинский Оригинал издан 2005 Оформление формат: 60x90 1/8 Издатель Явва Носитель книга ISBN 966-96328-1-1 Внешние изображения Редакция газеты «Червоный го...

Grant Williams

Questa voce sull'argomento cestisti statunitensi è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Grant Williams Grant Williams con la maglia di Tennessee Nazionalità Stati Uniti Altezza 198 cm Peso 107 kg Pallacanestro Ruolo Ala grande Squadra Charlotte Hornets Carriera Giovanili Providence Day School2016-2019 Tenn. Volunteers104 (1.633) Squadre di club 2019-2023 Boston Celtics28...

Ferdinando Rebecchi

Questa voce sull'argomento calciatori italiani è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Ferdinando Rebecchi Nazionalità Italia Calcio Ruolo Ala Carriera Squadre di club1 1919-1921 Parma19 (4)1921-1922 Spezia8 (1)1922-1926 Parma46 (13) 1 I due numeri indicano le presenze e le reti segnate, per le sole partite di campionato.Il simbolo → indica un trasferimento in prestito. ...

ロバート・デ・ニーロ

ロバート・デ・ニーロRobert De Niro 2011年のデ・ニーロ生年月日 (1943-08-17) 1943年8月17日（80歳）出生地アメリカ合衆国・ニューヨーク州ニューヨーク市身長 177 cm職業俳優、映画監督、映画プロデューサージャンル映画、テレビドラマ活動期間 1963年 -配偶者ダイアン・アボット（1976年 - 1988年）グレイス・ハイタワー（1997年 - ）主な作品『ミーン・ストリート』（1973年）...

Jakob Piil

Jakob PiilJakob Piil lors de la HEW Cyclassics 2005InformationsNaissance 9 mars 1973 (51 ans)OdenseNationalité danoiseDistinction Cycliste danois de l'année (2002)Équipes professionnelles 09.1996-12.1996RDM-New Systems (stagiaire)1997RDM-Asfra-Sitra1998-1999Acceptcard2000Memory Card-Jack & Jones2001-2002CSC-Tiscali2003-2006CSC2007T-MobilePrincipales victoires 1 championnat Champion du Danemark sur route (2001)1 classiqueParis-Tours (2002)1 étape de grand tourTour de France (1 ét...

Medial tarsal arteries

Medial tarsal arteriesAnterior tibial artery, dorsalis pedis artery and the muscles and bones of the leg - anterior view. (Medial tarsal visible but not labeled, at bottom right.)DetailsSourceArteria dorsalis pedisIdentifiersLatinarteriae tarsales medialesTA98A12.2.16.050TA24716FMA70818Anatomical terminology[edit on Wikidata] The medial tarsal arteries are two or three small branches which ramify on the medial border of the foot and join the medial malleolar network. References This artic...

Kafé Malam

Kafé MalamPrancis: Le Café de nuitSenimanVincent van GoghTahun1888 (1888)F463MediumMinyak di atas kanvasUkuran72.4 cm × 92.1 cm (28.5 in × 36.3 in)LokasiYale University Art Gallery, New Haven Kafé Malam (bahasa Prancis: Le Café de nuit) adalah sebuah lukisan minyak yang dibuat oleh seniman Belanda Vincent van Gogh pada September 1888 di Arles.[1] Judulnya dicantumkan di bagian kanan bawah bersama dengan tanda tangannya. Lukisan ...

نادي الزيتون (السعودية)

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (يوليو 2016) نادي الزيتون السعودي الألوان الأخضر و الأبيض تأسس عام 1395 هـ الملعب سبت العلاية السعودية البلد السعودي�...

Buddhist art

Artistic practices influenced by Buddhism Buddhist artRepresentation of the Buddha in the Greco-Buddhist art of Gandhara, 1st century CESeated Maitreya sculpture, Kathmandu Valley, Nepal, c. 1250–1350Thangka of Shakyamuni Buddha, Tibet, c. 18th century Part of a series onBuddhism Glossary Index Outline History Timeline The Buddha Pre-sectarian Buddhism Councils Silk Road transmission of Buddhism Decline in the Indian subcontinent Later Buddhists Buddhist modernism DharmaConcepts...

Dharmendra

DharmendraLahirDharam Singh Deol8 Desember 1935 (umur 88)Phagwara, Punjab, IndiaTempat tinggalMumbai, IndiaNama lainDharminderPekerjaanactor, producer, politicianPartai politikBJPSuami/istriParkash Kaur (1954 - present) Hema Malini (1980 - sekarang)AnakSunny Deol (Ajay Singh Deol) Bobby Deol (Vijay Singh Deol) Ajeeta Deol Vijeta Deol Esha Deol Ahana Deol Dharam Singh Deol (bahasa Punjabi: ਧਰਮਿੰਦਰ ਸਿੰਘ ਦਿਉਲ), lahir 8 Desember 1935), dikenal sebagai ...

White perch

Species of fish This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: White perch – news · newspapers · books · scholar · JSTOR (February 2015) (Learn how and when to remove this message) White perch Conservation status Least Concern (IUCN 3.1)[1] Scientific classification Domain: Eukaryota Kingdom: ...

Maksim Kiselyov

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Desember 2023. Maksim KiselyovInformasi pribadiNama lengkap Maksim Anatolyevich KiselyovTanggal lahir 2 Februari 1991 (umur 33)Tinggi 1,75 m (5 ft 9 in)Posisi bermain GelandangInformasi klubKlub saat ini FC Volga TverKarier senior*Tahun Tim Tampi...

Auguste Marie Henri Picot de Dampierre

General during the French Revolution Auguste Marie Henri Picot, Marquis de Dampierre Auguste Marie Henri Picot de Dampierre (French pronunciation: [oɡyst maʁi ɑ̃ʁi piko də dɑ̃pjɛʁ]; 19 August 1756 – 9 May 1793), styled the Marquis de Dampierre and usually known as Dampierre [dɑ̃.pjɛʁ], was a French general during the time of the French Revolution. He served in many of the early battles of the War of the First Coalition, and was killed in action in 1793. His nam...

First ministry of Armand-Emmanuel du Plessis de Richelieu

First Richelieu ministryCabinet of FranceArmand-Emmanuel du Plessis de RichelieuDate formed26 September 1815Date dissolved29 December 1818People and organisationsHead of stateLouis XVIII of FranceHead of governmentArmand-Emmanuel du Plessis de RichelieuHistoryPredecessorMinistry of Charles-Maurice de Talleyrand-PérigordSuccessorMinistry of Jean-Joseph Dessolles The First ministry of Armand-Emmanuel du Plessis de Richelieu was formed on 26 September 1815 after the dismissal of the Ministry of...

Enguerrand VII de Coucy

14th-century French nobleman This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Enguerrand VII de Coucy – news · newspapers · books · scholar · JSTOR (February 2015) (Learn how and when to remove this message) Enguerrand VIILord of CoucyArms of Enguerrand VII, Lord of Coucy, KGBornEnguerrand de Coucy1340Coucy C...

Umm Ghuwailina

District in Ad-Dawhah, QatarUmm Ghuwailina أم غويلينةDistrictUmm GhuwailinaShow map of DohaUmm GhuwailinaShow map of QatarCoordinates: 25°16′33″N 51°32′45″E / 25.275825°N 51.545898°E / 25.275825; 51.545898Country QatarMunicipalityAd-DawhahZoneZone 27District no.24Area • Total1.4 km2 (0.5 sq mi)Elevation[1]13 m (43 ft)Population • Total26,069 • Density19,000/km2 (48,000/sq mi)...

Непальский конгресс

Непальский конгресснепальск. नेपाली कांग्रेस Лидер Шер Бахадур Деуба Основатель Б. П. Коирала Основана 9 апреля 1950 Штаб-квартира Катманду, Непал Страна Непал Идеология ЛевоцентризмСоциал-демократияДемократический социализм Интернационал Социалистический и...