Computer Arithmetics for Nanoelectronics Vlad P. Shmerko Svetlana N. Yanushkevich Sergey Edward Lyshevski Computer Arithmetics for Nanoelectronics Computer Arithmetics for Nanoelectronics Vlad P. Shmerko Svetlana N. Yanushkevich Sergey Edward Lyshevski Boca Raton London New York CRC Press is an imprint of the Taylor & Francis Group, an informa business CRC Press Taylor & Francis Group 6000 Broken Sound Parkway NW, Suite 300 Boca Raton, FL 33487-2742 © 2009 by Taylor & Francis Group, LLC CRC Press is an imprint of Taylor & Francis Group, an Informa business No claim to original U.S. Government works Version Date: 20131125 International Standard Book Number-13: 978-1-4200-6623-4 (eBook - PDF) This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been made to publish reliable data and information, but the author and publisher cannot assume responsibility for the validity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint. Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmit- ted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers. For permission to photocopy or use material electronically from this work, please access www.copyright. com (http://www.copyright.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged. Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe. Visit the Taylor & Francis Web site at http://www.taylorandfrancis.com and the CRC Press Web site at http://www.crcpress.com This book is dedicated to the memory of Claude Shannon CONTENTS Preface xxi 1 Introduction 1 1.1 Computational paradigms for nanocomputing structures . . . 1 1.2 Biological inspiration for computing . . . . . . . . . . . . . . 8 1.2.1 Artificial neural networks . . . . . . . . . . . . . . . . 8 1.2.2 Evolutionary algorithms and evolvable hardware . . . 10 1.2.3 Self-assembly . . . . . . . . . . . . . . . . . . . . . . . 11 1.3 Molecular computing devices . . . . . . . . . . . . . . . . . . 14 1.4 Fault tolerance . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.5 Computing in 3D . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.6 Multivalued processing . . . . . . . . . . . . . . . . . . . . . . 23 1.7 Further study . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2 Computational Nanostructures 29 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.2 Theoretical background . . . . . . . . . . . . . . . . . . . . . 30 Analysis and synthesis 2.3 . . . . . . . . . . . . . . . . . . . . 31 2.3.1 Design hierarchy . . . . . . . . . . . . . . . . . . . . . 32 2.3.2 Top-down design methodology . . . . . . . . . . . . . 33 2.3.3 Bottom-up design methodology . . . . . . . . . . . . . 34 2.3.4 Design styles . . . . . . . . . . . . . . . . . . . . . . . 35 2.3.5 Modeling and simulation . . . . . . . . . . . . . . . . . 35 2.4 Implementation technologies . . . . . . . . . . . . . . . . . . . 36 2.5 Predictable technologies . . . . . . . . . . . . . . . . . . . . . 40 2.6 Nanoelectronic networks . . . . . . . . . . . . . . . . . . . . . 42 2.6.1 CMOS-molecular electronics . . . . . . . . . . . . . . . 42 2.6.2 Neuromorphic computing paradigm. . . . . . . . . . . 42 2.6.3 Interconnect . . . . . . . . . . . . . . . . . . . . . . . . 43 2.6.4 Carbon-nanotube-basedlogic devices . . . . . . . . . . 44 2.6.5 Crossbar-basedcomputing structures . . . . . . . . . . 44 2.6.6 Noise. . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.7 Switch-based computing structures . . . . . . . . . . . . . . . 46 2.7.1 Switches . . . . . . . . . . . . . . . . . . . . . . . . . . 46 vii viii Contents 2.7.2 Switch-based networks represented by decision diagrams. . . . . . . . . . . . . . . . . . . . . . . . . . 48 2.8 Spatial computational nanostructures . . . . . . . . . . . . . . 51 2.8.1 Graph embedding problem. . . . . . . . . . . . . . . . 52 2.8.2 Embedding decision tree into spatial dimensions . . . 53 2.9 Further study . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3 Binary Arithmetic 59 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.2 Positional numbers . . . . . . . . . . . . . . . . . . . . . . . . 60 3.2.1 The decimal system . . . . . . . . . . . . . . . . . . . 60 3.2.2 Number radix . . . . . . . . . . . . . . . . . . . . . . . 61 3.2.3 Fractional binary numbers . . . . . . . . . . . . . . . . 64 3.2.4 Word size . . . . . . . . . . . . . . . . . . . . . . . . . 65 3.3 Counting in a positional number system . . . . . . . . . . . . 65 3.4 Basic arithmetic operations in various number systems . . . . 66 3.5 Binary arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . 66 3.6 Radix-complement representations . . . . . . . . . . . . . . . 69 3.6.1 10’s and 9’s Complement systems . . . . . . . . . . . . 70 3.6.2 1’s Complement system . . . . . . . . . . . . . . . . . 71 3.6.3 2’s Complement. . . . . . . . . . . . . . . . . . . . . . 72 3.7 Conversion of numbers in various radices . . . . . . . . . . . . 73 3.8 Overflow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 3.9 Implementation of binary arithmetic . . . . . . . . . . . . . . 80 3.10 Other binary codes . . . . . . . . . . . . . . . . . . . . . . . . 80 3.10.1 Gray code . . . . . . . . . . . . . . . . . . . . . . . . . 81 3.10.2 Weighted codes . . . . . . . . . . . . . . . . . . . . . . 83 3.10.3 Binary-coded decimal . . . . . . . . . . . . . . . . . . 84 3.11 Further study . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 4 Residue Arithmetic 87 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 4.2 The basics of residue arithmetic . . . . . . . . . . . . . . . . . 87 4.3 Addition in residue arithmetic . . . . . . . . . . . . . . . . . . 89 4.4 Multiplication in residue arithmetic . . . . . . . . . . . . . . . 89 4.5 Computing powers in residue arithmetic . . . . . . . . . . . . 91 4.6 Solving modular equations . . . . . . . . . . . . . . . . . . . . 92 4.7 Complete residue systems . . . . . . . . . . . . . . . . . . . . 92 4.8 Further study . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 5 Graph-Based Data Structures 97 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 5.2 Graphs in discrete device and system design . . . . . . . . . . 97 5.2.1 Graphs at the logical level . . . . . . . . . . . . . . . . 97 5.2.2 Graphs at the physical design level . . . . . . . . . . . 99 Contents ix 5.3 Basic definitions . . . . . . . . . . . . . . . . . . . . . . . . . 99 5.3.1 Directed graphs . . . . . . . . . . . . . . . . . . . . . . 100 5.3.2 Flow graphs . . . . . . . . . . . . . . . . . . . . . . . . 101 5.3.3 Undirected graphs . . . . . . . . . . . . . . . . . . . . 102 5.3.4 A path in a graph . . . . . . . . . . . . . . . . . . . . 103 5.3.5 Isomorphism . . . . . . . . . . . . . . . . . . . . . . . 103 5.3.6 A subgraph and spanning tree. . . . . . . . . . . . . . 104 5.3.7 Cartesian product . . . . . . . . . . . . . . . . . . . . 106 5.3.8 Planarity . . . . . . . . . . . . . . . . . . . . . . . . . 106 5.3.9 Operations on graphs . . . . . . . . . . . . . . . . . . 107 5.3.10 Embedding . . . . . . . . . . . . . . . . . . . . . . . . 108 5.4 Tree-like graphs and decision trees . . . . . . . . . . . . . . . 108 5.4.1 Basic definitions . . . . . . . . . . . . . . . . . . . . . 109 5.4.2 Lattice topology of graphs . . . . . . . . . . . . . . . . 110 5.4.3 H-trees. . . . . . . . . . . . . . . . . . . . . . . . . . . 111 5.4.4 Binary decision trees and functions . . . . . . . . . . . 112 5.4.5 The relationship between decision trees and cube-like graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 5.4.6 The simplification of graphs . . . . . . . . . . . . . . . 113 5.5 Voronoi diagrams . . . . . . . . . . . . . . . . . . . . . . . . . 115 5.5.1 Direct and inverse Voronoi transform . . . . . . . . . . 118 5.5.2 Distance mapping of feature points . . . . . . . . . . . 120 5.5.3 Distance map . . . . . . . . . . . . . . . . . . . . . . . 121 5.6 Further study . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 6 Foundation of Boolean Data Structures 131 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 6.2 Definition of algebra over the set {0,1} . . . . . . . . . . . . . 132 6.2.1 Boolean algebra over the set {0,1} . . . . . . . . . . . 132 6.2.2 Postulates . . . . . . . . . . . . . . . . . . . . . . . . . 132 6.2.3 The principle of duality . . . . . . . . . . . . . . . . . 133 6.2.4 Switch-based interpretation . . . . . . . . . . . . . . . 136 6.2.5 Boolean algebra over Boolean vectors. . . . . . . . . . 136 6.2.6 DeMorgan’s law. . . . . . . . . . . . . . . . . . . . . . 138 6.3 Boolean functions . . . . . . . . . . . . . . . . . . . . . . . . . 138 6.3.1 Boolean formulas . . . . . . . . . . . . . . . . . . . . . 138 6.3.2 Boolean functions. . . . . . . . . . . . . . . . . . . . . 139 6.4 Fundamentals of computing Boolean functions . . . . . . . . . 140 6.4.1 Literals and terms . . . . . . . . . . . . . . . . . . . . 141 6.4.2 Minterms and maxterms . . . . . . . . . . . . . . . . . 141 6.4.3 Canonical SOP and POS expressions . . . . . . . . . . 142 6.4.4 Algebraic construction of standard SOP and POS forms . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 6.5 Proving the validity of Boolean equations . . . . . . . . . . . 145 6.6 Gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 x Contents 6.6.1 Elementary Boolean functions . . . . . . . . . . . . . . 147 6.6.2 Switch models for logic gates . . . . . . . . . . . . . . 147 6.6.3 Timing diagrams . . . . . . . . . . . . . . . . . . . . . 150 6.6.4 Performance parameters . . . . . . . . . . . . . . . . . 153 6.7 Local transformations . . . . . . . . . . . . . . . . . . . . . . 153 6.8 Properties of Boolean functions . . . . . . . . . . . . . . . . . 154 6.8.1 Self-dual Boolean functions . . . . . . . . . . . . . . . 155 6.8.2 Monotonic Boolean functions . . . . . . . . . . . . . . 156 6.8.3 Linear functions . . . . . . . . . . . . . . . . . . . . . 162 6.8.4 Universal set of functions . . . . . . . . . . . . . . . . 163 6.9 Further study . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 7 Boolean Data Structures 169 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 7.2 Data structure types . . . . . . . . . . . . . . . . . . . . . . . 170 7.3 Relationships between data structures . . . . . . . . . . . . . 170 7.4 The truth table . . . . . . . . . . . . . . . . . . . . . . . . . . 171 7.4.1 Construction of the truth table . . . . . . . . . . . . . 171 7.4.2 Truth tables for incompletely specified functions . . . 172 7.4.3 Truth vector . . . . . . . . . . . . . . . . . . . . . . . 173 7.4.4 Minterm and maxterm representations . . . . . . . . . 174 7.4.5 Reduction of truth tables . . . . . . . . . . . . . . . . 174 7.4.6 Properties of the truth table . . . . . . . . . . . . . . . 175 7.4.7 Deriving standard SOP and POS expressions from a truth table . . . . . . . . . . . . . . . . . . . . . . . . 176 7.5 K-map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 7.5.1 RepresentationofstandardSOPandPOSexpressions using K-maps . . . . . . . . . . . . . . . . . . . . . . . 178 7.5.2 A K-map for a Boolean function of two variables . . . 178 7.5.3 A K-map for a Boolean function of three variables . . 178 7.5.4 A K-map for a Boolean function of four variables . . . 179 7.5.5 A K-map for an incompletely specified Boolean function . . . . . . . . . . . . . . . . . . . . . . . . . . 180 7.6 Cube data structure . . . . . . . . . . . . . . . . . . . . . . . 182 7.7 Graphical data structure for cube representation . . . . . . . 184 7.8 Logic networks . . . . . . . . . . . . . . . . . . . . . . . . . . 190 7.8.1 Design goals . . . . . . . . . . . . . . . . . . . . . . . . 190 7.8.2 Basic components of a logic network . . . . . . . . . . 191 7.8.3 Specification . . . . . . . . . . . . . . . . . . . . . . . 193 7.8.4 Network verification . . . . . . . . . . . . . . . . . . . 193 7.9 Networks of threshold gates . . . . . . . . . . . . . . . . . . . 195 7.9.1 Threshold functions . . . . . . . . . . . . . . . . . . . 195 7.9.2 McCulloch–Pitts models of Boolean functions . . . . . 196 7.9.3 Threshold networks. . . . . . . . . . . . . . . . . . . . 197 7.10 Binary decision trees . . . . . . . . . . . . . . . . . . . . . . . 198 Contents xi 7.10.1 RepresentationofelementaryBooleanfunctionsusing decision trees . . . . . . . . . . . . . . . . . . . . . . . 199 7.10.2 Minterm and maxterm expression representations using decision trees . . . . . . . . . . . . . . . . . . . . 199 7.10.3 Representation of elementary Boolean functions by incomplete decision trees . . . . . . . . . . . . . . . . . 202 7.11 Decision diagrams . . . . . . . . . . . . . . . . . . . . . . . . 204 7.12 Further study . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 8 Fundamental Expansions 209 8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 8.2 Shannon expansion . . . . . . . . . . . . . . . . . . . . . . . . 211 8.2.1 Expansion with respect to a single variable . . . . . . 211 8.2.2 Expansion with respect to a group of variables . . . . 214 8.2.3 Expansion with respect to all variables . . . . . . . . . 216 8.2.4 Various forms of Shannon expansions . . . . . . . . . . 218 8.3 Shannon expansion for symmetric Boolean functions . . . . . 219 8.3.1 Symmetric functions . . . . . . . . . . . . . . . . . . . 220 8.3.2 Partially symmetric Boolean functions . . . . . . . . . 221 8.3.3 Totally symmetric Boolean functions . . . . . . . . . . 221 8.3.4 Detection of symmetric Boolean functions . . . . . . . 223 8.3.5 Characteristic set . . . . . . . . . . . . . . . . . . . . . 223 8.3.6 Elementary symmetric functions . . . . . . . . . . . . 224 8.3.7 Operations on elementary symmetric functions . . . . 225 8.3.8 Shannon expansion with respect to a group of symmetric variables . . . . . . . . . . . . . . . . . . . 227 8.4 Techniques for computing symmetric functions . . . . . . . . 227 8.4.1 Computing partially symmetric functions . . . . . . . 227 8.4.2 Computing totally symmetric functions . . . . . . . . 228 8.4.3 Carrier vector . . . . . . . . . . . . . . . . . . . . . . . 232 8.5 The logic Taylor expansion . . . . . . . . . . . . . . . . . . . 233 8.5.1 Change in a digital system. . . . . . . . . . . . . . . . 234 8.5.2 Boolean difference . . . . . . . . . . . . . . . . . . . . 234 8.5.3 Boolean difference and Shannon expansion. . . . . . . 236 8.5.4 Properties of Boolean difference . . . . . . . . . . . . . 237 8.5.5 The logic Taylor expansion . . . . . . . . . . . . . . . 238 8.6 Graphical representation of fundamental expansions . . . . . 244 8.6.1 Shannon expansion as a decision tree node function. . 244 8.6.2 Matrix notation of the node function . . . . . . . . . . 245 8.6.3 Using Shannon expansion in decision trees . . . . . . . 245 8.7 Further study . . . . . . . . . . . . . . . . . . . . . . . . . . . 248 9 Arithmetic of the Polynomials 255 9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255 9.2 Algebra of the polynomial forms . . . . . . . . . . . . . . . . 263