数逻复习笔记

Komorebi_shine · 2024-10-12 09:37:52 · 科技·工程

《数字逻辑与处理基础》课程复习笔记（24秋学期）

绪论 Class1

处理实际问题的步骤：建模与计算

建模：确定输入、输出与映射f三部分
计算：使用合适的设备（电路），实现映射f

数字电路的优点

抵抗噪声，稳定性好，可靠性高

基于数字电路“宽进严出”特性，低于容限的噪声不影响。
两种状态，更稳定，易于传输、存储、判别、校验
分层清晰，设计自动化，可借助二值逻辑计算，可以设计复用
功耗低，成本低
适合尺寸缩减

数字电路分层：器件、电路、逻辑、模块、系统

促进了电路复用、迁移，减少工作量，为EDA工具创造了条件。

处理器的目标：利用有限元件，在约束条件下实现特定功能并满足指标需求。

指标：能耗、频率（延时）、工艺（制造成本）、设计成本（能力）、可靠性、环境等

处理器的基本思想:

数字化：数据与过程离散化，采样、量化、编码。
同步化：遵循一定时序，避免电路闲置，实现效率提升。
结构化：小模块组成大功能。

两种设计处理方法的思路：

思路	硬件类型	实现不同功能的方式	优点	不足
定制硬件思路	专用芯片	改变电路结构	高性能	无扩展性，设计成本高
通用硬件思路	通用处理器	改变指令	扩展性好，易操作	性能低，效率低

摩尔定律

集成电路最小元器件复杂性（数量）每年翻倍。
更多表述：每18个月，集成电路器件数量翻倍；每18个月，处理器性能翻倍，价格减半。
特征尺寸微缩的好处：面积减少，能耗降低，效率增高，成本降低

摩尔定律受到限制：

功率密度过大，温度升高，影响稳定性——多核协作
量子效应（隧穿），半导体器件失效
工艺限制，成本增大，对设备要求高

处理器的发展历程

两状态量
计算理论（图灵）
计算机架构（冯诺依曼）
晶体管、集成电路的推广
各种现代处理器

单核频率提升多核协作功能专门化

课程目标：

熟悉数字电路与处理器的基本原理及评价指标；
掌握基础数字电路和处理器的分析和设计方法；
理解数字系统的设计思想，具备数字系统设计开发的初步能力。

布尔代数 Class 2

二进制编码

二进制编码优势

符合自然现象
易于电路实现（CMOS）
运算容易
传输可靠

二进制数的表示

第i位的权值为2^{(i-1)}；

MSB：最高的有效位；LSB：最低的有效位。

浮点数：单精度、双精度、一般格式、特殊情况

有符号数的最高位为符号位，0表示正，1表示负，n位有符号数的表示范围from -2^{(n-1)} to 2^{(n-1)}-1。

补码用于解决正数、负数0重复的问题。

对正数而言，原码、反码（即1-补码）、2-补码均为原形式；
对负数而言，反码为对原码各位取反（符号位固定为1），2-补码为反码+1的结果。
也就是说，负数的补码，符号位后面数越大，负数越大（绝对值越小），如2-补码11111111表示-1，2-补码10000000表示-128
由此可得，正数最大数和负数最小数在补码意义上是首尾相连的，正数最大数+1=负数最小数；从一个数开始连续+1，最终能回到这个数

二进制运算

加（或运算）,加法进位（与运算）
减

借助补码的减法原理：n位补码A的字面数值（符号位当数值位）为2^n-A。

方法：对a-b，求出-b的补码，a的原码加上b的补码即为结果
加减法运算的溢出问题

溢出：计算结果超出了二进制数表示限度（n位有符号二进制数）

对符号位溢出两次，可以相互抵消；对符号位溢出1次，会导致计算结果出错（溢出）

判断方法：
(符号位进位 \oplus 最高运算位进位)
其中符号位进位指参与运算两个数都是负数（符号位为1）
乘（与运算）
位移（左移末位后补0，乘2；右移删除末位，除2下取整）

