Ж. Программы, используемые при машинной реализации преобразований.

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

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

Это разграничение в общем сохраняется и сейчас, хотя подходы к сравнительной оценке аппаратных и программных средств должны быть иными в связи со следующим. Аппаратные средства строятся сейчас, как правило, на базе микропроцессоров. Микропроцессор же, по самому определению его, представляет собой БИС или СБИС, предназначенную для программно-управляемой обработки данных, или, как говорят по-другому, — представляет собой БИС (СБИС) с программируемой логикой. Таким образом программное управление становится сейчас характерным и для устройств, которые относятся к аппаратным средствам. С другой стороны,

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

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

Проиллюстрируем сказанное на примере построенного в СССР выполняющего БПФ процессора, работающего в качестве периферийного процессора-расширителя для ЭВМ СМ-3 или СМ-4. О работе этого процессора в статье [269] сказано следующее: "Процессор Фурье является устройством конвейерного типа, связанным с оперативной памятью комплекса через блок связи с комплексом (БСК). Обмен данными с комплексом в БСК осуществляется в параллельной форме, на выходе БСК происходит преобразование из параллельной в последовательную форму и обратно. Обработка данных в процессоре Фурье производится в последовательной форме, действительная и мнимая части передаются по двум однопроводным линиям. Процессор Фурье выполняет прямое и обратное дискретное преобразование Фурье. Как отмечено, на основе теоремы о свертке, применив повторное прямое и обратное ДПФ, можно осуществлять нерекурсивную цифровую фильтрацию, вычислять корреляционные функции и производить иные действия.

При спектральном анализе данное устройство по оценке авторов работы [269] "благодаря аппаратной реализации основного алгоритма БПФ и ряда сопутствующих вычислительных и управляющих процедур вычисляет спектральные характеристики на два-три порядка быстрее". Программное обеспечение процессора, в том числе и касающееся работы диагностической системы, здесь такое: "Программное обеспечение описываемого процессора включает в свой состав универсальный драйвер (позволяющий настраивать процессор на выполнение широкого набора алгоритмов и инициировать обработку с его помощью в различных режимах) и библиотеку модулей, обеспечивающих доступ к ресурсам специализированного процессора из программ, написанных на языке ФОРТРАН. Существующее программное обеспечение работает под управлением операционной системы РАФОС. Особые требования к процессору Фурье по обеспечению продолжительной высокопроизводительной работы в режиме реального времени в системах обработки научной информации и АСУ ТП потребовали создания системы программно-аппаратного диагностирования. В последнюю входят программная модель тракта обработки данных, программа формирования эталонных массивов и исходных данных, управляющая программа и программа сравнения. Программная модель позволяет получать результаты обработки эталонных массивов как на выходе специализированных процессоров, так и в достаточном количестве точек в заданные моменты времени. Аппаратная поддержка диагностической системы состоит из

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

Приведенный пример взаимодействия программных и аппаратных средств является показательным. Можно привести и ряд других примеров совместной работы специализированного процессора Фурье и ЭВМ. Так, согласно [181], при построении одноплатного матричного процессора, выполняющего прямое и обратное БПФ, предназначенного для настольных систем, "пришлось создать специальную конструкцию платы и схему тесного сопряжения матричного процессора с компьютером, позволившую упростить относительно сложную задачу программирования взаимодействия платы матричного процессора с ведущим микрокомпьютером. Матричный процессор с его ЗУ отображен на адресное пространство ведущей ЭВМ". Кроме алгоритма прямого и обратного преобразований Фурье предусмотрена здесь реализация алгоритмов определения спектральной плотности мощности сигналов и взвешивания окном Хзмминга, а при необходимости и окнами Кайзера, Бартлета и Хзмминга, о которых у нас упоминалось в гл. III.

В качестве еще одного примера сошлемся на приведенные в статье [375] сведения о разработке системы, состоящей из мини ЭВМ, модуля сбора данных и специального блока для вычисления коэффициентов БПФ. Здесь программа на ЭВМ управляет АЦП, преобразующим аналоговые сигналы, поступающие на вход системы, и цифровые сигналы передаются в память ЭВМ. Другая программа управляет блоком вычисления коэффициентов БПФ и организует выполнение БПФ для данных, находящихся в памяти ЭВМ. В статье [426] рассмотрена работа 600 канального мультиплексора телекоммуникационной службы, предназначенного для переключений системы частотного и временного кодирования; при работе мультиплексора используется процессор, выполняющий 64-точечное БПФ.

