Сколько ошибок исправляет код бчх

Содержание

• 1 Исправление ошибок в помехоустойчивом кодировании
• 2 Параметры помехоустойчивого кодирования
• 3 Контроль чётности
• 4 Классификация помехоустойчивых кодов
• 5 Код Хэмминга
  • 5.1 Декодирование кода Хэмминга
  • 5.2 Расстояние Хэмминга
• 6 Помехоустойчивые коды
  • 6.1 Компромиссы при использовании помехоустойчивых кодов
  • 6.2 Необходимость чередования (перемежения)

Коды Боуза — Чоудхури — Хоквингхема (БЧХ-коды) — в теории кодирования это широкий класс циклических кодов, применяемых для защиты информации от ошибок (см. Обнаружение и исправление ошибок). Отличается возможностью построения кода с заранее определенными корректирующими свойствами, а именно, минимальным кодовым расстоянием. Коды Рида — Соломона являются частным случаем БЧХ-кодов.

Формальное описание

БЧХ-код является циклическим кодом, который можно задать порождающим полиномом. Для его нахождения в случае БЧХ-кода необходимо заранее определить длину кода n (она не может быть произвольной) и требуемое минимальное расстояние . Найти порождающий полином можно следующим образом.

Пусть α — примитивный элемент поля GF(q^m) (то есть ), пусть β = α^s, — элемент поля GF(q^m) порядка . Тогда нормированный полином g(x) минимальной степени над полем GF(q), корнями которого являются d − 1 подряд идущих степеней элемента β для некоторого целого l₀ (в том числе 0 и 1), является порождающим полиномом БЧХ-кода над полем GF(q) с длиной n и минимальный расстоянием .

Число проверочных символов r равно степени g(x), число информационных символов k = n − r, величина d называется конструктивным расстоянием БЧХ-кода. Если n = q^m − 1, то код называется примитивным, иначе непримитивным.

Так же, как и для циклического кода, кодовый полином c(x) может быть получен из информационного полинома m(x), степени не больше k − 1, путем перемножения m(x) и g(x):

c(x) = m(x)g(x).

Построение

Для нахождения порождающего полинома необходимо выполнить несколько этапов:

• выбрать q, то есть поле GF(q), над которым будет построен код;
• выбрать длину n кода из условия n = (q^m − 1) / s, где m,s — целые положительные числа;
• задать величину d конструктивного расстояния;

1) построить циклотомические классы элемента β = α^s поля GF(q^m) над полем GF(q), где α — примитивный элемент GF(q^m);

2) поскольку каждому такому циклотомическому классу соответвует неприводимый полином над GF(q), корнями которого являются элементы этого и только этого класса, со степенью равной количеству элементов в классе, то выбрать таким образом, чтобы суммарная длина циклотомических классов была минимальна

3) вычислить порождающий полином , где f_i(x) — полином, соответсвующий i-ому циклотомическому классу

Примеры кодов

Примитивный 2-ичный (15,7,5) код

Пусть q = 2, требуемая длина кода n = 2⁴ − 1 = 15 и минимальное расстояние . Возьмем α — примитивный элемент поля GF(16), и α,α²,α³,α⁴ — четыре подряд идущих степеней элемента α. Они принадлежат двум циклотомическим классам над полем GF(2), которым соответсвуют неприводимые полиномы f₁(x) = x⁴ + x + 1 и f₂(x) = x⁴ + x³ + x² + x + 1. Тогда полином

g(x) = f₁(x)f₂(x) = x⁸ + x⁷ + x⁶ + x⁴ + 1

имеет в качестве корней элементы α,α²,α³,α⁴ и является порождающим полиномом БЧХ-кода с параметрами (15,7,5).

16-ричный (15,11,5) код (код Рида — Соломона)

Пусть n = q − 1 = 15 и α — примитивный элемент GF(16). Тогда

g(x) = (x − α)(x − α²)(x − α³)(x − α⁴) = x⁴ + α¹³x³ + α⁶x² + α³x + α¹⁰

.

Каждому элементу поля GF(16) можно сопоставить 4 битам, поэтому одно кодовое слово эквивалентно 60=15*4 битам, таким образом набору из 44 бит ставится в соответствие набор из 60 бит. Можно сказать, что такой код работает с полубайтами информации.

Кодирование

Для кодирования кодами БЧХ применяются те же методы, что и для кодирования циклическими кодами.

