Aritmética módulo 2
Este artigo não cita fontes confiáveis. (Março de 2016) |
Esta página ou seção foi marcada para revisão devido a incoerências ou dados de confiabilidade duvidosa.Fevereiro de 2008) ( |
A aritmética módulo 2 é uma forma de aritmética modular especialmente usada em ciência da computação por ser facilmente implementada dentro de processadores utilizando o sistema binário. Uma característica importante desta forma de aritmética é o fato de não haver propagação de dígitos (carry) entre as casas binárias nas operações aritméticas. Por exemplo, em binário tradicional 012 + 012 = 102, onde há uma propagação do dígito 1 para uma casa à esquerda. Na aritmética módulo 2 temos que 012 + 012 = 002, onde não há propagação do dígito 1. Ter em conta que, ao longo deste tópico, a nomenclatura "X2" refere-se a um número binário X (i.e. na base 2).
Representação polinomial
[editar | editar código-fonte]Os números binários usados na aritmética módulo 2 podem ser vistos como sendo polinômios onde cada dígito é um dos coeficientes do polinômio. Assim o número 100102 pode ser representado por , ou simplesmente . As operações sobre estes coeficientes obedecem a aritmética modular de base 2, onde temos:
- Obs: 1 + 1 = 0 (e vai 1 que se soma ao dígito seguinte)
Igualmente, a operação de subtração segue a mesma regra de aritmética modular em relação aos coeficientes dos polinômios:
- Obs: 0 - 1 = 1 (e vai 1 que se subtrai ao dígito seguinte)
Soma e subtração : caso comum
[editar | editar código-fonte]Podemos notar no diagrama supracitado, que as duas operações tem sempre o mesmo resultado equivalente ao da operação lógica de ou exclusivo (ou XOR, da sigla em inglês eXclusive OR). A aritmética módulo 2 pode então ser facilmente calculada através de uma operação de ou-exclusivo realizada bit a bit entre os coeficientes do polinômio, ou seja, dos dígitos binários.
Como exemplo podemos somar o polinômio com outro polinômio . O primeiro passo é a transformação do polinômio em um número binário:
e
Procedemos então ao ou-exclusivo bit-a-bit (designada também por "soma polinomial em módulo 2"):
ou ainda:
Divisão
[editar | editar código-fonte]Existem diversas formas realizar a divisão de módulo 2 entre dois números binarios. A melhor maneira é fazer a representação polinomial do Dividendo D e do Divisor d , e subtrair consequentemente os monómios do polinômio D. Ao Dividendo polinomial D inicial, é concantenado á sua direita tantos monómios quanto o grau do polinômio d .
Exemplo: Dividir 101011 por 11001
11001 corresponde ao Divisor d(o qual também é designado por polinômio "gerador"), e é representado pelo polinômio de grau 4, 1 + 1 + 0+ 0 + 1 =
101011 corresponde ao Dividendo inicial D
1010110000 corresponde ao Dividendo inicial D concatenado com tantos bits nulos quanto o grau do polinômio d (Neste caso o grau polinomial é de 4)
Assim sendo, 1010110000 o qual corresponde ao Dividendo final , será expresso pelo polinômio
1 + 0 + 1 + 0 + 1 + 1 + 0 + 0 + 0 + 0
Procedemos á divisão :
__ __ __ __ __ __ |
-__ __
0 __0
- __0
0 0
- 1
0 1
RESTO : +1 = 1 + 0+ 0+ 1 ; EM BINARIO : 1 0 0 1
QUOCIENTE : = 1 + 1 + 0 + 0 + 0+ 1 ; EM BINARIO: 1 1 0 0 0 1