ForHosting KIT · 数学

線形フィードバックシフトレジスタ

最初のビット列、タップ位置、ステップ数を入力すると、フィボナッチ型LFSRの出力ビット列が分かります。初期値1000、タップ4と1で8ステップ動かすと00011110を出し、最後は1101になります。CRCの演習に便利です。ブラウザで無料で使えます。

  • 無料
  • ブラウザで動作
  • 登録不要
  • データは端末の外に出ません
ご利用方法 ウェブAPIメールTelegramアプリ 近日
入力した場合
状態
1000
タップ回数
4, 1
結果
長さ
4
配列
00011110
最終状態
1101

線形フィードバックシフトレジスタ、略して LFSR は、ビットの列を保持し、クロックのたびにいくつかのタップ位置を XOR して新しい入力ビットを求め、残りをずらすコンパクトなディジタル機械です。設計者は照合表を置かずに、疑似乱数ビット列、巡回冗長の剰余、スクランブル系列、内蔵自己試験パターンを作るために LFSR を使います。この計算機は、初期レジスタ状態を 0 と 1 の文字列として受け取り、左から数える 1 始まりのタップ位置の一覧と、実行するクロック段数を受け取ります。実装は Fibonacci 型 LFSR です。各段で右端ビットを出力し、レジスタを 1 つ右へずらし、タップしたビットの XOR を左端へ挿入します。

Fibonacci 型 LFSR とは何か、各クロックがビットをどう出すか

線形フィードバックシフトレジスタは、次の入力ビットが現在の内容の線形関数である有限状態機械で、その演算は二元体 GF(2) の上で行われます。ハードウェアではその線形関数は XOR そのものです。位置は状態文字列の左端を 1、右端を n と数えます。

各クロックでエンジンはそれらのタップのビットを読み、XOR して 1 ビットのフィードバックを得て、右端ビットを次の出力標本として出し、すべてのビットを 1 つ右へずらし、空いた左端セルへフィードバックビットを書き込みます。この段を繰り返すと、周期がたかだか 2^n 引く 1 の決定的なビット列が得られます。

全ゼロ状態は不動点であり、最大周期(原始)多項式のそれ以外の状態は、残る 2^n 引く 1 個の非ゼロベクトルを一通り辿ってから繰り返します。4 ビットレジスタのタップ 4 と 1 に対応する x^4 プラス x プラス 1 のような教室定番の多項式は、非ゼロのシードから始めればその最大周期に達します。

Galois 型 LFSR はシフト中に複数セルへ XOR し、同じ多項式でも関連はあるが同一ではない系列を出します。この計算機は Galois 配線をエミュレートしません。

入力の契約、タップの番号付け、応答の形、エラー

state は 0 と 1 の文字からなる初期レジスタです。左端の文字が位置 1、文字列の長さがレジスタ幅で、1 から 64 ビットまでです。state 内の空白は無視されるので、1 0 0 0 のような間隔付きニブルも受け付けます。

taps は Fibonacci フィードバックを作るために XOR する、1 始まりの整数位置の空でない配列です。各タップは 1 からレジスタ長まで(両端含む)になければなりません。steps は実行するクロック数で、1 から 4096 の整数です。

各クロックは出力ビットを 1 つ出します。回り込みは別の多項式を黙って実装してしまうからです。呼び出し側はそこから機械を再開できます。

LFSRのビット列が役立つ場面

ディジタル設計の授業や HDL 実験では、Fibonacci 型 LFSR を手で数段進め、データシートの多項式をビットダンプと照合させます。左から右への同じ番号付けと右シフトの同じ約束を使う決定的オラクルは、どちら端がビット 0 かという議論を消します。

通信と符号化の宿題は、CRC 剰余検査、Gold 符号、加法スクランブラの線形エンジンとして短い LFSR を使います。シリコンや FPGA 生地の内蔵自己試験と PRBS 生成器は本質的に LFSR です。検証の失敗は残高を消費しません。

教室での LFSR と CRC の演習

シードとタップ一覧から Fibonacci レジスタを進め、出力ビット列と最終状態を手計算の宿題や教科書の多項式と照合します。

PRBS と内蔵自己試験の接頭辞

最大周期 LFSR 系列の既知の接頭辞を作り、FPGA、ASIC、またはソフトウェアスクランブラがリセット後に指定タップと一致するかを確認します。

HDL 試験台向けのオラクル

決定的なビットダンプで単体試験を駆動し、Verilog または VHDL の LFSR モデルが逆方向シフトや 0 始まりタップを黙って採用しないようにします。

この線形フィードバックシフトレジスタは各段でどのように進みますか?

