Теория кодирования

 
 
 
 
 
Н.Ю. Прокопенко  
 
 
 
 
 
 
 
 
ТЕОРИЯ КОДИРОВАНИЯ 
 
Учебное пособие 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Нижний Новгород 
2023 
 

Министерство науки и высшего образования Российской Федерации 
Федеральное государственное бюджетное образовательное учреждение высшего образования  
«Нижегородский государственный архитектурно-строительный университет»  
 
 
 
 
 
 
Н.Ю. Прокопенко  
 
 
 
 
 
ТЕОРИЯ КОДИРОВАНИЯ 
 

Утверждено редакционно-издательским советом университета в 

качестве учебного пособия 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Нижний Новгород 
ННГАСУ 
2023 
 

УДК 519(075) 
ББК 22.17я73 
П78 

 

Публикуется в авторской редакции 

Рецензенты: 

И.Н. Цветкова – канд. физ.-мат. наук, доцент кафедры информатики и 

информационных технологий Нижегородского института управления Российской 
академии народного хозяйства и государственной службы при Президенте РФ (НИУ 
РАНХиГС) 

О.А. Парфенова – зам. руководителя дивизиона «Корпоративные проекты 1С» 

ООО «Группа ЛАД» 
 

Прокопенко Н.Ю. Теория кодирования [Электронный ресурс]: учеб. пособие / Н.Ю. 
Прокопенко; Нижегор. гос. архитектур. - строит. ун-т – Н. Новгород: ННГАСУ, 2023. – 94 
с. 1 электрон. опт. диск (CD-RW)  
ISBN 978-5-528-00533-1 
 
 

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

ББК 22.17я73 
 
 

 

 

 

 

 

 

 

 

ISBN 978-5-528-00533-1 
 
 
                   © Прокопенко Н.Ю., 2023 
 
 
 
 
           © ННГАСУ, 2023 

  
 

Оглавление 

1. Введение в теорию кодирования ..................................................................... 5 

Задания ................................................................................................................ 15 

2. Алфавитное кодирование ............................................................................... 17 

3. Алгоритм Маркова распознавания взаимной однозначности алфавитного 

кодирования ........................................................................................................... 23 

Задания ................................................................................................................ 28 

4. Построение префиксного кода ...................................................................... 30 

4.1. Представление префиксного кода с помощью дерева ............................. 32 

4.2. Алгоритмы построения префиксного кода по набору длин 

элементарных кодов .............................................................................................. 33 

5. Оптимальное кодирование ............................................................................. 39 

5.1. Алгоритм Фано ............................................................................................ 42 

5.2. Алгоритм Шеннона ..................................................................................... 45 

5.3. Алгоритм Хаффмана ................................................................................... 46 

Задания ................................................................................................................ 57 

6. Помехоустойчивое кодирование ................................................................... 59 

6.1. Классификация помехоустойчивых кодов ................................................ 60 

6.2. Код Хэмминга .............................................................................................. 67 

6.3. Линейно блочные коды ............................................................................... 75 

Задания ................................................................................................................ 91 

Список литературы ............................................................................................... 94 

 

 

 

1. Введение в теорию кодирования 

Теория кодирования– это раздел теории информации, изучающий 

способы отождествления сообщений с отражающими их сигналами. Задачей 

теории кодирования является согласование источника информации с каналом 

связи. 

Кодирование буквально пронизывает информационные технологии и 

является центральным вопросом при решении самых разных (практически всех) 

задач программирования: 

 
Представление данных произвольной природы (например, чисел, 

текста, графики) в памяти компьютера; 

 
Защита информации от несанкционированного доступа; 

 
Обеспечение помехоустойчивости при передаче данных по каналам 

связи; 

 
Сжатие информации в базах данных. 

Кодированием 
называют 
универсальный 
способ 
отображения 

информации при ее хранении, обработке и передаче в виде системы 

соответствий между сигналами и элементами сообщений, при помощи которых 

эти элементы можно зафиксировать. 

Объектом кодирования служит как дискретная, так и непрерывная 

информация, которая поступает к потребителю через источник информации. 

Понятие кодирование означает преобразование информации в форму, удобную 

для передачи по определенному каналу связи. 

Обратная операция – декодирование – заключается в восстановлении 

принятого сообщения из закодированного вида в общепринятый, доступный 

для потребителя. 

В теории кодирования существует ряд направлений: 

− 
статическое или эффективное кодирование; 

− 
помехоустойчивое кодирование; 

− 
корректирующие коды; 

