주파수 영역, 실제 장소인가?

• 이산 Fourier 변환(DFT) 은 통신과 신호 처리의 핵심 도구지만, 주파수 영역이 현실을 해석하는 유일한 방식은 아님
• DCT처럼 입력 샘플에 기저 함수 값을 곱해 주파수 bin을 구하는 구조에서는, 기저를 바꾸는 것만으로 다른 규칙의 주파수 영역을 만들 수 있음
• Walsh 행렬은 +1과 -1만 쓰는 정사각파 기저를 제공하며, sequency와 직교성을 맞추면 시간 영역과 주파수 표현을 왕복할 수 있음
• Hadamard 행렬은 Walsh 행렬을 재정렬한 형태로, Kronecker product나 비트 연산으로 만들고 행을 sequency 기준으로 다시 정렬해 WHT에 활용함
• 같은 입력도 DCT에서는 여러 조화 성분으로 퍼지고 Walsh-Hadamard 변환에서는 정사각파 성분으로 나뉘어, DFT가 “진실”을 독점하지 않음을 보여줌

---

Fourier 주파수 영역을 다시 보기

• 주파수 영역은 복잡한 신호를 사인파의 진폭과 위상으로 바꿔 표현하는 수학적 공간임
• 이 표현 덕분에 시간 영역이나 공간 영역에서 직접 다루기 어려운 신호 처리 작업을 더 쉽게 수행할 수 있음
• DFT는 통신과 신호 처리에서 중심적 역할을 하지만, 정사각파를 홀수차 사인 조화파의 합으로 바꾸는 해석이 현실의 유일한 해석인지는 별개의 문제임
• 사인파는 자연에 널리 존재해 Fourier 계열 도구가 많은 작업에 잘 맞지만, 다른 규칙으로 동작하는 잘 정의된 주파수 영역도 만들 수 있음

DCT를 기저 함수로 이해하기

• 이산 코사인 변환(DCT)은 DFT의 단순화된 실수 전용 버전으로 볼 수 있음
• DCT-II는 입력 값 s_n에 특정 코사인 식의 값을 곱한 뒤 합산해 특정 주파수 bin F_k의 크기를 구함
• 핵심은 현재 DCT bin 번호에 해당하는 주파수의 코사인파를 만드는 기저 함수임
• 일반화하면 B(k, n)이 k와 n에 따라 multiplier를 반환하고, 이를 입력 샘플과 곱해 합산하는 구조가 됨
• 소프트웨어 관점에서는 B(k, n)을 조회 배열로, 수학적으로는 행렬로 볼 수 있음
• N=16 DCT 기저 행렬에서 첫 행 k=0은 0Hz에 해당하는 DC 성분이며, 모든 값이 +1.00인 코사인임
• 이후 행들은 반 주기, 한 주기, 한 주기 반처럼 점차 빠르게 변하는 코사인 형태를 가짐

정사각파 기저와 Walsh 행렬

• 사인 주파수가 아니라 정사각파로 신호를 나누는 기저 함수는 Walsh 행렬로 만들 수 있음
• Walsh 행렬은 서로 다른 속도로 움직이는 정사각파들로 구성되며, 모든 multiplier가 +1 또는 -1임
• 계산은 입력 데이터 일부의 부호를 뒤집고 합산하는 방식으로 단순해짐
• 단순해 보이는 행렬도 두 조건을 만족해야 함
  • 각 행은 이전 행보다 부호 전환이 하나 더 많은 sequency 순서를 가져야 함
  • 시간 영역 데이터와 주파수 표현 사이를 매끄럽게 왕복하려면 직교성을 유지해야 함
• Walsh 행렬을 직접 만들려면 N×N 배열에서 시작하며, N은 2의 거듭제곱이어야 함
  • 왼쪽 첫 열에 모든 행의 +1을 넣음
  • 새 열을 기존 값의 거울 복사로 만들고, 새로 추가한 영역을 여러 수평 구간으로 나눠 일부 구간의 부호를 뒤집음
  • 반복마다 열을 복사하고 행 구간 수를 늘려 번갈아 부호를 뒤집음

