Skip to main content
Bounty Ended with 150 reputation awarded by Marcus Müller
added 70 characters in body
Source Link
Royi
  • 20.5k
  • 4
  • 199
  • 240

At first I thought it is about circular convolution, but it is not. After desperate attempts to do it by myself I found thisthe article: Convolution Using Discrete Sine and Cosine Transforms (https://dr.ntu.edu.sg/bitstream/10356/94137/1/Convolution%20Using%20Discrete%20Sine%20and%20Cosine%20Transforms.pdfAlternative Link).

At first I thought it is about circular convolution, but it is not. After desperate attempts to do it by myself I found this article: https://dr.ntu.edu.sg/bitstream/10356/94137/1/Convolution%20Using%20Discrete%20Sine%20and%20Cosine%20Transforms.pdf.

At first I thought it is about circular convolution, but it is not. After desperate attempts to do it by myself I found the article: Convolution Using Discrete Sine and Cosine Transforms (Alternative Link).

added 26 characters in body
Source Link

$\displaystyle C_1\{f\}[n] = \sum_{k=0}^{N} c_k f[k]cos\Bigl[\frac{π}{N}nk\Bigl], \text{where}\ c_k = \left\{ \begin{array}{l} \frac{1}{2}, k≡0\ (mod\ N), \\1,\ \text{otherwise}\end{array} \right. \tag{4}$$\displaystyle C_1\{f\}[n] = \sum_{k=0}^{N} c_k f[k]\\cos\Bigl[\frac{π}{N}nk\Bigl], \text{where}\ c_k = \left\{ \begin{array}{l} \tfrac12, \qquad &k (\mod N)=0, \\ 1,\qquad &\text{otherwise} \\ \end{array} \right. \tag{4}$

DST-I (N+1) points: $$S_1\{f\}[n] = \sum_{k=0}^{N} f[k]sin\Bigl[\frac{π}{N}nk\Bigl]=\sum_{k=0}^{N} c_k f[k] sin\Bigl[\frac{π}{N}nk\Bigl] \tag{5}$$$$S_1\{f\}[n] = \sum_{k=0}^{N} f[k]\sin\Bigl[\frac{π}{N}nk\Bigl]=\sum_{k=0}^{N} c_k f[k] \sin\Bigl[\frac{π}{N}nk\Bigl] \tag{5}$$

$$C_2\{f\}[n] = \sum_{k=0}^{N} f[k]cos\Bigl[\frac{π}{N}\Bigl(k+\frac{1}{2}\Bigl)n\Bigl] \tag{6}$$$$C_2\{f\}[n] = \sum_{k=0}^{N} f[k]\cos\Bigl[\frac{π}{N}\Bigl(k+\tfrac12\Bigl)n\Bigl] \tag{6}$$

$$S_2\{f\}[n] = \sum_{k=0}^{N} f[k]sin\Bigl[\frac{π}{N}\Bigl(k+\frac{1}{2}\Bigl)n\Bigl] \tag{7}$$$$S_2\{f\}[n] = \sum_{k=0}^{N} f[k]\sin\Bigl[\frac{π}{N}\Bigl(k+\tfrac12\Bigl)n\Bigl] \tag{7}$$

Inverse DCT-I: $$C_1^{-1} = \frac{2}{N}C_1 \tag{8}$$ Inverse DST-I: $$S_1^{-1} = \frac{2}{N}S_1 \tag{9}$$ Inverse DCT-II (N+1) points: $$C_2^{-1}\{F_{C_2}\}[k] = \frac{2}{N}\sum_{n=0}^{N} c_n F_{C_2}[n]cos\Bigl[\frac{π}{N}n\Bigl(k+\frac{1}{2}\Bigl)\Bigl] \tag{10}$$$$C_2^{-1}\{F_{C_2}\}[k] = \frac{2}{N}\sum_{n=0}^{N} c_n F_{C_2}[n]\cos\Bigl[\frac{π}{N}n\Bigl(k+\tfrac12\Bigl)\Bigl] \tag{10}$$ $C_2^{-1}\{C_2\{f\}\}[k] = f[k]$ except for $k=N$ there it is going to be $f[N-1]$.

Inverse DST-II (N+1) points: $$C_2^{-1}\{F_{S_2}\}[k] = \frac{2}{N}\sum_{n=0}^{N} c_n F_{S_2}[n]sin\Bigl[\frac{π}{N}n\Bigl(k+\frac{1}{2}\Bigl)\Bigl] \tag{11}$$$$C_2^{-1}\{F_{S_2}\}[k] = \frac{2}{N}\sum_{n=0}^{N} c_n F_{S_2}[n]\sin\Bigl[\frac{π}{N}n\Bigl(k+\tfrac12\Bigl)\Bigl] \tag{11}$$ $S_2^{-1}\{S_2\{f\}\}[k] = f[k]$ except for $k=N$ there it is going to be $-f[N-1]$. Also, they are not interchangeable.

$$\sum_{m=0}^{2N} A[m] c_m cos\Bigl[\frac{π}{N}nm\Bigl] = \sum_{m=0}^{N} p_m(A[m] + A[2N-m]) c_m cos\Bigl[\frac{π}{N}nm\Bigl]$$$$\sum_{m=0}^{2N} A[m] c_m \cos\Bigl[\frac{π}{N}nm\Bigl] = \sum_{m=0}^{N} p_m(A[m] + A[2N-m]) c_m \cos\Bigl[\frac{π}{N}nm\Bigl]$$ $p_m = \frac{1}{2}$$p_m = \tfrac12$ if $m = N$ else $p_m = 1$

from the other hand we have $$\sum_{m=0}^{2N} \frac{A[m]}{c_m} c_m cos\Bigl[\frac{π}{N}nm\Bigl] = \sum_{x=0}^{N}\sum_{y=0}^{N} f[x]g[y]cos\Bigl[\frac{π}{N}n(x+y)\Bigl]$$$$\sum_{m=0}^{2N} \frac{A[m]}{c_m} c_m \cos\Bigl[\frac{π}{N}nm\Bigl] = \sum_{x=0}^{N}\sum_{y=0}^{N} f[x]g[y]\cos\Bigl[\frac{π}{N}n(x+y)\Bigl]$$ $$\sum_{x=0}^{N}\sum_{y=0}^{N} f[x]g[y]cos\Bigl[\frac{π}{N}n(x+y)\Bigl] = \\\sum_{x=0}^{N}\sum_{y=0}^{N} f[x]g[y]\biggl(cos\Bigl[\frac{π}{N}nx\Bigl]cos\Bigl[\frac{π}{N}ny\Bigl] - sin\Bigl[\frac{π}{N}nx\Bigl]sin\Bigl[\frac{π}{N}ny\Bigl]\biggl) = \\ \biggl(\sum_{x=0}^{N} f[x]cos\Bigl[\frac{π}{N}nx\Bigl]\biggl)\cdot\biggl(\sum_{y=0}^{N} g[y]cos\Bigl[\frac{π}{N}ny\Bigl]\biggl) - \biggl(\sum_{x=0}^{N} f[x]sin \Bigl[\frac{π}{N}nx\Bigl]\biggl)\cdot\biggl(\sum_{y=0}^{N} g[y]sin\Bigl[\frac{π}{N}ny\Bigl]\biggl)$$$$\sum_{x=0}^{N}\sum_{y=0}^{N} f[x]g[y]\cos\Bigl[\frac{π}{N}n(x+y)\Bigl] = \\\sum_{x=0}^{N}\sum_{y=0}^{N} f[x]g[y]\biggl(\cos\Bigl[\frac{π}{N}nx\Bigl]\cos\Bigl[\frac{π}{N}ny\Bigl] - \sin\Bigl[\frac{π}{N}nx\Bigl]\sin\Bigl[\frac{π}{N}ny\Bigl]\biggl) = \\ \biggl(\sum_{x=0}^{N} f[x]\cos\Bigl[\frac{π}{N}nx\Bigl]\biggl)\cdot\biggl(\sum_{y=0}^{N} g[y]\cos\Bigl[\frac{π}{N}ny\Bigl]\biggl) - \biggl(\sum_{x=0}^{N} f[x]\sin \Bigl[\frac{π}{N}nx\Bigl]\biggl)\cdot\biggl(\sum_{y=0}^{N} g[y]\sin\Bigl[\frac{π}{N}ny\Bigl]\biggl)$$

$$\sum_{m=0}^{2N} A[m] cos\Bigl[\frac{π}{N}\Bigl(m+\frac{1}{2}\Bigl)n\Bigl] = \sum_{m=0}^{2N-2} A[m] cos\Bigl[\frac{π}{N}\Bigl(m+\frac{1}{2}\Bigl)n\Bigl] = \sum_{m=0}^{N-1} (A[m] + A[2N-1-m]) cos\Bigl[\frac{π}{N}\Bigl(m+\frac{1}{2}\Bigl)n\Bigl] $$$$\sum_{m=0}^{2N} A[m] \cos\Bigl[\frac{π}{N}\Bigl(m+\tfrac12\Bigl)n\Bigl] = \sum_{m=0}^{2N-2} A[m] \cos\Bigl[\frac{π}{N}\Bigl(m+\tfrac12\Bigl)n\Bigl] = \sum_{m=0}^{N-1} (A[m] + A[2N-1-m]) \cos\Bigl[\frac{π}{N}\Bigl(m+\tfrac12\Bigl)n\Bigl] $$

And the expression is going to be: $$\sum_{m=0}^{2N} A[m] cos\Bigl[\frac{π}{N}\Bigl(m+\frac{1}{2}\Bigl)n\Bigl] = \sum_{m=0}^{2N} A[m] \Bigl(cos\Bigl[\frac{πn}{2N}\Bigl]cos\Bigl[\frac{π}{N}kn\Bigl] - sin\Bigl[\frac{πn}{2N}\Bigl]sin\Bigl[\frac{π}{N}kn\Bigl]\Bigl) = \\ cos\Bigl[\frac{πn}{2N}\Bigl](F^{/}_{C_1}G^{/}_{C_1} - F_{S_1}G_{S_1}) - sin\Bigl[\frac{πn}{2N}\Bigl](F^{/}_{C_1}G_{S_1} + F_{S_1}G^{/}_{C_1}) = \\ =F^{/}_{C_1}(cos\Bigl[\frac{πn}{2N}\Bigl]G^{/}_{C_1} - sin\Bigl[\frac{πn}{2N}\Bigl]G_{S_1}) - F_{S_1}(cos\Bigl[\frac{πn}{2N}\Bigl]G_{S_1}+ sin\Bigl[\frac{πn}{2N}\Bigl]G^{/}_{C_1}) = \\ =F^{/}_{C_1}G_{C_2} - F_{S_1}G_{S_2} = G^{/}_{C_1}F_{C_2} - G_{S_1}F_{S_2} $$$$\sum_{m=0}^{2N} A[m] \cos\Bigl[\frac{π}{N}\Bigl(m+\tfrac12\Bigl)n\Bigl] = \sum_{m=0}^{2N} A[m] \Bigl(\cos\Bigl[\frac{πn}{2N}\Bigl]\cos\Bigl[\frac{π}{N}kn\Bigl] - \sin\Bigl[\frac{πn}{2N}\Bigl]\sin\Bigl[\frac{π}{N}kn\Bigl]\Bigl) = \\ \cos\Bigl[\frac{πn}{2N}\Bigl](F^{/}_{C_1}G^{/}_{C_1} - F_{S_1}G_{S_1}) - \sin\Bigl[\frac{πn}{2N}\Bigl](F^{/}_{C_1}G_{S_1} + F_{S_1}G^{/}_{C_1}) = \\ =F^{/}_{C_1}(\cos\Bigl[\frac{πn}{2N}\Bigl]G^{/}_{C_1} - \sin\Bigl[\frac{πn}{2N}\Bigl]G_{S_1}) - F_{S_1}(\cos\Bigl[\frac{πn}{2N}\Bigl]G_{S_1}+ \sin\Bigl[\frac{πn}{2N}\Bigl]G^{/}_{C_1}) = \\ =F^{/}_{C_1}G_{C_2} - F_{S_1}G_{S_2} = G^{/}_{C_1}F_{C_2} - G_{S_1}F_{S_2} $$

$\displaystyle C_1\{f\}[n] = \sum_{k=0}^{N} c_k f[k]cos\Bigl[\frac{π}{N}nk\Bigl], \text{where}\ c_k = \left\{ \begin{array}{l} \frac{1}{2}, k≡0\ (mod\ N), \\1,\ \text{otherwise}\end{array} \right. \tag{4}$

DST-I (N+1) points: $$S_1\{f\}[n] = \sum_{k=0}^{N} f[k]sin\Bigl[\frac{π}{N}nk\Bigl]=\sum_{k=0}^{N} c_k f[k] sin\Bigl[\frac{π}{N}nk\Bigl] \tag{5}$$

$$C_2\{f\}[n] = \sum_{k=0}^{N} f[k]cos\Bigl[\frac{π}{N}\Bigl(k+\frac{1}{2}\Bigl)n\Bigl] \tag{6}$$

$$S_2\{f\}[n] = \sum_{k=0}^{N} f[k]sin\Bigl[\frac{π}{N}\Bigl(k+\frac{1}{2}\Bigl)n\Bigl] \tag{7}$$

Inverse DCT-I: $$C_1^{-1} = \frac{2}{N}C_1 \tag{8}$$ Inverse DST-I: $$S_1^{-1} = \frac{2}{N}S_1 \tag{9}$$ Inverse DCT-II (N+1) points: $$C_2^{-1}\{F_{C_2}\}[k] = \frac{2}{N}\sum_{n=0}^{N} c_n F_{C_2}[n]cos\Bigl[\frac{π}{N}n\Bigl(k+\frac{1}{2}\Bigl)\Bigl] \tag{10}$$ $C_2^{-1}\{C_2\{f\}\}[k] = f[k]$ except for $k=N$ there it is going to be $f[N-1]$.

Inverse DST-II (N+1) points: $$C_2^{-1}\{F_{S_2}\}[k] = \frac{2}{N}\sum_{n=0}^{N} c_n F_{S_2}[n]sin\Bigl[\frac{π}{N}n\Bigl(k+\frac{1}{2}\Bigl)\Bigl] \tag{11}$$ $S_2^{-1}\{S_2\{f\}\}[k] = f[k]$ except for $k=N$ there it is going to be $-f[N-1]$. Also, they are not interchangeable.

$$\sum_{m=0}^{2N} A[m] c_m cos\Bigl[\frac{π}{N}nm\Bigl] = \sum_{m=0}^{N} p_m(A[m] + A[2N-m]) c_m cos\Bigl[\frac{π}{N}nm\Bigl]$$ $p_m = \frac{1}{2}$ if $m = N$ else $p_m = 1$

from the other hand we have $$\sum_{m=0}^{2N} \frac{A[m]}{c_m} c_m cos\Bigl[\frac{π}{N}nm\Bigl] = \sum_{x=0}^{N}\sum_{y=0}^{N} f[x]g[y]cos\Bigl[\frac{π}{N}n(x+y)\Bigl]$$ $$\sum_{x=0}^{N}\sum_{y=0}^{N} f[x]g[y]cos\Bigl[\frac{π}{N}n(x+y)\Bigl] = \\\sum_{x=0}^{N}\sum_{y=0}^{N} f[x]g[y]\biggl(cos\Bigl[\frac{π}{N}nx\Bigl]cos\Bigl[\frac{π}{N}ny\Bigl] - sin\Bigl[\frac{π}{N}nx\Bigl]sin\Bigl[\frac{π}{N}ny\Bigl]\biggl) = \\ \biggl(\sum_{x=0}^{N} f[x]cos\Bigl[\frac{π}{N}nx\Bigl]\biggl)\cdot\biggl(\sum_{y=0}^{N} g[y]cos\Bigl[\frac{π}{N}ny\Bigl]\biggl) - \biggl(\sum_{x=0}^{N} f[x]sin \Bigl[\frac{π}{N}nx\Bigl]\biggl)\cdot\biggl(\sum_{y=0}^{N} g[y]sin\Bigl[\frac{π}{N}ny\Bigl]\biggl)$$

$$\sum_{m=0}^{2N} A[m] cos\Bigl[\frac{π}{N}\Bigl(m+\frac{1}{2}\Bigl)n\Bigl] = \sum_{m=0}^{2N-2} A[m] cos\Bigl[\frac{π}{N}\Bigl(m+\frac{1}{2}\Bigl)n\Bigl] = \sum_{m=0}^{N-1} (A[m] + A[2N-1-m]) cos\Bigl[\frac{π}{N}\Bigl(m+\frac{1}{2}\Bigl)n\Bigl] $$

And the expression is going to be: $$\sum_{m=0}^{2N} A[m] cos\Bigl[\frac{π}{N}\Bigl(m+\frac{1}{2}\Bigl)n\Bigl] = \sum_{m=0}^{2N} A[m] \Bigl(cos\Bigl[\frac{πn}{2N}\Bigl]cos\Bigl[\frac{π}{N}kn\Bigl] - sin\Bigl[\frac{πn}{2N}\Bigl]sin\Bigl[\frac{π}{N}kn\Bigl]\Bigl) = \\ cos\Bigl[\frac{πn}{2N}\Bigl](F^{/}_{C_1}G^{/}_{C_1} - F_{S_1}G_{S_1}) - sin\Bigl[\frac{πn}{2N}\Bigl](F^{/}_{C_1}G_{S_1} + F_{S_1}G^{/}_{C_1}) = \\ =F^{/}_{C_1}(cos\Bigl[\frac{πn}{2N}\Bigl]G^{/}_{C_1} - sin\Bigl[\frac{πn}{2N}\Bigl]G_{S_1}) - F_{S_1}(cos\Bigl[\frac{πn}{2N}\Bigl]G_{S_1}+ sin\Bigl[\frac{πn}{2N}\Bigl]G^{/}_{C_1}) = \\ =F^{/}_{C_1}G_{C_2} - F_{S_1}G_{S_2} = G^{/}_{C_1}F_{C_2} - G_{S_1}F_{S_2} $$

$\displaystyle C_1\{f\}[n] = \sum_{k=0}^{N} c_k f[k]\\cos\Bigl[\frac{π}{N}nk\Bigl], \text{where}\ c_k = \left\{ \begin{array}{l} \tfrac12, \qquad &k (\mod N)=0, \\ 1,\qquad &\text{otherwise} \\ \end{array} \right. \tag{4}$

DST-I (N+1) points: $$S_1\{f\}[n] = \sum_{k=0}^{N} f[k]\sin\Bigl[\frac{π}{N}nk\Bigl]=\sum_{k=0}^{N} c_k f[k] \sin\Bigl[\frac{π}{N}nk\Bigl] \tag{5}$$

$$C_2\{f\}[n] = \sum_{k=0}^{N} f[k]\cos\Bigl[\frac{π}{N}\Bigl(k+\tfrac12\Bigl)n\Bigl] \tag{6}$$

$$S_2\{f\}[n] = \sum_{k=0}^{N} f[k]\sin\Bigl[\frac{π}{N}\Bigl(k+\tfrac12\Bigl)n\Bigl] \tag{7}$$

Inverse DCT-I: $$C_1^{-1} = \frac{2}{N}C_1 \tag{8}$$ Inverse DST-I: $$S_1^{-1} = \frac{2}{N}S_1 \tag{9}$$ Inverse DCT-II (N+1) points: $$C_2^{-1}\{F_{C_2}\}[k] = \frac{2}{N}\sum_{n=0}^{N} c_n F_{C_2}[n]\cos\Bigl[\frac{π}{N}n\Bigl(k+\tfrac12\Bigl)\Bigl] \tag{10}$$ $C_2^{-1}\{C_2\{f\}\}[k] = f[k]$ except for $k=N$ there it is going to be $f[N-1]$.

Inverse DST-II (N+1) points: $$C_2^{-1}\{F_{S_2}\}[k] = \frac{2}{N}\sum_{n=0}^{N} c_n F_{S_2}[n]\sin\Bigl[\frac{π}{N}n\Bigl(k+\tfrac12\Bigl)\Bigl] \tag{11}$$ $S_2^{-1}\{S_2\{f\}\}[k] = f[k]$ except for $k=N$ there it is going to be $-f[N-1]$. Also, they are not interchangeable.

$$\sum_{m=0}^{2N} A[m] c_m \cos\Bigl[\frac{π}{N}nm\Bigl] = \sum_{m=0}^{N} p_m(A[m] + A[2N-m]) c_m \cos\Bigl[\frac{π}{N}nm\Bigl]$$ $p_m = \tfrac12$ if $m = N$ else $p_m = 1$

from the other hand we have $$\sum_{m=0}^{2N} \frac{A[m]}{c_m} c_m \cos\Bigl[\frac{π}{N}nm\Bigl] = \sum_{x=0}^{N}\sum_{y=0}^{N} f[x]g[y]\cos\Bigl[\frac{π}{N}n(x+y)\Bigl]$$ $$\sum_{x=0}^{N}\sum_{y=0}^{N} f[x]g[y]\cos\Bigl[\frac{π}{N}n(x+y)\Bigl] = \\\sum_{x=0}^{N}\sum_{y=0}^{N} f[x]g[y]\biggl(\cos\Bigl[\frac{π}{N}nx\Bigl]\cos\Bigl[\frac{π}{N}ny\Bigl] - \sin\Bigl[\frac{π}{N}nx\Bigl]\sin\Bigl[\frac{π}{N}ny\Bigl]\biggl) = \\ \biggl(\sum_{x=0}^{N} f[x]\cos\Bigl[\frac{π}{N}nx\Bigl]\biggl)\cdot\biggl(\sum_{y=0}^{N} g[y]\cos\Bigl[\frac{π}{N}ny\Bigl]\biggl) - \biggl(\sum_{x=0}^{N} f[x]\sin \Bigl[\frac{π}{N}nx\Bigl]\biggl)\cdot\biggl(\sum_{y=0}^{N} g[y]\sin\Bigl[\frac{π}{N}ny\Bigl]\biggl)$$

$$\sum_{m=0}^{2N} A[m] \cos\Bigl[\frac{π}{N}\Bigl(m+\tfrac12\Bigl)n\Bigl] = \sum_{m=0}^{2N-2} A[m] \cos\Bigl[\frac{π}{N}\Bigl(m+\tfrac12\Bigl)n\Bigl] = \sum_{m=0}^{N-1} (A[m] + A[2N-1-m]) \cos\Bigl[\frac{π}{N}\Bigl(m+\tfrac12\Bigl)n\Bigl] $$

And the expression is going to be: $$\sum_{m=0}^{2N} A[m] \cos\Bigl[\frac{π}{N}\Bigl(m+\tfrac12\Bigl)n\Bigl] = \sum_{m=0}^{2N} A[m] \Bigl(\cos\Bigl[\frac{πn}{2N}\Bigl]\cos\Bigl[\frac{π}{N}kn\Bigl] - \sin\Bigl[\frac{πn}{2N}\Bigl]\sin\Bigl[\frac{π}{N}kn\Bigl]\Bigl) = \\ \cos\Bigl[\frac{πn}{2N}\Bigl](F^{/}_{C_1}G^{/}_{C_1} - F_{S_1}G_{S_1}) - \sin\Bigl[\frac{πn}{2N}\Bigl](F^{/}_{C_1}G_{S_1} + F_{S_1}G^{/}_{C_1}) = \\ =F^{/}_{C_1}(\cos\Bigl[\frac{πn}{2N}\Bigl]G^{/}_{C_1} - \sin\Bigl[\frac{πn}{2N}\Bigl]G_{S_1}) - F_{S_1}(\cos\Bigl[\frac{πn}{2N}\Bigl]G_{S_1}+ \sin\Bigl[\frac{πn}{2N}\Bigl]G^{/}_{C_1}) = \\ =F^{/}_{C_1}G_{C_2} - F_{S_1}G_{S_2} = G^{/}_{C_1}F_{C_2} - G_{S_1}F_{S_2} $$

added 9 characters in body
Source Link
dogtype
  • 366
  • 3
  • 5

N for data: $f[0]\ldots f[N-1]$ and $f[N] = 0$: DST-II (N+1) points, N for data:

DST-II (N+1) points, N for data:

$f[0]\ldots f[N-1]$ and $f[N] = 0$:

N for data: $f[0]\ldots f[N-1]$ and $f[N] = 0$: DST-II (N+1) points, N for data: $f[0]\ldots f[N-1]$ and $f[N] = 0$:

N for data: $f[0]\ldots f[N-1]$ and $f[N] = 0$

DST-II (N+1) points, N for data:

$f[0]\ldots f[N-1]$ and $f[N] = 0$:

edited body
Source Link
dogtype
  • 366
  • 3
  • 5
Loading
Source Link
dogtype
  • 366
  • 3
  • 5
Loading