Recent attempts to increase the capacity of the compact disc (CD) and digital versatile disc (DVD) have explored the use of multilevel recording instead of binary recording. Systems that achieve an increase in capacity of about three times that of conventional CD have been proposed for production. Marks in these systems are multilevel and fixed-length as opposed to binary and variable length in CD and DVD. The main objective of this work is to evaluate the performance of multilevel ($M$-ary) runlength-limited (RLL) coded sequences in optical data storage. First, the waterfilling capacity of a multilevel optical recording channel ($M$-ary ORC) is derived and evaluated. This provides insight into the achievable user bit densities, as well as a theoretical limit against which simulated systems can be compared. Then, we evaluate the performance of RLL codes on the $M$-ary ORC. A new channel model that includes the runlength constraint in the transmitted signal is used. We compare the performance of specific RLL codes, namely $M$-ary permutation codes, to that of real systems using multilevel fixed-length marks for recording and the theoretical limits. The Viterbi detector is used to estimate the original recorded symbols from the readout signal. Then, error correction is used to reduce the symbol error probability. We use a combined ECC/RLL code for phrase encoding. We evaluate the use of trellis coded modulation (TCM) for amplitude encoding. The detection of the readout signal is also studied. A post-processing algorithm for the Viterbi detector is introduced, which ensures that the detected word satisfies the code constraints. Specifying the codes and detector for the $M$-ary ORC gives a complete system whose performance can be compared to that of the recently developed systems found in the literature and the theoretical limits calculated in this research.

ITC/USA 2013 Conference Proceedings / The Forty-Ninth Annual International Telemetering Conference and Technical Exhibition / October 21-24, 2013 / Bally's Hotel & Convention Center, Las Vegas, NV / Constrained codes also known as modulation codes are a key component in the digital magnetic recording systems. The constrained codes forbid particular input data patterns which lead to some of the dominant error events or higher media noise. In data recording systems, a concatenated approach toward the constrained code and error-correcting code (ECC) is typically used and the decoding is done independently. In this paper, we show the improvement in combining the decoding of the constrained code and the ECC using generalized belief propagation (GBP) algorithm. We consider the performance of a combined modulation constraints and the ECC on a binary symmetric channel (BSC). We show that combining demodulation and decoding results in a superior performance compared to concatenated schemes. Furthermore, we compute the capacity of the joint ECC and modulation codes for 1-D and 2-D constraints.

