잡음이 많은 비트 스트림을 읽는 이중화 알고리즘

Question

손실이 많은 비트 스트림을 읽었으므로 최대한 많은 사용 가능한 데이터를 복구해야합니다. 0의 자리에 1이 있고 1의 자리에 0이있을 수 있지만 정확도는 아마도 80 %를 넘을 것입니다.

알고리즘이 누락되거나 너무 많은 비트를 보충 할 수 있다면 보너스가됩니다.

내가 읽는 소스는 잡음 (아날로그 FFT를 통한 마이크)이며 읽기 타이밍은 컴퓨터 속도에 따라 다를 수 있습니다.

CD-ROM에서 사용되는 알고리즘에 대해 3 장에서 읽은 것을 기억하십니까? 레이어, 그래서 여러 레이어를 사용하여 추측하고있어 좋은 옵션입니다. 나는 세부 사항을 기억하지 않는다. 그래서 누군가가 위대한 것이 될 몇 가지 아이디어를 공유 할 수 있다면! :)

편집 : 추가 샘플 데이터

 
Best case data: 
in: 0000010101000010110100101101100111000000100100101101100111000000100100001100000010000101110101001101100111000101110000001001111011001100110000001001100111011110110101011100111011000100110000001000010111 
out: 0010101000010110100101101100111000000100100101101100111000000100100001100000010000101110101001101100111000101110000001001111011001100110000001001100111011110110101011100111011000100110000001000010111011 

Bade case (timing is off, samples are missing): 
out: 00101010000101101001011011001110000001001001011011001110000001001000011000000100001011101010011011001 
in: 00111101001011111110010010111111011110000010010000111000011101001101111110000110111011110111111111101 

Edit2가

: 나는 데이터가 전송되는 설정 제어 할 수 있어요. 현재 간단한 XOR 검사를 구현하려고 시도하고 있습니다 (충분하지는 않지만).

Answer 1

forward error correction을 사용해야합니다. XOR 패리티 검사는 오류가 발생할 때만 감지합니다. 간단한 오류 수정 알고리즘은 데이터의 각 청크를 여러 번 (적어도 3 회) 보내고 다수결을 내리는 것입니다.

알고리즘의 선택은 여러 가지 요인에 따라 달라집니다

:

• 채널 활용
• 오류 유형 (무료 많은 시간이 있다면, 당신은 효율적인 코딩이 필요하지 않습니다) : 나쁜 비트는 무작위입니다 간격 또는 보통
• 처리 시간 연속으로 발생합니까 : 데이터 전송이 내가 제대로 이해하면

Answer 2

은 가능성을 많이 볼 수 있습니다 :이 변경된 비트와 함께 당신을 도울 수 있지만, 모든 비트를 가질 때마다 확인 부적합 할 수 http://en.wikipedia.org/wiki/Error_detection_and_correction

.

결국에는 간단한 코드를 몇 줄 이상 사용하게 될 것입니다.

Answer 3

빨리 할 필요가있는 경우 코드의 복잡성이 제한됩니다, 당신은 두 가지 요구 사항이 :

1. 신호를 사운드로 변조 한 다음이를 복조하십시오.
2. 채널이 신뢰할 수 없으므로 오류 수정을 적용하십시오.

변조 및 복조는 정보를 변조하기 위해 several ways과 함께 잘 알려진 응용 프로그램입니다.

2 번 오류 수정도 잘 알려져 있으며 여러 가지 가능성이 있습니다. 적용 할 수있는 것은 오류율과 양면 작업이있어 ​​재전송을 요청할 수 있는지 여부에 따라 다릅니다. 괜찮은 품질을 가지고 있고 재전송을 요청할 수 있다면 TCP가 사용하는 것과 같은 접근법을 탐구 해 볼 가치가 있습니다.

그렇지 않으면 CDROM에서 사용되는 것과 같은 오류 검색 및 오류 수정 알고리즘을 사용해야합니다. 수행 변조/복조없이 재전송 가능성을 갖는 주석

후

편집 문제를 좁힌 다. 타이밍 문제가있는 경우 발신자와 자동으로 다시 동기화하고 신호 대 잡음비를 높이는 방법이 있으므로 기존 (드) 변조 방법을 읽는 것이 좋습니다.

핵심 문제로; 오류 수정 오류를 감지 할 수 있으려면 출력 스트림에 패리티 비트를 추가해야합니다. 앞으로 오류 정정 기사로 시작하는 @Justin은 매우 간단하지만 여전히 강력 해 보이는 구성표가 Hamming(7,4) 구성표임을 시사합니다.