Testing pseudo-random sequence – InformTFB

Testing pseudo-random sequence

Testing pseudo-random sequence

As end users of the communication channel, we had to take part in testing the modified communication system. As a matter of fact, our participation was simple – to bring a laptop and a pairing unit, connect it to the system and continuously output any information frames from the computer as a certain “payload”.

The developers had to run the system in different modes, and then the telemetrists gave us the received data array. After that, we had to check the checksums (sorry, cyclically redundant code) of each frame and, if we found errors, enter their number in the test report.

Therefore, it was necessary to prepare a simple program (in the sense of software) for testing. And the question arose, what should I give out as “information”? After all, we did not solve the trivial “lattice” AA55, but a pseudorandom sequence using a primitive Galois polynomial.

The algorithm there is really very simple:

ISSUING A PSEUDO-RANDOM SEQUENCE ----

PSP: MOV EBX, VALUE; INITIALLY ALL UNITS
MOV CX, LENGTH_PSP ;THE NUMBERS OF TAPS OF THE FEEDBACK

;- - - - SETTING THE FEEDBACK WITHDRAWAL POSITION ----

M1: MOV EAX,1
XCHG CH,CL
SHL EAX,CL
XCHG CH,CL

;- - - - PROCESSING THE NEXT BIT ----

ROR EBX,1
JNB M2

;---- THE NEXT BIT IS A UNIT ----

AND EAX, EBX; HIGHLIGHT THE FEEDBACK SIGNAL
MOV EAX,1
JNZ @
SHL EAX,CL
OR EBX, EAX ;IF FEEDBACK=0, ADD 1
JMPS M4
@: SHL EAX,CL
NOT EAX
AND EBX, EAX ;IF FEEDBACK=1, ADD 0
JMPS M4

;---- THE NEXT BIT IS ZERO ----

M2: AND EAX, EBX; HIGHLIGHT THE FEEDBACK SIGNAL
MOV EAX, 1
JZ @
SHL EAX, CL
OR EBX, EAX ;IF FEEDBACK=1, ADD 1
JMPS M3
@: SHL EAX,CL
NOT EAX
AND EBX, EAX ;IF FEEDBACK=0, ADD 0

;---- ISSUANCE OF ZERO ----

M3: CLC
RCR BYTE,1
JMPS @

;- - - - ISSUING A UNIT ----

M4: STC
RCR BYTE,1

;- - - - OUTPUT OF THE NEXT PSP BYTE ----

@ : DEC BITS ;THE BYTE HASN'T RUN OUT YET ?
JNZ M1

MOV BITS, 8; AGAIN 8 BITS
MOV VALUE, EBX ;TO CONTINUE THE PSP
MOV AL, BYTE; ISSUED THE NEXT BYTE OF THE PSP
RET

This subroutine outputs all possible combinations of zeros and ones (except for a single zero combination) of a given length in pseudorandom order. In our case, for a length of 32 bits, half a billion pseudo-random bytes are obtained before repeating this sequence again. Very simple and beautiful.

Since the tests were long, they were divided into 2 days. On the first day, we plugged in the laptop and left, since we had nothing to do during the actual tests. The received data was processed in the evening, and everything is in order.

The second day of testing. Again, everything was connected and was about to leave, when suddenly a report came over the loudspeaker from the hardware room: the “payload” signal disappeared!

What the hell? Yes, there is only one cable in the system goes. Restarted the program. Report again: the signal disappeared. For half an hour, an hour, we try to fix something, although most of the attempts are reduced to walking around the computer table and shrugging our shoulders.

Everything repeats itself: when you turn on the computer, the hardware declares that it sees the “carrier” (and what is this? We don’t have any “carrier”!), then run the program itself and the signal disappears again. Suddenly after an hour in talks with hardware interferes with the telemetry: Yes no signal failure! I accept everything normally, just like yesterday.

Fu-you, well-you. Yesterday, everything was really fine!

We begin to understand.

It turns out that a young specialist was on duty in the control room yesterday. He was asked, is there a “payload”signal? He glanced at the oscilloscope – and there was our noisy pseudo-random sequence running. He doesn’t know what the signal should look like, so he calmly reports: Yes, there is.

And today there is an experienced person on duty, who has conducted tests many times. But it seems that such “payload” signals were never given to him. We turn on the computer – it reports that it sees a “carrier” (this is actually the output of only zeros). And when the program starts to produce a pseudo-random sequence, instead of reporting “I see a noise-like signal”, it immediately makes a false conclusion: the signal has disappeared, white noise.

Thus, it turned out not only testing the communication channel with a pseudo-random sequence, but also random testing of the pseudo-random sequence itself, which convincingly confirmed its randomness, because a completely experienced person could not distinguish it from white noise.

This made me think about mathematics in General and about the unusual people who moved it (and, at the same time, the development of all science) forward. We used the Galois polynomial. Just 20 years of Evariste Galois ‘ life and 4 years of studying mathematics left a legacy that we still use without hesitation.

Of course, Galois ‘ work did not come from scratch. We can say that he took the banner from the hands of Nils Abel, who also passed away very early. And after the absurd death of Galois, in a duel, and even under murky circumstances, the development of mathematics, of course, did not stop. For example, twenty years later, Chebyshev polynomials appeared, which we use every time we use the FPU to calculate trinogometric functions.

But still, the mathematician’s personality also plays an important role. Even in antiquity, philosophers and mathematicians used to tell each other a sophistical joke about Achilles and the tortoise. At the same time, they were one step away from a great mathematical discovery: the sum of an infinite number series can be finite. But then had the boys with fresh eyes, like Galois, who would rather stupid conclusion “Achilles will never overtake the turtle,” would a step in the right direction: “Achilles can never overtake the tortoise in a given time, for the first second, but the second will overtake” means, notwithstanding the infinite division of time into parts, the sum of these infinite parts end! There was no such mathematician then, and the series (which we do not quite rightly call Taylor series) were pushed back thousands of years.

If Galois hadn’t died at a young age, how many more discoveries could he have made? And if he had met Charles Babbage, or Ada Lovelace, we might be living in a completely different computer world right now.…

Valery Radokhleb
Valery Radokhleb
Web developer, designer

Leave a Reply

Your email address will not be published. Required fields are marked *