# 3.1 概述

​ CORDIC(坐标旋转数字算法)是一种计算三角、双曲和其他数学函数的有效方法。它是一种数字算法，每次运算均产生一次结果输出。这使我们能够根据应用需求调整算法精度；增加运算迭代次数可以得到更精确的结果。运算精度与运算性能和占用资源并列，是一种通用的设计评估指标。CORDIC是只使用加法、减法、移位和查找表实现的简单算法，这种算法在FPGA中实现效率高，在硬件算法实现中经常用到。
CORDIC算法是1950年由Jack Volder发明，它最开始是作为数字解决方案替代模拟方案应用于B-58轰炸机实时导航上，它的功能是计算旋转角度。在那个时代用硬件实现乘法的成本是相当高的，同时CPUs的计算能力也非常有限。因此这个算法需要有低的运算复杂度和使用简单的运算操作。多年之后，它被应用于数学协处理器、线性系统、雷达信号处理、傅立叶变换和其它数字信号处理算法中。现在，它广泛应用于FPGA设计中。Vivado HLS用CODIC进行三角函数计算，同时CORDIC也是现代FPGA IP CORE库中的标准运算模块。
​ 本章目标是演示如何使用高级语言创建优化CORDIC算法。随着本书的深入，我们研究设计的硬核复杂性也在逐渐增加。CORDIC算法是一种迭代算法；因此，大多数计算都在一个for循环中执行。代码本身并不复杂，但是用来创建最优硬件实现结构是需要设计人员对代码有深入理解的。一个优秀的HLS设计人员如果希望创建最优设计，就必须理解算法。因此，我们在本章前部分给出了CORDIC算法的数学和计算背景。

​ 我们在本章强调的HLS主要优化方式是为变量选择正确的数据表示。正如我们在本章后面所讨论的，设计人员必须仔细权衡运算结果精度、性能和设计的资源利用率。数据表示是这种权衡的一个重要因素—“较大”数字（那些大位宽数据)，通常是以增加使用资源(更多的寄存器和逻辑块)和降低处理性能为代价来提供更精确数据。我们将在第3.5.5节中提供了关于数据表示和任意精度数据类型的背景。
​ 本章与工程应用相结合，针对运算精度(计算的准确性)、资源占用和处理性能的权衡进行了更深入的实验。本章目的是提供足够的知识经验，以便人们可以在这个项目中进行练习，例如，这一章和那个工程是相互补充的。那个工程的目标是建立一个相位探测器，它使用了一个CORDIC和一个复数匹配滤波器，这个滤波器我们在前一章中已经介绍过它了。

# 3.2 背景

​ CORDIC核心思想是在一个二维平面上高效地执行一组矢量旋转。在这些旋转运算的基础上增加一些简单控制，我们就可以实现各种基础操作，例如，三角函数，双曲函数，对数函数，实乘和复乘，以及矩阵分解和因式分解。CORDIC已经广泛应用于信号处理、机器人技术、通信和许多科学计算领域。由于CORDIC占用资源少，所以常用在FPGA设计中。
​ 在下文中，我们将介绍CORDIC如何执行给定输入角θ的正弦和余弦的过程。这是使用一系列矢量旋转来完成的，这些简单的操作在硬件中使用非常有效。在高层次，算法使用一系列旋转来工作，目标是达到目标输入角θ。实现这种效率的关键创新是旋转可以以需要最少计算的方式完成。尤其我们使用乘以2的常数幂来执行旋转。这意味着简单地在硬件中移动位是非常有效的，因为它不需要任何逻辑。
​ 图3.1提供了用于计算cosφ和sinφ的CORDIC程序的高级概述。在这种情况下，我们在x轴上开始初始旋转矢量，即0°角。然后，我们执行一系列迭代旋转;在这个例子中，我们只执行四次旋转，但通常这是40次旋转。每个后续旋转使用越来越小的角度，这意味着每次迭代都会为输出值增加更多精度。在每次迭代中，我们决定以较小的角度进行正向或负向旋转。我们旋转的角度值是先验固定的;因此，我们可以轻松地将它们的值存储在一个小内存中，并保持我们到目前为止已经旋转的累积角度的运行总和。如果该累积角度大于我们的目标角度φ，则我们执行负旋转。如果它更小，那么旋转就是正的。一旦我们完成了足够数量的旋转，我们就可以通过直接读取最终旋转矢量的x和y值来确定cosφ和sinφ。如果我们的最终向量的幅度为1，则x =cosφ且y =sinφ。

