Fast Walsh Hadamard Transform (FWHT)

참고

가장 단순하게는 xor convolution을 빠르게 계산하는 방법이라고 생각해도 된다.

이제 WHT를 적용한 결과가 어떻게 나오면 pointwise로 곱해서 처리할수 있는지, WHT를 어떻게 빠르게 계산하는지 등은 위에 있는 링크들을 참고하면 된다. 저것만 이해하면 FWHT를 이용해서 xor/or/and convolution을 계산하는 것은 충분히 가능하다

좀 헷갈릴만한 부분은, 위키피디아의 Fast Walsh–Hadamard transform 항목에서는 xor convolution 같은 얘기는 없고, 뜬금없어 보이는 행렬만 보여주고 있는 것으로 설명방법이 완전히 다르다. 사실 원칙적으로 WHT는 수열에 Hadamard matrix를 곱해주는 방식으로 계산되는 것이고, xor convolution을 위해서는 특정한 형태의 Hadamard matrix가 필요한 것 뿐이다. 근데 어차피 이것을 그냥 곱하지 않고 빠르게 계산하는 방법이 필요한 것이고, xor convolution 과 같은 특정 연산을 설명할 때에는 그냥 바로 결과값으로 변환하는 과정을 설명하는 것으로 충분하기 때문에 굳이 저걸 다 설명하지 않았던 것.