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

Размещено на http://www.allbest.ru/

Министерство высшего и среднего специального образования РФ

Московский Государственный Институт Электронной Техники

(Технический Университет)

факультет МПиТК

кафедра ВТ

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА к дипломному проекту на тему

«Специализированный микропроцессор для вычисления быстрого преобразования Фурье»

Дипломант: Марков А.А.

Руководитель проекта: Широ Г.Э.

Консультант: Широ Г.Э.

Консультант по технологической части: Грушевский А.М.

2001 г.

Содержание

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

1.1 ТЗ

1.2 Введение

1.3 БПФ и его реализация

1.4 Архитектура микропроцессора

1.5.1 ПЗУ микропроцессора

1.6 Взаимодействие с внешним ОЗУ

1.6.1 Цикл чтения из ОЗУ

1.6.2 Цикл записи в ОЗУ

1.7 Устройство, вычисляющее БПФ

2. Быстродействующий умножитель

2.1 Введение

2.2 Архитектура умножителей

2.2.1 Итеративный умножитель

2.2.2 Линейная архитектура

2.2.3 Параллельная архитектура

2.3 Генерация частичных произведений

2.3.1 Классическая генерация частичных произведений

2.3.2 Алгоритм Бута

2.4 Дерево Уоллеса

2.5 Сумматор с предвычислением переносов

3. Технологический процесс монтажа печатной платы устройства БПФ на базе специализированного микропроцессора

3.1 Введение

3.2 Монтаж навесных компонентов на печатных платах

3.2.1 Основные методы пайки

3.3 Выбор варианта монтажа

3.4 Разработка технологического процесса сборки и монтажа печатной платы устройства БПФ

3.4.1 Выбор флюса

3.4.2 Выбор припоя

3.4.3 Выбор очистительных жидкостей

3.4.4 Выбор клеев

3.5 Алгоритм технологического процесса сборки и монтажа устройства на базе специализированного микропроцессора

3.6 Вывод

4. Сегментация рынка пользователей специализированного микропроцессор

4.1 Введение

4.2 Принципы сегментации

4.3 Формализованная методика расчета сегментации рынка

4.4 Поиск сегментов рынка микропроцессора

5. Рациональная организация рабочего места проектировщика интегральных схем

51 Введение

5.2 Неблагоприятные факторы

5.3 Электроопасность и пожароопасность

5.4 Шумы

5.5 Микроклимат

5.6 Освещенность

5.7 Расчет искусственного освещения

5.8 Воздействие статического электричества и излучения

5.9 Организационные мероприятия по созданию условий безопасного труда

5.10 Психофизиологические факторы

5.11 Вывод

Заключение

Литература

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

микропроцессор плата пользователь вычисление

1.1 ТЗ

Разработать схему микропроцессора (МП), реализующую функцию вычисления «Быстрого преобразования Фурье» (БПФ) на уровне эскизного проекта. При разработке сделать упор на минимизацию размера ОЗУ на кристалле микропроцессора. Исходная последовательность отсчетов - 4096 точек. Точность - 16 разрядов. Проработать до уровня принципиальной электрической схемы основой узел МП - умножитель. Разрядность входных операндов - 16 бит. Разработать эскиз устройства для вычисления БПФ (на базе МП), работающее в составе персонального компьютера. Интерфейс устройства - PCI.

1.2 Введение

Одним из наиболее эффективных направлений анализа набора данных является анализ спектра полученных данных. Под данными в этом случае понимается произвольный набор значений-отсчетов, часто - полученный опытным путем. В качестве инструмента выступают различные дискретные преобразования, как то: «дискретное преобразование Фурье» (ДПФ), вейвлет-преобразованиe, и т.д. Полученные в результате преобразования значения - коэффициенты при базисных функциях (в случае ДПФ это cos и sin) - составляют спектр исходного набора данных.

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

С точки зрения схемотехники, вычисление ДПФ - довольно трудоемкая задача. Согласно формуле вычисления ДПФ, , (N - количество исходных отсчетов, x(n) - n-ый отсчет, X(k) - k-ый коэффициент спектра), на вычисление одного коэффициента спектра идет N операций умножения. Нетрудно представить, что для вычисления полного ДПФ нужно затратить N² операций умножения, и столько же операций сложения. Быстрое преобразование Фурье позволяет сократить число операций умножения с N² до Nlog₂(N). Для сравнения: при вычислении 4096-точечного ДПФ, разница в скорости между двумя алгоритмами составляет два порядка (!). БПФ в этом случае оказывается быстрее классического ДПФ где-то в 300 раз.

В данном дипломном проекте рассматривается аппаратная реализация быстрого преобразования Фурье, разработанная в виде специализированного микропроцессора. Особенностями реализации являются:

- небольшой размер ОЗУ на кристалле

- высокое быстродействие, обусловленное применяемым алгоритмом умножения и совмещением внутренних микроопераций МП при работе с внешним ОЗУ.

1.3 БПФ и его реализация

Какое количество вычислений требуется, чтобы вычислить дискретное преобразование Фурье N точек? Долгое время, до середины 60-х, стандартным ответом было следующее.

