Содержание к диссертации
Введение
ГЛАВА 1. Общие вопросы организации работы функционально ориентированных процессоров 12
1.1.Принципы построения функционально ориентированных процессоров 12
1.2. Методы приближенного вычисления значений 16
1.3. Методы вычисления значений полиномов одного аргумента 32
1.4. Выводы по главе 1 43
ГЛАВА 2. Адаптивный алгоритм вычисления значений степенных функций и полиномов 44
2.1. Использование специального кодирования данных в процессе вычисления значений степенных функций 44
2.2. Использование специального кодирования данных в процессе вычисления значений полиномов 69
2.3. Метод геометрической фиксации 101
2.4. Выводы по главе 2 117
ГЛАВА 3. Вычислительные структуры, предназначенные для вычисления значений степенных функций и полиномов 118
3.1. Структуры, предназначенные для вычисления значений степенных функций 118
3.2. Структуры, предназначенные для вычисления значений полиномов 180
3.3. Структуры, предназначенные для ускоренного вычисления суммы * многих чисел 212
3.4. Выводы по главе 3 223
ГЛАВА 4. Применение разработанных методов вычисления значения полинома и суммы многих чисел на практике .224
4.1. Расширение функциональной ориентации процессоров цифровой обработки сигналов (ЦОС) за счет незначительной модернизации архитектуры процессора 224
4.2. Увеличение производительности цифровых фильтров за счет ускорения процедуры сложения многих чисел 232
4.3. Перспективы использования метода преобразования массива подлежащих сложению кодов к разным геометрическим формам 244
4.4. Вариант методики проектирования функционально риентированных процессоров для вычисления значений полиномов 245
4.5. Выводы по главе 4 253
Заключение 254
Цитируемая литература 267
- Методы вычисления значений полиномов одного аргумента
- Использование специального кодирования данных в процессе вычисления значений полиномов
- Структуры, предназначенные для вычисления значений полиномов
- Увеличение производительности цифровых фильтров за счет ускорения процедуры сложения многих чисел
Введение к работе
Актуальность темы. Новые нетрадиционные формы представления информации должны предоставить новые возможности при организации вычислительных процессов, что, в свою очередь, позволяет рассчитывать на повышение производительности, процессоров, решающих задачи вычислительного характера. Реализация нетрадиционных форм представления информации сводится к нетрадиционному специальному кодированию данных. В большинстве случаев специальное кодирование данных преследует цели обнаружения и исправления ошибок при хранении и передаче двоичных кодов и другие вспомогательные по отношению к обработке информации цели.
Однако встречались попытки использовать специальные формы кодирования информации для целей повышения производительности вычислительных систем. Например, в итерационных алгоритмах "цифра за цифрой" в процессе формирования итерационной последовательности, которая сходится к значению вычисляемой функции, осуществляется сопоставление кода аргумента с системой специальных констант. Эти системы констант зависят от вычисляемой функции и могут представлять собой, например, значения арктангенсов целой степени двойки, значения логарифмов и т.п. Можно сказать, что в алгоритмах "цифра за цифрой" происходит своеобразное перекодирование исходного кода аргумента. Известны способы представления данных в форме кодов золотой пропорции и кодов Фиббоначи. По сути, эти методы сводятся к формам избыточного кодирования и требуют более значительных объемов памяти для хранения данных, чем обычное двоичное позиционное кодирование данных. При этом бесспорная абсолютная эффективность применения кодов золотой пропорции и кодов Фиббоначи не столь очевидна.
Надо отметить, что возможности различных модификаций бинарного кодирования данных далеко не исчерпаны.
Рационально попытаться применить новые специальные способы кодирования данных к наиболее популярным вычислительным задачам.
Одним из самых популярных вычислительных инструментов является полином. При этом любой из известных способов вычисления полиномов (кроме прямых табличных) представляет собой цепь арифметических действий умножения и сложения. Рассмотрим процесс вычисления значения конкретного полинома:
Р (x)=Ax4+Bx3+Cx2+Dx+E. Если обратить внимание на самый распространенный способ вычисления полиномов - схему Горнера, то можно заметить, что этот метод представляет собой цепь чередующихся умножений и сложений: P(x)=(((Ax + B)x + C)x + D)x + E. Схематично этот процесс вычисления значения полинома Р(Х) можно представить ломаной линией на рисунке (рис.1), где умножение обозначено значком *, а сложение -2.
Из рисунка ясно видно, что процесс вычисления значения полинома одного аргумента Р(Х) представляет собой ломаный путь движения от значения аргумента X к значению полинома Р(Х). При этом происходит вычисление массы промежуточных значений, получаемых в результате выполнения операций ум-
ножения и суммирования, которые являются своеобразными ступенями на пути получения значения Р(х). Важно отметить, что вычисление этих промежуточных результатов не является основной задачей вычисления значения Р(х). Это наводит на мысль о том, что, объективно, должен существовать более стремительный, более непосредственный метод вычисления значения полинома одного аргумента Р(Х). В идеальном случае такой метод можно интерпретировать вектором, который имеет начало в точке X, а конец в точке Р(х).
X
Рис.1.
На поиск таких более стремительных и более непосредственных методов вычисления значения полинома одного аргумента Р(Х) и должны быть направлены исследования возможностей предоставляемых новым, специальным кодированием данных. В диссертационной работе проводится исследование некоторых специальных способов кодирования данных. При этом выполняется анализ возможностей, которые предоставляют специальные арифметические коды при организации вычисления значений степенных функций и полиномов одного аргумента, а также в процессе вычисления суммы многих чисел.
Цель и задачи исследования. Целью диссертационного исследования является разработка алгоритмов вычисления значений степенных функций и полиномов, учитывающих специфику формы представления аргумента. Цель достигается за счет:
применения специального кодирования данных;
результатов исследования специфики, присущей процессам вычисления значений степенных функций и полиномов;
результатов исследования специфики, присущей процессу вычисления суммы многих чисел.
Для достижения поставленной цели решаются следующие задачи:
1. Исследование графовой интерпретации процессов вычисления значений
степенных функций и полиномов.
2. Разработка адаптивных алгоритмов вычисления значений степенных функ
ций и полиномов для аргументов, позиционные коды которых содержат ма
лое число единиц.
3. Разработка вычислительных архитектур, предназначенных для вычисления
значений степенных функций и полиномов одного аргумента, для аргумен
тов, прямые позиционные коды которых содержат малое число единиц.
4. Разработка алгоритма и соответствующей вычислительной архитектуры, предназначенной для повышения эффективности вычисления суммы мно-гихчисел.
Методы исследования. В работе были использованы фрагменты теории фафов, комбинаторики, методов вычислительной математики, а также принципы организации матричных, параллельных и конвейерных вычислительных систем.
Научная новизна. Научная новизна проведенного исследования обуславливается тем, что в основу исследования были положены новые подходы к организации вычислительных процессов. В частности новые теоретические результаты были получены:
в процессе углубленного исследования регулярностей и симметрии, прису
щих процессам вычисления значений степенных функций и полиномов на
фоне специальных способов кодирования данных;
в результате исследования процесса получения суммы многих чисел, исхо
дя из параметров геометрической формы, которую образуют единичные би
ты, содержащиеся в массиве подлежащих сложению двоичных кодов.
Непосредственно научная новизна проведенного исследования заключается в следующем:
впервые предложен алгоритм эффективного вычисления значений степен
ных функций для аргументов, позиционные коды которых содержат малое
число единиц;
впервые предложен алгоритм эффективного вычисления значений полиномов для аргументов, позиционные коды которых содержат малое число единиц;
впервые предложен алгоритм эффективного суммирования многих чисел. Время вычисления суммы многих чисел по данному алгоритму не зависит от числа слагаемых, а зависит только от разрядности слагаемых;
разработан вариант методики проектирования архитектур функционально ориентированных процессоров, отличающийся тем, что в процессе проектирования учитывается специфика данных, позиционные коды которых содержат малое число единиц.
Практическая ценность работы. Практическая значимость диссертации состоит втом, что при организации вычислений значений степенных функций и полиномов в режиме ОКМД, происходит уменьшение времени, затрачиваемого на весь процесс вычисления. Кроме этого, разработанные аппаратные фрагменты, реализующие новый метод сложения многих чисел, могут быть использованы при проектировании разнообразных структур цифровых фильтров (например, цифровых усредняющих фильтров), традиционно входящих в состав архитектуры современных микропроцессоров цифровой обработки сигналов.
Апробация работы. Основные положения и результаты диссертационных исследований докладывались и обсуждались на научных конференциях СПбГЭТУ «ЛЭТИ» (1996-2002 гг.), на заседаниях и семинарах кафедры вычислительной техники, а также на семинарах, проводимых учебной лабораторией фирмы Motorola.
Реализация результатов работы. Научные и практические результаты, полученные в диссертационной работе, были использованы в ОАО "Радиоавионика" при выполнении НИР ВТ-201 "Исследование методов построения семейства высокопроизводительных отказоустойчивых БЦВМ нового поколения с элементами ИИ на основе RISC-микропроцессоров".
Публикации. По теме диссертационной работы опубликованы 6 статей. Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы, включающего 77 наименований и одного приложения. Основная часть работы изложена на 144 страницах машинописного текста. Работа содержит 138 рисунков и 7таблиц.
Методы вычисления значений полиномов одного аргумента
Существует большое количество методов вычисления значений полиномов одного аргумента Рт(х). Время вычисления полинома одного аргумента степени "m" зависит от возможностей распараллеливания выбранного алгоритма вычисления и аппаратной мощности вычислительной структуры, реализующей этот алгоритм. По степени возможности распараллеливания алгоритмы делятся на последовательные и параллельные. Для оценки временных затрат используется понятие арифметической сложности алгоритмов. Арифметическая сложность по следовательных алгоритмов измеряется числом основных операций. Сложность параллельных алгоритмов определяется временем реализации данного алгоритма на к -процессорной вычислительной архитектуре [63]. При анализе сложности параллельных алгоритмов используется идеализированная модель параллельных вычислений [1], т. е. не учитывается время, затрачиваемое на выполнение вспомогательных операций. Считается, что не возникает конфликтов при обращении к ресурсам памяти, отсутствует задержка выполнения команд устройством управления, игнорируются затраты времени на обмены данными и т. д. Не учитывается погрешность алгоритмов, поскольку практическая значимость этих оценок невелика, так как они, как правило, получаются сильно завышенными и плохо учитывающими специфику вычислений, производимых на конкретной вычислительной структуре [17]. Различают ограниченный параллелизм, если имеется к -процессорная вычислительная архитектура (к — некоторое число) и неограниченный параллелизм, когда имеется достаточное количество процессоров. Время, затрачиваемое алгоритмом, называется временной сложностью этого алгоритма. Поведение этой сложности в пределе при увеличении размера задачи (количества входных данных) называется асимптотической временной сложностью алгоритма. Аналогично можно определить емкостную сложность и асимптотическую емкостную сложность. Именно асимптотическая сложность алгоритма определяет в итоге размер задач, которые можно решать этим алгоритмом. Если алгоритм обрабатывает входы размера "п" за время сп2, где "с" - некоторая постоянная, то говорят, что асимптотическая временная сложность этого алгоритма есть 0(п2) (читается " порядка п2 "). Точнее, говорят, что (неотрицательная) функция g(n) есть 0(f(n)), если существует такая постоянная "с", что g(n) cf{n) для всех, кроме конечного (возможно пустого) множества, неотрицательных значений п. Другими словами, можно сказать, что асимптотической временной сложностью алгоритма 0(f(n)) называется оценка времени, затрачиваемого на выполнение этого алгоритма, выраженная в микропроцессорных циклах.
В известных алгоритмах вычисления полинома одного аргумента Рт(х) активно используются операции умножения и сложения. При алгоритмической реализации более емкой и весомой с точки зрения затрачиваемого времени является операция умножения. При наличии в структуре специализированного процессора матричного умножителя и арифметическое сложение и арифметическое умножение занимают один микропроцессорный цикл. По этой причине, в качестве акта вычисления полинома можно определить операцию умножения. При этом временной интервал, необходимый для выполнения операции арифметического умножения, будем называть шагом.
Рассмотрим наиболее известные алгоритмы вычисления значений полиномов одного аргумента, обеспечивающие достаточно приемлемые показатели быстродействия.
Схема Горнера
Для последовательных алгоритмов вычисления значений полинома степени m оптимальна схема Горнера, но она нерациональна для параллельных алгоритмов, так как требует выполнения m умножений и m сложений в строго последовательном порядке. Широко известны метод Эстрина [81]. и правило Горнера k-го порядка [80].
Использование специального кодирования данных в процессе вычисления значений полиномов
Поскольку слагаемыми, сумма которых дает значение полинома, являются степенные функции, рассмотрим детальнее особенности свойственные степенным функциям.
Стоит отметить тот факт, что всем степенным функциям присущи стройность и регулярность графов формирования и расстановки наборов номеров единичных бит аргумента. Особенно наглядно это видно на примерах графов формирования и расстановки наборов разных степенных функций при малом числе единичных бит в коде аргумента.
Рассмотрим случай, в котором в коде аргумента присутствует только 3 единичных бита (S=3). Проанализируем этот случай на примере степенных функций X2, X3 и X4 .Начнем с квадратичной функции. Для случая, при котором X содержит только 3 единичных бита новое представление X имеет вид {I_2, Ц}. Пусть L.2=b, Ц=а. Граф формирования и » расстановки наборов номеров единичных бит аргумента X для функции X2 (при S=3) показан на рис. 2.22. Внутри узлов графа показаны вклады соответствующих наборов номеров единичных бит аргумента X.
Теперь рассмотрим случай кубической функции X3. Граф формирования и расстановки наборов номеров единичных бит аргумента X для функции X3 (при S=3) показан на рис. 2.23 (внутри узлов фафа показаны вклады соответствующих наборов номеров единичных бит аргумента X).
Граф формирования и расстановки наборов номеров единичных бит со своими вкладами для функции X4 (при S=3) показан на рис. 2.24. Графы 3-х последних рассмотренных примеров могут быть преобразованы к виду, в котором фигурируют только расстояния между единичными битами без сомножителей. Эволюция графа для функции X2 (рис. 2.22), для случая S=3 представлена на рис. 2.25. Исходный граф, отмеченный пунктом 1), можно дополнить дугами, обозначающими расстояния между всеми соседними узлами на результирующей разрядной сетке. В результате граф приобретает вид, показанный на рис. 2.25 (пункт 2). На следующем шаге граф может быть преобразован к виду, изображенному), в котором дуги отмечены только расстояниями между единичными битами (без сомножителей). На последнем шаге граф приводится к виду изображенному на рис. 2.25 (пункт 4).
Вид фафа на рис. 2.25 (пункт 4) ясно демонстрирует регулярность и однородность относительного расположения вкладов наборов номеров единичных бит аргумента для случая X2 и S=3. В изображении фафа явно просматривается специфическая симметрия. При этом дуги типа а ориентированны строго параллельно в одном направлении, а дуги типа Ь ориентированны параллельно в другом направлении.
Аналогичные преобразования можно проделать и для кубической зависимости. Эволюция графа для функции X3 (рис. 2.23), для случая S=3 представлена на рис. 2.26. Исходный граф, отмеченный пунктом 1), можно дополнить дугами, обозначающими расстояния между всеми соседними узлами и убрать дуги типа ka, kb (где к - сомножитель при соответствующем Lj) на результирующей разрядной сетке. Теперь граф приобретает вид, показанный на рис. 2.26 (пункт 2), в котором дуги отмечены только расстояниями между единичными битами (без сомножителей).
Переориентация дуг в пространстве на последнем шаге приводит граф к конечному виду, показанному на рис. 2.26 (пункт 3). Вид графа после последнего преобразования также подчеркивает регулярность и симметрию относительного расположения вкладов наборов номеров единичных бит аргумента для случая X3 и S=3. При этом дуги типа а ориентированны строго параллельно в одном направлении, а дуги типа b ориентированны параллельно в другом направлении Достоверность преобразования графов может быть подтверждена сравнением расстояний всех узлов от начального на исходном и конечном графах. Например, на рис. 2.26 (пункт 1) крайний левый узел, имеющий вклад 1, находится на расстоянии 3a+3b=3(a+b) от начального узла (рис. 2.27.).
После выполнения всех преобразований граф приобретает вид, показанный на рис. 2.26 (пункт 3)). Обращая внимание на нижнюю часть конечного графа (рис. 2.28), можно убедиться в том, что расстояние между крайним левым узлом и начальным не изменилось a+b+a+b+a+b =3 (a+b).
Аналогичные сравнения для расстояний между другими узлами подтверждают достоверность эквивалентности исходного и преобразованного графов.
Подобные преобразования можно проделать и для графа функции X4 при коде аргумента, который содержит 3 единичных бита (рис. 2.24). Для подтверждения достоверности эквивалентности исходного и преобразованного фафов отметим все узлы исходного графа, показанного на рис. 2.24, расстояниями между конкретным узлом и начальным узлом (рис. 2.29). Расстояния выражаются в числе разрядов на фоне полной разрядной сетки. Вид преобразованного конечного графа с узлами, отмеченными расстояниями между конкретным узлом и начальным узлом, представлен на рис. 2.30.
Сопоставление отмеченных узлов фафов и их относительного расположения на рис. 2.29 и рис. 2.30 подтверждает эквивалентность этих фафов.
Структуры, предназначенные для вычисления значений полиномов
В том случае, когда аргумент - X представлен прямым двоичным кодом, с фиксированной после крайнего младшего разряда точкой (т.е. X — целое) аппаратные затраты на сдвигатель и умножитель оказываются значительными, поскольку не допускается отбрасывание разрядов результата. Но если перейти к диапазону чисел по модулю меньше единицы, то допускается потеря младших разрядов результата с соответствующим округлением, обеспечивающим заданную точность вычислений. При этом аппаратные затраты на реализацию сдвигателя и умножителя не выглядят астрономическими и зависят от заданных требований по точности. Во многих микропроцессорах схемы сдвигателя и умножителя представляют собой аппаратные фрагменты, вырабатывающие результат длиной "2п", где п - разрядность аргумента. При этом пользователю предоставляется возможность отдельно сохранять в памяти старшую и младшую части результата. Будем считать, что в нашем распоряжении именно такая структура аппаратного сдвигателя. Во второй главе было показано, что для случая кодов аргументов с малым числом единиц качественной разницы между процессами вычисления значения полинома и степенной функции нет. В обоих случаях для вычисления значения полинома надо выполнять операции чтения из ПЗУ, сдвига и сложения. Из этого следует, что специальные части рассмотренных вычислительных структур подобны специальным частям для вычисления значения полинома (для случая кодов аргументов с малым числом единиц).
Выполним оценку аппаратных затрат на специальные операционные части рассматриваемых вычислительных структур, позволяющих вычислять значения полинома в особенных случаях. Будем использо вать формат входных аргументов с фиксированной точкой в диапазоне чисел по модулю меньше единицы. Как известно, в этом диапазоне чисел номера двоичных разрядов, представляют собой следующий ряд чисел: 0,-1,-2,-3, ...н, ... ,-(п-1), где п - разрядность числа, О - номер знакового бита, -І - номер І -го разряда. Также, как и для диапазона целых чисел, процесс вычисления значения полинома степени М (для случая кодов аргументов с малым числом единиц) подразумевает последовательное выполнение следующих этапов: 1) формирование всевозможных М-местных наборов номеров единичных бит; 2) вычисление вклада каждого М-местного набора; 3) расстановка вкладов М-местных наборов; 4) суммирование расставленных вкладов.
Двоичные веса разрядов представляют собой отрицательные числа, т.е. сдвиги констант, считываемых из ПЗУ, будут выполняться вправо. Для иллюстрации будем рассматривать полином степени М=4. Результаты проводимого анализа легко могут быть распространены на случай произвольной степени полинома одного аргумента. Проанализируем 4 случая: 1) число единиц в прямом двоичном позиционном коде аргумента равно 1; 2) число единиц в прямом двоичном позиционном коде аргумента равно 2; 3) число единиц в прямом двоичном позиционном коде аргумента равно 3; 4) число единиц в прямом двоичном позиционном коде аргумента равно 4.
В этом случае АЦП одновременно с аналого-цифровым преобразованием вырабатывает признак того, что код аргумента содержит только одну единицу (S=1). При условии, что один бит в коде аргумента занят под знак числа (рассматривается формат представления чисел с фиксированной точкой и разрядностью равной "п"), возможно (п - 1) вариантов кодов, содержащих только одну единицу. Для анализа возьмем маленькую разрядность входного аргумента. Пусть разрядность аргумента 8. В процессе вычисления будем использовать прямой двоичный код без знака. Другими словами (п - 1) = 7. В данном рассматриваемом случае аргумент представлен в следующем виде: Х-{а}, где а - номер единственного бита в коде аргумента ( а 0). На рис. 3.50 приведена разрядная сетка результата с расставленными по ней наборами единичных бит для степенных функций входящих в выражение полинома Р4(х) = Кдх4+ K3X3 + Кг + К х . Расстановка наборов выполняется по пронумерованной разрядной сетке, так, чтобы сумма всех цифр каждого М-местного набора была равна номеру разряда (разрядного среза). На данном рисунке представлены два случая а = -1 и а = -2. С учетом знака всего может быть 2(п - 1) значений аргументов. На рис. 3.51 приведена разрядная сетка результата с расставленными по ней вкладами соответствующих наборов номеров единичных бит.
Увеличение производительности цифровых фильтров за счет ускорения процедуры сложения многих чисел
Как известно, задача вычисления суммы многих чисел является одним из популярнейших алгоритмических инструментов в классе алгоритмов ЦОС. Алгоритмы фазовой коррекции, Доплеровской фильтрации, пространственной фильтрации, вычисления свертки, машинной графики [5], обработки изображений [54] и др. активно используют суммирование многих чисел. По сути, вышеуказанные алгоритмы вычисления «свертки» представляет собой операцию суммирования произведений - SOP (sum of products). При этом вычислительная система, реализующая алгоритмы ЦОС в реальном масштабе времени, может работать в разных режимах. В тех случаях, когда подлежащие суммированию значения произведений поступают на вход суммирующей схемы с ритмом, превышающим частоту работы суммирующего блока, особое значение приобретает задача организации эффективного сложения многих чисел. На этом пути можно предложить новые, учитывающие специфику и ритм обработки, способы вычисления суммы многих чисел. Поиск в этом направлении привел к версии алгоритма вычисления суммы многих чисел, который может быть реализован с помощью вычислительной структуры, показанной на рис.4.3.
Работа рассматриваемой вычислительной структуры основана на идее организации сложения многих чисел одного знака методом геометрической фиксации. Суть упомянутого метода состоит в том, что, производя эквивалентные преобразования массива кодов чисел одного знака, можно привести основную массу подлежащих суммированию кодов к прямоугольной форме, образованной единичными битами. Предлагаемый метод приведения единичного рельефа подлежащих суммированию кодов к эквивалентной прямоугольной форме подробно описан в параграфе 2.3.1. Фиксация прямоугольника единичных бит с последующим измерением его параметров позволяет быстро и легко получить значение суммы кодов, образующих этот прямоугольник.
Эта сумма представляет собой простую функцию двух переменных: ширины и высоты прямоугольника. Для получения результирующей суммы многих чисел надо к сумме кодов, образовавших прямоугольник, надо прибавить остаточный код, который не вошел в прямоугольник единичных бит. Реализующая вышеописанный метод структура (рис.4.3.) состоит из двух блоков специализированной буферной памяти, которые состоят из набора сдвиговых регистров (рис.4.4), S— E двух блоков специальной обработки - SU и вычитающего блока - SUB.
Пусть стоит задача выполнить сложение N чисел, представленных в форме с фиксированной точкой, последовательно поступающих на, предназначенную для получения суммы, вычислительную структуру. Положим, что п - разрядность обрабатываемых чисел без знака.
Рассматриваемая вычислительная структура (рис. 4.3.) работает в следующем порядке. На вход этой вычислительной структуры поступает поток подлежащих суммированию значений произведений Pj. Значение знакового бита S выбирает блок специализированной памяти, в который происходит запись данного числа. Таким образом, осуществляется предварительное разделение потока чисел на отрицательные и положительные. Это необходимо для того, чтобы в каждом из двух каналов вычислительной структуры велась обработка чисел одного знака.
Специализированная буферная память (рис.4.4.) представляет собой набор из п сдвигающих регистров (п - разрядность обрабатываемых чисел без знака), имеющих последовательный вход и параллельный выход (рис.4.5.).
Каждый N-разрядный сдвигающий регистр имеет последовательный вход данных D, вход управления сдвигом SH и параллельный выход разрядов 1,2,3, ...N-1.N. Перед началом работы нулевой разряд каждого сдвигающего регистра устанавливается в состояние 1, а разряды 1,2,3, ... N-1.N - в состояние 0 (на рисунке сдвигающий регистр показан в начальном состоянии). На последовательный вход D всех сдвигающих регистров постоянно подключен уровень логического нуля. На вход управления сдвигом SH каждого из п сдвигающих регистров подключен выход одного из разрядов выходной п - разрядной магистрали данных каскада, вырабатывающего слагаемые.