CORDIC算法的基本目标是以有效的方式执行一系列旋转。 让我们首先考虑如何进行旋转。 在二维中，旋转矩阵是：
$R(\theta) = \begin{bmatrix} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{bmatrix} \quad(3.1)$
CORDIC使用迭代算法将矢量v旋转到某个角度目标，这取决于CORDIC正在执行的功能。 一次旋转是
$v_{i} = R_{i} * v_{i-1}$

$\begin{bmatrix} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{bmatrix}\begin{bmatrix} x_{i-1} \\ y_{i-1} \end{bmatrix} = \begin{bmatrix} x_i \\ y_i \end{bmatrix} \quad(3.2)$

$x_i = x_{i-1} \cos \theta - y_{i-1} \sin \theta \quad(3.3)$
$y_i = x_{i-1} \sin \theta + y_{i-1} \cos \theta \quad(3.4)$

$R(90^\circ) = \begin{bmatrix} \cos 90^\circ & -\sin 90^\circ \\ \sin 90^\circ & \cos 90^\circ \end{bmatrix} = \begin{bmatrix} 0 & -1 \\ 1 & 0 \end{bmatrix} \quad(3.5)$

\begin{aligned} x_i &= x_{i-1} \cos 90^\circ - y_{i-1} \sin 90^\circ \\ &= x_{i-1} \cdot 0 - y_{i-1} \cdot 1 \\ &= -y_{i-1} \end{aligned} \quad(3.6)
\begin{aligned} y_i &= x_{i-1} \sin 90^\circ + y_{i-1} \cos 90^\circ \\ &= x_{i-1} \cdot 1 + y_{i-1} \cdot 0 \\ &= x_{i-1} \end{aligned} \quad(3.7)

$\begin{bmatrix} 0 & -1 \\ 1 & 0 \\ \end{bmatrix}\begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} -y \\ x \end{bmatrix} \quad(3.8)$

$R(45^\circ) = \begin{bmatrix} \cos 45^\circ & -\sin 45^\circ \\ \sin 45^\circ & \cos 45^\circ \end{bmatrix} = \begin{bmatrix} \sqrt 2/2 & -\sqrt 2/2 \\ \sqrt 2/2 & \sqrt 2/2 \end{bmatrix} \quad(3.9)$

$x_i = x_{i-1} \cos 45^\circ - y_{i-1} \sin 45^\circ = x_{i-1} \cdot \sqrt 2/2 - y_{i-1} \cdot \sqrt 2/2 \quad(3.10)$
$y_i = x_{i-1} \sin 45^\circ + y_{i-1} \cos 45^\circ= x_{i-1} \cdot \sqrt 2/2 + y_{i-1} \cdot \sqrt 2/2 \quad(3.11)$

$\begin{bmatrix} \sqrt 2/2 & -\sqrt 2/2 \\ \sqrt 2/2 & \sqrt 2/2 \\ \end{bmatrix} \begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} \sqrt 2/2 x - \sqrt 2/2 y \\ \sqrt 2/2 x + \sqrt 2/2 y \\ \end{bmatrix} \quad(3.12)$

$R() = \begin{bmatrix} 1 & -1 \\ 1 & 1 \\ \end{bmatrix} \quad(3.13)$

$x_i = x_{i-1} - y_{i-1}\quad(3.14)$
$y_i = x_{i-1} + y_{i-1}\quad(3.15)$
​用矩阵向量的形式表示
$\begin{bmatrix}1 & -1 \\ 1 & 1 \end{bmatrix}\begin{bmatrix}x \\ y \end{bmatrix}= \begin{bmatrix}x - y \\x + y \end{bmatrix} \quad(3.16)$
​ 这个很容易计算，而且不需要任何“困难”的乘法。但这次运算结果是什么呢?结果证明这次运算实现了完美的45度旋转；现在，我们得到了一个高效方式来实现一次45度旋转。但是，这个变换也把矢量以
$\sqrt{2}$

