This blog shows C code and Python code for a pseudo random binary sequence (PRBS). The applications for a PRBS will be discussed in later blogs.
A good general reference for a PRBS is wikipedia. In hardware, FPGAÂ or software a PRBS can be implemented as a linear feedback shift register (LFSR). This is shown below for a 7-bit shift register.
The LFSR is comprised of N registers connected in cascade and shifting left 1 bit with each sample time. A number of bits are exclusive or'ed together and the result shifted into bit 0. At the same time the Nth bit is shifted out as the new output at each sample time. The N-bit pattern repeats based on the polynomial selected. Polynomials for which the repeat length is 2^N-1 bits are referred to as maximal length polynomials.
This is an example of the output of the PRBS7 that has been scaled to the range +/-1,
The Python code for a PRBS is shown below for a 15bit polynomial (PRBS15):
| # TremaineConsultingGroup | |
| # Brian Tremaine | |
| # prbs.py | |
| # August 11, 2021 | |
| # Prototype PRBS generator | |
| # | |
| # PRBS15 = x^15 + x^14 + 1 Wikipeda | |
| # .--->X--------------------------------------------------------> | |
| # | | | | |
| # bit | | | | |
| # <----- D D D D D D D D D D D D D D D <-- | |
| # | |
| # bit15 <------------------------------- bit1 | |
| # | |
| # PRBS7 = x^7 + x^6 + 1 | |
| # | |
| # .--->X------------------------> | |
| # | | | | |
| # bit | | | | |
| # <------ D D D D D D D <--| | |
| # | |
| # bit7 <--------------- bit1 | |
| from scipy import signal | |
| import matplotlib.pyplot as plt | |
| """ ============ main ====================================== | |
| """ | |
| if __name__ == '__main__': | |
| bit= list() | |
| start = 1; | |
| lfsr = start; | |
| i= 1 | |
| while True: | |
| fb= ((lfsr>>14) ^ (lfsr>>13) & 1) | |
| lfsr = ((lfsr<<1) + fb) & (2**15-1) | |
| bit.append(fb) | |
| print (i, lfsr, fb, bin(lfsr) ) | |
| if lfsr==start : | |
| print('repeat pattern length', i) | |
| break; | |
| i = i+1 | |
| bit = [float(i) for i in bit] | |
| for i in range(2**15-1): | |
| bit[i]= 2*(bit[i] - 0.5) | |
| plt.plot(bit); plt.title('PRBS') | |
| plt.show() | |
| u = signal.correlate(bit,bit) | |
| plt.plot(u); plt.title('PRBS corr') | |
| plt.show() | |
| print("done!") | |
The C code for a PRBS is shown here:
| // replicated from wikipeda, https://en.wikipedia.org/wiki/Pseudorandom_binary_sequence | |
| // Example of PRBS7 | |
| #include <stdio.h> | |
| #include <stdint.h> | |
| #include <stdlib.h> | |
| int main(int argc, char* argv[]) { | |
| uint8_t start = 0x02; | |
| uint8_t a = start; | |
| int i; | |
| for (i = 1;; i++) { | |
| int newbit = (((a >> 6) ^ (a >> 5)) & 1); | |
| a = ((a << 1) | newbit) & 0x7f; | |
| printf("%x\n", a); | |
| if (a == start) { | |
| printf("repetition period is %d\n", i); | |
| break; | |
| } | |
| } | |
| } |
In an application I had with an embedded MCU I did not have the memory space to generate the full PRBS length in available memory. In that application I generated the new bit of the sequence each time the PRBS routine was called each sample period Ts. The C code for this is shown below.
| Prbs_t is a struct used in the prbs function: | |
| typedef struct | |
| { | |
| uint16_t start; // start LFSR value | |
| uint16_t lfsr; // LFSR current register | |
| uint16_t index; // LFSR index | |
| uint16_t newbit; // current newbit | |
| } Prbs_t; | |
| /** | |
| * @brief generate PRBS15 signal for bode plot system ID | |
| * polynomial x^15 + x^14 + 1 | |
| * @param Prbs_t *p | |
| * @retval int16_t prbs value | |
| */ | |
| uint16_t prbs(Prbs_t *p) | |
| { | |
| p->newbit = (((p->lfsr >> 14) ^ (p->lfsr >> 13)) & 1); | |
| p->lfsr = ((p->lfsr << 1) | p->newbit) & 0x7fff; | |
| p->index++; | |
| if (p->index > (1<<15)-1) | |
| p->index = 0; // ? 0 or 1? | |
| return p->newbit; | |
| } |
The code above calls a function with a pointer to a struct and returns the new bit. The struct is used because I want the elements to be self-contained and they also need to be static between calls.
I'll talk about specific applications later but for now I will say the PRBS has a maximal length of M=2^N-1 for specific polynomials. This means the register contents repeats every M sample periods. For the PRBS u(k), the cross-correlation of u(k) with itself, Ruu(k), is nearly an impulse function. The value of the Ruu(k) is as follows:
= M*a^2Â for lag = 0, +/-M, +/-2M, +/-3M ...
= a^2Â otherwise
To get the cross-correlation mentioned above the correlation must be over a several M sequences. A cross-correlation of a single sequence is shown below for a PRBS7. For this limited sequence the max value is 127 and for non-zero lag the max value is about 12. For a sequence of 32 or more cycles the zero lag is 127 and the non-zero lag approaches 1.
The PRBS signal is a good approximation of the Kronecker Delta functions so the frequency content is evenly distributed (flat) across its spectral range of M/Ts to 0.5/Ts, where Ts is the sample rate or clock period.
I will talk about applications of the PRBS for system identification in an upcoming blog.