100 Mbit manchester coded signal in FPGA

Please let me be moderator, for this is interesting.
Let's simplify the discussion by assuming no jitter and no glitches.
Lets also agree that Manchester code is ambiguous in an all-1 or al-0
transmission, since they look identical. The decoder needs a 0-1 or 1-0
bit transition in order to start on the "right foot".
That is all well-known.
The question then is:
Can Manchester Code be decoded with the help of a local clock that is,
for example, exactly 3 times the bit rate, or are there severe
limitations on the local clock frequency.
The simple approach that triggers on a transition and then suppresses
the next one, if it occurs at half-bit time, has a problem with a local
3x asynchronous decoding clock.
John suggests a solution, and Rickman does not accept it.
Round 2:

Peter Alfke

John_H wrote:
> You may not notice but I did decode exactly what you show BUT I included the
> preceeding and following bits as well.  The inversion is the issue.  Some
> references suggest the bit value is in the first half, some the second.
> This is pointed out later in the wikipedia article.  I used the first half
> of the bit period for the data but you can see my bit half pairs are
> correct.

First let me say that I am not trying to be rude in any way.  If you
read my posts and see something that you find offensive, I did not
intend that.  My comment below about reviewing Wikipedia was meant as a
simple statement, not an insult.  So I apologize for anything that is
perceived as offensive.  Please keep in mind that writing is very
different from speaking.  Since tone can not be conveyed redily words
can be interpreted very differently depending on the tone you perceive.


For the technical issues... The inversion is not the relevant issue.
If you had an algorithm that would decode the stream I gave you as the
inverted data I would have accepted that.  The problem is the timing.
The way Manchester is decoded is to trigger a timer (it was a one shot
back when I first worked on this problem) that will ignore any
following transitions for approx 3/4 of a bit time.  This gives you
+-1/4 of a bit time to allow for distortion and jitter in the signal.
When you sample the incoming signal with a 3x clock or a 4x clock there
are degenerate cases where the signal is sampled at the time it is
changing which adds a full clock period to the jitter.  In both of
these cases there is not enough margin to allow for this an you can get
erroneous decoding.

Your analysis, if I understood it correctly, produced 6 bits of data
when there were only four.  I am also interested in the algorithm you
used.  It would be instructive if you gave us the detail of how you
decode the bit stream.

Ok, I think I understand where the extra 2 bits came from.  Somehow you
assumed that the intial and final zeros were adjacent to ones and added
extra edges that produced data.  So we can ignore those edges and the
other data looks good.  But what was your algorithm?  You need to have
a method that can be implemented in logic.  I am pretty confident that
no matter what algorithm you choose, I can find a case where it won't
work.


> Of COURSE the sampling doesn't produce an evenly PACED distribution of
> pulses, it produces counts of 2 to 4 for the two half bits from adjecent
> values and counts from 1-2 for the isolated half bits.  It happens that
> these overlap as I described.  If you only have an all-zero or all-one
> pattern then no, you cannot ambiguously extract the data.  Once you get any
> other data, the alignment is guaranteed.

I think you are referring to the initial alignment.  Manchester
encoding is typically used in systems where the signal is broadcast
over a radio or other analog medium which can have timing and amplitude
distortions which can introduce erroneous bits.  That is typically
handled by sending a synchrononization sequence of alternating 1s and
0s.  This produces a pattern of transitions only at the bit center to
assure proper alignment.  The sequences I sent did not include any
medium induced distortions, so the initial transition was a bit center
and was an appropriate transition to start your process.

> You mentioned the sequences need to be decoded to 1001 yet you decoded 1100.
> At the 2x transmit output, the encoded sequence would be either 10100101 or
> 01011010 depending on your polarity.  Is that what you were attempting to
> show?  Or was it 1100?

Yes, the second bitstream produces a wrong pattern because of the
jitter introduced.  That is my point.  You can decode the first
bitstream because there is no distortion.  But the second bitstream
shows that that distortion introduced by sampling on the transition
will give errors and can not be avoided with a 3x or 4x clocking
scheme.


> Your "go back to Wikipedia" comment was uncalled for.  If you don't
> understand what I'm trying to describe or vice-versa, it's a problem with
> the communication medium (to include the inaccuracies of English) and not
> that I'm brain challenged.