$\sqrt{2}$

​ 现在我们介绍高效矩阵旋转概念，即，只进行加/减和2的幂次乘法运算(即移位操作)。再考虑旋转矩阵
$R_{i}(\theta) = \begin{bmatrix} \cos(\theta_{i}) & -\sin(\theta_{i}) \\\sin(\theta_{i}) & \cos(\theta_{i})\end{bmatrix}\quad(3.17)$

$\cos(\theta_{i}) = {\frac{1}{\sqrt{1 + \tan^2(\theta_{i})}}} \quad(3.18)$
$\sin(\theta_{i}) = \frac{\tan(\theta_{i})}{\sqrt{1 +\tan^2(\theta_{i})}} \quad(3.19)$

$R_i = \frac{1}{\sqrt{1 + \tan^2(\theta_i)}} \begin{bmatrix} 1 & - \tan(\theta_i) \\ \tan(\theta_i) & 1 \end{bmatrix} \quad(3.20)$
​ 如果我们限制
$tan(\theta_i)$

$tan(\theta_i)= 2^{-i}$
。旋转矩阵就变成了
$v_i = K_i \begin{bmatrix} 1 & - 2^{-i} \\ 2^{-i} & 1 \end{bmatrix}\begin{bmatrix} x_{i-1} \\ y_{i-1} \end{bmatrix} \quad(3.21)$

$K_i = \frac{1}{\sqrt{1 + 2^{-2i}}} \quad(3.22)$

$2^{-i}$

$tan(\theta_i)= 2^{-i}$
。后续我们将证明这不是什么严重问题。第二，我们只展示了一个方向的旋转；而CORDIC要求能够旋转
$\pm\theta$
。这个可以通过添加σ值（1或−1）来表示正向或者逆向旋转来修正这个错误。我们可能在每次迭代/旋转中有不同的
$\sigma_i$
。因此旋转操作可概括为
$v_i = K_i \begin{bmatrix} 1 & -\sigma_i 2^{-i} \\ \sigma_i 2^{-i} &1 \end{bmatrix} \begin{bmatrix} x_{i-1} \\ y_{i-1} \end{bmatrix} \quad(3.23)$

$k_i$
，在迭代过程中
$k_i$

$K(n) = \prod_{i=0}^{n-1} K_i = \prod_{i=0}^{n-1}\frac {1}{\sqrt{1 + 2^{-2i}}} \quad(3.24)$
$K = \lim_{n \to \infty}K(n) \approx 0.6072529350088812561694 \quad(3.25)$
​ 不同迭代的比例因子可以预先计算并存储。如果我们总是做固定次数的旋转，这个比例因子就是一个常数。这种修正也可以在旋转之前适当地缩放
$v_o$

$A = \frac{1}{K} = \lim_{n \to \infty} \prod_{i=0}^{n-1} {\sqrt{1 +2^{-2i}}}\approx 1.64676025812107 \quad(3.26)$

$\theta_i$
。其中
$\theta_i =arctan2^{-i}$
。我们可以提前计算每一个i对应的
$\theta_i$

​ 表3.1提供了CORDIC前7次迭代的统计信息。第一行是“零”旋转(即 i = 0),这是一次 45度旋转。它的比例因子为1.41421。第二行旋转因子为
$2^{-1} = 0.5$
。这个结果的旋转角度为
$\theta=arctan(2^{-1}) = 26.565^\circ$
,这个旋转的比例因子为1.11803。CORDIC增益是所有比例因子的积。在这个例子中，它的比例因子是前两个比例因子之积，即，1.58114 = 1.41421*1.11803。这个过程i的数值在增加，而旋转角度和比例因子越来越小。值得注意的是CORDIC比例因子最终趋于稳定≈1.64676025812107 数值正如公式3.26。另外，请注意，当旋转角度变小时，它们对数据精度的影响也逐步减弱。

