УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ДВУМЕРНОГО ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ Российский патент 1996 года по МПК G06F17/14 

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

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

В основу работы устройства [1] положена параллельно-последовательная организация вычислений.

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

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

Поставленная задача достигается тем, что в устройство, содержащее с первого по t-й блоки обработки 1 (где t порядок входной матрицы) и первый блок ввода 2, причем вход импульсов 24 подключен к тактовым входам блоков обработки с первого по t-й и первого блока ввода 2, информационные входы первой группы 15 устройства подключены к информационным входам первой группы первого блока обработки, информационные входы второй группы 14 устройства подключены к информационным входам первой группы первого блока ввода, первый и второй управляющие входы 19 и 20 устройства подключены соответственно к первому и второму управляющим входам первого блока обработки, выходы первой группы, первый и второй выходы i-го блока обработки (где i 1,t-1) подключены соответственно к информационным входам первой группы, первому и второму управляющим входам (i+1)-го блока обработки, введены с (t+1)-го по L-й блоки обработки 1, где L t + R, R число резервных блоков обработки, второй блок ввода 3, L комбинационных сумматоров 4, (L-1) регистров 5, триггер 6, группа из L узлов сравнения 7, узел сравнения 8, L групп элементов И 9, L групп элементов ИЛИ 10 и 11, элемент ИЛИ-НЕ 12 и элемент ИЛИ 13, причем тактовый вход 24 устройства подключен к тактовым входам блоков обработки с (t+1)-го по L-й, входам записи/считывания регистров, тактовым входам триггеров 6 и второго блока ввода 3, выходы первой группы, первый и второй выходы j-го блока обработки (где j t, L-1) подключены соответственно к информационным входам первой группы, первому и второму управляющим входам (j+1)-го блока обработки, выходы первого блока ввода 2 подключены ко входам первой группы узла сравнения 8, инверсный выход которого подключен к информационному входу триггера 6, выход которого подключен к первому входу элемента ИЛИ 13, выход которого подключен к выходу признака отказа устройства 30, выходы второго блока ввода 3 подключены ко входам второй группы узла сравнения 8 и информационным входам второй группы первого блока обработки, третий управляющий вход 21 и управляющие входы первой группы 22 устройства подключены соответственно к третьему управляющему входу и управляющим входам первой группы первого блока обработки, управляющие входы второй группы 23 устройства подключены к управляющим входам вторых групп блоков обработки с первого по L-й и входам первых групп узлов сравнения 7 группы, выходы второй группы k-го блока обработки (где k 1, L-1) подключены соответственно к первым входам элементов И 9 k-й группы и информационным входам второй группы (k+1)-го блока обработки, выходы второй группы L-го блока обработки подключены соответственно к первым входам элементов И 9 L-й группы, третий выход k-го блока обработки подключен к третьему управляющему входу (k+1)-го блока обработки, выходы третьей группы k-го блока обработки подключены соответственно к первым входам элементов ИЛИ 10 k-й группы, выходы которых подключены соответственно к управляющим входам первой группы (k+1)-го блока обработки, четвертый выход l-го блока обработки подключен к информационному входу l-комбинационного сумматора 4 и l-му выходу 29 группы признака отказа устройства, выходы четвертой группы l-го блока обработки подключены соответственно к информационным входам группы l-го комбинационного сумматора 4, выходы k-го комбинационного сумматора подключены к информационным входам k-го регистра 5 и входам второй группы k-го узла сравнения 7 группы, выходы L-го комбинационного сумматора 4 подключены ко входам второй группы L-го узла сравнения 7 группы, выходы k-го регистра 5 подключены соответственно ко вторым входам элементов ИЛИ 10 k-й группы, выход l-го узла сравнения 7 группы подключен ко вторым входам элементов И 9 l-й группы и l-му входу элемента ИЛИ-НЕ 12, выход которого подключен ко второму входу элемента ИЛИ 13, выходы элементов И 9 групп с первой по L-ю подключены к соответствующим входам элементов ИЛИ 11 L-й группы, выходы которых подключены соответственно к выходам 31 результата устройства, информационные входы второй группы 14 которого подключены соответственно к информационным входам первой группы второго блока ввода 3, информационные входы третьей группы 16 устройства подключены к информационным входам вторых групп первого и второго блоков ввода, четвертый и пятый управляющие входы 17 устройства подключены соответственно к первым и вторым входам первого и второго блоков ввода, шестой и седьмой управляющие входы 18 устройства подключены соответственно к третьим и четвертым входам первого и второго блоков ввода, l-й вход установки 25 первой группы устройства подключен к первому входу установки l-го блока обработки, l-й вход установки 26 второй группы устройства подключен ко второму входу установки l-го блока обработки, l-й вход установки 28 третьей группы устройства подключен к третьему входу установки l-го блока обработки, l-й вход блокировки 27 устройства подключен ко входу блокировки l-го блока обработки. Каждый блок обработки 1 содержит первый и второй вычислительные узлы 49 и 50, узел сравнения 51, триггер 52, с первого по третий узлы элементов И 53 55, узел элементов ИЛИ 56 и элемент И 57, причем в каждом блоке обработки информационные входы первой и второй групп 58 и 59, первый, второй и третий управляющие входы 60 62 и управляющие входы группы 63 подключены соответственно ко входам группы первого узла элементов И 53 и входам группы второго узла элементов И 54, выходы первой группы первого узла элементов И 53 подключены соответственно ко входам первой группы узла элементов ИЛИ 56, выходы которого подключены соответственно к выходам первой группы 73, второй группы 74, первому 75, второму 76 и третьему 77 выходам блока обработки, выходы первой группы второго узла элементов И 54 подключены соответственно к информационным входам первой и второй групп, первым, вторым и третьим управляющим входам первого и второго вычислительных узлов 49 и 50, выходы первой и второй групп, первый, второй и третий выходы первого вычислительного узла 49 подключены соответственно ко входам группы третьего узла элементов И 55 и входам первой группы узла сравнения 51, выход которого подключен к информационному входу триггера 52, выход которого подключен к информационному входу первого узла элементов И 53, входу второго узла элементов И 54, четвертому выходу 71 блока обработки и входу третьего узла элементов И 55, выходы которого подключены соответственно ко входам второй группы узла элементов ИЛИ 56, выходы первой и второй групп, первый, второй и третий выходы второго вычислительного узла 50 подключены соответственно ко входам второй группы узла сравнения 51, управляющие входы 64 второй группы подключены соответственно к управляющим входам группы первого 49 и второго 50 вычислительных узлов, тактовый вход 69 и вход блокировки 68 блока обработки подключены соответственно к первому и второму (инверсному) входам элемента И 57, выход которого подключен к тактовым входам первого и второго вычислительных узлов и триггера 52, вход установки в нуль и вход установки в единицу которого подключены соответственно к первому 66 и второму 67 установочным входам триггера 52, третий вход установки блока обработки подключен ко входам начальной установки первого и второго вычислительных узлов, выходы вторых групп первого и второго узлов элементов И 53 и 54 подключены соответственно к выходам третьей группы 72 и выходам четвертой группы 70 блока обработки.

