Mã tuyến tính

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

Trong lý thuyết mã hóa, mã tuyến tínhmã sửa lỗi trong đó mọi tổ hợp tuyến tính của các mã tự cũng là một mã tự. Mã tuyến tính thường được phân loại thành mã khốimã chập, mặc dù mã Turbo có thể được coi là thuộc cả hai thể loại.[1] Mã tuyến tính thường có thuật toán mã hóa và giải mã hiệu quả hơn các loại mã khác (tham khảo giải mã hội chứng).

Mã tuyến tính được dùng trong sửa lỗi trước và được dùng để truyền các kí hiệu (chẳng hạn như bit) trên một kênh liên lạc sao cho, nếu có lỗi trong quá trình truyền, người nhận có thể phát hiện và sửa một số lỗi trong khối nhận được. Mỗi mã tự trong một mã khối tuyến tính là một khối các kí hiệu được mã hoá thành một khối lớn hơn khối ban đầu. Lượng thông tin thừa trong mỗi khối được dùng để phát hiện và sửa các lỗi trong quá trình truyền. Độ dài n của mã khối tuyến tính số kí hiệu trong một khối. Ví dụ, mã Hamming [7,4,3] là một mã nhị phân tuyến tính biểu diễn mỗi thông điệp 4 bit bằng một mã tự 7 bit. Hai mã tự khác nhau sai khác ở ít nhất 3 bit. Do đó, mã có thể phát hiện 2 lỗi sai và sửa 1 lỗi sai.[2] Mã này gồm 24=16 mã tự.

Định nghĩa và các tham số[sửa | sửa mã nguồn]

Một mã tuyến tính với độ dài n và hạng/số chiều k là một không gian con C với số chiều k của không gian vectơ \mathbb{F}_q^n trong đó \mathbb{F}_qtrường hữu hạn với q phần tử. Mã như vậy gọi là mã q-phân. Nếu q = 2 hay q = 3, thì mã đó được gọi tương ứng là mã nhị phân, và mã tam phân. Các vectơ trong C được gọi là các mã tự. Kích thước của một mã là số mã tự, và đúng bằng qk.

Trọng lượng của một mã tự là số lượng phần tử khác không của nó và khoảng cách giữa hai mã tự là khoảng cách Hamming giữa chúng, nghĩa là số phần tử khác nhau giữa hai mã tự. Khoảng cách d của một mã là trọng lượng nhỏ nhất trong các mã tự khác không, hoặc một cách tương đương, khoảng cách nhỏ nhất giữa hai mã tự khác nhau. Mã tuyến tính độ dài n, số chiều k, và khoảng cách d được kí hiệu là mã [n,k,d].

Ghi chú: Ta sử dụng cơ sở thông thường cho \mathbb{F}_q^n vì mỗi tọa độ ứng với một kí hiệu được truyền trên "kênh nhiễu". Chỉ khi sử dụng cơ sở này thì khoảng cách Hamming mới tương ứng với số lỗi sai trong quá trình truyền.

Tính chất[sửa | sửa mã nguồn]

Vì là một không gian con của \mathbb{F}_q^n, toàn bộ mã C (có kích thước lớn) có thể được biểu diễn chỉ bằng một hệ sinh gồm ít nhất mã tự (gọi là cơ sở trong đại số tuyến tính). Nếu ghép các mã tự này làm các hàng của ma trận G thì ma trận đó gọi là ma trận sinh của mã C. Khi G có dạng khối G = (I_k | A), trong đó I_k là ma trận đơn vị k \times k và A là một ma trận k \times (n-k), thì ta nói G nằm ở dạng chuẩn.

Ma trận H biểu diễn biến đổi tuyến tính \phi: \mathbb{F}_q^n\to \mathbb{F}_q^{n-k}hạt nhânC được gọi là ma trận kiểm tra của C (còn được gọi là ma trận kiểm tra tính chẵn lẻ). Nếu C là mã với ma trận sinh G ở dạng chuẩn, G = (Ik | A), thì H = (−At | In − k) là ma trận kiểm tra của C. Mã sinh bởi H được gọi là mã đối ngẫu của C.

Tính chất tuyến tính đảm bảo khoảng cách Hamming nhỏ nhất d giữa mã tự c0 và bất kì mã tự c ≠ c0 nào là độc lập với c0. Điều này được suy ra từ tính chất hiệu c − c0 của hai mã tự trong C cũng là một mã tự (nghĩa là một phần tử của không gian C), và tính chất d(c, c0) = d(c − c0, 0). Theo các tính chất này,

\min_{c \in C,\ c \neq c_0}d(c,c_0)=\min_{c \in C, c \neq c_0}d(c-c_0, 0)=\min_{c \in C, c \neq 0}d(c, 0)=d.

Nói cách khác, để xác định khoảng cách nhỏ nhất giữa các mã tự của một mã tuyến tính, chỉ cần xét khoảng cách giữa các mã tự khác không và mã tự không. Mã tự khác không có trọng lượng nhỏ nhất chính là mã tự gần mã tự không nhất và trọng số đó chính là khoảng cách nhỏ nhất.

Khoảng cách d của một mã tuyến tính C cũng bằng số nhỏ nhất các cột phụ thuộc tuyến tính của ma trận kiểm tra H.

