我在 Wikipedia 上找到了以下線性反饋移位暫存器程式的示例，但我根本不明白：
#include <stdint.h>
#include <stdio.h>
unsigned lfsr_fib()
{
uint16_t start_state = 0xACE1u; /* Any nonzero start state will work. */
uint16_t lfsr = start_state;
uint16_t bit; /* Must be 16-bit to allow bit<<15 later in the code */
unsigned period = 0;
do
{ /* taps: 16 14 13 11; feedback polynomial: x^16 x^14 x^13 x^11 1 */
bit = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5)) & 1u;
lfsr = (lfsr >> 1) | (bit << 15);
period;
}
while (lfsr != start_state);
return period;
}
int main()
{
printf("%d\n", lfsr_fib());
return 0;
}
uj5u.com熱心網友回復：
首先，關于 LFSR 的花絮。使用 LFSR 計算滾動反饋，最終確定單個位值。然后在將暫存器向下移動一位后，將該值放入暫存器的最高有效位。您發布的 LFSR 推進中的兩個最重要的操作是：
/* taps: 16 14 13 11; feedback polynomial: x^16 x^14 x^13 x^11 1 */
bit = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5)) & 1u;
lfsr = (lfsr >> 1) | (bit << 15);
bit = 您在該行中看到的位移對應于相應指數 >= 1 的多項式項。它們的一系列拉動和 XOR 最終用于計算最后一位。
((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5))
16 14 13 11
然后將該結果通過在將暫存器向下移位一位后將其放入前導位中來饋入：
lfsr = (lfsr >> 1) | (bit << 15);
當與適當的原始多項式一起使用時（其生成超出了本文的范圍，但如果你愿意的話，這是一個有趣的調查），這可以生成一個最大周期（所有值在序列開始之前就用完了重復，除了零，這是基本 LFSR 的死亡，希望有明顯的原因）。提供的代碼通過確保 2^N-1 不再出現原始素數來測驗這一點，其中 N 是 LFSR 的位寬。您提供的示例使用 16 位 LFSR，運行時將按預期列印 65535。八位版本如下所示：
unsigned lfsr_fib8()
{
uint8_t start_state = 0x01;
uint8_t lfsr = start_state;
uint8_t bit;
unsigned period = 0;
do
{ /* taps: 8 6 5 4 ; feedback polynomial: x^8 x^6 x^5 x^4 1 */
bit = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 4)) & 1u;
lfsr = (lfsr >> 1) | (uint8_t)(bit << 7);
period;
} while (lfsr != start_state);
return period;
}
正如預期的那樣，這將產生 255。最后，對于您的問題，一個 4 位版本。在這里，我們必須有一點創意（但不多），因為我們沒有只有 4 位寬的固有原生型別。沒關系。只需確保您只使用低半位元組，并且不要使用高于 0x0F 的任何值來啟動啟動狀態。
unsigned lfsr_fib4()
{
uint8_t start_state = 0x01;
uint8_t lfsr = start_state;
uint8_t bit;
unsigned period = 0;
do
{ /* taps: 4 1 ; feedback polynomial: x^4 x 1 */
bit = ((lfsr >> 0) ^ (lfsr >> 3)) & 1u;
lfsr = ((lfsr >> 1) | (uint8_t)(bit << 3)) & 0x0F;
period;
} while (lfsr != start_state);
return period;
}
正如預期的那樣，這將回傳 15。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/419671.html
標籤：
下一篇：系統呼叫如何讓父母等待孩子