Hadamard 행렬에서 Walsh 배열 만들기

• 문헌과 오픈소스 코드에서는 Walsh 배열을 직접 만들기보다 Hadamard 행렬에서 유도하는 경우가 많음
• Hadamard 행렬은 Walsh 배열의 행 순서를 바꾼 형태임
  • 예를 들어 N=16에서 Walsh의 row #15는 Hadamard에서 #1로 이동하고, Walsh의 row #1은 #8에 놓임
• Hadamard 구성이 먼저 역사적으로 등장했고 Walsh가 그 위에 구축됐다는 점이 이런 관례의 한 이유임
• 실용적으로는 Hadamard 행렬을 만드는 방법이 더 잘 문서화되어 있으며, 간단하고 효율적인 비트 조작 방식도 있음
• 교과서적 구성은 1×1 배열에서 시작해 이전 행렬 H_{n-1}을 4개 타일로 복사하는 방식임
  • 왼쪽 위, 오른쪽 위, 왼쪽 아래는 그대로 복사함
  • 오른쪽 아래는 모든 부호를 뒤집음
  • 이 확장에는 Kronecker product 표기 ⊗가 쓰이지만, 실제 동작은 복사와 부호 반전임
• 구성 단계를 n번 거치면 Hadamard 행렬의 크기는 항상 2^n × 2^n이 됨
• 특정 셀의 Hadamard 값은 x & y를 계산한 뒤, 결과에서 켜진 bit 수가 짝수인지 홀수인지로 구할 수 있음
  • 켜진 bit 수가 홀수면 -1, 짝수면 +1
  • C 코드에서는 __builtin_popcount(x & y) % 2로 구현함

Walsh-Hadamard 변환 구현

• Hadamard 행렬을 직관적인 Walsh 순서로 바꾸려면 행을 sequency 기준으로 정렬해야 함
• 가장 단순한 방법은 각 행에서 부호 변화 횟수를 세는 것임
• 다른 비트 조작 방식도 가능함
  • Walsh 행 번호를 자기 자신을 1bit 오른쪽으로 민 값과 XOR해 Gray code를 만듦
  • 마지막 nbit의 순서를 뒤집어 Hadamard 행 매핑을 계산함
• 이렇게 만든 Walsh 배열로 DCT 구현의 기저를 바꾸면 “discrete square transform”과 역변환을 만들 수 있음
• 기술적으로 이 변환은 Walsh–Hadamard transform(WHT) 임
• 예시 입력 1 1 1 1 5 5 5 5를 DCT로 처리하면 여러 주파수 bin에 조화 성분이 퍼짐
  • DCT : +24.00 -10.25 -0.00 +3.60 +0.00 -2.41 -0.00 +2.04
• 같은 입력을 정사각파 변환으로 처리하면 F_0과 F_1에만 0이 아닌 성분이 나타남
  • SQFT : +24.00 -16.00 +0.00 +0.00 +0.00 +0.00 +0.00 +0.00
• 역변환 isqft()는 원래 입력을 복원함
  • ISQFT : +1.00 +1.00 +1.00 +1.00 +5.00 +5.00 +5.00 +5.00

스펙트로그램 비교와 실용적 위치

• Gorillaz의 “DARE”에서 가져온 11초 오디오 클립으로 DCT 스펙트로그램과 Walsh-Hadamard 스펙트로그램을 비교함
• Walsh-Hadamard 변환은 낮은 성능의 컴퓨터에서도 계산 효율이 좋고, 특정 유형의 데이터에 잘 맞아 몇몇 틈새 용도로 쓰임
• 결론은 WHT를 더 많이 써야 한다는 것이 아니라, 이산 Fourier 변환이 진실을 독점하지 않는다는 점임
• 스펙트로그램은 44.1kHz mono 오디오 파일에서 DCT와 WHT로 계산됨
  • 입력 샘플 window는 512
  • transform stepover는 1
  • 출력 배열 크기는 약 512 × 485k
  • 픽셀 강도는 정규화한 절댓값에 gamma 약 0.4를 적용함
  • 이미지는 Lanczos resampling으로 리사이즈하고, 검정–하늘색–흰색 선형 colormap으로 렌더링함
