인터넷은 어떻게 작동하나요? 2부

이번 강의/포스트에서는 네트워크에 대해 이야기하겠습니다.

비트, 신호 및 패킷 소개

전 세계 통신 네트워크를 통해 정보를 전달하고 교환할 수 있는 능력은 사람들이 일하고 즐기고 생활하는 방식에 혁명을 일으켰습니다. 세기가 바뀌면서 미국 국립공학학회(National Academy of Engineering)는 20세기에 사회적으로 가장 큰 영향을 미친 기술 20개를 나열했습니다. 이 목록에는 전기화, 자동차, 비행기 등 삶을 변화시키는 혁신이 포함되었습니다. 또한 이 책의 초점이 되는 기술 기반인 라디오, 텔레비전, 전화, 인터넷, 컴퓨터 등 네 가지 통신 기술도 포함되어 있습니다.

놀랍게도 인터넷은 20세기 후반에 개발되었기 때문에 13위에 그쳤으며 위원회는 인터넷의 가장 중요한 영향이 21세기에 발생할 것이라고 믿었습니다. 그 예측은 정확해 보입니다. 무선 네트워크와 모바일 장치의 확산, 소셜 네트워크의 증가, 언제 어디서나 통신이 상업과 사회적 연결을 변화시켰으며 심지어 사회적, 정치적 변화를 주도했습니다.

소통은 현대 생활의 기본입니다. 인터넷, 해당 애플리케이션, 네트워크로 연결된 모바일 장치가 없는 생활은 상상하기 어렵습니다. 2011년 초까지 전 세계적으로 50억 대 이상의 휴대 전화가 사용되었으며, 그 중 10억 대 이상이 "광대역" 연결이 가능했습니다. 이는 2011년 전기, 신발, 칫솔 또는 화장실을 사용하는 사람의 수를 초과한 것입니다!

목표

이 게시물/강좌(무엇을 부르든)는 통신 네트워크의 작동 방식을 설명하는 것을 목표로 합니다. 이는 두 가지 이유로 연구할 가치가 있습니다.

• 이러한 시스템에 사용되는 설계 원리와 분석 기술을 이해합니다.
• 기술적 아이디어가 컴퓨터 과학(CS) 및 전기 공학(EE)의 다른 분야와 관련이 있기 때문입니다. 이는 커뮤니케이션 시스템을 공부하는 것이 광범위하게 적용 가능한 개념을 배울 수 있는 좋은 방법이 됩니다.

MIT(Massachusetts Institute of Technology)에서는 2학년 학생들이 확률과 푸리에 급수에 대한 노출과 함께 이러한 과정을 수강합니다.

전통적으로 '낮은 수준의 통신'(단일 링크를 통해 정보가 이동하는 방식)은 EE 주제로 간주되었으며, '네트워킹'(여러 링크의 네트워크 구축)은 CS 주제로 간주되었습니다. 전통적인 디지털 커뮤니케이션 과정에서는 네트워크 구축을 거의 다루지 않으며, 컴퓨터 네트워크 과정에서는 물리적 링크를 통한 커뮤니케이션을 블랙박스로 취급합니다. 이 책은 두 측면에 대한 포괄적인 이해를 제공하여 이러한 격차를 해소하는 것을 목표로 합니다.

전송할 정보가 있는 소스부터 패킷(전송을 위해 분할된 메시지), 비트("0" 또는 "1"), 신호(아날로그 파형)까지 통신 시스템을 엔드 투 엔드로 다룹니다. 전선, 광섬유, 무선 또는 음파와 같은 링크를 통해 전송됩니다. 간단한 지점 간 링크, 여러 노드가 있는 공유 미디어, 더 큰 네트워크를 형성하기 위해 연결되는 대규모 멀티홉 네트워크 등 다양한 네트워크를 살펴보겠습니다.

테마

