2012.12.17.
DIGITAL TECHNICS I Dr. Bálint Pődör Óbuda University, Microelectronics and Technology Institute 12. LECTURE: FUNCTIONAL BUILDING BLOCKS III
1st year BSc course 1st (Autumn) term 2012/2013 (Temporary, not-edited version!)
1
12. LECTURE 1. Parity bit, parity generator 2. Arithmetic elements
2
1
2012.12.17.
HIBAJELZÉS ÉS HIBAJAVÍTÁS Hibajavítás: hiba felismerés illetve hiba javítása. Redundancia szükésges a kódban. Legegyszerűbb eset: bit-hiba jelzése Elv: a hiba akkor deríthető fel, ha a kódszó készletben bármely két kódszó között a Hamming-távolság legalább kettő, vagy nagyobb.
3
Kódok hibavédelmi képessége
Adatforrás
Rendeltetési hely
Átvivő közeg
Zaj, zavar Hiba felismerés feltétele:
Hiba javítás feltétele:
D2
D3
Általánosságban
2 m k 1 k
m információs bithez k ellenőrző bit szükséges 4
2
2012.12.17.
HAMMING TÁVOLSÁG Két kódszó Hamming távolságát úgy határozzák meg, hogy a két kódszó azonos helyen álló elemeit összehasonlítják, és megállapítják hány helyen áll különböző bit. Az így kapott szám a Hamming távolság. A Gray kód pl. bármely két szomszédos kódszava csak egy bitben különbözik, ezért a Gray kód Hamming távolsága 1. A BCD és a bináris kód (legkisebb) Hamming távolsága szintén 1.
5
HIBAFELISMERŐ ÉS HIBAJAVÍTÓ KÓDOK
Legegyszerűbb hibafelismerési eljárás:
paritásbit átvitele Két lehetőség páros paritás páratlan paritás
Kód Paritásbit 11011 11010
6
3
2012.12.17.
PARITÁSBIT Páros paritás: az 1-esek száma páros. A kódszóban lévő 1-esek számát 1 vagy 0 hozzáadásával párossá egészítjük ki. 0 a paritásbit, ha az 1-esek száma páros volt. Páratlan paritás: az 1-esek száma páratlan. A kódszóban lévő 1-esek számát 1 vagy 0 hozzáadásával páratlanná egészítjük ki. 1 a paritásbit, ha az 1-esek száma páros volt.
7
PARITÁS GENERÁTOR Paritásbit képzése: ANTIVALENCIA (XOR) művelet alkalmazása a kódszó bitjeire, pl. 4 bit esetén háromszor.
Példa: Kódszó
Paritásbit
0001 0110 1110
0001=1 0110=0 1110=1 8
4
2012.12.17.
PÁROS PARITÁSBIT GENERÁLÁS A
B
C
D
F
0
0
0
0
0
0
0
0
1
1
0
0
1
0
1
0
0
1
1
0
0
1
0
0
1
0
1
0
1
0
0
1
1
0
0
0
1
1
1
1
1
0
0
0
1
1
0
0
1
0
1
0
1
0
X
1
0
1
1
X
1
1
0
0
X
1
1
0
1
X
1
1
1
0
X
1
1
1
1
X
Egy F(A,B,C,D) logikai függvény 4-bites BCD karaktereket egészít ki páros paritás bittel. Készítsen logikai hálózatot a megvalósításra.
F(A,B,C,D) = 4 (1,2,4,7,8)X:(10-15) 9
PÁROS PARITÁSBIT GENERÁLÁS C 1
1
1
1 B
X
X
X
X
X
X
A 1 D
10
5
2012.12.17.
PÁROS PARITÁSBIT GENERÁLÁS F=ABCD
C 1
1
1
=1
1
=1
B X
X
X
X
X
X
=1
A 1
D
11
13-INPUT PARITY CHECKER/GENERATOR The HEF4531B is a parity checker/generator with 13 parity inputs (I0 to I12) and a parity output (O). When the number of parity inputs that are HIGH is even, the output is LOW. When the number of parity inputs that are HIGH is odd, the output is HIGH. For words of 12 bits or less, the output can be used to generate either odd or even parity by appropriate termination of the unused parity input(s). For words of 14 or more bits, the devices can be cascaded by connecting the output of one device to any parity input of another device. When cascading devices, it is recommended that the output of one device be connected to the I12 input of the other device since there is less delay to the output from the I12 input than from any other input (I0 to I11).
Functional diagram of HEF4531B parity checker/generator
12
6
2012.12.17.
13-INPUT PARITY CHECKER/GENERATOR
Logic diagram Pinning diagram
13
Circuits for Binary Addition • Half adder (add two 1-bit numbers) – Sum = Ai' Bi + Ai Bi' = Ai xor Bi – Cout = Ai Bi • Full adder (carry-in to cascade for multi-bit adders) – Sum = Ci xor A xor B – Cout = B Ci + A Ci + A B = Ci (A + B) + A B
Ai 0 0 1 1
Bi 0 1 0 1
Sum Cout 0 0 1 0 1 0 1 1
Ai 0 0 0 0 1 1 1 1
Bi 0 0 1 1 0 0 1 1
Cin 0 1 0 1 0 1 0 1
Sum Cout 0 0 1 0 1 0 0 1 1 0 0 1 0 1 1 1
7
2012.12.17.
FÉLÖSSZEADÓ (HALF-ADDER) Feladata két bit összeadása
S
A HA
C
B S: sum C: carry
15
HALF ADDER —
—
S = AB + AB = A B C=AB Félösszeadó: két bemenet és két kimenet. Két bináris számjegyet tud összeadni, előállítja az összeget és átvitelt. Nem veszi figyelembe a kisebb helyértékről jövő átvitelt.
A B
•
•
=1
S
&
C
félösszeadó 16
8
2012.12.17.
(1-BIT) FULL ADDER • Its function is to add two bits and the carry from the previous position, and to generate the sum and the carry S = S(A,B,Cin)
Cout = C(A,B,Cin)
A B
S Full adder Cout
Cin
17
A TELJES ÖSSZEADÓ EGYENLETEI A 0 0 0 0 1 1 1 1
B Cin 0 0 0 1 1 0 1 1 0 0 0 1 1 0 1 1
S Cou 0 0 1 0 1 0 0 1 1 0 0 1 0 1 1 1
__ _ _ S = ABCin + ABCin + __ ABCin + ABCin = A B Cin az összeg bit 1-es, ha a három változó közül egy vagy három 1-es (kizáró VAGY függvény) Cout = (A B)Cin + AB (Vagy minimalizálva: Cout = AB + BCin + ACin)
az átvitel bit 1-es, ha két változó egyidejűleg 1-es (majoritás logikai függvény)
18
9
2012.12.17.
FULL ADDER: BOOLEAN FUNCTIONS Sum __ _ _ __ Si = AiBiCi-1 + AiBiCi-1 + AiBiCi-1 + AiBiCi-1
Carry _ _ _ Ci = AiBiCi-1 + AiBiCi-1 + AiBiCi-1 + AiBiCi-1 = AiBi + AiCi-1 + BiCi-1 The sum can be expressed as a three-variable exclusive OR function (Si = AiBiCi). The carry is the three-variable majority function and can also be expressed in various other algebraic forms. 19
TELJES ÖSSZEADÓ (FULL ADDER) A B Cin S Co ut
0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 1 Késleltetés: összeg (S) 3tgate átvitel (Cout) 2tgate
1 0 0 1
1 0 1 0
0 1 0 0
1 0 1 1
1 1 1 1 1 20
10
2012.12.17.
Full adder implementations A B
• Standard approach – 6 gates – 2 XORs, 2 ANDs, 2 ORs
S
Cin A B Cin
Cout
A B
• – – –
Alternative implementation Cout = A B + Cin (A xor B) = A B + B Cin + A Cin 5 gates half adder is an XOR gate and AND gate 2 XORs, 2 ANDs, 1 OR A B
A xor B Half Adder Cout A B
Sum
A xor B xor Cin Half Adder Cout Cin (A xor B)
Cin
Sum Sum
Cout
TELJES ÖSSZEADÓ A teljes összeadó két félösszeadóból állítható össze. Az első képezi a két összeadandó bit összegét, a második ehhez adja hozzá az előző helyértéken keletkezett átvitelt.
(Ai Bi) Ai Bi
Ci-1
+1/2
(Ai Bi) Ci-1 +1/2
AiBi
Késleltetés: összeg (S) 2tgate átvitel (C) 3tgate
(Ai Bi)Ci-1 1
Si
Ci 22
11
2012.12.17.
2-BIT BINARY FULL ADDER 54/7482
23
2-BIT BINARY FULL ADDER 54/7482
Function table and logic diagram
24
12
2012.12.17.
2-BIT BINARY FULL ADDER 54/7482
25
4 BITES PÁRHUZAMOS ÖSSZEADÓ (SOROS ÁTVITEL, RIPPLE CARRY) Az átvitel sorosan terjed!
y3 x3
TÖ c4
y2 x2 c3
TÖ
y1 x1 c2
TÖ
y0 x0 c1
c0
TÖ
s3
s2
s1
s0
y3 x3
y2 x2
y1 x1
y0 x0
cin
4-bites összeadó cout
s3
s2
s1
s0
26
13
2012.12.17.
4-BITES ÖSSZEADÓ
• Négy teljes összeadó egy 4-bites összeadót alkot. • Összesen kilenc bemenet: – Két 4-bites szám, A3 A2 A1 A0 és B3 B2 B1 B0 – Egy áthozat, CI • Öt kimenet: – Egy 4-bites összeg, S3 S2 S1 S0 – Egy átvitel, CO • Ha strukturálatlan kombinációs hálózatként kezelnénk, akkor egy 512-soros, és 5 kimenetű igazságtáblázattal lehetne leírni! 27
KASZKÁD KAPCSOLÁS
Két 4-bites összeadóból kaszkád kapcsolással 8-bites összeadó alakítható ki, stb.
28
14
2012.12.17.
ÖSSZEADÓ/KIVONÓ ÁRAMKÖR 2-ES KOMPLEMENS B2
A2
B1
A1
B0
A0
ADD/SUB
BIN(n)
Bn
0
0
0
0
1
1
1
0
1
1
1
0
ADD/SUB
B
A CIN
B
Full Adder
COUT
A CIN
Full Adder
COUT
SUM
SUM
B
A CIN
Full Adder
COUT
SUM
A/S 0 Bin B & C IN 0 Q A B
Q2
Q1
Q0
XOR kapuk mint vezérelt inverterek funkcionálnak
A / S 1 Bin B & C IN 1 Q A B
29
4 BITES ÖSSZEADÓ/KIVONÓ ÁRAMKÖR x3 x2 x1 x0 y3
y2
cin A MUX MUX
B
y1
MUX
y0
MUX
s
4 bites teljes összeadó C
z3 z2 z1 z0
30 cout
15
2012.12.17.
TWO’S COMPLEMENT ADDER/SUBTRACTOR Q = (q3 q2 q1 q0)2 P = (p3 p2 p1 p0)2
4A3A2A 1A 4B 3B 2B 1B
MUX (74157) 4Y 3Y 2Y 1Y
A4 A3 A2 A1 C4
Select
S G
B4 B3 B2 B1
ADDER (7483) S4 S3 S2 S1
C0 Select
Function
0
R=P+Q
1
R=P+Q+1
R = (r4 r3 r2 r1)2
KITEKINTÉS: ARITMETIKAI LOGIKAI EGYSÉG (ALU) Mind TTL, mind CMOS változatban van ALU (24 kivezetéses tokozás): Két 4-4 bites kódszón bitenként elvégezhető többek között mind a 16 kétváltozós logikai művelet (logikai függvény), az eredmény szintén 4-változós kódszóként adódik.
32
16
2012.12.17.
1-BITES ”ALU”
33
ARITHMETIC LOGIC UNIT (ALU) x
y n
n
Shift count
OP code
Arithmetic
Logic
Shifter
CTRL
MUX
MUX
n Cond. code z
34
17
