Здесь ровно три ошибки

Другие вопросы

В какой игре существует обвес оружия?

У менякомп интел коре 2 дуо, 2 гига оперативки, стоит XP,ПОСТАВЛЮ сЕМЕРКУ директ закачаю 11, потянет его? Видеоадаптер

Оскорбил врач, на медкомиссии. Есть управа на него?

где взять серийный номер для adobe photoshop

как избавится от восполеных прыщей в дом. условиях

Как можно создать такую картинку или что-то типо этого?

Почему лагает PoinT BlanK??? я блин уже 3 раз задаю этот вопрос тут.

Что мне нужно знать чтобы купить процессор?

Есть у когонить рабочие читы на сегодняшний день Warface. Благодарю.

сильный кашель, как остановить

помогите пожалуйста зайти в настройки модема

Где находятся почки и что будет если по ним ударить?

Как самому выявить у себя мерцательную аритмию? Каковы симптомы?

Вопрос по игре point blank.

Для ее пояснения обратимся к материалам

☞

ПУНКТА и рассмотрим циклические коды в $ 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_jlambda_1^j+E_klambda_1^k= tilde G(lambda_1), E_jlambda_2^j+E_klambda_2^k= tilde G(lambda_2), E_jlambda_3^j+E_klambda_3^k= tilde G(lambda_3), E_jlambda_4^j+E_klambda_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{2pi}{n}+mathbf i sin frac{2pi}{n} $$
— корне степени n из единицы. Посмотрим как можно использовать эту возможность для решения задачи исправления ошибок. Подставим корни в предыдущую систему, воспользовавшись равенствами
$$ varepsilon_1^j = varepsilon_j=cos frac{2pi,j}{n}+mathbf i sin frac{2pi , j}{n} , varepsilon_1^k=varepsilon_k= cos frac{2pi,k}{n}+mathbf i sin frac{2pi,k}{n} , $$
получим «систему ошибок»¹⁾
$$
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_1varepsilon_j+sigma_0varepsilon_j^2&=0, & times E_j varepsilon_j & & times E_j varepsilon_j^2 &
& & & + & & +
sigma_2+sigma_1varepsilon_k+sigma_0varepsilon_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_2tilde G(varepsilon_1)+sigma_1tilde G(varepsilon_1^2)+sigma_0tilde G(varepsilon_1^3)&=0,
sigma_2tilde G(varepsilon_1^2)+sigma_1tilde G(varepsilon_1^3)+sigma_0tilde 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 $ применяем критерий существования нетривиального решения: определитель этой системы должен быть равен нулю.

♦

В следующем пункте я часто буду употреблять подобные детерминантные представления, нетрадиционные для теории кодирования. В последней обычно разыскивают полином ошибочных позиций в виде нормализованного полинома — со старшим коэффициентом равным $ 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) $. Действительно, при любом $ nin mathbb N $ полином $ X_n(x) $ будет иметь корнем $ varepsilon_1 $, равно как и любой другой первообразный корень степени $ n_{} $. Тогда при $ nge 5 $ и $ n_{} $ — простом, все степени $ {varepsilon_1^j}_{j=1}^{n-1} $ будут первообразными корнями степени $ n_{} $, и, следовательно, будут корнями полинома $ X_n(x) $. В этом случае можно было бы взять $ g(x)equiv X_n(x) $, однако, хотя с формальной точки зрения это и допустимо, тем не менее, с точки зрения практической пользы такой вариант бессмыслен: при любом способе кодирования в циклическом коде размерность кодового пространства $ mathbb U $ становится равной $ 1_{} $, т.е. в $ n_{} $-кодовом слове остается единственный свободный разряд, который можно использовать в качестве информационного.

Итак, число $ nge 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 $$
$$ 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{2pi}{15}+mathbf i sin frac{2pi}{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_2approx 0.669131-0.743145, mathbf i . $$
Если при передаче по каналу произошли — как утверждается в условии — ровно две ошибки, то получившиеся значения должны быть корнями $ 15 $-й степени из единицы. Это немедленно проверяется. Остается выяснить каким значениям показателей $ varepsilon_j $ и $ varepsilon_k $ соответствуют эти числа.
$$ 15 arccos(-0.104528)/(2pi) approx 4 quad mbox{ и } quad 0.994522>0 quad Rightarrow j=4 . $$
$$ 15 arccos(0.669131)/(2pi) 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_4approx -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
$$
вырождается в тождество $ 0equiv 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 muapprox -0.978148+0.207912 , mathbf i .
$$
Далее идем как в предыдущем случае: действительно, $ mu^{15} = 1 $ и
$$ 15 arccos(-0.978148)/(2pi) 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_jvarepsilon_j+E_kvarepsilon_k+E_svarepsilon_s & E_jvarepsilon_j^2+E_kvarepsilon_k^2+E_svarepsilon_s^2 &
E_jvarepsilon_j^3+E_kvarepsilon_k^3+E_svarepsilon_s^3
E_jvarepsilon_j^2+E_kvarepsilon_k^2+E_svarepsilon_s^2 &
E_jvarepsilon_j^3+E_kvarepsilon_k^3+E_svarepsilon_s^3 &
E_jvarepsilon_j^4+E_kvarepsilon_k^4+E_svarepsilon_s^4
E_jvarepsilon_j^3+E_kvarepsilon_k^3+E_svarepsilon_s^3 &
E_jvarepsilon_j^4+E_kvarepsilon_k^4+E_svarepsilon_s^4 &
E_jvarepsilon_j^5+E_kvarepsilon_k^5+E_svarepsilon_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_jvarepsilon_kvarepsilon_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_jvarepsilon_kvarepsilon_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} $ в уравнении ошибочных позиций отличен от нуля и уравнение не обращается в тривиальное тождество $ 0equiv 0 $.