Определим как , тогда формула ДПФ может быть записана: , где k = 0,…, N-1; x(n) - последовательность из N временных отсчетов. Иными словами матрица, с W^nk в качестве (n,k)-ых элементов, умножается на вектор x(n). В результате получается вектор X(k). Очевидно, что операция матричного умножения требует для своей реализации О(N²) умножений и O(N²) сложений. Плюс небольшое число операций, необходимых для генерации степеней W (которые, впрочем, могут быть сгенерированы заранее).

Рассмотрим алгоритм быстрого преобразования Фурье с прореживанием по времени. Пусть длина исходной последовательности является степенью двойки, т.е.: N=2^L, где L > 0 - целое. Выделим из нее последовательность ее четных членов и последовательность нечетных, и сгруппируем соответствующим образом:

Каждая из сумм F_n представляет собой N/2-точечное ДПФ, которое аналогичным образом можно представить через N/4-точечные, а те, в свою очередь, через N/8-точечные и так далее, пока не останутся только одноточечные преобразования. Т.е. на каком-то шаге мы получим, что F^{eoeeoeooee…oee} = x(n) для некоторого n. Сразу появляется вопрос - а каким наборам «е» и «о» соответствуют какие «n»? Ответ таков: инвертируйте порядок следования «е» и «о», затем положите e = 0, а o = 1, и вы получите двоичное значение n. Пример соответствия индексов для N=8 можно видеть на рисунке 1.1.



Рис 1.1

Алгоритм вычисления БПФ, в результате, выглядит следующим образом: предположим, у нас есть вектор данных x(n). Расположим его значения в порядке двоичной инверсии номеров. Мы получили конечные, одноточечные преобразования. Затем происходит рекомбинация пар для вычисления частичных преобразований по следующим формулам:

X_m(p) = X_m+1(p)+W^dX_m+1(q)

X_m(q) = X_m+1(p)-W^dX_m+1(q),

т.н. «бабочка», где m и m+1 - последовательные уровни преобразования, а W^d - соответствующие уровню коэффициенты.

Затем рекомбинируют смежные пары пар и т.д. до получения полного преобразования. На каждом уровне совершается порядка N операций умножения. Всего уровней log₂N. Следовательно весь алгоритм займет порядка Nlog₂N операций.

«Бабочка» - основной элемент преобразования. БПФ любой последовательности можно выразить через элементы-бабочки. Графически в дальнейшем будем обозначать ее так: (Рис 1.2)



Рис. 1.2 Графическое обозначение «бабочки».

Архитектурно «бабочка» выглядит следующим образом:

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

В нашем случае исходные операнды 16-тиразрядные. На выходе умножителя также 16-тиразрядное число (|W|1, младшие 16 разрядов отбрасываются, что в данном случае эквивалентно округлению). На выходе одного из конечных сумматоров теоретически может возникнуть переполнение. Для борьбы с этим используется адаптивный алгоритм, подробно описанный в следующем разделе.

1.4 Архитектура микропроцессора

Структурная схема простейшего микропроцессора, вычисляющего БПФ, выглядит следующим образом(см. рис 1.3):

Алгоритм его работы следующий:

1) Записываем входную последовательность в ОЗУ1 в соответствии с двоичной инверсией номеров.

2) Данные считываются из ОЗУ1 в соответствии с требуемым порядком, преобразовываются бабочкой, и записываются в ОЗУ2.

3) Данные считываются из ОЗУ2 в соответствии с требуемым порядком, преобразовываются бабочкой, и записываются в ОЗУ1

4) Повторяем шаги 2, 3 до получения полного преобразования

5) Выгружаем полученное преобразование из ОЗУ1

Рис 1.3 Простейший микропроцессор для вычисления БПФ

Недостатки такой организации микропроцессора следующие:

1) Необходимость иметь большое ОЗУ на кристалле. На практике это требование означает, что, фактически, изготовить такой кристалл в России будет проблематично.

2) Наиболее выгодно использовать бабочки с n входами (n зависит от конкретного случая)

Все это позволяет подойти к проблеме вычисления 4096-точечного БПФ следующим образом.

Будем вычислять БПФ в два прохода (отсюда название - двухпроходный БПФ процессор). Для этого возьмем бабочку на 64 входа (4096 = 64*64). И, выбирая данные последовательно, блок за блоком, вычислим с ее помощью частичное БПФ с глубиной шесть уровней (первый проход). Затем еще раз пройдемся, теперь уже по полученным данным, и повторно подадим их на вход бабочки порциями, но теперь уже не последовательно, а в том порядке, в котором мы подавали бы их на вход бабочки, если бы делали БПФ на 4096 точки целиком. Полученные в результате данные и будут искомым спектром Фурье.

Рассмотрим этот процесс более детально на примере бабочки на 16 входов:

Рис 1.4 Пример «бабочки» на 16 входов

Слева - исходные отсчеты, расположенные в том порядке, в котором требуется для выполнения БПФ. Справа - результирующие коэффициенты спектра Фурье. Как видно из рисунка, соседние уровни отличаются друг от друга только коэффициентами бабочек W, и порядком межсоединений. Таким образом, мы можем объединить несколько элементарных бабочек (на 2 входа) в одну, и, управляя только коэффициентами этой новой бабочки, выразить все преобразование посредством ее одной.

