УДК 519.688
MSC: 42A38, 42B10
DOI: 10.21538/0134-4889-2020-26-3-249-257
Работа выполнена при поддержке Министерства науки и высшего образования РФ в рамках выполнения работ по Государственному заданию ФНИЦ “Кристаллография и фотоника” РАН (соглашение № 007 - ГЗ/Ч3363/26) — в части исследования систем счисления и Российского фонда фундаментальных исследований (проекты РФФИ №19-07-00357_а, № 18-29-03135_ мк) — в части исследования машинной арифметики.
Полный текст статьи (Full text)
Статья переведена: ISSN 0081-5438
Proceedings of the Steklov Institute of Mathematics, 2021, Vol. 313, Suppl. 1, pp. S33–S39. (Abstract)
В работе рассматривается специфическая версия авторского подхода к синтезу базисов дискретных ортогональных преобразований (ДОП), учитывающего связь структуры базисных функций преобразования и существованием той или иной системы счисления на (многомерном) множестве индексов входного сигнала. В отличие от случая прототипной работы В. М. Чернова “Дискретные ортогональные преобразования с базисами, порожденными самоподобными последовательностями” (2018), в которой рассматривались ДО, ассоциированные с безизбыточными системами счисления (т. е. с такими системами счисления, в которых каждый индекс входного сигнала имел бы единственное представление в избранной системе счисления), в данной работе рассматривается случай так называемых полных систем счисления. Для них уже нет биективного соответствия между множеством входных индексов ДОП и множеством их цифровых представлений. Потенциально такие постановки прикладных задач естественно возникают в распознавании изображений, искусственном интеллекте, теории формальных языков, математическом программировании и в других областях, где анализируемые объекты характеризуются многими разнородными признаками, которые могут быть и количественными, и качественными, и смешанными. При этом сами объекты могут существовать в нескольких экземплярах, имеющих, в частности и противоречивые описания, которые должны рассматриваться и анализироваться как единое целое. Такие многопризнаковые объекты можно представить как мультимножества (“множества с повторениями”). В силу того, что дискретный спектральный анализ является одним из основных инструментов перечисленных задач в классической “множественной” интерпретации объектов исследования, в настоящей работе предпринимается попытка экстраполяции некоторых идей и методов дискретного спектрального анализа на случай анализа мультимножественных объектов.
Ключевые слова: мультимножества, дискретные ортогональные преобразования, полные последовательности
СПИСОК ЛИТЕРАТУРЫ
1. Петровский А. Б. Пространства множеств и мультимножеств. Москва: Едиториал УРСС, 2003. 248 p.
2. Петровский А. Б. Теория измеримых множеств и мультимножеств. Москва: Наука, 2018. 359 с.
3. М. Айгнер. Комбинаторная теория; пер. с англ. Москва: Мир, 1982. 558 c.
4. Баранов В. И., Стечкин Б. С. Экстремальные комбинаторные задачи и их приложения. Москва: Наука, 1989. 240 c.
5. Чернов В. М. Дискретные ортогональные преобразования с базисами, порожденными самоподобными последовательностями // Компьютерная оптика. 2018. Т. 42, № 5. C. 904–911.
6. Chernov V. M. Some spectral properties of fractal curves // Machine Graphics & Vision. 1996. Vol. 5, no. 1/2. P. 413–422.
7. Chernov V. M. Tauber theorems for Dirichlet series and fractals // Proc. ICPR’96. Vienna, 1996. Vol. 2, Track B. P. 656–661. doi: 10.1109/ICPR.1996.546905
8. Brown J. L. Note on complete sequences of integers // The American Math. Monthly. 1961. Vol. 68, no. 6. P. 557–560. doi: 10.2307/2311150
9. Pillai S. S. An arithmetical function concerning primes // Annamalai University J. 1930. pp. 159–167.
10. The On-Line Encyclopedia of Integer Sequences (OEIS). [e-resource]. URL: https://oeis.org/
11. Feinberg M. Fibonacci — Tribonacci. Fibonacci. Quart. 1963. Vol. 1, no. 30. P. 71–74.
12. Noe T. D. Primes in Fibonacci $n$-step and Lucas $n$-step sequences // J. Integer Seq. 2005. Vol. 8, Article 05.4.4. 12 p.
13. Moore T. L. Using Euler’s formula to solve plane separation problems // The College Mathematics J. 1991. Vol. 22, no. 2. P. 125–130. doi:10.2307/2686448
14. Steiner J. Einige Gesetze uber die Theilung der Ebene und des Raumes (A few statements about the division of the plane and of space) // J. Reine Angew. Math. 1826. Vol. 1. P. 349–364. doi: 10.1515/crll.1826.1.349
Поступила 14.04.2020
После доработки 23.06.2020
Принята к публикации 27.07.2020
Чернов Владимир Михайлович
д.-р физ.-мат наук
главный науч. сотрудник
Институт систем обработки изображений РАН,
филиал ФНИЦ “Кристаллография и фотоника” РАН,
г. Самара;
профессор
Самарский национальный исследовательский университет им. академика С.П. Королева,
г. Самара
e-mail: schraube@samtel.ru
Чичева Марина Александровна
канд. техн. наук
старший науч. сотрудник
Институт систем обработки изображений РАН,
филиал ФНИЦ “Кристаллография и фотоника” РАН,
г. Самара;
доцент
Самарский национальный исследовательский университет им. академика С.П. Королева,
г. Самара
e-mail: mchi@geosamara.ru
Ссылка на статью: В.М. Чернов, М.А. Чичева. Дискретные ортогональные преобразования на мультимножествах, ассоциированных с полными последовательностями // Тр. Ин-та математики и механики УрО РАН. 2020. Т. 26, № 3. С. 249-257
English
V.M. Chernov, M.A. Chicheva. Discrete orthogonal transforms on multisets associated with complete sequences
We consider a specific version of the authors’ approach to the synthesis of bases of discrete orthogonal transforms (DOTs). The approach takes into account the relation between the structure of basis functions of a transform and the existence of a certain numeral system on the (multidimensional) index set of the input signal. In contrast to Chernov’s prototype paper “Discrete orthogonal transforms with bases generated by self-similar sequences” (2018), which was concerned with DOTs associated with irredundant numeral systems (where each index of the input signal has a unique representation in a chosen numeral system), in the present paper we study the case of the so-called complete numeral systems. In this case, there is no bijection between the set of input indices of DOTs and the set of their digital representations. Potentially, such statements of applied problems naturally appear in image recognition, artificial intelligence, theory of formal languages, mathematical programming, and other areas where the analyzed objects are characterized by many heterogeneous attributes, which can be quantitative, qualitative, and mixed. There may be several copies of each objects, and the copies may have inconsistent descriptions, which must be considered and analyzed as a whole. Such objects with many attributes can be represented as multisets (“sets with repetitions”). Since discrete spectral analysis is a basic tool for solving the described problems in the classical "multiple” interpretation of objects, we try to extend some ideas and methods of spectral analysis to the case of multiset objects.
Keywords: multisets, discrete orthogonal transformations, complete sequences
Received April 14, 2020
Revised June 23, 2020
Accepted July 27, 2020
Funding Agency: This work was supported by the Ministry of Science and Higher Education of the Russian Federation within the state assignment to the Federal Research Center “Crystallography and Photonics” of the Russian Academy of Sciences (agreement no. 007-GZ/Ch3363/26) in studying numeral systems and by the Russian Foundation for Basic Research (project nos. 19-07-00357_a and 18-29-03135) in studying machine arithmetics.
Vladimir Mikhailovich Chernov, Dr. Phys.-Math. Sci., Prof., Image Processing Systems Institute of the Russian Academy of Sciences — Branch of the Federal Scientific Research Center Crystallography and Photonics of Russian Academy of Sciences, Samara, 443001 Russia; Samara National Research University, Samara, 443086 Russia, e-mail: schraube@samtel.ru
Marina Aleksandrovna Chicheva, Cand. Sci. (Phys.-Math), Image Processing Systems Institute of the Russian Academy of Sciences — Branch of the Federal Scientific Research Center Crystallography and Photonics of Russian Academy of Sciences, Samara, 443001 Russia; Samara National Research University, Samara, 443086 Russia, e-mail: mchi@geosamara.ru
Cite this article as: V.M. Chernov, M.A. Chicheva. Discrete orthogonal transforms on multisets associated with complete sequences, Trudy Instituta Matematiki i Mekhaniki URO RAN, 2020, vol. 26, no. 3, pp. 249–257; Proceedings of the Steklov Institute of Mathematics (Suppl.), 2021, Vol. 313, Suppl. 1, pp. S33–S39.
[References -> on the "English" button bottom right]
