Algoritmos para processamento digital de sinais.

Felipe Electronic · 7 de abril de 2014

Resolvi pegar o port da criança e dar uma olhada.

Conforme especificado no documento do algoritmo original de Ulmann (que ele baseou esse codigo ai), a FHT pode ser feita reaproveitando uma boa parte do código de um FFT, por exemplo a parte de reordenar o vetor em moto bit-reversed é igual, isso ajuda para fazer um port para o usuario usar FFT ou a FHT.

O port pra C ali não precisa, do jeito que esta ta bem codificado, além das funções adicionais. Para mexer mesmo talvez somente pro Bascom ou casos como uso no CCS.

Vou rodar o código do jeito que está e medir o desempenho no PIC24 - (Simples, ele nao tem MAC, 16bits mesmo datawide do código, e arquitetura muito parecida com micros competidores). No ARM não deu nem graça, é muito rápido e ainda da pra otimizar mais usando expressões C que forçam o compilador a usar instruções do HW especifico pra DSP (SIMD, MAC).

Abs!

MatheusLPS · 8 de abril de 2014

Fala povo.

Meu port está pronto. Falta só ler o código novamente e tentar diminuir o tamanho ocupado pelas variáveis.

Na simulação está ótimo. Não contei o tempo de execução ainda. Estou lendo o canal AD a cada 50uS (20khz).

Para uma entrada de 5Khz, tenho essa saída:

10000 khz / 64 amostras: 32 saídas, sendo 10000/32 = 312.5Hz, ou seja, cada bin estará distante 312.5Hz do outro. Sendo assim, meu exemplo de entrada de 5Khz, terá que estar na posição 16:

