Hamming mesafesi. Büyük petrol ve gaz ansiklopedisi

Uzunluktaki ikili kelimelerden oluşan bir sette a ve b kelimeleri arasındaki m mesafesi d(a,b), bu kelimelerin eşleşmeyen konumlarının sayısıdır, örneğin: a = 01101 ve b = 00111 kelimeleri arasındaki mesafe 2'dir.

Bu şekilde tanımlanan kavrama Hamming mesafesi adı verilmektedir.

Aşağıdaki mesafe aksiyomlarını karşılar:

1) d(a,b)  0 ve d(a,b)=0 ancak ve ancak a = b ise;

2) d(a,b) = d(b,a) ;

3) d(a,b) + d(b,c)  d(a,c) (üçgen eşitsizliği).

Bir a kelimesinin ağırlığı w(a), koordinatları arasındaki birlerin sayısıdır. O halde a ve b kelimeleri arasındaki mesafe, toplamlarının a b'sinin ağırlığıdır: d(a,b)=w(a b) , burada  sembolü koordinat bazında modülo 2 toplama işlemini belirtir. Sezgisel olarak kod, hata tespitine ve düzeltmeye daha uygundur, kod sözcükleri ne kadar farklıysa. Hamming mesafesi kavramı bunu açıklığa kavuşturmamızı sağlar.

Teorem Bir kodun k (veya daha az) konumdaki hataları tespit edebilmesi için kod sözcükler arasındaki en küçük mesafenin  k+1 olması gerekli ve yeterlidir.

Bu teoremin ispatı aşağıdaki ifadenin ispatına benzer.

Teorem. Kodun k (veya daha az) konumdaki tüm hataları düzeltebilmesi için kod sözcükleri arasındaki en küçük mesafenin  2k + 1 olması gerekli ve yeterlidir.

32. Kodların düzeltme yeteneği ile ilgili teorem.

Hataları otomatik olarak düzeltebilen kodlara kendi kendini düzelten kodlar denir. Tek hataları düzeltmek üzere tasarlanmış, kendi kendini düzelten bir kod oluşturmak için bir kontrol basamağı yeterli değildir. Aşağıda görülebileceği gibi, kontrol bitlerinin sayısı k, 2k≥k+m+1 veya k≥log2(k+m+1) eşitsizliğini sağlayacak şekilde seçilmelidir; burada m, ana ikili bitlerin sayısıdır kod sözcüğünden. Şu anda ikili blok düzeltme kodları büyük ilgi görüyor. Bu tür kodlar kullanıldığında bilgiler aynı uzunluktaki bloklar halinde iletilir ve her blok birbirinden bağımsız olarak kodlanır ve kodu çözülür. Hemen hemen tüm blok kodlarında karakterler bilgi ve doğrulama olarak ikiye ayrılabilir.

Kendi kendini düzelten kodların temel özellikleri şunlardır:

1. İzin verilen ve yasaklanan kombinasyonların sayısı. Eğer n bloktaki sembollerin sayısıysa, r bloktaki kontrol sembollerinin sayısıdır, k bilgi sembollerinin sayısıdır, bu durumda 2n olası kod kombinasyonlarının sayısıdır, 2k izin verilen kod kombinasyonlarının sayısıdır, 2n −2k yasaklanmış kombinasyonların sayısıdır.

2. Kod artıklığı. rn değerine düzeltme kodunun fazlalığı denir.

3. Minimum kod mesafesi. Minimum kod mesafesi d, izin verilen bir kombinasyondan diğerine geçiş için gereken minimum bozuk sembol sayısıdır.

4. Tespit edilen ve düzeltilen hataların sayısı. Eğer g kodun düzeltebileceği hata sayısı ise d≥2g+1 olması gerekli ve yeterlidir.

5. Kodların düzeltme yetenekleri.

33. Matris kodlaması. Grup kodları.

Kodlama şemasını açıkça belirtirken ( m, n)-kodu 2 m'lik kod sözcüklerini belirtmelidir ki bu çok verimsizdir.

Bir kodlama şemasını tanımlamanın ekonomik bir yolu matris kodlama tekniğidir.

