Xem mã nguồn của Chặn Gilbert–Varshamov

Trong [[lý thuyết mã hóa]], '''chặn Gilbert–Varshamov''' (chứng minh bởi [[Edgar Gilbert]]<ref>{{chú thích|first=E. N.|last=Gilbert|authorlink=Edgar Gilbert|title=A comparison of signalling alphabets|journal=[[Bell System Technical Journal]]|volume=31|year=1952|pages=504–522}}</ref> và một cách độc lập bởi Rom Varshamov<ref>{{chú thích|first=R. R.|last=Varshamov|title=Estimate of the number of signals in error correcting codes|journal=Dokl. Acad. Nauk SSSR|volume=117|year=1957|pages=739–741}}.</ref>) là một giới hạn của các tham số  của một [[mã]] (không nhất thiết [[mã tuyến tính|tuyến tính]]). Nó còn được gọi là '''chặn Gilbert–[[Claude Shannon|Shannon]]–Varshamov''' (hay '''chặn GSV'''), nhưng tên gọi "chặn Gilbert–Varshamov" là phổ biến nhất. Varshamov chứng minh kết quả này bằng phương pháp xác suất. Xem thêm về chứng minh này ở [[chặn Gilbert&ndash;Varshamov cho mã tuyến tính]].

==Phát biểu==
Đặt

:<math>A_q(n,d)</math>

là số lớn nhất các mã tự của mã <math>C</math> trên bảng chữ cái kích thước ''q'', độ dài ''n'' và khoảng cách nhỏ nhất ''d'' (có thể coi bảng chữ cái là [[trường (đại số)|trường]] <math>\mathbb{F}_q</math> gồm có ''q'' phần tử).

Khi đó:

:<math>A_q(n,d) \geq \frac{q^n}{\sum_{j=0}^{d-1} \binom{n}{j}(q-1)^j}.</math>

==Chứng minh==
Đặt <math>C</math> là một mã độ dài <math>n</math>, [[khoảng cách Hamming]] nhỏ nhất <math>d</math> với kích thước cực đại:

:<math>|C|=A_q(n,d).\,</math>

Khi đó với mọi <math>x\in\mathbb{F}_q^n</math>&nbsp;, tồn tại một mã tự <math>c_x \in C</math> sao cho khoảng cách Hamming <math>d(x,c_x)</math> giữa <math>x</math> và <math>c_x</math> thỏa mãn

:<math>d(x,c_x)\leq d-1</math>

vì nếu không ta có thể thêm ''x'' vào tập hợp các mã tự mà vẫn duy trì khoảng cách nhỏ nhất ''d'' – mâu thuẫn với giả thiết về tính cực đại của <math>|C|</math>.

Do đó <math>\mathbb{F}_q^n</math> được phủ bởi [[phép hợp|hợp]] của các [[quả cầu|hình cầu]] bán kính ''d''&nbsp;&minus;&nbsp;1 với [[quả cầu|tâm]] ở các điểm <math>c \in C</math>:

:<math>\mathbb{F}_q^n =\cup_{c \in C} B(c,d-1).\, </math>

Mỗi hình cầu có chứa

:<math>
\sum_{j=0}^{d-1} \binom{n}{j}(q-1)^j
</math>

điểm vì có thể chọn thay đổi không quá <math>d-1</math> trong số <math>n</math> vị trí của mã tự (so với giá trị ở tâm hình cầu) và mỗi lần thay đổi có thể lựa chọn một trong {{math|''q''-1}} giá trị mới. Do đó

:<math>
\begin{align}
|\mathbb{F}_q^n| & = |\cup_{c \in C} B(c,d-1)| \\
\\
& \leq \sum_{c \in C} |B(c,d-1)| \\
\\
& = |C|\sum_{j=0}^{d-1} \binom{n}{j}(q-1)^j \\
\\
\end{align}
</math>

Nghĩa là:

:<math>
A_q(n,d) \geq \frac{q^n}{\sum_{j=0}^{d-1} \binom{n}{j}(q-1)^j}
</math>

(Ở đây ta sử dụng tính chất: <math>|\mathbb{F}_q^n|=q^n</math>).

==Chặn chặt hơn cho lũy thừa số nguyên tố==
Khi ''q'' là lũy thừa số nguyên tố, có thể chứng minh chặn chặt hơn <math>A_q(n,d)\ge q^k</math> trong đó ''k'' là số nguyên lớn nhất thỏa mãn

: <math>q^k < \frac{q^n}{\sum_{j=0}^{d-2} \binom{n-1}{j}(q-1)^j}.</math>

==Xem thêm==

*[[Chặn Singleton]]
*[[Chặn Hamming]]
*[[Chặn Johnson]]
*[[Chặn Plotkin]]
*[[Chặn Griesmer]]
*[[Chặn Grey–Rankin]]
*[[Chặn Gilbert–Varshamov cho mã tuyến tính]]
*[[Chặn Elias-Bassalygo]]

==Tham khảo==

{{Tham khảo}}

[[Thể loại:Lý thuyết mã hóa]]