디지털 커뮤니케이션의 핵심 과제 세 가지는 신뢰성, 공유, 확장성입니다. 이 소개 섹션에서는 처음 두 가지에 중점을 둡니다.

신뢰할 수 있음

다양한 요인으로 인해 의사소통이 불안정해집니다. 독립적인 구성 요소 오류에 의존하여 신뢰할 수 없는 구성 요소에 대한 신뢰성을 달성하기 위해 중복성을 사용하는 신뢰성 향상 기술을 연구합니다.

주요 과제는 통신 품질을 저하시키는 소음, 간섭, 비트 오류, 패킷 손실(수정할 수 없는 오류, 대기열 오버플로 또는 링크/소프트웨어 오류로 인한)을 극복하는 것입니다.

신뢰성 외에도 속도도 중요합니다. 신뢰성 기술은 중복성을 사용하여 속도를 줄이는 경우가 많습니다. 많은 통신 시스템은 안정성과 속도의 균형을 유지합니다.

통신 속도는 1980년대 초 초당 킬로비트에서 오늘날 무선에서는 초당 100메가비트, 유선 링크에서는 초당 1~10기가비트로 급격히 증가했습니다.

오류 수정 코드 사용, 기호 간 간섭 처리, 재전송 프로토콜 및 내결함성 라우팅 등 통신이 신뢰할 수 없는 이유와 이를 해결하는 방법을 알아봅니다.

효율적인 공유

모든 노드 쌍에 대한 전용 링크는 엄청나게 비쌉니다. 나눔은 필수입니다. 지점간 링크 공유, 미디어 공유, 멀티홉 네트워크에 대해 공부하겠습니다.

매체 공유(이더넷, Wi-Fi, 셀룰러 네트워크 및 위성 네트워크 관련), 변조/복조(다른 주파수를 통해 전송), 매체 액세스 제어(MAC) 프로토콜(네트워크 노드 동작을 관리하는 규칙)에 대해 다룹니다. . 시간 공유(각 노드가 전용 시간 동안 전송)와 주파수 공유(대역폭 분할)에 대해 살펴보겠습니다. 그런 다음 많은 통신이 링크를 공유하고 스위치로 조정되는 멀티홉 네트워크로 넘어갑니다.

주요 질문에는 다중 통신이 네트워크를 공유하는 방법, 메시지가 네트워크를 통과하는 방법, 멀티홉 네트워크에서 안정적인 통신을 보장하는 방법이 포함됩니다.

공유 기술과 안정성 메커니즘이 네트워크 효율성을 결정합니다. 효율성은 주어진 요구 사항에 대한 비용을 최소화하거나 주어진 네트워크에 대한 "유용한 작업"(총 처리량, 처리량 변동 및 평균 지연/지연 시간)을 최대화하는 것으로 구성될 수 있습니다. 이 게시물은 처리량과 대기 시간에 중점을 둡니다.

확장성

확장성(대규모를 처리하는 네트워크 설계)이 중요합니다. 이 게시물에서는 이에 대해 간략하게 다루며 이후 강의를 위해 자세한 논의를 남겨둡니다.

개요 및 계획

수업은 소스, 비트, 신호, 패킷의 추상화의 네 부분으로 나누어 순서대로 학습합니다.

1. 소스: 정보, 엔트로피, 소스 코딩(데이터 압축), 허프만 코드, Lempel-Ziv-Welch 알고리즘의 기본부터 시작합니다.
2. 비트: 오류 수정 코드(선형 블록 코드 및 컨벌루션 코드)를 사용하여 비트 오류 극복을 해결합니다.
3. 신호: 변조/복조, 선형 시불변(LTI) 채널을 사용한 신호 왜곡 모델링, 시간/주파수 영역 표현, 채널/필터의 주파수 응답을 다룹니다.
4. 패킷: MAC 프로토콜을 사용한 매체 공유, 다중 홉 네트워크에서의 라우팅 및 안정적인 데이터 전송 프로토콜을 연구합니다.

