Основы теории принятая статистических решений 1051 40 страница

	а^0	а^1	а^2	а^3	а^4	а^5	а^6
а^0	а^0	а'	а^2	а^3	а^4	а^5	а^6
а'	а'	а^2	а^3	а^4	а^5	а^6	а^0
а^2	а^2	а^3	а^4	а^5	а^6	а^0	а^1
а^3	а^3	а^4	а^5	а^6	а^0	а^1	а^2
а^4	а^4	а^5	а^6	а^0	а^1	а^2	а^3
а^5	а’	а^6	а^0	а^1	а^2	а^3	а^4
а^6	а^6	а^0	а'	а^2	а^3	а^4	а’

8.1.4.4. Простой тест для проверки полинома на примитивность

Существует еще один, чрезвычайно простой способ проверки, является ли поли­ном примитивным. У нередуцируемого полинома, который является примитивным, по крайней мере, хотя бы один из корней должен быть примитивным элементом. Примитивным элементом называется такой элемент поля, который, будучи возведен­ным в более высокие степени, даст все ненулевые элементы поля. Поскольку данное поле является конечным, количество таких элементов также конечно.

Пример 8.2. Примитивный полином должен иметь, по крайней мере, хотя бы один примитивный элемент

Найдите т = 3 корня полинома fiX) = 1 + X + X³ и определите, примитивен ли полином. Для этого проверьте, имеется ли среди корней полинома хотя бы один примитивный эле­мент. Каковы корни полинома? Какие из них примитивны?

Решение

Корни будут найдены прямым перебором. Итак, сх°= 1 не будет корнем, поскольку Дсх°) = 1. Те­перь, чтобы проверить, является ли корнем а¹, воспользуемся табл. 8.2. Поскольку Да) = 1 + а + а³ = 1 + сх° = 0, значит, а будет корнем полинома. Далее поверим, будет ли корнем а². Да²) = 1 + а² + ос⁶ = 1 + сх° = 0. Значит, и а² также будет корнем полинома. Теперь проверим а³. Да³) = 1 + а³ + а² = 1 + а⁵ = cd Ф 0. Следовательно, а³ корнем полинома не является. Будет ли корнем а⁴? Да⁴) = а¹² + а⁴ + 1= 1 + а⁰ = 0. Да, а⁴ будет корнем полинома. Значит, корнями полинома flX) = 1 + X + X³ будут а, а² и О⁴. Нетрудно убедиться, что последовательно возводя в степень любой из этих корней, можно получить все 7 ненулевых элементов поля. Таким образом, все корни будут примитивными элементами. Поскольку в определении требуется, чтобы по крайней мере один из корней был примитивным, полином является примитивным.

