Информатика и вычислительная техника

2.7.1. Прямые коды

Применяются для представления в ЭВМ числовых данных и используют двоичную систему счисления.

Выполним построение прямого кода для десятичных цифр с помощью табл. 2.1. Вначале выпишем десятичные цифры и их двоичные эквиваленты (табл. 2.2):

Таблица 2.2.

Связь десятичных и двоичных чисел

Десятичная цифра	Двоичный эквивалент
0	0
1	1
2	10
3	11
4	100
5	101
6	110
7	111
8	1000
9	1001

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

Таблица 2.3.

Прямые коды десятичных цифр

Десятичные цифры	Прямые коды
0	0000
1	0001
2	0010
3	0011
4	0100
5	0101
6	0110
7	0111
8	1000
9	1001

Закодируем построенными кодами дискретное сообщение 1743. Для этого каждый символ сообщения заменим двоичной комбинацией из табл. 2.3. Получим: 0001011101000011.

Закодируем построенными кодами дискретное сообщение 2012 тем же способом. Получим: 0010000000010010.

Для декодирования, например, последнего сигнала он просматривается (сканируется) в направлении слева направо (т.е. в направлении его составления). Поскольку известно, что длина кодовой комбинации - 4 двоичных символа, в строке выделяются последовательно четырехсимвольные комбинации и каждая сопоставляется с кодовой таблицей (в нашем примере это табл. 2.2). В кодовой таблице ищется подходящая строка и выполняется замена исходным символом. Таким образом, процедура декодирования примера представляется макетом:

0010	0000	0001	0010
2	0	1	2

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

Пример 2.18. Построить двоичные коды для символов a, b, c, d.

Пронумеруем исходные символы, начиная с нуля, и по табл. 2.1 сформируем двоичные коды для номеров символов. Тогда двоичные коды исходных символов примут вид:

Исходные символы	Номер	Двоичный код
a	0	0
b	1	1
c	2	10
d	3	11

Для получения двоичного кода постоянной длины добавим незначащие нули к кодовым комбинациям для a и b. Получим табл. 2.4:

Таблица 2.4.

Прямые коды символов

Исходные символы	Двоичные коды
a	00
b	01
c	10
d	11

Закодируем полученными кодами дискретный сигнал abba. Для этого выполним замену каждого символа сигнала на соответствующую кодовую комбинацию из табл. 2.4. Получим: 00010100.

Декодирование выполняется аналогично рассмотренному выше.

2.7.2. ASCII-коды

Наиболее распространенным кодом по образцу является код ASCII (American Standard Code for Information Interchange), который используется для внутреннего представления символьной информации в операционной системе MS DOS, в Блокноте операционной системы Windows'xx, а также для кодирования текстовых файлов в Интернете. Структура кода представлена ниже:

0

1

2

3

4

5

6

7

8

9

A

B

C

D

E

F

0

…

…

0

@

P

`

p

А

Р

а

…

…

…

р

Ё

1

…

…

!

1

A

Q

a

q

Б

С

б

…

…

…

с

ё

2

…

…

“

2

B

R

b

r

В

Т

в

…

…

…

т

/

3

…

…

#

3

C

S

c

s

Г

У

г

…

…

…

у

\

4

…

…

$

4

D

T

d

t

Д

Ф

д

…

…

…

ф

/

5

…

…

%

5

E

U

e

u

Е

Х

е

…

…

…

х

\

6

…

…

&

6

F

V

f

v

Ж

Ц

ж

…

…

…

ц

7

…

…

`

7

G

W

g

w

З

Ч

з

…

…

…

ч

8

…

…

(

8

H

X

h

x

И

Ш

и

…

…

…

ш

9

…

…

)

9

I

Y

i

y

Й

Щ

й

…

…

…

щ

A

…

…

*

:

J

Z

j

z

К

Ъ

к

…

…

…

ъ

B

…

…

+

;

K

[

k

{

Л

Ы

л

…

…

…

ы

C

…

…

,

<

L

\

l

|

М

Ь

м

…

…

…

ь

№

D

…

…

-

=

M

]

m

}

Н

Э

н

…

…

…

э

¤

E

…

…

.

>

N

^

n

~

О

Ю

о

…

…

…

ю

F

…

…

/

?

O

_

o

¤

П

Я

п

…

…

…

я

Таблица кодов содержит 16 столбцов и 16 строк; каждая строка и столбец пронумерованы в шестнадцатеричной системе счисления цифрами от 0 до F. Шестнадцатеричное представление ASCII-кода складывается из номера столбца и номера строки, в которых располагается символ. Так, например, ASCII-код символа 1 есть число 31₁₆, что по правилам перевода означает 110001₂. В двоичной системе код представляется восемью разрядами, т.е. двоичный ASCII-код символа 1 есть 00110001₂.

