Logisim

Logisim简介：

介绍

Logisim 使用图形用户接口，设计并仿真数字电路，包含基础库（基础门电路，存储器，多路选择器等简单器件）

特点:

• 开源(open-source)

• 可在任意支持 Java 5 及以上版本的机器上运行

• 画图接口基于直观的工具栏

• 电路可以存为文件，也可以 GIF 格式导出或打印输出

• 允许层次化的电路设计：子电路调用

• 包含众多内置电路器件：输入/输出，门电路，多路选择器，以及RAM存储器

• 内置组合逻辑分析模块，支持在电路、真值表和表达式之间转换

Logisim门电路

工具布局

总结：

1. Logisim 提供图形界面，以鼠标拖拽的形式可以新建部件以及进行部件间连线。

2. 也可通过快捷键 Ctrl+D 增加一个所选择的部件。

元件概览（不止门电路）

Wiring(线路) 组件

Splitter

The splitter creates a correspondence between a multi-bit value and several separate subsets of those bits.(简而言之就是将一个多位比特数同许多分割开的多位比特数的子集做联系) Despite its name, it can ==either split a multi-bit value into component parts==, or it can ==combine component parts into a multi-bit value== - or ==indeed it can do both at once==.

具体实例：When you work with multi-bit values, you will often want to route different bits in different directions. The Wiring library’s splitter tool allows you to accomplish this.

For example, suppose we want a circuit that computes the bitwise AND of the two nibbles of its eight-bit input (the upper four bits and the lower four bits)(省流：将一个二进制数的高四位同低四位做与运算). We will have an eight-bit value coming from the input pin, and we want to split that into two four-bit values. In the below circuit, we have used a splitter to accomplish this: The 8-bit input comes into the splitter, which divides the 8 bits into two 4-bit values, which are then fed into the AND gate and from there to the output.

In this example, the splitter ‘’splits’’ an incoming value into multiple outgoing values. But splitters can also work the other way: It can ==combine multiple values into a single value==. In fact, they are ==non-directional==: They can send values one way at one time and another way later, and they can even do both at the same time, as in the below example where a value travels eastward through the two splitters, then is routed back westward through them again, and then back eastward where it finally reaches its output.

Logisim treats splitters specially when propagating values within a circuit: Whereas all other components have ==a computed delay(计算延迟)== for purposes of simulating their behavior, values propagate through splitters (as well as wires) instantaneously.(省流：值传递经过splitters时无计算延迟)

The key to understanding splitters is their attributes. In the following, the term split end refers to one of the multiple wires on one side(像刷子毛的那一端的任意一个接口), while the term combined end refers to the single wire on the other side.

• The Facing attribute tells where the ==split ends== should be relative to ==the combined end==.(控制刷子毛朝向)
• The Fan Out attribute specifies how many ==split ends== there are.(分多少根刷子毛出去)
• The Bit Width In attribute specifies the bit width of ==the combined end==.(接入几位的比特)
• The Bit x attribute says which split end corresponds to bit x of the combined end. If multiple bits correspond to the same split end, then their relative ordering will be the same as in the combined end. Logisim splitters cannot have a bit from the combined end correspond to multiple split ends.(表示编号为0-((Fan Out)-1))的刷子毛的相对位置？）

Note that any change to the Fan Out or Bit Width In attributes will reset all Bit x attributes so that they will distribute the bits of the combined value as evenly as possible among the split ends.

Probe

Probe 作为一个显示线路数据值的部件，可以对==多位宽数据==进行实时监控，简而言之，就是可以直接显示接线的数值，并且不影响整个电路的运行。

熟练掌握 Probe 部件，可以方便对电路进行实时监控，做到分部件测试的效果。

Probe并不与电路中其他组件交互，适用于排错。

Probe的接入引脚接收的比特位数是可变的，取决于输入的比特位数。

通过点击Probe工具，便可在希望添加Probe器件的地方添加该器件。大多数情况下Probe器件与输出管脚器件功能一致，但当电路作为子电路器件使用时，输出管脚将作为接口的一部分，而Probe并不作为接口的一部分。除此以外，Probe并不具有Data Bits属性用以进行配置。从属性上看，Pin管脚和Probe十分接近，区别在于Pin管脚边框较厚且为黑色，Probe边框较窄且为黑色。

Probe的Facing属性可以更改其朝向，Label属性可以更改当前显示的内容，Label Location属性可以Label属性与器件的相对位置，还可以通过Label Font属性来修改标签词形。而Radix属性用来表示进制表示的形式。

Tunnel

Tunnel 部件是在整个 Logisim 实验中简化电路布线复杂度效果最好的一个部件，可以让你在纷繁复杂的接线中解脱出来，让你能够更加专心的关注于各个部件的设计，而不被复杂的接线所打扰。

Tunnel 名为隧道，即它可以将标签相同 Tunnel 之间的数据，通过一个不可见的“隧道”进行传输，在使用过程中，可以链接数据的输入端和输出端，使得数据可以方便简单的传输。

==注：Tunnel 需要增加标签以区分不同的数据。并且每个标签只允许有一个输入，输出的数量不做限制。但是在有较多 Tunnel 部件的时候，要特别留意标签的名字，防止出现混乱。==

Pull Resistor

Behavior

When connected to a point, this component has an effect only when the value at that point is the floating value (Z)(即0、1、x中的x，浮动值，或不确定的值). In this case, the resistor pulls the wire to which it is connected toward the value indicated in its “Pull Direction” attribute.(可以通过连接输入、输出间的电路将输入端的x值变为1(One)、0(Zero)、E(Error))


If it is connected to a multiple-bit value, then each bit in the value that is floating is pulled in the direction specified, while the bits that are not floating are left unchanged(省流:多位情况下恒定值保持不变，浮动值改变).

Pins

The resistor has just one pin, which is an output and has a bit width that is derived from whichever component it is connected.

Attributes

When the component is selected or being added, the arrow keys alter its Facing attribute.

• Facing

  The direction in which the component’s pin lies from component’s center.

• Pull Direction

  Specifies the value to which a floating value should be pulled. This could be 0, 1, or the error value.

Clock

Behavior

The clock toggles(切换) its output value on a regular schedule as long as ticks are enabled via the Simulate menu. (要先在最顶上一排中的Simulate menu里开启Ticks，才能让Clock”走起来“)(Ticks are disabled by default.) A “tick” is Logisim’s unit of time; the speed at which ticks occur can be selected from the Simulate menu’s Tick Frequency submenu.

The clock’s cycle can be configured using its High Duration and Low Duration attributes.

Note that Logisim’s simulation of clocks is quite unrealistic: In real circuits, ==multiple clocks will drift from one another and will never move in lockstep==. But in Logisim, all clocks experience ticks at the same rate.

Pins

A clock has only one pin, an output with a bit width of 1, whose value will represent the current value of the clock. The location of this pin is specified in the Facing attribute. The clock’s value will toggle on its schedule whenever ticks are enabled(只要启动,时间就会走), and it will toggle whenever it is clicked using the Poke Tool.

