5 - 3 同步时序逻辑电路设计

第五章同步时序逻辑电路数字系统逻辑设计DigitalSystemandLogicDesign主编：王维华、曲兆瑞山东大学出版社主讲人：李新山东大学计算机科学与技术学院计算机科学与技术学院22内容提要5.3同步时序逻辑电路设计概述5.1时序逻辑电路概述5.5状态化简5.4建立状态表5.2同步时序逻辑电路分析5.6状态分配和网络实现计算机科学与技术学院35.3同步时序逻辑电路设计概述同步时序逻辑电路设计(又称为同步时序逻辑电路综合)对给定功能要求，做出电路实现时序逻辑电路设计是时序逻辑电路分析的逆过程，设计过程更复杂设计步骤(4步)（1）建立状态表：确定状态及转换关系建立输入、输出以及状态之间的关系（2）状态化简：消除多余状态（3）状态分配：用二进制编码表示各状态（4）电路实现：由赋值状态表确定各触发器的激励函数和电路输出，做出电路图说明：有的设计可能不需要经过全部步骤，如计数器设计不需要化简、赋值，可以直接写出赋值状态表。下面分别介绍各部的具体做法。计算机科学与技术学院45.4建立状态表建立状态表就是对给定的设计要求，初步确定所需状态个数及其转换关系，写出描述给定功能要求的状态转换表。两种基本方法信号序列法信号序列是指作用于网络的输入信号序列和相应的网络输出信号序列信号序列法是先确定作用于网络的信号序列，再指定状态，作出状态转换表状态图法先根据设计要求作出状态转换图，再由状态转换图写出状态转换表。作状态转换图可以先设定一个初态，再根据所作用的输入信号和系统的功能要求逐步推导出相继状态及其转换关系，完成状态转换图。比较：状态图法中的各状态可以有特定的含义，比较容易理解和掌握以下通过例题，介绍用状态图法建立状态转换表的具体做法。计算机科学与技术学院55.4建立状态表状态图是用从状态引出的有向线段表示状态的转换关系，用标注在有向线段上的数码表示输入信号以及输出信号这种表示方法在输入信号较多时，从状态引出的线段就比较多，看起来不够清晰为此我们在建立状态表时采用图b所示的表示方法，即把作用于状态的全部输入信号以及相应的输出信号都列在状态右边的大括号中，括号右边引出的有向线段表示状态的转换关系。计算机科学与技术学院65.4建立状态表同步时序逻辑电路作用1：进行信号检测序列检测：序列的分组是任意的例如：对信号X＝101001100011进行序列检测，则可有多种分组，其中有两组“100”序列代码检测：代码的分组是固定的例如：对信号X＝101001100011进行代码检测，则只有101，001，100，011四个分组，其中有一组“100”代码代码检测器不仅要保存合乎要求的信号，还要“记住”代码的分组情况计算机科学与技术学院7例1建立“100”序列检测器的状态表例4.5-1建立“100”序列检测器的状态表。该检测器有一个串行输入信号X和一个输出信号Z(由CP脉冲划分节拍)。平时Z＝0，当输入信号X出现“100”序列时Z＝1。分析：序列监测器需要记住前两拍的输入信号，因此该网络是具有存储功能的时序逻辑网络yx/z0/0A(无1)0/1C(有10)1/0B(有1)1/00/01/0yxA/0ABC01y’/zC/0A/1B/0B/0B/0状态表状态图计算机科学与技术学院8例2建立“100”代码检测器的状态表例4.5-2建立“100”代码检测器的状态表。该检测器有一个串行输入端X和一个输出端Z(由CP脉冲划分节拍)，其功能是检测三位二进制代码是否是100。平时Z＝0，当检测到“100”代码时Z＝1。yx/z1/0A(等待首位)0/1D(有10)1/0B(有1)0/0E(有两位)1/0C(有一位)0/00/00/01/01/0yxC/0ABCDE01y’/zD/0E/0B/0E/0E/0A/1A/0A/0A/0状态表状态图计算机科学与技术学院9例3建立串行加法器的状态表例4.5-3建立串行加法器的状态表。串行加法器有两个串行信号输入端A,B和一个输出信号Z(由CP脉冲划分节拍)。A，B分别串行输入两个二进制数(先送低位)，Z串行输出两数相加的“和”yAB/Z00/001/110/111/0S1(加前无进位)S2(加前有进位)yABS1/0S1S200011110y’/ZS2/0S1/0S1/0S1/0S2/0S2/1S2/0(无进位)(有进位)00/101/010/011/1(无进位)(有进位)状态表状态图计算机科学与技术学院10例4串行比较器例4.5-4建立一个串行数据比较器的状态表。串行数据比较器的功能是比较两个串行二进制数的大小。比较器有三个输入端x3、x2、x1和两个输出端z2、z1(由CP脉冲划分节拍)。当x3＝0时，x2和x1分别串行输入两个二进制数(先送低位)；这时输出z2z1＝00。当x3＝1时，x2和x1分别输入两个二进制数的最高位；这时z2z1输出比较结果。即：若x2＜x1，则z2z1＝01；若x2＞x1，则z2z1＝10；若x2＝x1，则z2z1＝11；计算机科学与技术学院11例4串行比较器当x3＝0时，x2和x1分别串行输入两个二进制数(先送低位)；这时输出z2z1＝00。当x3＝1时，x2和x1分别输入两个二进制数的最高位；这时z2z1输出比较结果。即：若x2＜x1，则z2z1＝01；若x2＞x1，则z2z1＝10；若x2＝x1，则z2z1＝11；yABC000001011010110111101100状态表状态图x3x2x1z2z1A/00B/00A/00C/00A/10A/11A/01A/11B/00B/00B/00C/00A/10A/01A/01A/01C/00B/00C/00C/00A/10A/10A/01A/10计算机科学与技术学院1212内容提要5.3同步时序逻辑电路设计概述5.1时序逻辑电路概述5.5状态化简5.4建立状态表5.2同步时序逻辑电路分析5.6状态分配和网络实现计算机科学与技术学院135.5状态化简合并状态表中外特性相同的状态（消除多余状态)外特性相同的状态常称为“相容状态”外特性是指状态的输入/输出特性化简步骤（1）找相容状态对（可以合并的状态对）（2）找最大相容集合（可以合并的个数最多的状态）（3）找最小闭覆盖（构成简化表的必要最大相容）（4）作简化状态表计算机科学与技术学院145.5状态化简合并状态表中外特性相同的状态（消除多余状态)外特性相同的状态常称为“相容状态”外特性是指状态的输入/输出特性x现态01AA/0B/0BA/0C/0CA/0D/0DA/0E/1EA/0E/1x现态01AA/0B/0BA/0C/0CA/0D/0DA/0D/1计算机科学与技术学院155.5.1确定相容状态对（概念定理）1.概念定理（设yi和yj是状态表M中的状态）▲状态相容对状态表M的任意输入序列X(n)作用下，yi和yj产生的指定输出都相同,则定义yi和yj为状态相容。（对任意输入序列）▲状态不相容如果存在某个输入序列X(n)，使yi和yj产生的某个指定输出不相同,则定义yi和yj为状态不相容。（某个输入序列）▲输出相容对状态表M的全部指定输入，yi和yj产生的指定输出都相同,则定义yi和yj为输出相容。（全部一次输入）▲输出不相容如果在状态表M的某个指定输入作用下，yi和yj产生的指定输出不相同,则定义yi和yj为输出不相容。（某个一次输入）计算机科学与技术学院16定理5.1yi和yj状态不相容的充分必要条件是：yi和yj输出不相容或次态不相容。5.5.1确定相容状态对（概念定理）例zy/yx01ABCA/0B/0C/0B/0A/1B/0AC输出不相容，AB次态不相容。计算机科学与技术学院175.5.1确定相容状态对（隐含表法）2.找相容对的隐含表法对状态表中的所有状态对，按定理5.1找出所有的不相容对，其余即为相容对。在查找过程中，用隐含表记录对各状态对的相容情况。zy/yx01ABCDEC/0B/0D/0E/0E/0E/0A/1A/0A/0A/0▲隐含表是一种阶梯状的表格，其中每个方格对应一个状态对。如BCDEABCD隐含表B,C的相容状态对计算机科学与技术学院185.5.1确定相容状态对（隐含表法）▲确定相容对的隐含表法①填隐含表将各状态对的相容情况填入隐含表的相应方格中×不相容√相容次态对隐含②查次态对用“×”标出所有不相容次态对③确定相容对无“×”方格所对应的状态对即为相容对计算机科学与技术学院195.5.1确定相容状态对P151例5.5-1确定图示状态表的相容状态对1.填隐含表(按列填表)2.查次态对zy/yx123456I1I2I33/0*2/**4/06/*5/1**/0*1/11/*1/**6/*4/*5/*6/*23456123453.定相容对对原始状态表进行顺序比较，1)输出不相同，打×，表示不等效2)输出完全相同，且（次态相同或呈交错），打√，表示状态等效3)输出完全相同，但次态不相同且非交错，将相容状态对填入隐含表以待进一步比较原始状态表隐含表无“×”方格所对应的状态对就是相容对2,6×√1,21,32,63,42,6×√4,5√1,54,51,61,51,61,4×××(1,3),(1,5),(2,4),(3,5),(4,6)不完全指定状态表是指含有任意项的状态表，其中任意项可以是次态或输出。计算机科学与技术学院205.5.2确定最大相容集合相容状态集合设Q={y1,y2,...,yk}是状态表M的一个状态集合，如果对于每一个状态对(yi,yj)∈Q，都有yiyj相容，则称Q为相容状态集合。用关系图法确定最大相容集合：1)用分布在圆周上的点表示各状态；2)用直线连接各相容状态对；3)找出各“最大完备多边形”，每个最大完整多边形对应一个最大相容集合。（完备多边形是指各顶点之间均有连线的广义多边形）最大相容集合设Q是状态表M的一个相容状态集合，如果不存在一个状态yp∈M，但yp∈Q，而yp与Q中的每个状态都相容，则称Q是最大相容集合，简称最大相容。最大相容就是状态个数最多并且相互相容的状态集合。计算机科学与技术学院215.5.3确定最大相容集合P153例5.5-2确定下列隐含表的最大相容2345612345步骤：关系图隐含表2,6×√1,21,32,63,42,6×√4,5√1,54,51,61,51,61,4×××1234561)用分布在圆周上的点表示各状态；2)用直线连接各相容状态对；3)找出各“最大完备多边形”123456{1,2,6}123456{1,4}123456{2,3,6}123456{2,5,6}123456{3,4}123456{4,5}计算机科学与技术学院225.5.2确定简化状态表从最大相容中找出构成简化状态表的必要最大相容，即最小闭覆盖。简化状态表如果M’是状态表M的简化状态表，则M’应满足：(a)覆盖性：∨对yi∈M，至少存在一个Cj∈M’，使M’覆盖了M的全部状态，我们就称M’满足覆盖性；(b)闭合性：∨对yi∈M，至少存在一个Cj∈M’，使Ci的次态∈Cj，即M’中状态的次态仍是M’的状态，我们就称M’满足闭合性；(c)状态个数最少。1.完全指定状态表的化简没有任意项的状态表，即状态表中次态和输出是完全指定的，没有任意项。2.不完全指定状态表的化简不完全指定状态表是指含有任意项的状态表，其中任意项可以是次态或输出。计算机科学与技术学院235.5.2.1完全指定状态表的化简定理5.2设M是完全指定状态表，yi,yj,yk∈M。如果yi和yk相容,yj和yk相容，则yi和yk相容。即对于完全指定状态表，状态相容具有传递性。定理5.3对于完全指定状态表，全部最大相容满足最小闭覆盖。即对于构成完全指定状态表的简化状态表，所有的最大相容都是必要的，所以找出最大相容后，就可以作简化状态表了。计算机科学与技术学院24完全指定状态表的化简举例P154例5.5-3简化下图所示的状态表状态表关系图和最大相容简化状态表最终的简化状态表步骤1:根据状态表确定隐含表,找相容状态对步骤3:找最小闭覆盖步骤