回家

爷爷奶奶天天盼星星,盼海月,就是盼我早一天能够回到武汉的家里。这个家,我自打被生下来,还没有回去过一次呢。不过明天我将终于如愿以偿了。

现在我已经满6个月了,可以很稳当地坐着,并且不时地用手撑住地面,身体前倾,做爬行的预备动作。妈妈说我偶尔可以倒退着爬上一两下,说这就是快能爬了的信号。爸爸就担心在他回日本之前看不到我爬,我会努力的,咱们爬着瞧吧。

回武汉后,更新这个MSN的重担就要落在爷爷奶奶的肩上了,也不知道他们弄不弄得好。

护照到了

今天护照到了,正好是我半岁的生日,值得庆祝一下。爸爸费心给我弄的照片虽然很漂亮,但是弄到护照上以后,整体偏暗,可惜了人家一脸好皮肤了。

护照到手了,下一步就是抓紧时间定回国的机票,我们预定4月28日回国,算起来我在日本就只能呆20多天了。


Constraint Programming in Oz

本文通过几个简单的例子,介绍约束逻辑程序设计的基本知识,以及如何用Mozart-Oz来实现。

(本文中将把Constraint Programming翻译为约束程序设计,译者本人并不知道许多专有名词的译法,因此可能有谬误,请见谅)

介绍

1. 什么是约束程序设计?

我们还是从一个例子着手吧。
例1.
有如下的数学算式:SEND+MORE=MONEY,每个字母代表一位从0到9的数字,首位不能为0,每个字母所代表的数字不同,请问各个字母所代表的数字是多少?
这个问题有唯一解答:9567+1085=10652
这就是一个条件约束问题。解决此类问题最简单的方法可以描述为"产生并测试"。我们很容易看出这个问题
有8个字母,而每个字母又可以是从0到9,即有10种可选方案。所以总共的可选答案是8^10种。产生程序将产生这8^10种可能解答, 然后使用测试程序来测试所产生的解答的正确性。下面列出这个问题的约束条件:
1. 8个字母所代表的数字两两不同。
2. S M不能为零
3. S*1000+E*100+N*10+D + M*1000+O*100+R*10+E = M*10000 + O*1000+N*100+E*10+Y
只要产生的某种组合符合上述三个条件就可以说是找到答案了。
但是显然这种方法在多数情况下是行不通的。这是由于组合问题中通常都存在组合爆炸,例如上题中如果不是8个字母, 而是9个的话,那么可能的组合数目就是9^10,字母仅仅只多了一个,而要产生的排列却增加了3倍多。
本文将详细介绍如何编制解决此类问题的程序,不过我们不使用传统的程序设计语言,而是使用一种已经包含了完整解决方案的语言:OZ。

2.基本原理

首先来看看需要使用什么方法才能够减少测试的次数吧。我们从另外一个简单例子入手。典型的条件约束问题具有如下的形式:
它 包含n个变量:V1,......,Vn, 每个变量的取值范围分别是:D1,......Dn,其中D1,......Dn都是包含有限元素的集合,通常集合中的元素都可以使用整数来表示。目标是 找到一组满足约束条件C(V1,......,Vn)的解。下面是一个简单的例子:
例2.有15个变量V1,......,V15,他们的取值范围都是{1,......,15},约束条件为:V1
V14
很明显这个问题只有一个答案就是Vk=k。我们来看如何让电脑来解决这个问题吧。
首先使用通常的产生并测试的方法:
我们可以通过下面的方法来产生一系列的可能组合:
选择一个尚未赋值的变量,从该变量的值域中选择一个值赋给此变量,重复此步骤直到所有的变量都赋上了值。这个操作将生成一个树状结构:每个非叶节点都代表一个尚未完全赋值的状态,叶节点则代表了一种可能的组合。
满足约束条件的叶节点就是问题的解,不满足约束条件的叶节点就是失败点。在本文中我们将经常使用图形来表达这种树状结构:
其中蓝色圆形代表选择点,即非叶节点。红色方形代表失败点,绿色菱形代表解节点。为了方便起见,一棵所有叶节点都是失败点的子树使用红色三角形代表,而包括了解节点的子树则使用绿色三角形代表。

