| RUS ENG |
| Полная версия |
|
|
|
| ПЕРСОНАЛИИ |
| Финько Олег Анатольевич |
|
| профессор |
| доктор технических наук (2005) |
# Синтез дискретных устройств реализации систем функций алгебры логики (ФАЛ), программные методы (посредством модулярных ЛОГИКО-ЧИСЛОВЫХ формул).
# Функциональное диагностирование дискретных устройств специального назначения (посредством ЧИСЛОВЫХ кодов).
# Контроль и ОБЕСПЕЧЕНИЕ целостности и имитозащиты данных (посредством КРИПТОКОДОВЫХ конструкций): системы связи, цифровые хранилища данных, спутниковые системы навигации (GNSS).
# Системы электронного документооборота (МЕТОДОЛОГИЯ).
______________________________________________________________
(к п. 1) Упрощается синтез и структура устройств реализации систем ФАЛ (однако получаемые схемы, в общем случае, по отношению к традиционным методам синтеза, – не минимальны). Созданы условия для опосредованного применения числовых методов кодового контроля ошибок вычислений в новой для них предметной области – логических вычислениях.
Рекомендации к применению: синтез аналого-цифровых устройств на перспективной (электрической, оптической и пр.) аналого-дискретной элементной базе (аналоговые преобразования – цифровой выход ), например, основанной на первом законе Кирхгофа.
$\textbf{Логико-числовые формулы реализации двоичных функций}$ (АиТ, 2004, №6. С. 37-60; ОПиПМ, 2006, №4; ОПиПМ, 2016, №2).
$Исходные\ данные:$ числовая нормальная форма (ЧНФ) для булевой функции $f_t(x_1,\, \ldots,\, x_n)$: \begin{eqnarray*} A(x_1,\, \ldots,\, x_n)=b_{0}+\sum^{2^n-1}_{i=1}b_{i}\centerdot \left(x^{i_1}_1 \wedge x^{i_2}_2 \wedge \ldots \wedge x^{i_n}_n \right), \end{eqnarray*} где $b_{0},b_{1},\ldots,a_{k^n-1} \in \mathbb{Z}$; $i_1, i_{2},\ldots,i_n$ – цифры двоичного представления $i$ ($i=\sum_{u=1}^n i_u 2^{n-u}$); $x_u^{i_u}=\left\{ \begin{array}{ll} x_u,& i_u\neq 0, \\ 1,& i_u=0. \end{array} \right. $
Обобщение числовой нормальной формы (ЧНФ) на систему булевых функций в $\mathbb{Z}$ (Малюгин В. Д. АиТ. 1982, №4. 84–93). Система $f_1(x_1,\, \ldots,\, x_n);\ \ldots;\ f_d(x_1,\, \ldots,\, x_n)$: \begin{eqnarray*} C(x_1,\, \ldots,\, x_n)=\sum^{2^n-1}_{i=0}c_i \centerdot \left(x^{i_1}_1 \wedge x^{i_2}_2 \wedge \ldots \wedge x^{i_n}_n \right), \end{eqnarray*} где $c_i\in\mathbb{Z}$; $c_i =\sum^d_{t=1} b_{t,\, i}2^{d-t}$ для $i=0,\,1\, \ldots,\, 2^{n-1}$; при этом, значение полинома $C(x_1,\, \ldots,\, x_n)$ на наборе $x_1,\, \ldots,\, x_n$ есть число $Y^{(x_1,\, \ldots,\, x_n)}=\sum_{t=1}^d f_t(x_1,\, \ldots,\, x_n)2^{d-t}$, а $\left(f_1(x_1,\, \ldots,\, x_n),\ \ldots,\ f_d(x_1,\, \ldots,\, x_n)\right)_2$ – двоичная его запись.
$\blacktriangleright$ $Положение\ 1.$ Обобщение алгебраической нормальной формы (полинома Жегалкина) на область кольца $\mathbb{Z_{2^d}}$ (частный случай ЧНФ В.Д. Малюгина). Система произвольных $f_1(x_1,\, \ldots,\, x_n);\ \ldots;\ f_d(x_1,\, \ldots,\, x_n)$ может быть представлена модулярным логико-числовым полиномом (МЛЧП): \begin{eqnarray} M(x_1,\, \ldots,\, x_n)=\sum^{2^n-1}_{i=0}\psi_i \centerdot \left(x^{i_1}_1 \wedge x^{i_2}_2 \wedge \ldots \wedge x^{i_n}_n \right) \pod{\mathbb{Z}_{2^d}}, \end{eqnarray} где $\psi_i\in\mathbb{Z}_{2^d}$; $\psi_i =\left | \sum_{t=1}^{d}b_{t,\,i} 2^{d-t} \right |_{2^d}=\left | c_i \right |_{2^d}$ для $i=0,\,1\, \ldots,\, 2^{n-1}$; при этом, значение полинома $M(x_1,\, \ldots,\, x_n)$ на наборе $x_1,\, \ldots,\, x_n$ есть число $Y^{(x_1,\, \ldots,\, x_n)}=\sum_{t=1}^d f_t(x_1,\, \ldots,\, x_n)2^{d-t}$, а $\left(f_1(x_1,\, \ldots,\, x_n),\ \ldots,\ f_d(x_1,\, \ldots,\, x_n)\right)_2$ – двоичная его запись.
$\mathbf{Замечание}$. Алгебраическая нормальная форма есть частный случай (1) при $d=1$.
$\textbf{Частный случай – схема Горнера:}$ $$M(x_1,\, \ldots,\, x_n)=\zeta_0 \oplus_p \zeta_1 \left(K_1 \oplus_p \zeta_2\left(K_2 \oplus_p \ldots \oplus_p \zeta_i \left(K_i \oplus_p \ldots \oplus_p \zeta_{2^n-1}K_{2^n-1}\right)\ldots \right)\right) \pod{\mathbb{GF}(m)},$$ где $K_i$ – элементарная $i$-я конъюнкция переменных $x_1,\, \ldots,\, x_n$; $p > 2^d$ – простое; $\zeta_0=\psi_0, \ \ \zeta_i=\left|\frac{\psi_{i}}{\prod_{j=0}^{i-1}\psi_j}\right|_p \ \ (i=1\ldots 2^n-1 )$; или $$M(x_1,\, \ldots,\, x_n)=\xi_0 \oplus_p \xi_1\left(\xi_2^{-1} K_1 \oplus_p \ldots \oplus_p \xi_i \left(\xi_{i+1}^{-1}K_i \oplus_p \ldots \oplus_p \xi_{2^n-2}^{-1}\left(\xi_{2^n-1}^{-1} K_{2^n-2} \oplus_p K_{2^n-1}\right)\ldots\right)\ldots\right)\pod{\mathbb{GF}(m)},$$ где $\xi_0=\psi_0, \ \ \xi_i=\left|\prod_{j=2^n-1}^{i}\xi_j\right|_p \ \ (i=1\ldots 2^n-1 )$.
$\blacktriangleright$ $Положение\ 2.$ Система $f_1(x_1,\, \ldots,\, x_n),\, \ldots,\,f_{d}(x_1,\, \ldots,\, x_n)$ может быть единственным способом задана произведением: \begin{align} N(x_1,\, \ldots,\, x_n)&=\prod_{i=1}^d m_i^{f_i(x_1,\, \ldots,\, x_n)} \nonumber \\ &= \nu_0 \prod_{i=1}^{2^n-1} \nu_i^{x^{i_1}_1 \wedge x^{i_2}_2 \wedge \ldots \wedge x^{i_n}_n} \pod{\mathbb{Z}_{p\geq m+1}}, \end{align} где $m=\prod_{i=1}^d m_i$; $m_t$ $(t=1,\,\ldots,\,d)$ – неповторяющиеся простые (2, 3, и т. д.); $\nu_j=\left | \prod_{t=1}^d m_t^{b_{t,\,j}}\right|_{p\geq m+1}=\left | \prod_{t=1}^d \left | m_t^{b_{t,\,j}}\right|_{p\geq m+1}\right|_{p\geq m+1}$ ($j=0,\, \ldots,\,2^n-1$); $b_{t,\,i}$ $(t=1,\,\ldots,\,d;\ \ i=0,\,1,\,\ldots,\,2^n-1)$ – коэффициенты ЧНФ $t$-й функции; при этом: $$ f_t(x_1,\, \ldots,\, x_n)= \begin{cases} 1, & \ \ m_t | N(x_1,\, \ldots,\, x_n); \\ 0, & \ \ m_t\not|\,N(x_1,\, \ldots,\, x_n). \end{cases} $$
$\textbf{Логико-числовые формулы реализации многозначных функций}$ (АиТ, 2005, №7. С. 66-86; ОПиПМ, 2006, №4).
$Исходные\ данные$ (см., например, Асланова Н. Х., Фараджев Р. Г. АиТ, 1992, №2. С.120-131): числовая нормальная форма для $k$-значной функции $f^{(k)}_t(x_1,\, \ldots,\, x_n)$, при $k>2$ и $k\in \mathbb{Z}$: \begin{eqnarray*} f^{(k)}(x_1,\, \ldots,\, x_n)=a_{0}+\sum^{k^n-1}_{i=1}a_{i}\centerdot \left(x^{i_1}_1 \wedge x^{i_2}_2 \wedge \ldots \wedge x^{i_n}_n \right), \end{eqnarray*} где $a_{0},a_{1},\ldots,a_{k^n-1} \in \mathbb{R}$; $i_1, i_{2},\ldots,i_n$ – цифры $k$-значного представления $i$ ($i=\sum_{u=1}^n i_u k^{n-u}$); $x_u^{i_u}=\left\{ \begin{array}{ll} x_u,& i_u\neq 0, \\ 1,& i_u=0. \end{array} \right. $
$\blacktriangleright$ $Положение\ 3.$ Произвольная $k$-значная $f^{(k)}(x_1,\, x_2, \ldots,\, x_n)$, при $k>2$ и $k\in \mathbb{Z}$ (т. е. не обязательно простом) может быть представлена МЛЧП: \begin{eqnarray} f^{(k)}(x_1,\, x_2, \ldots,\, x_n)=\sum^{k^n-1}_{i=0}\rho_i \centerdot \left(x^{i_1}_1 \wedge x^{i_2}_2 \wedge \ldots \wedge x^{i_n}_n\right) \pod{\mathbb{GF}(m)}, \end{eqnarray} где $m \geq k$ ($m$, очевидно, – простое), $\rho_{i}=\left|a_i\right|_m$.
$\blacktriangleright$ $Обобщение\ положений\ 1\ и\ 3.$ Система произвольных $k$-значных $f_1^{(k)}(x_1,\, x_2, \ldots,\, x_n); \ldots; f_d^{(k)}(x_1,\, x_2, \ldots,\, x_n)$, при $k>2$ и $k\in \mathbb{Z}$ может быть представлена МЛЧП: \begin{eqnarray} \Omega^{(k)}(x_1,\, x_2, \ldots,\, x_n)=\sum^{k^n-1}_{i=0}\omega_i \centerdot \left(x^{i_1}_1 \wedge x^{i_2}_2 \wedge \ldots \wedge x^{i_n}_n\right) \pod{\mathbb{GF}(m)}, \end{eqnarray} где $m > k^d$; $\omega_i=\left|\sum_{t=1}^d a_{t,\,i} k^{d-t}\right|_m$ для $i=0,\,1,\, \ldots k^{n-1}$; при этом, значение полинома $\Omega^{(k)}(x_1,\, x_2, \ldots,\, x_n)$ на наборе $x_1,\, \ldots,\, x_n$ есть число $\sum_{i=1}^d f_i^{(k)}(x_1,\, \ldots,\, x_n)k^{d-i}$, а $\left(f_1^{(k)}(x_1,\, \ldots,\, x_n),\ \ldots,\ f_d^{(k)}(x_1,\, \ldots,\, x_n)\right)_k$ – $k$-ичная его запись.
Для (3) и (4) по аналогии с полиномами для булевых функций строятся схемы Горнера.
$\blacktriangleright$ $Обобщение\ положения \ 2 .$ Система произвольных $k$-значных $f_1^{(k)}(x_1,\, x_2, \ldots,\, x_n); \ldots; f_d^{(k)}(x_1,\, x_2, \ldots,\, x_n)$ может быть представлена логико-числовой формулой: \begin{align} N^{(k)}(x_1,\, \ldots,\, x_n)&=\prod_{i=1}^d m_i^{f^{(k)}_i(x_1,\, \ldots,\, x_n)}\nonumber \\ &=\mu_0 \prod_{i=1}^{k^n-1}\mu_i^{x^{i_1}_1 \wedge x^{i_2}_2 \wedge \ldots \wedge x^{i_n}_n} \pod{\mathbb{Z}_{p\geq m+1}}, \end{align} где $m=\prod_{t=1}^d m_t^{k-1}$; $m_t$ $(t=1,\,\ldots,\,d)$ – неповторяющиеся простые (2, 3, и т. д.); $\mu_j=\left | \prod_{t=1}^d m_t^{a_{t,\,j}}\right|_{p\geq m+1}$ ($j=0,\, \ldots,\,k^n-1$); $a_{t,\,i}$ $(t=1,\,\ldots,\,d;\ \ i=0,\,1,\,\ldots,\,k^n-1)$ – коэффициенты ЧНФ $t$-й $k$-значной функции; при этом: $$ f_t^{(k)}(x_1,\, \ldots,\, x_n)= \alpha, \ \ \mbox{если}\ \ \ m_t^{\alpha} | N^{(k)}(x_1,\, \ldots,\, x_n)\ \ (0 \leq \alpha<k) \ \ \mbox{и} \ \ m_t^{\beta} \not| N^{(k)}(x_1,\, \ldots,\, x_n),\ k>\beta>\alpha. $$
$\mathbf{Замечание}$. В общем случае кодировка значений $f^{(k)}_t(x_1,\, \ldots,\, x_n)$ может включать в себя область отрицательных чисел, например, при $k$ нечетном: $\{ -\frac{k}{2},\, -\left(\frac{k}{2}-1\right),\, \ldots,\,0,\, \ldots,\, \frac{k}{2}-1,\,\frac{k}{2} \}$. Тогда вычисление (5) следует осуществлять уже не в $\mathbb{Z}_p$, а в $\mathbb{GF}(p)$ (т.е. при простом $p$). Кроме того, $\mu_j=\left | \prod_{t=1}^d m_t^{r_{t}a_{t,\,j}}\right|_{p\geq m+1}$ для $j=0,\, \ldots,\,k^n-1$ и $r_{t}=\pm 1$ в зависимости от знака значения $t$-ой функции.
Например, при $k=3$ и области значений $f^{(3)}_t(x_1,\, \ldots,\, x_n)\in \{-1,\,0,\,1\}$: $$ f^{(3)}_t(x_1,\, \ldots,\, x_n)= \begin{cases} 1, & \ \ m_t | N^{(3)}(x_1,\, \ldots,\, x_n); \\ 0, & \ \ m_t\not|\,N^{(3)}(x_1,\, \ldots,\, x_n); \\ -1, & \ \ m_{t_1}^{-1} | N^{(3)}(x_1,\, \ldots,\, x_n). \end{cases} $$ При этом возникает дополнительное требование к выбору простых множителей: $\gcd{(m_{t_1}^{-1}, \, m_{t_2})}=1 \ \ (t_1,\,t_2=1,\,2,\,\ldots,\,d)$.
$\blacktriangleright$ $Положение\ 4.$ Система произвольных $k$-значных $f_1^{(k)}(x_1,\, x_2, \ldots,\, x_n); \ldots; f_d^{(k)}(x_1,\, x_2, \ldots,\, x_n)$ при $k>2$ и $k\in \mathbb{Z}$ может быть представлена МЛЧП: \begin{eqnarray} \Theta^{(k)}(x_1,\, x_2, \ldots,\, x_n)&=&f^{(k)}_1(x_1,\, x_2, \ldots,\, x_n)\frac{mq_1}{m_1}+ \ldots +f^{(k)}_d(x_1,\, x_2, \ldots,\, x_n)\frac{mq_d}{m_d} \pod{\mathbb{Z}_m} \nonumber \\ &=&\zeta_0 + \sum^{k^n-1}_{i=1}\zeta_i \centerdot \left(x^{i_1}_1 \wedge x^{i_2}_2 \wedge \ldots \wedge x^{i_n}_n\right) \pod{\mathbb{Z}_m}, \end{eqnarray} $m>k^d$; $m=\prod_{i=1}^d m_i$; $m_i \geq k$; $m_i$ – неповторяющиеся простые для $\forall i$; $\zeta_i=\left|\sum^{d}_{t=1}a_{t,\,i}\frac{m q_t}{m_t}\right|_m$ для $i=0,\,1,\,\ldots,\,k^n-1$, где $a_{t,\,i}$ – коэффициенты ЧНФ $t$-й $k$-значной функции; $q_i$ удовлетворяет сравнению $q_i m m_i^{-1} \equiv 1 \mod{m}$. Результат вычисления: \begin{eqnarray*} \left\lbrace \begin{split} f_1^{(k)}(x_1,\, \ldots,\, x_n) = \left | \Theta^{(k)}(x_1,\, \ldots,\, x_n) \right |_{m_1} \\ \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \\ f_d^{(k)}(x_1, \ldots,\, x_n) = \left| \Theta^{(k)}(x_1, \ldots,\, x_n) \right |_{m_d}. \end{split} \right. \end{eqnarray*}
ИСТИНА
