Вероятность ошибочного приема кода

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

для подготовки к Госэкзамену

Тема Кодирование информации

Помехозащищенные коды.

КОДЫ ГРЕЯ

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

В качестве примера рассмотрим двоичный код Грея, применяемый для отображения десятичных чисел. Код использует десять кодовых комбинаций для каждого разряда, т.е. содержит четыре бита на каждый разряд десятичного числа (М = 10 < 2⁴). Так как код двоичный, то каждый элемент кода может принимать значения «0» или «1». Основной особенностью кодов Грея является следующее. Последовательность кодовых комбинаций принята такая, что при изменении непрерывной величины каждый последующий отсчет непрерывной функции отображается кодовой комбинацией, отличающейся от предыдущей только в одном (любом) битовом разряде. Это позволяет свести ошибку считывания к минимуму, тем самым сделать код помехозащищенным.

В таблице приведены десятичные числа и вероятные кодовые комбинации для их отображения.

Таблица

Число	Код Грея	Число	Код Грея

 

ИЗБЫТОЧНЫЕ КОДЫ

Для обеспечения помехоустойчивости кода вводят дополнительные разряды. Если, например, для кодирования всех символов внешнего алфавита достаточно иметь k -разрядный первичный код, то для обеспечения помехоустойчивости к разрядам первичного кода добавляется r избыточных разрядов. При этом длина результирующей кодовой комбинации становится равной n = k + r.

Избыточные коды бывают разделимыми и неразделимым и.

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

В качестве примера неразделимого кода может служить код с постоянным весом «2 из 5». Особенностью этого кода является то, что в любой его кодовой комбинации длины 5 имеется ровно две единицы. Таким образом, всего разрешенных кодовых комбинаций кода «2 из 5 » имеется С²₅ = 5!/(2!×3!) = 10. Обнаруживающая способность данного кода основывается на свойстве, состоящем в том, что любая одиночная ошибка изменяет число единиц в кодовой комбинации.

Для оценки свойств помехоустойчивых кодов служит коэффициент избыточности кода.

,

где M – число возможных кодовых комбинаций, N – число разрешенных кодовых комбинаций.

Для разделимых кодов формула упрощается:

,

где n - длина кодовой комбинации; k - число информационных разрядов.

Видно, что коэффициент избыточности принимает значения от 0 (отсутствие избыточности) до 1 (избыточность неограниченно велика). Коэффициент избыточности характеризует качество помехоустойчивого кода: чем меньше избыточность кода при прочих равных условиях, тем код лучше.

Экономичные коды.

Оптимальным с точки зрения экономичности часто считают такой код, при котором на передачу сообщений затрачивается минимальное время, то есть когда каждая кодовая комбинация передает максимальное количество информации. Если кодируемые значения не равновероятны, то для получения наибольшей информативности каждого элемента кода используют неравномерные коды, получившие название статистических кодов или кодов Шеннона – Фано. При построении неравномерных статистических кодов стремятся повысить информативность каждого символа. В этих кодах длина комбинации тем больше, чем меньше вероятность возникновения отсчета функции. Количество информации, которое содержится в одном элементе хода, определяется энтропией источника.

Характеристикой неравномерного кода является его средняя длина n_ср, определяемаякак математическое ожидание длин кодов по всему ансамблю кодируемых символов (отсчетов):

,

где n_i - длина кодовой комбинации, соответствующая i-му символу; p_i - вероятность i-го символа; М - число символов.

Найдем среднюю информацию, содержащуюся в одном закодированном символе:

Далее можно подсчитать количество информации, которое приходится на один символ кода:

I_k = H/n_ср

Код будет тем ближе к оптимальному, чем ближе полученное значение к единице.

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

Задача 1.

Определить коэффициент избыточности неразделимого двоичного кода с постоянным весом «3 из 7».

Решение

Число возможных кодовых комбинаций длины 7 равно 2⁷ = 128.

Число разрешенных кодовых комбинаций С³₇ = 7!/(3!*4!) = 35.

Коэффициент избыточности

К_И = 1 – (log 35)/(log 128) = 0,267.

 

Задача 2.

Определить коэффициент избыточности 8-разрядного разделимого двоичного кода с проверкой на четность.

Решение