Данная таблица делится на две части: столбцы с номерами от 0 до 7 составляют стандарт кода - неизменяемую часть; столбцы с номерами от 8 до F являются расширением кода и используются, в частности, для кодирования символов национальных алфавитов. В столбцах с номерами 0 и 1 находятся управляющие символы, которые применяются, например, для управления принтером. Столбцы с номерами от 2 до 7 содержат знаки препинания, арифметических действий, некоторые служебные символы, а также заглавные и строчные буквы латинского алфавита. Расширение кода включает символы псевдографики, буквы национальных алфавитов и другие символы.

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

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

WINDOWS

57 49 4E 44 4F 57 53

Если удалить пропуски между кодовыми комбинациями, получим дискретный сигнал, построенный из символов шестнадцатеричного алфавита: 57494E444F5753.

Закодируем теперь ASCII-кодом тот же дискретный сигнал, но «написанный» несколько по-другому - Windows. Получим: 57696Е646F7773.

Анализ показывает, что первое шестнадцатеричное число имеет меньшее значение, чем второе, т.е. 57494E444F5753<57696Е646F7773. Это позволяет компьютеру выполнять упорядочение символьных данных, используя для этого внутреннее представление любых типов данных в виде чисел. Таким образом, WINDOWS<Windows.

2.7.3. Коды, учитывающие частоту информационных элементов

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

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

Пусть известны частоты букв и русского алфавита, и служебных символов (табл. 2.5):



Таблица 2.5.

Частоты букв русского алфавита и служебных символов

Буква	Частота		Буква	Частота		Буква	Частота
о	0,090		м	0,026		й	0,010
е (ё)	0,072		д	0,025		х	0,009
а	0,062		п	0,023		ж	0,007
и	0,062		у	0,021		ю	0,006
т	0,053		я	0,018		ш	0,006
н	0,053		ы	0,016		ц	0,004
с	0,045		з	0,016		щ	0,003
р	0,040		ь,ъ	0,014		э	0,003
в	0,038		б	0,014		ф	0,001
л	0,035		г	0,013		пробелы и знаки препинания	0,175
к	0,028		ч	0,012

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

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

Таблица 2.6.

Коды, учитывающие частоту

Буква	Частота	Код		Буква	Частота	Код		Буква	Частота	Код
о	0,090	000000		к	0,028	100001		г	0,013	000111
е	0,072	000001		м	0,026	000110		ч	0,012	001101
ё	0.072	000010		д	0,025	001010		й	0,010	011001
а	0,062	000100		п	0,023	010010		х	0,009	110001
и	0,062	001000		у	0,021	100010		ж	0,007	001011
т	0,053	010000		я	0,018	001100		ю	0,006	010011
н	0,053	100000		ы	0,016	010100		ш	0,006	100011
с	0,045	000011		з	0,016	100100		ц	0,004	001110
р	0,040	000101		ь	0.014	011000		щ	0,003	011100
в	0,038	001001		ъ	0,014	101000		э	0,003	111000
л	0,035	010001		б	0,014	110000		ф	0,001	101010

Как видно из табл. 2.6, минимальное число единиц, равное нулю, у символа с максимальной частотой - буквы «о». У кодов букв от «е» до «н» использована только одна единица в разных позициях кодовых комбинаций. В кодах символов от «с» до «б» применены 2 единицы в разных комбинациях. В остальных случаях используются 3 единицы.

Закодируем, например, слово «окно» с помощью построенной нами кодовой таблицы: 000000100001100000000000. Как видно, здесь только три единицы (читай - включенные лампочки).

Закодируем теперь слово «шумы»: 10001110001000110010100. Здесь девять единиц, т.е. этот сигнал более энергозатратен.

2.7.4. Коды Грея

В качестве кодового алфавита используются двоичные символы.

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

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

код Грея для 0 и 1 равен 0₂ и 1₂, соответственно. Получаем два кода Грея;

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

		номера столбцов
		0	1
номера строк	0	0	1
	1	3	2

Как видно, в ячейках матрицы размещены кодируемые десятичные числа, включая и уже закодированные 0 и 1. Стрелки показывают, как заполняются ячейки матрицы символами исходного алфавита (выделены полужирно). Тогда код Грея для произвольного числа, размещенного в некоторой ячейке, формируется как номер строки и номер столбца для этой ячейки. Так, код Грея для числа 0 - это 00₂, а для 1 - это 01₂, для 2 - 11₂, для 3 - это 10₂.

получив коды Грея для четырех десятичных чисел, используем их в качестве номеров строк и столбцов, чтобы сформировать кодовые комбинации для всех (4х4=16>10) символов алфавита:

	00	01	11	10
00	0	1	2	3
01	7	6	5	4
11	8	9
10

