A Floating-point Extended Kalman Filter Implementation for Autonomous Mobile Robots

Localization and Mapping are two of the most important capabilities for autonomous mobile robots and have been receiving considerable attention from the scientific computing community over the last 10 years. One of the most efficient methods to address these problems is based on the use of the Extended Kalman Filter (EKF). The EKF simultaneously estimates a model of the environment (map) and the position of the robot based on odometric and exteroceptive sensor information. As this algorithm demands a considerable amount of computation, it is usually executed on high end PCs coupled to the robot. In this work we present an FPGA-based architecture for the EKF algorithm that is capable of processing two-dimensional maps containing up to 1.8 k features at real time (14 Hz), a three-fold improvement over a Pentium M 1.6 GHz, and a 13-fold improvement over an ARM920T 200 MHz. The proposed architecture also consumes only 1.3% of the Pentium and 12.3% of the ARM energy per feature.

A Parallel Hardware Architecture for Scale and Rotation Invariant Feature Detection

This paper proposes a parallel hardware architecture for image feature detection based on the Scale Invariant Feature Transform algorithm and applied to the Simultaneous Localization And Mapping problem. The work also proposes specific hardware optimizations considered fundamental to embed such a robotic control system on-a-chip. The proposed architecture is completely stand-alone; it reads the input data directly from a CMOS image sensor and provides the results via a field-programmable gate array coupled to an embedded processor. The results may either be used directly in an on-chip application or accessed through an Ethernet connection. The system is able to detect features up to 30 frames per second (320 x 240 pixels) and has accuracy similar to a PC-based implementation. The achieved system performance is at least one order of magnitude better than a PC-based solution, a result achieved by investigating the impact of several hardware-orientated optimizations oil performance, area and accuracy.

Implementação de um sistema de síntese de alto nível baseado em modelos java

Este trabalho apresenta uma metodologia para a geração automática de ASICs, em VHDL, a partir da linguagem de entrada Java. Como linguagem de especificação adotou-se a Linguagem Java por esta possuir características desejáveis para especificação a nível de sistema, como: orientação a objetos, portabilidade e segurança. O sistema é especificamente projetado para suportar síntese de ASICs a partir dos modelos de computação Máquina de Estados Finita e Pipeline. Neste trabalho, adotou-se estes modelos de computação por serem mais usados em sistemas embarcados As principais características exploradas são a disponibilização da geração de ASICs para a ferramenta SASHIMI, o alto nível de abstração com que o projetista pode contar em seu projeto, as otimizações de escalonamento realizadas automaticamente, e o sistema ser capaz de abstrair diferentes modelos de computação para uma descrição em VHDL. Portanto, o ambiente permite a redução do tempo de projeto e, consequentemente, dos custos agregados, diminuindo a probabilidade de erros na elaboração do projeto, portabilidade e reuso de código – através da orientação a objetos de Java – podendo-se proteger os investimentos prévios em desenvolvimento de software. A validação desses conceitos foi realizada mediante estudos de casos, utilizando-se algumas aplicações e analisando os resultados obtidos com a geração dos ASICs.

Study of the audio coding algorithm of the MPEG-4 AAC standard and comparison among implementations of modules of the algorithm

Audio coding is used to compress digital audio signals, thereby reducing the amount of bits needed to transmit or to store an audio signal. This is useful when network bandwidth or storage capacity is very limited. Audio compression algorithms are based on an encoding and decoding process. In the encoding step, the uncompressed audio signal is transformed into a coded representation, thereby compressing the audio signal. Thereafter, the coded audio signal eventually needs to be restored (e.g. for playing back) through decoding of the coded audio signal. The decoder receives the bitstream and reconverts it into an uncompressed signal. ISO-MPEG is a standard for high-quality, low bit-rate video and audio coding. The audio part of the standard is composed by algorithms for high-quality low-bit-rate audio coding, i.e. algorithms that reduce the original bit-rate, while guaranteeing high quality of the audio signal. The audio coding algorithms consists of MPEG-1 (with three different layers), MPEG-2, MPEG-2 AAC, and MPEG-4. This work presents a study of the MPEG-4 AAC audio coding algorithm. Besides, it presents the implementation of the AAC algorithm on different platforms, and comparisons among implementations. The implementations are in C language, in Assembly of Intel Pentium, in C-language using DSP processor, and in HDL. Since each implementation has its own application niche, each one is valid as a final solution. Moreover, another purpose of this work is the comparison among these implementations, considering estimated costs, execution time, and advantages and disadvantages of each one.

Projeto cooperativo no Ambiente Cave baseado em espaço compartilhado de objetos

Este trabalho apresenta o módulo Collaborative Service, uma extensão do ambiente Cave, desenvolvido para suportar conceitos de trabalho cooperativo no projeto de circuitos integrados. Esta extensão por sua vez, é baseada na metodologia Pair- Programming e nas tecnologias Jini e Javaspaces. O módulo Collaborative Service foi desenvolvido para auxiliar a continuidade do processo de desenvolvimento de circuitos integrados complexos, inserindo uma dinâmica de grupo através da extensão de Pair-Programming para máquinas remotas. Esse modelo permite que dois ou mais projetistas interajam em um mesmo projeto ou blocos de projeto, independente de suas localizações geográficas e tipos de plataformas de hardware/software. Ele foi projetado para ser genérico e essa característica o torna capaz de suportar as ferramentas de CAD, atuais e futuras, do ambiente Cave (um framework de apoio ao projeto de circuitos integrados). Como estudo de caso, foram utilizadas duas ferramentas do Ambiente Cave. O primeiro caso mostra uma cooperação em nível de descrições gráficas, representada pela ferramenta Blade, um editor de esquemáticos hierárquico. O segundo caso foi representado pelo editor de descrições textuais (VHDL, Verilog e Linguagem C), chamado Homero. No estudo de caso com a ferramenta Blade foi demonstrado que a cooperação proposta por esse modelo pode atuar sob diferentes níveis de hierarquia de projeto, além de suportar a interação de inúmeros projetistas em um mesmo bloco. Na ferramenta Homero, demonstrou-se a cooperação em nível de descrições textuais, representados por (códigos) projetos VHDL acrescidos da participação de vários projetistas. Com esses exemplos, foi possível demonstrar as estratégias de percepção e comunicação com os projetistas, além de descrever a criação de blocos de projeto de uma forma cooperativa. Como contribuição desse trabalho, acrescenta-se ao Ambiente Cave mais um recurso para o projeto de circuitos integrados. Nesse sentido, grupos de projetistas podem projetar um sistema ou circuito integrado de forma cooperativa utilizando-se das funcionalidades desse modelo.

Desenvolvimento de arquitetura para sistemas de reconhecimento automático de voz baseados em modelos ocultos de Markov

Este trabalho foi realizado dentro da área de reconhecimento automático de voz (RAV). Atualmente, a maioria dos sistemas de RAV é baseada nos modelos ocultos de Markov (HMMs) [GOM 99] [GOM 99b], quer utilizando-os exclusivamente, quer utilizando-os em conjunto com outras técnicas e constituindo sistemas híbridos. A abordagem estatística dos HMMs tem mostrado ser uma das mais poderosas ferramentas disponíveis para a modelagem acústica e temporal do sinal de voz. A melhora da taxa de reconhecimento exige algoritmos mais complexos [RAV 96]. O aumento do tamanho do vocabulário ou do número de locutores exige um processamento computacional adicional. Certas aplicações, como a verificação de locutor ou o reconhecimento de diálogo podem exigir processamento em tempo real [DOD 85] [MAM 96]. Outras aplicações tais como brinquedos ou máquinas portáveis ainda podem agregar o requisito de portabilidade, e de baixo consumo, além de um sistema fisicamente compacto. Tais necessidades exigem uma solução em hardware. O presente trabalho propõe a implementação de um sistema de RAV utilizando hardware baseado em FPGAs (Field Programmable Gate Arrays) e otimizando os algoritmos que se utilizam no RAV. Foi feito um estudo dos sistemas de RAV e das técnicas que a maioria dos sistemas utiliza em cada etapa que os conforma. Deu-se especial ênfase aos Modelos Ocultos de Markov, seus algoritmos de cálculo de probabilidades, de treinamento e de decodificação de estados, e sua aplicação nos sistemas de RAV. Foi realizado um estudo comparativo dos sistemas em hardware, produzidos por outros centros de pesquisa, identificando algumas das suas características mais relevantes. Foi implementado um modelo de software, descrito neste trabalho, utilizado para validar os algoritmos de RAV e auxiliar na especificação em hardware. Um conjunto de funções digitais implementadas em FPGA, necessárias para o desenvolvimento de sistemas de RAV é descrito. Foram realizadas algumas modificações nos algoritmos de RAV para facilitar a implementação digital dos mesmos. A conexão, entre as funções digitais projetadas, para a implementação de um sistema de reconhecimento de palavras isoladas é aqui apresentado. A implementação em FPGA da etapa de pré-processamento, que inclui a pré-ênfase, janelamento e extração de características, e a implementação da etapa de reconhecimento são apresentadas finalmente neste trabalho.