As I posted above, I was not trying to insult you.  I was suggesting
that you do not understand how to decode a Manchester encoded signal
and should check the references.  Sorry that it sounded like an insult.
 I have no reason to insult anyone here and I apologize.


> Embedded clocks are used all over.  Successfully.  But you don't see it.
> Are you right?

I don't understand what you are saying with this.


> "rickman" <spamgoeshere4@yahoo.com> wrote in message
> news:1155329590.259386.229690@h48g2000cwc.googlegroups.com...
> > John_H wrote:
> >> "John_H" <newsgroup@johnhandwork.com> wrote in message
> >> news:Iu5Dg.7581$Oh1.4082@news01.roc.ny...
> >>
> >> >  0001101110010000
> >> > 10  01  01  10  10   01
> >> > 1   0    0     1    1    0
> >> >
> >> > 0000101111010000
> >> > 10   01 01  10  10  01
> >> > 1    0   0   1    1    0
> > Ok, that is what you are not getting.  Time sampling does not produce
> > an even distribution of pulses in the time sampled domain with a 3x
> > clock.  The above sequences both need to be decoded to the same
> > sequence, 1001.  The first sequence assumes "ideal" sampling with no
> > timing abiguities.  The second sequence is what you might get if the
> > sampling is done right on the important edges and a small amount of
> > jitter messes up your data.
> >
> > 000_1101110010000
> >     ^  First bit = 1
> > 00011_01110010000
> >        ^  edge between bits, ignore
> > 000110_1110010000
> >          ^  Second bit = 1
> > 000110111_0010000
> >               ^  Third bit = 0
> > 00011011100_10000
> >                   ^  edge between bits, ignore
> > 000110111001_0000
> >                     ^  Fourth bit = 0

rickman wrote:
> First let me say that I am not trying to be rude in any way.  If you
> read my posts and see something that you find offensive, I did not
> intend that.  My comment below about reviewing Wikipedia was meant as a
> simple statement, not an insult.  So I apologize for anything that is
> perceived as offensive.  Please keep in mind that writing is very
> different from speaking.  Since tone can not be conveyed readily words
> can be interpreted very differently depending on the tone you perceive.

I appreciate that you recognize the ineffectiveness of communication and 
that you're not intending to be rude.  That helps.

> For the technical issues... The inversion is not the relevant issue.
> If you had an algorithm that would decode the stream I gave you as the
> inverted data I would have accepted that.  The problem is the timing.
> The way Manchester is decoded is to trigger a timer (it was a one shot
> back when I first worked on this problem) that will ignore any
> following transitions for approx 3/4 of a bit time.  This gives you
> +-1/4 of a bit time to allow for distortion and jitter in the signal.
> When you sample the incoming signal with a 3x clock or a 4x clock there
> are degenerate cases where the signal is sampled at the time it is
> changing which adds a full clock period to the jitter.  In both of
> these cases there is not enough margin to allow for this an you can get
> erroneous decoding.

If you choose to use a one-shot for the decoding, you are limited to a 
higher clock rate.  There is more than one way to do a decode.  The 
degenerate cases - all 1s, all 0s, repeating 0011 - can keep the data 
from *starting* a proper decode but cannot confuse the system once data 
*has* started.

> Your analysis, if I understood it correctly, produced 6 bits of data
> when there were only four.  I am also interested in the algorithm you
> used.  It would be instructive if you gave us the detail of how you
> decode the bit stream.

For your sampling challenged stream using the second half of the bit 
pair for data:

0000101111010000
|||:  :  :  :
000:  :<- first 3 bits indicates bit boundary at middle position
  000  : <- another says adjust boundary again
   001 :  <- the first pair is 0.1 or binary 1
       :  :  :Timing is now "locked"
      011 :<- the second pair is 0.1 or binary 1
         110 :<- 3rd pair 1.0 or binary 0
            100  <- 4th pair is 1.0 or binary 0

Full decode.
The first detection of a constant sequence of 3 bits will remove all 
ambiguity.  If the clock is known to be in the range (2x,4x) exclusive 
(please tighten the range for jitter or duty cycle) then there will be 
instances of at least 3 consecutive constant samples somewhere in the 
data stream.  The closer to 2x or the less data diversity, the longer it 
takes for initial lock bit it *will* lock on all data following that 
first "triple."

