수정 이산 코사인 변환

1. 개요

수정 이산 코사인 변환(MDCT)은 입력의 절반 개수만큼의 출력을 갖는 겹쳐진 변환으로, 실수 집합에서 정의되는 선형 함수이다. MDCT는 시간 영역 에일리어싱 제거(TDAC) 기술을 사용하여 원래 데이터를 복원할 수 있는 역변환인 IMDCT를 갖는다. MDCT는 고속 푸리에 변환(FFT)과 유사한 방식으로 계산할 수 있으며, 윈도우 함수를 사용하여 변환 속성을 개선할 수 있다. MDCT는 DCT-IV와 밀접한 관련이 있으며, 오디오 압축 등 다양한 분야에서 사용된다.

2. 정의

MDCT는 다른 푸리에 관련 변환과 달리 입력의 절반 개수만큼의 출력을 갖는 겹쳐진 변환이다. 선형 함수 F : R^2N → R^N (여기서 R은 실수 집합)으로, 2N개의 실수 x₀, ..., x_2N-1은 다음 공식에 따라 N개의 실수 X₀, ..., X_N-1로 변환된다.

:$X\_k\; =\; \backslash sum\_\{n=0\}^\{2N-1\}\; x\_n\; \backslash cos\; \backslash left[\backslash frac\{\backslash pi\}\{N\}\; \backslash left(n+\backslash frac\{1\}\{2\}+\backslash frac\{N\}\{2\}\backslash right)\; \backslash left(k+\backslash frac\{1\}\{2\}\backslash right)\; \backslash right]$

(변환 앞의 정규화 계수는 규약에 따라 달라진다. 아래에서 설명할 MDCT와 IMDCT의 정규화 곱만이 제약된다.)

2.1. 역변환

역 MDCT는 IMDCT로 알려져 있다. 입력과 출력의 수가 다르기 때문에, 언뜻 보면 MDCT가 가역적이지 않은 것처럼 보일 수 있다. 그러나 완벽한 가역성은 겹치는 블록들의 연속적인 겹침 IMDCT들을 더하여 달성되며, 이는 오류를 상쇄시키고 원래의 데이터를 복원하게 한다. 이 기술은 시간 영역 에일리어싱 제거 (TDAC)로 알려져 있다.

IMDCT는 N개의 실수 X₀, ..., X_N-1을 다음 공식에 따라 2N개의 실수 y₀, ..., y_2N-1로 변환한다.

:$y\_n\; =\; \backslash frac\{1\}\{N\}\; \backslash sum\_\{k=0\}^\{N-1\}\; X\_k\; \backslash cos\; \backslash left[\backslash frac\{\backslash pi\}\{N\}\; \backslash left(n+\backslash frac\{1\}\{2\}+\backslash frac\{N\}\{2\}\backslash right)\; \backslash left(k+\backslash frac\{1\}\{2\}\backslash right)\; \backslash right]$

(DCT-IV와 같이, 직교 변환의 경우 역변환은 정변환과 동일한 형태를 갖는다.)

일반적인 윈도우 정규화(아래 참조)를 사용하는 윈도우 MDCT의 경우, IMDCT 앞에 있는 정규화 계수는 2를 곱해야 한다(즉, 2/N이 됨).

2.2. 계산

고속 푸리에 변환(FFT)과 같이 재귀적으로 계산을 인수분해하여 O(N log N)의 복잡도로 MDCT 공식을 직접 적용하면 O(N²) 연산이 필요한 경우보다 계산 복잡도를 줄일 수 있다. 또한, O(N)개의 전처리 및 후처리 단계를 통해 DFT(FFT) 또는 DCT와 같은 다른 변환으로도 MDCT를 계산할 수 있다.

3. 윈도우 함수

일반적인 신호 압축에서, 변환 속성은 수정 이산 코사인 변환(MDCT)에서 x_n에 곱해지고, 역 MDCT(IMDCT) 공식에서 y_n에 곱해지는 윈도우 함수 w_n (n = 0, ..., 2N−1)을 사용하여 개선된다. 윈도우 함수는 n = 0 및 2N 경계에서 0으로 부드럽게 수렴하여 불연속성을 피하게 한다. 즉, MDCT 전 또는 IMDCT 후에 데이터에 윈도우 함수가 적용된다. 원칙적으로 x와 y는 서로 다른 윈도우 함수를 가질 수 있으며, 블록마다 변경될 수도 있지만, 단순성을 위해 동일한 크기의 블록에 동일한 윈도우 함수를 사용하는 경우를 고려한다.

