Kod teorisi

Gelen bilgi teorisi , kodlama teorisi kodları ve bunların özellikleri ve çeşitli görev yetenekleri ile ilgilenen iletişim kanallarının . İki iletişim modeli vardır: gürültülü ve gürültüsüz . Gürültü olmadan, iletişim için kaynak kodlaması yeterlidir. Gürültü ile, düzeltici kodlarla iletişim mümkündür .

Tarih

Bilgiyi bu kadar matematiksel olarak tanımlayarak, kodlama teorisinin kuruluş aşaması Claude Shannon tarafından alındı . Başka tanımlar da var, ancak Shannon'ın entropisi en başarılı olanıydı. Böylece, bilgi teorisinin iki temel sorusuna cevap  verilebilir: Bilginin aktarımı için gerekli kaynaklar nelerdir ve ne kadar bilginin güvenilir bir şekilde aktarılabileceği.

Kod teorisi , bu son kanal kodlama sorusuyla ilgilenir. Shannon, enformasyon teorisinin iki temel sorusunu yanıtlarken, çok güçlü bir düzeltici kodlar dizisi sağlayamadı . Özellikle, kanal kodlama teoreminin sağladığı limite ulaşan bir kod örneği belirlememiştir.

Kod teorisinin doldurduğu bu boşluktur. Günümüzde iyi düzeltici kodlar üretmeyi amaçlayan çok sayıda yöntem vardır.

Kod özellikleri

Kodlar ilk olarak bir sembol tarafından iletilen bilgi miktarı ile ayırt edilir . Simetrik ikili kanal en yaygın olan, sık sık bir ele alacağız ikili kod . Bununla birlikte, üçlü kodlar ve genel olarak q-ary kodları da vardır.

Aşağıdaki değişken adları çoğunlukla kural tarafından kullanılır. M boyutunda olan kod sözcüklerini içeren bir koddur . Bir kod sözcüğünün uzunluğu ile belirtilir . Böyle bir koda kod denir .

Hata tespiti ve düzeltmesi

Çoğu kod, hata tespiti veya hata düzeltme için kullanılır.

Minimum mesafe ve kod çözme

Bir kodun minimum mesafesi, kod çözme hatası olasılığını etkiler. Minimum mesafe, belirtilen önemli bir parametredir . Böyle bir koda kod denir .

Kod aileleri

Eşdeğer kodlar

Tüm hata düzeltme özellikleri aynıysa iki kod eşdeğerdir.

Kod türleri

Genellikle üç tür kod vardır.

  • Bir lineer kod a, düzeltme kodu , bir hangi vektör alan yapısı uygulanır .
  • Bir çevrimsel kod için bir vektör alanı daha fazla bir yapıya sahip bir düzeltme kodu. Genel olarak, kod kelimelerini polinomlar olarak düşünebiliriz . Örnek: Reed-Solomon kodu .
  • Bir doğrusal olmayan kod için bir vektör alan yapı elde olmadan çeşitli şekillerde imal edilebilir bir düzeltme kodu.

Az sayıda özel durum var. Bir önemsiz kod dolayısıyla onun bir kod anlamıyla kopya ilk mesaj olduğunu abeslik . Bir sistematik kod kodlanacak mesajı kodlanmış mesajın içerdiği edildiği bir koddur.

Ayrıca, bazı düzeltici kodlar kuantum kodları olarak kullanılabilir .

Diğer önemli kod türleri şunlardır:

  • cebirsel kod
  • rastgele kod
Aileler

Düzeltme kodları da ailelere göre sınıflandırılabilir.

  • Bir eşlik kodu , mesaja bir veya daha fazla eşlik biti ekler .
  • Bir yineleme kodu her bit birden fazla kopyası aktarılacak gönderir.
  • Hamming kodları en iyi bilinen aileyiz. İkili Hamming kodları döngüsel kodlara eşdeğerdir ve bazı ikili olmayan kodlar da vardır.
  • Bir Golay kodu bir olan lineer kod teoride ve pratikte önem.
  • Bir Reed-Müller kodu, kod çözme özelliklerinin özellikle pratik olduğu düşünülen doğrusal bir koddur.
  • BCH kodları bir genelleme vardır Hamming kodları . Bunlar aynı zamanda döngüsel kodlardır. Reed-Solomon kodu özel bir durumdur .
  • Bir kuadratik kalıntı kod göre bir siklik kodu ikinci dereceden tortu .
  • Bir Goppa kodu siklik kodları gibi, bir Goppa polinom olarak adlandırılan bir polinom dayanmaktadır.
  • Bir stabilize edici kod bir ölçümüne dayanan sendromu bir biçiminde bulunacağı şekilde gerçekleştirilir, vektör içinde .
  • Bir genişletici kodu  (in) hataların sabit bir kısmını gidermek için hala mümkün olduğu olan bir doğrusal koddur.
  • Süper konsantre kod Spielman , doğrusal zamanda kodlanabilen ve kodu çözülebilen tek koddur .
  • Bir alternatif kodu pratik öneme sahip bir lineer kodudur.
  • Bir Hadamard kod , bir elde edilen bir kod olan Hadamard matris .
  • Bir LDPC kodu , seyrek bir eşlik matrisine sahip bir koddur.
