2.3. Linear code

Định nghĩa 2.49 (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}_2\) 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 2.50

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

Định nghĩa 2.51

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 2.52

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

Định nghĩa 2.53

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

Định nghĩa 2.54

Redundancy (hay избыточность) của \([n, k]_q\) code là số \(r = n - k\).

Định nghĩa 2.55

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 2.56

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

2.3.1. Ma trận sinh

Định nghĩa 2.57

Ma trận \(\bm{G}\) được gọi là ma trận sinh (hay порождающая матрица) của code \(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ì \(G\) là ma trận kích thước \(k \times n\).

Nhận xét 2.21

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 k\) 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\).

2.3.2. Coder

Định nghĩa 2.58

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 2.59

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 2.60

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

Định nghĩa 2.61

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_n) \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 2.62

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.

2.3.3. Ma trận kiểm tra

Định nghĩa 2.63

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 \mathcal{C}: \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 2.64

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.

Nhận xét 2.22

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\).

2.3.4. Linear code

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 2.65

Спектр весов 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.

2.3.5. Dual code (mã đối ngẫu) và kiểm tra chẵn lẻ (check-parity)

Định nghĩa 2.66 (Dual code)

Dual code (hay mã đối ngẫu, дуальный код) của linear code \(\mathcal{C}\) là code \(\mathcal{C}^\top\) được sinh bởi parity-check matrix \(\bm{H}\) của code \(\mathcal{C}\).

Nhận xét 2.23

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

Nhận xét 2.24

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

Nhận xét 2.25

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

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

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 2.67

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 2.68

Vector \(\bm{h} \in V_n(q)\) được gọi là parity-check (hay проверка на чётность) 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}\).

Nhận xét 2.26

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