Устройство для возведения бинарной матрицы в квадрат

Изобретение относится к области вычислительной техники и может быть использовано для возведения бинарной матрицы размером n*n элементов в квадрат. Техническим результатом является снижение аппаратной сложности при реализации возможности возведения бинарной матрицы размером n*n элементов в квадрат. Технический результат заявляемого технического решения достигается тем, что заявленное решение содержит n*n блоков хранения и группу из n выходных элементов ИЛИ, каждый из блоков хранения содержит элемент И, группу элементов И, группу элементов ИЛИ, триггер, введены первый и второй инверторы, первый, второй и третий сдвиговые регистры, первый, второй и третий элементы задержки, первый, второй, третий и четвертой элементы И, первый, второй и третий коммутаторы; первый, второй и третий элемент ИЛИ, двухступенчатый триггер, вход сброса ячейки блока хранения. 4 ил., 1 табл.

 

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

Известно устройство для умножения бинарных матриц (Патент РФ на полезную модель № 193927. Устройство для умножения бинарных матриц. заявл. 26.06.2019, опубл. 21.11.2019, бюл. № 33.), содержащее матрицу из операционных блоков (где n – размер перемножаемых квадратных матриц), первый и второй блоки коэффициентов матриц, сдвиговый регистр, группу из двухступенчатых регистров, каждый из блоков коэффициентов матриц содержит блоков хранения и группу из выходных элементов ИЛИ, каждый из блоков хранения содержит элемент И, группу из элементов И, группу из элементов ИЛИ, в составе каждого операционного блока первый, второй, третий триггер, первый, второй, третий элементы И, первый, второй элементы ИЛИ, инвертор, в составе каждого блока хранения – триггер, группа элементов И, группа элементов ИЛИ.

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

Наиболее близким по технической сущности к заявляемому изобретению является устройство для умножения ленточной матрицы на полную матрицу (авторское свидетельство СССР № 1534471, кл. G06F 15/347, заявл. 15.01.88, опубл. 07.01.90, бюл. № 1), содержащее матрицу (где m – ширина ленты матрицы – множимого, n – число столбцов матрицы – множителя) операционных блоков, каждый из которых содержит три регистра, умножитель, сумматор, матрицу элементов задержки .

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

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

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

На фиг. 1 изображена функциональная схема устройства; на фиг. 2 – схема блоков хранения; на фиг. 3 – схема ячейки блоков хранения; на фиг. 4 – временные диаграммы этапа умножения i-ой строки на j-ый столбец (а – случай, когда ; б – случай, когда единичное значение получено в результате умножения; в – случай, когда после выполнения умножения; г – временные диаграммы вычисления всех произведений ).

