GT 6: Thử nhóm bất ứng biến giải mã nhanh
6. Thử nhóm bất ứng biến giải mã nhanh
6.1. Ý tưởng của Kautz-Singleton
Hồi 1964, Kautz và Singleton đề xuất cách xây dựng ma trận -phân-cách dựa trên hai ý tưởng chính. Thứ nhất là nếu các cột của ma trận có “cân nặng” (số số
trên cột) đủ lớn và nếu hai cột bất kỳ có phần giao đủ nhỏ thì ma trận sẽ là ma trận phân cách. Thứ hai là ta có thể dùng phương pháp nối mã (code concatenation) để xây dựng một ma trận thỏa tính chất thứ nhất. Chúng ta thảo luận ý tưởng của Kautz-Singleton trước, sau đó chỉ ra cách dùng ý tưởng này và một ý mới để xây dựng ma trận phân cách giải mã nhanh được.
Bổ đề 1 Gọi
là một ma trận nhị phân
mà mỗi cột có cân nặng ít nhất là
, và phần giao của hai cột bất kỳ (các số
chung của hai cột) có lực lượng nhiều nhất là
. Thì,
là ma trận
-phân-cách với bất kỳ
nào thỏa mãn
. Cụ thể là
sẽ là ma trận
-phân-cách.
Bổ đề này dễ chứng minh. Ta nói tiếp ý tưởng thứ hai. Trước hết hãy định nghĩa phép nối mã.
Gọi là một mã
, nghĩa là một ánh xạ từ
vào
, trong đó
. (Phép nối mã có thể định nghĩa tổng quát hơn, nhưng ta không cần điều đó.) Như vậy, mỗi ký tự mã của
là một thành viên của tập
gồm
phần tử, và vì thế cũng có thể xem như một thành viên của tập
. Mỗi một từ mã của
có
vị trí. Mã
sẽ được gọi là mã ngoài (outer code).




