algebcodes_1

7.10. Решение ключевого уравнения на случай ошибок и стираний251

Имеем

z6 = (α5z4 + α3z3 + α7z2 + α7z + α)(α3z2 + α5z + α2) + (α7z + α5). q0(z) = α3z2 + α5z + α2, r0(z) = α7z + α5.

Видим,что впервые неравенство deg rk(z) ≤ (t + l − 1) выполняется при k = 0, так как t = 2, l = 2. Согласно процедуре вычислений,

u−2(z) = 0, u−1(z) = 1,

u0(z) = q0(z)u−1(z) + u−2(z) = α3z2 + α5z + α2.

Следовательно,

σ(z) = χu0(z).

Для того, чтобы выполнялось условие σ(0) = 1, положим χ = α6. Тогда

σ(z) = αz2 + α3z + 1.

Корни этого многочлена суть z1 = 1, z2 = α7. Локаторы оши-

бок X1 = 1, X2 = α.

Перейдём к нахождению значений ошибок и стираний. Напомним, что выше был введён в обращение многочлен

корнями которого являются величины, обратные локаторам ошибок и локаторам стираний. Объединим оба эти явления под названием "искажения" , а многочлен (7.10.72) назовём многочленом локаторов искажений и будем искать значения искажений. Решение этой задачи достигается посредством многочлена

~

−ω~(z) = σ~(z)S(z)(modzd−1), который мы назовём многочле-

ном значений искажений. Возьмём производную от σ~(z) :

Подставим в (7.9.59) и (7.10.73) любой корень Xj−1 многочлена локаторов искажений. Тогда получим

Действительно, в каждой из сумм (7.9.59) и (7.10.73) останется в точности по одному слагаемому, именно

в сумме (7.9.59).

Остальные обращаются в нуль. Из (7.10.74), (7.10.75) следует

Знаменатель последней дроби не обращается в нуль, так как многочлен σ~(z) не имеет кратных корней.

Продолжим пример 7.9.

σ~(z) = σ(z)ν(z) = (αz2 + α3z + 1)(αz2 + z + 1) =

= α2z4 + α6z3 + α6z2 + α5z + 1. (7.10.78)

~ d−1 −ω~(z) = σ~(z)S(z)(modz ) =

=(α5z4 + α3z3 + α7z2 + α7z + α)(α3z2 + α5z + α2)(modz6) =

=α7z3 + α5z2 + αz + α.

Отсюда ω(z) = α3z3 + αz2 + α5z + α5.

Так как локаторы искажений

X1 = 1, X2 = α, X3 = α2, X4 = α7,

то окончательно:

Остаётся сравнить полученный результат с парой векторов – отправленным вектором u и принятым вектором v.

Заметим, что замена стёртого символа ci нулём означает вычитание ci − ci. Поэтому, восстановление данного стирания выполняется заменой символа стирания величиной ci, в точности равной дроби (7.10.77) с обратным знаком.

Читателю предлагается довести до конца процедуру по вычислению значений ошибок примера 7.5., удалив сначала знак тильды в формулах, начиная с (7.9.59), так как упомянутый пример имеет дело только с ошибками, а не стираниями.

Декодирование посредством алгоритма Эвклида интересно не только из-за простоты понимания всей процедуры. Наибольший интерес представляет сама возможность применения алгоритма Эвклида. Еще раз подчеркнём замечание, приведённое в придисловии ко второму изданию. Фундаментальный алгебраический факт, известный с незапамятных времён, через века

оказался как-будто специально приготовленным для решения ключевого уравнения, которое появилось совсем недавно ради

вполне практической задачи: надёжной передачи инфомации.

7.11. Коды РС и построение каскадных кодов

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

рамках даже большой части общего руководства по теории кодирования. Поэтому здесь будет указан основной принцип построения каскадных кодов. Заинтересовавшийся читатель сможет обратиться к таким источникам, как [4, 7, 8].

Без потери общности и ради простоты ограничимся случаем q = 2m. Пусть a = (a1, a2, . . . , ak) есть вектор информационных символов над полем GF (2m). Он кодируется в вектор некоторого линейного кода с параметрами n2, k2, d2. Этот код называют внешним кодом. Чаще всего внешним (n2, k2, d2)- кодом бывает код РС, и потому n2 ≤ 2m − 1. Представим каждый символ внешнего кода в виде вектора длины m над GF (2), а затем, приняв эти m символов за информационные, их кодируют в вектор линейного кода с параметрами n1, k1 = m, d1. Этот код называют внутренним кодом. Получится код над

GF (2) с параметрами N = n1n2, K = k1k2, D = d1d2. Повидимому, первые два параметра очевидны. Покажем спра-

ведливость равенства D = d1d2. Действительно, два вектора внешнего кода различаются не менее, чем в d2 компонентах, а каждая пара символов внутреннего кода в каждой из этих компонент различается не менее, чем в d1 компонентах. Полученный код называется суперкодом.

Возможно иное, эквивалентное, описание каскадного кода. Пусть имеется двоичная информационная последовательность длины K = k1k2. Она разбивается на k2 отрезков длины k1.

Эти отрезки рассматриваются как элементы поля GF (2k1 ). По-

следовательность длины k2 над полем GF (2k1 ) будет ни чем иным, как информационной последовательностью, которая кодируется в кодовый вектор кода длины n2 над тем же полем с кодовым расстоянием d2. Пусть таким вектором будет

A = (α1, α2, . . . , αn2 ), αi GF (2k). Кодирование заканчивается тем, что каждый элемент αi кодируется внутренним кодом в

