ECE 645

Computer Arithmetic
Spring 2014

Schedule of Project Presentations
Monday, May 12, 6:00-9:20pm
The Nguyen Engineering Building, room 3507

Time and location: Wednesday, 4:30-7:10 PM, Aquia Building, room 219
Instructor: Kris Gaj
Email: kgaj (at)
Office hours: Monday, Wednesday, 3:00-4:00 PM;  Wednesday, 7:30-8:30 PM; and by appointment
Syllabus: link

Required Textbooks:

Behrooz Parhami, Computer Arithmetic: Algorithms and Hardware Design, 2nd Edition, Oxford University Press, New York, 2010.

Recommended Textbooks

Jean-Pierre Deschamps, Gery Jean Antoine Bioul, Gustavo D. Sutter,  Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems,  Wiley-Interscience, 2006.

Joseph Cavanagh, Computer Arithmetic and Verilog HDL Fundamentals, CRC Press, 2009.

Milos D. Ercegovac and Tomas Lang, Digital Arithmetic, Morgan Kaufmann Publishers, 2004.

Isreal Koren, Computer Arithmetic Algorithms, 2nd edition, A. K. Peters, Natick, MA, 2002.

Sundar Rajan, Essential VHDL: RTL Synthesis Done Right, S & G Publishing, 1998.

Other literature

Software Packages Used in This Class

Course Description

Course Outline (subject to possible modifications):

  1. Objectives, Scope, and Organization. 01/22/2014
  2. Basic Adders and Counters.  Implementation of Adders in FPGAs.   01/22/2014, 01/29/2014
  3. Carry-Lookahead and Carry-Select Adders. Hybrid Adders.   02/05/2014
  4. Conditional-Sum Adders and Parallel Prefix Network Adders.    02/12/2014
  5. Fixed-Point Representations. 02/19/2014
  6. Endianness. Floating-Point Representations.   02/26/2014
  7. Rounding. Operations in the Galois Fields.  03/05/2014
  8. Multioperand Addition.   03/19/2014
  9. Midterm Exam    03/26/2014
  10. Tree and Array Multipliers. Squaring. FPGA Implementation of Multipliers. 04/02/2014
  11. Sequential Multipliers: Part 1. Radix-2 Multipliers. 04/09/2014
  12. Sequential Multipliers: Part 2.  High-Radix Multipliers.  04/16/2014
  13. Advanced High-Radix Multipliers. Serial and Modular Multipliers. Basic Dividers.   04/23/2014
  14. Advanced Dividers. 04/30/2014

Lecture slides

Lecture 11: Advanced Dividers. [PPT, PDF]

Lecture 10: Basic Dividers. [PPT, PDF]

        Radix 2 Restoring Divider (unsigned):   diagram 1, diagram 2

        Radix 2 Non-Restoring Divider (unsigned):   diagram

Lecture 9: High-Radix Sequential Multipliers. Bit-Serial Multipliers. Modular Multipliers. [PPT, PDF]

Radix 4 Sequential Multiplier with Booth Encoding without CSA (unsigned a and x):  diagram, recoding logic

Radix 4 Sequential Multiplier with Booth Encoding with CSA (unsigned a, signed x):  diagram 1, diagram 2

Lecture 8: FPGA Multipliers. Radix 2 Sequential Multipliers. [PPT, PDF]

FPGA Multipliers:  diagram 1, diagram 2, diagram 3

Radix 2 Sequential Multipliers Left-Shift Version (unsigned):  diagram

Radix 2 Sequential Multipliers Right-Shift Version with CSA (unsigned):   example, diagram 1, diagram 2, timing 1, timing 2

Lecture 7: Tree and Array Multipliers. [PPT, PDF]

Lecture 6: Multioperand Addition. Modular Addition. [PPT, PDF]

Lecture 5: Floating Point Representations. Rounding. Representation of the Galois Field elements. [PPT, PDF]

Lecture 4: Fixed-Point Representations. Endianness. [PPT, PDF]

Lecture 3: Conditional-Sum Adders and Parallel Prefix Network Adders. FPGA Optimized Adders. [PPT, PDF]

Lecture 2: Carry-Lookahead, Carry-Select, & Hybrid Adders. [PPT, PDF]

Lecture 1: Basic Adders and Counters. Implementation of Adders in FPGAs. [PPT, PDF]

Lecture 0: Objectives, Scope, and Organization of the Course [PPT, PDF]

Posted gradually before a given lecture.

See the course web page from Spring 2013 for slides from the previous year.



Project can be done either individually or in groups of two students.

The students can choose one of the following project types:

Recommended Outline of Your Specification

Recommended Outline of Your Presentation

List and Format of Project Deliverables

