Часть I. ОСНОВЫ ЦИФРОВОЙ СВЯЗИ И БЛОЧНОГО КОДИРОВАНИЯ

Глава 1. ЦИФРОВЫЕ СИСТЕМЫ СВЯЗИ: ФУНДАМЕНТАЛЬНЫЕ КОНЦЕПЦИИ И ПАРАМЕТРЫ

Если первую половину двадцатого века можно считать эрой радиосвязи, развитие которой привело к созданию методов (в основном аналоговых) надежной передачи сообщений, в том числе речевых, и телевизионных изображений, то вторую половину двадцатого века следует признать эрой развития цифровой связи.

Толчком к совершенствованию методов цифровой связи послужили три обстоятельства:

1) Определяемые целым рядом приложений растущие потребности в передаче данных самых разнообразных типов, от информации в банках данных ЭВМ до информации от удаленных оконечных устройств, в сочетании с возрастающими требованиями к точности передачи;

2) Быстрое развитие систем с синхронными искусственными спутниками связи, что хотя и облегчило глобальную связь при весьма высоких скоростях передачи данных, но в силу высокой стоимости запуска и вызванных этим ограничений на мощность и полосу частот потребовало отыскания эффективных методов использования ресурсов канала;

3) Создание сетей связи, одновременно обслуживающих многих пользователей с различными скоростями и при различных требованиях. Из экономических соображений здесь на первый план выступают методы простого и эффективного уплотнения данных и многократный доступ к каналам.

Перечисленные направления эволюционировали всю третью четверть двадцатого века параллельно с полупроводниковой технологией, необходимой для создания эффективных, гибких и надежных систем цифровой связи. Теоретические основы последних были заложены в сороковые годы К. Е. Шенноном в его прославленной работе «Математическая теория связи» [1948]. С редкостной интуицией Шеннон почувствовал, что надежная цифровая связь по каналам связи и максимально эффективное преобразование аналоговых сигналов в цифровую форму — двойственные аспекты одной проблемы и, следовательно, допускают общее описание и почти одинаковое решение. Это решение, по существу, появилось уже

в основополагающей работе Шеннона. Следующие два десятилетия целый ряд исследователей был занят уточнением и украшением теории и переводом ее на язык практических разработок; их усилиям сопутствовало развитие технологии, необходимой для реализации продиктованных теорией методов и алгоритмов.

Двойственную проблему, сформулированную и решенную Шенноном, лучше всего описать с помощью структурной схемы, приведенной на рис. 1.1. Источник моделируется как случайный генератор данных или как подлежащий передаче стохастический сигнал.

Рис. 1.1. Основная модель системы цифровой связи

Кодер источника осуществляет отображение выхода источника в дискретную последовательность (обычно двоичную). Отображение, осуществляемое кодером может быть взаимно однозначным, если сам источник имеет дискретный выход. На некоторое время заменим канал с кодером и декодером (обведено пунктиром на рис. 1.1) непосредственным соединением, называемым каналом без шума. Если отображение кодера источника взаимно однозначно, то декодер источника, осуществляя только обратное отображение, предоставляет получателю информацию, в точности совпадающую с созданной источником. Следовательно, назначение пары кодер-декодер источника заключается в минимальном представлении выхода источника. Мерой достигаемого сжатия данных служит скорость выраженная числом символов (обычно двоичных) в единицу времени, которое необходимо для полного представления и последующего восстановления декодером источника выходной последовательности источника. Минимальная скорость, с которой последовательность стохастического дискретного источника может быть передана по каналу без шума с последующим точным восстановлением, связана с основным параметром стохастического источника, называемым энтропией.

Выходной сигнал аналогового источника нельзя точно представить дискретной последовательностью, поскольку последовательность на выходе источника принимает значения из несчетного множества, которое, очевидно, нельзя отобразить взаимно однозначно на дискретное множество, т. е. на дискретный алфавит. Лучшее, что можно сделать, отображая такой источник в дискретную последовательность, — это примириться с некоторыми искажениями, остающимися после обработки декодером источника,

осуществляющего здесь всего лишь аппроксимацию обратного отображения. В таких случаях фиксируется максимально допустимое искажение (соответствующим образом введенное), и цель состоит в минимизации скорости вновь определяемой числом дискретных символов в единицу времени, при ограничениях на искажения. При решении этой задачи возникает необходимость в обобщении энтропии источника, называемом скоростью как функцией погрешности. Указанная функция погрешности задает минимальную скорость, с которой выходная последовательность источника может быть передана по каналу без шума и восстановлена с заданной погрешностью.

