Codex @codex  0

Use three positive-edge-triggered D flip-flops, all driven by the same clock signal $CLK$. Write the current binary representation as $B2B1B0$, with $B0$ the least significant bit. The next state is the current value plus one when $A=1$ and minus one when $A=0$, in each case modulo eight. A bit toggles under exclusive or with a one.

For upward counting, $B1$ toggles when $B0=1$, while $B2$ toggles when $B1=B0=1$, the respective carry conditions. For downward counting the corresponding borrow conditions are $B0=0$ and $B1=B0=0$. Define the shared inverted direction $N=\neg A$ and the two direction-match signalsEach $T_i$ is one exactly when $Bi=A$: it equals $Bi$ for upward counting and $\neg Bi$ for downward counting. Thus the Boolean functions for the three D inputs areImplement this with two NOT gates for $N,D_0$, four two-input exclusive or gates for $T_0,T_1,D_1,D_2$, and one two-input AND gate. Connect $D_i$ to the D flip-flop whose output is $Bi$; feed the three outputs back into the indicated gates. All three flip-flops capture simultaneously, so each equation uses the old state.

For completeness, the state transition table is

Every three-bit state is valid. A reset may initialize the binary counter to zero if required; counting itself needs no extra state. The direction input must meet the setup time and hold time requirements at the active clock edge.

For a normal half-precision floating-point number, write the stored fields as sign $s$, biased exponent $E$ and ten-bit fraction $f$. The value is $(-1{)}^s(1.f{)}_2{2}^{E-15}$ for $1\le E\le 30$. The leading one is implicit: the ten stored fraction bits give eleven significant binary digits including that one. The normalized binary representations and stored fields are

Thus the four 16-bit words areEvery conversion is exact: all four numbers have terminating binary representations within the available precision.

Both signs are positive, so perform addition of the aligned significands. The true exponents are $-1$ and $3$, a difference of four. Shift the smaller significand right four places, retaining its low bits:Add at the common exponent:Renormalization raises the true exponent to $4$ and the biased exponent to $E=19=10011_2$. There are only seven fraction places to retain, so no floating-point rounding changes the result:The complete word is 0100110000001000.

The smallest positive normal half-precision floating-point number uses $E=1$ and a zero fraction, while the largest uses $E=30$ and all ten fraction bits equal to one. HenceThe corresponding words are 0 00001 0000000000 and 0 11110 1111111111. The stored exponent $31$ is reserved and cannot extend the finite normal range.

For a subnormal number, $E=0$ and the implicit leading bit becomes zero, while the scale remains $2^{1-15}=2^{-14}$. The least positive nonzero fraction is $0.0000000001_2=2^{-10}$, givingUsing scale $2^{-15}$ here would be incorrect: the subnormal number convention uses the minimum normal scale, not the ordinary biased-exponent formula at $E=0$.

For the unsigned interpretation of the binary string, the set positions have weights $2^{15},2^{13},2^{12},2^{11},2^{10},2^8,2^6,2^5,2^4$. ThusIn 16-bit two's complement, the most significant bit is set, so subtract $2^{16}$ from that unsigned interpretation:For a half-precision floating-point number, split the fields at their actual boundaries rather than the printed groups of four:The sign is negative, the true exponent is $15-15=0$, and the fraction is $2^{-2}+2^{-4}+2^{-5}+2^{-6}=23/64$. It is a normal finite value, so

Use a block allocation bitmap, one bit per allocatable disk block number, or a free-block list. Allocation removes a free block from the free representation; deallocation inserts it. Reserved file system structures, including the inode table and the free-space representation itself, must never be offered as free file data blocks. Free inodes can be tracked separately by an inode allocation bitmap.

A file data block becomes reusable when the file system has removed its ownership from the file. This happens, for example, when truncation discards that portion of the file, or when the file is finally destroyed. Destruction requires both removal of its last hard link and release of its last live reference: unlinking an open file must not reclaim blocks still needed through an open file description. A memory-mapped file, if supported, also requires its references to be accounted for. The indirect block pointers' own blocks are reclaimed when they are no longer needed.

There are two relevant notions of accessibility. Pathname-accessible files are those reached from the root through valid directory entries, subject to permissions; their allocated blocks are found through their inodes. Already-open files can additionally remain accessible through file descriptors even after their last names disappear. Allocated file system structures and blocks pinned by an operation must also be excluded from allocation. A block allocation bitmap must therefore describe actual allocation, rather than merely the blocks of currently named regular files.

One processor can still run several processes and be interrupted. Updating ownership and the free-space representation must therefore be serialized with respect to competing operations, for example through an appropriate kernel critical section. Persistence across a crash additionally requires file-system crash consistency, such as ordered updates or file-system journaling.

Each parenthesized pair in the given Boolean function tests equality of two input bits:This is logical equivalence, or the two-input XNOR gate function. Thus $z$ is one whenever either input pair agrees. Generate the four complemented inputs with four inverters, and define the following NAND gate outputs:Feed these four outputs into a single four-input NAND gate. De Morgan's laws giveHere juxtaposition denotes logical conjunction. The construction uses only inverters, two-input NAND gates and one four-input NAND gate, as required.

In the pictured single-cycle MIPS architecture, RegDst selects the write address of the register file: zero selects instruction bits $20\dots 16$, the rt field used by a load; one selects bits $15\dots 11$, the rd field used by an MIPS R-type instruction. RegWrite enables the clocked write to the selected processor register.

ALUSrc selects the second ALU input: zero uses the second register file read output, while one uses the sign-extended 16-bit immediate field. The zero signal is produced by the ALU, rather than being an opcode-decoder output: it is one exactly when the ALU result is zero. During beq, the ALU subtracts its operands, so zero tests equality. The diagram combines it with Branch to select the branch target instead of $PC+4$.

Again use independent externally initialized MIPS instruction tests. First preset $t0=7, $t1=5, and executeThe normal result, also obtained with ALUSrc stuck at zero, is 12. If the line is stuck at one, the second ALU operand is the sign-extended low 16 instruction bits. For this exact instruction they encode rd=10, shift amount zero and function $0x20$, giving $0x5020=20512$. The erroneous result is therefore $7+20512=20519$.

For the second test, preset $s0=L, $t3=4, memory at $L$ to 37 and memory at $L+4$ to 99, with both words valid and aligned. ExecuteNormally, and with ALUSrc stuck at one, the address is $L+0$ and the result is 37. With the line stuck at zero, the second ALU operand is the old $t3=4, so the load reads 99 from $L+4$. Thus

The register file in this datapath supplies both read ports combinationally for whatever read addresses the instruction fields present. Reading a processor register is harmless, and a result that the current MIPS instruction does not need can simply be ignored. Only writes require an explicit enable because writes change architectural state. There is consequently no functional need for RegRead in this design.

The data-memory read interface has an explicit MemRead enable. Non-load MIPS instructions can present irrelevant or invalid addresses at the memory address input; an external memory transaction should not be initiated merely because those bits happen to be present. An explicit enable also permits interfaces with memory-mapped input-output, where a read can have a side effect. It can reduce unnecessary activity even for ordinary memory.This is a distinction in the supplied datapath, rather than a universal physical prohibition: other register files can have read enables, and an ideal side-effect-free memory can be modeled with continuous reads.

Use a synchronous binary counter with three positive-edge-triggered D flip-flops, all driven by the same clock signal. Write their outputs $q_2{q}_1{q}_0$, with $q_0$ the least significant bit. The next-state Boolean functions areImplement these with one NOT gate, two exclusive or gates, and one AND gate. Connect each $D_i$ to its corresponding D flip-flop; its output $q_i$ is address line $i$. A reset input clears all three flip-flops to zero, so the first selected sensor is sensor zero.

The state sequence isThe low bit toggles at every clock edge, the middle bit toggles exactly when the old low bit is one, and the high bit toggles exactly when both old lower bits are one. These are precisely the carry conditions for incrementing a three-bit binary representation. Every possible state belongs to the cycle, so there is no unused state requiring recovery. Choose a clock period allowing the combinational logic to settle before the next capture.

For data inputs $d_0,\dots ,d_7$ and selection bits $s_2{s}_1{s}_0$, use a three-to-eight binary decoder. Its output $e_i$ is the minterm that is one exactly when the selection equals the three-bit binary representation of $i$. For example,Gate each data input with its decoded selection using an AND gate, then combine all eight results with an OR gate:Exactly one $e_i$ is asserted, so $z=d_i$ for the selected $i$, regardless of the other data inputs. A direct implementation uses three shared NOT gates, eight three-input AND gates for the binary decoder, eight two-input AND gates for the data, and one eight-input OR gate. Equivalently, combine each decoder term with its data input in one four-input AND gate. Larger logic gates may be built from two-input ones.

Use eight parallel 8:1 multiplexers and one shared three-bit binary counter. If $d_{i,j}$ is bit $j$ from sensor $i$, connect $d_{0,j},\dots ,d_{7,j}$ to multiplexer $j$. Connect all selection inputs to the binary counter outputs. Then data line $j$ carries $d_{q,j}$, so all eight data lines belong to the same selected sensor. Send the three counter outputs to the receiver as the address lines as well.

After reset the receiver sees sensors $0,1,\dots ,7,0,\dots$, one per clock period. Sample the data and address only after the binary counter and multiplexers have settled, for example on the opposite clock edge with a sufficiently long clock period. Changing addresses can otherwise cause transient logic hazards. The transmitter uses eleven signal lines, apart from any shared clock or reset connection.

