calculation of redundancy

Go To Last Post
8 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Hallo,
I am trying to implement a test transmission using the pocsag protocol. But the calculation of redundancy c(x)is not fair.
Can anyone look at the code program and tell me what has been done wrong?

I am using Code::Blocks editor
thank you for your attention

 

#include <math.h>
#include <stdio.h>
#include <limits.h>
#include <string.h>

#define BITMASK(b) (1 << ((b) % CHAR_BIT))
#define BITSLOT(b) ((b) / CHAR_BIT)
#define BITSET(a, b) ((a)[BITSLOT(b)] |= BITMASK(b))
#define BITCLEAR(a, b) ((a)[BITSLOT(b)] &= ~BITMASK(b))
#define BITTEST(a, b) ((a)[BITSLOT(b)] & BITMASK(b))
#define BITNSLOTS(nb) ((nb + CHAR_BIT - 1) / CHAR_BIT)

#define POCSAG_PREAMBLE_CODEWORD    0xAAAAAAAA
#define POCSAG_IDLE_CODEWORD        0x7A89C197
#define POCSAG_SYNCH_CODEWORD       0x7CD215D8

int             m = 5, n = 31, k = 21, t = 2, d = 5;
int                length = 31;
int             p[6];        /* irreducible polynomial */
int             alpha_to[32], index_of[32], g[11];
int             recd[31], data[21], bb[11];
int             numerr, errpos[32], decerror = 0;
int             seed;

 

/* Primitive polynomial of degree 5 */
void read_p()
{
    register int    i;
    p[0] = p[2] = p[5] = 1;
    p[1] = p[3] = p[4] =0;
    // 100101 (x^5 + x^2 +1)  1
}

void turnTo_bin(int *dst, int x)
{
    int i;

    for (i =sizeof x * CHAR_BIT-1; i >= 0; --i)
        *dst++ = x >> i & 1;

}

void sevendigitTo21bin(int n)
{
    int buf[128];            /* binary number */
    //int n = 1234563;         /* decimal number */

    unsigned int i;

    turnTo_bin(buf, n);

    int j = sizeof n * CHAR_BIT;
    int k = 0;
    //printf("%d\n", (j - 21));
    for (i = j - 21; i < j; ++i)
        data[k++] = buf[i];

    for (i = 0; i < 21; ++i)
        printf("%d",data[i]);

    getEncoder();

}

void generate_gf()
/*
 * generate GF(2**m) from the irreducible polynomial p(X) in p[0]..p[m]
 * lookup tables:  index->polynomial form   alpha_to[] contains j=alpha**i;
 * polynomial form -> index form  index_of[j=alpha**i] = i alpha=2 is the
 * primitive element of GF(2**m)
 */
{
    register int    i, mask;
    mask = 1;
    alpha_to[m] = 0;
    for (i = 0; i < m; i++) {
        alpha_to[i] = mask;
        index_of[alpha_to[i]] = i;
        if (p[i] != 0)
            alpha_to[m] ^= mask;
        mask <<= 1;
    }
    index_of[alpha_to[m]] = m;
    mask >>= 1;
    for (i = m + 1; i < n; i++) {
        if (alpha_to[i - 1] >= mask)
          alpha_to[i] = alpha_to[m] ^ ((alpha_to[i - 1] ^ mask) << 1);
        else
          alpha_to[i] = alpha_to[i - 1] << 1;
        index_of[alpha_to[i]] = i;
    }
    index_of[0] = -1;
}

