매우 높은 비버스트 오류에 대한 알고리즘은 무엇입니까?
https://stackoverflow.com/questions/603727
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
오류율이 매우 높은 바이너리 스트림이 있습니다.오류율은 50%이며 각 비트가 반전될 확률이 50%라는 의미입니다.오류는 갑자기 발생하지 않고 완전히 무작위이므로 리드-솔로몬 코드는 제대로 작동하지 않습니다.
스트림에 어떤 체계나 알고리즘을 적용해야 합니까?나는 오버 헤드에 전혀 관심이 없습니다.
이것은 모두 이론적인 것이므로 스트림의 오류를 줄일 수 있는지 물어볼 필요가 없습니다.
편집하다
불가능하다고 말하지 마십시오. 첫 번째 대답은 가능하다는 것을 알려줍니다. 시끄러운 채널 코딩 정리.
해결책
시끄러운 채널 코딩 정리는 실제로 채널의 섀넌 용량을 달성 할 수 있다고 말합니다. 그렇습니다 ~ 아니다 채널에 0이 아닌 용량이 있다고 가정 해 봅시다!
만약 너라면 무작위 화 채널의 비트의 100%, 50%는 변하지 않으므로 비트의 무작위 50% 만 뒤집습니다. 해당 채널을 통해 데이터를 보낼 수 없다는 것은 분명해야합니다. Shannon 용량은 0입니다.
다른 팁
오류율이 50%인 경우 기본적으로 임의의 노이즈가 아닌가? 내 말은, 단 한 번만 전송하려고 노력하는 것을 고려하십시오. 당신이 보내는 경우 무한 오른쪽 비트의 스트림, 50% 오류율은 오른쪽 비트가 1 또는 0이든 반 1과 반 0을 얻을 수 있습니다.
실제로 50% 미만인 경우 (예 : 비트의 50%가 "Flipped"대신 "무작위"가 될 것입니다) 데이터를 반복 할 수 있습니다. 각 비트를 128 번 전송하고 각 100 비트마다 더 많은 것을 얻을 수 있습니다. 받았다. 그것은 모든 솔루션에서 수학적이 아니라 크게 비효율적이며 코드 간단한 코드입니다. :)
리드-솔로몬 오류 수정의 요점은 대부분의 실제 오류가 버스트에서 발생한다는 것입니다. 오류가 완전히 무작위 인 경우, 즉 Poisson Distributed가되면, 수학적으로 효율적인 방식으로 간단하고 효율적인 방식으로 스트림에 중복성을 추가하면 작동합니다. 당신이 볼 수있는 한 가지는 숨겨진 Markov 모델입니다. 격자 코드. 이것은 기본적으로 중복성을 추가하는 수학적으로 효율적인 방법입니다.
또한, 시끄러운 채널 코딩 정리. 엄밀히 말하면 디지털 데이터에는 적용되지 않지만 이러한 비트 소스가 아날로그 프로세스이거나 비트를 모델링 할 수있는 경우 마치 그들은 아날로그 과정의 결과였으며, 당신이 할 수있는 최선이 무엇인지에 대한 통찰력을 줄 수 있습니다. 이렇게하면 수학적으로 가능한 것보다 더 잘하는 시간을 낭비하지 못하게됩니다.
채널이 50% 실제 노이즈 속도에 접근함에 따라 더 이상 정보를 전혀 전송할 수 없습니다. Jon Skeet의 답변을 위해 오류율이 50% 미만인 경우 의도 된 데이터의 더 긴 버스트를 중복적이고 통계적으로 원래 가치에 대한 신뢰 수준을 검토하여 데이터를 얻을 수 있습니다. 주어진 길이에 필요한 버스트 길이와 신뢰도는 노이즈의 특성에 따라 도출됩니다. 그러나 여기서 수행하는 일은 전송 된 스트림의 순 신호 대 노이즈 비율을 향상시키기 위해 데이터 속도를 효과적으로 낮추는 것입니다.
귀하의 질문에서, 당신은 이것을 옵션으로 배제했을 수도 있지만, 더 나은 인코딩 체계는 데이터 스트림 자체의 상대적 존재 (또는 그렇지 않은)를 기반으로 할 수 있습니다. 다시 말해, 이진을 전송하려면 .... 1/0의 교대 스트림을 보냅니다. 0을 보내려면 아무것도 보내거나 일정한 레벨을 보내십시오. 아이디어는 무엇이든 보내는 것이 하나의 상태를 나타내며 다른 상태를 나타내는 것 (그리고 수신)을 나타내는 것입니다. 이것은 효과적으로 유형과 비슷합니다 바이폴라 인코딩 데이터의.
오류율이 50%인 경우 비트 스트림은 무작위이며 원래 비트 스트림과 상관관계가 없습니다.이는 완전히 무작위인 비트 스트림으로 스트림을 XOR하는 것과 같으며 결과는 완전히 무작위입니다.그리고 그것에 대해 당신이 할 수 있는 일은 아무것도 없습니다.
모든 계획이 작동하려면 반전율이 50% 미만이어야 합니다.물론 50% 이상일 수도 있지만 먼저 스트림을 반전시킨 다음 오류율이 50% 미만인 것처럼 처리할 수 있습니다.
오류가 완전히 무작위적이고 매우 빈번한 경우(예:비트의 25%가 반전됨) 강력한 오류 감지 방식을 찾는 것은 매우 어렵습니다.상당한 양의 중복성을 추가해야 합니다.
터보 코드를 살펴 보셨습니까?
- Markusq
도! 50% 무작위로 50%를 뒤집어 놓은 것으로 잘못 읽었습니다.
만약에 바로 그거죠 비트의 50%가 주어진 전송에서 뒤집어지며, 각 비트가 50% 확률로 뒤집히지 않고 두 비트의 전송을 보내서 약간의 정보를 보낼 수 있습니다. 수신 된 코드 워드의 첫 번째 비트가 1이면 다른 비트는 플랫링되지 않습니다.