Устройство для возведения бинарной матрицы в квадрат (фиг. 1) содержит элемент НЕ 1, первый 2, второй 3 и третий 9 сдвиговые регистры, элемент задержки 4, элемент И 5, элемент И 6, элемент задержки 7, элемент НЕ 8, блок коэффициентов матрицы 10, коммутатор 11, двухступенчатый триггер 12, элемент И 13, элемент ИЛИ 14, элемент И 15, элемент ИЛИ 16, элемент задержки 17, элемент ИЛИ 18, коммутатор 19, коммутатор 20, управляющий вход 21, вход 22 адреса строки, вход 23 адреса столбца, вход 24 синхронизации, управляющий вход 25, вход 26 синхронизации, вход 27 синхронизации, вход 28 инициализации, вход 29 сброса, выход 30 для выгрузки результатов, блок коэффициентов матрицы содержит группу входов 31 в качестве адресов строк при чтении из запоминающего устройства, группу входов 32 в качестве адресов столбцов при чтении из запоминающего устройства, одноименный вход 33 в качестве адреса строки при записи в ЗУ, одноименный вход 34 в качестве адреса столбца при записи в ЗУ, вход 35 данных записи ЗУ, вход 36 синхровход записи ЗУ, вход сброса 37, каждый блок коэффициентов матрицы 10 имеют однотипную структуру (фиг. 2), каждый из них включает своем составе блоков хранения 52, каждый из которых (фиг. 3) содержит триггер 40, элемент И 39, блок элементов И 41, блок элементов ИЛИ 42, вход 48 синхронизации, вход 49 адреса строки записи,, вход 50 сброса, вход 45 адреса столбца записи, вход 47 данных записи, группу входов 46 адресов строк чтения, группу входов 44 адресов столбцов чтения, группу входов 43 данных от предыдущей строки, группу выходов 51 данных для следующей строки, в состав каждого из блоков коэффициентов матриц также входят группа входов 31 адресов строк чтения, группа входов 32 адресов столбцов чтения, вход 33 адреса строки записи, вход 34 адреса столбца записи, вход 35 данных записи, вход 36 синхронизации, вход 37 сброса, группа элементов ИЛИ 53, группа выходов 38, причем вход инициализации 28 подключен ко входу первого инвертора 1, выход которого подключен к информационным входам первого 2 и второго 3 сдвиговых регистров, вход синхронизации 26 подключен ко второму входу первого элемента И 5, выход которого подключен к синхровходу первого сдвигового регистра 2, выход первого элемента И 5 подключен ко входу второго элемента задержки 7, выход которого подключен ко второму входу второго элемента И 6, первый вход которого подключен к выходу первого сдвигового регистра 2, выход второго элемента И 6 подключен к синхровходу второго сдвигового регистра 3, а входы загрузки первого 2 и второго 3 сдвигового регистра подключены к выходу первого элемента задержки 4, ко входу которого подключен вход инициализации 28, выход первого сдвигового регистра 2 подключен к первому входу первого коммутатора 19, выхода второго сдвигового регистра 3 подключен к первому входу второго коммутатора 20, второй и третий вход первого 19 и второго 20 коммутатора подключен к первому входу 21 устройства, четвертый вход первого коммутатора 19 подключен ко входу адрес строки 22, четвертый вход второго коммутатора 20 подключен ко входу адресу столбца 23, выход первого коммутатора 19 подключен к первому 31₁, третьему 31₂ и седьмому 33 входам блока коэффициентов матрицы 10, выход второго коммутатора 20 подключен ко второму 32₁, шестому 32₃ и восьмому 34 входам блока коэффициентов матрицы 10, на девятый вход 35 блока коэффициентов матрицы 10 подается единичное значение, одиннадцатый вход 37 блока коэффициентов матрицы 10 подключен ко входу инициализации 28 устройства, ко входам четыре 32₂ и пять 31₃ блока коэффициентов матрицы 10 подключен выход третьего сдвигового регистра 9, информационный вход которого подключен к выходу второго инвертора 8, вход которого подключен ко второму входу устройства 25, вход загрузки данных третьего сдвигового регистра 9 подключен к выходу третьего элемента задержки 17, вход подключен ко второму входу устройства 25, синхровход третьего сдвигового регистра 9 подключен к синхровходу 27 устройства, первый выход 38₁ блока коэффициентов матрицы 10 подключен к первому входу третьего коммутатора 11, второй и третий вход которого подключены ко второму входу устройства 25, выход третьего коммутатора 11 подключен к информационному входу двухступенчатого триггера 12, синхровход двухступенчатого триггера подключен к синхровходу 24 устройства, выход двухступенчатого триггера 12 подключен ко второму входу первого элемента ИЛИ 14, вход которого подключен к выходу третьего элемента И 13, первый вход которого подключен ко второму выходу 38₂ блока коэффициентов матрицы 10, а второй вход – к третьему выходу 38₃ блока коэффициентов матрицы 10, выход первого элемента ИЛИ 14 подключен к четвертому входу третьего коммутатора 11, выход двухступенчатого триггера 12 подключен ко второму входу четвертого элемента И 15, первый вход которого подключен к синхровходу 27, выхода четвертого элемента И 15 подключен к первому входу третьего элемента ИЛИ 16, первый вход которого подключен ко входу сброса 29 устройства, выход третьего элемента ИЛИ подключен к десятому входу 36 блока коэффициентов матрицы 10, выход двухступенчатого триггера 12 подключен к первому входу второго элемента ИЛИ 18, второй вход которого подключен к выходу третьего сдвигового регистра 9, выход второго элемента ИЛИ 18 подключен к первому входу первого элемента И 5, первый выход 38₁ блока коэффициентов матрицы 10 подключен к выходу 30 устройства, синхровход блока коэффициентов матрицы 36 подключен к синхровходу 48 каждого из блоков хранения 52, k-й вход (где ) в составе группы адресов строк чтения 31 блока коэффициентов матрицы подключен ко входу 46 адресов строк чтения -го блока хранения (где ), k-й вход (где ) в составе группы адресов столбцов чтения 32 блока коэффициентов матрицы подключен ко входу 44 адресов столбцов чтения -го блока хранения (где ), k-й вход (где ) в составе группы входов 43 данных от предыдущей строки -го блока хранения (где , ) подключен к k-му выходу данных 51 для следующей строки -го блока хранения, k-й вход (где ) в составе группы адресов строк записи 33 блока коэффициентов матрицы подключен ко входу 49 адресов строк записи -го блока хранения (где ), k-й вход (где ) в составе группы адресов столбцов записи 34 блока коэффициентов матрицы подключен ко входу 45 адресов столбцов записи -го блока хранения (где ), вход 35 данных записи блока коэффициентов матрицы подключен ко входу 47 данных записи каждого из блоков хранения, k-й выход (где ) в составе группы выходов 51 данных для следующей строки -го блока хранения (где ) подключен к p-му входу k-го элемента группы элементов ИЛИ 53 блока коэффициентов матрицы, выход k-го (где ) элемента группы элементов ИЛИ 53 блока коэффициентов матрицы подключен к k-му выходу 38 в составе группы выходов блока коэффициентов матрицы, в составе каждого из блоков хранения первый вход элемента И 39 блока хранения подключен ко входу 45 адреса столбца записи блока хранения, синхросигнал 48 поступает на второй вход элемента И 39 блока хранения, третий вход элемента И 39 блока хранения подключен ко входу 49 адреса строки записи блока хранения, информационный вход триггера 40 подключен ко входу 47 данных записи блока хранения, а синхровход триггера 40 – к выходу элемента И 39, вход сброса триггера 40 подключен ко входу 50 сброса блока хранения, выход триггера 40 подключен к первому входу каждого из n элементов группы элементов И , выход каждого из n элементов группы элементов И подключен к первому входу каждого из n элементов группы элементов ИЛИ , второй вход каждого i-го элемента группы элементов ИЛИ подключен к i-му разряду входа данных от предыдущей строки блока хранения, а выход каждого i-го элемента группы элементов ИЛИ подключен к i-му разряду выхода данных для следующей строки блока хранения, второй вход каждого i-го элемента группы элементов И подключен к i-му разряду входа адреса строки чтения блока хранения, а третий вход каждого i-го элемента группы элементов И подключен к i-му разряду входа адреса столбца чтения блока хранения.