Длина кодовой комбинации равна 8;

Число информационных разрядов равно 7.

Коэффициент избыточности

К_И = 1 –7/8 = 0,125.

Задача 3.

Требуется построить оптимальный с точки зрения экономичности двоичный код, отображающий 5 дискретных значений (отсчетов), если они возникают с вероятностями 1/2, 1/4, 1/8, 1/16, 1/16. Доказать, что построенный код экономичнее равномерного кода.

Решение

Для построения оптимального кода воспользуемся способом, по которому создаются неравномерные статистические коды Шеннона – Фано. Согласно этому способу, кодируемые символы разделяются на две приблизительно равновероятные группы: для первой группы символов на первом месте комбинации ставится 0, а для второй группы символов - 1. Далее каждая группа снова делится на две приблизительно равновероятные подгруппы; для символов первой подгруппы на втором месте ставится 0, а для второй подгруппы - 1 и т.д.

Составим таблицу вероятности появления отсчетов:

Отсчет	х1	х2	х3	х4	х5
Вероятность появления	1/2	1/4	1/8	1/16	1/16

Разделим отсчеты на две равновероятные группы, отнеся к первой отсчет х₁ уровни, а ко второй – остальные. Для первой группы на первом месте кодовой комбинации поставим 0, а для второй группы – 1. Получим:

Отсчет	х1	х2	х3	х4	х5
Кодовые комбинации		1…	1…	1…	1…

Поскольку в первой группе оказался только один отсчет, его кодирование закончено. Далее разделим вторую группу, а на две равновероятные подгруппы, в одну из которых отнесем отсчет х₂, а в другую – остальные. Для первой полученной подгруппы на следующем месте кодовой комбинации поставим 0, а для второй подгруппы – 1. Получим:

Отсчет	х1	х2	х3	х4	х5
Кодовые комбинации			11…	11…	11…

Разделим оставшиеся отсчеты на следующие равновероятные подгруппы, отнеся к первой х₃, а ко второй – остальные. Добавляя символы кода, получим:

Отсчет	х1	х2	х3	х4	х5
Кодовые комбинации				111…	111…

Продолжая аналогично, получим окончательную кодовую таблицу:

Отсчет	х1	х2	х3	х4	х5
Кодовые комбинации

Оценим оптимальность кода, найдя его среднюю длину и энтропию на один символ.

n_ср = 1/2 + 2·1/4 + 3·1/8 +2·4·1/16 = 1,875;

H = (-1/2·log₂1/2 -1/4·log₂1/4 – 1/8·log₂1/8 - 2·1/16·log₂1/16) = 1,.875.

Количество информации, приходящееся на один символ кода

I_k = H/n_ср = 1

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

I’_k = 1,875/3 = 0,625

Таким образом, построенный код более экономичен, чем равномерный.

 

Задача 4.

Определить вероятности возникновения в двоичном симметричном канале нуля, одной, двух, трех ошибок в кодовой комбинации длиной 5, если вероятность ошибочного приема разряда равна 0,1.

Решение

Вероятность безошибочного приема

p_0,5 = 5!/(0!*5!)*0,1⁰*(1-0,1)⁵ = 0,59

Вероятность одной ошибки

p_1,5 = 5!/(1!*4!)*0,1*(1-0,1)⁴ = 0,33

Вероятность двух ошибок

p_2,5 = 5!/(2!*3!)*0,1²*(1-0,1)³ = 0,07

Вероятность трех ошибок

p_3,5 = 5!/(3!*2!)*×0,1³*(1-0,1)² = 0,008

Тема Преобразование информации

Первичные преобразователи

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

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

где K_П – коэффициент преобразования; Du - приращение выходной величины (u), Dx – приращение первичного сообщения (x).

Показатель K_П однозначно характеризует лишь линейные и безинерционные преобразователи.

Преобразователь называется безинерционным, если значение K_П не зависит от длительности (продолжительности) приращений Dx. Любой реальный преобразователь может считаться безинерционным лишь в определенном диапазоне длительностей приращений.

Преобразователь называется линейным, если имеет место зависимость u = u(x) = k₀x + b, где k₀, b - const. Любой реальный преобразователь может считаться линейным лишь в определенном диапазоне изменения величины x. Для линейного преобразователя K_П = k₀.

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

