7.2. Умножение и деление многочленов

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

Схема, изображенная на рис. 7.2, Используется для умножения любого многочлена на входе

на фиксированный многочлен

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

Когда на входе появляется первый коэффициент многочлена то на выходе появляется первый коэффициент произведения а разный . В этот момент все разряды запоминающего устройства содержат нули. Спустя единицу времени на входе появляется находится в первом разряде, а все остальные разряды содержат нули.

Рис. 7.2. Схема для умножения многочленов.

Как можно увидеть из рис. 7.2, выход будет равен т. е. величине второго коэффициента в произведении Аналогично, через две единицы времени на входе появится а разряды регистра сдвига будут содержать элементы . Выход равен что 11 есть третий коэффициент произведения Дальнейшие операции производятся аналогичным образом. После сдвигов в разрядах регистра содержатся элементы и выход равен а т. е. предпоследнему коэффициенту произведения После и сдвигов регистр сдвига содержит элементы и выход равен последнему коэффициенту произведения так что произведение получено полностью.

Другая схема для умножения показана на рис. 7.3. Коэффициенты произведения формируются в регистре сдвига. После того как первый символ подается на вход, выход равен а разряды содержат только нули. После одного сдвига разряды содержат элементы и вход равен Так выход равен т. е. равен второму коэффициенту. После следующего сдвига разряды содержат элементы и вход равен Следовательно,

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

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

Рис. 7,3. Другая схема для умножения многочленов.

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

Рис. 7.4. Схема для умножения с двумя входами.

Схемы такого вида, как показано на рис. 7.3, могут иметь более чем один вход. Например, схема, изображенная на рис. 7.4, имеет два входа, а выход равен

где

Схема изображена для случая, когда многочлены имеют одну и ту же степень, однако если степени многочленов не совпадают, то в качестве можно выбрать наибольшую степень и положить коэффициенты высших порядков в одном многочлене равными 0.

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

Рис. 7.5. Схемы для умножения на многочлен

Схема для деления многочлена на многочлен показана на рис. 7.6. Запоминающее устройство вначале должно содержать нули. Выход принимает значения, равные 0, для первых сдвигов, т. е. до тех пор, пока первый входной символ не достигнет конца регистра сдвига.

Рис. 7.6. Схема для деления многочленов.

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

Рис. 7.7. Схема для деления на многочлен .

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

Таблица 7.1а (см. скан) Сравнение деления столбиком и операций в схеме для деления. Обычное деление столбиком

Заметим, что при обычном делении столбиком члены высших порядков расположены слева, в то время как в регистре сдвига члены высших порядков располагаются справа.

Первые шесть сдвигов не имеют аналогий при делении "столбиком". После шестого сдвига содержимое регистра сдвига соответствует многочлену, обозначенному на табл. 7.1а буквой А. Его старший коэффициент равен первому символу частного и, кроме того, равен выходу после седьмого сдвига. Обратной связи соответствует многочлен, обозначенный В, а входу — одночлен С, сносимый вниз при делении столбиком. После седьмого сдвига содержимому регистра сдвига соответствует многочлен, обозначенный буквой Обратная связь дает многочлен ?; одночлен сносимый вниз, совпадает с входным символом, и после восьмого сдвига регистра сдвига его содержимым является многочлен Этот процесс продолжается до тех пор, пока после четырнадцати сдвигов, по одному для каждого коэффициента делимого, содержимым регистра сдвига не станет остаток от деления и все коэффициенты частного не появятся на выходе.

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

Таблица 7.16 (см. скан) Сравнение деления столбиком и операций в схеме для деления. Последовательные операции в схеме для деления

на рис. 7.3, и схемы для деления, изображенной на рис. 7.6. Здесь предполагается, что степень многочлена не превосходит степени многочлена (см. следующий пример).

Рис. 7.8. Схема для умножения на многочлен и деления на многочлен

Пример. На рис. 7.9 показана схема регистра сдвига, используемого для умножения входного многочлена на многочлен и для деления результата на мнгочлен Регистр сдвига содержит часть делимого, находящуюся в процессе обработки. Входные соединения прибавляют к содержимому регистра сдвига произведение многочлена

и входного символа, вместо того чтобы просто прибавить входной символ, как это было в схеме для деления (рис. 7.6).

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

Рис. 7.9. Схема для умножения на многочлен и деления на многочлен

В этом случае для того, чтобы закончить деление, требуется произвести столько дополнительных сдвигов с нулем на входе, сколько было добавлено разрядов. На рис. 7.10 приведен пример схемы для умножения входного многочлена на многочлен и для деления получившегося произведения на многочлен

Рис. 7.10, Схема для умножения на многочлен и деления на многочлен

В этом случае для того, чтобы закончить вычисление частного и остатка, приходится производить подряд четыре сдвига с нулем на входе после подачи на вход коэффициента при слагаемом нулевой степени.