Например, для примера, приведенного выше (БПФ на 16 точек), можно взять в качестве базовой бабочку на 4 входа, и результирующее БПФ будет выглядеть так (см. рис. 1.5). При кажущейся сложности межсоединений первого уровня бабочек со вторым, алгоритм очень прост: на вход первой бабочки второго уровня подаются 0-ой, 4-ый, 8-ой, 12-ый выходы предыдущего уровня. На вход второй бабочки, соответственно, 1-ый, 5-ый, 9-ый, 13-ый. И так далее, перебирая все бабочки. Как видно, мы берем в данном случае каждый четвертый выход. Это правило сохраняется и в случае бабочек более высоких порядков.

Рис 1.5 Реализация 16-ти точечного БПФ бабочками на 4 входа

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

На выходе бабочки мы имеем два 17-тиразрядных числа. Разряды 0..15 передаются на выход, 16-ый - сигнальный. Если 16-ый разряд одной из бабочек k-го уроня выставлен в единицу, мы имеем переполнение, и все коэффициенты на выходах всех бабочек k-го уровня делятся на два (сдвигом вправо на один разряд) перед подачей на входы бабочек следующего уровня. Блок управления получает сигнал о том, что коэффициенты были смасштабированы по амплитуде и увеличивает счетчик числа масштабирований на единицу. После выполнения БПФ, конечные значения коэффициентов спектра домножаются на 2^k, где k-сохраненной в блоке управления число масшабирований.

Размещено на http://www.allbest.ru/

Одним их коренных отличий и преимуществ данного микропроцессора (пункт, отдельно отмеченный в ТЗ) является небольшой размер ОЗУ на кристалле. Рассмотрим подробнее вопрос минимизации размера ОЗУ. Будем хранить входные и промежуточные данные во внешнем ОЗУ (которое, к примеру, может быть зарубежного производства). Самые известные производители микросхем ОЗУ - Samsung, Texas Instruments, Micron. Для простоты возьмем статическое ОЗУ. Для выборки данных и хранения их непосредственно перед и после преобразования нужно небольшое буферное ОЗУ, которое и будет размещено на кристалле. В нашем случае размер буферного ОЗУ составляет 2x64x16. Функциональная схема микропроцессора будет выглядеть следующим образом (см. рис. 1.6). Пунктирной линией обведен микропроцессор.

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

	Микрооперация 1	Микрооперация 2	Микрооперация 3
1	Закачивание блока данных из внешнего ОЗУ во внутреннее, буферное ОЗУ.
2	Частичное ДПФ блока данных на бабочке и сброс результата во второе буферное ОЗУ	Закачивание следующего блока данных из внешнего ОЗУ
3	Вывод блока промежуточных данных из буферного ОЗУ во внешнее	Частичное ДПФ блока данных на бабочке и сброс результата во второе буферное ОЗУ	Закачивание следующего блока данных из внешнего ОЗУ1

¹ Обоснование возможности реализации операций ввода и вывода в/из внешнего ОЗУ во время преобразования будет дано позже.

Стадия 3 повторяется до тех пор, пока не будут выбраны все данные из внешнего ОЗУ.

1.5.1 ПЗУ микропроцессора

Посмотрим еще раз на формулу коэффициентов W_N:

Для нашей бабочки N принимает значения {2,4,8,16,32,64} на первом проходе и {128,256,512,1024,2048,4096} на втором. Как следует из формулы, каждый набор значений W_N на уровне преобразования t, является подмножеством значений W_N на уровне (t+1). Т.е. нам надо хранить только значения последнего уровня - W₄₀₉₆. Учитывая то, формула W_N симметрична, можно хранить лишь половину значений (это также видно и из схемы бабочки), т.е. 2048.

Можно поступить иначе: из набора коэффициентов можно получить все остальные последовательным умножением на поворачивающие множители . В этом случае эффективность немного упадет, зато размер ПЗУ получится очень небольшим (68x16). Величина разрядной сетки значений - 16 бит. ПЗУ также размещается на кристалле микропроцессора.

1.6 Взаимодействие с внешним ОЗУ

Теоретически, внешнее ОЗУ может быть любым. Возьмем для простоты в качестве внешнего статическое асинхронное ОЗУ. Конструктивно оно выполнено в виде единой микросхемы. В настоящее время можно найти множество различных вариантов от разных производителей, особенно учитывая небольшую емкость ОЗУ - 4Кx16 (уже существуют и выпускаются микросхемы статического ОЗУ на 4Мбита).

Рассмотрим взаимодействие между микропроцессором и ОЗУ на уровне временных диаграмм. В качестве ОЗУ возьмем 16-ти разрядную микросхему памяти Samsung серии K6R1016C1C. Соответствующие временные диаграммы фаз чтения и записи тогда будут выглядеть следующим образом:

1.6.1 Цикл чтения из ОЗУ

Размещено на http://www.allbest.ru/

1) На линии WE выставляется высокий уровень (чтение). Выставляются сигналы CS и OE.

2) На шине адреса(AB) выставляется адрес требуемого слова.

3) Через время t_выб, необходимое для того, чтобы извлечь слово по нужному адресу из памяти, результат можно снимать с шины данных(DB).

1.6.2 Цикл записи в ОЗУ:

1) На шине адреса(AB) выставляется адрес ячейки памяти для записи.

2) Выставляются сигналы CS и WE.

