УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ДВУМЕРНОГО МАССИВА ДАННЫХ (ВАРИАНТЫ) Российский патент 2005 года по МПК G06F7/06 G06F17/16 

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

Известно “Устройство для исследования сетей Петри” по патенту РФ № 2024057, предназначенное для сортировки данных и содержащее блок управления, регистр начальной маркировки, формирователь пачек импульсов, блок задания топологии графа, элементы ИЛИ, формирователь одиночного импульса с временной задержкой, две группы элементов И, дешифратор, схему сравнения, блок памяти, элементы задержки. Блок памяти является общим для аналога и заявляемого изобретения.

Также известно “Устройство для перебора перестановок” по патенту РФ № 2012054, предназначенное для формирования в произвольной последовательности перестановок, и может быть использовано для решения комбинаторных задач. Устройство содержит два дешифратора, два мультипликатора, два элемента ИЛИ, группу из n сумматоров, блоков деления, две группы из n регистров, три группы элементов задержки и группу элементов И. Общими признаками для аналога и предлагаемого технического решения являются две группы из n регистров. Недостатком данного устройства является то, что объектом перестановок является одномерный массив данных.

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

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

Блок регистров первой памяти содержит mn первых регистров хранения единиц информации, каждый из которых принадлежит одному из m непересекающихся множеств, содержащих по n этих регистров, и символизирующих одну из m строк двумерного массива данных, и одновременно принадлежит одному из n непересекающихся множеств, содержащих по m этих регистров, и символизирующих один из n столбцов двумерного массива данных, выходы данных регистров соединены с соответствующими входами блока управления записью в регистры второй памяти.

Блок регистров второй памяти содержит mn вторых регистров хранения единиц информации, каждый из которых принадлежит одному из m непересекающихся множеств, содержащих по n этих регистров, и символизирующих одну из m строк двумерного массива данных, и одновременно принадлежит одному из n непересекающихся множеств, содержащих по m этих регистров, и символизирующих один из n столбцов двумерного массива данных, входы данных регистров соединены с соответствующими выходами блока управления записью в регистры второй памяти.

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

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

Блок управления вводом номеров строк содержит m (по числу строк двумерного массива) дешифраторов номера строки, входы которых являются входами устройства для внешних сигналов, а m выходов каждого из них соединены с соответствующими m входами блока управления считыванием строк, а именно с m первыми входами первых конъюнкторов соответствующего субблока блока управления считыванием строк.

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

Блок управления считыванием столбцов содержит блок управления вводом номеров столбцов, соединенный n² выходами с соответствующими n² входами блока управления считыванием столбцов, также содержит n субблоков, каждый из которых содержит n вторых логических конъюнкторов, первые входы которых подключены к соответствующим выходам блока управления вводом номеров столбцов, вторые входы которых являются входом устройства для вторых тактовых импульсов, второй логический дизъюнктор, к n входам которого подсоединены выходы вторых логических конъюнкторов данного субблока, а выход является выходом данного субблока и подключен к соответствующему входу блока управления записью в регистры второй памяти.

Блок управления вводом номеров столбцов содержит n (по числу столбцов двумерного массива) дешифраторов номера столбца, входы которых являются входами устройства для внешних сигналов, а n выходов каждого из них соединены с соответствующими n входами блока управления считыванием столбцов, а именно с n первыми входами вторых конъюнкторов соответствующего субблока блока управления считыванием столбцов.

Блок управления записью в регистры второй памяти содержит набор из mn третьих логических конъюнкторов, каждый из которых соответствует одному и только одному из регистров блока регистров первой памяти и соответственно относится к определенной строке и определенному столбцу двумерного массива данных, первые входы которых соединены с соответствующим выходом блока управления считыванием строк, а именно с выходом соответствующего первого логического дизъюнктора, при этом к выходу данного k-го логического дизъюнктора подключено n третьих логических конъюнкторов, соответствующих данной k-той строке, вторые входы третьих логических конъюнкторов соединены с соответствующим выходом блока управления считыванием столбцов, а именно с выходом соответствующего второго логического дизъюнктора, при этом к выходу данного 1-го второго логического дизъюнктора подключено m третьих логических конъюнкторов, соответствующих данному 1-му столбцу, третьи входы третьих логических конъюнкторов соединены с выходами соответствующих регистров блока регистров первой памяти, также содержит третий логический дизъюнктор, к mn входам которого подключены выходы третьих логических конъюнкторов, также содержит набор из mn четвертых логических конъюнкторов, каждый из которых соответствует одному и только одному регистру из блока регистров второй памяти и связан своим выходом со входом соответствующего регистра, первые входы четвертых логических конъюнкторов соединены между собой и подключены к выходу третьего логического дизъюнктора, вторые входы четвертых логических конъюнкторов каждой k-той строки соединены между собой и подключены к соответствующей шине k-го первого тактового импульса, третьи входы четвертых логических конъюнкторов каждого 1-того столбца соединены между собой и подключены к соответствующей шине 1-го второго тактового импульса.

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

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

