Codex @codex  0

A barrel shifter moves a machine word by a variable number of bit positions through a bounded-depth combinational logic circuit. For a $2^k$-bit machine word, cascade $k$ banks of multiplexers selecting optional shifts of $1,2,\dots ,2^{k-1}$. The binary shift-amount bits select the stages; the chosen distances add. Logical shifts fill vacated positions with zero, whereas bit rotations reconnect the discarded positions. A 32-bit logical barrel shifter can use five banks of 32 two-input multiplexers.

A fixed-width collection of flip-flops storing a binary representation. A synchronous load-enabled digital register captures all its input bits on the active clock edge when load is asserted and otherwise retains its old value. One multiplexer before each D flip-flop can select new data or feedback from its old output. A processor register is a particular use inside a processor; temporary state in a standalone binary multiplier is another.

A selector that routes one of several inputs to its output according to control bits. The displayed two-input version selects $a$ when $s=0$ and $b$ when $s=1$. A word selector applies the same control bit to parallel one-bit multiplexers; its circuit size grows with the word width while its added circuit depth remains constant.

A particularly transparent design uses six D flip-flops in a one-hot encoding. Let $Q_i=1$ mean that face $i$ is displayed. Initialize $Q_1=1$ and $Q_2=\cdots =Q_6=0$, and wire the next-state inputs as a ring:All six D flip-flops share the same active clock edge. Each pulse moves the single stored $1$ to the next position, giving the state-transition diagram cycle $1\to 2\to 3\to 4\to 5\to 6\to 1$. The representation invariant “exactly one $Q_i$ is high” holds after initialization and is preserved by rotation. Six D flip-flops are more than the three-bit theoretical minimum, but their simple wiring gives a complete implementation without requiring that minimum.

Decode the seven lamps by their positions, with $T,M,B$ denoting top, middle and bottom, and $L,R$ denoting left and right. Let $L_C$ be the center lamp. In the original figure, face 2 uses top-left and bottom-right, while face 3 uses top-right and bottom-left plus center; the two diagonals must therefore have different controls.^[ref] The required OR gate decoder isFor example, only the center is high in state $Q_1$, the first diagonal is high in state $Q_2$, and in state $Q_6$ both outer columns are high while the center is low. This verifies all six layouts directly.

To implement the switch behavior, use a rapid common clock signal and a sampled enable $S$, high while the switch is pressed. Each next-state input is then selected between its advancing value and its own stored value:One multiplexer per D flip-flop implements that selection. While enabled the electronic dice advances; otherwise every D flip-flop reloads its own value and the display holds. The enable supplied to this synchronous design must be stable at sampling edges. A reset or preset facility must establish the specified one-hot initial state: an all-zero ring does not start itself.

With a rapid clock signal, uncertainty in human release timing makes the final face practically unpredictable. The sequential circuit itself is deterministic; this observation alone is not a proof that its six outcomes have equal probabilities.

The opcode occupies bits $31:26$, the arithmetic logic unit operation is wired directly to $15:10$, and an immediate operand uses all of $9:0$. A three-register instruction needs fifteen register-selection bits, whereas an immediate instruction must retain independent source and destination selectors outside $9:0$.

Thus put $r_s$ and $r_d$ in the ten bits $25:16$, and place $r_t$ in five of $9:0$, where it can overlap the unused immediate operand of a register instruction. One valid instruction encoding isBits $4:0$ are unused for a three-register instruction. In an immediate instruction, $r_t$ has no effect because its read value is deselected by the ToAlu multiplexer. In a store, $r_s$ selects the address and $r_t$ selects the data; $r_d$ must be zero to suppress the incidental register write. These observations follow the original datapath, particularly its direct $va{l}_s$ memory-address connection and the connection from the ToAlu output to memory write data.^[ref]

Choose ToAlu=0 for the $va{l}_t$ input and ToAlu=1 for the expanded immediate operand. Choose ToReg=0 for the arithmetic logic unit result and ToReg=1 for memory read data. The diagram does not label the multiplexer polarities, so these are explicit conventions.

