<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=Windows-1252">
<style type="text/css" style="display:none;"> P {margin-top:0;margin-bottom:0;} </style>
</head>
<body dir="ltr">
<div style="font-family: Arial, Helvetica, sans-serif; font-size: 10pt; color: rgb(0, 0, 0);">
<p style="margin: 0in 0in 8pt; line-height: 107%; font-size: 11pt; font-family: Calibri, sans-serif">
<span style="font-size: 14pt; line-height: normal;">Pseudo-Random Binary Sequences – PRBS generators (apparently AKA Linear-Feedback Shift Registers – LFSRs) are frequently misunderstood and likely still a considerable way from being completely understood.
They are often thought to produce what is equivalent to a “coin-flip” (CF) results (H=1, T=0) as, typically, (22 ACTUAL flips):</span></p>
<p style="margin: 0in 0in 8pt; line-height: 107%; font-size: 11pt; font-family: Calibri, sans-serif">
<a><span style="font-size: 14pt; line-height: normal;">0 0 1 0 0 1 0 0 0 1 1 1 1 1 0 0 1 1 0 0 0 1</span><span style="font-size: 14pt; line-height: normal;">
</span><span style="font-size: 14pt; line-height: normal;">(CF-A)</span></a></p>
<span style="mso-bookmark:_Hlk27857958"></span>
<p style="margin: 0in 0in 8pt; line-height: 107%; font-size: 11pt; font-family: Calibri, sans-serif">
<span style="font-size: 14pt; line-height: normal;">although we know full-well that a result such as:</span></p>
<p style="margin: 0in 0in 8pt; line-height: 107%; font-size: 11pt; font-family: Calibri, sans-serif">
<span style="font-size: 14pt; line-height: normal;">1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1</span><span style="font-size: 14pt; line-height: normal;">
</span><span style="font-size: 14pt; line-height: normal;">(All ONES!)</span></p>
<p style="margin: 0in 0in 8pt; line-height: 107%; font-size: 11pt; font-family: Calibri, sans-serif">
<span style="font-size: 14pt; line-height: normal;">is possible and is as likely as the particular CF-A result recorded in my experiment.
</span><span style="font-size: 14pt; line-height: normal;"> </span><span style="font-size: 14pt; line-height: normal;">There are 2^22 – 1 = 4,194,304 -1 = 4,194,303 PRBS “states” ALL OF WHICH make an appearance in a full PRBS “cycle”.</span><span style="font-size: 14pt; line-height: normal;">
</span><span style="font-size: 14pt; line-height: normal;">Thereafter, all </span>
<a><span style="font-size: 14pt; line-height: normal;">4,194,303 </span></a><span style="font-size: 14pt; line-height: normal;">repeat exactly.</span><span style="font-size: 14pt; line-height: normal;">
</span><span style="font-size: 14pt; line-height: normal;">A discussion of this generator and related matters which are also addressed below is posted at:</span></p>
<p style="margin: 0in 0in 8pt; line-height: 107%; font-size: 11pt; font-family: Calibri, sans-serif">
<a href="http://electronotes.netfirms.com/AN402.pdf"><span style="font-size: 14pt; line-height: normal;">http://electronotes.netfirms.com/AN402.pdf</span></a></p>
<p style="margin: 0in 0in 8pt; line-height: 107%; font-size: 11pt; font-family: Calibri, sans-serif">
<span style="font-size: 14pt; line-height: normal;">Jan 10, 2014</span><span style="font-size: 14pt; line-height: normal;">
</span><span style="font-size: 14pt; line-height: normal;">ANOMALIES IN PSEUDO-RANDOM GENERATORS</span></p>
<p style="margin: 0in 0in 8pt; line-height: 107%; font-size: 11pt; font-family: Calibri, sans-serif">
<o:p><span style="font-size: 14pt; line-height: normal;"> </span></o:p></p>
<p style="margin: 0in 0in 8pt; line-height: 107%; font-size: 11pt; font-family: Calibri, sans-serif">
<span style="font-size: 14pt; line-height: normal;"> </span><span style="font-size: 14pt; line-height: normal;">HOWEVER, the CF and the PRBS are fundamentally different in a least three ways.</span><span style="font-size: 14pt; line-height: normal;">
</span></p>
<p style="margin: 0in 0in 8pt; line-height: 107%; font-size: 11pt; font-family: Calibri, sans-serif">
<o:p><span style="font-size: 14pt; line-height: normal;"> </span></o:p></p>
<p style="margin: 0in 0in 8pt; line-height: 107%; font-size: 11pt; font-family: Calibri, sans-serif">
<span style="font-size: 14pt; line-height: normal;">(1) The PRBS is deterministic – the CF-A, if clocked as a PRBS generator state (example in AN-402), can only be followed by:
</span></p>
<p style="margin: 0in 0in 8pt; line-height: 107%; font-size: 11pt; font-family: Calibri, sans-serif">
<span style="font-size: 14pt; line-height: normal;">1 0 0 1 0 0 1 0 0 0 1 1 1 1 1 0 0 1 1 0 0 0</span><span style="font-size: 14pt; line-height: normal;">
</span><span style="font-size: 14pt; line-height: normal;">(CF-B)</span></p>
<p style="margin: 0in 0in 8pt; line-height: 107%; font-size: 11pt; font-family: Calibri, sans-serif">
<span style="font-size: 14pt; line-height: normal;">a right-shifted version of CF-A, with the left-most entry thereafter replaced with 1 (EXOR of 1 and 0).</span><span style="font-size: 14pt; line-height: normal;">
</span><span style="font-size: 14pt; line-height: normal;"> </span><span style="font-size: 14pt; line-height: normal;">If the left-most were INSTEAD filled by coin-flip, the register state:</span></p>
<p style="margin: 0in 0in 8pt; line-height: 107%; font-size: 11pt; font-family: Calibri, sans-serif">
<span style="font-size: 14pt; line-height: normal;">0 0 0 1 0 0 1 0 0 0 1 1 1 1 1 0 0 1 1 0 0 0</span><span style="font-size: 14pt; line-height: normal;">
</span><span style="font-size: 14pt; line-height: normal;">(CF-C)</span></p>
<p style="margin: 0in 0in 8pt; line-height: 107%; font-size: 11pt; font-family: Calibri, sans-serif">
<span style="font-size: 14pt; line-height: normal;">would be equally likely with CF-B.</span></p>
<p style="margin: 0in 0in 8pt; line-height: 107%; font-size: 11pt; font-family: Calibri, sans-serif">
<o:p><span style="font-size: 14pt; line-height: normal;"> </span></o:p></p>
<p style="margin: 0in 0in 8pt; line-height: 107%; font-size: 11pt; font-family: Calibri, sans-serif">
<span style="font-size: 14pt; line-height: normal;">(2)</span><span style="font-size: 14pt; line-height: normal;">
</span><span style="font-size: 14pt; line-height: normal;">The fact that all possible length 22 states (except all zeros) of the PRBS MUST appear before any repeats means, for example, that no length-22 “state” of 0’s and 1’s could appear more than once in
the 4,194,303 time series. The implications of this need to be studied.</span><span style="font-size: 14pt; line-height: normal;">
</span><span style="font-size: 14pt; line-height: normal;">For example, a length 23 series of all 1’s would be</span><span style="font-size: 14pt; line-height: normal;"> </span><span style="font-size: 14pt; line-height: normal;">impossible – representing two
instances of a length 22 sequence.</span></p>
<p style="margin: 0in 0in 8pt; line-height: 107%; font-size: 11pt; font-family: Calibri, sans-serif;tab-stops:42.75pt">
<span style="font-size: 14pt; line-height: normal;"><br>
</span></p>
<p style="margin: 0in 0in 8pt; line-height: 107%; font-size: 11pt; font-family: Calibri, sans-serif;tab-stops:42.75pt">
<span style="font-size: 14pt; line-height: normal;">(3) By far the most important distinction between a CF-generated sequence and a PRBS is in the STRUCTURED EVOLUTION of the PRBS.</span><span style="font-size: 14pt; line-height: normal;">
</span><span style="font-size: 14pt; line-height: normal;">In particular, portions of the PBBS contain (by definition and/or observation) rather obvious segments that at least appear to be (and likely sound) non-random.</span><span style="font-size: 14pt; line-height: normal;">
</span><span style="font-size: 14pt; line-height: normal;">For example: the sequence of 22 ones (All ONES above), which is often a part of power-up initialization, (although it must eventually occur, and occur periodically with period 4,194,303).</span><span style="font-size: 14pt; line-height: normal;">
</span><span style="font-size: 14pt; line-height: normal;">If generated by a CF procedure, All ONES might well occur in virtual isolation, juxtaposed among numerous much more random-looking segments of which CDF-A would be typical.</span><span style="font-size: 14pt; line-height: normal;">
</span><span style="font-size: 14pt; line-height: normal;">If generated by the PRBS generator however, it would be surrounded by EXTENSIVE non-random-LOOKING material on BOTH sides.</span><span style="font-size: 14pt; line-height: normal;">
</span><span style="font-size: 14pt; line-height: normal;">This material occurs in noticeably ordered “Frames” of length 22, consecutive ones/zeros patterns which are simple and “obvious”.</span><span style="font-size: 14pt; line-height: normal;">
</span><span style="font-size: 14pt; line-height: normal;">We observe and fully understand how the clocking and feedback logic dictates the intriguing evolving nature: from random-looking segments, evolving to the unique state, followed by its dissipation back
to something looking more random again.</span><span style="font-size: 14pt; line-height: normal;">
</span><span style="font-size: 14pt; line-height: normal;">Thus non-random-looking order fades-in from noise then fades back out.
</span><span style="font-size: 14pt; line-height: normal;"> </span><span style="font-size: 14pt; line-height: normal;">At this point, look at and study the examples in AN-402 if you have not done so.</span><span style="font-size: 14pt; line-height: normal;">
</span><span style="font-size: 14pt; line-height: normal;"> </span></p>
<p style="margin: 0in 0in 8pt; line-height: 107%; font-size: 11pt; font-family: Calibri, sans-serif">
<span style="font-size: 14pt; line-height: normal;"> </span><span style="font-size: 14pt; line-height: normal;">In addition, it is not just a single power-up initialization anomaly that we deal with.
</span><span style="font-size: 14pt; line-height: normal;"> </span><span style="font-size: 14pt; line-height: normal;">There are many more (see example).</span><span style="font-size: 14pt; line-height: normal;">
</span><span style="font-size: 14pt; line-height: normal;">Indeed, it may well be the case that there are countless such frames which just become less and less evident (thus more like expected randomness).</span><span style="font-size: 14pt; line-height: normal;">
</span><span style="font-size: 14pt; line-height: normal;">We are most concerned with these anomalies as they may appear with slow-clocking rates (perhaps melody controllers) or as audible so-called “heartbeats” as “clink – swish - clunk” audible markers.</span></p>
<p style="margin: 0in 0in 8pt; line-height: 107%; font-size: 11pt; font-family: Calibri, sans-serif">
<span style="font-size: 14pt; line-height: normal;"> </span><span style="font-size: 14pt; line-height: normal;">Once we have chosen a PRBS sequence length that will take perhaps 10 seconds to repeat, little is accomplished by making the register longer
(it may in fact just make the anomalies last longer).</span><span style="font-size: 14pt; line-height: normal;">
</span><span style="font-size: 14pt; line-height: normal;">A length-N anomaly in a length-N register could be expected to take perhaps N full-register replacements to dissipate an anomaly, thus N^2 clockings to “wash out”.
</span><span style="font-size: 14pt; line-height: normal;"> </span><span style="font-size: 14pt; line-height: normal;"> </span><span style="font-size: 14pt; line-height: normal;">This would also have required N^2 clockings to assemble.</span><span style="font-size: 14pt; line-height: normal;">
</span><span style="font-size: 14pt; line-height: normal;">For N=22 that might be 2(N^2) = 968 or roughly 1000 sample to “hide”.</span><span style="font-size: 14pt; line-height: normal;">
</span><span style="font-size: 14pt; line-height: normal;">This could be tried by EXORing the entire sequence with a shorter (“chop-up”) PRBS of perhaps N=10 (2^N-1 = 1023)</span></p>
<p style="margin: 0in 0in 8pt; line-height: 107%; font-size: 11pt; font-family: Calibri, sans-serif">
<span style="font-size: 14pt; line-height: normal;">Comments invited. </span></p>
<p style="margin: 0in 0in 8pt; line-height: 107%; font-size: 11pt; font-family: Calibri, sans-serif">
<span style="font-size: 14pt; line-height: normal;">Bernie </span></p>
<p style="margin: 0in 0in 8pt; line-height: 107%; font-size: 11pt; font-family: Calibri, sans-serif">
<o:p><span style="font-size: 14pt; line-height: normal;"> </span></o:p></p>
<br>
</div>
</body>
</html>