Generalized Majority Voter Design Method for N-Modular Redundant Systems Used in Mission- and Safety-Critical Applications

Abstract

Mission- and safety-critical circuits and systems employ redundancy in their designs to overcome any faults or failures of constituent circuits and systems during the normal operation. In this aspect, the N-modular redundancy (NMR) is widely used. An NMR system is comprised of N identical systems, the corresponding outputs of which are majority voted to generate the system outputs. To perform majority voting, a majority voter is required, and the sizes of majority voters tend to vary depending on an NMR system. Majority voters corresponding to NMR systems are physically realized by enumerating the majority input clauses corresponding to an NMR system and then synthesizing the majority logic equation. The issue is that the number of majority input clauses corresponding to an NMR system is governed by a mathematical combination, the complexity of which increases substantially with increases in the level of redundancy. In this context, the design of a majority voter of any size corresponding to an NMR specification based on a new, generalized design approach is described. The proposed approach is inherently hierarchical and progressive since any NMR majority voter can be constructed from an (N − 2)MR majority voter along with additional logic corresponding to the two extra inputs. Further, the proposed approach paves the way for simultaneous production of the NMR system outputs corresponding to different degrees of redundancy, which is not intrinsic to the existing methods. This feature is additionally useful for any sharing of common logic with diverse degrees of redundancy in appropriate portions of an NMR implementation.

1. Introduction

Mission- and safety-critical circuits and systems that are used in many real-world applications such as space, aerospace, defense, nuclear power plants, electric power systems, industrial control and automation, banking and finance etc., usually employ redundancy in their designs to embed a specific degree of fault tolerance to withstand arbitrary fault(s) or failure(s) of the constituent circuit(s) or system(s) when they might occur [1,2]. In this context, the NMR scheme is well known and widely used [3,4]. In NMR, N identical function modules are used, where N is odd, and the ‘function module’ may be a circuit or a system. At any time, out of the N identical function modules, at least (N + 1)/2 function modules should maintain the correct operation to guarantee the correctness of an NMR system. The corresponding output(s) of the N function modules are majority voted to generate the NMR system outputs. Majority voting in an NMR system is performed using a majority voter. The number of (majority) voters to be used in an NMR system would depend on the number of outputs produced by the function module. Henceforth in our discussions, the term ‘voter(s)’ shall imply ‘majority voter(s)’, unless stated otherwise.

The 3MR is the basic 3-tuple version of the NMR, which specifies the use of 3 identical function modules and the fault or failure of maximum of 1 function module is tolerated. The 5MR is the 5-tuple version of the NMR wherein 5 identical function modules are used and the faults or failures of maximum of 2 function modules are tolerated. The 7MR and 9MR are the 7-tuple and 9-tuple versions of the NMR which employ 7 and 9 function modules and they can accommodate the faults or failures of maximum of 3 and 4 function modules respectively. In general, the fault(s) or failure(s) of maximum of (N − 1)/2 function modules are tolerated by an NMR system.

To mitigate the impact of radiation and other harsh phenomena on small device geometries in the nanoelectronics era [5,6], higher levels of NMR are suggested to be used to overcome multiple fault(s) or failure(s), which are likely to occur [7,8]. However, it may be noted that to enhance the fault or failure tolerance of an NMR system by one, two extra function modules should have to be added. Due to this, the drawbacks with the NMR are aggravated increases in system design metrics, and cost, especially when the level(s) of redundancy should have to be increased. To alleviate the drawbacks with full NMR, progressive module redundancy (PMR) [9] was suggested as a solution. PMR is an architectural technique which recommends the selective use of different degrees of NMR in the sensitive portions of a circuit or system according to the nature of their criticality rather than the blanket use of a higher order NMR for an entire circuit or system which could exacerbate the design parameters, and cost. Hence, PMR helps to ameliorate the drawbacks of the NMR scheme by opting for the selective deployment of higher degrees of NMR in the different portions of a circuit or system according to their extent of sensitivity. PMR would help to partly alleviate the drawbacks of the NMR scheme whilst optimizing an NMR system with respect to the design metrics and cost and simultaneously increasing the robustness of the system.

A typical NMR system is shown in Figure 1, where N identical function modules are used with each function module producing say, K outputs. Hence, K majority voters are used to perform majority voting of the corresponding outputs of the N function modules and the outputs of these majority voters define the NMR system outputs.

