找到两个最差的值并删除总和
Find two worst values and delete in sum
微控制器负责采样 ADC 值（模数转换）。由于这些部分受到公差和噪声的影响，因此可以通过删除 4 个最差值来显着提高精度。查找和删除确实需要时间，这是不理想的，因为它会增加循环时间。
想象一下 100MHz 的频率，所以软件的每个命令确实需要 10ns 来处理，命令越多，控制器被阻止执行下一组样本的时间就越长
所以我的目标是尽可能快地完成排序过程，我目前使用这段代码，但这只会删除最差的两个！
uint16_t getValue(void){
adcval[8] = {};
uint16_t min = 16383 //14bit full
uint16_t max = 1; //zero is physically almost impossible!
uint32_t sum = 0; //variable for the summing
for(uint8_t i=0; i<8;i++){
if(adc[i] > max) max = adc[i];
if(adc[i] < min) min = adc[i];
sum=sum+adcval[i];
}
uint16_t result = (sum-max-min)/6; //remove two worst and divide by 6
return result;
}
现在我想扩展此功能以删除 8 个样本中的 4 个最差值以获得更高的精度。关于如何做到这一点有什么建议吗？
此外，如果能构建一个高效函数来查找偏差最大的值，而不是最高和最低值，那就太棒了。例如，假设这两个数组
uint16_t adc1[8] {5,6,10,11,11,12,20,22};
uint16_t adc2[8] {5,6,7,7,10,11,15,16};
第一种情况将通过所描述的机制获得精度（删除最差的 4 个）。但是第二种情况会删除值 5 和 6 以及 15 和 16。但这在理论上会使计算更糟，因为删除 10、11、15、16 会更好。有什么快速删除最离谱的4个的方法吗？
鉴于您有一个固定大小的数组，硬编码排序网络应该能够正确地对整个数组进行排序，只需进行 19 次比较。目前您已经进行了 8+2*8=24 次比较，尽管编译器可能展开循环，留下 16 次比较。可以想象，根据微控制器硬件，可以以某种程度的并行性实现排序网络——也许您还必须按顺序查询 adc 值，这样您就有机会在等待比较时对它们进行预排序.
最佳排序网络应该可以在线搜索到。 Wikipedia 有一些指点。
所以，你最终会得到这样的代码：
sort_data(adcval);
return (adcval[2]+adcval[3]+adcval[4]+adcval[5])/4;
更新：
从这张最佳排序网络图片 (source) 中可以看出，一个完整的排序需要 19 次比较。但是，如果您只想提取中间的 4 个值，那么其中 3 个并不是严格需要的。所以你可以进行 16 次比较。
如果您的 ADC 返回 5 到 16 14 位的值，电压参考为 3.3V，则电压在 1mV 到 3mV 之间变化。它很可能是正确的读数。 14位ADC很难设计好的输入电路。
不如运行运行宁平均。 运行ning 平均值是多少？它是软件低通滤波器。
蓝色是来自 ADC 的读数，红色是 -运行ning 平均值
第二个信号是非常低幅度的正弦波（9-27mV - 假设 14 位和 3.3Vref）
算法：
static int average;
int running_average(int val, int level)
{
average -= average / level;
average += val * level;
return average / level;
}
void init_average(int val, int level)
{
average = val * level;
}
如果level是2的幂。这个版本只需要6条指令（没有分支）来计算平均值。
static int average;
int running_average(int val, int level)
{
average -= average >> level;
average += val << level;
return average >> level;
}
void init_average(int val, int level)
{
average = val << level;
}
我假设平均值不会溢出。如果是你需要选择更大的类型
to delete the 4 worst values out of the 8 samples
方法在geeksforgeeks k largest(or smallest) elements in an array中有描述，您可以实施最适合您的方法。
我决定使用 this good site 生成最佳排序算法，其中 SWAP() 宏需要对 8 个元素的数组进行排序。然后我创建了一个小的 C 程序，它将在我的排序函数上测试 8 元素数组的任意组合。然后，因为我们只关心 4 个元素的组，所以我做了一些蛮力 - 对于每个 SWAP() 宏，我试图注释宏并查看程序是否仍然成功。我可以评论 5 SWAP 宏，留下 14 次比较来识别 8 个样本数组中最小的 4 个元素。
/**
* Sorts the array, but only so that groups of 4 matter.
* So group of 4 smallest elements and 4 biggest elements
* will be sorted ok.
* s[0]...s[3] will have lowest 4 elements
* so they have to be "deleted"
* s[4]...s[7] will have the highest 4 values
*/
void sort_but_4_matter(int s[8]) {
#define SWAP(x, y) do { \
if (s[x] > s[y]) { \
const int t = s[x]; \
s[x] = s[y]; \
s[y] = t; \
} \
} while(0)
SWAP(0, 1);
//SWAP(2, 3);
SWAP(0, 2);
//SWAP(1, 3);
//SWAP(1, 2);
SWAP(4, 5);
SWAP(6, 7);
SWAP(4, 6);
SWAP(5, 7);
//SWAP(5, 6);
SWAP(0, 4);
SWAP(1, 5);
SWAP(1, 4);
SWAP(2, 6);
SWAP(3, 7);
//SWAP(3, 6);
SWAP(2, 4);
SWAP(3, 5);
SWAP(3, 4);
#undef SWAP
}
/* -------- testing code */
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
int cmp_int(const void *a, const void *b) {
return *(const int*)a - *(const int*)b;
}
void printit_arr(const int *arr, size_t n) {
printf("{");
for (size_t i = 0; i < n; ++i) {
printf("%d", arr[i]);
if (i != n - 1) {
printf(" ");
}
}
printf("}");
}
void printit(const char *pre, const int arr[8],
const int in[8], const int res[4]) {
printf("%s: ", pre);
printit_arr(arr, 8);
printf(" ");
printit_arr(in, 8);
printf(" ");
printit_arr(res, 4);
printf("\n");
}
int err = 0;
void test(const int arr[8], const int res[4]) {
int in[8];
memcpy(in, arr, sizeof(int) * 8);
sort_but_4_matter(in);
// sort for memcmp below
qsort(in, 4, sizeof(int), cmp_int);
if (memcmp(in, res, sizeof(int) * 4) != 0) {
printit("T", arr, in, res);
err = 1;
}
}
void test_all_combinations() {
const int result[4] = { 0, 1, 2, 3 }; // sorted
const size_t n = 8;
int num[8] = { 0, 1, 2, 3, 4, 5, 6, 7 };
for (size_t j = 0; j < n; j++) {
for (size_t i = 0; i < n-1; i++) {
int temp = num[i];
num[i] = num[i+1];
num[i+1] = temp;
test(num, result);
}
}
}
int main() {
test_all_combinations();
return err;
}
Tested on godbolt。在 x86_64 上使用 gcc -O2 的 sort_but_4_matter 编译为少于 100 条指令。
这个答案有点话题性，因为它推荐了一种硬件解决方案，但如果需要性能并且 MCU 无法实施 P__J__ 的解决方案，那么这是您的下一个最佳选择。
您似乎想消除输入信号中的噪音。这可以使用 DSP (digital signal processing) 在软件中完成，但 也可以通过不同的硬件配置来完成。
通过在 ADC 之前适当的 space 添加适当的滤波器，可以从 ADC 输出中去除很多（外部）噪声。 （你当然不能低于 ADC 固有的一定量，但是唉。）
electronics.stackexchange.com 上有几个问答。
- 一种解决方案是添加一个电容器来过滤一些高频噪声。正如 DerStorm8
所述
- The Photon has another great solution here 通过建议 RC、Sallen-Key 和级联 Sallen-Key 滤波器作为连续信号滤波器。
Here (ADN007) 是 Microchip 在 "Techniques that Reduce System Noise in ADC Circuits"
上的模拟设计说明
It may seem that designing a low noise, 12-bit Analog-to-Digital
Converter (ADC) board or even a 10-bit board is easy. This is
true, unless one ignores the basics of low noise design. For
instance, one would think that most amplifiers and resistors work
effectively in 12-bit or 10-bit environments. However, poor device
selection becomes a major factor in the success or failure of the
circuit. Another, often ignored, area that contributes a great deal
of noise, is conducted noise. Conducted noise is already in the
circuit board by the time the signal arrives at the input of the
ADC. The most effective way to remove this noise is by using a
low-pass (anti-aliasing) filter prior to the ADC. Including by-pass
capacitors and using a ground plane will also eliminate this type
of noise. A third source of noise is radiated noise. The major
sources of this type of noise are Electromagnetic Interference
(EMI) or capacitive coupling of signals from trace-to-trace.
If all three of these issues are addressed, then it is true that
designing a low noise 12-bit ADC board is easy.
以及他们推荐的解决路径：
It is easy to design a true 12-bit ADC system by using a few
key low noise guidelines. First, examine your devices (resistors
and amplifiers) to make sure they are low noise. Second, use a
ground plane whenever possible. Third, include a low-pass filter
in the signal path if you are changing the signal from analog to
digital. Finally, and always, include by-pass capacitors. These
capacitors not only remove noise but also foster circuit stability.
Here 是 Analog Devices 关于输入噪声的一篇好论文。他们在这里注意到 "there are some instances where input noise can actually be helpful in achieving higher resolution."
All analog-to-digital converters (ADCs) have a certain amount of input-referred noise—modeled as a noise source connected in series with the input of a noise-free ADC. Input-referred noise is not to be confused with quantization noise, which is only of interest when an ADC is processing time-varying signals. In most cases, less input noise is better; however, there are some instances where input noise can actually be helpful in achieving higher resolution. If this doesn’t seem to make sense right now, read on to find out how some noise can be good noise.
微控制器负责采样 ADC 值（模数转换）。由于这些部分受到公差和噪声的影响，因此可以通过删除 4 个最差值来显着提高精度。查找和删除确实需要时间，这是不理想的，因为它会增加循环时间。
想象一下 100MHz 的频率，所以软件的每个命令确实需要 10ns 来处理，命令越多，控制器被阻止执行下一组样本的时间就越长
所以我的目标是尽可能快地完成排序过程，我目前使用这段代码，但这只会删除最差的两个！
uint16_t getValue(void){
adcval[8] = {};
uint16_t min = 16383 //14bit full
uint16_t max = 1; //zero is physically almost impossible!
uint32_t sum = 0; //variable for the summing
for(uint8_t i=0; i<8;i++){
if(adc[i] > max) max = adc[i];
if(adc[i] < min) min = adc[i];
sum=sum+adcval[i];
}
uint16_t result = (sum-max-min)/6; //remove two worst and divide by 6
return result;
}
现在我想扩展此功能以删除 8 个样本中的 4 个最差值以获得更高的精度。关于如何做到这一点有什么建议吗？
此外，如果能构建一个高效函数来查找偏差最大的值，而不是最高和最低值，那就太棒了。例如，假设这两个数组
uint16_t adc1[8] {5,6,10,11,11,12,20,22};
uint16_t adc2[8] {5,6,7,7,10,11,15,16};
第一种情况将通过所描述的机制获得精度（删除最差的 4 个）。但是第二种情况会删除值 5 和 6 以及 15 和 16。但这在理论上会使计算更糟，因为删除 10、11、15、16 会更好。有什么快速删除最离谱的4个的方法吗？
鉴于您有一个固定大小的数组，硬编码排序网络应该能够正确地对整个数组进行排序，只需进行 19 次比较。目前您已经进行了 8+2*8=24 次比较，尽管编译器可能展开循环，留下 16 次比较。可以想象，根据微控制器硬件，可以以某种程度的并行性实现排序网络——也许您还必须按顺序查询 adc 值，这样您就有机会在等待比较时对它们进行预排序.
最佳排序网络应该可以在线搜索到。 Wikipedia 有一些指点。
所以，你最终会得到这样的代码：
sort_data(adcval);
return (adcval[2]+adcval[3]+adcval[4]+adcval[5])/4;
更新：
从这张最佳排序网络图片 (source) 中可以看出，一个完整的排序需要 19 次比较。但是，如果您只想提取中间的 4 个值，那么其中 3 个并不是严格需要的。所以你可以进行 16 次比较。
如果您的 ADC 返回 5 到 16 14 位的值，电压参考为 3.3V，则电压在 1mV 到 3mV 之间变化。它很可能是正确的读数。 14位ADC很难设计好的输入电路。
不如运行运行宁平均。 运行ning 平均值是多少？它是软件低通滤波器。
第二个信号是非常低幅度的正弦波（9-27mV - 假设 14 位和 3.3Vref）
算法：
static int average;
int running_average(int val, int level)
{
average -= average / level;
average += val * level;
return average / level;
}
void init_average(int val, int level)
{
average = val * level;
}
如果level是2的幂。这个版本只需要6条指令（没有分支）来计算平均值。
static int average;
int running_average(int val, int level)
{
average -= average >> level;
average += val << level;
return average >> level;
}
void init_average(int val, int level)
{
average = val << level;
}
我假设平均值不会溢出。如果是你需要选择更大的类型
to delete the 4 worst values out of the 8 samples
方法在geeksforgeeks k largest(or smallest) elements in an array中有描述，您可以实施最适合您的方法。
我决定使用 this good site 生成最佳排序算法，其中 SWAP() 宏需要对 8 个元素的数组进行排序。然后我创建了一个小的 C 程序，它将在我的排序函数上测试 8 元素数组的任意组合。然后，因为我们只关心 4 个元素的组，所以我做了一些蛮力 - 对于每个 SWAP() 宏，我试图注释宏并查看程序是否仍然成功。我可以评论 5 SWAP 宏，留下 14 次比较来识别 8 个样本数组中最小的 4 个元素。
/**
* Sorts the array, but only so that groups of 4 matter.
* So group of 4 smallest elements and 4 biggest elements
* will be sorted ok.
* s[0]...s[3] will have lowest 4 elements
* so they have to be "deleted"
* s[4]...s[7] will have the highest 4 values
*/
void sort_but_4_matter(int s[8]) {
#define SWAP(x, y) do { \
if (s[x] > s[y]) { \
const int t = s[x]; \
s[x] = s[y]; \
s[y] = t; \
} \
} while(0)
SWAP(0, 1);
//SWAP(2, 3);
SWAP(0, 2);
//SWAP(1, 3);
//SWAP(1, 2);
SWAP(4, 5);
SWAP(6, 7);
SWAP(4, 6);
SWAP(5, 7);
//SWAP(5, 6);
SWAP(0, 4);
SWAP(1, 5);
SWAP(1, 4);
SWAP(2, 6);
SWAP(3, 7);
//SWAP(3, 6);
SWAP(2, 4);
SWAP(3, 5);
SWAP(3, 4);
#undef SWAP
}
/* -------- testing code */
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
int cmp_int(const void *a, const void *b) {
return *(const int*)a - *(const int*)b;
}
void printit_arr(const int *arr, size_t n) {
printf("{");
for (size_t i = 0; i < n; ++i) {
printf("%d", arr[i]);
if (i != n - 1) {
printf(" ");
}
}
printf("}");
}
void printit(const char *pre, const int arr[8],
const int in[8], const int res[4]) {
printf("%s: ", pre);
printit_arr(arr, 8);
printf(" ");
printit_arr(in, 8);
printf(" ");
printit_arr(res, 4);
printf("\n");
}
int err = 0;
void test(const int arr[8], const int res[4]) {
int in[8];
memcpy(in, arr, sizeof(int) * 8);
sort_but_4_matter(in);
// sort for memcmp below
qsort(in, 4, sizeof(int), cmp_int);
if (memcmp(in, res, sizeof(int) * 4) != 0) {
printit("T", arr, in, res);
err = 1;
}
}
void test_all_combinations() {
const int result[4] = { 0, 1, 2, 3 }; // sorted
const size_t n = 8;
int num[8] = { 0, 1, 2, 3, 4, 5, 6, 7 };
for (size_t j = 0; j < n; j++) {
for (size_t i = 0; i < n-1; i++) {
int temp = num[i];
num[i] = num[i+1];
num[i+1] = temp;
test(num, result);
}
}
}
int main() {
test_all_combinations();
return err;
}
Tested on godbolt。在 x86_64 上使用 gcc -O2 的 sort_but_4_matter 编译为少于 100 条指令。
这个答案有点话题性，因为它推荐了一种硬件解决方案，但如果需要性能并且 MCU 无法实施 P__J__ 的解决方案，那么这是您的下一个最佳选择。
您似乎想消除输入信号中的噪音。这可以使用 DSP (digital signal processing) 在软件中完成，但 也可以通过不同的硬件配置来完成。
通过在 ADC 之前适当的 space 添加适当的滤波器，可以从 ADC 输出中去除很多（外部）噪声。 （你当然不能低于 ADC 固有的一定量，但是唉。）
electronics.stackexchange.com 上有几个问答。
- 一种解决方案是添加一个电容器来过滤一些高频噪声。正如 DerStorm8 所述
- The Photon has another great solution here 通过建议 RC、Sallen-Key 和级联 Sallen-Key 滤波器作为连续信号滤波器。
Here (ADN007) 是 Microchip 在 "Techniques that Reduce System Noise in ADC Circuits"
上的模拟设计说明It may seem that designing a low noise, 12-bit Analog-to-Digital Converter (ADC) board or even a 10-bit board is easy. This is true, unless one ignores the basics of low noise design. For instance, one would think that most amplifiers and resistors work effectively in 12-bit or 10-bit environments. However, poor device selection becomes a major factor in the success or failure of the circuit. Another, often ignored, area that contributes a great deal of noise, is conducted noise. Conducted noise is already in the circuit board by the time the signal arrives at the input of the ADC. The most effective way to remove this noise is by using a low-pass (anti-aliasing) filter prior to the ADC. Including by-pass capacitors and using a ground plane will also eliminate this type of noise. A third source of noise is radiated noise. The major sources of this type of noise are Electromagnetic Interference (EMI) or capacitive coupling of signals from trace-to-trace. If all three of these issues are addressed, then it is true that designing a low noise 12-bit ADC board is easy.
以及他们推荐的解决路径：
It is easy to design a true 12-bit ADC system by using a few key low noise guidelines. First, examine your devices (resistors and amplifiers) to make sure they are low noise. Second, use a ground plane whenever possible. Third, include a low-pass filter in the signal path if you are changing the signal from analog to digital. Finally, and always, include by-pass capacitors. These capacitors not only remove noise but also foster circuit stability.
Here 是 Analog Devices 关于输入噪声的一篇好论文。他们在这里注意到 "there are some instances where input noise can actually be helpful in achieving higher resolution."
All analog-to-digital converters (ADCs) have a certain amount of input-referred noise—modeled as a noise source connected in series with the input of a noise-free ADC. Input-referred noise is not to be confused with quantization noise, which is only of interest when an ADC is processing time-varying signals. In most cases, less input noise is better; however, there are some instances where input noise can actually be helpful in achieving higher resolution. If this doesn’t seem to make sense right now, read on to find out how some noise can be good noise.