Orientador: Renato Baldini Filho / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-17T02:17:07Z (GMT). No. of bitstreams: 1 Goncalves_MariaLeopoldinaMartinsNevesSeixas_M.pdf: 2201748 bytes, checksum: 3f3d1f237a11eabcf9d6c393f0ca0cce (MD5) Previous issue date: 2010 / Resumo: Esta dissertação aborda o estudo de códigos corretores de erro baseados em matrizes quaternárias esparsas, aplicadas em sistemas de transmissão OFDM. Os códigos LDPC (Low Density Parity Check) constituem uma importante família de códigos gerados a partir de matrizes de verificação esparsas e são considerados como uma das classes de códigos que apresentam melhor desempenho em sistemas de comunicação digital. Os códigos LDPC desenvolvidos sobre o anel Z4 são o grande foco deste trabalho e para efeito de comparação de desempenho é utilizado como referência o padrão proposto pelo SBTVD (Sistema Brasileiro de Televisão Digital). No sistema de TV Digital, o receptor deve ser robusto a vários tipos de canal. Para uma recepção fixa o canal pode ser influenciado pelo ruído AWGN (Aditive White Gaussian Noise), já para uma recepção móvel o sinal pode sofrer várias reflexões e refrações, o que é caracterizado pelas interferências do desvanecimento plano e/ou seletivo. Para minimizar este problema é proposto a utilização da técnica de transmissão OFDM (Orthogonal Frequency Division Multiplexing), devido às suas vantagens com canais seletivos em frequência, como é comumente observado nos canais dos sistemas de comunicações móveis digitais. A decodificação dos códigos é feita utilizando uma adaptação (generalização) do algoritmo SISO (Soft Input Soft Output) proposto por P. Farrell e J. Moreira [39], [5]. É feita uma análise comparativa dos códigos do ponto de vista do desempenho, através de simulação de códigos de diferentes comprimentos para cada um dos três canais descritos acima. Os códigos LDPC definidos sobre Z4 apresentam bom desempenho e demonstram ser bons candidatos a sua utilização em conjunto com sistemas OFDM / Abstract: This dissertation addresses the study of error correcting codes based on sparse non-binary matrices. The LDPC (Low Density Parity Check) codes constitute a efficient family of codes generated by sparse parity check matrices and it is considered as one of the classes of codes that presents the best performance in digital communications systems. LDPC codes over the ring of integers modulo-4 (Z4) are the main focus of this work. The standard proposed by SBTVD (Brazilian Digital Television System) is used as reference for performance comparisons. It is proposed the substitution of the inner code in the channel encoding at the transmitter, for a LDPC code. On Digital TV system, the receiver must be robust to some kinds of interferences. For a fixed channel, the receiving end is basically influenced by the AWGN (Additive White Gaussian Noise). For mobile channels, the signal suffers reflections and refractions, which can be characterized as flat and frequency-selective fading. To minimize those interferences it is proposed the associated use of the OFDM (Orthogonal Frequency Division Multiplexing) technique. The decoding process is based on a generalization of the SISO (Soft Input Soft Output) algorithm proposed by P. Farrell and J. Moreira [39], [5]. A comparative analysis of the LDPC codes is made based on BER performance and on computational complexity. Finally, the simulation results for different codes lengths are presented, highlighted the significantive improvement in performance for LDPC codes / Mestrado / Telecomunicações e Telemática / Mestre em Engenharia Elétrica

Orientadores: Reginaldo Palazzo Junior, Carlile Campos Lavor / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-11T22:44:54Z (GMT). No. of bitstreams: 1 LaGuardia_GiulianoGadioli_D.pdf: 1126065 bytes, checksum: c3ad65915db4e87e1752adbbbbef2841 (MD5) Previous issue date: 2008 / Resumo: Como principais contribuições desta tese, apresentamos novos métodos de construção que geram novas famílias de códigos quânticos CSS. As construções são baseadas em códigos cíclicos (clássicos) BCH, Reed-Solomon, Reed-Muller, Resíduos quadráticos e também nos códigos derivados do produto tensorial de dois códigos Reed-Solomon. Os principais códigos quânticos construídos neste trabalho, em termos de parâmetros, são os derivados dos códigos BCH clássicos. Além disso, estudamos as condições necessárias para analisar as situações nas quais os códigos cíclicos quânticos (clássicos) são códigos MDS (do inglês, Maximum- Distance-Separable codes). Apresentamos, também, novas conexões entre a teoria de matróides e a teoria dos códigos quânticos CSS, que acreditamos serem as primeiras conexões entre tais teorias. Mais especificamente, demonstramos que a função enumeradora de pesos de um código quântico CSS é uma avaliação do polinômio de Tutte da soma direta dos matróides originados a partir dos códigos clássicos utilizados na construção CSS. / Abstract: This thesis proposes, as the main contributions, constructions method of new families of quantum CSS codes. These constructions are based on classical cyclic codes of the types BCH, Reed-Solomon, Reed-Muller, Quadratic Residue and also are based on product codes of classical Reed-Solomon codes. The main family of quantum codes constructed in this work, i. e., quantum codes having better parameters, are the ones derived from classical BCH codes. Moreover, we present some new conditions in which quantum CSS cyclic codes are quantumMDS codes. In addition, we provide the elements to connect matroid theory and quantum coding theory. More specifically, we show that the weight enumerator of a CSS quantum code is equivalent to evaluating the Tutte polynomial of the direct sum of the matroid associated to the classical codes used in the CSS construction. / Doutorado / Telecomunicações e Telemática / Doutor em Engenharia Elétrica

