Недвоичные линейные покрывающие коды

Автор: Давыдов А. А.

Журнал: Труды Московского физико-технического института @trudy-mipt

Статья в выпуске: 2 (54) т.14, 2022 года.

Бесплатный доступ

Представлен обзор известных работ по теме «Недвоичные линейные покрывающие коды» и проведён анализ основных результатов. Рассматриваются линейные покрывающие [n, n - r]qR-коды над полем из q элементов, q > 2. Если радиус покрытия R и коразмерность (избыточность) r фиксированы, то проблемой покрытия является построение кодов относительно небольшой длины n и/или получение хороших оценок длины. Функция длины ℓq (r, R) - это наименьшая возможная длина q-ичного линейного кода коразмерности r и радиуса покрытия R. В статье приведена известная нижняя граница функции длины и cформулированы две основные проблемы: построение кодов, асимптотически достигающих границы, и кодов, имеющих близкие к границе параметры. Подробно рассмотрены случаи, когда в литературе указанные проблемы решены путем построения бесконечных семейств покрывающих кодов. Отмечено взаимно однозначное соответствие между линейными покрывающими кодами и насыщающими множествами в проективных пространствах PG(N, q). Рассмотрены каскадные qm-конструкции удлинения покрывающих кодов как инструмент построения бесконечных кодовых семейств растущей коразмерности. Отмечены некоторые проблемы многократных покрытий.

Еще

Покрывающие коды, линейные коды, функция длины, насыщающие множества в проективной геометрии

Короткий адрес: https://sciup.org/142235306

IDR: 142235306

Список литературы Недвоичные линейные покрывающие коды

