2.2. Bài toán decode tổng quát

Khi vector \(\bm{x}\) được truyền qua kênh truyền, không gì đảm bảo chúng ta sẽ nhận được chính xác \(\bm{x}\) ở bên nhận, mà có thể là \(\bm{y}\) nào đó.

Các codeword nằm trong một block code nào đó là tập con của \(V_n(q)\), trong khi ở bên nhận có thể là một vector bất kỳ trong \(V_n(q)\). Bài toán decode đặt ra câu hỏi, làm sao biết được vector \(\bm{y}\) sẽ được decode thành vector nào trong block code.

Định nghĩa 2.45 (Bài toán decode)

Bài toán decode của \((n)_q\) code \(\mathcal{C}\) là bài toán cho trước vector \(\bm{y} \in V_n(q)\), ta tìm codeword \(\bm{c} \in \mathcal{C}\) của code \((n)_q\) sao cho \(\rho_H (\bm{c}, \bm{y}) = \min\limits_{\bm{c}' \in \mathcal{C}} \rho_H (\bm{c}', \bm{y})\) với \(\rho_H\) là khoảng cách Hamming.

Input:

  • vector \(\bm{y} \in V_n(q)\) nhận được từ kênh truyền;

  • \(\mathcal{C}\) là \((n)_q\) code.

Output:

  • vector \(\bm{c} \in \mathcal{C}\) là codeword sao cho \(\displaystyle{\rho_H (\bm{c}, \bm{y}) = \min_{\bm{c}' \in \mathcal{C}} \rho_H(\bm{c}', \bm{y})}\).

Định nghĩa 2.46 (Bài toán decode)

Bài toán decode của \((n)_q\) code \(\mathcal{C}\) là bài toán cho trước vector \(\bm{y} \in V_n(q)\), ta tìm codeword \(\bm{c} \in \mathcal{C}\) của code \((n)_q\) sao cho \(\mathrm{wt}(\bm{y} - \bm{c}) = \min\limits_{\bm{c}' \in \mathcal{C}} \mathrm{wt}(\bm{y} - \bm{c}')\) với \(\mathrm{wt}\) là trọng số Hamming.

Input:

  • vector \(\bm{y} \in V_n(q)\) là vector nhận được từ kênh truyền;

  • \(\mathcal{C}\) là \((n)_q\) code.

Output:

  • vector \(\bm{c} \in \mathcal{C}\) là codeword sao cho \(\mathrm{wt}(\bm{y} - \bm{c}) = \min\limits_{\bm{c}' \in \mathcal{C}} \mathrm{wt} (\bm{y} - \bm{c}')\).

Định nghĩa 2.47 (Bài toán decode)

Bài toán decode của \((n)_q\) code \(\mathcal{C}\) 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{y} - \bm{e} \in \mathcal{C}\), nghĩa là \(\bm{y} - \bm{e}\) là codeword, và vector \(\bm{e}\) có trọng số Hamming nhỏ nhất \(\mathrm{wt}(\bm{e}) \to \min\).

Input:

  • vector \(\bm{y} \in V_n(q)\) là vector nhận được từ kênh truyền;

  • \(\mathcal{C}\) là \((n)_q\) code.

Output:

  • vector \(\bm{e} \in V_n(q)\) sao cho \(\bm{y} - \bm{e} \in \mathcal{C}\), nghĩa là \(\bm{y} - \bm{e}\) là codeword;

  • và vector \(\bm{e}\) có trọng số Hamming nhỏ nhất \(\mathrm{wt}(\bm{e}) \to \min\).

Nhận xét 2.20

Các định nghĩa về bài toán decode ở trên tương đương nhau.

Định nghĩa 2.48 (Decoder)

Decoder của code \((n)_q\) \(\mathcal{C}\) là thuật toán mà với vector \(\bm{y} \in V_n(q)\) cho trước, tìm được codeword \(\bm{c} \in \mathcal{C}\) sao cho vector \(\bm{e} = \bm{y} - \bm{c}\) có trọng số Hamming nhỏ nhất có thể, nghĩa là \(\bm{c} = \underset{\bm{u} \in \mathcal{C}}{\operatorname{argmin}} \mathrm{wt}(\bm{y} - \bm{u})\).

Decoder của code \(\mathcal{C}\) sẽ giải bài toán decode trên code \(\mathcal{C}\).