No description available.

This thesis investigates channel-coded physical layer network coding, in which the relay directly transforms the noisy superimposed channel-coded packets received from the two end nodes, to the network-coded combination of the source packets. This is in contrast to the traditional multiple-access problem, in which the goal is to obtain each message explicitly at the relay. Here, the end nodes $A$ and $B$ choose their symbols, $S_A$ and $S_B$, from a small non-binary field, $\mathbb{F}$, and use non-binary PSK constellation mapper during the transmission phase. The relay then directly decodes the network-coded combination ${aS_A+bS_B}$ over $\mathbb{F}$ from the noisy superimposed channel-coded packets received from two end nodes. Trying to obtain $S_A$ and $S_B$ explicitly at the relay is overly ambitious when the relay only needs $aS_B+bS_B$. For the binary case, the only possible network-coded combination, ${S_A+S_B}$ over the binary field, does not offer the best performance in several channel conditions. The advantage of working over non-binary fields is that it offers the opportunity to decode according to multiple decoding coefficients $(a,b)$. As only one of the network-coded combinations needs to be successfully decoded, a key advantage is then a reduction in error probability by attempting to decode against all choices of decoding coefficients. In this thesis, we compare different constellation mappers and prove that not all of them have distinct performance in terms of frame error rate. Moreover, we derive a lower bound on the frame error rate performance of decoding the network-coded combinations at the relay. Simulation results show that if we adopt concatenated Reed-Solomon and convolutional coding or low density parity check codes at the two end nodes, our non-binary constellations can outperform the binary case significantly in the sense of minimizing the frame error rate and, in particular, the ternary constellation has the best frame error rate performance among all considered cases.

Mathematical optimization is applicable to nearly every scientific discipline. This thesis specifically focuses on optimization applications to digital communications and signal processing. Within the digital communications framework, the channel encoder attempts to encode a message from a source (the sender) in such a way that the channel decoder can utilize the encoding to correct errors in the message caused by the transmission over the channel. Low-density parity-check (LDPC) codes are an especially popular code for this purpose. Following the channel encoder in the digital communications framework, the modulator converts the encoded message bits to a physical waveform, which is sent over the channel and converted back to bits at the demodulator. The modulator and demodulator present special challenges for what is known as the two-antenna problem. The main results of this work are two algorithms related to the development of optimization methods for LDPC codes and the two-antenna problem. Current methods for optimization of LDPC codes analyze the degree distribution pair asymptotically as block length approaches infinity. This effectively ignores the discrete nature of the space of valid degree distribution pairs for LDPC codes of finite block length. While large codes are likely to conform reasonably well to the infinite block length analysis, shorter codes have no such guarantee. Chapter 2 more thoroughly introduces LDPC codes, and Chapter 3 presents and analyzes an algorithm for completely enumerating the space of all valid degree distribution pairs for a given block length, code rate, maximum variable node degree, and maximum check node degree. This algorithm is then demonstrated on an example LDPC code of finite block length. Finally, we discuss how the result of this algorithm can be utilized by discrete optimization routines to form novel methods for the optimization of small block length LDPC codes. In order to solve the two-antenna problem, which is introduced in greater detail in Chapter 2, it is necessary to obtain reliable estimates of the timing offset and channel gains caused by the transmission of the signal through the channel. The timing offset estimator can be formulated as an optimization problem, and an optimization method used to solve it was previously developed. However, this optimization method does not utilize gradient information, and as a result is inefficient. Chapter 4 presents and analyzes an improved gradient-based optimization method that solves the two-antenna problem much more efficiently.

On sait depuis vingt ans maintenant qu'un ordinateur quantique permettrait de résoudre en temps polynomial plusieurs problèmes considérés comme difficiles dans le modèle classique de calcul, comme la factorisation ou le logarithme discret. Entre autres, un tel ordinateur mettrait à mal tous les systèmes de chiffrement à clé publique actuellement utilisés en pratique, mais sa réalisation se heurte, entre autres, aux phénomènes de décohérence qui viennent entacher l'état des qubits qui le constituent. Pour protéger ces qubits, on utilise des codes correcteurs quantiques, qui doivent non seulement être performants mais aussi munis d'un décodage très rapide, sous peine de voir s'accumuler les erreurs plus vite qu'on ne peut les corriger. Une solution très prometteuse est fournie par des équivalents quantiques des codes LDPC (Low Density Parity Check, à matrice de parité creuse). Ces codes classiques offrent beaucoup d'avantages : ils sont faciles à générer, rapides à décoder (grâce à un algorithme de décodage itératif) et performants. Mais leur version quantique se heurte (entre autres) à deux problèmes. On peut voir un code quantique comme une paire de codes classiques, dont les matrices de parité sont orthogonales entre elles. Le premier problème consiste alors à construire deux « bons » codes qui vérifient cette propriété. L'autre vient du décodage : chaque ligne de la matrice de parité d'un des codes fournit un mot de code de poids faible pour le second code. En réalité, dans un code quantique, les erreurs correspondantes sont bénignes et n'affectent pas le système, mais il est difficile d'en tenir compte avec l'algorithme de décodage itératif usuel. On étudie dans un premier temps une construction existante, basée sur un produit de deux codes classiques. Cette construction, qui possède de bonnes propriétés théoriques (dimension et distance minimale), s'est avérée décevante dans les performances pratiques, qui s'expliquent par la structure particulière du code produit. Nous proposons ensuite plusieurs variantes de cette construction, possédant potentiellement de bonnes propriétés de correction. Ensuite, on étudie des codes dits q-Aires~: ce type de construction, inspiré des codes classiques, consiste à agrandir un code LDPC existant en augmentant la taille de son alphabet. Cette construction, qui s'applique à n'importe quel code quantique 2-Régulier (c'est-À-Dire dont les matrices de parité possèdent exactement deux 1 par colonne), a donné de très bonnes performances dans le cas particulier du code torique. Ce code bien connu se décode usuellement très bien avec un algorithme spécifique, mais mal avec l'algorithme usuel de propagation de croyances. Enfin, un équivalent quantique des codes spatialement couplés est proposé. Cette idée vient également du monde classique, où elle améliore de façon spectaculaire les performances des codes LDPC : le décodage s'effectue en temps quasi-Linéaire et atteint, de manière prouvée, la capacité des canaux symétriques à entrées binaires. Si dans le cas quantique, la preuve éventuelle reste encore à faire, certaines constructions spatialement couplées ont abouti à d'excellentes performances, bien au-Delà de toutes les autres constructions de codes LDPC quantiques proposées jusqu'à présent. / Quantum information is a developping field of study with various applications (in cryptography, fast computing, ...). Its basic element, the qubit, is volatile : any measurement changes its value. This also applies to unvolontary measurements due to an imperfect insulation (as seen in any practical setting). Unless we can detect and correct these modifications, any quantum computation is bound to fail. These unwanted modifications remind us of errors that can happen in the transmission of a (classical) message. These errors can be accounted for with an error-Correcting code. For quantum errors, we need to set quantum error-Correcting codes. In order to prevent the clotting of errors that cannot be compensated, these quantum error-Correcting codes need to be both efficient and fast. Among classical error-Correcting codes, Low Density Parity Check (LDPC) codes provide many perks: They are easy to create, fast to decode (with an iterative decoding algorithme, known as belief propagation) and close to optimal. Their quantum equivalents should then be good candidates, even if they present two major drawbacks (among other less important ones). A quantum error correction code can be seen as a combination of two classical codes, with orthogonal parity-Check matrices. The first issue is the building of two efficient codes with this property. The other is in the decoding: each row of the parity-Check matrix from one code gives a low-Weight codeword of the other code. In fact, with quantum codes, corresponding errors do no affect the system, but are difficult to account for with the usual iterative decoding algorithm. In the first place, this thesis studies an existing construction, based on the product of two classical codes. This construction has good theoritical properties (dimension and minimal distance), but has shown disappointing practical results, which are explained by the resulting code's structure. Several variations, which could have good theoritical properties are also analyzed but produce no usable results at this time. We then move to the study of q-Ary codes. This construction, derived from classical codes, is the enlargement of an existing LDPC code through the augmentation of its alphabet. It applies to any 2-Regular quantum code (meaning with parity-Check matrices that have exactly two ones per column) and gives good performance with the well-Known toric code, which can be easily decoded with its own specific algorithm (but not that easily with the usual belief-Propagation algorithm). Finally this thesis explores a quantum equivalent of spatially coupled codes, an idea also derived from the classical field, where it greatly enhances the performance of LDPC codes. A result which has been proven. If, in its quantum form, a proof is still not derived, some spatially-Coupled constructions have lead to excellent performance, well beyond other recent constuctions.