Методы декодирования

Коды БЧХ являются циклическими кодами, поэтому к ним применимы все методы, используемые для декодирования циклических кодов. Однако существуют гораздо лучшие алгоритмы, разработанные именно для БЧХ-кодов.

Исторически первым методом декодирования был найден Питерсоном для двоичного случая (q = 2), затем Горенстейном и Цирлером для общего случая. Упрощение алгоритма было найдено Берлекэмпом, а затем усовершенствовано Месси (алгоритм Берлекэмпа — Месси). Существует отличный от этих методов декдирования — метод основанный на алгоритме Евклида.

Алгоритм Питерсона — Горенстейна — Цирлера (ПГЦ)

Пусть БЧХ код над полем GF(q) длины n и с конструктивным расстоянием d задается порождающим полиномом g(x), который имеет среди своих корней элементы ,  — целое число (например 0 или 1). Тогда каждое кодовое слово обладает тем свойством, что . Принятое слово r(x) можно записать как r(x) = c(x) + e(x), где e(x) — полином ошибок. Пусть произошло ошибок на позициях (t максимальное число исправляемых ошибок), значит , а  — величины ошибок.

Можно составить j-ый синдром S_j принятого слова r(x):

.

Задача состоит в нахождений числа ошибок u, их позиций и их значений при известных синдромах S_j.

Предположим, для начала, что u в точности равно t. Запишем (1) в виде системы нелинейных(!) уравнений в явном виде:

Обозначим через локатор k-ой ошибки, а через величину ошибки, . При этом все X_k различны, так как порядок элемента β равен n, и поэтому при известном X_k можно определить i_k как i_k = log_βX_k.

Составим полином локаторов ошибок:

Корнями этого полинома являются элементы, обратные локаторам ошибок. Помножим обе части этого полинома на . Полученное равенство будет справедливо для :

Положим и подставим в (3). Получится равенство, справедливое для каждого и при всех :

Таким образом для каждого l можно записать свое равенство. Если их просуммировать по l, то получиться равенство, справедливое для каждого :

.

.

Учитывая (2) и то, что (то есть меняется в тех же пределах, что и ранее) получаем систему линейных уравнений:

.

Или в матричной форме

,

где

Если число ошибок и в самом деле равно t, то система (4) разрешима, и можно найти значения коэффициентов . Если же число u < t, то определитель матрицы S^(t) системы (4) будет равен 0. Это есть признак того, что количество ошибок меньше t. Поэтому необходимо составить систему (4), предполагая число ошибок равным t − 1. Высчитать определитель новой матрицы S^{(t − 1)} и т. д., до тех пор, пока не установим истинное число ошибок.

После этого можно решить систему (4) и получить коэффициенты полинома локаторов ошибок. Его корни (элементы, обратные локаторам ошибок) можно найти простым перебором по всем элементам поля GF(q^m). К ним найти элементы, обратные по умножению, — это локаторы ошибок . По локаторам можно найти позиции ошибок (i_k = log_βX_k), а значения Y_k ошибок из системы (2), приняв t = u. Декодирование завершено.

См. также

• Обнаружение и исправление ошибок
• Конечное поле
• Многочлен над конечным полем
• Матрица Вандермонда
• Линейный код
• Циклический код
• Код Рида — Соломона

Литература

• Блейхут Р. Теория и практика кодов, контролирующих ошибки = Theory and practice of error control codes. — М.: Мир, 1986. — С. 576.

• Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. — М.: Мир, 1976. — С. 596.

3.1. КОДЫ БЧХ, ИСПРАВЛЯЮЩИЕ ДВЕ ОШИБКИ (I)

Известно из гл. 1, что коды Хэмминга исправляют одиночные ошибки. В этой главе будут введены коды, которые в определенном смысле обобщают их на случай ошибок и называются кодами Боуза-Чоудхури-Хоквингема (или, кратко, кодами БЧХ). в этой же главе мы введем одну из центральных тем теории кодирования, а именно теорию конечных полей.

Попытаемся вначале найти обобщение кодов Хэмминга, позволяющее исправлять две ошибки.

Двоичный код Хэмминга длины должен иметь проверочных символов, чтобы исправлять одну ошибку. Естественное предположение состоит в том, что для исправления двух ошибок необходимо проверочных символов. Итак, попытаемся построить проверочную матрицу кода, исправляющего две ошибки, добавляя еще строк к проверочной матрице кода Хэмминга.

