единиц времени после того,как коэффициент при X^0 поступил на вход.
Таким образом,в некотором смысле задержка на выходе равна r единицам времени.
ПРИМЕР.С помощью схемы,изображённой ниже,производится умножение входного полинома на полином h(X) = X^5 + X^4 + X^3 + 1.
┌─┐ ┌─┐ ┌─┐
┌────│+│───│+│─────────────────│+│─────>
│ └─┘ └─┘ └─┘
│ ┌─┐ │ ┌─┐ │ ┌─┐ ┌─┐ ┌─┐ │
──┴─│ │─┴─│ │─┴─│ │───│ │───│ │───┘
Вход └─┘ └─┘ └─┘ └─┘ └─┘
┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐
┌─│ │───│ │───│ │─│+│─│ │─│+│─│ │─│+│──>
│ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘
│ │ │ │
──┴──────────────────┴───────┴───────┘
Вход
Д Е Л Е Н И Е П О Л И Н О М О В .
Схема деления полинома d(X) = dnX^n + dn-1X^n-1 +...+d0 на многочлен g(X) = grX^r + gr-1X^r-1 +...+ g0 показана на рис.ДП.
Выход
┌───────┬────────┬─────<──<────┬────────┬────────┬───────┬─────>
┌───┐ ┌───┐ ┌───┐ ┌─────┐ ┌─────┐ ┌─────┐┌─────┐
│-g0│ │-g1│ │-g2│ │-gr-3│ │-gr-2│ │-gr-1││gr^-1│
└───┘ └───┘ └───┘ └─────┘ └─────┘ └─────┘└─────┘
│ │ │ │ │ │ │
┌─┐ ┌─┐ ┌─┐ ┌──┐ ┌─┐ ┌──┐ ┌─┐ ┌──┐ ┌─┐ ┌──┐ ┌─┐ ┌──┐│
──│+│─│ │─│+│─│ │─│+│─│ │─>...─│+│─│ │─│+│─ │ │─│+│─│ │┘
└─┘ └─┘ └─┘ └──┘ └─┘ └──┘ └─┘ └──┘ └─┘ └──┘ └─┘ └──┘
Вход
Рис.ДП.
Устройство памяти вначале должно содержать нули.Выходной символ принимает значения,равные 0,для первых r сдвигов,т.е.до тех пор,пока первый входной символ не достигнет конца регистра сдвига.После этого появляется первый ненулевой выходной символ,который равен
dn gr^-1 - первому коэффициенту частного.Для каждого коэффициента частного qj необходимо вычесть из делимого многочлен qj g(X).Это вычитание производится с помощью обратной связи.После всех n сдвигов на выходе появится частное от деления,а остаток от деления будет находиться в регистре сдвига.Работу схемы легче всего понять с помощью подробных примеров.
ПРИМЕР.На рисунке изображена схема,предназначенная для деления полинома на входе на полином g(X) = X^6 + X^5 + X^4 + X^3 + 1.
┌─────<────────────┬───<────┬───<────┬───<───┐
┌─┐ ┌──┐ ┌──┐ ┌──┐ ┌─┐ ┌──┐ ┌─┐ ┌──┐ ┌─┐ ┌──┐ │ Выход
────────>│+│─│ │─│ │─│ │─│+│─│ │─│+│─│ │─│+│─│ │─┴────────>
Вход └─┘ └──┘ └──┘ └──┘ └─┘ └──┘ └─┘ └──┘ └─┘ └──┘
В таблице последовательные этапы деления многочлена X^13 + X^11 +
+ X^10 + X^7 + X^4 + X^3 + X + 1 на полином g(X) сравниваются с последовательными операциями по этой схеме.Заметим,что при обычном делении столбиком члены высших порядков расположены слева,тогда как в регистре сдвига члены высших порядков располагаются справа.
ПОСЛЕДОВАТЕЛЬНЫЕ ОПЕРАЦИИ В СХЕМЕ ДЛЯ ДЕЛЕНИЯ
═══════════════════════════════════════════════════════════════════
Содержимое Выходной Обратная связь Входной
j регистра сдвига смвол в момент j-го символ после j сдвигов после j-го сдвига в момент сдвига j-го сдвига
═══════════════════════════════════════════════════════════════════
0 0 0 0 0 0 0 0 -- -1 1 0 0 0 0 0 0 0 0 0 0 0 0 1
2 0 1 0 0 0 0 0 0 0 0 0 0 0 0
3 1 0 1 0 0 0 0 0 0 0 0 0 0 1
4 1 1 0 1 0 0 0 0 0 0 0 0 0 1
5 0 1 1 0 1 0 0 0 0 0 0 0 0 0
6 A 0 0 1 1 0 1 1 0 0 0 0 0 0 0
7 D 0 0 0 0 0 1 1 1 0 0 1 1 1 B 1 - C
8 G 1 0 0 1 1 1 1 1 0 0 1 1 1 E 0 - F
9 1 1 0 1 0 0 0 1 0 0 1 1 1 0
10 1 1 1 0 1 0 0 0 0 0 0 0 0 1
11 1 1 1 1 0 1 1 0 0 0 0 0 0 1
12 1 1 1 0 0 1 1 1 0 0 1 1 1 0
13 0 1 1 0 1 1 1 1 0 0 1 1 1 1
14 0 0 1 0 1 0 0 1 0 0 1 1 1 1
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.