Daha önce her kodlama şeması, uzunluk kod sözcüğünü belirten tablolarla açıklanıyordu. N uzunluktaki her kaynak kelime için M. Uzun bloklar için bu yöntem büyük miktarda bellek gerektirir ve bu nedenle pratik değildir. Örneğin, ( 16, 33 ) kodu 33 * 2 16 = 2,162,688 bit gerektirecektir.

Çok daha az bellek gerektirir matris kodlaması. İzin vermek e boyut matrisi m×n e ij elemanlarından oluşan, burada Ben satır numarasıdır ve J - sütun numarası. Matris elemanlarının her biri e ben 0 veya 1 olabilir. Kodlama işlem tarafından uygulanır. b = aE veya kod sözcüklerinin vektörler olarak, yani boyutun satır matrisleri olarak kabul edildiği durumlarda 1×n.

Kodlama aynı kod sözcüğünü farklı kaynak iletilere atamamalıdır. Bunu başarmanın basit bir yolu, M matris sütunları birim matris oluşturduk. Herhangi bir vektör kimlik matrisi ile çarpıldığında aynı vektör elde edilir; dolayısıyla farklı mesaj vektörleri sistematik kodun farklı vektörlerine karşılık gelir.

Matris kodları da denir doğrusal kodlar. Doğrusal için (n - r, n)-minimum Hamming mesafeli kodlar D var Plotkin alt sınırı (Plotkin) minimum kontrol biti sayısı için R en n³ 2d − 1,

İkili ( Bir m, n) kodu, eğer kod sözcükleri bir grup oluşturuyorsa, grup kodu olarak adlandırılır.

m uzunluğundaki tüm ikili kelimelerin kümesinin, a a ilişkisinin geçerli olduğu, koordinat bazında toplama modulo 2 işlemiyle değişmeli bir grup oluşturduğuna dikkat edin. Sonuç olarak, m uzunluğundaki a mesaj kelimeleri kümesi değişmeli bir gruptur.

Blok kodu çağrılır grup, kod kelimelerinin bir grup oluşturması durumunda.

Kod bir grup kodu ise, iki kod kelimesi arasındaki en küçük mesafe, sıfır olmayan kelimenin en küçük ağırlığına eşittir.

Bu ilişkiden şu sonuç çıkıyor d(b Ben ,B J ) = w(b Ben + B J ).

Bir joker karakter kodu kullanıldığında, yalnızca kod sözcüklerine tam olarak eşit olan hata dizelerine karşılık gelen hatalar tespit edilmez.

Bu tür hata satırları bir kod sözcüğünü diğerine çevirir.

Dolayısıyla bir hatanın fark edilmeden kalma olasılığı, kod sözcüklerine eşit olan tüm hata dizilerinin olasılıklarının toplamına eşittir.

Tüm ikili sözcüklerin kümesi bir = bir 1 ... A M uzunluk M bitsel toplamaya göre bir Abelian (değişmeli) grup oluşturur.

İzin vermek e - kodlama m×n-bir matris M × M- sıfırdan farklı bir determinantı olan bir alt matris, örneğin kimlik. Daha sonra haritalama bir → bir E uzunluktaki tüm ikili sözcüklerden oluşan bir grubu çevirir M uzunluğundaki bir grup kod sözcüğüne N.

O zaman şunu elde ettiğimizi varsayalım:

yani Bu nedenle, uzunluktaki ikili kelimelerden oluşan bir grubun bire bir eşlenmesi M belirli bir matrisi kullanarak e bir grup işleminin özelliklerini korur; bu, kod sözcüklerinin bir grup oluşturduğu anlamına gelir.

Grup kodu özelliği: Kod vektörleri arasındaki minimum kod mesafesi, sıfır olmayan vektörlerin minimum ağırlığına eşittir. Kod vektörünün ağırlığı, kod kombinasyonundaki birlerin sayısına eşittir.

Boyutu k ve n parametreleriyle belirlenen matrisleri kullanarak grup kodlarını belirlemek uygundur. Satır sayısı k ve sütun sayısı n = k+m'dir.

Bu matrisler tarafından oluşturulan kodlara (n, k)-kodları denir ve karşılık gelen matrislere jeneratörler (üreticiler) adı verilir.

Sayfa 1