Recommended Outline of Your Report

Hardware Projects

Area:  Public Key Cryptography

Project 1: Post-quantum public key-cryptography: McEliece scheme


Project 2: Implementation of RSA using DSP units


Project 3: Implementation of RSA based on the Huang et al. architecture for Montgomery multiplication


  • M. Huang, K. Gaj, T. El-Ghazawi, "New Hardware Architectures for Montgomery Modular Multiplication Algorithm," IEEE Transactions on Computers, IEEE Transactions on Computers, vol. 60, no. 7, July 2011, pp. 923-936.
  • M. Huang, K. Gaj, S. Kwon, and T. El-Ghazawi, "An Optimized Hardware Architecture for the Montgomery Multiplication Algorithm," Proc. 11th International Workshop on Practice and Theory in Public Key Cryptography, PKC 2008, Barcelona, Spain, pp. 214-228, Mar. 2008. (paper + slides in PDF + slides in PPT)
  • C implementation of the Montgomery multiplication (to be provided by the instructor)

Area: Coding Theory

Project 4: Reed-Solomon Code for RAID systems


Project 5: Error Correcting Code Encoder and Decoder for Physical Unclonable Functions


Area: Financial Computations

Project 6: Floating point unit for Decimal64 floating-point format (supporting at least multiplication and addition)


Area: Factoring

Project 7: Trial Division by Small Primes

Project 8: Pollard's Rho Method of Factoring

Area: FPGA-optimized Arithmetic Units

Project 9: FPGA-optimized Adders and Modular Adders for Long Integers


Software Projects

Project 10: Comparative analysis of multi-precision arithmetic libraries for public key cryptography


Analytical Projects

Project 11: Comparative analysis of DSP units of Xilinx, Altera, and Microsemi FPGAs


Project 12: Comparative analysis of CORDIC-based architectures for Direct Digital Frequency Synthesizer (DDFS)


Project 13: Comparative analysis of hardware architectures for Fast Fourier Transform


Project 14: Comparative analysis of fast exponentiation algorithms


Homework Assignment

Homework 4 - due Monday, March 17, 11:59pm; solutions to bonus problems can be submitted by Sunday, March 23, 11:59pm

Homework 3 Bonus - due Saturday, March 1, 11:59pm

Homework 3 - due Wednesday, February 26, 4:30pm; please use the following Answer Sheets

Homework 2 Bonus - due Sunday, February 16, 11:59pm

Homework 2 - due Saturday, February 15, 11:59pm; please use the following Answer Sheets

Homework 1 - due Wednesday, February 5, 4:30pm (at the beginning of the class); solutions to bonus problems can be submitted by Saturday, February 8, 11:59pm

Posted gradually about a week before a given assignment is due.

See the course web page from Spring 2013 for homework assignment from the previous year.


Reference Materials


Please see Tutorials available on the page: Tutorials and Lab Manuals.

Use "645" or "ECE 645" as a filter.

Computer Arithmetic Algorithms Simulators

Simulator by Isreal Koren


VHDL Instructions: Templates & Examples

Frequently Asked Questions about VHDL from comp.lang.vhdl

OpenCores Coding Guidelines

The Low Carb VHDL Tutorial - by Bryan Mealy - HDL Resources of EDA Industry Working Groups

VHDL Tips & Tricks - a very useful set of slides from the Integrated Systems Laboratory, ETH Zurich


Related course web pages

ECE 645: Spring 2013, Spring 2012

ECE 545: Fall 2013, Fall 2012

ECE 448: Spring 2013, Spring 2012


Practice Exams

DISCLAIMER: The exams from previous years are not representative of the material covered in class this semester, and may include questions you are not required to know solutions to, and omit material covered in class this year.

Midterm Exam from Spring 2013

Midterm Exam from Spring 2012 - solutions

Midterm Exam from Spring 2011

Midterm Exam from Spring 2010 - solutions

Midterm Exam from Spring 2009 - solutions

Midterm Exam 1 from Spring 2007 - solutions

Midterm Exam 1 from Spring 2005 - solutions

Practice Midterm Exam from Spring 2005

Midterm Exam 1 from Spring 2004 - solutions

Practice Midterm Exam from Spring 2004

Midterm Exam 1 from Spring 2002 - solutions

Midterm Exam 1 from Spring 2000

Final Exam from Spring 2013

Final Exam from Spring 2012

Final Exam from Spring 2011

Final Exam from Spring 2010 Solutions: Problem 1, Problem 2, Problem 3, Problem 5

Final Exam from Spring 2009

Midterm Exam 2 from Spring 2007

Midterm Exam 2 from Spring 2006

Midterm Exam 2 from Spring 2005