Thesis (M.A.)--Rowan University, 2007. / Typescript. Includes bibliographical references.

Thesis (Ph. D.)--University of Wisconsin--Madison, 1966. / Typescript. Vita. Includes bibliographical references (leaves 148-150).

Thesis (Ph.D.) -- University of Texas at Dallas, 2006 / Includes vita. Includes bibliographical references (leaves 102-110)

Polar codes were invented as the first error-correcting codes to achieve the capacity for the discrete channels with relatively low-complexity for encoding and decoding. However, this is only possible with significantly large code lengths which are not practical for many systems. Meanwhile, the performance of the finite-lengths polar codes is not competitive with other modern error-correcting codes. This can be attributed to the suboptimality of the decoding process and the relatively poor minimum Hamming distances. This thesis aims to improve the performance of polar codes. The contributions include improving the performance of the conventional successive cancellation decoder. This is based on a novel technique, namely one-step decision delay, which incorporates some extra computational nodes to the code tree. Also, this thesis presents two methods for increasing the Hamming distances of polar codes; in the first, the code rate remains unchanged, while in the second, that produces superior performance, a modest reduction in the code rate occurs. Both methods enhance the performance with using belief propagation decoder. In addition, the latency of the decoding process is reduced by applying the fast Hadamard transform decoder on polar codes for the first time. In this regard, a method to modify the encoder is presented for some lengths that are not normally compatible with the proposed decoder. Interestingly, this modification method has another advantage that in the sense that it increases the minimum Hamming distances of the codes. Furthermore, this thesis presents the utilisation of polar codes in some practical communication systems. Firstly, polar codes are examined over power line communication systems. In this respect, the construction of polar codes is analysed by using three different methods. Additionally, the practical performance of polar codes is illustrated for both single-carrier and multi-carrier channels. Secondly, this thesis explores polar codes for unequal error protection by partitioning the information sets into a number of subsets with different reliabilities. JPEG2000, which is an image compression method, is used for validating the advantages of the proposed technique. Moreover, a new joint source channel decoding is proposed from the combination of the polar decoder and JPEG2000 decoder in order to enhance the quality of the compressed images. Finally, polar codes are investigated for the energy transfer by presenting new subcodes that are chosen according to the weights of the produced codewords. In this context, two modes of energy transfer are presented. The proposed modes can successfully extend the lifetime of the receiver's battery.

Tout d’abord, mon sujet de recherche porte sur le cryptographie à clé publique, plus précisément la cryptographie basée sur la théorie des codes correcteurs d’erreurs. L’objectif principal de cette thèse est d’analyser la sécurité des systèmes de chiffrement. Pour cela j’étudie les propriétés structurelles des différentes familles de codes linéaires utilisées dans la pratique. Mon travail de recherche s’est orienté de maniéré naturelle, vers l’étude des deux dernières propositions de cryptosystèmes, plus exactement le schéma de McEliece à base des codes MDPC [MTSB13](moderate parity check codes) et des codes Polaires [SK14]. Dans le cas des codes MDPC on a mis en évidence une faiblesse importante au niveau des clés utilisées par les utilisateurs du système. En effet, on a proposé un algorithme très efficace qui permet de retrouver une clé privé à partir d’une clé publique. Ensuite on a compté le nombre des clés faibles et on a utilisé le problème d’équivalence de codes pour élargir le nombre de clés faibles. On a publié notre travail de recherche dans une conférence internationale en cryptographie [BDLO16]. Ensuite on a étudié les codes Polaires et leur application à la cryptographie à clé publique. Depuis leur découverte par E. Arikan [Arı09], les codes Polaires font partie des famille de codes les plus étudié du point de vue de le théorie de l’information. Ce sont des codes très efficaces en terme de performance car ils atteignent la capacité des canaux binaires symétriques et ils admettent des algorithmes d’encodage et décodage très rapides. Néanmoins, peu des choses sont connu sur leur propriétés structurelles. Dans ce cadre la, on a introduit un formalisme algébrique qui nous a permit de révéler unegrande partie de la structure de ces codes. En effet, on a réussi à répondre à des questions fondamentales concernant les codes Polaires comme : le dual ou la distance minimale d’un code Polaire, le groupe des permutations ou le nombre des mots de poids faible d’un code Polaire. On a publié nos résultats dans une conférence internationale en théorie de l’information [BDOT16]. Par la suite on a réussi à faire une cryptanalyse complète du schéma de McEliece à base des codes Polaires. Ce résultat a été une application directe des propriétés découvertes sur les codes Polaires et il a été publié dans une conférence internationale en cryptographie post-quantique [BCD+16]. / First of all, during my PhD I focused on the public key cryptography, more exactly on the code-based cryptography. The main motivation is to study the security of the latest encryption schemes. For that, I analyzed in detail the structural properties of the main code families. Thus, my research was naturally directed to the study of the McEliece based encryption schemes, among which the latest MDCP based variant [MTSB13] and Polar codes variant [SK14]. In the case of the MDPC based variant, we manage to reveal an important weakness regarding the key pairs that are used in the protocol. Indeed, we proposed an efficient algorithm that retrieves the private key given the public key of the scheme. Next we counted the proportion of weak keys and we used the code equivalence problem to extend the number of weak keys. We published our results in an international conference in cryptography [BDLO16]. Next we studied the Polar codes and their application to public key cryptography.Since they were discovered by Arikan [Arı09], Polar codes are part of the most studied from an information theory point of view, family of codes. In terms of performance they are really efficient since they are capacity achieving over the Binary Discrete Memoryless Channels and they allow extremely fast encoding and decoding algorithms. Nonetheless, few facts are known about their structure. In this context, we have introduced an algebraic formalism which allowed us to reveal a big part of the structure of Polar codes. Indeed, we have managed to answer fundamental questions regarding Polar codes such as the dual, the minimum distance, the permutation group and the number of minimum weight codewords of a Polar code. Our results were published in an international conference in information theory [BDOT16]. We also managed to completely cryptanalyze the McEliece variant using Polar codes. The attack was a direct application of the aforementioned results on the structural properties of Polar codes and it was published in an international conference in postquantum cryptography [BCD+16].

