부호 이론 문서 원본 보기

{{위키데이터 속성 추적}}

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

네 가지 유형의 코딩이 있다.<ref>{{서적 인용|url=https://books.google.com/books?id=ZigejECe4r0C|제목=Data Communications and Networks|성=James Irvine|성2=David Harle|날짜=2002|쪽=18|장=2.4.4 Types of Coding|isbn=9780471808725|인용문=There are four types of coding}}
</ref>

# [[데이터 압축]] (또는 ''소스 코딩'' )
# [[오류 검출 정정|오류 검출]] (또는 ''채널 코딩'' )
# [[암호학|암호화 코딩]]
# 라인 코딩

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

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

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

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

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

1972년 나시르 아흐메드는 [[이산 코사인 변환]] (DCT)을 제안했다.<ref name="Ahmed">{{웹 인용|url=https://www.scribd.com/doc/52879771/DCT-History|제목=How I Came Up With the Discrete Cosine Transform|성=Nasir Ahmed|저자링크=N. Ahmed|출판사=Digital Signal Processing, Vol. 1, Iss. 1, 1991, pp. 4-5}}</ref> DCT는 [[JPEG]], [[MPEG]] 및 [[MP3]]와 같은 멀티미디어 형식의 기반인 가장 널리 사용되는 [[손실 압축]] 알고리즘이다.

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

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

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

: <math>C:\mathcal{X}\to\Sigma^*</math> (또는 <math>\Sigma^+</math> 빈 문자열이 알파벳의 일부가 아닌 경우).

<math>C(x)</math>는 <math>x</math>와 관련된 부호 워드다.

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

: <math>l(C(x)).</math>

부호의 예상 길이는

: <math>l(C) = \sum_{x\in\mathcal{X}}l(C(x))\mathbb{P}[X=x] .</math>

부호 워드의 연결 <math>C(x_1, \ldots, x_k) = C(x_1)C(x_2) \cdots C(x_k)</math> .

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

: <math>C(\epsilon) = \epsilon</math>

=== 속성 ===

# <math>C:\mathcal{X}\to\Sigma^*</math>는 injective하면 non-singular하다 [[단사 함수|.]]
# <math>C:\mathcal{X}^*\to\Sigma^*</math> injective하면 고유하게 디코딩할 수 있다.
# <math>C:\mathcal{X}\to\Sigma^*</math> 이면 <math>C(x_1)</math>가 <math>C(x_2)</math>의 prefix가 아니라면, 즉각적이다. (그리고 그 역도 성립한다).

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

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

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

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

CD는 교차 삽입된 리드-솔로몬 코딩 을 사용하여 데이터를 디스크에 퍼뜨린다.<ref>
Todd Campbell.
[https://abcnews.go.com/Technology/story?id=119305&page=1 "Answer Geek: Error Correction Rule CDs"].
</ref>

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

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

== 암호화 코딩 ==
[[암호학|암호화]] 또는 암호화 코딩은 제3자( 적이 라고 함)가 있는 상태에서 보안 통신 을 위한 기술을 연습하고 연구하는 것이다.<ref name="rivest90">{{서적 인용|제목=Handbook of Theoretical Computer Science|성=Rivest|이름=Ronald L.|저자링크=Ron Rivest|연도=1990|편집자-성=J. Van Leeuwen|권=1|출판사=Elsevier|장=Cryptology}}</ref> 보다 일반적으로 공격자를 차단하는 [[통신 프로토콜|프로토콜]]을 구성하고 분석하는 것이다.<ref name="modern-crypto">{{서적 인용|제목=Introduction to Modern Cryptography|성=Bellare|이름=Mihir|성2=Rogaway|이름2=Phillip|날짜=21 September 2005|쪽=10|장=Introduction}}</ref> 데이터 기밀성, [[데이터 무결성]], [[인증]] 및 [[부인봉쇄|부인 방지]]와 같은 [[정보 보안]]의 다양한 측면<ref name="hac">{{서적 인용|url=https://archive.org/details/handbookofapplie0000mene|제목=Handbook of Applied Cryptography|성=Menezes|이름=A. J.|성2=van Oorschot|이름2=P. C.|연도=1997|isbn=978-0-8493-8523-0|성3=Vanstone|이름3=S. A.}}</ref> 은 현대 암호화의 핵심이다. 현대 암호학은 [[수학]], [[컴퓨터 과학]] 및 [[전기공학|전기 공학]] 분야의 교차점에 존재한다. 암호화 응용 프로그램에는 [[현금 자동 입출금기|ATM 카드]], [[비밀번호|컴퓨터 암호]] 및 [[전자 상거래]]가 포함된다.

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

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

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

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

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

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

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

== 같이 보기 ==
* [[해밍 거리]]
== 각주 ==
{{각주}}
{{전거 통제}}

[[분류:오류 검출 정정]]
[[분류:부호 이론]]