void gen_poly()
/*
 * Compute generator polynomial of BCH code of length = 31, redundancy = 10
 * (OK, this is not very efficient, but we only do it once, right? :)
 */
{
    register int    ii, jj, ll, kaux;
    int             test, aux, nocycles, root, noterms, rdncy;
    int             cycle[15][6], size[15], min[11], zeros[11];
    /* Generate cycle sets modulo 31 */
    cycle[0][0] = 0; size[0] = 1;
    cycle[1][0] = 1; size[1] = 1;
    jj = 1;            /* cycle set index */
    do {
        /* Generate the jj-th cycle set */
        ii = 0;
        do {
            ii++;
            cycle[jj][ii] = (cycle[jj][ii - 1] * 2) % n;
            size[jj]++;
            aux = (cycle[jj][ii] * 2) % n;
        } while (aux != cycle[jj][0]);
        /* Next cycle set representative */
        ll = 0;
        do {
            ll++;
            test = 0;
            for (ii = 1; ((ii <= jj) && (!test)); ii++)
            /* Examine previous cycle sets */
              for (kaux = 0; ((kaux < size[ii]) && (!test)); kaux++)
                    if (ll == cycle[ii][kaux])
                        test = 1;
        } while ((test) && (ll < (n - 1)));
        if (!(test)) {
            jj++;    /* next cycle set index */
            cycle[jj][0] = ll;
            size[jj] = 1;
        }
    } while (ll < (n - 1));
    nocycles = jj;        /* number of cycle sets modulo n */
    /* Search for roots 1, 2, ..., d-1 in cycle sets */
    kaux = 0;
    rdncy = 0;
    for (ii = 1; ii <= nocycles; ii++) {
        min[kaux] = 0;
        for (jj = 0; jj < size[ii]; jj++)
            for (root = 1; root < d; root++)
                if (root == cycle[ii][jj])
                    min[kaux] = ii;
        if (min[kaux]) {
            rdncy += size[min[kaux]];
            kaux++;
        }
    }
    noterms = kaux;
    kaux = 1;
    for (ii = 0; ii < noterms; ii++)
        for (jj = 0; jj < size[min[ii]]; jj++) {
            zeros[kaux] = cycle[min[ii]][jj];
            kaux++;
        }
    printf("This is a (%d, %d, %d) binary BCH code\n", length, k, d);
    /* Compute generator polynomial */
    g[0] = alpha_to[zeros[1]];
    g[1] = 1;        /* g(x) = (X + zeros[1]) initially */
    for (ii = 2; ii <= rdncy; ii++) {
      g[ii] = 1;
      for (jj = ii - 1; jj > 0; jj--)
        if (g[jj] != 0)
          g[jj] = g[jj - 1] ^ alpha_to[(index_of[g[jj]] + zeros[ii]) % n];
        else
          g[jj] = g[jj - 1];
      g[0] = alpha_to[(index_of[g[0]] + zeros[ii]) % n];
    }
    printf("g(x) = ");
    for (ii = rdncy; ii >= 0; --ii) {
      printf("%d", g[ii]);
      if (ii && ((ii % 70) == 0))
        printf("\n");
    }
    printf("\n");
}

void encode_bch()
/*
 * Calculate redundant bits bb[], codeword is c(X) = data(X)*X**(n-k)+ bb(X)
 */
{
    register int    i, j;
    register int    feedback;
    for (i = 0; i < length - k; i++)
        bb[i] = 0;
    for (i = k - 1; i >= 0; i--) {
        feedback = data[i] ^ bb[length - k - 1];
        if (feedback != 0) {
            for (j = length - k - 1; j > 0; j--)
                if (g[j] != 0)
                    bb[j] = bb[j - 1] ^ feedback;
                else
                    bb[j] = bb[j - 1];
            bb[0] = g[0] && feedback;
        } else {
            for (j = length - k - 1; j > 0; j--)
                bb[j] = bb[j - 1];
            bb[0] = 0;
        };
    };
};

int getEncoder()
{
   int i;
    /* ENCODE */
    encode_bch();            /* encode data */

   for (i = 0; i < length - k; i++)
        recd[i] = bb[i];    /* first (length-k) bits are redundancy */
    for (i = 0; i < k; i++)
        recd[i + length - k] = data[i];    /* last k bits are data */
    printf("\n");

    /*
     *printf("b(x) = data(x)*x(power[n-k])mod[g(x)]\n");
     *printf("c(x) = data(x)*x(power[n-k]+b(x)\n");
     */
    printf("c(x) = ");

    char recdString[32];
    int result = 0;

    for(i=0; i<31; i++){
        recdString[i] = (recd[i] == 1) ? '1' : '0';
        printf("%d", recd[i]);
    }
    printf("\n");
    result = binstr2int(strrev(recdString));
   

   return result;

}
int Getbch()
{
    int codeword = getEncoder();

    return codeword;
}

char *strrev(char *str){
    int end = strlen(str)-1;
    int start = 0;

    while( start<end ){
        str[start] ^= str[end];
        str[end]   ^= str[start];
        str[start] ^= str[end];
        ++start;
        --end;
    }
    return str;
}

    /*
    *transform binary string to integer
    */
int binstr2int(char *bs){
    int ret = 0;
    int val = 1;

    while(*bs){
       if (*bs++ == '1') ret = ret + val;
       val = val*2;
    }
    return ret;
}