Uma Metodologia para o desenvolvimento de aplicações de visão computacional utilizando um projeto conjunto de hardware e software

As tarefas de visão computacional incentivam uma significativa parte da pesquisa em todas as áreas científicas e industriais, entre as quais, cita-se a área voltada para o desenvolvimento de arquiteturas de computadores. A visão computacional é considerada um dos problemas mais desafiadores para a computação de alto desempenho, pois esta requer um grande desempenho, bem como um alto grau de flexibilidade. A flexibilidade é necessária pois a visão computacional abrange aplicações em que há diferentes tarefas a serem realizadas com diferentes necessidades de desempenho. Esta flexibilidade é particularmente importante em sistemas destinados a atuar como ambientes experimentais para novas técnicas de processamento visual ou para a prototipação de novas aplicações. Computação configurável tem demonstrado, por meio de exemplos implementados pela comunidade científica, fornecer uma boa relação entre alto desempenho e flexibilidade necessária para a implementação de diferentes técnicas utilizadas na área de visão computacional. Contudo, poucos esforços de pesquisa têm sido realizados na concepção de sistemas completos visando a solução de um problema de visão computacional, incluindo ambos os requisitos de software e de hardware. O principal objetivo deste trabalho é mostrar que as técnicas e tecnologias disponíveis na área de computação configurável podem ser empregadas para a concepção de um sistema capaz de implementar um grande número de aplicações da área de visão computacional na pesquisa e no ambiente industrial. Entretanto, não é escopo deste trabalho implementar um sistema de computação que seja suficiente para abordar os requerimentos necessários para todas as aplicações em visão computacional, mas os métodos aqui introduzidos podem ser utilizados como uma base geral de implementação de várias tarefas de visão computacional. Este trabalho utiliza ambientes que permitem implementações conjuntas de hardware e software, pois os mesmos facilitam a validação das técnicas aqui apresentadas, por meio da implementação de um estudo de caso, sendo parte deste estudo de caso implementado em software e outra parte em hardware.

Geração de código no projeto de sistemas reativos a partir da linguagem RS

A linguagem síncrona RS é destinada ao desenvolvimento de sistemas reativos. O presente trabalho tem como objetivo criar meios que facilitem o uso da linguagem RS no projeto e implementação desses sistemas, permitindo que, à partir da especificação de um sistema reativo, seja realizada a sua implementação de forma automática. Deste modo, a linguagem RS é utilizada para a descrição do comportamento de um sistema em um alto nível de abstração, antes de serfeitas a decomposição do sistema em componentes de software ou hardware. A implmentação do protótipo do sistema computacional dedicado é obtida através de uma síntese automática desse modelo de alto nível. Foram implementados geradores de código que utilizam o código objeto fornecido pelo compilador da linguagem RS. Os geradores fazem a tradução para a linguagem C, para a linguagem JAVA, ou para a linguagem de descrição de hardware VHDL. A partir da síntese desses códigos poderá ser obtida a implementação do sistema em um micrcoomputador comercial, em um microcomputador Java de dedicado (ASIP Java), ou em um hardware de aplicação específica (ASIC). Foram realizados estudos de caso representativos dos sistemas reativos embaraçados e de tempo rel. Estes estudos de caso serviram para validar os geradores de código bem como para analisar o uso da linguagem RS no projeto e implementação desses sistemas.

Inserção de testabilidade em um núcleo pré-projetado de um microcontrolador 8051 fonte compatível

