RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor
Subscription

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



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






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


Diskr. Mat., 2017, Volume 29, Issue 4, Pages 87–105 (Mi dm1451)  

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

A method of synthesis of irredundant circuits admitting single fault detection tests of constant length

D. S. Romanova, E. Yu. Romanovab

a Lomonosov Moscow State University
b Russian State Social University, Moscow

Abstract: A constructive proof is given that in each of the bases $B'=\{ x\mathbin& y, x\oplus y, x\sim y\}$, $B_1=\{ x\mathbin& y, x\oplus y, 1\}$ any $n$-place Boolean function may be implemented: a) by an irredundant combinational circuit with $n$ inputs and one output admitting (under single stuck-at faults at inputs and outputs of gates) a single fault detection test of length at most 16, b) by an irredundant combinational circuit with $n$ inputs and one output admitting (under single stuck-at faults at inputs and outputs of gates and at primary inputs) a single fault detection test of length at most $2n-2\log_2 n+O(1)$; besides, there exists an $n$-place function that cannot be implemented by an irredundant circuit admitting a detecting test whose length is smaller than $2n-2\log_2 n-\Omega(1)$, c) by an irredundant combinational circuit with $n$ inputs and three outputs admitting (under single stuck-at faults at inputs and outputs of gates and at primary inputs) a single fault detection test of length at most 17.

Keywords: circuit of gates, fault detection test, stuck-at fault, Shannon function, easily testable circuit.

Funding Agency Grant Number
Russian Foundation for Basic Research 16-01-00593-а
18-01-00800-а
15-01-07474-а
Ministry of Education and Science of the Russian Federation 1.9328.2017/БЧ


DOI: https://doi.org/10.4213/dm1451

Full text: PDF file (538 kB)
First page: PDF file
References: PDF file   HTML file

English version:
Discrete Mathematics and Applications, 2019, 29:1, 35–48

Bibliographic databases:

UDC: 519.718
Received: 23.08.2017
Revised: 06.11.2017

Citation: D. S. Romanov, E. Yu. Romanova, “A method of synthesis of irredundant circuits admitting single fault detection tests of constant length”, Diskr. Mat., 29:4 (2017), 87–105; Discrete Math. Appl., 29:1 (2019), 35–48

Citation in format AMSBIB
\Bibitem{RomRom17}
\by D.~S.~Romanov, E.~Yu.~Romanova
\paper A method of synthesis of irredundant circuits admitting single fault detection tests of constant length
\jour Diskr. Mat.
\yr 2017
\vol 29
\issue 4
\pages 87--105
\mathnet{http://mi.mathnet.ru/dm1451}
\crossref{https://doi.org/10.4213/dm1451}
\elib{http://elibrary.ru/item.asp?id=30737805}
\transl
\jour Discrete Math. Appl.
\yr 2019
\vol 29
\issue 1
\pages 35--48
\crossref{https://doi.org/10.1515/dma-2019-0005}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000459400000005}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85062484942}


Linking options:
  • http://mi.mathnet.ru/eng/dm1451
  • https://doi.org/10.4213/dm1451
  • http://mi.mathnet.ru/eng/dm/v29/i4/p87

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. K. A. Popkov, “Sintez legkotestiruemykh skhem pri odnotipnykh konstantnykh neispravnostyakh na vkhodakh i vykhodakh elementov”, Preprinty IPM im. M. V. Keldysha, 2018, 087, 18 pp.  mathnet  crossref  elib
    2. K. A. Popkov, “Sintez legkotestiruemykh skhem pri proizvolnykh konstantnykh neispravnostyakh na vkhodakh i vykhodakh elementov”, Preprinty IPM im. M. V. Keldysha, 2018, 149, 32 pp.  mathnet  crossref  elib
    3. K. A. Popkov, “Sintez legkotestiruemykh skhem pri odnotipnykh konstantnykh neispravnostyakh na vkhodakh i vykhodakh elementov”, Intellektualnye sistemy. Teoriya i prilozheniya, 22:3 (2018), 131–147  mathnet
    4. K. A. Popkov, “Sintez legkotestiruemykh skhem pri proizvolnykh konstantnykh neispravnostyakh na vkhodakh i vykhodakh elementov”, PDM, 2019, no. 43, 78–100  mathnet  crossref
  • Дискретная математика
    Number of views:
    This page:207
    References:19
    First page:25

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020