Получаем табл. 2.7:

Таблица 2.7.

Код Грея для десятичных цифр

Десятичная цифра	Код Грея
0	0000
1	0001
2	0011
3	0010
4	0110
5	0111
6	0101
7	0100
8	1100
9	1101

Как видно, коды упорядоченных чисел 1 и 2 различаются одним двоичным разрядом, а прямые коды этих же цифр - двумя разрядами. Аналогичную картину можно наблюдать в случае пар цифр 3 и 4; 5 и 6; 7 и 8.

Используем построенный код для кодирования числа 2012: 0011000000010011.

2.8. Криптографическое кодирование

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

2.8.1. Метод простой подстановки

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

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

Таблица 2.8.

Таблица соответствия символов из примера 2.19

А

Б

В

Г

Д

Е

Ё

Ж

З

И

Й

К

Л

М

Н

О

П

Р

С

Т

У

Ф

Х

Ц

Ч

Ш

Щ

Ь

Ы

Ъ

Э

Ю

Я

!

№

$

%

?

*

(

)

{

}

[

]

-

|

=

«

`

~

\

:

_

<

>

^

,

.

4

7

в

0

е

?

@

Тогда сообщение ИНФОРМАТИКА будет закодировано следующим образом: }=<«~|!:}]!.

Данный метод кодирования является ненадежным, так как при достаточно большой выборке закодированных сообщений при известных частотах символов исходного алфавита можно с определенной долей погрешности выполнить декодирование. В самом деле, пусть есть представительная выборка закодированных русскоязычных сообщений, общее число букв в которых равно M, и известны частоты букв русского алфавита (табл. 2.9):

Таблица 2.9.

Частоты букв кириллицы

Буква	Частота	Буква	Частота	Буква	Частота
о	0,090	м	0,026	й	0,010
е (ё)	0,072	д	0,025	х	0,009
а	0,062	п	0,023	ж	0,007
и	0,062	у	0,021	ю	0,006
т	0,053	я	0,018	ш	0,006
н	0,053	ы	0,016	ц	0,004
с	0,045	з	0,016	щ	0,003
р	0,040	ь,ъ	0,014	э	0,003
в	0,038	б	0,014	ф	0,001
л	0,035	г	0,013	пробелы и знаки препинания	0,175
к	0,028	ч	0,012

Можно рассчитать частоту f_S каждого s-го символа по формуле (2.2):

где m_S - количество s-х символов в сообщениях (иначе - абсолютная частота s-того символа).

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

Пример 2.20. Пусть есть закодированное сообщение из примера 2.19: }=<»~|!:}]!

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

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

Определим, что общее число символов М в конспекте на момент подготовки данного примера составляет 275979 символов.

Определяем, сколько раз встречаются интересующие нас символы из закодированного сообщения - m_s (табл. 2.10, строка m_s). Это позволяет рассчитать частоты символов f_s по формуле (2.2) и заполнить строку f_s табл. 2.10.

Сопоставим теперь полученные данные с таблицей частот. Наиболее близкие по значению символы для полученных частот сведены в табл. 2.10 в последнюю строку:

Таблица 2.10.

Таблица близости символов по частоте

s-й символ	}	=	<	«	~	|	!	:	]
ms	18716	14396	1436	22027	12058	8503	16835	13426	6592
fs	0,068	0,052	0,005	0,078	0,044	0,031	0,061	0,049	0,024
подходящий символ из таблицы частот	е,а,и	т,н	ю,ш,ц	е,о	с,р	л,к	а,и	т,н,с	д,п

Таким образом, кодовые символы из закодированного сообщения могут быть заменены символами из соответствующего множества:

}

=

<

«

~

|

!

:

}

]

!

исходные символы

е,а,и

т,н

ю,ш,ц

е,о

с,р

л,к

а,и

т,н,с

е,а,и

д,п

а,и

символы для замены

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

Очевидно, декодирование также возможно при известной таблице соответствия.

2.8.2. Метод Виженера

Разрушить статистические зависимости в закодированных сообщениях и тем самым повысить надежность кодирования можно с помощью метода Виженера.

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

Таблица 2.11.

Таблица соответствия для метода Виженера

А	Б	В	Г	Д	Е	Ё	Ж	З	И	Й	К	Л	М	Н	О	П	Р	С	Т	У	Ф	Х	Ц	Ч	Ш	Щ	Ь	Ы	Ъ	Э	Ю	Я
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32

Затем задаются ключом кодирования - словом в исходном алфавите, например, АСУ.

Собственно кодирование (второй этап) выполняется следующим образом: выписывают дискретный сигнал, подлежащий кодированию, например, пусть это будет сообщение ИНФОРМАТИКА, и выполняют следующие шаги:

а) под каждым его символом записывают порядковый номер из таблицы соответствия:

И	Н	Ф	О	Р	М	А	Т	И	К	А
9	14	21	15	17	13	0	19	9	11	0

б) под сообщением многократно выписывают ключевое слово:

И	Н	Ф	О	Р	М	А	Т	И	К	А
9	14	21	15	17	13	0	19	9	11	0
А	С	У	А	С	У	А	С	У	А	С

в) под символами ключа выписывают их порядковые номера из таблицы соответствия:

И	Н	Ф	О	Р	М	А	Т	И	К	А
9	14	21	15	17	13	0	19	9	11	0
А	С	У	А	С	У	А	С	У	А	С
0	18	20	0	18	20	0	18	20	0	18

г) порядковые номера символов складываются по модулю, равному числу символов исходного алфавита (в нашем случае - 33):

И	Н	Ф	О	Р	М	А	Т	И	К	А
9	14	21	15	17	13	0	19	9	11	0
А	С	У	А	С	У	А	С	У	А	С
0	18	20	0	18	20	0	18	20	0	18
9	32	8	15	2	0	0	4	29	11	18

Напомним, что сложение по модулю (обозначается ) выполняется без перемещения единицы переноса в старший разряд. Так мы получили, например, при сложении по модулю 33 чисел 21 и 20 (сумма равна 41, что на 8 превышает модуль 33) значение 8,

д) полученный числовой ряд преобразуется в символы исходного алфавита по таблице соответствия (табл. 2.11):

И	Н	Ф	О	Р	М	А	Т	И	К	А
9	14	21	15	17	13	0	19	9	11	0
А	С	У	А	С	У	А	С	У	А	С
0	18	20	0	18	20	0	18	20	0	18
9	32	8	15	2	0	0	4	29	11	18
И	Я	З	О	В	А	А	Д	Ъ	К	С

Таким образом, вместо дискретного сигнала ИНФОРМАТИКА имеем сообщение ИЯЗОВААДЪКС.

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

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

Пример 2.21. Декодировать сообщение ИЯЗОВААДЪКС, задавшись ключом АСУ и зная таблицу соответствия:

а) выписываем под закодированным сообщением порядковые номера символов из таблицы соответствия:

И	Я	З	О	В	А	А	Д	Ъ	К	С
9	32	8	15	2	0	0	4	29	11	18

б) выписываем под сообщением ключ с порядковыми номерами символов:

И	Я	З	О	В	А	А	Д	Ъ	К	С
9	32	8	15	2	0	0	4	29	11	18
А	С	У	А	С	У	А	С	У	А	С
0	18	20	0	18	20	0	18	20	0	18

в) вычитаем с учетом модуля 33 из чисел в закодированном сообщении числа для ключа:

И	Я	З	О	В	А	А	Д	Ъ	К	С
9	32	8	15	2	0	0	4	29	11	18
А	С	У	А	С	У	А	С	У	А	С
0	18	20	0	18	20	0	18	20	0	18
9	14	21	15	17	13	0	19	9	11	0

г) преобразуем числа в символы по таблице соответствия:

И	Я	З	О	В	А	А	Д	Ъ	К	С
9	32	8	15	2	0	0	4	29	11	18
А	С	У	А	С	У	А	С	У	А	С
0	18	20	0	18	20	0	18	20	0	18
9	14	21	15	17	13	0	19	9	11	0
И	Н	Ф	О	Р	М	А	Т	И	К	А

При декодировании возникла сложность в получении кодов символов Ф, Р, М, Т. В самом деле, при вычитании из 8 числа 20 получалось -12. Тогда к 8 прибавили модуль 33, получили 41 и уже из 41 вычли 20. Получили 21 - порядковый номер символа Ф. Аналогично поступили и с остальными проблемными символами.

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

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

2.9.1. Универсальные методы

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

где k - число символов исходного алфавита.

Строятся двоичные коды переменной длины по принципу: чем больше частота символа, тем короче его код. Эффективность кода определяется средним числом двоичных разрядов для кодирования одного символа - l_ср по формуле (2.4):

где n_s - число двоичных разрядов для кодирования s-го символа;

f_s - частота s-го символа.

Существуют два универсальных метода эффективного кодирования: Шеннона-Фано и Хаффмена. Входными данными для обоих методов является множество исходных символов с частотами; результат - эффективные коды.

2.9.1.1. Метод Шеннона-Фано

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

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

б) кодовым комбинациям первой части приписывается 1, кодовым комбинациям второй части приписывается 0;

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

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

д) анализируется оставшийся список: если он пуст - код построен, работа заканчивается. Если нет - выполняется шаг а).

Пример 2.22. Даны символы a, b, c, d с частотами f_a=0,5; f_b=0,25; f_c=0,125; f_d=0,125. Построить эффективный код методом Шеннона-Фано.

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

Первая линия деления проходит под символом a: соответствующие суммы ₁ и ₂ равны между собой и равны 0,5. Тогда формируемым кодовым комбинациям дописывается 1 для верхней (первой) части и 0 для нижней (второй) части. Поскольку это первый шаг формирования кода, двоичные цифры не дописываются, а только начинают формировать код. В силу того, что верхняя часть списка содержит только один элемент (символ а), работа с ней заканчивается, а эффективный код для этого символа считается сформированным.

Второе деление выполняется под символом b: суммы частот ₁ и ₂ вновь равны между собой и равны 0,25. Тогда кодовой комбинации символов верхней части дописывается 1, а нижней части - 0. Таким образом, к полученным на первом шаге фрагментам кода, равным 0, добавляются новые символы. Поскольку верхняя часть нового списка содержит только один символ (b), формирование кода для него закончено.

Третье деление проходит между символами c и d: к кодовой комбинации символа c приписывается 1, коду символа d приписывается 0.

Таким образом, получили коды:

a - 1,

b - 01,

c - 001,

d - 000.

Определим эффективность построенного кода:

l_ср = 0,5*1 + 0,25*01 + 0,125*3 + 0,125*3 = 1,75.

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

Закодируем дискретный сигнал abba построенным кодом: 101011.

Таблица 2.12.

Построение эффективного кода методом Шеннона-Фано

Исход- ные сим- волы	Час- тоты символов	Этапы построения кода	Формируемый код
		первое деление	второе деление	третье деление	первое деление	второе деление	третье деление
a	0,5	1=0,5	код для символа a сформирован	1	-	-
b	0,25		1 = 0,25	код для символа b сформирован	0	1	-
c	0,125	2=0,25+0,125+0,125=0,5	2=0,125+0,125=0,25	1 = 0,125 2 = 0,125	0	0	1
d	0,125				0	0	0

2.9.1.2. Метод Хаффмена

Этот метод имеет два преимущества по сравнению с методом Шеннона-Фано: он устраняет неоднозначность кодирования, возникающую из-за примерного равенства сумм частот при разделении списка на две части (линия деления проводится неоднозначно), и имеет, в общем случае, большую эффективность кода.

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

1) объединение частот:

две последние частоты складываются, а соответствующие символы исключаются из списка;

оставшийся после исключения символов список пополняется полученной в предыдущем пункте суммой частот и вновь упорядочивается;

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

2) построение кодового дерева:

строится двоичное кодовое дерево: корнем его является вершина, полученная в результате объединения частот, равная 1; листьями - исходные вершины; остальные вершины соответствуют либо суммарным, либо исходным частотам, причем для каждой вершины левая подчиненная вершина соответствует большему слагаемому, а правая - меньшему; ребра дерева связывают вершины-суммы с вершинами-слагаемыми. Структура дерева показывает, как происходило объединение частот;

ребра дерева кодируются: каждое левое кодируется единицей, каждое правое - нулем;

3) формирование кода: для получения кодов листьев (исходных кодируемых символов) продвигаются от корня к нужной вершине и «собирают» коды проходимых ребер.

Пример 2.23. Даны символы a, b, c, d с частотами f_a=0,5; f_b=0,25; f_c=0,125; f_d=0,125. Построить эффективный код методом Хаффмена.

1) объединение частот (табл. 2.13):

Таблица 2.13.

Объединение частот

Исходные символы s	Частоты fs	Этапы объединения
		первый	второй	третий
a	0,5	0,5	0,5	1
b	0,25	0,25	0,5
c	0,125	0,25
d	0,125



2) построение кодового дерева:

3) формирование кода:

a - 1;

b - 01;

c - 001;

d - 000.

Как видно, полученные коды совпадают с теми, что были сформированы методом Шеннона-Фано, следовательно, они имеют одинаковую эффективность.

Закодируем дискретное сообщение abba построенным кодом: 101011.

2.9.1.3. Повышение эффективности кодирования

Повысить эффективность кодирования можно, строя код не для символа, а для блоков из n символов. Рассмотрим этот тезис на примере.

Пример 2.24. Даны символы a и b с частотами, соответственно, 0,9 и 0,1. Построить эффективный код методом Шеннона-Фано для блоков из двух символов (n=2).

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

Блоки исходных Частоты блоков

символов f ^блока = f₁ * f₂

aa 0,81

ab 0,09

ba 0,09

bb 0,01

Построение кода сведем в табл. 2.14.

Таблица 2.14.

Метод Шеннона-Фано для блоков символов

Блоки исходных символов	Частоты блоков	Этапы построения кода
		первый	второй	третий
aa	0,81	1	код построен
ab	0,09	0	1	код построен
ba	0,09	0	0	1
bb	0,01	0	0	0

Таким образом, получены коды:

aa - 1;

ab - 01;

ba - 001;

bb - 000.

Определим эффективность построенного кода. Для этого рассчитаем сначала показатель эффективности для блока символов:

l_ср ^блока = 0,81*1 + 0,09*2 + 0,09*3 + 0,01*3 = 1,28.

Поскольку в блоке два символа (n=2), для одного символа

При посимвольном кодировании для эффективного кода потребуется по одному двоичному разряду. В самом деле, применение метода Шеннона-Фано дает результат, представленный в табл. 2.15.

Таблица 2.15.

Метод Шеннона-Фано для отдельного символа

Исходные символы	Частоты символов	Построение кода
a	0,9	1
b	0,1	0

Таким образом, при блочном кодировании выигрыш составил 1-0,64=0,36 двоичных разрядов на один кодируемый символ в среднем.

Эффективность блочного кодирования тем выше, чем больше символов включается в блок.

Закодируем построенным кодом дискретный сигнал abba: 01001.

2.9.1.4. Декодирование универсальных эффективных кодов

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

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

Для раскрытия данного тезиса вернемся к кодам из примера 2.23. Там самым коротким кодом был код для символа a со значением 1. Как видно, ни один другой код (более длинный) не имеет в своем начале символ 1. Второй по длине код для символа b имеет значение 01 и, как показывает анализ, не является началом ни для кода 001, ни для кода 000. Таким образом, код из примера 2.23 является префиксным.

Свойство префиксности позволяет декодировать сообщения, закодированные эффективными кодами.

Пусть получено сообщение 1010010001, составленное из кодов, построенных в примере 2.23:

a - 1;

b - 01;

c - 001;

d - 000.

Выполним его декодирование.

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

Итак, имеем:

направление просмотра цепочки

1 0 1 0 0 1 0 0 0 1

a ^{- - -} a

b ^{- -}

с d

Здесь знак «-» означает, что попытка декодирования не удалась.

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

Отметим, что методы Шеннона-Фано и Хаффмена строят префиксные коды.

2.9.2. Специальные методы эффективного кодирования

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

2.9.2.1. Методы эффективного кодирования числовых последовательностей

Различают два метода - разностное кодирование и кодирование повторений.

Суть разностного кодирования заключается в хранении вмес-то абсолютных значений либо разностей двух смежных чисел, либо отк-лонения чисел от их среднего значения. Например, для последо-вательности чисел: 2 14 18 27 34 первый способ даст после-довательность: 2 12 4 9 7.

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

Этот метод эффективен для монотонно возрастающих или монотонно убывающих после-довательностей. Его недостаток состоит в том, что для получения значения n-го члена последовательности надо декодировать все предыдущие (n-1) членов последовательности.

Второй способ порождает последо-вательность: -17 -5 -1 8 15, поскольку среднее значение для исходной последовательности - 19.

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

Таким образом, реальная закодированная последовательность из примера имеет несколько другой вид, что снижает эффективность: -17 -5 -1 8 15 19. Здесь среднее арифметическое записано крайним справа.

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

Кодирование повторений заключается в замене цепочки оди-наковых цифровых символов самим символом и числом повторений (возможно включение разделителей). Напри-мер, для последовательности: 55556666888888 применение этого способа даст последовательность: 5(4)6(4)8(6), где круглые скобки играют роль разделителей.

Данный метод может быть использован для эффективного кодирования растровых форматов изображений. Растровыми называются форматы изображений, которые получаются во время ввода изображения путем кодирования каждой точки - пиксела (pixel - PIсture ELement) - двумерного пространства, на котором расположено исходное изображение, даже если эта точка не содержит самого изображения. Очевидно, в общем случае, изображение занимает не все пространство. Тем не менее кодированию подлежат и «пустоты», при этом те точки, которые содержат изображение, в простейшем случае (для монохромных изображений) кодируются двоичной 1, точки без изображения кодируются двоичным 0. В результате получаются числовые последовательности, подобные следующей:

00000000000000000000000000000000000000000000000010000000000000000000.

Переведем эту двоичную последовательность в набор шестнадцатеричных цифр, используя тетрады. Получим последовательность шестнадцатеричных цифр: 00000000000080000.

Очевидно, к таким последовательностям можно применить метод кодирования повторений. В результате для нашего случая получим (круглые скобки используем как разделители): 0(С)8000, что означает: 0 повторяется 12 раз (С₁₆ = 12), для остальных символов число повторений не вводится.

Поскольку результирующая последовательность должна также быть шестнадцатеричной, полученное выражение преобразуем следующим образом: заменим круглые скобки соответствующими ASCII-кодами. Тогда открывающей скобке соответствует код 28₁₆, закрывающей - 29₁₆. Получим: 028С2980000.

Длина результата меньше исходной последовательности (11 символов против 17), поэтому получен эффект в 6 символов.

2.9.2.2. Методы эффективного кодирования словарей

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

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

Пусть есть фрагмент словаря со словами: вычислитель, вычислительный, вычислять.

Очевидно, у двух подряд расположенных слов есть общие буквы в начале. Тогда можно выполнить следующую замену: вычислитель, 11ный , 6ять , где числа означают, сколько букв из предыдущего слова надо взять, чтобы восстановить данное слово. Здесь слово «вычислитель» можно рассматривать как некоторое базовое слово, которое не подвергается кодированию.

Таким образом, имеем:

исходный словарь закодированный словарь

вычислитель вычислитель

вычислительный 11ный

вычислять 6ять

Недостаток данного подхода заключается в необходимости декодировать все (n-1) слов, начиная с базового слова, для декодирования n-го слова словаря.

Второй подход состоит в том, что формируется вспомогательный словарь, в который включаются наиболее часто повторяющиеся части слов (в нашем случае, например, это фрагменты слов «вычисл» и «итель»). Каждому такому фрагменту назначается код, например, его порядковый номер во вспомогательном словаре. Затем в основном словаре фрагменты слов заменяются их кодами из вспомогательного словаря.

Для нашего примера будут сформированы два словаря:

основной вспомогательный

12 1 - вычисл

12ный 2 - итель

1ять

Таким образом, при заданном вспомогательном словаре выполняется преобразование исходного словаря в закодированный:

исходный словарь закодированный словарь

вычислитель 12

вычислительный 12ный

вычислять 1ять

2.9.2.3. Методы эффективного кодирования естественно-языковых текстов

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

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

Например, пусть задан исходный текст:

«информатика изучает способы обработки информации».

В этом тексте дважды повторяются фрагменты «информа» длиной 7 символов (они выделены полужирно). Построим эффективно закодированный текст:

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

«информатика изучает способы обработки 38/7ции»,

38 символов

где знак / играет роль разделителя.

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

Таким образом, для нашего примера имеем:

«31/7тика изучает способы обработки информации».

31 символ

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

2.10. Помехозащитное кодирование

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

2.10.1. Искажение кодовых комбинаций

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

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

Искажение рассматривается как сложение по модулю 2 исходной кодовой комбинации a₁a₂…a_k и вектора ошибки b₁b₂…b_k: a₁a₂…a_k b₁b₂…b_k = c₁c₂…c_k ,где c₁c₂…c_k - искаженная кодовая комбинация.

Пусть имеется таблица кодов (табл. 2.16):

Таблица 2.16.

Прямые коды

Исходные символы	Прямые коды
a	00
b	01
c	10
d	11

Пусть на передаваемые кодовые комбинации накладывается помеха с кратностью ошибки 1, т.е. соответствующие ошибке кодовые комбинации - элементы множества {01, 10}.

Передается кодовая комбинация 10 (код символа c). Тогда возможное искажение представлено в табл. 2.17.

Таблица 2.17.

Результат искажения

Передаваемая кодовая комбинация	Вектор ошибки	Принимаемая кодовая комбинация	Результат декодирования
10	01	11	d
10	10	00	a

Таким образом, в результате ошибки принимающая сторона вместо символа c примет символ d или a и ошибка даже не будет обнаружена.

2.10.2. Кодовое расстояние и корректирующая способность кода

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

Расстоянием d_ij между кодовыми комбинациями i и j называется число различных разрядов в кодовых комбинациях i и j. Например, если есть коды 01 и 10, расстояние между ними равно 2: они различаются в двух разрядах.

Кодовым расстоянием d для кода, содержащего m кодовых комбинаций, является минимальное расстояние между всеми парами кодовых комбинаций, т.е. d=min{d_ij}.

Определим кодовое расстояние для кода из табл. 2.16:

d_ab = 1; d_ad = 2; d_bd = 1; d_ac = 1; d_bc = 2; d_cd = 1.

Тогда d = min{1,2,1,1,2,1} = 1. Это означает, что всякая ошибка кратности 1 (и более) переводит исходную кодовую комбинацию в другую кодовую комбинацию, которая также принадлежит коду.

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

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

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

Таблица 2.18.

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

Исходные символы	Информационные разряды кода	Проверочный разряд кода	Результирующий код
a	00	0	000
b	01	1	011
c	10	1	101
d	11	0	110

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

Определим кодовое расстояние полученного кода:

d_ab = 2; d_ad = 2; d_bd = 2; d_ac = 2; d_bc = 2; d_cd = 2.

Тогда d = min{2,2,2,2,2,2} = 2.

Пусть передается кодовая комбинация, соответствующая символу c, - 101. Пусть на нее накладывается ошибка кратности 1. Возможные результаты искажения приведены в табл. 2.19.



Таблица 2.19.

Результаты искажения

Передаваемая кодовая комбинация	Вектор ошибки	Принимаемая кодовая комбинация	Результат декодирования
101	001	100	Невозможно декодировать
101	010	111	То же
101	100	001	“-“

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

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

Разрешенными кодовыми комбинациями называются те, которые соответствуют символам исходного алфавита. Их количество равно числу исходных символов (m). Запрещенные кодовые комбинации - это те, которые отсутствуют в исходной кодовой таблице. Их количество определяется по формуле: 2^r - m, где r - общее число двоичных разрядов (информационные плюс проверочные) в коде.

Сформируем все разрешенные и запрещенные кодовые комбинации для нашего кода, при этом используем схему формирования кода Грея (обозначения строк - исходные коды, обозначения столбцов - значения проверочных разрядов):

	0	1
00	a
01		b
11	d
10		c

Здесь пустые ячейки означают запрещенные кодовые комбинации. Как видно, отстояние кодовых комбинаций для исходных символов a, b, c, d равно двум разрядам:

символы, находящиеся в одном столбце (a и d, b и c), имеют одинаковый проверочный разряд, но находятся в несмежных строках, которые различаются двумя разрядами;

символы, находящиеся в смежных строках (a и b, b и d, d и c), которые различаются одним разрядом, расположены попарно в разных столбцах, имеющих различное обозначение.

Поэтому при наличии ошибки кратности 1 кодовая комбинация переходит в соседнюю запрещенную комбинацию.

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



	0	1
0	a	b
1	c	d

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

Существует связь между кодовым расстоянием d и минимальной кратностью ошибки q, которую код может обнаруживать: d q + 1.

Пример 2.25. На базе кода табл. 2.16 построить код, обнаруживающий ошибки кратности 2.

Воспользуемся схемой формирования кода Грея с некоторыми модификациями.

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

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

С учетом сделанных замечаний схема имеет четыре столбца и четыре строки и представлена ниже:

	00	01	11	10
000	a
011		b
110			d
101				c

Таким образом, построен следующий код:

00000 a, 01101 b, 11011 d, 10110 c.

Определим кодовое расстояние d построенного кода:

d_ab = 3; d_ad = 4; d_bd = 3; d_ac = 3; d_bc = 4; d_cd = 3.

Тогда d = min{3,4,3,3,4,3} = 3.

Проверим, обнаруживает ли построенный код ошибку кратности 2. Для этого зададимся произвольной кодовой комбинацией, например, 01101 (символ b). Результат проверок приведен в табл. 2.20:



Таблица 2.20.

Результат декодирования

Передаваемая кодовая комбинация	Вектор ошибки	Принимаемая кодовая комбинация	Результат декодирования
01101	00011	01110	Невозможно декодировать
01101	00101	01000	То же
01101	00110	01011	“-“
01101	01001	00100	“-“
01101	01010	00111	“-“
01101	01100	00001	“-“
01101	10001	11100	“-“
01101	10010	11111	“-“
01101	10100	11001	“-“
01101	11000	10101	“-“

Таким образом, задача решена.

2.10.3. Коды, исправляющие ошибки

Особое значение имеют помехозащитные коды, которые могут исправлять ошибки определенной кратности. Соотношение между максимальной кратностью исправляемой ошибки q и кодовым расстоянием d определяется по формуле (2.5):

d 2q + 1. (2.5)

В основу исправления ошибок положена следующая идея: определяется множество кодовых комбинаций, включающее все разрешенные и те запрещенные, которые получены при искажении ошибкой кратности не более q. Это множество разбивается на m подмножеств, где m - число исходных кодируемых символов. В каждое подмножество входят: одна разрешенная кодовая комбинация и ближайшие к ней запрещенные, которые отстоят от разрешенной на расстояние не больше q. Тогда при декодировании определяется, в какое подмножество входит принятая кодовая комбинация. Если она является разрешенной, то сразу декодируется; если она запрещенная, то исправляется на разрешенную, с которой находится в одном подмножестве, а затем декодируется.

Пример 2.26. Построить помехозащитный код, исправляющий ошибку кратности 1, для передачи двух символов: a и b.

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

a 0,

b 1.

Поскольку по заданию q = 1, для исправления ошибки кратности 1 кодовое расстояние должно быть равно, по меньшей мере, 3.

Поскольку в первичном коде обеспечено расстояние между кодовыми комбинациями, равное 1, для выполнения условия d = 3 необходимо, чтобы проверочные разряды обеспечивали расстояние между кодовыми комбинациями, по меньшей мере, равным 2. Очевидно, для этого число проверочных разрядов должно быть не меньше 2. Тогда разрешенные кодовые комбинации могут иметь вид: