[blog] “Silicon Cowboys”, a história da Compaq

Nesta semana assisti ao documentário (disponível no Netflix) “Silicon Cowboys” que conta a história da fundação da Compaq. Os fundadores parecem ser três grandes figuras.

A Compaq parece ser uma história de sucesso que juntou algum brilhantismo técnico com um gerenciamento todo brilhante. “Não era sobre criarmos um computador ou ficarmos ricos. Era sobre criarmos uma empresa boa para se trabalhar” disse Rod, um dos cabeças da companhia.

Oriundos da Texas Instruments – Rod Canion, Bill Murto e Jim Harris – pediram demissão para fundarem sua própria empresa. Detalhe: eles não sabiam o que seria. Após cogitarem até um restaurante de comida mexicana, Rod Canion vislumbrou a ideia de um computador pessoal compatível com o IBM PC, mas que fosse portátil. Ao que parece ele percebeu, e o mercado definiu a portabilidade como uma característica necessária para a computação pessoal. Não preciso dizer aonde chegamos.

O ‘pulo do gato’ da companhia se deu quando a IBM resolveu entrar no segmentado e incipiente mercado de computadores pessoais. Para isso lançou mão de um projeto feito todo com componentes OEM, com um microprocessador 8088 da Intel e o sistema operacional vindo da Microsoft (PC-DOS). Se a os componentes eram todos OEM, o clone do hardware era fácil. Mas eles precisavam de um software básico (sistema operacional) idêntico para a compatibilidade completa. Para isso fizeram uma engenharia reversa, num processo muito parecido com o qual a brasileira UNITRON clonou um Macintosh Fat Mac, também em meados dos anos 80, durante a reserva de mercado no Brasil. A partir daí, o feito atingido na época foi como desbancar o Google.

A Compaq é responsável pelo fato de não falarmos MAC ou IBM hoje, e sim MAC ou PC. Quantas vezes uma boa ideia tem as condições necessárias para mudar a história assim?

Escalonamento cooperativo em software embarcado (2/2)

sch

Escalonador cooperativo para soft real-time

Os sistemas com requisitos de tempo-real são classificados em soft, firm e hard, apesar de estes critérios não serem bem estabelecidos. Em sistemas ‘hard’, os requisitos de tempo precisam ser estritamente atendidos sob pena da falha total. No soft/firm, o não cumprimento das deadlines é tolerado em alguma medida, ocasionando degradação da qualidade do sistema sem levar à falha total.

Na última publicação descrevi algumas arquiteturas de escalonadores (schedulers) que na sua melhor forma executava toda tarefa agendada no mesmo intervalo de tempo, e também poderia reagendar ou descartar a tarefa.

Vou estender esta última arquitetura um pouco mais, agora ao invés de informar ao escalonador somente o endereço da função, também vou informar uma frequência de execução que deve ser cumprida.

Como agora precisamos contar os ticks do relógio para atender aos requisitos temporais, precisaremos de uma referência de tempo. Para isso podemos usar um temporizador que gere uma interrupção a cada Q segundos. O serviço que atende esta interrupção informa ao escalonador que houve um tick de relógio. O menor intervalo de tempo entre um tick e outro é por vezes chamado de quantum e é uma escolha importante de projeto.

O escalonador será composto basicamente por um buffer circular que aponta para os processos, e um disparador que fica responsável por arbitrar qual processo está pronto para ser disparado.

A figura abaixo ilustra a arquitetura proposta:

sch

Cada estrutura de processo é declarada com um período (em ticks do sistema). Quando o processo é adicionado ao buffer circular, um inteiro é inicializado, em tempo de execução, com o período informado na chamada de sistema. A cada interrupção gerada pelo tick do relógio, este número é decrementado e pode ser visto como uma deadline. A cada ciclo de máquina, o árbitro varre pelo processo com o menor prazo de execução, para dispará-lo em seguida (colocado na posição inicial do buffer). A função evocada retorna REPEAT ou ONESHOT, caso queira ou não ser reagendada, ou FAIL como código de erro. O código abaixo mostra o cabeçalho do programa (desisti de escrever os códigos no texto da publicação, o editor do WordPress é muito ruim!):

header