Attributes

When the component is selected or being added, the arrow keys alter its Facing attribute.

• Facing

  The side of the component where its output pin should be.

• High Duration

  The length of time within each cycle that the clock’s output should be 1.(省流:1持续的时间)

• Low Duration

  The length of time within each cycle that the clock’s output should be 0.(0持续的时间)

• Label

  The text within the label associated with the clock component.

• Label Location

  The location of the label relative to the component.

• Label Font

  The font with which to render the label.

Poke Tool Behavior

Clicking a clock component will toggle its current output value immediately.(再点击Poke后，直接点击clock即可转换clock的值)

Text Tool Behavior

Allows the label associated with the component to be edited.

Constant

Behavior

Emits the value specified in its Value attribute.(省流:正如其名，不断输出其显示值)

Pins

There is only one pin, an output whose bit width matches the Data Bits attribute. The location of this pin is specified in the Facing attribute. The component constantly outputs on this pin whatever value specified in the Value attribute.

Attributes

When the component is selected or being added, the hexademical digits ‘0’ through ‘9’ and ‘a’ through ‘f’ alter its Value attribute, Alt-0 through Alt-9 alter its Data Bits attribute, and the arrow keys alter its Facing attribute.

• Facing

  The direction in which the pin is located relative to where the value is drawn.

• Data Bits

  The bit width of the value placed onto the wire.

• Value

  The value, written in hexademical, that is emitted by the component. The number of bits used to specify the value cannot exceed the component’s bit width.

Power/Ground

Behavior