3) На шине данных(DB) выставляются данные, которые необходимо записать в память. Выдерживается время для гарантированной записи данных в память, по прошествии которого сигналы CS и WE снимаются.

Цикл записи в статическое ОЗУ

Размещено на http://www.allbest.ru/

Для микросхем этой серии длительности циклов чтения и записи слова по определенному адресу лежат в диапазоне 1020 нс. Учитывая то, что данные на вход бабочки подаются блоками по 64 слова, получаем, что полная длительность цикла чтения и записи не менее 6401280 нс. Учитывая то, что время работы одного умножителя в среднем 17нс, время работы бабочки на 64 входа составляет никак не меньше (и это еще без учета сложений). Следовательно за время преобразования вполне можно успеть выкачать из внешнего ОЗУ новую порцию данных и сбросить старую. Так что «простоев» бабочки из-за медленных внешних каналов не будет

1.7 Устройство, вычисляющее БПФ

Рассмотрим на уровне эскиза устройство, выполняющее БПФ. В качестве интерфейсной шины выбрана шину PCI. Действительно, шина ISA не является удачным выбором по двум причинам:

1) Гораздо более низкая производительность, чем у шины PCI (8Мгц против 33Мгц, 16 разрядов против 32).

2) Практическое отсутствие в настоящее время поддержки шины ISA со стороны производителей материнских плат.

В «общении» ПК с устройством можно рассматривать две фазы. Первая - передача устройству набора исходных данных. Вторая - получение от устройства набора коэффициентов ДПФ.

Вообще говоря, для полноценной поддержки PCI со стороны устройства удобнее всего поставить готовый контроллер от таких фирм, как AMCC. Он гарантирует, что устройство будет полностью соответствовать спецификации PCI, а интерфейс, который он предлагает пользователю, гораздо проще в использовании. Тогда устройство для вычисления БПФ будет функционально состоять из трех следующих блоков: микроконтроллера AMCC S5920, микросхемы статического ОЗУ и собственно микропроцессора.

2. Быстродействующий умножитель

2.1 Введение

Умножитель является основным элементом «бабочки» микропроцессора. От его быстродействия зависит быстродействие всей системы в целом.

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

Второй непременной составляющей умножителя является блок сумматоров, который складывает получившиеся на первом этапе частичные произведения для получения окончательного ответа. В данной дипломной работе, этот блок состоит из двух частей: дерева Уоллеса и сумматора с предвычислением переносов (СПП). Дерево Уоллеса сводит сложение M чисел к сложению двух, а СПП складывает эти оставшиеся числа.

2.2 Архитектура умножителей

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

2.2.1 Итеративный умножитель

Самый простой способ сложить несколько частичных произведений показан на рисунке 2.1. Он основан на сумматоре с регистром - аккумулятором и сдвиговом регистре. Этот умножитель относительно медленен, т.к. сложение N частичных произведений занимает N тактов. Самый простой способ тактирования - использовать синхронизацию системы, в которой применяется этот умножитель. Обычно частота системы гораздо меньше, чем максимально возможная частота работы такого умножителя, так что для того, чтобы минимизировать задержку, нужно использовать множитель частоты, что не всегда удобно и возможно, или умножитель должен тактироваться своей собственной частотой.



Рис 2.1 Итеративный умножитель

2.2.2 Линейная архитектура

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



Рис 2.2 Сложение трех операндов за такт

2.2.3 Параллельная архитектура

Для того, чтобы сложить несколько частичных произведений, совсем необязательно соединять сумматоры последовательно. Вместо этого их можно соединить так, чтобы максимально распараллелить вычисления, как показано на рис. 2.3. В этом случае схемотехнические затраты такие же, как в случае умножителей с линейной архитектурой, но межсоединения элементов носят более сложный характер. Время сложения N элементов в этом случае пропорционально log N, что гораздо быстрее для больших значений N. С другой стороны, дополнительная сложность межсоединений сумматоров может потребовать увеличения размеров и величины задержки.



Рис 2.3 Умножитель с параллельной архитектурой

2.3 Генерация частичных произведений

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

2.3.1 Классическая генерация частичных произведений

На рисунке 2.4 представлен процесс вычисления частичных произведений в простейшем случае (сложение столбиком). Разрядность элементов - 16.

Рис 2.4

Каждая точка на рисунке - это один бит, принимающий значения {0,1}. Частичные произведения представлены горизонтальными строками точек. Они сдвинуты друг относительно друга для того, чтобы соответствовать различным арифметическим весам множителя.

Грубо говоря, общее число бит (256 для этого случая) в области частичных произведений пропорционально величине требуемого для реализации алгоритма оборудования. Кроме того, время работы такой схемы зависит от «высоты» секции частичных произведений (т.е. от максимального числа бит в каждой вертикальной колонке). Эта зависимость может менять свой характер от логарифмической (при реализации сложения в виде дерева) до линейной (когда суммирование реализовано строго последовательно). И все же, независимо от способа реализации, чем меньше частичных произведений, тем лучше.

Для данного случая, логика выбора частичных произведений очень проста. Она состоит из одного логического вентиля «И» на бит (см. рисунок 2.5).

Рис 2.5 Схема выбора частичных произведений

2.3.2 Алгоритм Бута