− 
циклические коды; 

− 
арифметические коды. 

Кодирование – это способ представления объектов одной природы (точек 

плоскости, 
чисел, 
слов 
какого-либо 
языка 
и 
т.д.) 
конечными 

последовательностями объектов другого множества (обычно конечного). 

Поскольку 
элементы 
этого 
второго 
конечного 
множества 
можно 

перенумеровать, то его всегда можно считать набором чисел, однако, это 

необязательно. 

Десятичная позиционная система счисления – это способ кодирования 

натуральных чисел, двоичная система счисления – это другой способ 

кодирования этих чисел. Римские цифры – еще один способ кодирования.  

Декартовы координаты – способ кодирования геометрических объектов. 

Замена имен номерами является кодированием, запись текстового файла 

на съемный носитель – кодирование, представление фотографии в цифровом 

фотоаппарате в виде файла – кодирование. 

Наборы символов, которыми пользуются при кодировании, называются 

алфавитами. Последовательности символов алфавита называются словами.  

Письменность – это алфавитное кодирование. Например, можем 

закодировать слово «информатика» последовательностью нулей и единиц. Для 

этого можем заменить буквы их порядковыми номерами в алфавите, и затем 

номера записать в двоичном виде. 

Примеры систем кодирования: 

1. Двоичная, восьмеричная и шестнадцатеричная системы счисления 

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

представимо в виде суммы степеней 2, причем каждая степень в этой сумме 

появляется не больше одного раза, т. е. с коэффициентом 0 или 1. Эти 

коэффициенты составляют представление числа в двоичной системе 

счисления. 

Например, 83=64+16+2+1=1010011. 

Таким образом, каждый набор из k нулей и единиц соответствует 

какому-либо числу в диапазоне от 0 до 2k−1. 

При переводе чисел из десятичной системы счисления в систему с 

основанием P > 1 обычно используют следующий алгоритм: 

1) если переводится целая часть числа, то она делится на P, после чего 

запоминается остаток от деления. Полученное частное вновь делится на P, 

остаток запоминается. Процедура продолжается до тех пор, пока частное не 

станет равным нулю. Остатки от деления на P выписываются в порядке, 

обратном их получению; 

2) если переводится дробная часть числа, то она умножается на P, после 

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

часть умножается на P и т. д. Процедура продолжается до тех пор, пока дробная 

часть не станет равной нулю. Целые части выписываются после запятой в 

порядке их получения. Результатом может быть либо конечная, либо 

периодическая дробь в системе счисления с основанием P. Поэтому, когда 

дробь является периодической, приходится обрывать умножение на каком-либо 

шаге и довольствоваться приближенной записью исходного числа в системе с 

основанием P. 

Пример. Перевести из десятичной в двоичную систему счисления 

число 42.73. 

Отдельно переведем целую и дробную части числа. 

a) 
Для перевода целой части (=42) проводим ряд последовательных 

делений десятичного числа 42 на 2. При каждом таком делении находим 

частное (r) и остаток (q). На каждом шаге полученное частное вновь делим на 2.  

42:2=21 (0) 

21:2=10 (1) 

10:2=5 (0) 

5:2=2 (1) 

2:2=1 (0) 

r=21, q=0 

r=10, q=1 

r=5, q=0 

r=2, q=1 

r=1, q=0 

1:2=0 (1) 
r=0, q=1 (Stop) 

Полученные остатки q выписываем, начиная с самого последнего и до 

первого. Это и будет двоичный код числа 42: 42= 101010. 

b) 
Для перевода дробной части (0.73) заданного десятичного числа в 

двоичное проводим ряд последовательных умножений на 2. В полученном 

произведении на каждом шаге отделяем целую часть (r) от дробной (q). 

Дробную часть вновь умножаем на 2 и т. д. Процесс заканчивается, если на 

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

которых очередная дробная часть уже встречалась на предыдущих шагах 

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

момент не наступает, то мы имеем с бесконечной двоичной дробью. 

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

последней – это и будет искомая двоичная дробь. 

0.73·2=1. (46) 

0.46·2=0. (92) 

0.92·2=1. (84) 

0.84·2=1. (68) 

0.68·2=1. (36) 

и т.д.  

r=1, q=0.46 

r=0, q=0.92 

r=1, q=0.84 

r=1, q=0.68 

r=1, q=0.36 

Мы прервали перевод дроби 0.73 и получили ее приближенное 

представление в виде бинарной дроби: 0.73≈0.10111… 

Окончательно получаем: 42.73≈101010.10111… 