В матрице регистров первой памяти записана информация. Задача изобретения заключается в том, чтобы осуществить заданную перестановку строк и/или столбцов матрицы. Например, поменять местами строки и столбцы следующей бинарной матрицы

Если осуществить следующую перестановку:

то получится преобразованная матрица:

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

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

В устройстве, в котором осуществляется перестановка как строк, так и столбцов, столбцы опрашиваются в пределах опроса одной строки. (Может быть и наоборот.)

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

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

Считанная единица информации, имеющая в первой памяти координаты <i, j> и заданные значения новых координат <t, s>, переписывается во вторую память в регистр, имеющий координаты <t, s>. Тем самым во второй памяти оказывается массив, в котором осуществлена перестановка строк и столбцов исходной матрицы. Данный результат обеспечивается тем, что считывание информации производится в порядке возрастания (убывания) номеров строк и столбцов, заданных извне, а запись во вторую память производится в порядке возрастания (убывания) номеров собственно регистров второй памяти.

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

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

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

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

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

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

В качестве дешифратора может быть использован набор из m (для строк) или из n (для столбцов) двухконтактных переключателей, на входы которых подано напряжение, а выходы являются выходами дешифратора.

Также в качестве дешифратора может быть использован многошаговый переключатель, на вход которого подано напряжение, а m (для строк) или n (для столбцов) выходов являются выходами дешифратора.

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

Также дешифратор может быть выполнен из двоичного счетчика, на вход которого подается последовательность импульсов, и двоично-десятичного дешифратора, входы которого соединены с выходами счетчика, а m (для строк) или n (для столбцов) выходов которого являются выходами дешифратора.

Первые и вторые тактовые импульсы, сигналы обнуления регистров, второй сигнал записи (обратной) могут поступать от внешнего устройства, с которым сопряжено устройство для сортировки двумерного массива данных, а могут вырабатываться встроенным в устройство синхронизатором или блоком формирования тактовых импульсов.

На фиг.1 представлена функциональная схема устройства, здесь 1 - блок управления вводом номеров строк, 2 - блок управления считыванием строк, 3 - блок регистров первый памяти, 4 - блок управления записью в регистры второй памяти, 5 - блок регистров второй памяти, 6 - блок управления обратной записью, 7 - блок управления считыванием столбцов, 8 - блок управления вводом номеров столбцов, 9 - синхронизатор. Показана полная конфигурация устройства, при этом для наглядности блоки управления вводом номеров столбцов и строк вынесены из блоков управления считыванием столбцов и строк. Жирными линиями показаны общие шины, содержащие несколько отдельных соединений. Так шина между блоками 6 и 3 содержит mn отдельных каналов передачи сигналов, шина между блоками 2 и 4 содержит m соединений, шина между 7 и 4 содержит n соединений, шина между 1 и 2 содержит m² соединений, шина между 8 и 7 содержит n² соединений, между блоками 4 и 5 - mn соединений, также между 5 и 6 и между 3 и 4 - по mn соединений. С выхода 3 блока 9 подается сигнал обнуления блока 3, с выхода 4 - второй сигнал записи (обратной), с выхода 5 - сигнал обнуления блока 5.

На фиг.2 изображена функциональная схема блока регистров первой памяти 3 с блоками управления вводом номеров строк 1 и столбцов 8 соответственно, с блоками управления считыванием строк 2 и столбцов 7 соответственно и фрагментом блока управления записью в регистры второй памяти 4. Блоки управления вводом номеров и управления считыванием раскрыты только для столбцов (7 и 8), аналогичные блоки для строк (1 и 2) имеют такую же конструкцию. Здесь 10 - третьи логические элементы И (конъюнкторы), принадлежащие блоку управления записью в регистры второй памяти 4, 11 - первые регистры хранения единиц информации, 12 - субблоки управления считыванием столбцов, входящие в состав блока 7, их число равно числу столбцов, 13 - вторые логические элементы ИЛИ (дизъюнкторы), имеющие n входов, 14 - вторые логические элементы И (конъюнкторы), 15 - дешифраторы номера столбцов, 16 - третий логический элемент ИЛИ (дизъюнктор). Нумерация выводов для элементов 11 и 10 показана только для элементов в верхней строке в левом столбце. У остальных элементов 11 и 10 она такая же.

Как сказано выше, блоки 7 и 8 раскрыты только для столбцов, аналогичные блоки для строк 1 и 2 имеют такую же конструкцию. В силу этого полным аналогом первых логических конъюнкторов, не показанных на фиг.2, являются элементы 14, а полным аналогом первых логических дизъюнкторов являются элементы 13.

На фиг.3 представлена схема блока регистров второй памяти со вторым фрагментом блока управления записью в регистры второй памяти и блоком управления обратной записью. Здесь 17 - пятые логические элементы И, принадлежащие блоку управления обратной записью, 18 - регистры хранения единиц информации, 19 - четвертые логические элементы И, принадлежащие блоку управления записью в регистры второй памяти 4. Нумерация выводов для элементов 18 и 17 показана только для элементов в верхней строке в левом столбце. У остальных элементов 18 и 17 она такая же.