Можно привести примеры использования программных методов и при микропроцессорной реализации других алгоритмов преобразований, кроме алгоритма БПФ. Так, согласно данным статьи [418], в которой говорится о выполнении алгоритма Винограда с помощью микропроцессора общего назначения, приведены сведения о разработке блока, обеспечивающего оптимизированное программное управление процедурой преобразования.

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

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

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

В книге [98], посвященной теории вычислений преобразования Фурье, приведена библиотека программ, предназначенных для решения различных задач спектрального и корреляционного анализа. В этой библиотеке имеются особые подпрограммы, служащие для программного обеспечения выполнения следующих действий: вычисления необходимых элементов матрицы, используемой в алгоритме БПФ; быстрого упорядочивания коэффициентов ДПФ, вычисляемых методом БПФ; вычисления ДПФ комплексного и действительного сигналов методом БПФ; вычисления многомерного ДПФ действительного и комплексного сигналов методом БПФ; оптимального интегрирования быстроосциллирующих функций (алгоритм БПФ используется для реализации оптимальной по точности квадратурной формулы при вычислении интегралов соответствующего вида); приближенного вычисления преобразования Фурье, тоже методом БПФ, необходимость в котором возникает в цифровом спектральном анализе, цифровом моделировании фильтров, распознавании образов, анализе речевых сигналов и в других областях; вычисления оценки автокорреляционной функции косвенным методом с помощью алгоритма БПФ; вычисления оценки автокорреляционной функции методом секционирования, тоже с помощью алгоритма БПФ; вычисления оценки взаимной корреляционной функции с помощью алгоритма БПФ; вычисления оценок спектральной плотности и корреляционной функции стационарного случайного процесса с помощью алгоритма БПФ; вычисления первичной оценки взаимной спектральной плотности стационарных случайных процессов с помощью алгоритма БПФ. Кроме того, в указанной библиотеке программ имеется программа выявления скрытых периодичностей, также выполняемая с применением БПФ. При реализации этой программы оказывается возможным разделение сигнала, состоящего из периодической составляющей и случайного остатка, на составные части.

При описании в статье [260] упоминавшейся нами многопроцессорной ЭВМ ПС-2000 указано на то, что первая очередь созданного для нее пакета прикладных программ обработки данных состоит из 7 процедур и 47 подпрограмм типа БПФ, свертки, расчета корреляционных функций и т.п.

В книге [192] приведены следующие программы: программа для машинного проектирования БИХ-фильтров; машинная программа, позволяющая автоматически проектировать многополосные КИХ-фильгры и выполнять преобразование Гильберта; машинная программа, которая вычисляет частотную характеристику цифрового фильтра при заданной точности (числе битов) представления коэффициентов фильтра; две машинные программы вычисления частотной характеристики, позволяющие оценивать влияние конечной длины слова представления коэффициентов фильтра на амплитудно-частотную характеристику; программа измерения спектра мощности на основе усреднения модифицированных периодограмм;

программа, формирующая карту загрузки памяти ПЗУ при реализации цифрового фильтра; программа эвристической (о том, что представляют собой эвристики, рассказано в книге [99]) оптимизации объединения полюсов и нулей и масштабирования для уменьшения ошибки округления. В приложении к книге [221] приведена программа расчета разнообразных оптимальных (минимаксных — понятие минимакса тоже пояснено в книге [99]) КИХ-фильтров, в том числе фильтров нижних и верхних частот, полосовых, режекторных, а также дифференциаторов и преобразователей Гильберта. Даны примеры, иллюстрирующие применение этой программы. Приведена подпрограмма вычисления модифицированной функции Бесселя, используемой при машинной реализации универсального семейства окон Кайзера.

В работе [78] представлен пакет программ для обобщенного спектрального анализа. Здесь описаны векторно-матричные процедуры быстрых дискретных ортогональных преобразований и приведены соответствующие программы реализации ортогональных преобразований в базисах дискретных экспоненциальных функций, функций Виленкина — Крестенсона, функций Уолша, функций Хаара и функций усеченного преобразования Адамара. Приложены программы формирования исходных матриц преобразования и программы переупорядочения для различных базисов.

В опубликованной в 1985 г. работе [61] сказано о том, что "к настоящему времени создано уже свыше 70 различных по структуре вариантов программного обеспечения обработки изображений: от простейших библиотек подпрограмм на фортране и/или ассемблере, к которым пользователь должен обращаться из собственной программы, до автономных диалоговых программных комплексов, включающих свой монитор, редактор текстов, синтаксический анализатор, интерпретатор команд и программы управления ресурсами памяти и ввода — вывода данных".

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