정보, 엔트로피 및 소스 코드의 동기

Claude Shannon의 정보 이론(1940년대 후반에 개발됨)은 많은 기술 분야, 특히 통신 시스템과 네트워크를 변화시킨 획기적인 아이디어입니다. 이 장에서는 정보 이면의 직관을 소개하고 이를 수학적으로 정의하며 이를 데이터 소스의 속성인 엔트로피와 연결합니다.

이러한 개념은 통신이나 저장 전에 효율적인 데이터 압축을 가능하게 하여 왜곡 없이 원본 데이터를 복구할 수 있게 해줍니다. 핵심 아이디어는 데이터 소스의 각 기호를 원하는 속성을 가진 코드워드에 매핑하는 소스 코딩입니다. 메시지는 일련의 기호입니다. 우리의 초점은 손상되지 않은 전송에서 원본 메시지를 완벽하게 복구할 수 있는 무손실 소스 코딩입니다.

정보와 엔트로피

Hartley의 작업을 기반으로 Shannon은 정보가 애플리케이션이나 메시지 의미 체계와 관계없이 일반적으로 정의될 수 있다는 것을 깨달았습니다. 의사소통에는 발신자(S)가 여러 가능한 메시지 중 하나를 선택하여 수신자(R)에게 보내는 과정이 포함됩니다. 예를 들어 S는 영국 도착 경로를 나타낼 수 있습니다.

• 육로로 이동할 경우 "1"
• 바다로 가는 경우 "2"

각 선택의 가능성이 동일하다면(사전 지식 없음) 전달되는 정보는 1비트입니다. 이 비트는 선택을 인코딩할 수 있습니다. 1000개의 독립적인 이벤트를 1000비트로 인코딩할 수 있습니다.

사전 지식이 하나의 선택(예: 폭풍으로 인한 육지)에 대해 더 높은 확률을 제시하는 경우 확률이 낮은 메시지(바다)가 더 많은 정보를 전달합니다. 마찬가지로 1월 보스턴의 온도 75°F는 32°F보다 더 많은 정보를 제공합니다.

사건에 대한 정보는 확률(p)에 따라 달라집니다. 확률이 낮을수록(사건 발생 가능성이 낮을수록) 정보가 더 높다는 의미입니다.

정보의 정의

Hartley는 정보(I)를 다음과 같이 정의했습니다.

I = log(1/p) = -log(p) (2.1)

밑이 2인 로그를 사용하며, 정보의 단위는 비트입니다. 로그 함수는 가산성을 보장합니다. 두 개의 독립적인 사건 A와 B의 정보(확률 pA와 pB)가 합산됩니다.

IA IB = log(1/pA) log(1/pB) = log(1/(pA*pB)) = log(1/P(A 및 B))

예

엔트로피

엔트로피(H)는 상호 배타적인 일련의 이벤트에서 예상되는 정보를 수량화합니다. 이벤트 i에 확률 pi가 있는 경우:

H(p1, p2, ... pN) = Σ pi * log(1/pi) (2.2)

엔트로피는 비트 단위로 측정되며 평균 불확실성을 나타냅니다. 확률 p와 1-p를 갖는 두 개의 상호 배타적인 사건의 경우:

H(p, 1-p) = -p*log(p) - (1-p)*log(1-p) (2.3)

H(p)는 p = 1/2를 기준으로 대칭이며 p = 1/2에서 최대 1비트입니다. H(0) = H(1) = 0. 엔트로피는 항상 음수가 아니며 H(p1, p2, ... pN) ≤ log N입니다.

소스 코드

소스 코딩은 메시지를 효율적으로 인코딩합니다. 많은 메시지에는 표준 인코딩(ASCII, 이미지 픽셀, 오디오 샘플)이 있습니다. 고정 길이 인코딩으로 쉽게 조작할 수 있습니다.