Fibonacci 型 LFSR を実装しています。1 始まりのタップ位置にあるビットの XOR がフィードバックです。右端ビットが出力され、レジスタは 1 つ右へずれ、フィードバックビットが左端セルへ書き込まれます。

タップ位置はどのように番号付けされますか?

タップは 1 始まりで、state 文字列の左から数えます。先頭文字が位置 1、末尾文字が位置 n で、n はレジスタ長です。4 ビット上の多項式 x^4+x+1 はタップ 4 と 1 です。

タップがレジスタ長を超えるとどうなりますか?

n より大きいタップは別の多項式を表すため、ハンドラは回り込みを拒み、契約を正直に保ちます。

全ゼロのシードは何を出しますか?

出力ビットはすべて 0 のまま、レジスタも全ゼロのままです。ゼロの XOR はゼロだからです。この不動点は本物の LFSR の振る舞いであり、誤りではありません。非自明な系列には非ゼロのシードを使ってください。

LFSRが作れる最も長い列はどのくらいですか?

レジスタ長をnとすると、繰り返すまでに最大で2のn乗から1を引いた数のビットです。4ビットでタップ4と1のような最大周期のタップなら、すべてゼロでない初期値からその上限に達します。

このページの機能はすべてAPIからも利用できます。自社システムに組み込みたいチーム向けのセクションです。それ以外の方は上のツールをそのままお使いください。

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

Bearerトークンで認証し、POST1回でタスクをキューに登録します。結果はWebhookまたは署名付きリンクで受け取れます。

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}'
{
  "state": "1000",
  "taps": [
    4,
    1
  ],
  "steps": 8
}
{
  "task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
  "type": "math.linear_feedback_shift_register",
  "status": "queued",
  "_links": {
    "result": "/tasks/tsk_…/result"
  }
}

非同期APIです。task_idは即時に返ります。ポーリングは1秒あたり1リクエストまでです。

1リクエストあたり$0.002

単価はすべて公開しています。トークン換算や独自クレジットはありません。失敗したタスクは課金されません。

max_length64
max_steps4096
HTTPコード意味
401unauthorizedAPIキーが無効か、指定されていません。Authorizationヘッダーを確認してください。
402insufficient_balance残高が不足しています。チャージ後に再度お試しください。
404unknown_type指定されたタスクタイプは存在しません。タイプ名を確認してください。
429rate_limitedリクエストが多すぎます。しばらく待ってから再度お試しください。

タップがレジスタ長を超えると、回り込みを捏造せず invalid_input で失敗します。

Fibonacci 型 LFSR とは何か、各クロックがビットをどう出すか

このエンドポイントが実装する Fibonacci 形式は、n ビットの列とタップ位置の一覧を保持します。各出力ビットが直前の状態だけの関数であるため、同じ state、同じ taps、同じ段数を送った 2 つのクライアントは同じ系列を得ます。

入力の契約、タップの番号付け、応答の形、エラー

必須フィールド 3 つを含む JSON ボディを POST してください。state の別名は seed または register、taps の別名は tap_positions、steps の別名は n または count です。欠落フィールド、state 内の非ビット、非整数、空のタップ一覧、公開上限を外れた値は、フィールド名を挙げて invalid_input で失敗し、課金されません。この機能に特有の誤りはレジスタをはみ出すタップです。state が 4 ビットで taps に 5 が含まれると、ハンドラは n を法とする回り込みをせず、タップ位置がレジスタ長を超えるというメッセージで拒否します。成功時のボディは length、正規化した state 文字列、taps、steps をエコーし、bits をクロック順の 0 と 1 の整数配列として返し、コピー用に同じビットを連結した sequence を返し、最後のシフト後のレジスタ内容である final_state を返します。例: state 1000、taps 4 と 1、steps 8 は bits 0,0,0,1,1,1,1,0、sequence 00011110、final_state 1101 を与えます。

LFSR ビット列 API が真価を発揮する場面

ここで基準系列を出せば、採点者はスクリーンショットではなく安定した JSON 契約と学生実装を比べられます。検証スクリプトはこのエンドポイントを呼んで最大周期系列の既知の接頭辞を作り、リセット後に被試験装置が同じ接頭辞を出すかを確かめられます。実装が純粋な parse の tier A であるため、成功した各呼び出しはモデルトークンも外向き通信もなく、公表された $0.002 の基本料金で済みます。

線形フィードバックシフトレジスタ計算機の料金はいくらですか。

ブラウザの用具は無料です。API 要求は成功した呼び出しごとに $0.002 で前払いの KIT 残高を使い、無効な入力は課金されません。

KITの完全なドキュメントを見る →