Лекции по ТБА v3

Generated by Foxit PDF Creator © Foxit Software

http://www.foxitsoftware.com For evaluation only.

51

NS=5

NS=7

1P

КС1

1P

КС2

1

1P

1

1P

2P

2P

2P

ВХ

ВХ

1

2P

1

3P

3P

3P

1

3P

1P

1P

1

1

2P

2P

ВХ

ВХ

3P

3P

Рис. 4.7. Комбинационные схемы для NS=5, 7

		NS=11				NS=13
	1P	1	1P		1P		1P
						1
					2P		2P
	2P	1	2P
					3P	1	3P
	3P		3P
	4P	1	4P
						&
1P		1					1
2P					4P			4P
3P
4P				1P
						1
				2P
				3P
				4P

Рис. 4.8. Комбинационные схемы для NS = 11, 13

Таблица 4.1. Логическая таблица (NS – r) для случая NS = 61

Aвх	Bвх	Cвх	Dвх	Eвх	Fвх	Aвых				Bвых	Cвых			Dвых			Eвых			Fвых
Aвх	0	Cвх	Dвх	Eвх	Fвх				вх	0						вх			вх			вх
							A					C	вх		D			E			F
Aвх	1	0	Dвх	Eвх	Fвх			вх		1	0					вх			вх			вх
							A								D			E			F
Aвх	1	1	0	Eвх	Fвх			вх		1	1			0					вх			вх
							A											E			F
Aвх	1	1	1	0	Fвх			вх		1	1			1			0					вх
							A														F
Aвх	1	1	1	1	0			вх		1	1			1			1			0
							A
0	0	0	0	0	0	0				0	0			0			0			0

Generated by Foxit PDF Creator © Foxit Software

http://www.foxitsoftware.com For evaluation only.

				52
АВХ					АВЫХ
			1
BВХ
					ВВЫХ

СВХ 1

1

&

DВХ 1

&

EВХ

FВХ

АВХ 1 ВВХ

СВХ

DВХ

EВХ

FВХ

СВЫХ

1	DВЫХ

1

1 EВЫХ

&

1 FВЫХ

Рис. 4.9. Комбинационная схема для NS = 61

Использование такого логического подхода к построению вычисли-

тельных блоков увеличивает задержку проведения «бабочки» на 3tкл, но умень-

шает число обращений к ОЗУ, снижает требования к блоку формирования ве-

совых коэффициентов, уменьшая его вычислительную сложность: отпадает не-

обходимость в вычислении V k или его хранении. Кроме того, снижается объем таблиц ППЗУ в самом вычислительном блоке определения <C>S и <D>S.

4.3. Реализация устройства БПФ в СОК

Структурная схема устройства для вычисления NS-точечного БПФ в СОК показана на рис. 4.10. Она содержит блоков определения вычетов

1-1, ..., 1- , арифметических блоков 2-1, ..., 2- , и блоков 3-1, ..., 3- памя-

ти весовых коэффициентов ( –число каналов СОК), синхронизатор 5 и блок восстановления результата 4 .

																					Generated by Foxit PDF Creator © Foxit Software
																					http://www.foxitsoftware.com																	For evaluation only.
25.01.2012 12:15 Курс лекций по дисциплине «Теория быстрых алгоритмов»
																															выход
								вход															от 5
																												4
														шина данных (ШД)
0																																						0
													от 5													от 5																					от 5
															0
																															...																		...
			1-1													1-2																							1-S
	1	2		...			8									1	2	...			8										1						2	... 8											1			2
								1						13								1						13																1					13
							2														2																							2
	.													14		.												14										.											14
	.						8									.					8																	.						8
							9						2-1	15							9					2-2		15																9			2-S	15
							10														10																							10
							11							16							11							16																11					16
							12														12																							12
	3-1															3-2																							3-S
																														шина управления (ШУ)
																														5

Рис. 4.10. Схема устройства БПФ в СОК

Устройство БПФ в СОК работает следующим образом.

Входные числа x(nT) ( n 1, Ns ) через шину данных (ШД) поступают в блоки 1 определения вычетов, формирующих параллельных каналов обра-

ботки чисел в кольце вычетов по выбранным модулям. Блоки 1 строятся на логических схемах или на ПЗУ, в которых каждое число на входе является адресом вычета. Число x (nT) считывает из блока 1 соответствующий вычет

xs	(nT). Для этой схемы данные группируются по	Ns	чисел. Затем группы
	8

чисел записываются в ОЗУ каналов. После записи массива чисел xs (nT) в уз-

лы памяти любого канала начинает выполняться операция «бабочка». Выче-

53

Generated by Foxit PDF Creator © Foxit Software

http://www.foxitsoftware.com For evaluation only.

25.01.2012 12:15 Курс лекций по дисциплине «Теория быстрых алгоритмов»

