Redução De Operações Através Do Compartilhamento De Subexpressões Geradas Por Decomposição De Coeficientes

Resumo

O aumento da complexidade no processamento de imagens no padrão FULLHD (1080p) e 3D é um desafio tecnológico e complexo, para o qual contribuem um conjunto de técnicas para reduzir a dissipação de potência e área dos dispositivos de processamento digital de Imagem. Neste aspecto a etapa de quantização de imagem é geralmente realizada reduzindo-se a quantidade de níveis de cor ou os coeficientes no domínio da frequência. No padrão de imagem JPEG a quantização geralmente é realizada sobre os coeficientes da transformada discreta do cosseno (DCT) que elimina os coeficientes menos significativos. Esses coeficientes são responsáveis por uma série de multiplicações que quando implementados em hardware ocupam muita área e dissipam elevada potência. Assim, o desenvolvimento de técnicas que possibilitem a redução de coeficientes, permite implementar arquiteturas otimizadas, visto que elas são diretamente proporcionais a eles. Neste trabalho elaborou-se um algoritmo em MATLAB para decomposição dos coeficientes produzidos por uma multiplicação de uma matriz por constantes, provenientes do processo de quantização de imagem no padrão JPEG utilizando DCT. A técnica de simplificação consiste em transformar os elementos de uma matriz, normalmente na base decimal, para o sistema de representação CSD, do inglês Canonical SignedDigit, (tendo como característica: a diminuição dos dígitos não zeros e o produto entre dígitos adjacentes igual a zero) ou MSD (MinimalSignedDigit), tendo como característica a diminuição dos dígitos não zeros. Tendo em vista que para cada digito não zero é efetuada uma operação. Para demonstrarmos a melhoria da mudança de representação dos coeficientes, levamos em consideração o número (14)10, representado por (1110)2 e quando aplicada a técnica CSD obtém-se a representação (10020)CSD, onde o dígito (2)CSD representa a operação contrária ao dígito (1)2, ou seja, subtrai-se. Nesta representação pode-se observar a redução de um dígito não zero, ou seja, uma operação e um deslocamento a menos. Outro exemplo, tendo como entrada os dados, (13)10 e (29)10 representados por (10201)CSD e (100201)CSD. Na transformação é geradas as seguintes expressões que representam os valores decompostos: 13=x<<4-x<<2+x<<0 e 29=x<<5-x<<2+x<<0, onde se obteve o compartilhamento da subexpressão S=x<<2+x<<0. Com isto, obtêm-se as expressões simplificadas, 19=x<<4-S e 35=x<<5-S. O Algoritmo verifica dentre as expressões geradas, as subexpressões comuns entre elas, a fim de compartilhar a mesma estrutura e acelerar o processamento. Para comparação de resultados de uma decomposição que não utiliza compartilhamento de subexpressões com uma que utiliza, foram inseridos no algoritmo 250 valores aleatórios gerados pelo próprio MATLAB. Para a implementação da primeira arquitetura, seriam necessárias 2857 operações, dentre elas, somas, subtrações e deslocamentos. Já para uma arquitetura que utiliza o compartilhamento de subexpressões necessitou-se de apenas 1137 operações