UOJ Logo ChthollyODT的博客

博客

Steffen's Polyhedron(柔性多面体)

2023-09-16 21:08:48 By ChthollyODT

The location of Steffen's Polyhedron's vertexes is listed as below:

$P_1 = (0, 0, 0)$

$P_2 = (-12, 0, 0)$

$P_3 = (\frac{1}{24}, -\frac{17*\sqrt[2]{287}}{24}, 0)$

$P_4 = (x, r\cos\theta ,r\sin\theta)$

$Note_1$: $x$ and $r$ in $P_4$ can be calculated with the following equation set :

$$ \begin{cases} \left\|P_4-P_1\right\|=5 \\ \left\|P_4-P_2\right\|=10 \end{cases} $$

$P_5$ to $P_7$ can be calculated with the following equation set :

$$ \begin{cases} \left\|P_7-P_6\right\|=10 \\ \left\|P_7-P_5\right\|=5 \\ \left\|P_7-P_3\right\|=12 \\ \left\|P_7-P_2\right\|=12 \\ \left\|P_6-P_5\right\|=12 \\ \left\|P_6-P_4\right\|=12 \\ \left\|P_6-P_1\right\|=10 \\ \left\|P_5-P_4\right\|=11 \\ \left\|P_5-P_2\right\|=10 \\ \end{cases} $$

$P_8$ and $P_9$ can be calculated with the following two equation sets :

$$ \begin{cases} \left\|P_8-P_7\right\|=5 \\ \left\|P_8-P_6\right\|=12 \\ \left\|P_8-P_3\right\|=10 \end{cases} $$

$$ \begin{cases} \left\|P_9-P_6\right\|=12 \\ \left\|P_9-P_3\right\|=10 \\ \left\|P_9-P_1\right\|=5 \end{cases} $$

Finally, the fourteens triangles that are used to make up this Polyhedron is $\triangle{p_1} {p_2} {p_3} , \triangle{p_7} {p_3} {p_2} , \triangle{p_1} {p_4} {p_2} , \triangle{p_2} {p_4} {p_5} , \triangle{p_2} {p_5} {p_7} , \triangle{p_1} {p_6} {p_4} , \triangle{p_4} {p_6} {p_5} , \triangle{p_5} {p_6} {p_7} , \triangle{p_6} {p_8} {p_7} , \triangle{p_6} {p_9} {p_8} , \triangle{p_1} {p_9} {p_6} , \triangle{p_3} {p_7} {p_8} , \triangle{p_3} {p_8} {p_9} , \triangle{p_1} {p_3} {p_9}$

Correctness Proof of RSA Algorithm Decryption

2023-03-03 21:24:30 By ChthollyODT

As we all known $c = m^e (mod\ n)$, so $m \equiv c^d (mod\ n) \equiv m^{ed} (mod\ n) \equiv m(mod\ φ(n)) \equiv m^{kφ(n)+1}(mod\ n)$,so we only need to prove that $m \equiv m^{kφ(n)+1}(mod\ n)$

Divided into two situations:

  1. $m$ and $n$ are mutually prime

By Euler's theorem $m^{φ(n)} \equiv 1 (mod\ n)$ ,so

$m^{kφ(n)} \equiv 1^k (mod\ n)$

$m^{kφ(n)} \equiv 1 (mod\ n)$

$m^{kφ(n)+1} \equiv m (mod\ n)$

  1. $m$ and $n$ are not mutually prime

Let $m < n$, $p$ and $q$ are both prime numbers, which means $m$ is either a multiple of $p$ or a multiple of $q$, and can't be a multiple of both $p$ and $q$ (if it is a multiple of both $p$ and $q$ , then let $m > n$), let $m$ be a multiple of $p$, then $m = cp$, where $c$ is positive, then $gcd(m, q) = 1$, according to Euler's theorem:

$m^{φ(q)} \equiv 1 (mod\ q)$

So

$m^{kφ(q)} \equiv 1 (mod\ q)$