This article focuses on the novel design of majority voters which are used in NMR systems. Generally, a majority voter is designed by deducing all the majority input clauses corresponding to an NMR system. To explain what a majority input clause is, let us consider the 3MR system for an example. The 3MR scheme has been widely used in many mission- and safety-critical applications [10,11,12,13,14] and for yield improvement in integrated circuits [15,16].

Figure 2a shows a 3MR system with 3 identical function modules labelled 1, 2 and 3. The outputs of the function modules A, B and C are given to a 3-input majority voter, which performs majority voting and produces the 3MR system output, V. The logic expression for the 3MR system output is given by Equation (1), where ‘AB’, ‘BC’, ‘AC’ and ‘ABC’ specify the four possible majority input clauses, where a clause implies a product term which is a logical conjunction of literals. The majority clauses ‘AB’, ‘BC’ and ‘AC’ signify that any two out of the three function modules operate correctly and produce the same output, and the majority clause ‘ABC’ signifies that all the three function modules operate correctly and produce the same output. The symbol ‘ that appears next to a variable or a term signifies the Boolean complement in the equations.

V = AB + BC + AC + ABC

(1)

V = B(B⊕C)’ + A(B⊕C)

(2)

V = AB + BC + AC

(3)

Equations (2) and (3) are alternative expressions for Equation (1), and Equations (1)–(3) are logically equivalent. Equation (1) lists all the majority input clauses; Equation (2) is based on the multiplexer (MUX) logic; and Equation (3) lists only the dominant majority clauses. In fact, Equation (3) can be factorized to reduce the number of literals as V = AB + (B + A) C. Equation (2) is synthesized as shown in Figure 2b [17], with the term (B⊕C) serving as the selection input (S) for the 2:1 MUX shown. If (B⊕C) evaluates to 0 then input B is selected by the 2:1 MUX and its value is forwarded to the output V. On the other hand, if (B⊕C) evaluates to 1 then input A is selected and its value is forwarded to the output V. Figure 2c shows a direct synthesis of Equation (3) using only one complex gate viz. AO222 [18]. The AO222 gate requires 12 transistors for a static CMOS style of implementation.

The total number of majority clauses governing an NMR system increases substantially with increases in the level of redundancy by O(2^{N − 1}). However, the number of dominant majority clauses is governed by the mathematical combination: O[NC_{(N + 1)/2}] = O[N!/{(N + 1)/2}!{(N − 1)/2}!]. This follows the principle of mathematical combination, where in general, NC_R = N!/{R!(N − R)!}. Figure 3 shows the counts of the maximum number of majority input clauses and the number of dominant majority input clauses governing different NMR systems. For example, for a 3MR system, the total number of majority input clauses is 4, as given in Equation (1), whereas the number of dominant majority clauses is 3, as given in Equation (3). Nevertheless, Equations (1) and (3) are logically equivalent. The majority clause ‘ABC’ in Equation (1) can be eliminated by applying the absorption axiom of Boolean algebra. However, to estimate the reliability of an NMR system, all the majority input clauses should have to be considered [1]. Due to the substantial increase in the number of majority (and dominant majority) input clauses for higher order NMR systems, the sizes of the higher order NMR majority voters are bound to increase. In this context, this article puts forward a hierarchical, progressive and generalized design approach for implementing majority voters of any size, whereby the design of an NMR majority voter from an (N − 2)MR majority voter is made feasible.

The remainder of the article is organized as follows. Section 2 discusses the existing methods for the design of majority voters corresponding to 5MR, 7MR and 9MR systems: (i) based on the MUX logic, and (ii) conventional logic synthesis. Section 3 describes the proposed generic method for designing majority voters for NMR systems, and illustrates their physical realization corresponding to 5MR, 7MR and 9MR systems. Section 4 presents the physical implementation results for example 5MR, 7MR and 9MR systems which utilize different kinds of majority voters and employ a 4 × 4 array multiplier for the function module. The design metrics estimated for the different NMR systems featuring single or multiple redundancies and incorporating diverse majority voter designs are also discussed in this section. Finally, Section 5 draws the conclusions.

2. Methods

The existing methods to design NMR majority voters are discussed in this section.

2.1. MUX-Based Design of Majority Voters

Parhami [19] suggested the use of the MUX-based logic for realizing higher order majority voters based on identifying the MUX logic among the majority input clauses corresponding to an NMR system. This method shall be referred to as the ‘MUX-based design’ in this article. The MUX-based design of 5MR, 7MR and 9MR majority voters are presented in [20], which utilize the gates of a 32/28 nm CMOS standard digital cell library [21].