Элемент НЕ 1 используется для формирования единичных значений «00…01» в регистрах 2 и 3 при инициализации схемы. Сдвиговые регистры 2 и 3 используются для хранения индексов i и j номеров строки и столбца матрицы соответственно. Элемент задержки 4 служит для задержки поступления сигнала 28 (L) на одноименные входы регистров 2 и 3, что позволяет избежать временных гонок и обеспечивает корректную запись начальных значений в регистры. Элемент И 5 закрывает синхровход регистра 2 от прохождения синхроимпульсов 26 до завершения работы схемы, предотвращая преждевременное изменение содержимого регистра 2. Элемент И 6 обеспечивает модификацию (сдвиг) содержимого регистра 3 по приходу синхросигнала 26 только при наличии единичного сигнала переноса из регистра 2. Элемент задержки 7 служит для задержки поступления сигнала на одноименные входы регистра 3, что позволяет избежать временных гонок и обеспечивает корректную запись начальных значений в регистр. Элемент НЕ 8 используется для формирования на информационном входе регистра 9 начального значения «00…01». Сдвиговый регистр 9 используется для хранения индекса k с целью обращения к элементам и матрицы. Блок коэффициентов матрицы 10 используется для хранения элементов матрицы, содержит . Коммутатор 11 применяется для инициализации начального значения двухступенчатого триггера 12 значением и его последующего изменения . Двухступенчатый триггер 12 хранит текущее значение , определяемое в ходе работы схемы. Элемент И 13 применяется для нахождения значения конъюнкции . Элемент ИЛИ 14 предназначен для определения модифицированного значения. Элемент И 15 управляет прохождением синхросигнала 27 на вход 36 запоминающего устройства 10, что обеспечивает запись единичного значения признака достижимости . Элемент ИЛИ 16 используется для сброса значение, который ранятся в блоке коэффициентов матрицы на этапе инициализации. Элемент задержки 17 предназначен для задержки поступления единичного значения сигнала 25 на вход записи регистра 9 с целью избежания временных гонок при формировании на его информационном входе значения «00…01». Элемент ИЛИ 18 используется для формирования бинарного признака окончания работы схемы. Коммутатор 19 применяется для инициализации начального значения i ЗУ 10 и его последующего изменения. Коммутатор 20 применяется для переключения начального значения j ЗУ 10 и его последующего изменения. На вход 21 подается двоичный сигнал, переключающий коммутаторы 19 и 20 между режимами загрузки данных и режимом работы схемы. Вход 22 используется в качестве адреса строки единичного элемента матрицы при ее загрузке. Вход 23 используется в качестве адреса строки единичного элемента матрицы при ее загрузке. На вход 24 подается синхросигнал, поступающий на синхровход триггера 12. На вход 25 подается сигнал , который устанавливается равным 1, при переключении в 0, закрывает коммутатор 11 для прохождения сигнала с выхода 38₁ ЗУ 10 на D-вход триггера 12 и, соответственно, открывает коммутатор 11 для прохождения значения сигнала с выхода элемента 14 на D-вход триггера 12, которое фиксируется в триггере 12 по приходу синхросигнала 24. На вход 26 подается синхроимпульс , поступающий на элемент И 5. На вход 27 подается синхросигнал . На вход 28 подается сигнал инициализации, который используется для задания начальных значений регистров 2 и 3. На вход 29 подается единичный импульс. Выход 30 используется для выгрузки результатов умножения (элементов матрицы). Группа входов 31₁, 31₂, 31₃ используется в качестве адресов строк при чтении из запоминающего устройства с использованием трех портов. Группа входов 32₁, 32₂, 32₃ используется в качестве адресов столбцов при чтении из запоминающего устройства с использованием трех портов. Одноименный вход 33 используется в качестве адреса строки при записи в ЗУ. Одноименный вход 34 используется в качестве адреса столбца при записи в ЗУ. Вход 35 используется в качестве входа данных записи блока коэффициентов матрицы. Вход 36 используется в качестве синхровхода записи блока коэффициентов матрицы 10. На вход 37 подается единичный импульс . Группа выходов 38₁, 38₂, 38₃ используются в качестве результатов чтения с использованием трех портов. Блоки хранения 52, объединенные в матрицу , образуют собой блок коэффициентов матрицы. Триггер 40 используется для хранение элементов матрицы . Элемент И 39 управляет прохождением синхросигнала 48 записи в ячейку с координатами , определяемую соответствующими сигналами на входах 45 и 49. Блоки элементов И управляют прохождением на входы соответствующих блоков элементов ИЛИ группы из n значений с выходов триггеров 40, причем выбранные значения определяются координатами искомых строк и столбцов на входах и . Элементы ИЛИ в составе блоков хранения 52 в совокупности с элементами ИЛИ обеспечивают получение на выходах блока коэффициентов матрицы очередной группы коэффициентов матрицы в соответствии с логикой работы матрицы, причем n пар адресов строк и столбцов искомых коэффициентов определяются значениями на входах и блоков хранения 52. Вход 48 синхронизации используется при записи начальных значений коэффициентов матриц в триггеры 40. Входы 49 и 45 адреса строки i и столбца j записи обеспечивают выбор ij-го блока хранения 52 в составе блока коэффициентов матрицы путем управления прохождением синхросигнала 48 через элемент И 39 при записи требуемого коэффициента со входа 47 в триггер 40 выбранного ij-го блока хранения 52. Вход 50 ячейки блока коэффициентов матрицы используется для сброса триггеров 40 в составе блоков хранения перед началом работы устройства. Вход 47 данных записи используется для приема блоком хранения 52 коэффициентов матриц с целью их записи в триггеры 40. Группа входов адресов строк чтения в совокупности с группой входов адресов столбцов чтения используются для управления прохождением значений группы из n коэффициентов матрицы из триггеров 40 блоков хранения 52 на выходы блока коэффициентов матрицы. Группа входов данных от предыдущей строки в совокупности с группой входов данных для следующей строки используется для формирования искомых значений дизъюнкции группы выбранных значений коэффициентов матриц по столбцам блоков хранения 52, получаемой на выходах блоков хранения 52 n-й строки блока коэффициентов матрицы. Вход 31 адресов строк чтения в совокупности со входом 32 адресов столбцов чтения используются для получения блоком коэффициентов матрицы адресов строк и столбцов требуемых элементов с целью их выборки из триггеров 40 и выдачи на выходы . Вход 33 адреса строки записи в совокупности со входом 34 адреса столбца записи используются для получения блоком коэффициентов матрицы значений i-й строки и j-го столбца с целью последующей записи в выбранный ij-й операционный блок значения коэффициента, поданного на вход 35 данных записи. Вход 36 синхронизации используется для приема стробирующего сигнала записи данных со входа 35 блока коэффициентов матрицы в выбранный ij-й блок хранения 52. Вход 37 блока коэффициентов матрицы используется для сброса триггеров 40 в составе блоков хранения перед началом работы устройства. Группа элементов ИЛИ используется для формирования на выходах блока коэффициентов матрицы дизъюнкций значений с выходов блоков хранения 52 блока коэффициентов матрицы с целью формирования группы из n искомых коэффициентов матрицы в соответствии с их адресами на входах 31 и 32. На выходах блока коэффициентов матрицы производится формирование группы из n коэффициентов матрицы.