• Walsh-Hadamard를 이미지 압축에 실험한 사례로 http://rotormind.com/blog/2019/hadamard-days-night/가 함께 소개됨

[GN⁺]

Hacker News 의견들

• 수학적으로 푸리에 변환은 시간 신호를 특정 직교 벡터 기저로 표현하는 방법일 뿐임
  지표면의 변위 벡터도 북/동 방향 기저로 표현할 수 있고, 어떤 도로 방향과 그에 수직인 방향으로도 표현할 수 있음
  시간 의존 신호나 “예쁜” 함수는 무한 차원 벡터 공간에 있어서 상상하기 어렵지만, 핵심 수학은 비슷하게 작동함
  푸리에 변환에서는 기저 벡터가 조화 함수이고, 주파수 영역은 무한히 많은 조화 함수 조합으로 신호를 보여주는 하나의 “지도”임
  Walsh–Hadamard 변환 같은 다른 기저의 지도도 똑같이 실재하며, 시간 영역 표현 역시 우리에게 익숙할 뿐 여러 지도 중 하나임

  • 맞는 답변이고, 여기에 덧붙이면 푸리에 변환은 시간 신호뿐 아니라 조각별 연속·미분 가능하고 Dirichlet 적분 가능한 함수에도 적용됨
    이미지 처리, 미분방정식 풀이, 빠른 곱셈 같은 응용이 많음
    수학적으로 이런 변환은 무손실이라 변환된 함수가 원래 함수와 정확히 같은 정보를 가지며, 변환만 있어도 원본으로 되돌릴 수 있음
    공학적으로는 특정 주파수 성분처럼 원치 않는 정보를 버리려고 변환하는 일이 많아서 이 점이 자주 흐려짐
    결국 함수 하나를 바라보는 여러 관점 중 하나임
  • 예전에는 나도 “다른 기저”라고 생각했지만, 요즘은 그 비유가 조금 위험하거나 적어도 전부는 아니라고 봄
    특히 다차원 공간에서 일반적인 다차원 푸리에 변환은 그 공간에 평탄한 계량이 있을 때만 제대로 작동함
    우주 자체가 휘어 있다는 점을 생각하면 경고 신호처럼 보임
    최근 특정 쌍곡 격자로 푸리에 급수를 일반화한 흥미로운 연구가 있었고, 그 결과 위치 공간보다 푸리에 공간의 차원이 더 높아질 수 있음
    게다가 이 “푸리에 공간”의 차원은 격자 이산화 방식에 따라 달라져서, 어떤 2차원 격자는 4차원 주파수 유사 영역을 갖고 다른 2차원 격자는 8차원 유사 영역을 가질 수 있음
    https://arxiv.org/abs/2108.09314 또는 https://www.pnas.org/doi/full/10.1073/pnas.2116869119
  • 과거 천문학자들은 주전원을 붙인 지구중심 우주 모델을 믿었고, 더 정확도가 필요하면 주전원을 더 추가했음
    완전히 틀린 모델이었지만, 사실상 푸리에 급수를 함수 근사기로 쓰고 있었던 셈임
  • 전반적으로 동의하지만, 모든 정규직교 기저는 주파수 스펙트럼을 나눔
    다항식 같은 기저를 써도 결국 주파수 성분으로 함수를 쌓는 것임
    푸리에 기저는 각 원소가 특정 주파수에 대응한다는 점에서 특별함
    다만 각 기저는 목적에 맞게 설계된 것에 가깝고, 기저 변환은 스펙트럼을 분석하기 복잡한 방식으로 재배열할 수 있음
    그때는 매끄러움 같은 다른 성질을 분석하게 됨
    관심 있는 대부분의 함수에는 특징적인 스펙트럼이 있지만, 푸리에 기저가 모든 질문에 답해 주지는 않음
  • 기저 벡터가 꼭 수직일 필요는 없지 않나?
    북쪽과 북동쪽처럼 어느 정도 수직 성분만 있으면 [n, e]도 다른 좌표로 표현할 수 있음
    구체적인 계수는 열 때문에 틀렸을 수 있지만, 핵심은 가능하다는 점임