void srand_fun()
{
    int i;
  seed = 1;
    srand(seed);
    /* Randomly generate DATA */
    for (i = 0; i < k; i++)
        data[i] = (rand() & 67108864) >> 26;

}

    typedef struct  Packet
    {
        int  iPacket;
        char cPacket[4];
    }Packet;

    typedef struct tagASCII7Bit
    {
        char Letter;
        char Bits[8];
    } ASCII7Bit;

    extern ASCII7Bit ASCII7BitTable[128];

ASCII7Bit ASCII7BitTable[128]=
{
    {0, "0000000"},            //NULL
    {1, "0000001"},
    {2, "0000010"},
    {3, "0000011"},
    {4, "0000100"},
    {5, "0000101"},
    {6, "0000110"},
    {7, "0000111"},
    {8, "0001000"},
    {9, "0001001"},
    {10, "0001010"},
    {11, "0001011"},
    {12, "0001100"},
    {13, "0001101"},
    {14, "0001110"},
    {15, "0001111"},
    {16, "0010000"},        //DLE
    {17, "0010001"},
    {18, "0010010"},
    {19, "0010011"},
    {20, "0010100"},
    {21, "0010101"},
    {22, "0010110"},
    {23, "0010111"},
    {24, "0011000"},
    {25, "0011001"},
    {26, "0011010"},
    {27, "0011011"},
    {28, "0011100"},
    {29, "0011101"},
    {30, "0011110"},
    {31, "0011111"},
    {' ', "0100000"},
    {'!', "0100001"},
    {'\"',"0100010"},
    {'#', "0100011"},
    {'$', "0100100"},
    {'%', "0100101"},
    {'&', "0100110"},
    {'\'',"0100111"},
    {'(', "0101000"},
    {')', "0101001"},
    {'*', "0101010"},
    {'+', "0101011"},
    {',', "0101100"},
    {'-', "0101101"},
    {'.', "0101110"},
    {'/', "0101111"},
    {'0', "0110000"},
    {'1', "0110001"},
    {'2', "0110010"},
    {'3', "0110011"},
    {'4', "0110100"},
    {'5', "0110101"},
    {'6', "0110110"},
    {'7', "0110111"},
    {'8', "0111000"},
    {'9', "0111001"},
    {':', "0111010"},
    {';', "0111011"},
    {'<', "0111100"},
    {'=', "0111101"},
    {'>', "0111110"},
    {'?', "0111111"},
    {'@', "1000000"},
    {'A', "1000001"},
    {'B', "1000010"},
    {'C', "1000011"},
    {'D', "1000100"},
    {'E', "1000101"},
    {'F', "1000110"},
    {'G', "1000111"},
    {'H', "1001000"},
    {'I', "1001001"},
    {'J', "1001010"},
    {'K', "1001011"},
    {'L', "1001100"},
    {'M', "1001101"},
    {'N', "1001110"},
    {'O', "1001111"},
    {'P', "1010000"},
    {'Q', "1010001"},
    {'R', "1010010"},
    {'S', "1010011"},
    {'T', "1010100"},
    {'U', "1010101"},
    {'V', "1010110"},
    {'W', "1010111"},
    {'X', "1011000"},
    {'Y', "1011001"},
    {'Z', "1011010"},
    {'[', "1011011"},
    {'\\', "1011100"},
    {']', "1011101"},
    {'^', "1011110"},
    {'_', "1011111"},
    {'`', "1100000"},
    {'a', "1100001"},
    {'b', "1100010"},
    {'c', "1100011"},
    {'d', "1100100"},
    {'e', "1100101"},
    {'f', "1100110"},
    {'g', "1100111"},
    {'h', "1101000"},
    {'i', "1101001"},
    {'j', "1101010"},
    {'k', "1101011"},
    {'l', "1101100"},
    {'m', "1101101"},
    {'n', "1101110"},
    {'o', "1101111"},
    {'p', "1110000"},
    {'q', "1110001"},
    {'r', "1110010"},
    {'s', "1110011"},
    {'t', "1110100"},
    {'u', "1110101"},
    {'v', "1110110"},
    {'w', "1110111"},
    {'x', "1111000"},
    {'y', "1111001"},
    {'z', "1111010"},
    {'{', "1111011"},
    {'|', "1111100"},
    {'}', "1111101"},
    {'~', "1111110"},
    {127, "1111111"}    //DEL
};

 

/*
 *
 */
