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

 

Изобретение относится к области вычислительной техники и может быть использовано в системах быстрой обработки сигналов. Техническим результатом является повышение быстродействия и упрощение. Устройство содержит регистры, умножители и сумматоры. 3 ил.

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

Известно "Устройство для умножения комплексных чисел" (а/с 1297034, G 06 F 7/49, 03.10.85 г.).

Это устройство не обеспечивает: а) необходимой простоты аппаратурной реализации; б) необходимого быстродействия из-за сложности управления вычислительным процессом.

Наиболее близким к заявляемому техническому решению является принятое за прототип "Арифметическое устройство для выполнения быстрого преобразования Хартли-Фурье" (присвоен патент 2125290, 6 G 06 F 7/14, заявка 96105426/09 (009126) от 20.03.96 г. ), содержащее регистры, коммутаторы, умножители с накопителями.

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

Это устройство не обеспечивает: а) необходимой простоты аппаратурной реализации; б) необходимого быстродействия.

Сущность изобретения заключается: - в упрощении схемы устройства за счет использования умножителей и сумматоров вместо коммутаторов и умножителей с накопителями; - в существенном увеличении быстродействия работы устройства, достигаемом за счет конвейеризации процесса вычисления базовой операции ("бабочки") алгоритма БПФ или БПХ; - в увеличении быстродействия работы устройства, достигаемом за счет регулярности и простоты управления вычислительным процессом арифметического устройства для выполнения БПФ или БПХ.

Для этого в устройство, содержащее пять регистров, введены три регистра, три умножителя, три сумматора.

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

На фиг. 1 приведена схема арифметического устройства для выполнения алгоритма БПХ; На фиг. 2 приведена временная диаграмма работы арифметического устройства.

В чертежах и тексте приняты следующие обозначения: 1. Первый вход данных.

2. Второй вход данных.

3. Вход управления умножителями.

4. Третий вход данных.

5. Четвертый вход данных.

6. Первый вход управления записью.

7. Первый вход управления сумматором.

8. Пятый вход данных.

9. Вход управления.

10. Шестой вход данных.

11. Второй вход управления записью.

12. Второй вход управления сумматором.

13. Третий вход управления записью.

14. Четвертый вход управления записью.

15. Первый регистр.

16. Второй регистр.

17. Третий регистр.

18. Четвертый регистр.

19. Пятый регистр.

20. Шестой регистр.

21. Первый умножитель.

22. Второй умножитель.

23. Первый сумматор.

24. Второй сумматор.

25. Третий умножитель.

26. Третий сумматор.

27. Седьмой регистр.

28. Восьмой регистр.

29. Первый выход результата.

30. Второй выход результата.

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

К информационным входам первого регистра 15, второго регистра 16, третьего регистра 17 и четвертого регистра 18 подключены соответственно первый вход данных 1, второй вход данных 2, третий вход данных 4 и четвертый вход данных 5. Входы управления записью регистров 15-18 соединены с первым входом управления записью 6. К информационным входам пятого регистра 19 и шестого регистра 20 подключены соответственно пятый вход данных 8 и шестой вход данных 10. Входы управления записью регистров 19, 20 соединены со вторым входом управления записью 11.

Выход первого регистра 15 и выход второго регистра 16 соединены соответственно с первым и вторым информационными входами первого умножителя 21. Выход третьего регистра 17 и выход четвертого регистра 18 соединены соответственно с первым и вторым информационными входами второго умножителя 22. Управляющие входы умножителей 21 и 22 соединены со входом управления умножителями 3. Выход первого умножителя 21 и выход второго умножителя 22 соединены соответственно с первым и вторым информационными входами первого сумматора 23. Управляющий вход сумматора 23 соединен с первым входом управления сумматором 7. Выход первого сумматора 23 соединен с первым информационным входом второго сумматора 24. Выход пятого регистра 19 соединен со вторым информационным входом второго сумматора 24 и с первым информационным входом третьего умножителя 25, второй информационный вход которого соединен с выходом шестого регистра 20. Управляющие входы сумматора 24 и умножителя 25 соединены со входом управления 9.

