有限状态机的UART设计

微电子学与计算机!""!年第#!期!!"随着$%&’技术的发展和电路复杂性的迅速提高，数字系统的设计方法发生了很大的变化，()*技术得到了飞速的发展；目前，基于()*技术的芯片设计正在成为数字系统设计的主流。其中利用硬件描述语言进行可编程*&’+设计是()*技术的一个重要应用，$,)%和$-./012,)%作为’(((标准硬件描述语言和一个工业标准，逐渐受到了广大硬件设计者的欢迎并取得了广泛的应用。硬件描述语言采用了自顶向下的设计方法，在更抽象的层次上把握并描述了系统的功能特性及电路结构，并具有制定电路规则时间短、易于修改、不受工艺限制等特点。随着电路规模和复杂度的增加，硬件描述语言愈显其优越性。本文结合3*45637/8-.9:0*9;7<=.171>94-?<-/8-.@5.:79A/BB-.C的设计，探讨了利用,)%设计可编程*&’+的方法，通过分析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:CH-:0;型状态机6QCH11.-型状态机图#H-:0;机和H11.-机模型示意图输入现态次态输出次态逻辑状态寄存器输出逻辑现态输入现态次态输出次态逻辑状态寄存器输出逻辑现态#./0123)4+($%&’%&56#(!$%&’789:;<=,通用异步接受发送器3*45是目前广泛使用的一种通用串行数据接口，其应用范围遍及计算机外设、工业控制等场合。3*45的作用是，它既可以./0123+($%&’%&M&HRS:9-T)-9/27H-B=1T1012;U1.3*45西安微电子技术研究所>?@ABC6西安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，如图-所示。其中，发送器模块和接收器模块是本$%&’设计的主要组成部分，也是我们讨论的重点。图-$%&’设计的模块划分示意图$%&’’B8AGHICC@B发送保持寄存器发送移位寄存器发送控制逻辑接收控制逻辑接收保持寄存器接收移位寄存器$%&’&@;@IF@B789:;<=波特时钟产生器48C8’64JBIC@’>@HKCL0MMLG>0<=&@G@C&@8:&>N9<<58BICL>@BB2F@BN<DO>@BBPBDH@>@BBQ64发送器部分由发送移位寄存器CGB、发送保持寄存器(缓冲器)CRB以及发送控制逻辑组成；接收器部分由接收移位寄存器BGB、接收保持寄存器(缓冲器)BRB以及接收控制逻辑组成，二者的接口定义如表#所示。下面我们将就发送器模块和接收器模块的设计进行讨论，对于波特时钟发生器模块，由于设计相对简单，限于篇幅，这里我们不作讨论。表#$%&’的模块接口定义ST2方向功能描述公共信号MLG>0<=S输入$%&’的外部系统时钟U89:;<=S$%&’工作的时钟信号，频率为波特率的#/倍&@G@C>1S系统复位信号0G>1S片选信号48C8ST2双向并行数据总线发送模块信号’642串行发送数据线JBIC@>1S并行数据写信号，低电平有效’>@HKCL2发送缓冲器为空，可以接收下一个要发送的并行数据接收模块信号&64S串行接收数据线&@8:>QS接收的并行数据读信号，高电平有效&>N9<<2接收缓冲器满，主机可以取数据58BICL>@BB2接收数据时发生奇偶校验错误2F@BVN<DO>@BB2下一数据已接收完，而上一数据尚未取走，溢出错误PB8H@>@BB2接收数据时停止位不为"，发生帧错误!"!./%&0!"发送器模块的设计主要集中在其控制逻辑的设计上，我们采用有限状态自动机来作为它的控制*-万方数据微电子学与计算机!""!年第#!期器，在设计中，我们共定义了六个发送器工作状态：$%&’()、$%*+,-+、$%.,&+、$%*/&0+、$%1,-&+2以及$%*+31，该自动机的状态转换图如图4所示。为了简化图示，在这里我们没有将状态机的输出在图中表示出来，实际上，该状态机的输出都在给定的状态中进行，根据米兰机和摩尔机的定义，我们可知该状态机属于摩尔机的范畴，下一节将讨论的接收模块控制逻辑亦属于摩尔机的范畴。对于这六个状态，我们采用了独热码56789:6$;6<8=的编码方式，这种编码方式虽然较二进制码5>?7@AB9;6<8=编码方式或格雷码5CA@B9;6<8=编码方式多用了三个触发器，但却可以省下许多组合电路，综合后的电路更加简单，可使电路的速度和可靠性得到显著提高，而总的单元数增加不多，这在触发器资源丰富的01D,器件中是一种行之有效的方法。图4E,-+发送器的状态转移图A8F8$G(HH"$G8IJ$BHH"$%1,-&+2K"#""""K$%*+31K#"""""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#PARG;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。图QE,-+发送器的后仿真波形图>@N<;LMA8F8$%(TA?$8%(;F%(<@$@+R’$%8IJ$BF$@$8F:?U$$FA’Q"!"4"4"4"4"4"4"4"4#"!""#""’QP,VQ#,"’"P"V"#""!"#!"#$%&’接收器模块的设计要相对复杂一些，因为它需要正确判断接收时刻以及进行一些错误检测。对于接收器模块，其控制逻辑仍然采用有限状态自动机来设计，我们共定义了P个状态，仍采用独热码编码方式，控制状态转移的波特时钟计数器共七位，其中高三位计数位表示了接收的二进制数据位数。该状态机的状态转换图如图P所示。图PE,-+接收器的状态转移图A8F8$G(HH"A%1,-&+2K"#""""KA%*+31K#"""""KA%*,W1()K""#"""KA%.,&+K"""#""KA%*+,-+K""""#"KA%&’()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#PARG;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万方数据!""!年第#!期微电子学与计算机假定接收的数据帧是"#"#"#"##"#，并将某些重要的中间信号也输出进行观察，见图$。图$%&’(接收器的后仿真波形图)*+,-./012134501*,46-245’78,*3*049+..:*0;3<4⋯90*=14⋯>?109.>⋯0423*312@;93020AABB8C"#"!"D"D"D"D"D"D"D"D#"!""#""E"D"&"C"&ECD&&8C!!"#$%&’(我们还采用了另外一种方法来设计%&’(，这种方法不用状态机来控制%&’(接收发送数据，其主要思想是在发送移位寄存器和接收移位寄存器的两端分别添加适当的辅助寄存器，并置以适当的初值，在发送或接收过程中，通过辅助寄存器以及移位寄存器各位的状态组合来判断发送或接受处于哪个阶段。在设计中，我们感到这种方法需要精巧的构思，控制信号复杂，调试不便，对于规模更大的电路而言，其设计速度显然难以提高。采用有限状态机方法，由于其状态及状态之间的转换关系明确，设计过程直观简单，易于理解，设计程序便于阅读存档，可以大大加快设计流程；但是这种方法所消耗的器件资源可能会略多于传统的设计方法，这可以通过优化程序组织使其降至最低，因此在器件资源丰富的今天在多数场合下是一种值得推荐的方法。此外，目前某些F8&工具，例如&-3;?1G685，可以直接支持状态图输入的方式，并可转换成H10;.>I685或者H685代码，这在一定场合下还是很有效的。")*+有限状态自动机作为自动机理论的一个重要组成部分，不仅是重要的软件基础理论，而且在硬件设计中也发挥着重要的作用，特别是在利用F8&技术进行可编程&JKL设计时，如果使用得当，可以提高设计效率，加快设计流程。本文分析了%&’(的功能特点，并采用有限状态自动机来设计其控制逻辑，实现了一个不可编程的异步串行通讯接口，该接口可用于构成一个简化的’J!M!标准接口，或者可以作为一个模块嵌入到其他电路中组成应用系统。在此基础上，我们可以比较容易地将其扩展为一个可编程的串行接口，并可进一步实现与;N31.E!C"接口芯片相兼容。,-./O#P陈意云Q编译原理和技术R第二版SQ中国科学技术大学出版社T#UU$QO!P李亚民Q计算机组成和系统结构Q清华大学出版社T!"""QOMP陈崇昕Q形式语言与自动机Q北京邮电学院出版社T#UEEQODP曾繁泰T陈美金QH685程序设计Q清华大学出版社T!""#QOCP白中英Q计算机组成原理Q科学出版社T#UU$QOVP周明德Q微型计算机原理及应用R修订版SQ清华大学出版社T#UU$QO$P夏宇闻Q复杂数字电路与系统的H10;.>I685设计技术Q北京航空航天大学出版社T#UUEQ6%&WX6*;Y.;NTJ6FWA+Y)*NIRA;Z*NKN23;3+31>9[;-0>1.1-30>N;-2(1-@N>.>I<TA;Z*N$#""CDS#$%&’()&*(@;2:*:10,;2-+22123@1\J[3@1>0<;N@*0,]*01,1Y2;IN*-->=:*N<;NI];3@*%&’(17*=:.1Q&9310*N*.<^;NI3@19+N-3;>N*N,-@*0*-310;23;->9%&’(T]1,1=>N230*313@1%&’(,12;IN+3;.;^;NI\J[3@1>0<QL>=:*0;NI];3@>3@10,12;IN=13@>,>.>I;12T3@1\J[G)*21,=13@>,>.>I<@1.:23>=*/13@1->N30>..;NI.>I;-=>01->=:01@1N2;?1*N,3@1,12;IN9.>]2@>03Y10Q&N,;3];..:.*<*;=:>03*N30>.1;NF8&31-@N>.>I<Q+,-./’0%*%&’(T\J[TF8&31-@N>.>I<T685,12-0;:3;>N黄海林男，!"""年毕业于中南大学，现为西安微电子技术研究所硕士研究生。研究方向为嵌入式计算机系统结构。沈绪榜男，研究员，中国科学院院士。主要从事计算机体系结构、嵌入式计算机及其芯片的研究工作。CC万方数据