Текст подпрограммы и версий
ftw1r_p.zip 		Тексты тестовых примеров
tftw1r_p.zip

Подпрограмма:  FTW1R (модуль FTW1R_p)

Назначение

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

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

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

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

procedure FTW1R(var A :Array of Real; N :Integer; L :Integer);


   Параметры
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.

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

Unit TFTW1R_p;
interface
uses
SysUtils, Math, { Delphi }
LStruct, Lfunc, UtRes_p, FTW1R_p;

function TFTW1R: String; 

implementation

function TFTW1R: String;
var
I,_i :Integer;
A :Array [0..7] of Real;
B :Array [0..7] of Real;
label
_1;
begin
Result := '';
for I:=1 to 8 do
 begin
  A[I-1] := (I);
_1:
  B[I-1] := A[I-1];
 end;
FTW1R(A,8,1);
FTW1R(B,8,3);
Result := Result + #$0D#$0A;
for _i:=0 to 7 do
 begin
  Result := Result + Format('%20.16f ',[A[_i]]);
  if ( ((_i+1) mod 4)=0 )
   then Result := Result + #$0D#$0A;
 end;
Result := Result + #$0D#$0A;
Result := Result + #$0D#$0A;
for _i:=0 to 7 do
 begin
  Result := Result + Format('%20.16f ',[B[_i]]);
  if ( ((_i+1) mod 4)=0 )
   then Result := Result + #$0D#$0A;
 end;
Result := Result + #$0D#$0A;
UtRes('TFTW1R',Result);  { вывод результатов в файл TFTW1R.res }
exit;
end;

end.

Результат:

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