​ 表3.1:CORDIC前7次迭代的旋转角度、比例因子和CORDIC增益。注意，角度每次迭代大约减小一半。比例因子表示在旋转过程中旋转矢量增加的长度。CORDIC增益是所有旋转矢量比例因子的累积，例如，某一次迭代的CORDIC增益是本次迭代和与该次迭代之前所有比例因子累积。
i
$2^{-i}$
Rotating Angle
Scaling Factor
CORDIC Gain
0
1.0
$45.000^\circ$
1.41421
1.41421
1
0.5
$26.565^{\circ}$
1.11803
1.58114
2
0.25
$14.036^{\circ}$
1.03078
1.62980
3
0.125
$7.125^{\circ}$
1.00778
1.64248
4
0.0625
$3.576^{\circ}$
1.00195
1.64569
5
0.03125
$1.790^{\circ}$
1.00049
1.64649
6
0.015625
$0.895^{\circ}$
1.00012
1.64669

# 3.3 计算正弦和余弦

​ 现在我们可以更精确地使用CORDIC计算一些给定角θ的正弦和余弦值。为了计算正弦和余弦值，我们从x轴正方向上的一个矢量开始(例如，初始角度45度)，然后执行一系列旋转直到我们逼近给定角θ。之后，我们可以直接读取旋转矢量的x和y值，这两个值即为对应cosθ和sinθ。这里假设最终矢量幅度等于1，你会看到计算正余弦并不难实现。
​ 让我们用一个示例来具体说明：计算
$sin60^\circ$
$cos60^\circ$
，即，
$\theta= 60^\circ$
。这个过程如图3.2所示。在这个例子中我们执行了五次旋转得到一个角度近似为
$60^\circ$
。我们初始矢量为0度即它从x轴正半轴开始。第一次旋转对应序号i = 0旋转了45度角(见表3.1)。由于我们想要得到
$60^\circ$
,所以我们沿正方向旋转。矢量旋转后得到
$45^\circ$

$60^\circ$

$45^\circ+ 26.565^\circ = 71.565^\circ$
,比例因子为1.118;
Could not load image

​ 两次旋转得到的比例因子为1.414×1.118 = 1.581，这也是CORDIC增益。继续讨论 i= 2,现在我们得到的角大于
$60^\circ$

$57.592^\circ$

​ 当我们做了足够多的旋转后，数据精度将会满足我们的要求，最后我们得到一个与期望输入角近似的矢量。这个矢量的x和y值，对应
$A_{R}$
$cos60^\circ$
$A_{R}$
$sin60^\circ$
,如果
$A_{R}$
= 1, 那么这个x与y的值正是我们想要得到的。由于我们通常知道将要执行的旋转次数，所以我们可以通过将预设初始矢量的大小为CORDIC增益的倒数来确保
$A_{R}$
= 1, 在我们的例子中,假设执行了五次旋转,如图3.2,可知需要设置初始矢量的值为
$1.64649^{-1} = 0.60735$
(当i=5时CORDIC增益的倒数;见表3.1)。由此，我们可以直接设置一个初始矢量为(0.60735，0)。
​ 如果我们再多做一次旋转，结果会变成怎样?再多做两次旋转(三次，四次，等等)会怎么样?当我们执行更多的旋转，精度会变成多少(例如，与MATLAB运算相比)?在一般情况下，你认为几次旋转是适合的?
​ 做更多的旋转有没有可能会使精度变得更差?提供一个发生这种情况的例子。
​ 图3.3提供了使用CORDIC算法实现正弦和余弦值计算的代码。它将输入角作为目标角，输出这个角对应的正弦和余弦值。代码使用数组cordic_phase作为查找表，这个查找表存储每次迭代的旋转角度。这个角度对应于表3.1中的“旋转角度”列中的值。我们假设cordic.h文件定义不同的数据类型(例如,COS_SIN_TYPE和THETA_TYPE)并设置NUM_ITERATIONS为某个常数。数据类型可以更改为不同的定点或浮点类型，设置NUM_ITERATIONS值要同时考虑我们期望的精度、资源和吞吐量。
//The file cordic.h holds definitions for the data types and constant valuse
#include "cordic.h"
//The cordic_phase array holds the angle for the current rotation
THETA_TYPE cordic_phase[NUM_ITERATIONS] = {
45, 26.56, 14.036, 7.125
3.576, 1.790, 0.895, ...
};
void
cordic(THETA_TYPE theta, COS_SIN_TYPE &s, COS_SIN_TYPE &c)
{
//Set the initial vector that we will rotate
//current_cos = I;current = Q
COS_SIN_TYPE current_cos =0.60735;
COS_SIN_TYPE current_sin = 0.0;
//Factor is the 2^(-L) value
COS_SIN_TYPE factor = 1.0;
//This loop iteratively rotates the initial vector to find the
//sine and cosine value corresponding to the input theta angle
for(int j = 0; j < NUM_ITERATIONS; j++){
//Determine if we are rotating by a positive or negative angle
int sigma = (theta < 0) ? -1 : 1;
//Save the current_cos,so that it can be used in the sine calculation
COS_SIN_TYPE temp_cos = current_cos;
//Perform the rotation
current_cos = current_cos - current_sin * sigma * factor;
current_sin = temp_cos * sigma * factor + current_sin;
//Determine the new theta
theta = theta - sigma * cordic_phase[j];
//Calculata next 2^(-L) value
factor = factor >> 1;
}
//Set the final sine and cosine values
s = current_sin;c = current_cos;
}

