2. Home
  3. ARCHIVE
  4. 2018
  5. VOL 40, NO 2 (2018)
  6. Архив номеров
  7. 2015 год
  8. 37-6

Electronic Modeling

Vol 37, No 6 (2015)

CONTENTS

Mathematical Modeling and Computation Methods

  LISTROVOY S.V, MOTSNYI S.V.
The Minimum Vertex Cover Problem Solving Algorithm for an Arbitrary Graph with Using the Systems of Quadratic Equations
3-18
  PALAHIN V.V.
Cumulant Models and Polynomial Method Signal Detection under Additive Interaction with Correlated Non-Gaussian Noise
19-34
  TIMCHENKO L.I., KOKRYATSKAYA N.I., PODDUBETSKAYA M.P.
Method for Modeling Parallel-hierarchical Network for Processing Data Based on the Construction of Functional Series
35-48

Computational Processes and Systems

  SAPOZHNIKOV V.V., SAPOZHNIKOV Vl.V., EFANOV D.V., DMITRIEV V.V., CHEREPANOVA M.R.
Organization of Combinational Circuits Concurrent Error Detection Systems Based on the Modified Code with Summation of Weighted Transitions
49-68

Application of Modeling Methods and Facilities

  FARHADZADEH E.M., MURADALIYEV A.Z., FARZALIYEV Y.Z.
Distribution of Sample of a Continuous Random Variable
69-82
  SAMOYLOV V.D., VYNNYCHUK S.D., ABRAMOVYCH R.P.
The Method of Lifting the Load Currents to Input Node to Calculate the Energy Distribution Networks
83-98
  LYUBYMOVA N.A.
Comparative Evaluation of Posterior Probabilities of Emissions in Multicomponent Processes of Atmospheric Pollution by Power Enterprise
99-110
  VOLOSHKO A.V, BEDERAK Ya.S, LUTCHYN T.N.
Operational Forecasting of Power Consumption at Enterprises with a Continuous Cycle of Work
111-118

Color figures to the articles are in the insets

 

 

THE MINIMUM VERTEX COVER PROBLEM SOLVING ALGORITHM FOR AN ARBITRARY GRAPH WITH USING THE SYSTEMS OF QUADRATIC EQUATIONS

S.V. Listrovoy, S.V. Motsnyi

ABSTRACT

This paper presents an algorithm for solving the minimum vertex cover problem for the arbitrary graphs using systems of quadratic equations that provide high level of the operations parallelization. Approximation algorithms with different approximation coefficients can be used in practice to solve such problems. Experimental analysis shows the advantages of the described methodology in comparison with existing implementations. The algorithm effectiveness can be significantly enhanced by the use of distributed systems with many cores.

KEYWORDS

vertex cover, approximation coefficient, quadratic equations, frequency of terms occurrences.

REFERENCES

1. Christofides, N. (1978), Teoriya grafov. Algoritmicheskiy podkhod [Graph Theory. An Algorithmic Approach], Mir, Moscow, Russia.
2. Vijay Vazirani, V. (2003), Approximation Algorithms, 2nd ed., Springer-Verlag, Berlin, Germany, pp. 306-334.
3. Zhang, Y. and et al. (1992), “Approximating the minimum weight weak vertex cover”, Elsevier, Theoretical Computer Science, Vol. 7, no. 4, pp. 404-416.
4. Roth-Korostensky, C. (2000), “Algorithms for building multiple sequence alignments and evolutionary trees”, PhD thesis, ETH Zrich Institute of Scientific Computing, Zrich, Switzerland.
5. Stege, U. (2000), “Resolving conflicts in problems from computational biology”, PhD thesis, ETH Zrich Institute of Scientific Computing, Zrich, Switzerland.
6. Jianer, C., Iyad, K.A. and Ge, X. (2010), “Improved Parameterized Upper Bounds for Vertex Cover”, Elsevier, Theoretical Computer Science, Vol. 411, Iss. 40-42, pp. 3736-3756.
7. Jianer, C., Iyad, K.A. and Ge, X. (2005), “Simplicity is beauty: Improved upper bounds for vertex cover”, Technical Report 05-008, TexasA&MUniversity, Utrecht, the Netherlands.
8. Karakostas, G. (2009), “A better approximation ratio for the vertex cover problem”, ACM Transactions on Algorithms (TALG), Vol. 5, Iss. 4, pp. 1-8.
9. Cheng, W., Yuren, Z. and Weiping, T. (2007), “Hybrid genetic algorithm for vertex cover problem”, Computer Engineering and Applications, Vol. 43, no. 14, pp. 27-29.
10. Miehalewiez, Z. and Fogel, D.B. (2004), How to solve it: Modern heuristics, 2nd ed., Springer-Verlag, Heidelberg, Berlin, Germany.
11. Listrovoy, S.V. and Minukhin, S.V. (2012), “Method for solving the minimum vertex cover problem in arbitrary graphs and the problem of minimal coverage”, Elektronnoe modelirovanie, Vol. 34, no. 1, pp. 29-45.
12. Listrovoy, S.V. and Minukhin, S.V. (2012), “Investigation of the scheduler for heterogeneous distributed computing systems based on minimal cover method”, International Journal of Computer Applications, Vol. 51, no. 19, ðp. 35-44.

