2
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
1
REPRESENTACIÓ INFORMACIÓ
2.1 Concepte de representació de la informació
2.2 Representació i aritmètica de nombres naturals
2.3 Representació i aritmètica de nombres enters
2.4 Representació de nombres reals
2.5 Altres mètodes de codificació de la informació
Dr. Joaquim Salvi, Dr. Arnau OliverEscola Politècnica Superior
Universitat de Girona
2
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
2.1 Concepte de representació de la informació
Informació: conjunt organitzat de dades que constitueixen un missatge capaç de canviar l’estat de coneixement del receptor.
Informar: acció de transmetre informació.
Informàtica: ciència que estudia el tractament automàtic de la informació.
3
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Procés d’informar
Canal: Medi a través del que es transmet la informació des de l’origen al destí.
Com que el medi no és perfecte, la informació que arriba al destí normalment no equival a la que ha enviat l’origen degut a pertorbacions externes que anomenem soroll.
Medi natural: ex: aire, poden transmetre ones mecàniques (parla) o ones electromagnètiques (ràdio, TV, 3G)
Medi artificial: ex: cables, poden transmetre electricitat (telèfon)
EMISOR MISSATGE CodificarDecodi-
ficarMISSATGE RECEPTORCANAL
SOROLL
4
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Codificació
Apareix la necessitat de codificar el missatge per a poder ser transmès pel medi i reduir l’efecte del soroll.
Alfabet: conjunt de símbols diferents utilitzats en la formació de codis
Base: nombre de símbols diferents d’un alfabet.
Codi: seqüència de símbols que representen un determinat fet o idea (missatge).
5
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
EGIPCI MAIA
AZTECASUDARÀBIC CUNEIFORME HITITA
FENICI
GREC
6
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Codificació
Amb un alfabet de N símbols i un codi de llargada M podem generar fins a NM missatges diferents.
N=2 Codi binari, Codi Morse
N=10 Codi decimal
N=26 Alfabet català
Cada símbol proporciona una quantitat d’informació Q inversament proporcional a la probabilitat d’aparició P.
Q=f(1/P) ex: GRN GIRONA Q 20% (Consonants)
ex: IOA GIRONA Q 5% (Vocals)
Quan tots els símbols són equiprobables, la informació transmesa és màxima i la mida del missatge més eficient.
7
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Senyals
La senyal és la portadora d’un missatge a través d’un medi.
Senyals deterministes: poden saber el seu valor en qualsevol instant de temps. Ex: y = cos(t)
Senyals aleatoris: no podem saber el seu valor exacte en un instant de temps, però si una probabilitat. Ex: y = pluja(t)
Senyals continus: el senyal és funció de variables contínues. Ex: temperatura física
Senyals discrets: el senyal és funció de variables discretes. Ex: dies de la setmana
Senyals analògics: el senyal és funció de variables continues dins d’un marge definit. Ex: indicador de velocitat
Senyals digitals: el senyal és funció de variables discretes que només poden prendre dos valors. Ex: interruptor de la llum
8
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Sistemes analògics i digitals
Els sistemes digitals són menys propensos a errors, més resistents al soroll i poden implementar sistemes de detecció i correcció d’errors en la transmissió del missatge.
Sistema analògicx(t) y(t)
analògic analògic
Sistema digitalx(t) y(t)
digital digital
Conversor
A / D
x(t) y(t)
analògic digital
Conversor
D / A
x(t) y(t)
digital analògic
9
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Sistemes digitals
Sistema digital asíncron: les variacions dels senyals es produeixen sense una cadència determinada
Sistema digital síncron: les variacions dels senyals es produeixen, si es produeixen, seguint la cadència que marca un senyal de clock.
Sistemes digitals combinacionals: Les sortides només depenen de les entrades en cada instant de temps: y(t) = f(x(t))
Sistemes digitals seqüencials: Les sortides depenen de les entrades i de la història d’aquestes entrades (estat del sistema):
y(t) = f(x(t), x(-,t-1)) y(t) = f(x(t), E(t))
asíncron síncron
10
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Representació i aritmètica de nombres Naturals
Sistema de numeració: codi emprat per a representar nombres com a cadenes de dígits
Base (B): nombre de símbols de l’alfabet
Símbol: cada un dels diferents elements de l’alfabet
Dígit: Posició d’un determinat símbol dins del codi
Notació posicional:
𝐴𝐵 = 𝐴𝑛𝐴𝑛−1…𝐴0 . 𝐴−1𝐴−𝑝 𝐵 0 ≤ 𝐴𝑖 < 𝐵
Polinomi equivalent: ens permet calcular el nombre en base 10
𝐴10 = 𝐴𝑛𝐵𝑛 + 𝐴𝑛−1𝐵
𝑛−1 +⋯+ 𝐴0𝐵0 + 𝐴−1𝐵
−1 + …+ 𝐴−𝑝𝐵−𝑝
= −𝑝𝑛 𝐴𝑖 𝐵𝑖
11
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
2.2 Representació i aritmètica de nombres Naturals
Exemples d’utilització del polinomi equivalent:
387.4510 = 3 · 102 +8 · 101 + 7 · 100 +4 · 10−1 +5 · 10−2 = 387.4510
312.45 = 3 · 52 +1 · 51 + 2 · 50 +4 · 5−1 = 82.810
426.36 0 ≤ 𝐴𝑖 < 6 Aquest no és un nombre en base 6
01101.012 = 0 · 24 +1 · 23 + 1 · 22 + 0 · 21 + 1 · 20 + 0 · 2−1 +1 · 2−2
= 13.2510
12
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Representació i aritmètica de nombres Naturals
Càlcul del nombre mínim de dígits que ens fa falta per a representar un nombre N10 a base B.
𝐵𝑛−1 ≤ 𝑁 < 𝐵𝑛
𝑙𝑜𝑔𝐵𝐵𝑛−1 ≤ 𝑙𝑜𝑔𝐵𝑁 < 𝑙𝑜𝑔𝐵𝐵
𝑛
𝑛 − 1 ≤ 𝑙𝑜𝑔𝐵𝑁 < 𝑛
Ex: representa el nombre N = 23510 en base 10
𝑛 − 1 ≤ 𝑙𝑜𝑔10235 < 𝑛
𝑛 − 1 ≤ 2,371 < 𝑛 → 𝑛 = 3 (nombre enter)
13
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Representació i aritmètica de nombres Naturals
Canvis de base
Per passar un nombre N en base B a base 10 utilitzarem el polinomi equivalent
𝑁𝐵 → 𝑀10 𝑀10 =
−𝑝
𝑛
𝑁𝑖 𝐵𝑖
Per passar un nombre N en base 10 a base B utilitzarem el mètode de les divisions i els productes successius.
𝑁10 → 𝑀𝐵 𝐷𝑖𝑣𝑖𝑠𝑖𝑜𝑛𝑠 − 𝑃𝑟𝑜𝑑𝑢𝑐𝑡𝑒𝑠 𝑠𝑢𝑐𝑐𝑒𝑠𝑠𝑖𝑢𝑠
Per a convertir un nombre N de base 𝐵1 a base 𝐵2 passarem per base 10.
𝑁𝐵1 → 𝑀10 → 𝑃𝐵2
14
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Representació i aritmètica de nombres Naturals
Exemples d’utilització del mètode de divisions–productes successius:
15310 = 2318
1538 = 19 𝑟𝑒𝑠𝑡𝑒 = 1
198 = 2 𝑟𝑒𝑠𝑡𝑒 = 3
2 8 = 0 𝑟𝑒𝑠𝑡𝑒 = 2
15
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Representació i aritmètica de nombres Naturals
Exemples d’utilització del mètode de divisions–productes successius:
0.687510 = 0.10112
0.6875 ∗ 2 = 1.37500.3750 ∗ 2 = 0.75000.7500 ∗ 2 = 1.50000. 5000 ∗ 2 = 1.0000
16
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Representació i aritmètica de nombres Naturals
Exemples d’utilització del mètode de divisions–productes successius:
En alguns casos hem de parar d’agafar decimals quan la precisió que aconseguim sigui la desitjada.
0.51310 ≈ 0.406518 l’Error 𝜀 = 0.51310 – (0.406518 → 𝑁10)
0.513 ∗ 8 = 4.1040.104 ∗ 8 = 0.8320.832 ∗ 8 = 6.6560.656 ∗ 8 = 5.2480.248 ∗ 8 = 1.984
...
17
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Representació i aritmètica de nombres Naturals
Exemples d’utilització del mètode de divisions–productes successius:
113.25610 = 1110001.012
113 2 0.256 ∗ 2 = 0.512
13 56 2 0.512 ∗ 2 = 1.024
1 16 28 2
0 0 14 2
0 7 2
1 3 2
1 1
18
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Sistemes de numeració d’interès en Informàtica
BINARI
Alfabet = 0,1 Base = 2
Cada dígit rep el nom de Bit.
Molt important doncs els sistemes digitals treballen de forma molt eficient emprant dos estats (encès/apagat, cert/fals, 1/0).
Decimal Binari
0 000
1 001
2 010
3 011
4 100
5 101
6 110
7 111
211 210 29 28 27 26 25 24 23 22 21 20
2048 1024 512 256 128 64 32 16 8 4 2 1
19
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Sistemes de numeració d’interès en Informàtica
OCTAL
Alfabet = 0,1,2,3,4,5,6,7 Base = 8
Decimal Octal
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
Decimal Octal
8 10
9 11
10 12
11 13
12 14
13 15
14 16
15 17
20
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Sistemes de numeració d’interès en Informàtica
HEXADECIMAL
Alfabet = 0,1,2,3,4,5,6,7,8,9, A, B, C, D, E, F Base = 16
Decimal Hexadecimal
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
Decimal Hexadecimal
8 8
9 9
10 A
11 B
12 C
13 D
14 E
15 F
Decimal Hexadecimal
16 10
17 11
18 12
19 13
20 14
21 15
22 16
23 17
21
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Canvis de base entre bases que són potència
𝑁𝐵 → 𝑀𝐵𝑝
Per passar un nombre N en base 𝐵 a base 𝐵𝑝, agruparem els dígits de N en grups de p elements a partir del punt decimal, afegint ceros si convé i aleshores convertim independentment cada grup a un dígit de M.
𝑁𝐵𝑝 → 𝑀𝐵
Per passar un nombre N en base 𝐵𝑝 a base 𝐵, transformarem cada dígit de N als P dígits de M que correspongui de forma totalment independent.
22
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Canvis de base entre bases que són potència
Exemples de canvis de base 𝑁𝐵 → 𝑀𝐵𝑝 :
1101100111011.0112 → 𝑀16 = 𝑀24
0001 1011 0011 1011.01102 → 1B3B. 616
12021.2123 → 𝑀9 = 𝑀32
01 20 21. 21 202 → 167.769
1101100111011.0112 → 𝑀4 = 𝑀22
01 10 11 00 11 10 11.01 102 → 1230323.124
Base 3 Base 9
00 0
01 1
02 2
10 3
11 4
12 5
20 6
21 7
22 8
Base 2 Base 4
00 0
01 1
10 2
11 3
23
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Canvis de base entre bases que són potència
Exemples de canvis de base 𝑁𝐵𝑝 → 𝑀𝐵 :
18F. 3816 → 𝑀218F. 3824 → 0001 1000 1111.0011 10002
18F. 3816 → 𝑀418F. 3842 → 12033.0324
Base 16 Base 4
0 00
1 01
2 02
3 03
4 10
5 11
6 12
7 13
8 20
9 21
A 22
B 23
C 30
D 31
E 32
F 33
24
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Canvis de base entre bases que són potència
Mètode de Ruffini: Ruffini es un mètode per transformar nombres Naturals (sense decimals) de 𝑁𝐵 → 𝑀10:
𝑁𝑛 𝑁𝑛−1 𝑁1 𝑁0
𝐵 𝐵 · 𝑁𝑛
𝑁𝑛 𝐵 · 𝑁𝑛 +𝑁𝑛−1 0𝑛𝑁𝑖 𝐵𝑖
25
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Canvis de base entre bases que són potència
Exemple d’utilització del mètode de Ruffini:
110102 → 2610 3F16 → 6310
1 1 0 1 0 3 F
2 2 6 12 26 16 48
1 3 6 13 26 3 63
26
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
2.3 Representació i aritmètica de nombres enters
El nombres enters són nombres naturals amb signe (+/-).
Estudiarem 3 maneres de representar-los:
- Magnitud i signe
- Complement a radical disminuït
- Complement a radical
27
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Magnitud i signe
Aquesta és la representació que utilitzem per a representar nombres naturals emprant el sistema decimal. Senzillament afegim una grafia (+/-) per a representar el signe davant del nombre natural.
−31010
En decimal, la grafia (+/-) la representarem amb un bit de signeS = (+→ 0; −→ 1)
−𝑁10= 𝑆𝑀𝑛−1𝑀𝑛−2…𝑀0 = 𝑀2
−310= 1112 +310= 0112
Rang de representació: + 2𝑛−1 − 1 ,− 2𝑛−1 − 1
S Magnitud
n bits
n-1 bits1 bit
28
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Complement a radical disminuït
Fer el complement a radical disminuït (CRD) d’un nombre equival a canviar-li el signe de la següent manera:
𝑁𝐵𝐶𝑅𝐷
−𝑁𝐵 = 𝐵𝑛 − 1 − 𝑁𝐵 on 𝑛=nombre de bits de 𝑁𝐵
Ex:
54670010𝐶𝑅𝐷
−54670010= 106 − 1 − 54670010== 999999 − 546700 = 45329910
45329910𝐶𝑅𝐷
−45329910= 106 − 1 − 45329910== 999999 − 453299 = 54670010
38EA16𝐶𝑅𝐷
−38EA16= 164 − 1 − 38EA16= FFFF − 38EA == C71516
29
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Complement a 1: C’1
En base 2 el complement a radical disminuït rep el nom de complement a 1: C’1.
Sabrem si un nombre es positiu o negatiu fixant-nos amb el primer bit (0 → +; 1 → −)
Ex:
10110012𝐶′1
−10110012= 27 − 1 − 10110012== 1111111 − 1011001 = 01001102
01001102 = 3810 10110012 = −3810
Fer el C’1 d’un nombre equival a canviar 0 → 1 i 1 → 0.
Rang de representació: + 2𝑛−1 − 1 ,− 2𝑛−1 − 1 =+ 27−1 − 1 ,− 27−1 − 1 = +63,−63
30
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Complement a 1: C’1
La simetria del rang ( + 2𝑛−1 − 1 ,− 2𝑛−1 − 1 ) comporta que tinguem dos representacions del 0: tenim +0 i -0. Això és una ineficiència del CRD que ho resoldrem amb el complement a radical (CR).
Ex: per n=3 el rang de representació és [+3,-3]
C’1 Decimal
000 0
001 1
010 2
011 3
100 -3
101 -2
110 -1
111 -0
31
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Complement a radical
Fer el complement a radical (CR) d’un nombre equival a canviar-li el signe de la següent manera:
𝑁𝐵𝐶𝑅−𝑁𝐵 = 𝐵𝑛 − 𝑁𝐵 𝑠𝑖 𝑁𝐵 > 0; 0 𝑠𝑖 𝑁𝐵 = 0
on 𝑛=nombre de bits de 𝑁𝐵
D’aquesta manera el 𝐶𝑅 𝑁𝐵 = 𝐶𝑅𝐷 𝑁𝐵 + 1
Ex:
238910𝐶𝑅−238910= 104 − 238910 = 10000 − 2389 = 761110
238910𝐶𝑅
9999 − 2389 + 1 = 7610 + 1 = 761110
Per 𝑛 = 4 i 010 tenim 010𝐶𝑅−010= 104 − 010 = 10000 − 0 =
10000 = 0000 = 0, tenim doncs una única representació pel 0.
32
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Complement a 2: C’2
En base 2 el complement a radical rep el nom de complement a 2: C’2.
Sabrem si un nombre es positiu o negatiu fixant-nos amb el primer bit (0 → +; 1 → −)
Ex:
10110012𝐶′2
𝐶′1 1011001 + 1 = 0100110 + 1 = 01001112
01001112𝐶′2
𝐶′1 0100111 + 1 = 1011000 + 1 = 10110012
01001102 = 3810 10110012 = −3810
Rang de representació: + 2𝑛−1 − 1 ,−2𝑛−1 = +(27−1 −
33
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Complement a 2: C’2
Ex: per n=3 el rang de representació és [+3,-4]
El C’2 és la forma Standard de representar nombres enters en sistemes digitals.
C’2 Decimal
000 0
001 1
010 2
011 3
100 -4
101 -3
110 -2
111 -1
34
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Overflow (Desbordament)
En la representació de nombres amb signe hem de tenir sempre en compte el rang de representació i estendre el signe si no tenim prou dígits per a representar-lo.
Ex: 310 + 1 = 0112 + 1 = 1002 = −4 𝑒𝑛 𝐶′2−3 𝑒𝑛 𝐶′1−0 𝑒𝑛 𝑀𝑆
En cap cas és +4 que és el nombre que buscàvem, degut a un desbordament.
35
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Overflow (Desbordament)
Estendrem doncs el 0112 en funció de la representació que utilitzem:
En MS afegirem 0 just desprès del bit de signe:+3 = 0112= 00112−3 = 1112= 10112
En C’1 i en C’2, estendrem el bit de signe+3 = 0112= 00112−3 = 101𝐶′2= 1101𝐶′2 ; −3 = 100𝐶′1= 1100𝐶′1
El bit de signe l’estendrem tantes vegades com sigui convenient per què tots els operants tinguin el mateix nombre de dígits i el resultat estigui dins del rang de representació
36
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Aritmètica amb nombres naturals
Si volem sumar dos nombres naturals de 𝑛 bits 𝑁2 i 𝑀2procedirem de la mateixa manera que fem en decimal.
𝑁𝑛−1 𝑁1 𝑁0
+ 𝑀𝑛−1 𝑀1 𝑀0
𝐶𝑛 𝑆𝑛−1 𝐶2 𝑆1 𝐶1 𝑆0
Sumant dos bits 𝑁𝑖 + 𝑀𝑖 obtenim un bit de suma 𝑆𝑖 i un bit de carry 𝐶𝑖+1
Ni Mi Si Ci+1
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1
37
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Aritmètica amb nombres naturals
Si sumem el bit de carry als bits dels operants tenim la forma tradicional de sumar nombres binaris naturals.
𝐶𝑛−1 𝐶1𝑁𝑛−1 𝑁1 𝑁0
+ 𝑀𝑛−1 𝑀1 𝑀0
𝐶𝑛 𝑆𝑛−1 𝑆1 𝑆0
Ci Ni Mi Si Ci+1
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1
38
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Aritmètica amb nombres naturals
Si volem restar dos nombres naturals de 𝑛 bits 𝑁2 i 𝑀2procedirem de la mateixa manera que fem en decimal.
𝑁𝑛−1 𝑁1 𝑁0
+ 𝑀𝑛−1 𝑀1 𝑀0
𝐶𝑛 𝐷𝑛−1 𝐶2 𝐷1 𝐶1 𝐷0
Restant dos bits 𝑁𝑖 + 𝑀𝑖 obtenim un bit de diferència 𝐷𝑖 i un bit de carry 𝐶𝑖+1
Ni Mi Di Ci+1
0 0 0 0
0 1 1 1
1 0 1 0
1 1 0 0
39
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Aritmètica amb nombres naturals
Si sumem el bits de carry als bits de 𝑀 tenim la forma tradicional de restar nombres binaris naturals.
𝑁𝑛−1 𝑁1 𝑁0
𝐶𝑛−1 𝐶1 0−𝑀𝑛−1 𝑀1 𝑀0
𝐶𝑛 𝐷𝑛−1 𝐷1 𝐷0
Ni Mi Ci Di Ci+1
0 0 0 0 0
0 0 1 1 1
0 1 0 1 1
0 1 1 0 1
1 0 0 1 0
1 0 1 0 0
1 1 0 0 0
1 1 1 1 1
40
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Aritmètica amb nombres enters
Tenim dues eines per sumar i restar nombres amb signe: el mètode de la suma i de la resta que hem vist abans.
Sabem, però, que 𝐴 − 𝐵 = 𝐴 + (−𝐵)
Podem, per tant simplificar i eliminar el mètode de restar, només canviant el signe dels operants?
41
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Aritmètica amb nombres enters
En Magnitud i Signe:
𝐴 + 𝐵 = 𝑠𝑖𝑔𝑛 𝐴 = 𝑠𝑖𝑔𝑛(𝐵) 𝐴 + 𝐵
𝑠𝑖𝑔𝑛 𝐴 ≠ 𝑠𝑖𝑔𝑛 𝐵 𝐴 − 𝐵 𝑜 𝐵 − 𝐴
𝐴 − 𝐵 = 𝑠𝑖𝑔𝑛 𝐴 = 𝑠𝑖𝑔𝑛 𝐵 𝐴 − 𝐵 𝑜 𝐵 − 𝐴
𝑠𝑖𝑔𝑛 𝐴 ≠ 𝑠𝑖𝑔𝑛 𝐵 𝐴 + 𝐵
No podem prescindir de l’operació de resta i l’algorisme és complex.
42
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Aritmètica amb nombres enters
En C’1, 𝐴 − 𝐵 = 𝐴 + −𝐵
Estendrem el signe per obtenir dos operants amb el mateix nombre de bits.
Sumarem el bit de carry 𝐶𝑛 del resultat de la suma al propi sumant.
Ex:
110 − 610 = 01𝐶′1 + −0110𝐶′1 = 01𝐶′1+1001𝐶′1 =0001𝐶′1+1001𝐶′1 = 01010𝐶′1 = 1010𝐶′1 + 0 = 1010𝐶′1 = −510
710 + (−310) = 0111𝐶′1 + −011𝐶′1 = 0111𝐶′1+100𝐶′1 =0111𝐶′1+1100𝐶′1 = 10011𝐶′1 = 0011𝐶′1 + 1 = 0100𝐶′1 = 410
43
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Aritmètica amb nombres enters
En C’1, 𝐴 − 𝐵 = 𝐴 + −𝐵
Si al sumar dos nombres del mateix signe, el resultat té signe contrari aleshores s’ha produït overflow i haurem d’estendre els bits dels operants i repetir l’operació.
Ex:
−710 − 510 = 1000𝐶′1 + −0101𝐶′1 = 1000𝐶′1+1010𝐶′1 =10010𝐶′1 = 0010𝐶′1 + 1 = 0011𝐶′1 = 310 Overflow
= 11000𝐶′1+11010𝐶′1 =110010𝐶′1 = 10010𝐶′1 + 1 = 10011𝐶′1 = −1210
44
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Aritmètica amb nombres enters
En C’2, 𝐴 − 𝐵 = 𝐴 + −𝐵
Estendrem el signe per obtenir dos operants amb el mateix nombre de bits. Prescindim del bit de carry 𝐶𝑛 del resultat
Si al sumar dos nombres del mateix signe, el resultat té signe contrari aleshores s’ha produït overflow i haurem d’estendre els bits dels operants i repetir l’operació.
Ex: −410 − 310 = 1100𝐶′2 + 1101𝐶′2 = 11001𝐶′2 = 1001𝐶′2 = −710
−710 + −610 = 1001𝐶′2 + 1010𝐶′2 = 10011𝐶′2 = +310 Overflow
−710 + −610 = 11001𝐶′2 + 11010𝐶′2 = 110011𝐶′2 = −1310
45
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Aritmètica amb nombres enters
En C’1, 𝐴 − 𝐵 = 𝐴 + −𝐵
Si al sumar dos nombres del mateix signe, el resultat té signe contrari aleshores s’ha produït overflow i haurem d’estendre els bits dels operants i repetir l’operació.
Ex:
−710 − 510 = 1000𝐶′1 + −0101𝐶′1 = 1000𝐶′1+1010𝐶′1 =10010𝐶′1 = 0010𝐶′1 + 1 = 0011𝐶′1 = 310 Overflow
= 11000𝐶′1+11010𝐶′1 =110010𝐶′1 = 10010𝐶′1 + 1 = 10011𝐶′1 = −1210
46
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Desplaçaments aritmètics amb nombres naturals
Desplaçament a l’esquerra:
𝑍𝐵 = (𝐴𝐵 ∗ B)= 𝐴𝑛𝐵𝑛 + 𝐴𝑛−1𝐵
𝑛−1 +⋯+ 𝐴0𝐵0 B = 𝐴𝑛𝐵
𝑛+1 +𝐴𝑛−1𝐵
𝑛 +⋯+ 𝐴0𝐵1 equival a desplaçar el nombre A una posició
a l’esquerra afegint un zero a la dreta i eliminant el dígit 𝐴𝑛
Si 𝐴𝑛 = 1 es produeix overflow
Ex:
001102 = 610𝑒𝑠𝑞
0110𝟎2 = 1210𝑒𝑠𝑞
1100𝟎2 = 2410
47
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Desplaçaments aritmètics amb nombres naturals
Desplaçament a la dreta:
𝑍𝐵 = (𝐴𝐵/B)= 𝐴𝑛𝐵𝑛 + 𝐴𝑛−1𝐵
𝑛−1 +⋯+ 𝐴0𝐵0 /B = 𝐴𝑛𝐵
𝑛−1 +𝐴𝑛−1𝐵
𝑛−2 +⋯+ 𝐴1𝐵0 equival a desplaçar el nombre A una
posició a la dreta afegint un zero a l’esquerra i eliminant el dígit 𝐴0
No es produeix overflow, però es pot perdre precisió.
Ex:
011012 = 610𝑑𝑟𝑡
𝟎01102 = 310𝑑𝑟𝑡
𝟎00012 = 110
48
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Desplaçaments aritmètics amb nombres enters
Desplaçament a l’esquerra: En MS i C’2 es desplaça el nombre 𝐴𝑛−1𝐴𝑛−2…𝐴1𝐴0 una posició a l’esquerra, afegint un 0 a la dreta, mantenint el bit de signe 𝐴𝑛sense desplaçar i per tant perdent el bit 𝐴𝑛−1 En C’1 no es pot utilitzar.
Es produeix overflow quan 𝐴𝑛−1 ≠ 𝐴𝑛
Ex:
001102 = 610𝑒𝑠𝑞
00110𝟎2 = 0110𝟎2 = 1210𝑒𝑠𝑞
01100𝟎2 =0100𝟎2 = 810 Overflow doncs 𝐴𝑛−1 ≠ 𝐴𝑛
1111𝑐′2 = −110𝑒𝑠𝑞
1110𝒄′2 = −210𝑒𝑠𝑞
1100𝑐′2 = −410
1110𝑐′1 = −110𝑒𝑠𝑞
1100𝒄′1 = −310𝑒𝑠𝑞
1000𝑐′1 = −710
49
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Desplaçaments aritmètics amb nombres enters
Desplaçament a la dreta:
En MS es desplaça el nombre 𝐴𝑛−1𝐴𝑛−2…𝐴1𝐴0 una posició a la dreta, afegint un 0 entre el signe 𝐴𝑛 i 𝐴𝑛−1, mantenint el bit de signe 𝐴𝑛sense desplaçar i perdent el bit 𝐴0. No es produeix overflow però es pot perdre precisió.
En C’2 es desplaça el nombre 𝐴𝑛𝐴𝑛−1…𝐴1𝐴0 una posició a la dreta, estenen el signe 𝐴𝑛. No es produeix overflow però es perd precisió quan el bit desplaçat és 1.
Ex:
MS: 1101𝑀𝑆 = −510𝑑𝑟𝑡
1𝟎10𝑀𝑆 = −210
C’2:𝟏010𝐶′2 = −610𝑑𝑟𝑡
𝟏101𝐶′2 = −310𝑑𝑟𝑡
𝟏𝟏10𝐶′2 = −210
50
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Multiplicació de nombres naturals
Si els nombres tenen signe els passarem a nombres naturals, farem la multiplicació i li re-introduirem el signe al resultat.
𝑍𝐵 =(𝑋𝐵 ∗ 𝑌𝐵) = 𝑋𝐵 0𝑛𝑌𝑖 𝐵𝑖= 0
𝑛𝑋𝐵𝑌𝑖 𝐵𝑖
0 ≤ 𝑋𝐵 ≤ 2𝑛 − 1, 0 ≤ 𝑌𝐵 ≤ 2𝑛 − 1 0 ≤ 𝑍𝐵 < 22𝑛 − 1
Procedirem en binari igual com multipliquem en decimal.
51
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Multiplicació de nombres naturals
Ex: 0 1 1 1 1 0 (30)
0 1 0 1 1 1 (23)
0 1 1 1 1 0
0 1 1 1 1 0
0 1 1 1 1 0
0 0 0 0 0 0
0 1 1 1 1 0
0 0 0 0 0 0
0 1 0 1 0 1 1 0 0 1 0 (690)
11 01
1 0
= 100
52
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Divisió de nombres naturals
Si els nombres tenen signe els passarem a nombres naturals, farem la divisió i li re-introduirem el signe al resultat.
Procedirem en binari igual com dividim en decimal.
Ex:
110,0,1 101
101 101
00101
101
0
53
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
2.4 Representació de nombres reals
El nombres reals són nombres amb signe i decimals
Estudiarem 2 maneres de representar-los:
- Coma fixa
- Coma flotant
54
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Coma fixa
Tenim 𝑛 bits per a representar un nombre 𝑁2 i decidim assignar 1 bit per signe 𝑆, 𝑛𝑒 per la part entera i 𝑛𝑓 bits per la part fraccionària: 𝑛 = 1 + 𝑛𝑒+𝑛𝑓; 𝑁2 = 𝑆𝐴𝑛𝑒−1𝐴𝑛𝑒−2…𝐴0. 𝐴−1…𝐴−𝑛𝑓
Interval de representació i precisió:
Precisió: distancia entre 2 nombres consecutius = 2−𝑛𝑓
−
−𝑛𝑓
𝑛𝑒−1
2𝑖 +
−𝑛𝑓
𝑛𝑒−1
2𝑖
+2−𝑛𝑓−2−𝑛𝑓 0
11...1.1...1 10...0.0..01 00...0.0..01 01...1.1...1
00...0.0...0
+2−𝑛𝑓
55
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Coma fixa
Ex:
Quin és l’interval de representació i la precisió per 𝑛𝑒 = 3 i
𝑛𝑓 = 5?
Part entera: de 0002 = 010 fins 1112 = 710
Part fraccionària: de .000012 = 0.0312510 fins .111112 = 0.96875102−1 + 2−2 + 2−3 + 2−4 + 2−5 = 0.5 + 0.25 + 0.125 + 0.0625 + 0.03125 = 0.9687510
1111.11111 1000.00001 0000.00001 0111.11111
0000.00000
-7.96875 -0.03125 +0.03125 +7.96875
+0.03125
0
56
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Coma fixa
Ex:
Quin és l’interval de representació i la precisió per 𝑛𝑒 = 5 i
𝑛𝑓 = 3?
Part entera: de 000002 = 010 fins 111112 = 3110
Part fraccionària: de .0012 = 0. 12510 fins .1112 = 0.875102−1 + 2−2 + 2−3 = 0.5 + 0.25 + 0.125 = 0. 87510
111111.111 100000.001 000000.001 011111.111
000000.000
-31. 875 -0.125 +0.125 +31.875
+0.125
0
57
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Coma fixa
Ex:
Quina és la representació en coma fixa del nombre 𝑁10 = −4.327si 𝑛𝑒 = 5 i 𝑛𝑓 = 6? Quin error cometem en la representació?
410 = 001002. 327 ∗ 2 = 0.654. 654 ∗ 2 = 1.308. 308 ∗ 2 = 0.616. 616 ∗ 2 = 1.232. 232 ∗ 2 = 0.464. 464 ∗ 2 = 0.928
0.32710 ≈ 0.0101002 = 0.5 + 0.0625 = 0.312510
Representació: 1 00100 010100
Error: 0.327-0.3125= 0.0145
58
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Coma fixa
Ex:
Quin és el mínim nombre de bits per a representar 𝑁10 = 6.465amb un error de representació < 0.01?
610 = 1102. 465 ∗ 2 = 0.93 𝜀 = 0.465 − 0 = 0.465
. 93 ∗ 2 = 1.86 𝜀 = 0.465 − 0.25 = 0.215
. 86 ∗ 2 = 1.72 𝜀 = 0.215 − 0.125 = 0.09
. 72 ∗ 2 = 1.44 𝜀 = 0.09 − 0.0625 = 0.0275
. 44 ∗ 2 = 0.88 𝜀 = 0.0275 − 0 = 0.0275
. 88 ∗ 2 = 1.76 𝜀 = 0.0275 − 0.015625 = 0.011875
. 76 ∗ 2 = 1.52 𝜀 = 0.011875 − 0.0078125 = 0.0040625 < 0.01
Representació: 0 110 0111011, per tant necessitem 11 bits.
59
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Coma flotant
Tenim 𝑛 bits per a representar un nombre 𝑁2 i decidim assignar 1 bit per signe 𝑆,i 𝑛𝑒 bits per l’exponent i 𝑛𝑚 per la mantissa : 𝑛 =1 + 𝑛𝑒+𝑛𝑚; 𝑁2 = 𝑆 𝑚𝑎𝑛𝑡𝑖𝑠𝑠𝑎 ∗ 2𝑒𝑥𝑝𝑜𝑛𝑒𝑛𝑡
L’exponent el representarem en C’2
La mantissa la normalitzarem de manera que la part entera sigui igual a 1. Aquest 1 no s’inclou en la representació.
Interval de representació:
La precisió depèn de cada nombre que representem. Quan major el nombre més petita la precisió i viceversa.
−𝑚𝑎𝑥 · 𝐵+𝑚𝑎𝑥 −𝑚𝑖𝑛 · 𝐵−𝑚𝑎𝑥 +𝑚𝑖𝑛 · 𝐵−𝑚𝑎𝑥 +𝑚𝑎𝑥 · 𝐵+𝑚𝑎𝑥
MNN mNN mNP MNP
60
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Coma flotant
Ex: Quina és la representació en coma flotant del nombre 𝑁10 =− 12.25 si 𝑛𝑚 = 9 i 𝑛𝑒 = 4? Determina el rang de representació?
12.2510 = 1100.012 = 1.10001 · 23
310 = 011𝐶′2 = 0011𝐶′2
Representació: 1 0011 100010000
Interval:
Màxima mantissa = 1.111111111 màxim exponent = 0111 (7)
Mínima mantissa = 1.000000000 mínim exponent = 1000 (-8)
MNP=1.111111111·27=11111111.11=28-1+0.5+0.25=255.75
mNP =1.0·2-8=1/256=0.00390625
MNN=-MNP mNN=-mNP
61
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Coma flotant
Ex: Representa el nombre 𝑁10 = 0.0465 en coma flotant si 𝑛𝑚 = 5i 𝑛𝑒 = 4?
N=0.0000101111=1.01111·2-5
-5=-(0101) = 1010+1=1011
Representació: 0 1011 01111
.0465 ∗ 2 = 0.093 0.5
. 093 ∗ 2 = 0.186 0.25
. 186 ∗ 2 = 0.372 0.125
. 372 ∗ 2 = 0.744 0.0625
. 744 ∗ 2 = 1.488 0.03125
. 488 ∗ 2 = 0.976 0.015625
. 976 ∗ 2 = 1.952 0.0078125
. 952 ∗ 2 = 1.904 0.00390625
. 904 ∗ 2 = 1.808 0.001953125
. 808 ∗ 2 = 1.616 0.0009765625
62
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
2.5 Altres mètodes de representació de la informació
Definicions:
Codi continu: Un codi binari és continu quan entre qualsevol dues codificacions de decimals adjacents només canvia 1 bit.
Codi cíclic: Un codi és cíclic si és continu i entre la darrera codificació i la primera codificació només canvia 1 bit.
Codi ponderat: Un codi és ponderat si a cada dígit binari se li assigna un pes en funció de la posició que ocupa el dígit en el codi.
63
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Altres codis de representació de la informació
Codi Gray: conegut com a codi reflexat. És continu i cíclic.
1 bit
Decimal Gray
0 0
1 1
2 bits
Decimal Gray
0 0 0
1 0 1
2 1 1
3 1 0
3 bits
Decimal Gray
0 0 00
1 0 01
2 0 11
3 0 10
4 1 10
5 1 11
6 1 01
7 1 00
64
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Altres codis de representació de la informació
Codi Gray:
Pas de codi binari a codi gray:
𝑁𝑛−1 𝑁𝑛−2… 𝑁2 𝑁1 𝑁0
𝑀𝑛−1 𝑀𝑛−2…𝑀2 𝑀1 𝑀0
Pas de codi gray a codi binari
𝑁𝑛−1 𝑁𝑛−2… 𝑁2 𝑁1 𝑁0
𝑀𝑛−1 𝑀𝑛−2…𝑀2 𝑀1 𝑀0
𝑀𝑖 = 0 𝑁𝑖 = 𝑁𝑖+1
𝑀𝑖 = 1 𝑁𝑖 ≠ 𝑁𝑖+1𝑀𝑛−1 = 𝑁𝑛−1
𝑀𝑛−1 = 𝑁𝑛−1
𝑀𝑖 = 0 𝑁𝑖 = 𝑀𝑖+1
𝑀𝑖 = 1 𝑁𝑖 ≠ 𝑀𝑖+1
65
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Altres codis de representació de la informació
Ex: convertir 11010111 de binari a Gray i de nou a binari
1 1 0 1 0 1 1 1
1 0 1 1 1 1 0 0 Sol: 10111100 en Gray
1 1 0 1 0 1 1 1 Sol: 11010111 en binari
66
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Altres codis de representació de la informació
Codi Johnson: És continu i cíclic.
1 bit
Decimal Johnson
0 0
1 1
2 bits
Decimal Johnson
0 00
1 01
2 11
3 10
3 bits
Decimal Johnson
0 000
1 001
2 011
3 111
4 110
5 100
67
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Altres codis de representació de la informació
Codi BCD (Binary Coded Decimal) Natural o BCD 8421: És ponderat. Es tracta de representar cada dígit decimal a binari de forma independent.
Ex: 58910= 0101 1000 1001BCD
Ex: 001110000100BCD=0011 1000 0100=38410
3 bits
Decimal BCD
0 0000
1 0001
2 0010
3 0011
4 0100
5 0101
6 0110
7 0111
8 1000
9 1001
68
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Altres codis de representació de la informació
Suma en Codi BCD 8421:
Sumem en binari cada grup de 4 bits. Si hi ha overflow sumem 0110 (6) al resultat i afegim 1 bit de carry al següent grup.
Ex: 24+17 = 410010 0100
0001 0111
0011 1011
1 0110
0100 0001
69
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Altres codis de representació de la informació
Codi BCD Excés 3: Equival al codi BCD 8421 + 0011 (3).
3 bits
Decimal BCD
0 0011
1 0100
2 0101
3 0110
4 0111
5 1000
6 1001
7 1010
8 1011
9 1100
70
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Altres codis de representació de la informació
També podem representar informació alfanumèrica a partir dels codis:
ASCII : American Standard Code for Information Interchange
EBCDIC: Extended BCD Interchange Code
Ambdós utilitzen grups de 8 bits anomenats bytes per a codificar nombres, lletres, caràcters de control, símbols de puntuació.
Amb 8 bits podem codificar fins a 256 símbols diferents. Els 127 primers són comuns, els altres 127 s’adapten a l’idioma (accents) i altres particularitats.
Actualment l’EBCDIC pràcticament no s’utilitza.
71
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Codi ASCII Standard: els 127 primers símbols (7 bits):
72
REPRESENTACIÓ DE LA INFORMACIÓ
ESTRUCTURA I TECNOLOGIA DE COMPUTADORS
Més informació:
Estructura i Tecnologia de Computadors, tema 2
https://www.documentauniversitaria.cat/botiga.php?a=llibre&id=809
www.unigrades.eu
Floyd, Thomas L. (2009). Digitals Fundamentals. PearsonInternational. – Capítol 2
Wikipedia: Codi Gray, Codi Johnson, Codi BCD,BCD Aiken i BCD XS3, Codi ASCII i Codi EBCDIC