систолический отказоустойчивый процессор дискретного преобразования фурье

Формула изобретения

1. СИСТОЛИЧЕСКИЙ ОТКАЗОУСТОЙЧИВЫЙ ПРОЦЕССОР ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащий первый входной регистр, первую систолическую матрицу преобразования Фурье по первой координате, включающую в себя N - 1 операционных блоков, где N - размер преобразования, первую систолическую матрицу преобразования Фурье по второй координате, включающую в себя N - 1 операционных блоков, первый блок сдвиговых регистров, включающий в себя N каналов, первый сумматор и блок синхронизации, причем первый выход результата и выход коэффициента операционного блока первых систолических матриц преобразования Фурье по первой и второй координатам соединены соответственно с входом (i + 1)-го операционного блока соответственно тех же матриц, отличающийся тем, что в него введены блок преобразования двоичного кода в код системы остаточных классов, первый и второй блоки преобразования кода весовых множителей в код системы остаточных классов, блок переключений, n + 1 входных регистров, где n - число рабочих оснований в системе остаточных классов, n + 1 систолических матриц преобразования Фурье по первой координате, блок обнаружения ошибки, n + 1 систолических матриц преобразования Фурье по второй координате, n + 1 сумматоров, n + 1 блоков сдвиговых регистров и блок преобразования кода системы остаточных классов в двоичный код, причем входы блоков преобразования двоичного кода и кодов весовых множителей в коды системы остаточных классов являются информационными входами процессора, информационный выход которого соединен с выходом преобразователя кода системы остаточных классов в двоичный код, выходы блоков преобразования двоичного кода и кодов весовых множителей в коды системы остаточных классов соединены соответственно с первым, вторым и третьим информационными входами блока переключений, первый выход которого соединен с первыми информационными входами n + 2 систолических матриц преобразования Фурье по первой координате, вторые и третьи информационные входы которых соединены соответственно с первыми и вторыми выходами n + 2 входных регистров, входы которых соединены с вторым выходом блока переключений, третий выход которого соединен с информационным выходом блока обнаружения ошибки, входы которого соединены соответственно с выходами n + 2 систолических матриц преобразования Фурье по первой координате, информационный выход блока обнаружения ошибки соединен с первыми информационными входами n + 2 систолических матриц преобразования Фурье по второй координате и с первыми входами n + 2 сумматоров, выходы которых соединены с первыми информационными входами n + 2 блоков сдвиговых регистров, первые выходы которых соединены соответственно с вторыми входами n + 2 сумматоров, четвертый выход блока переключений соединен с вторыми информационными входами n + 2 систолических матриц преобразования Фурье по второй координате, третьи выходы операционных блоков которых соединены соответственно с второго по N-й входами n + 2 сдвиговых регистров, выходы которых соединены соответственно с третьими входами n + 2 систолических матриц преобразования Фурье по второй координате, тактовые входы систолических матриц преобразования Фурье по первой и второй координатам и n + 2 блоков сдвиговых регистров соединены с тактовым выходом блока синхронизации, первый и второй управляющие выходы которого соединены соответственно с входами управления блока переключений и n + 2 блоков сдвиговых регистров, а управляющий вход блока синхронизации соединен с управляющим выходом блока обнаружения ошибки, четвертый информационный вход блока переключений соединен с вторыми выходами n + 2 блоков сдвиговых регистров, третьи выходы которых соединены соответственно с входами блока преобразования кода системы остаточных классов в двоичный код.

2. Процессор по п.1, отличающийся тем, что канал блока сдвиговых регистров содержит коммутатор, N последовательно соединенных регистров и дополнительный регистр, причем информационный вход и вход управления канала соединены соответственно с информационным входом и входом управления коммутатора, первый выход которого соединен с входом дополнительного регистра, первый и второй выходы которого являются соответственно первым и вторым выходами канала, второй выход коммутатора соединен с входом первого из N последовательно соединенных регистров, первый и второй выходы последнего из которых соединены соответственно с первым и третьим выходами канала.

3. Процессор по п.1, отличающийся тем, что блок переключений содержит две группы по n + 2 коммутаторов и две группы по n + 2 мультиплексоров, причем первый и второй информационные входы блока соединены соответственно с входами коммутаторов первой и второй групп, третий и четвертый информационные входы блока соединены соответственно с первыми входами мультиплексоров первой и второй групп блока, первые выходы коммутаторов первой и второй групп являются соответственно первым и вторым выходами блока, третий и четвертый выходы которого соединены соответственно с выходами мультиплексоров первой и второй групп, вторые входы которых соединены соответственно с вторыми выходами коммутаторов первой и второй групп, управляющие входы коммутаторов и мультиплексоров первой и второй групп соединены с входом управления блока переключений.

