Especificação do Trabalho

Descrição e Objetivo

Esse trabalho em grupo consiste em um aprofundamento do estudo dos mecanismos de detecção e correção de erros utilizados em redes de computadores e outros sistemas computacionais. O trabalho é constituído do estudo, implementação e análise de certos métodos simples de correção de erros. Mais especificamente, esse trabalho pode ser dividido nas seguintes etapas:

1. Implementar funções de codificação e decodificação de um pacote, utilizando o método de paridade bidimensional com três tamanhos diferentes de matriz de paridade (ou parametrizável).
2. Pesquisar sobre Código de Hamming, compreendendo como o método funciona.
3. Implementar funções de codificação e decodificação de um pacote, utilizando o método de Código de Hamming com três níveis diferentes de paridade (ou parametrizável).
4. Executar experimentos com os métodos implementados, avaliando métricas como a taxa de erro de bits e o overhead introduzido pelos métodos.
5. Escrever um relatório, explicando o funcionamento do Código de Hamming, documentando as implementações realizadas e reportando a metodologia e resultados obtidos na avaliação.
6. Realizar uma apresentação do conteúdo do relatório.

As seções a seguir detalham cada um destes pontos.

Implementações de Referência

Para auxiliar nas tarefas de implementação envolvidas nesse trabalho, estão sendo disponibilizadas implementações de referência. Tais implementações consistem em variações de uma espécie de simulador de transmissão de pacotes. Esse simulador gera um pacote aleatório, realiza a codificação desse pacote utilizando um determinado método de detecção e correção de erros, insere erros aleatórios no pacote, realiza a decodificação de acordo com o método utilizado e, ao final, conta o número de bits errados encontrados (em relação ao conteúdo original do pacote aleatório gerado). Esse processo é repetido por uma quantidade determinada de vezes e, por fim, o programa exibe algumas estatísticas referentes às simulações.

As implementações de referência estão disponíveis em duas linguagens: C e Python. Para cada linguagem, estão disponíveis os seguintes arquivos:

• ParidadeBidimensional.c / ParidadeBidimensional.py: codificação e decodificação realizadas de acordo com o método de paridade bidimensional usando uma matriz 2 X 4;
• noFEC.c / noFEC.py: sem codificação ou decodificação (i.e., não são adicionados bits de paridade e o pacote e transmitido exatamente como gerado);
• template.c / template.py: implementações incompletas a serem utilizadas como base para as implementações pedidas nessa especificação (as funções a serem completadas estão destacadas no código).

As implementações em C fazem uso da biblioteca matemática da linguagem. Por isso, é necessário especificar opções adequadas durante o processo de compilação. Por exemplo, com o compilador gcc pode-se utilizar os seguintes comandos:

# gcc ParidadeBidimensional.c -o ParidadeBidimensional -Wall -lm

# gcc noFEC.c -o noFEC -Wall -lm

Todos os programas recebem os mesmos argumentos através da linha de comando. Quando executados sem argumentos, todos exibem uma pequena ajuda, decrevendo esses parâmetros:

# python noFEC.py

Simulador de metodos de FEC/codificacao.

Modo de uso:

    .noFEC.py <tam_pacote> <reps> <prob. erro>

Onde:

    - <tam_pacote>: tamanho do pacote usado nas simulacoes (em bytes).

    - <reps>: numero de repeticoes da simulacao.

    - <prob. erro>: probabilidade de erro de bits (i.e., probabilidade

de que um dado bit tenha seu valor alterado pelo canal.)

Quando alimentados com parâmetros adequados, todos os programas devem gerar como saída algo similar a:

# ./ParidadeBidimensional 1500 100 0.05

Numero de transmissoes simuladas: 100

Numero de bits transmitidos: 1200000

Numero de bits errados inseridos: 105263

Taxa de erro de bits (antes da decodificacao): 5.01%

Numero de bits corrompidos apos decodificacao: 32012

Taxa de erro de bits (apos decodificacao): 2.67%

Numero de pacotes corrompidos: 100

Taxa de erro de pacotes: 100.00%

A ideia é que as implementações de referência provejam exemplos de como o grupo deverá implementar seu próprio código. Além disso, os arquivos de template podem (e devem) ser usados como base para as novas implementações. O template na linguagem C demanda a escrita de 3 funções (codificação, decodificação e tamanho do pacote codificado), enquanto o template em Python necessita apenas da reescrita de duas funções (codificação e decodificação).

Os grupos são livres para escolher a linguagem de programação mais adequada ao desenvolvimento das suas implementações. A linguagem escolhida pode, inclusive, ser diferente de C ou Python. Nesse caso, no entanto, o grupo se responsabilizará por reimplementar as demais funcionalidades das implementações de referência na linguagem escolhida.

Implementação da Paridade Bidimensional