Линейность. Этот параметр характеризует степень приближения реальной функции u = u(x) к линейной зависимости u = k₀x или степень отклонения от линейной зависимости. Часто используют показатель, называющийся коэффициент нелинейных искажений (КНИ). Он имеет следующий смысл. Если первичное воздействие имеет вид гармонических колебаний с частотой w₀, то часто выходное напряжение преобразователя с амплитудой U₀ вследствие его нелинейности не будет чисто гармоническим, а будет содержать колебания более высоких частот, которые называются гармониками. Их частоты - w₁, w₂, w₃,...и амплитуды - U₁, U₂, U₃,....Коэффициент нелинейных искажений вычисляется по формуле

Квантование сигналов

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

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

Существует несколько методов дискретизации - квантование по времени и квантование по уровню.

Квантование непрерывного сигнала по времени

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

Непрерывное (аналоговое) сообщение X(t) может быть преобразовано в дискретный вид (последовательность чисел) с помощью процесса взятия отсчетов мгновенных или средних значений через интервалы Dt₁, Dt₂, Dt₃....С практической точки зрения интервалы выборки берутся одинаковыми.

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

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

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

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

Квантование непрерывного сигнала по уровню

С математической точки зрения квантование по уровню является процессом замены непрерывной функции непрерывного аргумента F(t) дискретной функцией непрерывного аргумента F_i(t). Полученная функция определяется набором конечных дискретных значений на всем интервале t для любого момента времени.

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

Правило квантования обычно выбирается таким, чтобы непрерывная величина X, лежащая в диапазоне iD < X < (i+1)D, заменялась значением iD (квантование по нижней границе), (i+1)D (квантование по верхней границе) или (i+1/2)D (квантование по середине). Такой вид квантования называется равномерным. Здесь i - целое число, а величина D является шагом квантования по уровню. При этом выполняется условие:

,

где X_max, X_min - экстремальные значения величины X; n - число уровней квантования.

На практике часто применяют оба рассмотренных вида квантования одновременно, то есть квантованный по времени аналоговый сигнал подвергают квантованию по уровню. При этом исходное непрерывное сообщение X(t) принимает вид дискретной функции дискретного аргумента – Y_j(t_i).

Восстановление непрерывного сообщения

На практике, в ряде случаев, после передачи квантованного (цифрового) сигнала по каналам связи, требуется его восстановление в непрерывный вид. Процесс восстановления непрерывного сообщения из квантованного называется сглаживанием или интерполяцией. Общий метод интерполяции состоит в том, чтобы отыскать непрерывную функцию F(t), проходящую через выборочные значения в моменты отсчетов t₀, t₁, t₂,...t_n и минимально уклоняющуюся в промежуточные моменты времени.

На практике часто ограничиваются ступенчатой аппроксимацией или трапециевидной аппроксимацией. Если квантование произведено через одинаковые интервалы времени Dt = Т_В, то в первом случае

,

где П(t) = 1, при 0 < t < T_В, и П(t) = 0, при других t.

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

Во втором случае

Это означает, что функция имеет вид прямых линий, проходящих между каждыми двумя выборками.

 

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

Задача 5.

Определить чувствительность линейного безинерционного преобразователя напряжения, если его коэффициент преобразования составляет 7, а при входном напряжении 0,3 мВ, выходное равно 1,4 мВ.

Решение.

Для линейного безинерционного преобразователя справедлива зависимость

U_ВЫХ = aU_ВХ + b, где a = К_П – коэффициент преобразования.

Можем записать: 7 × 0,3 + b = 1,4. Отсюда b = -0,7.

В результате получаем уравнение преобразователя:

U_ВЫХ = 7U_ВХ – 0,7.

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

7U_ВХ(min) – 0,7 = 0

Отсюда получаем: U_ВХ(min) = 0,1 мВ

Задача 6.

Определить значение сигнала U = 2 + 5t – 2t² в момент времени t = 1,7, если он был квантован по времени с периодом Т = 0,2, а затем восстановлен трапециевидной аппроксимацией.

Решение.

В соответствии с заданным периодом квантования, отсчеты мгновенных значений сигнала были взяты в моменты времени t¢ = 1,6 и t²= 1,8. Значения сигнала в данные моменты времени составят:

