Cordic算法说明与实现设计
Cordic 算法说明
———— 王聪颖
假设调制信号为()m t ，则其经FM 调制后的表达式为：
()cos(())t
c f S t t K m
d ωττ=+? 式（1）
其中c ω为载波信号，f K 为常量。因此，()m t 构成了()S t 信号的部分相位分量，而FM 解调过程就是将()m t 从()S t 的相位中提取出来，这里就可以通过Cordic 算法计算出()S t 信号的相位。
一、算法介绍
在本次设计中，为了实现FM 的解调，主要对比了三种算法的实现方法：查表法和Cordic 算法的两种不同实现方法。下面一一进行介绍：
1）查表法：此方法其依据是当[0,/4]θπ∈时，tan [0,1]θ∈且单调递增，这样就可以在[0,/4]θπ∈内建立一个tan θ与θ相对应的表，根据tan θ计算出当前的相位值，同时，利用三角函数关系，将[0,2]π分成大小为/4π的8个部分，并将它们映射至[0,/4]π内从而准确求解。
2）Cordic 算法：其核心是笛卡尔坐标平面旋转，即在xy 坐标平面上将点11(,)x y 旋转θ角度到点22(,)x y 的标准方法如下所示：
211211cos sin sin cos x x y y x y θθθθ=-?
?=+?
式（2）
图1 平面坐标旋转示意图
将式（2）中的cos θ提取出来，在增加一角度累加方程，即可得到Cordic 算法方程组。
(1)()()(1)()()(1)()()tan tan i i i j i i i j i i i j x x d y y y d y z z d θθθ+++?
=-?
=+??=-?
式（3） 在式（3）中，j d 的值为1或-1。
在这里出现两种方法实现Cordic 算法以求的相位：1）取0
2*
45i θ-=，2）取t a n 2i
θ-=
。
第一种方式暂且称为Cordic 角度法，第二种方式我们暂且称之为Cordic 正切法。
二、算法的比较及实现
三种通过计算相位来进行FM解调的算法有其不同的特点：
查表法：其思路简单，只需要利用输入的正弦和余弦值求得其映射在0～45度间的正切值，然后进行查表最终获得相位值。但这种方法首先需要建一个比较大的表格以保证所得到的相位值有足够的精度，这就需要较大的空间，其次在求取正切值的时候必须使用除法，这样如果利用硬件实现这种算法具有一定困难。
Cordic角度法与Cordic正切法：与查表法相比，利用Cordic算法需要进行多次迭代以实现角度的准确逼近，但是所需建的表格较小，其表格的大小与迭代的次数相同。相比之下，正切法比角度法拥有更多的优势，角度法中每次迭代需要两个乘法、三个加法和一个移位运算，而正切法每次迭代仅需三个加法和两个移位运算。
利用DSP仿真软件对以上三种方法进行了测试：对精度要求较高时利用查表法其速度较快，但会占用较多的系统资源，在对精度要求稍低的情况下采用Cordic算法会有比较好的效果，且在同等情况下，正切法较角度法更有优势。在这里迭代次数的分界线约为9，即Cordic算法的迭代次数达到9次时，其消耗的时间开始超过查表法，因此当精度要求大于等于9位时，采用Cordic算法将消耗比查表法更过的时间。此时需要根据系统的需求合理的选择相应的算法。
以上三种FM解调算法的程序流程图如下：
图2 查表法求相位
图3 Cordic角度法求相位
图4 Cordic正切法求相位
在本次设计中FM信号中相位信息的提取采用的是Cordic正切法，其初始表格如下：
在具体的实现中可根据需要将θ的值进行等比放大。
算法设计与分析课程设计(完整版)
HUNAN CITY UNIVERSITY 算法设计与分析课程设计 题目：求最大值与最小值问题 专业： 学号： 姓名： 指导教师： 成绩： 二0年月日
一、问题描述 输入一列整数，求出该列整数中的最大值与最小值。 二、课程设计目的 通过课程设计，提高用计算机解决实际问题的能力，提高独立实践的能力，将课本上的理论知识和实际有机的结合起来，锻炼分析解决实际问题的能力。提高适应实际，实践编程的能力。在实际的编程和调试综合试题的基础上，把高级语言程序设计的思想、编程巧和解题思路进行总结与概括，通过比较系统地练习达到真正比较熟练地掌握计算机编程的基本功，为后续的学习打下基础。了解一般程序设计的基本思路与方法。 三、问题分析 看到这个题目我们最容易想到的算法是直接比较算法：将数组的第 1 个元素分别赋给两个临时变量：fmax:=A[1]; fmin:=A[1]; 然后从数组的第 2 个元素 A[2]开始直到第 n个元素逐个与 fmax 和 fmin 比较，在每次比较中，如果A[i] > fmax，则用 A[i]的值替换 fmax 的值；如果 A[i] < fmin，则用 A[i]的值替换 fmin 的值；否则保持 fmax（fmin）的值不变。这样在程序结束时的fmax、fmin 的值就分别是数组的最大值和最小值。这个算法在最好、最坏情况下，元素的比较次数都是 2(n-1)，而平均比较次数也为 2(n-1)。 如果将上面的比较过程修改为：从数组的第 2 个元素 A[2]开始直到第 n 个元素，每个 A[i]都是首先与 fmax 比较，如果 A[i]>fmax,则用 A[i]的值替换 fmax 的值；否则才将 A[i]与 fmin 比较，如果 A[i] < fmin，则用 A[i]的值替换 fmin 的值。 这样的算法在最好、最坏情况下使用的比较次数分别是 n-1 和 2(n-1),而平均比较次数是 3(n-1)/2,因为在比较过程中，将有一半的几率出现 A[i]>fmax 情况。
内部堆排序算法的实现课程设计说明书
数据结构课程设计设计说明书 内部堆排序算法的实现 学生姓名金少伟 学号1121024029 班级信管1101 成绩 指导教师曹阳 数学与计算机科学学院 2013年3月15日
课程设计任务书 2012—2013学年第二学期 课程设计名称：数据结构课程设计 课程设计题目：内部堆排序算法的实现 完成期限：自2013年3 月4日至2013年3 月15 日共 2 周 设计内容： 堆排序（heap sort）是直接选择排序法的改进，排序时，需要一个记录大小的辅助空间。n个关键字序列K1，K2，…，Kn称为堆，当且仅当该序列满足如下性质(简称为堆性质)：ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ n) 若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。（即如果按照线性存储该树，可得到一个不下降序列或不上升序列）。 本课程设计中主要完成以下内容： 1.设计堆排序算法并实现该算法。 2.对堆排序的时间复杂度及空间复杂度进行计算与探讨。 3.寻找改进堆排序的方法。 基本要求如下： 1.程序设计界面友好； 2.设计思想阐述清晰； 3.算法流程图正确； 4.软件测试方案合理、有效。指导教师：曹阳教研室负责人：申静 课程设计评阅
摘要 堆排序是直接选择排序法的改进。本课设以VC++6.0作为开发环境，C语言作为编程语言，编程实现了堆排序算法。程序运行正确，操作简单，易于为用户接受。 关键词：堆排序；C语言；时间复杂度
算法课程设计
<<算法与程序设计>>课程作业 班级：计本08-1班 学号：3081817106 姓名：詹萍
简单算法 符号三角形问题：这个问题用的是回溯法解决的，符号三角形要求在符号三角形的第1行有n个由“+”和“-”组成的符号，以后每行符号比上行少1个，2个同号下面是“+”，2个异号下面是“-”。计算有多少个不同的符号三角形，使其所含“+”和“-”的个数相同。 解题思路： 1、针对所给问题定义解空间，该问题的解空间为n元组x1,x2,x3...xn，其中xi ∈S，S={0，1}，其中0代表“+”， 1代表“-”； 2、确定易于搜索的解空间结构，例如子集树，排列树，该问题是子集树； 3、以深度优先原则搜索解空间树，并利用剪枝函数避免无效搜索，这里的约束函数应该为：在符号三角形的第一行的前i个符号x1...xi确定后，就确定了一个由i*（i+1）/2个符号组成的符号三角形。下一步确定了x(i+1)的值后，只要在前面已确定的符号三角形的右边加一条边，就可以扩展为x1...x(i+1)所相应的符号三角形。最终由x1...xn所确定的符号三角形中包含的“+”号个数与“-”号个数同为n*（n+1）/4。因此在回溯搜索过程中可用当前符号三角形所包含的“+”号个数与“-”号个数均不超过n*（n+1）/4作为可行性约束；用0和1代替+和-，执行异或操作推出下一行对应符号，当所有符号总数为奇数时无解，当某种符号超过总数一半时无解。 4.由于回溯法是对解空间的深度优先搜索，不断改变第一行每个符号，搜索符合条件的解，因此可以使用递归回溯。 #include
CORDIC算法的优化及硬件实现
CORDIC算法的优化及硬件实现 【摘要】本文介绍了CORDIC算法的基本原理并分析了其优化的方法，在QUARTUS9.0平台上基本实现了其功能，有效的降低了资源的消耗并提升了工作频率。 【关键词】CORDIC优化；FPGA；仿真 CORDIC算法全称为坐标旋转数字计算机，它是由J.V older于1959年提出，cordic的运用大大降低了常用函数如sin，cos，sinh，cosh等在硬件上实现的难度，它主要是将复杂的函数在硬件上通过加减和移位运算递归计算出函数值，由于以上特性使得这一算法特变适合在FPGA上实现。 1.CORDIC算法基本原理 CORDIC算法主要是在一个平面上某一向量（x1，y1）经过旋转角后得到新的向量（x2，y2），如图1所示。 根据变换规则二者有如下关系： 2.传统CORDIC算法的局限性及优化 CORDIC算法在FPGA中主要通过流水线来实现，通常要将提前算出作为的输入预先存储到ROM中，随着流水线级数的增加ROM表的容量成指数增长增加了系统的资源消耗，CORDIC每次运算都要经过多次迭代随着迭代次数的增加计算速度受到很大的影响，一个结果往往要经过多个时钟周期才能得到，此外传统的CORDIC算法的角度范围受到很大的约束，旋转的最大的角度范围为-99.88≤≤99.88无法达到0≤≤360必须对输入的角度预先进行处理才能使其达到收敛针对以上情况采取优化反正切函数表来减少迭代次数，简化校正因子等可以解决资源和速度的缺陷，对于角度的收敛问题采用分象限法如表1。 对于一个15级流水线可以通过以上的方法减少到12次迭代减少了3级流水线，并且减少了ROM的使用量提高了运行效率。 3.CORDIC算法硬件的实现 由于CORDIC算法主要通过加减以及移位来实现，说以特别适合在FPGA 上实现，在这里我采用Altera公司的Cyclon2器件组中的EP2C5Q208C8整个实现过程都是在Quartus9.0中完成图2为系统的整体架构。 当接收完六个字节数据后开始进行优化CORDIC算法迭代运算流程图如图3所示。
CORDIC算法原理及matlab仿真
.1、坐标旋转数字计算机CORDIC 坐标旋转数字计算机CORDIC(COordinate Rotation DIgital Computer)算法，通过移位和加减运算，能递归计算常用函数值，如Sin，Cos，Sinh，Cosh等函数，由J. Volder于1959年提出，首先用于导航系统，使得矢量的旋转和定向运算不需要做查三角函数表、乘法、开方及反三角函数等复杂运算。J. Walther 在1974年用它研究了一种能计算出多种超越函数的统一算法。 1.2、CORDIC原理 如图所示，初始向量（X(0)，Y(0)）旋转θ角度之后得到向量（X1，Y1），此向量有如下关系： CORDIC算法 X1=X0*cos(θ)-Y0*sin(θ)=cos(θ)(X0-Y0*tan(θ)) Y1=Y0*cos(θ)+X0*sin(θ)=cos(θ)(Y0+X0*tan(θ)) 注：θ为待求角 假设初始向量经过N次旋转之后得到新向量，且每次旋转角度δ正切值都为2的倍数，则第i次旋转角度为δ=arctan(2^(-i))，即cosδ=（1/（1+2^(-2i)））^0.5。 容易得到角度θ≈∑S(i)●δ(i)，其中S(i)=1或－1，表示旋转角度的方向，第i步旋转可以表示为： X(i+1)=(（1/（1+2^(-2i)））^0.5)●(X(i)-S(i)Y(i)2^(-i)) Y(i+1)=(（1/（1+2^(-2i)））^0.5)●(Y(i)+S(i)X(i)2^(-i)) 其中（1/（1+2^(-2i)））^0.5)称为校模因子，当旋转次数一定时，趋于一个常数，Π（1/（1+2^(-2i)））^0.5)≈0.6073 这样，算法每一步就可以简化为： X(i+1)=0.6073●(X(i)-S(i)Y(i)2^(-i)) Y(i+1)=0.6073●(Y(i)+S(i)X(i)2^(-i)) 从而可以看出，对于移动的角度θ，现在只需要硬件加减法器和移位器就可以算出结果。引入Z，表示i次旋转后相位累加的部分和，则： Z(i+1)=Z(i)-S(i)arctan(2^(-i)) 经过n次旋转之后，Z→0，即与目标角重合，即： X(n)=X1=X0*cos(θ)-Y0*sin(θ) Y(n)=Y1=Y0*cos(θ)+X0*sin(θ)
计算机算法设计与分析课程设计.
成绩评定表 学生姓名吴旭东班级学号1309010236 专业信息与计算 科学课程设计题目 分治法解决棋盘覆 盖问题；回溯法解 决数字拆分问题 评 语 组长签字： 成绩 日期20 年月日
课程设计任务书 学院理学院专业信息与计算科学 学生姓名吴旭东班级学号1309010236 课程设计题目分治法解决棋盘覆盖问题；回溯法解决数字拆分问题实践教学要求与任务: 要求： 1．巩固和加深对基本算法的理解和运用，提高综合运用课程知识进行算法设计与分析的能力。 2．培养学生自学参考书籍，查阅手册、和文献资料的能力。 3．通过实际课程设计，掌握利用分治法或动态规划算法，回溯法或分支限界法等方法的算法的基本思想，并能运用这些方法设计算法并编写程序解决实际问题。 4．了解与课程有关的知识，能正确解释和分析实验结果。 任务： 按照算法设计方法和原理，设计算法，编写程序并分析结果，完成如下内容： 1.运用分治算法求解排序问题。 2. 运用回溯算法求解N后问题。 工作计划与进度安排: 第12周：查阅资料。掌握算法设计思想，进行算法设计。 第13周：算法实现，调试程序并进行结果分析。 撰写课程设计报告，验收与答辩。 指导教师： 201 年月日专业负责人： 201 年月日 学院教学副院长： 201 年月日
算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。算法 （Algorithm）是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中，算法要用计算机算法语言描述，算法代表用计算机解一类问题的精确、有效的方法。 分治法字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。在一个2^k*2^k的棋盘上， 恰有一个放歌与其他方格不同，且称该棋盘为特殊棋盘。 回溯法的基本做法是深度优先搜索，是一种组织得井井有条的、能避免不必要重复搜索的穷举式搜索算法。数字拆分问题是指将一个整数划分为多个整数之和的问题。利用回溯法可以很好地解决数字拆分问题。将数字拆分然后回溯，从未解决问题。 关键词：分治法，回溯法，棋盘覆盖，数字拆分
基于流水线结构的cordic算法的实现
基于流水线结构的cordic 算法的实现 摘要 系统在处理数据的时候，一个指令周期含有多个时钟脉冲，每个脉冲周期由不同的部件完成不同的操作。非流水线结构是指一个指令周期完成以后再接受下一条处理数据的指令；而流水线结构，每个时钟脉冲都接受下一条处理数据的指令，只是不同的部件做不同的事情，就象生产线流水操作一样，并不是等一个或一批产品做完，再接受下一批生产命令，而是每个工序完成以后，立即接受下一批生产任务。这样提高了系统处理数据的速度。 随着超大规模集成电路(Very Large Scale Integrated circuits , VLSI)技术的飞速发展,经常需要用硬件快速和精确地进行三角函数值的计算,而坐标旋转算法(Coordinate Rotational Digital Computer, CORDIC)能够将多种难以用硬件电路直接实现的复杂的三角函数运算分解为统一的加减、移位操作,极大地降低了硬件设计的复杂性。 在现代信号处理中,经常会遇到三角函数、超越函数和坐标转化等问题。传统的实现方法有查找表多项式展开等方法，但是这些方法在精度、速度、简单性和效率方面往往不能兼顾。CORDIC 算法则可以很好地兼顾这几方面的要求。CORDIC算法只使用移位和加减运算，硬件实现简单。使用流水线结构，每级CORDIC使用独立的单元，这样使运算速度非常快。当流水线填满之后，每个时钟周期就会得到一个结果。 从CORDIC算法的基本原理出发，讨论其工作过程以及旋转角的覆盖范围，在此基础上，给出具有流水线结构的FPGA实现方法以及增益因子的大小与流水线级数的确定关系，给出了verilog实现算法，在Quartus6.0调试与仿真，验证采用FPGA实现的CORDIC算法的有效性。
算法课程设计说明书
课程设计说明书 设计题目：二分法查找 专业：软件工程班级：11-2 设计人：王佳贺 山东科技大学 2013年11 月27日
课程设计任务书 学院：信息科学与工程学院专业：软件工程班级：2011-1 姓名：王佳贺 一、课程设计题目：二分法查找 二、课程设计主要参考资料 （1）《算法分析与设计》（第三版）王晓东电子工业出版社2007 （2） 三、课程设计应解决的主要问题 （1）查询数据 （2） （3） 四、课程设计相关附件（如：图纸、软件等）： （1） （2） 五、任务发出日期：2013-11-21 课程设计完成日期：2013-11-27 指导教师签字：系主任签字：
指导教师对课程设计的评语 成绩： 指导教师签字： 年月日
1二分法详细设计 1.1二分搜索算法 下面我们考虑一种简单的情况。假设该线性表已经排好序了，不妨设它按照主键的递增顺序排列（即由小到大排列）。在这种情况下，我们是否有改进查找效率的可能呢？ 如果线性表里只有一个元素，则只要比较这个元素和x就可以确定x是否在线性表中。因此这个问题满足分治法的第一个适用条件；同时我们注意到对于排好序的线性表L有以下性质：比较x和L中任意一个元素L[i]，若x=L[i]，则x在L中的位置就是i；如果x
CORDIC算法VHDL实现
LIBRARY ieee; USE ieee.std_logic_1164.all; USE ieee.std_logic_arith.all; USE ieee.STD_LOGIC_UNSIGNED.all; ENTITY cordicCOS_SIN IS PORT ( clk :IN std_logic; deg_in :IN std_logic_vector (13 downto 0); cos :OUT std_logic_vector(15 downto 0); sin :OUT std_logic_vector(15 downto 0) ); END cordicCOS_SIN; architecture rlt_cordicCOS_SIN of cordicCOS_SIN is constant c1:std_logic_vector(13 downto 0):=CONV_STD_LOGIC_VECTOR(4096,14); constant c2:std_logic_vector(13 downto 0):=CONV_STD_LOGIC_VECTOR(2048,14); constant c3:std_logic_vector(13 downto 0):=CONV_STD_LOGIC_VECTOR(1209,14); --arctan(1/2) constant c4:std_logic_vector(13 downto 0):=CONV_STD_LOGIC_VECTOR(639,14); --arctan(1/4) --constant x0:std_logic_vector(15 downto 0):=CONV_STD_LOGIC_VECTOR(19895,16); signal x0 :std_logic_vector(15 downto 0); signal y1,x1 :std_logic_vector(15 downto 0); signal y2,x2 :std_logic_vector(15 downto 0); signal y3,x3 :std_logic_vector(17 downto 0); signal y4,x4 :std_logic_vector(19 downto 0); signal p1,p2,p3,p4 :std_logic_vector(13 downto 0); begin x0 <= conv_std_logic_vector(26980,16); ---------------------------------step 1------------------------------------ process(clk) begin if rising_edge(clk) then if deg_in(13) ='1' then y1 <= x"0000" -x0; else y1 <= x0; end if;
操作系统课程设计(LRU算法)完整版内含代码
操作系统课程设计LRU页面调度算法 学号： 姓名： 学院： 专业： 班级： 指导老师： 日期：
目录 一、实验题目 (1) 二、课程设计的目的 (1) 三、设计容 (1) 四、设计要求 (1) 五、设计思想 (1) 六、主要数据结构及其说明 (2) 七、硬件支持 (3) 八、源程序文件 (3) 九、程序运行结果 (7) 十、实验体会 (8)
一实验题目 LRU页面调度算法 二课程设计的目的 操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合一起，独立分析和解决实际问题的机会。 1.进一步巩固和复习操作系统的基础知识。 2. 培养学生结构化程序、模块化程序设计的方法和能力。 3.提高学生调试程序的技巧和软件设计的能力。 4.提高学生分析问题、解决问题以及综合利用C语言进行程序设计的能力。 三设计容 程序应模拟实现LRU算法思想，对n个页面实现模拟调度。 四设计要求 1．不同的功能使用不同的函数实现（模块化），对每个函数的功能和调用接口要注释清楚。对程序其它部分也进行必要的注释。 2．对系统进行功能模块分析、画出总流程图和各模块流程图。 3．用户界面要求使用方便、简洁明了、美观大方、格式统一。所有功能可以反复使用，最好使用菜单。 4．通过命令行相应选项能直接进入某个相应菜单选项的功能模块。 5．所有程序需调试通过。 五设计思想 最近最久未使用（LRU）页调度算法是选择最近最久未使用的页面予以淘汰。 算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间，当所要访问的页面在存块中时，就不淘汰页面，否则，淘汰页面中时间最长的，即淘汰最近最久未使用的页面。
数据结构与算法课程设计学生成绩管理系统
. 课程设计说明书 题目：数据结构与算法课程设计 ：学院（系） 专业班级：号：学 学生姓名： 指导教师：教师职称： 起止时间： '. .
课程设计（论文）任务及评语
'. . 目录 第章课程设计目的与要求 _______________________________________________ 11 1.1 课程设计目的 ________________________________________________________ 1 1.2 课程设计的实验环境 __________________________________________________ 1 1.3 课程设计的预备知识 __________________________________________________ 1 1.4 课程设计要求 ________________________________________________________ 1第章课程设计内容 _______________________________________________________ 22 2.1题目的选择 _________________________________________________________ _ 2
2.2 题目的具体实现 ______________________________________________________ 2 2.3 思考题解析 _________________________________________________________ 12 总结： _________________________________________________________ ________ 14 参考文献 _________________________________________________ 错误!未定义书签。 '. . 课程设计目的与要求1第章 课程设计目的1.1 本课程设计是计算机科学与技术专业、软件工程专业的专业技术实践课。 本实践课的主要目的是：使学生学会利用在课堂中学过的理论知识，解决相应的实际问题，深入理解和灵活掌握所学的内容，培养学生理论和实践相结合的能力，培养学生分析问题解决问题的能力。同时，在实验步骤规范化、程序设计
分支算法循环赛日程表课程设计
摘要 分治算法在实际中有广泛的应用，例如，对于n个元素的排序问题，当n = 1 时，不需任何计算；当n = 2 时，只要做一次比较即可排好序；当n = 3时只要做两次比较即可……而当n较大时，问题就不容易那么处理了。要想直接解决一个较大的问题，有时是相当困难的。分治算法的基本思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。如果原问题可分割成k个子问题，1 < k < n+1，且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治算法就是可行的。由分治算法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易求出其解。由此自然引出递归算法。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。 本次课程设计正是采用分治算法来解决循环赛日程表的安排问题。根据算法的设计结果，采用c语言实现算法，通过测试分析，程序运行结果正确，运行效率较高。 关键词：分治算法
目录 摘要 ..................................................................................................................... I 1 问题描述 (1) 2 问题分析 (2) 3 算法设计 (3) 4 算法实现 (7) 5 测试分析 (11) 结论 (12) 参考文献 (13)
1 问题描述 设有n位选手参加网球循环赛，n=2k，循环赛共进行n-1天，每位选手要与其他n-1位选手比赛一场，且每位选手每天比赛一场，不能轮空，按以下要求为比赛安排日程， 1)每位选手必须与其他n-1格选手格赛一场； 2)每个选手每天只能赛一场； 3)循环赛一共进行n-1天； 请按此要求将比赛日程表设计成有n行和n-1列的一个表。在表中的第i行和第j列处填入第i个选手在第j天所遇到的选手，其中1≤i≤n,1≤j≤n-1。
cordic算法详解
CORDIC The calculus courses provide us with tools to compute the values of trigonometric functions,for example,via series expansions, polynomial,and rational function approximations.However,these implementations tend to require multiplication and division operations that make them expensive in hardware. In contrast,CORDIC(COrdinate Rotation Digital Computer)algorithms need only adders,shifters and comparators for computing a wide range of elementary functions.The method is especially e?cient when?xed point implementations of signal processing algorithms on hardware are considered.For example,CORDIC is extremely popular in hardware accelerators and also in SIMD(Single-Instruction Multiple Data)realizations.Furthermore,almost all function calculators employ CORDIC. Intel processors used CORDIC for trigonometric functions till80486. CORDIC is a good choice for hardware solutions such as FPGA in which cost(gate count)minimization is more important than throughput maximization.In software implementations CORDIC enables most of the code and data be shared between routines for trigonometric and hyperbolic functions,helping to conserve memory.CORDIC algorithm is often used to implement rotations needed in modulators and demodulators. CORDIC algorithm was introduced in1959by Volder for implementing a real-time navigation computer for aeronautical appli-cations.The algorithm was initially formulated for computing the values of trigonometric functions.In early1970s the CORDIC techniques were extended to exponential,logarithm,forward and inverse circular and hyperbolic functions,ratios and square roots(Walther1971).Its concepts have also been developed to include calculation of the Discrete Fourier Transform(Despain 1974).More recently(Bajard et al1994)e?cient hardware technique known as BKM for computing complex exponentials and trigonometric functions was proposed and has since been very widely applied. 1
CORDIC算法在FPGA中的实现
微 处 理 机 M I CROPROCESS ORS ?大规模集成电路设计、制造与应用? C OR D I C 算法在FPG A 中的实现 王智霞,王广生 (北京工业大学电控学院,北京100022) 摘 要:CORD I C 算法是在许多角度计算方面有着广泛应用的经典算法,通过考虑FPG A 的结构、精度局限和速度要求,采用流水线技术(p i peline ),在FPG A 上用CORD I C 算法实现了对于大吞吐量数据的向量倾角的计算,并对实际应用中内部步骤寄存器精度的选取给出了较为详细的方法。 关键词:坐标旋转数字计算;FPG A;流水线中图分类号:T N4 文献标识码:B 文章编号:1002-2279(2007)01-0004-04 FP GA B a sed R ea li za ti o n o f CO RD I C A l go rithm WANG Zhi -xia,WANG Guang -sheng (B eijing university of technology,B eijing 100022,China ) Abstract:CORD I C algorithm is a classic algorith m with many app licati ons .Considering the archi 2tecture,p recisi on and s peed of FPG A ,the p i peline technol ogy is used in computing large number of vect or angle values .This article p r ovides the way of confir m the wide of inner p r ocessing register . Key words:CORD I C;FPG A;Pi peline 1 引 言 FPG A 以其灵活性和使用方便在现今的数字领 域已经得到了广泛的应用。但FPG A 实现数字系统也有其自身的局限性,其一是器件资源的门阵列规模的限制,其二是单元延迟限制,所以,这就需要设计者充分考虑器件的实际工作能力。 角度的旋转计算在数字领域尤其是数字通信领域是一种应用非常广泛的计算,如果用传统的除法器、乘法器等计算方法,需要占用大量的FPG A 资源,这样就不能满足设计者的要求,需要设计者考虑其他的算法实现这种类型的计算。 CORD I C 算法在硬件电路的实现上只用到了加法器和移位器,这样就大大节约了FPG A 的资源,从而可以满足设计者的要求。 2 CORD I C 算法简介 CORD I C (Coordinate Rotati on D igital Computer ), 又名:坐标旋转数字计算,是J.Voider 等人于1959 年在设计美国航空导航控制系统的过程中提出来的 一种算法。下面就简要地介绍一下CORD I C 算法的 基本数学思想。 如图1所示,向量逆时针旋转θ度角得到 向量OB ,这个关系可以用矩阵表示如式1[1] : X j Y j = cos θ -sin θsin θ cos θX i Y i =cos θ1 -tan θ tan θ 1X i Y j (1) 图1 向量旋转坐标图 如果假设θ是由n 个θn 角度叠加而成的,那么根据式( 1)得出每一步的叠加操作需要按照式(2)行 X n +1Y n +1=cos θn 1 -tan θn tan θn 1X n Y n (2)利用式2经过n 步叠加可以表示由向量旋 转到向量OB ,如下表示: X j Y j =cos θ0?cos θ1...cos θn 1 -tan θ0tan θ0 1...1 - tan θn tan θn 1X i Y i (3)作者简介:王智霞(1980-),女,北京人,硕士研究生,主研方向:嵌入式系统设计与实现,大规模集成电路系统设计,数字通信。 收稿日期:2005-02-23 第1期 2007年2月 No .1Feb .,2007
A算法的改进课程设计
沈阳大学
Floyd-Warshall算法的描述如下： for k ← 1 to n do for i ← 1 to n do for j ← 1 to n do if (Di,k + Dk,j < Di,j) then Di,j ← Di,k + Dk,j; 其中Di,j表示由点i到点j的代价，当Di,j为∞表示两点之间没有任何连接。 （2）Dijkstra 求单源、无负权的最短路。时效性较好，时间复杂度为O（V*V+E）。 源点可达的话，O（V*lgV+E*lgV）=>O（E*lgV）。 当是稀疏图的情况时，此时E=V*V/lgV，所以算法的时间复杂度可为O（V^2）。若是斐波那契堆作优先队列的话，算法时间复杂度，则为O（V*lgV + E）。 （3）Bellman-Ford 求单源最短路，可以判断有无负权回路（若有，则不存在最短路），时效性较好，时间复杂度O（VE）。 Bellman-Ford算法是求解单源最短路径问题的一种算法。 单源点的最短路径问题是指：给定一个加权有向图G和源点s，对于图G中的任意一点v，求从s到v的最短路径。与Dijkstra算法不同的是，在Bellman-Ford算法中，边的权值可以为负数。设想从我们可以从图中找到一个环路（即从v出发，经过若干个点之后又回到v）且这个环路中所有边的权值之和为负。那么通过这个环路，环路中任意两点的最短路径就可以无穷小下去。如果不处理这个负环路，程序就会永远运行下去。而Bellman-Ford算法具有分辨这种负环路的能力。A*（A-Star)算法是一种静态路网中求解最短路最有效的直接搜索方法。注意是最有效的直接搜索算法。之后涌现了很多预处理算法（ALT，CH，HL等等），在线查询效率是A*算法的数千甚至上万倍。公式表示为：f(n)=g(n)+h(n),其中f(n) 是从初始点经由节点n到目标点的估价函数，g(n) 是在状态空间中从初始节点到n节点的实际代价，h(n) 是从n到目标节点最佳路径的估计代价。保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：
cordic算法详解
cordic算法详解 转载自小一休哥的文章： https://www.wendangku.net/doc/0c8496600.html,/qq_39210023/article/details/77456031 目前，学习与开发FPGA的程序员们大多使用的是Verilog HDL语言（以下简称为Verilog），关于Verilog的诸多优点一休哥就不多介绍了，在此，我们将重点放在Verilog的运算操作上。 我们都知道，在Verilog中，运算一般分为逻辑运算（与或非等）与算术运算（加减乘除等）。而在一开始学习Verilog 时，老司机一定会提醒我们，“切记，千万别用‘/’除、‘%’取模（有的也叫取余）和‘**’幂。”这话说的不无道理，因为这三个运算是不可综合的。但，需清楚理解的是，不可综合的具体意思为不能综合为简单的模块，当我们在程序中调用了这些运算时，‘/’除和‘%’取模在Quartus软件中是可以综合的，因此可以正常调用运行，但是会消耗一些逻辑资源，而且会产生延时，即这两个运算的处理时间会很长，可能会大于时序控制时钟的单周期时间。此时呢，我们会建议你调用IP 核来实现运算操作，虽然这样也会消耗许多逻辑资源，但产生的延时相对较小满足了你基本的需求。 问题好像迎刃而解了，可是仔细一想，除了这些运算，我们
还剩下什么？对呀，三角函数，反三角函数，对数函数，指数函数呢，这些函数我们在高中就学习了的呀，难道在FPGA 中就没有用武之地吗？有人会说，查找表呗，首先将某个运算的所有可能的输入与输出对一一罗列出来，然后放进Rom 中，然后根据输入查表得到输出。这个方法虽然有效的避免了延时问题，却是一个十分消耗资源的方法，不适合资源紧张的设计。那么，就真的没有办法了吗？ 答案就是咱们今天的标题了，CORDIC，而且CORDIC是一个比较全能的算法，通过这一原理，我们可以实现三角函数，反三角函数，对数函数，指数函数等多种运算。接下来，一休哥就带领大家来学习CORDIC的原理吧。（题外话：请相信一休哥，本文不会让你感到太多痛苦~） 本文将分三个小部分来展开介绍： 1、CORDIC的基本原理介绍 2、CORDIC的具体操作流程介绍 3、CORDIC的旋转模式——Verilog仿真 本文涉及到的全部资料链接：
课程设计说明书示例
面向过程程序设计（C语言）课程设计 设计说明书 通讯录管理系统 起止日期： 2012 年 12 月 18 日至 2012 年 12月 23日 学生姓名 班级 学号 成绩 指导教师(签字) 计算机与通信学院 2012 年 12 月 23 日 通讯录管理系统
一、设计要求 综合运用C语言程序设计课程的主要知识，设计一个用于通讯录管理的程序，设计指标由程序的功能要求和技术要求具体说明。 1、功能要求 通信录管理程序至少应具有如下功能： （1）输入功能：能通过键盘向通信录输入数据。要求随时都能使用该项功能实现记录输入，一次可以输入一条记录，也可以输入多条记录。所谓一条记录，是指通信录中一个人员的完整信息。 （2）显示功能：能显示通信录存储的记录信息，在显示时能提供下列显示方式： ①按自然顺序显示。即按照向通信录输入数据时各条记录的先后顺序，显示通信录中已有的记录信息。 ②按照一定的排列顺序显示通信录信息。排序顺序有多种，如按姓名查询、按所在城市查询，任何一种查询都要有明确的查询结果。 （3）查询功能：能查询通信录信息。要求至少提供两种查询方式，如按照姓名查询、按所在城市查询，任何一种查询都要有明确的查询结果。 （4）修改功能：能对通信录存储的信息进行修改。要求至少提供两种修改方式，如按照姓名修改、按照通信录记录序号修改。记录序号是通信录记录的自然顺序编号。 （5）删除功能：能对通信录的信息进行删除。要求删除时以记录为单位，既能一次删除一条记录，也能一次删除多条记录。 （6）保存功能：能将记录保存在任何自定义的文件中，如保存在：c:\score。 （7）读取功能：能将保存在文件中的记录读取出来，并在屏幕上显示。 （8）通信录管理结束后，能够正常退出通信录管理程序。
课程设计设计说明书格式规范
课程设计设计说明书格式规范
————————————————————————————————作者: ————————————————————————————————日期:
课程设计设计说明书格式规范 一、课程设计设计说明书格式规范 装订成册的书面说明书和完整电子文档各一份，说明书统一采用Ａ４纸打印，说明书格式如下,顺序为: （一)封面 （二）索命数正文，包括: 1、摘要（包括中文摘要和英文摘要)： 分别为300字左右,应包括:工作目的、内容、结论、关键词 2、目录 以上部分以I、IＩ……编制页码。以下部分根据章节编写序号和页码。 3、主体部分(不少于１20０0字,按要求设定页眉页角,要求居中） 主要包括引言或绪论、正文、结论、致谢，采用全角符号,英文和数字半角。每页2８行、每行32-35个汉字，1.5倍行间距3．１格式:主体部分的编写格式由引言（绪论)开始,以结论结束。主体部分必须由1页开始。一级标题之间换页，二级标题之间空行。 ３.2序号 3.２．1毕业说明书各章应有序号,序号用阿拉伯数字编码,层次 1××××(三号黑体，居中） 格式为：? ×××××××××××××××××××××× (内容用小四号宋体)。? 1.1××××(小三号黑体,居左) ××××××××××××××××××××× (内容用小四号宋体)。?1．1．1××××(四号黑体，居左）?×××××××××××××××××××× （内容用小四号宋体）。 ①×××× (用与内容同样大小的宋体） 1）××××(用与内容同样大小的宋体） a.××××(用与内容同样大小的宋体）?３.2.2说明书中的图、表、公式、算式等，一律用阿拉伯数字分别依序连编号编排序号。序号分章依序编码，其标注形式应便于互相区别，可分别为：图2.1、表3.2式（3.５）等? 3.2.3说明书一律用阿拉伯数字连续编页