No description available.

Orientadores: Jaime Portugheis, Celso de Almeida / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-26T15:56:15Z (GMT). No. of bitstreams: 1 Santos_LailsonFerreirados_M.pdf: 1842807 bytes, checksum: dc8a5492d7e9a3e4224974176413f42c (MD5) Previous issue date: 2014 / Resumo: Esta dissertação analisa decodificadores LDPC (do inglês, Low-Density Parity-Check) sobre GF(q) de baixa complexidade num canal AWGN de entrada binária. É realizada uma revisão bibliográfica dos algoritmos binários baseados na técnica bit-flipping e seus desempenhos são comparados. As principais contribuições deste trabalho estão relacionadas com a investigação do algoritmo de decodificação WSF (do inglês, Weighted Symbol-Flipping} para códigos LDPC não binários. O algoritmo WSF é composto por duas partes: função de troca e regra de seleção do novo símbolo candidato. Primeiramente, é demonstrado que a regra de seleção do novo símbolo candidato baseada nos valores absolutos das saídas do canal observado, é equivalente a uma baseada em distâncias euclidianas. Também é verificado que a variação do valor do fator peso do algoritmo WSF sem o mecanismo de detecção de laços infinitos, não influencia no desempenho do decodificador, podendo ser ignorado. E por final, é proposto um algoritmo SF (do inglês, Symbol-Flipping) para códigos LDPC não binários, sendo que a função de troca é baseada apenas nos valores inteiros das síndromes e troca múltiplos bits em paralelo. O algoritmo SF obteve um melhor desempenho do que WSF para ordem do campo de Galois grandes / Abstract: This dissertation analyzes low complexity decoding algorithms for low-density parity-check (LDPC) codes over GF(q) in a binary input AWGN (BI-AWGN) channel. A literature review of binary algorithms based on bit-flipping techniques is presented and their performances are compared. The main contributions of this dissertation is associated with the investigation about weighted symbol-flipping (SF) algorithm for nonbinary LDPC codes. The weighted SF algorithm has two main parts: the symbol-flipping function and the new candidate symbol rule. First, it is demonstrated that a rule for choosing the new candidate symbol based on absolute values of observed channel outputs is equivalent to a rule based on Euclidean distances. Then, it is verified that the weighting factor of flipping function has negligible impact on algorithm performance. Motivated by this fact, a SF decoding algorithm is proposed whose flipping function requires only syndrome values and flips symbols in parallel. It is observed that SF decoding outperforms WSF for q-ary codes with large q / Mestrado / Telecomunicações e Telemática / Mestre em Engenharia Elétrica

Orientador: Tomasz Kowaltowski / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-16T09:36:09Z (GMT). No. of bitstreams: 1 Silva_HeloisaVieiradaRochaCorrea_M.pdf: 3970508 bytes, checksum: b82f5b6dcbc566239038e2563432a626 (MD5) Previous issue date: 1981 / Resumo: O trabalho aqui apresentado é um estudo de métodos de recuperação de erros no processo de compilação, aplicáveis à analisadores descendentes para linguagens do tipo LL. Inicialmente faz-se uma exposição sobre o processo de compilação e possíveis fontes de erro. Está incluída também uma indicação sucinta dos métodos de recuperação para erros léxicos e dos métodos aplicáveis à analisadores ascendentes. Segue um resumo sobre a implementação de análise descendente e a descrição de vários métodos de recuperação aplicáveis a este tipo de análise. Finalmente, apresentam-se os resultados experimentais da implementação de alguns destes métodos para a linguagem pascal. Chega-se à conclusão de que nenhum desses métodos apresenta comportamento satisfatório em todas as situações, mas alguns parecem ter desempenho geral melhor do que outros. / Abstract: We present in this thesis a survey of compiling error recovery methods applicable to top-down parse for LL languages. First we describe the compilation process and possible sources of errors. We also include a short description of recovery methods for lexical errors, and of methods applicable to bottom-up parsers. Next we describe the implementation of top-bottom parsers, and of several recovery methods applicable to this kind of parsing. Finally we show the experimental results of implementing some of these methods for the Pascal language. Our conclusion is that none of these methods is satisfactory in all circumstances, but some of them seem to perform in general better than others. / Mestrado / Mestre em Ciência da Computação