$(m^{kφ(q)})^{φ(p)} \equiv 1^{φ(p)} (mod\ q)$

$(m^{kφ(q)})^{φ(p)} \equiv 1 (mod\ q)$

$m^{kφ(n)} \equiv 1 (mod\ q)$

Therefore, there exists an integer $r$ such that $m^{kφ(n)} = 1 + rq$, multiply both sides by $m = cp$, we can get:

$m^{kφ(n)+1} = m + rcpq = m + rcn$

The result is :

$m^{kφ(n)+1} \equiv m (mod\ n)$

In summary, regardless of whether m and n are mutually prime, RSA can correctly decrypt the message

RSA Algorithm

2023-02-24 19:10:33 By ChthollyODT

请问 $RSA$ 有相关代码支持在已知 $pk = (N, e)$ 和 $ϕ(N)$ 的时候求出 $p q$ 呢?

声源识别Project

2023-01-08 13:06:34 By ChthollyODT

误差相关:

  1. 关于窄带的误差:

  2. 关于宽带的误差:

我在处理这方面时并没有单纯的对宽带进行拆分重组,而是借用了另一种算法 $TDOA$ 来进行大规模的辅助校准。虽然 $TDOA$ 算法运算量相对较小,但其存在着精细度和采样率正相关的不足,因而直接运算会导致极为缓慢的运算,所以采取了一种特殊的方法令其在较小采样率小下也可以保证较高的准度。

  • Q1:为什么不单纯的使用 $MUSIC$ ?
  • A1:分为以下三点:
  • 高分辨率谱估计算法需要获得各个麦克风之间的时空相关矩阵,而只有在信号是平稳的,并且声源和噪声的估计参数是不变的情况下,才可能通过时间平均估计求得麦克风之间的相关矩阵。
  • 高分辨率谱估计算法均假设声波信号为远场平面波信号;
  • 高分辨率谱估计算法主要针对窄带信号提出,在信号为宽带信号时,需要将宽带信号分为多个子带信号,对于每个子带信号分别利用高分辨率算法进行声源定位,最后根据得到的结果计算声源位置。这一方法使得算法复杂度增加,很难实时实现。

  • Q2:那为什么最后还是会有较大的误差呢:

  • A2:正如结果图所示,误差开始很大,到最后逐渐缩小。但会有很明显的周期性回弹,分析,下来一共有如下几个原因:
  • 开始误差大是因为采用了 基于几何方式 求解最优角度 的方法,由于该方法需要比较多的预处理,自然会有极大的延迟,同时这也是造成接下来周期性误差的主要原因。

在此附上另一种 基于子空间搜索算法的代码

[ang1,ang2,LocX,LocY] = SubspaceSearch(rxsignaltmp,Mic_Loc_H,Mic_Loc_L,[25 75],[25 75],1,1,fs);
LocEst1(ii,:) = [ang1,ang2, LocX,LocY,ii*DataNum/fs];

%相关的 function 可在 SubspaceSearch.m 内查询。
  1. 虽然校验算法在宽带上有着极为优越的性能与准度,但由于低采样率还是无法达到最佳效果。与前一条相比,此误差因素较小,且为实际应用(及时性)考虑几乎无法避免。
  2. 绘图所需时间导致结果和校验不同可能会导致极小的偏差,可以忽略不计。 附结果图和算法比对图。 算法比对图 $$算法比对图$$

结果图 $$结果误差图$$

问题与解决

  1. 我们在进行窄带研究时对音频的多种频率有了了解(比如中心频率,截止频率等),这有效的帮助我们解决了初期的基本数据填写问题。
  2. 对于宽带问题,相比于直接解决,将其通过流程图分解为几个小问题是更好的策略。同时我们也学会了不同函数分写在不同的 $.m$ 文件内,这样不仅可以是主文件清晰易懂,而且可以有效处理函数之间相互调用而引起的排列冲突问题。