What your example missed was the occasional shortening of the full bit 
period.  I showed above bringing down three bits at a time.  The three 
bits would "slide" further by one bit if another sequence of 4 constant 
samples showed up, throwing away the extra bit and aligning a new bit 
trio for analysis.  The opposite of this slide is the need for a 
compression.  If the bit trio that's analyzed has a sequence of 010 or 
101, the bit pair is the first two bits (01. or 10. in the notation I 
used above) and the next bit trio starts with the 3rd bit in the current 
bit trio, not the bit after.

Triples (000 or 111) declare the starting point for bit trio analysis. 
If a four constant sample - a quad - is seen, it's just another triple 
one bit over that again declares a new starting point, throwing away one 
redundant bit.  Active bit trios (010 or 101) which are analyzed for the 
Manchester pair use only the first two bits for the pair and the 3rtd 
bit becomes the start of the next bit trio for analysis.

I'm getting a simulation together to run bunches of these sequences.  If 
the Xilinx tools support simulation, I should have that done today.  If 
not, tools at work need to be employed after hours.

> Ok, I think I understand where the extra 2 bits came from.  Somehow you
> assumed that the intial and final zeros were adjacent to ones and added
> extra edges that produced data.  So we can ignore those edges and the
> other data looks good.  But what was your algorithm?  You need to have
> a method that can be implemented in logic.  I am pretty confident that
> no matter what algorithm you choose, I can find a case where it won't
> work.

The first bit came from backing up the extraction in a sense suggested 
by Brian Drummond in the embedded clocks thread - retroactive decoding - 
along with the knowledge that the last half of the Manchester bit pair 
is 0.  Similarly the first half of the bit pair at the end of your 
sequence absolutely *starts* with a zero.  These known quantities 
weren't covered explicitly in the algorithm I've demonstrated but could 
have been.

<snip>

>> You mentioned the sequences need to be decoded to 1001 yet you decoded 1100.
>> At the 2x transmit output, the encoded sequence would be either 10100101 or
>> 01011010 depending on your polarity.  Is that what you were attempting to
>> show?  Or was it 1100?
> 
> Yes, the second bitstream produces a wrong pattern because of the
> jitter introduced.  That is my point.  You can decode the first
> bitstream because there is no distortion.  But the second bitstream
> shows that that distortion introduced by sampling on the transition
> will give errors and can not be avoided with a 3x or 4x clocking
> scheme.

The two bitstreams decoded identically in my example.  You said 1001 but 
you showed 1100.

<snip>

I'll have Verilog ready later.  It's specifically for the 2x-4x 
(exlusive) case and - like any Manchester decoder - will have a lock 
delay based on the data and sampling conditions.  This wide range means 
something about the rate must be known but no precision on that 
knowledge.  Simple RC oscillators could be used at both ends for a 3x 
sampler and work with this algorithm.

Manchester decoding with greater than 3x allows the sampling to be split 
into distinct halves where the error for sampling of N/2 and N-wide 
pulses in an Nx sampling scheme do not overlap.  They may abut at lower 
values and higher distortion but they don't overlap, allowing simpler 
decoding schemes.

Embedded clocks work.

- John_H

I can't say I understand your algorithm exactly, but try it on this
example
00001100110010000

Can you describe your decoding in a way that can be implemented in
logic.  Even if it is a lookup table, it should be definable in logical
terms.


John_H wrote:
> For your sampling challenged stream using the second half of the bit
> pair for data:
>
> 0000101111010000
> |||:  :  :  :
> 000:  :<- first 3 bits indicates bit boundary at middle position
>   000  : <- another says adjust boundary again
>    001 :  <- the first pair is 0.1 or binary 1
>        :  :  :Timing is now "locked"
>       011 :<- the second pair is 0.1 or binary 1
>          110 :<- 3rd pair 1.0 or binary 0
>             100  <- 4th pair is 1.0 or binary 0

rickman wrote:
> I can't say I understand your algorithm exactly, but try it on this
> example
> 00001100110010000
   000 realign
    000 realign
     001 Manchester pair 0.1
        100 Manchester pair 1.0
           110 Manchester pair 1.0
              010 Manchester pair 01.
                000 realign
                 000 realign
     ------------ 001 (assumed) Manchester pair 0.1
      1  0  0  1   1
     ------------

