具有同时多种子检测与并行扩展能力的BLAST算法加速器研究
Hans Journal of Computational Biology计算生物学, 2015, 5, 1-10
Published Online March 2015 in Hans. https://www.wendangku.net/doc/ea5806605.html,/journal/hjcb
https://www.wendangku.net/doc/ea5806605.html,/10.12677/hjcb.2015.51001
The Research on BLAST Accelerator with
Parallel Multi-Seeds Detection and Extension
Fei Xia, Guoqing Jin, Chunlei Zhang
Electronic Engineering College, Naval Engineering University, Wuhan Hubei
Email: xcyphoenix@https://www.wendangku.net/doc/ea5806605.html,
Received: Feb. 6th, 2015; accepted: Feb. 21st, 2015; published: Feb. 28th, 2015
Copyright ? 2015 by authors and Hans Publishers Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY).
https://www.wendangku.net/doc/ea5806605.html,/licenses/by/4.0/
Abstract
BLAST adopts index-based approach to detect the matches between two substrings by looking up a large table and processing one match per query. In this paper, we propose a systolic array ap-proach to detect string matches without using looking up tables. The pipelining systolic array is implemented as a multi-seeds detection and parallel extension engine to accelerate the first two stages of NCBI BLAST algorithm. Different from the index-based approach, our implementation con- sumes little memory resources and eliminates redundant string extensions. Our FPGA implemen-tation achieves superior performance results in both of processing element number and clock frequency over related works in the area of FPGA BLAST accelerators. The experimental results show a speedup factor of more than 20× over the NCBI BLAST software running on a current main- stream PC platform.
Keywords
Multi-Seeds Detection, Hardware Acceleration, Bio-Sequence Searching, FPGA
具有同时多种子检测与并行扩展能力的BLAST 算法加速器研究
夏飞，金国庆，张春雷
海军工程大学电子工程学院，湖北武汉
Email: xcyphoenix@https://www.wendangku.net/doc/ea5806605.html,
具有同时多种子检测与并行扩展能力的BLAST算法加速器研究
收稿日期：2015年2月6日；录用日期：2015年2月21日；发布日期：2015年2月28日
摘要
本文针对目前流行的BLAST算法存在的种子检测效率不高的问题，提出了一种不同于常规查询策略的并行多种子检测算法，并基于脉动阵列结构设计和实现了一种具备同时多种子检测与并行扩展能力的算法加速器，实现了对NCBI BLAST程序前两个阶段的加速。加速器阵列采用流水工作模式，能够动态计算所有单词的匹配点位置，避免了索引结构的存储开销；采用了阵列分组和并行种子收集策略减少了有效种子数量；采用组内种子合并策略避免了冗余扩展操作；采用多种子并行扩展策略实现了无阻塞的数据库搜索，显著提高了数据库搜索效率。实验结果表明，本设计在阵列规模和时钟频率上都优于相关研究工作，相对于目前主流的通用微处理器可获得20倍以上的加速效果。
关键词
多种子并行检测，硬件加速，生物序列搜索，FPGA
1. 引言
BLAST (Basic Local Alignment Search Tool) [1]是目前搜索效率最高、使用最广泛的启发式序列数据库搜索算法。目前大多数BLAST搜索工具运行于集群或并行计算机上，如Grid Blast [2]、Cyberpara Blast
[3]、Blast Quest [4]、Turbo Blast [5]、Parallel Blast [6]、Scala Blast [7]等。随着生物序列数据库规模的急
剧膨胀(GenBank的规模每18个月翻一番[8]，目前数据库包含的序列数量超过1.7 × 108条，残基数量已接近1600亿)，生物序列比对研究对计算能力的需求远远超过计算能力的增长。
FPGA (Field Programmable Gate Array)器件以其可编程特性、细粒度并行能力、丰富的计算资源、灵活的算法适应性和较低的硬件代价成为理想的算法加速平台。为了提高搜索效率，基于FPGA平台的并行BLAST算法成为研究热点。近年来备受关注的研究成果有Mercury BLASTn [9]-[11]、Mercury BLASTp
[12]、RC-BLAST [13]、Tree-BLAST [14]、FPGA/FLASH [15]、Multi-engine BLASTn [16] [17]，并且产生
了一批商用计算平台，如BEE2 [18]、CLC Cube [19]、Mitrion [20]和DeCypher [21]等。以上工作的共同特点是使用FPGA对算法中计算简单、数据密集的部分进行加速，将目标序列中的单词作为数据流，使其逐一通过算法加速器，在请求和目标序列之间寻找匹配的种子(seed)，然后将其扩展为无空位的HSP 片段(High Score Pairs)，最后将HSP发送给通用微处理器执行进一步扩展和生成统计结果。
目前绝大多数硬件并行方案都采用基于索引表的搜索方法，通过建立表格来记录请求序列中单词出现的位置，然后通过查表的方法寻找种子。这种方法存在两个问题：首先，由于访存端口的限制，每次只能查询一个单词，也就意味着最多只能发现一个种子；其次，索引表的存储和访问开销将会成为系统的性能瓶颈。例如，Mercury BLASTn [10]和Mitrion [20]使用了基于Hash表的查找策略，根据请求序列建立Hash表，然后将目标序列中的单词作用于Hash函数并查表，匹配则说明找到了一个种子。由于FPGA 的存储资源有限，Hash表通常存储在FPGA片外，这样外部存储器访问延迟将会成为处理过程的瓶颈。
RC-BLAST [13]和BEE2 [18]采用了基于索引表方法：首先为请求序列中的单词建立位置索引，然后以目标序列中的单词作为地址查询索引表，如果找到匹配则返回相应的位置信息。由于片内存储容量的限制，RC-BLAST [13]假设任意单词在请求序列中最多只出现三次，但实际上单词在序列中出现的位置和次数都是随机的，这样的假设并不合理。与以上两种索引表相比，FPGA/FLASH [15]采用了更新颖的设计：
具有同时多种子检测与并行扩展能力的BLAST 算法加速器研究
它为请求序列和整个数据库都建立索引，对每个单词，通过查找索引表便可以直接得到其在数据库中出现的位置和上下文字符，避免了对数据库的全面搜索；同时减少了扩展阶段对数据库的随机访问次数。但是该方法会导致极大的存储开销(例如为人类基因组数据库建立索引要耗费超过150 GB 存储空间，是原始数据的50倍[15])。随着生物序列原始数据量的增长，这种方法带来的存储开销将难以承受。为了进一步提高搜索效率，Multi-engines BLASTn [17]设计了64个独立的搜索引擎将请求序列与数据库中的64条目标序列同时进行比较，但就每一个引擎而言，仍采用与RC-BLAST 和BEE2相同的基于位置索引的搜索方法。从本质上说，以上工作都采用了单种子检测方法，即每个时钟周期最多只能发现一个种子。最近，Mercury BLASTp [12]使用了双种子搜索引擎来加速种子检测，但是该方法仍然基于位置索引表，通过复制逻辑模块(包括查找表和单词命中模块)来提高种子检测效率。
除了上述基于查表的方法外，还存在一类基于算术/逻辑运算的搜索方法，Tree-BLAST [14]是其中的典型代表。Tree-BLAST 没有采用基于种子的传统启发式搜索策略，而用直接打分的方法寻找高分片段对。由于需要给每4个处理单元分配一个存储模块实现替换矩阵的存储，片内存储资源限制了请求序列的规模，最大只能支持包含1024个碱基字符的请求序列。
2. BLAST 算法并行计算结构
图1是硬件BLAST 算法并行计算结构，算法核心逻辑由IO 接口和PE 阵列控制器、片内存储器、多种子检测阵列、种子收集与合并模块和并行扩展模块构成。IO 接口和PE 阵列控制器实现与主机的数据交互，PE 阵列初始化以及数据格式转换，并控制目标序列以步进的方式进入PE 阵列。片内存储器由多个存储体构成，用于保存请求和目标序列的多个副本，为并行扩展提供所需的序列片段。算法核心与两个外部存储器相连，从Memory#1中载入目标序列，输入多种子检测阵列，经过种子检测、合并和无空位扩展，将HSP 列表写入Memory#2。
3. 多种子检测阵列
本阶段的功能是在请求序列和目标序列中搜索长度为3氨基酸字符的匹配单词串。假设11i i i q q q ?+和()11,1,i i i s s s i j ?+≥分别是查询和目标序列中长度为3的单词，如果条件()()()1111i j i j i j q s q s q s ??++=∧=∧=成立则意味着单词匹配成功，即种子被成功检测。
图2为PE 并行多种子检测算法，L 为PE 阵列长度。种子检测和位置报告是PE 的两个主要功能。处理阶段语句S3判断种子检测条件。种子的位置信息包括在请求和目标序列中的偏移以及目标序列在数据库中的编号，分别由初始化阶段语句S2、处理阶段的语句S1和S2动态生成。
图3是并行多种子检测阵列的结构。阵列由PE 单元串联构成。请求序列寄存在阵列中(每个PE 存储一个氨基酸字符)，数据库中的序列依次流过PE 阵列。PE[i] (阵列中的第i 个PE)接收来自相邻PE 发出的字符对()11,i j q s ??和()11,i j q s ++的比较结果，并比较字符对(),i j q s ，判断是否检测到种子。所有PE 并行执行上述操作，因此阵列具备多种子检测能力(图3所示的阵列同时检测出两个种子：PE2发现AKL ，PE3发现KLP)。
图4是PE 模块结构框图，中部虚线框内的3输入与门实现种子检测，是PE 模块的核心。左右相邻PE 产生的字符对匹配标志与当前PE 产生的匹配结果一起送入与门的输入端。当这3个输入信号均为TRUE 时，PE 将单词匹配结果置为1。图中上下两部分所示的3个累加器负责生成匹配点(种子)位置。如果当前输入字符为序列结束标志，则将序列位置寄存器清零，同时目标序列ID 寄存器加1。序列停顿信号和阵列停顿信号分别用于控制初始化和搜索阶段PE 的工作状态。由于单词匹配结果依赖于3对氨基酸字符的比较结果，因此匹配结果的生成是PE 的关键路径。时序分析表明，该路径的延时小于3 ns ，不会
具有同时多种子检测与并行扩展能力的BLAST 算法加速器研究
Figure 1. Parallel structure of BLAST algorithm
图1. BLAST 算法并行计算结构
所有PE 同时执行以下过程：
初始化阶段: // 将查询序列输入PE 阵列，并记录每个字符所处的PE 编号，即在查询序列中的偏移位置
S1：氨基酸字符寄存器、单词匹配标志、种子位置信息寄存器组清零；
S2：if (PE 阵列未暂停)
查询序列位置寄存器加1； // 记录种子在查询序列中的位置
if (PE 阵列未暂停)
S1：目标序列位置寄存器加1； // 记录种子在当前目标序列中的位置
S2：if (当前目标序列结束)
目标序列ID 寄存器加1；// 记录当前目标序列在数据库中的编号
else if (q i = s j )
将当前字符对比较结果置1并输出给相邻PE ；
S3：if ( (q i = s j ) & (q i-1 = s j-1) & (q i+1 = s j+1) )
单词匹配标志置1； // 发现种子
输出种子的位置信息；// 包括在查询和目标序列中的位置以及目标序列在数据库中的编号
处理阶段
:
Figure 2. The seeds detecting algorithm for each PE
图2. 并行多种子检测算法
目标序列请求序列Figure 3. Structure of multi-seeds detection array
图3. 并行多种子检测阵列结构
具有同时多种子检测与并行扩展能力的BLAST算法加速器研究
成为FPGA实现的瓶颈。
4. 设计实现与优化
采用并行多种子检测有以下好处：1) 能够有效提高搜索程序的单词匹配能力。2) 阵列每次报告的种子都位于打分矩阵的同一条对角线上，便于对其进行过滤。3) 能提高数据吞吐率，有助于减少扩展阶段的空闲等待，提高资源利用率。另一方面，在有效提高种子检测效率的同时对后端处理能力提出了更高要求：1) 如何快速实现对多种子的收集将成为提高实际搜索效率的关键。2) 阵列同时报告的多个种子处于矩阵的同一条对角线上，这意味着可能存在连续的种子，对这些种子执行扩展将导致出现相同的结果。3) 单种子的扩展操作是串行的，扩展能力将成为搜索的瓶颈。为了提高阵列搜索效率，本文通过阵列分组实现并行种子搜集，通过组内种子合并实现种子过滤，通过多种子并行扩展匹配阵列的种子检测能力。4.1. 阵列分组和并行种子收集
如图5所示，将多种子检测阵列划分为若干个PE组，同时将种子收集与合并模块分割为若干子模块，与PE组一一对应，并行收集PE组报告的种子，并将其写入局部FIFO。局部FIFO中的数据经过多级合并后进入Hit FIFO，随即执行无空位扩展。
分组策略的好处是控制了模块的逻辑量和互连端口的规模，优化了硬件逻辑设计。通过对PE阵列和种子合并模块进行分组，将两者之间庞大的多路选择器(MUX)拆分为规模较小的子模块(subMUX)，从而消除了FPGA设计瓶颈。为了保证设计平衡，需要控制划分的粒度。实验表明由64个PE构成一组是最佳选择。由于将多路选择器的规模由512选1缩小为64选1，由8个组构成的PE阵列的时钟频率可由分组前的55 MHz提升至156 MHz，并且随着阵列规模的增长，频率不会出现明显降低。分组优化的代价是增加了多级局部FIFO和FIFO合并模块，局部FIFO使用FPGA片内存储资源实现，FIFO级数等于log2G，与庞大的多路选择器相比，FIFO合并模块消耗的逻辑资源可以忽略不计。
4.2. 组内种子合并
由于种子扩展过程是串行的，并行多种子检测对后端的扩展能力提出了很高的要求，本文通过组内
Figure 4. PE module structure
图4.细粒度并行BLAST算法PE结构
具有同时多种子检测与并行扩展能力的BLAST 算法加速器研究
种子合并策略来减少对扩展阶段的压力。而且由于PE 阵列每次报告的多个种子都位于矩阵同一反对角线上。当请求和目标序列中的两个片段相似度很高时，组内连续的多个PE 会同时发出种子命中信号，但这些种子在序列中所处的位置是连续的，属于同一个高分片断。如果将每个种子都传递给扩展模块将会导致不必要的重复扩展。为此，本章采用组内相邻种子合并策略减少有效种子的数量。
图6是种子收集与合并模块端口连接示意图。合并的好处是可以减少有效种子的数量，减轻扩展阶段的压力；同时通过消除冗余扩展来提高扩展效率。种子合并过程是：一旦PE 阵列检测到单词匹配，便暂停目标序列的传递，并寄存标志位。根据单词匹配标志合并相邻种子，同时将合并后的有效种子传递给扩展模块，当所有匹配标志处理完后再重启搜索阵列。
图7是PE 组内相邻种子合并算法。种子收集与合并子模块寄存对应PE 组产生的单词匹配标志，并判断是否有种子被发现(S1)。语句S4寻找并记录匹配标志寄存器中“首1”的位置(1代表检测到匹配的单词)。S6中的循环将多个连续种子合并为一个有效种子。假设当前PE 组处于图3所示的状态，PE2和PE3同时检测到种子(PE2发现AKL ，PE3发现KLP)。如果不进行合并优化，种子收集与合并子模块会将这两个种子依次写入局部FIFO ，随后将执行两次扩展。通过将两者合并为一个有效种子AKLP ，则只需执行一次扩展。语句S7判断是否发现足够长的精确匹配片断。如果相邻种子的数量大于8 (对应10个
Figure 5. Array partition and hierarchical merging
图5. 多种子检测阵列分组与种子分级合并过程
多种子检测阵列
PE Group PE Group
Figure 6. Port connection module
图6. 种子收集与合并模块端口连接示意图
具有同时多种子检测与并行扩展能力的BLAST 算法加速器研究
所有种子收集与合并子模块同时执行以下过程：
初始化阶段:
S1：种子位置寄存器、单词匹配标志寄存器清0；
处理阶段:
S1：HSP 标志清0，并寄存PE Group 产生的单词匹配标志位；
S2：While (单词匹配标志寄存器不等于全0) // 说明有PE 检测到种子
Do S3 ~ S8;
S3：阵列停顿信号置1； // PE 阵列暂停
S4：找到并记录目前第一个种子的位置；// 即单词匹配标志寄存器中首1的位置
S5：将单词匹配标志寄存器对应位置0，并判断相邻的下一个位置；
S6：While (单词匹配标志寄存器的当前标志位等于1) // 说明发现了相邻的种子
Do {
将单词匹配标志寄存器当前位置清0；
记录已发现的相邻种子数量，并指向标志寄存器的下一个位置；
}
S7：If (相邻种子数量大于阀值)
HSP 标志置1；
S8：报告有效种子的位置信息；
// 包括在查询和目标序列中的位置，目标序列ID 以及HSP 标志
S9： 重新启动PE 阵列，返回 S1; Figure 7. Successive seeds merging algorithm
图7. PE 组内相邻种子合并算法
以上连续字符对的精确匹配)，扩展模块将不会对该有效种子进行处理而直接将其输出。对于上述情况，如果不采用合并优化策略，记录匹配位置需要8个时钟周期，加上扩展开销，共需要72个时钟周期。而且扩展模块会报告发现8个HSP (而实际上只有1个有效HSP)。采用合并策略后只需要8个周期便可发现该HSP ，减少了不必要的重复扩展。
4.3. 多路并行扩展
无空位扩展的过程是根据种子所处的位置读出两条长度为K 的蛋白质子序列q 和s ，然后将子序列中的字符对()(),,1i t j t q s t k ++≤≤进行逐一比较，然后将分值累加。由于PE 阵列具备并行多种子检测能力，而扩展阶段由于序列存储器访问的限制，每个周期只能读出一对氨基酸字符，导致种子的扩展能力与检测能力不匹配。即使通过合并策略减少了有效种子的数量，但当阵列规模较大时，仍可能由于扩展能力不足导致阵列出现阻塞。
为了解决上述问题，本章采用了如图8所示的多路并行扩展策略平衡两阶段的处理能力。由于所有的扩展模块都需要同时访问序列存储器获取扩展所需的序列片断，因此为每个扩展模块都设置了独立的序列存储器副本(包括QryMem 和Sub Mem ，分别存储请求和目标序列)，为并行扩展提供足够的存储端口。这样来自不同Hit FIFO 中的多个种子便可以并行地执行扩展。
5. 实验与性能分析
5.1. FPGA 实现
我们在XC5VLX330和XC4VLX160芯片上分别实现了包含3072和2048个PE 的搜索阵列。与Tree- BLAST [14]不同的是，阵列规模主要受限于逻辑而不是存储资源。从表1可以看到，使用同样的芯片XC4VLX160，本设计用更少的存储资源实现了更长的PE 阵列，阵列规模为Tree-BLAST 的2倍，同时设计频率也高于相关工作。
加速器的主要存储开销为序列存储器和种子合并FIFO 。以规模为3072个PE 的阵列为例，序列存储
具有同时多种子检测与并行扩展能力的BLAST算法加速器研究
Figure 8. Structure of multi-channel parallel extension
图8.多路并行扩展结构
Table 1. Performance results and comparison
表1.基于线性阵列的BLAST算法加速器实现结果对比
Ours Tree-BLAST [14] FPGA XC5VLX330 XC4VLX160 XC2VP70 XC4VLX160
阵列规模3072 2048 600 1024
逻辑资源73% 71% --- 78%
存储资源31% 38% --- 88%
时钟频率133MHz 189MHz 110MHz 178MHz
开销为36 K × 5 bit，加上FIFO (16 K × 32 bit)，共计692 Kbits，仅占XC5VLX330存储容量的6%。而基于索引表的搜索方法均受限于FPGA存储资源。RC-BLAST [13]在Xilinx 4085XLA上实现了最大规模为
64 K × 64 bits的索引表，但只能记录每个单词在请求序列中的3次出现。Mercury BLASTn [10]和Mitrion
BLAST [20]将Hash表移至外部存储器中，导致存储访问延迟成为流水线设计的瓶颈。与基于索引表的RC-BLAST和基于线性阵列的Tree-BLAST相比，本设计对存储资源的需求分别降低约90%和50%。存储需求的降低减少了存储访问的复杂度，进而减小了FPGA布局布线的难度。
5.2. 加速性能
测试采用的搜索软件为NCBI BLAST [22]，版本号2.2.16，使用Blosum62蛋白质替换矩阵。软件运行环境为Windows XP SP3操作系统，Visual Studio 2008 开发环境，Visual C++编译器，版本号为
15.00.30729.01。
实验输入的请求序列取自Swiss-Prot数据库，长度为128~8192 bps，搜索对象为Swiss-Prot (从EBI 下载[23]，包含274,295条序列，共100,686,439个氨基酸字符)。BLASTn用于DNA数据库搜索，请求序列取自drosoph.nt数据库，长度为128~8192 bps，搜索对象为drosoph.nt [24]，包含1170条DNA序列。
每个输入长度随机选择10条序列，每条序列运行3次，取平均执行时间。表1中4 K和8 K长度下的硬件执行时间为模拟结果。
从表2可以看到，软件搜索时间随着序列规模的增长而急剧增加(BLASTp由128 bps时的1901 ms 增加至8 Kbps时的61,162 ms，BLASTn由128 bps时的6225 ms增加至8 Kbps时的15,344 ms)，而硬件
具有同时多种子检测与并行扩展能力的BLAST算法加速器研究Table 2. Execution time (ms) and speed-up for different queries
表2.BLASTp和BLASTn算法加速效果(时间单位：毫秒)
阵列规模
BLASTp BLASTn
软件硬件加速比软件硬件加速比
128 1901 1047 1.82 6625 1115 5.58
512 5603 1090 5.14 8904 1147 7.76
1 K 9327 1157 8.06 9953 1180 8.43
3 K 25132 1487 16.9 12360 1260 9.81
4 K(*)32469 1620 20.0 13,531 1316 10.3
8 K(*)61162 2207 27.2 15,344 1393 11.0
搜索时间增长很缓慢。主要原因是随着序列长度的增加，软件建立索引表和执行搜索过程的开销都显著增加，而硬件搜索时间等于数据库流过阵列的时间加上停顿时间(即L + S + 停顿时间)。在这三个参数中，S为常量(等于数据库包含的字符数)，与S相比，请求序列长度L的增加可以忽略不计，而停顿时间与种子数量直接相关。由于采用了多种优化策略施，在目标数据库确定的情况下，L的增加并不会导致种子数量和扩展开销急剧增加，所以加速比会相应增大。当输入序列长度为3072 bps时，使用算法加速器执行BLASTp和BLASTn程序搜索目标数据库，可分别获得约17倍和10倍的加速比；而模拟结果显示，当序列长度为8 Kbps时，可获得27倍和11倍的加速效果。
5.3. 性能功耗比
目前单个微处理器的平均功耗约为70 W~ 95 W [25]，而使用Xilinx ISE Xpower工具的功耗分析结果表明，算法加速器功耗不超过10 W，XC5VLX330芯片的最大功耗小于30 W，仅为微处理器功耗的30%左右。因此就性能功耗比而言，基于FPGA平台的细粒度并行BLAST算法加速器方案明显优于传统的基于通用微处理器的解决方案。
6. 结论
本文提出一种基于脉动阵列结构的具备同时多种子检测与并行扩展能力的BLAST算法加速器，并构建原型系统实现了对NCBI BLAST程序前两个阶段的加速。
文章提出了同时多种子检测算法，并设计了基于线性结构的并行多种子搜索阵列；采用阵列分组和并行种子收集、组内种子合并和多种子并行扩展策略实现了无阻塞的数据库搜索，成功对BLAST算法实现硬件加速，相对于通用微处理器取得了20倍以上的加速效果。此外，本文提出的多种子并行检测方法同样适用于对多种启发式搜索算法的种子(单词)检测阶段实现硬件加速。
基金项目
国家自然科学基金，基于异构平台的高复杂度生物序列分析算法并行化研究(61202127)，湖南省2013年学位与研究生教育专项基金(YB2013B008)。
参考文献(References)
[1]Altschul, S.F., Gish, W., Miller, M., Myers, E.W. and Lipman, D.J. (1990) Basic local alignment search tool. Journal
of Molecular Biology, 215, 403-410.
[2]Kim, T.K., et al. (2005) HGBS: A hardware-oriented grid blast system. Proceedings of 5th International Symposium on
具有同时多种子检测与并行扩展能力的BLAST算法加速器研究
Cluster Computing and the Grid, 1, 520-526.
[3]Yutao, Q. and Feng, L. (2003) Cyberparablast: The parallelized blast web server.Proceedings of 2nd International
Conference on Cyberworlds (CW’03), 3-5 December 2003, 474-477.
[4]Farmerie, W.G., Hammer, J., Liu, L. and Schneider, M. (2003) Having a blast: Analyzing gene sequence data with
blastquest. Proceedings of 14th International Workshop on Database and Expert Systems Applications (DEXA’03),
Prague, 1-5 September 2003, 37-41.
[5]Bjornson, R., Sherman, A., Weston, S., Willard, N. and Wing, J. (2002) Turboblast: A parallel implementation of blast
built on the turbo-hub. Proceedings of 16th International Parallel and Distributed Processing Symposium (IPDPS’02),
Ft. Lauderdale, 15-19 April 2002, 183-190.
[6]Lin, H., Ma, X., Chandramohan, P., Geist, A. and Samatova, N. (2005) Efficient data access for parallel blast. Pro-
ceedings of the 19th International Parallel and Distributed Processing Symposium (IPDPS’05), 1, 8 p.
[7]Oehmen, C. and Nieplocha, J. (2006) Scalablast: A Scalable Implementation of BLAST for High-Performance Data-
Intensive Bioinformatics Analysis. IEEE Transaction on Parallel and Distributed Systems, 17, 740-749.
[8]National Center for Biotechnology Information (2014) Notes on GenBankstatistics.
https://www.wendangku.net/doc/ea5806605.html,/genbank/statistics
[9]Buhler, J.D., Lancaster, J.M., Jacob, A.C. and Chamberlain, R.D. (2007) Mercury Blastn: Faster DNA sequence com-
parison using a streaming hardware architecture. Proceedings of 3rd Annual Reconfigurable Systems Summer Institute
(RSSI’07), Urbana, 17-20 July 2007, 10 p.
[10]Krishnanurthy, P., Buhler, J., Chamberlain, R., et al. (2007) Biosequence similarity search on the mercury system.
Proceedings of 15th IEEE International Conference on Application-Specific Systems, Architectures and Processors
(ASAP’04), 365-375. Journal of VLSI Signal Process System, 49, 101-121.
[11]Lancaster, J.M., Buhler, J.D. and Chamberlain, R.D. (2009) Acceleration of ungapped extension in Mercury BLAST.
Journal of Microprocessors & Microsystems, 33, 281-289.
[12]Jacob, A., Lancaster, J., Buhler, J. and Chamberlain, R.D. (2007) FPGA-accelerated seed generation in Mercury
BLASTP. Proceedings of the 15th Annual IEEE Symposium on Field-Programmable Custom Computing Machines,
Napa, 23-25 April 2007, 95-106.
[13]Muriki, K. and Underwood, K.D. and Sass, R. (2005) RC-BLAST: Towards a portable, cost-effective open source
hardware implementation. Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium,
Denver, 4-8 April 2005, 196-203.
[14]Herbordt, M.C., Model, J., Gu, Y.F., Sukhwani, B. and Van Court, T. (2006) Single pass, blast-like, approximate string
matching on FPGAs. Proceedings of 14th Annual IEEE Symposium on Field-Programmable Custom Computing Ma-
chines, Napa, 24-26 April 2006, 217-226.
[15]Lavenier, D., Xinchun, L. and Georges, G. (2006) Seed-based genomic sequence comparison using a FPGA/FLASH
accelerator. Proceedings of IEEE International Conference on Field Programmable Technology, Bangkok, 13-15 De-
cember 2006, 41-48.
[16]Sotiriades, E. and Dollas, A. (2007) Design space exploration for the BLAST algorithm implementation. Proceedings
of the 15th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, Napa, 23-25 April 2007,
323-326.
[17]Sotiriades, E., Kozanitis, C. and Dollas, A. (2006) FPGA based architecture for DNA sequence comparison and data-
base search. Proceedings of the 20th IEEE International Parallel and Distributed Processing Symposium, Rhodes Isl-
and, 25-29 April 2006, 186-193.
[18]Chang, C. (2012) BLAST implementation on BEE2. Technical Report, Electrical Engineering and Computer Science
University of California at Berkeley. https://www.wendangku.net/doc/ea5806605.html,
[19]CLC desktop Hardware-acceleration. White Paper on CLC Bioinformatics Cube, 2006. https://www.wendangku.net/doc/ea5806605.html,
[20]Mitrion. Inc. (2009) Ncbi blast accelerator. https://www.wendangku.net/doc/ea5806605.html,
[21]Timelogic Biocomputing Solisions (2010) Timelogic decypher BLAST engine introduction.
https://www.wendangku.net/doc/ea5806605.html,/decypher_blast.html
[22]NCBI BLAST software download, 2010. ftp://https://www.wendangku.net/doc/ea5806605.html,/blast/
[23]European Bioinformatics Institute, EBI (2008) EBI database web.
https://www.wendangku.net/doc/ea5806605.html,/uniprot/database/download.html
[24]National Center for Biotechnology Information (2009) BLAST database web. https://www.wendangku.net/doc/ea5806605.html,/Blast.cgi
[25]General purpose micro-processor power dissipation statistic. List of CPU power dissipation figures, 2014.
https://www.wendangku.net/doc/ea5806605.html,/wiki/ListofCPUpowerdissipation
一种基于置信度稳定性的SCMA多用户检测算法
第46卷 第1期2019年1月 计算机科学COM PU T ER SCIENCE Vol .46No .1Jan .2019 到稿日期：2017-12-21 返修日期：2018-03-23 本文受国家高技术研究发展计划项目（2015A A 01A 704），上海市自然科学基金（15ZR 1447600），中国科学院重点部署项目（KG FZD -135-18-013，Y T ）资助。 李 茂（1990－），男，硕士生，主要研究方向为稀疏扩频通信，E -mail ：limao 693＠sina .com ；周志刚（1974－），男，博士，研究员，主要研究方向为 毫米波高速通信，E -mail ：zhigang .zhou ＠mail .sim .ac .cn （通信作者）；王 涛（1991－），男，硕士生，主要研究方向为波束赋形。 一种基于置信度稳定性的ＳＣＭＡ多用户检测算法 李 茂 1，2 周志刚1 王 涛 1，2 （中国科学院上海微系统与信息技术研究所 上海200050）1 （中国科学院大学 北京100049） 2 摘 要 稀疏码分多址（即非正交多址）（Sparse Code M ultiple Access ，SCM A ）技术，具有在有限频谱资源下过载通信的特点，能够显著提升频谱利用率。得益于稀疏码分多址码本的稀疏性，消息传递算法（M essage Passing Algorithm ，M PA ）成为经典多用户检测算法。在传统M PA 方法中，尽管与最大似然译码具有相近的误比特率（Bit Error Ratio ， BER ）性能，但指数运算的复杂度仍然很高。据此，设计一种基于置信度的动态边缘选择更新方法，以减少不必要的节点运算。每次迭代中，利用因子图模型中功能节点到变量节点的置信度稳定性信息，动态判定是否需要节点更新运 算。仿真结果表明，动态边缘选择方案使得算法的复杂度得到显著降低，并且能够与BER 取得良好的均衡。关键词 稀疏码分多址，消息传递算法，动态边缘选择，置信度传播 中图法分类号 T N 929.5 文献标识码 A ＤＯＩ 10.11896／j .issn .1002-137X .2019.01.021 ＭｕｌｔｉｕｓｅｒＤｅｔｅｃｔｉｏｎＳｃｈｅｍｅｆｏｒＳＣＭＡＳｙｓｔｅｍｓＢａｓｅｄｏｎＳｔａｂｉｌｉｔｙｏｆＢｅｌｉｅｆＰｒｏｐａｇａｔｉｏｎ LI Mao 1，2 ZHOU Zhi -g ang 1 WANG Tao 1， 2 （Shanghai Institute of Microsystem and Information T echnology ，Chinese Academy of Sciences ，Shanghai 200050，China ）1 （U niversity of Chinese Academy of Sciences ，Beijing 100049，China ）2 Ａｂｓｔｒａｃｔ The main feature of sparse code multiple access ，i .e .，non -orthogonal multiple access ，is supported by over -loaded connection with limited resources ，which can greatly improve the spectrum utilization .Thanks to the sparsity of the SCM A codebook sets ，M PA becomes a basic receiver decoding algorithm .Although there exists a similar bit error ratio （BER ）p erformance between the maximum likelihood （M L ）detection scheme and traditional M AP method ，the complexity of the exponential calculation is still high .To further reduce the complexity problem ，a novel low -complexity detection algorithm based on dynamic edge selection strategy was proposed to reduce unnecessary node operation .In each iteration ，the belief propagation stability information of the function node to the variable node in the factor graph model is used to dynamically determine whether a node update operation is required .The simulation results show that the complexity of the dynamic edge selection algorithm is significantly reduced ，and the BER can be well balanced . Ｋｅｙｗｏｒｄｓ Sparse code multiple access ，Message passing algorithm ，Dynamic edge -selection ，Belief propagation 1 前言 随着移动和物联网（Internet of Things ，IoT ）设备数量呈指数型增长，未来5G 蜂窝网需要具备大规模连接、超密度及低延迟的特性，以完成对不同应用场景的支持［1］。现阶段4G 通信主要通过OFDM 与M IM O 联合调制的方式提高频谱利用率，但OFDM 本身的正交性及M IMO 天线技术在空间分集、复用和波束赋形3种模式的冲突，使其不具备过载通信的能力［2-3］。作为编码域非正交技术，稀疏码分多址在大规模连接和过载通信方面表现出巨大的优势，成为5G 空口技术的主要候选者之一［4］。 低密度签名（Low Density Signature ，LDS ）作为一种非正交技术，是CDM A 系统在增加低密度扩频序列后的演进技术，使过载率达到200％以上，并且使用迭代多用户检测方式来降低算法复杂度［5］。SCM A 的本质是基于LDS 和QAM 调制技术的联合改进，综合了LDS 的过载通信能力和QAM 的抗噪声性能［4，6］ 。与LDS 技术的不同之处在于，SCM A 能 够将二进制比特流根据预定义码本直接编码映射至多维复数域［6］。将QAM 调制和LDS 扩频矩阵组合成多维星座码本的形式，使得SCM A 还能够提供额外的星座整型和编码增益，同时也为构建小尺寸星座图提供可能［7］。因此，参考LDS 稀疏矩阵解码方式，将消息传递算法作为多用户检测基 万方数据
基于两点乘积及全波傅里叶算法的应用
2.两点乘积算法： 程序： %两点乘积算法,输入正弦波，取得电气角度相隔pi/2的采样时刻的数据值，计算出正弦量的有效值。 clear; N=12; %每周期采12个点 for n=0:48; t=0.02*n/N; y=sin(2*pi*n/N); %输入正弦波量y=sin(w*t) s(1,n+1)=y; %将y采样所得的值赋值给s if n>3 a=s(1,n-3); %输出相差0.5*pi的两点采样值 b=s(1,n); Ym=sqrt(a^2+b^2); Y=Ym/1.414; %输出正弦量的有效值 subplot(211) %绘制t-Y，即正弦量有效值与时间关系的图形 plot(t,Y,'-bo'); pause(0.005); xlim([-0.01,0.08]); ylim([0,1]); hold on end subplot(212); %绘制t-y，输入与时间关系的即图形 plot(t,y,'-bo'); pause(0.005); hold on end
基于两点乘积及全波傅里叶算法的应用 利用全波傅里叶算法和两点乘积算法计算 1.全波傅里叶算法： 程序： %全波傅里叶算法 clear N=24; %每周期采24个点 for n=0:96; t=0.02*n/N; y=sin(2*pi*n/N); %输入正弦波量y=sin(w*t) x1(1,n+1)=y; %将y采样所得的值赋值给x1 if n>24 X1s=0; X1c=0; for k=(n-24):(n-1) a1=x1(1,k); a2=a1*sin(2*k*pi/N); X1s=a2+X1s; end for j=(n-24):(n-1) b1=x1(1,j); b2=b1*cos(2*j*pi/N); X1c=b2+X1c; end X1s=(2/N)*X1s; %输出正弦系数 x1(2,n+1)=X1s; X1c=(2/N)*X1c; %输出余弦系数 x1(3,n+1)=X1c; X=sqrt(0.5*(X1s^2+X1c^2)); %求出基波分量有效值 x1(4,n+1)=X; end if n<24 X=0; end subplot(212); %绘制t-X，即基波分量有效值与时间关系的图形 plot(t,X,'-bo'); xlim([0,0.1]); ylim([0,1]); pause(0.0005); hold on subplot(211); %绘制t-y，即输入与时间关系的图形 plot(t,y,'-ok');
SCMA系统多用户检测算法研究.doc
SCMA系统多用户检测算法研究 稀疏码多址接入(Sparse Code Multiple Access,SCMA),作为一个前景广阔的5G无线空口技术,是一种基于码本的频谱效率较优的非正交多址接入技术,现有的SCMA多用户检测算法主要是消息传递算法(Message Passing Algorithm,MPA),MPA算法是一种接近最优的最大后验概率检测算法性能的次优的多用户检测算法,该算法在迭代过程中,函数节点与变量节点的消息在因子图中并行传递,即首先更新函数节点消息,然后更新变量节点消息,本质上该算法是基于并行策略的思想。本文针对现有的SCMA系统接收端基于并行传递的MPA算法(Parallel MPA,PMPA)存在信息收敛不理想以及算法复杂度过高的问题,从提升误比特率(Bit Error Ratio,BER)性能和降低算法复杂度两个角度改进PMPA 算法,得到两类改进算法,即基于串行策略的MPA算法(Serial MPA,SMPA)和基于残差的动态消息调度策略的MPA算法(Residual Dynamic MPA,R-DMPA)。SMPA算法以函数节点或变量节点为序,具体地提出基于函数节点串行更新的MPA算法(Function Node Serial MPA,FN-SMPA)和基于变量节点串行更新的MPA算法(Variable Node Serial MPA,VN-SMPA),SMPA算法按串行方式进行消息更新与传递,保证更新消息能够立即进入当前迭代过程,改善了消息传递的收敛速 率;R-DMPA算法引入了残差的概念对节点更新的顺序进行排序,优先更新残差值大的节点消息,相较于PMPA和SMPA算法,R-DMPA算法的收敛速率更快,已更新的消息能够更快地融入到当前迭代过程。 仿真结果验证了EXIT图分析的正确性。最后通过外信息转移图(Extrinsic Information Transfer,EXIT)这一数学工具从理论上分析MPA算法的收敛特性。首先将SCMA接收机检测器分为函数节点译码器和变量节点译码器,然后给出译
向量 - 向量叉乘 向量点乘
向量- 向量叉乘向量点乘 2010年07月28日星期三14:33 向量（Vector） 在几乎所有的几何问题中，向量（有时也称矢量）是一个基本点。向量的定义包含方向和一个数（长度）。在二维空间中，一个向量可以用一对x和y来表示。例如由点（1,3）到（5,1的向量可以用(4,-2）来表示。这里大家要特别注意，我这样说并不代表向量定义了起点和终点。向量仅仅定义方向和长度。 向量加法 向量也支持各种数学运算。最简单的就是加法。我们可以对两个向量相加，得到的仍然是一个向量。我们有： V1（x1, y1）+V2（x2, y2）=V3(x1+x2, y1+y2) 下图表示了四个向量相加。注意就像普通的加法一样,相加的次序对结果没有影响（满足交换律），减法也是一样的。 点乘（Dot Product） 如果说加法是凭直觉就可以知道的，另外还有一些运算就不是那么明显的，比如点乘和叉乘。点乘比较简单，是相应元素的乘积的和： V1( x1, y1) V2(x2, y2) = x1*x2 + y1*y2 注意结果不是一个向量，而是一个标量（Scalar）。点乘有什么用呢，我们有： A B = |A||B|Cos(θ) θ是向量A和向量B见的夹角。这里|A|我们称为向量A的模(norm)，也就是A的长度，在二维空间中就是|A| = sqrt(x2+y2)。这样我们就和容易计算两条线的夹角：Cos(θ) = A B /(|A||B|) 当然你知道要用一下反余弦函数acos()啦。（回忆一下cos(90)=0 和cos(0) = 1还是有好处的，希望你没有忘记。）这可以告诉我们如果点乘的结果，简称点积，为0的话就表示这两个向量垂直。当两向量平行时，点积有最大值 另外，点乘运算不仅限于2维空间，他可以推广到任意维空间。（译注：不少人对量子力学中的高维空间无法理解，其实如果你不要试图在视觉上想象高维空间，而仅仅把它看成三维空间在数学上的推广，那么就好理解了）
数据结构课程设计计算器
数据结构课程设计报告 实验一：计算器 设计要求 1、问题描述：设计一个计算器，可以实现计算器的简单运算，输出并检验结果的正确性，以及检验运算表达式的正确性。 2、输入：不含变量的数学表达式的中缀形式，可以接受的操作符包括+、-、*、/、%、(、)。 具体事例如下： 3、输出：如果表达式正确，则输出表达式的正确结果；如果表达式非法，则输出错误信息。 具体事例如下： 知识点：堆栈、队列 实际输入输出情况： 正确的表达式
对负数的处理 表达式括号不匹配 表达式出现非法字符 表达式中操作符位置错误 求余操作符左右出现非整数 其他输入错误 数据结构与算法描述 解决问题的整体思路： 将用户输入的中缀表达式转换成后缀表达式，再利用转换后的后缀表达式进行计算得出结果。 解决本问题所需要的数据结构与算法： 用到的数据结构是堆栈。主要算法描述如下： A．将中缀表达式转换为后缀表达式： 1. 将中缀表达式从头逐个字符扫描，在此过程中，遇到的字符有以下几种情况： 1）数字 2）小数点 3）合法操作符+ - * / %
4）左括号 5）右括号 6）非法字符 2. 首先为操作符初始化一个map 《并行算法设计与分析》考题与答案 一、1.3，处理器PI的编号是： 解：对于n ×n 网孔结构,令位于第j行，第k 列（0≤j，k≤n-1）的处理器为P i（0≤i≤n2-1）。以16处理器网孔为例,n=4（假设j、k由0开始）： 由p0=p(j,k)=p(0,0) P8=p(j,k)=p(2,0) P1=p(j,k)=p(0,1) P9=p(j,k)=p(2,1) P2=p(j,k)=p(0,2) P10=p(j,k)=p(2,2) P3=p(j,k)=p(0,3) P11=p(j,k)=p(2,3) P4=p(j,k)=p(1,0) P12=p(j,k)=p(3,0) P5=p(j,k)=p(1,1) P13=p(j,k)=p(3,1) P6=p(j,k)=p(1,2) P14=p(j,k)=p(3,2) P7=p(j,k)=p(1,3) P15=p(j,k)=p(3,3) 同时观察i和j、k之间的关系，可以得出i的表达式为：i= j * n+k 一、1.6矩阵相乘（心动算法） a)相乘过程 设 A 矩阵= 121221122121 4321 B 矩阵=1 23443212121121 2 【注】矩阵元素中A(i,l)表示自左向右移动的矩阵，B(l,j)表示自上向下移动的矩阵，黑色倾斜加粗标记表示已经计算出的矩阵元素,如12, C(i,j)= C(i,j)+ A(i,l)* B(l,j) 1 2、 4、 6、 8、 10 计算完毕 b)可以在10步后完成，移动矩阵长L=7，4*4矩阵N=4,所以需要L+N-1=10 信息科学 DS-CDMA中经典多用户检测算法 丁文秋 （南京信息职业技术学院，江苏南京210046） 引言 CDMA是在第三代移动通信系统中被广泛应用的一种多址技术，其最早是在军事通信领域为了抗干扰而诞生并且得到广泛研究的，它的主要原理是利用信号的正交性原理，通过相互正交或准正交的扩频码（Spreading Code），以及不同形状的码片（CHIPS）构建相互正交或准正交的特征信号（Sig-nature Waveform），用来作为各个用户数字信息的载体。CDMA信号中不同用户的信息相互叠加，占据相同的信号带宽。如果用户扩频码之间不能严格正交，则会引起用户间相互干扰，即“多址干扰MAI”，这也是CDMA系统的自干扰特性[1]。随着用户数增多，MAI将增大，接收机的误码率性能也会随之变差。多用户检测是一种从接收端设计入手的干扰抑制方法，主要作用是从各个用户信息相互叠加的信号中可靠地解调出部分或全部用户的信息。多用户检测技术是消除多址干扰，提高系统性能的有效方法。 1CDM A信号的模型 在对CDMA信号的研究中，通常用到离散CDMA信号模型，如下所示[1] (1) 式中，为每个码片持续时间T c内的信号构成的信号向量（N×1），S 为扩频码集矩阵（N×K）A为幅度对角矩阵diag （K×K）, 为系统中K个用户在同一比特持续时间内要传送的比特信息构成的向量(K×1)，为零均值，方差为的高斯随机向量（N×1）。 2最优多用户检测算法（ML） 不确定性最优多用户检测算法是1986年Verdu提出的最大似然（ML）多用户检测算法[1]。对于同步CDM A系统，接收信号的最佳解调向量如下表示: (2) 对于CDMA系统中同时传送信息的K个用户来说，每个用户传送信息b k的取值有＋1和－1两种可能，向量的组合有2k种，这种算法的目的就是要从2k种组合的用户信息向量中找出一种使似然函数最大的输出信息向量。使用该算法时，用户每发送一个比特信息，该算法的复杂度为。实际的CDMA系统具有相当庞大的活动用户数量，该算法的复杂度随用户数量的增加呈指数上涨，实际的系统中该算法运算的复杂度会使得系统难以忍受。 3解相关多用户检测算法(DEC) 多址干扰是由于不同用户的扩频码不能完全正交引起的[2]。抑制多址干扰的影响，去除所有用户扩频码之间的相关性，是解相关检测的基本思想。 考虑离散CDMA信号模型： 第一步，用转置后的扩频码集矩阵S左乘信 号Y得到匹配信号Z (3) 其中，叫做相关矩阵，第一步的处理实 质上就是对每个用户进行匹配的单用户检测。 第二步，对相关矩阵R求逆，得到R-1。 第三步，用R-1左乘第一步中得到的匹配信号 Z，并对结果进行判决： (4) (5) 由于需要计算相关矩阵的逆矩阵，使得解相 关多用户检测算法的计算复杂度达到了[3]。 4最小均方多用户检测算法(MM SE) 最小均方（M MSE）多用户检测算法同时考虑 了背景噪声和多址干扰，该多用户检测算法的实质 是使发送的信息与检测输出数据的均方误差最小， 即代价函数最小[4]，其检测过程如下： (6) 其中为相关矩阵，A为振幅矩阵， 为高斯白噪声的方差。将线性变换矩阵与匹配 滤波器组输出向量相乘得到最小均方误差检测器 输出，再对此输出进行判决 (7) (8) 和解相关多用户检测一样最小均方多用户检 测算法也需要计算相关矩阵的逆，在运算复杂度上 相对解相关多用户检测算法没有改变。 5连续干扰抵消多用户检测算法(SIC) 在CDM A通信系统中，干扰抵消是一种有效 的次最优抗干扰方法[5]，它属于非线性多用户检测 算法。干扰抵消的基本思路是分别估计每个用户产 生的多址干扰，接着减去所有的多址干扰，其中典 型的一种算法为迫零判决反馈多用户检测算法 （ZF-DF），其主要过程如下： 首先由于系统的相关矩阵R是正定的，对其 做QR分解R=M F，其中M是一个可逆阵，F为一 个下三角阵，对M矩阵求逆，得到M-1，用M-1做为 系统的白化噪声滤波器，过程如下： (9) 由上式的结果，可以看出，因为F是下三角矩 阵，所以第一个用户的比特信息不含多址干扰，可 以直接判决得出；第二个用户比特信息的多址干扰 只来自第一个用户相同时间发送的比特信息，所以 第二个用户只需要根据已判决出来的第一个用户 的比特信息进行串行干扰抵消，进而判决，便可以 得到自己的比特信息。 6并行干扰抵消多用户检测算法（PIC） 与连续干扰抵消多用户检测算法不同，并行 干扰抵消多用户检测算法并行地估计和去除所有 其他用户的多址干扰[6]。算法的基本思想是利用接 收信号的初始值(或前级)判决值，构造所有用户的 干扰信号，然后再同时并行从接收信号中抵消掉所 有用户的干扰。 这种多用户检 测算法通常具 有多级结构。并 行干扰抵消多 用户检测的第 m+1步计算输 出由第m步计 算结果输入而得到，具体计算过程可以用下式表 示： (10) 其中Z为匹配滤波器组的输出向量，R为相 关矩阵，I为单位矩阵。 性能仿真比较 本文对各种经典多用户检测算法进行性能比 较，仿真程序采用MATLAB，扩频码采用Walsh序 列，每个用户传100000个比特的信息，对用户比 特信息进行扩频后采用BPSK调制，然后发送在高 斯白噪声信道上传输，以图1中横坐标为系统中的 比特信噪比，单位为dB，纵坐标为用户1的误比特 率。其中PIC算法采用了2级的结构，SIC算法没 有对用户信号功率进行排序，而ZF-DF算法对用 户信号功率进行了排序，对功率大的信号先进行判 决。MMSE算法和ZF-DF算法中假设对幅度矩阵 A的估计都是准确的。从图1可以看出，对于 DS-CDMA系统若只做单用户匹配解调而不做多 用户检测,用户的误码性能将大大下降(图中最上方 的曲线),各种多用户检测算法均对用户的误码性能 有一定的增益。由于在仿真中MMSE算法假设振 幅估计和噪声功率估计都是准确的所以其性能最 佳,ZF-DF算法的性能稍逊色于MMSE算法。 结论 介绍了几种经典多用户检测算法，并对算法 的性能进行仿真比较，通过比较可以看出多用户检 测算法在误码率性能上比传统的匹配解调算法有 大幅度的提高，多用户检测是一种从接收端设计入 手的干扰抑制算法，是消除多址干扰，缓解远近效 应，提高系统性能的有效方法，在后3G，乃至4G系 统中必将会得到广泛的应用。 参考文献 [1]Verdu S.Multiuser detection[M]．Cambridge University Press,1998. [2]R.Kohno,M.Hatori,H.Imai.Cancellation tech- nique of co-channel interference in asynchronous spread spectrum multiple access systems[J].Elect. And Comma.In Japan,vol.66,1983:20-29. [3]Z.Xie,R.T.Short,C.K.Rushforth.A family of sub- optimum detectors for coherent multi-user com- munications[J].IEEE JSAC,vol.8,May1990: 683-690. [4]A.Klein,G.K.Kaleh,P.W.Baier. 摘要：多址干扰以及远近效应是影响DS-CDMA系统性能的两大关键问题。多用户检测是一种从接收端设计入手的干扰抑制方法，主要作用是从用户信息相互叠加的CDMA信号中可靠地解调出部分或全部用户的信息。多用户检测技术是消除多址干扰，缓解远近效应，提高系统性能的有效方法，本文介绍了几种经典的多用户检测算法，并通过仿真给出了所介绍的经典多用户检测算法的性能比较。 关键词：DS-CDMA；多址干扰；多用户检测 （下转37页） 单片机十进制加法计算器设计 摘要 本设计是基于51系列的单片机进行的十进制计算器系统设计，可以完成计 算器的键盘输入，进行加、减、乘、除3位无符号数字的简单四则运算，并在LED上相应的显示结果。 设计过程在硬件与软件方面进行同步设计。硬件方面从功能考虑，首先选择内部存储资源丰富的AT89C51单片机，输入采用4×4矩阵键盘。显示采用3位7段共阴极LED动态显示。软件方面从分析计算器功能、流程图设计，再到程序的编写进行系统设计。编程语言方面从程序总体设计以及高效性和功能性对C 语言和汇编语言进行比较分析，针对计算器四则运算算法特别是乘法和除法运算的实现，最终选用全球编译效率最高的KEIL公司的μVision3软件，采用汇编语言进行编程，并用proteus仿真。 引言 十进制加法计算器的原理与设计是单片机课程设计课题中的一个。在完成理论学习和必要的实验后，我们掌握了单片机的基本原理以及编程和各种基本功能的应用，但对单片机的硬件实际应用设计和单片机完整的用户程序设计还不清楚，实际动手能力不够，因此对该课程进行一次课程设计是有必要的。 单片机课程设计既要让学生巩固课本学到的理论，还要让学生学习单片机硬件电路设计和用户程序设计，使所学的知识更深一层的理解，十进制加法计算器原理与硬软件的课程设计主要是通过学生独立设计方案并自己动手用计算机电路设计软件，编写和调试，最后仿真用户程序，来加深对单片机的认识，充分发挥学生的个人创新能力，并提高学生对单片机的兴趣，同时学习查阅资料、参考资料的方法。 关键词：单片机、计算器、AT89C51芯片、汇编语言、数码管、加减乘除 目录 摘要 (01) 引言 (01) 一、设计任务和要求............................. 1、1 设计要求 1、2 性能指标 1、3 设计方案的确定 二、单片机简要原理............................. 2、1 AT89C51的介绍 2、2 单片机最小系统 2、3 七段共阳极数码管 三、硬件设计................................... 3、1 键盘电路的设计 3、2 显示电路的设计 四、软件设计................................... 4、1 系统设计 4、2 显示电路的设计 五、调试与仿真................................. 5、1 Keil C51单片机软件开发系统 5、2 proteus的操作 六、心得体会.................................... 参考文献......................................... 附录1 系统硬件电路图............................ 附录2 程序清单.................................. 第四章 并行算法的设计基础 习题例题： 1. 试证明Brent 定理：令W (n)是某并行算法A 在运行时间T(n)内所执行的运算数量，则 A 使用p 台处理器可在t(n)＝O(W(n)／p+T(n))时间内执行完毕。 2. 假定P i （1≤i ≤n ）开始时存有数据d i , 所谓累加求和指用 1 i j j d =∑来代替P i 中的原始值 d i 。 算法 PRAM-EREW 上累加求和算法 输入： P i 中保存有d i , l ≤ i ≤ n 输出： P i 中的内容为 i j j l d =∑ begin for j = 0 to logn – 1 do for i = 2j + 1 to n par-do (i) P i = d i-(2^i) (ii) d i = d i + d i-(2^j) endfor endfor end (1)试用n=8为例，按照上述算法逐步计算出累加和。 (2)分析算法时间复杂度。 3. 在APRAM 模型上设计算法时，应尽量使各处理器内的局部计算时间和读写时间大致 与同步时间B 相当。当在APRAM 上计算M 个数的和时，可以借用B 叉树求和的办法。 假定有j 个处理器计算n 个数的和，此时每个处理器上分配n/p 个数，各处理器先求出自身的局和；然后从共享存储器中读取它的B 个孩子的局和，累加后置入指定的共享存储单元SM 中；最后根处理器所计算的和即为全和。算法如下： 算法 APRAM 上求和算法 输入： n 个待求和的数 输出： 总和在共享存储单元SM 中 Begin (1) 各处理器求n/p 个数的局和,并将其写入SM 中 (2) Barrier (3) for k = [ log B ( p(B – 1) + 1) ] – 2 downto 0 do 3.1 for all P i , 0 ≤ i ≤ p – 1,do if P i 在第k 级 then P i 计算其B 各孩子的局和并与其自身局和相加,然后将结果写入SM 中 endif 微机课程设计报告 题目简易计算器仿真 学院（部）信息学院 专业通信工程 班级2011240401 学生姓名张静 学号33 12 月14 日至12 月27 日共2 周 指导教师（签字）吴向东宋蓓蓓 单片机十进制加法计算器设计 摘要 本设计是基于51系列的单片机进行的十进制计算器系统设计，可以完成计 算器的键盘输入，进行加、减、乘、除3位无符号数字的简单四则运算，并在LED上相应的显示结果。 软件方面从分析计算器功能、流程图设计，再到程序的编写进行系统设计。编程语言方面从程序总体设计以及高效性和功能性对C语言和汇编语言进行比较分析，针对计算器四则运算算法特别是乘法和除法运算的实现，最终选用全球编译效率最高的KEIL公司的μVision3软件，采用汇编语言进行编程，并用proteus仿真。 引言 十进制加法计算器的原理与设计是单片机课程设计课题中的一个。在完成理论学习和必要的实验后，我们掌握了单片机的基本原理以及编程和各种基本功能的应用，但对单片机的硬件实际应用设计和单片机完整的用户程序设计还不清楚，实际动手能力不够，因此对该课程进行一次课程设计是有必要的。 单片机课程设计既要让学生巩固课本学到的理论，还要让学生学习单片机硬件电路设计和用户程序设计，使所学的知识更深一层的理解，十进制加法计算器原理与硬软件的课程设计主要是通过学生独立设计方案并自己动手用计算机电路设计软件，编写和调试，最后仿真用户程序，来加深对单片机的认识，充分发挥学生的个人创新能力，并提高学生对单片机的兴趣，同时学习查阅资料、参考资料的方法。 关键词：单片机、计算器、AT89C52芯片、汇编语言、数码管、加减乘除 《计算机系统结构》大作业 对并行算法的介绍和展望 专业计算机科学与技术 班级 111 学号 111425020133 姓名完颜杨威 日期 2014年4月17日 河南科技大学国际教育学院 对并行算法的介绍和展望 我们知道，算法是求解问题的方法和步骤。而并行算法就是用多台处理机联合求解问题的方法和步骤，其执行过程是将给定的问题首先分解成若干个尽量相互独立的子问题，然后使用多台计算机同时求解它，从而最终求得原问题的解。并行算法的研究涉及到理论、设计、实现、应用等多个方面，要保持并行算法研究的持续性和完整性，需要建立一套完整的“理论－设计－实现－应用”的学科体系，也就是所谓的并行算法研究的生态环境。其中，并行算法理论是并行算法研究的理论基础，包含并行计算模型和并行计算复杂性等；并行算法的设计与分析是并行算法研究的核心内容；并行算法的实现是并行算法研究的应用基础，包含并行算法实现的硬件平台和软件支撑技术等；并行应用是并行算法研究的发展动力，除了包含传统的科学工程计算应用外，还有新兴的与社会相关的社会服务型计算应用等。 并行算法主要分为数值计算问题的并行算法和非数值计算问题的并行算法。而并行算法的研究主要分为并行计算理论、并行算法的设计与分析、和并行算法的实现三个层次。现在，并行算法之所以受到极大的重视，是为了提高计算速度、提高计算精度，以及满足实时计算需要等。然而，相对于串行计算，并行计算又可以划分成时间并行和空间并行。时间并行即流水线技术，空间并行使用多个处理器执行并发计算，当前研究的主要是空间的并行问题。并行算法是一门还没有发展成熟的学科，虽然人们已经总结出了相当多的经验，但是远远不及串行算法那样丰富。并行算法设计中最常用的的方法是PCAM方法，即划分，通信，组合，映射。首先划分，就是将一个问题平均划分成若干份，并让各个处理器去同时执行；通信阶段，就是要分析执行过程中所要交换的数据和任务的协调情况，而组合则是要求将较小的问题组合到一起以提高性能和减少任务开销，映射则是要将任务分配到每一个处理器上。任何一个并行算法必须在一个科学的计算模型中进行设计。我们知道，任何算法必须有计算模型。任何并行计算模型必须要有为数不多、有明确定义的、可以定量计算的或者可以实际测量的参数，这些参数可以构成相应函数。并行计算模型是算法设计者与体系结构研究者之间的一个桥梁，是并行算法设计和分析的基础。它屏蔽了并行机之间的差异，从并行机中抽取若干个能反映计算特性的可计算或可测量的参数，并按照模型所定义的计算行为构造成本函数，以此进行算法的复杂度分析。 经过多年的发展，我国在并行算法的研究上也取得了显著进展，并行计算的应用已遍布天气预报、石油勘探、航空航天、核能利用、生物工程等领域，理论研究与应用普及均取得了很大发展。随着高性价比可扩展集群并行系统的逐步成熟和应用，大规模电力系统潮流并行计算和分布式仿真成为可能。目前，并行算法在地震数据处理中应用已较为成熟，近年来向更实用的基于PC机群的并行技术发展.然而，在非地震方法中，并行算法应用较少见文献报道，研究尚处于初级研究阶段。在大地电磁的二维和三维正、反演问题上，并行计算技术逐渐得到越来越多关注和重视.随着资源和能源需求的增长，地球物理勘探向深度和广度快速发展，大幅增长的数据量使得高性能并行计算机和高效的并行算法在勘探地球物理学中的发展和应用将占据愈来愈重要的地位。计算机技术在生物医学领域已经广泛应用，实践证明，并行算法在生物医学工程的各个领域中具有广泛的应用价值，能有效提高作业效率。随着电子科学技术的发展，电磁问题变得越来越复杂，为了在有限的计算机资源条件下求解大规模复杂电磁问题，许电磁学家已 安卓应用程序设计 ——简易计算器的实现院（系）名称 专业名称 学生姓名 学生学号 课程名称 2016年6月日 1.系统需求分析 Android是以Linux为核心的手机操作平台，作为一款开放式的操作系统，随着Android 的快速发展，如今已允许开发者使用多种编程语言来开发Android应用程序，而不再是以前只能使用Java开发Android应用程序的单一局面，因而受到众多开发者的欢迎，成为真正意义上的开放式操作系统。计算器通过算法实行简单的数学计算从而提高了数学计算的效率，实现计算器的界面优化，使界面更加友好，操作更加方便。基于android的计算器的设计,系统具有良好的界面；必要的交互信息；简约美观的效果。使用人员能快捷简单地进行操作，即可单机按钮进行操作，即时准确地获得需要的计算的结果，充分降低了数字计算的难度和节约了时间。 2.系统概要设计 2.1计算器功能概要设计 根据需求，符合用户的实际要求，系统应实现以下功能：计算器界面友好，方便使用，，具有基本的加、减、乘、除功能，能够判断用户输入运算数是否正确，支持小数运算，具有清除功能。 图2.1系统功能图 整个程序基于Android技术开发，除总体模块外主要分为输入模块、显示模块以及计算模块这三大部分。在整个系统中总体模块控制系统的生命周期，输入模块部分负责读取用户输入的数据，显示模块部分负责显示用户之前输入的数据以及显示最终的计算结果，计算模块部分负责进行数据的运算以及一些其他的功能。具体的说，总体模块的作用主要是生成应用程序的主类，控制应用程序的生命周期。 输入模块主要描述了计算器键盘以及键盘的监听即主要负责读取用户的键盘输入以及 响应触屏的按键，需要监听手机动作以及用指针事件处理方法处理触屏的单击动作。同时提供了较为直观的键盘图形用户界面。 显示模块描述了计算器的显示区，即该区域用于显示用户输入的数据以及最终的计算结 VB应用程序的设计方法 ——“简易计算器”教学设计 揭阳第一中学卢嘉圳 教学内容：利用所学知识制作Visual Basic程序“简易计算器” 教学目标：能熟练运用CommandButton控件及TextBox控件进行Visual Basic(以下简称VB)程序的设计，能熟练运用条件语句编写代码 教学重点:运用开发VB程序一般过程的思路来开发“简易计算器” 教学难点:分析得出实现“简易计算器”各运算功能的算法。 教材分析： 当我刚开始进行程序设计的教学时，便感觉比较难教。这是因为程序设计本身枯燥、严谨，较难理解，而且学生大多数都是初学者，没有相应的知识基础。对于《程序设计实例》，我们选用的教材是广东教育出版社出版的《信息技术》第四册，该书采用的程序设计语言是VB，而学生是仅学过了一点点简单的QB编程之后就进入《程序设计实例》的学习的。 教材为我们总结了设计VB程序的一般步骤：创建用户界面；设置控件属性；编写事件程序代码；运行应用程序。我总结了一下，其实VB程序设计可分为设计用户界面及编写程序代码两个环节。 教学过程： 一、引入新课 任务：让学生按照书上提示完成一个非常简单的VB程序——“计算器”（仅包含开方、平方、求绝对值功能）的制作。 目的：加强对CommandButton控件及TextBox控件的掌握，复习对开方、求绝对值函数的使用。 引入本节课的学习任务：设计一个简易计算器，包含加、减、乘、除、开方、平方等运算。程序界面可参考下图。 具体功能为：在Text1中输入一个数值，然后单击代表运算符的按钮则运算结果会在text2中显示出来；比如在text1中输入一个2，然后按“+”按钮，再输入一个3按“-”按钮，再输入一个-4按“*”按钮，则实际为(2-3)*(-4)；最后在text2中显示结果为4。 第5章 并行算法的一般设计策略 习题例题： 1、 令n是待排序的元素数，p＝2d是d维超立方中处理器的数目。假定开始随机选定主元x，并将其播送给所有其他处理器，每个处理器按索接收到的x，对其n/p个元素按照≤x 和＞x进行划分，然后按维进行交换。这样在超立方上实现的快排序算法如下： 算法5.6 超立方上快排序算法 输入：n个元素，B = n/p, d = log p 输出： 按超立方编号进行全局排序 Begin (1)id = processor’s label (2)for i=1 to d do (2.1) x = pivot / * 选主元 * / (2.2) 划分B为B1和B2满足B1 ≤B＜B2 (2.3) if第i位是零 then (i) 沿第i维发送B2给其邻者 (ii) C = 沿第i维接收的子序列 (iii) B= B1∪C else (i) 沿第i维发送B1给其邻者 (ii) C = 沿第i维接收的子序列 (iii) B= B2∪C endif endfor (3)使用串行快排序算法局部排序B = n/p个数 End ① 试解释上述算法的原理。 ② 试举一例说明上述算法的逐步执行过程。 2、 ① 令T = babaababaa。P =abab，试用算法5.4计算两者的匹配情况。 ② 试分析KMP算法为何不能简单并行化。 3、 给定序列（33，21，13，54，82，33，40，72）和8个处理器，试按照算法5.2构造一棵为在PRAM-CRCW模型上执行快排序所用的二叉树。 4、 计算duel(p, q)函数的算法如下： 算法5.7 计算串匹配的duel(p, q) 的算法 输入： WIT〔1: n-m+1〕，1≤p＜q≤n-m+1，(p - q) ＜ m/2 输出： 返回竞争幸存者的位置或者null（表示p和q之一不存在） Begin if p=null then duel= q else 模拟计算器 学生姓名：**** 指导老师：**** 摘要本课程设计的课题是设计一个模拟计算器的程序，能够进行表达式的计算，并且表达式中可以包含Abs()和Sqrt()运算。在课程设计中，系统开发平台为Windows ，程序设计设计语言采用C++，程序运行平台为Windows 或*nix。本程序的关键就是表达式的分离和处理，在程序设计中，采用了将输入的中缀表达式转化为后缀表达式的方法，具有可靠的运行效率。本程序做到了对输入的表达式（表达式可以包含浮点数并且Abs()和Sqrt()中可以嵌套子表达式）进行判定表达式是否合法并且求出表达式的值的功能。经过一系列的调试运行，程序实现了设计目标，可以正确的处理用户输入的表达式，对海量级数据都能够通过计算机运算快速解决。 关键词C++程序设计；数据结构；表达式运算；栈；中缀表达式；后缀表达式；字符串处理；表达式合法判定； 目录 1 引言 (3) 1.1课程设计目的 (3) 1.2课程设计内容 (3) 2 设计思路与方案 (4) 3 详细实现 (5) 3.1 表达式的合法判定 (5) 3.2 中缀表达式转化为后缀表达式 (5) 3.3 处理后缀表达式 (7) 3.4 表达式嵌套处理 (8) 4 运行环境与结果 (9) 4.1 运行环境 (9) 4.2 运行结果 (9) 5 结束语 (12) 参考文献 (13) 附录1：模拟计算器源程序清单 (14) 1 引言 本课程设计主要解决的是传统计算器中，不能对表达式进行运算的问题，通过制作该计算器模拟程序，可以做到快速的求解表达式的值，并且能够判定用户输入的表达式是否合法。该模拟计算器的核心部分就在用户输入的中缀表达式的转化，程序中用到了“栈”的后进先出的基本性质。利用两个“栈”，一个“数据栈”，一个“运算符栈”来把中缀表达式转换成后缀表达式。最后利用后缀表达式来求解表达式的值。该算法的复杂度为O(n)，能够高效、快速地求解表达式的值，提高用户的效率。 1.1课程设计目的 数据结构主要是研究计算机存储，组织数据，非数值计算程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。学习数据结构是为了将实际问题中涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。 模拟计算器程序主要利用了“栈”这种数据结构来把中缀表达式转化为后缀表达式，并且运用了递归的思想来解决Abs()和Sqrt()中嵌套表达式的问题，其中还有一些统计的思想来判定表达式是否合法的算法。 1.2课程设计内容 本次课程设计为计算器模拟程序，主要解决表达式计算的问题，实现分别按表达式处理的过程分解为几个子过程，详细的求解过程如下：1 用户输入表达式。 2 判定表达式是否合法。 3 把中缀表达式转化为后缀表达式。 4 求出后缀表达式的结果。 5 输出表达式的结果。通过设计该程序，从而做到方便的求出一个表达式的值，而不需要一步一步进行运算。并行算法设计与分析考题与答案
DS_CDMA中经典多用户检测算法
简易计算器
并行算法的设计基础
微机课设简易计算器
对并行算法的介绍和展望——学期大作业
基于安卓的计算器的设计与实现
计算器制作
习题作业-第五章 并行算法的一般设计方法
模拟计算器程序-课程设计