Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
ского изображения этого удобно определить
Величину (5 можно интерпретировать как индекс модуляции; а — как энергетическое отношение сигнал/шум в канале на одну степень свободы источника и d*!(2WxA) — как отношение среднеквадратической ошибки к мощности источника.
{\ 1V2U,. cc = S/(riiV0).
Тогда
СПИСОК ОБОЗНАЧЕНИЙ
ф Сложение по модулю 2.
Yх~] Наибольшее целое число, меньшее или равное х (целая часть х).
l_xj Наименьшее целое число, большее или равное х.
хх у х приближенно равно у.
х€.У х пренебрежимо мало по сравнению с у.
г Среднее значение (математическое ожидание) случайной величины г. fAg / по определению равно g.
[[ / j| Норма функции /, |j /1 = V j /2 (х) dx.
(f-g) Скалярное произведение функций / и g, (/-g) = J/ (х) g (х) dx.
[/ (D)]" fm Dm -\-fn+ ; D'» + i + ... -I- fn Dn при n > tn
и 0 при т > n, где f (D) = — многочлен.
A° Дополнение множества A.
A\jB Объединение множеств А к В (т. е. множество элементов, содер-
жащихся в А или в В или в обоих множествах).
и Ат л1ил2ил3и--.
т
А[\В Пересечение множеств А и В (т. е. множество элементов, содер-
жащихся в множествах А и В одновременно).
|| Л || Число элементов в множестве А.
х<^А Элемент а содержится в множестве А.
а : S Множества элементов а, таких, что удовлетворяется утверждение S.
Например, 2 хп является суммой хп по п, для которых хп> 1.
п: хп> 1
/l = (a:S) А определяется как множество элементов а, для которых удовлетворяется утверждение S.
S1=>S2 Из утверждения следует утверждение S2.
SX<==^S2 Из утверждения Sx следует S2 и из S2 следует Sx.
------------ Обозначает конец теоремы.
| Обозначает конец доказательства.
НОД Наибольший общий делитель.
Н( ) Энтропия; см. § 2. 2.
$? {х) —х log х — (1—Jc) log (1—х)ш, 0 < х < 1.
I ( ) Информация; см. § 2.2.
НОК Наименьшее общее кратное,
lim Предел при х, стремящемся к у справа.
lim Предел при х, стремящемся к у слева. х-*у~
Rn(m) Остаток от деления т на п (т и п — положительные целые числа).
i?g<0)/(Z)) Остаток от деления многочлена / (D) на g(D).
sup f (х) Верхняя грань; наименьшее число, не меньшее f(x) во всей допустимой области значений х. Если существует максимум, то sup / (х) = тах / (х). inf f (х) Нижняя грань; наибольшее число, не превосходящее / (х) во всей допустимой области значений х. Если существует минимум, то inf / (л-) = min/ (я).
23* 691
ПРИМЕЧАНИЯ РЕДАКТОРОВ
К главе 1.
Первоначальное знакомство с идеями теории информации можно получить по книгам Харкевича (1965), А. Яглома и П. Яглома (1973).
К главе 2.
Колмогоров (1956) предложил наиболее общий подход к построению теории передачи информации и наметил программу его строгого математического обоснования. Этому же посвящена статья Добрушина (1961). Эти две работы рекомендуются математически настроенному читателю, впервые знакомящемуся с теорией информации.
Новые логические основания теории информации, построенные на понятии сложности последовательности, были предложены Колмогоровым (1965, 1969). Колмогоров показал, что такие понятия теории информации как «энтропия» и «информация» могут быть введены без ссылки на теорию вероятностей и тем самым могут быть применены к индивидуальным событиям. Дальнейшее развитие этих идей содержится в статье Звонкина и Левина (1970).
К главе 3.
Постановка задачи кодирования для сокращения длины последовательности букв, вырабатываемых источником сообщений, была обобщена Фитингофом (1966) на случай, когда неизвестны вероятностные свойства источника. Для этого случая была доказана теорема, аналогичная теореме 3.3.1, и построен эффективный универсальный способ кодирования. Аналогичная постановка задачи, когда вероятностные свойства источника полностью или частично неизвестны, рассматривалась Кричевским (1968), получившим асимптотику сходимости к нулю избыточности для различных методов кодирования. Фитингоф (1967) ввел новое минимаксное определение оптимального кодирования (отличное от предложенного Шенноном, состоящего в минимизации п) и построил соответствующие этому определению оптимальные коды. В работе Бабкина (1971) предложен универсальный метод кодирования, допускающий сравнительно простую реализацию.
Марков (1960, 1961, 1962, 1963) исследовал свойство взаимной однозначности неравномерного кодирования. В его работе построен графический алгоритм определения существования этого свойства. Декодирование неравномерного кода с помощью конечного автомата было рассмотрено Левенштейном (1961) для случая, когда в начальный момент кодирующий и декодирующий автомат синхронизованы и когда такая синхронизация отсутствует. Коды, обладающие свойством синхронизации, были рассмотрены Кирилловым (1959), Левенштейном (1965, 1969, 197J) и другими авторами.
