Bộ tạo số ngẫu nhiên thường được sử dụng trong lập trình cho nhiều mục đích khác nhau. Ví dụ, chúng có thể được dùng để tạo hiệu ứng ánh sáng nhấp nháy ngẫu nhiên hoặc thêm nhiễu vào tín hiệu hình ảnh để giảm thiểu các hiện tượng răng cưa và đường viền. Do máy tính hoạt động theo quy luật, chúng không thể tạo ra số ngẫu nhiên thực sự. Thay vào đó, chúng ta sử dụng các quy trình tạo ra chuỗi số có vẻ ngẫu nhiên, mặc dù chúng tuân theo một mô hình dự đoán được. Những số này được gọi là số giả ngẫu nhiên.
Bộ tạo số giả ngẫu nhiên được sử dụng rộng rãi, từ các ứng dụng đơn giản đến các hệ thống mã hóa phức tạp. Bài viết này sẽ tập trung vào một loại bộ tạo số giả ngẫu nhiên đơn giản: Sequence Generator Using Shift Register (bộ tạo chuỗi sử dụng thanh ghi dịch chuyển). Bộ tạo này sử dụng một thanh ghi dịch chuyển, với bit trống được điền bằng kết quả của phép toán XOR (exclusive-or) giữa hai bit khác trong thanh ghi.
Một ví dụ về bộ tạo số giả ngẫu nhiên sử dụng thanh ghi dịch chuyển 4 bit được minh họa như sau: mỗi bước thời gian, bit thứ 3 và thứ 2 được kết hợp bằng phép XOR; thanh ghi được dịch chuyển sang trái một bước; kết quả của phép XOR được đưa vào bit 0. Bắt đầu với giá trị 0001, chuỗi bit sẽ lặp lại theo mô hình: 0001, 0010, 0100, 1001, 0011, 0110, 1101, 1010, 0101, 1011, 0111, 1111, 1110, 1100, 1000, 0001. Chuỗi này có độ dài 15 bit, là độ dài tối đa có thể cho thanh ghi 4 bit (2^4 – 1).
Việc lựa chọn các bit để thực hiện phép XOR rất quan trọng. Một lựa chọn sai có thể dẫn đến chuỗi ngắn hơn. Ví dụ, nếu sử dụng bit thứ 2 thay vì bit thứ 3 trong ví dụ trên, chuỗi sẽ chỉ có độ dài 6 bit.
Có một bảng liệt kê các giá trị m (vị trí bit được chọn cho phép XOR) tối ưu cho thanh ghi n bit để tạo ra chuỗi có độ dài tối đa (2^n – 1). Nếu m là một lựa chọn tốt cho n, thì n-m cũng vậy.
Về mặt lý thuyết, bộ tạo chuỗi sử dụng thanh ghi dịch chuyển hoạt động dựa trên việc tính lũy thừa liên tiếp của một số x trong trường hữu hạn Galois bậc 2^n. Các số được sử dụng là đa thức với hệ số modulo 2. Mỗi vị trí trong thanh ghi đại diện cho một hệ số của đa thức, và việc dịch chuyển sang trái tương đương với việc nhân với x. Phép XOR thực hiện phép toán modulo.
Ví dụ, trong thanh ghi 4 bit với m=3, mỗi mẫu bit tương ứng với một đa thức. Mẫu 0101 tương ứng với đa thức x^3 + x. Việc dịch trái tương đương với việc nhân với x. Quá trình này được thực hiện modulo đa thức Q = x^4 + x + 1.
Để đạt được chu kỳ tối đa, Q phải là đa thức nguyên tố và x phải chu kỳ qua tất cả 2^n – 1 đa thức khác không modulo Q.
Tóm lại, bộ tạo chuỗi ngẫu nhiên sử dụng thanh ghi dịch chuyển là một phương pháp hiệu quả để tạo ra số giả ngẫu nhiên. Bằng cách sử dụng phép toán dịch chuyển và XOR, kết hợp với việc lựa chọn đúng các tham số, ta có thể tạo ra chuỗi số có tính ngẫu nhiên cao và độ dài tối đa. Phương pháp này dựa trên lý thuyết trường Galois và có nhiều ứng dụng trong mã hóa, sửa lỗi và khoa học máy tính.
