Giới hạn Singleton
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  với độ dài , kích thước , và khoảng cách  (mỗi mã tự có độ dài , dùng để biểu diễn một thông điệp có độ dài , và hai mã tự khác nhau có ít nhất  ký hiệu khác nhau).

Phát biểu của giới hạn Singleton
Khoảng cách của một tập  bao gồm các mã tự có độ dài  được định nghĩa như sau:

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

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

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

Giả sử  là một mã có khoảng cách . Rõ ràng mọi mã tự  là khác nhau. Nếu ta xóa  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 . 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

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

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

Mã MDS

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 ), mã sử dụng toàn bộ  (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.

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ó.

Xem thêm
Giới hạn Gilbert–Varshamov
Giới hạn Plotkin
Giới hạn Hamming
Giới hạn Johnson
Giới hạn Griesmer

Ghi chú

Tham khảo
 
Đọc thêm
 
 
 L. R. Vermani: Elements of algebraic coding theory, Chapman & Hall, 1996.

Lý thuyết mã hóa
Bất đẳng thức
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 với độ dài , kích thước , và khoảng cách (mỗi mã tự có độ dài , dùng để biểu diễn một thông điệp có độ dài , và hai mã tự khác nhau có ít nhất ký hiệu khác nhau) . Phát biểu của giới hạn Singleton Khoảng cách của một tập bao gồm các mã tự có độ dài được định nghĩa như sau : trong đó là khoảng cách Hamming giữa và \. Biểu thức biểu diễn số lượng mã tự tối đa của một mã khối có độ dài , khoảng cách , và sử dụng ký hiệu trong một bảng chữ cái kích thước \. Giới hạn Singleton khẳng định rằng Chứng minh Trước hết , ta nhận thấy có chuỗi độ dài gồm các ký kiệu trong một bảng chữ cái kích thước , do mỗi ký kiệu có lựa chọn khác nhau , độc lập với các ký hiệu còn lại . Giả sử là một mã có khoảng cách \. Rõ ràng mọi mã tự là khác nhau . Nếu ta xóa 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 \. 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 và do đó có tối đa mã tự khác nhau . Do đó số mã tự khác nhau trong mã cũng được giới hạn bởi Mã MDS Mã khối đạt đến giới hạn Singleton gọi là mã MDS (viết tắt tiếng Anh - maximum distance separa ble) . 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 ) , mã sử dụng toàn bộ (khoảng cách mã sử dụng đúngbit chẵn lẻ (khoảng cáchvà 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 . 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ó . Xem thêm Giới hạn Gilbert–Varshamov Giới hạn Plotkin Giới hạn Hamming Giới hạn Johnson Giới hạn Griesmer Ghi chú Tham khảo Đọc thêm L . R . Vermani : Elements of algebraic coding theory , Chapman & Hall , Lý thuyết mã hóa Bất đẳng thức