3.5. Bài toán decode trên linear code

Định nghĩa 3.34 (Decode với ma trận sinh)

Bài toán decode trên linear code \([n, k]_q\) với ma trận sinh \(\bm{G}\) trong điều kiện kênh truyền có \(t\) lỗi là bài toán cho trước vector \(\bm{y} \in V_n(q)\), ta tìm vector \(\bm{m} \in V_k(q)\) sao cho vector \(\bm{e} = \bm{y} - \bm{m} \bm{G}\) có trọng số Hamming bằng \(t\).

Input:

  • vector \(\bm{y} \in V_n(q)\);

  • ma trận sinh \(\bm{G}\) cỡ \(k \times n\);

  • số tự nhiên \(t \in \mathbb{N}\).

Output:

  • vector \(\bm{m} \in V_k(q)\) sao cho vector \(\bm{e} = \bm{y} - \bm{m} \bm{G}\) có trọng số Hamming bằng \(t\).

Định nghĩa 3.35 (Decode với ma trận kiểm tra chẵn lẻ)

Bài toán decode trên linear code \([n, k]_q\) với ma trận parity-check \(\bm{H}\) trong điều kiện kênh truyền có \(t\) lỗi là bài toán cho trước vector \(\bm{y} \in V_n(q)\), ta tìm vector \(\bm{e} \in V_n(q)\) sao cho \(\bm{e} \bm{H}^\top = \bm{y} \bm{H}^\top\) và vector \(\bm{e}\) có trọng số Hamming bằng \(t\), hay \(\mathrm{wt}(\bm{e}) = t\).

Input:

  • vector \(\bm{y} \in V_n(q)\), ma trận parity-check \(\bm{H}\) cỡ \((n - k) \times n\) và số tự nhiên \(t \in \mathbb{N}\).

Output:

  • vector \(\bm{e} \in V_n(q)\) có trọng số Hamming bằng \(t\), hay \(\mathrm{wt}(\bm{e}) = t\), sao cho \(\bm{e} \bm{H}^\top = \bm{y} \bm{H}^\top\).

Từ các bài toán decode linear code liên hệ với bài toán decode syndrome code.

Định nghĩa 3.36 (Bài toán tối ưu syndrome decoding)

Bài toán tối ưu (hay bài toán tổng quát) của syndrome decode \([n, k]_q\) với ma trận parity-check \(\bm{H}\) là bài toán cho trước vector \(\bm{s} \in V_{n-k}(q)\), ta tìm vector \(\bm{e} \in V_n(q)\) sao cho \(\bm{H} \bm{e}^\top = \bm{s}^\top\) và vector \(\bm{e}\) có trọng số Hamming nhỏ nhất có thể, hay \(\mathrm{wt}(\bm{e}) \to \min\).

Input:

  • \(\bm{s} \in V_{n-k}(q)\) là syndrome;

  • \(\bm{H}\) là ma trận parity-check cỡ \((n - k) \times n\) của \([n, k]_q\) code \(\mathcal{C}\)

Output:

  • vector \(\bm{e} \in V_n(q)\) thỏa mãn \(\bm{H} \bm{e}^\top = \bm{s}^\top\) và vector \(\bm{e}\) có trọng số Hamming nhỏ nhất có thể, hay \(\mathrm{wt}(\bm{e}) \to \min\).

Định nghĩa 3.38 (Bài toán quyết định syndrome decoding)

Bài toán quyết định syndrome decoding, gọi ngắn gọn là bài toán syndrome decoding, \(SD(\bm{H}, \bm{s}, t)\) là bài toán xác định theo syndrome \(\bm{s} \in V_r(q)\) xem có tồn tại hay không vector \(\bm{e} \in V_n(q)\) có trọng số Hamming bằng \(t\) và thỏa mãn \(\bm{H} \bm{e}^\top = \bm{s}^\top\).

Input:

  • \(\bm{H}\) là ma trận cỡ \(r \times n\) trên \(\mathbb{F}_q\)

  • \(\bm{s} \in V_r(q)\) là syndrome;

  • \(t \in \mathbb{N}\) là trọng số Hamming.

Output: tồn tại hay không vector \(\bm{e} \in V_n(q)\) có trọng số Hamming \(\mathrm{wt}(\bm{e}) = t\) và thỏa \(\bm{H} \bm{e}^\top = \bm{s}^\top\).

Định lý 3.2 (Định lí từ [12])

Bài toán nhận dạng syndrome code \(SD(\bm{H}, \bm{s}, t)\) là NP-complete.