делит и правую. По индукции можно заключить, что если неприводимый многочлен / делит произведение нескольких многочленов, Wg\ то существует такое к, что / делит g*. Наконец, если

и g* неприводимы и Ц/< = \\g\ то каждый делит некоторый

T(ft)

а каждый g делит некоторый так что разложение любого

многочлена в произведение неприводимых сомножителей единственно с точностью до порядка сомножителей и выбора скалярных множителей. Это эквивалентно следующей теореме:

2.14. Теорема. Любой нормированный многочлен над полем F однозначно записывается в виде произведения нормированных неприводимых многочленов над F.

Этот результат справедлив для любого поля F. Аналогом теоремы 2.14 для целых чисел является утверждение о том, что любое натуральное число, не равное 1, однозначно представимо в виде произведения простых сомножителей.

Так как степень произведения многочленов равна сумме их степеней ), то, очевидно, любой многочлен первой степени неприводим. Очевидно также, что многочлен степени d не может иметь более чем d линейных делителей. Более того, мы утверждаем, что линейный многочлен х - I, является делителем многочлена / {х) тогда и только тогда, когда / {\) = О, т. е. тогда и только тогда, когда является корнем многочлена / {х). Действительно, равенство

/ {х) ={x-l)q {х) + г, где q {х) - частное, а г - остаток от деления / (ж) на {х - \), справедливо при всех x. Так как deg г <; deg (х - ), то г - константа. Полагая а: = , получим, что г = / (). Тем самым доказана

2.15. Теорема. Многочлен степени d над полем F в любом поле, содержащем F, имеет не более d корней.

Заметим, что теорема 2.15 неверна для многочленов с коэффициентами из кольца 2). Например, квадратный многочлен - 1 имеет четыре корня в кольце классов вычетов по модулю 15, а именно 1, 4, И и 14.

Такая ситуация, как правило, имеет место для составных модулей. Если pi - простые, а - произвольные положительные числа, то сравнение А mod \\р\ эквивалентно системе сравнений А =

= В mod p\i.

) Для того, чтобы даже при / = О выполнялось равенство deg (jg) = = deg f + deg g, мы должны принять следующее определение: deg О = - оо.

2) В кольце определены для любых двух элементов сумма, разность и произведение, но не всегда возможно деление на ненулевой элемент.- Прим. перев.

Таким образом, сравнение х = \ mod 15 эквивалентно паре сравнений х = I mod 5 и а: = 1 mod 3, каждое из которых имеет точно два решения. Следовательно, в результате имеются четыре решения: а: = ± 1 mod 3 и а: = ± 1 mod 5 с любой комбинацией знаков.

В общем случае решения сравнений по составному модулю описываются следующими утверждениями:

2.16. Китайская теорема об остатках для чисел. Для заданных простых чисел р, р, . . ., Pk и произвольные чисел Ci, Са, . . ., Cf, система сравнений А = Ci mod р1 имеет единственное решение по модулю \\р1

2.17. Китайская теорема об остатках для многочленов. Для заданных неприводимых многочленов /1>(а:), (а:), . • •» () " произвольных многочленов g (х), g<2 (х), . . ., g (а;) система сравнений h (х) = g> {х) mod [/<" (а;)]* однозначно разрешима относительно h {х) по модулю \\ {х)Ук