Assuming A, B, C, D and E are the inputs to a 5MR majority voter, whose output is designated W, the MUX-based logic equation for the 5MR majority voter is given by Equation (4). The optimized MUX-based logic synthesis of Equation (4) is depicted by Figure 4. In Figure 4, the primary inputs D and E serve as the selection inputs for the 4:1 MUX.

W = ABC(D’E’) + (AB + BC + AC)(D’E + DE’) + (A + B + C)DE

(4)

Now assuming A, B, C, D, E, F and G are the inputs to a 7MR majority voter, whose output is designated X, its MUX-based logic equation is given by Equation (5). The optimized MUX-based synthesis of Equation (5) is portrayed by Figure 5.

X = ABCD(E’F’G’) + (ABC + ABD + ACD + BCD)(E’F’G + E’FG’ + EF’G’) + (AB + AC +
AD + BC + BD + CD)(E’FG + EF’G + EFG’) + (A + B + C + D)EFG

(5)

Primary inputs E and F serve as the selection inputs for the 4:1 MUXes present in the penultimate logic level in Figure 5, and primary input G serves as the selection input for the last 2:1 MUX. Nevertheless, there exists a scope for a further but moderate optimization of the circuit shown in Figure 5. For example, the OA221 gates highlighted in Figure 5 can be replaced by OA211 gates. However, because the standard cell library [21] does not have the OA211 gate, the OA221 gate has been used instead.

Assuming A, B, C, D, E, F, G, H and I are the inputs to a 9MR majority voter, whose output is designated Y, the MUX-based logic equation for the 9MR majority voter is given by Equation (6). The optimized MUX-based realization of Equation (6) is shown in Figure 6. In Figure 6, primary inputs F and G serve as the selection inputs for the 4:1 MUXes present in the penultimate logic level, and inputs H and I serve as the selection inputs for the 4:1 MUX present in the last logic level.

Y = ABCDE(F’G’H’I’) + (ABCD + ABCE + ACDE + BCDE)(F’G’H’I + F’G’HI’
+ F’GH’I’ + FG’H’I’) + (ABC + ABD + ABE + ACD + ACE + ADE + BCD + BCE
+ BDE + CDE)(F’G’HI + F’GH’I + F’GHI’ + FG’H’I + FG’HI’ + FGH’I’) + (AB +
AC + AD + AE + BC + BD + BE + CD + CE + DE)(F’GHI + FG’HI + FGH’I +
FGHI’) + (A + B + C + D + E)FGHI

(6)

2.2. Direct Synthesis of Majority Voters

An alternative approach is to derive all the majority input clauses or the dominant majority input clauses corresponding to the majority voter of an NMR system as a sum-of-products expression and then synthesize it by a logic synthesis tool using a standard digital cell library [21], without extracting the MUX-based logic. This approach shall be referred to as ‘Direct synthesis’ in this article. Direct synthesis is quite cumbersome, as it was already mentioned that the number of dominant majority clauses is governed by the mathematical combination, O[NC_{(N + 1)/2}]. However, direct synthesis using a logic synthesis tool may optimize the voter logic better and hence might lead to a more compact majority voter compared to the MUX-based design. 5MR, 7MR and 9MR majority voters realized through the direct synthesis approach are portrayed by Figure 7, Figure 8 and Figure 9 respectively. In Figure 7, Figure 8 and Figure 9, A, B, C, D, E, F, G, H and I represent the primary inputs, and W, X and Y represent the primary outputs.

3. Proposed Design Method for Majority Voters

We propose a new, generalized method for the design of NMR majority voters by following a ‘divide and conquer approach’. We ascertain how a (N − 2)MR majority voter along with two extra inputs can be used to determine the output of a NMR majority voter. For example, can a 5MR majority voter be designed using a 3MR majority voter and additional logic involving the two extra inputs? We show in this section how this is feasible by describing our proposed generalized majority voter design method. For the 3MR majority voter, which serves as the foundation, we use the design shown in Figure 2b. With the 3MR voter serving as the basis, we note that any NMR majority voter can be constructed from the 3MR voter and including extra logic corresponding to the additional inputs, which is governed by O[N − 3]. We also analyze how our divide and conquer approach fares in comparison with the existing design approaches based on example implementations.

