3.3. Mã tuyến tính

Định nghĩa 3.13 (Linear code)

Block code \((n)_q\) \(\mathcal{C}\) được gọi là tuyến tính (hay linear) nếu với mọi \(a, b \in \mathbb{F}_q\) và với mọi codeword \(\bm{x}, \bm{y} \in \mathcal{C}\) thì vector \(a \cdot \bm{x} + b \cdot \bm{y}\) cũng là codeword thuộc \(\mathcal{C}\).

Ta kí hiệu linear code (mã tuyến tính) là \([n]_q\). Có thể thấy block code \([n]_q\) là không gian vector con của \(V_n(q)\).

Định nghĩa 3.14 (Độ dài mã tuyến tính)

Đối với code \([n]_q\) thì số \(n\) được gọi là độ dài của code.

Định nghĩa 3.15 (Số chiều mã tuyến tính)

Số chiều của code \([n]_q\) là số \(k\) bằng với số chiều của không gian vector con \(\mathcal{C}\) của \(V_n(q)\).

Định nghĩa 3.16 (Mã \([n,k]_q\))

Linear code \(\mathcal{C}\) có độ dài \(n\) và số chiều \(k\) được gọi là \([n, k]_q\) code.

Định nghĩa 3.17 (Tốc độ truyền)

Tốc độ truyền của \([n, k]_q\) code là số \(R = \dfrac{k}{n}\).

Định nghĩa 3.18 (Độ dư)

Độ dư (hay redundancy) của \([n, k]_q\) code là số \(r = n - k\).

Định nghĩa 3.19 (Khoảng cách tối thiểu)

Khoảng cách nhỏ nhất của code \(\mathcal{C}\) là số \(d\) bằng với trọng số Hamming nhỏ nhất của các codeword trong \(\mathcal{C}\)

\[d = \min_{\bm{u} \in \mathcal{C}, \bm{u} \neq \bm{0}} \mathrm{wt}(\bm{u}).\]

Định nghĩa 3.20 (Mã \([n,k,d]_q\))

Linear code \([n, k]_q\) với khoảng cách nhỏ nhất \(d\) được gọi là \([n, k, d]_q\) code.

3.3.1. Ma trận sinh

Định nghĩa 3.21 (Ma trận sinh)

Ma trận \(\bm{G}\) được gọi là ma trận sinh của code \(\mathcal{C}\) nếu nó chứa các vector trong cơ sở của không gian vector con \(\mathcal{C}\).

Nếu \(\mathcal{C}\) là \([n, k]_q\) code thì \(\bm{G}\) là ma trận kích thước \(k \times n\).

Chú ý 3.2 (Các ma trận sinh tương đương)

Nếu \(G\) là ma trận sinh của \([n, k]_q\) code thì

\[\mathcal{C} = \{ \bm{a} \cdot \bm{G} : \bm{a} \in V_k(q) \}.\]

Ở đây ta nói ma trận \(\bm{G}\) sinh ra code \(\mathcal{C}\).

Theo kiến thức đại số tuyến tính, nếu \(\bm{G}_1\) và \(\bm{G}_2\) kích thước \(k \times n\) cùng sinh ra một code \(\mathcal{C}\) thì tồn tại ma trận khả nghịch \(\bm{A}\) kích thước \(k \times k\) trên \(\mathbb{F}_q\) sao cho \(\bm{A} \bm{G}_1 = \bm{G}_2\).

3.3.2. Coder

Định nghĩa 3.22 (Bộ mã hóa)

Coder \(\varphi: V_k(q) \to V_n(q)\) cho \([n, k]_q\) code xác định bởi ma trận sinh \(\bm{G}\) theo nghĩa:

\[\varphi((a_1, \ldots, a_k)) = (a_1, \ldots, a_k) \cdot \bm{G}.\]

Định nghĩa 3.23 (Ma trận sinh dạng hệ thống)

Ma trận \(\bm{G}\) kích thước \(k \times n\) được gọi là systematic nếu nó có dạng:

\[\bm{G} = (\bm{I}_k \Vert \bm{G}_0),\]

với \(\bm{I}_k\) là ma trận đơn vị \(k \times k\) và \(\bm{G}_0\) là ma trận cỡ \(k \times (n - k)\) nào đó.

Định nghĩa 3.24 (Mã dạng hệ thống)

Code được gọi là systematic nếu nó có ma trận sinh \(\bm{G}\) là systematic.

Định nghĩa 3.25 (Bộ mã hóa dạng hệ thống)

Coder \(\varphi_{\bm{G}}\) của systematic code \([n, k]_q\), xác định bởi ma trận sinh systematic \(\bm{G} = (\bm{I}_k \Vert \bm{G}_0)\), được gọi là systematic.

Khi đó với mọi thông điệp \(\bm{a} = (a_1, \ldots, a_k) \in V_k(q)\) thì coder thực hiện:

\[\bm{a} = (a_1, \ldots, a_k) \xrightarrow{\varphi} (a_1, \ldots, a_k, \bm{a} \cdot \bm{G}_0).\]

Lưu ý rằng không phải code nào cũng là systematic và do đó không chắc chắn tồn tại systematic coder.

Định nghĩa 3.26 (Tập thông tin)