void OnCalculate()
{
    //UpdateData(TRUE);
    char m_Message[] = "5";
    //char m_EncodedMessage;
    char m_Reciever[] = "0000008";
    int iPOCSAGMsg[68];

    int i,j;
    Packet MyPacket;

    //first send preamble
    //72 bytes=576 bits of 101010.....
    for (i=0; i<72; i++)
    {
        //Send POCSAG_PREAMBLE_CODEWORD
        MyPacket.iPacket = POCSAG_PREAMBLE_CODEWORD;
    }

    for (i=0; i<68; i++)
    {
        //Send iPOCSAGMsg[i];
        iPOCSAGMsg[i] = MyPacket.iPacket;
    }

    int iReciever = atoi(m_Reciever);        //

    //Reset the codewords
    for (i=0; i<68; i++)
    iPOCSAGMsg[i] = POCSAG_IDLE_CODEWORD;

    //Initilizing Synch Codewords
    for (i=0; i<68; i+=17)
    iPOCSAGMsg[i] = POCSAG_SYNCH_CODEWORD;        // 0,17,35,53

    //compute address codeword
    int iStartFrame=iReciever%8;    

    // 100101101011010000|011
    // Bildung der function-bit
    int iAddress = iReciever >> 3;    
    iAddress  = iAddress<<2;            
    iAddress |=0x01;                          //A(x)
   

    read_p();                                     // read generator polynomial g(x)
    generate_gf();                             // generate the Galois Field GF(2**m)
    gen_poly();                                 // Compute the generator polynomial of BCH code
    printf("\n Add Data = ");
    sevendigitTo21bin(iAddress);        // iAddress shall be send to bch_Encoder
    printf("\n");
    int iAddressEnc = Getbch();

    printf("\n iAddresseEnc = %d\n", iAddressEnc);

  

    iPOCSAGMsg[iStartFrame*2+1] = iAddressEnc;
     printf("\n iPOCSAGMsg[iStartFrame*2+1] = %d\n", iPOCSAGMsg[iStartFrame*2+1]);

  

   //computer message codeword
    char TempBits[186];
    int iLen = strlen(m_Message);

    char cMessage[132];

    memset(cMessage,0,132);
    strcpy(cMessage, m_Message);
    printf("\n m_M cMessage= %c\n", cMessage);

    for (i=0; i<iLen; i++)
    {
        char c = cMessage[i];
        printf("\n cMessage= %c\n", c);

        int j;
        for (j=0; j<128; j++)
        if (ASCII7BitTable[j].Letter == c)
        {

        char* TempStr = ASCII7BitTable[j].Bits;
            printf("\n TempStr= %s\n", TempStr);

            strrev(TempStr);
            strcat(TempBits,TempStr);
            printf("\n TempBits= %s\n", TempBits);
            break;
        }
    }

 

    //EOT = End of Transmission
    char *TempStr = ASCII7BitTable[4].Bits;
    printf("\n EOT= %s\n", ASCII7BitTable[4].Bits);
    strrev(TempStr);
    strcat(TempBits,TempStr);
    printf("\n TempBits= %s\n", TempBits);

 

    //now we have bits of message!
    int iMessageCodewords = (iLen+1)*7/20;

    //printf("\n iMessageCodewords %d\n", iMessageCodewords);
    if (iMessageCodewords*20 != (iLen+1)*7)
    iMessageCodewords++;

    int iRemainBit = iMessageCodewords*20-7*(iLen+1);
    float fRemain = ceil((float) iRemainBit/7);
    iRemainBit = (int) fRemain;
    //printf("\n iRemainBit %d\n", iRemainBit);

    for (i=0; i<iRemainBit; i++)
    {
        TempStr = ASCII7BitTable[4].Bits;
        strrev(TempStr);
        strcat(TempBits,TempStr);
        
    }
    printf("\n Nach iRemain strlen(TempBits)= %d\n", strlen(TempBits));
    iRemainBit = strlen(TempBits)%20;

    

   //must remove iRemainBits from right of string
    TempBits[strlen(TempBits)-iRemainBit]= '\0';
 

    /*
    To declare an ``array'' of 2100 bits:
    uint32_t MSGBits[BITNSLOTS(2100)]; and SETBIT function
    */
    char MsgBits[BITNSLOTS(15)];

    for(i=0; i< sizeof(MsgBits); i++)
    {
        BITSET(MsgBits,i);
    }
    strcpy(MsgBits,TempBits);
    printf("\n MsgBits= %s\n", MsgBits);

    int k=strlen(TempBits)-1;
    int iCodeword=1;

    for (i=k; i>=0; i-=20)
    {
        int iMsgCode = 1<<31;
        //0x80000000
        int j;
        for (j=0; j<20; j++)
        {
            if (i-j>=0)
            iMsgCode |= MsgBits[i-j]<<(30-j);

    }

        read_p();                                       // read generator polynomial g(x)
        generate_gf();                               // generate the Galois Field GF(2**m)
        gen_poly();                                   // Compute the generator polynomial of BCH code

        printf("\n iMsgcode Data =%");
        sevendigitTo21bin(iMsgCode);        // iAddress shall be send to bch_Encoder

        iMsgCode = Getbch();
        printf("\n iMsgcode = %d\n", iMsgCode);
        if ((iStartFrame*2+1+iCodeword)%17 == 0)
        iCodeword++;

        iPOCSAGMsg[iStartFrame*2+1+iCodeword] = iMsgCode;
        //printf("\n iPOCSAGMsg = %d\n", iPOCSAGMsg);
        iCodeword++;
    }
    printf("\n iPOCSAGMsg = %d\n", iPOCSAGMsg);

 

    char szRes;
    char szTemp;
    for (i=0; i<68; i++)
    {
        printf("%X  ",iPOCSAGMsg[i]);
        szRes += szTemp;
        if (i%17==0)
        szRes += EOF;
        if (i%17==8 || i%17==16)
        szRes += EOF;

    }

 char m_EncodedMessage = szRes;      

   
}

