코드 이론. 코딩 이론

무료 백과 사전, 위키피디아에서

코딩 이론- 코드 속성의 과학 및 목표 달성을 위한 적합성.

일반 정보

인코딩은 데이터를 직접 사용하기 편리한 형식에서 전송, 저장, 자동 처리 및 무단 액세스로부터 보존하기 편리한 형식으로 변환하는 프로세스입니다. 코딩 이론의 주요 문제는 일대일 코딩 문제와 주어진 조건에서 통신 채널을 구현하는 복잡성을 포함합니다.86. 이와 관련하여 코딩 이론은 주로 다음 영역을 고려합니다.18:

데이터 압축

앞으로 오류 수정

암호화

암호화(다른 그리스어에서. κρυπτός - 숨겨진 γράφω - 나는 쓴다), 기밀성(외부인이 정보를 읽을 수 없음), 데이터 무결성(정보가 눈에 띄지 않게 변경될 수 없음), 인증(객체의 저자 또는 기타 속성에 대한 인증)을 보장하는 방법에 대한 지식 분야입니다. 뿐만 아니라 저자권을 거부할 수 없음

2006년 4월 4일 레니드 체르냐크 범주:기술

"열린 시스템" 컴퓨터의 출현과 동시에 신호 코딩 이론이 만들어지지 않았다면 컴퓨터의 생성은 불가능할 것입니다. 코딩 이론은 컴퓨팅 개발에 큰 영향을 미친 수학 분야 중 하나입니다.

"열린 시스템"

컴퓨터의 출현과 동시에 신호 코딩 이론이 만들어지지 않았다면 컴퓨터를 만드는 것은 불가능했을 것입니다.

코딩 이론은 컴퓨팅의 발전에 현저한 영향을 미친 수학 분야 중 하나입니다. 그 범위는 실제(또는 노이즈) 채널을 통한 데이터 전송으로 확장되며 주제는 전송된 정보의 정확성을 보장하는 것입니다. 즉, 신호를 보낸 후 데이터에서 유용한 정보를 안정적이고 쉽게 추출할 수 있도록 데이터를 가장 잘 패킹하는 방법을 연구합니다. 때때로 코딩 이론은 암호화와 혼동되지만 이것은 사실이 아닙니다. 암호화는 반대 문제를 해결하며 그 목표는 데이터에서 정보를 추출하기 어렵게 만드는 것입니다.

데이터를 인코딩해야 할 필요성은 전신이 발명된 직후인 150여 년 전에 처음 발생했습니다. 채널은 비싸고 신뢰할 수 없었기 때문에 비용을 최소화하고 전보 전송의 신뢰성을 높이는 작업이 시급했습니다. 문제는 대서양 횡단 케이블 부설로 인해 악화되었습니다. 1845년부터 특수 코드북이 사용되었습니다. 그들의 도움으로 전신 기사는 메시지를 수동으로 "압축"하여 일반적인 단어 시퀀스를 더 짧은 코드로 대체했습니다. 동시에 전송의 정확성을 확인하기 위해 패리티가 사용되기 시작했으며, 이 방법은 1세대 및 2세대 컴퓨터에서 천공 카드 입력의 정확성을 확인하는 데에도 사용되었습니다. 이를 위해 체크섬이 있는 특별히 준비된 카드를 마지막 입력 데크에 삽입했습니다. 입력 장치가 그다지 안정적이지 않은 경우(또는 데크가 너무 큰 경우) 오류가 발생할 수 있습니다. 이를 수정하기 위해 계산된 체크섬이 카드에 저장된 금액과 일치할 때까지 입력 절차를 반복했습니다. 이 계획은 불편할 뿐만 아니라 이중 결함도 놓치고 있습니다. 통신 채널이 발달함에 따라 보다 효과적인 제어 메커니즘이 필요했습니다.

노이즈 채널을 통한 데이터 전송 문제에 대한 최초의 이론적 솔루션은 통계 정보 이론의 창시자인 Claude Shannon이 제안했습니다. Shannon은 당시의 스타였으며 미국 학계 엘리트 중 한 명이었습니다. Vannevar Bush의 대학원생으로서 그는 1940년에 30세 미만의 과학자에게 수여되는 노벨상(노벨상과 혼동하지 말 것!)을 받았습니다. Bell Labs에 있는 동안 Shannon은 "A Mathematical Theory of Message Transmission"(1948)을 저술하여 채널의 대역폭이 메시지 소스의 엔트로피보다 크면 메시지를 인코딩할 수 있음을 보여주었습니다. 부당한 지체 없이 전송됩니다. 이 결론은 Shannon이 증명한 정리 중 하나에 포함되어 있으며, 그 의미는 대역폭이 충분한 채널이 있으면 약간의 시간 지연을 두고 메시지를 전송할 수 있다는 사실로 요약됩니다. 또한 그는 채널에 노이즈가 존재하는 상황에서 안정적인 전송의 이론적 가능성을 보여주었습니다. C = W log ((P+N)/N) 공식은 그의 고향인 미시간에 설치된 Shannon의 겸손한 기념비에 새겨져 있으며 그 가치는 Albert Einstein의 공식 E = mc 2 와 비교됩니다.

Shannon의 작업은 정보 이론 분야에서 더 많은 연구를 불러일으켰지만 실용적인 공학 응용 프로그램은 없었습니다. 이론에서 실제로의 전환은 Bell Labs의 Shannon 동료인 Richard Hamming의 노력으로 가능해졌습니다. 그는 "해밍 코드"라고 불리는 코드 클래스를 발견하여 명성을 얻었습니다. 40년대 중반 벨 모델 V 계전기 계산기에서 천공카드로 작업하는 불편함이 그들의 해밍코드 발명을 촉발시켰다는 전설이 있다. 그는 작업자가 없는 주말에 기계 작업을 할 시간이 주어졌고, 그 자신이 입력을 만지작거려야 했습니다. 그럴 수 있지만 Hamming은 주로 프로세서와 메모리 사이의 컴퓨터의 데이터 전송 라인을 포함하여 통신 채널의 오류를 수정할 수 있는 코드를 제안했습니다. 해밍 코드는 Shannon의 정리가 나타내는 가능성이 실제로 어떻게 실현될 수 있는지에 대한 증거가 되었습니다.

Hamming은 1950년에 논문을 발표했지만 내부 보고에 따르면 그의 코딩 이론은 1947년으로 거슬러 올라갑니다. 따라서 누군가는 Shannon이 아닌 Hamming이 코딩 이론의 아버지로 간주되어야 한다고 믿습니다. 그러나 기술의 역사에서 처음을 찾는 것은 쓸모가 없습니다.

