Mã khối

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ố 

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ạc có nhiễ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à  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 Σ 
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à  là trường hữu hạn .

Chiều dài thông điệp k 
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 n 
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ệ R 
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 d 
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  là khoảng cách Hamming giữa  và , nghĩa là số vị trí khác nhau giữa  và . Định nghĩa khoảng cách nhỏ nhất  của mã  là
.
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ến 
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ảo

Liên kết ngoài 
 Coding Concepts and Block Coding  

Lý thuyết mã hóa