Hadamard Matrices

ICMS

HADAMARD MATRICES

Jacques Hadamard (1865-1963) is best known as the mathematician who first proved the prime number theorem (in 1896). In 1893, he introduced Hadamard matrices that have found important applications in creating Error Correcting Codes, Experimental and Combinatorial Designs, Weighing Matrices, masks for spectroscopic analysis; and in Encryption and several other fields.

Hadamard matrices are square matrices of order n with the following properties:

These matrices also satisfy the following:

n must be 1, 2 or 4k.

The scalar product of any two distinct rows (or columns) is zero (that is, they are orthogonal).

If every entry of the square matrix B (of order n) has absolute value at most 1, then | det B| £ | det H| = nⁿ^/2.

If all the entries in the first row and the first column of a Hadamard matrix are +1, then it is called normalised. A normalised Hadamard matrix of order n satisfies:

Construction of Hadamard Matrices

If H is a Hadamard matrix, then so is .

This gives an easy way of generating a Hadamard matrix of order 2k from that of order k.

*Let H =* .**
Then the above procedure gives us the following normalised Hadamard matrix:

You are invited to visit our computer display to see examples of Hadamard matrices of various orders.

HADAMARD MATRICES & ERROR CORRECTING CODES

Hadamard Matrices have played an important role in error correction. In 1971 it was a Hadamard (error correcting) code that Mars Mariner 9 used to transmit some of the first and most stunning full-colour photographs of Mars.

Hadamard codes are used because they have maximal error correction capability for a given length of codeword and are fast and easy to implement in computer hardware.

Constructing a Hadamard Code

Take a Hadamard matrix H. In the rows of H and H replace each 1 by 0. This gives us the list of the codewords. A Hadamard matrix of order n=2^k will produce a Hadamard code with 2^k+1 codewords. The code has minimum distance 2^{k- 1} and hence detects up to 2^{k- 1-} 1 errors and corrects up to 2^{k- 2-} 1 errors. (Take a look at the construction of these codes on our computer display).

Coding and Decoding

If the method described in the panel Hadamard Matrices is used to generate H (of order n), then the resulting Hadamard code is a linear code. We can then find a generator matrix. The coding function thus maps B^k^+1® Bⁿ.

Syndrome decoding is not used for Hadamard codes. The nature of these codes allows decoding with greater efficiency.

Decoding Procedure

Let the received codeword be w.

In w replace every 0 with 1 to get v.
Calculate vH^T = ( a₁,&,a_i,&,a_n) .
Find r such that | a_r| ³ | a_i| for each i. This position will be unique if at most 2^{k- 2-} 1 errors have occurred.
Correct w to the codeword corresponding to the r^th row of H (if a_{r >} 0) or to the r^th row of H (if a_r < 0).

The following example illustrates the decoding procedure. Where we have used a Hadamard matrix of order 16:

HADAMARD MATRICES & EXPERIMENTAL DESIGNS

Experimentation is an essential part of the scientific investigation of nature. Design of experiments has become an important branch of mathematics, especially combinatorics.

One important class of combinatorial designs is Block Designs. The purpose of the experiment is to test v objects (called varieties) on several subjects so that their relative merits can be ascertained. An obvious way is to test all the varieties on all the subjects. Besides being uneconomical, this is often impossible. Therefore we impose some restrictions on the design of the experiment.

A Block Design consists of a set S of v varieties and a collection of b subsets of S, called blocks. Statistical considerations make the following conditions natural to a Block Design -

If k < v then the design is called an Incomplete Block Design. If we wish to make pair-wise comparisons, then the following additional condition is imposed

A (b, n , r, k, l )- Balanced Incomplete Block Design (BIBD) is an Incomplete Block Design satisfying the three conditions.

A convenient way to express a BIBD is to use a matrix, called the incidence matrix. Here each row represents a block, while each column represents a variety. The entries in the matrix are filled thus, if the first block contains the first variety, then the corresponding entry, i.e., a₁₁ = 1, otherwise a₁₁ = 0 and likewise for all the other entries.

Hadamard matrices generate incidence matrices of a special class of BIBDs where b = v (and this forces k = r). Such a BIBD is called (n , k, l ) - BIBD. In fact, a Hadamard Matrix of order 4m exists if and only if there exists a (4m- 1, 2m- 1, m- 1) - BIBD.

For example, by this process, a normalised Hadamard matrix of order 8 gives the incidence matrix for a (7, 3, 1) BIBD. For this and other similar constructions, please see our computer display.

CRYPTOGRAPHY, S-BOXES AND HADAMARD MATRICES

The Importance of Private Key Encryption

Private key encryption has become important in the modern era as the standard encryption for e-commerce, e-banking and e-mail. Claude Shannon (1940s) outlined two characteristics that have since become an integral part of new private key cryptographic algorithms - confusion and diffusion. Confusion obscures the relationship between plain text and cipher text. Diffusion spreads the redundancies through the coded data. Both frustrate attempts to look at redundancies and statistical patterns that are of great help in cracking the cipher.

Block Ciphers - DES et al

Block ciphers encrypt data in chunks or "blocks". The first block cipher to gain widespread popularity and endorsement by several government agencies was DES (Data Encryption Standard). After being adopted as a standard by ANSI in 1981, DES has been the algorithm of choice for many organisations throughout the world.

In a private-key encryption system like DES, the only secret component is the key. The key is used to generate several subkeys of required length (48 bits each). M is the message of length 32 bits that is to be encrypted. It is first expanded to length 48 (getting P) using a certain fixed expansion permutation. Next find P XOR K, where K is a subkey. This is then broken into 8 strings of length 6 bits. Each of these is substituted (confusion) by an entry from the 8 S-Boxes (S stands for Substitution). The outputs are 4 bit strings which are joined to form a single string of length 32 bits. This final output is then permuted (diffusion). This process is repeated 16 times using a different subkey every time.

If you are interested in how S-Boxes work, please see our computer display.

Design Of S-Boxes

In cracking these block ciphers the most powerful and common techniques used are differential & linear cryptanalysis. These methods depend on feeding in known plain texts and evaluating the relationship between the resultant cipher texts. To protect the cipher from these attacks, the S-Boxes must satisfy

Mathematical tools such as Hadamard Matrices and the Walsh-Hadamard Transform enable one to create S-Boxes satisfying these properties.