Устройство работает следующим образом. Перед началом работы устройства на вход 28 подается единичный импульс, который поступает на вход сброса 37 блока коэффициентов матрицы 10. Со входа сброса 37 блока коэффициентов матрицы 10 единичный импульс проходит на входы 50 всех блоков хранения . Со входа 50 блока хранения 52 единичный импульс проходит на вход сброса триггера 40, что, с учетом нулевого значения на входе установки триггера 40, обеспечивает запись нулевого значения. В результате во всех блоках хранения оказывается записано нулевое значение.

Также единичный импульс со входа 28 поступает на элемент НЕ 1 и формирует на информационных входах сдвиговых регистров 2 и 3 значения «00…01». Далее, проходя через элемент задержки 4, единичное значение сигнала со входа 28 поступает на входы загрузки данных сдвиговых регистров 2 и 3, обеспечивая тем самым фиксацию в них начальных значений «00…01».

На этапе загрузки исходных данных на вход 21 подается нулевое значение, которое переключает коммутаторы 19 и 20 для прохождения сигналов адреса записи строки и адреса записи столбца со входов 22 и 23 на одноименные входы 33 и 34 блока коэффициентов матрицы 10 соответственно. Далее, на входы 22 и 23 внешним устройством поочередно подаются адреса строк и столбцов элементов загружаемой матрицы, имеющих единичное значение. Запись каждого единичного значения производится путем подачи единичного импульса на вход 29, который проходит через элемент ИЛИ 16 на синхровход записи 36 блока коэффициентов матрицы 10.