Двойственной к первой оказывается проблема надежной передачи дискретной последовательности (выходной последовательности кодера источника) по каналу с шумом. Рассмотрим теперь блоки, обведенные пунктиром на рис. 1.1. Будем трактовать канал с шумом как случайное отображение входной последовательности, определенной на заданном дискретном множестве (дискретном алфавите в выходную последовательность, определенную на произвольном множестве не обязательно совпадающем с входным. Фактически для большинства физических каналов выходное пространство часто непрерывно (несчетно), хотя довольно часто рассматривают и дискретные модели, каналов.

Задачи кодера и декодера канала заключаются в осуществлении отображений входной дискретной последовательности в последовательность на входе канала, и обратно, последовательности на выходе канала в выходную дискретную последовательность: Эти отображения должны минимизировать влияние шума канала, т. е. минимизировать число различий между входной и выходной дискретными последовательностями. Такой подход основан на введении избыточности кодером канала с последующим ее использованием декодером канала для возможно более точного восстановления входной последовательности. Грубо говоря, кодирование в канале двойственно кодированию источника в том смысле, что последнее убирает или уменьшает избыточность, тогда как первое вводит ее в целях уменьшения ошибок. Этой двойственности, как станет ясно читателю, прочитавшему книгу до конца, можно придать гораздо более точный количественный смысл.

Сформулируем самый замечательный вывод шенноновской теории кодирования в канале: введя при кодировании в канале достаточную, но конечную избыточность, декодером канала можно восстановить входную последовательность с любой желаемой точностью. Мера вводимой избыточности определяется скоростью, равной числу дискретных символов в единицу времени на входе кодера и на выходе декодера канала. Эта скорость, численно совпадая со скоростью на выходе кодера источника и на входе декодера источника, должна ввиду избыточности быть меньше скорости передачи в канале. Главный результат работы Шеннона заключается в том, что если скорость на входе кодера канала не превышает некоторого предела, определяемого пропускной

способностью канала (основного параметра канала, представляющего собой функцию от задающего канал условного распределения), то существуют такие операции кодирования и декодирования, которые асимптотически (при достаточно длинных последовательностях) могут привести к безошибочному восстановлению входной последовательности.

Из теории кодирования источника и теории кодирования в канале следует, что если минимальная скорость, при которой дискретная последовательность источника может быть однозначно представлена кодером источника, меньше максимальной скорости, при которой выходная последовательность канала может быть безошибочно восстановлена декодером канала, то приведенная на рис. 1.1 система может передать цифровые данные от источника к получателю со сколь угодно большой точностью. Это справедливо и для аналоговых источников с той разницей, что при определенных (допустимых) искажениях, задающих минимальную скорость источника, эта скорость должна быть меньше упомянутой максимальной скорости канала.

Настоящая книга ставит своей целью представить количественно указанные фундаментальные понятия теории систем цифровой связи и показать их применимость к существующим каналам и источникам.

В первой главе введены основные числовые характеристики — энтропия источника и пропускная способность канала — и положено начало выяснению их смысла. Показано, что энтропия является ключевым параметром теоремы кодирования без шума для источника, приведенной в § 1.1. Аналогичная роль пропускной способности канала частично объяснена в § 1.3: в процессе доказательства обращения теоремы кодирования в канале устанавливается, что ни при какой скорости, превышающей предельную предписываемую пропускной способностью, ни одна пара кодер-декодер канала не позволяет добиться безошибочного восстановления. Смысл пропускной способности выясняется полностью только в следующих двух главах. В гл. 2 определяются и вводятся модели каналов, представляющих наибольший интерес для проектировщика систем связи; там же даются начальные понятия кодирования и декодирования в канале. В гл. 3 заканчивается доказательство теоремы кодирования в канале для специального класса кодов канала, называемых блочными кодами, и, таким образом, выясняется полностью значение пропускной способности.

Хотя потенциальные возможности кодирования в канале выявляются в гл. 3, применимость его на практике и способы аппаратурной реализации остаются не ясными. Рассмотрению этого вопроса посвящена гл. 4, где описан наиболее пригодный для практического использования мощный класс кодов, называемых сверточными, для которых операция кодирования в канале выполняется цифровым линейным фильтром, а декодирования — естественным образом связана с простыми свойствами самого кода. В гл. 5 свойства таких кодов сравниваются со свойствами блочных кодов,

изученными в гл 3. Затем в гл. 6 исследуется другая процедура декодирования называемая последовательным декодированием. Эта процедура позволяет при определенных условиях и ограничениях использовать весьма мощные сверточные коды.

Наконец в гл 7 мы возвращаемся к задаче кодирования источника, впервые рассматривая здесь аналоговые источники и основы теории передачи с погрешностью для источников без памяти. Обсуждаются методы блочного и сверточного кодирования, чем устанавливается довольно примечательная двойственность между постановками и решениями задач кодирования источников и кодирования в каналах. В гл. 8 концепции гл. 7 обобщаются на источники с памятью, а также приводятся более общие результаты теории передачи с погрешностью.

Шенноновская математическая теория связи почти с самого начала получила название теории информации. И хотя один из аспектов указанной теории связан с определением информации и выяснением ее смысла с позиций инженера, к главным достижениям теории следует отнести выяснение возможностей и ограничении систем цифровой связи. Естественно, тем не менее, начать с количественных определений информации в форме, полезной для инженера-связиста. Это побуждает нас дать в § 1.1 определение энтропии и выявить ее роль как основной числовой характеристики кодирования дискретного источника.