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

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

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

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

Сущность изобретения заключается в следующем. Процессор выполняет двумерное дискретное преобразование Фурье ДПФ.

X_N= C_N=
E_N= ,, (1) где X_N - матрица исходных данных;
С_N - матрица результатов;
E_N - матрица действительных экспоненци- альных функций, все матрицы имеют порядок N.

Процессор реализует преобразования (1) по формулам
C⁽¹⁾=(E_NX^(l)) ;;
C⁽²⁾={ W(N

Анализ формул (2) показывает, что для вычисления ДПФ необходимо производить два действия: действительное сложение и умножение. Применение непозиционной системы счисления - системы остаточных классов (СОК) позволяет представить число в виде набора остатков по основаниям Р₁, Р₂,...,Р_k (P_i,i= - взаимно простые между собой и Р₁ < Р₂ < ...<Р_k), т.е. N = ( α₁, α₂,.. ., α_k), причем образование цифр α_iосуществляется следующим процессом:
α_i=N-P_i для i=1,2,...,k.. (3)
Основным достоинством СОК является независимость образования разрядов числа, в силу чего каждый разряд несет информацию обо всем исходном числе, отсюда вытекает возможность их независимой параллельной обработки. Это позволяет привлечь принципиально новые методы арифметического контроля. При введении дополнительного контрольного основания остаток, взятый по этому основанию, несет избыточную информацию об исходном числе, что при условии 2 ^. Р_k-1^. P_k < P_k+1 (k+1 - контрольное основание) позволяет обнаружить и исправить одиночную ошибку в цифрах по рабочим основаниям системы.

Пусть имеют чиcло N = ( α₁, α₂,..., α_k, α_k+1), в то же время это число может быть получено как
N= α_iB_i-rP_n ,, (4) где B_i - ортогональные базисы системы счисления;
r - ранг числа;
P_n= - полный диапазон (5)
ρ = P_i - рабочий диапазон (6)
Подставляют равенство (6) в равенство (5). Получают
P_n= ρ·P_k+1.. (7) Если N < ρ , то число N - правильное, а если N > ρ, то оно - неправильное. Иными словами, если
S = (8) и S = 0, то число N = (α₁, α₂,..., α_k, α_k+1) - правильное, S > 0, то число N неправильное.

Подставляют в формулу (8) равенство (4)
S = = = . (9) Но B_i = R_i ρ + A_i (10) где R_i= , A_i - остаток. Но А_i = B_i, где B_i - ортогональный базис по основаниям Р₁, Р₂, Р₃,...,Р_k.

Подставляют равенство (10) в равенство (9)
S = +R ; r = .

Коэффициенты R_i и B_i для выбранной системы являются постоянными.

Берут систему оснований р₁ = 2, р₂ = 3, р₃ = 5, р₄ = 23.

P_п= P_i=2·3·5·23=690 ;
ρ = р₁^. р₂^. р₃ = 2 ^. 3 ^. 5 = 30.

Ортогональные базисы В₁ = 345, В₂ = =460, В₃ = 276, В₄ = 300.

Вычисляют коэффициенты
В₁ = 30 R₁ + B'₁ = 30 ^. 11 + 15;
B₂ = 30 R₂ + B'₂ = 30 ^. 15 + 10;
B₃ = 30 R₃ + B'₃ = 30 ^. 9 + 6;
B₄ = 30 R₄ + 30 ^.10.

Берут число N = 14. В СОК оно имеет вид N = (0, 2, 4, 14). Вычисляют значение
S = + 11·0+15·2+9·4+10·14=0.

Произошла ошибка N = (0, 0, 4, 14).

S = + 11·0+15·0+9·4+10·14=15..

В соответствии со значением S, поданным на вход ПЗУ, на выходе последнего появляется число со значением , представленным в ПСС:
N_ист= + Δ ..

ПЗУ работает в соответствии с таблицей.

В соответствии со значениями таблицы в первом примере имеют
=14;; N_ист = 14 + 0 = 14, во втором примере
=24;; N_ист = |24 + 20|₃₀⁺ = 14.

Введение трех преобразователей двоичного кода в код СК обеспечивает преобразование значений входных данных (Х^(l) по k+1 основаниям СОК. Введение k систолических матриц-строк обеспечивает получение значений одномерного ДПФ по основаниям СОК. Введение k промежуточных сумматоров обеспечивает получение суммы по основаниям СОК. Введение k входных регистров обеспечивает запись значений входных данных (Х^(l)) по основаниям СОК. Введение k систолических матриц-столбцов обеспечивает получение значения двумерного преобразования Фурье по основаниям СОК. Введение k блоков сдвиговых регистров обеспечивает хранение промежуточных значений. Введение блока преобразования кода СОК в двоичный код обеспечивает преобразование значений двумерного преобразования Фурье, представленного в СОК, в двоичный код. Введение блока коррекции ошибки обеспечивает определение наличия ошибки по основанию СОК и величину Δ коррекции. Введение выходного сумматора обеспечивает получение истинного результата.

На фиг. 1 представлена функциональная схема систолического процессора ДПФ с коррекцией ошибки; на фиг. 2 - функциональная схема блока коррекции ошибки.

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

Блок 16 коррекции ошибки (фиг. 2) содержит информационные входы 21, k+1 входных регистров 22, k-входовой мультиплексор 23, первый блок 24 памяти, второй блок 25 памяти, первый умножитель 26, второй умножитель 27, сумматор 28 по модулю k+1, дополнительный регистр 29, счетчик 30, третий блок 31 памяти, информационный выход 32, вход 33 подсчета переходов.

Вход 1 систолического процессора подключен к входу первого преобразователя 4 двоичного кода в СОК, выход которого подключен к первым входам операционных блоков 9 систолических матриц-строк 8. Вход 2 подсоединен к входу второго преобразователя 5 двоичного кода в СОК, выход которого подключен к входу блока 7 входных регистров. Выходы последнего подсоединены к вторым и третьим входам первых операционных блоков 9 систолических матриц-строк, выходы 10 которых подключены к первым входам промежуточных сумматоров 11 и первым входам операционных блоков 13 систолических матриц-столбцов 12. Структура операционных блоков 9 и 13 аналогична прототипу. Выходы k+1 промежуточных сумматоров 11 подключены к первым информационным входам k+1 блоков 14 сдвиговых регистров. Вторые входы первых операционных блоков 13 систолических матриц-столбцов 12 подключены к выходам третьего преобразователя 6 двоичного кода весовых множителей в код СОК, вход которого является входом 3 процессора. Третьи выходы j-х операционных блоков 13 систолических матриц-столбцов 12 подключены соответственно к (j+1)-м информационным входам блоков 14 сдвиговых регистров, а (j+1)-e выходы блоков 14 подсоединены к третьим входам j-х операционных блоков 13 систолических матриц-столбцов 12. Тактовые входы блоков сдвиговых регистров, операционных блоков первых и вторых матриц объединены и являются тактовым входом 20 процессора. Вторые выходы блоков 14 сдвиговых регистров подключены к входам блока 15 преобразования кода СОК в двоичный код и к входам блока 16 коррекции ошибки, выход которого подключен к второму входу выходного сумматора 17, первый вход которого соединен с выходом блока 15 преобразования кода СОК в двоичный код. Выход сумматора 17 является выходом 18 процессора. Информационные входы 21 блока 16 коррекции ошибки подключены соответственно к входам k+1 входных регистров 22, выходы которых с первого по k-й подключены к входам мультиплексора 23. Выход последнего подключен к первому входу первого умножителя 26, второй вход которого подключен к выходу первого блока 24 памяти. Выход (k+1)-го регистра 22 подключен к первому входу второго умножителя 27, второй вход которого подключен к выходу второго блока 25 памяти. Выходы первого и второго умножителей подключены к первому и второму входам сумматора 28 по модулю k+1, выход которого подключен к входу дополнительного регистра 29. Выход регистра 29 подключен к третьему входу сумматора 28 и адресным входам третьего блока 31 памяти, выход которого является выходом 32 блока коррекции ошибки. Вход 33 подсчета переходов подключен к входу счетчика 30, выход которого подключен к четвертому входу сумматора 28 по модулю k+1.

Систолический процессор работает следующим образом.

Он реализует преобразование (1) по формулам (2). В выражении (2) преобразование в круглых скобках для каждого l выполняется систолическими матрицами-строками 8 лишь один раз с использованием этого результата во всех параллельных ветвях вычисления С(d). Дополнительные операции в выражении (2), соответствующие вычислению преобразования Фурье по второй координате, выполняются дополнительными сумматорами 11, систолическими матрицами-столбцами 12 и блоками 14 сдвиговых регистров, осуществляющими накопления текущих результатов двумерного ДПФ. При этом исходные данные Х^(l) загружаются по входу 2 систолического процессора, затем преобразуются в код СОК по k+1 основаниям СОК в преобразователе 5, а после через блок 7 регистров подаются на вторые и третьи входы систолических матриц-строк 8. На вход 1 поступают весовые множители W_n^m-1 (m ∈ ) , которые в преобразователе 4 преобразуются в код СОК по k+1 основаниям и затем подаются на первые входы систолических матриц-строк 8. С выхода 10 этих матриц считывается результат, соответствующий вычислению одномерного ДПФ, который поступает на первые входы систолических матриц-столбцов 12, на вторые входы которых подаются с входа 3 через блок 6 преобразованные в СОК значения весовых множителей W^l-1 (l ∈ ). Результат двумерного ДПФ снимается с выходов блоков 14 сдвиговых регистров и поступает на вход блока 15 преобразования кода СОК в двоичный код, где преобразуется в двоичный код. С выхода блока 15 полученный результат подается на вход блока 16 коррекции ошибки и на первый вход выходного сумматора 17, где и происходят определение и коррекция результата. Выход сумматора 17 является выходом процессора. Работой процессора управляет блок 19 синхронизации.

Блок 16 коррекции ошибки работает следующим образом.

Значения α_i из k регистров 22 поступают на входы мультиплексора 23, а с (k+1)-го регистра 22 - на второй умножитель 27, где происходит умножение на константу R_k+1. Значения α_i (i=) с выхода мультиплексора поступают на вход первого умножителя 26, где происходит умножение на R_i. В первый такт значения α₁^. R₁ и α_k+1^. R_k+1 подаются на входы сумматора 28, где и происходит сложение. Полученный результат записывается в дополнительный регистр 29. С первого выхода регистра 29 полученный результат (он является промежуточным) подается на вход сумматора 28, а на другой вход - значение α₂^. R₂. После этого происходит сложение и запись результата в регистр 29. Параллельно с преобразованием чисел из СОК в двоичный код происходит вычисление r' - количества переходов через ρ в счетчике 30, с выхода которого это значение поступает на четвертый вход сумматора 28. По окончании суммирования результат сложения S подается на вход третьего блока 31 памяти, где в соответствии с его величиной на выходе появляется значение Δ коррекции.

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

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

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