| Thread Links | Date Links | ||||
|---|---|---|---|---|---|
| Thread Prev | Thread Next | Thread Index | Date Prev | Date Next | Date Index |
|
Pete, Thanks for your explanation. It makes allot of sense. I wonder though… If you would like to draw sequences from a uniform distribution over their types, why not just do that? We know that for any sequence of length N, there is a polynomial (of N) number of types. Drawing uniformly over the types is thus easy to implement. Once you have selected the type you can simply draw a sequence of that type. You can repeat this process as long as you’d like and get a nice uniform distribution over the 10,000 years support you showed. Additionally, since the basis for the implementation would be LFSRs, it can be made completely repeatable. Regards, Yuval From: Anslow, Peter [mailto:panslow@xxxxxxxxx]
Yuval, In my understanding, the term “i.i.d” means “independent and identically distributed”. What we would like to obtain from testing with the various test patterns discussed is that the stress they apply to the test system is sufficiently high to indicate that the performance seen with
the short test pattern is representative of the worst performance seen with a long period (10,000 years) of random data. So, we are not looking for something that looks like random data. This would be somewhat benign as the short section of data seen in
the test period is not as stressful as the worst case seen in 10,000 years. From the green curve on slide 6 of anslow_3bs_03_0714, 32,000 bits of random data only has about half of the baseline wander that you would see in 10,000 years of random data. Similarly,
the green curve on slide 9 of anslow_3bs_03_0714, 32,000 bits of random data only has about half of the clock content variation that you would see in 10,000 years of random data. In contrast to this, the SSPR pattern does a better job of stressing the test
system for baseline wander and clock content by an amount that is representative of a long period of random data. Regards, Pete Anslow |
Senior Standards Advisor From: Yuval Domb [mailto:yuvald@xxxxxxxxxxxx]
Pete, Your lecture about pattern characteristics was very interesting and triggered some thoughts for me. I’d like to share those thoughts with you and the forum. I’ll divide those thoughts to two categories, pattern creation, and pattern analysis: 1.
Patten creation:
a.
The use of PRBS sequences, or perhaps more correctly LFSR sequences, in place of true uniformly distributed sequences, has been around for many years. As far as I know, the bit stream resulting from those sequences
can be shown to be empirically uniformly distributed. As far as I know, there has never been a claim that those sequences are necessarily empirically i.i.d., or close to i.i.d. This hasn’t stopped the industry from using those sequences, assuming they are
empirically i.i.d., resulting in the problems you presented yesterday.
b.
A method I have used several times, for both binary and PAM/QAM data patterns is to take a few LFSR sequences of different lengths and combine them in different ways to get to much longer sequences. I have never
seen much documentation about this method, and am not sure why, but it works. To clarify let’s examine three examples:
i. Take two sequences PRBS15 and PRBS17. If you check you’ll see that the LCM of their lengths is (2^15-1)*(2^17-1) since they have no common factors. If you
create a bit stream that is their XOR you’ll get a sequence of length equal to their LCM, which by the Shannon Crypto Lemma is more i.i.d. than the previous two.
ii. Take the same two sequences from above and concatenate them to create a PAM4 sequence of length equivalent again to their LCM. It is a little bit more
complicated to prove but this sequence is also more i.i.d. than using either of the previous two to create a PAM4 sequence by concatenating pairs of adjacent bits.
iii. Take the bit sequence from (i) and create a PAM4 sequence by concatenating pairs of adjacent bits. Obviously, if the bit sequence is truly i.i.d., so
is the PAM4 sequence.
c.
The above method can be used with a greater number of baseline LFSR sequences, thus by Shannon’s Crypto Lemma, the resulting sequence will tend to be closer to true i.i.d., as desired.
d.
The length of the complete resulting sequence is very long, but once it is i.i.d., so are sub-sequences of it, so short length sequences using this method are possible. 2.
Pattern analysis:
a.
The purpose, as I understand, is to verify that some given sequence is empirically i.i.d.
b.
The method you presented was not completely clear to me. I did however understand that it is somewhat related to examining the distribution of typical sequences. It is well known that the types of a collection
of binary N-tuples, each one resulting from N Bernoulli(0.5) trials, is binomially distributed (not Gaussian). I’m not sure, but I suppose that this works the other way too, so that if you have a set sequences of binomially distributed Hamming weight, they
are resulting from an i.i.d. distribution. It seems to me that your method examines the distribution of the types or Hamming weights of the sequences and how far it is from the binomial. This method has a few potential pit falls:
i. It is suitable for binary sequences but not for larger alphabet, such as PAM4. For larger alphabet you would need to examine the distribution of the types
using strong typicality, which is a much more complicated distribution. I think you noticed that and gave some heuristic method of converting this back to something that looks more like Hamming weights. This is probably similar to examining weak typicality
instead of strong, but I’m not sure it would capture enough detail to show that the original sequence is i.i.d.
ii. The finite length of the sequences you examined will tend to create aliasing which may hide out some of the detail. For example, a sequence of length 1
will always look close to binomial.
c.
It is unclear to me why we cannot use the ordinary test for empirically estimating the time behavior of a random process. This method deals directly with the sequence rather than with manipulations of it. To do
this all you need to do is take the sequence, assume it is resulting from a WSS random process, and estimate its spectrum. This allows you to use whatever alphabet you would like. The aliasing problem exists here too, but there are known ways to get around
it (i.e. examine longer frames) such as using frame overlap and averaging (Welch method). The resulting spectral estimation is for long frames with low estimation variance. A true i.i.d. sequence would result in a white spectrum. Also, the method is very quick
since its computation is based on FFT. Hope I was clear enough with my descriptions. Regards, Yuval |