"오류 수정 코드"(Error-Correcting Code, ECC)를 처음 제안한 사람이 해밍이라는 것은 확실합니다. 이러한 코드의 최신 수정은 모든 데이터 저장 시스템과 프로세서와 RAM 간의 교환에 사용됩니다. 변형 중 하나인 Reed-Solomon 코드는 CD에 사용되어 긁힘과 먼지 입자를 유발할 수 있는 삐걱거리는 소리와 소음 없이 녹음을 재생할 수 있습니다. Hamming을 기반으로 하는 많은 버전의 코드가 있으며 코딩 알고리즘과 검사 비트 수가 다릅니다. 이러한 코드는 행성 간 스테이션과의 심우주 통신 개발과 관련하여 특별한 의미를 얻었습니다. 예를 들어 Reed-Muller 코드에는 7개의 정보 비트에 대한 32개의 제어 비트 또는 6개의 정보 비트에 대한 26개의 제어 비트가 있습니다.

최신 ECC 코드 중에서 LDPC(Low-Density Parity-check Code) 코드를 언급해야 한다. 사실 그들은 약 30년 동안 알려져 왔지만 고화질 텔레비전이 발전하기 시작한 최근 몇 년 동안 그들에 대한 특별한 관심이 발견되었습니다. LDPC 코드는 100% 신뢰할 수는 없지만 채널 대역폭을 최대한 활용하면서 오류율을 원하는 수준으로 조정할 수 있습니다. "터보 코드"는 그들과 가깝고 깊은 공간에 있고 채널 대역폭이 제한된 물체로 작업할 때 효과적입니다.

Vladimir Alexandrovich Kotelnikov의 이름은 코딩 이론의 역사에 확고하게 새겨져 있습니다. 1933년 "통신의 기술 재구성에 관한 제1차 연합 회의를 위한 무선 통신에 관한 자료"에서 그는 "대역폭? 에테르? 그리고?와이어? 코텔니코프라는 이름은 등가로서 코딩 이론에서 가장 중요한 정리 중 하나의 이름에 포함되어 있습니다. 이 정리는 전송된 신호가 정보 손실 없이 복원될 수 있는 조건을 정의합니다.

이 정리는 "WKS 정리"(약어 WKS는 Whittaker, Kotelnikov, Shannon에서 가져옴)를 포함하여 다양하게 불려 왔습니다. 일부 출처에서는 Nyquist-Shannon 샘플링 정리와 Whittaker-Shannon 샘플링 정리를 모두 사용하고 있으며, 국내 대학 교과서에서는 단순히 "Kotelnikov의 정리"가 가장 많이 발견됩니다. 사실, 정리는 더 긴 역사를 가지고 있습니다. 첫 번째 부분은 프랑스 수학자 Emile Borel이 1897년에 증명했습니다. Edmund Whittaker는 1915년에 기부했습니다. 1920년 일본의 Kinnosuki Ogura는 Whittaker의 연구에 대한 수정 사항을 발표했으며 1928년에는 미국인 Harry Nyquist가 디지털화 및 아날로그 신호 재구성의 원칙을 개선했습니다.

클로드 섀넌(1916 - 2001)는 학창 시절부터 수학과 전기 공학에 동일한 관심을 보였습니다. 1932 년에 그는 1936 년 Massachusetts Institute of Technology에서 University of Michigan에 입학하여 1940 년에 졸업하여 전기 공학 석사 학위와 수학 박사 학위를 받았습니다. 1941년 Shannon은 Bell Laboratories에 합류했습니다. 여기에서 그는 나중에 정보 이론으로 귀결된 아이디어를 개발하기 시작했습니다. 1948년 Shannon은 과학자의 기본 아이디어, 특히 엔트로피를 통한 정보량 결정이 공식화된 "수학적 커뮤니케이션 이론"이라는 기사를 발표했으며 두 가지 선택을 결정하는 정보 단위도 제안했습니다. 똑같이 가능한 옵션, 즉 나중에 비트라고 불리는 것 . 1957-1961년에 Shannon은 현재 그의 이름을 딴 노이즈 통신 채널에 대한 처리량 정리를 증명한 작업을 발표했습니다. 1957년 Shannon은 Massachusetts Institute of Technology의 교수가 되었고 21년 후 은퇴했습니다. "적절한 휴식"에서 Shannon은 저글링에 대한 오랜 열정에 전적으로 헌신했습니다. 그는 여러 저글링 기계를 만들었고 심지어 저글링의 일반 이론을 만들었습니다.

리처드 해밍(1915 - 1998) 시카고 대학교에서 교육을 시작했으며 1937년에 학사 학위를 받았습니다. 1939년에 그는 네브래스카 대학교에서 석사 학위를, 일리노이 대학교에서 수학 박사 학위를 받았습니다. 1945년 해밍은 원자폭탄을 만들기 위한 대규모 정부 연구 노력인 맨해튼 프로젝트에 참여하기 시작했습니다. 1946년에 Hamming은 Bell Telephone Laboratories에 입사하여 Claude Shannon과 함께 일했습니다. 1976년 해밍은 캘리포니아 몬터레이에 있는 해군 대학원에서 학과장을 받았습니다.

오류 감지 및 수정 코드에 대한 근본적인 연구로 그를 유명하게 만든 작품은 1950년 Hamming에 의해 출판되었습니다. 1956년에 그는 초기 IBM 650 메인프레임 중 하나의 개발에 참여했으며, 그의 작업은 나중에 고급 프로그래밍 언어로 발전한 프로그래밍 언어의 토대를 마련했습니다. 컴퓨터 과학 분야에 대한 Hamming의 공헌을 인정하여 IEEE는 그의 이름을 딴 컴퓨터 과학 및 시스템 이론에 대한 공로 메달을 제정했습니다.

블라디미르 코텔니코프(1908-2005) 1926년 N. E. Bauman(MVTU)의 이름을 딴 모스크바 고등 기술 학교의 전기 공학부에 입학했지만 모스크바 전력 공학 연구소(MPEI)를 졸업했습니다. 독립 연구소. 대학원(1931-1933)에서 공부하는 동안 Kotelnikov는 나중에 그의 이름을 딴 "참조 정리"를 수학적으로 정확하게 공식화하고 증명했습니다. 1933년 대학원을 졸업한 후 모스크바 전력 공학 연구소에서 가르치고 있던 코텔니코프는 통신 중앙 연구소(TsNIIS)에서 일하기 시작했습니다. 1941년에 V. A. Kotelnikov는 수학적으로 해독할 수 없는 시스템이 충족해야 하는 요구 사항에 대한 명확한 입장을 공식화했으며 이를 해독할 수 없다는 증거를 제시했습니다. 1944년에 Kotelnikov는 MPEI의 무선 공학 학부장인 교수직을 맡아 1980년까지 일했습니다. 1953년, 45세의 나이에 코텔니코프는 즉시 소련 과학 아카데미 정회원으로 선출되었습니다. 1968년부터 1990년까지 V. A. Kotelnikov는 모스크바 물리 기술 연구소의 학과장이자 교수였습니다.