U¢ = 2 + 5×1,6 – 2×1,6² = 4,88; и U² = 2 + 5×1,8 – 2×1,8² = 4,52.

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

U_восс(1,7) = (U¢ + U²)/2 = (4,88 + 4,52)/2 = 4,7

 

Задача 7.

Непрерывное сообщение квантуется по уровню и по времени. Шаг квантования по уровню равен 0,02 условной единицы. Какова должна быть максимальная величина интервала квантования по времени, если в спектре сигнала не содержится частот выше 1,0 кГц, а его производная изменяется не более, чем на 100 условных единиц в секунду.

Решение.

Величина интервала квантования, вычисленная на основе теоремы Котельникова, будет равна

Т_к1 = 1/2F_кр = 1/(2·1,0*10³) = 5·10^-4 c.

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

Т_к2 = D/ v =0,02/100 = 2·10^-4 c.

Из двух найденных величин следует выбрать меньшую – 2·10^-4 c

Тема Передача информации по каналам связи.

Физический уровень.

 

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

Поток информации это количество информации, передаваемое в единицу времени.

Для дискретного источника, передающего в канал связи N элементов в секунду поток информации (бит/сек) равен:

I = H(x)N

где H(x) - энтропия источника (равная среднему количеству информации на один элемент сообщения).

Максимальный поток информации по передающему каналу может быть записан:

,

где F_К – полоса частот канала; D_К – динамический диапазон канала.

Этот параметр называется пропускной способностью канала.

В свою очередь:

,

где N_C - средняя мощность полезного сигнала; N_Ш - средняя мощность шумов.

Логический уровень.

 

Модели дискретных каналов передачи.

На логическом уровне может быть построена модель дискретного канала, которая отражает процесс передачи элементов кода по этому каналу. В общем случае дискретный канал имеет на входе множество символов кода Х с энтропией источника Н(Х), а на выходе множество символов Y с энтропией H(Y). Модель такого канала можно изобразить в виде графа, в узлах которого расположены символы кода, а дуги отображают вероятности перехода из одного символа в другой. Количество символов конечно и определяется основанием системы счисления кода на входе канала. Вероятности переходов могут быть записаны в виде матрицы. Элемент матрицы P(y_i/x_j) определяет появление на выходе символа y_i при подаче на вход символа x_j.

 

Вероятности, связывающие символы с одинаковыми индексами, называются вероятностями прохождения, остальные – вероятности трансформации.

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

По основанию системы счисления кода на входе канала различают двоичные, десятичные и другие каналы.

Пропускная способность канала на логическом уровне определяется количеством бит на один символ (знак) и не связана со временем. Количество информации, передаваемое одним символом, составит

I_max = H_max(Y) – H_min(Y/X).

Если n – количество символов на входе канала, m – количество символов на выходе канала, слагаемые можно подсчитать так.

Максимальная энтропия выходного сигнала:

, где

Энтропия шумов:

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

Задача 8.

Определить полосу пропускания канала передачи на видеомонитор изображения, содержащего 5*10⁵ элементов трех основных цветов. Изображение передается с частотой 25 кадров/с. Каждый элемент имеет 8 равновероятных градаций яркости. Полезный сигнал является шумоподобным, отношение мощностей сигнал/шум равно 15

Решение.

Поток информации, рассчитанный через информационную энтропию, будет равен:

I = -(5*10⁵)*25*3*log₂(1/8) = 112,5×10⁶ (бит/с).

Необходимая полоса пропускания:

F_K = I/D = I/[log₂(1+N_C/N_Ш)] = I/log₂(16) = 112,5*10⁶/4 = 28,125*10⁶ Гц = 28,125 МГц

 

Задача 9.

Определить за какое время можно передать по каналу связи запись музыкального произведения, чтобы при последующем воспроизведении слышимые искажения отсутствовали. Продолжительность произведения 4,5 минуты, полоса частот канала 6 МГц, динамический диапазон канала в 4 раза уже диапазона произведения. Принять, что верхний предел частот, слышимых человеком равен 25 кГц

Решение.

Объем передаваемой информации:

V_C = F_CD_CT_C = 25*10³*D_C*×4,5*60 = 6,75*10⁶*D_C бит.