Could not load image

​ 此代码接近于“软件”版本。它有多种方式来提高其性能并减小资源面积。我们将在本章后面讨论如何优化这段代码。

# 3.4 笛卡尔向极坐标转换

​ 通过一些修改，CORDIC可以实现其它功能。例如，它可以实现笛卡尔和极坐标系转换；我们将在本节详细地描述这一点。CORDIC还可以做其他很多功能，我们把它留给读者作为练习。
​ 一个二维矢量v可以使用笛卡儿坐标系统(x,y)或极坐标系统(r,θ)来表示，对于极坐标系r是半径坐标(矢量的长度)和θ是角度坐标。这两种坐标系都有优缺点。例如，如果我们想做一个旋转，那么极坐标形式更容易实现，而笛卡尔坐标系更适合描述线性变换。
​ 两种坐标系之间的转换关系如下式所示：
\begin{aligned} x = r \cos \theta \quad(3.27) \\ y = r \sin \theta \quad(3.28) \\ r =\sqrt{x^2 + y^2} \quad(3.29) \\ \theta = atan2(y, x) \quad(3.30) \end{aligned}
atan2在arctan函数中定义为
$atan2(y, x) = \begin{cases} \arctan(\frac{y}{x}) \quad\quad\quad {if } x > 0 \\ \arctan(\frac{y}{x}) + \pi \quad {if } x < 0 { and } y \ge 0 \\ \arctan(\frac{y}{x}) - \pi \quad {if } x < 0 { and } y < 0 \\ \frac{\pi}{2} \quad \quad\quad {if } x = 0 { and } y > 0 \\ -\frac{\pi}{2} \quad\quad\quad {if } x = 0 { and } y < 0 \\ \text{undefined} \quad\quad\quad {if } x = 0 { and } y = 0 \end{cases}$
​ 这里提供了一种在两个坐标系之间转换的方法。然而，这些操作在硬件中并不容易实现。例如，sine，cosine，平方根和arctan都不是简单操作，它们需要大量的运算资源。但是我们可以使用CORDIC算法通过一系列简单的迭代旋转来实现这些操作。
​ 给定一个用笛卡尔坐标系表示的数(x, y)，我们使用CORDIC算法可以计算它的角度和幅度坐标(即，将它转换成极坐标形式)。为实现这一点，我们将给定的笛卡尔坐标系下的数据旋转为0度。一旦这个旋转完成，幅度就是最终旋转矢量的x值。要确定角度坐标，我们只需关注CORDIC执行旋转的累计角度。矢量旋转(i=0第一次旋转、i=1第二次旋转、i=3第三次旋转……)的角度可以存储在查找表中，用来计算sine /cosine。因此，我们只需要通过对这些角进行加减就可以得到总的旋转角度，而这里的加减操作取决于旋转方向。
​ 该算法与计算给定角的正弦和余弦相似。我们执行一系列带有递增值i的旋转，使最终的矢量位于(靠近)x的正半轴上（即0度)。这可以用正旋转或负旋转来实现，正负旋转取决于矢量的y值，而这个矢量的幅度和角度值都是我们希望确定的。
​ 算法执行第一步旋转得到的初始矢量在象限I或者IV。旋转
$90^\circ$

