6.3. Использование кодов Рида—Соломона для исправления стираний

Код Рида—Соломона с минимальным расстоянием d может исправлять d—1 или менее стираний. При этом под стиранием понимается такое состояние приемника, когда значение сигнала попадает в так называемую зону неопределенности. Для кас­кадных кодов под стиранием понимают «маскирование». Это означает, что на предшествующем уровне декодирования при­меняют код, обнаруживающий ошибки, что позволяет пометить специальным образом элементы кодовых комбинаций с обнару­женными ошибками. Таким образом, при передаче кодового вектора по стирающему каналу на приемной стороне становят­ся известными номера позиций Х₁,X₂, ..., X_t со стираниями пли отмеченные специальной «маской». Поэтому задачей деко­дирования является определение неизвестных кодовых элемен­тов, расположенных на этих позициях. Алгоритм исправления стираний мало чем отличается от исправления ошибок и сво­дится к решению системы уравнений (6.8) относительно неиз­вестных Y_t, которые являются значениями стертых символов комбинации либо значениями вектора ошибок в позициях, по­меченных «масками».

Рассмотрим пример исправления стираний. Пусть (п, k)— код Рида—Соломона с образующим полиномом g(x) = (х+ 1)(x+ а) имеет минимальное расстояние d = 3. Тогда такой код исправляет одно или два стирания. Проверочная матрица имеет вид (6.17).

Пусть далее, а — примитивный элемент поля GF (2³) с по­рождающим полиномом Р (х) = 1 + х+x³. Тогда, выбрав дли­ну комбинации n = 2³—1, мы построим код (7, 5), который может исправлять одно или два стирания или однократную ошибку без стираний.

Рассмотрим передачу по стирающему каналу кодового век-гора

(c₀c₁c₂c₃c₄c₅c₆)=(a⁶1aa²a³a⁴a⁵),

где элементы с_i являются коэффициентами разрешенной ко­довой комбинации кода (7, 5), представленной полиномом (6.1). Предположим, что в результате приема имели место два стирания и были стерты элементы c₂ и с₄ и тогда на декодер поступит комбинация (а⁶ 1 0 а² 0 а⁴ а⁵). Таким образом стер­тые позиции Х₁ = х² и Х₂ = х⁴ известны. Умножив принятый вектор со стираниями на Н^T в соответствии с (6.17), получим значения синдромов

S₀=Y₁+Y₂=1

S₁=Y₁X₁+Y₂X₂=a

Решая полученную систему уравнений относительно значе­ний стертых символов Y₁ и Y₂ находим:

Y₁=(S₁+X₂S₀)/(X₁+X₂)=a;

Y₂=S₀+Y₁=a³.

Таким образом, зная номера X₁ и X₂ стертых символов, мо­жет быть осуществлено исправление стираний путем замены, ну­лей найденными значениями Y₁ и Y₂.

6.4. Реализация действий над элементами поля

При построении кодирующих и декодирующих устройств циклических кодов, особенно БЧХ и Рида—Соломона, должны быть реализованы операции умножения и деления в поле GF(2^k). Рассмотрим реализационные основы таких действий над элементами конечного поля Галуа.

Пусть задан примитивный полином k-й степени над про­стым полем GF (2):

Квадратной матрице F соответствует характеристический поли­ном f (λ), представляющий собой определитель характеристи­ческой матрицы [λЕ— F], где Е — квадратная единичная мат­рица k-го порядка, т. е. f (λ) =│ λ Е— F│. Корни полинома f (λ ) λ ₁, λ ₂, … λ _k, называемые характеристическими числами, являются решением векового [9] уравнения │ λ Е— F│ = 0.

Как видно из этого уравнения, одним из корней полинома f (λ ) является сопровождающая матрица F. Действительно, если в характеристический полином f (λ ) вместо λ подставить F, то получим f (F) = │FE — F│ =0, Тем самым доказана тео­рема Гамильтона—Кэли [9], в соответствии с которой всякая квадратная матрица F является корнем своего характеристиче­ского полинома f (λ ).