En considérant les polynômes sur le corps fini de Galois à deux éléments, notre intention porte sur la divisibilité des trinômes x^am+x^bs+1, pour m>s≥1, par un polynôme irréductible de degré r, pour cela, nous avons réalisé le résultat :S'il existe m, s des entiers positifs tels que le trinôme x^am+x^bs+1 soit divisible par un polynôme irréductible de degré r sur F2, alors a et b ne sont pas divisibles par (2r- 1). Pour ce type de trinômes nous conjecturons que le rapport πM(a,b)/ πM(1,1) tend vers une limite finie (dépendant de a et b) quand M tend vers l'infini. Notre recherche porte ensuite sur les codes cycliques de rendement 1/2 sur les deux corps finis F3 et F5 et nous accentuons notre recherche sur ceux iso duaux. Le problème central dans la théorie du codage est trouver la plus grande distance minimum dq pour laquelle un code de paramètres [n, q, d] sur Fq existe. Dans ce contexte nous avons réussi à optimiser cette distance pour les codes cycliques de taux 1/2 sur F3 et F5 en allant jusqu’à la longueur 74 pour les codes ternaires et 42 pour ceux sur F5. Nous avons aussi réussi à construire sept classes de codes cycliques iso-duaux sur le corps fini à 3 éléments et trois classes de codes cycliques iso-duaux sur le corps fini à 5 éléments. / Considering polynomials over the Galois finite fields for two elements, our intention stand over the divisibility of the trinomials x^am+x^bs+1, for m>s ≥ 1, by an irreducible polynomial of degree r, for this, we contribute to the result :If there exist positive integers m, s such that the trinomial x^am+x^bs+1 is divisible by an irreducible polynomial of degree r over F2, then a and b are not divisible by (2^r- 1). For this type of trinomials we conjectured that the ratios πM(a,b)/ πM(1,1) tend to a finite limit (dependently of a and b) when M tend to infinity. Our research stand at sequel on the cyclic codes of rate 1/2 over the two finite fields F3 and F5 and we check our research over whose are isodual. The so-called fundamental problem in coding theory is finding the largest value of dq for which a code of parameters [n, q, d] over Fq exists. In this context we have successfully optimize this distance for the cyclic codes of rate 1/2 over F3 and F5 up to length 74 for the ternary cyclic codes and 42 for whose over F5. We have also successful to construct seven classes of isodual cyclic codes over the field of 3 elements and three classes over the field of 5 elements.

No description available.

No description available.

No description available.

