Vai alla Home Page About me Courseware Federica Living Library Federica Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica
 
I corsi di Ingegneria
 
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