The Gateway to Computer Science Excellence
+2 votes
674 views
Designer mealy machine to decrement a binary number by 1
in Theory of Computation by Active (1.5k points) | 674 views

2 Answers

+2 votes
Best answer

First, let's see some inputs and their corresponding outputs to get an idea of what we want to build.

Input Output
100110 100101
111111 111110
001001 001000
110000 101111

Things to note here:

Starting from the LSB of the input, we change every 0 we see to a 1, and on encountering the first 1, we change it to a 0. Then the remaining bits remain the same.

e.g. when the input is 10100, we get the output 10011(subtracting 1 from the input). The 0 at the LSB is turned to a 1, then the next 0 is also turned to a 1, then on the first 1 (from LSB side), we change it to a 0. The remaining bits (up till MSB) remain the same.

This gave me the idea for the machine:

Here state q1 flips all the bits until we get a 1. On a 1 we move to state q2, where all the inputs bits remain the same.

NOTE: The input is provided to the machine from the least significant bit. i.e., scanning of the input is from left to right.

P.S. All all 0 input, the machine will give all 1s.

by Boss (17.8k points)
selected by
0 votes
I will encourage you to solve the problem and its quite interesting, nevertheless, I will provide you the hints just to help you out in decoding the logic.

decrementing 1 from a binary number is equivalent to adding it's  2's complement to it.

Let's take an example:

Let a 4-bit binary number, A=0111 (+7),

add 4-bit  -1 to it, lets call it B=1111(-1)

A+B=0110,

Notice is LSB is 1, its directly switched to 0.

Decreasing the result further by 1, we get +5, as, 0101.

So if LSB is 0, and second bit from Left is 1, make it 0 and Leftmost bit as 1.

Generalizing it, if k bits from left are 0 and k+1th is 1 then make all the k bits 1 and k+1th bit will become 0 from 1.

Extrapolate the result on various examples and ones you understand the logic, try to design the machine by your own.
by Junior (941 points)

No related questions found

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,324 answers
198,406 comments
105,170 users