На фиг.4 представлена функциональная схема синхронизатора.

На фиг.5 показаны четыре различных варианта выполнения дешифратора номера столбца (строки).

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

Устройство работает следующим образом.

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

В исходном состоянии в регистрах первой памяти 11 записана некоторая информация в виде двумерного массива. Топологически блок регистров 3 представляет собой двумерную матрицу, состоящую из n столбцов и m строк (фиг.2). Регистры 11 представляют собой логические электронные элементы на базе триггера, предназначенные для хранения логического нуля или единицы (в виде определенных уровней электрического напряжения). Регистры 11 и 18 устроены таким образом, что при подаче единицы на вход 1 регистра он устанавливается в нулевое состояние, т.е. на его выходе 3 - логический ноль. При подаче единицы на вход 2 - на выходе 3 устанавливается логическая единица.

Сигналы записи исходной информации в регистры 11 на фиг.2 не показаны, но она может осуществляться по вторым входам регистров 11 через схемы ИЛИ.

На первые входы как регистров 11, так и регистров 18 (фиг.3) подается сигнал установки в ноль. В начальном состоянии он может формироваться при включении устройства или подаваться от внешнего устройства перед записью массива.

Тактовые импульсы отсутствуют, поэтому на входах 3 и 2 элементов 10 - логический ноль и соответственно на их выходах также ноль (фиг.2). Соответственно первый сигнал записи отсутствует (точнее, имеет нулевое значение). Все сигналы на входах элементов 19 равны нулю и на входы 2 всех регистров 18 поступает ноль (фиг.3).

С выходов 3 элементов 17 на входы 2 элементов 11 поступают нули, следовательно, регистры 11 сохраняют свое состояние.

На входы блоков управления вводом номеров столбцов 8 и строк 1 (фиг.1) соответственно подаются номера столбцов и строк. В исходном состоянии на входах дешифраторов 15 (фиг.2), которые входят в блоки 8 и 2, сигналы отсутствуют. Соответственно на первых входах логических элементов И (конъюнкторах) 14 находится логический ноль и на их выходах также - логический ноль, следовательно, и на выходах логических элементов ИЛИ 13 также логический ноль. Аналогичная картина присутствует для считывания строк, где первые логические конъюнкторы соответствуют элементам 14, а первые логические дизъюнкторы соответствуют элементам 13 (на фиг.2 не показана полностью, речь идет о m выходах блока 2, которые подаются на входы 3 элементов 10).

На входы дешифраторов 15 (аналогично для строк - m входов блока 1) подаются некоторым образом сигналы, соответствующие номерам столбцов (строк), далее “строк” опускается и подразумевается полная аналогия со столбцами. Подача сигнала номера столбца означает замыкание для каждого элемента 15 одного из тумблеров (случай 1) на фиг.5). При этом на выбранный вход элемента 15 подается электрический сигнал, соответствующий параметрам сигнала для логической единицы. Случай 2) (фиг.5) аналогичен, но здесь n тумблеров заменены одним переключателем на n положений. Случай 3) предполагает появление на k входах элемента 15 внешних сигналов, которые представляют собой двоичную комбинацию, равную задаваемому номеру в двоичном коде. Этот код может поступать от внешнего устройства, которое может управлять работой рассматриваемого устройства. Двоично-десятичный дешифратор 34 преобразовывает двоичный код в десятичный, и на одном из его выходов появляется логическая единица, которая и поступает на вход 1 одного из элементов 14 субблока 12 (фиг.2) (для строк вместо элемента 14 следует понимать первый логический конъюнктор). В случае 4) (фиг.5) на вход двоичного счетчика 35 поступает от внешнего устройства пачка импульсов, содержащая количество импульсов, равное задаваемому номеру. Дешифратор 36 преобразовывает двоичный код, накопленный в 35 в десятичный, и обеспечивает появление единицы на одном из своих выходов.

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

На нижней диаграмме (фиг.6) показан первый по времени сигнал, который может соответствовать сообщению о вводе номеров строк и столбцов. Этим сообщением может быть либо сигнал, вводимый оператором после ввода последнего номера, либо сигнал, формируемый внешним устройством. Данный сигнал может запускать синхронизатор 9 (фиг.1) путем подачи единицы на вход 1 триггера 20 (фиг.4), что приводит к появлению единицы на выходе 2 триггера 20, в дальнейшем запускается механизм формирования тактовых импульсов. В случае, если синхронизация работы устройства осуществляется без синхронизатора 9, а с использованием внешнего управляющего устройства, то сигнал запуска синхронизации является внутренним для внешнего устройства и запускает формирование тактовых сигналов, которые поступают на входы заявляемого устройства.

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

Эти импульсы подаются на входы 2 элементов 14 для столбцов (аналогично для строк - на входы первых логических конъюнкторов). При этом j-тый импульс подается на каждый j-тый элемент 14 в каждом из субблоков 12. Таким образом, для каждого столбца последовательно появляются сигналы на входах 2 элементов 14. Если на входе 1 j-го элемента 14 в s-том субблоке 12 находится единица, а это будет, если задан j-тый номер для данного субблока, то на выходе j-го элемента 14 также появится единица, которая пройдет на выход s-го субблока 12 и попадет на входы 2 элементов 10 s-го столбца. В результате появляется разрешение на считывание информации из столбца под номером s, для которого задан номер j.