코딩 이론의 탄생

2006년 4월 4일 레니드 체르냐크 범주:기술

"열린 시스템"

컴퓨터의 출현과 동시에 신호 코딩 이론이 만들어지지 않았다면 컴퓨터를 만드는 것은 불가능했을 것입니다.

코딩 이론의 탄생

"이 과정의 목표는 기술 미래를 준비하는 것입니다."

헤이 하브르. 멋진 기사 "당신과 당신의 직업"(+219, 2442 북마크, 394k 읽기)을 기억하십니까?

그래서 Hamming(예, 예, 자체 검사 및 자체 수정 Hamming 코드)에는 그의 강의를 기반으로 작성된 전체 책이 있습니다. 남자가 마음을 말하기 때문에 우리는 그것을 번역합니다.

이 책은 IT에 관한 것이 아니라 엄청나게 멋진 사람들의 사고 방식에 관한 책입니다. “그냥 긍정적인 생각만 하는 것이 아닙니다. 위대한 일을 할 가능성을 높이는 조건을 설명합니다.”

우리는 이미 28장(30장 중)을 번역했습니다. 그리고 우리는 "in paper"출판물을 작업하고 있습니다.

코딩이론 - I

컴퓨터와 작동 방식을 고려했다면 이제 정보 표현에 대한 질문, 즉 컴퓨터가 우리가 처리하려는 정보를 표현하는 방법을 살펴보겠습니다. 문자의 의미는 처리 방법에 따라 달라질 수 있으며 기계는 사용된 비트에 대해 특정한 의미를 갖지 않습니다. 4장에서 소프트웨어의 역사를 논의할 때 정지 명령의 코드가 다른 명령의 코드와 동일한 합성 프로그래밍 언어를 고려했습니다. 이 상황은 대부분의 언어에서 일반적이며 명령의 의미는 해당 프로그램에 의해 결정됩니다.

정보 표현 문제를 단순화하기 위해 정보를 지점에서 지점으로 전송하는 문제를 고려하십시오. 이 질문은 정보 저장 문제와 관련이 있습니다. 시간과 공간에서 정보 전송의 문제는 동일합니다. 그림 10.1은 일반적인 정보 전달 모델을 보여줍니다.

그림 10.1

그림 10.1의 왼쪽에는 정보의 출처가 있습니다. 모델을 고려할 때 소스의 특성은 우리에게 중요하지 않습니다. 알파벳 문자, 숫자, 수학 공식, 음표, 댄스 동작을 나타낼 수있는 기호 집합이 될 수 있습니다. 소스의 특성과 여기에 저장된 문자의 의미는 전송 모델의 일부가 아닙니다. 우리는 정보의 출처만을 고려하며, 이러한 제한으로 많은 영역으로 확장될 수 있는 강력하고 일반적인 이론을 얻습니다. 이것은 많은 응용 프로그램에서 추상화한 것입니다.

Shannon이 1940년대 후반에 정보 이론을 창안했을 때 커뮤니케이션 이론이라고 불러야 한다고 생각했지만 그는 정보라는 용어를 고집했습니다. 이 용어는 이론에 대한 관심 증가와 끊임없는 좌절의 끊임없는 원인이 되었습니다. 수사관들은 전체 "정보 이론"을 구축하기를 원했고 캐릭터 세트에 대한 이론으로 퇴보했습니다. 전송 모델로 돌아가서 전송을 위해 인코딩해야 하는 데이터 소스가 있습니다.

인코더는 두 부분으로 구성되며 첫 번째 부분은 소스 인코더라고 하며 정확한 이름은 소스 유형에 따라 다릅니다. 서로 다른 데이터 유형의 소스는 서로 다른 유형의 인코더에 해당합니다.

인코딩 프로세스의 두 번째 부분은 채널 코딩이라고 하며 데이터 전송을 위한 채널 유형에 따라 다릅니다. 따라서 인코딩 프로세스의 두 번째 부분은 전송 채널 유형과 일치합니다. 따라서 표준 인터페이스를 사용할 때 소스의 데이터는 먼저 인터페이스의 요구 사항에 따라 인코딩된 다음 사용되는 데이터 전송 채널의 요구 사항에 따라 인코딩됩니다.

모델에 따르면 그림 10.1에서 데이터 링크는 "추가 무작위 노이즈"의 영향을 받습니다. 이 시점에서 시스템의 모든 노이즈가 병합됩니다. 인코더는 왜곡 없이 모든 심볼을 수신하고 디코더는 오류 없이 기능을 수행한다고 가정합니다. 이것은 약간의 이상화이지만 많은 실용적인 목적을 위해 현실에 가깝습니다.

디코딩 단계는 또한 채널 - 표준, 표준 - 데이터 수신기의 두 단계로 구성됩니다. 전송이 끝나면 데이터가 소비자에게 전송됩니다. 다시 말하지만 소비자가 이 데이터를 해석하는 방식은 고려하지 않습니다.

앞서 언급했듯이 전화 메시지, 라디오, TV 프로그램과 같은 데이터 전송 시스템은 데이터를 컴퓨터 레지스터의 숫자 집합으로 나타냅니다. 다시 말하지만 공간 전송은 시간 전송이나 정보 저장과 다르지 않습니다. 일정 시간이 지나면 필요할 정보가 있다면 인코딩하여 데이터 저장 소스에 저장해야 합니다. 필요한 경우 정보가 해독됩니다. 인코딩 및 디코딩 시스템이 동일하면 변경되지 않은 전송 채널을 통해 데이터를 전송합니다.

제시된 이론과 일반적인 물리학 이론의 근본적인 차이점은 소스와 수신기에 노이즈가 없다는 가정입니다. 사실 모든 장비에서 오류가 발생합니다. 양자역학에서 잡음은 초기 조건이 아닌 불확정성 원리에 따라 어느 단계에서나 발생한다. 어쨌든 정보 이론의 노이즈 개념은 양자 역학의 유사한 개념과 동일하지 않습니다.
명확성을 위해 시스템에서 데이터 표현의 이진 형식을 추가로 고려할 것입니다. 다른 양식도 비슷한 방식으로 처리되므로 단순성을 위해 고려하지 않습니다.

자주 등장하는 문자는 짧고 드문 문자는 긴 점과 대시의 고전적인 모스 부호에서와 같이 가변 길이의 코드화된 문자가 있는 시스템부터 시작하겠습니다. 이 접근 방식을 사용하면 높은 코드 효율성을 얻을 수 있지만 모스 부호는 점과 대시 사이에 공백 문자가 포함되어 있기 때문에 2진법이 아니라 3항이라는 점에 유의할 가치가 있습니다. 코드의 모든 문자 길이가 같은 경우 이러한 코드를 블록이라고 합니다.