Orientador: Jaime Portugheis / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-18T15:49:19Z (GMT). No. of bitstreams: 1 PujaicoRivera_Fernando_M.pdf: 2105653 bytes, checksum: f62384ffbf5226353eba3406ba7735b8 (MD5) Previous issue date: 2011 / Resumo: Desde que Gallager introduziu o algoritmo de decodificação Bit-Flipping (BF) com decisão abrupta para códigos Low Density Parity Check (LDPC), outras duas variantes foram propostas por Sipser e Spielman para os códigos conhecidos como "Expander Codes". Posteriormente, uma versão da decodificação BF por decisão suave conhecida como decodificação Modified Weighted BF (MWBF), foi investigada. Esta tese propõe versões modificadas dos algoritmos de Sipser e Spielman. Resultados de simulações para códigos Low Density Generator Matrix (LDGM) sistemáticos, com comprimento longo mostraram um melhor desempenho da versão proposta. Adicionalmente, para um comprimento médio dos códigos LDGM, resultados de simulações mostraram um desempenho similar à decodificação MWBF com a vantagem de não ser necessário o uso de operações em ponto flutuante / Abstract: Since Gallager introduced Bit-Flipping (BF) decoding with hard-decision for Low-Density Parity- Check Codes (LDPC), other two variants were proposed by Sipser and Spielman for expander codes. Later, a soft-decision version of BF decoding, known as Modified Weighted BF (MWBF) decoding, was investigated. This thesis proposes modified versions of Sipser and Spielman algorithms. Simulation results for long systematic Low-Density Generator Matrix (LDGM) codes show a better performance of the proposed versions. Moreover, for moderate length systematic LDGM codes, simulation results show performance similar to that of MWBF decoding with the advantage of not requiring floating-point operations / Mestrado / Telecomunicações e Telemática / Mestre em Engenharia Elétrica

Orientadores: Paulo Roberto Brumatti, Fernando Eduardo Torres Orihuela / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-05T23:44:44Z (GMT). No. of bitstreams: 1 Melo_Nolmar_M.pdf: 705654 bytes, checksum: b8ecfe0cc3ffd2dd2f63bc813a9c4a8d (MD5) Previous issue date: 2006 / Resumo: O objetivo central desta dissertação foi o de apresentar os Códigos Geométricos de Goppa via métodos elementares que foram introduzidos por J. H. van Lint, R. Pellikaan e T. Hfhold por volta de 1998. Numa primeira parte da dissertação são apresentados os conceitos fundamentais sobre corpos de funções racionais de uma curva algébrica na direção de se definir os códigos de Goppa de maneira clássica, neste estudo nos baseamos principalmente no livro ¿Algebraic Function Fields and Codes¿ de H. Stichtenoth. A segunda parte inicia-se com a introdução dos conceitos de funções peso, grau e ordem que são fundamentais para o estudo dos Códigos de Goppa via métodos elementares de álgebra linear e de semigrupos, tal estudo foi baseado em ¿Algebraic geometry codes¿ de J. H. van Lint, R. Pellikaan e T. Hfhold.A dissertação termina com a apresentação de exemplos que ilustram os métodos elementares que nos referimos acima / Abstract: The central objective of this dissertation was to present the Goppa Geometry Codes via elementary methods which were introduced by J. H. van Lint, R. Pellikaan and T. Hfhold about 1998. On the first past of such dissertation are presented the fundamental concepts about fields of rational functions of an algebraic curve in the direction as to define the Goppa Codes on a classical manner. In this study we based ourselves mainly on the book ¿Algebraic Function Fields and Codes¿ of H. Stichtenoth. The second part is initiated with an introduction about the functions weight, degree and order which are fundamental for the study of the Goppa Codes throught elementary methods of linear algebra and of semigroups and such study was based on ¿Algebraic Geometry Codes¿ of J. h. van Lint, R. Pellikaan and T. Hfhold. The dissertation ends up with a presentation of examples which illustrate the elementary methods that we have referred to above / Mestrado / Algebra / Mestre em Matemática

