Радиоэлектронные системы Основы построения и теория. Справочник . Под ред. Я.Д. Ширмана (2007) (1151789), страница 211
Текст из файла (страница 211)
469 28. ЭЛЕМЕНТЫ ОБЩЕЙ АЛГЕБРЫ И ТЕОРИИ ЧИСЕЛ Используются в разделах Справочника: ° при цифровой обработке сигналов (см. разд. 19.9); ° при кодировании и декодировании передаваемой информации (см. разд. 24.4 — 24.8); ° при выборе законов модуляции (кодирования) локационных зондирующих сигналов (см. разд. 18А — 18.6, 23.2-23.4, 23.5.3). 28.1. Основные понятия 28.1.1.
Понятие общей (абспз ракп>ной) алгебры Относится к учению об операциях над любыми систематизированными математическими объектами. Примерами систем таких объектов являются системы целых чисел, вещественных чисел, многочленов (полиномов), векторов, матриц и т.д. Внимание фиксируется на особенностях проводимых над объектами математических операций. Системы классифицируются по характеру этих операций, иначе, по их алгебраической структуре, что позволяет отвлекаться от природы математических объектов.
Так, для известного тождества элементарной алгебры (а + Ь) = (а + Ь) (а + Ь) = а + 2 аЬ + Ь 2 2 2 несущественно, принадлежат ли а и Ь к вещественным или к комплексным числам. Существенно зато, что при выводе приведенного соотношения предполагалась возможность проведения операций и сложения, и умножения, использовались свойства дистрибутивности (а + Ь)с = ас + Ьс и коммутативности Ьа = аЬ проводимых операций. Поскольку коммутативность умножения матриц в общем случае отсутствует, матрицы как математические объекты должны быть отнесены в алгебраическую структуру, отличаюшуюся от вещественных или комплексных чисел. Целесообразность изучения общих особенностей алгебраических структур определяется тем, что проще совместно рассмотреть системы с общей алгебраической структурой, чем рассматривать каждую из систем в отдельности. Результаты, известные для одной из систем, распространяются при этом на другие системы с той же структурой !2.37, 2.87, 4.28, 6.74, 8.10, 8.23).
28.1.2. Математические системы общей алгебры Это группы, кольца, поля и т.д. Группа. Зто множество элементов с определенной, часто обозначаемой знаком *, операцией для каждой пары элементов, которое обладает свойствами: ° замкнутости, т.е, получения в результате операции элемента той же группы; ° ассоциативности а * Ь в с = (а * Ь) в с = а * (Ь * с); ° существования единичного (нейтрального) элемента а', такого, что а * д = а * а = а для каждого а; ° существования для каждого а обратного элемента Ь, такого, что а * Ь = а.
Группа Абеля. Отличается коммутативиостью проводимой в ней операции а * Ь = Ь ' а. Операцию часто обозначают знаком плюс а + Ь = Ь + а и называют операцией сложения (сложением). Нейтральмый эле- 470 мент группы по определению существует, его называют при сложении нулем. Обратный а элемент по определению также существует, его обозначают при сложении -а. Обозначения дополняют, если наряду с операцией сложения вводятся другие операции. Кольцо. Зто группа Абеля по операции сложения, обладающая некоторой дополмительной операцией.
Ее обычно называют операцией умножения (умножением) и часто обозначают соседним расположением элементов аЬ или а . Ь. Постулируют: замкнутость; ассоциативность и дистрибутивность совокупности операций сложения и умножения (а + Ь)с = ас + Ьс (разд. 28.2). Обратный а по операции умножения элемент, обозна-! чаемый а, и, даже, единичный (нейтральный) по этой операции элемент могут не существовать. Поле. Это кольцо, ненулевые элементы которого образуют групп> Абеля па операции умножения. И еди-! ничный элемент и обратный а элемент а по умножению в ней, следовательно, сушествуют.
Существуют -1т -е поэтому отрицательные степени (а ) = а элементов с показателями степени т из поля. Примерами полей с бескомечным числом элементов являются поля рациональных, вещественных и комплексных чисел. Поле Галуа. Это поле СзЕ (д) с калечны.м числам д элементов (см. разд. 28.3). Сравнительная характеристика введенных понятий. Абелева группа — это множество, элементы которого можно складывать и вычитать, кольцо — множество, элементы которого можно складывать, вычитать и умножать, поле — множество, элементы которого можно складывать, вычитать, умножать и делить. Поле Галуа— это поле с конечным числом элементов (конечное поле).
28.2. Кольце целых чисел и многочленов Целые числа (вместе с известными для них операциями) удовлетворяют определению кольца. Сложение, вычитание и умножение возможны всегда, другие условия отнесения этой системы к кольцам соблюдаются. Деление возможно не всегда, поскольку правильная дробь целым числом не является. Зато возможно деление с остатком. Остаток в теорию чисеч называют вычетом по тодучю делителя. Соотношение для остатков от деления на модули называют сравнениями. Сравнения 13 = 1 (той 4), 9 = 1 (глод 4), — 3 = 1 (пюд 4) означают, что числа !3 = 43+ 1, 9 = 42+ ! и — 3 = — !.4 + 1 имеют один и тот же остаток 1 при делении на 4, иначе, один и тот же вычет 1 по модулю 4. Перечисленные определения переносятся на многочзепы (полиноты) с целыми показателями степени переменной и коэффициентами из поля (илн, как говорят, кнад полем») вешественных или комплексных чисел. В частности, для многочленов могут использоваться сравнения вида 4 3 г л + 2л = л + з + 1 = 2з + ! (пюд (з — 1)), поскольку остатки от деления з + 2з = (з — 1) + 2з + 1 и 4 4 з + з ь 1 = (з — 1)з + 2з + 1 на з — 1 равны 2з ь !.
3 2 2 Справедливы и другие аналогии колец целых чисел с многочленами. Так, вводятся простые чисза р = 2, 3, 5, 7, 11, 13„..., которые делятся только на ер и на я1. Вводятся и ненулевые многочлены р(з), делящиеся только на ~р(л) и на ненулевые числа, которые называют неприводичыми многочленаии. Если коэффициент при старшем члене неприводимого многочлена равен единице, его называют простым.
Числа и многочлеиы, не являющиеся простыми (не- приводимыми), разлагаются на .иножитвли. Из этих множителей н для чисел, н для многочленов могут составляться наибольшие общие делитези (НОД) и наименьшие общие кратные (НОК). Так, для чисел 12 = = 2 2 3 и ! 5 = 3 5 значение НОД = 3, а значение НОК = = 2 2.3 5 = 60. Для многочленов л — Зл + 2 = (л — 1) (л — 2) и л + л — 2 = (л — 1) (л + 2) г г значение НОД = л — 1, а значение НОК = (л — ! ) (л — 2) (л ь 2). Числа и многочлены называют взаимно простыни, если их НОД = 1.
Нахождение НОД облегчается при использовании алгоритма Евклида. 28.2.1. Алгоритм Евклида Обеспечивает вычисление НОД чисел (многочленов) за счет использования итеративной процедуры деления. Большее из двух чисел (многочлен старшей степени переменной л) делится на меньшее число (многочлен меньшей степени). В результате деления чаще всего выявляется остаток. С остатком оперируют как с меньшим числом, приняв за большее то число, которое раньше было меньшим, и повторяют процедуру. Итерации продолжаются до достижения деления без остатка.
Последний делитель и является НОД первоначально взятых чисел. Пусть, например, заданы числа 30 и 2!. Остаток от деления 30 на 21 равем 9. Остаток от деления 21 на 9 равен 3. Число 9 делится на 3 без остатка. Последний делитель является НОД. Аналогичный алгоритм справедлив и для многочленов. 28.2.2. Функция Эйлере Определяет количество положительных целых чисел к(п), которые не превышают положительного числа и и взаимно просты с и (причем число 1 в состав и включается). Используется в разд. 18.5.2, 18.6.3 Если и — простое число, то к(п) = п — !.
Если и является произведением целочисленных степеней двух простых и неравньгх единице чисел и = 1! 17 а!' а ', тогда среди меньших п чисел найдется и! = и/а! целых чисел, делящихся на а1, и пг = и/аг целых чисел, делящихся на аг. Как в состав п1, так и в состав пг входит п1г = п/а!аг целых чисел, делящихся и на а1, и на аг. Поэтому к(п) = и — (п1+ пг — п1г) = и 1 — — 1 —— а!)1, аг) Аналогично, если п представляет собой произведение з целочисленных степеней простых чисел и = 1, 17 а1'агз ...
а,'; то к(п) = п 1- — 1- — ... 1-— 28.2.3. Китайская теорема об остатках для чисел Сущность теоремы. Утверждает возможность однозначного восстановления неотрицательного целого числа ц, не превосходящего произведения некоторых попарно взаимно простых сотножипилей-делителей (моДУлей) ть по остаткал7 Д, от дслениЯ 7/ на эти модули: Д7 = 7/ (пзод т,). Возможность и алгоритм восстановления были известны еще в древнем Китае.
Восстановление проводится по формуле ц=~~ 17Я, (глод т). (28.1) 7=! Здесь и- число взаимно простых модулей, т — произведение всех этих модулей, /., — числовые коэффициенты. Они заранее вычисляются для выбранной системы модулей путем более трудоемкой, чем (28.!), процедуры. Согласно этой процедуре Е, = А/7 М7 (шод т), М, = т/ть (28.2) Число М, соответствует произведению модулей, дополняющих модуль ть Число Л', подбирают из условия А', М, = 1 (шод т7) . (28.3) Пример. Пусть выбрано /7 = 3 взаимно простых модуля: т! = 3, тг = 4, тз = 5.
Числа А7! определяются согласно (28.3) из сравнения по модулю 3: 207У! =! (шод3). Чтобы решить сравнение, достаточно перебрать т1 целых чисел, желательно наиболее близких к нулю, т.е. — 1, О, 1 (нли же О, 1, 2, если отрицательные числа исключаются). Сравнение удовлетворяется при 7У1 = — 1, откуда /,1 = -М1 = — 20. Аналогично А/г = -1„ 77/3 = -2, ьг = -1 15 = -!5, /3 = -2.12 = -24.
Соотношение (28.1) принимает внд 7/ = — 20Д1 — 15Дг — 24ДЗ (шоб 60) (28.4) или, что то же самое, д = 40Д! ь45 Дг +36 Ь/3 (шог( 60). (28.5) Особенности применении. В соответствии с (28.4), (28.5) может быть восстановлено любое неотрицательное число, меньшее 60, по остаткам от деления на модули 3, 4, 5. Например, по остаткам от деления числа 15 на модули 3, 4, 5, равным О, 3, О, и по остаткам от деления на эти же модули числа 56, равным 2, О, 1, эти числа восстанавливаются: 7/' = -20 0 — 15 3 — 24 0 = -45 ь 60 = 15 (пюд 60), 7/" = — 20 2 — 15.0 — 24 1 = -64 + 60.2 = 56 (пюд 60).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
