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, formula_2 là một tập hợp các ký tự và formula_3 và formula_4 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 formula_2. Kích thước formula_6 của bảng chữ cái thường được ký hiệu là formula_7. Nếu formula_8, thì mã khối được gọi là mã khối "nhị phân". Trong nhiều ứng dụng formula_7 thường được chọn là lũy thừa số nguyên tố, và formula_2 là trường hữu hạn formula_11.
Chiều dài thông điệp k.
Mỗi thông điệp "m" là một phần tử của formula_12, hay nói cách khác, là một xâu ký tự độ dài formula_3.
Tham số formula_3 đượ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 formula_4 của một mã khối là số ký tự trong một khối. Mỗi xâu formula_16 trong formula_17 là một xâu ký tự độ dài formula_4 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 formula_19 với một thông điệp formula_20 nhất định, thì formula_16 được gọi là mã tự của formula_20.
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 formula_24 đ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á formula_25 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 formula_26 là một đơn ánh.
Khoảng cách d.
Khoảng cách hay khoảng cách nhỏ nhất formula_27 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 formula_28 là tỉ lệ formula_29.
Một cách cụ thể hơn, với hai mã tự formula_30, đặt formula_31 là khoảng cách Hamming giữa formula_32 và formula_33, nghĩa là số vị trí khác nhau giữa formula_32 và formula_33. Định nghĩa khoảng cách nhỏ nhất formula_27 của mã formula_26 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 formula_25.
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 formula_27 cho phép phát hiện formula_41 lỗi vì sau khi thay đổi không quá formula_41 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á formula_43 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 formula_43 từ khối tự nhận được chỉ có đúng một mã tự. Nếu có nhiều hơn formula_43 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 formula_2 kích thước formula_7, với chiều dài khối formula_4, chiều dài thông điệp/số chiều formula_3, và khoảng cách formula_27 thường được ký hiệu là mã formula_51.
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 formula_52.
Khi formula_8 hay mã là mã nhị phân, thì không nhất thiết phải ghi rõ formula_7.
Với mã MDS, khoảng cách luôn là formula_55. 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 formula_27.
Đôi khi, đặc biệt là mã không phải mã khối, ký hiệu formula_57 được dùng để chỉ mã có formula_58 mã tự độ dài formula_4. Với mã khối với số chiều formula_3 trên bảng chữ cái formula_7, số mã tự là formula_62.