대칭 윈도우 w_n = w_2N−1−n에 대해, 윈도우가 Princen-Bradley 조건

:$w\_n^2\; +\; w\_\{n\; +\; N\}^2\; =\; 1$.

을 만족하면 변환은 가역적이다(TDAC가 작동한다).

3.1. 윈도우 함수의 종류

다양한 윈도우 함수가 사용된다. 변조된 랩 변환(MLT)으로 알려진 형태를 생성하는 윈도우는 다음과 같다.

:$w\_n\; =\; \backslash sin\; \backslash left[\backslash frac\{\backslash pi\}\{2N\}\; \backslash left(n+\backslash frac\{1\}\{2\}\backslash right)\; \backslash right]$

이것은 MP3 및 MPEG-2 AAC에 사용된다.

:$w\_n\; =\; \backslash sin\; \backslash left(\; \backslash frac\{\backslash pi\}\{2\}\; \backslash sin^2\; \backslash left[\backslash frac\{\backslash pi\}\{2N\}\; \backslash left(n+\backslash frac\{1\}\{2\}\backslash right)\; \backslash right]\; \backslash right)$

위 식은 Vorbis에 사용된다. AC-3는 Kaiser–Bessel 유도(KBD) 윈도우를 사용하며, MPEG-4 AAC도 KBD 윈도우를 사용할 수 있다.

MDCT에 적용되는 윈도우는 다른 유형의 신호 분석에 사용되는 윈도우와 다르다는 점에 유의해야 한다. MDCT 윈도우는 Princen–Bradley 조건을 충족해야 하기 때문이다. 이러한 차이점의 한 가지 이유는 MDCT 윈도우가 MDCT(분석) 및 IMDCT(합성) 모두에 두 번 적용되기 때문이다.

4. DCT-IV와의 관계 및 TDAC의 기원