코드의 첫 번째 명백한 필수 속성은 노이즈가 없을 때 메시지를 명확하게 디코딩하는 기능입니다. 적어도 이것은 바람직한 속성인 것 같지만 일부 상황에서는 이 요구 사항을 무시할 수 있습니다. 전송 채널의 데이터는 수신자에게 0과 1의 스트림으로 나타납니다.

인접한 2개의 문자를 이중 확장, 3개의 인접한 문자를 삼중 확장이라고 부르며 일반적으로 N자를 보내면 수신자는 N개의 기본 코드에 추가된 것을 보게 됩니다. N 값을 모르는 수신자는 스트림을 브로드캐스트 블록으로 나누어야 합니다. 즉, 수신자는 원본 메시지를 재구성하기 위해 고유한 방식으로 스트림을 분해할 수 있어야 합니다.

적은 수의 문자로 구성된 알파벳을 고려하십시오. 일반적으로 알파벳은 훨씬 큽니다. 언어 알파벳은 대문자와 소문자, 숫자, 기호, 문장 부호를 포함하여 16~36자로 시작합니다. 예를 들어 ASCII 테이블에서 128 = 2^7 문자입니다.
4개의 문자 s1, s2, s3, s4로 구성된 특수 코드를 고려하십시오.

s1 = 0; s2 = 00; s3 = 01; s4 = 11.

수신자가 다음 수신된 표현을 해석하는 방법

어떻게 s1s1s4또는 어떻게 s2s4?

이 질문에 명확하게 답할 수는 없습니다. 이 코드는 확실히 디코딩되지 않았으므로 만족스럽지 않습니다. 한편, 코드

s1 = 0; s2 = 10; s3 = 110; s4 = 111

고유한 방식으로 메시지를 디코딩합니다. 임의의 문자열을 수신자가 어떻게 해독할지 생각해 봅시다. 그림 10.II의 모양에 따라 디코딩 트리를 구축해야 합니다. 선

1101000010011011100010100110 …

문자 블록으로 분할 가능

110, 10, 0, 10, 0, 110, 111, 0, 0, 0, 10, 10, 0, 110, …

디코딩 트리를 구성하기 위한 다음 규칙에 따라:

트리의 맨 위에 있으면 다음 문자를 읽으십시오. 트리의 리프에 도달하면 시퀀스를 문자로 변환하고 처음으로 돌아갑니다.

이러한 트리가 존재하는 이유는 어떤 문자도 다른 문자의 접두사가 아니므로 디코딩 트리의 맨 위로 언제 돌아가야 하는지 항상 알 수 있기 때문입니다.

다음 사항에 주의할 필요가 있습니다. 첫째, 디코딩은 각 비트가 한 번만 검사되는 엄격한 스트리밍 프로세스입니다. 둘째, 프로토콜에는 일반적으로 디코딩 프로세스의 끝을 표시하고 메시지의 끝을 나타내는 데 필요한 문자가 포함됩니다.

후행 문자를 사용하지 않는 것은 코드 설계에서 흔히 범하는 실수입니다. 물론 영구적인 디코딩 모드가 제공될 수 있으며 이 경우 종료 기호가 필요하지 않습니다.

그림 10.II

다음 질문은 스트리밍(즉시) 디코딩을 위한 코드입니다. 이전 문자 매핑에서 얻은 코드를 고려하십시오.

s1 = 0; s2 = 01; s3 = 011; s4 = 111.

시퀀스가 있다고 가정합니다. 011111...111 . 메시지의 텍스트를 해독할 수 있는 유일한 방법은 그룹의 끝에서 3까지 비트를 그룹화하고 1 앞에 선행 0이 있는 그룹을 선택한 다음 해독할 수 있습니다. 이러한 코드는 고유한 방식으로 해독할 수 있지만 즉시 해독할 수는 없습니다! 디코딩하려면 전송이 끝날 때까지 기다려야 합니다! 실제로 이 접근법은 디코딩 속도를 평준화하므로(McMillan의 정리) 즉각적인 디코딩 방법을 찾아야 합니다.

동일한 문자 Si를 인코딩하는 두 가지 방법을 고려하십시오.

s1 = 0; s2 = 10; s3 = 110; s4=1110, s5=1111,

이 방법의 디코딩 트리는 그림 10.III에 나와 있습니다.

그림 10.III

두 번째 방법

s1 = 00; s2 = 01; s3 = 100; s4=110, s5=111,

이 치료의 디코딩 트리는 그림 10.IV에 나와 있습니다.

코드 품질을 측정하는 가장 확실한 방법은 일부 메시지 세트의 평균 길이입니다. 이를 위해서는 각 기호의 코드 길이에 해당 발생 확률 pi를 곱한 값을 계산해야 합니다. 이렇게 하면 전체 코드의 길이를 알 수 있습니다. q개의 알파벳에 대한 평균 길이 L 코드의 공식은 다음과 같습니다.

여기서 pi는 문자 si의 발생 확률이고, li은 인코딩된 문자의 해당 길이입니다. 효율적인 코드를 위해 L 값은 가능한 한 작아야 합니다. P1 = 1/2, p2 = 1/4, p3 = 1/8, p4 = 1/16 및 p5 = 1/16이면 코드 #1에 대해 코드 길이 값을 얻습니다.

그리고 코드 #2

얻은 값은 첫 번째 코드에 대한 선호도를 나타냅니다.
알파벳의 모든 단어의 출현 확률이 같으면 두 번째 코드가 더 바람직합니다. 예를 들어, pi = 1/5, 코드 길이 #1

그리고 코드 길이 #2

이 결과는 코드 2에 대한 선호도를 보여줍니다. 따라서 "좋은" 코드를 설계할 때 문자의 출현 확률을 고려해야 합니다.

그림 10.IV

그림 10.V

문자 코드 길이 li의 한계 값을 결정하는 Kraft의 부등식을 고려하십시오. 기저 2에 따르면 부등식은 다음과 같이 표현됩니다.

이 부등식은 알파벳에 너무 많은 짧은 문자가 있을 수 없다고 말합니다. 그렇지 않으면 합계가 상당히 커질 것입니다.

빠르고 고유한 디코딩 가능한 코드에 대한 Kraft의 부등식을 증명하기 위해 디코딩 트리를 구성하고 수학적 유도 방법을 적용합니다. 그림 10.V와 같이 나무에 하나 또는 두 개의 잎이 있으면 부등식이 참이라는 데 의심의 여지가 없습니다. 또한 트리에 2개 이상의 잎이 있는 경우 길이 m인 트리를 2개의 하위 트리로 나눕니다. 귀납법에 따르면 높이가 m -1 이하인 각 분기에 대해 부등식이 참이라고 가정합니다. 유도의 원리에 따라 부등식을 각 분기에 적용합니다. 가지 코드 K"와 K""의 길이를 나타내자. 트리의 두 가지가 병합되면 각각의 길이가 1씩 증가하므로 코드의 길이는 합계 K'/2와 K'로 구성됩니다. '/2,