그러나 이러한 인코딩은 비효율적일 수 있습니다. 영어 텍스트에서는 'e'가 'x'보다 더 자주 나타납니다. 'e'를 더 적은 비트로 인코딩하고 'x'를 더 많은 비트로 인코딩하면 평균 메시지 길이를 줄일 수 있습니다. 이는 정보 개념과 일치합니다. 즉, 빈도가 높은 기호(pi가 높음)는 더 적은 정보를 전달하고 더 적은 비트가 필요합니다.

코드는 정보를 비트 시퀀스로 매핑합니다. 코드워드는 코드의 비트 시퀀스입니다. 소스 코드는 인코딩된 메시지 길이를 정보 내용(엔트로피)에 맞춰 데이터를 압축하는 것을 목표로 합니다.

예: 1000개 등급(A, B, C, D)을 확률로 인코딩:

고정 길이 인코딩: 2비트/등급(총 2000비트). 디코딩은 간단하지만 비효율적입니다.

가변 길이 인코딩(예): A=10, B=0, C=110, D=111. 길이는 메시지에 따라 다릅니다. 디코딩에는 순차적 처리가 필요합니다. 이 예제 코드는 최적이 아닙니다.

얼마나 많은 압축이 가능합니까?

이상적으로 압축은 정보를 표현하는 데 필요한 비트만 사용합니다. 엔트로피(식 2.2)는 모호성을 방지하는 데 필요한 평균 비트 수에 대한 하한을 제공합니다. 더 적은 비트를 전송하면 수신자에서 해결되지 않은 선택이 발생합니다.

등급 예시에서 등급당 예상되는 정보는 1.626비트입니다. 1000개 등급을 인코딩하려면 평균 1626비트가 필요합니다. 예제 가변 길이 코드는 1667비트를 사용하므로 최적이 아닙니다. 등급의 인코딩 시퀀스는 압축을 향상시킬 수 있습니다.

좋은 코드를 찾는 것은 어렵습니다. 때로는 상황별 코드가 매우 효율적일 수 있습니다(예: 발신자와 수신자 모두 모든 소네트를 알고 있는 경우 단 8비트를 사용하여 셰익스피어 소네트를 인코딩).

왜 압축인가?

압축은 여러 가지 장점을 제공합니다.

• 빠른 전송: 메시지가 짧을수록 전송 시간이 줄어들고 네트워크 용량이 늘어납니다.
• 효율적인 리소스 사용: 메시지가 작을수록 네트워크 리소스(대역폭, 버퍼)가 절약되어 더 많은 통신이 가능합니다.
• 오류가 발생하기 쉬운 링크에 대한 처리량 향상: 오류 수정 코딩 전 압축을 통해 오류 복원력을 위한 최적화된 중복성을 제공합니다.

압축은 일반적으로 엔드 투 엔드 기능(애플리케이션 계층)이지만 데이터가 압축 가능하고 중복성이 포함된 경우 링크 계층에도 적용될 수 있습니다. 다음 장에서는 Huffman 코드와 LZW(Lempel-Ziv-Welch) 압축을 다룹니다.

압축 알고리즘: Huffman 및 Lempel-Ziv-Welch(LZW)

이 장에서는 메시지 압축(메시지가 일련의 기호임)을 위한 두 가지 소스 코딩 알고리즘, 즉 허프만 코딩과 Lempel-Ziv-Welch(LZW)에 대해 설명합니다. 허프만 코딩은 기호 확률이 알려져 있고 독립적일 때 효율적입니다. LZW는 적응형이므로 확률에 대한 사전 지식이 필요하지 않습니다. 둘 다 널리 사용됩니다(GIF, JPEG, MPEG, MP3 등).

좋은 소스코드의 속성

코드는 알파벳(텍스트, 픽셀 강도 또는 추상 기호)의 기호를 코드워드로 매핑합니다. 바이너리 코드워드는 많은 통신 채널에 편리합니다.

