Спирина, М.С. Дискретная математика

которые возможно передавать по этому каналу связи за единицу времени. Для каналов связи с помехами справедлива вторая теорема Шеннона ( прямая теорема кодирования), согласно которой всегда существует способ кодирования, такой, что информация может быть передана с какой угодно высокой достоверностью при боль­ шой длине передаваемых слов, если скорость передачи не выше пропускной способности канала связи. Пусть кодом являются N слов qu q2, q^ длины п. Пусть p(qt) — вероятность неправиль- 1 N ной передачи сообщения q ,. Тогда величина — £ р, будет сред- ™ i=i ней вероятностью ошибки. Минимальную среднюю ошибку сре­ ди всевозможных кодов обозначим р(п, М). Тогда скоростью пе ­ редачи будет R =\og2N / п. Теорема Шеннона утверждает, что при R < С p (n ,N )— - эО. Таким образом, вторая теорема Шеннона доказывает принци­ пиальную возможность помехоустойчивого кодирования. Обоснован­ ная Шенноном, схема передачи данных представлена в общем виде на рис. 6.7. Кодирующее устройство преобразует некоторое сообщение в код т2. В канале связи за счет помех (шумов) сообщение может быть искажено: т2 -> ту Декодирующее устройство преобразует сообщение тг в т2. Затем т2 преобразуется в /я*. При кодировании кодер канала обеспечивает заданную досто­ верность сообщения в процессе ее передачи и хранения. Однако из-за помех в канале связи при декодировании возможны искаже­ ния. Поэтому возможно преобразование сообщения т3 не в т2, а в /я2‘ (искаженное т2), а затем в /я/ (искаженное тх). Сформулируем три глобальные проблемы кодирования: . создание шифра кодирования; Помехи Рис. 6.7. Обобщенная схема передачи данных 319