Простейший алгоритм уменьшения числа частичных произведений, предложенный Бутом, состоит в следующем: биты множителя группируются по два и, в зависимости от значения битов в группе, из множества {0, M, 2M, 3M} выбирается один из четырех вариантов частичного произведения (M - множимое). Это сокращает число частичных произведений вдвое, но для 3M требует распространения переносов, перед тем, как будут сгенерированы следующие частичные произведения. Вместо этого используется модифицированный алгоритм Бута, который сокращает число частичных произведений меньше, чем в два раза, но не требует предварительного сложения для вычисления частичных произведений. Общая идея состоит в том, чтобы при декодировании множителя чуть усложнить работу, выбирая варианты частичных произведений из множества {0, M, 2M, 4M + -M}. Все составляющие множества могут быть получены простыми логическими сдвигами и дополнением. Как можно видеть, элемент 3M был заменен на 4M + -M. В зависимости от значений битов смежной группы, или 4M сдвигается в более значащую группу (становясь при этом M) или -M сдвигается в менее значащую группу (становясь при этом -4M). Рисунок X.X демонстрирует точечную диаграмму умножения двух 16тиразрядных чисел, используя модифицированный алгоритм Бута.

Рис 2.6

Таблица выбора частичных произведений
Биты множителя	Слагаемое
000	0
001	+Множимое
010	+Множимое
011	+2 x Множимое
100	-2 x Множимое
101	-Множимое
110	-Множимое
111	0

S = 0, если слагаемое положительно (4 верхние строки таблицы)

S = 1, если слагаемое отрицательно (4 нижние строки таблицы)

Множитель делится на пересекающиеся группы по 3 бита и каждая группа декодируется для выбора частичного произведения из таблицы. Каждое частичное произведение сдвинуто по отношению к соседям на 2 позиции. Число частичных произведений сократилось с 16 до 9.

В общем случае, число слагаемых будет [(n+2) / 2], где n - разрядность операнда. Различные слагаемые получаются простым сдвигом множимого. Отрицательные частичные произведения - побитовым дополнением к соответствующему положительному слагаемому и добавлением единицы к результату (бит S на правой стороне рисунка). Число битов сократилось с 256 до 177. Это не чистый выигрыш, т.к. при этом дополнительно усложняется логика выборки частичных произведений.

Рассмотрим теперь метод сокращения затрат на распространение знаков частичных произведений. В общем случае появляется необходимость распространять знаки слагаемых в пределах разрядной сетки. Это увеличивает число бит, необходимых для сложения, так что избавимся от этого, используя алгоритм генерации переносов.

Пусть S₀ - S₇ - знаковые биты полученных нами частичных произведений (знак последнего слагаемого S₉ не играет никакой роли, поскольку оно всегда положительно или 0). Тогда сумма всех знаков может быть записана как

(1)

Используя равенства

и

Выражение (1) после простейших алгебраических преобразований и отбрасывания незначащей части, выходящей за пределы разрядной сетки, можно переписать так:

На этом месте можно остановится, и записать алгоритм генерации знака следующим образом:

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

- Добавить «1» восемнадцатым разрядом каждому частичному произведению.

- Добавить 1 в битовую колонку 17.

Несмотря на значительное уменьшение общего числа бит, число сумматоров уменьшится ненамного. Это происходит из-за увеличившегося числа бит в семнадцатой колонке (10 вместо 9). Для того, чтобы получить наиболее экономичное решение, используем модифицированный алгоритм генерации знака. Преобразуем выражение:

Последний член этого выражения принимает значения из множества {3,4} в зависимости от значения . Т.е. при , он равен «100» или «», а при , значение его равно «».

Распространение переноса сведено к добавлению единиц и знаков частичных произведений. На рисунке 2.7 - пример работающей схемы Бута:



Множитель = 63669₁₀ = 1111100010110101

Множимое (М) = 40119₁₀ = 1001110010110111

Рис 2.7

2.4 Дерево Уоллеса

Как уже было рассмотрено, существует множество различных архитектур умножителей, т.к. полученные на выходе схемы Бута частичные произведения можно суммировать по-разному. Классические способы (итеративный, линейный) с относительно медленны. Одним из наиболее эффективных их известных им замен является дерево Уоллеса.

Архитектура дерева Уоллеса позволяет складывать биты разных разрядов частичных произведений одновременно. Это делается так: на каждом шаге мы уменьшаем количество слагаемых с n до 2n/3 с помощью сумматоров с запоминанием переноса (полных сумматоров). Эта процедура рекурсивно повторяется до тех пор, пока не останется два слагаемых. Пример схемы, уменьшающей число операндов с трех до двух можно видеть на рисунке 2.8



CSA - Carry save adder, полный сумматор.

Рис. 2.8

Рассмотрим общую идею подробнее:

1) Возьмем любой «срез» суммы частичных произведений шириной в 1 бит. Приплюсуем к нему биты, получившиеся на выходе предыдущей колонки (переносы). Пусть общее число битов n.

2) Разложим n как n=3k₀+l₀, где 0<=l₀<=2. На первом шаге каждый из k₀ триплетов сжимается полным сумматором до двух значений - сумма/перенос. Переносы приплюсуются к битам следующей колонки, всего же осталось 2k₀+l₀ бит. Их можно разложить как 2k₀+l₀ = 3k₁+l₁, где 0<=l₁=2, а затем сжать триплеты полными сумматорами.

