Preface ........................................................ xi
Chapter 1. Introduction ......................................... 1
PART 1. HADAMARD MATRICES, THEIR APPLICATIONS AND
GENERALISATIONS ......................................... 7
Chapter 2. Hadamard Matrices .................................... 9
2.1. Classical Constructions ................................... 10
2.1.1. Sylvester Hadamard matrices ........................ 11
2.1.2. Paley Hadamard matrices ............................ 11
2.1.3. Hadamard designs ................................... 12
2.1.4. Williamson Hadamard matrices ....................... 15
2.2. Equivalence Classes ....................................... 16
2.3. The First Link: Group Developed Constructions ............. 20
2.3.1. Menon Hadamard matrices ............................ 21
2.3.2. Ito Hadamard matrices .............................. 23
2.4. Towards the Hadamard Conjecture ........................... 25
Chapter 3. Applications in Signal Processing, Coding and
Cryptography ........................................ 27
3.1. Spectroscopy: Walsh-Hadamard Transforms ................... 28
3.1.1. Signal analysis and synthesis ...................... 28
3.1.2. The Walsh-Hadamard Transform ....................... 29
3.1.3. The Fast Hadamard Transform ........................ 33
3.1.4. Hadamard spectroscopy .............................. 33
3.2. Error Correction: Hadamard Codes .......................... 35
3.2.1. Error-correcting codes ............................. 36
3.2.2. Hadamard codes ..................................... 39
3.3. Signal Modulation and Separation: Hadamard Codes .......... 43
3.3.1. CDMA for mobile, wireless and optical
communications ..................................... 45
3.3.2. 3-D holographic memory for data storage and
retrieval .......................................... 47
3.4. Signal Correlation: Perfect Sequences and Arrays .......... 48
3.4.1. Timing and synchronisation: Perfect binary
sequences .......................................... 49
3.4.2. Signal array correlation: Perfect binary arrays .... 50
3.5. Cryptography: Nonlinear Functions ......................... 53
3.5.1. Binary bent functions and maximally nonlinear
functions .......................................... 55
3.5.2. Perfect and almost perfect nonlinear functions ..... 59
Chapter 4. Generalised Hadamard Matrices ....................... 62
4.1. Butson Matrices ........................................... 63
4.2. Complex Hadamard Matrices ................................. 66
4.2.1. Quaternary complex Hadamard matrices ............... 67
4.2.2. Unimodular complex Hadamard matrices ............... 69
4.3. Generalised Hadamard Matrices ............................. 70
4.3.1. Generalised Hadamard matrix constructions .......... 71
4.3.2. Generalised Hadamard matrices and Butson
matrices ........................................... 73
4.3.3. Generalised Hadamard matrices and class regular
divisible designs .................................. 74
4.3.4. Group developed GH(w, v/w) and semiregular
relative difference sets ........................... 75
4.4. Applications of Complex and Generalised Hadamard
Matrices .................................................. 78
4.4.1. Quaternary complex Hadamard transforms ............. 78
4.4.2. Perfect quaternary sequences and arrays ............ 79
4.4.3. Quaternary error-correcting codes .................. 81
4.4.4. Generalised Hadamard matrices and Hadamard codes ... 83
4.5. Unification: Generalised Butson Hadamard Matrices and
Transforms ................................................ 84
4.5.1. The jacket matrix construction ..................... 85
4.5.2. The Generalised Hadamard Transform ................. 90
Chapter 5. Higher Dimensional Hadamard Matrices ................ 92
5.1. Classical Constructions ................................... 94
5.1.1. Boolean function construction for order 2 .......... 95
5.1.2. Product construction ............................... 97
5.1.3. Group developed construction ....................... 97
5.1.4. Perfect binary array construction .................. 98
5.2. Equivalence Classes ....................................... 99
5.3. Applications in Spectroscopy, Coding and Cryptography .... 100
5.3.1. Multidimensional Walsh Hadamard transforms ........ 101
5.3.2. Error-correcting array codes ...................... 102
5.3.3. Cryptography: bent functions and the strict
avalanche criterion ............................... 105
5.4. The Second Link: Cocyclic Construction ................... 106
PART 2. COCYCLIC HADAMARD MATRICES ............................ 111
Chapter 6. Cocycles and Cocyclic Hadamard Matrices ............ 113
6.1. Cocycles and Group Cohomology ............................ 114
6.2. Cocycles are Everywhere .................................. 116
6.2.1. Examples of cocycles .............................. 116
6.2.2. New from old ...................................... 117
6.2.3. Characteristic properties ......................... 119
6.2.4. Orthogonality and its inheritance ................. 121
6.3. Computation of Cocycles .................................. 122
6.3.1. Algorithm 1 — abelian groups ...................... 124
6.3.2. Algorithm 2 — MAGMA implementation ................ 126
6.3.3. Algorithm 3 — Homological perturbation ............ 127
6.4. Cocyclic Hadamard Matrices ............................... 128
6.4.1 Sylvester Hadamard matrices ........................ 128
6.4.2. Menon Hadamard matrices ........................... 129
6.4.3. Williamson Hadamard matrices ...................... 129
6.4.4. Ito Hadamard matrices ............................. 129
6.4.5. Generalisations of Ito Hadamard matrices .......... 130
6.4.6. Numerical results ................................. 131
6.5. The Cocyclic Hadamard Conjecture ......................... 133
6.5.1. Noncocyclic Hadamard matrix constructions? ........ 134
6.5.2. Status report — research problems in cocyclic
Hadamard matrices ................................. 137
Chapter 7. The Five-fold Constellation ........................ 139
7.1. Factor Pairs and Extensions .............................. 139
7.2. Orthogonality for Factor Pairs ........................... 143
7.3. All the Cocyclic Generalised Hadamard Matrices ........... 146
7.3.1 Cocyclic generalised Hadamard matrix
constructions ...................................... 149
7.4. The Five-fold Constellation .............................. 151
7.4.1. Restrictions on existence of cocyclic
generalised Hadamard matrices ..................... 158
7.4.2. Two approaches .................................... 160
Chapter 8. Bundles and Shift Action ........................... 162
8.1. Bundles and the Five-fold Constellation .................. 163
8.1.1. Equivalence of transversals ....................... 163
8.1.2. Bundles of factor pairs ........................... 165
8.2. Bundles of Functions — The Splitting Case ................ 170
8.3. Bundles of Cocycles — The Central Case ................... 174
8.3.1. Automorphism action versus shift action ........... 174
8.3.2. A taxonomy for central semiregular RDS s .......... 176
8.3.3. Bundles with trivial shift action — the
multiplicative cocycles ........................... 178
8.4. Shift Action — The Central Case .......................... 181
8.4.1. Orbit structure for cyclic groups ................. 184
8.4.2. Relationship between orbit structures in
distinct cohomology classes ....................... 185
8.5. Shift Orbits — The Central Splitting Case ................ 185
8.5.1. When С is an elementary abelian p-group ........... 187
8.5.2. When С is an elementary abelian p-group and G
is a p-group ...................................... 188
Chapter 9. The Future: Novel Constructions and Applications ... 192
9.1. New Applications of Cocycles ............................. 192
9.1.1. Computation in Galois rings ....................... 192
9.1.2. Elliptic curve cryptosystems ...................... 195
9.1.3. Cocyclic codes .................................... 197
9.1.4. Cocyclic Butson matrices and codes ................ 202
9.2. New Group Developed Generalised Hadamard Matrices ........ 204
9.2.1. Group developed GH matrices and PN functions ...... 204
9.2.2. PN functions and a theory of highly nonlinear
functions ......................................... 208
9.3. New Cocyclic Generalised Hadamard Matrices ............... 212
9.3.1. Direct sum constructions .......................... 212
9.3.2. Multiplicative orthogonal cocycles and
presemifields ..................................... 216
9.3.3. Swing action ...................................... 224
9.4. New Hadamard Codes ....................................... 225
9.4.1. Class A cocyclic Hadamard codes ................... 225
9.4.2. Class В cocyclic Hadamard codes ................... 227
9.4.3. Class С cocyclic Hadamard codes ................... 229
9.5. New Highly Nonlinear Functions ........................... 230
9.5.1. 1-D differential uniformity ....................... 230
9.5.2. Differential 2-row uniformity and APN functions ... 233
9.5.3. 2-D total differential uniformity ................. 235
Bibliography .................................................. 238
Index ......................................................... 259
|