Orientador: Celso de Almeida / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica / Made available in DSpace on 2018-07-18T11:56:22Z (GMT). No. of bitstreams: 1 Fernandes_VirginiaPereira_M.pdf: 3904812 bytes, checksum: 969c76bb2dffede349e22f2eb7aa52f7 (MD5) Previous issue date: 1993 / Resumo: o trabalho apresenta uma introdução a sistemas de gravação de dados. Estudamos com ênfase a importância do emprego de códigos de linha em sistemas de gravação de dados. Tais códigos são responsáveis pela diminuição da interferência inter-simbólica, auxiliam na recuperação do sincronismo, além de adequar o espectro do sinal às exigências do canal, e ainda proporcionam aumento da densidade de armazenamento de dados. Finalmente, tratamos de sistemas na presença de ruído. Deste modo, mencionamos a necessidade do uso dos códigos corretores de erro, a fim de corrigir os erros provocados pelos ruídos do canal, ou de regiões defeituosas no prório meio de gravação. Assim, podemos obter um armazenamento confiável de dados / Abstract: Not informed. / Mestrado / Mestre em Engenharia Elétrica

Orientador: Helio Waldman / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de engenharia Eletrica / Made available in DSpace on 2018-07-18T16:40:06Z (GMT). No. of bitstreams: 1 Nisenbaum_Eduardo_D.pdf: 6187106 bytes, checksum: c37c2d1433a225ce152c9c85f4fba14d (MD5) Previous issue date: 1993 / Resumo: Nesse trabalho faz-se a investigação de códigos binários que reunem restrições de distância mínima e nulo espectral no DC simultaneamente, aqui chamados de Códigos de linha com controle de erros (CLCEs). Começamos pela busca computacional de códigos de bloco monoalfabéticos e bialfabéticos (Cap. 2). Em seguida investigamos centros e tamanhos de esferas extremas de Hamming no espaço DC restrito com fins de obter limitantes superiores e inferiores para a Taxa x distância mínima relativa (Cap. 3). O capítulo 4 mostra algumas técnicas construtivas para CLCEs que são implementáveis na prática. Por fim , no capítulo 5, fazemos uma análise de desempenho desses códigos num sistema exemplo: Sistema de comunicações óticas de deteção direta / Abstract: Not informed. / Doutorado / Doutor em Engenharia Elétrica