Каждый блок ввода 2 (3) содержит первую группу из L регистров 32, вторую группу из L регистров 33, с первой по (L-1)-ю группы элементов И 34, с 1-й по (2L-1)-ю группы элементов И 35, с первого по (L-1)-ю группы элементов ИЛИ 38, с L-й по (2L-1)-ю группы элементов ИЛИ 39, первый и второй элементы И 36 и 37 и 2L-ю группу элементов ИЛИ 40, причем в каждом блоке ввода тактовый вход 47 блока ввода подключен к первым входам первого и второго элементов И 36 и 37, вторые входы которых подключены соответственно к первому и второму управляющим входам 43 и 44 блока ввода, выход первого элемента И 36 подключен ко входам записи/считывания регистров 32 первой группы, выход второго элемента И 37 подключен ко входам записи/считывания регистров 33 второй группы, третий управляющий вход 45 блока ввода подключен к первым входам элементов И 34 групп с первой по (L-1)-ю, четвертый управляющий вход 46 блока ввода подключен к первым входам элементов И 35 групп с L-й по (2L-1)-ю, k-й информационный вход 41 первой группы (где k 1, L-1) блока ввода подключен к первым входам элементов ИЛИ 38 k-й группы, L-й информационный вход 41 первой группы блока ввода подключен к информационному входу L-го регистра 32 первой группы, k-й информационный вход 42 второй группы блока ввода подключен к первым входам элементов ИЛИ 39 (L-1+k)-й группы, L-й информационный вход 42 второй группы блока ввода подключен к информационному входу L-го регистра 33 второй группы, выходы первых регистров первой и второй групп 32 и 33 подключены соответственно к первым и вторым входам элементов ИЛИ 40 2L-й группы, выходы которых подключены соответственно к выходам 48 блока ввода, информационные входы k-го регистра 32 первой группы подключены соответственно к выходам элементов ИЛИ 38 k-й группы, входы второй группы которых подключены соответственно к выходам элементов И 34 k-й группы, входы второй группы которых подключены соответственно к выходам (k+1)-го регистра 32 первой группы, информационные входы k-го регистра 33 второй группы подключены соответственно к выходам элементов ИЛИ 39 (L-1+k)-й группы, входы второй группы которых подключены соответственно к выходам элементов И 35 (L-1+k)-й группы, входы второй группы которых подключены соответственно к выходам (k+1)-го регистра 33 первой группы.

Каждый вычислительный узел 49 (50) содержит три регистра 78 80, первую и вторую группы регистров 80 и 81, комбинационный умножитель 83, комбинационный сумматор 84, 2L+15 групп элементов И 85 102, восемь групп элементов ИЛИ 103 110, восемь элементов И 111 118, двенадцать элементов ИЛИ 119 130, элемент ИЛИ-НЕ 131, девять триггеров 132 140 и дешифратор 141, причем информационные входы 143 первой группы вычислительного узла подключены соответственно к информационным входам первого регистра 78, второго регистра 80 и первым входам элементов И 90 первой группы, выходы которых подключены соответственно к первым входам элементов ИЛИ 105 первой группы, выходы которых подключены соответственно к информационным входам первого регистра 82₁ первой группы, информационные входы второй группы 142 вычислительного узла подключены соответственно к первым входам элементов И 85 второй группы, выходы которых подключены соответственно к первым входам элементов ИЛИ 103 второй группы, выходы которых подключены соответственно к информационным входам первого регистра 81₁ второй группы, выходы которого подключены к первым входам элементов И 87 третьей группы, первым входам элементов И 88 четвертой группы и информационным входам второго регистра 82₂ второй группы, выходы первого регистра 78 подключены к информационным входам третьего регистра 79, первым входам элементов И 91 шестой группы, выходы которых подключены соответственно к первым входам элементов ИЛИ 107 третьей группы, выходы которых подключены ко входам первой группы комбинационного умножителя 83, выходы которого подключены ко входам первой группы комбинационного сумматора 84, выходы которого подключены к первым входам элементов И седьмой 94 и восьмой 97 групп, выходы элементов И восьмой группы 97 подключены соответственно ко вторым входам элементов ИЛИ 105 первой группы, выходы второго регистра 80 подключены к первым входам элементов И девятой 95 и десятой 96 групп, выходы которых подключены соответственно к третьим входам элементов ИЛИ 105 первой группы и первым входам элементов ИЛИ 106 четвертой группы, выходы которых подключены соответственно ко входам второй группы комбинационного сумматора 84, выходы третьего регистра 79 подключены соответственно к первым входам элементов И 93 одиннадцатой группы, выходы которых подключены соответственно к первым входам элементов ИЛИ 104 пятой группы, выходы которых подключены соответственно к выходам 151 первой группы вычислительного узла, выходы элементов ИЛИ 109 шестой группы подключены к первым входам элементов И двенадцатой группы 89 и тринадцатой группы 86, выходы которых подключены соответственно к первым входам элементов ИЛИ 108 седьмой группы и вторым входам элементов ИЛИ 103 второй группы, выходы элементов ИЛИ 110 восьмой группы подключены к первым входам элементов И четырнадцатой группы 98, пятнадцатой группы 99 и шестнадцатой группы 100, выходы которых подключены соответственно к третьим входам элементов И 105 первой группы, вторым входам элементов ИЛИ 106 четвертой группы, вторым входам элементов ИЛИ 107 третьей группы, выходы элементов ИЛИ 108 седьмой группы подключены соответственно ко входам второй группы комбинационного умножителя 83, выходы k-го регистра 102 первой группы (где k 1, L-1) подключены соответственно к информационным входам (k+1)-го регистра 102 первой группы и первым входам элементов И 102 (16+k)-й группы, выходы L-го регистра первой группы подключены соответственно к первым входам элементов И 102 (16+L)-й группы, выходы элементов И 102 групп с семнадцатой по (16+L)-ю подключены к соответствующим входам элементов ИЛИ 110 восьмой группы, выходы n-го регистра 81 (где n 2, L-1) второй группы подключены к информационным входам (n+1)-го регистра 81 второй группы и первым входам элементов И 101 (15+L+n)-й группы, выходы L-го регистра 81 второй группы подключены к первым входам элементов И 101 (2L+15)-й группы, выходы элементов И 101 с (L+17)-й по (2L+15)-ю группы подключены к соответствующим входам элементов ИЛИ 109 шестой группы, выходы элементов И 88 четвертой группы подключены соответственно к выходам 150 второй группы вычислительного узла, первый управляющий вход 144 которого подключен к первым (инверсным) входам первого и второго элементов И 113 и 114, первым входам элементов И с третьего по шестой 115 118 и информационному входу первого триггера 138, выход которого подключен к первому выходу вычислительного узла, второй управляющий вход 145 которого подключен ко вторым (инверсным) входам первого, третьего, четвертого элементов И 113, 115 и 116, вторым входам второго, пятого, шестого элементов И 114, 117 и 118 и информационному входу второго триггера 139, выход которого подключен ко второму выходу 153 вычислительного узла, третий управляющий вход 146 которого подключен к третьим (инверсным) входам второго, третьего, пятого элементов И 114, 115 и 117, третьим входам первого, четвертого и шестого элементов И 113, 116 и 118 и информационному входу третьего триггера 140, выход которого подключен к третьему выходу 154 вычислительного узла, управляющие входы группы 147 подключены соответственно ко входам дешифратора 141, выход первого элемента И 113 подключен к информационному входу четвертого триггера 132, первому входу первого элемента ИЛИ 119 и первому входу второго элемента ИЛИ 120, выход второго элемента И 114 подключен к информационному входу пятого триггера 133, второму входу первого элемента ИЛИ 119, второму входу второго элемента ИЛИ 120, вторым входам элементов И 90 первой группы и первому входу третьего элемента ИЛИ 121, выход которого подключен к первому входу седьмого элемента И 112, выход которого подключен ко входу записи/считывания второго регистра 80, выход третьего элемента И подключен к информационному входу шестого триггера 134, первому входу четвертого элемента ИЛИ 122, первому входу пятого элемента ИЛИ 123, третьему входу второго элемента ИЛИ 120 и второму входу третьего элемента ИЛИ 121, выход четвертого элемента И 116 подключен к информационному входу седьмого триггера 135, второму входу четвертого элемента ИЛИ 122, четвертому входу второго элемента ИЛИ 120, второму входу пятого элемента ИЛИ 123, вторым входам элементов И 95 девятой группы, выходы которых подключены к четвертым входам элементов ИЛИ 105 первой группы, выходы пятого элемента И 117 подключены к информационному входу восьмого триггера 136, третьему входу первого элемента ИЛИ 119, пятому входу второго элемента ИЛИ 120 и первому входу шестого элемента ИЛИ 124, выход которого подключен ко вторым входам элементов И 98 четырнадцатой группы, выход шестого элемента И 118 подключен к информационному входу девятого триггера 137 и второму входу шестого элемента ИЛИ 124, выход первого элемента ИЛИ 119 подключен ко вторым входам элементов И 85 второй группы, выход четвертого элемента ИЛИ 122 подключен ко вторым входам элементов И 86 тринадцатой группы, выход второго элемента ИЛИ 120 подключен к первому входу восьмого элемента ИЛИ 111, выход которого подключен ко входу записи/считывания первого регистра 81₁ второй группы, выход пятого элемента ИЛИ 123 подключен ко вторым входам элементов И 97 восьмой группы, выход четвертого триггера 132 подключен к первому входу седьмого элемента ИЛИ 125, выход пятого триггера 133 подключен ко второму входу седьмого элемента ИЛИ 125 и вторым входам элементов И 96 десятой группы, выход шестого триггера 134 подключен к первому входу восьмого элемента ИЛИ 126, вторым входам элементов И 91 пятой группы и первому входу девятого элемента ИЛИ 127, выход которого подключен ко вторым входам элементов И 100 шестнадцатой группы, выход седьмого триггера 135 подключен ко второму входу восьмого элемента ИЛИ 126 и второму входу девятого элемента ИЛИ 127. Выход восьмого триггера 136 подключен к первому входу девятого элемента ИЛИ 130, третьему входу седьмого элемента ИЛИ 125, первому входу элемента ИЛИ-НЕ 131, первому входу десятого элемента ИЛИ 129, первому входу одиннадцатого элемента ИЛИ 128 и вторым входам элементов И 92 шестой группы, выход девятого триггера 137 подключен ко второму входу девятого элемента ИЛИ 130, второму входу элемента ИЛИ-НЕ 131, второму входу девятого элемента ИЛИ 129, второму входу одиннадцатого элемента ИЛИ 128 и третьим входам элементов И 92 шестой группы, выход девятого элемента ИЛИ 130 подключен ко вторым входам элементов И 87 третьей группы, выходы которых подключены соответственно ко вторым входам элементов ИЛИ 108 седьмой группы, выходы седьмого и восьмого элементов ИЛИ 125 и 126 подключены соответственно ко вторым входам элементов И 88 четвертой группы и элементов И 89 двенадцатой группы, выход десятого элемента ИЛИ 129 подключен ко вторым входам элементов И 94 седьмой группы, выходы которых подключены соответственно ко вторым входам элементов ИЛИ 104 пятой группы, выходы элементов И 91 пятой группы подключены соответственно к третьим входам элементов ИЛИ 106 четвертой группы, выход одиннадцатого элемента ИЛИ 128 подключен ко вторым входам элементов И 99 пятнадцатой группы, выход элемента ИЛИ-НЕ 131 подключен ко вторым входам элементов И 93 одиннадцатой группы, l-й выход дешифратора 141 подключен ко вторым входам элементов И 102 (16+l)-й группы и элементов И 101 (L+l+15)-й группы, вход 149 установки в исходное состояние вычислительного узла подключен ко входам установки в нуль всех регистров и триггеров, тактовый вход 148 вычислительного узла подключен ко входам записи/считывания первого, третьего регистров, всех регистров первой группы, регистров со второго по L-й второй группы, входам синхронизации всех триггеров и вторым входам седьмого и восьмого элементов И.