> Can you describe your decoding in a way that can be implemented in
> logic.  Even if it is a lookup table, it should be definable in logical
> terms.

------- The rest of the post is just code -----------------------
Before simulation:

module
   Manchester
   ( input            clk
   , input            reset
   , input            datIn
   , output reg [1:0] ManchesterPair
   , output reg       usePair
   );

reg       r_reset = 1'b1;
reg       startup;
reg [4:0] rcv;
reg       short;
reg       long;
reg [1:0] bitStart;

always @(posedge clk)
begin
   r_reset <= reset;
   if( r_reset )
   begin
     startup        <= 1'b0;
     rcv            <= 5'b01000;
     ManchesterPair <= 2'h0;
     bitStart       <= 2'h0;
     usePair        <= 1'b0;
   end
   else
   begin
     if( ~startup )
     begin
       startup <= rcv[1];  // First 1 starts off valid receive
       rcv <= {rcv[1] ? 3'b101 : 3'b010, rcv[0], datIn};
     end
     else
       rcv <= {rcv[3:0],datIn};

     short <= rcv[3:1]==3'b010 | rcv[3:1]==3'b101;
     long  <= rcv[3:1]==3'b000 | rcv[3:1]==3'b111;

     if( bitStart== 2'h3 )
     begin
       ManchesterPair <= short ? {rcv[4],rcv[3]}
                               : {rcv[4],rcv[2]};
       bitStart <= short ? 2'h2 : 2'h1;
     end
     else                       // Either 3 or 4 samples
       bitStart <= long ? 2'h2  // start the valid data
                 : bitStart + (bitStart>2'h0);

     usePair <= bitStart==2'h3;
   end
end

endmodule

Ok, I thought this would fail and it did.  This sequence is the same
bit pattern as before, with one edge detected differently from jitter.

0001101110010000
0001100110010000
______^ - this should be pointing to the second zero after the 1->0
transition

Can you fix your algorithm to deal with this case?
Do you see what I am referring to about the jitter making it impossible
to distinguish the mid-bit transition from inter-bit transitions?

John_H wrote:
> rickman wrote:
> > I can't say I understand your algorithm exactly, but try it on this
> > example
> > 00001100110010000
>    000 realign
>     000 realign
>      001 Manchester pair 0.1
>         100 Manchester pair 1.0
>            110 Manchester pair 1.0
>               010 Manchester pair 01.
>                 000 realign
>                  000 realign
>      ------------ 001 (assumed) Manchester pair 0.1
>       1  0  0  1   1
>      ------------
>
> > Can you describe your decoding in a way that can be implemented in
> > logic.  Even if it is a lookup table, it should be definable in logical
> > terms.
>
> ------- The rest of the post is just code -----------------------
> Before simulation:
>
> module
>    Manchester
>    ( input            clk
>    , input            reset
>    , input            datIn
>    , output reg [1:0] ManchesterPair
>    , output reg       usePair
>    );
>
> reg       r_reset = 1'b1;
> reg       startup;
> reg [4:0] rcv;
> reg       short;
> reg       long;
> reg [1:0] bitStart;
>
> always @(posedge clk)
> begin
>    r_reset <= reset;
>    if( r_reset )
>    begin
>      startup        <= 1'b0;
>      rcv            <= 5'b01000;
>      ManchesterPair <= 2'h0;
>      bitStart       <= 2'h0;
>      usePair        <= 1'b0;
>    end
>    else
>    begin
>      if( ~startup )
>      begin
>        startup <= rcv[1];  // First 1 starts off valid receive
>        rcv <= {rcv[1] ? 3'b101 : 3'b010, rcv[0], datIn};
>      end
>      else
>        rcv <= {rcv[3:0],datIn};
>
>      short <= rcv[3:1]==3'b010 | rcv[3:1]==3'b101;
>      long  <= rcv[3:1]==3'b000 | rcv[3:1]==3'b111;
>
>      if( bitStart== 2'h3 )
>      begin
>        ManchesterPair <= short ? {rcv[4],rcv[3]}
>                                : {rcv[4],rcv[2]};
>        bitStart <= short ? 2'h2 : 2'h1;
>      end
>      else                       // Either 3 or 4 samples
>        bitStart <= long ? 2'h2  // start the valid data
>                  : bitStart + (bitStart>2'h0);
> 
>      usePair <= bitStart==2'h3;
>    end
> end
> 
> endmodule

rickman wrote:
> Ok, I thought this would fail and it did.  This sequence is the same
> bit pattern as before, with one edge detected differently from jitter.

     01 01 10 10
> 0001101110010000
   ?00?10?11?01?00? <- ? indicates sample can go either way
> 0001100110010000
     01\__/10 10
     ambiguous
       1001
<snip>

Thank you, rickman.  Your persistence has shown me that a 3x solution 
probably cannot unambiguously decode a Manchester encoded signal.  I 
would hope that running through the simulations would have pointed this 
out quickly and clearly.  For the 3x case, the unambiguous pairs 
determined by the runs of three or more constant values decode fine in 
the first case but cannot guarantee a decode in the second, at least if 
the run of 4 is discounted for the moment; I feel ignoring it is 
necessary for the general case since phases will slip between the 
sampler and the transmit clock.

In the second example you gave above that has the one key bit sampling 
the other side of the edge, the pairs (also working backward from the 
end of the pattern) end up with a gap that I cannot determine the 
appropriate bit.

Despite my early confidence, you appear correct.


My background dealt a lot with the CMI (Complementary Mark Inversion) 
encoding for 140 Mbit/s telecom data.  This format requires a rising 
edge at mid bit for a zero (always a 01 pair of half bits) while a one 
had no mid-bit transition at all (either a 00 or 11 half bit pair). 
Transitions from a one to a one would switch polarity, guaranteeing at 
least one transition per bit period where falling edges *only* occur at 
the edge of the bit period.  This encoding scheme appears to be easier 
to decode than the Manchester at lower oversampling rates.

I don't easily find a solution to the Manchester decoder that will work 
simply for a very wide frequency range (such as 10x) while handling 
small multiplier values without confusion.  The limits for widest half 
pulse versus narrowest full pulse sample periods aren't so easy to 
define when the ideal multiplier is unknown.

I appreciate the "fun" in delving deeper into this subject than I 
normally would go.  If you want something "like" Manchester but with 
better behavior, perhaps CMI is an encoding to consider.

- John Handwork

"John_H" <johnhandwork@mail.com> wrote in message 
news:qqyDg.11048$hH1.10036@trnddc08...
>
> I appreciate the "fun" in delving deeper into this subject than I normally 
> would go.  If you want something "like" Manchester but with better 
> behavior, perhaps CMI is an encoding to consider.
>
I think CMI has a problem with four times oversampling. From G.703:-
<quote>
CMI is a 2-level non-return-to-zero code in which binary 0 is coded so that 
both amplitude levels, A1
and A2, are attained consecutively, each for half a unit time interval 
(T/2).
Binary 1 is coded by either of the amplitude levels A1 or A2, for one full 
unit time interval (T), in
such a way that the level alternates for successive binary 1s.

For binary 0, there is always a positive transition at the midpoint of the 
binary unit time interval.

For binary 1:
a) there is a positive transition at the start of the binary unit time 
interval if in the preceeding time interval the level was A1;
b) there is a negative transition at the start of the binary unit time 
interval if the last binary 1 was encoded by level A2.
</quote>


So, a falling edge is the start of a symbol, no problem. The difficulty 
comes when there's a binary one symbol coded as (b) above, followed by a 
symbol of either type where the sampling point coincides with the rising 
edge, followed by a long string of binary zeroes. Until the next binary one 
comes along, it's not possible to resolve what the mystery bit is. I think 
if you wait for the next binary one you can resolve the mystery bit, but 
you'd need a fifo of depth equal to the longest string of zeroes you can 
receive.

With four times oversampling.

| 0 | 1 | X | 0 | 0 | 0 | 0 | 0 |
00110000011100110011001100110011
        ^^
Which one of the marked bits is wrong?

BTW, excellent thread guys. It interesting that NRZ and RZ are much easier 
to recover with low sample rates. This is because with NRZ a transition 
means the start of a symbol, and ONLY occurs at the start of a symbol. With 
RZ, a rising edge means the start of a symbol, a falling edge the middle and 
ONLY those places. Manchester coding, and CMI to a lesser extent, suffer 
from the problem that certain transitions can be either at the start or in 
the centre of a bit. If only they didn't have DC, NRZ and RZ would be better 
choices! It's easy to see why AMI coding is so popular.

Cheers, Syms.