Na estrutura process a variável deadline é com sinal para poder registrar o atraso, quando ocorrer. Além disso, se a tarefa for reagendada, o contador do novo processo apontado no buffer vai iniciar subtraindo este atraso para ajustar o atraso total do sistema.

buffer

Quando o disparador varre o buffer para selecionar o processo com a menor deadline, ele também organiza a fila em ordem decrescente de deadlines. Se o processo anterior retornou FAIL, o escalonador analisa se o deadline do próximo processo a ser executado é menor que o período do atual. Caso verdadeiro ele dispara o processo mais uma vez. Por isso foi necessário organizar o buffer sempre em ordem crescente de atraso, para garantir que o processo atual seja comparado com o mais crítico da fila.

Quando a menor deadline da fila for maior que 0,  será necessário esperar até o contador chegar a zero, e uma boa prática é utilizar este tempo para colocar o processador em um modo de baixo consumo (verificando no manual do processador se neste modo ele ainda é sensível à interrupção que gera o tick!).

escalonador

escalonador2

A configuração do temporizador que realiza a interrupção para gerar o tick do relógio depende da arquitetura. O código abaixo escrevi para um ATMega328p rodando a 16MHz. Ele está gerando o tick a cada 4ms.

isr

Abaixo as rotinas para habilitar e sair do modo IDLE:

powersch-2.jpg

A função schInit() inicializa o scheduler, zerando os índices do buffer e inicializando o temporizador para geração do tick do sistema.

O programa principal de um sistema utilizando este scheduler teria a seguinte cara:

mainsch

Aviso: o código acima tem propósitos didáticos e não é um artefato validado. Não há nenhuma garantia de funcionamento livre de erros, e o autor não se responsabiliza pelo uso.

O texto desta postagem é original. Os seguintes livros foram consultados para sua elaboração:
[1] Programação de sistemas embarcados, Rodrigo Almeida e outros.
[2] Real-Time Systems Development, Rob Williams 
[3] Patterns for Time-Triggered Embedded Systems,  Michael J. Pont

Escalonamento cooperativo de tarefas em software embarcado (1/2)

sch

Arquiteturas para escalonamento cooperativo de tarefas

Na publicação anterior escrevi sobre o uso do chamado super-loop e suas limitações quando falamos em atender requisitos de tempo em uma planta. Além disso, também mostrei que podemos utilizar interrupções disparadas por temporizadores para garantir que tarefas sejam executados em intervalos definidos. Neste caso, para cada tarefa periódica precisamos de um temporizador. Em sistemas um pouco mais complexos, ambas as arquiteturas são muito suscetíveis a erros e de difícil manutenção e reuso/extensão.

Um escalonador é um bloco de código que permite ao programador inserir tarefas que serão chamadas em intervalos regulares sem que seja necessário um serviço de interrupção (ISR) dedicado a cada uma delas (podemos pensá-lo como um ISR compartilhado). Quando comparado ao super-loop, o escalonador permite que o programador não se preocupe em manejar os delays entre uma tarefa e outra para garantir a periodicidade desejada. Quando comparado a utilização com temporizadores, o uso de um escalonador é menos custoso pois não necessitamos de um temporizador para cada tarefa periódica.

Existem dois tipos gerais de escalonadores os cooperativos e os preemptivos. Os escalonadores cooperativos simplesmente executam uma tarefa após a outra, com ou sem deadline no tempo. Os escalonadores preemptivos indexam prioridades a cada uma das tarefas, e caso um evento que chame uma tarefa de maior prioridade ocorra durante a execução de uma menos prioritária, esta é pausada e retomada após a conclusão daquela. Por isso estes escalanadores são ditos multitarefas. (A tarefa atual não precisa terminar para que outra seja executada. Guardadas as devidas proporções e aplicabilidade, o MS Windows é multitarefas pois o usuário do PC pode alternar entre uma tarefa e outra, e o sistema operacional chaveia o contexto do microprocessador – alterna entre um processo e outro – dando a impressão de que todas as tarefas estão sendo executadas ao mesmo tempo. O antigo MS-DOS é monotarefa. )

Vou explorar aqui algumas implementações para escalonadores cooperativos.

Escalonamento cooperativo utilizando máquinas de estados

