3. Структурный синтез автоматов и кодирование информации

3.1. КОДИРОВАНИЕ, СОСТОЯНИЯ, ВХОДНЫХ И ВЫХОДНЫХ СИМВОЛОВ АВТОМАТА

Реальные автоматы имеют более сложную организацию, чем модель абстрактного автомата. Прежде всего каждый символ абстрактных алфавитов V, W и S представляется в виде цепочки символов соответствующего структурного алфавита X, Y, и Q соответственно. Эти цепочки имеют длину соответственно n, m и r для входных, выходных символов и символов состояний.

Представление символов абстрактного алфавита буквами соответствующего структурного алфавита называется кодированием.

Таким образом, мы вводим функции кодирования

Ψv : V → X ⁿ ,

Ψw : W → Y ^m ,

Ψs : S → Q ^k

Или в другом обозначении

x =Ψv (v) (v V)

y = Ψw (w) (w W),

q= Ψs (S) (s S),

где x =(x₁,…,x_n), y=(y₁,…,y_m), q=(q₁,…,q_{e) –}

- обозначения цепочек, кодирующих абстрактные символы v, w и s соответственно.

В вычислительной технике используют стандартные алфавиты устройств ввода – вывода.

Например: код ASCII, шестнадцатеричный алфавит

(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F) 8 – ричный (0, 1, 2, 3, 4, 5, 6, 7) 10 – ричнный (0, 1,......9) и двоичный (0, 1). Двоичный алфавит очень важен, поскольку он оказался наиболее удобным для технической реализации автоматов в виде конкретных устройств.

Количество разрядов в кодах x, y и q выбирается на основе соотношений