Emits a single value onto a wire. For a power element, indicated by a triangle(长得一个小雨伞样）, this value will be one (or, if the Data Bits attribute is more than 1, an all-ones value). For a ground element, indicated by an arrow of three shortening parallel lines(神似WiFi信号图标被一把棍子戳平了), this value will be zero (or, if the Data Bits attribute is more than 1, an all-zero value).

The same functionality can be achieved using the more versatile Constant component. The only reason to prefer ground and power is that they are standard electronic symbols.(因为标准所以爱)

Pins

There is only one pin, an output whose bit width matches the Data Bits attribute. The component constantly outputs the same value on this pin: for a ground component, the output is an all-zero value, and for a power component, the output is an all-one value.(省流：power全输出1，ground全输出0)

Attributes

When the component is selected or being added, Alt-0 through Alt-9 alter its Data Bits attribute and the arrow keys alter its Facing attribute.

• Facing

  The direction in which the arrow will point from the location of its pin.

• Data Bits

  The bit width of the value placed onto the wire.

Transistor

Behavior

A transistor has two inputs, called gate and source, and one output, called drain. When diagrammed, the source input and drain output are drawn connected by a plate;(source同drain直接通过极板相连) Logisim draws an arrowhead to indicate the direction of flow from input to output.(箭头表示输入到输出流向) The gate input is drawn connected to a plate that is parallel to the plate connecting source to drain.(gate在极板之上) Logisim supports two types of transistors, with slightly different behaviors described below; the P-type(positive) transistor is indicated by a circle connecting the gate input to its plate, while the N-type(negative) transistor has no such circle.

Depending on the value found at gate, the value at source may be transmitted to drain; or there may be no connection from source, so drain is left floating. The determination of transmitting or disconnecting depends on the type of transistor: A P-type transistor (indicated by a circle on the gate line) transmits when gate is 0(gate是0且在P状态下，drain的值与source的值相同), while an N-type transistor (which has no such circle) transmits when gate is 1. (反之亦然)The behavior is summarized by the following tables.

​ P-type

gate	drain
0	source
1	Z
X/Z	X*

​ N-type

gate	drain
0	Z
1	source
X/Z	X*

*:if source is Z, drain is Z; otherwise drain is X.

If the Data Bits attribute is more than 1,==the gate input is still a single bit==, but its value is applied simultaneously to each of the source input’s bits.An N-type transistor behaves very similarly to a Controlled Buffer. The primary difference is that a transistor is meant for more basic circuit designs.(基础即王道)

Pins (assuming component faces east, gate line top/left)

West edge (input, bit width matches Data Bits attribute)(source)

The component’s source input that will transmit to the output if triggered by the gate input.

North edge (input, bit width 1)(gate)

The component’s gate input. For P-type transistors, the transistor will transmit if the gate value is 0; for N-type transistors, this will trigger the transistor if the gate value is 1.

East edge (output, bit width matches Data Bits attribute)(drain)

The component’s output, which will match the source input if indicated by the gate input, or will be floating if the gate input is the negation of what indicates negation. If gate is floating or an error value, then the output will be ==an error value==.

Transmission Gate

一个Transmission Gate有三个输入(source、n-gate、p-gate)、一个输出(drain)。与Transistor类似的，source同drain直接通过两极板相连，而p-gate(同P-type一样有小圆圈)和n-gate(同N-type一样没圆圈)分别平行存在于上下极板(出场器件).

==The transmission gate is simply the combination of two complementary transistors.==(鞭辟入里)Indeed, the same behavior can be achieved in Logisim by using just one transistor. However, designers sometimes prefer to use matched pairs of transistors due to electrical issues with draining voltage that is more complex than Logisim attempts to simulate.(不知所云，设计师为王？)

只有p-gate和n-gate分别为0和1时，source可以原封不动的传给drain。

p-gate	n-gate	drain
0	0	X*
0	1	source
1	0	Z
1	1	X*
X/Z	any	X*
any	X/Z	X*

Bit Extender

Behavior

The bit extender transforms a value into a value of another bit width. If it’s being transformed into a smaller bit width,(入大出小就截断，保留低位) it is simply truncated to keep the lowest-order bits. If it’s being transformed into a large bit width, the lowest-order bits are the same,(入小出大就补齐) and you have a choice about what the additional high-order bits will be: They can all be 0, all be 1, all match the input’s sign bit (its highest-order bit), or the component can have an additional one-bit input that determines the identity of these other bits.

Pins

• West edge (input, bit width from Bit Width In attribute)

  The multi-bit input whose value is to be transformed.

• East edge (output, bit width from Bit Width Out attribute)

  The computed output.

• North edge (input, bit width 1)

  ==Specifies what the additional bits in the output should be==. This pin is available only when the Extension Type attribute is Input.

Attributes

When the component is selected or being added, the digits 0 through 9 alter the Bit Width In attribute and Alt-0 through Alt-9 alter its Bit Width Out attribute.

• Bit Width In

  The input’s bit width.

• Bit Width Out

  The output’s bit width.

• Extension Type

  Assuming the output bit width exceeds the input bit width, this attribute configures what the additional output bits should be. If Zero or One, the additional bits are 0 or 1 accordingly. If Sign, ==the additional bits are taken to match the highest-order bit in the input==. (拿原来最高位去补齐多出来的，类似用符号位(sign)补齐)And if Input, ==the component has a second input on its north side whose one-bit value is used for the additional bits==.(input提供的只能是一位，也就是说补齐时所有方式补齐的位都全是0或全是1，好多余的设计)

Gates(逻辑门) 组件

##### Buffer

Behavior

The buffer simply passes through to its right output whatever input it receives on the left side. (正常情况下，传啥输啥，除非改变其Attributes中的Output Value)

Buffers are ==the most useless== of the gate components provided in Logisim; (官方认证)its presence in the Gates library is just as much a matter of completeness (a component for each possible one-input truth table) as it is a matter of providing useful functionality. Still, it can be occasionally useful to ensure that values propagate in only one direction along a wire.(莫名其妙的用途，存在即合理？)

Attributes

Output Value：

Indicates how false and true results should be translated into output values. By default, false is indicated by a low voltage (0) and true by a high voltage (1), but one or the other can be replaced by a high-impedance (floating) value instead. This allows wired-or and wired-and connections, as illustrated in the AND/OR/NAND/NOR Gate documentation.

用Buffer和Pull resistor构建与门和非门。下图中左边两个Buffer的Output Value属性都为floating/1(即1得1、0得x),the resistor pulls to 0.右边两个Buffer的Output Value属性都为0/floating(即1得x、0得0),the resistor pulls to 1.


XOR(异或)/XNOR(同或)/Odd Parity(奇检验)/Even Parity(偶检验) Gate

x	y	XOR	XNOR	Odd Parity	Even Parity
0	0	0	1	0	1
0	1	1	0	1	0
1	0	1	0	1	0
1	1	0	1	0	1

As you can see, the Odd Parity gate and the XOR gate behave identically with two inputs; similarly, the even parity gate and the XNOR gate behave identically.(相似但不相同)But if there are more than two specified inputs, the XOR gate will emit 1 only when there is exactly one 1 input(异或只有在仅有一个1输入时输出为1), whereas the Odd Parity gate will emit 1 if there are an odd number of 1 inputs(而奇检验在输入为1的个数为奇数的情况下输出就为1). The XNOR gate will emit 1 only when there is not exactly one 1 input(同或在输入为一个1时输出为0，其余情况输出均为1), while the Even Parity gate will emit 1 if there are an even number of 1 inputs(偶检验在输入为偶数个1时输出为1). The XOR and XNOR gates include an attribute titled Multiple-Input Behavior that allow them to be configured to use the Odd Parity and Even Parity behavior.

Controlled Buffer/Inverter

正如其名，Controlled Buffer/Inverter就是由一个控制位(正常情况下器件南边的把儿，需要输入值)控制的Buffer/Inverter(NOT gate).因此，也被称为three-state buffers/inverters。

当控制位为1时Controlled Buffer/Inverter分别为Buffer/NOT gate;

当控制位为0或者未知(i.e., floating)时,两种器件的输出均为x;

当控制位为Error(such as would occur when two conflicting values are being fed into the input)时，器件输出值均为error。

Controlled buffers can be useful when you have a wire (often called a bus) whose value should match the output of one of several components. By placing a controlled buffer between each component output and the bus, you can control whether that component’s output is fed onto the bus or not.

Plexers(复用器)组件

Multiplexer

多路选择器，将左端多个输入（从上到下以0开始编号）经过下端左侧的选择（若选择为浮动值则输出全为浮动值x）其中一个编号复制到右端输出。下端右侧还有一个输入，在其为0时将输出全置为浮动值x，不论输入值以及选择的编号是多少；其为其他值时无影响。

Demultiplexer

多路分配器（网易有道翻译），将左端一个输入经过下端右侧的选择（若选择为浮动值则输出全为浮动值x）其中一个编号复制到右端（从上到下以0为始编号）相应编号输出。下端左侧还有一个输入，其为0时将输出全置为浮动值x，不论输入值以及选择的编号是多少；其为其他值时无影响。

Decoder

译码器，根据下端右侧输入的编号在右端（从上到下以0为始编号）输出1。下端左侧还有一个输入，其为0时将输出全置为浮动值x，不论输入值以及选择的编号是多少；其为其他值时无影响。

最大的功能在于可以将二进制编码转换为相应的独热码，如101的3位二进制编码作为输入就可以被转换为00100000的8位独热码作为输出。

Priority Encoder

优先编码器，左端引脚从上到下以0为始编号，右端上引脚输出左端输入为1的引脚的最大编号，右端下引脚输出是否找到最大编号：若未找到输出0，同时右端上引脚也输出0或者全为浮动值x（依据Disabled Output属性确定）；若找到则输出1，同时右端上引脚输出最大编号。除此之外，在该器件的下端还有一个Enable In输入引脚来决定器件是否运行：若输入为0，则停止运行；否则正常运行。并且该器件上端还有一个Enable Out输出引脚：只有当器件正常运行并且右端没有输出时即右端下引脚为0时输出1，其余情况都输出0.上述性质可以实现多个编码器串接来适应额外的输入。

An additional output of the priority encoder is 1 whenever the priority encoder is enabled and finds a 1 on one of the indexed inputs. When chaining priority encoders together, this output can be used to identify which of the encoders was triggered.（省流：右端下引脚的输出可以用来判断多个串接起来的优先编码器中哪个被“激活”了）

Bit Selector

该器件可将多位比特数，从低位起均分为位数相同的多个切片，若高位不够切则用0补齐再根据下端输入的切片索引在右端输出相应的切片。例如：输入多位比特为01010101，设置Bit Selector的Output Bits为3即均分为位数为三的多个切片，那么切片0即为101，切片1为010，切片2为001，切片3为000。

Arithmetic(运算器)组件

Adder

作为一个加法器，该器件的功能就是将左端(正常情况下)两个输入相加并加上上端输入的carry-in(c in)位，得到sum，从右端输出sum溢出后的部分，下端输出carry-out(c out)为sum溢出的部分。如此一来多个该器件相连结可以扩大加法的范围。

Subtractor

作为一个减法器，该器件的功能就是将左上端(正常情况下)的输入减去左下端的输入并且减去borrow-in(b in)位，得到sum，从右端输出sum溢出后的部分，在假定无符号数减法的情况下，如果左上大于等于（左下+borrow-in）则下端borrow-out(b out)输出0，反之输出1，表示从更高一位借一位1，例如:左上:10000000,左下:10000000，b in:1，则b out:1，sum:11111111即110000000-10000001。

Multiplier

作为一个乘法器，该器件的功能就是将左端(正常情况下)两个输入相乘并加上上端输入的carry-in(c in)位，得到sum，从右端输出sum溢出后的部分（the lower dataBits bits of the product of the two values coming in the west edge, plus the cin value），下端carry-out输出sum溢出的部分（the upper dataBits bits of the product）。

Divider

作为一个除法器，该器件拥有三个输入端，两个输出端，主要功能是将左上端输入的数同上端输入的数结合，上端作高为，左上端做低位，作为dividend，除以左下端输入的数divisor，根据quotient * divisor + remainder = dividend，右端输出quotient，下端输出remainder。但是输出时并不考虑溢出问题，若溢出只会显示溢出后结果，无法查询完整结果，ps：需手动控制防溢出(除法老是出问题)。

Negator

取相反数即取反+1的操作。

Comparator

比较器顾名思义，即将左上端输入的数同左下端输入的数作比较，大于情况输出在右上端，等于情况输出在右中端，小于情况输出在右下端。

Shifter

移位器将左上端输入的data移动左下端输入的dist位数，dist的位数根据data输入的位数决定，用y表示data的位数、x表示dist的位数，则x为2^x^>=y中x的最小整数值。

而其中移动的类型又分为5种：

• 逻辑左移（Logical Left）:左移低位补0. For example, 11001011 logically shifted left twice is 00101100. (The top two ones are lost.)

• 逻辑右移（Logical Right）: 右移高位补0. For example, 11001011 logically shifted right twice is 00110010. (The bottom two ones are lost.)

• 算术右移（Arithmetic Right）: 右移高位根据最高位补. For example, 11001011 arithmetically shifted right twice is 11110010.

• 循环左移（Rotate Left）: 左移低位由高位溢出的补齐. For example, 11001011 rotated left twice is 00101111.

• 循环右移（Rotate Right）: 右移高位由低位溢出补齐. For example, 11001011 rotated right twice is 11110010.

Bit Adder

输出输入的二进制数中的1的个数。

Bit Finder

索引器根据Attributes中的Type（Lowest-order 1、Lowest-order 0、Highest-order 1、Highest-order 0）在左端输入的数中寻找相应的索引，若没找到则在下端显示0并右端也同样显示0；若找到则在下端显示1并在右端显示相应的索引。

Memory(存储)组件

D/T/J-K/S-R Flip-Flop

每个触发器储存一个数据位，并通过右端Q释放，右端Q下侧一端还会输出当前触发器储存的值的补码（省流：若Q为1则Q下为0；反之亦然）。通常情况下，释放值将会受左端输入影响。尤其是当以三角形为标记的clock输入端的输入值发生0/1变换或者低电平持续以及高电平持续时。

D Flip-Flop

D	Q
0	0
1	1

当时钟触发（根据器件Trigger属性（0->1切换、1->0切换、低电平持续、高电平持续）中的描述决定）时，触发器储存的值变为该时刻D输入的值。

T Flip-Flop

T	Q
0	Q
1	Q‘

当时钟触发（根据器件Trigger属性（0->1切换、1->0切换）中的描述决定）时，触发器储存的值要么保持不变要么切换，当T输入为1时切换，当T为0时保持不变。

J-K Flip-Flop

J	K	Q
0	0	Q
0	1	0
1	0	1
1	1	Q’

当时钟触发（根据器件Trigger属性（0->1切换、1->0切换）中的描述决定）时，若J输入和K输入（下文简称J和K）一样，同为0时，Q值不变；同为1时，Q值切换。若J和K不一样，则J（Jump）为1时，Q值为1；K（Kill）为1时，Q值为0。

S-R Flip-Flop

S	R	Q
0	0	Q
0	1	0
1	0	1
1	1	Q

当时钟触发（根据器件Trigger属性（0->1切换、1->0切换、低电平持续、高电平持续）中的描述决定）时，若S输入和R输入（下文简称S和R）一样，则Q值保持不变；若S和R不一样，则S（set）为1时，Q值为1；R（reset）为1时，Q值为0。

此外

每一个触发器的下端从左至右都有三个输入端口，按顺序记为1、en、0端口。1端口输入为1时，Q值立刻变为1且停止触发，1端口其余值对触发器无影响。en端口为0时，时钟的触发将被忽略，其余值时始终仍可触发。0端口为1时，Q值立刻变为0且停止触发，0端口其余值对触发器无影响。0端口将Q值置0优先于1端口置1。

Register

一个寄存器储存一个多比特值，并以十六进制的形式体现在器件中，从右端Q输出相应的二进制值。器件左端有D（Data）（上）输入端和en（enable）（下）输入端，D端输入数据，en端决定寄存器是否接收clock端的触发，当en端为1时接收clock端触发，当始终触发根据器件Trigger属性（0->1切换、1->0切换、低电平持续、高电平持续）中的描述决定）时，寄存器的值和Q端的值变为D端此时的值；当en端为0时忽略clock端的触发信号。器件下端从左至右有两个输入端分别为clock端（左）和0端口（右），0端口为1时，寄存器的值和Q值立刻变为0且停止触发，0端口其余值对触发器无影响。

Counter

Behavior

计数器共有5个输入端（三个在左端，从上至下为load端、D（Data）端、ct（count）端，另外两个在下端，从左至右为clock端和0（clear）端），两个输出端（在右端，从上至下依次为Q端和carry端）。当0端不为1时，且当时钟触发（根据器件Trigger属性（0->1切换、1->0切换）中的描述决定）时，计数器的值和Q值会根据load端和count端的值发生如下表的变化：

load(加载)	count(计数)	触发变化
0/x	0	计数器的值和Q值保持不变
0/x	1/x	计数器的值和Q值递增
1	0	计数器的值和Q值变为D值(可以理解为加载上传)
1	1/x	计数器的值和Q值递减

当0端不为1但无时钟触发时，计数器的值和Q值保持不变；当0端为1时，Q值变为0，不管任何输入。除此之外，carry端在Q值达到==定义的最大值==（由Attributes中的Maximum Value定义）并且时钟触发的变化为递增或者Q值为0并且时钟触发的变化为递减时为1，其余情况均为0.

Attributes

==特别注意==：Action On Overflow：代表“溢出”时的行为（递增过定义的最大值或者递减过0的时候），共有四种：Wrap around（定义的最大值增为0，0减为定义的最大值）、Stay at value(保持不变)、Continue counting(定义的最大值递增直到比特位所能表示的最大值，继续增为0；0减为比特位所能表示的最大值)、Load next value(“溢出”时变化为D值)。

Shift Register

移位寄存器按阶段存储并输出值，并从左向右按时间顺序加入或删除不同的阶段的值。

左端有三个输入口，左上为1比特值，当其不为0时，寄存器做正常的一位存储行为；反之停止移位存储。不过当Load输入端(上最左)为1时，左上输入的值将被忽略。左中的位宽根据寄存器存储的位宽决定，是输入数据的端口。左下是clock端，当时钟触发时，寄存器会进行移位存储，将会移位处理，或者加载上传数据(Load==1时)。

上端最左端为Load端，其输入为1时，会将其右侧上端有输入的引脚的值在下一次时钟触发时加载上传到移位寄存器对应的阶段的值上。

下端最左端为clear端，其输入为1时，将把移位寄存器的所有阶段的值置为0。其右侧所有端口在有输出端口相连时会输出相应阶段的值。

右端有一个输出端口，输出最后一个阶段的值，即最右边的一个阶段的值。

Random

该器件根据特定的公式来产生随机数。

RAM存储器

RAM 是一个可读可写的存储器，在实验中，采用的是读与写相互分离的类型，所以在选择 RAM 时，请将数据接口选择为 “Separate load and store ports”。

RAM可以储存多达16777216个值(在the Address Bit Width属性中指定)，每个值最多可以包含32位(在the Data Bit Width属性中指定)。

RAM储存的当前值显示在组件中，显示的地址在显示区左侧以灰色列示。在其内部，每个值都用16进制表示。当前所选地址的值将以反向文本显示（即黑底白字）。

RAM有三种不同的传输界面，取决于the Data Interface attribute属性。

1.One synchronous load/store port（默认，一个同步加载/存储接口):此时该器件有一个单接口在左端即可加载上传也可储存数据。而这些的执行取决于ld端（下端从左至右数第三个）的输入:1(或浮动)表示将数据加载到组件左端指定的地址，0表示将数据存储在端口上。为了将数据传入和传出组件，您需要使用受控缓冲区组件，如下所示。

