Aritmética módulo 2

Predefinição:Sem-fontes Predefinição:Revisão 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 01₂ + 01₂ = 10₂, onde há uma propagação do dígito 1 para uma casa à esquerda. Na aritmética módulo 2 temos que 01₂ + 01₂ = 00₂, onde não há propagação do dígito 1. Ter em conta que, ao longo deste tópico, a nomenclatura "X₂" refere-se a um número binário X (i.e. na base 2).

Representação polinomial

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 10010₂ pode ser representado por $1x^4+0x^3+0x^2+1x^1+0x^0$, ou simplesmente $x^4+x$. As operações sobre estes coeficientes obedecem a aritmética modular de base 2, onde temos:

$\{\begin{array}{cc}0+0(\mathrm{mod}2)& =0\\ 0+1(\mathrm{mod}2)& =1\\ 1+0(\mathrm{mod}2)& =1\\ 1+1(\mathrm{mod}2)& =0\end{array}$

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:

$\{\begin{array}{cc}0-0(\mathrm{mod}2)& =0\\ 0-1(\mathrm{mod}2)& =1\\ 1-0(\mathrm{mod}2)& =1\\ 1-1(\mathrm{mod}2)& =0\end{array}$

Obs: 0 - 1 = 1 (e vai 1 que se subtrai ao dígito seguinte)

Soma e subtração : caso comum

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 $x^4+x$ com outro polinômio $x^4+x^3+1$. O primeiro passo é a transformação do polinômio em um número binário:

$x^4+x=10010_2$

e

$x^4+x^3+1=11001_2$

Procedemos então ao ou-exclusivo bit-a-bit (designada também por "soma polinomial em módulo 2"):

$\begin{array}{cc}& (x^4+x)+(x^4+x^3+1)\\ =& (1+1)x^4+(0+1)x^3+(0+0)x^2+(0+1)x^1+(0+1)x^0\\ =& (0)x^4+(1)x^3+(0)x^2+(1)x^1+(1)x^0\\ =& x^3+x+1\end{array}$

ou ainda:

$10010_2\oplus 11001_2=01011_2$

Divisão

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$x^4$ + 1$x^3$ + 0$x^2$+ 0$x^1$ + 1$x^0$ = $x^4+x^3+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$x^9$ + 0$x^8$ + 1$x^7$ + 0$x^6$ + 1$x^5$ + 1$x^4$ + 0$x^3$ + 0$x^2$ + 0$x^1$ + 0$x^0=x^9+x^7+x^5+x^4$

Procedemos á divisão :

 $x^9$__ $x^7$__$x^5$   $x^4$ __ __ __ __    | $x^4+x^3+1$

-$x^9$$x^8$__ __$x^5$                            $x^5+x^4+1$
 0 $x^8$ $x^7$__0
  -$x^8$ $x^7$ __0   $x^4$
    0  0         $x^4$
                  -$x^4$ $x^3$              1
                   0 $x^3$               1

RESTO :  $x^3$+1 = 1 $x^3$+ 0$x^2$+ 0$x^1$+ 1 $x^0$;  EM BINARIO : 1 0 0 1

QUOCIENTE :  $x^5+x^4+1$ = 1 $x^5$+ 1 $x^4$+ 0 $x^3$+ 0 $x^2$+ 0$x^1$+ 1 $x^0$;  EM BINARIO: 1 1 0 0 0 1

Predefinição:Esboço-matemática