ты арифметических операций «×» и «+» хранятся в схеме операционного уз-

ла и оттуда считываются.

Следующим шагов по улучшению вычислительных характеристик устройств БПФ в СОК является индексное представление вычетов. Индекс-

ные БПФ в СОК не содержат умножителей, и ,как следствие, имеют мини-

мальное число каналов СОК и высокое быстродействие.

БПФ в СОК( старый вариант)

Синтез непозиционных устройств БПФ содержит следующие этапы:

1.Выбор системы модулей и ее оптимизация.

2.Синтез функциональных модулей БПФ в СОК.

3.Аппаратная реализация алгоритмов БПФ в СОК с заданными свойствами.

	x(kT) x(kT )	x(kT)	Ns x(kT) mod Ns	(5.1)
		Ns
Каждое число входной последовательности x(kT ) и все весовые коэф-
фициенты W переводятся в остаточные классы. Это означает, что:
1)	выбирается система модулей по максимально возможному ре-
зультату;
2)	определяется вычет каждого числа и каждого весового коэффи-

циента по определенному модулю;

3)и образуется многоканальная система обработки данных.

1.Выбор системы модулей для БПФ в СОК.

Наибольшее влияние на число каналов БПФ в СОК оказывает макси-

мальный диапазон результата max , который зависит от числа отсчетов N,

разрядности R1 входных данных x(nT ) и разрядности R2		весовых коэффи-
циентов W k .
max	2R1 R2 log2 N1	(5.2)

54

log2 log2 N R1 R2 1

Generated by Foxit PDF Creator © Foxit Software

http://www.foxitsoftware.com For evaluation only.

25.01.2012 12:15 Курс лекций по дисциплине «Теория быстрых алгоритмов»

где N1 N .

2

Разрядность R1 входных чисел определяется динамическим диапазо-

ном D1 входных сигналов:

R1 D1 , где D1 выражено в децибелах. 6

Например, для наиболее частных случаев ЦОС D1 =60 дБ, т.е. R1 10.

Величина R2 выбирается исходя:

либо из точности дискретизации 1 ,

либо из заданного соотношения 2 СКЗ(ошибки) , СКЗ(сигнала)

либо принимается, что R2 R1.

R	2	log	2	(1	0,5	),	0	1
					1		1
		0,5(log2 log2 N1 log2 6 log2 2 ),							0 2 1	(5.3)
R2

D1

R2

6

Отсюда следует основное соотношение для теоретического определе-

ния числа каналов и модулей в СОК при реализации N-точечного БПФ: (5.4)

Зная N, D1 и задаваясь 1( 2 ) , из формул (5.3-5.4) можно определить систему модулей СОК Ns , минимизируя и (или) Rs max . Или, напротив, по структуре процессора, вычисляющего алгоритм «бабочка» в СОК, и его бы-

стродействию T2 , а также быстродействию позиционного БПФ T1 , определя-

ется max T1 .

T2

После вычисления N, D1 и определяется

Ns . Так можно вычислить верхний предел и

ский характер. При этом max 220 .

Rs max и система модулей

Ns . Он носит теоретиче-

55

Generated by Foxit PDF Creator © Foxit Software

http://www.foxitsoftware.com For evaluation only.

25.01.2012 12:15 Курс лекций по дисциплине «Теория быстрых алгоритмов»

Компьютерное моделирование показывает, что на практике макси-

мально возможный результат не превышает 218 для подавляющего большин-

ства алгоритмов.

Теперь о многоканальной системе обработки данных.

Как известно, базовой вычислительной операцией БПФ является «ба-

бочка».

C A B W k

С прореживанием по времени – ,

D A B W k

C A B

С прореживанием по частоте – .

D (A B) W k

Для осуществления этих преобразований в любом s -канале СОК необ-

ходимо провести операции сложения, вычитания и умножения по соответст-

вующему модулю.

Например,

	k
Сs	As Bs Ws	(5.5)
	k
		k
Ds	As Bs Ws	As Bs Vs

где As , Bs , Cs , Ws , Vs – вычеты по модулю Ns .

Это соотношения используются при построении схемы БПФ в СОК.

As							загрузка
Bs						ТМ			C s
W sk
							загрузка
						ТМ			Ds
Vsk

Рис. Базовый табличный модуль (для Rs 3...4)

Для Rs 5...6 :

56

Generated by Foxit PDF Creator © Foxit Software

http://www.foxitsoftware.com For evaluation only.

25.01.2012 12:15 Курс лекций по дисциплине «Теория быстрых алгоритмов»

Wsk	загрузка
Bs	ТМ
As	загрузка
Vsk	ТМ

загрузка

ТМ Cs

загрузка

ТМ Ds

Операнды подаются на шину адреса табличных модулей, а с информа-