O método de paridade bidimensional foi estudado durante as aulas. Ele consiste na quebra do pacote em blocos de n X m bits. Os bits de cada bloco são dispostos em uma matriz de n linhas por m colunas e paridades são computadas para cada linha e cada coluna (resultando, portanto, em n + m bits de paridade). Os bits do bloco acrescidos dos bits de paridade recém-calculados são adicionados ao pacote codificado resultante e o processo se repete para o próximo bloco de bits.

Usando uma matriz 2 X 4, por exemplo (como na implementação de referência fornecida para a paridade bidimensional), pode-se utilizar o seguinte esquema de codificação <=> decodificação:

O grupo deverá realizar três implementações das rotinas de codificação e decodificação do método de paridade bidimensional com matrizes de dimensões diferentes (ou uma implementação que seja parametrizável pelas dimensões da matriz de paridade desejada). As dimensões escolhidas devem, obrigatoriamente, ser diferentes do 2 x 4 usado na implementação de referência.

Pesquisa sobre Código de Hamming

O Código de Hamming, criado por Richard Hamming em 1950, é um método de detecção e correção de erros baseado em blocos (assim como a paridade bidimensional). Embora tenha sido criado há quase 70 anos, esse método ainda é bastante utilizado em diversas tecnologias atuais (como em memórias com verificação de integridade).

O grupo deverá conduzir uma pesquisa sobre esse método, usando quaisquer recursos bibliográficos que julgar adequados (e.g., livros, Internet). Ao final desse estudo, o grupo deve:

• Entender como funciona o método.
• Entender quais são os parâmetros do método.
• Entender como funcionam os algoritmos de codificação e decodificação do método.

Implementação do Código de Hamming

Após a pesquisa, o grupo deverá proceder à implementação do método sobre o template das implementações de referência. Assim como no caso da paridade bidimensional, o grupo deverá realizar três implementações com diferentes quantidades de bits de paridade por bloco (ou uma parametrizável). Note que, nesse caso, obrigatoriamente, uma das implementações deve ser a do Hamming(7,4), ou seja, a que gera blocos de 7 bits, sendo 4 bits de dados e 7 - 4 = 3 de paridade.

Avaliação

Com base nas implementações realizadas e nas de referência fornecidas com essa especificação, o grupo deverá proceder à fase de avaliação dos métodos. Nessa fase, o grupo deverá realizar diversas execuções das várias implementações, variando parâmetros como:

• Probabilidade de inserção de erros em cada bit.
• Tamanho do pacote gerado.

O número de repetições em cada execução é de escolha do grupo, mas deverá ser de, ao menos, 1000. Mais repetições fazem com que a execução seja mais demorada, mas geram amostras mais representativas estatisticamente (lembre-se, há aleatoriedade envolvida nessas execuções).

Os resultados das execuções devem ser documentados na forma de tabelas e/ou gráficos a serem incluídos no relatório e na apresentação do trabalho. Além de documentar os resultados, é fundamental que o grupo analise os resultados obtidos, tirando conclusões. Dentre as perguntas que se deseja responder com essa avaliação estão:

• Como os diferentes parâmetros afetam a eficiência dos métodos implementados?
• O quão eficazes esses métodos são em relação a uma solução sem utilização de mecanismos de codificação?
• Qual método (paridade bidimensional ou Codificação de Hamming) foi mais eficiente em geral?
• É possível estabelecer uma relação entre o percentual de overhead introduzido (i.e., o quanto o pacote cresce com a adição de paridade) e a taxa de erro de bits resultante para cada um dos dois métodos?

Relatório

O relatório deverá documentar o desenvolvimento do trabalho realizado pelo grupo. Isso inclui uma explicação sobre o funcionamento do Código de Hamming, uma breve documentação das implementações desenvolvidas (e.g., funções criadas, estruturas de dados usadas, abstrações), a listagem dos parâmetros escolhidos para a Paridade Bidimensional e para o Código de Hamming, a metodologia usada na avaliação e seus resultados.

Como citado anteriormente, é fundamental que a avaliação inclua uma análise crítica dos resultados por parte do grupo. Assim, sugere-se que o relatório contemple as respostas (justificadas) para as perguntas apresentadas na seção anterior.

Note que, caso o grupo tenha optado por uma linguagem de programação diferente de Python ou C, o relatório deverá conter uma descrição mais detalhada dos aspectos de implementação, incluindo a linguagem utilizada, instruções de compilação/execução e descrição de classes/módulos principais.

Requisitos e Restrições

Embora a parte de implementação do trabalho possa ser feita em qualquer linguagem, algumas restrições devem ser observadas:

• Os códigos codificação e decodificação deverão ser de autoria dos membros do grupo, sem que se recorra à trechos de códigos de terceiros ou bibliotecas que implementem total ou parcialmente as funcionalidades aqui listadas (funções/métodos de manipulações básicas da linguagem escolhida podem ser utilizadas).
• O código final deve ser compilável/executável sem a necessidade de bibliotecas, frameworks ou ferramentas pagas.

