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

Định nghĩa 2.70

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 2.71

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 2.72

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(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(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 2.74

Bài toán nhận dạng syndrome decode (hay распознавательная задача синдромного декодирования) hay đơn giản là bài toán syndrome decode (hay задача синдромного декодирования) \(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í 2.8 (Định lí từ [35])

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