下载文档原格式
串串（String）又叫做字符串，是一种特殊的线性表的结构，表中每一个元素仅由一个字符组成。
随着计算机的发展，串在文字编辑、词法扫描、符号处理以及定理证明等诸多领域已经得到了越来越广泛的应用。
第一节串的定义和表示1、串的逻辑结构定义串是由零个到任意多个字符组成的一个字符序列。
一般记为：S=’ a1a2a3……a n’(n>=0)其中S为串名，序列a1a2a3……a n为串值，n称为串的长度，我们将n=0的串称为空串(null string)。
串中任意一段连续的字符组成的子序列我们称之为该串的子串，字符在序列中的序号称为该字符在串中的位置。
在描述中，为了区分空串和空格串(s=‘’)，我们一般采用来表示空串。
2、串的基本操作串一般包含以下几种基本的常用操作：1、length(S)，求S串的长度。
2、delete(S,I,L)，将S串从第I位开始删除L位。
3、insert(S,I,T)，在S的第I位之前插入串T。
4、str(N,S)，将数字N转化为串S。
5、val(S,N,K)，将串S转化为数字N；K的作用是当S中含有不为数字的字符时，K记录下其位置，并且S没有被转化为N。
3、串的储存结构一般我们采用以下两种方式保存一个串：1、字符串类型，描述为：const n=串的最大长度type strtype=string[n]这里由于tp的限制，n只能为[1..255]。
在fp或者delphi中，我们还可以使用另外一种类型，描述为：const n=串的最大长度type strtype=qstring[n]这里的n就没有限制了，只要空间允许，开多大都可以。
2、数组来保存，描述为：const n=串的最大长度type strtype=records:array[1..n] of char;len:0..n;end;第二节模式匹配问题与一般的线性表不同，我们一般将串看成一个整体，它有一种特殊的操作——模式匹配。
1．FPGA从串加载模式概述基带板上采用的FPGA是Xilinx公司Virtex-II系列XC2V3000，其配置文件的下载模式有5种：主串模式（master serial）、从串模式（slave serial）、主并模式（master selectMAP）、从并模式（slave selectMAP）、JTAG模式。
其中，JTAG模式在开发调试阶段使用。
其余四种下载模式，可分为串行下载方式和并行下载方式。
串行下载方式和并行下载方式都有主、从2种模式。
主、从模式的最大区别在于：主模式的下载同步时钟（CCLK）由FPGA提供；从模式的下载同步时钟（CCLK）由外部时钟源或者外部控制信号提供。
主模式对下载时序的要求比从模式严格得多。
因此从处理机易于控制下载过程的角度，一般选择使用从串模式或从并模式。
本设计采用从串模式进行FPGA配置，可以使实现相对简单，并且能够减少占用MPC8260的资源。
在从串模式下，进行FPGA程序加载仅需要使用五个信号引脚，此外还需要设置M[2:0]信号以选择配置模式。
所使用引脚的详细描述见下表2．从串模式下载时序和过程从串模式的配置过程将配置比特流载入到FPGA，有四个主要阶段：清除配置内存初始化载入配置数据设备启动1．上电：The V CCINT power pins must be supplied with a 1.5 V source. (Refer to the Virtex-II DataSheet for DC characteristics.) The IOB voltage input for Bank 4 (V CCO_4) and the auxiliaryvoltage input (V CCAUX) are also used as a logic input to the Power-On-Reset (POR)circuitry. Even if this bank is not being used, V CCO_4 must be connected to a 1.5 V or greater source.2．清除配置内存在内存清除阶段，非配置I/O管脚为带有可选上拉电阻的三态。
串的模式匹配算法字符串模式匹配是计算机科学中一种常用的算法。
它是一种检索字符串中特定模式的技术，可以用来在字符串中查找相应的模式，进而完成相应的任务。
字符串模式匹配的基本思想是，用一个模式串pattern去匹配另一个主串text，如果在text中找到和pattern完全匹配的子串，则该子串就是pattern的匹配串。
字符串模式匹配的过程就是在text中搜索所有可能的子串，然后比较它们是否和pattern完全匹配。
字符串模式匹配的算法有很多，其中著名的有暴力匹配算法、KMP算法、BM算法和Sunday算法等。
暴力匹配算法是最简单也是最常用的字符串模式匹配算法，其思想是从主串的某一位置开始，依次比较pattern中每一个字符，如果某个字符不匹配，则从主串的下一位置重新开始匹配。
KMP算法（Knuth-Morris-Pratt算法）是一种更为高效的字符串模式匹配算法，它的特点是利用了已匹配过的字符的信息，使搜索更加有效。
它的实现思想是，在pattern中先建立一个next数组，next数组的值代表pattern中每个字符前面的字符串的最大公共前缀和最大公共后缀的长度，这样可以在主串和模式串匹配失败时，利用next数组跳转到更有可能匹配成功的位置继续搜索，从而提高字符串模式匹配的效率。
BM算法（Boyer-Moore算法）也是一种高效的字符串模式匹配算法，它的实现思想是利用主串中每个字符最后出现的位置信息，以及模式串中每个字符最右出现的位置信息来跳转搜索，从而减少不必要的比较次数，提高搜索效率。
Sunday算法是一种简单而高效的字符串模式匹配算法，它的实现思想是，在主串中搜索时，每次从pattern的最右边开始比较，如果不匹配，则根据主串中下一个字符在pattern中出现的位置，将pattern整体向右移动相应位数，继续比较，这样可以减少不必要的比较次数，提高算法的效率。
字符串模式匹配算法的应用非常广泛，它可以用来查找文本中的关键字，检查一个字符串是否以另一个字符串开头或结尾，查找文本中的模式，查找拼写错误，检查字符串中是否包含特定的字符等。
数据结构—串的模式匹配数据结构—串的模式匹配1.介绍串的模式匹配是计算机科学中的一个重要问题，用于在一个较长的字符串（称为主串）中查找一个较短的字符串（称为模式串）出现的位置。
本文档将详细介绍串的模式匹配算法及其实现。
2.算法一：暴力匹配法暴力匹配法是最简单直观的一种模式匹配算法，它通过逐个比较主串和模式串的字符进行匹配。
具体步骤如下：1.从主串的第一个字符开始，逐个比较主串和模式串的字符。
2.如果当前字符匹配成功，则比较下一个字符，直到模式串结束或出现不匹配的字符。
3.如果匹配成功，返回当前字符在主串中的位置，否则继续从主串的下一个位置开始匹配。
3.算法二：KMP匹配算法KMP匹配算法是一种改进的模式匹配算法，它通过构建一个部分匹配表来减少不必要的比较次数。
具体步骤如下：1.构建模式串的部分匹配表，即找出模式串中每个字符对应的最长公共前后缀长度。
2.从主串的第一个字符开始，逐个比较主串和模式串的字符。
3.如果当前字符匹配成功，则继续比较下一个字符。
4.如果当前字符不匹配，则根据部分匹配表的值调整模式串的位置，直到模式串移动到合适的位置。
4.算法三：Boyer-Moore匹配算法Boyer-Moore匹配算法是一种高效的模式匹配算法，它通过利用模式串中的字符出现位置和不匹配字符进行跳跃式的匹配。
具体步骤如下：1.构建一个坏字符规则表，记录模式串中每个字符出现的最后一个位置。
2.从主串的第一个字符开始，逐个比较主串和模式串的字符。
3.如果当前字符匹配成功，则继续比较下一个字符。
4.如果当前字符不匹配，则根据坏字符规则表的值调整模式串的位置，使模式串向后滑动。
5.算法四：Rabin-Karp匹配算法Rabin-Karp匹配算法是一种基于哈希算法的模式匹配算法，它通过计算主串和模式串的哈希值进行匹配。
具体步骤如下：1.计算模式串的哈希值。
2.从主串的第一个字符开始，逐个计算主串中与模式串长度相同的子串的哈希值。
串的模式匹配算法——BF算法在主串中，从指定的起始位置pos开始，⽤i和j分别指⽰主串S和模式T中正待⽐较的字符位置，i的初值为pos，j的初值为1。
i与j所指⽰的字符⽐较，若相等，则i与j指⽰的位置同时后移，⽐较下⼀对字符。
若不等，从主串的下⼀个字符（i=i-j+2）开始重新和模式T 的第⼀个字符（j=1）⽐较。
若j⼤于模式T的长度，则说明匹配成功，返回和模式T的第⼀个字符相等的字符在主串S中的序号（i-T.length）。
否则匹配失败。
1public class BF {2public static void main(String[] args) {3 String S="ababcabcacbab";4 String T="abcac";5char[] charS=S.toCharArray();6char[] charT=T.toCharArray();7int pos=1;8 run(charS,charT,pos);9 }10public static void run(char[] charS,char[] charT,int pos) {11int i=pos;12int j=1;13while(i<=charS.length && j<=charT.length)14 {15if(charS[i-1] == charT[j-1])16 {17 ++i;18 ++j;19 }else20 {21 i=i-j+2;22 j=1;23 }24 }25if(j>charT.length)26 {27 System.out.println("匹配成功,序号为"+(i-charT.length));28 }else29 {30 System.out.println("匹配失败");31 }32 }33 }BF算法在最坏的条件下时间复杂度为O(m×n)。
主串模式——最常用的FPGA配置模式1．配置单片FPGA在主串模式下，由FPGA的CCLK管脚给PROM提供工作时钟，相应地PROM在CCLK 的上升沿提供将数据从D0管脚送到FPGA的DIN管脚。
无论PROM芯片类型（即使其支持并行配置），都只利用其串行配置功能。
例如Spartan3E单片FPGA的主串配置电路如图5-12所示。
图5-12 Soartan-3E主从模式配置电路1）信号管脚说明其中要注意3类管脚的连接方式：首先，模式选择管脚M[2:0]在配置过程中或者INIT_B变高时，必须设置为全0，当FPGA的输出管脚DONE变高后，模式配置管脚可以作为普通I/O管脚使用；其次，HSWAP管脚的输入电平在器件配置阶段必须保持不变，可以拉低使能FPGA所有I/O管脚的上拉电阻，也可以拉高去掉FPGA所有I/O管脚的上拉电阻，当FPGA配置完毕，输出信号DONE变高后，可以作为普通I/O管脚使用；最后，FPGA的DOUT管脚仅在多芯片配置时有效，在单芯片配置中悬空。
（1）对图5-12中FPGA芯片各个管脚的功能和配置进行简单介绍，如表5-5所示。
表5-5 主串模式下FPGA配置管脚说明（2）必须要掌握从设备PROM的管脚信号。
下面对图5-12中PROM芯片各个管脚的功能和配置进行简单介绍，如表5-6所列。
表5-6 主串模式下PROM配置管脚说明2）配置电路的关键点主串配置电路最关键的3点就是JTAG链的完整性、电源电压的设置以及CCLK 信号的考虑。
只要这3步任何一个环节出现问题，都不能正确配置PROM芯片。
（1）JTAG链的完整性FPGA和PROM芯片都有自身的JTAG接口电路，所谓的JTAG链完整性指的是将JTAG 连接器、FPGA、PROM的TMS、TCK连在一起，保证从JTAG连接器TDI到其TDO 之间，形成JTAG连接器的“TDI （TDI~TDO）（TDI~TDO） JTAG连接器TDO”的闭合回路，其中（TDI~TDO）为FPGA或者PROM芯片自身的一对输入、输出管脚。
图5-12中配置电路的JTAG链从连接器的TDI到FPGA的TDI，再从FPGA的TDO到PROM的TDI，最后从PROM的TDO到连接器的TDO，形成了完整的JTAG链，FPGA芯片被称为链首芯片。
也可以根据需要调换FPGA和PROM的位置，使PROM 成为链首芯片。
（2）电源适配性如图5-13所示，由于FPGA和PROM要完成数据通信，二者的接口电平必须一致，即FPGA相应分组的管脚电压Vcco_2必须和PROM Vcco的输入电压大小一致，且理想值为2.5V，这是由于FPGA的PROG_B和DONE管脚由2.5V的Vccaux供电。
此外，由于JTAG连接器的电压也由2.5V的Vccaux提供，因此PROM的VCCJ也必须为2.5V。
因此，如果接口电压和参考电压不同，在配置阶段需要将相应分组的管脚电压和参考电压设置为一致；在配置完成后，再将其切换到用户所需的工作电压。
当然，FPGA和PROM也可以自适应3.3V的I/O电平以及JTAG电平，但需要进行一定的改动，即添加几个外部限流电阻，如图5-13所示。
在主串模式下，XCFxxS系列PROM的核电压必须为3.3V，XCFxxP系列PROM的核电压必须为1.8V。
图5-13 3.3V的JTAG配置电路示意图图5-13中的RSER、RPAR这两个电阻要特别注意。
首先，RSER= 68Ω将流入每个输入的电流限制到 9.5 mA；其次，N = 3三个输入的二极管导通，RPAR = VCCAUX min/ NIIN = 2.375V/（3*9.5mA）=83 Ω或 82 Ω（与标准值误差小于 5% 的电阻）（3）CCLK的信号完整性CCLK信号是JTAG配置数据传输的时钟信号，其信号完整性非常关键。
FPGA配置电路刚开始以最低时钟工作，如果没有特别指定，将逐渐提高频率。
CCLK信号是由FPGA内部产生的，对于不同的芯片和电平，其最大值如表5-7所示。
表5-7 不同PROM芯片的最大配置时钟频率3）主串配置电路工作流程一般FPGA芯片都有两个配置触发事件：上电复位以及软件复位。
不同配置模式的工作流程基本是一致的，下面对整个过程进行详细说明。
（1）普通配置过程当FPGA上电后，如果核电压、参考电压以及I/O电压正确，则进入配置模式。
数据首先以TCK的速度通过JTAG连接器的TDI管脚，进入FPGA芯片的TDI管脚。
然后再以同样的速率从FPGA的TDO管脚将配置数据送入PROM芯片的TDI管脚，此时PROM通过其TDO向JTAG连接器的TDO环回数据，构成完整的JTAG链；又由于FPGA芯片DONE信号为低（片选PROM芯片）、INIT_B输出电平为高（使能PROM数据输出管脚），PROM通过DO以CCLK的速率将配置数据送给FPGA。
第三，FPGA开始接收配置数据，并完成CRC校验，若CRC校验通过，DONE信号管脚输出高电平；若CRC校验失败，DONE信号为低，配置过程失败，但此时FPGA并不给出任何指示，这时由于需要在DONE管脚上添加LED以输出提示信号。
最后，PROM由于CE管脚输入为高，关闭数据输出管脚，清空地址计数器，进入休眠状态，配置结束。
（2）复位配置过程当PROG_B处于低电平超过500ns时，会强制FPGA进入重配置阶段；当PROG_B信号变高时，会清空FPGA配置存储器，并将DONE、INIT_B拉低。
由于DONE信号和PROM芯片CE信号相连，PROM片选有效。
CF信号有效，将PROM内部地址计数器清零。
当清空FPGA配置存储器后，OE/RESET变高，地址累加器开始在CLK 的上升沿加1。
FPGA配置结束后，DONE信号管脚输出高电平，PROM关闭数据输出管脚，清空地址计数器，进入休眠状态。
复位配置的过程如图5-14所示。
图5-14 复位后FPGA配置阶段示意图2．配置多片FPGA多片FPGA的配置电路和单片的类似，但是多片FPGA之间有主（Master）、从（Slave）之分，且需要选择不同的配置模式。
两片Spartan 3E系列FPGA的典型配置电路如图5-15所示，两片FPGA存在主、从地位之分。
图5-15 主从模式下两片FPGA的配置电路如果系统中有更多的FPGA芯片，只需要在后面继续添加即可，即从链首FPGA获得CCLK，将芯片TCK、TMS和JTAG连接器的TCK、TMS连接在一起，最后把上一级FPGA的TDO连接到本地TDI，并将本地TDO和JTAG连接器的TDO连在一起，构成完整的JTAG链。
当链首FPGA完成配置后，将利用其DOUT管脚为在CCLK的下降沿为后续芯片传送配置数据，而其自身在CCLK的上升沿从PROM读取配置数据。
注意：除了链首FPGA的模式选择信号M[2:0]=3’b000外，其余FPGA的模式选择信号M[2:0]=3’b111。
如果多片相同FPGA配置相同的数据，可以采用图5-16所示的配置电路。
图5-16 配置数据相同的多片相同FPGA的配置电路5.3.2 SPI串行Flash配置模式1．SPI串行配置介绍串行Flash的特点是占用管脚比较少，作为系统的数据存贮非常适合，一般都是采用串行外设接口（SPI总线接口）。
Flash存贮器与EEPROM根本不同的特征就是EEPROM可以按字节进行数据的改写，而Flash只能先擦除一个区间，然后改写其内容。
一般情况下，这个擦除区间叫做扇区（Sector），也有部分厂家引入了页面（Page）的概念。
选择Flash产品时，最小擦除区间是比较重要的指标。
在写入Flash时，如果写入的数据不能正好是一个最小擦除区间的尺寸，就需要把整个区间的数据全部保存另外一个存贮空间，擦除这个空间，然后才能重新对这个区间改写。
大多数Flash工艺更容易实现较大的擦除区间，因此较小的擦除区间的Flash的价格一般会稍贵一些。
此外， SPI是标准的4线同步串行双向总线，提供控制器和外设之间的串行通信数据链路，广泛应用于嵌入式设备中。
Xilinx公司的新款FPGA都支持SPI接口。
SPI总线通过4根信号线来完成主、从之间的通信，典型的SPI系统中常包含一个主设备以及至少一个从设备，在FPGA应用场合中，FPGA芯片为主设备，SPI串行FLASH为从设备。
4个SPI接口信号的名称和功能如表5-8所示。
表5-8 SPI接口信号列表一个主芯片和一个从芯片的通信接口如图M所示。
FPGA通过SCLK控制双方通信的时序，在SS_n为低时，FPGA通过MOSI信号线将数据传送到FLASH，在同一个时钟周期中，FLASH通过SOMI将数据传输到FPGA芯片。
无论主、从设备，数据都是在时钟电平跳转时输出，并在下一个相反的电平跳转沿，送入另外一个芯片。
图5-17 SPI接口连接示意图其中SCLK信号支持不同的速率，一般常采用20MHz。
通过SPI接口中的CPOL和CPHA这两个比特定义了4种通信时序。
其中，CPOL信号定义了SCLK的空闲状态，当CPOL为低时，SCLK的低电平为空闲状态，否则其空闲状态为高电平；CPHA定义了数据有效的上升沿位置，当其为低时，数据在第1个电平调转沿有效，否则数据在第2个电平跳转沿有效。
其相应的时序逻辑如图M所示。
图5-18a CPHA为高时SPI的总线时序示意图图5-18b CPHA为高时SPI的总线时序示意图可以通过增加片选信号SS_n的位宽来支持多个从设备，SS_n的位宽等于从设备的个数。
对于某时刻被选中的从设备和主设备而言，其读写时序逻辑和图M一样。
图5-19 多个从芯片的连接电路图SPI串行FLASH作为一种新兴的高性能非易失性存储器，其有效读写次数高达百万次，不仅引脚数量少、封装小、容量大，可以节约电路板空间，还能够降低功耗和噪声。
从功能上看，可以用于代码存储以及大容量的数据和语音存储，对于以读为主，仅有少量擦写和写入时间的应用来说，支持分区（多页）擦除和页写入的串行存储是最佳方案。
2．SPI串行FLASH配置电路SPI串行配置模式常用于已采用了SPI串行FLASH PROM的系统，在上电时将配置数据加载到FPGA中，这一过程只需向SPI串行发送一个4字节的指令，其后串行FLASH中的数据就像PROM配置方式一样连续加载到FPGA中。
一旦配置完成，SPI中的额外存储空间还能用于其它应用目的。
1）SPI配置电路虽然SPI接口是标准的4线接口，但不同的SPI FLASH PROM芯片采用了不同的指令协议。
FPGA芯片通过变量选择信号VS[2:0]来定义FPGA和SPI FLASH的通信方式、FPGA的读指令以及在有效接收数据前插入的冗余比特数。
