Kuresel paketleme sinirinin ispati

Question

$q$ bir asal kuvveti ve $\mathbb F_q$ bu asal kuvvete denk gelen sonlu cisim olsun. $C$ kumesi $\mathbb F_q^n$ icerisinde bir kod uzayi olsun. Bu uzay icerisindeki fakli elemanlar arasindaki Hamming mesafesinin en kucugune $d$ diyelim.


Gosteriniz: $|C|\leq \frac{q^n}{\sum\limits_{i=0}^\delta\big(\begin{matrix} n \\ i \end{matrix}\big)(q-1)^i}$ oyle ki $\delta=\lfloor (d-1)/2\rfloor$.

Bugun kodlama teorisi dersinde ogrencilerin cozmesi gereken sorulardan biri, burda da paylasayim dedim.

Comments

Kuresel paketleme dediginiz "Sphere Packing" mi Sercan Hocam? Lattice teorisi kullanilan?

---

Link ya da referans var mi? Cok uygulanabilir oldugundan, kullanilir bence. Lattice/izgaradan secilen noktalari kod olarak dusunursek, buradaki kod uzayini da izgara olarak... olmali.

ingilizcesi dedigin gibi.

---

Matematik Koyu'nde Ozgur Kisisel anlatmisti. 4 boyutta 3 boyutlu cisimleri en yogun paketlemenin lattice paketleme oldugunu soyleyen bir teorem vardi. Sanirim hala kanitlanamamis ya da son zamanlarda kanitlanmisti. Sonra n boyuta genellemek vs.

Sphere packing problem diye aratinca cikmasi lazim

Answer 1

$x=x_1x_2\cdots x_n$ olarak yazalim.

Buna uzakligi $1$ olamasi icin  girdilerin secim sayisi, yani bir girdisini degistirecegimiz girdilerin secim sayisi $C(n,1)$ olur. 
Buna uzakligi $2$ olmasi icin  girdilerin secim sayisi, yani bir girdisini degistirecegimiz girdilerin secim sayisi $C(n,2)$ olur.
$\vdots$
Buna uzakligi $i$ olmasi icin girdilerin secim sayisi, yani bir girdisini degistirecegimiz girdilerin secim sayisi $C(n,i)$ olur. 

Her girdi icin kendisinden farkli $q-1$ eleman oldugundan

Buna uzakligi $1$ olan  eleman sayisi, yani bir girdisini degistirecegimiz eleman sayisi $C(n,1)(q-1)$ olur. 
Buna uzakligi $2$ olan eleman sayisi, yani bir girdisini degistirecegimiz eleman sayisi $C(n,2)(q-1)^2$ olur. 
$\vdots$
Buna uzakligi $i$ olan eleman sayisi, yani bir girdisini degistirecegimiz eleman sayisi $C(n,i)(q-1)^i$ olur. 

Eger  minimum mesafe $d$ ise $\delta$ uzakligina kadar kendisi disinda hicbir eleman kod uzayinda olamaz. Yani her $\sum\limits_{i=0}^\delta C(n,i)(q-1)^i$ icin sadece bir eleman bu kod uzayinda olabilir.  Tum uzayimizda da $q^n$ eleman oldugundan bu siniri elde ederiz.