В качестве примера возьмем Тогда матрица имеет своими столбцами все возможные ненулевые -векторы:

что мы сокращенно обозначим как

где через число обозначен соответствующий ему двоичный 4-вектор. Мы собираемся добавить к еще 4 строки, например таким способом

где значением функции также является вектор длины 4 из нулей и единиц. Поэтому столбец матрицы

представляет собой вектор-столбец длины 8.

Как выбрать функцию Предположим, что произошли две ошибки — на позициях Тогда (по теореме 4 гл. 1) синдром равен

Необходимо выбрать так, чтобы декодер по мог найти т. е. чтобы он мог одновременно решить уравнения

относительно при заданных При этом все эти элементы являются векторами длины

Для того чтобы решить эти уравнения, нам хотелось бы уметь складывать, вычитать, умножать и делить эти -векторы. Другими словами, мы хотим, чтобы эти -векторы образовывали поле. Вначале опишем построение этого поля, а затем вернемся к проблеме построения кодов, исправляющих две ошибки.

Определение. Поле — это множество элементов в котором определены операции сложения, вычитания, умножения и деления (за исключением деления на 0, которое не определено). Сложение и умножение должны удовлетворять коммутативному, ассоциативному и дистрибутивному законам: для любых элементов у в этом поле должны выполняться соотношения а

кроме того, должны существовать элементы 0, 1 (и для любого а) такие, что

Конечное поле содержит конечное число элементов, и это число называется порядком поля.

Конечные поля называются полями Галуа по имени их первого исследователя Эвариста Галуа.

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

☞

ПУНКТА и рассмотрим циклические коды в $ 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) $; повреждение любого количества битов внутри этого столбца оказывается эквивалентным простой замене истинного элемента поля на другой элемент поля. И тогда алгоритм БЧХ нахождения синдромов ошибок реагирует на все произошедшие внутри столбца изменения как на единичную ошибку.

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

☞

ЗДЕСЬ.

A block code (specifically a Hamming code) where redundant bits are added as a block to the end of the initial message

A continuous code convolutional code where redundant bits are added continuously into the structure of the code word

A short illustration of interleaving idea

