Ich warte mal wieder mit einem kleinen Snippet auf, heute geht es um ein LinearFeedbackShiftRegister.
Erstmal: Wozu braucht man das überhaupt? LFSR werden dazu genutzt um schnell Pseudo-Zufallszahlen zu generieren. Diese sind streng deterministisch, deshalb bietet es sich überhaupt nicht an, so etwas zur Schlüsselerzeugung (Kryptografie) zu verwenden, wird aber dennoch in diesem Bereich genutzt, jedoch nicht zur Schlüssel Generierung sondern zur Rauscherzeugung. Wer mehr wissen möchte, der lese sich bitte in Wikipedia den Artikel durch Linear Rückgekoppeltes Schieberegister.
Der Code ist unspektatkulär, die Kommentare auf englisch, weil ich das gerade mehr gewohnt bin, wer Langeweile hat kann ja mal ein bisschen damit rumspielen.
Das Ganze ist in Hardware natürlich wesentlich schöner umzusetzen, da man pro Takt genau ein Schlüsselbit generieren kann.
#include <Array.au3>
; LFSR Generator
Func _GenerateLFSR($LFSRvector, $key, $count = 0)
Local $degree = UBound($LFSRvector)
Local $findSequence = False
If StringLen($key) <> UBound($LFSRvector) Then ;Vector has to be same size as key
Return -1
EndIf
If $count = 0 Then ;count = 0 => We search for the longest
$count = 2 ^ ($degree) ;sequence until it repeats itself
$findSequence = True ;Longest sequence possible is apparantly
EndIf ;2^m - 1, therefore we have to compute
; ;2^m steps to compare (or look for = 2^m)
Local $repeat
Local $xorFlipFlop ;Feedback Register
Local $keyArray = StringSplit($key, "") ;
Local $outputArray[$count][$degree + 1] ;Last column will be output
For $i = 0 To $degree - 1 Step 1 ;Initialize Array (Hardware Implemenatation:
$outputArray[0][$i] = $keyArray[$i + 1] ; Initialize Flip Flops)
Next
$outputArray[0][$degree] = $keyArray[$degree] ;s0 = k0
For $row = 1 To $count - 1 Step 1 ;Simulates a clock
$xorFlipFlop = 0 ;Feedback, will be computed while setting new registers
For $column = 1 To $degree - 1 Step 1 ;Set all registers except the feedback one
$outputArray[$row][$column] = $outputArray[$row - 1][$column - 1] ;New[i] = Old[i - 1]
If ($LFSRvector[$column] == 1) Then ;Check whether pi = 1, so if the current bit will shift back
$xorFlipFlop += $outputArray[$row - 1][$column] ;If so, add
EndIf
Next
$outputArray[$row][$degree] = $outputArray[$row][$degree - 1] ;Set Output = Last register
$outputArray[$row][0] = Mod($xorFlipFlop, 2) ;Set feedback register = XOR (which is congruent m1odulus 2)
If $findSequence Then ;Check whether we need to find the sequence or not
$repeat = true ;Initialize whether it's repetition or not
For $i = 0 To $degree Step 1 ;Iterate through all registers
If $outputArray[0][$i] <> $outputArray[$row][$i] Then ;Compare bitwise
$repeat = false ;If unequal, it does not repeat
ExitLoop ;Can stop loop on first occurence
EndIf
Next
If $repeat Then
ReDim $outputArray[$row][$degree + 1] ;Cut Array, because we just need the unique sequence
Return $outputArray
EndIf
EndIf
Next
Return $outputArray
EndFunc ;==>_GenerateLFSR
Dim $LFSRvector[3] = [0, 1, 1]
_ArrayDisplay(_GenerateLFSR($LFSRvector, "100", 0))
Alles anzeigen
Anmerkung: Wem gerade eine effizientere Implementierung in Software einfällt, der möge diese gerne teilen Ich brauchte nur ein schnelles Script, da ich keine Lust hatte die Tabellen von Hand aufzustellen.