© The Institution of Engineering and Technology
This study presents the design and implementation of an efficient structure for fault tolerant bit-parallel polynomial basis multiplication and squaring over GF(2 m ), based on a similar strategy of Roving method with a minimum overhead. The Roving method is an efficient method for the circuits in which many similar and independent structures exist. The architectures of the polynomial basis multiplication and squaring over binary finite fields have inherent regularity in their subsections of the structures. Therefore, they are compatible to the applied version of Roving fault tolerant method. To generalise the proposed architecture, the multiplication and squaring operations are examined for different primitive polynomial, including general irreducible polynomials, irreducible pentanomials and irreducible trinomials. In the proposed design, the extracted common circuit has low hardware utilisation compared with that of the main circuit. The fault tolerant circuit is constructed by using three copies of the common circuit, a comparator and a voter circuit. The comparator and voter have parallel architectures with low critical path delays, which is a critical factor in any highly computational system. The design has been successfully verified and synthesised onVirtex-4 XC4VLX200 FPGA using Xilinx ISE 11. The results show an overall improvement in the speed and hardware usage compared with those of previous designs.
References
-
-
1)
-
27. Reyhani-Masoleh, A., Hasan, M.A.: ‘Fault detection architectures for field multiplication using polynomial bases’, IEEE Trans. Comput., 2006, 55, (9), pp. 1089–1103 (doi: 10.1109/TC.2006.147).
-
2)
-
12. Hariri, A., Reyhani-Masoleh, A.: ‘Concurrent error detection in montgomery multiplication over binary extension fields’, IEEE Trans. Comput., 2011, 60, (9), pp. 1341–1353 (doi: 10.1109/TC.2010.258).
-
3)
-
18. Bayat-Saramdi, S., Hasan, M.A.: ‘On concurrent detection of errors in polynomial basis multiplication’, IEEE Trans. Very Large Scale Integration (VLSI) Syst., 2007, 15, (4), pp. 413–426 (doi: 10.1109/TVLSI.2007.893659).
-
4)
-
17. Morales-Sandoval, M., Feregrino-Uribe, C., Kitsos, P.: ‘Bit-serial and digit-serial GF(2m) montgomery multipliers using linear feedback shift registers’, IET Comput. Digit. Tech., 2011, 5, (2), pp. 86–94 (doi: 10.1049/iet-cdt.2010.0021).
-
5)
-
22. Wu, H.: ‘Bit-parallel finite field multiplier and squarer using polynomial basis’, IEEE Trans. Comput., 2002, 51, (7), pp. 750–758 (doi: 10.1109/TC.2002.1017695).
-
6)
-
14. Mathew, J., Singh, J., Jabir, A.M., et al: ‘Fault tolerant bit parallel finite field multipliers using LDPC codes’. IEEE Int. Symp. on Circuits and Systems, ISCAS 2008, 18–21 May 2008, pp. 1684–1687.
-
7)
-
1. Carpiluppi, M.: ‘Fault Tolerance in large scale systems: hybrid and distributed approaches’. , University of Bologna, 2007.
-
8)
-
3. Hankerson, D., Menezes, A., Vanstone, S.: ‘Guide to elliptic curve cryptography’ (Springer-Verlag, New York, 2004, 1st edn.).
-
9)
-
23. Abramovici, M., Emmert, J.M., Stroud, C.E.: ‘Roving STARs: an integrated approach to on-line testing, diagnosis, and fault tolerance for FPGAs in adaptive computing systems’. Proc. Third NASA/DoD Workshop on Evolvable Hardware, Long Beach, Calif, USA, July 2001, pp. 73–92.
-
10)
-
5. Lee, C.Y., Chiou, C.W., Lin, J.M.: ‘Concurrent error detection in a polynomial basis multiplier over GF(2m)’, J. Electron. Test., Theory Appl., 2006, 22, pp. 143–150 (doi: 10.1007/s10836-006-7446-9).
-
11)
-
4. Shelly, S., Chacko, B.T.: ‘Fault detection multipliers in polynomial and normal basis’, Int. J. Comput. Appl. (0975-8887), 2010, 1, (5), pp. 102–106.
-
12)
-
2. Cheatham, A.A., Emmert, J.M.: ‘A survey of fault tolerant methodologies for FPGAs’, ACM Trans. Des. Autom. Electron. Syst., 2006, 11, (2), pp. 501–533 (doi: 10.1145/1142155.1142167).
-
13)
-
13. Bayat-Saramdi, S., Hasan, M.A.: ‘Run-time error detection in polynomial basis multiplication using linear codes’. Proc. IEEE Int. Conf. Application specific Systems, Architectures and Processors, Montreal, Que., 9–11 July 2007, pp. 204–209.
-
14)
-
7. Kumar-Singh, A., Bera, A., Rahaman, H., et al: ‘Error detecting dual basis bit parallel systolic multiplication architecture over GF(2m)’, J. Electron. Sci. Technol. China, 2009, 7, (4), pp. 336–342.
-
15)
-
20. Cohen, H., Frey, G., Avanzi, R., et al: ‘Handbook of elliptic and hyperelliptic curve cryptography’ (CRC Press, Boca Raton, 2006, 1st edn.).
-
16)
-
10. Chang, H.W., Chiou, C.W., Chou, F.H., et al: ‘concurrent error detection in polynomial basis multiplier over GF(2m) using irreducible trinomial’, J. Comput., 2011, 22, (3), pp. 11–25.
-
17)
-
21. Xiong, X., Fan, H.: ‘GF(2n) bit-parallel squarer using generalised polynomial basis for new class of irreducible pentanomials’, Electron. Lett., 2014, 50, (9), pp. 655–657 (doi: 10.1049/el.2014.0006).
-
18)
-
26. Martinez, C.D., Deepthi-Bollepalli, L.P., Hoe, D.H.K.: ‘A fault tolerant parallel-prefix adder for VLSI and FPGA design’. Proc. 44th IEEE Southeastern Symp. on System Theory, 11–13 March 2012, pp. 121–125.
-
19)
-
24. Bauer, L., Braun, C., Imhof, M.E., et al: ‘OTERA: online test strategies for reliable Reconfigurable architectures’. Proc. IEEE Conf. on Adaptive Hardware and Systems (AHS-2012) 2012 NASA/ESA, pp. 38–45.
-
20)
-
16. Rodriguez-Henriquez, F., Saqib, N.A., Diaz-Perez, A., et al: ‘Cryptographic algorithms on reconfigurable hardware’ (Springer US, New York, 2006, 1st edn.).
-
21)
-
9. Reyhani-Masoleh, A., Hasan, M.A.: ‘Error detection in polynomial basis multipliers over binary extension fields’. Proc. Cryptographic Hardware and Embedded Systems-CHES 2002, LNCS 2523, 2003, pp. 515–528.
-
22)
-
19. Deschamps, J.P., Imaña, J.L., Sutter, G.D.: ‘Hardware implementation of finite-field arithmetic’ (McGraw-Hill, New York, 2009, 1st edn.).
-
23)
-
15. Huang, W.T., Tan, S.Y., Chiou, C.W., et al: ‘On-line error detection in a polynomial basis multiplier over GF(2m) using self-checking alternating logic’, J. Comput., 2013, 24, (2), pp. 46–58.
-
24)
-
11. Chiou, C.W., Lee, C.Y., Deng, A.W., et al: ‘Concurrent error detection in montgomery multiplication over GF(2m)’, IEICE Trans. Fundam., 2006, 89, (2), pp. 566–574 (doi: 10.1093/ietfec/e89-a.2.566).
-
25)
-
8. Lee, C.Y., Chiou, C.W., Lin, J.L.: ‘Concurrent error detection in a bit-parallel systolic multiplier for dual basis of GF(2m)’, J. Electron. Test. Theory Appl., 2005, 21, (5), pp. 539–549 (doi: 10.1007/s10836-005-1053-z).
-
26)
-
25. Hoe, D.H.K., Deepthi-Bollepalli, L.P., Martinez, C.D.: ‘FPGA fault tolerant arithmetic logic: a case study using parallel-prefix adders’ (Hindawi Publishing Corporation, VLSI Design, 2013), , pp. 1–10.
-
27)
-
6. Bayat-Saramdi, S., Hasan, M.A.: ‘Concurrent error detection in finite-field arithmetic operations using pipelined and systolic architectures’, IEEE Trans. Comput., 2009, 58, (11), pp. 1553–1567 (doi: 10.1109/TC.2009.62).
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cdt.2015.0020
Related content
content/journals/10.1049/iet-cdt.2015.0020
pub_keyword,iet_inspecKeyword,pub_concept
6
6