RUS  ENG
Полная версия
ПЕРСОНАЛИИ
Финько Олег Анатольевич
Финько Олег Анатольевич
профессор
доктор технических наук (2005)

Специальность ВАК: 05.13.01 (системный анализ, управление и обработка информации (по отраслям))
Дата рождения: 13.07.1963
E-mail:
Сайт: https://ofinko.ru
Ключевые слова: компьютерная алгебра, модулярная арифметика, система остаточных классов, китайская теорема об остатках, функция алгебры логики, многозначные логические функции, система булевых функций, числовая нормальная форма, алгебраическая нормальная форма, полином Жегалкина, синтез дискретных схем, функциональное диагностирование цифровых устройств, имитозащита, контроль целостности.
Коды УДК: 519.7
Коды MSC: *03B50, 68W30, *68M07, *94C10, 06E30, 13M99

Основные темы научной работы:

# Синтез дискретных устройств реализации систем функций алгебры логики (ФАЛ), программные методы (посредством модулярных ЛОГИКО-ЧИСЛОВЫХ формул).

# Функциональное диагностирование дискретных устройств специального назначения (посредством ЧИСЛОВЫХ кодов).

# Контроль и ОБЕСПЕЧЕНИЕ целостности и имитозащиты данных (посредством КРИПТОКОДОВЫХ конструкций): системы связи, цифровые хранилища данных, спутниковые системы навигации (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*}


Основные публикации:
  1. Финько О. А., Модулярная арифметика параллельных логических вычислений, ред. В. Д. Малюгин, ИПУ РАН, М., 2003, 224 с.  elib
  2. Финько О. А., “Реализация систем булевых функций большой размерности методами модулярной арифметики”, Автоматика и телемеханика, 2004, № 6, 37–60  mathnet  crossref  mathscinet  zmath  isi  scopus
  3. Финько О. А., “Модулярные формы систем $k$-значных функций алгебры логики”, Автоматика и телемеханика, 2005, № 7, 66–86  mathnet  crossref  mathscinet  zmath  scopus
  4. Ткаченко А.В., Финько О.А., “Синтез и преобразование сложных структурных кодов”, Автоматика и телемеханика, 1995, № 5, 183–189  mathnet  zmath  isi  scopus
  5. Oleg Finko, Sergey Dichenko, “Two-dimensional control and assurance of data integrity in information systems based on residue number system codes and cryptographic hash functions”, Proceedings of the 2018 Multidisciplinary Symposium on Computer Science and ICT (Stavropol, Russia, October 15, 2018), 2254, CEUR Workshop Proceedings, 2018, 8 p.  scopus

Публикации за последние годы

Персональные страницы:

Организации:


© МИАН, 2024