Выход второго сумматора 24 соединен с информационным входом седьмого регистра 27 и с первым информационным входом третьего сумматора 26, второй информационный вход которого соединен с выходом третьего умножителя 25. Управляющий вход сумматора 26 соединен со вторым входом управления сумматором 12. Выход третьего сумматора 26 соединен с информационным входом восьмого регистра 28. Входы управления записью регистров 27, 28 соединены соответственно с третьим входом управления записью 13 и с четвертым входом управления записью 14. Выходы седьмого и восьмого регистров 27, 28 соединены соответственно с первым и вторым выходами результата 29, 30 и являются информационными выходами устройства.

Устройство работает следующим образом.

Матричный рекуррентный алгоритм БПФ, описанный в а/с 633426, G 06 F 15/332, 13.03.89 г., представляется следующими формулами:

где p, t - размерности матриц A, B, Q, F, G на разных итерациях.

р=2^m-1; t=2^r-m; p*t=2^r-1; r=lоg₂N, где m - номер итерации, m=1, 2, 3, .. .., r, N = 2^r - размерность обрабатываемого массива данных;
матрицы А_p ^t, В_p ^t являются половинами массива данных на соответствующей итерации;
матрицы F_p ^t, G_p ^t являются половинами массива результатов на соответствующей итерации;
Q_p ¹ - первый вектор-столбец матрицы весовых коэффициентов Q_p ^t на соответствующей итерации.

Операция В_p ^t * Q_p ¹ является статическим (поэлементным) произведением матрицы В_p ^t на вектор-столбец Q_p ¹.

Весовые коэффициенты представляются следующим выражением:
Q(k) = exp(-j2(k-1)/N),
где k=1, 2, 3, ..., N/2;
Если взять N = 2, то формулы (1) принимают вид:

Формулы (2) представляют собой известное выражение базовой операции БПФ - "бабочки".

Арифметическое устройство выполняет "бабочку" БПФ в соответствии с формулами (2). Учтем, что числа A, B, Q, F и G являются комплексными. Обозначим:
где a, b, f, g, q - действительные части комплексных чисел A, B, F, G, Q, а ,,,, - мнимые части этих чисел. Как показано в описании патента 2125290, 6 G 06 F 7/14, заявка 96105426/09 (009126) от 20.03.96 г. (название патента: "Арифметическое устройство для выполнения быстрого преобразования Хартли-Фурье"), формулы (2) можно представить в виде двух скалярных произведений матриц на вектор-столбцы:

Предлагаемое арифметическое устройство вычисляет операцию "бабочка" как матричную: вычислением скалярного произведения (3). Можно представить вычислительный процесс по формулам (3) с использованием математического знака суммирования:

где _i и _i - числа a, b, -, -a,1,q , 2, a _i и _i - числа ,,b,-, 1, q, и 2.

Суммы
представляют собой операции скалярного умножения.

Алгоритм скалярного произведения позволяет организовать процесс вычисления "бабочки" БПФ в конвейере, т.е. результат "бабочки" будет выдаваться каждый такт (числа f и , g и ), что существенно увеличивает скорость вычисления всего алгоритма БПФ.

Таким образом, можно выполнить вычисления за 4 такта работы умножителей и сумматоров. Считаем, что такт умножения равен по длительности такту сложения (вычитания). На третьем такте появляются результаты f и . На четвертом такте появляются результаты g и .
Конвейер заполняется за 4 такта, затем результаты вычисления "бабочек" (числа f и , g и ) появляются на выходе каждый такт.

Матричный рекуррентный алгоритм быстрого преобразования Хартли (БПХ) с прореживанием по времени, описанный в патенте РФ 2071221, 6 G 06 F 17/14, заявка 94024301/09 (023698) от 29.06.94 г. (название изобретения: "Процессор для быстрого преобразования Хартли"), представляется следующими формулами:

