Mã tuyến tính

Trong lý thuyết mã hóa, mã tuyến tính là mã 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ối và mã 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 2⁴=16 mã tự.

Định nghĩa và các tham số

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} _{q}$ là trườ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 q^k.

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

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}$ có hạt nhân là C đượ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 = (I_k | A), thì H = (−A^t | I_n − 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ự c₀ và bất kì mã tự c ≠ c₀ nào là độc lập với c₀. Điều này được suy ra từ tính chất hiệu c − c₀ 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, c₀) = d(c − c₀, 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}\neq 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$ vì ${\boldsymbol {H}}\cdot {\boldsymbol {c'}}^{T}={\boldsymbol {0}}$ . Do đó ta có $d\leq 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

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\geq 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

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ụ: Sau đây 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

Mã 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 sinh có k hàng) thường được gọi là mã (n, k). Mã tuyến tính thường được ký hiệu là [n, k, d], trong đó d là khoảng cách Hamming nhỏ nhất giữa hai mã tự.

Ghi chú. Ký hiệu [n, k, d] là khác với ký hiệu (n, M, d) 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ụ

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

Mã lặp
Mã chẵn lẻ
Mã vòng
Mã Hamming
Mã Golay, bao gồm cả mã Golay nhị phân và mã Golay tam phân
Mã đa thức, trong đó mã BCH là một ví dụ
Mã Reed–Solomon
Mã Reed–Muller
Mã Goppa
Mã kiểm tra chẵn lẻ mật độ thấp
Mã đồ thị giãn nở
Mã kiểm tra chẵn lẻ nhiều chiều

Xem thêm

Phương pháp giải mã

Ghi chú

^ William E. Ryan and Shu Lin (2009). Channel Codes: Classical and Modern. Cambridge University Press. tr. 4. ISBN 978-0-521-84868-8.
^ 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=: giá trị tổng kiểm (trợ giúp).

Liên kết ngoài

Chương trình sinh mã q-phân Lưu trữ 2007-09-27 tại Wayback Machine
Tính các tham số của mã tuyến tính – một giao diện trực tuyến để sinh và tính các tham số (chẳng hạn khoảng cách nhỏ nhất) của mã sửa lỗi tuyến tính.
Bảng mã: Chặn của các tham số của các loại mã khác nhau, IAKS, Fakultät für Informatik, Universität Karlsruhe (TH)]. Bảng trực tuyến được cập nhật các tham số tối ưu cho nhiều loại mã.

[1] William E. Ryan and Shu Lin (2009). Channel Codes: Classical and Modern. Cambridge University Press. tr. 4. ISBN 978-0-521-84868-8.

[Cover_and_Thomas-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=: giá trị tổng kiểm (trợ giúp).

[1]

[2]