The block schematic of our proposed approach is portrayed by Figure 10, where the output of a NMR voter is determined based on the output of the (N − 2)MR voter and the two extra inputs, labelled X and Y, along with their associated logic. The additional logic corresponds to the three general conditions labelled Condition 1, Condition 2, and Condition 3 in Figure 10.

In Figure 10, the outputs of the 2-input XNOR and XOR gates, representing Condition 1 and Condition 2, are denoted by C1 and C2 respectively. The output of the Condition 3 logic corresponding to the NMR voter is denoted by C3. The output of the 3-input AND gate is given as the selection input for the 2:1 MUX and it is denoted as S. Based on the three conditions i.e., Conditions 1, 2 and 3, we determine whether a NMR majority voter output would differ from a (N − 2)MR majority voter output or remain the same. These conditions are discussed below.

• Condition 1: Represents the XNOR-ing of the two extra inputs (X and Y) present in an NMR majority voter. If X and Y are equal, then C1 would assume 1, otherwise it would assume 0.
• Condition 2: Represents the XOR-ing of one of the extra inputs (say, X) with the (N − 2)MR majority voter output. C2 would assume 1 if the extra input considered is complementary to the (N − 2)MR majority voter output, otherwise it would assume 0.
• Condition 3: If C1 or C2 or both C1 and C2 would assume 0, the output of the 3-input AND gate would be 0 i.e., S = 0, which implies that the NMR voter output would be the same as the (N − 2)MR voter output. The logic used to realize Condition 3 is quite sophisticated and considers those input clauses for which an (N − 2)MR voter would output 0 or 1 due to only (N − 1)/2 inputs being 0 or 1 respectively, and consequently an NMR voter output may become contrary to the (N − 2)MR voter output. In conjunction with the logic used to realize Conditions 1 and 2, Condition 3 is used to either forward the (N − 2)MR voter output as the NMR voter output or complement the former and forward that as the NMR voter output. This is achieved by determining whether a 0 is produced by an (N − 2)MR majority voter due to all the (N − 2) inputs being 0 or only (N − 1)/2 inputs are 0, and similarly whether a 1 is produced by an (N − 2)MR majority voter due to all the (N − 2) inputs being 1 or only (N − 1)/2 inputs are 1.

To explain the underlying concept behind the proposed majority voter design method, we refer to

Table 1. Illustrating the operation of the (proposed) generalized majority voter design approach.

(N − 2)MR Majority Voter Output	Extra Inputs		Internal Outputs			MUX Select Input	NMR Majority Voter Output
	X	Y	C1	C2	C3	S
0	0	0	0	1	–	0	0
0	0	1	0	0	–	0	0
0	1	0	1	0	–	0	0
0	1	1	1	1	0/1	0/1	0/1
1	0	0	1	1	0/1	0/1	0/1
1	0	1	1	0	–	0	1
1	1	0	0	0	–	0	1
1	1	1	0	1	–	0	1

. In Table 1, the ‘–’ in the column corresponding to C3 represents the do not care condition. Referring to Figure 10 and Table 1, if the (N − 2)MR voter output is 0, and if X or Y or both X and Y are 0, then C1 and/or C2 would evaluate to 0, and hence S = 0. This implies that the NMR voter output would be the same as the (N − 2)MR voter output. The bottom-line is when the (N − 2)MR voter output is 0 due to (N − 1)/2 inputs being 0, and even if one of the extra inputs introduced in the NMR voter i.e., X or Y is 0, this would result in at least (N + 1)/2 inputs of the NMR voter to have assumed 0, and thus the NMR voter output will be the same as the (N − 2)MR voter output which is 0. On the other hand, if X or Y or both X and Y are 1, then C1 and/or C2 would evaluate to 0 and hence S = 0. Again, this implies that the NMR voter output would be the same as the (N − 2)MR voter output. When the (N − 2)MR voter output is 1 due to (N − 1)/2 inputs being 1, and even if one of the extra inputs i.e., X or Y is 1, this would result in at least (N + 1)/2 inputs of the NMR voter to have assumed 1, and therefore the NMR voter output will be the same as the (N − 2)MR voter output, which is 1. With respect to these conditions, the value of C3 is treated as a do not care since the AND gate shown in Figure 10 would output 0 even when one of its inputs is 0.

