Corrigindo erros por meio de códigos lineares

Desde os trabalhos de Claude Shannon, em 1948, o avan¸co tecnológico na área das telecomunicações tem sido notável. Um grande problema na transmissão de mensagens por algum canal sempre residiu no fato de que, ao atravessar o canal, o conteúdo transmitido sofre distorções e chega modificado ao destinatário, o que impossibita a sua leitura correta. Graças ao trabalho de Shannon, esse problema obteve uma solução. Para identificar erros na transmissão de uma mensagem e corrigí-los, criaram-se os códigos corretores de erros, dos quais trataremos neste artigo, com destaque à classe dos códigos lineares. Para tanto, serão dados alguns resultados importantes relacionados aos corpos finitos, que são estruturas algébricas importantes sobre as quais se constroem esses códigos.

Criptografia de Chave Pública com Base em Códigos

Este trabalho de dissertação foca o sistema criptográfico de McEliece. Este é um sistema criptográfico de chave pública que tira partido do facto do problema de descodificação de um código linear geral ser NP-completo. Mais especificamente, este sistema criptográfico usa um código de Goppa sobre um corpo finito como chave privada, para o qual existe um algoritmo de descodificação eficiente, e um código linear geral, derivado do código Goppa anterior, como chave pública. Assim, neste trabalho, começa-se por analisar alguns resultados sobre corpos finitos, necessários ao longo desta dissertação. Posteriormente, estudam-se os códigos lineares sobre corpos finitos, em particular os códigos de Goppa, apresentando-se um algoritmo de descodificação para estes códigos. Em seguida, é apresentada uma descrição detalhada do sistema criptográfico de McEliece e são analisados alguns ataques a este sistema criptográfico. Por fim, é ainda analisada a sua aplicação na segurança de assinaturas digitais.

Uma construção de códigos BCH

Um código BCH C (respectivamente, um código BCH C 0 ) de comprimento n sobre o anel local Zp k (respectivamente, sobre o corpo Zp) é um ideal no anel Zpk [X] (Xn−1) (respectivamente, no anel Zp[X] (Xn−1) ), que ´e gerado por um polinômio mônico que divide Xn−1. Shankar [1] mostrou que as raízes de Xn−1 são as unidades do anel de Galois GR(p k , s) (respectivamente, corpo de Galois GF(p, s)) que é uma extensão do anel Zp k (respectivamente, do corpo Zp), onde s é o grau de um polinômio irredutível f(X) ∈ Zp k [X]. Neste estudo, assumimos que para si = b i , onde b é um primo e i é um inteiro não negativo tal que 0 ≤ i ≤ t, existem extensões de anéis de Galois correspondentes GR(p k , si) (respectivamente, extensões do corpo de Galois GF(p, si)) do anel Zp k (respectivamente, do corpo Zp). Assim, si = b i para i = 2 ou si = b i para i > 2. De modo análogo a [1], neste trabalho, apresentamos uma sequência de códigos BCH C0, C1, · · · , Ct−1C sobre Zp k de comprimentos n0, n1, · · · , nt−1, nt , e uma sequência de códigos BCH C 0 0 , C0 1 , · · · , C0 t−1 , C0 sobre Zp de comprimentos n0, n1, · · · , nt−1, nt , onde cada ni divide p si − 1. Palavras Chave: Anel de Galois, corpo de Galois, código BCH.

Aplicações de ágebra linear aos códigos corretos de erros e ao ensino médio

Pós-graduação em Matemática em Rede Nacional - IBILCE

Implementação de códigos LDPC em OFDM e SC-FDE