Значение коэффициента со входа 35 блока коэффициентов матрицы поступает на входы 47 блоков хранения 52 и затем на информационный вход триггера 40 в каждом из блоков хранения. Значения адресов строки и столбца со входов 33 и 34 блока коэффициентов матрицы 10 поступают соответственно на входы 49 и 45 блоков хранения 52, причем i-й разряд со входа 33 подается на входы 49 блоков хранения 52 i-й строки блока коэффициентов матрицы, а j-й разряд со входа 34 подается на входы 45 блоков хранения 52 j-го столбца блока коэффициентов матрицы, . Синхроимпульс со входа 36 блока коэффициентов матрицы 10 поступает на входы 48 блоков хранения 52 и далее на вход элемента И 39. Единичные значения со входов 49 и 45, соответствующие выбранному блоку хранения , поступают на вход элемента И 39 блока хранения и открывают его для прохождения синхросигнала на синхровход триггера 40, обеспечивая запись очередного коэффициента. Во всех остальных блоках хранения 52 как минимум на одном из входов 49 или 45 присутствует нулевое значение, элементы И 39 закрыты для прохождения синхросигнала и запись значения в триггер 40 не происходит.

На этапе работы на вход 21 подается единичное значение, которое переключает коммутаторы 19 и 20 для прохождения значений и в унитарном коде с выходов сдвиговых регистров 2 и 3 на входы и блока коэффициентов матрицы 10 соответственно. Значения и на входах обеспечивают чтение значения , формируемого на выходе блока коэффициентов матрицы 10.

Чтение информации из блока коэффициентов матрицы 10, имеющего матричную структуру из блоков хранения , происходит следующим образом. Блок коэффициентов матрицы 10 включает в своем составе три порта чтения, образованных входами адреса строки первого порта , адреса столбца первого порта , адреса строки второго порта , адреса столбца второго порта и адреса строки третьего порта , адреса столбца третьего порта . Чтение информации по каждому из портов происходит единообразно. Единичное значение i-го бита на входе 31 блока коэффициентов матрицы 10 обеспечивает выбор i-ой строки, а единичное значение j-го бита на входе 32 блока коэффициентов матрицы 10 – выбор j-го столбца. Указанные единичные значения со входов и блока хранения открывают элемент И для прохождения сигнала с выхода триггера 40 на первый вход элемента ИЛИ . На выходах элементов И всех остальных блоков хранения 52 сформировано нулевое значение ввиду того, что элементы И закрыты для прохождения сигнала с триггеров 40 нулевым значением со входов или , что формирует нулевые значения на выходах 51₁. Значение проходит через элементы И 41₁ и ИЛИ 42₁ и попадает на выход блока хранения . На входы блоков хранения первой строки подаются нулевые значения. На входах всех остальных блоков хранения, кроме присутствуют нулевые значение. Значения с выхода 51₁ проходит последовательно через элементы ИЛИ 42₁ блоков хранения и элемент ИЛИ 53₁, попадая на выход 38₁.