정리가 입증되었습니다.

Macmillan 정리의 증명을 고려하십시오. 스트림 방식이 아닌 디코딩 가능한 코드에 크래프트 부등식을 적용해 보겠습니다. 그 증명은 어떤 숫자 K > 1에 대해 숫자의 n승이 확실히 n의 선형 함수보다 크다는 사실에 근거합니다. 여기서 n은 상당히 큰 숫자입니다. Kraft의 부등식을 n승으로 올리고 식을 합으로 나타냅니다.

여기서 Nk는 길이가 k인 문자 수이고 합계는 n번째 문자 표현의 최소 길이에서 시작하여 nl의 최대 길이에서 끝납니다. 여기서 l은 인코딩된 문자의 최대 길이입니다. 그것은 고유한 디코딩 요구 사항에서 따릅니다. 금액은 다음과 같이 표시됩니다.

K > 1이면 부등식이 거짓이 되려면 n을 상당히 크게 설정해야 합니다. 따라서 k<= 1; теорема Макмиллана доказана.

Kraft의 부등식을 적용한 몇 가지 예를 살펴보겠습니다. 길이가 1, 3, 3, 3인 고유하게 디코딩 가능한 코드가 있을 수 있습니까? 예, 왜냐하면

길이 1, 2, 2, 3은 어떻습니까? 공식에 따라 계산

불평등이 위반되었습니다! 이 코드에 짧은 문자가 너무 많습니다.

도트 코드(쉼표 코드)는 모두 1로 구성된 마지막 문자를 제외하고 문자 0으로 끝나는 문자 1로 구성된 코드입니다. 특별한 경우 중 하나는 코드입니다.

s1 = 0; s2 = 10; s3 = 110; s4 = 1110; s5= 11111.

이 코드의 경우 Kraft 부등식에 대한 표현식을 얻습니다.

이 경우 평등을 달성합니다. 포인트 코드의 경우 Kraft의 부등식이 등식으로 변질되는 것을 쉽게 알 수 있습니다.

코드를 작성할 때 Kraft 합계에 주의를 기울여야 합니다. Kraft 합계가 1을 초과하기 시작하면 평균 코드 길이를 줄이기 위해 다른 길이의 기호를 포함하라는 신호입니다.

Kraft의 부등식은 이 코드가 고유하게 디코딩 가능하다고 말하는 것이 아니라 고유하게 디코딩 가능한 그러한 길이의 기호를 가진 코드가 있다는 점에 유의해야 합니다. 고유한 디코딩 가능한 코드를 구축하기 위해 비트 li의 해당 길이를 이진수로 할당할 수 있습니다. 예를 들어 길이가 2, 2, 3, 3, 4, 4, 4, 4인 경우 Kraft 부등식을 얻습니다.

따라서 이러한 고유한 디코딩 가능한 스트림 코드가 존재할 수 있습니다.

s1 = 00; s2 = 01; s3 = 100; s4 = 101;

S5 = 1100; s6 = 1101; s7 = 1110; s8 = 1111;

우리가 아이디어를 교환할 때 실제로 일어나는 일에 주목하고 싶습니다. 예를 들어, 이 시점에서 내 머리의 아이디어를 당신의 머리로 옮기고 싶습니다. 나는 당신이 이 생각을 이해할 수 있을 것이라고 믿는 몇 가지 말을 하고 있습니다.

그러나 나중에 이 아이디어를 친구에게 전달하고 싶을 때 완전히 다른 단어를 말할 것입니다. 실제로 의미 또는 의미는 특정 단어에 포함되어 있지 않습니다. 몇 가지 단어를 사용했지만 같은 생각을 전달하기 위해 완전히 다른 단어를 사용할 수 있습니다. 따라서 서로 다른 단어가 동일한 정보를 전달할 수 있습니다. 그러나 대담 자에게 메시지를 이해하지 못한다고 말하면 원칙적으로 대담자는 의미, 두 번째 또는 세 번째를 전달하기 위해 다른 단어 집합을 선택합니다. 따라서 정보는 특정 단어 집합에 포함되지 않습니다. 특정 단어를 받으면 대담자가 전달하려는 아이디어로 단어를 번역하는 훌륭한 작업을 수행하십시오.

대담 자에게 적응하기 위해 단어를 선택하는 법을 배웁니다. 어떤 의미에서 우리는 우리의 생각과 채널의 노이즈 수준에 따라 단어를 선택하지만 이러한 비교는 디코딩 프로세스에서 노이즈를 나타내는 데 사용하는 모델을 정확하게 반영하지 않습니다. 대규모 조직에서 심각한 문제는 대담자가 상대방의 말을 들을 수 없다는 것입니다. 높은 위치에 있는 직원은 "듣고 싶은 것"을 듣습니다. 어떤 경우에는 회사 사다리를 올라갈 때 이것을 염두에 두어야 합니다. 정형화된 형태의 정보 표현은 우리 삶의 과정을 부분적으로 반영한 것이며 컴퓨터 응용 프로그램에서 정형 규칙의 경계를 훨씬 넘어서는 광범위한 적용을 발견했습니다.

계속하려면...

책의 번역, 레이아웃 및 출판을 돕고 싶은 사람 - 개인 또는 이메일로 작성 [이메일 보호]

그건 그렇고, 우리는 또 다른 멋진 책의 번역을 시작했습니다.

다양한 정보 소스와 전송 채널을 분석하려면 메시지에 포함되고 신호에 의해 전달되는 정보의 양을 추정할 수 있는 정량적 측정이 필요합니다. 이러한 조치는 미국 과학자 C. Shannon에 의해 1946년에 도입되었습니다.

또한, 우리는 정보 소스가 불연속적이라고 가정하고 기본 메시지 시퀀스(i,)를 제공하며 각 메시지는 개별 앙상블(알파벳) a, a 2 ,...,d A에서 선택됩니다. 에게정보 소스의 알파벳 볼륨입니다.

각 기본 메시지에는 고려 중인 정보 소스의 상태에 대한 정보 집합(고려 중인 예에서)으로 특정 정보가 포함되어 있습니다. 이 정보의 척도를 정량화하기 위해 의미론적 내용과 수신자에 대한 이 정보의 중요성 정도는 중요하지 않습니다. 메시지를 받기 전에 수신자는 항상 내가 어떤 메시지인지 확신하지 못합니다. 가능한 모든 것 중에서 그에게 주어질 것입니다. 이 불확실성은 메시지 i 전송의 사전 확률 P(i)를 사용하여 추정됩니다. 개별 소스의 기본 메시지에 포함된 정보의 객관적인 양적 척도는 주어진 메시지를 선택할 확률에 의해 설정되고 이 확률의 함수로 cc를 결정한다고 결론을 내립니다. 동일한 기능이 개별 소스의 상태와 관련하여 정보 수신자가 갖는 불확실성의 정도를 나타냅니다. 예상 정보에 대한 불확실성의 정도가 정보 전송 채널에 대한 요구 사항을 결정한다고 결론 내릴 수 있습니다.