ционных выходов снимаются числа Cs и Ds . В первом случае объем памяти

TM 256 байт, во втором – объем TM 4 Кбайт.

«Бабочку» реализуют схемы базовых табличных модулей. В непере-

страиваемых структурах это может быть ППЗУ, а в перестраиваемых – сверхоперативные ЗУ, загружаемые из основной памяти таблицами выпол-

няемых арифметических операций. Аппаратурные затраты уменьшаются, а

быстродействие увеличивается, если функциональные модули в СОК реали-

зованы на комбинированных операционных схемах (КОС), выполненных в виде заказных СБИС или синтезированных на ПЛМ или ПЛИС.

Приведем пример схемы СБИС для вычисления БПФ на КОС.

W

k

A

Bs

V

k

A

B

s

s

s

s

s

MS

MS

MS

MS

MK

MK

Пs

Пs

MD1

MD2

MD1

MD2

Сs

Ds

МК – матрица конъюнкций,

МD – матрица дизъюнкций,

57

Generated by Foxit PDF Creator © Foxit Software

http://www.foxitsoftware.com For evaluation only.

25.01.2012 12:15 Курс лекций по дисциплине «Теория быстрых алгоритмов»

MS – мультиплексоры,

Пs – произведение.

Вэтой схеме совмещен ряд логических операций «И» и «ИЛИ». Двуме-

стная операция БПФ выполняется в два такта:
1.		Сначала на МК через MS подаются числа Bs ,Ws k и Bs ,Vs k , а с вы-
ходов умножителей считываются произведения Пs																											этих пар.
2.		Далее числа Пs											и As складываются в той же КОС в направлении
МК MD2 и на выходах суммирования образуются числа Cs и Ds .
Приведем пример вычислительного блока «бабочка» в канале Ns																																			2:
A0								&															C 0
W 0																							D 0
			A0
																				&															C 0
																														1
B 0																																			D 0
							&												&
W 0
Пусть Ns 5 . Нарисовать логическую схему КОС для этого случая:
													As Bs Ws									k
									Сs
																						k							k
													As Bs Ws											As Bs
									Ds																		Vs
А = 0, 1, 2, 3, 4; В = 0, 1, 2, 3, 4.
			А											В											А+В					А×В
		000											001										001						000
		000											010										010						000
		000											011										011						000
		000											100										100						000
		001											001										010						001
		001											010										011						010

58

Generated by Foxit PDF Creator © Foxit Software

http://www.foxitsoftware.com For evaluation only.

25.01.2012 12:15 Курс лекций по дисциплине «Теория быстрых алгоритмов»

	001	011		100		011
	001	100		101		100
	010	001		011		000
	010	010		100		100
	010	011		101		110
	010	100		110		100
	011	000		011		000
	011	010		101		110
	011	011		110		1001
	011	100		111		1100
	100	000		100		000
	100	010		110		1000
	100	011		111		1100
	100	100		1000		10000
А В с1,с2 ,...,сm , где ci (ai			bi ) mod Ni , ai		Amod Ni .

Использование такого логического подхода к построению вычислитель-

ных блоков уменьшает число обращений к ОЗУ, снижает требования к блоку формирования весовых коэффициентов, уменьшая его вычислительную сложность. Кроме того, уменьшается объем таблиц ППЗУ в самом вычисли-

тельном блоке определения вычета С и D.

Реализация схем БПФ в СОК

Устройство вычисления Ns -точечного БПФ в СОК.

59

Generated by Foxit PDF Creator © Foxit Software

http://www.foxitsoftware.com For evaluation only.

25.01.2012 12:15 Курс лекций по дисциплине «Теория быстрых алгоритмов»

						вход									от 5
																						4
												ШД
											от 5
		1-1														1-2																		1-S															1-
		1		…8												1	…8															1		…8												1		…8
											13																	…														…
						2-1												2-2																	2-S														2-

3-

3-1		3-2		3-S

МУ

от 5

– число каналов СОК

блоки 1-1, 1-2,…, 1- – блоки определенных вычетов

2-1, 2-2, …, 2- – арифметические блоки

3-1, …, 3- – блоки памяти весовых коэффициентов

4 – блок восстановленного результата

5 – синхронизаторы.

Устройство БПФ в СОК работает следующим образом.

Входные числа x (nT) ( n 1, Ns ) через шину данных (ШД) поступают в блоки 1 определения вычетов, формирующих -параллельных каналов об-

работки чисел в кольце вычетов по выбранным модулям. Блоки 1 строятся на логических схемах или на ПЗУ, в которых каждое число на входе является адресом вычета. Число x (nT) считывает из блока 1 соответствующий вычет

xs	(nT). Для этой схемы данные группируются по	Ns	чисел. Затем группы
	8

чисел записываются в ОЗУ каналов. После записи массива чисел xs (nT) в уз-

60