c++ - 如何在 C++ 中为不同的多项式创建 LFSR

Question

我正在努力学习如何 right >>和 left << c++中的移位操作。我已经阅读了互联网上的一些文章和这里的一些主题，但我仍然感到困惑。我正在尝试根据用户输入编写一个 LFSR(线性反馈移位寄存器)，用户应该将 长度、种子和多项式抽头位置 作为 LFSR 代码的输入。

代码是这样的:

#include <iostream>
#include <string>
#include <cmath>

using namespace std;

int main()
{
    string seed;
    unsigned int length, pos;

    cout << "Type the length and the seed" << endl;
    cin >> length >> seed;
    cout << "Polynomial tap positions" << endl;
    cin >> pos;

    //Creating array with the LFSR size
    unsigned int *sizee = new unsigned int[length];
    //Convert the seed from char to int
    for (unsigned int i = 0; i < length; i++) {
        sizee[i] = seed[i] - '0';
    }
    //Shifting
    unsigned int seq = std::pow(2,length)-1;
    for (unsigned int i = 1; i <= seq ; i++) {
        //Shift Operation here
        //Show user the value
    }

    delete[] sizee;

    return 0;
}

如何向右移动位，例如，长度 = 5 的 LFSR 中的种子 00001 和 Tap 位置(Xor 位置)5 和 3 (x^5+x^3+1)？我希望获得类似这样的结果:00001 > 10000 > 01000 > 00100 > 10010，依此类推，直到循环结束，将斐波那契数列视为架构类型。

Answer 1

如果要在计算机上将 LFSR 编码为整数，首先需要了解 LFSR 和整数使用的表示形式。有两个重要的问题/差异:

• LFSRs 通常从 1 开始对它们的位进行编号，并在位处点击i 对应于多项式中有 xⁱ
• 整数通常从 0 开始对其位进行编号，位 i 对应于 2ⁱ
• 传统上，LFSR 的第 1 位显示在左侧，最高位显示在右侧
• 整数通常以big-endian形式书写，0位在右边，最高位在左边

当您将整数用于 LFSR 时，这会导致两件重要的事情:

• LFSR 的位 i 变成整数的位 i-1
• LFSR 的右移变为整数的左移。

因此您的基本 LFSR 步骤变为:

seed = (seed << 1) | parity(seed & polynomial)

其中 seed 是 LFSR 的内容(加上当您的整数大小大于 LFSR 长度时先前移出的额外位)，多项式 是抽头位 - - 为多项式中的每个 xⁱ 设置位 i-1 的整数，并且 parity 是一个函数计算一个整数中所有位的异或——可以在大多数 CPU 上使用标志技巧或一条指令来完成，但没有简单的方法用 C 来表达它。