Cohen G., Honkaía I., Litsyn S., Lobstein A. Covering Codes. North-Holland Math. Library, V. 54. Amsterdam: Elsevier, 1997.
Brualdi R.A., Litsyn S., Pless V. Covering radius. Handbook of coding theory V. 1 / ed. by V.S. Pless, W.C Huffman. Amsterdam: Elsevier, 1998. P. 755-826.
Graham R.L., Sloane N.J.A. On the covering radius of codes // IEEE Transactions on Information Theory. 1985. V. 31, N 3. P. 385-401.
Davydov A.A., Giulietti M., Marcugini S., Pambianco F. Linear nonbinarv covering codes and saturating sets in projective spaces // Advances in Mathematics of Communications. 2011. V. 5, N 1. P. 119-147.
Bierbrauer J. Introduction to coding theory. Boca Raton, FL: Chapman & Hall, CRC Press, 2005.
Huffman W.C., Pless V.S. Fundamentals of Error-Correcting Codes. Cambridge: Cambridge Univ. Press, 2003.
MacWilliams F.J., Sloane N.J.A. The Theory of Error-Correcting Codes. 3rd edition. Amsterdam: North-Holland, 1981.
Roth R.M. Introduction to Coding Theory. Cambridge: Cambridge Univ. Press, 2006.
Lobstein A. Covering radius, an online bibliography. 2022. Available: https://www.lri.fr/~ lobstein/bib-a-jour.pdf
Aravamuthan S., Lodha S. Covering codes for Hats-on-a-line // Electronic J. Combinatorics. 2006. V. 13, N 21.
Astola J. T., Stankovic R.S. Determination of sparse representations of multiple-valued logic functions by using covering codes //J. Multiple-Valued Logic Soft Computing. 2012. V. 19, N 4. P. 285-306.
Bartoli D., Davydov A.A., Giulietti M., Marcugini S., Pambianco F. New upper bounds on the smallest size of a saturating set in a projective plane // Proceedings of XV International Symposium «Problems of Redundancy in Information and Control Systems (REDUNDANCY)». St .-Petersburg, Russia. IEEE Xplore. 2016. P. 18-22.
Bartoli D., Davydov A. A., Giulietti M., Marcugini S., Pambianco F. New bounds for linear codes of covering radius 2 // Proceedings of 5-th International Castle Meeting, ICMCTA «Coding Theory and Applications». Vihula, Estonia. Lecture Notes in Computer Science. Springer, Cham. 2017. V. 10495, P. 1-10.
Bartoli D., Davydov A.A., Giulietti M., Marcugini S., Pambianco F. New bounds for linear codes of covering radii 2 and 3 // Cryptography and Communications. 2019. V. 11, N 5, P. 903-920.
Bartoli D., Davydov A.A., Marcugini S., Pambianco F. Tables, bounds and graphics of short linear codes with covering radius 3 and codimension 4 and 5. 2020 // arXiv:1712.07078 fcs.IT].
Bierbrauer J., Fridrich J. Constructing good covering codes for applications in steganographv // Transactions of Data Hiding Multimedia Security III. Lecture Notes in Computer Science, Springer-Verlag. 2008. V. 4920. P. 1-22.
Chen H. List-decodable codes and covering codes // arXiv:2109.02818 fcs.IT]. 2022.
Давыдов А.А. Конструкции линейных покрывающих кодов // Проблемы передачи информации. 1990. Т. 26, вып. 4. С. 38-55.
Davydov A.A. Constructions and families of covering codes and saturated sets of points in projective geometry // IEEE Transactions on Information Theory. 1995. V. 41, N 6. P. 2071-2080.
Davydov A.A. Constructions and families of nonbinarv linear codes with covering radius 2 11 IEEE Transactions on Information Theory. 1999. V. 45, N 5. P. 1679-1686.
Davydov A.A., Giulietti M., Marcugini S., Pambianco F. Linear covering codes over nonbinarv finite fields // Proceedings of XI International Workshop «Algebraic and Combintorial Coding Theory, АССТ2008», Pamporovo, Bulgaria. 2008. P. 70-75. Available: http://www.moi.math.bas.bg/acct2008/bl2.pdf
Davydov A.A., Marcugini S., Pambianco F. Linear codes with covering radius 2, 3 and saturating sets in projective geometry // IEEE Transactions on Information Theory. 2004. V. 50, N 3. P. 537-541.
Davydov A. A., Marcugini S., Pambianco F. New covering codes of radius R, codimension tR and tR + and saturating sets in projective spaces // Designs, Codes and Cryptography. 2019. V. 87, N 12. P. 2771-2792.
Davydov A.A., Marcugini S., Pambianco F. New bounds for linear codes of covering radius 3 and 2-saturating sets in projective spaces // Proceedings of XVI International Symposium «Problems of Redundancy in Inform. Control Systems (REDUNDANCY)». Moscow, Russia. IEEE Xplore. 2019. P. 47-52.
Davydov A.A., Marcugini S., Pambianco F. Bounds for complete arcs in PG(3, q) and covering codes of radius 3, codimension 4, under a certain probabilistic conjecture // «Computational Science and Its Applications - ICCSA 2020», Lecture Notes in Computer Science, Springer, Cham. 2020. V. 12249. P. 107-122.
Davydov A.A., Marcugini S., Pambianco F. Upper bounds on the length function for covering codes with covering radius R and codimension tR + 1 // Advances in Mathematics of Communications. 2022. doi: 10.3934/amc.2021074.
Davydov A.A., Ostergârd P.R.J. New linear codes with covering radius 2 and odd basis // Designs, Codes and Cryptography. 1999. V. 16, N 1. P. 29-39.
Davydov A.A., Ostergârd P.R.J. On saturating sets in small projective geometries // European J. Combinatorics. 2000. V. 21, N 5. P. 563-570.
Davydov A. A., Ostergârd P.R.J., Linear codes with covering radius R = 2,3 and R
Davydov A.A., Ostergârd P.R.J. Linear codes with covering radius 3 // Designs, Codes and Cryptography. 2010. V. 54, N 3. P. 253-271.
Denaux L. Constructing saturating sets in projective spaces using subgeometries // Designs, Codes and Cryptography. 2021. doi.10.1007/sl0623-021-00951-y
Denaux L. Higgledy-piggledy sets in projective spaces of small dimension // arXiv:2109.08572 [math.CO]. 2021.
Etzion T., Storme L. Galois geometries and coding theory // Designs, Codes and Cryptography. 2016. V. 78, N 1. P. 311-350.
Exoo G., Junnila V., Laihonen T., Ranto S. Constructions for identifying codes / / Proceedings of XI International Workshop «Algebraic and Combintorial Coding Theory, ACCT2008». Pamporovo, Bulgaria. 2008. P. 92-98. Available: http://www.moi.math.bas.bg/acct2008/bl6.pdf.
Galand F., Kabatiansky G. Information hiding by coverings // Proceeings of 2003 IEEE Information Theory Workshop (Cat. No. 03EX674). Paris. 2003. IEEE Xplore. P. 151-154.
Галан Ф., Кабатянский Г.А. Покрытия, центрированные коды и комбинаторная стеганография // Проблемы передачи информации. 2009. Т. 45, вып. 3. С. 106-111.
Giulietti M. The geometry of covering codes: small complete caps and saturating sets in Galois spaces // Surveys in Combinatorics 2013 / Ed. by Blackburn S.R., Hollowav R., WTildon M. London Math. Soc. Lecture Note Series V. 409. Cambridge: Cambridge University Press, 2013. P. 51-90.
Guo Q., Johansson T., Lôndahl С. Solving LPN using covering codes // J. Cryptologv. 2020. V. 33, N 1. C. 1-33.
Héger T., Nagy Z.L. Short minimal codes and covering codes via strong blocking sets in projective spaces // IEEE Transactions on Information Theory. 2022. V. 68, N 2. P. 881-890.
Но C.T., Bruck J., Agrawal R. Partial-sum queries in OLAP data cubes using covering codes 11 IEEE Transactions on Computers. 1998. V. 47, N 12. P. 1326-1340.
Kiss G., Kovâcs I., Kutnar K., Ruff J., Sparl P. A note on a geometric construction of large Caylev graphs of given degree and diameter // Studia Univ. «Babe§ -Bolvai», Mathematica. 2009. V. LIV, N 3. P. 77-84.
Klein A., Storme L. Applications of finite geometry in coding theory and cryptography. Security, Coding Theory and Related Combinatorics, NATO Science for Peace and Security,
Ser. D: Information and Communication Security V. 29 / Ed. by D. Crnkovic, V. Tonchev IOS Press, 2011. P. 38-58.
Laihonen T.K. Sequences of optimal identifying codes // IEEE Transactions on Information Theory. 2002. V. 48, N 3. P. 774-776.
Landjev I., Storme L. Galois geometry and coding theory. Current Research Topics in Galois geometry / ed. by J. De Beule, L. Storme. Chapter 8. New York: NOVA Academic, 2011. P. 187-214.
Lenstra if. W., Jr., Seroussi G. On hats and other covers // Proceedings of IEEE International Symposium on Information Theory. Lausanne, Switzerland. 2002. IEEE Xplore. P. 342-342.
Nagy Z.L. Saturating sets in projective planes and hvpergraph covers // Discrete Mathematics. 2018. V. 341, N 4. P. 1078-1083.
Struik R. Covering Codes. Ph.D thesis. Eindhoven University of Technology. The Netherlands, 1994.
Garcia C., Peyrat C. Large Caylev graphs on an abelian group // Discrete Applied Mathematics. 1997. V. 75, N 2. R 125-133.
Boros E., Szônyi T., Tichler K. On defining sets for projective planes // Discrete Mathematics. 2005. V. 303. P. 17-31.
Koksal C. E. An analysis of blocking switches using error control codes // IEEE Transactions on Information Theory. 2007. V. 53, N 8. P. 2892-2897.
Mennink B., Neves S. On the resilience of Even-Mansour to invariant permutations // Designs, Codes and Cryptography. 2021. V. 89, N 5. P. 859-893.
Kovâcs S.J. Small saturated sets in finite projective planes // Rendiconti di Matematica, Serie VII. 1992. V. 12. P. 157-164.
Hirschfeld J. W.P. Finite Projective Spaces of Three Dimensions. Oxford: Oxford Univ. Press, 1985.
Hirschfeld J. W.P. Projective Geometries over Finite Fields. 2nd edition. Oxford: Oxford Univ. Press, 1999.
Hirschfeld J.W.P., Storme L. The packing problem in statistics, coding theory and finite projective spaces: Update 2001 // Proceedings of 4-th Isle of Thorns Conf. «Finite Geometries» / ed. by A. Blokhuis, J.W.P. Hirschfeld, D. Jungnickel, J.A. Thas. Develop. Math. V. 3. Dordrecht: Kluwer, 2001. P. 201-246.
Hirschfeld J. W.P., Thas J.A. Open problems in finite projective spaces // Finite Fields and their Applications. 2015. V. 32, N 1. P. 44-81.
Brualdi R.A., Pless V.S, Wilson R.M. Short codes with a given covering radius // IEEE Transactions on Information Theory. 1989. V. 35, N 1. P. 99-109.
Fancsali S.L., Sziklai P. Lines in Higgledv-Piggledy arrangement // Electronic J. Combinatorics. 2014. V. 21, N 2. Paper 15.
Bonini M., Borello M. Minimal linear codes arising from blocking sets //J. Algebraic Combinatorics. 2020. V. 53, N 5. P. 327-341.
Ughi E. Saturated configurations of points in projective Galois spaces // Europian J. Combinatorics. 1987. V. 8, N 3. P. 325-334.
Sonnino A. Transitive PSL(2, 7)-invariant 42-arcs in 3-dimensional projective spaces // Designs, Codes and Cryptography. 2014. V. 72, N 2. P. 455-463.
Honkala I., Litsyn S. Generalizations of the covering radius problem in coding theory // Bulletin Institute of Combinatorics and its Applications. 1996. V. 17, N 1. P. 39-46.
Hàmàlàinen if. O., Rankinen S. Upper bounds for football pool problems and mixed covering codes 11 J. Combinatorial Theory Ser. A. 1991. V. 56, N 1. P. 84-95.
Bartoli D., Davydov A. A., Giulietti M., Marcugini S., Bam,bianco F. Multiple coverings of the farthest-off points with small density from projective geometry // Advances in Mathematics of Communications. 2015. V. 9, N 1. P 63-85.
Bartoli D., Davydov A.A., Giulietti M., Marcugini S., Bam,bianco F. Further results on multiple coverings of the farthest-off points // Advances in Mathematics of Communications. 2016. V. 10, N 3. P. 613-632.
Justesen J., H0holdt T. Bounds on list decoding of MDS codes // IEEE Transactions on Information Theory. 2001. V. 47, N 4. P. 1604-1609.
Kaipa K. Deep holes and MDS extensions of Reed-Solomon codes // IEEE Transactions on Information Theory. 2017. V. 63, N 8. P. 4940-4948.
Bartoli D., Davydov A.A., Marcugini S., Bambianco F. On planes through points off the twisted cubic in PG(3, q) and multiple covering codes // Finite Fields and their Applications. 2020. V. 67. Paper 101710.
Davydov A.A., Marcugini S., Bambianco F. On the weight distribution of the cosets of MDS codes // Advances in Mathematics of Communications. 2022. doi: 10.3934/amc.2021042.

Еще

Статья научная