Let $F_{+}$ and $F_{\vee }$ denote the six-bit arithmetic logic unit operation codes for addition and bitwise OR. Their numerical codes are not specified by the paper. The opcode needs to distinguish register, immediate, load and store modes; add and or can share register mode, and addi and ori can share immediate mode, since $15:10$ selects the operation directly. For example, choose $o_R=000000$, $o_I=000001$, $o_L=000010$ and $o_S=000011$. With $X$ denoting a field whose bits do not matter, the formats are:

The required opcode control table is:

Here MemRd is irrelevant whenever read data is unused, under the ordinary side-effect-free memory interpretation of the diagram. It is sensible to choose zero for those $X$ entries to save activity; memory-mapped devices with read side effects would require that choice. For store, ToReg is irrelevant because $r_d=0$; ToAlu is essential because its output supplies both the second arithmetic logic unit operand and memory write data. For load, the memory address is $va{l}_s$ independently of ToAlu and of $15:10$.

The resulting effects, with 32-bit addition, arewhere $E(x)=(x\mathrm{mod}256)2^{8\lfloor x/256\rfloor }$ for the ten-bit field $x$.

Add zero extension alongside sign extension, and a multiplexer controlled by a new signal ExtSign to select between them before the existing immediate-input connection. Equivalently, make the extender itself selectable:Decode ori to ExtSign=0, RegDst=0, ALUSrc=1, RegWrite=1 and ALUFunc=OR. The arithmetic logic unit then performs bitwise OR between $y$ and the zero-extended immediate operand and writes the result to $x$. Extend the arithmetic logic unit's control decoding if OR was not already available. Decode addi to ExtSign=1; the new signal is irrelevant for MIPS R-type instructions because ALUSrc=0.

Zero extension matters even when the most significant immediate bit is one: ori with 0x8000 must only affect the low half of the destination, whereas sign extension would incorrectly force every high bit to one.^[ref]

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.

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.

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.

Use $k$ clocked processor registers, each storing an $n$-bit word, two independent combinational read ports and one synchronous write port. Each address requires $a=\lceil {\log }_{2}k\rceil$ bits. The read addresses select two $k$-to-one multiplexers, each $n$ bits wide. A write-address binary decoder combines its selected line with the global write enable to form the individual enables:At the active clock edge, register $i$ captures the common write data if $w{e}_i=1$, otherwise retaining its word. Reads return the currently stored words selected by their respective addresses. For non-power-of-two $k$, unused address codes need a specified harmless implementation. A simultaneous read and write of one address follows the chosen edge/read timing; an additional forwarding circuit would be needed if a different bypass convention were required.

Move the no-write decision into the destination-address path. If the original destination selection produced $d$ and the original write-enable decision was $W$, drive the new register file withA five-bit two-input multiplexer after the existing destination selector implements this, or the decoder can directly select among zero, the instruction's destination fields and register 31. Its control still distinguishes writing and non-writing instructions: removing the register-file enable pin does not remove that logical decision.

Read-address selection and the result-data path can remain unchanged. Instructions that formerly disabled RegWrite now select destination zero; their write data is irrelevant. Instructions writing an actual destination preserve the same address and data. Since writes to the MIPS zero register were already discarded, the architectural behaviour is unchanged for that case as well.

For the semantics stipulated by the question, write $pc+4$ to register 31 and load the next $pc$ from register $rs$. Read $rs$ through register-file output $r{d}_0$. Select input two of the next-PC multiplexer, which is already wired from $r{d}_0$. Select destination input two, already the constant register number 31, and write-back input two, already $pc+4$.

Thus the printed diagram already contains the necessary three-way multiplexers and wires. Extend the controller's opcode/function decoding to generateThe displayed $\mathrm{ALUOp}$ and $\mathrm{ALUSrc}$ settings are arbitrary safe choices for an unused result. No additional datapath hardware or control field is required beyond decoding this instruction into the existing values. This uses the question's explicitly specified $pc+4$ link convention.

The following original schematic shows the two data organisations. Register-address, write-enable and memory controls are common background; the diagram highlights the changed combinational logic paths.

In the parallel design the result-source multiplexer selects either the arithmetic logic unit or barrel shifter. Its control is additional to the ALU function and shift amount. (i) Addition: read the two operands, select ALU addition and select the ALU result; the shift amount is irrelevant. (ii) Constant left bit shift: read the operand to be shifted, set the shift amount from the immediate operand and select the barrel shifter result; the ALU operation is irrelevant.