Independente da arquitetura do escalonador, se ele for cooperativo suas operações podem ser descritas da seguinte forma:

  • as tarefas são agendadas para ocorrer em um determinado período de tempo

  • quando o agendamento ocorre, a tarefa é armazenada em uma lista de espera

  • quando a tarefa atual termina, a próxima é executada (se houver)

  • após a completude das tarefas, o controle do sistema volta ao escalonador

Se a solução a ser implementada não tiver padrões rígidos de resposta temporal, a utilização de uma máquina de estados garante a facilidade no reuso e manutenção do código.

Supomos um programa que utilize um display, um teclado e uma porta serial. A porta serial responde aos comandos vindos pelo teclado ou pela serial. O display é atualizado periodicamente. A máquina de estados pode ser modelada da seguinte forma (figura retirada de [1]):

fsm001

Uma implementação em C para esta FSM poderia ser:

#include <serial.h>
#include <keypad.h>
#include <display.h>
#define LE_TECLADO 0
#define LE_SERIAL 1
#define ESCREVE_SERIAL 2
// programa principal
void main(void)
{
   kpInit();
   displayInit();
   serialInit();
while (1)
{
 // atualiza display
    displayUpdate();
    switch(state)
    case LE_TECLADO:
    if (kpRead() != 0) // chegou comando
    {
    /* mais processamento */
      state = ESCREVE_SERIAL;
    }
    else
    {
      state = LE_TECLADO;
    }
    break;
    case LE_SERIAL:
    if (serialRead() != 0) // chegou comando
    {
      state = ESCREVE_SERIAL;
    }
    else
    {
      state = LE_SERIAL;
    }
   break;
   case ESCREVE_SERIAL:
   /* processa comando e responde */
   break; 
   default: 
     state=LE_TECLADO;
     break;
}

Perceba que como a função de atualizar o display precisa ser executada intermitentemente entre um estado e outro, ela pode ser acomodada antes do switch-case.

Neste caso, as funções serão executadas até a completude antes de passar a vez. Uma característica desejável de um sistema embarcado é o determinismo. Podemos então configurar um período de tempo fixo para todas as tarefas ocorrerem. Este período obviamente precisa ser maior que o pior caso de tempo de execução.

// programa principal
void main(void)
{
  kpInit();
  displayInit();
  serialInit();
  while (1)
  {
    // atualiza display
     displayUpdate();
     timerInit(300); // liga contador que vira a cada 300 ms 
     switch(state) 
     { 
      case LE_TECLADO: 
        if (kpRead() != 0) // chegou comando 
        { 
        /* algum processamento */ 
          state = ESCREVE_SERIAL; 
        } 
        else 
        { 
          state = LE_TECLADO; 
        } 
        break; 
     case LE_SERIAL: 
        if (serialRead() != 0) // chegou comando 
        { 
          state = ESCREVE_SERIAL; 
        } 
        else 
        { 
          state = LE_SERIAL;
        }
        break; 
     case ESCREVE_SERIAL: 
       /* processa comando e responde */ 
       break; 
     default: 
       state=LE_TECLADO; 
       break; 
  } 
  timerWait(); // espera o contador virar 
}

A desvantagem aqui é o tempo ocioso que o processador espera “somente” para padronizar as tarefas. Porém perceba que passamos de uma arquitetura cujo tempo de execução era difícil de prever para uma com tempo bem definido, e isto é um ganho enorme. O tempo livre aliás poderia ser utilizado para colocar o sistema em baixo consumo de energia, o acordando novamente com a interrupção do temporizador. Esta arquitetura é uma boa escolha para hardwares limitados em memória.

Escalonamento cooperativo com ponteiros para funções

Collins Walls no seu blog descreve o que diz ser um RTOS de uma linha, que basicamente utiliza um ponteiro para funções.

#define NTASKS 3
// pool de funções
void (*tasklist[NTASKS])() = {alpha, beta, gamma};
int taskcount;
void main()
{
  while (1)
  {
  // dispatcher
  for (taskcount=0; taskcount<NTASKS; taskcount++)
  {
   (*tasklist[taskcount])();
  } 
}

Apesar de simples, esta estrutura nos fornece muitos conceitos úteis. O uso de ponteiros para função já nos permite imaginar que as informações das tarefas a serem executada estarão armazenadas em algum espaço da memória, e o escalonador fica responsável por buscá-las e executá-las, sob alguma lógica de controle. Neste caso, é simplesmente a ordem do endereço das funções na matriz de ponteiros tasklist. Mas poderíamos adicionar mais critérios de escolha. Talvez um deadline temporal, informação de prioridade ou delay inicial.

Poderíamos garantir que todas as tarefas fossem executadas em um mesmo intervalo de tempo, com a mesma técnica aplicada na máquina de estados.

Poderíamos também criar uma pequena API:

// para adicionar tarefas

#define N_TASK 4 // numero de tarefas
typedef void(* ptrFunc)();
int pos;
void() addTask(ptrFunc newFunc)
{
  if (pos < N_TASK-1) // verifica se ha espaço no vetor
  {
    tasklist[pos] = newFunc;
  }
    pos++; //incremente posicao
}
// para disparar o escalonador
void sch_loop(void)
{
  int i;
  while(1)
  {
    for(i=0;i<N_TASK-1;i++)
    { 
      (*tasklist[i])();
    }
  }
}
// inicializa sch
void sch_init()
{
 pos=0;
}

E aí nosso código principal seria:

void main();
{
 schInit();
 addTask(alpha);
 addTask(beta);
 addTask(gama);
 schLoop();
}

Esta codificação parece ser desnecessária para executar três funções em fila, sem nenhum critério. O super-loop resolveria. Concordo, porém é o esqueleto de uma arquitetura que pode ser estendida para criar um scheduler mais robusto.

Executando processos uma única vez ou indefinidamente

No código apresentado as tarefas serão executadas na mesma ordem, ad infinitum. É interessante informarmos ao escalonador se a tarefa que acaba de retornar quer ou não ser executada ciclicamente. Para isso podemos criar códigos de retorno para as funções:

#define ONESHOT 0;
#define FAIL 1;
#define REPEAT 2;

Para executar processos uma única vez, precisamos poder removê-los do vetor de processos dinamicamente. Para isso, vamos transformar o vetor tasklist num buffer circular. As funções são inseridas no início do buffer e executadas em ordem. Caso uma função retorne REPEAT ela é inserida ao final do buffer. As tarefas são (re)agendadas dinamicamente.

Assim, precisamos alterar a função addTask para controlar o buffer tasklist de forma circular:

char addTask(ptrFunc newFunc)
{
 if ((last+1)%(N_TASK+1) != first)
 {
   tasklist[last] = newFunc;
   last=(last+1)%(N_TASK+1);
   return 0;
 }
 else 
 {
   return 1; //error
 }
}

A função schLoop agora precisa checar pelo valor de retorno do processo que acabou de executar. Se ele for REPEAT, ele é armazenado ao final do buffer.

void schLoop()
{
 while (1)
 {
   if (first != last) // tem algo
   {
     if ((*tasklist[first])() == REPEAT)
     {
       addTask(tasklist[first]); // reagenda
     }
      first=(fist+1)%N_TASK; // proximo processo
   }
 }
}

No próximo texto irei estender este escalonador para atender requisitos temporais de um sistema soft real-time.

O texto desta postagem é original. Os seguintes livros foram consultados para sua elaboração:
[1] Programação de sistemas embarcados, Rodrigo Almeida e outros.
[2] Real-Time Systems Development, Rob Williams 
[3] Patterns for Time-Triggered Embedded Systems,  Michael J. Pont

Operando números negativos em computadores

maxresdefault

Os conceitos de aritmética modular eram utilizados em computadores mecânicos, e já não eram novidade naquela época. (Imagem de: https://www.youtube.com/watch?v=nmwSmwNF9XY)

1. 《Tudo é número》(Pitágoras)

Os autores costumam dizer que a Matemática é desenvolvida conforme o homem necessita. Assim, podemos imaginar que os humanos primitivos faziam risquinhos para representar uma coleção de objetos (cabras, peles, filhos…). Constatada sua ineficiência, criaram-se símbolos que representavam tamanhos de coleções diferentes, depois símbolos que representavam uma coleção de outros símbolos, e a coisa foi ficando cada vez mais sofisticada.

Costumamos representar os numerais em uma base B, da seguinte forma, em uma notação de ponto fixo onde “a” é inteiro:

eq

O sistema de base 10 que utilizamos é composto pelos símbolos {0,1,2,3,4,5,6,7,8,9} para representar as quantidades de zero a nove unidades de algo. Aliás, o zero é uma invenção muito interessante pois é um símbolo que representa ‘não há’. Sei que até há algum tempo não existia consenso sobre o zero ser Natural ou não.

Dizemos também que utilizamos um sistema posicional – desloque o número para esquerda ou direita ele assume centenas, dezenas, milhares, centésimos…

2. O sinal é outro símbolo

Certamente você já internalizou o conceito, mas se em engenharia os números são abstrações de grandezas físicas, o sinal sempre carrega outro significado. Se eu tenho +R$100,00 na conta-corrente esse dinheiro pode sair do banco e entrar no meu bolso. Se eu tenho -R$100,00, este dinheiro somente pode assumir a direção contrária. Um móvel com aceleração de -12m/s^2 permanece em repouso sob uma referência que acelera a 12m/s^2. Não à toa, os números negativos também são chamados de relativos, e ter isto em mente ajuda a entender como representá-los em um computador digital.

Vamos analisar um somador hipotético, sem sinal, que utiliza 3 bits para representar cada uma das suas parcelas, e também 3 bits para representar o resultado. Em notação decimal, as entradas variam de 0 a 7. Ao somarmos 7+7, por exemplo, a saída ‘estoura’:

 111
+111
====
1110

O importante aqui é você perceber que estamos trabalhando num universo onde o maior número possível de ser representado é o 7. E isto é exatamente o que ocorre quando construímos computadores. Se o meu computador pode somente ter 3 bits, é como se tudo o que tivéssemos fosse um conjunto de 8 elementos distintos.

(d.i) Definição. Um Grupo G é um conjunto de elementos em que se pode definir uma operação binária *, que satisfaz os critérios de fechamento, elemento neutro, elemento simétrico e associatividade. Um exemplo de grupo é o conjunto dos inteiros (Z) para as operações de soma e multiplicação.

G = {x, y, z} é um grupo, se para uma operação binária *, {G, *} satisfaz os seguintes axiomas:

a) fechamento: Se x e y ∈ G, x *y ∈ G
b) elemento neutro: Existe um elemento I ∈ G, tal que a*I = I*a = a,
c) elemento simétrico: Para todo elemento a ∈ G, existe um elemento s tal que a * s = I
d) associatividade: Para x, y, z ∈ G é verdadeiro que: x*y*z = (x*y)*z = x*(y*z)

