ForHosting KIT · Mathematik

LFSR-Schieberegister

Geben Sie eine Startreihe von Bits, die Abgriffspositionen und eine Schrittzahl an und erhalten Sie die Bitfolge eines Fibonacci-LFSR: Startwert 1000 mit Abgriffen 4 und 1 über 8 Schritte gibt 00011110 aus und endet bei 1101. Praktisch für CRC-Übungen. Kostenlos in Ihrem Browser.

Kostenlos
Läuft in Ihrem Browser
Ohne Anmeldung
Ihre Daten bleiben auf Ihrem Gerät

Im Browser ausführen – kostenlos API ansehen

Nutzen Sie es über WebAPIE-MailTelegramApp bald

Rechenbeispiel

Wenn Sie eingeben

Zustand: 1000
Tipper: 4, 1

Erhalten Sie

Länge: 4
Sequenz: 00011110
Endzustand: 1101

Ein linear rückgekoppeltes Schieberegister, oder LFSR, ist eine kompakte digitale Maschine, die eine Reihe von Bits speichert und bei jedem Taktimpuls XOR über einige Abgriffspositionen bildet, um ein neues Eingangsbit zu berechnen, während der Rest geschoben wird. Entwickler nutzen LFSR, um pseudozufällige Bitströme, zyklische Redundanzreste, Verwürfelungsfolgen und eingebaute Selbsttestmuster zu erzeugen, ohne eine Nachschlagetabelle zu speichern. Dieser Rechner nimmt den Anfangszustand des Registers als Zeichenkette aus Nullen und Einsen entgegen, eine Liste von Abgriffspositionen, die ab 1 von links gezählt werden, und die Anzahl der auszuführenden Taktschritte. Er implementiert ein Fibonacci-LFSR: jeder Schritt gibt das rechteste Bit aus, schiebt das Register um eine Stelle nach rechts und fügt links das XOR der abgegriffenen Bits ein.

Was ein Fibonacci-LFSR ist und wie jeder Takt ein Bit erzeugt

Ein linear rückgekoppeltes Schieberegister ist ein endlicher Automat, dessen nächstes Eingangsbit eine lineare Funktion seines aktuellen Inhalts ist, genommen über den zweielementigen Körper GF(2). In Hardware ist diese lineare Funktion einfach XOR. Die Fibonacci-Form, die dieser Endpunkt umsetzt, hält eine Reihe von n Bits und eine Liste von Abgriffspositionen.

Die Positionen sind von 1 links in der Zustandszeichenkette bis n rechts nummeriert. Bei jedem Takt liest die Engine die Bits an diesen Abgriffen, verknüpft sie per XOR zu einem einzigen Rückkopplungsbit, gibt das rechteste Bit als nächste Ausgangsstichprobe aus, schiebt jedes Bit um eine Stelle nach rechts und schreibt das Rückkopplungsbit in die frei gewordene linke Zelle.

Die Wiederholung dieses Schritts erzeugt eine deterministische Bitfolge, deren Periode höchstens 2^n minus eins beträgt: der All-Null-Zustand ist ein Fixpunkt, und jeder andere Zustand eines Maximalperioden-Polynoms (primitiv) durchläuft die restlichen 2^n minus eins von null verschiedenen Vektoren, bevor er sich wiederholt. Klassische Unterrichtspolynome wie x^4 plus x plus eins, das den Abgriffen 4 und 1 auf einem Vier-Bit-Register entspricht, erreichen diese Maximalperiode, wenn sie von einer von null verschiedenen Saat starten.

Galois-LFSR verknüpfen XOR in mehrere Zellen während des Schiebens und erzeugen für dasselbe Polynom einen verwandten, aber nicht identischen Strom; dieser Rechner emuliert die Galois-Verdrahtung nicht.

Anwendungsfälle

Unterrichtsübungen zu LFSR und CRC

Takten Sie ein Fibonacci-Register aus einer Saat und einer Abgriffsliste und vergleichen Sie die ausgegebene Bitfolge und den Endzustand mit der von Hand gelösten Hausaufgabe oder dem Polynom im Lehrbuch.

PRBS- und Selbsttest-Präfixe

Erzeugen Sie ein bekanntes Präfix eines Maximalperioden-LFSR-Stroms, um zu prüfen, dass ein FPGA, ein ASIC oder ein Software-Verwürfler nach dem Reset zu den angegebenen Abgriffen passt.

Orakel für HDL-Prüfstände

Speisen Sie Einheitstests mit einem deterministischen Bitdump, damit ein Verilog- oder VHDL-LFSR-Modell nicht stillschweigend die entgegengesetzte Schieberichtung oder bei 0 beginnende Abgriffe übernimmt.

Häufige Fragen