其它编码

BCD码

8421BCD码方法：十制按每一进位对应4位二进制数，再拼接

会造成数的浪费

格雷码

特点：相邻两位有且仅有一个数位不同

优点：减少出错（相邻数间变化时只有一个二进制位变化）

逻辑运算

运算	非	与	或	异或
运算规则	1变0，0变1	有0就为0，全1才为1(与非：有0就为1，全1才为0)	有1就为1，全0才为0(或非：有1就为0，全0才为1)	相同为1，不同为0（同或：相同为0，不同为1）
优先级	高	中	低	低
表达式	\bar A	A+B	A\cdot B	A \oplus B
电路元件图	三角+右侧小圆	左侧弯+半圆	左侧直+半圆	左侧双弯线+半圆

元件图形规则：

三角表示单变量传递，半圆表示多变量运算；
右侧小圆表示取反
左侧弯线表示或系列，直线表示与系列
左侧两条弯线表示异或系列

运算定律（重要）

运算律	表达式
交换律	A+B=B+A;AB=BA
结合律	A+(B+C)=(A+B)+C;A(BC)=(AB)C
分配律（乘法与加法)	A(B+C)=AB+AC,(AB)+C=AC+BC
0和1	A+0=A;A+1=1;A\cdot 0=0;A\cdot 1=A
幂等与互补	A+A=A;A+\bar A=1;A\cdot A=A;A\cdot\bar A=0
对合律	\overline {\overline A}=A
德摩根律	\overline{A+B}=\bar A\cdot \bar B;\overline{A\cdot B}=\bar A+ \bar B
一些其他的定理	X+XY=X;X(X+Y)=X;(X+Y)(Y+Z)(\bar X+Z)=(X+Y)(\bar X+Z);XY+YZ+\bar XZ=XY+\bar XZ

证明逻辑式的常用方法：

列真值表
利用已有逻辑式推导

德摩根律的应用

非或=与非，非与=或非
电路化简
表达式取反运算：所有变量取反，与、或互换，0、1互换
POS与SOP的转换：两次取反，对内层应用德摩根律展开，再取未出现的项

只能使用特定逻辑运算的表达式转换

核心：德摩根律

例：只能用与非

与：与非+非
或：非或=与非，所有运算量取反，或运算改与非
非：（不能单独用非时）和1做与非运算

例：只能用或非

与：非与=或非，所有运算量取反，与运算改或非
或：或非+非
非：（不能单独用非时）和0做或非运算

布尔函数

表达方式：真值表；逻辑函数

两级逻辑

最小项：每个变量都出现一次，所有变量或取反全部做与运算后的积式，用小写字母表示。只有一种变量组合能让一个最小项取值为1

（最大项：每个变量都出现一次，所有变量或取反全部做或运算的和式，用大写字母表示。只有一种变量组合能让一个最大项取值为0）

编号：二进制顺序编号，0~2^n-1

与或表达式SOP：一些最小项的和；或与表达式POS：一些最大项的积

无关项：实际问题中不会出现或取值无关紧要的项，用d（或D）表示，写作-

SOP与POS转换：两次取反。结论：无关项编号照抄，去除无关项后最小项与最大项编号互补（未出现的都出现）

函数化简：卡诺图