Аналогично формируются сигналы на входах 3 элементов 10, которые управляют считыванием строк. При одновременном появлении единиц на входах 2 и 3 элементов 10, если в соответствующем регистре 11 записана единица, единица с выхода 4 элемента 10 поступает на один из входов элемента 16 и через него на входы 1 элементов 19, как первый сигнал записи (фиг.3). Считываемый в данный момент регистр 11 может оказаться в нулевом состоянии, поэтому на выходе элемента 16 единица может не появиться. Эту ситуацию на диаграмме (фиг.6) символизируют белые квадраты.

Первые и вторые тактовые импульсы поступают также на соответствующие входы элементов 19, а именно на входы 2 t-той строки - t-тый первый тактовый импульс, а на входы 3 s-того столбца - s-тый второй тактовый импульс.

Если на входе 1 элемента 19 возникает единица, а это происходит, когда есть единица в регистре 11 с координатами <i, j>, то происходит запись единицы в регистр с координатами <t, s>.

Таким образом, по истечении mn вторых тактовых импульсов вся информация из регистров 11 будет переписана в регистры 18 с новыми координатами.

Если обратная перезапись не требуется, то работа устройства завершается.

Если требуется обратная перезапись, то на входы 2 элементов 11 подается сигнал обнуления первой памяти, а именно логическая единица, все регистры 11 переводятся в ноль. Далее через элементы 17, на первые входы которых подается второй сигнал записи (обратной), происходит перезапись содержимого регистров 17 в регистры 11, имеющие те же координаты, что и регистры 17. Далее на входы 1 регистров 18 подается сигнал обнуления регистров второй памяти, они переводятся в нулевое состояние. На этом работа устройства завершается.

Синхронизатор 9 (фиг.4) может работать следующим образом.

В начальном состоянии на вход 1 триггера 20 подается сигнал логической единицы, который устанавливает 20 в единичное состояние по выходу 3, также переводит счетчик 27 в состояние, в котором в нем записана единица, счетчик 25 - в нулевое состояние, сдвиговые регистры 31, 32 и 33 - в нулевое состояние. Счетчик 27 переводится в состояние записанной единицы для того, чтобы сэкономить один цикл из n импульсов. В исходном состоянии на выходах дешифраторов 21 и 22 нули, поэтому на выходе элемента 30 - ноль, а на выходе инвертора 29 - единица. После установки в единицу триггера 20 на входах 3 и 1 элемента 24 - единицы, поэтому тактовые импульсы от генератора 23 начинают проходить через элемент 24.

Их считает по входу n+1 счетчик 25, через дешифратор 21 импульсы попадают на выход схемы синхронизатора 9 в виде вторых тактовых импульсов. Первые тактовые импульсы выходят из дешифратора 22.

При появлении n+1-го тактового импульса на входе счетчика 25 вход 2 элемента 26 открывается, и очередной тактовый импульс от 23 проходит на вход m+1 счетчика 27 и добавляет в нем единицу, вызывая появление следующего тактового импульса на выходе синхронизатора из пачки первых тактовых импульсов. Счетчик 25 устроен таким образом, что считает импульсы только до n+1, следующим импульсом он сбрасывается в ноль и начинает считать сначала. Так же устроен и счетчик 27, с той разницей, что он считает до m и сбрасывается очередным импульсом в единицу.

Первые и вторые тактовые импульсы вырабатываются до тех пор, пока на выходе m дешифратора 21 и выходе n дешифратора 22 одновременно не появляются единицы. В этом случае открывается элемент 28 для прохождения тактовых импульсов от 23 и закрывается элемент 24 через инвертор 29 и схему совпадения 30. На счетчики 25 и 27 тактовые импульсы больше не поступают, напротив, они начинают поступать с элемента 28 на вход 1 сдвигового регистра 31.

При поступлении импульса на вход 1 элемент 31 переключается в единичное состояние, с его выхода 3 в устройство уходит сигнал обнуления регистров первой памяти. Появление второго импульса сбрасывает 31 в ноль и вызывает появление на его выходе 4 импульса, который устанавливает в единицу сдвиговый регистр 32, с выхода 3 которого в устройство поступает сигнал обратной записи. Аналогичным образом третий тактовый импульс вызывает появление сигнала обнуления регистров второй памяти. Одновременно единица на выходе 3 элемента 33 сбрасывает в ноль по входу 2 триггер 20. Ноль на его выходе 3 запирает элемент 24. На этом цикл работы синхронизатора завершается.

Сигнал, который обнуляет 20, также может обнулять счетчики 25 и 27.

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

