УказательРазделыОбозначенияАвторО проекте


{.} Настоящий раздел поддерживается компанией


§

Для понимания материалов настоящего раздела крайне желательно ознакомиться с разделом ☞ ЦИКЛИЧЕСКИЕ КОДЫ.


Коды Боуза-Чоудхури-Хоквингема

Идея

Для ее пояснения обратимся к материалам ☞ ПУНКТА и рассмотрим циклические коды в \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<n,a_{r}\ne 0), равносильна тому, что полином G(x)=b_0+b_1x+b_2x^2+\dots+b_{n-1}x^{n-1} делится на g_{}(x). Предположим теперь, что при передаче по зашумленному каналу связи кодовый полином (кодовое слово) исказился и на выходе мы получили полином

\tilde G(x)= G(x)+E_jx^j+E_kx^k \quad npu \quad \{j,k\} \subset \{0,1,2,\dots,n-1\},\ j < k,\ \{E_j,E_k\} \subset \mathbb Z \ .

В ☞ ПУНКТЕ предлагался метод нахождения ошибок в случае, когда они соседствуют, т.е. k=j+1. Фактически, задача в такой постановке оказывалась задачей с тремя неизвестными: требовалось найти место ошибки j_{} и величины ошибок E_j,E_{j+1}. Теперь мы рассмотреть общий случай, когда неизвестными являются четыре величины j,k,E_j,E_k. Интуитивно понятно, что для нахождения этих четырех неизвестных требуется, по меньшей мере, такое же количество условий. По аналогии с рассмотренным в ☞ ПУНКТЕ подходом, будем пытаться найти эти условия виде \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}

корне степени 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} \ ,

получим «систему ошибок»1)

\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, удовлетворяют «уравнению ошибочных позиций»2)

\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 применяем критерий существования нетривиального решения: определитель этой системы должен быть равен нулю.

§

В следующем пункте я часто буду употреблять подобные детерминантные представления, нетрадиционные для теории кодирования. В последней обычно разыскивают полином ошибочных позиций в виде нормализованного полинома — со старшим коэффициентом равным 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. По аналогии с подходом ☞ ПУНКТА можно попробовать выбрать полином g_{}(x) как произведение полиномов деления круга 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), однако, хотя с формальной точки зрения это и допустимо, тем не менее, с точки зрения практической пользы такой вариант бессмыслен: при любом способе кодирования в циклическом коде размерность кодового пространства \mathbb U становится равной 1_{}, т.е. в n_{}-кодовом слове остается единственный свободный разряд, который можно использовать в качестве информационного.

Итак, число n\ge 5 должно быть составным. Пусть n_{}— нечетно. Тогда (см. ☞ ЗДЕСЬ) величины \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 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 и \quad 0.994522>0 \quad \Rightarrow j=4 \ .
15 \arccos(0.669131)/(2\pi) \approx 2 \quad и \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 и \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| \ .

Этот определитель относится к типу ганкелевых; для его вычисления представим его в виде определителя произведения трех матриц

\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\} \ .

Применение теоремы Бине-Коши сводит вычисление этого определителя к произведению определителей составляющих матриц. Определитель первой матрицы является определителем Вандермонда

\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), имеющего корнями последовательные степени примитивного элемента поля Галуа \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, приведенной ☞ ЗДЕСЬ, корнями этого же полинома будут и величины \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} означает наименьшее общее кратное неприводимых над \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 (см. разбор ☞ ЗДЕСЬ). Возьмем 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_{} проверочных. Иными словами, этот линейный код является (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). Кодирование передаваемой информации производится любым из способов, принятых в циклических кодах.

Покажем, что такой код способен исправить от одной до \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, приведенной ☞ ЗДЕСЬ.

\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} равен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, и это4) свидетельствует о том, что количество ошибок не может равняться 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} \ .

Построенный выше двоичный код является примером кода Боуза-Чоудхури-Хоквингема5) или БЧХ-кода. Его кодовое расстояние не превосходит величины

d_0=1+2\tau \ ,

которая называется конструктивным расстоянием БЧХ-кода. Число k_{} информационных символов БЧХ-кода и, соответственно, число n-k=2^M-k-1 проверочных символов зависит от степеней множителей полинома g_{}(x) — неприводимых по модулю 2_{} полиномов.

=>

Код Хэмминга является частным случаем БЧХ-кода, он соответствует случаю \tau=1. В этом случае кодовым полиномом берется просто произвольный примитивный полином — поскольку его корнями обязательно будут две последовательные степени \mathfrak A и \mathfrak A^2 (см. теорему 1 ☞ ЗДЕСЬ ) примитивного элемента поля \mathbf{GF}(2^M), то, в соответствии с теоремой, он способен исправлять одну ошибку линейного (2^M-1,2^M-M-1)-кода.

