理解定点运算

Question

我正在为如何对不同精度的定点数执行算术而苦恼。我已经阅读了 the paper by R. Yates，但我仍然迷路了。在下文中，我使用 Yates 的符号，其中 A(n,m) 指定具有 n 整数位、m 小数位和 n + m + 1 位的带符号定点格式。

小问题：当[=17=时，A(a,b)*A(c,d)和A(a,b)+A(c,d)究竟是如何执行的？ ] != c 和 b != d?

长问题：在我的 FFT 算法中，我正在生成一个随机信号，其值介于 -10V 和 10V 之间（在) 缩放为 A(15,16)，旋转因子 (tw) 缩放为 A(2,29)。两者都存储为 ints。像这样：

float temp = (((float)rand() / (float)(RAND_MAX)) * (MAX_SIG - MIN_SIG)) + MIN_SIG;
int in_seq[i][j] = (int)(roundf(temp *(1 << numFracBits)));

旋转因子也类似。

现在我需要执行

res = a*tw
问题:
a) 我该如何实现？
b) res 的大小应该是 64 位吗？
c) 因为我知道 a 和 tw 的范围，所以我可以使 'res' A(17,14) 吗？如果是，我是否应该将 a*tw 缩放 2^14 以在 res 中存储正确的值？
a + res
问题:
a)这两个不同Q格式的号码如何相加？
b)如果没有，我该如何操作？

Answer 1

也许举个例子最简单。

假设您要将两个数字相加，一个格式为 A(3, 5)，另一个格式为 A(2, 10).

您可以通过将两个数字转换为 "common" 格式来实现 - 也就是说，它们的小数部分应该具有相同的位数。

一种保守的做法是选择更多的位数。也就是说，将第一个数字向左移动 5 位，将其转换为 A(3, 10)。然后，添加第二个数字。

加法的结果具有较大格式的范围，加上 1 位。在我的示例中，如果您添加 A(3, 10) 和 A(2, 10)，结果的格式为 A(4, 10).

我称此为 "conservative" 方式，因为您不会丢失信息 - 它保证结果可以定点格式表示，而不会丢失精度。但是，在实践中，您会希望对计算结果使用较小的格式。为此，请考虑以下想法：

您可以使用不太准确的格式作为您的常用表示形式。在我的示例中，您可以通过将整数 right 移动 5 位来将 second 数字转换为 A(2, 5)。这会损失精度，通常这种精度损失不会有问题，因为无论如何你都会向它添加一个不太精确的数字。
结果的整数部分可以少使用 1 位。在应用中，经常会出现结果不能太大的情况。在这种情况下，您可以少分配 1 位来表示它。您可能想检查结果是否太大，clamp 到所需范围。

现在，乘法。

可以将两个定点数直接相乘 - 它们可以是任何格式。结果的格式是 "sum of the input formats" - 所有部分相加 - 整数部分加 1。在我的示例中，A(3, 5) 与 A(2, 10) 相乘得到格式为 A(7, 15) 的数字。这是一个保守的规则 - 输出格式能够在不损失精度的情况下存储结果，但在应用程序中，几乎总是你想要降低输出的精度，因为它太许多位。

在您的情况下，所有数字的位数都是 32，您可能希望以所有中间结果都具有 32 位的方式降低精度。

例如，A(17, 14) 乘以 A(2, 29) 得到 A(20, 43) - 需要 64 位。您可能应该从中删除 32 位，然后丢弃其余部分。结果的范围是多少？如果您的旋转因子是一个最大为 4 的数字，则结果可能会受到 2^19 的限制（需要上面的保守数字 20 来适应将 -1 << 31 乘以 -1 << 31 的边缘情况 - 它几乎总是值得拒绝这种边缘情况）。

因此使用 A(19, 12) 作为输出格式，即从输出的小数部分中删除 31 位。

所以，而不是

res = a*tw;

你可能想要

int64_t res_tmp = (int64_t)a * tw;      // A(20, 43)
if (res_tmp == ((int64_t)1 << 62)) // you might want to neglect this edge case
    --res_tmp;                          // A(19, 43)
int32_t res = (int32_t)(res_tmp >> 31); // A(19, 12)

Answer 2

您的问题似乎假设有一种正确的方法可以执行您感兴趣的操作，但您明确询问了一些指导操作执行方式的细节。也许这就是你困惑的核心。

res = a*tw

a表示为A(15,16)，tw表示为A(2,29)，所以它们的乘积自然表示为A(18,45)。您需要更多的值位（与两个因素相加的位数一样多）来保持完全的精度。 A(18,45) 是您应该如何解释将 ints 扩展为 64 位有符号整数类型（例如 int64_t）并计算其乘积的结果。

如果您实际上不需要或不想要 45 位小数，那么您确实可以将其四舍五入为 A(18,13)（或对于任何非负数为 A(18+x,13-x) x) 不改变结果的大小。那确实需要缩放。我可能会这样实现它：

/*
 * Computes a magnitude-preserving fixed-point product of any two signed
 * fixed-point numbers with a combined 31 (or fewer) value bits.  If x
 * is represented as A(s,t) and y is represented as A(u,v),
 * where s + t == u + v == 31, then the representation of the result is
 * A(s + u + 1, t + v - 32).
 */
int32_t fixed_product(int32_t x, int32_t y) {
    int64_t full_product = (int64_t) x * (int64_t) y;
    int32_t truncated = full_product / (1U << 31);
    int round_up = ((uint32_t) full_product) >> 31;

    return truncated + round_up;
}

这避免了几个潜在的问题和有符号整数算法的实现定义特征。它假定您希望结果采用一致的格式（即，仅取决于输入的格式，而不取决于其实际值），而不会溢出。

a + res

如果您不能依赖操作数最初具有相同的比例，加法实际上会有点困难。您需要重新缩放，以便它们匹配，然后才能执行加法。在一般情况下，如果不舍入一些精度，您可能无法做到这一点。

在你的情况下，你从一个 A(15,16) 和一个 A(18,13) 开始。您可以计算 A(19,16) 或更宽（实际上可能是 A(47,16)）的中间结果，它可以保持幅度而不损失任何精度，但是如果您想以 32 位表示，那么您可以做的最好没有改变大小的风险是 A(19,11)。那将是这样的：

int32_t a_plus_res(int32_t a, int32_t res) {
    int64_t res16 = ((int64_t) res) * (1 << 3);
    int64_t sum16 = a + res16;
    int round_up = (((uint32_t) sum16) >> 4) & 1;

    return (int32_t) ((sum16 / (1 << 5)) + round_up);
}

通用版本需要接受操作数表示的比例作为附加参数。这样的事情是有可能的，但是以上就够了。

上述所有假设每个操作数和结果的定点格式是常数。这或多或少是定点的显着特征，一方面将其与浮点格式区分开来，另一方面将其与任意精度格式区分开来。但是，您确实可以选择允许格式变化，并使用每个值的单独变量来跟踪它们。这基本上是定点和任意精度格式的混合体，而且会更混乱。

此外，上述假设必须不惜一切代价避免溢出。也可以将操作数和结果放在一致的范围内；这将使加法更简单，乘法更复杂，并且会带来算术溢出的可能性。如果您有理由相信您的特定数据不太可能发生这种溢出，那么这可能是可以接受的。

理解定点运算

understanding Fixed point arithmetic

c

fixed-point