The logic pertaining to C3 basically comprises those input clauses which have only (N − 1)/2 inputs in an (N − 2)MR voter being 0 or 1. Hence, if only (N − 1)/2 inputs in an (N − 2)MR voter are 0 or 1 then C3 evaluates to 1. The logic producing C1 or C2 are fixed as per definition but the logic producing C3 would vary depending on the NMR system considered. The logic equation corresponding to C3 would be a sum-of-products expression, and the number of product terms in the expression is governed by the sum of two mathematical combinations, which is given as O[(N − 2)C_{(N − 3)/2} + (N − 2)C_{(N − 1)/2}]. The logic expression corresponding to C3 may be synthesized using a logic synthesis tool.

Now let us assume that only (N − 1)/2 inputs in an (N − 2)MR voter are 0, and hence the (N − 2)MR voter output is 0 according to the Boolean majority. But this implies that the remaining input in the (N − 2)MR voter is 1. Under this condition, if the two extra inputs introduced in the NMR voter i.e., X and Y assume 1, overall this would cause (N + 1)/2 out of the N inputs in the NMR voter assuming 1, which represents a Boolean majority for the NMR voter. Given this, C1, C2 and C3 would evaluate to 1, and hence S = 1 in Figure 10. Consequently, the (N − 2)MR voter output, which is 0, would be complemented, and 1 is produced as the NMR voter output.

Let us also consider that only (N − 1)/2 inputs in an (N − 2)MR voter are 1, and hence the (N − 2)MR voter output is 1 based on the Boolean majority. But this implies that the remaining input in the (N − 2)MR voter is 0. Under this condition, if the two extra inputs introduced in the NMR voter i.e., X and Y both assume 0, overall this would lead to (N + 1)/2 inputs assuming 0 in the NMR voter, which represents a Boolean majority. Given this, C1, C2 and C3 would evaluate to 1, and S = 1 in Figure 10. Therefore, the (N − 2)MR voter output, which is 1, would be inverted and its complement i.e., 0 is produced as the NMR voter output.

The important advantage of the proposed approach is that different levels of redundancies can be simultaneously provisioned without having to individually design the circuits commensurate with specific redundancies, i.e., NMR system outputs corresponding to different redundancies can be produced in parallel. Note that this advantage is not inherent in the existing (i.e., MUX-based and Direct synthesis) majority voter design methods. Figure 11 shows the block schematic of a hierarchical NMR voter implementation based on the 3MR voter, where N is assumed to be 9. In fact, the hierarchy can be extended to any N, with N being odd. The access points labelled X1, X2, X3 and X4 in Figure 11 represent the regions from where the 3MR, 5MR, 7MR and 9MR voter outputs can be simultaneously obtained, which underlines the flexibility inherent in the proposed method. In fact, this flexibility would be best exploited when the same logic but which corresponds to different degrees of redundancy may be required for use in different portions of an NMR system and thereby the common logic can be effectively shared. Therefore, any of the voter output(s) corresponding to the access point(s) shown may be utilized in the succeeding sub-circuits/sub-systems to achieve an efficient PMR configuration for the design of safety-critical circuits/systems.

3.1. Proposed 5MR Majority Voter

Let A, B and C be the inputs of the 3MR majority voter, and let A, B, C, D and E be the inputs of the 5MR majority voter. The proposed design of the 5MR majority voter based on the 3MR majority voter and the two extra inputs (D and E) is shown in Figure 12. The three conditions (C1, C2 and C3) of the 5MR voter are expressed by Equations (7)–(9). In Figure 12, INT1 and INT2 represent the internal outputs which are utilized in the designs of the proposed 7MR and 9MR majority voters.

C1_5MR = (D⊕E)’

(7)

C2_5MR = D⊕V_3MR

(8)

C3_5MR = A’B’C + AB’C’ + A’BC’ + A’BC + AB’C + ABC’

(9)

3.2. Proposed 7MR Majority Voter

Let A, B, C, D and E be the inputs to the 5MR majority voter, and let A, B, C, D, E, F and G be the inputs to the 7MR majority voter. Given this, the proposed design of the 7MR majority voter based on the 5MR majority voter and the two extra inputs (F and G) is shown in Figure 13. The internal output INT2 from Figure 12 is utilized in Figure 13. The equations governing the three conditions (C1, C2 and C3) of the 7MR voter are given by Equations (10)–(12).

C1_7MR = (F⊕G)’

(10)

C2_7MR = F⊕V_5MR

(11)

