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

Question

我正在尝试学习如何在 C++ 中进行 right >> 和 left << 移位操作。我已经阅读了互联网上的一些文章和这里的一些主题，但我仍然感到困惑。我正在尝试根据用户输入编写 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

首先，您将无法使用 >> 和 << 运算符，因为您有一个整数数组。

<< 和 >> 运算符仅为数字数据类型定义。您应该切换到仅使用 int。

对于单个 int，您的 LFSR 算法变为：

Calculate your tap bit: tapbit = necessary bits XORed ( ^ ) together
// ^ Note this will require shifts as well, I'd reccomend a for loop through all your taps

Shift register to the right: seed = seed >> 1;
Set the leftmost bit to the calculated tap bit: seed = seed | ( tapbit << length );

Answer 2

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

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

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

位i变为整数

i-1

LFSR 的右移变为整数的左移。

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

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

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

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

How to create a LFSR in c++ for different polynomials

c++

bit-manipulation

bit-shift