Universidade Católica de Pelotas
ANDRÉ MARCELO COELHO DA SILVA
TÉCNICAS PARA O AUMENTO DE DESEMPENHO DE
ARQUITETURAS DEDICADAS DAS TRANSFORMADAS
DIRETAS E DE ESTIMAÇÃO DE MOVIMENTO DO PADRÃO
H.264/AVC DE CODIFICAÇÃO DE VÍDEO
PELOTAS
2009
ANDRÉ MARCELO COELHO DA SILVA
TÉCNICAS PARA O AUMENTO DE DESEMPENHO DE
ARQUITETURAS DEDICADAS DAS TRANSFORMADAS
DIRETAS E DE ESTIMAÇÃO DE MOVIMENTO DO PADRÃO
H.264/AVC DE CODIFICAÇÃO DE VÍDEO
Dissertação apresentada no programa de
Pós-graduação
em
informática
da
Universidade Católica de Pelotas como
requisito parcial para a obtenção do grau
de mestre em Informática
Prof. Orientador: Dr. Eduardo Costa
Prof. Co-orientador: Dr. Sérgio Almeida
PELOTAS
2009
1
AGRADECIMENTOS
Em cada desafio que conseguimos superar é necessário comemorar mas é muito
importante olhar para trás para sempre nos lembrarmos das adversidades e como é
difícil alcançar o ponto final.
É preciso ter garra, fé e dedicação para atingir os objetivos. Existem momentos que
temos que tirar forças de onde nem nós mesmos sabíamos que tínhamos. Outras vezes
precisamos que outras pessoas nos ajudem, às vezes, com apenas algumas palavras
de incentivo.
Neste momento de agradecimentos existem várias pessoas que contribuíram de
alguma forma para que este trabalho tivesse êxito. Porém existem algumas pessoas
que são extremamente importantes em nossas vidas e outras que foram importantes
para este trabalho.
Na minha vida, são muito importantes os meus pais, Elmo Ribeiro da Silva e Gelsinete
Coelho da Silva, por ser neles onde sempre encontro apoio incondicional para
realização das minhas tarefas, para tomar as decisões e também compreensão e
incentivo nas horas de maior necessidade. Um grande agradecimento a minha irmã
Andréia Coelho da Silva pela amizade e companheirismo nas horas de maior
necessidade, e minha vó Nair Vargas Coelho por ser a minha segunda mãe.
Agradeço também aos meus colegas do mestrado e também aos colegas do LAMIPS
que contribuíram de alguma forma para a realização deste trabalho final. Faço aqui um
agradecimento especial ao colega João Altermann pela ajuda nesta última etapa do
trabalho. E um especial agradecimento ao meu orientador, Prof. Eduardo Costa, e ao
meu co-orientador, Prof. Sérgio Almeida, pela dedicação, compreensão e significativas
contribuições para a realização deste trabalho.
Por fim, agradeço a DEUS por permitir chegar ao fim desta etapa com sucesso.
2
SUMÁRIO
LISTA DE FIGURAS .......................................................................................... 5
LISTA DE TABELAS ......................................................................................... 7
LISTA DE ABREVIATURAS E SIGLAS ............................................................ 8
RESUMO.......................................................................................................... 10
ABSTRACT...................................................................................................... 11
1 INTRODUÇÃO .............................................................................................. 12
1.1 Motivação .................................................................................................. 12
1.2 Objetivos ................................................................................................... 13
1.3 Metodologia ............................................................................................... 14
1.4 Contribuições do Trabalho ........................................................................ 15
1.5 Organização do Trabalho .......................................................................... 16
2 CONCEITOS BÁSICOS DA COMPRESSÃO DE VÍDEO ............................ 17
2.1 Espaço de Cores e Sub-Amostragem de Cores ........................................ 17
2.2 Partição do Vídeo Digital ........................................................................... 19
2.3 Redundância de Dados ............................................................................. 21
2.3.1 Redundância Espacial ............................................................................ 22
2.3.2 Redundância Temporal .......................................................................... 22
2.3.3 Redundância Entrópica .......................................................................... 22
2.4 Sumário ..................................................................................................... 23
3 O PADRÃO H.264/AVC ............................................................................... 24
3.1 Histórico do padrão H.264/AVC ................................................................ 24
3.2 Perfis ......................................................................................................... 26
3.3 Formato dos Dados Codificados ............................................................... 27
3.4 Núcleo do Padrão H.264/AVC ................................................................... 28
3.4.1 Módulo de Predição Inter-Quadro .......................................................... 30
3.4.2 Módulo de Predição Intra-Quadro .......................................................... 35
3.4.3 O Módulo das Transformadas Diretas (T) e das
Transformadas Inversas T-1 ................................................................... 36
3.4.4 O Módulo da Quantização Direta (Q) e da
Quantização Inversa (Q-1) ...................................................................... 37
3.4.5 O Módulo do Filtro de Deblocagem ........................................................ 38
3.4.6 O Módulo da Codificação de Entropia .................................................... 38
3.5 Alguns Trabalhos da Literatura de Desenvolvimento
dos Módulos do Padrão H.264/AVC .......................................................... 40
3.6 Sumário ..................................................................................................... 41
4 TRANSFORMADAS DIRETAS (BLOCO T) E ESTIMAÇÃO
DE MOVIMENTO DO PADRÃO H.264/AVC ............................................... 42
4.1 O Módulo das Transformadas Diretas (T) ................................................. 42
4.1.1 A Transformada Discreta do Cosseno (DCT) ......................................... 45
4.1.2 A Transformada Hadamard .................................................................... 46
4.2 O Módulo da Estimação de Movimento ..................................................... 47
4.2.1 Algoritmo Diamond Search (PORTO, 2008) ........................................... 52
4.3 Sumário ..................................................................................................... 53
5 CIRCUITOS SOMADORES EFICIENTES ................................................... 54
3
5.1 Somador Carry Save ................................................................................. 54
5.2 O Compressor 4:2 ..................................................................................... 55
5.3 Compressores Hierárquicos 8:2 e 16:2 ..................................................... 58
5.4 Análise Comparativa dos Compressores .................................................. 64
5.6 Sumário ..................................................................................................... 65
6 ESTUDOS DE CASO: MÓDULO T E ESTIMAÇÃO DE MOVIMENTO ....... 66
6.1 Soluções arquiteturais: Módulo T .............................................................. 66
6.1.1 Estudo de caso para a FDCT-2D ........................................................... 66
6.1.1.1 Arquiteturas Propostas Neste Trabalho ............................................... 66
6.1.1.2 Arquitetura proposta por (AGOSTINI, 2007) ....................................... 69
6.1.1.3 Resultados de síntese ......................................................................... 70
6.1.2 Estudo de caso para a Transformada Hadamard 4x4 ............................ 71
6.1.2.1 Implementações de Arquiteturas Combinacionais em FPGA .............. 71
6.1.2.1.1 Arquitetura Combinacional com Somadores/Subtratores
Ripple Carry ..................................................................................... 72
6.1.2.1.2 Arquitetura Combinacional com Compressor 4:2 ............................. 73
6.1.2.1.3 Arquitetura Combinacional com Compressor 4:2 e
Subtrator Carry-Save ........................................................................ 74
6.1.2.1.4 Arquitetura Combinacional com Compressor 8:2 ............................. 75
6.1.2.1.5 - Arquitetura Combinacional com Compressor 16:2 ......................... 76
6.1.2.1.6 Resultados das Arquiteturas Combinacionais .................................. 77
6.1.2.2 Implementações de Arquiteturas Seriais em FPGA ............................ 78
6.1.2.2.1 Arquitetura Serial com Separabilidade ............................................. 78
6.1.2.2.2 Arquitetura Serial sem Separabilidade ............................................. 81
6.1.2.3 Implementações em ASIC para a Transformada Hadamard 4x4 ........ 83
6.1.2.4 Resultados de Síntese ........................................................................ 84
6.1.3 Arquitetura para Transformada Hadamard 2x2 ...................................... 85
6.1.3.1 - Resultados de Síntese ...................................................................... 86
6.1.4 Validação do Módulo T Completo .......................................................... 87
6.1.5 Comparação com Resultados da Literatura ........................................... 87
6.2 Soluções Arquiteturais: Estimação de Movimento (ME) ............................ 89
6.2.1 Otimização proposta neste trabalho ....................................................... 91
6.2.2 Avaliação dos Resultados ...................................................................... 92
6.2.3 Resultados de Síntese ........................................................................... 93
6.2.4 Comparação com Resultados da Literatura ........................................... 95
7 CONCLUSÕES E TRABALHOS FUTUROS ............................................... 97
7.1 Trabalhos Futuros ..................................................................................... 98
7.1.1 Aplicação dos Somadores Compressores ao Módulo das
Transformadas Inversas ......................................................................... 98
7.1.2 Verificação do Consumo de Potência dos Módulos das
Transformadas ....................................................................................... 98
7.1.3 Verificação do Aumento do Paralelismo na Arquitetura da ME
para Verificação do Uso dos Somadores Compressores ....................... 99
REFERÊNCIAS ............................................................................................. 100
ANEXOS ....................................................................................................... 105
4
LISTA DE FIGURAS
Figura 2.1: Mostra da Sub-amostragen no Formato 4:2:0 ............................... 19
Figura 2.2: Possíveis Partições de um Macrobloco ......................................... 20
Figura 2.3: Possíveis Partições de um Sub-Macrobloco ................................. 20
Figura 2.4: Divisão de um Quadro com Várias Partições ................................ 21
Figura 3.1: Estrutura dos Perfis Atuais do Padrão H.264/AVC (ROSA, 2009) 27
Figura 3.2: Seqüência de Unidades NAL ........................................................ 28
Figura 3.3: Diagrama de Blocos do Codificador do Padrão H.264/AVC .......... 29
Figura 3.4: Diagrama de Blocos do Decodificador do Padrão H.264/AVC ...... 30
Figura 3.5: Determinação do Vetor de Movimento para um Bloco .................. 31
Figura 3.6: Quadro do Vídeo Antes da MC ..................................................... 33
Figura 3.7: Quadro do Vídeo Após a MC ........................................................ 34
Figura 3.8: Quadro de Luminância Resídual ................................................... 34
Figura 3.9: Nove modos de predição Intra-Quadro para Blocos
de 4x4 Pixels ................................................................................. 35
Figura 3.10: Quatro modos de predição Intra-Quadro para Blocos
de 16x16 Pixels ........................................................................... 36
Figura 4.1: Diagrama de Blocos do Módulo da Transformadas Diretas (T) .... 44
Figura 4.2: Ordem de Processamento de Amostras pelo Módulo T ................ 45
Figura. 4.3: Estimação de Movimento com Precisão de Fração de Pixel ........ 49
Figura 4.4: Large Diamond (LDSP) (L) e Small Diamond (SDSP) (S) ............. 52
Figura 4.5(a): Busca por uma aresta ............................................................... 53
Figura 4.5(b): Busca por um vértice ................................................................ 53
Figura 5.1: Exemplo de um Somador Carry Save ........................................... 54
Figura 5.2: Exemplo de Soma de Números de 4 bits Usando a
Estrutura Carry Save ..................................................................... 55
Figura 5.3: Estrutura do Compressor 4:2 ........................................................ 56
Figura 5.4: Compressor 4:2 Utilizando Multiplexadores .................................. 58
Figura 5.5: Circuito Somador de 14 bits Utilizando Compressor 4:2 ............... 58
Figura 5.6: Diagrama de Blocos do Circuito Compressor 8:2 .......................... 59
Figura 5.7: Estrutura Hierárquica do Compressor 8:2 ..................................... 59
Figura 5.8: Circuito Somador de 14 Bits Utilizando Compressor 8:2 ............... 61
Figura 5.9: Diagrama de Blocos do Circuito Compressor 16:2 ........................ 61
Figura 5.10: Estrutura Hierárquica do Compressor 16:2 ................................. 62
Figura 5.11: Circuito Somador de 14 bits Utilizando Compressor 16:2 ........... 64
Figura 6.1: Arquitetura para FDCT-2D utilizando compressores 4:2 ............... 67
Figura 6.2: Arquitetura para FDCT-2D utilizando compressores 8:2 ............... 68
Figura 6.3: Arquitetura para FDCT-2D utilizando compressores 16:2 ............. 69
Figura 6.4: Arquitetura para a FDCT-2D proposta por (AGOSTINI, 2007) ...... 70
Figura 6.5: Arquitetura Combinacional com Somadores/Subtratores
Ripple Carry (AGOSTINI, 2007) .................................................... 72
Figura 6.6: Arquitetura Combinacional com Compressores 4:2 ...................... 74
Figura 6.7: Arquitetura Combinacional com Compressor 4:2 e
Subtrator Carry Save ..................................................................... 75
Figura 6.8: Arquitetura Combinacional com Compressor 8:2 .......................... 76
5
Figura 6.9: Arquitetura Combinacional com Compressor 16:2 ........................ 77
Figura 6.10: Arquitetura Serial com separabilidade Utilizando
o Compressor 4:2 ........................................................................ 79
Figura 6.11: Arquitetura Serial sem Separabilidade Utilizando
o Compressor 16:2 ...................................................................... 81
Figura 6.12: Arquitetura para a Hadamard 4x4 implementada
na Tecnologia ASIC ..................................................................... 83
Figura 6.13: Arquitetura para a Hadamard 4x4 implementada
na Tecnologia ASIC ..................................................................... 84
Figura 6.14: Arquitetura para a Transformada Hadamard 2x2 ........................ 86
Figura 6.15: Arquitetura para ME proposta em (PORTO, 2008) ..................... 90
Figura 6.16: Arquitetura da Unidade de Processamento (UP) ........................ 91
Figura 6.17(a) Estrutura da UP da ME com Compressor 4:2 .......................... 92
Figura 6.17(b) Estrutura da UP da ME com Compressor 8:2 .......................... 92
6
LISTA DE TABELAS
Tabela 5.1: Verdade do Compressor 4:2 ........................................................ 57
Tabela 5.2: Tabela Verdade do Compressor 8:2 ............................................. 60
Tabela 5.3: Tabela Verdade do Compressor 16:2 ........................................... 63
Tabela 5.4: Resultado de Síntese Para os Compressores .............................. 65
Tabela 6.1: Resultados de Síntese para a FDCT-2D sem Separabilidade ..... 71
Tabela 6.2: Resultados de Área, Atraso e Potência para as
Arquiteturas Combinacionais ........................................................ 78
Tabela 6.3: Resultado de Síntese para Transformadas 1-D ........................... 80
Tabela 6.4: Resultado de Síntese da Arquitetura Serial com
Separabilidade .............................................................................. 80
Tabela 6.5: Resultado de Síntese da Arquitetura Serial sem
Separabilidade .............................................................................. 82
Tabela 6.6: Resultados Transformada Hadamard 4x4 .................................... 85
Tabela 6.7: Resultados de Síntese da Transformada Hadamard 2x2 ............. 87
Tabela 6.8: Resultados para o Módulo T Completo ........................................ 87
Tabela 6.9: Resultados Comparativos com Trabalhos Relacionados ............. 89
Tabela 6.10: Resultados de Síntese para Arquiteturas da ME ........................ 95
Tabela 6.11: Resultados Comparativos .......................................................... 96
7
LISTA DE ABREVIATURAS E SIGLAS
1-D
2-D
AC
ASIC
AVC
CABAC
CD
Codec
CAVLC
DC
DCT
DCT-2D
DPCM
DVD
FDCT
FDCT-2D
FRExt
HD
HDTV
HD-DVD
HSI
HT
IDCT
IDCT-2D
IEC
IHT
ISO
ITU-T
JVT
MB
MC
ME
MPEG
NAL
Q
Q−1
QP
RAM
RBSP
RGB
SBTVD
T
T−1
VCEG
Uma Dimensão
Duas Dimensões
Alternate Current
Application Specific Integrated Circuit
Advanced Video Coding
Context-Based Adaptative Binary Arithmetic Coding
Compact Disk
Codificador/Decodificador
Context-Based Adaptative Variable Length Coding
Direct Current
Discrete Cosine Transform
Discrete Cosine Transform in Two-Dimensions
Differential Pulse Code Modulation
Digital Versatile Disk
Forward Discrete Cosine Transform
Forward Discrete Cosine Transform in Two-Dimensions
Fidelity range Extensions
Hard Disk
High Definition Digital Television
High Density Digital Versatile Disc
Hue, Saturation, intensity
Hadamard Transform
Inverse Discrete Cosine Transform
Inverse Discrete Cosine Transform in Two-Dimensions
International Electrotechnical Commission
Inverse Hadamard Transform
International Organization for Standardization
International Telecommunication Union - Telecommunication
Joint Video Team
Macrobloco
Motion Compesation
Motion Estimation
Moving Picture Experts Group
Network Abstraction Layer
Quantização
Quantização Inversa
Parâmetro de Quantização
Random Access Memory
Raw Byte Sequence Payload
Red, Green, Blue
Sistema Brasileiro de Televisão Digital
Transformada
Transformada Inversa
Video Coding Experts Group
8
VCL
YCbCr
Video Coding Layer
Luminance, Chrominance Blue, Chrominance Red
9
RESUMO
A crescente utilização de vídeos digitais na Internet, em dispositivos móveis e também na TV
digital faz com que haja um interesse crescente em pesquisas nesta área, tanto na indústria quanto
no meio acadêmico. Este trabalho segue esta tendência e tem como proposta estudar aspectos de
vídeo digital, compressão de vídeo e também do padrão H.264/AVC de compressão de vídeo
para a implementação de arquiteturas dedicadas eficientes em desempenho, isto é, com elevada
frequência de operação, dos módulos do codificador do padrão H.264/AVC. Em particular, este
trabalho apresenta algumas alternativas arquiteturais para aumento de desempenho de dois
módulos do padrão H.264/AVC, que são: Módulo T (composto pelas Transformadas Diretas –
Transformadas Hadamard e Transformada Discreta do Coseno) e Estimação de Movimento
(ME). A implementação destes módulos foi realizada utilizando técnicas para o aumento de
desempenho, tais como o uso de somadores eficientes e pipeline. Uma característica dos
somadores eficientes utilizados neste trabalho é o uso elevado de recursos de hardware. Assim,
as arquiteturas implementadas neste trabalho também apresentaram esta característica. Os
módulos implementados apresentam como principal característica um elevado número de
operações aritméticas de soma e subtração para o seu processamento. Desta forma, a motivação
deste trabalho consiste em aumentar o desempenho destes módulos, a partir da utilização de
circuitos somadores/subtratores eficientes presentes na literatura. Em particular, são utilizados
circuitos somadores compressores 4:2, 8:2 e 16:2, pois estes realizam a soma simultânea de 4, 8 e
16 operandos, respectivamente, sem penalidades em área e no caminho crítico. As arquiteturas
foram descritas em VHDL e direcionadas para tecnologia ASIC, a validação e resultados foram
obtidos através da ferramenta Leonardo Spectrum da Mentor Graphics. Para os estudos de caso
utilizados neste trabalho (Transformadas Diretas e Estimação de Movimento), foram feitas
comparações com soluções apresentadas na literatura e os resultados mostram que as arquiteturas
implementadas neste trabalho obtiveram significativos ganhos em desempenho, quando
comparadas com soluções apresentadas na literatura.
Palavras-chave: Compressão de Vídeo, Padrão H.264/AVC, Vídeo Digital, Transformadas
Diretas, Estimação de Movimento.
10
ABSTRACT
TITLE: “TECHNIQUES FOR THE INCREASE OF PERFORMANCE OF FORWARD
TRANSFORMS AND MOTION ESTIMATION DEDICATED ARCHITECTURES OF THE
H.264/AVC VIDEO CODING STANDARD”
The increasing use of digital video on the Internet, devices and also in mobile digital TV has lead
to an increasing interest for research in this area, from both industry and academia. This work
follows this trend by proposing the investigation of the main aspects of digital video, video
compression and also of the H.264/AVC video compression for the implementation of
performance efficient dedicated architectures for some modules of the H.264/AVC encoder. In
particular, this work presents some architectural alternatives for the increase of performance of
two modules of the H.264/AVC, which are: T Module (composed by the Forward Hadamard and
Discrete Cosine Transforms) and Motion Estimation (ME). For the implementation of these
modules the use of techniques to the increase of performance has been considered, such as the
use of efficient adders and pipeline. This efficient adders presents high use of hardware features.
Thus, the implemented architectures in this work presented these characteristics too. The main
aspect presented by the implemented modules is a large number of arithmetic operations of
addition and subtraction for their processing. Thus, the motivation of this work is the increase of
performance of these modules, from the use of efficient adder/subtractor circuits that are present
in literature. In particular, 4:2, 8:2 and 16:2 adder compressors that perform the simultaneous
addition of 4, 8 and 16 operands, respectively, with no penalties in area and the critical path are
used. The architectures were described in VHDL and targeted to ASIC technology. The
validation of the circuits and the obtained results were performed by using Leonardo Spectrum
tool from Mentor Graphics. Comparisons against the solutions of the literature were done and the
main results show that the architectures proposed in this work are more efficient. Significant
gains in performance are achievable using our solutions for both Forward Transforms and Motion
Estimation architectures.
Keywords: Video Compression, H.264/AVC Standard, Digital Video, Forward Transforms,
Motion Estimation.
11
1 INTRODUÇÃO
Vídeos digitais apresentam uma demanda cada vez maior, devido à possibilidade da sua
utilização em diversas áreas de aplicações, tais como Web, videoconferências, transmissões em
broadcast, e também SBTVD (Sistema Brasileiro de TV Digital) (DTV, 2008), que está em
funcionamento em algumas cidades do Brasil desde dezembro de 2007.
Para a transmissão eficiente de vídeos digitais, é necessário fazer a compressão das
informações, isto é, reduzir o número de bits necessários à sua representação, sem a perda
significativa de informações. Esta redução pode ser realizada através da exploração de uma
característica existente nas seqüências de vídeo, definida como redundância. Esta propriedade
permite que grande parte dos dados necessários para representar um vídeo digital possa ser
descartada.
Com a finalidade de fazer a compressão eficiente dos vídeos digitais, foi desenvolvido
pela ITU-T, o padrão de compressão de vídeo H.264/AVC (WIEGAND, 2003), que é o mais
recente padrão de compressão de vídeo, sendo este mais eficiente em relação a outros padrões
existentes, tais como MPEG-2 (ITU-T, 1994) e H.263 (ITU, 2000). Esta eficiência de
compressão
é
obtida
ao
custo
de
um
acréscimo
computacional
no
seu
codec
(codificador/decodificador), fazendo com que a complexidade computacional de alguns módulos
do padrão H.264/AVC tenham um acréscimo significativo em relação aos padrões anteriores.
Além da compressão de vídeos para a transmissão via rede de computadores,
principalmente a Web, outro ponto importante a ser explorado é o armazenamento adequado das
informações. Este aspecto contribui para a otimização de recursos geralmente utilizados para tal
finalidade, tais como DVDs, CDs, HDs e etc.
Diante do quadro exposto e dos desafios ainda presentes, tem-se que a compressão de
vídeo e o padrão H.264/AVC são assuntos que estão sendo amplamente estudados por
pesquisadores do meio acadêmico e da indústria e muitas contribuições significativas ainda
podem ser dadas no sentido de aumentar a eficiência da transmissão dos vídeos digitais.
1.1 Motivação
Além dos vídeos digitais, outro setor que vem apresentando um aumento significativo
em termos de utilização são os dispositivos móveis operados por bateria, tais como palmtops,
câmeras e filmadoras digitais portáteis, telefones celulares entre outros. Para estes dispositivos,
12
estão sendo cada vez mais utilizadas aplicações com vídeos digitais. Entretanto, para estas
aplicações, um fator de extrema importância é possuir um codec eficaz, isto é, que realize as
tarefas de codificação/decodificação do vídeo com eficiência de desempenho, pois dispositivos
móveis que operem informações de vídeo digital tenderão a ter o tempo de vida útil das suas
baterias reduzido. Além disso, estes dispositivos móveis não podem apresentar aquecimento
elevado em seus circuitos, para não comprometer o seu funcionamento e a sua utilização pelos
usuários.
Neste sentido, torna-se importante o projeto e implementação de módulos do padrão
H.264/AVC que satisfaçam às exigências de desempenho, de acordo com a taxa de
processamento a ser utilizada, pois esta métrica é fator crítico para o projeto do codec do padrão
H.264/AVC voltado para a utilização de dispositivos que pretendam trabalhar com vídeos em
tempo real, ou seja, processem o mínimo de 30 quadros por segundo. Com isto, este trabalho tem
como objetivo aplicar técnicas para o aumento de desempenho a alguns módulos do codificador
do padrão H.264/AVC, de tal forma que vários equipamentos que utilizam vídeos digitais possam
ser utilizados de forma eficiente.
1.2 Objetivos
Este trabalho tem por objetivo estudar e aplicar técnicas para o aumento de desempenho
existentes na literatura para o codec do padrão H.264/AVC, tais como o uso de operadores
aritméticos eficientes, pipelining, viabilizando a sua utilização em TV digital, dispositivos
móveis operados por bateria, etc. Esta linha de estudo vem sendo pesquisada com maior força
recentemente em grupos de pesquisa internacionais (UDYAWAR , 2006), (KOZIRI, 2006), (LIN
2006), (KUO 2006), (PARLAK, 2007), (LOPEX, 2008) e (HISHAN, 2009), visto um maior
número de equipamentos portáteis que vêm sendo lançados no mercado recentemente, cuja
aplicação de vídeos digitais é imediata.
Particularmente, as técnicas para o aumento de desempenho são aplicadas a vários
módulos integrantes da etapa de compressão de vídeo, dentre os quais se destacam os módulos
das transformadas e de estimação de movimento do padrão H.264/AVC. Desta forma, são
explorados os seguintes módulos neste trabalho: i) Transformadas Hadamard e Transformada
Discreta do Cosseno; ii) Estimação de movimento.
13
Dentre as etapas dos compressores atuais, a mais complexa e que resulta nos melhores
resultados de taxa de compressão é a estimação de movimento (ME – Motion Estimation). A ME
é responsável por encontrar uma co-relação entre quadros, mapeando a redundância temporal
entre os quadros vizinhos de uma cena. O processo de estimação é extremamente complexo, o
que torna indispensáveis arquiteturas de hardware dedicadas eficientes para este fim, quando se
deseja trabalhar com vídeos de alta resolução em tempo real. Por outro lado, os algoritmos das
Transformadas Hadamard 4x4 e 2x2 e Transformada Discreta do Cosseno (DCT), que fazem
parte integrante do bloco T do padrão H.264/AVC, agregam um grande número de operações
aritméticas. Desta forma, torna-se importante a implementação de arquiteturas dedicadas destes
algoritmos, com operadores aritméticos eficientes, que possam reduzir a complexidade
computacional dos cálculos realizados por estes módulos.
1.3 Metodologia
Em um estudo inicial, tornou-se possível observar que alguns módulos do codec do
padrão H.264/AVC apresentam um excelente estudo de caso para a aplicação de operadores
aritméticos eficientes presentes na literatura (COSTA, 2002). O primeiro estudo de caso feito foi
na Transformada Hadamard 4x4 presente no módulo das transformadas diretas (T). Neste
primeiro experimento foram desenvolvidas sete arquiteturas combinacionais para a transformada
Hadamard 4x4, sendo cinco arquiteturas paralelas e duas arquiteturas seriais direcionadas para a
tecnologia FPGA (Field Programmable Gate Array). As arquiteturas foram desenvolvidas em
linguagem de descrição de hardware VHDL (Very High Speed Integrated Circuits Hardware
Description Language) e sintetizadas na ferramenta Quartus II da Altera para a obtenção de
resultados de uso de recursos de hardware e frequência de operação. Em particular, o módulo das
transformadas diretas (T), que além da Transformada Hadamard (FHAD – Forward Hadamard
Transform) é formado também pela Transformada Discreta do Cosseno (FDCT – Forward
Discrete Cosine Transform) e o módulo da Estimação de Movimento (ME – Motion Estimation),
apresentam um elevado número de operações aritméticas em seus algoritmos. Desta forma, este
trabalho explora a utilização de circuitos somadores eficientes que possam realizar estas
operações no menor tempo possível. Neste contexto, os circuitos somadores compressores estão
presentes na literatura como circuitos eficientes para a realização de somas simultâneas de vários
operandos (WEINBERGER, 1981). Neste trabalho são utilizados circuitos somadores
compressores 4:2, 8:2 e 16:2 em arquiteturas dedicadas para os módulos citados anteriormente.
14
Após a verificação dos resultados obtidos com o estudo inicial, foram realizadas implementações
de todas as transformadas que compõe o módulo T, a integração destas transformadas para a
implementação do módulo T completo e também o desenvolvimento do módulo de estimação de
movimento. Estas arquiteturas foram direcionadas para a tecnologia ASIC (Application Specific
Integrated Circuit) TSMC 0,18um CMOS standard cells. As arquiteturas foram descritas em
VHDL e a ferramenta Leonardo Spectrum da Mentor Graphics foi utilizada para a síntese e
obtenção dos resultados de área utilizada e atraso dos circuitos.
1.4 Contribuições do Trabalho
A partir do estudo realizado, para a exploração das diferentes alternativas arquiteturais
dos módulos das Transformadas Diretas e de Estimação de Movimento do padrão H.264/AVC,
com técnicas para o aumento de desempenho, apresentam-se as seguintes contribuições:
- Exploração arquitetural das diferentes arquiteturas específicas para os algoritmos propostos em
(AGOSTINI, 2007). Neste trabalho citado, foram especificadas arquiteturas para os módulos das
Transformadas Direta e Inversa. Neste trabalho, foram utilizadas técnicas para o aumento de
desempenho nas arquiteturas implementadas, especificamente da Transformada Hadamard 4x4.
Em particular, foram aplicados operadores aritméticos eficientes nestas arquiteturas para a
redução da complexidade computacional dos cálculos realizados por estes circuitos. Os principais
resultados estão apresentados em (SILVA, 2009)
- Validação do bloco T do padrão H.264/AVC. Além das Transformadas Hadamard, o bloco T do
padrão H.264/AVC é composto pela Transformada Discreta do Cosseno (DCT). Desta forma,
nesta parte do trabalho houve a validação completa do bloco T, verificando-se o impacto do
aumento de desempenho que é obtido quando da aplicação das técnicas propostas em todos os
blocos das transformadas. Para tal, todos os módulos das transformadas foram implementados e
foram realizadas comparações de desempenho entre as diferentes configurações propostas.
(ALTERMANN, 2009)
- Exploração arquitetural e aplicação de técnicas para o aumento de desempenho em algoritmos
do bloco de estimação de movimento. Em (PORTO, 2008), apresentam-se arquiteturas dedicadas
para realizar o processo de estimação de movimento. Este algoritmo, chamado Diamond Search,
apresenta em sua estrutura um elevado número de operações aritméticos. Desta forma, o objetivo
15
nesta parte do trabalho foi a investigação do impacto em aumento de desempenho, na utilização
de operadores aritméticos mais eficientes neste algoritmo heurísticos que foi implementado em
hardware dedicado (SILVA 2009) (PORTO 2010).
1.5 Organização do Trabalho
Este trabalho foi dividido da seguinte forma. No capítulo 2 é apresentada uma breve
introdução aos conceitos de compressão de vídeo e também sobre vídeo digital. O capítulo 3 é
dedicado ao histórico do padrão de compressão de vídeo H.264/AVC. No capítulo 4 é feita uma
abordagem das principais características dos módulos do padrão H.264/AVC que foram
utilizados neste trabalho como estudos de caso. O capítulo 5 é direcionado para o estudo
realizado sobre os somadores compressores 4:2, 8:2 e 16:2. No capítulo 6 são mostradas as
arquiteturas dedicadas propostas neste trabalho com o uso dos somadores compressores, bem
como os resultados obtidos com estas estruturas. Finalmente, no capítulo 7 são apresentadas as
conclusões obtidas com o trabalho, assim como as principais idéias para trabalhos futuros.
16
2 CONCEITOS BÁSICOS DA COMPRESSÃO DE VÍDEO
Este capítulo apresenta, resumidamente, alguns conceitos básicos sobre vídeos digitais,
compressão de vídeos digitais e também sobre a sua forma de representação.
2.1 Espaço de Cores e Sub-Amostragem de Cores
A representação digital de um vídeo colorido está associada à interpretação das cores
pelo sistema visual humano. O sistema humano de visão possui elementos sensíveis à luz
chamados bastonetes e cones. Os bastonetes são sensíveis à intensidade luminosa, enquanto os
cones são sensíveis às cores primárias (GONZÁLES, 2003). Em função desta estrutura do
sistema visual humano, todas as cores são vistas como combinações variáveis das três cores
primárias: vermelho (R - red), verde (G - green) e azul (B - blue). O sistema visual humano é
capaz de discernir milhares de cores distintas a partir de combinações de intensidades distintas
das cores primárias. Por outro lado, o sistema visual humano não consegue distinguir mais do que
duas dúzias de tons de cinza que, na verdade, indicam a intensidade luminosa da imagem
(GONZÁLES, 2003).
Existem muitas formas de representar as cores de forma digital. Um sistema para
representar cores é chamado de espaço de cores e a definição do espaço de cor a ser utilizado
para representar um vídeo é essencial para a eficiência da codificação deste vídeo.
São vários os espaços de cores usados para representar imagens digitais, tais como:
RGB, HSI e YCbCr (SHI, 1999). O espaço de cores RGB é um dos mais comuns, tendo em vista
que é este o espaço de cores utilizado nos monitores coloridos. O RGB representa, em três
matrizes distintas, as três cores primárias captadas pelo sistema visual humano: vermelho, verde e
azul. Daí advém o nome deste espaço de cores (do inglês red, green e blue - RGB). No espaço de
cores YCbCr as três componentes utilizadas são luminância (Y), que define a intensidade
luminosa ou o brilho, crominância azul (Cb) e crominância vermelha (Cr) (MIANO, 1999).
Os componentes R, G e B possuem um elevado grau de correlação, tornando difícil o
processamento de cada uma das informações de cor de forma independente. Por isso, a
compressão de vídeos é aplicada para espaços de cores do tipo luminância e crominância, como o
YCbCr (RICHARDSON, 2002).
Outra vantagem do espaço de cor YCbCr sobre o espaço RGB é que no espaço YCbCr a
informação de cor está completamente separada da informação de brilho. Deste modo, estas
17
informações podem ser tratadas de forma diferenciada pelos compressores de imagens estáticas e
vídeos.
O sistema visual humano possui cerca de 240 milhões de bastonetes e 13 milhões de
cones (GONZALES, 2003). Deste modo, o sistema visual humano é muito mais sensível a
informações de luminância do que as informações de crominância. Desta forma, é conveniente
que os padrões de compressão de imagens estáticas e vídeos explorarem esta característica
psicovisual humana para aumentar a eficiência de codificação, o que se dá através da redução da
taxa de amostragem dos componentes de crominância em relação aos componentes de luminância
(RICHARDSON, 2002). Esta operação é chamada de sub-amostragem de cores e é realizada
sobre o espaço de cores YCbCr nos padrões de compressão de vídeos atuais.
Existem várias formas de relacionar os componentes de crominância com o componente
de luminância para realizar a sub-amostragem. Os formatos mais comuns são o 4:4:4, o 4:2:2 e o
4:2:0. No formato 4:4:4, para cada quatro amostras de luminância (Y), existem quatro amostras
de crominância azul (Cb) e quatro amostras de crominância vermelha (Cr). Por isso, os três
componentes de cor possuem a mesma resolução e existe uma amostra de cada elemento de cor
para cada pixel da imagem e, assim, a sub-amostragem não é aplicada. No formato 4:2:2, para
cada quatro amostras de Y na direção horizontal, existem apenas duas amostras de Cb e duas
amostras de Cr. Neste caso, as amostras de crominância possuem a mesma resolução vertical das
amostras de luminância, mas possuem metade da resolução horizontal. No formato 4:2:0, para
cada quatro amostras de Y, existe apenas uma amostra de Cb e uma amostra de Cr. Neste caso, as
amostras de crominância possuem metade da resolução horizontal e metade da resolução vertical
do que as amostras de luminância. A nomenclatura 4:2:0 é usada por motivos históricos, pois os
números não representam a relação lógica entre os componentes de cor, a qual deveria ser 4:1:1
(RICHARDSON, 2003).
A sub-amostragem de cor aumenta significativamente a eficiência da compressão, uma
vez que parte da informação da imagem é simplesmente descartada, sem causar impacto visual
perceptível ao olho humano. Considerando o formato 4:2:0 como exemplo, uma vez que cada
componente de crominância possui exatamente um quarto das amostras presentes no componente
de luminância, então um vídeo YCbCr no formato 4:2:0 irá utilizar exatamente a metade das
18
amostras necessárias para um vídeo RGB ou YCbCr no formato 4:4:4. Isso implica em uma taxa
de compressão de 50%, considerando apenas a sub-amostragem.
O padrão H.264/AVC considera que os dados do vídeo de entrada estão no espaço de
cores YCbCr (PURI, 2004). Sub-amostragens de cor nos formatos 4:2:0, 4:2:2 e 4:4:4 são
permitidos, a Figura 2.1 mostra o formato 4:2:0 que é o mais utilizado. Os círculos com
preenchimento em branco são amostras de luminância (Y), enquanto os círculos em cinza e preto,
representam as amostras de Crominância vermelha (Cr) e Crominância azul (Cb)
respectivamente.
Figura 2.1: Mostra da Sub-amostragen no Formato 4:2:0
2.2 Partição do Vídeo Digital
Um vídeo digital é formado por uma seqüência de quadros (frames), que, por sua vez,
são formados por pontos (pixels). Cada quadro do vídeo é dividido em slices, que são divididos
em macroblocos. Os macroblocos podem ser divididos em sub-macroblocos e blocos. O padrão
H.264/AVC é o primeiro que prevê a utilização de macroblocos com tamanhos variáveis (16x16,
16x8, 8x16 ou 8x8 pixels). Uma partição 8x8 é chamada sub-macrobloco, e um sub-macrobloco
com partição 8x8 pode ser particionado em blocos de 8x8, 8x4, 4x8 ou 4x4 pixels (PURI, 2004).
As Figuras 2.2 e 2.3 demonstram esta divisão.
19
Figura 2.2: Possíveis Partições de um Macrobloco
Figura 2.3: Possíveis Partições de um Sub-Macrobloco
A escolha do tamanho da partição depende de alguns fatores, porém nas áreas do quadro
do vídeo digital onde se tem mais movimento, o tamanho de partição escolhido deve ser menor
do que aqueles escolhidos para áreas onde se tem um menor movimento. Isto ocorre devido ao
fato de se tentar reduzir ao máximo o resíduo gerado pela etapa de predição. O resíduo é a
diferença dos elementos de luminância entre o quadro de referência e o quadro de vídeo atual
(que está sendo codificado), este resíduo passará pelo módulo das transformadas após a etapa de
predição para eliminar informações que não são relevantes para o olho humano.
A Figura 2.4 mostra um quadro de resíduos gerados sem compensação de movimento,
ou seja, através da predição intra-quadro, onde o codificador escolhe a melhor partição de acordo
com as mudanças existentes entre quadros, onde a menos mudanças a partição escolhida é 16x16
pixels, enquanto em áreas com mais mudanças partições menores são selecionadas.
20
Figura 2.4: Divisão de um Quadro com Várias Partições
Em um vídeo digital existe muita redundância na informação decorrente da similaridade
existente entre pontos vizinhos e também entre quadros vizinhos. Pontos vizinhos são pontos que
pertencem ao mesmo quadro e que são espacialmente vizinhos. Quadros vizinhos são quadros
pertencentes ao mesmo vídeo e que são temporalmente vizinhos.
A compressão de vídeos é uma técnica que utiliza algoritmos (codecs) para diminuir o
tamanho de uma imagem através da redução destas informações redundantes que formam a
imagem (SILVA, 2006).
2.3 Redundância de Dados
O objetivo da compressão de vídeo é eliminar as informações que são redundantes em
um vídeo digital, e assim, diminuir o número de bits necessários para a sua representação. Os
padrões de compressão de vídeo exploram justamente uma característica dos vídeos digitais que
são os vários tipos de redundância. Existem basicamente três tipos de redundâncias que são
exploradas na compressão de vídeos (AGOSTINI, 2007), são elas:
21
2.3.1 Redundância Espacial
A redundância espacial é, também, chamada de redundância intra-quadro ou
redundância interpixel e advém da correlação existente entre os pixels espacialmente distribuídos
em um quadro. Esta correlação pode ser percebida, tanto no domínio espacial, quanto no domínio
das freqüências. Esta correlação é visualmente percebida no domínio espacial quando são
observados pixels vizinhos em um quadro, que tendem a possuir valores semelhantes. Neste caso,
a redundância pode ser reduzida através da operação chamada de codificação intra-quadro,
presente em alguns padrões de codificação de vídeo atuais.
No domínio das freqüências a operação realizada para reduzir a redundância espacial é
chamada de quantização. Para aplicar a quantização, antes as informações da imagem devem ser
transformadas do domínio espacial para o domínio das freqüências. A quantização é uma divisão
inteira dos coeficientes gerados pela transformação e reduz grande parte dos coeficientes à zero.
Esta operação é irreversível, pois o resto da divisão não é armazenado e, deste modo, a
quantização gera perdas no processo de codificação. Mas é importante ressaltar que estas perdas
tendem a interferir de forma nula ou pouco significativa na qualidade perceptual da imagem.
2.3.2 Redundância Temporal
A redundância temporal, também chamada de redundância inter-quadros, é causada pela
correlação existente entre quadros temporalmente próximos em um vídeo. Na verdade, a
redundância temporal poderia ser classificada como apenas mais uma dimensão da redundância
espacial, como faz (GONZALES, 2003). Muitos blocos de pixels simplesmente não mudam de
valor de um quadro para outro em um vídeo, como por exemplo, em um fundo que não foi
alterado de um quadro para outro. Outros pixels apresentam uma pequena variação de valores
causada, por exemplo, por uma variação de iluminação. Por fim, também é possível que o bloco
de pixels simplesmente tenha se deslocado de um quadro para o outro, como por exemplo, em um
movimento de um objeto em uma cena. Todos os padrões atuais de codificação de vídeo visam
reduzir a redundância temporal. A exploração eficiente da redundância temporal conduz a
elevadas taxas de compressão, o que é fundamental para o sucesso dos codificadores.
2.3.3 Redundância Entrópica
A redundância entrópica está relacionada com as probabilidades de ocorrência dos
símbolos codificados. A entropia é uma medida da quantidade média de informação transmitida
por símbolo do vídeo (SHI, 1999). A quantidade de informação nova transmitida por um símbolo
22
diminui na medida em que a probabilidade de ocorrência deste símbolo aumenta. Então, os
codificadores que exploram a redundância entrópica têm por objetivo transmitir o máximo de
informação possível por símbolo codificado e, deste modo, representar mais informações com um
número menor de bits. A codificação de entropia, como é chamada, utiliza diferentes técnicas e
algoritmos de compressão sem perdas para atingir este objetivo.
Além destes três tipos de redundância existe um outro tipo de redundância também
explorada pelo padrão H.264/AVC, que diz respeito às características do sistema visual humano,
que fazem com que não consigamos captar alguns tipos de informações na imagem. Além disso,
algumas informações da imagem, como o brilho, por exemplo, são mais importantes para o
sistema visual humano do que outras, como a crominância. Este tipo de redundância de
informação é chamado de redundância psicovisual.
Este tipo de redundância é explorada pelo padrão na sub-amostragem de cores utilizadas
pelo vídeo digital, pois utilizando um sub-espaço de amostragem do tipo YCbCr 4:2:0, já existe
um eliminação das informações de cor do vídeo, fazendo com que o vídeo já esteja representado
com uma compressão referente a este tipo de redundância.
2.4 Sumário
Neste capítulo foram abordados alguns conceitos básicos sobre a compressão de vídeo
como: partições de macroblocos, espaço de cores e sub-amostragem de cores, além dos tipos de
redundâncias existentes em vídeos digitais. No próximo capítulo serão abordados os principais
pontos relacionados ao padrão H.24/AVC de compressão de vídeo, descrevendo o histórico,
conceitos e as características dos principais módulos constituintes do padrão.
23
3 O PADRÃO H.264/AVC
Este capítulo traz um breve histórico e alguns conceitos além dos principais módulos do
codificador e do decodificador do padrão H.264/AVC de compressão de vídeo.
3.1 Histórico do padrão H.264/AVC
O padrão de compressão de vídeo H.264/AVC, foco deste trabalho, é o mais novo
padrão de compressão de vídeo e foi desenvolvido com o objetivo de dobrar a taxa de
compressão em relação aos demais padrões existentes até então. O padrão H.264/AVC foi
desenvolvido pelo JVT (ITU, 2000) que foi formado a partir de uma união entre os especialistas
do VCEG da ITU-T (ITU, 2003) e do MPEG da ISO/IEC (ISO, 1993). A primeira versão do
H.264/AVC foi aprovada em 2003.
O padrão H.264/AVC foi desenvolvido por um período de aproximadamente quatro
anos. As raízes deste padrão estão no projeto H.26L da ITU-T, que foi iniciado pelo VCEG (ITU,
2005), que construiu a chamada para propostas no início de 1998 e que criou o primeiro rascunho
deste novo padrão em agosto de 1999. O objetivo do projeto H.26L era dobrar a eficiência de
codificação atingida pelo padrão H.263 (ITU, 2000).
Antes do padrão H.264/AVC surgir, alguns outros padrões já haviam sido criados e já
estavam consolidados, servindo de base para o desenvolvimento do H.264/AVC. O primeiro
padrão relevante para a construção do H.264/AVC foi o H.261 da ITU-T (ITU, 1990). Este
padrão lançou as bases do que é usado até hoje na maioria dos padrões de compressão de vídeo:
DPCM com estimação de movimento na direção temporal, transformada discreta do coseno,
aplicada ao resíduo, e quantização linear seguida de codificação por entropia. Após o padrão
H.261, surgiu o padrão MPEG-1 da ISO/IEC (ISO, 1993) seguido do padrão MPEG-2 da
ISO/IEC, que também foi padronizado pela ITU-T como H.262 (ITU, 1994). Este padrão se
tornou um padrão popular e é muito usado até a atualidade em diversas aplicações. Apesar do
grande sucesso do padrão MPEG-2, a evolução dos padrões de compressão de vídeo não parou. O
padrão H.263 (ITU, 2000) foi lançado e incorporou alguns avanços obtidos pelos padrões MPEG1 e MPEG-2, bem como técnicas novas que vinham sendo pesquisadas intensamente tanto pela
indústria quanto pela academia.
Em 2001 o grupo MPEG da ISO/IEC finalizou o desenvolvimento do seu mais recente
padrão, conhecido como MPEG-4 Parte 2 (ISO, 1999). Então, ainda neste ano, o MPEG
24
construiu uma nova chamada de propostas, similar à do H.26L da ITU-T, para melhorar ainda
mais a eficiência de codificação atingida pelo MPEG-4. Então o VCEG, da ITU-T resolveu
submeter seu rascunho em resposta à chamada de propostas do MPEG e propôs a união de
esforços para completar o trabalho.
Analisando as respostas para sua chamada de propostas, o MPEG chegou a conclusões
que afirmaram as escolhas de desenvolvimento realizadas pelo VCEG no H.26L:
•
A estrutura de compensação de movimento com a transformada discreta do coseno
(DCT) era melhor do que as outras.
•
Algumas ferramentas de codificação de vídeo que foram excluídas no passado (do
MPEG-2, do H.263 ou do MPEG-4 Parte 2) por causa da sua complexidade
computacional, poderiam ser reexaminadas para inclusão no próximo padrão, devido
aos avanços na tecnologia de hardware.
•
Para maximizar a eficiência de codificação, a sintaxe do novo padrão não poderia
ser compatível com os padrões anteriores. Então, para permitir um avanço mais
acelerado na construção do novo padrão e para evitar duplicação de esforços, o ITUT e o ISO/IEC concordaram em unir esforços para desenvolverem, em conjunto, a
próxima geração de padrão para codificação de vídeo e concordaram em usar o
H.26L como ponto de partida. Então, foi criado, em dezembro de 2001, o JVT (ITU,
2005), formado por especialistas do VCEG e do MPEG. O JVT tinha o objetivo de
completar o desenvolvimento técnico do padrão até o ano de 2003. A ITU-T decidiu
adotar o padrão com o nome de ITU-T H.264/AVC e a ISO/IEC decidiu adotar o
padrão com o nome de MPEG-4 parte 10 - AVC (Advanced Video Coding Codificação de Vídeo Avançada). O padrão H.264/AVC teve seu rascunho final
(ITU, 2003) aprovado em outubro de 2003 (SULLIVAN, 2005). Em julho de 2004, o
JVT adicionou algumas novas funcionalidades ao padrão H.264/AVC através de
uma extensão do padrão chamada de Fidelity Range Extensions (FRExt) (ITU,
2005).
25
3.2 Perfis
O padrão H.264/AVC contém um grande conjunto de ferramentas de codificação de
vídeo, contudo, não se faz necessária a implementação de todas as ferramentas para todas as
aplicações. Por exemplo, as ferramentas de resiliência à erros, podem não serem necessárias para
armazenamento de vídeos ou CDs. Se todos os decodificadores fossem obrigados a implementar
todas as ferramentas, eles seriam desnecessariamente muito complexos.
Assim, o padrão define subconjuntos de ferramentas de codificação, que são
implementadas de acordo com a classe de aplicação. Um decodificador pode escolher por
implementar somente um subconjunto (perfil) de ferramentas. Primeiramente o padrão definiu
três perfis: Baseline, Main e Extended.
O perfil Baseline é direcionado a aplicações como vídeotelefonia, videoconferência e
vídeo sem fio. O perfil Baseline suporta codificação intra-quadro e inter-quadro (usando somente
slices I e P) e uma codificação de entropia com códigos de comprimento de palavra variável
adaptativos ao contexto (CAVLC). O perfil Main é focado na transmissão de televisão e no
armazenamento de vídeo (AGOSTINI, 2005).
Slices do tipo I (intra), são slices formados por macroblocos que foram codificados
utilizando a predição intra-quadros. Os slices do tipo P (Preditivos), são os slices formados por
macroblocos do tipo I e P, macroblocos do tipo P foram codificados através da predição interquadro e utilizam apenas um quadro do vídeo como referência. Os slices do tipo B (Bipreditivos), podem conter macroblocos do tipo I e B, os do tipo B são formados através da
codificação inter-quadro e possuem até dois quadros como referência.
Estes três perfis inicialmente propostos pelo padrão H.264/AVC não incluíram suporte
para vídeos com qualidade mais elevada, como as necessárias em ambientes profissionais. Para
responder às exigências deste tipo de aplicação, uma continuação do projeto JVT foi realizada
para adicionar novas extensões para as capacidades do padrão original. Estas extensões foram
chamadas de extensões para alcance de fidelidade (fidelity range extensions - FRExt). O FRExt
produziu um grupo de quatro novos perfis chamados coletivamente de perfis High (SULLIVAN,
2004). A Figura 3.1 mostra a estrutura de divisão entre os perfis do padrão H.264/AVC.
O perfil High (HP) inclui vídeo com 8 bits por amostra e com relação de cor 4:2:0. O
perfil High 10 (Hi10P) suporta vídeo a 10 bits por amostra, também com uma relação de cor
26
4:2:0. O perfil High 4:2:2 (H422P) inclui suporte à relação de cor 4:2:2 e vídeos a 10 bits por
amostra. Finalmente, o perfil High 4:4:4 (H444P) dá suporte à relação de cor 4:4:4 (ou seja, sem
nenhuma subamostragem), suporte a vídeo com até 12 bits por amostra e, adicionalmente,
suporta a codificação sem perdas em regiões do vídeo.
Extended
Slices
SP e SI
Partição de
dados
Grupo de Slices
e ASO
Main
Predição
ponderada
High
Transformada 8x8
High 4:2:2
Formato
4:2:2
Predição Intra 8x8
Slices B
Slices I
Monocromático
Quantização
adaptativa
High 10
Slices P
Slices
Redundantes
CAVLC
CABAC
Amostras
Até 10 bits
Baseline
Figura 3.1: Estrutura dos Perfis Atuais do Padrão H.264/AVC (ROSA, 2009)
3.3 Formato dos Dados Codificados
O H.264/AVC faz uma distinção entre e a Camada de Codificação de Vídeo (VCL) e a
Camada de Abstração de Rede (NAL). A saída do processo de codificação é o dado VCL (uma
seqüência de bits que representam os dados do vídeo codificado) que são mapeados para a
unidade NAL para uma posterior transmissão ou armazenamento. Cada unidade NAL contém um
Raw Byte Sequence Payload (RBSP), que é um conjunto de dados correspondentes ao dado do
vídeo codificado ou são informações de cabeçalho. Uma seqüência de vídeo codificado é
representado por uma seqüência de unidades NAL, como mostra a Figura 3.2, e pode ser
transmitida através de uma rede baseada em pacotes, com uma transmissão em bitstream ou
armazenada em um arquivo. O propósito de especificação separada entre a VCL e a NAL, é de
fazer uma clara distinção entre as características de codificação (VCL) das características de
transporte (NAL).
27
Figura 3.2: Seqüência de Unidades NAL
3.4 Núcleo do Padrão H.264/AVC
O padrão H.264/AVC atingiu seu objetivo de alcançar as mais elevadas taxas de
processamento dentre todos os padrões existentes. Mas para isso, foi necessário um grande
aumento na complexidade computacional das operações dos codecs que seguem o padrão
H.264/AVC em relação aos demais padrões disponíveis na atualidade. Este aumento de
complexidade impede, pelo menos na tecnologia atual, a utilização de codecs H.264/AVC
implementados em software quando as resoluções são elevadas e/ou quando se deseja tempo real,
com 30 quadros por segundo, por exemplo. A complexidade do problema via software somado
pelo enorme interesse comercial que reside neste padrão, têm impulsionado equipes de pesquisa e
desenvolvimento ao redor do mundo a tratarem deste tema visando otimizações algorítmicas e/ou
implementações em hardware para que os requisitos das aplicações sejam atendidos.
Existem muitas aplicações potenciais para codecs H.264/AVC, que vão desde aparelhos
celulares à televisão digital e, por isso, a indústria está extremamente ativa nesta área e algumas
soluções para HDTV já estão disponíveis, principalmente para decodificadores (que são mais
simples). Estas soluções comerciais costumam conter muitos segredos industriais, de modo que
muitas destas soluções não estão reportadas em detalhes na literatura. Do ponto de vista da
academia, existem muitas equipes espalhadas pelo mundo trabalhando com o H.264/AVC,
buscando soluções de software e/ou hardware para tentar resolver o problema da complexidade
elevada do padrão. Vários trabalhos têm sido publicados nos últimos anos, mas a área encontra-se
ainda repleta de problemas sem solução e, conseqüentemente, muitas contribuições inovadoras
poderão ser descobertas e implementadas.
A Figura 3.3 apresenta o codificador. Existem, neste modelo, dois quadros do vídeo
sendo utilizados simultaneamente. Além do quadro atual, que está sendo comprimido, também é
utilizado um quadro de referência anteriormente processado. Os quadros são divididos em
diversas partes, normalmente chamadas de macroblocos, para serem processados utilizando a
codificação inter-quadros ou intra-quadros. A chave seletora na Figura 3.3 representa a decisão
tomada pelo hardware de controle do codificador sobre qual modo de codificação deve ser
28
utilizado para cada bloco. A codificação Intra-quadros não depende de blocos de quadros
anteriores e é realizada considerando apenas as informações contidas no quadro. Deste modo, na
codificação Intra-quadros é explorada a redundância espacial. A codificação Inter-quadros é mais
utilizada e são construídos a partir do quadro atual e de quadros previamente codificados.
Após um bloco do quadro atual ser codificado, pela codificação intra-quadro ou pela
codificação inter-quadros, é realizada uma subtração entre os valores do bloco original e os
resultados da codificação. Esta diferença é chamada de resíduo. O resíduo, então, é enviado para
os módulos responsáveis por reduzir a redundância espacial no domínio das freqüências. A
primeira operação nesta direção é a transformada (módulo T na Figura 3.3). O módulo T
transforma a informação do domínio espacial para o domínio das freqüências. Neste domínio, a
Quantização pode ser aplicada, reduzindo a redundância espacial presente nos resíduos. Por fim,
a codificação de entropia reduz a redundância entrópica, que está relacionada à forma como os
dados são codificados.
Figura 3.3: Diagrama de Blocos do Codificador do Padrão H.264/AVC (RICHARDSON, 2003)
Como as perdas de informação, que geram a diferença entre o quadro atual original e o
quadro atual reconstruído, acontecem no estágio de quantização, a imagem deve ser reconstruída
a partir deste ponto. A codificação e decodificação de entropia são desnecessárias para a
reconstrução do quadro atual justamente porque estas etapas não geram perdas. Então, é aplicada
a operação inversa da quantização e, após a quantização inversa, é aplicada a transformada
inversa, gerando os resíduos reconstruídos. Aos resíduos é somado o resultado da codificação
intra-quadro ou inter-quadros do bloco reconstruído. Finalmente, o bloco reconstruído está pronto
29
e pode ser armazenado para ser utilizado pela codificação inter-quadros do próximo quadro ou
pode ser utilizado diretamente pela codificação intra-quadro dos próximos blocos do quadro
atual.
A Figura 3.4 mostra o decodificador do padrão H.264/AVC. Como a codificação de
entropia não gera perdas de informação, a operação de decodificação de entropia gera exatamente
o mesmo resultado gerado pela saída da quantização no codificador. Após a decodificação de
entropia, as amostras remontadas são entregues para a quantização inversa e para a transformada
inversa, reconstruindo o resíduo. Estas operações são idênticas às apresentadas no codificador. A
decodificação inter-quadros utiliza o quadro de referência para localizar os blocos de referência.
Estes blocos são, então, somados aos resíduos, para gerar os blocos reconstruídos. Finalmente, os
blocos reconstruídos são armazenados para serem usados como referência para a decodificação
do próximo quadro e para a visualização do vídeo decodificado. A decodificação intra-quadro
utiliza os blocos reconstruídos do quadro atual para reconstruir os blocos codificados pelo
codificador inter-quadros. De maneira similar à codificação inter-quadros, os macroblocos que
passam pela decodificação intra-quadro são somados aos resíduos e armazenados para serem
usados como referência e para visualização do vídeo.
Figura 3.4: Diagrama de Blocos do Decodificador do Padrão H.264/AVC (RICHARDSON,
2003)
3.4.1 Módulo de Predição Inter-Quadro
Neste módulo estão contidos os módulos de estimação de movimento (ME – Motion
Estimation) e compensação de movimento (MC – Motion Compensation), que juntos realizam
um processo de predição de um array retangular de pixels, que pode ser um macrobloco ou
bloco, através da escolha de um outro array retangular similar de algum quadro de referência que
30
já foi previamente codificado, e mapeando esta escolha através de um vetor de movimento (MV).
Como já foi dito anteriormente no padrão H.264/AVC este array retangular pode ter os seguintes
tamanhos: 4x4, 4x8, 8x4, 8x8, 16x8, 8,16 e 16x16 pixels.
O módulo da estimação de movimento está presente apenas nos codificadores. Este
módulo é o que apresenta a maior complexidade computacional dentre todos os módulos de um
codificador H.264/AVC (PURI, 2004). Este grande custo computacional é função das inovações
inseridas neste módulo do padrão, que tiveram o objetivo de atingir elevadas taxas de
compressão. Residem nos módulos da ME e MC as principais fontes de ganhos do H.264/AVC
em relação aos demais padrões de compressão de vídeo (RICHARDSON, 2003).
Além do uso de blocos de tamanho variável para realizar a ME e a MC. O H.264/AVC
também prevê o uso de múltiplos quadros de referência, que não precisam ser somente os
quadros I ou P imediatamente anteriores ou posteriores. Também é uma inovação o uso de novas
opções para a bi-predição, como a predição ponderada e direta para os slices do tipo B. Além
disso, os vetores de movimento podem apontar para fora da borda do quadro. Por fim, a predição
de vetores de movimento com base nos vetores vizinhos também é uma novidade (ITU-T, 2005),
(RICHARDSON, 2003) e (WIEGAND, 2003).
Figura 3.5: Determinação do Vetor de Movimento para um Bloco
A estimação de movimento deve prover as ferramentas de codificação capazes de
localizar, nos quadros de referência, qual macrobloco mais se assemelha ao macrobloco atual.
Assim que o macrobloco é encontrado, a ME deve gerar um vetor indicando a posição deste
macrobloco no quadro de referência. Este vetor é chamado de vetor de movimento e deve ser
31
inserido junto com a codificação do macrobloco. A Figura 3.5 ilustra um quadro de referência e
um quadro atual. No quadro de referência está destacada a área de pesquisa e o bloco que está
sendo pesquisado.
Para a simplificação do processo, a realização da estimação de movimento é considerado
apenas o componente de luminância do macrobloco. Cada componente de crominância possui a
metade da resolução horizontal e vertical do componente de luminância, então os componentes
horizontal e vertical de cada vetor de movimento são divididos por dois para serem aplicados aos
blocos de crominância (AGOSTINI, 2007).
A compensação de movimento é o processo de compensação para o deslocamento de
objetos movidos de um quadro para outro. O Compensador de Movimento (MC) no codificador
H.264/AVC é uma etapa precedida pela etapa de Estimação de Movimento (ME). É função da
compensação de movimento, a partir do vetor de movimento gerado na ME, localizar os blocos
de melhor casamento na memória de quadros anteriormente codificados (quadros passados e/ou
futuros) e montar o quadro predito. Este quadro será subtraído do quadro atual para gerar o
quadro de resíduos que passará pelas transformadas existentes no módulo T (transformada
discreta do cosseno - DCT, transformada Hadamard 4x4 e transformada Hadamard 2x2) que é
foco deste trabalho. As Figuras 3.6, 3.7 e 3.8 mostram o mesmo quadro de um vídeo antes e
depois da compensação de movimento e também um quadro de resíduo das luminâncias,
utilizando uma partição de macrobloco de 16x16 pixels (SILVA, 2006).
32
Figura 3.6: Quadro do Vídeo Antes da MC
Na Figura 3.7 ficam nítidas as bordas dos blocos de 16x16 pixels, após a reconstrução da
imagem pelo compensador de movimento. Isto acontece devido ao fato do "casamento" entre
blocos vizinhos não acontecer perfeitamente, fazendo com que seja gerado o chamado Efeito de
Bloco. Para suavizar este efeito é utilizado um filtro de deblocagem, este filtro é detalhado na
seção 3.4.5.
33
Figura 3.7: Quadro do Vídeo Após a MC
Figura 3.8: Quadro de Luminância Resídual
34
3.4.2 Módulo de Predição Intra-Quadro
A predição intra-quadro é realizada através da interpolação de valores dos pixels das
bordas de blocos espacialmente vizinhos que foram anteriormente codificados. Esta interpolação
é realizada direcionalmente, com múltiplos modos, sendo cada um deles empregado em uma
direção espacial diferente, o padrão H.264/AVC define nove modos diferentes de predição intraquadro (PURI, 2005) para blocos de luminância 4x4, estes nove modos estão mostrados na
Figura 3.8, onde a direção espacial é indicada pela direção da seta (AGOSTINI, 2007).
Contudo, a predição intra-quadro pode ocorrer com blocos de luminância com tamanho
de 16x16 pixels. Neste caso, existem quatro modos possíveis de se realizar a predição, conforme
está apresentado na Figura 3.9. Os modos 0 e 1 são simples cópias na vertical ou na horizontal
das amostras reconstruídas das bordas. O modo 2 é o modo DC e é formado por uma média
simples dos elementos das bordas, cujo resultado é copiado para todas as posições do bloco. O
modo 3 aplica uma função linear que considera as amostras horizontais e verticais (H e V na
Figura 3.9) das bordas.
Figura 3.9: Nove modos de predição Intra-Quadro para Blocos de 4x4 Pixels
35
Na Figura 3.9, que envolve a predição Intra-Quadro 4x4, nos modos 0 (vertical) e 1
(horizontal) o bloco predito é construído pela cópia das amostras vizinhas A-D e I-L. O modo 2
(DC) faz uma média das amostras A-D e I-L e copia o resultado para todas as amostras do bloco
predito. Os modos diagonais (3 a 8) são calculados por interpolações lineares (usando os valores
das amostras vizinhas), dependendo das direções e da posição da amostra no bloco predito.
Figura 3.10: Quatro modos de predição Intra-Quadro para Blocos de 16x16 Pixels
Na Figura 3.10, que envolve a predição Intra-Quadro 16x16, no modo 0, o macrobloco
predito é construído pela cópia das amostras vizinhas contidas em H.. O modo 1 é similar ao
modo 0, mas copia as amostras em V. O modo 2 (DC) realiza uma média das amostras contidas
em H e V e copia o resultado para todas as amostras do macrobloco predito. O modo 3 é o mais
complexo, pois necessita a geração prévia de parâmetros de ajuste antes do cálculo da predição
para cada amostra do macrobloco predito. Estes parâmetros de ajuste estão relacionados com as
coordenadas x,y do macrobloco e com os valores de H e V que são previamente calculados em
função das coordenadas x,y do macrobloco (DINIZ, 2009).
Deve-se observar que os modos de predição para amostras de crominância são
semelhantes aos modos Intra 16x16, porém os números dos modos são alterados (modo 0 – DC,
modo 1 – horizontal, modo 2 – vertical, modo 3 – plano). Além disso, os modos de predição
Intra-Quadro para crominância são aplicados em blocos 8x8.
3.4.3 O Módulo das Transformadas Diretas (T) e das Transformadas Inversas T-1
O módulo T, que será o alvo deste trabalho, é responsável pelas transformadas diretas e
está presente apenas nos codificadores H.264/AVC. As entradas para o módulo T são blocos 4x4
de resíduos gerados pela etapa de predição. A FDCT 2-D (Transformada Discreta do Cosseno
Direta bi dimensional) é aplicada a todas as amostras de entrada, tanto de luminância quanto de
36
crominância. O cálculo da FDCT 2-D é aplicado sobre todos os dados de entrada, mas, no caso
de amostras com informação de crominância ou com informação de luminância, cuja predição
tenha sido do tipo intra-quadro 16x16, é necessário a realização de um cálculo extra. Em ambos
os casos, aplica-se a transformada Hadamard 2-D direta sobre os coeficientes DC resultantes da
FDCT 2-D. Esta segunda transformada, trata-se de uma inovação do padrão H.264/AVC e tem
por objetivo atingir ainda mais compressão em áreas homogêneas do vídeo. Os coeficientes DC
dos blocos de luminância cuja predição tenha sido intra-quadro 16x16 são submetidos a uma
transformada Hadamard 4x4 direta. Por outro lado, uma transformada Hadamard 2x2 direta é
aplicada a todos os coeficientes DC dos blocos de crominância. A transformada Hadamard 4x4
direta definida pelo padrão H.264/AVC é aplicada apenas sobre os elementos DC dos blocos 4x4
(resultantes da aplicação da FDCT 2-D) de um macrobloco 16x16 de luminância que tenha
utilizado a predição intra-quadro 16x16. Maiores detalhes deste bloco das transformadas serão
abordados no Capítulo 4.
As operações das transformadas inversas (bloco T-1) são muito semelhantes às operações
das transformadas diretas. As transformadas Hadamard 2x2 e Hadamard 4x4 são calculadas
diretamente sobre os coeficientes DC provenientes da etapa de quantização, antes da etapa de
quantização inversa. Após estas operações, os coeficientes são entregues à etapa de quantização
inversa para então serem processado pela etapa inversa da Transformada Discreta do Coseno
Inversa (IDCT 2-D). Para coeficientes de crominância ou de luminância, quando a predição
selecionada é Intra 16x16, a transformada Hadamard 4x4 inversa é aplicada sobre os coeficientes
DC dos blocos de luminância, enquanto que, para os blocos de crominância, aplica-se a
Hadamard 2x2 inversa sobre os blocos 2x2 de coefciientes DC de crominância.
3.4.4 O Módulo da Quantização Direta (Q) e da Quantização Inversa (Q-1)
O módulo Q realiza a quantização direta e a correção da escala do cálculo das
transformadas. Este módulo está presente apenas no codificador H.264/AVC. A quantização é
também chamada de scaling no padrão H.264/AVC. O fator de escala para cada elemento em
cada bloco varia em função do parâmetro de quantização (QP – Quantization Parameter)
associado com o macrobloco que contém o bloco, e com uma função de posição do elemento
dentro do bloco. Um algoritmo de controle no codificador do padrão controla o valor do
parâmetro de quantização (PURI, 2004).
37
O módulo Q-1 realiza a quantização inversa e a correção da escala do cálculo das
transformadas. Alguns autores defendem que não é correto chamar este bloco de quantização
inversa, uma vez que a quantização direta é um processo irreversível. Deste modo, estes autores
utilizam o termo rescaling ao invés do termo quantização inversa (AGOSTINI, 2007). O módulo
Q-1 está presente nos codificadores e nos decodificadores H.264/AVC, como pode ser visto nas
Figuras 3.1 e 3.2.
3.4.5 O Módulo do Filtro de Deblocagem
Este filtro é mandatório nos decodificadores, mas opcional nos codificadores de vídeo
(de acordo com o padrão H.264/AVC). Este filtro se encontra no laço de codificação interquadros (ver Figura 3.3), tendo como objetivo tornar mais suave o efeito de blocos do quadro
reconstruído antes dele ser usado para a predição do tipo Inter-quadros de um macrobloco ou para
ser exibido. Este efeito de bloco pode ser visualizado na Figura 3.7.
O filtro de deblocagem opera sobre um macrobloco após a compensação de movimento
e da codificação residual, ou sobre um macrobloco após a predição intra-quadro e a codificação
residual, dependendo se o macrobloco é codificado através da codificação intra-quadro ou interquadro. O resultado na saída do filtro de deblocagem é armazenado para ser usado como quadro
de referência, exceção para aquelas figuras que não serão usadas como quadro de referência.
O filtro atua nas bordas do macrobloco e do bloco, a operação do filtro de deblocagem é
adaptativa em relação a um conjunto de vários fatores, entre eles estão o parâmetro de
quantização do macrobloco atual e dos macroblocos vizinhos, a magnitude do vetor de
movimento e o tipo de codificação do macrobloco. Também são levados em consideração os
valores dos pixels que serão filtrados, tanto do macrobloco atual como os valores dos
macroblocos vizinhos.
3.4.6 O Módulo da Codificação de Entropia
Na codificação de entropia, que está presente nos codificadores e decodificadores o
padrão H.264/AVC introduz algumas ferramentas que aumentam bastante a sua eficiência de
codificação. Nos níveis hierárquicos superiores (quadros,etc.), os elementos sintáticos são
codificados usando códigos binários fixos ou de comprimento variável. A partir do nível de slices
ou abaixo (macroblocos, blocos, etc.), os elementos sintáticos são codificados usando a
38
codificação aritmética adaptativa ao contexto (CABAC) (RICHARDSON, 2003) ou códigos de
comprimento variável (VLC).
No caso do uso de VLC, a informação residual (coeficientes das transformadas
quantizados) é codificada usando a codificação de comprimento variável adaptativa ao contexto
(CAVLC) (RICHARDSON, 2003), enquanto que as demais unidades de codificação são
codificadas usando códigos de comprimento variável com construção regular, como a codificação
Exp-Golomb (SALOMON, 2000). A opção pelo CABAC não está disponível nos perfis baseline
e extended.
A principal inovação introduzida na codificação de entropia do padrão H.264/AVC,
tanto na codificação aritmética quanto na codificação VLC é o uso de codificação adaptativa
baseada em contextos. Nela, a maneira com que são codificados os diversos elementos sintáticos
depende do elemento a ser codificado, da fase em que se encontra o algoritmo de codificação e
dos elementos sintáticos que já foram codificados (AGOSTINI, 2007).
A especificação do padrão H.264/AVC define apenas a sintaxe do bitstream e o
processo de decodificação. O processo de codificação é deixado de fora do escopo do padrão para
permitir maior flexibilidade para as implementações. Mas o controle do codificador é um
problema chave para a compressão, pois ele determina quais as decisões de codificação serão
tomadas para cada vídeo processado (WIEGAND, 2003) e uma das decisões que o codificador
necessita tomar é sobre qual o tipo de codificação utilizar (CABAC ou CAVLC). É muito
importante que as decisões tomadas sejam as melhores possíveis, pois com escolhas sub-ótimas,
alguns dos benefícios trazidos pelo H.264/AVC podem ser perdidos (PURI, 2004). Independente
da decisão tomada pelo codificador o decodificador deve estar apto para atender a todas.
A codificação/decodificação aritmética requer operações aritméticas para gerar as faixas,
o que faz com que a codificação aritmética (CABAC) seja bem mais complexa
computacionalmente do que os códigos de comprimento variável (CAVLC). Esta complexidade
elevada deve ser tratada tanto pelo codificador quanto pelo decodificador H.264/AVC e é um
custo adicional associado ao uso do CABAC. Por outro lado, os ganhos em eficiência de
codificação com a utilização do CABAC são significativos, 15% mais eficiente. Assim, o
compromisso entre complexidade e eficiência de codificação deve ser avaliado para a tomada de
decisão de qual tipo de codificador será utilizado na codificação de entropia dos codecs
H.264/AVC.
39
3.5 Alguns Trabalhos da Literatura de Desenvolvimento dos Módulos do
Padrão H.264/AVC
Como já foi citado neste trabalho existe muita pesquisa sendo realizada sobre o padrão
H.264/AVC, tanto pela comunidade acadêmica quanto pela indústria, pois, o H.264/AVC está
sendo adotado como o padrão para as mais diversas aplicações, desde a TV Digital, onde as
informações da imagem do vídeo serão transmitidas na forma digital (bit) ao invés da forma
analógica tradicional, até o Blu-Ray que é um formato de disco óptico da nova geração para vídeo
de alta definição e armazenamento de dados de alta densidade e que compete para se converter no
padrão de discos ópticos sucessor do DVD tendo como seu rival o HD-DVD.
Portanto esta seção tem como objetivo mostrar alguns trabalhos de pesquisa que estão
sendo realizados na área e que permitem a utilização deste padrão em várias aplicações. São
apresentados alguns trabalhos de pesquisa para cada um dos blocos do padrão H.264/AVC
,mostrados nas Figuras 3.1 e 3.2.
No trabalho de (JIN, 2007), é proposta uma execução em pipeline para a codificação
Intra-Quadro 4x4, a fim de reduzir as dependências entre blocos consecutivos. Além disso, o
trabalho cita que esta execução da predição Intra-Quadro com pipeline pode ser integrado com
outras operações da codificação Intra-Quadro, permitindo uma execução em paralelo. O trabalho
também mostra que com esta implementação o tempo de execução é reduzido em até 41%
quando comparado com trabalhos anteriores.
Em (HWANGBO, 2007), uma arquitetura para a transformada inversa 2-D do
decodificador do H.264/AVC é proposta. A arquitetura utiliza um bloco de multiplicação e
permutação de matrizes. Pela utilização da permutação de matrizes, a matriz da IDCT é
regularizada e a transformada Hadamard inversa é inserida na IDCT com uma menor
modificação. Com isto, esta arquitetura proposta eliminou o array de registradores de
transposição para fazer a transformada direta 2-D possível com a latência mínima de um ciclo de
clock.
No trabalho de (AZEVEDO, 2007), é apresentado o desenvolvimento de uma arquitetura
para a compensação de movimento bi-preditiva para o decodificador do H.264/AVC (MoCHA).
O projeto da arquitetura caracterizou uma hierarquia de memória para reduzir a largura de banda
e o número de ciclos de acesso a memória. A arquitetura usa um datapath simples para processar
40
áreas com referências bi-preditivas e processa amostras de luminância e chrominância em
paralelo.
Em (CHAO, 2007), é proposta uma arquitetura de decodificação combinada e o projeto
de transformada flexível com um alto throughput para a decodificação do resíduo dos
decodificadores do H.264/AVC. A quantização inversa é combinada com a CAVLC para
conseguir uma simplificação no decodificador. Além disso, é também proposta uma arquitetura
para a transformada flexível que realiza a computação de todas as transformadas que são
utilizadas no decodificador do padrão H.264/AVC. Assim, todas as transformadas são realizadas
na mesma arquitetura.
Este trabalho de dissertação de mestrado tem como objetivo dar uma contribuição para o
desenvolvimento do padrão H.264/AVC com técnicas para o aumento de desempenho dos blocos
das Transformadas e de Estimação de Movimento.
3.6 Sumário
Este capítulo apresentou as principais características do padrão H.264/AVC. Foi
abordado o histórico do padrão, assim como os principais perfis, que incluem as principais
ferramentas do padrão, de acordo com a aplicação. Foram também mostradas as principais
características dos principais módulos que compõem o codificador e o decodificador do padrão
H.264/AVC. O próximo capítulo será dedicado ao estudo das transformadas diretas e da
estimação de movimento do padrão H.264/AVC, que são os principais alvos de estudo deste
trabalho.
41
4 TRANSFORMADAS DIRETAS (BLOCO T) E ESTIMAÇÃO DE
MOVIMENTO DO PADRÃO H.264/AVC
Dadas as elevadas taxas de compressão de dados necessárias para a utilização das novas
tecnologias, qualquer sistema de codificação de vídeo moderno terá que fazer uso da
compensação/estimação de movimento para minimizar a redundância temporal em seqüências de
vídeo. A redundância temporal (também chamada de redundância inter-quadros) é causada pela
correlação existente entre quadros temporalmente próximos em um vídeo. Contudo, ao contrário
do que acontece nas aplicações de emissão e armazenamento de vídeo, os requisitos em termos
de desempenho impostos por estas aplicações não permitem o uso de métodos ótimos de
estimação de movimento, tal como o algoritmo de pesquisa exaustiva. Desta forma, torna-se
necessária a pesquisa de algoritmos que possam atender aos requisitos de reduzida complexidade
computacional com aspectos de eficiência na qualidade do vídeo digital em alta definição. Neste
trabalho, será utilizado como ponto de partida o algoritmo de estimação de movimento proposto
em (PORTO, 2008), que é baseado no algoritmo de busca Diamond Search.
Além da estimação de movimento, a etapa de predição intra-quadro é outra inovação
introduzida pelo padrão H.264/AVC, pois é realizada no domínio espacial. O módulo das
transformadas (chamado de bloco T) aparece no caminho crítico da codificação intra-quadro. os
algoritmos das Transformadas Hadamard 4x4 e 2x2 e Transformada Discreta do Cosseno (DCT),
que fazem parte integrante do bloco T do padrão H.264/AVC, agregam um grande número de
operações aritméticas. Desta forma, torna-se importante a implementação de arquiteturas
dedicadas destes algoritmos, com operadores aritméticos eficientes, que possam reduzir a
complexidade computacional dos cálculos realizados por estes módulos.
A seguir são apresentados conceitos das transformadas presentes no módulo T do padrão
H.264/AVC, bem como os principais conceitos relativos à etapa de estimação de movimento.
4.1 O Módulo das Transformadas Diretas (T)
Como dito anteriormente, a predição intra-quadro é mais uma inovação do padrão
H.264/AVC. Após um bloco do quadro atual ser codificado pela codificação intra-quadro ou pela
codificação inter-quadros, é realizada uma subtração entre os valores do bloco original e os
resultados da codificação. Esta diferença é chamada de resíduo. O resíduo é enviado para os
módulos responsáveis por reduzir a redundância espacial no domínio das freqüências.
42
A redundância espacial advém da correlação existente entre os pixels espacialmente
distribuídos em um quadro. Esta correlação pode ser percebida, tanto no domínio espacial, quanto
no domínio das freqüências. No domínio espacial, esta correlação é visualmente percebida
quando são observados pixels vizinhos em um quadro, que tendem a possuir valores semelhantes.
Neste caso, a redundância pode ser reduzida através da operação chamada de codificação intraquadro. No domínio das freqüências a operação realizada para reduzir a redundância espacial é
chamada de quantização.
Para aplicar a quantização, antes as informações da imagem devem ser transformadas do
domínio espacial para o domínio das freqüências. A primeira operação nesta direção é o módulo
T (módulo das transformadas) que transforma a informação do domínio espacial para o domínio
das freqüências. Após, a quantização pode ser aplicada, reduzindo a redundância espacial
presente nos resíduos. No bloco da quantização ocorre a eliminação de informação que não é
perceptível ao olho humano, ou mesmo a eliminação de informação desnecessária para o perfeito
entendimento do vídeo.
O módulo T, que será o alvo deste trabalho e está apresentado na Figura 4.1, é
responsável pelas transformadas diretas e está presente apenas nos codificadores H.264/AVC. As
entradas para o módulo T são blocos 4x4 de resíduos gerados pela etapa de predição. A FDCT 2D (Transformada Discreta do Cosseno Direta bi dimensional) é aplicada a todas as amostras de
entrada, tanto de luminância quanto de crominância. O cálculo da FDCT 2-D é aplicado sobre
todos os dados de entrada, mas, no caso de amostras com informação de crominância ou com
informação de luminância, cuja predição tenha sido do tipo intra-quadros 16x16, é necessário a
realização de um cálculo extra. Em ambos os casos, aplica-se a transformada Hadamard 2-D
direta sobre os coeficientes DC resultantes da FDCT 2-D. Esta segunda transformada, trata-se de
uma inovação do padrão H.264/AVC e tem por objetivo atingir ainda mais compressão em áreas
homogêneas do vídeo. Os coeficientes DC dos blocos de luminância, cuja predição tenha sido
intra-quadros 16x16, são submetidos a uma transformada Hadamard 4x4 direta. Por outro lado,
uma transformada Hadamard 2x2 direta é aplicada a todos os coeficientes DC dos blocos de
crominância. A transformada Hadamard 4x4 direta definida pelo padrão H.264/AVC é aplicada
apenas sobre os elementos DC dos blocos 4x4 (resultantes da aplicação da FDCT 2-D) de um
macrobloco 16x16 de luminância que tenha utilizado a predição intra-quadros 16x16.
43
Figura 4.1: Diagrama de Blocos do Módulo da Transformadas Diretas (T)
A Figura 4.2 mostra como o bloco T separa as 16x16 amostras de luminância (Y) e as
8x8 amostras de crominância (Cb e Cr) para as transformadas. Inicialmente, o macrobloco de
luminância (Y na Figura 4.2) passa pela FDCT 2-D. Se o modo é intra-quadro 16x16, então,
como foi explicado, os coeficientes DCs das matrizes 4x4 resultantes da FDCT 2-D passam pela
Hadamard 4x4 direta. Neste caso, primeiramente é enviado para saída o bloco -1 na Figura 4.2,
com os resultados da Hadamard 4x4 direta, e depois os elementos AC são o enviados para a saída
(blocos 0 a 15 na Figura 4.2). Se o modo não é intra-quadro 16x16, então os blocos 0 a 15 são
enviados diretamente para a saída e a Hadamard 4x4 não é aplicada. Seguindo os 16 blocos de
luminância, são processados quatro blocos de crominância Cb e quatro blocos de crominância Cr.
Os blocos de crominância passam pela FDCT 2-D e, sob os elementos DC dos resultados, é
aplicada a Hadamard 2-D 2x2. Então é enviado para a saída o bloco 16 na Figura 4.2, com os
resultados da Hadamard 2x2 para o componente Cb, depois é enviado o bloco 17, com os
resultados da Hadamard 2x2 para Cr. Finalmente, os coeficientes AC de crominância são
enviados para a saída, primeiro os de Cb (blocos 18 a 21) e depois os de Cr (blocos 22 a 25)
(AGOSTINI, 2005).
44
Figura 4.2: Ordem de Processamento de Amostras pelo Módulo T
A seguir são apresentados os principais conceitos de cada uma das transformadas
presentes no módulo T do padrão H.264/AVC.
4.1.1 A Transformada Discreta do Cosseno (DCT)
Como mostrado em (KHAYAM, 2003) a DCT 2-D direta (DCT em duas dimensões) é
uma extensão direta da FDCT 1-D (Forward DCT 1-D). Esta transformada é aplicada a todas as
amostras de entrada, tanto de luminância quanto de crominância. A FDCT 2-D do padrão
H.264/AVC é uma aproximação inteira da DCT 2-D real. Esta aproximação foi realizada para
reduzir a complexidade do cálculo e evitar erros de casamento entre o codificador e o
decodificador, ou seja, evitar que sejam realizados cálculos diferentes para a codificação e a
decodificação de um mesmo quadro do vídeo. O cálculo da FDCT 2-D é aplicado sobre todos os
dados de entrada, tanto de luminância (blocos 4x4) quanto de crominância (blocos 2x2), e a sua
aproximação é definida de acordo com a Equação 4.1 (AGOSTINI, 2007).
(4.1)
45
Na Equação 4.1, X é a matriz 4x4 de entrada, Cf é a matriz da FDCT 1-D inteira, CfT é a
transposta da matriz da FDCT e Ef é a matriz de fatores de escala. O símbolo
na matriz Ef são
constantes de aproximação da matriz da Transformada do Coseno e são representadas pela
Equação 4.2.
(4.2)
4.1.2 A Transformada Hadamard
No caso de amostras com informação de crominância ou com informação de luminância,
cuja predição tenha sido do tipo intra-quadro 16x16, um cálculo adicional com a transformada
Hadamard é realizado sobre os coeficientes DC resultantes da FDCT 2-D. A transformada
Hadamard é uma inovação do padrão H.264/AVC e foi inserida com o objetivo de atingir ainda
mais compressão em áreas homogêneas do vídeo. A transformada Hadamard explora uma
correlação residual que ainda permaneça sobre os coeficientes da FDCT 2-D (RICHARDSON,
2002).
Os coeficientes DC dos blocos de luminância cuja predição tenha sido intra-quadro
16x16 são submetidos a uma transformada Hadamard 4x4 direta. Por outro lado, uma
transformada Hadamard 2x2 direta é aplicada sob os coeficientes DC dos blocos de crominância.
Então, os 16 elementos DC dos 16 blocos do macrobloco irão formar a matriz 4x4 WD de entrada
para a Hadamard direta 4x4, como mostra a Equação (4.3). Na Equação 4.3, YD representa o
bloco de resíduos DC transformados pela Hadamard 4x4.
(4.3)
46
Como pode ser observado na equação 4.3, os elementos das matrizes possuem apenas
valores -1 e 1. Deste modo, apenas somas e subtrações são necessárias para realizar os cálculos
relativos a esta transformada. A divisão por dois realizada em todos os elementos da matriz de
resultados é um simples deslocamento de uma casa binária para a direita (AGOSTINI, 2007).
A transformada Hadamard 2x2 é aplicada apenas para amostras DC de crominância.
Esta transformada é utilizada tanto para Cb quanto para Cr. Em função da relação de entrada
4:2:0 para Y, Cb e Cr, cada macrobloco possui 16x16 amostras de luminância, 8x8 amostras de
Cb e 8x8 amostras de Cr. As amostras de crominância passam pela FDCT 2-D em blocos de 4x4
amostras. Então, cada matriz 8x8 de entrada é formada por quatro matrizes 4x4. Os quatro
elementos DC das quatro matrizes resultantes da FDCT 2-D passam pela Hadamard 2-D 2x2. O
cálculo da Hadamard 2x2 definido pelo padrão H.264/AVC está apresentado em (4.4). Pode ser
observado na fórmula abaixo que os cálculos da Hadamard 2x2 sobre as amostras DC de Cb e Cr
são muito simples, consistindo de poucas somas e subtrações. Assim como na Equação 4.3, WD
representa o bloco de resíduos DC. Já o termo WQD representa o bloco de resíduos DC
transformados pela Hadamard 2x2. O módulo T, sendo formado pelas três transformadas que
estão apresentadas, deve sincronizar a operação entre elas, de modo a gerar o fluxo correto de
dados na sua saída.
(4.4)
4.2 O Módulo da Estimação de Movimento
O módulo da estimação de movimento está presente apenas na etapa de codificação de
vídeo. Este módulo é o que apresenta a maior complexidade computacional dentre todos os
módulos de um codificador H.264/AVC (PURI, 2004). Este grande custo computacional é função
das inovações inseridas neste módulo do padrão, que tiveram o objetivo de atingir elevadas taxas
de compressão.
Para a simplificação do processo, para a realização da estimação de movimento é
considerado apenas o componente de luminância do macrobloco, pois, cada componente de
47
crominância possui a metade da resolução horizontal e vertical do componente de luminância,
então os componentes horizontal e vertical de cada vetor de movimento são divididos por dois
para serem aplicados aos blocos de crominância.
A principal inovação do H.264/AVC no ponto de vista da estimação de movimento está
na possibilidade de utilização de tamanhos de blocos variáveis para realizar a estimação de
movimento. Ao invés de usar um macrobloco inteiro na estimação de movimento, o padrão
H.264/AVC permite o uso de partições de macrobloco e partições de sub-macroblocos. As
partições de macroblocos possuem tamanhos de 16x16, 8x16, 16x8 e 8x8 e as partições de submacroblocos são permitidas somente se a partição de macrobloco selecionada foi a de 8x8. Neste
caso, as quatro partições 8x8 do macrobloco podem ser divididas em mais quatro formas que
podem ter o tamanho 8x8, 4x8, 8x4 ou 4x4, como já foi apresentado anteriormente nas Figuras
2.1 e 2.2.
Este método de particionar macroblocos em sub-blocos de tamanho variável é conhecido
como compensação de movimento estruturada em árvore. Cada bloco de crominância é dividido
da mesma maneira que os blocos de luminância, exceto pelo tamanho da partição, que terá
exatamente a metade da resolução horizontal e vertical da partição de luminância. Por exemplo,
uma partição de 8x16 de luminância corresponde a uma partição de 4x8 de crominância. Um
vetor de movimento é necessário para cada partição de macrobloco ou sub-macrobloco. Cada
vetor de movimento precisa ser codificado e transmitido junto com as informações do vídeo
codificado (bitstream), bem como o tipo de partição escolhida. A escolha de um tamanho de
partição grande (16x16, 16x8, 8x16) implica na utilização de um número menor de vetores de
movimento e também uma quantidade menor de bits é necessária para indicar o tipo de partição
utilizada. Por outro lado, o resíduo gerado pode conter uma quantidade significativa de energia
em áreas com muitos detalhes. A escolha de um tamanho de partição pequeno (8x4, 4x4) pode
gerar um resíduo com quantidade de energia mínima depois da compensação de movimento, mas
esta escolha requer a utilização de um número maior de vetores de movimento, além da
necessidade de identificar a partição de sub-macrobloco escolhida. Assim é possível perceber que
a escolha do tamanho da partição possui um impacto significativo no desempenho da compressão
(RICHARDSON, 2003).
48
Em geral, uma partição grande é apropriada para áreas mais homogêneas do quadro e
uma partição menor tende a ser mais apropriada para áreas com muitos detalhes. O tamanho de
partição é escolhido no algoritmo do codificador a partir de alguma métrica que conduza a uma
codificação mais eficiente, isto é, que analise o compromisso entre a geração de um resíduo
mínimo e a geração de um número mínimo de vetores de movimento. A melhor escolha é
realizada tomando por base os resultados da análise para todos os tamanhos de partição de cada
macrobloco. Então, é escolhido aquele tamanho de partição que apresentar a maior eficiência de
codificação. Pode-se concluir que a complexidade computacional desta operação é bastante
elevada, uma vez que os cálculos da estimação de movimento são realizados para vários
tamanhos de partição diferentes e apenas uma destas partições é escolhida. Por isso, a estimação
de movimento é o módulo mais crítico na implementação de codificadores H.264/AVC. Uma
outra característica importante da estimação de movimento do padrão H.264/AVC é que ela
prevê uma precisão de ¼ de pixel para os vetores de movimento. Normalmente, os movimentos
que acontecem de um quadro para o outro não estão restritos a posições inteiras de pixel. Assim,
se são utilizados apenas vetores de movimento com valores inteiros, normalmente não é possível
encontrar casamentos bons. Por isso, o padrão H.264/AVC prevê a utilização de vetores de
movimento com valores fracionários de ½ pixel e de ¼ de pixel. Na Figura 4.3 é apresentado um
exemplo da precisão do vetor de movimento com valores fracionários. Na Figura 4.3, um bloco
4x4 no quadro atual (a) é predito de uma região do quadro de referência na vizinhança da posição
do bloco atual. Se as componentes horizontal e vertical do vetor de movimento são inteiras (b),
existem amostras relevantes do bloco. Se uma ou ambas as componentes do vetor são valores
fracionários (c), as amostras de predição são geradas pela interpolação entre amostras adjacentes
no quadro de referência (RICHARDSON, 2003).
Figura. 4.3: Estimação de Movimento com Precisão de Fração de Pixel
49
A estimação de movimento deve prover um algoritmo eficiente capaz de localizar, nos
quadros de referência, qual macrobloco mais se assemelha ao macrobloco atual. Assim que o
macrobloco é encontrado, a ME deve gerar um vetor indicando a posição deste macrobloco no
quadro de referência. Este vetor é chamado de vetor de movimento e deve ser inserido junto com
a codificação do macrobloco. Os algoritmos de busca para a estimação de movimento
determinam a forma como o melhor casamento (best matching), para o bloco do quadro atual,
será buscado dentro da área de pesquisa do quadro de referência. O algoritmo de busca tem
influência direta na complexidade computacional da estimação, bem como na qualidade dos
vetores gerados. Podem-se dividir os algoritmos de estimação em dois grandes grupos:
algoritmos ótimos e sub-ótimos.
Algoritmos ótimos analisam todas as posições dentro da área de pesquisa para gerar o
vetor que represente a menor diferença entre as regiões pesquisadas. Algoritmos sub-ótimos
utilizam determinados métodos de busca que eliminam alguns cálculos, reduzindo a
complexidade e gerando vetores que podem não ser os que resultam no menor erro.
O critério de similaridade (critério de distorção) é a maneira como as diferenças entre as
regiões comparadas são avaliadas. Os critérios podem considerar desde a simples diferença
aritmética entre as regiões até cálculos que tentam fazer uma relação com o resultado visual da
comparação (RICHARDSON, 2002). Dentre os critérios mais utilizados pode-se citar o erro
médio quadrático MSE (Mean Square Error), o menor erro absoluto MAE (Minimum Absolute
Error) (RICHARDSON, 2002) e a soma das diferenças absolutas SAD (Sum of Absolute
Differences) (RICHARDSON, 2002). O SAD é o critério de similaridade mais comumente
utilizado para os algoritmos de estimação de movimento, devido à sua simplicidade. O SAD
calcula a distorção entre regiões comparadas como sendo o somatório das diferenças absolutas,
para cada ponto do bloco atual e do bloco candidato da área de pesquisa (KUHN, 1999). A
função para o cálculo do SAD é dada de acordo com a Equação (4.5):
(4.5)
50
onde:
• SADx,y representa o SAD para a posição (x,y).
• R representa amostras do quadro reconstruído.
• P representa amostras do quadro original.
• N é o tamanho do bloco.
O primeiro passo, para calcular o SAD para o bloco de posição (x,y), é calcular o
módulo da diferença entre as amostras do bloco de referência e do bloco da área de pesquisa.
Esse cálculo é repetido para todas as amostras do bloco de tamanho NxN, sendo que os resultados
intermediários são acumulados, e o resultado final desta acumulação é o valor resultante de SAD
para o bloco candidato da área de pesquisa. O resultado do SAD é sempre positivo, pois a
acumulação é feita através do somatório dos módulos das diferenças (ZANDONAI, 2002). Como
são necessárias apenas somas, subtrações e acumulações este critério é largamente utilizado em
aplicações em hardware. Daqui para frente neste trabalho, toda vez que for mencionado critério
de similaridade ou resultado de erro para qualquer algoritmo, estaremos sempre nos referindo ao
resultado de SAD. O SAD será o critério adotado para todas as avaliações dos algoritmos
apresentados neste trabalho.
Pode-se citar para a etapa de estimação de movimento os seguintes algoritmos: busca
completa (Full Search - FS) (BHASKARAN, 1999) e (LIN, 2005), Three Step Search (TSS)
(JING, 2004), Diamond Search (DS) (KUHN, 1999) e (YI, 2005), One at a Time Search (OTS)
(RICHARDSON, 2002), Hexagon Based Search (HS) (ZHU, 2002) e Dual Cross Search (DCS)
(BANH, 2004). Dos algoritmos citados, apenas o algoritmo Full Search pode ser considerado um
algoritmo ótimo, pois ele avalia todas as posições possíveis da área de pesquisa para determinar o
melhor resultado. Os demais algoritmos se enquadram na classe de algoritmos sub-ótimos, que
utilizam determinadas heurísticas para reduzir o número de cálculos na obtenção do melhor
casamento entre os blocos. Em (PORTO, 2008) foi realizado um trabalho mostrando que o
algoritmo Diamond Search foi o mais eficiente entre os algoritmos citados. Desta forma, foi
implementado um hardware dedicado para esta estrutura, cujos detalhes são mostrados no
capítulo seis deste estudo. O objetivo deste trabalho é aumentar o desempenho desta arquitetura a
partir do uso de somadores compressores.
51
4.2.1 Algoritmo Diamond Search (PORTO, 2008)
O algoritmo Diamond Search possui dois padrões diamante que são usados na etapa
inicial e final do algoritmo. A Figura 4.4 ilustra os padrões Large Diamond Search Pattern
(LDSP) e o padrão Small Diamond Search Pattern (SDSP). O padrão LDSP consiste em nove
comparações e é utilizado na etapa inicial da pesquisa. Já o padrão SDSP consiste em quatro
comparações e é utilizado na etapa final da pesquisa, com o intuito de refinar o resultado obtido
na etapa anterior (KUHN, 1999).
Figura 4.4: Large Diamond (LDSP) (L) e Small Diamond (SDSP) (S)
O algoritmo começa aplicando o padrão LDSP ao centro da área de pesquisa. Caso o
valor de menor erro seja encontrado no centro, o algoritmo aplica o padrão SDSP para refinar o
resultado obtido. Caso contrário, um novo LDSP é aplicado à posição de menor erro da etapa
anterior. Esta posição pode pertencer a uma aresta ou a um vértice do diamante. As Figuras,
4.5(a) e 4.5(b) representam, respectivamente, a busca por uma aresta e a busca por um vértice. No
caso da busca por uma aresta, mais três valores são calculados para formar um novo diamante em
torno da nova origem. Quando o novo centro é um vértice do diamante, mais cinco valores são
calculados para formar o novo diamante em torno do centro. Caso o menor erro não seja
encontrado no centro do novo diamante, a etapa de busca será repetida, seja ela por uma aresta ou
por um vértice. Quando o menor erro for encontrado para o centro do diamante o padrão SDSP é
aplicado. Então mais quatro valores imediatamente ao redor do centro serão calculados e a
posição com o menor erro será a escolhida.
52
Figura 4.5(a): Busca por uma aresta
Figura 4.5(b): Busca por um vértice
Novamente não se pode determinar o número de operações do algoritmo. O algoritmo
Diamond Search pode começar a sua busca em uma direção e desviar a pesquisa ao longo do
processo, o que pode evitar que o algoritmo caia em um mínimo local.
4.3 Sumário
Este capítulo apresentou detalhes e as principais características de dois módulos do
padrão H.264/AVC, que são alvo deste trabalho. Foram mostrados os principais aspectos do
bloco T (que é composta das Transformadas Diretas) e do bloco de Estimação de Movimento.
Estes blocos são compostos de um grande número de operações aritméticas de soma e subtração.
Para a realização destas operações de forma eficiente, utiliza-se neste trabalho, circuitos
somadores Carry Save (CSA) e somadores compressores que realizam a soma de mais de dois
operandos simultaneamente de forma eficiente. No próximo capítulo serão mostrados os
principais aspectos dos somadores eficientes utilizados neste trabalho.
53
5 CIRCUITOS SOMADORES EFICIENTES
Vários circuitos somadores são apresentados na literatura no sentido de acelerar a
propagação do carry ao longo dos módulos somadores. Neste trabalho, explora-se a soma de
vários operandos simultaneamente, com o menor caminho crítico possível, como forma de
acelerar os cálculos das Transformadas Diretas e da Estimação de Movimento. São utilizados
circuitos somadores Carry Save e somadores compressores que podem realizar soma simultânea
de n valores de operandos. A seguir, são apresentados alguns conceitos de circuitos somadores
Carry Save e circuitos somadores compressores, bem como as suas estruturas básicas. Em relação
ao somador compressor, é apresentado o compressor 4:2, que permite realizar a soma de 4
valores simultaneamente. Após, apresenta-se a extensão desta estrutura para compressores 8:2 e
16:2, que são estruturas que realizam a soma de 8 e 16 operandos simultaneamente.
5.1 Somador Carry Save
O somador Carry Save tem como principal finalidade somar mais de dois números de
uma vez. O seu princípio de funcionamento é baseado na idéia de calcular separadamente a soma
e o carry. Após, somá-los separadamente, com o valor de carry multiplicado por dois
(deslocamento à esquerda), alcançando assim a soma total. Esta estrutura tem como vantagem
conseguir somar vários números mais rapidamente. O somador Carry Save (CSA) tem a
característica de efetuar a soma de três números simultaneamente. A idéia básica é que três
números possam ser reduzidos para dois, como um compressor 3:2, como mostra o exemplo da
Figura 5.1 (PARHAMI, 1999).
Figura 5.1: Exemplo de um Somador Carry Save
54
Como pode ser observado na Figura 5.1, somente na recombinação do carry com a soma
é utilizado um somador onde o carry é propagado. Apenas na última linha de soma é que existe a
propagação normal do carry a partir da utilização de somadores do tipo Ripple Carry (RCA). A
Figura 5.2 mostra um exemplo de adição de seis números usando o somador Carry Save.
Figura 5.2: Exemplo de Soma de Números de 4 bits Usando a Estrutura Carry Save
Como é mostrado na Figura 5.2, o somador Carry Save é apresentado como um bloco
com três entradas e duas saídas. Neste caso, os somadores completos full-adder não dependem de
outras somas para efetuar sua operação. Cada somador recebe três números e produz dois como
saída, tal que 2*C+S=P+Q+R. De fato, pode-se então converter o problema de computação
P+Q+R para 2*C+S sem esperar carry algum. Os módulos x2 mostrados na Figura 5.1 não
requerem lógicas adicionais, sendo somente necessário a interconexão apropriada dos blocos. A
soma final M+2N representa uma soma normal de dois números. O somador Carry Save se torna
bastante rápido devido ao fato de simplificar as saídas de carry ao invés de propagar para a
esquerda.
5.2 O Compressor 4:2
Em (WEINBERGER, 1981) foi apresentada uma estrutura de soma de números
chamada 4-2 Carry-Save module na qual era possível a realização da soma simultânea de quatro
55
números. Esta estrutura foi posteriormente aperfeiçoada por (OKLOBDZIJA, 1996). Esta
estrutura contém uma combinação de células de somadores completos em conexão truncada na
qual possibilita uma rápida compressão dos produtos parciais. Como mostra a Figura 5.3, um
compressor 4:2 possui cinco entradas e três saídas.
Figura 5.3: Estrutura do Compressor 4:2
As cinco entradas e a saída da soma possuem o mesmo peso(j), e as saídas Cout e Carry
possuem peso maior (j+1). Além disto, a saída Cout não é função de Cin (que faz com que não
ocorra a propagação do sinal de carry). Para esta implementação as saídas da soma (sum), do
carry intermediário (Cout) e do carry de saída (carry) são expressas pelas Equações (5.1), (5.2) e
(5.3) (PARHAMI, 1999).
Sum=[(A
B)
C]
D]
Cin
Cout=A• B + A •C + B• C
Carry=[(A
B)
C] • (D + Cin) + D •Cin
(5.1)
(5.2)
(5.3)
O compressor 4:2 descrito pelas equações acima possui um caminho crítico dado pela
soma dos atrasos de 4 portas lógicas XOR conectadas em série, como mostra a Equação (5.1). A
Figura 5.3 mostra que este compressor pode ser implementado utilizando dois somadores
completos em série, o que reforça o caminho crítico composto pelas 4 portas lógicas XOR. A
implementação desta estrutura torna as somas dos produtos parciais mais rápidas devido à maior
compressão dos termos de soma. A Tabela verdade de um compressor 4:2 é mostrada na Tabela
5.1.
56
De fato, o resultado de uma operação de soma usando compressor 4:2 é dado por: Sum +
2(Cout + carry). Como pode ser visto em um exemplo da Tabela 5.1, com todos os valores de
entrada em nível lógico 1 (inclusive o termo Cin), o resultado será dado por 111 que é
equivalente a: [1+2(1+1)]=5. Para haver o resultado correto, deve haver uma recombinação dos
resultados parciais de Cout e carry através de um meio somador.
Tabela 5.1: Verdade do Compressor 4:2
Um aperfeiçoamento na estrutura de um circuito compressor 4:2, usando multiplexador
(OKLOBDZIJA, 1996) é mostrado na Figura 5.4. Esta estrutura possui um caminho critico com
seu valor de atraso máximo dado por três portas XOR, o que representa um caminho crítico
menor do que o mostrado na estrutura da Figura 5.3. Outra vantagem deste tipo de estrutura é o
fato de que o circuito multiplexador e a porta XOR podem ser otimizados no nível de transistores
utilizando portas de transmissão (PRASAD, 2001).
A Figura 5.5 apresenta um exemplo de utilização de compressores 4:2 em uma soma de
4 números de 14 bits. Deve-se observar que são necessários halfadders (HA) e fulladders (FA)
para a recombinação dos valores parciais das somas anteriores, visto que há a propagação de
57
carry de um módulo de soma do compressor para o próximo bloco. Uma linha de pipeline,
introduzida entre os compressores e a linha de soma dos resultados parciais dos compressores, é
usada para o aumento de desempenho dos circuitos compressores.
Figura 5.4: Compressor 4:2 Utilizando Multiplexadores
Figura 5.5: Circuito Somador de 14 bits Utilizando Compressor 4:2
5.3 Compressores Hierárquicos 8:2 e 16:2
A partir do projeto do compressor 4:2, foram feitas implementações de outras estruturas
para a realização de um maior número de somas simultâneas. Nesta etapa, utiliza-se a extensão
do compressor 4:2 para a realização dos compressores 8:2 e 16:2 que permitem a soma
simultânea de até 8 e 16 valores respectivamente. A Figura 5.6 apresenta o compressor 8:2 e a
Figura 5.7 mostra o diagrama em blocos do compressor 8:2 a partir da utilização de compressores
4:2.
58
Figura 5.6: Diagrama de Blocos do Circuito Compressor 8:2
Figura 5.7: Estrutura Hierárquica do Compressor 8:2
O compressor 8:2 é composto por treze entradas, sendo oito delas primárias (A, B, C, D,
E, F, G e H) e cinco entradas de carry de entrada - Cin (Cin0, Cin1, Cin2, Cin3 e Cin4). A
estrutura do compressor apresenta sete saídas, sendo duas primárias (Sum e carry) e cinco para
carry de saída - Cout (Cout0, Cout1, Cout2, Cout3 e Cout4). Assim como no compressor 4:2, o
compressor 8:2 tem suas entradas e a saída Sum com mesmo peso (j) e as saídas restantes com
peso (j+1). A representação para a obtenção dos valores de soma a partir dos valores de entrada é
mostrada na Equação 5.4.
59
Soma = Sum + 2(Cout0 + Cout1 + Cout2 + Cout3 + Cout4 + Carry)
(5.4)
Quando todas as entradas estiverem em nível lógico 1, inclusive todas as entradas de
Cin, a soma deverá ser 13, ou seja, Soma = 1 + 2(1+1+1+1+1+1) = 13. Observa-se na Tabela 5.2
que para a entrada (j) igual a 13, a saída com peso (j+1) é igual a 6 e a saída Sum com peso j é
igual a 1. A interpretação deste resultado está estabelecida no fato de que o valor 6 multiplicado
por 2 (peso j+1 =2) é somado ao valor de Sum de valor igual a 1 (peso j = 1). O mesmo raciocínio
é utilizado para os demais valores da Tabela 5.2.
Tabela 5.2: Tabela Verdade do Compressor 8:2
A Figura 5.8 mostra um exemplo de soma de 8 números de 14 bits a partir da utilização
de blocos compressores 8:2. Da mesma forma, como mostrado anteriormente para o compressor
4:2, são utilizados halfadders e fulladders para a realização das somas dos resultados parciais dos
módulos compressores.
60
Figura 5.8: Circuito Somador de 14 Bits Utilizando Compressor 8:2
A partir do projeto de compressores 8:2, foi possível a expansão do circuito compressor
para realizar a adição de 16 operandos simultaneamente. A Figura 5.9 mostra o diagrama de
blocos do compressor 16:2 e a Figura 5.10 representa a estrutura hierárquica do compressor 16:2
com a utilização de compressores 8:2 e 4:2.
Figura 5.9: Diagrama de Blocos do Circuito Compressor 16:2
61
Figura 5.10: Estrutura Hierárquica do Compressor 16:2
O compressor 16:2 é composto por 29 entradas, sendo dezesseis delas primárias (A, B,
C, D, E, F, G, H, I, J, L, M, N, O, P e Q) e treze entradas de carry de entrada - Cin (Cin0, Cin1,
Cin2, Cin3, Cin4, Cin5, Cin6, Cin7, Cin8, Cin9, Cin10, Cin11 e Cin12). A estrutura também
apresenta quinze saídas, sendo duas primárias (Sum e carry) e treze para carry de saída - Cout
(Cout0, Cout1, Cout2, Cout3, Cout4, Cout5, Cout6, Cout7, Cout8, Cout9, Cout10, Cout11 e
Cout12). Para a obtenção dos valores de soma, a partir dos valores de entrada, faz-se necessário
também o uso de uma equação representativa, dada na Equação 5.5.
Soma = Sum + 2(Cout0 + Cout1 + ... + Cout11 + Cout12 + Carry)
(5.5)
Se por exemplo, todas as entradas estiverem em nível lógico 1, inclusive todas as
entradas de Cin, a soma deverá apresentar um valor igual a 29. Desta forma, de acordo com a
equação 5.5: Soma = 1+2(1+1+1+1+1+1+1+1+1+1+1+1+1+1) = 29. Assim como para o
compressor 8:2, observa-se na Tabela 5.3 a influência dos pesos nos resultados apresentados na
Tabela 5.1. Por exemplo, para o valor de entrada igual a 29, o resultado de soma é obtido a partir
do valor de saída igual a 14, que deve ser multiplicado por 2 (devido ao peso j+1), somado ao
valor Sum igual a 1 (devido ao peso j).
62
Tabela 5.3: Tabela Verdade do Compressor 16:2
A Figura 5.11 apresenta um exemplo de soma de 16 operandos de 14 bits a partir da
utilização de compressores 16:2. Mais uma vez observa-se a necessidade da utilização de uma
última linha de meio somador (HA) e somadores completos (FA) para a recombinação das somas
dos valores de carry gerados pelos blocos dos compressores 16:2.
63
Figura 5.11: Circuito Somador de 14 bits Utilizando Compressor 16:2
5.4 Análise Comparativa dos Compressores
Nesta seção são apresentados resultados de síntese em FPGA mapeados para o
dispositivo EP1S20F780C5 da Altera (ALTERA, 2008) para os compressores 4:2, 8:2 e 16:2
respectivamente. A Tabela 5.4 mostra resultados de área e atraso dos circuitos compressores.
Como era esperado, o compressor 4:2 apresenta os melhores resultados de área e atraso.
Entretanto, deve-se observar na Tabela 5.4 que a diferença de atraso entre os compressores 4:2 e
8:2 não é significativa. Este resultado é interessante, visto que o compressor 8:2 pode ser
utilizado para uma maior quantidade de somas simultâneas de operandos com um reduzido valor
de atraso. Esta mesma relação é mantida quando é comparado o atraso do compressor 8:2 ao
atraso do compressor 16:2, o que torna atrativo o uso deste compressor para aplicações que
requerem uma maior quantidade de operações de soma, visto que este circuito pode realizar uma
grande quantidade de somas simultâneas com um valor de atraso relativamente baixo quando
comparado aos outros compressores. Além disso, os compressores 8:2 e 16:2 são implementados
a partir de blocos compressores 4:2 que apresenta um reduzido caminho crítico.
Para valores de área (elementos lógicos), os compressores mantêm uma proporção de
crescimento, visto que além do aumento de área existente entre os compressores há também um
aumento no número de entradas e saídas de carry, Cin e Cout nas arquiteturas. Os valores de
consumo de área obtidos mostram um aumento nos compressores 8:2 e 16:2 em relação ao
compressor 4:2. Com estes resultados, observa-se que é necessário considerar a aplicação alvo
onde será(ão) inserido(s) o(s) compressor(s), para que se possa observar a melhor relação custo
64
vs. benefício do número de entradas a serem somadas com o tempo gasto nestas operações e
escolher a melhor alternativa para ser utilizada. Caso o foco do projeto seja desempenho, pode-se
ter o compressor 16:2 como o mais indicado, pois realiza mais somas simultâneas em um ciclo de
relógio, com um atraso relativamente reduzido. Porém, quando a meta do projeto visa a utilização
menor de hardware, deve-se utilizar o compressor 4:2.
Tabela 5.4: Resultado de Síntese Para os Compressores
Elementos Lógicos
Atraso
Compressor
(LUTs)
(ns)
4:2
72
24,807
8:2
177
29,592
16:2
402
32,722
5.6 Sumário
Neste capítulo foram apresentados os principais conceitos sobre circuitos somadores
compressores. Foi possível observar a possibilidade de expansão destes circuitos compressores a
partir da estrutura básica de um compressor 4:2. Este estudo serve como base para a aplicação
destes compressores em circuitos que envolvam um grande número de operações de soma e
subtração. Neste trabalho, os blocos das Transformadas Diretas e a Estimação de Movimento do
padrão de compressão de vídeo do padrão H.264/AVC são usados como estudos de caso para a
aplicação dos somadores compressores. No próximo capítulo serão apresentadas as
implementações destas arquiteturas com o uso destes compressores, bem como os seus resultados
de síntese.
65
6 ESTUDOS DE CASO: MÓDULO T E ESTIMAÇÃO DE MOVIMENTO
Este capítulo apresenta os estudos de caso utilizados para o uso de somadores eficientes
para o aumento de desempenho das arquiteturas implementadas. Foram utilizados dois estudos de
caso referentes aos blocos operacionais no padrão H.264/AVC de compressão de vídeo, que são:
módulo das transformadas diretas e o módulo da estimação de movimento. Estes blocos foram
escolhidos em função do grande número de operações aritméticas agregadas aos algoritmos. No
caso, são utilizados circuitos somadores compressores 4:2, 8:2 e 16:2 que realizam operações
simultâneas de 4, 8 e 16 operandos respectivamente. A seguir são apresentados detalhes dos
módulos e as alternativas arquiteturais utilizadas com a inclusão dos somadores compressores.
6.1 Soluções arquiteturais: Módulo T
Na implementação das arquiteturas das transformadas que compõe o módulo T (FDCT2D, Transformada Hadamard 4x4 e Transformada Hadamard 2x2) foram feitos estudos
particulares em cada transformada para identificar qual somador compressor se comporta melhor
em cada caso. Por este motivo, em cada transformada foram estudados diferentes somadores
compressores na implementação do módulo T. Assim, nas próximas seções deste trabalho serão
mostrados os estudos individuais feitos para cada transformada. Após, será mostrada o resultado
obtido com a implementação completa do módulo T.
6.1.1 Estudo de caso para a FDCT-2D
Para a arquitetura da FDCT-2D foram feitas três implementações sem separabilidade
utilizando diferentes somadores compressores. Todas as implementações foram projetadas
seguindo o algoritmo definido na Equação 4.1. A partir dos resultados obtidos com as três
implementações foi feita a escolha de qual alternativa arquitetural será utilizada na
implementação do módulo T. Na FDCT-2D todas as entradas possuem 8 bits e as saídas 14 bits.
As três implementações foram comparadas com a arquitetura descritas na literatura (AGOSTINI,
2007).
6.1.1.1 Arquiteturas Propostas Neste Trabalho
A primeira arquitetura desenvolvida para implementar a FDCT 2-D, está apresentada na
Figura 6.1 e utiliza somadores compressores 4:2 (CA 4-2). A arquitetura da FDCT 2-D foi
projetada em um pipeline de quatro estágios. Interno a cada compressor 4:2 foi inserido um
estágio de pipeline. Este estágio de pipeline foi inserido entre a linha de compressores e a linha
66
de somadores utilizada para fazer a recombinação dos resultados parciais de soma e carry dos
compressores (ver figura 5.5). Além disso, a arquitetura possui mais um estágio implementado
com registradores, indicado na Figura 6.1 com o retângulo tracejado. Assim, cada estágio
necessita de somente um ciclo de relógio para realizar os seus cálculos. Nesta arquitetura, foram
utilizados 16 somadores compressores 4:2 em cada coluna. Os pequenos quadrados com shifters
para a esquerda representam os blocos de multiplicação por 2 que são necessários de acordo com
o algoritmo da transformada. Estas multiplicações são feitas com o deslocamento de uma posição
do operando binário para esquerda. As entradas possuem 8 bits de largura e 14 bits na saída e a
latência da arquitetura é de 4 ciclos de relógio.
Figura 6.1: Arquitetura para FDCT-2D utilizando compressores 4:2
A segunda versão arquitetural explorada, apresentada na Figura 6.2, utiliza oito
somadores compressores 8:2 (CA 8-2). A arquitetura foi projetada em um pipeline de dois
estágios. Novamente, um estágio do pipeline é interno ao compressor 8:2. O segundo estágio está
localizado entre a coluna dos compressores 8:2 e a coluna de somadores (como pode ser visto na
Figura 6.2). Esta coluna de somadores foi necessária para finalizar os cálculos de transformada
67
conforme o algoritmo apresentado na Equação 4.1. Nesta arquitetura a latência é de 2 ciclos de
relógio.
A última alternativa foi utilizando o compressor 16:2 (CA 16-2). Nesta versão foram
empregados 16 somadores compressores 16:2 que sozinhos realizam o cálculo completo da
FDCT-2D. Assim, a arquitetura apresenta somente um estágio de pipeline. Este estágio é interno
aos compressores 16:2, apresentando uma latência de um ciclo de relógio. A Figura 6.3 mostra
esta arquitetura.
Figura 6.2: Arquitetura para FDCT-2D utilizando compressores 8:2
68
Figura 6.3: Arquitetura para FDCT-2D utilizando compressores 16:2
6.1.1.2 Arquitetura proposta por (AGOSTINI, 2007)
Para validar os resultados de implementação obtidos com as três versões para a FDCT-2D
proposta neste trabalho foi feita uma comparação de resultados com a arquitetura descrita na
literatura proposta por (AGOSTINI, 2007). Esta arquitetura foi projetada em um pipeline de
quatro estágios, sendo que cada estágio utiliza 16 ciclos de relógio para finalizar as suas
operações. Como pode ser observado na Figura 6.4, apenas um operador é utilizado por estágio
de pipeline. A latência da arquitetura sem separabilidade é de 64 ciclos de relógio e são utilizados
8 bits na entrada e 14 bits na saída.
69
Figura 6.4 – Arquitetura para a FDCT-2D proposta por (AGOSTINI, 2007)
6.1.1.3 Resultados de síntese
A Tabela 6.1 mostra os resultados obtidos com as três implementações. Com o uso de
apenas um somador aritmético por estágio de pipeline a arquitetura original atingiu o menor uso
dos recursos de área, porém obteve o segundo pior resultado em frequência de operação
ganhando somente da arquitetura CA 4-2.
O estudo proposto neste trabalho é focado em aumentar o desempenho dos módulos do
padrão H.264/AVC. Portanto, os resultados mostram um ganho significativo no aumento de
desempenho da FDCT-2D quando são utilizados o compressor 8:2 e o compressor 16:2. Na
arquitetura CA 8-2 a frequência de operação foi um pouco maior que a arquitetura CA 16-2
devido à frequência do compressor 8:2 ser maior que a frequência do compressor 16:2. Outro
fator importante foi a inserção do pipeline nas arquiteturas, os resultados mostram que essa
técnica é mais eficaz para a arquitetura CA 8-2, pois, apresentou o melhor resultado de frequência
devido ao caminho crítico desta arquitetura ser composto somente pelo somador interno do
compressor 8:2. Contudo, a CA 16-2 foi a escolhida para implementar a FDCT-2D no módulo T
devido ao fato de que a diferença entre as freqüências de operação serem muito baixas e a CA 162 apresentar a sua latência de apenas um ciclo de relógio. O throughput é calculado em função do
número de amostras por segundo. Por exemplo, para a arquitetura da Transformada Discreta do
70
Coseno (CA 16-2), que opera 16 amostras em uma frequência de operação de 432,9 MHz, a taxa
é de 6.92G amostras por segundo (432.9,62MHz*16 = 6.92G amostras/s).
Tabela 6.1: Resultados de Síntese para a FDCT-2D sem Separabilidade
Área
Throughput
Arquitetura
Latência Frequência (MHz)
(# de gates)
(amostras/s)
Original (AGOSTINI,2007)
6375
4
398,40
6.37G
CA 4-2
10247
4
377,35
6.03G
CA 8-2
12083
2
434,78
6.95G
*CA 16-2
17027
1
432,90
6.92G
6.1.2 Estudo de caso para a Transformada Hadamard 4x4
A transformada Hadamard 4x4 foi o ponto de partida dos estudos com os somadores
compressores nos módulos do padrão H.264/AVC. Por este motivo, para esta transformada
particularmente, foram feitas várias implementações. Primeiramente foram realizadas
implementações em FPGAs, a fim de verificar o desempenho destes somadores neste módulo do
padrão. Após, também foram realizadas implementações das arquiteturas, que obtiveram melhor
desempenho em FPGA, na tecnologia ASIC.
Nesta seção são apresentados resultados obtidos a partir do uso de compressores nas
arquiteturas dedicadas da Transformada Hadamard 4x4 Direta, tanto para as implementações em
FPGA bem como para as implementações em ASIC.
6.1.2.1 Implementações de Arquiteturas Combinacionais em FPGA
Para FPGA foram feitas as seguintes implementações: arquitetura serial com
separabilidade, arquitetura serial sem separabilidade e arquitetura paralela combinacional,
explorando a utilização dos compressores 4:2, 8:2 e 16:2. As arquiteturas combinacionais
processam 16 amostras de entrada por ciclo de relógio, realizando seus cálculos no mesmo ciclo.
Consequentemente, suas amostras de saída também serão entregues no mesmo ciclo de relógio.
Particularmente, foram implementadas as seguintes arquiteturas combinacionais dedicadas para a
Transformada Hadamard: Arquitetura Combinacional com Compressor 4:2, Arquitetura
Combinacional com Compressor 4:2 e Subtrator Carry Save, Arquitetura Combinacional com
Ripple Carry, Arquitetura Combinacional com Compressor 8:2 e finalmente a Arquitetura
Combinacional com Compressor 16:2.
71
Todas as versões foram descritas em VHDL sintetizadas na ferramenta Quartus II e
mapeadas para o dispositivo Stratix EP1S20F780C5 ambos da Altera. Embora os resultados
obtidos neste trabalho tenham sido direcionados para FPGA, tem-se como foco na continuação
deste trabalho de mestrado, a obtenção destes resultados voltados para ASIC. Os resultados em
FPGA servem como parâmetro inicial de análise de comportamento das arquiteturas em relação a
esta tecnologia. Os resultados obtidos com estas implementações foram comparados com as
arquiteturas descritas em (AGOSTINI, 2007), que utilizam o somador Macro Function otimizado
para FPGA, para realizar as operações de soma e subtração.
6.1.2.1.1 Arquitetura Combinacional com Somadores/Subtratores Ripple Carry
Quando o projeto de hardware é focado para implementações em ASIC, é necessário
encontrar uma alternativa para o uso dos somadores nesta tecnologia, pois o uso de somadores
Macro Function são direcionados apenas para aplicações em FPGA. Entre os somadores
descritos na literatura, o que é utilizado como referência é o somador Ripple Carry. Este somador
possui a desvantagem de que em cada etapa da soma é necessário utilizar o carry da etapa
anterior e isto gera um grande atraso devido à propagação de carry por todos os bits de soma
como mostra a Figura 6.5.
Figura 6.5: Arquitetura Combinacional com Somadores/Subtratores Ripple Carry (AGOSTINI,
2007)
72
Esta versão arquitetural tem como finalidade a comparação de comportamento de um
somador que é muito empregado em aplicações ASIC. A arquitetura desta implementação é a
mesma implementada por (AGOSTINI, 2007).
6.1.2.1.2 Arquitetura Combinacional com Compressor 4:2
A primeira alternativa combinacional explorada para a Transformada Hadamard utiliza o
compressor 4:2 de 14 bits para realizar a soma de quatro operandos de entrada. Esta operação
resulta em uma saída de 16 bits. Com isto, para realizar a próxima adição de quatro números é
necessário o uso de compressores 4:2 de 16 bits. Para os casos onde é necessário realizar
subtrações, foi utilizado nesta arquitetura um circuito responsável pelo complemento de dois dos
operandos de entrada, representado na Figura 6.6 pelos retângulos menores posicionados na
entrada da arquitetura. Este circuito realiza a inversão bit a bit do operando de entrada, e após o
soma com o valor ”1”, gerando assim o resultado em complemento de dois.
E este resultado servirá de entrada para o compressor, onde será realizada a soma com os
outros números para o cálculo da subtração. Nesta alternativa arquitetural foram empregados
complementadores de 14 e 16 bits. A inclusão do circuito complementador pode gerar um
acréscimo no consumo de potência e no atraso da arquitetura, pois a inversão bit a bit de um
operando tem como consequência o aumento na atividade de chaveamento do circuito, resultando
assim, no aumento de consumo de potência do circuito. O somador utilizado no módulo de
complemento de dois foi do tipo Ripple Carry. Este somador implica no aumento do atraso do
circuito, devido à propagação interna do carry neste operador aritmético. Na Figura 6.6, a divisão
por 2 (conforme a Equação 4.3 do algoritmo), está representada pela indicação “>>” nos
retângulos.
73
Figura 6.6: Arquitetura Combinacional com Compressores 4:2
6.1.2.1.3 Arquitetura Combinacional com Compressor 4:2 e Subtrator Carry-Save
Uma alternativa arquitetural proposta neste trabalho leva em consideração a subtração
dos operandos sem a necessidade dos módulos para realizar o complemento de dois. Esta
arquitetura é mostrada na Figura 6.7. Nesta nova arquitetura, são empregados circuitos
subtratores
Carry
Save
para
a
realização
de
subtração
de
três
operandos.
Os
somadores/subtratores Carry Save possuem uma estrutura interna otimizada, que propagam o
carry de um estágio de soma na diagonal. Isto faz com que o atraso diminua quando comparado a
somadores/subtratores tradicionais do tipo Ripple Carry.
Para realizar a implementação desta arquitetura foi necessário fazer uma manipulação
nos cálculos dos valores. Um exemplo desta manipulação pode-se verificar no cálculo do
operando b4 da Figura 6.7. Nas arquiteturas que utilizam os módulos de complemento a dois para
realizar a subtração, este operando é calculado da seguinte maneira: b4 = W0 + W4 – W8 – W12.
Com a manipulação, o cálculo de b4 é realizado através da soma dos quatros operandos de
entrada e após é feita a subtração desta soma pelo dobro dos valores de W8 e W12. Assim, o
cálculo de b4 é dado da seguinte maneira: b4 = W0 + W4 + W8 + W12 – 2*W8 – 2*W12. Como já
dito anteriormente esta alternativa foi estudada a fim de eliminar o módulo de complemento de
74
dois utilizado nas outras arquiteturas e também possibilitou o uso de um subtrator eficiente, no
caso, o Carry Save.
Figura 6.7: Arquitetura Combinacional com Compressor 4:2 e Subtrator Carry Save
6.1.2.1.4 Arquitetura Combinacional com Compressor 8:2
A terceira alternativa arquitetural explorada neste trabalho, utiliza o compressor 8:2 na
estrutura combinacional. Para atender à configuração de entradas paralelas, foi necessária a
utilização de 16 compressores 8:2 para a realização das somas das 16 amostras. Assim, para a
obtenção da saída final (S) da transformada, foi necessária a utilização de uma barreira de
somadores Ripple Carry na saída dos compressores 8:2 como mostra a Figura 6.8. Esta
arquitetura utiliza também o módulo de complemento de dois para a realização da subtração dos
operandos. Mais uma vez, a divisão por 2 do algoritmo está representada por “>>” nos
retângulos.
75
Figura 6.8: Arquitetura Combinacional com Compressor 8:2
6.1.2.1.5 - Arquitetura Combinacional com Compressor 16:2
A quarta e última alternativa arquitetural explorada, utiliza o compressor 16:2 na
estrutura combinacional. A principal vantagem desta alternativa é o fato de não utilizar uma
barreira de somadores após os compressores para calcular a saída final (S), como é o caso da
implementação anterior que utiliza o compressor 8:2. Na alternativa da Figura 6.9, o compressor
16:2 realiza o cálculo total da transformada fazendo a soma das dezesseis amostras de entrada e
gerando o resultado final após o deslocamento á direita (divisão por 2).
76
Figura 6.9: Arquitetura Combinacional com Compressor 16:2
6.1.2.1.6 Resultados das Arquiteturas Combinacionais
A Tabela 6.2 apresenta os resultados de área e atraso das arquiteturas combinacionais
implementadas. A arquitetura com o menor uso dos recursos de hardaware foi a que utiliza os
somadores Macro Function, pois este somador é otimizado para FPGA. Isto pode ser
comprovado a partir dos resultados das arquiteturas com somadores Ripple Carry e com o
compressor 4:2 e subtrator Carry Save que apresentam maiores valores de área em relação à
arquitetura com somador Macro Function, pois estes somadores não são otimizados para FPGA.
Entretanto, a exploração arquitetural feita com o compressor 4:2 e subtrator Carry Save mostrouse mais eficaz (com menos recursos de hardware) do que a arquitetura com somador Ripple
Carry.
As alternativas com os compressores 8:2 e 16:2 aumentaram significantemente o uso de
recursos de hardware. Isto devido ao fato destes compressores serem implementados a partir dos
77
compressores 4:2, que utilizam multiplexadores e portas XOR na sua estrutura interna. Nota-se
que a arquitetura com compressor 8:2 utiliza mais recursos de hardware do que a arquitetura com
compressor 16:2. Isto se explica pelo fato da arquitetura com compressor 8:2 utilizar uma barreira
de somadores, que não é necessária na implementação com compressor 16:2.
Tabela 6.2: Resultados de Área e Atraso para as Arquiteturas Combinacionais
Arquitetura
LUTS Atraso(ns)
Combinacional
Com Compressor 4:2
2.792
33,674
Com Compressor 4:2 e
1.654
27,795
Subtrator Carry-Save
Com Somador/Subtrator Ripple Carry 1.754
33,155
Com Compressor 8:2
5.295
34,794
Com Compressor 16:2
4.854
36,201
Com somador Macro Function
1.360
12,141
(AGOSTINI, 2007)
Além de apresentar menor valor de área, a arquitetura com somador Macro Function foi
a que apresentou o menor atraso entre todas as alternativas. Isto se deve ao fato deste somador,
otimizado para FPGA, ser mais eficiente, pois possui uma cadeia de propagação do carry
eficiente que faz com que o atraso da arquitetura com este somador seja menor do que as outras
alternativas. Entretanto, em relação às arquiteturas que não utilizam o somador Macro Function,
a arquitetura que apresentou o melhor resultado de atraso foi aquela com compressor 4:2 e
subtrator Carry Save. Isto mostra a eficiência do subtrator Carry Save que propaga o carry na
diagonal. Dentre as arquiteturas apenas com compressores a arquitetura com o pior atraso foi a
que utiliza compressor 16:2, como mostra a Tabela 6.2. Isto se explica pelo fato deste compressor
possuir compressores 8:2 e 4:2 no seu caminho crítico.
6.1.2.2 Implementações de Arquiteturas Seriais em FPGA
Esta seção apresenta as implementações das arquiteturas seriais com o uso dos
compressores. São apresentadas duas alternativas arquiteturais, sendo estas: serial com
separabilidade e serial sem separabilidade.
6.1.2.2.1 Arquitetura Serial com Separabilidade
Esta arquitetura apresenta a propriedade de separabilidade, isto é, a transformada
Hadamard 4x4 2-D é dividida em duas etapas de uma dimensão (1-D), onde o resultado da
78
primeira é transposto e a segunda transformada é então aplicada. Os valores de entradas são
entregues serialmente, ou seja, uma amostra a cada ciclo de relógio. A Figura 6.10 mostra a
arquitetura proposta com o uso do compressor 4:2.
Figura 6.10: Arquitetura Serial com separabilidade Utilizando o Compressor 4:2
Com o uso dos compressores 4:2, a arquitetura da transformada Hadamard 1-D opera em
4 ciclos de relógio para a finalização de seus cálculos, enquanto que na arquitetura original esta
operação levava 8 ciclos de relógio. Isto ocorre devido ao fato do compressor 4:2 realizar o
cálculo de quatro valores de soma simultaneamente para a sua entrada de dados.
Para a operação de subtração foram conectados, circuitos que realizam o complemento
de dois, em cada saída dos buffers ping-pong, como mostram os pequenos retângulos entre o
buffer ping-pong e os multiplexadores da Figura 6.10. Também são utilizados circuitos
multiplexadores conectados nas entradas do compressor, os quais são responsáveis por fazer a
seleção entre o valor original ou complementado. O processo realizado pelo buffer de
transposição é formado por duas memórias de 16 posições com 16 bits. Estas memórias
funcionam de maneira intercalada, isto é, quando os resultados da primeira Hadamard estão
sendo escritos no buffer 1, o buffer 2 está mandando os resultados para a segunda Hadamard 1-D.
Logo que se encerre o processo de escrita nas 16 posições, o processo é invertido, fazendo com
que o buffer 1 (com os resultados da primeira Hadamard 1-D) dê início à entrega dos valores para
o buffer 2. A Tabela 6.4 apresenta os valores de comparação dos diferentes módulos que
compõem a arquitetura serial com separabilidade.
Primeiramente, foram obtidos resultados para a Transformada 1-D. Com estes valores
conclui-se que a arquitetura implementada apresenta uma maior freqüência de operação para a
primeira e segunda Hadamard comparada com a arquitetura de (AGOSTINI, 2007), como mostra
a Tabela 6.3. Isso ocorre devido a realização dos cálculos da Hadamard 1-D serem realizados em
79
quatro ciclos de relógio. Além disso, a arquitetura proposta utiliza somente um buffer e um
compressor para realizar o cálculo da transformada Hadamard 1-D, enquanto que na arquitetura
original são necessários dois buffers e dois somadores. Esta diminuição de requisitos de
hardware por parte da arquitetura implementada tem conseqüências na redução de área e também
do caminho crítico da arquitetura proposta.
Arquiteturas
1ª Had 1-D
(Implementada)
1ª Had 1-D
(AGOSTINI, 2007)
Buffer de
Transposição
2ª Had 1-D
(Implementada)
2ª Had 1-D
(AGOSTINI, 2007)
Tabela 6.3: Resultado de Síntese para Transformadas 1-D
Elementos
Memória
Frequência
Lógicos (LUTs)
(bits)
(MHz)
Latência
(ciclos)
206
0
357,78
4
232
0
253,04
8
37
512
319,18
16
234
0
341,53
4
262
0
203,92
8
Embora a arquitetura implementada para a primeira e para segunda Hadamard tenha
apresentado melhores resultados de freqüência de operação, este mesmo fato não ocorre quando
da implementação da arquitetura da Transformada Hadamard 4x4 em duas dimensões (2-D).
Observa-se neste caso, que a arquitetura original apresenta os melhores resultados em termo de
freqüência de operação, como pode ser observado na Tabela 6.4. Isto pode ter ocorrido devido ao
melhor mapeamento interno do componente FPGA para esta arquitetura ao conectar-se os
módulos da transformada. Entretanto, deve-se observar que a arquitetura implementada apresenta
a menor utilização de recursos de hardware em relação à arquitetura original. Outro aspecto
importante a ser destacado é a menor quantidade de ciclos de relógio utilizada pela arquitetura
implementada, devido ao fato de utilizar compressores 4:2 que realizam a soma simultânea de 4
operandos.
Tabela 6.4: Resultado de Síntese da Arquitetura Serial com Separabilidade
Elementos
Frequência
Latência
Arquitetura
Memória
Lógicos (LUTs)
(MHz)
(ciclos)
Implementada
456
512
97,26
24
(AGOSTINI,
514
512
183,04
32
2007)
80
6.1.2.2.2 Arquitetura Serial sem Separabilidade
Outra arquitetura dedicada implementada para a Transformada Hadamard 4x4 Direta foi
a arquitetura serial sem separabilidade. A motivação para o estudo desta arquitetura deve-se ao
fato da solução da arquitetura original de (AGOSTINI, 2007) apresentar uma latência elevada.
Neste caso, o uso de compressores pode reduzir de forma significativa o número de ciclos de
relógio.
Para esta arquitetura, torna-se interessante a utilização do compressor 16:2, visto que o
uso deste tipo de compressor pode acelerar as operações de soma e subtração, considerando que a
estrutura deste possibilita a soma simultânea de dezesseis números. A utilização deste compressor
reduz a arquitetura para um compressor 16:2, dezesseis multiplexadores e complementadores, um
buffer ping-pong e deslocador à direita, como mostra a Figura 6.11.
Figura 6.11: Arquitetura Serial sem Separabilidade Utilizando o Compressor 16:2
Os valores para a entrada desta arquitetura também são entregues serialmente, isto é, a
cada ciclo de relógio, o (buffer ping-pong) de dezesseis posições, recebe uma nova amostra.
81
Nesta arquitetura são utilizados os circuitos que realizam o complemento de dois, assim também
como multiplexadores para a seleção das entradas complementadas. A arquitetura é constituída
de um (buffer ping-pong) de 16 posições, representado na Figura 6.11 pelo retângulo numerado
de 0 à 15, armazenando toda a matriz 4x4 de entrada. Assim que as 16 amostras de entrada são
recebidas o (buffer ping-pong) as transfere para as entradas dos circuitos de complemento de dois
e para os multiplexadores.
Essa característica da soma de 16 amostras simultaneamente faz com que sejam
necessários 16 ciclos de relógio para a realização dos cálculos da Transformada Hadamard. Com
isto, esta solução arquitetural possui uma menor latência do que a arquitetura original que opera
em 64 ciclos de relógio, como pode ser observado na Tabela 6.5.
Tabela 6.5: Resultado de Síntese da Arquitetura Serial sem Separabilidade
Frequência
Latência
Arquiteturas
LUTs
(MHz)
(ciclos)
Implementada
1047
288,1
16
(AGOSTINI,
2249
146,11
64
2007)
Como pode ser observado na Tabela 6.5, a arquitetura com compressor 16:2 apresenta
um menor uso de recursos de hardware. Isso acontece devido à redução do número de (buffers
ping-pong) e de somadores. Esta redução também propicia a redução do caminho crítico do
circuito, fazendo com que a arquitetura com compressor 16:2 apresente uma maior freqüência de
operação. Esta maior freqüência aliada a um menor número de ciclos de relógio confere a esta
arquitetura um grande desempenho, quando comparada com a arquitetura original.
Portanto, esta seção apresentou as alternativas arquiteturais para a Transformada
Hadamard Direta 4x4. Foram abordadas sete implementações, sendo estas voltadas para
arquiteturas seriais: uma serial com separabilidade e uma serial sem separabilidade e quatro
arquiteturas combinacionais. Foram obtidos resultados de área, freqüência de operação e atraso
para as arquiteturas descritas, com a síntese sendo realizada com a ferramenta (Quartus II) da
Altera. A partir deste estudo, o trabalho atingiu o seu objetivo inicial de verificar o
comportamento das arquiteturas dedicadas da Transformada Hadamard, quando do uso de
circuitos somadores compressores 4:2, 8:2 e 16:2. Este estudo serviu como embasamento para as
futuras implementações de arquiteturas voltadas para ASIC.
82
6.1.2.3 Implementações em ASIC para a Transformada Hadamard 4x4
Nesta seção são descritas as três versões arquiteturais implementadas para a
transformada Hadamard 4x4. Para as implementações ASIC, foram apenas implementadas
arquiteturas combinacionais. Os compressores 4:2, 8:2 e 16:2 que foram utilizados neste estudo,
incluem uma barreira de pipelines internamente entre a linha de compressores e a linha de
somadores para a recombinação dos resultados parciais de soma e carry. Os somadores utilizados
na estrutura interna dos compressores (somadores usados na linha de recombinação dos
resultados parciais de soma e carry) foram implementados com o operador “+” da biblioteca
Standard cells da ferramenta Leonardo Spectrum. Portanto, como o projeto é otimizado para
desempenho, a ferramenta utiliza o somador Carry Look Ahead. Além disso, as entradas da
transformada Hadamard 4x4 têm uma largura de 14 bits e suas saídas com 17 bits.
No caso das implementações utilizando o compressor 4:2 foi inserida uma coluna de
registradores entre as colunas de compressores. Assim, esta arquitetura foi desenvolvida com um
pipeline de um estágio como mostra a Figura 6.12.
Figura 6.12: Arquitetura para a Hadamard 4x4 implementada na Tecnologia ASIC
Na arquitetura com compressor 8:2 também foi inserida uma barreira de registradores
entre a coluna de compressores 8:2 e a coluna de somadores para realizar a implementação em
pipeline. Neste caso, também foi utilizado o operador “+” (tanto internamente nos compressores
83
como nos somadores externos). Estes somadores são implementado com o Carry Look Ahead,
como dito anteriormente. A Figura 6.13 mostra a arquitetura para esta versão arquitetural.
Figura 6.13: Arquitetura para a Hadamard 4x4 implementada na Tecnologia ASIC
A arquitetura utilizando o compressor 16:2 não sofreu alteração comparada a
implementação direcionada para FPGA já mostrada na Figura 6.9.
6.1.2.4 Resultados de Síntese
Todas as arquiteturas foram descritas em linguagem de descrição de hardware – VHDL.
Para a síntese das arquiteturas foi utilizada a ferramenta Leonardo Spectrum para a tecnologia
standard cell TSMC 0.18um. A Tabela 6.6 apresenta os resultados de síntese para a arquitetura
proposta por (AGOSTINI, 2007) da transformada Hadamard 4x4 e também para as soluções
desenvolvidas com o compressor 4:2, compressor 8:2 e compressor 16:2. A latência, área (em
84
termos de números de portas lógicas), frequência de operação, são apresentados para a arquitetura
original e para as três novas arquiteturas propostas. Estas três novas arquiteturas para a
transformada Hadamard 4x4 são: com compressor 4:2 (CA 4-2), com compressor 8:2 (CA 8-2) e
com compressor 16:2 (CA 16-2).
Como observado na Tabela 6.6, as três novas arquiteturas implementadas para a
transformada Hadamard 4x4 apresentaram maior uso de área que a arquitetura original proposta
em (AGOSTINI, 2007). Isto mostra que os compressores não são a melhor escolha quando o
projeto está direcionado para utilizar poucos recursos de área. Contudo, este trabalho é focado em
desempenho e neste requisito a arquitetura CA 8-2 obteve melhores resultados em termos de
frequência de operação e latência, quando comparada com a arquitetura original e a arquitetura
com compressor 4-2. Este resultado se deve ao fato desta arquitetura utilizar apenas uma coluna
de compressores 8:2, enquanto que a arquitetura CA 4-2 utilizar duas colunas de compressores e
A arquitetura CA 16-2 apresentou uma frequência de operação menor que a arquitetura original.
Isto devido ao fato do compressor 16:2 utilizado na arquitetura CA 16-2 apresentar um caminho
critico maior que o compressor 8:2. Porém, esta implementação (CA 16-2) obteve um dado
relevante: a latência de 1 ciclo de relógio. Esta baixa latência deve-se ao fato de o compressor
16:2 que é utilizado nesta implementação realizar a soma dos 16 operandos de entrada, que são
necessários para gerar um resultado final, de uma só vez.
Tabela 6.6: Resultados da Transformada Hadamard 4x4
Área
Frequência Throughput
Arquitetura
Latência
(# de gates)
(MHz)
(Amostras/s)
(AGOSTINI, 2007)
9991
4
384,61
6.15G
CA 4-2
17084
4
278,55
4.45G
*CA 8-2
19769
2
390,62
6.24G
CA 16-2
30030
1
353,35
5.65G
6.1.3 Arquitetura para Transformada Hadamard 2x2
Como pôde ser visto na Equação 4.4, a matriz de entrada com os elementos DC que
determina o cálculo da transformada Hadamard 2x2 é composta somente por quatro operandos.
Assim, para obter o resultado final de cálculo desta transformada é necessário implementar
somente adições e algumas subtrações, utilizando-se no máximo quatro operandos. Tendo em
vista esta característica da transformada Hadamard 2x2, implementou-se somente uma alternativa
arquitetural, mostrada na Figura 6.14, utilizando o somador compressor 4:2. Para esta
85
transformada a utilização dos compressores que adicionam mais de quatro operandos como o
compressor 8:2 e o compressor 16:2, não faz sentido.
Esta arquitetura é bastante simples, além do compressor 4:2 a arquitetura possui
módulos de complemento de dois utilizados quando se faz necessário a realização de subtrações.
As entradas são de 14 bits e a saída é representada em 16 bits.
Figura 6.14: Arquitetura para a Transformada Hadamard 2x2
6.1.3.1 - Resultados de Síntese
As duas arquiteturas foram descritas em linguagem de descrição de hardware – VHDL.
Para a síntese das arquiteturas foi utilizada a ferramenta Leonardo Spectrum para a tecnologia
standard cell TSMC 0.18um. A Tabela 6.7 apresenta os resultados de síntese para a arquitetura
original da transformada Hadamard 2x2 (AGOSTINI, 2007) e também para a nova solução
desenvolvida com o uso do compressor 4:2 (CA 4-2). A latência, área (em números de portas
lógicas), frequência de operação, são apresentados para a arquitetura original e para a nova
arquitetura proposta. A arquitetura CA 4-2 proposta apresentou maior uso de recursos de
hardware do que a arquitetura original. Por outro lado, a nova arquitetura desenvolvida
apresentou maior frequência de operação, 467,29 MHz, contra 431,03 MHz obtida pela
arquitetura proposta em (AGOSTINI, 2007). Além disso, a latência da nova arquitetura é de
somente 1 ciclo de relógio e este resultado, juntamente com a maior frequência de operação,
fazem desta arquitetura uma eficiente alternativa para a transformada Hadamard 2x2 (com maior
throughput, como pode ser visto na Tabela 6.7.
86
Tabela 6.7: Resultados de Síntese da Transformada Hadamard 2x2
Frequência
Área
Latência
(MHz)
(# de gates)
AGOSTINI, 2007
1170
2
431,03
*CA 4-2
1984
1
467,29
Arquitetura
Throughput
(amostras/s)
1.72G
1.87G
6.1.4 Validação do Módulo T Completo
As arquiteturas desenvolvidas foram descritas em VHDL e sintetizadas para a tecnologia
standard cell TSMC 0.18um. A síntese foi gerada usando a ferramenta Leonardo Spectrum. A
Tabela 6.8 mostra os resultados de síntese para as arquiteturas das transformadas propostas e para
a implementação completa do módulo T. Estes resultados são apresentados em termos de número
de gates usadas, frequência máxima, latência com pipeline e throughput.
Tabela 6.8: Resultados para o Módulo T Completo
2x2 FHAD
Área Frequência Latência Throughput
(gates)
(MHz)
(ciclos) (amostras/s)
17027
432.9
1
6.92 G
1984
467.2
1
1.86 G
4x4 FHAD
20710
390.6
2
6.24 G
Modulo T
43107
390.6
-
6.24 G
Arquitetura
4x4 FDCT
A frequência de operação do módulo será a mesma da transformada Hadamard 4x4,
pois, esta transformada possui o maior caminho critico entre as transformadas que compõe o
módulo T. O custo de área do módulo T é igual à soma das gates das três transformas mais os
dois buffer (de luminância e crominância, conforme a Figura 4.1). Para atingir esta alta
frequência foi necessário o uso de pipeline em pontos estratégicos para reduzir o caminho critico.
A arquitetura proposta neste trabalho opera em modo intra 16x16 e pode processar um
macrobloco em 27 ciclos de relógio e com a frequência máxima de operação, a arquitetura
proposta pode processar 2782 HD1080p (1920x1080 pixels) quadros por segundo. Para alcançar
real time (30 quadros por segundo) a arquitetura necessita de somente 0.24 MHz.
6.1.5 Comparação com Resultados da Literatura
Até o momento, várias arquiteturas VLSI para as transformadas do módulo T foram
apresentadas, mas existem poucos trabalhos com o modulo T completo para o padrão
87
H.264/AVC.
Assim como este trabalho de TFG, em (PORTO, 2007), apresenta-se uma
implementação completamente paralela para o modulo T direcionada para FPGA, usando
operadores aritméticos da biblioteca Xilinx. Esta arquitetura pode alcançar 303.63 MHz com uma
latência de macrobloco de 31 ciclos de relógio. Outras arquiteturas multi-transformadas foram
propostas na literatura atual. Em (AGOSTINI, 2006), a arquitetura multi-transformada processa
todas as transformadas do modulo T e também está apta a selecionar o nível de paralelismo
desejado. No trabalho (WANG, 2003) é proposta uma arquitetura que pode processar todas as
transformadas 4x4 do módulo T (FDCT e Hadamard) com uso de recursos de hardware de 6538
gates e thoughput de 320M amostras/s operando numa frequência de 80 MHz. A arquitetura
proposta em (KUAN, 2006) é composta por uma multi-transformada sem memória transposta e
pode alcançar 1.6G amostras/s com uma frequência de 200MHz. Outra multi-transformada
proposta em (WEI, 2008) opera a 200 MHz processando 16 amostras por ciclo. A arquitetura
proposta em (PORTO, 2007) foi sintetizada em FPGA. Para realizar uma comparação justa com
o trabalho de (PORTO, 2007), reproduzimos esta arquitetura em versão ASIC usando operados
aritméticos da biblioteca utilizada, chamada Rp.
Como mostra a Tabela 6.9 nossa arquitetura foi comparada com trabalhos relacionados
da literatura atual. A solução (PORTO, 2007) é uma arquitetura dedicada ao modulo T. Outras
comparações são com arquiteturas multi-transformadas. Desta forma, os resultados de latência de
macrobloco foram estipulados do mesmo modo que feito neste trabalho. Nossa arquitetura
alcançou alta frequência de operação comparada com (AGOSTINI, 2006), (WANG, 2003),
(KUAN, 2006) e (WEI, 2008), e portanto, um maior throughput. Comparado com a solução de
(PORTO, 2007), nossa arquitetura alcançou a mesma frequência de operação, mas pode processar
um macrobloco com menor quantidade de ciclos de relógio (27 contra 31). A utilização de
somadores compressores para encontrar o máximo de paralelismo acarreta em maior custo de
área, ou seja, realizar maior número de somas simultâneas implica em maior custo de recursos de
área na nossa arquitetura.
88
Tabela 6.9: Resultados Comparativos com Trabalhos Relacionados
ARQUITETURAS
(PORTO,
(AGOSTINI,
(WANG,
(KUAN,
(WEI,
2007)
2006)
2003)
2006)
2008)
Processo
(µm)
Área
(gates)
Frequência
(MHz)
Throughput
(amostras/s)
Latência do
MB (ciclos)
Proposta
0.18
0.35
0.35
0.18
0.18
0.18
20310
18353
6538
6482
11038
43107
390.6
218.7
80
100
200
390.6
6.24G
3.5G
320M
800M
3.2G
6.24G
31
100
100
-
27
27
Um alto throughput e baixa latência são importantes requisitos para o desempenho geral
do codificador do H.264/AVC. Isto porque o módulo de predição usa o bloco intra atual para
gerar o próximo bloco intra predito, mas o bloco atual deve ser processado pelo módulo T e pela
quantização para ser usado no módulo de predição (AGOSTINI, 2007). Baseado nestes requisitos
a arquitetura proposta neste trabalho possui alto desempenho, quando comparada com trabalhos
relacionados da literatura.
6.2 Soluções Arquiteturais: Estimação de Movimento (ME)
As arquiteturas desenvolvidas nesta parte do trabalho são baseadas em (PORTO, 2008).
Esta arquitetura é mostrada na Figura 6.15. A arquitetura possui um módulo de memória, que
reúne um conjunto de memórias internas para armazenar os blocos que são candidatos a bloco de
referência e o bloco do quadro atual que é bloco para o qual a estimação está sendo realizada. São
utilizadas nove unidades de processamento (UP), onde cada UP é responsável por calcular o SAD
para um bloco candidato. A Figura 6.15 também apresenta o módulo de controle e o comparador.
O comparador recebe o resultado de SAD calculado pelas nove UPs e encontra o menor
resultado.
Cada UP processa oito amostras em paralelo. Isso significa que uma linha inteira do
bloco de 16x16 sub-amostrado (o bloco sub-amostrado possui 16 linhas de oito amostras) é
processada em paralelo. A Figura 6.16 lustra a arquitetura de uma UP de oito amostras. Este
bloco consiste em uma árvore de somadores em pipeline. Primeiramente, as oito amostras do
89
bloco atual e do bloco candidato são subtraídas. Após, o módulo da diferença entre as amostras é
somado e o resultado final da acumulação das diferenças, para todas as amostras da linha, é
armazenado no registrador de saída.
A UP tem uma latência de quatro ciclos de relógio e, com o pipeline completo, ela pode
calcular uma linha de bloco candidato a cada ciclo de relógio. Um conjunto somador/acumulador
é utilizado nas saídas das UPs para armazenar os resultados intermediários de cada bloco
candidato. Ao todo, 16 acumulações são necessárias para gerar o resultado final do SAD para um
bloco candidato, sendo uma acumulação para cada linha do bloco. As UPs recebem os dados das
memórias de bloco candidato (CBM) e da memória do bloco atual (CB). Cada UP recebe uma
palavra da CBM e uma palavra da CB e calcula a diferença entre as oito amostras presentes em
cada uma destas palavras.
Figura 6.15: Arquitetura para ME proposta em (PORTO, 2008)
90
B0
abs
R0
B1
abs
R1
B2
abs
R2
B3
abs
R3
B4
abs
R4
B5
abs
R5
B6
abs
R6
B7
abs
R7
Figura 6.16: Arquitetura da Unidade de Processamento (UP)
6.2.1 Otimização proposta neste trabalho
Neste trabalho foram proposta duas novas arquiteturas para a ME, onde a principal
inovação encontra-se localizada nas noves UPs existentes na arquitetura original. A UP
desenvolvida em (PORTO, 2008) utiliza uma árvore de somadores com um pipeline de quatro
estágios. Cada UP pode processar oito amostras em paralelo e isto permite que uma linha de
16x16 do bloco sub-amostrado seja processada em paralelo. Então, oito acumulações podem ser
usadas para gerar o resultado final do SAD de cada bloco, sendo uma acumulação por linha.
Igualmente a arquitetura original apresentada anteriormente, a solução proposta também
processa oito amostrars em paralelo. A principal diferença entre estas arquiteturas para UPs é o
tipo de somadores utilizados. A arquitetura proposta usa somadores compressores eficientes para
calcular as adições da UP. A Figura 6.17(a) mostra a arquitetura para a UP com compressor 4:2.
Dois compressores 4:2 são usados para realizar a soma de oito operandos que estão
disponibilizados na saída da primeira coluna de registradores. Os valores calculados pelos
compressores 4:2 representam os módulos da diferença de cada par de operandos de entrada. O
resultado final da UP é calculado pela soma dos resultados produzidos pelas saídas de cada
compressor 4:2. Portanto, o fato de quatro somas simultâneas serem realizadas pelo compressor
4:2, permite a eliminação de uma coluna de somadores, como pode ser comparado nas Figuras
91
6.14 e 6.17(a). Assim, a solução arquitetural proposta permite a redução de um ciclo de relógio
quando comparada à solução original.
Com a intenção de aumentar o desempenho da UP, foi proposto uma solução arquitetural
com o uso dos compressores 8:2, como pode ser visto na Figura 6.17(b). Nesta arquitetura, oito
amostras podem ser processadas simultaneamente pelo compressor 8:2, e isto, comparado com a
solução original, permite a eliminação de duas colunas da árvore de somadores. Assim, a UP com
compressor 8:2 reduz o cálculo em dois ciclos de relógio. Como pode ser visto na Figura 6.17(b)
após a primeira coluna de registradores, somente um compressor 8:2 é necessário para calcular o
resultado final.
Figura 6.17 Estrutura da UP da ME (a) com Compressor 4:2; (b) com Compressor 8:2
6.2.2 Avaliação dos Resultados
A arquitetura original e as duas arquiteturas propostas (usando compressor 4:2 e
compressor 8:2) utilizam 26 ciclos de relógio para preencher toda a memória e iniciar o cálculo
do SAD. A arquitetura original das UPs tem uma latência de quatro ciclos, enquanto que as
arquiteturas com o compressor 4:2 e com o compressor 8:2 têm uma latência de três e dois ciclos
92
respectivamente. Todas as versões necessitam de sete ciclos a mais para calcular o SAD de um
bloco.
O comparador usa cinco ciclos para escolher o menor SAD. Assim, 42 ciclos de relógio
são necessários para processar o primeiro LDSP na arquitetura original. O SDSP necessita de 20
ciclos para calcular o SAD para quatro blocos candidatos de SDSP. Então, no melhor caso, a
arquitetura original pode gerar um vetor de movimento em 62 ciclos.
A arquitetura desenvolvida com UPs utilizando o compressor 4:2 usa 41 ciclos de
relógio para processar a primeira LDSP, e 19 ciclos para calcular o SDSP. Assim, no melhor
caso, esta arquitetura pode gerar um vetor de movimento em 60 ciclos de relógio. A segunda
arquitetura, usando o compressor 8:2 nas UPs, utiliza somente 40 ciclos de relógio para calcular o
primeiro LDSP e 18 ciclos para processar a SDSP. Então, no melhor caso, esta arquitetura usa 58
ciclos de relógio para gerar um vetor de movimento.
O algoritmo da arquitetura original utiliza em média três interações para encontrar o
melhor caso. Dez ciclos de relógio são necessários para a latência da memória. A UP original usa
mais 11 ciclos, enquanto que a UP com compressor 4:2 utiliza 10 ciclos e a UP com compressor
8:2 usa 9 ciclos de relógio. Então, cada interação na arquitetura original da ME utiliza 26 ciclos
de relógio, enquanto as soluções com o compressor 4:2 e 8:2, utilizam 25 e 24 ciclos,
respectivamente.
Todas as alternativas foram implementadas utilizando o controle dinâmico de iteração
(DIC). Esta inovação foi introduzida para limitar o número máximo de iterações que o algoritmo
pode executar para gerar um vetor de movimento. Nestas arquiteturas, o DIC permite 20 ciclos
para cada geração de vetor de movimento. Este número foi definido através de uma análise em
software realizada em (PORTO, 2008), que concluiu que o algoritmo não utilizava mais do que
14 iterações para gerar um vetor de movimento. Então, considerando o pior caso, a arquitetura
original utiliza um máximo de 582 ciclos para gerar um vetor de movimento. As arquiteturas com
compressor 4:2 e com o compressor 8:2 utilizam 560 e 538 ciclos respectivamente.
6.2.3 Resultados de Síntese
As arquiteturas foram implementadas em linguagem de descrição de hardware – VHDL.
Para a síntese das arquiteturas foi utilizada a ferramenta Leonardo Spectrum para a tecnologia
93
standard cell TSMC 0.18um. A Tabela 6.10 apresenta os resultados de síntese para a arquitetura
original da ME e também para as soluções desenvolvidas com o compressor 4:2 e com o
compressor 8:2. A latência, área (em termos de números de portas lógicas), frequência de
operação e número de quadros por segundo (fps) para HDTV, considerando o pior caso e o caso
médio, são apresentados para a arquitetura original e para as duas novas arquiteturas propostas
(ME com compressor 4:2 e ME com compressor 8:2). O caso médio para o calculo de fps foi
obtido através de implementação em software do algoritmo (PORTO, 2008). O algoritmo utiliza
em média três interações no segundo passo de interação. O número de interações que o algoritmo
realiza no caso médio foi obtido através da implementação em software. Esse número de
interações também foi utilizado para o cálculo de fps nas arquiteturas com os compressores. O
pior caso está definido pelo DIC, e todas as arquiteturas permitem 20 interações para cada
geração de vetor de movimento.
Como observado na Tabela 6.10, a arquitetura da ME com o compressor 4:2 e a
arquitetura com o compressor 8:2 são mais eficientes que a arquitetura original proposta em
(PORTO, 2008). Particularmente, a arquitetura para ME com o compressor 4:2 é a que apresenta
a maior frequência de operação entre as arquiteturas. Isto se deve ao fato do somador compressor
4:2 usado nas UPs da ME possuir um caminho crítico menor que o caminho crítico do somador
compressor 8:2 usado na segunda alternativa para as UPs implementadas. A arquitetura das UPs
com o compressor 4:2 apresenta uma latência de 60 ciclos de relógio. Com isto, esta arquitetura
pode processar 63 quadros por segundo para HDTV 1080p no pior caso.
Este valor foi obtido através do cálculo realizado com o período da arquitetura
multiplicado pelo número de vetores do quadro e pelo número de ciclos gasta para processar um
vetor de movimento. Esse será o tempo total necessário para processar um quadro do vídeo.
Após, basta somente fazer a divisão de 1 segundo pelo valor anteriormente calculado para termos
o número de quadros por segundo que a arquitetura processa.
Por outro lado, quando três interações são necessárias para calcular um vetor de
movimento, a arquitetura pode processar 240 quadros por segundo.
A arquitetura da ME com compressor 8:2 apresenta uma menor freqüência de operação
do que a arquitetura com compressor 4:2. Contudo, a arquitetura com compressor 8:2 apresenta
dois ciclos de relógio a menos (58 contra 60 da arquitetura com compressor 4:2). Esta diferença
de freqüência de operação entre as duas arquiteturas não é significante. Então, a arquitetura para
94
ME com compressor 8:2 alcança os melhores resultados para o processamento de quadros por
segundo HDTV 1080p (65 quadros por segundo no pior caso e 269 quadros por segundo no caso
médio).
Outro importante ponto a ser observado na Tabela 6.10 é o maior número de portas
lógicas apresentado pela arquitetura com compressor 4:2. Foi observado que o uso separado de
dois compressores 4:2 contribuiu para o alto número de portas lógicas apresentada pela
arquitetura que utiliza o compressor 4:2. Contudo, quando utilizado um somador mais complexo,
como o compressor 8:2, a arquitetura utiliza uma única coluna de somadores e perde uma coluna
de registradores. Isto contribui para o menor número de portas lógicas apresentada pela
arquitetura que utiliza o compressor 8:2.
Tabela 6.10: Resultados de Síntese para Arquiteturas da ME
Arquitetura
ME com
ME com
Parâmetros
Original (Porto,
compressor 4:2
compressor 8:2
2008)
Latência UP
11
10
9
(ciclos de clock)
Área
28.087
29.702
28.858
(# de gates)
Frequência
272.6
287.3
283.0
(MHz)
HDTV 1080p fps
58
63
65
(pior caso)
HDTV 1080p fps
240
263
269
(caso médio)
6.2.4 Comparação com Resultados da Literatura
As versões standard cell da arquitetura da ME foram comparadas com outras
implementações publicadas na literatura. A Tabela 6.11 mostra a comparação das arquiteturas
para a ME implementadas neste trabalho com implementações apresentadas em (LI, 2005),
(GAEDKE, 2007) e (HE, 2007).
95
Solução
Tabela 6.11: Resultados Comparativos
Área
Frequência
Processo
(K gates)
(MHz)
HDTV
(FPS)
(LI, 2005)
0.18µm
17.5
200
23
(GAEDKE, 2007)
90nm
1200
334
25
(HE, 2007)
0.25µm
1020
100
46
(PORTO, 2008)
(pior caso)
0.18µm
28.8
272
57
0.18µm
29.7
287
63
0.18µm
28.0
283
65
ME com
compressor 4:2
(pior caso)
ME com
compressor 8:2
(pior caso)
As arquiteturas apresentadas em (GAEDKE, 2007) e (HE, 2007) usam o algorimo Full
Search e foram desenvolvidas para aplicações HDTV. As arquiteturas para a ME desenvolvidas
neste trabalho apresentaram uma significante redução em termos de resulatdos de área quando
comparadas a (GAEDKE, 2007) e (HE, 2007), onde mais de 30 vezes menos área foi utilizado.
Contudo, as arquiteturas desenvolvidas apresentaram um uso de recursos de hardware um pouco
maior que a arquitetura (LI, 2005).
O fato das arquiteturas propostas e também a arquitetura de (PORTO, 2008) serem
baseadas em algoritmos rápidos, e considerar uma pequena área de pesquisa, torna estas
arquiteturas mais eficientes do que as de (LI, 2005), (GAEDKE, 2007) e (HE, 2007). As
arquiteturas deste trabalho apresentaram maior throughput, inclusive quando não alcançou a
maior frequencia de operação entre as soluções standard cells.
As arquiteturas utilizando compressor 4:2 e compressor 8:2 também apresentaram a
melhor relação entre uso de recursos de hardware e throughput entre todos os trabalhos
comparados. Particularmente, a arquitetura para a ME com compressor 8:2 apresentou o melhor
resultado de taxa de processamento, com um incremento muito pequeno na utilização de gates,
em comparação com a arquitetura de (PORTO, 2008)
96
7 CONCLUSÕES E TRABALHOS FUTUROS
Esta dissertação apresentou soluções arquiteturais de alto desempenho para dois
módulos do padrão H.264/AVC: o módulo das transformadas diretas (T) e o módulo de
estimação de movimento. Uma ampla avaliação inicial sobre a viabilidade de inclusão se
somadores eficientes nos módulos do padrão foi desenvolvida, que serviu como base para
escolher os módulos e os somadores que melhor serviam para a realização das implementações
em hardware.
O trabalho apresentado nesta dissertação foi dividido em três grandes etapas: i) estudo
de somadores eficientes, principalmente os somadores compressores 4:2, 8:2 e 16:2, ii) avaliação
dos módulos do padrão H.264/AVC nos quais poderiam ser aplicados estes somadores com
sucesso e iii) desenvolvimento arquitetural.
Na primeira etapa, uma ampla pesquisa foi realizada sobre os principais somadores
eficientes existentes na literatura. Além dos compressores, somadores como Ripple Carry e
Carry Look Ahead também foram utilizados. Com este estudo inicial, foi verificado que os
somadores que melhor atendem aos requisitos de desempenho são os somadores compressores. O
estudo dos compressores começou pelo compressor 4:2, foram feitas simulações para a
comparação com outros somadores que indicaram o melhor desempenho do compressor 4:2 para
a adição simultânea de quatro operandos. A partir destes resultados foi realizado o
desenvolvimento dos compressores 8:2 e 16:2 para serem usados na adição simultânea de 8 e 16
operandos, respectivamente.
Na segunda etapa desta dissertação, foi realizada uma ampla investigação nos módulos
do padrão H.264/AVC para localizar situações de aplicabilidade dos somadores investigados.
Nesta etapa foi identificado que o módulo das transformadas diretas do padrão, por conter as
transformadas FDCT-2D, transformada Hadamard 4x4 e transformada Hadamard 2x2, que
realizam os seus cálculos basicamente utilizando somas e subtrações, seriam um excelente estudo
de caso. Além deste, o módulo de estimação de movimento foi escolhido por ser um módulo que
apresentou o maior número de inovações no padrão e também por ser um módulo com elevada
complexidade computacional e, portanto, a exigência de desempenho ser alta. Neste módulo, a
unidade de processamento (UP) para o cálculo do SAD é composta por uma árvore de
somadores. Desta forma, os somadores compressores foram também empregados neste módulo.
97
Na terceira etapa do trabalho foram desenvolvidas as diversas arquiteturas de hardware
para as transformadas, tanto para ASIC como FPGA, e também para a estimação de movimento.
As primeiras arquiteturas desenvolvidas para a transformada Hadamard 4x4 foram descritas em
VHDL e sintetizadas para FPGA da Altera. Após foram feitas as descrições voltadas para ASIC
das arquiteturas da FDCT-2D, Hadamard 4x4, Hadamard 2x2 e estimação de movimento. Os
resultados de síntese para todas as arquiteturas foram apresentados e mostraram que as
arquiteturas desenvolvidas obtiveram um alto desempenho, quando do uso dos somadores
compressores. Os resultados obtidos na implementação dos módulos da transformada direta e da
estimação de movimento obtiveram resultados muito satisfatórios, inclusive com o
reconhecimento de publicações em importantes eventos da área, como pode ser visto nas
referências bibliográficas.
7.1 Trabalhos Futuros
Esta seção sugere algumas idéias de futuros trabalhos que darão prosseguimento à linha
de pesquisa seguida nesta dissertação de mestrado.
7.1.1 Aplicação dos Somadores Compressores ao Módulo das Transformadas Inversas
Como trabalhos futuros, pretende-se desenvolver com aumento de desempenho outros
módulos do padrão H.264/VAC, como o módulo das transformadas inversas (T-1). Como as
matrizes de cálculo das transformadas inversas são muito próximas às transformadas diretas,
pretende-se aplicar os somadores eficientes também a este módulo.
7.1.2 Verificação do Consumo de Potência dos Módulos das Transformadas
Um dos principais aspectos dos circuitos somadores compressores é a possibilidade de
redução do consumo de potência. Isto pelo fato dos compressores serem compostos por portas
lógicas XOR e circuitos multiplexadores (MUX). Como estes circuitos podem ser desenvolvidos
com transistores de passagem, logo os somadores compressores podem ser bem otimizados
quando desenvolvidos com esta metodologia. Desta forma, pretende-se verificar o impacto no
consumo de potência dos módulos das transformadas direta e inversa, quando do uso dos
somadores compressores.
98
7.1.3 Verificação do Aumento do Paralelismo na Arquitetura da ME para Verificação do
Uso dos Somadores Compressores
Visto que os compressores permitem fazer a soma de muitos operandos simultaneamente
e que as memórias para o armazenamento dos blocos candidato e atual são muito pequenas (9216
bits no total) a questão central seria verificar se não daria para paralelizar ainda mais o hardware
(fazer mais interações por ciclo de relógio) no sentido de verificar qual seria o impacto disto em
desempenho e consumo de potência.
99
REFERÊNCIAS
AGOSTINI, L. V. Desenvolvimento de Arquiteturas de Alto Desempenho Dedicadas à
Compressão de Vídeo Segundo o Padrão H.264/AVC. 2005. Proposta de Tese de Doutorado
— UFRGS, Porto Alegre/Rs.
AGOSTINI L.; ET ALL, “High Throughput Multitransform and Multiparallelism IP for
H.264/AVC Video Compression Standard” IEEE INTERNATIONAL SYMPOSIUM ON
CIRCUITS AND SYSTEMS, KOS ISLAND, 2006.
AGOSTINI, L. V. “Desenvolvimento de Arquiteturas de Alto Desempenho Dedicadas à
Compressão de Vídeo Segundo o Padrão H.264/AVC”. 2007. Tese de Doutorado — UFRGS,
Porto Alegre/RS.
ALTERA. www.altera.com, Acessado em: junho, 2008. [S.l: s.n.], 2008.
ALTERMANN, J.; COSTA, E.; ALMEIDA, S.; SILVA, A. “High Performance Architecture
for the Forward Transforms Module of the H.264/AVC HVideo Compression Standard”.
IN: ISCAS, 2009.
AZEVEDO, A.; ZATT, B.; AGOSTINI, L.; BAMPI, S. ”MoCHA: a Bi-Predictive Motion
Compensation Hardware for H.264/AVC Decoder Targeting HDTV”. [S.L.]: IN: IEEE
International Symposium on Circuits and Systems, 2007. 4P.
CHAO, Y.; WEI, S.; YANG, J.; LIU, B. ”Combined Decoding and Flexible Transform
Designs for Effective H.264/AVC Decoders”. [S.L.]: IN: IEEE International Symposium on
Circuits and Systems, 2007. 4P.
COSTA, E. A. C. DA. “Operadores Aritméticos de Baixo Consumo para Arquiteturas de
Circuitos DSP”. 2002. Tese de Doutorado — UFRGS, Porto Alegre/RS.
DINIZ, C. “Arquitetura de Hardware Dedicada para a Predição Intra-Quadro em
codificadores do Padrão H.264/AVC de Compressão de Vídeo”. Dissertação de Mestrado.
PPGC – UFRGS. 2009.
DTV. www.dtv.org.br, Acesado em: junho, 2008. [S.L.: S.N.], 2008.
GAEDKE, K.; BORSUM, M.; GEORGI, M.; KLUGER, A.; LE GLANIC, J.; BERNARD, P.
“Architecture and VLSI Implementation of a programmable HD Real-Time Motion
Estimator.” IEEE International Symposium on Circuits and Systems, NEW ORLEANS, USA,
2007. PP. 1609-1612.
GONZALES, R.; WOODS, R. “Processamento de Imagens Digitais”. São Paulo: Edgar
Blücher, 2003.
100
HE, W.; MAO, Z. “An Improved Frame-Level Pipelined Architecture for High Resolution
Video Motion Estimation” IEEE International Symposium On Circuits And Systems, NEW
ORLEANS, USA, 2007. PP. 1381-1384
HISHAN, C.; KOMAL, K.; AND MISHRA, A. “Low Power and Less Area Architecture for
Integer Motion Estimation”. International Journal of Electronics, Circuits and Systems, 3:1, pp.
11-17, 2009.
HWANGBO, W.; KIM, J.; KYUNG, C. ”A High-Performance 2-D Inverse Transform
Architecture for the H.264/AVC Decoder”. [S.L.]: IN: IEEE International Symposium on
Circuits and Systems, 2007. 4P.
ISO/IEC. ”Coding of Moving Pictures and Associated Audio for Digital Storage Media up to
About 1.5Mbits/s - Part 2: Video”. [S.L.: S.N.], 1993.
ISO/IEC. ”MPEG-4 Part 2 (01/99): Coding of Audio Visual Objets - part 2: Visual”.[S.L.:
S.N.], 1999.
ITU-T. ”Recommendation H.261 v1(11/90): Video Codec for Audiovisual Services at px64
Kbit/s”. [S.L.: S.N.], 1990.
ITU-T; ISO/IEC. ”ITU-T Recommendation H.262 and ISO/IEC 13818-2(MPEG-2): Generic
Coding of Moving Pictures and Associated Audio Information - Part 2: Video”. [S.L.: S.N.],
1994.
ITU-T. ”Recommendation H.263
Communication”. [S.L.: S.N.], 2000.
(11/2000):
Video
Coding
for
Low
Bit
Rate
ITU-T. ”Recommendation H.264 (05/03): Advanced Video Coding for Generic Audio visual
Services”. [S.L.: S.N.], 2003.
ITU-T. ”Recommendation H.264 (03/05): Advanced Video Coding for Generic Audio visual
Services”. [S.L.: S.N.], 2005.
JIN, G.; JUNG, J.; LEE, H. ”An Efficient Pipelined Architecture for H.264/AVC Intra Frame
Processing”. [S.L.]: IN: IEEE International Symposium on Circuits and Systems, 2007. 4P.
KHAYAM, S. ”The Discrete Cosine Transform (DCT): Theory and Application”.
Department of Electrical & Computer Engineering, Michigan State University, 2003.
KOZIRI, M.; STAMOULIS, G.; KATSVOUNIDIS, I. “A Low-Power VLSI Architecture for
Intra and Inter Prediction”. In: H.264. ISCAS, 2006.
KUAN-HUNG C.; JIUN-IN G.; JINN-SHYAN W. ‘A high-performance direct 2-D
Transform Coding IP Design for MPEG-4AVC/H.264.’ Ieee Transactions on Circuits and
Systems for Video Technology, VOLUME 16, ISSUE 4, APRIL 2006 PP. 472-483.
101
KUHN, P. M. “Algorithms, Complexity Analysis and VLSI Architectures for MPEG-4
Motion Estimation.” SPRINGER, JUNE 1999.
KUO, C-CHUNG; LEI, S-FANG. “Design of a Low Power Architecture for CABAC
Encoder.” In: H.264. ISCAS 2006.
LI, T.; LI, S.; SHEN, C. “A Novel Configurable Motion Estimation Architecture for HighEfficiency MPEG-4/H.264 Encoding” IEEE Asia and South Pacific Design Aut. Conf.,
Shanghai, CHINA, 2005, PP 1264-1267.
LIN, H-YAO; LU, Y-HONG; LIU, B-DA; YANG, J-FERR. “Low Power Design of H.264
CAVLC Decoder”. ISCAS 2006.
LOPEZ, S.; CALLICO, G.; TOBAJAS, F.; LOPEZ, J. AND SARMIENTO, R. “A Flexible
Template for H.264/AVC Block Matching Motion Estimation Architectures.” IEEE
Transactions on Consumer Electronics, vol. 54, pp. 845-851, May 2008.
MIANO, J. Compressed Image File Formats: JPEG, PNG, GIF, XBM, BMP. NEW YORK
ASSISON-WESLEY, 1999.
OKLOBDZIJA, V.; VILLEGER, D.; LIU, S. A Method for Speed Optimized Partial Product
Reduction and Generation of Fast Parallel Multipliers and Alghorimic Approach. [S.L.]:
IEEE Transaction on Computers, VOL.45, N◦ 3, 1996.
PARHAMI, B. Computer Arithmetic: Algorithmis and Hardware Designs. [S.L.]: OXFORD
UNIVERSITY PRESS, 1999.
PARLAK, M.; HAMZAOGLU, I. A Low Power Implementation of H.264 Adaptive
Deblocking Filter Algorithm. Second IEEE NASA/ESA Conference on Adaptive Hardware
and Systems (AHS 2007). 2007.
PORTO, R.; PORTO, M.; BAMPI, S.; AGOSTINI, L “High Throughput Architecture for
Forward Transform Module of H.264/AVC Video Coding Standard” IEEE International
Conference on Electronics, Circuits and Systems, 2007. ICECS 2007.
PORTO, M.; BAMPI, S.; SUSIN, A.; AGOSTINI, L. “Architectural Design for the New QSDS
with Dynamic Iteration Control Motion Estimation Algorithm Targeting HDTV.” In:
SBCCI 2008, Gramado, Brasil.
PORTO, M.; SILVA, A. M. C. DA.; ALMEIDA, S. J. M. DE; COSTA, E. A. C. DA. “Motion
Estimation Architecture Using Efficient Adder-Compressors for HDTV Video Coding” In:
Journal of Integrated Circuits and Systems, 2010.
PRASAD, K.; PARHI, K. LOW “Power 4-2 and 5-2 Compressors.” [S.L.]: Proceedings of the
35th Asilomar Conference on Signals, Systems and Computers, VOL. I, 2001. 5P.
102
PURI, A.; CHEN, X.; LUTHRA, A. “Video Coding Using the H.264/MPEG-4 AVC
Compression Standard.” [S.L.]: ELSEVIER B. V., 2004. 57P.
RICHARDSON, I. VIDEO CODING DESIGN – “Developing Image and Video Compression
Systems.” CHICHESTER: JOHN WILEY AND SONS, 2002.
RICHARDSON, I. “H.264 and MPEG-4 Video Compression - Video Coding for Next
Genration Multimedia.” CHICHESTER: JOHN WILEY AND SONS, 2003.
ROSA, V. “Projeto de Arquiteturas de Hardware para a Compressão de Vídeo no Padrão
H.264/AVC.” Proposta De Tese De Doutorado, UFRGS, 2009 – Porto Alegre/Rs, Brasil.
SHI, Y.; SUN, H. “Image and Video Compression for Multimedia Engineering:
Fundamentals, Algorithms and Standards.” BOCA RATON: CRC PRESS, 1999.
SILVA, A. M. C. DA. “Desenvolvimento de um Compensador de Movimento para o Padrão
H.264 de Compressão de Vídeo”. 2006. Monografia de Graduação — UFPEL, Pelotas/RS.
SILVA, A. M. C. DA.; ALMEIDA, S. J. M. DE; COSTA, E. A. C. DA.; BAMPI, S.
“Architectural Exploration of Forward 4x4 Hadamard Transform Directed to H.264/AVC
Video Compression Standard.” In: VLSI-SOC, 2009a, Florianópolis, Brasil
SILVA, A. M. C. DA.; PORTO, M.; ALMEIDA, S. J. M. DE; COSTA, E. A. C. DA. “High
Performance Motion Estimation Architecture Using Efficient Adder-Compressors.” In:
SBCCI, 2009b, Natal, Brasil.
SULLIVAN, G.; WIEGAND, T. “Video Compression - From Concepts to the H.264/AVC
Standard.” [S.L.]: Proceedings of the IEEE, 2005. 13P.
UDYAWAR, K.; RAMACHANDRAN, A.; SHANDILYA, S. “Motion Estimation and Mode
Decision for Low Power” H.264. ISCAS, 2006.
WANG, T.; et al., ‘‘Parallel 4x4 2D transform and inverse transform architecture for
MPEG-4 AVC/H.264,’’ in Proceedings of IEEE International Symposium on Circuits and
Systems, May 2003, pp. 800—803.
WEI, C.; HOU HUI, LAI JINMEI, TONG JIARONG, MIN HAO, “A High-Performance
Reconfigurable 2-D Transform Architecture for H.264” IEEE INTERNATIONAL
CONFERENCE ON ELECTRONICS, CIRCUITS AND SYSTEMS, 2008. ICECS 2008.
WEINBERGER, A. “4-2 Carry-Save Adder Module”. [S.L.]: IBM Technical Disclosure
Bulletin, 1981.
103
WIEGAND, T.; SULLIVAN, G.; BJONTEGAARD, G.; LUTHRA, A. “Overview of the
H.264/AVC Video Coding Standard.” [S.L.]: IEEE Transactions on Circuits and Systems for
Video Technology, 2003. 19P.
104
ANEXOS
105
ARTIGOS PUBLICADOS
Architectural Exploration of Forward 4x4 Hadamard Transform Directed to H.264/AVC
Video Compression Standard. André Marcelo C. Silva, Sérgio J. M. de Almeida, Eduardo A.
C. da Costa. In: VLSI-SOC, 2009, Florianópolis, Brasil
High Performance Motion Estimation Architecture Using Efficient Adder-Compressors.
André Marcelo C. Silva, Sérgio J. M. de Almeida, Eduardo A. C. da Costa, Sérgio Bampi. In:
SBCCI, 2009, Natal, Brasil. (Este paper foi convidado a ser publicado no Journal of Integrated
Circuits and Systems, JICS)
Parallel-Prefix Adders Applied to Adder Compressors. João S. Altermann, André Marcelo C.
Silva, Sérgio J. M. de Almeida, Eduardo A. C. da Costa. In: IBERCHIP, 2009 – Buenos Aires,
Argentina.
SUBMETIDO - High Performance Architecture for the Forward Transforms Module of the
H.264/AVC HVideo Compression Standard. João S. Altermann, Sérgio J. M. de Almeida,
Eduardo A. C. da Costa, André Marcelo C. Silva. In: ISCAS 2010, Paris, França
106