Поскольку диапазон канала в 4 раза уже диапазона сигнала,
т.е. D_C = 4D_K получим

V_C = 27*10⁶×D_K бит.

Из выражения для объема канала и условия передачи получим:

T_К = V_C /(F_КD_К) = 27*10⁶×D_K/(6*10^6*D_K) = 4,5 с

 

Задача 10.

 

Сигнал подается на вход канала с вероятностью 0,6. Определить количество информации, передаваемое по каналу, если граф канала приведен на рисунке.

Решение.

Матрица вероятностей будет иметь вид: .

Вероятности P(х_i) таковы: P(х₁) = 0,6; P(х₂) = 1 – 0,6 = 0,4.

Рассчитаем вероятности P(y_i).

Р(у₁) = Р(х₁)Р(у₁/х₁) + Р(х₂)Р(у₁/х₂) = 0,6×0,9 + 0,4×0,3 = 0,66;

Р(у₂) = Р(х₁)Р(у₂/х₁) + Р(х₂)Р(у₂/х₂) = 0,6×0,1 + 0,4×0,7 = 0,34

Максимальная энтропия в выходных сигналах:

H(Y) = -Р(у₁)×log₂Р(у₁) - Р(у₂)×log₂Р(у₂) = -0,6× log₂0,6 - 0,4×log₂0,4 = 0,925

Энтропия шумов (условная энтропия):

H(Y/Х) = -Р(х₁)[Р(у₁/х₁)×log₂Р(у₁/х₁)+Р(у₂/х₁)×log₂Р(у₂/х₁)] -

- Р(х₂)[Р(у₁/х₂)×log₂Р(у₁/х₂) + Р(у₂/х₂)×log₂Р(у₂/х₂)] =

= - 0,6[0,9×log₂0,9 + 0,1×log₂0,1] - 0,4[0,3log₂0,3 + 0,7×log₂0,7] = 0,634

Отсюда количество информации, передаваемое по каналу:

I = H (Y) – H (Y/X) = 0,925 – 0,634 = 0,29 бит/знак.

 

Задача 11.

Определить количество информации, передаваемое по двоичному каналу со стиранием с равновероятными сигналами на входе, если вероятность искажения символа равна нулю, а вероятность стирания 0,1.

Решение.

Граф такого канала будет иметь вид, показанный на рис.

Матрица вероятностей передачи:

Вероятности на входе P(х₁) = P(х₂) = 0,5.

Вероятности на выходе:

Р(у₁) = Р(х₁)Р(у₁/х₁) = 0,5×0,9 = 0,45; Р(у₂) = Р(у₁) = 0,45

Р(у_С) = Р(х₁)Р(у_С/х₁) + Р(х₂)Р(у_С/х₂) = 0,5×0,1 + 0,5×0,1 = 0,1

Отсюда максимальная энтропия в выходных сигналах по (6.11):

H(Y) = -Р(у₁)×log₂Р(у₁) - Р(у₂)×log₂Р(у₂) -Р(у_С)×log₂Р(у_С) =

-0,45×log₂0,45 -0,45×log₂0,45 -0,1×log₂0,1 = 1,369

Энтропия шумов по (6.12):

H(Y/Х) = -Р(х₁)[Р(у₁/х₁)×log₂Р(у₁/х₁) + Р(у_С/х₁)×log₂Р(у_С/х₁)] -

- Р(х₂)[Р(у_С/х₂)×log₂Р(у_С/х₂) + Р(у₂/х₂)×log₂Р(у₂/х₂)] =

= - 0,5[0,9×log₂0,9 + 0,1×log₂0,1] - 0,5[0,1log₂0,1 + 0,9×log₂0,9] = 0,469

Отсюда количество информации, передаваемое по каналу по (6.10):

I = H (Y) – H (Y/X) = 1,369 – 0,469 = 0,9 бит/знак.

 

Тема Конечные автоматы

 

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

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

Автомат следующим образом реагирует на поступление входных сигналов.

Во-первых, состояние автомата изменяется в соответствии с одношаговой функцией переходов:

z(t_j) = j[ z(t_j-1), x(t_j)]

Во-вторых, в каждый момент автоматного времени на выходеавтомата появляется выходной сигнал y(t_j), определяемый функцией выходов

