function x = fwt ( n, x )
%*****************************************************************************80
%
%% FWT performs a fast Walsh transform.
%
% Discussion:
%
% This routine performs a fast Walsh transform on an input series X
% leaving the transformed results in X.
% X is dimensioned N, which must be a power of 2.
% The results of this Walsh transform are in sequency order.
%
% The output sequence could be normalized by dividing by N.
%
% Note that the program text in the reference included the line
% y(jd) = abs ( x(j) - x(j2) )
% which has been corrected to:
% y(jd) = x(j) - x(j2)
%
% Licensing:
%
% This code is distributed under the GNU LGPL license.
%
% Modified:
%
% 16 March 2011
%
% Author:
%
% Ken Beauchamp
%
% Reference:
%
% Ken Beauchamp,
% Walsh functions and their applications,
% Academic Press, 1975,
% ISBN: 0-12-084050-2,
% LC: QA404.5.B33.
%
% Parameters:
%
% Input, integer N, the number of items in X.
% N must be a power of 2.
%
% Input, real X(N), the data to be transformed.
%
% Output, real X(N), the transformed data.
%
n2 = floor ( n / 2 );
m = i4_log_2 ( n );
for l = 1 : m
ny = 0;
nz = 2^(l-1);
nzi = 2 * nz;
nzn = floor ( n / nzi );
for i = 1 : nzn
nx = ny + 1;
ny = ny + nz;
js = ( i - 1 ) * nzi;
jd = js + nzi + 1;
for j = nx : ny
js = js + 1;
j2 = j + n2;
y(js) = x(j) + x(j2);
jd = jd - 1;
y(jd) = x(j) - x(j2);
end
end
x(1:n) = y(1:n);
end
return
end