Хочется развить этот успех на случай произвольного количества ошибок. К сожалению, на пути исполнения этого желания стоит препятствием уже упомянутое ранее ограничение на степень $ n_{} $. При фиксировании этого числа, добавление в состав кодового полинома $ g_{}(x) $ новых сомножителей из числа полиномов $ X_{ell} (x) $ уменьшает количество информационных разрядов.

Будем строить двоичный циклический $ n_{} $-разрядный код для случая $ n=2^M-1, Min mathbb N $. Основываясь на идее предыдущего пункта, будем строить его на основе порождающего полинома $ g_{}(x) $, имеющего корнями последовательные степени примитивного элемента поля Галуа $ mathfrak A in mathbf{GF}(2^M) $:
$$ mathfrak A, mathfrak A^2, mathfrak A^3,dots,mathfrak A^{2tau} 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}^{2tau} $. Строго говоря, определим $ g_{}(x) $ равенством
$$ g(x)equiv operatorname{HOK}(f_1,f_2,dots,f_{2tau}) , $$
где $ 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}^{2tau} $, где $ 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}^{2tau} $ полинома $ 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^{2tau})&= mathfrak A^{2tau 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}^{2tau} $, где $ 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^{2ell})
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} $ равен³⁾
$$
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 $, и это⁴⁾ свидетельствует о том, что количество ошибок не может равняться $ 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} . $$

♦

Построенный выше двоичный код является примером кода Боуза-Чоудхури-Хоквингема⁵⁾ или БЧХ-кода. Его кодовое расстояние не превосходит величины
$$ d_0=1+2tau , $$
которая называется конструктивным расстоянием БЧХ-кода. Число $ 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})timesdots 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^{2tau}) $ представляют суммы степеней его корней; такие суммы — в случае полинома над $ 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, 2sigma_2=-(s_2+sigma_1s_1), 3sigma_3=-(s_3+sigma_1s_2+sigma_2s_1),dots,
$$
$$
ksigma_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+2tau-1} quad npu quad m_0ge 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) $. Нам даже пришлось решать алгебраические уравнения, содержащие подобные полиномы⁶⁾. Если первоначальный шок от использования подобных объектов преодолен, то попробуем пойти и дальше — допустим к рассмотрению в качестве порождающего циклический код полинома $ 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) ,
$$
которое — с помощью таблицы, приведенной

☞

ЗДЕСЬ — можно преобразовать к виду, когда коэффициентами мономов становятся степени примитивного элемента:
$$
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_1mathfrak A+B_2mathfrak A^2+B_3mathfrak 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 ,
$$
$$
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 случаем, также относят к БЧХ-кодам, но они имеют специальное название — это коды Рида-Соломона⁷⁾.

В примере $ 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 являются не цифрами, а совсем даже готичными выражениями… Реально мы имеем дело с полиномом от двух величин — $ 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 они исправлялись по алгоритму, который изначально «заточен» под ситуацию двух ошибок! Почему этот алгоритм отработал правильно? Объяснение заключается в том, что две из трех произошедших ошибок оказались компактно расположенными в одном столбце информационной таблицы . Кодирование этого столбца производится с помощью одного-единственного элемента поля $ mathbf{GF}(16) $; повреждение любого количества битов внутри этого столбца оказывается эквивалентным простой замене истинного элемента поля на другой элемент поля. И тогда алгоритм БЧХ нахождения синдромов ошибок реагирует на все произошедшие внутри столбца изменения как на единичную ошибку.

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

☞

ЗДЕСЬ.

Thomas de Mahy

Louis XVI

Marie Antoinette Queen of France with her three eldest children

Favras Family

The execution of the Marquis de Favras on February 19, 1790 in Paris

Thomas de Mahy

Louis XVI

Marie Antoinette Queen of France with her three eldest children

Favras Family

The execution of the Marquis de Favras on February 19, 1790 in Paris