Problema căutării matroidelor uniforme

Abstract

Matroidele sunt obiecte matematice care generalizează proprietatea de independenţă liniară, utilă pentru construirea matricelor generatoare ale codurilor non-binare corectoare de erori. Căutarea matroidelor, în special, a celor uniforme, este o problemă de complexitate polinomială. În lucrare este propusă o metodă de căutare bazată pe generarea şi analiza cicloclaselor asupra câmpurilor Galois extinse. Aceasta a diminuat esenţial complexitatea procedeului de căutare. Totodată, s-a observat că unele structuri matematice, şi anume, matricele Vandermonde, pot fi utilizate pentru reprezentarea matroidelor uniforme. Aceasta a permis, în particular, generarea codului matroid bun pentru controlul erorilor în CD-ROMuri. În lucrare au mai fost analizate şi găsite limitele de existenţă pentru unele tipuri de matroide uniforme.

Matroids are mathematical objects that generalize the properties of linear dependence, used to construct the generator matrices of the non-binary error-correcting codes. The matroids, namely, uniform searching has the polynomial complexity. In the paper the matroid based on cycloclasses generation and analysis over Galois field extension is proposed. So, the searching complexity was drastically decreased. From the other hand, it was observed that the knowing mathematical structures, namely, Vandermonde matrices could be applied to represent the uniform matroids. This allows constructing the matroid code for control the errors in the CD-ROMs. Also, was found and established the bounds of existence of some uniform matroids.

Les matroides sont objets mathématiques, qui généralisent la propriété de la dépendance linéaire, et c'est pour cela que sont très utile à la construction des matrices engendrant des codes corrigeant les erreurs. La recherche des matroides, à savoir, homogène est tâche de la polynomiale complexité. Dans le travail est proposé et on examine la méthode fondée sur la génération et l'analyse des cycloclasses au-dessus de les champs élargis Galois, qu'a permis beaucoup de diminuer la complexité de la procédure de prospection. Dans le travail, sont trouvés aussi et on établit les frontières de l'existence de certains types des matroides homogènes.

Матроиды – это математические объекты, которые обобщают свойство линейной зависимости, и поэтому являются весьма полезными для построения порождающих матриц кодов, корректирующих ошибки. В работе предложен и рассмотрен метод, основанный на генерации и анализе циклоклассов над расширенными полями Галуа, что позволило существенно уменьшить сложность поисковой процедуры. С другой стороны, отмечено, что некоторые известные математические структуры, а именно, матрицы Вандермонда, могут быть использованы для представления однородных матроидов, что позволило построить матроидный код для CD-ROM. В работе, также найдены и установлены границы существования некоторых типов однородных матроидов.