Схемы деления на образующий многочлен

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

Схема деления на регистре сдвига с сумматорами по модулю 2.

Существуют различные варианты построения таких делителей, отличающихся числом ячеек памяти регистра (m или k) и схемой включения сумматоров в цепи обратной связи.

Рассмотрим схему деления на основе m-разрядного регистра сдвига. Строится схема по следующему правилу:

- число ячеек регистра равно степени образующего многочлена; ячейка регистра для старшей степени многочлена отсутствует, но всегда присутствует ячейка ;

- сумматоры ставятся перед ячейками регистра, соответствующими ненулевым членам образующего многочлена, при этом сумматор, соответствующий старшему члену образующего многочлена, отбрасывается;

- делимое, начиная со старшего разряда, поступает на вход первого сумматора, соответствующего члену ;

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

Составленная в соответствии с этими правилами схема деления на образующий многочлен представлена на рис. 2.4.

Рис. 2.4. Схема деления на базе регистра сдвига.

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

Характерной особенностью построения регистра является то, что ячейки памяти имеют двухступенчатую структуру. Прием информации в первую ступень осуществляется по переднему фронту ТИ, а передача информации из первой ступени во вторую – по заднему фронту.

В таблице 2.5 символы 0 и 1 характеризуют состояние второй ступени ячеек памяти, устанавливающееся после прохождения заднего фронта ТИ.

Перед началом деления все ячейки регистра устанавливаются в нулевое состояние под действием импульса «Сброс».

Таблица 2.4

Таблица состояний ячеек регистра

За первые m тактов ( ) коэффициенты многочлена-делимого, подаваемые на вход схемы деления, заполняют регистр, причем коэффициент при x в старшей степени появляется на выходе ячейки . В следующем такте 1 с выхода ячейки по цепи обратной связи подается на вторые входы сумматоров по модулю 2, что равносильно вычитанию образующего многочлена из многочлена-делимого. Если после окончания предыдущего такта на выходе ячейки , соответствующей старшей степени остатка, устанавливается 0, то в следующем такте образующий многочлен не вычитается. Коэффициенты делимого просто смещаются вперед по регистру на один разряд, что находится в полном соответствии с тем, как это делается при делении многочленов столбиком. После окончания n-го такта ( ) в ячейках регистра хранятся коэффициенты остатка от деления многочлена-делимого на образующий многочлен.

СПИСОК ЛИТЕРАТУРЫ

1. В.А. Острейковский. Информатика. – М.: «Высшая школа», 2001.

2. А.И. Спиридонов. «Основы теории информации и кодирования». Учебное пособие. – СПб/Псков, Изд. СПбГПУ, 2004 – 140 с.