Codes quasi-cycliques : constructions algébriques et représentations par treillis
Institution:
NiceDisciplines:
Directors:
Abstract EN:
Quasi-cyclic codes are block codes. They generalize cyclic codes and approximate convolutional codes. Moreover, quasi-cyclic codes are asymptotically good. Trellises are oriented labeled graphs, which represent block codes. Trellises could be conventional or tail-biting. We present two different algebraic approaches to quasi-cyclic codes. We associate the algebraic structure, which extends the cubic construction (a+x | b+x | a+b+x) into the quintic and the septic constructions, to the conventional trellises. The cyclic approach is associated to the tail-biting trellises. We introduce a graphical construction for quasi-cyclic codes; this construction is based on trellises. In the case of convolutional trellises, this construction is a generalization of the squared and cubing constructions proposed by G. D. Forney Jr. Some algebraic constructions of new self-dual binary codes are given. These new codes have parameters [70, 35, 12] or [72, 36, 12] or other. They are obtained with the cubic, the quintic or the septic construction and they are constructed with the computer language Magma.
Abstract FR:
Au sein des codes correcteurs d'erreurs et de la Théorie de l'Information, les codes quasi-cycliques tiennent une place particulière. Ces codes de longueur finie généralisent les codes cycliques et approchent les codes de longueur infinie que sont les codes convolutifs. Les codes quasi-cycliques possèdent de plus d'excellents paramètres : ils ont une grande capacité de correction. Nous présentons deux approches algébriques différentes pour ces codes : l'approche constructive proposée par Ling San et Patrick Solé, qui ont généralisé la construction cubique en la construction quintique et la construction septique, et l'approche cyclique reprise par Kristine Lally. Les treillis sont des graphes qui permettent de représenter les codes correcteurs d'erreurs, dans le but de les décoder avec l'algorithme de Viterbi. Il existe deux types de treillis : les treillis conventionnels et les treillis cycliques. À chacun de ces types de treillis nous associons une construction graphique de codes quasi-cycliques qui correspond à l'une des deux approches algébriques présentées précédemment : Pour les treillis conventionnels, la construction graphique est une généralisation de la construction de G. D. Forney. Elle rejoint l'approche de S. Ling et P. Solé sous certaines conditions. Les treillis cycliques sont associés à la représentation cyclique de K. Lally. Ces treillis permettent de représenter les codes avec moins de sommets que les treillis conventionnels. Enfin, de nouveaux codes auto-duaux, entre autres des codes de paramètres [70,35,12] et [72, 36,12], sont construits à partir des constructions cubiques, quintiques et septiques et du logiciel Magma.