A ideia de infinito não é concebível para uma máquina, e utilizaremos grupos finitos.

(d.ii) Definição. Um grupo finito é um conjunto finito de elementos com uma operação binária que satisfaz os axiomas do fechamento, associatividade, e cancelamento (Se a*x = b*x, a = b).

Para o meu computador de 3 bits talvez seria conveniente utilizarmos os conjuntos:

A= { 0, 1, 2, 3, 4, 5, 6, 7}, ou

B = { 16, 17, 18, 19, 20, 21, 22, 23} quem sabe.

Eu empilhei os conjuntos acima para forçar a ideia de congruência entre os elementos. Além disso, para a operação de adição +, os axiomas de (d.ii) são satisfeitos se definirmos: 7+1 =0 em A e 23+1=16 e A e B podem ser considerados grupos.

(d.iii) Definição. Dizemos que dois grupos são equivalentes quando existe uma relação biunívoca, tal que para todo elemento a ∈ A e b ∈ B, existe k inteiro tal que a = b + kN, onde N é o número de elementos (módulo) de A e B.

Utilizando os exemplos A e B acima:

2 = 18 + 8k, se k = -2

20 = 4 + 8k, se k = 2,

3. Subtração com números não-negativos

Talvez seja conveniente representarmos um grupo finito G onde o maior módulo possível é 8, na forma de um círculo de comprimento 8:

