Question

Signal

讯号是一连串的数字。分为两种，离散和连续。

对于数学家来说，就是一维数列（离散）、一维函数（连续）。对于讯号学家来说，就是数位讯号（离散）、类比讯号（连续）。“讯号”只不过是一个比较亲民的词彙而已。

Signal Reconstruction

Signal Reconstruction

讯号重建。找到原本波形。其实就是找到内插函数。

数列通常很长。如果採用多项式内插，那麽内插函数必须是非常高次的多项式。然而，非常高次的多项式，有剧烈震盪的现象，无法平顺的符合资料，称做“ Runge's Phenomenon ”。

数列通常取自真实世界、源自物理现象。例如声音讯号，是由不同频率的波，叠加而成的。详见“ 傅立叶转换 ”。

由于上述两点，因而衍生了其他内插演算法。

Signal Resampling

讯号重新取样。改变疏密程度，重新求得数值。变密称做 upsampling、变疏称做 downsampling。也有人把变密称做 interpolation、变疏称做 decimation。

首先重建讯号，找到内插函数。代入新位置，求得新讯号。

演算法（Triangle Interpolation）（Linear Interpolation）

三角波，等价于线性内插。不切实际，但是算得快。

演算法（Sinc Interpolation）

方波函数，实施逆向傅立叶转换，频域转时域（反过来也行），就是 sinc 函数。如果频域只有特定几个频率有方波（理想中是无限薄的脉衝，但是实际上是有点厚的方波），那麽时域採用 sinc 函数，最理想不过了。算得极慢。

演算法（Lanczos Interpolation）

http://en.wikipedia.org/wiki/Lanczos_resampling

加强版。自由调整胖瘦。砍掉绵延的小波，只留主要的部分。

演算法（Mitchell-Netravali Filter）

http://de.wikipedia.org/wiki/Mitchell-Netravali-Filter

加强版。改用三次多项式函数模拟之。算得快。

Signal Estimation

Signal Estimation

讯号估计。找到讯号的规律。其实就是找到迴归函数。迴归函数是递迴函数、週期函数等等具有规律的函数。

误差设定成“ 均方误差 Mean Squared Error ”：平方误差，再除以数列长度；即是平方误差的平均值。如此一来，长度不同的数列，得以互相比较误差大小。

Signal Prediction

讯号预测。讯号有某种规律，请预测接下来的讯号。

首先估计讯号，找到迴归函数。代入新位置，求得新讯号。

演算法（Linear Prediction）（Linear Predictive Coding）

Linear Regression 是用线性函数符合资料，Linear Prediction 是用线性递迴函数符合资料。演算法请参考往后的 Filter 章节。时间複杂度 O(N^2)，在频域计算可加速为 O(NlogN)。

求得线性递迴函数之后，欲预测下一个新讯号，直接代入最后 K 个旧讯号即可。时间複杂度 O(K)，K 是线性递迴函数的项数。

求得线性递迴函数之后，欲预测第 M 个新讯号，共有四种演算法，请参考“ Linear Recurrence ”。时间複杂度 O(K^2 * logM)，在频域计算可加速为 O(KlogK * logM)。

Signal Separation

Signal Separation

讯号分离。许多道讯号叠合在一起，请分离出原始讯号。

演算法（Independent Component Analysis）

请参考“ Independent Component Analysis ”。

演算法（Discrete Fourier Transform）

请参考“ Fourier Transform ”。

Signal Representation

Karhunen-Loève Transform（Hotelling Transform）

Principal Compoment Analysis，数据是一道讯号。就这样。

请参考“ Principal Component Analysis ”。

Floating Signal

Floating Signal

先前曾经介绍浮动数字。数学家命名为“随机变数 random variable”，然而一点也不随机。

经典的随机变数：

uniform random variable
binomial random variable
Gaussian random variable
Poisson random variable

此处介绍一连串的浮动数字，也就是浮动数列。分为两种，离散和连续。数学家命名为“随机数列 random sequence”和“随机过程 random process”，然而一点也不随机。

经典的随机数列和随机过程：

Gaussian process：每个随机变数都是高斯分布，每个随机变数组合都是多维高斯分布。
Wiener process：高斯过程的积分。就是“布朗运动”。
Markov process：以先前几个随机变数的数值，决定下一个随机变数。

Random Signal

Random Signal（Noise）

随机讯号，通常称作“杂讯”或“噪讯”，没人称作“乱讯”。

古代数学家没有仔细区分“乱：无规矩”和“浮动：有规矩”的差别，把两者都命名为随机，混淆视听。大家搞不清楚状况的情况下，大家一直没有深入研究杂讯的演算法。

将就的方式是 1D Random Number。然而数字一轮一轮循环，很蠢。

将就的方式是将 2D Random Number 投影到一维。然而没有任何理论根据，纯粹凭感觉。

个人认为应该考虑三个面向：无法预测（齐乱）、均匀分布（聚散）、相近数字不接连出现（地序）。

由于没人研究杂讯，大家只好援引浮动数列，以描述杂讯。

例如“ White Gaussian Noise ”：高斯随机数列，每个随机变数的平均数（浮动中心）和变异数（浮动范围）均相同。因为刚好是白杂讯，所以名称裡面有白。

Random Signal 的频谱

http://en.wikipedia.org/wiki/Colors_of_noise

数学家仿照光谱由红到紫的特性，尝试分类杂讯。

 white: 强度为常数
  grey: 强度符合人类听觉曲线。（不那麽白）
   red: 强度正比于频率倒数平方。　　以频率对数为座标轴，渐减 6dB。
  pink: 强度正比于频率倒数。　　　　以频率对数为座标轴，渐减 3dB。（不那麽红）