4. Процессор по п.1, отличающийся тем, что блок обнаружения ошибки содержит регистр, первый и второй узлы свертки по модулю, первый и второй сумматоры, элемент ИЛИ - НЕ, элемент ИЛИ и группу элементов И, причем информационные входы регистра являются информационным входом блока, информационный выход которого соединен с выходами элементов И группы, первые входы которых соединены соответственно с выходами регистра, с входами первого и второго узлов свертки по модулю и с первыми входами первого и второго сумматоров, вторые входы которых соединены соответственно с выходами первого и второго узлов свертки по модулю, выходы первого и второго сумматоров соединены соответственно с входами элемента ИЛИ и элемента ИЛИ - НЕ, выход которого соединен с вторыми входами элементов И группы, а выход элемента ИЛИ является управляющим выходом блока.

Описание изобретения к патенту

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

Известен систолический процессор дискретного преобразования Фурье - ДПФ (авт.св. СССР N 1363343, кл. G 06 F 15/332, 30.12.87), выбранный в качестве прототипа и содержащий информационные входы, входной регистр, первую (систолическую) матрицу, операционные блоки первой матрицы, вторую (систолическую) матрицу, операционные блоки второй матрицы, сумматор, каналы, информационные выходы, блок синхронизации.

Недостатком данного устpойства является невысокая отказоустойчивость.

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

Сущность изобретения заключается в следующем. Процессор выполняет двумерное преобразование Фурье. Для выполнения ДПФ необходимо производить два действия - сложение и умножение. Непозиционная система счисления, в частности система остаточных классов (СОК), позволяет выполнять рациональные операции (сложение, умножение), причем с большой скоростью. Данная система счисления обладает основным достоинством - независимостью образования разрядов числа, в силу чего каждый разряд несет информацию обо всем исходном числе. Отсюда вытекает возможность их независимой параллельной обработки.

Введение двух дополнительных контрольных оснований (при условии, что p_n-1 p_n < p_n+1 p_n+2, где p_i - основания СОК; n - количество рабочих оснований; p_n+1 и p_n+2 - контрольные основания) позволяет обнаруживать ошибки в цифрах не только по двум любым основаниям, но даже и по трем. Введение блока преобразования двоичного кода в код СОК обеспечивает преобразование значений входных данных Х^(к)по n+2 основаниям СОК ( (K ) ). Введение двух блоков преобразования двоичного кода весовых множителей (W^(d), d ) в код СОК обеспечивает преобразование значений весовых множителей по n+2 основаниям СОК. Введение n+1 систолических матриц преобразования Фурье по первой координате обеспечивает получение значений одномерного ДПФ по основаниям СОК. Введение n+1 дополнительных сумматоров обеспечивает получение сумм по основаниям СОК. Введение n+1 входных регистров обеспечивает запись значений Х^(к) по основаниям СОК. Введение n+1 систолических матриц преобразования Фурье по второй координате обеспечивает получение значения двумерного преобразования Фурье по основаниям СОК. Введение n+1 блоков сдвиговых регистров обеспечивает хранение промежуточных значений. Введение бока преобразования кода СОК в двоичный код обеспечивает преобразование значений двумерного преобразования Фурье, представленного в СОК, в двоичный код. Введение блока обнаружения ошибки обеспечивает обнаружение ошибки по основаниям СОК. Введение блока переключений обеспечивает необходимые переключения при обнаружении ошибки. Таким образом, предлагаемое техническое решение обладает существенными отличиями.

На фиг.1 представлена функциональная схема систолического отказоустойчивого процессора ДПФ; на фиг. 2 - функциональная схема канала блока сдвиговых регистров; на фиг. 3 - функциональная схема блока переключений; на фиг. 4 - функциональная схема блока обнаружения ошибки; на фиг. 5 показаны временные диаграммы соотношения управляющих сигналов У₁...У₄ при обнаружении ошибки; на фиг. 6 - временные диаграммы поступления управляющего сигала У₅ на входы каналов.

