---- Для понимания материалов настоящего раздела крайне желательно ознакомиться с разделом ((/codes/cyclic)). ==Коды Боуза-Чоудхури-Хоквингема== ===Идея== Для ее пояснения обратимся к материалам ☞ ((:codes:cyclic#анализом_с_помощью_корней_порождающего_полинома ПУНКТА)) и рассмотрим циклические коды в $ \mathbb Z^n $. Принадлежность кодового слова $ (b_0,b_1,\dots,b_{n-1}) $ циклическому коду $ C_{} $, порождаемому полиномом $$ g(x)=a_0+a_1x+a_2x^2+\dots+a_{r}x^{r}, (r ☞ ((:codes:cyclic#анализом_с_помощью_корней_порождающего_полинома ПУНКТЕ)) предлагался метод нахождения ошибок в случае, когда они соседствуют, т.е. $ k=j+1 $. Фактически, задача в такой постановке оказывалась задачей с тремя неизвестными: требовалось найти место ошибки $ j_{} $ и величины ошибок $ E_j,E_{j+1} $. Теперь мы рассмотреть общий случай, когда неизвестными являются четыре величины $ j,k,E_j,E_k $. Интуитивно понятно, что для нахождения этих четырех неизвестных требуется, по меньшей мере, такое же количество условий. По аналогии с рассмотренным в ☞ ((:codes:cyclic#анализом_с_помощью_корней_порождающего_полинома ПУНКТЕ)) подходом, будем пытаться найти эти условия виде $ \tilde G(\lambda_{\ell})=0 $, где $ \lambda_{\ell} $ --- корень порождающего код полинома $ g_{}(x) $, т.е. $ g_{}(\lambda_{\ell})=0 $ и $ G(\lambda_{\ell})=0 $. Если $ \lambda_1,\lambda_2,\lambda_3,\lambda_4 $ --- различные корни полинома $ g_{}(x) $, то подстановка их в "зашумленный" полином $ \tilde G(x) $ приведет к системе уравнений $$ E_j\lambda_1^j+E_k\lambda_1^k= \tilde G(\lambda_1),\ E_j\lambda_2^j+E_k\lambda_2^k= \tilde G(\lambda_2),\ E_j\lambda_3^j+E_k\lambda_3^k= \tilde G(\lambda_3),\ E_j\lambda_4^j+E_k\lambda_4^k= \tilde G(\lambda_4) \ , $$ линейной по неизвестным $ E_j $ и $ E_k $, но нелинейной по значениям индексов $ j_{} $ и $ k_{} $. Эту систему требуется решить в целых числах. Можно попробовать осуществить поиск решений перебором вариантов (например, положив гипотезой что величины ошибок $ E_j $ и $ E_k $ невелики); однако этот подход не кажется конструктивным если оценить число потенциально возможных комбинаций в зависимости от $ n_{} $. Допустим теперь, что порождающий $ n_{} $-код полином $ g_{}(x) $ удается подобрать так, чтобы его корнями оказались бы величины $$ \lambda_1=\varepsilon_1,\ \lambda_2=\varepsilon_1^2,\ \lambda_3=\varepsilon_1^3,\ \lambda_4=\varepsilon_1^4 \quad npu \quad \varepsilon_1=\cos \frac{2\pi}{n}+\mathbf i \sin \frac{2\pi}{n} $$ --- ((:complex_num#корни_из_единицы корне степени n из единицы)). Посмотрим как можно использовать эту возможность для решения задачи исправления ошибок. Подставим корни в предыдущую систему, воспользовавшись равенствами $$ \varepsilon_1^j = \varepsilon_j=\cos \frac{2\pi\,j}{n}+\mathbf i \sin \frac{2\pi \, j}{n} ,\ \varepsilon_1^k=\varepsilon_k= \cos \frac{2\pi\,k}{n}+\mathbf i \sin \frac{2\pi\,k}{n} \ , $$ получим "систему ошибок"[[Это название --- мое изобретение, ((http://ru.wikipedia.org/wiki/%CA%EE%EC%E5%E4%E8%FF_%EE%F8%E8%E1%EE%EA Шекспиром навеянное)) --- за пределами настоящего пункта не используется; все канонические определения содержатся в следующем пункте.]] $$ \left\{ \begin{array}{rrl} E_j \varepsilon_j & + E_k \varepsilon_k & = \tilde G(\varepsilon_1), \\ E_j \varepsilon_j^2 & + E_k \varepsilon_k^2 & = \tilde G(\varepsilon_1^2), \\ E_j \varepsilon_j^3& + E_k \varepsilon_k^3 & = \tilde G(\varepsilon_1^3), \\ E_j \varepsilon_j^4 & + E_k \varepsilon_k^4 & = \tilde G(\varepsilon_1^4). \end{array} \right. $$ Попробуем на основе этих равенств сконструировать новое --- квадратное: $$ \sigma_2+\sigma_1x+\sigma_0x^2=0 \ , $$ которому должны удовлетворять обе величины $ \varepsilon_j $ и $ \varepsilon_k $. С этой целью умножим первое из этих разыскиваемых уравнений на $ E_j \varepsilon_j $, второе --- на $ E_k \varepsilon_k $ $$ \left\{ \begin{array}{rl|lc|lc} \sigma_2+\sigma_1\varepsilon_j+\sigma_0\varepsilon_j^2&=0, & \times E_j \varepsilon_j & & \times E_j \varepsilon_j^2 & \\ & & & + & & + \\ \sigma_2+\sigma_1\varepsilon_k+\sigma_0\varepsilon_k^2&=0 & \times E_k \varepsilon_k & & \times E_k \varepsilon_k^2. & \end{array} \right. $$ и сложим: $$ \sigma_2 (E_j \varepsilon_j +E_k \varepsilon_k)+\sigma_1(E_j \varepsilon_j^2 +E_k \varepsilon_k^2)+\sigma_0(E_j \varepsilon_j^3 +E_k \varepsilon_k^3)=0 \ ; $$ аналогичным образом, домножим первое из равенств на $ E_j \varepsilon_j^2 $, второе --- на $ E_k \varepsilon_k^2 $ и сложим: $$ \sigma_2 (E_j \varepsilon_j^2 +E_k \varepsilon_k^2)+\sigma_1(E_j \varepsilon_j^3 +E_k \varepsilon_k^3)+\sigma_0(E_j \varepsilon_j^4 +E_k \varepsilon_k^4)=0 \ . $$ Обратим теперь внимание на то, что все величины, стоящие в полученных формулах в круглых скобках, нам известны из приведенной выше системы: $$ \left\{ \begin{array}{rl} \sigma_2\tilde G(\varepsilon_1)+\sigma_1\tilde G(\varepsilon_1^2)+\sigma_0\tilde G(\varepsilon_1^3)&=0, \\ \sigma_2\tilde G(\varepsilon_1^2)+\sigma_1\tilde G(\varepsilon_1^3)+\sigma_0\tilde G(\varepsilon_1^4)&=0. \end{array} \right. $$ Эта система линейна относительно неизвестных коэффициентов $ \sigma_0, \sigma_1,\sigma_2 $. Возникает вопрос о ее разрешимости. !!Т!! **Теорема.** //Пусть порождающий код полином обладает корнями// $ \varepsilon_1,\varepsilon_1^2,\varepsilon_1^3,\varepsilon_1^4 $. //Если при передаче кодового полинома// $$ G(x)=b_0+b_1x+b_2x^2+\dots+b_{n-1}x^{n-1} $$ //произошли ровно две ошибки в// $ j_{} $//-м и// $ k_{} $//-м коэффициентах, и на выходе канала связи получен полином// $ \tilde G(x) $, //то корни степени// $ n_{} $ //из единицы, обозначенные// $ \varepsilon_j $ //и// $ \varepsilon_k $, //удовлетворяют// "уравнению ошибочных позиций"[[Снова доморощенное определение...]] $$ \left| \begin{array}{ccc} \tilde G(\varepsilon_1) & \tilde G(\varepsilon_1^2) & \tilde G(\varepsilon_1^3) \\ \tilde G(\varepsilon_1^2) & \tilde G(\varepsilon_1^3) & \tilde G(\varepsilon_1^4) \\ 1 & x & x^2 \end{array} \right|=0 \ . $$ **Доказательство.** Фактически к двум линейным уравнениям мы приписываем $ \sigma_2+\sigma_1x+\sigma_0x^2=0 $, и к получившейся линейной однородной системе относительно неизвестных $ \sigma_2,\sigma_1,\sigma_0 $ применяем критерий ((:algebra2:linearsystems#система_однородных_уравнений существования нетривиального решения)): определитель этой системы должен быть равен нулю. ♦ В следующем пункте я часто буду употреблять подобные детерминантные представления, нетрадиционные для теории кодирования. В последней обычно разыскивают полином ошибочных позиций в виде нормализованного полинома --- со старшим коэффициентом равным $ 1_{} $. Разрешив уравнение ошибочных позиций, мы определим величины $ \varepsilon_j $ и $ \varepsilon_k $, и, следовательно, сможем восстановить значения соответствующих индексов $ \{j,k\} \subset \{0,1,2,\dots,n-1\} $, т.е. __номеров коэффициентов полинома__, в которых произошли ошибки. Величины же $ E_j $ и $ E_k $ этих ошибок восстанавливаются из первых двух уравнений системы ошибок: $$ \left\{ \begin{array}{rrl} E_j \varepsilon_j & + E_k \varepsilon_k & = \tilde G(\varepsilon_1), \\ E_j \varepsilon_j^2 & + E_k \varepsilon_k^2 & = \tilde G(\varepsilon_1^2) \end{array} \right. $$ Впрочем, как правило, величины $ E_j $ и $ E_k $ можно установить только из первого уравнения --- если воспользоваться условием их __вещественности__. Остался открытым вопрос о возможности выбора порождающего циклический код полинома $ g_{}(x) $, имеющего одновременно корнями $ \varepsilon_1, \varepsilon_1^2,\varepsilon_1^3,\varepsilon_1^4 $. При этом полином $ g_{}(x) $ должен иметь целочисленные коэффициенты --- иначе мы не сможем организовать выбор кодовых слов в пространстве $ \mathbb Z^n $. По аналогии с подходом ☞ ((:codes:cyclic#анализом_с_помощью_корней_порождающего_полинома ПУНКТА)) можно попробовать выбрать полином $ g_{}(x) $ как произведение ((:complex_num:circlediv полиномов деления круга)) $ X_j(x) $. Действительно, при любом $ n\in \mathbb N $ полином $ X_n(x) $ будет иметь корнем $ \varepsilon_1 $, равно как и любой другой первообразный корень степени $ n_{} $. Тогда при $ n\ge 5 $ и $ n_{} $ --- простом, все степени $ \{\varepsilon_1^j\}_{j=1}^{n-1} $ будут первообразными корнями степени $ n_{} $, и, следовательно, будут корнями полинома $ X_n(x) $. В этом случае можно было бы взять $ g(x)\equiv X_n(x) $, однако, хотя с формальной точки зрения это и допустимо, тем не менее, с точки зрения практической пользы такой вариант бессмыслен: при любом ((:codes:cyclic#кодирование способе кодирования)) в циклическом коде размерность кодового пространства $ \mathbb U $ становится равной $ 1_{} $, т.е. в $ n_{} $-кодовом слове остается единственный свободный разряд, который можно использовать в качестве информационного. Итак, число $ n\ge 5 $ должно быть составным. Пусть $ n_{} $--- нечетно. Тогда (см. ☞ ((:complex_num#корни_из_единицы ЗДЕСЬ))) величины $ \varepsilon_1, \varepsilon_1^2,\varepsilon_1^4 $ будут все первообразными корнями и, следовательно, корнями полинома $ X_n(x) $. Если $ n_{} $ не делится на $ 3_{} $, то и $ \varepsilon_1^3 $ будет первообразным корнем, т.е. корнем $ X_n(x) $. Обобщим эти рассуждения: если $ n_{}\ge 5 $ --- составное и $ \operatorname{HOD}(n,6)=1 $, то можно взять $ g(x)\equiv X_n(x) $. Если $ \operatorname{HOD}(n,6)>1 $, то полином $ g_{}(x) $ можно построить в виде произведения полиномов $ X_j(x) $. Так, при $ \operatorname{HOD}(n,6)=2 $ можно взять $ g(x)\equiv X_n(x)X_{n/2}(x) $ в случае когда $ n_{} $ не делится на $ 4_{} $ и $ g(x)\equiv X_n(x)X_{n/2}(x)X_{n/4}(x) $ в случае когда $ n_{} $ делится на $ 4_{} $ !!П!! **Пример.** Пусть $ n=15 $ и порождающий циклический код полином выбран в виде $$ g(x)\equiv X_5(x)X_{15}(x)\equiv (1+x+x^2+x^3+x^4)(1-x+x^3-x^4+x^5-x^7+x^8) \equiv $$ $$ \equiv 1+x^3+x^6+x^9+x^{12} \ . $$ Пусть при передаче некоторого кодового полинома $ G_{}(x) $ на выходе канала получен полином $$ \tilde G(x)=-1+5\,x+2\,x^2-x^3+3\,x^4+2\,x^5-x^6+5\,x^7+2\,x^8-x^9+5\,x^{10}+2\,x^{11}-x^{12}+2\,x^{13}+2\,x^{14} \ . $$ Требуется восстановить кодовый полином $ G_{}(x) $, основываясь на гипотезе, что при передаче произошло ровно две ошибки. **Решение.** Порождающий код полином $ g_{}(x) $ удовлетворяет условиям теоремы: его корнями являются величины $ \varepsilon_1, \varepsilon_1^2,\varepsilon_1^3,\varepsilon_1^4 $ при $$ \varepsilon_1=\cos \frac{2\pi}{15}+\mathbf i \sin \frac{2\pi}{15} \approx 0.913545+0.406736\, \mathbf i \ . $$ Вычисляем $ \tilde G(\varepsilon_1) \approx -1.798335+0.240391 \, \mathbf i $. Поскольку $ \tilde G(\varepsilon_1) \ne 0 $, то заключаем, что хотя бы одна ошибка при передаче по каналу произошла. Вычисляем дополнительно $ \tilde G(\varepsilon_1^2), \tilde G(\varepsilon_1^3), \tilde G(\varepsilon_1^4) $ и составляем уравнение ошибочных позиций из теоремы: $$ \left| \begin{array}{rrr} -1.798335+0.240391 \, \mathbf i & 2.269881+3.399389 \, \mathbf i & 1.809017+3.665469 \, \mathbf i \\ 2.269881+3.399389 \, \mathbf i & 1.809017+3.665469 \, \mathbf i & 1.107352-1.437208 \, \mathbf i \\ 1 & x & x^2 \end{array} \right|=0 $$ или $$ (17.562306-12.759762\, \mathbf i) +(-6.708203964+11.618950\, \mathbf i)x+(2.269125-21.589284\, \mathbf i)x^2=0 \ . $$ Решаем его и находим $$ \mu_1 \approx -0.104528+0.994522\, \mathbf i,\ \mu_2\approx 0.669131-0.743145\, \mathbf i \ . $$ Если при передаче по каналу произошли --- как утверждается в условии --- ровно две ошибки, то получившиеся значения должны быть корнями $ 15 $-й степени из единицы. Это немедленно проверяется. Остается выяснить каким значениям показателей $ \varepsilon_j $ и $ \varepsilon_k $ соответствуют эти числа. $$ 15 \arccos(-0.104528)/(2\pi) \approx 4 \quad \mbox{ и } \quad 0.994522>0 \quad \Rightarrow j=4 \ . $$ $$ 15 \arccos(0.669131)/(2\pi) \approx 2 \quad \mbox{ и } \quad -0.743145<0 \quad \Rightarrow k=15-2=13 \ . $$ Итак, полином $ \tilde G(x) $ имеет ошибочные коэффициенты при $ x^{4} $ и $ x^{13} $. Для нахождения величин этих ошибок имеем уравнение $$ E_4 \mu_1 + E_{13} \mu_2 = \tilde G(\varepsilon_1) \quad \iff \quad \left\{ \begin{array}{rrr} -0.104528 E_4 &+0.669131 E_{13} & = -1.798335, \\ 0.994522 E_4 &-0.743145 E_{13} & = 0.240391. \end{array} \right. $$ Откуда получаем $ E_4\approx -1.999997, E_{13} \approx -2.999997 $. Заключаем, что $ G(x)\equiv \tilde G(x) +2\,x^4+3\,x^{13} $. Теперь проверим насколько "устойчив" алгоритм к истинному количеству ошибок. Допустим, что вместо предполагаемых двух ошибок произошла одна и на выходе канала получен полином $ \tilde G(x)\equiv G(x)-4\,x^7 $. Уравнение ошибочных позиций из теоремы $$ \left| \begin{array}{rrr} 3.912590-0.831647 \, \mathbf i & -3.654182+1.626946 \, \mathbf i & 3.236068-2.351141 \, \mathbf i \\ -3.654182+1.626946 \, \mathbf i & 3.236068-2.351141 \, \mathbf i & -2.676522+2.972579 \, \mathbf i \\ 1 & x & x^2 \end{array} \right|=0 $$ вырождается в тождество $ 0\equiv 0 $. С формальной точки зрения, истинность уравнения сохраняется, только информации из него не извлечь... Модифицируем метод, играя на понижение количества ошибок --- составим уравнение $$ \left| \begin{array}{cc} \tilde G(\varepsilon_1) & \tilde G(\varepsilon_1^2) \\ 1 & x \end{array} \right|=0 \ \quad \iff $$ $$ \iff \quad (3.654181840-1.626946579\, \mathbf i )+(3.912590396-.8316467668\, \mathbf i )x=0 \quad \iff \mu\approx -0.978148+0.207912 \, \mathbf i \ . $$ Далее идем как в предыдущем случае: действительно, $ \mu^{15} = 1 $ и $$ 15 \arccos(-0.978148)/(2\pi) \approx 7 \quad \mbox{ и } \quad 0.207912 >0 \quad \Rightarrow j=7 \ . $$ Место ошибки обнаружено верно. Ее величину определяем из условия $ \tilde G(\varepsilon_1)=E_7 \mu $. ♦ Распространение идеи подхода для случая трех и более ошибок очевидно. Так, если порождающий $ n_{} $-код полином $ g_{}(x) $ имеет корнями $ \{\varepsilon_1^j\}_{j=1}^6 $, то это даст возможность исправления не менее трех ошибок. Соответствующее уравнение ошибочных позиций для определения номеров испорченных коэффициентов: $$ \left| \begin{array}{cccc} \tilde G(\varepsilon_1) & \tilde G(\varepsilon_1^2) & \tilde G(\varepsilon_1^3) & \tilde G(\varepsilon_1^4) \\ \tilde G(\varepsilon_1^2) & \tilde G(\varepsilon_1^3) & \tilde G(\varepsilon_1^4) & \tilde G(\varepsilon_1^5)\\ \tilde G(\varepsilon_1^3) & \tilde G(\varepsilon_1^4) & \tilde G(\varepsilon_1^5) & \tilde G(\varepsilon_1^6) \\ 1 & x & x^2 & x^3 \end{array} \right|=0 $$ строится по аналогии со случаем двух ошибок. Покажем здесь, что при наличии ровно трех ошибок в полиноме $ \tilde G(x) $, явившихся результатом передачи кодового полинома $ G_{}(x) $, построенное уравнение нетривиально. Итак, пусть $ \tilde G(x)\equiv G(x)+E_jx^j+E_kx^k+E_sx^s $. Рассмотрим коэффициент при $ x^{3} $ в уравнении ошибок: $$ \left| \begin{array}{ccc} \tilde G(\varepsilon_1) & \tilde G(\varepsilon_1^2) & \tilde G(\varepsilon_1^3) \\ \tilde G(\varepsilon_1^2) & \tilde G(\varepsilon_1^3) & \tilde G(\varepsilon_1^4) \\ \tilde G(\varepsilon_1^3) & \tilde G(\varepsilon_1^4) & \tilde G(\varepsilon_1^5) \end{array} \right|= \left| \begin{array}{ccc} E_j\varepsilon_j+E_k\varepsilon_k+E_s\varepsilon_s & E_j\varepsilon_j^2+E_k\varepsilon_k^2+E_s\varepsilon_s^2 & E_j\varepsilon_j^3+E_k\varepsilon_k^3+E_s\varepsilon_s^3 \\ E_j\varepsilon_j^2+E_k\varepsilon_k^2+E_s\varepsilon_s^2 & E_j\varepsilon_j^3+E_k\varepsilon_k^3+E_s\varepsilon_s^3 & E_j\varepsilon_j^4+E_k\varepsilon_k^4+E_s\varepsilon_s^4 \\ E_j\varepsilon_j^3+E_k\varepsilon_k^3+E_s\varepsilon_s^3 & E_j\varepsilon_j^4+E_k\varepsilon_k^4+E_s\varepsilon_s^4 & E_j\varepsilon_j^5+E_k\varepsilon_k^5+E_s\varepsilon_s^5 \end{array} \right| \ . $$ Этот определитель относится к типу ((:algebra2/hankel ганкелевых)); для его вычисления представим его в виде определителя произведения трех матриц $$ \det \left\{ \left( \begin{array}{ccc} 1 & 1 & 1 \\ \varepsilon_j & \varepsilon_k & \varepsilon_s \\ \varepsilon_j^2 & \varepsilon_k^2 & \varepsilon_s^2 \end{array} \right) \left( \begin{array}{ccc} E_j & 0 & 0 \\ 0& E_k & 0 \\ 0 & 0 & E_s \end{array} \right) \left( \begin{array}{ccc} \varepsilon_j & \varepsilon_j^2 & \varepsilon_j^3 \\ \varepsilon_k & \varepsilon_k^2 & \varepsilon_k^3 \\ \varepsilon_s & \varepsilon_s^2 & \varepsilon_s^3 \end{array} \right) \right\} \ . $$ Применение ((:algebra2:dets#теорема_бине_-_коши теоремы Бине-Коши)) сводит вычисление этого определителя к произведению определителей составляющих матриц. Определитель первой матрицы является ((:algebra2/vander определителем Вандермонда)) --- $$ \left| \begin{array}{ccc} 1 & 1 & 1 \\ \varepsilon_j & \varepsilon_k & \varepsilon_s \\ \varepsilon_j^2 & \varepsilon_k^2 & \varepsilon_s^2 \end{array} \right|=(\varepsilon_k -\varepsilon_j)(\varepsilon_s-\varepsilon_j)(\varepsilon_s-\varepsilon_k), $$ он отличен от нуля, поскольку, по предположению, числа $ \varepsilon_j, \varepsilon_k, \varepsilon_s $ все различны. Далее, определитель третьей матрицы $$ \left| \begin{array}{ccc} \varepsilon_j & \varepsilon_j^2 & \varepsilon_j^3 \\ \varepsilon_k & \varepsilon_k^2 & \varepsilon_k^3 \\ \varepsilon_s & \varepsilon_s^2 & \varepsilon_s^3 \end{array} \right|=\varepsilon_j\varepsilon_k\varepsilon_s \left| \begin{array}{ccc} 1 & 1 & 1 \\ \varepsilon_j & \varepsilon_k & \varepsilon_s \\ \varepsilon_j^2 & \varepsilon_k^2 & \varepsilon_s^2 \end{array} \right|=\varepsilon_j\varepsilon_k\varepsilon_s(\varepsilon_k -\varepsilon_j)(\varepsilon_s-\varepsilon_j)(\varepsilon_s-\varepsilon_k) \ , $$ также отличен от нуля, поскольку все числа $ \varepsilon_j,\varepsilon_k,\varepsilon_s $ еще и ненулевые. Определитель средней матрицы равен $ E_jE_kE_s $ и отличен от нуля по предположению, что величины ошибок --- ненулевые. Следовательно, коэффициент при $ x^{3} $ в уравнении ошибочных позиций отличен от нуля и уравнение не обращается в тривиальное тождество $ 0\equiv 0 $. Хочется развить этот успех на случай произвольного количества ошибок. К сожалению, на пути исполнения этого желания стоит препятствием уже упомянутое ранее ограничение на степень $ n_{} $. При фиксировании этого числа, добавление в состав кодового полинома $ g_{}(x) $ новых сомножителей из числа полиномов $ X_{\ell} (x) $ уменьшает количество информационных разрядов. ===Двоичные БЧХ-коды== Будем строить двоичный циклический $ n_{} $-разрядный код для случая $ n=2^M-1, M\in \mathbb N $. Основываясь на идее предыдущего пункта, будем строить его на основе порождающего полинома $ g_{}(x) $, имеющего корнями последовательные степени ((:gruppe:galois:vspom2 примитивного элемента поля Галуа)) $ \mathfrak A \in \mathbf{GF}(2^M) $: $$ \mathfrak A, \mathfrak A^2, \mathfrak A^3,\dots,\mathfrak A^{2\tau} \quad npu \quad \tau \ge 2 \ . $$ Как построить такой полином? Примитивный элемент $ \mathfrak A $ поля $ \mathbf{GF}(2^M) $ является корнем неприводимого полинома степени $ m_{} $ над $ \mathbf{GF}(2) $ --- который также называется примитивным. Выражения для примитивных полиномов берутся из заранее составленных таблиц. Обозначим этот полином $ f_{1}(x) $. Тогда, в соответствии с теоремой 1, приведенной ☞ ((:gruppe:galois#полиномы_над_gf_p ЗДЕСЬ)), корнями этого же полинома будут и величины $ \mathfrak A^2, \mathfrak A^4,\dots, \mathfrak A^{2^{m-1}} $. Но вот величина $ \mathfrak A^3 $ не будет корнем $ f_{1}(x) $. С другой стороны, она будет корнем некоторого другого неприводимого полинома $ f_3(x) $. Поэтому интересующий нас полином $ g_{}(x) $ должен иметь представление в виде произведения примитивных полиномов $$ g(x)\equiv f_1(x)f_3(x)\times \dots \ , $$ каждый из которых имеет корнем определенную величину из множества $ \{ \mathfrak A^{j}\}_{j=1}^{2\tau} $. Строго говоря, определим $ g_{}(x) $ равенством $$ g(x)\equiv \operatorname{HOK}(f_1,f_2,\dots,f_{2\tau}) \ , $$ где $ \operatorname{HOK} $ означает ((:polynomial#наибольший_общий_делитель наименьшее общее кратное)) неприводимых над $ \mathbf{GF}(2) $ полиномов $ f_{j}(x) $, таких, что $ f_{j}(\mathfrak A^{j})=\mathfrak o $. Такое представление позволяет, во-первых, обеспечить выполнение требования к структуре множества корней полинома $ g_{}(x) $, а, во-вторых, отбросить "дублирующие" полиномы. !!П!! **Пример.** Пусть $ M=4 $. Построить полином, корнями которого являются $ \mathfrak A, \mathfrak A^2, \mathfrak A^3, \mathfrak A^4 $, где $ \mathfrak A $ означает примитивный элемент поля $ \mathbf{GF}(16) $. **Решение.** Примитивный элемент поля $ \mathbf{GF}(16) $ является корнем одного из неприводимых над $ \mathbf{GF}(2) $ полиномов: $ x^4+x+1 $ или $ x^4+x^3+1 $ (см. разбор ☞ ((:gruppe:galois:vspom3 ЗДЕСЬ))). Возьмем $ f_1(x)=x^4+x+1 $. Корнями этого полинома будут также $ \mathfrak A^2 $ и $ \mathfrak A^4 $. Величина $ \mathfrak A^3 $ будет корнем полинома $ f_3(x)=x^4+x^3+x^2+x+1 $. Таким образом, $$ g(x)\equiv (x^4+x+1)(x^4+x^3+x^2+x+1) \pmod{2} \equiv x^8+x^7+x^6+x^4+1 \ . $$ Кодовое пространство, порождаемое этим полиномом, имеет размерность $ k=15-8=7 $, т.е. на $ 7_{} $ информационных битов приходится $ 8_{} $ проверочных. Иными словами, этот линейный код ((:codes:hamming#линейные_коды является)) $ (15,7) $-кодом. Если бы мы поставили задачу нахождения полинома $ g_{}(x) $ с корнями $ \mathfrak A, \mathfrak A^2, \mathfrak A^3, \mathfrak A^4,\mathfrak A^5,\mathfrak A^6 $, то для нам пришлось бы домножить предыдущий полином на $ x^2+x+1 $, поскольку именно его корнем является $ \mathfrak A^5 $ (в то время как $ \mathfrak A^6 $ является корнем уже используемого полинома $ f_3 $): $$ g(x)\equiv (x^4+x+1)(x^4+x^3+x^2+x+1)(x^2+x+1) \pmod{2} \equiv x^{10}+x^8+x^5+x^4+x^2+x+1 \ . $$ Код, порождаемый этим полиномом, является $ (15,5) $-кодом, т.е. на $ 5_{} $ информационных битов приходится $ 10_{} $ проверочных. ♦ Итак, допустим нам удалось построить циклический код на основе порождающего полинома $ g_{}(x) $, имеющего корнями $ \{ \mathfrak A^{j}\}_{j=1}^{2\tau} $, где $ \mathfrak A $ --- примитивный элемент поля $ \mathbf{GF}(2^M) $. Кодирование передаваемой информации производится любым из способов, ((:codes:cyclic#кодирование принятых в циклических кодах)). Покажем, что такой код способен исправить от одной до $ \tau_{} $ ошибок при передаче по каналу связи. Пусть при передаче кодового полинома $ G_{}(x) $ произошло ровно $ \ell_{} $ ошибок в коэффициентах при $ x^{j_1},x^{j_2},\dots,x^{j_{\ell}} $: $$ \tilde G(x) \equiv G(x)+E_{j_1} x^{j_1}+E_{j_2} x^{j_2}+\dots+ E_{j_{\ell}} x^{j_{\ell}} \pmod{2} \ . $$ Заметим, что для двоичного кода ошибка --- это либо $ 0 \to 1 $, либо $ 1 \to 0 $, и, следовательно, величина ошибки $ E_{j} $ всегда равна $ 1_{} $. Подставляем в полином $ \tilde G(x) $ корни $ \{ \mathfrak A^{j}\}_{j=1}^{2\tau} $ полинома $ g_{}(x) $. Кодовый полином обращается на них в нуль, так что получаем: $$\left\{\begin{array}{lllll} \tilde G(\mathfrak A)&= \mathfrak A^{j_1}&+\mathfrak A^{j_2}&+\dots& + \mathfrak A^{j_{\ell}}, \\ \tilde G(\mathfrak A^2)&= \mathfrak A^{2j_1}&+\mathfrak A^{2j_2}&+\dots& + \mathfrak A^{2j_{\ell}}, \\ \tilde G(\mathfrak A^3)&= \mathfrak A^{3j_1}&+\mathfrak A^{3j_2}&+\dots& + \mathfrak A^{3j_{\ell}}, \\ \dots & & & \dots \\ \tilde G(\mathfrak A^{2\tau})&= \mathfrak A^{2\tau j_1}&+\mathfrak A^{2 \tau j_2}&+\dots& + \mathfrak A^{2 \tau j_{\ell}}. \end{array} \right. $$ Величины $ \mathfrak A^{j_1},\mathfrak A^{j_2},\dots,\mathfrak A^{j_{\ell}} $ называются **локаторами ошибок**. Система уравнений для их определения --- существенно нелинейная. Однако, благодаря наработанному в предыдущем пункте, у нас имеется конструктивный подход к ее решению. Именно, мы разыскиваем полином $$ L(x)=\sigma_{0}x^{\ell}+ \sigma_1x^{\ell-1}+\dots+\sigma_{\ell} $$ имеющий корнями локаторы ошибок, т.е. такой, что $$ L(\mathfrak A^{j_1})=\mathfrak o,L(\mathfrak A^{j_2})=\mathfrak o,\dots, L(\mathfrak A^{j_{\ell}})=\mathfrak o \ . $$ Полином $ L(x) $ называется **полиномом локаторов ошибок**. Подчеркнем, что его коэффициенты являются элементами поля Галуа: $ \{\sigma_j\}_{j=0}^{\ell} \subset \mathbf{GF}(2^M) $. !!Т!! **Теорема.** //Пусть порождающий код полином обладает корнями// $ \{ \mathfrak A^{j}\}_{j=1}^{2\tau} $, где $ \mathfrak A $ --- примитивный элемент поля $ \mathbf{GF}(2^M) $. //Если при передаче кодового полинома// $$ G(x)=b_0+b_1x+b_2x^2+\dots+b_{n-1}x^{n-1}, \ (n=2^M-1) $$ //произошли ровно// $ \ell $ //ошибок в коэффициентах с номерами// $ \{j_k\}_{k=1}^{\ell} $, //и на выходе канала связи получен полином// $ \tilde G(x) $, //то при// $ \tau \ge \ell $ //локаторы ошибок// $ \{\mathfrak A^{j_k}\}_{k=1}^{\ell} $ //удовлетворяют уравнению// $$ L(x)= \left| \begin{array}{lllcl} \tilde G(\mathfrak A) & \tilde G(\mathfrak A^2) & \tilde G(\mathfrak A^3) & \dots & \tilde G(\mathfrak A^{\ell+1}) \\ \tilde G(\mathfrak A^2) & \tilde G(\mathfrak A^3) & \tilde G(\mathfrak A^4) & \dots & \tilde G(\mathfrak A^{\ell+2}) \\ \tilde G(\mathfrak A^3) & \tilde G(\mathfrak A^4) & \tilde G(\mathfrak A^5) & \dots & \tilde G(\mathfrak A^{\ell+3}) \\ \dots & & & & \dots \\ \tilde G(\mathfrak A^{\ell}) & \tilde G(\mathfrak A^{\ell+1}) & \tilde G(\mathfrak A^{\ell+2}) & \dots & \tilde G(\mathfrak A^{2\ell}) \\ 1 & x & x^2 & \dots & x^{\ell} \end{array} \right|=\mathfrak o $$ //и это уравнение имеет степень// $ \ell_{} $. //Если же произошло меньше чем// $ \ell_{} $ //ошибок, то это уравнение обращается в тождество// $ \mathfrak o = \mathfrak o $. !!П!! **Пример.** Рассмотрим $ (15,5) $-код из предыдущего примера --- пусть порождающий его полином имеет вид $$ g(x)= x^{10}+x^8+x^5+x^4+x^2+x+1 \ . $$ Пусть при передаче некоторого кодового полинома $ G_{}(x) $ произошло некоторое количество ошибок, и на выходе канала связи оказался полином $$ \tilde G(x)= 1+x^3+x^4+x^7+x^{10}+x^{12}+x^{13}+x^{14} \ . $$ Попробуем исправить эти ошибки, основываясь на предыдущем результате. Максимально возможное количество ошибок, которых потенциально возможно "отловить" с его помощью, равно $ 3_{} $. Положив эту оценку стартовой гипотезой, строим детерминантное представление для полинома локаторов ошибок: $$ L(x)= \left| \begin{array}{lllcl} \tilde G(\mathfrak A) & \tilde G(\mathfrak A^2) & \tilde G(\mathfrak A^3) & \tilde G(\mathfrak A^4) \\ \tilde G(\mathfrak A^2) & \tilde G(\mathfrak A^3) & \tilde G(\mathfrak A^4) & \tilde G(\mathfrak A^5) \\ \tilde G(\mathfrak A^3) & \tilde G(\mathfrak A^4) & \tilde G(\mathfrak A^5) & \tilde G(\mathfrak A^6) \\ 1 & x & x^2 & x^{3} \end{array} \right| \ . $$ Здесь через $ \mathfrak A $ обозначен корень полинома $ x^4+x+1 $; он является примитивным элементом поля $ \mathbf{GF}(16) $. Вычисляем элементы определителя, пользуясь таблицей для степеней $ \mathfrak A^j $, приведенной ☞ ((:gruppe:galois:vspom4 ЗДЕСЬ)). $$ \begin{array}{rccccccc} \tilde G(\mathfrak A) =& 1 +\mathfrak A^3 &+ \mathfrak A^4 &+\mathfrak A^7&+\mathfrak A^{10}& +\mathfrak A^{12}& +\mathfrak A^{13}& +\mathfrak A^{14}= \\ =&1+\mathfrak A^3&+(\mathfrak A+1)& +(\mathfrak A^3+\mathfrak A+1) &+(\mathfrak A^2+\mathfrak A+1)&+(\mathfrak A^3+\mathfrak A^2+\mathfrak A+1)&+(\mathfrak A^3+\mathfrak A^2+1)&+(\mathfrak A^3+1)= \end{array} $$ $$ {}_{} \qquad =\mathfrak A^3+\mathfrak A^2+1=\mathfrak A^{13} \ . $$ Поскольку $ \tilde G(\mathfrak A) \ne \mathfrak o $, то хотя бы одна ошибка при передаче произошла. Далее, $$ \tilde G(\mathfrak A^2)=\mathfrak A^3+\mathfrak A^2+\mathfrak A=\mathfrak A^{11},\ \tilde G(\mathfrak A^3)=\mathfrak o,\ \tilde G(\mathfrak A^4)=\mathfrak A^3+\mathfrak A +1=\mathfrak A^7,\ \tilde G(\mathfrak A^5)=\mathfrak A^2+\mathfrak A=\mathfrak A^5,\ \tilde G(\mathfrak A^6)=\mathfrak o \ . $$ Разложение определителя по последней строке, начинаем с правого угла: коэффициент при $ x^{3} $ равен[[Пока не решил, какое из представлений элементов поля Галуа более удобно для счёта определителей, привожу оба варианта.]] $$ \left| \begin{array}{ccc} \mathfrak A^3+\mathfrak A^2+1 & \mathfrak A^3+\mathfrak A^2+\mathfrak A & \mathfrak o \\ \mathfrak A^3+\mathfrak A^2+\mathfrak A & \mathfrak o & \mathfrak A^3+\mathfrak A +1 \\ \mathfrak o & \mathfrak A^3+\mathfrak A +1 & \mathfrak A^2+\mathfrak A \end{array} \right| = \left| \begin{array}{ccc} \mathfrak A^{13} & \mathfrak A^{11} & \mathfrak o \\ \mathfrak A^{11} & \mathfrak o & \mathfrak A^7 \\ \mathfrak o & \mathfrak A^7 & \mathfrak A^5 \end{array} \right|=\mathfrak o \ . $$ Следовательно, $ \deg L(x)\le 3 $, и это[[На самом деле, $ L(x) $ тождественно равен $ \mathfrak o $, но этот факт совершенно не существен для последующего.]] свидетельствует о том, что количество ошибок не может равняться $ 3_{} $. Выдвигаем гипотезу о том, что количество ошибок передачи равно $ 2_{} $. Уменьшаем размерность соответствующего определителя: $$ L(x)= \left| \begin{array}{lll} \tilde G(\mathfrak A) & \tilde G(\mathfrak A^2) & \tilde G(\mathfrak A^3) \\ \tilde G(\mathfrak A^2) & \tilde G(\mathfrak A^3) & \tilde G(\mathfrak A^4) \\ 1 & x & x^2 \end{array} \right| = \left| \begin{array}{ccc} \mathfrak A^{13} & \mathfrak A^{11} & \mathfrak o \\ \mathfrak A^{11} & \mathfrak o & \mathfrak A^7 \\ 1 & x & x^2 \end{array} \right|=\mathfrak A^{22}x^2+\mathfrak A^{20}x+\mathfrak A^{18}=\mathfrak A^{7}x^2+\mathfrak A^{5}x+\mathfrak A^{3} \ . $$ В этом случае полином $ L(x) $ нетривиален. Непосредственной проверкой убеждаемся, что корнями полинома являются элементы поля $ \mathfrak A^{3} $ и $ \mathfrak A^{8} $. Это --- локаторы ошибок, они указывают на позиции ошибок в $ 3_{} $-м и $ 8 $-м коэффициентах полинома $ \tilde G(x) $. Кодовым является полином $$ G(x)= 1+x^4+x^7+x^8+x^{10}+x^{12}+x^{13}+x^{14} \ . $$ ♦ Построенный выше двоичный код является примером **кода Боуза-Чоудхури-Хоквингема**[[Bose R.C., Ray-Chaudhury D.K., Hocquenghem A.]] или **БЧХ-кода**. Его ((:codes:hamming#расстояние_хэмминга кодовое расстояние)) не превосходит величины $$ d_0=1+2\tau \ , $$ которая называется **конструктивным расстоянием** БЧХ-кода. Число $ k_{} $ информационных символов БЧХ-кода и, соответственно, число $ n-k=2^M-k-1 $ проверочных символов зависит от степеней множителей полинома $ g_{}(x) $ --- неприводимых по модулю $ 2_{} $ полиномов. !!=>!! ((:codes:cyclic#двоичные_коды Код Хэмминга)) является частным случаем БЧХ-кода, он соответствует случаю $ \tau=1 $. В этом случае кодовым полиномом берется просто произвольный примитивный полином --- поскольку его корнями обязательно будут две последовательные степени $ \mathfrak A $ и $ \mathfrak A^2 $ (см. теорему $ 1 $ ☞ ((:gruppe:galois#полиномы_над_gf_p ЗДЕСЬ)) ) примитивного элемента поля $ \mathbf{GF}(2^M) $, то, в соответствии с теоремой, он способен исправлять одну ошибку линейного $ (2^M-1,2^M-M-1) $-кода. Теперь сделаем несколько комментариев, позволяющих упростить вычисление полинома локаторов ошибок, а также "развить успех" в разных направлениях. 1. В соответствии с ((:gruppegalois:vspom3 теоремой Шёнеманна)), для любого полинома $ F_{}(x) $ над $ \mathbf{GF}(2) $ имеет место сравнение $ \left[F(x)\right]^2 \equiv F(x^2) \pmod{2} $. Тогда $$ \tilde G(\mathfrak A^2)=\left(\tilde G(\mathfrak A)\right)^2,\ \tilde G(\mathfrak A^4)=\left(\tilde G(\mathfrak A^2)\right)^2, \tilde G(\mathfrak A^6)=\left(\tilde G(\mathfrak A^3)\right)^2,\dots $$ Таким образом, вычислив значения $ \tilde G(\mathfrak A^j) $ для нечетных показателей $ j_{} $, значения $ \tilde G ( \mathfrak A^{2j}) $ получим возведением в квадрат уже вычисленного $ \tilde G(\mathfrak A^j) $. (Понаблюдайте проявление этого свойства в предыдущем примере). 2. Полином $ L_{}(x) $ раскладывается на линейные множители над полем $ \mathbf{GF}(2^M) $: $$ L(x) \equiv \sigma_{\ell}(x-\mathfrak A^{j_1})(x-\mathfrak A^{j_2})\times\dots \times (x-\mathfrak A^{j_{\ell}}) \ . $$ Величины $ \tilde G(\mathfrak A),\tilde G(\mathfrak A^2),\tilde G(\mathfrak A^3),\dots, \tilde G(\mathfrak A^{2\tau}) $ представляют суммы степеней его корней; такие суммы --- в случае полинома над $ \mathbb Q,\mathbb R $ или $ \mathbb C_{} $ --- называются ((:dets:discrim:waring суммами Ньютона)). Известно, что над этими полями коэффициенты полинома рационально выражаются через суммы Ньютона: если обозначить корни нормализованного полинома $$ L(x)=x^{\ell}+\sigma_{1}x^{\ell-1}+\sigma_{2}x^{\ell-2}+\dots+\sigma_{\ell} $$ через $ \lambda_1,\dots,\lambda_{\ell} $, а его $ k_{} $-ю сумму Ньютона через $ s_k=\lambda_1^k+\dots+\lambda_{\ell}^k $, то коэффициенты полинома $ L(x) $ выражаются через суммы Ньютона по следующим рекурсивным ((:dets:discrim:waring#обращение_формул_ньютона формулам Ньютона)): $$ \sigma_{1}=-s_1, 2\sigma_2=-(s_2+\sigma_1s_1), 3\sigma_3=-(s_3+\sigma_1s_2+\sigma_2s_1),\dots, $$ $$ k\sigma_k=-(s_{k}+\sigma_1s_{k-1}+\sigma_2s_{k-2}+\dots+\sigma_{k-1}s_1) \ npu \ k \le \ell. $$ В случае полинома $ L_{}(x) $ над $ \mathbf{GF}(2) $ эти формулы следует рассматривать по модулю $ 2_{} $ и формулы с четными номерами отбрасываются потому как являются следствиями предыдущих, а также комментария 1 . Следующее детерминантное представление полинома аналогично приведенному в конце ☞ ((:dets:discrim:waring#обращение_формул_ньютона ПУНКТА)) для полинома над бесконечными полями; для наглядности я приведу его для случая $ \ell = 4 $: $$ L(x)= \left| \begin{array}{lllll} \tilde G(\mathfrak A) & 1 & 0 & 0 & 0 \\ \tilde G(\mathfrak A^3) & \tilde G(\mathfrak A^2) & \tilde G(\mathfrak A) & 1 & 0 \\ \tilde G(\mathfrak A^5) & \tilde G(\mathfrak A^4) & \tilde G(\mathfrak A^3) & \tilde G(\mathfrak A^2) & \tilde G(\mathfrak A) \\ \tilde G(\mathfrak A^7) & \tilde G(\mathfrak A^6) & \tilde G(\mathfrak A^5) & \tilde G(\mathfrak A^4) & \tilde G(\mathfrak A^3) \\ x^4 & x^3 & x^2 & x & 1 \end{array} \right| $$ !!П!! **Пример.** Рассмотрим $ (15,5) $-код из предыдущего примера с порождающим полиномом $$ g(x)= x^{10}+x^8+x^5+x^4+x^2+x+1 \ . $$ Пусть при передаче некоторого кодового полинома на выходе канала связи оказался полином $$ \tilde G(x)= 1+x+x^4+x^7+x^8+x^9+x^{11}+x^{14} \ . $$ Примитивный элемент поля $ \mathbf{GF}(16) $ выбираем тем же, что и ранее: пусть $ \mathfrak A $ является корнем полинома $ x^4+x+1 $, входящего сомножителем в $ g_{}(x) $. Поскольку $$ \tilde G(\mathfrak A)=\mathfrak A+1 \ne \mathfrak o \ , $$ то при передаче по каналу произошла хотя бы одна ошибка. Положив начальной гипотезой наличие $ \ell=2 $ ошибок, строим полином: $$ L(x)= \left| \begin{array}{lll} \tilde G(\mathfrak A) & 1 & 0 \\ \tilde G(\mathfrak A^3) & \tilde G(\mathfrak A^2) & \tilde G(\mathfrak A) \\ x^2 & x & 1 \end{array} \right| =\left| \begin{array}{ccc} \mathfrak A+1 & 1 & 0 \\ \mathfrak A^3 & \mathfrak A^2+1 & \mathfrak A+1 \\ x^2 & x & 1 \end{array} \right|=(\mathfrak A+1)x^2+(\mathfrak A^2+1)x+(\mathfrak A^2+\mathfrak A+1) $$ Этот полином не имеет корней среди $ \{\mathfrak A^j\}_{j=0}^{14} $. Положив гипотезой наличие $ \ell=3 $ ошибок (максимального количества ошибок, возможного для исправления настоящим кодом), строим полином $$ L(x)= \left| \begin{array}{llll} \tilde G(\mathfrak A) & 1 & 0 & 0 \\ \tilde G(\mathfrak A^3) & \tilde G(\mathfrak A^2) & \tilde G(\mathfrak A) & 1 \\ \tilde G(\mathfrak A^5) & \tilde G(\mathfrak A^4) & \tilde G(\mathfrak A^3) & \tilde G(\mathfrak A^2) \\ x^3 & x^2 & x & 1 \end{array} \right| =\left| \begin{array}{cccc} \mathfrak A+1 & 1 & 0 & 0 \\ \mathfrak A^3 & \mathfrak A^2+1 & \mathfrak A+1 & 1 \\ 1 & \mathfrak A & \mathfrak A^3 & \mathfrak A^2+1 \\ x^3 & x^2 & x & 1 \end{array} \right|= $$ $$ =(\mathfrak A^2+\mathfrak A+1)x^3+(\mathfrak A^3+1)x^2+(\mathfrak A^3+\mathfrak A^2+\mathfrak A+1)x+\mathfrak A^2 \ . $$ Полином имеет корнями $ \mathfrak A^3, \mathfrak A^8,\mathfrak A^{11} $, следовательно ошибки произошли в коэффициентах при $ x^3, x^8 $ и $ x^{11} $, и кодовым полиномом является $$ G(x)=1+x+x^3+x^4+x^7+x^9+x^{14} \ . $$ ♦ 3. Основное требование к порождающему код полиному иметь корнями последовательность первых степеней примитивного элемента поля допускает модификации. Эти модификации касаются двух выражений: "первых степеней" и "примитивного элемента". Так, с одной стороны, можно потребовать от порождающего код полинома $ g_{}(x) $ обращения в нуль на последовательности степеней примитивного элемента поля $$ \mathfrak A^{m_0}, \mathfrak A^{m_0+1}, \mathfrak A^{m_0+2},\dots,\mathfrak A^{m_0+2\tau-1} \quad npu \quad m_0\ge 1,\ \tau \ge 2 \ , $$ не обязательно начинающейся с первой его степени. Небольшая модификация приведенного выше алгоритма исправления ошибок позволит применять его. С другой стороны, можно отказаться от требования примитивности элемента $ \mathfrak A $. Пусть ((:gruppe:galois:vspom2 порядок элемента)) $ \mathfrak B \in \mathbf{GF}(2^M) $ равен $ n_{} $. Тогда все его степени $$ \mathfrak B^0,\mathfrak B^1,\mathfrak B^2,\dots,\mathfrak B^{n-1} $$ будут различными элементами поля и локаторы ошибок $ n_{} $-разрядного кода позволят однозначно установить места ошибок. Таким образом, в этом случае мы уменьшаем количество разрядов кода с максимально возможного $ 2^M-1 $ до некоторого делителя этого числа. !!П!! **Пример.** Пусть $ M=6 $. Построить $ 21 $-разрядный код, исправляющий две ошибки. **Решение.** Поле $ \mathbf{GF}(2^6) $ исследовано ☞ ((:gruppe:galois:vspom1 ЗДЕСЬ)). Число $ 2^6-1=63 $ делится на $ 21 $, следовательно в $ \mathbf{GF}(2^6) $ существует элемент порядка $ 21 $, в качестве этого элемента можно взять произвольный корень полинома $ f_{6,2}(x)=x^6+x^5+x^4+x^2+1 $. Если обозначить корень этого полинома через $ \mathfrak B_{} $, то найдется такой примитивный элемент $ \mathfrak A \in \mathbf{GF}(2^6) $, что $ \mathfrak B =\mathfrak A^3 $. Если мы ставим целью подобрать полином $ g_{}(x) $ с корнями, среди которых имеются $ \mathfrak B, \mathfrak B^2, \mathfrak B^3,\mathfrak B^4 $, то все эти корни, кроме $ \mathfrak B^3 $, будут корнями $ f_{6,2}(x) $. Корень же $ \mathfrak B^3=\mathfrak A^9 $ будет корнем полинома $ x^3+x+1 $ (проверьте что именно его, а не двойственного ему $ x^3+x^2+1 $). Таким образом, полином $ g(x)=(x^6+x^5+x^4+x^2+1)(x^3+x+1)=x^9+x^8+x^5+x^4+x^2+x+1 $ порождает $ (21,12) $-циклический код, исправляющий две ошибки. ♦ ===Коды Рида-Соломона== В предыдущем пункте мы столкнулись с необходимостью рассмотрения полиномов относительно переменной $ x_{} $, коэффициентами которых оказывались не числа, а элементы поля Галуа $ \mathbf{GF}(2^M) $. Нам даже пришлось решать алгебраические уравнения, содержащие подобные полиномы[[Кстати, обнаружили, что они могут быть несовместными в $ \mathbf{GF}(2^M) $.]]. Если первоначальный шок от использования подобных объектов преодолен, то попробуем пойти и дальше --- допустим к рассмотрению в качестве порождающего циклический код полинома $ g_{}(x) $ не только полиномы с двоичными коэффициентами, но также и с коэффициентами из $ \mathbf{GF}(2^M) $. Начнем с формального обобщения **БЧХ**-кода, а уж практическое применение этого обобщения обсудим позже. !!П!! **Пример 1.** Рассмотрим код с порождающим полиномом равным $$ g(x)=(x-\mathfrak A)(x-\mathfrak A^2)(x-\mathfrak A^3)(x-\mathfrak A^4) $$ при $ \mathfrak A $ --- корне полинома $ f(x)= x^4+x+1 $. Перемножив линейные сомножители по модулю $ 2,f(x) $, получим представление порождающего полинома в виде $$ g(x)=x^4+(\mathfrak A^3+\mathfrak A^2+1)x^3+(\mathfrak A^3+\mathfrak A^2)x^2+\mathfrak A^3\,x+(\mathfrak A^2+\mathfrak A+1) \ , $$ которое --- с помощью таблицы, приведенной ☞ ((:gruppe:galois:vspom4 ЗДЕСЬ)) --- можно преобразовать к виду, когда коэффициентами мономов становятся степени примитивного элемента: $$ g(x)=x^4+\mathfrak A^{13}x^3+\mathfrak A^6\,x^2+\mathfrak A^3\,x+\mathfrak A^{10} ; $$ однако в дальнейших рассчетах более удобно именно первое представление. Пусть для передачи некоторого информационного вектора $ (x_1,x_2,\dots,x_{11}) \in \mathbb V^{11} $ используется ((:codes:cyclic#кодирование несистематическое кодирование)) и кодовым полиномом является $$ G(x)\equiv (x_1x^{10}+x_2\,x^9+\dots+x_{11}) g(x) \pmod{2} , $$ который при передаче по каналу связи преобразуется в $$ \tilde G(x) = x^{14}+(\mathfrak A^3+\mathfrak A^2+1)x^{13}+(\mathfrak A^3+\mathfrak A^2+1)x^{12}+(\mathfrak A^3+1)x^{11}+ $$ $$ +(\mathfrak A^2+\mathfrak A+1)x^{10}+(\mathfrak A^3+1)x^9+(\mathfrak A+1)x^8 +(\mathfrak A^3+\mathfrak A^2+\mathfrak A)x^7+ $$ $$ +(\mathfrak A^3+\mathfrak A+1)x^6+x^5+(\mathfrak A^2+1)x^4+(\mathfrak A^3+1)x^3+(\mathfrak A^3+\mathfrak A+1)x^2+\mathfrak A^3x+ $$ $$ +(\mathfrak A^2+\mathfrak A+1) \ , $$ предположительно содержащий две ошибки в коэффициентах, т.е. $$ \tilde G(x) \equiv G(x)+E_jx^j + E_kx^k \quad npu \quad \{j,k\} \subset \{0,1,2,\dots,14\},\ \{E_j,E_k\} \subset \mathbf{GF}(16) \ . $$ Акцентируем, что в данном случае, в отличие от предыдущего пункта, величины ошибок $ E_j $ и $ E_k $ являются элементами поля $ \mathbf{GF}(16) $, т.е. представляют собой выражения $ B_0+B_1\mathfrak A+B_2\mathfrak A^2+B_3\mathfrak A^3 $ при $ \{B_0,B_1,B_2,B_3\} \subset \{0,1\} $. Требуется восстановить информационный вектор. Действуя по сценарию ☞ ((#идея ПУНКТА)) и руководствуясь гипотезой о двух ошибках, составляем систему уравнений $$ \left\{ \begin{array}{lll} E_j \mathfrak A^j & + E_k \mathfrak A^k & = \tilde G(\mathfrak A), \\ E_j \mathfrak A^{2j} & + E_k \mathfrak A^{2k} & = \tilde G(\mathfrak A^2), \\ E_j \mathfrak A^{3j} & + E_k \mathfrak A^{3k} & = \tilde G(\mathfrak A^3), \\ E_j \mathfrak A^{4j} & + E_k \mathfrak A^{4k} & = \tilde G(\mathfrak A^4). \end{array} \right. $$ которую пытаемся решить относительно локаторов ошибок $ \mathfrak A^j, \mathfrak A^k $ и величин ошибок $ E_j, E_k $. Уравнение локаторов ошибок разыскивается в виде: $$ \left| \begin{array}{lll} \tilde G(\mathfrak A) & \tilde G(\mathfrak A^2) & \tilde G(\mathfrak A^3) \\ \tilde G(\mathfrak A^2) & \tilde G(\mathfrak A^3) & \tilde G(\mathfrak A^4) \\ 1 & x & x^2 \end{array} \right|= \left| \begin{array}{ccc} \mathfrak A^3+\mathfrak A^2+1 & \mathfrak A^3+\mathfrak A+1 & \mathfrak o \\ \mathfrak A^3+\mathfrak A+1 & \mathfrak o & \mathfrak A^3+\mathfrak A^2 \\ 1 & x & x^2 \end{array} \right|= \mathfrak o \ . $$ Поскольку $ \tilde G(\mathfrak A)\ne \mathfrak o $, то, крайней мере, одна ошибка имеется. Раскладываем определитель по последней строке: $$ (\mathfrak A^3+1)x^2+(\mathfrak A+1)x+(\mathfrak A^3+\mathfrak A^2+1) = \mathfrak o \ . $$ Корнями этого уравнения оказываются $ \mathfrak A^3 $ и $ \mathfrak A^{11} $. Таким образом, $ j=3, k=11 $, т.е. ошибки передачи по каналу содержатся в коэффициентах при $ x^{3} $ и $ x^{11} $. Величины ошибок $ E_3 $ и $ E_{11} $ находим из приведенной выше системы линейных уравнений, в которой коэффициенты нами теперь установлены: $$\left\{ \begin{array}{lllll} E_3 \mathfrak A^3&+E_{11}\mathfrak A^{11}&=\tilde G(\mathfrak A)&= \mathfrak A^3+\mathfrak A^2+1&=\mathfrak A^{13}, \\ E_3 \mathfrak A^6&+E_{11}\mathfrak A^{22}&=\tilde G(\mathfrak A^2)&= \mathfrak A^3+\mathfrak A+1&=\mathfrak A^{7}, \end{array} \right . $$ Решаем эту систему по ((:algebra2:linearsystems#матричный_формализм_метода_гаусса формулам Крамера)): $$ E_3=\frac{ \left| \begin{array}{ll} \mathfrak A^{13} & \mathfrak A^{11} \\ \mathfrak A^7 & \mathfrak A^{22} \end{array} \right| }{ \left| \begin{array}{ll} \mathfrak A^{3} & \mathfrak A^{11} \\ \mathfrak A^6 & \mathfrak A^{22} \end{array} \right| }=\frac{\mathfrak A^{35}+\mathfrak A^{18}}{\mathfrak A^{25}+\mathfrak A^{17}}=\frac{\mathfrak A^{5}+\mathfrak A^{3}}{\mathfrak A^{10}+\mathfrak A^{2}}=\frac{\mathfrak A^{11}}{\mathfrak A^{4}}=\mathfrak A^{7}=\mathfrak A^{3}+\mathfrak A+1 , $$ $$ E_{11}= \frac{\left| \begin{array}{ll} \mathfrak A^{3} & \mathfrak A^{13} \\ \mathfrak A^6 & \mathfrak A^{7} \end{array} \right| }{ \left| \begin{array}{ll} \mathfrak A^{3} & \mathfrak A^{11} \\ \mathfrak A^6 & \mathfrak A^{22} \end{array} \right| }=\mathfrak A^{3}+\mathfrak A^2+1 \ . $$ Таким образом, кодовый полином равен $$ G(x)\equiv \tilde G(x)+(\mathfrak A^{3}+\mathfrak A+1)x^3+(\mathfrak A^{3}+\mathfrak A^2+1)x^{11} \ , $$ его частное от деления на порождающий полином $ g_{}(x) $ равно $ x^{10}+x^8+x^7+x^6+x^3+x^2+1 $, т.е. информационным вектором является $ (10111001101) $. ♦ Итак, формальное обобщение двоичного **БЧХ**-кода из предыдущего пункта произведено. Порождающий код полином $ g_{}(x) $ оказывается делителем полинома $ x^{2^M-1} - 1 $, но только делителем не с двоичными коэффициентами, а с коэффициентами из $ \mathbf{GF}(2^M) $. Этот полином правильно исправляет ошибки, а его степень существенно меньше степени порождающего полинома двоичного **БЧХ**-кода, решающего ту же задачу. Правда, выражения для коэффициентов полинома становятся более сложными, но если уж мы принципиально решили связываться с формализмом полей Галуа, то упомянутое усложнение не кажется существенным. Коды, построенные по аналогии с разобранным в примере 1 случаем, также относят к **БЧХ**-кодам, но они имеют специальное название --- это **коды Рида-Соломона**[[Reed I.S., Solomon G.]]. В примере $ 1 $ в качестве порождающего код полинома рассматривался полином над полем $ \mathbf{GF}(16) $, в то время как собственно информационный полином, который был вычислен на последнем шаге, оказался полиномом над $ \mathbf{GF}(2) $. А что будет, если взять и в качестве информационного полинома не полином над $ \mathbf{GF}(2) $, а полином над $ \mathbf{GF}(16) $ ? !!П!! **Пример 2.** Рассмотрим код из предыдущего примера. Пусть информационный полином равен $$ P(x)=(\mathfrak A^3+\mathfrak A^2+1)x^{10}+(\mathfrak A^2+1)x^9+(\mathfrak A^3+\mathfrak A^2+\mathfrak A+1)x^8+\mathfrak A\,x^7+(\mathfrak A^2+\mathfrak A+1)x^6+ $$ $$ +(\mathfrak A^3+\mathfrak A^2+1)x^3 +(\mathfrak A+1)x^2+(\mathfrak A^3+1)\ . $$ Далее идем по проложенному в предыдущем примере пути. Используем несистематическое кодирование, получаем кодовый полином $$ G(x)\equiv P(x)g(x) \pmod{2} = $$ $$ =(\mathfrak A^3+\mathfrak A^2+1)x^{14}+(\mathfrak A^3+\mathfrak A+1)x^{13}+ \dots+ x^3+(\mathfrak A^3+\mathfrak A^2+\mathfrak A+1)x^2+\mathfrak A^2\,x+ $$ $$ +(\mathfrak A^3+\mathfrak A) \, $$ пересылаем по каналу, на выходе получаем испорченный полином $$ \tilde G(x)\equiv G(x)+(\mathfrak A^2+1)\,x^{13}+\mathfrak A^3\,x^3 = $$ $$ =(\mathfrak A^3+\mathfrak A^2+1)x^{14}+(\mathfrak A^3+\mathfrak A^2)x^{13}+ \dots+ (\mathfrak A^3+1)x^3+(\mathfrak A^3+\mathfrak A^2+\mathfrak A+1)x^2+\mathfrak A^2\,x+ $$ $$ +(\mathfrak A^3+\mathfrak A) \ , $$ т.е. снова оказываемся в ситуации наличия двух ошибок в коэффициентах при степенях $ x_{} $. Уравнение синдромов ошибок: $$ \left| \begin{array}{ccc} \mathfrak o & \mathfrak A^3+1 & \mathfrak A^3+\mathfrak A+1 \\ \mathfrak A^3+1 & \mathfrak A^3+\mathfrak A+1 & \mathfrak o \\ 1 & x & x^2 \end{array} \right|= \mathfrak o \ \iff \ (\mathfrak A^3+\mathfrak A^2+1)x^2+(\mathfrak A^3+\mathfrak A^2)x+(\mathfrak A^3+1) = \mathfrak o $$ имеет корнями правильные значения синдромов $ \mathfrak A^3 $ и $ \mathfrak A^{13} $. Величины ошибок системе уравнений $$\left\{ \begin{array}{llll} E_3 \mathfrak A^3&+E_{13}\mathfrak A^{13}&=\tilde G(\mathfrak A)&= \mathfrak o , \\ E_3 \mathfrak A^6&+E_{13}\mathfrak A^{26}&=\tilde G(\mathfrak A^2)&= \mathfrak A^3+1 \end{array} \right . $$ удовлетворяют. ♦ Теперь попробуем придать "физический смысл" приведенным примерам. Что такое информационный полином $ P(x) $ из примера 2? Если в примере 1 нас интересовали только коэффициенты подобного полинома --- именно эти двоичные цифры несли информацию, а собственно степени переменной $ x_{} $ нужны были исключительно для удобства преобразований --- то коэффициенты полинома $ P(x) $ из примера 2 являются не цифрами, а совсем даже ((http://lurkmore.ru/%D0%93%D0%BE%D1%82%D0%B8%D1%87%D0%BD%D0%BE готичными)) выражениями... :-? Реально мы имеем дело с полиномом от двух величин --- $ x_{} $ и $ \mathfrak A $. В общем случае полинома нескольких переменных над произвольным полем (не обязательно полем Галуа) --- его можно задать набором коэффициентов --- см. ☞ ((:polynomialm#общая_информация ЗДЕСЬ)). Что можно сказать о потенциально возможном виде полинома $ P(x,\mathfrak A) $, который можно было взять в качестве информационного в примере 2? Он подчиняется следующим ограничениям на степени: $$ \deg_x P< 15, \deg_{\mathfrak A} P< 4 \ ; $$ последняя оценка накладывается степенью порождающего код полинома $ g(x,\mathfrak A) $. Для однозначного задания полинома при таких ограничениях требуются $ 15 \times 4=60 $ коэффициентов --- и этими коэффициентами являются числа $ 0_{} $ и $ 1_{} $. Кое-что начинает проясняться ;-): нас интересуют не коэффициенты при степенях $ x_{} $, а при степенях мономов $ x^k \mathfrak A^{\ell} $! Таким образом, в информационном полиноме $ P(x,\mathfrak A) $ заложена информация о $ 60 $ его коэффициентах. Эти коэффициенты можно записать в последовательность (договорившись предварительно о способе ((:polynomialm#общая_информация упорядочения мономов)) ). Представим этот массив не одномерным: $$ \begin{array}{ccccccc} x^{10} \mathfrak A^{3} & x^{10} \mathfrak A^{2} & x^{10} \mathfrak A & x^{10} & x^{9} \mathfrak A^{3} & x^{9} \mathfrak A^{2} & \dots \\ 1 & 1 & 0 & 1 & 0 & 1 & \dots , \end{array} $$ а двумерным --- т.е. рассмотрим ((:algebra2#определение_обозначения матрицу)). Фактически, полином уже представлен в виде, из которого матрица извлекается мгновенно: $$ \begin{array}{cc} & x^{10}\, x^9 \ x^8 \ x^7 \ x^6 \ x^5 \ x^4 \ x^3 \ \ x^2 \ x \ 1 \\ & \downarrow \ \ \downarrow \ \ \ \downarrow \ \ \downarrow \ \ \downarrow \ \ \ \downarrow \ \ \ \downarrow \ \ \downarrow \ \ \ \downarrow \ \ \downarrow \ \ \downarrow \\ \begin{array}{ll} \mathfrak A^{3} & \rightarrow \\ \mathfrak A^{2} & \rightarrow \\ \mathfrak A^{3} & \rightarrow \\ 1 & \rightarrow \\ \end{array} & \left[ \begin{array}{ccccccccccc} 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1&1&1&0&1&0&0&1&0&0&0 \\ 0&0&1&1&1&0&0&0&1&0&0 \\ 1&1&1&0&1&0&0&1&1&0&1 \end{array} \right] \end{array} $$ Кодовый полином $ G_{}(x) $ и результат его передачи по каналу связи --- полином $ \tilde G(x) $ также можно представить в аналогичном виде: {{ codes:cyclic:reedsal.jpg |}} В $ 60 $-битном кодовом слове при передаче произошли __три__ ошибки, но в примере 2 они исправлялись по алгоритму, который изначально "заточен" под ситуацию __двух__ ошибок! Почему этот алгоритм отработал правильно? Объяснение заключается в том, что две из трех произошедших ошибок оказались компактно расположенными в одном столбце информационной таблицы[[Он официально называется **полубайтом**, но я не буду здесь множить определения.]]. Кодирование этого столбца производится с помощью одного-единственного элемента поля $ \mathbf{GF}(16) $; повреждение любого количества битов внутри этого столбца оказывается эквивалентным простой замене истинного элемента поля на другой элемент поля. И тогда алгоритм БЧХ нахождения синдромов ошибок реагирует на все произошедшие внутри столбца изменения как на единичную ошибку. Такая возможность "упаковки" ошибок весьма существенна для практики: дело в том, что ошибки передачи часто имеют обыкновение происходить серией[[Беда не приходит одна.]]. Поэтому применение кодов Рида-Соломона очень распространено --- причем не только в задачах исправления ошибок, но и восстановления потерянных данных; подробнее см. ☞ ((:codes:raid ЗДЕСЬ)). ==Источники== [1]. **Питерсон У., Уэлдон Э.** //Коды, исправляющие ошибки.// М.Мир. 1976.