О тестирующем множестве для кодов типа Препараты

О тестирующем множестве для кодов типа Препараты

Васильева А. Ю.
Дискретный анализ и исследование операций, 30, 2, 5-14 (2023)
Скачать статью

УДК 519.8+518.25 
DOI: 10.33048/daio.2023.30.753

Аннотация:

Изучается вопрос о восстановлении объекта из заданного класса по его пересечению с так называемым тестирующим множеством. В качестве класса рассматриваются коды типа Препараты, т. е. нелинейные коды длины $n = 2^{2m} − 1, m = 2, 3, \dots$, с кодовым расстоянием 5 и мощности вдвое большей, чем у максимального линейного кода такой же длины с тем же кодовым расстоянием. Указаны условия, при которых объединение нескольких концентрических сфер является тестирующим множеством для кодов типа Препараты.

Литература:
  1. Васильева А. Ю. О реконструктивных множествах вершин в булевом кубе // Дискрет. анализ и исслед. операций. 2012. Т. 19, № 1. С. 3–16. 
     
  2. Зиновьев В. А., Леонтьев В. К. Несуществование совершенных кодов над полями Галуа // Пробл. управления и теории информации. 1973. Т. 2, № 2. С. 123–132. 
     
  3. Tietäväinen A. On the nonexistence of perfect codes over finite fields // SIAM J. Appl. Math. 1973. V. 24, No. 1. P. 88–96. 
     
  4. Zaitsev G. V., Zinoviev V. A., Semakov N. V. Interrelation of Preparata and Hamming codes and extension of Hamming codes to new double-errorcorrecting codes // Proc. 2nd Int. Symp. Information Theory (Tsahkadsor, Armenia, USSR, Sept. 2–8, 1971). Budapest: Akad´emiai Kiad´o, 1973. P. 257–264. 
     
  5. Семаков Н. В., Зиновьев В. А., Зайцев Г. В. Равномерно упакованные коды // Пробл. передачи информации. 1971. Т. 7, № 1. С. 38–50. 
     
  6. Krasikov I., Litsyn S. On integral zeros of Krawtchouk polynomials // J. Comb. Theory. Ser. A. 1996. V. 74, No. 1. P. 71–99. 
     
  7. Августинович С. В. Об одном свойстве совершенных двоичных кодов // Дискрет. анализ и исслед. операций. 1995. Т. 2, № 1. С. 4–6. 
     
  8. Кротов Д. С., Васильева А. Ю. О совершенных кодах, не включающих кодов Препараты // Пробл. передачи информации. 2016. Т. 52, № 3. С. 92–96. 
     
  9. Vasil’eva A. Yu. On the reconstruction of Preparata-like codes // Proc. 15th Int. Workshop Algebraic and Combinatorial Coding Theory (Albena, Bulgaria, June 18–24, 2016). Sofia: Inst. Math. Inform., 2016. P. 296–300.

Исследование выполнено в рамках государственного задания ИМ СО РАН (проект № FWNF–2022–0017).

Васильева Анастасия Юрьевна
  1. Институт математики им. С. Л. Соболева, 
    пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
  2. Новосибирский гос. университет, 
    ул. Пирогова, 2, 630090 Новосибирск, Россия

E-mail: vasilan@math.nsc.ru

Статья поступила 1 сентября 2022 г. 
После доработки — 14 сентября 2022 г. 
Принята к публикации 16 сентября 2022 г.

Abstract:

The reconstruction of an object of a given class by its intersection with some (so-called testing) set is studied. For the class, we consider Preparata-like codes, i. e. nonlinear codes of length $n = 2^{2m} − 1, m = 2, 3, \dots$, with code distance 5 and twice the size of a linear code of the same length and distance. We determine conditions under which the union of a few concentric spheres forms the testing set for Preparata-like codes.

References:
  1. A. Yu. Vasil’eva, On reconstructive sets of vertices in the Boolean cube, Diskretn. Anal. Issled. Oper. 19 (1), 3–16 (2012) [Russian] [J. Appl. Ind. Math. 6 (3), 393–402 (2012)]. 
     
  2. V. A. Zinoviev and V. K. Leontiev, On non-existence of perfect codes over Galois fields, Probl. Upravl. Teor. Inf. 2 (2), 123–132 (1973) [Russian]. 
     
  3. A. Tietäväinen, On the nonexistence of perfect codes over finite fields, SIAM J. Appl. Math. 24 (1), 88–96 (1973).  
     
  4. G. V. Zaitsev, V. A. Zinoviev, and N. V. Semakov, Interrelation of Preparata and Hamming codes and extension of Hamming codes to new double-errorcorrecting codes, in Proc. 2nd Int. Symp. Information Theory, Tsahkadsor, Armenia, USSR, Sept. 2–8, 1971 (Akadémiai Kiadó, Budapest, 1973), pp. 257–264 
     
  5. N. V. Semakov, V. A. Zinoviev, and G. V. Zaitsev, Uniformly packed codes, Probl. Peredachi Inf. 7 (1), 38–50 (1971) [Russian] [Probl. Inf. Transm. 7 (1), 30–39 (1971)]. 
     
  6. I. Krasikov and S. Litsyn, On integral zeros of Krawtchouk polynomials, J. Comb. Theory, Ser. A, 74 (1), 71–99 (1996). 
     
  7. S. V. Avgustinovich, On a property of perfect binary codes, Diskretn. Anal. Issled. Oper. 2 (1), 4–6 (1995) [Russian] [Operations Research and Discrete Analysis (Kluwer Acad. Publ., Dordrecht, 1997), pp. 227–232 (Math. Its Appl., Vol. 391)]. 
     
  8. D. S. Krotov and A. Yu. Vasil’eva, On perfect codes that do not contain Preparata-like codes, Probl. Peredachi Inf. 52 (3), 92–96 (2016) [Russian] [Probl. Inf. Transm. 52 (3), 284–288 (2016)]. 
     
  9. A. Yu. Vasil’eva, On the reconstruction of Preparata-like codes, in Proc. 15th Int. Workshop on Algebraic and Combinatorial Coding Theory, Albena, Bulgaria, June 18–24, 2016 (Inst. Math. Inform., Sofia, 2016), pp. 296–300.