Os desenvolvimentos dos sistemas de comunicação sem fios apontam para transmissões de alta velocidade e alta qualidade de serviço com um uso eficiente de energia. Eficiência espectral pode ser obtida por modulações multinível, enquanto que melhorias na eficiência de potência podem ser proporcionadas pelo uso de códigos corretores de erros. Os códigos Low-Density Parity-Check (LDPC), devido ao seu desempenho próximo do limite de Shannon e baixa complexidade na implementação e descodificação são apropriados para futuros sistemas de comunicações sem fios. Por outro lado, o uso de modulações multinível acarreta limitações na amplificação. Contudo, uma amplificação eficiente pode ser assegurada por estruturas de transmissão onde as modulações multinível são decompostas em submodulações com envolvente constante que podem ser amplificadas por amplificadores não lineares a operar na zona de saturação. Neste tipo de estruturas surgem desvios de fase e ganho, produzindo distorções na constelação resultante da soma de todos os sinais amplificados. O trabalho foca-se no uso dos códigos LDPC em esquemas multiportadora e monoportadora, com especial ênfase na performance de uma equalização iterativa implementada no domínio da frequência por um Iterative Block-Decision Feedback Equalizer (IB-DFE). São analisados aspectos como o impacto do número de iterações no processo de descodificação dentro das iterações do processo de equalização. Os códigos LDPC também serão utilizados para compensar os desvios de fase em recetores iterativos para sistemas baseados em transmissores com vários ramos de amplificação. É feito um estudo sobre o modo como estes códigos podem aumentar a tolerância a erros de fase que incluí uma análise da complexidade e um algoritmo para estimação dos desequilíbrios de fase.

Modelos de regressão lineares para estimativa de produtividade da soja no oeste do Paraná, utilizando dados espectrais

The main objective of this work was to evaluate the linear regression between spectral response and soybean yield in regional scale. In this study were monitored 36 municipalities from the west region of the states of Parana using five images of Landsat 5/TM during 2004/05 season. The spectral response was converted in physical values, apparent and surface reflectances, by radiometric transformation and atmospheric corrections and both used to calculate NDVI and GVI vegetation indices. Those ones were compared by multiple and simple regression with government official yield values (IBGE). Diagnostic processing method to identify influents values or collinearity was applied to the data too. The results showed that the mean surface reflectance value from all images was more correlated with yield than individual dates. Further, the multiple regressions using all dates and both vegetation indices gave better results than simple regression.

Medidas lineares dos estágios de desenvolvimento da dentição permanente humana usando Tomografia Computadorizada de Feixe Cônico: um estudo preliminar

OBJETIVO: determinar as medidas lineares dos estágios de desenvolvimento da dentição permanente humana, usando tomografia computadorizada de feixe cônico (TCFC). MÉTODOS: este estudo foi desenvolvido a partir de bancos de dados de clínicas radiológicas privadas, envolvendo 18 pacientes (13 do sexo masculino, 5 do sexo feminino, com idades variando entre 3 e 20 anos). As imagens das TCFC foram obtidas por meio do sistema i-CAT e medidas com uma função específica do programa desse mesmo sistema. Duzentos e trinta e oito dentes foram analisados, em diferentes estágios de desenvolvimento, nos planos coronal e sagital. O método foi baseado na delimitação e mensuração das distâncias entre pontos anatômicos correspondentes ao desenvolvimento das coroas e raízes dentárias. A partir dos valores obtidos, pôde-se desenvolver um modelo quantitativo para se avaliar os estágios inicial e final de desenvolvimento para todos os grupos dentários. RESULTADOS E CONCLUSÕES: as medidas obtidas dos diferentes grupos dentários estão de acordo com as estimativas das investigações publicadas previamente. As imagens por TCFC dos diferentes estágios de desenvolvimento podem contribuir no diagnóstico, planejamento e resultado dos tratamentos em diversas especialidades odontológicas. As dimensões das coroas e das raízes dentárias podem ter importantes aplicações clínicas e em pesquisas, constituindo uma técnica não invasiva que contribui com estudos in vivo. Entretanto, mais estudos são recomendados a fim de minimizar possíveis variáveis metodológicas.

Estimação da área foliar por método não destrutivo, utilizando medidas lineares das folhas de espécies de Passiflora