В этом примере описан относительно простой метод проверки полинома на примитивность. Для проверяемого полинома нужно составить регистр LFSR с контуром обратной связи, со­ответствующим коэффициентам полинома, как показано на рис. 8.8. Затем в схему регистра следует загрузить любое ненулевое состояние и выполнять за каждый такт правый сдвиг. Если за один период схема сгенерирует все ненулевые элементы поля, то данный полином с полем GF(2"‘) будет примитивным.

8.1.5. Кодирование Рида-Соломона

В уравнении (8.2) представлена наиболее распространенная форма кодов Рида- Соломона через параметры п, к, t и некоторое положительное число т > 2. Приведем это уравнение повторно:

(пД) = (2^й - 1, 2^т - 1 - 2t).

Здесь п - к = 2t — число контрольных символов, at— количество ошибочных битов в символе, которые может исправить код. Генерирующий полином для кода Рида- Соломона имеет следующий вид:

gW ⁼8о + gi% + g2%² + ••• + g2t-iX²' *+Х²'. (8.21)

Степень полиномиального генератора равна числу контрольных символов. Коды Рида-Соломона являются подмножеством кодов БХЧ, которые обсуждались в разде­ле 6.8.3 и показаны в табл. 6.4. Поэтому связь между степенью полиномиального ге­нератора и числом контрольных символов, как и в кодах БХЧ, не должна оказаться неожиданностью. В этом можно убедиться, подвергнув проверке любой генератор из табл. 6.4. Поскольку полиномиальный генератор имеет порядок 21, мы должны иметь в точности 2г последовательные степени а, которые являются корнями полинома. Обозначим корни g(X) как: а, а², а²'. Нет необходимости начинать именно с корня а, это можно сделать с помощью любой степени а. Возьмем к примеру код (7, 3) с возможностью коррекции двухсимвольных ошибок. Мы выразим полиномиальный генератор через 2t = п - к - 4 корня следующим образом:

g(X) = (X - а)(Х - а²) (X - а³) (X - а⁴) =

= (X² - (а + а²)Х + а³)(Х² - (а³ + а⁴)Х + а⁷) =

= (X² - а⁴Х + а³)(Х² - а⁶Х + а⁰) =

= X⁴ - (а⁴ + а⁶)Х³ + (а³ + а¹⁰ + а°)Х² - (а⁴ + а⁹)Х + а³ =

= X⁴ - а³Х³ + а°Х² - а'х + а³.

Поменяв порядок расположения членов полинома на обратный и заменив знаки “минус” на “плюс”, так как над двоичным полем +1 =-1, генератор g(X) можно будет представить следующим образом:

g(X) = а³ + а^[Х + а°Х² + а³Х³ + X⁴. (8.22)

8.1.5.1. Кодирование в систематической форме

Так как код Рида-Соломона является циклическим, кодирование в систематиче­ской форме аналогично процедуре двоичного кодирования, разработанной в разде­ле 6.7.3. Мы можем осуществить сдвиг полинома сообщения т(Х) в крайние правые к разряды регистра кодового слова и произвести последующее прибавление полинома четности р(Х) в крайние левые п-к разряды. Поэтому мы умножаем т(Х) на X""*, проделав алгебраическую операцию таким образом, что т(Х) оказывается сдвинутым вправо на п-к позиций. В главе 6 это показано в уравнении (6.61) на примере двоич­ного кодирования. Далее мы делим Х"'⁴т(Х) на полиномиальный генератор g(X), что можно записать следующим образом:

X^я - ⁴m(X) - q(X)g(X) + р(Х). (8.23)

Здесь q(X) и р(Х) — это частное и остаток от полиномиального деления. Как и в слу­чае двоичного кодирования, остаток будет четным. Уравнение (8.23) можно перепи­сать следующим образом:

р(Х) = X" ~*т(Х) по модулю g(X). (8.24)

Результирующий полином кодового слова U(X), показанный в уравнении (6.64), можно переписать следующим образом:

ЩХ) = р(Х) + Х^а~^кт(Х). (8.25)

Продемонстрируем шаги, подразумеваемые уравнениями (8.24) и (8.25), закодиро­вав сообщение из трех символов

010 110 1П а¹ а³ а⁵

с помощью кода Рида-Соломона (7,3), генератор которого определяется уравнением (8.22). Сначала мы умножаем (сдвиг вверх) полином сообщения а¹ + а?Х + а⁵Х² на Х^п~^к = Х⁴, что дает а'Х + а'Х⁵ + ofX⁶. Далее мы делим такой сдвинутый вверх полином сообщения на по­линомиальный генератор из уравнения (8.22), а³ + а'Х + а°Х² + а³Х³ + X⁴. Полиномиальное деление недвоичных коэффициентов — это еще более утомительная процедура, чем ее двоичный аналог (см. пример 6.9), поскольку операции сложения (вычитания) и умноже­ния (деления) выполняются согласно табл. 8.2 и 8.3. Мы оставим читателю в качестве са­мостоятельного упражнения проверку того, что полиномиальное деление даст в результате следующий полиномиальный остаток (полином четности):

р(Х) = а⁰ + а²Х + а⁴*² + а⁶*³.

Затем, из уравнения (8.25), полином кодового слова можно записать следующим образом: U(X) = а⁰ + а²Х + а⁴Х² + а⁶Х³ + а’Х⁴ + а³Х⁵ + а⁵*⁶.

8.1.5.2. Систематическое кодирование с помощью (п -к)-разрядного регистра сдвига

Как показано на рис. 8.9, кодирование последовательности из 3 символов в сис­тематической форме на основе кода Рида-Соломона (7, 3), определяемого генератором g(X) из уравнения (8.22), требует реализации регистра LFSR. Нетрудно убедиться, что элементы умножителя на рис. 8.9, взятые справа налево, соответствуют коэффициен­там полинома в уравнении (8.22). Этот процесс кодирования является недвоичным аналогом циклического кодирования, которое описывалось в разделе 6.7.5. Здесь, в соответствии с уравнением (8.20), ненулевые кодовые слова образованы 2^т -1 = 7 символами, и каждый символ состоит из т - 3 бит.

  010 110 111 --------------------»- Переключатель 2 а’ а³ а⁵ Рис. 8.9. Кодер LFSR для кода (7, 3)

Следует отметить сходство между рис. 8.9, 6.18 и 6.19. Во всех трех случаях ко­личество разрядов в регистре равно п-к. Рисунки в главе 6 отображают пример двоичного кодирования, где каждый разряд содержит 1 бит. В данной главе при­веден пример недвоичного кодирования, так что каждый разряд регистра сдвига, изображенного на рис. 8.9, содержит 3-битовый символ. На рис. 6.18 коэффици­енты, обозначенные g_b g₂,..., являются двоичными. Поэтому они принимают од­но из значений 0 или 1, просто указывая на наличие или отсутствие связи в LFSR. На рис. 8.9 каждый коэффициент является 3-битовым, так что они могут принимать одно из 8 значений.

Недвоичные операции, осуществляемые кодером, показанным на рис. 8.9, создают кодовые слова в систематической форме, так же как и в двоичном случае. Эти опера­ции определяются следующими шагами.

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

2. В течение первых к тактовых импульсов переключатель 2 находится в нижнем положении, что обеспечивает одновременную передачу всех символов сообщения непосредственно на регистр выхода (на рис. 8.9 не показан).

3. После передачи к-то символа на регистр выхода, переключатель 1 открывается, а переключатель 2 переходит в верхнее положение.

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

5. Общее число тактовых импульсов равно п, и содержимое регистра выхода явля­ется полиномом кодового слова р(Х)+ Х""*ш(Х), где р(Х) представляет собой ко­довые символы, а ш(Х) — символы сообщения в полиномиальной форме.

Для проверки возьмем ту же последовательность символов, что и в разделе 8.1.5.1.

010 110 111

а¹ а³ ос⁵

Здесь крайний правый символ является самым первым и крайний правый бит также является самым первым. Последовательность действий в течение первых к = 3 сдвигов в цепи кодирования на рис. 8.9 будет иметь следующий вид.

ОЧЕРЕДЬ ВВОДА ТАКТ СОДЕРЖИМОЕ РЕГИСТРА ОБРАТНАЯ СВЯЗЬ

а^1 а^3	а^5						а^5
а^1	а^3		а^1	а^6	а^5	а^1	а^0
	а^1		а^3		а^2	а^2	а^4
	—		а^0	а?	а^4	а^6	—

Как можно видеть, после третьего такта регистр содержит 4 контрольных сим­вола, а⁰, а², а⁴ и а⁶. Затем переключатель 1 переходит в верхнее положение, и контрольные символы, содержащиеся в регистре, подаются на выход. Поэтому выходное кодовое слово, записанное в полиномиальной форме, можно предста­вить в следующем виде:

U(X) = £«„X".

л = 0

= (100) + (001)X + (01 l)X² +(101)X³ + (OIO)X⁴ + (110)X⁵ + (11 ^X⁶.

Процесс проверки содержимого регистра во время разных тактов несколько сложнее, чем в случае бинарного кодирования. Здесь сложение и умножение элементов поля должны выполняться согласно табл. 8.2 и 8.3.

Корни полиномиального генератора g(X) должны быть и корнями кодового слова, генерируемого g(X), поскольку правильное кодовое слово имеет следующий вид:

U(X) = m(X)g(X). (8.27)

Следовательно, произвольное кодовое слово, выражаемое через корень генератора g(X), должно давать нуль. Представляется интересным, действительно ли полином ко­дового слова в уравнении (8.26) дает нуль, когда он выражается через какой-либо из четырех корней g(X). Иными словами, это означает проверку следующего:

U(a) = U(a²) = U(a³) = U(a⁴) = 0.

Независимо выполнив вычисления для разных корней, получим следующее:

U(a) = a⁰ + a³ + a⁶ + a⁹ + a⁵ + a⁸ + a¹¹ =

= a⁰ + a³ + a⁶ + a² + a⁵ + a¹ + a⁴ =

= a¹ + a⁰ + a⁶ + a⁴ =

= a³ + a³ = 0,

U(a²) = a⁰ + a⁴ + a⁸ + a¹² + a⁹ + a¹³ + a¹⁷ =

= a⁰ + a⁴ + a¹ + a⁵ + a² + a⁶ + a³ =

= a⁵ + a⁶ + a⁰ + a³ =

= a¹ + a¹ = 0,

U(a³) = a⁰ + a⁵ + a¹⁰ + a¹⁵ + a¹³ + a¹⁸ + a²³ =

= a⁰ + a⁵ + a³ + a¹ + a⁶ + a⁴ + a² =

= a⁴ + a⁰ + a³ + a² =

= a⁵ + a⁵ = 0,

U(a⁴) = a⁰ + a⁶ + a¹² + a¹⁸ + a¹⁷ + a²³ + a²⁹ =

= a⁰ + a⁶ + a⁵ + a⁴ + a³ + a² + a¹ =

= a² + a⁰ + a⁵ + a¹ =

= a⁶ + a⁶ = 0.

Эти вычисления показывают, что, как и ожидалось, кодовое слово, выражаемое через любой корень генератора g(X), должно давать нуль.

8.1.6. Декодирование Рида-Соломона

В разделе 8.1.5 тестовое сообщение кодируется в систематической форме с помощью кода Рида-Соломона (7, 3), что дает в результате полином кодового слова, описывае­мый уравнением (8.26). Допустим, что в ходе передачи это кодовое слово подверглось искажению: 2 символа были приняты с ошибкой. (Такое количество ошибок соответ­ствует максимальной способности кода к коррекции ошибок.) При использовании 7- символьного кодового слова модель ошибки можно представить в полиномиальной форме следующим образом:

е(Х) = ^У*Ге„Х^п. (8.28)

п = О

Пусть двухсимвольная ошибка будет такой, что е(Х) = 0 + ОХ + ОХ² + а²Х³ + а⁵Х* + OX⁵ + 0Х⁶ =

(8.29)

= (ООО) + (000)Х + (ООО)Х² + (001)Х³ + (11DX⁴ + (000)Х⁵ + (ООО)Х⁶.

Другими словами, контрольный символ искажен 1-битовой ошибкой (представленной как а²), а символ сообщения — 3-битовой ошибкой (представленной как а⁵). В данном случае принятый полином поврежденного кодового слова г(Х) пред­ставляется в виде суммы полинома переданного кодового слова и полинома модели ошибки, как показано ниже.

г(Х) = U(X) + е(Х) (8.30)

Следуя уравнению (8.30), мы суммируем U(X) из уравнения (8.26) и е(Х) из уравне­ния (8.29) и имеем следующее:

г(Х) = (100) + (001)Х + (011)Х² + (100)Х³ + (lOl)X⁴ + (110)Х⁵ + (111)*⁶ =

= ос⁰ + а²Х + а⁴Х² + а°Х³ + а⁶*⁴ + а³Х⁵ + а⁵*⁶. (8.31)

В данном примере исправления 2-символьной ошибки имеется четыре неизвест­ных — два относятся к расположению ошибки, а два касаются ошибочных значений. Отметим важное различие между недвоичным декодированием г(Х), которое мы пока­зали в уравнении (8.31), и двоичным, которое описывалось в главе 6. При двоичном декодировании декодеру нужно знать лишь расположение ошибки. Если известно, где находится ошибка, бит нужно поменять с 1 на 0 или наоборот. Но здесь недвоичные символы требуют, чтобы мы не только узнали расположение ошибки, но и определи­ли правильное значение символа, расположенного на этой позиции. Поскольку в данном примере у нас имеется четыре неизвестных, нам нужно четыре уравнения, чтобы найти их.

8.1.6.1. Вычисление синдрома

Вернемся к разделу 6.4.7 и напомним, что синдром — это результат проверки чет­ности, выполняемой над г, чтобы определить, принадлежит ли г набору кодовых слов. Если г является членом набора, то синдром S имеет значение, равное 0. Любое нену­левое значение S означает наличие ошибок. Точно так же, как и в двоичном случае, синдром S состоит из п-к символов, {5,} (/ = 1,..., п - к). Таким образом, для нашего кода (7, 3) имеется по четыре символа в каждом векторе синдрома; их значения мож­но рассчитать из принятого полинома г(Х). Заметим, как облегчаются вычисления благодаря самой структуре кода, определяемой уравнением (8.27).

Из этой структуры можно видеть, что каждый правильный полином кодового слова U(X) является кратным полиномиальному генератору g(X). Следовательно, корни g(X) также должны быть корнями U(X). Поскольку г(Х) = U(X) + е(Х), то г(Х), вычисляемый с каждым корнем g(X), должен давать нуль, только если т(Х) будет правильным кодовым словом. Любые ошибки приведут в итоге к ненулевому результату в одном (или более) случае. Вычисления символов синдрома можно записать следующим образом:

S, =г(Х)

Здесь, как было показано в уравнении (8.29), г(Х) содержит 2-символьные ошибки. Если г(Х) окажется правильным кодовым словом, то это приведет к тому, что все сим­волы синдрома S, будут равны нулю. В данном примере четыре символа синдрома на­ходятся следующим образом:

5, = г(а) = а⁰ + а³ + а⁶ + а³ + а¹⁰ + а⁸ + а¹¹ =

= а° + а³ + а⁶ + а³ + а² + а¹+а⁴= (8.33)

= а³,

52 = г(а²) = а⁰ + а⁴ + а⁸ + а⁶ + а¹⁴ + а¹³ + а¹⁷ =

= а⁰ + а⁴ + а¹ + а⁶ + а⁰ + а⁶ + а¹ = (8.34)

= а⁵,

53 = г(а³) = а⁰ + а⁵ + а¹⁰ + а⁹ + а¹⁸ + а¹⁸ + а²³ =

= а⁰ + а⁵ + а³ + а² + а⁴ + а⁴ + а² = (8.35)

= а⁶,

S₄ = г(а⁴) = а⁰ + а⁶ + а¹² + а¹² + а²² + а²³ + а²⁹ =

= а⁰ + а⁶ + а⁵ + а⁵ + а¹ + а² + а¹ = (8.36)

= 0.

Результат подтверждает, что принятое кодовое слово содержит ошибку (введенную нами), поскольку S Ф 0.

Пример 8.3. Повторная проверка значений синдрома

Для рассматриваемого кода Рида-Соломона (7, 3) модель ошибки известна, поскольку мы выбрали ее заранее. Вспомним свойство кодов, обсуждаемое в разделе 6.4.8.1, когда была введена нормальная матрица. Все элементы класса смежности (строка) нормальной матрицы имеют один и тот же синдром. Нужно показать, что это свойство справедливо и для кода Рида-Соломона, путем вычисления полинома ошибок е(Х) со значениями корней g(X). Это должно дать те же значения синдрома, что и вычисление г(Х) со значениями корней g(X). Другими словами, это должно дать те же значения, которые были получены в уравнениях (8.33)—(8.36).

S,= r(X)

5, = [U(X) + e(X)]

X = a'

5, = г(а') = U(a') + e(a') = 0 + e(a') Из уравнения (8.29) следует, что е(Х) = ОЙГ³ + а'Х⁴, поэтому

S\ = e(a*) = a⁵ + a⁹ =

= a⁵ + a² =

= a³,

S₂ = e(a²) = a⁸ + a¹³ = = a¹ + a⁶ =

= a⁵,

53 = e(a³) = a^u + a¹⁷ =

= a⁴ + a³ =

= a⁶,

54 = e(a⁴) = a¹⁴ + a²¹ =

= a° + a° =

= 0.

Из этих результатов можно заключить, что значения синдрома одинаковы — как получен­ные путем вычисления е(Х) со значениями корней g(X), так и полученные путем вычисле­ния г(Х) с теми же значениями корней g(X).

8.1.6.2. Локализация ошибки

Допустим, в кодовом слове имеется v ошибок, расположенных на позициях Х^л, X^h,..., X^Jv. Тогда полином ошибок, определяемый уравнениями (8.28) и (8.29), можно записать следующим образом:

е(Х)=е, X^h + е, Х^>2 +...+е, X^lv. ’ h h.

Индексы 1, 2,..., v обозначают 1-ю, 2-ю,..., v-ю ошибки, а индекс j — расположе­ние ошибки. Для коррекции искаженного кодового слова нужно определить каждое значение ошибки е_}1 и ее расположение X^Jl, где I = 1, 2,..., v. Обозначим номер ло-

катора ошибки как |3_; =а^л. Далее вычисляем n-k=2t символа синдрома, подставляя а, в принятый полином при i = 1, 2,..., 2г.

У нас имеется 21 неизвестных (г значений ошибок и г расположений) и система 2/ уравнений. Впрочем, эту систему 2/ уравнений нельзя решить обычным путем, по­скольку уравнения в ней нелинейны (некоторые неизвестные входят в уравнение в степени). Методика, позволяющая решить эту систему уравнений, называется алго­ритмом декодирования Рида-Соломона.

Если вычислен ненулевой вектор синдрома (один или более его символов не равны ну­лю), это означает, что была принята ошибка. Далее нужно узнать расположение ошибки (или ошибок). Полином локатора ошибок можно определить следующим образом:

о(Х) = (1 + Р,Х)(1 + р₂Х)... (1 + РД) = = 1 4- 0[Х + <7₂Х² 4-... 4- G_VX*.

Корнями о(Х) будут 1/р„ 1/р₂,..., 1/р„. Величины, обратные корням о(Х), будут представлять номера расположений моделей ошибки е(Х). Тогда, воспользовавшись авторегрессионной техникой моделирования [5], мы составим из синдромов матрицу, в которой первые t синдромов будут использоваться для предсказания следующего синдрома:

5,	$2	S3
52	S3	S<
S,-i	s.	S'+i
S,	S'+i	S'+2

	Q		-5° +
	0,-1		~St + 2
	o2		~ ^2, _i
	6"		.~s2t

S,

+ 1

^}21-2

>21-1

Мы воспользовались авторегрессионной моделью уравнения (8.40), взяв матрицу наибольшей размерности с ненулевым определителем. Для кода (7, 3) с коррекцией двухсимвольных ошибок матрица будет иметь размерность 2 х 2, и модель запишется следующим образом:

(8.41)

Чтобы найти коэффициенты о, и о₂ полинома локатора ошибок o(.Y), сначала не­обходимо вычислить обратную матрицу для уравнения (8.42). Обратная матрица для матрицы [А] определяется следующим образом:

, _r, cofactor f A]

Inv A =----------- p—:—*■.

^{1 J} det [A]

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

= a³a⁶ - a⁵a⁵ = a⁹ + a¹⁰

а	а^5'		р О*	а^5'
а^5	Р	II	а^5	СП

2 3 5 = a +or =a

cofactor

			а^6 а^5
в \	а^5		а^5 а^3	-а^5	а^6	а^5
а^5	а^6		а^5	— U	I я	а^3

Inv

Р О*	Я			я		а^1	Р О
а^5	а^3,		г-	а^5		О в	а^5

= a²

Проверка надежности

Если обратная матрица вычислена правильно, то произведение исходной и обратной матрицы должно дать единичную матрицу:

а^1	а^0		а^4 + а^5	а^3 + а^10			0'
г ^s=	а^5		а^6 + а^б	а^5 + а^п

a a

a a

С помощью уравнения (8.42) начнем поиск положений ошибок с вычисления ко­эффициентов полинома локатора ошибок а(Х), как показано далее.

	а^6		а^7		О в 1.
	О		а^6		Р О*

a a

a a

Из уравнений (8.39) и (8.47)

а(Х) = а⁰ + а,Х + а₂Х² =

---

Дата добавления: 2015-10-28