Binary Search - The SAR ADC's best kept secret

Inside of every successive-approximation-register-analog-to-digital converter (SAR ADC) is a digital-to-analog converter (DAC!) This DAC generates an analog voltage that gets compared to the input signal. By changing the DAC, it is possible to find a digital code that closely matches the input signal.

What is a binary search?

Binary searches have uses outside of the data conversion world. In computer programming, they are used to shorten the time to search through an array. Since we are dealing with bits, a binary search is a simple algorithm to implement in hardware or software, and it is relatively fast. Conceptually the way this works is by continuously dividing the number of comparisons in half. For example, let's consider the vADC's design.

Linear DAC Codes from 0x0 to 0xF. (Notice the relay noise!)

In vADC's design, I'm planning a Vref of 5.00 volts. If the incoming signal is 1.0 volt, how do we search for it? One option would be to start the DAC at 0 volts and compare until we get above 1.0 volts. A significant downside to this approach is that every binary code may have to get tested to find a result. While 1.0 volts would trip the comparator very early, 5.0 volts would require running through the entire range of codes. Binary searches start in the middle and keep halving the comparison.

So if our Vref is 5.0 volts and we have a 4-bit DAC, then binary code 0x8 (b1000) represents 2.5 volts-or half of Vref. When using a binary search we compare Vin to that 2.5 volts and then decide if we need to increase or decrease the DAC's voltage. In the case of a Vin of 1.0 volts, if compared to 2.5 volts, we need to go down. Now the DAC goes half-way between 0 and 2.5 volts, which is going to be 1.25 volts. That's still too high, so now we go on more step down and that is 0.625 volts. Look at that! Now we are too low. so we go back up again until we are closer to 1.0 volts.

On paper, eventually, we can get close enough to 1.0 volts to say we "found" the value. In practice, we're stuck with the resolution of the DAC. Four bits at 5 volts means each individual bit is worth 300 millivolts. That means our closest binary code is going to end up representing 0.9 to 1.2 volts.

How to implement a binary search

Initially, I tried to write the Arduino code exactly like the description above. However, my friends on my live stream chat steered me in a more correct direction. Instead of thinking about the decimal voltages, just think in binary. vADC has a 4-bit DAC. If we start with only the most significant bit (MSB) set to 1, that represents half of the Vref voltage. And then if we look at the next bit to the right, that represents half of the remaining voltage. So the code becomes rather simple:

1. Set the high bit of the DAC.
2. Test the voltage with the comparator
3. The comparator's result becomes that bit.

Let's use two voltages as an example 1.0 and 4.0. Starting with 1.0.

1.00 volt Binary Search Example

DAC Binary Search for 1.00 volts

1. S/H Amplifier samples the input voltage at 1.0 volts.
2. DAC is set to b1000 (0x8), representing 2.50 volts.
3. Comparator result is a LOW because the Input volts is less than the DAC voltage
4. Put a 0 in the DAC code's binary and set the next bit.
5. DAC code becomes 0b0100 (0x4), representing 1.25 volts
6. Comparator result is a LOW because the Input voltage is less than the DAC voltage
7. Put a 0 in the DAC code's binary and set the next bit.
8. DAC Code becomes 0b0010 (0x2), representing 0.63 volts
9. Comparator result is a HIGH because the Input voltage is higher than the DAC voltage
10. Put a 1 in the DAC code's binary (which in this case, stays set.) and set the next bit
11. DAC Code becomes 0b0011(0x3), representing 0.95 volts
12. Comparator result is a HIGH because the Input voltage is higher than the DAC voltage
13. Put a 1 in the DAC code's binary

Take note that steps 2-13 are essentially a loop. The key is moving from left to right (or MSB to LSB ). If a bit results in a voltage that is too high, then there is no reason to test any more codes with that bit set to 1. That behavior is the binary search and means we never have to test more than 4 codes

4.00v Binary Search Example

Here is a scope screenshot of the DAC searching for an input voltage of 4.00 volts. You can see how it starts at 2.5 volts, just like before, but now hunts "up." The second to last code is too far, so it backs down a single bit to get closer to the input voltage.

I should note, to make it easy to trigger the scope and see the start of the search, the register always sets the DAC output to 0 volts as a first step. This step is not part of the binary search. It makes the visualization easier. In a real-world application, there probably isn't a good reason to waste a cycle doing that.

DAC Binary Search for 4.00 volts

vADC Search Code

Here is the code from the current vADC prototype. I do not expect this to change much. It works as expected.

if (start_SAR) {
    double adc_voltage_step = adc_vref / ((pow(2,dac_width)-1.0));
    start_SAR = false;

    // sample Vin
    digitalWrite(sh_enable, HIGH);
    delay(500); digitalWrite(sh_enable, LOW);

    // always start with 0, for loop sets it to 0b1000
    final_countdown = 0;

    // test from MSB to LSB
    for (int x=(dac_width-1); x>=0; x--) {
        bitWrite(final_countdown, x, 1);
        send_data_to_bits(convert_to_bit(final_countdown));
         delay(500); // let slow humans see the "current" value
        bitWrite(final_countdown, x, digitalRead(comparator_result));
     }

     // if last compare results in 0, need to turn off LSB
     send_data_to_bits(convert_to_bit(final_countdown));
    
    // send final value    
    Serial.print("Conversion: "); Serial.print(final_countdown);
    Serial.print(",");
    Serial.print(final_countdown * 0.3);
        Serial.println("V");
}

There are functions in that code, like convert_to_bit() that need to be re-factored. That particular function is a gross-looking switch-statement to enable individual bits' relays and LEDs. (The relay's logic is inverted relative to the LEDs, which uglifies the code.)

For the latest code, check out the vADC Github repository.

The primary benefit of using the binary search is speed. It can fully digitize the input signal in far fewer iterations than if we searched from 0x0 to 0xF. The second benefit is that it is relatively easy to implement in hardware. That benefit might not be fully realized in this project since we are using an Arduino Nano 33 Every. But in writing the code, I tried to demonstrate the effective steps that are occurring and hint at how it could be implemented with basic logic circuits. Perhaps one day, I can tackle that particular challenge.

For now, I need to grab my camera and record a short video.