Основы кодирования информации в проектах LabVIEW

А. П. Горбенко, В. Т. Корниенко 

Основы кодирования
информации в проектах
LabVIEW

                    Учебно-методическое пособие

Москва 
Берлин 
2020 

УДК 004.312.26(075.8) + 004.4(075.8) 

Горбенко А. П., Корниенко В. Т. Основы кодирования информации в 
проектах LabVIEW: учебно-методическое пособие / А. П. Горбенко, 
В.Т. Корниенко. — Москва ; Берлин : Директ-Медиа, 2020. — 71 с.

ISBN 978-5-4475-9732-0

 Рассмотрены вопросы кодирования информации с использованием 
технологии 
виртуальных 
приборов 
LabVIEW. 
Изложены 
принципы 
формирования сжимающего кода Хаффмана, помехоустойчивых кодов 
Хемминга, Рида−Маллера и сверточного кода, а также примеры создания 
виртуальных приборов LabVIEW кодеров и декодеров рассмотренных кодов 
в приложениях систем передачи информации. 
Предназначено для студентов радиотехнических специальностей для 
изучения разделов дисциплин "Алгоритмы кодирования и шифрования 
информации" и "Основы кодирования и шифрования информации". 

Табл. 7 . Ил. 40. Библиогр.: 23 назв. 

Рецензент Макаров А. М., д-р техн. наук, профессор, зав. кафедрой 
комплексной защиты информации и стандартизации Северо-Кавказского 
федерального университета. 

ISBN 978-5-4475-9733-7      © Корниенко В.Т., текст, 2020
                                               © Издательство «Директ-Медиа», оформление, 2020

Содержание 

ВВЕДЕНИЕ ......................................................................................................................4 

1. АЛГОРИТМ КОДИРОВАНИЯ ХАФФМАНА...........................................................6

1.1. Цель.........................................................................................................................6 

1.2. Краткие теоретические сведения...........................................................................6 

1.3. Задания для самостоятельной проработки..........................................................14 

1.4. Рекомендации к выполнению лабораторного задания.......................................14 

Контрольные вопросы.................................................................................................26 

2. АЛГОРИТМ КОДИРОВАНИЯ ХЕММИНГА .........................................................27

2.1. Цель.......................................................................................................................27 

2.2. Краткие теоретические сведения.........................................................................27 

2.3. Задания для самостоятельной проработки..........................................................36 

2.4. Рекомендации к выполнению лабораторного задания.......................................37 

Контрольные вопросы.................................................................................................43 

3. АЛГОРИТМ КОДИРОВАНИЯ РИДА−МАЛЛЕРА.................................................45

3.1. Цель.......................................................................................................................45 

3.2. Краткие теоретические сведения.........................................................................45 

3.3. Задания для самостоятельной проработки..........................................................50 

3.4. Рекомендации к выполнению лабораторного задания.......................................51 

Контрольные вопросы.................................................................................................53 

4. СВЕРТОЧНЫЕ КОДЫ ..............................................................................................54

4.1.Цель........................................................................................................................54 

4.2. Краткие теоретические сведения.........................................................................54 

4.3. Задания для самостоятельной проработки..........................................................62 

4.4. Рекомендации к выполнению лабораторного задания.......................................62 

Контрольные вопросы.................................................................................................67 

БИБЛИОГРАФИЧЕСКИЙ СПИСОК ...........................................................................69 

ВВЕДЕНИЕ 

Предлагаемое учебно-методическое пособие необходимо для усвоения 

материала, преподаваемого по дисциплинам "Алгоритмы кодирования и 

шифрования 
информации" 
и 
"Основы 
кодирования 
и 
шифрования 

информации". Материал пособия составлен в соответствии с требованиями 

стандарта специальности «Радиоэлектронные системы и комплексы» по данной 

дисциплине. В основу пособия положены основополагающие принципы 

построения цифровых систем связи. 

Для успешного усвоения разделов дисциплины необходимы знания, 

полученные 
студентами 
при 
изучении 
предшествовавших 
дисциплин, 

касающихся 
высшей 
математики, 
информатики, 
теории 
электросвязи, 

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

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

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

Цель преподавания дисциплины: 

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

особенностях различных видов кодов; 

– сформировать у студентов системы научных понятий и научно 

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

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

связи; 

– обеспечить 
студентов 
профессиональным 
владением 
основами 

построения и расчета характеристик кодеков радиотехнических систем 

средствами LabVIEW. 

В результате изучения дисциплины студенты должны: 

• освоить принципы построения кодеров и декодеров и их основные 

функции; 

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

средствами LabVIEW; 

• освоить навыки проектирования кодеров и декодеров с помощью 

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

цифровой обработки сигналов. 

При решении задач проектирования кодеров и декодеров определяются 

основные 
показатели 
эффективности 
их 
функционирования, 
которые 

рассмотрены 
в 
отдельных 
разделах. 
Для 
выполнения 
заданий 
при 

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

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

программирования LabVIEW фирмы National Instruments. 

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

изложены основы сжимающего кода Хаффмана и основы алгоритмического 

проектирование кодера и декодера средствами LabVIEW. 

Во втором разделе изложены основы помехоустойчивого кода Хемминга 

и алгоритмическое проектирование его кодера и декодера при создании 

виртуального прибора LabVIEW. 

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

высокой корректирующей способностью на примере кода Рида−Маллера и 

алгоритмическое проектирование его кодера при создании виртуального 