Теперь сделаем несколько комментариев, позволяющих упростить вычисление полинома локаторов ошибок, а также «развить успех» в разных направлениях.

1. В соответствии с теоремой Шёнеманна, для любого полинома 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_{} — называются суммами Ньютона. Известно, что над этими полями коэффициенты полинома рационально выражаются через суммы Ньютона: если обозначить корни нормализованного полинома

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) выражаются через суммы Ньютона по следующим рекурсивным формулам Ньютона:

\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 . Следующее детерминантное представление полинома аналогично приведенному в конце ☞ ПУНКТА для полинома над бесконечными полями; для наглядности я приведу его для случая \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. Пусть порядок элемента \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) исследовано ☞ ЗДЕСЬ. Число 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). Нам даже пришлось решать алгебраические уравнения, содержащие подобные полиномы6). Если первоначальный шок от использования подобных объектов преодолен, то попробуем пойти и дальше — допустим к рассмотрению в качестве порождающего циклический код полинома g_{}(x) не только полиномы с двоичными коэффициентами, но также и с коэффициентами из \mathbf{GF}(2^M).

Начнем с формального обобщения БЧХ-кода, а уж практическое применение этого обобщения обсудим позже.

П

Пример 1. Рассмотрим код с порождающим полиномом равным

g(x)=(x-\mathfrak A)(x-\mathfrak A^2)(x-\mathfrak A^3)(x-\mathfrak A^4) \quad при \quad \mathfrak A \ - \quad корне полинома \quad 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) \ ,

которое — с помощью таблицы, приведенной ☞ ЗДЕСЬ — можно преобразовать к виду, когда коэффициентами мономов становятся степени примитивного элемента:

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} используется несистематическое кодирование и кодовым полиномом является

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 .

Решаем эту систему по формулам Крамера:

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 , \quad 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 случаем, также относят к БЧХ-кодам, но они имеют специальное название — это коды Рида-Соломона7).

В примере 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 \quad \iff \quad (\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 являются не цифрами, а совсем даже готичными выражениями… :-? Реально мы имеем дело с полиномом от двух величин — x_{} и \mathfrak A. В общем случае полинома нескольких переменных над произвольным полем (не обязательно полем Галуа) — его можно задать набором коэффициентов — см. ☞ ЗДЕСЬ. Что можно сказать о потенциально возможном виде полинома 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 его коэффициентах. Эти коэффициенты можно записать в последовательность (договорившись предварительно о способе упорядочения мономов ). Представим этот массив не одномерным:

\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}

а двумерным — т.е. рассмотрим матрицу. Фактически, полином уже представлен в виде, из которого матрица извлекается мгновенно:

\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) также можно представить в аналогичном виде:

В 60-битном кодовом слове при передаче произошли три ошибки, но в примере 2 они исправлялись по алгоритму, который изначально «заточен» под ситуацию двух ошибок! Почему этот алгоритм отработал правильно? Объяснение заключается в том, что две из трех произошедших ошибок оказались компактно расположенными в одном столбце информационной таблицы8). Кодирование этого столбца производится с помощью одного-единственного элемента поля \mathbf{GF}(16); повреждение любого количества битов внутри этого столбца оказывается эквивалентным простой замене истинного элемента поля на другой элемент поля. И тогда алгоритм БЧХ нахождения синдромов ошибок реагирует на все произошедшие внутри столбца изменения как на единичную ошибку.

Такая возможность «упаковки» ошибок весьма существенна для практики: дело в том, что ошибки передачи часто имеют обыкновение происходить серией9). Поэтому применение кодов Рида-Соломона очень распространено — причем не только в задачах исправления ошибок, но и восстановления потерянных данных; подробнее см. ☞ ЗДЕСЬ.

Источники

[1]. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. М.Мир. 1976.

1) Это название — мое изобретение, Шекспиром навеянное — за пределами настоящего пункта не используется; все канонические определения содержатся в следующем пункте.
2) Снова доморощенное определение…
3) Пока не решил, какое из представлений элементов поля Галуа более удобно для счёта определителей, привожу оба варианта.
4) На самом деле, L(x) тождественно равен \mathfrak o, но этот факт совершенно не существен для последующего.
5) Bose R.C., Ray-Chaudhury D.K., Hocquenghem A.
6) Кстати, обнаружили, что они могут быть несовместными в \mathbf{GF}(2^M).
7) Reed I.S., Solomon G.
8) Он официально называется полубайтом, но я не буду здесь множить определения.
9) Беда не приходит одна.

2017/02/28 19:12 редактировал au