No intuito de validar seus projetos de sistemas integrados, o Grupo de Microeletrônica da UFRGS tem investido na inserção de estruturas de teste nos núcleos de hardware que tem desenvolvido. Um exemplo de tal tipo de sistema é a “caneta tradutora”, especificada e parcialmente desenvolvida por Denis Franco. Esta caneta se utiliza de um microcontrolador 8051 descrito em VHDL, o qual ainda carece de estruturas dedicadas com funções orientadas à testabilidade. Este trabalho exemplifica a integração de teste em um circuito eletrônico préprojetado. Neste caso específico, foi utilizado o microcontrolador 8051 fonte compatível que será inserido no contexto da caneta tradutora. O método utilizado apoiou-se na norma IEEE1149.1, destinada a definir uma infra-estrutura baseada na técnica do boundary scan para o teste de placas de circuito impresso. São apresentadas características de testabilidade desenvolvidas para o microcontrolador, utilizando-se a técnica do boundary scan em sua periferia e a técnica do scan path em seu núcleo. A inserção destas características de teste facilita a depuração e testes em nível de sistema, imaginando-se o sistema como algo maior, fazendo parte do sistema da caneta tradutora como um todo. São elaborados exemplos de testes, demonstrando a funcionalidade do circuito de teste inserido neste núcleo e a possibilidade de detecção de falhas em pontos distintos do sistema. Finalmente, avalia-se o custo associado à integração desta infra-estrutura de teste, tanto em termos de acréscimo de área em silício, quanto em termos de degradação de desempenho do sistema.

ONNIS-GI: uma rede neural oscilatória para segmentação de imagens implementada em arquitetura maciçamente paralela

A presente tese apresenta a concepção de uma rede neural oscilatória e sua realização em arquitetura maciçamente paralela, a qual é adequada à implementação de chips de visão digitais para segmentação de imagens. A rede proposta, em sua versão final, foi denominada ONNIS-GI (Oscillatory Neural Network for Image Segmentation with Global Inhibition) e foi inspirada em uma rede denominada LEGION (Locally Excitatory Globally Inhibitory Oscillator Network), também de concepção recente. Inicialmente, é apresentada uma introdução aos procedimentos de segmentação de imagens, cujo objetivo é o de situar e enfatizar a importância do tema abordado dentro de um contexto abrangente, o qual inclui aplicações de visão artificial em geral. Outro aspecto abordado diz respeito à utilização de redes neurais artificiais em segmentação de imagens, enfatizando as denominadas redes neurais oscilatórias, as quais têm apresentado resultados estimulantes nesta área. A implementação de chips de visão, integrando sensores de imagens e redes maciçamente paralelas de processadores, é também abordada no texto, ressaltando o objetivo prático da nova rede neural proposta. No estudo da rede LEGION, são apresentados resultados de aplicações originais desenvolvidas em segmentação de imagens, nos quais é verificada sua propriedade de separação temporal dos segmentos. A versão contínua da rede, um arranjo paralelo de neurônios baseados em equações diferenciais, apresenta elevada complexidade computacional para implementação em hardware digital e muitos parâmetros, com procedimento de ajuste pouco prático. Por outro lado, sua arquitetura maciçamente paralela apresenta-se particularmente adequada à implementação de chips de visão analógicos com capacidade de segmentação de imagens. Com base nos bons resultados obtidos nas aplicações desenvolvidas, é proposta uma nova rede neural, em duas versões, ONNIS e ONNIS-GI, as quais suplantam a rede LEGION em diversos aspectos relativos à implementação prática. A estrutura dos elementos de processamento das duas versões da rede, sua implementação em arquitetura maciçamente paralela e resultados de simulações e implementações em FPGA são apresentados, demonstrando a viabilidade da proposta. Como resultado final, conclui-se que a rede ONNIS-GI apresenta maior apelo de ordem prática, sendo uma abordagem inovadora e promissora na solução de problemas de segmentação de imagens, possuindo capacidade para separar temporalmente os segmentos encontrados e facilitando a posterior identificação dos mesmos. Sob o ponto de vista prático, a nova rede pode ser utilizada para implementar chips de visão digitais com arquitetura maciçamente paralela, explorando a velocidade de tais topologias e apresentando também flexibilidade para implementação de procedimentos de segmentação de imagens mais sofisticados.