С другой стороны, легко проверить, что заданный прими­тивный полином Р (х) в точности совпадает с характеристиче­ским полиномом f(X) при подстановке х = λ , т. е. f (λ ) = Р (λ ). Отсюда следует, что матрица F является также корнем поли­нома Р (х), т. е. Р (F) = 0. Последнее условие приводит к важ­ному следствию, заключающемуся в том, что множество эле­ментов поля GF(2^k) построенного по примитивному полиному Р (х), изоморфно множеству полиномов — вычетов по модулю P(F). Другими словами, любому элементу a^m поля GF(2^k), выраженному через степенной базис

где. а — первообразный элемент поля, а коэффициенты а, eGF(2), взаимнооднозначно соответствует многочлен

приведенный по модулю Р (F). Указанное свойство позволяет достаточно просто реализовать умножение и деление элемен­тов поля GF (2^к) в векторной форме. Рассмотрим эти действия.

6.4.1. Умножение элементов поля

Пусть необходимо умножить элемент аⁱ на элемент a^J. С этой целью выразим эти элементы поля GF (2^k) через степен­ной базис следующим образом:

Тогда произведение aⁱa^j=a^m=c₀+c₁a+c₂a²+…+c_k-1a^k-1 может быть реализовано в векторной форме следующим обра­зом:

(a₀a₁…a_k)F^j=(a₀a₁…a_k)[b₀E+b₁F+…b_k-1F^k-1]=

Напомним, что для двоичных кодов сложение производится по mod 2.

Структурная схема умножителя в соответствии с алгорит­мом (6.24) представлена на рис. 6.8.

Рис. 6.8. Структурная схема умножителя произвольных элементов поля GF(2^k)

Рассмотрим конкретный пример.

Пусть поле GF (2⁴) образовано примитивным полиномом Р (х) = 1+x+x⁴. Сопровождающая матрица F этого полино­ма и ее степени F² и F³ имеют вид

Необходимо произвести умножение двух элементов аⁱ и а^j, принадлежащих полю GF (2⁴).

Выразим аⁱ и а^j через базис {1, а, а², а³} следующим образом:

Таким образом, векторная форма записи элементов аⁱ и а^j будет соответственно [а] = [а₀, а_ь а₂, a₃] и [b] = [b_о, b₁, b₂, b₃]. Заменив элемент поля a^J на F^j, равный F^j=b₀E+b₁F+b₂F²+b₃F³, найдем произведение (aⁱa^j )= с_о +c₁a+c₂a²+c₃a³ в векторной форме, используя алгоритм (6.24), а именно

У чтем, что для данного полинома Р (х) и его матрицы F имеют место равенства:

Тогда вектор [c]=[c₀,c₁,c₂,c₃], соответствующий произведению aⁱa^j, будет равен поэлементной сумме по модулю два

Ф ункциональная схема существенно упрощается, если необходимо произвольный элемент поля aⁱ умножить на константу a^j. Пусть для рассматриваемого выше примера необходимо производить умножение на а⁵. Тогда произведение аⁱa⁵ в векторной форме будет выражаться следующим образом:

Функциональная схема такого умножителя представлена на рис. 6.10.

Рис 6.9. Функциональная схема умножения произвольных элементов поля GF (2⁴) с образующим многочленом Р(х) = 1 + х + х⁴

Другой распространенный в настоящее время алгоритм ум­ножения элементов поля GF (2^k) основан на применении опе­раций логарифмирования и антилогарифмирования в полях GF (2^k) [4, 6].

Рис. 6.10. Функциональная схема ум­ножения произвольного элемента аⁱ поля GF(2⁴) на константу a⁵

Если некоторый элемент поля β=aⁱ принадлежит полю GF(2^k), то логарифм элемента β по основанию a€GF (2^k) есть показатель степени i, а именно: Log β = log aⁱ=i, i≥0. Тогда, умножение aⁱa^j= a^m может быть реализовано по сле­дующему алгоритму, представленному на рис. 6.11.