Kod kombinasyonları

Bir veya iki temel kodu birleştiren işlemlerden yeni kodlar elde edilebilir.

  • önemsiz işlemler: delme veya kısaltma
  • bitiştirme: kod Forney , kod Justesen  (en)
  • ürün
Diğer özellikler

Ayrıca belirli kod sınıflarını özelliklerine göre ayırırız.

  • kesişen kod
  • ayırma kodu
  • (2014) dissimile ve çapa = 111110110

Kod ve "tasarım"

Kodlar ve kombinatoryal tasarımlar arasında bir bağlantı vardır .

Kod teorisinin temel problemi

Izin vermek için bir kod ve -naire olan en büyüğü olsun. Kod teorisinin temel sorunu bu değerleri belirlemektir.

Kaynak kodlama

Kaynak kodlamanın amacı , dilin tekrarlayan bilgilerini, fazlalığını sıkıştırmak olabilir . Herhangi bir dil için, bir mesajın entropisini , yani aktarılan bilginin miktarını düşünebiliriz . Bu , kaynak kodlama teoremine yol açar .

Kanal kodlama

Amaç, iletişim kanalındaki gürültüyü telafi etmek için bir mesaja fazlalık bilgi eklemektir . Bu , kanal kodlama teoremine yol açar ve kod teorisinin kökenini buna borçluyuz .

Bazı kriptografik problemler , kod çözme zorluğu varsayımına dayanmaktadır .

Cebirsel kod teorisi

Cebirsel kod teorisi, kodların özelliklerinin cebirsel olarak ifade edildiği kod teorisinin bir alt alanıdır. Başka bir deyişle, yaklaşım olasılıkçı olan geleneksel yaklaşımın aksine cebirseldir . Esas olarak çalışıyoruz:

  • "iyi" kodların oluşturulması, yani bazı istenen parametrelerle, örneğin:
    • kod kelimelerinin uzunluğu
    • geçerli kod kelimelerinin toplam sayısı
    • Asgari Hamming iki geçerli kod kelimeler arasındaki mesafe
  • bu kodların verimli bir şekilde çözülmesi

Metin analizinde kullanır

Kod analizi, kullanılan kod zayıfsa (örneğin, César veya Vigenère kodu ) şifreleme metninin kodunu çözmeye çalışmak için kullanışlıdır . Bir metnin istatistiksel özelliklerinin tespiti, dili anlamadan bile, bir metnin birden fazla yazarı olup olmadığını kontrol etmeyi mümkün kılar (böylece Papyrus Voynich'in iki farklı yazarı olduğunu doğrulayabiliriz ; ilgili makaleye bakın). Aynı zamanda, Victor Hugo'nun metinlerini analiz etmeyi ve bu istatistiksel özellikler aracılığıyla yazılarının on yılını tespit etmeyi mümkün kılar . IBM Bilim Merkezi ayrıca Charles de Gaulle'ün konuşmalarını inceledi ve bu konuşmaların birkaç "kritik" konuşma dışında (örneğin30 Mayıs 1968). Stanford Üniversitesi ayrıca ilgili kelime dağarcığını tarafından Marcel Proust ve Paul Valéry . Mühendis Jean-Jacques Walter da Kuran'ın metni üzerine bu analizi gerçekleştirdi ve ona göre birkaç düzine yazara (en az 30 farklı yazar, muhtemelen 50, en fazla 100) atıfta bulunan bir devlet tezini savundu. diller, iki yüz yıldan fazla bir süre.

Kurgusal literatürde, bu teori, Le Monde Robert Escarpit'in gazetecisi için Le Littératron adlı kitabında bir uzmanın kafelerdeki konuşmalarda dile getirilen konuşmalardan yola çıkarak , her şeyden önce şakaları uyandıran nihai popülist söylemi oluşturmak için bir bilgisayar kullandığı bir pivot görevi görür. ama yavaş yavaş müthiş bir etki gösterir.

Referanslar

  1. Önsöz (in) Elwyn R. Berlekamp , Cebirsel Kodlama Teorisi , McGraw-Hill , 1968, 466 s.
  2. "Le Grand Witness" programında Jean-Jacques Walter ile 8/10/2013 röportajı
  3. Kuran'ın istatistiksel analizi .

Ayrıca görün

İlgili Makaleler

Kaynakça

İşlerNesne
  • Adam Woryna , "  Üç öğeli kodlar kümesindeki ön ek kodlarının oranı hakkında  ", Ayrık Matematik , cilt.  343, n o  8,2020, Madde n o  111939 ( DOI  10.1016 / j.disc.2020.111939 ).

Dış bağlantılar

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">