ПРИМЕЧАНИЯ РЕДАКТОРОВ

К главе 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, 1971) и другими авторами.

Первое математическое доказательство теоремы Макмиллана было дано Хинчиным (1956).

К главе 4.

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

К главе 5.

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

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

Границы для вероятности ошибки в дискретных каналах исследовались в ряде работ советских авторов. Добрушин (1962 б) получил асимптотические выражения для оптимальной вероятности ошибки в каналах, симметричных по входу и выходу. Добрушин (1962 а) и Молчанов (1967) получили выражения для асимптотики оптимальной вероятности ошибки при конечном числе передаваемых сообщений. Границы сферической упаковки для вероятности ошибки в каналах с памятью исследовались Егарминым (1969), который на основе развитого им метода получил выражение для показателя экспоненты в канале с эргодическим марковским аддитивным шумом. Результаты, аналогичные изложенным в § 5.9, были получены Габидулиным (1969).

К главе 6.

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

Новый класс линейных кодов, исправляющих ошибки, предложил Гоппа (1970). Коды этого класса задаются некоторым многочленам над полем Коды БЧХ являются единственными циклическими кодами, входящими в этот класс. Построеиие кодов основано на отождествлении исходного пространства двоичных векторов с некоторым множеством рациональных функций. Параметры кода следующие: где длина кода, число информационных символов, степень многочлена, задающего код. Гоппа показал, что для всех введенных кодов существует схема декодирования, аналогичная алгоритму Питерсона для БЧХ-кодов. Гоппа (1971) показал также, что почти все коды рассматриваемого класса приближаются с ростом к границе Варшамова-Гилберта.

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

Среди работ по последовательному декодированию необходимо отметить работу Добрушина (1964), посвященную строгому математическому анализу алгоритма Возенкрафта и работу Кошелева (1966 а), предложившего модификацию этого алгоритма. Пинскер (1965) разработал итеративный алгоритм последовательного декодирования, позволяющий увеличить вычислительную скорость процедуры. Новый алгоритм последовательного декодирования был предложен и рассчитан Зигангировым (1966). Этот алгоритм требует меньшего числа онераций, чем рассмотренный в книге алгоритм Фано.

К главе 7.

Теорема кодирования для непрерывных по амплитуде и дискретных по времени кайвлов без памяти является следствием теоремы кодирования, доказанной Добрушиным (1959).

Пропускная способность общего дискретного по времени гауссовского канала без памяти и с памятью рассматривалась в работе Пинскера (1956). Цыбаковым (1965) были найдены выражения для пропускной способности невырожденных и вырожденных многомерных гауссовских каналов.

К главе 8.

Строгое математическое описание и представление белого шума можно найти в книге Гельфаида и Вилеикина (1961).

Теорема отсчетов, представленная в § 8.1, в советской литературе часто называется теоремой Котельникова.

Выражение для количества информации гауссовских процессов исследовалось во многих работах советских авторов. Применимость теоремы Шеииоиа для гауссовских каналов является следствием теоремы кодирования Добрушииа

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

Пятошиным (1968) исследовалась пропускная способность гауссовского канала, когда на входе канала вводилось дополнительное ограничение, состоящее в том, что число входных сигналов не может быть больше некоторого целого числа К.

В работах советских авторов были предложены и исследованы ряд моделей реальных каналов. В работе Сифорова (1958) приведены формулы и оценки пропускной способности канала с замираниями. Было показано, что наличие замирания уменьшает пропускную способность канала не более чем на 17%. Выражения для пропускной способности различных диспергирующих каналов с замираниями исследовались Цыбаковым (1959 а, б).

Изучение пропускной способности каналов при разнесенном приеме было проведено в работах Овсеевича и Пинскера (1961). Было показано, что наличие разнесенного присно ослабляет эффекты диспергирования и замирания в канале.

К главе 9.

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

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

Ерохиным (1958) были найдены выражения для -энтропии дискретных сообщений с вероятностью ошибки в качестве критерия верности.

Выражения для -энтропии гауссовских случайных векторов и процессов при среднеквадратическом критерии верности были выписаны Колмогоровым (1956). Пинскер (1963 б) распространил эти результаты наиболее широкий класс гауссовских процессов при взвешенном среднеквадратическом критерии верности. Цыбаков (1969) получил выражение -энтропии, когда критерий верности задается произвольной неотрицательно определенной квадратичной формой.

Метод передачи гауссовской случайной величины, аналогичный предложенному Шелквийком (1966), рассматривался Зигаигировым (1967).

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

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ И РЕКОМЕНДУЕМЫЕ КНИГИ

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)