function x = walsh_transform ( n, x )
%*****************************************************************************80
%
%% WALSH_TRANSFORM performs a fast Walsh transform.
%
% Discussion:
%
% This routine performs a fast Wash transform on an input series X
% leaving the transformed results in X. The array Y is working space.
% X and Y are 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.
%
% 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 );
z = - 1.0;
for j = 1 : m
n1 = 2^( m - j + 1 );
j1 = 2^( j - 1 );
for l = 1 : j1
is = ( l - 1 ) * n1 + 1;
i1 = 0;
w = z;
for i = is : 2 : is + n1 - 1
a = x(i);
x(is+i1) = a + x(i+1);
i1 = i1 + 1;
y(i1) = ( x(i+1) - a ) * w;
w = w * z;
end
n2 = floor ( n1 / 2 );;
x(n2+is:n1+is-1) = y(1:n2);
end
end
return
end