Vai alla Home Page About me Courseware Federica Living Library Federica Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Bruno Fadini » 6.Funzioni XOR, EQ, parità e disparità - Modulo 2


Corso di Reti logiche

Funzioni XOR, EQ, parità e disparità

Argomenti

  • Funzioni XOR ed EQ
  • Funzioni disparità e parità
  • Controllo di errore
  • Decomposizione funzionale

Funzioni XOR ed EQ

Funzione XOR

Funzione XOR


Funzioni XOR ed EQ

Reti logiche:

  • genera un segnale che indica se due bit sono uguali o diversi.
  • parità p(x,y)
Funzione EQ

Funzione EQ


Funzioni XOR ed EQ

Forme NAND e NOR a 2 livelli

Forme NAND e NOR a 2 livelli


Funzioni XOR ed EQ

In figura, forme NAND e NOR a 3 livelli

In figura, forme NAND e NOR a 3 livelli


Funzioni XOR ed EQ

Conclusioni

  • EQ negata di XOR, ma anche la duale
  • L’insieme (XOR, EQ) non è F.C.
  • ..ma è usato in molte applicazioni
  • Soprattutto XOR
    • Aritmetica
    • Disparità e parità (vedi in seguito)

Disparità e parità

Disparità d(X)

  • Dato un insieme X di n variabili, è d(X)=1 se e solo se il numero di bit “1″ in X è dispari
  • Per n=2 si ha d(X)=x1 ⊕ x2 =XOR (x1,x2)
  • Si dice anche XOR generalizzata d(X)=XOR(X) e si usano i simboli in figura
  • Disparità e parità sono funzioni che si applicano al controllo di errore nelle reti logiche
Simboli della XOR generalizzata

Simboli della XOR generalizzata


Disparità e parità

Parità p(X) = d(X)

  • Per n=2 si ha p(X)=x1 EQ x2 = XNOR(x1,x2)
  • Si dice anche XNOR generalizzata p(X)=XNOR(X) e si usano i simboli in figura
Simboli della XNOR generalizzata

Simboli della XNOR generalizzata


Disparità e parità

  • Per la proprietà dei numeri dispari
    • La somma di un numero pari di numeri dispari è pari
    • La somma di un numero dispari di numeri dispari è dispari
  • Vale per la disparità la proprietà:
    • se si suddivide X in sottoinsiemi disgiunti (X1,X2,…Xn)
    • il numero di “1″ di X è dispari se è dispari
    • il numero di sottoinsiemi con un numero dispari di “1″:
    • d(X)=d(d(X1),d(X2),…d(Xn))
  • Non così per la parità

UNA DISPARITA’ A N È DECOMPONIBILE IN PIÙ DISPARITÀ A K

Disparità e parità

Disparità a 4 con XOR a 2 su 3 livelli

Disparità a 4 con XOR a 2 su 3 livelli

Disparità a 4 con XOR a 2 su 2 livelli

Disparità a 4 con XOR a 2 su 2 livelli

Disparità a 8 con XOR a 3 o 2 su 2 livelli

Disparità a 8 con XOR a 3 o 2 su 2 livelli


Controllo di errori

Bit di parità e controllo

  • Nella trasmissione o nella memorizzazione di un’informazione la “perdita” di un bit (trasformazione da 0 a 1 o viceversa) è la più diffusa causa di errore
  • Le reti di parità/disparitè si usano per effettuare un semplice controllo di errore
  • In fase d trasmissione (o memorizzazione) si aggiunge un bit tale che il numero complessivo di bit “1″ sia a parità assegnata (p.e. pari)- Il bit si dice di parità
  • In fase di ricezione (o lettura) una rete di parità (o disparità) controlla la parità e, se diversa da quella assegnata, segnala l’errore, ponendo ad esempio ad 1 un segnale di controllo err ed avendosi dunque:
    • err=1 -> CERTEZZA della sua presenza
    • err=0 -> PROBABILITA’ di assenza di errori
  • Il sistema si basa sulla massimizzazione di questa probabilità

Controllo di errori

I riferimenti teorici – distanza di Hamming

  • L’informazione da trasmettere o memorizzare è un “codice a lunghezza fissa” (vedi lez. 10)
  • Distanza di Hamming D=numero di bit diversi tra due parole codice
  • Distanza minima di un codice: la distanza minima fra 2 sue parole-codiice
  • Sindrome di errore: la parola-codice non appartiene al codice

Controllo di errori

I riferimenti teorici – Teorema di Hamming

Un codice a distanza minima:

  • d+1 può individuare gli errori simultanei su d bit
  • 2c+1 può correggere gli errori simultanei su c bit

Controllo di errori

Disparità e controllo di errore

  • In partenza (o in scrittura), d(X) calcola il bit di parità
  • In arrivo (o lettura), d(X) calcola il segnale err
  • Si ricorda:
    • err=0 -> probabilmente è X’=X
    • err=0 -> certamente è X’≠X
    • (potrebbe anche essere X’=X perché l’errore è sul bit di parità:. trascuriamo questo caso per sicurezza e semplicità)
Schema esplicativo

Schema esplicativo


Decomposizione funzionale

  • Decomposizione funzionale in generale
  • Decomposizione funzionale (D.F.): funzione in funzione di funzioni
  • D.F. semplice (D.F.S): Funzioni di livello 2
  • D.F. disgiunta (D.F.D): le funzioni componenti fanno capo ad insiemi disgiunti delle X
  • D.F. semplice e disgiunta (D.F.S.D.):
  • Le D.F. già incontrate
    • Forme elementari (canoniche o semplici): D.F.S.D. in (AND,OR,NOT), (NAND), (NOR)
    • XOR generalizzate: D.F.D. in termini di XOR più semplici

Decomposizione funzionale

Decomposizione funzionale particolare

  • D.F.S.D. in termini di funzione qualsiasi ? Esiste possibilità di riconoscere se esiste una forma del tipo
    • Insiemi X1 e X2, Funzioni g1 ed g2
    • y1 = g1(X1)
    • f(X) = g2 (X2,y1)
  • SI RINVIA AGLI APPROFONDIMENTI
Schema esplicativo

Schema esplicativo


Prossima lezione

Minimizzazione – Parte I – Modulo 2

I materiali di supporto della lezione

B. Fadini, A. Esposito, Teoria e Progetto delle Reti Logiche, Napoli Liguori Ed., II ed, 1994. Cap. I

U. De Carlini, B. Fadini, Macchine per l'elaborazione delle informazioni, Napoli Liguori Ed., II ed., 1995 (Capitoli III e VII)

B. Fadini, N. Mazzocca, Reti Logiche – Complementi ed Esercizi, Napoli Liguori Ed. 1995

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion