Matrix_id, support, a cui vengono assegnati, sempre in maniera ciclica, i valori di id e row copiandoli da quelli estratti da m1, e infine tale oggetto support viene aggiunto nella matrice m2.
Figura 4.8: funzione transformMatrix_id
La calculateEPI, questa funzione calcola i PIE nella matrice. Essa riceve in ingresso la matrice dinamica (ArrayList<Matrix_id>) m3 su cui deve operare e restituisce in output un array dinamico aepi che contiene elementi di tipo Essential_Prime_Implicants. In pratica analizza la matrice per righe e per colonne e se riscontra per quella colonna un elemento uguale a 1 incrementa il valore di un opportuno contatore (counter).
Figura 4.9: funzione calculateEPI, prima parte
Se al termine della colonna risulta che il contatore è proprio uguale a 1, questo indica che ho proprio trovato un PIE e va a salvare tale elemento nella variabile pi del tipo
Essential_Prime_Implicants, memorizzandone il valore (i), la riga (Id_Row) e la colonna (Id_Column) di appartenenza.
Figura 4.10: funzione calculateEPI, seconda parte
La deleteRowsNull, questa funzione riceve in ingresso la matrice dinamica (ArrayList<Matrix_id>) m3 e la controlla per verificare se ci sono righe nulle: se è così elimina tali righe per semplificare la matrice poiché tali righe sono irrilevanti ai fini del calcolo dei PIE. Anche in questo caso la matrice viene esaminata per righe e per colonne in maniera ciclica, e tramite un contatore counter0, si memorizza il numero di 0 contenuti nella riga: se il valore del contatore è uguale al numero di elementi contenuti nella riga significa che la riga è nulla e pertanto la riga viene eliminata dalla matrice m3.
Figura 4.11: funzione deleteRowsNull
La searchOneRow, questa funzione riceve in ingresso una riga dinamica row_1 e restituisce un ArrayList di interi elements che contiene le posizioni dei valori uguali a 1 nella riga (in pratica il numero della colonna a cui il valore 1 appartiene). La funzione esamina la riga e verifica in maniera ciclica il valore dei vari elementi in essa contenuti: se un valore (index) è uguale a 1 lo aggiunge all’array dinamico elements.
Figura 4.12: funzione searchOneRow
La searchOneColumn, questa funzione riceve in ingresso la matrice dinamica (ArrayList<Matrix_id>) m3, e l’ArrayList di interi row e restituisce una matrice dinamica di interi ArrayList<ArrayList<Integer>> listElements. In pratica la funzione esamina la matrice m3 per colonna e se incontra un elemento della colonna uguale a 1 lo aggiunge a un array dinamico support; poi una volta che la colonna è terminata, inserisce support in una matrice, un ArrayList di ArrayList listElements. In questo modo tengo traccia della posizione dei valori uguali a 1 incontrati in ciascuna colonna della matrice.
Figura 4.13: funzione searchOneColumn
La deleteDominatedRows, questa funzione consente di eliminare le righe dominate presenti nella matrice dinamica m3, che la funzione riceve in input. Tale funzione sfrutta la funzione searchOneRow. In pratica di ogni riga i della matrice con searchOneRow calcolo il vettore elements_i che contiene le posizioni degli eventuali 1 presenti nella riga i-esima, poi itero tale processo anche su tutte le altre k righe della matrice m3, con k = i+1, calcolando così per ogni k-esima riga il vettore elements_k, che contiene le posizioni degli eventuali 1 presenti nella k-esima riga. A questo punto la funzione effettua un confronto tra elements_i ed elements_k: in particolare se l’array elements_i contiene l’array elements_k allora questo significa che la riga k-esima è dominata e quindi la posso eliminare dalla matrice; invece se si verifica l’inverso elimino la riga i-esima dalla matrice.
Figura 4.14: funzione deleteDominatedRows
La deleteEqualRows, anche questa funzione riceve in ingresso la matrice dinamica m3, di elementi di tipo Matrix_id, sulla quale va ad operare. Tale funzione va ad esaminare in maniera ciclica riga per riga tutta la matrice e se trova due righe
uguali, ne elimina la seconda.
Figura 4.15: funzione deleteEqualRows
La deleteColumn, questa funzione consente di eliminare una colonna specifica dalla matrice. Essa riceve in ingresso la matrice m3 e il valore dell’indice della colonna che si vuole eliminare dalla matrice (indexCol). In maniera sempre ciclica si accede alla colonna individuata dal suo indice e si eliminano man mano tutti gli elementi che appartengono ad essa. Riducendo così la matrice di una colonna.
Figura 4.16: funzione deleteColumn
La deleteDominantColumns, questa funzione consente di eliminare le colonne dominanti dalla matrice dinamica m3, che si presenta come un ArrayList di oggetti di tipo Matrix_id, che la funzione riceve in ingresso. Tale funzione sfrutta la funzione searchOneColumn. In pratica con SearchOneColumn trovo un array di array, la matrice dinamica listElements2, che contiene le posizioni degli 1 riscontrati nelle colonne della matrice. Poi, in maniera ciclica, si va ad esaminare proprio listElements2, copio la riga m-esima in un array elements_m e la riga n- esima in un array elements_n con n = m+1, questo per fare il confronto. Se elements_m è uguale o contiene elements_n, significa che la colonna m-esima nella matrice m3 è dominante e quindi la vado ad eliminare; inoltre vado ad eliminare
anche la riga m-esima corrispondente da listElements2. Se invece si verifica l’inverso vado ad eliminare la colonna n-esima da m3 e la riga n-esima corrispondente da listElements2. Infine se invece la riga m-esima della matrice listElements2 è vuota elimino la colonna m-esima dalla matrice m3 e la rispettiva riga m da listElements2; questo perché tale colonna contiene tutti 0 e quindi è irrilevante ai fini del calcolo dei PIE.
L
Figura 4.17: funzione deleteDominantColumns
La reduceMatrix, è la funzione che implementa l’algoritmo di Quine-McCluskey, l’algoritmo di riduzione, sfruttando e richiamando le funzioni che abbiamo descritto e che sono presenti nella classe ReductionAlgorithm.java. La funzione riceve in input: la matrice m_Id che è definita come ArrayList di Matrix_id ed è
quella sulla quale vado ad operare; e gli array a1 e a2 che conterranno i PIE che andremo man mano a trovare all’interno della matrice. All’interno della funzione ho definito: un array di Essential_Prime_Implicants aepi che conterrà i primi implicanti essenziali; un array di interi list che per ogni PIE contiene gli indici delle colonne coperte dalla riga che costituisce il PIE; un TreeSet di interi, list2, che uso per ordinare gli indici contenuti in list ed evitare ripetizioni; ed un ulteriore TreeSet aepiOrd, che uso per ordinare gli elementi dell’array aepi. Quest’ultima operazione l’ho fatta perché ho notato che l’ordine è importante per eliminare le colonne della matrice in maniera ordinata e corretta (dall’ultima alla prima, cioè da destra verso sinistra). A questo punto la funzione richiama la funzione calculateEPI e calcola così i PIE e li inserisce nell’array aepi. Poi passa a copiare i primi implicanti essenziali nei due array a1 e a2, in maniera tale da rappresentarli in modo diverso (nel primo caso rappresentati dal valore preceduto dalla lettera
“T”, che sta per Trace, nel secondo caso rappresentati solo dal valore).
Figura 4.18: funzione reduceMatrix, prima parte
Dopodiché viene invocata la funzione searchOneRow per calcolare il valore di list, i cui elementi poi vengono copiati in list2 (in modo da essere ordinati). Individuati gli indici delle colonne e delle righe a cui appartengono i primi implicanti essenziali, si passa in maniera ciclica ad eliminare tali colonne prima e tali righe
poi dalla matrice. Successivamente, per ottenere le operazioni desiderate, vengono invocate le altre funzioni in maniera ordinata: deleteEqualRows, deleteDominatedRows, deleteDominantColumns, deleteRowsNull.
Figura 4.19: funzione reduceMatrix, seconda parte
Tutte queste operazioni poi vengono ripetute in maniera ciclica, tramite il processo do- while, ricordando che nei passi successivi in realtà i nuovi primi implicanti che vengono
trovati sono detti secondari; il processo continua finché la matrice non diventa vuota, oppure se non è vuota si controlla la sua dimensione e se dopo la riduzione questa non cambia significa che non può essere più ridotta e quindi si esce dal ciclo. Il tutto proprio come previsto e indicato dall’algoritmo di riduzione che abbiamo adottato. Usciti dal ciclo, poi come ultima operazione, verranno aggiunti in a1 e a2 anche i primi implicanti secondari trovati.