автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Иерархические схемы кодирования и проблема делимости

Введение.,.;.

Часть 1. Иерархическое кодирование для источников с заданной мерой погрешности

Предварительные замечания , . .,>•.• .-'.:.••.:.,.'.-,.

Глава 1. Теорема о многоуровневом кодировании для источника с заданным критерием точности

1.1. Описание схемы -уровневого кодирования

1, 2. Формальное определение

1. 3. Область достижимости

1, 4. Типовой ансамбль

1. 5. Теорема 1-уровневого кодирования

Замечания к главе

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

Б простейшем изложении суть теоретики-информационного подхода состоит в следующем.

Если кодирование данных производить блоками достаточно большой длины, то надежность операций кодирования и декодирования будет следовать из закона больших чисел, который в данном случае проявляется в форме статистической устойчивости источники каналов. При этом, если вектор скоростей кодирования принадлежит так называемой области достижимых скоростей, то вероятность ошибки декодирования экспоненциально'убывает с ростом длины блока. Отыскание границы достижимых скоростей для системы с одним пользователем основано на сравнении двух величин: информационной -скорости источника (е) , определяемой как минимальное количество информации, достаточное для описания выходного символа источника со средней погрешностью, не превышающей 8 , и пропускной способности какала £ ) определяемой как максимальное количество -информации, ^которое-может- быть -мередано ш -каналу при условии5 что на передачу одного символа расходуется в среднем не более IX единиц некоторого входного ресурса (анергии, пиковой мощности, стоимости и т.п.)• Если выполняется неравенство