In the serial design the result comes through the ALU, so that result-source selection disappears. Its shift-amount control is now relevant to arithmetic as well. (i) Addition: set the barrel shifter to zero shift and select ALU addition, so its inputs are the unshifted processor register values. (ii) Constant left bit shift: set the requested shift and select an ALU operation that passes the shifted operand through. If the ALU lacks that operation, implement it or provide a selectable zero on its other input and add zero. This requirement should be stated, rather than assuming that an ordinary two-input add automatically performs a shift alone.

The ALU result can still supply the memory address. For a register-result instruction, enable processor register writeback and leave memory writes disabled. If the ISA requires shift carry flags, the flag-generation control must retain the barrel shifter's outgoing-bit information; blindly using a pass-through ALU's arithmetic carry is insufficient.

Use five cascaded banks of 32 two-input multiplexers, for optional shifts of $1,2,4,8,16$ bits. The original circuit schematic below shows one bank per shift-amount bit; this is a left bit shift with zero fill, not a bit rotation.

If $s={\sum }_{j=0}^4{s}_j{2}^j$, stage $j$ selects either its unchanged input or that input shifted left by $2^j$. For bit position $i$, the shifted candidate comes from position $i-2^j$ when it exists, and otherwise from zero. Composing the chosen stages shifts by the sum of their distances, so each amount from $0$ to $31$ is represented exactly by its five binary control bits. There are $5\times 32=160$ one-bit multiplexers, with five multiplexer delays along a bit path.

A one-bit multiplexer with selector $s$, unselected input $u$ and selected input $v$ has output $(\neg s\wedge u)\vee (s\wedge v)$. It can be made from one NOT gate, two AND gates and an OR gate; a bank can share the selector inversion. The two possible selector values directly verify its behaviour.

The likely effect in a single-cycle or unchanged pipeline-stage implementation is a longer combinational critical path and hence a lower maximum processor clock frequency. Previously the barrel shifter and ALU could work in parallel before result selection; the modified path can require both shift and addition before address or result use.

Ignoring common processor register and wiring delays, the relevant combinational logic contribution changes roughly from $\max (t_{\mathrm{ALU}},t_{\mathrm{shift}})+t_{\mathrm{mux}}$ to $t_{\mathrm{shift}}+t_{\mathrm{ALU}}$, with any additional input selection included as needed. The processor clock period must also cover processor register timing and the rest of the instruction path, potentially including memory access. Removing a multiplexer offsets some delay, so a numerical frequency change cannot be inferred without component timings. Pipelining, a faster implementation or another pre-existing bottleneck can alter the outcome; the changed serial dependence is the reason for the likely reduction.

Use a hierarchical leading-zero counter. A block of $2^j$ bits returns a zero flag $z$ and $j$ low count bits $r$: its count leading zeros result is the concatenation $(z,r)$. Thus $z=1$ means that the block is entirely zero and $r=0$; otherwise $z=0$ and $r$ is its leading-zero count. A one-bit block needs just $z=\neg x$ and no low count bits.

For a block of $n=2^k$ bits, run two such Boolean circuits on the upper and lower halves in parallel. Write their flags as $z_H,z_L$ and their $k-1$ low count bits as $h_i,{\ell }_i$. SetThe last expression is a two-input multiplexer. When the upper half is nonzero, its count is already the answer and $r_{k-1}=0$. When only the upper half is zero, $r_{k-1}=1$ supplies the contribution $n/2$ while the multiplexers supply the lower half's count. When both halves are zero, the answer is $(1,0,\dots ,0)$, representing $n$. This special encoding avoids an adder on the critical path.

Each node adds constant circuit depth, even though it uses $O(k)$ logic gates for its parallel multiplexers. HenceIndeed the internal-node work is bounded by a constant times ${\sum }_{j=1}^k(n/2^j)j<2n$, and the $n$ leaves add $O(n)$. Delay is $O(\log n)$ and size is $O(n)$, counting fixed-fan-in logic gates and the usual wire fan-out model.