快速多维沃尔什-哈达马尔在朱莉娅身上变身?

Question

我一直在寻找FWHT(Fast Walsh-Hadamard变换(的快速实现来理解它并在python中实现它(实现应该能够处理n维数组，并且应该能够在任何特定的维度集上应用转换(。

我遇到了 Julia 实现 (https://github.com/stevengj/Hadamard.jl(，它似乎很好，但由于我是 Julia 的新手，我无法理解代码的一部分：

for (Tr,Tc,fftw,lib) in ((:Float64,:Complex128,"fftw",FFTW.libfftw),
(:Float32,:Complex64,"fftwf",FFTW.libfftwf))
@eval function Plan_Hadamard{N}(X::StridedArray{$Tc,N}, Y::StridedArray{$Tc,N},
region, flags::Unsigned, timelimit::Real,
bitreverse::Bool)
set_timelimit($Tr, timelimit)
dims, howmany = dims_howmany(X, Y, [size(X)...], region)
dims = hadamardize(dims, bitreverse)
plan = ccall(($(string(fftw,"_plan_guru64_dft")),$lib),
PlanPtr,
(Int32, Ptr{Int}, Int32, Ptr{Int},
Ptr{$Tc}, Ptr{$Tc}, Int32, UInt32),
size(dims,2), dims, size(howmany,2), howmany,
X, Y, FFTW.FORWARD, flags)
set_timelimit($Tr, NO_TIMELIMIT)
if plan == C_NULL
error("FFTW could not create plan") # shouldn't normally happen
end
return cFFTWPlan{$Tc,FFTW.FORWARD,X===Y,N}(plan, flags, region, X, Y)
end
@eval function Plan_Hadamard{N}(X::StridedArray{$Tr,N}, Y::StridedArray{$Tr,N},
region, flags::Unsigned, timelimit::Real,
bitreverse::Bool)
set_timelimit($Tr, timelimit)
dims, howmany = dims_howmany(X, Y, [size(X)...], region)
dims = hadamardize(dims, bitreverse)
kind = Array{Int32}(size(dims,2))
kind[:] = R2HC
plan = ccall(($(string(fftw,"_plan_guru64_r2r")),$lib),
PlanPtr,
(Int32, Ptr{Int}, Int32, Ptr{Int},
Ptr{$Tr}, Ptr{$Tr}, Ptr{Int32}, UInt32),
size(dims,2), dims, size(howmany,2), howmany,
X, Y, kind, flags)
set_timelimit($Tr, NO_TIMELIMIT)
if plan == C_NULL
error("FFTW could not create plan") # shouldn't normally happen
end
return r2rFFTWPlan{$Tr,(map(Int,kind)...),X===Y,N}(plan, flags, region, X, Y)
end
end

在上面的代码中，计划变量是什么，如何使用它，在哪里可以找到它的实现？

以下行的大括号中的输入是什么？

cFFTWPlan{$Tc,FFTW.FORWARD,X===Y,N}

Answer 1

这是构建一个FFTW"计划"来执行多维FFT。cFFTWPlan类型是围绕 Cfftw_plan指针的包装器，在 FFTW.jl 模块中实现。 大括号中的参数是 Julia 类型参数：在这种情况下，指示数字类型 (Tc(、FFTW 变换方向FORWARD、变换是否就地 (X===Y( 以及变换的维数 (N(。 这里有两种方法，一种用于创建cFFTWPlan的复数数据的 FWHT(调用fftw_plan_guru_dft(，另一种用于创建r2rFFTWPlan的实数数据(调用 fftw_plan_guru_r2r(。 (这些内部类型的 FFTW.jl 没有文档。 直接对 FFTW 库的低级 C 调用记录在 FFTW 手册中。

原则上，应该可以对 NumPy 数组的 FFTW 进行类似的调用。 但是，现有的 pyFFTW 包装器似乎不支持 FFTW 的 r2r 转换(真实数据的 FWHT 需要(，因此您必须添加它。

或者你可以通过pyjulia包从Python调用Julia Hadamard.jl模块。 或者你可以使用其他一些Python FWHT包，比如 https://github.com/FALCONN-LIB/FFHT

Answer 2

有一本小册子用一些基本的直观方式解释了它。 预扣税小册子 例如，[a，b] 的 2 点变换是 [a+b，a-b]，它可以再次通过相同的动作反转 [(a+b(+(a-b(，(a+b(-(a-b](=[2a，2b]。然后，它解释了如何从 2 个 2 点变换等构造 4 点变换。