Mã tuyến tính ============= .. prf:definition:: Linear code :label: def-lincode Block code :math:`(n)_q` :math:`\mathcal{C}` được gọi là **tuyến tính** (hay **linear**) nếu với mọi :math:`a, b \in \mathbb{F}_q` và với mọi codeword :math:`\bm{x}, \bm{y} \in \mathcal{C}` thì vector :math:`a \cdot \bm{x} + b \cdot \bm{y}` cũng là codeword thuộc :math:`\mathcal{C}`. Ta kí hiệu linear code (mã tuyến tính) là :math:`[n]_q`. Có thể thấy block code :math:`[n]_q` là không gian vector con của :math:`V_n(q)`. .. prf:definition:: Độ dài mã tuyến tính :label: def-len-lincode Đối với code :math:`[n]_q` thì số :math:`n` được gọi là **độ dài** của code. .. prf:definition:: Số chiều mã tuyến tính :label: def-dim-lincode **Số chiều** của code :math:`[n]_q` là số :math:`k` bằng với số chiều của không gian vector con :math:`\mathcal{C}` của :math:`V_n(q)`. .. prf:definition:: Mã :math:`[n,k]_q` :label: def-nk-code Linear code :math:`\mathcal{C}` có độ dài :math:`n` và số chiều :math:`k` được gọi là :math:`[n, k]_q` code. .. prf:definition:: Tốc độ truyền :label: def-speed-lincode **Tốc độ truyền** của :math:`[n, k]_q` code là số :math:`R = \dfrac{k}{n}`. .. prf:definition:: Độ dư :label: def-redudancy-lincode **Độ dư** (hay **redundancy**) của :math:`[n, k]_q` code là số :math:`r = n - k`. .. prf:definition:: Khoảng cách tối thiểu :label: def-min-dist-lincode **Khoảng cách nhỏ nhất** của code :math:`\mathcal{C}` là số :math:`d` bằng với trọng số Hamming nhỏ nhất của các codeword trong :math:`\mathcal{C}` .. math:: d = \min_{\bm{u} \in \mathcal{C}, \bm{u} \neq \bm{0}} \mathrm{wt}(\bm{u}). .. prf:definition:: Mã :math:`[n,k,d]_q` :label: def-nkd-code Linear code :math:`[n, k]_q` với khoảng cách nhỏ nhất :math:`d` được gọi là :math:`[n, k, d]_q` code. Ma trận sinh ------------- .. prf:definition:: Ma trận sinh :label: def-genmat-lincode Ma trận :math:`\bm{G}` được gọi là **ma trận sinh** của code :math:`\mathcal{C}` nếu nó chứa các vector trong cơ sở của không gian vector con :math:`\mathcal{C}`. Nếu :math:`\mathcal{C}` là :math:`[n, k]_q` code thì :math:`\bm{G}` là ma trận kích thước :math:`k \times n`. .. prf:remark:: Các ma trận sinh tương đương :label: rmk-genmat-lincode Nếu :math:`G` là ma trận sinh của :math:`[n, k]_q` code thì .. math:: \mathcal{C} = \{ \bm{a} \cdot \bm{G} : \bm{a} \in V_k(q) \}. Ở đây ta nói ma trận :math:`\bm{G}` sinh ra code :math:`\mathcal{C}`. Theo kiến thức đại số tuyến tính, nếu :math:`\bm{G}_1` và :math:`\bm{G}_2` kích thước :math:`k \times n` cùng sinh ra một code :math:`\mathcal{C}` thì tồn tại ma trận khả nghịch :math:`\bm{A}` kích thước :math:`k \times k` trên :math:`\mathbb{F}_q` sao cho :math:`\bm{A} \bm{G}_1 = \bm{G}_2`. Coder ------ .. prf:definition:: Bộ mã hóa :label: def-coder **Coder** :math:`\varphi: V_k(q) \to V_n(q)` cho :math:`[n, k]_q` code xác định bởi ma trận sinh :math:`\bm{G}` theo nghĩa: .. math:: \varphi((a_1, \ldots, a_k)) = (a_1, \ldots, a_k) \cdot \bm{G}. .. prf:definition:: Ma trận sinh dạng hệ thống :label: def-systematic-mat Ma trận :math:`\bm{G}` kích thước :math:`k \times n` được gọi là **systematic** nếu nó có dạng: .. math:: \bm{G} = (\bm{I}_k \Vert \bm{G}_0), với :math:`\bm{I}_k` là ma trận đơn vị :math:`k \times k` và :math:`\bm{G}_0` là ma trận cỡ :math:`k \times (n - k)` nào đó. .. prf:definition:: Mã dạng hệ thống :label: def-systematic-code Code được gọi là **systematic** nếu nó có ma trận sinh :math:`\bm{G}` là systematic. .. prf:definition:: Bộ mã hóa dạng hệ thống :label: def-systematic-lincode Coder :math:`\varphi_{\bm{G}}` của systematic code :math:`[n, k]_q`, xác định bởi ma trận sinh systematic :math:`\bm{G} = (\bm{I}_k \Vert \bm{G}_0)`, được gọi là **systematic**. Khi đó với mọi thông điệp :math:`\bm{a} = (a_1, \ldots, a_k) \in V_k(q)` thì coder thực hiện: .. math:: \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. .. prf:definition:: Tập thông tin :label: def-info-set Ta đánh số tọa độ các codeword trong :math:`[n, k]_q` code từ :math:`1` tới :math:`n`. **Tập thông tin** (hay **information set**) :math:`\mathcal{I}` của code :math:`[n, k]_q` là tập con của tập đánh số tọa độ, nghĩa là :math:`\mathcal{I} \subseteq \{ 1, \ldots, n \}`, sao cho :math:`\lvert \mathcal{I} \rvert = k` và ma trận con :math:`\bm{G}_k` kích thước :math:`k \times k` của ma trận sinh :math:`\bm{G}` khả nghịch. Ma trận kiểm tra ----------------- .. prf:definition:: Ma trận kiểm tra chẵn lẻ :label: def-parity-mat Nếu :math:`\mathcal{C}` là hạt nhân của ma trận :math:`\bm{H}`, tức là .. math:: \mathcal{C} = \ker(\bm{H}) = \{ \bm{v} \in V_n(q): \bm{H} \bm{v}^\top = \bm{0} \}, thì ta nói :math:`\bm{H}` là **ma trận kiểm tra chẵn lẻ** (hay **parity-check matrix**). Ta có thể thấy :math:`\bm{G} \bm{H}^\top = \bm{0}`. .. prf:definition:: Syndrome :label: def-syndrom **Syndrome** :math:`S_{\bm{H}}(\bm{y})` của vector :math:`\bm{y} \in V_n(q)` tương ứng với ma trận parity-check :math:`\bm{H}` của :math:`[n, k]_q` code :math:`\mathcal{C}` là vector cột :math:`S_{\bm{H}}(\bm{y}) = \bm{H} \cdot \bm{y}^\top`. Khi đó :math:`S_{\bm{H}}(\bm{y})` có độ dài :math:`r = n - k` -- chính là redundancy ở trên. .. prf:remark:: Các ma trận kiểm tra chẵn lẻ tương đương :label: rmk-parity-mat Nếu :math:`\bm{H}_1` và :math:`\bm{H}_2` là hai ma trận parity-check của code :math:`\mathcal{C}` thì :math:`S_{\bm{H}_1}(\bm{y}) = \bm{A} \cdot S_{\bm{H}_2}(\bm{y})` với :math:`\bm{A}` là ma trận khả nghịch thỏa mãn :math:`\bm{H}_2 = \bm{A} \cdot \bm{H}_1`. Phổ trọng số của mã tuyến tính ------------------------------ Do :math:`[n]_q` code cũng là :math:`(n)_q` code nên ta cũng có định nghĩa phổ trọng số như :math:`(n)_q`: .. prf:definition:: Phổ trọng số của mã tuyến tính :label: def-spec-lincode **Phổ trọng số** của :math:`[n]_q` code :math:`\mathcal{C}` là vector :math:`(A_0, A_1, \ldots, A_n) \in \mathbb{Z}^{n+1}_{\geqslant 0}` với :math:`A_i \geqslant 0` là số lượng vector có trọng số bằng :math:`i` trong code. Mã đối ngẫu và kiểm tra chẵn lẻ ------------------------------- .. prf:definition:: Dual code :label: def-dual-code **Dual code** (hay **mã đối ngẫu**) của linear code :math:`\mathcal{C}` là code :math:`\mathcal{C}^\perp` được sinh bởi parity-check matrix :math:`\bm{H}` của code :math:`\mathcal{C}`. .. prf:remark:: Số chiều của mã đối ngẫu :label: rmk-dual-code Dual code với :math:`[n, k]_q` code là :math:`[n, n-k]_q` code. .. prf:remark:: Đối ngẫu hai lần :label: rmk-code-T Với mọi code :math:`\mathcal{C}` ta có :math:`(\mathcal{C}^\perp)^\perp = \mathcal{C}`. .. prf:remark:: Đối ngẫu của tổng hai mã :label: rmk-sum-code Với mọi :math:`[n]_q` code :math:`\mathcal{C}` và :math:`\mathcal{B}` thì ta có đẳng thức: .. math:: (\mathcal{C} + \mathcal{B})^\perp = \mathcal{C}^\perp \cap \mathcal{B}^\perp. Trong đó :math:`\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 :math:`\mathcal{C}` và :math:`\mathcal{B}`. .. prf:definition:: Tích vô hướng :label: def-inner-prod-code Với các vector :math:`\bm{x} = (x_1, \ldots, x_n)` và :math:`\bm{y} = (y_1, \ldots, y_n)` trong :math:`V_n(q)` ta định nghĩa **tích vô hướng** (hay **inner product**, **dot product**) của hai vector là: .. math:: \langle \bm{x}, \bm{y} \rangle = x_1 y_1 + \ldots + x_n y_n \in \mathbb{F}_q. .. prf:definition:: Vector kiểm tra chẵn lẻ :label: def-parity-vec Vector :math:`\bm{h} \in V_n(q)` được gọi là **parity-check** của :math:`[n]_q` code nếu với mọi :math:`\bm{c} \in \mathcal{C}` ta có :math:`\langle \bm{c}, \bm{h} \rangle = 0`, nói cách khác vector :math:`\bm{h}` trực giao với mọi vector :math:`\bm{c} \in \mathcal{C}`. .. prf:remark:: Mối liên hệ với mã đối ngẫu :label: rmk-parity-matvec Dual code :math:`\mathcal{C}^\perp` trùng với tập tất cả parity-check vector của code :math:`\mathcal{C}`.