$90^\circ$

$90^\circ$

$\pm90^\circ$

$\pm90^\circ$

​ 这里存在旋转矢量最终径向数值的问题；它的大小与旋转前初始大小不同；它受CORDIC增益的影响。当然，也可以通过乘以对应CORDIC增益的倒数(例如，1/1.647 = 0.607)来精确计算矢量径向值。然而，这违背了设计CORDIC算法避免乘法运算的目的。不幸的是，这种乘法不能简单地使用移位和加法来实现。幸运的是，这个因素通常并不重要。例如，在无线通信中用于调制的调幅键控中，你只需要知道相对幅度。或者在其他应用中，这个振幅增益可以由系统的其他部分来补偿掉。
Could not load image

# 3.5 数字表示

​ cordic函数使用当前常用的变量类型。例如，变量sigma被定义为int类型，其他变量使用自定义数据类型(例如，THETA_TYPE和COS_SIN_TYPE)。在许多情况下，HLS工具能够进一步优化这些值，来实现硬件资源优化。举个例子,在图3.3中,变量sigma的值为1或−1，即使已经将变量声明为至少包含32位位宽的int类型，在不改变程序功能的情况下，可以用更少的位数用来实现。在其它情况下，特别是变量经常出现在函数输入、存储和递归中，HLS工具不能针对变量进行自动优化。在这些情况下，修改代码使用较小的数据类型是避免资源浪费的重要优化手段。
​ 虽然减少变量位宽通常是一个好的优化方法，但是这种优化方法可能改变程序的行为。一个小位宽数据类型不能像大位宽数据类型那样表征大量信息，而且无限的二进制数可以表示所有无限精度的实数。幸运的是，作为设计人员，我们可以选择符合特定需求的精度，并且可以在精度、资源占用和性能之间进行权衡。

## 3.5.1 二进制和十六进制数