Submitted by Carmen Torres (carmensct@globo.com) on 2018-02-09T18:11:30Z No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Tese_MapeamentoBitsAdaptacao.pdf: 986310 bytes, checksum: 6e1b30f6ca34fc67df43f3141680c73a (MD5) / Approved for entry into archive by Edisangela Bastos (edisangela@ufpa.br) on 2018-02-16T16:12:49Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Tese_MapeamentoBitsAdaptacao.pdf: 986310 bytes, checksum: 6e1b30f6ca34fc67df43f3141680c73a (MD5) / Made available in DSpace on 2018-02-16T16:12:49Z (GMT). No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Tese_MapeamentoBitsAdaptacao.pdf: 986310 bytes, checksum: 6e1b30f6ca34fc67df43f3141680c73a (MD5) Previous issue date: 2017-09-29 / CNPq - Conselho Nacional de Desenvolvimento Científico e Tecnológico / Os codigos com matriz de vericação de paridade de baixa densidade (LDPC) tem sido adotados como estrategia de correção de erros em diversos padrões de sistemas de comunicação, como nos sistemas G.hn (padrão que unifica as redes domesticas) e IEEE 802.11n (padrão para redes sem o locais). Nestes sistemas com modulação de amplitude em quadratura (QAM) codicados com LDPC, mapear propriamente os bits codificados para os diferentes sub-canais, considerando o fato de os sub-canais terem diferentes qualidades, garante uma melhora no desempenho geral do sistema. Nesse sentido, esta Tese apresenta uma nova técnica de mapeamento de bits, baseada na suposição de que bits transmitidos em sub-canais \bons" ajudam bits transmitidos em sub-canais \ruins". Isto e possível através de algumas restrições impostas ao grafo de Tanner associado, semelhantes aos códigos Root-LDPC. A otimização deste mapeamento de bits utilizando curvas de transferência de informação extrínseca (EXIT charts) também e apresentada. Observa-se que esse mapeamento tem a vantagem de um espaço de busca de otimização reduzido quando aplicado ao sistema com modo de transmissão de portadora única. Além disso, em situações nas quais o espaço de busca não e tão reduzido, como em aplicações baseadas em multiplexação por divisão de frequência ortogonal (OFDM), chegou-se a uma simples regra pratica associada as restrições do mapeamento de bits que praticamente elimina a necessidade de uma otimização. Por fim, um estudo do impacto do nível de desequilíbrio de contabilidade através dos sub-canais sobre o desempenho do mapeamento de bits e apresentado. Os resultados das simulações mostram que a estratégia de mapeamento de bits melhora o desempenho do sistema, e que, na presença de variações do canal, o sistema pode, adaptativamente, aplicar um novo mapeamento de bits sem a necessidade de recorrer a uma otimização complexa, podendo ser muito útil em sistemas práticos. / Low-Density parity-check (LDPC) codes are being adopted as the error correction strategy in di erent system standards, such as the G.hn (home networking standard) and the IEEE 802.11n (wireless local standard). In these LDPC-coded quadrature amplitude modulation (QAM) systems, mapping the LDPC coded bits properly to the di erent sub-channels considering the fact that sub-channels have di erent qualities ensures an improved overall system performance. Accordingly, this thesis presents a new bit mapping technique based on the assumption that bits transmitted in \good" sub-channels, help bits transmitted in \bad" sub-channels. This can be made possible through some restrictions to be imposed on the associated Tanner graph, akin to Root-LDPC codes. An optimization of the root-like bit mapping through extrinsic information transfer (EXIT) charts analysis is also presented. We show that this mapping has the advantage of a reduced optimization search space when applied to single-carrier based systems. Moreover, in situations where the search space is not só reduced, such as in orthogonal frequency division multiplexing (OFDM)-based applications, we arrive at a rule of thumb associated with the bit mapping constraints that practically eliminates the need for an optimization. Finally, a study of the impact of the level of reliability imbalance across the sub-channels on the performance of the root-like bit mapping is presented. Simulation results show that the new bit mapping strategy improves performance, and that in the presence of channel variations, the system can, adaptively, apply a new bit mapping without the need of a complex optimization, which can be very useful in practical systems.