• 석사 때 동역학계 그룹에서 화이트보드 앞에서 나눈 대화가 떠오름
  “왼쪽에서 시스템에 에너지가 주입되고, 오른쪽 여기서 소산됩니다”
  “하지만 시스템은 회전 불변이라 왼쪽과 오른쪽이 없잖아요”
  “주파수 공간에서 말한 겁니다”
  “아, 실제 공간을 말하는 줄 알았어요”
  “바보예요? 누가 실제 공간에서 생각합니까?”

  • 잠깐, 주파수 공간에도 왼쪽과 오른쪽이 있나?
    추상적 표현이라 공간 차원의 좌우상하와 직접 관계는 없는 것 아닌가
  • 평생 상아탑 학계를 향해 내뿜은 경멸만 모아도 작은 섬나라 하나를 10년은 돌릴 수 있을 듯함
  • 석사 과정에서는 서로 바보라고 부르나, 아니면 많이 각색한 건가?

• 복소 지수 기저 함수가 선형 시불변(LTI) 시스템의 고유벡터라는 점에서 푸리에 기저는 독특함
  다른 변환에는 이 성질이 없음
  회로, 통신 채널, 안테나 등 많은 현실 시스템이 LTI이고, 이 성질 덕분에 서로 다른 주파수로 전송된 신호가 간섭하지 않음
  그래서 푸리에 변환이 다른 변환보다 널리 쓰임
  양자물리에서도 위치와 운동량의 파동함수로 푸리에 쌍을 쓰는 연결이 있는데, 다른 변환에는 이런 성질이 없음

  • 이 얘기를 꺼낸 사람이 거의 없어서 놀랐음
    전기공학 배경에서는 분석을 위해 많은 시스템을 선형 또는 매우 약한 비선형으로 가정하고, 신호도 대체로 주기적이라 푸리에 변환이 자연스러움
    합성곱은 곱셈이 되고, 복소 지수의 시간 미분은 j*omega를 곱하는 일이 됨
    합성곱과 시간 미분보다 곱셈을 하는 편이 훨씬 낫다
    “흔한 특정 상황에서 편리해서 푸리에 표현을 쓴다”를 받아들이면, 다른 문제에 다른 수학적 변환을 쓰는 것도 놀랄 일이 아님
  • 기술적으로는 라플라스 기저의 특수한 경우 아닌가?
    많은 강의가 가장 일반적인 양방향 라플라스 변환을 제대로 다루지 않고, 양방향 푸리에 변환에서 단방향 라플라스 변환으로 바로 넘어가는 점이 늘 의아했음
    https://en.wikipedia.org/wiki/Two-sided_Laplace_transform

• “실재하는 장소”냐고 묻는다면, 예전에 한 광학 실험이 떠오름
  그림을 렌즈 몇 개에 통과시키면 주파수들의 평면이 생기고, 다시 렌즈를 거쳐 화면에 투사됨
  그 주파수 평면의 일부를 막으면 이미지가 바뀜
  다루기 엄청 까다로웠고, St Andrew’s의 Dr Bruce Sinclair에게 큰 감사를 느꼈음
  물리 실험실 작업은 사물이 어떻게 작동하는지 보게 해 주지만, 실험 몇 달 뒤 이론을 다시 보면 꽤 길을 잃게 됨

  • 주파수들의 평면은 늘 생기는 것 아닌가?
    그래서 개구가 해상도를 제한하고, 반사망원경에서 회절 스파이크가 생기는 식으로 이어지는 것 같음
  • 소프트웨어로도 할 수 있음: https://imagemagick.org/Usage/fourier/#noise_removal
  • 광학으로 주파수 영역 표현을 얻는 성질은 광원 기반의 여러 현미경법과 분광법에서 꽤 편리함
  • 푸리에 광학임
    Schlieren도 이런 식으로 작동함

