부호 이론

3. 정보원 부호화 (소스 코딩)

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

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

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

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

팩시밀리 전송은 간단한 런 렝스 인코딩 부호화를 사용한다. 소스 부호화는 송신기의 필요에 불필요한 모든 데이터를 제거하여 전송에 필요한 대역폭을 줄인다.

3. 1. 정보원 부호화의 정의 및 성질

4. 통신로 부호화 (채널 코딩)

통신로 부호화(채널 코딩)는 데이터 전송 과정에서 발생하는 오류를 검출하고 정정하기 위한 기술이다.^[3] 통신로 부호화는 전송 속도, 부호어의 개수, 오류 검출 및 정정 능력 사이의 균형을 고려하여 설계된다.^[3] CD, 우주 통신, 모뎀, 휴대 전화 등 다양한 통신 환경에 따라 적합한 통신로 부호화 방식이 사용된다.^[3][26]

채널 부호 이론의 목적은 빠르게 전송하고 많은 유효한 부호어를 포함하며 많은 오류를 수정하거나 최소한 감지할 수 있는 부호를 찾는 것이다.^[3] 이러한 성능은 상호 배타적이지 않지만, 이들 영역에서의 성능은 상충 관계에 있다.^[3] 따라서, 서로 다른 부호는 서로 다른 응용 분야에 최적이다. 이러한 부호의 필요한 속성은 주로 전송 중에 오류가 발생할 확률에 따라 달라진다.^[3]

CD는 데이터를 디스크 전체에 분산시키기 위해 교차 인터리브 리드-솔로몬 부호를 사용한다.^[3] 일반적인 CD에서 손상은 주로 먼지나 긁힘이다. ^[26] 그렇게 좋은 부호는 아니지만, 단순 반복 부호는 이해하기 쉬운 예로 사용될 수 있다. 데이터 비트 블록(소리를 나타냄)을 가져와서 세 번 전송한다고 가정해 보자. 수신기에서는 세 번의 반복을 비트 단위로 검사하고 다수결 투표를 한다. 여기서 트위스트는 비트를 순서대로 전송하지 않는다는 것이다. 우리는 그것들을 인터리브한다. 데이터 비트 블록은 먼저 4개의 작은 블록으로 나뉜다. 그런 다음 블록을 순환하며 첫 번째 블록에서 비트 하나, 두 번째 블록에서 비트 하나 등을 전송한다. 이것은 데이터를 디스크 표면에 분산시키기 위해 세 번 수행된다. 단순 반복 부호의 맥락에서 이것은 효과적이지 않은 것처럼 보일 수 있다. 그러나 이 인터리빙 기술을 사용할 때 긁힘이나 먼지 반점의 "버스트" 오류를 수정하는 데 매우 효과적인 더 강력한 부호가 알려져 있다.^[3]

다른 부호는 다른 응용 분야에 더 적합하다. 우주 공간에서의 통신은 수신기의 열잡음의 영향이 크며, 이는 CD의 흠집 등과는 달리, 연속적인 노이즈이다. 전화 회선을 사용한 모뎀에서는 노이즈가 있기 때문에 전송 속도가 제한되는데, 이와 마찬가지이다. 휴대전화는 감쇠가 문제가 된다. 고주파에서는 수신기가 불과 몇 센티미터 움직이는 것만으로도 감쇠로 인해 신호를 잡을 수 없게 된다. 이러한 감쇠에 대처하는 통신로 부호화의 기법도 존재한다.^[3]

4. 1. 선형 블록 부호

• 순환 부호 (예: 해밍 부호)^[4]
• 반복 부호^[4]
• 패리티 부호^[4]
• 다항식 코드 (예: BCH 부호)^[4]
• 리드-솔로몬 부호^[4]
• 대수 기하 부호^[4]
• 리드-뮬러 부호^[4]
• 완전 부호^[4]
• 국소 복구 가능 코드

4. 2. 컨볼루션 부호

5. 암호 부호화