짝수 N에 대해 수정 이산 코사인 변환(MDCT)는 기본적으로 DCT-IV(이산 코사인 변환#DCT-IV)와 동일하며, 입력은 N/2만큼 이동하고 두 개의 N 블록 데이터가 한 번에 변환된다. 이러한 등가성을 통해 시간 영역 에일리어싱 제거(TDAC)와 같은 중요한 속성을 도출할 수 있다.

MDCT와 DCT-IV의 관계를 정확히 이해하려면, DCT-IV가 교대로 짝수/홀수 경계 조건을 가진다는 것을 알아야 한다. 왼쪽 경계(n = -1/2 부근)에서는 짝수, 오른쪽 경계(n = N - 1/2 부근)에서는 홀수이다. 이는 이산 푸리에 변환(DFT)와 같은 주기적 경계가 아니다. 입력 배열 x를 (x, -x_R, -x, x_R, ...) 등으로 확장할 수 있다. 여기서 x_R은 x를 역순으로 나타낸다.

2N개의 입력과 N개의 출력을 갖는 MDCT에서 입력을 크기가 N/2인 네 개의 블록 (a, b, c, d)으로 나눈다. MDCT 정의의 +N/2 항에서 이 블록들을 오른쪽으로 N/2만큼 이동하면 (b, c, d)가 N개의 DCT-IV 입력의 끝을 넘어 확장되므로, 경계 조건에 따라 "접어야" 한다.

따라서 2N개의 입력 (a, b, c, d)의 MDCT는 N개의 입력 (-c_R-d, a-b_R)에 대한 DCT-IV와 같다. 여기서 R은 역순을 나타낸다.

IMDCT 공식은 DCT-IV의 1/2이며, 출력은 경계 조건을 통해 길이 2N으로 확장되고 왼쪽으로 N/2만큼 이동된다. 역 DCT-IV는 입력 (-c_R-d, a-b_R)를 다시 제공하며, 경계 조건을 통해 확장되고 이동되면 IMDCT(MDCT(a, b, c, d)) = (a-b_R, b-a_R, c+d_R, d+c_R) / 2를 얻는다.

IMDCT 출력의 절반은 중복되며, b-a_R = -(a-b_R)_R와 같다. 입력을 크기 N의 블록 A = (a, b), B = (c, d)로 그룹화하면, IMDCT(MDCT(A, B)) = (A-A_R, B+B_R) / 2로 표현할 수 있다.

연속하는 50% 중첩된 2N 블록 (B, C)의 MDCT를 계산하면, IMDCT는 (B-B_R, C+C_R) / 2를 생성한다. 이 값이 이전 IMDCT 결과와 중첩된 절반에서 더해지면 역순 항이 상쇄되고 B를 얻어 원래 데이터를 복구한다.

"시간 영역 에일리어싱 제거"라는 용어는 논리적 DCT-IV의 경계를 넘어 확장되는 입력 데이터가 나이퀴스트 주파수를 초과하는 주파수가 낮은 주파수로 에일리어싱되는 것처럼, 데이터가 시간 영역에서 에일리어싱되기 때문에 붙여졌다. c-d_R 등의 조합은 더할 때 취소되도록 정확한 부호를 갖는다.

홀수 N의 경우, N/2는 정수가 아니므로 MDCT는 DCT-IV의 시프트 순열이 아니다. 이 경우, 반 샘플만큼 추가 시프트하면 MDCT/IMDCT가 DCT-III/II와 동등해진다.

4.1. TDAC for the windowed MDCT

위에서 TDAC(시간 영역 에일리어싱 제거) 속성은 일반적인 MDCT(수정 이산 코사인 변환)에 대해 증명되었으며, 겹치는 절반에서 연속적인 블록의 IMDCT(역 MDCT)를 더하면 원본 데이터를 복구할 수 있음을 보여주었다. 윈도우가 적용된 MDCT에 대한 이 역 속성의 유도는 약간 더 복잡하다.

크기가 N인 블록 A, B, C에 대해, 2N개의 입력 (A,B)와 (B,C)의 겹치는 연속적인 집합을 고려해 보자. 위에서 $(A,B)$와 $(B,C)$가 MDCT되고, IMDCT되고, 겹치는 절반에서 더해지면 $(B+B\_R)\; /\; 2\; +\; (B-B\_R)\; /\; 2\; =\; B$, 즉 원본 데이터를 얻는 것을 기억해야 한다.

이제 MDCT 입력 및 IMDCT 출력을 길이 2N의 윈도우 함수로 곱한다고 가정한다. 위와 마찬가지로 대칭 윈도우 함수를 가정하며, 따라서 W가 길이 N 벡터이고 R이 이전과 같이 반전을 나타내는 $(W,W\_R)$ 형태이다. 그러면 Princen-Bradley 조건은 $W^2\; +\; W\_R^2\; =\; (1,1,\backslash ldots)$로 쓸 수 있으며, 제곱과 덧셈은 요소별로 수행된다.

따라서 $(A,B)$를 MDCT하는 대신, 이제 $(WA,W\_R\; B)$를 MDCT한다(모든 곱셈은 요소별로 수행됨). 이것이 IMDCT되고 다시 (요소별로) 윈도우 함수로 곱해지면, 마지막 N 절반은 다음과 같다.

:$W\_R\; \backslash cdot\; (W\_R\; B+(W\_R\; B)\_R)\; =W\_R\; \backslash cdot\; (W\_R\; B+W\; B\_R)\; =\; W\_R^2\; B+WW\_R\; B\_R$.

(IMDCT 정규화가 윈도우된 경우에 2의 인수로 다르기 때문에, 더 이상 1/2를 곱하지 않는다.)

마찬가지로, $(B,C)$의 윈도우 MDCT 및 IMDCT는 처음 N 절반에서 다음을 생성한다.

:$W\; \backslash cdot\; (WB\; -\; W\_R\; B\_R)\; =\; W^2\; B\; -\; W\; W\_R\; B\_R$.

이 두 절반을 더하면 다음을 얻는다.

:$(W\_R^2\; B+WW\_R\; B\_R)\; +\; (W^2\; B\; -\; W\; W\_R\; B\_R)=\; \backslash left(W\_R^2\; +\; W^2\backslash right)B\; =\; B,$

원본 데이터를 복구한다.