Eşit uzunluktaki iki dizi arasındaki Hamming mesafesi, eşleşmeyen elemanların işgal ettiği konumların sayısına karşılık gelir. Farklı uzunluktaki diziler durumunda Hamming mesafesi, eşleşmeyen elemanların işgal ettiği minimum konum sayısı olarak tanımlanır.

Aynı uzunluktaki u ve v kelimeleri arasındaki Hamming mesafesi d(u,v), bu kelimelerin ıraksak rakam sayısına eşittir. Blok kod teorisinde kullanılır (V.

Hamming mesafesinin metrik özelliklerini kullanarak, /l'nin Xt üzerinde bir metrik olduğu, ancak karışık periyodik diziler kümesi üzerinde bir metrik olmadığı doğrudan doğrulanır.

Bu yakınlık fonksiyonu Hamming mesafesine eşdeğerdir.

KLOP algoritmasındaki metrik p, Hamming mesafesi ile belirtilir.

Arama prosedürü Hamming mesafesinin sıfır olduğu bir konum bulabilirse sorun çözülecektir.

B ve B3 bulanık alt kümelerinin, bulanıklık derecelerinin ve Hamming mesafesinin karşılaştırılması, söz konusu bulanık alt kümelerin farklı olduğunu göstermektedir. Bununla birlikte, elde edilen bulanık alt kümeye ait derecesi maksimum olan m2 G Uz öğesini hesaplanan değer olarak alırsak, bu şekilde hesaplanan R bulanık ilişkisinin kullanımı haklı gösterilebilir. Bu yaklaşımla, reaktörün ikinci bölgesindeki maksimum sıcaklık ile polietilen eriyik akış hızı arasındaki ilişkinin doğrusal olmayanlığını tanımlamanın mümkün olduğu gerçeğiyle birlikte, bu yöntem, reaktörün sabit olmayan doğasını hesaba katmaz. teknolojik sürecin özelliklerindeki değişikliklerle ilişkili olan LDPE'yi elde etme süreci.

Bu kodun transfer fonksiyonu, tamamı sıfır olan yoldan Hamming mesafesi d - olan ve belirli bir düğümde tamamı sıfır olan yolla birleşen tek bir yol olduğunu gösterir. Şekil 2'de gösterilen durum diyagramından. 8.2.6 veya Şekil 8.2.6'da gösterilen kafes diyagramı. 8.2.5'te d6'dan gelen yolun acbe olduğu açıktır. Yine durum diyagramından veya kafesten bu yolların acdbe ve acbcbe olduğunu görüyoruz. (8.1.2)'deki üçüncü terim, mesafesi d 0 vb. olan dört yol olduğunu gösterir. Böylece transfer fonksiyonu bize evrişimli kodun uzaklık özelliklerini verir.

Bu sonuç, tamamı sıfırlardan (/0) oluşan bir yolun alınan diziden d3 Hamming mesafesine sahip olduğu, buna karşılık /1'den oluşan bir yolun alınan yoldan d5 Hamming mesafesine sahip olduğu gözlemiyle tutarlıdır. Dolayısıyla Hamming mesafesi, zor karar çözme için eşdeğer bir ölçümdür.

Stefan Zweig'in "İnsanlığın En Güzel Saatleri" kitabında, ilhamın ateşiyle bir gecede ünlü "La Marseillaise"yi yazan Fransız subayı Rouget de Lisle'nin harika bir hikayesi olan "Bir Gecenin Dehası" var. Bu 1792'de devrimci Marsilya'daydı. Şarkı birkaç gün içinde Fransa'nın her yerine yayıldı, hızla dünya çapında büyük bir popülerlik kazandı ve ardından Fransız Cumhuriyeti'nin milli marşı haline geldi. Tarih, bu tek şarkı sayesinde Rouget adını gelecek nesillerin anısına yaşattı.

Benzer şekilde, Richard Hamming'e "tek fikrin dehası" denilebilir. Bunu 1950'de hata düzeltme kodlarına ayrılmış tek bilimsel makalesinde formüle etti. Makale, mesaj iletimi sırasında meydana gelen tek hataları düzelten bir blok kodun yapımını içeriyordu.

Richard Hamming sürekli olarak aktif bilimsel araştırmalarla meşguldü, ancak hacmi açısından bilimsel çalışmalarının önemsiz bir yüzdesini oluşturan bilgi teorisi alanındaki tek çalışması ün kazandı. Bu makale hızla dünya çapında ün kazandı ve ona hak ettiği şöhreti getirdi.

Nasıl ki Faraday ve Maxwell'in keşiflerini telekomünikasyon alanında hayatımızı değiştiren sayısız icat takip ettiyse, Claude Shannon ve Vladimir Kotelnikov'un bilgi teorisini, potansiyel gürültü bağışıklığı teorisini yaratmasının ardından da, telekomünikasyon alanında yeni fırsatlar açıldı. telekomünikasyonun gelişimi. Bilgi teorisinin en önemli bölümlerinden biri Hamming'in temellerini attığı kodlama teorisidir.

Shannon, iletim hızının kapasitesini aşmaması durumunda bilginin bir iletişim kanalı üzerinden hatasız olarak iletilebileceğini tespit etti. Ancak Shannon'ın kanıtı yapıcı değildi. Kendisi ve başka bir Amerikalı bilim adamı S. O. Rice tarafından yapılan daha sonraki çalışmalar, rastgele seçilen hemen hemen her kodun, mesaj alımı için gürültü bağışıklığının teorik sınırına ulaşılmasına izin verdiğini gösterdi. Bununla birlikte, böyle bir kodun kod çözme karmaşıklığı yüksekti: alınan kod kombinasyonunun kodunu çözmek için gereken işlem sayısı, uzunluğuyla birlikte katlanarak arttı.

Hamming, artıklık ve basit kod çözme ile kodlar oluşturmak için yapıcı bir yöntem öneren ilk kişiydi. Onun çalışması, bu alanda daha sonra yapılacak çalışmaların çoğunun yönünü önceden belirledi.

Onun onuruna, Elektrik ve Elektronik Mühendisleri Enstitüsü, bilgi teorisine önemli katkılarda bulunan bilim adamlarını ödüllendirmek amacıyla bir madalya kurdu.

Sinyal işleme sırasında hataları düzeltebilen kodlar (dijital bilgisayarlardaki iletişim kanallarında vb.), Hamming tarafından, Shannon'ın bu konuda teori için sağlam bir temel oluşturan ünlü "Matematiksel İletişim Teorisi" makalesinin yayınlandığı 1948'den önce bile önerildi. alan.

Bu yazıda Shannon, 1947'de Bell Laboratuarlarından meslektaşı Richard Hamming tarafından yapılan araştırmaya atıfta bulunarak, örnek olarak tüm hataları düzelten 7 uzunluğunda basit bir kodu tanımladı. Hamming'in orijinal materyalinin yayınlanması, patent nedenleriyle Nisan 1950'ye ertelendi. Shannon'ın söz konusu makalede verdiği hata düzeltme kodu örneğinin, bir başka Amerikalı bilim adamı M. E. Golay'ın araştırmasını başlattığını da belirtelim. Golay, Hamming'den bağımsız olarak tek hataları düzelten kodları keşfetti. 1949'da (yani Hamming'den önce), IEEE Tutanakları'nda sonuçları hakkında kısa bir not (sadece yarım sayfa) yayınladı. Bu notta, yalnızca ikili kodları değil, aynı zamanda kombinasyonları sonlu bir alana (belirli toplama, çıkarma, bölme ve çarpma işlemlerini içeren matematiksel bir öğe kümesi) ait pn öğeleriyle (p bir asaldır) genel kodları da ele aldı. ve n bir tamsayıdır).