violet: 强度负正比于频率倒数平方。　以频率对数为座标轴，渐增 6dB。
  blue: 强度负正比于频率倒数。　　　以频率对数为座标轴，渐增 3dB。（不那麽紫）

Smooth Random Signal（Smooth Noise）

http://lodev.org/cgtutor/randomnoise.html

http://www.iquilezles.org/www/articles/warp/warp.htm

计算学家运用“ 内插 ”，制造柔顺的杂讯。网路上已有详细教学文章，请读者自行参考。

“ value noise ”：等距设置随机数值，内插得到其馀数值。内插是为了制造绵延感。

“ perlin noise ”：柔顺绵延，有点规律又不失随机。演算法的每个步骤，好像有道理、又好像在鬼扯，非常奇葩。

“ fBm noise ”：叠加各种解析度（频率）的杂讯，更细腻、更自然。解析度是 2 的各种次方。杂讯可以是上述任意一种。隐含混沌与碎形的概念。

“ wavelet noise ”：叠加各种频率暨振幅的波。类似 fBm noise。

Filter

Filter

输入是一串数列，输出是一串数列，数列到数列的函数，称做“滤波器”。

每个输出变数分开来看，滤波器其实是由许多函数组成。

简单的例子是每项加 1 的滤波器、每项延迟 1 时刻的滤波器。

当全部函数都相同，仅仅索引值不同，可以简化成一个函数。

Linear Time-Invariant Filter（LTI Filter）

滤波器由全部相同的线性函数构成。

LTI Filter 等价于多项式乘法、摺积，容易计算。

LTI Fliter 通常写成线性组合形式

数列 x，经过 LTI 滤波器 h，得到数列 y：
y(n) = h(0)x(n) + h(1)x(n-1) + h(2)x(n-2) + ... + h(p)x(n-p)

Linear Filter 可以写成矩阵形式

[ h(0) 0    0    0 ... ]
[ h(1) h(0) 0    0 ... ]
[ h(2) h(1) h(0) 0 ... ]
[        :             ] [ x(0) ]   [ y(0) ]
[ h(p-1)~h(0) 0 0  ... ] [ x(1) ]   [ y(1) ]
[ h(p)~h(0) 0 0 0  ... ] [ x(2) ] = [ y(2) ]
[ 0 h(p)~h(0) 0 0  ... ] [   :  ]   [   :  ]
[ 0 0 h(p)~h(0) 0  ... ] [ x(n) ]   [ y(n) ]
[         :            ]
[ ...  0 h(p)~h(0) 0 0 ]
[ ...  0 0 h(p)~h(0) 0 ]
[ ...  0 0 0 h(p)~h(0) ]
           A                 x          y

数列看做向量，就可以写成矩阵形式。好处如下：

一、套用矩阵运算的技巧。例如一连串的 LTI Filter，得以複合成单一一个 LTI Filter！

二、援引线性代数进行分析。例如计算 eigenvector，以找出不受 LTI Filter 影响的数列！

LTI Fliter 可以写成摺积形式

{ x(0) x(1) x(2) ... x(n) } dot { h(0) 0    0    ... } = y(0)
{ x(0) x(1) x(2) ... x(n) } dot { h(1) h(0) 0    ... } = y(1)
{ x(0) x(1) x(2) ... x(n) } dot { h(2) h(1) h(0) ... } = y(2)
            :                              :               :
{ x(0) x(1) x(2) ... x(n) } dot { ... h(2) h(1) h(0) } = y(n)
-----------------------------------------------------------------
{ x(0) x(1) x(2) ... x(n) } dot { ... h(3) h(2) h(1) } = y(n+1)
{ x(0) x(1) x(2) ... x(n) } dot { ... h(4) h(3) h(2) } = y(n+2)
            :                              :               :
{ x(0) x(1) x(2) ... x(n) } dot { ...  0 h(p-1) h(p) } = y(n+p-1)
{ x(0) x(1) x(2) ... x(n) } dot { ...  0 0      h(p) } = y(n+p)

            x           convolution       h            =   y

数列末端，增加多馀项次，就可以写成摺积形式。好处如下：

一、援引多项式进行分析。例如当 LTI Filter 的多项式函数图形，没有无限大、无限小的尖峰，那麽此 LTI Filter 一定是 moving average model。

二、援引傅立叶转换进行分析，时域循环摺积等于频域乘法。

LTI Fliter 的三个基本问题

x pass h = ☐
x pass ☐ = y
h

三个问题都有时域和频域两种解法。儘管频域解法的时间複杂度较低，但是没人使用频域解法！一来滤波器长度通常很短，实施傅立叶转换反而浪费很多时间；二来滤波器无法完美转换到频域。

x pass h = ☐

时域。滑动视窗的加权平均值，非常简单。时间複杂度 O(XH)，或者简单写成 O(N^2)。

频域。数列补零，摺积改作循环摺积，时域循环摺积就是频域乘法。运用快速傅立叶转换或快速数论转换，时间複杂度 O(XlogX + HlogH)，或者简单写成 O(NlogN)。

Circuit（Under Construction!）

Resistor-Capacitor Circuit（RC Circuit）

low-pass filter

high-pass filter

Resistor-Inductor-Capacitor Circuit（RLC Circuit）

sine wave

Controller

PID controller

SMC controller

Transfer Function

Modulation

A2A: AM FM
D2A: ASK FSK PSK
A2D: PAM PWM PPM PCM
D2D: coding theory
http://www.hightech.tw/index.php/2012-06-06-14-12-38/25-comm-network
http://www.hightech.tw/index.php/2012-06-06-14-12-38/27-wireless-communication

Multiplexing

Fuzzy Logic

把布林数的 AND 和 OR 运算，变成函数的 min 和 max 运算。

Karnik-Mendel algorithm