4.4.2. Реализация путем применения переменных состояния

Если воспользоваться массивом переменных состояния, то можно получить реализацию, отличающуюся от реализации прямым методом, согласно (4.3). Этот альтернативный метод реализации рекурсивного алгоритма может обеспечить уменьшение требуемого объема памяти ЦВМ. Массив переменных состояния обозначим Это отражено в соотношении

Чтобы проследить, каким образом введение этого массива сказывается на реализации, сделаем отождествления

Уравнения (4.56) и (4.57) предполагают выполнение двух операций. Во-первых, массив В воздействует рекурсивным образом на массив в результате чего получается массив переменных состояния во-вторых, массив А воздействует на массив в результате чего вычисляется выходной массив

Уравнение (4.56) дает (принимается, что операции нормализации, согласно (4.3), уже выполнены)

Рекурсивные уравнения

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

Уравнение (4.60) описывает эволюцию массива переменных состояния. Выходной массив формируется из массива переменных состояния:

Фиг. 4.32. (см. скан) Реализация двумерного рекурсивного фильтра с использованием промежуточного массива переменных состояния.

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

Замечания по реализации

Фиг. 4.32 может навести на мысль о том, что введенный дополнительный двумерный массив требует большего объема памяти ЦВМ, чем алгоритм фиг. 4.33, являющийся прямой реализацией (4.3). Это соответствовало бы истине, если бы все массивы, используемые при вычислениях, хранились в главном

Фиг. 4.33. Прямая реализация двумерного рекурсивного фильтра.

запоминающем устройстве машины. Однако в случае обработки больших двумерных массивов это очень часто оказывается непрактичным. Более обычная ситуация при использовании больших массивов данных — хранение двумерных данных во внешнем накопителе большой емкости, откуда они переписываются в память ЦВМ для обработки одного столбца или одной строки за один раз. Чтобы проиллюстрировать сказанное, рассмотрим случай переноса данных по одному столбцу. При этом допущении фиг. 4.32 показывает, что для получения одного столбца выходных данных следует в качестве обрабатываемого массива использовать один столбец входных данных и производить обновление массива переменных состояния данными этого столбца, как это следует из (4.60). Тогда столбец выходных данных вычисляется путем обработки массива № согласно (4.61). При использовании этого метода число столбцов массива которые должны храниться в главном машины в какой-то момент времени, не превышает или Фиг. 4.33 показывает, что в случае прямой реализации алгоритма в главном требуется одновременно хранить столбцов данных. Когда главное процессора имеет ограниченную емкость, этот фактор может оказаться существенным.

Литература

(см. скан)

(см. скан)