Chứng minh: Xét c là mã tự có trọng số nhỏ nhất. Theo định nghĩa, \boldsymbol{H} \cdot \boldsymbol{c}^T = \boldsymbol{0} nên các cột \boldsymbol{H_i} với c_i\ne 0 phụ thuộc tuyến tính. Vì vậy số cột nhỏ nhất phụ thuộc tuyến tính là nhỏ hơn hoặc bằng d.

Mặt khác xét một tập hợp nhỏ nhất các cột phụ thuộc tuyến tính \{ \boldsymbol{H_j} | j \in S \} trong đó S là tập hợp các chỉ số các cột này. \sum_{i=1}^n (c_i \cdot \boldsymbol{H_i}) = \sum_{j \in S} (c_j \cdot \boldsymbol{H_j}) + \sum_{j \notin S} (c_j \cdot \boldsymbol{H_j}) =  \boldsymbol{0}. Xét vectơ \boldsymbol{c'} sao cho c_j^{'}=0 nếu j \notin S. Ta nhận thấy \boldsymbol{c'} \in C\boldsymbol{H} \cdot \boldsymbol{c'}^T = \boldsymbol{0}. Do đó ta có d \le wt(\boldsymbol{c'}) , chính là số nhỏ nhất các cột phụ thuộc tuyến tính của \boldsymbol{H}.

Như vậy, ta thu được kết quả cần chứng minh.

Ví dụ: mã Hamming[sửa | sửa mã nguồn]

Bài chi tiết: mã Hamming

Là loại mã đầu tiên được dùng cho mục đích sửa lỗi, mã Hamming được sử dụng rộng rãi trong các hệ thống truyền thông số. Với mọi số nguyên dương r \ge 2 , tồn tại một mã Hamming  [2^r-1, 2^r-r-1,3]_2. Vì d=3, mã Hamming có thể sửa lỗi 1 bit.

Ví dụ: Sau đây là ma trận sinh và ma trận sửa lỗi của mã Hamming  [7,4,3]_2.

\boldsymbol{G}=\begin{pmatrix} 1\ 1\ 0\ 1\ 0\ 0\ 0 \\ 0\ 1\ 1\ 0\ 1\ 0\ 0 \\ 1\ 1\ 1\ 0\ 0\ 1\ 0 \\ 1\ 0\ 1\ 0\ 0\ 0\ 1 \end{pmatrix} ,: \boldsymbol{H}=\begin{pmatrix} 1\ 0\ 0\ 1\ 0\ 1\ 1 \\ 0\ 1\ 0\ 1\ 1\ 1\ 0 \\ 0\ 0\ 1\ 0\ 1\ 1\ 1  \end{pmatrix}

Ví dụ: mã Hadamard[sửa | sửa mã nguồn]

Bài chi tiết: Mã Hadamard

Mã Hadamard là một mã tuyến tính [2^r, r, 2^{r-1}]_2 có thể sửa nhiều lỗi. Có thể xây dựng ma trận sinh của mã Hadamard lần lượt từng cột một: cột thứ i là các bit của biểu diễn nhị phân của số nguyên i, như trong ví dụ dưới đây. Mã Hadamard có khoảng cách nhỏ nhất 2^{r-1} và do đó có thể sửa 2^{r-2}-1 lỗi.

Ví dụ: Say đâu là ma trận sinh của mã Hadamard  [8,3,4]_2: \boldsymbol{G}_{Had}=\begin{pmatrix} 0\ 0\ 0\ 0\ 1\ 1\ 1\ 1\\ 0\ 0\ 1\ 1\ 0\ 0\ 1\ 1\\ 0\ 1\ 0\ 1\ 0\ 1\ 0\  1\end{pmatrix}.

Mã Hadamard là một trường hợp đặc biệt của mã Reed–Muller. Nếu ta loại bỏ cột thứ nhất (cột toàn 0) của \boldsymbol{G}_{Had}, thì thu được mã đơn hình [7,3,4]_2, chính là mã đối ngẫu của mã Hamming.

Kí hiệu phổ biến[sửa | sửa mã nguồn]

thường được kí hiệu bởi chữ cái C. Mã có chiều dài n và số chiều k (nghĩa là có k mã tự trong cơ sở và ma trận sinhk hàng) thường được gọi là mã (nk). Mã tuyến tính thường được kí hiệu là [nkd], trong đó d là khoảng cách Hamming nhỏ nhất giữa hai mã tự.

Ghi chú. Kí hiệu [nkd] là khác với kí hiệu (nMd) thường được dùng để kí hiệu mã không tuyến tính chiều dài n, kích thước M (nghĩa là có M mã tự), và khoảng cách Hamming nhỏ nhất d.

Ví dụ[sửa | sửa mã nguồn]

Một vài ví dụ của mã tuyến tính bao gồm:

Xem thêm[sửa | sửa mã nguồn]

Ghi chú[sửa | sửa mã nguồn]

  1. ^ William E. Ryan and Shu Lin (2009). Channel Codes: Classical and Modern. Cambridge University Press. tr. 4. ISBN 978-0-521-84868-8. 
  2. ^ Thomas M. Cover and Joy A. Thomas (1991). Elements of Information Theory. John Wiley & Sons, Inc. tr. 210–211. ISBN 0-471-06259-5 Kiểm tra giá trị |isbn= (trợ giúp). 

Liên kết ngoài[sửa | sửa mã nguồn]