A Signal Processing Toolkit 6 898 Final Project Jay B Hancock Abstract I implement a signal processing toolkit in Ocaml to take advantage of type checking Processors implement a mapping between input and output Signals store values between processors and at inputs and outputs to the system A system graph is built via the interconnection of processor nodes and signal edges Causal assumptions plus an ordered production of output points from processors allow us to insure that the system will operate properly The system is tested in an IIR recursive filter definition Background and Motivation Digital Signal Processing uses a mathematical entity called a signal which is a function that maps the integers to an abstract data type and operations on signals such as convolve add delay and fast fourier transform A system is a directed graph of operation nodes and signal edges with one node as the input and another node as the output The main book of influence for such a system is 1 In a real time application we want to stream data through a sequence of processors Some processors have different signal input vs output rates which indicates that some signals will require greater storage than others There are two possibile design choices for building systems The first is to take advantage of currying the processor functions which would allow signal edges between processor nodes to disappear The second is to define an output signal for each processor node so that all processors are connected by signals The latter may be more inefficient but it is closer to the model of a signal flow graph used in DSP courses thus I chose it To be efficient we would rather have a push model instead of a pull model If we use a pull model then the processor would waste cycles polling the signal to see if its value has been defined For the push model we shall consider the observer design pattern Then the signal is a subject to be observed by processors When the signal s state changes it notifies its processor observers so that they may attempt to generate their next output values Since real time data is causal we impose three conditions First that any signal point for n 0 equals 0 We note one exception to this rule and that will be when we are generating a mathematical signal such as exp jx Second ly that all processors will produce outputs successively i e the first output point we produce will be at n 0 and given that we just produced an output at point n N then the next point we must produce is n N 1 Third that all processors must operate causally i e when a processor produces an output point at time n N then it must only rely on input values for times n N Using this policy signals generated as outputs of processors will not accidentally skip generating a value and leave the system stuck Also the total delay to the system will be the minimum sum delay through each non feedback paths from input to output As a practical matter processors input points must have a finite delay from the output point so infinite values cannot be used which may otherwise cause the processor to wait forever We want to assure correct operation of the system Given the above properties if all inputs are defined starting at n 0 and successively then all output points will be eventually defined We want to check that this will ensure proper operation in all cases including those with feedback loops I will simply assert that this is the case for our purposes in this paper As a practical matter signals have finite memory capacity even if they have infinite domain It is necessary to purge the signal s memory of values that are no longer needed We can determine these values a priori because processors have finite delays The memory requirement of a signal is proportional to the memory requirement the processor For instance y1 n x n where y is the output and x is the input requires one point of memory while y2 n x n 1 x n 2 requires two memory points Because we are generating point successively y3 n x n x n M requires M memory points The locking function is therefore a function that maps n to an interval of the domain For the three cases above the locking function is l1 m m m n l2 m m m n 2 and l3 m m m n M Since signals are causal all normal locking functions will take the form of l3 m where M is dependent on the processor There may be unforeseen cases where the locking function will not take this form One such example is if we want to debug a system we can set the locking function to All so that no points will be thrown away A signal can have several observers The locking mechanism must account for several locking functions on a signal Since the observers will change their locking function independently of each other we must store each observer s function separately and take the union of them to determine the total locked region Purging the signal is necessary for memory management A purge operation simply compares defined points in the signal with the locking function and deletes the points that are not locked There are two possible techniques for purging the signal One is to purge a particular signal each time the locking function is updated The purge operation could be expensive so a second improved technique is to purge all signals when memory usage reaches a certain size Despite expense I chose the first technique A simple mechanism will simply recheck all points against the lock while a more complicated mechanism could identify the points that were just unlocked and only compare those If points in the signal data structure are stored successively and all locking functions are GreaterThanEqual then the points can be checked and purged in order from the beginning of the storage until the first locked point In a real system if the purge command checks all points in the data structure it could have an overhead as high as the number of memory points which is M from y3 above This may not be deterministic if the processor relies on a stream with random delays Care must be taken during initialization because multiple observers can be added to the signal Initialization must set the lock but no t cause a purge command If it were to purge the signal then one processor may start observing a signal and erase it before a second processor is attached to observe the same data that was just erased After initialization of the system it may be run by defining data on the input stream s of the system Once the system is run there are no guarantees about