Quais as técnicas que você pode usar para codificar dados em um canal unidirecional com perdas?

Question

Imagine que você tem um canal de comunicação que é inerentemente perdas e one-way. Isto é, existe algum ruído inerente que é impossível removê que faz com que, por exemplo, bits aleatórios para ser alternado. Imagine também que é uma maneira -. você não pode pedir a retransmissão

Mas você precisa enviar dados sobre ele independentemente. Quais as técnicas que você pode usar para enviar números e texto ao longo desse canal?

1. É possível números codificar de forma que pouco aleatório, mesmo com girando eles ainda podem ser interpretados como valores perto do original ( lossy transmittion)?

2. Existe uma maneira para enviar uma cadeia de caracteres (ASCII, por exemplo) em um lossless moda?

Isto é apenas para diversão. Eu sei que você pode usar o código morse ou qualquer comunicação muito baixo binário frequência. Eu sei sobre bits de paridade e somas de verificação para detectar erros e tentar novamente. Eu sei que você também pode usar um sinal analógico. Só estou curioso se existem técnicas computer-sciency interessantes para enviar este material através de um canal com perdas.

Answer 1

Dependendo alguns detalhes que você não fornecer sobre o seu canal com perdas, eu recomendaria, primeiro usando um código de Gray para garantir que os erros de um único bit resultar em pequenas diferenças (para cobrir o seu desejo de mitigação da perda na transmissão lossy), e depois, possivelmente, também codifica o fluxo resultante com algum "sem perdas" (== tentativas ser perda de menos ;-) codificação.

Reed-Solomon e suas variantes são particularmente bom se o seu episódios de ruído são propensos a ocorrer em pequenas rajadas (erros de vários bits dentro de, digamos, um único byte), que deve interoperar bem com Gray codificação (desde erros multi-bit são os assassinos para o aspecto "perda de mitigação" de Gray, projetado para degradar normalmente para erros de bit único no fio). Isso porque R-S é intrinsecamente um esquema de bloco, e vários erros dentro de um bloco são basicamente o mesmo que um único erro em que, do ponto de vista do R-S; -)

.

RS é particularmente impressionante, se muitos dos erros são rasuras - para colocá-lo simplesmente , um apagamento é um símbolo que foi provavelmente mutilado na transmissão, mas para que você sabe o fato crucial que foi mutilado. A camada física, dependendo de como ele é projetado, pode muitas vezes têm dicas sobre esse fato, e se há uma maneira para que possa informar as camadas mais altas, que podem ser de ajuda crucial. Deixe-me explicar rasuras um pouco ...:

dizer para um exemplo simplificado que um 0 é enviado como um nível de -1 volt e um 1 é enviado como um nível de 1 volt (WRT alguns onda de referência), mas não há ruído (ruído física pode muitas vezes ser bem modelado, pergunte a qualquer engenheiro de comunicação competente ;-); dependendo do modelo de ruído a descodificação pode ser qualquer coisa que -0,7 V e para baixo é considerado um bit 0, nada 0,7 V ou superior é considerada um bit 1, nada no meio é considerado uma rasura, isto é, a camada superior é contada que o bit em questão provavelmente foi mutilado em transmissão e deve ser desconsiderada. (Às vezes eu dar isso como um exemplo de minha tese de que, por vezes, abstrações DEVE "vazar" - de uma forma controlada e arquitetada: o corolário Martelli para Spolsky de Lei de Leaky Abstrações -!).

Um código RS com qualquer relação de redundância pode ser cerca de duas vezes mais eficaz para corrigir rasuras (erros do descodificador é contada sobre) como pode ser a corrigir erros de outra maneira desconhecidos - também é possível misturar ambos os aspectos, corrigindo tanto algumas rasuras e alguns erros de outra maneira desconhecidos.

Como a cereja no topo, códigos personalizados RS pode ser (razoavelmente fácil) projetado e adaptado para reduzir a probabilidade de erros não corrigidos para abaixo de qualquer limiar necessário q dado um modelo preciso das características do canal físico em termos de rasuras e sem ser detectado erros (incluindo tanto a probabilidade e burstiness).

Eu não chamaria toda esta área um "computador-sciency" um, na verdade: de volta quando me formei (MSEE, 30 anos atrás), eu estava principalmente tentando evitar coisas "CS" em favor de design de chips, sistema design, sistemas de rádio avançadas, & c -. ainda me ensinaram essas coisas (bem, o subconjunto que já estava dentro do reino do uso prático de engenharia ;-) muito bem

E, apenas para confirmar que as coisas não mudaram tanto assim em uma geração: a minha filha só tem seus MS em engenharia de telecomunicações (estritamente com foco em sistemas de rádio avançados) - ela não pode criar praticamente qualquer programa sério , algoritmo, ou estrutura de dados (embora ela fez muito bem nas disciplinas obrigatórias em C e Java, não havia absolutamente nenhuma profundidade CS nesses cursos, nem em outros lugares in seu currículo - sua linguagem diária de trabalho é Matlab ... -!) - mas ela sabe mais sobre informação e teoria do código do que eu já aprendi, e isso é antes qualquer estudo nível de doutorado (ela vai ficar para o seu doutoramento, mas que ainda não começou).

Então, eu reivindicar esses campos são mais EE-y de CS-y (embora, naturalmente, os limites estão sempre difusa - testemunha o fato de que depois de alguns anos projetar chips que acabou por ser um SW cara mais ou menos por acidente, e assim fiz um monte de meus contemporâneos; -).

Answer 2

Esta questão é objecto de teoria da codificação .

Answer 3

Provavelmente um dos métodos mais conhecidos é usar Hamming código . Pode não ser a melhor maneira de corrigir erros em grandes escalas, mas é incrivelmente simples de entender.

Answer 4

• Existe a redundante codificação usada em mídia óptica que lata recuperar-loss bit.
  • ECC também é usado em hard-discos e RAM
• TCP protocolo pode lidar com um monte de perda de dados com retransmissões.

Answer 5

De qualquer códigos turbo ou noreferrer de baixa densidade códigos de verificação de paridade para dados gerais, porque estes vêm mais próximo se aproximando do limite Shannon -. ver wikipedia

Answer 6

Você pode usar códigos Reed-Solomon .

Answer 7

Veja também a protocolo de janela deslizante (que é usado pelo TCP).

Embora isso inclui lidar com pacotes de ser re-ordenada ou totalmente perdido, que não fazia parte de sua definição do problema.

Answer 8

Como diz Alex Martelli, há muita teoria da codificação no mundo, mas códigos Reed-Solomon são definitivamente um ponto doce. Se você realmente deseja construir algo, Jim Plank escreveu um bom tutorial sobre Reed-Solomon codificação. Plank tem um interesse profissional na codificação com muita experiência prática para apoiá-la.

Answer 9

Gostaria de ir para algumas destas sugestões, seguido por vários envios dos mesmos dados. Então, de que maneira você pode esperar erros diferentes a serem introduzidas em diferentes pontos no fluxo, e você pode ser capaz de inferir o número desejado muito mais fácil.