Приложение 1. ПРОГРАММЫ ВЫЧИСЛЕНИЙ НА ЭВМ

Кто вдруг, напившись, одержал победу, Тот только по-латыни изъясняться б стал.

Д.ж. Чосер

Данное приложение содержит ряд оригинальных программ общего назначения, снабженных поэтому большим числом поясняющих комментариев и замечаний, которым предшествует знак «!». При воспроизведении этих программ пользователь может опустить любую строку-комментарий или любую часть строки, расположенную после знака «!». Данные программы написаны на удобочитаемом языке БЕЙСИК и предназначены для пользователей, которые в принципе будут приспосабливать их для собственных нужд. Для этой группы пользователей представляется более простым переход (трансляция) с БЕЙСИКа на язык ФОРТРАН, ПАСКАЛЬ, СИ.

С целью обеспечения наглядности программ была использована нумерация строк, например для нумерации подпрограмм применяются числа, кратные 1000. Таким образом, одним и тем же подпрограммам, используемым в разных программах, могут быть присвоены кодовые признаки в виде порядкового номера строки. Поэтому можно исключить процедуру вызова подпрограммы и связанного с ней списка параметров, однако при этом предполагается, что пользователи, часто использующие одну и ту же подпрограмму, должны применять в составе главной программы набор команд CALL. Для небольшого числа представляемых здесь коротких программ не предусматривается использование команд CALL. Все приведенные программы структурно в явном виде содержат преамбулу, главную программу, используемые данные и подпрограммы. Команды GOTO используются только в тех случаях, когда они обладают приоритетом, а циклы FOR-NEXT выделены в виде блоков по отношению к другим командам. Алгебраические символы, как это принято, выделены курсивом и используются в описаниях массивов (DIM), а также при необходимости подстановки численных значений.

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

Характерные признаки языка.

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

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

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

Если условие не выполняется, то, естественно, С не полагается равным 2, однако также и не приводится к 1/10, нужно непосредственно перейти к выполнению процедуры, реализуемой в строке со следующим порядковым номером.

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

Так как интервалы в языке БЕЙСИК не учитываются, блок циклов FOR-NEXT используется только для наглядности представления и нет необходимости сохранять его при переписывании.

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

Введение в программы

FHTBAS - программа для алгоритма быстрого преобразования Хартли, обеспечивающая определение дпскретного преобразования Фурье и вывод на печать комплексного результата наряду с ДПХ, из которого получается ДПФ. Она приводится в связи с обсуждением в тексте различных подпрограмм.

- частный быстрый алгоритм, представляемый в форме подпрограммы, которая может быть включена в программу общего назначения. Этот алгоритм позволяет определить ДПХ вещественной последовательности. Данная программа представлена в сжатой форме и быстрее осуществляет выполнение ее составных частей, чем путем перехода к подпрограммам в пределах большой подпрограммы. Однако нумерация ее строк продолжает нумерацию строк программы так что при необходимости может быть восстановлена вся структура алгоритма. Для тригонометрических функций и для операции перестановки используются более сложные методы, что увеличивает время счета. Встроенный алгоритм снижает требования к памяти ЭВМ и позволяет получить результаты для больших N. В общем случае применимы методы, используемые для табулированных функций и базирующиеся на работе [О. Випетап. Conversion of FFT’s to Fast Hartley Transforms, SIAM J. Sci. Statist. Comp., 1985 (Переход от БПФ к быстрому преобразованию Хартли)]. Метод перестановки описан Эвансом. Соответствующие программы на языке ФОРТРАН можно найти в работе [Z. Wang. Fast Algorithms for the Discrete W Transform and for the Discrete Fourier Transform, IEEE Trans. Acoustics, Speech and Signal Processing, vol. ASSP 32, pp. 803-816, 1984 (Быстрые алгоритмы для дискретного преобразования Винограда и дискретного преобразования Фурье)] и (в том числе для основания 4) в статье [Н. V. Sorensen, D. L. Jones, S. С. Burrus, М. Т. Heideman. On Computing the Discrete Hartley Transform, IEEE Trans. Acoustics, Speech and Signal Processing, 1985 (О вычислении дискретного преобразования Хартли) в печати].

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

вычисляет обычную свертку Для вычисления обычной взаимной корреляционной функции последовательностей выполняется реверсирование

вычисляет циклическую свертку Для циклической

взаимной корреляционной функции осуществляется реверсирование

выполняет в Компактной форме процедуру свертки путем умножения матриц.

реализует вычисление корреляционной функции.

реализует вычисление циклической корреляционной функции.

осуществляет обращение свертки.

инвертирует вещественную последовательность для получения обратной ее последовательности, которая при выполнении свертки с заданной последовательностью дает

осуществляет обращение корреляционной функции, что дает исходную последовательность при заданной корреляционной функции.

выполняет свертку при операции умножения в области преобразования.

вычисляет корреляционную функцию при операции умножения в области преобразования.

является вариантом ДПХ для основания 4.

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

- версия на языке ФОРТРАН программы написанной на БЕЙСИКе. Переход от программ, написанных на языке к программам на языке ФОРТРАН, оказывается достаточно простым. Этот пример своего рода Розеттский камень. Принципиальное различие для состоит в замене циклов соответствующими циклами FOR-NEXT и в необычной фразеологии языка, например

- версия программы на языке ФОРТРАН, написанная в качестве подпрограммы, входящей в главную программу.

Программа FHTBAS

(см. скан)

(см. скан)

(см. скан)

(см. скан)

Программа FHTSUB

(см. скан)

(см. скан)

