Linear Feedback Shift Register (LFSR) Nedir?
Bilgisayarlar programlandıkları gibi deterministik, yani belirli koşullar altında hep aynı çıktıyı üretecek şekilde çalışan elektronik aygıtlardır. Elinizde bir kural seti varsa bilgisayar kullanarak bunun programını kolaylıkla yazabilirsiniz. Ancak bazı problemler bilgisayarların yapabileceklerinin biraz fazlasını gerektirmektedir. Örneğin; rastgele sayı üretimi. Bilgisayarda rastgele bir sayı üretmek istediğinizi varsayalım. Bunu nasıl yapardınız ? Ve yine varsayalım ki bir şekilde rastsal sayı üretmeyi buldunuz; bunun gerçekten rastgele olduğunu nasıl ispatlarsınız. Belki de sadece rastgele gibi gözüken bir sayı buldunuz. İşte böyle rastgeleymiş gibi gözüken sayı dizilerine pseudo-random(yalancı-rastsal) sayılar denir. Yalancı-rastsal sayılar belirli matematiksel modeller kullanılarak üretilmiş sayılardır. Ve kurulan modeller için başka bir noktada aynı şartları sağlarsanız aynı rastsal sayıları üretebilecektir, yani tekrarlanabilir olacaktır. Ancak gerçek bir rastgele sayı üreteci tüm değişkenleri sabit tutsanız bile farklı ve tekrarlanamaz sayılar üretmelidir.
Bu yazıda yalancı-rastsal sayı üretme yöntemlerinin temel bileşenlerinden olan Linear Feedback Shift Register (LFSR)’ların çalışma prensibinden ve hangi amaçla kullanılabileceklerinden bahsedilecektir. LSFR, donanımsal bir karşılığı olan bir birimdir. Her bir saat darbesiyle (clock cycle) bir birim kayan bitlerden oluşmaktadır. Normal shift register’lardan farkı soldan eklenecek sayının varsayılan olarak 0 veya 1 değil; belirli bir matematiksel formülle oluşturulmasından kaynaklanmaktadır.
Yukarıda şematik gösterimi verilen 4 bitlik bir LFSR’a saat darbesi geldiğinde; S0 bitinden itibaren kaydırılmaya başlanır ve sırayla tüm bitler birer bit sağa kayar. S4 bitinin değeri aşağıdaki formül uyarınca hesaplanır ve en soldaki bit değerine yazılır.
s4 = c3·s3 + c2·s2 + c1·s1 + c0·s0 (mod 2)
Buradaki çarpım ifadesi mod 2 aritmetiğinde olduğu için AND kapısıyla tariflenebilir. Yine aynı şekilde toplam ifadesi de XOR kapısıyla ifade edilebilir.
LFSR’ların Periyodu
Linear Feedback Shift Register’lar aynı zamanda bir state machine gibi de çalışırlar. Her bir saat darbesinde başka bir duruma geçerler. Özel bir durum olarak LFSR’lar 0 0 0 0 (tüm bitlerin sıfır olduğu durum)’dan başlayamazlar. Tüm bitler sıfır olursa LFSR tek bir state’te sabit kalır. Dolayısıyla LFSR’ herhangi bir stateten başlayıp gidebildiği tüm statelere gittikten sonra tekrar başladığı state’e geri döner.
Burada asıl önemli nokta şudur, LFSR sahip olduğu bit sayısıyla olabildiğince çok state’e gitmelidir. Böylelikle daha verimli çalışabilir durumda olur. Örneğin 4 bite sahip bir LFSR maksimum 2⁴-1 = 15 farklı state’e geçebilir. Bu durumda olan LFSR’lara maximal period LFSR denir. Yani durum uzayındaki tüm durumları ziyaret edebilme yeteneğine sahiptir. Biz de bunun olmasını isteriz.
Maksimallik Koşulu
LFSR’ın c değerlerini bir polinomun katsayıları gibi düşünebiliriz. Bu polinom özel bir sınırlı alan (Finite Field) üzerinde tanımlanmıştır. GF(2) yani Galoise Field(2)’de tanımlanan bu polinomun katsayıları 0 ve 1'lerden oluşur ve tüm işlemler modulo 2 ‘de yapılmaktadır. Bir LFSR’ın maksimal olabilmesi için bağlantı polinomu’nun primitive olması gerekir. Yani LFSR tasarlarken öyle tasarlamalıyız ki; başlangıç periyodu ne olursa olsun (tamamen sıfır hariç) tüm durumları gezsin. İşte bunu yapabilmek için polinomu primitive seçmeliyiz.
Buradan sonraki tüm işlemlerin GF(2)’de yapılacağını hatırlatmak isterim.
Primitive Kontrolü
Bir polinomun primitive’liği test etmeden önce o polinomun indirgenemez (irreducible) yani kendinden daha küçük polinomlara bölünememesi gerekmektedir. Bu ilk şarttır; gereklidir ancak primitive’lik için yeterli değildir.
x¹+1'den başlayarak sırasıyla x²+1, x³+1,x⁴+1… gibi polinomlar test edilecek polinoma bölünür. Yani; (x^n+1) / TestEdilecekPolinom işlemi tekrarlanır. Ta ki kalan 0 oluncaya dek. Kalan sıfır olduğunda x’in kuvveti eğer 2^bit_sayisi-1'e eşitse polinom primitve’dir. Yazarak biraz karışık olmuş olabilir; aşağıdaki python koduna bakarak primitive polinom test etme algoritmasını daha iyi kavrayabilirsiniz.
Sonuç
Bilgisayarlara rastgele değerler ürettirmenin bir yöntemi olan LFSR’ları ve çalışma mantıklarını inceledik. Oldukça ilginç bir konu olan rastgele sayı üreteçlerinin kullanım yerlerini; neden rastgele sayılara ihtiyaç duyduğumuzu ilerleyen yazılarda paylaşmayı düşünüyorum. Yazması benim için epey faydalı olan bu yazının sonunda umarım sizlere de bir katkım olmuştur.