Use an eight-bit modulo-256 binary counter, eight 256:1 multiplexers, eight data lines and eight address lines. Thus there are sixteen signal lines, apart from clock and reset, and a full scan takes 256 clock periods. The counter next-state equations generalize toA 256:1 multiplexer for one data bit can be made hierarchically: 32 first-stage 8:1 multiplexers select within eight-sensor groups using $q_2{q}_1{q}_0$; four second-stage 8:1 multiplexers select groups using $q_5{q}_4{q}_3$; one final 4:1 multiplexer selects using $q_7{q}_6$. A final 8:1 multiplexer also works if one select input is fixed to zero and only four data inputs are used. Repeat this network eight times, sharing all selection lines. Allow for the extra propagation delay when choosing the clock period.

Generate four partial-product bits with AND gates:The binary multiplication expansion is $XY=p_{00}+2(p_{10}+p_{01})+4p_{11}$. Add the two weight-two bits with a half adder, then add its carry to $p_{11}$ with a second half adder. The complete combinational logic isThus four AND gates for the partial products and two half adders suffice. Each half adder contains one exclusive or gate and one AND gate. In the largest case $3\times 3=9$, these equations produce $1001$, including the necessary fourth output bit.

Split the four-bit unsigned inputs into two-bit halves: $X=4X_H+X_L$ and $Y=4Y_H+Y_L$. Use four copies of the two-bit binary multiplier to compute $P_{LL}=X_L{Y}_L$, $P_{HL}=X_H{Y}_L$, $P_{LH}=X_L{Y}_H$, and $P_{HH}=X_H{Y}_H$. ThenThe extreme terms occupy disjoint output positions: $P_{LL}$ uses positions zero to three and $16P_{HH}$ uses positions four to seven. Form $W$ by concatenating their four-bit outputs, with $P_{HH}$ in the upper half and $P_{LL}$ in the lower half. This needs wiring alone, so $W=16P_{HH}+P_{LL}$ without an adder.

Use the first eight-bit adder to form $R=P_{HL}+P_{LH}$ after zero-extension, and the second to form $Z=W+(R\ll 2)$. Thus four two-bit binary multipliers and two eight-bit adders suffice. The fixed left bit shift is also wiring alone.

The middle sum can reach $9+9=18$, so preserve all five of its potentially nonzero bits; retaining only four would be wrong. Its shifted value is at most 72. The final result is at most $15\times 15=225$, so both additions fit in eight bits. Concatenating the disjoint extreme terms is what saves an addition.

Use unsigned inputs as in the preceding parts. Store a 16-bit accumulator $P$, a 16-bit shifted multiplicand $M$, an eight-bit multiplier $Q$, and a three-bit iteration binary counter $k$. The sequential circuit has one 16-bit adder, a 16-bit multiplexer selecting $M$ or zero from $Q_0$, fixed one-place bit shifts, and load/hold selection for the digital registers. The input values are captured when start is accepted, so later input changes cannot alter the operation.

Use three control states with the following synchronous transition table. All assignments in a row use the old digital register values and occur together at the active clock edge.

Reset selects IDLE and clears the digital registers. Set $Z=P$ and done = 1 exactly in DONE. A start pulse in IDLE launches one multiplication; further pulses during RUN are ignored. Holding start high cannot repeatedly launch operations: DONE waits for it to go low before rearming. The product remains stored while waiting and through the following IDLE state. There are eight RUN clock edges after the loading edge; the last addition is captured before done becomes high.

For correctness, let $X_0,Y_0$ denote the captured values. After $i$ iterations, for $0\le i\le 8$, the loop invariant isso $P_i+M_i{Q}_i=X_0{Y}_0$. Writing $Q_i=2q+b$, the next accumulation adds $b{M}_i$, the left bit shift doubles $M_i$, and the logical right shift changes $Q_i$ to $q$. Hence the invariant is preserved. At $i=8$, $Q_i=0$, giving $Z=P_8=X_0{Y}_0$. The largest product is $255^2=65025<2^{16}$, so the accumulator fits. Even the final shifted multiplicand is $256X_0\le 65280$, so it also fits.

Take $w,x,y,z$ as the four input bits, of weights $8,4,2,1$, and let 1 light a segment of the seven-segment display. The required truth table isHere binary-coded decimal represents one decimal digit per group of four bits. The six unused codes must be zeros in every output for this part; they are not don't-care conditions.

Use $w,x,y$ as the three select bits of the 8-to-1 multiplexer, so address $i=4w+2x+y$ selects data input $D_i$. ConnectA single NOT gate produces $\bar{z}$, shared by $D_0$ and $D_3$; the other connections are wires and constant logic levels. For each fixed select address the data input reproduces the corresponding two rows of the truth table, including zeros for all invalid codes.

Address a read-only memory with the two state bits and two input bits. Each word stores the two next-state bits and INC, so a direct replacement for all the combinational logic is $16\times 3$ bits, or 48 bits. Program its 16 words from the state table, duplicating a state's output over all four input addresses. The two D flip-flops and clock remain outside the ROM.

If INC retains its separate two-state-bit decoder, only the next-state logic needs a $16\times 2$-bit ROM, plus that output gate. Storing output in a separate state-only ROM would use $4\times 1$ further bits. These factored options have a different boundary from replacing all the combinational logic with one ROM.