"Esta obra, o primeiro de três volumes dedicados ao tema geral de Sistemas Digitais, constitui um trabalho de grande envergadura e exigência. Desconheço qualquer obra escrita em Portugal sobre o mesmo tema, nem conheço muitas, no mundo, que ofereçam a mesma abrangência e aprofundamento da matéria tratada. Pela coragem que revelou ao entregar-se a este trabalho, e pela forma cuidada como cumpriu a missão a que se propôs, são justificadas palavras de elogio ao seu autor."
José Alfredo Ribeiro da Silva Matos
Professor Catedrático da Faculdade de Engenharia
da Universidade do Porto
PREFÁCIO xi
I SISTEMAS DE NUMERAÇAO E CÓDIGOS 1
1 SISTEMAS DE NUMERAÇÃO 3
1.1 Sistemas de Numeração Posicionais 5
1.1.1 Representação dos números sem sinal 6
1.2 O Sistema de Numeração Binário 9
1.2.1 Propriedades do sistema de numeração binário 9
1.2.2 Adição binária 13
1.2.3 Subtracção binária 16
1.2.4 Multiplicação e divisão binárias 17
1.3 O Sistema de Numeração Octal 18
1.3.1 Operações aritméticas no sistema octal 19
1.4 O Sistema de Numeração Hexadecimal 22
1.5 Mudança de Sistema de Numeração 25
1.5.1 Conversão da base b1? 10 para a base b2 = 10 25
1.5.2 Conversão da base b1 = 10 para a base b2 ? 10 26
1.5.3 Critério de paragem da dízima 31
1.5.4 Conversão entre as bases b1 = bt2 e b2 33
1.6 Números Binários Com e Sem Sinal 34
1.6.1 Posicionamento da vírgula 36
1.7 Notação de Complemento Para 2 37
1.7.1 Complemento para 2 de um número 37
1.7.2 Números inteiros em complemento para 2 41
1.7.3 Adição em complemento para 2 43
1.7.4 “Overfow” na adição em complemento para 2 45
1.7.5 Subtracção em complemento para 2 47
1.7.6 “Overfow” na subtracção em complemento para 2 49
1.8 Exercícios 50
Referências Bibliográficas 56
2 CÓDIGOS 57
2.1 Modelo de Comunicação Digital 60
2.2 Redundância 64
2.3 Códigos Binários 64
2.3.1 Interesse dos códigos binários 64
2.3.2 Código binário natural - CBN 65
2.3.3 Código binário reflectido ou código de Gray - CBR 66
2.3.4 Conversões entre palavras do CBN e do CBR 69
2.4 Códigos Decimais-Binários 71
2.4.1 Condições de formação dos códigos decimais-binários 71
2.4.2 O código BCD ou código 8 4 2 1 73
2.4.3 Códigos decimais-binários autocomplementares 76
2.4.4 Códigos decimais-binários redundantes 77
2.5 Códigos Alfanuméricos 77
2.6 Códigos Detectores e Correctores de Erros 79
2.6.1 Propriedades gerais dos códigos detectores e correctores de erros 80
2.6.2 Códigos de paridade 80
2.6.3 Códigos m-em-n 82
2.6.4 Códigos correctores de erros (de Hamming) 83
2.7 Exercícios 87
Referências Bibliográficas 92
II • FUNDAMENTOS ALGÉBRICOS 93
3 ÁLGEBRAS DE BOOLE 95
3.1 Axiomática da Álgebra de Boole 97
3.2 Alguns Teoremas 105
3.3 Álgebras Isomorfas da Álgebra de Boole Binária 114
3.4 Álgebras de Boole e Diagramas de Venn 116
3.4.1 Diagramas de Venn para os axiomas 117
3.4.2 Diagramas de Venn para alguns teoremas 120
3.5 Exercícios 121
Referências Bibliográficas 128
4 FUNÇÕES BOOLEANAS 131
4.1 Quantidades e Variáveis Booleanas 133
4.2 Funções Booleanas 135
4.3 Expressões Lógicas 141
4.4 Formas Normais e Formas Canónicas 142
4.4.1 Formas canónicas das funções completamente especificadas 145
4.4.2 Formas canónicas das funções incompletamente especificadas 156
4.4.3 Singularidade das formas canónicas 158
4.4.4 Mintermos e maxtermos das funções booleanas e dos seus complementos 159
4.5 Funções de Zero, Uma e Duas Variáveis Booleanas Simples 162
4.6 Primitivas e Conjuntos Completos 166
4.7 Exercícios 168
Referências Bibliográficas 177
5 REPRESENTAÇÃO DAS FUNÇÕES BOOLEANAS 179
5.1 Representação por Tabelas de Verdade 181
5.2 Representação por Logigrama 187
5.3 Representação por Diagramas Temporais 203
5.4 Quadros de Karnaugh 206
5.5 Representação de Funções Booleanas Simples por Quadros de Karnaugh 219
5.6 Exercícios 224
Referências Bibliográficas 227
6 MINIMIZAÇÃO ALGÉBRICA DAS FUNÇÕES BOOLEANAS 229
6.1 Circuitos Lógicos Mínimos 232
6.2 Critérios de Minimização 237
6.3 Simplificação Algébrica 246
6.4 Implicação e Inclusão 254
6.5 Implicantes e Implicados 258
6.5.1 Termos reduzidos 258
6.5.2 Implicantes e implicados primos 261
6.5.3 Importância dos implicantes e dos implicados primos 267
6.5.4 Implicantes e implicados primos de uma função completamente especificada 268
6.5.5 Implicantes e implicados primos essenciais 274
6.6 Expressões Irredundantes 275
6.7 Expressões Mínimas 287
6.8 Formas Irredundantes e Formas Mínimas de Funções Complementares 289
6.9 Minimização das Funções Incompletamente Especificadas 296
6.10 Minimização das Funções Booleanas Gerais 307
6.11 Exercícios 332
Referências Bibliográficas 3417 MÉTODO DE KARNAUGH 343
7.1 Agrupamentos de Uns e de Zeros 345
7.2 Implicantes e Implicados Primos em Quadros de Karnaugh 367
7.3 Implicantes e Implicados Primos Essenciais 376
7.4 Algoritmo de Karnaugh 390
7.5 Minimização das Funções Booleanas Simples Incompletamente Especificadas 395
7.6 Minimização das Funções Booleanas Gerais 403
7.7 Exercícios 412
Referências Bibliográficas 422
8 MÉTODO DE QUINE-MCCLUSKEY 425
8.1 Geração dos Implicantes e dos Implicados Primos 428
8.2 Tabelas de Implicantes e de Implicados Primos 436
8.3 O Problema da Cobertura 443
8.4 O Método de Petrick 449
8.5 O Algoritmo de Quine-McCluskey 455
8.6 Minimização das Funções Incompletamente Especificadas 456
8.7 Minimização das Funções Booleanas Gerais 459
8.8 Exercícios 470
Referências Bibliográficas 472
ÍNDICE REMISSIVO 473
Carlos Sêrro obteve a licenciatura em Engenharia Electrotécnica, pelo Instituto Superior Técnico (IST), em 1970, os graus de M.Sc. em Engenharia Electrotécnica, em 1975, e de Ph.D. em “Computer Science”, em 1979, ambos pela Universidade de Manchester no Reino Unido, e o grau de Doutor em Engenharia Electrotécnica, pela Universidade Técnica de Lisboa, em 1979.
Actualmente é Professor Associado do IST, tendo aí leccionado disciplinas de Sistemas Digitais, de Microprocessadores, de Arquitectura de Computadores e de Sistemas Tolerantes a Falhas em diversas licenciaturas (de Engenharia Electrotécnica e de Computadores, de Engenharia Informática e de Computadores, de Engenharia Aeroespacial e de Engenharia Física Tecnológica), e no mestrado de Engenharia Electrotécnica e de Computadores.
Foi investigador do Centro de Análise e Processamento de Sinais do INIC (Instituto Nacional de Investigação Científica), de 1980 a 1982, e do INESC (Instituto de Engenharia de Sistemas e Computadores), de 1980 a 1996.
As suas áreas principais de investigação são os Sistemas Distribuídos e de Tempo Real, os Sistemas Digitais e os Sistemas Tolerantes a Falhas.
Em 1992 e 1993 foi investigador convidado da Universidade da Califórnia, em Irvine, onde trabalhou em Sistemas de Tempo Real e Tolerantes a Falhas.
É membro da “The New York Academy of Sciences”, do IEEE (“The Institute of Electrical and Electronics Engineers”), da “IEEE Computer Society”, da “IEEE Reliability Society”, tendo ainda sido membro do “Advisory Board” do “INESC Journal of Research and Development”.