# SA.py : successive approximation algorithm
# 11/26/2003
# Jiwon Hahn

#N bit A/D conversion of input in range Vmin~Vmin 
def successive_approximation(N, input, Vmin, Vmax, print_flag): 
	A = 0 #analog approximation
	D = range(N) #binrary output storage
	IN = input*1.0/(Vmax-Vmin)*(2**N-1) #scaled input
	OUT = '' #binary output
	count = 0

	if print_flag:
		print 'input: %.2f V in range (%d V ~ %d V)' %(input,Vmin,Vmax)
	for i in range(N-1,-1,-1):
		A += (2**i)
		if A <= IN:
			D[count]='1'
		else:
			A -= (2**i)
			D[count]='0'
		if print_flag:
			print '%d-th approximation: %.3fV' \
				% (count+1, A*(Vmax-Vmin)*1.0/(2**N-1))
		count +=1
	#examine the LSB for accuracy (allow approximation > input)
	if A+1-IN < IN-A: 
		D[N-1] = '1'

	#format binary output	
	for i in range(N): 
		OUT += D[i]
	return OUT

def binary_to_decimal(bin): #for testing
	dec = 0
	bit = len(bin)-1
	for i in range(len(bin)):
		dec += int(bin[i])*(2**bit)
		bit -= 1
	return dec	

#test
if __name__ == '__main__':
	a = successive_approximation(10, 3.14, 0, 5, 1) #hw1 problem 6
	print 'output: ', a
	
	for i in range(1024): #check all approximations of 10-bit values
		b = successive_approximation(10, i, 0, 2**10-1, 0)
		if i!=binary_to_decimal(b): #assert
			print "ERROR: inaccurate approximation of ", i