일반적으로 확률 아빠,)일부 기본 메시지 i(이하 기호라고 함)의 소스 선택은 이전에 선택한 기호에 따라 달라집니다. 조건부 확률이며 그러한 선택의 선험적 확률과 일치하지 않습니다.

팀 그 ^ 아빠:) = 1, 모든 i가 완전한 이벤트 그룹을 형성하기 때문에

gyi), 이러한 기호의 선택은 일부 기능 종속성을 사용하여 수행됩니다. J(a,)= P(a,) = 1, 소스에 의한 기호 선택이 선험적으로 결정된 경우, J(a,)= „ ㅏ 피(에이티,에이)가 그러한 선택의 확률이면 한 쌍의 기호에 포함된 정보의 양은 각 기호 i와 i에 포함된 정보의 양의 합과 같습니다. 정보의 양적 척도의 이러한 속성을 가산성이라고 합니다. .

우리는 믿습니다 아빠,)- 앞에 있는 모든 문자 다음에 문자 i를 선택할 조건부 확률 아빠,,i,)는 기호 i를 선택할 조건부 확률입니다. i 이후, 그리고 이전의 모든 것, 그러나 피 (a 1, a 1) \u003d 피 (a) P(i,|i y), 덧셈 조건은 다음과 같이 쓸 수 있습니다.

표기법을 소개합니다 아빠) = P p P (ar) \u003d Q재작성 조건(5.1):

우리는 믿습니다 R, O* 0. 식(5.2)을 사용하여 함수의 형식을 결정합니다(p (아르 자형).미분하여 곱하기 아르 자형* 0 및 표시 RO = 아르 자형,써 내려 가다

관계식 (5.3)이 만족됨을 유의하십시오. R f O u^^O. 그러나 이 요구 사항은 (5.3)의 오른쪽과 왼쪽의 불변성으로 이어집니다. Pq>"(피)=아르"(/?) - 에게 - const. 그런 다음 방정식에 도달합니다. PC> "(피) = 에게통합 후 우리는

우리가 다시 쓸 것이라는 점을 고려하자

결과적으로 J(a,)의 속성에 대한 두 가지 조건이 충족되면 함수 종속의 형태가 J(a,)기호를 선택할 확률 에일정한 계수까지 에게고유하게 정의된

계수 에게척도에만 영향을 미치고 정보량을 측정하는 단위 체계를 결정합니다. ln[P]부터 에프 0이면 선택하는 것이 합리적입니다. 정보량의 척도가 되도록 Os에게 J(가)긍정적이었다.

받아 들인 케이=-1, 기록

따라서 정보량의 단위는 이벤트가 발생했다는 정보와 같으며 그 확률은 다음과 같습니다. 나.이러한 정보량의 단위를 자연단위라고 한다. 다음과 같이 가정하는 경우가 더 많습니다. 에게= - 그러면

따라서 우리는 확률이 같은 두 가지 이벤트 중 하나의 발생에 대한 메시지를 포함하고 "비트"라고 하는 정보량의 이진 단위에 도달했습니다. 이 장치는 통신 기술에서 이진 코드를 사용하기 때문에 널리 보급되었습니다. 일반적인 경우에 로그의 밑을 선택하면 다음을 얻습니다.

여기서 로그는 임의의 밑을 가질 수 있습니다.

정보의 정량적 척도의 가산성 속성은 표현(5.9)에 기초하여 일련의 문자로 구성된 메시지의 정보량을 결정할 수 있게 합니다. 소스가 이러한 시퀀스를 선택할 확률은 이전에 사용 가능한 모든 메시지를 고려하여 고려됩니다.

기본 메시지에 포함된 정보의 정량적 측정 a(, 평균 정보량에 대한 아이디어를 제공하지 않음 J(A) 하나의 기본 메시지가 선택될 때 소스에서 발행 기원 후

정보의 평균량은 정보의 출처를 전체적으로 특징 짓고 통신 시스템의 가장 중요한 특성 중 하나입니다.

알파벳을 사용하여 독립적인 메시지의 개별 소스에 대해 이 특성을 정의해 보겠습니다. 에게.로 표시 에)문자당 평균 정보량이며 랜덤 변수의 수학적 기대치입니다. L - 무작위로 선택된 문자에 포함된 정보의 양 ㅏ

기호당 평균 정보량을 독립 메시지 소스의 엔트로피라고 합니다. 엔트로피는 다음 문자를 선택할 때 평균 선험적 불확실성을 나타내는 지표입니다.

확률 중 하나가 아빠) 1과 같으면(따라서 다른 모든 항목은 0과 같음) 정보 소스의 엔트로피가 0이 됩니다. 메시지가 완전히 정의됩니다.

