|
=== Прямое решение (алгоритм Питерсона — Горенстейна — Цирлера, ПГЦ) ===
Пусть БЧХ -код над полем <math>GF(q)</math> длины <math>n</math> и с конструктивным расстоянием <math>d</math> задаетсязадаётся порождающим полиномом <math>g(x)</math>, который имеет среди своих корней элементы <math>\beta^{l_0},\; \beta^{l_0+1},\; \ldots,\; \beta^{l_0+d-2} ,\quad \beta \in GF(q^m), \quad \beta^n = 1, \quad l_0</math> — целое число (например, 0 или 1). Тогда каждое кодовое слово обладает тем свойством, что <math>c(\beta^{l_0-1+j}) = 0, \quad j = 1,\; 2,\; \ldots,\; d - 1</math>. Принятое слово <math>r(x)</math> можно записать как <math>r(x) = c(x) + e(x)</math>, где <math>e(x)</math> — полином ошибок. Пусть произошло <math>u \leqslant t = (d - 1)/2</math> ошибок на позициях <math>i_1,\; i_2,\; \ldots,\; i_u</math> (<math>t</math> — максимальное число исправляемых ошибок), значит <math>e(x) = e_{i_1} x^{i_1} + e_{i_2} x^{i_2} + \ldots + e_{i_u} x^{i_u}</math>, а <math>e_{i_1},\; e_{i_2},\; \ldots,\; e_{i_u}</math> — величины ошибок.
Можно составить <math>j</math>-й ''синдром'' <math>S_j</math> принятого слова <math>r(x)</math>:
: <math>S_j = r(\beta^{l_0-1+j}) = e(\beta^{l_0-1+j}), \quad j = 1, \ldots, d - 1.</math>
<center>
<math>S_j = r(\beta^{l_0-1+j}) = e(\beta^{l_0-1+j}), \quad j=1,\;\ldots,\;d-1.\quad\quad (1)</math>
</center>
Задача состоит в нахождении числа ошибок <math>u</math>, их позиций <math>i_1,\; i_2,\; \ldots,\; i_u</math> и их значений <math>e_{i_1},\; e_{i_2},\; \ldots,\; e_{i_u}</math> при известных синдромах <math>S_j</math>.
Предположим, для начала, что <math>u</math> в точности равно <math>t</math>. Запишем <math>(1)</math>синдромы в виде [[Система нелинейных уравнений|системы нелинейных уравнений]] в явном виде:
: <math>
<center>
\begin{cases}
S_1 = e_{i_1} \beta^{l_0 i_1} + e_{i_2} \beta^{l_0 i_2} + \ldots + e_{i_t} \beta^{l_0 i_t}, \\
S_2 = e_{i_1} \beta^{(l_0+1) i_1} + e_{i_2} \beta^{(l_0+1) i_2} + \ldots + e_{i_t} \beta^{(l_0+1) i_t}, \\
\vdots \\
S_{d-1} = e_{i_1} \beta^{(l_0+d-2) i_1} + e_{i_2} \beta^{(l_0+d-2) i_2} + \ldots + e_{i_t} \beta^{(l_0+d-2) i_t}. \\
\end{cases}
</math>
Обозначим через <math>X_k = \beta^{i_k}</math> ''локатор'' <math>k</math>-й ошибки, а через <math>Y_k = e_{i_k}</math> — ''величину'' ошибки, <math>k = 1, \ldots, t</math>. При этом все <math>X_k</math> различны, так как порядок элемента <math>\beta</math> равен <math>n</math>, и поэтому при известном <math>X_k</math> можно определить <math>i_k</math> как <math>i_k = \log_\beta X_k </math>.
<math>
: <math>
{ \begin{cases}
\begin{cases}
S_1 = e_{i_1} \beta^{l_0 i_1} + e_{i_2} \beta^{l_0 i_2} + \ldots + e_{i_t} \beta^{l_0 i_t} \\
S_2 S_1 = e_{i_1}Y_1 \betaX_1^{(l_0+1) i_1} + e_{i_2}Y_2 \betaX_2^{(l_0+1) i_2} + \ldots + e_{i_t}Y_t \betaX_t^{(l_0+1) i_t}, \\
S_2 = Y_1 X_1^{l_0+1} + Y_2 X_2^{l_0+1} + \ldots + Y_t X_t^{l_0+1}, \\
\cdots \cdots \cdots \cdots \cdots \cdots \cdots \\
\vdots \\
S_{d-1} = e_{i_1} \beta^{(l_0+d-2) i_1} + e_{i_2} \beta^{(l_0+d-2) i_2} + \ldots + e_{i_t} \beta^{(l_0+d-2) i_t} \\
S_{d-1} = Y_1 X_1^{l_0+d-2} + Y_2 X_2^{l_0+d-2} + \ldots + Y_t X_t^{l_0+d-2}.
\end{cases} }
\end{cases}
</math>
</center>
Обозначим через <math>X_k = \beta^{i_k}</math> ''локатор'' <math>k</math>-ой ошибки, а через <math>Y_k = e_{i_k}</math> ''величину'' ошибки, <math>k=1,\;\ldots,\;t</math>. При этом все <math>X_k</math> различны, так как порядок элемента <math>\beta</math> равен <math>n</math>, и поэтому при известном <math>X_k</math> можно определить <math>i_k</math> как <math>i_k = \log_{\beta} X_k </math>.
<center>
<math>
{ \begin{cases}
S_1 = Y_1 X_1^{l_0} + Y_2 X_2^{l_0} + \ldots + Y_t X_t^{l_0} \\
S_2 = Y_1 X_1^{l_0+1} + Y_2 X_2^{l_0+1} + \ldots + Y_t X_t^{l_0+1} \quad \quad \quad \quad \quad\quad(2) \\
\cdots \cdots \cdots \cdots \cdots \cdots \cdots \\
S_{d-1} = Y_1 X_1^{l_0+d-2} + Y_2 X_2^{l_0+d-2} + \ldots + Y_t X_t^{l_0+d-2}
\end{cases} }
</math>
</center>
Составим ''полином локаторов ошибок'':
: <math>\Lambda (x) = (1 - x X_1)(1 - x X_2) \ldots (1 - x X_t) = \Lambda_t x^t + \Lambda_{t-1} x^{t-1} + \ldots + \Lambda_1 x + 1.</math>
<center>
<math>\Lambda (x) = (1-xX_1)(1-xX_2)\ldots (1-xX_t) = \Lambda_t x^t + \Lambda_{t-1} x^{t-1} + \ldots + \Lambda_1 x + 1</math>
</center>
Корнями этого полинома являются элементы, обратные локаторам ошибок. Помножим обе части этого полинома на <math>Y_l X_{l}X_l^{\vartheta+t}</math>. Полученное равенство будет справедливо для <math>\vartheta = l_0,\; l_0 + 1,\; \ldots,\; l_0 + d - 1,\quad l = 1,\; \ldots,\; t</math>:
: <math>\Lambda(x) Y_l X_l^{\vartheta+t} = \Lambda_t x^t Y_l X_l^{\vartheta+t} + \Lambda_{t-1} x^{t-1} Y_l X_l^{\vartheta+t} + \ldots + \Lambda_1 x Y_l X_l^{\vartheta+t} + Y_l X_l^{\vartheta+t}.</math>
<center>
<math>\Lambda (x) Y_l X_{l}^{\vartheta+t} = \Lambda_t x^t Y_l X_{l}^{\vartheta+t} + \Lambda_{t-1} x^{t-1} Y_l X_{l}^{\vartheta+t} + \ldots + \Lambda_1 x Y_l X_{l}^{\vartheta+t} + Y_l X_{l}^{\vartheta+t} \quad (3)</math>
</center>
ПоложимЕсли подставить сюда <math>x = X_l^{-1}</math>, ито подставим в <math>(3)</math>. Получитсяполучится равенство, справедливое для каждого <math>l \in \{1,\; 2,\; \ldots,\; t\}</math> и при всех <math>\vartheta \in \{ l_0,\; l_0 + 1,\; \ldots,\; l_0 + d -1 1\}</math>:
: <math>0 = \Lambda_t Y_l X_l^{\vartheta} + \Lambda_{t-1} Y_l X_l^{\vartheta+1} + \ldots + \Lambda_1 Y_l X_l^{\vartheta+t-1} + Y_l X_l^{\vartheta+t}.</math>
Таким образом для каждого <math>l</math> можно записать своё равенство. Если их просуммировать по <math>l</math>, то получится равенство, справедливое для каждого <math>\vartheta \in \{l_0, l_0 + 1, \ldots, l_0 + d - 1\}</math>:
<center>
: <math>0 = \Lambda_t Y_l X_\sum_{l=1}^t Y_l X_l^{\vartheta} + \Lambda_{t-1} Y_l X_\sum_{l=1}^t Y_l X_l^{\vartheta+1} + \ldots + \Lambda_Lambda_1 \sum_{l=1}^t Y_l X_{l}X_l^{\vartheta+t-1} + Y_l X_\sum_{l=1}^t Y_l X_l^{\vartheta+t}.</math>
</center>
Поскольку <math>S_{j+p} = \sum_{l=1}^t Y_l X_l^{l_0+j+p-1} = \sum_{l=1}^t Y_l X_l^{\vartheta+p},\ j = 1, \ldots, d - 1,\ \vartheta = l_0 + j - 1</math> (то есть, <math>\vartheta</math> меняется в тех же пределах, что и ранее), система уравнений для синдромов преобразуется в [[Система линейных алгебраических уравнений|систему линейных уравнений]]:
Таким образом для каждого <math>l</math> можно записать своё равенство. Если их просуммировать по <math>l</math>, то получится равенство, справедливое для каждого <math>\vartheta \in { l_0,\;l_0+1,\;\ldots,\;l_0+d-1 }</math>:
: <math>
\begin{cases}
<center>
<math>0 = S_1 \Lambda_t \sum_{l=1}^t+ Y_l X_{l}^{\vartheta} +S_2 \Lambda_{t-1} \sum_{l=1}^t Y_l X_{l}^{\vartheta+1} + \ldots + S_t \Lambda_{1}Lambda_1 \sum_{l=1}^t Y_l X_-S_{l}^{\vartheta+t-1} + \sum_{l=1}^t, Y_l X_{l}^{\vartheta+t}</math>.\
S_2 \Lambda_t + S_3 \Lambda_{t-1} + \ldots + S_{t+1} \Lambda_1 = -S_{t+2}, \\
</center>.
\vdots \\
S_t \Lambda_t + S_{t+1} \Lambda_{t-1} + \ldots + S_{2t-1} \Lambda_1 = -S_{2t},
Учитывая <math>(2)</math> и то, что <math>S_{j+p} = \sum_{l=1}^t Y_l X_{l}^{l_0+j+p-1} = \sum_{l=1}^t Y_l X_{l}^{\vartheta+p}, \quad j=1,\;\ldots,\;d-1, \quad \vartheta = l_0+j-1 </math> (то есть <math>\vartheta</math> меняется в тех же пределах, что и ранее) получаем [[Система линейных алгебраических уравнений|систему линейных уравнений]]:
\end{cases}
<center>
<math>
{ \begin{cases}
S_1 \Lambda_t + S_2 \Lambda_{t-1} + \ldots + S_t \Lambda_1 = -S_{t+1} \\
S_2 \Lambda_t + S_3 \Lambda_{t-1} + \ldots + S_{t+1} \Lambda_1 = -S_{t+2} \quad \quad \quad \quad \quad\quad(4) \\
\cdots \cdots \cdots \cdots \cdots \cdots \cdots \\
S_t \Lambda_t + S_{t+1} \Lambda_{t-1} + \ldots + S_{2t-1} \Lambda_1 = -S_{2t}
\end{cases} }
</math>
или, в матричной форме,
</center>
: <math>S^{(t)} \bar\Lambda^{(t)} = -\bar s^{(t)},</math>
Или в матричной форме
<center>
<math>S^{(t)} \bar\Lambda^{(t)} = -\bar s^{(t)},</math>
</center>
где
: <math>
S^{(t)} = \begin{pmatrix}
<center>
S_1 & S_2 & \ldots & S_t \\
<math>
S_2 & S_3 & \ldots & S_{t+1} \\
S^{(t)}={ \left[ \begin{matrix}
S_1 \cdots & S_2\cdots & \ldotscdots & S_t \\
S_2 S_t & S_3S_{t+1} & \ldots & S_{t+2t-1} \\
\end{pmatrix},
\cdots & \cdots & \cdots & \\
\quad
S_t & S_{t+1} & \ldots & S_{2t-1}
\bar\Lambda^{(t)} = \begin{pmatrix}
\end{matrix} \right] }, \quad \quad \quad \quad \quad\quad(5)
\Lambda_t \\
\Lambda_{t-1} \\
\cdots \\
\Lambda_1
\end{pmatrix},
\quad
\bar s^{(t)} = \begin{pmatrix}
S_{t+1} \\
S_{t+2} \\
\cdots \\
S_{2t}
\end{pmatrix}.
</math>
Если число ошибок и в самом деле равно <math>t</math>, то эта система разрешима, и можно найти значения коэффициентов <math>\Lambda_1, \ldots, \Lambda_t</math>. Если же число <math>u < t</math>, то [[определитель]] матрицы <math>S^{(t)}</math> будет равен <math>0</math>. Это есть признак того, что количество ошибок меньше <math>t</math>. Поэтому необходимо составить систему, предполагая число ошибок равным <math>t - 1</math>, вычислить определитель новой матрицы <math>S^{(t-1)}</math> и т. д. до тех пор, пока не установим истинное число ошибок.
<math>
\bar\Lambda^{(t)} =
{ \left[ \begin{matrix}
\Lambda_t \\
\Lambda_{t-1} \\
\cdots \\
\Lambda_1
\end{matrix} \right] },
\quad \quad
\bar s^{(t)}
{ \left[ \begin{matrix}
S_{t+1} \\
S_{t+2} \\
\cdots \\
S_{2t}
\end{matrix} \right] }
</math>
</center>
Если число ошибок и в самом деле равно <math>t</math>, то система <math>(4)</math> разрешима, и можно найти значения коэффициентов <math>\Lambda_{1},\ldots,\Lambda_{t}</math>. Если же число <math>u < t</math>, то [[определитель]] матрицы <math>S^{(t)}</math> системы <math>(4)</math> будет равен <math>0</math>. Это есть признак того, что количество ошибок меньше <math>t</math>. Поэтому необходимо составить систему <math>(4)</math>, предполагая число ошибок равным <math>t-1</math>. Высчитать определитель новой матрицы <math>S^{(t-1)}</math> и т. д., до тех пор, пока не установим истинное число ошибок.
=== Поиск Ченя ===
| 