Objetivou-se, com este trabalho, desenvolver uma equação confiável, que possibilite calcular a área foliar de forma rápida e não destrutiva, utilizando medidas lineares da folha, para as diferentes espécies de Passiflora (P. alata, P. coccinea, P. gibertii, P. ligularis, P. misera, P. mucronata, P. nitida, P. setacea). Foram coletadas trezentas folhas, de diferentes tamanhos, de cada espécie. Realizaram-se análises de regressão da área foliar versus comprimento da nervura principal, maior largura da folha e o produto destas. A área foliar foi medida com um dispositivo de medição automática e as medidas lineares foram determinadas utilizando-se régua. O modelo linear escolhido, para todas as espécies, foi o que utiliza o produto das variáveis independentes, por apresentar maior coeficiente de determinação (R²) e maior significância do coeficiente de regressão. Os modelos apresentaram coeficiente de determinação ajustado superior a 0,927 e índice de desempenho ótimo, segundo a classificação de Camargo e Sentelhas. No processo de validação do modelo, mostrou-se que a correlação da área foliar medida com a área foliar observada foi muito alta. Os resultados obtidos neste estudo demonstram que a área foliar das espécies de Passifloras podem ser preditas, usando-se as determinações do comprimento e da largura das folhas.

Comunicações Não-coerentes em Sistemas MIMO: Desenho do Receptor e Construção de Códigos

Este trabalho aborda o problema do desenho de códigos espácio-temporais para sistemas de comunicação multiple-input multiple-output (MIMO) sem fios. Considera-se o contexto realista e desafiante da recepção não-coerente (a realização do canal é desconhecida no receptor). O detector conhecido como generalized likelihood ratio test (GLRT)é implementado no receptor e, ao contrário da maioria das abordagens actuais, permite-se uma estrutura de correlação arbitrária para o ruído gaussiano de observação. Apresenta-se uma análise teórica para a probabilidade de erro do detector, em ambos os regimes assimptóticos de relação sinal-ruído (SNR) alta e baixa. Essa análise conduz a um critério de optimalidade para desenho de códigos e permite uma re-interpretação geométrica do problema abordado como um problema de empacotamento óptimo num producto Cartesiano de espaço projectivos. A construção dos códigos implica a resolução de um problema de optimização não-linear, não-diferenciável e de dimensão elevada, o qual foi abordado aqui em duas fases. A primeira fase explora uma relaxação convexa do problema original para obter uma estimativa inicial. A segunda fase, refina essa estimativa através de um algoritmo iterativo de descida do gradiente ao longo de geodésicas, explorando-se assim a geometria Riemanniana imposta pelas restricões de potência sobre os códigos espáciotemporais. Mostra-se que o desempenho dos novos códigos obtidos por este método excede o das soluções previamente conhecidas. De facto, para algumas configurações particulares, estas novas constelações atingem o limiar de Rankin e são por isso garantidamente óptimas.

Dos códigos de barras aos códigos bidimensionais de resposta rápida

