Giới hạn Singleton

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

Trong lý thuyết mã hóa, giới hạn Singleton, đặt theo tên của Richard Collom Singleton, là một giới hạn trên cho kích thước của mã khối C với độ dài n, kích thước r, và khoảng cách d (mỗi mã tự có độ dài n, dùng để biểu diễn một thông điệp có độ dài r, và hai mã tự khác nhau có ít nhất d kí hiệu khác nhau).

Phát biểu của giới hạn Singleton[sửa | sửa mã nguồn]

Khoảng cách của một tập C bao gồm các mã tự có độ dài n được định nghĩa như sau:

d = \min_{x,y \in C, x \neq y} d(x,y)

trong đó d(x,y)khoảng cách Hamming giữa xy. Biểu thức A_{q}(n,d) biểu diễn số lượng mã tự tối đa của một mã khối có độ dài n, khoảng cách d, và sử dụng kí hiệu trong một bảng chữ cái kích thước q.

Giới hạn Singleton khẳng định rằng

A_q(n,d) \leq q^{n-d+1}.

Chứng minh[sửa | sửa mã nguồn]

Trước hết, ta nhận thấy có q^n chuỗi độ dài n gồm các kí kiệu trong một bảng chữ cái kích thước q, do mỗi kí kiệu có q lựa chọn khác nhau, độc lập với các kí hiệu còn lại.

Giả sử C là một mã có khoảng cách d. Rõ ràng mọi mã tự c \in C là khác nhau. Nếu ta xóa d-1 kí hiệu đầu tiên của mỗi mã tự thì chúng vẫn khác nhau do khoảng cách Hamming giữa các mã tự ban đầu là ít nhất d. Do đó số lượng mã tự khác nhau sau khi xóa là không đổi.

Các mã tự mới có chiều dài

n-(d-1)=n-d+1

và do đó có tối đa

q^{n-d+1}

mã tự khác nhau. Do đó số mã tự khác nhau trong mã C cũng được giới hạn bởi

|C| \le A_q(n,d) \leq q^{n-d+1}.

Mã MDS[sửa | sửa mã nguồn]

Mã khối đạt đến giới hạn Singleton gọi là mã MDS (viết tắt tiếng Anh - maximum distance separable). Một vài ví dụ của mã MDS bao gồm mã chỉ có đúng một mã tự (khoảng cách n), mã sử dụng toàn bộ (F_{q})^{n} (khoảng cách 1), mã sử dụng đúng 1 bit chẵn lẻ (khoảng cách 2) và mã đối ngẫu của nó. Các mã này gọi là các mã MDS "tầm thường".

Trong trường hợp bảng chữ cái nhị phân, chỉ có các mã MDS tầm thường.[1]

Một vài ví dụ không tầm thường của mã MDS bao gồm mã Reed-Solomon và các phiên bản mở rộng của nó.[2]

Xem thêm[sửa | sửa mã nguồn]

Ghi chú[sửa | sửa mã nguồn]

  1. ^ xem, chẳng hạn, Vermani (1996), Mệnh đề 9.2.
  2. ^ xem, chẳng hạn, MacWilliams và Sloane, Ch. 11.

Tài liệu tham khảo[sửa | sửa mã nguồn]

Đọc thêm