Code covered by the BSD License  

Highlights from
Spline based function approximation for HDL synthesis

Spline based function approximation for HDL synthesis

by

 

This is a suite of simple utilities that allow for efficient approximation of complex functions in a

[x,pp]=create_lut3(fcn, rng, tol)
function [x,pp]=create_lut3(fcn, rng, tol)
% this is a function to generate approximation lookup tables using
% elementry operations in hardware. supports EML and VHDL.
%
% Sean Little
% Copyright 2010 The MathWorks, Inc.

% close all
x=rng;
inc=(rng(2)-rng(1))/2;
err=@(s,xx) max(abs(fcn(xx(:))-apply_table2(s,xx)));

pp=[];
initialized=false;

vis_res=10000;
vis_x=linspace(rng(1),rng(2),vis_res);
vis_y=fcn(vis_x);
vis_h=ones(7,1)*-1;% preallocated to a vector of invalid handles

make_movie=false;
num_frames=10;
if make_movie
	close all
	avih=avifile('lut.avi','compression','none');
end

stop_subdivide=false(size(vis_x));

breath_first();

if make_movie
	avih=close(avih);
end

	function breath_first()
		plot_progress();
		while ~initialized || err(pp,vis_x)>tol
			define_breaks();
			
			pp=spline(x,fcn(x));
			plot_progress();
			
			initialized=true;
		end
	end

	function define_breaks()
		% need to guarantee that the end points of the interval are
		% actually breaks in the spline
		inc=inc/2;
		new_x=rng(1) : inc : rng(2);
		
		if initialized
			% basically the goal here is to find areas where more than 2
			% sequential knots are below the error tolerance...these
			% regions do not need to be subdivided...
			
			err_curve=abs(fcn(vis_x(:))-apply_table2(pp,vis_x));
			indx=err_curve<tol;
% 			figure(2),semilogy(vis_x,err_curve,'b',vis_x(indx),err_curve(indx),'rx');
% 			title(sprintf('inc=%.5f',inc))

			[seg,uq]=construct_segment(indx);
			ml=min_length(vis_x(1), vis_x(1)+inc);
			for i=1:length(uq)
				ind=seg==uq(i);
				stop_subdivide(ind)=sum(ind)>ml;
			end
			stop_subdivide = stop_subdivide & indx';
		end
		
		if any(stop_subdivide)
			keep=nearestpoint(vis_x(~stop_subdivide),new_x);
			new_x=union(new_x(keep), x(2:end-1));
		end
		
		x=[rng(1)-inc, new_x, rng(2)+inc];
	end

	function plot_progress()
		if initialized
			% apply_table2 is not robust enough to be called before
			% initialization
			err_curve=abs(fcn(vis_x(:))-apply_table2(pp,vis_x));
			ok=err_curve<tol;
		end
		ttl=@(s,xx,vx,i) sprintf('Number of "knots": %d, Max error: %g, INC: %g',length(xx)-2,err(s,vx),i);
		xx=x(2:end-1);
		if isempty(xx) || ~initialized
			return;
% 			plot(vis_x, vis_y, 'b',...
% 				x([1,end]), fcn(x([1,end])), 'ko');
% 			title('Not yet initalized.');
		elseif ~all(ishandle(vis_h))
			subplot(211)
			vis_h(1:3)=plot(vis_x, vis_y, 'b',...
				xx, fcn(xx), 'rx',...
				x([1,end]), fcn(x([1,end])), 'ko');
			vis_h(4)=title(ttl(pp,x,vis_x,inc));
			subplot(212)
			vis_h(5:6)=semilogy(vis_x(ok), err_curve(ok), 'g.',...
				vis_x(~ok), err_curve(~ok), 'r.');
			vis_h(7)=nline(rng(1),tol,rng(2),tol,'k');
		else
			set(vis_h(2),'xdata',xx,        'ydata',fcn(xx));
			set(vis_h(3),'xdata',x([1,end]),'ydata',fcn(x([1,end])));
			set(vis_h(5),'xdata',vis_x(ok), 'ydata',err_curve(ok));
			set(vis_h(6),'xdata',vis_x(~ok),'ydata',err_curve(~ok));
			set(vis_h(4),'string',ttl(pp,x,vis_x,inc));
			axis(subplot(211),'tight');
		end
		
		if make_movie
			drawnow();
			frm=getframe(gcf);
			for mi=1:num_frames
				avih=addframe(avih, frm);
			end
		else
			pause
		end
	end

	function ind=min_length(x1,x2)
		closest=@(xx) min(abs(vis_x-xx));
		[~,ind1]=closest(x1);
		[~,ind2]=closest(x2);
		ind=ind2-ind1;
	end
end

function [seg,uq]=construct_segment(indx)
[~,duplicate_indx]=adj_unique(indx);
duplicate_indx(~indx)=0;
seg=cumsum(duplicate_indx);
seg(~indx)=0;
uq=unique(seg);
uq(~uq)=[];
end

Contact us