Szybka transformata Walsha-Hadamarda

Szybka transformata Walsha-Hadamarda zastosowana do wektora o długości 8

Przykład wektora wejściowego (1, 0, 1, 0, 0, 1, 1, 0)

W matematyce obliczeniowej uporządkowana przez Hadamarda szybka transformata Walsha-Hadamarda ( FWHT _h ) jest wydajnym algorytmem do obliczania transformaty Walsha-Hadamarda (WHT). Naiwna implementacja WHT rzędu $\$ złożoność obliczeniową O ( $n ^$ ) displaystyle FWHT _h wymaga tylko dodawania lub odejmowania ${\ displaystyle n \ log n} .$

FWHT _h to algorytm typu „dziel i zwyciężaj” $n/2}$ który rekurencyjnie dzieli podatek u źródła o rozmiarze na dwa mniejsze WHT o rozmiarze $displaystyle$ . Ta implementacja $}$ z rekurencyjną definicją macierzy Hadamarda : ${\ Displaystyle 2 ^ {m} \ razy 2 ^ {m}$ :

${\ Displaystyle H_ {m} = {\ Frac {1} {\ sqrt {2}}} {\ rozpocząć {pmatrix} H_ {m-1} i H_ {m-1} \\ H_ {m-1} i - H_{m-1}\end{pmacierz}}.}$

Czynniki $etapu$ można zgrupować lub nawet

Uporządkowana sekwencyjnie , znana również jako uporządkowana przez Walsha, szybka transformata Walsha-Hadamarda, FWHT _w , jest uzyskiwana przez obliczenie FWHT _h jak powyżej, a następnie przestawienie wyników.

$m$ implementacja transformaty Walsha-Hadamarda wynika z rozkładu macierzy transformacji Hadamarda gdzie A to -ty z ${\ displaystyle H_ {m}}$ .

Przykładowy kod Pythona

   
    
      
       
        
           0    
                  
                  
                    
                    
                      
        
          
           def  fwht  (  a  )  ->  None  :  """Szybka transformata Walsha-Hadamarda w miejscu tablicy a."""  h  =  1  while  h  <  len  (  a  ):  # wykonaj FWHT  dla  i  w  zakresie  (  ,  len  (  a  ),  godz  *  2  ):  dla  j  w  przedziale  (  ja  ,  ja  +  godz  ):  x  =  za  [  j  ]  y  =  za  [  j  +  godz  ]  za  [  jot  ]  =  x  +  y  za  [  j  +  godz  ]  =  x  -  y  # znormalizuj i zwiększ  a  /=  2  h  *=  2 

Zobacz też

• Szybka transformata Fouriera

Linki zewnętrzne

• Charles Constantine Gumas, Sto lat, szybka transformacja Hadamarda okazuje się przydatna w komunikacji cyfrowej