При переводе чисел из системы счисления с основанием P в десятичную 

систему счисления необходимо пронумеровать разряды целой части справа 

налево, начиная с нулевого, и в дробной части, начиная с разряда сразу после 

запятой слева направо. 

Пример. 

а) 1000001(2). 

1000001(2)=1·26+0·25+0·24+0·23+0·22+ 0·21+1·20 = 64+1=65(10). 

Замечание. Очевидно, что если в каком-либо разряде стоит нуль, то 

соответствующее слагаемое можно опускать. 

б) 1000011111,0101(2). 

1000011111,0101(2)=1·29 + 1·24 + 1·23 + 1·22 + 1·21 + 1·20 + 1·2-2 + 1·2-4= 512 + 16 

+ 8 + 4 + 2 + 1 + 0,25 + 0,0625 = 543,3125(10). 

Двоичная система счисления удобна для компьютера, но неудобна для 

человека – слишком длинные получаются записи чисел:  

3796510 = 10010100010011012 

Компромиссом между интересами человека и машины являются системы 

счисления с основаниями, близкими к 10, но являющимися степенью двойки – 

8 и 16. 

В восьмеричной системе, совершенно естественно, 8 цифр – 0, 1, 2, 3, 4, 5, 

6, 7. Каждому разряду восьмеричной системы соответствуют 3 разряда 

двоичной системы, и переход от одной системы к другой очень прост: 

0 — 000  
2 — 010 
4 — 100 
6 — 110 

1 — 001  
3 — 011   
5 — 101    
7 — 111 

3796510 = 10010100010011012 =1121158 

Восьмеричная 
запись 
сейчас 
используется 
относительно 
редко. 

Шестнадцатеричная система, напротив, очень популярна.  

Соответствие между шестнадцатеричными цифрами и десятичными числами

16 
0 
1 
2 
3 
4 
5 
6 
7 
8 
9 
A 
B 
C 
D 
E 
F 

10 
0 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 

 
Соответствие между шестнадцатеричными цифрами и двоичным 

разложением: 

0 
— 
0000 
  4 
— 
0100 
  8 
— 
1000 
  C 
— 
1100 

1 
— 
0001 
  5 
— 
0101 
  9 
— 
1001 
  D 
— 
1101 

2 
— 
0010 
  6 
— 
0110 
  A 
— 
1010 
  E 
— 
1110 

3 
— 
0011 
  7 
— 
0111 
  В 
— 
1011 
  F 
— 
1111 

3796510 = 10010100010011012 =1121158 = 944D16 

2. Кодирование текста 

Текст – это последовательность символов, входящих в некоторый 

алфавит. Кодирование текста сводится к двоичному кодированию алфавита, на 

основе которого он построен. Чаще всего применяется байтовое кодирование 

алфавита. В этом случае максимальная мощность алфавита составляет 256 

символов. Такой алфавит может содержать два набора буквенных символов 

(например, русский и латинский), цифры, знаки препинания и математические 

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

алфавита является код ASCII. 

ASCII – это аббревиатура для American Standard Code for Information 

Interchange. Он стал мировым стандартом кодировки для практически всех 

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

причем стандарт фиксирует верхнюю половину таблицы с кодами от 0 до 127. 

Представив байт двумя 16-ми цифрами, в таблице представлены коды от 

00 до 7F.  

 
0 
1 2 3 4 5 
6 7 
8 9 A B
C D E
F

0  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

1  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

2 sp ! 
“ # $ % & ^ 
( 
) 
* + . 
, 
- 
/ 

3 0 
1 2 3 4 5 
6 7 
8 9  
 
 
 
 
 

4 @ A B C D E F G H I 
J 
K L
M N O

5 P 
Q R S
T
U
V
W X Y Z
 
 
 
 
 

6 ` 
a 
b c d e 
f 
g 
h i 
j 
k l 
m
n o 

7 p 
q r 
s t 
u 
v w x y z 
 
 
 
 
 

Первые две строчки заполнены служебными символами (типа возврата 

каретки, перевода строки, табуляции, звонка, конца передачи). Следующая 

строка начинается с 20 – кода пробела. Дальше идут различные специальные 

знаки. Дальше идет строка цифр: от 30 для 0 до 39 для 9. Остаток заполнен 

спецзнаками. Строки 4 и 5 заполнены прописными латинскими буквами: 40 для 

@, 41 для A и т. д. вплоть до 5A для Z. Строки 6 и 7 аналогично заполнены 

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

можно посмотреть в справочнике.