modulo

Desta forma, podemos representar qualquer número inteiro a = b + kN, onde k é o “número de voltas” dadas no círculo de comprimento N, e ‘b’ o restante de arco (em unidades) necessário para completar ‘a’, que chamamos de resto ou resíduo.

Assim, para o nosso grupo de módulo 8:
i) 21 = 5 + 2x8
ii) 64 = 0 + 8x8
iii) 10 = 2 + 1x8

Que podemos escrever da seguinte forma:
iv) 21 ≡ 5 (mod8) (21 é congruente a 5 módulo 8)
v) 64 ≡ 0 (mod8) (64 é congruente a 0 módulo 8)
vi) 10 ≡ 2 (mod8) (10 é conguente a 2 módulo 8)

Se eu quero resolver 8 – 6, posso evitar trabalhar com subtrações. Primeiro vamos pensar graficamente:

  • Partindo do zero e andando 8 unidades voltamos ao zero, ou: 8 ≡ 0 (mod8)
  • Partindo do zero e andando 6 unidades a esquerda, chegamos ao 2, ou: -6 ≡ 2 mod8

Logo: 8 (mod8) – 6 (mod8) ≡ 0 (mod8) + 2 (mod8) ≡ 2 (mod8).

Abaixo, com exemplos, descrevo um algoritmo para resolver subtrações utilizando números não-negativos em um grupo módulo N.

