Transformada discreta de seno

Existem versões diferentes da transformada discreta de seno.

Em matemática, a transformada discreta de seno (DST, do inglês Discrete Sine Transform) é a versão da transformada de seno para um domínio discreto. Na verdade, podem-se definir 4 tipos diferentes de DST, de acordo com critérios diversos; essas transformadas são denotadas DST1, DST2, DST3 e DST4 ou DST-I, DST-II, DST-III e DST-IV

Transformadas discretas, ao contrário das transformadas contínuas, aplicam-se não a funções contínuas mas a amostras obtidas destas. A partir de uma função contínua f(t) obtém-se uma sequência de n valores f(k), sendo k um número inteiro de 0 a n-1; a transformada discreta de seno da sequência f(k) é uma outra sequência, que chamaremos S(k), dada pelas expressões de definição. A sequência original pode ser recuperada a partir da sequência S(k) por meio das expressões de definição da transformação inversa. A amostragem deve ser executada sobre um intervalo de comprimento τ, suficiente para que todas as componentes significativas de f(t) estejam representadas devidamente em f(k) (ver Taxa de amostragem); assume-se que o intervalo Δt entre as amostragens é fixo.

A recuperação da sequência original pela aplicação da transformada inversa assume que a função f(t) é nula para t < 0 e também que ela é uma função "ímpar", no sentido de termos f(k) = - f(n-k) no intervalo considerado.

A DST possui as propriedade notáveis de:

• ser mais simples que a transformada discreta de Fourier e possuir propriedades similares, e assim se prestar melhor à solução de problemas de equações diferenciais com condições de contorno tais que a impliquem na presença de somente funções ímpares na resposta
• se aproximar assintoticamente da transformada de Karhunen-Loève, que é, do ponto de vista teórico, ótima sob vários aspectos importantes para o processamento digital de sinais, apresentando sobre esta a vantagem apreciável de ser independente da função de entrada.

Definições

Se chamarmos f_k e S_k ao k-ésimo coeficiente de f(k) e S(k), respectivamente, podemos definir a transformada discreta de seno de tipo 1 (DST1) por meio da expressão seguinte:

$S_{k}\;=\;{\sqrt {\frac {2}{n}}}\cdot \sum _{j\;=1}^{n-1}f_{j}\cdot \sin \left({\frac {jk\pi }{n}}\right)\;\;\;\;\;(1a)$

Vemos que a sequência S(k) terá apenas n-1 valores, porque os coeficientes extremos devem ser nulos: tanto k quanto j situam-se no intervalo [1,n-1], e não no intervalo [0,n-1], como é usual na definição de transformadas discretas. A transformada inversa é dada por

$f_{k}\;=\;{\sqrt {\frac {2}{n}}}\cdot \sum _{j\;=1}^{n-1}S_{j}\cdot \sin \left({\frac {jk\pi }{n}}\right)\;\;\;\;\;(2a)$

também com k e j no intervalo [1,n-1]. Note-se a simetria entre a transformação direta e a inversa, e a similaridade com as transformações contínuas correspondentes.

Alternativamente, pode-se definir a DST1 como a matriz que, multiplicada por f(k), resulta em S(k); em notação matricial, S = D_s · f. Se denotarmos os coeficientes da matriz D_s por s_jk, podemos escrever

$s_{jk}\;=\;{\sqrt {\frac {2}{n}}}\cdot \sin \left({\frac {jk\pi }{n}}\right)\qquad |\;k,j\in [1,n-1]\qquad (3a)$

Como a transformada de seno é simétrica, a mesma matriz serve para a obtenção da inversa. Assim, podemos escrever f = D_s · S.

A título de exemplo, eis a matriz S para n = 4:

$\mathbf {S} \;=\;\left({\begin{matrix}{\frac {1}{2}}&{\sqrt {2}}&{\frac {1}{2}}\\{\sqrt {2}}&0&-{\sqrt {2}}\\{\frac {1}{2}}&-{\sqrt {2}}&{\frac {1}{2}}\end{matrix}}\right)$

Propriedades

Ortonormalidade

A matriz da DST1 (D_s) é unitária e composta de vetores coluna ortogonais. Essas duas propriedades implicam que esses vetores formam uma base ortonormal. Isso é expresso matematicamente por meio do produto interno:

$\langle \mathbf {d} _{i},\mathbf {d} _{j}\rangle \;=\;\mathbf {d} _{i}\cdot \mathbf {d} _{j}^{T}\;=\;\delta _{ij}\qquad (4a)$

onde d_k é um vetor coluna qualquer de D_s, e δ é o delta de Kronecker.