2.One asynchronous load/store port(一个异步加载/存储接口)

此时器件没有时钟端。当ld端输入为0时，在数据接口处的值会被存储到内存中。如果，当ld端输入为0时，地址或数据发生变化，则会发生额外的存储。这个选项意味着更接近于许多可用的随机存取存储器的接口。

3.Separate load and store ports（单独的加载和存储接口）

此时提供了两个数据端口-一个在左端用于存储数据，另一个在右端用于加载数据。此状态下有7个输入端，1个输出端。

器件左端有两个端口，左上为A端口，输入的值将表示选择的存储地址（address）；左下为D端口，输入的值将表示写入的值。

器件下端有5个输入端口，从左至右分别是str、sel、clock、ld、clr。其中str端口决定是否将左D端口的数据上传到A端输入的地址上（前提是sel端口输入值不为0）。sel端口的作用便是决定该地址是否被选择，即是否被选中。ld端口决定左D端口的数据是否上传到右D端口上（前提是sel端口输入值不为0）。clr端口的作用便是将RAM中所有地址的值置0。

器件的右端有一个D端口，当sel== 1 且 ld==1，该端口将输出左D端口的值。

ROM存储器

ROM 是一个只读类型的存储器，顾名思义，在使用过程中只能对其进行读取操作，而==不能进行写操作==，所以 ROM 在创建时，必须一次性将所有的信息全部导入，之后不可再进行更改。