На фиг. 1 представлена структурная схема устройства, на фиг. 2 - структурная схема блока ввода, на фиг. 3 структурная схема блока обработки, на фиг. 4 структурная схема вычислительного узла.

Устройство содержит L блоков обработки 1, где L P + R, P размерность входной матрицы Х (P, Q), R число резервных блоков обработки, блоки ввода 2 и 3, L комбинационных сумматоров 4, (L-1) регистр 5, триггер 6, (L+1) узел сравнения 7₁,7_L, 8, L групп элементов И 9, L групп элементов ИЛИ 10₁,10_L-1, 11, элемент ИЛИ-НЕ 13, информационные входы 14 - 16, управляющие входы 17 23, тактовый вход 24, входы установки 25 27, входы блокировки 28, группу входов 29 признака отказа, выход 30 признака отказа и выход 31 результата устройства. Каждый блок ввода 2 (3) содержит регистры 32 и 33, группы элементов И 34 37, группы элементов ИЛИ 38 40, информационные входы 41 и 42, управляющие входы 43 46, тактовый вход 47 и выходы 48. Каждый блок обработки 1 содержит вычислительные узлы 49 и 50, узел сравнения 51, триггер 52, узлы элементов И 53 55, узел элементов ИЛИ 56, элемент И 57, информационные входы 58 и 59, управляющие входы 60 64, входы установки 65 67, вход блокировки 68, тактовый вход 69 и выходы 70 77. Каждый вычислительный узел 53 (54) содержит регистры 78 82, комбинационный умножитель 83, комбинационный сумматор 84, группы элементов И 85 102, группы элементов ИЛИ 103 110, элементы 111 118, элементы ИЛИ 119 130, элемент ИЛИ-НЕ 131, триггеры 132 140, дешифратор 141, информационные входы 142 и 143, управляющие входы 144 147, тактовый вход 148, вход установки в исходное состояние 149 и выходы 150 154.

В основу работы устройства для вычисления двумерного ДПФ по формулам:
, где



положены следующие рекуррентные соотношения:
b(j, p, 0) x_p,Q-1,
b(j,P,q)=b(j,P,q-1)ωjτ

+x_P,Q-1-q,
b_jp b(j, p, Q-1),
y(i, j, -1) 0,
y(i,j,P)=y(i,j,P-1)ωiI+b_j,P-1-p,
Y_ij Y(i, j, P-1).

Вычислительный узел 49 (50) обладает возможностью реализации следующих функций:
Aⁱ⁺¹ aⁱ,
Bⁱ⁺¹ bⁱ,
Cⁱ⁺¹ cⁱ,
где аⁱ, bⁱ и cⁱ значения управляющих сигналов соответственно на первом, втором и третьем входах вычислительного узла на i-м такте, Aⁱ, Bⁱ и Cⁱ значения управляющих сигналов соответственно на первом, втором и третьем тактовых выходах вычислительного узла на (i+1)-м такте.

Wⁱ⁺¹=ωⁱ, если
μi1

∨ μi2 = 1
αi1 ∨ αi2 ∨ αi5 = 1
где ωⁱ значение на первом информационном выходе вычислительного узла на i-м такте,
Wⁱ⁺¹ значение на первом информационном выходе вычислительного узла на (i+1)-м такте,

где х^i-1 значение на втором информационном входе вычислительного узла на (i-1)-м такте,
xⁱ⁺¹ значение на втором информационном выходе вычислительного узла на (i+1)-м такте,
Yⁱ dⁱ•eⁱ•+fⁱ,


Z^i-τ-1=x^i-τ-2, если μi-τ-22 ∨ μi-τ-23/ =1;


где


Каждый вычислительный узел 49 (50) работает в шести режимах, которые задаются комбинацией сигналов аⁱ, bⁱ и сⁱ, подаваемых на входы соответственно 144, 145 и 146 на i-м такте.

Первый режим работы вычислительного узла задается комбинацией τi1

(aⁱ, bⁱ, cⁱ) (0, 0, 1). При этом на выходе элемента И 113 формируется сигнал μ₁, а на выходе триггера 132 сигнал αi1 (по сигналу μi1 обеспечивается запись в регистры на i-м такте, а по сигналу αⁱ на (i+1)-такте). Сигнал m₁ подается на соответствующие входы элементов И 95 и на соответствующие входы элементов ИЛИ 119 и 120 (открываются элементы И 85, 93, 95 и 111). На входы 142 подается элемент ωⁱ, и через элементы И 85 и ИЛИ 103 его значение записывается в регистр 81₁ на i-м такте. Информация из регистра 81_j переписывается в регистр 81_j+1. Сигнал α₁ подается на соответствующий вход элемента ИЛИ 125 (открываются элементы И 88 и 93). Содержимое регистра 81₁ через элементы И 91 выдается на выход 142 вычислительного узла. Входной элемент х, подаваемый на вход 143, записывается в регистр 78₁. Содержимое регистра 80 через элементы И 95 и ИЛИ 105 записывается в регистр 82₁. Содержимое регистра 82j записывается в регистр 82_j+1. Содержимое регистра 79 через элементы И 93 и ИЛИ 104 выдается на выход 151.

Во втором режиме работы τi2

