Uma outra forma de explicar o “complemento 2”

Yep! Vira e mexe eu volto aos temas mais fundamentais. Eis-me aqui, de novo, falando de aritmética inteira binária pra você… Vou tentar explicar, de novo, mas de uma outra forma, o que significa usar “sinais” em valores binários inteiros e, para isso, vou recorrer à base numérica decimal. Aquela mesma a qual estamos mais que acostumados.

Números são representações simbólicas de quantidades e, portanto, não têm “sinal”. Você consegue contar 3 coisas (para citar um exemplo de quantidade), mas não consegue contar -3 coisas. O sinal ‘-‘ ai é usado para adicionar um sentido à quantidade. Pode ser que o sentido seja que “faltam” 3 coisas ou que você queira dizer 3, mas no sentido contrário ao convencional. No último caso a representação é relativa a algum ponto tomado como origem… O fato é que você adicionou o sinal ‘-‘ para colocar um sentido extra à quantidade 3. Isso significa que essa qualidade é “artificial”, em relação à quantidade de coisas… Ainda mais: significa que esse símbolo adicional complementa o significado da quantidade (lembre-se dessa palavra!).

No sistema decimal isso é fácil fazer, especialmente quando você se acostuma com o conceito de “menos” (de falta ou “sentido contrário”), mas a coisa é mais difícil quando estamos falando de representações de valores no interior de um computador… Por exemplo, poderíamos ter bits  sinalizados se usássemos 3 níveis de tensão, por exemplo, +5 V, 0 e -5V. A tensão mais alta corresponderia a ‘1’ e a mais baixa a ‘-1’, mas, neste caso, deixaríamos de ter uma base binária para trabalharmos com um sistema ternário porque 3 níveis em cada “algarismo” caracteriza um sistema de base 3… Existe também um outro problema em usar a simbologia do ‘+’ ou ‘-‘: No sistema decimal podemos escrever a quantidade do tamanho que quisermos, se tivermos paciência e tempo, e só colocarmos o sinal ‘-‘ na frente para “inverter o sentido” do valor. Num computador, a quantidade de bits disponíveis para operações aritméticas é limitado. Então, em binário, em termos de circuitos eletrônicos, não dá para usar 3 níveis e também não dá para representar um valor indefinidamente. Um bit não pode ser “negativo” (em oposição a um “positivo”) e não podemos ter tantos bits quanto quisermos. É nesse sentido que sempre digo que não existem valores inteiros negativos em binário.

Acontece que precisamos, em certos casos, representar valores binários como se fossem negativos. Ao invés de usarmos um símbolo especial como ‘-‘ para isso usamos um bit extra… Por exemplo, com um único bit podemos representar apenas dois valores: 0 e 1. Mas, se usarmos 2 bits e fizermos de conta que o bit de mais alta ordem nos diz se o valor é positivo ou negativo, então temos a nossa representação sinalizada de um valor… Por convenção, se esse bit extra for 0, o outro bit representa um valor positivo (0b01 representa o valor +1), mas se esse bit extra for 1, então o outro bit representa um valor negativo (0b11 representa -1). É como se o último bit fosse + ou -. Mas há um problema ai…

E se tivermos uma quantidade maior de bits? O que significa 0b1111 (para citar um exemplo com apenas 4 bits) em termos de valor sinalizado? Se usarmos a definição simples de que o bit de alta ordem significa ‘-‘ e os demais bits nos dão o valor, esse exemplo deveria representar -7. Mas ele, de fato, representa -1. O bit de alta ordem complementa o significado do valor adicionando -2^N ao valor dos bits inferiores (no caso N=3, que corresponde à posição do bit “de sinal”, no valor). Ou seja, 0b1111 é convertido para decimal realizando a operação -2^3+(2^2+2^1+2^0)=-8+7=-1. Note que, no caso de usarmos 2 bits apenas, o complemento é -2. Então 0b11 é calculado como -2+1=-1… Se o bit de alta ordem for zero, o complemento simplesmente não é adicionado ao valor. Repare que, -2 é o valor 2 com a complementação ‘-‘ na frente, em decimal. Acredito que daí aparece o termo “complemento 2”.

