Utils_2.cpp
上传用户:speoil
上传日期:2021-10-06
资源大小:100k
文件大小:6k
源码类别:

3G开发

开发平台:

C/C++

  1. #include <stdio.h>
  2. #include <math.h>
  3. #include <stdlib.h>
  4. #include <iostream.h>
  5. #include <fstream.h>
  6. #include <ctype.h>
  7. #include <wchar.h>
  8. #include "Utils_1.h"
  9. #include "Utils_2.h"
  10. #include "LDPC_2.h"
  11. /************************************************************************
  12.  *
  13.  * GF(q)
  14.  *
  15.  ************************************************************************/
  16. // Static integers
  17. int GFq::q = -1;
  18. GFq GFq::alpha[MAX_Q];
  19. int GFq::reverse_alpha[MAX_Q];
  20. GFq GFq::inverse[MAX_Q];
  21. BOOLEAN GFq::IsPrimeQ = FALSE;
  22. BOOLEAN GFq::IsModuloOperations = FALSE;
  23. BOOLEAN IsPrime(int num)
  24. {
  25.    BOOLEAN Reply = TRUE;
  26.    for (int i = 2; i < num; i++)
  27.    {
  28.       if ((num % i) == 0)
  29.       {
  30.          Reply = FALSE;
  31.          break;
  32.       }
  33.    }
  34.    return Reply;
  35. }
  36. int GFq::log_2_q;
  37. int GFq::mask;
  38. void GFq::Initialize(int p_q)
  39. {
  40.    if (p_q == GFq::q)         // if already initialized with the same q
  41.    return;
  42.    if (p_q > MAX_Q)
  43.    {
  44.       cout << "GFq::Initialize: p_q exceeds MAX_Qn";
  45.       exit(1);
  46.    }
  47.    q = p_q;
  48.    //-----------------------------------------------------------------------
  49.    // Initialize 
  50.    //-----------------------------------------------------------------------
  51.    if ((q > 2) && IsPowerOfTwo(q))
  52.    {
  53.       // Store for use by other utilities
  54.       log_2_q = Intlog2(q);
  55.       mask = 0;
  56.       for (int i = 0; i < log_2_q; i++)
  57.       {
  58.          mask <<= 1;
  59.          mask |= 1;
  60.       }
  61.       switch(q)
  62.       {
  63.       case 4:  GenerateAlphas(2);   break;
  64.       case 8:  GenerateAlphas(3);   break;
  65.       case 16:  GenerateAlphas(4);   break;
  66.       case 32:  GenerateAlphas(5);   break;
  67.       case 64:  GenerateAlphas(6);   break;
  68.       case 256:  GenerateAlphas(8);   break;
  69.       default:
  70.          cout << "GFq::Initialize: Unsupported value of qn";
  71.          exit(1);
  72.       }
  73.       IsPrimeQ = FALSE;
  74.       IsModuloOperations = FALSE;
  75.    }
  76.    else
  77.    {
  78.       if (q == 2)
  79.       {
  80.          log_2_q = 1;
  81.          mask = 1;
  82.       }
  83.       IsModuloOperations = TRUE;
  84.       IsPrimeQ = IsPrime(q);
  85.    }
  86.    //-----------------------------------------------------------------------
  87.    // Calc inverse
  88.    //-----------------------------------------------------------------------
  89.    for (int i = 1; i < q; i++)
  90.       for (int j = 1; j < q; j++)
  91.       {
  92.          GFq g1(i), g2(j);
  93.          if ((g1 * g2) == GFq::One())
  94.             inverse[i] = g2;
  95.       }
  96. }
  97. void GFq::GenerateAlphas(int m)
  98. {
  99.   int generator_polynomial;
  100.   int X0 = 1, 
  101.       X1 = 1 << 1, 
  102.       X2 = 1 << 2,
  103.       X3 = 1 << 3,
  104.       X4 = 1 << 4,
  105.       X5 = 1 << 5,
  106.       X6 = 1 << 6,
  107. //      X7 = 1 << 7,
  108.       X8 = 1 << 8;
  109.   switch(m)
  110.     {
  111.     case 2:  generator_polynomial = X0 ^ X1 ^ X2;     break;
  112.     case 3:  generator_polynomial = X0 ^ X1 ^ X3;     break;
  113.     case 4:  generator_polynomial = X0 ^ X1 ^ X4;     break;
  114.     case 5:  generator_polynomial = X0 ^ X2 ^ X5;     break;
  115.     case 6:  generator_polynomial = X0 ^ X1 ^ X6;     break;
  116.     case 8:  generator_polynomial = X8 ^ X4 ^ X3 ^ X2 ^ X0; break;
  117.     default:
  118.       cout << "GFq::GenerateAlphas: Unidentified Galois fieldn";
  119.       exit(1);
  120.       break;
  121.     }
  122.   //------------------------------------------------
  123.   // Generate alphas
  124.   //------------------------------------------------
  125.   int x = 1;
  126.   int overflow = 1 << m;
  127.   for (int i = 0; i < (q-1); i++)
  128.   {
  129.      alpha[i].val = x;
  130.      x <<= 1;                // multiply by alpha
  131.      if (x & overflow)       // if overflowed
  132.         x ^= generator_polynomial;
  133.   }
  134.   //------------------------------------------------
  135.   // Generate reverse alphas: inverse function
  136.   //------------------------------------------------
  137.   for (int i = 0; i < (q-1); i++)
  138.      reverse_alpha[alpha[i].val] = i;
  139. }
  140. /************************************************************************************
  141.  *
  142.  * GF(q) Matrix
  143.  *
  144.  ************************************************************************************/
  145. matrix &Identity(int N)
  146. {
  147.    static matrix I;
  148.    I.Init(N, N);
  149.    for (int i = 0; i < N; i++)
  150.       I.Element(i,i) = 1;
  151.    return I;
  152. }
  153. matrix &matrix::Inverse()
  154. {
  155.    static matrix Result;
  156.    if (N != M)
  157.    {
  158.       cout << "Attempt to invert a nonsquare matrixn";
  159.       exit(1);
  160.    }
  161.    matrix Aux(*this);               // temporary storage for this
  162.    Result = Identity(N);      // temporary result
  163.    //------------------------------------------------------------
  164.    // Go through each column and eliminate unwanted rows
  165.    //------------------------------------------------------------
  166.    for (int j = 0; j < N; j++)
  167.    {
  168.       // find a remaining row where column is non zero
  169.       int NonZeroRow = -1;
  170.       for (int i = j; i < N; i++)
  171.       {
  172.          if (!Aux.Element(i,j).IsZero())
  173.          {
  174.             NonZeroRow = i;
  175.             break;
  176.          }
  177.       }
  178.       if (NonZeroRow == -1)
  179.       {
  180.          Result.SetNull();          // if matrix is singular
  181.          return Result;
  182.       }
  183.       if (NonZeroRow != j)          // Move row to desired position
  184.       {
  185.          Aux.SwitchRows(j, NonZeroRow);
  186.          Result.SwitchRows(j, NonZeroRow);
  187.       }
  188.       // Divide so that leading value is a one
  189.       GFq Multiplier = Aux.Element(j,j).Inverse();
  190.       Aux.MultRow(j, Multiplier);
  191.       Result.MultRow(j, Multiplier);
  192.       // Eliminate column at all other rows
  193.       for (int i = 0; i < N; i++)
  194.       {
  195.          if (i == j) continue;         // skip row at current column
  196.          if (!Aux.Element(i,j).IsZero())
  197.          {
  198.             GFq Eliminator = Aux.Element(i,j).Minus();
  199.             Aux.AddRow(i, j, Eliminator);
  200.             Result.AddRow(i, j, Eliminator);
  201.          }
  202.       }
  203.    }
  204.    return Result;
  205. }
  206. void matrix::Add(int row, check_node &Check, GFq Mult)
  207. {
  208.    for (int i = 0; i < Check.GetDegree(); i++)
  209.    {
  210.       int VarID = Check.GetEdge(i).LeftNode().GetID();
  211.       GFq label = Check.GetEdge(i).label;
  212.       Element(row, VarID) += Mult * label;
  213.    }
  214. }
  215. void matrix::Set(int row, check_node &Check)
  216. {
  217.    for (int i = 0; i < Check.GetDegree(); i++)
  218.    {
  219.       int VarID = Check.GetEdge(i).LeftNode().GetID();
  220.       GFq label = Check.GetEdge(i).label;
  221.       Element(row, VarID) = label;
  222.    }
  223. }