QianQing's Blog

介绍SymPy的一些基本方法

广义不等式使用符号，似乎意味着这与上的有相似的性质。但是一个很明显区别在于，上的是一个线性序，即任意两点都是可比的（对于至少有一个成立）。但是这个性质对于其他广义不等式并不一定成立，这导致最小、最大这些概念在广义不等式的研究中变得更加复杂。

如果，那么称是关于广义不等式的最小元，以同样的方式也可以定义最大元。如果一个集合有最小（或最大）元，那么它们是唯一的。

与之相对的是极小元。如果可以推得，那么称是上关于广义不等式得极小元。以同样的方式可以定义极大元。

用集合符号可以描述最小元和极小元。元素是中的一个最小元，当且仅当. 这里就表示了与相比大于或等于的所有元素（）。

元素是中的一个极小元，当且仅当. 这里表示与相比小于或者等于的所有元素（），其与的唯一共同点是

当，导出的偏序关系就是上一般的序，此时，极小和最小的概念是一致的。

例：考虑锥，其导出的是关于上的不等式。可以给出关于极小元、最小元的集合描述。此时广义不等式的含义是在的右方、上方。是集合的极小元，表示中其他所有点都在其右方、上方。为集合的极小元，说明中没有任何一个点在的左方、下方。可以参考下图，和分别是其所在多边形的最小元、极小元

正常锥（Proper cones）

我们称一个锥是正常锥如果其满足以下四个条件：

1. 是凸的
2. 是闭的
3. 是实的，即包含非空的内部
4. 是尖(pointed)的，即不包含直线，或者等价的说：

广义不等式（Generalized inequality）

补充：偏序关系，，如果关系是自反、反对称、传递的，那么是上的偏序关系，可以用表示。例如小于等于关系就是上的偏序关系

正常锥可以用来定义广义不等式，即上的偏序关系。正常锥可以定义上的偏序关系：

也可以记作。类似地，可以定义严格偏序关系：.

当时，偏序关系就是通常意义上的，相应的，严格偏序关系与上的对应。因此，广义不等式包含了上的不等式，这是广义不等式的一种特殊情况

广义不等式的性质

1. 对加法保序：如果并且，那么
2. 具有传递性
3. 对非负数乘是保序的：如果，那么
4. 是自反的
5. 是反对称的
6. 对极限运算是保序的：如果对于，均有，那么有

相应的严格广义不等式也有一些性质

2. 对加法保序
3. 对非负数乘保序
4. 反自反：
5. ，则存在足够小的使得

以上这些性质从定义和正常锥、凸锥的知识很容易推出

关于wire

在Verilog中，wire可以看作一个导线（或则任意位宽的总线），需要注意的几点是：

1. wire可以用于将实例化时的输入输出端口连接到电路的其他地方
2. wire类型必须被其他东西驱动而不能用于储存其他数据
3. wire类型在always@块中不能作为=和<=的左值
4. wire是assign语句的左值唯一合法的类型
5. wire只能用于组合逻辑电路

关于reg

reg和wire比较类似，但是能够储存信息，类似寄存器，需要注意的几点是：

1. reg可以在实例化模块时连接其输入
2. reg不可以再实例化模块时连接其输出
3. reg可以在声明模块时作为其输出
4. reg不可以在声明模块时作为其输入
5. reg类型时always@块中作为=,<=左值的唯一合法类型
6. reg不能作为assign语句的左值
7. reg类型可以创建寄存器，以用于类似于always@(posedge)的块
8. reg可以描述组合逻辑也可以描述时序逻辑

reg和wire的共性

1. 都可以作为实例化模块时的输入
2. 都可以作为always@块中=,<=的右值以及assign的右值

本次我们来讨论一类叫线性分式的函数，其比仿射函数更加普遍，而且也是保凸的。

透视函数(The perspective function)

我们定义为透视函数，其定义域为。此处表示正实数集合。

