| Thread Links | Date Links | ||||
|---|---|---|---|---|---|
| Thread Prev | Thread Next | Thread Index | Date Prev | Date Next | Date Index |
|
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 |