이산 사인 변환

수학에서 **이산 사인 변환**(, **DST**)은 이산 푸리에 변환(DFT)과 유사한 푸리에 관련 변환이지만, 순수하게 실수 행렬을 사용한다. 이는 대략 두 배 길이의 DFT에서 홀 대칭을 가진 실수 데이터(실수이자 홀함수인 함수의 푸리에 변환은 허수이자 홀함수이기 때문)에 가해지는 허수 부분과 동일하며, 일부 변형에서는 입력 및 출력 데이터가 반 샘플만큼 이동한다.

DST는 실수이자 짝함수인 함수의 DFT와 동일한 이산 코사인 변환(DCT)과 관련이 있다. 경계 조건이 다양한 DCT 및 DST 유형과 어떻게 연관되는지에 대한 일반적인 논의는 DCT 문서를 참조하라. 일반적으로 DST는 x=0에서의 노이만 경계 조건을 디리클레 조건으로 대체함으로써 DCT로부터 유도된다. DCT와 DST 모두 1974년에 나시르 아메드, T. 나타라잔, 그리고 K. R. 라오에 의해 기술되었다. 제1종 DST(DST-I)는 이후 1976년에 아닐 K. 제인에 의해 기술되었고, 제2종 DST(DST-II)는 1978년 H.B. 케크라와 J.K. 솔란카에 의해 기술되었다.

## 응용
DST는 편미분 방정식을 스펙트럼 방법으로 풀 때 널리 사용되며, 여기서 DST의 다양한 변형은 배열의 양 끝단에서 약간씩 다른 홀/짝 경계 조건에 대응한다.

## 비공식적 개요
섬네일|right|350px|N=9개 데이터 포인트(빨간 점)에 대해, 가장 흔한 네 가지 유형의 DST(I-IV 유형)에서 DST 입력 데이터의 암시적인 짝/홀 확장을 나타낸 삽화.

다른 푸리에 관련 변환과 마찬가지로 이산 사인 변환(DST)은 함수나 신호를 서로 다른 진폭과 주파수를 가진 사인 곡선들의 합으로 표현한다. 이산 푸리에 변환(DFT)과 마찬가지로 DST는 유한한 개수의 이산 데이터 포인트에서 함수에 작용한다. DST와 DFT의 명백한 차이점은 전자는 사인 함수만을 사용하는 반면, 후자는 코사인과 사인 모두를(복소지수 형태) 사용한다는 것이다. 그러나 이러한 가시적인 차이는 더 깊은 차이의 결과일 뿐이다. 즉, DST는 DFT나 다른 관련 변환과는 다른 경계 조건을 함의한다.

DFT나 DST 또는 푸리에 급수와 같이 유한한 정의역에서 함수에 작용하는 푸리에 관련 변환은 정의역 외부에서 해당 함수의 확장을 암시적으로 정의하는 것으로 생각할 수 있다. 즉, 함수 f(x)를 사인 곡선들의 합으로 쓰고 나면, 원래의 f(x)가 지정되지 않았던 x에 대해서도 그 합을 계산할 수 있다. DFT는 푸리에 급수와 마찬가지로 원래 함수의 주기적 확장을 함의한다. DST는 사인 변환과 마찬가지로 원래 함수의 홀 확장을 함의한다.

그러나 DST는 유한하고 이산적인 수열에서 작동하기 때문에 연속 사인 변환에는 적용되지 않는 두 가지 문제가 발생한다. 첫째, 정의역의 왼쪽과 오른쪽 경계(즉, 아래 정의에서 각각 최소 n 및 최대 n 경계) 모두에서 함수가 짝수인지 홀수인지 지정해야 한다. 둘째, 함수가 어떤 점을 기준으로 짝수인지 홀수인지 지정해야 한다. 특히, 간격이 일정한 세 개의 데이터 포인트 수열 (a,b,c)를 고려하고 왼쪽 경계가 홀수라고 지정한다고 가정해 보자. 두 가지 합리적인 가능성이 있다. 데이터가 a 이전의 점을 기준으로 홀수인 경우 홀수 확장은 (&minus;c,&minus;b,&minus;a,0,a,b,c)가 되고, 데이터가 a와 이전 점의 중간 지점을 기준으로 홀수인 경우 홀수 확장은 (&minus;c,&minus;b,&minus;a,a,b,c)가 된다.

