Текст подпрограммы и версий ( Фортран )
ftw1r.zip 		Тексты тестовых примеров ( Фортран )
tftw1r.zip
Текст подпрограммы и версий ( Си )
ftw1r_c.zip 		Тексты тестовых примеров ( Си )
tftw1r_c.zip
Текст подпрограммы и версий ( Паскаль )
ftw1r_p.zip 		Тексты тестовых примеров ( Паскаль )
tftw1r_p.zip

Подпрограмма:  FTW1R

Назначение

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

Математическое описание

Дискретные функции Уолша длины  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.

Использование 

    SUBROUTINE  FTW1R (A, N, L) 
   Параметры
A - вещественный вектоp длины  N; перед началом работы подпрограммы содержит элементы преобразуемого ряда  A, по окончании - элементы преобразованного ряда;
N - целая степень двух, заданная длина вектоpа  A (тип: целый);
L - определяет вид преобразования (тип: целый);
L = 1 - выполняется преобразование Уолша по системе функций, расположенных в "естественном" порядке;
L = 2 - система базисных функций расположена в "двоично - инверсном" порядке;
L = 3 - система базисных функций упорядочена по "частоте". 
   Версии:  нет 
   Вызываемые подпрограммы:  нет 
   Замечания по использованию
  1. 

Подпрограмма FTW1R обращается к вспомогательным подпрограммам с именами: FTWWR, FTI1R, FTG1R.

  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.

Пример использования 

      REAL  A(8), B(8)
      DO 1  I = 1, 8
      A(I) = FLOAT(I)
   1 B(I) = A(I)
      CALL  FTW1R (A, 8, 1)
      CALL  FTW1R (B, 8, 3)

Результат:

      A  =  ( 36.,   -4.,  -8.,    0.,  -16.,  0.,  0.,   0. )
      B  =  ( 36.,  -16.,   0.,   -8.,     0.,  0.,  0., -4. )