En esta tesis profundizamos en el estudio de los códigos flag. Un flag es una sucesión de subespacios encajados de un espacio vectorial finitodimensional sobre un cuerpo también finito y un código flag es una colección no vacía de flags. Estos códigos fueron introducidos en 2018 por Liebhold et al. como una generalización de los códigos de subespacio, ampliamente estudiados en la última década. Cada código flag define de forma natural una familia de códigos de subespacio: sus códigos proyectados. A lo largo de esta tesis, investigamos la relación existente entre los códigos flag y sus respectivos códigos proyectados, a través de problemas de diferente naturaleza y utilizando herramientas provenientes de distintas áreas de las matemáticas. A continuación, exponemos brevemente el contenido de cada uno de los nueve capítulos que constituyen esta tesis. En primer lugar, abordamos el estudio de los códigos flag de distancia óptima. Estos códigos presentan gran interés puesto que detectan y corrigen el máximo número de errores y/o borrados posibles. En el Capítulo 1 caracterizamos estos códigos en términos de sus códigos proyectados. Además, bajo ciertas condiciones, concluimos que los códigos flag de distancia óptima alcanzan también el máximo cardinal posible cuando uno de sus códigos proyectados es un código spread. Los Capítulos 1 y 2 están dedicados al estudio y la construcción sistemática de esta familia especial de códigos flag (los de distancia óptima con un spread como proyectado) para cualquier elección de los parámetros. Por otra parte, en los Capítulos 3 y 6 utilizamos la acción transitiva del grupo general lineal sobre la variedad de flags y determinamos subgrupos adecuados para obtener construcciones, ahora orbitales, de códigos flag de distancia óptima con un spread entre sus proyectados. El Capítulo 4, por su parte, es un estudio general de propiedades de códigos flag orbitales bajo la acción natural del grupo multiplicativo de un cuerpo finito: los códigos flag cíclicos. Para ello, resulta crucial conocer el llamado mejor amigo del flag generador. En el mismo trabajo, estudiamos los “códigos flag de Galois”, en los que el flag generador está dado por una torre de subcuerpos encajados. En este caso, obtenemos construcciones orbitales cíclicas con spreads en todos los códigos proyectados. Además, probamos que las posibilidades para la distancia de un código flag de Galois son muy reducidas y determinamos qué subgrupos permiten alcanzar cada una de ellas. Este estudio continúa en el Capítulo 7, donde consideramos los llamados códigos flag de Galois generalizados: aquellos en los que el flag generador contiene cuerpos encajados, pero no todos sus subespacios son cuerpos. En este caso, mostramos que la presencia de cuerpos en el flag generador tampoco es compatible con todos los valores de la distancia de los códigos orbitales que este genera. Sin embargo, presentamos construcciones de estos códigos que nos permiten afirmar que, al contrario de lo que ocurre con los códigos de Galois, no todas las distancias compatibles con la estructura de cuerpos son realmente alcanzables. En el Capítulo 5 hacemos un estudio pormenorizado de los códigos flag consistentes: una familia de códigos flag cuyos parámetros quedan perfectamente determinados por los de sus códigos proyectados. Además, probamos que, bajo la condición de consistencia, ciertas propiedades estructurales de un código flag son equivalentes a las análogas para sus códigos proyectados y presentamos varias familias de ejemplos. Por último, la condición de consistencia también resulta ser de gran utilidad a la hora de decodificar códigos flag y proporcionamos un algoritmo de decodificación en el canal de borrado. Los Capítulos 8 y 9 están dedicados al estudio del parámetro distancia de los códigos flag. En el primero de ellos, introducimos el concepto de vector distancia y determinamos los valores de la distancia entre flags que pueden ser obtenidos a través de vectores distancia satisfaciendo determinadas condiciones. Este estudio se relaciona, a continuación, con el número de subespacios que dos flags distintos pueden compartir sin comprometer el valor de la distancia mínima de un código flag. Como consecuencia, obtenemos nuevas cotas para el cardinal de códigos flag para cualquier elección de los parámetros. Por último, en el Capítulo 9, interpretamos la distancia entre flags a través de estructuras combinatorias que construimos ad hoc para el estudio de nuestro problema. Más concretamente, asociamos un diagrama de Ferrers adecuado a la variedad de flags completos y, a través de él, identificamos condiciones sobre la distancia entre flags con ciertos elementos combinatorios provenientes de la Teoría de Particiones. Este nuevo diccionario nos permite obtener nuevos resultados que relacionan los parámetros de un código flag con los de sus proyectados, así como reinterpretar la caracterización de códigos flag de distancia óptima propuesta en el primer capítulo en términos de objetos combinatorios. / Generalitat Valenciana y Fondo Social Europeo (ACIF/2018/196)