8.7. Делители и устройства с плавающей запятой

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

1. Четырехквадрантный матричный делитель

Рассмотрим четырехквадрантный делитель, составленный из комбинационной матрицы суммирующих и вычитающих логических элементов. Будем считать, что на вход схемы поступают 24-разрядное делимое (числитель) и 12-разрядный делитель (знаменатель), оба в дополнительном коде, а на выходе образуются 12-разрядные частное и остаток. Можно рассматривать случаи, когда делитель и делимое являются произвольными целыми или дробными числами или константами. Будем считать, что входные числа — правильные дроби с запятой, расположенной непосредственно правее знакового разряда; это будет учтено при построении логики индикации переполнения.

В основу работы матричной схемы положен метод деления без восстановления остатка. С целью упрощения описания этого метода примем сначала, что делимое и делитель — положительные правильные дроби, причем делитель больше делимого или равен ему. При этих условиях частное также будет, очевидно, положительной правильной дробью. Для получения первого значащего разряда частного вычисляется частичное делимое как разность между делимым и пробным делителем, равным половине фактического. Если частичное делимое положительно, то в качестве разряда частного принимается единица. Если же оно отрицательно, т. е. если пробный делитель «не умещается» в делимом, то искомый разряд равен нулю. При обычном делении (с восстановлением остатка) в этом случае нужно сложить пробный делитель с частичным делимым для восстановления исходного делимого и попытаться вычесть новый пробный делитель. При делении без восстановления остатка используется тот факт, что каждый последующий пробный делитель в два раза меньше предыдущего. Поэтому сложение пробного делителя (т. е. операция восстановления) с последующим вычитанием его половины всегда будет совпадать с простым добавлением половины пробного делителя. Таким образом, если первый значащий разряд частного равен 1, то предыдущее значение пробного делителя делится пополам и затем вычитается из частичного делимого для получения следующего разряда частного. Если же первый разряд частного равен нулю, то пробный делитель делится пополам и затем добавляется к частичному делимому для получения следующего разряда частного. Эта процедура продолжается до тех пор, пока не будет получено требуемое количество разрядов частного. Преимущества этого алгоритма отчетливо выявляются при реализации его в виде нетактируемой матрицы. В нем нет обратных связей и шагов «назад», процесс протекает без всяких условий от начала и до конца.

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

На верхней большей части блок-схемы рассматриваемого алгоритма (фиг. 8.36) представлена процедура получения разрядов частного, а на нижней части показан процесс заключительной коррекции. Вычисление разрядов частного на каждом этапе производится но следующим правилам:

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

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

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

Фиг. 8.36. Последовательность получения четырех разрядов частного с использованием алгоритма без восстановления остатка.

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

1. Если и делитель и делимое положительные, присвоить знаковому разряду частного значение 0 и ничего не делать со значащими разрядами.

2. Если и делитель и делимое отрицательные, присвоить знаковому разряду частного значение 0 и проинвертировать значащие разряды.

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

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

В принципе при -разрядном делителе (включая знаковый разряд) для представления всех сумм и разностей в матричной схеме достаточно  разрядов. Разность (или сумма) между любым частичным делимым и его пробным делителем также может быть представлена не более чем  разрядами (включая знак). Таким образом, для рассматриваемого случая (фиг. 8.36) оба разряда, 12-й и 13-й, отведенные во всех частичных делимых под знаковые, обязательно будут одинаковыми. В противном случае выдается сигнал переполнения. С точки зрения дробных операндов этот сигнал означает, что делимое по величине больше делителя. Такой режим запрещен, так как в этом случае частное превысит 1 и его, следовательно, нельзя представить правильной дробью, у которой все значащие разряды находятся справа от запятой. Это обстоятельство и фиксируется сигналом переполнения.

Фиг. 8.37. Матричный делитель размером (4х8) без сохранения остатка с индикацией переполнения и заключительной знаковой коррекцией (по Бланкеншипу). Числитель — 8 разрядов, знаменатель — 4 разряда, частное — 4 разряда, остаток — 4 разряда.

Частичное делимое, определяющее младший разряд частного [т. е. результат последнего этапа сложения (вычитания)], следует рассматривать как остаток. Он представляет собой 12-разрядное число (11 разрядов и знак) и следующим образом связан с другими операндами:

Делимое = (Частное) х (Делитель) + Остаток.

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

На фиг. 8.37 показан пример построения устройства для деления восьмиразрядного делимого на четырехразрядный делитель с четырехразрядными частным и остатком на выходе. Простым наращиванием его можно довести до 24/12 разрядов. Представленные на схеме сумматоры-вычитатели могут быть построены на основе двухнаносекундной четырехразрядной ИС ЭСЛ типа МС10181 (арифметико-логическое устройство). Эта ИС в зависимости от управляющего сигнала может быть запрограммирована или на сложение, или на вычитание. Вычитание осуществляется путем изменения знака числа на входе В с последующим суммированием. Фактически для выполнения этой операции требуется проинвертировать разряды  и добавить единицу. Инверсия внутри ИС предусмотрена, но для добавления единицы необходимо во время вычитания подать сигнал на вход  (вход переноса в младший разряд).

