Радиоэлектронные системы Основы построения и теория. Справочник . Под ред. Я.Д. Ширмана (2007) (1151789), страница 212
Текст из файла (страница 212)
Достоинство описанной процедуры состоит в возможности сведения арифметических операций над числами, особенно операций умножения, к аналогичным операциям над более простыми остатками (см. разд, 19.9). Китайскую теорему об остатках для чисел используют иногда для восстановлемия истинной дальности (скорости) по ряду неоднозначных ее отсчетов (см. разд.
23.5.3). 28.2А. Китайская теорема об остатках для многочленов Аналогична теореме об остатках для чисел. Пусть задана система взаимно простых многочленовделителей (модулей) т, (л), 7' = 1, 2,, /г, произведение которых равно т(л). Пусть далее остатки от деления произвольного миогочлема 9(л) на взаимно простые мо- 471 дули т,(з) известны и равны Д,(з). Многочлен с/(з) может быть восстановлен по остаткам (вычетам) согласно формуле л ц(з) = ~ Е,(з)Д,(з) (шобт(з)), (28.6) где С,(з) = /!/,(з) Мс(з) (шос( т(з)), М,(з) = т(з)/т,(з), /Ц,(з) Мс(з) = 1 (шос! т,(з)) .
(28.7) 28.2.6. Примеры еосстаноепения иногочленое по остаткаи Используются в разд. 19.9 для пояснения быстрых цифровых сверток. г Пример 1. т(з) = з — 1. В этом случае А. = 2, тс(з) = = з — 1 = Мг(з), тг(з) = з + 1 = М!(з), Сравнения (28.7) принимают вид (3 + 1) /3/1(з) = ! (шоб (з — 1)), (з — 1) /3/г(з) = 1 (шос1 (з+ 1)) . Сомножителы + 1 в левой части первого из них при делении на модуль з — 1 дает в остатке 2, а сомножитель з — 1 в левой части второго сравнения при делении на модуль (з + 1) дает в остатке — 2, что позволяет перейти к эквивалентным сравнениям: 2/ц!(з) = 1 (снос! (з — 1)), -2!цг(з) = 1 (!пос) (з + 1)) .
Отсюда /3/12(з) = ~1/2, Е! г(з) = Цз а 1)/2, з+1 з-1 г с/(з) = — Я(з) — — Дг(з) (снос! (з — 1)). (28.8) 2 2 Проверка результата. По формуле (28.8) может быть восстановлен многочлен меньшей, чем з, степени, г с/(з) = с/!з + с/о. Остатки от деления его на модули з ~ 1 составляют Д! г = с/о е с/!. В соответствии с (28.8), действительно, с/(з) = Е з + цо Прил!ар 2 т(Я) = з(з — 1)(з + а). Здесь а число 0 < а < ьэ.
В разд. 19.9 используются значения а = 1 и а -+ о. И в том и в другом случае !с = 3, т !(з) = з, тг(з) = з — 1, тз(з) = з + а, М!(з) = (з — !)(л + а), Мг(з) = з(з + а), Мз(з) = з(з — 1). Сравнения (28.7) принимают вид: (з — 1)(з + а) У1(з) = 1 (шоб л), з(з + а) /с/г(з) = 1 (и!ос1 (з — 1)), з(з — 1) сзсз(з) = 1 (шос1 (з + а)) . Поскольку (з — 1)(з+ а) = -а(снос! з), з(з ь а) = а ь 1 (шос1 (з — 1)), з(з — 1) = а -ь а (шос1 (з + а)), то справедливы сравнения по соответствующим про- стым модулям: У!(з) = — 1/а, /3/г(з) = Па + 1), й/з(з) = 1/а (а + 1) .
Согласно (28.6) по произведению простых модулей т(з) справедливо сравнение (з — 1)(з + а) 9(в) = - й(з)+ (28.9) з(з + а) з(з — 1) а+1 а(а+ 1) Проверка результата. Остатки деления трехчлена г с/(з) = цгз + с/1з + с/о на простые модули з, з — 1, з + а при а -+ со характеризуются соотношениями: 01(з) с/о Рг(з) с/г + 9! + цо 1!ш [03(з)/аг] цг. Подстановка приведенных значений в (28.9) восстанавливает трехчлен. 3 Пример 3. т(з) = з — 1. Для вещественных з в этом случае /с = 2, т!(з) = а — 1, тг(з) = з + з е 1. г Сравнения (28.7) принимают вид (з +э+1)!У!(з) = 1 (и!од(з — 1)), г (з — 1) /3/г(з) = 1 (шос! (з + з+ 1)), г откуда /3/!(3) = 1/3, Уг(з) = -(3+ 2)/3 .
Тогда /.!(з) = (з + э+ 1)/3, /г(з) =-(з — 1)(з+ 2)/3, г так что 3 +5+1 зг+з-2 з ц(з) = . 9(з)- Дг(з) (шос1(з — 1)). 3 3 (28.10) 28.3. Поля Галуа По определению (разд. 28.1), включают конечное число элементов (целых чисел„многочленов и т.д.). Пюбыч поляч, в отличие от колец, присусца операция деления.
Поэтому наряду с положительными степенями элементов существуют отрицательные, а значит, не всякое кольцо с конечным числом элементов р обладает свойствами поля. Число элементов поля Галуа р обязательно просэпое (простые поля Гаэуа б/г (р)) либо степень простога числа р = 2, 3, 4, ... (расширенные поля Гаэуа бг (ри)). 2В.3.1. Простые числовые поля Галуа Операции над элементами поля бг" (р) сводятся к операциям над вычетами этих элементов по модулю р. В любом таком поле существует ненулевой примитивный элемент а, такой, что все остальные ненулевые элементы являются его степенями.
Так, в поле бг" (7) с числом 7 — 1 = 6 ненулевых элементов справедливы следующие сравнения по модулю семь; 3 = 3,3 =2, 3 =6,3 =4,3 = 5,3 =1 (спод7), ! г 3 4 5 б откуда видно, что число 3 является примитивнь!м элементом поля бг (7). Показатели степени примитивных элементов выполняют роль обычных логарис/элсовс 1о833 =1, !ойз 2= 1ойз 3'=2, 1о836= 1о833 =3 (шоб7).
.3 При перемножении ненулевых элементов поля Галуа показатели степени его примитивньсх элементов складываются, при делении вычитаются так же, как в наи- 472 более распространенных числовых полях с бесконечным числом элементов. Сложение и вычитание показателей в СЕ (р) производится па,чодулю числа ненулевых элементов р — 1, в рассмотренном частном случае по модулю 6 = 7 — 1. Как уже отмечалось, в связи с допустимостью операций деления наряду с положительными степенями используют отрицательные. Так, в поле СЕ(7) значение 3 =4,поскольку 3 4=3 3 =3 =1.
-2 2 2 4 6 Число примитивных элементов поля СЕ (9). Определяется функцией Эйлера ж(9 — 1) (разд. 28.2.2), независимо от того, является ли д первой или высшей степенью простого числа р. Так, для поля Галуа СЕ (7) имеются два примитивных элемента ж(6) = 6 1 — 1 — — =2. Кроме указанного уже примитивного элемента 3, примитивен также элемент 5. Действительно, по модулю семь справедливы сравнения 5 = 5, 5 = 4, 5 = 5 .5 = 6, 5 = 2, 5 = э, 5 = 1. ! 2 3 ! 2 4 5 6 По-прежнему ненулевые элементы поля 1, 2, 3, 4, 5, 6 являются различными степенями примитивного элемента, здесь элемента 5. Любой не равный 3 и 5 элемент поля СЕ (7), например элемент 2, свойством примитивности не обладает.
Действительно, по модулю сечь: 2 =2,2 =4,2 = 1,2 =2 2 =2,2 =4,2 = 1. ! 2 3 4 3 ! 5 6 Элементы поля 3, 5, 6 не сводятся в данном случае к степеням элемента 2. Число примитивных элементов поля Галуа СЕ (9) возрастает с увеличением д, хотя и не очень быстро. Так, для простого поля Галуа СЕ (11) примитивны четыре элемента поля: т(10) = 1О 1- — 1- — =4.
Как нетрудно проверить описанным выше способом, зто элементы 2, 6, 7, 8. Указанные особенности примитивных элементов имеют практическое значение в технике РЭС, например, при выборе вариантов частотной н фазовой манипуляции сигналов (см, разд. 18.5, 18.6). Поля Ферма и Мерсенна. Это частные случаи простых числовых полей Галуа, описываемых выражением СЕ (2! е. 1).
Их называют полями Ферма при знаке плюс и полями Мерсенна при знаке минус в приведенном выражении. Существуют при значениях показателей степени р, для которых числа 2" е 1 простые. Это показатели: ° р = 2, 4, 8, 16, ... для простьгх чисел Ферма 5, 17, 257, 65 537, ° р = 3, 5, 7, 13, 17, 19, 31 для простых чисел Мерсенна 7, 31, 127, 8191, 131 071, 524 287, 2 147 483 647. Поля Ферма и Мерсенна используются в цифровой обработке сигналов, основанной на теоретико-числовых преобразованиях (см. разд.
19.9.6 и 28.3.5). Совместно с другими простыми полями Галуа они используются также при выборе законов частотной манипуляции (см. разд. 18.5). 28.3.2. Расширенные поля Галуа Многочленное представление элементов поля. Элементы полей СЕ (р~) описывают не только числами, но и многочленами степенью не выше р — 1 и-! 9 = ~~',ахл ь 2=0 (28. 11) с коэффициентами ах = О, 1, ..., р — 1 из простого поля Галуа СЕ !р). При р=! многочлен вырождается в число. Сложение многочлеиов сводится к сложению их коэффициентов по модулю простого числа р, что сводит сумму к одному из элементов поля Галуа СЕ (р ) Умножение (без рекомендуемого перехода к степенному представлению) проводят по двойному.чодулю (пюдЯл), шод р) .
Таблица 28.1. Неиулевьге элементы паля Галуа СЕ(2 ) Двоичное обозначение Многочленное обозначение Степенное обозначение Десятичное обозначение а =а о 001 010 100 О1! !1О 1!! !О! 00! а =а а =а 4+1 Л +4 2 а'=а а =а з -2 а'=а 4 +1 1 а =а' Пример степенного и двоичного представлений расширенного поля Галуа СЕ(2 ) = бЕ(8). Представлен в табл. 28.2.
Примитивным элементом поля являет- 473 В качестве функцииЯл) выбирают многочлен степени р с коэффициентами из поля СЕ (р), который не делится без остатка ни на один элемент поля СЕ (р): Яз) = 2 3 = л + з + 1 для поля СЕ'(2 ), Ял) = з + л + 1 для поля СЕ (2 ), Яз) = л + л + 1 для поля СР (2 ). 3 4 4 Числовые представления элементов поля.
Не исключается и трактовка элементов поля СЕ (р") как чисел. Набор коэффициентов каждого многочленного элемента поля, взятый в порядке убывания индексов коэффициентов аи 1, аи 2, ..., ао (28.11), можно рассматривать как обозначение некоторого числа в р-ричной системе счисления. От р-ричного обозначения элементов поля можно перейти к десятичному. Наличие примитивных элементов расширенных полей Галуа позволяет вводить, как и дяя простых полей, степенные представления. При любом представлении число ненулевых элеменгов поля СЕ (р ) является степенью р простого числа р, часто числа р = 2. и Пример различнык представлений расширенного поля Галуа СЕ(2 ) = бЕ(8). В табл.
28.1 представлены 3= ненулевые элементы поля в степенном, многочленном, двоичном и десятичном обозначениях. Примитивным элементом поля СЕ (8) является здесь в многочленном обозначении элемент л = 0 л + 1 з + О, т.е. 010 в двоич- 2 ном обозначении или 2 в десятичном обозначении, что обеспечено надлежащим выбором многочленаЯл).
ся здесь элемент а = 0010 в двоичном обозначении, 2 в десятичном обозначении или л — в степенном. Таблица 28.2. Ненулевые элел|ентсв поля Галуа ОХ (2') Операции сложения и умножения при числовом представлении расширенных полей Галуа СР (2 ) = = СЕ (4). Слагаемые (сомножнтели) содержатся в первых строке и столбце табл. 28.3 (28.4), суммы (произведения) находятся на перекрестиях.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
