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ố[sửa | sửa mã nguồn]

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

C:\Sigma ^{k}\to \Sigma ^{n}

.

Ở đây, $\Sigma$ là một tập hợp các ký tự và $k$ và $n$ 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 | sửa mã nguồn]

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 $\Sigma$ . Kích thước $|\Sigma |$ của bảng chữ cái thường được ký hiệu là $q$ . Nếu $q=2$ , thì mã khối được gọi là mã khối nhị phân. Trong nhiều ứng dụng $q$ thường được chọn là lũy thừa số nguyên tố, và $\Sigma$ là trường hữu hạn $\mathbb {F} _{q}$ .

Chiều dài thông điệp k[sửa | sửa mã nguồn]

Mỗi thông điệp m là một phần tử của $\Sigma ^{k}$ , hay nói cách khác, là một xâu ký tự độ dài $k$ . Tham số $k$ đượ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[sửa | sửa mã nguồn]

Chiều dài khối $n$ của một mã khối là số ký tự trong một khối. Mỗi xâu $c$ trong $\Sigma ^{n}$ là một xâu ký tự độ dài $n$ 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 $c=C(m)$ với một thông điệp $m$ nhất định, thì $c$ được gọi là mã tự của $m$ .

Tỉ lệ R[sửa | sửa mã nguồn]

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:

R=k/n

.

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 $1-R$ đ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á $1$ 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 $C$ là một đơn ánh.

Khoảng cách d[sửa | sửa mã nguồn]

Khoảng cách hay khoảng cách nhỏ nhất $d$ 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 $\delta$ là tỉ lệ $d/n$ . Một cách cụ thể hơn, với hai mã tự $c_{1},c_{2}\in \Sigma ^{n}$ , đặt $\Delta (c_{1},c_{2})$ là khoảng cách Hamming giữa $c_{1}$ và $c_{2}$ , nghĩa là số vị trí khác nhau giữa $c_{1}$ và $c_{2}$ . Định nghĩa khoảng cách nhỏ nhất $d$ của mã $C$ là

d:=\min _{m_{1},m_{2}\in \Sigma ^{k};m_{1}\neq m_{2}}\Delta (C(m_{1}),C(m_{2}))

.

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 $1$ .

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 $d$ cho phép phát hiện $d-1$ lỗi vì sau khi thay đổi không quá $d-1$ 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á $(d-1)/2$ 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 $(d-1)/2$ từ khối tự nhận được chỉ có đúng một mã tự. Nếu có nhiều hơn $(d-1)/2$ 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[sửa | sửa mã nguồn]

Mã khối dùng bảng chữ cái $\Sigma$ kích thước $q$ , với chiều dài khối $n$ , chiều dài thông điệp/số chiều $k$ , và khoảng cách $d$ thường được ký hiệu là mã $(n,k,d)_{q}$ . 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 $[n,k,d]_{q}$ . Khi $q=2$ hay mã là mã nhị phân, thì không nhất thiết phải ghi rõ $q$ .

Với mã MDS, khoảng cách luôn là $d=n-k+1$ . 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 $d$ .

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