Различные варианты устройств для сортировки двумерного массива данных выполняются из электронных дискретных элементов, выполняющих логические функции. Триггер 20, регистры 11 и 18, счетчики 25, 27, 35, сдвиговые регистры 31-33 принадлежат к тем элементам, которые способны сохранять свое состояние после пропадания входного сигнала, поэтому их переключение, т.е. изменение значения на их выходах с нуля на единицу и наоборот происходит по переднему фронту подаваемого сигнала, поэтому они могут управляться короткими импульсами. Сигналы на входах и выходах других элементов, а также на выходах 3 регистров 11, 18, 31, 32, 33, триггера 20, также на выходах счетчиков 25 (выходы 1-m), 27 (выходы 1-n) и 35 (выходы 1-k) должны иметь длительность, достаточную для обеспечения переключения всех элементов в заданной цепи, т.е. превышать суммарное время переходных процессов всех элементов, которые должны поменять свое состояние в данном такте. Соответствующей должна быть и длительность тактовых импульсов.

Например, второй тактовый импульс по одной цепи должен осуществить переключение элементов 14, 13, 10, 16, 19 и 18 и по другой цепи - 19 и 18 (фиг.2 и 3). Ясно, что длительность его должна быть не меньше суммарного времени переключения элементов в первой цепи. Длительность тактового импульса из генератора 23 должна быть еще больше, т.к. внутри самого синхронизатора 9 также происходят внутренние переключения (фиг.4).

Выходы 4 сдвиговых регистров 31-33, выполненных на базе триггера, служат для соединения сдвиговых регистров в цепь и могут выдавать короткие импульсы для переключения следующего регистра в цепи.

Счетчики 25, 27 и 33 собираются из логических элементов - двоичных счетчиков, каждый из которых выполнен на основе триггера.

Дешифраторы могут быть выполнены как конечные автоматы с использованием элементов Пирса и/или Шеффера.

Элементы И и ИЛИ могут быть выполнены из элементов Пирса и/или Шеффера.

Регистры 11 и 18 являются хранителями единиц информации. В случае, если в устройстве хранится и обрабатывается двумерный массив, представляющий собой бинарную матрицу, то каждый такой регистр представляет собой элементарный дискретный элемент, в основе которого один триггер. Если единицами информации являются более сложные объекты, например, значения атрибутов базы данных, то один регистр 11 или 18 представляет собой набор элементарных дискретных элементов, число которых в наборе равно числу двоичных разрядов в коде, с помощью которого кодируется данное значение. В этом случае элементы 10, 19, 17 и 16 также превращаются в соответствующие наборы дискретных двоичных элементов.

Изобретение относится к вычислительной технике, а именно к устройствам обработки числовых массивов информации, предназначенным для перестановки строк и столбцов двумерного массива данных, представленного в виде матрицы. Техническим результатом является обеспечение заданной перестановки строк и/или столбцов матрицы. Для этого, согласно первому варианту, устройство содержит блок регистров первой памяти, блок регистров второй памяти, блок управления записью в регистры второй памяти, блок управления считыванием столбцов, блок управления считыванием строк, блок управления обратной записью; согласно второму варианту устройство содержит все те же элементы за исключением блока управления обратной записью. Третий вариант устройства отличается от второго варианта отсутствием блока управления считыванием столбцов, а четвертый вариант устройства отличается от второго отсутствием блока управления считыванием строк. 4 с. и 19 з.п. ф-лы, 6 ил.

