C/C++中基于有限域的计算器

计算机在进行复杂的计算时，其本质上进行的是一系列的最基础的加法运算，因为乘除法本质上也是加法。因此，在我们开展网络编码的应用学习之前，师兄安排了这么一章。经过这章的学习，你将熟悉如何进行编码操作。等到后面章节，等引入网络拓扑之后，将这些编码操作放在网络的中间节点进行执行，这就是网络编码的方案了。

有限域运算库

我们不需要自己再重新写运算库了，只需要include现有的库即可。简单介绍一下我们之前写好的库。大家可以在本书配套的代码中找到。

前面介绍过，由于现代计算机都是字节主导的，所有寄存器都是以字节为基本单位的。因此，在实际使用中使用 $GF(2^8)$ 这个域的情况特别多。为了具有一般性，我们提供的域可以是 $GF(2^m), m\in[1-12]$ 。当然了，大家也可以使用别人提供的库，我最开始的时候采用的就是田纳西大学一个老师写的运算库。

下面我简单介绍一下有限域运算库的基本原理。采用有限域运算可以回避浮点运算，也就是说计算的过程中不会产生小数，所以计算的效率较高。另一方面，由于有限域上的元素个元素个数有限，其运算结果也是非常有限的。比如说，在 $GF(256)$ 域上，任意两个数相乘的结果一共也只有 $256\times 256$ 个。由于我们变量类型byte类型就可以表达该域上的数，所以为了提高计算效率，我们只需要采用 $256\times 256 = 64KBytes$ 空间来事先保存这所有的结果，那么在实际计算的过程中，就不用再计算了。只需要查表即可。比如：我们需要计算 $54\times 129$ 的值，只需要直接访问二维数组的 $data[53][128]$ 的值即可。进行变量访问时不需要再重复进行大量的移位操作，因而能够极大地节省时间。类似地，域上的两个数相除也建立一个表，需要计算时，直接访问内存即可。

那么大家一定有一个疑问，既然预先生成计算结果表如此方便，那岂不是特别好。任何域上的计算都直接用查表法就好了。这里就涉及到一个Tradeoff的问题。因为用来存储结果的二维表的尺寸是随着域的大小增加的。当域特别大的时候，我们就需要非常大的空间来存表，这就显得不划算了。比方说，在 $GF(2^{12})$ 上，我们的乘法表的尺寸就得是 $2^{12}\times 2^{12} \times 4=64MB$ 空间才够存储，其中需要乘以4是因为byte类型已经不够存储占12bit位的数，必须采用int类型所有乘以4个字节。所以说，查表法本质上是用空间换取时间。大量的实践表明 $GF(256)$ 这个大小的域能获得一个较好的平衡点，能够以较小的计算开销获得较高的计算效率。

另外，我们还没有说到加法和减法操作，在 $GF(2^m)$ 类型的域上，加法和减法都用异或运算，在计算时，只需要逐字逐句相与即可。计算开销已经非常小，无需再单独构造表。

开始我们的第一个编码工作！

说了那么多，这节我们开始我们的第一个编码工作。实现一个超简单的有限域运算器。我们用打算用vs开发。请大家自行安装vs2013或者vs2015,安装过程可自行查资料，这个很简单。考虑到很多同学在开始学习之前，并没有接触过vs开发环境，因此，我们的前两个实例都是图文并茂德的，属于手把手教的类型。照着做，我觉得大家应该都能搞明白。等大家程序编出来后，我觉得大家可以再回过头来理解理解MFC的框架，理解界面的设计，变量的绑定，消息的相应等操作。

打开Visual Studio，不管哪个版本，相信你都能在在左上角的工具栏找到“文件—新建—项目”大胆地点下去。如下图：

在新建的项目中，按“模板—Visual C++—MFC”的路径，新建一个MFC的应用程序。这时，你还需要为它起个名字，并存储在一个自定义的位置，如下图：

这时候会弹出来MFC的应用程序向导，如下图：

其实真正有用的是下图，在“应用程序类型”一栏要选择“基于对话框”；“MFC的使用”一栏，选择“在静态库中使用”。

后面的就是个性化的一些选项，懒人同志们可以直接单击“完成”(^=^) 完成后，我们就可以看到这样的一个对话框了。

在右侧的工具箱，我们找到“Edit Control”（编辑控制）、“Static Text”（静态文字）、“Button”（按钮）3个控件。

如果因为各种各样的迷之问题，你找不到工具箱了，请从“视图—工具箱”中把它拯救出来。

下面开始布局吧，布局成下图这个样子：

并为“Button”和“Static Text”改好名字，如上图。接下来，我们就要绑定变量了，使得前台看到的这些编辑框，按钮能够和后台的某个变量相关联上，然后我们在代码里就能对对话框中的数据进行读取和赋值了。

将“类别”改为“Value”；“变量类型”选择“int”型，并为这个变量起一个名字“m_nAlter1“。这里我们采用“匈牙利命名法”。以此类推，将后面两个“Edit Control”分别改为“m_nAlter2”和“m_nResult”。

