3.1. Nhập môn mật mã dựa trên mã sửa sai

Định nghĩa 3.1 (Block code)

Block code \((n)_q\) là tập hợp \(\mathcal{C}\) bất kì chứa các vector độ dài \(n\) trên trường \(\mathbb{F}_q\).

Định nghĩa 3.2 (Codeword)

Codeword (hay từ mã) là bất kì vector nào trong block code \(\mathcal{C}\).

Định nghĩa 3.3 (Lực lượng của code)

Lực lượng (hay cardinality) \(M\) của block code \(\mathcal{C}\) là số lượng codeword trong \(\mathcal{C}\).

Kí hiệu \(M = \lvert C \rvert\).

Định nghĩa 3.4 (Mã \((n,M)_q\))

Block code \(\mathcal{C}\) trên trường \(\mathbb{F}_q\) có độ dài \(n\) và có lực lượng \(M\) được gọi là \((n, M)_q\) code.

Định nghĩa 3.5 (Độ dài của code)

Độ dài của \((n)_q\) code \(\mathcal{C}\) là số \(n\) chỉ độ dài mỗi codeword (độ dài mỗi vector).

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

Khoảng cách tối thiểu (hay minimum distance) của code \(\mathcal{C}\) là số \(d\) chỉ khoảng cách Hamming nhỏ nhất giữa hai codeword trong code \(\mathcal{C}\):

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

Nhắc lại, trọng số Hamming của một vector là số phần tử khác \(0\) trong vector đó:

\[\mathrm{wt}(x_1, x_2, \ldots, x_n) = \lvert \{ x_i : x_i \neq 0 \} \rvert.\]

Định nghĩa 3.7 (Mã \((n,M,d)_q\))

Block code \(\mathcal{C}\) trên trường \(\mathbb{F}_q\) với độ dài \(n\), lực lượng \(M\) và có khoảng cách tối thiểu \(d\) được gọi là \((n, M, d)_q\) code.

Thông tin ban đầu có thể được chia thành các đoạn độ dài \(k\) và mỗi đoạn như vậy được encode thành một đoạn độ dài \(n\).

Cụ thể hơn, hàm encode biến đổi một thông điệp là vector \(\bm{a}\) độ dài \(k\) thành codeword \(\bm{c} \in \mathcal{C}\) với độ dài \(n\):

\[\varphi: V_k(q) \to \mathcal{C}, \quad \varphi(\bm{a}) = \bm{c}.\]

Ánh xạ \(\varphi\) cần là đơn ánh (one-to-one) vì chúng ta không muốn hai thông điệp độ dài \(k\) cùng encode ra một codeword độ dài \(n\) (khi decode chúng ta không biết sẽ ra thông điệp nào).

Bổ đề 3.1 (Điều kiện tồn tại ánh xạ mã hóa)

Để \((n, M)_q\) code có thể encode được các thông điệp độ dài \(k\) thì điều kiện cần và đủ để tồn tại ánh xạ \(\varphi\) như trên là \(k \leqslant \lfloor \log_q M \rfloor\).

Định nghĩa 3.8 (Phổ trọng số)

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