Материал конференции: "XIV международный научный семинар "Дискретная математика и ее приложения" имени академика О.Б. Лупанова (20-25 июня 2022 г., Москва)"
Авторы:Зизов В.С.
Сложность клеточных дешифраторов с повторяющимися входами
Аннотация:
Модель клеточных схем (КС) впервые была предложена в 1967 году С.С. Кравцовым, им же для неё был получен порядок функции Шеннона. Модель КС является математической моделью интегральных схем (ИС), учитывающей особенности физического синтеза. Наличие требований на геометрию схемы, обеспечивающих учёт необходимых трассировочных ресурсов при создании ИС, представляет собой принципиальное отличие от хорошо изученных классов схем из функциональных элементов (СФЭ). Аналогичная математическая модель в зарубежных источниках была описана в 1980 году К.Д. Томпсоном. Для исследований, связанных с ИС, модель является основополагающей, и считается удовлетворительным приближением для ИС, по крайней мере для монокристаллических систем. Более того, она остаётся точным приближением для небольших участков (отдельных компонентов) ИС в случаях, когда модель не может верно отразить все особенности проектируемых систем. В настоящей работе устанавливаются асимптотические оценки площади клеточных схем, реализующих дешифратор порядка n с повторяющимися входами.