На этапе умножения i-й строки на j-й столбец на вход 25 подается единичное значение.

Значение с выхода блока коэффициентов матрицы 10 проходит через коммутатор 11, открытый единичным значением сигнала со входа 25, и попадает на информационный вход двухступенчатого триггера 12. По приходу синхросигнала со входа 24 прочитанное значение сохраняется в двухступенчатом триггере 12. На выходе элемента ИЛИ 18 формируется единичное значение сигнала готовности.

Установленный в единицу сигнал со входа 25 приходит через инвертор 8 и формирует на информационном входе сдвигового регистра 9 значение «00…01» (единица в младшем нулевом разряде), что записывается в сдвиговый регистр 9 при прохождении соответствующего единичного значения сигнала со входа 25 на вход загрузки данных сдвигового регистра 9 через элемент задержки 17. Данное значение представляет собой номер индекса k, используемый для получения значений и матрицы. Значения i и k, поступающие на входы и блока коэффициентов матрицы 10, формируют на его выходе значение , а значения k и j, поступающие на входы и блока коэффициентов матрицы 10 – значение на выходе . Прочитанные значения подаются на входы элемента И 13, на выходе которого формируется конъюнкция . Сформированное значение подается на первый вход элемента ИЛИ 14, на второй вход которого с выхода двухступенчатого триггера 12 подается сформированное на предыдущих шагах работы значение дизъюнкции. На выходе элемента ИЛИ 14 формируется значение , которое подается на второй вход коммутатора 11.

Далее сигнал со входа 25 переключается в ноль, что закрывает коммутатор 11 для прохождения значения сигнала с выхода блока коэффициентов матрицы 10 на информационный вход двухступенчатого триггера 12, и, соответственно, открывает коммутатор 11 для прохождения значения сигнала с выхода элемента ИЛИ 14 на информационный вход двухступенчатого триггера 12, которое фиксируется в двухступенчатом триггере 12 по приходу синхросигнала со входа 24.

Далее синхросигнал со входа 27 устанавливается в единичное значение, которое производит сдвиг влево содержимого сдвигового регистра 9, что фактически эквивалентно инкременту текущего значения k в унитарном коде. Если на данной итерации в двухступенчатом триггере 12 хранится единичное значение, оно открывает элемент И 15 для прохождения синхросигнала со входа 27 через элемент ИЛИ 16 на синхровход записи 36 блока коэффициентов матрицы 10, что приводит к записи единичного значения в элемент матрицы взамен предыдущего нулевого. В противном случае (двухступенчатый триггер 12 хранит нулевое значение) новое значение k обеспечивает чтение новых значений и матрицы из блока коэффициентов матрицы 10 – производится переход к новой итерации.

Если после обработки очередного k-го дизъюнкта двухступенчатый триггер 12 хранит единичное значение, на выходе элемента ИЛИ 18 аналогично рассмотренному выше формируется единичное значение признака окончания обработки.

Если после поступления n синхроимпульсов на вход 27 в двухступенчатом триггере 12 хранится нулевое значение, в старшем разряде сдвигового регистра 9 формируется единичное значение, которое поступает на второй вход элемента ИЛИ 18 и формирует на его выходе единичное значение.

После завершения умножения i-й строки на j-й столбец единичное значение с выхода элемента ИЛИ 18 открывает элемент И 5 для прохождения синхросигнала со входа 26 на синхровход регистра 2, обеспечивая сдвиг его содержимого в сторону старших разрядов ( инкремент значения i в унитарном коде). Далее процесс умножения повторяется для (i+1)-й строки и j-го столбца аналогично рассмотренному выше. После выполнения n итераций умножения единичное значение в составе сдвигового регистра 2 попадает в (n+1)-й разряд. С выхода сдвигового регистра 2 указанное значение открывает элемент И 6 для прохождения сихнросигнала со входа 26 через элементы И 5 и элемент задержки 7 на синхровход сдвигового регистра 3, обеспечивая инкремент номера j-го столбца в унитарном коде. Поступление n² синхроимпульсов на вход 26 обеспечивает получение n² результатов умножения .