n ≥ ] log_|x| |V| [,

m≥ ] log_|y| |W| [,

k≥ ] log_|q| |S| [,

где ]α[ - округление до ближайшего большего целого;

|V|, |W|, |S|, |X|, |Y|, |Q| - мощности (числа символов)

алфавитов V, W, S, X, Y, Q.

В случае аппаратно-реализованных автоматов на двоичных элементах X= Y = Q = {0, 1} : n ≥ log₂ |V| [, m ≥ ]og₂ |W|[, k ≥]og₂ |S|[.

В дальнейшем будет рассматриваться случай только двоичного алфавита.

Основные понятия теории кодирования (4, 5, 6)

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

Цель кодирования – преобразование информации в такую форму, которая наиболее удобна для передачи, хранения и переработки информации.

Равномерное кодирование

Равномерным кодированием называется такое, при котором буквы алфавита А заменяются буквами алфавита В, причем каждой букве а А ставится в соответствие цепочка s букв из В одной и той же длины.

Например А= {a0 , a1, a2, a3, a4, a5, a6, a7,}, B= {0, 1}, коды букв из А приведены в табл. 12.

Таблица 12

а	s(a)
а0 а1 а2 а3 а4 а5 а6 а7	000 001 010 011 100 101 110 111

Если m= |A|, n= |B|, то длина цепочки s равна

|s|= ] log_n m[,

где ] [ означает операцию округления числа до ближайшего большего целого.

Эффективное кодирование

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

Пусть вероятности букв алфавита А заданы табл. 13.

Таблица 13

Буквы	Вероятность Р(а)	Кодовая комбинация s(a)
а0 а1 а2 а3 а4 а5 а6 а7	1/2 1/4 1/8 1/16 1/32 1/64 1/128 1/128	1 01 001 0001 00001 000001 0000001 0000000

Код Шеннона-фэно строится следующим образом. Буквы упорядочиваются в порядке уменьшения их вероятности. Затем они разбиваются на две группы – верхнюю и нижнюю – примерно с одинаковой суммой вероятностей. Буквы верхней группы получают первый символ кода 1, а буквы нижней – 0. Дальше процесс разбиения продолжается для каждой группы с записью очередных символов 1 и 0 в соответствующие позиции. Процесс заканчивается тогда, когда в каждой группе останется по одной букве.

Среднее число двоичных символов на букву алфавита А равно:

1ср=Р(а0) * 1(а0) +...+Р(ам)*1(ам),

где Р(а) – вероятность буквы а;

1(а)=|s(a)| - длина кодовой комбинации для а.

В рассмотренном примере при равномерном кодировании 1ср=3, а при кодировании по методу Шеннона-фэно приблизительно 1ср=1,984.

В данном примере 1ср=Н, где Н – энтропия источника сообщения, что связано с тем что вероятности Р(а) равны отрицательным степеням двойки. В общем случае коды Шеннона-фено дают 1ср>Н. Коды, получаемые по рассмотренной методике, являются префиксными, т.е. ни одна кодовая комбинация не является началом другой, более длинной комбинации (см. Табл. 13). Поэтому последовательность кодовых символов не требует разделителей. Например, последовательность символов 00010100000100000001010001111011101 воспринимается однозначно, как а3а1а5а7а0а1а3а0а0а0а1а0а0а1.

3. 2. ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ

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

Простейший вид помехоустойчивого кодирования - это контроль чётности, который заключается в следующем. К машинному слову X = x[n] x[n-1] ... x[1] х[0], которое необхо­димо контролировать, добавляется контрольный разряд у, который вы­числяется по Формуле: у - x[n] x[n-l] ... x[l] х[0], где 0 - логическая операция сложения по модулю 2,

Таким образом получается код с разрядом контроля четности

[Х]ч = x[n] x[n-l] ... х[1] x[0] у , причем при отсутствии искажений, контрольная сумма равна 0,т. е.

S = x[n] x[n-l]  ... x[1] x[0] у = 0. Если появляется сбой в одном, трех, пяти и т.д., т.е. в нечетном числе разрядов, то контрольная сумма S принимает значение 1.

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

пример. X = 1101 , тогда у =1101 = 1 и [ х ]ч = 11011 , причем S = 110011 = 0.

Если произойдет сбой, в результате которого [ X ]ч примет значение 11001, то S = 11001 = 1,

что и свидетельствует о наличии ошибки.

Коды Xэмминга

Эти коды являются классическим примером кодов, позволяющих локализовать сбой и, следовательно, исправить искаженный разряд. Для защиты n - разрядного слова добавляется k контрольных раз рядов. Таким образом, обшая длина кода Хэмиинга равна n+k .

Значение К выбирается из условия, что контрольные разряды образуют двоичное число, указывавшее номер искаженного Разряда или отсутствие искажений, т. е. это число принимает не менее n+k+1 зна чений. Следовательно, должно выполняться условие 2^k  n+k+1. Рассмотрим построение кода Хэмминга для 4-разрядных информа ционных слов Х= x3 х2 xl х0 . Число контрольных разрядов в этом случае k=3, а код Хэмминга [X]x= y7 y6 y5 У4 y3 y2 y1. Разряды кода Хэмминга разбиваются на k групп: Гk-1,Гk-2,.. ,Г1,Г0. в рас­сматриваемом примере это можно представить табл. 14.

Таблица 14

Разряд	Г2	Г1	Г0	Новое обозн.
-
у1			*	z0
у2		*		z1
у3		*	*	x0
у4	*			z2
у5	*		*	x1
у6	*	*		x2
у7	*	*	*	x3

В группу Г0 включены разряды y[i] , двоичные номера которых содержат 1 в младшем разряде yl, В группу Г1 включены разряды у[i] , двоичные номера которых содержат единицу в первом разряде, т. е. У2=1 и т. д.

В каждой группе разряд, содержащий один символ в строке, объявляется контрольным, т.е. y1=z0, y2=z1, y4=z2. В качестве ин­формационных берутся оставшиеся разряды. Например, у7=х3, y6=х2, y5=x1, y3-x0. Новые обозначения разрядов приведены в правом столбце табл.14.

В каждой группе Г1,Г2 и Г3 вычисляется сумма информационных разрядов по модулю 2 и ее значение присваивается контрольному разряду группы:

z0 = х0х1x3;

z1= х0х2хЗ;

z2 = xlx2x3.

Для определения номера искаженного разряда вычисляются суммы:

u0 = x0xlx3z0;

u1 = x0x2x3z1;

u2 = x1x2хЗz2;

что и дает двоичный номер u2 u1 u0 искаженного разряда.

Приме. Закодировать по методу Хэмнинга число 11. В по­лученный код искусственно ввести ошибку и затеи определить номер искаженного разряда.

Решение. Переведем число в двоичную систему счисления: DEC(11)= 1011. Число информационных двоичных разрядов n = 4. Количество контрольных разрядов К определим из условия:

2^k n + k + 1 или 2^k  5+k . Условие выполняется при к = 3. вид (см. табл. 14):

X3 Х2 X1

номера разрядов 76 5

Информационным разрядам этого кода присваиваем соответствующие значения, тогда код числа 11 примет вид:

1 0 1 z2 1 zl z0 . Определим значения контрольных разрядов:

z0 = x0x1xЗ = 111=1;

z1 = х0х2х3 = 101 = 0 ;

z2 = x1x2x3 = 101 = 0 ,

В результате получаем искомый код Хэмиинга: [11]x = 1010101 допустим, что в результате сбоя в разряде x0 возникла ошибка, т.е. единичное значение x0 изменилось на противоположное(нулевое). В результате код стал равен 1010001. Осуществим проверку искаженного кода:

u0.= z0x0x1x3 = 1011 = 1 ;

u1 =z1x0x2x3 = 0001 = 1 ;

u2 - z2x1x2x3 = 0101 = 0 ;

В результате получили, что ошибка в третьем разряде (011 в = 3 ), исправление ошибки сводится к инвертированию ошибочного разряда, что позволяет восстановить истинное значение кода,