O segundo algoritmo que vou mostrar é o código de Hamming.
Este código é gerado por operações lineares sobre blocos de dados e foi desenvolvido por Richard Hamming. É muito utilizado no processamento de sinal e nas telecomunicações. Também devido à sua simplicidade é utilizado em memórias de computador tipo ECC.
Para um bloco de dados constituído por n bits (ou palavra), o código de Hamming é obtido inserindo pontos de controle, denominados bits de paridade, como mostrado na tabela abaixo. Para uma palavra de comprimento n bits, são inseridos um número fixo k bits de paridade, ficando a palavra de código com um comprimento N= n + k. A composição do código final é feita de acordo com a montagem das paridades abaixo:
Vamos ver um exemplo real para entender melhor. Veja no vídeo como é feito o algoritmo que implementa o código de Hamming (7,4), ou seja para palavras de 4 bits, gera um código final de 7 bits.
Estou estudando sobre a operação de redes de computadores e me deparei com alguns algoritmos bastante interessantes que são utilizados pelos protocolos de comunicação para garantir que durante a transmissão de dados sejamos capazes de detectar erros de transmissão e até mesmo de corrigi-los.
Neste post vou descrever dois deles:
O CRC (Cyclic redundancy check) que permite detectar erros de transmissão e que já vamos achar pronto sua implementação em Java, basta saber chamar as classes corretamente.
O Código de Hamming que permite detectar e corrigir erros nos bits transmitidos
O CRC (verificação de redundância cíclica) é um código capaz de detectar erros. Utiliza uma técnica polinomial que gera um valor (com poucos bits de tamanho se comparado com bloco de dados que queremos verificar). Este valor é utilizado para verificar se houve erro na transmissão de dados. A fórmula indicada abaixo é complicada, mas por incrível que pareça pode ser implementada em hardware com componentes comuns.
Além disto o CRC apresenta boa eficiência em detectar erros causados por ruído em canais de transmissão. Vamos ver como implementá-lo em Java.
Vamos ver neste post alguns exemplos utilizando IO com Java. Nesta sequência de cinco vídeos vamos ver algumas opções de utilização de java.io.
No vídeo #1 vamos criar duas classes. A primeira JavaIoStream será a classe com método main() que irá chamar todas as demais classes dos nossos exemplos, desta forma, ela é basicamente uma classe com um método estático que instancia as demais classes. Note que não precisamos fazer a importação das classes pois todas pertencem ao mesmo pacote.
Utilizamos neste vídeo a classe EscrevendoByteStream que utiliza basicamente duas classes:
java.io.FileInputStream: que permite criar um fluxo de entrada de dados (input stream) que nos permitirá ler os dados de um arquivo determinado na criação da classe;
java.io.FileOutputStream: que permite criar um fluxo inverso de dados ou seja permite escrever em um arquivo os dados que são enviados para a stream.
O nosso exemplo é bastante simples. Criamos uma stream de entrada e uma de saída, encaminhamos todo o conteúdo da primeira para a segunda. Pronto! Temos uma cópia fiel do arquivo original.
É importante destacar que são verificadas duas exceções nesta classe:
java.io.FileNotFoundException: que acontece quando tentando ler um arquivo e ele não existe;
java.io.IOException: uma exceção mais genérica que acontece durante a leitura e gravação do arquivo, como por exemplo se o arquivo estiver corrompido. É possível fazer um tratamento mais refinado, porém para o nosso exemplo, isto basta.
No vídeo #2 melhoramos um pouco a nossa classe EscrevendoByteStream, criando uma nova classe EscrevendoByteStream02. Note que não estamos herdando nada da primeira classe. Usamos o código original como base para fazer algumas melhorias:
utilizamos um recurso do Java 7 denominado try...with resources. Como ele podemos criar um try que inicializa os recursos e na saída do try estes recursos são automaticamente fechados e liberados, poupando nosso esforço como programadores
no exemplo original a leitura era feita byte a byte. É possível melhorar a performance lendo um bloco de dados. Na verdade, a melhoria é basicamente no loop. Normalmente os sistemas operacionais já leem um bloco de dados do disco e armazenam em buffer, assim a leitura no Java de um bloco de dados, faz um acesso ao sistema operacional que lê um bloco inteiro do disco e depois as leituras dos demais caracteres é feita deste buffer que já está em memória.
notem no nosso exemplo que mantive as chamadas para o método close dos streams. Faça um teste retirando esta chamada, você verá que não será gerado erro. Isto porque o try...with resources já fecha os recursos abertos automaticamente.
No vídeo #3 tratamos de utilizar "character streams". A primeira vista parece que é uma opção pior que aquelas dos vídeos #1 e #2, porém veremos que as classes java.io.BufferedReader e java.io.BufferedWriter apresentam recursos adicionais para tratamento de caracteres que permite codificar os dados de acordo com um charset ou convertê-lo de um charset para outro. Estas opções não conseguimos fazer com FileInputStream/FileOutputStream que tratam com os dados brutos. Se vocês compararem os exemplos verão que o processo é semelhante.
Neste vídeo (#4) mostramos que é possível trabalhar com buffer. No nosso exemplo a chamada foi feita em duas linhas, mais por questões didáticas: FileReader fr = new FileReader(entrada); BufferedReader fin = new BufferedReader(fr); mas poderia ter sido feita em uma linha BufferedReader fin = new BufferedReader(new FileReader(entrada));
O mesmo valor para a saída.
Continuando a explorar os recursos de FileReader, vamos ver como obter realizar um pré tratamento dos dados de entrada utilizando a classe java.util.Scanner. No nosso exemplo #5, utilizaremos esta classe para obter os valores de um arquivo separados por vírgulas, também chamado de CSV. Note que basta definir o delimitador para poder trabalhar com um arquivo separado por espaços, ou por tabulações ou por ponto e vírgula. A classe Scanner é muito versátil e voltaremos a ela em outro post.