(см. скан)

Примечания: а) Подставить числовые значения в строку 9040.

б) Дать описание массива перед входом в подпрограмму.

в) Эта подпрограмма предполагает, что пользователь будет последовательно осуществлять деление на N.

г) За исключением и Р, названия переменных в основном такие же, как в с дополнительной цифрой 9, что позволяет избежать дублирования. Список переменных:

д) Строка 9635 запоминает переменную N. Пользователь может выразить желание начать с упоминания в главной программе того, что так что строка 9090 не завершает выполнения процедуры; тогда строки 9080 и 9100, ответственные за ошибки в упоминании могут быть исключены.

е)    © 1985 The Board of Trustees of the Leland Standford Junior Univ.

Программа FHTPS

(см. скан)

(см. скан)

Примечания, а) Дать описание для N и Р, как это требуется строкой 30.

б) Подпрограмма 1000 формирует последовательность данных, представляющих полосовой шум.

в) Подпрограмма 2000 обеспечивает грубый спектр мощности.

г) Подпрограмма 3000 обеспечивает сглаживание спектра мощности с использованием быстрого и изящного алгоритма биномиального сглаживания. Подобрать степень сглаживания в соответствии с требованием строки 50. При соответствующие коэффициенты сглаживающей последовательности равны при они имеют вид . В подпрограмме вывода данных на терминал коэффициент вида предусматривает значения 4, 16 и т.д., что также обусловливает аннулирование коэффициента 2 в строке 2010 и коэффициента N в подпрограмме 9000.

Программа CONV

(см. скан)

Примечания, а) Подставить числовые значения I, в в строки 110, 130 и 140. Для вывода данных на терминал использовались значения

б) Ввод данных может осуществляться с помощью формулы, а не с использованием оператора например:

или с применением оператора присвоения, в частности:

в) Для взаимной корреляционной функции последовательностей а именно для перепишем строку 1010 в виде

Программа CCONV

(см. скан)

(см. скан)

Примечания: а) Для приведенных данных Требуемые числовые значения должны быть подставлены в строки 50 и 60.

б) Ввод данных (при соответствующем выборе констант - Перев.) может быть осуществлен с помощью оператора DATA по аналогии с программой подпрограмма 1000 иллюстрирует другие методы.

в) Для циклической взаимной корреляционной функции осуществляется реверсирование

Программа MATCON

(см. скан)

Примечания.

а) Подставить численные значения (число элементов последовательностей в строки 30 и 40. В выборке используются

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

Программа ACF

(см. скан)

(см. скан)

Примечание, а) Подставить числовое значение в строки 40 и 60. В примере используется значение

Программа CACF

(см. скан)

(см. скан)

Примечание. Подставить числовое значение для и в строки 30 и 40. В примере используется значение

Программа ICONV

(см. скан)

(см. скан)

Примечания, а) Подставить значения в строки 30, 40, 50 и 60. В этом примере используются значения

б) Данная программа реализует прямой алгоритм «ручного счета», опубликованный в книге R. N. Bracewell. The Fourier Transform and Its Applications, McGraw-Hill, 1965 (P. Брейсуэлл. Преобразование Фурье и его приложения).

Программа RECIP

(см. скан)

(см. скан)

Примечания: а) Подставить значения и в строки 30, 40 и 50. В примере используются значения

б) Данный алгоритм является частным случаем программы когда

Программа ICORR

(см. скан)

(см. скан)

Выборочные результаты вывода данных:

(см. скан)

Примечания, а) Подставить числовые значения в строку 30, а значения строку 20.

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

в) За исключением случая, когда корреляционная функция конечной последовательности (что имеет место в данном примере), последовательности будут иметь бесконечное число элементов.

г) Термин «каузальный», используемый в смысле является важным условием в физике и безусловно выполняемым в вычислительной технике.

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

Программа FHTCONV

(см. скан)

Выборочные результаты вывода данных

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

б) Указать числовое значение переменной Р в строке 30.

в) Подставить числовое значение N в строку 30 и заменить им величину в строке 900.

г) Заменить в строке 150 подпрограмму 4000 подпрограммой 4400, если ни одна из рассматриваемых функций не обладает свойством симметрии; в строке 5020 заменить на

Программа FHTACF

(см. скан)

Выборочные результаты вывода данных для последовательности, содержащей 7 единичных элементов, при

Примечания, а) Записать значений функция в подпрограмме 1000 и дополнить ее нулями до N.

б) Указать числовое значение в строке 40.

в) Подставить числовое значение N в строку 30 и заменить им величину в строке 900.

Программа FHTRX4

(см. скан)

(см. скан)

Примечания, а) Подставить числовые значения в строку 30 и строку 60 так, чтобы число элементов было равно

б) См. обсуждение в гл. 8.

в) Предварительное табулирование тригонометрических функций осуществляется по аналогии с программой FHTSUB.

г)    © 1985 The Board of Trustees of the Leland Stanford Junior Univ.

Программа FASTPERMUTE

(см. скан)

(см. скан)

Примечания: а) Для строки 80 установить значение Р, а для строки 70 - соответствие размерности и величины

б) Описание массива справедливо для для больших N ввести в качестве максимального значения индекса массива.

в) См. обсуждение в гл. 8.

Программа FHTBASFOR

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

Примечания, а) Данная подпрограма предполагает, что пользователь будет последовательно осуществлять деление на N.

б) В данной подпрограмме имена переменных и нумерация строк в основном аналогичны программе FHTSUB.

в) © 1985 The Board of Trustees of the Leland Stanford Junior Univ.