C3_7MR = (ABC’ + AB’C + A’BC + ABC)D’E’ + (AB’C’ + A’BC’ + A’B’C + ABC’ + AB’C
+ A’BC)(D’E + DE’) + (A’B’C’ + AB’C’ + A’BC’ + A’B’C)DE

(12)

3.3. Proposed 9MR Majority Voter

Let A, B, C, D, E, F and G be the inputs to the 7MR majority voter, and let A, B, C, D, E, F, G, H and I be the inputs to the 9MR majority voter. Given this, the proposed design of the 9MR majority voter based on the 7MR majority voter and the two extra inputs (H and I) is shown in Figure 14. The intermediate output INT1 from Figure 12 is used in Figure 14. The equations governing the three conditions (C1, C2 and C3) of the 9MR voter are given by Equations (13)–(15).

C1_9MR = (H⊕I)’

(13)

C2_9MR = H⊕V_7MR

(14)

C3_9MR = (ABCD’ + ABC’D + AB’CD + A’BCD + ABCD)E’F’G’ + (ABC’D’ + AB’CD’ +
AB’C’D + A’BCD’ + A’BC’D + ABCD’ + ABC’D + A’BCD + AB’CD + A’B’CD)(E’F’G
+ E’FG’ + EF’G’) + (AB’C’D’ + A’BC’D’ + A’B’CD’ + A’B’C’D + ABC’D’ + A’BCD’ +
A’BC’D + A’B’CD + AB’C’D + AB’CD’)(E’FG + EFG’ + EF’G) + (A’B’C’D’ + A’BC’D’
+ A’B’CD’ + A’B’C’D + AB’C’D’)EFG

(15)

4. Results and Discussion

4.1. Example NMR System Implementations with Single Redundancy

The example 5MR, 7MR and 9MR systems were implemented by incorporating different types of majority voters viz. MUX-based, direct synthesis, and the proposed designs. Note that example NMR system implementations incorporating the MUX-based voter designs were alone considered in [20]. In this work, example NMR system implementations comprising the directly synthesized majority voters are additionally considered for comparison.

A 4 × 4 Braun array multiplier has been used as the function module like [20]. The 4-bit array multiplier has 8 inputs and produces 8 outputs, and requires sixteen 2-input AND gates, four half adders, and eight full adders. It occupies 84.38 µm² of silicon when physically realized using a 32/28 nm standard digital cell library [21]. Since the array multiplier produces 8 outputs, 8 majority voters are used to realize the NMR systems as in [20]. All the NMR systems were implemented using the same digital cell library [21].

Functional simulations were performed using Synopsys VCS by supplying distinct input vectors pertaining to the array multiplier at time intervals of 2.5 ns (i.e., 400 MHz) to the NMR systems. The test benches used to perform functional simulation of the 5MR systems containing different majority voters are identical. Similarly, the test benches used to perform functional simulations of the 7MR and 9MR systems comprising diverse majority voters are also identical. Since identical copies of the function module were used and the test benches were uniformly applied to all the NMR systems incorporating different majority voters, this paves the way for a straightforward comparison of the design metrics of corresponding 5MR, 7MR and 9MR systems. Thus, the differences between the design metrics of corresponding 5MR, 7MR and 9MR systems are attributable to the differences between the corresponding majority voter logic.

The MUX-based 5MR, 7MR and 9MR voters were designed in a semi-custom fashion using the gates of the standard digital cell library [21], according to the gate level schematics given in [20]. The proposed 5MR, 7MR and 9MR voters were also designed in a semi-custom fashion. The logic corresponding to Condition 3 of the proposed 5MR, 7MR and 9MR voters were synthesized using Synopsys Design Vision. The direct synthesis of 5MR, 7MR and 9MR majority voters was also done using Synopsys Design Vision. Default wire loads were automatically included commensurate with the corresponding NMR implementations while performing the simulations. The design metrics of the 5MR, 7MR and 9MR systems, estimated using Synopsys PrimeTime, are given in

Table 2. Implementation results obtained for NMR systems featuring single redundancy, and incorporating diverse majority voters (mentioned within brackets in the first column). The design metrics correspond to a 32/28 nm CMOS process.