(p.1) Problema.
Resolva 15 – 8 somente com números não-negativos, em G = {0,1,2,3,4,5,6,7}
1o - Ache o minuendo congruente no grupo desejado. 
O ‘equivalente modulo 8’ de 15 pode ser encontrado em G com (1):
15 = b + 8k, se k = 1, b = 7.
2o - Ache o subtraendo equivalente ao grupo desejado e some ao minuendo:
O equivalente a 8 em G é 0.
8 = b + 8x1; b = 0
Assim:
7 + 0 = 7.
3o - Encontre o equivalente do resultado no grupo desejado:
7 já esta no grupo desejado, e é o resultado.

(p.2) Problema.
Resolva: 22 – 12, somente com números não negativos em 
G = {8,9,10,11,12,13,14,15}
O equivalente de 22 no grupo G é:
22 = a + 8k, k = 1, e a = 14 
Assim:
14 + 12 = 26
Cujo equivalente em {8, 9, 10, 11, 12, 13, 14, 15} é:
26 = b + k8, k = 2 e b = 10.

Uma pequena demonstração algébrica do método pode ser feita.
(dm.i) Demonstração.
Sejam M, S e D pontos do meu universo módulo N, de forma que:
(i) M-S=D para
(ii) M>=S e D <= N.
e
(iii) D = 0 para M=S.
Queremos demonstrar que:
(iv) D = N - [(N-M) + S]
O lado direito de (iv) satifaz (ii) para M>=S.
Ainda para M=S, (iii) é satisfeito: D=N-N-M+M=0
Naturalmente em (iv):
D= M-S = N-N+M-S
D = M-S
como queria demonstrar.

4. Complementos numéricos

(d.iv) Definição.
(d.iv’) O complemento de b de um número de n dígitos y, na base b, é dado por: b^n – y.
(d.iv’’) O complemento de b-1 de um número de n dígitos y, na base b, é dado por (b^n – 1) - y

Os livros em geral começam a tratando do assunto desta postagem com uma tabela:

 Elemento | Complemento de 9 
 ---------------------------
    0     |    9
    1     |    8
    2     |    7  
    3     |    6
    4     |    5
    5     |    4
    6     |    3
    7     |    2
    8     |    1
    9     |    0

Tabela 1. Complementos de 9 para dos inteiros de 0 a 9

O método dos complementos é uma aplicação direta da aritmética modular, e fundamentalmente utiliza dos mesmos conceitos explicados nas seções anteriores.

Podemos efetuar as subtrações somente com números não-negativos, usando o complemento do minuendo somado ao subtraendo, e tomando o complemento da soma como resposta.

8-3 → 1 + 3 = 4.

O complemento para 9 de 4 é 5, que é a nossa resposta.

Quando tratamos de números maiores que dezenas, fazemos o complemento para 99, 999, 9999… (nossa aritmética continua posicional!)

Exemplo:

Resolva 953 – 53 utilizando o método dos complementos, em módulo 9

046+ 53 = 99

Cujo complemento para 999 é 900, que é a nossa resposta.

5. Complemento de 2

A base para a representação numérica digital é a binária B = {0, 1}, e vamos utilizar os conceitos de aritmética modular para operarmos subtrações com números binários.