Доказательство (для многочленов). Так как многочлен W [/ {x)Yi не имеет с [/<*> {x)Yi нетривиальных общих делителей,

то, используя алгоритм Евклида, можно найти такой многочлен а(*>(а;), что а<Ч) П (а:)Г-= 1 mod [/<*(а:)]. Положим далее

h{x) = 2*() й*W П t/* Очевидно, для всех i при этом

выполняется сравнение h (х) = (а:) mod {x)Yk Если Я {х) также является решением этой системы уравнений, то Н (х) - h (х) делится на [/<*> (а:)] для всех i = 1, 2, . . ., к, так что Н (х) = = h{x) modfl [Г {х)Гш-

Доказательство китайской теоремы об остатках для чисел полностью повторяет приведенное выше рассуждение для многочленов.

Следствия из алгоритма Евклида для многочленов в основном аналогичны следствиям из алгоритма Евклида для чисел. Однако в деталях эти следствия существенно различны. Несмотря на это имеется один важный частный случай, в котором возможно построение прямого соответствия.

2.18. Теорема. Если число d - н. о. д. чисел тип, то над любым полем многочлен xf - I является н. о. д. многочленов х -1 и ж" - 1.

Доказательство. Запишем формулу геометрической прогрессии

(уд (г/-1) - S г/ -"S И = г/" -1-

t=0 i=l г=0

Полагая у =--- х- и умножая на х, получаем, что

х I S - 1) =-- xf-i+k - х.

Таким образом, шагу алгоритма деления для чисел г-2 = ahh-i соответствует равенство

/ft-2 l = {xh[ 2 {x-Y\]{x--i) + {X-i). t=0

Следовательно, ж* - 1 - остаток от деления x- - 1 на, ж-! - 1 для всех к и алгоритм Евклида для многочленов строится в прямом соответствии с алгоритмом Евклида для чисел. При г„ = О получаем /•<" = ж" - 1 = 0. Многочлен, полученный на предпоследнем шаге алгоритма, является н. о. д. исходных многочленов ж*"-1 и ж" - 1. .

Теоремы 2.14-2.18 очень важны, однако польза от варианта непрерывных дробей алгоритма Евклида не ограничивается этими теоретическими результатами. Он составляет также основу технической реализации одной из арифметических операций (деления), необходимых для декодирования БЧХ-кодов. Перейдем к рассмотрению этой реализации.

*2.2. Логические цепи )

Б логических устройствах используются три основных элемента «И», «ИЛИ» и инвертор «НЕТ». Они представлены на рис. 2.1. Элементы И и ИЛИ могут иметь несколько входов, на каждый из которых подается двоичный сигнал, принимаюш,ий значения О или 1. Выход элемента И равен нулю всегда, кроме случая, когда все входы равны единице; в этом случае выход элемента тоже равен единице. Выход элемента ИЛИ равен единице всегда, кроме случая, когда все его входы равны нулю; в последнем случае выход также равен нулю. Инвертор в противоположность элементам И и ИЛИ имеет только один вход, сигнал на его выходе противоположен сигналу на его входе: если входной сигнал имеет значение О, то сигнал на выходе принимает значение 1; если входной сигнал принимает значение 1, то сигнал на выходе равен 0.

) Разделы, отмеченные звездочкой, можно при нервом чтении пропустить.

Практические схемы, реализуюп1;ие логические свойства этих трех элементов, могут быть построены из транзисторов, сопротивлений, диодов, вакуумных ламп и других компонентов; в зависимости от конкретных свойств этих компонентов обш,ее устройство имеет

у = Лх,- УУх у = х

Рис. 2.1. Элементы «И», «ИЛИ» и «НЕ».

определенные ограничения - так называемые конструктивные ограничения. Примеры конструктивных ограничений дают максимальное допустимое число входов элементов И и ИЛИ и число элементов, удовлетворительное прохождение сигнала через которые не требует дополнительного усиления. Обычно схема инвертора содержит

у = (Xj Axj) V (Xj AXg)

= Xi®X2

Рис. 2.2. Двоичный сумматор с двумя входами.

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

Полезной комбинацией элементов И, ИЛИ и НЕ является двоичный сумматор с двумя входами, изображенный на рис. 2,2. Этот

элемент обозначается символом @.

Как показано на рис. 2.3, с помощью различных способов каскад-5 ного соединения двоичных сумма- ] торов с двумя входами можно по- строить двоичный сумматор с N входами. Независимо от способг каскадного соединения всегда tj буется N - i двоичных сумматоров с двумя входами, так каг каждый такой сумматор всего нг единицу уменьшает число суммин руемых сигналов. Однако cxeMsf рис. 2.3 (с), вообще говоря, боле< совершенна, чем схема рис. 2.3 (Ь) так как при таком соединении один из сигналов не должен прс ходить более, чем через 1 + log сумматоров с двумя входами.

Другой полезной комбинацие! элементов И, ИЛИ и НЕ являете! триггер, схема которого изображс на на рис. 2.4, Особенностью три1 гера является петля обратно связи, содержащая два инверто! и два элемента ИЛИ. Когда ci гналы на входах элементов ИЛ вне петли принимают значение то на одной стороне петли буд< сигнал 1, а на другой - 0. Ecj команда управления равна нул1 то сигналы во всей петле ociai постоянными независимо от сип ла на входе. Однако, если упра ляющая команда равна единш то в зависимости от сигнала входе один или другой из элеме тов ИЛИ (в соответствии с кс кретным значением входного

Рис. 2.3. Двоичный сумматор с шестью входами (а) можно реализовать либо по схеме (Ь), либо по схеме (с).

гнала) добавляет в цепь единицу. При этом выходной сигнал, ci маемый с правой стороны петли, становится равным входно! После того как команда управления опять принимает нулевое зна1 ние, сигналы петли сохраняют свое новое значение. Таким oOf зом, триггер является устройством памяти. Значение его выхо

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

Более сложный триггер изображен на рис. 2.5. Его существенной частью опять является петля обратной связи, содержащая два инвертора и два элемента ИЛИ. Однако данный триггер имеет большее число входов, а именно х, у и z. Сигналы с каждого из этих входов пропускаются в схему периодическим тактовым сигналом,

Вход

Команда управления

Выход

Рис. 2.4. Триггер.

который принимает одно из значений О или 1 на временных интервалах определенной, заранее заданной длины. Таким образом, этот триггер может переключаться только в определенные интервалы времени, когда тактовый сигнал равен 1. Если тактовый сигнал равен единице и сигнал управления для х равен единице, то выходной сигнал принимает значение, равное входу х; если сигнал управления для у равен 1, то выходной сигнал принимает значение, равное входу у; если сигнал управления для z равен 1, то выходной сигнал принимает значение, равное входу 2. Предполагается, что на триггер никогда не подается одновременно два разных сигнала управления входами.

Часто оказывается необходимым посылать идентичные сигналы управления на входы нескольких триггеров. Рассмотрим в качестве примера схему, изображенную на рис. 2.6. Квадраты, обозначенные буквой А, представляют собой первый регистр триггеров, буквой " - второй регистр и буквой С - третий регистр. Каждый триг-