Lecture

Datapath Subsystems Design

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

In course

EE-330: Digital IC design

Digital IC Design presents the fundamentals of digital integrated circuit design. The methods and techniques aiming at the fabrication and development of digital integrated circuits are reviewed, the major design style pertaining to digital logic and memor ...

Description

This lecture covers the design of datapath subsystems, focusing on various types of adders including carry-lookahead, carry-select, carry-save, and parallel-prefix adders. It also discusses multiplication algorithms, such as shift-and-add, array multipliers, and Booth's algorithm, as well as non-restoring division. The presentation includes examples and comparisons of adder performances.

Instructor

Alexandre Schmid

Alexandre Schmid received the M.Sc. degree in microengineering and the Ph.D. degree in electrical engineering from the Swiss Federal Institute of Technology (EPFL), Lausanne, Switzerland, in 1994 and 2000, respectively. Since 1994, he has been with the EPFL, working with the Integrated Systems Laboratory as a Research and Teaching Assistant, and with the Electronics Laboratories as a Postdoctoral Fellow. In 2002, he was a Senior Research Associate with the Microelectronic Systems Laboratory, where he has been conducting research in the fields of bioelectronic interfaces and implantable biomedical electronics, nonconventional signal processing and neuromorphic hardware, and reliability of nanoelectronic devices, and also teaches with the Microengineering and Electrical Engineering Departments of EPFL. Since 2011, he is a Maître d'Enseignement et de Recherche (MER) Faculty Member with EPFL. He is a coauthor of two books, Reliability of Nanoscale Circuits and Systems, Methodologies and Circuit Architectures, Springer, 2011, and Wireless Cortical Implantable Systems, Springer, 2013, and a coeditor of one book, as well as over 100 articles published in journals and conferences. Dr. Schmid has served as the General Chair of the Fourth International Conference on Nano-Networks in 2009 and has been serving as an Associate Editor of the Institute of Electrical, Information, and Communication Engineers Electronics Express since 2009.

Official source

Related concepts (32)

Multiplication algorithm

A multiplication algorithm is an algorithm (or method) to multiply two numbers. Depending on the size of the numbers, different algorithms are more efficient than others. Efficient multiplication algorithms have existed since the advent of the decimal system. If a positional numeral system is used, a natural way of multiplying numbers is taught in schools as long multiplication, sometimes called grade-school multiplication, sometimes called the Standard Algorithm: multiply the multiplicand by each digit of the multiplier and then add up all the properly shifted results.

Booth's multiplication algorithm

Booth's multiplication algorithm is a multiplication algorithm that multiplies two signed binary numbers in two's complement notation. The algorithm was invented by Andrew Donald Booth in 1950 while doing research on crystallography at Birkbeck College in Bloomsbury, London. Booth's algorithm is of interest in the study of computer architecture. Booth's algorithm examines adjacent pairs of bits of the 'N'-bit multiplier Y in signed two's complement representation, including an implicit bit below the least significant bit, y−1 = 0.

Binary multiplier

A binary multiplier is an electronic circuit used in digital electronics, such as a computer, to multiply two binary numbers. A variety of techniques can be used to implement a digital multiplier. Most techniques involve computing the set of partial products, which are then summed together using binary adders. This process is similar to long multiplication, except that it uses a base-2 (binary) numeral system. Between 1947 and 1949 Arthur Alec Robinson worked for English Electric Ltd, as a student apprentice, and then as a development engineer.

Karatsuba algorithm

The Karatsuba algorithm is a fast multiplication algorithm. It was discovered by Anatoly Karatsuba in 1960 and published in 1962. It is a divide-and-conquer algorithm that reduces the multiplication of two n-digit numbers to three multiplications of n/2-digit numbers and, by repeating this reduction, to at most single-digit multiplications. It is therefore asymptotically faster than the traditional algorithm, which performs single-digit products.

Matrix multiplication algorithm

Because matrix multiplication is such a central operation in many numerical algorithms, much work has been invested in making matrix multiplication algorithms efficient. Applications of matrix multiplication in computational problems are found in many fields including scientific computing and pattern recognition and in seemingly unrelated problems such as counting the paths through a graph. Many different algorithms have been designed for multiplying matrices on different types of hardware, including parallel and distributed systems, where the computational work is spread over multiple processors (perhaps over a network).

Related lectures (64)

Algorithms for Big Numbers: Z_n and Orders

Covers algorithms for big numbers, Z_n, and orders in a group, explaining arithmetic operations and cryptographic concepts.

Analyse 2: Division euclidienne

Explores the process of division euclidienne in polynomials, emphasizing the importance of polynomial degrees during operations.

Datapath Subsystems Design

Covers the design of datapath subsystems, focusing on basic combinational components and various implementation options for adders, multipliers, and shifters.

Polynomials: Operations and Properties

Explores polynomial operations, properties, and subspaces in vector spaces.

Linear Algebra: Matrices Properties