本想在寒假期间写点什么的…无奈域名出了点问题…
导致这一个半月里面网站一直处于无法访问的状态…
想起以前积累的计算几何模板…想差不多可以整理下发出来…
不过充斥着define…以及define的奇怪用法…可以说完全是C语言风格的代码…
总之这是一个基于数组和define而不是类和template的模板…会有人看吗…
如果每段代码都注解出一步步怎么得到的话…工程浩大…
结果心血来潮…给几乎每段代码画了个图片…
蓝色是已知,红色是所求…
画了几个才发现…有些还真难用图片表达啊…
那么就开始吧…
这个月几乎都在搞保研的事情…结果没拿到资格…算了…也算经历过了…
心血来潮想搞搞FFT玩玩…
虽然在数字信号处理课上有比较详细的讲过…不过是基2的,对于不是2^N点的FFT只能补零吗…
本来是想做做图像的FFT看看…但是图像的边不是2^N点的…而且补零可能也不方便…做滤波估计还会被补的0影响…
不管怎么样…还是先看看基2的FFT怎么做吧…
稍微看了下Wiki上的…貌似还有不少别的方法的FFT…
还是先看看经典的Cooley Tukey算法吧…
离散傅立叶变换的定义式大约是这个样子的
这里用W方便表示,W(a,n)表示极角是a/n个360度的角度,这里关于角度的性质W也有
作为例子,展开个n=8的情况
为了计算右边那一列n个数,直接算要n^2级别的计算量
现在将黄色和绿色的部分分别取出来
X_e和X_o分别是原数列的偶数项和奇数项的离散傅立叶变换,递归的子结构出现了
放到原式中就变成了
这样,只要分别计算出X_e和X_o并附加2*n级别的计算量,就能完成原本要n^2级别的计算量才能完成的运算了
不过毕竟是最基础的方法…代码的运行效率还有很多优化的余地
虽然说是基2的,但是实际上只是个特例
实质上这个方法并不是对分成2份才有效
比如以n=6作为例子,既可以分成2份:
也可以分成3份:
而且依然满足递归的子结构的要求
也就是,n=a*b的情况下,可以分成a份,计算a个长度为b的子序列的离散傅立叶变换值,附加a*n的级别的运算量,就可以完成n点的离散傅立叶变换了
这样,对任意的n都可以做快速傅立叶变换了:分解质因数
可惜n是质数的时候,貌似只能用定义式了…
基2,4,8的情况下,在代码级别上还可以有很好的优化
因为这时会让中间很多步骤中有关W的复数运算简化很多,不用复数乘法,而用实部虚部做较少的加减法来完成
浮点数真是功不可没啊…用很小的精度代价让一个浮点数包含了原序列每个数的一部分信息…就像全息照相一样呢…
最近在看Objective-c
虽说是c语言扩展出来的…可是这里面的对象甚至类本身却是动态的…
查了下貌似这叫反射?
倒是和不少脚本型的语言很像…
了解下语法之类的可以看看这里(这篇东西同时有中文版),Wiki上还有些和C++的对比
一点点看下来,一开始还没什么,感觉只是语法变了下
嗯…#include变成#import
创建类用@interface,还可以继承,不过只能继承一个父类
objective-c的方法名很有特点…并不是完整名称后面跟参数列表…而是两者交织起来…
虽然这样打字可能要多些(没有带提示功能的编辑器的话,很吃力…),但是阅读起来更加明晰,不会出现忘记第几个参数是什么作用的情况了
实现类在@implementation块内写
这里就有些舒服了,方法名直接复制到对应的implementation块中就可以开始写方法的内容了
用C++的时候,要把成员函数的声明复制过来,然后在返回类型和函数名之间加上”类名::”的东西,感觉很麻烦呢…
this变成了self,要调用父类的方法而自身却重载过了这个方法时,可以对super调用方法
用-的是对象的method,用+的是类的method,后者相当于C++的静态成员函数
id类型是万能的对象,就像void*,对id对象可以调用任何方法,只要它的本体有这个方法就可以,没有的话…就会产生异常
看到后面感觉越来越玄乎…难道一个对象里存了一个方法列表,并且方法名和参数类型都有吗?…
事实上就是这样没错…一个对象指针所指的是个这样的结构体(摘自objc.h)
typedef struct objc_object {
struct objc_class* class_pointer;
} *id;
实际对象在这个基础上后面还会跟上它的成员变量…
而这个objc_class呢,则是这样的结构(摘自objc.h)
struct objc_class {
MetaClass class_pointer; /* Pointer to the class’s
[...]
话说有快一个月没有写点什么了…
这段时间里也发生了各种事…
其中一个是EDA课程的大作业(用VHDL设计洗衣机芯片)…deadline是在7月9日(周五)…
而期末考试是在7月5日,7月7日,7月9日…EDA大作业心血来潮赶着在7月7日的时候就做好交了…不过也庆幸没有往后拖…
因为后来得了胃炎…7月9日的考试时真是煎熬啊…胃很难受,又饿着肚子又反胃…
EDA这门课结束了…VHDL语言的东西也不知道以后还会不会接触…写点什么纪念下吧…
VHDL是一种硬件描述语言…比如用来编写各种芯片…
课上用的环境是maxplus II…不过貌似落伍了?…
编写硬件真是和编写软件差很多…
基本上,VHDL中每条语句之间都是并发的,软件则是顺序执行的(当然多核多线程下可能有真正意义上的并发)…
因为软件每条指令背后都有个cpu时钟…指令之间有着先后顺序…
而VHDL则是用最基本的门电路构建一个从输入到输出的逻辑关系…不计信息传播速度的话,输出只在输入改变的时候改变…
那么…先说下VHDL的几个够用的语法吧…
首先,和C++中#include语句类似的是library
LIBRARY IEEE;
话说到现在也没太搞明白library后面跟的东西是从什么文件夹里找的…
vhdl中use是类似C++中的using的东西
USE IEEE.STD_LOGIC_1164.ALL;
USE IEEE.STD_LOGIC_UNSIGNED.ALL;
就像using namespace std;一样平常…
恩…对应C++的namespace的话应该是package了吧…
不过…我没有用过namespace,也没有用过package…不用管这些也挺够用的…
然后是元件(实体)的定义…一段vhdl程序就是用来做成一个元件的…就像C++中一个函数(感觉比起类来说更接近函数)
这个实体的定义是放在entity语句中的,其中主要是port语句定义端口名字和类型,就像C++中定义函数参数一样
ENTITY counter IS
PORT(clk,en,reset:IN STD_LOGIC;
target:IN STD_LOGIC_VECTOR(4 DOWNTO 0);
q:OUT STD_LOGIC);
–counter:clk来一个上升沿则内部计数器加一,直到内部计数器与target值相同时q端从0变成1
–en:1-enable,0-disable
–reset:0-nothing 1-reset to 0
END ENTITY counter;
这样定义了一个叫做counter的元件(实体)
其中clk,en,reset是输入端,并且都是1bit大小(STD_LOGIC是1个bit),也就是这三个端口分别占用一个引脚…
target也是输入端,但是有5bit大小,也就是它用了5个引脚,要指定是哪个引脚可以用下标,就像C++的数组一样
q是输出端,1bit大小
下面是注释…在vhdl中用–表示注释…
到这里,就像是C++中声明了一个函数,但是函数内容还没有
下面要用architecture来写这个元件内部结构了,相当于C++的函数体
ARCHITECTURE behav OF counter IS
–这里可以放内部信号的定义
–引用外部元件的定义也写在这里
BEGIN
–这里放代码(赋值语句)
END ARCHITECTURE behav;
内部信号类似于C++中函数体中的局部变量,作用域是整个元件(实体)内部
然后代码部分…是的…从根本上来说只有赋值语句…
连接电路的时候除了连连线之外还能做什么呢…
vhdl只是做这种连线的工作…
赋值语句是用
唔嗯…标题是不是该叫
Range encoding 区间编码
呢…
算术编码经常听到…和huffman编码同样是熵编码
要压缩什么信息的话,熵编码一般来说是最后的杀手锏了…
因为熵编码后得到的信息流的冗余度已经逼近了0…几乎每一位都已经携带了它所能携带的最大信息量了:每个符号出现的概率(次数)几乎相同…
就这个信息流而言,如果当作灰度图像,你将看到雪花屏…
这也就是为什么像rar之类的压缩软件压缩后的文件如果还想压缩一次的话反而会变大…
因此想要获得更高的压缩比的话…在熵压缩之前极尽一切可能利用原信息中数据的内在联系来压缩冗余信息吧…
对每个符号之间没有任何相关性的情况下…可能我们就只剩熵压缩了…
不过现实中大部分信息的各个符号间还是有很强的相关性的…
说一下信息量…一定会出现的事件不携带信息…出现概率越小的事件携带的信息量越大
比如掷硬币…一般情况下每次掷硬币的结果只携带1bit的信息…因为出现正面反面的概率相同…
但是如果真的用1bit来记录每次掷硬币的结果的话…比如0表示正面朝上,1表示反面朝上…
就会有个问题:如果结果是硬币立起来了…用什么符号记录呢?…
假设有2^-30的概率硬币立起来了…
这样的话…一次硬币立起来就携带了30bits的信息量…一次正面或一次反面则携带了略微小于1bit的信息量…
至于用什么方法记录…转义符是个不错的选择…
比如咱用30个0后面跟一个1来表示硬币立起来了,用30个0后面跟一个0表示确确实实刚才抛出了连续30次正面
回到算术编码上来…
先和huffman编码比较一下吧…算术压缩的优势在哪里呢…
能用小于1bit的长度来存那些信息量小于1bit的信息
huffman编码就是这里弱了…对于信息量小于1位的信息,huffman 编码方式最小也要消耗1位来表示
结果如果要用huffman编码来编上面的投掷硬币结果的信息的话…就会变成用0表示正面,10表示反面,11表示硬币立起来了…
这样平均下来…要用1.5bits来记录1次投掷…不合算啊…
算术编码的话平均下来可以以接近1bit来记录1次投掷…
一些基本原理的话很多地方都有…
比如维基百科
这篇文章也不错
上图像通信课的时候老师说过…算术编码虽然有优势…但因为有专利的原因…当时并没得到广泛应用
倒是都用huffman编码来实现熵编码…毕竟普通情况下huffman编码也不必算术编码差多少…
至于现在…不知道还有什么限制没…
在看了上面的维基百科之后,发现了这个区间编码
和算术编码用长小数表示信息的方法不同,这用的是大整数表示…
看了一下感觉实际上和算术编码的本质是一样的…只不过小数被避免了…
而且感觉更合我口味…
然后说说我心血来潮想要把这算法实现出来…(终于进入正题?了)
虽然很早就对此有所耳闻…原理也很易懂…但是一直没有动手写过…
先撇开高阶的和带转义码的编码方法不谈…光是0阶,256符号(1字节)初始概率1/256的自适应方式就让人碰壁了…
当然…我用的方法更像区间编码而不是算术编码…因为我用整数区间而不是小数区间…
我目前还没深入理解过浮点数…发明浮点数的人真伟大…
每压缩一个字节,该字节表示的符号的频次就加一,随着数据量的增加,这个频次就越来越接近其出现的真实概率,这就是普通的自适应…
计算某个字符b对应的新区间大小就是frequency[b]*range/count
新区间下界是sum{frequency[i],i=0..b-1}*range/count+low
这里count是之前处理过的字节数加上初始的256,low是当前区间的下界
这里为止都是很容易想到的…
至于怎么以有限搞定无限精度…
最初的想法是计算到新区间之后,看看这个新区间的上界和下界的最高位是否相同,相同则输出该位,然后区间变大一倍(最高位丢弃,其余左移,上界加1),继续判最高位是否相同,直到不相同就停止输出…
最后当前区间就设为这个新区间,然后读入下一个字节继续压缩…
然后问题出现了…数据量大了之后就会出现压缩错误的情况(解压后的数据在后半段全乱了,只有前面一部分才是正确的)
原因是当新区间大小很小,但是却正好在1000..00B(MAX/2)上下的时候…无法通过输出位来扩大区间大小,因为最高位不相同,但是压缩下一个字节的时候因为当前区间太小,导致这回的新区间大小为0了…
自己想了几种方案…但还是解决不了…
后来找到了这份代码
仔细读了之后才恍然大悟…原来还能这样做…
因为当新区间正好在1000..00B(MAX/2)上下的时候,上界的前缀一定是1后面跟很多0,而下界的前缀一定是0后面跟很多1…
所以可以先记录下待输出多少位(在上面的代码里叫bits_outstanding),然后扩展区间大小(下界减去MAX/4,区间大小加倍)…直到区间大小超过MAX/4为止
当然如果遇到上下界的最高位相同的时候,终于可以输出了
但是别着急,还有 bits_outstanding个位没有输出呢,如果当前这个最高位是1,那么就输出一个1然后bits_outstanding-1个0,然后再输出当前这个最高位1
否则则是一个0,bits_outstanding-1个1,然后0
因为:
好了…到这里压缩的主要部分就搞定了…留下接口,让代码细节从眼中消失吧…
现在无论符号数有多少个,都可以随心所欲的压缩了…
因为输入一个新区间,就能输出正确的压缩后比特流,同时更新当前区间
至于输入一个符号你用什么方式转换成什么样的区间,多少个区间,采用几阶模型,用不用转义符,都是上面一层的事情…