부호 이론

부호 이론은 부호의 속성과 특정 응용 프로그램에 대한 부호의 적합성에 대한 연구이다. 부호는 데이터 압축, 암호화, 오류 감지 및 수정, 데이터 전송 및 데이터 스토리지에 사용된다. 부호는 효율적이고 신뢰할 수 있는 데이터 전송 방법을 설계하기 위해 정보이론, 전기 공학, 수학, 언어학 및 컴퓨터 과학과 같은 다양한 과학 분야에서 연구된다. 여기에는 일반적으로 중복 제거 및 전송된 데이터의 오류 수정 또는 감지가 포함된다.

네 가지 유형의 코딩이 있다.^[1]

데이터 압축 (또는 소스 코딩 )
오류 검출 (또는 채널 코딩 )
암호화 코딩
라인 코딩

데이터 압축은 데이터를 보다 효율적으로 전송하기 위해 소스의 데이터에서 중복성을 제거하려고 시도한다. 예를 들어, ZIP 데이터 압축은 인터넷 트래픽을 줄이는 등의 목적으로 데이터 파일을 더 작게 만든다. 데이터 압축 및 오류 수정은 연관지어 연구할 수 있다.

오류 수정은 추가 데이터 비트를 추가하여 전송 채널에 존재하는 교란에 대한 데이터 전송을 보다 강력하게 만든다. 일반 사용자는 오류 수정을 사용하는 많은 응용 프로그램을 인식하지 못할 수 있다. 일반적인 음악 CD (CD)는 리드 솔로몬 부호를 사용하여 흠집과 먼지를 수정한다. 이 응용 프로그램에서 전송 채널은 CD 자체이다. 휴대 전화는 또한 코딩 기술을 사용하여 고주파 무선 전송의 페이딩 및 노이즈를 수정한다. 데이터 모뎀, 전화 전송 및 심우주 통신망은 모두 채널 코딩 기술을 사용하여 예를 들어 터보 부호 및 LDPC 부호를 통해 비트를 가져온다.

부호 이론의 역사 편집

1948년 클로드 섀넌의 작업은 보낸 사람이 전송하려는 정보를 가장 잘 인코딩하는 방법의 문제에 중점을 둔다. 이 기초 작업에서 그는 노버트 위너가 개발한 확률 이론의 도구를 사용했는데, 이는 당시 통신 이론에 적용되는 초기 단계였다. 섀넌은 본질적으로 정보이론 분야를 발명하면서 메시지의 불확실성에 대한 척도로 정보 엔트로피를 개발했다.

이진 골레 부호는 1949년에 개발되었다. 각 24비트 워드에서 최대 3개의 오류를 수정하고 네 번째 워드를 감지할 수 있는 오류 수정 부호이다.

리처드 해밍은 벨 연구소에서 수치적 방법, 자동 코딩 시스템, 오류 감지 및 오류 수정 부호에 대한 작업으로 1968년 튜링 상을 수상했다. 그는 해밍 부호, 해밍 창, 해밍 수 및 해밍 거리로 알려진 개념을 발명했다.

1972년 나시르 아흐메드는 이산 코사인 변환 (DCT)을 제안했다.^[2] DCT는 JPEG, MPEG 및 MP3와 같은 멀티미디어 형식의 기반인 가장 널리 사용되는 손실 압축 알고리즘이다.

소스 코딩 편집

소스 코딩의 목적은 소스 데이터를 가져와 더 작게 만드는 것이다.

정의 편집

데이터는 확률 변수로 볼 수 있다. $X:\Omega \to {\mathcal {X}}$ , 어디 $x\in {\mathcal {X}}$ 확률로 나타난다 $\mathbb {P} [X=x]$ .

데이터는 알파벳 위의 문자열(단어)로 인코딩된다. $\Sigma$ .

C:{\mathcal {X}}\to \Sigma ^{*}

(또는

\Sigma ^{+}

빈 문자열이 알파벳의 일부가 아닌 경우).

$C(x)$ 는 $x$ 와 관련된 부호 워드다.

부호 워드의 길이는 다음과 같이 작성된다.

l(C(x)).

부호의 예상 길이는

l(C)=\sum _{x\in {\mathcal {X}}}l(C(x))\mathbb {P} [X=x].

부호 워드의 연결 $C(x_{1},\ldots ,x_{k})=C(x_{1})C(x_{2})\cdots C(x_{k})$ .

빈 문자열의 부호 워드는 빈 문자열 자체이다.

C(\epsilon )=\epsilon

속성 편집

$C:{\mathcal {X}}\to \Sigma ^{*}$ 는 injective하면 non-singular하다 .
$C:{\mathcal {X}}^{*}\to \Sigma ^{*}$ injective하면 고유하게 디코딩할 수 있다.
$C:{\mathcal {X}}\to \Sigma ^{*}$ 이면 $C(x_{1})$ 가 $C(x_{2})$ 의 prefix가 아니라면, 즉각적이다. (그리고 그 역도 성립한다).