이러한 선택은 DST의 모든 표준 변형뿐만 아니라 이산 코사인 변환(DCT)으로 이어진다. 각 경계는 짝수 또는 홀수일 수 있고(경계당 2가지 선택), 데이터 포인트 또는 두 데이터 포인트의 중간 지점을 기준으로 대칭일 수 있으므로(경계당 2가지 선택), 총 2 \times 2 \times 2 \times 2 = 16가지 가능성이 존재한다. 이 가능성 중 절반인 왼쪽 경계가 홀수인 경우는 8가지 유형의 DST에 해당하며, 나머지 절반은 8가지 유형의 DCT이다.

이러한 서로 다른 경계 조건은 변환의 응용 분야에 강력한 영향을 미치며, 다양한 DCT 유형에 고유하게 유용한 속성을 부여한다. 가장 직접적으로, 스펙트럼 방법으로 편미분 방정식을 풀기 위해 푸리에 관련 변환을 사용할 때 경계 조건은 해결하려는 문제의 일부로 직접 지정된다.

## 정의
형식적으로 이산 사인 변환은 선형 가역 함수 F : **R**N  **R**N (여기서 **R**은 실수 집합을 나타냄) 또는 이와 동등한 N &times; N 행렬이다. 정의가 약간씩 수정된 여러 DST 변형이 존재한다. N개의 실수 x0,...,xN − 1은 다음 공식 중 하나에 따라 N개의 실수 X0,...,XN − 1로 변환된다.