где р=2^m-1, t=2^r-m, m=1, 2, 3, ..., r;
р, t - размерности матриц на разных итерациях;
С_p ¹ и S_p ¹ - первые вектор-столбцы матриц весовых коэффициентов С_p ^t и S_p ^t на соответствующей итерации;
r - число итераций;
m - номер итерации;
N - длина исходного массива, N=2^r.

Операция В_p ^t*С_p ¹ представляет собой поэлементное (статическое) умножение столбцов матрицы В_p ^t на вектор-столбец С_p ¹. Матрица получена из матрицы В_p ^t. Строки матрицы кроме первой, представлены строками матрицы В_p ^t, размещенными в обратном порядке (инверсия строк).

Весовые коэффициенты представляются следующими выражениями:
С(k)=cоs(2(k-1)/N); S(k)=sin(2(k-1)/N); где k=1, 2, 3, ..., N/2.

Если взять N= 2, то базовая операция БПХ ("бабочка") будет описываться выражением:

Формулы (6) можно представить в виде скалярного произведения матрицы на вектор-столбец:

где входные действительные числа; F, G - выходные действительные числа (результат счета); С и S - весовые коэффициенты.

Как показано в описании патента 2125290, 6 G 06 F 7/14, заявка 96105426/09 от 20.03.96 г. (название патента: "Арифметическое устройство для выполнения быстрого преобразования Хартли-Фурье"), формулы (7) можно представить с использованием математического знака суммирования:

где _i,_i - числа
Сумма
представляет собой операцию скалярного умножения.

Алгоритм скалярного произведения здесь, как и в случае БПФ, позволяет организовать процесс вычисления "бабочки" БПХ в конвейере, т.е. результат "бабочки" будет выдаваться каждый такт (числа F и G), что существенно увеличивает скорость вычисления всего алгоритма БПХ.

Вычисление "бабочки" БПХ выполняется за 4 такта работы умножителей и сумматоров. На третьем такте появляется результат F, а на четвертом - результат G.

Конвейер заполняется за 4 такта, затем результаты вычисления каждой последующей "бабочки" (числа F и G) появляются на выходе каждый такт.

Как мы видим, формулы для вычисления операции "бабочка" аналогичны для БПФ и БПХ. Поэтому в дальнейшем будет рассмотрен процесс вычисления "бабочки" БПХ.

На фиг. 1 приведена схема арифметического устройства для выполнения базовой операции БПХ в конвейере.

По входам 1, 2, 4, 5, 8, 10 в арифметическое устройство поступают действительные числа Регистры 15-20 осуществляют прием и хранение этих чисел. Указанные числа записываются в регистры параллельным кодом. Регистр 15 принимает и хранит число В, регистр 16 - число С, регистр 17 - число регистр 18 - число S, регистр 19 - число A, а регистр 20 - число 2. По входам 6 и 11 устройства на входы управления записью регистров поступают коды записи.

Арифметическое устройство обрабатывает поступающие действительные числа согласно формулам (7). Не выполняется лишь операция умножения числа A на 1, как излишняя. По мере выполнения тактов конвейера с выходов регистров 19 и 20 поступают действительные числа и подмешиваются в скалярное произведение в соответствии с (7). По входам 3, 7, 9 и 12 устройства поступают соответствующие коды управления на умножители 21, 22, 25 и сумматоры 23, 24 и 26. Умножители и сумматоры выполняют операцию вычисления "бабочки" БПХ по тактам, при этом каждый раз результат передается дальше на следующую ступень конвейера, а предыдущая ступень уже готова обрабатывать новые операнды. Три такта работы конвейера затрачиваются на вычисление результата F и один такт на вычисление результата G. Проследим по тактам, как осуществляются вычисления.

1. Из регистра 15 операнд В поступает на первый вход умножителя 21. Из регистра 16 операнд С поступает на второй вход умножителя 21. Операнды В и С перемножаются в умножителе 21 и результат запоминается на выходе умножителя 21.

Одновременно из регистра 17 операнд поступает на первый вход умножителя 22. Из регистра 18 операнд S поступает на второй вход умножителя 22. Операнды и S перемножаются и результат запоминается на выходе умножителя 22.