对于 RAM 和 ROM 的数据的导入有以下两种方式：

1. 手动导入：可手动在数据区域选择内存直接进行更改
2. 文件导入：可编写相应的数据文件，进行一次性导入，文件头需要增加一行 ==v2.0 raw== 字样才可以正确导入。

对于 RAM 和 ROM 的数据位宽，在实验中，请选择 ==32 位==，这与 ==MIPS 的指令长度相匹配==，至于地址位宽，请确保位宽长度能够容纳实验要求的指令数量。

ROM组件最多可存储16,777,216个值，每个值最多可包含32位。电路可以访问ROM中的电流值，但不能改变它们。用户可以通过Poke工具交互式地修改单个值，或者用户可以通过菜单工具修改整个内容。

Input/Output(输入/输出)组件

Base（基本）组件

例：

搭建异或电路

x^y=x XOR y=(x AND NOT y) OR (NOT x AND y)

真值表

x	y	x XOR y
0	0	0
0	1	1
1	0	1
1	1	0

图示：

Logisim组合电路

子电路

创建子电路

通过Project栏下的Add Circuit；

添加子电路内容

子电路布线

设置子电路外观

ps:更改外观时，可对端口增加文字说明，提高可读性

引用子电路

3种方法：

1.在Project菜单中选择View Simulasion Tree，窗格将显示正在访问的电路的子电路的层次结构，双击层次结构中的一个元素将显示该子电路中的仿真情况。

2.通过在子电路上右键或者右键同时点击ctrl键得到选项点击View即可。

3.选用Poke工具，点击子电路出现放大后双击放大镜即可进入该子电路。

Wire colors


利用Logisim进行组合逻辑分析

三种主要技术

1.逻辑电路

2.布尔表达式

3.真值表

运用组合逻辑分析模块，可根据逻辑表达式得到相应的真值表。也可通过输入真值表，再产生相应的表达式，或者产生相应的电路。

打开组合逻辑分析模块的方式：

1. Window 栏目下的 Combinational Analysis

2. Project 栏目下的 Analyze Circuit

ps:Logisim的组合逻辑分析并不支持异或操作。

Logisim时序电路

SR锁存器（SR latch）

SR锁存器由两个==交叉耦合的或非门==（或者，等价地，两个==反置输入的与非门==）组成，整个电路的状态可以由 S（Set）和 R（Reset）输入来决定，对应得到两个相反的输出 Q 和 ~Q，它的真值表如下：

其中 SD 和 RD 为是电路输入的两个端口，Q^n^ 表示电路当前的输出，Q^n+1^ 表示电路下一个状态的输出。由真值表可以看出，这个电路的输出不仅和当前输入有关，也和==上一次的输出==有关。显然这个电路就是一种能记住自己之前状态的电路。其实，这就是一个最简单的时序电路，我们称之为 SR 锁存器。

观察其功能一栏，可以看到，通过改变 SD 和 RD 为合适的值，我们可以改变电路的输出，而当 SD 和 RD 为均为 0 时，电路会一直保持原来的输出不变，这看上去很像 U 盘之类的设备（通电时能够修改存储的内容，断电时保持内容不变）。事实上，通过配合合适的外部电路，我们就可以使用这个电路来存储整个电路的状态，从而搭建起更复杂的时序电路。(其实同Memory组件里的S-R Flip-Flop器件类似)

常见的两种搭建方法：

1.使用或非门

2.使用与非门

寄存器

基本寄存器

一些概念

时钟沿

时钟上升沿：数字时钟电路中，数字电平从低电平（数字 “0”）变为高电平（数字 “1”）的那一瞬间叫作上升沿。

时钟下降沿：数字时钟电路中，数字电平从高电平（数字 “1”）变为低电平（数字 “0”）的那一瞬间叫作下降沿。

复位信号

寄存器会接受一个外部传入的、可以将自身存储数据清零的信号。寄存器的复位信号有两种，分别是同步复位和异步复位。

同步复位：复位信号只有在时钟上升沿到来时，才能有效。也就是说，同步复位操作永远发生在时钟上升沿，即便复位信号提前到来，也无法立刻完成复位操作。

异步复位：无论时钟沿是否到来，只要复位信号有效，就对系统进行复位。

关键路径

为加快时序逻辑电路的运行速度，一个重要的手段就是提高时钟频率。但是，时钟频率是能无限增加的吗？显然不是。一个重要的限制就是寄存器之间组合逻辑电路的关键路径延迟。

具体来说，一个简单的时序逻辑电路如下：

两个寄存器之间的加法器，是一个组合逻辑电路。其本身存在一定的门延迟。也就是说，加法器的输入信号稳定的一段时间之后，输出信号才能稳定。如果时钟周期比这个门延迟的时间还要短，那么后面的寄存器读入的值就==无法确定==。

