标签软件算法下的文章 - 我的学记|刘航宇的博客

登录 / 注册

软件算法(共9篇)

找到 9 篇与软件算法相关的结果

Python与Verilog实现卡尔曼滤波器 — 机器人位置估计摘要：本文介绍了卡尔曼滤波在机器人位置估计中的应用，分别用Python和Verilog实现了卡尔曼滤波器，并对比了两种实现方式的优缺点。目录一、引言：为什么机器人需要卡尔曼滤波？二、卡尔曼滤波的五大核心公式三、以机器人为例卡尔曼公式实现和说明设计运动传感器的观测值卡尔曼滤波四、Verilog实现：定点运算与硬件加速4.1 系统架构 4.2 核心代码解析（1）Kalman_1：状态预测（公式1）（2）Kalman_2_3：协方差预测与增益计算（公式2、3）（3）Kalman_4_5：状态与协方差更新（公式4、5）（4）Kalman_ctrl：数据源控制 4.3 10级流水线时序五、Python vs Verilog：对比分析六、总结工程参考代码清单Python仿真代码 Verilog完整工程文件一、引言：为什么机器人需要卡尔曼滤波？想象你开发了一个可以在树林里自主导航的机器人。为了知道它的实时位置，你在机器人上安装了GPS传感器，但GPS的精度大约为10米——在布满沟壑和悬崖的树林里，10米的误差足以让机器人坠入深渊。此时，你还可以获取一些额外的运动信息：里程计可以记录机器人的行走距离，惯性测量单元（IMU）可以感知姿态变化。但这些传感器同样存在噪声和漂移。GPS告诉了你"大概在哪"，里程计告诉了你"走了多远"，但两者都不完美。卡尔曼滤波（Kalman Filter）的核心思想正是：综合利用所有可用的信息，根据其本身的噪声特性分配权重，得到一个比任何单一估计都更准确的结果。本文将从原理出发，分别用 Python（浮点运算，算法验证）和 Verilog（定点运算，硬件加速）实现一维卡尔曼滤波器，用于机器人位置估计。二、卡尔曼滤波的五大核心公式卡尔曼滤波是一种最优线性递归估计算法，由预测（Prediction）和更新（Update）两个阶段组成，共五个核心公式：对于线性离散系统，卡尔曼滤波通过以下五个公式递归运行：阶段公式含义预测$\hat{X}_k^- = A\hat{X}_{k-1} + BU_{k-1}$先验状态估计：用上一时刻的最优估计预测当前状态预测$P_k^- = AP_{k-1}A^T + Q$先验误差协方差：预测的不确定性会累积更新$K_k = \frac{P_k^-H^T}{HP_k^-H^T + R}$卡尔曼增益：决定"更信预测还是更信测量"更新$\hat{X}_k = \hat{X}_k^- + K_k(Z_k - H\hat{X}_k^-)$后验状态估计：用测量残差修正预测更新$P_k = (I - K_kH)P_k^-$后验误差协方差：更新后的不确定性其中： $A$ 为状态转移矩阵，$B$ 为控制矩阵，$H$ 为观测矩阵 $Q$ 为过程噪声协方差，$R$ 为测量噪声协方差 $K_k$ 是卡尔曼增益，它是整个算法的"灵魂"：$P_k^-$ 越大（预测越不靠谱），$K_k$ 越大，越重视测量反馈。三、以机器人为例卡尔曼公式实现和说明下面我们用一个例子来说明上述卡尔曼滤波公式的内在逻辑。假如我们有一台轮式机器人 Robo 如图所示，它只能够进行一维直线运动。 pmqvRRH.png图片我们用状态向量 $\vec{x}$ 来表示机器人的当前状态： $\vec{x}=\left[ \begin{array}{c}{p} \\ {v}\end{array}\right] \\$ 其中 $p$ 和 $v$ 分别为相对于绝对坐标系 $O_1$ 的位移。那么我们要做的是，已知某时刻的最佳状态估计 $\hat{\mathbf{x}}_{k}$ ，预测下一时刻的最佳估计 $\hat{\mathbf{x}}_{k+1}$ 。设计运动我们为 Robo 设计一个匀加速直线运动。设初始状态向量为 $\vec{x_0}=\left[ \begin{array}{c}{0} &{1}\end{array}\right]^T $ ，并有一个加速指令性，使其以 $a = 0.1$ 的加速度做匀加速直线运动。那么根据匀加速直线运动的位移计算公式，任意时刻 $k$ 的位移 $p$ 与速度 $v$ 都可以由位移、速度、加速度递推得到： $\begin{aligned} p_{k} &=p_{k-1}+v_{k-1} \times \Delta k+a\times \frac{\Delta k^{2}}{2} \\ v_{k} &=v_{k-1}+a \times \Delta k \end{aligned} \tag{3} $ 将其转化为矩阵形式： $\left[ \begin{array}{c}{p_{k}} \\ {v_{k}}\end{array}\right]=\left[ \begin{array}{cc}{1} & {\Delta k} \\ {0} & {1}\end{array}\right] \left[ \begin{array}{c}{p_{k-1}} \\ {v_{k-1}}\end{array}\right]+\left[ \begin{array}{c}{\frac{\Delta k^{2}}{2}} \\ {\Delta k}\end{array}\right] a \tag{4}$ $x_{t}=F_{t} x_{t-1}+B_{t} a \\$ 我们取时间间隔 $\Delta k = 1$ ，由上式编程计算得到机器人的真实状态向量轨迹： import numpy as np import math import matplotlib.pyplot as plt if __name__=="__main__": ## 1.设计一个匀加速直线运动，以观测此运动 X_real = np.mat(np.zeros((2, 100))) # 空矩阵，用于存放真实状态向量 X_real[:, 0] = np.mat([[0.0], # 初始状态向量 [1.0]]) a_real = 0.1# 真实加速度 F = np.mat([[1.0, 1.0], # 状态转移矩阵 [0.0, 1.0]]) Q = np.mat([[0.0001, 0.0], # 状态转移协方差矩阵，我们假设外部干扰很小 [0.0, 0.0001]]) B = np.mat([[0.5], # 控制矩阵 [1.0]]) for i in range(99): X_real[:, i + 1] = F * X_real[:, i] + B * a_real # 计算真实状态向量 X_real = np.array(X_real) fig = plt.figure(1) plt.grid() plt.title('real displacement') plt.xlabel('k (s)') plt.ylabel('x (m)') plt.plot(X_real[0, :]) plt.show() fig = plt.figure(2) plt.grid() plt.title('real velocity') plt.xlabel('k (s)') plt.ylabel('v (m/s)') plt.plot(X_real[1, :]) plt.show() X_real = np.mat(X_real)pasted_1786518907327_xixy8e.png图片位移真实值 pasted_1786518920293_nxitzh.png图片速度真实值传感器的观测值我们有一台传感器 $O_2$ 放置于机器人的前方，它可以测得机器人位移 $s$ 和速度 $w$ 。当然，传感器自身本身有一定的噪声 $\xi$ ，其协方差为 $R$ 。由于传感器的信息是相对于自身坐标系 $O_2$ 的，而我们的状态向量 $\vec{x}$ 是相对于绝对坐标系 $O_1$ 的，二者的方向刚好相反，我们使用观测矩阵 $\mathbf{H}$ 来转换二者的关系。因此，相对于真实状态向量，传感器的观测向量可以表示如下： $\left[ \begin{array}{c}{s} \\ {w}\end{array}\right]=\left[ \begin{array}{cc}{-1} & 0\\ {0} & {-1}\end{array}\right] \left[ \begin{array}{c}{p} \\ {v}\end{array}\right]+\left[ \begin{array}{c}{\xi_p} \\ {\xi_v}\end{array}\right] \tag{5}$ $z_{t}=H x_{t}+\xi \\$ 我们设传感器噪声的协方差 $R$ 为单位阵(噪声方差为1)。根据上式编写程序，得到的传感器的观测值如下： ## 2.建立传感器观测值 z_t = np.mat(np.zeros((2, 100))) # 空矩阵，用于存放传感器观测值 H = np.mat(np.zeros((2, 2))) H[0, 0], H[1, 1] = -1.0, -1.0 noise = np.mat(np.random.randn(2,100)) # 加入位移方差为1，速度方差为1的传感器噪声 R = np.mat([[1.0, 0.0], # 观测噪声的协方差矩阵 [0.0, 1.0]]) for i in range(100): z_t[:, i] = H * X_real[:, i] + noise[:, i] z_t = np.array(z_t) fig = plt.figure(3) plt.grid() plt.title('sensor displacement') plt.xlabel('k (s)') plt.ylabel('x (m)') plt.plot(z_t[0, :]) plt.show() fig = plt.figure(4) plt.grid() plt.title('sensor velocity') plt.xlabel('k (s)') plt.ylabel('v (m/s)') plt.plot(z_t[1, :]) plt.show() z_t = np.mat(z_t)pasted_1786518974937_94intu.png图片传感器观测到的位移，与真实值相反且有噪声 pasted_1786519009388_5uhe6m.png图片传感器观测到的速度，与真实值相反且有噪声卡尔曼滤波前两步的操作主要是为了获取数据，现在我们利用预测和更新公式对以上数据进行卡尔曼滤波： ## 3.执行线性卡尔曼滤波 Q = np.mat([[1.0, 0.0], # 状态转移协方差矩阵，我们假设外部干扰很小， [0.0, 1.0]])# 转移矩阵可信度很高 # 建立一系列空序列用于储存结果 X_update = np.mat(np.zeros((2, 100))) P_update = np.zeros((100, 2, 2)) X_predict = np.mat(np.zeros((2, 100))) P_predict = np.zeros((100, 2, 2)) P_update[0, :, :] = np.mat([[1.0, 0.0], # 状态向量协方差矩阵初值 [0.0, 1.0]]) P_predict[0, :, :] = np.mat([[1.0, 0.0], # 状态向量协方差矩阵初值 [0.0, 1.0]]) for i in range(99): # 预测 X_predict[:, i + 1] = F * X_update[:, i] + B * a_real P_p = F * np.mat(P_update[i, :, :]) * F.T + Q P_predict[i + 1, :, :] = P_p # 更新 K = P_p * H.T * np.linalg.inv(H * P_p * H.T + R) # 卡尔曼增益 P_u = P_p - K * H * P_p P_update[i + 1, :, :] = P_u X_update[:, i + 1] = X_predict[:, i + 1] + K * (z_t[:, i + 1] - H * X_predict[:, i + 1]) X_update = np.array(X_update) X_real = np.array(X_real) fig = plt.figure(5) plt.grid() plt.title('Kalman predict displacement') plt.xlabel('k (s)') plt.ylabel('x (m)') plt.plot(X_real[0, :], label='real', color='b') plt.plot(X_update[0, :], label='predict', color='r') plt.legend() plt.show() fig = plt.figure(6) plt.grid() plt.title('Kalman predict velocity') plt.xlabel('k (s)') plt.ylabel('v (m/s)') plt.plot(X_real[1, :], label='real', color='b') plt.plot(X_update[1, :], label='predict', color='r') plt.legend() plt.show() X_update = np.mat(X_update) X_real = np.mat(X_real)pasted_1786519044132_v2numq.png图片位移卡尔曼滤波结果 pasted_1786519056398_qpvdv1.png图片速度卡尔曼滤波结果可以看出，卡尔曼滤波将存在误差的传感器信号和状态向量很好的融合，较好地预测出了真实地机器人运动状态。四、Verilog实现：定点运算与硬件加速当我们需要将卡尔曼滤波部署到FPGA或ASIC上时，Python的浮点运算就不再适用。硬件实现需要考虑：定点数表示、流水线设计、时序约束和资源复用。附件中的Verilog代码展示了一个轻量级、10级流水线的卡尔曼滤波器实现。 4.1 系统架构 pasted_1786519272107_29m7o0.png图片整个系统分为5个模块：模块功能对应公式Kalman顶层模块，实例化子模块并连接信号—Kalman_1预测状态 X^-公式1Kalman_2_3预测协方差 P^- 并计算增益 Kg公式2、3Kalman_4_5更新状态 X 和协方差 P公式4、5Kalman_ctrl数据控制器，从DPRAM读取测量值—以及3个共享运算器：add（加减法）、mux（乘法）、div（除法）。 4.2 核心代码解析（1）Kalman_1：状态预测（公式1） module Kalman_1( input clk_50M, input Rst_n, input [15:0] X_last, // t-1时刻的后验估计 input [15:0] B_X_last, // 控制输入（预留，当前为0） output reg [15:0] X_ // t时刻的先验估计 ); // 流水线计数 0~9 always@(posedge clk_50M or negedge Rst_n) begin if(!Rst_n) X_ <= 16'd0; else begin case (Count) 4'd1: begin X_ <= X_last; // X^- = X_last（简化模型） end // ... 其他时钟周期可用于更复杂的预测 endcase end end endmodule设计要点：当前实现为简化模型，直接令 X^- = X_last。B_X_last 预留了控制输入接口，可扩展为带速度项的运动模型。（2）Kalman_2_3：协方差预测与增益计算（公式2、3） module Kalman_2_3( input clk_50M, input Rst_n, input [15:0] P_last, output reg [15:0] P_, output reg [15:0] Kg ); reg [15:0] Q_error = 0; // 系统过程协方差 reg [15:0] R_error = 3; // 测量噪声协方差 always@(posedge clk_50M or negedge Rst_n) begin case (Count) 4'd1: begin ADD_sub <= 1'd1; // 加法 ADD_dataa <= P_last * 'd100; // P_last 放大100倍 ADD_datab <= Q_error; // + Q end 4'd2: begin P_ <= ADD_result; // P^-（仍放大100倍） ADD_dataa <= ADD_result / 'd10; // 缩小10倍 ADD_datab <= R_error * 'd10; // R 放大10倍 end 4'd3: begin DIV_dataa <= P_; // 被除数 = P^-（×100） DIV_datab <= ADD_result; // 除数 = P^-/10 + R×10 end 4'd4: begin Kg <= DIV_result; // Kg = P^- / (P^- + R) P_ <= P_ / 'd100; // P^- 恢复原始量级 end endcase end endmodule定点数与缩放处理：这是硬件实现中最关键的部分。由于16位定点数无法直接表示小数，代码采用了缩放因子（Scaling Factor）策略： P_last * 100：将协方差放大100倍，避免小数被截断 R_error * 10：测量噪声放大10倍最终 Kg 的计算结果也需要在后续模块中相应缩放 // 在Kalman_4_5中处理缩放还原 MULT_datab <= ADD_result / 'd10; // 乘法结果缩小10倍 ADD_datab <= Kg / 10; // Kg缩小10倍用于1-Kg计算（3）Kalman_4_5：状态与协方差更新（公式4、5） module Kalman_4_5( input clk_50M, input Rst_n, input [15:0] in_data, // 测量值 Z input [15:0] X_, // 先验估计 input [15:0] P_, // 先验协方差 input [15:0] Kg, // 卡尔曼增益 output reg [15:0] X, // 后验估计 output reg [15:0] P // 后验协方差 ); always@(posedge clk_50M or negedge Rst_n) begin case (Count) 4'd2: begin // 计算 |Z - X^-|，通过比较大小确定减法顺序 if(in_data > X_) begin ADD_dataa <= in_data; ADD_datab <= X_; end else begin ADD_dataa <= X_; ADD_datab <= in_data; end end 4'd5: begin MULT_dataa <= Kg; MULT_datab <= ADD_result; // Kg * |Z - X^-| end 4'd6: begin // 根据in_data和X_的大小关系，决定加或减 if(in_data > X_) ADD_sub <= 1'd1; // 加法：X = X^- + Kg*(Z-X^-) else ADD_sub <= 1'd0; // 减法：X = X^- - Kg*(X^- - Z) ADD_dataa <= X_; ADD_datab <= MULT_result / 'd10; end 4'd7: begin X <= ADD_result; // 输出更新后的状态 ADD_dataa <= 16'd1; ADD_datab <= Kg / 10; // 1 - Kg/10 end 4'd8: begin MULT_dataa <= P_; MULT_datab <= ADD_result; // P = P^- * (1 - Kg) end 4'd9: begin P <= MULT_result; // 输出更新后的协方差 end endcase end endmodule有符号数处理技巧：由于Verilog中 [15:0] 默认是无符号数，代码巧妙地通过先取绝对值做减法，再根据大小关系决定加减，避免了有符号数运算的复杂性。（4）Kalman_ctrl：数据源控制该模块模拟了传感器数据源。实际应用中，这里可以替换为ADC接口、串口接收或传感器总线（如I2C/SPI）。 4.3 10级流水线时序 pasted_1786519515333_7gcyvi.png图片每个滤波周期 = 10个时钟周期 @ 50MHz = 200ns，即每秒可处理500万次滤波迭代，这是硬件加速相比软件的巨大优势。五、Python vs Verilog：对比分析对比维度Python实现Verilog实现数据表示IEEE 754 双精度浮点（64位）16位定点整数 + 缩放因子运算精度高（~15位有效数字）有限（受限于位宽和缩放策略）执行速度受限于CPU，~μs级50MHz时钟，200ns/次迭代资源消耗内存（MB级）LUT/FF/DSP（硬件资源）开发难度低，代码简洁高，需处理时序、缩放、位宽适用场景算法验证、仿真、离线分析实时嵌入式、FPGA加速、ASIC可移植性跨平台依赖具体FPGA/ASIC工艺关键差异——定点数缩放： Python中可以直接写 Kg = P_pred / (P_pred + R)，而Verilog中必须手动管理数值范围： # Python：自然优雅 Kg = P_pred / (P_pred + R) # 0.09... X = X_pred + Kg * (z - X_pred)// Verilog：需要精心设计的缩放 // P_last * 100 -> ADD -> /100 -> DIV -> Kg // Kg / 10 -> MULT -> /10 -> ADD -> X这种"不优雅"是硬件实现的代价，但也是达到实时性能的必要手段。六、总结卡尔曼滤波是机器人状态估计的基石算法。本文从机器人位置估计这一经典场景出发：原理层面：梳理了卡尔曼滤波的五大核心公式，阐明了预测与更新的闭环逻辑。 Python层面：利用浮点运算实现了算法原型，验证了滤波器对噪声的抑制效果和增益收敛特性。 Verilog层面：设计了10级流水线的定点数实现，通过缩放因子策略在16位位宽下完成了滤波运算，达到了200ns/次迭代的实时性能。两种实现方式各有其用：Python用于"想清楚"，在算法层面验证正确性；Verilog用于"跑得快"，在硬件层面实现实时处理。在实际工程中，通常先用Python/MATLAB进行算法仿真和参数整定，再将验证通过的算法移植到Verilog/VHDL进行硬件部署——这正是从算法到芯片的完整开发流程。工程参考代码清单 Python仿真代码见上文第三节完整代码。 Verilog完整工程文件