下面是以 $GCC$ 为例的一个导图: GCC

  1. 对于 $MUSIC$ 函数的分段处理,我们开始想的是直接插入,之后又尝试了双边算数/几何均值,单调拟合的方式,但都收效甚微,尤其是最后一种算法拖慢了 $20\%$ 的运算时间。这一点仍然无法较为优秀的解决。

  2. 宽带的套壳检验似乎可以触发类似于“循环展开”的 $CPU$ 并发,从硬件上增加了效率。(存疑)

拓展:

几种声源识别算法以及分类

到达方向估计

  1. 基于相对时延估计的方法。由于阵列的几何结构,各个阵列接收到的信号都有不同程度的延时,而基于相对时延估计的方法通过互相关、广义互相关($Generalized\ Cross-Correlation, GCC$)或相位差等来估计各个阵列信号之间的时延差,再结合阵列的几何结构来估算声源的方位角信息。

  2. 基于波束形成的方法。该算法通常对阵列的各阵元使用所有角度补偿相位,以实现对目标区域的扫描,然后对各信号进行加权求和,将波束输出功率最大的方向作为目标声源的方向。常见的基于波束形成的声源方位角估计算法有延迟相加($Delay\ and\ Sum, DS$)算法,最小方差无失真响应($Minimum\ Variance\ Distortionless\ Response, MVDR$)算法,可控响应功率相位变换法($Steered\ Response\ Power-Phase\ Transform, SRP-PHAT$)等。

  3. 基于信号子空间的方法。这类算法一般可以分为相干子空间方法和非相干子空间方法,在非相干子空间算法中,最经典的算法为多信号分类($Multiple\ Signal\ Classification, MUSIC$)算法,其思想是将信号的协方差进行特征提取,利用特征向量构建信号子空间和噪声子空间,再将噪声子空间构建高分辨率空间谱。由于声源信号是宽带信号,可以对声源信号使用傅立叶变换分解成多个窄带信号,再对每个窄带利用$MUSIC$算法定位,将各窄带估计得结果加权组合得宽带方位估计。而相干子空间方法是将窄带信号汇聚到某一参考频率,从而采用窄带子空间处理方法进行方位估计。

  4. 基于模态域的方法。上述方法皆是阵元域的处理方法,而模态域的一大特性是其波束和导向矢量的频率无关,依据此可以设计出具有低频指向型的波束形成器,也可以降低阵元域波束扫描的频点数。模态域的处理方法与阵元域相比,其波束形成多出一步模态展开的操作,模态展开可通过傅立叶变换实现,展开后的每阶模态都有与之对应的空间特征波束,对应于特定的波束响应,可以看作是组合成期望波束响应的一组基。理论上来讲,只要模态展开的阶数足够高,理论是可以组合逼近成任意的波束。模态域的方法目前应用在球型阵列和环型阵列上有比较好的结果。

  5. 基于机器学习(或深度学习)的方法。与传统基于模型的方法相比,基于机器学习的方法是数据驱动的,甚至无需定义传播模型。基于机器学习的方法将声源定位看作是一个多分类或者线性回归问题,利用其非常强的非线形拟合能力,直接将多通道数据特征映射成定位结果。基于机器学习的方法主要也发展成了两种方向,即基于网格的方法和无网格的方法,这两种方法在定位精度和估计声源个数上各有优势。

距离估计

与$DOA$估计相比,声源距离的估计研究起步较晚。在得到$DOA$估计结果后,声源被定位在了由传声器和捕获信号之间的双曲线内,若采用多个传声器阵列对源信号进行$DOA$估计,则可通过每个传声器阵列的双曲线交点对声源进行定位。然而,该方法并不适用于远距离测距,许多研究也停留在室内的短距离声源测距上。

在室内条件下,当声源距离发生变化时,来自反射声的能量(如室内混响漫射声场)可以假定是保持不变,而来自直达声的能量会发生变化。这两种能量的比值被称为直达混响比($Direct-to-Reverberant\ ratio, DRR$),该比值与声源距离的估计密切相关。理论上,信号的$DRR$可以通过声源到达传声器的房间冲激响应函数($Room\ Impulse\ Responses, RIRs$)直接计算出。但声源距离的估计受多方因素的影响(如$RIRs$未知,近场与远场模型不匹配,混响能量会因距离的改变而改变等),这些方法并不成熟,无法得到很好的应用。

