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