2. С выхода умножителя 21 произведение поступает на первый вход сумматора 23. С выхода умножителя 22 произведение поступает на второй вход сумматора 23. Поступающие операнды суммируются в сумматоре 23 и результат запоминается на выходе сумматора 23.

3. С выхода сумматора 23 полученная сумма поступает на первый вход сумматора 24. Из регистра 19 операнд A поступает на второй вход сумматора 24. Поступающие операнды суммируются и результат запоминается на выходе сумматора 24. Получен первый результат - число F. Число F записывается в регистр 27.

Одновременно операнд A из регистра 19 поступает на первый вход умножителя 25. Из регистра 20 число 2 поступает на второй вход этого умножителя. Операнды перемножаются и результат запоминается на выходе умножителя 25.

4. С выхода сумматора 24 число F (в дополнительном коде) поступает на первый вход сумматора 26. С выхода умножителя 25 произведение Aх2 поступает на второй вход сумматора 26. Поступающие операнды суммируются в сумматоре 26 (фактически выполняется операция вычитания Aх2-F). Получен второй результат - число G. Число G записывается в регистр 28. По входам 13 и 14 устройства на входы управления записью регистров 27 и 28 поступают коды записи.

Таким образом, полный цикл вычисления базовой операции ("бабочки") БПХ занимает четыре такта работы конвейера, иначе говоря, четыре такта работы умножителей и сумматоров. Результаты вычисления базовой операции (числа F и G) из регистров 27 и 28 поступают на выходы 29 и 30 устройства со сдвигом на такт между собой.

Конвейер заполняется за 4 такта, затем результаты вычисления каждой следующей "бабочки" (числа F и G) появляются на выходе устройства каждый такт.

Временная диаграмма работы арифметического устройства при вычислении нескольких "бабочек" БПХ приведена на фиг.2.

2. Устройство по п.1, отличающееся тем, что дополнительно введено r-1 арифметических устройств по п.1, 3r формирователей адресов, 3r элементов И, r + 1 блоков памяти, г блоков постоянной памяти, блок управления, регистр. Здесь r= log₂N - количество итераций, которые необходимо выполнить для вычисления БПХ или БПФ массива данных произвольной размерности N=2^r, r зависит от размерности массива данных N (r=1, 2, 3, ...).

Таким образом, расширяются возможности устройства по п.1 за счет реализации с помощью описанного в п.1 арифметического устройства конвейерного устройства для выполнения быстрого преобразования Хартли-Фурье (т.е. конвейера по итерациям, вычисляющего БПХ или БПФ).

Сущность изобретения по п.2 заключается:
- в существенном увеличении быстродействия работы устройства, достигаемом за счет полной конвейеризации процесса вычисления алгоритма БПФ или БПХ по итерациям (реализуется конвейер по итерациям) и использования в вычислительном процессе арифметического устройства, описанного в п.1;
- в обеспечении естественного порядка следования входной и выходной информации;
- в упрощении схемы, за счет введения идентичных формирователей адресов, выполненных на ПЗУ, в которых закодированы последовательности адресов чисел, необходимых для выполнения БПФ или БПХ по итерациям;
- в увеличении быстродействия работы устройства, достигаемом за счет регулярности и простоты управления вычислительным процессом БПФ или БПХ.

Устройство будет понятно из следующего описания и приложенного к нему чертежа.

На фиг. 3 приведена схема конвейерного устройства по п.2 для выполнения алгоритма БПХ с использованием конвейера по итерациям.

В чертеже и тексте приняты следующие обозначения:
31. Арифметическое устройство по п.1.

32. Информационный вход конвейерного устройства по п.2.

33. Вход тактовой частоты.

34. Первый элемент И.

35. Второй элемент И.

36. Третий элемент И.

37. Первый блок памяти.

38. Формирователь адресов.

39. Блок управления.

40. Выход первого блока памяти.

41. Выход первого формирователя адресов.

42. Выход второго формирователя адресов.

43. Выход третьего формирователя адресов.

