计算机入门学习笔记（一）
我全程摸鱼，妈的计入门杀我。
Lecture 1
- a bit is 0-1 digit
- a byte = 8 bit (memory cell unit)
- a word = 32 byte / 64 byte nowadays
- 1 KB = 1024 bytes
逻辑门
与，或，非可以表示出所有的布尔函数。也就是说对于函数 \(f \colon \;\; \{0, 1\}^n \to \{0, 1\}\) ，总存在仅使用与或非三个运算的关于 \(a_1, a_2, \ldots, a_n\) 的有限的表达式可以表示出函数 \(f\) 。
具体构造方式略。
更简单地，NAND 和 NOR 两个运算就可以表示出所有的布尔函数。
加法器
1 bits adders (half adder, full adder).
ripple-carry adder.
减法器
Shifters
乘法器 = 加法器 + Shifters
补码表示
Lecture 2
锁存器 SR latch
D latch
Master-slave D filp-flop
multiplexer
demultiplexer
Lecture 11. Fourier Transform and DCT
傅立叶变换是时域上的信号函数 (time domain) 到频域上的信号函数 (frequency domain) 的转换。
信号函数 \(f\) 周期为 \(T\) 且每个周期黎曼可积，其写作傅立叶级数 (Fourier series) 的形式为
\[ f(t) = \frac{a_0}{2} + \sum_{n=1}^{\infty}(a_n \cos(n \omega t) + b_n \sin(n \omega t)) \]
其中角速度 \(\omega = \frac{2\pi}{T}\) 。
对于 \(n, m \in \mathbb{N}\) ：
\[ \int_0^T \cos(n \omega t) dt = \int_0^T \sin(n \omega t) dt = 0 \]
\[ \int_0^T \cos^2(n \omega t) dt = \int_0^T \sin^2(n \omega t) dt = \frac{T}{2} \]
\[ \int_0^T \cos(n \omega t) \sin(m \omega t) dt = 0 \]
\[ \int_0^T \cos(n \omega t) \cos(m \omega t) dt = \int_0^T \sin(n \omega t) \sin(m \omega t) dt = \delta_{nm} \frac{T}{2} \]
即 \(\{1, \cos(n \omega t), \sin(n \omega t)\}\) 构成了一个正交基。由此计算 \(\int_0^T f(t) dt, \int_0^T f(t) \cos(n \omega t) dt, \int_0^T f(t) \sin(n \omega t) dt\) 可以最终得到
\[ a_0 = \frac{2}{T} \int_0^T f(t) dt \]
\[ a_n = \frac{2}{T} \int_0^T f(t) \cos(n \omega t) dt \]
\[ b_n = \frac{2}{T} \int_0^T f(t) \sin(n \omega t) dt \]
傅立叶级数的另一个形式是
\[ f(t) = \frac{a_0}{2} + \sum_{n=1}^{\infty} c_n \cos(n \omega t + \varphi_n) \]
其中 \(c_n = \sqrt{a_n^2 + b_n^2}, \varphi_n = \arctan(-\frac{b_n}{a_n})\) 。
根据欧拉公式 (Euler's formula) 有 \(e^{ix} = \cos x + i \sin x\) 。同时 \(z = x + i y = |z| \exp(i \arctan(\frac{y}{x}))\) 。
傅立叶级数的另一个形式是
\[ f(t) = \sum_{n=-\infty}^{\infty} (F_n \cos(n \omega t) + i F_n \sin(n \omega t)) = \sum_{n=-\infty}^{\infty} F_n \exp(i n \omega t) \]
其中 \(F_n = \frac{a_n}{2} - i \frac{b_n}{2}, F_{-n} = \overline{F_n}\) ，进一步地有
\[ F_n = \frac{1}{T} \int_0^T f(t) \exp(-i n \omega t) dt \]
根据周期性还可以得到
\[ F_n = \frac{1}{T} \int_{-\frac{T}{2}}^{\frac{T}{2}} f(t) \exp(-i n \omega t) dt \]
上面给出了频域离散的情况，在 \(T \to +\infty, \omega \to 0\) 上便可以推广到连续的频域，
\[ F(\omega') = F(n \omega) = \lim \frac{F_n}{\omega} = \frac{1}{2\pi} \int_{-\infty}^{+\infty} f(t) \exp(-i \omega' t) dt \]
\[ f(t) = \lim \sum_{n=-\infty}^{\infty} \omega F(\omega') \exp(i n \omega t) = \int_{-\infty}^{+\infty} F(\omega') \exp(i \omega' t) d\omega \]
另一种形式为
\[ F(\omega) = \frac{1}{\sqrt{2\pi}} \int_{-\infty}^{+\infty} f(t) \exp(- i \omega t) dt \]
\[ f(t) = \frac{1}{\sqrt{2\pi}} \int_{-\infty}^{+\infty} F(\omega) \exp(i \omega t) d\omega \]
离散傅立叶变换 (discrete Fourier transform, DFT) 的形式为
\[ \begin{aligned} X_n &= \sum_{k=0}^{N-1} x_k e^{-i 2 \pi n k / N} \\ x_n &= \frac{1}{N} \sum_{k=0}^{N-1} X_k e^{i 2 \pi n k / N} \\ \end{aligned} \]
令 \(\omega = \exp(i 2 \pi / N)\) ，可知傅立叶矩阵 \((M_N)_{jk} = \omega^{-jk}\) 的逆为 \((M_N^{-1})_{jk} = \frac{1}{N} \omega^{jk}\) 。
离散余弦变换 (discrete cosine transform, DCT) ，略。