손실이 있는 단방향 채널에서 데이터를 인코딩하는 데 어떤 기술을 사용할 수 있습니까?

StackOverflow https://stackoverflow.com/questions/1231489

  •  22-07-2019
  •  | 
  •  

문제

다음과 같은 의사소통 채널이 있다고 상상해 보십시오. 본질적으로 손실이 있는 그리고 단방향.즉, 제거할 수 없는 고유한 노이즈가 있어 무작위 비트가 토글됩니다.또한 이것이 일방향이라고 상상해 보십시오. 재전송을 요청할 수 없습니다.

하지만 상관없이 데이터를 보내야 합니다.어떤 기술을 사용하여 보낼 수 있나요? 숫자 그리고 텍스트 그 채널에서요?

  1. 임의의 비트를 조작하더라도 여전히 원본에 가까운 값으로 해석될 수 있도록 숫자를 인코딩하는 것이 가능합니까(손실이 많은 전송)?

  2. 문자열(ASCII 등)을 보낼 수 있는 방법이 있나요? 무손실 패션?

이것은 단지 재미를 위한 것입니다.모스 부호나 매우 낮은 주파수의 이진 통신을 사용할 수 있다는 것을 알고 있습니다.오류를 감지하고 재시도하기 위한 패리티 비트와 체크섬에 대해 알고 있습니다.아날로그 신호를 사용하는 것이 나을 수도 있다는 것을 알고 있습니다.손실이 있는 채널을 통해 이 내용을 보내는 흥미로운 컴퓨터 과학 기술이 있는지 궁금합니다.

도움이 되었습니까?

해결책

손실이 있는 채널에 대해 제공하지 않은 일부 세부 정보에 따라 먼저 다음을 사용하는 것이 좋습니다. 그레이 코드 단일 비트 오류로 인해 작은 차이가 발생하는지 확인하고(손실 전송 시 손실 완화에 대한 요구 사항을 충족하기 위해) 결과 스트림을 일부 "무손실"(==시도하다 무손실 ;-) 인코딩.

리드솔로몬 노이즈 에피소드가 작은 폭발(예: 단일 바이트 내에서 여러 비트 실수)로 발생하기 쉬운 경우 그 변형이 특히 좋습니다. 이는 그레이 코딩과 잘 상호 운용되어야 합니다(다중 비트 실수는 "손실"의 킬러이므로). 완화" 측면은 회선의 단일 비트 오류에 대해 적절하게 저하되도록 설계되었습니다.이는 R-S가 본질적으로 블록 방식이고 R-S의 관점에서 볼 때 한 블록 내의 여러 오류는 기본적으로 단일 오류와 동일하기 때문입니다.

R-S는 오류가 많은 경우 특히 훌륭합니다. 삭제 -- 간단히 말해서, 삭제는 전송 중에 훼손되었을 가능성이 가장 높은 기호이지만, 이에 대해 귀하는 그것이 훼손되었다는 중요한 사실을 알고 있습니다.물리적 계층은 설계 방식에 따라 종종 해당 사실에 대한 힌트를 가질 수 있으며, 상위 계층에 이를 알릴 수 있는 방법이 있다면 이는 중요한 도움이 될 수 있습니다.삭제에 대해 조금 설명하겠습니다...:

간단한 예를 들어 0이 -1V 레벨로 전송되고 1이 +1V 레벨로 전송되지만(일부 기준파 작성) 노이즈가 있다고 가정해 보겠습니다(물리적 노이즈는 종종 잘 모델링될 수 있습니다. 유능한 통신 엔지니어;-);노이즈 모델에 따라 디코딩은 -0.7V 이하가 0비트로 간주되고, +0.7V 이상이 1비트로 간주되며, 그 사이의 모든 것은 삭제로 간주됩니다. 즉, 상위 계층에 전달됩니다. 문제의 비트는 전송 중에 손상되었을 수 있으므로 무시해야 합니다.(나는 때때로 추상화가 통제되고 설계된 방식으로 "누출"되어야 한다는 내 논문의 한 예로서 이것을 제시합니다.Spolsky의 Martelli의 추론 누출 추상화의 법칙!-).

