Majority multiplexing - Economical redundant fault-tolerant designs for nanoarchitectures

Sandip Roy, Valeriu Beiu

Research output: Contribution to journalArticlepeer-review

101 Citations (Scopus)


Motivated by the need for economical fault-tolerant designs for nanoarchitectures, we explore a novel multiplexing-based redundant design scheme at small (≤100) and very small (≤10) redundancy factors. In particular, we adapt a strategy known as von Neumann multiplexing to circuits of majority gates with three inputs and for the first time exactly analyze the performance of a multiplexing scheme for very small redundancies, using combinatorial arguments. We also develop an extension of von Neumann multiplexing that further improves performance by excluding unnecessary restorative stages in the computation. Our results show that the optimized three-input majority multiplexing (MAJ-3 MUX) outperforms the latest scheme presented in the literature, known as parallel restitution (PAR-REST), by a factor between two and four, for 48 ≤ R ≤ 100. Our scheme performs extremely well at very small redundancies, for which our analysis is the only accurate one. Finally, we determine an upper bound on the maximum tolerable failure probability when any redundancy factor may be used. This bound clearly indicates the advantage of using three-input majority gates in terms of reliable operation.

Original languageEnglish
Pages (from-to)441-451
Number of pages11
JournalIEEE Transactions on Nanotechnology
Issue number4
Publication statusPublished - Jul 2005
Externally publishedYes


  • Fault/defect tolerance
  • Majority gates
  • Nanoarchitectures
  • Von neumann multiplexing

ASJC Scopus subject areas

  • Computer Science Applications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Majority multiplexing - Economical redundant fault-tolerant designs for nanoarchitectures'. Together they form a unique fingerprint.

Cite this