Е. Погрешности при выполнении преобразований.
Вопросы анализа погрешностей фурье-процессоров и других упоминавшихся нами устройств и принятия мер для сведения к минимуму возникающих погрешностей — одни из главных в рассматриваемой области техники.
Приходится иметь дело с погрешностями следующих видов. Появляются ошибки при дискретизации непрерывных величин, если не соблюдаются условия, определяемые теоремой Котельникова. При ограничении представления функций рядом Фурье с конечным числом членов получается лишь приближенная аппроксимация функций. Погрешности возникают и при ограничениях спектра, когда производятся интегральные преобразования. Погрешности появляются и в связи с тем, что практически ограничена точность квантования сигналов при цифровой их обработке. Точность вычисления коэффициентов Фурье уменьшается, если временная дискретизация производится неравномерно. Точность вычисления спектра методом дискретного преобразования Фурье уменьшается и в том случае, если пропускаются некоторые отсчеты ординат процесса.
При реализации цифровых методов выполнения преобразований Фурье появляются ошибки из-за округления или усечения чисел, о которых было рассказано нами раньше (раздел Б в § 2). Было отмечено, что ошибки округления равносильны воздействию внутренних шумов. Принимаются меры к тому, чтобы по возможности уменьшить и эти погрешности.
Приведем следующий пример. В работе [44] описан основанный на использовании теории матричной факторизации метод анализа погрешностей вычисления спектральных векторов при выполнении БПФ. В результате проведенного анализа определены матрицы погрешностей и показана возможность уменьшения погрешностей вычислений путем оптимизации процедуры квантования весовых коэффициентов.
Существуют различные подходы к оценке точности аппаратной реализации быстрого преобразования Фурье. Один из них описан в статье [224]. Автор ее пишет о том, что "практическое использование спецпроцессоров с короткой разрядной сеткой (24, 16 и менее разрядов) в задачах цифровой обработки сигналов и изображений, особенно в тех случаях, когда результаты выполненного преобразования являются исходными данными для новых вычислений, производимых с помощью спецпроцессора, требуют достаточно строгих оценок дисперсии выходной погрешности и, соответственно, выходного отношения сигнал — шум". В статье описана предложенная методика расчета оценки верхней границы средней погрешности алгоритмов БПФ. Применения этой методики иллюстрируются примерами, относящимися к алгоритмам выполнения БПФ с прореживанием по частоте и по времени. Рассмотрены случаи представления чисел с фиксированной
и с плавающей запятой. Оценки, полученные для прореживания по частоте, сравнены с тем, что дало экспериментальное исследование точности серийно выпускаемого в СССР спецпроцессора Фурье Выяснено, что те и другие данные хорошо согласуются. Отметим указанный в работе [81] подход к определению коэффициентов Фурье периодического сигнала с заданной погрешностью.
В гл- IV было показано, в какой мере удовлетворительно аппроксимируются различные сигналы, когда используются тригонометрические функции и функции Уолша. При соответствующем виде исходных сигналов возможно точное их представление конечным количеством функций Уолша или Хаара, что также было показано в гл. IV при рассмотрении методов анализа и синтеза логических функций.
Если иметь в виду ошибки округления, то преимуществом теоретико-числовых и полиномиальных преобразований является то, что при их выполнении они вообще исключаются. В.Г. Лабунец особо отмечает в книге [138] преимущество преобразования Фурье — Галуа перед преобразованием Фурье при вычислении свертки, заключающееся в том, что "эффекты усечения и округления, неизбежно ведущие к внутренним шумам, исключаются, так как все вычисления в -арифметике абсолютно точные". И. и .К. Труонг, говоря о преобразовании над конечным полем где является числом Мерсенна, тоже обращают внимание на то, что "такие операции, как фильтрация и свертка, могут выполняться с помощью такого преобразования комплексных чисел без ошибок округления" [225].
Кроме специфических погрешностей, появляющихся при выполнении преобразований Фурье и других ортогональных преобразований, при цифровой фильтрации, выполнении операций корреляции и свертки для рассматриваемой области приложений возможно возникновение и других погрешностей, являющихся общими для любой цифровой обработки информации. Говоря об этом, имеем в виду ошибки, возникающие в процессе работы микроэлектронных элементов и узлов. С созданием СБИС, в которых на площади тетрадной клетки размещаются десятки тысяч функциональных элементов, и в особенности при создании суперкристаллов ССИС, в которых располагаются миллионы и десятки миллионов субмикронных элементов, одной из главных стала задача обеспечения надежной работы размещенных на них устройств. При выполнении всех функций обработки информации с помощью множества таких миниатюрных элементов нельзя гарантировать безотказную работу каждого из них. Однако при большом количестве элементов, часть которых может быть избыточной, становится возможным использование последних для организации эффективного обнаружения появляющихся ошибок и автоматического их исправления. Применяются методы резервирования и помехоустойчивого кодирования информации. Они используются и при построении фурье-процессоров, устройств, выполняющих преобразования Уолша и Хаара, и при построении других устройств обработки информации, о которых говорилось выше. Метод помехоустойчивого кодирования, предложенный Хэммингом, был описан автором в книге [100]. Другой из методов помехоустойчивого кодирования основан на применении так называемых кодов Рида — Соломона [31, 53]. При применении этих кодов для кодирования и
декодирования информации используется преобразование Ферма. Такое использование преобразования Ферма при вычислении циклических сверток описано в работе [316], в которой говорится о построении СБИС-кристалла, выполняющего функции множительного устройства.
Возникают также задачи оценки точности программ преобразований, например, программы быстрого преобразования Фурье, реализуемой на универсальных ЭВМ [196]. О машинных программах рассматриваемых преобразований будет сказано особо в следующем разделе.