In digitale schakelingen is een schuifregister¹ een opeenvolging van flip-flops die dezelfde klok delen en waarbij de uitgang van elke flip-flop verbonden is met de data-ingang van de volgende flip-flop in de reeks. Dit resulteert in een circuit dat een bitreeks voorstelt. Die bitreeks schuift bij elke klokslag één positie op naar rechts, waarbij aan de linkerkant een input bit wordt ingeschoven dat aan het schuifregister wordt aangeboden en aan de rechterkant het laatste bit (output bit) wordt uitgeschoven.

Een 16-bit schuifregister.

Een linear-feedback shift register² (afgekort LFSR) is een schuifregister dat als belangrijkste kenmerk heeft dat het input bit bepaald wordt als een lineaire functie van de vorige toestand van het schuifregister. De meest gebruikte lineaire functie van afzonderlijke bits is de booleaanse operator "exclusieve of³" (exclusive or, XOR). Het input bit van een LFSR wordt dus doorgaans bepaald als de XOR van een selectie van bits in de vorige toestand van het schuifregister.

Een 16-bit linear-feedback shift register (LFSR). De taps die in deze LFSR gebruikt worden, zorgen ervoor dat het schuifregister het maximaal aantal van 65535 toestanden doorloopt, exlusief de toestand die enkel uit nullen bestaat. De toestand die getoond wordt heeft hexadecimale waarde 0xace1, en wordt gevolgd door een toestand met hexademicale waarde 0x5670.

De begintoestand van een LFSR wordt de seed genoemd. Omdat de werking van het register deterministisch is, wordt de reeks waarden die het register produceert volledig bepaald door de huidige (of vorige) toestand ervan. Omdat het register slechts een eindig aantal mogelijke toestanden heeft, moet het uiteindelijk in een herhalende cyclus terechtkomen. Een LFSR met een goed gekozen feedbackfunctie kan echter een reeks bits produceren die willekeurig lijkt en een zeer lange cyclus heeft.

De bitposities van een schuifregister worden van links naar rechts genummerd vanaf 1. De bitposities die gebruikt worden om de volgende toestand te bepalen worden de taps genoemd: in bovenstaande figuur zijn de taps [11, 13, 14, 16]. Het meeste rechtse bit van het LFSR wordt het output bit genoemd. De taps worden sequentieel geXORed en daarna teruggekoppeld naar het meest linkse bit (input bit).

Als alternatief voor XOR-gebaseerde feedback in een LFSR, kan men ook een XNOR⁴ gebruiken. Deze functie is strikt gezien geen lineaire afbeelding, maar resulteert in een LFSR waarvan de toestand het complement is van de toestand van een XOR-gebaseerde LFSR. Een toestand waarbij alle bits gelijk zijn aan één is illegaal bij een XNOR-feedback, net zoals een toestand met allemaal nullen illegaal is bij het gebruik van XOR. Deze toestanden worden als illegaal beschouwd omdat het register als het ware geblokkeerd blijft zitten in deze toestanden.

Opgave

Schrijf een klasse LFSR waarmee linear-feedback shift registers kunnen voorgesteld worden. Bij het instantiëren van objecten van de klasse LFSR moeten twee argumenten doorgegeven worden: i) een string die bestaat uit een opeenvolging van nullen (0) en enen (1) die de seed van het schuifregister voorstelt (en meteen ook aangeeft hoeveel flip-flops het register telt) en ii) een collectie (een lijst, een tuple of een verzameling) van integers die als taps gebruikt worden door het LFSR. Optioneel kan aan een derde parameter xor nog een Booleaanse waarde doorgegeven worden (standaardwaarde: True) die aangeeft of het LFSR gebruikt maakt van XOR (True) of XNOR (False) poorten voor de feedback.

Zorg ervoor dat de volgende ingebouwde functies op de aangegeven manier werken met argumenten van de klasse LFSR:

next: brengt het LFSR naar zijn volgende toestand (resultaat van een klokslag) en geeft de uitgeschoven output bit (int) terug
int: geeft een integer terug met de decimale waarde van de huidige toestand van het LFSR
bin: geeft een string terug met de binaire waarde van de huidige toestand van het LFSR (zelfde formaat als de string die wordt teruggegeven door bin($$x$$), waarbij $$x$$ een integer is met de decimale waarde van de huidige toestand van het LFSR)
hex: geeft een string terug met de hexadecimale waarde van de huidige toestand van het LFSR (zelfde formaat als de string die wordt teruggegeven door hex($$x$$), waarbij $$x$$ een integer is met de decimale waarde van de huidige toestand van het LFSR)
print: schrijft een stringvoorstelling uit die bestaat uit een reeks nullen (0) en enen (1) die correspondeert met de huidige toestand van het LFSR

Zorg er ook voor dat methode states kan aangeroepen worden op alle objecten van de klasse LFSR. Bij het aanroepen van deze methode moeten geen argumenten doorgegeven worden. De methode moet het register herhaaldelijk naar zijn volgende toestand brengen, totdat het register een toestand bereikt die eerder bij de methode-aanroep werd waargenomen (inclusief de toestand bij aanvang van de methode-aanroep). De methode moet teruggeven hoeveel iteraties hiervoor nodig waren.

Voorbeeld

        >>> register = LFSR('1010110011100001', [11, 13, 14, 16], xor=True)
>>> print(register)
1010110011100001
>>> bin(register)
'0b1010110011100001'
>>> int(register)
44257
>>> hex(register)
'0xace1'

>>> next(register)
1
>>> print(register)
0101011001110000
>>> bin(register)
'0b101011001110000'
>>> int(register)
22128
>>> hex(register)
'0x5670'

>>> next(register)
0
>>> print(register)
1010101100111000
>>> bin(register)
'0b1010101100111000'
>>> int(register)
43832
>>> hex(register)
'0xab38'

>>> register.states()
65535
>>> print(register)
1010101100111000
>>> bin(register)
'0b1010101100111000'