NMR System Type	Power (μW)	Delay (ns)	Area (μm2)
5MR (MUX-based design)	120.7	0.98	529.64
5MR (Direct synthesis)	134.9	1.25	637.39
5MR (Proposed)	131.0	1.25	688.22
7MR (MUX-based design)	191.3	1.12	865.11
7MR (Direct synthesis)	181.7	1.19	842.74
7MR (Proposed)	214.3	1.54	1117.22
9MR (MUX-based design)	278.5	1.23	1269.7
9MR (Direct synthesis)	250.0	1.33	1214.81
9MR (Proposed)	334.9	1.84	1771.89

.

From Table 2, we infer that, in general, the NMR implementations incorporating the proposed majority voters consume more area. This is due to the increased area occupancy of the proposed majority voters compared to the existing voter designs. The area occupancies of the diverse majority voters are portrayed through Figure 15, and the silicon areas of the 5MR, 7MR and 9MR voters are highlighted. Although the proposed majority voter design method is generalized unlike the existing methods, the reason for the increased area occupancy of the proposed majority voters is due to the increases in the size of the Condition 3 logic. The Condition 3 logic of the proposed 5MR, 7MR and 9MR majority voters consume 10.16 µm², 17.02 µm² and 45.22 µm² of silicon. This is owing to the increases in the number of products governing the Condition 3 logic expression, as given by (9), (12) and (15). The number of product terms corresponding to C3 for the 5MR, 7MR and 9MR systems equate to 6, 20 and 70 respectively.

Additionally, the NMR systems incorporating the proposed majority voters exhibit more critical path delay. This is a consequence of the proportionate increases in the logic depth of the proposed majority voters due to the cascaded arrangement of logic gates to realize higher order NMR voter outputs, as evident from Figure 11. Because of the cascading of logic gates, the critical path delay of any NMR majority voter (T_{NMR_MV}) designed based on our method can be characterized through a general equation viz. Equation (16). In Equation (16), T_XOR2, T_MUX21 and T_AND3 represent the typical propagation delays of minimum sized 2-input XOR, 2:1 MUX, and 3-input AND gates present in the library [20]. In Equation (16), the first term given within brackets on the right-side represents the critical path delay of the 3MR majority voter shown in Figure 2b.

T_{NMR_MV} = T_XOR2 + T_MUX21 + (N − 3)/2(T_XOR2 + T_AND3 + T_MUX21)

(16)

For every increase in the order of the NMR, the second term on the right-side of Equation (16) will increase by an order of magnitude due to the factor, (N − 3)/2. The order of magnitude increase is owing to the cascading of gates to realize higher order majority voters according to our proposed method, as shown in Figure 11. For majority voters realized using the MUX-based or direct synthesis methods, there is no proportionate increase in the critical path delay unlike the proposed method since the corresponding majority voters can be individually optimized for speed due to the absence of any generalization, and hence the MUX-based or the directly synthesized majority voters are likely to have lesser critical path delays.

However, it is important to note here that the simultaneous production of the majority voter outputs corresponding to different degrees of redundancy is not possible based on the existing methods. For example, in the 9MR majority voter designed according to the proposed method, through the respective access points which are highlighted in Figure 11, the 7MR and 5MR majority voter outputs can be obtained in parallel, which appears to be beneficial for a PMR implementation. On the other hand, in the case of the MUX-based or the direct synthesis approaches, only one majority voter output corresponding to a specific redundancy configuration can be obtained.

Based on Equation (16), the critical path delay of an NMR system (T_NMR) designed based on our proposed method can be expressed using Equation (17), where T_BAM4 denotes the typical propagation delay of the 4 × 4 array multiplier. In Equation (17), T_AND2, T_HA and T_FA represent the respective propagation delays of the minimum sized 2-input AND gate, half adder and full adder present in the cell library [21].

T_NMR = T_BAM4 + T_{NMR_MV} = T_AND2 + 2T_HA + 4T_FA + T_XOR2 + T_MUX21 +
(N − 3)/2(T_XOR2 + T_AND3 + T_MUX21)

(17)

By substituting the typical propagation delays of the minimum size gates present in the cell library [21], the theoretical critical path delays of the example 5MR, 7MR and 9MR systems incorporating the proposed majority voters were calculated based on Equation (17) and they are plotted versus the practical critical path delays given in Table 2 for comparison.

Figure 16 shows that the theoretical delays calculated, and the practical delays estimated follow a similar trend, which validates the theoretical delay model given by Equation (17). Nevertheless, the differences between the theoretical and practical delay values are because the interconnect delays were not accounted for in the theoretical calculations.