прибора LabVIEW. 

В 
четвертом 
разделе 
рассмотрены 
основы 
помехоустойчивого 

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

кодера и декодера при создании виртуального прибора LabVIEW. 

Перед выполнением заданий для самостоятельной проработки полезно 

ознакомиться с базовой частью основ программирования в LabVIEW. 

1. АЛГОРИТМ КОДИРОВАНИЯ ХАФФМАНА 
 

1.1. Цель  

Изучение принципа построения кодера Хаффмана и его алгоритмической 

модели в LabVIEW. 

 

1.2. Краткие теоретические сведения 

Алгоритм кодирования Хаффмана – адаптивный алгоритм оптимального 

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

Префиксный 
код 
– 
код, 
обеспечивающий 
запись 
кодового 
слова 

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

сообщения, т.е. префиксным кодом является тот, в котором для любого слова a 

не существует слова ab, где b – любая последовательность символов (никакое 

более короткое слово не является началом другого более длинного слова кода). 

Префиксные 
коды 
широко 
используются 
в 
различных 
областях 

информационных 
технологий, 
на 
них 
основаны 
алгоритмы 
сжатия 

информации, используемые в различных протоколах передачи данных. К 

префиксным кодам относятся такие распространённые коды, как Юникод, Код 

Хаффмана, Код Фибоначчи и др. [1].  

Например, код, состоящий из слов 0, 10 и 11, является префиксным, и 

сообщение 01001101110 можно разбить на слова единственным образом: 0 10 0 

11 0 11 10. Код, состоящий из слов 0, 10, 11 и 100, префиксным не является, и 

то же сообщение 01001101110 можно трактовать несколькими способами: 0 10 

0 11 0 11 10 и 0 100 11 0 11 10. 

Применение кода Хаффмана. Алгоритмы сжатия нашли широкое 

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

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

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

сжатия по алгоритму Хаффмана основывается на построении кодовой таблицы, 

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

пропорциональна 
частоте 
появления 
этого 
символа. 
Существуют 
две 

разновидности вероятностных методов, различающихся способом определения 

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

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

началом 
процесса 
сжатия 
(используется 
при 
сжатии 
изображений); 

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

все время меняется и по мере считывания нового блока данных происходит 

перерасчет начальных значений частот (используется в протоколах связи).  

Алгоритм кодирования Хаффмана используется в протоколах сжатия 

данных MNP (Microcom Networking Protocol), используемых в модемах. 

Принцип работы MNP-модема заключается в использовании при передаче 

информации блоков переменной длины. Модем принимает от компьютера 

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

по линии другому MNP-модему. При сборке этого пакета информации 

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

блока можно изменять от 64 до 256 байт с шагом в 64 байта, причем, на 

высококачественных телефонных линиях можно использовать блоки большей 

длины, что увеличивает скорость передачи [2]. 

MNP-модемы различаются по классам – от 1 до 9. Каждый класс 

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

расширенными возможностями. Для более совершенных классов требуется 

более совершенное аппаратное обеспечение, более мощный процессор для 

микроконтролера модема. Широко используются MNP5- и  MNP7-протоколы, 

отличающиеся от более совершенного протокола V.42bis и имеющие 

совместимость. 

Протокол MNP5 реализует комбинацию адаптивного кодирования с 

применением кода Хаффмана и группового кодирования. Реальная скорость их 

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

данных модемом.  

Протокол MNP7 использует более эффективный (по сравнению с MNP5) 

алгоритм сжатия данных и позволяет достичь коэффициента сжатия порядка 

3,1. MNP7 использует улучшенную форму кодирования методом Хаффмана в 

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

последовательностей минимально возможной длины.  

Протокол V.42bis использует алгоритм словарного типа Лемпеля-Зива
Уэлча 
(LZW-алгоритме), 
обеспечивая 
преимущество 
достижения 

коэффициента сжатия 4,1 файлов с оптимальной структурой.  

Другое применение алгоритма Хаффмана известно при сжатии 24-битных 

изображений в JPEG (Joint Photographic Expert Group – подразделение в рамках 

ISO – Международной организации по стандартизации). Алгоритм JPEG 

основан на дискретном косинусоидальном преобразовании – ДКП (Discrete
Cosine Transform – DCT), применяемом к матрице изображения для получения 

некоторой новой матрицы коэффициентов. ДКП раскладывает изображение по 

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

Структура алгоритма JPEG [2] состоит из следующих этапов, последний 

из которых – это алгоритм Хаффмана: 

–  изображение из цветового пространства RGB преобразуется в цветовое 

пространство YCrCb (иногда называют YUV). В нем Y – яркостная 

составляющая, а Cr, Cb – компоненты, отвечающие за цвет (хроматический 

красный и хроматический синий);  

–  исходное изображение разбивается на матрицы 8 x 8;  

–  применяется ДКП к каждой рабочей матрице;  

–  для каждой компоненты (Y, U и V) задается своя матрица квантования 

(на этом шаге осуществляется управление степенью сжатия, и происходят 

самые большие потери); 

–  матрица 8 x 8 преобразуется в 64-элементный вектор при помощи 

"зигзаг"-сканирования;  

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

кодирования; 

–  производится кодированием по Хаффману с фиксированной таблицей. 

Структура алгоритма Хаффмана  при заданном наборе символов, 

представляющих алфавит передаваемого сообщения ABCDEFGH, выглядит 

следующим образом [1]: