LFSR (Linear Feedback Shift Registers)
Galois LFSR 在硬體實作中更受歡迎，主要是因為它的異或門（XOR gate）是並聯位在暫存器之間，電路延遲（Propagation Delay）較低，時鐘頻率可以跑得更高；而 Fibonacci 的 XOR 則是串聯在回授路徑上。
Galois vs Fibonacci LFSR 實作模擬
這個程式會顯示兩個 4-bit 的移位暫存器（多項式採用 x^4 + x^3 + 1），點擊按鈕後可以同步觀察兩者的位移與 XOR 運算的差異。
Galois LFSR (左側):
原理：當輸出位元為
1時，特定的 "Tap" 位元會在移位過程中與輸出值進行 XOR。視覺觀察：你會發現它的 XOR 運算是「由外往內」注入的。
Fibonacci LFSR (右側):
原理：選定多個位元（Taps）進行 XOR 運算後，將結果回傳到第一個位元。
視覺觀察：這是一般教科書最常教的方式，所有運算都在「回授路徑」上完成。
import tkinter as tk
from tkinter import ttk
class LFSRVisualizer:
def __init__(self, root):
self.root = root
self.root.title("LFSR 實作對比: Galois vs Fibonacci (x^4 + x^3 + 1)")
# 初始狀態 (4-bit, 不能為全 0)
self.galois_state = [1, 0, 0, 0]
self.fibonacci_state = [1, 0, 0, 0]
self.setup_ui()
def setup_ui(self):
# 使用主要容器
main_frame = ttk.Frame(self.root, padding="20")
main_frame.grid(row=0, column=0)
# 標題與多項式說明
title_label = ttk.Label(main_frame, text="多項式: x⁴ + x³ + 1", font=("Arial", 14, "bold"))
title_label.grid(row=0, column=0, columnspan=2, pady=(0, 20))
# --- 左側: Galois ---
galois_frame = ttk.LabelFrame(main_frame, text=" Galois LFSR (內部異或) ", padding="10")
galois_frame.grid(row=1, column=0, padx=15)
# Galois 電路示意圖 (簡化文字版)
self.g_diag = tk.Label(galois_frame, text="[IN] → [b0] → [b1] → [b2] → (XOR) → [b3] → [OUT]\n"
" ↑______________|",
font=("Courier", 10), justify=tk.LEFT, bg="#f0f0f0")
self.g_diag.pack(pady=5)
self.galois_canvas = tk.Canvas(galois_frame, width=320, height=100, bg="white")
self.galois_canvas.pack()
# --- 右側: Fibonacci ---
fib_frame = ttk.LabelFrame(main_frame, text=" Fibonacci LFSR (外部回授) ", padding="10")
fib_frame.grid(row=1, column=1, padx=15)
# Fibonacci 電路示意圖 (簡化文字版)
self.f_diag = tk.Label(fib_frame, text=" ____________(XOR) <--- [b2] <--- [b3] [OUT]\n"
" ↓ |___________________|\n"
"[IN] → [b0] → [b1] → [b2] → [b3]",
font=("Courier", 10), justify=tk.LEFT, bg="#f0f0f0")
self.f_diag.pack(pady=5)
self.fib_canvas = tk.Canvas(fib_frame, width=320, height=100, bg="white")
self.fib_canvas.pack()
# --- 控制區 ---
btn_frame = ttk.Frame(main_frame)
btn_frame.grid(row=2, column=0, columnspan=2, pady=20)
self.step_btn = ttk.Button(btn_frame, text=" 執行一個移位 (Step) ", command=self.step)
self.step_btn.pack(side=tk.LEFT, padx=5)
self.reset_btn = ttk.Button(btn_frame, text=" 重設 (Reset) ", command=self.reset)
self.reset_btn.pack(side=tk.LEFT, padx=5)
self.draw_registers()
def draw_single_lfsr(self, canvas, state, highlight_idx=None):
canvas.delete("all")
for i in range(4):
x0, y0 = 40 + (i * 60), 30
x1, y1 = x0 + 45, 75
# 繪製暫存器方框
color = "#e1f5fe" if i != highlight_idx else "#fff9c4"
canvas.create_rectangle(x0, y0, x1, y1, fill=color, outline="black", width=2)
# 數值
canvas.create_text(x0 + 22, y0 + 22, text=str(state[i]), font=("Arial", 18, "bold"))
# 索引
canvas.create_text(x0 + 22, y0 - 10, text=f"b{i}", font=("Arial", 10))
# 箭頭
if i < 3:
canvas.create_line(x1, (y0+y1)/2, x1+15, (y0+y1)/2, arrow=tk.LAST)
def draw_registers(self):
self.draw_single_lfsr(self.galois_canvas, self.galois_state)
self.draw_single_lfsr(self.fib_canvas, self.fib_state_visual())
def fib_state_visual(self):
return self.fibonacci_state
def step(self):
# 1. Galois Logic (x^4 + x^3 + 1)
# 輸出位元是最後一格 (b3)
out = self.galois_state[3]
new_g = [0] * 4
new_g[0] = out # b3 回授到 b0
new_g[1] = self.galois_state[0] # 正常移位
new_g[2] = self.galois_state[1] # 正常移位
new_g[3] = self.galois_state[2] ^ out # Tap 在此：b2 XOR b3(out)
self.galois_state = new_g
# 2. Fibonacci Logic (x^4 + x^3 + 1)
# Tap 在 b2(x^3) 與 b3(x^4)
feedback = self.fibonacci_state[2] ^ self.fibonacci_state[3]
new_f = [feedback] + self.fibonacci_state[:-1]
self.fibonacci_state = new_f
self.draw_registers()
def reset(self):
self.galois_state = [1, 0, 0, 0]
self.fibonacci_state = [1, 0, 0, 0]
self.draw_registers()
if __name__ == "__main__":
root = tk.Tk()
app = LFSRVisualizer(root)
root.mainloop()
沒有留言:
張貼留言