Kaplama kodu - Covering code - Wikipedia

İçinde kodlama teorisi, bir kaplama kodu bir dizi unsurdur (adı kod sözcükleri) bir uzayda, uzayın her öğesinin bazı kod sözcüklerinin sabit bir mesafesi içinde olması özelliği ile.

Tanım

İzin Vermek , , olmak tamsayılar.A kodu bir alfabe Q boyut |Q| = q denirq-ary R-uzunluk kodunu kapsayan neğer her kelime için var kod sözcüğü öyle ki Hamming mesafesi Başka bir deyişle, küreler (veya toplar veya kale alanları) yarıçap RHamming ile ilgili olarak metrik kod sözcükleri etrafında C tüketmek zorunda sonlu metrik uzay .The kaplama yarıçapı bir kodun C en küçüğü R öyle ki C dır-dir R-covering.Every mükemmel kod minimum boyutta bir kaplama kodudur.

Misal

C = {0134,0223,1402,1431,1444,2123,2234,3002,3310,4010,4341} 4 uzunluğunda 5 ary 2 kapsayan bir koddur.[1]

Kaplama sorunu

kararlılık minimum boyutta bir q-ary R-uzunluk kodunu kapsayan n çok zor bir problem. Çoğu durumda, yalnızca üst ve alt sınırlar aralarında büyük bir boşluk olduğu bilinmektedir.Bir örtme kodunun her yapısı bir üst sınır verir Kq(nRAlt sınırlar, küre kaplama sınırını ve Rodemich sınırlarını içerir. ve .[2]Örtme sorunu, bölgedeki paketleme sorunu ile yakından ilgilidir. , yani bir maksimum boyutun belirlenmesi q-ary e-hata düzeltme uzunluk kodu n.

Futbol havuzları sorunu

Belirli bir durum, futbol havuzları sorunu, dayalı futbol havuzu bahis, amacın sonuçları tahmin etmek olduğu n ev sahibi olarak futbol maçları kazanır, berabere veya deplasmanda kazanır veya en azından tahmin etmek için n - 1 Birden fazla bahis içeren bunlardan. Böylece üçlü bir örtü, K3(n, 1), aranır.

Eğer sonra 3n-k ihtiyaç duyulduğu için n = 4, k = 2, 9 gereklidir; için n = 13, k = 3, 59049 gerekli.[3] 2011 itibariyle bilinen en iyi sınırlar[4] vardır

n1234567891011121314
K3(n,1)13592771-73156-186402-4861060-12692854-36457832-947721531-2770259049166610-177147
K3(n,2)133815-1726-3454-81130-219323-5557291919-21875062-656112204-19683
K3(n,3)133611-1214-2727-5457-105117-243282-657612-12151553-2187

Başvurular

Standart iş[5] Kaplama kodlarında aşağıdaki uygulamaları listeler.

Referanslar

  1. ^ P.R.J. Östergård, Üst sınırlar q-ary örtme kodları, Bilgi Teorisi Üzerine IEEE İşlemleri, 37 (1991), 660-664
  2. ^ E.R. Rodemich, Kale alanlarına göre koruma, Kombinatoryal Teori Dergisi, 9 (1970), 117-128
  3. ^ http://alexandria.tue.nl/repository/freearticles/593454.pdf
  4. ^ http://www.sztaki.hu/~keri/codes/3_tables.pdf
  5. ^ G. Cohen, I. Honkala, S. Litsyn, A. Lobstein, Kapsam Kodları, Elsevier (1997) ISBN  0-444-82511-8
  6. ^ H. Hämäläinen, I. Honkala, S. Litsyn, P.R.J. Östergård, Futbol havuzları - matematikçiler için bir oyun, American Mathematical Monthly, 102 (1995), 579-588

Dış bağlantılar