Outra explicação interessante é o do porquê do “macete” de inverter os bits e somar 1 se o último bit estiver setado, para obtermos a representação do valor como se fosse negativo. Note que, com dois bits, temos o conjunto de valores binários B={0b00, 0b01, 0b10, 0b11} que pode ser dividido em dois subconjuntos (P=\{0b00,0b01\} e M=\{0b10,0b11\}, onde B=P\cup M (dei o nome dos subconjuntos de P e M para significarem Plus e Minus, o conjunto B é dos Bits). O conjunto B é assimétrico no que se refere aos valores extremos! Do lado positivo temos, em decimal, 0 e +1, e do lado negativo, -1 e -2. Isso quer dizer que o valor -2 não pode ser “espelhado” para obtermos a representação “positiva” +2, usando apenas dois bits. Quer dizer mais ainda: temos 1 quantidade a mais do lado negativo. Assim, para obtermos -1 à partir de 1, já que temos uma quantidade extra do lado negativo, temos que “somar um” à inversão dos bits (“menos” 0b01 é o seu inverso, 0b10,  “mais 1”). No sentido contrário teremos que “tirar” esse um que colocamos, “somando” +1 ao valor negativo (x-(-1)=x+1)… Essa é a origem do “macete”.

Anúncios

Listas circulares, do jeito Knuth (e do Linux)…

Já falei sobre listas encadeadas ao estilo Sedgewick aqui, mas eis uma maneira de implementar listas que fica ainda mais simples… O header abaixo mostra a implementação atual do MyToyOS, devidamente copiado do estilo Knuth e Linus de listas circulares:

#ifndef __LIST_INCLUDED__
#define __LIST_INCLUDED__

// Essa é a estrutura de um nó de uma lista, 
// mas também do nó "batente" ou "cabeça" da
// lista. E, uma vez que mantemos o nó "cabeça",
// a lista é "circular", para facilitar a 
// manipulação (sempre haverá um nó cabeça!).
// A lista "vazia" tem apenas a cabeça, apontando
// para si própria.
//
// Note que a lista é double linked e circular.
//
// COMO USAR:
//
// Suponha que você queira manter uma "lista de
// retângulos", onde um retângulo tenha a estrutura:
//
//   struct rect {
//     int left, top, right, bottom;
//   };
//
// A lista pode ser definida como:
//
//  struct _list_head rect_list_head;
//  INIT_LIST_HEAD(&rect_list_head);
//
// É claro, podemos inicializar a lista diretamente:
//
//  struct _list_head rect_list_head = 
//             EMPTY_LIST(rect_list_head);
//
// A última forma é útil para inicialização de listas
// locais estáticas e globais.
//
// No exemplo dos retângulos, os nós da lista, DEVEM
// ser definidos como:
//
//   struct rect_node {
//     struct _list_head next_rect;  // Isso tem que estar
//                                   // no início!
//     struct rect rc;
//   };
//
// Para adicionar um retângulo no fim da lista:
//
//   _list_add_tail(&rect_list_head, 
//                  (struct _list_head *)&rc_node);
//
// Para adicionar um retângulo no início da lista:
//
//   _list_add_after(&rect_list_head, 
//                   (struct _list_head *)&rc_node);
//
// Para retirar um retângulo da lista:
//
//   _list_unlink((struct _list_head *)&rc_node);
//
// Para percorrer a lista, do início ao fim:
//
//   struct _list_head *p;
//   _list_foreach(p, &rect_list_head)
//   {
//     // faz algo com o ponteiro p aqui.
//   }
//
// Para percorrer a lista do fim para o início:
//
//   struct _list_head *p;
//   _list_foreach_reverse(p, &rc_list_head)
//   {
//     // faz algo com o ponteiro p aqui.
//   }
//
// Infelizmente AINDA não criei a rotina para 
// percorrer toda a lista à partir de um nó 
// específico. Mas, você pode fazer isso guardando
// o nó en questão, percorrendo a lista em uma
// direção até o nó head (_list_foreach*) e 
// depois percorrer do head para o nó guardado. 
// Por exemplo, para frente:
//
//  struct _list_head *p = (struct _list_head *)&rc_node;
//  struct _list_head *q = p->prev;
//  struct _list_head *r = p;
//  _list_foreach(r, q)
//  { ... }
//  _list_forearch(r, &rc_list_head)
//  {
//    if (r == q) break;
//  }
//
// Repare também que, embora tenhamos um "batente", o 
// macro aceita qualquer nó da lista como "alvo". Mas 
// é necessário cuidado porque o "batente" real não tem
// dados.
//

// Estrutura da "cabeça" da lista.
struct _list_head { 
  struct _list_head *next;
  struct _list_head *prev; // Funciona como 'tail' para a 
                           // cabeça da lista.
};

// Os macros citados acima...
#define INIT_LIST_HEAD(name) \
  { (name)->next = (name)->prev = (name); }
#define EMPTY_LIST(name) \
  { .next = .prev = &(name); }

// Essencialmente a mesma coisa que acima, mas lida com o
// ponteiro para a "cabeça" da lista.
static inline void _list_init(struct _list_head *head)
{
  head->next = head->prev = head;
}

// A lista está vazia? Se next aponta para a cabeça, está!
static inline _Bool _list_empty(struct _list_head *head)
{ return head == head->next; }

// Insere o novo item depois do item "prev".
static inline void _list_add_after(struct _list_head *prev, 
                                   struct _list_head *_new)
{
  struct _list_head *next;
  struct _list_head *prev;

  next = head->next;
  prev = head->prev;

  if (_list_empty(head)) // Caso especial!
    head->prev = _new;
  _new->next = next;
  _new->prev = prev;
  head->next = _new;
}

// Addiciona um item no fim da lista.
static inline void _list_add_tail(struct _list_head *head, 
                                  struct _list_head *_new)
{
  _list_add_after(head->prev, _new);
}

// Apaga um nó da lista.
// OBS: Cuidado ao usar free(). o nó pode ser a cabeça!
static inline void _list_unlink(struct _list_head *node)
{
  // Note que se a lista estiver vazia, nada acontece.
  struct _list_head *next;
  struct _list_head *prev;

  next = node->next;
  prev = node->prev;
  prev->next = node->next;
  next->prev = node->prev;
}

// Percorrer uma lista pode ser feito com:
//
// struct _list_head *p = &mylist;
//
// for (p = mylist->next; p != &mylist; p = p->next)
// { ... }
//
// Dai o macro abaixo (tanto p quanto head são ponteiros:
//
// OBS: É bom lembrar que a cada iteração do loop o 
//      ponteiro de controle apontará para o próximo
//      item da lista (ou para o anterior se o sentido
//      for reverso) até que ele retorne para a "cabeça".
//      Assim, usá-lo para deletar itens na lista deve
//      ser feito com cuidado.
#define _list_foreach(p,head) \
  for (p=head->next; p != head; p=p->next)

#define _list_foreach_reverse(p,head) \
  for (p=head->prev; p != head; p=p->prev)

#endif

Por que as funções estão definidas no header e não num módulo C separado? Ora, as rotinas são tão simples que posso fazê-las inline. Rotinas em módulos separados, necessariamente, não são “inlineáveis”. Os macros _list_foreach e _list_foreach_reverse não podem ser funções porque são atalhos para a construção do loop que percorrerá toda a lista… Aliás, um conselho: Cuidado com o código abaixo

struct _list_head *p;
_list_foreach(p, &list_of_rects)
{
  _list_unlink(p);
}

Dependendo do que você fizer com os ponteiros do nó apontado por p, o loop não fará o que você quer (mas, do jeito que está, deve funcionar, porque o componente next de p continua apontando para o próximo item, embora o nó não faça mais parte da lista… No fim das contas apenas o a cabeça da lista sobrará (não será “desligada” da lista)…

Note também que nenhuma das rotinas é responsável por alocar ou dealocar a estrutura de um nó. Tudo o que elas fazem são as ligações corretas para manter a lista. É sua responsabilidade alocar ou liberar nós, incluindo a “cabeça”, é sempre deixada na lista no caso do desligamento de todos os nós…

A característica circular da lista torna fácil algumas operações (principalmente _list_foreach e sua contraparte).

Um macete usando NULL pointers…

Você provavelmente aprendeu que ponteiros NULL são perigosos. Eles causam “segmentation faults” ou “General Protection Faults” e devem ser evitados. Eis o detalhe: Isso só acontece se o ponteiro for derreferenciado!

O macete abaixo mostra um jeito de obter o offset de um membro de uma estrutura sem usar o macro offsetof, definido em stddef.h, pelo menos desde a versão ISO 9989:1999 da linguagem C:

#define offsetof(T,member) \
  ( (unsigned int) &( (T *)0 )->member )

Notou o uso do NULL pointer? Pois é! Não estamos derreferenciando o bicho, só calculando o endereço efetivo do membro da estrutura… Se você fizer:

Yep! MS-DOS!

O membro z da estrutura S está no offset 8 (Faz sentido: x está no início da estrutura, portanto no offset 0. Como cada float ocupa 4 bytes, y estará no offset 4)… Fiz isso no MS-DOS, usando o Borland C++ 3.1 para mostrar para vocês que isso sempre foi válido, desde os primórdios.

O que essa macro faz, na verdade? Ora, o endereço efetivo é calculado com base no endereço do objeto, cujo endereço está no ponteiro… Ao usar o endereço 0 (zero), tudo o que temos é o offset do membro da estrutura!

 

De novo: Por que programar diretamente em assembly geralmente não é uma boa ideia…

Sim… de novo estou advogando contra mim mesmo. Eu uso assembly sempre que posso e quando isso não implica em códigos dependentes de arquitetura. Mas, para o novato, que está aprendendo assembly agora, programar nessa linguagem quase sempre é sinônimo de desastre. Eis o porquê:

Convenções de chamadas existem por um bom motivo

Quando estamos aprendendo é sugerido que manter o contexto da função chamadora é importante. Por contexto quero dizer os registradores que estavam sendo usados pela função que chamou a sua… Isso parece razoável, mas não é assim que compiladores de nível mais alto fazem… Um exemplo simples é a implementação padrão da função strcpy, em C:

char *strcpy(char *d, char *s)
{
  char *p = d;
  while (*p++ = *s++);
  return d;
}

Note que a função não verifica o conteúdo dos ponteiros (eles PODEM ser NULL e causarem segmentation fault) e o código gerado também não se preocupa em preservar o conteúdo dos registradores. No x86-64 isso é mais evidente:

strcpy:
  mov   rax,rdi
  mov   rdx,rdi
.loop:
  add   rsi,1
  movzx ecx,byte [rsi-1]
  add   rdx,1
  test  cl,cl
  mov   [rdx-1],cl
  jne   .loop
  ret

Aqui a função alterou, sem escrúpulos, o conteúdo de RAX, RCX, RDX, RSI e RDI. Isso acontece porque, no modo x86-64, o GCC só se preocupa em manter os registradores RBX, RBP, RSP e de R12 até R15. Já no modo i386, os mantidos devem ser EBX, EBP e ESP apenas. Todos os demais podem ser modificados.

Há uma vantagem escondida nessa aproximação: Se você sabe que o compilador C vai manter, à todo custo, esses registradores inalterados entre chamadas, tanto ele quanto você pode usá-los como “variáveis temporárias” (desde que preserve os seus conteúdos vindos da função chamadora!)… Quanto aos demais, se sua função chama outra e você precisa preservar o conteúdo de EAX, por exemplo, então é obrigá-lo a salvá-lo você mesmo (na pilha, por exemplo!).

Ahhh, sim… nas convenções de chamada usadas por C, pelo menos no modo i386, EAX é usado para retornar um valor e o par EDX:EAX, se esse valor for maior que 32 bits. Se sua função não retorna valores, pode mexer com EAX e EDX à vontade e deixá-los “bagunçados”. Eles não precisam ser preservados, neste caso.

Usando a pilha para manter variáveis locais entre chamadas

O GCC tenta manter todas as variáveis locais em registradores, mas, eventualmente, precisa guardá-los para uso futuro (depois do retorno da chamada de alguma função). Geralmente ele faz algo assim:

f:
  sub esp,4
  ...
  mov [esp],eax
  call some_function
  mov eax,[esp]
  ...
  add esp,4
  ret

ESP, quando sua função é chamada, aponta para o endereço de retorno da função chamadora. Como a pilha cresce para baixo, nossa função resolveu alocar 4 bytes (no modo i386 a pilha deve estar sempre alinhada por DWORD) adicionando 4 ao ESP. Antes de retornar (RET) o conteúdo de ESP deve voltar ao valor original que estava (lembra-se que ele é um dos que têm que ser preservados?).

É claro que você poderia guardar o conteúdo dessa variável “local” dentro de algum endereço no segmento de dados ou, até mesmo, no segmento de código, mas ai ela deixaria de ser “local”, não é?

Por que não usar PUSH e POP?

Depois que você aprende o conceito de pilha, parece muito mais simples usar as instruções PUSH e POP do que usar o esquema que mostrei acima. O mesmo fragmento de código em poderia fazer, retirando aqueles SUB e ADD e codificando como:

f:
  ...
  push eax
  call some_function
  pop  eax
  ...
  ret

A função fica menor? Fica! Parece mais simples? Parece! Mas ela tem um problema… As instruções PUSH e POP são ligeiramente mais lentas que MOV porque cada PUSH e cada POP, além de lerem/gravarem na pilha os valores dos registradores têm que adicionar 4 ou retirar 4 de ESP. O código acima, sem usar PUSH e POP, é equivalente a:

f:
  ...
  sub  esp,4
  mov  [esp],eax
  call some_function
  mov  eax,[esp]
  add  esp,4
  ...
  ret

Essa sequência de SUB/MOV e MOV/ADD acontece em cada um dos PUSHes e POPs, respectivamente. O que o compilador C faz é, já que ele sabe quantos bytes vai precisar usar da pilha, ele os aloca de antemão e usa apenas MOVs para guardar os valores!

Ainda não se convenceu que usar a pilha é melhor?

Se você ainda acha que guardar estados no segmento de dados ou código é uma boa ideia, existe mais um motivo para não fazê-lo. Um acesso à memória depende do cálculo do “endereço efetivo”, que pode ser dado por uma expressão. Por exemplo:

mov eax,[esp]
mov eax,[esp+4]
mov eax,[ebx+esi+8]
mov eax,[ebx+esi*8+8]
mov eax,[0x7ffffff0]

Nos primeiros 4 casos o “endereço” de onde um DWORD será lido é dado pelas expressões envolvendo registradores. No primeiro e no segundo caso não há gasto de ciclos de clock adicionais e o acesso é muito parecido com quando você acessa um registrador qualquer, em termos de performance. Os outros casos envolvem cálculos mais complicados e, no caso do último, um deslocamento maior que 2047. Qualquer deslocamento maior que 2047 causa o consumo de 1 ciclo de clock extra (além do cálculo)… Por exemplo, se usássemos [esp+4096] teríamos o consumo de 1 ciclo a mais na instrução… Se usássemos [ebx+esi+4096], teríamos o consumo de 1 ciclo a mais, graças ao cálculo de EBX+ESI e ainda mais 1 porque o offset é maior que 2047.

Ao usar a pilha e manter as variáveis locais próximas de onde ESP aponta, digamos, menos de 2 KiB perto, não há consumo de ciclo extra. É como se o processador estivesse lendo/gravando num registrador.

É claro que existem outras penalidades: Cache Misses, TLB misses e Page Faults, por exemplo… Mas, isso poderia ocorrer nos outros casos também…

 

Adote uma convenção de chamadas ao estilo de C…

Deixar para as funções chamadoras manterem seus próprios contextos e evitar fazer testes desnecessários em funções de baixo nível são sempre boas ideias… Suas funções de baixo nível devem fazer apenas o que elas precisam fazer. Verificar se ponteiros são nulos, se valores estão dentro da faixa desejada etc, são tarefas para funções de níveis mais altos, mais “inteligentes”. Essa estratégia leva a códigos menores e mais rápidos, sempre!

Para quem está criando o próprio “toy OS”…

Conheço algumas pessoas que estão experimentando a criação do próprio sistema operacional de brinquedo. Já vi alguns projetos interessantes, a maioria voltada para o modo protegido i386 (32 bits). Aqui vai uma dica para quem está usando o GCC para gerar código freestanding

A convenção de chamada padrão da linguagem C é chamada de cdecl, onde os argumentos de uma função são sempre empilhadas, na ordem do último argumento para o primeiro; e a função chamadora é a responsável por “limpar” a pilha dos argumentos. Acontece que ficar usando pilha para passagem de argumentos é um jeito bem lento de se fazer as coisas. Será que não tem alguma forma de usar registradores? Felizmente, tem! Antes, vamos dar uma olhada nas funções abaixo:

__attribute__((noinline))
int f(int a, int b, int c) 
{ return a * b + c; }

__attribute__((noinline))
int g(int a, int b, int c, int d, int e) 
{ return ( f(a, b, c) - d) / e; }

Se você compilar com as opções tradicionais, obterá algo assim:

; Código equivalente, para NASM, compilado com
; o GCC via:
;
; $ cc -O2 -S -masm=intel -ffreestanding -m32 test.c
;
  bits 32
  section .text

; A estrutura da pilha após a chamada de f é:

;   ESP+0:  Endereço de retorno colocado pelo CALL.
;   ESP+4:  Valor de 'a';
;   ESP+8:  Valor de 'b':
;   ESP+12: Valor de 'c';
;
  global f
f:
  mov  eax,[esp+8]
  imul eax,[esp+4]
  add  eax,[esp+12]
  ret

; A estrutura da pilha após a chamada de g é:
;
; ESP+0:  Endereço de retorno colocado pelo CALL;
; ESP+4:  Valor de 'a';
; ESP+8:  Valor de 'b';
; ESP+12: Valor de 'c';
; ESP+16: Valor de 'd';
; ESP+20: Valor de 'e';
;
  global g
g:
  ; Aqui tem um "macete"... Como cada PUSH
  ; decrementará ESP em 4, para acessar a próxima referência
  ; à pilha, temos que usar o mesmo offset "ESP+12".
  push	dword [esp+12]  ; Empilha 'c'.
  push	dword [esp+12]  ; Empilha 'b'.
  push	dword [esp+12]  ; Empilha 'a'.
  call	f
  add   esp, 12         ; Livra-se dos 12 bytes empilhados.

  sub   eax, [esp+16]
  cdq
  idiv  dword [esp+20]
  ret

Cada referência à memória consome, pelo menos, 1 ciclo de clock adicional para a instrução e, ainda, aumenta um bocado o tamanho do código. Eis o micro código das duas funções, obtida com o objdump:

f:
   0: 8b 44 24 08      mov  eax,[esp+0x8]
   4: 0f af 44 24 04   imul eax,[esp+0x4]
   9: 03 44 24 0c      add  eax,[esp+0xc]
   d: c3               ret

g:
  10: ff 74 24 0c      push DWORD PTR [esp+0xc]
  14: ff 74 24 0c      push DWORD PTR [esp+0xc]
  18: ff 74 24 0c      push DWORD PTR [esp+0xc]
  1c: e8 fc ff ff ff   call f
  21: 83 c4 0c         add  esp,0xc
  24: 2b 44 24 10      sub  eax,[esp+0x10]
  28: 99               cdq  
  29: f7 7c 24 14      idiv DWORD PTR [esp+0x14]
  2d: c3               ret

Agora, vejamos como fica o mesmo código, compilado com o GCC, mas incluindo a opção -mregparm=3:

f:
   0:	0f af d0         imul edx,eax
   3:	8d 04 0a         lea  eax,[edx+ecx*1]
   6:	c3               ret  

g:
  10:	e8 fc ff ff ff   call f
  15:	2b 44 24 04      sub  eax,[esp+0x4]
  19:	99               cdq  
  1a:	f7 7c 24 08      idiv DWORD PTR [esp+0x8]
  1e:	c3               ret    

O que aconteceu aqui é que o atributo regparm faz com que os 3 primeiros argumentos, se forem inteiros, são passados sempre pelos registradores EAX, EDX e ECX, nessa ordem. Os demais argumentos são empilhados, de acordo com a convenção de chamada cdecl. Na função g, apenas os argumentos d e e estarão empilhados e, como e é empilhado primeiro, ele estará em [ESP+8], deixando d em [ESP+4].

Note que, como EAX, EDX e ECX já contém os argumentos que serão passados para f, na função g, nenhum empilhamento é necessário, retirando os 3 PUSHs que existiam antes, bem como a limpeza da pilha. Do lado da função f, já que os argumentos estão todos em registradores, podemos usar LEA para fazer a adição final…

Bem… o resultado final é que as duas funções ficarão bem mais rápidas e com a metade do tamanho das originais!

Simplificação lógica usando mapas de Karnaugh

Uma querida amiga, no Facebook, mostrou-se interessada em aprender um bocado a respeito de eletrônica digital e topou com os mapas de Karnaugh, como recurso para tornar mais simples o esforço de realizar “simplificações” de expressões lógicas. Neste texto vou mostrar para vocês dois estilos diferentes de mapas, como montá-los e usá-los. Mas, antes, é importante entender como fazer esse tipo de simplificação manualmente.

Como na álgebra tradicional, a Booleana também é baseada em certas operações elementares. Para facilitar a compreensão, usarei o símbolo de adição (+) para representar a operação OR e multiplicações para representar AND. Assim, a expressão S=A+BC será a mesma coisa que S=A\quad OR\quad(B\quad AND\quad C).

A primeira propriedade é a de identidade. Ou seja, A+0=A e A\cdot1=A. Outra propriedade interessante é a que acontece quando invertemos o valor fixado para as operações OR e AND: A+1=1 e A\cdot0=0. Com essas quatro proriedade fica fácil de ver que: A(B+1)=A\cdot1=A, por exemplo… Também temos a propriedade distributiva, A(B+1)=AB+A, assim como na aritmética tradicional. O que não é muito evidente é que AND também pode ser distribuído: A+(BC)=(A+B)(A+C), e vice-versa, se colocarmos A “em evidência”.

Vejamos como isso funciona com uma expressão do tipo S=A+\overline{A}B: Pela propriedade distributiva podemos reescrever a expressão como S=(A+\overline{A})(A+B). Se A+\overline{A}=1 e, ao mesmo tempo, X\cdot1=X. O que nos dá: S=A+\overline{A}B=(A+\overline{A})(A+B)=1\cdot(A+B)=A+B, ou seja, eliminamos o \overline{A} da expressão.

Acontece que esse tipo de simplificação pode ser bem complicada para fazer “de cabeça”. E podemos nos confundir se podemos (ou se devemos) realizar uma distribuição usando AND ou OR. Para isso existem os mapas de Karnaugh.

Simplificação com mapa de Karnaugh

Como funciona esse mapa? Trata-se de um retângulo onde, nas colunas, temos as representações de A e seu inverso (1 e 0, ou vice-versa) e nas linhas, B e seu inverso. Uma expressão a ser simplificada deve ser interpretada como sendo constituída de “somas” de produtos… No caso da expressão S=A+\overline{A}B, o A isolado deve ser transformado para A=A(B+\overline{B})=AB+A\overline{B} e assim, obtemos a equação final S=AB+A\overline{B}+\overline{A}B. Daí, em cada termo das “adições” colocamos, no mapa, o valor 1.

Agora precisamos “agrupar” esses uns de acordo com as seguintes regras:

  1. Apenas “uns” adjacentes podem formar grupos (“uns” diagonais não!);
  2. Apenas grupos de 2^n “uns” podem ser formados. Ou seja, cada grupo pode ser formado por 1, 2, 4, 8, 16… “uns”;
  3. Apenas grupos “linhas”, “quadrados” ou “retângulos” podem ser formados (veremos isso com mapas com 3 ou mais variáveis);
  4. Devemos sempre começar pelos maiores grupos possíveis;
  5. Podemos compartilhar “uns” de grupos que já tenham sido formados, desde que pelo menos 1 deles não faça parte de outros grupos;
  6. Se não há mais “uns” fora de grupos já formados, novos grupos não devem ser formados;
  7. A menor quantidade possível de grupos deve ser formada.

Com essas regras obteremos a equação final com a menor quantidade de termos (regra 7) com menores termos (especialmente a regra 4).

No exemplo acima tivemos que formar 2 grupos com 2 “uns” (o verde e o avermelhado) porquê não pudemos criar nenhum grupo com 4 “uns”.

Para cada grupo verificamos quais variáveis não possuem complementos e as escrevemos como um produto… No caso, o grupo vermelho é composto de A, mas têm B e \overline{B}, portanto ambos são eliminados, ficando apenas A… A mesma coisa se dá com o grupo verde, ficando apenas B.

Note que, no mapa com duas variáveis, se tivéssemos uma expressão do tipo S=AB+A\overline{B}+\overline{A}B+\overline{A}\overline{B}, todos as 4 posições teriam “uns” e o resultado final serial S=1… Isso nos dá uma regra interessante:

  • Grupos com 2^n “uns” eliminam n variáveis.

Um grupo grande com 4 “uns” eliminará, necessariamente, 2 variáveis da expressão. No caso anterior, como a expressão só tem duas variáveis, o resultado só pode ser 1. Isso ficará claro, adiante, com mapas maiores.

Mapas de 3 ou 4 variáveis

A diferença de um mapa com mais de duas variáveis é que ele pode se “fechar” lateralmente. No mapa abaixo, para colocarmos mais uma variável, decidi particionar as colunas A e \overline{A} em duas, mas note que para que a porção \overline{C} fique completa, os lados direito e esquerdo do mapa precisam “se tocar”. Ou seja, o mapa deixou de ser plano para ser cilíndrico.

Exemplo com 3 variáveis

No exemplo acima, temos que começar com um grupo de 4 “uns” (o avermelhado). Note que os “uns” continuam adjacentes, mas  não formam uma linha. Formam um “quadrado”… Com isso fica “sobrando” um “1” no mapa que, infelizmente, não pode formar nenhum outro grupo de 4, restando apenas uma possibilidade: um grupo de 2 “uns”, usando um já usado no grupo anterior.

O grupo de 4 “uns” elimina duas das três variáveis. Se prestarmos atenção o grupo usa A, \overline{A}, B e \overline{B}, mas usa apenas \overline{C}… O grupo de dois “uns” elimina uma única variável, permanecendo apenas A\overline{B}.

Um mapa de 4 variáveis faz e mesma coisa que o mapa de 3, mas ele dividirá as linhas de B e \overline{B}, da mesma forma que fiz com C e \overline{C}, mas do lado direito no mapa… Assim, ele se fechará nos dois sentidos, formando uma “toroide” (um cilindro fechado dos dois lados… ou um “pneu”):

Mapa com 4 variáveis

Mapas com mais de 4 variáveis e a codificação de Gray

Mapas com mais de 4 variáveis podem ser montados de acordo com o esquema anterior, porém em 3D. Eu acho particularmente difícil conceber tais mapas tridimensionais e, portanto, para continuar usando Karnaugh, um outro esquema, mais tradicional, é necessário. O mapa pode ser montado de forma bidimensional onde cada linha ou coluna varie, entre uma e outra, em apenas 1 bit, como mostrado abaixo:

Esse tipo de mapa tem que usar uma codificação para cada linha/coluna chamada de código de Gray, já que, assim como mapa de 4 variáveis, ele se “fecha” nos dois sentidos… Isso fica meio chato de montar, mas o código de Gray pode ser obtido para n bits assim:

Começamos pelos dois primeiros valores: 0 e 1. Os dois próximos são os mesmos dois primeiros, porém revertidos, com o próximo bit setado. Ou seja, se temos 0 e 1, obtemos 11 e 10 e teremos a sequência {00,01,11,10}. A próxima sequência é essa mesma, revertida, com o próximo bit setado, ou seja, {110,111,101,100}, o que nos dá a sequência completa {000,001,011,010,110,111,101,100}, para 3 bits… Esse mesmo algoritmo pode ser usado para n bits…

No que concerne o uso do mapa, você coloca os “uns” em cada uma das posições dos produtos, onde 0 significa a variável “negada”, e segue as mesmas regras anteriores (grupos grandes, poucos grupos e grupos de 2^n “uns”). A chatice é determinar quais das variáveis não sofreram alterações nos grupos… Suponha que tenhamos um grupo de 8 “uns” e verificamos que apenas A e B não sofreram variações (A=0 e B=1, no grupo todo, por exemplo)… Assim, para esse grupo de 8 “uns” (e, por causa disso 3 variáveis serão eliminadas, necessariamente, já que 2^3=8), obteremos \overline{A}B.

Desse jeito podemos montar mapas de qualquer tamanho. Mas, atenção que apenas 4 bits nos darão uma linha com 16 possibilidades diferentes. Um mapa com 8 bits, agrupados de 4 em 4, nos dará um mapa com 256 posições!

Usando mapas de Karnaugh com comparações, num if…then…else

Claro que usei variáveis booleanas A, B, C, … levando em conta que elas podem assumir apenas dois valores: true ou false. A mesma coisa pode ser feita com uma comparação como (x < 0), só temos que tomar cuidado com os complementos… Por exemplo, o contrário de (x < 0) é (x >= 0)… Assim, um if do tipo:

if ((x < 0) || ((x >= 0) && (a == b))) { ... }

Pode ser decrito como tendo A=(x < 0), \overline{A}=(x >= 0) e B=(a==b). O que nos daria a expressão A+\overline{A}B. Como vimos, isso pode ser simplificado para A+B e, portanto, o if acima ficaria:

if ((x < 0) || (a == b)) { ... }

O compilador pode fazer essa simplificação para nós, mas nem sempre ele consegue.

Dica: Qualidade de fones de ouvidos…

Não se aplica apenas a fones de ouvidos, mas à saída de amplificadores (como o da sua placa de som) e outros equipamentos de áudio.

Anteriormente, escrevi um artigo que deixou alguns meio “brabos” comigo (por causa do título) onde digo que “DJ’s não sabem de nada“. Falei sobre o uso de equalizadores, sobre como a qualidade de CDs é muito superior aos discos de Vynil e sobre a “loudness wars“. Aqui vai uma dica para você que quer alguma maneira de saber se a qualidade do fone de ouvido (ou da placa-de-som, ou das caixas-de-som) é boa ou não… Trata-se de observar a “resposta de frequência”…

O que isso significa? Todo som audível pode ser desmembrados em “bandas” de frequências, começando à partir dos 20 Hz até os 20 kHz (a faixa média, audível por nós, humanos). Podemos traçar um gráfico mostrando em quais pontos dessa grande faixa conseguimos ouvir, com a intensidade (amplitude ou altura) original e em que pontos essa intensidade é diminuída (atenuada) ou aumentada (amplificada). Eis um exemplo de um gráfico de “resposta de frequências” de um fone de ouvido genérico:

Neste gráfico temos duas escalas: No eixo vertical temos uma escala linear. Cada linha é exatamente 5 dB maior ou menor que a linha anterior. No eixo horizontal temos uma escala “exponencial”. Note o padrão ente a linha 100 e a linha 1000. Os traços vão ficando mais e mais perto uns dos outros, numa espécie de compressão, para que possamos traçar o gráfico em uma escala muito maior sem gastar muito espaço… Ainda, a partir da linha 100, a próxima, à direita, representa 200 e, portanto, de uma linha para outra houve uma variação de 100 unidades… Mas, a partir da linha 1000, às linhas à direita variam de 1000 em 1000 (ou seja, numa escala 10 vezes maior que a anterior). A esse tipo de escalonamento bidimensional damos o nome de “escala semi-logarítmica” (porque uma delas não é “logarítmica”!).

De acordo com o texto em que sacaneio os DJ’s, sabemos que “decibel” é uma unidade de medida relativa, uma razão… 0 dB equivale a uma relação de 1:1, 3 dB equivale a, aproximadamente, uma razão de 2:1 e, -3 dB a uma relação de 1:2… É padrão considerar qualquer coisa abaixo de -3 dB como “inaceitável” em termos de “perda” ou “atenuação”. Então, o que esse gráfico de “resposta” nos diz?

Bem… Mais ou menos abaixo de 100 Hz e acima de 15 kHz o sinal será atenuado para menos de -3 dB. Ou seja, o som vai ficar “baixinho” nessas frequências… O gráfico diz mais ainda: Mais ou menos lá pros 150 Hz até os 2 kHz a amplitude do sinal será mais ou menos a original (não há perdas e nem ganhos significativos, ou seja, fica em torno dos 0 dB). E, também, para frequências entre 2 kHz até pouco depois dos 10 kHz há um “ganho” de volume (amplitude)… ou seja, essas frequências vão parecer mais altas no seu ouvido.

Ora, de forma ideal, o que você quer é um fone que tenha uma resposta em torno dos 0 dB para toda a faixa audível. Então, quanto mais “retinha” for a curva, perto dos 0 dB, melhor…. Poucos fones oferecem isso. Um exemplo é o Koss Porta Pro:

Koss Porta Pro e sua resposta de frequência

Note a pouquíssima amplificação ou atenuação em toda a banda audível e o repentino corte na frequência de 20 kHz! Isso faz da Koss, além de ser a empresa que inventou os fones de ouvido, um dos melhores fabricantes na área.