Wie taktet dieses linear rückgekoppelte Schieberegister jeden Schritt?

Es implementiert ein Fibonacci-LFSR. Das XOR der Bits an den ab 1 nummerierten Abgriffspositionen ist die Rückkopplung. Das rechteste Bit wird ausgegeben, das Register schiebt eine Stelle nach rechts, und das Rückkopplungsbit wird in die linkeste Zelle geschrieben.

Wie werden Abgriffspositionen nummeriert?

Abgriffe sind ab 1 nummeriert und werden von links in der state-Zeichenkette gezählt: das erste Zeichen ist Position 1 und das letzte ist Position n, wobei n die Registerlänge ist. Das Polynom x^4+x+1 auf vier Bits entspricht den Abgriffen 4 und 1.

Was erzeugt eine Saat aus lauter Nullen?

Alle Ausgangsbits bleiben 0 und das Register bleibt bei Nullen, weil XOR von Nullen null ist. Dieser Fixpunkt ist echtes LFSR-Verhalten, kein Fehler. Verwenden Sie eine von null verschiedene Saat für einen nichttrivialen Strom.

Was passiert, wenn ein Abgriff über die Registerlänge hinausgeht?

Der Lauf wird mit einem Hinweis abgelehnt, statt die Position umzubrechen. Jeder Abgriff muss zwischen 1 und der Anzahl der Bits im Startwert liegen, von links gezählt.

Wie lang kann die Folge eines LFSR höchstens werden?

Höchstens 2 hoch n minus 1 Bits, bevor sie sich wiederholt, wobei n die Registerlänge ist. Abgriffe mit maximaler Periode, etwa 4 und 1 bei vier Bits, erreichen diese Grenze ab jedem Startwert, der nicht nur aus Nullen besteht.

Ist das ein Fibonacci- oder ein Galois-LFSR?

Ein Fibonacci-LFSR: Bei jedem Schritt geht das rechte Bit hinaus, das Register rückt nach rechts und die XOR-Verknüpfung der Abgriffe kommt links hinein. Eine Galois-Verdrahtung ergibt eine verwandte, aber andere Folge und wird hier nicht nachgebildet.

Für Entwickler — API-Zugang

Alles auf dieser Seite ist auch per API verfügbar. Dieser Abschnitt richtet sich an Teams, die es in ihre eigenen Systeme einbinden möchten; alle anderen nutzen einfach das Tool oben.

Endpunkt

POSThttps://api.kit.forhosting.com/math/linear-feedback-shift-register

Authentifizierung per Bearer-Token. Ein einziger POST stellt die Aufgabe in die Warteschlange; das Ergebnis erhalten Sie per Webhook oder über einen signierten Link.

Aufruf aus Ihrem Stack

curl -X POST https://api.kit.forhosting.com/math/linear-feedback-shift-register \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"state":"1000","taps":[4,1],"steps":8}'

const res = await fetch("https://api.kit.forhosting.com/math/linear-feedback-shift-register", {
  method: "POST",
  headers: {
    "Authorization": `Bearer ${process.env.KIT_KEY}`,
    "Content-Type": "application/json"
  },
  body: JSON.stringify({
    "state": "1000",
    "taps": [
      4,
      1
    ],
    "steps": 8
  })
});
const { task_id } = await res.json();

import os, requests

res = requests.post(
    "https://api.kit.forhosting.com/math/linear-feedback-shift-register",
    headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
    json={
    "state": "1000",
    "taps": [
        4,
        1
    ],
    "steps": 8
},
)
task_id = res.json()["task_id"]

<?php
$res = file_get_contents("https://api.kit.forhosting.com/math/linear-feedback-shift-register", false, stream_context_create([
  "http" => [
    "method"  => "POST",
    "header"  => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
    "content" => '{"state":"1000","taps":[4,1],"steps":8}',
  ],
]));
$task = json_decode($res, true);

