Transformada discreta de Hartley

À medida que a velocidade de computação continua a aumentar, problemas multidimensionais de maior escala tornam-se computacionalmente viáveis, exigindo a necessidade de algoritmos multidimensionais rápidos. Abaixo, apresentam-se três destes algoritmos.

Em busca de separabilidade para obtenção de eficiência, considera-se a seguinte transformada (Bracewell, 1983):^[2]

$${\displaystyle {\hat {X}}(k_{1},k_{2},...,k_{r})=\sum _{n_{1}=0}^{N_{1}-1}\sum _{n_{2}=0}^{N_{2}-1}\dots \sum _{n_{r}=0}^{N_{r}-1}x(n_{1},n_{2},...,n_{r}){\rm {cas}}\left({\frac {2\pi n_{1}k_{1}}{N_{1}}}\right)\dots {\rm {cas}}\left({\frac {2\pi n_{r}k_{r}}{N_{r}}}\right).}$$

Foi demonstrado em Bortfeld (1995)^[13] que as duas podem ser relacionadas através de algumas adições. Por exemplo, em 3-D,

$${\displaystyle X(k_{1},k_{2},k_{3})={\frac {1}{2}}[{\hat {X}}(k_{1},k_{2},-k_{3})+{\hat {X}}(k_{1},-k_{2},k_{3})+{\hat {X}}(-k_{1},k_{2},k_{3})-{\hat {X}}(-k_{1},-k_{2},-k_{3})].}$$

Para ${\displaystyle {\hat {X}}}$, podem então ser implementados algoritmos linha-coluna (R-C). Esta técnica é habitualmente utilizada devido à simplicidade dos algoritmos R-C, mas não estão otimizados para espaços multidimensionais (M-D) de uma forma geral.

Outros algoritmos rápidos foram desenvolvidos, tais como os algoritmos de base 2, base 4 e split-radix. Por exemplo, Boussakta (2000)^[14] desenvolveu a base vetorial 3-D,

$${\displaystyle X(k_{1},k_{2},...,k_{r})=\sum _{n_{1}=0}^{N-1}\sum _{n_{2}=0}^{N-1}\sum _{n_{3}=0}^{N-1}x(n_{1},n_{2},n_{3}){\rm {cas}}\left({\frac {2\pi }{N}}(n_{1}k_{1}+n_{2}k_{2}+n_{3}k_{3})\right)}$$

$${\displaystyle =\sum _{n_{1}:par}\sum _{n_{2}:par}\sum _{n_{3}:par}+\sum _{n_{1}:par}\sum _{n_{2}:par}\sum _{n_{3}:impar}+\sum _{n_{1}:par}\sum _{n_{2}:impar}\sum _{n_{3}:par}}$$

$${\displaystyle +\sum _{n_{1}:par}\sum _{n_{2}:impar}\sum _{n_{3}:impar}+\sum _{n_{1}:impar}\sum _{n_{2}:par}\sum _{n_{3}:par}+\sum _{n_{1}:impar}\sum _{n_{2}:par}\sum _{n_{3}:impar}}$$

$${\displaystyle +\sum _{n_{1}:impar}\sum _{n_{2}:impar}\sum _{n_{3}:par}+\sum _{n_{1}:impar}\sum _{n_{2}:impar}\sum _{n_{3}:impar}.}$$

Foi também exposto em Boussakta (2000)^[14] que este algoritmo de base vetorial 3D requer ${\displaystyle \left({\frac {7}{4}}\right)N^{3}\log _{2}N}$ multiplicações e ${\displaystyle \left({\frac {31}{8}}\right)N^{3}\log _{2}N}$ adições, comparado com as ${\displaystyle 3N^{3}\log _{2}N}$ multiplicações e ${\displaystyle \left({\frac {9}{2}}\right)N^{3}\log _{2}N+3N^{2}}$ adições da abordagem linha-coluna. A desvantagem é que a implementação deste tipo de algoritmos baseados em decomposição de raízes é difícil de generalizar para sinais de dimensões arbitrárias.

Também foram utilizadas transformadas teóricas dos números para resolver a MD-DHT, uma vez que estas executam convoluções extremamente rápidas. Em Boussakta (1988),^[15] foi demonstrado como decompor a transformada MD-DHT numa forma que consiste em convoluções:

Para o caso 2-D (o caso 3-D também é coberto na referida referência),

$${\displaystyle X(k,l)=\sum _{n=0}^{N-1}\sum _{m=0}^{M-1}x(n,m){\rm {cas}}\left({\frac {2\pi nk}{N}}+{\frac {2\pi ml}{M}}\right),\;}$$ ${\displaystyle k=0,1,\ldots ,N-1}$ , ${\displaystyle l=0,1,\ldots ,M-1}$

pode ser decomposto em convoluções circulares 1-D e 2-D da seguinte forma:

$${\displaystyle X(k,l)={\begin{cases}X_{1}(k,0)\\X_{2}(0,l)\\X_{3}(k,l)\end{cases}}}$$

onde

$${\displaystyle X_{1}(k,0)=\sum _{n=0}^{N-1}\left(\sum _{m=0}^{M-1}x(n,m)\right){\rm {cas}}\left({\frac {2\pi nk}{N}}\right),\;}$$ ${\displaystyle k=0,1,\ldots ,N-1}$

$${\displaystyle X_{2}(0,l)=\sum _{m=0}^{M-1}\left(\sum _{n=0}^{N-1}x(n,m)\right){\rm {cas}}\left({\frac {2\pi ml}{M}}\right),\;}$$ ${\displaystyle l=1,2,\dots ,M-1}$

