Qual algoritmo para extremamente elevado não estourar erros?

Question

Eu tenho um fluxo binário que tem uma elevada taxa de erro. A taxa de erro é 50% o que significa que cada bit tem uma probabilidade de 50% de ser invertida. O erro não ocorre em rajadas e é completamente aleatória, e códigos Reed-Solomon não iria funcionar bem.

Qual esquema ou algoritmo que eu deveria aplicar para o fluxo? Eu não me importo sobre a sobrecarga em tudo.

Isso tudo é teórico, por isso não há sentido em perguntar se eu poderia apenas reduzir o erro do fluxo.

Editar

Não diga que não é possível, a primeira resposta que lhe diga que é possível com canal barulhento codificação teorema.

Answer 1

A codificação teorema noisy-canal diz que você pode realmente atingir a capacidade de Shannon para o canal. Ele faz não dizem que o canal tem capacidade diferente de zero!

Se você Randomize 100% dos bits no canal, 50% deles não serão alterados, assim você só virar uma aleatória de 50% dos bits. Deveria ser óbvio que você não pode enviar dados através de um tal canal -. Sua capacidade de Shannon é zero

Answer 2

Se a taxa de erro é de 50%, então isso é o ruído basicamente aleatória não é? Quero dizer, considere apenas tentando transmitir um único bit. Se você enviar um infinito fluxo do bit direita, com uma taxa de erro de 50% você vai ter meio 1s e 0s metade se o bit direito é 1 ou 0.

Se ele é realmente menos de 50% (por exemplo, 50% dos bits será "aleatório" em vez de "virada"), então você poderia simplesmente repetir os dados - transmitir cada bit 128 vezes e trabalhar para fora o que você receber mais por cada um 100 bits recebidos. Esse é o código simples de, altamente ineficiente, não matemática em tudo solução:)

Answer 3

Bem, todo o ponto de correção de erros Reed-Solomon é que a maioria dos erros do mundo real ocorrer em rajadas, para que intercalam e de-intercalam os dados. Se os seus erros são completamente aleatórios, ou seja Poisson distribuído, em seguida, apenas adicionando a redundância para o fluxo em um simples, forma matematicamente eficiente irá funcionar. Uma coisa que você poderia olhar para algum tipo de modelo de Markov oculto, como treliça código. Este é basicamente apenas uma maneira matematicamente eficiente de adicionar redundância.

Além disso, ter um olhar para o codificação teorema canal barulhento. Estritamente falando, ele doesn 't aplicam a dados digitais, mas se sua fonte desses bits é algum processo analógico, ou se você pode modelar seus bits como se que foram o resultado de algum processo analógico, que poderia lhe dar algumas dicas em que o melhor que você poderia fazer poderia ser. Isto impedi-lo de perder tempo tentando fazer melhor do que é matematicamente possível.

Answer 4

Como o canal se aproxima de 50% taxa real de ruído, já não se torna possível transmitir qualquer tipo de informação. Para a resposta de Jon Skeet, se a taxa de erro é nada menos do que o ruído de 50%, então você pode obter dados através fazendo mais longas rajadas de dados destinados de forma redundante e estatisticamente olhando para o resultado a algum nível de confiança no valor original. Os níveis de comprimento e de confiança estourar necessários para um determinado comprimento, então, ser derivado com base em uma caracterização do ruído. Entenda, no entanto, o que você está fazendo aqui é efetivamente reduzindo a taxa de dados para melhorar o sinal net-ruído do fluxo transmitido.

Na sua pergunta, você pode ter governado isso como uma opção, mas um esquema melhor codificação pode basear-se na existência relativa (ou não) de transmitir-se os dados. Em outras palavras, para transmitir um binário .... enviar um fluxo alternado de 1/0. Para enviar um zero, envie nada ou talvez envie um nível constante. A ideia é que o envio (e receber) nada representa um estado e enviar (e receber) nada representa o outro estado. Isso equivaleria a se assemelhar a um tipo de bipolar codificação dos dados.

Answer 5

Se a sua taxa de erro é de 50% do fluxo de bits é aleatória e não tem correlação com o fluxo de bits original. É como você está XORing o fluxo com um fluxo de bits completamente aleatória, e o resultado é completamente aleatório. E não há nada que você possa fazer sobre isso.

A taxa de aleta deve ser inferior a 50%, a fim de qualquer esquema de trabalho. Claro, poderia ser acima de 50%, mas, em seguida, você pode primeiro invertido o fluxo e, em seguida, processá-lo como se a taxa de erro foi abaixo de 50%.

Se os erros são completamente aleatório e muito frequente (por exemplo, 25% dos pedaços são invertidos), é muito difícil chegar a um esquema de detecção de erro robusto. Você precisa adicionar uma quantidade significativa de redundância.

Answer 6

Você já olhou nos códigos turbo?

- MarkusQ

Doh! Eu descaracterizou que 50% randomizado, não 50% capotou.

Answer 7

Se exatamente 50% dos bits são invertidos em qualquer transmissão, em vez de cada bit que está sendo capotou com 50% de probabilidade, você pode enviar um pouco de informação através do envio de uma transmissão de dois bits - -. enviar um 0 como 00 e um 1 como 01. Se o primeiro bit da palavra de código recebida é 1, então o outro bit é unflipped