Program Counter Design: Part 1

1/19/2022

What is a Program Counter?

The Program Counter is the first part of my computer design that interacts directly with the control logic system which will eventually allow me to program the computer to create a meaningful output. The Program counter is the component that keeps track of the current address, which is linked to the current instruction being executed (as dictated by the software). The program counter can either increment by 1 (going to the next address), or jump to a certain address (in the case of a jump instruction).

Basic Fetch Instruction Flow:

The execution of instructions within the computer design follows a procedure to ensure accurate and efficient operation. This procedure is executed on the falling edge of each clock cycle. Each particular OP Code (indicates functionality of call such as add) will route the CPU to a particular section of the computer which is governed by a separate four-bit instruction counter, which will be further detailed in a subsequent analysis of the control logic.

The basic procedure consists of the following steps:

1. The Program Counter transfers the data to the Address Register, which indicates the current line of code being executed.
2. The data from RAM is then transferred to the Instruction Register, utilizing the Address Register as the access address, to indicate the current instruction to be executed.
3. The Program Counter is incremented to access the next line of code for the subsequent fetch cycle.
4. The operation dictated by the OP Code of the current instruction is executed.
5. The process returns to step 1 to execute the next instruction.

It is apparent from this basic flow that the Program Counter must possess the capability to be selectively disabled or enabled to prevent unnecessary incrementations during each fetch cycle. Additionally, the Program Counter must be able to output to the bus for transfer to the Address Register. This functionality is particularly important for jump instructions that allow for the software implementation of loops and functions. Furthermore, it is important to note that this is just a basic flow and there may be additional steps or considerations that may be needed to be taken into account.

The two most popular methods of implementing a Program Counter are by cascading JK flip Flops or a system of two registers feeding in and out of a half adder.

Method 1: JK Flip Flop

The JK flip flop is an extension of the SR Flip Flop/Latch that was discussed in a previous post. In short the SR Latch has two inputs (S and R). When S (set) goes high and R (reset) is low a high value is latched to the output, and when R (reset) goes high and S (Set) goes low a low value is latched at the output. When both are low the previous value is latched (remembered), and when both are high this is known as a forbidden state.

The conversion of an SR latch to an SR flip flop can be achieved by simply ANDing each input with a clock input signal. When the clock is low, the circuit will reflect the state of the latch, as the input will be 00 (any bit ANDed with 0 is 0; X0=0). Conversely, when the clock is high, the SR latch becomes active and directly follows the input S and R (any bit ANDed with 1 is the original bit; X1=X). Additionally, this circuit can be simplified by utilizing NAND gates in place of AND gates.

However, the SR Flip Flop still suffers from the shortcoming of the forbidden state (11), where both Q and Q’ are set to 1, which is not a valid state. The solution to this issue is the JK Flip Flop, which differs from the SR Flip Flop by looping the outputs (both Q and Q’) back to the input. This means that S and R still function the same way, and the latch state still occurs for 00. However, now the previously forbidden state (11) has functionality. When the input is 11 the output is toggled (a value of 1 becomes a 0, and 0 a 1). This is because each NAND gate takes feedback from the output (with J taking Q’ and K taking Q). This feature, in conjunction with the capability to retain state, provides greater control over the output and allows for the implementation of more complex logic circuits such as a Program Counter.

The JK Flip Flop divides the clock input by 2 by toggling its output on each rising edge of the clock input. This means that for every two rising edges of the clock input, the output of the JK Flip Flop will change state once. Since the output is changing state once for every two rising edges of the clock input, the frequency of the output is half of the clock input.

To further illustrate this, let’s consider a clock input with a frequency of 8 Hz and a JK Flip Flop connected to it. The clock input will generate 8 rising edges per second, but the output of the JK Flip Flop will only change state 4 times per second because it toggles on each rising edge of the clock input. Therefore, the output frequency of the JK Flip Flop is 4 Hz which is half of the clock input frequency of 8 Hz.

This concept is particularly useful when looking at the expected output of a counter:

000
001
010
011
100
101
110
111

The JK Flip Flop, when utilized as a binary counter, leverages its toggling behavior on each rising edge of the clock input to divide the frequency of the input by a factor of 2. By cascading multiple JK Flip Flops, the output frequency is further divided by successive powers of 2, with each stage of the cascade representing a specific bit in the binary representation. The least significant bit (LSB; rightmost bit) is represented by the first stage, and the most significant bit (MSB; leftmost bit) is represented by the final stage. This allows for a clear and intuitive representation of the binary count, with the LSB toggling on each clock cycle, the second bit cycling every 2 clock cycles, and the MSB cycling every 4 clock cycles. This behavior can be easily visualized through the progression of the binary representation, with each stage of the cascade representing a higher order bit.

Method 2: Registers and Half Adder

To me the simpler solution to the problem is the use of two registers and a half adder to increment the PC. The Half adder was described in a previous post. In short the half adder takes in two inputs, and outputs the binary addition of the two numbers with both an output bit and a carry bit.

This approach utilizes the concept of a pipeline register, comprising of a feed-out register and a feed-in register. The feed-out register serves as the source register that provides the input for the half adder, which performs binary addition on the contents of the two registers. The resulting output is then captured by the feed-in register. The critical aspect of this methodology is the utilization of inverse clocks for the two registers, thus enabling the feed-in register to capture the output from the half adder during a high state, while the feed-out register provides input to the half adder during a low state. This results in a seamless and efficient increment of the program counter (PC).

When a signal of zero is applied to the carry-in input of the half adder, the value remains unchanged between the feed-out and feed-in registers, effectively preventing an increment to the address. However, when a signal of one is applied to the carry-in input, the output of the feed-out register is incremented by one on the falling edge of the clock, and subsequently passed to the feed-in register on the rising edge, thus effectively incrementing the address. This approach can be viewed as a means of enabling or disabling the increment functionality of the program counter, with the carry-in signal serving as a “count enable” signal.

Furthermore, the system employs combinational logic that controls the input of the feed-in register. This logic includes a reset signal and a load signal, where a high reset signal results in a value of 0 being passed to the feed-in register, and a high load signal results in the value from the bus being pulled into the feed-in register. When both reset and load signals are low, the value from the half-adder circuit is passed to the feed-in register unaffected.

From here through the use of Boolean Algebra techniques the truth table can be modeled using two OR gates and two AND gates (simplified as a three input AND gate). Then using simplification techniques described in other posts this circuit can be converted to a system of all NOR gates to minimize the number of transistors needed (from 10 to 7 transistors):

Which Method I Utilized in My Design

After conducting a thorough evaluation and experimentation, it was determined that Method 2 was the superior solution for my particular implementation. The use of a feed out register and feed in register, in conjunction with a half adder and combinational logic, presented several advantages over the alternative approach. Firstly, the implementation of Method 2 is easier to comprehend and allows for easier debugging and troubleshooting in case of any errors. Additionally, the ability to load a value from the bus and reset the value with this method is more straightforward and does not depend on the clock of a previous output, as in Method 1. Lastly, the design of Method 2 was more cost-effective and efficient for my design, as it is constructed using the registers that I have already designed and ordered, requiring only the design of a half adder circuit and combinational logic to control the input of the feed in register.