Full text: PDF (in Russian)

CUMULANT MODELS AND POLYNOMIAL METHOD SIGNAL DETECTION UNDER ADDITIVE INTERACTION WITH CORRELATED NON-GAUSSIAN NOISE

V.V. Palahin

ABSTRACT

The models and methods of processing statistically dependent random variables for the synthesis and analysis of polynomial algorithms for signals detection on the background of correlated non-Gaussian noise under the moment-cumulant description of random processes are developed. It is shown that the nonlinear processing of sample values and account of the parameters of non-Gaussian distributions of statistically dependent random variables can improve the efficiency of polynomial decision rules that is a decrease of the probability of errors of the first and second kind, as compared with well-known results.

KEYWORDS

stochastic polynomials, moment quality criteria, correlated non-Gaussian noise.

REFERENCES

1. Levin, B.R. (1989), Teoreticheskie osnovy statisticheskoi radiotechniki [Theoretical foundations of statistical radio engineering, 3rd ed., revised. and suppl.], Radio i svyaz, Moscow, Russia.
2. Van Trees, H.L. (2013), Detection, Estimation, and Modulation Theory, Part IV,Optimum Array Processing, John Wiley & Sons, New York, USA.
3. Vijay K. Madisetti (2010), The Digital Signal Processing, Handbook, Digital Signal Processing Fundamentals, CRC Press, USA.
4. Duan, F., Chapeau-Blondeau, F. and Abbott, D. (2014), “Non-Gaussian noise benefits for coherent detection of narrowband weak signal”, Physics Letters, A 378, pp. 1820-1824.
5. Bezruk, V.M. and Pevtsov, G.M. (2007), Teoreticheskie osnovy proektirovaniya sistem raspoznavaniya signalov dlya avtomatizirovannogo radiokontrolya [Theoretical bases of designing the systems of signals identification for automated radio control], Kollegium, Kharkov, Ukraine.
6. Malakhov, A.N. (1979), Kumulyantnyi analiz negaussovskikh protsessov i ikh preobrazovaniy [Cumulant analysis of non-Gaussian processes and their transformation], Sovetskoe radio, Moscow, Russia.
7. Kunchenko, Y. (2002), Polynomial Parameter Estimations of Close to Gaussian Random Variables, Shaker Verlag, Herzogenrath, Germany.
8. Palahin, V.V. (2009), “Moment criterion of quality statistical hypothesis testing for processing signals on background of the correlated non-Gaussian noise”, Sistemy obrabotki informatsii, Vol. 78, Iss. 4, pp. 96-101.
9. Palahin, V.V., Goncharov, À.V. and Filipov, V.V. (2015), “Features of the constant signal parameter estimation by the method of truncated polynomial maximization”, Oxford Journal of Scientific Research, IV, Vol. 9, no.1, pp.170-177.
10. Palahin, V.V. (2015), “Software of computer simulation of detecting and distinguishing signals on the background of non-Gaussian noise”, Informatika i matematicheskie metody v modelirovanii, Vol. 5, no. 5, pp. 103-114.
11. Kendall, M. and Stewart, A. (1973), Statisticheskie vyvody i svyazi [Statistical inference and communication], Nauka, Moscow, Russia.