body := bytes.NewBufferString(`{"state":"1000","taps":[4,1],"steps":8}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/math/linear-feedback-shift-register", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)

Beispiel-Anfrage

{
  "state": "1000",
  "taps": [
    4,
    1
  ],
  "steps": 8
}

Beispiel-Antwort

{
  "task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
  "type": "math.linear_feedback_shift_register",
  "status": "queued",
  "_links": {
    "result": "/tasks/tsk_…/result"
  }
}

Die API arbeitet asynchron: Sie erhalten sofort eine task_id. Polling ist mit 1 Anfrage pro Sekunde erlaubt.

Preis

pro Anfrage$0.002

Der Preis steht auf der Seite – keine Tokens, keine Credits. Fehlgeschlagene Aufgaben werden nicht berechnet.

Limits

`max_length`	64
`max_steps`	4096

Fehler

HTTP	Code	Bedeutung
`401`	`unauthorized`	Der API-Schlüssel fehlt oder ist ungültig – prüfen Sie den Authorization-Header (Bearer).
`402`	`insufficient_balance`	Ihr Guthaben reicht für diese Aufgabe nicht aus – Aufladungen verfallen nicht.
`404`	`unknown_type`	Unbekannter Aufgabentyp – prüfen Sie das Feld „type“ gegen den Katalog.
`429`	`rate_limited`	Zu viele Anfragen – warten Sie kurz; Polling ist mit 1 Anfrage pro Sekunde erlaubt.

Technische Hinweise

Liegt ein Abgriff hinter der Registerlänge, schlägt die Aufgabe mit invalid_input fehl, statt eine Umwicklung zu erfinden.

Eingabevertrag, Abgriffsnummerierung, Antwortform und Fehler

Senden Sie per POST einen JSON-Körper mit drei Pflichtfeldern. state ist das Anfangsregister als Zeichenkette aus 0- und 1-Zeichen; das linkeste Zeichen ist Position 1 und die Länge der Zeichenkette ist die Registerbreite, von einem bis vierundsechzig Bits. Leerraum innerhalb von state wird ignoriert, sodass ein beabstandetes Nibble wie 1 0 0 0 akzeptiert wird. taps ist ein nicht leeres Array ganzzahliger, ab 1 nummerierter Positionen, deren Bits per XOR die Fibonacci-Rückkopplung bilden; jeder Abgriff muss zwischen 1 und der Registerlänge einschließlich liegen. steps ist die Anzahl der auszuführenden Takte, eine ganze Zahl von 1 bis 4096; jeder Takt gibt ein Ausgangsbit aus. Alias seed oder register für state, tap_positions für taps sowie n oder count für steps werden akzeptiert. Fehlende Felder, Nicht-Bits in state, Nichtganzzahlen, leere Abgriffslisten und Werte außerhalb der veröffentlichten Grenzen schlagen mit invalid_input fehl, nennen das Feld und werden nicht berechnet. Bei Erfolg gibt der Körper length, die kanonische state-Zeichenkette, taps und steps als Echo zurück; bits als Array von 0- und 1-Ganzzahlen in Taktordnung; sequence als dieselben Bits verkettet zum Kopieren; und final_state, den Registerinhalt nach dem letzten Schieben, damit ein Aufrufer die Maschine fortsetzen kann. Beispiel: state 1000, taps 4 und 1, steps 8 ergibt bits 0,0,0,1,1,1,1,0, sequence 00011110 und final_state 1101.

Wo sich eine API für LFSR-Bitfolgen bezahlt macht

Kurse im Digitalentwurf und HDL-Labore lassen Lernende ein Fibonacci-LFSR von Hand über einige Schritte takten und ein Datenblatt-Polynom mit einem Bitdump abgleichen; ein deterministisches Orakel, das dieselbe Nummerierung von links nach rechts und dieselbe Rechts-Schiebe-Konvention nutzt, beendet Streitereien darüber, welches Ende Bit null ist. Eingebaute Selbsttest- und PRBS-Generatoren in Silizium und FPGA-Geweben sind im Kern LFSR: Verifikationsskripte können diesen Endpunkt aufrufen, um ein bekanntes Präfix einer Maximalperiodenfolge zu erzeugen, und dann prüfen, dass das Gerät unter Test nach dem Reset dasselbe Präfix ausgibt. Fehlgeschlagene Validierung wird nicht berechnet. Aufgaben in Nachrichtentechnik und Codierung nutzen kurze LFSR als linearen Motor hinter CRC-Restprüfungen, Gold-Codes und additiver Verwürfelung; den Referenzstrom hier zu erzeugen, lässt einen Bewerter eine Studierendenimplementierung gegen einen stabilen JSON-Vertrag statt gegen einen Screenshot vergleichen. Weil die Umsetzung reines Parse-Tier A ist, kostet jeder erfolgreiche Aufruf den veröffentlichten Grundpreis $0.002 ohne Modell-Tokens und ohne ausgehenden Netzverkehr.

Technische Fragen

Was geschieht, wenn ein Abgriff die Registerlänge überschreitet?

Die Aufgabe schlägt mit invalid_input fehl. Ein Abgriff größer als n würde ein anderes Polynom beschreiben; der Handler lehnt Umwicklung ab, damit der Vertrag ehrlich bleibt.

Was kostet der Rechner für linear rückgekoppelte Schieberegister?

Das Browser-Werkzeug ist kostenlos. API-Anfragen nutzen das vorausbezahlte KIT-Guthaben zu $0.002 pro erfolgreichem Aufruf; ungültige Eingabe wird nicht berechnet.

Vollständige KIT-Dokumentation lesen →