예: 6.02의 인코딩 등급: A=1, B=01, C=000, D=001. 일련의 등급은 0010001110100001로 전송되고 "DCAAABCB"로 디코딩될 수 있습니다.

순간 코드: 기호는 해당 코드워드가 수신되는 즉시 해독됩니다. 위의 등급 인코딩은 즉각적입니다. 순간적이지 않은 코드는 앞을 내다보거나 끝에서부터 디코딩해야 하므로 디코딩하기가 더 어렵습니다.

코드 트리 및 접두어 없는 코드: 코드 트리는 코드를 시각화합니다. 이진 코드 트리에서 가장자리에는 0 또는 1로 레이블이 지정됩니다. 루트에서 기호까지의 경로는 해당 인코딩을 제공합니다. 접두사가 없는 코드는 리프 노드에만 기호가 있으므로 코드워드가 다른 코드워드의 접두사가 되지 않도록 합니다. 접두어가 없는 코드는 즉시 적용됩니다.

예상 코드 길이(L): 확률 pi 및 코드워드 길이 li를 갖는 N 기호의 경우: L = Σ pi * 리. L이 작은 코드는 압축에 적합합니다. 최적 코드에는 최소 L이 있습니다. Shannon은 L ≥ H(엔트로피)를 보여주며, 엔트로피를 달성하는 코드는 점근적으로 존재합니다.

허프만 코드

허프만 코드는 주어진 기호 확률에 따라 효율적인 인코딩을 제공합니다. 가능성이 높은 기호는 코드가 더 짧아집니다.

Huffman의 알고리즘은 가능성이 가장 낮은 기호부터 시작하여 상향식 코드 트리를 구축합니다.

1. 입력: S의 (확률, 기호) 튜플을 설정합니다.
2. 가능성이 가장 낮은 두 개의 기호를 새로운 튜플로 결합합니다(결합된 기호, 확률의 합). S에 새 튜플을 추가합니다.
3. S에 튜플(루트)이 하나만 있을 때까지 2단계를 반복합니다.

결과 코드 트리는 가변 길이 코드를 정의합니다.

허프만 코드의 속성

• 비고유성: 트리 구성 중 임의의 타이 브레이킹으로 인해 최적의 코드(및 트리)가 여러 개 존재할 수 있습니다.
• 최적성: 허프만 코드는 고정된 알려진 확률 분포에서 추출된 독립 기호에 대한 순간 코드 중에서 최소 예상 길이를 갖습니다.

LZW: 적응형 가변 길이 소스 코드

문자 확률을 기반으로 한 단순한 허프만 코딩에는 한계가 있습니다. 메시지 내용에 맞게 조정되는 적응형 인코딩이 더 나은 성능을 발휘할 수 있습니다. LZW는 널리 사용되는 적응형 알고리즘입니다.

LZW는 N비트 인덱스 간 심볼 시퀀스를 매핑하는 문자열 테이블을 구축합니다. 테이블(2^N 항목)은 단일 바이트 시퀀스(0-255)로 초기화됩니다. 인코딩:

1. 테이블에 시퀀스(S)가 있는 동안 바이트를 누적합니다.
2. S 다음 바이트(b)가 테이블에 없는 경우:
   • S에게 코드를 전송하세요
   • 테이블에 S b를 추가하세요.
   • S를 b로 재설정합니다.
3. 모든 바이트가 처리될 때까지 반복합니다. 그런 다음 최종 S에 대한 코드를 전송합니다.

디코더는 코드를 수신하면 테이블을 다시 작성하여 원본 메시지를 복구할 수 있습니다.

LZW 관찰:

• Greedy: 가장 긴 일치 항목을 찾습니다.
• 적응형: 테이블 항목은 실제 메시지 순서를 반영합니다.
• 차선: 사용하지 않은 항목이 포함될 수 있습니다.
• 가변 압축: 테이블이 채워질수록 압축이 증가합니다.
• 테이블 재초기화: 테이블이 가득 차면 확률 변화에 맞춰 재설정됩니다. 일부 변형은 명시적 재설정을 위해 CLEAR 코드를 사용합니다.

