Устройство для свертки двоичногочисла в вычет по

Устройство для свертки двоичногочисла в вычет по

Иллюстрации

Показать все

Реферат

 

и;= .. y» c.

ИЗОБРЕТЕНИЯ

24И07

Союа Советских

Социалистических

Республик

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

Зависимое от авт. свидетельства М

Кл. 42шг, 5/02

Заявлено ЗО,X1.1967 (Мя 1199551/26-24) с присоединением заявки ЛЪ

Приоритет

Опубликовано 01.1Ч.1969. Бюллетень A% 13

Дата опубликования описания 12.Ч111.1969

МПК G 06f

УДК 681.325,53 (088.8) Комитет по делам изобретений и открытий ори Соеете Министров

СССР

Авторы изобретения

Н. Н. Трофимов и А. И. Долгов

Заявитель

УСТРОЙСТВО ДЛЯ СВЕРТКИ ДВОИЧНОГО

ЧИСЛА В ВЪ|ЧЕТ ПО ПРОИЗВОЛЬНОМУ МОДУЛЮ

Предложение относится к вычислительной технике.

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

В известном устройстве пары объединены по признаку соседства.

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

Обобщенная схема устройства свертки приведена на чертеже.

Устройство содержит матрицы конъюнктивных элементов 1 — 5 соответственно первой— пятой ступеней пирамиды, выходные шины б преобразователя свертки, пары входных шин

7 — 88 матриц первой ступени (горизонтальных и вертикальных), соединенные с выходами триггеров 89 — 70.

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

Пусть пг = 17. Парафазные выходы триггеров разрядов с номерами 0,8, 16,24 (наименьшие неотрицательные вычеты соответствующих весов по модулю 17 равны 1) подают на входы

7 — 10 матриц первой ступени, выходы триггеров разрядов с номерами 1, 9, 17, 25 (вычеты равны 2) — на входы 11, 12, 18, 14 и т. д.

Количество различных результатов на выходе каждой матрицы не может превысить трех, 241107

Например, на выходе матриц, имеющих входы

7, 8, возможны следующие результаты: О, 1, 2 (т. е. 0)(2О+ 0+2s = О 1)(2o+ 0 (2в=О)(2гг+ 1 X (2 =1,1)(2г+1)(2 =2) . Следовательно, все матрицы второй ступени пирамиды должны иметь размерность 3 (3. Так как на входы матриц второй ступени подают выходы тех матриц первой ступени, которые формируют результаты из одинаковой совокупности возможных значений, то количество различных результатов на выходе матрицы 2 будет равно пяти. В частности, для матрицы 2, связанной с матрицами первой ступени, имеющими входы 7 — 10, возбуждение выходов ассоциируется с получением одного из результатов О, 1, 2, 3, 4 за счет комбинирования величин О, 1, 2, подаваемых на ее горизонтальные и вертикальные входы. Лналогично для матрицы 2, связанной с матрицами первой ступени, имеющими входы

11 — 14, могут быть получены значения результатов О, 2, 4, 6, 8. Таким образом, в предложенном устройстве матрицы третьей ступени имеют размерность 5)(5, причем среди них нельзя найти такие, которые формируют результаты из одинаковой совокупности возможных значений. В частности, для матрицы 8, связанной с ранее упомянутыми матрицами второй ступени, возбуждение выходов соответствует получению одного из результатов

О, 1, 2... 12 за счет комбинирования величин

О, 1, 2, 3, 4, подаваемых на ее вертикальные входы, и величин О, 2, 4, 6, 8, подаваемых на горизонтальные входы. Очевидно, что размерность матриц четвертой ступени 13+13, а пятой — 17 (17.

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

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

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

Выходы триггеров разрядов с номерами

О, 8, 16, 24 подключают соответственно к 7 — 10 выходам матриц первой ступени; выходы 4, 12, 20, 28 триггеров — к 11 — 14 входам и т. д.

Каждая из матриц первой ступени пирамиды, как и ранее, имеет размерность 2;(2 и количество выходов, равное трем; матрицы второй ступени имеют размерность 3)(3 и по пять выходных шин, а размерность матриц третьей ступени, как и ранее, 5+5, однако у каждой из них девять выходов. Действительно, совокупность возможных результатов на выходе матрицьг 2, связанной с матрицами первой ступени, имеющими входы 7 — 10, будет О, 1, 2, 3, 4, а на выходе матрицы 2, связанной с матрицами первой ступени, имеющими входы 11 — 14, будет — 4, — 3,— 2, — 1,0. Элементы первой совокупности могут быть получены из элементов второй путем суммирования последних с константой, равной 4. Это является достаточным условием, приводящим к тому, что количество различных результатов на выходе рассматриваемой матрицы 8 будет 9 (а не 18, как при предыдущем способе коммутации): О,+-1,+ 2,+3,+-4. Итак, размерность матриц четвертой ступени оказывается равной 9)(9.

Матрица 5, расположенная в пятой ступени пирамиды, будет иметь размерность 17 ;17.

Предмет изобретения

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

Составитель И. Н. Горелова

Редактор Л. А. Утехина Техред T. П. Курилко Корректор Л. В. IОшина

Заказ 1857,16 Тираж 480 Подписное

Ц. -11 .1111И Комитета по делам изобретешш и открытий при Совете Министров СССР

Москва, Центр, пр. Серова, д. 4

Типография, пр. Сапунова, 2