西安电子科技大学算法上机报告
西安电子科技大学
(2018年度)
算法分析
实
验
报
告
实验名称：渗透实验
班级：1603012
*名：**
学号：***********
实验一：渗透问题（Percolation）
一、实验题目
使用合并-查找（union-find）数据结构，编写程序通过蒙特卡罗模拟（Monte Carlo simulation）来估计渗透阈值的值。
给定由随机分布的绝缘材料和金属材料构成的组合系统：金属材料占多大比例才能使组合系统成为电导体？给定一个表面有水的多孔渗水地形（或下面有油），水将在什么条件下能够通过底部排出（或油渗透到表面）？科学家们已经定义了一个称为渗透（percolation）的抽象过程来模拟这种情况。
模型：我们使用N×N网格点来模型一个渗透系统。每个格点或是open格点或是blocked
格点。一个full site是一个open格点，它可以通过一连串的邻近（左，右，上，下）open格点连通到顶行的一个open格点。如果在底行中有一个full site格点，则称系统是渗透的。（对于绝缘/金属材料的例子，open格点对应于金属材料，渗透系统有一条从顶行到底行的金属路径，且full sites格点导电。对于多孔物质示例，open格点对应于空格，水可能流过，从而渗透系统使水充满open格点，自顶向下流动。）
问题：在一个著名的科学问题中，研究人员对以下问题感兴趣：如果将格点以空置概率p 独立地设置为open格点（因此以概率1-p被设置为blocked格点），系统渗透的概率是多少？当p = 0时，系统不会渗出; 当p=1时，系统渗透。下图显示了20×20随机网格和100×100随机网格的格点空置概率p与渗滤概率。
当N足够大时，存在阈值p*，使得当p
Percolation数据类型：模型化一个Percolation系统，创建含有以下API的数据类型Percolation。public class Percolation {
public Percolation(int N) // create N-by-N grid, with all sites blocked
public void open(int i, int j) // open site (row i, column j) if it is not already
public boolean isOpen(int i, int j) // is site (row i, column j) open?
public boolean isFull(int i, int j) // is site (row i, column j) full?
public boolean percolates() // does the system percolate?
public static void main(String[] args) // test client, optional
}
约定行i列j下标在1和N之间，其中(1, 1)为左上格点位置：如果open(), isOpen(), or isFull()不在这个规定的范围，则抛出IndexOutOfBoundsException例外。如果N≤ 0，构造函数应该抛出IllegalArgumentException例外。构造函数应该与N2成正比。所有方法应该为常量时间加上常量次调用合并-查找方法union(), find(), connected(), and count()。
蒙特卡洛模拟（Monte Carlo simulation）.要估计渗透阈值，考虑以下计算实验：•初始化所有格点为blocked。
•重复以下操作直到系统渗出：
o在所有blocked的格点之间随机均匀选择一个格点(row i, column j)。
o设置这个格点(row i, column j)为open格点。
•open格点的比例提供了系统渗透时渗透阈值的一个估计。
例如，如果在20×20的网格中，根据以下快照的open格点数，那么对渗滤阈值的估计是204/400 = 0.51，因为当第204个格点被open时系统渗透。
50 open sites100 open sites150 open sites204 open sites
通过重复该计算实验T次并对结果求平均值，我们获得了更准确的渗滤阈值估计。令x t是第t次计算实验中open格点所占比例。样本均值μ提供渗滤阈值的一个估计值；样本标准差σ测量阈值的灵敏性。
μ=x1+x2+⋯+x T
T , σ2=(x1−μ)2+(x2−μ)2+⋯+(x T−μ)2
T−1
假设T足够大（例如至少30），以下为渗滤阈值提供95％置信区间：
[μ−
√T μ
√T
]
我们创建数据类型PercolationStats来执行一系列计算实验，包含以下API。
public class PercolationStats {
public PercolationStats(int N, int T) // perform T independent computational experiments on an N-by-N grid
public double mean() // sample mean of percolation threshold
public double stddev() // sample standard deviation of percolation threshold public double confidenceLo() // returns lower bound of the 95% confidence interval public double confidenceHi() // returns upper bound of the 95% confidence interval public static void main(String[] args) // test client, described below
}
在N≤ 0或T≤ 0时，构造函数应该抛出https://www.docsj.com/doc/2a19377912.html,ng.IllegalArgumentException例外。
此外，还包括一个main( )方法，它取两个命令行参数N和T，在N×N网格上进行T次独立的计算实验（上面讨论），并打印出均值μ、标准差σ和95％渗透阈值的置信区间。使用标准库中的标准随机数生成随机数；使用标准统计库来计算样本均值和标准差。Example values after creating PercolationStats(200, 100)
mean() = 0.5929934999999997
stddev() = 0.00876990421552567
confidenceLow() = 0.5912745987737567
confidenceHigh() = 0.5947124012262428
Example values after creating PercolationStats(200, 100)
mean() = 0.592877
stddev() = 0.009990523717073799
confidenceLow() = 0.5909188573514536
confidenceHigh() = 0.5948351426485464
Example values after creating PercolationStats(2, 100000)
mean() = 0.6669475
stddev() = 0.11775205263262094
confidenceLow() = 0.666217665216461
confidenceHigh() = 0.6676773347835391
运行时间和内存占用分析。
使用quick-find算法（QuickFindUF.java from algs4.jar）实现Percolation数据类型。进行实验表明当N加倍时对运行时间的影响；使用近似表示法，给出在计算机上的总时间，它是输入N和T的函数表达式。
使用weighted quick-union算法（WeightedQuickUnionUF.java from algs4.jar）实现Percolation 数据类型。进行实验表明当N加倍时对运行时间的影响；使用近似表示法，给出在计算机上的总时间，它是输入N和T的函数表达式。
二、算法设计
程序要求实现对一个NxN矩阵的连通性判断问题,则可以使用quick-find算法和加权quick-union算法来实现，因为算法中的数组是一维的，所以首要解决的问题就是将NxN矩阵中的点经过变换转换到一维数组中对应的位置来完成之后的算法求解。
将它们在连通分量数组中的编号依次设置为0~NxN-1。为了之后检验连通性的问题，有一个非常巧妙的方法。抽象出在矩阵的顶部有一个单独的注水口，它和第一行的所有点都是连通的，在矩阵的底部有一个出水口，它和最后一行的所有点是连通的，并分别将注水口和出水口在连通分量数组中的编号设为NxN和NxN+1。按照题目的要求每次随机打开矩阵中的一个点，然后判断与它邻近的点（上下左右）是否已经被打开，若已经打开就将它们连接起来。那么每次打开一个新的结点之后检验连通性,只需要检验注水口和出水口是否连通即可。
具体设计：
设计Percolation类，分别使用quick-find和weight quick-union算法进行合并。Percolation 类中设计open方法打开一个点，并将该点与其它相邻的点合并。
public class Percolation {
private int matrixLength; //网格大小
private boolean[] matrix; //记录方格是否打开数组
private QuickFindUF qu; //合并查找类变量
//或者：private WeightedQuickUnionUF wqu;
private int virtualTop; //注水口
private int virtualbottom; //出水口
public Percolation(int N){
if (N <= 0) {
throw new IllegalArgumentException("length must be positive");
}
matrixLength = N;
virtualTop = matrixLength * matrixLength;
virtualbottom = matrixLength * matrixLength + 1;
matrix = new boolean[N * N];
qu = new QuickFindUF(N * N + 2);
}
//检查边界
private void checkValidIndex(int row,int col){
if(row <= 0 || row >matrixLength){
throw new IndexOutOfBoundsException("row index out of bounds"); }
if(col <= 0 || col >matrixLength){
throw new IndexOutOfBoundsException("col index out of bounds"); }
}
//计算点(row i, col j)的一维坐标
private int rowCol_to_real(int row,int col){
return (row - 1) * matrixLength + col - 1;
}
//打开一个点
public void open(int row,int col){
checkValidIndex(row, col); //检查边界
int real = rowCol_to_real(row, col); //转换成一维坐标
if (matrix[real]) {
return; //如果已经是打开的，就直接返回 }
matrix[real] = true;
if (row == 1) { //如果是第一行的情况，那么让他连接top的虚拟点 qu.union(real, virtualTop);
}
if (row == matrixLength) { //如果是最后一行的情况，那么让他连接bottom的虚拟点
qu.union(real, virtualbottom);
}
int neighbor; //记录相邻点的坐标
//判断周围的四个点是否是打开的，如果是的话就连接
if (row > 1) { // up
neighbor = rowCol_to_real(row - 1, col);
if (matrix[neighbor]) {
qu.union(real, neighbor);
}
}
if (row < matrixLength) { // down
neighbor = rowCol_to_real(row + 1, col);
if (matrix[neighbor]) {
qu.union(real, neighbor);
}
}
if (col > 1) { // left
neighbor = rowCol_to_real(row, col - 1);
if (matrix[neighbor]) {
qu.union(real, neighbor);
}
}
if (col < matrixLength) { // right
neighbor = rowCol_to_real(row, col + 1);
if (matrix[neighbor]) {
qu.union(real, neighbor);
}
}
}
public boolean isOpen(int row,int col){ //判断这个点是不是已打开的 checkValidIndex(row, col);
return matrix[rowCol_to_real(row, col)];
}
public boolean isPercolated(){ //判断网格是否渗透 return qu.isConnect(virtualTop, virtualbottom);
}
}
QuickFindUF算法核心：每个点所在连通分量记录在以该点为下标的数组中，find方法的复杂度低，但合并时要遍历数组中的所有点，将其中一个连通分量中所有点的连通分量记录改为另一个连通分量，union方法的复杂度高。
public int find(int p) { //由标号找该点所在连通分量
return id[p];
}
public void union(int p,int q){ //合并两个连通分量
int pID=find(p);
int qID=find(q);
if(pID==qID){
return;
}
for(int i=0;i if(id[i]==pID) id[i]=qID; count--; } WeightedQuickUnionUF算法核心：以每个点为下标的数组中记录该点的父亲节点，由父亲节点找到根节点，根节点为该连通分量的标记；增加size数组记录每个连通分量的大小，在union时比较两个连通分量的size的大小，将小连通分量连接到大连通分量上，以此来减小树的高度减少查找根节点的时间。 public int find(int p) {//复杂度为两倍的树的高度h 即2h while(p!=id[p]){ p=id[p]; } return p; } public void union(int p,int q){//不计算find的情况下union的算法复杂度为1 int i=find(p); int j=find(q); if(i==j){ return; } if(sz[i] id[i]=j; sz[j]+=sz[i]; } else{ id[j]=i; sz[i]+=sz[j]; } count--; } 三、实验结果及分析 1.QuickFindUF合并查找： 通过以上数据分析： N一定时，运行时间与T成正比；T一定时，运行时间与N^4成正比；所以用quick-find 方法解决渗透问题的时间成长量级为：~N^4T 2.WeightedQuickUnionUF算法： N一定时，运行时间与T成正比；T一定时，运行时间与lgN2成正比；所以用quick-find 方法解决渗透问题的时间成长量级为：~lgN2T 两种算法均得出渗透问题的阈值约为0.59。 （二）几种排序算法的实验性能比较 一、实验题目 实现插入排序（Insertion Sort，IS），自顶向下归并排序（Top-down Mergesort，TDM），自底向上归并排序（Bottom-up Mergesort，BUM），随机快速排序（Random Quicksort，RQ），Dijkstra 3-路划分快速排序（Quicksort with Dijkstra 3-way Partition，QD3P）。在你的计算机上针对不同输入规模数据进行实验，对比上述排序算法的时间及空间占用性能。要求对于每次输入运行10次，记录每次时间，取平均值。 二、算法设计 1.每种排序算法均实现下列模板中的各个方法： public class Example { public static void sort(Comparable[] a) {} private static boolean less(Comparable v,Comparable w) { return https://www.docsj.com/doc/2a19377912.html,pareTo(w)<0; } private static void exch(Comparable[] a,int i,int j) { Comparable t=a[i];a[i]=a[j];a[j]=t; } private static void show(Comparable[] a) { for(int i=0;i System.out.println(a[i]+" "); System.out.println(); } public static boolean isSorted(Comparable[] a) { for(int i=0;i if(less(a[i],a[i-1])) return false; return true; } } 参与排序的数据均实现Comparable接口。 2.插入排序算法： public static void sort(Comparable[] a) { int N=a.length; for(int i=1;i for(int j=i;j>0&&less(a[j],a[j-1]);j--) exch(a,j,j-1); } } 从i=0开始依次取i，将a[i]插入到已经部分有序的a[0]~a[i-1]的合适的位置。 3.自顶向下排序算法： private static void sort(Comparable[] a,int lo,int hi) { if(hi<=lo) return; int mid=lo+(hi-lo)/2; sort(a,lo,mid); sort(a,mid+1,hi); merge(a,lo,mid,hi); } 在sort方法中递归地调用sort方法将大数组二分为两个小数组直至两个小数组大小为1，再在递归返回时调用merge方法将已经有序的两个小数组合并成一个较大的有序数组。 public static void merge(Comparable[] a,int lo,int mid,int hi) { int i=lo,j=mid+1; for(int k=lo;k<=hi;k++) aux[k]=a[k]; for(int k=lo;k<=hi;k++) if(i>mid) a[k]=aux[j++]; else if(j>hi) a[k]=aux[i++]; else if(less(aux[j],aux[i])) a[k]=aux[j++]; else a[k]=aux[i++]; } merge方法不断从两个数组中取出数据进行比较，较小的数据插入到辅助数组中并取该较小数据所在数组的下一个数据继续比较，当有某个数组中的数据取完时则将另一个数组中剩下的数据全部放到辅助数组中，完成两个有序数组合为一个有序数组的排序。 4.自底向上排序算法： public static void sort(Comparable[] a) { int N=a.length; aux=new Comparable[N]; for(int sz=1;sz for(int lo=0;lo merge(a,lo,lo+sz-1,Math.min(lo+sz*2-1, N-1)); } 从数组大小size为1开始将相邻的大小为size的两个数组用merge方法归并排序，直至辅助数组中的数排完，辅助数组成为每2*size部分有序的数组；增大数组大小size 为上一次归并的两个数组大小size的两倍，继续用merge方法将相邻的大小为size的数组排序；增大size重复上一步直至将整个辅助数组排成有序的。merge方法同上。 5.随机快速排序算法： private static void sort(Comparable[] a,int lo,int hi) { if(hi<=lo) return; int j=partition(a,lo,hi); sort(a,lo,j-1); sort(a,j+1,hi); } private static int partition(Comparable[] a,int lo,int hi) { int i=lo,j=hi+1; Comparable v=a[lo]; while(true) { while(less(a[++i],v)) if(i==hi)break; while(less(v,a[--j])) if(j==lo)break; if(i>=j)break; exch(a,i,j); } exch(a,lo,j); return j; } Partition方法以传入的数组的第一个数据为切分数据，比切分数据小的数据全部移动到切分数据左边，比切分数据大的全部移动到切分数据右边，将切分数据移动到正确的位置并返回该位置j。 sort方法调用Partition方法得到切分数据a[j]，再递归地对a[j]左右两边的数组调用sort方法直至传入sort方法的数组大小为1（大小为1的数组恒有序），整个数组排序完成。 三、实验结果及分析 由以上实验结果可以看出插入排序花的时间最多，其他四种排序算法时间开销相差不大，比插入排序快很多，随机快排排序最快。 （三）地图路由（Map Routing） 一、实验题目 实现经典的Dijkstra最短路径算法，并对其进行优化。这种算法广泛应用于地理信息系统（GIS），包括MapQuest和基于GPS的汽车导航系统。 地图：本次实验对象是图maps或graphs，其中顶点为平面上的点，这些点由权值为欧氏距离的边相连成图。可将顶点视为城市，将边视为相连的道路。为了在文件中表示地图，我们列出了顶点数和边数，然后列出顶点（索引后跟其x和y坐标），然后列出边（顶点对），最后列出源点和汇点。例如，如下左图信息表示右图： Dijkstra算法：Dijkstra算法是最短路径问题的经典解决方案。它在教科书第21章中有描述。基本思路不难理解。对于图中的每个顶点，我们维护从源点到该顶点的最短已知的路径长度，并且将这些长度保持在优先队列（priority queue, PQ）中。初始时，我们把所有的顶点放在这个队列中，并设置高优先级，然后将源点的优先级设为0.0。算法通过从PQ 中取出最低优先级的顶点，然后检查可从该顶点经由一条边可达的所有顶点，以查看这条边是否提供了从源点到那个顶点较之之前已知的最短路径的更短路径。如果是这样，它会降低优先级来反映这种新的信息。 这里给出了Dijkstra算法计算从0到5的最短路径0-1-2-5的详细过程。 process 0 (0.0) lower 3 to 3841.9 lower 1 to 1897.4 process 1 (1897.4) lower 4 to 3776.2 lower 2 to 2537.7 process 2 (2537.7) lower 5 to 6274.0 process 4 (3776.2) process 3 (3841.9) process 5 (6274.0) 该方法计算最短路径的长度。为了记录路径，我们还保持每个顶点的源点到该顶点最短路径上的前驱。文件Euclidean Graph.java，Point.java，IndexPQ.java，IntIterator.java和Dijkstra.java提供了针对map的Dijkstra算法的基本框架实现，你应该以此作为起点。客户端程序ShortestPath.java求解一个单源点最短路径问题，并使用图形绘制了结果。客户端程序Paths.java求解了许多最短路径问题，并将最短路径打印到标准输出。客户端程序Distances.java求解了许多最短路径问题，仅将距离打印到标准输出。 目标：优化Dijkstra算法，使其可以处理给定图的数千条最短路径查询。一旦你读取图（并可选地预处理），你的程序应该在亚线性时间内解决最短路径问题。一种方法是预先计算出所有顶点对的最短路径；然而，你无法承受存储所有这些信息所需的二次空间。你的目标是减少每次最短路径计算所涉及的工作量，而不会占用过多的空间。建议你选择下面的一些潜在想法来实现，或者你可以开发和实现自己的想法。 想法1：Dijkstra算法的朴素实现检查图中的所有V个顶点。减少检查的顶点数量的一种策略是一旦发现目的地的最短路径就停止搜索。通过这种方法，可以使每个最短路径查询的运行时间与E' log V'成比例，其中E'和V'是Dijkstra算法检查的边和顶点数。然而，这需要一些小心，因为只是重新初始化所有距离为∞就需要与V成正比的时间。由于你在不断执行查询，因而只需重新初始化在先前查询中改变的那些值来大大加速查询。 想法2：你可以利用问题的欧式几何来进一步减少搜索时间，这在算法书的第21.5节描述过。对于一般图，Dijkstra通过将d[w]更新为d[v] + 从v到w的距离来松弛边v-w。对于地图，则将d[w]更新为d[v] + 从v到w的距离+ 从w到d的欧式距离 从v到d的欧式距离。这种方法称之为A*算法。这种启发式方法会有性能上的影响，但不会影响正确性。 想法3：使用更快的优先队列。在提供的优先队列中有一些优化空间。你也可以考虑使用Sedgewick程序20.10中的多路堆。 测试：美国大陆文件usa.txt包含87,575个交叉口和121,961条道路。图形非常稀疏-平均的度为2.8。你的主要目标应该是快速回答这个网络上的顶点对的最短路径查询。你的算法可能会有不同执行时间，这取决于两个顶点是否在附近或相距较远。我们提供测试这两种情况的输入文件。你可以假设所有的x和y坐标都是0到10,000之间的整数。 二、算法设计 因为要实现地图路由,地图是一个加权无向图，图中所用的边为加权无向边，实现一个加权无向图的数据结构,初始化地图后，利用Dijkstra算法来找出最短路径。 经典的Dijkstra算法是初始化时就把所有节点的最短路径找出来了，程序优化则可以重用代码（想法1），多次查询两节点间最短路径用同一对象，并且每次查询当找到目标节点后便停止，不再遍历其他的节点。然后将上一次查询改变的成员变量部分还原，以供下一次的查询使用，这样便大大的优化了传统的Dijkstra算法。优化方法采用的想法1减少检查的顶点数量,一旦发现目的地的最短路径就停止搜索。 通过这种方法使每个最短路径查询的运行时间与Elog V成比例,在不断执行查询，每次重新初始化在先前查询中改变的那些值来大大加速查询。 public class DijkstraUndirectedSP { private double[] distTo; private Edge[] edgeTo; private IndexMinPQ private EdgeWeightedGraph mGraph; private int from; public DijkstraUndirectedSP(EdgeWeightedGraph G) { //设置算法的起点 public void setFrom(int from) {} //更新到节点的最短路径 private void relax(Edge e, int v) {} //获取到某一节点的最短距离 public double distTo(intv) {} //在这里才执行相关的路径初始化 public boolean hasPathTo(intv) {} //还原上一次查询被修改的部分 public void itijkstra() {} //遍历到一个节点所经过的边 public Iterable } 想法1实现： 调用setFrom函数设置算法的起点,每次设置新的起点后,调用initDijkstra方法还原上次查询操作被修改的数据。 //设置算法的起点 public void setFrom(int from) { / /开始新的一-次查询后把上一次修改过的部分还原初始化 initDijkstra(); this.from = from; distTo[from] = 0.0; pq. insert(from, distTo[from]); } //还原上一次查询被修改的部分 public void initDijkstra(){ for (int i = 0; i < mGraph.v(); i++) { if (pq. contains(i)) { pq.delete(i); } if (edgeTo[i]l=nul1) { edgeTo[i]=null; } if (!Double. isInfinite(distTo(i))) { distTo[i]=Double. POSITIVE_ INFINITY; } } } 当执行查询源点到目的地的最短路径时调用hasPathTo方法来查询，不断的从优先队列pq中找出当前最短路径最小的节点,然后对此节点的邻节点进行relax松弛。 如果从优先队列中得到的最小权值点就是目标节点的话即为找到两节点的最短路劲退出函数循环, //执行相关的路径初始化 public boolean hasPathTo(int v) { while (!pq.isEmpty()) { int X= pq.delMin(); //找到目标节点就直接退出循环，并初始化已经被修改的值 if (x==v) { return true; } for (Edge e : mGraph. adj(x)) relax(e, x); } return distTo[v] < Double. POSITIVE INFINITY; } 在主函数中从文本文件中读取相应的数据初始化所有顶点，无向边，构造出加权无向图。: 三、实验结果 上机心得体会 这学期算法上机三道大题各对应了几个章节的内容,通过这次的上机作业对面向对象编程思想有了更加深入的了解，熟悉了连通性问题中quick-find和加权quick-union算法数据结构。对各种排序算法的性能,适用情况有了进一步的认识。熟悉了基于加权无向图的Dijkstra 算法,优先级队列的使用，并且自己思考对传统的Dijkstra算法进行了优化，无论是时间上还是空间上性能都有了很大的提升。这三次试验大大加深了我对算法课上学习内容的理解，熟悉了基本的算法与数据结构，同时综合编程能力有了很大的提升，最后感谢老师每一次上机的耐心指导。 西安电子科技大学软件学院工程硕士论文写作指导 （技术报告类） 版本：0.5 作者：鲍亮 日期：2012年9月20日 西安电子科技大学 学位论文创新性声明 秉承学校严谨的学分和优良的科学道德，本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名：日期 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后结合学位论文研究课题再攥写的文章一律署名单位为西安电子科技大学。 （保密的论文在解密后遵守此规定） 本学位论文属于保密，在年解密后适用本授权书。 本人签名：日期 导师签名：日期 什么是技术报告类论文 软件工程专业工程硕士学位论文可以提交技术报告类学位论文，该类学位论文以作者从事的软件系统研发项目中的技术工作为主体内容进行撰写，需要重点突出关键技术的突破情况。下面进行详细说明。 志鹏学术 论文写作 期刊发表 微‖信号huili636 技术报告（也称为科学报告）是描述技术或科学研究过程、进展或结果的文档，或者是对技术或科学研究问题目前状态的报告。技术报告通常也包括研究的建议和结论。技术报告需要以技术问题为主线，详细报告技术问题的出现场景，解决问题时采用的关键技术及效果等。在学位论文中，作者应结合具体项目，系统论述软件系统的需求、项目的完成情况，并对关键技术进行详细介绍，可包括： (1)系统的需求分析，包括功能需求与非功能性需求； (2)根据需求，说明在实现这些功能时会面临的关键技术及技术指标； (3)针对每项关键技术，进行详细论述，内容需要涵盖：关键技术的研究方案、 关键技术的攻关情况和技术指标的实现情况。 在撰写技术报告类学位论文时，应注重与实际项目的结合，避免大量空谈、科普相关技术；同时应注意结合作者本人实际工作选择需要重点论述的问题和相关技术，核心内容论述要充分、深入、具体，避免全面但蜻蜓点水似的泛泛而谈。 论文题目一般为“XXX系统中XXX技术的研究”，即题目中应给出论文相关具体项目名称，如“在线交易系统中数据持久化技术的研究”等。 反走样：在光栅显示器上显示图形时，直线段或图形边界或多或少会呈锯齿状。原因是图形信号是连续的，而在光栅显示系统中，用来表示图形的却是一个个离散的象素。这种用离散量表示连续量引起的失真现象称之为走样；用于减少或消除这种效果的技术称为反走样 反走样方法主要有：提高分辨率、区域采样和加权区域采样 提高分辨率：把显示器分辨率提高一倍，锯齿宽度也减小了一倍，所以显示出的直线段看起来就平直光滑了一些。这种反走样方法是以4倍的存储器代价和扫描转换时间获得的。因此，增加分辨率虽然简单，但是不经济的方法，而且它也只能减轻而不能消除锯齿问题。 区域采样方法：假定每个象素是一个具有一定面积的小区域，将直线段看作具有一定宽度的狭长矩形。当直线段与象素有交时，求出两者相交区域的面积，然后根据相交区域面积的大小确定该象素的亮度值。 加权区域采样：相交区域对象素亮度的贡献依赖于该区域与象素中心的距离。当直线经过该象素时，该象素的亮度F是在两者相交区域A′上对滤波器进行积分的积分值 刚体：平移和旋转的组合，保持线段的长度，保持角的大小，图形不变形，为刚体变化 仿射：旋转、平移、缩放的组合为仿射变换，平行边仍然平行，错切变换也为仿射变换 较高次数逼近的三种方法：1将y和z直接表示成x的显函数即y=f(x) z=g(x)2用一个形如f(x,y,z)=0的隐式方程的解来表示曲线3曲线的参数表示 前两方法缺点：1由一个x值不能得到多个y值；这一定义不是旋转不变的；描述具有与坐标轴垂直的切线的曲线是困难的2给定方程的解可能更多；曲线段做链接时，很难确定他们的切线方向在连接点上是否相等 参数表示为什么要选择三做参数：1低于三次的函数控制曲线形状时不够灵活，高于三次的曲线会增加不必要的摆动其增加计算量2三次参数曲线是三维空间中次数最低的非平面曲线3定义高次曲线需要更多条件，这样在交互生成时会造成曲线的摆动而难以控制 G0连续：两条曲线段拼接成一条曲线 G1连续：两条曲线段拼接点处切向量方向相同。若相等（方向、大小）－C1 Gn连续：两条曲线段拼接点处切向量的阶导数方向相同。n阶导数相等－Cn B样条曲线优势：1四点加权求和，调和函数非负且和为1，具有凸壳特性2可证明Qi和Qi+1在连接点处连续3曲线段三次函数，所以整个曲线具有连续4凸壳的对曲线裁剪有用 中点生成算法： TBRL中点生成算法： 西安电子科技大学出版社《计算方法》任传祥等编著第九章计算方法上机参考答案 实验一，算法一 #include #include 数字信号处理 实验报告 班级：**** 姓名：郭** 学号：***** 联系方式：***** 西安电子科技大学 电子工程学院 绪论 数字信号处理起源于十八世纪的数学，随着信息科学和计算机技术的迅速发 展，数字信号处理的理论与应用得到迅速发展，形成一门极其重要的学科。当今 数字信号处理的理论和方法已经得到长足的发展，成为数字化时代的重要支撑， 其在各个学科和技术领域中的应用具有悠久的历史，已经渗透到我们生活和工作 的各个方面。 数字信号处理相对于模拟信号处理具有许多优点，比如灵活性好，数字信号 处理系统的性能取决于系统参数，这些参数很容易修改，并且数字系统可以分时 复用，用一套数字系统可以分是处理多路信号；高精度和高稳定性，数字系统的 运算字符有足够高的精度，同时数字系统不会随使用环境的变化而变化，尤其使 用了超大规模集成的DSP 芯片，简化了设备，更提高了系统稳定性和可靠性；便 于开发和升级，由于软件可以方便传送，复制和升级，系统的性能可以得到不断 地改善；功能强，数字信号处理不仅能够完成一维信号的处理，还可以试下安多 维信号的处理；便于大规模集成，数字部件具有高度的规范性，对电路参数要求 不严格，容易大规模集成和生产。 数字信号处理用途广泛，对其进行一系列学习与研究也是非常必要的。本次 通过对几个典型的数字信号实例分析来进一步学习和验证数字信号理论基础。 实验一主要是产生常见的信号序列和对数字信号进行简单处理，如三点滑动 平均算法、调幅广播（AM ）调制高频正弦信号和线性卷积。 实验二则是通过编程算法来了解DFT 的运算原理以及了解快速傅里叶变换 FFT 的方法。 实验三是应用IRR 和FIR 滤波器对实际音频信号进行处理。 实验一 ●实验目的 加深对序列基本知识的掌握理解 ●实验原理与方法 1.几种常见的典型序列： 0()1, 00,0(){()()(),()sin()j n n n n u n x n Ae x n a u n a x n A n σωω?+≥<====+单位阶跃序列：复指数序列：实指数序列：为实数 正弦序列： 西安电子科技大学 (2018年度) 算法分析 实 验 报 告 实验名称：渗透实验 班级：1603012 *名：** 学号：*********** 实验一：渗透问题（Percolation） 一、实验题目 使用合并-查找（union-find）数据结构，编写程序通过蒙特卡罗模拟（Monte Carlo simulation）来估计渗透阈值的值。 给定由随机分布的绝缘材料和金属材料构成的组合系统：金属材料占多大比例才能使组合系统成为电导体？给定一个表面有水的多孔渗水地形（或下面有油），水将在什么条件下能够通过底部排出（或油渗透到表面）？科学家们已经定义了一个称为渗透（percolation）的抽象过程来模拟这种情况。 模型：我们使用N×N网格点来模型一个渗透系统。每个格点或是open格点或是blocked 格点。一个full site是一个open格点，它可以通过一连串的邻近（左，右，上，下）open格点连通到顶行的一个open格点。如果在底行中有一个full site格点，则称系统是渗透的。（对于绝缘/金属材料的例子，open格点对应于金属材料，渗透系统有一条从顶行到底行的金属路径，且full sites格点导电。对于多孔物质示例，open格点对应于空格，水可能流过，从而渗透系统使水充满open格点，自顶向下流动。） 问题：在一个著名的科学问题中，研究人员对以下问题感兴趣：如果将格点以空置概率p 独立地设置为open格点（因此以概率1-p被设置为blocked格点），系统渗透的概率是多少？当p = 0时，系统不会渗出; 当p=1时，系统渗透。下图显示了20×20随机网格和100×100随机网格的格点空置概率p与渗滤概率。 当N足够大时，存在阈值p*，使得当p 课程设计说明书 设计题目：操作系统课程设计 班级：信息管理与信息系统2011级 学号： 姓名： 山东科技大学 2013年12 月25 日 课程设计任务书 学院信息科学与工程专业信息学管理与信息系统班级2011-1 姓名 一、课程设计题目：操作系统课程设计 二、课程设计主要参考资料 （1）Abraham Silberschatz & Peter Baer Galvin & Greg Gagne. Operating System Concepts（第七版影印版）. 高等教育出版社. 2007.3. （2）计算机操作系统（第三版）西安电子科技大学出版社 （3） 三、课程设计应解决的主要问题： （1）CPU调度算法的模拟实现 （2）死锁相关算法的实现 （3）磁盘调度算法的实现 四、课程设计相关附件（如：图纸、软件等）： （1）程序源代码 （2） 五、任务发出日期：2013-10-1 课程设计完成日期：2014-1-1 指导教师签字： 指导教师对课程设计的评语成绩： 指导教师签字： 年月日 设计1 CPU调度算法的模拟实现 一、设计目的 1、根据系统的资源分配策略所规定的资源分配算法 2、利用编程语言，模拟实现先来先服务（FCFS）、最短作业优先（非抢占SJF）、非抢占优先调度算法、时间片轮转调度算法（RR） 3、针对模拟进程，利用CPU调度算法进行调度 4、进行算法评价，计算平均周转时间和平均等待时间 二、设计要求 1、调度所需的进程参数由输入产生（手工输入或者随机数产生） 2、输出调度结果 3、输出算法评价指标 三、设计说明 1、定义public类： class program{ public: char name;//进程名 int atime;//进程到达的时间 int stime;//进程服务的时间 int btime;//进程开始执行的时间 int ftime;//进程完成的时间 int rtime;//进程的周转时间 float qrtime;//进程的带权周转时间 }; 2、冒泡排序： class program t; for( i=1;i 西安电子科技大学作业题目算法设计技术与方法实验报告 专业名称计算机系统结构 班级 学生姓名 学生学号 二0一四年十二月 ● 1.分别实现多项式求值的四种运算，若针对不同规模的输入值a，各算法的运行时间，问题规模n分别取10，50，100，150，200，300，400，500，10000，20000，50000，100000时绘制四种算法运行时间的比较图。 实验代码： num=[10 50 100 150 200 300 400 500 10000 20000 50000 100000]; x=input('please enter x:') for m=1:12 a=rand(1,num(m)+1); tic; p1(m)=polyval(a,x); t1(m)=toc; tic; p2(m)=0; for i=1:num(m)+1 p2(m)=p2(m)+a(i)*x^(i-1); t2(m)=toc; end tic; p3(m)=a(1); q=1; for j=2:num(m)+1 q=q*x; p3(m)=p3(m)+a(j)*q; t3(m)=toc; end tic; p4(m)=a(num(m)+1); for k=1:num(m); p4(m)=x*p4(m)+a(num(m)+1-k); t4(m)=toc; end end semilogx(num,t1,'b+',num,t2,'gx',num,t3,'r*',num,t4,'ko'); xlabel('num=10,50,100,150,200,300,400,500,10000,20000,50000,100000' ) ; ylabel('time'); title('The comparison chart of four different methods for polyval') 运行结果： 操作系统程序设计课程设计报告 课题: 请求分页式存储管理页面置换算法姓名： 学号： 同组姓名： 专业班级： 指导教师： 设计时间： 目录 1. 系统描述 (3) 2. 分析与设计 (3) 2.1.系统功能模块图 (3) 2.2.系统文件结构描述 (3) 2.3.系统功能流程图 (4) 2.4．UI设计以及操作说明： (4) 2.5.测试数据及期望 (11) 3.系统测试 (12) 4.总结心得体会 (12) 5.参考文献 (13) 6.核心代码 (13) 1. 系统描述 系统使用.net framework 4.0开发的，图形用户界面使用winform程序设计，功能模块分别实现了请求分页式存储管理的LRU算法，FIFO 算法。 通过虚拟系统存储的概念和实现方法，进行运行的时候不需要把所有页面都装入内存中，只需要将部分页面调入内存，就可以运行。在运行过程中，若要访问的页面不在内存中，则需用请求调入的功能将其装入内存中，如果此时内存中没有空白的物理块，就通过页面置换功能淘汰一个页面，根据LRU,FIFO两种淘汰算法来进行页面置换，并能计算出FIFO，LRU两种算法在不同内存容量中的的命中率。 系统运行时通过输入访问内存的顺序，以及分配的内存页面数，来进行二种算法的页面置换，实现了虚拟存储的功能和特点。 2. 分析与设计 2.1.系统功能模块图 图4.1 页式存储管理模块划分 2.2.系统文件结构描述 2.3.系统功能流程图 开始 还有指令？ 计算页号 找到了吗？ 新页进入计算过程数组第一位，其余为一次下移 计算命中率 结束Y N N Y FIFO 开始 还有指令？ 计算页号 找到了吗？ 比较现有页面计数项的大小，新页面替换最大项页面 计算命中率 结束 Y N N Y LRU 2.4．UI 设计以及操作说明： 主窗体： 一、控制对象： 1.2.1 被控对象 本次设计为软件仿真，通过PID算法控制系统在单位阶跃信号u(t)的激励下产生的零状态响应。传递函数表达式为： 1.2.2 设计规定 规定系统可以快速响应，并且可以迅速达成盼望的输出值。 本次设计选用PID控制算法，PID控制器由比例控制单元P、积分控制单元I和微分控制单元D组成。其输入与输出的关系为 式中，为比例系数；为积分时间常数；为微分时间常数。 二、控制规定分析： 设定目的温度，使温度呈单位阶跃形式在目的温度处趋于震荡稳定。使系统可以在任意设定的目的温度下，从现有温度达成目的温度，并趋于稳定状态。 三、可行性分析: 参考国内外的技术资料，可以通过计算机仿真技术实现该模拟温度闭环控制系统；运用C语言实现基于PID算法的模拟温度闭环控制系统。 四、总体设计： 4.1控制系统组成 控制系统框图如图1所示。 图1 控制系统框图 4.2工作原理： 在图1 所示系统中，D(z)为该系统的被控对象，零状态下，输入为单位阶跃信号R 的输出反馈给输入。在参数给定值R 的情况下，给定值R 与反馈值比较得到偏差 ，通过PID 调节器运算产生相应的控制量，PID 调节器的输出作为被控对象的输入信号，是输入的数值稳定在给定值R 。 4.3模拟PID 控制算法原理： 在模拟系统中PID 算法的表达式为： 式中，P(t)为调节器输出信号，e(t)为调节器偏差信号，它等于测量值与给定值之差；Kp 为调节器的比例系数，1/T1为调节器的积分时间， Td 为调节器的微分时间。 在计算机控制系统中，必须对上式进行离散化使其成为数字式的差分方程。将积分式和微分项近似用求和及增量式表达。即： PID 控制器 D(z) u 1(t) R + e(t) _ u(t) (完整word版)西安电子科技大学2009年计算机研究生复试上机题编辑整理： 尊敬的读者朋友们： 这里是精品文档编辑中心，本文档内容是由我和我的同事精心编辑整理后发布的，发布之前我们对文中内容进行仔细校对，但是难免会有疏漏的地方，但是任然希望（(完整word版)西安电子科技大学2009年计算机研究生复试上机题）的内容能够给您的工作和学习带来便利。同时也真诚的希望收到您的建议和反馈，这将是我们进步的源泉，前进的动力。 本文可编辑可修改，如果觉得对您有帮助请收藏以便随时查阅，最后祝您生活愉快业绩进步，以下为(完整word版)西安电子科技大学2009年计算机研究生复试上机题的全部内容。 2009年西电计算机研究生复试上机题 二月 28, 2010 by admin Problem A:请写一个程序,给出指定整数范围【a ，b】内所有的完数,一个数如果恰好等于除它本身外的所有因子之和，这个数就称为完数，例如6是完数，因为6=1+2+3.输入说明：共一组数据，为两个正整数，分别表示a和b（1〈a 2022年西安电子科技大学计算机科学与技术专业《数据结构与算法》 科目期末试卷A（有答案） 一、选择题 1、无向图G=(V，E)，其中：V={a，b，c，d，e，f}，E={(a，b)，(a， e)，(a，c)，(b， e)，(c，f)，(f，d)，(e，d)}，对该图进行深度优先遍历，得到的顶点序列正确的是 （）。 A.a，b，e，c，d，f B.a，c，f,e，b，d C.a，e，b，c，f, d D.a，e，d，f，c，b 2、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。 A.N B.2N-1 C.2N D.N-1 3、以下数据结构中，（）是非线性数据结构。 A.树 B.字符串 C.队 D.栈 4、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）。 A.仅修改队头指针 B.仅修改队尾指针 C.队头、队尾指针都可能要修改 D.队头、队尾指针都要修改 5、动态存储管理系统中，通常可有（）种不同的分配策略。 A.1 B.2 C.3 D.4 6、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行 匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别 （）。 A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝2 7、下列关于无向连通图特性的叙述中，正确的是（）。 Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1 A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ 8、设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩子，下列结论正确的是（）。 A.在树T中，X是其双亲的第一个孩子 B.在树T中，X一定无右兄弟 C.在树T中，X一定是叶结点 D.在树T中，X一定有左兄弟 9、一个具有1025个结点的二叉树的高h为（）。 A.11 B.10 C.11至1025之间 D.10至1024之间 10、下列二叉排序树中查找效率最高的是（）。 A.平衡二叉树 B.二叉查找树 C.没有左子树的二叉排序树 D.没有右子树的二叉排序树 二、填空题 11、起始地址为480，大小为8的块，其伙伴块的起始地址是______；若块大小为32，则其伙伴块的起始地址为______。 12、下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空： 目录 目录 (1) 1．课程设计目的 0 1.1编写目的 0 2．课程设计内容 0 2.1设计内容 0 3.1模块调用关系图 (2) 4．测试数据和结果 (6) 5．参考文献 (6) 6．总结 (6) 1．课程设计目的 1.1编写目的 本课程设计的目的是通过磁盘调度算法设计一个磁盘调度模拟系统, 从而使磁盘调度算法更加形象化,容易使人理解,使磁盘调度的特点更简单 明了,能使使用者加深对先来先服务算法、最短寻道时间优先算法、扫描算法以及循环扫描算法等磁盘调度算法的理解; 2．课程设计内容 2.1设计内容 系统主界面可以灵活选择某种算法,算法包括：先来先服务算法FCFS、最短寻道时间优先算法SSTF、扫描算法SCAN、循环扫描算法CSCAN; 1、先来先服务算法FCFS 这是一种比较简单的磁盘调度算法;它根据进程请求访问磁盘的先后次序进行调度;此算法的优点是公平、简单,且每个进程的请求都能依次得到处理,不会出现某一进程的请求长期得不到满足的情况;此算法由于未对寻道进行优化,在对磁盘的访问请求比较多的情况下,此算法将降低设备服务的吞吐量,致使平均寻道时间可能较长,但各进程得到服务的响应时间的变化幅度较小; 2、最短寻道时间优先算法SSTF 该算法选择这样的进程,其要求访问的磁道与当前磁头所在的磁道距 离最近,以使每次的寻道时间最短,该算法可以得到比较好的吞吐量,但却 不能保证平均寻道时间最短;其缺点是对用户的服务请求的响应机会不是 均等的,因而导致响应时间的变化幅度很大;在服务请求很多的情况下,对 内外边缘磁道的请求将会无限期的被延迟,有些请求的响应时间将不可预期; X X X X学院课程设计报告 DH密钥协商算法 课程名称：密码算法程序设计 学生姓名： 学生学号： 专业班级： 任课教师： 2014年12 月1日 目录 1. 选题背景 (1) 2. DH密钥协商算法 (1) 2.1 算法的产生 (1) 2.2 算法的描述 (2) 2.3 算法的安全性 (3) 3.DH密钥协商算法的实现 (4) 3.1 设计要求 (4) 3.1.1 功能要求 (4) 3.2 模块划分及实现 (5) 3.2.1 小素数试除 (5) 3.2.2 模重复平方法 (5) 3.2.3 Miller-Rabin检测算法 (6) 3.2.4 原根的产生 (8) 3.2.5 产生随机素数 (10) 4.测试报告 (11) 结论 (16) 参考文献 (16) 附源代码 (17) 1. 选题背景 密钥协商实际上是一个协议，它通过两个或多个成员在一个公开的信道上通信联合地建立一个秘密密钥，一般情况下，一个密钥协商方案的密钥是某个函数的值，其输入量由通信双方提供，协商过程是由一系列的顺序步骤完成的。会话密钥由每个协议参与者分别产生的参数通过一定的计算得出。常见的密钥协商协议，如IKE。 密钥协商协议的生成方式则可分为证书型和无证书型。证书型是指在会话密钥的产生过程中，由一个可信的证书中心（CA）给参与密钥协商的各方各分发一个证书，此证书中含有此方的公钥，ID及其他信息。证书型密钥协商协议的优点是提供认证，目前PKI（公钥密码体制）广泛部署，比较成熟，应用面广，且由PKG管理公私钥对有利于统一管理，缺点是计算代价大，需要一个可信的CA，同时证书还需要维护。无证书型是指各方在进行会话密钥的协商过程中不需要证书的参与，这是目前密钥协商协议的主流种类，优点是不需要CA的参与，减少了计算量，尤其是在低耗环境下应用的更多，同时安全性也不比证书型弱。几乎没有明显的缺点，只是设计一个安全的更加低耗的无证书密钥协商方案不是很容易。 现有的流行的密钥协商协议，都使用了Diffie-Hellman，它们基本上可以看成是Diffie-Hellman的扩展。也就是说，群组密钥协商协议可以理解成如何使用Diffie-Hellman来实现群的密钥交换。 2. DH密钥协商算法 2.1 算法的产生 Diffie-Hellman密钥交换协议是第一个被提出的密钥协商方案，是美国斯坦福大学的W.Diffie和M.E.Hellman于1976年提出的，它是第一个发表的公钥密码体制，Diffie-Hellman算法的唯一目的就是使两个用户能安全的交换密钥，从而得到一个共享的会话密钥（秘密密钥）。需要注意的是，该算法本身不能用于加密解密，只能用于密钥的交换，双方确定要用的密钥后，要使用其他对称密钥操作加密算法实际加密和解密消息。 目录 目录1 1．课程设计目地0b5E2R。 1.1编写目地0p1Ean。 2．课程设计内容0DXDiT。 2.1设计内容0RTCrp。 3.1模块调用关系图25PCzV。4．测试数据和结果6jLBHr。5．参考文献9xHAQX。 6．总结9LDAYt。 1．课程设计目地 1.1编写目地 本课程设计地目地是通过磁盘调度算法设计一个磁盘调度模拟系统，从而使磁盘调度算法更加形象化，容易使人理解，使磁盘调度地特点更简单明了，能使使用者加深对先来先服务算法、最短寻道时间优先算法、扫描算法以及循环扫描算法等磁盘调度算法地理解.Zzz6Z。 2．课程设计内容 2.1设计内容 系统主界面可以灵活选择某种算法，算法包括：先来先服务算法（FCFS）、最短寻道时间优先算法（SSTF）、扫描算法（SCAN）、循环扫描算法（CSCAN）.dvzfv。 1、先来先服务算法（FCFS） 这是一种比较简单地磁盘调度算法.它根据进程请求访问磁盘地先后次序进行调度.此算法地优点是公平、简单，且每个进程地请求都能依次得到处理，不会出现某一进程地请求长期得不到满足地情况.此算法由于未对寻道进行优化，在对磁盘地访问请求比较多地情况下，此算法将降低设备服务地吞吐量，致使平均寻道时间可能较长，但各进程得到服务地响应时间地变化幅度较小.rqyn1。 2、最短寻道时间优先算法（SSTF） 该算法选择这样地进程，其要求访问地磁道与当前磁头所在地磁道距离最近，以使每次地寻道时间最短，该算法可以得到比较好地吞吐量，但却不能保证平均寻道时间最短.其缺点是对用户地服务请求地响应机会不是均等地，因而导致响应时间地变化幅度很大.在服务请求很多地情况下，对内外边缘磁道地请求将会无限期地被延迟，有些请求地响应时间将不可预期.Emxvx。 【最新整理，下载后即可编辑】 Lloyd —Max 算法的总结 摘 要：本文分析模拟—数字信号转变过程中抽象信号为离散时间，幅度连续，无记忆的 随机信号的最佳量化问题。并对算法做了总结，应用MATLAB 编写程序实现该算 法，最后给出了运用该程序进行计算的几个例子。 关键词：非均匀量化，失真度，Lloyd —Max 算法 一．引言 模数转换要经过抽样，量化和编码三个步骤。如下图所示： SCH 为带限的平稳随机过程，根据抽样理论，我们可以对此随机信号进行奈圭斯特抽样抽样的输出为 。它是与 等效的离散抽样序列。经过量化器以后， 用L 个电平值来表示次 序列，然后对此L 个电平进行编码（假设为2进制码）。如果L 为2的整数幂。则每个量化电平需要的码长为： , 如果L 不是2的整数幂。则上式为 。如果L 个电平值不等概的情况下，我们可以用哈夫蔓编码（又叫熵编码）增加编码效率。 然而，量化过程用到数据的压缩，从而引进了信号的失真。这种失真即为量化失真。我们用量化误差来表示。本文的重点就是讨论如何最大限度的减小量化误差。 }K S )(t x )(nT x )(t x ) (~nT x k L R 2log =⎣⎦1log 2+=L R 二．信息论的解释 2．1．失真度D 假定抽样器的输 出序列为 ，量化器的输出序列为 。 为不同的量化值。则两个量化值的失真为： 如果p=2 ；则此失真称为均方失真。 平均失真量为： 如果x （t ）是服从概率密度函数为p （x ）的随机信号，则： 失真度D ： 如果用： 来表示。 量化噪声MSE ： 量化信噪比SNR ： 2．2．率失真函数R （D ）： 我们假定信源为无记忆，连续幅度，它的幅度概率密度函数为p （x ），则率失真函数R （D ）的表示式为： p k k k k x x x x d ~)~,(-=∑==n k k k x x d n x x d 1)~,(1)~,({}⎰+∞∞-==dx x p x x d x x d E D n n )()~,(~,( ∑⎰∑⎰==---==L k x x L k x x k k k k k k dx x p x x dx x p x x d 11211 )()~()()~,(n x x x f ~~)(+==()D n E MSE ==2~())~(22n E x E SNR ={}[])~,()(~,(~x x I MIN D R D x x d E x x P ≤=2~)~,(k k k k x x x x d -={}k x ~{}k x k x ~ 16位布斯算法乘法器和ALU Booth算法16位乘法器西安电子科技大学大三集成电路设计与集成系统专业尹俊镖 一乘法器原理分析 16位有符号乘法器可以分为三个部分:根据输入的被乘数和乘数产生部分积、部分积压缩产生和和进位、将产生的和和进位相加。这三个部分分别对应着编码方式、拓扑结构以及加法器。 被乘数X(16-bit) 符号位扩展 S01?X(17-bit)X(17-比特)0 1?X2?X MUX ADD/SUBBooth译码 &ALU(17-bit) 控制逻辑符号位扩展 S乘积(低16-bit)乘数乘积(高16-bit) 保留移出位右移2-bit 1 编码方式: 本设计采用booth2编码。 部分积是负数时S=1，部分积是正数时S=0; 当部分积是+0时，E=1，部分积是-0时，E=0，其余情况E=S取反。 2 拓扑结构: 本设计采用二进制树的拓扑结构。二进制树拓扑结构排列的较为规整，且部分积压缩的速度也非常快。 部分积压缩的目的是为了减小进位传播的延时，采用进位保留加法器，根据当前位信息产生下一位的进位，仅仅产生而没有进位行波传播，这样就可以把当前的多位压缩到较少的位数。经过几次压后，把部分积压缩成和以及进位。 部分积主要是通过counter和compressor进行压缩，通常使用(3:2)counter 和(4:2)compressor。 (3:2)counter其实质就是一个全加器，进位输入为ci，进位输出为c; (4:2)compressor可以由两个全加器组成，ci为进位输入，Coin为内部进位，输入到下一位的进位输入Ci，Coex为输出进位。 上图为二进制树的拓扑结构图，每4个部分积输入到一个(4:2)compressor 中，产生两个输出，则8个部分积使用3次(4:2)compressor就可以得到和和进位。部分积的压缩方式可以见下图。 如图中所示，加上最后一个部分积的进位，共有9个部分积，本设计把最后的进位位移到第一个部分积上，使用5个全加器，把进位融合到第一个部分积，这样就转变成8个部分积了，再使用两级二进制树压缩，所以总共使用了三级压缩，最终得到部分积的和和进位。为了免去不必要的硬件开销，对于部分积边上的位采用counter压缩。上文提到的符号位扩展的改进方法，其目的也就是减少硬件开销，所以在不影响性能的情况下，单独出来部分积的边缘位是十分有必要的。西安电子科技大学技术报告类论文模板
西安电子科技大学计算机图形学重点总结,缩印必备!
西安电子科技大学出版社计算方法上机答案
数字信号处理实验报告(西电)
西安电子科技大学算法上机报告
操作系统实验报告3篇
算法设计技术与方法报告_西电公茂果老师授课
操作系统请求分页式存储管理页面置换算法课程设计报告
计算机控制技术课程设计报告基于PID算法的模拟温度闭环控制系统课程设计报告
(精校版)西安电子科技大学2009年计算机研究生复试上机题
2022年西安电子科技大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)
操作系统磁盘调度算法实验报告
DH密钥协商算法报告文档
操作系统磁盘调度算法实验研究报告
Lloyd-MAX算法的研究报告(精编文档).doc
16位布斯算法乘法器和ALU
- 西安电子科技大学微机原理大作业
- 基础实验化学胡笳答案西安电子科技大学
- 西电网络安全实验
- 2021年西安电子科技大学计组实验报告
- 西安电子科技大学自考《高级语言程序设计》课程实践报告
- 西安电子科技大学课程实验报告封面及内容模版2016
- 西安电子科技大学国家大学生创新性实验计划中期检查报告
- 西安电子科技大学电力电子实验报告
- 西安电子科技大学电磁场与电磁波实验报告与数据
- 西安电子科技大学算法上机报告
- 西安电子科技大学电磁场与电磁波实验报告与数据
- 西安电子科技大学电子线路实验pp (2013新版)
- 《数字信号处理》第三版课后实验答案 西安电子科技大学出版社
- 西安电子科技大学EDA实验报告
- 西安电子科技大学虚拟仿真实验教学中心建设计划书
- 西安电子科技大学2008年度国家大学生创新性实验计划拟...
- 西安电子科技大学电子线路实验报告
- 西安电子科技大学国家大学生创新性试验计划拟立项-教学改革与研究
- 西安电子科技大学实验报告封面
- 西安电子科技大学课程实验报告封面及内容模版2016