Устройство для транспонирования матриц

 

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

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

СО1 1ИАЛИСТИЧЕСНИХ

РЕСПУБЛИН

А1 (19) (111 (51) 4 G 06 F 15/347

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

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

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

00 ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPblTHA (21) 4035084/24-24 (22) 11.03.86 (46) 15.03.88, Бюл. М 10 (71) Физико-механический институт им. Г.В. Карпенко (72) П.М. Сопрунюк, Л.A. Коваль, И.С. Витер и B.М. Кравчук (53) 68 1 ° 325(088.8) (56) Погребенко С.В., Царевский Г.С.Препринт ИКИ АН СССР, У 699, 1982, с. 35.

Хуанг Т.С. и др, Быстрые алгоритмы в цифровой обработке изображений.

Пер. с англ. — М.: Радио и связь, 1984, с. 20-24, 27. (54) УСТРОЙСТВО ДЛЯ ТРАКСПОЧИРОВА"

НИЯ МАТРИЦ (57) Изобретение относится к вычислительной технике, может быть использовано при дискретных преобразованиях Фурье и позволяет транспонировать непрерывный лоток матриц в темпе поступления элементов матриц на вход устройства. И(елью изобретения является сокращение агпаратурных затрат за счет записи очередного элемента входной матрицы в ячейку памяти",освободившуюся после считывания очередного элемента транспонируемой матрицы. Устройство со138 l 540...А А

20 гк+(2к

АА ...A;.. AA„, где А;

А

N держит вход 1 для установки порядка транспонируемых матриц, счетчик 2, блок 3 памяти, накапливающие сумматоры 4 и 5, элемент И 6, мультиплексор 7, адресную шину 8 блока 9 памяти, шину 10 данных, вход 11, регистр

12 ввода, канал 13 разрешения записи, регистр 14 вывода, выход 15. TIoставленная цель достигается тем, что матрицы транспонируют считыванием, начиная с первой, из каждой 2" -й ячейки блока 9 памяти, до полного опроса ее ячеек, где 2 — количест х

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

Цель изобретения — сокращение аппаратурных затрат.

На фиг. 1 представлена функциональная схема примера реализации устройства; на фиг. 2 — функциональная схема накаппгзающих сумматоров.

Устройство содержит вход 1 для установки порядка транспонируемых матриц, счетчик ?, блок 3 памяти, накапливающие сумматоры 4 и 5, элемент 6 И, мультиплексор 7, адресную шину 8 блока 9 памяти, шину 10 данных, вход 11, регистр 12 ввода, канал 13 разрешения записи, регистр 14 вывода, выход 15.

В состав накапливающих сумматоров 4 и 5 входят сумматор 16 и регистр 17.

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

Записывают двоичный код адреса (ДКА) ячеек блока 9 памяти в виде:

i --й разряд ДКА, принимающий значение 0 или 1; младший разряд ДКА для записи первой (п=1) матрицы потока в блок 9 памяти; количество разрядов ДКА и во столбцов матрицы; п — порядковый н >мер матрицы потока. При таком способе организации счета после считывания последнего элемента предыдущей матрицы следует считывание второго элемента текущей матрицы, причем параллельно со считыванием осуществляется запись в освободившуюся ячейку памяти элемента; последующей матрицы, а по окончании записи ее транспонируют, начиная с первой из каждой 2 " )к -й ячейки памяти.

2 ил. где Р— составное число, кратное степени 2 и равное объему одной матрицы потока, под-. лежащей транспонированию.

Для считывания первой матрицы (п=1) ДКА принимает вид

А ...А А А А ...Л;...A А к < о н н кч!

О т.е. младший разряд будет А„.

Для записи второй матрицы (и = 2) испол .зуется тот же ДКА, что и для считывания первой матрицы, а считы15 вание осуществляется с использованием ДКА. т,е, при увеличении п на единицу, младшего разряда ДКА увеличивается на К с учетом того, что А является следующим стаРшим разрядом для

А.

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

35 положении младшего разряда ДКА, в виде ДКА второй ячейки блока 9 поступает на входы накапливающих сум1381540 маторов 4 и 5 (фиг. 2), работающих в режиме суммирования (F = А + В +

+ перенос). На выходе накапливающих сумматоров 4 и 5 уже имеется нулевой адрес первой ячейки блока 9, по которому, при наличии сигнала ввода из регистра 12 ввода, производится запись первого элемента первой матрицы потока (n = 1) ° Тактируемый регистром 12 ввода накапливающий сумматор 4 выдает ДКА следующих ячеек блока 9.

Когда первая матрица будет полностью записана, срабатывает элемент 6 И и уменьшает двоичный код на выходе счетчика 2 на ециницу, изменяет ДКА на выходе блока 3 на ДКА к

2 -й ячейки и тем самым подготавливает к выдаче ДКА считывания из накапливающего сумматора 5 и такие же

ДКА записи из накапливающего сумматора 4. Таким образом, с учетом того, что скорость считывания должна быть не меньше скорости записи, вторая матрица (n = 2) записывается в освобождающиеся последовательно ячейки памяти блока 9 в моменты времени между считыванием отдельных элементов первой матрицы. После записи второй матрицы на выходе блока

3 будет ДКА 2 -ой ячейки, в коак торой записан (2" +1)-й элемент второй матрицы, являющийся также вторым элементом транспонированной второй матрицы. Далее процесс повторяется.

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

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

1381540

Составитель А. Мишин

Техред М.Ходанич

Корректор О. Кундрик

Редактор Н. Киштулинец

Заказ 1186/47 Тираж 704

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

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

Подписное

Производственно-полиграфическое предприятие, r. Ужгород, ул. Проектная, 4