透视函数可以理解为，对一个维的向量，用最后一维除前维，并且将最后一维舍去。也即对最后一维进行了规范化。

可以用小孔成像来理解透视函数，如下图的小孔成像，上方的一系列点透过小孔映射到了上。原来的点何其对应的像的映射就对应了透视函数。

透视函数的保凸性

通过小孔成像的例子，我们可以很直观地理解透视函数的一系列性质。

如果是凸集，那么它的像也是凸集。这个结论很直观：通过小孔观察凸的物体还是凸的。

更加严谨地，我们可以证明线段在透视函数地作用下会被映射为线段。假设，并且，那么对于，就有：

，其中

容易知道其中的关系是单调的：当在0，1之间变化形成线段时，也在0，1之间形成线段，这说明。

接着，假设是凸的，并且。为了显示的凸性，我们需要说明在中。而这是显然的，这条线段就是在的像，因为属于。

透视函数的反函数的保凸性

一个凸集在透视函数下面的原像也是凸的：如果是凸集，那么也是凸的。证明如下，

假设。需要说明，也即。

显然，。可以从下式看出：

，其中

从而知道上面需要说明的结论是显然的。

线性分式函数(Linear-fractional functions)

线性分式函数是由透视函数和仿射函数复合而成的。设是仿射的，即，其中,,,.

则由给出的函数 称为线性分式（或投射）函数。如果则的定义域为，并且是仿射函数。因此我们知道仿射函数和线性函数都是特殊的线性分式函数。

线性分式函数的投射解释

可以将线性分式函数表示为：将矩阵作用于（左乘）点，得到；然后将所得的结果进行归一化（伸缩变换）看，使得最后一个分量为1，得到.

线性分式函数的保凸性

线性分式函数是保凸的。如果是凸集并且在的定义域中（即任意满足），那么的像也是凸集。

根据前面的结果可以知道线性分式函数的逆映射也是保凸的

一些时序逻辑电路的行为级建模的例子

移位寄存器的Verilog建模

对于双向移位寄存器74HCT194，其建模时要实现的核心功能在于，的四种值时的数据的不同操作，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

module shift74x194_beh(
	input S0,S1,
    input Dsl,Dsr,
    input CP,CR,
    input [0:3]D,
    output reg [0:3]Q
);
    always @(posedge CP,negedge CR)
        if(!CR)Q<=4'b0000;
    	else
            case({S1,S0})
                2'b00: Q<=Q;			//输出保持不变
                2'b01: Q<={Dsr,Q[0,2]};	//右移
                2'b02: Q<={Q[1,3],Dsl};	//左移
                2'b03: Q<=D;			//并行置数
            endcase
endmodule

计数器的Verilog建模

带有使能端和同步置数端的可逆二进制计数器

参数n设置位数，Up_down为1/0控制计数器递增/递减

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

module updowncount #(parameter n=4)
    (
    	input Load,Up_down,En,CP,
        input [n-1:0]D,
        output reg [n-1:0]Q
    );
    integer direction;
    
    always @(posedge CP)
    begin
        if(Up_down)
            direction<=1;
        else
            direction<=-1;
        if(Load)
            Q<=D;
        else if(En)
            Q<=Q+direction;
        else
            Q<=Q;
    end
endmodule

带有异步清零功能的D触发器构成的4位二进制计数器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

module D_FF(
	output reg Q,
    input D,CP,Rd
);
    always @(negedge CP,negedge Rd)
    begin
        if(!Rd)Q<=0;
        else Q<=D;
    end
endmodule

module rippecounter(
    output Q0,Q1,Q2,Q3,
    input CP,CR
);
    //实例化引用触发器模块
    D_FF FF0(Q0,~Q0,CP,CR);
    D_FF FF1(Q1,~Q1,Q0,CR);
    D_FF FF2(Q2,~Q2,Q1,CR);
    D_FF FF3(Q3,~Q3,Q2,CR);