算法评价指标

针对DOA估计和距离估计的方法,需要依靠一些指标来衡量声源定位的性能,常见的评价指标如下:

  1. 平均误差($Average\ error$)。它衡量的是估计的误差,通常将估计值与真实值进行比较,将这些值的平均差异表现出来。具体实现的方法包括绝对误差、均方误差、均方根误差和最大误差等。

  2. 准确率($Accuracy$)。这个指标通常用于$DOA$估计,我们假定如果估计值在真实值一定的误差范围内,则认定该估计是正确的,否之,认定为错误。它衡量了多少比例的检测是正确的。

  3. 查准率($Precision$)、查准率($Recall$)和F1分数($F_1-score$)。这些指标在机器学习分类任务中比较常见的。针对估计一个声源的位置,如果估计正确,则称为真正例($True\ positive$);如果估计错误,则称为假反例($False\ negative$)。假设该位置没有声源,如果估计的结果也是没有,则称为真反例($True\ negative$);如果估计的结果是有声源,则称为假正例($False\ positive$)。查全率衡量所检测正确的声源位置个数占所有声源的比例;查准率衡量所估计到的声源位置中,有多少位置估计是正确的比例。一般来说,查准率和查全率呈负相关关系,而$F_1$分数为这两个指标的调和平均,提供它们之间的平衡。

  4. 声源的数量(Number\ of\ sources)。该指标衡量所能估计到声源的数量,而不在乎声源的具体位置。

  5. 还有一些其他的性能指标,如将某声源定位方法用在语音识别、声源分离、语音拾取任务的预处理,上述任务依赖于声源定位的效果,通过这些任务的性能表现来间接评价声源定位的性能。

未来展望

在过去几十年里,声源定位领域有了巨大的发展,很多问题都得到了解决。例如,在半个世纪以前,研究人员认为声源定位在噪声和混响的条件下,其鲁棒性非常差,认为这个问题几乎不可能解决,但现在很多针对声源定位方法也正是基于噪声和混响条件下的研究,性能也得到很好的改善。目前的方法也存在如上一节所述的局限性,而且在声源定位中,仅依靠音频信号对距离进行估计的研究方法效果较差,但如今的趋势表明,这些研究问题正不断得到解决。

检验(TDOA)算法相关公式:

  1. 波动方程 $$ν^2x(t,r) - \frac{1}{c^2} \frac{{x'(t,r)}^2}{{t'}^2} = 0$$ $$Laplace\ operator, r = [x,y,z]^T$$ $$x(t,r) = A e^{j(ωt-k.r)}$$ $$k = \frac{2pi}{λ}[sinψcosθ, sinψsinθ, cosψ]$$ $$λ = \frac{c}{f}$$

Circle

  1. 麦克风阵列 $$D(f,θ,ψ) = \sum_{m=0}^{M-1}ω_m(f)e^{jkmdsinψcosθ}$$ $$ψ_m(f) = -kmdsin'ψcos'θ(When\ get\ the\ max\ number)$$

  2. 空间采样定理 $$F_s \geq 2F_{max} = \frac{2sinψcosθ}{λ_{min}}$$ $$F_s = \frac{1}{d}$$ $$d \leq \frac{λ_{min}}{2}$$

  3. 噪音模型 $$x_i(n) = h_i(n) * s(n - τ_i) + v_i(n) = α_is(n - τ_i) + \sum_{p=1}^{inf}α_is(n - τ_i) + v_i(n)$$

  4. GCC kJkIC.png kJWyE.png kJ0GP.png GCC

  5. 详细复杂度比较 Algorithm

求助(遗传算法)

2022-09-22 17:54:18 By ChthollyODT

请问大佬们有推荐的讲遗传算法的文章吗?

还有大佬们有推荐的关于 GA 的题目吗?QWQ

ChthollyODT Avatar