现在来看看前面的问题:一共有15个变量,每个变量的可能取值有15个,那么总共的可能组合就是15^15=437,893,890,380,859,275种, 就目前的计算机来说这是个天文数字了。

3. 交错产生和测试

前 面所介绍的"产生并测试"的方法,是在完全产生了一种组合之后,再来测试这个组合。我们可以把产生和测试交错进行,这样可以极大地提高效率。在每一次选择 之后都使用约束条件来判断这步选择是否合理,而不是完全产生了某种组合之后再来判断。例如在上面的例子中,当给V1和V2赋值之后,就可以立即使用V1
传播和分配(Propagate and Distribute)
到目前为止,我想你应该已经认识到使用简单的"产生并测试"的方法是行不通的,而"交错产生和测试"虽然能够提高效率,但是也有它的局限性:若使用这种方法来解例2,那么搜索树将包含917477个节点。如果变量数目增加到100又会如何呢?:)
那么使用什么方法呢?我们不希望测试过程只是被动的检测某种组合是否满足条件,而希望测试过程是积极的。这就是说通过测试,我们希望缩小变量的取值范围。在前面的例子中,V1和V2的取值范围都是1到15,但是由于V1
然而在通常情况下搜索是不可避免的,我们的目的是在每次搜索之前先通过约束条件尽量缩小变量的取值范围。这种方法在约束程序设计中被叫做"传播和分配(propagate and distribute)"。
传播通过简单的确定性的推导过程尽量减少可能的解的个数。当传播过程无法继续的时候,就需要进行分配。所谓分配就是进行非确定性的选择(下面将详细介绍,如果有何不明白请继续阅读),这样搜索树的尺寸能够尽量缩小,我们可以把传播的过程看作对搜索树的裁剪。

Mozart OZ

OZ 是一门程序设计语言,而Mozart则是它的实现系统之一。OZ是一门新兴的程序设计语言,因此它也包含了许多特别的技术。自然,约束程序设计是它的主要 功能之一,除此之外它有像Prolog一样的逻辑程序设计模式,有Lisp, SML式的函数式程序设计模式,另外还有并行计算,多线程,面向对象等模式。本文主要介绍它在约束程序设计方面的运用,至于其它方面将在必要的时候进行讲 解。

1. 安装

Mozart支持许多操作系统,你可以到www.mozart-oz.org下载相应的版本。除此之外你的电脑上必须安装Emacs(Xemacs),Mozart将使用这个编辑器作为开发界面。安装中如果出现什么问题,请参照mozart的帮助文档。
下面是运行界面,最上面的窗口就是我们写程序的地方。中间一部分(标有Oz compiler)用来显示编译信息,最下面一行是Emacs的提示栏,用来显示和输入一些编辑信息。

我 们先来看如何做HelloWorld程序,在最上面的窗口输入下面文字之后,按Ctrl+.然后按Ctrl+b就会把当前窗口中的程序送交编译器编译运 行,当然也可以选择OZ菜单中的feed buffer选项,另外还有Feed Region,Feed Line,Feed Paragraph等选项,Region表示当前的本选择的文字,Line表示光标所在的行,Paragraph表示一段程序(没有空行分隔)。我们看到 编译信息窗口出现了编译信息,accepted表示编译通过,可是运行的结果在哪里呢?运行的结果在一个尚未打开的buffer中,选择OZ-> Show/Hide->Emulator就可以看到结果了。

把上面的Show改为Browse,即{Browse 'Hello World!'}并feed buffer之后,将看到
窗口出现。此后我们都将使用OZ browser来显示结果。

2. 传播

OZ包含了整个约束程序设计所需要的功能,我们想来看看传播(propagate),即OZ是如何最大限度的缩小变量的取值范围的。
先输入如下程序(把上面的Oz Browser,先关闭,把程序buffer中的文字也请清空)

declare X Y Z
X::1#10
Y::1#10
Z::1#10
{Browse [X Y Z]}