Os códigos de barras são exemplos de sistemas de identificação com algarismo de controlo, que tem como objetivo verificar se foi cometido pelo menos um erro de escrita, leitura ou transmissão da informação. Nos códigos de barras, o algarismo de controlo é o algarismo das unidades (primeiro algarismo da direita). Os restantes algarismos de um código de barras contêm informação específica. Por exemplo, os três primeiros algarismos da esquerda identificam sempre o país de origem (com a exceção dos códigos de barras dos livros, que apresentam o prefixo 978 ou 979, e dos códigos de uso interno das superfícies comerciais como, por exemplo, para os artigos embalados na padaria ou na peixaria de um supermercado, que começam por 2). Seguem-se alguns exemplos: 300-379 (França e Mónaco); 400-440 (Alemanha); 500-509 (Reino Unido); 520 (Grécia); 539 (Irlanda); 540-549 (Bélgica e Luxemburgo); 560 (Portugal); 690-695 (China); 760-769 (Suíça); 789-790 (Brasil); 840-849 (Espanha e Andorra); 888 (Singapura); 958 (Macau). Observe-se que os países com uma maior produção têm à sua disposição mais de um prefixo de três algarismos. (...) Para se verificar se o número do código de barras está correto, procede-se da seguinte forma (...) obtêm-se, respetivamente, as somas I e P; por fim, calcula-se o valor de S=I+3xP que deverá ser um múltiplo de 10 (ou seja, o seu algarismo das unidades deverá ser 0). (...) E que relação existe entre as barras e os algarismos? Ao olhar com atenção para um código de barras EAN-13, reparamos que os 13 algarismos são distribuídos da seguinte forma: o primeiro algarismo surge isolado à esquerda das barras, enquanto que os restantes surgem por baixo destas, divididos em dois grupos de seis algarismos separados por barras geralmente mais compridas do que as restantes: três barras nas laterais (preto-branco-preto) e cinco barras ao centro (branco-preto-branco-preto-branco). As restantes barras são mais curtas e codificam os 12 algarismos (indiretamente, também codificam o algarismo da esquerda). (...) A representação dos algarismos por barras brancas e pretas respeita alguns princípios como os de paridade e simetria, pelo que um algarismo não é sempre representado da mesma forma. Este aspeto permite que um código de barras possa ser lido por um leitor ótico sem qualquer ambiguidade, quer esteja na posição normal ou "de pernas para o ar". (...) Recentemente surgiu uma nova geração de códigos de barras designados por códigos de resposta rápida ou códigos QR (do inglês Quick Response). Certamente o leitor já os viu em cartazes publicitários ou em revistas. (...)

Proposta de metodologia usando regressões lineares no cálculo dos efeitos vibratórios do rebentamento de explosivos

Este trabalho apresenta o estudo das leis de propagação das velocidades de vibração resultantes do uso de explosivo em diferentes maciços. Foram efectuados estudos para três tipos de maciços diferentes, granito, quartzito e calcário. Efectuaram-se campanhas de monitorização e registo dos dados em cada uma das situações. Caracterizando e utilizando duas leis de propagação de velocidades no maciço, a de Johnson e Langefors, calculou-se as suas variáveis por método estatístico de regressões lineares múltiplas. Com a obtenção das variáveis fizeram-se estudos de previsão dos valores de vibração a obter utilizando a carga explosiva aplicada nos desmontes. Através dos valores de vibração obtidos em cada pega de fogo para cada tipo de maciço comparou-se quais das duas leis apresentam o valor de velocidade de vibração menor desviado do real. Conforme ficou verificado neste estudo, a equação de Langefors garante uma mais-valia da sua aplicação na previsão das velocidades de vibração pois joga favoravelmente a nível da segurança assim como apresenta um menor desvio face à equação de Johnson quando comparada com o valor real de vibração obtido. Com isto o método de utilização de regressões lineares múltiplas como cálculo dos efeitos vibratórios é extremamente vantajoso a nível de prevenção de danos e cálculo de velocidades de vibração inferiores ao imposto pela Norma.

Robôs quadrúpedes: geração de trajectórias em tempo real usando sistemas dinâmicos não-lineares