3) Продолжаем процедуру рекурсивно до тех пор, пока не останется два значения.

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

Номера бит (младшие биты имеют меньшие номера)	7	6	5	4	3	2	1	0
Общее число бит (с учетом переносов из предыдущего разряда)	4+2	5+1	3+1	4	2	3	1	2
Количество переносов в следующий разряд	3	3	2	2	1	1	0	0
Количество требуемых сумматоров 1	2+	2+	1+	1+		1	0	0
Количество бит на выходе	2	2	2	2	2	1	1	2

¹ - дробь означает полусумматор.

2.5 Сумматор с предвычислением переносов

Рассмотрим классическое каскадное суммирование двух чисел. Сложение двух бит в разряде может привести к формированию переноса. В любом случае мы не можем перейти к суммированию следующего разряда, не получив значения переноса в текущем. Это приводит к тому, что перенос «путешествует» через все разряды. Как результат, финальная сумма и перенос будут доступны после значительной задержки. Для схемы на рисунке 2.9, значение бита суммы в самом старшем разряде будет доступно после 2(N-1) +1 значений задержек срабатывания вентилей., где N - число бит операндов. Финальный перенос будет доступен через 2N значений задержек срабатывания вентилей Эта задержка добавляется ко всем остальным задержкам, связанным с межсоединениями.



Рис 2.9

Недостаток каскадного сложения в том, что работа его становится чересчур медленной в случае сложения операндов большой разрядности. Например, для 32х разрядного сумматора, который используется в данной дипломной работе, эта задержка составит около 63 ns, если время срабатывания логического элемента будет 1 ns, что приведет к тому, что значение максимальной частоты, на которой будет работать этот сумматор, составит всего лишь около 16MHz! Эту проблему решает сумматор с предвычислением переносов, вычисляющий переносы в процессе, основываясь на входных операндах. Общая идея такова - перенос из разряда формируется в двух случаях: когда оба входных бита операндов a_i и b_i равны 1, или когда один из них 1, и перенос из предыдущего разряда также 1. Следовательно, можно записать:

Произведем замену обозначений:

;

Заметим, что G и P зависят только от бит операндов, и не зависят от значения переноса из предыдущего разряда. Если нужно вычислить значение переноса в конкретном разряде, не нужно ждать, пока перенос пройдет все предыдущие разряды. Рассмотрим на примере 4х битного сумматора.

Обратите внимание, что C₄, выходной бит переноса, будет доступен после трех задержек. Бит суммы вычисляется следующим образом:

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

В реализации сумматор с предвычислением переносов выгодно разбить на два блока: полный сумматор, генерирующий дополнительно сигналы P и G, и логику (схема ускоренного переноса), вычисляющую переносы, исходя из подаваемых ей на входы сигналов P, G, C₀. Построим на их базе 4-битный сумматор.



Рис 2.10 4х битный сумматор

Недостаток сумматора с предвычислением переносов в том, что логика схемы ускоренного переноса становится слишком сложной для случая более 4 бит. По этой причине используют иерархическую структуру при построении сумматоров разрядностью более 4х бит. Пример для сумматора разрядностью 16 бит на рисунке 2.11

Рис 2.11 16-ти битный сумматор

3. Технологический процесс монтажа печатной платы устройства БПФ на базе специализированного микропроцессора

3.1 Введение

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

В настоящее время при конструировании радиоэлектронной аппаратуры используется единая система технологической подготовки. Эта система предусматривает широкое применение прогрессивных технологий с использованием специальных средств технологического оснащения.

Вообще весь процесс сборки и монтажа печатной платы, если его рассмотреть упрощенно, можно разделить на несколько циклов, каждый из которых содержит в себе несколько операций:

Заготовительно-подготовительные операции;

Сборочно-монтажные операции;

Регулировочные и настроечные операции;

Контрольно-проверочные операции;

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

Рассмотрим процесс монтажа печатной платы со специализированным микропроцессором, описываемым в данном проекте.

3.2 Монтаж навесных компонентов на печатных платах

Основная часть современной радиоэлектронной аппаратуры состоит из навесных компонентов, таких как: интегральные микросхемы, полупроводниковые дискретные элементы (диоды, транзисторы и т.д.). Затем эти навесные компоненты устанавливаются на основания в виде печатных плат. Монтаж компонентов с контактными площадками платы может осуществляться с применением следующих методов микроконтактирования:

Сварка; Пайка; Накрутка; Монтаж с использованием электропроводящих клеев.

В настоящее время при монтаже компонентов на печатную плату особенно широко применяется пайка. Это объясняется особенностями данного способа монтажа навесных элементов. Основные особенности состоят в следующем:

Пайка позволяет исключить повреждения полупроводниковых приборов (в частности разрушение от влияния высокой температуры), поскольку температуру плавления припоя можно выбрать довольно низкую.

Пайка обеспечивает довольно хорошую ремонтопригодность радиоэлектронной аппаратуры.

Большая площадь пайки обеспечивает с одной стороны малое переходное сопротивление, с другой - механическую устойчивость.

3.2.1 Основные методы пайки