然后用Feed Paragraph把上面程序段送交编译器。
declare 关键字用来声明变量,这里声明了三个变量标识符:X Y Z,OZ中所有的变量标识符都必须大写。X::1#10意思是说X的取值范围从1到10,包括1和10。::传播器是用来定义约束变量的取值范围的,而 1#10则是某个可能的取值空间。最后我们用Browse把三个变量的值显示出来,[X Y Z]把这三个变量做成一个列表,关于列表,如果你熟悉Prolog,Lisp的话应该不会陌生。出现的结果如下:

我们看到变量标识符后面就是此变量的取值范围。
此后我们每输入一句语句,就用Feed Line把它送交编译器,这样可以动态地看到程序运行的结果,Browse中的显示内容不再用图表示,我在前面加上>>前缀表示是Browser中的内容。

X<:Y
>> [X{1#9} Y{2#10} Z{1#10}]

输 入X<:Y之后我们惊奇的发现,Browser中的内容变化了,这也是Brwoser的强大功能之一,它并不只是简单的把结果显示出来,当变量发生 变化的时候,这些变化也会立刻在Browser中体现出来。X<:Y是一个一个传播器,当我们把这个约束条件送交编译器后,传播起作用了,同时缩小 了X Y的取值范围。

Y<:Z
>> [X{1#8} Y{2#9} Z{3#10}]

输入Y<:Z后我们发现X的取值范围也发生了变化,这也就是说X<:Y这个传播器也起了作用。

X+Y+Z=:6
>>[1 2 3]

我们发现这个约束条件加上之后,X Y Z的值就都确定下来了。

我们看到了传播器可以自己进行推导,尽量的减小变量的取值范围。不过这种推导也是非常复杂的,因此Mozart在这方面做了某些限制。例如Y=:2*X并不能够推导出Y必须是偶数,
除了上面的这些简单的传播器之外,Mozart还提供了许多很高级的约束传播器,等我们需要的时候再进行讲解。

3. 分配

当传播器无法在缩小变量的取值范围的时候,就需要进行分配了。所谓分配就是把变量组中的某个变量的取值范围分成两个部分,然后分别再对这两个部分进行传播和分配。
下面我们先来看一个完整的传播分配的例子:
我们要解决的问题如下:

X Y Z属于{0,1,...,7}
X+Y=3*Z
X-Y=Z

首先我们可以根据上面的约束条件写出如下的传播器:

X::1#7
Y::1#7
Z::1#7

上面三个传播器可以缩写为: [X Y Z] ::: 1#7,我们用列表把三个变量扩起来,然后用:::定义这个列表的取值范围,即列表中的每个元素的取值范围。剩下的两个等式的传播器如下:

X + Y =: 3*Z
X - Y =: Z

如果你把上述的传播器传送给编译器的话,

declare X Y Z
[X Y Z]:::1#7
X+Y=:3*Z
X-Y=:Z
{Browse [X Y Z]}

将得到如下结果:

>> [X{2#7} Y{1#6} Z{1#4}]

很显然,并没有找到答案。
因 此我们要使用分配器,把上述变量中的某个变量的取值范围分成两个部分,然后再分别对这两个部分进行传播。分配的方式有很多, 最简单的方式就是选择变量组中的第一个变量,假设这个变量的取值范围是a#b,那么分开的两组范围就是a和(a+1)#b。这种分配方式叫做naïve。 分配语句如下:

{FD.distribute naive [X Y Z]}

这句话表示我们要对变量组X Y Z的值域进行分配,分配方式是naïve。
我们先来看看实现程序:

declare
proc {Equations Sol}
X Y Z
in
Sol = solution(x:X y:Y z:Z)
% Propagate
[X Y Z] ::: 1#7
X + Y =: 3*Z
X - Y =: Z
% Distribute
{FD.distribute naive [X Y Z]}
end
{Explorer.all Equations}

这里我们声明了一个过程,过程的声明方式如下:

proc {Equations Sol}
end

Equations为过程名,Sol为过程的参数,这里这个参数是作为返回值用的。
X Y Z是这个过程的内部变量标识符,我们用一个结solution(x:X y:Y z:Z)把这三个变量包含起来,并赋予Sol,这样过程的返回值就是一组解了。
下面的分别定义传播器和分配器,%表示注释:

% Propagate
[X Y Z] ::: 1#7
X + Y =: 3*Z
X - Y =: Z
% Distribute
{FD.distribute naive [X Y Z]}

定义了上述函数之后,我们还必须把这个函数传递给专门的搜索引擎:

{Explorer.all Equations}
{Explorer.one Equations}

Explorer.all找Equations的所有解,而Explorer.one只搜索一个解。把上面的程序传送给编译器后,我们看到如下的结果:

我们看到Explorer显示的是一棵搜索树,按照上面树的节点的顺序一起双击,则节点的值在下面的Inspector

中显示出来。图中每个蓝色的圆形节点都表示一次分配的过程。我们看到节点1的值就是前面只进行传播之后的结果。由于得到这个结果之后无法再进行传播,因此分配器对变量组[X Y Z]中的第一个变量X进行分配,得到如下两组取值范围:

[X{2} Y{1#6} Z{1#4}]
[X{3#7} Y{1#6} Z{1#4}]

对[X{2} Y{1#6} Z{1#4}]进行传播最终得到一组解:2#solution(x:2 y:1 z:1),即图中的第二个节点,解都是由绿色的菱形表示。而节点3就是上面的第二组取值范围[X{3#7} Y{1#6} Z{1#4}]进行传播之后的结果[X{3#7} Y{1#5} Z{2#4}],我们看到Y和Z的值域发生了变化。因为传播器无法对[X{3#7} Y{1#5} Z{2#4}]这个取值范围进行传播以获得更小的取值范围,因此分配器再次进行分配:

[X{3} Y{1#5} Z{2#4}]
[X{4#7} Y{1#5} Z{2#4}]

传播器对第一组结果进行传播发现自相矛盾,因此我们得到一个红色的正方形节点,表示失败。对[X{4#7} Y{1#5} Z{2#4}]进行传播的结果为节点4。
如此下去当整个搜索树完成的时候,我们得到三个绿色的菱形节点,也就是三组解。
现 在我们知道了传播分配的基本原理,在OZ中提供各种各样的分配器。例如有些分配器是找到变量组中可能取值个数最少变量进行分配,这样有助于尽早确定这个变 量的值,而有的分配器是把变量的取值范围等分为两部分,这样做有助于传播器最大限度的对搜索树进行裁剪。不同的问题采用不同的分配器,得到结果最终是一样 的,不过效率就有很大的区别了。

传播与分配的原理

待续...


DSP/BIOS中的线程

RY DSP开发 2006/04/25

DSP/BIOS中的线程和电脑中的线程有很大区别。关于DSP/BIOS的详细介绍请参考TMS320 DSP/BIOS User's Guide。下面简单地介绍一下DSP/BIOS的线程。
为了让DSP能够同时处理多个任务,DSP/BIOS提供了如下几种类型的线程。
HWI(硬件中断),SWI(软件中断),TSK(任务),IDL(空闲线程)。

HWI 其实就是中断服务。当硬件中断产生之后,DSP/BIOS就会调用相应的HWI函数。如果把HWI设置为Dispatch的话,则会在调用HWI函数的前 后自动调用HWI_enter和HWI_exit。在HWI函数的执行时,若有其他的硬件中断产生,当前的HWI会被新的中断抢占,也就是说DSP会先去 执行新的HWI。如果希望当前的HWI在不被其他的HWI打断的话,可以在不能被打断的代码前后调用HWI_disable和HWI_enable。 HWI的优先级是硬件级别的优先级(固定的),若同时有多个中断向DSP请求的话,它决定DSP先响应哪个中断。而中断所对应的HWI则是可以被任何其他 的HWI抢占。
SWI有15级优先级,高优先级的SWI可以抢占低优先级的SWI。一般通过SWI_post(或者类似的函数)来启动它。SWI和HWI一样都是不能被阻塞(blocking)的线程。也就是说一旦它们被运行,就要运行到终点为止,除非被其它的线程抢占。

HWI和SWI都使用系统堆栈,而每个TSK都有自己的堆栈。可以在TSK线程之间随意地互相切换,切换时DSP/BIOS将自动地更新堆栈寄存器,因此TSK线程可以被阻塞。这样TSK就可以写成一个死循环:

While(1){
   Do_some_task();
   Yield_to_other_task();
}

Do_some_task 做这个TSK所要做的事情,Yield_to_other_task则把控制权转给其他的TSK。例如如果是把控制权转给同样优先级的其他TSK,则可以 调用TSK_yield函数。如果是要把控制权转给低优先级的TSK,则可以调用TSK_sleep函数让自己休眠一段时间,或者调用SEM_pend函 数等待。除非TSK中调用了HWI_disable或者SWI_disable,否则它在任何时候都可以被HWI或者SWI抢占。
TSK和电脑上的线程有些类似,而HWI和SWI则不一样。下面举一个例子说明一下:假设有线程SWI1,SWI2,TSK1,TSK2。SWI1的优先级大于SWI2,TSK1的优先级大于TSK2。
则:
若 在SWI2运行当中,SWI1被post了的话,DSP马上转到SWI1运行,并且直到SWI1运行结束之后再继续SWI2的运行。这就是说SWI只能被 抢占,不能被阻塞。这是因为所有的SWI和HWI都公用系统堆栈,一旦SWI1运行,堆栈的最上层就变成了SWI1的环境,除非SWI1运行结束,是无法 切换回到SWI2的环境中去的。

若在TSK2运行当中,TSK1进入ready状态的话,DSP马上转到TSK1运行。稍后如果TSK1被阻塞的 话,DSP再继续TSK2运行,当TSK1所等待的信号就绪之后,再转入TSK1运行,如此反复。也就是说DSP可以在TSK之间相互切换。这正是因为每 个TSK都有自己独立的堆栈可以保存自己的运行环境。


取样频率转换算法(sampling rate converter 简称SRC)

RY DSP开发 2006/04/12

把模拟声音信号转换为数字声音信号,需要对模拟信号按照一定的取样频率进行取样。目前比较常用的取样频率有8000Hz, 11025Hz, 16000Hz, 22050Hz, 32000Hz, 44100Hz, 48000Hz,另外还有高取样频率88200Hz,96000Hz等。例如CD采用的是44100Hz,而电话则一般采用8000Hz。Mp3文件格式 则支持48000Hz以下所有的取样频率。

假设要设计MP3播放器,为了能够播放所有取样频率,有两种办法。一种是硬件支持,这需要数模转换器支 持多种取样频率,而硬件必须能够产生两套时钟,8000Hz和11025Hz。这无疑增加了硬件成本。第二种办法就是硬件只支持一种取样频率,而通过软件 改变声音信号的取样频率。

转换取样频率的基本方法就是对离散的信号进行插值。插值运算有很多种算法,例如拉格朗日插值法,三阶样条曲线,贝赛尔曲线,以及线性插值等等。这些方法在图形方面应用十分广泛,很多矢量绘图软件都支持几种曲线插值算法。但是这些算法无一能运用到数字声音信号上。

在 数字声音信号领域,我们关心的是插值运算的结果和原声音信号的误差。由香农定理可知,如果取样频率高于声音信号的最高频率的两倍的话,就可以精确地从取样 信号恢复原信号。因此最理想的数字声音信号的插值算法就是基于此理论,从而精确地恢复原信号。得到原信号之后,只要再对其用新的取样频率进行取样,就可以 实现取样频率转换了。这种插值算法被称为限频带插值(Bandlimited Interpolation)。
限频带插值的原理和实现算法的详细资料可以参考http://ccrma.stanford.edu/~jos/resample/ 。下面只简单地介绍一下其原理。

假设对于连续时间信号x(t)进行取样之后得到一个数列x(n*T),这里我们用t表示连续时间,n是一个整数,而T是取样周期。我们假设x(t)的频带在-F/2 和F/2之间,F是取样频率,即1/T。
从香农定理可以知道按照如下公式可以从x(nT)计算出x(t)。

x(t) = ∑ x(nT) * h(t - nT) ( n=-∞ …∞)
其中,h(t) = sinc(F * t) = sin(PI * F * t) / (PI * F * t)

我 们来看看这个公式的解释。我们知道,时域两个信号相乘,频域则是这两个信号的频谱进行卷积。取样之后的信号可以看作原信号与周期是T的脉冲信号相乘。于是 取样之后信号的频域就是原信号频谱与周期脉冲信号的频谱的卷积。脉冲信号转换成频域之后,仍然是脉冲形式,间隔刚好是两倍的取样频率。这样卷积出来的结果 就是原信号的频谱在频率轴上不断的重复,就好象时域中的周期信号一样。为了从取样后的信号还原为原信号,就需要对取样后的信号进行滤波,如果使用理想的低 通滤波器,就可以得到-F/2 和F/2范围内的原信号的频谱了。这种理想低通滤波器转换到时域之后,就是sinc函数,所以如果信号与sinc函数卷积的话,就等于对信号进行理想低通 滤波,这正是上面公式所表达的意思。
虽然从理论上来说可以把取样后的信号还原为原信号,但是由于需要和sinc函数卷积,而sinc函数的长度又 是无限的,所以实际上精确地还原原信号是不可能的。在实际运算中,我们可以取sinc函数中值较大的部分进行卷积运算而把很小的值都看作0。这其实就是把 sinc函数和某个窗函数相乘。窗函数如何选择直接影响到最后的还原精度。窗函数要尽量能用较少的点数达到较高的精度。

在实现变调算法 (改变音调,但不改变速度)时我用到过SRC,那时为了方面起见,我直接截取sinc函数的一段进行卷积,相当于选择了矩形窗函数。本以为多取些sinc 函数的点应该能够得到比较好的效果,可是用这个SRC程序对低频声音进行处理的时候,出现了高频噪声。后来选择hanning窗函数与sinc函数相乘, 终于解决了这个高频噪声问题。让我我深深地体会到窗函数的重要性。


Labview的实时控制系统初步完成

这是一个汽车轮胎实验系统。它通过串口RS-432从传感器获取轮胎的受力数据,经过用C语言编写的计算内核分析计算之后,再由Labview把结果传给 NI-motion以控制电动机的转动(控制轮胎的前进方向)。电动机带动机械部分运转,从而传感器获取的数据发生变化。这种控制计算需要一秒钟运行 1000次,由于电动机部分的响应延迟,Labview最快也只能每3ms向NI-motion发送一次控制命令。Labview还从NI-motion 的模拟电压输入端口读取方向盘的转动信息,传递给计算内核,以控制汽车的方向。NI-motion的输入部分速度更慢,目前暂时设置为每10ms读取一次 方向盘输入。因此我采用了三个线程来实现上述功能,一个实时线程以1ms为周期,从传感器读取数据并调用计算内核进行计算。一个以3ms为周期,把计算的 结果传递给NI-motion以控制电动机,一个以10ms为周期从方向盘读取角度信息。3个线程之间采用realtime PIPE传输数据。

Labview 除了进行上述操作之外,还需要把计算内核输出的许多结果保存成文件,前面的文章已经提到过硬盘的存取会导致无法在1ms周期之内完成计算,因此只能先临时 把结果保存在内存中,等操作结束之后,一次把内存中的数据全部写入文件。另外,为了可视化计算数据,Labview以每秒30帧左右的速率用TCP/IP 向电脑主机发送数据,由电脑主机上的3D汽车模拟程序实时地演示汽车当前的动作。因此还有一个优先级最低的线程在空闲的时候向主机传递数据。


开源音频视频转换软件

最近大肆购物一顿,购买了SANYO的Xacti DMX-HD1,一个SD卡摄像机,它说能直接录制为MP4文件。一个CREATIVE的Zen Vision:M,它说能够播放MPEG4文件,包括DIVX和XIVD等多种格式。我对众多的视频格式自然是一头雾水,我所希望的就是用Xacti摄的 像,可以直接在Zen上播放。既然两个都说是支持MP4,那我就买了试试看吧。结果大失所望,Zen拒绝播放用Xacti录制的文件。只好找转换软件,搜 索了一下午,有许多软件但是都不免费,最后找到了这个mediacoder 。看网页介绍,它能在许多种格式的多媒体文档之间相互转换,看作者的名字应该是中国人写的这么一个好软件,真令人感到自豪。这下可以把我那可爱的宝宝的音容 笑貌随身携带了。