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

Рассмотрена модель клеточных схем (КС) в одном базисе из функциональных и коммутационных элементов, который построен на основе стандартного базиса Б$_0$, состоящего из функций алгебры логики (ФАЛ) $x_1 \& x_2, $ $ x_1\lor x_2, $ $\overline{x}_1$. В рамках этой модели входы и выходы КС $\Sigma$, которым сопоставляются различные выходные и выходные булевы переменные (БП), бесповторно располагаются на границе соответствующей ей прямоугольной решетки, а сама КС $\Sigma$ как структурно, так и функционально соответствует некоторой схеме из функциональных элементов (СФЭ) в базисе Б$_0$ с теми же наборами входных и выходных булевых переменных.
Исследована сложность (площадь) КС с $n$ входами и $2^n$ выходами, которая реализует систему из всех $2^n$ элементарных конъюнкций ранга $n$ от входных булевых переменных, то есть дешифратор порядка $n$. Доказано, что минимально возможная площадь клеточной схемы, реализующей дешифратор порядка $n$, $n = 1, 2, \dots$, равна $n2^{n-1}(1+\mathcal{O}({1}/{n}))$, тем самым, для нее впервые в модели КС получены так называемые асимптотические оценки высокой степени точности, то есть оценки с относительной погрешностью порядка $\mathcal{O} ({1}/{n})$.