ДОПОЛНЕНИЕ IV. ПРЕДЕЛЬНЫЕ ВОЗМОЖНОСТИ НАДЕЖНОГО РАЗЛИЧЕНИЯ БОЛЬШОГО ЧИСЛА СИГНАЛОВ ПРИ НАЛИЧИИ ШУМА

§ IV.1. ВВОДНЫЕ ЗАМЕЧАНИЯ

В основном тексте книги подробно рассматривалась задача обнаружения сигнала на фоне шума. Она сводится к задаче оптимального выбора между двумя гипотезами, решаемой в классической и последовательной постановке. Более общая задача различения сигналов сводится к задаче оптимального выбора между гипотезами. До сих пор неизвестно эффективное решение общей задачи для фиксированного [97].

Однако если рассмотреть предельный случай растущего с объемом выборки числа гипотез то возможен ряд интересных оптимальных постановок задач и их решений, связанных с теорией потенциальной помехоустойчивости В. А. Котельникова [15]. В частности, решение таких задач выясняет предельные возможности надежного различения растущего с объемом выборки числа сигналов, передаваемых по каналу с шумами, впервые установленные Шенноном [79]. Специфика задач такого рода состоит в том, что в них производится оптимальный выбор между гипотезами (декодирование) об оптимально заданных значениях параметра распределения (кодирование), причем истинное значение параметра всегда точно совпадает с одним из гипотетических значений.

Обычно же в статистических приложениях мы не располагаем возможностью произвольно задавать все гипотетические значения параметра и истинное значение не всегда совпадает с гипотетическим.

Например, в задачах обнаружения параметр сигнал/шум при наличии одного шума всегда имеет

определенное независящее от нас значение, а истинное значение этого параметра при наличии сигнала, как правило, не совпадает с гипотетическим.

В § IV.2 дана постановка задачи надежного различения растущего с объемом выборки числа сигналов, передаваемых в дискретные моменты времени по дискретному каналу с достаточно общим случаем шумов.

Далее в § IV.3 выводятся простые оптимальные соотношения, оценивающие максимальный порядок роста числа надежно различаемых сигналов с ростом объема выборки

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

В § IV.4 оценивается эффективность использования последовательного декодирования вместо классического. Кроме того, обсуждаются технические возможности реализации оптимальных процедур, связанные с необходимостью иметь большой объем памяти.

В заключении в § IV.5 обсуждается связь полученных результатов с результатами теории информации, а также связь различных фундаментальных констант статистики и теории информации, встречающихся по тексту книги.

§ IV.2. СТАТИСТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ

Рассмотрим дискретную во времени передачу сигналов по каналу с дискретным входом и выходом, при наличии шумов, независимо воздействующих на входные посылки в различные моменты времени.

Непрерывную во времени передачу сигналов по непрерывному каналу можно свести к указанному выше дискретному случаю выбором достаточно малого интервала дискретизации по амплитуде и достаточно большого интервала дискретизации по времени.

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

Пусть действие шумов в каждый момент времени описывается -матрицей вероятностей переходов

элементы которой являются условными вероятностями появления выходного символа при условии появления входного символа Так определенный канал мы будем называть дискретным каналом с независимыми шумами.

Поступающие на вход канала сигналы кодируются входными кодовыми комбинациями длины

состоящими из входных символов.

Последние под действием шумов переходят в выходные кодовые комбинации длины

состоящие из выходных символов.

Пусть передаче подлежат сигналов, пронумерованных целыми числами от 1 до

Так как каждому сигналу однозначно сопоставляется своя выходная кодовая комбинация то всего необходимо иметь различных входных кодовых комбинаций

составляющих кодовую таблицу.

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

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

вероятность травильного декодирования Мы будем допускать кодовые таблицы с повторяющимися входными кодовыми комбинациями, но при этом будем полагать, что для них

Используя матрицу можно вычислить условную вероятность появления х на выходе при условии передачи а [см. (IV.3)]. Вероятность можно рассматривать, как вероятность выборки х объема , при фиксации значения параметра а. Тогда задачу различения сигналов, передаваемых по каналу с шумами на основании принятой кодовой комбинации х, можно свести к задаче выбора между гипотезами о значении параметра а вероятности по выборке х (см. гл. 3). Специфика рассматриваемой задачи состоит в точном совладении истинного значения параметра а с одним из назначаемых нами многомерных гипотетических значений

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

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

Такое определение соответствует естественному желанию надежно передавать как можно больше сигналов, что уменьшает вероятность правильного декодирования.

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

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

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