Algoritmo per la creazione della tabella di generazione del dia-

del diagramma degli stati

Prima di descrivere l’algoritmo per la creazione della tabella di generazione del dia- gramma degli stati `e necessario definire il concetto di n-point.

Definizione 4.1.1. Un n-point `e l’insieme delle coordinate di un bit di un punto ap-

partenente alla curva del primo ordine, concatenati in un unico valore di n bits. Questi punti rappresentano i punti centrali dei sotto-quadranti in cui lo spazio `e partizionato.

Il primo passo per la generazione della chiave derivata di Hilbert prevede la costruzione della tabella di generazione del diagramma degli stati o generator table. La funzione principale di questa tabella `e quella di descrivere come una particolare curva del primo ordine sia trasformata in una del secondo ordine. Una generator table si compone di un numero ben preciso di righe e colonne; ciascuna riga corrisponde ad un punto che

giace su una curva del primo ordine, quindi sono presenti in totale rnrighe, nel nostro

caso r=2 e n pari al numero di dimensioni della curva. Le righe sono ordinate in base al valore dei numeri di sequenza (sequence numbers) dei punti sulla curva e insieme definiscono la curva del primo ordine che corrisponde al primo stato nel diagramma degli stati. Questa tabella contiene al suo interno l’informazione necessaria per eseguire la trasformazione di una curva del primo ordine in una del secondo, in particolare indica come sostituire ciascun punto appartenente alla curva del primo ordine con un’altra curva del primo ordine eventualmente riflessa oppure ruotata. Queste curve, con cui sono sostituiti i punti, saranno chiamate, nel contesto del diagramma degli stati, stati successivi o next-states. Le colonne che compongono la generator table sono le seguenti: Y, X1, X2, δY e T(Y).

Figura 4.1 – Generator table nel caso bidimensionale

In figura 4.1 `e mostrato un esempio di generator table. La colonna Y contiene tutti

i membri del dominio del mapping dei punti da uno spazio unidimensionale ad uno n-dimensionale per una curva del primo ordine. Ciascun valore esprime la distanza dall’inizio della curva e rappresenta la chiave derivata di un punto sulla curva. In ogni riga `e contenuto un valore numerico distinto compreso nell’intervallo [0, ..., rn − 1], composto da un numero di cifre pari al numero di dimensioni n e di cui ciascuna cifra pu`o assumere un valore compreso nell’intervallo [0, ..., r − 1]. I valori presenti

nella colonna Y della tabella di generazione del diagramma degli stati sono ordinati in ordine crescente. Per esempio nel caso bidimensionale, quindi con n pari a due, la colonna Y della generator table conterr`a i seguenti valori: 002, 012, 102 e 112.

I valori presenti nella colonna X1 della tabella esprimono l’ordinamento dei punti

sulla curva del primo ordine. Il metodo utilizzato per calcolarli [22], si basa sull’utilizzo

della sequenza Gray-code. La Gray-code sequence `e una sequenza di numeri binari in

cui qualsiasi coppia di membri consecutivi differiscono tra di loro per il valore di un bit in un’unica posizione.

L’algoritmo per il calcolo della sequenza Gray-code di ordine n `e il seguente: 1. Si inizializza la sequenza come [0, 1].

2. La sequenza viene raddoppiata, aggiungendo i membri della sequenza al passo precedente in ordine inverso.

3. A ciascun membro della prima met`a della sequenza viene aggiunto un bit di

valore 0 come bit pi`u significativo, mentre ai membri della seconda met`a un bit

di valore 1.

4. I passi 2 e 3 vengono ripetuti per produrre sequenze successive sempre pi`u lunghe, raddoppiando la lunghezza ad ogni iterazione. Il numero di bit, necessario per

rappresentare ciascun elemento della sequenza, aumenta di una unit`a ad ogni

iterazione.

5. Dopo n iterazioni la sequenza contiene 2n _{elementi distinti ciascuno composto}

da n bits. Tale sequenza viene chiamata Gray-code sequence.

Esempio 4.1.2. Mostriamo di seguito un esempio di generazione della Gray-code sequence.

[0, 1] [0, 1, 1, 0]

[00, 01, 11, 10] = Gray-code sequence di ordine 2 [00, 01, 11, 10, 10, 11, 01, 00]

[000, 001, 011, 010, 110, 111, 101, 100] = Gray-code sequence di ordine 3 ...

La colonna X1 della generator table contiene i membri della sequenza Gray-code cos`ı

calcolati. Le colonna Y contiene le chiavi derivate dei punti sulla curva del primo

ordine, mentre la colonna X1 contiene le coordinate di quei punti. La terza colonna

della generator table `e la colonna X2, in cui in ciascuna entry `e contenuta una coppia

di valori ognuno di n bits. Ciascuna coppia di valori corrisponde alle prime ed ultime coordinate dei punti su una curva del primo ordine, nei quali un punto preso dalla

colonna X1 viene mappato nella trasformazione al secondo ordine.

Figura 4.2 – Mapping della curva del primo ordine nella curva di Hilbert del secondo ordine

Consideriamo ad esempio la figura 4.2(a) ed in particolare il punto di coordinate 00 a cui corrisponde la chiave derivata 0 sulla curva del primo ordine. Il punto 00 viene trasformato in una curva del primo ordine ruotata rispetto a quella originale, come mostrato in figura 4.2(b). Le coordinate del primo punto della curva ruotata sono 00, mentre quelle dell’ultimo punto sono 01 che sono proprio i valori riportati nella colonna X2.

Le entrate di questa colonna, per una curva di n dimensioni, sono popolate tramite i membri della X2Gray-code sequence di ordine n.

L’algoritmo per il calcolo della sequenza X2Gray-code di ordine n `e il seguente:

1. Si inizializza la sequenza di ordine 1 come [0, 1, 0, 1].

2. Si inizializza la sequenza di ordine n pari alla sequenza di ordine n-1

3. Si sostituisce il valore dell’ultimo membro della sequenza con il valore del penul- timo membro, cos`ı da ottenere gli ultimi due membri di valore uguale.

4. A ciascun membro della sequenza, tranne che all’ultimo, si aggiunge come pre- fisso un bit pari a 0, mentre all”ultimo membro un bit pari ad 1.

5. Si raddoppia la lunghezza della sequenza fin qui ottenuta in maniera speculare, in modo tale che l’ultimo membro sia uguale al primo, il penultimo uguale al secondo e cos`ı via.

6. Si invertono i valori di tutti i bit pi`u significativi dei membri della seconda met`a della sequenza.

7. Si ripetono i punti dal numero 2 al numero 6 per ottenere la X2Gray-code sequence di ordine n.

Esempio 4.1.3. Mostriamo di seguito un esempio di generazione della X2Gray-code sequence.

[0, 1, 0, 1] [0, 1, 0, 0] [00, 01, 00, 10]

[00, 01, 00, 10, 10, 00, 01, 00]

[00, 01, 00, 10, 00, 10, 11, 10] = X2Gray-code sequence di ordine 2 ...

I valori contenuti nella colonna δY , per la curva di Hilbert, sono composti da n bits ciascuno e di questi uno soltanto possiede valore pari ad uno, mentre tutte le altre n-1 cifre hanno valore pari a zero. La posizione del bit settato ad uno indica l’asse su cui giacciono il primo e l’ultimo punto della curva del primo ordine, nella quale il

punto nella colonna X1 viene mappato nella trasformazione al secondo ordine. In altri

termini δY indica quale `e la dimensione su cui vi `e variazione tra le coordinate dei due punti che indicano l’inizio e la fine della curva. Ciascuna riga contiene un numero, il cui valore `e determinato dalla differenza bit a bit dei due valori presenti nella colonna

X2 della medesima riga. Ad esempio nel caso bidimensionale, nel caso in cui i valori

della colonna X2 siano rispettivamente 11 e 10, il valore presente alla colonna δY della

stessa riga sar`a 01.

La colonna T(Y) contiene una matrice di trasformazione di dimensione n × n per ogni entry, la quale esprime come una curva del primo ordine differisca dalla curva del

primo ordine definita dai valori contenuti dalle colonne Y e X1. In particolare tale

matrice indica come una curva del primo ordine, le cui coordinate del primo ed ultimo

punto, espresse come n-points, e contenute nella coppia di valori della colonna X2,

differisca dallo stato iniziale S0 e quindi implicitamente incapsula lo stato successivo o

next-state per ciascun punto (contenuto nella colonna X1) nello stato S0. La matrice

di trasformazione per lo stato S0 stesso `e uguale alla matrice identit`a.

L’algoritmo per il calcolo della matrice di trasformazione di ciascuna riga `e il

seguente:

1. Si setta la prima riga della matrice pari al valore contenuto nella colonna δY della medesima entry a cui la matrice di trasformazione si riferisce.

2. Per ciascuna riga della matrice dalla seconda alla n-esima, si pone la riga i -esima pari al valore della riga (i -1)-esima, a cui viene applicato uno shift circolare verso destra di una posizione.

3. Si aggiustano i segni degli elementi della matrice con valore diverso in base alla regola di Bially definita in [23]: se l’i -esimo bit del primo numero della coppia contenuta nella colonna X2della medesima riga `e diverso da zero allora l’elemento

non zero della i -esima colonna della matrice `e posto uguale a -1.