Generate Hadamard transform martrix and Walsh transform martrix. input n is the log2(width) n = 2, H4 n = 3, H8

printHadamard.py

# -*- coding: utf-8 -*-
"""
Created on Fri May 24 10:29:36 2013
 
@author: Stardrad Yin
"""
# http://fourier.eng.hmc.edu/e161/lectures/wht/node3.html
 
import numpy
from Tkinter import Tk
 
def getBitArray(iNum, bits = 0):
    rst = []
    while iNum > 0:
        rst.append(iNum & 1)
        iNum >>= 1
    while len(rst) < bits:
        rst.append(0)
    return rst
 
def getNewIdx(num, mN):
    # print num,
    tar = 0
    for i in xrange(mN):
        bit = (num & 1) ^ ((num & 2) >> 1)
        # tar |= (bit << i) # Get Grey Code
        tar |= (bit << (mN - i - 1)) # Get Grey Code and bit reverse
        num >>= 1    
    # print '->', tar
    return tar
 
def sequenceOrder(martrix, mN):
    rows = 2 ** mN
    rtMar = [0] * (rows ** 2)
    for i in xrange(rows):
            j = getNewIdx(i, mN)            
            rtMar[i*rows: (i+1)*rows] = martrix[j*rows: (j+1)*rows]
    return rtMar
        
def printMartrix(naHad, copyTo = False):
    nM = int(numpy.sqrt(len(naHad)))
    tmpStr = ''
    for i in xrange(nM):
        for j in xrange(nM):
            tmpStr += '{:3d}'.format(naHad[i*nM + j])
        tmpStr += '\n'
    print tmpStr
    if copyTo:
        r = Tk()
        r.withdraw()
        r.clipboard_clear()
        r.clipboard_append(tmpStr)
        r.destroy()
 
oriStr = raw_input('Please input n:')
while not oriStr.isdigit() and eval(oriStr) > 0:
    print 'Not a number'
    oriStr = raw_input('Please input n:')
    
n = int(eval(oriStr))
 
tmpStr = ''
naHad = []
 
for x in xrange(2 ** n):
    for y in xrange(2 ** n):
        naHad.append((-1) ** (numpy.dot(getBitArray(x, n), getBitArray(y, n)) ) )
 
print 'Natural Order Hadamard Martrix:'
printMartrix(naHad)
seMar = sequenceOrder(naHad, n)
print 'Sequenced Order Hadamard Martrix(AVC, HEVC):'
printMartrix(seMar, True)
print 'Sequnced..Martrix copied to clipboard'

n = 3, output is :

Natural Order Hadamard Martrix:
  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

Sequenced Order Hadamard Martrix(AVC, HEVC):
  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

n = 2

Natural Order Hadamard Martrix:
  1  1  1  1
  1 -1  1 -1
  1  1 -1 -1
  1 -1 -1  1

Sequenced Order Hadamard Martrix(AVC, HEVC):
  1  1  1  1
  1  1 -1 -1
  1 -1 -1  1
  1 -1  1 -1