Automata, Snippets

Finite State Machine: Implementing Binary Adder in Java

Leave a comment

A Finite State Machine (FSM) is a mathematical model of computation that transitions between a finite set of states based on input. One elegant application is a binary adder — where two binary strings are added bit-by-bit from right to left, with the FSM managing carry propagation between two states: no-carry (state 0) and carry (state 1). In this post, we implement this FSM-based binary adder in Java, complete with state transition functions and step-by-step output.

Binary Adder using Finite State Machine in Java

import java.io.*;

class BinaryAdderFSM {

    /**
     * Next-state function: given two bits and current carry state,
     * returns the new carry state after addition.
     * State 0 = no carry, State 1 = carry
     */
    static int nextCarryState(char bitA, char bitB, int currentCarry) {
        // If we are in no-carry state, only move to carry if both bits are 1
        if (currentCarry == 0) {
            return (bitA == '1' && bitB == '1') ? 1 : 0;
        }
        // If we are in carry state, stay in carry unless both bits are 0
        else {
            return (bitA == '0' && bitB == '0') ? 0 : 1;
        }
    }

    /**
     * Output function: given two bits and current carry state,
     * computes the result bit (sum bit) for this position.
     */
    static int computeResultBit(char bitA, char bitB, int currentCarry) {
        // Both bits same in no-carry state: sum bit is 0
        if (currentCarry == 0 && ((bitA == '0' && bitB == '0') || (bitA == '1' && bitB == '1'))) {
            return 0;
        }
        // Bits differ in no-carry state: sum bit is 1
        if (currentCarry == 0) {
            return 1;
        }
        // Both bits same in carry state: sum bit is 1
        if (currentCarry == 1 && ((bitA == '0' && bitB == '0') || (bitA == '1' && bitB == '1'))) {
            return 1;
        }
        // Bits differ in carry state: sum bit is 0
        return 0;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        System.out.println("Enter First Binary String:");
        String binaryA = reader.readLine();

        System.out.println("Enter Second Binary String:");
        String binaryB = reader.readLine();

        int stringLength = binaryA.length();
        int[] resultBits = new int[stringLength]; // stores result bit for each position
        int carryState   = 0;                      // initial FSM state: no carry

        // Process bits from right (least significant) to left (most significant)
        for (int i = stringLength - 1; i >= 0; i--) {
            char bitA = binaryA.charAt(i);
            char bitB = binaryB.charAt(i);

            int resultBit = computeResultBit(bitA, bitB, carryState);
            carryState    = nextCarryState(bitA, bitB, carryState);

            System.out.println(bitA + "+" + bitB + " => State=" + carryState + " ResultBit=" + resultBit);
            resultBits[i] = resultBit;
        }

        // Print final result
        System.out.println("Result:");
        for (int i = 0; i < stringLength; i++) {
            System.out.print(resultBits[i]);
        }
        System.out.println();
        System.out.println("Final Carry State: " + (carryState == 0 ? "No Carry" : "Carry"));
    }
}

How the Code Works

  1. Two binary strings are read — binaryA and binaryB — which must be of equal length.
  2. The loop iterates from the rightmost (least significant) bit to the leftmost, simulating how binary addition works from LSB to MSB.
  3. computeResultBit() applies the FSM output function: the result bit is derived from the two input bits and the current carry state using XOR-like logic.
  4. nextCarryState() applies the FSM transition function: carry becomes 1 if the sum of the two bits plus the current carry exceeds 1.
  5. The result bits are stored in resultBits[] and printed in order from MSB to LSB.
  6. The final carry state indicates whether there is an overflow carry beyond the most significant bit.

Sample Output

Enter First Binary String:
101011
Enter Second Binary String:
100110

1+0 => State=0 ResultBit=1
1+1 => State=1 ResultBit=0
0+1 => State=1 ResultBit=0
1+0 => State=1 ResultBit=0
0+0 => State=0 ResultBit=1
1+1 => State=1 ResultBit=0

Result:
010001
Final Carry State: Carry

Output Explanation

  1. The program processes the two binary strings 101011 and 100110 from right to left, one bit pair at a time.
  2. At each step it prints the two bits, the resulting carry state, and the output result bit for that position.
  3. The accumulated result bits form 010001, which is the binary sum of the two inputs ignoring the final carry.
  4. The final carry state Carry indicates the mathematical sum exceeds the bit-width — in full precision a leading 1 bit would be prepended to give 1010001.

See Also

Conclusion

This FSM-based binary adder elegantly demonstrates how finite state machines can model arithmetic operations. The two-state machine (no-carry and carry) cleanly separates the transition logic from the output logic, making the code easy to reason about. Once you understand this pattern, you can extend it to subtraction, multi-bit adders, or any sequential arithmetic circuit.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.