왜 디지털인가? 통신 추상화 및 디지털 신호

이 장에서는 아날로그의 문제점과 디지털의 이론적 근거를 중심으로 아날로그와 디지털 통신을 설명합니다. 아날로그 통신 링크(물리적 링크는 기본적으로 가장 낮은 수준에서 아날로그이기 때문에 필요함)를 통해 디지털 데이터를 보내고 받는 방법을 제시합니다. 또한 이 책의 나머지 부분의 기초를 형성하는 메시지 → 패킷 → 비트 → 신호 등 계층형 통신 모델을 소개합니다.

데이터 소스

통신 기술을 통해 사용자(사람 또는 애플리케이션)가 메시지를 교환할 수 있습니다. 데이터 소스는 본질적으로 디지털(예: 컴퓨터 생성 데이터)이거나 아날로그(예: 비디오, 오디오, 센서 데이터)일 수 있습니다. 최신 시스템은 소스에 관계없이 모든 데이터를 디지털화하는 경우가 많습니다.

왜 디지털인가?

디지털 커뮤니케이션은 두 가지 이유로 탁월합니다.

1. 모듈화: 디지털 추상화를 통해 모듈을 구성하여 대규모 시스템을 구축할 수 있습니다.
2. 정교한 처리: 알고리즘을 사용하여 데이터 품질과 시스템 성능을 향상시킬 수 있습니다.

그러나 물리적 링크는 아날로그이므로 디지털에서 아날로그로, 아날로그에서 디지털로 변환이 필요합니다.

많은 응용 분야에서 아날로그가 자연스러운 이유

아날로그 표현은 물리적 링크 속성에 잘 매핑됩니다. 예:

• 흑백 TV: 영상 휘도(회색 음영)는 전압 레벨(0V = 검정색, 1V = 흰색)로 표시됩니다.

• 아날로그 전화기: 음파가 전기 신호로 변환됩니다.

아날로그 신호는 다양한 전압/강도/파장 수준으로 전송될 수 있으며 수신기에서 쉽게 측정할 수 있습니다.

그렇다면 왜 아날로그가 아닌가?

오류가 없는 통신 링크는 없습니다. 잡음과 왜곡은 신호를 교란시키며 이러한 오류는 여러 전송 단계에 걸쳐 누적됩니다(계단 효과). 이로 인해 아날로그 시스템, 특히 복잡한 시스템을 안정적으로 구축하기가 어렵습니다. 디지털 신호로 이 문제를 해결할 수 있습니다.

디지털 신호: 비트를 신호에 매핑

디지털 신호는 이산 값을 사용하여 비트를 표시하므로 잡음과의 확실한 구별이 가능합니다. 바이너리 신호는 "0"에 대해 V0, "1"에 대해 V1이라는 두 가지 전압을 사용합니다. 노이즈를 처리하려면 V0와 V1을 충분히 분리해야 합니다.

