Minimum search length analog to digital converter
The disclosure relates converting an analog input signal to a digital output signal in a number of successive approximation cycles. A sampled analog input signal is received, and a decision node is loaded from a decision tree stored in memory, where each decision node in the decision tree stores an optimal threshold value and an address to one or more next decision nodes. The optimal threshold value, a first output flag and a second output flag associated with a currently loaded decision node is read from the decision tree in the memory, and the sampled first analog input signal is compared with the optimal threshold value and, based on a result of the comparison, a next decision node is loaded from the decision tree stored in memory according to the address associated with the currently loaded decision node or the digital output signal is output.
1. An analog to digital converter (ADC) system for converting an analog input signal into a digital output signal in a number of successive approximation cycles, comprising:
a sample and hold unit configured to sample a first analog signal;
a digital-to-analog converter (DAC) configured to convert a feedback signal to a second analog signal;
a comparator coupled to the sample and hold unit and the DAC, and configured to compare the sampled first analog signal with the second analog signal to generate an indication signal, the indication signal indicating whether a comparison result between the sampled first analog signal and the second analog signal can be determined;
a controller coupled to the DAC and the comparator and accessing decision nodes stored in memory, each decision node storing an optimal threshold value and an address to one or more next decision nodes, the controller configured to:
load a current decision node from the memory and read the optimal threshold value associated with the current decision node; and
compare the sampled first analog input signal with the optimal threshold value and, based on a result of the comparison, load the next decision node according to the address associated with the current decision node from the memory or output the digital output signal; and
a processor configured to:
collect output statistics from the ADC;
calculate a probability for each analog input signal based on the output statistics and generate a decision tree including the decision nodes;
calculate the optimal threshold for each of the decision nodes in the decision tree using the calculated probability of each analog input signal over a search interval, the search interval comprising a lower boundary value and an upper boundary value; and
wherein the decision tree and the associated optimal thresholds are stored in the memory for each of the decision nodes.
2. The ADC of claim 1 , wherein the controller is further configured to:
update the search interval to be between the lower boundary value and the optimal threshold value in response to the result of the comparison indicating that the sampled first analog signal is less than or equal to the optimal threshold value; and
update the search interval to be between the optimal threshold value +1 and the upper boundary value in response to the result of the comparison indicating that the sampled first analog signal is greater than the optimal threshold value.
3. The ADC of claim 1 , wherein the controller is further configured to:
load a first output flag in response to the result of the comparison indicating that the sampled first analog signal is less than or equal to the optimal threshold value;
load a second output flag in response to the result of the comparison indicating that the sampled first analog signal is greater than the optimal threshold value;
output the digital output signal when the first or second output flag in the current decision node is true; and
read an address of the next decision node from memory when the first or second output flag is false, and loading the next decision node at the read address.
4. The ADC of claim 1 , wherein the optimal threshold value for the search interval is determined by the equation:
t
=
arg
min
t
(
∑
k
=
r
t
Pr
k
-
∑
k
=
t
+
1
q
-
1
Pr
k
)
where t is the optimal threshold value, k is a number of analog input signals, Pr is the probability, r is a lower bound of the search interval and q is an upper bound of the search interval.
5. The ADC of claim 1 , wherein the controller comprises a successive approximation register (SAR) and is further configured to:
receive the comparison result from the comparator,
store the comparison result and generate the feedback signal according to the comparison result, and
feed the feedback signal back to the DAC, when the indication signal indicates that the comparison result can be determined.
6. The ADC of claim 1 , wherein the memory stores the decision nodes as a decision tree structure and each of the decision nodes stores the optimal threshold value and one or more addresses such that the one or more addresses are pre-determined addresses and organized in multiple levels, the decision nodes including a root node and for each node at each level, except the lowest level, two child nodes in the immediately lower level, whereby the address of each child node is computable from the address of the respective decision node having that child node.
7. A method for converting an analog input signal to a digital output signal in a number of successive approximation cycles, comprising:
receiving a sampled analog input signal;
loading a decision node from a decision tree stored in memory, each decision node in the decision tree storing an optimal threshold value and an address to one or more next decision nodes;
reading the optimal threshold value, a first output flag and a second output flag associated with a currently loaded decision node in the decision tree from the memory;
comparing the sampled first analog input signal with the optimal threshold value and, based on a result of the comparison, loading a next decision node from the decision tree stored in the memory according to the address associated with the currently loaded decision node or outputting the digital output signal;
sampling a first analog signal at a sample and hold unit and generating the sampled analog input signal;
converting a feedback signal to a second analog signal at a digital-to-analog converter (DAC); and
comparing the sampled analog signal with the second analog signal to generate an indication signal at a comparator communicatively coupled to the sample and hold unit and the DAC, the indication signal indicating whether a comparison result between the sampled analog signal and the second analog signal can be determined.
8. The method of claim 7 , further comprising:
collecting output statistics from the ADC;
calculating a probability for each analog input signal based on the output statistics and generate a decision tree including the decision nodes;
calculating the optimal threshold for each of the decision nodes in the decision tree using the calculated probability of each analog input signal over a search interval, the search interval comprising a lower boundary value and an upper boundary value; and
storing the decision tree and the associated optimal thresholds for each of the decision nodes in the memory.
9. The method of claim 8 , further comprising:
updating the search interval to be between the lower boundary value and the optimal threshold value in response to the result of the comparison indicating that the sampled analog signal is less than or equal to the optimal threshold value; and
updating the search interval to be between the optimal threshold value +1 and the upper boundary value in response to the result of the comparison indicating that the sampled analog signal is greater than the optimal threshold value.
10. The method of claim 7 , further comprising:
loading a first output flag in response to the result of the comparison indicating that the sampled analog signal is less than or equal to the optimal threshold value;
loading a second output flag in response to the result of the comparison indicating that the sampled analog signal is greater than the optimal threshold value;
outputting the digital output signal when the first or second output flag in the currently loaded decision node is true; and
reading an address of the next decision node from the memory of the currently loaded decision node when the first or second output flag is false, and loading the next decision node at the read address.
11. The method of claim 8 , wherein the optimal threshold value for the search interval is determined by the equation:
t
=
arg
min
t
(
∑
k
=
r
t
Pr
k
-
∑
k
=
t
+
1
q
-
1
Pr
k
)
,
where t is the optimal threshold value, k is a number of analog input signals, Pr is the probability, r is a lower bound of the search interval and q is an upper bound of the search interval.
12. The method of claim 7 , further comprising:
receiving the comparison result from the comparator,
storing the comparison result and generating the feedback signal according to the comparison result, and
feeding the feedback signal back to the DAC, when the indication signal indicates that the comparison result can be determined.
13. An analog to digital converter (ADC) for converting an analog input signal into a digital output signal in a number of successive approximation cycles, comprising:
a non-transitory memory storage comprising instructions; and
one or more processors in communication with the memory, wherein the one or more processors execute the instructions to:
receive a sampled analog input signal;
load a decision node from a decision tree stored in memory, each decision node in the decision tree storing an optimal threshold value and an address to one or more next decision nodes;
read the optimal threshold value, a first output flag and a second output flag associated with a currently loaded decision node in the decision tree from the memory; and
compare the sampled first analog input signal with the optimal threshold value and, based on a result of the comparison, load a next decision node from the decision tree stored in memory according to the address associated with the currently loaded decision node or output the digital output signal;
sample a first analog signal at a sample and hold unit and generating the sampled analog input signal;
convert a feedback signal to a second analog signal at a digital-to-analog converter (DAC); and
compare the sampled analog signal with the second analog signal to generate an indication signal at a comparator communicatively coupled to the sample and hold unit and the DAC, the indication signal indicating whether a comparison result between the sampled analog signal and the second analog signal can be determined.
14. The ADC of claim 13 , wherein the one or more processors further execute the instructions to:
collect output statistics from the ADC;
calculate a probability for each analog input signal based on the output statistics and generate a decision tree including the decision nodes;
calculate the optimal threshold for each of the decision nodes in the decision tree using the calculated probability of each analog input signal over a search interval, the search interval comprising a lower boundary value and an upper boundary value; and
wherein, the decision tree and the associated optimal thresholds for each of the decision nodes are stored in the memory.
15. The ADC of claim 14 , wherein the one or more processors further execute the instructions to:
update the search interval to be between the lower boundary value and the optimal threshold value in response to the result of the comparison indicating that the sampled analog signal is less than or equal to the optimal threshold value; and
update the search interval to be between the optimal threshold value +1 and the upper boundary value in response to the result of the comparison indicating that the sampled analog signal is greater than the optimal threshold value.
16. The ADC of claim 13 , wherein the one or more processors further execute the instructions to:
load a first output flag in response to the result of the comparison indicating that the sampled analog signal is less than or equal to the optimal threshold value;
load a second output flag in response to the result of the comparison indicating that the sampled analog signal is greater than the optimal threshold value;
output the digital output signal when the first or second output flag in the currently loaded decision node is true; and
read an address of the next decision node from the memory of the currently loaded decision node when the first or second output flag is false, and loading the next decision node at the read address.
17. The ADC of claim 14 , wherein the optimal threshold value for the search interval is determined by the equation:
t
=
arg
min
t
(
∑
k
=
r
t
Pr
k
-
∑
k
=
t
+
1
q
-
1
Pr
k
)
,
where t is the optimal threshold value, k is a number of analog input signals, Pr is the probability, r is a lower bound of the search interval and q is an upper bound of the search interval.