access icon free Efficient implementation of bit-parallel fault tolerant polynomial basis multiplication and squaring over GF(2 m )

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.

Inspec keywords: field programmable gate arrays; fault tolerant computing; multiplying circuits; polynomials; logic design; Galois fields; parallel architectures

Other keywords: irreducible trinomials; bit-parallel fault tolerant polynomial basis multiplication; Virtex-4 XC4VLX200 FPGA; fault tolerant circuit; GF(2m); common circuit; Roving fault tolerant method; Xilinx ISE 11; general irreducible polynomials; binary finite fields; irreducible pentanomials; parallel architectures; voter circuit; bit-parallel fault tolerant polynomial basis squaring; primitive polynomial; independent structures; low critical path delays; comparator

Subjects: Codes; Logic and switching circuits; Logic design methods; Algebra; Algebra; Logic circuits; Digital circuit design, modelling and testing; Performance evaluation and testing

References

    1. 1)
    2. 2)
    3. 3)
    4. 4)
    5. 5)
    6. 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. 16841687.
    7. 7)
      • 1. Carpiluppi, M.: ‘Fault Tolerance in large scale systems: hybrid and distributed approaches’. A PhD thesis, University of Bologna, 2007.
    8. 8)
      • 3. Hankerson, D., Menezes, A., Vanstone, S.: ‘Guide to elliptic curve cryptography’ (Springer-Verlag, New York, 2004, 1st edn.).
    9. 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. 7392.
    10. 10)
    11. 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. 102106.
    12. 12)
    13. 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. 204209.
    14. 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. 336342.
    15. 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. 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. 1125.
    17. 17)
    18. 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. 121125.
    19. 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. 3845.
    20. 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. 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. 515528.
    22. 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. 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. 4658.
    24. 24)
    25. 25)
    26. 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), Vol. 2013, Article ID 382682, pp. 110.
    27. 27)
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cdt.2015.0020
Loading

Related content

content/journals/10.1049/iet-cdt.2015.0020
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading