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) gmu.edu
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, 2^nd 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

Simulators: Aldec Active HDL, ModelSim SE, Xilinx ISim

FPGA Toolsets available in the ECE Labs: Xilinx ISE, Altera Quartus II Subscription Edition

FPGA Toolsets available at home: Xilinx WebPACK, Altera Quartus II Web Edition

Synthesis Tools: Xilinx XST, Quartus II Integrated Synthesis, Synopsys Synplify Premier DP

Course Description

Course Outline (subject to possible modifications):

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

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

The students can choose one of the following project types:

Hardware projects: Design and comparison of selected computer arithmetic hardware architectures using VHDL or Verilog.
Software projects: Development of efficient software implementations of selected arithmetic algorithms in a high-level programming language.
Analytical projects: Literature search, analysis, and comparison of various computer arithmetic algorithms and architectures.

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

Resources:

D. Engelbert, R. Overbeck and A. Schmidt, "A Summary of McEliece-Type Cryptosystems and their Security," Journal of Mathematical Cryptology , Volume 1 (2), Apr 1, 2007 and Cryptology ePrint Archive: Report 2006/162, pages 4-14.
Java implementation of the McEliece scheme (see de.flexiprovider.pqc.ecc.mceliece)

Project 2: Implementation of RSA using DSP units

Resources:

D. Suzuki and T. Matsumoto, "How to Maximize the Potential of FPGA-Based DSPs for Modular Exponentiation," IEICE Trans. Fundamentals, vol. E94-A, no. 1, Jan. 2011, pp. 211-222.
D. Suzuki, "How to Maximize the Potential of FPGA Resources for Modular Exponentiation," Cryptographic Hardware and Embedded Systems workshop, CHES 2007, Vienna, Austria, LNCS, vol. 4727, pp. 272-288.
C implementation of the Montgomery multiplication (to be provided by the instructor)

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

Resources:

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

Resources:

J.S. Plank, "A Tutorial on Reed-Solomon Coding for Fault-Tolerance in RAID-like Systems," Software - Practice & Experience, 27(9), September 1997, pp. 995-1012 (see errata) and Technical Report UT-CS-96-332, University of Tennessee, July, 1996 (revised in 1999, errata in 2003).
Fast Galois Field Arithmetic Library in C/C++
L. Rizzo, "Effective Erasure Codes for Reliable Computer Communication Protocols," ACM SIG-COMM Computer Communication Review 27, 2 (1997), pp. 24–36.
Implementation in C: zfec

C.K.P. Clarke, "Reed-Solomon Error Correction," BBC R&D White Paper, WHP 031, July 2002.

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

Resources:

R. Maes, A. Van Herrewege, I. Verbauwhede, "PUFKY: A Fully Functional PUF-based Cryptographic Key Generator," Proc. CHES 2012, LNCS 7428, pp. 302-319.
S. Lin and D. Costello, Error Control Coding, 2nd. Ed., Prentice Hall, 2004.

Area: Financial Computations

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

Resources:

Decimal64 floating-point format, Wikipedia
IEEE 754-2008, Wikipedia
General Decimal Arithmetic website

C. Minchola, M. Vazquez, and G. Sutter, "A FPGA IEEE-754-2008 Decimal64 Floating-Point Adder/Subtractor," Proc. 2011 VII Southern Conference on Programmable Logic, SPL'11, Córdoba, Argentina, Apr. 2011.
C. Minchola and G. Sutter, "A FPGA IEEE-754-2008 Decimal64 Floating-Point Multiplier," Proc. 2009 International Conference on Reconfigurable Computing and FPGAs, ReConFig '09, Cancun, Mexico, Dec. 2011.
M. Baesler, S. Voigt, T. Teufel, "An IEEE 754-2008 Decimal Parallel and Pipelined FPGA Floating-Point Multiplier," 2010 International Conference on Field Programmable Logic and Applications, FPL 2010, Milan, Italy, Sep. 2010 (paper + slides).

Area: Factoring

Project 7: Trial Division by Small Primes

G. Southern, C. Mason, L. Chikkam, P. Baier, and K. Gaj, "FPGA Implementation of High Throughput Circuit for Trial Division by Small Primes," Proc. Special Purpose Hardware for Attacking Cryptographic Systems, SHARCS 2007, Vienna, Austria, Sep. 2007. (paper + slides)

Project 8: Pollard's Rho Method of Factoring

R. Bachimanchi, "FPGA and ASIC Implementation of Rho and P-1 Methods of Factoring," MS Thesis, George Mason University, May 2007 (thesis + slides). See in particular Chapters 2.1, 3, 4.2.

Area: FPGA-optimized Arithmetic Units

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

Resources:

H. Nguyen, B. Pasca, and T. Preusser, "FPGA-specific arithmetic optimizations of short-latency adders," in 2011 International Conference on Field Programmable Logic and Applications (FPL), 2011, pp. 232–237.
M. Rogawski, E. Homsirikamol, K. Gaj, "A Novel Modular Adder for One Thousand Bits and More Using Fast Carry Chains of Modern FPGAs" (unpublished, available on request).
S. Hauck, M.M. Hosler, and T.W. Fry, "High-Performance Carry Chains for FPGA’s," IEEE TVLSI, vol. 8, no. 2, April 2000.

Software Projects

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

Resources:

A. Abusharekh, Comparative Analysis of Multi-precision Arithmetic Libraries for Public Key Cryptography (text + slides), MS Thesis, George Mason University, Spring 2004.
GMP - The GNU Multiple Precision Arithmetic Library
MIRACL - Multiprecision Integer and Rational Arithmetic Cryptographic Library
RELIC - Efficient LIbrary for Cryptography
NTL - A Library for doing Number Theory
eBACS: ECRYPT Benchmarking of Cryptographic Systems

Analytical Projects

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

Resources:

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

Resources:

S.A. Khan, Digital Design of Signal Processing Systems: A Practical Approach, Wiley 2011. Chapter 12: CORDIC-based DDFS Architectures.
B. Parhami, Computer Arithmetic: Algorithms and Hardware Design, 2nd Edition, Oxford University Press, New York, 2010. Chapter 22 The CORDIC Algorithms.

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

Resources:

L. Tan and J. Jiang, Digital Signal Processing: Fundamentals and Applications, 2nd edition, Elsevier 2011, Chapter 4.5 Fast Fourier Transform.
S.A. Khan, Digital Design of Signal Processing Systems: A Practical Approach, Wiley 2011, Chapters 8.5.3-8.5.5, 8.6.
OpenCores: DSP Core.

Project 14: Comparative analysis of fast exponentiation algorithms

Resources:

Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone, Handbook of Applied Cryptography, CRC Press, Inc., 1996. Chapter 14: Efficient Implementations.
K. Okeya, K. Schmidt-Samoa, C. Spahn, and T. Takagi, "Signed Binary Representations Revisited," in Advances in Cryptology – CRYPTO 2004
LNCS 3152, 2004, pp. 123-139.

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

Tutorials

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

VHDL Instructions: Templates & Examples

Frequently Asked Questions about VHDL from comp.lang.vhdl

OpenCores Coding Guidelines

The Low Carb VHDL Tutorial - by Bryan Mealy

vhdl.org - 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