endmodule

带有使能端和异步清零的模10计数器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

module m10_counter(
    output reg [3:0]Q,
    input CE,CP,CR
);
    always @(posedge CP,negedge CR)
    begin
        if(!CR)Q=4'b0000;
        else if(CE)
            begin
                if(Q>=4'b1001)
                    Q<=4'b0000
                else Q<=Q+1'1;
            end
        else Q<=Q;
    end
endmodule

需要注意的是，电路的功能描述和具体的硬件电路结构是无关的，从这个模10计数器的建模中可以看出这一点

状态转换图的Verilog建模

以检测连续输入序列的电路为例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

module Mealey_sequence_detector(
	input A,CP,CR,
    output reg Y
);
    reg [1:0]current_state,next_state;//中间变量
    parameter S0=2'b00,S1=2'01,S2=2'b11;
    always @(negedge CP,negedge CR)//时序电路
    begin
        if(~CR)	current_state<=S0;
        else	current_state<=next_state;	//状态转换
    end
    always @(current_state,A)//组合电路
    begin
        case(current_state)//准备下一状态
            Y=0;
            S0:begin	next_state=(A==1)?S1:S0;	end
            S1:begin	next_state=(A==1)?S2:S0;	end
            S3:if(A==1)	begin	next_state=S2;	end
            	else	begin 	Y=1;next_state=S0;	end
            default:	begin next_state=S0;	end
        endcase
    end
endmodule

verilog的行为级建模使用关键词initial和always定义的两种结构类型的语句。一个模块的内部可以包含多个initial和always语句块，仿真的时候，这些语句块同时并行执行，直到仿真结束

initial语句块通常用来描述激励信号，仿真时仅执行一次，课本中没有详细介绍。

always语句本身是一个无限循环语句，即不停地循环执行其中地内容。其语法一般如下

1
2
3
4
5

always @(敏感信号列表)
begin
    块内部局部变量的定义
    过程赋值语句
end

敏感信号分为两种，电平敏感信号和边沿敏感信号

1

always @(D,S)

上面是电平敏感信号，当D或S的电平改变的时候，会执行always块中的内容

而边沿敏感信号分别使用posedge和negedge表示上升沿、下降沿

1

always @(posedge CP,negedge CR)

表示CP信号上升沿或者CR信号下降沿来的时候执行always语句块中的内容

always块内部的赋值语句分为两种：阻塞型和非阻塞型。其中阻塞型使用"="，非阻塞型使用"<="。

阻塞型赋值的多条语句是逐条进行的，而非阻塞型赋值可以理解为是同时进行的。

锁存器和触发器的Verilog建模实例

门控D锁存器

1
2
3
4
5
6
7
8
9

module D_latch(
	input D,E,
    output reg Q,
    output QN
);
    assign QN=~Q;
    always @(E,D)
        if(E) Q<=D;
endmodule 

基本D触发器

1
2
3
4
5
6
7
8

module DFF(
	output reg Q,
    input D,
    input CP
);
    always @(posedge CP)
        Q<=D;
endmodule

带有同步清零功能的D触发器

1
2
3
4
5
6
7
8

module sync_rst_DFF(
	output reg Q,
    input D,CP,Rd
);
    always @(posedge CP)
        if(~Rd)Q<=1'b0;
    	else Q<=D;
endmodule

在之前的内容中我们讨论了一些凸集。接下来会讨论一些保凸运算，顾名思义，保凸运算会保持集合的凸的性质。研究保凸运算的意义在于，这样我们可以通过一些已知的凸集去构造新的凸集，同时也可以利用这些运算的保凸的性质去确定一些其他集合的凸性。

交集(Intersection)

交集是保凸的，也就是说 ，如果是凸集，那么也是凸集。这个性质显然可以推广到无穷个集合的交运算：如果对于任意，都是凸的，那么也是凸的。

一个简单的例子是，多面体是半空间和超平面的交集，因此多面体是空的。

一个闭集是包含它的所有半空间的叫交集：

与此同时，并集是不具有保凸性质的，容易举出的例子是：一般来说两条直线的并集不是凸集。

仿射函数(Affine functions)

如果一个函数是一个线性函数和一个常数/常向量的和，即具有的形式，其中，那么我们说函数是仿射的。

假设是一个仿射函数，并且是凸的，那么在下的象也是凸的。

上面的这个结论从几何上是容易解释的：一个点在一个线段上，那么经过映射后，点的像还在线段的像上。

由上面的结论，容易得出类似的：如果是仿射函数，那么在下的原像是凸的。

两个简单例子是伸缩和平移。还有例子是，一个凸集向某几个坐标的投影是凸的，即如果是凸集，那么是凸集。

两个集合的和可以定义为：. 如果和是凸集，那么是凸的。

如果是凸的，那么他们的直积也是凸集。这个集合在线性函数的像下是和。

例如，椭球是单位Euclid球在仿射映射下的像。

半正定锥(the positive semidefinite cone)

使用记号表示对称矩阵的集合，也即

这可以看成是一个维数为的向量空间。使用表示对称半正定矩阵的集合，。使用表示对称正定矩阵的集合

集合是一个凸锥：如果，并且，那么 。由半正定矩阵的定义可知：，如果并且，那么

举个例子，对于上的半定锥

下面的图显示了这个锥的边界

多面体(Polyhedra)

多面体定义为有限个线性等式和不等式的解集。

.

因此，多面体时有限个半空间和超平面的交集。仿射集合（例如子空间、超平面、直线）、射线、线段、半空间都是多面体。

多面体是凸集。有界的多面体有时也称为多胞形。下图为五个半空间的交集定义的多面体

可以使用紧凑表达式

.

其中

,

此处的代表上的向量不等式（分量不等式）：表示.

例如，非负象限是具有非负分量的点的集合，即

非负象限既是多面体也是锥，因此被称为多面体锥

单纯形(Simplexes)

单纯形是一类重要的多面体。设个点仿射独立，即线性独立，那么这些点就决定了一个单纯形，如下

,

这个单纯形的仿射维数为，因此也称为空间的维单纯形

一些常见的单纯形

1维单纯形是一条线段；2维单纯形是一个三角形；3维单纯形是一个四面体

单位单纯形是由零向量和单位向量决定的维单纯形，可以表示为满足下列条件的向量的集合：

概率单纯形是由单位向量决定的维单纯形，可以表示为满足下列条件的向量的集合。概率单纯形中的向量对应于含有个元素的集合的概率分布，可理解为第个元素的概率

使用多面体描述单纯形

为了用多面体来描述单纯形，采用以下步骤将单纯形的定义式变形：

由单纯形的定义式可知，的充要条件是，对于某些，有，与之等价地，若定义和,

可以知道的充要条件是.

对于成立。可以注意到仿射独立意味着矩阵的秩维。因此，存在非奇异矩阵使得

对式子左乘，得到

从上面两个式子中可以看出当且仅当并且向量满足和，换言之，我们得到了的充要条件为：

这些是的线性等式和不等式，可以描述一个多面体。

多面体的凸包描述

有限集合的凸包是.

这个凸包是一个有界的多面体，但是无法简单地用多面体地定义式来描述（即难以用线性等式和不等式地集合将其表示出来）

凸包的一个扩展表示是。其中。此处考虑的非负线性组合，但是仅仅要求前个系数之和为1。此外，还可以将上式解释为点的凸包加上的锥包。上面这个凸包的表示定义了一个多面体。反之也成立，任意多面体可以表示为这样的形式

“如何表示多面体”这一问题有一些非常实用的结果，一个简单的例子是定义在范数空间的上的单位球

可以由个线性不等式(其中表示第维的单位向量)表示为多面体的形式。