É importante que as implementações se concentrem exclusivamente nas rotinas de codificação e decodificação, sem alteração do funcionamento do restante do código (i.e., interface com usuário e restante da simulação das transmissões). O grupo pode criar funções/métodos/classes auxiliares, se achar conveniente, mas as demais partes do template não devem ter sua funcionalidade modificada.

O relatório é de formato livre, sem limites inferiores ou superiores de páginas. Apenas como um guia geral, 8 páginas devem ser suficientes (embora não necessárias) para contemplar todos os itens listados nessa especificação.

Os grupos poderão ser formados com no mínimo 2 e no máximo 5 alunos.

Apresentação

Como parte da avaliação, o grupo deverá realizar uma apresentação do trabalho desenvolvido para o restante da turma durante o horário da aula em data a ser combinada com o professor posteriormente. A apresentação deverá ser realizada por todos os integrantes e contemplar os seguintes itens:

• Explicação do funcionamento do Código de Hamming, conforme estudado pelo grupo.
• Visão geral das implementações realizadas.
• Exemplo de execução das implementações realizadas.
• Parâmetros selecionados.
• Resultados encontrados e conclusões.

O tempo máximo de apresentação será definido juntamente com a data exata da apresentação. A apresentação poderá ser baseada em slides ou não, de acordo com decisão de cada grupo.

Critério de Avaliação

Cada trabalho receberá uma nota variando de 0 a 10. Esta pontuação será dividida nas seguintes proporções:

1. Até 2,0 pontos para a implementação da paridade bidimensional (três versões ou versão parametrizada), dos quais:
   1. Até 0,5 ponto para a rotina de codificação.
   2. Até 1,0 ponto para a rotina de decodificação.
   3. Até 0,5 ponto a existência e qualidade de comentários ao longo do código.
2. Até 3,0 pontos para a implementação do Código de Hamming (três versões ou versão parametrizada), dos quais:
   1. Até 1,0 ponto para a rotina de codificação.
   2. Até 1,5 pontos para a rotina de decodificação.
   3. Até 0,5 ponto a existência e qualidade de comentários ao longo do código.
3. Até 1,5 pontos para a apresentação.
4. Até 3,5 pontos para o relatório, dos quais:
   1. Até 2,0 pontos para a explicação do funcionamento do Código de Hamming.
   2. Até 1,0 ponto para a avaliação e conclusões.
   3. Até 0,5 ponto para a documentação dos demais aspectos do trabalho.

As implementações serão avaliadas apenas em relação à correção do código e aderência a esta especificação. Não haverá pontuação associada ao desempenho/eficiência da implementação.

Além da pontuação básica, cada grupo poderá fazer jus aos seguintes pontos extras:

1. Até 1,0 ponto para a pesquisa e descrição do método de Código Convolucional utilizado no IEEE 802.11g.
2. Até 1,0 ponto para a implementação do método de Código Convolucional utilizado no IEEE 802.11g.
3. Até 1,0 ponto para a inclusão de avaliação do método de Código Convolucional utilizado no IEEE 802.11g no relatório e na apresentação.

Esses pontos extras serão somados à pontuação total do trabalho, fazendo com que o trabalho possa valer até 13 pontos. Como o trabalho vale 20% da nota final da disciplina, esses três pontos extras no trabalho equivalem a 6 décimos extras na média final.

Entrega

A data limite para a entrega do trabalho está disponível no calendário da página da disciplina. Os grupos devem ficar atentos a potenciais mudanças nessa data ao longo do período. A entrega deverá ser realizada por e-mail, através do endereço dpassos@ic.uff.br. O e-mail deverá conter:

• Identificador do trabalho (e.g., “Trabalho de Redes II”).
• Lista dos integrantes do grupo.
• Código fonte das implementações.
• Instruções de compilação/execução/uso da implementação (se pertinente).
• Relatório.

Serão aceitos, sem penalidade, e-mails enviados até as 19:59 da data limite (i.e., até o horário da aula). Os e-mails de entrega de trabalho terão seus recebimentos devidamente confirmados. É responsabilidade do grupo garantir que o trabalho seja recebido, aguardando pela confirmação e reenviando a mensagem caso não a recebam em tempo razoável. Em caso de dúvidas ou correções relacionadas a esta especificação, também é responsabilidade de cada grupo entrar em contato (seja pessoalmente, ou através do mesmo endereço de e-mail) requisitando esclarecimentos dentro do prazo de entrega do trabalho.

Uma vez entregue o trabalho, não serão aceitas alterações (nem inclusões, nem remoções) na lista de integrantes do grupo em nenhuma hipótese. Por isso, sugere-se atenção no momento do envio da mensagem para que a lista contenha todos os integrantes do grupo.