44. Первый блок постоянной памяти.

45. Выход первого блока постоянной памяти.

46. Выход первого арифметического устройства по п.1.

47. Второй блок памяти.

48. Выход второго блока памяти.

49. Первый выход блока управления.

50. Второй выход блока управления.

51. Третий выход блока управления.

52. Четвертый выход блока управления.

53. Пятый выход блока управления.

54. Шестой выход блока управления.

55. Седьмой выход блока управления.

56. Восьмой выход блока управления.

57. Девятый выход блока управления.

58. Десятый выход блока управления.

59. Одиннадцатый выход блока управления.

.......

.......

.......

48+6r. 6r-й выход блока управления.

49+6r. 6r+1-й выход блока управления.

50+6r. 6r+2-й выход блока управления.

51+6r. 6r+3-й выход блока управления.

52+6r. Выход r-го арифметического устройства по п.1.

53+6r. r+1-й блок памяти.

54+6r. Выход r+1-гo блока памяти.

55+6r. Девятый регистр.

56+6r. Информационный выход конвейерного устройства по п.2.

В состав конвейерного устройства для выполнения быстрого преобразования Хартли-Фурье по п.2. (см. фиг.3) входят г арифметических устройств по п.1, r+1 блоков памяти, г блоков постоянной памяти, 3r формирователей адресов, 3r элементов И, блок управления, регистр. Здесь r=log₂N - количество итераций, которые необходимо выполнить для вычисления БПХ или БПФ массива данных произвольной размерности N=2^r, r зависит от размерности массива данных N (r=1, 2, 3 ,...). Число ступеней в конвейерном устройстве равно r.

К первым входам первого 34, второго 35, третьего 36 элементов И подключен вход тактовой частоты 33, с которым соединены также первые входы элементов И следующих r-1 ступеней конвейерного устройства, а также вход блока управления 39. Первый выход 49, второй выход 50, третий выход 51 блока управления 39 соединены соответственно со вторыми входами первого 34, второго 35, третьего 36 элементов И, к выходам которых подключены соответственно входы первого, второго, третьего формирователей адресов 38. Информационный вход конвейерного устройства 32 подключен к первому входу первого блока памяти 37, второй, третий и четвертый входы которого соединены соответственно с четвертым 52 пятым 53 выходами блока управления 39 и с выходом 41 первого формирователя адресов 38. Выход 40 первого блока памяти 37 соединен с первым входом первого арифметического устройства 31, второй и третий входы которого соединены соответственно с выходом 45 первого блока постоянной памяти 44 и с шестым выходом 54 блока управления 39. Вход первого блока постоянной памяти 44 соединен с выходом 43 третьего формирователя адресов 38. Выход 42 второго формирователя адресов 38 соединен со вторым входом второго блока памяти 47, первый вход которого соединен с выходом 46 первого арифметического устройства 31. Третий и четвертый входы второго блока памяти 47 соединены соответственно с седьмым 55 и восьмым 56 выходами блока управления 39.

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

Пятый вход второго блока памяти 47 соединен с выходом четвертого формирователя адресов 38 (на фиг. 3 не показан). Девятый 57, десятый 58 и одиннадцатый 59 выходы блока управления 39 соединены со вторыми входами соответственно четвертого, пятого и шестого элементов И (на фиг.3 не показаны).

................

................

................

6r-й выход 48+6r блока управления 39 соединен с третьим входом r-го арифметического устройства 31, выход 52+6r которого соединен с первым входом r+1-го блока памяти 53+6r. 6r+1-й выход 49+6r и 6r+2-й выход 50+6r блока управления 39 соединены соответственно с третьим и четвертым входами r+1-го блока памяти 53+6r, выход 54+6r которого соединен с информационным входом девятого регистра 55+6r, вход управления записью которого соединен с 6r+3-м выходом 51+6r блока управления 39. Выход 56+6r девятого регистра 55+6r является информационным выходом конвейерного устройства.

Формирователь адресов 38 выполнен по а/с 1425667, G 06 F 9/36, 19.02.87 г.