Full text: PDF (in Russian)

METHOD FOR MODELING PARALLEL- HIERARCHICAL NETWORK FOR PROCESSING DATA BASED ON THE CONSTRUCTION OF FUNCTIONAL SERIES

L.I. Timchenko, N.I. Kokryatskaya, M.P. Piddubetskaya

ABSTRACT

The method for modeling parallel-hierarchical network based on the functional series is presented. The software, which allows simulatingG-transformation at every level of the network according to the previously chosen elements, has been developed. The software, which simulates the basic network of arbitrary dimension by creating its functional series, has been developed as well. The results may be used to solve problems of processing and organizing large bodies of data, including graphical ones.

KEYWORDS

parallel-hierarchical network, functional series, basic network, tail element.

REFERENCES

1. Ruei-Yu Wu, Gen-Huey Chen , Jung-Sheng Fu and Gerard J. Chang (2008), “Finding cycles in hierarchical hypercube networks”, J. Information Processing Letters, Vol. 109, Iss. 2, pp. 112-115.
2. Sven Behnke (2003), Hierarchical neural networks for image interpretation, Springer-Verlag, Berlin, Heidelberg, New York.
3. Srivastava, L., Singh, S.N. and Sharma, J. (1998), “Parallel self-organizing hierarchical neural network-based fast voltage estimation”, IEE Proceedings, Generation, Transmission and Distribution, Vol. 145, Iss. 1, pp. 98-104.
4. Middleton, V.T.C. and Hawkins, R. (1998), Sustainable tourism: a marketing perspective, Butterworth-Heinemann, Oxford, UK.
5. Thompson, R.H. and Swanson, L.W. (2010), “Hypothesis-driven structural connectivity analysis supports network over hierarchical model of brain architecture”, Proceedings of the National Academy of Sciences USA, Vol. 107, Iss. 34, pp. 15235-15239. Published online 2010 August 9, - doi: 10.1073/pnas.1009112107.
6. Lafer-Sousa, Rosa and Conway, Bevil R. (2013) “Parallel, multi-stage processing of colors, faces and shapes in macaque inferior temporal cortex”, Nature Neuroscience, no. 16, pp. 1870-1878.
7. Kaiser, M. (1994), “Time-delay neural networks for control”, Proceedings of the 4th International Symposium on Robot Control (SYROCO’94), Capri, Italy.
8. Timchenko, L.I., Melnikov, V.V., Kokryatskaya, N.I. and Kutaev, Y.F. (2011), “The method of organization of parallel-hierarchical networks for pattern recognition”, Kibernetika i sistemny analiz, no. 1, pp. 152-163.
9. Timchenko, L.I.,Melnikov, V.V.,Kokryatskaya,N.I. and et al. (2009), “The use of parallel-hierarchical method of image recognition spots of laser beams”, Materialy Mezhdunarodnoi nauchno-tekhnicheskoi konferentsii “Mnogoprotsessornye vychislitelnye i upravlyayushchie sistemy” [Proceedings of International Scientific-Technical Conference «Multiprocessor Computing and Control Systems»], Taganrog, September 28-October 3, 2009, pp. 147-150.
10. Timchenko, L.I. (1997), “Processes in real and artificial neuron networks”, Visnyk VPI, no.1, pp. 5-10.
11. Timchenko, L.I. (2000), “Multi-stage parallel-hierarchical network as a model of neural computing circuits”, Kibernetika i sistemny analiz, no. 2, pp.114-134.
12. Timchenko, L.I., Kokryatskaya, N.I., Melnikov, V.V. and Kosenko, G.L. (2013), “Method of forecasting energy center positions of laser beam spot images using a parallel hierarchical network for optical communication systems”, J. Opt. Eng., Vol. 52, no. 5, 055003 (May 09, 2013), doi: 10.1117/1.OE.52.5.055003.

Full text: PDF (in Russian)