В соответствии со сделанными ранее выводами следует ожидать, что для выполнения всех сложений (вычитаний) потребуется пять разрядов, так как делитель имеет четыре разряда. Однако можно показать, что -й разряд легко получить, используя выход переноса -го разряда и немного изменив правила. Сформулируем коротко эти упрощенные правила:

1. Первый этап. Если знаки делителя и делимого не совпадают, следует производить сложение, если совпадают — вычитание.

2. Все последующие этапы. Если выходной сигнал переноса () -го разряда предыдущего сумматора-вычитателя равен 1, нужно записать 1 в разряд частного. Кроме того, если выходной сигнал переноса отличается от знакового разряда делителя, то на данном этапе следует произвести вычитание, а в противном случае — сложение.

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

4. Заключительная коррекция. Это правило удобнее всего сформулировать в виде следующей таблицы:

Логические уравнения имеют вид

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

Схема 24/12-разрядного делителя состоит из 12 12-разрядных каскадов. На первых 11 формируются разряды частного, на последнем выполняется коррекция. Каждый каскад состоит из трех ИС МС10181, включенных по схеме образования ускоренного переноса на 9 разрядов. Таким образом, всего требуется 36 корпусов МС10181. На каждом каскаде все небходимые разряды частичного делимого образуются за 13 нс, поэтому вся операция деления занимает 12x13 = 156 нс. Количество корпусов, необходимых для управления и индикации переполнения, а также для распределения данных, незначительно. Следовательно, этот делитель требует меньшего количества корпусов, чем умножитель двенадцатиразрядных чисел, построенный на той же логической серии.

2. Цифровые устройства с плавающей запятой

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

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

Использование плавающей запятой при фильтрации и БПФ, по-видимому, не создает дополнительных трудностей, связанных с округлением, но часто улучшает работу устройств. Однако при этом приходится использовать больший объем оборудования во многих универсальных ЦВМ операции с плавающей запятой реализуются не аппаратурными, а программными средствами, что приводит к удлинению программ и увеличению времени их выполнения. Алгоритмы работы устройств умножения и сложения с плавающей запятой сложнее, чем аналогичные алгоритмы с фиксированной запятой.

При умножении с плавающей запятой производится суммирование порядков сомножителей и умножение с фиксированной занятой их мантисс. Поскольку величина мантиссы (в десятичной системе) больше или равна 0,5, но меньше 1, то произведение двух мантисс заключено между 0,25 и 1. Это означает, что произведение будет либо выровнено по левому разряду), либо смещено на один разряд. В качестве упражнения составьте схему четырехразрядного устройства сложения порядков для умножителя с плавающей запятой.

При сложении с плавающей запятой необходимо выполнить следующие операции:

1. Определить, какой из двух порядков больше.

2. Из большего порядка вычесть меньший.

3. Полученную разность использовать для сдвига вправо мантиссы с меньшим порядком.

4. Сложить обе мантиссы.

5. Определить количество старших разрядов суммы, состоящих из одних нулей (или единиц).

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

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

Основным узлом сумматора, в котором выполняются операции 3 и 6, является устройство сдвига на произвольное число разрядов. Проще всего эти операции выполнить с помощью последовательного регистра сдвига и счетчика числа сдвигов, однако затрачиваемое при этом время довольно значительно. Другой метод состоит в разработке логической матрицы, в которой предусмотрены все сдвиги. Он позволяет достичь большого быстродействия, но требует большего объема оборудования, чем при построении матричного умножителя. Компромиссное решение показано на фиг. 8.38. Каждая точка представляет собой управляемый переключатель, с помощью которого входная линия подключается к одной из двух выходных линий. В данной схеме восемь различных сдвигов обеспечиваются тремя уровнями переключателей; в общем случае для -разрядной сдвигающей цепи необходимо обеспечить  уровней переключения.

Фиг. 8.38. Матричная схема сдвига на 0—8 разрядов.

Фиг. 8.39. Схема подсчета количества сдвигов влево, необходимых для нормализации (по Бланкеншипу).

Фиг. 8.40. Преобразователь количества единичных выходов в четырехразрядное двоичное число (по Бланкеншипу).

Для выполнения пятой операции при сложении с плавающей запятой необходимо иметь логическую схему подсчета количества одинаковых старших разрядов. На фиг. 8.39 и 8.40 показаны схемы, предназначенные для решения этой задачи для случая 12-разрядного числа. Первая схема (фиг. 8.39) преобразует 11 входных разрядов в 10 выходных. Количество единичных выходов определяется количеством сдвигов влево, необходимых для нормализации входного числа. Вторая схема (фиг. 8.40) составлена из полных сумматоров и выполняет операцию подсчета количества единичных выходов первой схемы.