수신기는 임계 전압(Vth = (V0 V1) / 2)을 사용하여 수신된 전압을 비트(전압

이 강의의 신호

전송 신호는 특정 시간 동안 유지되는 고정 전압 파형입니다. 연속 신호는 이산시간 샘플로 표현됩니다. 샘플링 속도(초당 샘플 수)는 발신자와 수신자가 합의합니다. 샘플 간격은 샘플 사이의 시간입니다.

클록킹 전송

송신자와 수신자는 클럭 속도에 동의해야 합니다. 비트는 클록 전환 시 전송됩니다. Samples_per_bit는 비트당 샘플 수입니다. 수신기는 수신된 샘플의 전환에서 클럭 에지를 추론합니다.

도전과제:

1. 시계 동기화: 발신자와 수신자의 시계가 다를 수 있습니다. 해결 방법: 감지된 전환을 기반으로 수신기의 적응형 타이밍.
2. 잦은 전환 보장: 클럭 복구에 필요합니다. 해결책: 라인 코딩(예: 8b/10b).

시계 및 데이터 복구

수신자의 시계는 발신자의 시계보다 약간 빠르거나 느릴 수 있습니다. 수신기는 전환에 따라 샘플링 인덱스를 동적으로 조정합니다.

• 현재 포인트와 이전 포인트 사이의 중간 샘플이 현재 샘플과 동일인 경우(샘플링이 너무 늦음): Samples_per_bit - 1만큼 인덱스를 증가시킵니다.
• 중간 샘플이 다른 경우(샘플링이 너무 이른 경우): Samples_per_bit 1씩 증가합니다.
• 전환이 없는 경우: Samples_per_bit씩 증가합니다.

초기 수정은 전송 시작 ​​시 0과 1이 교대로 반복되는 트레이닝 시퀀스를 통해 지원됩니다.

8b/10b를 사용한 라인 코딩

8b/10b는 DC 균형 및 빈번한 전환을 해결합니다. 8비트 기호를 10비트 전송 기호에 매핑하여 다음을 보장합니다.

• 0 또는 1의 최대 실행은 5비트입니다.
• 모든 샘플에서 1과 0의 최대 차이는 6입니다.
• 특수 7비트 시퀀스를 통해 패킷 경계 감지가 가능합니다.

인코딩 과정:

1. 패킷 데이터는 바이트 단위로 나누어집니다.
2. 각 바이트는 10비트 기호에 매핑됩니다.
3. 패킷은 동기화를 위한 훈련 시퀀스와 SYNC 패턴으로 구성됩니다.

커뮤니케이션 추상화

통신 시스템에는 Mapper(비트를 신호로), Demapper(신호를 비트로), 채널 코딩(오류 수정), 채널 디코딩 등 여러 모듈이 포함됩니다. 메시지는 패킷으로 분할되어 여러 링크를 통해 전송됩니다. 세 가지 핵심 추상화는 패킷, 비트, 신호입니다. 이 책은 이들과 통신 네트워크 내에서의 상호 작용에 중점을 둡니다.

오류 수정 코드를 사용하여 비트 오류에 대처

이 장에서는 통신 채널과 저장 미디어에서 피할 수 없는 비트 오류를 ​​방지하기 위해 중복성을 추가하는 데 중점을 두고 안정적인 디지털 통신 기술을 논의합니다. 핵심 개념은 채널 코딩입니다. 즉, 송신측에서 인코딩하고 수신측에서 디코딩하여 오류를 수정하거나 수정 불가능한 오류를 감지합니다. 이 장에서는 오류 수정 코드, 특히 선형 블록 코드와 (나중에) 컨벌루션 코드에 중점을 둡니다.

비트 오류 및 BSC

BSC(이진 대칭 채널) 모델은 단일 매개변수 ε(비트 반전 확률)을 사용하여 비트 오류를 ​​특성화합니다. 여기서 전송된 비트는 다른 비트와 관계없이 확률 ε로 반전됩니다. ε은 경험적으로 추정할 수 있습니다. S비트 크기의 패킷에 대한 패킷 오류 확률(PER):

PER = 1 - (1 - ε)^S (5.1)

ε

실제 채널에서는 기록에 따라 오류 확률이 달라지는 버스트 오류가 나타날 수 있습니다(최근 비트에도 오류가 있는 경우 더 높음).

가장 간단한 코드: 반복

A 반복 코드는 비트 b를 b의 n개 복사본으로 인코딩합니다. 코드율은 1/n입니다. 최대 우도 디코딩은 수신된 코드워드에서 가장 가능성이 높은 메시지를 선택합니다. BSC의 경우 이는 수신된 비트와 공통된 비트가 가장 많은 코드워드를 선택하는 것을 의미합니다.

반복 코드에 대한 디코딩 오류 확률(원문의 수식 5.3 참조) 코드율이 높아질수록 확률은 기하급수적으로 감소하지만 오버헤드가 높아 비효율적입니다.

임베딩 및 해밍 거리

해밍 거리(HD) 두 n비트 단어 사이의 서로 다른 비트 위치의 수입니다. 단일 오류 정정(SEC)의 경우 유효한 두 코드워드 사이의 HD는 3 이상이어야 합니다. 최소 해밍 거리 D를 갖는 코드는 D-1 오류를 감지하고 층(D/2 -1) 오류.

선형 블록 코드 및 패리티 계산

선형 블록 코드 (n, k)는 메시지 비트에 대한 선형 함수(가중치 합)를 사용하여 k비트 메시지를 n비트 코드워드로 매핑합니다. 대수 블록 코드는 블록 내에서 이러한 작업을 수행합니다. (n,k,d) 코드는 최소 해밍 거리 'd'를 갖는 블록 코드를 나타낸다. 코드율 = k/n.

선형 코드에서는 두 코드워드의 합도 코드워드가 되어야 합니다. 모두 0인 코드워드는 모든 선형 코드에 존재합니다. 선형 블록 코드의 최소 해밍 거리는 0이 아닌 가장 작은 코드워드의 가중치(1의 수)와 같습니다. 이진 선형 코드 모듈로-2 연산(Galois Field F2)을 사용합니다.

직사각형 패리티 SEC 코드

패리티는 모듈로-2 비트 합계입니다. 짝수 패리티 코드는 각 메시지에 패리티 비트를 추가하여 코드워드가 짝수 패리티를 갖도록 합니다. 이는 단일 오류(HD=2)를 감지합니다.

직사각형 패리티 코드는 k 비트를 r x c 배열로 배열하고 행 및 열 패리티를 추가합니다. 코드워드: 메시지 행 패리티 열 패리티. 길이: n = rc r c. 이 코드는 SEC 코드(HD=3)입니다. 디코딩에는 행 및 열 패리티를 확인하고 두 패리티 모두 오류를 나타내는 경우 해당 비트를 수정하는 작업이 포함됩니다.

SEC 코드에는 몇 개의 패리티 비트가 필요합니까?

모든 선형 코드는 체계적 코드(패리티 비트가 뒤따르는 메시지 비트)로 변환될 수 있습니다. SEC의 경우 패리티 조합 수(2^(n-k))는 수정 가능한 상황 수(n 1)보다 크거나 같아야 합니다.

n 1 ≤ 2^(n-k) (5.6)

패리티 비트 수는 메시지 비트에 따라 최소한 대수적으로 증가합니다.

해밍 코드

해밍 코드는 대수 패리티 비트 증가를 갖는 효율적인 SEC 코드입니다. 각 패리티 비트는 여러 데이터 비트를 보호하며 단일 오류는 고유한 패리티 오류 조합을 생성합니다.

신드롬 비트(Ei)는 패리티를 확인하여 수신기에서 계산됩니다. 신드롬 비트의 조합은 잘못된 비트(있는 경우)를 나타냅니다.

해밍 코드 구성에 논리가 있습니까?

해밍 코드 구성:

1. 2의 거듭제곱인 인덱스(1, 2, 4, 8,...)에 패리티 비트를 할당합니다.
2. 나머지 인덱스에 데이터 비트를 할당합니다.
3. 데이터 비트 di는 index(pj)가 index(dipj에 대한 패리티 계산에 포함됩니다. >) 이진 표현(비트 AND는 0이 아님).

2진수로 처리되는 신드롬 비트((7,4) 예의 E3E2E1)는 수정해야 할 비트의 인덱스를 제공합니다.

참고: 이는 웹 개발에 필요한 정보일 뿐입니다. Sysops의 경우 네트워크와 그 기초가 2학기 과정입니다.

위 내용은 인터넷은 어떻게 작동하나요? 2부의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!