FPGA&ASIC 通信&信息处理 VLSI&IC验证软硬件算法 # ASIC/FPGA # 信号处理 # Verilog # 软件算法

刘航宇 8月12日
1 56 2
在FPGA上部署轻量BP神经网络-Python与Verilog：信号检测实战摘要：本文介绍了在FPGA上部署轻量BP神经网络进行信号检测的实战，包括系统架构、神经网络模型设计、FPGA硬件实现详解以及关键优化技巧，实验结果表明该方案功耗低、性能好。目录储备知识：一、背景：为什么要在FPGA上跑神经网络？二、系统整体架构三、神经网络模型设计：极致轻量四、FPGA硬件实现详解4.1 串并转换模块（Serial-to-Parallel 4.2 数据归一化模块 4.3 隐藏层神经元模块（核心计算单元） 4.4 ReLU激活函数模块 4.5 输出层神经元模块 4.6 阈值判断模块五、关键优化技巧5.1 归一化的"逆向"处理 5.2 权值二值化（BWN）降低功耗 5.3 亚稳态消除六、实验结果：功耗与性能七、总结与思考 python和verilog源程序下载储备知识：我们在前文讲了BP神经网络算法和激活函数 BP神经网络算法 https://ee.ac.cn/index.php/archives/612.html 激活函数讲解 https://ee.ac.cn/index.php/archives/617.html 一、背景：为什么要在FPGA上跑神经网络？在无源物联网（Battery-free IoT）和反向散射通信（Backscatter）场景中，传统的信号检测方法（如能量检测）虽然电路简单，但无法区分同频段的多种信号，且受噪声影响大；而基于PC或GPU的深度学习方案虽然精度高，但功耗动辄数十瓦，显然无法部署在依赖能量采集的微瓦级标签上。核心矛盾在于：缺乏一种检测精度高、功耗极低（毫瓦级）、且能实时处理的解决方案。答案是将轻量级的BP神经网络部署到低功耗FPGA上，在边缘端完成信号推理。二、系统整体架构整个检测系统的链路如下：目标信号 → 天线 → 阻抗匹配 → LNA放大 → 包络检波(ENV) → ADC采样(1MSPS, 12bit) → FPGA(BP神经网络推理) → 调制控制信号在FPGA内部，BP神经网络负责识别当前输入的512点采样数据是否为目标信号的前导码（Preamble）。一旦识别成功，输出控制信号，开启后端的Backscatter调制模块。 FPGA选型：Actel IGLOO/e系列 AGLE600V5-FG484。选择它的原因是： Flash架构：上电即运行，无需外部配置芯片，适合无源系统；超低功耗：静态功耗仅0.046mW，适合能量采集场景；资源适中：13824个逻辑单元，足以容纳轻量级网络。三、神经网络模型设计：极致轻量为了在FPGA上高效部署，网络结构必须足够"轻"。本文设计的网络结构如下： pasted_1785558315326_lc6zyp.png图片层级神经元数说明输入层512对应ADC采集的一条信号的512个采样点隐藏层2仅2个神经元，大幅降低计算量输出层1二分类：是目标信号(1) / 非目标信号(0)激活函数：隐藏层和输出层均采用 ReLU。 $$f(x) = \max(0, x)$$ 选择ReLU的原因不仅是训练效果好，更重要的是硬件实现极其简单——只需一个比较器判断正负，无需计算指数或乘法，这对FPGA非常友好。 pasted_1785561816152_bsny25.png图片训练环境：TensorFlow/Keras，使用Adam优化器和MSE损失函数。在真实环境数据集上训练后，测试集识别准确率可达 95.76%。 pasted_1785561967835_yy5zgm.png图片四、FPGA硬件实现详解 FPGA内部的神经网络是一个纯推理引擎。本节按数据流方向，逐个拆解每个模块的设计思路和Verilog实现要点。 pasted_1785562098406_gf64mu.png图片整体RTL结构如下： pasted_1785563631508_f74j4w.png图片 4.1 串并转换模块（Serial-to-Parallel pasted_1785563649652_chqrj8.png图片 ADC（ADS7042）在片选信号CS拉低后，先输出2个前导0，再输出12位有效数据（D11→D0），每个数据位占用一个CLK周期。设计要点： CS和CLK由FPGA内部产生，CS每16个CLK周期拉低一次；在CS下降沿开始，用计数器对串行数据移位寄存；凑齐12位有效数据后，输出一组并行数据 adc_data[11:0]。波形图 pmhbofe.png图片 module serial_p(input data0_in,input cs,input clk,output[12:0] data0_out,input rst); reg[11:0] temp; reg[12:0] save; integer count; integer cnt; always @(negedge clk or negedge rst) begin if(!rst) begin//reset temp<=12'b000000000000; count<=-1; save<=12'b111111111111; cnt<=-1; end else if(cs&&count%16==0) begin save<={1'b0,temp}; count<=1; cnt<=cnt+1; if(cnt==512) begin cnt<=1; end end else if(cs) begin temp<=12'b0; count<=1; end else if(count<3) count<=count+1; else begin temp<={temp,data0_in}; count<=count+1; end end assign data0_out=save; endmodule 4.2 数据归一化模块问题：训练时，输入数据被归一化到 [0, 1.8]（对应ADC参考电压1.8V）。如果在FPGA中直接用除法做 Vin = adc_data / 4095 * 1.8，会消耗大量逻辑资源（FPGA做除法器代价极高）。解决方案：在软件端完成归一化，FPGA端只做整数运算。具体做法：在Python/Keras训练时，将输入数据 x 归一化为 x_norm = x / 4095 * 1.8；在提取权值时，将第一层权值 w 除以 1.8 并放大 1024 倍取整；这样FPGA输入的原始ADC值 adc_data（范围0~4095）直接与预处理后的权值相乘，等效于完成了归一化+加权。 # 创建一个自定义的回调对象 cb = MyCallback() # 以只读方式打开训练数据文件 with open('/content/work/data/data.txt') as traindata: # 读取文件内容 data = traindata.read() # 将文件内容转换为numpy数组，并将数据类型转换为float，并将数组形状调整为(47100, 2) data = np.array(list(data.split()), dtype=float).reshape((47100, 2)) # 创建一个最大最小归一化对象 min_max_scaler = preprocessing.MinMaxScaler() # 归一化 data = data * (1/65535) # 以只读方式打开训练标签文件 with open('/content/work/data/label.txt') as labda: # 读取文件内容 labels = labda.read() # 将文件内容转换为numpy数组，并将数据类型转换为float，并将数组形状调整为(47100, 2) labels = np.array(list(labels.split()), dtype=float).reshape((47100, 2)) # 对data和labels进行乱序，保持它们的对应关系 # 为了保持对应关系，需要先将data和labels沿着第二个维度拼接起来，形成一个(100, 4)的数组 # 然后对这个数组进行乱序，再将它们沿着第二个维度分开，还原成data和labels data_labels = np.concatenate((data, labels), axis=1) np.random.shuffle(data_labels) data = data_labels[:, :2] labels = data_labels[:, 2:]FPGA端实现：实际上，归一化模块在FPGA中被合并到了权值预处理阶段，硬件上不需要额外的归一化电路。但为了模块化清晰，也可以显式设计一个"电压映射"模块，将12bit ADC码值转换为定点数格式：工程建议：永远不要在FPGA里做除法。所有线性变换（归一化、缩放）都应在软件端合并到权值中，FPGA只做整数乘加。 4.3 隐藏层神经元模块（核心计算单元）隐藏层的数学表达式： $$y = \text{ReLU}\left( \sum_{i=1}^{512} x_i \cdot w_i + b \right)$$ , i = 1..512 工程难点： 512次乘累加如果在一个时钟周期完成，需要512个乘法器，资源爆炸；如果纯串行完成，需要512个时钟周期，一条chirp要512×512=262144个周期，太慢。解决方案：采用串行MAC流水线 + 双缓冲FIFO 架构。设计思路：权值存储：512个权值和1个偏置在编译时以 reg [31:0] w[0:511] 形式固化在FPGA中； FIFO缓存：ADC每输出一个采样点，立即写入FIFO。FIFO深度设为16即可（只要保证不溢出），因为读出速度（MAC运算）和写入速度（ADC采样）基本匹配；串行MAC：每个时钟周期从FIFO读出一个数据 xi，与对应的 wi 相乘，累加到累加器 acc； 512个周期后：累加器结果加上偏置 b，送入ReLU模块。 pasted_1785563798085_32317i.png图片 FIFO波形图 pmhqDBt.png图片关键设计细节：位宽设计：输入22bit × 权值32bit = 乘法结果54bit，累加512次需要额外9bit，因此累加器至少需要 63bit。如果位宽不够，累加会溢出，导致结果完全错误。时序约束：乘法器和加法器要满足16MHz时钟的建立保持时间。如果组合逻辑延迟太大，需要插入流水线寄存器（将乘法器和加法器分两级完成）。双神经元并行：隐藏层有2个神经元，需要例化两个上述模块，各自独立的权值存储和累加器，但共享同一个FIFO输入。 4.4 ReLU激活函数模块 ReLU的硬件实现是整个网络中最简单的部分： pmhqWcj.png图片 module relu ( input wire clk, input wire rst_n, input wire [31:0] x_in, // MAC+bias结果 input wire x_valid, output reg [31:0] y_out, output reg y_valid ); always @(posedge clk or negedge rst_n) begin if (!rst_n) begin y_out <= 32'd0; y_valid <= 1'b0; end else begin y_valid <= x_valid; if ($signed(x_in) >= 0) y_out <= x_in; else y_out <= 32'd0; end end endmodule4.5 输出层神经元模块输出层只有1个神经元，输入是隐藏层2个神经元的输出： $$\text{output} = \text{ReLU}\left( h_1 \cdot w'_1 + h_2 \cdot w'_2 + b' \right)$$ 这个模块与隐藏层类似，但逻辑资源消耗极小。 pmhq7NT.png图片 module nerual_out( clk, rst,x1,x2,data_out ); input clk, rst; input signed[0:49] x1,x2; output signed[79:0] data_out; //<statements> //reg signed[0:28] weight[0:1]; reg signed[0:7] save,save1,save2; localparam bais=-50'd214979034352654; //localparam bais = -26'd6406874; localparam weight0 = 29'd22506522; localparam weight1 =-29'd341584992; //integer bais; integer count; always @(negedge clk or negedge rst) begin if(!rst) //reset,set values and bias begin // bais<=-50'd214979034352654; // weight[0]<=29'd22506522; // weight[1]<=-29'd341584992; save<=0; save1<=0; save2<=0; count<=0; end else begin save1<=x1*weight0; save2<=x2*weight1; count<=count+1; if(count>518) save<=save1+save2+bais;//Multiply the input by the weights and add up the results end end assign data_out=save; endmodule4.6 阈值判断模块为什么需要阈值判断？前面提到，我们在保存权值时将所有参数扩大了 1024 倍（即 $2^{10}$）。这意味着：隐藏层的输出值也被放大了约1024倍；输出层的计算结果同样被放大；原本训练时，输出层ReLU后大于0即判定为目标信号；现在由于数值被放大，不能简单以0为界，需要设定一个等效的阈值。阈值推导：原始判定边界：输出 > 0.5（二分类常用阈值）；放大后等效边界：threshold = 0.5 × 1024 × 1024 = 524288；实际上，由于隐藏层和输出层都放大了1024倍，总放大倍数为 $1024^2 = 1048576$，因此： threshold = 0.5 × 1048576 = 524288。波形图 pmhqXv9.png图片五、关键优化技巧 5.1 归一化的"逆向"处理再次强调这个最重要的优化：处理方式FPGA资源消耗推荐度FPGA内做除法（adc/4095）极高，需除法器IP❌FPGA内用移位近似除法中等，精度损失大△权值预处理（本文方法）零额外消耗✅具体做法：训练时归一化：$V_{\text{in}} = \frac{\text{adc_data}}{4095} \times 1.8$；提取权值时：$w' = \frac{w}{1.8} \times 1024$，取整； FPGA输入：直接使用原始ADC值 $x$（0~4095）；等效运算。 5.2 权值二值化（BWN）降低功耗为了进一步压缩模型、降低功耗，本文采用了 Binary-Weight-Networks (BWN) 对权值进行二值化：权值只取 +1 或 -1；引入缩放因子 α 保证量化后的权值尽可能接近原始浮点权值。二值化后，乘法运算退化为加减法或符号位判断，FPGA资源占用和动态功耗大幅下降。虽然精度略有损失，但在本场景中仍能保持97%以上的识别率。二值化乘法器的Verilog实现： // 二值化权值乘法：只需判断符号 wire signed [31:0] product; assign product = bin_weight ? x_in : -x_in; // bin_weight=1为正，0为负相比32bit×32bit的硬件乘法器，这个逻辑几乎不消耗DSP资源。 5.3 亚稳态消除 ADC数据输入和CS信号是异步信号（相对于16MHz系统时钟），必须做双级触发器同步，防止亚稳态传播： reg adc_dat_d1, adc_dat_d2; always @(posedge clk) begin adc_dat_d1 <= adc_dat; // 第一级 adc_dat_d2 <= adc_dat_d1; // 第二级（稳定后使用） end wire adc_dat_sync = adc_dat_d2;六、实验结果：功耗与性能通过 Actel Libero SOC 对FPGA各模块进行功耗仿真，结果如下：工作模式静态功耗动态功耗总功耗空闲态0.046 mW00.046 mW正常工作0.046 mW2.79 mW2.835 mWFlash*Freeze模式0.115 mW00.115 mW2.835 mW 的总功耗，对于低功耗设备来说是完全可以接受的。各子模块动态功耗分解：串并转换：0.01 mW 隐藏层神经元（含FIFO）：0.083 mW ReLU激活：0.067 mW 输出层神经元：0.067 mW 七、总结与思考本文介绍了一套完整的从算法到硬件的轻量化神经网络部署方案：算法层：针对低功耗约束，设计了512-2-1极简BP网络，避免使用CNN/RNN等重算力模型；数据层：在真实环境中采集目标信号，建立含噪样本库，并通过数据增强提升泛化能力；硬件层：基于Actel低功耗FPGA，用FIFO流水、整数运算、ReLU硬判决、权值二值化等手段，实现了毫瓦级推理；系统层：与射频前端（LNA、包络检波、ADC）紧密配合，形成完整的标签信号检测链路。可扩展性：该FPGA神经网络框架不仅可用于目标信号检测，只需更换训练数据集和权值参数，即可用于FMCW、RFID等其他射频信号的识别，具备良好的通用性。 python和verilog源程序下载