​ 计算机和fpga通常使用二进制来表示数据，这使数据可以由开关信号组成的二进制数字或简单的位来有效地表示。二进制数在大多数情况下都像普通的十进制数一样工作，但是如果你不熟悉它们的工作原理，它们常常会导致混淆错误，在许多嵌入式系统和fpga中尤其如此，在这些系统中，最小化数据位宽可以极大地提高系统总体性能和效率。在本节中，我们将总结二进制算法以及计算机表示数字的基本方法。
​ 当我们表示一个普通整数，例如4062，它可以表示成(4 * 1000)+(0 * 100)+(6 * 10)+(2 * 1) = 4062，或者我们可以按如下方式表示
$10^3$
$10^2$
$10^1$
$10^0$
unsigned
4
0
6
2
= 4062
​ 二进制数表达方式与这个相似，不过没有用到数字0到9和10的幂。二进制数用0和1以及2的幂来表示数值
$2^3$
$2^2$
$2^1$
$2^0$
unsigned
1
0
1
1
= 11
​ 因为(1 * 8) + (0 * 4) + (1 * 2) + (1 * 1) = 11。为了避免歧义，二进制数经常在前边加“0b”，这个使0b1011很明显表示的是十进制11而不是数值1011。二进制数最高位是最关键的位置，同时二进制数最低位是最不重要的位置。
​ 十六进制数用0到15和16的幂次来表示数值
$16^3$
$16^2$
$16^1$
$16^0$
unsigned
8
0
3
15
= 32831
​ 为了避免歧义，数字10到15表示为字母“A”到“F”，同时十六进制数据前缀“0x”，因此在c语言中上面的数值可表示为0x803F。
​ 注意，二进制同样可以表示小数，这种类型数据通常叫做定点数，通过简单的拓展这种形式也可以表示负数。因此"0b1011.01"等效于：
$2^3$
$2^2$
$2^1$
$2^0$
$2^{-1}$
$2^-2$
unsigned
1
0
1
1
0
1
= 11.25
​ 因为8 + 2 + 1 + 1/4 = 11.25。不幸的是，C标准没有提供二进制表示常数的形式，尽管gcc和一些其他的编译器允许整型常数（没有小数点），这些常量前边会加“0b”。C99标准提供了一种描述浮点常数的方法，这种方法通过十六进制和指数来表示，注意指数是无法省略的，甚至值为0的情况下也不能省略。
float p1 = 0xB.4p0;//Initialize p1 to "11.25"
float p2 = 0xB4p-4;//Initialize p2 to "11.25"
​ 一般来说，对于一个无符号数，只需要填写数值中非零的数字，没有显示的数字都可以假设为零。因此，用更多的数字表示相同的值很容易：只要添加尽可能多的零就可以了。这个过程通常称为零扩展。注意，每个附加的数字都增加了可以表示数值的范围。在二进制数中每添加一位，可以使表示的数字范围增加一倍，而在十六进制数字中每增加一位会使可表示的数字范围增加16倍。
$2^7$
$2^6$
$2^5$
$2^4$
$2^3$
$2^2$
$2^1$
$2^0$
$2^{-1}$
$2^-2$
$2^-3$
$2^-4$
unsigned
0
0
0
0
1
0
1
1
0
1
0
0
=11.25
​ 注意，二进制数可以定义为任意位宽，而不仅仅是8、16和32位。例如System C[ 2 ]通过定义一系列模板类，可以实现任意精度整数和定点数（包括 sc_int<>,sc_uint<>,sc_bigint<>,sc_ubigint<>,sc_fixed<>,和sc_ufinxed<>）尽管它们最初是为系统模型定义的，而不是为了综合，但这些类在HLS工具中可以广泛使用。Vivado HLS包含相似的模板类（ap_int<>,ap_uint<>,ap_fixed<>,和ap_ufixed<>）这些类在通常情况下在仿真和综合上都会比SystemC类性能好。
​ 通过使用0值，任意精度数被很好的定义(虽然用处不大)。列出所有能用0位数字表示的数字。

## 3.5.2 负数

​ 负数的表示比正数稍微复杂一些，一定程度上是因为它有不同的表示方法。一种简单的方法是用符号位表示负数，通常称为有符号幅值表示。这种表示只是在数字前面添加了一个额外的位，以表示它是否有符号。有符号幅值表示法的奇怪之处是，有不止一种方法可以表示0。这使得有些简单操作例如 operator == () 实现起来更加复杂。
+/-
$2^1$
$2^0$
signed magnitude
0
1
1
= 3
0
1
0
= 2
0
0
1
= 1
0
0
0
= 0
1
0
0
= -0
1
0
1
= -1
1
1
0
= -2
1
1
1
= -3
​ 另一种表示负数的方法是用偏移码表示。这种表示方法是增加了一个常量偏移(通常等于最高位数值)，否则视为正数：
$2^2$
$2^1$
$2^0$
biased
1
1
1
= 3
1
1
0
= 2
1
0
1
= 1
1
0
0
= 0
0
1
1
= -1
0
1
0
= -2
0
0
1
= -3
0
0
0
=- 4
​ 然而，到目前为止，最常用的用于实现负数的技术被称为“二进制补码”。二进制补码中最重要的位表示数值的符号(即数值表示为符号+大小)，二进制补码也表示偏移量是否可以用。理解这种表示方法的思路是将最高位表示成对应位宽的负数。
-
$2^2$
$2^1$
$2^0$
two's complement
0
1
1
= 3
0
1
0
= 2
0
0
1
= 1
0
0
0
= 0
1
1
1
= -1
1
1
0
= -2
1
0
1
= -3
1
0
0
= -4
-
$2^4$
$2^3$
$2^2$
$2^1$
$2^0$
two's complement
0
0
0
1
1
= 3
0
0
0
1
0
= 2
0
0
0
0
1
= 1
0
0
0
0
0
= 0
1
1
1
1
1
= -1
1
1
1
1
0
= -2
1
1
1
0
1
= -3
1
1
1
0
0
= -4
​ 无符号数与二进制补码之间的一个重要区别是，我们需要确切地知道数值有多少位来表示，因为最高位与其它位代表不同的意义。此外，当扩展带符号的二进制补码时要复制符号位到所有新增的比特位。这个过程通常称为符号位扩展。在本书的其余部分中，除非另有说明，我们通常假设所有带符号的数字都用二进制补码表示。
​ N位二进制补码能表示的正数最大是多少?最大的负数是多少?
​ 给定一个正数x,如何用二进制补码来表示−x?−0的二进制补码是什么?如果x是N位二进制补码所能表示的最大的负数,那么−x是什么?