变量取值写在横、纵表头，可以是两个逻辑变量的结合，按格雷码顺序排开取值（相邻的项只有一个逻辑变量取值不同）。靠前的变量放竖排，靠后的变量放横排。
把逻辑式写成POS形式，如果有项未包含所有元素，则补乘该元素与取反的和(A+\bar A)，再展开括号
对应最小项（最大项）取值写在表中对应格，如对POS，存在该最小项填1，不存在该最小项填0，无关项填-
化简：尽量合并相邻的格子，每个格子取值均为1且边长均为2的幂次的矩形可以合并，取矩形可以跨越表格边界（首尾相接性）。 例如，4*4表格4个角落可以合并成2*2矩形
无关项可以视合并最简化而任意取值。
合并的矩形为蕴含项，不能再扩大的矩形为本原蕴含项，包含了“独一无二”的格子（即该格不在其他本原蕴含项内）的本原蕴含项为本质本原蕴含项。
取出蕴含项，规则：取出所有本质本原蕴含项，再选取包含了还未被覆盖格子的本原蕴含项。要求：单个本原蕴含项尽量大，取的本原蕴含项尽量少。

要求延时、面积最小类问题

一般与非、或非的延时、面积均较小，优先使用这两个运算，再和非运算组合，寻找最优方案。

组合逻辑 Class 3

逻辑门的电路实现

传输门：控制输入信号是否向输出端传递。

NMOS和PMOS并联，G端信号相反，S端连输入——

输出	G高	G低
输入高	通过NMOS传输，输出高	不传输，输出隔离
输入低	通过PMOS传输，输出低	不传输，输出隔离

优点：避免了单个MOS管控制传输带来的VTH压降，且使得1和0都可以传输。

G端信号称为使能EN。逻辑门也可以添加使能，使能为1时正常工作，使能为0时隔断。有时同时将EN与EN'加在同一个门上下，工作机制与单个EN控制相同。

隔离态：与输入无关，实际的状态由后电路决定，代表一种不工作的状态。

传输门逻辑电路正常工作的要求：

输出无冲突隐患（如A和A'同时通到输出端）
输出无悬浮可能（如各支路都低使能隔断）

因此，通常将两支路的传输门首尾串联，EN1'与EN2连接，确保必是一通一断。

组合逻辑

输出是当前输入函数，与其它时间的输入无关（不存在状态、反馈等）

组合逻辑的功能分析

给定电路
将电路的逻辑门改写成逻辑运算，得到表达式
通过枚举输入逻辑变量的取值，得到真值表
通过真值表找规律

组合逻辑的设计实现

定义问题的输入、输出。一种输出的简单形式为：为所有可能的结果状态定义一个输出量，为该状态时该输出量为1，其他量为0。同一时刻，输出量为1的个数必定为1。
枚举输入，获得真值表
根据真值表作出卡诺图，进行化简，列出逻辑表达式
将逻辑运算改写成逻辑门，画出电路

对复杂逻辑，可以选定一些表达式为共用的变量（共享项），由此组成层级更高的表达式，可节省逻辑门。

组合逻辑的评价指标

逻辑电平

数字逻辑电路确定状态的方式：设定电压阈值，高于高阈值的为1，低于低阈值的为0，中间的为禁带（无对应状态，不稳定），应当避免。

经过多个逻辑电路后，同一个信号可能会发生强度偏移（向中间偏移），进入禁带或另一状态范围（如高电平电压不断下降）

0和1对应电压范围越宽（高阈值低，低阈值高），抗干扰能力越强。

噪声容限

不同元件电压阈值不同，如果后一个元件阈值比前一个元件更靠中间（允许的电压范围更大），电路就更稳定（不易误判）。

因此，需要尽量增大电路的噪声容限：高阈值差或低阈值差。

转换时间

电路状态变化需要时间：0到1的上升时间tr和1到0的下降时间tf。

一般定义为电压在10%Vm与90%Vm之间转换的时间。

延时

输入变化引发输出变化过程的时间。分为输入0到1和输入1到0的延时，实际计算时可以用二者均值或最值。

扇入扇出系数

一个门前面/后面连接的模块数

扇入系数增大，等效电容增大，延时增大

扇出系数增大，驱动输出状态改变更困难，等效电容增大，延时增大

功耗、能量

平均功耗（最终将电容等元件排除）和瞬时功耗

CMOS电路功耗来源

静态功耗：漏电流|{亚阈值漏电、栅极漏电、D/S衬底漏电}