1. ^ Charles Wang; Dean Sklar; Diana Johnson (Winter 2001–2002). «Forward Error-Correction Coding». Crosslink. The Aerospace Corporation. 3 (1). Archived from the original on 14 March 2012. Retrieved 5 March 2006.
2. ^ Charles Wang; Dean Sklar; Diana Johnson (Winter 2001–2002). «Forward Error-Correction Coding». Crosslink. The Aerospace Corporation. 3 (1). Archived from the original on 14 March 2012. Retrieved 5 March 2006. How Forward Error-Correcting Codes Work]
3. ^ ^{a b} Maunder, Robert (2016). «Overview of Channel Coding».
4. ^ Glover, Neal; Dudley, Trent (1990). Practical Error Correction Design For Engineers (Revision 1.1, 2nd ed.). CO, USA: Cirrus Logic. ISBN 0-927239-00-0.
5. ^ ^{a b} Hamming, Richard Wesley (April 1950). «Error Detecting and Error Correcting Codes». Bell System Technical Journal. USA: AT&T. 29 (2): 147–160. doi:10.1002/j.1538-7305.1950.tb00463.x. S2CID 61141773.
6. ^ «Hamming codes for NAND flash memory devices» Archived 21 August 2016 at the Wayback Machine. EE Times-Asia. Apparently based on «Micron Technical Note TN-29-08: Hamming Codes for NAND Flash Memory Devices». 2005. Both say: «The Hamming algorithm is an industry-accepted method for error detection and correction in many SLC NAND flash-based applications.»
7. ^ ^{a b} «What Types of ECC Should Be Used on Flash Memory?» (Application note). Spansion. 2011. Both Reed–Solomon algorithm and BCH algorithm are common ECC choices for MLC NAND flash. … Hamming based block codes are the most commonly used ECC for SLC…. both Reed–Solomon and BCH are able to handle multiple errors and are widely used on MLC flash.
8. ^ Jim Cooke (August 2007). «The Inconvenient Truths of NAND Flash Memory» (PDF). p. 28. For SLC, a code with a correction threshold of 1 is sufficient. t=4 required … for MLC.
9. ^ Baldi, M.; Chiaraluce, F. (2008). «A Simple Scheme for Belief Propagation Decoding of BCH and RS Codes in Multimedia Transmissions». International Journal of Digital Multimedia Broadcasting. 2008: 1–12. doi:10.1155/2008/957846.
10. ^ Shah, Gaurav; Molina, Andres; Blaze, Matt (2006). «Keyboards and covert channels». USENIX. Retrieved 20 December 2018.
11. ^ Tse, David; Viswanath, Pramod (2005), Fundamentals of Wireless Communication, Cambridge University Press, UK
12. ^ Shannon, C. E. (1948). «A mathematical theory of communication» (PDF). Bell System Technical Journal. 27 (3–4): 379–423 & 623–656. doi:10.1002/j.1538-7305.1948.tb01338.x. hdl:11858/00-001M-0000-002C-4314-2.
13. ^ Rosas, F.; Brante, G.; Souza, R. D.; Oberli, C. (2014). «Optimizing the code rate for achieving energy-efficient wireless communications». Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC). pp. 775–780. doi:10.1109/WCNC.2014.6952166. ISBN 978-1-4799-3083-8.
14. ^ IEEE Standard, section 20.3.11.6 «802.11n-2009» Archived 3 February 2013 at the Wayback Machine, IEEE, 29 October 2009, accessed 21 March 2011.
15. ^ ^{a b} Vucetic, B.; Yuan, J. (2000). Turbo codes: principles and applications. Springer Verlag. ISBN 978-0-7923-7868-6.
16. ^ Luby, Michael; Mitzenmacher, M.; Shokrollahi, A.; Spielman, D.; Stemann, V. (1997). «Practical Loss-Resilient Codes». Proc. 29th Annual Association for Computing Machinery (ACM) Symposium on Theory of Computation.
17. ^ «Digital Video Broadcast (DVB); Second generation framing structure, channel coding and modulation systems for Broadcasting, Interactive Services, News Gathering and other satellite broadband applications (DVB-S2)». En 302 307. ETSI (V1.2.1). April 2009.
18. ^ Andrews, K. S.; Divsalar, D.; Dolinar, S.; Hamkins, J.; Jones, C. R.; Pollara, F. (November 2007). «The Development of Turbo and LDPC Codes for Deep-Space Applications». Proceedings of the IEEE. 95 (11): 2142–2156. doi:10.1109/JPROC.2007.905132. S2CID 9289140.
19. ^ Dolinar, S.; Divsalar, D. (15 August 1995). «Weight Distributions for Turbo Codes Using Random and Nonrandom Permutations». TDA Progress Report. 122: 42–122. Bibcode:1995TDAPR.122…56D. CiteSeerX 10.1.1.105.6640.
20. ^ Takeshita, Oscar (2006). «Permutation Polynomial Interleavers: An Algebraic-Geometric Perspective». IEEE Transactions on Information Theory. 53 (6): 2116–2132. arXiv:cs/0601048. Bibcode:2006cs……..1048T. doi:10.1109/TIT.2007.896870. S2CID 660.
21. ^ 3GPP TS 36.212, version 8.8.0, page 14
22. ^ «Digital Video Broadcast (DVB); Frame structure, channel coding and modulation for a second generation digital terrestrial television broadcasting system (DVB-T2)». En 302 755. ETSI (V1.1.1). September 2009.
23. ^ Techie (3 June 2010). «Explaining Interleaving». W3 Techie Blog. Retrieved 3 June 2010.
24. ^ Krastanov, Stefan; Jiang, Liang (8 September 2017). «Deep Neural Network Probabilistic Decoder for Stabilizer Codes». Scientific Reports. 7 (1): 11003. arXiv:1705.09334. Bibcode:2017NatSR…711003K. doi:10.1038/s41598-017-11266-1. PMC 5591216. PMID 28887480.
25. ^ Nordstrom, A.W.; Robinson, J.P. (1967), «An optimum nonlinear code», Information and Control, 11 (5–6): 613–616, doi:10.1016/S0019-9958(67)90835-2
26. ^ Perry, Jonathan; Balakrishnan, Hari; Shah, Devavrat (2011). «Rateless Spinal Codes». Proceedings of the 10th ACM Workshop on Hot Topics in Networks. pp. 1–6. doi:10.1145/2070562.2070568. hdl:1721.1/79676. ISBN 9781450310598.