1180220
Chặn Gilbert–Varshamov
https://vi.wikipedia.org/wiki?curid=1180220
Title: Chặn Gilbert–Varshamov
Trong lý thuyết mã hóa, chặn Gilbert–Varshamov (chứng minh bởi Edgar Gilbert và một cách độc lập bởi Rom Varshamov) 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
là số lớn nhất các mã tự của mã formula_2 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 formula_3 gồm có "q" phần tử).
Khi đó:
Chứng minh.
Đặt formula_2 là một mã độ dài formula_6, khoảng cách Hamming nhỏ nhất formula_7 với kích thước cực đại:
Khi đó với mọi formula_9 , tồn tại một mã tự formula_10 sao cho khoảng cách Hamming formula_11 giữa formula_12 và formula_13 thỏa mãn
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 formula_15.
Do đó formula_16 đượ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 formula_17:
Mỗi hình cầu có chứa
điểm vì có thể chọn thay đổi không quá formula_20 trong số formula_6 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 giá trị mới. Do đó
Nghĩa là:
(Ở đây ta sử dụng tính chất: formula_24).
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 formula_25 trong đó "k" là số nguyên lớn nhất thỏa mãn