Orientador: Jaime Portugheis / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-25T19:09:11Z (GMT). No. of bitstreams: 1 PujaicoRivera_Fernando_D.pdf: 1689945 bytes, checksum: b226b1d9cf87f31fc3d470ac895b0e33 (MD5) Previous issue date: 2014 / Resumo: Esta tese propõe um sistema de transmissão de informação de várias fontes correlacionadas sobre canais ruidosos. Inicialmente se aborda o problema da codificação fonte-canal conjunta. Para este problema se definirá conceitos de taxas ótimas e se apresentará a maneira de obtê-las. Posteriormente, será proposto um algoritmo de decodificação conjunta com complexidade tratável. Diversos resultados de desempenho do algoritmo proposto serão apresentados. Estes resultados mostram um bom compromisso entre desempenho e complexidade quando comparados com a decodificação independente. Finalmente, o algoritmo de decodificação conjunta seguido de uma proposta de regra de fusão é usado no problema CEO e o desempenho deste novo algoritmo é apresentado / Abstract: This thesis proposes a system that transmits information from various correlated sources over noisy channels. Initially, it addresses the problem of joint source-channel coding. To solve this problem, concepts of optimal rates will be defined and the way to obtain them will be presented. Subsequently, a joint decoding algorithm with a tractable complexity is proposed. Several performance results of the proposed algorithm will be presented. These results show a good compromise between performance and complexity when compared to the non-joint decoding. Finally, the joint decoding algorithm, followed by a proposal for a fusion rule is used in the CEO problem and the performance of this new algorithm is presented / Doutorado / Telecomunicações e Telemática / Doutor em Engenharia Elétrica

Orientador: Reginaldo Palazzo Júnior / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-18T18:43:43Z (GMT). No. of bitstreams: 1 Faria_LuzineteCristinaBonanide_D.pdf: 17107444 bytes, checksum: 4faf2de7876247b3c74423dc7a3043d1 (MD5) Previous issue date: 2011 / Resumo: Um dos grandes desafios da comunidade científica em teorias da informação genética, comunicação genética e codificação genética é verificar a existência de uma estrutura matemática relacionada com a estrutura do DNA. Este trabalho propõe modelos para o sistema de comunicação de informação genética e genômica análogos ao modelo de um sistema de comunicação digital. Ambos os modelos são capazes de identificar, reproduzir e classificar matematicamente diferentes sequências de DNA. O primeiro identifica e reproduz a sequência de nucleotídeos de uma fita simples do DNA através da codificação genética e, o segundo identifica e reproduz a sequência das bases complementares da fita dupla do DNA através da codificação genômica. Os objetivos principais do presente trabalho são: a) caracterização matemática dos modelos de codificação genética e codificação genômica, b) proposta de um algoritmo para identificação de sequências de DNA; c) mostrar que sequências de DNA com características biológicas distintas, incluindo proteínas, gene e genoma em termos das fitas simples do DNA e da dupla hélice do DNA são identificadas como palavras-código dos códigos G-linearidade (BCH sobre corpos e BCH sobre anéis), reproduzidas e classificadas matematicamente, d) representação algébrica via polinômios primitivos/geradores e seus polinômios recíprocos das fitas simples do DNA (fita codante e fita não codante) e da dupla hélice do DNA, e) mostrar a existência de códigos concatenados (nested codes) entre algumas sequências de direcionamento e suas respectivas proteínas organelares, f) mostrar a arquitetura biológica (Biological frame) do genoma do plasmídeo Lactococcus lactis. Os resultados apresentados neste trabalho contribuem para o desenvolvimento de uma metodologia que poderá ser aplicada em análises mutacionais e de polimorfismos, produção de novos fármacos, melhoramento genético, entre outros, reduzindo tempo e custos laboratoriais / Abstract: One of the great challenges of the scientific community on theories of genetic information, genetic communication and genetic coding is to determine a mathematical structure related to the structure of DNA. This thesis proposes a model of a communication system for genetic and genomic information similar to the model of a digital communication system. Both models are able to identify, reproduce and classify mathematically different sequences of DNA. The first model identifies and reproduces the nucleotide sequence of a single DNA strand via the genetic encoding. The latter identifies and reproduces the sequence of the complementary bases of the double DNA strand through genomic encoding. The aims of this work are: a) a mathematical characterization of the models of genetic coding and genomic coding, b) the proposal of an algorithm for the identification of DNA sequences, c) to show that DNA sequences with distinct biological characteristics, including protein, gene and genome in terms of the single strands of DNA and of the double helix of DNA are identified as codewords of the G-linearity codes (BCH codes over fields and BCH codes over rings), mathematically reproduced and classified, d) algebraic representation via primitive/generator polynomials and their reciprocal polynomials of single DNA strands (coding strand and non-coding strand) and the double DNA strand, e) to show the existence of concatenated codes (nested codes) between some targeting sequences and their corresponding organelles proteins, f) to show the biological architecture (Biological frame) of the plasmid Lactococcus lactis genome. The results presented in this work contribute to the development of a methodology that can be applied to mutational analysis and polymorphisms, production of new drugs, genetic improvement, among others, reducing time and laboratory costs / Doutorado / Telecomunicações e Telemática / Doutor em Engenharia Elétrica