Устройство работает следующим образом.

Число ступеней в конвейерном устройстве равно r, т.е. равно количеству итераций, которые необходимо выполнить для вычисления БПХ или БПФ массива данных размерности N=2^r. Мы рассмотрим конвейерное устройство для вычисления БПХ.

Вычисления по итерациям осуществляются согласно матричному рекуррентному алгоритму БПХ (5). Исходная информация в виде массива действительных чисел длиной N= 2^r поступает в естественном порядке следования на информационный вход конвейерного устройства 32 и записывается в первую область первого блока памяти 37. Информация поступает с тактом работы конвейера арифметического устройства по п.1. Сигналы записи поступают с выхода 52 блока управления 39. На вход тактовой частоты 33 поступают тактовые импульсы. После того, как в первую область первого блока памяти 37 будет записан весь массив длиной N= 2^r, записанная информация из первой области без изменения порядка следования перезаписывается во вторую область первого блока памяти 37, а в первую область блока памяти 37 с информационного входа 32 начинает записываться следующий входной массив длиной N. В это время, над массивом, находящимся во второй области первого блока памяти 37, начинает выполняться 1-я итерация алгоритма БПХ. Коммутация первой и второй областей первого блока памяти 37 осуществляется сигналом с выхода 53 блока управления 39. В качестве блоков памяти 37, 47, ..., 53+6r могут быть использованы микросхемы двухпортовой памяти, позволяющие одновременно записывать и считывать информацию.

Рассмотрим работу 1-й ступени конвейерного устройства, т.е. выполнение первой итерации алгоритма БПХ. С выходов 49, 50 и 51 блока управления 39 соответствующие сигналы разрешения поступают на элементы И34, И35 и И36. Тактовые импульсы с выходов элементов И34, И35 и И36 поступают соответственно на входы первого, второго и третьего формирователей адресов 38. Все три формирователя адресов 38 начинают формировать адреса операндов и адреса для записи результатов "бабочки" - чисел F и G в соответствии с временной диаграммой работы арифметического устройства по п.1 (фиг.2).

На выходе 41 первого формирователя адресов 38, начиная с 1-й "бабочки" БПХ, появляются адреса операндов поступающие во вторую область первого блока памяти 37. С выхода 40 блока памяти 37 операнды соответствующие этим адресам, параллельным кодом поступают на первый вход первого арифметического устройства 31.

На выходе 43 третьего формирователя адресов 38 появляются адреса операндов С, S и числа 2, поступающие на вход первого блока постоянной памяти 44. С выхода 45 первого блока постоянной памяти 44 операнды C, S и число 2, соответствующие этим адресам, параллельным кодом поступают на второй вход первого арифметического устройства 31.

Арифметическое устройство 31 обрабатывает поступающие действительные числа согласно формулам (7) - как было описано выше. Конвейер заполняется за 4 такта, затем результаты вычисления каждой следующей "бабочки" БПХ (числа F и G) появляются на выходе арифметического устройства 31 каждый такт (в соответствии с временной диаграммой работы, приведенной на фиг.2).

Второй формирователь адресов 38 вырабатывает адреса для записи чисел F и G; затем эти адреса с выхода 42 второго формирователя адресов поступают в первую область второго блока памяти 47. Результаты вычисления "бабочек" - числа F и G, появляющиеся на выходе первого арифметического устройства 31, записываются по этим адресам в первую область блока памяти 47. Сигналы записи поступают с выхода 55 блока управления 39.

Подробнее работа формирователей адресов 38 описана в патенте РФ 2071221, 6 G 06 F 17/14, заявка 94024301/09 от 29.06.94 г., название изобретения: "Процессор для быстрого преобразования Хартли".

Сигналы управления умножителями и сумматорами 21, 22, 23, 24, 25, 26, а также сигналы управления записью в регистры 15, 16, 17, 18, 19, 20, 27 и 28 арифметического устройства 31 поступают с выхода 54 блока управления 39.

