Index Generation Functions
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 Eulerfs 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
Authorfs Biography.. . . . . . . . . . . 159
Index... . . 161

Back