Многофункциональное вычислительное устройство

 

Изобретение относится к области вычислительной техники си может быть использовано для выполнения операций умножения, деления, извлечения квадратного корня и сортировки больших массивов многоразрядных чисел . Цель изобретения - расширение функциональных возможностей устройства за счет выполнения операции сортировки и повышение производительности обработки больших массивов данных. Устройство конвейерноматричного типа содержит матрицу из N строк и N стлобцов, два дополнительных столбца из N ячеек и N ячеек управления, триггеры, N схем выбора максимального числа, N схем формирования сигнала считывания и элемент ИЛИ, где N - разрядность операндов. Каждая ячейка матрицы и дополнительного столбца содержит два три1 гера, логические элементы и сумматор, а ячейка управления - логические элементы И, ИЛИ. Схема выбора максимально1 о числа содержит последовательно соединенные элемент ИЛИ, элемент ИСКЛЮЧАКЩЕЕ ИЛИ и триггер , а схема формирования сигнала считывания дополнительно к этим элементам включает триггер, два элемента ШШ, элемент И, Эффективность устройства растет с увеличением разрядности чисел и объема обрабатываемой информации. 2 з.п, ф-лы, 8 ил., 2 табл. с S (Л

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

<5 > 4 G 06 F 7/38

ОПИСАНИЕ ИЗОБРЕТЕНИЯ " :

К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3911184/24-24 (22) 14.06.85 (46) 28.02,87. Бюл. У 8 (7 1) Львовский политехнический институт им. Ленинского комсомола (72) В.И. Раш и В.В. Черкасская (53) 681,325(088,8) (56) Авторское свидетельство СССР

993252, кл. С 06 F 7/38, 1981.

Авторское свидетельство СССР

N - 1124284, кл. G F 7/38, 1983. (54) МНОГОФУНКЦИОНАЛЬНОЕ ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО (57) Изобретение относится к области вычислительной техники и может быть использовано для выполнения операций умножения, деления, извлечения квадратного корня и сортировки больших массивов многоразрядных чисел. Цель изобретения — расширение функциональных возможностей устройства за счет выполнения операции сортировки и повышение производительности обработки больших масси„„SU„, 1293727 А1 вов данных. Устройство конвейерноматричного типа содержит матрицу иэ

N строк и N стлобцов, два дополнительных столбца из К ячеек и И ячеек управления, триггеры, N схем выбора максимального числа, N схем формирования сигнала считывания и элемент ИЛИ, где N — разрядность операндов. Каждая ячейка матрицы и дополнительного столбца содержит два триггера, логические элементы и сумматор, а ячейка управления — логические элементы И, ИЛИ. Схема выбора максимального числа содержит последовательно соединенные элемент

ИЛИ, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ и тригvep а схема формирования сигнала считывания дополнительно к этим элементам включает триггер, два элемента ИЛИ, элемент И. Эффективность устройства растет с увеличением разрядности чисел и обьема обрабатываемой информации. 2 з.п. ф-лы, 8 ил., 2 табл.

93,727 2

27, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 28 и сумматор ?9.

Дополнительная ячейка 2 состоит из триггеров 30 и 31, элемента И 32, элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 33 и сумматора 34.

Управляющая ячейка 3 выполнена на элементах И 35-39 и элементах

ИЛИ 40-43.

10 Блок 4 выбора максимального числа состоит из триггера 44, элемента ИЛИ 45 и элемента ИСКЛЮЧАЮЩЕЕ

ИЛИ 46.

Блок 5 формирования сигнала счи15 тывания содержит триггеры 47 и 48, элементы ИЛИ 49-51, элемент И.52 и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 53.

Блок 15 синхронизации образуют генератор 54 тактовых импульсов, 20 элементы И 55 и 56, дешифратор 57, дешифратор 58 нуля и двоичный счетчик 59, В табл. 1 показано состояние управляющих сигналов в зависимости от

25 выполняемой операции, в табл. 2 состояние информационных входов и выходов устройства в зависимости от выполняемой операции. ! Таблица 1

30—

;Ю

Операция Управляющие сигналы нием нием корня . ени- ровко

О 0

0 0

0 1

Умножение 1

40 С=Со+А В 1 Деление О

Извлечение

45 корня 0

0 0

1 О

Сортировка 0

Таблица 2

Операции

Входы

Выходы

12

8 9 1б

Код 0...0 Инолимое Иношитель

Умноление

Пдоиэаедение старший младший раарлл ааайнд с Co+A В

Константа То ше То ше со

То же

Частное

Остатох

Делимое Делитель

Деление

1 12

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

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

На фиг. 1 представлена функциональная схема устройства; на фиг.2 функциональная схема ячейки матрицы; йа фиг. 3 — схема дополнительной ячейки; на фиг. 4 — схема управляющей ячейки; на фиг. 5 — схема блока выбора максимального числа; на фиг. б — схема блока формирования сигнала считывания, на фиг. 7 — схема блока синхронизации; на фиг. 8— алгоритм сортировки, Устройство содержит ячейки 1 матрицы, дополнительные ячейки 2, управляющие ячейки 3, блоки 4 выбора максимального числа, блоки 5 формирования сигнала считывания, элемент ИЛИ 6, триггеры 7, образующие первую и вторую косоугольные матрицы 7.1 и 7.2 три1теров и косоугольную матрицу 7.3 пар триггеров, первую входную шину 8 операнда, вторую входную шину 9 операнда, выходную шину 10 остатка, выходную шину 11 сортировки,.первую 12 и вторую 13 выходные шины результата и выходную шину 14 сигнала считывания устройства, а также блок 15 синхронизации, третью входную шину 16 операнда, входную шину 17 управления умножением, шину 18 значения "1", шину

19 значения "0", входную шину 20 кода операции и входную шину 21 общего сброса устройства, Ячейку 1 образуют три|теры 22 и

23, элементы И 24-26, элемент ИЛИ мно- сорти деле- извлече-.!

293727

Продолжение табл.2

Выходы

Входы

1З 10

8 9 16

Нэвлечение корня

Подкорен- Код 0...0 ное вырахение .

Сортировка

Код чнеиа

Код числа

Операции умножения и С = C o+A H, выполняются аналогично, однако при умножении на входы 8 подают код

0...0, а при второй операции — код константы Со. При.умножении на втором информационном входе ячейки 3 и на третьих управляющих входах 17 ячеек 2 установлен единичный сигнал, а на втором пятом и шестом выходах управляющей ячейки — нулевой.

Это позволяет настроить на логическое повторение элементы ИСКЛЮЧАЮЩЕЕ

ИЛИ 28 ячеек 1, элемент ИСКЛЮЧАЮЩЕЕ

ИЛИ 33 и элемент И 32 ячейки 2 первой строки. На второй информационный вход ячейки 2 и вход 8 устройства подают нулевой код.

В первом такте первое N-разрядное множимое поступает по шине 9 в триггеры 22 ячеек первой строки. N-й разряд первого множимого поступает по шине 16 в ячейку 3 и через элемент ИЛИ 41 на первый выхбд и первый управляющий вход первой ячейки

1 первой строки. Значение N-го разряда множителя устанавливается на первых входах элементов И 25 всех ячеек 1, на вторые входы которых поступают разряды множнмого с триггера 22. Остальные разряды множителя по входу 16 записываются s триггеры

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

Во втором такте частичная сумма с третьих выходов ячеек 1 первой строки переписывается в триггеры 23 по вторым информационным входам яче" ек 1 второй строки и в триггер 31 по второму информационному входу в ячейку 2 старшего разряда. Первое множимое переписывается с триггеров 22 ячеек 1 первой строки B эти же триггеры второй строки по третьим информационным входам (старший разряд через ячейку 3). (N-1)-й разряд множителя с триггера 7 первого столбца первой косоугольной.ивтрицы

Корень То ае

7.! поступает через ячейку 3 второй строки на элементы И 25 ячеек 1 второй строки. Остальные разряды множителя -переписываются в триггеры 7 !

5 второго столбца первой косоугольной матрицы 7.1.В этом такте во второй строке образуется частичная сумма произведения первого множимого на (N-1)-й разряд множителя, которая складывается с полученной ранее частичной суммой произведения первого множимого íà N-й разряд множителя. Одновременно в первой строке формируется значение старшего разря25 да произведения в ячейке 2: сигнал переноса со второго выхода ячейки

2 второй строки поступает на первый управляющий вход ячейки 2 первой строки и через элементы 32 и 33 на

ЗО вход сумматора 34.

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

В этом такте содержимое триггеров ячеек второй строки переписывается

4п в триггеры ячеек третьей строки, (N-2)-разряд первого множителя переписывается с триггера 7 второго ..

1 . столбца первой косоугольной матрицы 7.1 в ячейку 3 и поступает на входы яче4g ек 1 третьей строки, значение старmего разряда произведения с третье-. го выхода ячейки 2 первой строки переписывается во второй триггер 7 первой пары второго столбца второй строки третьей косоугольной матрицы

7.3,в триггеры ячеек первой строки поступает вторая пара операндов, остальные разряды первого множителя переписываются в триггеры 7 третьего столбца первой косоугольной матрицы 7.1. В этом такте получают в первой строке частичную сумму про изведения второго множимого íà N-й разряд второго множителя, который

5 12 поступает на третий вход ячейки 3 и в ячейки 1 первой строки. Одновременно в третьей строке получают час тичную сумму произведения первого множимного на (N-2)-й разряд первого множителя, которую складывают с полученным ранее результатом. Во второй строке получают вторую цифру старшего разряда произведения, 937?7 мируются единичные (нулевые) сигналы, в связи с чем в сумматорах 29

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

Во втором такте на второй вход второй ячейки 3 может поступить единичный (нулевой) сигнал с второго выхода ячейки 2 первой строки, втором, пятом и шестом на выходах сфор10

По истечении 2n+1 тактов работы результат произведения первой пары чисел получают на выходах 13 (старшие разряды) и на выходах 10 (млад.шие разряды) устройства. Результат произведения следующих пар чисел получают через каждые 3 такта. Старший разряд при операции С=Со + А В формируется на первом выходе 12 устройства.

Операция деления, В ячейках 3 на входах втором и управления делением установлены единичные сигналы, а на третьих управляющих входах ячеек 2 — нрлевые сигналы (табл. 1), Это позволяет настроить на логическое повторение элементы И 25 ячеек 1, оборвать цепь распространения переносов между ячейками 2 и использовать ячейки

2 как ячейки

В первом такте по второму информационному входу ячейки 2, вторым информационным входам ячеек l и установочному входу триггеров 7 второй косоугольной матрицы 7.2 и подают 2И разрядов делимого, которые записывают в соответствующие триггеры

31 ячейки 2, триггеры 23 ячеек 1 и соответствующие триггеры 7 второй косоугольной матрицы 7,2. По шине

9 поступают N разрядов делителя, которые записывают в триггеры 22 ячеек первой строки. Использование ячейки 2 в качестве ячейки 1 позволяет сдвинуть делимое на один разряд влево относительно делителя. Оцерация делЕния производится по алгоритму без восстановления остатка. Вычитанию иэ очередного остатка делителя соответствует суммирование дополнительного кода делителя, Первая цифра первого частного ( формируется на втором выходе ячейки

2 первой строки, единичный (нулевой) сигнал которого свидетельствует о положительном (отрицательном) текущем остатке. Первый остаток перво15

40 ячеек 1 второй строки может быть осуществлено вычитание (суммирование) из кода текущего остатка, Первую цифру частно-о с второго выхода ячейки 2 первой строки записывают в первый триггер 7 первой пары первого столбца третьей косоугольной матрицы

7.3. Первый делитель из триггера 22 ячеек 1 первой строки по четвертому выходу переписывают в аналогичные триггеры ячеек 1 второй строки по третьим информационным входам (в первую ячейку 1 через ячейку 3 второй строки)„ Первый остаток от деления первой пары чисел с третьих выходов ячеек 1 первой строки записывают в триггеры 31 ячейки 2, в триггеры 23 ячеек t,. остальные разряцы делимого с триггером 7 первой строки второй косоугольной матрицы

7.2 переписывают в триггеры 7 второй строки той же матрицы и в триггер 23 N-й ячейки 1 второй строки.

В ячейках 1 и ячейке 2 второй строки образуется вторая цифра первого частного и второй остаток от деления первой пары чисел. Одновременно по шинам 8 и 9 на первую строку поступает вторая пара операндов и в ячейках первой строки формируются первая цифра второго частного и первый остаток от деления второй пары чисел, Результат частного первой пары операндов получают через и тактов на выходах 12, а остаток — на выходах 10. Результат вычислений последующих пар чисел получают на этих выходах через каждый такт.

Операция извлечения корня, Элементы И 25 ячеек 1 установлены на логическое повторение. На входе 17 устройства установлен нулевой сигнал,:в связи с чем ячейки 2 участвуют в:вычислительном процессе как ячейки 1, В первом такте по второму информационному входу и ячейку 2 старшего разряда подают нулевой сигнал, 7 г а по шине 8 — (2N-1)-разрядный код мантиссы подкоренного выражения, который записывается в триггер 3 1 ячейки 2, триггеры 23 ячеек 1 и триггеры 7 первой строки второй косоугольной матрицы 7.2. В триггеры 22 ячеек 1 первой строки записывается нулевой код. В вычислительном процессе участвуют лишь ячейка

2 и две ячейки 1 старших разрядов первой строки матрицы, в которых записан код ОС, С . Этот .код суммируется с кодом " 111", который устанавливается на выходах элементов

28 и 33 этих ячеек. В результате определяется первая цифра корня, которая формируется на третьих выходах соответствующих ячеек 1.

Во втором такте первая цифра корня z с второго выхода ячейки 2 первой строки записывается в первый триггер 7 первой пары третьего столбца косоугольной матрицы 7.3,, а с третьих выходов соответствующих ячеек 1 матрицы и триггеров 7 первой строки второй косоугольной матрицы 7,2 переписываются цифры первого подкоренного выражения в триггеры ячеек второй строки. В вычислительном процессе принимают участие ячейка 2 и три первые ячейки

1 второй строки ° Остальные ячейки

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

Первая часть равна поразрядной операции ИСКЛЮЧАЮ%ЕЕ ИЛИ цифры 21 с кодом

0Z1 и формируется в ячейках 2 и 1 второй строки устройства. Вторая часть равна ,коду "11" и формируется во второй и третьей ячейках 1 этой же строки. В результате определяется вторая цифра корня, которая формируется на втором выходе ячейки 2 второй стро-. ки, и второй остаток на третьих выходах ячеек 1. Одновременно на первую строку поступает второе подкоренное выражение. В дальнейшем извлечение корня осуществляется по алгоритму без восстановления остатка.

В i-м такте к очередному, сдвинутому на 1 разряд влево, остатку справа присоединяются две следующие

93727 8

5

45 цифры подкоренного выражения С gj i 1

С; и получают код, который суммируется с кодом Z; Q+ (OZ, ...Z; ).11.

Действие 7, Ю О осуществляется на

f элементах ИСКЛЮЧАЮЩЕЕ ИЛИ 33 ячейки 2, а действие Z. O+ (OZ ...Zi) на элементах 28 ячеек 1. Одновременно на первую строку устройства поступает i — e подкоренное выражение.

В N-м такте работы предпоследний остаток объединяется с последней . цифрой корня и суммируется с кодом

Z„,0+ (07... ° Z„,).1, а на первую строку поступает N-e подкоренное выражение.

Результат извлечения корня формируется в М-м такте на выходах 12 (результат извлечения корня) и выходах 10 (остаток). Результат извлечения следующего подкоренного выражения-получают через один такт.

Операция сортировки.

Перед началом работы от ЗВМ в блок 15 синхронизации поступает сигнал "Общий сброс" по входной шине

20 устройства. На выходе дешифратора 58 появляется сигнал, которым сбрасываются все триггеры устройства. Тактовые импульсы генератора 54 проходят через элемент И 56 на Свходы и Р-входы всех триггеров устройства (нулевой сигнал на выходе дешифратора 58 не мешает их прохождению). Одновременно тактовые импульсы генератора 54 через элемент

И 55 (при сортировке на втором входе элемента И 55 единичный сигнал) поступают на счетчик 59. Когда счетчик отсчитывает N тактов, на выходе дешифратора 58 появляется единичный сигнал, который закрывает элемент

И 56 и прекращает дальнейшее поступление тактовых импульсов в устройство. В (И+1)-м такте на выходе управления сортировкой появляется единичный сигнал.

На втором входе ячейки 3 первой строки установлен единичный сигнал.

На четвертых входах ячеек 3 всех строк установлены единичные сигналы с первых выходов блоков 5 (с инверсных выходов сброшенных триггеров

48). Так как управляющий вход блока

5 последней строки подключен к нулевой шине, а триггеры сброшены, нулевой сигнал по третьим выходам подается на управляющий вход всех блоков 5, а но вторым выходам — на чет1 293727

55 вертые управляющие входы всех ячеек 1, не разрешая считывания содержимого триггеров 22 через элемент

И 26 на восьмые выходы ячеек 1 и выход 11 устройства.

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

В первом такте N-разрядный код первого сортируемого числа поступает по шине 9 и записывается в триггеры 22 ячеек 1 первой строки.

Во втором такте содержимое триггеров 22 с четвертых выходов ячеек

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

По истечении N тактов во всех строках устройства будут записаны коды N сортируемых чисел.

Одновременно сортируемые числа проходят через блоки 4 для формирования максимального числа из данных и чисел. Б схемах 4 анализируются состояния одноименных разрядов сортируемых чисел. Если в 1.-м разряде всех кодов содержатся все нули, то в нем устанавливается единичный сигнал, а если хоть одна единица — нулевой сигнал. Перед началом работы триггеры 44 блоков 4 сброшены и на одном из входов элементов ИЛИ 45 установлены "0"t. На вторые входы этих элементов 45 поступают коды сортируемых чисел, В единичные состояния устанавливаются те триггеры 44, на второй вход которых поступает единичный сигнал. Б дальнейшем состояние этих триггеров не изменяется.

Сформированный код максимального числа за п тактов по выходам блоков

4 поступает на соответствующие входы элементов ИЛИ 27 всех ячеек 1.

В (n+1)-м такте на вход управления сортировкой ячеек 3 всех строк поступает единичный сигнал, который проходит через элемент И 38 на третий управляющий выход ячеек 1 и разрешает просмотр записанного массива.

Ю

t0

В вертикальном направлении просмотр ведется снизу вверх, т,е. от

N-й строки до первой. В горизонталь ном направлении слева направо элементы ИЛИ 27 и элементы И 24 ячеек

1 образуют цепь последовательного просмотра содержимого триггеров 22 этих ячеек. Цель просмотра не прерывается в том случае, если в соответствующих ячейках на третьих информационн-m входах имеются 1 или если во всех одноименных разрядах всех строк содержатся 0 . Наличие единичного сигнала на информационном входе схемы 5 свидетельствует о том, что в 1.-й строке находится максимальное число, Этот единичный сигнал поступает в триггер 47 блока 5 и через элемент И 52 на второй выход, разрешая считывание максимального числа с триггеров 22 ячеек 1 через элемент И 26 по соответствующим восьмым выходам данной строки, Единичный с тнал на третьем выходе блока 5, где найдено максимальное число, поступает на управляющий вход блока 5 расположенной выше строки, Он запрещает считывание с этой строки, если на информационном входе также установлена "1". Поэтому сначала считывается максимальное число с нижней 1 é строки, а затем с (i-1)-й, (i-2)-й и т,д,, если в данном массиве имеется несколько максимальных чисел.

Единичный сигнал с выхода триггера 47 поступает через элемент .

ИЛИ 6 на выход 14 и управляет считыванием максимального числа. В слу.э чае наличия нескольких максимальных чисел единичный сигнал на выходе 14 присутствует до тех пор, пока последнее максимальное число не будет считано. Нулевой сигнал на выходе

14 разрешает просмотр следующих чисел,, Если в триггере 47 -й строки записана "1" (" 1" на втором выходе и на четвертых управляющих входах ячеек 1) то с этой строки производится считывание максимального числа на выход 11 устройства через элемент И 26 по восьмым выходам ячеек 1

l.-й строки. Одновременно с триггера

47 единичный сигнал поступает на элемент ИЛИ 50 и через элемент 53

ИСКЛВЧАККЕЕ ИЛИ записывается по Sвходу в триггер 48. На первом выхо11 12937? де появляется нулевой сигнал, который, поступая на четвертый вход ячейки 3 этой строки, JJCTBHBB31HBB

Il ll

0 н а четвертом выходе ячейки 3 и исключает данную строку и з дальнейш е го просмотра ° Далее " 0 " с четвертого выхода ячейки 3 проходит в сю строку, поступает на информационный вход блока 5 этой строки и через эл емент ИЛИ 4 9 и о R-входу записывается в триггер 4 7, Появившийся " 0 " н а третьем выходе разрешает считывание максимального слова с расположенных в ьппе строк, а 0 н а четвертом выходе свидетельствует о б окончании считывания с данной с т р оки.!

2 управляющим входом и пятым выходом ячейки матрицы, второй вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ ячейки подключен к выходу элемента И ячейки матрицы, выход элемента ИСКЛЮЧАЮ1ПЕЕ ИЛИ ячей.

Следующий просмотр сортируемых чисел начинается после считывания 20 всех максимальных чисел в данном массиве и появлении нулевого сигнала на выходе 14 элемента ИЛИ 6.

Формула из обретения 25

1. Многофункциональное вычислительное устройство, содержащее матрицу NxN ячеек, столбец из N управляющих ячеек и столбец из N дополнительных ячеек (N — разрядность операндов), причем первый управляющий и первый информационный входы и-й ячейки р-й строки матрицы (n=1,2,..., ...,N-1; р=1,2,...,N) подключены соответственно к первому и второму выходам (и+1)-й ячейки р-й строки матрицы, первый управляющий и первый информационный входы р-й ячейки

N-го столбца матрицы подключены соответственно к первому и второму выходам р-й управляющей ячейки столбца, второй выход р-й ячейки первого столбца матрицы подключен к первому информационному входу р-й дополнительной ячейки столбца, второй информационный вход ячейки m-й (ш =

= 2,3. ..N) строки и п-го столбца матрицы подключен к третьему выходу ячейки (m-1)-й строки (п+1)-го . gg столбца матрицы, второй информационный вход р-й ячейки первой строки матрицы является р-м разрядом первой входной шины операнда устройства, гретий выход и-й ячейки первого столбца матрицы подключен ко второму информационному входу (n+1)-й дополнительной ячейки столбца, третий выход р-й ячейки N-й строки является р-м разрядом выходной шины остатка устройства, третий информационный вход к-й (z=1,2,...,m-2) ячейки m é строки матрицы подключен к четвертому выходу z é ячейки (m-1)-й строки, третий информационный вход (†- и ячейки m-й строки ((= m,...,N) подключен к четвертому выходу -й ячейки (m-1)-й строки, третий информационный вход (m-i)-й ячейки m-й строки матрицы подключен к третьему выходу m-й управляющей ячейки столбца, четвертый выход и-й ячейки п é строки матрицы подключен к первому входу (и+1)-й управляющей ячейки столбца, третий информационный вход р-й ячейки первой строки матрицы является р-м

1 разрядом второй входной шины операнда устройства, второй управляющий вход m-й ячейки р-й строки матрицы подключен к пятому выходу (m — 1) — и ячейки той же строки матрицы, второй управляющий вход первой ячейки р-й строки подключен к четвертому выходу р-й управляющей ячейки столбца, третий управляющий вход р-й ячейки р-й строки матрицы подключен к пятому выходу р-й управляющей ячейки столбца, третий управляющий вход первой ячейки m-й строки матрицы подключен к первому выходу m-й дополнительной ячейки столбца, третий управляющий вход 1-й ячейки строки матрицы (j=3,. ° .,N; i

2...,,j-1) подключен к шестому выходу (i-1)-й ячейки той же строки матрицы, третий управляющий вход

j é ячейки (j -2) — и строки матрицы подключен к второму выходу (j-2)-й управляющей ячейки столбца, тре тий управляющий вход t-й ячейки (j-2)-й строки матрицы (t=j+1,...,N) подключен к пятому выходу (t-1)-Й ячейки той же строки матрицы, второй информационный вход первой дополнительной ячейки столбца является 2N — м разрядом первой входной шины операнда устройства, причем ячейка матрицы содержит сумматор, эле-, мент ИСКЛЮЧАЮЩЕЕ ИЛИ и элемент И, причем первый вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ ячейки является вторым

i 29372 ки матрицы подключен к первому информационному входу сумматора ячей-: ка матрицы, выход суммы сумматора ячейки является третьим выходом ячейки матрицы, выход переноса сумматора ячейки матрицы являются вторым выходом ячейки матрицы, вход переноса сумматора ячейки матрицы является первым информационным входом ячейки матрицы, первый вход элемен- fQ та И ячейки матрицы является первым управляющим входом ячейки матрицы и первым выходом ячейки матрицы, второй вход (n+1)-й управляющей ячейки столбца и первый управляющий 15 вход и-й дополнительной ячейки столбца подключены к второму выходу (и+1)-й дополнительной ячейки столбца, первый управляющий вход N-й дополнительный ячейки столбца подклю- 20 чен к шине значения логического нуля устройства, шестой выход р-й управляющей ячейки столбца подключен к второму управляющему входу р-й дополнительной ячейки столбца, третий вход первой управляющей ячейки столбца является первым разрядом, третьей входной шины операнда устройства, третий управляющей вход всех дополнительных ячеек столбца З0 является вхоцной шиной управления умножением устройства, второй вход первой управляющей ячейки столбца подключен к шине значения логической единицы устройства, причем уп- З5 равляющая ячейка содержит четыре элемента ИЛИ и четыре элемента И, причем первый вход первого элемента

ИЛИ управляющей ячейки является третьим входом этой ячейки, второй вход 40 первого элемента ИЛИ управляющей ячейки подключен к первым входам первого и второго элементов И и второго элемента ИЛИ упра яющей ячейки и является входом управления де- 45 лением управляющей ячейки, первый вход третьего элемента И управляющей ячейки соединен с третьим входом первого элемента ИЛИ управляющей ячейки, первым входом третьего 50 элемента ИЛИ управляющей ячейки, первым входом третьего элемента ИЛИ управляющей ячейки, вторым входом второго элемента ИЛИ управляющей ячейки и является входом управления извлечением квадратного корня управляющей ячейки, выход второго элемента ИЛИ у ц авляющей ячейки под7 14 ключен к первому входу четвертые элемента И управляющей ячейки, второй вход четвертого элемента И управляющей ячейки подключен к вторым входам первого, второго и третьего элементов И управляющей ячейки и является вторым входом управляющей ячейки, выходы второго и третьего элементов И управляющей ячейки подключены соответственно к второму входу третьего элемента ИЛИ управляющей ячейки и первому входу четвертого элемента ИЛИ управляющей ячейки, второй вход четвертого элемента ИЛИ управляющей ячейки является первым входом управляющей ячейки, выход четвертого элемента И управляющей ячейки является шестым выходом управляющей ячейки, выход третьего элемента ИЛИ управляющей ячейки является пятым выходом управляющей ячейки, выход первого элемента И управляющей ячейки является вторым выходом управляющей ячейки, выход четвертого элемента ИЛИ управляющей ячейки является третьим выходом управляющей ячейки, выход первого элемента ИЛИ управляющей ячейки является первым выходом управляющей ячейки, о т л и ч а ю— щ е е с я тем, что, с целью расширения функциональных возможностей путем введения операции сортировки и увеличения производительности устройства, оно дополнительно содержит

N блоков выбора максимального числа, N блоков формирования сигналов считывания, первую косоугольную матрицу триггеров, состоящую из (N-1) строк, п-я строка которой содержит п триггеров, косоугольную матрицу пар триггеров, состоящую из (N-i) строк,п-я строка которой содержит п пар триггеров, элемент ИЛИ, вторую косоугольную матрицу триггеров, содержащую (М-1) столбцов, причем и-й столбец этой матрицы содержит и триггеров, причем восьмой выход и-й ячейки р-го столбца матрицы подключен к четвертому информационному входу (и+1)-й ячейки р-го столбца матрицы, вход р-ro столбца выбора максимального числа соецинен с третьим информационным входом р-й ячейки первой строки матрицы, выход рго блока выбора максимального числа подключен к четвертому информационному входу р-й ячейки первой строки

15 1293 матрицы, вход первого триггера и — и строки первой косоугольной матрицы триггеров является (и+1)-м разрядом третьей входной шины операнда устройства, выход и-го триггера и-й строки первой косоугольной матрицы триггеров подключен к третьему входу (и+1)-й управляющей ячейки столбца, выход х-го триггера, где х =

1,...,j-2, (j-1)-й строки первой косоугольной матрицы триггеров подключен ко входу (х+1)-го триггера той же строки первой косоугольной матрицы триггеров, входы первого и второго триггеров и-й пары и-й строки косоугольной матрицы пар триггеров подключены соответственно ко второму и третьему выходам и-й дополнительной ячейки столбца, выход первого триггера и-й пары (Ы-1)-й 20 строки косоугольной матрицы пар триггеров является и-и разрядом первой выходной шины результата устройства, выход второго триггера и-й пары (N-1)-й строки косоугольной

25 матрицы пар триггеров является и-м разрядом второй выходной шины результата устройства, второй выход

N-й дополнительной ячейки столбца является N-м разрядом первой выходной шины результата устройства, третий выход N-й дополнительной ячейки столбца является N — раэрядом второй выходной шины результата устройства, выходы первого, второго тригге- З5 ров х-й пары (j-2)-й строки косоугольной матрицы пар триггеров подключены к входам соответственно первого и второго триггеров х-й пары (j-1)-й строки косоугольной матрицы пар 40 триггеров, вход первого триггера иго столбца второй косоугольной матрицы триггеров является (N+n)-м разрядом первой входной шины операнда устройства, выход и-го триггера и- 45 го столбца второй косоугольной матрицы триггеров подключен к второму информационному входу N-й ячейки (п+1)-й строки матрицы, выход х-ro триггера (j 1) — го столбца второй 50 косоугольной матрицы триггеров подключен к входу (х+ 1)-го триггера того же столбца второй косоугольной матрицы триггеров, первый выход рго блока формирования сигнала считы- 55 вания подключен к четвертому входу р-й управляющей ячейки столбца, второй выход р-го блока формирова727 ния сигнала считывания подключен к четвертым управляющим входам всех ячеек р-й строки матрицы, управляющий вход и-го блока формирования сигнала считывания подключен к третьему выходу (и+1)-го блока формирования сигнала считывания, управляющий вход N-ro блока формирования сигнала считывания подключен к шине значения логического нуля устройства, четвертый выход р-го блока формирования сигнала считывания подключен к р-му входу элемента ИЛИ, входы сброса всех блоков формирова- . ния сигналов считывания подключены к выходу сброса блока синхронизации, выход элемента ИЛИ является выходной шиной сигнала считывания устройства, информационный вход р-го блока формирования сигнала считывания подключен к пятому выходу р-й ячейки N-го столбца матрицы, вход кода операции блока синхронизации является входной шиной кода операции устройства, вход общего сброса блока синхронизации является входной шиной общего сброса устройства, выход тактовых импульсов блока синхронизации подключен к синхровходам всех триггеров устройства, выход сброса блока синхронизации подключен к входам сброса всех триггеров устройства, выход управления сортировкой блока синхронизации подключен к входам управления сортировкой всех управляющих ячеек столбца, выход управления делением блока синхронизации подключен к входам управления делением всех управляющих ячеек столбца, выход управления извлечением квадратного корня блока синхронизации подключен к входам управления извлечением квад- ратного корня всех управляющих ячеек столбца, седьмой выход d-й (d

=1,...,N N) ячейки матрицыявляется

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

1 29373 тьим информационным входом ячейки, выход второго триггера ячейки матрицы подключен к второму входу первого элемента И ячейки матрицы, первому входу элемента ИЛИ ячейки и 5 первому входу второго элемента И ячейки и является четвертым выходом ячейки матрицы, второй вход второго элемента И ячейки матрицы явля.ется четвертым управляющим входом 10 ячейки матрицы, выход второго элемента И ячейки матрицы является седьмым выходом ячейки матрицы, второй вход элемента фЛИ ячейки матрицы является четвертым информаци- 15 онным входом и восьмым выходом ячейки матрицы, выход элемента ИЛИ ячейки матрицы подключен к первому входу третьего элемента И ячейки матрицы, второй вход третьего элемен- 20 та И ячейки матрицы является третьим управляющим входом ячейки матрицы, выход третьего элемента И ячейки матрицы является шестым выходом, ячейки матрицы, дополнительная ячей25 ка матрицы содержит два rp«rrepa, элемент И, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ и сумматор, причем выход первого триггера дополнительной ячейки подключен к первому входу элемента И дополнительной ячейки, второй вход элемента И дополнительной ячейки является первым управляющим входом дополнительной ячейки, выход элемента И дополнительной ячейки подключен 35 к первому входу элемента ИСКЛЮЧАЮЩЕЕ

ИЛИ дополнительной ячейки, второй вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ дополнительной ячейки является вторым управляющим входом и первым выходом @ дополнительной ячейки, выход второго триггера дополнительной ячейки подключен к первому информационному входу сумматора дополнительной ячейки, выход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ дополнительной ячейки подключен ко второму информационному входу сумматора дополнительной ячейки, вход переноса сумматора дополнительной ячейки является первым информацион- 50 ным входом дополнительной ячейки, выход переноса сумматора дополнительной ячейки, является вторым выходом дополнительной ячейки, выход суммы сумматора дополнительной ячей- 55 ки является третьим выходом дополнительной ячейки, установочный вход второго триггера дополнительной ячей7 18 ки является вторым информационным входом дополнительной ячейки, установочный вход первого триггера дополнительной ячейки является третьим управляющим входом дополнительной ячейки, управляющая ячейка дополнительно содержит пятый элемент И, причем первый вход пятого элемента

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

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

2. Устройство по и. 1, о т л и— ч а ю щ е е с я тем, что каждый блок выбора максимального числа содержит триггер, элемент ИЛИ и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ„ причем первый вход элемента ИЛИ является входом блока выбора максимального числа, второй вход элемента ИЛИ подключен

12937

19 к прямому выходу триггера, выход элемента ИЛИ подключен к первому входу элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, вто. рой вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ подключен к шине значения логического нуля устройства, выход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ подключен к установочному входу триггера, инверсный выход триггера является выходом блока выбора максимального числа. 10

3. Устройство по п. 1, о т л и ч а ю щ е е с я тем, что каждый блок формирования сигнала считывания содержит два триггера, три элемента

ИЛИ, элемент И и элемент ИСКЛЮЧАЮЩЕЕ

ИЛИ, причем инверсный вход перво о элемента ИЛИ объединен с входом асинхронной установки первого триггера и является информационным входом блока формирования сигнала счи- 20 тывания, прямой вход первого элемента ИЛИ является входом сброса блока формирования сигнала считывания, выход первого элемента ИЛИ подключен

25 к входу асинхронного сброса первого триггера, выход первого триггера подключен к первым входам второго элемента ИЛИ и элемента И и яв27 20 ляется четвертым выходом блока формирования сигнала считывания, второй вход второго элемента ИЛИ подключен к прямому выходу второго триггера, выход второго элемента ИЛИ подключен к первому входу элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, второй вход элемента ИСКЛЮЧАЮ!ПЕЕ ИЛИ подключен к шине значения логической единицы устройства, выход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ подключен к входу асинхронной установки второго триггера, вход асинхронного сброса второго триггера объединен со вторым входом первого элемента ИЛИ, инверсный выход второго триггера является первым выходом блока формирования сигнала считывания, выход элемента И подключен к первому входу третьего элемента ИЛИ и является вторым выходом блока формирования сигнала считывания, вторые входы элемента И и третьего элемента ИЛИ объединены между собой и являются управляющими входом блока формирования сигнала считывания, выход третьего элемента ИЛИ является третьим выходом блока формирования сигнала считывания.

l293727

1293727

Фиг. 7

Составитель С. Силаев

Техред И.Попович Корректор Т.

Редактор Л. Пчелинская

Заказ 387/53 Тираж б73 Подписное

ВНИИПИ Государственного комитета СССР по целам изобретений и открытий

1 13035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г„Ужгород,ул. 11роектная 4 рОектмВн9