• DFT의 또 다른 흥미로운 일반화로 Lomb-Scargle 변환이 있음
  시간 영역에서 고정된 측정 간격이 필요하지 않음
  천체물리처럼 측정 간격이 일정하지 않을 때 주기 신호의 주파수를 찾는 데 자주 쓰임
  https://iopscience.iop.org/article/10.3847/1538-4365/aab766는 일반적인 소개이고, https://docs.astropy.org/en/stable/timeseries/lombscargle.ht...는 Python의 astropy 라이브러리에서 쓰는 방법을 잘 소개함

  • 최근 Prometheus 데이터를 주파수 영역으로 표현하면 용량 계획에서 주간·일간·연간 접근 패턴을 시각화하는 데 유용하지 않을까 많이 생각함
    자동 확장은 장애성 성능 저하를 피하게 해 줄 수 있지만, 연간 예산이 얼마여야 하는지와 그 이유를 알려주지는 못함
    다만 Prometheus 데이터는 진짜 표본화 간격이라고 보기 어려움
    클러스터의 각 머신이 일정 간격으로 보고하더라도 서로 동기화되어 있지는 않음

• 다른 관점에서 보면 달팽이관은 푸리에 변환의 “실제” 구현처럼 볼 수 있음
  https://www.britannica.com/science/sound-physics/The-ear-as-...

  • 달팽이관은 오히려 글의 요지를 뒷받침함
    주파수 영역으로 변환하긴 하지만 푸리에 변환을 하거나 근사하지는 않음
    달팽이관이 “구현”하는 시간→주파수 영역 변환은 웨이블릿 변환에 더 가까움
    달팽이관을 푸리에 변환으로 해석하는 건 눈의 원뿔세포가 빨강·초록·파랑 빛에만 반응한다고 생각하는 실수와 비슷함
    실제로 각 세포는 일정 범위의 주파수에 걸쳐 다르게 반응함
    원뿔세포는 저·중·고 주파수 영역에서 정점을 찍고 양쪽으로 줄어들며, 달팽이관 유모세포는 정점 주파수의 조화음에 2차 피크가 있는 더 웨이블릿 같은 반응 곡선을 가짐
    전문가가 아니라 열성 아마추어라서, 더 잘 아는 사람이 정정해 주길 기대함
  • 생물학이 물리학에 얼마나 단단히 뿌리내려 있는지 잊기 쉬움
    대학 때 우리 줄기세포주가 뼈로 분화하는 문제가 있었는데, 알고 보니 환경의 단단함이 줄기세포가 감지할 수 있는 신호였음
    딱딱한 배양 접시가 세포에게 뼈세포가 되어야 한다고 말하고 있던 셈임

• 글에서 “Hadamard 행렬의 행을 sequency 기준으로 정렬하려면 0 교차 횟수를 세는 것보다 우아한 알고리즘을 모른다”고 했는데, 행렬을 보고 패턴을 추측했더니 이미 알려진 방법이었음
  https://en.wikipedia.org/wiki/Walsh_matrix에 따르면 Walsh 행렬의 sequency 정렬은 Hadamard 행렬에 먼저 비트 반전 순열을 적용하고, 이어 Gray-code 순열을 적용해 얻을 수 있음