원리 편집

소스의 엔트로피는 정보의 척도이다. 기본적으로 소스 부호는 소스에 존재하는 중복성을 줄이고 더 많은 정보를 전달하는 더 적은 비트로 소스를 나타내려고 한다.

특정 가정된 확률 모델에 따라 메시지의 평균 길이를 최소화하려고 명시적으로 시도하는 데이터 압축을 엔트로피 인코딩 이라고 한다.

소스 코딩 방식에서 사용되는 다양한 기술은 소스의 엔트로피 한계를 달성하기 위해 시도한다. C ( x ) ≥ H ( x ), 여기서 H ( x )는 소스의 엔트로피(비트 전송률)이고 C ( x )는 압축 후의 비트 전송률이다. 특히, 어떤 소스 코딩 방식도 소스의 엔트로피보다 나을 수 없다.

채널 코딩 편집

채널 부호 이론의 목적은 빠르게 전송하고 많은 유효한 부호 워드를 포함하며 많은 오류를 수정하거나 최소한 감지할 수 있는 부호를 찾는 것이다. 상호 배타적이지는 않지만 이러한 영역의 성능은 트레이드 오프이다. 따라서 다른 부호는 다른 응용 프로그램에 최적이다. 이 부호의 필요한 속성은 주로 전송 중 오류가 발생할 확률에 따라 다르다. 일반적인 CD에서 손상은 주로 먼지나 긁힘이다.

CD는 교차 삽입된 리드-솔로몬 코딩 을 사용하여 데이터를 디스크에 퍼뜨린다.^[3]

아주 좋은 부호는 아니지만 간단한 반복 부호가 이해하기 쉬운 예가 될 수 있다. 사운드를 나타내는 데이터 비트 블록을 세 번 전송한다고 가정한다. 수신기에서 우리는 3번의 반복을 비트별로 검사하고 다수결을 할 것이다. 이것에 대한 반전은 우리가 단순히 비트를 순서대로 보내지 않는다는 것이다. 우리는 그것들을 끼워 넣다. 데이터 비트 블록은 먼저 4개의 더 작은 블록으로 나뉜다. 그런 다음 블록을 순환하고 첫 번째 비트에서 한 비트를 보낸 다음 두 번째 비트 등을 보낸다. 이것은 디스크 표면에 데이터를 퍼뜨리기 위해 세 번 수행된다. 단순 반복 부호의 맥락에서 이것은 효과적이지 않을 수 있다. 그러나 이 인터리빙 기술을 사용할 때 스크래치 또는 먼지 얼룩의 "버스트" 오류를 수정하는 데 매우 효과적인 더 강력한 부호가 알려져 있다.

선형 부호 편집

대수부호화이론( algebraic coding theory )이라는 용어는 부호의 성질을 대수적 용어로 표현하고 더 연구하는 부호화이론의 하위분야를 말한다.

암호화 코딩 편집

암호화 또는 암호화 코딩은 제3자( 적이 라고 함)가 있는 상태에서 보안 통신 을 위한 기술을 연습하고 연구하는 것이다.^[4] 보다 일반적으로 공격자를 차단하는 프로토콜을 구성하고 분석하는 것이다.^[5] 데이터 기밀성, 데이터 무결성, 인증 및 부인 방지와 같은 정보 보안의 다양한 측면^[6] 은 현대 암호화의 핵심이다. 현대 암호학은 수학, 컴퓨터 과학 및 전기 공학 분야의 교차점에 존재한다. 암호화 응용 프로그램에는 ATM 카드, 컴퓨터 암호 및 전자 상거래가 포함된다.

현대 이전의 암호화는 정보를 읽을 수 있는 상태에서 의미 없는 것으로 변환하는 암호화 와 사실상 동의어였다. 암호화된 메시지의 발신자는 원래 정보를 복구하는 데 필요한 디코딩 기술을 의도된 수신자와만 공유하여 원하지 않는 사람이 동일한 작업을 수행하는 것을 방지한다. 제1차 세계 대전과 컴퓨터의 출현 이후 암호학을 수행하는 데 사용되는 방법은 점점 더 복잡해지고 적용 범위가 더 넓어졌다.

현대 암호학은 수학적 이론과 컴퓨터 과학 실습에 크게 기반을 두고 있다. 암호화 알고리즘은 계산 경도 가정 을 중심으로 설계되어 이러한 알고리즘을 실제로 적군이 깨뜨리기 어렵게 만든다. 이러한 시스템을 깨는 것은 이론적으로 가능하지만 알려진 실제 수단으로는 불가능하다. 따라서 이러한 체계를 컴퓨터 보안이라고 한다. 정수 인수분해 알고리즘의 개선과 더 빠른 컴퓨팅 기술과 같은 이론적 발전을 위해서는 이러한 솔루션이 지속적으로 적용되어야 한다. 무제한 컴퓨팅 파워로도 provably 수 없는 정보 이론상 안전한 체계가 존재하지만(예: 일회용 패드 ) 이러한 체계는 이론적으로 깨질 수 있지만 계산적으로 안전한 최고의 메커니즘보다 구현하기가 더 어렵다.