### DST-I
섬네일|upright=1.35|이산 사인 변환 (https://www.desmos.com/calculator/k5jlr0ykzw).

:\begin{align}X_k &= \sum_{n=0}^{N-1} x_n \sin \left[\frac \pi {N+1} (n+1) (k+1) \right] & k &= 0, \dots, N-1\\
X_{k-1} &= \sum_{n=1}^{N} x_{n-1} \sin \left[\frac {\pi nk} {N+1}\right] & k &= 1, \dots, N\end{align}

DST-I 행렬은 (스케일 인자를 제외하고) 직교행렬이다.

DST-I은 0번째와 중간 지점을 기준으로 홀수 대칭인 실수 수열의 DFT를 1/2로 스케일링한 것과 정확히 동일하다. 예를 들어, N=3인 실수 (a,b,c)의 DST-I은 8개의 실수 (0,a,b,c,0,&minus;c,&minus;b,&minus;a) (홀수 대칭)의 DFT를 1/2로 스케일링한 것과 정확히 동일하다. (반면, DST 유형 II-IV는 해당 DFT에서 반 샘플 이동을 포함한다.) 이것이 사인 함수의 분모에 N&nbsp;+&nbsp;1이 들어가는 이유이다. 해당 DFT는 2(N+1)개의 포인트를 가지며 사인 주파수에 2π/2(N+1)를 가지므로 DST-I은 주파수에 π/(N+1)를 갖는다.

따라서 DST-I은 다음과 같은 경계 조건에 대응한다: xn은 n&nbsp;=&nbsp;−1을 기준으로 홀수이고 n=N을 기준으로 홀수이다. Xk에 대해서도 마찬가지이다.

### DST-II
X_k =
   \sum_{n=0}^{N-1} x_n \sin \left[\frac \pi N \left(n+\frac{1}{2}\right) (k+1)\right] \quad \quad k = 0, \dots, N-1

일부 저자는 XN − 1 항에 1/을 추가로 곱하기도 한다(DST-III의 해당 변경 사항은 아래 참조). 이렇게 하면 DST-II 행렬이 직교행렬이 되지만(스케일 인자 제외), 반 샘플 이동된 입력의 실수-홀수 DFT와의 직접적인 대응 관계는 깨진다.

DST-II는 다음과 같은 경계 조건을 함의한다: xn은 n&nbsp;=&nbsp;−1/2을 기준으로 홀수이고 n&nbsp;=&nbsp;N&nbsp;−&nbsp;1/2을 기준으로 홀수이다. Xk는 k&nbsp;=&nbsp;−1을 기준으로 홀수이고 k&nbsp;=&nbsp;N&nbsp;−&nbsp;1을 기준으로 짝수이다.

### DST-III
X_k = \frac{(-1)^k}{2} x_{N-1} + \sum_{n=0}^{N-2} x_n \sin \left[\frac{\pi}{N} (n+1) \left(k+\frac{1}{2}\right) \right] \quad \quad k = 0, \dots, N-1

일부 저자는 xN − 1 항에 를 추가로 곱한다(DST-II의 해당 변경 사항은 위 참조). 이렇게 하면 DST-III 행렬이 직교행렬이 되지만(스케일 인자 제외), 반 샘플 이동된 출력의 실수-홀수 DFT와의 직접적인 대응 관계는 깨진다.

DST-III은 다음과 같은 경계 조건을 함의한다: xn은 n&nbsp;=&nbsp;−1을 기준으로 홀수이고 n&nbsp;=&nbsp;N&nbsp;−&nbsp;1을 기준으로 짝수이다. Xk는 k&nbsp;=&nbsp;−1/2을 기준으로 홀수이고 k&nbsp;=&nbsp;N&nbsp;−&nbsp;1/2을 기준으로 홀수이다.

### DST-IV
X_k = \sum_{n=0}^{N-1} x_n \sin \left[\frac \pi N  \left(n+\frac{1}{2}\right) \left(k+\frac{1}{2}\right) \right] \quad \quad k = 0, \dots, N-1

DST-IV 행렬은 (스케일 인자를 제외하고) 직교행렬이다.

DST-IV는 다음과 같은 경계 조건을 함의한다: xn은 n&nbsp;=&nbsp;−1/2을 기준으로 홀수이고 n&nbsp;=&nbsp;N&nbsp;−&nbsp;1/2을 기준으로 짝수이다. Xk에 대해서도 마찬가지이다.

### DST V–VIII
DST 유형 I-IV는 짝수 차수의 실수-홀수 DFT와 동일하다. 원칙적으로 논리적으로 홀수 차수인 실수-홀수 DFT에 대응하는 네 가지 추가 유형의 이산 사인 변환(Martucci, 1994)이 존재하며, 이는 사인 인수의 분모에 N+1/2 인수를 가진다. 그러나 이러한 변형은 실제로 거의 사용되지 않는 것으로 보인다.

### 역변환
DST-I의 역변환은 2/(N&nbsp;+&nbsp;1)을 곱한 DST-I이다. DST-IV의 역변환은 2/N을 곱한 DST-IV이다. DST-II의 역변환은 2/N을 곱한 DST-III이다(그 반대도 마찬가지이다).

DFT와 마찬가지로 이러한 변환 정의 앞의 정규화 계수는 단지 관례일 뿐이며 처리 방식에 따라 다르다. 예를 들어, 일부 저자는 역변환에 추가적인 곱셈 인자가 필요하지 않도록 변환에 \sqrt{2/N}을 곱하기도 한다.

## 계산
이러한 공식의 직접적인 적용에는 O(N2) 연산이 필요하지만, 고속 푸리에 변환(FFT)과 유사하게 계산을 분해하여 O(N log N) 복잡도로 동일한 결과를 계산할 수 있다. (O(N) 전처리 및 후처리 단계와 결합된 FFT를 통해 DST를 계산할 수도 있다.)

DST-III 또는 DST-IV는 각각 입력 순서를 뒤집고 다른 모든 출력의 부호를 반전시킴으로써 DCT-III 또는 DCT-IV(이산 코사인 변환 참조)로부터 계산될 수 있으며, DCT-II로부터의 DST-II도 마찬가지이다. 이러한 방식으로 DST의 II-IV 유형은 해당 DCT 유형과 정확히 동일한 수의 산술 연산(덧셈 및 곱셈)을 필요로 한다는 결과가 나온다.

## 일반화
사인 및 쌍곡사인 함수로 구성된 변환군이 존재한다. 이러한 변환은 서로 다른 경계 조건을 가진 얇은 사각형 판의 고유 진동을 기반으로 만들어진다.

## 각주

## 참고 문헌
* S. A. Martucci, "Symmetric convolution and the discrete sine and cosine transforms," IEEE Trans. Signal Process. **SP-42**, 1038–1051 (1994).
* Matteo Frigo and Steven G. Johnson: *FFTW*, FFTW Home Page. A free (GPL) C library that can compute fast DSTs (types I–IV) in one or more dimensions, of arbitrary size. Also M. Frigo and S. G. Johnson, "The Design and Implementation of FFTW3," *Proceedings of the IEEE* **93** (2), 216–231 (2005).
* Takuya Ooura: General Purpose FFT Package, FFT Package 1-dim / 2-dim. Free C & FORTRAN libraries for computing fast DSTs in one, two or three dimensions, power of 2 sizes.
* .
* R. Chivukula and Y. Reznik, "Fast Computing of Discrete Cosine and Sine Transforms of Types VI and VII," Proc. SPIE Vol. 8135, 2011.

분류:푸리에 해석학
분류:이산 변환