Because of the increases in the areas of the NMR systems incorporating the proposed majority voters, their power dissipation is also expected to be higher than the power dissipation of NMR systems incorporating the other majority voters (i.e., MUX-based or direct synthesis), which is confirmed by Table 2.

4.2. Example NMR System Implementations with Multiple Redundancies

The proposed method to synthesize an NMR system is inherently hierarchical and can produce primary outputs corresponding to different degrees of redundancy, as discussed in Section 3 (see Figure 11). For example, this implies that if a 7MR system is considered for implementation, not only 7MR outputs but 3MR and 5MR outputs are also simultaneously produced, as depicted by Figure 11. Such an inherent hierarchy leading to the parallel production of primary outputs corresponding to multiple redundancies is not implicit in the existing MUX-based or direct synthesis majority voter design methods. Thus, to perform an apple-to-apple comparison, we considered the synthesis of NMR systems with outputs pertaining to different degrees of redundancy by utilizing the MUX-based and direct synthesis methods to realize the corresponding majority voters. This implies that when a 7MR system is designed by utilizing 7MR majority voters based on the MUX-based and direct synthesis methods, a similar number of 3MR and 5MR majority voters are also additionally utilized based on the respective methods to produce multiple redundancies. This kind of NMR system implementation with multiple redundancies could be useful for the efficient implementation of PMR at the circuit or sub-system or system levels. This is because if there exists some commonality in the logic of a circuit or a system realization, the different degrees of redundancies could be effectively shared to efficiently realize NMR circuits or systems corresponding to the PMR technique.

The test benches used for the functional simulations are maintained the same as earlier, and the simulation environment is also maintained the same. The input vectors were also supplied at the same frequency as mentioned earlier. For the NMR system implementations with multiple redundancies, the power, delay, and area metrics were estimated, and they are given in

Table 3. Implementation results obtained for NMR systems featuring multiple redundancies and incorporating diverse majority voters (mentioned within brackets in the first column). The design metrics correspond to a 32/28 nm CMOS process.

Multiple NMR System Type	Power (μW)	Delay (ns)	Area (μm2)
5MR-3MR (MUX-based design)	128.7	0.98	590.63
5MR-3MR (Direct synthesis)	142.9	1.25	698.39
5MR-3MR (Proposed)	131.0	1.25	688.22
7MR-5MR-3MR (MUX-based design)	221.0	1.14	1033.86
7MR-5MR-3MR (Direct synthesis)	226.5	1.26	1119.25
7MR-5MR-3MR (Proposed)	214.3	1.54	1117.22
9MR-7MR-5MR-3MR (MUX-based design)	361.6	1.28	1712.93
9MR-7MR-5MR-3MR (Direct synthesis)	339.6	1.35	1743.43
9MR-7MR-5MR-3MR (Proposed)	334.9	1.84	1771.89

.

From Table 3, we note that the NMR systems featuring multiple redundancies dissipate less power when the majority voters designed based on the proposed method are used. It is very likely that this low power advantage will be improved especially when a complex or sophisticated function module is considered. In terms of the area occupancy, the differences may not be significant, especially when the order of redundancy is increased. For example, for the 9MR-7MR-5MR-3MR configuration shown in Table 3, the diverse NMR implementations with multiple redundancies which utilize different majority voters occupy almost the same area. With respect to delay, the MUX-based design of multiple majority voters is found to be advantageous, as compared to the design of multiple majority voters based on the other methods.

5. Conclusions

A new generalized, hierarchical design approach for NMR majority voters was presented. We implemented example 5MR, 7MR and 9MR systems by considering an array multiplier as the function module with majority voters corresponding to MUX-based, direct synthesis, and the proposed methods. The proposed approach is inherently hierarchical and progressive due to the cascaded arrangement of NMR primary outputs and the design of any NMR majority voter from an (N − 2)MR majority voter is feasible. In fact, the design of any NMR majority voter from the 3MR voter is feasible. Our approach can facilitate the parallel production of NMR outputs corresponding to different degrees of redundancy, which is not possible with the existing methods (MUX-based or direct synthesis). Even when this is performed, an NMR system featuring multiple redundancies and incorporating the proposed majority voters’ results in less power. This advantage could benefit the efficient realization of PMR in the design of circuits or systems meant for mission- or safety-critical applications. Further, when there would be an opportunity to utilize common logic during the implementation of multiple redundancies based on the PMR, the proposed majority voter design method would be more beneficial than the existing design methods in terms of low power.