A geração de trajectórias de robôs em tempo real é uma tarefa muito complexa, não existindo ainda um algoritmo que a permita resolver de forma eficaz. De facto, há controladores eficientes para trajectórias previamente definidas, todavia, a adaptação a variações imprevisíveis, como sendo terrenos irregulares ou obstáculos, constitui ainda um problema em aberto na geração de trajectórias em tempo real de robôs. Neste trabalho apresentam-se modelos de geradores centrais de padrões de locomoção (CPGs), inspirados na biologia, que geram os ritmos locomotores num robô quadrúpede. Os CPGs são modelados matematicamente por sistemas acoplados de células (ou neurónios), sendo a dinâmica de cada célula dada por um sistema de equações diferenciais ordinárias não lineares. Assume-se que as trajectórias dos robôs são constituídas por esta parte rítmica e por uma parte discreta. A parte discreta pode ser embebida na parte rítmica, (a.1) como um offset ou (a.2) adicionada às expressões rítmicas, ou (b) pode ser calculada independentemente e adicionada exactamente antes do envio dos sinais para as articulações do robô. A parte discreta permite inserir no passo locomotor uma perturbação, que poderá estar associada à locomoção em terrenos irregulares ou à existência de obstáculos na trajectória do robô. Para se proceder á análise do sistema com parte discreta, será variado o parâmetro g. O parâmetro g, presente nas equações da parte discreta, representa o offset do sinal após a inclusão da parte discreta. Revê-se a teoria de bifurcação e simetria que permite a classificação das soluções periódicas produzidas pelos modelos de CPGs com passos locomotores quadrúpedes. Nas simulações numéricas, usam-se as equações de Morris-Lecar e o oscilador de Hopf como modelos da dinâmica interna de cada célula para a parte rítmica. A parte discreta é modelada por um sistema inspirado no modelo VITE. Medem-se a amplitude e a frequência de dois passos locomotores para variação do parâmetro g, no intervalo [-5;5]. Consideram-se duas formas distintas de incluir a parte discreta na parte rítmica: (a) como um (a.1) offset ou (a.2) somada nas expressões que modelam a parte rítmica, e (b) somada ao sinal da parte rítmica antes de ser enviado às articulações do robô. No caso (a.1), considerando o oscilador de Hopf como dinâmica interna das células, verifica-se que a amplitude e frequência se mantêm constantes para -50.2. A extensão do movimento varia de forma directamente proporcional à amplitude. No caso das equações de Morris-Lecar, quando a componente discreta é embebida (a.2), a amplitude e a frequência aumentam e depois diminuem para - 0.170.5 Pode concluir-se que: (1) a melhor forma de inserção da parte discreta que menos perturbação insere no robô é a inserção como offset; (2) a inserção da parte discreta parece ser independente do sistema de equações diferenciais ordinárias que modelam a dinâmica interna de cada célula. Como trabalho futuro, é importante prosseguir o estudo das diferentes formas de inserção da parte discreta na parte rítmica do movimento, para que se possa gerar uma locomoção quadrúpede, robusta, flexível, com objectivos, em terrenos irregulares, modelada por correcções discretas aos padrões rítmicos.

Deteção automática de incêndios. Detetores lineares de calor e de fumos

Existem situações particulares de deteção de incêndio nas quais os tradicionais detetores pontuais de fumo e calor podem não ser a solução mais adequada. São exemplo destas situações, a proteção de grandes áreas e/ou grandes distâncias. Nestas situações, poder-se-á equacionar a utilização de detetores lineares de calor e de fumos.

Problemas de programação matemática com restrições lineares de equilíbrio

Neste trabalho é desenvolvido um algoritmo enumerativo paramétrico de optimização global para a resolução de Problemas de Programação Matemática com Restrições de Equilíbrio ou de Complementaridade (MPEC). A comparação com outras técnicas globais da literatura é efectuada para um leque variado de problemas, de modo a poder avaliar a eficiência do processo proposto. A utilização de algoritmos de MPEC para a resolução de alguns problemas de optimização global é o outro grande objectivo desta tese. Nesse sentido são introduzidas novas formula¸c˜oes de programas bilineares e lineares complementares como MPECs. São ainda analisadas e discutidas formulaçõess MPEC para o problema de programação linear inteira 0-1, para a determinação do Conjunto Independente Máximo de um Grafo (MIS) e para a estimação do Número de Condição de uma Matriz. Para o problema MIS é desenvolvido um algoritmo de ramificação e limitação, baseado na decomposição de uma função quadrática numa diferença de duas funçõess convexas (DC). Finalmente é introduzida uma técnica MPEC local para a estimação do número de condição com a norma l1 e é estabelecido para matrizes de Minkowski que o número de condição nessa norma pode ser estimado com apenas um sistema de equações lineares. Em todos os desenvolvimentos houve uma grande preocupação em testar as novas formulações e algoritmos com problemas conhecidos da literatura, de modo a aferir da qualidade e interesse dessas propostas.