Cellautomat

En cellautomat är en diskret beräkningsmodell där ett antal celler utgör modellens tillstånd. För varje cell beror nästa tillstånd på dess nuvarande tillstånd, dess närmaste grannars tillstånd samt en uppsättning uppdateringsregler.

En sådan uppsättning regler är Rule 30, publicerad av Stephen Wolfram. Dessa uppdateringsregler genererar en skenbar slumpmässighet trots avsaknad av något som rimligen skulle kunna betraktas som slumpmässigt indata. Mer matematiskt korrekt uttryckt ger reglerna upphov till ett kaotist, aperiodiskt beteende hos cellautomaten. En cellautomat med Rule 30 kan därmed fungera som en slumptalsgenerator.

Notera dock att även om Rule 30 genererar en bra rektangelfördelad slumptalssekvens, är den inte en kryptografiskt säker PRNG. Rule 30 skall därför inte användas för strömkrypto eller vid nyckelgenerering.

Implementation

Informasics IP-kärna Rule 30 implementerar en endimensionell cellautomat där ändarna är sammankopplade till en ring. Cellautomaten består av 32 enbitars celler, vilket gör att automaten genererar ett 32-bit ord varje cykel.

Konstruktionen har implementerats i en Altera Cyclone II FPGA. Konstruktionen kräver 32 registers och 64 LE:s. Den maximala interna klockfrekvensen är drygt 400MHz, vilket ger en PRNG-bandbredd på 1.6 GByte/s.

IP-kärnan Rule 30 inkluderar RTL-kod i Verilog 2001, dokumentation, testbänk, samt scriptfil för att simulera konstruktionen med den öppna Verilogsimulatorn Icarus Verilog. 

Licens för användning av IP-kärnan Rule 30 är en så kallad Two Clause BSD License.

IP-kärnan kan laddas ner på sidan Produkter/IP-kärnor/Rule 30 Slumptalsgenerator.