基于有限状态机的UART设计

微电子学与计算机 !""!年第 #!期 ! !" 随着 $%&’ 技术的发展和电路复杂性的迅速提 高，数字系统的设计方法发生了很大的变化，()* 技术得到了飞速的发展；目前，基于 ()* 技术的芯 片设计正在成为数字系统设计的主流。其中利用硬 件描述语言进行可编程 *&’+ 设计是 ()* 技术的 一个重要应用，$,)% 和 $-./012 ,)% 作为 ’((( 标 准硬件描述语言和一个工业 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 ，逐渐受到了广大 硬件设计者的欢迎并取得了广泛的应用。硬件描述 语言采用了自顶向下的设计方法，在更抽象的层次 上把握并描述了系统的功能特性及电路结构，并具 有制定电路规则时间短、易于修改、不受 工艺 钢结构制作工艺流程车尿素生产工艺流程自动玻璃钢生产工艺2工艺纪律检查制度q345焊接工艺规程 限制 等特点。随着电路规模和复杂度的增加，硬件描述 语言愈显其优越性。 本文结合 3*45 637/8-.9:0 *9;7<=.171>9 4-? <-/8-. @ 5.:79A/BB-.C的设计，探讨了利用 ,)% 设计可 编程 *&’+ 的方法，通过 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 3*45 的功能，提出利 用有限状态自动机来描述 3*45 核心控制逻辑的 方法，并将这种方法与其它方法进行了比较。 " #$%&’()*+,- 自从 +=1A9D; 于 #EFG 年建立形式语言的描述 以来，形式语言及自动机的理论发展得很快。这种 理论对计算机科学有着深刻的影响，特别是对程序 设计语言的设计、编译理论和计算复杂性等方面， 更有重大作用。作为自动机理论的重要组成部分， 有限状态自动机是具有离散输入输出系统的一种 数学模型，可用一个五元组来表示：HI6JK5K!KL"KMC， 根据每次转换的后继状态是否唯一，有限状态自动 机又可分为确定的有限状态自动机6)M*C和不确定 的有限状态自动机6NM*C。有限状态自动机的语言 识别能力等价于右线性文法，所定义的语言属于 +=1A9D;文法体系中的 O型语言6正规集C。 在硬件设计中，自动机理论也找到了用武之 地，在我们设计时序电路时，常常使用有限状态自 动机理论，手工设计一个时序电路的步骤如下： 6#C 画出状态转移图； 6!C 写出状态转移表； 6OC 写出下一个状态的布尔表达式，并尽可能地 化简； 6PC 写出输出信号的真值表； 6FC 写出输出信号的布尔表达式并化简； 6GC 根据下一状态和输出信号的布尔表达式，画 出逻辑图。 在利用 ()* 工具进行可编程 *&’+ 设计时，我 们经常使用的是一种有输出的有限状态自动机，输 出可以是控制信号也可以是最终的输出。根据输 出、自动机状态及输入三者之间的关系，又可分为 两种自动机：其一，自动机的输出不仅与它所处的 状态有关，而且与输入有关，这种自动机称为米兰 机6H-:0;C；其二，自动机的输出只与到达的状态有 关，称为摩尔机 6H11.-C；两种自动机的区分如图 # 所示。在实际设计中，可以根据具体情况选用，并对 自动机的状态选用合适的编码方式，将其存储到以 一组触发器中，下一状态是输入与当前状态的函 数，在输入的约束下在状态之间进行转换，从而完 成控制功能。 6:C H-:0;型状态机 6QC H11.-型状态机 图 # H-:0;机和 H11.-机模型示意图 输入 现态 次态 输出次态 逻辑 状态 寄存器 输出 逻辑 现态 输入 现态 次态 输出次态 逻辑 状态 寄存器 输出 逻辑 现态 # ./0123)4+( $%&’%&56 #(! $%&’789:;<=, 通用异步接受发送器 3*45 是目前广泛使用 的一种通用串行数据接口，其应用范围遍及计算机 外设、工业控制等场合。3*45的作用是，它既可以 ./0123+( $%&’%& M&HRS:9-T )-9/27 H-B=1T1012; U1. 3*45 西安微电子技术研究所 >?@ ABC 6西安 V#""FPC 摘 要：文章结合 3*45 的设计，分析阐述了硬件设计中的有限状态自动机理论；并在分析 3*45 功能特点的 基础上，给出了利用有限状态自动机理论进行 3*45设计的实例。与其他设计方法相比较，利用有限状态自动机 理论设计控制逻辑具有直观简单、设计流程短等优点，在 ()*技术中必将发挥重要的作用。 关键字：3*45，有限状态自动机，()*技术，,)%描述 收稿日期W !""!R"FR#" F! !""!年第 #!期 微电子学与计算机 接收外围设备的串行数据输入，并转换成计算机内 部所需的并行数据，也可以把计算机内部的并行数 据转换成串行数据，并发送给外围设备。$%&’主要 由接收器、发送器和控制部分组成，其中接收器和 发送器部分都是双缓冲结构。$%&’传送的每个串 行字符由四个部分组成： (#) 一个低电平开始位； (!) *+,个有效数据位； (-) 一个奇偶校验位； (.) #+!个高电平停止位。 两个相邻串行字符之间的间隔是高电平的空 闲位，它可以是任意长度。下一个字符的开始，必然 是以高电平的停止位或空闲位变为低电平的开始 位为标志。 $%&’在发送或接收数据时，使用的时钟信号 频率是波特率的 #/ 倍，我们称这个时钟信号为波 特时钟，这个时钟由 $%&’ 对外部输入的系统时钟 进行分频得到。$%&’每 #/个波特时钟发送或接收 一个二进制位，图 ! 表示了 $%&’ 对数据的采样情 形。 图 ! $%&’对数据的采样 启动检测 确定检测到开始位 采样数据 01203 #/’ 启动位 4%’% 在发送时，由 05$ 来的并行数据由缓冲器接 收，然后送至发送移位寄存器，在波特时钟的同步 下，首先发送低电平开始位，接着由 ’64 线将有效 数据位逐位地串行移出，最后发送奇偶校验位和停 止位，组成一个完整的数据帧。在接收时，接收器部 分监视 &64 线，当发现一个低电平信号，以后又连 续采样到 , 个波特时钟的“"”信号，则确定它是开 始位而非干扰信号，由此开始一个数据帧的接收过 程，以后每隔 #/个波特时钟脉冲采样一次 &64线。 在本次设计的 $%&’ 中，我们采用固定的波特 率、固定的奇偶校验方式(奇校验)以及固定的字符 格式：#位开始位、, 位有效数据位、# 位奇偶校验位 以及 # 位停止位；因此该 $%&’ 是一个不可编程的 串行通信接口。但是串行接口的核心功能已经实 现，由此我们可以比较容易地将其扩充为可编程的 串行通信接口。 !"# $%&’!"#$%&’()*+,- 本次设计的 $%&’ 主要由三个模块构成：波特 时钟发生器模块 789:;<=>?@A@B8CDBEF、发送器模块 CB8AGHICC@BEF以及接收模块 B@;@IF@BEF，如图 - 所示。 其中，发送器模块和接收器模块是本 $%&’ 设计的 主要组成部分，也是我们讨论的重点。 发送器部分由发送移位寄存器 CGB、发送保持寄 存器(缓冲器)CJB 以及发送控制逻辑组成；接收器部 分由接收移位寄存器 BGB、接收保持寄存器(缓冲器) BJB 以及接收控制逻辑组成，二者的接口定义如表 # 所示。下面我们将就发送器模块和接收器模块的设 计进行讨论，对于波特时钟发生器模块，由于设计 相对简单，限于篇幅，这里我们不作讨论。 表 # $%&’的模块接口定义 K L 2 方向 功能描述 公共 信号 MNG>0<= K 输入 $%&’的外部系统时钟 O89:;<= K $%&’ 工作的时钟信号，频率为 波特率的 #/ 倍 &@G@C>1 K 系统复位信号 0G>1 K 片选信号 48C8 K L 2 双向并行数据总线 发送 模块 信号 ’64 2 串行发送数据线 PBIC@>1 K 并行数据写信号，低电平有效 ’>@HQCN 2 发送缓冲器为空，可以接收下一个要发送的并行数据 接收 模块 信号 &64 K 串行接收数据线 &@8:>R K 接收的并行数据读信号，高电平 有效 &>S9<< 2 接收缓冲器满，主机可以取数据 58BICN>@BB 2 接收数据时发生奇偶校验错误 2F@BT S@BB 2 下一数据已接收完，而上一数据 尚未取走，溢出错误 VB8H@>@BB 2 接收数据时停止位不为 "，发生帧错误 !"! ./%&0!" 发送器模块的设计主要集中在其控制逻辑的 设计上，我们采用有限状态自动机来作为它的控制 *- 微电子学与计算机 !""!年第 #!期 器，在设计中，我们共定义了六个发送器工作状态： $%&’()、$%*+,-+、$%.,&+、$%*/&0+、$%1,-&+2 以及 $%*+31，该自动机的状态转换图如图 4 所示。为了 简化图示，在这里我们没有将状态机的输出在图中 表示出来，实际上，该状态机的输出都在给定的状 态中进行，根据米兰机和摩尔机的定义，我们可知 该状态机属于摩尔机的范畴，下一节将讨论的接收 模块控制逻辑亦属于摩尔机的范畴。对于这六个状 态，我们采用了独热码56789:6$ ;6<8=的编码方式，这 种编码方式虽然较二进制码5>?7@AB9;6<8=编码方式 或格雷码5CA@B9;6<8=编码方式多用了三个触发器， 但却可以省下许多组合电路，综合后的电路更加简 单，可使电路的速度和可靠性得到显著提高，而总 的单元数增加不多，这在触发器资源丰富的 01D, 器件中是一种行之有效的方法。 图 4 E,-+发送器的状态转移图 A8F8$G(HH" $G8IJ$BHH" $%1,-&+2 K "#"""" K $%*+31 K #""""" K $%*/&0+ K ""#""" K $%.,&+ K """#"" K $%*+,-+ K """"#" K $%&’() K """""# K$G8IJ$BHH# ;LMG;6N7$OH#P ;LMG;6N7$OH#Q ;LMG;6N7$OH#P ;LMG;6N7$OH#P $RG;6N7$HHS ;LMG;6N7$HH#Q ;LMG;6N7$HH#P ARG;6N7$OHHS ;LMG;6N7$HH#P ;LMG;6N7$HH#P @7< $G8IJ$B ;LMG;6N7$HH#P @7< 76$ $G8IJ$B 由于是每 #P 个波特时钟发送一个二进制位， 因此我们需要设立一个 4 位的同步计数器来计数 波特时钟；为了判断有效数据位是否发送完，我们 将 4 位的波特时钟计数器扩展到 S 位，这样计数器 的高 4 位正好表示了发送二进制位的个数，利用这 一点，可以减少控制信号，简化设计过程。 当电路复位以后，控制器首先进入 $%&’() 状 态，当检测到缓冲器 $:A 不空时，转入到 $%*+,-+状 态，控制发送器发送低电平开始位；随后进入 $%.,&+ 状态，开始发送有效数据位，当计数器计数 #Q 个波特时钟后，转入 $%*/&0+ 状态，发出移位信 号；之后进入下一 $%.,&+状态，发送下一位数据 位；当 S 位有效数据位发送完之后，进入 $%1,-&+2 状态，发送奇偶校验位；最后转入 $%*+31 状态，发 送停止位；这样就完成了一个数据帧的发送过程。 作为例证，我们给出了发送器的后仿真波形， 其中假定发送的数据是 ’Q:，并将某些重要的中间 信号也输出进行观察，见图 Q。 图 Q E,-+发送器的后仿真波形图 >@N<;LM A8F8$%( TA?$8%( ;F%( <@$@ +R’ $%8IJ$B F$@$8 F:?U$ $FA ’Q "! "4 "4 "4 "4 "4 "4 "4 "4 #" !" "# "" ’Q P, VQ #, "’ "P "V "# "" !"# !"#$%&’ 接收器模块的设计要相对复杂一些，因为它需 要正确判断接收时刻以及进行一些错误检测。对于 接收器模块，其控制逻辑仍然采用有限状态自动机 来设计，我们共定义了 P 个状态，仍采用独热码编 码方式，控制状态转移的波特时钟计数器共七位， 其中高三位计数位表示了接收的二进制数据位数。 该状态机的状态转换图如图 P所示。 图 P E,-+接收器的状态转移图 A8F8$G(HH" A%1,-&+2 K "#"""" K A%*+31 K #""""" K A%*,W1() K ""#""" K A%.,&+ K """#"" K A%*+,-+ K """"#" K A%&’() K """""# K-R’HH# ;LMG;6N7$OH#P ;LMG;6N7$OH#Q ;LMG;6N7$OH#P ;LMG;6N7$OHS $RG;6N7$HHS ;LMG;6N7$HH#Q ;LMG;6N7$HH#P ARG;6N7$OHHS ;LMG;6N7$HHS @7< -R’HH# ;LMG;6N7$HH#P -R’HH" ;LMG;6N7$HHS @7< -R’HH" 系统复位后，状态机默认为 A%&’() 状态，当检 测到 -R’ 线出现低电平信号后，则转入到 A%*+,-+ 状态，并开始对波特时钟进行计数，当计数到 S 时， 即接收位单元的中间时，若 -R’ 线上仍为低电平， 则确定这是一个开始位，随后状态机交替进入 A%.,&+ 状态和 A%*,W1() 状态接收 S 个有效数据 位，之后状态机进入 A%1,-&+2 状态接收奇偶校验 位，最后进入 A%*+31 状态接收停止位，完成一个数 据帧的接收过程。 同样，我们给出了接收器的后仿真波形，其中 Q4 !""!年第 #!期 微电子学与计算机 假定接收的数据帧是 "#"#"#"##"#，并将某些重要 的中间信号也输出进行观察，见图 $。 图 $ %&’(接收器的后仿真波形图 )*+,-./ 0121345 01*,46 -245 ’78 ,*3* 049+.. :*0;3<4⋯ 90*=14⋯ >?109.>⋯ 0423*31 2@;93 020 AA BB 8C "# "! "D "D "D "D "D "D "D "D #" !" "# "" E" D" &" C" &E CD && 8C ! !"#$%&’( 我们还采用了另外一种方法来设计 %&’(，这 种方法不用状态机来控制 %&’( 接收发送数据，其 主要思想是在发送移位寄存器和接收移位寄存器 的两端分别添加适当的辅助寄存器，并置以适当的 初值，在发送或接收过程中，通过辅助寄存器以及 移位寄存器各位的状态组合来判断发送或接受处 于哪个阶段。在设计中，我们感到这种方法需要精 巧的构思，控制信号复杂，调试不便，对于规模更大 的电路而言，其设计速度显然难以提高。 采用有限状态机方法，由于其状态及状态之间 的转换关系明确，设计过程直观简单，易于理解，设 计程序便于阅读存档，可以大大加快设计流程；但 是这种方法所消耗的器件资源可能会略多于传统 的设计方法，这可以通过优化程序组织使其降至最 低，因此在器件资源丰富的今天在多数场合下是一 种值得推荐的方法。此外，目前某些 F8& 工具，例 如 &-3;?1G685，可以直接支持状态图输入的方式， 并可转换成 H10;.>I 685或者 H685代码，这在一 定场合下还是很有效的。 " )*+ 有限状态自动机作为自动机理论的一个重要 组成部分，不仅是重要的软件基础理论，而且在硬 件设计中也发挥着重要的作用，特别是在利用 F8& 技术进行可编程 &JKL 设计时，如果使用得当，可以 提高设计效率，加快设计流程。 本文分析了 %&’( 的功能特点，并采用有限状 态自动机来设计其控制逻辑，实现了一个不可编程 的异步串行通讯接口，该接口可用于构成一个简化 的 ’J!M! 标准接口，或者可以作为一个模块嵌入到 其他电路中组成应用系统。在此基础上，我们可以 比较容易地将其扩展为一个可编程的串行接口，并 可进一步实现与 ;N31. E!C"接口芯片相兼容。 ,-./ O#P 陈意云Q 编译原理和技术R第二版SQ 中国科学技术大学出 版社T #UU$Q O!P 李亚民Q 计算机组成和系统结构Q 清华大学出版社T !"""Q OMP 陈崇昕Q 形式语言与自动机Q 北京邮电学院出版社T #UEEQ ODP 曾繁泰T 陈美金Q H685程序设计Q 清华大学出版社T !""#Q OCP 白中英Q 计算机组成原理Q科学出版社T #UU$Q OVP 周明德Q 微型计算机原理及应用R修订版SQ 清华大学出版 社T #UU$Q O$P 夏宇闻Q 复杂数字电路与系统的 H10;.>I 685 设计技术Q 北京航空航天大学出版社T #UUEQ 6%&WX 6*;Y.;NT J6FW A+Y)*NI RA;Z*N KN23;3+31 >9 [;-0>1.1-30>N;-2 (1-@N>.>I0< ;N @*0,]*01 ,1Y 2;IN *-->=:*N<;NI ];3@ * %&’( 17*=:.1Q &9310 *N*.<^;NI 3@1 9+N-3;>N *N, -@*0*-310;23;- >9 %&’(T ]1 ,1=>N230*31 3@1 %&’( ,12;IN +3;.;^;NI \J[ 3@1>0=:*0;NI ];3@ >3@10 ,12;IN =13@>,>.>I;12T 3@1 \J[G)*21, =13@>,>.>I< @1.:2 3> =*/1 3@1 ->N30>..;NI .>I;- =>01 ->=:01@1N2;?1 *N, 3@1 ,12;IN 9.>] 2@>03Y 10Q &N, ;3 ];.. :.*< * ;=:>03*N3 0>.1 ;N F8& 31-@N>.>I.>IN 黄海林 男，!"""年毕业于中南大学，现为西安微电子技术 研究所硕士研究生。研究方向为嵌入式计算机系统结构。 沈绪榜 男，研究员，中国科学院院士。主要从事计算机体系 结构、嵌入式计算机及其芯片的研究工作。 CC