在寄存器之间的逻辑较为复杂的情况下，可能存在多条路径。关键路径，是指同步逻辑电路中，组合逻辑延时最大的路径。

深入探讨

在时序逻辑电路中，会常常见到这样的情形：

寄存器的输出端经过一些组合逻辑电路，链接到寄存器的输入端。

分析可知，当时钟上升沿来到时，数据更新为寄存器中的值 + 1。a = a + 1，这样的表达式十分像导致短路的电路（如果在组合逻辑电路中就是会短路的）。初学者很容易将寄存器理解为上升沿时对前一个输入信号的赋值。这样理解，确实难以解释其短路的问题。那么，在上升沿到来时，电路内部究竟发生了什么？

在解释这个问题之前，我们先来看下面这个例子。

当第一个时钟上升沿到来时，左边的寄存器会赋值成 1，但右边的寄存器仍然是 0。如果是在时钟上升沿到来时，进行赋值，如何保证不会一次性让两个寄存器都变成 1 呢？

这两个问题事关寄存器上升沿赋值的本质。在上一节中我们谈到，寄存器本质就是一个 D 触发器。

它是由两个 D 锁存器构成的。D 锁存器的功能是当 CP 为高电平(1)时，Q 赋值为 D。当时钟低电平(0)时，左侧的锁存器将 D 赋值给 N1，当时钟高电平(1)时，右侧的锁存器将 N1 赋值给 Q。这个世界上本没有上升沿赋值，只有高低电平赋值。通过这样两个 D 锁存器结合形成的 D 触发器，宏观上就表现为了上升沿的赋值。这个过程有点类似于船只通过大坝的过程。先打开第一道关卡，堵第二道关卡（时钟低电平时），让船（输入数据）到中转站（N1），然后堵上第一道关卡，开第二道关卡（时钟高电平时），让船只通过。由于两个过程交替进行，宏观上就变成了，时钟在上升沿时，数据进行赋值。

移位寄存器

有限状态机

状态机的定义与行为

有限状态机（ Finite-state machine ，简称 FSM ），其所描述的是一个对象，在一段时间内，经过一系列事件后，其状态进行一系列转移的行为特征。

状态机的构成和基本性质

数学定义：构成一个有限状态机的六元组为：状态集合，输入集合，输出集合，状态转移函数，输出函数，初始状态。给定以上六个集合，函数或元素，就可以确定一个有限状态机。

据此，有限状态机具有以下特征：

• 在任何时间点，状态、输入、输出均为给定的有限种情况之一。

• 对于一对确定的当前状态和输入，只有一个固定且唯一的次态（下一个周期的状态）。

• 对于一对确定的当前状态和输入，只有一种固定且唯一的输出情况。

状态机的时序行为

我们以周期为时间段的单位计时。方便起见，这里将最先到来的周期记为第 0 周期。 每个周期内不同时间点的输入可能变化，但每个周期内的状态==一定不变==。

状态转移行为可以描述成如下过程：

• 当第 0 周期开始，状态 state 设为初始状态 state0 。
• 每当第 n 周期结束前的最后一瞬间，记该瞬间的输入为 *inputn*。
• 每当第 n 周期结束，第 n+1 周期开始时，状态变为状态转移函数给出的次态：

staten+1=Fnext_state(staten,inputn)

输出行为可以描述成如下过程：

• 在任意周期中的任意时间点，输出为 Foutput(state,input)。这里的 input 是当前时间点的输入，state 是当前时间点的状态。

Moore 和 Mealy 状态机的区别

区分状态机类型时：当==输出函数的结果==会随 input 变化而改变时，该状态机为 Mealy 机，否则为 Moore 机。

前者的输出逻辑与有限状态机的当前状态和当前输入有关。后者的输出逻辑仅与状态机当前状态值有关。

体现在状态图中就是前者的输入会连接入输出电路中进而影响输出值，而后者则没有。

例子

考虑一个饮食不太规律的人。这个人可能会跳过一天中的几顿饭。我们可以用状态机模拟这个人，并且分析其状态。比如：这个人吃的上顿饭是不是早饭？

状态转移

一个人的就餐状态可以划分为：上一顿是早饭，上一顿是午饭，上一顿是晚饭，三种，时间状态分：早，中，晚。这两部分构成了状态。（那就有<早，早>（前一个为上一顿饭，后一个为当前时间）、<早，中>、<早，晚>、<中，早>、<晚，早>、<中，中>、<中，晚>、<晚，中>、<晚，晚>共9种状态，联想到二进制数则需要高位三种、低位三种，也就是四位数表示）影响状态的因素（输入），简单起见假设只有吃东西，不吃东西两种。每逢饭点（每一周期结束或开始时），时间状态改变。如果这个人在吃饭，那么上一顿饭的内容就会发生改变。如果不在饭点，那么吃的东西并非正餐，不改变状态。

用伪代码描述这个次态逻辑如下：

状态 = <上顿饭, 当前时间>;
下一周期的上顿饭 = 吃不吃 ? 当前时间对应的饭 : 上顿饭;
下一周期的当前时间 = 当前时间 + 1;
次态 = <下一周期的上顿饭, 下一周期的当前时间>;

输出

输出的内容与此时的输入是否有关，决定了该状态机是 Moore 机还是 Mealy 机。这是 Moore 机和 Mealy 机最根本的区别。

如果输出以下内容，由于输出与输入（现在吃不吃）无关，这是个 Moore 机：

上顿饭是不是早饭 = 上顿饭 == "早饭" ? "是" : "否";

如果输出以下内容，由于输出与输入（现在吃不吃）有关，这是个 Mealy 机：

在不在吃 = 吃不吃 ? "是" : "否"；

设计电路

之后再根据题目要求，补齐图中输出电路，设计状态机的工作就告一段落了。

总结

• 采用状态机解决问题时，状态（和状态转移）的设计对工作的难度有着至关重要的影响。设计状态机时，你应当设计好输入，状态，输出之间的关系。

• 完成设计过程之后，实现组合电路部分。可以参考下图。（图中是 Mealy 机的基本结构。如果你所需的结果是一个 Moore 状态机，输出电路的结果应当与状态机输入无关。）

有限状态机所需的最小位数并不是每一个子状态的位数乘以子状态个数的结果，应该是在二进制下总状态数所需的最小位数。例如：如果有9种状态则应需要至少4位，因为2^4^=16>9，而2^3^=8<9。同理若有625种状态，则应至少需要10位即可，因为2^10^=1024>625,而2^9^=512<625。

Logisim设计指南

1.对电路进行标识（Label）

2.使用适当的多路选择器（Multiplexer）

3. 不要使用常量来扩展信号

在电路中尽量避免使用常量。

4. 不要将信号和它取反的结果作为多路选择器（Multiplexer）的输入

5. 适当使用常量

正如3中提到的，在通常情况下，你绘制的电路不应需要任何常量。两种例外的情况是：

(a) 子电路需要的输入比你需要使用的多;