In this work, a multilayer security solution for digital communication systems is provided by considering the joint effects of physical-layer security channel codes with application-layer cryptography. We address two problems: first, the cryptanalysis of error-prone ciphertext; second, the design of a practical physical-layer security coding scheme. To our knowledge, the cryptographic attack model of the noisy-ciphertext attack is a novel concept. The more traditional assumption that the attacker has the ciphertext is generally assumed when performing cryptanalysis. However, with the ever-increasing amount of viable research in physical-layer security, it now becomes essential to perform the analysis when ciphertext is unreliable. We do so for the simple substitution cipher using an information-theoretic framework, and for stream ciphers by characterizing the success or failure of fast-correlation attacks when the ciphertext contains errors. We then present a practical coding scheme that can be used in conjunction with cryptography to ensure positive error rates in an eavesdropper's observed ciphertext, while guaranteeing error-free communications for legitimate receivers. Our codes are called stopping set codes, and provide a blanket of security that covers nearly all possible system configurations and channel parameters. The codes require a public authenticated feedback channel. The solutions to these two problems indicate the inherent strengthening of security that can be obtained by confusing an attacker about the ciphertext, and then give a practical method for providing the confusion. The aggregate result is a multilayer security solution for transmitting secret data that showcases security enhancements over standalone cryptography.

The VLSI implementation complexity of a low density parity check (LDPC) decoder is largely influenced by the interconnect and the storage requirements. This dissertation presents the decoder architectures for regular and irregular LDPC codes that provide substantial gains over existing academic and commercial implementations. Several structured properties of LDPC codes and decoding algorithms are observed and are used to construct hardware implementation with reduced processing complexity. The proposed architectures utilize an on-the-fly computation paradigm which permits scheduling of the computations in a way that the memory requirements and re-computations are reduced. Using this paradigm, the run-time configurable and multi-rate VLSI architectures for the rate compatible array LDPC codes and irregular block LDPC codes are designed. Rate compatible array codes are considered for DSL applications. Irregular block LDPC codes are proposed for IEEE 802.16e, IEEE 802.11n, and IEEE 802.20. When compared with a recent implementation of an 802.11n LDPC decoder, the proposed decoder reduces the logic complexity by 6.45x and memory complexity by 2x for a given data throughput. When compared to the latest reported multi-rate decoders, this decoder design has an area efficiency of around 5.5x and energy efficiency of 2.6x for a given data throughput. The numbers are normalized for a 180nm CMOS process. Properly designed array codes have low error floors and meet the requirements of magnetic channel and other applications which need several Gbps of data throughput. A high throughput and fixed code architecture for array LDPC codes has been designed. No modification to the code is performed as this can result in high error floors. This parallel decoder architecture has no routing congestion and is scalable for longer block lengths. When compared to the latest fixed code parallel decoders in the literature, this design has an area efficiency of around 36x and an energy efficiency of 3x for a given data throughput. Again, the numbers are normalized for a 180nm CMOS process. In summary, the design and analysis details of the proposed architectures are described in this dissertation. The results from the extensive simulation and VHDL verification on FPGA and ASIC design platforms are also presented.

Low Density Parity Check (LDPC) codes are the parity check codes of long block length, whose parity check matrices have relatively few non-zero entries. To improve the performance at relatively short block lengths, LDPC codes are constructed by either pseudo-random or quasi-cyclic methods instead of random construction methods. In this thesis, pseudo-random code construction methods, the effects of closed loops and the graph connectivity on the performance of pseudo-random LDPC codes are investigated. Moreover, quasi-cyclic LDPC codes, which have encoding and storage advantages over pseudo-random LDPC codes, their construction methods and performances are reviewed. Finally, performance comparison between pseudo-random and quasi-cyclic LDPC codes is given for both regular and irregular cases.

Traditional solutions to information security in communication systems act in the application layer and are oblivious to the effects in the physical layer. Physical-layer security methods, of which information-theoretic security is a special case, try to extract security from the random effects in the physical layer. In information-theoretic security, there are two asymptotic notions of secrecy---weak and strong secrecy This dissertation investigates the problem of information-theoretic strong secrecy on the binary erasure wiretap channel (BEWC) with a specific focus on designing practical codes. The codes designed in this work are based on analysis and techniques from error-correcting codes. In particular, the dual codes of certain low-density parity-check (LDPC) codes are shown to achieve strong secrecy in a coset coding scheme. First, we analyze the asymptotic block-error rate of short-cycle-free LDPC codes when they are transmitted over a binary erasure channel (BEC) and decoded using the belief propagation (BP) decoder. Under certain conditions, we show that the asymptotic block-error rate falls according to an inverse square law in block length, which is shown to be a sufficient condition for the dual codes to achieve strong secrecy. Next, we construct large-girth LDPC codes using algorithms from graph theory and show that the asymptotic bit-error rate of these codes follow a sub-exponential decay as the block length increases, which is a sufficient condition for strong secrecy. The secrecy rates achieved by the duals of large-girth LDPC codes are shown to be an improvement over that of the duals of short-cycle-free LDPC codes.

No description available.