wireworld
WireWorld
"O Mundo dos fios"
WireWorld, ou "mundo dos fios", é uma regra de "automato celular" descrita inicialmente por Brian Silverman em 1987.
Basicamente o mundo dos fios consiste em uma matriz infinita, na prática o quão grande você desejar, aonde cada célula da matriz pode assumir somente quatro valores diferentes. chamados de "vazio", "fio", "cauda" e "cabeça". A célula vazia(vazio) é um local aonde não existe nada, nem fios nem impulsos lógicos; A célula com fio é aonde os impulsos trafegam, e "cauda" e "cabeça" são as duas partes do impulso necessárias para definir em um determinado estado a direção do inpulso no fio.
Estes valores interagem entre si e mudam de acordo com quatro regras descritas a seguir:
1. Uma célula vazia sempre continuará vazia.
2. Uma célula contendo "cabeça" sempre se tornará "cauda".
3. Uma célula contendo "cauda" sempre se tornará "fio".
4. Uma céula contendo "fio" se tornará "cabeça" se houver duas ou três cabeças vizinhas(8 vizinhos), senão permanecerá fio.
As regras são simples, com exceção da quarta regra que exige um pouco mais de esforço para compreender, a cada ciclo de processamendo do WireWorld estas regras são aplicadas em todas as células da matriz do mundo. Utilizando estas regras simples é possível construir operações lógicas básicas e até flip-flops, consequentemente criar sistemas lógicos complexos, de fato adiante irei apresentar um computador programável construido no WireWorld.
Sinais
Graças a estas regras pulsos lógicos podem trafegar em sequências de células "fios" ou um fio, como você pode observar.
(clique nas imagens para ver a animação)
A cabeça precede a cauda. As quatro regras são aplicadas e produzem este efeito de transporte de um sinal.
Obviamente no WireWorld as coisas são bm diferentes do mundo real, um pulso necessita de um tempo para trafegar em um barramento e as coisas devem ser construídas de forma que tudo fique sincronizado. Um fio mais longo produzirá considerável atraso nos sinais.
Em um sistema lógico operante no wireworld deve se definir o "clock", que é medido na distância entre uma "cabeça" de um pulso e a próxima. Michael Greene demonstrou que é possível construír todas as funções lógicas com um clock 3, o menor possível. No artigo inicial apresentado na Scientific American foi apresentado algumas operações lógicas trabalhando a clock de 13.
A seguir apresentamos um barramento com clock 6.
Note como é simples duplicar um sinal com mesmo sincronismo.
Diodo
O diodo é um dos componentes eletrônicos mais básicos, construído inicialmente com uma válvula e hoje com semicondutores, a função do diodo é permitir somente o tráfego do sinal em um sentido(positivo - negativo). No mundo dos fios existe uma construção de equivalente lógico ao diodo:
A porta OR:
Apresentamos a porta OR, cuja operação lógica "ou" consiste em liberar uma saída ativa se pelo menos uma das entradas for ativa:
É possível concatenar portas OR para criar uma porta OR equivalente com maior número de entradas.
A Porta Exclusive OR:
A porta XOR, ou exclusivo, libera um sinal ativo se somente uma das entradas for ativa:
A porta AND-NOT:
Esta construção faz a operação lógica "A and not B", cujo objetivo é apresentar uma saída ativa se A for ativo e B não, somente nessa condição:
Devido a simplicidade desta construçãos ser maior do que a própria porta AND, apresentamos esta, entretando a porta AND pode ser facilmente construída fazendo concatenações de portas AND-NOT. Outra possibilidade para implementar uma porta AND-NOT é esta:
Memória ROM:
A ROM, memória somente leitura deve ser útil para um sistema verificar tabelas de dados como para uso em displays de sete segmentos. Observe esta construção:
Os sinais vindos de baixo atingem células de ROM específicas que liberam um sinal lógico ou não, dependendo do que foi "gravado" na memória, esta gravação é "física" pois é uma configuração de células fios diferente em cada bit da memória.
O Flip Flop
Aprensentamos o módulo que permite armazenar um bit de dado dinamicamente, o flip flop, com duas operações ele permite escrever e apagar um bit na sua contrução e uma saída pode ser lida.
Utilizando flip-flops podem ser construidos registradores, que são as bases para o computador WireWorld, descrito a seguir, apesar de que os registradores de fato implementados utilizam outro sistema de armazenamento que ocupam menos espaço.
O computador WireWorld
O computador WireWorld tem uma arquitetura simples, sua memória principal endereçável é formada por sessenta e quatro registradores, sua saída é um simples display de cinco números no sistema decimal.
Este computador foi implementado por David Moore e Mark Owen, maiores informações podem ser encontradas neste site, como o conjunto de instruções e mais detalhes sobre o seu funcionamento. No exemplo que anexo no simulador WireWorld o computador está programado para calcular todos os números primos.
Este é o programa escrito para gerar os números primos na saída:
Reg Hex Disassembly
1 001e MOV R0 ,R30 ; set display to 2
2 361f MOV R54,R31 ; initialise mask register for sign bit test
3 2021 MOV R32,R33 ; set candidate prime p=3
4 3c22 MOV R60,R34 ; the trial divisor q is stored in the adder as its
; negative: here it is initialised to -1, i.e. q=1
5 3d23 MOV R61,R35 ; other summand=-2
6 3c3d MOV R60,R61 ; next trial divisor q=q+2
7 3d20 MOV R61,R32 ; move p to adder summand input a, which holds remainder
8 3924 MOV R57,R36 ; for the first time round the loop, set the target
; for the branch if subtraction gives zero to 20: this
; detects the case p==q, which means we have done all
; the trial divisors and p is prime
9 3725 MOV R55,R37 ; if subtraction result non-zero, target is 13
10 383d MOV R56,R61 ; test a-q
11 3f38 MOV R63,R56 ; branch to selected target
12 3d3d MOV R61,R61 ; a-=q
13 3d3d MOV R61,R61 ; a-=q (continuing here if subtraction result not zero)
14 353d MOV R53,R61 ; move a-q to and-not register to check sign
15 3926 MOV R57,R38 ; target is 9 if a-q positive (round subtraction loop
; again)
16 3727 MOV R55,R39 ; else target is 5 (q does not divide p, so try next q)
17 3836 MOV R56,R54 ; test a-q AND 0x8000
18 3f38 MOV R63,R56 ; branch to selected target
19 3928 MOV R57,R40 ; reset target for other branch to 21 (a zero result
; from the subtraction now indicates q properly
; divides p and so p is composite)
20 0020 MOV R0 ,R32 ; p is prime: write it to the display
21 3d20 MOV R61,R32 ; move p to adder
22 3c1e MOV R60,R30 ; other summand=2
23 3f29 MOV R63,R41 ; goto 4 to try new p
24 203d MOV R32,R61 ; p+=2
25 ; unused
26 ; unused
27 ; unused
28 ; unused
29 ; unused
30 0002 ; constant 2
31 7fff ; constant mask for sign bit testing
32 0005 ; current candidate p
33 0003 ; constant 3
34 fffe ; constant -1
35 fffd ; constant -2
36 0014 20 ; branch target: trial divisor q equal to candidate p,
; and hence prime found
37 000d 13 ; branch target: trial divisor q less than candidate p
38 0009 9 ; branch target: more subtractions to do
39 0005 5 ; branch target: next trial divisor q
40 0015 21 ; branch target: subtraction gave zero, so p composite
41 0004 4 ; branch target: next candidate p
42 fffc ; constant -3
Note que os endereçamentos são dados em termos do registrador, já que são poucos neste computador. Foram utilizados diversos módulos de operações lógicas que não descrevi aqui, como um banco de registradores, demultiplexador, conversor binário-BCD, gerador de pulsos e um somador binário juntamente com outras operações lógicas aritméticas na ULA.
Existem muitos detalhes da arquitetura deste computador que não coloquei aqui mas estas informações estão disponíveis na página dos autores.
Download
(anexo arquivos de exemplo inclusive o computador wireworld)
(caso o programa requira algum arquivo, baixe estes arquivos, coloque-os no mesmo diretório ou o diretório SYSTEM do windows)
Links
http://www.quinapalus.com/wi-index.html
http://mathworld.wolfram.com/WireWorld.html
Copyright 2006 - Rodrigo Setti