Saida da leitura do canal AD ((read_adc() -512)*32  12416, -10560, -12448,  10528,  12416, -10560, -12448,  10528,  12416, -10560, -12448,  10528,  12416, -10560, -12448,  10528,  12416, -10560, -12448,  10528,  12416, -10560, -12448,  10528,  12416, -10560, -12448,  10528,  12416, -10560, -12448,  10528,  12416, -10560, -12448,  10528,  12416, -10560, -12448,  10528,  12416, -10560, -12448,  10528,  12416, -10560, -12448,  10528,  12416, -10560, -12448,  10528,  12416, -10560, -12448,  10528,  12416, -10560, -12448,  10528,  12416, -10560, -12448,  10528 Saida da função fhtDitInt():    -16,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,    944,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,  11488,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0 Saida da função complexToReal():      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,     63,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0,      0   0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |*************************************************************** 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 |

Testar com audio real agora.

Falou

MatheusLPS · 9 de abril de 2014

Bom, simulando a 20Mhz, deu em torno de 60mS no 18F2550. Ainda atualizo 4 MAX7219 com 4 matrizes.

Vou montar um protótipo e testar na prática com 48Mhz utilizando PLL. Vamos ver no que dá. Imagino que chegue a 30mS por cálculo da FHT + atualização dos displays.

Com isso, acho que dá para atualizar a pelo menos 30Hz.

Falou

MatheusLPS · 9 de abril de 2014

Algumas marcações com relação ao tempo de execução.

Tudo simulado. Não testado na bancada ainda.

Falou

Felipe Electronic · 9 de abril de 2014

30mS para calcular a FHT num 18F?

Acho que da pra otimizar mais, Matheus tem como mandar a listagem em Assembly pra nos vermos o que o compilador ta gerando pra calcular a FHT, de repente algumas otimizações como "loop unrolling" ou forçar o uso do multiplicador via HW do PIC podem não estarem sendo feitas.

Aqui na bancada rodei no PIC24F a 32MHz (ou seja máxima execução de 16MIPS) e consegui tempos inferiores a 200uS com 256 pontos. O XC16 otimizou bem a listagem em assembly.

Fiz os testes reais, e usei um dos timers do PIC para medir o tempo, gostei dos resultados... vou montar uma simulação no Proteus como o @Matheus_LPS fez e postarei aqui

Abs.

MatheusLPS · 9 de abril de 2014

@

Quando chegar em casa, passo a listagem assembly.

Mas veja o que o autor do artigo comenta sobre rodar no arduino:

"Having said this, the library is easily fast enough to provide real-time Fourier analysis even on a 16Mhz ATmega328P and requires around 17 ms to both permute the input and perform the FHT (of 256 inputs). Performance can be significantly improved by clocking the ATmega at its full 20Mhz if required."

O PIC é mais lento. Aqui deu os próximos a 30mS. Quase o dobro do tempo do cara. Bom, vou mandar o que você solicitou mais tarde para vermos.

Falou

Felipe Electronic · 9 de abril de 2014

No caso do PIC24 é completamente entendível porque o desempenho é melhor visto que o data width é de 16bits, portanto requer menos movimentação de memória do que nos nossos colegas de 8bits.

Levar 17ms no AVR também é entendível, mas veja que ele processou a FHT com 256 pontos, enquanto que a demonstração que você fez com PIC foram com 32 pontos estou certo?

Ainda assim creio que o compilador esteja fazendo alguma coisa (ou não esteja fazendo alguma coisa no meio de campo).

Vamos nos falando.

Abs.

MatheusLPS · 9 de abril de 2014

@

Qual modelo específico de PIC24F você está usando?

Falou

Felipe Electronic · 10 de abril de 2014

Fala Matheus estou usando esse

http://www.microchip.com/wwwproducts/Devices.aspx?product=PIC24F16KA102

Faz parte de uma familia melhorada da microchip, de baixo custo mas muito poderoso, estou escrevendo um RTOS e estou seriamente trabalhando num port pra ele.

Detalhe o microstick, ferramenta de desenvolvimento com ele está baratíssimo!

Vou continuar a fazer mais testes

Abs.

Felipe

MatheusLPS · 10 de abril de 2014

@

Boa dica. Vi aqui e custa $34 a placa de desenvolvimento. Bem barato mesmo.

Bom, segui sua dica de olhar o ASM gerado pelo código do CCS.

Observei muita coisa interessante.

Dei uma enxugada no meu port. Eu havia declarado várias variáveis como 16 bits, sendo que poderiam ser de 8 bits (apenas contadores). Só nessa mudança consegui diminuir em 10mS a execução da rotina de FHT.

Outra detalhe mais importante que posso tentar modificar é o seguinte:

O PIC18 possui multiplicação por hardware de variáveis de 8 bits. Exemplo:

Se eu faço isso:

int8 a=10,b=50;int16 c; c = a * b

O CCS não otimiza a multiplicação. Ele faz multiplicação aritimética.

Mas se eu utilizo uma função específica dele a _mul():

int8 a=10, b=50;int16 c; c = _mul(a,;

Dessa forma acima, ele otima o código e usa o comando MULWF. Resultando em uma multiplicação por hardware. Ótimo.

No entanto, na rotina FHT, o autor utiliza valores de 16 bits. O vetor que armazena os valores AD são de 16 bits, e a própria rotina pega essas valores e "amplifica" para signed int16 (16 bits com sinal). Ficam em torno de + ou - 16800. Algo nesse ponto aí.

Dentro da rotina, temos multiplicação de variáveis de 16 bits. Isso é o que gargala o código no PIC18. Pelo menos eu acho. Olhando o ASM gerado pela multiplicação, ele fica enorme. Realmente usando de multiplicação aritimética.

Olhando a página que você enviou do PIC24, nela diz isso:

CPU:

Up to 16 MIPS performance
Single Cycle Instruction Execution
16 x 16 Hardware Multiply, & 32-bit x 16-bit Hardware Divider
C Compiler Optimized Instruction Set System

Olha aí, ele possui multiplicação de 16 x 16 via hardware.

No caso, eu poderia alterar o port que fiz para evitar essa multiplicação de 16 x 16. Tornando ela 8 x 8 e só no final tranformar tudo em 16 bits novamente.Não sei se vai ficar bom.

Devo testar primeiro com o PIC18 a 48Mhz para ver como fica. Se fiocar ruim, tento modificar o código como disse acima.

Não quero fazer isso agora pois tenho medo de mexer mais e mais e no final ficar ruim. Eu posso perder resoluação com isso eu acho.

Bom é isso.

Se eu falei alguma asneira, pode corrigir aí.

Falou

Felipe Electronic · 10 de abril de 2014

@Matheus_LPS,

evoluiu bastante no período que estive fora, meus parabéns!

Bem vamos as suas considerações, na verdade estão todas corretas, o que temos de gargalo agora é a multiplicação por hardware...deixe me ver se da pra eu dar um pitaco:

o problema de fazer multiplicação 8x8 duas vezes para cada operação é um problema que nao da pra mexer, dado o data wide do PIC18, o que pode ser melhorado são os passos intermediários, por exemplo a forma como ele acessa a memória para fazer as multiplicações.

Você também pode criar sua rotina otimizada de multiplicação de 16bits, de forma que os data fetches fiquem sob o seu controle, como? veja, você já descobriu que ele usou o mulwf usando o _mul(a, certo?

Vou tentar implementar uma rotina 16x16 rápida usando a macro que me passaste e depois voce pode testar o resultado

Vou ver se termino ate o fim do dia.

EDIT: @Matheus_LPS, segue a rotina que escrevi, com ela é possivel fazer multiplicação 16x16 bits com resultado de 32bits

usando aquela macro _mul() ou seja apenas fazendo multiplicação 8x8. Usa somente shifts e mascaras, nada de operações complexas. Vale lembar que nao cooloquei nenhum controle de parametro, se estourar as duas variaveis de 16bits o resultado vira com overflow, portanto atenção. O resultado é um numero de 32bits, para escalar ele para 16bits basta tomar o valor e fazer 16 shifts para direita (isso é rápido no PIC18).

Faça um teste substituindo os * pela chamada dessa funcao.

OBS.: Precisa da biblioteca <stdint.h> ´para uso dos tipos padrão do C, se nao tiver ela disponivel no CCS basta voce reescrever os tipos para os equivalentes no CCS ex: uint16_t para int16 no CCS.

Oia o código:

/**********************************************************		dFastMult()				Multiplica de forma eficiente dois numeros		de 16bits com resultado de 16bits				parametros: wMult1 -- operando 1					wMult2 -- operando 2		retorna: 	Resultado da multiplicação em 32bits**********************************************************/uint32_t dFastMult(uint16_t wMult1, uint16_t wMult2)	{	uint32_t dResultado = 0;	//utiliza um algoritmo de separação de operandos:	//onde:	// A*B = (A_hi * B_hi << 16) + (B_lo * A_Hi << 8) + (A_lo* B_hi << 8) + (A_lo * B_lo)	// lo = low	// hi = hi		//temporarios de 8bits para escalar o resultado	uint8_t  bAtempHi = 0, bAtempLo = 0;		//temporarios de 8bits para escalar o resultado	uint8_t  bBtempHi = 0, bBtempLo = 0;			//iniccializa variaveis em modo 8bits:	//parte alta  A	bAtempHi = (uint8_t)((wMult1 & 0xFF00)>> 8);		//parte alta B	bBtempHi = (uint8_t)((wMult2 & 0xFF00)>> 8);		//parte baixa A	bAtempLo = (uint8_t)((wMult1 & 0x00FF));		//parte baixa B	bBtempLo = (uint8_t)((wMult2 & 0x00FF));		//executa o algoritmo	dResultado = (uint32_t)((_mul(bAtempHi , bBtempHi) << 16) + 				(_mul(bBtempLo , bAtempHi) << 8) + 				(_mul(bAtempLo, bBtempHi) << 8) + 				(_mul(bAtempLo , bBtempLo)));	return(dResultado);	}

Abs.

Felipe

aphawk · 12 de abril de 2014

@ e @MatheusLPS,

Opa, gostei !!!! Acho que agora vai sair mesmo o analizador de espectro !

Matheus, eu ví seu exemplo com o Max7219, se quiser eu tenho algo comigo que eu comprei faz mais de um ano, só esperando este projeto virar realidade :

30 matrizes 8x8 BICOLOR verde e vermelho, especiais para funcionar com o Max7219! Podemos em uma das linhas ligar ambos os Leds, para termos uma cor diferente, tipo um amarelo, sinalizando 0 db, acima dessa linha ligamos os vermelhos, e abaixo ligamos os verdes. Usamos duas matrizes na vertical, para aumentar a resolução. Se conseguirmos 10 frequências e ainda mais em Estéreo, podemos usar 3 matrizes na horizontal , e teremos um total de 6 matrizes,fazendo uma única de 24 col x 16 lin . Podemos usar duas colunas para mostrar o volume aplicado também. Deve ficar muito bonito isso !

Felipe, manda bala que estou quase fazendo o layout já !!!!

Paulo

MatheusLPS · 12 de abril de 2014

@

Poxa, só hoje que vi que você editou o seu post. Não tinha visto a rotina que você postou pois não recebi a notificação que você fez em meu nome. Vou testar ela com certeza!

@aphawk

Poxa, estou atrás de umas matrizes assim!!!

Mas tem um detalhe simples. A rotina que o cara mostrou utiliza 32, 64, 128 e 256 pontos de amostras e retorna a metade disso como resultado.

Dessa forma, a sua ideia de usar uma combinação de matrizes para obter 24x16 nao ficaria muito bom. Podemos fazer 16x16 ou 32x16. Esse valor, 32x16 é que estou tendo em mente.

Eu já tinha pensando mesmo em usar duas na vertical para aumentar a resolução. Nesse caso, do estéreo, seriam duas de 32x16 certo? Uma para cada canal.

isso vai ficar bem legal.

Falou

Felipe Electronic · 13 de abril de 2014

Então, só um adendo.

Eu ainda acho que seria mais bonitao usando display TFT

Vamos ver como ficou o port do @Matheus_LPS e assim que ele der um retorno eu faço o port dessa multiplicação eficiente pro AVR também

@aphawk, sabe se no Bascom existe alguma macro ou diretiva de compilador que force o uso da multiplicação por hardware do AVR?

valeu!

aphawk · 13 de abril de 2014

@,

Se usar o chip que tenha isso no hardware, é automático. Mas eu posso criar as rotinas em assembler e chamar as mesmas como uma função normal dentro do Bascom, eu vou desassemblar um programinha e ver como o compilador está fazendo para um Atmega328P.

Eu tava aqui pensando com meus botões em como usar dois canais do A/d para fazer os samplings dos canais esquerdo e direito, e fazer os processamentos dos dois, e fazer as atualizações dos displays... No caso do Atmega temos 2k de Ram, o que é o suficiente para manter dois buffers de amostragens, e escolher qual o buffer a ser processado, mas precisamos ver exatamente como fazer os processamentos, olhe o problema que eu estou pensando :

As frequências padrão para o analizador são estas :

32 64 128 256 512 1024 2048 4096 8192 16384 .

Não dá para fazer um sampling para tratar toda a banda com 32 hz de espaçamento ! São 512 pontos, e vai demorar bastante isso.

Por outro lado, pensei em fazer algo doido :

Usar dois canais A/d , mas com taxas diferentes ! Assim, um deles faria a aquisição com espaçamento temporal para podermos processar de 32 hz até 512 hz, o que daria apenas 16 pontos e deve ser muito rápido o processamento; o outro A/d vai fazer a aquisição para processarmos de 1024 até 16384, com espaçamento de 1024 teremos tambem 16 pontos

Programamos os timers para isso, e teremos um total de 4 buffers para serem processados ( no caso de estéreo ), e serão os quatro com 16 pontos. Mesmo que seja 4 buffers de 32 pontos , seria bem rápido !

Não sei se essa transformada permite o tratamento matemático desse tipo que planejei, nem sei se fiz algum erro teórico nisso, que que voce acha ?

Concordo que fica muito mais bonito com o TFT.... Só não sei se usando SPI ou I2C vamos conseguir atualizar todas as barras com um bom refresh... se tiver de usar modos paralelos de 8 ou 16 bits, dá tranquilo, mas só de pensar ligar tantos fios no display me desanima ...

@MatheusLPS,

Bom, eu tenho aqui 30 delas, não encontrei em lugar nenhum para comprar, mas como eu já tive negócio com um fabricante de matrizes que tinha essa opção no catálogo sob encomenda, eu fiz isso, encomendei 30 peças hehehe !

Fica tranquilo que dá para a gente fazer 3 conjuntos de 32x16 para montarmos nossos 3 aparelhos, estão na mão !

Quanto ao sampling, repare o problema que eu citei para o Felipe, para obtermos resolução de 32 hz precisamos de uma matriz enorme e que demoraria muito para processar..... Espero que o que eu falei seja possível de ser feito....

Mas um display com TFT ficaria muito bonito também ....

Paulo

Felipe Electronic · 14 de abril de 2014

@aphawk

Se usar o chip que tenha isso no hardware, é automático. Mas eu posso criar as rotinas em assembler e chamar as mesmas como uma função normal dentro do Bascom, eu vou desassemblar um programinha e ver como o compilador está fazendo para um Atmega328P.

Sem problemas, se a rotina de multiplicação 8x8 for rápida, nem vale a pena mexer. Caso contrário seria bom avaliar a multiplicação 16X16 acima forçando o uso da instrução MUL ou SMUL via hardware.

Eu tava aqui pensando com meus botões em como usar dois canais do A/d para fazer os samplings dos canais esquerdo e direito, e fazer os processamentos dos dois, e fazer as atualizações dos displays... No caso do Atmega temos 2k de Ram, o que é o suficiente para manter dois buffers de amostragens, e escolher qual o buffer a ser processado, mas precisamos ver exatamente como fazer os processamentos, olhe o problema que eu estou pensando :

As frequências padrão para o analizador são estas :
32 64 128 256 512 1024 2048 4096 8192 16384 .
Não dá para fazer um sampling para tratar toda a banda com 32 hz de espaçamento ! São 512 pontos, e vai demorar bastante isso.
Por outro lado, pensei em fazer algo doido :
Usar dois canais A/d , mas com taxas diferentes ! Assim, um deles faria a aquisição com espaçamento temporal para podermos processar de 32 hz até 512 hz, o que daria apenas 16 pontos e deve ser muito rápido o processamento; o outro A/d vai fazer a aquisição para processarmos de 1024 até 16384, com espaçamento de 1024 teremos tambem 16 pontos
Programamos os timers para isso, e teremos um total de 4 buffers para serem processados ( no caso de estéreo ), e serão os quatro com 16 pontos. Mesmo que seja 4 buffers de 32 pontos , seria bem rápido !

Nesse problema eu partiria para uma abordagem mais simples, usar dois microcontroladores! Um para processamento e outro só para o IHM, e matamos dois problemas de uma vez, isso vai permitir calcular de forma rápida a FFT (seja de 256 ou 512 pontos) e enviar apenas o quadro de dados sem nenhuma formatação para o segundo micro usando uma UART.

No MCU da IHM a utilização de dois buffers operando em ping-pong ja formariam a base para os gráficos, e poderiamos consumir seu processamento apenas para formatar o gráfico e dar refresh na tela. Com essa abordagem poderiamos ter o overhead do sistema melhor distribuido afinal um mega8 ou derivados são baratinhos, melhor do que colocar tudo dentro de um mega 328 e ter que ficar mexendo no cálculo da FFT (que só lembrando, se mudar a quantidade de pontos, muda o twiddle factors, e a porcaria da rotina do bit-reversed). O que acham? Vamos partir para a simplicidade?

Sobre o display, acredito que se fizer BEM FEITO da pra conseguir uma boa taxa de frames por segundo, utilizando um pouco de estrutura de dados podemos formar uma fila, e ir adicionando os quadros em ordem, e criar uma tarefa separada so para a atualização do LCD. utilização de transmissão por interrupção (nada de polling!) também melhora consideravelmente a taxa de refresh...

Enfim, vejam o que é melhor...

Abs!

aphawk · 15 de abril de 2014

@ e @MatheusLPS,

Podemos usar dois processadores, mas não adianta pensar em Atmega8 se usar buffer de 512 pontos, pois só tem 1k de Sram.

Além do mais, pelo menos em DIP, encontro mais barato o Atmega328 do que o Atmega8 hoje..... não sei nos outros invólucros.

E ainda tem esta : podemos rodar o Atmega328 a 32 Mhz com clock externo !!!! Creio que com isto não precisaria usar dois processadores, mas se for para facilitar o software, tudo bem.

Por outro lado, a 32 Mhz podemos usar display com interface SPI numa excelente velocidade, que com certeza vai atingir uma boa taxa de refresh. Creio que atualizar o display a 30 fps será bem fácil com esse clock. Aliás, acho que dá para fazer tudo com só um processador nessa velocidade, com displays SPI.

Paulo

MatheusLPS · 15 de abril de 2014

Bom, a ideia é boa. Mas tenho que testar o comportamento do PIC nesse tipo de display pois nunca usei.

Uma vez usei display gráfico e ficou meio lerdão. A rotina que usei preenchia pixel a pixel. Aí demorava um pouco. Pelo menos eu percebia...

A vantagem de usar um display TFT é que fica mais enxuta a montagem.

EDIT: Sobre usar dois uC, não vejo problemas. Estão muito baratos e facilita o código pois não precisamos ficam polindo bytes para obter ganhos pequenos. Chega um ponto que o uC está no limite e isso só causa cansaço no programador.

Falou

Felipe Electronic · 15 de abril de 2014

@aphawk,

Podemos usar dois processadores, mas não adianta pensar em Atmega8 se usar buffer de 512 pontos, pois só tem 1k de Sram.
Além do mais, pelo menos em DIP, encontro mais barato o Atmega328 do que o Atmega8 hoje..... não sei nos outros invólucros.

Citei o Mega8 apenas para fins de referência, fazendo uma pesquisa mais detalhada, o 328p se mostra bem mais adequado a aplicação.

E ainda tem esta : podemos rodar o Atmega328 a 32 Mhz com clock externo !!!! Creio que com isto não precisaria usar dois processadores, mas se for para facilitar o software, tudo bem.

Queria desmistificar um ponto sobre qualidade de software aproveitando o que disse, clock alto (extraindo os full 20MIPS no caso) não implica em desempenho se a qualidade do software desenvolvida não for boa. Citei o uso de dois processadores não pelo fato de falta de desempenho do AVR de fazer tudo num lugar só, o que enxergo é que usando o mega no gargalo, vai caber tudo, só que a complexidadade do software nao vai justificar a simplicidade do projeto, pensem nos inumeros mecanismos de sincronização de interrupção que teriamos que usar para processar a FHT e dar sweep no display? Usar um kernelzinho multitarefa resolveria o problema...mas nao num AVR.

Por isso a abordagem de pegar o problema e dividir em subtarefas mais fáceis de executar, vale lembrar que o conceito de processamento da FFT exige uma forma de programar, e o conceito de apresentar os dados exige outra forma de programar, então por que nao deixar a cargo de dois processadores trabalharem de forma concorrente (nesse caso paralelos e assincronos) e tratar as tarefas em separado? Verão que fora a montagem, que vai ficar mais chatinha, o software final vai ficar beeeeeem menor, mais legível, realmente feito "for dummies".

@Matheus_LPS,

Bom, a ideia é boa. Mas tenho que testar o comportamento do PIC nesse tipo de display pois nunca usei.

Uma vez usei display gráfico e ficou meio lerdão. A rotina que usei preenchia pixel a pixel. Aí demorava um pouco. Pelo menos eu percebia...

Dado a "baratisse" dos PIC24 nos ultimos anos, nao seria interessante considerar seu uso? Não que o PIC18 não de conta, apenas sugiro pois a arquitetura 24F está em tendência de se tornar a arquitetura padrão Microchip. Em todo o caso o que acha do uso de dois processadores para tratarem em separado?

EDIT: Sobre usar dois uC, não vejo problemas. Estão muito baratos e facilita o código pois não precisamos ficam polindo bytes para obter ganhos pequenos. Chega um ponto que o uC está no limite e isso só causa cansaço no programador.

É bem disso que falo.

Abs.

Felipe