直接数字合成中的线性插值

Question

我正在使用C语言开发微控制器DDS项目，但在计算线性插值以平滑输出值方面遇到了一些困难。目前程序使用24位累加器的前8位作为8位输出值数组的索引。我需要编写一个函数，它将获取累加器的中间和低位字节，并在数组中“上一个”和“下一个”值之间生成一个值。如果在快速硬件上，这将是非常简单的，但由于我使用的是微控制器，所以我确实需要避免进行任何浮点运算或除法！

在这些限制下，我不确定如何从我的两个8位输入数字和累加器的低2个字节（表示两个输入值之间的“距离”）中获取8位插值值。感谢您提前给予的任何建议！

澄清：

DDS = 直接数字合成

在DDS中，波形是使用查找表从相位累加器生成的。相位累加器通常包含整数部分和小数部分。整数部分用作查找表的索引。在简单的DDS实现中，忽略小数部分，但对于更高质量的输出，小数部分用于在相邻的查找表值之间进行插值（通常只是线性插值）。对于上述问题，我们正在寻找如何有效地执行给定分数f（其中0 <= f <1）的两个查找表值之间的线性插值。

- MattyZ

---

DDS是直接数字合成技术，用于音频/无线电/通信等领域的波形生成。 - Paul R

Answer 1

假设你有一个波形数值的表格（无论是一个象限还是四个象限都可以），那么一种可能的优化方式是存储相邻表格数值之间的增量值。例如，如果你有一个N=256的波形表格LUT[N]，那么你还有一个增量值表格LUT_delta[N]。这两个预计算表格之间的关系是：LUT_delta[i] = LUT[i+1] - LUT[i]。因此，不需要查找两个连续的表格数值LUT[i]和LUT[i+1]，然后将它们相减以得到增量，再进行插值，而是只需查找第一个表格数值LUT[i]和增量LUT_delta[i]，然后计算出插值值。这需要相同数量的表格查找，但需要较少的数学运算。如果你正在使用DSP，应该能够使用单个乘累加指令进行插值，否则在通用CPU上需要进行乘法、缩放和加法。此外，如果你交错存储LUT和LUT_delta值，可能能够通过单个读取来查找LUT[i]和LUT_delta[i]，然后解压缩这两个值。

伪代码：

extract integer LUT index, i, from accumulator // just need a shift for this
extract fractional part of accumulator, f // mask or subtract to get f
get p = LUT[i] // lookup waveform value
get delta = LUT_delta[i] // lookup delta
calculate p_interp = p + p_delta * f // single multiply-accumulate instruction on most DSPs - need scaling on general purpose CPUs

- Paul R

---

我可能没有正确理解你的意思 - 但是使用24位累加器，这意味着我需要为表中每个点之间的2^16增量存储一个增量值吗？如果我有那种空间，我会以更高的分辨率存储表格，并不会费心进行插值！ :) - MattyZ

@Bitrex - 如果您有一个N点表（例如N = 256），那么您只需要第二个N点表来存储差值，其中LUT_delta [i] = LUT [i + 1] - LUT [i]。 - Paul R

啊，我明白了。我认为我有足够的空间放置那么大的桌子！ - MattyZ

@Bitrex：你可能需要先进行基准测试，不使用第二个表格，只有在确实需要时才考虑这种优化。像另一个帖子中所说的那样，使用2的幂次方作为表格大小等。还要注意，delta值需要被标记为有符号数（除非你只是使用单象限表）。 - Paul R

Answer 2

为了进行线性插值而不需要进行除法运算，你应该确保分母是2的幂次方。

value(x) = previous,
value(x+1) = next value(x + dx) = previous + (next - previous) * dx

你的问题是如何计算dx？诀窍在于计算出你的插值索引（累加器的16个低位）使得最大值（dx = 1）是2的幂次方：

value(x + dx) = previous + ((next - previous) * index) / 1024

在这里，您已经计算出了步长值，使得最大步长为1024，对应于dx=1。索引=512是dx = 0.5等等...

- shodanex

---

我明白了，在我的情况下，使用24位累加器并利用前8位作为索引（2^16步长值），所以除法应该是2^16或者右移16位。 - MattyZ

是的，问题在于你必须能够在计算中存储（下一个-上一个）* 2 ^ 16。 - shodanex

Answer 3

如果您想要更好的精度，我建议先检查累加器的低位。例如，如果我们想要4个输出值而不是1个：

Acc += 0x2000;
uint lower_bits = Acc & 0xffff;
int rl = LUT[ Acc >> 16];
int rh = LUT[(Acc >> 16) + 1];
if (lower_bits < 0x4000)
    return rl;
if (lower_bits < 0x8000)
    return (rl * 3 + rh) >> 2;
if (lower_bits < 0xC000)
    return (rl + rh) >> 1;
return (rl + rh * 3) >> 2;

- ruslik

Answer 4

如果你真的需要速度，请查看AVR汇编器。

- Prof. Falken

Answer 5

两个值之间的线性插值，a和b是(a+b)/2。

这在简单硬件中很容易实现，不需要除法或浮点数。

除以2 == 右移一位。

- S.Lott

---

仅插值中点-对于上述问题，您可能需要插值任意一点。 - Paul R

"任意的"? 中点似乎和其他任意点一样。 - S.Lott

@S.Lott：如果您仔细阅读问题，他正在使用相位累加器进行DDS - 相位累加器的小数部分确定了需要插值的两个值之间的点。至于“任意”，我的字典上说：2. 数学中（常数或其他数量）未指定值。 - Paul R

@S.Lott：我认为OP可能错误地假设大多数SO上的人都熟悉DDS和相位累加器。 - Paul R

S.Lott：我认为如果仔细阅读问题，所有必要的信息实际上都已经在其中了，但是如果您有一些关于如何使其更清晰的想法，那么肯定会受到欢迎。 - Paul R