В настоящее время существует большое разнообразие методов пайки. Но из всего многообразия методов можно выделить следующие, так называемые основные методы пайки, т.е., которые используются чаще всего:

пайка погружением в расплавленный припой;

- пайка волной припоя;

- пайка групповым паяльником;

- дозированная пайка;

- пайка параллельными электродами;

- паро-фазная пайка.

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

Рассмотрим эти методы более подробно:

- Пайка погружением в расплавленный припой:

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

- Пайка волной припоя.

Сущность метода заключается в пропускании печатной платы через гребень свободно проливающегося из щелевого сопла расплавленного припоя. Часто используют еще и дополнительную волну, наряду с основной. Это позволяет провести более качественную пайку, особенно в отношении компонентов поверхностного монтажа. Благодаря своим преимуществам (высокая производительность, относительно слабое термическое воздействие как на полупроводниковые приборы, так и на изделие вообще, высокое качество паяных соединений и т.д.) этот метод получил наиболее широкое распространение в радиоэлектронной промышленности.

- Пайка групповым паяльником.

Этот способ является довольно эффективным с точки зрения повышения производительности процесса пайки планарных видов изделий электронной техники. При таком способе один или два паяльника паяют сразу все выводы изделия. Кроме того, этот метод позволяет получить паяные соединения, которые по внешнему виду и по физическим свойствам никак не отличаются от соединений паянных вручную. Производительность процесса составляет 250-300 соединений в минуту. Высокое качество пайки достигается при одновременной пайке 7-8 выводов одним паяльником. Увеличение числа одновременно паяемых выводов до 12...20 ведет к снижению качества паяных соединений. Это происходит потому, что даже у одного корпуса выводы имеют различную толщину и, вследствие этого, по-разному прилегают к паяльнику и имеют разный нагрев.

- Дозированная пайка

Это механический способ пайки, с использованием обычного миниатюрного паяльника. Паяльник закреплен на устройстве, которое обеспечивает его механическую подачу. Это устройство называется механизмом подачи. При движении вниз, паяльник расплавляет кусок проволочного припоя, который подается на определенную длину. Благодаря этому на жале паяльника оказывается именно та доза припоя, которая и является необходимой для пайки одного паяного соединения. Поскольку за один такт времени паяльник паяет всего одно соединение, то производительность этого метода оказывается несколько ниже, чем при использовании способа групповой пайки.

- Пайка параллельными электродами

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

- Паро-фазная пайка (для поверхностного монтажа).

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

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

В качестве инструмента для пайки соединений при монтаже РЭА как правило применяют электрические паяльники непрерывного действия, нагревательный элемент которых представляет собой спираль из нихромовой проволоки, охватывающей медный стержень паяльника. Паяльник должен обеспечивать интенсивный подвод тепла к месту пайки. Он должен быстро нагреваться (время нагрева 1.5 - 2 мин.), иметь при достаточной мощности небольшую массу, быть хорошо отбалансированным, рукоятка во время работы паяльника не должна нагреваться. Обгоревший рабочий стержень должен заменяться легко, без разборки паяльника.

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

3.3 Выбор варианта монтажа

Развитием монтажно-сборочных работ на печатной плате является переход от монтажа компонентов с выводами к поверхностному монтажу безвыводных компонентов в микрокорпусах или компонентов с планарными выводами. Его преимущества по сравнению с традиционным методом сводятся к следующим:

Конструкционные:

- увеличение функциональной сложности на единицу площади (меньшие габариты микросборок);

- уменьшение размера конечного изделия (благодаря уменьшению размеров микросборок);

- улучшение частотных характеристик (вследствие уменьшения длины сигнальных шин);

- повышение помехозащищенности от электромагнитных, в частности радиочастотных, помех (из за уменьшения длины сигнальных шин);

Технологические:

- возможен полностью автоматизированный процесс сборки и монтажа;

- технология поверхностного монтажа компонентов (ПМК) проще поддается автоматизации, чем традиционная (компоненты разработаны с учетом возможности автоматизации сборки и монтажа на поверхность плат, что гораздо легче, чем в отверстия);

- повышение эффективности использования производственных площадей (на одной и той же площади с помощью ПМК можно изготовить больше изделий, чем при обычном монтаже);

- Снижение капитальных затрат;

- Снижение затрат на материалы (особенно в будущих изделиях);

- Уменьшение трудовых затрат (преимущественно из-за уменьшения объема ремонтных работ);

- Не требуется предварительной подготовки компонентов и соответствующего оборудования.

Преимущества, связанные с повышением показателей качества:

- улучшение качества пайки (исключение перемычек припоя);

- повышение надежности размещения компонентов на плате (переменные технологические факторы в ПМК контролируются);

- уменьшение количества слоев при том же самом уровне функциональной сложности (отказ от применения металлизированных сквозных отверстий существенно увеличивает площадь, отводимую под компоненты и трассировку устройств);

- уменьшение количества металлизированных отверстий, каждое из которых служит потенциальным источником дефектов.

Но наряду с преимуществами ПМК приходится решать ряд проблем связанных с его недостатками, например:

- затруднен отвод тепла (изделия ПМК требуют большего отвода тепла);

- необходимость обеспечения копланарности для компонентов на платах (особенно крупногабаритных компонентов);

- сложность выполнения ремонтных работ (при простоте демонтажа большинства чипов компонентов существуют трудности монтажа некоторых из них).