FPGA&ASIC 通信&信息处理机器学习软硬件算法 # ASIC/FPGA # 信号处理 # 机器学习 # 软件算法 # 物联网 # Python

刘航宇 8月1日
0 52 6
基于51/52单片机电容、电感、电阻参数测量系统设计与Proteus仿真摘要：本文介绍了基于51/52单片机的电容、电感、电阻参数测量系统的设计与Proteus仿真。系统采用频率转换法，通过单片机读取频率并计算得到参数值，具有高精度和便于数字化显示的特点。文章详细阐述了系统设计、单元电路设计、程序设计以及仿真调试过程。目录一、设计任务和要求二、方案设计与论证2.1 系统总设计框图 2.2 方案一：电桥平衡原理① 电阻的测量：直流电桥平衡原理 ② 电容的测量：交流电桥平衡原理 ③ 电感的测量：交流电桥平衡原理 2.3 方案二：频率转换法（本设计采用）① 电阻的测量：555 构成单稳态 ② 电容的测量：555 构成单稳态 ③ 电感的测量：电容三点式正弦波振荡 2.4 方案对比与选择三、单元电路设计和参数计算3.1 电阻的检测单元电路设计 3.2 电容的检测单元电路设计 3.3 电感的检测单元电路设计四、总原理图及元器件清单4.1 总原理图 4.2 元器件清单五、程序设计5.1 程序流程图 5.2 核心代码中断函数（频率测量）主函数显示函数键盘检测函数 5.3 完整程序清单及protues仿真文件（附录）六、安装与调试6.1 仿真调试（1）电阻测量电路仿真（2）电容测量电路仿真（3）电感测量电路仿真调试要点液晶显示电路调试仿真整体显示 6.2 实物调试电阻检测电容检测电感检测八、参考文献九、附录-完整软件程序与protues仿真文件完整程序与仿真文件见文章末尾一、设计任务和要求设计并制作一个元器件参数测量仪电阻阻值测量，范围：100Ω ~ 1MΩ 电容容值测量，范围：100pF ~ 10000pF 测量精度：±5% 电感参数的测量扩大量程提高测量精度二、方案设计与论证 2.1 系统总设计框图 pasted_1784990858481_sxzptf.png图片图1 系统总设计框图在测量各元件参数时，采用首先把电感、电容、电阻的参数转化为频率[1]，再送至单片机检测，检测结束后，送至 LCD1602 进行显示。 2.2 方案一：电桥平衡原理 ① 电阻的测量：直流电桥平衡原理 pasted_1784990980814_5yavx3.png图片图2 直流电桥平衡电路图根据电路平衡原理，不断调节电位器 R3，使得电表指针指向正中间，再测量电位器电阻值。 ② 电容的测量：交流电桥平衡原理 pasted_1784991076614_jito75.png图片图3 交流电桥平衡电路图通过调节 Z1、Z2 使电桥平衡。这时电表的读数为零。通过读取 Z1、Z2、Zn 的值，即可得到被测电容的值。 ③ 电感的测量：交流电桥平衡原理 pasted_1784991402619_84r7tl.png图片图4 交流电桥平衡电路图2.3 方案二：频率转换法（本设计采用） ① 电阻的测量：555 构成单稳态 pasted_1784991953296_lg44ir.png图片图5 555 定时器构成单稳态电路图根据 555 定时器构成单稳态，产生脉冲波形，通过单片机读取高低电平得出频率，通过公式换算得到电阻阻值。 ② 电容的测量：555 构成单稳态 pasted_1785027612555_za97df.png图片图6 555 定时器构成单稳态电路图** 根据 555 定时器构成单稳态，产生脉冲波形，通过单片机读取高低电平得出频率，通过公式换算得到电容值。 ③ 电感的测量：电容三点式正弦波振荡 pasted_1785027682239_4u3sw9.png图片图7 电容三点式正弦波振荡电路图由电容三点式正弦波振荡电路得出频率，通过单片机读取高低电平得出频率，通过公式换算得到电感值。 2.4 方案对比与选择对比项方案一（电桥法）方案二（频率法）测量精度受人为调节影响大单片机数字化，精度高操作难度调节麻烦，不易操作自动测量，一键显示电感测量不易测得准确值振荡电路，相对稳定数字化不易数字化便于单片机处理结论：方案二通过单片机读取转化，精确度会明显提高，且便于数字化显示。故本设计选择方案二。三、单元电路设计和参数计算 3.1 电阻的检测单元电路设计 pasted_1785027698225_mjicut.png图片图8 555 定时器构成单稳态电路图由 555 单稳态触发公式： $$f=\frac{1}{\ln2(R_{1}+2R_x)C}$$ 得： $$R_x=\frac{1}{2}(\frac{1}{\ln2fC}-R_{1})$$ 从而，可以计算得出电阻值的大小。 3.2 电容的检测单元电路设计 pasted_1785028035648_x380cp.png图片图9 555 定时器构成单稳态电路图根据 555 定时器构成单稳态，产生脉冲波形，通过单片机读取高低电平得出频率，通过公式换算得到电容值[2]。由： $$f=\frac{1}{\ln2^*(R_1+2R_2)^*C_x}$$ 若 R1 = R2，得： $$C_x=\frac{1}{3\ln2^*f^*R_1}$$ 从而，可以计算得出电容值的大小。 3.3 电感的检测单元电路设计 pasted_1785028091408_lymeeb.png图片图10 电容三点式正弦波振荡电路图由 LC 振荡频率公式： $$f=\frac{1}{2\pi\sqrt{\frac{C_1*C_2}{C_1+C_2}*L_x}}$$ 得： $$L_x=\frac{1}{\left(2\pi f\right)^2\frac{C_1*C_2}{C_1+C_2}}$$ 从而，可以计算得出电感值的大小。四、总原理图及元器件清单 4.1 总原理图 pasted_1785028273962_o8rzuv.png图片图11 电阻、电容、电感参数测试总原理图 pasted_1785028294514_u0wku4.png图片图12 测量电阻、电容部分的原理图 pasted_1785028310991_mmmde2.png图片图13 测量电感以及 ±5V 发生原理图4.2 元器件清单元件序号型号数量备注U1STC89C52RC1单片机R3A103J1排阻R2, R3, R17, R1810KΩ4电位器X111.0592M1晶振C325V, 10uF1电解电容C1, C2, C11103 (0.01uF)3瓷片电容R1, R13, R1810KΩ3电阻J1, J2, J3, J4—4按键U216021液晶A1, A2NE5552555 定时器R4300Ω1电阻R5, R6510KΩ2电阻C4~C9104 (0.1uF)6瓷片电容R7, R9100KΩ2电阻C1050V, 22uF1电解电容Q1~Q3S9108 (NPN)3三极管R102KΩ1电阻R8, R11, R141KΩ3电阻C12, C1350V, 47uF2电解电容R12, R1939KΩ2电阻R15, R1651Ω2电阻C1425V, 470uF1电解电容U3NE555321运放五、程序设计 5.1 程序流程图图14 中断程序流程图 pasted_1785028347463_kh1ui9.png图片图15 主程序流程图 pasted_1785028417008_m02be6.png图片初始化 (led_init, t_init, keyscan) ↓ 清屏 ↓ 循环: ├── 显示频率 display_f(f) └── 根据 a 值分支: ├── case 1: 计算电阻 R，显示 display_R(R) ├── case 2: 计算电容 C，显示 display_C(C) └── case 3: 计算电感 L，显示 display_L(L)5.2 核心代码中断函数（频率测量） void T0_count() interrupt 1 { switch(a) { case 1: // 电阻测量 while(R_out); while(!R_out); TH0 = 0; TL0 = 0; while(R_out); while(!R_out); th0 = TH0; tl0 = TL0; TR0 = 0; break; case 2: // 电容测量 while(C_out); while(!C_out); TH0 = 0; TL0 = 0; while(C_out); while(!C_out); th0 = TH0; tl0 = TL0; TR0 = 0; break; case 3: // 电感测量 while(L_out); while(!L_out); TH0 = 0; TL0 = 0; while(L_out); while(!L_out); th0 = TH0; tl0 = TL0; TR0 = 0; break; } f = 1000000.0 / 1.085069 / (th0 * 256 + tl0) + 0.5; }主函数 void main() { led_init(); // 液晶初始化 t_init(); // 定时器初始化 keyscan(); // 按键检测 write_com(0x01); // 清屏 while(1) { display_f(f); switch(a) { case 1: // 电阻: R = (T/0.693 - 150) 换算 R = (ulong)(5000000.0 / 0.6931472 / f - 150 + 0.5); display_R(R); break; case 2: // 电容: C = 换算公式 C = (int)(100000000.0 / 153 / 0.6931472 / f + 0.5); display_C(C); break; case 3: // 电感: L = 1/(4π²f²C) 换算 L = (int)(1000000000000.0 / 0.1 / PI / PI / f / f + 0.5); display_L(L); break; } } }显示函数 // 频率显示 void display_f(ulong f) { uchar count = 0; ulong f0 = f; while(f) { f = f / 10; count++; } for(num = 5 + count; num > 5; num--) { table2[num] = f0 % 10 + 48; f0 = f0 / 10; } write_com(0x80); for(num = 0; num < 6 + count; num++) { write_data(table2[num]); delayms(5); } } // 电阻显示 void display_R(ulong R) { uchar count = 0; ulong R0 = R; while(R) { R = R / 10; count++; } for(num = 6 + count; num > 6; num--) { table3[num] = R0 % 10 + 48; R0 = R0 / 10; } write_com(0x80 + 0x40); for(num = 0; num < 7 + count; num++) { write_data(table3[num]); delayms(5); } } // 电容显示 void display_C(uint C) { uchar count = 0; uint C0 = C; while(C) { C = C / 10; count++; } for(num = 5 + count; num > 5; num--) { table4[num] = C0 % 10 + 48; C0 = C0 / 10; } write_com(0x80 + 0x40); for(num = 0; num < 6 + count; num++) { write_data(table4[num]); delayms(5); } } // 电感显示 void display_L(uint L) { uchar count = 0; uint L0 = L; while(L) { L = L / 10; count++; } for(num = 5 + count; num > 5; num--) { table5[num] = L0 % 10 + 48; L0 = L0 / 10; } write_com(0x80 + 0x40); for(num = 0; num < 6 + count; num++) { write_data(table5[num]); delayms(5); } }键盘检测函数 void keyscan() { if(key_R == 0) // 检测电阻按键 { delayms(10); // 消抖 if(key_R == 0) a = 1; } else if(key_C == 0) // 检测电容按键 { delayms(10); if(key_C == 0) a = 2; } else if(key_L == 0) // 检测电感按键 { delayms(10); if(key_L == 0) a = 3; } else while(key_R && key_C && key_L); // 等待按键按下 }5.3 完整程序清单及protues仿真文件（附录）见文末附录部分。六、安装与调试 6.1 仿真调试（1）电阻测量电路仿真图16 电阻测量的仿真电路图 pasted_1785028525830_e8xagf.png图片图17 电阻测量的仿真输出波形 pasted_1785028553380_77yjdf.png图片（2）电容测量电路仿真图18 电容测量的仿真电路图 pasted_1785028566386_213kgj.png图片图19 电容测量的仿真输出波形 pasted_1785028577785_fn2fqc.png图片（3）电感测量电路仿真图20 电感测量的仿真电路图 pasted_1785028588732_9bvoyx.png图片图21 电感测量的仿真输出波形 pasted_1785028599631_39ilf2.png图片调试要点接通电源，用示波器观察输出波形，若为方波，则电路焊接无误，否则检查电路[3] 在调试过程中发现，若改变电源电压，输出方波的频率会发生变化，计算出的数值存在一定误差当 VCC 为 3.25V 左右时误差较小液晶显示电路调试将测量电路的输出分别与单片机的 P1^5、P1^6、P1^7 相接，观察液晶是否显示测量结果在调试过程中发现，电阻、电容的测量误差较小由于电容三点式震荡电路的频率不稳定，电感测量的误差较大仿真整体显示图22 电阻测量显示 pasted_1785028620741_10mwwy.png图片图23 电容测量显示 pasted_1785028631102_motyub.png图片图24 电感测量显示 pasted_1785028644198_twwyn4.png图片图25 电源生成模块显示 pm2vEdK.png图片6.2 实物调试实物按照仿真电路搭建，通电显示 "Welcome! RCL detector"。图26 实物开机界面 pm2vmJe.png图片电阻检测插入 2.7KΩ 电阻若显示不准确，调节仿真中 R2 对应的电位器即可改变输出频率，使得检测精准检测显示 2735Ω，可见调试准确图27 电阻检测显示 pm2vnRH.png图片电容检测插入 0.1uF 电容若显示不准确，调节仿真中 R3 对应的电位器即可改变输出频率，使得检测精准检测显示 101pF，可见调试准确[4] 图28 电容检测显示 pm2vuzd.png图片电感检测插入 65mH 电感若显示不准确，调节程序计算公式5，即可改显示结果，使得检测精准检测显示 65535uH，可见调试准确图29 电感检测显示 pm2vMQA.png图片八、参考文献 [1]杨沁佳.浅谈电感传感器微位移检测仪的原理与设计[J].数字通信世界,2019(09):143+159. [2]张璐雅,阮景.一种基于555时基电路的振荡器设计[J].集成电路应用,2019,36(12):12-13. [3]谢琪林.浅谈STC89S51单片机时序[J].电子测试,2020(24):139-140. [4]黄江.基于STM32的高精度电容测量仪设计[J].信息技术与信息化,2020(11):140-141. [5]王晓辉,王智永,韩智伟,胡帅可,谢印庆.基于三极管放大原理的电容三点式LC振荡器的设计[J].电子世界,2020(03):206. [6] E. L. Pankratov. An approach to model manufacturing of an enhanced swing differential Colpitts oscillator based on heterostructures to increase density of their elements with account mismatch-induced stress: on optimization of annealing. 2020, :1-19. 九、附录-完整软件程序与protues仿真文件 // ============================================ // RCL 测量仪程序 // 基于 STC89C52RC + NE555 + LCD1602 // ============================================ #include <reg52.h> #define uint unsigned int #define uchar unsigned char #define ulong unsigned long #define PI 3.1415926 // ========== 字符串常量 ========== uchar code table1[8] = "Welcome! RCL detector"; uchar table2[16] = "f(Hz)="; uchar table3[16] = "R(Ohm)="; uchar table4[16] = "C(pF)="; uchar table5[16] = "L(uH)=";

嵌入式＆系统通信&信息处理软硬件算法 # 嵌入式 # 信号处理 # 软件算法 # 物联网

刘航宇 7月26日
0 39 5
通讯等不确定性条件下设计无人机之间的安全距离摘要：本文针对无人机通信不确定性，提出基于分离原理的安全半径设计方法。通过仿真和实验验证，该方法有效提高了无人机飞行安全性和效率。引用文章：简介 1. 研究问题 2. 分离原理介绍 3. 安全半径设计 4. 仿真及实验验证引用文章： Q. Quan, R. Fu and K. -Y. Cai, "How Far Two UAVs Should Be subject to Communication Uncertainties," in IEEE Transactions on Intelligent Transportation Systems, doi: 10.1109/TITS.2022.3213555. 简介近年来，无人机技术的快速发展使得低空空域中无人机的数量爆炸增长。碰撞避免作为无人机应用的关键技术，近年来人们已经进行了大量研究，设计出各种方法使得无人机在飞行过程中与障碍物保持一定安全距离（本文将该距离称为无人机的安全半径）。然而，在碰撞避免相关研究中，不确定性往往是难以处理的问题。针对不确定性，主流的方法包括对不确定性进行预测，以及在闭环控制中给予补偿。然而，以上方法很依赖于预测及补偿的精准设计，设计不当将有可能导致控制器失效。本研究受地面交通中车辆间安全距离启发，基于对通信不确定性和无人机控制器性能的假设，提出了安全半径设计和控制器设计的原则（本文称为分离原理）。进一步，安全半径具体通常通过经验预先设计，如果设计得过大或过小将分别影响无人机飞行的高效性及安全性。如何根据无人机模型及通信不确定性确定其安全半径下界仍然是悬而未决的问题。利用分离原理，本文研究了设计阶段（无不确定性）和飞行阶段（受不确定性影响）的无人机安全半径设计。最后，通过仿真和实验表明了所提方法的有效性。图片 1. 研究问题本研究中，无人机与障碍物的运动模型均建模为多旋翼模型，换句话说，我们考虑的障碍物可以等效为另一架多旋翼飞行器。对于多旋翼飞行器而言，其可以获得自身以及障碍物的实时位置和速度。为简单描述起见，本文建模均为二维，类似的建模及分析方法可以扩展到三维情况。我们首先建立多旋翼的具体控制模型如下。其中多旋翼的位置和速度分别表示为，速度控制模型建立为一阶惯性环节，其时间常数与无人机的机动性能相关，控制输入为期望速度。在此基础上，本文定义一种新的滤波位置模型如下。多旋翼滤波位置的物理意义是根据多旋翼的当前位置、速度及机动能力，对其运动趋势预测。在此基础上，定义多旋翼的安全区域为以滤波位置为圆心的圆形区域，其半径称为安全半径。对于障碍物，我们类似定义其滤波位置，以及以障碍物滤波位置为圆心的圆形障碍物区域，半径称为障碍物半径。图片进一步，我们针对不确定性做了以下2点假设：（1）无人机和障碍物对自身的三维位置及三维速度估计均存在噪声；（2）无人机在获取障碍物状态信息时，存在通信延迟及丢包。该通信网络模型如下图所示。图片本研究中，丢包模型进一步建模为均值模型，且假设估计噪声、通信延迟、丢包均值模型误差均存在上界且上界已知。其数学定义如下：图片进一步，本文对无人机的控制器性能做出如下假设：（1）在无不确定性的理想状态下，无人机的控制器可以使无人机和障碍物之间的真实距离始终大于给定安全距离；（2）在存在以上不确定性的实际情况中，无人机的控制器可以使无人机和障碍物之间的估计距离始终保持给定安全距离。本研究的具体目标是在不确定性上界已知的条件下计算出无人机安全半径的下界。图片 2. 分离原理介绍无人机在理想状态下设计的控制器中给定的安全半径值，在实际含有不确定性的环境中将转化为估计安全半径；直观上理解，将含有不确定性的无人机与障碍物之间的估计位置误差代替真实位置误差作为反馈时，控制器将难以维持给定的安全半径。本研究中，分离原理具体研究的是不确定性在满足什么条件时无人机的控制器设计和安全半径设计过程可分离，也就是估计安全半径和安全半径相等，成立。分离原理具体数学描述如下：图片分离原理中提出的三个条件包括一个充分必要条件(i)以及两个充分条件(ii)和(iii)。其中，条件(i)为理论推导，在实际中难以得到验证，通常可通过条件(ii)和(iii)进行验证。条件(ii)对无人机速度的限制较宽，该式在障碍物主动躲避无人机的条件下容易达成。反之，条件(iii)对无人机速度的限制较苛刻，要求无人机速度严格大于障碍物速度，适用于在障碍物不主动躲避无人机的情况下。以上两种情况的区别如下图所示。图片 3. 安全半径设计根据上述分离原理的提出，在分离原理满足的前提下，基于无人机的安全半径模型和通信网络模型，可以进一步设计合适大小的无人机安全半径。如前文所述，安全半径设计过大会增加环境的冗余度，设计过小则无法保证飞行过程的安全。在本研究中，给出了在理想情况下以及实际情况下安全半径的下界，分别如下：图片 4. 仿真及实验验证仿真及实验验证在仿真中，我们针对单障碍物、多非合作障碍物、多合作障碍物设计了三种场景来验证我们方法的有效性。在实验中，我们使用DJI tello无人机对以上情况进行测试，结果与我们的理论一致。实验视频： https://youtu.be/LkSDPFGa_1E 论文地址 https://rfly.buaa.edu.cn/pdfs/2022/How_far_two_UAVs_should_be_subject_to_communication_uncertainties.pdf

软硬件算法 # 软件算法

刘航宇 2年前
0 1,049 2
面向对象在编程中的概念摘要：本文介绍了面向对象编程（OOP）的概念，包括其与面向过程的区别、三大特性（封装、继承、多态）和五大基本原则。同时，阐述了OOP的用途和应用领域，如人工智能、企业级应用等。前言那么究竟什么是面向对象呢？面向过程面向对象面向对象的三大特性封装继承多态面向对象的五大基本原则单一职责原则（Single-Responsibility Principle）开放封闭原则（Open-Closed principle）里氏替换原则（Liskov-Substitution Principle）依赖倒置原则（Dependecy-Inversion Principle）接口隔离原则（Interface-Segregation Principle）面向对象编程的用途面向对象编程的应用领域前言在刚接触java、C++、Python语言的时候，就知道这是一门面向对象的语言。学不好java的原因找到了，面向对象的语言，没有对象怎么学 ::(狗头) 图片那么究竟什么是面向对象呢？面向对象，Object Oriented Programming，简称为OOP。说到面向对象，不得不提一嘴面向过程。面向过程面向过程是一种自顶而下的编程模式。把问题分解成一个一个步骤，每个步骤用函数实现，依次调用即可。举个生活中的例子，假如你想吃红烧肉，你需要买肉，买调料，洗肉，切肉，烧肉，装盘。需要我们具体每一步去实现，每个步骤相互协调，最终盛出来的才是正宗好吃的红烧肉。面向对象面向对象就是将问题分解成一个一个步骤，对每个步骤进行相应的抽象，形成对象，通过不同对象之间的调用，组合解决问题。还是你想吃红烧肉这个例子，不过这次不同的是你发现了一家餐馆里有红烧肉这道菜，你要做的只是去点菜，就可以吃到红烧肉。针不戳，针不戳，面向对象针不戳，你不用再去关心红烧肉繁琐的制作流程，就能吃到美味的红烧肉。我们接着往下看图片面向对象的三大特性封装封装就是把客观的事物封装成抽象的类，并且类可以把自己的数据和方法只让可信的类或者对象操作，对不可信的类进行信息的隐藏。简单的说就是：封装使对象的设计者与对象的使用者分开，使用者只要知道对象可以做什么就可以了，不需要知道具体是怎么实现的。封装可以有助于提高类和系统的安全性这里有点像FPGA的IP了，电子人懂！继承当多个类中存在相同属性和行为时，将这些内容就可以抽取到一个单独的类中，使得多个类无需再定义这些属性和行为，只需继承那个类即可。通过继承创建的新类称为“子类”或“派生类”，被继承的类称为“基类”、“父类”或“超类” 多态多态同一个行为具有多个不同表现形式或形态的能力。是指一个类实例（对象）的相同方法在不同情形有不同表现形式。多态机制使具有不同内部结构的对象可以共享相同的外部接口。这意味着，虽然针对不同对象的具体操作不同，但通过一个公共的类，它们（那些操作）可以通过相同的方式予以调用。菜鸟教程中的例子就很形象现实中，比如我们按下 F1 键这个动作：如果当前在 Flash 界面下弹出的就是 AS 3 的帮助文档；如果当前在 Word 下弹出的就是 Word 帮助；在 Windows 下弹出的就是 Windows 帮助和支持。同一个事件发生在不同的对象上会产生不同的结果。面向对象的五大基本原则单一职责原则（Single-Responsibility Principle）简而言之，就是一个类最好只有一个能引起变化的原因，只做一件事，单一职责原则可以看做是低耦合高内聚思想的延伸，提高高内聚来减少引起变化的原因。开放封闭原则（Open-Closed principle）简而言之，就是软件实体应该是可扩展的，但是不可修改。因为修改程序有可能会对原来的程序造成错误。即对扩展开放，对修改封闭里氏替换原则（Liskov-Substitution Principle）简而言之，就是子类一定可以替换父类，子类包含其基类（父类）的功能依赖倒置原则（Dependecy-Inversion Principle）高层次的模块不应该依赖于低层次的模块，他们都应该依赖于抽象。抽象不应该依赖于具体实现，具体实现应该依赖于抽象。依赖于抽象即对接口编程，不要对实现编程接口隔离原则（Interface-Segregation Principle）图片简而言之，就是使用多个小的专门的接口，而不要使用一个大的总接口。例如将一个房子再分割成卧室，厨房，厕所等等，而不是将所有功能放在一起面向对象编程的用途使用封装（信息隐藏）可以对外部隐藏数据使用继承可以重用代码使用多态可以重载操作符/方法/函数，即相同的函数名或操作符名称可用于多种任务数据抽象可以用抽象实现项目易于迁移（可以从小项目转换成大项目）同一项目分工软件复杂性可控面向对象编程的应用领域人工智能与专家系统企业级应用神经网络与并行编程办公自动化系统

编程&脚本笔记 # 软件算法 # C/C++

刘航宇 3年前
0 503 4
2023-11-01
机器学习/深度学习-10个激活函数详解摘要：本文详细介绍了深度学习中常见的十种激活函数，包括Sigmoid、Tanh、ReLU、Leaky ReLU、ELU、PReLU、Softmax、Swish、Maxout和Softplus，并分析了它们的优缺点。图片综述 1. Sigmoid 激活函数 2. Tanh / 双曲正切激活函数 3. ReLU 激活函数 4. Leaky ReLU 5. ELU 6. PReLU（Parametric ReLU） 7. Softmax 8. Swish 9. Maxout 10. Softplus 综述激活函数（Activation Function）是一种添加到人工神经网络中的函数，旨在帮助网络学习数据中的复杂模式。类似于人类大脑中基于神经元的模型，激活函数最终决定了要发射给下一个神经元的内容。在人工神经网络中，一个节点的激活函数定义了该节点在给定的输入或输入集合下的输出。标准的计算机芯片电路可以看作是根据输入得到开（1）或关（0）输出的数字电路激活函数。因此，激活函数是确定神经网络输出的数学方程式，本文概述了深度学习中常见的十种激活函数及其优缺点。首先我们来了解一下人工神经元的工作原理，大致如下：图片上述过程的数学可视化过程如下图所示：图片 1. Sigmoid 激活函数 lofj8ajx.png图片 Sigmoid 函数的图像看起来像一个 S 形曲线。函数表达式如下： $$\[\mathrm{f(z)=1/(1+e^{\wedge}-z)}\]$$ 在什么情况下适合使用 Sigmoid 激活函数呢？ Sigmoid 函数的输出范围是 0 到 1。由于输出值限定在 0 到 1，因此它对每个神经元的输出进行了归一化；用于将预测概率作为输出的模型。由于概率的取值范围是 0 到 1，因此 Sigmoid 函数非常合适；梯度平滑，避免「跳跃」的输出值；函数是可微的。这意味着可以找到任意两个点的 sigmoid 曲线的斜率；明确的预测，即非常接近 1 或 0。 Sigmoid 激活函数有哪些缺点？倾向于梯度消失；函数输出不是以 0 为中心的，这会降低权重更新的效率； Sigmoid 函数执行指数运算，计算机运行得较慢。 2. Tanh / 双曲正切激活函数图片 tanh 激活函数的图像也是 S 形，表达式如下： $$f(x)=tanh(x)=\frac{2}{1+e^{-2x}}-1$$ tanh 是一个双曲正切函数。tanh 函数和 sigmoid 函数的曲线相对相似。但是它比 sigmoid 函数更有一些优势。图片首先，当输入较大或较小时，输出几乎是平滑的并且梯度较小，这不利于权重更新。二者的区别在于输出间隔，tanh 的输出间隔为 1，并且整个函数以 0 为中心，比 sigmoid 函数更好；在 tanh 图中，负输入将被强映射为负，而零输入被映射为接近零。注意：在一般的二元分类问题中，tanh 函数用于隐藏层，而 sigmoid 函数用于输出层，但这并不是固定的，需要根据特定问题进行调整。 3. ReLU 激活函数图片 ReLU 激活函数图像如上图所示，函数表达式如下：图片 ReLU 函数是深度学习中较为流行的一种激活函数，相比于 sigmoid 函数和 tanh 函数，它具有如下优点：当输入为正时，不存在梯度饱和问题。计算速度快得多。ReLU 函数中只存在线性关系，因此它的计算速度比 sigmoid 和 tanh 更快当然，它也有缺点： Dead ReLU 问题。当输入为负时，ReLU 完全失效，在正向传播过程中，这不是问题。有些区域很敏感，有些则不敏感。但是在反向传播过程中，如果输入负数，则梯度将完全为零，sigmoid 函数和 tanh 函数也具有相同的问题；我们发现 ReLU 函数的输出为 0 或正数，这意味着 ReLU 函数不是以 0 为中心的函数。 4. Leaky ReLU 它是一种专门设计用于解决 Dead ReLU 问题的激活函数：图片 ReLU vs Leaky ReLU 为什么 Leaky ReLU 比 ReLU 更好？ $$f(y_i)=\begin{cases}y_i,&\text{if }y_i>0\\a_iy_i,&\text{if }y_i\leq0\end{cases}.$$ 1、Leaky ReLU 通过把 x 的非常小的线性分量给予负输入（0.01x）来调整负值的零梯度（zero gradients）问题； 2、leak 有助于扩大 ReLU 函数的范围，通常 a 的值为 0.01 左右； 3、Leaky ReLU 的函数范围是（负无穷到正无穷）。注意：从理论上讲，Leaky ReLU 具有 ReLU 的所有优点，而且 Dead ReLU 不会有任何问题，但在实际操作中，尚未完全证明 Leaky ReLU 总是比 ReLU 更好。 5. ELU 图片 ELU vs Leaky ReLU vs ReLU ELU 的提出也解决了 ReLU 的问题。与 ReLU 相比，ELU 有负值，这会使激活的平均值接近零。均值激活接近于零可以使学习更快，因为它们使梯度更接近自然梯度。图片显然，ELU 具有 ReLU 的所有优点，并且：没有 Dead ReLU 问题，输出的平均值接近 0，以 0 为中心； ELU 通过减少偏置偏移的影响，使正常梯度更接近于单位自然梯度，从而使均值向零加速学习； ELU 在较小的输入下会饱和至负值，从而减少前向传播的变异和信息。一个小问题是它的计算强度更高。与 Leaky ReLU 类似，尽管理论上比 ReLU 要好，但目前在实践中没有充分的证据表明 ELU 总是比 ReLU 好。 6. PReLU（Parametric ReLU）图片 PReLU 也是 ReLU 的改进版本： $$f(y_i)=\begin{cases}y_i,&\text{if }y_i>0\\a_iy_i,&\text{if }y_i\leq0\end{cases}.$$ 看一下 PReLU 的公式：参数α通常为 0 到 1 之间的数字，并且通常相对较小。如果 a_i= 0，则 f 变为 ReLU 如果 a_i> 0，则 f 变为 leaky ReLU 如果 a_i 是可学习的参数，则 f 变为 PReLU PReLU 的优点如下：在负值域，PReLU 的斜率较小，这也可以避免 Dead ReLU 问题。与 ELU 相比，PReLU 在负值域是线性运算。尽管斜率很小，但不会趋于 0。 7. Softmax 图片 Softmax 是用于多类分类问题的激活函数，在多类分类问题中，超过两个类标签则需要类成员关系。对于长度为 K 的任意实向量，Softmax 可以将其压缩为长度为 K，值在（0，1）范围内，并且向量中元素的总和为 1 的实向量。图片 Softmax 与正常的 max 函数不同：max 函数仅输出最大值，但 Softmax 确保较小的值具有较小的概率，并且不会直接丢弃。我们可以认为它是 argmax 函数的概率版本或「soft」版本。 Softmax 函数的分母结合了原始输出值的所有因子，这意味着 Softmax 函数获得的各种概率彼此相关。 Softmax 激活函数的主要缺点是：在零点不可微；负输入的梯度为零，这意味着对于该区域的激活，权重不会在反向传播期间更新，因此会产生永不激活的死亡神经元。 8. Swish 图片函数表达式：y = x * sigmoid (x) Swish 的设计受到了 LSTM 和高速网络中 gating 的 sigmoid 函数使用的启发。我们使用相同的 gating 值来简化 gating 机制，这称为 self-gating。 self-gating 的优点在于它只需要简单的标量输入，而普通的 gating 则需要多个标量输入。这使得诸如 Swish 之类的 self-gated 激活函数能够轻松替换以单个标量为输入的激活函数（例如 ReLU），而无需更改隐藏容量或参数数量。 Swish 激活函数的主要优点如下：「无界性」有助于防止慢速训练期间，梯度逐渐接近 0 并导致饱和；（同时，有界性也是有优势的，因为有界激活函数可以具有很强的正则化，并且较大的负输入问题也能解决）；导数恒 > 0；平滑度在优化和泛化中起了重要作用。 9. Maxout 图片在 Maxout 层，激活函数是输入的最大值，因此只有 2 个 maxout 节点的多层感知机就可以拟合任意的凸函数。单个 Maxout 节点可以解释为对一个实值函数进行分段线性近似 (PWL) ，其中函数图上任意两点之间的线段位于图（凸函数）的上方。 $ReLU=\max\bigl(0,x\bigr),\mathrm{abs}\bigl(x\bigr)=\max\bigl(x,-x\bigr)$ Maxout 也可以对 d 维向量（V）实现：图片假设两个凸函数 h_1(x) 和 h_2(x)，由两个 Maxout 节点近似化，函数 g(x) 是连续的 PWL 函数。 $$g\bigl(x\bigr)=h_1\bigl(x\bigr)-h_2\bigl(x\bigr)$$ 因此，由两个 Maxout 节点组成的 Maxout 层可以很好地近似任何连续函数。图片 10. Softplus 图片 Softplus 函数：f（x）= ln（1 + exp x） Softplus 的导数为 f ′(x)=exp(x) / ( 1+exp⁡ x ) = 1/ (1 +exp(−x )) ，也称为 logistic / sigmoid 函数。 Softplus 函数类似于 ReLU 函数，但是相对较平滑，像 ReLU 一样是单侧抑制。它的接受范围很广：(0, + inf)。

机器学习 # 机器学习 # 软件算法 # DL/ML

刘航宇 3年前
0 692 0
RFID编码简介摘要：本文介绍了RFID信号编码系统，包括信源编码和信道编码，并详细阐述了多种编码方法，如NRZ、Manchester、RZ、DBP、Miller等，以及选择编码方法时需考虑的因素，如能量来源、检错能力和时钟提取等。信号编码系统包括信源编码和信道编码两大类，器作用是把要传输的信息尽可能的与传输信道相匹配，并提供对信息的某种保护以防止信息受到干扰。信源编码与信源译码的目的是提高信息传输的有效性以及完成模数转换等；信道编码与信道译码的目的是增强信号的抗干扰能力，提高传输的可靠性。常见的编码方法如下图：图片 RFID系统常用编码方法：反向不归零（NRZ）编码曼彻斯特（Manchester）编码单极性归零（RZ）编码差动双相（DBP）编码密勒（Miller）编码和差动编码图片 1、反向不归零编码（NRZ，Non Return Zero）反向不归零编码用高电平表示二进制“1”，低电平表示二进制“0”，如下图所示：图片此码型不宜传输，有以下原因有直流，一般信道难于传输零频附近的频率分量；接收端判决门限与信号功率有关，不方便使用；不能直接用来提取位同步信号，因为NRZ中不含有位同步信号频率成分；要求传输线有一根接地。注：ISO14443 TYPE B协议中电子标签和阅读器传递数据时均采用NRZ 2、曼彻斯特编码（Manchester）曼彻斯特编码也被称为分相编码（Split-Phase Coding）。某比特位的值是由该比特长度内半个比特周期时电平的变化（上升或下降）来表示的，在半个比特周期时的负跳变表示二进制“1”，半个比特周期时的正跳变表示二进制“0”，如下图所示：图片曼彻斯特编码的特点曼彻斯特编码在采用负载波的负载调制或者反向散射调制时，通常用于从电子标签到读写器的数据传输，因为这有利于发现数据传输的错误。这是因为在比特长度内，“没有变化”的状态是不允许的。当多个标签同时发送的数据位有不同值时，则接收的上升边和下降边互相抵消，导致在整个比特长度内是不间断的负载波信号，由于该状态不允许，所以读写器利用该错误就可以判定碰撞发生的具体位置。曼彻斯特编码由于跳变都发生在每一个码元中间，接收端可以方便地利用它作为同步时钟。注： ISO14443 TYPE A协议中电子标签向阅读器传递数据时采用曼彻斯特编码。 ISO18000-6 TYPE B 读写器向电子标签传递数据时采用的是曼彻斯特编码 3、单极性归零编码（Unipolar RZ）当发码1时发出正电流，但正电流持续的时间短于一个码元的时间宽度，即发出一个窄脉冲当发码0时，完全不发送电流单极性归零编码可用来提取位同步信号。 pPbm28I.png图片 4、差动双相编码（DBP）差动双相编码在半个比特周期中的任意的边沿表示二进制“0”，而没有边沿就是二进制“1”，如下图所示。此外在每个比特周期开始时，电平都要反相。因此，对于接收器来说，位节拍比较容易重建。 pPbmR2t.png图片 5、密勒编码（Miller）密勒编码在半个比特周期内的任意边沿表示二进制“1”，而经过下一个比特周期中不变的电平表示二进制“0”。一连串的比特周期开始时产生电平交变，如下图所示，因此，对于接收器来说，位节拍也比较容易重建。 pPbmhKf.png图片 pPbm5qS.png图片 6、修正密勒码编码 7、脉冲-间歇编码对于脉冲—间歇编码来说，在下一脉冲前的暂停持续时间t表示二进制“1”，而下一脉冲前的暂停持续时间2t则表示二进制“0”，如下图所示。 pPbnUoQ.png图片这种编码方法在电感耦合的射频系统中用于从读写器到电子标签的数据传输，由于脉冲转换时间很短，所以就可以在数据传输过程中保证从读写器的高频场中连续给射频标签供给能量。 8、脉冲位置编码（PPM，Pulse Position Modulation）脉冲位置编码与上述的脉冲间歇编码类似，不同的是，在脉冲位置编码中，每个数据比特的宽度是一致的。其中，脉冲在第一个时间段表示“00”，第二个时间段表示“01”，第三个时间段表示“10”，第四个时间段表示“11”，如图所示 pPbnwJs.png图片注：ISO15693协议中，数据编码采用PPM 9、FM0编码 FM0（即Bi-Phase Space）编码的全称为双相间隔码编码、工作原理是在一个位窗内采用电平变化来表示逻辑。如果电平从位窗的起始处翻转，则表示逻辑“1”。如果电平除了在位窗的起始处翻转，还在位窗中间翻转则表示逻辑“0”。 pPbn0Wn.png图片注：ISO18000-6 typeA 由标签向阅读器的数据发送采用FM0编码 10、PIE编码 PIE（Pulse interval encoding）编码的全称为脉冲宽度编码，原理是通过定义脉冲下降沿之间的不同时间宽度来表示数据。在该标准的规定中，由阅读器发往标签的数据帧由SOF（帧开始信号）、EOF（帧结束信号）、数据0和1组成。在标准中定义了一个名称为“Tari”的时间间隔，也称为基准时间间隔，该时间段为相邻两个脉冲下降沿的时间宽度，持续为25μs。 pPbnBzq.png图片注：ISO18000-6 typeA 由阅读器向标签的数据发送采用PIE编码 ============================================= 注：选择编码方法的考虑因素编码方式的选择要考虑电子标签能量的来源在REID系统中使用的电子标签常常是无源的，而无源标签需要在读写器的通信过程中获得自身的能量供应。为了保证系统的正常工作，信道编码方式必须保证不能中断读写器对电子标签的能量供应。在RFID系统中，当电子标签是无源标签时，经常要求基带编码在每两个相邻数据位元间具有跳变的特点，这种相邻数据间有跳变的码，不仅可以保证在连续出现“0”时对电子标签的能量供应，而且便于电子标签从接收到的码中提取时钟信息。编码方式的选择要考虑电子标签的检错的能力出于保障系统可靠工作的需要，还必须在编码中提供数据一级的校验保护，编码方式应该提供这种功能。可以根据码型的变化来判断是否发生误码或有电子标签冲突发生。在实际的数据传输中，由于信道中干扰的存在，数据必然会在传输过程中发生错误，这时要求信道编码能够提供一定程度的检测错误的能力。曼彻斯特编码、差动双向编码、单极性归零编码具有较强的编码检错能力。编码方式的选择要考虑电子标签时钟的提取在电子标签芯片中，一般不会有时钟电路，电子标签芯片一般需要在读写器发来的码流中提取时钟。曼彻斯特编码、密勒编码、差动双向编码容易使电子标签提取时钟。

通信&信息处理 # 通信&射频 # 软件算法

刘航宇 3年前
0 2,595 0
算法-反转链表C&Python实现摘要：本文介绍了如何使用C++和Python实现单链表的反转。文章首先回顾了空间复杂度和时间复杂度的概念，然后分别给出了C++和Python的实现代码，包括初始化指针、遍历链表和反转节点指向的步骤。描述基础数据结构知识回顾题解C++篇题解Python篇描述给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。数据范围： 0≤n≤1000 要求：空间复杂度 O(1) ，时间复杂度 O(n) 。如当输入链表{1,2,3}时，经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。以上转换过程如下图所示： pCqibqO.png图片基础数据结构知识回顾空间复杂度 O (1) 表示算法执行所需要的临时空间不随着某个变量 n 的大小而变化，即此算法空间复杂度为一个常量，可表示为 O (1)。例如，下面的代码中，变量 i、j、m 所分配的空间都不随着 n 的变化而变化，因此它的空间复杂度是 O (1)。 int i = 1; int j = 2; ++i; j++; int m = i + j;时间复杂度 O (n) 表示算法执行的时间与 n 成正比，即此算法时间复杂度为线性阶，可表示为 O (n)。例如，下面的代码中，for 循环里面的代码会执行 n 遍，因此它消耗的时间是随着 n 的变化而变化的，因此这类代码都可以用 O (n) 来表示它的时间复杂度。 for (i=1; i<=n; ++i) { j = i; j++; }题解C++篇可以先用一个vector将单链表的指针都存起来，然后再构造链表。此方法简单易懂，代码好些。 // 定义一个Solution类 class Solution { public: // 定义一个函数，接收一个链表的头节点指针，返回一个反转后的链表的头节点指针 ListNode* ReverseList(ListNode* pHead) { // 如果头节点指针为空，直接返回空指针 if (!pHead) return nullptr; // 定义一个vector，用于存储链表中的每个节点指针 vector<ListNode*> v; // 遍历链表，将每个节点指针放入vector中 while (pHead) { v.push_back(pHead); pHead = pHead->next; } // 反转vector，也可以逆向遍历 reverse(v.begin(), v.end()); // 取出vector中的第一个元素，作为反转后的链表的头节点指针 ListNode *head = v[0]; // 定义一个当前节点指针，初始化为头节点指针 ListNode *cur = head; // 从第二个元素开始遍历vector，构造反转后的链表 for (int i=1; i<v.size(); ++i) { // 当前节点的下一个指针指向下一个节点 cur->next = v[i]; // 当前节点后移 cur = cur->next; } // 切记最后一个节点的下一个指针指向nullptr cur->next = nullptr; // 返回反转后的链表的头节点指针 return head; } };初始化：3个指针 1）pre指针指向已经反转好的链表的最后一个节点，最开始没有反转，所以指向nullptr 2）cur指针指向待反转链表的第一个节点，最开始第一个节点待反转，所以指向head 3）nex指针指向待反转链表的第二个节点，目的是保存链表，因为cur改变指向后，后面的链表则失效了，所以需要保存接下来，循环执行以下三个操作 1）nex = cur->next, 保存作用 2）cur->next = pre 未反转链表的第一个节点的下个指针指向已反转链表的最后一个节点 3）pre = cur， cur = nex; 指针后移，操作下一个未反转链表的第一个节点循环条件，当然是cur != nullptr 循环结束后，cur当然为nullptr，所以返回pre，即为反转后的头结点这里以1->2->3->4->5 举例： pCqAcsP.png图片 pCqAgqf.png图片 pCqAWdS.png图片 pCqA4iQ.png图片 pCqAIRs.png图片 // 定义一个Solution类 class Solution { public: // 定义一个函数，接收一个链表的头节点指针，返回一个反转后的链表的头节点指针 ListNode* ReverseList(ListNode* pHead) { // 定义一个前驱节点指针，初始化为nullptr ListNode *pre = nullptr; // 定义一个当前节点指针，初始化为头节点指针 ListNode *cur = pHead; // 定义一个后继节点指针，初始化为nullptr ListNode *nex = nullptr; // 遍历链表，反转每个节点的指向 while (cur) { // 记录当前节点的下一个节点 nex = cur->next; // 将当前节点的下一个指针指向前驱节点 cur->next = pre; // 将前驱节点更新为当前节点 pre = cur; // 将当前节点更新为后继节点 cur = nex; } // 返回反转后的链表的头节点指针，即原链表的尾节点指针 return pre; } };题解Python篇假设链表为 1->2->3->4->null 空就是链表的尾 obj： 4->3->2->1->null 那么逻辑是首先设定待反转链表的尾 pre = none head 代表一个动态的表头逐步取下一次链表的值然后利用temp保存 head.next 第一次迭代head为1 temp 为2 原始链表中是1->2 现在我们需要翻转即令head.next = pre 实现 1->none 但此时链表切断了变成了 1->none 2->3->4 所以我们要移动指针，另pre = head 也就是pre从none 变成1 下一次即可完成2->1的链接此外另head = next 也就是说把指针移动到后面仍然链接的链表上这样执行下一次循环则实现把2->3 转变为 2->1->none 然后再次迭代直到最后一次 head 变成了none 而pre变成了4 则pre是新的链表的表头完成翻转 # -*- coding:utf-8 -*- # 定义一个ListNode类，表示链表中的节点 # class ListNode: # def __init__(self, x): # self.val = x # 节点的值 # self.next = None # 节点的下一个指针 # 定义一个Solution类，用于解决问题 class Solution: # 定义一个函数，接收一个链表的头节点，返回一个反转后的链表的头节点 def ReverseList(self, pHead): # write code here pre = None # 定义一个前驱节点，初始化为None head = pHead # 定义一个当前节点，初始化为头节点 while head: # 遍历链表，反转每个节点的指向 temp = head.next # 记录当前节点的下一个节点 head.next = pre # 将当前节点的下一个指针指向前驱节点 pre = head # 将前驱节点更新为当前节点 head = temp # 将当前节点更新为下一个节点 return pre # 返回反转后的链表的头节点，即原链表的尾节点

编程&脚本笔记软硬件算法 # 软件算法 # C/C++# Python

刘航宇 3年前
0 388 2
2023-05-15
机器学习代码实现:线性回归与岭回归摘要：本文介绍了线性回归和岭回归的机器学习模型及其代码实现。首先阐述了线性回归模型的基本原理和损失函数，然后展示了如何通过正规方程直接求解参数。接着，详细介绍了线性回归的Python实现，包括fit、predict和loss方法。最后，介绍了岭回归模型，并展示了如何通过增加正则项来控制参数规模，以及如何通过Python代码实现岭回归。1.线性回归模型线性回归模型是最简单的一种线性模型，模型的形式就是： $y=W^T x+b$ 我们可以通过对原本的输入向量x扩增一个为1的维度将参数W和b统一成一个参数W，即模型变成了 $y=W^T x$ 这里的W是原本两个参数合并之后的而其损失函数的形式是残差平方损失RSS $L=\frac{1}{2 m} \sum_{i=1}^m\left(W^T x_i-y_i\right)^2=\frac{1}{2 m}\left(W^T X-y\right)^T\left(W^T X-y\right)$ 我们很容易就可以通过求导得到线性回归模型的关于W的梯度 $\nabla_W L=\frac{1}{m} \sum_{i=1}^m\left(W^T x_i-y_i\right) x_i=\frac{1}{m} X^T\left(W^T X-y\right)$ 这样一来我们就可以通过梯度下降的方式来训练参数W，可以用下面的公式表示 $W:=W-\alpha \frac{1}{m} X^T\left(W^T X-y\right)$ 但实际上线性模型的参数W可以直接求解出，即： $W=\left(X^T X\right)^{-1} X^T y$ 2.线性回归的编程实现具体代码中的参数的形式可能和上面的公式推导略有区别，我们实现了一个LinearRegression的类，包含fit，predict和loss三个主要的方法，fit方法就是求解线性模型的过程，这里我们直接使用了正规方程来解 class LinearRegression: def fit(self, X: np.ndarray, y: np.ndarray) -> float: N, D = X.shape # 将每个样本的特征增加一个维度，用1表示，使得bias和weight可以一起计算 # 这里在输入的样本矩阵X末尾增加一列来给每个样本的特征向量增加一个维度 # 现在X变成了N*(D+1)维的矩阵了 expand_X = np.column_stack((X, np.ones((N, 1)))) self.w = np.matmul(np.matmul(np.linalg.inv(np.matmul(expand_X.T, expand_X)), expand_X.T), y) return self.loss(X, y)predict实际上就是将输入的矩阵X放到模型中进行计算得到对应的结果，loss给出了损失函数的计算方式： def loss(self, X: np.ndarray, y: np.ndarray): """ 线性回归模型使用的是RSS损失函数 :param X:需要预测的特征矩阵X，维度是N*D :param y:标签label :return: """ delta = y - self.predict(X) total_loss = np.sum(delta ** 2) / X.shape[0] return total_loss3.岭回归Ridge Regression与代码实现岭回归实际上就是一种使用了正则项的线性回归模型，也就是在损失函数上加上了正则项来控制参数的规模，即： $L=\frac{1}{2 m} \sum_{i=1}^m\left(W^T x_i-y_i\right)^2+\lambda\|W\|_2=\frac{1}{2 m}\left(W^T X-y\right)^T\left(W^T X-y\right)+\lambda W^T W$ 因此最终的模型的正规方程就变成了： $W=\left(X^T X+\lambda I\right)^{-1} X^T y$ 这里的\lambda是待定的正则项参数，可以根据情况选定，岭回归模型训练的具体代码如下 class RidgeRegression: def fit(self, X: np.ndarray, y: np.ndarray): N, D = X.shape I = np.identity(D + 1) I[D][D] = 0 expand_X = np.column_stack((X, np.ones((N, 1)))) self.W = np.matmul(np.matmul(np.linalg.inv(np.matmul(expand_X.T, expand_X) + self.reg * I), expand_X.T), y) return self.loss(X, y)4.数据集实验这里使用了随机生成的二位数据点来对线性模型进行测试，测试结果如下： image.png图片线性模型测试结果岭回归也使用同样的代码进行测试。

机器学习软硬件算法 # 机器学习 # 软件算法

刘航宇 3年前
0 378 1

317 文章数

569 评论量

关于作者：刘航宇，FPGA工程师，西北大学电子系硕士，有多年西北大学电子通信考研辅导和FPGA与嵌入式项目指导经验

人生倒计时

最新回复

小魏先生
2026-08-26

看看
泽泽
2026-08-22

支持typecho1.3吗
平平淡淡
2026-08-22

不错不错