(b) 常量能使你的电路更加简单。每当你想要向电路中添加一个常量时，思考一下能否通过使用其他门电路来优化掉这个常量。

6. 不要将一个信号同时作为多路选择器（Multiplexer）的输入端和控制端

这样的多路选择器可以用一个或门代替掉。

7. 学会做全面测试

请确认你提交的电路中不包含任何红色的连线，并且能够通过你自己构造的测试。如果你设计的电路使用二进制补码输入，请务必测试正、负数两种情况。

你构造的测试点至少应包括：正数+正数、正数+负数、负数+负数、负数+正数，另外不要忘记 0。

8. 使用正确的数据流方向

在 Logisim 中，通常的数据流方向是==由上至下==、==由左至右==，虽然很多器件可以通过更改朝向来改变输入输出的方向，但多路选择器（Multiplexer）等器件的朝向是不能更改的。

9. 学会编辑子电路外观

通常子电路的默认外观都非常丑陋，接口拥挤，而且没有注释，所以推荐大家尽可能自行编辑子电路外观，这里给出一个示例。

10.子电路输入修改

修改时要同时修改不然在时序逻辑电路中会导致不同子电路的时序混乱。

Logisim 自动化方法概览

观察电路的实际储存形式，可以发现它只是 ==XML 代码==，因此可以使用代码自动生成的方法简化操作，达到提高效率的目的，接下来我们就对方法本身进行介绍，并针对某个具体问题进行讲解。

circ 文件与标签

Logisim 使用的文件是 .circ 文件，它是使用扩展性标记语言编写的文件，Logisim 通过这种文件来存储电路。这是一种描述性文件，和网页用的语言 HTML 类似，可以通过直接修改文件来更改电路图。作为一种 XML 文件，它主要是被用于传输数据，而非显示数据，这是与 HTML 的不同之处，因此它的标签均是==可以自定义==的。只需满足如 <foo>bar</foo> 式的格式即可，在 Logisim 中同样也有 Logisim 自行规定的一些标签，通过标签的类型其中比较常见的有：

• <circuit> 是电路或子电路的标签，用于标记整个电路

• <wire> 标签，用于连线，通过 x-y 属性定位，需要自己尝试。例如：

  <wire from="(230,180)" to="(300,180)"/>

• <comp> 标签，拥有 loc 和 name 属性，用于调用库元件

  <comp lib="0" loc="(130,220)" name="Tunnel">
       <a name="width" val="5"/>
       <a name="label" val="A3"/>
     </comp>

我们的自动化方法其实是一种半自动方法，需要我们去观察使用 GUI 工具搭建出来的电路，再在这个基础上进行代码生成，其实是一种聪明的复制粘贴。

以内存矩阵为例

下面我们来考虑这么一个问题：

假设我们现在有 8 位字长，存储容量为 256B（8 位地址）的 ROM 芯片，我们需要搭建合理的电路，将其扩展成，32 位字长，存储容量为 16KB 的 ROM（12 位地址）。ROM 芯片如图：

从理论上分析，字长扩展了 4 倍，地址扩展了 4 位，因此共需 4 * 16 = 64 块原芯片，预计是要摆出一个 16 行 4 列的芯片矩阵。看，面对如此大量的芯片，传统地在 Logisim 中“手撸”一个电路就显得十分繁琐了。因此我们需要采用自动化的方法。

首先我们需使用 ==GUI== 工具拖放元件，这一步其实是非常重要的，通过合理的尝试，我们可以找到显示效果最漂亮的摆放方式，为之后的编码提供位置信息。

之后我们需要观察产生的 .circ 文件，文件中我们可以发现，<comp> 标签表示对库元件的调用，用 <a> 标签表示相关的属性，loc 属性表示位置.每个 <comp> 标签就是一个个 ROM 芯片。我们自动化方法的核心其实就是构造一个可以被==重复==摆放的最小单元，而且这个最小单元往往通过 Tunnel 连带着输出一起。在本例中即是这个 <comp> 标签

<comp lib="4" loc="(420,290)" name="ROM">
      <a name="contents">addr/data: 8 8
0
</a>
    </comp>
    <comp lib="4" loc="(260,390)" name="ROM">
      <a name="contents">addr/data: 8 8
0
</a>
    </comp>
    <comp lib="4" loc="(260,290)" name="ROM">
      <a name="contents">addr/data: 8 8
0
</a>

接着我们需要编写脚本去批量生成按照规律摆放的 ROM 芯片，在此我们使用较为简单的 Python 语言去编写脚本。需要知道的是，整个自动化方法的核心就是把摆放电路这件机械重复的事，交由计算机去完成。我们只需要根据前文所确定的最小单元，与摆放的位置信息，就能够编写相应的代码来自动生成所要的部分电路 XML。

start_x = 260
start_y = 290
step_x = 160
step_y = 100

template = """
    </comp>
        <comp lib="4" loc="(%d,%d)" name="ROM">
        <a name="contents">addr/data: 8 8
0
</a>
    </comp>
"""

result = ""
for i in range(0,4):
    for j in range(0,16):
        result += template % (start_x + step_x * i,start_y + step_y * j)

print(result)

观察所编写的代码，其实只是将最小单位的位置信息参数化，进行重复输出而已，编写起来应该比较简单。之后我们只需将生成的 XML 黏贴到源文件中 main 下合适的部分即可。最终效果如下：

可以注意到的是，此时我们还没有解决连线的大问题，因此我们就要使用 Tunnel 简化布线，Tunnel 元件直接不用 wire 连接在部件上组成最小单位，再进行自动化方法即可。效果如图，可以发现 Tunnel 的名字同样也参数化了，这样就可以通过有规律的 Tunnel 信号进行操作。

总结

自动化方法：

1.尝试

2.发现最小单位

3.编写生成代码

4.使用XML代码

CHALLENGE ! ! !

题面

黄小板同学暗中观察了公司负责人很久，觉得他搭建的电路性能实在太差，他提出只需要 64 个周期就能计算出 32 位无符号整数能表示的最大数位置上的斐波那契数的（最后 32bit），在完成搭建这样的电路后，公司负责人五体投地，宣布给黄小板开出了东门烤串无限量供应的实习工资，从此黄小板每日吃串，终于吃成了黄老板…

那么，这个电路是什么样子的呢？

注意：这道题是一个对你的挑战，需要一定的算法和工程能力，请谨慎思考，大胆尝试！

提交要求

思路

由于输入N为32位无符号数，用常规的计算方法需要O(n)的时间复杂度，当N很大时，计算周期将会远远超过64。因此需要另辟蹊径。

首先先观察到：
$$
fib(n) = 1 * fib(n-1) +1 * fib(n-2);fib(n-1) = 1 * fib(n-1) + 0 * fib(n-2),(n>2,n∈N;fib(n)为斐波那契数列的第n项)
$$
为什么第二个式子的右侧要多写一个0*fib(n-2)这么一个无用项？其实是为了同第一个式子右侧做对应，方便看出$$(fib(n),fib(n-1))$$与$(fib(n-1),fib(n-2))$之间的关系。

