Two Input Muller's C-Element
Anand P Paralkar
I wrote two pieces of code for a problem that requires the implementation
of a two input Muller's C-element. For those of us who dont know what a
Muller's C-element is; The Muller's C-element is a state machine which has
the following state table:
in1 in2 out
0 0 0
0 1 P
1 0 P
1 1 1
P : Previous value of out
The two codes are:
-----------------------------------------------------------------
Code1:
entity muller_c is
port (in1, in2 : in bit;
mout : out bit);
end entity muller_c;
architecture rtl of muller_c is
begin
process (in1, in2) is
variable state : bit;
variable in_cat : bit_vector (1 downto 0);
begin
in_cat := (in2, in1);
case (in_cat) is
when "00" => state := '0';
when "01" => state := state;
when "10" => state := state;
when "11" => state := '1';
when others => null;
end case;
mout <= state;
end process;
end architecture rtl;
-------------------------------------------------------------------
Code2:
entity muller_c is
port (in1, in2 : in bit;
mout : out bit);
end entity muller_c;
architecture rtl of muller_c is
begin
process (in1, in2) is
variable in_cat : bit_vector (1 downto 0);
begin
in_cat := (in2, in1);
case (in_cat) is
when "00" => mout <= '0';
when "01" => null;
when "10" => null;
when "11" => mout <= '1';
when others => null;
end case;
end process;
end architecture rtl;
-------------------------------------------------------------------
The first implementation is different from the second one, in that, the
second one does not make use of the 'state' variable.
I would like to know which one of the two implementation is more
appropriate and why?
Any information on where a Muller's C-element is used (application of
Muller's C-element) would be really great to know.
Thanks,
Anand
Jussi Lähteenmäki
They are pretty much the same, the first one being more readable with
large designs as you don't have to explicitly guess which signals remain
intact in each case...
regards,
juza
: I wrote two pieces of code for a problem that requires the implementation
: Thanks,
: Anand
--
Juza
David Binnie
ENTITY Muller_C IS
PORT( A, B : IN bit;
C: INOUT bit); -- ieee 1076-1993 allows an entity to read its own
o/ps
END Muller_c;
ARCHITECTURE a1_arch OF Muller_C IS
BEGIN
C <= '0' WHEN A='0' AND B='0' ELSE
'1' WHEN A='1' AND B='1' ELSE C ;
END a1_arch;
ARCHITECTURE a1a_arch OF Muller_C IS
BEGIN
C <= C WHEN A/=B ELSE A;
END a1a_arch;
ARCHITECTURE b2a_arch OF Muller_C IS
BEGIN
PROCESS(A,B)
BEGIN
IF NOT A = B THEN -- 'not equal to' does not work here.
NULL;
ELSE
C <= A;
END IF;
END PROCESS;
END b2a_arch;
ARCHITECTURE a2_arch OF Muller_C IS
BEGIN
my_block:BLOCK ( A = B)
BEGIN
C <= GUARDED A;
END BLOCK my_block;
END a2_arch;
ARCHITECTURE b_arch OF Muller_C IS
BEGIN
PROCESS(A,B)
BEGIN
IF A='0' AND B='0' THEN
C <= '0';
ELSIF A='1' AND B='1' THEN
C <= '1';
END IF;
END PROCESS;
END b_arch;
ARCHITECTURE b2_arch OF Muller_C IS
BEGIN
PROCESS(A,B)
VARIABLE AB:Bit_Vector(1 DOWNTO 0);
BEGIN
AB:= A & B;
CASE AB IS
WHEN "00" => C <= '0';
WHEN "11" => C <= '1';
WHEN OTHERS => NULL;
END CASE;
END PROCESS;
END b2_arch;
--ARCHITECTURE c_arch OF Muller_C IS
--BEGIN
-- PROCESS
-- BEGIN
-- WAIT UNTIL A='0' AND B='0';
-- C <= '0';
-- WAIT UNTIL A='1' AND B='1';
-- C <= '1';
-- END PROCESS;
--END c_arch;
You pays your money....................
Kai Harrekilde-Petersen
> Any information on where a Muller's C-element is used (application of
> Muller's C-element) would be really great to know.
MÜller-C elements are often used in self-timed or delay-insensitive
design methods. Essentially, it synchronizes events on two wires,
such that it will only pass on an event to the output, once both
events on the input has arrived.
I think of it as an "Event-AND" gate. The XOR gate is an "Event-OR"
gate.
Ivan E. Sutherland described the use of Müller-C elements in his
Turing-award lecture, called "Micropipelines". You can find it in
Communications of the ACM, June 1989, Volume 32, Number 6, pp.
720--738.
Hope this helps,
Kai Harrekilde-Petersen.
Ralf Hildebrandt
> -----------------------------------------------------------------
> Code1:
>
> entity muller_c is
> port (in1, in2 : in bit;
> mout : out bit);
> end entity muller_c;
>
> architecture rtl of muller_c is
> begin
> process (in1, in2) is
> variable state : bit;
> variable in_cat : bit_vector (1 downto 0);
> begin
> in_cat := (in2, in1);
> case (in_cat) is
> when "00" => state := '0';
> when "01" => state := state;
> when "10" => state := state;
> when "11" => state := '1';
> when others => null;
> end case;
> mout <= state;
> end process;
> end architecture rtl;
> -------------------------------------------------------------------
Well... this may lead to hazarderous state-changes.
When in1 and in2 change not at exactly the same time (everytime in
reality), bad state-transitions may occour.
What about a clocked process?
process (clock) is
variable state : bit;
variable in_cat : bit_vector (1 downto 0);
begin
if rising_edge(clock) then
in_cat := (in2, in1);
case (in_cat) is
when "00" => state := '0';
when "01" => state := state;
when "10" => state := state;
when "11" => state := '1';
when others => null;
end case;
mout <= state;
end if;
end process;
(This is a flip-flop.)
Furthermore - if you really want to describe a asynchronous (not
clocked) behavior, then your
> in1 in2 out
> 0 0 0
> 0 1 P
> 1 0 P
> 1 1 1
>
> P : Previous value of out
can be implemented with
process(in1,in2)
begin
if (in1='0' AND in2='0') then
mout<='0';
elsif (in1='1' AND in2='1') then
mout<='1';
end if;
end process;
(This is a latch. It has the same hazard-problems like your description.)
Ralf
marcus harnisch
> Well... this may lead to hazarderous state-changes.
>
> When in1 and in2 change not at exactly the same time (everytime in
> reality), bad state-transitions may occour.
Hi Ralf,
To me the truth table looks pretty much race-free. Did I miss
anything?
Best regards,
Marcus
Ralf Hildebrandt
>> in1 in2 out
>> 0 0 0
>> 0 1 P
> > 1 0 P
>> 1 1 1
>>
>> P : Previous value of out
> To me the truth table looks pretty much race-free. Did I miss
> anything?
Let in1='0' and in2='1', let state mout='0'. What happens, if in1
changes to in1='1' and in2='0'?
With no hazards mout='0' after change, but what happens, if in1 changes
to '1', before in2 falls down to '0'? -> mout changes to '1', but this
is wrong.
Ralf
Kai Harrekilde-Petersen
The philosofical(sp?) question here is whether or not the output ought
to change state. Certainly, if the both inputs transition at exactly
the same time, I would argue that the output should NOT change state.
(Another way to describe the Müller-C element is a 3-input
majority-vote element, where the output is feed back to one of the
inputs. This description, btw, makes it quite easy to extend the
Müller-C element to all even number of inputs).
When using the Müller-C element for asynchronous state machines, the
design methodology makes sure that the "01" -> "10" transition on the
inputs cannot happen. The "00" <--> "11" input transitions _can_
occur, but they are not problematic (the output change is well
defined).
Regards,
Kai
Marcus Harnisch
Ralf Hildebrandt <Ralf-Hil...@gmx.de> writes:
> Let in1='0' and in2='1', let state mout='0'. What happens, if in1
> changes to in1='1' and in2='0'?
>
> With no hazards mout='0' after change, but what happens, if in1
> changes to '1', before in2 falls down to '0'? -> mout changes to '1',
> but this is wrong.
Well, yes. I considered the two states 01 and 10 as meta states that
will only ever be reached during transitions between two "real" states
00 and 11. Provided your design is glitch free there won't be any
races.
Best regards,
Marcus