İletişim teorisinin bir takım temel fikirlerinin, iletişim kanalları üzerinden mesaj iletme problemlerini çözen bilim adamları tarafından uygulanmaya başlamadan önce bile özel matematiksel sonuçlar olarak bilindiğini belirtmek gerekir. Kodlama teorisi alanında önde gelen Amerikalı uzmanlardan E. Berlekamp, “Cebirsel Kodlama Teorisi” adlı kitabında oldukça ilginç bir açıklama yaptı. Hamming kodlarının tasarımının, 1942'de ünlü Amerikalı matematikçi R. A. Fisher tarafından, faktör analizi teorisine (matematiksel istatistiğin dallarından biri) ve bunun matematikle bağlantısına adanmış bir çalışmada farklı bir bağlamda tanımlandığını belirtti. Grup teorisi. Bu arada, analog sinyalleri dijital biçimde temsil etme olasılığını gösteren V. A. Kotelnikov teoremi, yirminci yüzyılın başlarında İngiliz matematikçiler E. T. ve J. M. Whitker tarafından fonksiyon enterpolasyonu teorisinin kısmi matematiksel sonuçlarından biri olarak keşfedildi. Ne Fisher'ın ne de adı geçen İngiliz bilim adamlarının, sonuçlarını modern dünyanın iletişim kanalları aracılığıyla bilgi aktarımının en önemli sorunlarıyla ilişkilendirmediği vurgulanmalıdır.

