View source for Triple modular redundancy

{{Short description|Method for increasing reliability}}
{{Other uses of|TMR|TMR (disambiguation)}}
[[File:Triple Modular Redundancy.JPG|thumb|right|350px|Triple Modular Redundancy. Three identical logic circuits (logic gates) are used to compute the specified Boolean function. The set of data at the input of the first circuit are identical to the input of the second and third gates.]]

In [[computing]], '''triple modular redundancy''', sometimes called '''triple-mode redundancy''',<ref>{{Cite web|url=http://www.xilinx.com/publications/archives/xcell/Xcell50.pdf|title=David Ratter. "FPGAs on Mars"|access-date=May 30, 2020}}</ref> ('''TMR''') is a [[fault-tolerant]] form of N-modular redundancy, in which three systems perform a process and that result is processed by a majority-voting system to produce a single output. If any one of the three systems fails, the other two systems can correct and mask the fault.

The TMR concept can be applied to many forms of [[Redundancy (engineering)|redundancy]], such as software redundancy in the form of [[N-version programming]], and is commonly found in [[fault-tolerant computer system]]s.

Space satellite systems often use TMR,<ref>{{cite web
|url=http://www.militaryaerospace.com/articles/2001/08/actel-engineers-use-triple-module-redundancy-in-new-rad-hard-fpga.html
|title=Actel engineers use triple-module redundancy in new rad-hard FPGA
|publisher=Military & Aerospace Electronics
|access-date=2017-04-09 }}</ref><ref>[https://escies.org/download/webDocumentFile?id=64426 ECSS-Q-HB-60-02A] : Techniques for radiation effects mitigation in ASICs and FPGAs handbook</ref> although satellite RAM usually uses [[Hamming(7,4)|Hamming error correction]].<ref>{{Cite web|url=https://radhome.gsfc.nasa.gov/radhome/papers/aspen.htm|archive-url=https://web.archive.org/web/20010304133002/http://radhome.gsfc.nasa.gov/radhome/papers/aspen.htm|url-status=dead|archive-date=March 4, 2001|title=Commercial Microelectronics Technologies for Applications in the Satellite Radiation Environment|website=radhome.gsfc.nasa.gov|access-date=May 30, 2020}}</ref>

Some [[ECC memory]] uses triple modular redundancy hardware (rather than the more common [[Hamming code]]), because triple modular redundancy hardware is faster than Hamming error correction hardware.<ref>{{cite web
 |title       = Using StrongArm SA-1110 in the On-Board Computer of Nanosatellite
 |publisher   = Tsinghua Space Center, Tsinghua University, Beijing
 |access-date  = 2009-02-16
 |url         = http://www.apmcsta.org/File/doc/Conferences/6th%20meeting/Chen%20Zhenyu.doc
 |url-status     = dead
 |archive-url  = https://web.archive.org/web/20111002152735/http://www.apmcsta.org/File/doc/Conferences/6th%20meeting/Chen%20Zhenyu.doc
 |archive-date = 2011-10-02
}}<!-- I wish I had a better reference --></ref> Called [[repetition code]], some communication systems use N-modular redundancy as a simple form of [[forward error correction]]. For example, 5-modular redundancy communication systems (such as [[FlexRay]]) use the majority of 5 samples – if any 2 of the 5 results are erroneous, the other 3 results can correct and mask the fault. 

Modular redundancy is a basic concept, dating to antiquity, while the first use of TMR in a computer was the Czechoslovak computer [[SAPO (computer)|SAPO]], in the 1950s.

== General case ==
The general case of TMR is called '''N-modular redundancy''', in which any positive number of replications of the same action is used. The number is typically taken to be at least three, so that error correction by majority vote can take place; it is also usually taken to be odd, so that no ties may happen.<ref name=nmr>{{cite book |last1=Shooman |first1=Martin L. |title=Reliability of computer systems and networks: fault tolerance, analysis and design |url=https://archive.org/details/reliabilitycompu00shoo_940 |url-access=limited |publisher=Wiley-Interscience |isbn=9780471293422 |chapter=N-Modular Redundancy |year=2002 |pages=[https://archive.org/details/reliabilitycompu00shoo_940/page/n167 145]–201 |doi=10.1002/047122460X.ch4}} [https://sce.uhcl.edu/goodwin/Ceng5334/downLoads/ch4_new.pdf Course notes]</ref>

== Majority logic gate ==
{{see also|Majority function}}

===3-input majority gate===
[[File:Majority Logic.png|thumb|right|350px|3-input majority gate using 4 [[NAND gate|NAND gates]]]]

The 3-input majority gate output is 1 if two or more of the inputs of the majority gate are 1; output is 0 if two or more of the majority gate's inputs are 0.  Thus, the majority gate is the [[Carry (arithmetic)#Computing|carry output]] of a [[full adder]], i.e., the majority gate is a [[voting machine]].<ref name=DilipSarwate2012/>

The 3-input majority gate can be represented by the following [[Boolean algebra (logic)|boolean equation]] and [[truth table]]:

: <math>Q = AB \lor BC \lor AC </math> 

{| class="wikitable" 
|- bgcolor="#ddeeff" align="center"
|colspan=3|'''INPUT'''<br>A &nbsp; B &nbsp; C || '''OUTPUT'''<br>Q
|- 
|{{no2|0}} || {{no2|0}} || {{no2|0}} || {{no2|0}}
|- 
|{{no2|0}} || {{no2|0}} || {{yes2|1}} || {{no2|0}}
|- 
|{{no2|0}} || {{yes2|1}} || {{no2|0}} || {{no2|0}}
|- 
|{{no2|0}} || {{yes2|1}} || {{yes2|1}} || {{yes2|1}}
|- 
|{{yes2|1}} || {{no2|0}} || {{no2|0}} || {{no2|0}}
|- 
|{{yes2|1}} || {{no2|0}} || {{yes2|1}} || {{yes2|1}}
|- 
|{{yes2|1}} || {{yes2|1}} || {{no2|0}} || {{yes2|1}}
|- 
|{{yes2|1}} || {{yes2|1}} || {{yes2|1}} || {{yes2|1}}
|}

In TMR, three identical logic circuits (logic gates) are used to compute the same set of specified Boolean function. If there are no circuit failures, the outputs of the three circuits are identical. But due to circuit failures, the outputs of the three circuits may be different.

===TMR operation===
Assuming the Boolean function computed by the three identical logic gates has value 1, then: (a) if no circuit has failed, all three circuits produce an output of value 1, and the majority gate output has value 1. (b) if one circuit fails and produces an output of 0, while the other two are working correctly and produce an output of 1, the majority gate output is 1, i.e., it still has the correct value. And similarly for the case when the Boolean function computed by the three identical circuits has value 0.  Thus, the majority gate output is guaranteed to be correct as long as no more than one of the three identical logic circuits has failed.<ref name=DilipSarwate2012>Dilip V. Sarwate, Lecture Notes for ECE 413 – Probability with Engineering Applications, [[UIUC College of Engineering#Departments|Department of Electrical and Computer Engineering (ECE)]], [[UIUC College of Engineering]], [[University of Illinois at Urbana-Champaign]]</ref>

For a TMR system with a single voter of reliability (probability of working) {{math|R<sub>v</sub>}} and three components of reliability {{math|R<sub>m</sub>}}, the probability of it being correct can be shown to be {{math|1=R<sub>TMR</sub> = R<sub>v</sub> (3 R<sub>m</sub><sup>2</sup> – 2 R<sub>m</sub><sup>3</sup>)}}.<ref name=nmr/>

TMR systems should use [[data scrubbing]] – rewrite flip-flops periodically – in order to avoid accumulation of errors.<ref>{{Cite book|last1=Zabolotny|first1=Wojciech M.|last2=Kudla|first2=Ignacy M.|last3=Pozniak|first3=Krzysztof T.|last4=Bunkowski|first4=Karol|last5=Kierzkowski|first5=Krzysztof|last6=Wrochna|first6=Grzegorz|last7=Krolikowski|first7=Jan|title=Photonics Applications in Industry and Research IV|date=2005-09-16|editor-last=Romaniuk|editor-first=Ryszard S.|editor2-last=Simrock|editor2-first=Stefan|editor3-last=Lutkovski|editor3-first=Vladimir M.|chapter=Radiation tolerant design of RLBCS system for RPC detector in LHC experiment|volume=5948|location=Warsaw, Poland|pages=59481E|doi=10.1117/12.622864|s2cid=15987757 }}</ref>

=== Voter ===
[[File:Triple Modular Redundancy et sa variante améliorée.png|thumb|Triple modular redundancy with one voter (top) and three voters (bottom)]]
The majority gate itself could fail.  This can be protected against by applying triple redundancy to the voters themselves.<ref>A.W. Krings.[http://www2.cs.uidaho.edu/~krings/CS449/Notes.S13/449-13-03.pdf "Redundancy"].2007</ref>

In a few TMR systems, such as the [[Saturn Launch Vehicle Digital Computer]] and '''functional triple modular redundancy (FTMR)''' systems, the voters are also triplicated. Three voters are used – one for each copy of the next stage of TMR logic. In such systems there is no [[single point of failure]].<ref>{{cite web|author1=Sandi Habinc|url=http://microelectronics.esa.int/techno/fpga_003_01-0-2.pdf|title=Functional Triple Modular Redundancy (FTMR): VHDL Design Methodology for Redundancy in Combinatorial and Sequential Logic|archive-url=https://web.archive.org/web/20120605210435/http://klabs.org/richcontent/fpga_content/DesignNotes/seu_hardening/functional_tmr_fpga_003_01-0-2.pdf |archive-date=2012-06-05|date=2002}}</ref><ref>{{cite journal |last1=Lyons |first1=R. E. |last2=Vanderkulk |first2=W. |title=The Use of Triple-Modular Redundancy to Improve Computer Reliability |journal=IBM Journal of Research and Development |url=http://www.ccs.neu.edu/course/csg712/resources/Lyons-Vanderkulk-62.pdf |date=April 1962 |volume=6 |issue=2 |pages=200–209 |doi=10.1147/rd.62.0200}}</ref>

Even though only using a single voter brings a single point of failure &ndash; a failed voter will bring down the entire system &ndash; most TMR systems do not use triplicated voters. This is because the majority gates are much less complex than the systems that they guard against, so they are much more [[Reliability engineering|reliable]].<ref name=DilipSarwate2012/> By using the reliability calculations, it is possible to find the minimum reliability of the voter for TMR to be a win.<ref name=nmr/>

==Chronometers==
To use triple modular redundancy, a ship must have at least three [[Marine chronometer|chronometers]]; two chronometers provided [[dual modular redundancy]], allowing a backup if one should cease to work, but not allowing any [[error correction]] if the two displayed a different time, since in case of contradiction between the  two chronometers, it would be impossible to know which one was wrong (the [[error detection]] obtained would be the same of having only one chronometer and checking it periodically). Three chronometers provided triple modular redundancy, allowing [[error correction]] if one of the three was wrong, so the pilot would take the average of the two with closer reading (vote for average precision).

There is an old adage to this effect, stating: "Never go to sea with two chronometers; take one or three."<ref>{{Cite book | isbn = 978-0-201-83595-3 | title = The Mythical Man-Month | last = Brooks | first = Frederick J. | author-link = Fred Brooks | year = 1995 | orig-year = 1975 | publisher = Addison-Wesley | page = [https://archive.org/details/mythicalmonth00broo/page/64 64] | title-link = The Mythical Man-Month }}</ref>

Mainly this means that if two [[Marine chronometer|chronometers]] contradict, how do you know which one is correct? At one time this observation or rule was an expensive one as the cost of three sufficiently accurate chronometers was more than the cost of many types of smaller merchant vessels.<ref>{{cite web
 |url          = http://www.irbs.com/lists/navigation/0107/0066.html
 |title        = Re: Longitude as a Romance
 |publisher    = Irbs.com, Navigation mailing list
 |date         = 2001-07-12
 |access-date   = 2009-02-16
 |archive-url  = https://web.archive.org/web/20110520040104/http://www.irbs.com/lists/navigation/0107/0066.html
 |archive-date = 2011-05-20
 |url-status     = dead
}}</ref>
Some vessels carried more than three chronometers – for example, [[HMS Beagle]] carried [[List of chronometers on HMS Beagle|22 chronometers]].<ref>
{{cite web
|author=R. Fitzroy
|title=Volume II: Proceedings of the Second Expedition
|page=18 |url=http://darwin-online.org.uk/content/frameset?viewtype=side&itemID=F10.2&pageseq=41}}</ref>  However, such a large number was usually only carried on ships undertaking survey work as was the case with the ''Beagle''.

In the modern era, ships at sea use [[GNSS]] navigation receivers (with [[GPS]], [[GLONASS]] & [[WAAS]] etc. support) – mostly running with WAAS or [[EGNOS]] support so as to provide accurate time (and location).

== In popular culture ==
* In [[Arthur C. Clarke]]'s science fiction novel ''[[Rendezvous with Rama]]'', the Ramans make heavy use of triple redundancy.
* In the popular anime ''[[Neon Genesis Evangelion]]'', the Magi are a set of three [[Biological computing|biological supercomputers]] that must agree with a 2/3 majority vote before delivering a decision.{{Citation needed|date=September 2023}}
* In the film ''[[Minority Report (film)|Minority Report]]'', 3 "precogs" are used to predict impending homicides, using a triple modular redundancy. In the plot, this system fails, causing a false positive: an innocent man is wrongly accused of murder.

== See also ==
* [[Fault tolerant system]]
* [[Lockstep (computing)]]
* [[Segal's law]]

==References==
{{Reflist}}

== External links ==
* [https://web.archive.org/web/20110216002312/http://www.embedded.com.au/pages/TMR.html Article about TMR] with reference to TMR usage in avionics and industry
* Johnson, J. M., & Wirthlin, M. J. (2010, February). [http://dl.acm.org/citation.cfm?id=1723154 Voter insertion algorithms for FPGA designs using triple modular redundancy.] In Proceedings of the 18th annual ACM/SIGDA international symposium on Field programmable gate arrays (pp.&nbsp;249–258). ACM.

[[Category:Engineering concepts]]
[[Category:Reliability engineering]]
[[Category:Safety]]
[[Category:Fault-tolerant computer systems]]
[[Category:Error detection and correction]]