Prikladnaya Diskretnaya Matematika. Supplement
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Prikl. Diskr. Mat. Suppl.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Prikladnaya Diskretnaya Matematika. Supplement, 2017, Issue 10, Pages 55–56
DOI: https://doi.org/10.17223/2226308X/10/23
(Mi pdma318)
 

This article is cited in 2 scientific papers (total in 2 papers)

Discrete Functions

A condition for uniqueness of linear decomposition of a Boolean function into disjunctive sum of indecomposable functions

A. V. Cheremushkin

Research Institute "Kvant", Moscow
Full-text PDF (522 kB) Citations (2)
References:
Abstract: Let $n\geq1$, $V_n=[\operatorname{GF}(2)]^n$, that is, $V_n$ is the $n$-dimensional vector space over the field $\operatorname{GF}(2)$, and $H_n$ be the group of shifts $\sigma_a\colon V_n\to V_n$ of the space $V_n$ defined as $\sigma_a(x)=a\oplus x$. Let $\mathcal F_n$ be the set of all Boolean functions $f\colon V_n \to \operatorname{GF}(2)$ in $n$ variables and, for integer $t\geq0$, let $\mathcal U_t$ be the set of all functions in $\mathcal F_n$ of degree not more than $t$. Let, at last, $(H_n)_f^{(t)}=\{\sigma_a\colon\sigma_a\in H_n, f(a\oplus x)\oplus f(x)\in\mathcal U_t\}$. We say that functions $g$ and $h$ in $\mathcal F_n$ are equivalent modulo $\mathcal U_t$ and write $g\equiv h\pmod{\mathcal U_t}$ if $g\oplus h\in\mathcal U_t$. Also, we say that a function $f\in\mathcal F_n$ is linearly decomposable into disjunctive sum modulo $\mathcal U_t$ if there exist a linear transformation $A$ of the vector space $V_n$, an integer $k\in\{1,2,\dots,n-1\}$, and some Boolean functions $f_1$ and $f_2$ such that, for any $x=x_1x_2\dots x_n\in V_n$, $f(xA)\equiv f_1(x_1,\dots,x_k)\oplus f_2(x_{k+1},\dots,x_n)\pmod{\mathcal U_t}$. In this case, the right part of the last equivalence is called a linear decomposition of the function $f$ into disjunctive sum modulo $\mathcal U_t$ and $f_1$, $f_2$ are the components of the decomposition. By the principle of mathematical induction, these notions are defined for every number $m\geq2$ of components in the sum and, further, just this definition of the linear decomposition of $f$ into disjunctive sum modulo $\mathcal U_t$ is meant. The main result is the following: if $s\geq2$, $(H_n)_f^{(s-1)}$ is trivial (consists only of the identical shift of $V_n$), and $f$ is linearly decomposable into disjunctive sum modulo $\mathcal U_s$, then there exists an unique linear decomposition $D$ of $f$ into disjunctive sum modulo $\mathcal U_s$ of linearly indecomposable (into disjunctive sum modulo $\mathcal U_s$) components. The term “uniqueness” of the decomposition $D$ means that any other similar decomposition of $f$ gives the same decomposition of $V_n$ into the direct sum of subspaces induced by its components that are, in turn, linearly equivalent modulo $\mathcal U_s$ to components in $D$.
Keywords: Boolean functions, disjunctive sum, linear transformation.
Document Type: Article
UDC: 519.719.325
Language: Russian
Citation: A. V. Cheremushkin, “A condition for uniqueness of linear decomposition of a Boolean function into disjunctive sum of indecomposable functions”, Prikl. Diskr. Mat. Suppl., 2017, no. 10, 55–56
Citation in format AMSBIB
\Bibitem{Che17}
\by A.~V.~Cheremushkin
\paper A condition for uniqueness of linear decomposition of a~Boolean function into disjunctive sum of indecomposable functions
\jour Prikl. Diskr. Mat. Suppl.
\yr 2017
\issue 10
\pages 55--56
\mathnet{http://mi.mathnet.ru/pdma318}
\crossref{https://doi.org/10.17223/2226308X/10/23}
Linking options:
  • https://www.mathnet.ru/eng/pdma318
  • https://www.mathnet.ru/eng/pdma/y2017/i10/p55
  • This publication is cited in the following 2 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Prikladnaya Diskretnaya Matematika. Supplement
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2025