As antenas (e os arrays de antenas) operam frequentemente em ambientes dinâmicos, onde os sinais (desejados e interferentes) chegam de mudar de direção e com poderes variados. Como resultado, os arrays de antenas adaptativas foram desenvolvidos. Esses arrays de antenas empregam um algoritmo de ponderação adaptativa, que adapta os pesos com base nos sinais recebidos para melhorar o desempenho da matriz. Nesta seção, o algoritmo LMS é introduzido. LMS significa Least-Mean-Square. Este algoritmo foi desenvolvido por Bernard Widrow na década de 1960, e é o primeiro algoritmo adaptativo amplamente utilizado. Ainda é amplamente utilizado no processamento de sinal digital adaptável e matrizes de antenas adaptativas, principalmente por sua simplicidade, facilidade de implementação e boas propriedades de convergência. O objetivo do algoritmo LMS é produzir os pesos MMSE para o ambiente dado. As definições de todos os termos utilizados nesta página seguem a partir da página MMSE. O que deve ser entendido antes de ler esta página. O objetivo do algoritmo LMS é produzir pesos de forma adaptativa que minimizem o erro médio-quadrado entre um sinal desejado e a saída de arrays falando, ele tenta maximizar a recepção na direção do sinal desejado (quem ou o que a matriz está tentando Se comunicar com) e minimizar a recepção dos sinais interferentes ou indesejáveis. Assim como no caso do MMSE, é necessária alguma informação antes que os pesos ideais possam ser determinados. E, assim como no caso de ponderação do MMSE, a informação necessária é a direção e a potência dos sinais desejados. A direção é especificada através do vetor de direção dos sinais desejados () e a energia do sinal é escrita como. Observe que esses parâmetros podem variar com o tempo, já que o meio ambiente está sendo alterado. As direções e a potência podem ser determinadas usando vários algoritmos de busca de direção, que analisam os sinais recebidos em cada antena para estimar as direções e a potência. Lembre-se de que o erro Mean-Squared entre o sinal desejado e a saída do arrays pode ser escrito como: O gradiente (derivada do vetor em relação ao vetor de peso) pode ser escrito como: O algoritmo LMS requer uma estimativa da matriz de autocorrelação para Obtenha pesos que minimizem o MSE. O algoritmo LMS estima a matriz de autocorrelação () usando apenas o sinal recebido atual em cada antena (especificado pelo vetor X). Os pesos são atualizados iterativamente, em instâncias discretas de tempo, denotadas por um índice k. A estimativa da matriz de autocorrelação no tempo k. Escrito com uma sobrecarga de barra, é escrito como: O algoritmo LMS então se aproxima do gradiente do MSE, substituindo na aproximação simples acima para a matriz de autocorrelação: os pesos adaptativos serão escritos como W (k), onde k é um índice que Especifica o tempo. O algoritmo de ponderação LMS simplesmente atualiza os pesos por uma pequena quantidade na direção do gradiente negativo da função MSE. Ao se mover na direção do gradiente negativo, o MSE geral é diminuído em cada passo de tempo. Desta forma, os pesos abordam iterativamente os valores ótimos que minimizam o MSE. Além disso, uma vez que o algoritmo adaptativo está atualizando continuamente, à medida que o ambiente muda, os pesos se adaptam também. Os pesos são atualizados a intervalos regulares e o peso no tempo k 1 está relacionado ao tempo k por: O parâmetro controla o tamanho das etapas que os pesos fazem e afeta a velocidade de convergência do algoritmo. Para garantir a convergência, deve ser inferior a 2 dividido pelo maior autovalor da matriz de autocorrelação. Substituindo na estimativa para o gradiente acima, o algoritmo de atualização do LMS pode ser escrito como uma equação iterativa simples: a simplicidade do algoritmo é a principal razão para seu uso generalizado. A equação de atualização acima não requer nenhuma matemática complexa, ele apenas usa as amostras atuais do sinal recebido em cada antena (X). Exemplo de Algoritmo LMS Assuma uma matriz linear de antenas, com espaçamento de meio wavelength e N 5 elementos na matriz. Bem, suponha que a relação sinal / ruído (SNR) seja de 20 dB e que o ruído é gaussiano e independente de uma antena para a próxima. Suponha que existem duas interferências que chegam de 40 e 110 graus, com potência de interferência de 10 dB (em relação ao sinal desejado). Espera-se que o sinal desejado seja de 90 graus. O algoritmo está começando a assumir um vetor de peso de todos (o vetor de peso inicial idealmente não tem impacto nos resultados finais): O parâmetro de convergência é escolhido para ser: Usando o ruído aleatório em cada etapa, o algoritmo é avançado a partir do peso inicial . O MSE resultante em cada passo de tempo é mostrado na figura a seguir, em relação ao MSE ótimo. O algoritmo LMS é bastante eficiente em se mover para os pesos ideais para este caso. Uma vez que o algoritmo usa uma aproximação da matriz de autocorrelação em cada passo de tempo, algumas das etapas realmente aumentam a MSE. No entanto, em média, o MSE diminui. Este algoritmo também é bastante robusto para ambientes em mudança. Vários algoritmos adaptativos expandiram-se sobre idéias usadas no algoritmo LMS original. A maioria desses algoritmos procura produzir propriedades de convergência melhoradas à custa do aumento da complexidade computacional. Por exemplo, o algoritmo recursivo de mínimos quadrados (RLS) procura minimizar o MSE exatamente como no algoritmo LMS. No entanto, ele usa uma atualização mais sofisticada para encontrar os pesos ótimos que se baseiam no lema da inversão da matriz. Ambos os algoritmos (e todos os outros com base no algoritmo LMS) têm os mesmos pesos ótimos aos quais os algoritmos tentam convergir. Essa página no algoritmo LMS é protegida por direitos autorais. Nenhuma parte pode ser reproduzida exceto com permissão do autor. Teoria da antena de direitos autorais, 2009-2017. Algoritmo LMS para arrays de antenas. Pesquisa em Linha, Pesquisa Binária e outras Técnicas de Pesquisa A busca de dados é um dos campos fundamentais da computação. Muitas vezes, a diferença entre um programa rápido e um lento é o uso de um bom algoritmo para o conjunto de dados. Este artigo se concentrará na busca de dados armazenados em uma estrutura de dados linear, como uma matriz ou lista vinculada. Naturalmente, o uso de uma tabela de hash ou uma árvore de pesquisa binária resultará em busca mais eficiente, mas, na maioria das vezes, uma matriz ou lista vinculada será usada. É necessário entender boas maneiras de procurar estruturas de dados não projetadas para oferecer suporte a pesquisas eficientes. Pesquisa linear O algoritmo mais óbvio é começar no início e caminhar até o final, testando uma correspondência em cada item: esse algoritmo tem o benefício da simplicidade, é difícil errar, ao contrário de outras soluções mais sofisticadas. O código acima segue a convenção deste artigo, eles são os seguintes: Todas as rotinas de pesquisa retornam um valor booleano verdadeiro para sucesso ou falha. A lista será uma matriz de números inteiros ou uma lista vinculada de números inteiros com uma chave. O item encontrado será salvo em uma referência para um ponteiro para uso no código do cliente. O próprio algoritmo é simples. Um loop 0-n-1 familiar para percorrer cada item na matriz, com um teste para ver se o item atual na lista corresponde à tecla de pesquisa. O loop pode terminar de uma das duas maneiras. Se eu chegar ao final da lista, a condição do loop falhará. Se o item atual na lista corresponder à chave, o loop é encerrado cedo com uma declaração de interrupção. Em seguida, o algoritmo testa a variável de índice para ver se é menos esse tamanho (portanto, o loop foi encerrado cedo e o item foi encontrado) ou não (e o item não foi encontrado).Para uma lista vinculada definida como: O algoritmo é Igualmente simples: em vez de um ciclo de contagem, usamos um idioma para andar uma lista vinculada. O idioma deve ser familiar para a maioria dos leitores. Para aqueles que não estão familiarizados com isso, é assim que é feito. -) O loop termina se eu for um ponteiro nulo (o algoritmo assume que um ponteiro nulo termina a lista) ou se o item foi encontrado. O algoritmo de pesquisa seqüencial básico pode ser melhorado de várias maneiras. Uma dessas maneiras é assumir que o item que está sendo buscado estará sempre na lista. Desta forma, você pode evitar as duas condições de término no loop em favor de apenas uma. Claro, isso cria o problema de uma pesquisa com falha. Se assumirmos que o item sempre será encontrado, como podemos testar a falha. A resposta é usar uma lista maior em tamanho do que a quantidade de itens por um. Uma lista com dez itens receberia um tamanho de onze para uso pelo algoritmo. O conceito é muito parecido com as strings de estilo C e o terminador nul. O caracter nul não tem uso prático, exceto como um objeto fofo que delimita o fim da string. Quando o algoritmo começa, podemos simplesmente colocar a chave de pesquisa em listas para assegurar que sempre será encontrado: Observe que a única prova no loop de percurso está testando uma correspondência. Sabemos que o item está na lista em algum lugar, então não há necessidade de um corpo de loop. Após o loop o algoritmo simplesmente testa se eu for menor que o tamanho. Se é, então, encontramos uma correspondência real, caso contrário, eu sou igual ao tamanho. Como a listagem é onde o item fofo foi, podemos dizer com segurança que o item não existe em nenhum outro lugar da lista. Esse algoritmo é mais rápido porque reduz dois testes no loop para um teste. Não é uma grande melhoria, mas se jwsearch é chamado frequentemente em grandes listas, a otimização pode se tornar notável. Outra variação da pesquisa seqüencial pressupõe que a lista seja ordenada (em ordem ordenada ascendente para o algoritmo que usaremos): o desempenho para uma pesquisa bem-sucedida, onde todas as chaves são igualmente prováveis é o mesmo que o algoritmo básico. A melhoria da velocidade é para pesquisas falhadas. Como a ausência de um item pode ser determinada com mais rapidez, a velocidade média de uma pesquisa com falha é o dobro do algoritmo anterior em média. Ao combinar a busca sequencial rápida e a busca sequencial ordenada, pode-se ter um algoritmo de busca sequencial altamente sintonizado. Exercício 1: o último parágrafo sugere um algoritmo de busca sequencial eficiente. Use o que você aprendeu a implementá-lo. Exercício 2: Escreva um programa de teste para verificar o funcionamento correto das funções dadas. Exercício 3: Você consegue pensar em uma maneira mais eficiente de realizar pesquisas seqüenciais? Que tal uma pesquisa não-sequencial Busca auto organizadora? Para listas que não possuem um requisito de ordem definida, um algoritmo auto organizado pode ser mais eficiente se alguns itens na lista São procurados com mais freqüência do que outros. Ao borbulhar um item encontrado em direção à frente da lista, pesquisas futuras desse item serão executadas mais rapidamente. Essa melhoria de velocidade aproveita o fato de que 80 de todas as operações são realizadas em 20 dos itens em um conjunto de dados. Se esses itens estiverem mais próximos da frente da lista, a pesquisa será acelerada consideravelmente. A primeira solução que vem à mente é mover o item encontrado para a frente. Com uma matriz, isso resultaria em mudança de memória bastante dispendiosa: preencher o buraco deixado removendo o item encontrado e, em seguida, mudar todo o conteúdo da matriz para abrir espaço na frente é terrivelmente caro e provavelmente tornaria este algoritmo impraticável para arrays. No entanto, com uma lista vinculada, a operação de splicing necessária para reestruturar a lista e enviar o item para a frente é rápida e trivial. Para uma estrutura de dados vinculada, mover um item para uma nova posição em grandes distâncias tem uma complexidade de tempo constante, O ( 1), enquanto que para a memória contígua, como uma matriz, a complexidade do tempo é O (N) onde N é o intervalo de itens que está sendo deslocado. Uma solução que é tão eficaz, mas leva mais tempo para alcançar o limite ideal é trocar o item encontrado pelo item anterior na lista. Este algoritmo é onde os arrays são superiores às listas vinculadas para o nosso conjunto de dados de números inteiros. O custo de trocar dois números inteiros é menor que o da cirurgia com ponteiros. O código também é simples: Exercício 4: A regra 80-20 realmente sugere uma melhoria em relação aos algoritmos de busca seqüencial anteriores. Em caso afirmativo, em que ponto o aumento do desempenho aumenta o custo da reestruturação da lista. Exercício 5: Sintonize a fonte 6 para Correr o mais rápido possível. Será útil usar no código de produção Exercício 6: Reescrever a fonte 8 para usar listas vinculadas. Compare e contraste as duas funções. Exercício 7: considere mudar o item em distâncias menores, 12 ou 13 da distância para a frente, por exemplo. É uma mudança que vale a pena o esforço É uma melhoria de qualquer maneira Busca em binário Todos os algoritmos de busca seqüencial têm o mesmo problema que eles caminham sobre toda a lista. Algumas de nossas melhorias funcionam para minimizar o custo de atravessar todo o conjunto de dados, mas essas melhorias apenas cobrem o que é realmente um problema com o algoritmo. Ao pensar nos dados de uma maneira diferente, podemos fazer melhorias de velocidade que são muito melhores do que qualquer busca sequencial pode garantir. Considere uma lista na ordem ordenada ascendente. Isso funcionaria para pesquisar desde o início até encontrar um item ou o final é alcançado, mas faz mais sentido remover o conjunto de dados de trabalho possível para que o item seja encontrado mais rapidamente. Se começássemos no meio da lista, poderíamos determinar qual metade do item está em (porque a lista está ordenada). Isso efetivamente divide a faixa de trabalho pela metade com um único teste. Ao repetir o procedimento, o resultado é um algoritmo de pesquisa altamente eficiente chamado busca binária. O algoritmo real é surpreendentemente complicado de implementar considerando a aparente simplicidade do conceito. Aqui está uma função correta que implementa pesquisa binária, marcando os limites inferiores e superiores atuais para o intervalo de trabalho: Nenhuma explicação será dada para este código. Espera-se que os leitores rastreiem sua execução em papel e com um programa de teste para entender completamente a sua elegância. A busca em binário é muito eficiente, mas pode ser melhorada ao escrever uma variação que procura mais como os humanos. Considere como você procuraria um nome na lista telefônica. Não conheço ninguém que comece no meio se estiver procurando por um nome que comece com B. Eles começariam no local mais provável e então usariam esse local como um indicador para o próximo local mais provável. Essa pesquisa é chamada de pesquisa de interpolação porque estima a posição do item que está sendo pesquisado com base nos limites superior e inferior do intervalo. O próprio algoritmo não é muito difícil, mas parece assim com o cálculo do intervalo: mais uma vez, nenhuma explicação será dada. Se você chegou até aqui, você deveria estar escrevendo o código de teste e fazendo execuções de papel de qualquer novo algoritmo que você conheça como hábito. Caso contrário, agora você não tem escolha porque não vou dizer apenas como funciona esta função. É Magica. -) A pesquisa de interpolação é teoricamente superior à pesquisa binária. Com uma complexidade de tempo médio de O (log log), a pesquisa de interpolação bate as buscas binárias O (log n) facilmente. No entanto, os testes mostraram que a pesquisa de interpolação não é significativamente melhor na prática, a menos que o conjunto de dados seja muito grande. Caso contrário, a busca em binário é mais rápida. Exercício 8: Explique por que a pesquisa binária é tão complicada de implementar. Mostre um exemplo de uma implementação incorreta. Exercício 9: A pesquisa binária usa um algoritmo de divisão e conquista. Que outros problemas pode resolver este algoritmo Exercício 10: Determine o limite inferior onde a pesquisa de interpolação se torna substancialmente melhor do que a pesquisa binária. Exercício 11: escreva uma função de pesquisa que usa pesquisa de interpolação até o limite inferior ser atingido e depois muda para pesquisa binária. O desempenho extra vale o esforço Conclusão A pesquisa é uma função importante na ciência da computação. Muitos algoritmos avançados e estruturas de dados foram concebidos com o único propósito de tornar as pesquisas mais eficientes. E, à medida que os conjuntos de dados se tornam maiores e maiores, bons algoritmos de busca se tornarão mais importantes. Em um ponto da história da computação, a pesquisa seqüencial era suficiente. Mas isso mudou rapidamente à medida que o valor dos computadores se tornou aparente. A busca linear tem muitas propriedades interessantes por direito próprio, mas também é uma base para todos os outros algoritmos de pesquisa. Aprender como funciona é fundamental. A busca em binário é a próxima etapa lógica na busca. Ao dividir o conjunto de dados de trabalho ao meio com cada comparação, o desempenho logarítmico, O (log n), é alcançado. Esse desempenho pode ser melhorado significativamente quando o conjunto de dados é muito grande usando a pesquisa de interpolação e melhorou novamente ao usar a pesquisa binária quando o conjunto de dados é menor.
No comments:
Post a Comment