Escalamento no domínio do tempo

Seja f(k) a sequência de valores amostrados a partir de f(t), e g(k) a sequência de valores amostrados a partir de g(t), segundo critérios idênticos (em particular, o número de amostras n e o intervalo Δt entre as mesmas). Seja g(t) = f(at). Como a transformação não trabalha diretamente com o tempo, e sim sobre sequências de valores amostrados, uma mudança na escala de tempo não altera a transformada. Podemos escrever

${\mathcal {DST}}\{f(k)\}\;=\;{\mathcal {DST}}\{g(k)\}\qquad (4b)$

Nisso a versão discreta da transformada de seno difere da versão contínua.

Deslocamento no tempo

Seja f(k) a sequência de valores amostrados a partir de f(t), e g(k) a sequência de valores amostrados a partir de g(t), segundo critérios idênticos (em particular, o número de amostras n e o intervalo Δt entre as mesmas), e seja g(t) = f(t + Δt). Nesse caso, é óbvio que g_k = f_k+1 para 0 ≤ k < n. Demonstra-se que:

$G_{k}\;=\;\cos \left({\frac {k\pi }{n}}\right)\cdot s_{k}\;-\;\sin \left({\frac {k\pi }{n}}\right)\cdot c_{k}\;+\ {\sqrt {\frac {2}{n}}}\;\sin \left({\frac {k\pi }{n}}\right)\cdot \left[{\frac {f_{0}}{\sqrt {2}}}\;-\;\left(1\;-\;{\frac {1}{\sqrt {2}}}\right)\cdot (-1)^{k}\cdot f_{n-1}\right]\qquad (4c)$

onde G_k é o k-ésimo coeficiente da transformada discreta de seno de g(k), s_k é o k-ésimo coeficiente da transformada discreta de seno de f(k), c_k é o k-ésimo coeficiente da transformada discreta de cosseno de f(k) e f_k é o k-ésimo coeficiente de f(k).

Diferenciação

Num domínio discreto, o operador de diferença Δ tem papel análogo ao do operador diferencial em um domínio contínuo. Seja f(k) a sequência de valores amostrados a partir de f(t), e g(k) a sequência de valores amostrados a partir de g(t), segundo critérios idênticos (em particular, o número de amostras n e o intervalo Δt entre as mesmas), e seja g(t) = f(t + Δt). A derivada de f(t) pode ser aproximada por uma função h(t) tal que

$h(t)\;=\;{\frac {g(t)\;-\;f(t)}{\Delta t}}\;\approx \;f'(t)$

Nesse caso, a aplicação do operador de diferença a f(k) resulta numa nova sequência h(k); podemos escrever Δf(k) = h(k). Os coeficientes de h(k) serão tais que h_k = g_k - f_k = f_k+1 - f_k, para 0 ≤ k < n. A DST1 de h(k) será dada por

${\mathcal {DST}}\{h(k)\}\;=\;{\mathcal {DST}}\{g(k)\}\;-\;{\mathcal {DST}}\{f(k)\}\qquad (4c)$

devido à propriedade básica de linearidade da transformação. É óbvio que h(k) está relacionada a h(t); os coeficientes de h(k) são os valores amostrados de h(t) multiplicados pela constante Δt. Como h(t) aproxima f'(t), podemos escrever