Ta đánh số tọa độ các codeword trong \([n, k]_q\) code từ \(1\) tới \(n\).

Tập thông tin (hay information set) \(\mathcal{I}\) của code \([n, k]_q\) là tập con của tập đánh số tọa độ, nghĩa là \(\mathcal{I} \subseteq \{ 1, \ldots, n \}\), sao cho \(\lvert \mathcal{I} \rvert = k\) và ma trận con \(\bm{G}_k\) kích thước \(k \times k\) của ma trận sinh \(\bm{G}\) khả nghịch.

3.3.3. Ma trận kiểm tra

Định nghĩa 3.27 (Ma trận kiểm tra chẵn lẻ)

Nếu \(\mathcal{C}\) là hạt nhân của ma trận \(\bm{H}\), tức là

\[\mathcal{C} = \ker(\bm{H}) = \{ \bm{v} \in V_n(q): \bm{H} \bm{v}^\top = \bm{0} \},\]

thì ta nói \(\bm{H}\) là ma trận kiểm tra chẵn lẻ (hay parity-check matrix).

Ta có thể thấy \(\bm{G} \bm{H}^\top = \bm{0}\).

Định nghĩa 3.28 (Syndrome)

Syndrome \(S_{\bm{H}}(\bm{y})\) của vector \(\bm{y} \in V_n(q)\) tương ứng với ma trận parity-check \(\bm{H}\) của \([n, k]_q\) code \(\mathcal{C}\) là vector cột \(S_{\bm{H}}(\bm{y}) = \bm{H} \cdot \bm{y}^\top\).

Khi đó \(S_{\bm{H}}(\bm{y})\) có độ dài \(r = n - k\) -- chính là redundancy ở trên.

Chú ý 3.3 (Các ma trận kiểm tra chẵn lẻ tương đương)

Nếu \(\bm{H}_1\) và \(\bm{H}_2\) là hai ma trận parity-check của code \(\mathcal{C}\) thì \(S_{\bm{H}_1}(\bm{y}) = \bm{A} \cdot S_{\bm{H}_2}(\bm{y})\) với \(\bm{A}\) là ma trận khả nghịch thỏa mãn \(\bm{H}_2 = \bm{A} \cdot \bm{H}_1\).

3.3.4. Phổ trọng số của mã tuyến tính

Do \([n]_q\) code cũng là \((n)_q\) code nên ta cũng có định nghĩa phổ trọng số như \((n)_q\):

Định nghĩa 3.29 (Phổ trọng số của mã tuyến tính)

Phổ trọng số của \([n]_q\) code \(\mathcal{C}\) là vector \((A_0, A_1, \ldots, A_n) \in \mathbb{Z}^{n+1}_{\geqslant 0}\) với \(A_i \geqslant 0\) là số lượng vector có trọng số bằng \(i\) trong code.

3.3.5. Mã đối ngẫu và kiểm tra chẵn lẻ

Định nghĩa 3.30 (Dual code)

Dual code (hay mã đối ngẫu) của linear code \(\mathcal{C}\) là code \(\mathcal{C}^\perp\) được sinh bởi parity-check matrix \(\bm{H}\) của code \(\mathcal{C}\).

Chú ý 3.4 (Số chiều của mã đối ngẫu)

Dual code với \([n, k]_q\) code là \([n, n-k]_q\) code.

Chú ý 3.5 (Đối ngẫu hai lần)

Với mọi code \(\mathcal{C}\) ta có \((\mathcal{C}^\perp)^\perp = \mathcal{C}\).

Chú ý 3.6 (Đối ngẫu của tổng hai mã)

Với mọi \([n]_q\) code \(\mathcal{C}\) và \(\mathcal{B}\) thì ta có đẳng thức:

\[(\mathcal{C} + \mathcal{B})^\perp = \mathcal{C}^\perp \cap \mathcal{B}^\perp.\]

Trong đó \(\mathcal{C} + \mathcal{B} = \{ \bm{u} + \bm{v} : \bm{u} \in \mathcal{C}, \bm{v} \in \mathcal{B} \}\) là tổng của hai code \(\mathcal{C}\) và \(\mathcal{B}\).

Định nghĩa 3.31 (Tích vô hướng)

Với các vector \(\bm{x} = (x_1, \ldots, x_n)\) và \(\bm{y} = (y_1, \ldots, y_n)\) trong \(V_n(q)\) ta định nghĩa tích vô hướng (hay inner product, dot product) của hai vector là:

\[\langle \bm{x}, \bm{y} \rangle = x_1 y_1 + \ldots + x_n y_n \in \mathbb{F}_q.\]

Định nghĩa 3.32 (Vector kiểm tra chẵn lẻ)

Vector \(\bm{h} \in V_n(q)\) được gọi là parity-check của \([n]_q\) code nếu với mọi \(\bm{c} \in \mathcal{C}\) ta có \(\langle \bm{c}, \bm{h} \rangle = 0\), nói cách khác vector \(\bm{h}\) trực giao với mọi vector \(\bm{c} \in \mathcal{C}\).

Chú ý 3.7 (Mối liên hệ với mã đối ngẫu)

Dual code \(\mathcal{C}^\perp\) trùng với tập tất cả parity-check vector của code \(\mathcal{C}\).