在密碼學與數位訊號處理中，LFSR（線性回饋移位暫存器，Linear Feedback Shift Register） 是用來產生偽隨機序列（也就是串流加密中所需的金鑰流）最核心的硬體架構。
LFSR 主要分為兩種實現架構：Fibonacci（斐波那契） 與 Galois（伽羅瓦）。其中，Galois LFSR 因為將互斥或（XOR）閘分散在各個暫存器之間，訊號不需要經過長串的級聯邏輯，因此在硬體電路中運作速度極快、延遲極低。
為了直觀說明 Galois LFSR 的運作原理，我們可以使用 Python 的 tkinter 套件來製作一個可視化的動態模擬器。
Galois LFSR 運作原理
一個 $n$ 階的 Galois LFSR 包含：
暫存器狀態（Registers）： 一組儲存
0或1的位元陣列（通常記為 $X_0, X_1, X_2 \dots$）。抽頭（Tap）： 決定哪些位置的暫存器需要參與 XOR 運算。這可以用一個特徵多項式來表示。
【移動規律】：
在每一個時脈脈衝（Clock）到來時：
輸出： 最末端（最小位元）的數值輸出，作為隨機位元。
回饋： 檢視這個輸出的值是
0還是1：如果輸出是
0：所有暫存器的值單純向右移一格。如果輸出是
1：所有暫存器的值向右移一格，但有抽頭（Tap）的位置必須與1進行 XOR 運算（也就是反轉訊號）。最左端（最高位元）則補入該輸出值。
我們使用一個經典的 4 階多項式：f(x) = x^4 + x^1 + 1 （抽頭在第 1 位與第 4 位），初始狀態（Seed）設為 1 0 1 1。
使用特徵多項式 f(x) = X^4 + X^1 + 1 （抽頭在 X_1 的輸入端，也就是當 X_0 輸出 1 時，會與X_2 移向 X_1 的資料進行 XOR）。
import customtkinter as ctk
import tkinter as tk
# 設定外觀風格與主題
ctk.set_appearance_mode("System")
ctk.set_default_color_theme("blue")
class GaloisLFSRVisualizer(ctk.CTk):
def __init__(self):
super().__init__()
# =============================================================
# 核心修正：強力繞過 CustomTkinter 內部與 Thonny/底層環境的相容性 Bug
# =============================================================
# 1. 繞過標題列顏色設定錯誤
self._windows_set_titlebar_color = lambda appearance_mode: None
# 2. 繞過背景縮放追蹤器 (Scaling Tracker) 的無限迴圈崩潰
try:
from customtkinter.windows.widgets.scaling.scaling_tracker import ScalingTracker
ScalingTracker.check_dpi_scaling = lambda *args, **kwargs: None
except Exception:
pass
# =============================================================
self.title("Galois LFSR 現代化動態模擬器")
self.geometry("800x520")
# 4位元 Galois LFSR 參數設定
self.num_bits = 4
self.state = [1, 0, 1, 1] # 初始種子 (Seed)
self.taps = [True, False, True, False] # [X3_in, X2_in, X1_in, X0_in] 是否有抽頭
self.clock_count = 0
self.is_playing = False
self.output_history = []
self.setup_ui()
# 確保 Canvas 佈局完成後再進行第一次繪製
self.update_idletasks()
self.draw_lfsr()
def setup_ui(self):
# 1. 標題與說明面板
self.title_frame = ctk.CTkFrame(self, fg_color="transparent")
self.title_frame.pack(pady=15, fill=ctk.X)
self.lbl_title = ctk.CTkLabel(self.title_frame, text="Galois LFSR 運作原理動態模擬", font=ctk.CTkFont(family="Helvetica", size=20, weight="bold"))
self.lbl_title.pack()
self.lbl_formula = ctk.CTkLabel(self.title_frame, text="特徵多項式: f(x) = X⁴ + X¹ + 1 (抽頭設於 X₁ 的輸入端)", font=ctk.CTkFont(family="Courier", size=13, weight="normal"))
self.lbl_formula.pack(pady=2)
# 2. 畫布面板 (放置傳統 Canvas 用於繪製電路圖)
self.canvas_frame = ctk.CTkFrame(self, width=740, height=190, corner_radius=10)
self.canvas_frame.pack(pady=10, padx=20, fill=ctk.BOTH, expand=True)
self.canvas = tk.Canvas(self.canvas_frame, bg="#ffffff", highlightthickness=0)
self.canvas.pack(padx=5, pady=5, fill=tk.BOTH, expand=True)
# 3. 狀態與數據顯示面板
self.info_frame = ctk.CTkFrame(self, corner_radius=10)
self.info_frame.pack(pady=10, padx=20, fill=ctk.X)
self.lbl_clock = ctk.CTkLabel(self.info_frame, text="目前時脈 (Clock): 0", font=ctk.CTkFont(size=13, weight="bold"), anchor="w")
self.lbl_clock.pack(side=ctk.TOP, fill=ctk.X, padx=15, pady=(8, 2))
self.lbl_status = ctk.CTkLabel(self.info_frame, text="準備就緒。請點擊單步執行或自動播放。", font=ctk.CTkFont(size=13), text_color="#1f77b4", anchor="w")
self.lbl_status.pack(side=ctk.TOP, fill=ctk.X, padx=15, pady=2)
self.lbl_output = ctk.CTkLabel(self.info_frame, text="產生的偽隨機序列 (Output): ", font=ctk.CTkFont(family="Courier", size=14, weight="bold"), text_color="#d62728", anchor="w")
self.lbl_output.pack(side=ctk.TOP, fill=ctk.X, padx=15, pady=(2, 8))
# 4. 控制按鈕面板
self.control_frame = ctk.CTkFrame(self, fg_color="transparent")
self.control_frame.pack(pady=15)
self.btn_next = ctk.CTkButton(self.control_frame, text="單步執行 (Next)", width=150, command=self.step_lfsr)
self.btn_next.grid(row=0, column=0, padx=10)
self.btn_toggle = ctk.CTkButton(self.control_frame, text="自動播放", width=150, fg_color="#2ca02c", hover_color="#238223", command=self.toggle_play)
self.btn_toggle.grid(row=0, column=1, padx=10)
self.btn_reset = ctk.CTkButton(self.control_frame, text="重設 (Reset)", width=150, fg_color="#7f7f7f", hover_color="#636363", command=self.reset_lfsr)
self.btn_reset.grid(row=0, column=2, padx=10)
def draw_lfsr(self, feedback_active=None):
"""利用 Canvas 繪製動態的 Galois LFSR 架構圖"""
self.canvas.delete("all")
canvas_width = self.canvas.winfo_width()
if canvas_width < 10:
canvas_width = 730
box_width, box_height = 60, 50
gap = 80
start_x = (canvas_width - ((self.num_bits - 1) * gap + box_width)) // 2 - 20
start_y = 50
# 1. 畫出主回饋線路
out_x = start_x + (self.num_bits - 1) * gap + box_width
out_y = start_y + box_height // 2
fb_color = "#1f77b4" if feedback_active == 1 else "#b0b0b0"
fb_width = 3 if feedback_active == 1 else 1.5
self.canvas.create_line(out_x, out_y, out_x + 30, out_y, fill=fb_color, width=fb_width)
self.canvas.create_line(out_x + 20, out_y, out_x + 20, out_y + 65, fill=fb_color, width=fb_width)
self.canvas.create_line(out_x + 20, out_y + 65, start_x - 45, out_y + 65, fill=fb_color, width=fb_width)
self.canvas.create_line(start_x - 45, out_y + 65, start_x - 45, out_y, fill=fb_color, width=fb_width)
self.canvas.create_line(start_x - 45, out_y, start_x, out_y, arrow=tk.LAST, fill=fb_color, width=fb_width)
self.canvas.create_text(out_x + 50, out_y - 15, text="Output", fill="#d62728", font=("Helvetica", 11, "bold"))
# 2. 依序繪製各個暫存器方塊 (從左到右為 X3, X2, X1, X0)
for i in range(self.num_bits):
x1 = start_x + i * gap
y1 = start_y
x2 = x1 + box_width
y2 = y1 + box_height
reg_name = f"X{self.num_bits - 1 - i}"
self.canvas.create_rectangle(x1, y1, x2, y2, fill="#e1f5fe", outline="#0288d1", width=2)
self.canvas.create_text((x1 + x2)//2, (y1 + y2)//2, text=str(self.state[i]), font=("Helvetica", 20, "bold"), fill="#212121")
self.canvas.create_text((x1 + x2)//2, y1 - 15, text=reg_name, font=("Helvetica", 11, "bold"), fill="#555555")
# 3. 處理暫存器之間的連接與 XOR 閘
if i < self.num_bits - 1:
next_x1 = start_x + (i + 1) * gap
mid_y = y1 + box_height // 2
if self.taps[i + 1]:
xor_x = x2 + (gap - box_width) // 2
self.canvas.create_oval(xor_x - 11, mid_y - 11, xor_x + 11, mid_y + 11, fill="#fff3e0", outline="#ffb74d", width=2)
self.canvas.create_text(xor_x, mid_y, text="⊕", font=("Helvetica", 14, "bold"), fill="#f57c00")
self.canvas.create_line(x2, mid_y, xor_x - 11, mid_y, fill="#666666", width=1.5)
self.canvas.create_line(xor_x + 11, mid_y, next_x1, mid_y, arrow=tk.LAST, fill="#666666", width=1.5)
self.canvas.create_line(xor_x, mid_y + 65, xor_x, mid_y + 11, arrow=tk.LAST, fill=fb_color, width=fb_width)
else:
self.canvas.create_line(x2, mid_y, next_x1, mid_y, arrow=tk.LAST, fill="#666666", width=1.5)
def step_lfsr(self):
"""執行一個 Clock 的標準 Galois 移位與 XOR 邏輯"""
self.clock_count += 1
output_bit = self.state[-1]
self.output_history.append(str(output_bit))
self.draw_lfsr(feedback_active=output_bit)
next_state = [0] * self.num_bits
next_state[0] = output_bit
status_msg = f"時脈 {self.clock_count}: 輸出位元 = {output_bit}。 "
if output_bit == 1:
status_msg += "回饋為 1 → 抽頭處 (X₁ 輸入端) 將與 1 進行 XOR 反轉。"
else:
status_msg += "回饋為 0 → 抽頭處不受影響，資料正常右移。"
for i in range(1, self.num_bits):
if self.taps[i]:
next_state[i] = self.state[i-1] ^ output_bit
else:
next_state[i] = self.state[i-1]
self.state = next_state
self.after(200, self.update_ui_text, status_msg)
def update_ui_text(self, status_msg):
self.lbl_clock.configure(text=f"目前時脈 (Clock): {self.clock_count}")
self.lbl_status.configure(text=status_msg)
self.lbl_output.configure(text=f"產生的偽隨機序列 (Output): {' '.join(self.output_history)}")
self.draw_lfsr()
def toggle_play(self):
"""切換自動播放 / 暫停"""
if self.is_playing:
self.is_playing = False
self.btn_toggle.configure(text="自動播放", fg_color="#2ca02c", hover_color="#238223")
else:
self.is_playing = True
self.btn_toggle.configure(text="暫停", fg_color="#d62728", hover_color="#b32021")
self.auto_play()
def auto_play(self):
if self.is_playing:
self.step_lfsr()
self.after(1000, self.auto_play)
def reset_lfsr(self):
self.state = [1, 0, 1, 1]
self.clock_count = 0
self.is_playing = False
self.output_history = []
self.btn_toggle.configure(text="自動播放", fg_color="#2ca02c", hover_color="#238223")
self.lbl_clock.configure(text="目前時脈 (Clock): 0")
self.lbl_status.configure(text="已重設。請點擊單步執行或自動播放。", text_color="#1f77b4")
self.lbl_output.configure(text="產生的偽隨機序列 (Output): ")
self.draw_lfsr()
if __name__ == "__main__":
app = GaloisLFSRVisualizer()
app.mainloop()
沒有留言:
張貼留言