(двоичный) вектор βi длины n1. Вектор B = (β1, β2, . . . , βn2 ) отправляется в канал связи.

Как видим, снова параметрами суперкода будут

N = n1n2, K = k1k2, D = d1d2.

Вспомним теперь (раздел 4.5) вывод границы Варшамова

— Гилберта посредством построения проверочной матрицы линейного кода, а значит, и самого кода. Это построение велось методом перебора, и его объем выражался числом порядка 2n,

где n есть длина кода. Иначе говоря объем перебора при таком построении кода зависит экспоненциально от длины n кода.

велико. Иными словами, пусть скорость передачи внутреннего

кода не слишком мала. Так как n2 = 2m − 1 = 2k1−1, то оказывается, что длина n1 внутреннего кода есть величина порядка

x log2 n2. Это значит, что даже если внутренний код получается методом перебора, то его объем выражается величиной порядка 2n1 2x log2 n2 = nx2 . Такой перебор может считаться вполне приемлемым: его объем по порядку не превосходит небольшой

степени длины внешнего кода (т.е. даже не суперкода). И вовсе не зависит от нее экспоненциально.

Если учесть, что внешний код является кодом с максималь-

но достижимым кодовым расстоянием d2, то становятся ясными весьма высокие качества каскадных кодов.

В литературе по теории кодирования показано, что класс всех каскадных кодов содержит коды, лежащие на границе

Варшамова—Гилберта.

Еще более результативной является идея обобщенных кас-

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

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

образом. Принятая последовательность поступает на декодер внутреннего кода. Каждый отрезок длины n1 один за другим рассматривается как, быть может искаженный, вектор внутреннего кода над GF (2), и декодер исправляет в нем все ошибки кратности (d1 − 1)/2 и менее.

Если в некотором отрезке произошло более, чем (d1 − 1)/2 ошибок, то декодирование может оказаться неверным. Имеет

место ошибка декодирования. После завершения работы внутреннего декодера принятая последовательность поступает на

внешний декодер. Каждый отрезок длины n1 рассматривается

внешним декодером как элемент поля GF (2m). Ошибочно декодированные внутренним декодером отрезки длины n1 пред-

ставляют собой искаженные компоненты вектора внешнего кода . Если таких компонент окажется не более, чем (d2 − 1)/2, то принятый вектор декодируется внешним декодером верно. Декодирование заканчивается.

7.12. Задачи к главе 7

7.1. Описать (15, 13)-код Рида — Соломона над полем GF (24), определив его длину, порождающий многочлен и число исправ-

ляемых ошибок.

7.2.Процедура удлинения кода РС в разделе 7.4 основана на списке корней порождающего многочлена в (7.4.8). Как изменятся рассуждения об удлинении, если к списку корней будет принадлежать 1?

7.3.Передача ведется кодом РС над GF (32), порождающий

многочлен которого имеет своими корнями αi, i = 1, . . . , 6.

Поле построено по модулю многочлена x2 + x + 2. Принят вектор v = (α, α6, α4, α2, 0, α3, α7, α). Исправить ошибки.

7.4. Доказать или опровергнуть, что для отыскания значений ошибок Y1, Y2, . . . , Yt можно воспользоваться любыми t подряд идущими уравнениями (6.9.48).

7.5. Показать, что в векторе циклического (n, k)- кода любые k

идущих подряд разрядов образуют информационную совокупность.

Глава 8.

Сводка границ

Приведем наиболее часто употребимые границы.

8.1. Верхние границы

Граница Хэмминга на случай четного d

Граница Бассалыго—Элайеса. Пусть A(n, d)− есть максимально возможное число кодовых векторов над GF (q) кода длины n с минимальным расстоянием d = 2t + 1. Тогда

qn

A(n, d) ≤ , (8.1.5)

Cnr(q − 1)r

8.2. Нижняя граница

Граница Варшамова—Гилберта Если выполняется неравенство

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

8.3. Асимптотические границы

Без труда находим, что при n → ∞ граница Синглтона дает

nd ≤ 1 − nk .

Перейдем к выводу асимптотической границы Плоткина. Из (8.1.2) получается

qk−1(qd + n − nq) ≤ d.

Отсюда при qd + n − nq > 0 имеем (см. задачу 5.14):

Для случая n = (qd − 1)/(q − 1) (благодаря предположению о выполнении этого условия границу Плоткина называют границей кодов с большим кодовым расстоянием) получается

()

Применяя a раз процедуру укорочения кода (см. задачу 5.14), получим

Из (8.3.8) и (8.3.9) при n − a = (qd − 1)/(q − 1)

()

Вспомним, что для исходного кода с k информационными символами, т.е. до применения процедуры укорочения, должно быть

B(n, d) = qk. Подставляя это значение в неравенство (8.3.10) и логарифмируя последнее по q, получим

Пренебрегая в этом неравенстве при n → ∞ последним слага-

емым и удаляя −1 из числителя первой дроби в правой части неравенства, получим окончательно

Это и есть асимптотическа форма границы Плоткина.

Для получения асимптотики остальных границ следует оценить числа сочетаний и суммы чисел сочетаний.

В основе этих оценок лежат неравенства Стирлинга для факториала:

1

= √2πλµnλλnµµn exp A,

где

0 < λ, µ < 1, λ + µ = 1,

и

Все приведенные выше выражения симметричны относительно λ, µ. Пусть для определенности и без потери общности λ ≥ µ. Тогда

Воспользуемся теперь упрощенными неравенствами Стирлинга.

Положим µn ≥ 3, λn ≥ 1, (или, наоборот, лишь бы одно из этих произведений было не меньше трех). Тогда