Kod Parametreleri için Sınırlar
Bu bölümde, bir kodun uzunluğu, boyutu (veya büyüklüğü) ve minimum uzaklığı parametrelerinden ikisi verildiğinde, doğrusal veya doğrusal olmayan bir kod için diğer parametreye ilişkin verilebilecek çeşitli sınırlardan bahsedeceğiz. Öncelikle, doğrusal bir kodun boyutuna üst sınır veren Küre Paketleme (veya Hamming) Sınırını ele alacağız. Bu bölümde bazı üst sınırların yanı sıra iki tane de alt sınırdan bahsedilecektir. Alt sınırların genellikle belirli kod inşalarıyla ilişkili olması nedeniyle bu sınırların sayısı üst sınırların sayısından daha azdır. Bu bölümde, ayrıca, verilen bir sınırı karşılayan kodlardan söz edeceğiz.
Küre Paketleme Sınırı, Örtme Yarıçapı ve Mükemmel Kodlar
Minimum uzaklık $d$, bir kodun işlevselliğinin temel bir ölçüsüdür. Kodlama kuramındaki en temel problem, verilen bir uzunluk ve kod sözcüğü sayısı için mümkün olan en büyük $d$ değerine sahip bir kod üretmektir. Alternatif olarak, $n$ ve $d$ verildiğinde, $\ff_{q}$ üzerinde uzunluğu $n$ ve minimum uzaklığı en az $d$ olan bir koddaki maksimum kod sözcüğü sayısı olan $A_{q}(n,d)$'yi belirlemektir. $A_{2}(n,d)$ sayısı $A(n,d)$ ile de gösterilir. Bu soruyu doğrusal olmak zorunda olmayan tüm kodlar için soruyoruz. Fakat aynı soruyu sadece doğrusal kodlar için sorduğumuz zaman $\ff_{q}$ üzerinde uzunluğu $n$ ve minimum ağırlığı en az $d$ olan bir doğrusal koddaki maksimum kod sözcüğü sayısı $B_{q}(n,d)$ (ikili durumda $B(n,d)$) sayısını bulmakla ilgileniyoruz demektir. $B_{q}(n,d)\leq A_{q}(n,d)$ olduğu ortadadır. $n$ ve $d$'nin küçük değerleri için $A(n,d)$ ve $B(n,d)$ değerlerinin olduğu tablolar verilmiştir.
Farklı kod sözcükleri etrafındaki $t$ yarıçaplı kürelerin ikişer ikişer ayrık olması, yaygın olarak Küre Paketleme Sınırı veya Hamming Sınırı olarak bilinen aşağıdaki temel eşitsizliği doğrudan verir.
Teorem 6.1: Küre Paketleme Sınırı
Kanıt
Küre Paketleme Sınırının ispatından görüyoruz ki sınırda eşitlik sağlandığında, $\ff_{q}^{n}$ uzayını $t$ yarıçaplı ayrık kürelerle gerçekten doldurmuş oluruz. Başka bir deyişle, $\ff_{q}^{n}$'deki her vektör, tam olarak bir kod sözcüğü merkezli $t$ yarıçaplı kürenin içinde yer alır. Bir kod için bu durum sağlandığında, bu koda mükemmel kod denir.
Örnek 6.17
Dolayısıyla $\mathcal{H}_{q,r}$ mükemmel bir koddur.
Hamming kodlarının yanı sıra, kodlama kuramının en önemli mükemmel kodları Golay kodlarıdır. Marcel Golay tarafından 1949'da keşfedilen bu kodlar, ikili ve üçlü olmak üzere iki türe ayrılır.
Golay Kodları
Tanım 6.1: Genişletilmiş İkili Golay Kodu
Genişletilmiş ikili Golay kodu $\mathcal{G}_{24}$, standart biçimde üreteç matrisi $G_{24}=[I_{12}\mid A]$ ile tanımlanan $[24,12]$ kodudur. Burada $A$ aşağıdaki $12\times 12$ matristir:
$$A=\begin{pmatrix}0&1&1&1&1&1&1&1&1&1&1&1\\1&1&1&0&1&1&1&0&0&0&1&0\\1&1&0&1&1&1&0&0&0&1&0&1\\1&0&1&1&1&0&0&0&1&0&1&1\\1&1&1&1&0&0&0&1&0&1&1&0\\1&1&1&0&0&0&1&0&1&1&0&1\\1&1&0&0&0&1&0&1&1&0&1&1\\1&0&0&0&1&0&1&1&0&1&1&1\\1&0&0&1&0&1&1&0&1&1&1&0\\1&0&1&0&1&1&0&1&1&1&0&0\\1&1&0&1&1&0&1&1&1&0&0&0\\1&0&1&1&0&1&1&1&0&0&0&1\end{pmatrix}.$$ $A$ matrisini elde etmek için şu pratik yöntemi kullanabiliriz. $A$'nın sütunlarını $\infty, 0, 1, 2, \ldots, 10$ olarak etiketleyelim. İlk satırda $\infty$ sütununa $0$, diğer sütunlarda $1$ yazalım. İkinci satırda $\infty$ ile $0, 1, 3, 4, 5, 9$ sütunlarına $1$ ve geri kalan sütunlara $0$ yazalım. Dikkat edilirse bu sütun numaraları tam sayıların $11$ modülündeki kareleridir: $0^{2}\equiv 0$, $1^{2}\equiv 1$, $2^{2}\equiv 4$, $3^{2}\equiv 9$, $4^{2}\equiv 5$, $5^{2}\equiv 3 \pmod{11}$. Sonraki satırlar, ikinci satırın $\infty$ sütunu dışındaki girişlerinin bir pozisyon sola döngüsel kaydırılmasıyla elde edilir.Teorem 6.2
Kanıt
• $\mcc$ kendisine dik bir kod ve $\mcc$'nin bir üreteç matrisinin satırlarının ağırlıkları 4 ile bölünebilirse, $\mcc$'nin her kod sözcüğünün ağırlığı 4 ile bölünebilir.
• Eğer $\mcc$'nin her kod sözcüğünün ağırlığı 4 ile bölünebilirse, o zaman $\mcc$ kendisine diktir.
📖 Detaya Git'den, $\mathcal{G}_{24}$'ün tüm kod sözcüklerinin ağırlıkları $4$'e bölünebilir.
Önceki bölümden, $\mathcal{G}_{24}$'ün bir $[24,12,d]$ öz-dual kod ve $d=4$ veya $d=8$ olduğu elde edilir. $d=4$ olduğunu varsayalım. $G_{24}$ bir öz dual kod ve $A^{T}=A$ olduğundan $[A^{T}\mid I_{12}]=[A\mid I_{12}]$ matrisi de $G_{24}$'ün bir üreteç matrisidir.
$\mathbf{a},\mathbf{b}\in\ff_{2}^{12}$ olmak üzere $\mathbf{c}=(\mathbf{a},\mathbf{b})$, $\mathcal{G}_{24}$'ün ağırlığı $4$ olan bir kod sözcüğü olsun. $\mathcal{G}_{24}$ öz-dual olduğundan, $(\mathbf{b},\mathbf{a})$ da bir kod sözcüğüdür. Dolayısıyla, genelliği bozmadan $\operatorname{wt}(\mathbf{a})\leq\operatorname{wt}(\mathbf{b})$ seçebiliriz. $\operatorname{wt}(\mathbf{a})=0$ ise $\mathbf{a}=\mathbf{0}$ olur ve $G_{24}$ standart biçimde olduğundan $\mathbf{b}=\mathbf{0}$, yani çelişki elde ederiz. $\operatorname{wt}(\mathbf{a})=1$ ise $\mathbf{c}$, $G_{24}$'ün satırlarından biridir ki bu da çelişkidir. $\operatorname{wt}(\mathbf{a})=2$ ise $\mathbf{c}$, $G_{24}$'ün iki satırının toplamıdır. Ancak $G_{24}$'ün herhangi iki satırının toplamının ağırlığının $4$'ten büyük olduğu doğrudan inceleme ile görülebilir. Dolayısıyla $d=8$'dir.Tanım 6.2: İkili Golay Kodu
📝 Ödev 6.1 (MTK698-2026) | ⏰ Son Teslim: 31.03.2026 00:00
Aşağıdakileri gösteriniz:
Yukarıdaki tanımda bahsedilen $\mathcal{G}_{24}$'ün herhangi bir koordinatından delinmiş kodların tümü birbirine denktir ve herhangi birine eşlik denetim koordinatı eklendiğinde $\mathcal{G}_{24}$ yeniden elde edilir.
- $\mathcal{G}_{23}$, $t=\lfloor(7-1)/2\rfloor=3$ hata düzeltme kapasitesine sahip mükemmel bir koddur.
Tanım 6.3: Genişletilmiş Üçlü Golay Kodu
Genişletilmiş üçlü Golay kodu $\mathcal{G}_{12}$, $\ff_{3}$ üzerinde bir üreteç matrisi standart biçimdeki $G_{12}=[I_{6}\mid B]$ matrisi olan $[12,6]$ kodudur. Burada $B$, $\ff_{3}$ üzerinde aşağıdaki $6\times 6$ matristir:
$$B=\begin{pmatrix}0&1&1&1&1&1\\1&0&1&2&2&1\\1&1&0&1&2&2\\1&2&1&0&1&2\\1&2&2&1&0&1\\1&1&2&2&1&0\end{pmatrix}.$$Tanım 6.4: Üçlü Golay Kodu
İkili ve üçlü Golay kodları, aşikâr mükemmel kodlar ve Hamming kodları dışında bilinen tek mükemmel kodlardır. Bu benzersizlik, onları kodlama kuramında özel bir konuma yerleştirmektedir.
📝 Ödev 6.2 (MTK698-2026) | ⏰ Son Teslim: 31.03.2026 00:00
Gösteriniz ki $\mathcal{G}_{12}$ bir $[12,6,6]$ öz-dual koddur.
- $[11,6,5]$ üçlü Golay kodlarının mükemmel olduğunu gösteriniz.
📝 Ödev 6.3 (MTK698-2026) | ⏰ Son Teslim: 05.04.2026 23:59
Aşağıdaki kodların mükemmel olduğunu gösteriniz:
- $\mcc=\ff_{q}^{n}$,
yalnızca bir kod sözcüğünden oluşan kodlar (doğrusal kodlar durumunda sıfır vektörü),
tek uzunluklu ikili tekrarlama kodları,
tek uzunluklu, bir $\mathbf{c}$ vektörü ile $0$'lar ve $1$'lerin yer değiştirilmiş hâli olan tümleyen vektörü $\bar{\mathbf{c}}$'den oluşan ikili kodlar.
tek uzunluklu, bir $\mathbf{c}$ vektörü ile $0$'lar ve $1$'lerin yer değiştirilmiş hâli olan tümleyen vektörü $\bar{\mathbf{c}}$'den oluşan ikili kodlar.
Bu kodlara aşikâr mükemmel kodlar denir.
📝 Ödev 6.4 (MTK698-2026) | ⏰ Son Teslim: 05.04.2026 23:59
Uzunluğu $n$ olan mükemmel $t$-hata düzelten bir doğrusal kodun, her $0\leq i\leq t$ için, ağırlığıBir kosetteki ağırlığı en küçük olan elemanların her birine o kosetin öncüsü denir. Bir koset öncüsünün ağırlığına ise o kosetin ağırlığı denir.
📖 Detaya Git $i$ olan tam $\binom{n}{i}$ koseti olduğunu ve bunlardan başka hiç koseti olmadığını kanıtlayınız. İpucu: $\ff_{q}^{n}$'de kaç tane ağırlığı $i$ olan vektör vardır? Ağırlıkları $i$ ve $j$ olan farklı vektörler, $i\leq t$ ve $j\leq t$ iken aynı kosette olabilir mi? Küre Paketleme Sınırındaki eşitliği kullanınız.
Hamming kodları mükemmeldir ve Golay kodları da önceki alıştırmalarda gösterildiği gibi mükemmeldir. Ayrıca, bir Hamming kodu ile aynı uzunluk, boyut ve minimum ağırlığa sahip tüm doğrusal kodların o Hamming koduna denk olduğu da kolayca gösterilebilir. Dolayısıyla bu kodların herhangi birini Hamming kodu olarak adlandırdık. Önceki alıştırmada tanımlanan bazı aşikâr mükemmel kodlar da bulunmaktadır. Böylece şimdiye kadar yapılanlarla aşağıdaki teoremin ispatının (küçük) bir kısmını elde etmiş oluruz.
Teorem 6.3: Mükemmel Kodların Sınıflandırması
- $\ff_{q}$ üzerinde doğrusal olmayan mükemmel tek-hata düzelten kodlar vardır ve bu tür tüm kodlar Hamming kodlarının parametrelerine sahiptir; yani uzunlukları $n=(q^{r}-1)/(q-1)$, kod sözcüğü sayıları $q^{n-r}$ ve minimum uzaklıkları $3$'tür. $\ff_{q}$ üzerindeki tek mükemmel tek-hata düzelten doğrusal kodlar Hamming kodlarıdır.
Aşikâr olmayan tek mükemmel çoklu-hata düzelten kodlar, $[23,12,7]$ ikili Golay kodu veya $[11,6,5]$ üçlü Golay koduyla aynı uzunluk, kod sözcüğü sayısı ve minimum uzaklığa sahiptir.
- $\mathbf{0}$ vektörünü içeren, $2^{12}$ (veya $3^{6}$) adet vektöre sahip, uzunluğu $23$ (veya $11$) ve minimum uzaklığı $7$ (veya $5$) olan herhangi bir ikili (veya üçlü), doğrusal olması gerekmeyen kod, $[23,12,7]$ ikili (veya $[11,6,5]$ üçlü) Golay koduna denktir.
Bu teoremde özetlenen mükemmel kodların sınıflandırılması, birçok araştırmacının katkıda bulunduğu önemli ve zor matematiksel çalışmaların bir ürünüdür. Ancak (ii) kısmının bir bölümü aşağıdaki alıştırmada kanıtlanabilir. (iii) kısmının kanıtı ise oldukça karmaşıktır ve bu dersin kapsamı dışındadır.
📝 Ödev 6.5 (MTK698-2026) | ⏰ Son Teslim: 05.04.2026 23:59
Bu alıştırmanın amacı, yukarıdaki teoremin (ii) kısmının bir bölümünü kanıtlamaktır. $\mcc$, $[n,k,7]$ parametrelerine sahip mükemmel bir ikili kod olsun.
Küre Paketleme Sınırındaki eşitliği kullanarak
$$(n+1)[(n+1)^{2}-3(n+1)+8]=3\cdot 2^{n-k+1}$$olduğunu kanıtlayınız.
- $n+1$'in $2^{b}$ veya $3\cdot 2^{b}$ biçiminde olduğunu kanıtlayınız; burada $b\leq n-k+1$'dir.
- $b<4$ olduğunu kanıtlayınız.
- $n=23$ veya $n=7$ olduğunu kanıtlayınız.
Biri $n=7$, diğeri $n=23$ olan iki tane mükemmel $[n,k,7]$ kodunun adını veriniz.
Doğrusal olmayan mükemmel kodlar, doğrusal bir mükemmel kodun bir koseti alınarak elde edilebilir. Yukarıdaki teorem, çoklu hata düzelten tüm doğrusal olmayan kodların, uzunluğu $23$ olan ikili Golay kodunun veya uzunluğu $11$ olan üçlü Golay kodunun kosetleri olduğunu göstermektedir. Öte yandan, Hamming kodlarının kosetleri olmayan doğrusal olmayan tek-hata düzelten kodlar da mevcuttur.
📝 Ödev 6.6 (MTK698-2026) | ⏰ Son Teslim: 05.04.2026 23:59
Doğrusal bir mükemmel kodun bir kosetinin de mükemmel bir kod olduğunu kanıtlayınız.
Tanımdan $t\leq\rho(\mcc)$'dir. Ayrıca $t=\rho(\mcc)$ ancak ve ancak $\mcc$ bir mükemmel koddur. Aslında bir kodun paketleme yarıçapı (yani $t$), kod sözcüğü merkezli kürelerin ayrık kalacağı şekilde seçilebilecek en büyük küre yarıçapıdır. Dolayısıyla bir kod, ancak örtme yarıçapı ile paketleme yarıçapı eşit olduğunda mükemmeldir. Kod mükemmel değilse örtme yarıçapı paketleme yarıçapından büyüktür.
Doğrusal olmayan bir $\mcc$ kodu için de örtme yarıçapı $\rho(\mcc)$ aynı şekilde tanımlanır ve yukarıdaki paragrafta söylenenler bu durum için de geçerlidir. Bu bölümde kanıtlayacağımız sonuçlar yalnızca doğrusal kodlar içindir.
Eğer $\mcc$, paketleme yarıçapı $t$ ve örtme yarıçapı $t+1$ olan bir kod ise $\mcc$'ye bir mükemmelimsi (en:quasi-perfect) kod denir. Bilinen çok sayıda doğrusal ve doğrusal olmayan yarı-mükemmel kod örneği vardır (örneğin bazı çift-hata düzelten BCH kodları ve bazı delinmiş Preparata kodları). Ancak mükemmel kodların aksine, yarı-mükemmerl kodlar için genel bir sınıflandırma bulunmamaktadır.
Bir $\mcc$ kodunun bir kosetinin ağırlığının, o kosetteki en küçük ağırlıklı vektörün ağırlığı olduğunu hatırlayalım. Aşağıdaki teoremi örtme yarıçapının tanımından kolayca elde edebiliriz. Teorem, örtme yarıçapının kodun kosetlerinin ağırlıklarıyla nasıl ilişkili olduğunu ortaya koymaktadır.
Teorem 6.4: Örtme Yarıçapının Karakterizasyonu
- $\rho(\mcc)$, $\mcc$'nin en büyük ağırlığa sahip kosetinin ağırlığıdır.
- $\rho(\mcc)$, sıfırdan farklı her sendromun $H$'nin en fazla $s$ sütununun bir doğrusal kombinasyonu olduğu ve bazı sendromlar için $s$ tane sütunun gerektiği en küçük $s$ sayısıdır.
📝 Ödev 6.7 (MTK698-2026) | ⏰ Son Teslim: 12.04.2026 23:59
Bu bölümü, özellikle daha önce ele alınan kodlar ve koset öncüleri ile ilgili, örtme yarıçapı hakkında bazı temel bilgileri bir araya getirerek bitiriyoruz.
Teorem 6.5: Örtme Yarıçapı Özellikleri
Eğer $\mcc=C_{1}\oplus C_{2}$ ise $\rho(\mcc)=\rho(C_{1})+\rho(C_{2})$'dir.
- $\rho(\mcc^{*})=\rho(\mcc)$ veya $\rho(\mcc^{*})=\rho(\mcc)-1$'dir.
- $\rho(\widehat{\mcc})=\rho(\mcc)$ veya $\rho(\widehat{\mcc})=\rho(\mcc)+1$'dir.
Eğer $q=2$ ise $\rho(\widehat{\mcc})=\rho(\mcc)+1$'dir.
- $\mathbf{x}$, $\mcc$'nin bir koset öncüsü olsun. Eğer $\mathbf{x}'\in\ff_{q}^{n}$, sıfırdan farklı tüm bileşenleri $\mathbf{x}$'in karşılık gelen bileşenleriyle aynı olan bir vektör ise $\mathbf{x}'$ de $\mcc$'nin bir koset öncüsüdür. Özel olarak, ağırlığı $s$ olan bir koset varsa her $0\leq t < s$ için ağırlığı $t$ olan bir koset de vardır.
Kanıt
İlk üç kısmın ispatı alıştırma olarak bırakılmıştır.
(iv) $\mathbf{x}=x_{1}\cdots x_{n}$, $\mcc$'nin bir koset öncüsü olsun. $\mathbf{x}'=x_{1}\cdots x_{n}1\in\ff_{2}^{n+1}$ alalım. (iii)'ten $\mathbf{x}'$'nün $\widehat{\mcc}$'nin bir koset öncüsü olduğunu göstermek yeterlidir. $\mathbf{c}=c_{1}\cdots c_{n}\in\mcc$ olsun ve $\widehat{\mathbf{c}}=c_{1}\cdots c_{n}c_{n+1}$ onun genişletilmiş hâli olsun. Eğer $\mathbf{c}$ çift ağırlıklı ise $\operatorname{wt}(\widehat{\mathbf{c}}+\mathbf{x}')=\operatorname{wt}(\mathbf{c}+\mathbf{x})+1\geq\operatorname{wt}(\mathbf{x})+1$ olur. $\mathbf{c}$'nin tek ağırlıklı olduğunu varsayalım. Bu durumda $\operatorname{wt}(\widehat{\mathbf{c}}+\mathbf{x}')=\operatorname{wt}(\mathbf{c}+\mathbf{x})$ olur. Eğer $\mathbf{x}$ çift (tek) ağırlıklı ise $\mathbf{c}+\mathbf{x}$ tek (çift) ağırlıklıdır ve dolayısıyla $\operatorname{wt}(\mathbf{c}+\mathbf{x})>\operatorname{wt}(\mathbf{x})$ olur çünkü $\mathbf{x}$ bir koset öncüsüdür. Her durumda $\operatorname{wt}(\widehat{\mathbf{c}}+\mathbf{x}')\geq\operatorname{wt}(\mathbf{x})+1=\operatorname{wt}(\mathbf{x}')$ olur ve dolayısıyla $\mathbf{x}'$ bir koset öncüsüdür.
(v) $\mathbf{x}=x_{1}\cdots x_{n}$ bir koset öncüsü olsun. Tümevarım sayesinde, $\mathbf{x}'=x_{1}'\cdots x_{n}'$, öyle ki her $j\neq i$ için $x_{j}=x_{j}'$ ve $x_{i}\neq x_{i}'=0$ şeklinde bir vektör için sonucu kanıtlamak yeterlidir. $\operatorname{wt}(\mathbf{x})=\operatorname{wt}(\mathbf{x}')+1$'dir. $\mathbf{x}'$'nin bir koset öncüsü olmadığını varsayalım. Bu durumda $\mathbf{x}'+\mathbf{c}$ bir koset öncüsü olacak şekilde bir $\mathbf{c}\in\mcc$ kod sözcüğü vardır ve dolayısıyla
$$\operatorname{wt}(\mathbf{x}'+\mathbf{c})\leq\operatorname{wt}(\mathbf{x}')-1=\operatorname{wt}(\mathbf{x})-2$$olur. Ancak $\mathbf{x}$ ve $\mathbf{x}'$ yalnızca bir koordinatta farklı olduğundan, $\operatorname{wt}(\mathbf{x}+\mathbf{c})\leq\operatorname{wt}(\mathbf{x}'+\mathbf{c})+1$ olur. Bunu kullanarak $\operatorname{wt}(\mathbf{x}+\mathbf{c})\leq\operatorname{wt}(\mathbf{x})-1$ elde edilir ki bu da $\mathbf{x}$'in koset öncüsü olmasıyla çelişir.
📝 Ödev 6.8 (MTK698-2026) | ⏰ Son Teslim: 12.04.2026 23:59
Aşağıdaki örnek, bir kodun genişletilmesi veya delinmesinin örtme yarıçapını değiştirmeyebileceğini göstermektedir. Bunu yukarıdaki teoremin (ii) ve (iii) kısımlarıyla karşılaştırınız.
Örnek 6.18
$A_q(n,d)$ ve $B_q(n,d)$
Kolayca görülebilir ki $B_{q}(n,d) \leq A_{q}(n,d)\le q^n$ ve $B_q(n,d)$, $q$'nun bir kuvvetidir. Buna göre $B_q(n,d)$, $A_q(n,d)$ için bir alt sınır, $A_q(n,d)$ de $B_q(n,d)$ için bir üst sınır sağlar. Ayrıca Küre Paketleme Sınırı, $A_{q}(n,d)$ için bir üst sınır sağlar ve bu sınır doğal olarak $B_{q}(n,d)$'nin de bir üst sınırıdır. Bu nedenle, $A_{q}(n,d)$ ve $B_{q}(n,d)$'nin değerlerini belirlemek, kodlama kuramında önemli bir araştırma alanıdır. Bu fonksiyonların tam değerlerini bulmak genellikle zordur, ancak çeşitli sınırlar ve tahminler geliştirilmiştir. Belli uzunluklar ve minimum uzaklık değerleri için $A_{q}(n,d)$ ve $B_{q}(n,d)$'nin değerleri bilinmektedir. Bu değerler, güncel literatürdeki tablolar ve veritabanlarında bulunabilir. (Örneğin, https://codetables.de/ gibi kaynaklarda bu tür bilgiler mevcuttur.)
Teorem 6.6
- $A_{q}(n,d)\leq A_{q}(n-1,d-1)$ ve $B_{q}(n,d)\leq B_{q}(n-1,d-1)$, ve
- $d$ çift ise $A_{2}(n,d)=A_{2}(n-1,d-1)$ ve $B_{2}(n,d)=B_{2}(n-1,d-1)$.
Ayrıca:
- $d$ çift ve $M=A_{2}(n,d)$ ise tüm kod sözcüklerinin ağırlığı çift olan ve tüm kod sözcüğü çiftleri arasındaki uzaklık da çift olan bir ikili $(n,M,d)$ kodu vardır.
Kanıt
(ii)'yi kanıtlamak için yalnızca $\mcc$ doğrusal olduğunda $A_{2}(n,d)\geq A_{2}(n-1,d-1)$ (veya $B_{2}(n,d)\geq B_{2}(n-1,d-1)$) olduğunu göstermemiz yeterli olur. Bu amaçla $\mcc$, $M$ adet kod sözcüğüne saip, $n-1$ uzunluklu, minimum uzaklığı $d-1$ olan bir ikili kod olsun. $\mcc$'ye bir eşlik denetim biti ekleyerek $n$ uzunluğunda ve $d$ minimum uzaklığında bir $\widehat{\mcc}$ kodu elde edilir; çünkü $d-1$ tektir. $\widehat{\mcc}$, $M$ adet kod sözcüğüne sahip olduğundan $A_{2}(n,d)\geq A_{2}(n-1,d-1)$ (veya $B_{2}(n,d)\geq B_{2}(n-1,d-1)$) elde edilir.
(iii) için, $\mcc$ ikili bir $(n,M,d)$ kodu ve $d$ çift ise daha önce belirtildiği gibi delinmiş kod $\mcc^{*}$, bir $(n-1,M,d-1)$ kodudur. $\mcc^{*}$'ın genişletilmesi, $d-1$ tek olduğundan bir $(n,M,d)$ kodu olan $\widehat{\mcc^{*}}$'ı verir; üstelik bu kod yalnızca çift ağırlıklı kod sözcüklerine sahiptir. $\mathrm{d}(\mathbf{x},\mathbf{y})=\mathrm{wt}(\mathbf{x}+\mathbf{y})=\mathrm{wt}(\mathbf{x})+\mathrm{wt}(\mathbf{y})-2\mathrm{wt}(\mathbf{x}\wedge\mathbf{y})$ olduğundan, kod sözcükleri arasındaki uzaklık da çifttir.
Örnek 6.19
Küre Paketleme Sınırında $n=7$ ve $d=4$ (yani $t=1$) kullanıldığında $A_{2}(7,4)\leq 16$ bulunur. Öte yandan, $n=6$ ve $d=3$ (yine $t=1$) kullanıldığında Küre Paketleme Sınırı $64/7$ sayısını verir, bu da $A_{2}(6,3)\leq 9$ anlamına gelir. O hâlde Teorem 6.6 (ii) gereği hem $A_{2}(7,4)$ hem de $A_{2}(6,3)$ için $9$ bir üst sınırdır.
Teorem 6.7
Kanıt
• $A_{q}(n,d)\leq A_{q}(n-1,d-1)$ ve $B_{q}(n,d)\leq B_{q}(n-1,d-1)$, ve
• $d$ çift ise $A_{2}(n,d)=A_{2}(n-1,d-1)$ ve $B_{2}(n,d)=B_{2}(n-1,d-1)$.
Ayrıca:
• $d$ çift ve $M=A_{2}(n,d)$ ise tüm kod sözcüklerinin ağırlığı çift olan ve tüm kod sözcüğü çiftleri arasındaki uzaklık da çift olan bir ikili $(n,M,d)$ kodu vardır.
📖 Detaya Git (ii) gereği $A_{2}(n,2)=A_{2}(n-1,1)$ olur. Ancak $A_{2}(n-1,1)\leq 2^{n-1}$ ve $\ff_{2}^{n-1}$ uzayının tamamı, uzunluğu $n-1$ ve minimum uzaklığı $1$ olan bir kod olduğundan $A_{2}(n-1,1)=2^{n-1}$ bulunur. Buna göre $\ff_{2}^{n-1}$ doğrusal olduğundan, Teorem 6.6 $d>1$ olsun. O zaman:
• $A_{q}(n,d)\leq A_{q}(n-1,d-1)$ ve $B_{q}(n,d)\leq B_{q}(n-1,d-1)$, ve
• $d$ çift ise $A_{2}(n,d)=A_{2}(n-1,d-1)$ ve $B_{2}(n,d)=B_{2}(n-1,d-1)$.
Ayrıca:
• $d$ çift ve $M=A_{2}(n,d)$ ise tüm kod sözcüklerinin ağırlığı çift olan ve tüm kod sözcüğü çiftleri arasındaki uzaklık da çift olan bir ikili $(n,M,d)$ kodu vardır.
📖 Detaya Git gereğince $2^{n-1}=B_{2}(n-1,1)=B_{2}(n,2)$ elde edilir.
Teorem 6.8
- $A_q(n,1)=B_q(n,1)=q^n$.
- $A_{q}(n,n)=B_{q}(n,n)=q$.
Kanıt
Dikkat edilirse $\ff_q^n$ bir $[n,n,1]$-doğrusal kodudur. Buna göre $q^n\le B_q(n,1)\le q^n$ ve böylece $q^n=B_q(n,1)\le A_q(n,1)\le q^n$ olur. Dolayısıyla $A_q(n,1)=B_q(n,1)=q^n$ bulunur.
- $n$ uzunluğundaki $\one$ (tümü-bir) vektörünün $q$ tane katından oluşan (yani $\ff_{q}$ üzerindeki tekrarlama kodundan oluşan) $q$ büyüklüğündeki doğrusal kodun minimum uzaklığı $n$'dir. Buna göre $A_{q}(n,n)\geq B_{q}(n,n)\geq q$ olur. Eğer $A_{q}(n,n)>q$ ise $q$'dan fazla kod sözcüğüne sahip minimum uzaklığı $n$ olan bir kod var demektir. Dolayısıyla kod sözcüklerinden en az ikisi bir koordinatta aynı değeri alır; ancak o zaman bu iki kod sözcüğü arasındaki uzaklık $n$'den küçük olur ki bu da bir çelişkidir. Böylece $A_{q}(n,n)=B_{q}(n,n)=q$ elde edilir.
Teorem 6.9
Kanıt
📝 Ödev 6.9 (MTK698-2026) | ⏰ Son Teslim: 12.04.2026 23:59
- $i$ sabit bir koordinat olmak üzere, $\mcc$'nin tüm kod sözcüklerinin $i$-yinci koordinatında $0$ bulunduğunu ya da $i$-yinci koordinatında $0$ bulunan tüm kod sözcüklerinden oluşan alt kümenin $\mcc$'nin bir $[n,k-1,d]$ doğrusal alt kodu olduğunu kanıtlayınız.
- $B_{q}(n,d)\leq q\,B_{q}(n-1,d)$ olduğunu kanıtlayınız.
Teorem 6.10
Kanıt
Alt Sınırlar
Küre Örtme Sınırı
Teorem 6.11: Küre Örtme Sınırı
Kanıt
(Bu nedenle, $S_{\ff_q}(\mathbf{c},d-1)$ ($1\leq i\leq M$) kürelerinin $\ff_q^{n}$'yi örttüğü söylenir; sınırın adı da buradan gelir.)
$|\ff_q^{n}|=q^{n}$ ve $|S_{\ff_q}(\mathbf{c}_{i},d-1)|=\displaystyle\sum_{i=0}^{d-1}\binom{n}{i}(q-1)^{i}$ olduğundan $$q^{n}\leq M\cdot \displaystyle\sum_{i=0}^{d-1}\binom{n}{i}(q-1)^{i}$$elde edilir. Buradan
$$\frac{q^{n}}{\displaystyle\sum_{i=0}^{d-1}\binom{n}{i}(q-1)^{i}}\leq M=A_{q}(n,d)$$sonucu çıkar.
Gilbert–Varshamov Sınırı
Gilbert–Varshamov Sınırı, kodlama kuramındaki en önemli alt sınırlardan biridir. Edgar Gilbert 1952'de doğrusal olmayan kodlar için bu sınırı ilk kez ortaya koymuş, R. R. Varshamov ise 1957'de bağımsız olarak aynı sonucu doğrusal kodlara genişletmiştir. Bu sınır, yaklaşık otuz yıl boyunca bilinen en iyi asimptotik alt sınır olarak kalmış ve uzun süre iyileştirilemeyeceği düşünülmüştür. Ancak 1981'de V. D. Goppa, cebirsel geometri kodlarını (Goppa kodları) kullanarak bu sınırı aşan doğrusal kodların inşa edilebileceğini göstermiş; ardından Tsfasman, Vlăduţ ve Zink (1982), yeterince büyük alfabe boyutları ($q\geq 49$) için Gilbert–Varshamov Sınırını kesin olarak geçen kodların varlığını kanıtlamıştır. Bu çığır açıcı sonuç, cebirsel geometrinin kodlama kuramındaki rolünü kökten değiştirmiş ve cebirsel geometri kodları alanının doğmasına öncülük etmiştir.
Teorem 6.12: Gilbert–Varshamov Sınırı
ise $\ff_{q}$ üzerinde minimum uzaklığı en az $d$ olan bir $[n,k]$-doğrusal kod vardır.
Kanıt
Yukarıdaki koşul sağlandığında, $\ff_{q}$ üzerinde her $d-1$ sütunu doğrusal bağımsız olan bir $(n-k)\times n$ boyutlu $H$ matrisinin var olduğunu göstereceğiz.
$H$'yi şu şekilde inşa edelim: $\mathbf{c}_{j}$, $H$'nin $j$-inci sütununu göstersin. $\mathbf{c}_{1}$, $\ff_{q}^{n-k}$'de sıfırdan farklı herhangi bir vektör olsun. $\mathbf{c}_{2}$, $\mathbf{c}_{1}$'in gerdiği uzayda olmayan herhangi bir vektör olsun. Herhangi bir $2\leq j\leq n$ için $\mathbf{c}_{j}$, $\mathbf{c}_{1},\ldots,\mathbf{c}_{j-1}$ vektörlerinin $d-2$ veya daha azının doğrusal gerdiği uzayda olmayan bir vektör olsun. $\mathbf{c}_{1},\ldots,\mathbf{c}_{j-1}$ ($2\leq j\leq n$) vektörlerinin $d-2$ veya daha azının doğrusal gerdiği uzaydaki vektör sayısı $$\sum_{i=0}^{d-2}\binom{j-1}{i}(q-1)^{i}\leq\sum_{i=0}^{d-2}\binom{n-1}{i}(q-1)^{i}< q^{n-k}$$ile verilir. Dolayısıyla $\mathbf{c}_{j}$ ($2\leq j\leq n$) vektörü her zaman bulunabilir.
Bu şekilde inşa edilen $H$ matrisi $(n-k)\times n$ boyutundadır ve her $d-1$ sütunu doğrusal bağımsızdır. $H$'nin sıfır uzayı, $\ff_{q}$ üzerinde uzunluğu $n$, minimum uzaklığı en az $d$ ve boyutu en az $k$ olan bir doğrusal koddur.
Singleton Sınırı ve MDS Kodlar
Üst sınırlar açısından çok önemli ve zarif bir sınır olan Singleton Sınırını burada ele alıyoruz.
Teorem 6.13: Singleton Sınırı
Özel olarak bir $[n,k,d]$-doğrusal kodu için $d\leq n-k+1$ eşitsizliği sağlanır.
Kanıt
Tanım 6.5
Singleton Sınırını eşitlikle sağlayan, yani $|C|=q^{n-d+1}$ olan bir $(n,M,d)$-koda MDS (maksimum uzaklıkla ayrılabilir) kod denir. Bir $[n,k,d]$ doğrusal kodun MDS olma koşulu $d=n-k+1$'dir.
MDS kodlarının bazı temel özelliklerini belirleyelim.
Teorem 6.14
- $C^{\perp}$ bir $[n,n-k,k+1]$ MDS kodudur.
- $C$'nin herhangi bir koordinattan delinmiş kodu bir $[n-1,k,d-1]$ MDS kodudur (sadece $d\geq 2$ ise).
- $C$'nin herhangi bir kod sözcüğü üzerinden kısaltılmış kodu bir $[n-1,k-1,d]$ MDS kodudur ($n>k$ ise).
Örnek 6.20
Reed–Solomon (RS) kodları MDS kodların en önemli örneklerini oluşturur. $\ff_q$ üzerinde farklı elemanlardan oluşan bir $\alpha_1,\alpha_2,\ldots,\alpha_n$ kümesi verilsin. $1 \leq k \leq n \leq q$ ise derecesi en fazla $k-1$ olan tüm polinomların $\alpha_1,\alpha_2,\ldots,\alpha_n$ noktalarında değerlenmesiyle oluşturulan
$$\text{RS}(n,k)=\{(f(\alpha_1),\ldots,f(\alpha_n)) : f(x)\in \ff_q[x],\deg f< k\}$$şeklindeki kod bir $[n,k,n-k+1]$ MDS kodudur.
Plotkin Sınırı
Plotkin Sınırı, özellikle minimum uzaklığın uzunluğun yarısından büyük olduğu durumda (yani $d>n/2$) Küre Paketleme Sınırından daha güçlü bir üst sınır verir. Önce ikili kod durumunu ele alalım.
Teorem 6.15: Plotkin Sınırı
Eğer $d$ tek ise $n<2d+1$ iken daha sıkı olan
$$A(n,d)\leq 2\left\lfloor\frac{d+1}{2d+1-n}\right\rfloor$$sınırı vardır.
Kanıt
Diğer taraftan her koordinat $l=1,2,\ldots,n$ için, $l$-inci koordinatında $0$ olan sözcük sayısını $n_{0}^{(l)}$, $1$ olan sözcük sayısını $n_{1}^{(l)}$ ile gösterelim. $l$-inci koordinattaki uzaklıklara katkı $2n_{0}^{(l)}n_{1}^{(l)}$ 'dir ve $n_{0}^{(l)}+n_{1}^{(l)}=M$ olduğundan bu katkı en fazla $M$ bir tek sayı olduğunda $\{n_0^l,n_1^l\}=\{\frac{M-1}{2},\frac{M+1}{2}\}$ iken, $M$ bir çift sayı olduğunda $n_0^l=n_1^l=\frac{M}{2}$ iken olur. Buna göre $2n_0^ln_1^l\le M^{2}/2$'dir. Tüm koordinatları (burada $n$ tane) toplarsak
$$D\leq \frac{nM^{2}}{2}.$$İki eşitsizlik birleştirildiğinde $M(M-1)d\leq nM^{2}/2$ ve $M\leq \frac{2d}{2d-n}$ elde edilir. $M$ tamsayı olduğundan $M\leq 2\lfloor d/(2d-n)\rfloor$ sonucu ortaya çıkar.
• $A_{q}(n,d)\leq A_{q}(n-1,d-1)$ ve $B_{q}(n,d)\leq B_{q}(n-1,d-1)$, ve
• $d$ çift ise $A_{2}(n,d)=A_{2}(n-1,d-1)$ ve $B_{2}(n,d)=B_{2}(n-1,d-1)$.
Ayrıca:
• $d$ çift ve $M=A_{2}(n,d)$ ise tüm kod sözcüklerinin ağırlığı çift olan ve tüm kod sözcüğü çiftleri arasındaki uzaklık da çift olan bir ikili $(n,M,d)$ kodu vardır.
📖 Detaya Git (ii) gereğince $A(n,d)=A(n+1,d+1)$ olur. Eğer $n+1 < 2(d+1)$, yani $n < 2d + 1$ ise yukarıdaki sınırdan dolayı $$A(n+1,d+1)\le 2\left\lfloor \frac{d+1}{2d + 1 - n}\right\rfloor$$
bulunur.
Örnek 6.21
Yukarıdaki teoremde verilen ilk Plotkin sınırı d bir tek sayı olduğunda gevşek bir sınırdır. Bu nedenle ikinci verilen sınır $A(n,d)$ için daha sıkı bir sınır belirler. Örneğin $A(5,3)$ için ilk verilen sınır $\frac{6}{6-5}=6$ iken ikici verilen sınır d=3 tek olduğundan $\frac{8}{2}=4$ olarak bulunur. Gerçekten de $A(5,3)=4$'tür çünkü $\mcc=\{00000,11100,00111,11011\}$ kodu ikili (5,4,3)-kodudur.
Yukarıdaki ikili Plotkin Sınırı, genel bir $q$-lu alfabe için de genelleştirilebilir. Bu genelleştirmede, $r=1-q^{-1}$ oranı kritik bir rol oynar.
Teorem 6.16: Genel Plotkin Sınırı
Kanıt
olsun. $\mathbf{c}\neq\mathbf{c}'$ olan her çift için $d(\mathbf{c},\mathbf{c}')\geq d$ olduğundan
$$M(M-1)d\leq T$$elde edilir. Şimdi $\mathcal{A}$, satırları $C$'nin $M$ adet kod sözcüğünden oluşan $M\times n$ dizisi olsun. $1\leq i\leq n$ ve $a\in A$ için $n_{i,a}$, $\mathcal{A}$'nın $i$-inci sütununda $a$'ya eşit olan giriş sayısını göstersin. O zaman her $1\leq i\leq n$ için $\sum_{a\in A}n_{i,a}=M$'dir. $\mathbf{c}=(c_{1},\ldots,c_{n})$ ve $\mathbf{c}'=(c_{1}',\ldots,c_{n}')$ yazılırsa
$$T=\sum_{i=1}^{n}\left(\sum_{\mathbf{c}\in C}\sum_{\mathbf{c}'\in C}d(c_{i},c_{i}')\right)=\sum_{i=1}^{n}\sum_{a\in A}n_{i,a}(M-n_{i,a})=M^{2}n-\sum_{i=1}^{n}\sum_{a\in A}n_{i,a}^{2}$$olur. $m=q$ ve $a_{1}=\cdots=a_{q}=1$ alarak Cauchy–Schwarz eşitsizliğini$\left(\sum_{r=1}^{m}a_{r}b_{r}\right)^{2}\leq\left(\sum_{r=1}^{m}a_{r}^{2}\right)\left(\sum_{r=1}^{m}b_{r}^{2}\right)$ uygularsak
$$T\leq M^{2}n-\sum_{i=1}^{n}q^{-1}\left(\sum_{a\in A}n_{i,a}\right)^{2}=M^{2}rn$$elde edilir. $M(M-1)d\leq M^{2}rn$ eşitsizliğinden $M\leq d/(d-rn)$ ve $M$ tamsayı olduğundan
$$A_{q}(n,d)\leq\left\lfloor\frac{d}{d-rn}\right\rfloor$$sonucu çıkar.