y(t_j) = y[ z(t_j-1), x(t_j)]

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

Рассмотрим табличный способ задания автомата. При этом используются таблицы переходов и выходов, строки которых соответствуют входным сигналам автомата, а столбцы - его состояниям. На пересечении i -ой строки и j -го столбца таблицы переходов помещается соответствующее значение j(z_k,x_i) функции переходов, а в таблице выходов - y(z_k, x_i) функции выходов.

При графическом способе задания конечного автомата используется понятие направленного графа. Граф автомата представляет собой набор вершин, соответствующих различным состояниям автомата и соединяющих вершин дуг графа, соответствующих тем или иным переходам автомата. Если входной сигнал x_k вызывает переход из состояния z_i в состояние z_j, то на графе автомата дуга, соединяющая вершину z_i с вершиной z_j, обозначается x_k. Для того, чтобы задать функцию выходов, дуги графа необходимо дополнительно отметить соответствующими выходными сигналами.

При решении задач моделирования часто более удобной формой является матричное задание конечного автомата. При этом можно рассматривать две матрицы – матрицу переходов и матрицу выходов. Матрица переходов есть квадратная матрица С=|| c_ij ||, строки которой соответствуют исходным состояниям, а столбцы - состояниям перехода. Элемент c_ij соответствует входному сигналу x_k, вызывающему переход из состояния z_i в состояние z_j. Если переход из состояния z_i в состояние z_j происходит под действием нескольких сигналов, элемент матрицы c_ij представляет собой множество входов для этого перехода, соединённых знаком дизъюнкции. Матрица выходов D=|| d_ij || строится аналогично, но ee элемент d_ij соответствует выходному сигналу y_S, выдаваемому при переходе. Для рассматриваемого автомата Мили матрицы имеют вид:

На практике наибольшее распространение получили два класса автоматов - автоматы Мили(Mealy) и автоматы Мура(Moore).

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

Для автомата Мура функция переходов имеет тот же вид, как и у автомата Мили, но функция выходов не зависит от входного сигнала, а является функцией только текущего состояния:

 

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

Задача 12.

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

Таблица переходов Таблица выходов.

x z z0 z1 z2 x1 y1 y1 y2 x2 y1 y2 y1

Решение

Граф автомата, заданного исходными таблицами:

Матрицы переходов и выходов:

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

 

Тема Дискретные цепи Маркова

 

Случайный процесс, протекающий в системе A, называется марковским или случайным процессом без последствия, если для любого момента времени t₀ вероятность любого состояния системы при t > t₀ зависит только от ее состояния при t = t₀ и не зависит от того, как и когда система пришла в это состояние. Если число состояний A_i, которые система может принимать, конечно, то такие системы описывает марковский случайный процесс с дискретными состояниями, или марковская цепь.

Если переходы системы из одного состояния в другое возможны в строго определенные, заранее фиксированные моменты времени t_j, то такую систему описывает марковский случайный процесс с дискретным временем. Марковский случайный процесс с дискретными состояниями и дискретным временем называют дискретной марковской цепью.

Обычно марковскую цепь изображают в виде графа, вершины которого соответствуют возможным состояниям системы A_i, а дуги - возможным переходам системы из состояния A_i ® A_j. Каждой дуге соответствует переходная вероятность p_ij(k)=p[A_j^(k)/A_i^(k-1)] - это условная вероятность перехода системы на k -ом шаге в состояние A_j при условии, что на предыдущем (k-1)- ом шаге система находилась в состоянии A_i.

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

Кроме того, на каждом шаге Марковская цепь характеризуется вектором вероятностей состояний:

|S(t)| = [S₁(t),S₂(t),... S_n(t)]

Вероятностью i- го состояния называется вероятность S_i(t) того, что в момент t система будет находиться в состоянии A_i. Очевидно, что для любого момента t сумма вероятностей всех состояний равна единице:

Марковская цепь называется однородной, если переходные вероятности не зависят от номера шага. Если переходные вероятности меняются от шага к шагу, марковская цепь называется неоднородной.

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

Эргодические Марковские цепи описываются сильно связанным графом. Это означает, что в такой системе возможен переход из любого состояния A_i в любое состояние A_j (i = 1..n) за конечное число шагов.