Chặn Gilbert–Varshamov

Trong lý thuyết mã hóa, chặn Gilbert–Varshamov (chứng minh bởi Edgar Gilbert^[1] và một cách độc lập bởi Rom Varshamov^[2]) là một giới hạn của các tham số của một mã (không nhất thiết tuyến tính). Nó còn được gọi là chặn Gilbert–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–Varshamov cho mã tuyến tính.

Phát biểu

Đặt

${\displaystyle A_{q}(n,d)}$

là số lớn nhất các mã tự của mã ${\displaystyle C}$ 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 ${\displaystyle \mathbb {F} _{q}}$ gồm có q phần tử).

Khi đó:

${\displaystyle A_{q}(n,d)\geq {\frac {q^{n}}{\sum _{j=0}^{d-1}{\binom {n}{j}}(q-1)^{j}}}.}$

Chứng minh

Đặt ${\displaystyle C}$ là một mã độ dài ${\displaystyle n}$, khoảng cách Hamming nhỏ nhất ${\displaystyle d}$ với kích thước cực đại:

${\displaystyle |C|=A_{q}(n,d).\,}$

Khi đó với mọi ${\displaystyle x\in \mathbb {F} _{q}^{n}}$ , tồn tại một mã tự ${\displaystyle c_{x}\in C}$ sao cho khoảng cách Hamming ${\displaystyle d(x,c_{x})}$ giữa ${\displaystyle x}$ và ${\displaystyle c_{x}}$ thỏa mãn

${\displaystyle d(x,c_{x})\leq d-1}$

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 ${\displaystyle |C|}$.

Do đó ${\displaystyle \mathbb {F} _{q}^{n}}$ được phủ bởi hợp của các hình cầu bán kính d − 1 với tâm ở các điểm ${\displaystyle c\in C}$:

${\displaystyle \mathbb {F} _{q}^{n}=\cup _{c\in C}B(c,d-1).\,}$

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

${\displaystyle \sum _{j=0}^{d-1}{\binom {n}{j}}(q-1)^{j}}$

điểm vì có thể chọn thay đổi không quá ${\displaystyle d-1}$ trong số ${\displaystyle n}$ 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 q-1 giá trị mới. Do đó

${\displaystyle {\begin{aligned}|\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{aligned}}}$

Nghĩa là:

${\displaystyle A_{q}(n,d)\geq {\frac {q^{n}}{\sum _{j=0}^{d-1}{\binom {n}{j}}(q-1)^{j}}}}$

(Ở đây ta sử dụng tính chất: ${\displaystyle |\mathbb {F} _{q}^{n}|=q^{n}}$).

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 ${\displaystyle A_{q}(n,d)\geq q^{k}}$ trong đó k là số nguyên lớn nhất thỏa mãn

${\displaystyle q^{k}<{\frac {q^{n}}{\sum _{j=0}^{d-2}{\binom {n-1}{j}}(q-1)^{j}}}.}$

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

1. Gilbert, E. N. (1952), “A comparison of signalling alphabets”, Bell System Technical Journal, 31: 504–522
2. Varshamov, R. R. (1957), “Estimate of the number of signals in error correcting codes”, Dokl. Acad. Nauk SSSR, 117: 739–741.