C++ : Shift register, SNRZI encoder/decoder

EDIT: solved, thx to Dialecticus, the correct code is in the second "frame" (?).

i have to write a program which will encode and decode large bit streams from/to files. The coding is Scrambled Non Return to Zero Invert, which is being used in the serial video data transmission. First i 开发者_如何学编程had to try out the functionality of my algorithm on some short and simple bit streams, e.g. a preamble 3FF 000 000 (10 bit words) which represents 10 ones and 20 zeros when written binary.

Here is the scrambler drawing: http://i.stack.imgur.com/ef3XP.gif

I wrote a test console program just like on the drawing which should encode this preamble and then decode the answer to get the starting preamble bit stream. This doesn't work, i.e. the decoder doesn't return the preamble. Here is it (i hope it is readable):

The code like Dysaster suggests:

#include "stdafx.h"
#include<iostream>
#include<vector>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
// Encoder -----------------------------------------------------------------------------------------------------------------------------------
cout<< endl <<" Encoder "<< endl;

// create an input vector and initialize it with 3FF 000 000
bool bInput[] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
vector< bool > vbInput( bInput, bInput + sizeof( bInput ) / sizeof( bool ) );

// create the shift register
bool bShiftReg[10] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };

// create an output vector 
vector< bool > vbOutput(40);

// iterator for the input
vector<bool>::iterator itInput = vbInput.begin();
cout<<"\n Input: ";
for( itInput = vbInput.begin(); itInput < vbInput.end(); itInput++)
    cout << " " << *itInput;

cout<<endl<<endl;

// iterator for the output
vector<bool>::iterator itOutput = vbOutput.begin();

for( itInput = vbInput.begin(); itInput < vbInput.end(); itInput++)
{
    // handle first and last values separately
    bShiftReg[ 9 ] = bShiftReg[ 9 ] ^ bShiftReg[ 8 ];
    bShiftReg[ 0 ] = *itInput ^ ( bShiftReg[ 4 ] ^ bShiftReg[ 8 ] );

    bool bTempReg[2];
    bTempReg[0] = bShiftReg[0];
    bTempReg[1] = bShiftReg[9];

    // shift operation
    for( unsigned char ucIndex = 8; ucIndex > 0; ucIndex-- )
    {
        bShiftReg[ ucIndex ] = bShiftReg[ ucIndex - 1 ];
    }

    bShiftReg[0] = bTempReg[0];
    bShiftReg[9] = bTempReg[1];

    // write to output
    //*itOutput = static_cast< int > ( bShiftReg[ 9 ] );
    *itOutput = bShiftReg[ 9 ];

    cout<<"\n Schift Reg: ";
    for( int i=0;i<10;i++)
    { cout << " " << bShiftReg[i]; }

    cout<<" Output: " << *itOutput;

    itOutput++;
}
cout<<"\n Output: ";
for( itOutput = vbOutput.begin(); itOutput < vbOutput.end(); itOutput++)
    cout << " " << *itOutput;

cout<<endl<<endl;

// Decoder -----------------------------------------------------------------------------------------------------------------------------------

cout<< endl <<" Decoder "<< endl;

// load the old ouput to the new input but use only bits 10:40
itOutput = vbOutput.begin() + 10;
for( itInput = vbInput.begin(); itInput < vbInput.end() - 10; itInput++)
{
    *itInput = *itOutput;
    itOutput++;

}

cout<<"\n Input: ";
for( itInput = vbInput.begin(); itInput < vbInput.end(); itInput++)
    cout << " " << *itInput;

// reset the shift reg
for(int i = 0;i<10;i++) bShiftReg[i] = 1;

// set output iterator to the begin of the vector
itOutput = vbOutput.begin();

for( itInput = vbInput.begin(); itInput < vbInput.end(); itInput++)
{
    // shift operation
    for( unsigned char ucIndex = 9; ucIndex > 1; ucIndex-- )
    {
        bShiftReg[ ucIndex ] = bShiftReg[ ucIndex - 1 ];
    }

    // write to output
    *itOutput = ( ( *itInput ^ bShiftReg[0] ) ^ bShiftReg[5] ) ^ bShiftReg[9];

    // write the first and second values
    bShiftReg[ 1 ] = bShiftReg[ 0 ] ^ *itInput;
    bShiftReg[ 0 ] = *itInput;

    cout<<"\n Schift Reg: ";
    for( int i=0;i<10;i++)
    { cout << " " << bShiftReg[i]; }

    cout<<" Output: " << *itOutput;

    itOutput++;
}
cout<<"\n Output: ";
for( itOutput = vbOutput.begin(); itOutput < vbOutput.end(); itOutput++)
    cout << " " << *itOutput;

cout<<endl<<endl;


return 0;
}

console output:

Encoder

Input: 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Output: 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 0 1 0 1

Decoder

Input: 0 1 0 1 0 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0

Output: 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 1 0

------------------- end console output

the code like Dialecticus suggests:

#include "stdafx.h"

#include<iostream>
#include<vector>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
// Encoder -----------------------------------------------------------------------------------------------------------------------------------
cout<< endl <<" Encoder "<< endl;

// create an input vector
bool bInput[] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
//bool bInput[] = { 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0 };
vector< bool > vbInput( bInput, bInput + sizeof( bInput ) / sizeof( bool ) );

// create the shift register
//bool bShiftReg[10] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
bool bShiftReg[10] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };

// create an output vector 
vector< bool > vbOutput(40);