1. Устройство для сортировки двумерного массива данных, содержащее блок регистров первой памяти и блок регистров второй памяти, отличающееся тем, что дополнительно содержит блок управления записью в регистры второй памяти, соединенный первыми mn входами с соответствующими mn выходами блока регистров первой памяти, а mn выходами с соответствующими mn входами блока регистров второй памяти, блок управления считыванием столбцов, на входы задания номера столбца которого подаются номера столбцов, а соответствующие n выходов которого соединены со вторыми n входами блока управления записью в регистры второй памяти, блок управления считыванием строк, на входы задания номера строки которого подаются номера строк, а соответствующие m выходов которого соединены с третьими m входами блока управления записью в регистры второй памяти, блок управления обратной записью, соединенный mn входами с соответствующими mn выходами блока регистров второй памяти, а mn выходами с соответствующими mn входами блока регистров первой памяти.2. Устройство по п.1, отличающееся тем, что блок регистров первой памяти содержит mn первых регистров хранения единиц информации, каждый из которых принадлежит одному из m непересекающихся множеств, содержащих по n этих регистров и символизирующих одну из m строк двумерного массива данных, и одновременно принадлежит одному из n непересекающихся множеств, содержащих по m этих регистров и символизирующих один из n столбцов двумерного массива данных, выходы данных регистров соединены с соответствующими входами блока управления записью в регистры второй памяти.3. Устройство по п.1, отличающееся тем, что блок регистров второй памяти содержит mn вторых регистров хранения единиц информации, каждый из которых принадлежит одному из m непересекающихся множеств, содержащих по n этих регистров и символизирующих одну из m строк двумерного массива данных, и одновременно принадлежит одному из n непересекающихся множеств, содержащих по m этих регистров и символизирующих один из n столбцов двумерного массива данных, входы данных регистров соединены с соответствующими выходами блока управления записью в регистры второй памяти.4. Устройство по п.1, отличающееся тем, что блок управления считыванием строк содержит m субблоков, каждый из которых содержит m первых логических конъюнкторов, первые входы которых являются входом задания номера строки устройства для сортировки двумерного массива данных, вторые входы являются входом первых тактовых импульсов устройства для сортировки двумерного массива данных, первый логический дизъюнктор, к m входам которого подсоединены выходы первых логических конъюнкторов данного субблока, а выход является выходом данного субблока и подключен к соответствующему входу блока управления записью в регистры второй памяти.5. Устройство по п.1, отличающееся тем, что блок управления считыванием столбцов содержит n субблоков, каждый из которых содержит n вторых логических конъюнкторов, первые входы которых являются входом задания номера столбца устройства для сортировки двумерного массива данных, вторые входы являются входом вторых тактовых импульсов устройства для сортировки двумерного массива данных, второй логический дизъюнктор, к n входам которого подсоединены выходы вторых логических конъюнкторов данного субблока, а выход является выходом данного субблока и подключен к соответствующему входу блока управления записью в регистры второй памяти.6. Устройство по п.1, отличающееся тем, что блок управления записью в регистры второй памяти содержит набор из mn третьих логических конъюнкторов, каждый из которых соответствует одному и только одному из регистров блока регистров первой памяти и соответственно относится к определенной строке и определенному столбцу двумерного массива данных, первые входы которых соединены с соответствующим выходом блока управления считыванием строк, а именно с выходом соответствующего первого логического дизъюнктора, при этом к выходу данного k-го логического дизъюнктора подключено n третьих логических конъюнкторов, соответствующих данной k-й строке, вторые входы третьих логических конъюнкторов соединены с соответствующим выходом блока управления считыванием столбцов, а именно с выходом соответствующего второго логического дизъюнктора, при этом к выходу данного l-го второго логического дизъюнктора подключено m третьих логических конъюнкторов, соответствующих данному l-му столбцу, третьи входы третьих логических конъюнкторов соединены с выходами соответствующих регистров блока регистров первой памяти, также содержит третий логический дизъюнктор, к mn входам которого подключены выходы третьих логических конъюнкторов, также содержит набор из mn четвертых логических конъюнкторов, каждый из которых соответствует одному и только одному регистру из блока регистров второй памяти и связан своим выходом со входом соответствующего регистра, первые входы четвертых логических конъюнкторов соединены между собой и подключены к выходу третьего логического дизъюнктора, вторые входы четвертых логических конъюнкторов каждой k-й строки соединены между собой и подключены к соответствующей шине k-ro первого тактового импульса, третьи входы четвертых логических конъюнкторов каждого l-го столбца соединены между собой и подключены к соответствующей шине l-го второго тактового импульса.7. Устройство по п.1, отличающееся тем, что блок управления обратной записью выполнен в виде набора из mn пятых логических конъюнкторов, каждый из которых соответствует одному и только одному из регистров блока регистров второй памяти, первые входы пятых логических конъюнкторов соединены между собой и являются входом второго сигнала записи устройства для сортировки двумерного массива данных, вторые входы соединены с выходами соответствующих регистров блока регистров второй памяти, а выходы соединены с соответствующими входами регистров блока регистров первой памяти, имеющих те же номера строк и столбцов, что и данные регистры блока регистров второй памяти.8. Устройство для сортировки двумерного массива данных, содержащее блок регистров первой памяти и блок регистров второй памяти, отличающееся тем, что дополнительно содержит блок управления записью в регистры второй памяти, соединенный первыми mn входами с соответствующими mn выходами блока регистров первой памяти, а mn выходами с соответствующими mn входами блока регистров второй памяти, блок управления считыванием столбцов, на входы задания номера столбца которого подаются номера столбцов, а соответствующие n выходов которого соединены со вторыми n входами блока управления записью в регистры второй памяти, блок управления считыванием строк, на входы задания номера строки которого подаются номера строк, а соответствующие m выходов которого соединены с третьими m входами блока управления записью в регистры второй памяти.9. Устройство по п.8, отличающееся тем, что блок регистров первой памяти содержит mn первых регистров хранения единиц информации, каждый из которых принадлежит одному из m непересекающихся множеств, содержащих по n этих регистров и символизирующих одну из m строк двумерного массива данных, и одновременно принадлежит одному из n непересекающихся множеств, содержащих по m этих регистров и символизирующих один из n столбцов двумерного массива данных, выходы данных регистров соединены с соответствующими входами блока управления записью в регистры второй памяти.10. Устройство по п.8, отличающееся тем, что блок регистров второй памяти содержит mn вторых регистров хранения единиц информации, каждый из которых принадлежит одному из m непересекающихся множеств, содержащих по n этих регистров и символизирующих одну из m строк двумерного массива данных, и одновременно принадлежит одному из n непересекающихся множеств, содержащих по m этих регистров и символизирующих один из n столбцов двумерного массива данных, входы данных регистров соединены с соответствующими выходами блока управления записью в регистры второй памяти.11. Устройство по п.8, отличающееся тем, что блок управления считыванием строк содержит m субблоков, каждый из которых содержит m первых логических конъюнкторов, первые входы которых являются входом задания номера строки устройства для сортировки двумерного массива данных, вторые входы являются входом первых тактовых импульсов устройства для сортировки двумерного массива данных, первый логический дизъюнктор, к m входам которого подсоединены выходы первых логических конъюнкторов данного субблока, а выход является выходом данного субблока и подключен к соответствующему входу блока управления записью в регистры второй памяти.12. Устройство по п.8, отличающееся тем, что блок управления считыванием столбцов содержит n субблоков, каждый из которых содержит n вторых логических конъюнкторов, первые входы которых являются входом задания номера столбца устройства для сортировки двумерного массива данных, вторые входы являются входом вторых тактовых импульсов устройства для сортировки двумерного массива данных, второй логический дизъюнктор, к n входам которого подсоединены выходы вторых логических конъюнкторов данного субблока, а выход является выходом данного субблока и подключен к соответствующему входу блока управления записью в регистры второй памяти.13. Устройство по п.8, отличающееся тем, что блок управления записью в регистры второй памяти содержит набор из mn третьих логических конъюнкторов, каждый из которых соответствует одному и только одному из регистров блока регистров первой памяти и соответственно относится к определенной строке и определенному столбцу двумерного массива данных, первые входы которых соединены с соответствующим выходом блока управления считыванием строк, а именно с выходом соответствующего первого логического дизъюнктора, при этом к выходу данного k-го логического дизъюнктора подключено n третьих логических конъюнкторов, соответствующих данной k-й строке, вторые входы третьих логических конъюнкторов соединены с соответствующим выходом блока управления считыванием столбцов, а именно с выходом соответствующего второго логического дизъюнктора, при этом к выходу данного l-го второго логического дизъюнктора подключено m третьих логических конъюнкторов, соответствующих данному l-му столбцу, третьи входы третьих логических конъюнкторов соединены с выходами соответствующих регистров блока регистров первой памяти, также содержит третий логический дизъюнктор, к mn входам которого подключены выходы третьих логических конъюнкторов, также содержит набор из mn четвертых логических конъюнкторов, каждый из которых соответствует одному и только одному регистру из блока регистров второй памяти и связан своим выходом со входом соответствующего регистра, первые входы четвертых логических конъюнкторов соединены между собой и подключены к выходу третьего логического дизъюнктора, вторые входы четвертых логических конъюнкторов каждой k-й строки соединены между собой и подключены к соответствующей шине k-го первого тактового импульса, третьи входы четвертых логических конъюнкторов каждого l-го столбца соединены между собой и подключены к соответствующей шине l-го второго тактового импульса.14. Устройство для сортировки двумерного массива данных, содержащее блок регистров первой памяти и блок регистров второй памяти, отличающееся тем, что дополнительно содержит блок управления записью в регистры второй памяти, соединенный первыми mn входами с соответствующими mn выходами блока регистров первой памяти, а mn выходами с соответствующими mn входами блока регистров второй памяти, блок управления считыванием строк, на входы задания номера строки которого подаются номера строк, а соответствующие m выходов которого соединены со вторыми m входами блока управления записью в регистры второй памяти.15. Устройство по п.14, отличающееся тем, что блок регистров первой памяти содержит mn первых регистров хранения единиц информации, каждый из которых принадлежит одному из m непересекающихся множеств, содержащих по n этих регистров и символизирующих одну из m строк двумерного массива данных, и одновременно принадлежит одному из n непересекающихся множеств, содержащих по m этих регистров и символизирующих один из n столбцов двумерного массива данных, выходы данных регистров соединены с соответствующими входами блока управления записью в регистры второй памяти.16. Устройство по п.14, отличающееся тем, что блок регистров второй памяти содержит mn вторых регистров хранения единиц информации, каждый из которых принадлежит одному из m непересекающихся множеств, содержащих по n этих регистров и символизирующих одну из m строк двумерного массива данных, и одновременно принадлежит одному из n непересекающихся множеств, содержащих по m этих регистров и символизирующих один из n столбцов двумерного массива данных, входы данных регистров соединены с соответствующими выходами блока управления записью в регистры второй памяти.17. Устройство по п.14, отличающееся тем, что блок управления считыванием строк содержит m субблоков, каждый из которых содержит m первых логических конъюнкторов, первые входы которых являются входом задания номера строки устройства для сортировки двумерного массива данных, вторые входы являются входом первых тактовых импульсов устройства для сортировки двумерного массива данных, первый логический дизъюнктор, к m входам которого подсоединены выходы первых логических конъюнкторов данного субблока, а выход является выходом данного субблока и подключен к соответствующему входу блока управления записью в регистры второй памяти.18. Устройство по п.14, отличающееся тем, что блок управления записью в регистры второй памяти содержит набор из mn третьих логических конъюнкторов, каждый из которых соответствует одному и только одному из регистров блока регистров первой памяти и соответственно относится к определенной строке и определенному столбцу двумерного массива данных, первые входы которых соединены с соответствующим выходом блока управления считыванием строк, а именно с выходом соответствующего первого логического дизъюнктора, при этом к выходу данного k-го логического дизъюнктора подключено n третьих логических конъюнкторов, соответствующих данной k-й строке, вторые входы третьих логических конъюнкторов соединены с соответствующим выходом блока управления считыванием столбцов, а именно с выходом соответствующего второго логического дизъюнктора, при этом к выходу данного l-го второго логического дизъюнктора подключено m третьих логических конъюнкторов, соответствующих данному l-му столбцу, третьи входы третьих логических конъюнкторов соединены с выходами соответствующих регистров блока регистров первой памяти, также содержит третий логический дизъюнктор, к mn входам которого подключены выходы третьих логических конъюнкторов, также содержит набор из mn четвертых логических конъюнкторов, каждый из которых соответствует одному и только одному регистру из блока регистров второй памяти и связан своим выходом со входом соответствующего регистра, первые входы четвертых логических конъюнкторов соединены между собой и подключены к выходу третьего логического дизъюнктора, вторые входы четвертых логических конъюнкторов каждой k-й строки соединены между собой и подключены к соответствующей шине k-го первого тактового импульса, третьи входы четвертых логических конъюнкторов каждого l-го столбца соединены между собой и подключены к соответствующей шине l-го второго тактового импульса.19. Устройство для сортировки двумерного массива данных, содержащее блок регистров первой памяти и блок регистров второй памяти, отличающееся тем, что дополнительно содержит блок управления записью в регистры второй памяти, соединенный первыми mn входами с соответствующими mn выходами блока регистров первой памяти, а mn выходами с соответствующими mn входами блока регистров второй памяти, блок управления считыванием столбцов, на входы задания номера столбца которого подаются номера столбцов, а соответствующие n выходов которого соединены со вторыми n входами блока управления записью в регистры второй памяти.20. Устройство по п.19, отличающееся тем, что блок регистров первой памяти содержит mn первых регистров хранения единиц информации, каждый из которых принадлежит одному из m непересекающихся множеств, содержащих по n этих регистров и символизирующих одну из m строк двумерного массива данных, и одновременно принадлежит одному из n непересекающихся множеств, содержащих по m этих регистров и символизирующих один из n столбцов двумерного массива данных, выходы данных регистров соединены с соответствующими входами блока управления записью в регистры второй памяти.21. Устройство по п.19, отличающееся тем, что блок регистров второй памяти содержит mn вторых регистров хранения единиц информации, каждый из которых принадлежит одному из m непересекающихся множеств, содержащих по n этих регистров и символизирующих одну из m строк двумерного массива данных, и одновременно принадлежит одному из n непересекающихся множеств, содержащих по m этих регистров и символизирующих один из n столбцов двумерного массива данных, входы данных регистров соединены с соответствующими выходами блока управления записью в регистры второй памяти.22. Устройство по п.19, отличающееся тем, что блок управления считыванием столбцов содержит n субблоков, каждый из которых содержит n вторых логических конъюнкторов, первые входы которых являются входом задания номера столбца устройства для сортировки двумерного массива данных, вторые входы являются входом вторых тактовых импульсов устройства для сортировки двумерного массива данных, второй логический дизъюнктор, к n входам которого подсоединены выходы вторых логических конъюнкторов данного субблока, а выход является выходом данного субблока и подключен к соответствующему входу блока управления записью в регистры второй памяти.23. Устройство по п.19, отличающееся тем, что блок управления записью в регистры второй памяти содержит набор из mn третьих логических конъюнкторов, каждый из которых соответствует одному и только одному из регистров блока регистров первой памяти и соответственно относится к определенной строке и определенному столбцу двумерного массива данных, первые входы которых соединены с соответствующим выходом блока управления считыванием строк, а именно с выходом соответствующего первого логического дизъюнктора, при этом к выходу данного k-го логического дизъюнктора подключено n третьих логических конъюнкторов, соответствующих данной k-й строке, вторые входы третьих логических конъюнкторов соединены с соответствующим выходом блока управления считыванием столбцов, а именно с выходом соответствующего второго логического дизъюнктора, при этом к выходу данного l-го второго логического дизъюнктора подключено m третьих логических конъюнкторов, соответствующих данному l-му столбцу, третьи входы третьих логических конъюнкторов соединены с выходами соответствующих регистров блока регистров первой памяти, также содержит третий логический дизъюнктор, к mn входам которого подключены выходы третьих логических конъюнкторов, также содержит набор из mn четвертых логических конъюнкторов, каждый из которых соответствует одному и только одному регистру из блока регистров второй памяти и связан своим выходом со входом соответствующего регистра, первые входы четвертых логических конъюнкторов соединены между собой и подключены к выходу третьего логического дизъюнктора, вторые входы четвертых логических конъюнкторов каждой k-й строки соединены между собой и подключены к соответствующей шине k-го первого тактового импульса, третьи входы четвертых логических конъюнкторов каждого l-го столбца соединены между собой и подключены к соответствующей шине l-го второго тактового импульса.