Текст подпрограммы и версий ftw1r_c.zip |
Тексты тестовых примеров tftw1r_c.zip |
Вычисление дискретного преобразавания Уолша вещественного ряда длины, равной степени двух, методом быстрого преобразования Уолша.
Дискретные функции Уолша длины N = 2 M принимают только два значения + 1 и - 1 и определяются как строки матрицы WN размерности N * N, удовлетворяющей следующему pекуppентному соотношению (матрицы Адамара)
| WN / 2 WN / 2 | | 1 1 | WN = | | , W2 = | | , N = 2 m. | WN / 2 - WN / 2 | | 1 - 1 |
кpоме "естественно" (по номеpам стpок) упорядоченной системы функций Уолша WalK ( i ) часто используются системы функций Уолша, расположенных в "двоично - инверсном" порядке - WalKb ( i ) и упорядоченных по "частоте" - WalKS ( i ). При этом:
WalKb ( i ) = Walp(K) ( i ) WalKS ( i ) = Walbg( K ) ( i ) ,
где p (K) - двоичная инверсия числа K длины m:
m-1 m-1
p ( ∑ K t * 2 t ) = ∑ K t * 2m - t - 1 ,
t=0 t=0
g (K) = K ⊕ [K / 2] - Gray - код числа K.
Здесь знак [ ] означает целую часть, а ⊕ - поразрядное циклическое сложение по модулю 2.
Если A - вектоp, определяющий данную дискретную функцию, WN - матрица Адамара, то дискретное преобразование Уолша - вектоp X = WN * A определяет коэффициенты разложения данной функции по системе WalK ( i ).
Коэффициенты разложения по системе WalKb ( i ) получаются переупорядочиванием коэффициентов разложения по системе WalК ( i ) с помощью двоичной инверсии.
Коэффициенты разложения по системе WalKS ( i ) получаются из коэффициентов разложения по системе WalKb ( i ) с помощью GRАУ - пеpестановки.
Соответствующие матрицы WN, WNb и WNS - симметричные и ортогональные, поэтому обратные преобразования совпадают (с точностью до множителя 1. / N) с прямыми.
Для вычисления преобразования Уолша по системе функций WalК ( i ) используется алгоритм, аналогичный алгоритму Кули - Тьюки для быстрого преобразования Фурье.
Описываемая подпрограмма прозволяет вычислить коэффициенты разложения по системе функций Уолша, упорядоченных любым из трех описываемых способов.
Данная подпрограмма подробно описана в [4, стp. 132] под именем WALSH.
1. | N.Ahmed, K.R.Rao, Walsh functions and Hadamard transform. Applications of Walsh functions. Proceeding of Walsh functions simposium, Washington, 1972. |
2. | C.Yen. Walsh functions and Gray code. IEEE Transactions, 1971, EMC - 13, N 3. |
3. | M.Lamquin. Etude de la fast Walsh transform. Revue H.F. 1973, 9, N 1. |
4. | А.Ф.Сысоев, Н.Н.Кирсанова. Алгоритм и подпрограмма для вычисления дискретного преобразования Уолша. Численный анализ на ФОРТРАНе, Изд. МГУ, 1974, вып. 9. |
int ftw1r_c (real *a, integer *n, integer *l)
Параметры
a - | вещественный вектоp длины n; перед началом работы подпрограммы содержит элементы преобразуемого ряда A, по окончании - элементы преобразованного ряда; |
n - | целая степень двух, заданная длина вектоpа a (тип: целый); |
l - | определяет вид преобразования (тип: целый); |
l = 1 - | выполняется преобразование Уолша по системе функций, расположенных в "естественном" порядке; |
l = 2 - | система базисных функций расположена в "двоично - инверсном" порядке; |
l = 3 - | система базисных функций упорядочена по "частоте". |
Версии: нет
Вызываемые подпрограммы: нет
Замечания по использованию
1. |
Подпрограмма ftw1r_c обращается к вспомогательным подпрограммам с именами: ftwwr_c, fti1r_c, ftg1r_c. | |
2. |
Длина преобразуемого ряда должна быть целой степенью двух: n = 2 m, m ≥ 1. | |
3. |
При работе подпрограммы значения параметров n и l сохраняются. | |
4. |
Двумерное преобразование Уолша с матрицей Адамара
Wn порядка n = 2 n
определяется формулой:
F = Wn * f * Wn , где f = { fi j } - преобразуемая, F = { Fi j } - pезультирующая матрицы порядка n * n. Если матрицы f и F расположить в виде одномерных массивов (по стpокам), то F может быть вычислено как одномерное преобразование Уолша вектоpа f длины n2 = 22 n. |
int main(void) { /* Local variables */ static float a[8], b[8]; extern int ftw1r_c(float *, int *, int *); static int i__; static int c__8 = 8; static int c__1 = 1; static int c__3 = 3; for (i__ = 1; i__ <= 8; ++i__) { a[i__ - 1] = (float) i__; /* l1: */ b[i__ - 1] = a[i__ - 1]; } ftw1r_c(a, &c__8, &c__1); ftw1r_c(b, &c__8, &c__3); for (i__ = 1; i__ <= 5; i__ += 4) { printf("\n %16.7e %16.7e %16.7e %16.7e ", a[i__-1], a[i__],a[i__+1], a[i__+2]); } printf("\n "); for (i__ = 1; i__ <= 5; i__ += 4) { printf("\n %16.7e %16.7e %16.7e %16.7e ", b[i__-1], b[i__],b[i__+1], b[i__+2]); } printf("\n "); return 0; } /* main */ Результат: a = ( 36., -4., -8., 0., -16., 0., 0., 0. ) b = ( 36., -16., 0., -8., 0., 0., 0., -4. )