Re: SJTP:Phantom sync headers
Pat,
I'm duly impressed. Thanks for your diligence!
Ben
pat_thaler@xxxxxxxxxxx wrote:
>
> 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
> > -----------------------------------------
> >
--
-----------------------------------------
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
-----------------------------------------