라인 코딩 편집

라인 부호 (디지털 베이스밴드 변조 또는 디지털 베이스밴드 전송 방법이라고도 함)는 베이스밴드 전송 목적으로 통신 시스템 내에서 사용하기 위해 선택된 부호이다. 라인 코딩은 디지털 데이터 전송에 자주 사용된다.

라인 코딩은 물리적 채널(및 수신 장비)의 특정 속성에 대해 최적으로 조정된 진폭 및 시간 이산 신호에 의해 전송될 디지털 신호를 나타내는 것으로 구성된다. 전송 링크에서 디지털 데이터의 1과 0을 나타내는 데 사용되는 전압 또는 전류의 파형 패턴을 라인 인코딩 이라고 한다. 라인 인코딩의 일반적인 유형은 유니폴라, 폴라, 바이폴라 및 맨체스터 인코딩이다.

부호 이론의 다른 응용 편집

부호 이론의 또 다른 관심사는 동기화를 돕는 부호를 설계하는 것이다. 위상 편이를 쉽게 감지하고 수정할 수 있고 여러 신호를 동일한 채널에서 보낼 수 있도록 부호를 설계할 수 있다.

일부 휴대 전화 시스템에서 사용되는 또 다른 부호 응용 프로그램은 CDMA( 부호 분할 다중 액세스 )이다. 각 전화기에는 다른 전화기의 부호와 거의 관련이 없는 부호 시퀀스가 할당된다. 전송할 때 부호 워드는 음성 메시지를 나타내는 데이터 비트를 변조하는 데 사용된다. 수신기에서 데이터를 복구하기 위해 복조 프로세스가 수행된다. 이 부호 클래스의 속성은 많은 사용자(다른 부호 사용)가 동시에 동일한 무선 채널을 사용할 수 있도록 한다. 수신기에는 다른 사용자의 신호가 낮은 수준의 잡음으로만 복조기에 나타난다.

부호의 또 다른 일반적인 클래스는 자동 반복 요청 (ARQ) 부호이다. 이 부호에서 발신자는 일반적으로 검사 비트를 추가하여 오류 검사를 위해 각 메시지에 중복성을 추가한다. 체크 비트가 메시지가 도착했을 때 나머지 메시지와 일치하지 않으면 수신자는 발신자에게 메시지를 재전송하도록 요청한다. 가장 단순한 광역 네트워크 프로토콜을 제외한 모든 프로토콜은 ARQ를 사용한다. 일반적인 프로토콜에는 SDLC (IBM), TCP (인터넷), X.25 (국제) 등이 있다. 거부된 패킷을 새 패킷과 일치시키는 문제 때문에 이 주제에 대한 광범위한 연구 분야가 있다.

각주 편집

↑ James Irvine; David Harle (2002). 〈2.4.4 Types of Coding〉. 《Data Communications and Networks》. 18쪽. ISBN 9780471808725. There are four types of coding
↑ Nasir Ahmed. “How I Came Up With the Discrete Cosine Transform”. Digital Signal Processing, Vol. 1, Iss. 1, 1991, pp. 4-5.
↑ Todd Campbell. "Answer Geek: Error Correction Rule CDs".
↑ Rivest, Ronald L. (1990). 〈Cryptology〉. J. Van Leeuwen. 《Handbook of Theoretical Computer Science》 1. Elsevier.
↑ Bellare, Mihir; Rogaway, Phillip (2005년 9월 21일). 〈Introduction〉. 《Introduction to Modern Cryptography》. 10쪽.
↑ Menezes, A. J.; van Oorschot, P. C.; Vanstone, S. A. (1997). 《Handbook of Applied Cryptography》. ISBN 978-0-8493-8523-0.

[1] James Irvine; David Harle (2002). 〈2.4.4 Types of Coding〉. 《Data Communications and Networks》. 18쪽. ISBN 9780471808725. There are four types of coding

[Ahmed-2] Nasir Ahmed. “How I Came Up With the Discrete Cosine Transform”. Digital Signal Processing, Vol. 1, Iss. 1, 1991, pp. 4-5.

[3] Todd Campbell. "Answer Geek: Error Correction Rule CDs".

[rivest90-4] Rivest, Ronald L. (1990). 〈Cryptology〉. J. Van Leeuwen. 《Handbook of Theoretical Computer Science》 1. Elsevier.

[modern-crypto-5] Bellare, Mihir; Rogaway, Phillip (2005년 9월 21일). 〈Introduction〉. 《Introduction to Modern Cryptography》. 10쪽.

[hac-6] Menezes, A. J.; van Oorschot, P. C.; Vanstone, S. A. (1997). 《Handbook of Applied Cryptography》. ISBN 978-0-8493-8523-0.

[1]

[2]

[3]

[4]

[5]

[6]