На этапе выгрузки на вход 21 подается нулевое значение, которое открывает коммутаторы 19 и 20 для прохождения сигналов адреса строки и столбца со входов 22 и 23 устройства на входы 31₁ и 32₁ блока коэффициентов матрицы 10 соответственно. На входы 22 и 23 устройства поочередно подаются адреса строк i и столбцов j читаемых элементов, которые поступают на входы 31₁ и 32₁ блока коэффициентов матрицы 10 соответственно, формируя на выходе 38₁ значение , поступающее на выход 30 устройства.

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

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

Блок хранения 52 предлагаемого устройства (фиг. 3) включает в себя: элемент И 39 сложностью 2 эквивалентных вентиля; триггер 40 сложностью 4 эквивалентных вентиля; элемент И 41 сложностью 2 эквивалентных вентиля; элемент ИЛИ 42 сложностью 1 эквивалентный вентиль.

Совокупная аппаратная сложность блока хранения предлагаемого устройства определяется как

Аппаратная сложность блока коэффициентов матрицы предлагаемого устройства складывается из аппаратной сложности блоков хранения и аппаратной сложности блока элементов 53:

Предлагаемое устройство содержит: элемент НЕ 1 сложностью 1 эквивалентный вентиль, сдвиговый регистр 2 сложностью эквивалентных вентилей, сдвиговый регистр 3 сложностью эквивалентных вентилей, элемент задержки 4 сложностью 2 эквивалентных вентиля, элемент И 5 сложностью 1 эквивалентный вентиль, элемент И 6 сложностью 1 эквивалентный вентиль, элемент задержки 7 сложностью 2 эквивалентных вентиля, элемент НЕ 8 сложностью 1 эквивалентный вентиль, сдвиговый регистр 9 сложностью эквивалентных вентилей, блок коэффициентов матрицы 10 сложностью коммутатор 11 сложностью 3 эквивалентных вентиля, двухступенчатый триггер 12 сложностью 8 эквивалентных вентилей, элемент И 13 сложностью 1 эквивалентный вентиль, элемент ИЛИ 14 сложностью 1 эквивалентный вентиль, элемент И 15 сложностью 1 эквивалентный вентиль, элемент ИЛИ 16 сложностью 1 эквивалентный вентиль, элемент задержки 17 сложностью 2 эквивалентных вентиля, элемент ИЛИ 18 сложностью 1 эквивалентный вентиль, коммутатор 19 сложностью 3n эквивалентных вентилей, коммутатор 20 сложностью 3n эквивалентных вентилей.

Совокупная аппаратная сложность предлагаемого устройства определяется как

Значения величины аппаратной сложности для прототипа приведены в Патенте РФ на полезную модель № 193927. Устройство для умножения бинарных матриц. заявл. 26.06.2019, опубл. 21.11.2019, бюл. № 33..

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

n	Предлагаемое устройство, ЭВ	Прототип, ЭВ	Выигрыш, раз
10	2,0×103	1,1×104	5,6
100	1,5×105	6,5×106	42,2
1000	1,5×107	6,1×109	402,3

Из представленных данных следует, что предлагаемое устройство обладает в 5,6 – 402,3 раз меньшей аппаратной сложностью по сравнению с прототипом в зависимости от размера матрицы n.