1) РКеНСС^, то передача с параметрами (н, у IX") возможна, в противном случае невозможна. В теории информации.неравенство (1) получило название теоремы передачи данных; его левая часть известна как £ -энтропия источника (или Функция "скорость-погрешность"), а правая часть как 'С -емкость канала (или Функция "пропускная способность - стоимость"). И та и другая величины вычисляются как асимптотические характеристики, возникающие при кодировании достаточно длинных блоков символов на выходе источника и входе канала. Б применении к многопользовательским задачам неравенство (1) принимает векторную форму, а область достижимых скоростей имеет вид выпуклой многомерной области. Отыскание границ областей достижимости, построение схем кодирования, позволяющих приблизиться к этим границам, а также оценка скорости экспоненциального убывания вероятности ошибки декодирования и составляет основное содержание теоретике-информационного подхода к указанному классу задач.

Проследим вкратце историю становления этой тематики.

Фундаментальная роль - £-энтропии источника и -емкости канала для расчета эффективности информационных систем была установлена в конце 40-х начале би-х годов в основополагающих работах Б. А. Коте ль никоей [10, 11] по теории потенциальной помехоустойчивости, К. 3. Шеннона по математическим основам теории связи Г583""и А. Колмогорова, и "его "учеников по- оценке мощностных характеристик покрытий и укладок многомерных метрических пространств Е'7, 8, 93. Разработка основ вероятностной теории

Лг г тгп тт-г\гч тт."4. тгмг^.тт-^ тч V.«пг*,гпптг А СГ Тт.ттщтг'"1 Г ООП ^Т^-г тт.—«.

XI у и-' ,Ц и П От £} уЫли X сЬ.Л. Л» ^ I ь! , , ^¿сьпи

С 423 , ЕС. Пинскера [233, Р. Л. Добрушинз [53 и др. С 4, 63. Сформулированные К Шенноном теоремы кодирования определили два основных направления теоретико-информационных исследований: разработку методов кодирования для источников и разработку методов кодирования для каналов. Как показал А. К Колмогоров [93, в наиболее общей форме шенноковская модель системы передачи данных представляет собой цепь Маркова

2) источник -> кодер источника -> кодер канала -> канал декодер канала декодер источника ->получатель, а неравенство (1) означает необходимое и достаточное условие-устойчивости этой цепи. Важно отметить, что кодер источника делает работу кодера канала не зависящей от статистических свойств источника, поэтому цепь Маркова, которую образуют два первых и два последних звена цепи (2), т.е.

2а) источник кодер источника декодер источника получатель можно изучать независимо от цепи Маркова, которую образуюттри внутренних звена, т.е. О'**'.4» Т/»ГЧТТГ\7"\ тллттп ттп . . ^ ТЛПТТП ЧТ ТТ.^, ТЛГ"\ ТТ.-. ГЛ ГЛПТТП ТТ г—I гъиц^у г^О/Хасылсь пли л. сии - Д^г^и-'гЦс;^' г«с1ПСиЛа- •

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

Е началу 60-х годов вместе с завершением формального обоснования теории информации как математического аппарата техники связи пришло также и понимание фундаментальной рож, которую эта теория призвана сыграть в изучении информационных систем более общей природы, наблюдаемых в квантовой физике, биологии, экономике, лингвистике и др. Однако трудности, связанные с достижением теоретических границ эффективности, выводимых из шенноновских теорем кодирования, наводили на скептические размышления. И хотя к этому Бремени относятся такие важные открытия, как метод последовательного декодирования Дж. Бозенкрафта и Б. Райффена [65] и предложенный Р. Галлагером С 431 вывод оценки вероятности ошибки декодирования, не требующий прямого применения аппарата больших уклоненный, встал вопрос о дальнейшем развитии.теории информации.

Существенное обобщение теорем кодирования произошло под воздействием запросов из области сетевых информационных ¡.систем. И хотя прежние трудности остались, "но открылись•новые перспективы. Возможность перенесения теорем кодирования на схемы со многими пользователями была отмечена самим Шенноном в его работе по двусторонним каналам связи [593. Работы Э. Еан-дер-Мойлена С 61] Р. Альсведе [ 293 и Т. Ковера [363 по широковещательным каналам связи, Р. Грзя [473 и Р. Ррзя и А. Байкера по сетям источников [493 положили начало многочисленным исследованиям эффективности многопользовательский информационных систем. Последовавшие затем работы Р. Галлагера С 453, Слепяна и Дж. Еулша Е 573 } Р. Галлагера [33, 3. Еан-дер-Мойлена [623 , Г, Ш. Полтырева, Ф. А. Таубина, Н. А. Шэхуновой [243, Кошелева Б. Е [123 и других авторов были посвящены как описанию различных информационных моделей, к которым применим шенноновский подход, так и .вычислению соответствующих этим моделям областей достижимости.

Помимо практической необходимости, диктовавшейся развитием реальных сетей связи, важным стимулом этих исследований было также и чисто математическое стремление разработать технику доказательства теорем Шеннона, адекватную тем или иным сетевым топологиям. Е частности, автором диссертации было замечено [70; 13, 14, 15, 523, что наиболее простые и естественные результаты получаются для схем с иерархической топологией. В основу диссертации положены результаты исследований По мн0Г0у00ВнеЕ0му иерархическому кодированию для источников с заданной .функцией 'погрешности, полученные автором в 1975-1981 и 1990-1994 годах, а также недавние результаты по иерархическому кодированию для каналов с заданной функцией стоимости, полученные автором совместно с 3. Ван-дер-Мойленом в 1992-1998 годах [54, 553. Эти результаты (в обновленной форме) изложены, соответственно, в первой и второй частях диссертации.

Дадим краткое описание постановки задачи и'полученных V результатов.

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

Возникает вопрос: .всегда ли это возможно?-А именно, всегда ттт.т tT¡—. »-л m ^tTTTTT т.-. rp v-\ rri т т *n гт:г\.ív ^.тгттггт m тпгтттг.г.тт* г.ппттт i jjJ'i uüo x ciu.ricic o a i y a 1 da i¡ uníame? Oj Д v i r¡ iu4n'jL,in pc¿.D.rí.bi соответствующему значению затратной функции или за многоэтапность надо "доплачивать"? Для всякой физической системы, предназначенной для выполнения некоторой полезной работы, ответ известен: введение промежуточных этапов работы неизбежно приводит

F. ТГ'-*- Т*Т'~,1 тгтттягт^ч тгт. ттт rv .f тгр. тт.-! * л m ¡2t ггл.ттт^^стттлл плпггттх тт.т'птплтлл!-1. к ^UilUJUlilX С JXXmDUíl раД-,ли,ЦСШ1, 1. tí. Г„ liu'njfljnfcíljfliu ptíO^ JIU J. ¡tíyy lUliifri lí к. п. д. системы. Поскольку в информационных схемах мы обычно абстрагируемся от многих технических аспектов реализации, то для достаточно простых информационных моделей действительно удается наблюдать эффект делимости, т. е. сохранения оптимальных показателей схемы при многоуровневой ее реализации/ Простейшим примером иерархически организованной делимой схемы является схема измерения длины линейкой с тремя уровнями градации. Если мы хотим узнать длину предмета с точностью до миллиметра, то, действуя последовательно, мы сначала находим число дециметров, потом находим поправку в сантиметрах и, наконец, поправку к поправке в миллиметрах. Очевидно, общее число десятичных разрядов, выражающих результат измерения, будет совпадать с тем, которое получилось бы, если бы мы, минуя первые два уровня градации, измеряли длину непосредственно в миллиметрах. Б математическом смысле мерная линейка - это "с-сеть, а приведенный пример - лишь простейший пример трехуровневой иерархической -сети. Говоря о простоте или сложности схемы, мы имеем в виду ее размерность, статистические свойства, тип выбранной метрики и другие параметры, определяющие схему как математическую структуру. В других многоуровневых моделях, более сложных, чем мерная линейка, свойство делимости может нарушаться и в этом есть элемент неожиданности! Оказывается, что есть метрики, "неудобные" для последовательных измерений, тара© как и при вполне хорошей метрике, например, эвклидовой, "неудобной" может оказаться статистика измеряемого объекта [34].

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

Первая часть состоит из четырех глав. В главе 1 описывается схема [ -уровневого иерархического кодирования, которую мы, следуя [у], представляем как цепь Маркова

3) источник ^ 1-уровневый кодер -> [ -уровневый декодер -> пользователей .

Для этой цепи доказывается 1-уровневая теорема кодирования, которая определяет область достижимых соотношений между

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

Рассматриваются два варианта доказательства |-уровневой теоремы. В главе 1 теорема кодирования доказывается применительно к схеме, работающей по методу полного перебора, в главе 2 -применительно к схеме последовательных приближений. Технически

Д,™пптлт,1птт1п пттт.-'.птллтттт,-'. г-\гп ттттт т*-1 тгчп ,-г г-г г-1, тгттг-'. |-\т -гг г т гт-п г--., -тт ттгт птглитт лиь 1. ±5сь и ^щсылспси ихшачслльл ^щпи их их и. Д-'хл идств полного перебора используется многоуровневый вариант доказательства, первоначально предложенного Шенноном С603 и усовершенствованного Галлагером [443 и Т.Бергером [323, а для схемы последовательных приближений применяется многоуровневый вариант доказательства, разработанного Дж. Омурой [693. При этом для схемы последовательных приближений в доказательство Омуры приходится вводить дополнительное предположение о согласованности переходных вероятностей, используемых в схеме с заданной мерой погрешности. А именно, предполагается, что схема обладает следующим свойством: если все предыдущие (т.е. уже найденные) приближения заменить на любые равноценные, т.е. имеющие такие же или меньшие погрешности, то математическое ожидание погрешности следующего приближения может от этого только уменьшиться. Мы называем это свойство свойством убывания: действительно, от того, что стрелок приблизился к цели, вероятност промаха может только уменьшиться. Свойство убывания выполняется, по меньшей мере, для источников без памяти с посимвольно аддитивно функцией погрешности. Еопрос о том можно ли построить доказательство без этого дополнительного предположения остается гггпт/«т\т тгп т т> а и л.

Е главе 3 изучается проблема эффективности многоуровневой иерархической схемы кодирования источников. Рассматривается двухуровневая схема и вводится определение делимости схемы для заданной пары погрешностей. Для дискретного стационарного источника без памяти с посимвольно аддитивной мерой погрешности выписывается матричное уравнение, называемое- уравнением.-.-. делимости, и доказывается критерий делимости, утверждающий, что источник делим для заданной пары погрешностей тогда и только тогда? когда уравнение делимости имеет стохастическое решение. Поскольку стохастическое решение (когда оно^сукрству!^ марковским свойством, то делимость схемы, имеющей три или более уровней, полностью определяется указанным двухуровневым критерием. Еводится понятие области делимости, т. е. двумерной области, расположенной в плоскости 8 А и обладающей тем свойством, что в каждой точке (£ BjJ^ £ ^ уравнение делимости имеет стохастическое решение.

Особую задачу составляет поиск стохастического решения. В главе 4 предложен метод локальной делимости, который позволяет свести задачу к изучению дифференциальных свойств уравнения делимости для.сближающихся погрешностей. Для троичного равновероятного источника с балансной матрицей погрешностей указанный метод позволяет заменить матричное уравнение системой из трех линейных уравнений, при этом границы области делимости достаточно просто выражаются через коэффициенты этой системы. Вычисляя последние, удается проследить полную картину изменения области делимости в зависимости от параметра, задающего балансну меру погрешности. Б 1991 году проблема делимости была переоткрыт в работе У. Зквитца и Т. Ковера С 38], не обративших внимание на у

Т-Тл гт тТ-гтЯ тгтлтлпттт.ттг Г "1 О "1 Л -1 С1 TT--. Q ттттг^С, -ггтгггггт^ ттт* г\ ^ TT ТТ.— т*1.-тд

1як?ялцш5ил илиилоЦ)гш L х^, . иисДясс diu j ju j цспис иоши xuari

Tff f-1 TT-V-i .-1 Ti TTO, tl'"1- Г OQ1 XJo TTHTTTTT "Г \ \ л'- TT m ТТиЛЛШПГГ У-;ГТТТ Т-ТТГГ7. TT T T TT1 T T T. TT ГТ[~ аь updBJiö nu l zjsj «. net Дйпг.ЕШ миmens «jsncrbxu« i-'^A имги\ацгиг1 uU многоуровневому кодированию источников, в связи с чем в заключительных замечаниях к первой части диссертации приводится краткий обзор недавних работ, затрагивающих различные аспекты этой проблемы.

Во второй части диссертации изучается схема многоуровневого иерархического кодирования для каналов с заданной функцией входных ограничений. Сама по себе задача кодирования для каналов двойственна к задаче кодирования для источников; эта

Й*п г-чт^гг-! гпт>ттт7/-\ <-\гпх. 7Т,-. ттг т тяп ттпп.т^птлг.тгттппштг тт-пггтг р.пттр.пттт ттг

ЛиИЫЛСППЬ'ЬИ) иЛСД^С! ПО ^ВидиШСППи'иХД ¿¡¡Пу А. и'иПШЗПИЛ математических конструкций - упаковки и покрытия метрических пространств; указанная двойственность отмечалась в работах А. Е Колмогорова и Б. М. Тихомирова [83, К. Шеннона [503 и К. Роджерса [253. Представляется естественным проследить двойственность этих конструкций также и в случае их иерархической реализации, Обращаясь к упомянутым выше функциям и С ($г\ следует ожидать, что, если многоуровневое кодирование делимого источника выглядит как пошаговое восхождение вверх по кривой скорость - погрешность, то многоуровневое кодирование для простейших моделей канала также должно выглядеть как пошаговое восхождение вверх по кривой пропускная способность - стоимость. Говоря более строго, во второй части мы пытаемся ответить на вопрос: что является аналогом уравнения делимости в случае многоуровневого кодирования для .каналов? Изучению этой задачи посвящены главы 5 и 5.

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

-Указанная: теорема-:, используется далее .как /-возможный подход. к изучению проблемы делимости каналов. Для этого вводится определение максимальной эффективности модели двухуровневого кодирования для канала с заданной стоимостью и доказывается ^ппйма, устанавливающая достаточные условия, при которых эта максимальная эффективность достигается, центральную роль опять играет матричное уравнение, задающее переход от распределения вероятностей, на котором достигается "дешевая" пропускная способность, к распределению, на котором достигается "дорогая" пропускная способность. Однако, в отличие от аналогичного уравнения для источника, уравнение для канала допускает множеств! стохастических решений, каждое из которых реализует указанный переход. Требование, чтобы стоимость достройки не превосходила разности тарифов, позволяет устранить эту неопределенность, выделяя наиболее экономное минимальное решение. Примеры минимального решения удается получить для двоичного канала с у ЛТ-ТиТ1'ЛТЗ Г*т?г у / гг1 т т т т ^ тт n m тт > >:>—• г; m ,-. тт т.т тг ттгт т-^ тт , -г

AcíiWUIHi iJBOil iVicij. pi'ii^bi-i u x vjrliviuL x on yl Для x oíwwuBonui U пстеыма O

H.pnnTTTíTT.^.TjTíCVií из /"i тгтттгир. п ттл П г* тп птгл.ттп Лгтт.тгт п тттттттп птг<" у .-¡тт l/í рситЧспйем ha 'w ub^hsUAj ontfyi паи ддида. '-.'¡ш^апг.y ¡u ¡Лу

ТТ ^ " 1 V т т Q TI П. -rTr-TV-w-1. ТП .-j ТТТТГТ тг -ТТГТ ТЛП ТТП ТГ'-l WTT ТТ т T-T-1 í-l LJ. \ А ТТТП ЛТ^П т-п ТТТТ:-<. тЗг ГЛ и Дмл Ла-Нсыла »п йсызгшсьЬт двиии х abimuxi п, схеме иерархического кодирования для источников; при этом матрица стоимостей двойственна матрице погрешностей, стохастический вектор, доставляющий пропускную способность, двойственен матрице тест-канала, а минимальная матрица переходов двойственна гИПП.ТГППт-ТТТЛПЦ'ПЛ^ lj(nmnTTTT|2 ТТГ.ПГПЛТЗ ТГ13 Т--ТТТ.-. ТЯ ТТ?Г\ TTT.TQ. Т Т", Т Т — ТТ ТТ ч" -ТТ.". ТТТТ\ т' т.т

U А идсИ, J. n-ítLAuw Mai. pi'lu.c , Дии х саВллллцсд ¿Л? lúe rúate ^ yeaJancnjíliLi Дс Х П.

Отметим, что в отличие от первой части работы,' вторая часть не дает окончательной формулировки критерия делимости для каналов. Дело в том, что одно из условий достижимости пропускной способности в двухуровневой модели требует, чтобы деградация,

- 19

ТТУЛ>-\Т.Т<-1 Т-1 г~\ ТГТ*1. ГТ , ТГ/Г ТТТ.Т\ТГТ. ТТ.-Ч Т^ ч ТТ*П ПТГЛ.ТТГч 1Т'-1 ТТТГ-гГ.Т-Г, Г*. ТТТЯ- ТТ"Ч ^.тт тл

11 уидовир,1ин10.л иш/1С1Х1та,липихх тах^лпЦчпа пег. алиДс лапшю, ирлсиДухло, и и п. уменьшению■его пропускной способности. ¡Это утверждение (т.е. неравенство) представляется очевидным, однако строгое доказательство отсутствует, поэтому мы ограничиваемся лишь достаточной формулировкой, включающэй указанное неравенство как условие.

Основное содержание каждой главы составляют постановка задачи, определения, формулировки теорем и краткое описание доказательств; полный текст доказательства, как правило, выносится е приложение. ГлаЕЫ сопровождаются кратким резюме, обзором литературы и историческими замечаниями. Список литературы является общим для всех глав.

Часть I. ИЕРАРХИЧЕСКОЕ КОДИРОВАНИЕ ДЛЯ ИСТОЧНИКОВ С ЗАДАННОЙ' МЕРОЙ 'ПОГРЕШНОСТИ

Б этой части работы рассматривается задача о многоуровневом кодировании источника для заданного набора допустимых погрешностей. Изучается класс схем с иерархической топологией, согласно которой каждый последующий уровень кодирования уменьшает погрешность, достигнутую в предыдущем уровне. Б главе 1 рассматривается полнопереборный вариант схемы, а в главе £ -схема, работающая по методу последовательных приближений. В главе 3 формулируется проблема делимости источника, понимаемая как проблема достижимости максимальной эффективности в многоуровневой схеме кодирования. Б главе 4 проблема делимости рассматривается на примере источника с балансной мерой погрешности.

Предварительные замечания

Разработка методов воспроизведения данных по их цифровому описанию является одним из центральных моментов, определяющих

•'ч-ртт.^и'гптт-пттр.птг ttt.s-.-v т т ТТГ-\Т^Г ГТТТ.ТиЛ 'V* у ЛТК,-*, ттгтр.т* тт.-ч гп\ г "С' улу тг гг. т тт.? аф^Спа. шзли^ хх> ± пи« ил^ I свЬ. ■ и ■ ряМЛал' хйи^Лл информации задача воспроизведения формулируется как задача кодирования источника с заданным уровнем точности С60, 44, 31, 323. Для наглядности, обычно рассматривается ситуация из области связи, когда источник сообщений обладает энтропией, превышающей тт¥-чг**.гттгг1т/»тттттг\ гтр.|-[^ттг.г-;т^ тлапп ттп Фппттп т*гт*гг-\ тгггг*.,-■. ,-г,-\/-\тгтг\ ттт.т¡з хрлл!^' 1,ГиДV л; и 1.1 и и и и .пи и х .и хил Да н^лиДпис ьиОицслнЬ приходится заменять его огрубленной копией из числа тех, которые записаны в специальной кодовой книге. Поскольку кодовая книга имеется и на передающей и на приемной стороне, то отправитель посылает получателю только номер выбранной им копии. Зная номер, .получатель .производит .операцию.декодирования^ т. е. по номеру находит в кодовой книге соответствующую копию, которую и рассматривает как более или менее приемлемую репродукцию исходного сообщения - оригинала. Качество воспроизведения при этом измеряется удельной погрешностью, т. е. средним отклонением репродукции от оригинала, отнесенным к размеру оригинала, например, к блоковой длине сообщения. Чем меньше допустимый уровень погрешности, тем выше скорость передачи информации, Обменные соотношения между информационной скоростью и погрешностью являются основным показателем эффективности информационной системы. Разработка схем, реализующих эти обменные соотношения, и составляет суть проблемы кодирования источников.

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

ТТ,~\ ТТ ~'Л£Т Т Т Т тт/"». Т Т-Г} X. С2. (—1 тгтт "^ГПТ.Т П ПГПГ.ПГПТ Т ПП ТГ.Л ТТ Г ГТГ\ГП Г\ ГТ ПППГПХТТЛ Ту и«¿¿Липс! у Ц р{ Г'С1х и ^ с? и¿±±'1 а ± о с» о. усьи. о: ^ДыисЬс< ¿/шп'^ / * 13 иерархической схеме воспроизведения кодовая книга имеет вид дерева с числом ярусов, равным числу пользователей, при этом репродукция для более требовательного пользователя получается путем улучшения предыдущей репродукции, изготовленной для менее т ре б о в ат е ль но го п о ль з о в ат е ля,

Г*" т >-■. у--.т ТТТ Л г"1.т.тттгту-\>-\\тттжпттттп, тит ГП ГЧТ ТТ ЛТ* ппг-. тттга Т* ,-• Т-. V. ТТ,ТТТ -. !—. Т.-'Т ,т и х сиус х ш-ьи хичлм ву^гипл ис уаул-п чет и Лп организованная схема обладает максимальной эффективностью в том и только в том случае, когда дополнительные информационные затраты. гт у--. т,т" ттт/г V л т-. г ~<ц~ тт ."V * (тр.г; тт,- тч т--,.ттттг|.п/т1т.т г.пппг т пл-^.тг, ~ тптптгтАптл. \ -( с Гш-^т^ц^гл ^ ^ийпег , у.збг.И и и х с;; х 1 л ? лДи в;

Т-Г V--. Т.ТГ-\ 7ТТ1ГТГ\ ^ТТТГГ/*Т ТТЛ-Т.Т Т/» "П. ГГ! Т. ГТ -Г1 Г^. ТТТТ Т ,-1 т х. "Тпт.-. ТТТТТ.ТТЛ ТТ ттгт яусичйшш <^НгЩшг1 илиуии х и иих усшяиЬхи. «ЫУЧШ-Л, Длл Лихи±/иА ' может быть построена многоуровневая иерархическая схема, обладающая максимальной эффективностью, называется делимым. Вопросы, связанные с проверкой свойства делимости для различны: моделей источников, и составляют суть проблемы делимости, Б главах 1 и 2 рассматриваются два возможных варианта многоуровневой теоремы кодирования. Непосредственное изучение проблемы делимости проводится в главах 3 и 4,

Переходим к основному содержанию первой части.

1. Арутюнян E. A. , Марутян P. 1.L "( E , A ) - достижимые скорос для множественного описания случайно меняющегося источника" IX Всесоюзная конференция по Теории Кодирования и Передачи Информации. Одесса, 1988; стр. 6-9.

2. Альсведе Р., Бегенер И Задачи поиска. Москва, ."Мир", 1982.

3. Галлагер Р. Г. Пропускная способность и кодирование для некоторых широковещательных каналов. Проблемы передачи информации, 1974, вып. 3, стр. 3-14.

4. Гельфанд И. К , Колмогоров А. К , Яг лом А. М.К общему определению количества информации". ДАН СССР, 1956, т. Ill, М4, с. 745-748

5. Добрушин P. JL "Общая формулировка основной теоремы Шеннона в теории информации". УМН, 1959, т. 14, вып. 6, с. 3-104.

6. Ерохин В. Д. " £ -энтропия дискретного случайного объекта". Теория вероятностей и ее применения, 1958, т. 3, N1,с. 103-107.

7. Колмогоров А. Е Теория передачи информации. Сессия АН СССР по научным проблемам автоматизации, 15-20 октября 1956 г. Изд-во МГУ, 1956.

8. Котельников Б. А. "0 пропускной способности "эфира" и проволоки в электросвязи". В кн.: Материалы к I Всесоюзному съезду по вопросам технической реконструкции дела связи и развития слаботочной промышленности. М. , 1933.

9. Котельников В. А. "Теория потенциальной помехоустойчивости". -Докторская диссертация, 1947 г. , Московский энергетический институт, Государственное Энергетическое Издательство, Москва Ленинград, 1956. "Радио и Связь", Москва, 1998.

10. Кошелев Е. Е "О задаче раздельного кодирования двух зависимых источников". Проблемы передачи информации, том ХШ, вып. 1, 1977, стр. 26-32.

11. Кошелев В. Е "Многоуровневое кодирование и теорема передачи данных". УП Всесоюзная конференция по теории кодирования и передачи информации; Вильнюс, 1978. Доклады. Часть I; теория информация, стр. 85-92.

12. Кошелев В. К "Иерархическое кодирование дискретных источников". Проблемы передачи информации, 1980, том 16, вып. 3, стр. 31-49.

13. Кошелев Б. Н. "Оценка средней погрешности для дискретной схемы последовательных приближений". Проблемы передачи информации. 1981, том 17, вып. 3, стр. 20-33.

14. Кошелев Е. К Частное сообщение: "Многоуровневое кодирование и проблема делимости". Доклад на семинаре по теории кодирования. Институт проблем передачи информации; Москва, 1991, февраль.

15. Кошелев В. К "О проблеме делимости источников и пространств". -Доклады Академии наук, том 332, N1 (сент. 1993); стр. 12-14.

16. Кошелев В. Н. "О проблеме делимости каналов с заданной функцией ограничений". Доклады Академии наук, 1994, том 335, N1,стр. 14-17.

17. Кошелев В. Е "О делимости дискретных источников с посимвольно-аддитивной мерой погрешности". Проблемы передачи информации, 1994, том 30, вып. 1, стр. 31-50.

18. Котов Б. Е. "Проблема делимости для двоичного источника". -Дипломная работа. МФТИ, ФУПМ, 1991-92.

19. Либкинд Л. М. "Двусторонние дискретные каналы связи без памяти". Проблемы передачи информации, том. 3, вып. 2, 1967,стр. 37-44.

20. Шшлав Ш. Б. 'в тещмтаго-ш^оршцшнннх^^^ жтщаг^1 ^задачш: поиска. Дополнение к 2., стр. 334-354.

21. Пинскер К С. "Информация и информационная устойчивость случайных величин и процессов". М.: Изд-во АН СССР, I960, с. 3-201.

22. Полтырев Г. Е , Таубин Ф. А. , Шехунова Е А. -"Применение теории широковещательных каналов в задачах передачи по классу каналов". В сб. "Системы обработки и передачи информации", ЛЗИС, Ленинград, 1976, стр. 3-9.

23. Роджерс К. Укладки и покрытия. М.: Мир, 1968.

24. Таубин Ф. А. Частное сообщение. Ленинградский Институт Авиационного приборостроения; Семинар кафедры АСУ, ноябрь, 1977г.

25. Хинчин А. Я. "Понятие энтропии в теории вероятностей". УМН, 1953, т. 8, еьш, 3, с. 3-20.

26. Хинчин А. Я. "Об основных теоремах теории информации". УМН, 1956, т. 11, вып. 1, с. 17-75.

27. Ahlswede R. "Multi-Way Communication Channels". Второй Международный симпозиум по Теории Информации, Цахкадзор, Армения, 1971, Тезисы докладов, стр.272.

28. Ahlswede R. } "The Rate-Distortion Region for Multiple Descriptions Without Excess Rate". IEEE Trails. Inform. Theory., IT-31 (6) pp. 721-726, Nov. 1985.

29. Berger T. "Rate-Distortion Theory for Sources with Abstract Alphabets and Memory". Inform. Oontr. , vol. 13, pp. 254-273, 1968.

30. Berger T. Rate Distortion Theory: A-Mathematical Easis for Data Compression. NY: Prentice-Hall, 1971.

31. Berger T. , Gibson J. D. "Lossy Source Coding". IEEE Trans. Inform. Theory, vol. IT-44, N6, pp. 2693-2723.

32. Chow J. , Berger T. "Failure of Successive Refinement for Symmetric Gaussion Mixtures". IEEE Trans. Inform. Theory, vol. 43, N1, January 1997, pp. 350-352.

33. Cover T. M. "Broadcost Channels". IEEE Trans, on Inform. Theory, vol. 18, N1, January, 1972.

34. Csiszor I. , Korner J. "Towards, a General Theory of Source Networks", IEEE Trans. Inform. Theory, vol. IT-26, N2, March 1980, pp. 155-165.37. klarst-M.-j. ^ïfte ^m^fBSBiwe 'f ï^swi'ststm^fsaë^sartage".

35. EE Trans. Inform. Theory,. voL 43, N1, January, 1997, pp. 347-350.

36. Equitz W. R. , Cover T, IvL "Successive Refinement of Information". IEEE Trans. Inform. Theory, 1991, vol. IT-37, N2, pp. 259-275.

37. W. H. R. Equitz, T. M. Cover, "Addendum to "Successive Refinement of Information"", IEEE Trans. Inform. Theory, vol.39, N4,pp. 1455-1466.

38. Elias P. "Networks of Gaussian Channels with Applications to Feedback Systems". IEEE Trans. Inform. Theory, vol. IT-13,pp. 493-501, July, 1967.

39. Elias P. , Feinstein A. and Shannon C. "A note on the Maximal Flow Trough a Network". IRE Trans. Inform. Theory; vol. IT-2, Dec. 1956.

40. Fano R. M. Transmission of Information. A statistical theory of communications. MIT Press, 1961.

41. Gal lager R. G. "A Simple Derivation of the Coding Theorems and Some Applications". IEEE Trans. Inform. Theory, IT-11, 3-18.

42. Gal lager R. G. Information Theory and Reliable Communication. New York: Wiley, 1968.45. -''Source Coding^tfri Siäe ^'foi^ätiün"and';1jrriTeTsa Coding". ISIT-76, Sweden; Proceedings.

43. Gallager R. G. "Energy limited channels; coding, multiaccess and spread spectrum", in Proc. 1988, Conf. Inform. Sei. Syst., p. 372, Princeton, Mar. 1988.

44. Gray R. M. "A New Class of Lower Bounds to Information Rates of Stationary Sources via a Conditional Rate-Distort ion Functions". IEEE Trans. Inform. Theory, 1973, vol.19, is. 4, pp. 480-489.

45. Gray R. M. , Neuhoff D. L. "Quantization". IEEE Trans. Inform. Theory, vol. IT-44, N6, pp. 2325-2383, October 1998.

46. Gray R. M. , Wyner A. D. "Source Coding for a Simple Network". Bell System Techn. J. , 1974, 53, 9; pp. 1681-1772.

47. Haroutunian E. A. , Haroutuman A.N. "Three Descriptions Rates-reliabilities -distortions Region Inner Bound". Computer Science and Information Thechnologies, Proceedings of -the Conference, September 25-30, 1997, Yerevan, Armenia, pp. 225-228.

48. Koshelev V.N. "On the Problem of Divisibility in Source and Channel Coding'". Sixth Joint Swedish-Russian International Workshop on Information Theory. August. 22-27, 1993, Moils, Sweden. Proceedings, pp. 25S-273.

49. Koshelev V. N. , Van der Meulen E. C. "Two-Level Coding* for Input-Constrained Channels", ISIT 1998, Cambridge, MA, USA, August 16-21, Proceedings, p. 430.

50. Koshelev V. N. , Van der Moulen E. C. "On the Efficiency of Successive Coding for Input Constrained Channels". To be published.

51. Rimoldi B. B. "Successive Refinement of Information: a Direct Proof of the Necessary and Sufficient Condition". ISIT-91, Budapest, 1991, Proceeding, p. 320.

52. Slepian D. , Wolf J. K. "Noiseless Coding of Correlated Information Sources". IEEE Trans. Inform. Theory, vol. IT-19, pp. 471-480, 1973.

53. Shannon С. Е. "Two-way Communication Channels". Froc. 4-th Berkeley Symposium on Math, Statistics and Probability 1960.

54. Van der Meulen E. C. "Advances in Multiple-User Communication Channels" Proceedings of the 1975, IEEE-USSR Joint Workshop on Information Theory, December 15-19, 1975, pp. 227-247.

55. Verdu S. "On channel capacity per unit. cost". IEEE Trans.- 315 л»-, Кч^л-пт Т'г.ллум! 1Гл1 ОС МРС i1П1П'!ПОЛ Сл>-ч-Н 1ППП Uli il il 111. I I fcUi у ) IU1. >JU) 14u.i, Ь'Р4 iUUUj

56. Wolf J. К. , Wyner A/D. ,""Ziv J, "Source Coding for Multiple Destnptions", Bell Syst. Techn. j. , vol.59, pp. 1417-1426, 1980.

57. Wozencraft j. , Re iff en B, Sequential Decoding, MIT Press, 1961.

58. Zhang Z. , Berger T. "Multiple Description Source Coding with no Excess Marginal Rate", IEEE Trans. Inform. Theory, vol.41,pp. 349-357, 1995.

59. Раотригин JL А. Случайный поиск,. "Знание", Москва, 1979 г.

60. Случайный поиск в задачах оптимизации. В сб. "Вопросы кибернетики", Научный совет по комплексной проблеме "Кибернетика" АН СССР, Москва, 1978 г.

61. Omura J. К. "A Coding Theorem for Discrete Time Sources", IEEE Trails. Inform. Theory, vol. IT-15, pp. 490-498, 1973.

62. Еошелев В. E Частное сообщение. Совместный Советско-Американский Семинар по Теории Информации, 15-19 декабря 1975 г.

63. Чиссар И,, Кернер Я. Теория информации. Москва, "Мир", 1985.

64. Gerrish А. М. "Estimation of Information Rates", Fh. D. thesis, Yale Univ., New Haven, CT, Dept. of Electr. Eng. , 1963.

65. St. Ten i moto, v ^iiwage vTmns»¿ssáí!m.; with,< ¡Gross,, I.nfk^aation First", Computer Graphics and Image Processing, vol.9, January 1979, pp. 72-75.

66. Lange M. M. "Hierarchical Representation of Patterns by Successive Approximations with Fiugres of Given Shope", Pattern Recognition and Image Analysis. Interperiodika Publishing (Nauka), 1994, vol.4, N4, pp. 414-421.

67. Haroutunian A.N., Haroutunifn E. A. "The Binary Hamming Rate-Reliability-Distortion Function". Conference on Computer Science and Information Thechnologies; Armenia., Yerevan, 25-29 September, 1997. Proceedings, pp. 222-224.

68. Rossignac J. "Comparing Progressive Refinement Techiques for accessing 3D Triangle Meshes". International Conferece on Visual Computing (ICVC-99); February 23-26, 1999, Goa, India

69. Lange M. M. "Hierarchical Structures for Fast Recognition of Geometric Shapes". Munich., Germany., 1998.

70. Gray R. M. "Vector Quantization"., IEEE ASSF Mag. , vol.1, pp. 4-29, Apr, 1984.

71. Calclerbank A. R. "The Art of Signaling: Fifty Yearsof Coding Theory" IEEE Trans. Inform. Theory, vol. 44, N 6, October 1998, pp. 2561-2595.

72. Merhav N. , Roth R. M. , Arikan E. "Hierarchical Guessmg with a Fidelity Criterion". IEEE Trans, on Inform. Theory, vol.45, N 1, January, 1999, pp. 330-337.

73. Коше лев В. К "О строгой блоковой аппроксимации равновероятных сообщений". Проблемы передачи информации, 1978, т. 14, вып. 2.

74. Кузюрин а Н. "Асимптотическое исследование задачи о покрытии". Проблемы кибернетики, 1980, вып. 37,стр. 19-56.

75. Viterby A. J. , Omura J. К. Prinoiples of Digital Commun i cations. McGraw-Hill, 1979.

76. E.G. van der Meulen, V. N. Koshelev. More on Duality Between Source and Channel Coding. Twentieth Symposium on Information Theory in the Benelux, 1999.- 31 s

77. Koshelev V.N. "Some Resalts on Source Encoding with Faithful ' Decoding". IEEE USSR Joint workshop on Information Theory. . December 15-19, 1975, Moscow, USSR; Proceedings, pp. 122-125.

78. Koshelev V.N. "Direct Sequential Encoding and Decoding for Discrete Sources". IEEE Trans. Inform. Theory, 1973, May, vol. IT-19, N3, pp. 340-343.