350 rub
Journal Electromagnetic Waves and Electronic Systems №3 for 2019 г.
Article in number:
Minimization of threshold and majority functions
Type of article: scientific article
DOI: 10.18127/j15604128-201903-06
UDC: 004.312.26
Authors:

M.Yu. Aliev – Head of Department,  JSC «Typhoon» (Kaluga) E-mail: arls@mail.ru

A.M. Donetskov – Ph.D.(Eng.), Associate Professor, Department «Information Systems and Networks», Kaluga branch of the Bauman MSTU

E-mail: dam1358@mail.ru

A.S. Nikolaev – Ph.D.(Eng.), Associate Professor,  Department «Information Systems and Networks», Kaluga branch of the Bauman MSTU

E-mail: nikolanta@yandex.ru

Abstract:

The article suggests a method of minimization of the threshold and the majority of functions, based on building the disjunctive normal form. Designed by clear Algorhythm minimize, to get the same results that do not depend on the Chehuman performing the minimization. A set of simple expressions to create-to give the process of obtaining a majority function. The proposed submission rezultirujushhej functions as a set of simple formulae, compared to single you affection, describes the evaluated function, as is done in all other Algoritmah to reduce the amount of waste minimization, mechanical errors that may occur in the process of minimization. If you encounter such errors, they are easier to spot and fix. The relative simplicity and formalizing the process optimization of mini allows you to distribute the proposed algorithm to minimize the threshold and majority functions with lots of entries, compared to the other existing algorithms. Description of the algorithm is accomplished by the execution of an example of its implementation for specific values of the number of inputs of the majority of the element. Unambiguous algorithm minimizing helped to create an expression to calculate the number of operations performed in the computation of the function. This allows you to assess the complexity of the device to be created before the creation of the device itself. Comparing the proposed algorithm with the best algorithms from the existing ones. The proposed algorithm in all cases gives the result, is not inferior to other minimization algorithms. With a relatively small number of entries number of element of the majority of the operations performed in the proposed method does not exceed the number of operations performed using other methods. When a large number of inputs of the majority of the proposed item method always gives the best result among the known algorithms for minimization.

The main direction of perfecting of devices of protection against mistakes is increase in frequency rate of the error corrected by the decoder. At the same time it is frequent restriction of frequency rate of the corrected error not possibilities of a code, but complexity of realization of the decoder are. The majority method of decoding of codes is one of the simplest methods of decoding of the correcting codes, both from the point of view of the theory, and at implementation. The register of shift (one or several), adders modulo two and a majority element are a part of the majority decoder. Increase in frequency rate of the corrected error demands creation of multiport majority elements. However the complexity of majority elements sharply increases at increase of quantity of arguments of majority function. The number of the logical actions which are carried out at calculation of majority function is defined by a possibility of realization of the majority decoder correcting multiple errors. Threshold decoding is synthesis of majority decoding, and the threshold element which is used in it includes a majority element as one of options of a threshold element. The algorithm of minimization of threshold (majority) function based on use of perfect disjunctive normal function is given in article. The basis of minimization is made by arrangement of majority function. The number of the logical actions which are carried out at calculation of majority function is defined by a possibility of realization of the majority decoder correcting multiple errors. Threshold decoding is synthesis of majority decoding, and the threshold element which is used in it includes a majority element as one of options of a threshold element. The algorithm of minimization of threshold (majority) function based on use of perfect disjunctive normal function is given in article. The basis of minimization is made by arrangement of conjunctions in a formula and serial introduction of brackets to the formed function. The uniqueness of an algorithm of minimization allowed to calculate number of the logical actions necessary for function evaluation, without making minimization. Comparison of the received results with results of minimization shows in other ways that the offered way yields the best results.

Pages: 33-39
References
  1. Kolesnik V.D., Mironchikov E.T. Dekodirovanie tsiklicheskikh kodov. M.: Svyaz. 1968. 252 s.
  2. Messi Dzh. Porogovoe dekodirovanie: Per. s angl. Pod red. E.L. Blokha. M.: Mir. 1966. 207 s.
  3. Karpov Yu.G. Teoriya avtomatov. SPb.: Piter. 2002. 206 s.
  4. Nikolaev A.S. Minimizatsiya mazhoritarnogo elementa v bazise I-ILI. Sb. statei Mezhdunar. nauchno-prakt. konf. «Sovremennaya nauka: Teoreticheskii i prakticheskii vzglyad» 25 dekabrya 2014 g. Ufa: Aeterna. 2014. Ch. 2. S. 54−56.
  5. Nikolaev A.S. Minimizatsiya formuly porogovoi funktsii. Simvol nauki. 2016. № 4. Ch. 3. S. 105−107.
  6. Nikolaev A.S. Slozhnost porogovoi funktsii i ee inversii. Simvol nauki. 2016. № 7. Ch. 2. S. 83−85.
  7. Nikolaev A.S. Minimizatsiya skhemy mazhoritarnogo elementa. Elektromagnitnye volny i elektronnye sistemy. 2016. T. 21. № 7. S. 32−36.
  8. Nikolaev A.S., Aksenov A.E. Regulyarnaya protsedura minimizatsii mazhoritarnogo elementa. Elektromagnitnye volny i elektronnye sistemy. 2017. T. 22. № 3. S. 42−46.
  9. Nikolaev A.S., Aliev M.Yu. Uproshchenie skhemy porogovogo elementa. Elektromagnitnye volny i elektronnye sistemy. 2018. T. 23. № 3. S. 6−12.
  10. Maksimov A.V. Optimalnoe proektirovanie assemblernykh programm vychislitelnykh algoritmov: teoriya, inzhenernye metody: Ucheb. posobie. SPb.: Lan. 2016. 192 s.
Date of receipt: 22 марта 2019 г.