int main()
{
    srand_fun();
    OnCalculate();

}

 

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Where did you get the original code? Has it been written for a CPU (ARM, PC, etc) where sizeof(int)==4 by any chance? Often such code comes a cropper when ported to an AVR where sizeof(int)==2. It's just one of the many reasons why "int" should never be used. In fact of all the basic C types (char, short, int, long, long long, etc) only char should be maintained. For everything else use stdint.h types like uint8_t, int16_t, uin32_t, etc then you will always get the bit width intended and code becomes more portable.

 

Another reason not to use int on an AVR which is an 8bit micro with very limited amounts of RAM is when you start doing things like:

int             alpha_to[32], index_of[32], g[11];
int             recd[31], data[21], bb[11];
int             numerr, errpos[32];

Although int is just 2 bytes for an AVR those lines just consumed 342 bytes of RAM. If you were using an AVR that only has 512 bytes of RAM (for example) that is a pretty significant chunk. If it's an AVR with 256 bytes you have REAL problems. So don't just blithely use "int" for everything. I haven't analysed it but suppose bb[11] there is an array of bits and each element only hold 0 or 1. Then you are using 22 bytes for something that could actually be packed into 2 bytes. So as you create each variable (or, worse, array of variables) in a micro program think "am I using the narrowest type possible to accomodate this?" and "does the data actually mean that the information can be packed into something even smaller than whole bytee?". Even an 8 bit is wasting 7 bits if it's only holding a 0/1 state.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quebracho seems to be the hardest wood.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Thanks for all the notifications made.
as I have said. I'm using the code first on Code :: Blocks
And that's after that I'll wear them with some modifications on the AVR.

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Code::Blocks is an editor. It is not a C compiler. So when you say you are using Code::Blocks it says nothing about how you are building/running the code. Do you mean "using the host C compiler on my PC"? Which compiler? Which OS?

 

Already I can see some fairly non-sensical code in there such as:

    char cMessage[132];

    memset(cMessage,0,132);
    strcpy(cMessage, m_Message);
    printf("\n m_M cMessage= %c\n", cMessage);
 char m_EncodedMessage = szRes;      
  
}

so is this:

 

a) code you wrote yourself?

 

b) code you got from the internet - if so where?

 

c) (what seems most likely) C++ code you got from the internet and have been trying to convert to plain C (all the "m_" in there suggest that it may have been class members)

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Ha That's what I thought the thread was about also.

 

However!

This code is crying out for a unittest or similar. I couldn't find an assert statement anywhere in all that code.

Until you write one (some) I can't see how you (or any other freak) can determine pass or fail.

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

 

 

https://www.codeproject.com/arti...

 

This is the link from the original code, which I tried to change it in C.
I thank you for the many remarks.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Sorry I forgot to say that
The author of code was inspired by this link

http://www.sxlist.com/techref/me...

 

I really apologize for my left way of approaching the AVR world.

My goal is to program a test transmission with the following tools.
> AVR STK500, ATmega16(L) 8, 4x16 LCD Display and 3x4 Keyboard.
At this moment I am in the programming phase of the redundancy calculation, ie  [A (x) * x ^ 10] mod [G (x)]
I read in a book that it is possible to do it from the polynom division with toggle.
I thank you in advance for the advice you could give me.