We investigate into the limitations of the sum-product algorithm for binary low density parity check (LDPC) codes having isolated short cycles. Independence assumption among messages passed, assumed reasonable in all configurations of graphs, fails the most in graphical structures with short cycles. This research work is a step forward towards understanding the effect of short cycles on error floors of the sum-product algorithm. We propose a modified sum-product algorithm by considering the statistical dependency of the messages passed in a cycle of length 4. We also formulate a modified algorithm in the log domain which eliminates the numerical instability and precision issues associated with the probability domain. Simulation results show a signal to noise ratio (SNR) improvement for the modified sum-product algorithm compared to the original algorithm. This suggests that dependency among messages improves the decisions and successfully mitigates the effects of length-4 cycles in the Tanner graph. The improvement is significant at high SNR region, suggesting a possible cause to the error floor effects on such graphs. Using density evolution techniques, we analysed the modified decoding algorithm. The threshold computed for the modified algorithm is higher than the threshold computed for the sum-product algorithm, validating the observed simulation results. We also prove that the conditional entropy of a codeword given the estimate obtained using the modified algorithm is lower compared to using the original sum-product algorithm.

Error-control codes, which are being extensively used in communication systems, have found themselves very useful in data storage as well during the past decade. This thesis deals with two types of codes for data storage, one pertaining to the issue of privacy and the other to reliability. In many scenarios, user accessing some critical data from a server would not want the server to learn the identity of data retrieved. This problem, called Private Information Retrieval (PIR) was rst formally introduced by Chor et al and they gave protocols for PIR in the case where multiple copies of the same data is stored in non-communicating servers. The PIR protocols that came up later also followed this replication model. The problem with data replication is the high storage overhead involved, which will lead to large storage costs. Later, Fazeli, Vardy and Yaakobi, came up with the notion of PIR code that enables information-theoretic PIR with low storage overhead. In the rst part of this thesis, construction of PIR codes for certain parameter values is presented. These constructions are based on a variant of conventional Reed-Muller (RM) codes called binary Projective Reed-Muller (PRM) codes. A lower bound on block length of systematic PIR codes is derived and the PRM based PIR codes are shown to be optimal with respect to this bound in some special cases. The codes constructed here have smaller block lengths than the short block length PIR codes known in the literature. The generalized Hamming weights of binary PRM codes are also studied. Another work described here is the implementation and evaluation of an erasure code called Coupled Layer (CL) code in Ceph distributed storage system. Erasure codes are used in distributed storage to ensure reliability. An additional desirable feature required for codes used in this setting is the ability to handle node repair efficiently. The Minimum Storage Regenerating (MSR) version of CL code downloads optimal amount of data from other nodes during repair of a failed node and even disk reads during this process is optimum, for that storage overhead. The CL-Near-MSR code, which is a variant of CL-MSR, can efficiently handle a restricted set of multiple node failures also. Four example CL codes were evaluated using a 26 node Amazon cluster and performance metrics like network bandwidth, disk read and repair time were measured. Repair time reduction of the order of 3 was observed for one of those codes, in comparison with Reed Solomon code having same parameters. To the best of our knowledge, such large gains in repair performance have never been demonstrated before.