Преимущества ПМК перевешивают ее недостатки и в будущем проблемы, связанные с указанными недостатками ПМК, могут быть частично или полностью решены. До выбора оборудования и начала производства следует провести научно исследовательскую работу для решения основных проблем. Проведение этой работы требует времени однако это в конечном итоге себя оправдывает (из за уменьшения потерь при освоении ПМК).

Существует 3 основных варианта реализации поверхностного монтажа:

- поверхностный монтаж на плате (односторонний или двухсторонний);

- смешанно-разнесенный вариант, когда традиционные компоненты размещают на лицевой стороне платы, а простые компоненты для поверхностного монтажа -- на обратной;

- смешанный монтаж, например на лицевой стороне платы и поверхностный на обратной (когда традиционные компоненты и сложные компоненты для поверхностного монтажа размещают на лицевой стороне платы, а простые поверхностно монтируемые компоненты на обратной стороне платы).

.

Рис. 2.1

Чисто поверхностный монтаж - все компоненты устанавливаются на поверхность платы (Рис. 2.1,а). Компоненты могут монтироваться на одной или обеих сторонах платы. Возможна одноступенчатая (одновременная) пайка всех компонентов. Смешанно-разнесенный вариант монтажа.- компоненты для поверхностного монтажа размещают с одной стороны платы, а традиционные - с другой (Рис. 2.1,б). Смешанный монтаж традиционных и устанавливаемых на поверхность компонентов - возможны любые комбинации тех и других компонентов с одной или двух сторон платы, но это требует многоступенчатой пайки (расплавлением дозированного припоя, волной и, возможно, ручной).

2.4 Разработка технологического процесса сборки и монтажа печатной платы устройства БПФ

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

В данной работе разработка технологического процесса монтажа приведена с целью определения наиболее рационального способа изготовления устройства с учетом полного использования технических возможностей данного производства при наименьших затратах труда. За основу разрабатываемого технологического процесса был взят типовой процесс монтажа печатной платы на экспериментальном производстве.

2.4.1 Выбор флюса

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

некоррозионногенные;

слабокоррозионногенные;

коррозионногенные.

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

Марка 1	Состав 2	Область применения 3
КСП	Сосновая канифоль 60-90%, спирт 10-40%.	Пайка и лужение деталей и проводников в изделии специального назначения.
ФКТ	Сосновая канифоль 10-40%, спирт 89-59%, тетрабром остальное.	Пайка и лужение контактных соединений и поверхностей в изделии специального назначения.
ЛТИ120	Сосновая канифоль 15-30%, спирт 76-68% деэтиламин остальное.	Пайка и лужение деталей и проводников в изделиях широкого применения.
ФДГ	Деэтиламин 4-6% глицерин остальное.	Групповая пайка деталей, оплавление после гальванического лужения.
ФЦА	Хлористый цинк 45%, хлористый аммоний 9%, вода остальное.	Предварительное лужение поверхностей при условии полного удаления флюса.

Принимая во внимание простоту изготовления и то, что изделие является специальным, выбираем флюс КСП.

3.4.2 Выбор припоя

При монтаже в качестве припоев используют различные сплавы цветных металлов, в зависимости от состава имеющие разную температуру плавления. Поэтому припои подразделяются на две группы:

1. Мягкие припои. (Состав: свинец, олово, сурьма; имеют температуру плавления ниже 350С; обладают сравнительно невысокой механической прочностью).

2. Твердые припои. (Состав: медь, цинк, серебро; температура плавления - 700 - 900С, высокая механическая прочность).

При выборе припоя к нему должны предъявляться определенные конструктивные и технологические требования:

- высокие электро и теплопроводность;

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

- коррозионная стойкость;

- герметичность;

- жидкотекучесть при температуре пайки;

- хорошее смачивание основного металла;

- подходящие для данной технологии и компонентов РЭА температура плавления и температурный интервал кристаллизации.

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

Марка припоя.	Состав %.	Тпл, оС	Применение.
ПОС-18	Олово 17-18 %, сурьма 2-2.5 %, свинец остальное.	277	Пайка деталей неответственного назначения.
ПОС-ЗО	Олово 29-30 %, сурьма 1.5-2 %, свинец остальное.	156	Лужение и пайка радиоприборов из меди и её сплавов, пайка токопроводящих деталей.
ПОС-40	Олово 39-40 %, сурьма 1.5-2 %, свинец остальное.	235	Лужение и пайка монтажных проводов, наконечников, кабелей и лепестков.
ПОС-61	Олово 59-61 %, сурьма 0.8 %, свинец остальное.	190	Пайка деталей не допускающих высокого нагрева в зоне пайки, ответственная электромонтажная пайка.

Как видно из таблицы, припой марки ПОС-61 имеет сравнительно низкую температуру плавления (190С) и сравнительно высокий предел прочности на растяжение (механическая прочность припоев повышается при увеличении содержания в них олова). Поэтому, так как в данном технологическом процессе монтажа используются элементы, не допускающие перегрева, и, кроме того, необходимо обеспечить еще и надежное крепление элементов, то при монтаже будем применять припой ПОС-61 ГОСТ 1499-70.

3.4.3 Выбор очистительных жидкостей

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

...