$${\displaystyle X_{3}(k,l)=\sum _{n=0}^{N-1}\sum _{m=0}^{M-1}x(n,m){\rm {cas}}\left({\frac {2\pi nk}{N}}+{\frac {2\pi ml}{M}}\right)\;,}$$

$${\displaystyle k=1,2,\ldots ,N-1}$$

$${\displaystyle l=1,2,\ldots ,M-1.}$$

Desenvolvendo ainda ${\displaystyle X_{3}}$,

$${\displaystyle X_{3}(k,l)=\sum _{n=0}^{N-1}x(n,0){\rm {cas}}\left({\frac {2\pi nk}{N}}\right)+\sum _{m=1}^{M-1}x(0,m){\rm {cas}}\left({\frac {2\pi ml}{M}}\right)}$$

$${\displaystyle +\sum _{n=1}^{N-1}\sum _{m=1}^{M-1}x(n,m){\rm {cas}}\left({\frac {2\pi nk}{N}}+{\frac {2\pi ml}{M}}\right).}$$

Neste momento, introduzimos a transformada de números de Fermat (FNT). O t-ésimo Número de Fermat é dado por ${\displaystyle F_{t}=2^{b}+1}$, com ${\displaystyle b=2^{t}}$. Os números de Fermat bem conhecidos são para ${\displaystyle t=0,1,2,3,4,5,6}$ (${\displaystyle F_{t}}$ é primo para ${\displaystyle 0\leq t\leq 4}$), (Boussakta, 1988).^[15] A transformada de números de Fermat é dada por:

$${\displaystyle X(k,l)=\sum _{n=0}^{N-1}\sum _{m=0}^{M-1}x(n,m)\alpha _{1}^{nk}\alpha _{2}^{ml}\mod F_{t}}$$

com ${\displaystyle k=0,\ldots ,N-1,l=0,\ldots ,M-1}$. ${\displaystyle \alpha _{1}}$ e ${\displaystyle \alpha _{2}}$ são raízes da unidade de ordem ${\displaystyle N}$ e ${\displaystyle M}$ respetivamente ${\displaystyle (\alpha _{1}^{N}=\alpha _{2}^{M}=1\mod F_{t})}$.

Voltando à decomposição, o último termo para ${\displaystyle X_{3}(k,l)}$ será denotado como ${\displaystyle X_{4}(k,l)}$, de modo que

$${\displaystyle X_{4}(k,l)=\sum _{n=1}^{N-1}\sum _{m=1}^{M-1}x(n,m){\rm {cas}}\left({\frac {2\pi nk}{N}}+{\frac {2\pi ml}{M}}\right),}$$

$${\displaystyle k=1,2,\ldots ,N-1}$$

$${\displaystyle l=1,2,\ldots ,M-1.}$$

Se ${\displaystyle g_{1}}$ e ${\displaystyle g_{2}}$ forem raízes primitivas de ${\displaystyle N}$ e ${\displaystyle M}$ (que se garante existirem caso ${\displaystyle M}$ e ${\displaystyle N}$ sejam primos), então ${\displaystyle g_{1}}$ e ${\displaystyle g_{2}}$ mapeiam ${\displaystyle (n,m)}$ em ${\displaystyle (g_{1}^{n}\mod N,g_{2}^{m}\mod M).}$ Logo, ao mapear ${\displaystyle n,m,k}$ e ${\displaystyle l}$ em ${\displaystyle g_{1}^{-n},g_{2}^{-m},g_{1}^{k}}$ e ${\displaystyle g_{2}^{l}}$, obtém-se o seguinte:

$${\displaystyle X_{4}(g_{1}^{k},g_{2}^{l})=\sum _{n=0}^{N-2}\sum _{m=0}^{M-2}x(g_{1}^{-n},g_{2}^{-m}){\rm {cas}}\left({\frac {2\pi g_{1}^{(-n+k)}}{N}}+{\frac {2\pi g_{2}^{(-m+l)}}{M}}\right),}$$

$${\displaystyle k=0,1,\ldots ,N-2}$$

$${\displaystyle l=0,1,\ldots ,M-2.}$$

Isto agora é uma convolução circular. Com ${\displaystyle Y(k,l)=X_{4}(g_{1}^{k},g_{2}^{l})}$, ${\displaystyle y(n,m)=x(g_{1}^{-n},g_{2}^{-m})}$, e ${\displaystyle h(n,m)={\rm {cas}}\left({\frac {2\pi g_{1}^{n}}{N}}+{\frac {2\pi g_{2}^{m}}{M}}\right)}$, obtém-se:

$${\displaystyle Y(k,l)=\sum _{n=0}^{N-2}\sum _{m=0}^{M-2}y(n,m)h(<k-n>_{N},<l-m>_{M})}$$

$${\displaystyle Y(k,l)=FNT^{-1}\{FNT[y(n,m)]\otimes FNT[h(n,m)]\}}$$

onde ${\displaystyle \otimes }$ denota a multiplicação termo a termo. Foi ainda mencionado em (Boussakta, 1988)^[15] que este algoritmo diminui o número de multiplicações por um fator entre 8 e 20 em relação a outros algoritmos DHT, mediante o ligeiro aumento no número de operações de deslocamento e adição, as quais são tidas como mais simples computacionalmente que as multiplicações. A principal desvantagem deste algoritmo é a restrição de que cada dimensão da transformada tem de possuir uma raiz primitiva.