Рис. 6.11. Структурная схема умножителя произволь­ных элементов аⁱ и а^j в поле GF(2^k) с использо­ванием логарифмировании и антилогарифмирования

Особенностью данного алгоритма является то, что комби­нациям из k нулей или k единиц на выходе арифметического сумматора должно соответствовать появление на выходе ан-тилогарифматора одинакового элемента, а именно а⁰ = 1.

Логарифмирование и антилогарифмирование реализуется чаще всего табличным способом.

6.4.2. Деление элементов поля

В теории циклических кодов часто встречающейся операцией является деление произвольного элемента aⁱ на некоторый эле­мент a^j, где aⁱ , aⁱ€GF (2^k). Вместе с тем на практике деле­ние элементов заменяется умножением элемента aⁱ на a^-j, т. е.

где a^-j —элемент поля, обратный элементу а^j. Напомним, что для любого элемента а^j в поле GF (2^k) всегда существует и обратный ему a^-j , которые связаны равенством a^ja^-j= 1. Та­ким образом, реализация деления осуществляется по той же схеме, что и умножение (рис. 6.9) с той разницей, что один из сомножителей является обратным элементом a^-j. Рассмот­рим способы обращения элементов поля GF(2^k).

Один из способов основан на свойстве полей Галуа, кото­рое заключается в том, что ненулевые элементы поля GF (2^k) образуют циклическую мильтипликативную группу порядка 2^k — 1, т. е. для любого ненулевого элемента а^j справедливо

равенство (а^j)^2k-1 = 1. Отсюда получается (а^j)^2k-2 =

= (a^J)^-1= a^-j. Для вычисления (2^k —2)-й степени элемента β можем воспользоваться одним из следующих двух равенств:

(β )^2k-2={[(β²β)²β]²… β }²= β ^-1 (6.27)

Характерной особенностью равенства (6.26) является то, что обращение элемента β может быть реализовано аппарат­ным путем за один шаг (такт), тогда как равенство (6.27) мо­жет быть реализовано за (k—1) последовательных этапов. Вместе с тем реализация последнего значительно проще. На каждом этапе необходимо осуществить умножение текущего значения на β и возведение результата в квадрат. Если элемент β выразить через базисные элементы поля 1, а, а², ..., а^k-1 в виде β = а₀ +a₁a+a₂a²+…a_k-1a^k-1, то на основании свойств (1.4) и (1.5) возведение в квадрат в поле GF (2*) со­ответствует выражению

Тогда операцию возведения в квадрат в векторной форме мож­но записать

(a₀a₁a₂…a_k-1)[X] = (b₀b₁b₂…b_k-1),

где [X] — квадратная матрица k-го порядка, строки которой представляют собой двоичные векторы элементов поля

Пример. Построить матрицу [X] и схему возведения в квад­рат, если конечное поле GF (2⁴) образовано примитивным по­линомом Р (х) = 1+x+x⁴

Выразим элементы поля а⁰, а², а⁴, а⁶ через базис {1, а, а² а³} в виде аⁱ = с₀ + с₁а + с₂а² + c₃а³, где с€GF (2):

И з векторов (с0 с1 с2 с3) указанных элементов составим матрицу [X]:

Пусть элементу аⁱ соответствует вектор (а₀ а₁ а₂ а₃). Для возведения аⁱ в квадрат произведем умножение вектора (а₀ а₁ а₂ а₃) на матрицу [X]:

Логическая схема возведения в квадрат в поле GF (2⁴) с

образующим полиномом Р(х) = 1 + х +x⁴ представлена на рис. 6.12.

Для проверки возведем эле­мент а⁵ в квадрат. Так как a⁵ = a +а², то для получения элемента (а⁵)² выполним ум­ножение вектора элемента а⁵ на матрицу [X], т. е.

Рис. 6.12. Функциональная схе­ма

возведения в квадрат про­извольного элемента аⁱ в по­ло GF(2⁴)

Полученный вектор (1110) соответствует элементу (а⁵)² = a¹⁰ поля GF (2⁴).