Устройство для возведения бинарной матрицы в квадрат, содержащее блоков хранения и группу из n выходных элементов ИЛИ, каждый из блоков хранения содержит элемент И, группу элементов И, группу элементов ИЛИ, триггер, причем в составе каждого из блоков коэффициентов матриц синхровход блока коэффициентов матрицы подключен к синхровходам каждого из блоков хранения, k-й вход (где ) в составе группы адресов строк чтения блока коэффициентов матрицы подключен ко входу адресов строк чтения -го блока хранения (где ), k-й вход (где ) в составе группы адресов столбцов чтения блока коэффициентов матрицы подключен ко входу адресов столбцов чтения -го блока хранения (где ), k-й вход (где ) в составе группы входов данных от предыдущей строки -го блока хранения (где , ) подключен к k-му выходу данных для следующей строки -го блока хранения, k-й вход (где ) в составе группы адресов строк записи блока коэффициентов матрицы подключен ко входу адресов строк записи -го блока хранения (где ), k-й вход (где ) в составе группы адресов столбцов записи блока коэффициентов матрицы подключен ко входу адресов столбцов записи -го блока хранения (где ), вход данных записи блока коэффициентов матрицы подключен ко входу данных записи каждого из блоков хранения, k-й выход (где ) в составе группы выходов данных для следующей строки -го блока хранения (где ) подключен к p-му входу k-го элемента группы элементов ИЛИ блока коэффициентов матрицы, выход k-го (где ) элемента группы элементов ИЛИ блока коэффициентов матрицы подключен к k-му выходу в составе группы выходов блока коэффициентов матрицы, первый вход элемента И блока хранения подключен ко входу адреса столбца записи блока хранения, синхросигнал поступает на второй вход элемента И блока хранения, третий вход элемента И блока хранения подключен ко входу адреса строки записи блока хранения, информационный вход триггера подключен ко входу данных записи блока хранения, а синхровход триггера – к выходу элемента И, вход сброса триггера подключен ко входу сброса блока хранения, выход триггера подключен к первому входу каждого из n элементов группы элементов И, выход каждого из n элементов группы элементов И подключен к первому входу каждого из n элементов группы элементов ИЛИ, второй вход каждого i-го элемента группы элементов ИЛИ подключен к i-му разряду входа данных от предыдущей строки блока хранения, а выход каждого i-го элемента группы элементов ИЛИ подключен к i-му разряду выхода данных для следующей строки блока хранения, второй вход каждого i-го элемента группы элементов И подключен к i-му разряду входа адреса строки чтения блока хранения, а третий вход каждого i-го элемента группы элементов И подключен к i-му разряду входа адреса столбца чтения блока хранения, дополнительно введены первый и второй инверторы, первый, второй и третий сдвиговые регистры, первый, второй и третий элементы задержки, первый, второй, третий и четвертой элементы И, первый, второй и третий коммутаторы; первый, второй и третий элементы ИЛИ, двухступенчатый триггер, вход сброса ячейки блока хранения, причем вход инициализации подключен ко входу первого инвертора, выход которого подключен к информационным входам первого и второго сдвиговых регистров, вход синхронизации подключен ко второму входу первого элемента И, выход которого подключен к синхровходу первого сдвигового регистра, выход первого элемента И подключен ко входу второго элемента задержки, выход которого подключен ко второму входу второго элемента И, первый вход которого подключен к выходу первого сдвигового регистра, выход второго элемента И подключен к синхровходу второго сдвигового регистра, а входы загрузки первого и второго сдвиговоых регистров подключены к выходу первого элемента задержки, ко входу которого подключен вход инициализации, выход первого сдвигового регистра подключен к первому входу первого коммутатора, выход второго сдвигового регистра подключен к первому входу второго коммутатора, второй и третий входы первого и второго коммутаторов подключены к первому входу устройства, четвертый вход первого коммутатора подключен ко входу адреса строки, четвертый вход второго коммутатора подключен ко входу адреса столбца, выход первого коммутатора подключен к первому, третьему и седьмому входам блока коэффициентов матрицы, выход второго коммутатора подключен ко второму, шестому и восьмому входам блока коэффициентов матрицы, на девятый вход блока коэффициентов матрицы подается единичное значение, одиннадцатый вход блока коэффициентов матрицы подключен ко входу инициализации устройства, ко входам четыре и пять блока коэффициентов матрицы подключен выход третьего сдвигового регистра, информационный вход которого подключен к выходу второго инвертора, вход которого подключен ко второму входу устройства, вход загрузки данных третьего сдвигового регистра подключен к выходу третьего элемента задержки, вход которого подключен ко второму входу устройства, синхровход третьего сдвигового регистра подключен к синхровходу устройства, первый выход блока коэффициентов матрицы подключен к первому входу третьего коммутатора, второй и третий входы которого подключены ко второму входу устройства, выход третьего коммутатора подключен к информационному входу двухступенчатого триггера, сихровход двухступенчатого триггера подключен к синхровходу устройства, выход двухступенчатого триггера подключен ко второму входу первого элемента ИЛИ, вход которого подключен к выходу третьего элемента И, первый вход которого подключен ко второму выходу блока коэффициентов матрицы, а второй вход – к третьему выходу блока коэффициентов матрицы, выход первого элемента ИЛИ подключен к четвертому входу третьего коммутатора, выход двухступенчатого триггера подключен ко второму входу четвертого элемента И, первый вход которого подключен к синхровходу, выход четвертого элемента И подключен к первому входу третьего элемента ИЛИ, первый вход которого подключен ко входу сброса устройства, выход третьего элемента ИЛИ подключен к десятому входу блока коэффициентов матрицы, выход двухступенчатого триггера подключен к первому входу второго элемента ИЛИ, второй вход которого подключен к выходу третьего сдвигового регистра, выход второго элемента ИЛИ подключен к первому входу первого элемента И, первый выход блока коэффициентов матрицы подключен к выходу устройства.