// iterator for the input
vector<bool>::iterator itInput = vbInput.begin();
cout<<"\n Input: ";
for( itInput = vbInput.begin(); itInput < vbInput.end(); itInput++)
    cout << " " << *itInput;

cout<<endl<<endl;

// iterator for the output
vector<bool>::iterator itOutput = vbOutput.begin();

for( itInput = vbInput.begin(); itInput < vbInput.end(); itInput++)
{
    // calculate values of every flipflop and the output and save them in a temp array
    bool bTempReg[10];
    bTempReg[0] = *itInput ^ ( bShiftReg[ 4 ] ^ bShiftReg[ 8 ] );
    bTempReg[1] = bShiftReg[0];
    bTempReg[2] = bShiftReg[1];
    bTempReg[3] = bShiftReg[2];
    bTempReg[4] = bShiftReg[3];
    bTempReg[5] = bShiftReg[4];
    bTempReg[6] = bShiftReg[5];
    bTempReg[7] = bShiftReg[6];
    bTempReg[8] = bShiftReg[7];
    bTempReg[9] = bShiftReg[8] ^ bShiftReg[9];
    *itOutput = bShiftReg[ 9 ];

    // assign values of the temp array to the flipflops
    for( unsigned char ucIndex = 0; ucIndex < 10; ucIndex++ )
    {
        bShiftReg[ ucIndex ] = bTempReg[ ucIndex ];
    }

    /*cout<<"\n Schift Reg: ";
    for( int i=0;i<10;i++)
    { cout << " " << bShiftReg[i]; }

    cout<<" Output: " << *itOutput;*/

    itOutput++;
}
cout<<"\n Output: ";
for( itOutput = vbOutput.begin(); itOutput < vbOutput.end(); itOutput++)
    cout << " " << *itOutput;

cout<<endl<<endl;

// Decoder -----------------------------------------------------------------------------------------------------------------------------------

cout<< endl <<" Decoder "<< endl;

// load the old ouput to the new input 
vbInput = vbOutput;

cout<<"\n Input: ";
for( itInput = vbInput.begin(); itInput < vbInput.end(); itInput++)
    cout << " " << *itInput;

// reset the shift reg
for(int i = 0;i<10;i++) bShiftReg[i] = 1;

// set output iterator to the begin of the vector
itOutput = vbOutput.begin();

for( itInput = vbInput.begin(); itInput < vbInput.end(); itInput++)
{
    // calculate values of every flipflop and the output and save them in a temp array
    bool bTempReg[10];
    bTempReg[0] = *itInput;
    bTempReg[1] = bShiftReg[ 0 ] ^ *itInput;
    bTempReg[2] = bShiftReg[1];
    bTempReg[3] = bShiftReg[2];
    bTempReg[4] = bShiftReg[3];
    bTempReg[5] = bShiftReg[4];
    bTempReg[6] = bShiftReg[5];
    bTempReg[7] = bShiftReg[6];
    bTempReg[8] = bShiftReg[7];
    bTempReg[9] = bShiftReg[8];
    *itOutput = ( ( *itInput ^ bShiftReg[0] ) ^ bShiftReg[5] ) ^ bShiftReg[9];

    // assign values of the temp array to the flipflops
    for( unsigned char ucIndex = 0; ucIndex < 10; ucIndex++ )
    {
        bShiftReg[ ucIndex ] = bTempReg[ ucIndex ];
    }

    /*cout<<"\n Schift Reg: ";
    for( int i=0;i<10;i++)
    { cout << " " << bShiftReg[i]; }
    cout<<" Output: " << *itOutput;*/

    itOutput++;
}
cout<<"\n Output: ";
for( itOutput = vbOutput.begin(); itOutput < vbOutput.end(); itOutput++)
    cout << " " << *itOutput;

cout<<endl<<endl;


return 0;
}

console output:

Encoder

Input: 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Output: 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1

Decoder

Input: 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 Output: 0 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0

im not sure about the order of shifting and writing to the output but it doesn't work either way. i really do appreciate your help, thank you!

EDIT: new version of code and console output. now the output of the descrambler looks similar to the input of the scrambler but it's rotated and there are 8 ones instead of 10. it doesn't matter if i make the output vector longer, e.g. to 40 bits.

I haven't read the decoding part of the code, but in the encoding, there is a big issue: you calculate bits 0 and 9 after you perform the shift, which is incorrect. You need to calculate them before you shift your main registers, save them in temp variables (actually it is safe to write #9, but not #0), shift the LFSR, put the calculated bits back in.

What you are doing now is effectively using bits 3 and 7 as tap points, and calculating bit #9 as bit#7 XOR bit#9 instead of the specified algorithm.

I expect a similar error on the decoding side, but didn't check.

Okay, I found one possible bug. While decoding you calculate output after you shifted all registers, but while encoding you calculate output before the shifting. Which one is it? No, I got it wrong, second try:

EDIT: Imagine that output is just another register. I think that you need to calculate the value of output as your first operation within each loop. After that, calculate the value of all registers. After that assign those values to registers. Don't assign values before you calculated them all.

The bottom line: first calculate all values, and only then assign all values. In general case that implies using temporary variables. You can get away from using temps only if there are no loops.

The solution: introduce another set of registers (bTempReg), have 11 lines of code where you assign a value to each bTempReg[0..9] and to output, and then in mini-loop[0..9] assign values of bTempReg back to bShiftReg.