가능한 모든 기호의 사전 확률이 같으면 엔트로피가 최대가 됩니다. 에게, 즉. R(a() = 1 /에게,그 다음에

소스가 확률이 P인 이진 기호를 독립적으로 선택하는 경우 = 피(엑스)및 P 2 \u003d 1-P이면 문자 당 엔트로피는

무화과. 16.1은 두 개의 이진 기호 중에서 선택할 선험적 확률에 대한 이진 소스의 엔트로피의 의존성을 보여줍니다. 이 그림은 또한 엔트로피가 R에서 최대임을 보여줍니다. = R 2 = 0,5

1 o 1 dvd - 이진 단위 log 2 2 = 1-

쌀. 5.1. 엔트로피 의존성 케이 =둘 중 하나를 선택할 확률에 대해 2

동일한 확률로 기호를 선택했지만 알파벳 크기가 다른 소스의 엔트로피 에게,성장에 따라 대수적으로 증가 에게.

기호를 선택할 확률이 다르면 소스의 엔트로피가 떨어집니다. 나(A)가능한 최대값에 비례 H(A) psh =통나무 에게.

기호 간의 상관 관계가 클수록 후속 기호를 선택할 자유가 줄어들고 새로 선택한 기호에 대한 정보가 줄어듭니다. 이는 조건부 분포의 불확실성이 무조건 분포의 엔트로피를 초과할 수 없기 때문입니다. 소스의 엔트로피를 메모리와 알파벳으로 표시 에게~을 통해 H(AA"),그리고 메모리가 없는 소스의 엔트로피, 하지만 같은 알파벳으로 - 통해 에)부등식을 증명하고

표기법을 도입하여 P(아")기호를 선택할 조건부 확률 a,(/ = 1, 2, 에게)기호가 이전에 선택되었다고 가정 아지즈 =1,2,에게)변환을 생략하고 증명 없이 작성합니다.

불평등을 증명합니다 (5.13).

(5.13) 또는 (5.14)의 평등은 다음과 같은 경우에 달성됩니다.

이것은 기호를 선택할 조건부 확률이 기호를 선택할 무조건적 확률과 같다는 것을 의미하며, 이는 메모리 없는 소스에서만 가능합니다.

흥미롭게도 러시아어 텍스트의 엔트로피는 문자당 1.5 이진 단위입니다. 동시에 같은 알파벳으로 케이= 32 독립적이고 동등한 가능성이 있는 기호의 조건 H(A) tp =문자당 5개의 이진수. 따라서 내부 링크가 있으면 엔트로피가 약 3.3배 감소합니다.

개별 소스의 중요한 특성은 중복성 p와 다음과 같습니다.

정보 출처의 중복성은 . 중복성이 없으면 당연히 p u = 0입니다.

심볼간 상관관계가 없는 소스에서 일정량의 정보를 전송하기 위해 모든 심볼의 동일한 확률로 전송 가능한 최소 심볼 수 /7 min: /r 0 (/7 0 R (L max)) 필요합니다. 엔트로피가 있는 소스에서 동일한 양의 정보를 전송하려면(기호가 상호 연결되어 있고 확률이 같지 않음) 평균 기호 수가 필요합니다. n = n'H(A) m JH(A).

이산 소스는 또한 시간 단위당 기호 수 v H에 의해 결정되는 성능으로 특징지어집니다.

성능이라면 나(A)이진 단위로 정의하고 시간을 초 단위로 정의한 다음 ON THE) -초당 이진 단위 수입니다. 길이가 충분히 큰 고정 문자 시퀀스를 생성하는 이산 소스의 경우 다음 개념이 도입됩니다. 피.모든 일반적인 시퀀스 NlMl (A)출처 피-»oo는 거의 동일한 발생 확률을 가짐

모든 비정형 시퀀스의 총 발생 확률은 0이 되는 경향이 있습니다. 평등(5.11)에 따라 일반적인 시퀀스의 확률이 다음과 같다고 가정합니다. /Nrm(A),소스의 엔트로피는 logN TIin(,4)이고 다음

노이즈가 있는 개별 채널을 통한 정보 전송의 양과 속도를 고려하십시오. 이전에는 일련의 문자(i,) 형식으로 개별 소스에서 생성된 정보를 고려했습니다.

이제 소스 정보가 인코딩되어 일련의 코드 기호를 나타낸다고 가정합니다. (비, (/ = 1,2,..티 -코드베이스)는 일련의 기호가 나타나는 출력에서 개별 정보 전송 채널과 일치합니다.

인코딩 작업이 문자 순서에 따라 일대일이라고 가정합니다. (비,)시퀀스(i,)를 고유하게 복원할 수 있습니다. 코드 기호로 소스 정보를 완전히 복원할 수 있습니다.

그러나 이스케이프 문자 |?를 고려하면. j와 기호(/>,)를 입력하면 정보 전송 채널에 간섭이 존재하여 복구가 불가능합니다. 출력 시퀀스의 엔트로피 //(/?)

입력 시퀀스의 엔트로피보다 클 수 있음 H(B) 수신자에 대한 정보량이 증가하지 않았습니다.

최상의 경우에는 입력과 출력의 일대일 관계가 가능하고 유용한 정보가 손실되지 않으며 최악의 경우 정보 전송 채널의 출력 심볼에서 입력 심볼에 대해 아무 말도 할 수 없으며, 유용한 정보는 채널에서 완전히 손실됩니다.

잡음이 있는 채널에서 정보 손실과 잡음이 있는 채널을 통해 전송되는 정보의 양을 추정해 보겠습니다. 전송된 문자 6으로 수신되면 문자가 올바르게 전송된 것으로 간주합니다.

상징 비제이같은 숫자(/= 제이).그런 다음 노이즈가 없는 이상적인 채널을 위해 다음과 같이 작성합니다.

기호로 비제이-불평등으로 인한 채널 출력에서(5.21)

불확실성은 불가피하다. 기호의 정보는 다음과 같다고 가정할 수 있습니다. 비 나는완전히 전송되지 않고 일부가 간섭으로 인해 채널에서 손실됩니다. 정보의 정량적 측정 개념을 기반으로 기호 ft를 받은 후 채널의 출력에서 발생하는 불확실성의 수치적 표현을 가정합니다. :

전송 중 채널에서 손실된 정보의 양을 결정합니다.

고정 피트 . 가능한 모든 기호에 대해 평균화(5.22)하여 합계를 얻습니다.

심볼을 수신할 때 메모리가 없는 채널을 통해 기본 심볼을 전송할 때 채널에서 손실되는 정보의 양을 결정합니다. 비제이(t).

모든 ft에 대한 합계(5.23)를 평균화할 때 값 Z?)를 얻습니다. n(in/in-메모리 없는 채널을 통해 한 문자를 전송할 때 손실되는 정보의 양을 결정합니다.

어디 P^bjbjj-전송될 때 이벤트의 공동 확률

상징 비.그것은 기호를 취할 것입니다 비티.

H [w/정보 출처의 특성에 따라 다름

채널 입력 안에그리고 통신 채널의 확률적 특성에 대해. 통계 커뮤니케이션 이론의 Shannon에 따르면 n(in/in채널 비신뢰성이라고 합니다.

조건부 엔트로피 HB/B, 이산 소스의 엔트로피

채널 입력에서 H(원)그리고 엔트로피 그리고 ^B) 출력에서

부정적인. 간섭이 없는 채널에서 채널 불안정성

n(v/v = 0. (5.20)에 따라 ㅎ^v/v^

채널의 입력과 출력이 통계적으로 독립적인 경우에만 평등이 발생합니다.

출력 기호는 입력 기호에 의존하지 않습니다. 채널이 끊어지거나 간섭이 매우 강한 경우입니다.

이전과 마찬가지로 일반적인 시퀀스의 경우 다음과 같이 작성할 수 있습니다.

간섭이 없으면 신뢰성이 떨어집니다.

채널을 통해 평균적으로 전송되는 정보에서 J[ b/ 기호 당 채널 입력에서 정보량의 차이를 이해합니다. 제이(비)및 /? 채널에서 손실된 정보).

정보 소스와 채널에 메모리가 없으면

식(5.27)은 채널 출력 기호의 엔트로피를 결정합니다. 채널 출력 정보의 일부는 유용하고 나머지는 채널의 간섭에 의해 생성되기 때문에 거짓입니다. 참고하자 n[v/ 2?)는 채널에서의 간섭에 대한 정보를 표현하고, 차이 i(d)-I(d/d) - 채널을 통과한 유용한 정보를 나타낸다.

채널의 출력에서 형성된 대부분의 시퀀스는 비정형이며 전체 확률이 매우 작습니다.

일반적으로 간섭의 가장 일반적인 유형인 추가 잡음이 고려됩니다. N(t);채널 출력 신호의 형식은 다음과 같습니다.

이산 신호의 경우 (5.28)에 따른 등가 잡음은 이산 구조를 갖습니다. 노이즈는 입력 및 출력 신호의 시퀀스와 유사한 불연속 무작위 시퀀스입니다. C1 = 0, 1,2와 같이 불연속 채널에서 가산성 잡음의 알파벳 기호를 나타내자. 티- 1). 이러한 채널의 조건부 전환 확률

왜냐하면 그리고 (^B/?) 그리고 (B) 결과적으로 입력에 대한 이산 채널 #(/)의 출력 시퀀스 정보 비(티)혹은 그 반대로도 및 (B) - H^in/in)(5).

즉, 채널을 통해 전송되는 정보는 입력된 정보를 초과할 수 없습니다.

채널 입력이 평균을 받는 경우 엑스케이 1초에 기호를 사용하면 잡음이 있는 채널을 통한 평균 정보 전송 속도를 결정할 수 있습니다.

어디 Н(В) = V k J(B,B^ -채널 입력에서의 소스 성능; n (in / in) \u003d U에서 n (in, in) ~단위 시간당 채널의 불안정성; H (B) = Vk H^B^- 채널의 출력에 의해 형성된 소스의 성능(유용한 정보의 일부와 잘못된 정보의 일부 제공) H ^ in / B ^ \u003d U에서 1 / (in / in)- 허위 정보의 양,

단위 시간당 채널에 간섭을 생성했습니다.

채널을 통한 정보 전송의 양과 속도에 대한 개념은 통신 채널의 다양한 섹션에 적용될 수 있습니다. 이것은 "인코더 입력 - 디코더 출력" 섹션일 수 있습니다.

고려 중인 채널의 섹션을 확장하면 구성 요소의 속도를 초과할 수 없습니다. 되돌릴 수 없는 변환은 정보 손실로 이어집니다. 돌이킬 수 없는 변환에는 간섭의 영향뿐만 아니라 감지, 중복 코드를 사용한 디코딩도 포함됩니다. 수신 손실을 줄이는 방법이 있습니다. 이것은 "일반적인 수신"입니다.

개별 채널의 대역폭과 최적 코딩 정리를 고려하십시오. Shannon은 입력 신호의 앙상블에 대한 여러 제한 하에서 알려진 속성(노이즈)을 가진 채널을 통해 가능한 최대 정보 전송 속도를 결정하는 특성을 도입했습니다. 이것은 채널 C의 대역폭입니다. 이산 채널의 경우

가능한 입력 소스에 의해 최대값이 보호되는 경우 안에주어진 Vk및 입력된 문자 알파벳의 볼륨 티.

개별 채널의 처리량 정의에 따라 다음과 같이 작성합니다.

독립적인 입력 및 출력(채널의 높은 노이즈 레벨)에서 C = 0이므로,

신호에 대한 간섭 간섭이 없는 경우.

메모리가 없는 이진 대칭 채널의 경우

쌀. 5.2.

파라미터에 대한 바이너리 채널 용량의 의존성 그래프 아르 자형그림에 나와 있습니다. 5.2. ~에 아르 자형= 1/2 채널 대역폭 C = 0, 조건부 엔트로피

//(/?//?) = 1. 실질적인 관심

그래프는 0을 나타냅니다.

최적 코딩에 대한 Shannon의 기본 정리는 용량 개념과 관련이 있습니다. 개별 채널에 대한 공식은 다음과 같습니다. 메시지 소스의 성능이 에)채널 C의 대역폭보다 작음:

최적의 코딩 및 디코딩 방법이 있으며, 채널의 오류 또는 비신뢰성 가능성이 있습니다. n[a!A j는 임의로 작을 수 있습니다. 만약에

그런 방법은 없습니다.

Shannon의 정리에 따라 유한 값 와 함께채널을 통한 오류 없는 정보 전송 속도의 한계 값입니다. 그러나 잡음이 많은 채널의 경우 최적의 코드를 찾는 방법은 나와 있지 않습니다. 그러나이 정리는 정보 전송 기술의 근본적인 가능성에 대한 견해를 근본적으로 바 꾸었습니다. Shannon 이전에는 잡음이 많은 채널에서 정보 전송 속도를 0으로 줄임으로써 임의로 작은 오류 확률을 얻을 수 있다고 믿었습니다. 예를 들어 이것은 메모리 없는 채널에서 문자 반복의 결과로 통신 충실도가 증가합니다.

Shannon의 정리에 대한 몇 가지 엄격한 증명이 알려져 있습니다. 정리는 무작위 코딩에 의해 이산 메모리리스 채널에 대해 증명되었습니다. 이 경우, 주어진 소스 및 주어진 채널에 대해 임의로 선택된 모든 코드 집합이 고려되고 모든 코드에 대한 평균 오류 디코딩 확률의 0에 대한 점근적 접근 방식의 사실이 기간의 무제한 증가로 주장됩니다. 메시지 순서. 따라서, 무오류 복호화 가능성을 제공하는 부호가 존재한다는 사실만이 증명될 뿐 명확한 부호화 방법은 제시되지 않는다. 동시에, 증명 과정에서 메시지 시퀀스의 앙상블과 전송에 사용되는 일대일 대응 코드 단어 세트의 엔트로피의 동등성을 유지하면서 앙상블은 안에코드 기호 시퀀스의 상호 의존성을 높이기 위해 추가적인 중복성을 도입해야 합니다. 이는 코드 단어가 선택된 코드 시퀀스 세트를 확장해야만 수행할 수 있습니다.

노이즈 채널에 대한 주요 코딩 정리가 특정 코드를 선택하는 명확한 방법을 나타내지 않고 정리의 증명에도 없다는 사실에도 불구하고 충분히 긴 메시지를 인코딩할 때 대부분의 무작위로 선택된 코드는 다음과 같이 표시될 수 있습니다. 잘못된 디코딩의 평균 확률을 약간 초과합니다. 그러나 긴 블록의 실제 코딩 가능성은 메모리 시스템 구현의 어려움과 엄청난 수의 코드 요소 시퀀스의 논리적 처리, 정보 전송 및 처리의 지연 증가로 인해 제한됩니다. 사실, 특히 흥미로운 것은 유한한 기간 동안 잘못된 디코딩의 확률을 결정할 수 있게 해주는 결과입니다. 피사용된 코드 블록. 실제로는 중간 정도의 지연 값으로 제한되며 채널 대역폭을 불완전하게 사용하여 전송 확률을 높입니다.