Wolfgang Goethe şunları söyledi: “Sadece bilgi edinmek yeterli değil; Ona bir uygulama bulmam lazım. Sadece dilemek yeterli değildir; yapma ihtiyacı". Teori ve teknoloji için... iletişim, Kotelnikov teoremi ve Hamming kodları olağanüstü bir öneme sahiptir, çünkü onlar sayesinde, yirminci yüzyılın sonunda telekomünikasyonda devrim yaratan ve dolayısıyla mühendislere dijital sistemler yaratma konusunda açık bir perspektif açıldı. haklı olarak bu bilim adamlarının isimleriyle anılıyorlar.

Kodlama teorisinin gelişimini hızlandıran bir katalizör haline gelen Hamming'in makalesi bilim camiasının ilgisini çekti. Tüm ders kitaplarında bu kod sınıfına Hamming kodları adı verilir ve kodlama teorisinin sunumu, bunların yapısının açıklanmasıyla başlar. Görünüşe göre, Golay'ın Hamming'le bağımsız olarak aynı fikirlere ulaştığı ve bunları daha önce yayınladığı göz önüne alındığında, bu kodlara Hamming-Golay kodları demek daha doğru olacaktır. Yazısının hak ettiği ilgiyi görmemesi büyük ihtimalle tesadüftür.

Shannon'ın teorisiyle karşılaştırıldığında Hamming'in ortaya koyduğu kodlar hayal kırıklığı yaratacak kadar zayıftı. Ancak Hamming'in hata düzeltme kodları oluşturmaya yönelik düzenli yöntemleri temel öneme sahipti. Mühendislere, bilgi teorisi yasalarının belirttiği sınırlara ulaşmanın pratik olasılığını gösterdiler. Bu kodlar bilgisayar sistemlerinin oluşturulmasında pratik uygulama alanı bulmuştur. Hamming'in makalesi aynı zamanda sonlu alanlar için daha yoğun paketlenme sorununa da bir çözüm getirdi. Kodlama teorisinin en önemli kavramlarını bilimsel kullanıma sundu - bir vektör uzayındaki kod kombinasyonları arasındaki Hamming mesafesi, ikili kodlar için bu kombinasyonların farklı sembollerle konumlarının sayısı olarak tanımlanır ve bloğun düzeltme yeteneği için Hamming sınırları kodları düzeltiyorum. İkili kodlar için Hamming sınırı aşağıdaki formül kullanılarak hesaplanır:

Bu ifadede, e hata sayısı, M kod kombinasyonlarına sahip (CjN binom katsayısıdır) N uzunluğundaki bir düzeltme blok koduyla düzeltilebilir.

Hamming'in çalışması, kodlama teorisinin daha sonraki gelişiminde önemli bir rol oynadı ve sonraki yıllarda yürütülen kapsamlı araştırmaları teşvik etti. 1956'da David Slepyan, eşlik kontrol kodlarının teorisini ciddi bir matematiksel temelde sunan ilk kişi oldu. Fransız bilim adamı A. Hoquenghem (1959) ve Amerikalı R. K. Bose ve D. K. Roy-Chowdhury (1960), kat hatalarını düzelten geniş bir kod sınıfı (BCH kodları) bulduklarında, kodlama teorisi alanında büyük bir değişiklik meydana geldi. Amerikalı araştırmacılar I. S. Reed ve G. Solomon (1960), BCH kodlarıyla ilgili ikili olmayan kanallar için bir kod sınıfı buldular.