Систолический отказоустойчивый процессор ДПФ (фиг.1) содержит информационные входы 1, 2, 3, два блока 4 и 6 преобразования двоичного кода весовых множителей в код СОК, блок 5 преобразования двоичного кода в код СОК, блок 7 переключений, блок 8 входных регистров, n+2 систолических матриц 9 преобразования Фурье по первой координате, операционные блоки 10 систолических матриц преобразования Фурье по первой координате, выходы 11 первых (систолических) матриц, блок 12 обнаружения ошибки, n+2 сумматоров 13, n+2 систолических матриц 14 преобразования Фурье по второй координате, операционные блоки 15 систолических матриц преобразования Фурье по второй координате, n+2 блоков 16 сдвиговых регистров по N каналов 17 в каждом, блок 18 преобразования кода СОК в двоичный код, блок 19 синхронизации, выход 20.

Входы 1, 2, 3 процессора соответственно подключены к входам блоков 4, 5, 6 преобразования двоичного кода в код СОК, выходы которых подключены к информационным входам блока 7 переключений. Первый выход блока 7 подключен к первым входам систолических матриц 9 преобразования Фурье по первой координате, а второй выход - к входам блока 8 входных регистров, выходы которого подсоединены к вторым и третьим входам систолических матриц 9. Выходы 11 матриц 9 подключены к входам блока 12 обнаружения ошибки, первый информационный выход которого объединен с третьим выходом блока 7 переключений и подключен к входам n+2 сумматоров 13 и к первым входам систолических матриц 14 преобразования Фурье по второй координате, на вторые входы которых подключен четвертый выход блока 7 переключений. Второй выход блока 12 обнаружения ошибки подсоединен к входу управления блока 19 синхронизации, первый выход которого подключен к управляющему входу блока 7 переключений. Тактовые входы операционных блоков первых и вторых матриц, блоков сдвиговых регистров объединены и подключены к тактовому выходу блока 19 синхронизации. Выходы n+2 сумматоров 13 подключены к первым информационным входам n+2 блоков 16 сдвиговых регистров, первые выходы которых подключены к вторым входам сумматоров 13. Третьи выходы j-х операционных блоков 15 систолических матриц 14 подключены соответственно к (j+1)-м информационным входам блоков 16 сдвиговых регистров, а (j+1)-е выходы блоков 16 подсоединены к третьим входам j-х операционных блоков 15 систолических матриц преобразования Фурье по второй координате. Вторые выходы блоков 16 сдвиговых регистров подключены к четвертому информационному входу блока 7 переключений. Входы управления блоков 16 сдвиговых регистров объединены и подключены к третьему выходу блока 19 синхронизации. Третьи выходы блоков 16 сдвиговых регистров подключены к входу блока 18 преобразования кода СОК в двоичный код, выход которого является информационным выходом 20 процессора.

Блок 16 сдвиговых регистров содержит N каналов 17, каждый из которых включает в себя (фиг.2) информационный вход 21, вход 22 управления, коммутатор 23, регистры 24, информационные выходы 25, 26, 27. Причем информационный вход 21 подключен к входу коммутатора 23, управляющий вход которого подключен к входу 22 управления. Первый и второй выходы коммутатора 23 подключены к регистрам 24. Первый выход регистра 24, подключенного к второму выходу коммутатора, является выходом 26 блока, а второй выход подключен к выходу 25. Регистры 24 подсоединены между собой последовательно. Выходы N-го регистра являются выходами 25 и 27 блока сдвиговых регистров.

Блок 7 переключений (фиг.3) содержит информационные входы 28, 29, 30, 31, вход 32 управления, n+2 коммутаторов 33, n+2 коммутаторов 34, n+2 мультиплексоров 35, n+2 мультиплексоров 36, информационные выходы 37, 38, 39, 40. Информационные входы 28 и 29 соответственно подключены к входам n+2 коммутаторов 34 и n+2 коммутаторов 33, первые выходы которых подключены соответственно к выходам 38 и 37 блока. Вторые выходы коммутаторов 33 подключены к вторым входам мультиплексоров 35, первые входы которых подключены к информационному входу 31. Вторые выходы n+2 коммутаторов 34 подключены к вторым входам n+2 мультиплексоров 36, первые входы которых подключены к информационному входу 30. Выходы мультиплексоров 35 и 3 подключены соответственно к выходам 39 и 40 блока. Управляющие входы коммутаторов 33, 34 мультиплексоров 35, 36 подключены к входу 32 управления блока.