Проводятся исследования, направленные на усовершенствование существующих и создание новых, все более совершенных программ. Один из основных вопросов, который здесь подлежал решению, следующий. Раньше ЭВМ работали, как правило, с последовательной обработкой данных, с переходом же к параллельным ЭВМ приходится иметь дело с параллельной обработкой информации. Насколько приемлемы ранее разработанные алгоритмы обработки для ЭВМ и вычислительных комплексов нового типа? Проведенный анализ показал, что в этой части не требуется изменений, так как первоначально разработанным алгоритмам присущ параллелизм. Упоминая об этом и затем возвращаясь к этому вопросу, авторы книги [272] пишут: "... алгоритмам, которые вначале были разработаны для последовательных компьютеров, присущ параллелизм, и они могут быть реализованы без изменений на параллельных вычислительных машинах".

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

рассмотреть структуру управления. Например, автор работы [11], ссылаясь на статью [397], делает следующее заключение: "при компиляции фортрановских программ часто создаются циклы, даже если количество итераций невелико. При этом необходимость в управлении выполнением цикла приводит к значительному увеличению времени счета. Чтобы сократить эти потерт, можно воспользоваться методом "раскрутки" циклов и тем самым за счет увеличения длины программы добиться существенного повышения быстродействия. Применение подобных приемов в случае серийных ИС обработки сигналов позволяет резко уменьшить время счета таких типовых задач, как БПФ". Изучаются вопросы подготовки данных, предназначенных для обработки специализированными фурье-процессорами [419].

Существует много различных языков программирования. Их описанию и примерам их использования при составлении программ посвящена специальная литература (например, программирование на языке Фортран рассмотрено в книге [153]). Почти все упоминавшиеся нами до сих пор программы написаны на языках Фортран или На Фортране написаны и приведенные в книге [304] программы выполнения быстрых преобразований Уолша и Хаара. Но используются и другие языки программирования, каждому из которых в отдельных случаях отдается предпочтение. Упомянем о некоторых из них. В статье [181] говорится о реализации алгоритма БПФ в виде одной строки на языках Бейсик, Паскаль или на языке HPL. В работе [229], посвященной реализации на универсальной ЭВМ алгоритмов быстрых преобразований Фурье и Уолша, отмечено, что программы двоичной инверсии на языках высокого уровня Алгол, Фортран требуют гораздо большего количества команд, чем это нужно при программировании в кодах машины, и что увеличение количества команд приводит к уменьшению скорости счета. Авторы работы [2], в которой рассмотрено числовое преобразование Ферма, приводят результаты моделирования, полученные при выполнении программы, записанной на языке Ассемблера для ЭВМ IBM 370.

В разделе "Массивы как смесь последовательных и параллельных подходов" книги [272] говорится о подходе, обеспечивающем возможность разделения параллельного и последовательного доступов, имеющихся в запоминающих устройствах процессорной матрицы, который зависит, однако, от типа ЭВМ. Сказано о том, что примеры такого подхода можно обнаружить во всех языках, которые были предложены или реализованы для ЭВМ (к числу их относятся языки CFD, CLYPNIR, ACTUS. Упомянут особо язык VECTRAN, представляющий собой экспериментальное расширение языка IBM - Фортран для обработки массивов и векторов.

В работе [332], в которой сообщено о применении -разрядного микропроцессора для решения задач на основе использования БПФ, указано на то, что работа микропроцессора программируется на языке

В статье [77] описано проектирование систем программного обеспечения автоматической обработки изображений с применением языка программирования Бейсик. В статье [61] говорится о том, что переход при цифровой обработке изображений к таким языкам общего назначения как Паскаль, ПЛ/1, позволит "разработать хорошо структурированные программы, которые легко читаются, проверяются, модифицируются и

отлаживаются, а также относительно просто переносятся на различные ЭВМ и операционные системы, где предусмотрены трансляторы для этих языков". Упомянуты также языки программирования PIXAL и ПАСКАЛЬ PL, получаемые, как оговорено, чаще всего путем расширения выразительных возможностей обычных языков общего назначения (Алгола для PIXAL, Паскаля для Паскаля PL). Автор указанной статьи высказывает свои соображения и по поводу появления нового общедоступного стандартного языка Ада. Сказано о том, что им в дальнейшем обязательно будут пользоваться разработчики прикладного программирования.

В заключение еще раз повторим, что большая часть опубликованных программ, используемых при преобразованиях Фурье, Уолша, Хаара и при других рассматриваемых нами преобразованиях, была написана на языках Фортран и ПЛ/1. Приведенные выше сведения должны дать представление о состоянии разработки и использования в данной области различных языков программирования.