1980'de Hamming, 1983'te Rusça'ya çevrilen "Kodlama Teorisi ve Bilgi Teorisi" adlı harika bir ders kitabı yazdı. Bu kitap, diğer çalışmaları gibi, soruların formülasyonunun özgünlüğü, sunumun popülerliği, pratik problemlerin derinlemesine anlaşılması, ortaya çıkan konuların matematiksel yorumunun doğruluğu ve makul derecede titizliği ile öne çıkıyor. Materyalin sunumu, okuyucunun şu veya bu teoremin neden doğru olduğunu sezgisel olarak anlayacağı şekilde yapılandırılmıştır.

) kod dizilerinin bir vektör uzayında, bu durumda iki ikili dizi (vektörler) arasındaki Hamming mesafesi ve uzunluk, bunların farklı olduğu konumların sayısıdır - bu formülasyonda Hamming mesafesi, Algoritmalar Sözlüğü'ne dahil edilmiştir ve Amerika Birleşik Devletleri Ulusal Standartlar Enstitüsü'nün Veri Yapıları (eng. NIST Algoritmalar ve Veri Yapıları Sözlüğü ).

Dolayısıyla, 0 011 1 ve 1 010 1 vektörleri arasındaki Hamming mesafesi 2'dir (farklı bitler kırmızıyla işaretlenmiştir). Daha sonra metrik, q-ary dizilerine genelleştirildi: bir çift "seçim" ve "çit" dizisi için Hamming mesafesi üçe eşittir.

Genel olarak nesneler ve boyutlar için Hamming mesafesi aşağıdaki fonksiyonla verilir:

Hamming mesafesi, aşağıdaki koşulları karşılayan bir metriğin özelliklerine sahiptir:

Biyoinformatik ve genomikte Hamming mesafesi

Edebiyat

Richard W. Hamming. Hata tespiti ve hata düzeltme kodları, Bell System Teknik Dergisi 29(2):147-160, 1950.
Richard Bleichut. Hata kontrol kodlarının teorisi ve uygulaması. M., "Mir", 1986

Bağlantılar

Richard Hamming ve kodlama teorisinin başlangıcı // Sanal Bilgisayar Müzesi

Wikimedia Vakfı. 2010.

Diğer sözlüklerde “Hamming mesafesinin” ne olduğunu görün:

Hamming mesafesi- Hamming mesafesi Aynı uzunluktaki iki kod dizisi u ve v arasındaki mesafe d(u,v), farklı oldukları sembollerin sayısına eşittir. Minimum Hamming mesafesi d olan bir blok kodu, kişinin (d 1) ve... ...'i tespit etmesine olanak tanır.

kod mesafesi- Tek tip bir kodda farklı kod sözcüklerinin tüm larvaları üzerinden alınan minimum Hamming mesafesi. [Önerilen terimlerin toplanması. Sayı 94. Bilgi aktarımı teorisi. SSCB Bilimler Akademisi. Teknik Terminoloji Komitesi. 1979] Konu teorisi... ... Teknik Çevirmen Kılavuzu

Matematik ve bilgi teorisi alanlarında doğrusal kod, hata tespit ve düzeltme şemalarında kullanılan önemli bir blok kod türüdür. Doğrusal kodlar diğer kodlara göre daha verimli algoritmaların uygulanmasına olanak sağlar... ... Vikipedi

İletişim teknolojisindeki hataların tespiti, bilginin kaydedilmesi/çoğaltılması veya iletişim hatları üzerinden iletilmesi sırasında veri bütünlüğünün izlenmesini amaçlayan bir eylemdir. Hata düzeltme (hata düzeltme) kurtarma prosedürü... ... Wikipedia

İletişim teknolojisindeki hataların tespiti, bilginin kaydedilmesi/çoğaltılması veya iletişim hatları üzerinden iletilmesi sırasında veri bütünlüğünün izlenmesini amaçlayan bir eylemdir. Sonra bilgileri geri yüklemek için hata düzeltme (hata düzeltme) prosedürü... ... Wikipedia