(0, 1, 0). При этом на выходе элемента И 114 формируется сигнал μ₂, а на выходе триггера 133 сигнал α₂. Сигнал μ₂ подается на соответствующие входы элементов И 90, на соответствующие входы элементов ИЛИ 119, 120 и 121, а сигнал α_2/ на соответствующий вход элемента ИЛИ 125. В результате этого открываются элементы И 85, 88, 93, 111 и 112. Как и в первом режиме, аналогично, элемент ω записывается в регистр 81₁, содержимое регистра 81₁ выдается на выход 150 и информация записывается в регистры 81_j. Входной элемент х записывается в регистр 82₂ через элементы И 90 и ИЛИ 105, а также записывается в регистр 78. Содержимое регистра 79 выдается на выход 151. Информация из регистра 82_j записывается в регистр 82_j+1.

В третьем режиме τi3

(1, 0, 0). При этом сигнал μ₃ формируется на выходе элемента И 116, а сигнал α₃ на выходе триггера 134. Сигнал μ₃ подается на соответствующие входы элементов ИЛИ 120, 121, 122 и 123, а сигнал α₃ на соответствующие входы элементов И 91 и элементов ИЛИ 126, 127. Открываются элементы И 86, 89, 91, 93, 97, 100 и элементы И 111, 112. Содержимое регистра 81_τ через элементы И 86 и ИЛИ 103 записывается в регистр 81₁. Содержимое регистра 81_j записывается в регистр 81_j+1. Входной элемент х записывается в регистры 78 и 80 (по сигналу m₃ открыт элемент И 112 и разрешается запись в регистр 80). На вход 151 выдается содержимое регистра 79. Содержимое сумматора 84 через элементы И 97 и ИЛИ 105 записывается в регистр 82₁ по сигналу μ₃. Содержимое регистра 82_τ<b> через элементы И 100 и ИЛИ 107 подается на соответствующие входы умножителя 83, на другие входы которого поступает содержимое регистра 81_τ<ω> через элементы И 89 и ИЛИ 108. На выходе умножителя 83 формируется значение b•ω. На одни входы сумматора 84 подается содержимое регистра 78₁ <x> через элементы И 91 и ИЛИ 106, а на другие входы значение b•ω. На выходе сумматора 84 формируется значение (b•ω+x) по сигналу α₃.

В четвертом режиме работы τi4

