Tsutomu Sasao
Morgan & Claypool Publishers,
Oct. 2019.
Amazon.com ,
Preface... . . xv Acknowledgments.. . . . . . . . . . . . . xvii 1 Introduction.. . . . . . . . . . . . . . . . . . . 1 1.1 Motivation.. . . . . . . . . . . . . . . . . . 1 1.2 Organization of the Book.. . . . . . . 1 2 Applications..5 2.1 IP Address Table.. . . . . . . . . . . . . 5 2.2 Terminal Access Controller.. . . . . 5 2.3 URL List.. . . . . . . . . . . . . . . . . . . 7 2.4 Computer Virus Scanning Circuit.7 2.5 Memory Patch Circuit.. . . . . . . . . 8 2.6 List of English Words.. . . . . . . . . 8 2.7 Code Converter.. . . . . . . . . . . . . . 8 2.8 Remarks.. . . . . . . . . . . . . . . . . . 10 3 Definitions and Basic Properties.. . . 11 3.1 Logic Functions.. . . . . . . . . . . . . 11 3.2 Functional Decomposition.. . . . . 11 3.3 Symmetric Functions.. . . . . . . . . 14 3.4 Linear Functions.. . . . . . . . . . . . 15 3.5 Constant-Weight Code.. . . . . . . . 15 3.6 Eulerfs Number e and its Property. . . . . . . . . . . . . . . . . . . 16 3.7 Remarks.. . . . . . . . . . . . . . . . . . 17 3.8 Exercises.. . . . . . . . . . . . . . . . . . 17 4 Index Generation Functions and Their Realizations. . . . . . . 19 4.1 Index Generation Function.. . . . 19 4.2 LUT Cascade Realization.. . . . . 21 xii 4.3 Index Generation Unit (IGU).. . . 24 4.4 Remarks.. . . . . . . . . . . . . . . . . . 29 4.5 Exercises.. . . . . . . . . . . . . . . . . . 29 5 Minimization of Primitive Variables. . . . . . . . . . . . . . . . . . . 31 5.1 Minimization Algorithm.. . . . . . 31 5.2 Detection of Essential Variables.. 33 5.3 Random Index Generation Functions. . . . . . . . . . . . . . . . . 35 5.4 Remarks.. . . . . . . . . . . . . . . . . . 36 5.5 Exercises.. . . . . . . . . . . . . . . . . . 37 6 Linear Transformations of Input Variables. . . . . . . . . . . . . . 41 6.1 Linear Decomposition.. . . . . . . . 41 6.2 Reduction by Linear Transformations. . . . . . . . . . . . . . . . 43 6.3 Heuristic Method to Find Linear Transformations. . . . . . . 45 6.4 Experimental Results.. . . . . . . . . 51 6.4.1 m-out-of-n Code to Index Converter. . . . . . . . . . 51 6.4.2 Random Index Generation Functions. . . . . . . . . . 52 6.4.3 IP Address Tables.. . . . 53 6.4.4 Lists of English Words.. 53 6.5 Remarks.. . . . . . . . . . . . . . . . . . 54 6.6 Exercises.. . . . . . . . . . . . . . . . . . 54 7 Iterative Reduction of Compound Variables. . . . . . . . . . . . . 57 7.1 Improved Upper Bound.. . . . . . . 57 7.2 Illustrative Examples.. . . . . . . . . 61 7.3 Iterative Method to Reduce Compound Variables. . . . . . . 68 7.4 Comparison of Minimization Methods. . . . . . . . . . . . . . . 69 7.4.1 Random Index Generation Functions. . . . . . . . . . 69 7.4.2 m-out-of-n Code to Index Converters. . . . . . . . . 70 7.4.3 IP Address Tables.. . . . 71 7.4.4 Lists of English Words.. 72 7.4.5 URL List.. . . . . . . . . . . 73 7.4.6 Computation Time.. . . . 73 7.5 Remarks.. . . . . . . . . . . . . . . . . . 73 7.6 Exercises.. . . . . . . . . . . . . . . . . . 74 xiii 8 Irreducible Index Generation Function. . . . . . . . . . . . . . . . . 75 8.1 Irreducible Index Generation Function. . . . . . . . . . . . . . . . 75 8.2 Minimum-Weight Irreducible Index Generation Functions77 8.3 Normal Minimum-Weight Irreducible Index Generation Functions . . . . . . . . . . . . . 78 8.3.1 Equivalence Classes.. . . 78 8.3.2 Normal Function.. . . . . 79 8.3.3 A Fast Method to Detect Irreducible Index Generation Functions . . . . . . . 80 8.3.4 Improved Upper Bound.81 8.4 Remarks.. . . . . . . . . . . . . . . . . . 85 8.5 Exercises.. . . . . . . . . . . . . . . . . . 86 9 SAT-Based Method to Find Linear Transformations. . . . . . 89 9.1 SAT-Based Formulation.. . . . . . . 89 9.2 Reduction of Search Space for General Functions. . . . . . . 92 9.3 Reduction of Search Space for cf-Symmetric Functions. . . 94 9.4 Experimental Results.. . . . . . . . . 97 9.4.1 Minimization System.. . 97 9.4.2 Randomly Generated Functions. . . . . . . . . . . . . . 98 9.4.3 m-out-of-n Code to Index Converters. . . . . . . . . 98 9.5 Remarks.. . . . . . . . . . . . . . . . . . 99 9.6 Exercises.. . . . . . . . . . . . . . . . . 100 10 Statistical Approach.. . . . . . . . . . . 101 10.1 Hash Function.. . . . . . . . . . . . . 101 10.2 Number of Vectors Realized by Main Memory. . . . . . . . 101 10.3 Hybrid Method.. . . . . . . . . . . . 104 10.4 Super Hybrid Method.. . . . . . . 107 10.5 Parallel Sieve Method.. . . . . . . 110 10.6 Remarks.. . . . . . . . . . . . . . . . . 111 10.7 Exercises.. . . . . . . . . . . . . . . . . 112 11 Realization Using Four IGUs.. . . . . 115 11.1 Realization Using Four IGUs.. . 115 11.2 Selection of Linear Transformations. . . . . . . . . . . . . . . . 119 11.3 Experimental Results.. . . . . . . . 122 11.3.1 Realization with 4IGUs. . . . . . . . . . . . . . . . . . . 122 xiv 11.3.2 Effect of Independent Linear Transformations. . 123 11.4 Remarks.. . . . . . . . . . . . . . . . . 123 12 References on Index Generation Functions. . . . . . . . . . . . . 125 12.1 Reduction of Variables.. . . . . . . 125 12.2 Realization with Multiple IGUs.125 12.3 Decomposition.. . . . . . . . . . . . 126 12.4 Analysis.. . . . . . . . . . . . . . . . . 126 12.5 Architecture.. . . . . . . . . . . . . . . 126 12.6 Applications.. . . . . . . . . . . . . . 126 12.7 Survey.. . . . . . . . . . . . . . . . . . . 126 12.8 Miscellaneous.. . . . . . . . . . . . . 126 13 Conclusions.. . . . . . . . . . . . . . . . . . 127 A Solutions..129 A.1 Solutions for Exercises in Chapter 3. . . . . . . . . . . . . . . . 129 A.2 Solutions for Exercises in Chapter 4. . . . . . . . . . . . . . . . 130 A.3 Solutions for Exercises in Chapter 5. . . . . . . . . . . . . . . . 131 A.4 Solutions for Exercises in Chapter 6. . . . . . . . . . . . . . . . 132 A.5 Solutions for Exercises in Chapter 7. . . . . . . . . . . . . . . . 137 A.6 Solutions for Exercises in Chapter 8. . . . . . . . . . . . . . . . 142 A.7 Solutions for Exercises in Chapter 9. . . . . . . . . . . . . . . . 143 A.8 Solutions for Exercises in Chapter 10. . . . . . . . . . . . . . . 143 Bibliography.. . . . . . . . . . . . . . . . . 151 Authorfs Biography.. . . . . . . . . . . 159 Index... . . 161