Скляр Б. Цифровая связь (2003) (1151859), страница 106
Текст из файла (страница 106)
Степенью полинома называется степень члена максимального порядка. Обозначим каждый ненулевой элемент ОР(2") полиномом ! а,(Х), в котором по крайней мере т коэффициентов а,(Х) ненулевые. Для ! = О, 1, 2, ..., 2 — 2, нулевым остатком и ненулевым частным. Обычно полипом записывают в порядке возрастания степеней.
Иногда более удобным является обратный формат записи (например, при выполнении полиномиального деления). Обраэующни алименты Хо Х! Х2 ав ! ! ! о л ав и а! 1 О О Рис. 8. 2 Отображение элементов лолл в базисные элементы ОР(8) с намотаю )(Х) = 1 + Х+ Х! Пример 8.1. Проверка полииома иа примитивность Основываясь на предыдущем определении примитивного полинома, укажите, какие из следующих нерелуцируемых полиномов будут примитивными. а) 1+Х+Х4 б) 1+Х+Х'+Х'+Х4 Рвтвние а) Мы можем проверил этот полинам порядка та4, определив, будет ли он делителем Х" +1= Х! и+1= Х!з+1 для значений л издиалазона1<л<15.
Нетрудно убедиться, что Х" + 1 делится на 1+Х+Х4 (см. раздел 6.8.1), и после повторения вычислений можно проверить, что при любых значениях л из диапазона 1 < л < 15 лилином Х" + 1 не делится на 1 + Х+ Х". Следовательно, 1 + Х+ Хь является примитивным полиномом. б) Легко проверить, что полинам является делителем Х" + 1. Проверив, делится ли Х" + 1 на 1+Х+ 2~+ Х'+ Х", лла значений л, меньших 15, можно также видеть, что указанный полинам является делителем Ха+1.
Следоватетьно, несмотря на то что полипом 1+ Х+ Х'+ Х'+ Х' является неприводимым, он не будет примитивным. 8.1.4.3. Попе расширения СР(2!) Рассмотрим пример, в котором будут задействованы примитивный полипом и конечное поле, которое он определяет. В табл. 8.1 содержатся примеры некоторых примитивных полиномов. Мы выберем первый из указанных там полиномов, ((Х) = 1+Х+Х', который определяет конечное поле ОР(2 ), где степень полинома т = 3. Таким образом, в поле, определяемом полиномом )(Х), имеется 2 =2'=8 элементов.
Поиск корней полинома((Х) — это поиск таких значений Х, при которыхЯХ)аО. Привычные нам двоичные элементы О и 1 не подходят полиному 1(Х) = 1+ Х+ Х' (они не являются корнями), э н е м и н 1 ы оооо аэ ! О О а'О ! О азов! аз ! ! О ал О поскольку Я1) = 1 и ЯО) = 1 (в рамках операций по модулю 2). Кроме того, основная теорема алгебры утверждает, что лелином порядка вэ должен иметь в точности вэ корней. Следовательно„в этом примере выражением) = О должно иметь 3 корня. Возникает определенная проблема, поскольку 3 корня не лежат в том же конечном поле, что и коэффициенты 7(х). А если они находятся где-то еще, то, наверняка, в поле расширения Сэг(25). Пусть а, элемент паля расширения, определяется как корень полиномаЯХ).
Следовательно, можно записать следующее: Яа) =О 1+а+а =О (8.16) а =-1 — а 2 Поскольку при операциях над двоичным полем +1 =-1, то а' можно представить следующим образом: а'=1+ а. (8.17) Таблица 8.1. Некоторые примитивные полиномы Таким образом, а' представляется в виде взвешенной суммы всех а-членов более низ- кого порядка. Фактически так можно представить все степени а. Например„рассмот- рим следующее: а4 а дэ д (1 +а) а 4 д2 (8.18,а) А теперь взглянем на следующий случай: 5 4 ( 2) 2+ Э (8.18,6) Из уравнений (8.17) и (8.18) получаем следующее; а =1+а+а.
Используя уравнение (8.18,в), получаем следующее: (8.18,в) а =а а =а. (1+а+а) =а+а +а =1+а. (8.18,г) 3 4 5 б 7 8 9 1О 12 ! 13 1+Х+Х' 1+ Х+Х" 1+ Х'+ Хэ 1+Х+Хэ 1+ Х'+ Х' 1+Х'+Х'+ Х'+Х' 1+Х44хэ 1+ Хэ+Хээ 1+Хэ+Х" 1+Х 4 Х44Х4+Хээ 1 4 Х+Хэ+Х44 Хээ 14 15 1б 17 18 19 20 2! 22 23 24 1+ Х+ Х'+ Хи + Х" 1+Х+Х" 1+ Х+ Х'+ Хо+ Хи 1+ Х'+ Х" 1+Хэ+Хэв 1+ Х+ Х'+ Х'+ Хв 1+ Х'+ Хи 1+ Х'+ 3~э 1 + Х+ Хэ' Хэ+ )(ээ 1 + Х+ Х'+ Х'+ Х" А теперь из уравнения (8.18,г) вычисляем а та.
а =а (1+а )та+а =1 та. 7 б 2 3 О (8.18,д) Заметьте, что а' = цо и, следовательно, восемью элементами конечного поля ОЕ(23) будут (8.19) () 0 1 2 3 4 5 б) Хз 3 Х1 Рис. 8.8. Отображение злемеитов поля в базисные элементы мохсно представить с памоибью схемы линейного регистра сдвига с обратной связью (1!пеаггеедбае зЬЯ гебииег — 7РЩ, построенною па примитивном полиноме Таблица 8.2. Таблица сложения для СР(8) приЯХ) = 1+ Х+ Х' цо О п4 а1 432 аз ггз О а1 аз аз а1 бх3 бхб я2 ссб ср сс4 а3 а1 О ц4 и' О цб аб О 3 а! а2 470 ц2 сбб аз цб а1 цз сР а' О аз пз аз а1 Отображение элементов поля в базисные элементы, которое описывается уравнением (8.14), можно проиллюстрировать с помощью схемы линейного регистра сдвига с обратной связью (!шеаг (еебЬаск зЫй ге8(пег — 1.ГЗВ) (рис.
8.8). Схема генерирует (при т = 3) 2" — 1 ненулевых элементов поля и, таким образом, обобщает процедуры, описанные в уравнениях (8.17) — (8.19). Следует отметить, что показанная на рис. 8.8 обратная связь соответствует коэффициентам полинома ЯХ) = 1+ Х+ Х', как и в случае двоичных циклических кодов (см. раздел б.7.5). Пусть вначале схема находится в некотором состоянии, например 1 О О; при выполнении правого сдвига на один такт можно убедиться, что каждый из элементов поля (за исключением нулевого), показанных на рис. 8.7, циклически будет появляться в разрядах регистра сдвига.
На данном конечном псле ОГ(23) можно определить две арифметические операции — сложение и умножение. В табл. 8.2 показана операция сложения, а в табл. 8.3 — операция умножения, но только лля ненулевых элементов. Правила суммирования следуют из уравнений (8.17) и (8.18д); и их можно доказать, обратившись к рис. 8.7, поскольку сумму двух элементов поля можно рассчитать путем сложения (во модулю 2) соответствуюьцих коэффициентов их базисных элементов. Правила умножения, указанные в табл.
8.3, следуют из обычной процедуры, в которой произведение элементов поля вычисляется путем сложения по модулю (2"-1) их показателей степеней или, для данного случая, по модулю 7. Таблица 8.3. Таблица умножения для Ср(8) приЯХ) = 1+ Х+ Хз гхб аз а2 а2 ггз гхз 4хб и' 424 п2 его а' а' а' п4 а2 426 а' его аз а2 а2 п4 624 п2 пз п2 ггз а2 а' п6 8.1.4.4. Простой тест для проверки полинома на примитивность Существует еше один, чрезвычайно простой способ проверки, является ли полипом примитивным. У нередуцируемого полинома, который является примитивным, по крайней мере, хотя бы олин из корней должен быль примитивным элементом. 11римигллвлыл2 элементом называется такой элемент поля, который, будучи возведенным в более высокие степени, даст все ненулевые элементы поля.
Поскольку данное поле является конечным, количество таких элементов также конечно. Пример 8.2. Примитивный полипом должен иметь, по крайней мере, хотя бы одни прюинтивный элемент Найдите гл = 3 корня полинома ЯХ) = 1+Х+ Х' и определите, примитивен ли полипом. Для этого проверьте, имеется ли среди корней полинома хотя бы один примитивный элемент. Каковы корни полинома? Какие из них примитивны? РгигяиЕ корни будут найдены прямым перебором. итак, а0 = 1 не будет корнем, поскольку Япе) = 1. теперь, чтобы проверить, является ли корнем а2, вкпользуемся табл.
8.2. Псскольк?Яа) = 1+ а ь аз = 1+ а0= О, значит, а будет корнем палинома. Далее поверим, будет ли корнем с22. Япз) = 1+ а2+ а6 = 1+ а0 = О. Значит, и а2 таске будет корнем пслннома. Теперь проверим аз. фаз) = 1+ аз+ аз = 1+ аз = а446 0. Следовательно, аз корнем полинома не является. Будет ли корнем аь? Яа4) = а22+ а4+ 1 = 1+ а0= 0 Да, п4 будет корнем полинома. Значит, коргыми полиномаЯХ) = 1+ Х+ Х' будут о. а' н а4. Нетрул24о убедиться, что последовательно возводя в степень любой из этих корней, можно получил, все 7 ненулевых элементов поля.
Таким образом, все корни будут примитивными элементами. Поскольку в определении требуется, чтобы по крайней мере один из корней был примитивным, полипом является примитивным. В этом примере описан относительно простой метод проверки полинома на примитивность. Для проверяемого полинома нужно составить регистр ЕЕЗК с контуром обратной связи, соответствующим коэффициентам полинома, как показано на рис.
8.8. Затем а схему регистра следует загрузить любое ненулевое состояние и выполнять за клждый такт правый сдвиг. Если за один период схема сгенерирует все ненулевые элементы поля, то данный полипом с полем ОР(2") будет примитивным. 8.1.5.
Кодирование Рида-Соломона В уравнении (8.2) представлена наиболее распространенная форма кодов Рида- Соломона через параметры л, 1, г и некоторое положительное число гл > 2. Приведем это уравнение повторно: (8.2О) (п„(с) = (2" — 1, 2 — 1 — 22). Здесь л — Л = 2г — число контрольных символов, а г — количество ошибочных битов в символе, которые может исправить код. Генерирующий полипом для кода Рида- Соломона имеет следующий вид: 8(Х) =Хе+у Х+хбХ + ... +Хб 1хе +Х~. (8.21) Степень полнномиального генератора равна числу контрольных символов.
Коды Рида-Соломона являются подмножеством кодов БХЧ, которые обсуждались в разделе 6.8.3 и показаны в табл. 6.4. Поэтому связь между степенью полиномиального генератора и числом контрольных символов, как и в кодах БХЧ, не должна оказаться неожиданностью. В этом можно убедиться, подвергнув проверке любой генератор из табл. 6.4. Поскольку полиномиальный генератор имеет порядок 26 мы должны иметь в точности 2г последовательные степени а, которые являются корнями полинома. Обозначим корни 8(Х) как: а, а', ..., аь. Нет необходимости начинать именно с корня а, это можно сделать с помощью любой степени а. Возьмем к примеру код (7, 3) с возможностью коррекции двухсимвольных ошибок.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