암호화 또는 암호 부호화는 제3자(적)가 있는 상태에서 보안 통신을 위한 기술을 연구하고 적용하는 학문이다.^[27] 이는 통신 프로토콜을 구성하고 분석하여 공격자를 차단하는 것을 목표로 한다.^[28] 현대 암호학은 정보 보안의 다양한 측면, 즉 데이터 기밀성, 데이터 무결성, 인증, 부인 방지 등을 다룬다.^[29] 수학, 컴퓨터 과학, 전기 공학의 교차점에 위치하며, ATM 카드, 컴퓨터 암호, 전자 상거래 등에 응용된다.

현대 이전의 암호화는 정보를 읽을 수 있는 상태에서 없는 것으로 변환하는 ''암호화'' 와 사실상 동의어였다. 암호화된 메시지를 해독하는 기술은 의도된 수신자만 보유하여 원하지 않는 접근을 방지했다. 제1차 세계 대전과 컴퓨터의 출현 이후 암호학은 더욱 복잡해지고 광범위하게 활용되었다.

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

6. 전송로 부호화 (라인 코딩)

전송로 부호화(디지털 베이스밴드 변조 또는 디지털 베이스밴드 전송 방식이라고도 함)는 데이터 전송로를 통해 디지털 신호를 전송할 때 디지털 신호를 데이터 전송로의 특성에 적합한 전압, 전류 또는 광자의 펄스 파형으로 변환하기 위한 부호화이다.^[23] 베이스밴드 전송 목적으로 통신 시스템 내에서 사용하기 위해 선택된 부호이다.

전송로 부호화는 전송되는 디지털 신호를 물리적 채널 및 수신 장치의 특성에 따라 최적으로 조정된 진폭 및 시간 이산 신호로 나타내는 것으로 구성된다. 디지털 데이터의 1과 0을 나타내기 위해 사용되는 전압 또는 전류의 파형 패턴을 전송로 부호화라고 한다. 일반적인 전송로 부호화 유형은 단극성, 극성, 양극성, 맨체스터 부호화가 있다.

7. 부호 이론의 다른 응용

부호 이론은 동기화를 돕는 부호를 설계하는 데에도 응용된다. 위상 편이를 쉽게 감지하고 수정할 수 있도록 부호를 설계하거나, 여러 신호를 동일한 채널에서 보낼 수 있도록 부호를 설계할 수 있다.

부호 분할 다중 접속(CDMA)은 부호 이론이 응용되는 또 다른 예시이다. 각 전화기에는 다른 전화기의 부호와 거의 관련이 없는 부호 시퀀스가 할당된다. 전송 시 부호 워드는 음성 메시지를 나타내는 데이터 비트를 변조하는 데 사용되며, 수신기에서 복조 프로세스를 통해 데이터가 복구된다. 이러한 부호의 특성 덕분에 여러 사용자(다른 부호 사용)가 동시에 동일한 무선 채널을 사용할 수 있으며, 수신기에는 다른 사용자의 신호가 낮은 수준의 잡음으로만 나타난다.

자동 반복 요청(ARQ) 부호 또한 부호 이론의 일반적인 응용 사례이다. 송신자는 오류 검사를 위해 각 메시지에 중복성(일반적으로 검사 비트)을 추가한다. 수신된 메시지의 검사 비트가 나머지 메시지와 일치하지 않으면 수신자는 송신자에게 메시지 재전송을 요청한다. 가장 단순한 광역 통신망 프로토콜을 제외한 모든 프로토콜은 ARQ를 사용하며, SDLC (IBM), TCP (인터넷), X.25 (국제) 등이 대표적인 예시이다. 거부된 패킷을 새 패킷과 일치시키는 문제는 이 분야의 주요 연구 과제 중 하나이다.

그룹 검사는 부호 이론을 활용하여 특정 항목을 효율적으로 식별하는 방법이다. 예를 들어, 매우 적은 수의 불량 제품 또는 감염된 시험 대상이 포함된 대규모 항목 그룹에서, 가능한 한 적은 수의 테스트를 통해 어떤 항목이 "다른지"를 결정하는 데 사용된다. 이 아이디어는 제2차 세계 대전 당시 미국 육군 항공대가 군인들의 매독 검사를 해야 했을 때 처음 고안되었다.^[11]