(1, 0, 1). На выходе элемента И 116 формируется сигнал μ₄, на выходе триггера 135 сигнал α₄. Сигнал μ₄ подается на соответствующие входы элементов ИЛИ 120, 122 и 123, а сигнал α₄ на входы элементов ИЛИ 126, 127 и элементов И 96. Открываются элементы И 86, 89, 93, 96, 97, 100 и 111. Аналогично, как и в третьем режиме, информация в регистрах 81_j циклически переписывается. На выходы 151 выдается содержимое регистра 79 через элементы И 93 и ИЛИ 104. В регистр 78 записывается входной элемент х. В регистр 82₁ записывается информация с выхода сумматора 84 через элементы И 97 и ИЛИ 105 по сигналу μ₄. Содержимое регистра 82_j записывается в регистр 82_j+1. По сигналу α₄ на выходе умножителя 83 формируется значение b•ω (элемент b подается с регистра 81_τ, а элемент w с регистра 82_τ, на выходе сумматора 84 значение (b•ω+x) (элемент х выдается с регистра 80 через элементы И 96 и ИЛИ 106).

В пятом режиме работы τi5

(1, 1, 0). На выходе элемента И 117 формируется сигнал μ₅, на выходе триггера 136 сигнал α₅. Сигнал μ₅ подается на выходы элементов ИЛИ 119, 120 и 124, а сигнал α₅ на выходы элементов И 92, элементов ИЛИ 119, 124, 125, 128, 129, 130 и элемента ИЛИ-НЕ 131. Открываются элементы И 85, 87, 88, 92, 94, 98, 99 и элемент И 111. Входной элемент ω записывается в регистр 81₁, который выдается через элементы И 88 на выход 150. Содержимое регистра 82_τ записывается в регистр 82₁ через элементы И 98 и ИЛИ 100. Содержимое регистра 82_j записывается в регистр 82_j+1. На одни входы умножителя 83 элемент Y подается с выходов регистра 78 через элементы И 92 и ИЛИ 107, а на другие выходы содержимое регистра 81₁<ω> через элементы И 87 и ИЛИ 108. На выходах умножителя 83 формируется значение y•ω, которое подается на одни выходы сумматора 84, на другие выходы которого подается содержимое регистра 82_τ <b> через элементы И 99 и ИЛИ 100. На выходах сумматора 84 формируется значение (y•ω+b), которое через элементы И 94 и ИЛИ 104 подается на выходы 151.

В шестом режиме работы τi6/

(1, 1, 1). На выходе элемента И 118 формируется сигнал μ₆, на выходе триггера 137 сигнал α₆. Сигнал μ₆ подается на выходы элементов ИЛИ 124, а сигнал α₆ на выходы элементов ИЛИ 129 и 130, элемента ИЛИ-НЕ 131 и элементов И 92. Открываются элементы 87, 92, 94, 98 и 99. Регистр 81₁ сохраняет состояние предыдущего такта, информация в регистрах 82_j циклически переписывается. На одни выходы умножителя 83 подается входной элемент Y с выхода регистра 78 через элементы И 92 и ИЛИ 107, а на другие входы содержимое регистра 81₁ <ω> через элементы И 87 и ИЛИ 108. На выходе умножителя 83 формируется значение y•ω, которое подается на одни выходы сумматора 84, на другие выходы которого подается содержимое регистра 82_τ <b> через элементы И 99 и ИЛИ 106. На выходах сумматора 84 формируется значение y•ω+b, которое подается через элементы И 94 и ИЛИ 104 на выходы 151.

Блок ввода 2 (3) работает следующим образом. При подаче на вход 45 нулевого сигнала γ элементы И 34 закрываются, на одни выходы элементов ИЛИ 38 подаются нулевые значения, на другие входы этих элементов подаются соответствующие коэффициенты ωjτ

, которые записываются в соответствующие регистры 32 при наличии на входе 43 единичного сигнала (элемент И 36 открывается и тактовый импульс подается на синхровходы всех регистров 32). При подаче на вход 45 единичного сигнала g элементы И 34 открываются, на входы 41 подаются нулевые значения, на вход 43 подается соответствующая последовательность единичных сигналов a, с выходов 48 выдаются соответствующие коэффициенты ωjτ.. Аналогичным образом записываются и выдаются на выходы 48 коэффициенты ωiI.

При описании работы устройства в обозначении τrν

индекс r указывает номер режима работы вычислительного узла, а индекс n номер такта работы устройства.

Коэффициенты ωiI

и ωjτ записываются в блоки 2 и 3 ввода при подаче их соответственно на входы 42 и 41 при единичных значениях g и d. Коэффициенты ωjτ выдаются с выходов 48 блока ввода на информационные входы 59 блока обработки I_I при наличии сигнала a 1 в моменты времени , а коэффициенты ωiI выдаются с выходов 48 блока ввода 3 на информационные входы 59 блока обработки I_I при наличии сигнала β 1 в моменты времени . Элементы x_pq подаются на информационные входы 15 устройства в моменты времени .

На управляющие входы 19, 20 и 21 устройства подаются соответствующие сигналы а, b и с, которые задают шесть режимов работы τ_i=(a, b, c) следующим образом:
τ₁=(0, 0, 1), τ₂=(0, 1, 0), τ₃=(1, 0, 0), τ₄=(1, 0, 1), τ₅=(1, 1, 0), τ₆=(1, 1, 1),
Управляющие сигналы подаются в следующей последовательности:

Элементы выходной матрицы y(I, τ) выдаются на выходы 31 в моменты времени

Для I=τ+P=Q=3 состояния регистров, значения на входах и выходах блоков обработки I_I, I₂ и I₃ приведены в таблице 1. В таблице 1 приводятся формируемые значения b(j, P, q) и Y(i, j, P-1) в соответствии с рекуррентными соотношениями вычисления двумерного дискретного преобразования Фурье.

Первый элемент Y_oo выдается на выходы 31 на ((Qτ+2P-2)-м) такте, а последний элемент y_I-1,τ-1 на (Q+I)τ+2P-3-м такте.

В каждом блоке обработки 1 производится дублирование вычислительных операций с помощью вычислительных узлов 49 и 50. Результаты выполнения операций, начинающиеся по заднему фронту тактового импульса, формируются на выходе сумматора 84 по завершении переходных процессов в комбинационных схемах 83 и 84 и выдаются на выходы 151 вычислительных узлов 49 (50), откуда эти результаты поступают соответственно на информационные входы узла сравнения 51. При совпадении информации, поступающей на информационные входы узла 51 из вычислительных узлов 49 и 50, данный блок обработки I_j считается исправным и единица с выхода узла сравнения 51 записывается в триггер 52, который используется для фиксации признака исправности данного блока обработки I_j. С выхода триггера 52 единица поступает на соответствующие входы элементов И 55 и информация с выходов 150 154 вычислительного узла 49 через элементы И 55 и ИЛИ 56 поступает на выходы 73 77 блока обработки 1_j. Единичный сигнал с выхода триггера 52 поступает также на инверсные входы элементов И 53 и блокирует обход данного блока обработки 1_j. В результате этого значение g, поступающее на вход 63 блока 1₁, выдается на выход 70 блока 1_j. Единичное значение выдается также на выход 71 блока 1_j и, соответственно, на выход 29_j признака отказа устройства. Единичный сигнал на выходе 29_j устройства указывает средствам внешнего управления об исправности блока 1_j. При несовпадении информации, поступающей на информационные входы узла сравнения 51 из вычислительных узлов 49 и 50, данный блок обработки I_j считается неисправным и нулевой сигнал с выхода узла сравнения 51 записывается в триггер 52. С выхода триггера 52 нулевой сигнал поступает на соответствующие входы элементов И 55, и выдача информации с выходов 150 154 вычислительного узла 49 блокируется. С выхода триггера 52 нулевой сигнал поступает на соответствующие входы элементов И 54 и на инверсные входы элементов И 53. В результате этого поступление значений ω, x, y, a, b, c в вычислительные узлы 49 и 50 через элементы И 54 блокируется и открывается путь обхода данного блока обработки I_j. В этом случае значения w, y, a, b, c, поступающие из предыдущего блока обработки I_j-1, через элементы И 53 и ИЛИ 56 выдаются соответственно на выходы 150 154 данного блока обработки I_j. Значение g, поступающее на вход 63 блока I_j, выдается на выход 72 блока 1_j. Нулевое значение выдается также на выход 71 блока 1_j и, соответственно, на выход 29_j признака отказа устройства. Нулевой сигнал на выходе 29_j устройства указывает средствам внешнего управления об обнаружении отказа блока 1_j.

Для того, чтобы в определенных ситуациях принудительно вывести блок I_j из состава устройства, используется установочный вход 25_j устройства. В этом случае средствами внешнего управления на входе 25_j устройства формируется единичный сигнал, который через вход 66 блока обработки I_j поступает на вход установки в нуль триггера 52. Для того, чтобы принудительно ввести блок обработки I_j в состав устройства, например, после его принудительного вывода или после фиксирования ложного отказа, используется вход 26_j устройства. В этом случае средствами внешнего управления на входе 26_j устройства формируется единичный сигнал, который через вход 67 блока обработки I_j поступает на вход установки в единицу триггера 52.

При этом работа блока обработки I_j может быть блокирована путем подачи на вход 27_j устройства единичного сигнала. В этом случае единичный сигнал через вход 68 блока I_j поступает на инверсный вход элемента И 57, который блокирует прохождение тактовых импульсов на тактовые входы вычислительных узлов 49 и 50 и триггера 52.

Для установки регистров и триггеров вычислительных узлов 49 и 50 блока I_j в исходное состояние при запусках и перепусках устройства используется вход 28_j устройства. Для установки блока I_j в исходное состояние на вход 28_j устройства подается единичный сигнал, который через вход 65 блока I_j поступает на входы установки в исходное состояние вычислительных узлов 49 и 50. Вход установки в исходное состояние вычислительных узлов 49 и 50 подключен ко входам установки в нулевое состояние всех регистров и триггеров узлов 49 и 50 (на фиг. 4 не показаны). На вход 22 устройства подается нулевое значение величины g. При наличии исправных блоков 1₁, 1_τ с выходов 29₁, 29_τ признака отказа устройства выдаются единичные сигналы, которые поступают на входы соответствующих комбинационных сумматоров 4₁, 4_τ. Значение g, поступающее на вход 63 блока 1_j, где j 1,t, в случае исправности блоков 1₁,1_j-1, равно j 1. В случае исправности блока 1_j данное значение g выдается на выход 70_j блока 1 и поступает на соответствующий вход комбинационного сумматора 2_j, с выхода которого снимается значение g 1, которое записывается в регистр 5_j и поступает на одни входы узла сравнения 7_j, на другие входы которого поступает значение t. Таким образом, на каждом такте в случае исправности блока 1_j с выхода комбинационного сумматора 2_j выдается значение g j.

При совпадении значений g и t с выхода узла сравнения 7_j выдается единичный сигнал, который открывает элементы И 9_τ (при этом все остальные элементы И 9 остаются закрытыми) и результат через элементы И 9_τ и элементы ИЛИ 11 выдается на выходы 31 устройства. В случае отказа блока 1_j происходит обход этого блока, как описано выше. При этом в случае исправности предыдущих блоков 1₁,1_j-1 на вход 63 блока 1_j поступает значение g j 1, которое далее поступает на выход 70 блока 1_j. С выходов 70 и 71 блока 1_j снимаются нулевые значения и, таким образом, с выхода комбинационного сумматора 4_j снимается нулевое значение g. В результате этого с выхода узла сравнения 4_τ снимается нулевое значение, которое закрывает элементы И 9_τ. Если блок 1_τ+1/ исправен, то на вход 63 блока 1_τ+1 поступает значение g=τ-1, с выхода 71 блока 1_τ+1 выдается единичный сигнал и, следовательно, с выхода комбинационного сумматора 4_τ+1 снимается значение g=τ. В результате этого с выхода узла сравнения 7_τ+1 снимается единичный сигнал, который открывает элементы И 9_τ+1 и результат через элементы И 9_τ+1 и элементы ИЛИ 11 выдается на выходы 31 результата устройства. Нулевое значение величины g, формируемой на комбинационном сумматоре 4_j на последующих тактах, поступает на соответствующие входы элементов ИЛИ 10_j и в дальнейшем не влияет на величину g, поступающую на вход 63 блока 1_j+1.

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

При обнаружении S отказов блоков 1 происходит обход отказавших блоков 1, как было описано выше. Пусть k номер последнего отказавшего блока 1 линейки, тогда с выхода 72 блока 1_k будет выдаваться значение g=τ-S, которое поступит на вход 63 блока 1_k+1. Поскольку блок 1_k+1 считается исправным, то с выхода 71 блока 1_k+1 выдается единичный сигнал, с выхода комбинационного сумматора 4_k+1 будет выдано значение, g=τ-S+1 которое поступит на вход 63 блока 1_k+2 и т. д. При попадании значения g на вход 63 исправного блока 1_j на выходе комбинационного сумматора 4_j формируется величина, равная g + 1. При попадании значения g на вход 63 неисправного блока 1_j на выходе комбинационного сумматора 4_j формируется нулевое значение, а значение g с выхода 72 блока 1_j поступает на вход 63 следующего блока 1_j+1 линейки. С выхода комбинационного сумматора 4_τ+S на выход узла сравнения 7_τ+S подается значение g=τ, с выхода узла сравнения 7_τ+S выдается единичный сигнал, который открывает элементы И 9_τ+S, и результат с выхода 74 блока 1_τ+S через элементы И 9_τ+S и ИЛИ 11 поступает на выходы 31 результата. В данном случае на один из выходов элемента ИЛИ-НЕ 12 поступает единичный сигнал и, соответственно, при наличии нулевого сигнала на выходе триггера 6 с выхода 30 признака отказа устройства снимается нулевой сигнал, который свидетельствует об исправности устройства. При R < S на выходах узлов сравнения 7₁. 7_L будут нулевые значения, с выхода элемента ИЛИ-НЕ 12 через элемент ИЛИ 13 на выход 30 признака отказа устройства будет выдано единичное значение, которое свидетельствует об исчерпании резерва и отказа устройства. Таким образом, при накоплении R отказов работоспособность устройства сохраняется и длина линейки исправно функционирующих блоков обработки 1 устройства остается постоянной.

Блоки ввода 2 и 3 также работают в режиме дублирования. При совпадении значений ω, поступающих с выходов 48 блоков ввода 2 и 3 на соответствующие входы узла сравнения 8, с инверсного выхода узла сравнения 8 на информационный вход триггера 6 поступает нулевой сигнал, который записывается в триггер 6. При несовпадении значений w, поступающих с выходов 48 блоков 2 и 3, с инверсного выхода узла сравнения 8 на информационный вход триггера 6 поступает единичный сигнал, который записывается в триггер 6. В этом случае единичный сигнал с выхода триггера 6 через элемент ИЛИ 13 проходит на выход 30 признака отказа устройства. Установка триггера 6 в нулевое состояние производится с помощью подачи сигнала установки в исходное состояние всего устройства (соответствующие цепи и, в частности, цепь установки в нуль триггера 6 на фиг. 1 4 не показаны). Таким образом, при обнаружении (R + 1)-го отказа устройства, либо при обнаружении отказа блока ввода с выхода 30 устройства выдается признак отказа, который далее поступает на средства внешнего управления. При работе устройства незаблокированные резервные блоки 1 автоматически функционируют в режиме контроля дублированием. В этом случае на входы первого резервного блока обработки 1_p, где p≥ τ+1, с выхода рабочей линейки устройства поступают вычислительные значения итерации. В результате обработки этого значения в вычислительных узлах 49 и 50 и последующего сравнения результатов в узле 51 резервных блоков обработки происходит обнуление значений триггеров 52 этих блоков. Дальнейшее использование этих резервных блоков обработки будет происходить с учетом их исправности.

Значение τ подается на выходы 23 устройства и далее через входы 64 блоков 1 и входы 147 вычислительных узлов 49 и 50 на входы дешифраторов 141. С t-го выхода дешифратора 141 единичное значение поступает на соответствующие входы элементов И 101_τ-1 и 102_τ. При этом информация с выходов регистра 81_τ через элементы И 101_τ-1, ИЛИ 109, И 86 и ИЛИ 103 поступает на информационные входы регистра 81₁, информация с выходов регистра 82_τ через элементы И 102_τ, ИЛИ 110, И 98 и ИЛИ 105 поступает на информационные входы регистра 82₁. Таким образом, путем задания конкретного значения t в устройстве реализуются возможности определения двумерного дискретного преобразования Фурье для t≅ L..

Рассмотрим работу устройства для конкретного случая R 1 и I=τ+P=Q=3. Пусть на тринадцатом такте работы устройства обнаружен отказ блока обработки 1₂. В этом случае организация входного и выходного потоков данных, управляющих сигналов, содержимое триггеров, регистров и формируемые значения на выходах блоков обработки 1₁, 1₂, 1₃ и 1₄ (где 1₄ резервный блок обработки), приведены в таблице 2.

На такте t 13 обнаружен отказ блока 1₂, на такте t 14 проведено обнуление блока 1₁, блокировка блока 1₂ (в дальнейшем информация, находящаяся в его узлах, не влияет на дальнейший процесс обработки). На такте t 15 произведены блокировка и обнуление блока 1₃, на такте t 16 произведен перезапуск устройства (на выходы блока 1₁ начата подача соответствующих значений), произведена разблокировка блока 1₃. С такта t 14 производится обход блока 1₂ и включение в работу резервного блока 1₄ путем коммутации соответствующих выходов блока 1₄ и выходов 31 устройства. Длина линейки устройства остается прежней.

Один из возможных алгоритмов восстановления вычислительного процесса после обнаружения отказа блока 1_j предусматривает следующую последовательность действий:
такт i: фиксирование блока 1_j с обнаруженным отказом;
такт i+1: блокировка блока 1_j, чтение информации с блока 1_j+1 в блок 1_j+2, обнуление и блокировка блока 1_j+1, обнуление блоков 1₁, 1_j-1;
такт i+2: чтение информации с блока 1_j+2 в блок 1_j+3, блокировка и обнуление блока 1_j+2;
такт i+3: перезапуск устройства, чтение информации с блока 1_j+3 в блок 1_j+4, блокировка и обнуление блока 1_j+3, разблокировка блока 1_j+1;
такт i+4: чтение информации с блока 1_j+4 в блок 1_j+5, блокировка и обнуление блока 1_j+5, разблокировка блока 1_j+2;
такт i+k: чтение информации с блока 1_j+k в блок 1_j+k+1, блокировка и обнуление блока 1_j+k-2.

Если t_n время (число тактов), требуемое к перезапуску устройства со стороны средств внешнего управления, то время реинициализации линейки составит (j+t_n) тактов.

В силу технологической структуры кристалла ИС состояние исправности или неисправности его различных долей взаимосвязаны. Степень связи между отказами различных долей ИС измеряется коэффициентом корреляции, величина которого тем больше, чем выше уровень и степень интеграции ИС [4] Наличие не менее 16-разрядных комбинационных узлов (умножителя, сумматора, регистров) обуславливает степень интеграции и уровень технологии достаточные для проявления высокой степени корреляции отказов. При контроле дублированием вычислительных узлов необходимо, чтобы отказы этих узлов были независимыми. Для этого нужно, чтобы узлы 49 и 50 блока обработки 1 были реализованы на разных кристаллах ИС. Аналогично, исходя из соображений корреляции отказов внутри кристалла ИС, необходимо, чтобы избыточные (резервные) блоки обработки 1 не размещались на одних кристаллах ИС вместе с рабочим.

Технико-экономический эффект предлагаемого устройства заключается в следующем.

В предлагаемом устройстве осуществляется непрерывный аппаратный контроль на протяжении всего времени работы и блокировка выдачи ошибочной информации при обнаружении отказавшего блока обработки. В устройстве реализован наиболее полный аппаратный контроль, ориентированный на обнаружение всех видов отказов, при этом время контроля сравнимо с тактовым периодом. Далее будем считать, что интенсивность отказов блока ввода существенно меньше интенсивности отказов блока обработки (в соответствии с объемом аппаратуры блока ввода и блока обработки). Достоверность функционирования блока обработки 1 устройства будет определяться [5] как
Dф(t) Pпр(t) + Poo(t),
где Рпр(t) вероятность правильной работы блока обработки 1, Poo(t) - вероятность правильной работы блока обработки 1 и выдача с выхода 71 блока обработки 1 сигнала отказа.

Для предлагаемого систолического устройства
Рпр(t) P2уз

(t)
Poo(t) 2Pуз(t)(1 Pуз(t)),
где Pуз(t) вероятность безотказной работы вычислительного узла 49 (50).

Следовательно, достоверность функционирования устройства (без учета блока ввода) может быть оценена как
D_ф=(2P_уз(t)-P2уз

(t))^τ.
При Pуз(t) 0,99, τ 3, D_ф 0,996;
Pуз(t) 0,99, t 10, D_ф 0,9891;
Pуз(t) 0,999, t 3, D_ф 0,9999997;
Pуз(t) 0,999, t 10, D_ф 0,999989;
Pуз(t) 0,9999 и выше D_ф практически равна 1.

Время восстановления вычислительного процесса (получение достоверного результата на выходах 31 устройства) пропорционально значению m_отк, где m_отк≅ τ, m_отк номер отказавшего блока обработки в линейке устройства. ТТТ11 ТТТ12

Изобретение относится к области вычислительной техники и может быть использовано в специализированных вычислительных системах для вычисления двумерного дискретного преобразования Фурье. Цель изобретения - повышение надежности за счет организации контроля и резервирования и расширение функциональных возможностей при решении задач различных размерностей. Поставленная цель достигается тем, что устройство содержит L блоков обработки, где L=τ+R, τ - размерность входной матрицы, R - число резервных блоков обработки, блоки ввода L комбинационных сумматоров, (L-1) регистр, триггер, (L+1) узел сравнения, L групп элементов И, L групп элементов ИЛИ, элемент ИЛИ-НЕ и элемент ИЛИ. В основу работы устройства положена параллельно-последовательная организация вычислений с аппаратным контролем, обходом и замещением отказавших блоков обработки. 2 з.п. ф-лы, 2 табл., 4 ил.

1. Устройство для вычисления двумерного дискретного преобразования Фурье, содержащее первый блок ввода и τ блоков обработки t порядок входной матрицы), каждый из которых включает первый вычислительный узел, причем вход тактовых импульсов устройства подключен к тактовым входам блоков обработки с первого по t-й и первого блока ввода, информационные входы первой группы устройства подключены к информационным входам первой группы первого блока обработки, информационные входы второй группы устройства подключены к информационным входам первой группы первого блока ввода, первый и второй управляющие входы устройства подключены соответственно к первому и второму управляющим входам первого блока обработки, выходы первой группы, первый и второй выходы i-го блока обработки (где i=1, ..., τ-1) подключены соответственно к информационным входам первой группы, первому и второму управляющим входам (i + 1)-го блока обработки, отличающееся тем, что в него введены с (τ+1)-го блока по L-й блоки обработки, где L=τ+R, R число резервных блоков обработки, второй блок ввода, L комбинационных сумматоров, L 1 регистров, группа из L узлов сравнения, узел сравнения, триггер, L групп элементов И, L групп элементов ИЛИ, элемент ИЛИ НЕ и элемент ИЛИ, причем тактовый вход устройства подключен к тактовым входам блоков обработки с (τ+1)-го по L-й, входам записи/считывания регистра, тактовым входам триггера и второго блока ввода, выходы первой группы, первый и второй выходы j-го блока обработки (где j τ L 1) подключены соответственно к информационным входам первой группы, первому и второму управляющим входам (j + 1)-го блока обработки, выходы первого блока ввода подключены к входам первой группы узла сравнения, инверсный выход которого подключен к информационному входу триггера, выход которого подключен к первому входу элемента ИЛИ, выход которого подключен к выходу признака отказа устройства, выходы второго блока ввода подключены к входам второй группы узла сравнения и информационным входам второй группы первого блока обработки, третий управляющий вход и управляющие входы первой группы устройства подключены соответственно к третьему управляющему входу и управляющим входам первой группы первого блока обработки, управляющие входы второй группы устройства подключены к управляющим входам вторых групп блоков обработки с первого по L-й и входам первых групп узлов сравнения группы, выходы второй группы k-го блока обработки (где k 1,L - 1) подключены соответственно к первым входам элементов И k-й группы и информационным входам второй группы (k + 1)-го блока обработки, выходы второй группы L-го блока обработки подключены соответственно к первым входам элементов И L-й группы, третий выход k-го блока обработки подключен к третьему управляющему входу (k + 1)-го блока обработки, выходы третьей группы k-го блока обработки подключены соответственно к первым входам элементов ИЛИ k-й группы, выходы которых подключены соответственно к управляющим входам первой группы (k + 1)-го блока обработки, четвертый выход 1-го блока обработки подключен к информационному входу 1-го комбинационного сумматора и 1-му выходу группы признака отказа устройства, выходы четвертой группы 1-го блока обработки подключены соответственно к информационным входам группы 1-го комбинационного сумматора, выходы k-го комбинационного сумматора подключены к информационным входам k-го регистра и входам второй группы k-го узла сравнения группы, выходы L-го комбиниционного сумматора подключены к входам второй группы L-го узла сравнения группы, выходы k-го регистра подключены соответственно к вторым входам элементов ИЛИ k-й группы, выход 1-го узла сравнения группы подключен к вторым входам элементов И 1-й группы и 1-му входу элемента ИЛИ НЕ, выход которого подключен к второму входу элемента ИЛИ, выходы элементов И групп с первой по L-ю подключены к соответствующим входам элементов ИЛИ L-й группы, выходы которых подключены соответственно к выходам результата устройства, информационные входы второй группы которого подключены соответственно к информационным входам первой группы второго блока ввода, информационные входы третьей группы устройства подключены к информационным входам вторых групп первого и второго блоков ввода, четвертый и пятый управляющие входы устройства подключены соответственно к первым и вторым входам первого и второго блоков ввода, шестой и седьмой управляющие входы устройства подключены соответственно к третьим и четвертым входам первого и второго блоков ввода, 1-й вход установки первой группы устройства подключен к первому входу установки 1-го блока обработки, 1-й вход установки второй группы устройства подключен к второму входу установки 1-го блока обработки, 1-й вход установки третьей группы устройства подключен к третьему входу установки 1-го блока обработки, 1-й вход блокировки устройства подключен к входу блокировки 1-го блока обработки, причем каждый блок обработки содержит второй вычислительный узел, узел сравнения, триггер, с первого по третий узлы элементов И, узел элементов ИЛИ и элемент И, причем в каждом блоке обработки информационные входы первой и второй групп, первый, второй и третий управляющие входы и управляющие входы группы подключены соответственно к входам группы первого узла элементов И и входам группы второго узла элементов И, выходы первой группы первого узла элементов И подключены соответственно к входам первой группы узла элементов ИЛИ, выходы которого подключены соответственно к выходам первой группы, второй группы, первому, второму и третьему выходам блока обработки, выходы первой группы второго узла элементов И подключены соответственно к информационным входам первой и второй групп, первым, вторым и третьим управляющим входам первого и второго вычислительных узлов, выходы первой и второй групп, первый, второй и третий выходы первого вычислительного узла подключены соответственно к входам группы третьего узла элементов И и входам первой группы узла сравнения, выход которого подключен к информационному входу триггера, выход которого подключен к инверсному входу первого узла элементов И, входу второго узла элементов И, четвертому выходу блока обработки и входу третьего узла элементов И, выходы которого подключены соответственно к входам второй группы узла элементов ИЛИ, выходы первой и второй групп, первый, второй и третий выходы второго вычислительного узла подключены соответственно к входам второй группы узла сравнения, управляющие входы второй группы подключены соответственно к управляющим входам группы первого и второго вычислительных узлов, тактовый вход и выход блокировки блока обработки подключены соответственно к первому и второму (инверсному) входам элемента И, выход которого подключен к тактовым входам первого и второго вычислительных узлов и триггера, вход установки в нуль и вход установки в единицу которого подключены соответственно к первому и второму установочным входам триггера, третий вход установки блока обработки подключен к входам начальной установки первого и второго вычислительных узлов, выходы вторым групп первого и второго узлов элементов И подключены соответственно к выходам третьей группы и выходам четвертой группы блока обработки. 2. Устройство по п.1, отличающееся тем, что каждый блок ввода содержит первую группу из L регистров, с первой по (L 1)-ю группы элементов И, с L-й по (2L 1)-ю группы элементов И, с первой по (L 1)-ю группы элементов ИЛИ, с L-й по (2L 1)-ю группы элементов ИЛИ, первый и второй элементы И и 2L-ю группу элементов ИЛИ, причем в каждом блоке ввода тактовый вход блока ввода подключен к первым входам первого и второго элементов И, вторые входы которых подключены соответственно к первому и второму управляющим входам блока ввода, выход первого элемента И подключен к входам записи/считывания регистров первой группы, выход второго элемента И подключен ко входам записи/считывания регистров второй группы, третий управляющий вход блока ввода подключен к первым входам элементов И групп с первой по (L 1)-ю, четвертый управляющий вход блока ввода подключен к первым входам элементов И групп с L-й по (2L 1)-ю, k-й информационный вход первой группы (где k 1,L 1) блока ввода подключен к первым входам элементов ИЛИ k-й группы, L-й информационный вход первой группы блока ввода подключен к информационному входу L-го регистра первой группы, k-й информационный вход второй группы блока ввода подключен к первым входам элементов ИЛИ (L 1 + k)-й группы, L-й информационный вход второй группы блока ввода подключен к информационному входу L-го регистра второй группы, выходы первых регистров первой и второй групп подключены соответственно к первым и вторым входам элементов ИЛИ 2L-й группы, выходы которых подключены соответственно к выходам блока ввода, информационные входы k-го регистра первой группы подключены соответственно к выходам элементов ИЛИ k-й группы, входы второй группы которых подключены соответственно к выходам элементов И k-й группы, входы второй группы которых подключены соответственно к выходам (k + 1)-го регистра первой группы, информационные входы k-го регистра второй группы подключены соответственно к выходам элементов ИЛИ (L 1 + k)-й группы, входы второй группы которых подключены соответственно к выходам элементов И (L 1 + k)-й группы, входы второй группы которых подключены соответственно к выходам (k + 1)-го регистра первой группы. 3. Устройство по п.1, отличающееся тем, что каждый вычислительный узел содержит три регистра, первую и вторую группы регистров, умножитель, сумматор, (2L + 15) групп элементов И, восемь групп элементов ИЛИ, восемь элементов И, двенадцать элементов ИЛИ, элемент ИЛИ НЕ, девять триггеров и дешифратор, причем информационные входы первой группы вычислительного узла подключены соответственно к информационным входам первого регистра, второго регистра и первым входам элементов И первой группы, выходы которых подключены соответственно к первым входам элементов ИЛИ первой группы, выходы которых подключены соответственно к информационным входам первого регистра первой группы, информационные входы второй группы вычислительного узла подключены соответственно к первым входам элементов И второй группы, выходы которых подключены соответственно к первым входам элементов ИЛИ второй группы, выходы которых подключены соответственно к информационным входам первого регистра второй группы, выходы которого подключены к первым входам элементов И третьей группы, первым входам элементов И четвертой группы и информационным входам второго регистра второй группы, выходы первого регистра подключены к информационным входам третьего регистра, первым входам элементов И пятой группы и первым входам элементов И шестой группы, выходы которых подключены соответственно к первым входам элементов ИЛИ третьей группы, выходы которых подключены к входам первой группы умножителя, выходы которого подключены к входам первой группы сумматора, выходы которого подключены к первым входам элементов И седьмой и восьмой групп, выходы элементов И восьмой группы подключены соответственно к вторым входам элементов ИЛИ первой группы, выходы второго регистра подключены к первым входам элементов И девятой и десятой групп, выходы которых подключены соответственно к третьим входам элементов ИЛИ первой группы и первым входам элементов ИЛИ четвертой группы, выходы которых подключены соответственно к входам второй группы сумматора, выходы третьего регистра подключены соответственно к первым входам элементов И одиннадцатой группы, выходы которых подключены соответственно к первым входам элементов ИЛИ пятой группы, выходы которых подключены соответственно к выходам первой группы вычислительного узла, выходы элементов ИЛИ шестой группы подключены к первым входам элементов И двенадцатой группы и тринадцатой группы, выходы которых подключены соответственно к первым входам элементов ИЛИ седьмой группы и вторым входам элементов ИЛИ второй группы, выходы элементов ИЛИ восьмой группы подключены к первым входам элементов И четырнадцатой группы, пятнадцатой группы и шестнадцатой группы, выходы которых подключены соответственно к третьим входам элементов И первой группы, вторым входам элементов ИЛИ четвертой группы и вторым входам элементов ИЛИ третьей группы, выходы элементов ИЛИ седьмой группы подключены соответственно к входам второй группы умножителя, выходы k-го регистра первой группы (где k 1,L 1) подключены соответственно к информационным входам (k + 1)-го регистра первой группы и первым входам элементов И (16 + k)-й группы, выходы L-го регистра первой группы подключены соответственно к первым входам элементов И (16 + L)-й группы, выходы элементов И групп с семнадцатой по (16 + L)-ю подключены к соответствующим входам элементов ИЛИ восьмой группы, выходы n-го регистра (где n 2,L 1) второй группы подключены к информационным входам (ν+1)-го регистра второй группы и первым входам элементов И (15 + L ν-й группы, выходы L-го регистра второй группы подключены к первым входам элементов И (2L + 15)-й группы, выходы элементов И с (L + 17)-й по (2L + 15)-ю группы подключены к соответствующим входам элементов ИЛИ шестой группы, выходы элементов И четвертой группы подключены соответственно к выходам второй группы вычислительного узла, первый управляющий вход которого подключен к первым (инверсным) входам первого и второго элементов И, первым входам элементов И с третьего по шестой и информационному входу первого триггера, выход которого подключен к первому выходу вычислительного узла, второй управляющий вход которого подключен к вторым (инверсным) входам первого, третьего, четвертого элементов И, вторым входам второго, пятого, шестого элементов И и информационному входу второго триггера, выход которого подключен к второму выходу вычислительного узла, третий управляющий вход которого подключен к третьим (инверсным) входами второго, третьего, пятого элементов И, третьим входам первого, четвертого и шестого элементов И и информационному входу третьего триггера, выход которого подключен к третьему выходу вычислительного узла, управляющие входы группы которого подключены соответственно к входам дешифратора, выход первого элемента И подключен к информационному входу четвертого триггера, первому входу первого элемента ИЛИ и первому входу второго элемента ИЛИ, выход второго элемента И подключен к информационному входу пятого триггера, второму входу первого элемента ИЛИ, второму входу второго элемента ИЛИ, вторым входам элементов И первой группы и первому входу третьего элемента ИЛИ, выход которого подключен к первому входу седьмого элемента И, выход которого подключен к входу записи/считывания второго регистра, выход третьего элемента И подключен к информационному входу шестого триггера, первому входу четвертого элемента ИЛИ, первому входу пятого элемента ИЛИ, третьему входу второго элемента ИЛИ и второму входу третьего элемента ИЛИ, выход четвертого элемента И подключен к информационному входу седьмого триггера, второму входу четвертого элемента ИЛИ, четвертому входу второго элемента ИЛИ, второму входу пятого элемента ИЛИ, вторым входам элементов И девятой группы, выходы которых подключены к четвертым входам элементов ИЛИ первой группы, выход пятого элемента И подключен к информационному входу восьмого триггера, третьему входу первого элемента ИЛИ, пятому входу второго элемента ИЛИ и первому входу шестого элемента ИЛИ, выход которого подключен к вторым входам элементов И четырнадцатой группы, выход шестого элемента И подключен к информационному входу девятого триггера и второму входу шестого элемента ИЛИ, выход первого элемента ИЛИ подключен к вторым входам элементов И второй группы, выход четвертого элемента ИЛИ подключен к вторым входам элементов И тринадцатой группы, выход второго элемента ИЛИ подключен к первому входу восьмого элемента ИЛИ, выход которого подключен к входу записи/считывания первого регистра второй группы, выход пятого элемента ИЛИ подключен к вторым входам элементов И восьмой группы, выход четвертого триггера подключен к первому входу седьмого элемента ИЛИ, выход пятого триггера подключен к второму входу седьмого элемента ИЛИ и вторым входам элементов И десятой группы, выход шестого триггера подключен к первому входу восьмого элемента ИЛИ, вторым входам элементов И пятой группы и первому входу девятого элемента ИЛИ, выход которого подключен к вторым входам элементов И шестнадцатой группы, выход седьмого триггера подключен к второму входу восьмого элемента ИЛИ и второму входу девятого элемента ИЛИ, выход восьмого триггера подключен к первому входу девятого элемента ИЛИ, третьему входу седьмого элемента ИЛИ, первому входу элемента ИЛИ НЕ, первому входу десятого элемента ИЛИ, первому входу одиннадцатого элемента ИЛИ и вторым входам элементов И шестой группы, выход девятого триггера подключен к второму входу девятого элемента ИЛИ, второму входу элемента ИЛИ НЕ, второму входу десятого элемента ИЛИ, второму входу одиннадцатого элемента ИЛИ и третьим входам элементов И шестой группы, выход девятого элемента ИЛИ подключен к вторым входам элементов И третьей группы, выходы которых подключены соответственно к вторым входам элементов ИЛИ седьмой группы, выходы седьмого и восьмого элементов ИЛИ подключены соответственно к вторым входам элементов И четвертой группы и элементов И двенадцатой группы, выход десятого элемента ИЛИ подключен к вторым входам элементов И седьмой группы, выходы которых подключены соответственно к вторым входам элементов ИЛИ пятой группы, выходы элементов И пятой группы подключены соответственно к третьим входам элементов ИЛИ четвертой группы, выход одиннадцатого элемента ИЛИ подключен к вторым входам элементов и пятнадцатой группы, выход элемента ИЛИ НЕ подключен ко вторым входам элементов И одиннадцатой группы, l-й выход дешифратора подключен к вторым входам элементов И (16 + l)-й группы и элементов И (L + l + 15)-й группы, вход установлен в исходное состояние вычислительного узла подключен ко входам установки в нуль всех регистров и триггеров, тактовый вход вычислительного узла подключен к входам записи/считывания первого, третьего регистров, всех регистров первой группы, регистров с второго по L-й второй группы, к входам синхронизации всех триггеров и к вторым входам седьмого и восьмого элементов И.