Decimal 0 a 7 | Binário | Congruentes
-----------------------------------------
      0       |   000   | ...,-8,0,8,...
      1       |   001   | ...,-7,1,9,...
      2       |   010   | ...,-6,2,10,...
      3       |   011   | ...,-5,3,11,...
      4       |   100   | ...,-4,4,12,...
      5       |   101   | ...,-3,5,13,...
      6       |   110   | ...,-2,6,14,...
      7       |   111   | ...,-1,7,15,...

Tabela 2. Inteiros decimais de 0 a 7 representados na forma binária, e seus congruentes módulo 8.

No nosso computador de três bits podemos representar a reta numérica com os pontos decimais 0 a 7, em base 2, da seguinte forma:

    b'    a'    a     b    c    d    e    f    g    h
    ?     ?    000  001  010  011  100  101  110  111
   ------------------------------------------------->

Queremos representar números negativos. Ora, 
Se a + s = 0, s é o simétrico de a se 0 representar o elemento neutro 
da álgebra.

No caso dos números representados na reta numérica acima:
a + s = 000 ↔ a' = 000; (000 + 000 = 000) 
b + s = 000 ↔ b’ = 111; (001 + 111 = 1000)
c + s = 000 ↔ c’ = 110; 
d + s = 000 ↔ d’ = 101;
e + s = 000 ↔ e’ = 100;
f + s = 000 ↔ f’ = 011;
g + s = 000 ↔ g’ = 001.

Exceto para f e g, todos os simétricos tem 1 no bit mais significativo, de forma que para lançar mão de números negativos poderíamos definir nosso grupo com os seguintes elementos escritos em base 2:

Decimal | Binário
------------------
  -4    | 100
  -3    | 101
  -2    | 110
  -1    | 111
   0    | 000
   1    | 001
   2    | 010
   3    | 011

Escolhemos não representar o 4, e sim o -4 a partir dos resultados empíricos para encontrar o elemento simétrico.

Perceba que continuamos com o mesmos elementos de antes, entretanto, atribuímos a ele um grupo equivalente, com elementos côngruos modulo 2, mantendo todas as propriedades que já tornavam aquele um grupo finito válido (definições d.i, d.ii, d.iii). É possível provar que o conjunto G = {100, 101, 110, 111, 000, 001, 010, 011} é um grupo finito.

O complemento de 2, do número binário y de três dígitos por (d.iv’) é então 8 – y. A representação binária do complemento de 2 de um número y, é utilizada para a representar o elemento simétrico s, tal que y + s = 0.  Como regra prática dizemos que o complemento de 2 de um número na base 2, é sua negação adicionada a 1. (Pense em um círculo somente com os pontos 0 e 1 na base 2, e comprove graficamente por que funciona).
Interpretação do '1' como sinal: 

Peguemos como exemplo a igualdade 011 + 101 = 1000, que poderia significar 3 + 5 = 8, que é côngruo a 0 módulo 8. Ainda na base 2, oito é representado por 1000. O ‘1’ se pensado como sinal, indica o sentido pelo qual ultrapassamos a origem ao representarmos nossos arcos de maneira contínua. Andando da esquerda para direita os elementos assumem valores cada vez maiores. Quando os 3 bits estouram e o vai-um é necessário para representar o estado naquele instante , significa que os elementos agora estão assumindo valores cada vez mais negativos em relação aos anteriores.

Você pode experimentar efetuar as operações com o complemento de 2 e verificar como a notação é muito conveniente.

Note que:
O complemento de 2 é definido para representar números de base 2, de
N bits, no intervalo de -2^(N-1) a 2^(N-1) – 1.
Ao operarmos representações com números de dígitos diferentes, devemos estender o sinal. 
Exemplo:

-16 - 2 =
 10000
+11110
======
101110
O texto deste artigo é original. As seguintes referências foram consultadas durante sua elaboração:
Conceitos Fundamentais da Matemática (Bento Jesus de Caraça)
Introduction to Logic Circuits and Logic Design With Verilog (Brock J. LaMeres)
Group Theory, em https://crypto.stanford.edu/pbc/notes/group/group.html
Introdução à Teoria dos Números, em http://vigo.ime.unicamp.br/Projeto/2012-1/ms777/ms777_Viviane.pdf