Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

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

Покупка
Артикул: 801960.01.99
Доступ онлайн
108 ₽
В корзину
Рассмотрены вопросы кодирования информации с использованием технологии виртуальных приборов LabVIEW. Изложены принципы формирования сжимающего кода Хаффмана, помехоустойчивых кодов Хемминга, Рида-Маллера и сверточного кода, а также примеры создания виртуальных приборов LabVIEW кодеров и декодеров рассмотренных кодов в приложениях систем передачи информации. Предназначено для студентов радиотехнических специальностей для изучения разделов дисциплин "Алгоритмы кодирования и шифрования информации" и "Основы кодирования и шифрования информации".
Горбенко, А. П. Основы кодирования информации в проектах LabVIEW / А. П. Горбенко, В. Т. Корниенко. - Москва : Директ-Медиа, 2020. - 71 с. - ISBN 978-5-4475-9732-0. - Текст : электронный. - URL: https://znanium.com/catalog/product/1988381 (дата обращения: 28.03.2024). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов. Для полноценной работы с документом, пожалуйста, перейдите в ридер.
А. П. Горбенко, В. Т. Корниенко 

Основы кодирования
информации в проектах
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]: 

1. Формируется первый (к = 1) столбец, где все буквы алфавита 

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

исходном, подлежащем кодированию файле. В соответствие каждой букве 

ставится значение вероятности. Две буквы, занявшие в столбце предпоследнюю 

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

символами соответственно "0" и "1".  

2 При известном к-м столбце строится (к + 1)-й столбик по тому же 

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

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

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

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

3. Этот процесс продолжается до тех пор, пока в очередном столбце под 

номером к – n (n – число букв в алфавите) не окажется одна-единственная 

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

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

контрольную функцию.  

4. Для определения кодового набора, соответствующего интересующей 

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

предыдущим столбцам, рассматривая каждый раз только те буквы, которые 

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

Хаффману. Если в указанном участке очередного столбца оказывается 

интересующая буква или какая-либо составная буква, включающая эту букву, 

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

которым отмечена эта буква или включающая ее составная буква. Этот процесс 

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

интересующая буква, как показано на рис.1.  

Например, для кодового набора, соответствующего букве Е, при 

движении от столбца с номером к = 8 к столбцу с номером к = 7, в котором 

составная буква (ACDEFGH), содержащая букву Е, дает основание для записи в 

первом разряде кодового набора буквы Е символа "0". В следующем столбце 

буква Е встречается в составной букве (EFGH) в столбце под номером к = 6. 

Поэтому во второй позиции кодового набора буквы Е записываем символ 0. В 

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

буквы Е записать символ 1. Далее буква Е ниже встречается во втором столбце. 

Исходя из этого четвертую позицию кодового набора заполняем символом 0. В 

итоге букве Е приписываем кодовый набор 0010. Поступая аналогичным 

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

алфавита, как приведено в табл.1 [1]. 

 

 

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

Хаффмана 

 

Особенности алгоритма Хаффмана. Из оптимальности алгоритма 

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

Например, кодирование букв А, В, С, D и Е при следующих значениях 

вероятностей их встречаемости: Р(А) = 0,49; P(D) = 0,16; Р(В) = 0,17; Р(Е) = 

=0,01; Р (С) = 0,17 с помощью алгоритма кодирования Хаффмана дает 

результат, приведенный в табл. 2. 

Таблица 1  

Сформированный код Хаффмана для заданного алфавита сообщения  

Буква 
Двоичный код 

А 
011 

В 
1 

С 
0100 

D 
0101 

Е 
0010 

F 
0011 

G 
0000 

Н 
0001 

 

Таблица 2  

Сформированный код Хаффмана для заданного алфавита сообщения  

Буква 
Двоичный код 

А 
1 

В 
01 

С 
000 

D 
0010 

Е 
0001 

 

Так как в процессе кодирования сообщениям сопоставляются только 

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

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

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

максимальной 
вероятностью 
появления 
соответствует 
минимальная 

Доступ онлайн
108 ₽
В корзину