[EN] This thesis studies the design of low-complexity soft-decision Non-Binary Low-Density Parity-Check (NB-LDPC) decoding algorithms and their corresponding hardware architectures suitable for decoding high-rate codes at high throughput (hundreds of Mbps and Gbps). In the first part of the thesis the main aspects concerning to the NB-LDPC codes are analyzed, including a study of the main bottlenecks of conventional softdecision decoding algorithms (Q-ary Sum of Products (QSPA), Extended Min-Sum (EMS), Min-Max and Trellis-Extended Min-Sum (T-EMS)) and their corresponding hardware architectures. Despite the limitations of T-EMS algorithm (high complexity in the Check Node (CN) processor, wiring congestion due to the high number of exchanged messages between processors and the inability to implement decoders over high-order Galois fields due to the high decoder complexity), it was selected as starting point for this thesis due to its capability to reach high-throughput. Taking into account the identified limitations of the T-EMS algorithm, the second part of the thesis includes six papers with the results of the research made in order to mitigate the T-EMS disadvantages, offering solutions that reduce the area, the latency and increase the throughput compared to previous proposals from literature without sacrificing coding gain. Specifically, five low-complexity decoding algorithms are proposed, which introduce simplifications in different parts of the decoding process. Besides, five complete decoder architectures are designed and implemented on a 90nm Complementary Metal-Oxide-Semiconductor (CMOS) technology. The results show an achievement in throughput higher than 1Gbps and an area less than 10 mm2. The increase in throughput is 120% and the reduction in area is 53% compared to previous implementations of T-EMS, for the (837,726) NB-LDPC code over GF(32). The proposed decoders reduce the CN area, latency, wiring between CN and Variable Node (VN) processor and the number of storage elements required in the decoder. Considering that these proposals improve both area and speed, the efficiency parameter (Mbps / Million NAND gates) is increased in almost five times compared to other proposals from literature. The improvements in terms of area allow us to implement NB-LDPC decoders over high-order fields which had not been possible until now due to the highcomplexity of decoders previously proposed in literature. Therefore, we present the first post-place and route report for high-rate codes over high-order fields higher than Galois Field (GF)(32). For example, for the (1536,1344) NB-LDPC code over GF(64) the throughput is 1259Mbps occupying an area of 28.90 mm2. On the other hand, a decoder architecture is implemented on a Field Programmable Gate Array (FPGA) device achieving 630 Mbps for the high-rate (2304,2048) NB-LDPC code over GF(16). To the best knowledge of the author, these results constitute the highest ones presented in literature for similar codes and implemented on the same technologies. / [ES] En esta tesis se aborda el estudio del diseño de algoritmos de baja complejidad para la decodificación de códigos de comprobación de paridad de baja densidad no binarios (NB-LDPC) y sus correspondientes arquitecturas apropiadas para decodificar códigos de alta tasa a altas velocidades (cientos de Mbps y Gbps). En la primera parte de la tesis los principales aspectos concernientes a los códigos NB-LDPC son analizados, incluyendo un estudio de los principales cuellos de botella presentes en los algoritmos de decodificación convencionales basados en decisión blanda (QSPA, EMS, Min-Max y T-EMS) y sus correspondientes arquitecturas hardware. A pesar de las limitaciones del algoritmo T-EMS (alta complejidad en el procesador del nodo de chequeo de paridad (CN), congestión en el rutado debido al intercambio de mensajes entre procesadores y la incapacidad de implementar decodificadores para campos de Galois de orden elevado debido a la elevada complejidad), éste fue seleccionado como punto de partida para esta tesis debido a su capacidad para alcanzar altas velocidades. Tomando en cuenta las limitaciones identificadas en el algoritmo T-EMS, la segunda parte de la tesis incluye seis artículos con los resultados de la investigación realizada con la finalidad de mitigar las desventajas del algoritmo T-EMS, ofreciendo soluciones que reducen el área, la latencia e incrementando la velocidad comparado con propuestas previas de la literatura sin sacrificar la ganancia de codificación. Especificamente, cinco algoritmos de decodificación de baja complejidad han sido propuestos, introduciendo simplificaciones en diferentes partes del proceso de decodificación. Además, arquitecturas completas de decodificadores han sido diseñadas e implementadas en una tecnologia CMOS de 90nm consiguiéndose una velocidad mayor a 1Gbps con un área menor a 10 mm2, aumentando la velocidad en 120% y reduciendo el área en 53% comparado con previas implementaciones del algoritmo T-EMS para el código (837,726) implementado sobre campo de Galois GF(32). Las arquitecturas propuestas reducen el área del CN, latencia, número de mensajes intercambiados entre el nodo de comprobación de paridad (CN) y el nodo variable (VN) y el número de elementos de almacenamiento en el decodificador. Considerando que estas propuestas mejoran tanto el área comola velocidad, el parámetro de eficiencia (Mbps / Millones de puertas NAND) se ha incrementado en casi cinco veces comparado con otras propuestas de la literatura. Las mejoras en términos de área nos ha permitido implementar decodificadores NBLDPC sobre campos de Galois de orden elevado, lo cual no habia sido posible hasta ahora debido a la alta complejidad de los decodificadores anteriormente propuestos en la literatura. Por lo tanto, en esta tesis se presentan los primeros resultados incluyendo el emplazamiento y rutado para códigos de alta tasa sobre campos finitos de orden mayor a GF(32). Por ejemplo, para el código (1536,1344) sobre GF(64) la velocidad es 1259 Mbps ocupando un área de 28.90 mm2. Por otro lado, una arquitectura de decodificador ha sido implementada en un dispositivo FPGA consiguiendo 660 Mbps de velocidad para el código de alta tasa (2304,2048) sobre GF(16). Estos resultados constituyen, según el mejor conocimiento del autor, los mayores presentados en la literatura para códigos similares implementados para las mismas tecnologías. / [CAT] En esta tesi s'aborda l'estudi del disseny d'algoritmes de baixa complexitat per a la descodificació de codis de comprovació de paritat de baixa densitat no binaris (NB-LDPC), i les seues corresponents arquitectures per a descodificar codis d'alta taxa a altes velocitats (centenars de Mbps i Gbps). En la primera part de la tesi els principals aspectes concernent als codis NBLDPC són analitzats, incloent un estudi dels principals colls de botella presents en els algoritmes de descodificació convencionals basats en decisió blana (QSPA, EMS, Min-Max i T-EMS) i les seues corresponents arquitectures. A pesar de les limitacions de l'algoritme T-EMS (alta complexitat en el processador del node de revisió de paritat (CN), congestió en el rutat a causa de l'intercanvi de missatges entre processadors i la incapacitat d'implementar descodificadors per a camps de Galois d'orde elevat a causa de l'elevada complexitat), este va ser seleccionat com a punt de partida per a esta tesi degut a la seua capacitat per a aconseguir altes velocitats. Tenint en compte les limitacions identificades en l'algoritme T-EMS, la segona part de la tesi inclou sis articles amb els resultats de la investigació realitzada amb la finalitat de mitigar els desavantatges de l'algoritme T-EMS, oferint solucions que redueixen l'àrea, la latència i incrementant la velocitat comparat amb propostes prèvies de la literatura sense sacrificar el guany de codificació. Específicament, s'han proposat cinc algoritmes de descodificació de baixa complexitat, introduint simplificacions en diferents parts del procés de descodificació. A més, s'han dissenyat arquitectures completes de descodificadors i s'han implementat en una tecnologia CMOS de 90nm aconseguint-se una velocitat major a 1Gbps amb una àrea menor a 10 mm2, augmentant la velocitat en 120% i reduint l'àrea en 53% comparat amb prèvies implementacions de l'algoritme T-EMS per al codi (837,726) implementat sobre camp de Galois GF(32). Les arquitectures proposades redueixen l'àrea del CN, la latència, el nombre de missatges intercanviats entre el node de comprovació de paritat (CN) i el node variable (VN) i el nombre d'elements d'emmagatzemament en el descodificador. Considerant que estes propostes milloren tant l'àrea com la velocitat, el paràmetre d'eficiència (Mbps / Milions deportes NAND) s'ha incrementat en quasi cinc vegades comparat amb altres propostes de la literatura. Les millores en termes d'àrea ens ha permès implementar descodificadors NBLDPC sobre camps de Galois d'orde elevat, la qual cosa no havia sigut possible fins ara a causa de l'alta complexitat dels descodificadors anteriorment proposats en la literatura. Per tant, nosaltres presentem els primers reports després de l'emplaçament i rutat per a codis d'alta taxa sobre camps finits d'orde major a GF(32). Per exemple, per al codi (1536,1344) sobre GF(64) la velocitat és 1259 Mbps ocupant una àrea de 28.90 mm2. D'altra banda, una arquitectura de descodificador ha sigut implementada en un dispositiu FPGA aconseguint 660 Mbps de velocitat per al codi d'alta taxa (2304,2048) sobre GF(16). Estos resultats constitueixen, per al millor coneixement de l'autor, els millors presentats en la literatura per a codis semblants implementats per a les mateixes tecnologies. / Lacruz Jucht, JO. (2016). VLSI algorithms and architectures for non-binary-LDPC decoding [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/73266 / TESIS

Este trabalho, elaborado por meio de pesquisa bibliográfica, apresenta um apanhado sobre os dígitos verificadores presentes no Cadastro de Pessoas Físicas (CPF), no código de barras, e no sistema ISBN; faz uma introdução sobre a métrica de Hamming e os códigos corretores de erros; cita a classe de códigos mais utilizada, que são os códigos lineares, e deixa a sugestão de uma proposta pedagógica para professores de matemática aplicarem no Ensino Fundamental, podendo ser ajustada também para o Ensino Médio. No apêndice A, são propostos alguns exercícios que podem ser trabalhados com os alunos em sala de aula. / This work, based on the attached references, presents an overview of the check digits that appear in the Brazilian document CPF, in the bar code and the ISBN system. Moreover, it makes an introduction to the Hamming metric and error-correcting codes. In particular, some considerations about linear codes are done and it makes a suggestion of a pedagogical approach to apply it in middle school and can also be adjusted to high school. In the Appendix A are proposed some exercises to students.

Orientador: Edson Ryoji Okamoto Iwaki / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Matemática Aplicada, 2013

Submitted by camilla martins (camillasmmartins@gmail.com) on 2017-04-24T11:48:05Z No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Tese_CorrecaoApagamentosRajadas.pdf: 12648601 bytes, checksum: 32c72b34186616144110cb119cba02b1 (MD5) / Approved for entry into archive by Edisangela Bastos (edisangela@ufpa.br) on 2017-04-24T16:57:51Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Tese_CorrecaoApagamentosRajadas.pdf: 12648601 bytes, checksum: 32c72b34186616144110cb119cba02b1 (MD5) / Made available in DSpace on 2017-04-24T16:57:51Z (GMT). No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Tese_CorrecaoApagamentosRajadas.pdf: 12648601 bytes, checksum: 32c72b34186616144110cb119cba02b1 (MD5) Previous issue date: 2016-10-21 / Nesta tese são propostos procedimentos para a construção de matrizes de verificação de paridade para codificação e decodificação de códigos LDPC (low-density paritycheck) na recuperação de bits apagados no canal com apagamentos em rajada. As matrizes de verificação de paridade são produzidas por concatenação das matrizes bases binárias justapostas por matrizes circulantes sendo de fácil implementação e de menor aleatoriedade. As matrizes bases são desenvolvidas a partir de fundamentos da álgebra e da geometria. Para demonstrar o potencial da técnica foi elaborado um conjunto de simulações que usa codificação de baixa complexidade, bem como o uso dos algoritmos soma e produto para recuperar os apagamentos. Foram gerados vários códigos LDPC, a partir das matrizes, e os resultados obtidos foram comparados com outros códigos LDPC obtidos da literatura. São ainda apresentados os resultados da simulação da recuperação de apagamentos resultantes da transmissão de uma imagem através de um canal ruidoso.partir das matrizes, e os resultados obtidos foram comparados com outros códigos LDPC obtidos da literatura. São ainda apresentados os resultados da simulação da recuperação de apagamentos resultantes da transmissão de uma imagem através de um canal ruidoso. / This thesis proposed procedures for the construction of parity check matrices for encoding and decoding of LDPC codes in the recovery of deleted bits in Burst Erasure Channel. The parity check matrices are produced by concatenation of binary bases matrices juxtaposed by circulating matrices are easy to implement and lower randomness. The base arrays are developed from the foundations of algebra and geometry. To demonstrate the potential of the technique, we developed a number of simulations using low complexity encoding as well as the sum-product algorithm. Several LDPC codes (matrices) were generated and the results were compared with other approaches. We also present the outcomes of erasure recovery simulations that result from the transmission of an image through a noisy channel.

Neste trabalho, usamos uma abordagem de anéis de grupo para caracterizar códigos cíclicos sobre anéis de cadeia, seus duais e algumas condições sobre códigos auto-duais. Caracterizamos também os códigos cíclicos livres sobre anéis de cadeia e por fim exibimos uma fórmula para o peso de qualquer código cíclico sobre anéis de cadeia de comprimento e p^n 2p^n. / In this thesis, we use an approach of group rings to characterize cyclic codes over chain rings, their duals and some conditions on self-dual codes. It also features free cyclic codes over chain rings and finally we show a formula for the weight of any cyclic code over chain rings of length p^n and 2p^n.