Uma ferramenta para geração de filtros FIR paralelos otimizados com coeficientes constantes

Esta dissertação trata da elaboração de uma ferrramenta para a geração de filtros FIR otimizados paralelos com coeficientes constantes. A ferramenta desenvolvida é capaz de gerar uma descrição VHDL de um filtro FIR paralelo com coeficientes constantes a partir das especificações do filtro. São exploradas técnicas de otimização de coeficientes e de otimização arquitetural. As técnicas empregadas são baseadas no uso de representações ternárias e redução do número de digitos não-zero dos coeficientes, uso de fatores de escala e eliminação de sub-expressões comuns. No texto, uma breve introdução sobre os filtros digitais é apresentada seguida por uma série de trabalhos encontrados na literatura relacionados às técnicas mencionadas e que são apresentados como base para o desenvolvimento da ferramenta implementada nesta dissertação. O funcionamento da ferramenta é detalhado tanto nos seus aspectos de algoritmo quanto em nível de implementação. São apresentados resultados de síntese em alguns de filtros hipotéticos projetados utilizando a ferramenta desenvolvida. Uma análise detalhada dos resultados obtidos é realizada. Os apêndices deste trabalho apresentam o código fonte da ferramenta de síntese de filtros desenvolvida.

Uma interface para o aumento da faixa de freqüências de operação de FPAAS

O crescente avanço nas mais diversas áreas da eletrônica, desde instrumentação em baixa freqüência até telecomunicações operando em freqüências muito elevadas, e a necessidade de soluções baratas em curto espaço de tempo que acompanhem a demanda de mercado, torna a procura por circuitos programáveis, tanto digitais como analógicos, um ponto comum em diversas pesquisas. Os dispositivos digitais programáveis, que têm como grande representante os Field Programmable Gate Arrays (FPGAs), vêm apresentando um elevado e contínuo crescimento em termos de complexidade, desempenho e número de transistores integrados, já há várias décadas. O desenvolvimento de dispositivos analógicos programáveis (Field Programmable Analog Arrays – FPAAs), entretanto, esbarra em dois pontos fundamentais que tornam sua evolução um tanto latente: a estreita largura de banda alcançada, conseqüência da necessidade de um grande número de chaves de programação e reconfiguração, e a elevada área consumida por componentes analógicos como resistores e capacitores, quando integrados em processos VLSI Este trabalho apresenta uma proposta para aumentar a faixa de freqüências das aplicações passíveis de serem utilizadas tanto em FPAAs comerciais quanto em outros FPAAs, através da utilização de uma interface de translação e seleção de sinais, mantendo características de programabilidade do FPAA em questão, sem aumentar em muito sua potência consumida. A proposta, a simulação e a implementação da interface são apresentadas ao longo desta dissertação. Resultados de simulação e resultados práticos obtidos comprovam a eficácia da proposta.

Mecanismos de reconfiguração dinâmica aplicados ao projeto de um processador de imagens reconfigurável

As modernas aplicações em diversas áreas como multimídia e telecomunicações exigem arquiteturas que ofereçam altas taxas de processamento. Entretanto, os padrões e algoritmos mudam com incrível rapidez o que gera a necessidade de que esses sistemas digitais tenham também por característica uma grande flexibilidade. Dentro desse contexto, tem-se as arquiteturas reconfiguráveis em geral e, mais recentemente, os sistemas reconfiguráveis em um único chip como soluções adequadas que podem oferecer desempenho, sendo, ao mesmo tempo, adaptáveis a novos problemas e a classes mais amplas de algoritmos dentro de um dado escopo de aplicação. Este trabalho apresenta o estado-da-arte em relação a arquiteturas reconfiguráveis nos meios acadêmcio e industrial e descreve todas as etapas de desenvolvimento do processador de imagens reconfigurável DRIP (Dynamically Reconfigurable Image Processor), desde suas origens como um processador estático até sua última versão reconfigurável em tempo de execução. O DRIP possui um pipeline composto por 81 processadores elementares. Esses processadores constituem a chave do processo de reconfiguração e possuem a capacidade de computar um grande número de algoritmos de processamento de imagens, mais específicamente dentro do domínio da filtragem digital de imagens. Durante o projeto, foram desenvolvidos uma série de modelos em linguagem de descrição de hardware da arquitetura e também ferramentas de software para auxiliar nos processos de implementação de novos algorimos, geração automática de modelos VHDL e validação das implementações. O desenvolvimento de mecanismos com o objetivo de incluir a possibilidade de reconfiguração dinâmica, naturalmente, introduz overheads na arquitetura. Contudo, o processo de reconfiguração do DRIP-RTR é da ordem de milhões de vezes mais rápido do que na versão estaticamente reconfigurável implementada em FPGAs Altera. Finalizando este trabalho, é apresentado o projeto lógico e elétrico do processador elementar do DRIP, visando uma futura implementação do sistema diretamente como um circuito VLSI.

