How to inverse LFSR and shift register in C?

Question

I'm programming an OFDM system, both the transmitter and receiver sides. The first function where the bits go is the scrambler, which is basically an LFSR, where my polynomial is x^7 + x^4 + 1, simply, I XOR the 7th and 4th bit in the register, and make it the new first bit of the shift register, and also XOR that value with the input value, to get the output value. Pictorially, it can be seen below.

I'm working with a an array of type short to hold the bits. I need this array type due to some later functions in the program. It's more convenient for me. I created a function to shift right the register, and another function for the scrambler. The code can be seen below:

void leftshift(short *in, short *out, unsigned long len, unsigned short shift) {

    unsigned long i;

    for (i = 0; i < len - shift; i++) {
        out[i] = in[i + shift];
    }

    for (i = len - shift; i < len; i++) {
        out[i] = 0;
    }
}

void rightshift(short *in, short *out, unsigned long len, unsigned short shift) {

    unsigned long i;

    for (i = len - 1; i >= shift; i--) {
        out[i] = in[i - 1];
    }

    for (i = 0; i < shift; i++) {
        out[i] = 0;
    }
}

void scrambler(short *in, short *out, unsigned long len, short *initial_state) {

    unsigned long i;
    short carry;
    short *shift_register = initial_state;

    for (i = 0; i < len; i++) {
        carry = (shift_register[3] + shift_register[6]) % 2;
        rightshift(shift_register, shift_register, 7, 1);
        shift_register[0] = carry;
        out[i] = (in[i] + carry) % 2;
    }
}

Now, the point is that as part of the descrambler process, I need to code the inverse of the scrambler. In my scrambler I'm doing right shift. Does the inverse of it involve just doing a left shift, and leaving the tap sequence and initial configuration of register the same? While, if I do a left shift and check the result, it is not the same result as the initial input. Any ideas?

EDIT:

int main(void) {

    const unsigned SIZE = 24;

    short in[SIZE] = { 0, 0, 0, 0, 1, 0, 0, 0, 
                       0, 1, 1, 1, 0, 0, 1, 0,
                       1, 0, 0, 1, 1, 1, 0, 0 };
    short init[7] = { 1, 1, 1, 1, 1, 1, 1 };

    short *out_scrambler = (short *)malloc(sizeof(short)*SIZE);
    short *out_descrambler = (short *)malloc(sizeof(short)*SIZE);

    scrambler(in, out_scrambler, SIZE, init);
    scrambler(out_scrambler, out_descrambler, SIZE, init);

    return 0;
}

All in all, this looks very inefficient. Any reason why you aren't using look-up tables? — Lundin, Aug 26 '16 at 10:57

score 1 · Accepted Answer · answered Aug 26 '16 at 10:47

1

The scrambling process is its own inverse; you just need to XOR with the same sequence again.

(a ^ b) ^ b == a

answered Aug 26 '16 at 10:47

Oliver Charlesworth

267,707
33
569
680

Yes, I though about it. But, if I just call the same scrambler function twice, where in the second call I make the output of the first one as input to the second call, the end result is not the same. I mean `out_descrambler != in`, in my edited code segment. – typos Aug 26 '16 at 11:00
@typos - That sounds like you just have a bug, which can be resolved with standard debugging practices. – Oliver Charlesworth Aug 26 '16 at 11:01
@typos It doesn't work in your edited part because the scrambler is modifying the same state as the descrambler. – Art Aug 26 '16 at 11:04
@typos You need separate "state"s for both the scrambler and descrambler AND you need to start them from the same initial state both before scrambling and before descrambling. – TripeHound Aug 26 '16 at 11:56
@Art yes, it was a bug. Basically, the scrambler function was modifying the `init` array too. Although, I tried to do an assignment like `short *shift_register = initial_state;`, hoping that only the `shift_register` will be modified, and `initial_state` will stay unmodified. Any way to change this around? – typos Aug 26 '16 at 12:15
@TripeHound What do you mean with "separate state"? Basically, if I reset the initial state to the original initial state after first scramble function, and call scramble function again, it reverses the effect of the first scramble function, which is what I want. – typos Aug 26 '16 at 12:36
1

@typos That should work, but I assumed the transmitter and receiver (of a given message) would be in different places, so would naturally have separate states. If communication is bi-directional (one "node" sends and receives) then the transmitter and receiver _on the same node_ would probably want separate "states" so that there's no chance of them interfering with each other. The bigger problem with a scheme like this would be ensuring both ends of a Tx/Rx link are initialised to the _same_ state before sending/receiving a message. – TripeHound Aug 26 '16 at 12:48
@TripeHound Thanks, got it. – typos Aug 31 '16 at 11:39

Art · Answer 2 · 2016-08-26T10:59:53.553

You have A xor X = B, your question is then how to get A from B, right? Or am I missing something here?

A xor X = B => B xor X = A

Also, your whole lfsr can be simplified to something like:

uint8_t state;
outbit = ((state >> 7) ^ (state >> 4)) & 1;
state = (state >> 1) | outbit;

The whole point of lfsrs is that they are insanely cheap. It's pretty counter-productive to implement them using 128 times more memory and a magnitude or three more instructions than necessary.

How to inverse LFSR and shift register in C?

2 Answers2