Таким образом осуществляется вычисление всех N/2 "бабочек" первой итерации алгоритма БПХ на первой ступени конвейерного устройства. По времени выполнение первой итерации (как и всех остальных) занимает N/2 тактов работы конвейера арифметического устройства 31 (такт работы конвейера обозначен T_ап на фиг.2).

После окончания счета первой итерации массив результатов, накопленный в первой области второго блока памяти 47, без изменения порядка следования перезаписывается во вторую область блока памяти 47, а в первую область блока памяти 47 вновь начинают записываться результаты вычисления 1-й итерации нового входного массива длиной N, который до этого находился в первой области первого блока памяти 37 и был перезаписан во вторую область блока памяти 37. Одновременно с этим в первую область блока памяти 37 с информационного входа конвейерного устройства 32 начинает записываться следующий входной массив длиной N с тактом работы конвейера арифметического устройства 31.

Коммутация первой и второй областей второго блока памяти 47 осуществляется сигналом с выхода 56 блока управления 39.

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

В каждый момент времени каждая ступень конвейерного устройства выполняет "свою" итерацию алгоритма БПХ: 1-я ступень - первую итерацию, 2-я ступень - вторую итерацию и т.д. Входная информация поступает на информационный вход 32 с тактом работы конвейера арифметического устройства 31.

Каждый раз по окончании выполнения итерации перезапись информации из первых областей блоков памяти 37, 47 и т.д. во вторые области этих блоков памяти происходит синхронно для всех блоков памяти. Число блоков памяти равно числу ступеней в конвейерном устройстве плюс единица, т.е. равно r+1.

Все r ступеней конвейерного устройства имеют одинаковую с 1-й ступенью схему и выполняют соответствующие итерации аналогично тому, как это было описано для 1-й ступени. Число выходов блока управления 39 пропорционально числу ступеней конвейерного устройства.

Рассмотрим работу последней, r-й ступени конвейерного устройства (при длине входного массива данных N=2^r). Эта ступень выполняет последнюю, r-ю итерацию алгоритма БПХ. Итерация выполняется аналогично предыдущим. Результаты вычисления "бабочек" - числа F и G с выхода r-го арифметического устройства 31 записываются в первую область r+1-го блока памяти 53+6r. Сигналы записи поступают с выхода 49+6r блока управления 39. Адреса операндов и адреса для записи результатов "бабочки" формируются соответствующими формирователями адресов 38 r-й ступени (на фиг.3 не показаны).

По окончании вычисления последней, N/2-й "бабочки", последней, r-й итерации в первой области r+1-го блока памяти 53+6r будет накоплен искомый массив спектра Хартли (массив дискретного преобразования Хартли - ДПХ) в естественном порядке следования. Затем, по сигналу с выхода 50+6r блока управления 39 массив спектра Хартли без изменения порядка следования из первой области перезаписывается во вторую область r+1-го блока памяти 53+6r. После этого ступени конвейерного устройства начинают выполнять соответствующие итерации, а результирующий спектр Хартли с выхода 54+6r r+1-гo блока памяти последовательно, с тактом работы Т_ап конвейера арифметического устройства 31 начинает записываться в регистр 55+6r. Код записи поступает на вход управления записью регистра 55+6r с выхода 51+6r блока управления 39. Затем полученный спектр Хартли (ДПХ) поступает на информационный выход конвейерного устройства 56+6r.

Конвейерное устройство по п.2 заполняется за rN/2 тактов работы конвейера арифметического устройства 31, затем искомый спектр Хартли исходных массивов появляется в естественном порядке следования на информационном выходе 56+6r с тактом работы Т_ап конвейера арифметического устройства 31 по п. 1. Причем, сначала выйдет 1-й массив ДПХ длиной N=2^r, за ним 2-й массив, потом 3-й и т.д. Т.е. результирующая последовательность ДПХ будет выходить массивами (частями) длиной N= 2^r, которые соответствуют исходным массивам данных также длиной N=2^r, поступающим на информационный вход 32.

Таким образом, достигается полная конвейеризация процесса вычисления алгоритма БПХ.

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

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

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3