Главная страница  |  Описание сайта  |  Контакты
УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ МАТРИЦЫ НА ВЕКТОР
УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ МАТРИЦЫ НА ВЕКТОР

УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ МАТРИЦЫ НА ВЕКТОР

Патент Российской Федерации
Суть изобретения: Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных машинах и устройствах обработки сигналов для умножения матрицы на вектор. Цель изобретения - повышение быстродействия устройства. Поставленная цель достигается тем, что устройство содержит n вычислительных модулей и 2 n блоков ввода, причем вычислительный модуль содержит вычислительные блоки четырех типов, которые осуществляют обработку данных на уровне разрядов, а блок ввода содержит элементы задержки, которые осуществляют задержку i-го разряда числа на /i + 1/ тактов. В основу работы устройства положен принцип двухуровневой систолической обработки данных, как на уровне слов, так и на уровне разрядов, что повышает эффективность использования оборудования и быстродействие устройства. 6 з. п. ф-лы, 2 табл. 9 ил.
Поиск по сайту

1. С помощью поисковых систем

   С помощью Google:    

2. Экспресс-поиск по номеру патента


введите номер патента (7 цифр)

3. По номеру патента и году публикации

2000000 ... 2099999   (1994-1997 гг.)

2100000 ... 2199999   (1997-2003 гг.)
Номер патента: 2011222
Класс(ы) патента: G06F15/347
Номер заявки: 5013895/24
Дата подачи заявки: 03.07.1991
Дата публикации: 15.04.1994
Заявитель(и): Якуш В.П.; Тиунчик А.А.; Лиходед Н.А.; Соболевский П.И.
Автор(ы): Якуш В.П.; Тиунчик А.А.; Лиходед Н.А.; Соболевский П.И.
Патентообладатель(и): Якуш Виктор Павлович
Описание изобретения: Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных машинах и устройствах обработки сигналов.
Известно устройство для умножения ленточной матрицы на вектор, содержащее l вычислительных модулей (l - ширина ленты), каждый из которых содержит три регистра, умножитель и сумматор.
Недостатком этого устройства является низкое быстродействие за счет большой длительности тактового импульса, равной времени умножения и сложения двух m-разрядных чисел.
Наиболее близким по технической сущности к предлагаемому изобретению является устройство для умножения ленточной матрицы на вектор, содержащее l вычислительных модулей и l-1 элементов задержки, причем каждый вычислительный модуль содержит три регистра, умножитель и сумматор.
Недостатком такого устройства является низкое быстродействие за счет большой длительности тактового импульса, определяемой временем умножения и сложения двух m-разрядных чисел.
Цель изобретения - повышение быстродействия. Поставленная цель достигается тем, что устройство для умножения матрицы на вектор содержит n вычислительных модулей, где n - размерность матрицы, причем выход 6j-го вычислительного модуля (j= ) подключен к первой группе информационных входов 6(j + 1)-го вычислительного модуля, 1j-й вход первой группы информационных входов устройства (j = ) подключен к информационному входу 4j-го блока ввода первой группы, выход которого подключен ко второй группе информационных входов 6j-го вычислительного модуля, 2j-й вход второй группы информационных входов устройства (j = ) подключен к информационному входу 5j-го блока ввода второй группы, выход которого подключен к третьей группе информационных входов 6j-го вычислительного модуля, выход 6n-го вычислительного модуля подключен к выходу 7 устройства, синхровход 3 которого подключен к синхровходам всех блоков ввода и вычислительных модулей, при этом каждый вычислительный модуль 6 содержит вычислительные блоки первого типа 14ij-е (i = , j = ; i > j), где m - разрядность чисел, представленных в дополнительных кодах, вычислительные блоки второго типа 15im-е (i = ), вычислительные блоки третьего типа 16ij-e (i = , j = ; j > i), вычислительные блоки четвертого типа 17 i, m + 1-e(i = ; q = 2m + log2n - 1, знак обозначает округление в сторону большего целого), причем 8i-й вход первой группы информационных входов (i = ) подключен к первому входу 17i, m + 1-го вычислительного блока четвертого типа, 9i-йвход второй группы информационных входов (i = ) вычислительного модуля 6 подключен к первому информационному входу 14i,1-го вычислительного блока первого типа, первый выход 14i,j-го вычислительного блока первого типа (i = , j = ; i ≥ j) подключен к первому информационному входу 14i+1, j+1-го вычислительного блока первого типа, первый выход 14i,m-1-го вычислительного блока первого типа (i = ) подключен к первому информационному входу 15i +1, m-го вычислительного блока второго типа, 101-й и 111-й входы соответственно третьей и четвертой групп информационных входов вычислительного модуля 6 подключены соответственно ко второму и третьему информационным входам 1411-го вычислительного блока 6, 10j-й и 11j-й входы соответственно третьей и четвертой групп информационных входов (j = ) вычислительного модуля 6 подключены соответственно ко второму и третьему информационным входам 161j-го вычислительного блока третьего типа, второй и третий выходы 14i1-го вычислительного блока первого типа (i = ) подключены соответственно ко второму и третьему информационным входам 14i+1-1-го вычислительного блока первого типа, второй и третий выходы 16ij-го вычислительного блока третьего типа (i = , j = ; j-i ≥ 2) подключены соответственно ко второму и третьему информационным входам 16i+1, j-го вычислительного блока третьего типа, второй и третий выходы 16ij-го вычислительного блока третьего типа (i = , j = ; j-i = 1) подключены соответственно ко второму и третьему информационным входам 14i+1, j-го вычислительного блока первого типа, второй и третий выходы 16m-1, m-го вычислительного блока третьего типа подключены соответственно ко второму и третьему информационным входам 15m,m-го вычислительного блока второго типа, второй и третий выходы 15im-го вычислительного блока второго типа (i = ) подключены соответственно ко второму и третьему информационным входам 15i+1, m-го вычислительного блока второго типа, второй и третий выходы 14ij-го вычислительного блока первого типа (i = , j = ; i-j≥ 0) подключены соответственно ко второму и третьему информационным входам 14i+1,j-го вычислительного блока первого типа, 12i-й вход пятой группы информационных входов i = ) вычислительного модуля 6 подключен к четвертому информационному входу 14i,1-го вычислительного блока первого типа, а 12i-й вход пятой группы информационных входов ( i = ) - ко второму информационному входу 17i, m+1-го вычислительного блока четвертого типа, четвертый выход 14ij-го вычислительного блока первого типа (i = , j = , i-j > 0) подключен к четвертому информационному входу 14i+1, j-го вычислительного блока первого типа, четвертый выход 1411-го вычислительного блока первого типа подключен к первому информационному входу 1612-го вычислительного блока третьего типа, четвертый выход 14ij-го вычислительного блока первого типа (i, j = ; i = j) подключен к первому информационному входу 16i+1, j-го вычислительного блока третьего типа, четвертый выход 14i,m-1-го вычислительного блока первого типа (i = ) подключен к четвертому информационному входу 15i,m-го вычислительного модуля второго типа, первый выход 16ij-го вычислительного блока третьего типа (i = , j = ; j > i) подключен к первому информационному входу 16i,j+1-го вычислительного блока третьего типа, первый выход 16im-го вычислительного блока третьего типа (i = ) подключен ко второму информационному входу 17i,m+1-го вычислительного блока четвертого типа, четвертый информационный вход 15i,m-го вычислительного блока второго типа (i = ) подключен ко второму информационному входу 17i,m+1-го вычислительного блока четвертого типа, третий информационный вход 17i,m+1-го вычислительного блока четвертого типа (i = ) подключен к первому выходу 17i-1,m+1-го вычислительного блока четвертого типа, второй выход 17i,m+1-го вычислительного блока четвертого типа (i = ) подключен к 18i-му выходу четвертой группы выходов вычислительного модуля 6, синхровход которого подключен к синхровходам всех вычислительных блоков, при этом вычислительный блок 14 первого типа содержит первый 19, второй 20, третий 21 и четвертый 22 информационные входы, синхровход 23, триггеры 24-28, элемент сумма по модулю два 29, элементы И30 - 33, элемент ИЛИ 34, первый 35, второй 36, третий 37 и четвертый 38 выходы, причем первый 19, второй 20, третий 21 и четвертый 22 информационные входы подключены соответственно к информационным входам первого 24, второго 25, третьего 26 и четвертого 27 триггеров, выход первого триггера 24 подключен к первому входу первого элемента И30 и к информационному входу пятого 28 триггера, выход которогоподключен к первому выходу 35 вычислительного блока 14, выход первого элемента И30 подключен к первым входам элемента сумма по модулю два 29, первого 31 и второго 32 элементов И, выход второго триггера 25 подключен к первому входу третьего элемента И33 и ко вторым входам элемента сумма по модулю два 29 и второго элемента И31, выход третьего триггера 26 подключен ко второму входу первого элемента И30 и к третьему выходу 37 вычислительного блока 14, выход четвертого триггера 27 подключен к третьему входу элемента сумма по модулю два 29, ко вторым входам третьего 32 и четвертого 33 элементов И, выходы второго 31, третьего 32 и четвертого 33 элементов И подключены соответственно к первому, второму и третьему входам элемента ИЛИ 34, выход которого подключен ко второму выходу 36 вычислительного блока 14, четвертый выход 38 которого подключен к выходу элемента сумма по модулю два 29 синхровход 23 вычислительного блока 14 подключен к синхровходам всех триггеров, при этом вычислительный блок 15 второго типа содержит первый 39, второй 40, третий 41 и четвертый 42 информационные входы, синхровход 43, триггеры 44-47, элемент сумма по модулю два 48, элементы И 49-52, элемент ИЛИ 53, первый 54, второй 55 и третий 56 выходы, причем первый 39, второй 40, третий 41 и четвертый 42 информационные входы вычислительного блока 15 подключены соответственно к информационным входам первого 44, второго 45, третьего 46 и четвертого 47 триггеров, инверсный выход первого триггера 44 подключен к первому входу первого элемента И49, выход которого подключен к первым входам второго 50 и третьего 51 элементов И и элемента сумма по модулю два 48, выход второго триггера 45 подключен к первому входу четвертого элемента И52, выход третьего триггера 46 подключен ко второму входу первого элемента И49 и к третьему выходу 56 вычислительного блока 15, выход четвертого триггера 47 подключен ко вторым входам элемента сумма по модулю два 48 и третьего элемента И51, выходы второго 50, третьего 51 и четвертого 52 элементов И подключены соответственно к первому, второму и третьему входам элемента ИЛИ 53, выход которого подключен ко второму выходу 55 вычислительного блока 15, третий 56 и первый 54 выходы которого подключены соответственно к выходу третьего триггера 46 и элемента сумма по модулю два 48, синхровход 43 вычислительного блока 15 подключен к синхровходам всех триггеров, при этом вычислительный блок 16 третьеготипа содержит первый 57, второй 58 и третий 59 информационные входы, синхровход 60, триггеры 61-63, первый 64, второй 65, и третий 66 выходы, причем первый 57, второй 58 и третий 59 информационные входы вычислительного блока 16 подключены соответственно к информационным входам первого 61, второго 62 и третьего 63 триггеров, выходы которых подключены соответственно к первому 64, второму 65 и третьему 66 выходам вычислительного блока 16, синхровход 60 которого подключен к синхровходам всех триггеров, при этом вычислительный блок четвертого типа 17 содержит первый 67, второй 68 и третий 69 информационные входы, синхровход 70, триггеры 71-73, элемент сумма по модулю два 74, элементы И 75-77, элемент ИЛИ 78, первый 79 и второй 80 выходы, причем первый 67, второй 68 и третий 69 информационные входы подключены соответственно к информационным входам первого 71, второго 72 и третьего 73 триггеров, выход первого 71 триггера подключен к первым входам первого 75 и второго 76 элементов И и элемента сумма по модулю два 74, выход второго триггера подключен к первому входу третьего 77 элемента И и ко вторым входам второго элемента 76 И и элемента сумма по модулю два 74, выход третьего триггера 73 подключен ко вторым входам первого 75 и третьего 77 элементов И и к третьему входу элемента сумма по модулю два 74, выходы первого 75, второго 76 и третьего 77 элементов И подключены соответственно к первому, второму и третьему входам элемента ИЛИ 78, выход которого подключен к первому 79 выходу вычислительного блока 17, второй 80 выход которого подключен к выходу элемента сумма по модулю два 80, синхровход 70 вычислительного блока 17 подключен к синхровходам всех триггеров, при этом блок ввода содержит синхровход 81, информационные входы 82i (i = ) элементы задержки 83i (i = ) и выходы 84i (i = ) причем первый 821 информационный вход подключен к 841-му выходу блока ввода, 82i-й информационный вход (i = ) подключен ко входу 83(i-1)-го элемента задержки на (i-1) тактов, выход которого подключен к 84i-му выходу блока ввода, синхровход 81 которого подключен к синхровходам всех элементов задержки 83. На фиг. 1 представлена структурная схема устройства для умножения матрицы на вектор; на фиг. 2 - структурная схема устройства для умножения матрицы на вектор для m = n = 3; на фиг. 3 - схема вычислительного модуля; на фиг. 4 - схема вычислительного модуля для m = 3; на фиг. 5 - схемавычислительного блока первого типа; на фиг. 6 - схема вычислительного блока второго типа; на фиг. 7 - схема вычислительного блока третьего типа; на фиг. 8 - схема вычислительного блока четвертого типа; на фиг. 9 - схема блока ввода.
Устройство для умножения матрицы на вектор (см. фиг. 1) содержит первую 1 и вторую 2 группу информационных входов, синхровход 3, блоки ввода первой 4 и второй 5 групп, вычислительные модули 6, выход 7.
Вычислительный модуль 6 (см. фиг. 3) содержит первую 8, вторую 9, третью 11, четвертую 10 и пятую 12 группы информационных входов, синхровход 13, вычислительные блоки первого типа 14ij (i = , j = ; i ≥ j), вычислительные блоки второго типа 15im (i = ), вычислительные блоки третьего типа 16ij (i = , j = ; j > i); вычислительные блоки четвертого типа 17i,m+1 (i = ) и выходы 18.
Вычислительный блок 14 первого типа (см. фиг. 5) содержит первый 19, второй 20, третий 21 и четвертый 22 информационные входы, синхровход 23, триггеры 24-28, элемент сумма по модулю два 29, элементы И 30-33, элемент ИЛИ 34, первый 35, второй 36, третий 37 и четвертый 38 выходы.
Вычислительный блок 15 второго типа (см. фиг. 6) содержит первый 39, второй 40, третий 41 и четвертый 42 информационные входы, синхровход 43, триггеры 44-47, элемент сумма по модулю два 48, элементы И 49-52, элемент ИЛИ 53, первый 54, второй 55 и третий 56 выходы.
Вычислительный блок 16 третьего типа (см. фиг. 7) содержит первый 57, второй 58 и третий 59 информационные входы, синхровход 60, триггеры 61-63, первый 64, второй 65 и третий 66 выходы.
Вычислительный блок 17 четвертого типа (см. фиг. 8) содержит первый 67, второй 68 и третий 69 информационные входы, синхровход 70, триггеры 71-73, элемент сумма по модулю два 74, элементы И 75-77, элемент ИЛИ 78, первый 79 и второй 80 выходы.
Блок ввода 4 или 5 (см. фиг. 9) содержит синхровход 81, информационные входы 82i (i = ), элементы задержки 83i (i = ) на i тактов и выходы 84i (i = ).
Вычислительный блок первого типа 14 (см. фиг. 5) обладает возможностью реализации функций
xj+2 = xj,
cj+1 = cjyj V cjajxj V yjajxj,
aj+1 = aj,
yj+1 = cj ⊕ yj ⊕ ajxj, где xj, cj, aj и yj - значения соответственно на первом 19, втором 20, третьем 21 и четвертом 22 информационных входах вычислительного блока 14 на j-м такте, xj+2, cj+1, aj+1 и yj+1 - значения соответственно на первом 35, втором 36, третьем 37 и четвертом 38 выходах вычислительного блока 14 на j+2 (j+1)-м такте.
Вычислительный блок второго типа 15 (см. фиг. 6) обладает возможностью реализации функций
aj+1 = aj,
cj+1 = cjyj V cja V yja,
yj+1 = cj ⊕ yj ⊕ a, где xj, cj, aj и yj - значения соответственно на первом 39, втором 40, третьем 41 и четвертом 42 информационных входах вычислительного блока 15 на j-м такте, yj+1, cj+1 и aj+1 - значения соответственно на первом 54, втором 55 и третьем 56 выходах вычислительного блока 15 на (j+1)-м такте.
Вычислительный блок третьего типа 16 (см. фиг. 7) обладает возможностью реализации функций
yj+1 = yj,
xj+1 = cj,
aj+1 = aj, где yj, cj и aj - значения соответственно на первом 57, втором 58 и третьем 59 информационных входах вычислительного блока 16 на j-м такте, yj+1, cj+1 и aj+1 - значения соответственно на первом 64, втором 65 и третьем 66 выходах вычислительного блока 16 на (j+1)-м такте.
Вычислительный блок четвертого типа 17 (см. фиг. 8) обладает возможностью реализации функций
cj+1 = yjcj V yjgj V gjcj,
yj+1 = yj ⊕ gj ⊕ cj,
где yj, gj и cj - значения соответственно на первом 67, втором 68 и третьем 69 информационных входах вычислительного блока 17 на j-м такте,
yj+1 и cj+1 - значения соответственно на первом 79 и втором 80 выходах вычислительного блока 17 на (j+1)-м такте.
Рассмотрим работу блока ввода (см. фиг. 9).
Входной элемент x подается одновременно всеми разрядами на t-м такте на входы 82. В обозначении x(i)t индекс t указывает номер такта, индекс i в скобах - номер разряда элемента x, индекс без скобок - номер элемента x. Элемент задержки 83i-й задерживает разряды x(i)-e на i тактов, т. е. на 84i-й выход подается i-й разряд элемента x на (t+1)-м такте. С выхода 84 блока ввода элемент xj подается на соответствующий вход 6j-го вычислительного модуля.
Рассмотрим работу вычислительного модуля 6 (см. фиг. 3).
Вычислительный модуль 6 выполняет операцию вида y' = ax+y, где a, x, y, y' - числа, представленные в дополнительном коде. На входы 8i-й (i = ) подается (i-1)-й разряд числа y на (i-1)-м такте. На вход 9i-й (i = ) подается (i-1)-й разряд числа x на (i-1)-м такте. На входы 10j-e (j = ) постоянно подаются нулевые значения, а на вход 10m-й-(m-1)-й разряд числа a на (m-1)-м такте. На вход 11j-й (j = ) подается (j-1)-й разряд числа a на (j-1)-м такте. На входы 12i-e (j = ) постоянно подаются нулевые значения. При этом, в соответствии с выполняемыми функциями вычислительных блоков 14, 15, 16, и 17, на 18i-x (i = ) выходах вычислительного модуля 6 формируется операция y' = ax + y в виде следующих рекуррентных соотношений:
y-1j = 0, j = , q = 2m +log2n - 1;
ci,i-1 = 0, i = ;
cm-1, m-2 = am-1;
xj = xm-1, j ≥ m-1.
i = , j = ;
yij = yi-1, j V ci,j-1 V aixj-i,
cij = yi-1,j cij-1 V yi-1,j aixj-i V ci,j-1 ajxj-i;
j = ;
ym-1,j = ym-2,j ⊕ cm-1, j ⊕ am-1 xj-m+1,
cm-1,j = ym-2,j cm-1,j V ym-2,j am-1 V
V cm-1,j am-1 ;
i = , j = ;
yij = yi,j-1;
i = , j = ;
yij = yi,j-1.
gj = ym-1,j, j = 1.
yj' = gj + yj, j = .
На 18i-м выходе формируется (i-1)-й разряд операции y' = ax + y на (m+i)-м такте. Последний (q-1)-й разряд формируется на (m+q)-м такте. На фиг. 4 для m = 3 приведена организация подачи разрядов чисел a и x соответственно на входах 11 и 9, на выходе 18 - разряды результата y'. Таким образом, на первых выходах вычислительных блоков 16im-x (i = ) и 15im-x (i = ) формируется произведение ax, а на выходах 18i-x - результат y' = ax+y. В табл. 1 приведены значения на входах и выходах при формировании произведения ax, а в табл. 2 - при формировании результата y'.
В основу работы устройства для умножения матрицы A = { aij} , i, j = на вектор x = { x-j} , j = положены рекуррентные соотношения
yi,o = 0, i = ;
yij = yi,j-1 + aij xj, i, j = ;
yi = yi,n, i = .
Элементы xjt и aijt подаются на входы соответственно 4j-го и 5j-го блоков ввода (j = ) с выхода которых данные элементы подаются на соответствующие входы 6j-го вычислительного модуля. Причем блоки вводов 4 и 5 осуществляют задержку i-го разряда элементов x и a на (i-1) тактов, т. е. i-й разряд этих элементов выдается на (t+i-1)-м такте. Длительность тактового импульса tти, подаваемого на синхровход 3, равна
tти = tтр + 2tи + tили, где tтр - время записи в триггер;
tи - задержка элемента И;
tили - задержка элемента ИЛИ.
На выходе 7 устройства i-й разряд элемента yj-го формируется на (m+n+i+j-1)-м такте.
Рассмотрим работу устройства при формировании элемента y1результирующей матрицы Y для случая m = n = 3 (см. фиг. 2). На входы 1jи 2j (j = 1,3) подаются соответственно элементы xj и aij, причем i-e разряды данных элементов подаются на входы вычислительных модулей 6 на (t+i-1)-м такте. На выходе вычислительного модуля 61 формируется младший разряд y1 на m-м такте, а старший разряд y1 - на (m+q-1)-м такте. На выходе вычислительного модуля 62 формируется младший разряд y1 на (m+1)-м такте, а старший разряд y1 - на (m+q)-м такте. На выходе вычислительного модуля 63 формируется младший разряд y1 на (m+n-1)-м такте, а старший разряд y1 - на (m+n+q-2)-м такте, т. е. младший разряд y1 формируется на 5-м такте, а старший разряд y1 - на 12-м такте. Аналогичным образом формируются элементы y2 и y3 (младшие разряды элементов y2 и y3 формируются соответственно на 6-м и 7-м такте, а старшие - на 13-м и 14-м тактах).
Полное время умножения (n x n) - матрицы на вектор равно (m+2n+q-1) тактов.
Таким образом,
предлагаемое устройство обладает более высоким быстродействием по сравнению с прототипом. Прототип реализует умножение (n x n)-матрицы на вектор за (2n-1) тактов, причем длительность тактового импульса равна времени умножения и сложения двух m-разрядных чисел. Например, для m = 32 и длительности тактового импульса 100 нс время умножения матрицы размерностью n = 100 на вектор составляет 20 мкс. Предлагаемое устройство выполняет данную задачу при меньшей длительности тактового импульса tти = tтр + 2tи + tили ≈ 10 нс за 2,94 мкс (выигрыш во времени составляет 7 раз). (56) Kung H. T. Leiseerson C. E. Systohic Arrays (for VLSI)-Sparse Matrix Proc. 1978, Society for Industrial and Applied Mathematicf, 1979, p. 262, fig 3-2.
Авторское свидетельство СССР N 1517039, кл. G 06 F 15/347, 1989.
Формула изобретения: 1. УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ МАТРИЦЫ НА ВЕКТОР, содержащее n вычислительных модулей (где n - размерность квадратной матрицы), причем выход j-го вычислительного модуля (j = 1, . . . , n - 1) соединен с информационными входами первой группы (j + 1)-го вычислительного модуля, выход n-го вычислительного модуля соединен с выходом результата устройства, синхровход которого соединен с синхровходами всех вычислительных модулей, отличающееся тем, что, с целью повышения быстродействия устройства, в него введены две группы по n блоков ввода в каждой, причем i-й информационный вход первой и второй групп устройства соединены соответственно с информационными входами i-х блоков ввода первой и второй групп (i = 1, . . . , n), выходы которых соединены соответственно с информационными входами второй и третьей групп i-го вычислительного модуля, информационные входы четвертой и пятой групп которого соединены с входом логического нуля устройства, синхровход которого соединен с синхровходами всех блоков ввода первой и второй групп.
2. Устройство по п. 1, отличающееся тем, что вычислительный модуль содержит (i, j)-е вычислительные блоки первого типа (i = , j = , i≥ j), где m - разрядность чисел, представленных в дополнительных кодах, (i, m)-е вычислительные блоки второго типа i = , (i, j) -е вычислительные блоки третьего типа (i = , j = , j>1), (i, m +1) -е вычислительные блоки четвертого типа (i = ; q= 2m + log2n - 1, знак обозначает округление в сторону большего целого), причем i-й информационный вход первой группы модуля (i = ) соединен с первым информационным входом (i, m + 1)-го вычислительного блока четвертого типа, i-й информационный вход второй группы модуля (i = ) подключен к первому информационному входу (i, 1)-го вычислительного блока первого типа, первый выход (i, j)-го вычислительного блока первого типа (i = , j = 1, m-2, i≥ j подключен к первому информационному входу (i + 1, j + 1)-го вычислительного блока первого типа, первый выход (i, m - 1)-го вычислительного блока первого типа (i = ) подключен к первому информационному входу (i + 1, m)-го вычислительного блока второго типа, первые информационные входы третьей и четвертой групп модуля подключены соответственно к второму и третьему информационным входам (1, 1)-го вычислительного блока первого типа j-е информационные входы третьей и четвертой групп (j = ) модуля подключены соответственно к первому и второму информационным входам (1, j)-го вычислительного блока третьего типа, первый и второй выходы (i, j)-го вычислительного блока третьего типа (i = , j = , i-j≥ 2) подключены соответственно к первому и второму информационным входам (i + 1, j)-го вычислительного блока третьего типа, первый и второй выходы (i, j)-го вычислительного блока третьего типа (i = , j = 2, , i-j = 1) подключены соответственно к второму и третьему информационным входам (i + 1, j)-го вычислительного блока первого типа, первый и второй выходы (m - 1, m)-го вычислительного блока третьего типа подключены соответственно к второму и третьему информационным входам (m, m)-го вычислительного блока второго типа, первый и второй выходы (i, m)-го вычислительного блока второго типа (i = ) подключены соответственно к второму и третьему информационным входам (i + 1, m)-го вычислительного блока второго типа, второй и третий выходы (i, j)-го вычислительного блока первого типа (i = , j = , i-j≥ 0) подключены соответственно к второму и третьему информационным входам (i + 1, j)-го вычислительного блока первого типа, i-й информационный вход пятой группы (i = ) модуля подключен к четвертому информационному входу (i, 1)-го вычислительного блока первого типа, i-й информационный вход пятой группы модуля (i = ), подключен к второму информационному входу (i, m + 1)-го вычислительного блока четвертого типа, четвертый выход (i, j)-го вычислительного блока первого типа (i = , j = , i-j>0) подключен к четвертому информационному входу (i, j + 1)-го вычислительного блока первого типа, четвертый выход (i, j)-го вычислительного блока первого типа (i, j = , i= j) подключен к третьему информационному входу (i, j + 1)-го вычислительного блока третьего типа, четвертый выход (i, m - 1)-го вычислительного блока первого типа (i= ) подключен к четвертому информационному входу (i, m)-го вычислительного модуля второго типа, третий выход (i, j)-го вычислительного блока третьего типа (i = , j = , j>i) подключен к третьему информационному входу (i, j + 1)-го вычислительного блока третьего типа, третий выход (i, m)-го вычислительного блока третьего типа (i = ) подключен к второму информационному входу (i, m + 1)-го вычислительного блока четвертого типа, третий выход (i, m)-го вычислительного блока второго типа (i = ) подключен к второму вычислительному входу (i, m + 1)-го вычислительного блока четвертого типа, третий информационный вход (i, m + 1)-го вычислительного блока четвертого типа (i = ) подключен к первому выходу (i - 1, m + 1)-го вычислительного блока четвертого типа, третий информационный вход (1, m + 1)-го вычислительного блока четвертого типа соединен с (m + 1)-м информационным входом четвертой группы модуля, второй выход (i, m + 1)-го вычислительного блока четвертого типа (i = ) подключен к i-му выходу группы модуля, синхровход которого подключен к синхровходам всех вычислительных блоков.
3. Устройство по п. 2, отличающееся тем, что вычислительный блок первого типа содержит пять триггеров, сумматор по модулю два, четыре элемента И и элемент ИЛИ, причем первый, второй, третий и четвертый информационные входы блока подключены соответственно к информационным входам первого, второго, третьего и четвертого триггеров, выход первого триггера подключен к первому входу первого элемента И и информационному входу пятого триггера, выход которого подключен к первому выходу блока, выход первого элемента И подключен к первым входам сумматора по модулю два, второго и третьего элементов И, выход третьего триггера подключен к первому входу четвертого элемента И и вторым входам сумматора по модулю два и второго элемента И, выход второго триггера подключен к второму входу первого элемента И и второму выходу блока, выход четвертого триггера подключен к третьему входу сумматора по модулю два и вторым входам третьего и четвертого элементов И, выходы второго, третьего и четвертого элементов И подключены соответственно к первому, второму и третьему входам элемента ИЛИ, выход которого подключен к третьему выходу блока, четвертый выход которого подключен к выходу сумматора по модулю два, синхровход блока подключен к синхровходам всех триггеров.
4. Устройство по п. 2, отличающееся тем, что вычислительный блок второго типа содержит четыре триггера, сумматор по модулю два, четыре элемента И и элемент ИЛИ, причем первый - четвертый информационные входы блока подключены соответственно к информационным входам первого - четвертого триггеров, инверсный выход первого триггера подключен к первому входу первого элемента И, выход которого подключен к первым входам второго и третьего элементов И и сумматора по модулю два, выход третьего триггера подключен к первому входу четвертого элемента И, вторым входам второго элемента И и сумматора по модулю два, выход второго триггера подключен к второму входу первого элемента И и второму выходу блока, выход четвертого триггера подключен к третьему входу сумматора по модулю два и вторым входам третьего и четвертого элементов И, выходы второго, третьего и четвертого элементов И подключены соответственно к первому, второму и третьему входам элемента ИЛИ, выход которого подключен к третьему выходу блока, первый выход которого подключен к выходу сумматора по модулю два, синхровход блока подключен к синхровходам всех триггеров.
5. Устройство по п. 2, отличающееся тем, что вычислительный блок третьего типа содержит три триггера, причем первый, второй и третий информационные входы блока подключены соответственно к информационным входам первого, второго и третьего триггеров, выходы которых подключены соответственно к первому, второму, третьему выходам блока, синхровход которого подключен к синхровходам всех триггеров.
6. Устройство по п. 2, отличающееся тем, что вычислительный блок четвертого типа содержит три триггера, сумматор по модулю два, три элемента И и элемент ИЛИ, причем первый, второй и третий информационные входы блока подключены соответственно к информационным входам первого, второго и третьего триггеров, выход первого триггера подключен к первым входам первого и второго элементов И и сумматора по модулю два, выход второго триггера подключен к первому входу третьего элемента И и к вторым входам второго элемента И и сумматора по модулю два, выход третьего триггера подключен к вторым входам первого и третьего элементов И и третьему входу сумматора по модулю два, выходы первого, второго и третьего элементов И подключены соответственно к первому, второму и третьему входам элемента ИЛИ, выход которого подключен к первому выходу вычислительного блока, второй выход которого подключен к выходу сумматора по модулю два, синхровход блока подключен к синхровходам всех триггеров.
7. Устройство по п. 1, отличающееся тем, что блок ввода содержит i элементов задержки (i = ), где m - разрядность числа), причем первый информационный вход блока подключен к первому выходу блока ввода, j-й информационный вход блока ( j = 2, m) подключен к входу (j - 1)-го элемента задержки, выход которого подключен к j-му выходу блока, синхровход которого подключен к синхровходам всех элементов задержки.