Trong lý thuyết mã hóa, mã khối là một tập hợp bao gồm nhiều mã sửa lỗi mã hóa dữ liệu theo từng khối. Có rất nhiều loại mã khối khác nhau, được sử dụng rộng rãi trong nhiều ứng dụng thực tiễn. Một nguyên nhân khiến mã khối hữu ích như vậy là nó cho phép sử dụng một tách thống nhất các phương pháp từ lý thuyết mã hóa, toán học, và khoa học máy tính để nghiên cứu về các giới hạn của mã khối. Các giới hạn đó thường ở dạng bất đẳng thức liên hệ các tham số của mã, chẳng hạn như tỉ lệ và khả năng phát hiện và sửa lỗi.

Một vài ví dụ tiêu biểu của mã khối là mã Reed–Solomon, mã Hamming, mã Hadamard, mã đồ thị giãn nở, mã Golay, mã Reed–Muller, và mã BCH. Các ví dụ này đều là các mã tuyến tính, nên chúng thường được gọi là các mã khối tuyến tính.

Mã khối và các tham sốSửa đổi

Mã sửa lỗi được dùng để truyền dữ liệu số một cách đáng tin cậy trên một kênh liên lạcnhiễu. Khi cần truyền nhiều dữ liệu bằng mã khối, người gửi chia dữ liệu thành nhiều phần nhỏ. Mỗi phần nhỏ được gọi là một thông điệp và thuật toán mã hóa khối mã hóa mỗi thông điệp thành một mã tự, còn được gọi là một khối trong mã hóa khối. Người gửi gửi tất cả các khối cho người nhận, sau đó người nhận sử dụng thuật toán phục hồi lại thông điệp ban đầu từ các khối có lỗi.

Một mã khối là một đơn ánh

 .

Ở đây,   là một tập hợp các ký tự và    là các số nguyên dương. Ý nghĩa các tham số này sẽ được mô tả dưới đây.

Bảng chữ cái ΣSửa đổi

Có thể coi dữ liệu cần được mã hóa là một xâu ký tự dùng bảng chữ cái  . Kích thước   của bảng chữ cái thường được ký hiệu là  . Nếu  , thì mã khối được gọi là mã khối nhị phân. Trong nhiều ứng dụng   thường được chọn là lũy thừa số nguyên tố, và  trường hữu hạn  .

Chiều dài thông điệp kSửa đổi

Mỗi thông điệp m là một phần tử của  , hay nói cách khác, là một xâu ký tự độ dài  . Tham số   được gọi là chiều dài thông điệp hay chiều của mã khối.

Chiều dài khối nSửa đổi

Chiều dài khối   của một mã khối là số ký tự trong một khối. Mỗi xâu   trong   là một xâu ký tự độ dài   và ứng với một khối (có lỗi) mà người nhận nhận được. Chúng được gọi là khối nhận được. Nếu   với một thông điệp   nhất định, thì   được gọi là mã tự của  .

Tỉ lệ RSửa đổi

Tỉ lệ của một mã khối được định nghĩa là tỉ lệ giữa chiều dài thông điệp và chiều dài khối:

 .

Tỉ lệ lớn nghĩa là lượng thông tin gửi đi trong mỗi khối là cao. Nói cách khác, tỉ lệ được dùng để đo tốc độ truyền và đại lượng   đo lượng dữ liệu thừa cần dùng để mã hóa. Theo lý thuyết thông tin, tỉ lệ không thể vượt quá   vì không thể nén dữ liệu trong mọi trường hợp. Một cách khác để suy ra nhận xét này là do   là một đơn ánh.

Khoảng cách dSửa đổi

Khoảng cách hay khoảng cách nhỏ nhất   của một mã khối là số ký tự khác nhau nhỏ nhất giữa hai mã tự bất kì, và khoảng cách tương đối   là tỉ lệ  . Một cách cụ thể hơn, với hai mã tự  , đặt  khoảng cách Hamming giữa   , nghĩa là số vị trí khác nhau giữa   . Định nghĩa khoảng cách nhỏ nhất   của mã  

 .

Do mọi mã đều là đơn ánh, khoảng cách nhỏ nhất luôn lớn hơn hoặc bằng  .

Khoảng cách lớn hơn cho phép phát hiện và sửa nhiều lỗi hơn. Chẳng hạn, nếu ta chỉ xét trường hợp lỗi làm thay đổi ký tự trong mã tự gửi đi nhưng không thêm hay xóa bớt ký tự thì số lỗi chính là số vị trí khác nhau giữa khối gửi đi và khối nhận được. Một mã với khoảng cách   cho phép phát hiện   lỗi vì sau khi thay đổi không quá   vị trí của một mã tự, ta không thể thu được một mã tự mới. Ngoài ra, nếu chỉ có không quá   lỗi, người nhận có thể sửa lỗi và tìm ra mã tự gửi đi. Đó là vì trong khoảng cách   từ khối tự nhận được chỉ có đúng một mã tự. Nếu có nhiều hơn   lỗi thì người nhận không thể tìm ra chính xác mã tự gửi đi. Một phương thức đối phó với trường hợp này là sử dụng giải mã danh sách, trong đó người nhận liệt kê tất cả các mã tự nằm trong một bán kính nhất định.

Ký hiệu phổ biếnSửa đổi

Mã khối dùng bảng chữ cái   kích thước  , với chiều dài khối  , chiều dài thông điệp/số chiều  , và khoảng cách   thường được ký hiệu là mã  . Nếu mã khối là mã khối tuyến tính thì thường dùng ký hiệu ngoặc vuông  . Khi   hay mã là mã nhị phân, thì không nhất thiết phải ghi rõ  .

Với mã MDS, khoảng cách luôn là  . Trong một số trường hợp khác không rõ chính xác khoảng cách của mã là bao nhiêu. Trong những trường hợp đó có thể bỏ qua thành phần  .

Đôi khi, đặc biệt là mã không phải mã khối, ký hiệu   được dùng để chỉ mã có   mã tự độ dài  . Với mã khối với số chiều   trên bảng chữ cái  , số mã tự là  .

Tham khảoSửa đổi

  • J.H. van Lint (1992). Introduction to Coding Theory. GTM. 86 (ấn bản 2). Springer-Verlag. tr. 31. ISBN 3-540-54894-7.
  • F.J. MacWilliams (1977). The Theory of Error-Correcting Codes. North-Holland. tr. 35. ISBN 0-444-85193-3. Đã bỏ qua tham số không rõ |coauthors= (gợi ý |author=) (trợ giúp)
  • W. Huffman (2003). Fundamentals of error-correcting codes. Cambridge University Press. ISBN 978-0-521-78280-7. Đã bỏ qua tham số không rõ |coauthors= (gợi ý |author=) (trợ giúp)
  • S. Lin (1983). Error Control Coding: Fundamentals and Applications. Prentice-Hall. ISBN 0-13-283796-X. Đã bỏ qua tham số không rõ |coauthors= (gợi ý |author=) (trợ giúp)

Liên kết ngoàiSửa đổi