아날로그 신호 처리 및 아날로그 전자공학 분야에서 정보는 아날로그 코딩 방식으로 유사하게 인코딩된다. 아날로그 코딩에는 아날로그 오류 정정,^[12] 아날로그 데이터 압축,^[13] 아날로그 암호화^[14] 등이 포함된다.

신경 부호화는 감각 정보 및 기타 정보가 뇌에서 뉴런의 회로망에 의해 어떻게 표현되는지를 연구하는 신경과학 분야이다. 신경 부호화 연구의 주된 목표는 자극과 개별 또는 앙상블 뉴런 반응 간의 관계, 그리고 앙상블 내 뉴런의 전기적 활동 간의 관계를 특징짓는 것이다.^[15] 뉴런은 디지털 데이터와 아날로그 신호 정보를 모두 부호화할 수 있으며,^[16] 정보 이론의 원리에 따라 정보를 압축하고,^[17] 뇌와 광범위한 신경계를 통해 전송되는 신호의 오류를 감지하고 수정하는 것으로 알려져 있다.^[18]

7. 1. 한국의 부호 이론 응용 사례

참조

_[1] 서적 Data Communications and Networks https://books.google[...] John Wiley & Sons 2002
_[2] 웹사이트 How I Came Up With the Discrete Cosine Transform https://www.scribd.c[...] Digital Signal Processing, Vol. 1, Iss. 1, 1991, pp. 4-5
_[3] 뉴스 Answer Geek: Error Correction Rule CDs https://abcnews.go.c[...]
_[4] 서적 Fourier Analysis on Finite Groups and Applications https://archive.org/[...] Cambridge University Press
_[5] 서적 Algebraic Codes for Data Transmission https://books.google[...] Cambridge University Press
_[6] 서적 Trellis and turbo coding https://books.google[...] Wiley-IEEE
_[7] 간행물 Trellis shaping 1992-03
_[8] 서적 Handbook of Theoretical Computer Science Elsevier
_[9] 서적 Introduction to Modern Cryptography 2005-09-21
_[10] 서적 Handbook of Applied Cryptography https://archive.org/[...] Taylor & Francis
_[11] 간행물 The detection of defective members of large populations 1943
_[12] 간행물 Analog Error-Correcting Codes Based on Chaotic Dynamical Systems http://allegro.mit.e[...] 2013-06-30
_[13] 학술 On Analog Signature Analysis
_[14] 간행물 Cryptanalyzing an Encryption Scheme Based on Blind Source Separation http://epubs.surrey.[...] 2008-04
_[15] 간행물 Multiple neural spike train data analysis: state-of-the-art and future challenges http://www.stat.colu[...] 2004-05
_[16] 서적 Parallel processing in neural systems and computers https://books.google[...] North-Holland 2013-06-30
_[17] 간행물 Information Distortion and Neural Coding http://www.math.ualb[...] 2013-06-30
_[18] 간행물 Spike timing precision and neural error correction: local behavior 2005-07
_[19] 서적 Data Communications and Networks https://books.google[...] 2002
_[20] 서적 Handbook of Theoretical Computer Science Elsevier
_[21] 서적 Introduction to Modern Cryptography 2005-09-21
_[22] 서적 Handbook of Applied Cryptography https://web.archive.[...]
_[23] 문서 JIS X 0009:1997 情報処理用語（データ通信） 09.05.01
_[24] 서적 Data Communications and Networks https://books.google[...] 2002
_[25] 웹인용 How I Came Up With the Discrete Cosine Transform https://www.scribd.c[...] Digital Signal Processing, Vol. 1, Iss. 1, 1991, pp. 4-5
_[26] 뉴스 Answer Geek: Error Correction Rule CDs https://abcnews.go.c[...]
_[27] 서적 Handbook of Theoretical Computer Science Elsevier
_[28] 서적 Introduction to Modern Cryptography 2005-09-21
_[29] 서적 Handbook of Applied Cryptography https://archive.org/[...]