Walsh-Hadamard Transform

1. What is the Walsh-Hadamard Transform?

The Walsh-Hadamard Transform (WHT) is a linear, orthogonal transform similar to the Fourier Transform but:

• Uses only +1 and -1 coefficients instead of sines and cosines.
• Very fast to compute, especially for powers-of-two-sized data (2×2, 4×4, 8×8…).
• Converts a signal or image from the spatial domain into the frequency domain (or more accurately, into Walsh frequencies).

It is used in:

• Image compression (like JPEG variants)
• Image processing / filtering
• Pattern recognition
• Fast signal processing

2. How WHT Works (Intuition)

Imagine an image block (e.g., 4×4) as a set of numbers. The WHT multiplies this block by a Hadamard matrix (Hₙ), which is a square matrix of size 2ⁿ × 2ⁿ, with only +1 and -1 entries. Each row of Hₙ represents a Walsh function (a pattern of +1 and -1).

Multiplying the image by Hₙ projects the image onto these patterns, producing coefficients that represent different “frequency components.”

Key idea:

• Row 1 of Hₙ → all + → captures the average brightness (low frequency)
• Row 2 → + – + – → captures horizontal changes
• Row 3 → ++– pattern → captures vertical changes
• Subsequent rows → higher “frequencies,” detecting edges, diagonals, and complex patterns

3. Mathematical Formulation

Let I be an image block (n×n), and Hₙ be the Hadamard matrix of the same size:

W = Hₙ × I × Hₙ

Where:

• W = WHT coefficients (same size as I)
• Hₙ = Hadamard matrix (orthogonal, entries +1/-1)

If you want normalized WHT, divide by n:

W_normalized = (1/n) × Hₙ × I × Hₙ

Step-by-step computation:

1. Multiply Hₙ × I → intermediate matrix
2. Multiply result × Hₙ → final WHT
3. Optionally divide by n to normalize

---

Walsh-Hadamard Transform Examples

2×2 Example

1	2
3	4

1	1
1	-1

4	6
-2	-2

10	-2
-4	0

---

4×4 Example

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

1	1	1	1
1	-1	1	-1
1	1	-1	-1
1	-1	-1	1

28	32	36	40
-8	-8	-8	-8
-16	-16	-16	-16
0	0	0	0

1360	-140	-140	0
-320	-160	0	0
-640	-320	0	0
0	0	0	0

---

8×8 Example

1	2	3	4	5	6	7	8
9	10	11	12	13	14	15	16
17	18	19	20	21	22	23	24
25	26	27	28	29	30	31	32
33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48
49	50	51	52	53	54	55	56
57	58	59	60	61	62	63	64

1	1	1	1	1	1	1	1
1	-1	1	-1	1	-1	1	-1
1	1	-1	-1	1	1	-1	-1
1	-1	-1	1	1	-1	-1	1
1	1	1	1	-1	-1	-1	-1
1	-1	1	-1	-1	1	-1	1
1	1	-1	-1	-1	-1	1	1
1	-1	-1	1	-1	1	1	-1

Step 1: Multiply H8 × I → intermediate matrix.

Step 2: Multiply intermediate × H8 → Final WHT. Optionally divide by 8 to normalize.