## 3.5.3 溢出、下溢和舍入

​ 当一个数值大于给定位宽所能表示的最大值时，就发生溢出(Overflow)。类似地，当一个数值小于可以表示的最小值时，就发生下溢(Underflow)。处理溢出或下溢的常见方法是简单地删除原始数字中最重要的位，这个操作通常称为包装(Wrapping)。
$2^5$
$2^4$
$2^3$
$2^2$
$2^1$
$2^0$
$2^{-1}$
$2^-2$
$2^-3$
$2^-4$
0
0
1
0
1
1
0
1
0
0
=11.25
0
1
0
1
1
0
1
0
0
=11.25
1
0
1
1
0
1
0
0
=11.25
0
1
1
0
1
0
0
=3.25
​ 通过包装二进制补码的方式解决溢出和下溢的问题可能会导致正数变为负数，负数变为正数。
|
$-2^3$
|
$2^2$
|
$2^1$
|
$2^0$
|
$2^{-1}$
|
$2^{-2}$
|
$2^{-3}$
|
$2^{-4}$
| two' complement || | ------ | ----- | ----- | ----- | -------- | -------- | -------- | -------- | --------------- | | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | =-4.75 |
$-2^2$
$2^1$
$2^0$
$2^{-1}$
$2^{-2}$
$2^{-3}$
$2^{-4}$
two' complement
0
1
1
0
1
0
0
=3.25
​ 同样，当一个数值不能通过给定小数位数来精确地表示时，需要采用舍入来解决这个问题。同样，这有几种常见的方法来对数值进行舍入。最简单的方法就是去掉额外不能表示的小数位数，但这样就会使数值变的更负。这种舍入的方法通常被称为向下舍入或向负无穷舍入。当向下舍入到最近的整数时，它就能与floot()函数对应起来，尽管它也可能舍入到其他小数位。
Could not load image
​ 同样，也可以使用类似的方法使舍入后数值变得更大(这种称为向上舍入或向正无穷舍入与ceil()函数相对应),向绝对值较小的方向舍入(称为向零舍入与trunc()函数相对应),或向绝对值更大的值舍入(称为远离零舍入或向无穷舍入和round()函数相对应)。然而，这些操作中没有一个总可以最小化舍入误差。一种更好的方法叫做向最接近偶数舍入、收敛舍入或四舍六入五成双，它在lrint()函数中实现。正如你所期望的，这种舍入方式总是选择最近可表示数字。另外，如果有两个误差相等的数，则取偶数。如果最后一个数值是零，那么任意精度数是一个偶数。这种方法是处理IEEE浮点数舍入的默认方法，因为它不仅可以最小化舍入误差，而且还可以确保计算随机数舍入误差之和趋于零。

## 3.5.4 二进制运算

​ 二进制加法与十进制加法相似，可以简单地对齐每位二进制数并进行加法运算，注意正确处理从一列到下一列的进位操作。注意，两个N位数值加或减的结果通常需要N+1位的数值来正确表示才不能溢出。对于小数，总是在符号位进行增加位宽
$2^3$
$2^2$
$2^1$
$2^0$
unsigned
0
1
1
=3
+
0
1
1
=3
=
0
1
1
0
=6
$2^3$
$2^2$
$2^1$
$2^0$
$2^{-1}$
unsigned
1
1
1
1
=7.5
+
1
1
1
1
=7.5
=
1
1
1
1
0
=15
​ 注意由于减法结果可能是负数，那个“额外的位数”就成了有符号二进制补码数据的符号位。
$2^3$
$2^2$
$2^1$
$2^0$
unsigned