Incremental Mealy Machine
A Mealy machine that can be constructed, so that the output string is increased, in magnitude, by 1 .
This machine is called the incrementing machine. Following is how to construct the incrementing machine.
Before the incrementing machine is constructed, consider how 1 is added to a binary number.
Since, if two numbers are added, the addition is performed from right to left, so while increasing the binary number by 1, the string (binary number) must be read by the corresponding Mealy machine from right to left,and hence the output string binary number will also be generated from right to left.
Consider the following additions
a)
100101110
b) 1001100111
+1
+1
100101111
1001101000
It may be observed from the above that
If the right most bit of binary number, to be incremented, is 0, the output binary number can be obtained by converting the right most bit to 1 and remaining bits unchanged.
If the right most bit of binary number is 1 then the output can be obtained, converting that 1 along with all its concatenated 1's to 0's, then converting the next 0 to 1 and remaining bits unchanged.
The observations (a) and (b) help to construct the Incrementing (Mealy) machine.
A Mealy machine that can be constructed, so that the output string is increased, in magnitude, by 1 .
This machine is called the incrementing machine. Following is how to construct the incrementing machine.
Before the incrementing machine is constructed, consider how 1 is added to a binary number.
Since, if two numbers are added, the addition is performed from right to left, so while increasing the binary number by 1, the string (binary number) must be read by the corresponding Mealy machine from right to left,and hence the output string binary number will also be generated from right to left.
Consider the following additions
a)
100101110
b) 1001100111
+1
+1
100101111
1001101000
It may be observed from the above that
If the right most bit of binary number, to be incremented, is 0, the output binary number can be obtained by converting the right most bit to 1 and remaining bits unchanged.
If the right most bit of binary number is 1 then the output can be obtained, converting that 1 along with all its concatenated 1's to 0's, then converting the next 0 to 1 and remaining bits unchanged.
The observations (a) and (b) help to construct the Incrementing (Mealy) machine.
No comments:
Post a Comment