Uma extensão do protocolo CAN para aplicações críticas em sistemas distribuídos

Sistemas computacionais de tempo-real são tipicamente construídos a partir de primitivas de sincronização que fornecem uma noção do tempo no objetivo de coordenar a execução múltiplos fluxos de instruções em um processador. Quando o processamento é centralizado, a base de tempo destas primitivas é extraída do oscilador local da plataforma, permitindo que as ações do sistema sejam devidamente ordenadas, respeitando restrições de tempo e causalidade. No entanto, em sistemas distribuídos o problema não pode ser resolvido desta forma em decorrência de imperfeições nos dispositivos físicos. Diferenças mínimas na freqüência de osciladores fazem com que as bases de tempo dos componentes divirjam cada vez mais ao longo do tempo, dificultando ou até mesmo impossibilitando um ordenamento consistente de eventos. Por esta razão, sincronização de relógios é um serviço de fundamental importância, sobretudo em aplicações críticas, onde os níveis de confiabilidade exigidos são mais elevados. O presente trabalho consiste na proposta e implementação de uma plataforma de comunicação otimizada para sistemas de controle distribuídos, caracterizados por uma alta regularidade no comportamento da comunicação. O objetivo é propor uma solução em baixo nível com suporte para o projeto de sistemas distribuídos no domínio de aplicações críticas. A plataforma proposta, à qual foi atribuído o nome CASCA, sigla para “Communication Architecture for Safety- Critical Applications”, é de fato uma extensão time-triggered do protocolo CAN. Acima da camada de enlace do protocolo original foram projetados mecanismos sincronização de relógios e criação inicial da base de tempo, implementados na forma de uma combinação de hardware e software. Principais características da plataforma são jitter mínimo, uma base de tempo global essencialmente distribuída e particionamento temporal. Diferentes alternativas de projeto foram consideradas, observando com maior atenção a viabilidade de prototipação em dispositivos FPGA para fins de validação e aplicação imediata em plataformas reconfiguráveis. Como forma de validação da plataforma, um sistema elementar formado por três nodos foi sintetizado com sucesso em bancada obtendo-se como resultado uma base de tempo essencialmente distribuída com precisão menor do que um micro-segundo.

Técnicas de controlo não-linear baseadas em Redes Neuronais: do algoritmo à implementação

O presente trabalho analisa soluções de controlo não-linear baseadas em Redes Neuronais e apresenta a sua aplicação a um caso prático, desde o algoritmo de treino até à implementação física em hardware. O estudo inicial do estado da arte da utilização das Redes Neuronais para o controlo leva à proposta de soluções iterativas para a definição da arquitectura das mesmas e para o estudo das técnicas de Regularização e Paragem de Treino Antecipada, através dos Algoritmos Genéticos e à proposta de uma forma de validação dos modelos obtidos. Ao longo da tese são utilizadas quatro malhas para o controlo baseado em modelos, uma das quais uma contribuição original, e é implementado um processo de identificação on-line, tendo por base o algoritmo de treino Levenberg-Marquardt e a técnica de Paragem de Treino Antecipada que permite o controlo de um sistema, sem necessidade de recorrer ao conhecimento prévio das suas características. O trabalho é finalizado com um estudo do hardware comercial disponível para a implementação de Redes Neuronais e com o desenvolvimento de uma solução de hardware utilizando uma FPGA. De referir que o trabalho prático de teste das soluções apresentadas é realizado com dados reais provenientes de um forno eléctrico de escala reduzida.