Блок 12 обнаружения ошибки (фиг.4) содержит информационные входы 41, регистр 42, блоки 43 и 44 модульной свертки, сумматоры 45 и 46, элемент ИЛИ-НЕ 47, блок 48 элементов И, элемент ИЛИ 49, информационный выход 50, выход 51 управления. Информационные входы 41 подключены к входам регистра 42, предназначенного для хранения числа, блоки 43 и 44, предназначенные для вычисления остатков числа по контрольным основаниям, подключены к первому выходу регистра 42. Входы сумматора 45 подключены к выходу блока 43 модульной свертки и к второму выходу регистра 42. Входы сумматора 46 подключены к выходу блока 44 модульной свертки и третьему выходу регистра 42. Выходы сумматоров 45 и 46 подключены к входам элементов ИЛИ-НЕ 47 и ИЛИ 49. Выход элемента ИЛИ-НЕ 47 подключен к первым входам элементов И блока 48, вторые входы которых подсоединены соответственно к выходам регистра 42. Выходы блока 48 и элемента ИЛИ 49 являются соответственно выходами 50 и 51 блока.

Процессор работает следующим образом.

Исходные данные (Х^(к)) и весовые множители W₁, W₂ поступают на входы 1, 2, 3 процессора. Так как на вход управления блока 19 синхронизации с выхода блока 12 обнаружения ошибки управляющих сигналов не поступало, то на первом выходе блока 19 появляется совокупность управляющих сигналов У₁, У₂, У₃, У₄ (причем У₁ = 0, У₂ = 0, У₃ = 0, У₄ = 0), которая поступает на входы коммутаторов 33, 34, мультиплексоров 35, 36, а с третьего выхода блока 19 поступает сигнал У₅ = 0 на входы коммутаторов 23. Исходные данные Х и W₁ преобразуются в код СОК в блоках 5 и 4 и через коммутаторы 33 и 34 блока 7 переключений поступают соответственно на первые входы систолических матриц 9 преобразования Фурье по первой координате (значения W^k-1) и на входы блока 8 входных регистров, а через них на вторые и третьи входы первых (систолических) матриц 9 (значения Х^k). После загрузки строки данных Х^k размером N и поступления весовых множителей W^k-1 систолические матрицы 9 преобразования Фурье по первой координате выполняют одновременное преобразование Фурье по основаниям СОК вида

С₁ = x₁ + W⁰(x₂ + W⁰(x₃ + W⁰(x₄ + ... + W⁰x_N)));

C₂ = x₁ + W¹(x₂ + W¹(x₃ + W¹(x₄ + ... + W¹x_N)));

C_N = x₁ + W^N-1(x₂ + W^N-1(x₃ + W^N-1(x₄ + ... + W^N-1x_N))), где W = exp(-j2 /N).

Отсчеты С_k (k = ) одномерного ДПФ по строке данных поступают на входы блока 12 обнаружения ошибки. Суть его работы заключается в следующем.

Пусть на его вход поступает число C_j = ( ₁, ₂, ..., _n+1, _n+2), где _i - остаток числа по модулю p_i (i = ). Основания p_n+1 и p_n+2 - контрольные. На входы блоков 43 и 44 (фиг.4) с первого выхода регистра 42 подается число C_j = ( ₁, ₂,..., _n) без остатков _n+1 и _n+2 с образованием на их выходах сигналов, соответствующих величинам

_n+1¹ ₁⁽¹⁾ ₁+ ₂⁽¹⁾ ₂+ ... + _n⁽¹⁾ _n(mod p_n+1);

_n+2¹ ₁⁽²⁾ ₁+ ₂⁽²⁾ ₂+ ... + _n⁽²⁾_n(mod p_n+2), где _i⁽¹⁾ и _i⁽²⁾ - константы системы счислены. Остаток _n+1 числа C_jпо контрольному основанию _n+1 с второго входа регистра 42 и величина _n+1 с выхода блока 43 модульной свертки подаются на входы первого сумматора 45 с образованием на его выходе синдрома ошибки, равного

₁ = _n+1 - _n+1¹(mod p_n+1 ).

Остаток _n+2 числа C_j с третьего выхода регистра 42 и величина _n+2¹ с выхода блока 44 модульной свертки подаются на входы сумматора 46 с образованием на его выходе синдрома ошибки, равного

_{2 n+2} - _n+2¹(mod p_n+2).