可以通过减小VTH或VDD降低静态功耗

动态功耗：开关电流、短路电流|{电容充放电、上拉电路和下拉电路同时导通}

电容多次充放电（MOS状态多次改变）会增大动态功耗，降低电压电压、减小电容、减小频率可以降低动态功耗。

功耗延时积：两种因素权衡的结果

组合逻辑实例

一般的编码方式：二进制顺序编码0~2^n-1

编码器

![3-1](https://cdn.luogu.com.cn/upload/image_hosting/0y5kbg2h.png) 更进一步：优先编码器，根据要求设计逻辑门（如，高位优先匹配状态） #### 译码器用m位二进制编码给出实际状态的电路（最小项形式） ![3-2](https://cdn.luogu.com.cn/upload/image_hosting/m8k3mcxo.png) 可以通过级联增加译码器可处理的二进制位数译码器可以用来实现简单逻辑函数，输出相当于所有可能状态的取值情况，将成立状态对应的输出位用逻辑电路连接即可。译码器是通过读取较少的输入，确定较多输出，输出是一系列状态（0或1），大量输出位构成一个完整的输出。 #### 多路选择器给出输入列表($2^n-1$个)，用顺序二进制编号，再给出选择参数(n位)，由选择参数将对应编号输入送到唯一输出端。多路选择器是通过读取较少的输入（参数），从大量已有的列表（输入）中选择一个提供唯一的输出。电路实现：选择参数二进制位匹配（最小项）与相对的输入取交，再求和。 ![3-3](https://cdn.luogu.com.cn/upload/image_hosting/tgcugxfu.png) 多路选择器的用途： **移位器**：每一位多路选择器的两种输入都分别与本位和上/下t位的值相连，统一的选择信号S控制选择器全部取本位或上/下t位，实现不移位或统一右/左移t位。缺少可连接上/下位输入来源的选择器，输入根据移位要求取0或1（对于有符号补码二进制数，可以让它们全部指向符号位）。 **实现逻辑函数**：将逻辑变量压缩成二进制选择参数，遍历变量的每一种取值预处理出可能的运算结果，根据变量取值放进对应的输出位（如f(0,1,0)结果放进输入D2）。运行的时候，根据给出的逻辑变量取值直接取出对应结果即可。处理选择器选择参数位数不足：将一些变量放在输入端，用逻辑门组成输入，如设置D3=变量E，用A,B,C变量选择输入列表中带E的表达式或不含E的二进制值）。由此可以讨论选择参与运算最多的变量作为选择参数，使输入端的逻辑电路尽量简单。 #### 加法器 ##### 半加器根据一位二进制加法的真值表，用异或门实现半加器（不进位）。 ##### 全加器考虑低位进位和本位进位，三变量，两输出本位结果：两加数、低位进位分别加，相当于两次异或本位进位：两加数、低位进位有至少两个1才会进位，两两求与再相加 ##### 多位加法器全加器级联，依次传递进位，可得行波进位加法器，为线性效率分析：限制效率的因素是，前一级的进位参与后一级的运算，需要等前一级计算完成才提供思路：计算与进位分离，前一级进位不再依赖前一级计算方法：预处理出后面位的进位（因后面位进位只与前面位进位和加数有关，加数已给出），所有位加法可以同时完成。此时电路的效率取决于计算进位的速度，由于将前位计算进位的逻辑式直接带进后位，逻辑运算复杂度与位数正相关——不可能预处理大量数位的进位继续拆分运算：将进位拆分成两类{进位传播PiCi，进位生成Gi}，分别代表由前位进位导致的进位和完全因本位加数导致的进位逻辑运算简化：$P_i=A_i \oplus B_i, G_i=A_iB_i, C_{i+1}=P_iC_i+G_i

Pi与Gi只与本位加数有关，可同时预处理产生；Ci是递推关系，效率为线性；Si由Ci产生，用时比Ci多1

一般将4位打包成一个单位，接受最低位进位，给出最高位进位，成为一个效率更高的4位加法器；将4位加法器继续级联，可以得到更多位的并行加法器；再次对4位加法器提取Pi与Gi预处理，可构造组内并行、组间并行进位加法器。

时序逻辑 Class 4&5

时序逻辑需求：之前输入，分部完成任务，提升性能

时钟clock

引入时钟：周期性的升降信号

可以用环形振荡器实现：奇数个反相器首尾相接，各反相器组成状态，共10种状态，周期为2nt_n（n为反相器数量）；也可以用物理元件激发周期信号，作为时钟

利用时钟：在边缘（变化时）采样，上升沿（触发器）、下降沿（锁存器）

时钟变化引发输出变化存在延时，称为\color{red}t_{cq}

时钟域：同一个时钟信号统一的电路范围。电路中各部分的时钟信号一般需要同步。

状态state 与有限状态机

必要信息的集合（类似算法），能描述系统工作的所有可能情况。

有限状态机：总状态和输入、输出数量有限

有限状态机有6大描述因素：初态、状态，输入、输出、状态转移函数、输出函数

摩尔机与米利机

摩尔机：输出由状态决定

米利机：输出由输入、状态决定

两种状态机在效率上并没有差别。

状态机的描述

状态转换表：将状态写在竖表头，输入写在横表头，表中填入输出和新的状态（摩尔机的输出不用区分不同的输入）

状态图（圆圈图）：将状态、输出、输入做成图，输入作为边，状态作为节点，摩尔机的输出放入节点，米利机的输出放在边上（与输入有关）

状态转移图用圆圈以及圆圈中的符号表示不同状态；用箭头以及箭头边上的输入符号表示状态转移的方式。

Moore：将输出和状态一起标在圈内；

Mealy：将输出标在状态转移的箭头上

锁存器

保持输入的状态不变的电路

双稳态单元：两个非门首尾相接，两门两个输出Q,\bar Q

原理：两次取反，稳定状态；偏离阈值电压后正反馈逼近0或1状态。

添加输入：双刀双掷开关，输入/锁存两状态；改进——输入端添加与非门，两门两个输入R,S与内部锁存取或。

SR锁存器的状态表：

Q	Q'	状态
S=0,R=0	之前Q	之前Q'	保持
S=1,R=0	1	0	置位
S=0,R=1	0	1	复位
S=1,R=1	不稳定	不稳定	不稳定

R称为复位端(R=1则设置Q=0），S称为置位端（S=1则设置Q=1）

S=1，R=1时，进一步改变输入会导致锁存状态不稳，需要避免，因此有规定SR=0。

引入使能C：输入最前面对使能求与非，使能为1才工作，使能为0即保持。

D锁存器：把取反的R与S归为一个信号（保持态由使能C控制）

C=1：Q=D通路

C=0：Q保持，Q与D断开

C=0时，Q的状态为C下降沿时刻的D状态（下降沿锁定）

D锁存器的另一种结构

中间为相反的传输门，时钟控制

时钟高：下方导通，D通到输出Q端，同时通过反馈回路，等候在上传输门的输入端（经历若干非门）

时钟低：下方隔断，上方导通，之前的Q从反馈回路输出，同时自我保持（经历若干非门）。下方的输入D对状态没有影响

锁存器的时间分析

最小脉冲宽度\color{green}t_w(min):得到结果所需要的最短的高信号时长

延迟：分高到低、低到高延迟，从输入到输出的时间

建立时间\color{blue}t_{su}：开始锁存前输入的必需最小保持时间（稳定后才可以读入）

D锁存器的建立时间：下传输门+右非门+左非门

保持时间\color{brown}t_{h}：开始锁存后输入的必需最小保持时间（读入过程需要保持稳定）

D锁存器的保持时间：左下非门（减时钟延迟）

少于这两个时间会导致输出混乱，被称为亚稳态

导致亚稳态的因素：时钟偏差与时钟域不同等

减少亚稳态的影响：同步器、异步FIFO

触发器

边沿触发：上升沿或下降沿触发，周围输入状态稳定

DFF

符号相比D锁存器，增加一个带三角的C时钟输入。

C上升沿时将输入D传递给Q，C为0或1时Q均不变

DFF的原理：

左侧为主锁存器，右侧为从锁存器，输入的时钟信号相反

时钟低：从锁存器读取上一个状态并保持；输入信号通过主锁存器下传输门，进入从锁存器并被阻隔；输出为从锁存器保持的状态

时钟高：输入信号断，主锁存器信号保持，并且传递给丛锁存器输出，输出为主锁存器保持的状态

两种状态的输出均为保持的状态，与输入不直接关联；时钟上升沿，主锁存器保持状态向从锁存器传递

两条限制分别对应上粗体与斜体

DFF的时间分析

建立时间\color{blue}t_{su}：时钟0到1前，输入D稳定在T2输入端准备保持的时间

DFF的建立时间：左边电路下传输门+右非门+左非门

保持时间\color{brown}t_h：T1断前输入D需保持稳定状态的时间（保持时间可以为负——时钟传递比输入D快）

DFF的保持时间：左边电路左下非门-时钟非门=0

输出响应时间\color{orange}t_{c-q}：时钟上升时信号从T3输入端传递到输出的时间

DFF的输出响应时间：右边电路下传输门+右非门

#### DFF的时序组织周期过慢：效率降低输入D的准备太慢周期过快：信号冲突输入D的建立保持时间不满足有反馈环路时间$\color{yellow}t_d=\color{orange}t_{c-q}+\color{purple}t_{logic}$输出响应时间与组合逻辑时间之和最小的周期还要加上建立时间$\color{pink}t_{cycle}=\color{yellow}t_d+\color{blue}t_{su}=\color{purple}t_{logic}+\color{orange}t_{c-q}+\color{blue}t_{su}

对组合逻辑时间\color{purple}t_{logic}提出了上限要求

反馈环路时间还需要大于电路要求的最小保持时间\color{yellow}t_d>\color{brown}t_h

对组合逻辑时间\color{purple}t_{logic}提出了下限要求

触发器的描述

特征方程：输出Q与D、输入Q的关系式

真值表、状态图

激励表：Q到新Q+的转移与输入状态D对应（追溯）

时序逻辑的分析

功能分析

求取逻辑式：

激励方程e=g(x,s)——组合逻辑输出至触发器输入
状态转移方程s+=h(s,e)/次态方程——触发器Q到Q+（DFF触发器：Q+=g(x,s)，状态转移直接采用激励）
组合逻辑f(x,s)

行为分析：状态转移表、状态图、时序图

根据电路，从输出端对应写出输出方程，从各触发器的输入端写出激励方程，对DFF，激励方程即为状态转移方程

再通过状态转移表表现各触发器状态与更新状态、输出的关系（可能需要输入作为第二维度）；可以用字母作为状态标识，避免反复书写逻辑01状态。

讨论：米利机与摩尔机

米利机的输出与状态转移相互分离（需要输入作为参量）

将米利机快速转换为摩尔机：输入或输出端加DFF限制，强制同步输出

性能分析

强调：周期必须大于输出响应时间、组合逻辑、建立时间之和；输出响应时间与组合逻辑的时间和必须大于保持时间

时序逻辑的设计

设计状态

可以描述系统工作的状态有很多种，需要选择在实现（传递与调用）上简单的状态。

尽量减少状态种数，可以将地位相同（来源、去路、输出相同）的状态合并

化简状态

等价状态：输出相等，次态等价（可以不相等，如互为次态）

不等价状态：存在输入让两个状态区分

行匹配：把状态转移表中次态和输出相同的行合并为新状态（观察法）

蕴含表：解决诸如互为次态的状态合并

将变量写作交错的二维表形式，表中填写两种状态的等价情况

等价打钩，不可能等价打叉，剩下可能等价的填入等价条件

最后依照已有的等价情况检验等价条件。

状态分配

用逻辑变量的01组合表示各种状态

独热编码：逻辑变量与状态数量相同，一一对应，状态对应的逻辑变量取1，其余取0

紧凑的编码方式顺序编码；状态从0开始编号，转换成二进制作为状态的表示

基于次态和输入/输出的准则一般能得到较优的状态表示（易化简，电路实现简单）

三条优先级依次降低的规则

在某一输入下，次态相同的状态相邻编码
同一状态的不同次态相邻编码
输出相同状态相邻编码

注：

对规则1，不同的输入分别判断，若两状态有多种输入对应的次态相同，该规则满足次数以相同次态的输入个数重复计数

对规则2，若有多个状态的次态相同，该规则满足次数按次态相同的状态数重复计数

确定方程

根据化简后状态表作卡诺图，确定逻辑表达式

作电路图

一般把输入信号画在同一水平面，传输门画在同一水平面，同一级逻辑门画在同一竖直面

典型时序逻辑

寄存器

功能：保存二进制、二进制移位

左移、右移移位寄存器：多个DFF输出输入串接（右移左串到右，左移右串到左），每一个时钟信号移位一次

串行输出：各DFF输出首尾相接，最后一个输出作为系统输出

并行输出：所有DFF输出同时对外引出，作为系统输出

串行输入：输入传递给第一个DFF，每次时钟将输入向后传递一个DFF

并行输入：输入同时提供给所有DFF

通用移位寄存器（支持以上所有操作），用多路选择器选择各种触发器输入

计数器

功能：记录脉冲数

加法、减法计数器：实现二进制递增递减，首尾状态成环

特殊进制计数器：n进制计数器，\lceil log_2n\rceil位状态并不全都启用，选择n种状态使得状态转移与电路最方便，其余的状态成为无关项。

自启动问题：电路刚通电时状态不稳定，初始状态为随机；表示数的状态可以通过环形状态转移实现功能，但无关态作为初态时未必能自行回到有意义状态正常工作。

判断：从各无关态开始连续状态转移，若能转移至有意义状态则可自启动，若在无关态中间循环则不能自启动，需要设置初值或改变状态设计

用移位寄存器实现计数器

环形计数器：寄存器末输入与初输入相连成环，T=n

扭环形计数器：寄存器末输入取反与初输入相连成环，T=2n

对n位环形计数器状态转移，基于状态中1的个数和排列，形成若干个循环（若选定一个1的状态为有效状态，则有2^n-n个无关项。

对n位扭环形计数器状态转移，基于状态中1的个数和排列，1的和为2n且01顺序同构的状态可以打通，形成若干个循环，为环形计数器的一半（若选定一个1的状态为有效状态，则有2^n-2n个无关项。

一般不能自启动，处理方法：可以设置初态进行预置、复位，也可以改变状态转移方程使无关项的环拆成导向有关项的链。

同步与异步

之前的计数器为同步计数器，所有DFF时钟相同。

异步计数器：各DFF时钟不同

DFF状态输入为原先的状态输出与输入取异或，控制输入为1时，每次时钟触发都会让DFF状态取反。时钟取上一个DFF的输出状态取反。

状态转移：每当一个时钟信号传给第一个DFF，第一级DFF取反；若本级状态由1变0，则意味着下一级的时钟（本级状态取反）有上升沿，下一级触发，状态取反。若所有DFF都为1，再触发时，会经由反馈回路将所有DFF置零。

Q0必须翻转

Qi是否翻转，取决于所有低位的触发器的状态是否都为1

如此，将所有DFF状态连接，即为每次递增1的二进制数

同步计数器的实现：把各级输出对各级输入的操作放在输入D前，用逻辑门实现。