RE: SJTP:Phantom sync headers
Jonathan,
Okay, so you and Ben want the full analytic treatment. I'll give it a try.
First, let me clear up what my assertion was. I didn't exactly say "that for
any combination of seed and data input, that every combination of two
consecutive bits within the 64 (including the first and last in combination
with the appropriate bit of the sync bits), will ALWAYS have at least one
'00' or one '11' within 64 iterations (64x64) bits."
What I said is that no location would mimic the sync header - that is, no
candidate location would consistantly have a transition between the bits. If
one is very, very, very, very unlucky and randomly chooses a seed and 64-bit
repeating data input, one might get a run of 64 iterations that looked like
a sync header and falsely lock. If one randomly chose seeds and data input
blocks and tried them at link speed, it would take about 58 years to get one
that mimicked (strange word, you have to add a k to the future present tense
to make it past tense) the sync header for 64 bits. If you purposely
engineered the code to do it, then I'm fairly sure that the equations can be
solved to get a run of up to 122 false sync headers. Except for a degenerate
case, you can't get longer runs because you have too many equations in too
few unknowns and can't get it. The degenerate case is that if you load
alternating 1's and 0's into the scrambler seed and into the data word, you
can get a continuous 1010101... pattern out of the scrambler.
If you have a false sync header for 64 blocks in the code and the lock state
machine is unlucky enough to try that location when that pattern comes up,
then it will temporarily lock to the wrong place. But the lock state machine
will soon discover its mistake and go on to try another spot.
What equations govern this?
Let:
S1 through S58 represent the scrambler seed with S58 being loaded into the
oldest position in the scrambler.
D0 through D63 represent the repeating data pattern with D0 being the first
bit to be scrambled.
Bn represent the bits of the transmitted bit stream with B0 being the first
bit out of the scrambler after the seed has been loaded.
In the following equations, I'll put the index for S, D, and B in
parenthesis when it is an expression. When it is just a letter or number, I
won't put on the parenthesis to save space and typing. Also, to save space,
+ between terms means XOR since there isn't an ASCII XOR while plus in an
index means normal addition.
Bn = Dn + S(39-n) + S(58-n) for n < 39
Dn + B(n-39) + S(58-n) for 38 < n < 58
D(n mod 64) + B(n-39) + B(n-58) for n > 57
One can use recursion to get any Bn in terms of Dn and Sn. The last case has
a term of D(n mod 64) because the data pattern repeats every 64 bits.
For a location to look like a sync header, we must have Bn + B(n+1) = 1.
That is, two consecutive bits have different values.
Examine the first location out of the scrambler (if you can create the run
there, you should be able to shift it to any other position).
B0 = D0 + S39 + S58
B1 = D1 + S38 + S57
B64 = D0 + B25 + B6
= D0 + (D25 + S14 + S33) + (D6 + S33 + S52)
= D0 + D6 + D25 + S14 + S52
B65 = D1 + D7 + D26 + S13 + S51
B128 = D0 + B89 + B70
= D0 + (D25 + B50 + B31) + (D14 + B31 + B12)
= D0 + D14 + D25 + (D50 + B11 + S8) + (D12 + S27 + S46)
= D0 + D12 + D14 + D25 + D50 + S8 + S27 + S46 + (D11 + S28 + S47)
= D0 + D11 + D12 + D14 + D25 + D50 + S8 + S27 + S28 + S46 + S47
B129 = D1 + D12 + D13 + D15 + D26 + D51 + S7 + S26 + S27 + S45 + S46
So to get a run of 3 false sync headers, one must solve for:
B0 + B1 = D0 + D1 + S38 + S39 + S57 + S58 = 1
B64 + B65 = D0 + D1 + D6 + D7 + D25 + D26 + S13 + S14 + S51 + S52 = 1
...
B4033 + B4034 = 1
By the time you get to that last one, you are doing about 100 levels of
recursion to get the terms down to the initial seed plus the data pattern.
The degenerate case mentioned above is where the seed in combination with
the data pattern results in the scrambler contents being the same as the
original seed at the end of each 64 data bits. To do that for a fixed data
pattern, one is solving a system of 58 equations for 58 variables (S1 = B63,
S2 = B62, ... S58 = B6). For the data pattern all zeros, the scrambler seed
which satisfies the equation is all zeros. If you set the seed and the data
to all zeros, you will never get anything out but all zeros (which doesn't
have a false sync header). I haven't done the calculation for LF yet.
If you don't do the repeating pattern, you are solving a system of 64
equations and with a fixed data pattern you have 58 variables to adjust. For
most data patterns you can't chose a seed that gives a false sync header
position that will get through the lock state machine except by doing a
pattern that repeats every 64 bits (in which case any transition location
will be continuously repeated). If you allow the data pattern to vary, you
are solving 64 equations with 122 variables and you should be able to create
a false sync header location that repeats for 64 or more up to 122
positions.
Regards,
Pat
-----Original Message-----
From: Jonathan Thatcher [mailto:Jonathan.Thatcher@xxxxxxxxxxxxxxxxxxxx]
Sent: Friday, May 11, 2001 1:02 PM
To: 'pat_thaler@xxxxxxxxxxx'; bbrown@xxxxxxxx;
stds-802-3-hssg-serialpmd@xxxxxxxx
Subject: RE: SJTP:Phantom sync headers
Pat,
So, you are saying that for any combination of seed and data input, that
every combination of two consecutive bits within the 64 (including the first
and last in combination with the appropriate bit of the sync bits), will
ALWAYS have at least one '00' or one '11' within 64 iterations (64x64) bits?
How do you know that?
I know that it is definitely not true for 2 iterations; and is definitely
true if the pattern is repeated in its entirety (2 ** 53 iterations) . I
can't even offer a hypothesis on how to know the length at which this
reverts from not true to true across all permutations and combinations.
jonathan
> -----Original Message-----
> From: pat_thaler@xxxxxxxxxxx [mailto:pat_thaler@xxxxxxxxxxx]
> Sent: Thursday, May 10, 2001 4:38 PM
> To: bbrown@xxxxxxxx; stds-802-3-hssg-serialpmd@xxxxxxxx
> Subject: RE: SJTP:Phantom sync headers
>
>
>
> Ben and Jonathan,
>
> As long as the pattern is being generated by setting the
> scrambler with a
> seed then letting the scrambler run with a fixed 64 bit data
> pattern into
> it, the patterns will not have any location that mimics the
> sync header. One
> would have to design a continuously changing data pattern
> synchronized with
> the seed load to get a data transition in a consistant spot
> for over 64 code
> blocks. If a repeating data pattern did that for any
> scrambler seed, it
> wouldn't be a very good scrambler.
>
> Regards,
> Pat
>
> -----Original Message-----
> From: Ben Brown [mailto:bbrown@xxxxxxxx]
> Sent: Thursday, May 10, 2001 9:59 AM
> To: serialpmd
> Subject: SJTP:Phantom sync headers
>
>
>
> All,
>
> Jonathan brought up an interesting point that I have
> elaborated upon below. Those who have begun or are
> interested in beginning to search for patterns should
> probably keep this in mind.
>
> Ben
>
> --
> -----------------------------------------
> Benjamin Brown
> AMCC
> 2 Commerce Park West
> Suite 104
> Bedford NH 03110
> 603-641-9837 - Work
> 603-491-0296 - Cell
> 603-626-7455 - Fax
> 603-798-4115 - Home Office
> bbrown@xxxxxxxx
> -----------------------------------------
>