Если число С не содержит ошибки, то величины ₁ и ₂ равны нулю. Данные значения поступают на входы элемента ИЛИ-НЕ 47 и элемента ИЛИ 49, с выхода которого не поступает сигнал на вход управления блока 19 синхронизации. С выхода элемента ИЛИ-НЕ 47 сигнал подается на входы элементов И блока 48 и значения числа С_j через блок 48 поступают на выход 50 блока 12 обнаружения ошибки. Затем значения C_k (k = ) поступают на входы сумматоров 13 и на первые входы систолических матриц 14 преобразования Фурье по второй координате, на вторые входы которых подаются значения W^m-1, представленные в СОК, поступающие с входа 3 процессора через блок 6 преобразования кода весовых множителей в код СОК и мультиплексор 36 блока 7 переключений. При этом вторые матрицы 14 и сумматоры 13 и связанные с ними блоки 16 сдвиговых регистров выполняют преобразование Фурье матрицы данных по второй координате. После обработки N строк данных по N отсчетам сформирована матрица результатов двумерного преобразования Фуре по основаниям СОК:

I_K1 = C_1K + W⁰(C_2K + W⁰(C_3K + W⁰(C_4K + ... + W⁰C_NK)));

I_K2 = C_1K + W¹(C_2K + W¹(C_3K + W¹(C_4K + ... + W¹C_NK)));

.

.

.

I_KN =C_1K + W^N-1(C_2K + W^N-1(C_3K + +W^N-1(C_4K + ... + W^N-1C_KN))). где W = exp(-j2 /N).

Отсчеты двумерного ДПФ, представленные в коде СОК, поступают на вход блока 18 преобразования кода СОК в двоичный код, выход которого является выходом 20 процессора.

При обнаружении ошибки ( ₁ или ₂ не равны нулю) с выхода блока 12 обнаружения ошибки поступает сигнал на вход управления блока 19 синхронизации, на первом выходе которого появляется следующая совокупность управляющих сигналов: У₁ = 1, У₂ = 1, У₃ = 1, У₄ = 1. При поступлении на управляющие входы коммутаторов 33 управлюящего сигнала У₁= 1 вход 29 (по которому поступают Х^k) блока 7 подключается к вторым входам мультиплексоров 35. При поступлении на управляющие входы коммутаторов 34 управляющего сигнала У₂ = 1 вход 28 (по которому поступают W^k-1) блока 7 подключается к вторым входам мультиплексоров 36. При поступлении на управляющие входы мультиплексоров 35 управляющего сигнала У₃ = 1 вторые входы подключаются к выходам и значения Х^k, представленные по основаниям СОК, поступают на входы сумматоров 13 и первые входы вторых (систолических) матриц 14. При поступлении на _управляющие входы мультиплексоров 36 управляющего сигнала У₄ = 1 значения W^k-1 с вторых входов коммутаторов поступают на вторые входы вторых (систолических) матриц 14. Одновременно с этим с третьего выхода блока 19 синхронизации подается сигнал У₅ = 1, который поступает на управляющие входы коммутаторов 23, которые подключают (фиг.2) информационные входы 21 через регистр 24 к первым выходам 25. При этом вторые матрицы 14, сумматоры 13, блоки 16 сдвиговых регистров выполняют одномерное преобразование Фурье по строке данных. По окончании выполнения одномерного ДПФ с выходов блока 19 синхронизации поступает следующая последовательность управляющих сигналов: У₁ = 1, У₂ = 2, У₃ = 0, У₄ = 0 (фиг.5). По этим командам через мультиплексоры 35 и 36 на входы сумматоров 13 и входы вторых (систолических) матриц 14 поступают значения С_k и W^m-1 (с входа 30 блока 7). При поступлении управляющего сигнала У₅ = 0 (временные диаграммы представлены на фиг.6) коммутаторы 23 подключат N регистров 24 и сумматоры 13, вторые (систолические) матрицы 14, блоки 16 сдвиговых регистров выполняют преобразования Фурье по второй координате. Следовательно, при обнаружении ошибки процессор работает по схеме: одномерное ДПФ == двумерное ДПФ. Время выполнения одномерного ДПФ текущей строки составляет Т₁ = 2(N-1), где - время выполнения базовой операции операционным блоком. Под базовой операцией операционного блока понимаются операции умножения, сложения и передачи операндов, реализуемые отдельным блоком. Время выполнения двумерного ДПФ строки Т₂ = 2N .