利用在《工科高等代数》这门课上学到的矩阵，可以得到以下关系式：
$$
\begin{bmatrix}fib(n)\fib(n-1)\end{bmatrix}=\begin{bmatrix}1&1\1&0\end{bmatrix}\begin{bmatrix}fib(n-1)\fib(n-2)\end{bmatrix} (n>2,n∈N)
$$
经过迭代就可以得到如下关系式：
$$
\begin{bmatrix}fib(n)\fib(n-1)\end{bmatrix}\begin{bmatrix}1&1\1&0\end{bmatrix}^2=\begin{bmatrix}1&1\1&0\end{bmatrix}^n\begin{bmatrix}fib(2)\fib(1)\end{bmatrix} (n>2,n∈N)
$$
因此只需要算出$\begin{bmatrix}1&1\1&0\end{bmatrix}$的(n-2)次幂即可，但是这样仍需要进行O(n)次矩阵相乘运算，时间复杂度并没有降低。注意到提交要求中的Hint:矩阵乘法的快速幂。

所谓快速幂，即是将一个数的幂运算拆解乘多个已运算得到的幂结果，进而减小运算次数，可将时间复杂度降低到O(logn)的方法。例如：若要计算a^13^一般的暴力方法即是用一个初始化为1的s存放循环相乘13次a的结果；但在快速幂方法下13==0b1101，则a^13^=a^0b1101^=a^0b1000^ * a^0b0100^ * a^0b0001^=a^8^ * a^4^ * a^1^=(((a^2^)^2^))^2^ * ((a^2^))^2^ * a,此时只需要大致计算log213次。因此，我们发现当计算两数相乘时，这两个数尽可能的越大，就越快接近最终结果。又因为幂运算的性质，观察到如果是偶次幂，将a^2n^直接转化为(a^n^)^2^则只需计算一次；如果是奇次幂，在偶次幂的基础上还得再多乘一次。由上述说明，定义power(a,n)为a^n^,则
$$
power(a,n)=power(a/2,n)^2*a (n为奇数)\power(a,n)=power(a/2,n)^2(n为偶数)\power(a,n)=1(n==0)
$$
由此可以得到C语言中递归代码如下：

inline int sqr(int a){//a^2
  return a*a;
}
int power(int a,int n){//a^n
	if(n==0){
		return 1;
	}
	return (n&1==1)?sqr(power(a,n/2))*a:sqr(power(a,n/2)); 
}

如此一来可以大量降低时间复杂度，实现64周期内算出答案的要求，只不过在题目中，a要看作是矩阵，而乘法运算要看成是矩阵相乘。因此先封装出矩阵相乘的子电路，便于后续调用。

但是问题有出现了在硬件设计中我们无法使用递归。因此需要将上述递归方法改写为迭代的方法。观察到我们一开始将13成二进制形式的方法，可不可以对n的二进制的每一位（从低到高）进行扫描，当该位为1时就将此时的a乘入ans中（显然a要随着扫描的进行而进行更新）；反之则不做处理。由此可以得到快速幂的迭代版本：

int power(int a,int n){//a^n
	int ans=1;//初始化
	while(n>0){//n==0时说明位数以移完32位或者已经没有是1的位了，此时即可跳出循环
	if(n&1==1){
		ans*=a;
	}
	a*=a;//a需要根据位数做相应的更新 
	n>>=1;//每次n右移将当前位推至第一位
	}
	//循环对a的次数n的二进制表示的每一位都进行扫描，若其为1则乘进ans中；若为0则无事发生。 
return ans;
}

有了上述代码就可以进行相应的电路设计了。

首先，为了初始化的方便，封装两个特殊矩阵：单位阵和乘子矩阵（即
$$
\begin{bmatrix}1&1\1&0\end{bmatrix}
$$
）

为了方便存储和初始化时以及代码中每轮循环的乘以乘子与否，再封装矩阵存储和矩阵选择两个子电路，方便计算电路的使用。

接着将代码中的循环和计算分别拆分为计时电路和计算电路：

在计时电路和计算电路中都有一个初始化器，它是由特定设置（最大值设置为1，Action on Overflow 设置为Stay at value）的counter计数器，这样一来在电路运行时会多出一个周期来进行初始化赋值（即第一个周期输出为0，之后输出均为1；输出到init在计时电路和计算电路结合多路选择器，实现初始化以及选择）。

再看计时电路，初始化后n被赋值为N-2（in），获取n的最低位n_lowest传给计算电路中作为ans选择不变(单位阵)还是乘以当前位上的乘子矩阵的依据，并将n同0进行比较得到freez信号，作为计算电路中计算是否停止的依据，注意：这里也要搭配多路选择器进行第一周期同之后周期的区分，因为第一个周期时，初始化与比较是同时进行的，如此得到的freeze信号将是0，会使计算电路在第一个周期停止工作，导致初始化并没有进入存储矩阵，而输入的第一位信息也没有成功进行计算，之后的值将全是0。之后计时电路将一直选择逻辑右移一位的n直到n等于0，发出freeze信号为0。

再看计算电路，左上端为初始化器，以及n_lowest和freeze。中间是两个“有限状态机”，上方是对于乘子矩阵的计算与存储，在初始化时选择最原始的乘子矩阵并存储赋值给a矩阵，之后每次都选择a^2^并存储赋值给a矩阵。下方的ans矩阵的计算与存储同理，根据n_lowest选择是单位阵（0）还是a矩阵（1），再同ans相乘得到ans‘矩阵在初始化部分，第一个周期选择单位阵，之后选择ans’矩阵并存储赋值给ans。

右上的输出电路根据freeze信号，当n！=0时一直输出0；当n==0时则输出ans_00 * fib(2)+ans_01 * fib(1),由于fib(1) == fib(1) == 1,所以即是输出ans_00+ans_01。

再在main板块中将计时电路同计算电路用电线相连即可得到所需电路。如下：

使用D触发器和与非门实现一个4人抢答逻辑电路

要求大致为

1.每个参赛者控制一个按钮，用按钮发出抢答信号（置1）

2.主持人控制一个按钮用于电路复位（置0）

3.开始比赛后，先按者将对应的一个发光二极管点亮，此后其余3人再按动按钮对电路不起作用

主要的实现难点在第三点，如何在有人抢答后将触发器的状态“锁住”，答案是：注意到题目给的与非门，联想到将状态锁住转变为将时钟信号锁住，即不发生变化。因此只要将4个触发器的反相输出~Q同时钟信号一同接到一个与非门的输入，输出再作为每个触发器的时钟信号即可。如此一来，在没人抢答时由于各触发器的反相输出均为1因此与非门的输出始终为系统时钟信号的反相，可以正常完成有人抢答就置1的功能，而一旦有人抢答了后，各触发器的反相输出中有0的存在将导致与非门的输出便会被置常值1，使得依靠时钟边沿触发的D触发器无法发挥作用，也就被“锁住”了。这样便实现了相应的需求。