• 글은 아주 일반적이고 철학적인 질문을 던지지만, 이후에는 다른 직교 기저와 변환을 찾을 수 있으니 주파수 영역이 별로 특별하지 않다고 말함
  그래도 주파수 영역과 푸리에 변환은 다른 많은 변환보다 특별하다고 봄
  자연에서 직접 관찰할 수 있기 때문임
  예를 들어 렌즈는 평행광에 실린 입력 이미지의 2차원 푸리에 변환을 수행하고, 이를 화면으로 볼 수 있음
  또 격자나 프리즘의 출력을 CCD에 투영해 빛의 파장이나 주파수를 측정할 수 있는데, 이것도 주파수 영역의 직접 측정임
  RF 파동에서도 비슷한 측정이 가능함

• 사인파는 Helmholtz 파동 방정식의 자연스러운 해라는 점에서 특별함
  사각파에는 무한 에너지 같은 다른 문제도 있음
  이 글은 수학자나 컴퓨터과학자에게는 말이 될 수 있지만, 소리와 파동의 근본 물리를 놓치고 있음

  • 사인파는 미분 연산자의 고유함수라는 점에서도 특별함
    물리 결과는 아마 그 성질의 결과일 가능성이 큼
    결국 현대 수학의 핵심 교훈은 대상을 여러 관점에서 보는 것이 유용하다는 데 있음
  • 맞는 말임
    엄청나게 많은 물리적 물체가 조화 진동자이고, 이는 물리학에 꽤 근본적인 기반을 둠
    푸리에 분석을 쓸 만한 다른 곳도 많이 떠오르지만, 사인파는 물리적으로 더 “실재”하고, 어떤 기저 집합으로도 표현 가능하다는 말은 더 “타당”한 쪽에 가까움
    “실재”라는 단어는 현상 뒤에 실제 진동자가 있다는 느낌을 주는 듯함
    사각파는 신호와 도함수 모두의 불연속 때문에 덜 물리적이고, 자연은 불연속을 정말 좋아하지 않음
  • 주파수 영역은 자연에 존재하는 많은 시스템을 근사적으로 설명하는 선형 시불변 연산에서 수학을 아주 쉽게 만들어 줌
    예를 들어 Gibbs 현상은 어떤 차단 주파수 위의 모든 주파수를 0으로 만든 주파수 응답의 역푸리에 변환에서 자연스럽게 나옴
    사각파의 주파수 영역이 Gibbs 현상을 어떻게 설명할지는 궁금함
    아마 시스템이 비선형인 것처럼 기본 사각파 주파수의 조화파들이 나타날 것 같음

• 학부 물리·수학을 하면서 함수 f(x)의 값을 무한히 많은 x에서 아는 것과, f의 주파수 성분을 무한히 많은 주파수에서 아는 것은 동등하다는 결론에 이르렀음
  철학적으로 두 표현은 똑같이 “실재”함
  어떤 문제는 한 표현에서 다른 표현보다 더 쉽게 풀릴 뿐임

  • 완전히 동의함
    시간 영역에서 주파수 영역으로 바꾸는 건 좌표계 전환과 같음
    시간 영역에 좁은 피크 하나가 있는 신호는 피크 위치의 델타 하나로 매우 작고 희소하게 표현할 수 있지만, 주파수 영역에서는 그렇게 압축된 표현이 나오지 않음
    반대로 시간 영역의 사인파 신호는 그쪽에서는 compact하지 않지만, 주파수 영역에서는 델타 몇 개만 있으면 됨
    시간과 주파수는 같은 것을 나타내는 두 방식이고, 어떤 경우에는 한 영역이 더 쉽고 다른 경우에는 반대임
    시간 영역에서 유계인 것은 주파수 영역에서 비유계가 되고 그 반대도 성립함을 증명할 수 있음
    그래서 한 영역에서 compact한 것은 다른 영역으로 가면 항상 퍼짐
    양자역학에서는 위치와 운동량이 위의 시간·주파수처럼 켤레 변수라서, 위치가 유계이면 운동량은 비유계가 되고 그 반대도 성립함
    이것이 Heisenberg 불확정성 원리의 핵심 아이디어임