后面我们为第一个“Static Text”修改ID，称为“IDC_m_chOperator”（疑问），并为其添加char型变量，起名叫做“m_chOperator”.

接下来，打开“类视图”，右键单击（疑问），向这个类添加一个变量，如下图：

我们为这个变量起名叫做“m_nType”,修改变量类型为“unsigned int”。其目的是保证输入一个正数，当m_nType=1时，控制“IDC_m_chOperator”，使计算器做加法运算，以此类推。界面的准备工作就算告一段落了，后面我们将逐步完成计算机后台的程序代码。

依次把+，-，*，/，^,Calculate按钮的ID修改为IDC_BUTTON_Add，IDC_BUTTON_Sul,IDC_BUTTON_Mul,IDC_BUTTON_Div,IDC_BUTTON_Exp,IDC_BUTTON_Cal。双击“+”加法按钮，写入如图的代码，后面以此类推。

void CCalculatorOverGaloisFieldDlg::OnBnClickedButtonAdd()
{
    // TODO:  在此添加控件通知处理程序代码
    UpdateData(TRUE);
    m_nType = 1;
    m_chOperator = "+";
    UpdateData(FALSE);
}


void CCalculatorOverGaloisFieldDlg::OnBnClickedButtonSub()
{
    // TODO:  在此添加控件通知处理程序代码
    UpdateData(TRUE);
    m_nType = 2;
    m_chOperator = "-";
    UpdateData(FALSE);

}


void CCalculatorOverGaloisFieldDlg::OnBnClickedButtonMul()
{
    // TODO:  在此添加控件通知处理程序代码
    UpdateData(TRUE);
    m_nType = 3;
    m_chOperator = "*";
    UpdateData(FALSE);
}


void CCalculatorOverGaloisFieldDlg::OnBnClickedButtonDiv()
{
    // TODO:  在此添加控件通知处理程序代码
    UpdateData(TRUE);
    m_nType = 4;
    m_chOperator = "/";
    UpdateData(FALSE);
}


void CCalculatorOverGaloisFieldDlg::OnBnClickedButtonExp()
{
    // TODO:  在此添加控件通知处理程序代码
    UpdateData(TRUE);
    m_nType = 5;
    m_chOperator = "^";
    UpdateData(FALSE);
}

后面我们将有限域运算库的头文件拷贝到我们创建的vs根目录下，并在代码开头，进行引用（写上 #include ”gf.c“）双击“Calculate”按钮，对源代码中已经写好的函数进行引用，写入以下代码。基于有限域的计算函数(乘、除、次方依次为mul,div,exp)。

void CCalculatorOverGaloisFieldDlg::OnBnClickedButtonCal()
{
    // TODO:  在此添加控件通知处理程序代码
    UpdateData(TRUE);
    gf_init(m, prim_poly[m]);
    if (m_nAlter1 > pow(2.0, m) || m_nAlter2 > pow(2.0, m))
    {
        MessageBox(_T("First value is greater than field size."));
        return;
    }
    if (m_nType == 1)
    {
        m_nResult = gf_add(m_nAlter1, m_nAlter2);
    }
    else if (m_nType == 2)
    {
        m_nResult = gf_sub(m_nAlter1, m_nAlter2);
    }
    else if (m_nType == 3)
    {
        m_nResult = gf_mul(m_nAlter1, m_nAlter2);
    }
    else if (m_nType == 4)
    {
        m_nResult = gf_div(m_nAlter1, m_nAlter2);
    }
    else if (m_nType == 5)
    {
        m_nResult = gf_exp(m_nAlter1, m_nAlter2);
    }
    UpdateData(FALSE);
}

然后将这个计算器定义在伽罗华域上，先在对话框中把最上方的“Static Text”和“Edit Control”两个控件按如图的方式摆放，并写上文字。再给“Edit Control”绑定一个int类型的变量，起个名字，称为“m”。

注意上面图中，我们有一行代码gf_init(m, prim[m]),这句代码的意义在于，对有限域进行初始化，而初始化的目的就是为了建立乘法表和除法表。

通过阅读代码，大家能够发现，我们原本在实数域上的加法 $a+b$ ，直接通过gf_add(a,b)来实现了。在有限域使用完毕后，使用如下代码：

gf_uninit();

为了方便使用，可以在OnInitDialog()函数给m,m_chOperator,m_nType变量赋初值。在该函数的如下图位置添加如下代码。

// TODO:  在此添加额外的初始化代码
    m = 8;
    m_chOperator = "+";
    m_nType = 1;
    UpdateData(FALSE);

    return TRUE;  // 除非将焦点设置到控件，否则返回 TRUE

为保证进行计算的数在我们的定义内，我们对其加上限制，如果超出我们定义的范围，就弹窗报错。

到此为止，就完成了有限域上计算机的基本雏形了。。尝试着编译、链接、运行吧。希望你能一切顺利，看到自己的程序顺利运行。如果有些小问题，经过调试，我相信一定能成功。

C/C++中基于有限域的计算器

C/C++中基于有限域的计算器

有限域运算库

开始我们的第一个编码工作！

results matching ""

No results matching ""