Technical Award - Partitioning Algorithm

Beginning in the 1980s, infrared airborne reconnaissance was transitioning from film cameras to semiconductor sensors and video imaging. Both technologies required cryogenically cooled imaging elements.  The illustration at right shows the AAD-5 infrared camera system, adjacent to the cryogenic cooling plant, built into an airborne reconnaissance pod.  Together they occupy most of the volume in the pod.

The first video infrared semiconductors were cryogenically cooled, and used a linear array of pixels that were scanned with mirrors to create a 2-dimensional image that could be displayed on a CRT monitor.  These arrays had strict limits on sensitivity and uniformity, characteristics that could influenced by altering the bias current though each pixel individually.

The test and calibration system had multiple bias current source cards, each with 15 input channels, but only 1 current source per card.  One channel per card could be tested at a time, and switching channels required 15 seconds of settling time.  With dozens or hundreds of pixels to test on each device, the time taken for calibration was a significant cost.  My goal was to develop some provably optimal algorithms that could adapt to the pixel arrays as they presented themselves, and choose a different sequence of test currents each time.

The test software started with an initial mid-range current value, resulting in 3 lists: pixels that were within specification, those who were above, and those who were below.  

The set of pixels that were below spec receive another probe current, above the initial value.  Likewise, the set that was above spec receive a lower value.

The process of division continues until the correct setting is discovered for all pixels.

Many people will recognize a binary search embedded in this strategy, but it’s not obvious at first sight what is the object of the search.  It is partly a binary search for the correct bias current, for each pixel, given the opportunities for parallelism and the constraints of physical switching.  It is also a binary division of unfinished pixels into groups requiring similar bias current.

A further refinement reduced the number of measurements by using the error (deviation from spec) at each pixel (or group average) to determine the next test current, rather than simple interval-halving.