Aritmética módulo 2

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{cases}0+0{\pmod {2}}&=0\\0+1{\pmod {2}}&=1\\1+0{\pmod {2}}&=1\\1+1{\pmod {2}}&=0\end{cases}}$

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{cases}0-0{\pmod {2}}&=0\\0-1{\pmod {2}}&=1\\1-0{\pmod {2}}&=1\\1-1{\pmod {2}}&=0\end{cases}}$

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{alignedat}{2}&(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{alignedat}}$

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