Уточненные оценки сложности дешифратора в модели клеточных схем из функциональных и коммутационных элементов

С.А. Ложкин, В.С. Зизов

Московский государственный университет имени М.В. Ломоносова, г. Москва, 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).

Литература

  1. Кравцов С.С. О реализации функций алгебры логики в одном классе схем из функциональных и коммутационных элементов // Проблемы кибернетики. – М.: Наука, 1967. – Вып. 19. – С. 285–292.
  2. Альбрехт А. О схемах из клеточных элементов // Проблемы кибернетики. – М.: Наука, 1975. – Вып. 33. – С. 209–214.
  3. Грибок С.В. Об одном базисе для схем из клеточных элементов // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и кибернетика. – 1999. – № 4. – С. 36–39.
  4. Ложкин С.А. О соотношении между сложностью и площадью клеточных дешифраторов // Проблемы теоретической кибернетики: Тез. докл. XIV Междунар. конф. – М.: Изд-во мех.-матем. фак. МГУ, 2005. – С. 88.
  5. Ложкин С.А., Евдокимова Т.Н. О сложности реализации некоторых систем функций в классе обобщенных клеточных схем // Материалы VIII Междунар. семинара «Дискретная математика и ее приложения». – М.: Изд-во мех.-матем. фак. МГУ, 2004. – С. 61–63.
  6. Ложкин С.А., Пашковский А.М. О сложности реализации некоторых систем функций алгебры логики клеточными и планарными схемами // Проблемы теоретической кибернетики: Тез. докл. IX Всесоюз. конф. – Волгоград, 1991. – Ч. 1. – С. 28.
  7. Грибок С.В. Об асимптотике сложности клеточного контактного дешифратора // Вестн. Нижегор. гос. ун-та. Матем. моделирование и оптимальное управление. – 2000. – Вып. 1. – С. 68–72.
  8. 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.
  9. Шкаликова Н.А. О реализации булевых функций схемами из клеточных элементов // Матем. вопросы кибернетики. – М.: Наука, 1989. – Вып. 2. – С. 177–197.
  10. 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.
  11. Жуков Д.А. О вычислении частичных булевых функций клеточными схемами // Дискрет. анализ и исслед. операций. Сер. 1. – 2004. – Т. 11, № 2. – С. 32–40.
  12. Яблонская А.Ю. О сложности реализации булевых функций из инвариантных классов клеточными схемами ограниченной высоты с кратными входами // Вестн. Нижегор. ун-та им. Н.И. Лобачевского. – 2012. – Т. 1, № 4. – С. 225–231.
  13. Thompson C.D. A complexity theory for VLSI: Ph.D. Thesis. – Pittsburgh, PA: Carnegie Mellon Univ., 1980. – 148 p.
  14. 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.
  15. 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.
  16. Калачев Г.В. Порядок мощности плоских схем, реализующих булевы функции // Дискретн. матем. – 2014. – Т. 26, № 1. – С. 49–74.
  17. Калачев Г.В. Об одновременной оптимизации площади, мощности и глубины плоских схем, реализующих частичные булевы операторы // Интеллектуальные системы. Теория и приложения. – 2016. – Т. 20, № 2. – С. 203–266.
  18. Калачев Г.В. О мощностной сложности плоских схем: Дис. . . . канд. физ.-матем. наук. – М., 2017. – 167 с.
  19. Ложкин С.А. Лекции по основам кибернетики. – М.: Изд. отд. фак. ВМиК МГУ, 2004. – 253 с.
  20. Ложкин С.А. Оценки высокой степени точности для сложности управляющих систем из некоторых классов // Математические вопросы кибернетики. – М.: Наука, 1996. – Вып. 6. – С. 189–214.
  21. Черемисин О.В. Об активности схем из клеточных элементов, реализующих систему всех конъюнкций // Дискрет. матем. – 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.