solution

Bộ tạo dòng khóa kiểu A5/1 (dùng trong mã hóa GSM) kết hợp ba thanh ghi LFSR Fibonacci $R_1, R_2, R_3$ (độ dài lần lượt $L_1, L_2, L_3$) bằng cơ chế xung nhịp bất quy tắc điều khiển theo đa số (majority clocking).

Mỗi thanh ghi $R_j$ có: trạng thái $L_j$ bit ở vị trí $1,\ldots,L_j$; danh sách tap riêng (bit phản hồi mới = XOR các bit tại vị trí tap của trạng thái hiện tại, dịch trái rồi chèn bit phản hồi vào vị trí cuối — giống định nghĩa LFSR ở các bài trước); và một vị trí clock tap riêng dùng để quyết định việc dịch.

Tại mỗi bước sinh 1 bit dòng khóa, với trạng thái hiện tại (trước khi dịch bất kỳ thanh ghi nào):

1. Bit dòng khóa ra = XOR bit ở vị trí 1 của cả ba thanh ghi.
2. Với mỗi $j$, lấy bit clock $c_j$ = bit tại vị trí clock tap của $R_j$.
3. Giá trị đa số $m$ = giá trị (0 hoặc 1) xuất hiện ở ít nhất 2 trong 3 bit $c_1, c_2, c_3$.
4. Thanh ghi $R_j$ chỉ được dịch (thực hiện đúng 1 bước LFSR như mô tả ở trên) nếu $c_j = m$; ngược lại $R_j$ giữ nguyên trạng thái ở bước này.

Lặp lại $n$ lần để sinh $n$ bit dòng khóa liên tiếp.

Ví dụ minh họa với ba thanh ghi độ dài 3, clock tap = vị trí 2 cho cả ba: $R_1$: tap$=\{3,1\}$, seed=110; $R_2$: tap$=\{3,2\}$, seed=011; $R_3$: tap$=\{3,1\}$, seed=101. Ở bước 1: bit ra $=1\oplus0\oplus1=0$; các bit clock là $(1,1,0)$ nên đa số $m=1$; chỉ $R_1, R_2$ được dịch. Với $n=5$, kết quả đầy đủ là 01110.