Выходная буква

Cтраница 4

Вначале рассматривается дискретный канал без памяти. Это такой канал, вход и выход которого представляют собой последовательности букв конечных алфавитов и для которого выходная буква в данный момент статистически зависит лишь от соответствующей входной буквы. [46]

Марковский источник. на ребрах указаны выход at и вероятность. [47]

Состояние марковского источника можно представить себе как тот объект, который определяет влияние истории источника на следующую букву. Так, например, стационарный источник, для которого каждая выходная буква статистически зависит лишь от / предыдущих выходных букв, является марковским источником, состояниями которого являются всевозможные последовательности из / букв. Из этого примера становится ясным, что большинство хороших стационарных источников может быть по крайней мере аппроксимировано марковскими источниками. [48]

Состояния автомата, сигналы-воздействия и сигналы-реакции задаются буквами соответствующих алфавитов: алфавита состояний, а также алфавитов входных и выходных сигналов. Законы взаимодействия букв этих алфавитов задаются двумя функциями - функцией переходов и функцией выходов, отображающими пары ( состояние - входная буква), в состояния и выходные буквы соответственно. Входной средой для автомата является множество слов во входном алфавите, а внутренней и выходной его средами являются множества слов в алфавите состояний и выходном алфавите. Автомат побуквенно перерабатывает слова из входной среды в слова двух других сред. Этот процесс называется поведением автомата. Свойства алфавитов и функций определяют разл. В случае когда все алфавиты конечны, получают конечный автомат, в противном случае автомат называют бесконечным. Замена функций на отношения приводит к частичным и недетерминированным автоматам; использование случайных функций приводит к вероятностному автомату. При интерпретации входной среды термами или графами приходят к автоматам над термами и автоматам в лабиринтах. [49]

Более часто, чем указанные матрицы, используется квадратная матрица, называемая матрицей соединений автомата, которая строится следующим образом. Строки и столбцы матрицы соединений соответствуют различным состояниям автомата, причем первая строка и первый столбец соответствует начальному состоянию q Q. Y или дизъюнкция выходных букв, которые появляются на выходе автомата. Если ни одна из букв входного алфавита не переводит автомат из состояния qh в qi, то на соответствующем пересечении ставится нуль. [50]

При этом новый канал К, обладает двумя выходными буквами и ah входными буквами. Однако в канале, у которого имеются ровно две выходные буквы, для того чтобы достичь пропускной способности, нужно, как показано в работе автора1), использовать лишь две входные буквы; именно в канале / С использовать только те две буквы, одна из которых обладает максимальной, а другая минимальной вероятностями перехода к одной из выходных букв. Эта пара может быть найдена следующим образом. Переходные вероятности для какой-либо буквы из алфавита канала К являются средними соответствующих переходных вероятностей для множества букв канала К, взятых по одной для каждого состояния. Ясно, что для того, чтобы максимизировать переходную вероятность к одной из выходных букв, требуется выбрать для каждого состояния букву с максимальной вероятностью перехода в эту выходную букву. Подобно этому, для минимизации нужно выбрать для каждого состояния букву с минимальной вероятностью перехода в указанную букву. При использовании лишь этих двух результирующих букв в канале К получим, что соответствующий канал даст желаемую пропускную способность. [51]

Тогда при помощи вероятностей gag p для предварительного канала R & U Ra и Для заключительного канала Та ( J Гр ( знак ( J означает последовательное использование каналов, соответствующее произведению матриц) получим канал Кз из канала Ki - Если Ki 3 Kz и Kz Ki, то будем говорить, что каналы Ki и Kz эквивалентны. Очевидно, канал с одной входной буквой, с одной выходной буквой и с вероятностью 1 для перехода является общей нижней границей для всех каналов. Общей ( конечной) верхней границы не существует. Однако если ограничиться каналами, у которых не больше п входных и выходных символов ( или им эквивалентными), то для этого подмножества можно найти верхнюю границу, а именно чистый канал с п входными и п выходными буквами, взаимно однозначно отображаемыми друг на друга. [52]

Предположим теперь, что передача начинается с М сообщений, подразделенных на группы, вероятности которых, согласно описанному ранее, приблизительно пропорциональны Рг. Тогда, если некоторая буква является уже принятой, множество возможных сообщений ( совместимых с этой принятой буквой) сводится к тем, которые объединены в группы, соответствующие буквам, соединенным с уже принятой буквой. Следовательно, общее относительное число сообщений во всех соединенных группах меньше или равно P0 - - ( t -) M для любой выходной буквы. [53]

Канал Kt идентичен каналу К. Производный канал К2 является таким каналом, у которого входные буквы в действительности есть стратегии при работе канала К для блоков из двух входных букв. Таким образом, эта функция может рассматриваться как некоторое правило для выбора второй входной буквы на конце 1 в зависимости от первой входной буквы и полученной первой выходной буквы. Если предположить, что х принимает а значений и у - Ъ значений, тогда пара ( х, у) принимает ab значений и, так как функция / может принимать а значений, то всего имеется ааЬ возможных функций. [54]

Страницы: 1 2 3 4