domingo, abril 16, 2023
Ontem falei com o meu amigo no algoritmo de Reed-Solomon de correcção do erro.
O telemóvel, o multibanco, a televisão digital, a comunicação em fibra óptica ou por satélite, os discos rígidos e os SSD, as pendrives, e muita mais coisas seriam pelo menos 10 vezes mais caros se não houvesse algoritmos de correcção do erro e haveria mesmo coisas, como os satélites de exploração do espaço profundo, que não existiriam.
E, no entanto, aposto que nunca ouviu falar destes nomes.
A questão foi "Sendo que o seu algoritmo é usado por todas as pessoas todos os dias, como é possível que ninguém ouça falar destes dois cientistas?
Chama-se a isto "ingratidão da humanidade".
Mas vamos ao problema e à forma como estes cientistas o resolveram.
Tudo tem erro.
Uma das leis da "ciência da informação" é que quando gravamos ou enviamos informação, nunca temos 100% de rigor. A diferença entre o que queremos e o que temos é o erro que, em termos físicos, é um ruído.
Se a informação for "analógica" (isto é, um número real), o erro é quantificado como o desvio padrão. Para diminuirmos o erro precisamos enviar várias cópias e usar a média. Podemos diminuir o erro (para diminuir o erro padrão de 0,1 para 0,01, é necessário repetir 100 vezes a mensagem) mas nunca podemos ter erro zero.
A vantagem de termos números binários é que podemos corrigir integralmente os erros. O erro no número binário é a probabilidade de um bit ser alterado, um zero passar a um ou um um passar a zero.
Reduzir o erro de 1/100 para 1/1000000000.
Guardo bits num disco e a gravação tem um erro de 1/100 (isto é, em cada 100 bits, 1 está errado). O que pretendo é ler a informação, corrigi-la e, depois, ficar com um erro de 1/10000 000000 (um em dez mil milhões). Aplica-se o mesmo raciocínio à transmissão de informação com ruído.
A forma intuitiva de fazer o sistema capaz de corrigir os erros é ter várias cópias da informação. Para reduzir o erro na proporção pretendida tenho de ter 11 cópias da mensagem e, depois, usar como valor correcto o mais frequente (que pode ser 0 ou 1). Desta forma, apenas 9% do disco poderá ser usado (os outros 91% são para as cópias de segurança).
O que Irving S. Reed e Gustave Solomon criaram em 1960 foi um algoritmo que consegue reduzir o erro sem a necessidade de ter 11 cópias.
Vejamos a simplicidade da ideia. A implementação do algoritmo não é bem como vou explicar mas consegue dar uma intuição do seu funcionamento.
1 = Vou partir a mensagem em blocos.
A minha informação é uma sequência com milhares de milhões de zeros e uns e vou dividir esta sequência em grupos. A implementação mais popular (nas pendrives e nos CDs) é o RS(255, 223) de 8 bits em que a parte "útil" são 223 bytes / 1784 bits e a parte redundante são 32 bytes/ 256 bits.
Esta implementação permite corrigir, em média, até 30 erros em 223 bytes.
Cada número vai ser um ponto (x; y), por exemplo, (1; 10100100), (2; 01001110), ...
2 = Calculo o polinómio de grau 223 que passa pelos 223 pontos de 8 bits (a informação).
Este polinómio é único. É necessário muito poder de cálculo para obter este polinómio mas, como é uma operação repetida, é implementado em hardware (o que torna a operação muito rápida).
3 = Calculo pontos adicionais.
Tenho de calcular informação redundante que consiste nos 32 pontos seguintes do polinómio. Os 32 pontos redundantes permite reduzir o erro de 1/28 = 3,6% em 1/10^9 (cálculos estatísticos que fiz).
4 = Melhorei substancialmente o processo.
Para reduzir o erro de 3,6% para 1/10^9 precisaria de 15 cópias repetidas (o bloco de 223 bytes precisa de 3345 bytes). Com o RS apenas preciso guardar 255 bytes. Desta forma, o algoritmo aumenta a capacidade útil do disco ou da transmissão de 6,67% para 87,45%.
E como conseguimos corrigir os erros?
Leio os 255 bytes e vou ajustar um polinómio de grau 223 aos 255 números.
Se não houver nenhum erro, o ajustamento é perfeito (todos os 255 pontos "caiem" no polinómio).
Se o ajustamento não for perfeito, há erros. Tenho então de os corrigir.
Retiro os 32 números que se afastam mais do ajustamento (estão ai os erros).
Calculo o polinómio de grau 223 que passam pelos 223 pontos restantes. Estes pontos não são apenas pontos dos primeiros 223 bytes pois os erros também acontecem na informação redundante.
Substituímos os 32 pontos que excluímos pelos valores obtidos a partir do polinómio e recuperamos os primeiros 223 bytes.
E já está tudo corrigido.
Por exemplo.
Imaginem que o chip de memória de 1Tb da Micron TCL tem nas células de 3 bits um erro de escrita de 10% (1 erro em cada 10 células escritas). Esta taxa de erro torna o chip totalmente inútil (os ficheiros terão uma enormidade de erros).
Vamos supor que a Micron pretende garantir um erro de leitura menor do que 1 num milhão de bits.
O chip com um erro de 1/10 é extraordinariamente mais barato do que outro chip com um erro de 1/1000000.
Haverá um incremento no custo por causa da área de reserva e do controlador (que calcula o Reed-Solomon) mas, mesmo assim, é um incremento extraordinariamente menor do que fazer um chip com um erro de 1/1000000.
Álgebra modular.
Vamos supor que temos números inteiros positivos com 4 bits (0 a 15) e que realizamos operações algébricas (somas, subtracções, multiplicações e divisões) com vários destes números.
Por exemplo (15+7+2)*12 + 13= 301 tem 9 bits.
O mais certo é que o resultado tenha mais do que 4 bits (301 tem 9 bits).
A álgebra modular tem propriedades, por exemplo,
resto(resto(X, 15) + resto(Y, 15), 15) = resto(X+Y, 15)
resto(resto(X, 15)*resto(Y, 15), 15) = resto(X*Y, 15)
Naturalmente, quando guardamos informação redundante usando o algoritmo de Reed-Solomon, os pontos vão ter mais bits do que os números considerados.
Temos então de reduzir o tamanho dos números trocando-os pelo resto da divisão inteira com o valor máximo possível. Por exemplo, se temos números de 4 bits, vamos dividir por 15. No exemplo, o resto da divisão de 301 por 15 é o valor 1.
O "bit de paridade" é o caso limite da redução e o conhecido "noves fora" (que reduz qualquer número a apenas um dígito) é a aplicação do conceito à numeração decimal.
Aplicando esta transformação há diminuição da informação mas, escolhendo o número de bits adequado (e com poder de cálculo), conseguimos manter uma quantidade suficiente de informação.
Vejamos um exemplo com 4 bits.
Tenho um sector de 16 bits, 4 números de 4 bits (1; 5), (2; 7), (3; 6), (4; 8) em que a ordenada é a ordem em que aparecem os números. Ajusto o polinómio que passa por estes pontos, V = 1x3 - 7,5x2 + 17,5x - 6.
Agora, vou usar o polinómio para calcular três pontos de informação redundante e que são, (5; 19), (6; 45), (7; 92). Estes números têm mais do que 4 bits, pelo que vou guardar apenas o resto da divisão por 15, (5; 4), (6; 0), (7; 2).
Vou ter no disco, ou transmitir, a mensagem (1; 5), (2; 7), (3; 6), (4; 8), (5; 4), (6; 0), (7; 2).
Quando recebo a informação, determino se os valores têm erro resolvendo a equação da regressão linear pelo método dos mínimos quadrado (que é cálculo matricial).
A matriz X é uma "constante", (1, 1, 1, 1); (1, 2, 4, 8); (1, 3, 9, 27); (1, 4, 16, 64); ...
Desta forma, M = (X^T.X)^(-1) também é uma constante calculada apenas uma vez na "vida".
Então, determino o polinómio com apenas duas multiplicações matriciais:
Quando acontece um erro.
Se não tivesse "reduzido" os números, era muito fácil identificar e corrigir os erros, bastava ajustar um polinómio de grau 3 aos 7 pontos e excluir os pontos mais distantes.
Ao "reduzir" os bits dos números redundantes, torna-se computacionalmente mais fácil identificar e corrigir os erros mas mantém-se possível.
Se usar números de 1 bit.
Se tivermos 4 bits, na estimação do polinómio "óptimo" saltamos de 15 em 15 mas se tivermos apenas 1bit, temos de experimentar muitos mais valores (saltamos de 1 em 1).
Números com mais bits obriga a mais bits redundantes mas diminui o tempo de cálculo.
Aplicando a álgebra modular reduzimos e uniformizamos a informação gravada mas precisamos de mais poder de cálculo quando precisamos identificar e corrigir os erros.
0 comentários:
Enviar um comentário