С.А. Ложкин, В.С. Зизов
Московский государственный университет имени М.В. Ломоносова, г. Москва, 119991, Россия
Полный текст PDF
DOI: 10.26907/2541-7746.2020.3.322-334
Для цитирования: Ложкин С.А., Зизов В.С. Уточненные оценки сложности дешифратора в модели клеточных схем из функциональных и коммутационных элементов // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. – 2020. – Т. 162, кн. 3. – С. 322–334. – doi: 10.26907/2541-7746.2020.3.322-334.
For citation: Lozhkin S.A., Zizov V.S. Refined estimates of the decoder complexity in the model of cellular circuits with functional and switching elements. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2020, vol. 162, no. 3, pp. 322–334. doi: 10.26907/2541-7746.2020.3.322-334. (In Russian)
Аннотация
Рассмотрена модель клеточных схем (КС) в одном базисе из функциональных и коммутационных элементов, который построен на основе стандартного базиса Б0, состоящего из функций алгебры логики (ФАЛ) x1 & x2, x1 ∨ x2, ˉx1. В рамках этой модели входы и выходы КС Σ, которым сопоставляются различные выходные и выходные булевы переменные (БП), бесповторно располагаются на границе соответствующей ей прямоугольной решетки, а сама КС Σ как структурно, так и функционально соответствует некоторой схеме из функциональных элементов (СФЭ) в базисе Б0 с теми же наборами входных и выходных булевых переменных.
Исследована сложность (площадь) КС с n входами и 2n выходами, которая реализует систему из всех 2n элементарных конъюнкций ранга n от входных булевых переменных, то есть дешифратор порядка n . Доказано, что минимально возможная площадь клеточной схемы, реализующей дешифратор порядка n , n = 1, 2,…, равна n2n−1(1 + O(1/n)), тем самым, для нее впервые в модели КС получены так называемые асимптотические оценки высокой степени точности, то есть оценки с относительной погрешностью порядка O(1/n).
Ключевые слова: функциональные элементы, коммутационные элементы, клеточные схемы, площадь, дешифратор, асимптотические оценки
Благодарности. Работа выполнена при поддержке гранта Московского центра фундаментальной и прикладной математики и РФФИ (проект № 18-01-00800).
Литература
- Кравцов С.С. О реализации функций алгебры логики в одном классе схем из функциональных и коммутационных элементов // Проблемы кибернетики. – М.: Наука, 1967. – Вып. 19. – С. 285–292.
- Альбрехт А. О схемах из клеточных элементов // Проблемы кибернетики. – М.: Наука, 1975. – Вып. 33. – С. 209–214.
- Грибок С.В. Об одном базисе для схем из клеточных элементов // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и кибернетика. – 1999. – № 4. – С. 36–39.
- Ложкин С.А. О соотношении между сложностью и площадью клеточных дешифраторов // Проблемы теоретической кибернетики: Тез. докл. XIV Междунар. конф. – М.: Изд-во мех.-матем. фак. МГУ, 2005. – С. 88.
- Ложкин С.А., Евдокимова Т.Н. О сложности реализации некоторых систем функций в классе обобщенных клеточных схем // Материалы VIII Междунар. семинара «Дискретная математика и ее приложения». – М.: Изд-во мех.-матем. фак. МГУ, 2004. – С. 61–63.
- Ложкин С.А., Пашковский А.М. О сложности реализации некоторых систем функций алгебры логики клеточными и планарными схемами // Проблемы теоретической кибернетики: Тез. докл. IX Всесоюз. конф. – Волгоград, 1991. – Ч. 1. – С. 28.
- Грибок С.В. Об асимптотике сложности клеточного контактного дешифратора // Вестн. Нижегор. гос. ун-та. Матем. моделирование и оптимальное управление. – 2000. – Вып. 1. – С. 68–72.
- Lozhkin S.A., Evdokimova T.N. On the asymptotics of complexity of a universal cellular contact multiterminal circuit // Moscow Univ. Comput. Math. Cybern. – 2005. – No 4. – P. 32–41.
- Шкаликова Н.А. О реализации булевых функций схемами из клеточных элементов // Матем. вопросы кибернетики. – М.: Наука, 1989. – Вып. 2. – С. 177–197.
- Hromkovich Yu., Lozhkin S., Rybko A., Sapozhenko A., Shkalikova N. Lower bounds on the area complexity of Boolean circuits // Theor. Comput. Sci. – 1992. – V. 97, No 2. – P. 285–300. – doi: 10.1016/0304-3975(92)90079-U.
- Жуков Д.А. О вычислении частичных булевых функций клеточными схемами // Дискрет. анализ и исслед. операций. Сер. 1. – 2004. – Т. 11, № 2. – С. 32–40.
- Яблонская А.Ю. О сложности реализации булевых функций из инвариантных классов клеточными схемами ограниченной высоты с кратными входами // Вестн. Нижегор. ун-та им. Н.И. Лобачевского. – 2012. – Т. 1, № 4. – С. 225–231.
- Thompson C.D. A complexity theory for VLSI: Ph.D. Thesis. – Pittsburgh, PA: Carnegie Mellon Univ., 1980. – 148 p.
- Chazelle B., Louis M. A model of computation for VLSI with related complexity results // J. Associat. Comput. Machinery. – 1985. – V. 32, No 3. – P. 573–588.
- Bilardi G., Pracchi M., Preparata F.P. A critique of network speed in VLSI models of computation // IEEE J. Solid-State Circuits. – 1982. – V. 17, No 4. – P. 696–702. – doi: 10.1109/JSSC.1982.1051799.
- Калачев Г.В. Порядок мощности плоских схем, реализующих булевы функции // Дискретн. матем. – 2014. – Т. 26, № 1. – С. 49–74.
- Калачев Г.В. Об одновременной оптимизации площади, мощности и глубины плоских схем, реализующих частичные булевы операторы // Интеллектуальные системы. Теория и приложения. – 2016. – Т. 20, № 2. – С. 203–266.
- Калачев Г.В. О мощностной сложности плоских схем: Дис. . . . канд. физ.-матем. наук. – М., 2017. – 167 с.
- Ложкин С.А. Лекции по основам кибернетики. – М.: Изд. отд. фак. ВМиК МГУ, 2004. – 253 с.
- Ложкин С.А. Оценки высокой степени точности для сложности управляющих систем из некоторых классов // Математические вопросы кибернетики. – М.: Наука, 1996. – Вып. 6. – С. 189–214.
- Черемисин О.В. Об активности схем из клеточных элементов, реализующих систему всех конъюнкций // Дискрет. матем. – 2003. – Т. 15, № 2. – С. 113–122.
Поступила в редакцию 12.08.2020
Ложкин Сергей Андреевич, доктор физико-математических наук, заведующий кафедрой математической кибернетики факультета вычислительной математики и кибернетики
Московский государственный университет имени М.В. Ломоносова Ленинские горы, д. 1, г. Москва, 119991, Россия
E-mail: lozhkin@cs.msu.ru
Зизов Вадим Сергеевич, магистр кафедры математической кибернетики факультета вычислительной математики и кибернетики
Московский государственный университет имени М.В. Ломоносова Ленинские горы, д. 1, г. Москва, 119991, Россия
E-mail: vzs815@gmail.com
Контент доступен под лицензией Creative Commons Attribution 4.0 License.