Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
•^1, 2> • • • > Х\, fj), ... , Хт = (Хт, 1 > • • •, Хт, n)i • ¦ • > ХМ = (Хм, 1 > • • ч
• хм. n)- Соответствие между целыми числами от 1 до М и двоичными последовательностями является произвольным и может быть выбрано, например, как запись этих целых чисел в двоичной системе. Однако
133
каким бы это соответствие ни было, оно будет считаться фиксированным, и когда двоичная последовательность, соответствующая целому числу т, поступает на кодер, то кодовое слово хт передается по каналу. Рис. 5.1.2 дает пример блокового кода с длиной блока 5 для канала, входной алфавит которого состоит из трех букв. Если, например, на кодер поступает последовательность (0,1), то по каналу передается последовательность (2, 2, 1,0, 1). Предположим здесь, что т8/тс = = 6/2, так что 5 символов канала могут быть переданы за время, требуемое для поступления двух двоичных символов в кодер.
Скорость R блокового кода определяется как
log М Llog2
R
N
N
(5.1.2)
Если LtJxc является целым числом, то согласно (5.1.1) это выражение преобразуется к виду R = (tc/ts) log 2. Таким образом, R в битах
поо-ледова - Кодовое
тельносгль т слово хт
00 1 0 0 0 0 0
01 2 11110
10 Ъ Z 2 1 0 1
11 ? о z 2 г г
Канал
,98 г. Л
01vS<'v
,98
Рис. 5.1.2. Код с блоковой длиной N—5 и М=4 кодовыми словами.
(т. е. при использовании log2) является числом двоичных символов, поступающих на кодер за время передачи символа канала. Когда инженер связист говорит о скорости передачи данных, он обычно под-разумевает число двоичных символов в секунду, которые поступают на передатчик. Отличие скорости в битах, которая была определена здесь, от этой скорости состоит в том, что последняя нормирована на символ в секунду, а не на символ на одно использование канала, как первая. Повсюду в этой главе будет удобно пользоваться натуральными логарифмами и в натуральных логарифмах R равна (\nM)/N. Переход от скорости R (в натуральных единицах на символ) к скорости, которую используют инженеры связисты (в двоичных символах на секунду) задается соотношением
R = (скорость передачи данных) • тс In 2. (5.1.3)
Следует заметить, что R не является энтропией (хотя она может быть интерпретирована как энтропия, если символы двоичного источника независимы и равновероятны) и R не является, в общем случае, средней взаимной информацией для канала.
Если возникающие иногда «глухие символы» или другие служебные символы должны быть переданы по каналу для того, чтобы установить синхронизацию, то мы будем продолжать определять i?=(ln M)/Nt 134
но (5.1.3) не будет справедливо строго и скорость передачи данных будет несколько меньше, чем указывает равенство (5.1.3).
Пусть у — (уи ..., г/д,) является выходной последовательностью канала, соответствующей некоторому кодовому слову на входе. Задача декодера состоит в том, чтобы на основе у построить гипотезу
о том, какая из М = 2L двоичных последовательностей поступила на кодер. Будем считать, что произошла ошибка при блоковом декодировании, если гипотеза, построенная декодером, отличается от последовательности, поступившей на кодер. Ошибка при блоковом декодировании означает, что произошли одна или более ошибок в последовательности L двоичных символов, но это событие не указывает, сколько ошибок произошло. В большинстве систем передачи данных интересным является как то, сколько ошибок произошло, так и то, как они распределены. Ни вероятность ошибки на символ, ни вероятность ошибки на блок не являются полностью адекватными мерами качества системы передачи. Здесь для простоты исследуется вероятность ошибки на блок. Однако, как будет показано, эта вероятность ошибки может быть сделана настолько малой при больших N и L, что различие между ошибками на блок и на символ приобретает второстепенное значение.
Так как нас будут интересовать ошибки на блок, то можно теперь не рассматривать двоичные последовательности и считать, что кодирование состоит просто в отображении целых чисел от 1 до М в кодовые слова от Xj до хлг- Если сообщение т поступает на кодер, то хт передается и декодер вырабатывает целое число т' на основе принятой последовательности у. Ошибка происходит, если т' Ф т.
Причиной, по которой мы ограничиваемся здесь рассмотрением блоковых кодов, является не то, что они лучше, в каком-то смысле, чем другие типы кодов, а просто потому, что их легче исследовать теоретически. В следующей главе будет рассмотрен важный класс неблоковых кодов, которые называются сверточными кодами. Они имеют некоторые преимущества при реализации, но их можно понять более основательно после того, как будут поняты свойства блоковых кодов.
При построении хороших блоковых кодов главными параметрами, на которые будет обращено внимание, являются: вероятность ошибки при блоковом декодировании, обозначаемая через Ре; длина блока N и скорость R. Не удивительным является то, что уменьшением R (которое можно достичь уменьшением числа двоичных символов в секунду, поступающих на кодер) можно также уменьшить Ре. Удивительным является то, что если R меньше, чем пропускная способность канала, то можно при фиксированной R, увеличивая N, найти коды, для которых Ре экспоненциально убывает с ростом N. Это составляет существо теоремы кодирования, доказываемой в § 5.6. Существует, конечно, цена для расплаты за то, что длина блока увеличивается. Во-первых, происходит задержка в системе. Первый двоичный символ блока поступающих данных, вообще говоря, должен быть задержан на Nxc сек до того, как будет сформировано кодовое слово и после этого еще на Nrc сек, необходимых для передачи кодового слова, по которому этот двоичный символ будет декодирован. Во-вторых,