${\mathcal {DST}}\{h(k)\}\;=\;{\frac {1}{\Delta t}}\cdot {\mathcal {DST}}\{f'(k)\}$

onde f'(k) é a sequência de valores amostrados de f'(t). Comparando-se a expressão (4c) com as expressões para a transformada de seno de f'(t), a derivada de f(t), percebe-se que neste caso a versão discreta se comporta de forma bastante diferente da versão contínua.

Da mesma forma, o comportamento da DST1 com relação à integração no domínio do tempo, à integração no domínio da frequência e à convolução não são similares ao da transformada contínua de seno. Essa é uma das grandes desvantagens da versão discreta.

Outras versões da DST

Interpretação

A DST1 pode ser pensada simplesmente como a discretização da transformada de seno. No entanto, a DST pode ser considerada de forma mais geral, a partir do problema físico do oscilador harmônico não amortecido, quando resolvido pelo método das diferenças finitas. A equação diferencial linear de segunda ordem

${\frac {d^{2}}{dt^{2}}}\;x(t)\;+\;\lambda x(t)\;=\;0$

onde x(t) descreve a posição da massa oscilante em um instante t qualquer, se transforma então na equação de diferença

$-x(k\;-\;1)\;+\;2x(k)\;-\;\lambda x(k)$

onde k é o tempo discreto. A solução da equação diferencial acima é uma combinação de funções senoidais; essas funções são as chamadas autofunções do problema. As autofunções da equação de diferença acima também são senoidais, com a diferença que neste caso são senóides discretizadas. Dois tipos de condição de contorno são especialmente relevantes:

• a condição de contorno de Neumann, ${\frac {d}{dt}}\;x(t_{a})\;=\;0$ no caso contínuo, e $x(k_{a}\;+\;1)\;=\;x(k_{a}\;-\;1)$ no caso discreto
• a condição de contorno de Dirichlet, $x(t_{b})\;=\;0$ no caso contínuo, e $x(k_{b})\;=\;0$ no caso discreto

Em geral, essas condições são aplicadas ao ponto inicial (x=0) ou ao ponto final do oscilador (x=L). Quando, no caso discreto, tais pontos coincidem com a grade que discretiza o problema, as autofunções coincidem com a DST1 e a DCT1, que correspondem exatamente às transformadas contínuas de seno e de cosseno; quando, ao contrário, os pontos extremos não estão posicionados sobre a grade, e sim a meio caminho entre duas linhas sucessivas da mesma, as autofunções do problema devem ser expressas a partir das outras versões discretas: DST2, DST3 etc.

Definições

As diversas versões da DST, assim, podem ser obtidas:

• aplicando-se a condição de contorno de Dirichlet no ponto inicial (x = 0)
• considerando que este ponto está sobre a grade ou que está a meio caminho entre duas linhas sucessivas da grade
• e aplicando-se a condição de contorno de Dirichlet ou a condição de contorno de Neumann no ponto final (x = L)
• considerando que este ponto está sobre a grade ou que está a meio caminho entre duas linhas sucessivas da grade

o que dá um total de 8 possibilidades, que estão listadas na tabela abaixo. Apenas as 4 primeiras são geralmente consideradas na literatura (as chamadas versões "pares" da DST); as demais (as versões "ímpares") aparecem a título de completude. A definição de cada versão aparece como o coeficiente da matriz que define a transformação, nos moldes da equação (3a) que define a DST1.

Tabela 1 - Versões da transformada discreta de seno

Posição do ponto inicial	Condição aplicada ao ponto final	Posição do ponto final	Versão da transformação	Definição
sobre a grade	Dirichlet	sobre a grade	DST1	${\sqrt {\frac {2}{n}}}\cdot \sin \left({\frac {jk\pi }{n}}\right)\qquad |\;k,j\in [1,n-1]$
fora da grade	Dirichlet	fora da grade	DST2	${\sqrt {\frac {2}{n}}}\cdot \epsilon _{k}\cdot \sin \left({\frac {\left(j\;+\;{\frac {1}{2}}\right)(k\;+\;1)\pi }{n}}\right)\qquad |\;k,j\in [0,n-1]$
sobre a grade	Neumann	sobre a grade	DST3	${\sqrt {\frac {2}{n}}}\cdot \epsilon _{j}\cdot \sin \left({\frac {(j\;+\;1)\left(k\;+\;{\frac {1}{2}}\right)\pi }{n}}\right)\qquad |\;k,j\in [0,n-1]$
fora da grade	Neumann	fora da grade	DST4	${\sqrt {\frac {2}{n}}}\cdot \sin \left({\frac {\left(j\;+\;{\frac {1}{2}}\right)\left(k\;+\;{\frac {1}{2}}\right)\pi }{n}}\right)\qquad |\;k,j\in [0,n-1]$
sobre a grade	Dirichlet	fora da grade	DST5	${\sqrt {\frac {4}{2n\;-\;1}}}\cdot \sin \left({\frac {2jk\pi }{2n\;-\;1}}\right)\qquad |\;k,j\in [1,n-1]$
sobre a grade	Dirichlet	fora da grade	DST6	${\sqrt {\frac {4}{2n\;-\;1}}}\cdot \sin \left({\frac {2\left(j\;+\;{\frac {1}{2}}\right)(k\;+\;1)\pi }{2n\;-\;1}}\right)\qquad |\;k,j\in [0,n-2]$
sobre a grade	Neumann	fora da grade	DST7	${\sqrt {\frac {4}{2n\;-\;1}}}\cdot \sin \left({\frac {2(j\;+\;1)\left(k\;+\;{\frac {1}{2}}\right)\pi }{2n\;-\;1}}\right)\qquad |\;k,j\in [0,n-2]$
fora da grade	Neumann	sobre a grade	DST8	${\sqrt {\frac {4}{2n\;-\;1}}}\cdot \epsilon _{j}\cdot \epsilon _{k}\cdot \sin \left({\frac {2\left(j\;+\;{\frac {1}{2}}\right)\left(k\;+\;{\frac {1}{2}}\right)\pi }{2n\;-\;1}}\right)\qquad |\;k,j\in [0,n-1]$
onde: sjk é o coeficiente da matriz S que define a transformação: O = S · f $\epsilon _{i}\;=\;\left\{{\begin{matrix}{\frac {1}{\sqrt {2}}}&:&i\;=\;n\;-\;1\\1&:&i\;\neq \;n\;-\;1\end{matrix}}\right.$ "fora da grade" significa "a meio caminho entre duas linhas sucessivas da grade"

Propriedades

As diversas versões da DST são lineares mas, apesar de serem todas unitárias, nem todas são suas próprias inversas. Se denotarmos por D_n a matriz de transformação da DSTn, podemos escrever:

$\mathbf {D_{1}} \;=\;\mathbf {D_{1}} ^{-1}\qquad \qquad \mathbf {D_{4}} \;=\;\mathbf {D_{4}} ^{-1}$

$\mathbf {D_{2}} \;=\;\mathbf {D_{3}} ^{-1}\qquad \qquad \mathbf {D_{3}} \;=\;\mathbf {D_{2}} ^{-1}$

Com relação ao escalamento no domínio do tempo e à diferenciação, todas elas se comportam da forma apresentada acima para a DST1. Com relação a um deslocamento no tempo, entretanto, elas diferem bastante uma da outra.

Desempenho da transformação

Métricas estatísticas

O desempenho da DST, em todas as suas versões, pode ser medido por meio de uma comparação com o da transformada de Karnuhen-Loève, que reconhecidamente possui o melhor teoricamente possível. A matriz D_s da DST é unitária e simétrica, como a matriz V da KLT, mas não produz uma diagonalização perfeita da matriz de autocorrelação A. A matriz A obtida a partir de D_s não será perfeitamente diagonal, aparecendo coeficientes não nulos proximo à diagonal principal; a presença desses coeficientes indica que os vetores coluna de A não são completamente independentes; a eliminação de um conjunto de autovetores na representação, com objetivos de simplificação e economia, conduzirá a um erro médio quadrático não-mínimo. Em compensação, demonstra-se que, para grandes valores de n e do coeficiente de correlação, o desempenho da DST se aproxima assintoticamente do da KLT. Como o cálculo da DST é muito mais simples e estão disponíveis algoritmos rápidos para seu cálculo, ela acaba sendo mais utilizada na prática que a KLT.

Custo de processamento

O custo de processamento da DST, em todas as suas versões, é bastante favorável, quando comparado com as concorrentes, como a KLT e a DFT, esta última normalmente calculada através do algoritmo da Transformada rápida de Fourier (FFT). Isso porque, em contraste com a KLT, o núcleo é fixo e podem ser desenvolvidos algoritmos rápidos para o cálculo dos coeficientes; em contraste com a FFT, a DST exige o cálculo de um número menor de coeficientes e o cálculo não envolve números complexos. Estão disponíveis algoritmos rápidos de diversos tipos, inclusive alguns baseados na própria FFT. A complexidade computacional dos melhores algoritmos é da ordem O{2·n·log₂(n)}: (n/2)·log₂(n) multiplicações mais n·log₂(n) adições. Uma vantagem adicional da maioria dos algoritmos é a sua estabilidade numérica, isto é, o resultado é relativamente pouco afetado por erros de arredondamento e outros relacionados.

Modernamente vêm sendo estudados algoritmos que empregam apenas números inteiros, com o objetivo de diminuir o custo computacional das transformadas discretas. Isso é possível porque, na maioria das aplicações práticas, a sequência de entrada é composta por valores inteiros, não por valores reais. Trabalhar apenas com números inteiros diminui também o uso de memória e evita erros de arredondamento e similares. A transformada discreta inteira de seno é obtida a partir de um desses algoritmos.

Distorções

O processamento digital, especialmente quando alguma compressão de dados está envolvida, pode produzir artefatos perceptíveis. Uma das causas principais na introdução de artefatos é o fato de o processamento frequentemente se efetuar em blocos independentes. A DSTtambém está sujeita a esse problema, que afeta inclusive a KLT, que é uma transformada otimizada apenas com relação às métricas estatísticas (erro médio quadrático, concentração de energia e variãncia etc.). Transformadas especiais, conhecidas como transformadas superpostas (ing. lapped transforms) foram desenvolvidas para minorar esses inconvenientes; a transformada discreta local de seno é uma delas.

Ver também

• Domínio do tempo
• Domínio da frequência
• Teorema da convolução
• Sistema causal
• Tempo discreto