ORGANIZATION OF COMBINATIONAL CIRCUITS CONCURRENT ERROR DETECTION SYSTEMS BASED ON THE MODIFIED CODE WITH SUMMATION OF WEIGHTED TRANSITIONS

V.V. Sapozhnikov, Vl.V. Sapozhnikov, D.V. Efanov, V.V. Dmitriev, M.R.Cherepanova

ABSTRACT

The authors adduce a way of formation of a code with summation, that is based on the weighting of transitions between adjacent bits in data vector and operations with transitions weight indexes. The consequence has been established for weight indexes and simple rules of modification of the code with summation of weighted transitions that allow us to form optimal, from the point of view of the minimumnumber of data bits undetectable errors, codes. It is shown that new codes allow organizing the concurrent error detection systems with lowered redundancy.

KEYWORDS

concurrent error detection system, testable system, hardware redundancy, error detection, duplication system, parity-based check system, code with summation, Berger code, optimal code with summation, code with summation of weighted transition, modified code with summation of weighted transition, benchmark circuits.

REFERENCES

1. McCluskey, E.J. (1986), Logic design principles: with emphasis on testable semicustom circuits, Prentice Hall PTR, New Jersey, USA.
2. Smolens, J.C., Jangwoo, Kim, Hoe, J.C. and Falsafi, B. (2005), “Understanding the performance of concurrent error detecting superscalar microarchitectures”, Proceedings of the 5th IEEE International Symposium on Signal Processing and Information Technology, Athens, Greece, December 21, 2005, pp. 13-18.
3. Fujiwara, E. (2006), Code design for dependable systems: theory and practical applications, John Wiley & Sons, New Jersey, USA.
4. Choudhury, M.R. and Mohanram, K. (2008), “Approximate logic circuits for low overhead, non-intrusive concurrent error detection”, Proceedings of the Ñonference on Design, Automation and Test in Europe (DATE’08), Munich, Germany, March 10-14, 2008, pp. 903-908.
5. Theeg, G. and Vlasenko, S. (2009), Railway signalling & interlocking, International compendium, Eurailpress, Hessen, Germany.
6. Bousselam, K., Di Natale, G., Flottes, M. and Rouzeyre, B. (2010), “Evaluation of concurrent error detection techniques on the advanced encryption standard”, Proceedings of 16th IEEE International On-Line Testing Symposium (IOLTS), Corfu, Greece, July 5-7, 2010, pp. 223-228.
7. Ubar, R., Raik, J. and Vierhaus, H.-T. (2011), “Design and test technology for dependable systems-on-chip”, Information Science Reference, IGI Global, Hershey, New York, USA.
8. Goessel, M. and Graf, S. (1994), Error detection circuits, McGraw-Hill, London, UK.
9. Lala, P.K. (2001), Self-checking and fault-tolerant digital design, Morgan Kaufmann Publishers, USA.
10. Sogomonyan, E.S. and Slabakov, E.V. (1989), Samoproveryaemye ustroystva i otkazoustoychivye sistemy [Self-checking devices and failover systems], Radio i svyaz, Moscow, Russia.
11. Sapozhnikov, V.V. and Sapozhnikov, Vl.V. (1992), Samoproveryaemye diskretnye ustroystva [Self-checking digital devices], Energoatomizdat, St. Petersburg, Russia.
12. Parkhomenko, P.P. and Sogomonyan, E.S. (1981), Osnovy tekhnicheskoy diagnostiki (optimizatsiya algoritmov diagnostirovaniya, apparaturnye sredstva) [Bases of technical diagnostics (optimization of diagnostic algorithms and equipment)], Energoatomizdat, Moscow, Russia.
13. Slabakov, E.V. and Sogomonyan, E.S. (1981), “Self-checking computing devices and systems (review)”, Avtomatika i telemekhanika, no. 11, pp. 147-167.
14. Piestrak, S.J. (1995), Design of self-testing checkers for unidirectional error detecting codes, Oficyna Wydawnicza Politechniki Wrocavskiej, Wrocaw, Poland.
15. Touba, N.A. and McCluskey, E.J. (1997), “Logic synthesis of multilevel circuits with concurrent error detection”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 16, pp. 783-789.
16. Nicolaidis, M. and Zorian, Y. (1998), “On-line testing for VLSI, à compendium of approaches”, Journal of Electronic Testing: Theory and Applications, no. 12, pp. 7-20.
17. Mitra, S. and McClaskey, E.J. (2000), “Which concurrent error detection scheme to choose?”, Proceedings of International Test Conference, USA, Atlantic City, NJ, October 03-05, 2000, pp. 985-994.
18. Matrosova, A., Levin, I. and Ostanin, S. (2001), “Survivable self-checking sequential circuits”, Proceedings of 2001 IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems (DFT 2001), San Francisco, California, October 24-26, 2001, pp. 395-402.
19. Kastensmidt, F.L., Carro, L. and Reis, R. (2006), Fault-tolerance techniques for SRAMbased, Springer, Dordrecht, Netherlands.
20. Efanov, D.V., Sapozhnikov, V.V. and Sapozhnikov, Vl.V. (2010), “On summation code properties in concurrent error detection systems”, Avtomatika i telemekhanika, no. 6, pp. 155-162.
21. Sapozhnikov, V.V., Sapozhnikov, Vl.V. and Efanov, D.V. (2015), “Application of summation codes for synthesis of railway automation and remote control systems using programmable logic integrated circuits”, Avtomatika na transporte, Vol. 1, no. 1, pp. 84-107.
22. Sapozhnikov, V.V., Sapozhnikov, Vl.V. and Efanov, D.V. (2015), “Dangerous errors detection at the operational outputs of combinational logic circuits”, Avtomatika na transporte, Vol. 1, no. 2, pp. 195-211.
23. Sogomonyan, E.S. (1974), “Design of inbuilt test self-checking circuits for combinational devices”, Avtomatika i telemekhanika, no. 2, pp. 121-133.
24. Aksyonova, G.P. (1979), “Necessary and sufficient conditions for the design of totally checking circuits of compression by modulo 2”, Avtomatika i telemekhanika, no. 9, pp. 126-135.
25. Ghosh, S., Basu, S. and Touba, N.A. (2005), “Synthesis of low power CED circuits based on parity codes”, Proceedings of the 23rd IEEE VLSI Test Symposium (VTS’05), Palm- Springs, CA, May 1-5, 2005, pp. 315-320.
26. Palframan, D.J., Nam Sung Kim and Lipasti, M.H. (2011), “Time redundant parity for low-cost transient error detection”, Proceedings of the Conference on Design, Automation and Test in Europe (DATE’11), Grenoble, France, March 14-18, 2011, pp. 1-6.
27. Berger, J.M. (1961), “À note on error detecting codes for asymmetric channels”, Information and Control, Vol. 4, Iss. 1, pp. 68-73.
28. Bose, B. and Lin, D.J. (1985), “Systematic unidirectional error-detection codes”, IEEE Trans. Comput., Vol. C-34, no. 11, pp. 1026-1032.
29. Das, D. and Touba, N.A. (1999), “Synthesis of circuits with low-cost concurrent error detection based on Bose-Lin codes”, Journal of Electronic Testing: Theory and Applications, Vol. 15, Iss. 1-2, pp. 145-155.
30. Blyudov, A.A., Efanov, D.V., Sapozhnikov, V.V. and Sapozhnikov, Vl.V. (2012), “Formation of modified Berger code with minimum number of undetectable errors of data bits”, Elektronnoe modelirovanie, Vol. 34, no. 6, pp. 17-29.
31. Blyudov, A.A., Efanov, D.V., Sapozhnikov, V.V. and Sapozhnikov, Vl.V. (2014), “On sum codes of unit bits in concurrent error detection systems, Avtomatika i telemekhanika, no. 8, pp. 131-145.
32. Berger, J.M. (1961), “A note on burst detecting sum codes”, Information and Control, Vol. 4, Iss. 2-3, pp. 297-299.
33. Das, D. and Touba, N.A. (1999), “Weight-based codes and their application to concurrent error detection of multilevel circuits”, Proceedings of the 17th IEEE VLSI Test Symposium, Dana Point, California, USA, April 25-29, 1999, pp. 370-376.
34. Das, D., Touba, N.A., Seuring, M. and Gossel, M. (2000), “Low cost concurrent error detection based on modulo weight-based codes”, Proceedings of the 6th IEEE International On-Line Testing Workshop (IOLTW), Palma de Mallorca, Spain, July 3-5, 2000, pp. 171-176.
35. Ghosh, S., Lai, K.W., Jone, W.B. and Chang, S.C. (2004), “Scan chain fault identification using weight-based codes for SoC circuits”, Proceedings of the 13th Asian Test Symposium, Taiwan, Kenting, November 15-17, 2004, pp. 210-215.
36. Srihari, P. (2014), “Sum codes: a binary channel coding scheme”, International Journal of Computer Science and Technology, Vol. 5, Iss. 1, pp. 60-64.
37. Sapozhnikov, V.V., Sapozhnikov, Vl.V. and Efanov, D.V. (2014), “Weighted sum codes for control organization of logic units”, Elektronnoe modelirovanie, Vol. 36, no. 1, pp. 59-80.
38. Efanov, D., Sapozhnikov, V., Sapozhnikov, Vl. and Nikitin, D. (2015), “Sum code formation with minimum total number of undetectable errors in data vectors”, Proceedings of the 13th IEEE East-West Design &Test Symposium (EWDTS’2015), Batumi, Georgia, September 26-29, 2015, pp. 141-148.
39. Saposhnikov, V. and Saposhnikov, Vl. (1999), “New code for fault detection in logic circuits”, Proceedings of the 4th International Conference on Unconventional Electromechanical and Electrical Systems, St. Petersburg, Russia, June 21-24, 1999, pp. 693-696.
40. Mehov, V., Saposhnikov, V., Sapozhnikov, Vl. and Urganskov, D. (2007), “Concurrent error detection based on new code with modulo weighted transitions between information bits”, Proceedings of the 7th IEEE East-West Design & Test Workshop (EWDTW’2007), Erevan, Armenia, September 25-30, 2007, pp. 21-26.
41. Mehov, V.B., Sapozhnikov, V.V. and Sapozhnikov, Vl.V. (2008), “Checking of combinational circuits basing on modification sum codes”, Avtomatika i telemekhanika, no. 8, pp. 153-165.
42. Sapozhnikov, V.V., Sapozhnikov, Vl.V., Efanov, D.V. and Dmitriev, V.V. (2014), “Properties of sum codes with weighted transitions with direct sequence of weight factors”, Informatika i sistemy upravleniya, no. 4, pp. 77-88.
43. Sapozhnikov, V., Sapozhnikov, Vl., Efanov, D., Dmitriev, V. and Cherepanova, M. (2015), “Optimum sum codes, that effectively detect the errors of low multiplicities”, Radio Electronics & Informatics, no. 1, pp. 17-22.
44. Busaba, F.Y. and Lala, P.K. (1994), “Self-checking combinational circuit design for single and unidirectional multibit errors”, Journal of Electronic Testing: Theory and Applications, Iss. 5, pp. 19-28.
45. Sapozhnikov, V.V., Morosov, A., Sapozhnikov, Vl.V. and G oessel, M. (1998), “A new design method for self-checking unidirectional combinational circuits”, Journal of Electronic Testing: Theory and Applications, Vol. 12, Iss. 1-2, pp. 41-53.
46. “Benchmarks: LGSynth89”, available at: http://www.cbl.ncsu.edu:16080/benchmarks/LGSynth89/ mlexamples/
47. “Collection of digital design benchmarks”, available at: http://ddd.fit.cvut.cz/prj/Benchmarks/.
48. Yang, S. (1991), “Logic synthesis and optimization benchmarks user guide: Version 3.0”, Technical Report, 1991-IWLS-UG-Saeyang, MCNC, USA.
49. Sentovich, E.M., Singh, K.J., Lavagno, L., Moon, C., Murgai, R., Saldanha, A., Savoj, H.,Stephan, P.R., Brayton, R.K. and Sangiovanni-Vincentelli, A. (1992), “SIS: a system for sequential circuit synthesis”, Electronics Research Laboratory, Department of Electrical Engineering and Computer Science, University of California, Berkeley, USA.

Full text: PDF (in Russian)