Підхід до позиційної алгебри логіки
The method of Boolean function representation in terms of positional logic algebra in compact operator form is offered. Compared with the known method, it uses position operators with a complexity of no more than two and only one type of equivalent transformations. The method is less labor intensive...
Збережено в:
| Дата: | 2023 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Англійська |
| Опубліковано: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2023
|
| Теми: | |
| Онлайн доступ: | https://journal.iasa.kpi.ua/article/view/273578 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | System research and information technologies |
| Завантажити файл: |  |
Репозитарії
System research and information technologies| _version_ | 1867334431336824832 |
|---|---|
| author | Kovalov, Mykola |
| author_facet | Kovalov, Mykola |
| author_institution_txt_mv | [
{
"author": "Mykola Kovalov",
"institution": "National Technical University of Ukraine \"Igor Sikorsky Kyiv Polytechnic Institute\", Kyiv"
}
] |
| author_sort | Kovalov, Mykola |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2023-05-24T21:28:17Z |
| description | The method of Boolean function representation in terms of positional logic algebra in compact operator form is offered. Compared with the known method, it uses position operators with a complexity of no more than two and only one type of equivalent transformations. The method is less labor intensive. It allows parallelizing logic calculations. The corresponding way of Boolean function implementation is developed. It competes with some known ways in terms of hardware complexity, resource intensity, and speed when implemented on an FPGA basis. Possibilities open up for creating effective automating means of representing Boolean functions from a large number of variables, synthesizing the corresponding LCs, and improving modern element bases. |
| doi_str_mv | 10.20535/SRIT.2308-8893.2023.1.11 |
| first_indexed | 2025-07-17T10:28:04Z |
| format | Article |
| fulltext |
M. Kovalov, 2023
Системні дослідження та інформаційні технології, 2023, № 1 129
UDC 004.047
DOI: 10.20535/SRIT.2308-8893.2023.1.11
APPROACH TO POSITIONAL LOGIC ALGEBRA
M. KOVALOV
Abstract. The method of Boolean function representation in terms of positional
logic algebra in compact operator form is offered. Compared with the known
method, it uses position operators with a complexity of no more than two and only
one type of equivalent transformations. The method is less labor intensive. It allows
parallelizing logic calculations. The corresponding way of Boolean function imple-
mentation is developed. It competes with some known ways in terms of hardware
complexity, resource intensity, and speed when implemented on an FPGA basis.
Possibilities open up for creating effective automating means of representing Boo-
lean functions from a large number of variables, synthesizing the corresponding
LCs, and improving modern element bases.
Keywords: boolean functions, positional logic algebra, positional operators, equiva-
lent transformations, logic circuits, FPGA.
INTRODUCTION
The development of information systems involves a significant expansion and
complication of logic calculations. Therefore, the development of new directions
in the study and implementation of Boolean functions (BF), one of which is posi-
tional logic algebra of (PLA), seems promising. It includes principles and
methods that allow BF representing and calculating using equivalent transforma-
tions and positional operators with polynomial complexity [1]. The application of
positionality principles for arithmetic and parallelization of logic calculations is
substantiated in PLA [1, 2]. Therefore, effective application of its apparatus is
possible for artificial intelligence, pattern recognition, cryptography and etc.,
where it is necessary to operate BF from a large number of variables.
However, the following problems might be identified within PLA framework:
cumbersome apparatus of sequentially performed equivalent transforma-
tions -, -, -, , i-inversions; -permutations; multi-parametric -, -,
-, -transformations) and complex positional operators). The known method
of BF representing from n variables [1] actually includes cumbersome analysis of
many n order operators. The operator, which generates the most similar BF and
has identical level, is chosen from them. After that with no less difficulty a se-
quence of multi-parameter equivalent transformations is selected. Therefore, for
large n value, the application of the method is significantly labor-intensive;
researches within PLA framework were mainly theoretical (solving a
complex systems of logic equations, determining ratios of NP- and P-complete
problem classes, etc.). Its practical application has not been considered enough [2, 3].
In view of these problems, it is reasonable not to idealize PLA and to oppose
it to Boolean algebra, but interaction. Therefore, a less labor-intensive method of
BF representing was proposed. It does not involve enumeration of solutions, but
the formation process of less complex operators, only one type of equivalent
M. Kovalov
ISSN 1681–6048 System Research & Information Technologies, 2023, № 1 130
transformations and some Boolean algebra apparatus. Also, prerequisites are cre-
ated for logic calculations parallelization. In accordance with the method hard-
ware implementation of the BF was developed, which competes with some
known methods in terms of hardware complexity, resource intensity and speed.
BF REPRESENTATION
The essence of the offered method is in the following. An arbitrary BF is covered
by its fragments given by the corresponding conjunctions. For each of them, a
simple positional operator can be formed, which generates closed BF of the frag-
ment, which must be corrected to obtain exact BF values:
)))(][()((~ 01
1
kicork
k
jkicort
kn
t
i XfXXfxf
i
S , (1)
here kX — input argument vector with k digit capacity;
t
kn
t
x~
1
— ( kn )-rank
conjunction ( nt ,1 ), which defines if fragment; k
ji
S — simple positional
operator (ji — binary vector of operator with dimension ( 1k ), 120 1 kj ;
k — operator order, nk ), which generates the BF-prototype (the closest to the
if ). BF-correction 1
icorrf has “1” values on those kX vectors, where k
ji
S has “0”
values but if has “1” values; BF-correction 0
icorrf has “0” values on those kX
vectors, where k
ji
S has “1” values but if has “0” values.
The covering process begins with shaping and analysis of great fragments.
With a large number of differences between BF-prototypes and fragments its sizes
should be reduced. For this reason, the BF might be covered by the operator's re-
cords (1) fast enough. If we disjunctively combine records (1) and transform the
resulting expression to the operator form, it will be received a representation of
the original BF in PLA terms. Obviously, it is necessary to minimize complexity
of such representation. There is no general decision of this minimization task.
Larger fragments may have many corrections, but smaller fragments may result in
a large number of fragments and records (1) respectively. Therefore, the follow-
ing rule is developed. If 1
icorrf and 0
icorrf don’t require large number of operators
(usually two), it is not further defragmentation. And according record (1) includes
in BF representation. On the other hand, the method does not need more complex
transformations of input arguments as inverting. For this reason, from large num-
ber of equivalent transformations it is expedient to use one-parameter w trans-
formation. It inverts binary digits of argument corresponding to “1” in binary w
code. For example, ][10
4
16 abcdSdcba . It is obvious that the implementation
of such transformation is trivial. So, the process of BF representing is as follows:
1. The set F of fragment representations in the form (1) that cover BF is as-
sumed to be empty. In set G of conjunctions that define analyzed fragments in-
clude initial BF Z.
2. If set G is empty, then go to step 9.
Approach to positional logic algebra
Системні дослідження та інформаційні технології, 2023, № 1 131
3. For each analyzed fragment in the set G generate:
– a binary vector )...( 0 kjjj of a simple positional operator k
jl
S that gen-
erates the BF-prototype, the closest to )( klpr Xf . Here 1mj )0( km , if
the case number when lf =1 on vectors kX with m 1's digits exceeds half of the
total number of such vectors, else 0mj ;
– estimate the operator number for describing of BF corrections )(1
klcorr Xf
and )(0
klcorr Xf based on mismatches between lf and )( klpr Xf .
4. Select a fragment sf with the simplest records of BF corrections.
5. If )(1
klcorr Xf and )(0
klcorr Xf records in PLA terms don’t require large
number of operators (typically two) then go to step 7.
6. Include in set G all conjunctions of the next ( 1 kn )-rank, which de-
fine non-empty sf fragments. Go to step 8.
7. The selected fragment sf written in form (1) include in the set F.
8. Exclude from G conjunction defining sf and alternative conjunctions ob-
tained with it in step 7, except the conjunction with which chosen conjunction can
be glued. Go to step 2.
9. Disjunctively merge all records in form (1) of fragments included in the
set F, obtaining a combined original BF representation. It includes positional op-
erators and logic operations of Boolean algebra:
,
1
i
r
i
fZ
(2)
where r — number of resulting fragments if )1( ri .
10. Open all brackets in (2) and simplify it using Boolean algebra relations.
11. The original BF representation obtained in previous step is finally re-
duced to an operator form using relations between PLA and Boolean algebra, for
example:
]...[~...~
121 aaSaa nw
n
n n ; (3)
]...[... 1221 1 aaSaa n
n
n n ; (4)
]...[]...[~...~
1211 1 aaSSaaSaa nw
k
j
kn
k
k
jkn kn
. (5)
Example. Let some BF )( 5XfF has values “1” on vectors 1–3, 13–15,
19, 21–23 and 25–28. Following the known method [1], BF can be represented by
a complex positional operator and a sequence of equivalent two-parameter trans-
formations like this:
]12345[16
17
16
18
23
20
21
24
19
29
17
30
4
14
1
4 xxxxxSSZ . (6)
The BF representation following the proposed method looks like:
s. 1: }.{{}; ZGF
M. Kovalov
ISSN 1681–6048 System Research & Information Technologies, 2023, № 1 132
Cycle 1:
s. 2: G is non-empty, go to s. 3.
s. 3–5: for Z form: ]12345[)12345( 5
24 xxxxxxxxxxf Zpr S .
)12345(1 xxxxxf Zcorr has values “1” on vectors 1–3, )12345(0 xxxxxf Zcorr has
values “0” on vectors 1–3, 7, 11, 29, 30. To record them more than 2 operators are
required, hence go to s. 6.
s. 6, 8: }5,4,3,2,1,5,4,3,2,1{ xxxxxxxxxxG .
Cycle 2:
s. 2: G is non-empty, go to s. 3.
s. 3–5: the fragment defined by the conjunction 1x requires the simplest cor-
rections. For it ]2345[)2345( 4
81
xxxxxxxxf
xpr
S . There is no need in
)2345(0
1
xxxxf
xcorr
, only one operator is enough for )2345(1
1
xxxxf
xкор
defining
on vector 1 ( 2345 xxxx =0001), hence go to s. 7.
s.7: write the selected fragment in the form (1) as 1xf
)2345]2345[(1 4
8 xxxxxxxxSx . Hence )}2345]2345[(1{ 4
8 xxxxxxxxSxF .
s. 8: }1{xG .
Cycle 3:
s. 2: G is non-empty, go to s. 3.
s. 3–5: for the fragment defined by conjunction 1x , form
]2345[)2345( 4
131 xxxxxxxxf xpr S . )2345(1
1 xxxxf xcorr has value “1” on vec-
tor 1, а )2345(0
1 xxxxf xcorr — has value “0” on vectors 3, 5, 14. More than 2 op-
erators are required to write them, hence go to s. 6.
s. 6, 8: }51,41,31,21,51,41,31,21{ xxxxxxxxxxxxxxxxG .
Cycle 4:
s. 2: G is non-empty, go to s. 3.
s. 3–5: the fragment defined by the conjunction 21xx does not require cor-
rection. For it ]345[)345( 3
521
xxxxxxf
xxpr
S . Go to s. 7.
s. 7: write the selected fragment in the form (1) as
]345[21 3
521
xxxSxxf
xx
. Hence ),2345]2345[(1{ 4
8 xxxxxxxxSxF
]}345[21 3
5 xxxSxx .
s. 8: }21{ xxG .
Cycle 5:
s. 2: G is non-empty, go to s. 3.
s. 3–5: for the fragment defined by conjunction 21xx , form
]345[)345( 3
521 xxxxxxf xxpr S . )345(1
21 xxxf xxcorr has value “1” on vector 4,
only one operator is enough for it, there is no need in 0
21xxкорf . Go to s. 7.
Approach to positional logic algebra
Системні дослідження та інформаційні технології, 2023, № 1 133
s. 7: write the selected fragment in the form (1) as 21xxf
)345]345[(21 3
5 xxxxxxSxx . Therefore ),2345]2345[(1{ 4
8 xxxxxxxxSxF
)}345]345[(21],345[21 3
5
3
5 xxxxxxSxxxxxSxx .
s. 8: }1{xG .
The set G is empty. Entire original BF is covered with fragments from the
set F, so go to s. 9.
s. 9: Get first Z representation:
]345[21)2345]2345[(1 3
5
4
8 xxxSxxxxxxxxxxSxZ
)345]345[(21 3
5 xxxxxxSxx . (7)
s. 10: Open brackets in (7):
]345[2112345]2345[1 3
5
4
8 xxxSxxxxxxxxxxxSxZ
12345]345[21 3
5 xxxxxxxxSxx .
Glue 3rd and 4th conjunctions and select common variables in the 2nd and
5th conjunctions:
].345[1)1515(234]2345[1 3
5
4
8 xxxSxxxxxxxxxxxxSxZ (8)
s. 11: expression in brackets of the second term in (8) might be written as
]15[2
5 xxS , for each conjunction, use (5). It is necessary to use corresponding one-
parameter transformations w for variable inverting (3):
]3451[]15234[]23451[ 3
5
1
424
2
5
3
1616
4
8
1
4 xxxxSSxxxxxSSxxxxxSSZ .
Now apply (4) and finally get original BF representing as:
]]3451[],15234[],23451[[ 3
5
1
424
2
5
3
1616
4
8
1
4
3
14 xxxxSSxxxxxSSxxxxxSSSZ . (9)
This example shows that the internal operators in complex positional opera-
tors serve to set the BF-prototypes of fragments, and the external ones set con-
junctions that uniquely determine these fragments. Therefore, the complexity of
positional operators in such representing in most does not exceed two, while
maintaining their compactness.
According to representation (9), it is possible to build a flow graph of logic
calculations (Fig. 1). If it is assumed that transformation and operator are per-
formed during the same time, then the calculation of the BF will take 4 steps. The
sequential process of calculating the same BF according to expression (6) lasts 8
steps. It might also be seen that, compared with the known method, the proposed
method also allows parallelize execution of positional operators and equivalent
transformations, reducing the time for BF calculating.
It is difficult to compare the complexities of the proposed and known [1]
methods directly. However, it might be done by evaluating the number of ana-
lyzed fragments in the maximum case and positional operators of order n. In ac-
cordance with the proposed method, first, the entire original BF is considered,
M. Kovalov
ISSN 1681–6048 System Research & Information Technologies, 2023, № 1 134
then — )2( n fragments depend on (n–1) variables, then — ))1(2( 2 n frag-
ments on (n–2) variables, etc. Therefor the maximum number of fragments is
evaluated as 1n
fN 2 . Estimating the number of operators analyzed in accor-
dance with the known method reduces to the combinatorial task of partitioning
the number n into terms. Using the Hardy-Ramanujan formula [4] and consider-
ing that for any complexity and order n it might be build )2( 1n operators at least,
get
2
1 32
4 3
n
n
op
e
N
n
all types positional operators. Obviously, the developed
method is significantly less labor intensive.
HARDWARE IMPLEMENTATION
The BF implementation in accordance with the proposed method is a combina-
tional logic circuit (LC). It should be based on the form (2). For example, hard-
ware implementation of the conjunctions and disjunctions in (1) and (2) is more
efficient directly using logic elements. And BF corrections are implemented in
accordance with their disjunctive normal form. The maximum number of frag-
ments in form (2) is a power of two. Hence the same number of identical func-
tional blocks (FBs) is applicable for its implementation, as well as the correspond-
ing number of other logic blocks and elements. Thus, structure of such LC
(Fig. 2) includes:
( 12 kn ) blocks for determining the number of “1” in the input argument
vector kX ;
( kn2 ) FBs for fragments if implementing;
OR logic element 4 for disjunction implementing in accordance with the
form (2).
Each FB contains:
group of logic elements 1, which with the corresponding block for determin-
ing the number of “1” implements a simple positional operator ][ k
k
j X
i
S for cur-
rent fragment;
]2...51[16 xxx
]1...4[4
8 yyS
]15[4 tyS 2
]654[14 tttS 3
t1
]152...4[24 xxxx
]12[2
5 yyS
]23...5[4
16 tyyS
5Y
t2
]3...5[3
5 xxS
]31[2
4 txS
t3
t4 t5 t6
5Y
Z
Fig. 1. Flow graph of logic calculations )( 5XfZ
Approach to positional logic algebra
Системні дослідження та інформаційні технології, 2023, № 1 135
l correction blocks (CBs “0” or “1”), that implement respectively BF-
corrections )(0
kicorr Xf and )(1
kicorr Xf with a group of logic elements 2. Each of
them is a k-input logic element AND with controlled input inverters;
block 3 of logic element AND, one input of which is the if value. Remain-
ing (n-k) inputs have controlled inverters for the implementation of the conjunc-
tion
t
kn
t
x~
1
accordance with (1).
Input signals of the LC:
input vector of arguments Xn (input X);
kn2 vectors of positional operators (input S);
kn2 control signals for CB inverters (input M);
kn2 control signals for inverters of block 3 (input N).
The number of BFs, calculable by the LC, is directly determined by thes
number and bit capacity k of FBs, CBs:
1
0
22 )()),((
kn
i
frBFPALBF
ikn
inlkNN , (10)
where ),( lkN frBF – the number of BFs depending on k variables, which, taking
into account l CBs “0” and “1”, are calculated by one FB.
Fig. 2. LC for the BF implementation by the proposed method
M. Kovalov
ISSN 1681–6048 System Research & Information Technologies, 2023, № 1 136
Being a complex combinatorial dependence 12 n
PALBFN (number of all
simple positional operators). Therefore, this LC is capable to calculate a large
number of practically used regular BFs depend on n variables. In addition, many
partially defined BFs might be extended to a form convenient for calculating on
similar LCs.
The following hardware characteristics of the proposed LC were defined:
– complexity as a number of two-input logic elements:
1))58(43(2)2,( 22 lknknL kn
PAL ; (11)
– LC depth defined as a number of cascades on signal way from input to
output through the block for determining the number of “1”, groups 1, 2 of logic
elements and block 3:
1)[(log][log] 22 knkknTPAL ; (12)
– input numbers:
)1)12(2(2 lknnN kn
PALin . (13)
The developed LC allows to simply change the number and bit capacity of
the main logic blocks. It allows flexible change the ratio between its functionality
and hardware requirements, that follows from (10)–(13).
Let’s implement BF considered in the example by this LC. According the
LC structure, it is necessary transform (7) so that all operators have same order 3.
Simple positional operator ][ k
k
j XS might be represented with simple operators
of smaller order in the next way:
]......[]......[]......[ 111
1
2111
1
11 xxxxxxxxxxxxx iik
k
jiiik
k
jiik
k
j
SSS . (14)
Using (14), represent the first operator in (7) as:
]345[2]345[2]2345[ 3
4
3
8
4
8 xxxSxxxxSxxxxxS .
Transform (7) to the form:
]345[21)345]345[(21 3
4
3
8 xxxSxxxxxxxxSxxZ
)345]345[(21]345[21 3
5
3
5 xxxxxxSxxxxxSxx , (15)
getting 4 fragments described by operators 3
5
3
5
3
4
3
8 ,,, SSSS . The first and last of
them are corrected by 3451
1 xxxfcorr and 3451
4 xxxfcorr respectively. There-
fore, for BF calculating in the form (15) it is suitable LC that includes 3-bit 2
blocks determining the number of “1” and 4 FBs, including one CB per block.
The input variables are inverted according to the input control signals M and N.
Zero values might be entered to the information inputs of unused CBs of FBs 2
and 3. Thus, LC inputs (Fig. 2) are:
blocks determining the number of “1”: 212 xx hh
1 XX ; l
2
l
1 XX
345 xxx ;
Approach to positional logic algebra
Системні дослідження та інформаційні технології, 2023, № 1 137
FB 1: 10001S , 1111M , 101N ;
FB 2: 01001S , 0002M , 112N ;
FB 3: 01013S , 0003M , 013N ;
FB 4: 01014S , 0114M , 004N .
PRACTICAL RESEARCH
In practical research, in addition to the developed method some known ways of
BF implementation [5] were considered. They implement any BF depend on n
variables with optimal hardware complexity:
– multiplexer with ( 1)n selector inputs based on a rectangular decoder [6].
The values of its hardware complexity, depth and number of inputs are:
3223)2,( 21
n
n
MUXnL , (16)
2
3n
TMUX , (17)
12 1 nN n
MUXin ; (18)
– LC based on the cascade method [7]:
)12(3)2,( 1 n
cascnL , (19)
)1(2 nTcasc , (20)
12 1 nN n
cascin . (21)
Dependences of hardware complexity, depth, number of LC inputs are based
on (10)–(13), (16)–(21). Also, for the developed LC structure with a different
number of FBs and CBs (l CB “0” and “1” in each FB) the number of countable
BFs depend on the number of variables n is obtained. The parameters of resource
intensity and speed of the FPGA-based (Field Programmable Gate Array) imple-
mentation of the proposed LC were gotten. Schemes were described on VHDL,
synthesis and modeling were carried out using Intel Quartus Prime and Siemens
Modelsim. Comparative studies are made.
Dependencies on Fig. 3 and 4 (given on a logarithmic scale) show that FB
number increasing (a k decreasing at invariable n) leads to the significant increase
of the calculable BF number and hardware complexity of the proposed LC (de-
pendencies 2, 5 and 7). However, it makes sense to increase, the number of CBs
within the FB. This can increase the functionality of the proposed LC to the level
provided by a large number of FBs, but with lower hardware costs (dependen-
cies 4–6). When 7n developed LC structure provides an overwhelming
advantage sod.
M. Kovalov
ISSN 1681–6048 System Research & Information Technologies, 2023, № 1 138
The resource intensity of the FPGA-based LC implementations (Fig. 5) at
most corresponds its hardware complexity (Fig. 3). When 10n the proposed
LC provides a significant advantage over the known ways also in the LC input
numbers (Fig. 6). From these dependences it is shown that for functionality ex-
panding and equipment minimizing more effectively increase the CB number.
The depth of the developed LC (Fig. 7) depends mainly on n, so the depend-
ences 1, 2, 5 and 7 are close to each other. A similar trend is observed for the per-
formance of LC integral implementations (dependencies 1, 2, 4–7 on Fig. 8). Al-
though the LCs based on multiplexer or cascade method, when implemented on
FPGA basis, have less depth, but the difference in performance is practically lev-
eled. The proposed LC structure may provide higher performance when a large
number of variables (n>11).
СONCLUSIONS
In comparison with the known method the developed method of boolean function
representation in terms of PLA is characterized by the following:
– uses positional operators with complexity no more than two and only one
type of equivalent transformations;
Fig. 6. LC input numbersFig. 5. Resource intensity of the LC integral
implementations
Fig. 3. Hardware complexity of LCs Fig. 4. Number of calculable BFs
Approach to positional logic algebra
Системні дослідження та інформаційні технології, 2023, № 1 139
– less labor intensive and compactness of BF representation;
– allows to parallelize execution of equivalent transformations and operators,
reducing BF calculation time.
The developed LC structure, in comparison with some known ways of BF
implementation, has a significantly fewer hardware complexity when 7n . As a
result, corresponding FPGA-based implementation also requires fewer logic re-
sources and input number without losing in performance. To expand its function-
ality, it is more efficient to increase the number of CBs in FBs. The regularity and
scalability of the LC structure provide effective control the involvement in opera-
tion process its parts by using, for example, “operand isolation” technology [8, 9].
This creates the prerequisites to change flexible the ratio between LC functional-
ity, technical and economic parameters of the integral implementation, “bypass-
ing” possible failures, increasing its reliability. In addition, possibilities for creat-
ing effective automating means of representing BF from a large number of
variables, synthesizing the corresponding LCs and modern element bases im-
provement open up.
REFERENCES
1. M. Telpiz, Algebra of positional operators and equivalent transformations. M.: Sci-
entific advice on a complex problem, 1988.
2. C.M. Hamann and L. Chtcherbanski, “Positional Logic Algebra — PLA – A Fasci-
nating Alternative Approach,”ICSI Technical Report TR-97-039, Sep. 1997.
3. M.I. Telpiz, “Sigma-notation and the equivalence of p and np classes,”J. Inf. Organ.
Sci., vol. 29, no. 2, Mar. 2012.
4. T. Jiang and K. Wang, “A generalized Hardy-Ramanujan formula for the number of
restricted integer partitions,”Journal of Number Theory, vol. 201, pp. 322–353, Aug.
Fig. 7. Depth of the LCs Fig. 8. Performance of the LC integral im-
plementations
1 — proposed LC ( 0, 0n k l ); 2 — proposed LC ( 1, 1n k l );
3 — proposed LC ( 1, 2n k l ); 4 — proposed LC ( 2, 0n k l );
5 — proposed LC ( 2, 1n k l ); 6 — proposed LC ( 2, 2n k l );
7 — proposed LC ( 3, 1n k l ); 8 — proposed LC ( 3, 2n k l ;
9 — multiplexer; 10 — LC based on the cascade method
M. Kovalov
ISSN 1681–6048 System Research & Information Technologies, 2023, № 1 140
2019. Accessed on: Feb. 6, 2023. [Online]. Available: https://doi.org/
10.1016/j.jnt.2019.02.006
5. D. Harris and S. Harris, Digital Design and Computer Architecture: ARM Edition.
Morgan Kaufmann, 2015.
6. A.N. Borodzhieva, I.I. Stoev, and V.A. Mutkov, “FPGA Implementation of Boolean
Functions Using Multiplexers,” in 2019 IEEE XXVIII International Scientific Con-
ference Electronics (ET), Sozopol, Bulgaria, Sep. 12–14, 2019. Accessed on: Feb. 6,
2023. [Online]. Available: https://doi.org/10.1109/et.2019.8878504
7. A.N. Borodzhieva, I.I. Stoev, I.D. Tsvetkova, S.L. Zaharieva, and V.A. Mutkov,
“FPGA Design of Boolean Functions Using a Cascade of Decoders and Logic
Gates,” in 2020 43rd International Convention on Information, Communication and
Electronic Technology (MIPRO), Opatija, Croatia, Sep. 28–Oct. 2, 2020, IEEE,
2020. Accessed on: Feb. 6, 2023. [Online]. Available: https://doi.org/10.23919/ mi-
pro48935.2020.9245448
8. A.A. M. Bsoul, S.J.E. Wilton, K.H. Tsoi, and W. Luk, “An FPGA Architecture and
CAD Flow Supporting Dynamically Controlled Power Gating,”IEEE Transactions
on Very Large-Scale Integration (VLSI) Systems, vol. 24, no. 1, pp. 178–191, Jan.
2016. Accessed on: Feb. 6, 2023. [Online]. Available: https://doi.org/10.1109/
tvlsi.2015.2393914
9. C. Ashok Kumar, B.K. Madhavi, and K.L. Kishore, “Enhanced Clock Gating Tech-
nique for Power Optimization in SRAM and Sequential Circuit,”Journal of Automa-
tion, Mobile Robotics and Intelligent Systems, pp. 32–38, Jan. 2022. Accessed on:
Feb. 6, 2023. [Online]. Available: https://doi.org/10.14313/jamris/2-2021/11
Received 09.02.2023
INFORMATION ON THE ARTICLE
Mykola O. Kovalov, ORCID: 0000-0002-2590-4052, National Technical University of
Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Ukraine, e-mail: kovua@yahoo.com
ПІДХІД ДО ПОЗИЦІЙНОЇ АЛГЕБРИ ЛОГІКИ / М.О. Ковальов
Анотація. Запропоновано метод подання булевих функцій у термінах пози-
ційної алгебри логіки в компактній операторній формі. Порівняно з відомим
методом у ньому застосовуються позиційні оператори зі складністю не більше
двох і лише одного виду еквівалентних перетворень. Метод відрізняється мен-
шою трудомісткістю і розкриває паралелізм логічних обчислень. Запропоно-
вано відповідний спосіб реалізації булевих функцій. Він становить конкурен-
цію деяким відомим способами за апаратною складністю, ресурсомісткістю та
швидкістю із застосуванням базису FPGA. Відкриваються можливості для
створення ефективних засобів автоматизації подання булевих функцій від ве-
ликої кількості змінних, синтезу відповідних комбінаційних схем та вдоскона-
лення сучасних елементних баз.
Ключові слова: булеві функції, позиційна алгебра логіки, позиційні операто-
ри, еквівалентні перетворення, комбінаційні схеми, FPGA.
|
| id | journaliasakpiua-article-273578 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | English |
| last_indexed | 2025-07-17T10:28:04Z |
| publishDate | 2023 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/8a/391ba4dc1d703d986a42b96ca5ea278a.pdf |
| spelling | journaliasakpiua-article-2735782023-05-24T21:28:17Z Approach to positional logic algebra Підхід до позиційної алгебри логіки Kovalov, Mykola булеві функції позиційна алгебра логіки позиційні оператори еквівалентні перетворення комбінаційні схеми FPGA boolean functions positional logic algebra positional operators equivalent transformations logic circuits FPGA The method of Boolean function representation in terms of positional logic algebra in compact operator form is offered. Compared with the known method, it uses position operators with a complexity of no more than two and only one type of equivalent transformations. The method is less labor intensive. It allows parallelizing logic calculations. The corresponding way of Boolean function implementation is developed. It competes with some known ways in terms of hardware complexity, resource intensity, and speed when implemented on an FPGA basis. Possibilities open up for creating effective automating means of representing Boolean functions from a large number of variables, synthesizing the corresponding LCs, and improving modern element bases. Запропоновано метод подання булевих функцій у термінах позиційної алгебри логіки в компактній операторній формі. Порівняно з відомим методом у ньому застосовуються позиційні оператори зі складністю не більше двох і лише одного виду еквівалентних перетворень. Метод відрізняється меншою трудомісткістю і розкриває паралелізм логічних обчислень. Запропоновано відповідний спосіб реалізації булевих функцій. Він становить конкуренцію деяким відомим способами за апаратною складністю, ресурсомісткістю та швидкістю із застосуванням базису FPGA. Відкриваються можливості для створення ефективних засобів автоматизації подання булевих функцій від великої кількості змінних, синтезу відповідних комбінаційних схем та вдосконалення сучасних елементних баз. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2023-03-30 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/273578 10.20535/SRIT.2308-8893.2023.1.11 System research and information technologies; No. 1 (2023); 129-140 Системные исследования и информационные технологии; № 1 (2023); 129-140 Системні дослідження та інформаційні технології; № 1 (2023); 129-140 2308-8893 1681-6048 en https://journal.iasa.kpi.ua/article/view/273578/274391 |
| spellingShingle | булеві функції позиційна алгебра логіки позиційні оператори еквівалентні перетворення комбінаційні схеми FPGA Kovalov, Mykola Підхід до позиційної алгебри логіки |
| title | Підхід до позиційної алгебри логіки |
| title_alt | Approach to positional logic algebra |
| title_full | Підхід до позиційної алгебри логіки |
| title_fullStr | Підхід до позиційної алгебри логіки |
| title_full_unstemmed | Підхід до позиційної алгебри логіки |
| title_short | Підхід до позиційної алгебри логіки |
| title_sort | підхід до позиційної алгебри логіки |
| topic | булеві функції позиційна алгебра логіки позиційні оператори еквівалентні перетворення комбінаційні схеми FPGA |
| topic_facet | булеві функції позиційна алгебра логіки позиційні оператори еквівалентні перетворення комбінаційні схеми FPGA boolean functions positional logic algebra positional operators equivalent transformations logic circuits FPGA |
| url | https://journal.iasa.kpi.ua/article/view/273578 |
| work_keys_str_mv | AT kovalovmykola approachtopositionallogicalgebra AT kovalovmykola pídhíddopozicíjnoíalgebrilogíki |