1236214
Thước Golomb
https://vi.wikipedia.org/wiki?curid=1236214
Title: Thước Golomb
Hiện nay vẫn chưa rõ độ phức tạp tính toán của việc tìm ra thước tối ưu bậc "n" (trong đó "n" được cho dưới dạng nhất phân). Đã từng có những dự đoán nó là một bài toán NP-khó. Có những bài toán có liên hệ đến việc xây dựng thước Golomb được chứng minh là NP-khó, nhưng người ta cũng nhấn mạnh rằng không có bài toán NP-đầy đủ đã biết nào có dạng tương tự như việc tìm thước Golomb tối ưu.
Định nghĩa.
Thước Golomb dưới dạng tập hợp.
Một tập hợp số nguyên
formula_1
là một thước Golomb khi và chỉ khi
formula_2
"Bậc" của thước Golomb là formula_3 và "chiều dài" của thước là formula_4. Dạng chính tắc có formula_5 và nếu formula_6, formula_7. Có thể thu được dạng đó bằng cách thực hiện phép tịnh tiến và lấy đối xứng.
Thước Golomb dưới dạng hàm số.
Một đơn ánh
formula_8
với formula_9 và formula_10 là một thước Golomb khi và chỉ khi
formula_11
"Bậc" của thước là formula_3 và "chiều dài" của thước là formula_13. Dạng chính tắc có
Tối ưu.
Thước Golomb bậc formula_3 và chiều dài n có thể là tối ưu theo một trong hai tiêu chuẩn sau:
Thuật ngữ "thước Golomb tối ưu" thường được dùng để chỉ loại thứ hai.
Ứng dụng thực tiễn.
Lý thuyết thông tin/Sửa lỗi.
Thước Golomb được dùng trong lý thuyết thông tin, cụ thể là trong mã sửa lỗi.
Lựa chọn tần số radio.
Thước Golomb được dùng cho việc lựa chọn tần số radio để giảm ảnh hưởng của nhiễu biến điệu tương hỗ trong cả trường hợp gần mặt đất và trong không gian.
Vị trí đặt ăngten radio.
Thước Golomb được dùng trong thiết kế của mảng pha của ăngten vô tuyến, chẳng hạn như trong kính thiên văn vô tuyến. Ở các điểm thu phát sóng, các ăngten thường nằm ở vị trí như trong thước Golomb [0,1,4,6].
Phương pháp xây dựng.
Có nhiều phương thức xây dựng thước Golomb tiệm cận tối ưu.