주어진 중복 비율을 가진 R-S 코드는 알려지지 않은 오류를 수정하는 것보다 삭제 수정(디코더에 전달되는 오류)에 약 두 배 더 효과적일 수 있습니다. 두 측면을 혼합하여 일부 삭제를 수정하는 것도 가능합니다. 다른 경우에는 알려지지 않은 오류가 있습니다.

맨 위에 있는 체리와 같이 사용자 정의 R-S 코드는 삭제 및 감지되지 않은 오류(포함) 측면에서 물리적 채널 특성의 정확한 모델이 제공되면 수정되지 않은 오류의 확률을 필요한 임계값 θ 미만으로 줄이기 위해 (합리적으로 쉽게) 설계되고 맞춤화될 수 있습니다. 확률과 폭발성 모두).

나는 실제로 이 전체 영역을 "컴퓨터 과학" 영역이라고 부르지 않을 것입니다.제가 졸업했을 때(MSEE, 30년 전) 저는 칩 설계, 시스템 설계, 고급 무선 시스템 등을 선호하여 "CS" 분야를 대부분 피하려고 노력했습니다. 이미 실용적인 엔지니어링 사용 영역 내에 있었습니다. ;-) 꽤 좋습니다.

그리고 한 세대 동안 상황이 그다지 많이 변하지 않았음을 확인하기 위해 다음을 수행합니다.내 딸은 방금 통신 공학 석사 학위를 받았습니다(엄격히 고급 무선 시스템에 중점을 두고 있습니다). 그녀는 어떤 심각한 프로그램, 알고리즘 또는 데이터 구조도 설계할 수 없습니다(C 및 Java 필수 과정에서는 훌륭했지만, 해당 과정이나 커리큘럼의 다른 부분에는 CS 깊이가 전혀 없었습니다. 그녀의 일상 업무 언어는 다음과 같습니다. MATLAB...!-) -- 하지만 그녀는 내가 배운 것보다 정보와 코딩 이론에 대해 더 많이 알고 있습니다. ~ 전에 모든 박사 과정 연구(그녀는 박사 과정을 계속하고 있지만 아직 시작되지 않았습니다).

그래서 나는 이 분야가 CS-y보다 EE-y에 더 가깝다고 주장합니다(물론 경계는 항상 모호합니다. 몇 년 동안 칩을 설계한 후 우연히 SW 전문가가 되었다는 사실을 확인하세요. 많은 동시대 사람들도 마찬가지였습니다. ;-).

다른 팁

이 질문의 주제는 코딩 이론.

아마도 더 잘 알려진 방법 중 하나는 다음을 사용하는 것입니다. 해밍 코드.대규모 오류를 수정하는 최선의 방법은 아닐 수도 있지만 이해하기는 매우 간단합니다.

어느 하나 터보 코드 또는 저밀도 패리티 검사 코드 일반 데이터의 경우 Shannon 한계에 접근하는 데 가장 가깝기 때문에 Wikipedia를 참조하세요.

당신이 사용할 수있는 리드솔로몬 코드.

또한 참조하십시오 슬라이딩 윈도우 프로토콜 (TCP에서 사용됨)

여기에는 재정렬되거나 완전히 손실되는 패킷 처리가 포함되지만 이는 문제 정의의 일부가 아닙니다.

Alex Martelli가 말했듯이 세상에는 수많은 코딩 이론이 있지만 Reed-Solomon 코드가 확실히 적합합니다.실제로 뭔가를 만들고 싶다면, 짐 플랭크 을 썼다 리드 솔로몬 코딩에 대한 좋은 튜토리얼.Plank는 코딩에 대한 전문적인 관심을 가지고 있으며 이를 뒷받침할 많은 실무적 전문 지식을 갖추고 있습니다.

나는 이러한 제안 중 일부를 선택한 다음 동일한 데이터를 여러 번 보냅니다.이렇게 하면 스트림의 여러 지점에서 다양한 오류가 발생하기를 기대할 수 있으며 원하는 숫자를 훨씬 더 쉽게 추론할 수 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top